class MenuLinkTree

class MenuLinkTree implements MenuLinkTreeInterface {
  
  /**
   * The menu link tree storage.
   *
   * @var \Drupal\Core\Menu\MenuTreeStorageInterface
   */
  protected $treeStorage;
  
  /**
   * The menu link plugin manager.
   *
   * @var \Drupal\Core\Menu\MenuLinkManagerInterface
   */
  protected $menuLinkManager;
  
  /**
   * The route provider to load routes by name.
   *
   * @var \Drupal\Core\Routing\RouteProviderInterface
   */
  protected $routeProvider;
  
  /**
   * The active menu trail service.
   *
   * @var \Drupal\Core\Menu\MenuActiveTrailInterface
   */
  protected $menuActiveTrail;
  
  /**
   * The controller resolver.
   *
   * @var \Drupal\Core\Controller\ControllerResolverInterface
   */
  protected $controllerResolver;
  
  /**
   * Constructs a \Drupal\Core\Menu\MenuLinkTree object.
   *
   * @param \Drupal\Core\Menu\MenuTreeStorageInterface $tree_storage
   *   The menu link tree storage.
   * @param \Drupal\Core\Menu\MenuLinkManagerInterface $menu_link_manager
   *   The menu link plugin manager.
   * @param \Drupal\Core\Routing\RouteProviderInterface $route_provider
   *   The route provider to load routes by name.
   * @param \Drupal\Core\Menu\MenuActiveTrailInterface $menu_active_trail
   *   The active menu trail service.
   * @param \Drupal\Core\Controller\ControllerResolverInterface $controller_resolver
   *   The controller resolver.
   */
  public function __construct(MenuTreeStorageInterface $tree_storage, MenuLinkManagerInterface $menu_link_manager, RouteProviderInterface $route_provider, MenuActiveTrailInterface $menu_active_trail, ControllerResolverInterface $controller_resolver) {
    $this->treeStorage = $tree_storage;
    $this->menuLinkManager = $menu_link_manager;
    $this->routeProvider = $route_provider;
    $this->menuActiveTrail = $menu_active_trail;
    $this->controllerResolver = $controller_resolver;
  }
  
  /**
   * {@inheritdoc}
   */
  public function getCurrentRouteMenuTreeParameters($menu_name) {
    $active_trail = $this->menuActiveTrail
      ->getActiveTrailIds($menu_name);
    $parameters = new MenuTreeParameters();
    $parameters->setActiveTrail($active_trail)
      ->addExpandedParents($active_trail)
      ->addExpandedParents($this->treeStorage
      ->getExpanded($menu_name, $active_trail));
    return $parameters;
  }
  
  /**
   * {@inheritdoc}
   */
  public function load($menu_name, MenuTreeParameters $parameters) {
    $data = $this->treeStorage
      ->loadTreeData($menu_name, $parameters);
    // Pre-load all the route objects in the tree for access checks.
    if ($data['route_names'] && $this->routeProvider instanceof PreloadableRouteProviderInterface) {
      $this->routeProvider
        ->getRoutesByNames($data['route_names']);
    }
    return $this->createInstances($data['tree']);
  }
  
  /**
   * Returns a tree containing of MenuLinkTreeElement based upon tree data.
   *
   * This method converts the tree representation as array coming from the tree
   * storage to a tree containing a list of MenuLinkTreeElement[].
   *
   * @param array $data_tree
   *   The tree data coming from the menu tree storage.
   *
   * @return \Drupal\Core\Menu\MenuLinkTreeElement[]
   *   An array containing the elements of a menu tree.
   */
  protected function createInstances(array $data_tree) {
    $tree = [];
    foreach ($data_tree as $key => $element) {
      $subtree = $this->createInstances($element['subtree']);
      // Build a MenuLinkTreeElement out of the menu tree link definition:
      // transform the tree link definition into a link definition and store
      // tree metadata.
      $tree[$key] = new MenuLinkTreeElement($this->menuLinkManager
        ->createInstance($element['definition']['id']), (bool) $element['has_children'], (int) $element['depth'], (bool) $element['in_active_trail'], $subtree);
    }
    return $tree;
  }
  
  /**
   * {@inheritdoc}
   */
  public function transform(array $tree, array $manipulators) {
    foreach ($manipulators as $manipulator) {
      $callable = $manipulator['callable'];
      $callable = $this->controllerResolver
        ->getControllerFromDefinition($callable);
      // Prepare the arguments for the menu tree manipulator callable; the first
      // argument is always the menu link tree.
      if (isset($manipulator['args'])) {
        array_unshift($manipulator['args'], $tree);
        $tree = call_user_func_array($callable, $manipulator['args']);
      }
      else {
        $tree = call_user_func($callable, $tree);
      }
    }
    return $tree;
  }
  
