After merging the menus, the result should be a single menu layout description. For each <Menu>, we have a list of directories where desktop entries can be found, a list of directories where directory entries can be found, and a series of <Include> and <Exclude> directives.

For each <Menu> element, build a pool of desktop entries by collecting entries found in each <AppDir> for the menu element. If two entries have the same desktop-file id, the entry for the earlier (closer to the top of the file) <AppDir> must be discarded. Next, add to the pool the entries for any <AppDir>s specified by ancestor <Menu> elements. If a parent menu has a duplicate entry (same desktop-file id), the entry for the child menu has priority.

Next, walk through all <Include> and <Exclude> statements. For each <Include>, match the rules against the pool of all desktop entries. For each desktop entry that matches one of the rules, add it to the menu to be displayed. For each <Exclude>, match the rules against the currently-included desktop entries. For each desktop entry that matches, remove it again from the menu.

Two passes are necessary, once for regular menus, and once for <OnlyUnallocated> menus.

The result is a tree of desktop entries, of course.