Refactor MenuTree to be simpler and have full unit test coverage

This was split off from #1805054-118: Cache localized, access filtered, URL resolved, and rendered menu trees.

msonnabaum reviewed this over at #1805054-121: Cache localized, access filtered, URL resolved, and rendered menu trees:

3. It took me a while to get the whole menu tree manipulator concept, but it still looks considerably simpler than what was there before. A few things threw me, but I think they are fixable.

$parameters->appendManipulator('menu_link.cacheable_access_check_tree_manipulator:checkNonDynamicAccess')
    ->appendManipulator('menu_link.default_tree_manipulators:translate')
    ->appendManipulator('menu_link.default_tree_manipulators:generateIndexAndSort')
    ->appendManipulator('menu_link.default_tree_manipulators:setHrefPropertyIfExternal')
    ->appendManipulator('menu_link.default_tree_manipulators:setTreeItemClass');

Using the servicename:method notation with two different services makes me think that this is an extensible system, where contrib could define new services to be added to menus in core. I don't think this is the case, which makes sense, but I think we can suggest it more in code.

This is indeed an extensible system; for example, the toolbar module has its own manipulator: toolbar_menu_navigation_links(). Similarly, contirb modules may want to apply their own tree manipulators.

You're right that existing rendered menus (e.g. the one in the menu administration area) cannot be manipulated by default, but that could be changed. And in the case of for example the menu block (SystemMenuBlock), it's possible for a contrib module to override that default implementation with a different one that applies different/additional menu tree manipulators.

I hope that clarified it for you.

pwolanin and I discussed in detail (3.5 hour long chat detail) how to move this forward and combine with #2256521: [META] New plan, Phase 2: Implement menu links as plugins, including static admin links and views, and custom links with menu_link_content entity, all managed via menu_ui module.

Even though pwolanin set out to refactor just Menu Link entities/storage, and I set out to just add render caching of menu trees (in #1805054: Cache localized, access filtered, URL resolved, and rendered menu trees), and those logically have close to zero overlap, the sad reality is that the menu system in HEAD is in a poor state. Due to the tight coupling in MenuTree, where lots of things live together that don't belong together, and worse yet, MenuTree calling out to procedural functions in menu.inc, the unfortunate consequence is that we have both cleaned up in different ways, with different goals in mind.

So, alas, even though we both had best intentions, we're now left to somehow reconcile both patches.

After careful deliberation, we've agreed to move forward by:

1. Closing #2289033: Refactor MenuTree to be simpler and have full unit test coverage (this issue) as a duplicate.
2. "Upgrading" #2256521: [META] New plan, Phase 2: Implement menu links as plugins, including static admin links and views, and custom links with menu_link_content entity, all managed via menu_ui module to incorporate the logic of that closed issue.
3. That will then still allow the main "render tree caching" logic over at #1805054-123: Cache localized, access filtered, URL resolved, and rendered menu trees to work, and apply relatively cleanly. Conceptually, this patch is "just" merged with that in #2256521.

We both began the discussion sad and frustrated, and came out hopeful — particularly because we should be able to move faster by combining our efforts on the same patch :) Particularly, we both want this mammoth, long overdue work to be behind us :P

The plan

In short: the following will be moved into pwolanin's patch from mine: MenuTreeItem, MenuTreeParameters, the menu tree manipulators concept, DefaultMenuTreeManipulators, MenuTree::render() (which brings all rendered menus to a single template: menu-tree.html.twig), the use of MenuTreeParameters everywhere and all added unit test coverage.

The rendering process becomes:

1. $tree = build($menu_name, $parameters) or buildSubtree($menu_name, $parent)
2. $tree = transform($tree, $manipulators)
3. $rendered = render($tree)

The plan: detail

pwolanin and I have also discussed how to do this exactly. Key to this all is that we agree on MenuTreeInterface (pwolanin renamed this to MenuLinkTree), so that's what we discussed in detail, and where we've agreed on how to combine everything.

In pwolanin's latest patch, over at #2256521-71: [META] New plan, Phase 2: Implement menu links as plugins, including static admin links and views, and custom links with menu_link_content entity, all managed via menu_ui module, it looks like this:

<?php

interface MenuLinkTreeInterface {

