class MenuTreeStorage

class MenuTreeStorage implements MenuTreeStorageInterface {
    use MenuLinkFieldDefinitions;
    
    /**
     * The maximum depth of a menu links tree.
     */
    const MAX_DEPTH = 9;
    
    /**
     * The database connection.
     *
     * @var \Drupal\Core\Database\Connection
     */
    protected $connection;
    
    /**
     * Cache backend instance for the extracted tree data.
     *
     * @var \Drupal\Core\Cache\CacheBackendInterface
     */
    protected $menuCacheBackend;
    
    /**
     * The cache tags invalidator.
     *
     * @var \Drupal\Core\Cache\CacheTagsInvalidatorInterface
     */
    protected $cacheTagsInvalidator;
    
    /**
     * The database table name.
     *
     * @var string
     */
    protected $table;
    
    /**
     * Additional database connection options to use in queries.
     *
     * @var array
     */
    protected $options = [];
    
    /**
     * Stores definitions that have already been loaded for better performance.
     *
     * An array of plugin definition arrays, keyed by plugin ID.
     *
     * @var array
     */
    protected $definitions = [];
    
    /**
     * List of serialized fields.
     *
     * @var array
     */
    protected $serializedFields;
    
    /**
     * Constructs a new \Drupal\Core\Menu\MenuTreeStorage.
     *
     * @param \Drupal\Core\Database\Connection $connection
     *   A Database connection to use for reading and writing configuration data.
     * @param \Drupal\Core\Cache\CacheBackendInterface $menu_cache_backend
     *   Cache backend instance for the extracted tree data.
     * @param \Drupal\Core\Cache\CacheTagsInvalidatorInterface $cache_tags_invalidator
     *   The cache tags invalidator.
     * @param string $table
     *   A database table name to store configuration data in.
     * @param array $options
     *   (optional) Any additional database connection options to use in queries.
     */
    public function __construct(Connection $connection, CacheBackendInterface $menu_cache_backend, CacheTagsInvalidatorInterface $cache_tags_invalidator, $table, array $options = []) {
        $this->connection = $connection;
        $this->menuCacheBackend = $menu_cache_backend;
        $this->cacheTagsInvalidator = $cache_tags_invalidator;
        $this->table = $table;
        $this->options = $options;
    }
    
    /**
     * {@inheritdoc}
     */
    public function maxDepth() {
        return static::MAX_DEPTH;
    }
    
    /**
     * {@inheritdoc}
     */
    public function resetDefinitions() {
        $this->definitions = [];
    }
    
    /**
     * {@inheritdoc}
     */
    public function rebuild(array $definitions) {
        $links = [];
        $children = [];
        $top_links = [];
        // Fetch the list of existing menus, in case some are not longer populated
        // after the rebuild.
        $before_menus = $this->getMenuNames();
        if ($definitions) {
            foreach ($definitions as $id => $link) {
                // Flag this link as discovered, i.e. saved via rebuild().
                $link['discovered'] = 1;
                // Note: The parent we set here might be just stored in the {menu_tree}
                // table, so it will not end up in $top_links. Therefore the later loop
                // on the orphan links, will handle those cases.
                if (!empty($link['parent'])) {
                    $children[$link['parent']][$id] = $id;
                }
                else {
                    // A top level link - we need them to root our tree.
                    $top_links[$id] = $id;
                    $link['parent'] = '';
                }
                $links[$id] = $link;
            }
        }
        foreach ($top_links as $id) {
            $this->saveRecursive($id, $children, $links);
        }
        // Handle any children we didn't find starting from top-level links.
        foreach ($children as $orphan_links) {
            foreach ($orphan_links as $id) {
                // Check for a parent that is not loaded above since only internal links
                // are loaded above.
                $parent = $this->loadFull($links[$id]['parent']);
                // If there is a parent add it to the links to be used in
                // ::saveRecursive().
                if ($parent) {
                    $links[$links[$id]['parent']] = $parent;
                }
                else {
                    // Force it to the top level.
                    $links[$id]['parent'] = '';
                }
                $this->saveRecursive($id, $children, $links);
            }
        }
        $result = $this->findNoLongerExistingLinks($definitions);
        // Remove all such items.
        if ($result) {
            $this->purgeMultiple($result);
        }
        $this->resetDefinitions();
        $affected_menus = $this->getMenuNames() + $before_menus;
        // Invalidate any cache tagged with any menu name.
        $cache_tags = Cache::buildTags('config:system.menu', $affected_menus, '.');
        $this->cacheTagsInvalidator
            ->invalidateTags($cache_tags);
        $this->resetDefinitions();
        // Every item in the cache bin should have one of the menu cache tags but it
        // is not guaranteed, so invalidate everything in the bin.
        $this->menuCacheBackend
            ->invalidateAll();
    }
    
    /**
     * Purges multiple menu links that no longer exist.
     *
     * @param array $ids
     *   An array of menu link IDs.
     */
    protected function purgeMultiple(array $ids) {
        $loaded = $this->loadFullMultiple($ids);
        foreach ($loaded as $id => $link) {
            if ($link['has_children']) {
                $children = $this->loadByProperties([
                    'parent' => $id,
                ]);
                foreach ($children as $child) {
                    $child['parent'] = $link['parent'];
                    $this->save($child);
                }
            }
        }
        $this->doDeleteMultiple($ids);
    }
    
    /**
     * Executes a select query while making sure the database table exists.
     *
     * @param \Drupal\Core\Database\Query\SelectInterface $query
     *   The select object to be executed.
     *
     * @return \Drupal\Core\Database\StatementInterface|null
     *   A prepared statement, or NULL if the query is not valid.
     *
     * @throws \Exception
     *   Thrown if the table could not be created or the database connection
     *   failed.
     */
    protected function safeExecuteSelect(SelectInterface $query) {
        try {
            return $query->execute();
        } catch (\Exception $e) {
            // If there was an exception, try to create the table.
            if ($this->ensureTableExists()) {
                return $query->execute();
            }
            // Some other failure that we can not recover from.
            throw new PluginException($e->getMessage(), 0, $e);
        }
    }
    
