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);
    }

}