Completely reimplemented the menu handling

The old code started to bit-rot and suffered from severe
code duplication. The new implementation tried to fix that
by treating generated menu items as immutable. This
dramatically reduced the amount of duplicated code and
allowed us to get rid of most cache structures. Hopefully
this implementation will prove to be less buggy and more
maintainable in the long run.