    /**
     * {@inheritdoc}
     */
    public function save(array $link) {
        $affected_menus = $this->doSave($link);
        $this->resetDefinitions();
        $cache_tags = Cache::buildTags('config:system.menu', $affected_menus, '.');
        $this->cacheTagsInvalidator
            ->invalidateTags($cache_tags);
        return $affected_menus;
    }
    
    /**
     * Saves a link without clearing caches.
     *
     * @param array $link
     *   A definition, according to $definitionFields, for a
     *   \Drupal\Core\Menu\MenuLinkInterface plugin.
     *
     * @return array
     *   The menu names affected by the save operation. This will be one menu
     *   name if the link is saved to the sane menu, or two if it is saved to a
     *   new menu.
     *
     * @throws \Exception
     *   Thrown if the storage back-end does not exist and could not be created.
     * @throws \Drupal\Component\Plugin\Exception\PluginException
     *   Thrown if the definition is invalid, for example, if the specified parent
     *   would cause the links children to be moved to greater than the maximum
     *   depth.
     */
    protected function doSave(array $link) {
        $affected_menus = [];
        // Get the existing definition if it exists. This does not use
        // self::loadFull() to avoid the unserialization of fields with 'serialize'
        // equal to TRUE as defined in self::schemaDefinition(). The makes $original
        // easier to compare with the return value of self::preSave().
        $query = $this->connection
            ->select($this->table, NULL, $this->options);
        $query->fields($this->table);
        $query->condition('id', $link['id']);
        $original = $this->safeExecuteSelect($query)
            ->fetchAssoc();
        if ($original) {
            $link['mlid'] = $original['mlid'];
            $link['has_children'] = $original['has_children'];
            $affected_menus[$original['menu_name']] = $original['menu_name'];
            $fields = $this->preSave($link, $original);
            // If $link matches the $original data then exit early as there are no
            // changes to make. Use array_diff_assoc() to check if they match because:
            // - Some of the data types of the values are not the same. The values
            //   in $original are all strings because they have come from database but
            //   $fields contains typed values.
            // - MenuTreeStorage::preSave() removes the 'mlid' from $fields.
            // - The order of the keys in $original and $fields is different.
            if (array_diff_assoc($fields, $original) == [] && array_diff_assoc($original, $fields) == [
                'mlid' => $link['mlid'],
            ]) {
                return $affected_menus;
            }
        }
        try {
            $transaction = $this->connection
                ->startTransaction();
            if (!$original) {
                // Generate a new mlid.
                // @todo Remove the 'return' option in Drupal 11.
                // @see https://www.drupal.org/project/drupal/issues/3256524
                $options = [
                    'return' => Database::RETURN_INSERT_ID,
                ] + $this->options;
                $link['mlid'] = $this->connection
                    ->insert($this->table, $options)
                    ->fields([
                    'id' => $link['id'],
                    'menu_name' => $link['menu_name'],
                ])
                    ->execute();
                $fields = $this->preSave($link, []);
            }
            // We may be moving the link to a new menu.
            $affected_menus[$fields['menu_name']] = $fields['menu_name'];
            $query = $this->connection
                ->update($this->table, $this->options);
            $query->condition('mlid', $link['mlid']);
            $query->fields($fields)
                ->execute();
            if ($original) {
                $this->updateParentalStatus($original);
            }
            $this->updateParentalStatus($link);
        } catch (\Exception $e) {
            if (isset($transaction)) {
                $transaction->rollBack();
            }
            throw $e;
        }
        return $affected_menus;
    }
    
    /**
     * Fills in all the fields the database save needs, using the link definition.
     *
     * @param array $link
     *   The link definition to be updated.
     * @param array $original
     *   The link definition before the changes. May be empty if not found.
     *
     * @return array
     *   The values which will be stored.
     *
     * @throws \Drupal\Component\Plugin\Exception\PluginException
     *   Thrown when the specific depth exceeds the maximum.
     */
    protected function preSave(array &$link, array $original) {
        static $schema_fields, $schema_defaults;
        if (empty($schema_fields)) {
            $schema = static::schemaDefinition();
            $schema_fields = $schema['fields'];
            foreach ($schema_fields as $name => $spec) {
                if (isset($spec['default'])) {
                    $schema_defaults[$name] = $spec['default'];
                }
            }
        }
        // Try to find a parent link. If found, assign it and derive its menu.
        $parent = $this->findParent($link, $original);
        if ($parent) {
            $link['parent'] = $parent['id'];
            $link['menu_name'] = $parent['menu_name'];
        }
        else {
            $link['parent'] = '';
        }
        // If no corresponding parent link was found, move the link to the
        // top-level.
        foreach ($schema_defaults as $name => $default) {
            if (!isset($link[$name])) {
                $link[$name] = $default;
            }
        }
        $fields = array_intersect_key($link, $schema_fields);
        // Sort the route parameters so that the query string will be the same.
        asort($fields['route_parameters']);
        // Since this will be urlencoded, it's safe to store and match against a
        // text field.
        $fields['route_param_key'] = $fields['route_parameters'] ? UrlHelper::buildQuery($fields['route_parameters']) : '';
        foreach ($this->serializedFields() as $name) {
            if (isset($fields[$name])) {
                $fields[$name] = serialize($fields[$name]);
            }
        }
        $this->setParents($fields, $parent, $original);
        // Need to check both parent and menu_name, since parent can be empty in any
        // menu.
        if ($original && ($link['parent'] != $original['parent'] || $link['menu_name'] != $original['menu_name'])) {
            $this->moveChildren($fields, $original);
        }
        // We needed the mlid above, but not in the update query.
        unset($fields['mlid']);
        // Cast Booleans to int, if needed.
        $fields['enabled'] = (int) $fields['enabled'];
        $fields['expanded'] = (int) $fields['expanded'];
        return $fields;
    }
    
