core/lib/Drupal/Core/Cache/MemoryBackend.php       |   8 +-
 .../Core/Menu/DefaultMenuLinkTreeManipulators.php  |  80 ++++++-------
 core/lib/Drupal/Core/Menu/MenuLinkTree.php         |  27 ++---
 core/lib/Drupal/Core/Menu/MenuLinkTreeElement.php  | 124 +++++++++++++++++++++
 .../Drupal/Core/Menu/MenuParentFormSelector.php    |  10 +-
 core/lib/Drupal/Core/Menu/MenuTreeStorage.php      |  72 ++++++------
 core/modules/menu_ui/menu_ui.admin.inc             |   2 +-
 core/modules/menu_ui/src/MenuForm.php              |  76 ++++++-------
 .../system/src/Controller/SystemController.php     |  11 +-
 core/modules/system/src/SystemManager.php          |   8 +-
 .../Cache/GenericCacheBackendUnitTestBase.php      |   8 ++
 .../system/src/Tests/Menu/MenuLinkTreeTest.php     |  31 +++---
 .../system/src/Tests/Menu/MenuTreeStorageTest.php  |  38 +++----
 core/modules/system/src/Tests/System/AdminTest.php |   6 +-
 core/modules/system/system.module                  |  12 +-
 core/modules/toolbar/toolbar.module                |  40 +++----
 .../Menu/DefaultMenuLinkTreeManipulatorsTest.php   |  73 ++++++------
 .../Tests/Core/Menu/MenuLinkTreeElementTest.php    |  63 +++++++++++
 18 files changed, 442 insertions(+), 247 deletions(-)