  /**
   * {@inheritdoc}
   */
  public function build(array $tree) {
    $tree_access_cacheability = new CacheableMetadata();
    $tree_link_cacheability = new CacheableMetadata();
    $items = $this->buildItems($tree, $tree_access_cacheability, $tree_link_cacheability);
    $build = [];
    // Apply the tree-wide gathered access cacheability metadata and link
    // cacheability metadata to the render array. This ensures that the
    // rendered menu is varied by the cache contexts that the access results
    // and (dynamic) links depended upon, and invalidated by the cache tags
    // that may change the values of the access results and links.
    $tree_cacheability = $tree_access_cacheability->merge($tree_link_cacheability);
    $tree_cacheability->applyTo($build);
    if ($items) {
      // Make sure Drupal\Core\Render\Element::children() does not re-order the
      // links.
      $build['#sorted'] = TRUE;
      // Get the menu name from the last link.
      $item = end($items);
      $link = $item['original_link'];
      $menu_name = $link->getMenuName();
      // Add the theme wrapper for outer markup.
      // Allow menu-specific theme overrides.
      $build['#theme'] = 'menu__' . strtr($menu_name, '-', '_');
      $build['#menu_name'] = $menu_name;
      $build['#items'] = $items;
      // Set cache tag.
      $build['#cache']['tags'][] = 'config:system.menu.' . $menu_name;
    }
    return $build;
  }
  
  /**
   * Builds the #items property for a menu tree's renderable array.
   *
   * Helper function for ::build().
   *
   * @param \Drupal\Core\Menu\MenuLinkTreeElement[] $tree
   *   A data structure representing the tree, as returned from
   *   MenuLinkTreeInterface::load().
   * @param \Drupal\Core\Cache\CacheableMetadata &$tree_access_cacheability
   *   Internal use only. The aggregated cacheability metadata for the access
   *   results across the entire tree. Used when rendering the root level.
   * @param \Drupal\Core\Cache\CacheableMetadata &$tree_link_cacheability
   *   Internal use only. The aggregated cacheability metadata for the menu
   *   links across the entire tree. Used when rendering the root level.
   *
   * @return array
   *   The value to use for the #items property of a renderable menu.
   *
   * @throws \DomainException
   */
  protected function buildItems(array $tree, CacheableMetadata &$tree_access_cacheability, CacheableMetadata &$tree_link_cacheability) {
    $items = [];
    foreach ($tree as $data) {
      /** @var \Drupal\Core\Menu\MenuLinkInterface $link */
      $link = $data->link;
      // Generally we only deal with visible links, but just in case.
      if (!$link->isEnabled()) {
        continue;
      }
      if ($data->access !== NULL && !$data->access instanceof AccessResultInterface) {
        throw new \DomainException('MenuLinkTreeElement::access must be either NULL or an AccessResultInterface object.');
      }
      // Gather the access cacheability of every item in the menu link tree,
      // including inaccessible items. This allows us to render cache the menu
      // tree, yet still automatically vary the rendered menu by the same cache
      // contexts that the access results vary by.
      // However, if $data->access is not an AccessResultInterface object, this
      // will still render the menu link, because this method does not want to
      // require access checking to be able to render a menu tree.
      if ($data->access instanceof AccessResultInterface) {
        $tree_access_cacheability = $tree_access_cacheability->merge(CacheableMetadata::createFromObject($data->access));
      }
      // Gather the cacheability of every item in the menu link tree. Some links
      // may be dynamic: they may have a dynamic text (e.g. a "Hi, <user>" link
      // text, which would vary by 'user' cache context), or a dynamic route
      // name or route parameters.
      $tree_link_cacheability = $tree_link_cacheability->merge(CacheableMetadata::createFromObject($data->link));
      // Only render accessible links.
      if ($data->access instanceof AccessResultInterface && !$data->access
        ->isAllowed()) {
        continue;
      }
      $element = [];
      // Set a variable for the <li> tag. Only set 'expanded' to true if the
      // link also has visible children within the current tree.
      $element['is_expanded'] = FALSE;
      $element['is_collapsed'] = FALSE;
      if ($data->hasChildren && !empty($data->subtree)) {
        $element['is_expanded'] = TRUE;
      }
      elseif ($data->hasChildren) {
        $element['is_collapsed'] = TRUE;
      }
      // Set a helper variable to indicate whether the link is in the active
      // trail.
      $element['in_active_trail'] = FALSE;
      if ($data->inActiveTrail) {
        $element['in_active_trail'] = TRUE;
      }
      // Note: links are rendered in the menu.html.twig template; and they
      // automatically bubble their associated cacheability metadata.
      $element['attributes'] = new Attribute();
      $element['title'] = $link->getTitle();
      $element['url'] = $link->getUrlObject();
      $element['url']->setOption('set_active_class', TRUE);
      $element['below'] = $data->subtree ? $this->buildItems($data->subtree, $tree_access_cacheability, $tree_link_cacheability) : [];
      if (isset($data->options)) {
        $element['url']->setOptions(NestedArray::mergeDeep($element['url']->getOptions(), $data->options));
      }
      $element['original_link'] = $link;
      // Index using the link's unique ID.
      $items[$link->getPluginId()] = $element;
    }
    return $items;
  }
  
  /**
   * {@inheritdoc}
   */
  public function maxDepth() {
    return $this->treeStorage
      ->maxDepth();
  }
  
  /**
   * {@inheritdoc}
   */
  public function getSubtreeHeight($id) {
    return $this->treeStorage
      ->getSubtreeHeight($id);
  }
  
  /**
   * {@inheritdoc}
   */
  public function getExpanded($menu_name, array $parents) {
    return $this->treeStorage
      ->getExpanded($menu_name, $parents);
  }

}