    /**
     * {@inheritdoc}
     */
    public function delete($id) {
        // Children get re-attached to the menu link's parent.
        $item = $this->loadFull($id);
        // It's possible the link is already deleted.
        if ($item) {
            $parent = $item['parent'];
            $children = $this->loadByProperties([
                'parent' => $id,
            ]);
            foreach ($children as $child) {
                $child['parent'] = $parent;
                $this->save($child);
            }
            $this->doDeleteMultiple([
                $id,
            ]);
            $this->updateParentalStatus($item);
            // Many children may have moved.
            $this->resetDefinitions();
            $this->cacheTagsInvalidator
                ->invalidateTags([
                'config:system.menu.' . $item['menu_name'],
            ]);
        }
    }
    
    /**
     * {@inheritdoc}
     */
    public function getSubtreeHeight($id) {
        $original = $this->loadFull($id);
        return $original ? $this->doFindChildrenRelativeDepth($original) + 1 : 0;
    }
    
    /**
     * Finds the relative depth of this link's deepest child.
     *
     * @param array $original
     *   The parent definition used to find the depth.
     *
     * @return int
     *   Returns the relative depth.
     */
    protected function doFindChildrenRelativeDepth(array $original) {
        $query = $this->connection
            ->select($this->table, NULL, $this->options);
        $query->addField($this->table, 'depth');
        $query->condition('menu_name', $original['menu_name']);
        $query->orderBy('depth', 'DESC');
        $query->range(0, 1);
        for ($i = 1; $i <= static::MAX_DEPTH && $original["p{$i}"]; $i++) {
            $query->condition("p{$i}", $original["p{$i}"]);
        }
        $max_depth = $this->safeExecuteSelect($query)
            ->fetchField();
        return $max_depth > $original['depth'] ? $max_depth - $original['depth'] : 0;
    }
    
    /**
     * Sets the materialized path field values based on the parent.
     *
     * @param array $fields
     *   The menu link.
     * @param array|false $parent
     *   The parent menu link.
     * @param array $original
     *   The original menu link.
     */
    protected function setParents(array &$fields, $parent, array $original) {
        // Directly fill parents for top-level links.
        if (empty($fields['parent'])) {
            $fields['p1'] = $fields['mlid'];
            for ($i = 2; $i <= $this->maxDepth(); $i++) {
                $fields["p{$i}"] = 0;
            }
            $fields['depth'] = 1;
        }
        else {
            // @todo We want to also check $original['has_children'] here, but that
            //   will be 0 even if there are children if those are not enabled.
            //   has_children is really just the rendering hint. So, we either need
            //   to define another column (has_any_children), or do the extra query.
            //   https://www.drupal.org/node/2302149
            if ($original) {
                $limit = $this->maxDepth() - $this->doFindChildrenRelativeDepth($original) - 1;
            }
            else {
                $limit = $this->maxDepth() - 1;
            }
            if ($parent['depth'] > $limit) {
                throw new PluginException("The link with ID {$fields['id']} or its children exceeded the maximum depth of {$this->maxDepth()}");
            }
            $fields['depth'] = $parent['depth'] + 1;
            $i = 1;
            while ($i < $fields['depth']) {
                $p = 'p' . $i++;
                $fields[$p] = $parent[$p];
            }
            $p = 'p' . $i++;
            // The parent (p1 - p9) corresponding to the depth always equals the mlid.
            $fields[$p] = $fields['mlid'];
            while ($i <= static::MAX_DEPTH) {
                $p = 'p' . $i++;
                $fields[$p] = 0;
            }
        }
    }
    
    /**
     * Re-parents a link's children when the link itself is moved.
     *
     * @param array $fields
     *   The changed menu link.
     * @param array $original
     *   The original menu link.
     */
    protected function moveChildren($fields, $original) {
        $query = $this->connection
            ->update($this->table, $this->options);
        $query->fields([
            'menu_name' => $fields['menu_name'],
        ]);
        $expressions = [];
        for ($i = 1; $i <= $fields['depth']; $i++) {
            $expressions[] = [
                "p{$i}",
                ":p_{$i}",
                [
                    ":p_{$i}" => $fields["p{$i}"],
                ],
            ];
        }
        $j = $original['depth'] + 1;
        while ($i <= $this->maxDepth() && $j <= $this->maxDepth()) {
            $expressions[] = [
                'p' . $i++,
                'p' . $j++,
                [],
            ];
        }
        while ($i <= $this->maxDepth()) {
            $expressions[] = [
                'p' . $i++,
                0,
                [],
            ];
        }
        $shift = $fields['depth'] - $original['depth'];
        if ($shift > 0) {
            // The order of expressions must be reversed so the new values don't
            // overwrite the old ones before they can be used because "Single-table
            // UPDATE assignments are generally evaluated from left to right".
            // @see http://dev.mysql.com/doc/refman/5.0/en/update.html
            $expressions = array_reverse($expressions);
        }
        foreach ($expressions as $expression) {
            $query->expression($expression[0], $expression[1], $expression[2]);
        }
        $query->expression('depth', '[depth] + :depth', [
            ':depth' => $shift,
        ]);
        $query->condition('menu_name', $original['menu_name']);
        for ($i = 1; $i <= $this->maxDepth() && $original["p{$i}"]; $i++) {
            $query->condition("p{$i}", $original["p{$i}"]);
        }
        $query->execute();
    }
    