diff --git a/core/lib/Drupal/Core/Cache/MemoryBackend.php b/core/lib/Drupal/Core/Cache/MemoryBackend.php
index 8cd759c..55d9a7b 100644
--- a/core/lib/Drupal/Core/Cache/MemoryBackend.php
+++ b/core/lib/Drupal/Core/Cache/MemoryBackend.php
@@ -38,7 +38,7 @@ public function __construct($bin) {
    */
   public function get($cid, $allow_invalid = FALSE) {
     if (isset($this->cache[$cid])) {
-      return $this->prepareItem($this->cache[$cid], $allow_invalid);
+      return $this->prepareItem(clone $this->cache[$cid], $allow_invalid);
     }
     else {
       return FALSE;
@@ -54,7 +54,7 @@ public function getMultiple(&$cids, $allow_invalid = FALSE) {
     $items = array_intersect_key($this->cache, array_flip($cids));
 
     foreach ($items as $item) {
-      $item = $this->prepareItem($item, $allow_invalid);
+      $item = $this->prepareItem(clone $item, $allow_invalid);
       if ($item) {
         $ret[$item->cid] = $item;
       }
@@ -83,6 +83,8 @@ protected function prepareItem($cache, $allow_invalid) {
       return FALSE;
     }
 
+    $cache->data = unserialize($cache->data);
+
     // Check expire time.
     $cache->valid = $cache->expire == Cache::PERMANENT || $cache->expire >= REQUEST_TIME;
 
@@ -99,7 +101,7 @@ protected function prepareItem($cache, $allow_invalid) {
   public function set($cid, $data, $expire = Cache::PERMANENT, array $tags = array()) {
     $this->cache[$cid] = (object) array(
       'cid' => $cid,
-      'data' => $data,
+      'data' => serialize($data),
       'created' => REQUEST_TIME,
       'expire' => $expire,
       'tags' => $this->flattenTags($tags),
diff --git a/core/lib/Drupal/Core/Menu/DefaultMenuLinkTreeManipulators.php b/core/lib/Drupal/Core/Menu/DefaultMenuLinkTreeManipulators.php
index 9e3c484..266ee8e 100644
--- a/core/lib/Drupal/Core/Menu/DefaultMenuLinkTreeManipulators.php
+++ b/core/lib/Drupal/Core/Menu/DefaultMenuLinkTreeManipulators.php
@@ -38,31 +38,31 @@ public function __construct(AccessManager $access_manager, AccountInterface $acc
   }
 
   /**
-   * Tree manipulator that performs access checks.
+   * Menu link tree manipulator that performs access checks.
    *
-   * Removes menu items from the given menu tree whose links are inaccessible
+   * Removes menu links from the given menu tree whose links are inaccessible
    * for the current user, sets the 'access' property to TRUE on tree elements
    * that are accessible for the current user.
    *
    * Makes the resulting menu tree impossible to render cache, unless render
    * caching per user is acceptable.
    *
-   * @param array $tree
-   *   The menu tree to manipulate.
+   * @param \Drupal\Core\Menu\MenuLinkTreeElement[] $tree
+   *   The menu link tree to manipulate.
    *
-   * @return array
-   *   The manipulated menu tree.
+   * @return \Drupal\Core\Menu\MenuLinkTreeElement[]
+   *   The manipulated menu link tree.
    */
   public function checkAccess(array $tree) {
-    foreach ($tree as $key => $item) {
+    foreach ($tree as $key => $element) {
       // Other menu tree manipulators may already have calculated access, do
       // not overwrite the existing value in that case.
-      if (!isset($item['access'])) {
-        $tree[$key]['access'] = $this->menuLinkCheckAccess($item['link']);
+      if (!isset($element->access)) {
+        $tree[$key]->access = $this->menuLinkCheckAccess($element->link);
       }
-      if ($tree[$key]['access']) {
-        if ($tree[$key]['below']) {
-          $tree[$key]['below'] = $this->checkAccess($tree[$key]['below']);
+      if ($tree[$key]->access) {
+        if ($tree[$key]->subtree) {
+          $tree[$key]->subtree = $this->checkAccess($tree[$key]->subtree);
         }
       }
       else {
@@ -96,22 +96,22 @@ protected function menuLinkCheckAccess(MenuLinkInterface $instance) {
   }
 
   /**
-   * Tree manipulator that generates a unique index, and sorts by it.
+   * Menu link tree manipulator that generates a unique index, and sorts by it.
    *
-   * @param array $tree
-   *   The menu tree to manipulate.
+   * @param \Drupal\Core\Menu\MenuLinkTreeElement[] $tree
+   *   The menu link tree to manipulate.
    *
-   * @return array
-   *   The manipulated menu tree.
+   * @return \Drupal\Core\Menu\MenuLinkTreeElement[]
+   *   The manipulated menu link tree.
    */
   public function generateIndexAndSort(array $tree) {
     $new_tree = array();
     foreach ($tree as $key => $v) {
-      if ($tree[$key]['below']) {
-        $tree[$key]['below'] = $this->generateIndexAndSort($tree[$key]['below']);
+      if ($tree[$key]->subtree) {
+        $tree[$key]->subtree = $this->generateIndexAndSort($tree[$key]->subtree);
       }
       /** @var \Drupal\Core\Menu\MenuLinkInterface $instance */
-      $instance = $tree[$key]['link'];
+      $instance = $tree[$key]->link;
       // The weights are made a uniform 5 digits by adding 50000 as an offset.
       // After $this->menuLinkCheckAccess(), $instance->getTitle() has the
       // localized or translated title. Adding the plugin id to the end of the
@@ -123,44 +123,44 @@ public function generateIndexAndSort(array $tree) {
   }
 
   /**
-   * Tree manipulator that flattens the tree to a single level.
+   * Menu link tree manipulator that flattens the tree to a single level.
    *
-   * @param array $tree
-   *   The menu tree to manipulate.
+   * @param \Drupal\Core\Menu\MenuLinkTreeElement[] $tree
+   *   The menu link tree to manipulate.
    *
-   * @return array
-   *   The manipulated menu tree.
+   * @return \Drupal\Core\Menu\MenuLinkTreeElement[]
+   *   The manipulated menu link tree.
    */
   public function flatten(array $tree) {
-    foreach ($tree as $key => $item) {
-      if ($tree[$key]['below']) {
-        $tree += $this->flatten($tree[$key]['below']);
+    foreach ($tree as $key => $element) {
+      if ($tree[$key]->subtree) {
+        $tree += $this->flatten($tree[$key]->subtree);
       }
-      $tree[$key]['below'] = array();
+      $tree[$key]->subtree = array();
     }
     return $tree;
   }
 
   /**
-   * Tree manipulator that extracts a subtree of the active trail.
+   * Menu link tree manipulator that extracts a subtree of the active trail.
    *
-   * @param array $tree
-   *   The menu tree to manipulate.
+   * @param \Drupal\Core\Menu\MenuLinkTreeElement[] $tree
+   *   The menu link tree to manipulate.
    * @param int $level
    *   The level in the active trail to extract.
    *
-   * @return array
-   *   The manipulated menu tree.
+   * @return \Drupal\Core\Menu\MenuLinkTreeElement[]
+   *   The manipulated menu link tree.
    */
   public function extractSubtreeOfActiveTrail(array $tree, $level) {
     // Go down the active trail until the right level is reached.
     while ($level-- > 0 && $tree) {
-      // Loop through the current level's items until we find one that is in the
-      // active trail.
-      while ($item = array_shift($tree)) {
-        if (isset($item['in_active_trail']) && $item['in_active_trail']) {
-          // If the item is in the active trail, we continue in the subtree.
-          $tree = empty($item['below']) ? array() : $item['below'];
+      // Loop through the current level's elements  until we find one that is in
+      // the active trail.
+      while ($element = array_shift($tree)) {
+        if ($element->inActiveTrail) {
+          // If the element is in the active trail, we continue in the subtree.
+          $tree = $element->subtree;
           break;
         }
       }
diff --git a/core/lib/Drupal/Core/Menu/MenuLinkTree.php b/core/lib/Drupal/Core/Menu/MenuLinkTree.php
index 23cdc55..aae8c10 100644
--- a/core/lib/Drupal/Core/Menu/MenuLinkTree.php
+++ b/core/lib/Drupal/Core/Menu/MenuLinkTree.php
@@ -121,24 +121,24 @@ public function render($tree) {
     foreach ($tree as $data) {
       $class = array();
       /** @var \Drupal\Core\Menu\MenuLinkInterface $link */
-      $link = $data['link'];
+      $link = $data->link;
       // Generally we only deal with visible links, but just in case.
       if ($link->isHidden()) {
         continue;
       }
       // Set a class for the <li>-tag. Only set 'expanded' class if the link
       // also has visible children within the current tree.
-      if ($data['has_children'] && $data['below']) {
+      if ($data->hasChildren && !empty($data->subtree)) {
         $class[] = 'expanded';
       }
-      elseif ($data['has_children']) {
+      elseif ($data->hasChildren) {
         $class[] = 'collapsed';
       }
       else {
         $class[] = 'leaf';
       }
       // Set a class if the link is in the active trail.
-      if ($data['in_active_trail']) {
+      if ($data->inActiveTrail) {
         $class[] = 'active-trail';
       }
 
@@ -147,9 +147,9 @@ public function render($tree) {
       $element['#attributes']['class'] = $class;
       $element['#title'] = $link->getTitle();
       $element['#url'] = $link->getUrlObject();
-      $element['#below'] = $data['below'] ? $this->render($data['below']) : array();
-      if (isset($data['options'])) {
-        $element['#url']->setOptions(NestedArray::mergeDeep($element['#url']->getOptions(), $data['options']));
+      $element['#below'] = $data->subtree ? $this->render($data->subtree) : array();
+      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.
@@ -283,13 +283,14 @@ public function transform(array $tree, array $manipulators) {
    * Helper function that recursively instantiates the plugins.
    */
   protected function createInstances(&$tree) {
-    foreach ($tree as $key => $v) {
-      if ($tree[$key]['below']) {
-        $this->createInstances($tree[$key]['below']);
+    foreach (array_keys($tree) as $id) {
+      // Upcast the MenuLinkTreeElement's "link" property from a definition to
+      // an instance.
+      $tree[$id]->link = $this->menuLinkManager->createInstance($tree[$id]->link['id']);
+
+      if (!empty($tree[$id]->subtree)) {
+        $this->createInstances($tree[$id]->subtree);
       }
-      $tree[$key]['link'] = $this->menuLinkManager->createInstance($tree[$key]['definition']['id']);
-      $tree[$key]['access'] = NULL;
-      unset($tree[$key]['definition']);
     }
   }
 
diff --git a/core/lib/Drupal/Core/Menu/MenuLinkTreeElement.php b/core/lib/Drupal/Core/Menu/MenuLinkTreeElement.php
new file mode 100644
index 0000000..bbafaae
--- /dev/null
+++ b/core/lib/Drupal/Core/Menu/MenuLinkTreeElement.php
@@ -0,0 +1,124 @@
+<?php
+
+/**
+ * @file
+ * Contains \Drupal\Core\Menu\MenuLinkTreeElement.
+ */
+
+namespace Drupal\Core\Menu;
+
+/**
+ * Provides a value object to model an element in a menu link tree.
+ *
+ * \Drupal\Core\Menu\MenuLinkTreeInterface objects represent a menu link's data.
+ * Objects of this class provide complimentary data: the placement in a tree.
+ * Therefore, we can summarize this split as follows:
+ * - Menu link objects contain all information about an individual menu link,
+ *   plus what their parent is. But they don't know where exactly in a menu link
+ *   tree they live.
+ * - Instances of this class are complimentary to those objects, they know:
+ *   1. all additional metadata from {menu_tree}, which contains "materialized"
+ *      metadata about a menu link tree, such as whether a link in the tree has
+ *      visible children and the depth relative to the root;
+ *   2. plus all additional metadata that's adjusted for the current tree query,
+ *      such as whether the link is in the active trail, whether the link is
+ *      accessible for the current user, and the link's children (which are only
+ *      loaded if the link was marked as "expanded" by the query).
+ *
+ * @see \Drupal\Core\Menu\MenuTreeStorage::loadTreeData()
+ */
+class MenuLinkTreeElement {
+
+  /**
+   * The menu link for this element in a menu link tree.
+   *
+   * @var \Drupal\Core\Menu\MenuLinkInterface|array
+   */
+  public $link;
+
+  /**
+   * The subtree of this element in the menu link tree (this link's children).
+   *
+   * (Children of a link are only loaded if a link is marked as "expanded" by
+   * the query.)
+   *
+   * @var \Drupal\Core\Menu\MenuLinkTreeElement[]
+   */
+  public $subtree;
+
+  /**
+   * The depth of this link relative to the root of the tree.
+   *
+   * @var int
+   */
+  public $depth;
+
+  /**
+   * Whether this link has any children at all.
+   *
+   * @var bool
+   */
+  public $hasChildren;
+
+  /**
+   * Whether this link is in the active trail.
+   *
+   * @var bool
+   */
+  public $inActiveTrail;
+
+  /**
+   * Whether this link is accessible by the current user.
+   *
+   * @var bool|NULL
+   */
+  public $access;
+
+  /**
+   * Additional options for this link.
+   *
+   * This is merged (\Drupal\Component\Utility\NestedArray::mergeDeep()) with
+   * \Drupal\Core\Menu\MenuLinkInterface::getOptions(), to allow menu link tree
+   * manipulators to add or override link options.
+   */
+  public $options;
+
+  /**
+   * Constructs a new MenuLinkTreeElement.
+   *
+   * @param \Drupal\Core\Menu\MenuLinkInterface|array $link
+   *   The menu link for this element in the menu link tree.
+   * @param bool $has_children
+   * @param int $depth
+   * @param bool $in_active_trail
+   * @param \Drupal\Core\Menu\MenuLinkTreeElement[] $subtree
+   *   The children of this element in the menu link tree.
+   */
+  public function __construct($link, $has_children, $depth, $in_active_trail, array $subtree) {
+    // Essential properties.
+    $this->link = $link;
+    $this->hasChildren = $has_children;
+    $this->depth = $depth;
+    $this->subtree = $subtree;
+    $this->inActiveTrail = $in_active_trail;
+
+    // Properties that will be updated by menu link tree manipulators.
+    $this->access = NULL;
+    $this->options = array();
+  }
+
+  /**
+   * Counts all menu links in the current subtree.
+   *
+   * @return int
+   *   The number of menu links in this subtree (one plus the number of menu
+   *   links in all descendants).
+   */
+  public function count() {
+    $sum = function ($carry, MenuLinkTreeElement $element) {
+      return $carry + $element->count();
+    };
+    return 1 + array_reduce($this->subtree, $sum);
+  }
+
+}
diff --git a/core/lib/Drupal/Core/Menu/MenuParentFormSelector.php b/core/lib/Drupal/Core/Menu/MenuParentFormSelector.php
index 322118d..406c6cd 100644
--- a/core/lib/Drupal/Core/Menu/MenuParentFormSelector.php
+++ b/core/lib/Drupal/Core/Menu/MenuParentFormSelector.php
@@ -116,21 +116,21 @@ protected function getParentDepthLimit($id) {
    *   The maximum depth of menu links considered for the select options.
    */
   protected function parentSelectOptionsTreeWalk(array $tree, $menu_name, $indent, array &$options, $exclude, $depth_limit) {
-    foreach ($tree as $data) {
-      if ($data['depth'] > $depth_limit) {
+    foreach ($tree as $element) {
+      if ($element->depth > $depth_limit) {
         // Don't iterate through any links on this level.
         break;
       }
       /** @var \Drupal\Core\Menu\MenuLinkInterface $link */
-      $link = $data['link'];
+      $link = $element->link;
       if ($link->getPluginId() != $exclude) {
         $title = $indent . ' ' . Unicode::truncate($link->getTitle(), 30, TRUE, FALSE);
         if ($link->isHidden()) {
           $title .= ' (' . t('disabled') . ')';
         }
         $options[$menu_name . ':' . $link->getPluginId()] = $title;
-        if ($data['below']) {
-          $this->parentSelectOptionsTreeWalk($data['below'], $menu_name, $indent . '--', $options, $exclude, $depth_limit);
+        if (!empty($element->subtree)) {
+          $this->parentSelectOptionsTreeWalk($element->subtree, $menu_name, $indent . '--', $options, $exclude, $depth_limit);
         }
       }
     }
diff --git a/core/lib/Drupal/Core/Menu/MenuTreeStorage.php b/core/lib/Drupal/Core/Menu/MenuTreeStorage.php
index 2d79383..5f2767b 100644
--- a/core/lib/Drupal/Core/Menu/MenuTreeStorage.php
+++ b/core/lib/Drupal/Core/Menu/MenuTreeStorage.php
@@ -55,7 +55,7 @@ class MenuTreeStorage implements MenuTreeStorageInterface {
   protected $options = array();
 
   /**
-   * Stores the defintions that have already been loaded for better performance..
+   * Stores the definitions that have already been loaded for better performance.
    */
   protected $definitions = array();
 
@@ -805,7 +805,7 @@ public function loadTreeData($menu_name, array $parameters = array()) {
       }
       $data['tree'] = $this->doBuildTreeData($links, $active_trail, $min_depth);
       $data['definitions'] = array();
-      $data['route_names'] = $this->collectRoutes($data['tree'], $data['definitions']);
+      $data['route_names'] = $this->collectRoutesAndDefinitions($data['tree'], $data['definitions']);
       $this->treeCacheBackend->set($tree_cid, $data, Cache::PERMANENT, array('menu' => $menu_name));
       // The definitions were already added to $this->definitions in
       // $this->doBuildTreeData()
@@ -815,7 +815,7 @@ public function loadTreeData($menu_name, array $parameters = array()) {
   }
 
   /**
-   * Traverses the menu tree and collects all the route names.
+   * Traverses the menu tree and collects all the route names and definitions.
    *
    * @param array $tree
    *   The menu tree you wish to operate on.
@@ -825,23 +825,31 @@ public function loadTreeData($menu_name, array $parameters = array()) {
    * @return array
    *   Array of route names, with all values being unique.
    */
-  protected function collectRoutes(array $tree, array &$definitions) {
-    return array_values($this->doCollectRoutes($tree, $definitions));
+  protected function collectRoutesAndDefinitions(array $tree, array &$definitions) {
+    return array_values($this->doCollectRoutesAndDefinitions($tree, $definitions));
   }
 
   /**
-   * Recursive helper function to collect all the route names and defintions.
+   * Recursive helper function to collect all the route names and definitions.
+   *
+   * @param array $tree
+   *   The menu link tree.
+   * @param array &$definitions
+   *   The collected definitions.
+   *
+   * @return array
+   *   The collected route names.
    */
-  protected function doCollectRoutes(array $tree, array &$definitions) {
+  protected function doCollectRoutesAndDefinitions(array $tree, array &$definitions) {
     $route_names = array();
-    foreach ($tree as $key => $v) {
-      $definition = $tree[$key]['definition'];
-      $definitions[$definition['id']] = $definition;
+    foreach (array_keys($tree) as $id) {
+      $definition = $this->definitions[$id];
+      $definitions[$id] = $definition;
       if (!empty($definition['route_name'])) {
         $route_names[$definition['route_name']] = $definition['route_name'];
       }
-      if ($tree[$key]['below']) {
-        $route_names += $this->doCollectRoutes($tree[$key]['below'], $definitions);
+      if (!empty($tree[$id]->subtree)) {
+        $route_names += $this->doCollectRoutesAndDefinitions($tree[$id]->subtree, $definitions);
       }
     }
     return $route_names;
@@ -881,11 +889,11 @@ public function loadSubtreeData($id, $max_relative_depth = NULL) {
       $links = $this->safeExecuteSelect($query)->fetchAll(\PDO::FETCH_ASSOC);
       $tree = $this->doBuildTreeData($links, array(), $root['depth']);
       $data['definitions'] = array();
-      $data['route_names'] = $this->collectRoutes($tree, $data['definitions']);
+      $data['route_names'] = $this->collectRoutesAndDefinitions($tree, $data['definitions']);
       $data['tree'] = $tree;
       if ($data['tree']) {
         $top = reset($tree);
-        $menu_name = $top['definition']['menu_name'];
+        $menu_name = $top->link['menu_name'];
         $this->treeCacheBackend->set($tree_cid, $data, Cache::PERMANENT, array('menu' => $menu_name));
       }
       // The definitions were already added to $this->definitions in
@@ -992,10 +1000,9 @@ protected function doBuildTreeData(array $links, array $parents = array(), $dept
    * @param array $links
    *   A flat array of menu links that are part of the menu. Each array element
    *   is an associative array of information about the menu link, containing
-   *   the fields from the {menu_links} table, and optionally additional
-   *   information from the {menu_router} table, if the menu item appears in
-   *   both tables. This array must be ordered depth-first.
-   *   See _menu_build_tree() for a sample query.
+   *   the fields from the {menu_tree} table. This array must be ordered
+   *   depth-first.
+   *   See ::loadTreeData() for a sample query.
    * @param array $parents
    *   An array of the menu link ID values that are in the path from the current
    *   page to the root of the menu tree.
@@ -1003,21 +1010,24 @@ protected function doBuildTreeData(array $links, array $parents = array(), $dept
    *   The minimum depth to include in the returned menu tree.
    *
    * @return array
-   *   The fully build tree.
+   *   The fully built tree.
    */
-  protected function treeDataRecursive(&$links, $parents, $depth) {
+  protected function treeDataRecursive(array &$links, array $parents, $depth) {
     $tree = array();
-    while ($item = array_pop($links)) {
-      // We need to determine if we're on the path to root so we can later build
-      // the correct active trail.
-      // Add the current link to the tree.
-      $tree[$item['id']] = array(
-        'definition' => $this->prepareLink($item, TRUE),
-        'has_children' => $item['has_children'],
-        'in_active_trail' => in_array($item['id'], $parents),
-        'below' => array(),
-        'depth' => $item['depth'],
+    while ($tree_link_definition = array_pop($links)) {
+      // Build a MenuLinkTreeElement out of the menu link tree definition:
+      // transform the menu link tree definition into a menu link definition and
+      // store tree metadata in MenuLinkTreeElement.
+      $tree[$tree_link_definition['id']] = new MenuLinkTreeElement(
+        $this->prepareLink($tree_link_definition, TRUE),
+        (bool) $tree_link_definition['has_children'],
+        (int) $tree_link_definition['depth'],
+        // We need to determine if we're on the path to root so we can later build
+        // the correct active trail.
+        in_array($tree_link_definition['id'], $parents),
+        array()
       );
+
       // Look ahead to the next link, but leave it on the array so it's
       // available to other recursive function calls if we return or build a
       // sub-tree.
@@ -1025,7 +1035,7 @@ protected function treeDataRecursive(&$links, $parents, $depth) {
       // Check whether the next link is the first in a new sub-tree.
       if ($next && $next['depth'] > $depth) {
         // Recursively call doBuildTreeData to build the sub-tree.
-        $tree[$item['id']]['below'] = $this->treeDataRecursive($links, $parents, $next['depth']);
+        $tree[$tree_link_definition['id']]->subtree = $this->treeDataRecursive($links, $parents, $next['depth']);
         // Fetch next link after filling the sub-tree.
         $next = end($links);
       }
diff --git a/core/modules/menu_ui/menu_ui.admin.inc b/core/modules/menu_ui/menu_ui.admin.inc
index 00d3e58..b8f0ef6 100644
--- a/core/modules/menu_ui/menu_ui.admin.inc
+++ b/core/modules/menu_ui/menu_ui.admin.inc
@@ -46,7 +46,7 @@ function theme_menu_overview_form($variables) {
 
       $indent = array(
         '#theme' => 'indentation',
-        '#size' => $element['#item']['depth'] - 1,
+        '#size' => $element['#item']->depth - 1,
       );
 
       $row = array();
diff --git a/core/modules/menu_ui/src/MenuForm.php b/core/modules/menu_ui/src/MenuForm.php
index 12d5cec..ceeb501 100644
--- a/core/modules/menu_ui/src/MenuForm.php
+++ b/core/modules/menu_ui/src/MenuForm.php
@@ -11,6 +11,7 @@
 use Drupal\Core\Entity\EntityForm;
 use Drupal\Core\Entity\Query\QueryFactory;
 use Drupal\Core\Language\LanguageInterface;
+use Drupal\Core\Menu\MenuLinkTreeElement;
 use Drupal\Core\Menu\MenuLinkTreeInterface;
 use Drupal\Core\Menu\MenuLinkManagerInterface;
 use Drupal\Core\Render\Element;
@@ -180,19 +181,6 @@ public function save(array $form, array &$form_state) {
   }
 
   /**
-   * Recursively count the number of menu links in a tree.
-   */
-  protected function countElements($tree, $count = 0) {
-    foreach ($tree as $element) {
-      $count++;
-      if (!empty($element['below'])) {
-        $this->countElements($element['below'], $count);
-      }
-    }
-    return $count;
-  }
-
-  /**
    * Form constructor to edit an entire menu tree at once.
    *
    * Shows for one menu the menu links accessible to the current user and
@@ -227,8 +215,14 @@ protected function buildOverviewForm(array &$form, array &$form_state) {
     $tree = $this->menuTree->transform($tree, $manipulators);
     $this->getRequest()->attributes->set('_menu_admin', FALSE);
 
-    $count = $this->countElements($tree);
-    $delta = max($count, 50);
+    // Determine the delta; the number of weights to be made available.
+    $count = function(array $tree) {
+      $sum = function ($carry, MenuLinkTreeElement $item) {
+        return $carry + $item->count();
+      };
+      return array_reduce($tree, $sum);
+    };
+    $delta = max($count($tree), 50);
 
     $form = array_merge($form, $this->buildOverviewTreeForm($tree, $delta));
     $form['#empty_text'] = $this->t('There are no menu links yet. <a href="@link">Add link</a>.', array('@link' => url('admin/structure/menu/manage/' . $this->entity->id() .'/add')));
@@ -249,41 +243,41 @@ protected function buildOverviewForm(array &$form, array &$form_state) {
    */
   protected function buildOverviewTreeForm($tree, $delta) {
     $form = &$this->overviewTreeForm;
-    foreach ($tree as $data) {
-      /** @var \Drupal\Core\Menu\MenuLinkInterface $item */
-      $item = $data['link'];
-      if ($item) {
-        $id = 'menu_plugin_id:' . $item->getPluginId();
-        $form[$id]['#item'] = $data;
-        $form[$id]['#attributes'] = $item->isHidden() ? array('class' => array('menu-disabled')) : array('class' => array('menu-enabled'));
-        $form[$id]['title']['#markup'] = \Drupal::linkGenerator()->generateFromUrl($item->getTitle(), $item->getUrlObject(), $item->getOptions());
-        if ($item->isHidden()) {
+    foreach ($tree as $element) {
+      /** @var \Drupal\Core\Menu\MenuLinkInterface $link */
+      $link = $element->link;
+      if ($link) {
+        $id = 'menu_plugin_id:' . $link->getPluginId();
+        $form[$id]['#item'] = $element;
+        $form[$id]['#attributes'] = $link->isHidden() ? array('class' => array('menu-disabled')) : array('class' => array('menu-enabled'));
+        $form[$id]['title']['#markup'] = \Drupal::linkGenerator()->generateFromUrl($link->getTitle(), $link->getUrlObject(), $link->getOptions());
+        if ($link->isHidden()) {
           $form[$id]['title']['#markup'] .= ' (' . $this->t('disabled') . ')';
         }
-        elseif (($url = $item->getUrlObject()) && !$url->isExternal() && $url->getRouteName() == 'user.page') {
+        elseif (($url = $link->getUrlObject()) && !$url->isExternal() && $url->getRouteName() == 'user.page') {
           $form[$id]['title']['#markup'] .= ' (' . $this->t('logged in users only') . ')';
         }
 
         $form[$id]['enabled'] = array(
           '#type' => 'checkbox',
-          '#title' => $this->t('Enable @title menu link', array('@title' => $item->getTitle())),
+          '#title' => $this->t('Enable @title menu link', array('@title' => $link->getTitle())),
           '#title_display' => 'invisible',
-          '#default_value' => !$item->isHidden(),
+          '#default_value' => !$link->isHidden(),
         );
         $form[$id]['weight'] = array(
           '#type' => 'weight',
           '#delta' => $delta,
-          '#default_value' => $item->getWeight(),
-          '#title' => $this->t('Weight for @title', array('@title' => $item->getTitle())),
+          '#default_value' => $link->getWeight(),
+          '#title' => $this->t('Weight for @title', array('@title' => $link->getTitle())),
           '#title_display' => 'invisible',
         );
         $form[$id]['id'] = array(
           '#type' => 'hidden',
-          '#value' => $item->getPluginId(),
+          '#value' => $link->getPluginId(),
         );
         $form[$id]['parent'] = array(
           '#type' => 'hidden',
-          '#default_value' => $item->getParent(),
+          '#default_value' => $link->getParent(),
         );
         // Build a list of operations.
         $operations = array();
@@ -291,7 +285,7 @@ protected function buildOverviewTreeForm($tree, $delta) {
           'title' => $this->t('Edit'),
         );
         // Allow for a custom edit link per plugin.
-        $edit_route = $item->getEditRoute();
+        $edit_route = $link->getEditRoute();
         if ($edit_route) {
           $operations['edit'] += $edit_route;
           // Bring the user back to the menu overview.
@@ -301,26 +295,26 @@ protected function buildOverviewTreeForm($tree, $delta) {
           // Fall back to the standard edit link.
           $operations['edit'] += array(
             'route_name' => 'menu_ui.link_edit',
-            'route_parameters' => array('menu_link_plugin' => $item->getPluginId()),
+            'route_parameters' => array('menu_link_plugin' => $link->getPluginId()),
           );
         }
         // Links can either be reset or deleted, not both.
-        if ($item->isResetable()) {
+        if ($link->isResetable()) {
           $operations['reset'] = array(
             'title' => $this->t('Reset'),
             'route_name' => 'menu_ui.link_reset',
-            'route_parameters' => array('menu_link_plugin' => $item->getPluginId()),
+            'route_parameters' => array('menu_link_plugin' => $link->getPluginId()),
           );
         }
-        elseif ($delete_link = $item->getDeleteRoute()) {
+        elseif ($delete_link = $link->getDeleteRoute()) {
           $operations['delete'] = $delete_link;
           $operations['delete']['query']['destination'] = $this->entity->url();
           $operations['delete']['title'] = $this->t('Delete');
         }
-        if ($item->isTranslatable()) {
+        if ($link->isTranslatable()) {
           $operations['translate'] = array(
             'title' => $this->t('Translate'),
-          ) + (array) $item->getTranslateRoute();
+          ) + (array) $link->getTranslateRoute();
         }
         $form[$id]['operations'] = array(
           '#type' => 'operations',
@@ -328,8 +322,8 @@ protected function buildOverviewTreeForm($tree, $delta) {
         );
       }
 
-      if ($data['below']) {
-        $this->buildOverviewTreeForm($data['below'], $delta);
+      if ($element->subtree) {
+        $this->buildOverviewTreeForm($element->subtree, $delta);
       }
     }
     return $form;
@@ -380,7 +374,7 @@ protected function submitOverviewForm(array $complete_form, array &$form_state)
         if ($updated_values) {
           // Use the ID from the actual plugin instance since the hidden value
           // in the form could be tampered with.
-          $this->menuLinkManager->updateLink($element['#item']['link']->getPLuginId(), $updated_values);
+          $this->menuLinkManager->updateLink($element['#item']->link->getPLuginId(), $updated_values);
         }
       }
     }
diff --git a/core/modules/system/src/Controller/SystemController.php b/core/modules/system/src/Controller/SystemController.php
index 61fe270..95725c4 100644
--- a/core/modules/system/src/Controller/SystemController.php
+++ b/core/modules/system/src/Controller/SystemController.php
@@ -118,7 +118,7 @@ public function overview($link_id) {
       drupal_set_message($this->t('One or more problems were detected with your Drupal installation. Check the <a href="@status">status report</a> for more information.', array('@status' => url('admin/reports/status'))), 'error');
     }
     $top_tree = $this->menuLinkTree->buildSubtree($link_id, 1);
-    $tree = !empty($top_tree[$link_id]['below']) ? $top_tree[$link_id]['below'] : array();
+    $tree = $top_tree[$link_id]->subtree;
     $manipulators = array(
       array('callable' => 'menu.default_tree_manipulators:checkAccess'),
       array('callable' => 'menu.default_tree_manipulators:generateIndexAndSort'),
@@ -126,12 +126,13 @@ public function overview($link_id) {
     $tree = $this->menuLinkTree->transform($tree, $manipulators);
     $blocks = array();
     // Load all menu links below it.
-    foreach ($tree as $key => $item) {
-      $block['title'] = $item['link']->getTitle();
-      $block['description'] = $item['link']->getDescription();
+    foreach ($tree as $key => $element) {
+      $link = $element->link;
+      $block['title'] = $link->getTitle();
+      $block['description'] = $link->getDescription();
       $block['content'] = array(
         '#theme' => 'admin_block_content',
-        '#content' => $this->systemManager->getAdminBlock($item['link']),
+        '#content' => $this->systemManager->getAdminBlock($link),
       );
 
       if (!empty($block['content']['#content'])) {
diff --git a/core/modules/system/src/SystemManager.php b/core/modules/system/src/SystemManager.php
index 5d54692..2b9108a 100644
--- a/core/modules/system/src/SystemManager.php
+++ b/core/modules/system/src/SystemManager.php
@@ -185,8 +185,8 @@ public function getMaxSeverity(&$requirements) {
    *   A render array suitable for drupal_render.
    */
   public function getBlockContents() {
-    $instance = $this->menuActiveTrail->getActiveLink();
-    if ($instance && $content = $this->getAdminBlock($instance)) {
+    $link = $this->menuActiveTrail->getActiveLink();
+    if ($link && $content = $this->getAdminBlock($link)) {
       $output = array(
         '#theme' => 'admin_block_content',
         '#content' => $content,
@@ -220,9 +220,9 @@ public function getAdminBlock(MenuLinkInterface $instance) {
       array('callable' => 'menu.default_tree_manipulators:generateIndexAndSort'),
     );
     $tree = $this->menuTree->transform($tree, $manipulators);
-    foreach ($tree as $key => $item) {
+    foreach ($tree as $key => $element) {
       /** @var $link \Drupal\Core\Menu\MenuLinkInterface */
-      $link = $item['link'];
+      $link = $element->link;
       $content[$key]['title'] = $link->getTitle();
       $content[$key]['options'] = $link->getOptions();
       $content[$key]['description'] = $link->getDescription();
diff --git a/core/modules/system/src/Tests/Cache/GenericCacheBackendUnitTestBase.php b/core/modules/system/src/Tests/Cache/GenericCacheBackendUnitTestBase.php
index f6ae8f8..ff1e098 100644
--- a/core/modules/system/src/Tests/Cache/GenericCacheBackendUnitTestBase.php
+++ b/core/modules/system/src/Tests/Cache/GenericCacheBackendUnitTestBase.php
@@ -188,6 +188,14 @@ public function testSetGet() {
     $cached = $backend->get('test6');
     $this->assert(is_object($cached), "Backend returned an object for cache id test6.");
     $this->assertIdentical($with_variable, $cached->data);
+
+    $data = new \stdClass();
+    $backend->set('test7', $data);
+    $expected_data = clone $data;
+    $data->this_should_not_be_in_the_cache = TRUE;
+    $cached = $backend->get('test7');
+    $this->assert(is_object($cached), "Backend returned an object for cache id test7.");
+    $this->assertEqual($expected_data, $cached->data);
   }
 
   /**
diff --git a/core/modules/system/src/Tests/Menu/MenuLinkTreeTest.php b/core/modules/system/src/Tests/Menu/MenuLinkTreeTest.php
index 5216a01..92099ba 100644
--- a/core/modules/system/src/Tests/Menu/MenuLinkTreeTest.php
+++ b/core/modules/system/src/Tests/Menu/MenuLinkTreeTest.php
@@ -7,6 +7,7 @@
 
 namespace Drupal\system\Tests\Menu;
 
+use Drupal\Core\Menu\MenuLinkTreeElement;
 use Drupal\simpletest\KernelTestBase;
 use Drupal\Tests\Core\Menu\MenuLinkMock;
 
@@ -116,28 +117,22 @@ public function testCreateLinksInMenu() {
       $this->menuLinkManager->createLink($instance->getPluginId(), $instance->getPluginDefinition());
     }
     $tree = $this->linkTree->buildTree('mock');
-    $this->assertEqual(count($tree), 5);
-    $this->assertEqual(count($this->flatten($tree)), 8);
+
+    $count = function(array $tree) {
+      $sum = function ($carry, MenuLinkTreeElement $item) {
+        return $carry + $item->count();
+      };
+      return array_reduce($tree, $sum);
+    };
+
+    $this->assertEqual($count($tree), 8);
     $tree = $this->linkTree->buildSubtree('test.example2');
     $top_link = reset($tree);
-    $this->assertEqual(count($top_link['below']), 1);
-    $child = reset($top_link['below']);
-    $this->assertEqual($child['link']->getPluginId(), $links[3]->getPluginId());
+    $this->assertEqual(count($top_link->subtree), 1);
+    $child = reset($top_link->subtree);
+    $this->assertEqual($child->link->getPluginId(), $links[3]->getPluginId());
     $height = $this->linkTree->getSubtreeHeight('test.example2');
     $this->assertEqual($height, 3);
   }
 
-  /**
-   * Flatten a menu tree.
-   */
-  public function flatten($tree) {
-    foreach ($tree as $key => $item) {
-      if ($tree[$key]['below']) {
-        $tree += $this->flatten($tree[$key]['below']);
-      }
-      unset($tree[$key]['below']);
-    }
-    return $tree;
-  }
-
 }
diff --git a/core/modules/system/src/Tests/Menu/MenuTreeStorageTest.php b/core/modules/system/src/Tests/Menu/MenuTreeStorageTest.php
index d31707e..6d25768 100644
--- a/core/modules/system/src/Tests/Menu/MenuTreeStorageTest.php
+++ b/core/modules/system/src/Tests/Menu/MenuTreeStorageTest.php
@@ -255,32 +255,32 @@ public function testLoadTree() {
 
     $data = $this->treeStorage->loadTreeData('tools');
     $tree = $data['tree'];
-    $this->assertEqual(count($tree['test1']['below']), 1);
-    $this->assertEqual(count($tree['test1']['below']['test2']['below']), 1);
-    $this->assertEqual(count($tree['test1']['below']['test2']['below']['test3']['below']), 0);
-    $this->assertEqual(count($tree['test4']['below']), 1);
-    $this->assertEqual(count($tree['test4']['below']['test5']['below']), 0);
+    $this->assertEqual(count($tree['test1']->subtree), 1);
+    $this->assertEqual(count($tree['test1']->subtree['test2']->subtree), 1);
+    $this->assertEqual(count($tree['test1']->subtree['test2']->subtree['test3']->subtree), 0);
+    $this->assertEqual(count($tree['test4']->subtree), 1);
+    $this->assertEqual(count($tree['test4']->subtree['test5']->subtree), 0);
 
     $data = $this->treeStorage->loadTreeData('tools', array('active_trail' => array('test4', 'test5')));
     $tree = $data['tree'];
-    $this->assertEqual(count($tree['test1']['below']), 1);
-    $this->assertFalse($tree['test1']['in_active_trail']);
-    $this->assertEqual(count($tree['test1']['below']['test2']['below']), 1);
-    $this->assertFalse($tree['test1']['below']['test2']['in_active_trail']);
-    $this->assertEqual(count($tree['test1']['below']['test2']['below']['test3']['below']), 0);
-    $this->assertFalse($tree['test1']['below']['test2']['below']['test3']['in_active_trail']);
-    $this->assertEqual(count($tree['test4']['below']), 1);
-    $this->assertTrue($tree['test4']['in_active_trail']);
-    $this->assertEqual(count($tree['test4']['below']['test5']['below']), 0);
-    $this->assertTrue($tree['test4']['below']['test5']['in_active_trail']);
+    $this->assertEqual(count($tree['test1']->subtree), 1);
+    $this->assertFalse($tree['test1']->inActiveTrail);
+    $this->assertEqual(count($tree['test1']->subtree['test2']->subtree), 1);
+    $this->assertFalse($tree['test1']->subtree['test2']->inActiveTrail);
+    $this->assertEqual(count($tree['test1']->subtree['test2']->subtree['test3']->subtree), 0);
+    $this->assertFalse($tree['test1']->subtree['test2']->subtree['test3']->inActiveTrail);
+    $this->assertEqual(count($tree['test4']->subtree), 1);
+    $this->assertTrue($tree['test4']->inActiveTrail);
+    $this->assertEqual(count($tree['test4']->subtree['test5']->subtree), 0);
+    $this->assertTrue($tree['test4']->subtree['test5']->inActiveTrail);
 
     $data = $this->treeStorage->loadTreeData('tools', array('active_trail' => array('test4', 'test5'), 'only_active_trail' => TRUE));
     $tree = $data['tree'];
     $this->assertTrue(empty($tree['test1']));
-    $this->assertEqual(count($tree['test4']['below']), 1);
-    $this->assertTrue($tree['test4']['in_active_trail']);
-    $this->assertEqual(count($tree['test4']['below']['test5']['below']), 0);
-    $this->assertTrue($tree['test4']['below']['test5']['in_active_trail']);
+    $this->assertEqual(count($tree['test4']->subtree), 1);
+    $this->assertTrue($tree['test4']->inActiveTrail);
+    $this->assertEqual(count($tree['test4']->subtree['test5']->subtree), 0);
+    $this->assertTrue($tree['test4']->subtree['test5']->inActiveTrail);
   }
 
   /**
diff --git a/core/modules/system/src/Tests/System/AdminTest.php b/core/modules/system/src/Tests/System/AdminTest.php
index 3a15495..7b40c07 100644
--- a/core/modules/system/src/Tests/System/AdminTest.php
+++ b/core/modules/system/src/Tests/System/AdminTest.php
@@ -135,7 +135,7 @@ protected function getTopLevelMenuLinks() {
     // The system.admin link is normally the parent of all top-level admin links.
     $link_id = 'system.admin';
     $top_tree = $menu_tree->buildSubtree($link_id, 1);
-    $tree = !empty($top_tree[$link_id]['below']) ? $top_tree[$link_id]['below'] : array();
+    $tree = $top_tree[$link_id]->subtree;
     $manipulators = array(
       array('callable' => 'menu.default_tree_manipulators:checkAccess'),
       array('callable' => 'menu.default_tree_manipulators:flatten'),
@@ -144,8 +144,8 @@ protected function getTopLevelMenuLinks() {
 
     // Transform the tree to a list of menu links.
     $menu_links = array();
-    foreach ($tree as $item) {
-      $menu_links[] = $item['link'];
+    foreach ($tree as $element) {
+      $menu_links[] = $element->link;
     }
 
     return $menu_links;
diff --git a/core/modules/system/system.module b/core/modules/system/system.module
index 9fd85f4..230e596 100644
--- a/core/modules/system/system.module
+++ b/core/modules/system/system.module
@@ -1470,15 +1470,15 @@ function system_get_module_admin_tasks($module, array $info) {
   }
 
   $admin_tasks = array();
-  foreach ($tree as $item) {
-    $instance = $item['link'];
-    if ($instance->getProvider() != $module) {
+  foreach ($tree as $element) {
+    $link = $element->link;
+    if ($link->getProvider() != $module) {
       continue;
     }
     $admin_tasks[] = array(
-      'title' => $instance->getTitle(),
-      'description' => $instance->getDescription(),
-      'url' => $instance->getUrlObject(),
+      'title' => $link->getTitle(),
+      'description' => $link->getDescription(),
+      'url' => $link->getUrlObject(),
     );
   }
 
diff --git a/core/modules/toolbar/toolbar.module b/core/modules/toolbar/toolbar.module
index 267ab3e..aa7eae9 100644
--- a/core/modules/toolbar/toolbar.module
+++ b/core/modules/toolbar/toolbar.module
@@ -427,23 +427,23 @@ function toolbar_prerender_toolbar_administration_tray(array $element) {
 }
 
 /**
- * Tree manipulator that adds toolbar-specific attributes.
+ * Menu link tree manipulator that adds toolbar-specific attributes.
  *
- * @param array $tree
- *   The menu tree to manipulate.
+ * @param \Drupal\Core\Menu\MenuLinkTreeElement[] $tree
+ *   The menu link tree to manipulate.
  *
- * @return array
- *   The manipulated menu tree.
+ * @return \Drupal\Core\Menu\MenuLinkTreeElement[]
+ *   The manipulated menu link tree.
  */
-function toolbar_menu_navigation_links($tree) {
-  foreach ($tree as $key => $item) {
-    if (!empty($item['below'])) {
-      toolbar_menu_navigation_links($tree[$key]['below']);
+function toolbar_menu_navigation_links(array $tree) {
+  foreach ($tree as $key => $element) {
+    if (!empty($element->subtree)) {
+      toolbar_menu_navigation_links($tree[$key]->subtree);
     }
 
     // Make sure we have a path specific ID in place, so we can attach icons
     // and behaviors to the menu links.
-    $link = $item['link'];
+    $link = $element->link;
     $url = $link->getUrlObject();
     if ($url->isExternal()) {
       // This is an unusual case, so just get a distinct, safe string.
@@ -456,10 +456,10 @@ function toolbar_menu_navigation_links($tree) {
     // Get the non-localized title to make the icon class.
     $definition = $link->getPluginDefinition();
 
-    $tree[$key]['options']['attributes']['id'] = 'toolbar-link-' . $id;
-    $tree[$key]['options']['attributes']['class'][] = 'toolbar-icon';
-    $tree[$key]['options']['attributes']['class'][] = 'toolbar-icon-' . strtolower(str_replace(' ', '-', $definition['title']));
-    $tree[$key]['options']['attributes']['title'] = String::checkPlain($link->getDescription());
+    $tree[$key]->options['attributes']['id'] = 'toolbar-link-' . $id;
+    $tree[$key]->options['attributes']['class'][] = 'toolbar-icon';
+    $tree[$key]->options['attributes']['class'][] = 'toolbar-icon-' . strtolower(str_replace(' ', '-', $definition['title']));
+    $tree[$key]->options['attributes']['title'] = String::checkPlain($link->getDescription());
   }
   return $tree;
 }
@@ -472,7 +472,7 @@ function toolbar_get_rendered_subtrees() {
   $menu_tree = \Drupal::service('menu.link_tree');
   $link_id = 'system.admin';
   $top_tree = $menu_tree->buildSubtree($link_id, 3);
-  $tree = !empty($top_tree[$link_id]['below']) ? $top_tree[$link_id]['below'] : array();
+  $tree = $top_tree[$link_id]->subtree;
   $manipulators = array(
     array('callable' => 'menu.default_tree_manipulators:checkAccess'),
     array('callable' => 'menu.default_tree_manipulators:generateIndexAndSort'),
@@ -480,17 +480,17 @@ function toolbar_get_rendered_subtrees() {
   );
   $tree = $menu_tree->transform($tree, $manipulators);
   $subtrees = array();
-  foreach ($tree as $tree_item) {
+  foreach ($tree as $element) {
     /** @var \Drupal\Core\Menu\MenuLinkInterface $item */
-    $item = $tree_item['link'];
-    if ($tree_item['below']) {
-      $subtree = $menu_tree->render($tree_item['below']);
+    $link = $element->link;
+    if (!empty($element->subtree)) {
+      $subtree = $menu_tree->render($element->subtree);
       $output = drupal_render($subtree);
     }
     else {
       $output = '';
     }
-    $id = str_replace(array('.', '<', '>'), array('-', '', '' ), $item->getUrlObject()->getRouteName());
+    $id = str_replace(array('.', '<', '>'), array('-', '', '' ), $link->getUrlObject()->getRouteName());
 
     $subtrees[$id] = $output;
   }
diff --git a/core/tests/Drupal/Tests/Core/Menu/DefaultMenuLinkTreeManipulatorsTest.php b/core/tests/Drupal/Tests/Core/Menu/DefaultMenuLinkTreeManipulatorsTest.php
index 88068c7..8962271 100644
--- a/core/tests/Drupal/Tests/Core/Menu/DefaultMenuLinkTreeManipulatorsTest.php
+++ b/core/tests/Drupal/Tests/Core/Menu/DefaultMenuLinkTreeManipulatorsTest.php
@@ -8,6 +8,7 @@
 namespace Drupal\Tests\Core\Menu;
 
 use Drupal\Core\Menu\DefaultMenuLinkTreeManipulators;
+use Drupal\Core\Menu\MenuLinkTreeElement;
 use Drupal\Tests\UnitTestCase;
 
 /**
@@ -102,17 +103,17 @@ protected function mockTree() {
       8 => MenuLinkMock::create(array('id' => 'test.example8', 'route_name' => 'example8', 'title' => 'quxqux', 'parent' => '')),
     );
     $this->originalTree = array();
-    $this->originalTree[1] = array('link' => $this->links[1], 'below' => array());
-    $this->originalTree[2] = array('link' => $this->links[2], 'below' => array(
-      3 => array('link' => $this->links[3], 'below' => array(
-          4 => array('link' => $this->links[4], 'below' => array()),
+    $this->originalTree[1] = new MenuLinkTreeElement($this->links[1], FALSE, 1, FALSE, array());
+    $this->originalTree[2] = new MenuLinkTreeElement($this->links[2], TRUE, 1, FALSE, array(
+      3 => new MenuLinkTreeElement($this->links[3], TRUE, 2, FALSE, array(
+          4 => new MenuLinkTreeElement($this->links[4], FALSE, 3, FALSE, array()),
         )),
     ));
-    $this->originalTree[5] = array('link' => $this->links[5], 'below' => array(
-      7 => array('link' => $this->links[7], 'below' => array()),
+    $this->originalTree[5] = new MenuLinkTreeElement($this->links[5], TRUE, 1, FALSE, array(
+      7 => new MenuLinkTreeElement($this->links[7], FALSE, 2, FALSE, array()),
     ));
-    $this->originalTree[6] = array('link' => $this->links[6], 'below' => array());
-    $this->originalTree[8] = array('link' => $this->links[8], 'below' => array());
+    $this->originalTree[6] = new MenuLinkTreeElement($this->links[6], FALSE, 1, FALSE, array());
+    $this->originalTree[8] = new MenuLinkTreeElement($this->links[8], FALSE, 1, FALSE, array());
   }
 
   /**
@@ -125,17 +126,17 @@ public function testGenerateIndexAndSort() {
     $tree = $this->originalTree;
     $tree = $this->defaultMenuTreeManipulators->generateIndexAndSort($tree);
 
-    // Validate that parent items #1, #2, #5 and #6 exist on the root level.
-    $this->assertEquals($this->links[1]->getPluginId(), $tree['50000 foo test.example1']['link']->getPluginId());
-    $this->assertEquals($this->links[2]->getPluginId(), $tree['50000 bar test.example2']['link']->getPluginId());
-    $this->assertEquals($this->links[5]->getPluginId(), $tree['50000 foofoo test.example5']['link']->getPluginId());
-    $this->assertEquals($this->links[6]->getPluginId(), $tree['50000 barbar test.example6']['link']->getPluginId());
-    $this->assertEquals($this->links[8]->getPluginId(), $tree['50000 quxqux test.example8']['link']->getPluginId());
+    // Validate that parent elements #1, #2, #5 and #6 exist on the root level.
+    $this->assertEquals($this->links[1]->getPluginId(), $tree['50000 foo test.example1']->link->getPluginId());
+    $this->assertEquals($this->links[2]->getPluginId(), $tree['50000 bar test.example2']->link->getPluginId());
+    $this->assertEquals($this->links[5]->getPluginId(), $tree['50000 foofoo test.example5']->link->getPluginId());
+    $this->assertEquals($this->links[6]->getPluginId(), $tree['50000 barbar test.example6']->link->getPluginId());
+    $this->assertEquals($this->links[8]->getPluginId(), $tree['50000 quxqux test.example8']->link->getPluginId());
 
-    // Validate that child item #4 exists at the correct location in the hierarchy.
-    $this->assertEquals($this->links[4]->getPluginId(), $tree['50000 bar test.example2']['below']['50000 baz test.example3']['below']['50000 qux test.example4']['link']->getPluginId());
-    // Validate that child item #7 exists at the correct location in the hierarchy.
-    $this->assertEquals($this->links[7]->getPluginId(), $tree['50000 foofoo test.example5']['below']['50000 bazbaz test.example7']['link']->getPluginId());
+    // Validate that child element #4 exists at the correct location in the hierarchy.
+    $this->assertEquals($this->links[4]->getPluginId(), $tree['50000 bar test.example2']->subtree['50000 baz test.example3']->subtree['50000 qux test.example4']->link->getPluginId());
+    // Validate that child element #7 exists at the correct location in the hierarchy.
+    $this->assertEquals($this->links[7]->getPluginId(), $tree['50000 foofoo test.example5']->subtree['50000 bazbaz test.example7']->link->getPluginId());
   }
 
   /**
@@ -158,34 +159,30 @@ public function testCheckAccess() {
       )));
 
     $this->mockTree();
-    $this->originalTree[5]['below'][7]['access'] = TRUE;
-    $this->originalTree[8]['access'] = FALSE;
+    $this->originalTree[5]->subtree[7]->access = TRUE;
+    $this->originalTree[8]->access = FALSE;
 
     $tree = $this->defaultMenuTreeManipulators->checkAccess($this->originalTree);
 
     // Menu link 1: route without parameters, access forbidden, hence removed.
     $this->assertFalse(array_key_exists(1, $tree));
     // Menu link 2: route with parameters, access granted.
-    $item = $tree[2];
-    $this->assertTrue(array_key_exists('access', $item));
-    $this->assertTrue($item['access']);
+    $element = $tree[2];
+    $this->assertTrue($element->access);
     // Menu link 3: route with parameters, access forbidden, hence removed,
     // including its children.
-    $this->assertFalse(array_key_exists(3, $tree[2]['below']));
+    $this->assertFalse(array_key_exists(3, $tree[2]->subtree));
     // Menu link 4: child of menu link 3, which already is removed.
-    $this->assertSame(array(), $tree[2]['below']);
+    $this->assertSame(array(), $tree[2]->subtree);
     // Menu link 5: no route name, treated as external, hence access granted.
-    $item = $tree[5];
-    $this->assertTrue(array_key_exists('access', $item));
-    $this->assertTrue($item['access']);
+    $element = $tree[5];
+    $this->assertTrue($element->access);
     // Menu link 6: external URL, hence access granted.
-    $item = $tree[6];
-    $this->assertTrue(array_key_exists('access', $item));
-    $this->assertTrue($item['access']);
+    $element = $tree[6];
+    $this->assertTrue($element->access);
     // Menu link 7: 'access' already set.
-    $item = $tree[5]['below'][7];
-    $this->assertTrue(array_key_exists('access', $item));
-    $this->assertTrue($item['access']);
+    $element = $tree[5]->subtree[7];
+    $this->assertTrue($element->access);
     // Menu link 8: 'access' already set, to FALSE, hence removed.
     $this->assertFalse(array_key_exists(8, $tree));
   }
@@ -222,7 +219,7 @@ public function testExtractSubtreeOfActiveTrail() {
 
     // Link 5 in the active trail.
     $this->mockTree();
-    $this->originalTree[5]['in_active_trail'] = TRUE;
+    $this->originalTree[5]->inActiveTrail = TRUE;
     // Get level 0.
     $tree = $this->defaultMenuTreeManipulators->extractSubtreeOfActiveTrail($this->originalTree, 0);
     $this->assertEquals(array(1, 2, 5, 6, 8), array_keys($tree));
@@ -235,7 +232,7 @@ public function testExtractSubtreeOfActiveTrail() {
 
     // Link 2 in the active trail.
     $this->mockTree();
-    $this->originalTree[2]['in_active_trail'] = TRUE;
+    $this->originalTree[2]->inActiveTrail = TRUE;
     // Get level 0.
     $tree = $this->defaultMenuTreeManipulators->extractSubtreeOfActiveTrail($this->originalTree, 0);
     $this->assertEquals(array(1, 2, 5, 6, 8), array_keys($tree));
@@ -248,8 +245,8 @@ public function testExtractSubtreeOfActiveTrail() {
 
     // Links 2 and 3 in the active trail.
     $this->mockTree();
-    $this->originalTree[2]['in_active_trail'] = TRUE;
-    $this->originalTree[2]['below'][3]['in_active_trail'] = TRUE;
+    $this->originalTree[2]->inActiveTrail = TRUE;
+    $this->originalTree[2]->subtree[3]->inActiveTrail = TRUE;
     // Get level 0.
     $tree = $this->defaultMenuTreeManipulators->extractSubtreeOfActiveTrail($this->originalTree, 0);
     $this->assertEquals(array(1, 2, 5, 6, 8), array_keys($tree));
diff --git a/core/tests/Drupal/Tests/Core/Menu/MenuLinkTreeElementTest.php b/core/tests/Drupal/Tests/Core/Menu/MenuLinkTreeElementTest.php
new file mode 100644
index 0000000..39cda99
--- /dev/null
+++ b/core/tests/Drupal/Tests/Core/Menu/MenuLinkTreeElementTest.php
@@ -0,0 +1,63 @@
+<?php
+
+/**
+ * @file
+ * Contains \Drupal\Tests\Core\Menu\MenuLinkTreeElementTest.
+ */
+
+namespace Drupal\Tests\Core\Menu;
+
+use Drupal\Core\Menu\MenuLinkTreeElement;
+use Drupal\Tests\UnitTestCase;
+
+/**
+ * Tests the menu link tree element value object.
+ *
+ * @group Drupal
+ * @group Menu
+ *
+ * @coversDefaultClass \Drupal\Core\Menu\MenuLinkTreeElement
+ */
+class MenuLinkTreeElementTest extends UnitTestCase {
+
+  /**
+   * {@inheritdoc}
+   */
+  public static function getInfo() {
+    return array(
+      'name' => 'Tests \Drupal\Core\Menu\MenuLinkTreeElement',
+      'description' => '',
+      'group' => 'Menu',
+    );
+  }
+
+  /**
+   * Tests construction.
+   *
+   * @covers ::__construct
+   */
+  public function testConstruction() {
+    $link = array();
+    $item = new MenuLinkTreeElement($link, FALSE, 3, FALSE, array());
+    $this->assertSame($link, $item->link);
+    $this->assertSame(FALSE, $item->hasChildren);
+    $this->assertSame(3, $item->depth);
+    $this->assertSame(FALSE, $item->inActiveTrail);
+    $this->assertSame(array(), $item->subtree);
+  }
+
+  /**
+   * Tests count().
+   *
+   * @covers ::count
+   */
+  public function testCount() {
+    $link_1 = array();
+    $link_2 = array();
+    $child_item = new MenuLinkTreeElement($link_2, FALSE, 2, FALSE, array());
+    $parent_item = new MenuLinkTreeElement($link_1, FALSE, 2, FALSE, array($child_item));
+    $this->assertSame(1, $child_item->count());
+    $this->assertSame(2, $parent_item->count());
+  }
+
+}