  public function maxDepth();
  public function buildRenderTree($tree);
  public function getActiveTrailIds($menu_name);
  public function getActiveMenuNames();
  public function setActiveMenuNames(array $menu_names);
  public function buildPageData($menu_name, $max_depth = NULL);
  public function buildAllData($menu_name, $id = NULL, $max_depth = NULL);
  public function buildTree($menu_name, array $parameters = array());
  public function buildSubtree($id, $max_relative_depth = NULL);
  public function getChildLinks($id, $max_relative_depth = NULL);
  public function menuLinkGetPreferred($route_name = NULL, array $route_parameters = array(), $selected_menu = NULL);
  public function getParentSelectOptions($id = '', array $menus = NULL);
  public function parentSelectElement($menu_parent, $id = '', array $menus = NULL);
  public function getMenuOptions(array $menu_names = NULL);
  public function getParentDepthLimit($id);
  public function resetStaticCache();

}

And we're going to refactor that to this, where "commented = planned to be deleted":

<?php

interface MenuLinkTreeInterface {

  public function maxDepth();
  //public function buildRenderTree($tree);
  public function render(MenuTreeItem[] $tree);
  //public function buildPageData($menu_name, $max_depth = NULL);
  //public function buildAllData($menu_name, $id = NULL, $max_depth = NULL);
  //public function buildTree($menu_name, array $parameters = array());
  public function build($menu_name, MenuTreeParameters $parameters);
  public function transform(MenuTreeItem[] $tree, array $manipulators);
  public function buildSubtree($id, $max_relative_depth = NULL);
  // @todo Reconsider later, after the above changes have been made.
  public function getChildLinks($id, $max_relative_depth = NULL);
  //public function resetStaticCache();

}

interface MenuActiveTrailInterface {
  
  public function getActiveTrailIds($menu_name);
  public function getActiveMenuNames();
  public function setActiveMenuNames(array $menu_names);
  public function menuLinkGetPreferred($route_name = NULL, array $route_parameters = array(), $selected_menu = NULL);
  
}

interface MenuParentFormSelectorInterface {

  //public function getParentSelectOptions($id = '', array $menus = NULL);
  public function parentSelectElement($menu_parent, $id = '', array $menus = NULL);
  //public function getMenuOptions(array $menu_names = NULL);
  //public function getParentDepthLimit($id);
  
}

Those changes amount to:

1. Introducing a value object to represent nodes (in the CS sense, not the Drupal sense) in the menu tree; I called them MenuTreeItem, on par with existing terminology in HEAD. The name and exact properties may change, but the concept is needed.
2. Making MenuLinkTree as focused as MenuTree in my patch. Notes:
   1. The MenuLinkTree::maxDepth() method is the successor for the MENU_MAX_DEPTH constant. We'd both like to get rid of it, but can't think of a better place for now. It's minor enough that it doesn't matter in the grand scheme of things, so barring a sudden insight, this is acceptable.
   2. Just like in my patch, buildPageData(), buildAllData() and buildTree() are removed in favor of a single build() method, which accepts parameters.
   3. We introduce the "tree manipulators" concept from my patch. DefaultMenuTreeManipulators can almost be copy/pasted verbatim from my patch, including test coverage.
   4. We introduce a MenuTreeParameters value object (just like in my patch), but pwolanin preferred to have the tree manipulators to not be defined as part of the MenuTreeParameters. This is a distinction that is also fine by me: MenuTreeParameters is then solely for determining which menu links to load, and the tree manipulators are applied as part of a new transform() step that accepts the tree manipulators.
   5. pwolanin strongly felt that buildSubtree() was necessary/valuable (to get the tree below a given parent item). This will just be an alias:buildSubtree($menu_name, $parent) === build($menu_name, $parameters = array('parent' => $parent)) (pseudocode).
   6. To neither of us, it was clear whether getChildLinks() belonged in the interface/was worth keeping around, but we figured that'd become clearer once all of the above had been done.
   7. The resetStaticCache() method was already planned to be removed, and will be.
3. Splitting off the methods relating to the active trail into MenuActiveTrail(Interface). This is like in my patch. But unlike in my patch, pwolanin has already done the work to get rid of the procedural menu.inc/menu_link_get_preferred() (YAY!) — though we probably want a better name for the method now :)
4. Moving the methods relating to presenting a menu tree in some shape in a form (to select a parent menu item, primarily) into MenuParentFormSelectorInterface. We both would like to remove this, but since we want modules to (finally) be able to override this form item cleanly (e.g. to use something that scales better, like Hierarchical Select), we need this to be a service.
   All other methods should go away though, but that may only be addressed in a follow-up issue.

@pwolanin: if I misrepresented anything, ping me, and I'll correct it.

Oh, yes, absolutely. I forgot to close this one. Thanks :)