    /**
     * Loads the parent definition if it exists.
     *
     * @param array $link
     *   The link definition to find the parent of.
     * @param array|false $original
     *   The original link that might be used to find the parent if the parent
     *   is not set on the $link, or FALSE if the original could not be loaded.
     *
     * @return array|false
     *   Returns a definition array, or FALSE if no parent was found.
     */
    protected function findParent($link, $original) {
        $parent = FALSE;
        // This item is explicitly top-level, skip the rest of the parenting.
        if (isset($link['parent']) && empty($link['parent'])) {
            return $parent;
        }
        // If we have a parent link ID, try to use that.
        $candidates = [];
        if (isset($link['parent'])) {
            $candidates[] = $link['parent'];
        }
        elseif (!empty($original['parent']) && $link['menu_name'] == $original['menu_name']) {
            // Otherwise, fall back to the original parent.
            $candidates[] = $original['parent'];
        }
        foreach ($candidates as $id) {
            $parent = $this->loadFull($id);
            if ($parent) {
                break;
            }
        }
        return $parent;
    }
    
    /**
     * Sets has_children for the link's parent if it has visible children.
     *
     * @param array $link
     *   The link to get a parent ID from.
     */
    protected function updateParentalStatus(array $link) {
        // If parent is empty, there is nothing to update.
        if (!empty($link['parent'])) {
            // Check if at least one visible child exists in the table.
            $query = $this->connection
                ->select($this->table, NULL, $this->options);
            $query->addExpression('1');
            $query->range(0, 1);
            $query->condition('menu_name', $link['menu_name'])
                ->condition('parent', $link['parent'])
                ->condition('enabled', 1);
            $parent_has_children = (bool) $query->execute()
                ->fetchField() ? 1 : 0;
            $this->connection
                ->update($this->table, $this->options)
                ->fields([
                'has_children' => $parent_has_children,
            ])
                ->condition('id', $link['parent'])
                ->execute();
        }
    }
    
    /**
     * Prepares a link by unserializing values and saving the definition.
     *
     * @param array $link
     *   The data loaded in the query.
     * @param bool $intersect
     *   If TRUE, filter out values that are not part of the actual definition.
     *
     * @return array
     *   The prepared link data.
     */
    protected function prepareLink(array $link, $intersect = FALSE) {
        foreach ($this->serializedFields() as $name) {
            if (isset($link[$name])) {
                $link[$name] = unserialize($link[$name]);
            }
        }
        if ($intersect) {
            $link = array_intersect_key($link, array_flip($this->definitionFields()));
        }
        $this->definitions[$link['id']] = $link;
        return $link;
    }
    
    /**
     * {@inheritdoc}
     */
    public function loadByProperties(array $properties) {
        $query = $this->connection
            ->select($this->table, NULL, $this->options);
        $query->fields($this->table, $this->definitionFields());
        foreach ($properties as $name => $value) {
            if (!in_array($name, $this->definitionFields(), TRUE)) {
                $fields = implode(', ', $this->definitionFields());
                throw new \InvalidArgumentException("An invalid property name, {$name} was specified. Allowed property names are: {$fields}.");
            }
            $query->condition($name, $value);
        }
        $loaded = $this->safeExecuteSelect($query)
            ->fetchAllAssoc('id', \PDO::FETCH_ASSOC);
        foreach ($loaded as $id => $link) {
            $loaded[$id] = $this->prepareLink($link);
        }
        return $loaded;
    }
    
    /**
     * {@inheritdoc}
     */
    public function loadByRoute($route_name, array $route_parameters = [], $menu_name = NULL) {
        // Sort the route parameters so that the query string will be the same.
        asort($route_parameters);
        // Since this will be urlencoded, it's safe to store and match against a
        // text field.
        // @todo Standardize an efficient way to load by route name and parameters
        //   in place of system path. https://www.drupal.org/node/2302139
        $param_key = $route_parameters ? UrlHelper::buildQuery($route_parameters) : '';
        $query = $this->connection
            ->select($this->table, NULL, $this->options);
        $query->fields($this->table, $this->definitionFields());
        $query->condition('route_name', $route_name);
        $query->condition('route_param_key', $param_key);
        if ($menu_name) {
            $query->condition('menu_name', $menu_name);
        }
        // Make the ordering deterministic.
        $query->orderBy('depth');
        $query->orderBy('weight');
        $query->orderBy('id');
        $loaded = $this->safeExecuteSelect($query)
            ->fetchAllAssoc('id', \PDO::FETCH_ASSOC);
        foreach ($loaded as $id => $link) {
            $loaded[$id] = $this->prepareLink($link);
        }
        return $loaded;
    }
    
    /**
     * {@inheritdoc}
     */
    public function loadMultiple(array $ids) {
        $missing_ids = array_diff($ids, array_keys($this->definitions));
        if ($missing_ids) {
            $query = $this->connection
                ->select($this->table, NULL, $this->options);
            $query->fields($this->table, $this->definitionFields());
            $query->condition('id', $missing_ids, 'IN');
            $loaded = $this->safeExecuteSelect($query)
                ->fetchAllAssoc('id', \PDO::FETCH_ASSOC);
            foreach ($loaded as $id => $link) {
                $this->definitions[$id] = $this->prepareLink($link);
            }
        }
        return array_intersect_key($this->definitions, array_flip($ids));
    }
    
    /**
     * {@inheritdoc}
     */
    public function load($id) {
        if (isset($this->definitions[$id])) {
            return $this->definitions[$id];
        }
        $loaded = $this->loadMultiple([
            $id,
        ]);
        return $loaded[$id] ?? FALSE;
    }
    
    /**
     * Loads all table fields, not just those that are in the plugin definition.
     *
     * @param string $id
     *   The menu link ID.
     *
     * @return array
     *   The loaded menu link definition or an empty array if not be found.
     */
    protected function loadFull($id) {
        $loaded = $this->loadFullMultiple([
            $id,
        ]);
        return $loaded[$id] ?? [];
    }
    
    /**
     * Loads all table fields for multiple menu link definitions by ID.
     *
     * @param array $ids
     *   The IDs to load.
     *
     * @return array
     *   The loaded menu link definitions.
     */
    protected function loadFullMultiple(array $ids) {
        $query = $this->connection
            ->select($this->table, NULL, $this->options);
        $query->fields($this->table);
        $query->condition('id', $ids, 'IN');
        $loaded = $this->safeExecuteSelect($query)
            ->fetchAllAssoc('id', \PDO::FETCH_ASSOC);
        foreach ($loaded as &$link) {
            foreach ($this->serializedFields() as $name) {
                if (isset($link[$name])) {
                    $link[$name] = unserialize($link[$name]);
                }
            }
        }
        return $loaded;
    }
    
    /**
     * {@inheritdoc}
     */
    public function getRootPathIds($id) {
        $subquery = $this->connection
            ->select($this->table, NULL, $this->options);
        // @todo Consider making this dynamic based on static::MAX_DEPTH or from the
        //   schema if that is generated using static::MAX_DEPTH.
        //   https://www.drupal.org/node/2302043
        $subquery->fields($this->table, [
            'p1',
            'p2',
            'p3',
            'p4',
            'p5',
            'p6',
            'p7',
            'p8',
            'p9',
        ]);
        $subquery->condition('id', $id);
        $result = current($subquery->execute()
            ->fetchAll(\PDO::FETCH_ASSOC));
        $ids = array_filter($result);
        if ($ids) {
            $query = $this->connection
                ->select($this->table, NULL, $this->options);
            $query->fields($this->table, [
                'id',
            ]);
            $query->orderBy('depth', 'DESC');
            $query->condition('mlid', $ids, 'IN');
            // @todo Cache this result in memory if we find it is being used more
            //   than once per page load. https://www.drupal.org/node/2302185
            return $this->safeExecuteSelect($query)
                ->fetchAllKeyed(0, 0);
        }
        return [];
    }
    
    /**
     * {@inheritdoc}
     */
    public function getExpanded($menu_name, array $parents) {
        // @todo Go back to tracking in state or some other way which menus have
        //   expanded links? https://www.drupal.org/node/2302187
        do {
            $query = $this->connection
                ->select($this->table, NULL, $this->options);
            $query->fields($this->table, [
                'id',
            ]);
            $query->condition('menu_name', $menu_name);
            $query->condition('expanded', 1);
            $query->condition('has_children', 1);
            $query->condition('enabled', 1);
            $query->condition('parent', $parents, 'IN');
            $query->condition('id', $parents, 'NOT IN');
            $result = $this->safeExecuteSelect($query)
                ->fetchAllKeyed(0, 0);
            $parents += $result;
        } while (!empty($result));
        return $parents;
    }
    
    /**
     * Saves menu links recursively.
     *
     * @param string $id
     *   The definition ID.
     * @param array $children
     *   An array of IDs of child links collected by parent ID.
     * @param array $links
     *   An array of all definitions keyed by ID.
     */
    protected function saveRecursive($id, &$children, &$links) {
        if (!empty($links[$id]['parent']) && empty($links[$links[$id]['parent']])) {
            // Invalid parent ID, so remove it.
            $links[$id]['parent'] = '';
        }
        $this->doSave($links[$id]);
        if (!empty($children[$id])) {
            foreach ($children[$id] as $next_id) {
                $this->saveRecursive($next_id, $children, $links);
            }
        }
        // Remove processed link names so we can find stragglers.
        unset($children[$id]);
    }
    
    /**
     * {@inheritdoc}
     */
    public function loadTreeData($menu_name, MenuTreeParameters $parameters) {
        $tree_cid = "tree-data:{$menu_name}:" . serialize($parameters);
        $cache = $this->menuCacheBackend
            ->get($tree_cid);
        if ($cache && isset($cache->data)) {
            $data = $cache->data;
            // Cache the definitions in memory so they don't need to be loaded again.
            $this->definitions += $data['definitions'];
            unset($data['definitions']);
        }
        else {
            $links = $this->loadLinks($menu_name, $parameters);
            $data['tree'] = $this->doBuildTreeData($links, $parameters->activeTrail, $parameters->minDepth);
            $data['definitions'] = [];
            $data['route_names'] = $this->collectRoutesAndDefinitions($data['tree'], $data['definitions']);
            $this->menuCacheBackend
                ->set($tree_cid, $data, Cache::PERMANENT, [
                'config:system.menu.' . $menu_name,
            ]);
            // The definitions were already added to $this->definitions in
            // $this->doBuildTreeData()
            unset($data['definitions']);
        }
        return $data;
    }
    
    /**
     * Loads links in the given menu, according to the given tree parameters.
     *
     * @param string $menu_name
     *   A menu name.
     * @param \Drupal\Core\Menu\MenuTreeParameters $parameters
     *   The parameters to determine which menu links to be loaded into a tree.
     *   This method will set the absolute minimum depth, which is used in
     *   MenuTreeStorage::doBuildTreeData().
     *
     * @return array
     *   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_tree} table. This array must be ordered
     *   depth-first.
     */
    protected function loadLinks($menu_name, MenuTreeParameters $parameters) {
        $query = $this->connection
            ->select($this->table, NULL, $this->options);
        $query->fields($this->table);
        // Allow a custom root to be specified for loading a menu link tree. If
        // omitted, the default root (i.e. the actual root, '') is used.
        if ($parameters->root !== '') {
            $root = $this->loadFull($parameters->root);
            // If the custom root does not exist, we cannot load the links below it.
            if (!$root) {
                return [];
            }
            // When specifying a custom root, we only want to find links whose
            // parent IDs match that of the root; that's how we ignore the rest of the
            // tree. In other words: we exclude everything unreachable from the
            // custom root.
            for ($i = 1; $i <= $root['depth']; $i++) {
                $query->condition("p{$i}", $root["p{$i}"]);
            }
            // When specifying a custom root, the menu is determined by that root.
            $menu_name = $root['menu_name'];
            // If the custom root exists, then we must rewrite some of our
            // parameters; parameters are relative to the root (default or custom),
            // but the queries require absolute numbers, so adjust correspondingly.
            if (isset($parameters->minDepth)) {
                $parameters->minDepth += $root['depth'];
            }
            else {
                $parameters->minDepth = $root['depth'];
            }
            if (isset($parameters->maxDepth)) {
                $parameters->maxDepth += $root['depth'];
            }
        }
        // If no minimum depth is specified, then set the actual minimum depth,
        // depending on the root.
        if (!isset($parameters->minDepth)) {
            if ($parameters->root !== '' && $root) {
                $parameters->minDepth = $root['depth'];
            }
            else {
                $parameters->minDepth = 1;
            }
        }
        for ($i = 1; $i <= $this->maxDepth(); $i++) {
            $query->orderBy('p' . $i, 'ASC');
        }
        $query->condition('menu_name', $menu_name);
        if (!empty($parameters->expandedParents)) {
            $query->condition('parent', $parameters->expandedParents, 'IN');
        }
        if (isset($parameters->minDepth) && $parameters->minDepth > 1) {
            $query->condition('depth', $parameters->minDepth, '>=');
        }
        if (isset($parameters->maxDepth)) {
            $query->condition('depth', $parameters->maxDepth, '<=');
        }
        // Add custom query conditions, if any were passed.
        if (!empty($parameters->conditions)) {
            // Only allow conditions that are testing definition fields.
            $parameters->conditions = array_intersect_key($parameters->conditions, array_flip($this->definitionFields()));
            $serialized_fields = $this->serializedFields();
            foreach ($parameters->conditions as $column => $value) {
                if (is_array($value)) {
                    $operator = $value[1];
                    $value = $value[0];
                }
                else {
                    $operator = '=';
                }
                if (in_array($column, $serialized_fields)) {
                    $value = serialize($value);
                }
                $query->condition($column, $value, $operator);
            }
        }
        $links = $this->safeExecuteSelect($query)
            ->fetchAllAssoc('id', \PDO::FETCH_ASSOC);
        return $links;
    }
    
    /**
     * Traverses the menu tree and collects all the route names and definitions.
     *
     * @param array $tree
     *   The menu tree you wish to operate on.
     * @param array $definitions
     *   An array to accumulate definitions by reference.
     *
     * @return array
     *   Array of route names, with all values being unique.
     */
    protected function collectRoutesAndDefinitions(array $tree, array &$definitions) {
        return array_values($this->doCollectRoutesAndDefinitions($tree, $definitions));
    }
    
    /**
     * Collects all the route names and definitions.
     *
     * @param array $tree
     *   A menu link tree from MenuTreeStorage::doBuildTreeData()
     * @param array $definitions
     *   The collected definitions which are populated by reference.
     *
     * @return array
     *   The collected route names.
     */
    protected function doCollectRoutesAndDefinitions(array $tree, array &$definitions) {
        $route_names = [];
        foreach (array_keys($tree) as $id) {
            $definitions[$id] = $this->definitions[$id];
            if (!empty($definitions[$id]['route_name'])) {
                $route_names[$definitions[$id]['route_name']] = $definitions[$id]['route_name'];
            }
            if ($tree[$id]['subtree']) {
                $route_names += $this->doCollectRoutesAndDefinitions($tree[$id]['subtree'], $definitions);
            }
        }
        return $route_names;
    }
    
    /**
     * {@inheritdoc}
     */
    public function loadSubtreeData($id, $max_relative_depth = NULL) {
        $tree = [];
        $root = $this->loadFull($id);
        if (!$root) {
            return $tree;
        }
        $parameters = new MenuTreeParameters();
        $parameters->setRoot($id)
            ->onlyEnabledLinks();
        return $this->loadTreeData($root['menu_name'], $parameters);
    }
    
    /**
     * {@inheritdoc}
     */
    public function menuNameInUse($menu_name) {
        $query = $this->connection
            ->select($this->table, NULL, $this->options);
        $query->addField($this->table, 'mlid');
        $query->condition('menu_name', $menu_name);
        $query->range(0, 1);
        return (bool) $this->safeExecuteSelect($query);
    }
    
    /**
     * {@inheritdoc}
     */
    public function getMenuNames() {
        $query = $this->connection
            ->select($this->table, NULL, $this->options);
        $query->addField($this->table, 'menu_name');
        $query->distinct();
        return $this->safeExecuteSelect($query)
            ->fetchAllKeyed(0, 0);
    }
    
    /**
     * {@inheritdoc}
     */
    public function countMenuLinks($menu_name = NULL) {
        $query = $this->connection
            ->select($this->table, NULL, $this->options);
        if ($menu_name) {
            $query->condition('menu_name', $menu_name);
        }
        return $this->safeExecuteSelect($query->countQuery())
            ->fetchField();
    }
    
    /**
     * {@inheritdoc}
     */
    public function getAllChildIds($id) {
        $root = $this->loadFull($id);
        if (!$root) {
            return [];
        }
        $query = $this->connection
            ->select($this->table, NULL, $this->options);
        $query->fields($this->table, [
            'id',
        ]);
        $query->condition('menu_name', $root['menu_name']);
        for ($i = 1; $i <= $root['depth']; $i++) {
            $query->condition("p{$i}", $root["p{$i}"]);
        }
        // The next p column should not be empty. This excludes the root link.
        $query->condition("p{$i}", 0, '>');
        return $this->safeExecuteSelect($query)
            ->fetchAllKeyed(0, 0);
    }
    
    /**
     * {@inheritdoc}
     */
    public function loadAllChildren($id, $max_relative_depth = NULL) {
        $parameters = new MenuTreeParameters();
        $parameters->setRoot($id)
            ->excludeRoot()
            ->setMaxDepth($max_relative_depth)
            ->onlyEnabledLinks();
        $links = $this->loadLinks(NULL, $parameters);
        foreach ($links as $id => $link) {
            $links[$id] = $this->prepareLink($link);
        }
        return $links;
    }
    
    /**
     * Prepares the data for calling $this->treeDataRecursive().
     */
    protected function doBuildTreeData(array $links, array $parents = [], $depth = 1) {
        // Reverse the array so we can use the more efficient array_pop() function.
        $links = array_reverse($links);
        return $this->treeDataRecursive($links, $parents, $depth);
    }
    
    /**
     * Builds the data representing a menu tree.
     *
     * The function is a bit complex because the rendering of a link depends on
     * the next menu link.
     *
     * @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 $this->table. This array must be ordered
     *   depth-first. MenuTreeStorage::loadTreeData() includes 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.
     * @param int $depth
     *   The minimum depth to include in the returned menu tree.
     *
     * @return array
     *   The fully built tree.
     *
     * @see \Drupal\Core\Menu\MenuTreeStorage::loadTreeData()
     */
    protected function treeDataRecursive(array &$links, array $parents, $depth) {
        $tree = [];
        while ($tree_link_definition = array_pop($links)) {
            $tree[$tree_link_definition['id']] = [
                'definition' => $this->prepareLink($tree_link_definition, TRUE),
                'has_children' => $tree_link_definition['has_children'],
                // We need to determine if we're on the path to root so we can later
                // build the correct active trail.
'in_active_trail' => in_array($tree_link_definition['id'], $parents),
                'subtree' => [],
                'depth' => $tree_link_definition['depth'],
            ];
            // 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.
            $next = end($links);
            // 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[$tree_link_definition['id']]['subtree'] = $this->treeDataRecursive($links, $parents, $next['depth']);
                // Fetch next link after filling the sub-tree.
                $next = end($links);
            }
            // Determine if we should exit the loop and return.
            if (!$next || $next['depth'] < $depth) {
                break;
            }
        }
        return $tree;
    }
    
    /**
     * Checks if the tree table exists and create it if not.
     *
     * @return bool
     *   TRUE if the table was created, FALSE otherwise.
     */
    protected function ensureTableExists() {
        try {
            $this->connection
                ->schema()
                ->createTable($this->table, static::schemaDefinition());
        } catch (DatabaseException $e) {
            // If another process has already created the config table, attempting to
            // recreate it will throw an exception. In this case just catch the
            // exception and do nothing.
        } catch (\Exception $e) {
            return FALSE;
        }
        return TRUE;
    }
    
    /**
     * Determines serialized fields in the storage.
     *
     * @return array
     *   A list of fields that are serialized in the database.
     */
    protected function serializedFields() {
        if (empty($this->serializedFields)) {
            $schema = static::schemaDefinition();
            foreach ($schema['fields'] as $name => $field) {
                if (!empty($field['serialize'])) {
                    $this->serializedFields[] = $name;
                }
            }
        }
        return $this->serializedFields;
    }
    
    /**
     * Determines fields that are part of the plugin definition.
     *
     * @return string[]
     *   The list of the subset of fields that are part of the plugin definition.
     */
    protected function definitionFields() {
        return array_keys($this->defaults);
    }
    
    /**
     * Defines the schema for the tree table.
     *
     * @return array
     *   The schema API definition for the SQL storage table.
     *
     * @internal
     */
    protected static function schemaDefinition() {
        $schema = [
            'description' => 'Contains the menu tree hierarchy.',
            'fields' => [
                'menu_name' => [
                    'description' => "The menu name. All links with the same menu name (such as 'tools') are part of the same menu.",
                    'type' => 'varchar_ascii',
                    'length' => 32,
                    'not null' => TRUE,
                    'default' => '',
                ],
                'mlid' => [
                    'description' => 'The menu link ID (mlid) is the integer primary key.',
                    'type' => 'serial',
                    'unsigned' => TRUE,
                    'not null' => TRUE,
                ],
                'id' => [
                    'description' => 'Unique machine name: the plugin ID.',
                    'type' => 'varchar_ascii',
                    'length' => 255,
                    'not null' => TRUE,
                ],
                'parent' => [
                    'description' => 'The plugin ID for the parent of this link.',
                    'type' => 'varchar_ascii',
                    'length' => 255,
                    'not null' => TRUE,
                    'default' => '',
                ],
                'route_name' => [
                    'description' => 'The machine name of a defined Symfony Route this menu link represents.',
                    'type' => 'varchar_ascii',
                    'length' => 255,
                ],
                'route_param_key' => [
                    'description' => 'An encoded string of route parameters for loading by route.',
                    'type' => 'varchar',
                    'length' => 255,
                ],
                'route_parameters' => [
                    'description' => 'Serialized array of route parameters of this menu link.',
                    'type' => 'blob',
                    'size' => 'big',
                    'not null' => FALSE,
                    'serialize' => TRUE,
                ],
                'url' => [
                    'description' => 'The external path this link points to (when not using a route).',
                    'type' => 'varchar',
                    'length' => 255,
                    'not null' => TRUE,
                    'default' => '',
                ],
                'title' => [
                    'description' => 'The serialized title for the link. May be a TranslatableMarkup.',
                    'type' => 'blob',
                    'size' => 'big',
                    'not null' => FALSE,
                    'serialize' => TRUE,
                ],
                'description' => [
                    'description' => 'The serialized description of this link - used for admin pages and title attribute. May be a TranslatableMarkup.',
                    'type' => 'blob',
                    'size' => 'big',
                    'not null' => FALSE,
                    'serialize' => TRUE,
                ],
                'class' => [
                    'description' => 'The class for this link plugin.',
                    'type' => 'text',
                    'not null' => FALSE,
                ],
                'options' => [
                    'description' => 'A serialized array of URL options, such as a query string or HTML attributes.',
                    'type' => 'blob',
                    'size' => 'big',
                    'not null' => FALSE,
                    'serialize' => TRUE,
                ],
                'provider' => [
                    'description' => 'The name of the module that generated this link.',
                    'type' => 'varchar_ascii',
                    'length' => DRUPAL_EXTENSION_NAME_MAX_LENGTH,
                    'not null' => TRUE,
                    'default' => 'system',
                ],
                'enabled' => [
                    'description' => 'A flag for whether the link should be rendered in menus. (0 = a disabled menu link that may be shown on admin screens, 1 = a normal, visible link)',
                    'type' => 'int',
                    'not null' => TRUE,
                    'default' => 1,
                    'size' => 'small',
                ],
                'discovered' => [
                    'description' => 'A flag for whether the link was discovered, so can be purged on rebuild',
                    'type' => 'int',
                    'not null' => TRUE,
                    'default' => 0,
                    'size' => 'small',
                ],
                'expanded' => [
                    'description' => 'Flag for whether this link should be rendered as expanded in menus - expanded links always have their child links displayed, instead of only when the link is in the active trail (1 = expanded, 0 = not expanded)',
                    'type' => 'int',
                    'not null' => TRUE,
                    'default' => 0,
                    'size' => 'small',
                ],
                'weight' => [
                    'description' => 'Link weight among links in the same menu at the same depth.',
                    'type' => 'int',
                    'not null' => TRUE,
                    'default' => 0,
                ],
                'metadata' => [
                    'description' => 'A serialized array of data that may be used by the plugin instance.',
                    'type' => 'blob',
                    'size' => 'big',
                    'not null' => FALSE,
                    'serialize' => TRUE,
                ],
                'has_children' => [
                    'description' => 'Flag indicating whether any enabled links have this link as a parent (1 = enabled children exist, 0 = no enabled children).',
                    'type' => 'int',
                    'not null' => TRUE,
                    'default' => 0,
                    'size' => 'small',
                ],
                'depth' => [
                    'description' => 'The depth relative to the top level. A link with empty parent will have depth == 1.',
                    'type' => 'int',
                    'not null' => TRUE,
                    'default' => 0,
                    'size' => 'small',
                ],
                'p1' => [
                    'description' => 'The first mlid in the materialized path. If N = depth, then pN must equal the mlid. If depth > 1 then p(N-1) must equal the parent link mlid. All pX where X > depth must equal zero. The columns p1 .. p9 are also called the parents.',
                    'type' => 'int',
                    'unsigned' => TRUE,
                    'not null' => TRUE,
                    'default' => 0,
                ],
                'p2' => [
                    'description' => 'The second mlid in the materialized path. See p1.',
                    'type' => 'int',
                    'unsigned' => TRUE,
                    'not null' => TRUE,
                    'default' => 0,
                ],
                'p3' => [
                    'description' => 'The third mlid in the materialized path. See p1.',
                    'type' => 'int',
                    'unsigned' => TRUE,
                    'not null' => TRUE,
                    'default' => 0,
                ],
                'p4' => [
                    'description' => 'The fourth mlid in the materialized path. See p1.',
                    'type' => 'int',
                    'unsigned' => TRUE,
                    'not null' => TRUE,
                    'default' => 0,
                ],
                'p5' => [
                    'description' => 'The fifth mlid in the materialized path. See p1.',
                    'type' => 'int',
                    'unsigned' => TRUE,
                    'not null' => TRUE,
                    'default' => 0,
                ],
                'p6' => [
                    'description' => 'The sixth mlid in the materialized path. See p1.',
                    'type' => 'int',
                    'unsigned' => TRUE,
                    'not null' => TRUE,
                    'default' => 0,
                ],
                'p7' => [
                    'description' => 'The seventh mlid in the materialized path. See p1.',
                    'type' => 'int',
                    'unsigned' => TRUE,
                    'not null' => TRUE,
                    'default' => 0,
                ],
                'p8' => [
                    'description' => 'The eighth mlid in the materialized path. See p1.',
                    'type' => 'int',
                    'unsigned' => TRUE,
                    'not null' => TRUE,
                    'default' => 0,
                ],
                'p9' => [
                    'description' => 'The ninth mlid in the materialized path. See p1.',
                    'type' => 'int',
                    'unsigned' => TRUE,
                    'not null' => TRUE,
                    'default' => 0,
                ],
                'form_class' => [
                    'description' => 'meh',
                    'type' => 'varchar',
                    'length' => 255,
                ],
            ],
            'indexes' => [
                'menu_parents' => [
                    'menu_name',
                    'p1',
                    'p2',
                    'p3',
                    'p4',
                    'p5',
                    'p6',
                    'p7',
                    'p8',
                    'p9',
                ],
                // @todo Test this index for effectiveness.
                //   https://www.drupal.org/node/2302197
'menu_parent_expand_child' => [
                    'menu_name',
                    'expanded',
                    'has_children',
                    [
                        'parent',
                        16,
                    ],
                ],
                'route_values' => [
                    [
                        'route_name',
                        32,
                    ],
                    [
                        'route_param_key',
                        16,
                    ],
                ],
            ],
            'primary key' => [
                'mlid',
            ],
            'unique keys' => [
                'id' => [
                    'id',
                ],
            ],
        ];
        return $schema;
    }
    
    /**
     * Find any previously discovered menu links that no longer exist.
     *
     * @param array $definitions
     *   The new menu link definitions.
     *
     * @return array
     *   A list of menu link IDs that no longer exist.
     */
    protected function findNoLongerExistingLinks(array $definitions) {
        if ($definitions) {
            $query = $this->connection
                ->select($this->table, NULL, $this->options);
            $query->addField($this->table, 'id');
            $query->condition('discovered', 1);
            $query->condition('id', array_keys($definitions), 'NOT IN');
            // Starting from links with the greatest depth will minimize the amount
            // of re-parenting done by the menu storage.
            $query->orderBy('depth', 'DESC');
            $result = $query->execute()
                ->fetchCol();
        }
        else {
            $result = [];
        }
        return $result;
    }
    
    /**
     * Purge menu links from the database.
     *
     * @param array $ids
     *   A list of menu link IDs to be purged.
     */
    protected function doDeleteMultiple(array $ids) {
        $this->connection
            ->delete($this->table, $this->options)
            ->condition('id', $ids, 'IN')
            ->execute();
    }

}