3 namespace Drupal\Core\Menu;
5 use Drupal\Component\Plugin\Exception\PluginException;
6 use Drupal\Component\Utility\UrlHelper;
7 use Drupal\Core\Cache\Cache;
8 use Drupal\Core\Cache\CacheBackendInterface;
9 use Drupal\Core\Cache\CacheTagsInvalidatorInterface;
10 use Drupal\Core\Database\Connection;
11 use Drupal\Core\Database\Database;
12 use Drupal\Core\Database\Query\SelectInterface;
13 use Drupal\Core\Database\SchemaObjectExistsException;
16 * Provides a menu tree storage using the database.
18 class MenuTreeStorage implements MenuTreeStorageInterface {
21 * The maximum depth of a menu links tree.
26 * The database connection.
28 * @var \Drupal\Core\Database\Connection
30 protected $connection;
33 * Cache backend instance for the extracted tree data.
35 * @var \Drupal\Core\Cache\CacheBackendInterface
37 protected $menuCacheBackend;
40 * The cache tags invalidator.
42 * @var \Drupal\Core\Cache\CacheTagsInvalidatorInterface
44 protected $cacheTagsInvalidator;
47 * The database table name.
54 * Additional database connection options to use in queries.
58 protected $options = [];
61 * Stores definitions that have already been loaded for better performance.
63 * An array of plugin definition arrays, keyed by plugin ID.
67 protected $definitions = [];
70 * List of serialized fields.
74 protected $serializedFields;
77 * List of plugin definition fields.
79 * @todo Decide how to keep these field definitions in sync.
80 * https://www.drupal.org/node/2302085
82 * @see \Drupal\Core\Menu\MenuLinkManager::$defaults
86 protected $definitionFields = [
106 * Constructs a new \Drupal\Core\Menu\MenuTreeStorage.
108 * @param \Drupal\Core\Database\Connection $connection
109 * A Database connection to use for reading and writing configuration data.
110 * @param \Drupal\Core\Cache\CacheBackendInterface $menu_cache_backend
111 * Cache backend instance for the extracted tree data.
112 * @param \Drupal\Core\Cache\CacheTagsInvalidatorInterface $cache_tags_invalidator
113 * The cache tags invalidator.
114 * @param string $table
115 * A database table name to store configuration data in.
116 * @param array $options
117 * (optional) Any additional database connection options to use in queries.
119 public function __construct(Connection $connection, CacheBackendInterface $menu_cache_backend, CacheTagsInvalidatorInterface $cache_tags_invalidator, $table, array $options = []) {
120 $this->connection = $connection;
121 $this->menuCacheBackend = $menu_cache_backend;
122 $this->cacheTagsInvalidator = $cache_tags_invalidator;
123 $this->table = $table;
124 $this->options = $options;
130 public function maxDepth() {
131 return static::MAX_DEPTH;
137 public function resetDefinitions() {
138 $this->definitions = [];
144 public function rebuild(array $definitions) {
148 // Fetch the list of existing menus, in case some are not longer populated
149 // after the rebuild.
150 $before_menus = $this->getMenuNames();
152 foreach ($definitions as $id => $link) {
153 // Flag this link as discovered, i.e. saved via rebuild().
154 $link['discovered'] = 1;
155 // Note: The parent we set here might be just stored in the {menu_tree}
156 // table, so it will not end up in $top_links. Therefore the later loop
157 // on the orphan links, will handle those cases.
158 if (!empty($link['parent'])) {
159 $children[$link['parent']][$id] = $id;
162 // A top level link - we need them to root our tree.
163 $top_links[$id] = $id;
164 $link['parent'] = '';
169 foreach ($top_links as $id) {
170 $this->saveRecursive($id, $children, $links);
172 // Handle any children we didn't find starting from top-level links.
173 foreach ($children as $orphan_links) {
174 foreach ($orphan_links as $id) {
175 // Check for a parent that is not loaded above since only internal links
177 $parent = $this->loadFull($links[$id]['parent']);
178 // If there is a parent add it to the links to be used in
179 // ::saveRecursive().
181 $links[$links[$id]['parent']] = $parent;
184 // Force it to the top level.
185 $links[$id]['parent'] = '';
187 $this->saveRecursive($id, $children, $links);
190 $result = $this->findNoLongerExistingLinks($definitions);
192 // Remove all such items.
194 $this->purgeMultiple($result);
196 $this->resetDefinitions();
197 $affected_menus = $this->getMenuNames() + $before_menus;
198 // Invalidate any cache tagged with any menu name.
199 $cache_tags = Cache::buildTags('config:system.menu', $affected_menus, '.');
200 $this->cacheTagsInvalidator->invalidateTags($cache_tags);
201 $this->resetDefinitions();
202 // Every item in the cache bin should have one of the menu cache tags but it
203 // is not guaranteed, so invalidate everything in the bin.
204 $this->menuCacheBackend->invalidateAll();
208 * Purges multiple menu links that no longer exist.
211 * An array of menu link IDs.
213 protected function purgeMultiple(array $ids) {
214 $loaded = $this->loadFullMultiple($ids);
215 foreach ($loaded as $id => $link) {
216 if ($link['has_children']) {
217 $children = $this->loadByProperties(['parent' => $id]);
218 foreach ($children as $child) {
219 $child['parent'] = $link['parent'];
224 $this->doDeleteMultiple($ids);
228 * Executes a select query while making sure the database table exists.
230 * @param \Drupal\Core\Database\Query\SelectInterface $query
231 * The select object to be executed.
233 * @return \Drupal\Core\Database\StatementInterface|null
234 * A prepared statement, or NULL if the query is not valid.
237 * Thrown if the table could not be created or the database connection
240 protected function safeExecuteSelect(SelectInterface $query) {
242 return $query->execute();
244 catch (\Exception $e) {
245 // If there was an exception, try to create the table.
246 if ($this->ensureTableExists()) {
247 return $query->execute();
249 // Some other failure that we can not recover from.
257 public function save(array $link) {
258 $affected_menus = $this->doSave($link);
259 $this->resetDefinitions();
260 $cache_tags = Cache::buildTags('config:system.menu', $affected_menus, '.');
261 $this->cacheTagsInvalidator->invalidateTags($cache_tags);
262 return $affected_menus;
266 * Saves a link without clearing caches.
269 * A definition, according to $definitionFields, for a
270 * \Drupal\Core\Menu\MenuLinkInterface plugin.
273 * The menu names affected by the save operation. This will be one menu
274 * name if the link is saved to the sane menu, or two if it is saved to a
278 * Thrown if the storage back-end does not exist and could not be created.
279 * @throws \Drupal\Component\Plugin\Exception\PluginException
280 * Thrown if the definition is invalid, for example, if the specified parent
281 * would cause the links children to be moved to greater than the maximum
284 protected function doSave(array $link) {
285 $affected_menus = [];
287 // Get the existing definition if it exists. This does not use
288 // self::loadFull() to avoid the unserialization of fields with 'serialize'
289 // equal to TRUE as defined in self::schemaDefinition(). The makes $original
290 // easier to compare with the return value of self::preSave().
291 $query = $this->connection->select($this->table, $this->options);
292 $query->fields($this->table);
293 $query->condition('id', $link['id']);
294 $original = $this->safeExecuteSelect($query)->fetchAssoc();
297 $link['mlid'] = $original['mlid'];
298 $link['has_children'] = $original['has_children'];
299 $affected_menus[$original['menu_name']] = $original['menu_name'];
300 $fields = $this->preSave($link, $original);
301 // If $link matches the $original data then exit early as there are no
302 // changes to make. Use array_diff_assoc() to check if they match because:
303 // - Some of the data types of the values are not the same. The values
304 // in $original are all strings because they have come from database but
305 // $fields contains typed values.
306 // - MenuTreeStorage::preSave() removes the 'mlid' from $fields.
307 // - The order of the keys in $original and $fields is different.
308 if (array_diff_assoc($fields, $original) == [] && array_diff_assoc($original, $fields) == ['mlid' => $link['mlid']]) {
309 return $affected_menus;
313 $transaction = $this->connection->startTransaction();
316 // Generate a new mlid.
317 $options = ['return' => Database::RETURN_INSERT_ID] + $this->options;
318 $link['mlid'] = $this->connection->insert($this->table, $options)
319 ->fields(['id' => $link['id'], 'menu_name' => $link['menu_name']])
321 $fields = $this->preSave($link, []);
323 // We may be moving the link to a new menu.
324 $affected_menus[$fields['menu_name']] = $fields['menu_name'];
325 $query = $this->connection->update($this->table, $this->options);
326 $query->condition('mlid', $link['mlid']);
327 $query->fields($fields)
330 $this->updateParentalStatus($original);
332 $this->updateParentalStatus($link);
334 catch (\Exception $e) {
335 $transaction->rollBack();
338 return $affected_menus;
342 * Fills in all the fields the database save needs, using the link definition.
345 * The link definition to be updated.
346 * @param array $original
347 * The link definition before the changes. May be empty if not found.
350 * The values which will be stored.
352 * @throws \Drupal\Component\Plugin\Exception\PluginException
353 * Thrown when the specific depth exceeds the maximum.
355 protected function preSave(array &$link, array $original) {
356 static $schema_fields, $schema_defaults;
357 if (empty($schema_fields)) {
358 $schema = static::schemaDefinition();
359 $schema_fields = $schema['fields'];
360 foreach ($schema_fields as $name => $spec) {
361 if (isset($spec['default'])) {
362 $schema_defaults[$name] = $spec['default'];
367 // Try to find a parent link. If found, assign it and derive its menu.
368 $parent = $this->findParent($link, $original);
370 $link['parent'] = $parent['id'];
371 $link['menu_name'] = $parent['menu_name'];
374 $link['parent'] = '';
377 // If no corresponding parent link was found, move the link to the
379 foreach ($schema_defaults as $name => $default) {
380 if (!isset($link[$name])) {
381 $link[$name] = $default;
384 $fields = array_intersect_key($link, $schema_fields);
385 // Sort the route parameters so that the query string will be the same.
386 asort($fields['route_parameters']);
387 // Since this will be urlencoded, it's safe to store and match against a
389 $fields['route_param_key'] = $fields['route_parameters'] ? UrlHelper::buildQuery($fields['route_parameters']) : '';
391 foreach ($this->serializedFields() as $name) {
392 if (isset($fields[$name])) {
393 $fields[$name] = serialize($fields[$name]);
396 $this->setParents($fields, $parent, $original);
398 // Need to check both parent and menu_name, since parent can be empty in any
400 if ($original && ($link['parent'] != $original['parent'] || $link['menu_name'] != $original['menu_name'])) {
401 $this->moveChildren($fields, $original);
403 // We needed the mlid above, but not in the update query.
404 unset($fields['mlid']);
406 // Cast Booleans to int, if needed.
407 $fields['enabled'] = (int) $fields['enabled'];
408 $fields['expanded'] = (int) $fields['expanded'];
415 public function delete($id) {
416 // Children get re-attached to the menu link's parent.
417 $item = $this->loadFull($id);
418 // It's possible the link is already deleted.
420 $parent = $item['parent'];
421 $children = $this->loadByProperties(['parent' => $id]);
422 foreach ($children as $child) {
423 $child['parent'] = $parent;
427 $this->doDeleteMultiple([$id]);
429 $this->updateParentalStatus($item);
430 // Many children may have moved.
431 $this->resetDefinitions();
432 $this->cacheTagsInvalidator->invalidateTags(['config:system.menu.' . $item['menu_name']]);
439 public function getSubtreeHeight($id) {
440 $original = $this->loadFull($id);
441 return $original ? $this->doFindChildrenRelativeDepth($original) + 1 : 0;
445 * Finds the relative depth of this link's deepest child.
447 * @param array $original
448 * The parent definition used to find the depth.
451 * Returns the relative depth.
453 protected function doFindChildrenRelativeDepth(array $original) {
454 $query = $this->connection->select($this->table, $this->options);
455 $query->addField($this->table, 'depth');
456 $query->condition('menu_name', $original['menu_name']);
457 $query->orderBy('depth', 'DESC');
460 for ($i = 1; $i <= static::MAX_DEPTH && $original["p$i"]; $i++) {
461 $query->condition("p$i", $original["p$i"]);
464 $max_depth = $this->safeExecuteSelect($query)->fetchField();
466 return ($max_depth > $original['depth']) ? $max_depth - $original['depth'] : 0;
470 * Sets the materialized path field values based on the parent.
472 * @param array $fields
474 * @param array|false $parent
475 * The parent menu link.
476 * @param array $original
477 * The original menu link.
479 protected function setParents(array &$fields, $parent, array $original) {
480 // Directly fill parents for top-level links.
481 if (empty($fields['parent'])) {
482 $fields['p1'] = $fields['mlid'];
483 for ($i = 2; $i <= $this->maxDepth(); $i++) {
486 $fields['depth'] = 1;
488 // Otherwise, ensure that this link's depth is not beyond the maximum depth
489 // and fill parents based on the parent link.
491 // @todo We want to also check $original['has_children'] here, but that
492 // will be 0 even if there are children if those are not enabled.
493 // has_children is really just the rendering hint. So, we either need
494 // to define another column (has_any_children), or do the extra query.
495 // https://www.drupal.org/node/2302149
497 $limit = $this->maxDepth() - $this->doFindChildrenRelativeDepth($original) - 1;
500 $limit = $this->maxDepth() - 1;
502 if ($parent['depth'] > $limit) {
503 throw new PluginException("The link with ID {$fields['id']} or its children exceeded the maximum depth of {$this->maxDepth()}");
505 $fields['depth'] = $parent['depth'] + 1;
507 while ($i < $fields['depth']) {
509 $fields[$p] = $parent[$p];
512 // The parent (p1 - p9) corresponding to the depth always equals the mlid.
513 $fields[$p] = $fields['mlid'];
514 while ($i <= static::MAX_DEPTH) {
522 * Re-parents a link's children when the link itself is moved.
524 * @param array $fields
525 * The changed menu link.
526 * @param array $original
527 * The original menu link.
529 protected function moveChildren($fields, $original) {
530 $query = $this->connection->update($this->table, $this->options);
532 $query->fields(['menu_name' => $fields['menu_name']]);
535 for ($i = 1; $i <= $fields['depth']; $i++) {
536 $expressions[] = ["p$i", ":p_$i", [":p_$i" => $fields["p$i"]]];
538 $j = $original['depth'] + 1;
539 while ($i <= $this->maxDepth() && $j <= $this->maxDepth()) {
540 $expressions[] = ['p' . $i++, 'p' . $j++, []];
542 while ($i <= $this->maxDepth()) {
543 $expressions[] = ['p' . $i++, 0, []];
546 $shift = $fields['depth'] - $original['depth'];
548 // The order of expressions must be reversed so the new values don't
549 // overwrite the old ones before they can be used because "Single-table
550 // UPDATE assignments are generally evaluated from left to right".
551 // @see http://dev.mysql.com/doc/refman/5.0/en/update.html
552 $expressions = array_reverse($expressions);
554 foreach ($expressions as $expression) {
555 $query->expression($expression[0], $expression[1], $expression[2]);
558 $query->expression('depth', 'depth + :depth', [':depth' => $shift]);
559 $query->condition('menu_name', $original['menu_name']);
561 for ($i = 1; $i <= $this->maxDepth() && $original["p$i"]; $i++) {
562 $query->condition("p$i", $original["p$i"]);
569 * Loads the parent definition if it exists.
572 * The link definition to find the parent of.
573 * @param array|false $original
574 * The original link that might be used to find the parent if the parent
575 * is not set on the $link, or FALSE if the original could not be loaded.
577 * @return array|false
578 * Returns a definition array, or FALSE if no parent was found.
580 protected function findParent($link, $original) {
583 // This item is explicitly top-level, skip the rest of the parenting.
584 if (isset($link['parent']) && empty($link['parent'])) {
588 // If we have a parent link ID, try to use that.
590 if (isset($link['parent'])) {
591 $candidates[] = $link['parent'];
593 elseif (!empty($original['parent']) && $link['menu_name'] == $original['menu_name']) {
594 // Otherwise, fall back to the original parent.
595 $candidates[] = $original['parent'];
598 foreach ($candidates as $id) {
599 $parent = $this->loadFull($id);
608 * Sets has_children for the link's parent if it has visible children.
611 * The link to get a parent ID from.
613 protected function updateParentalStatus(array $link) {
614 // If parent is empty, there is nothing to update.
615 if (!empty($link['parent'])) {
616 // Check if at least one visible child exists in the table.
617 $query = $this->connection->select($this->table, $this->options);
618 $query->addExpression('1');
621 ->condition('menu_name', $link['menu_name'])
622 ->condition('parent', $link['parent'])
623 ->condition('enabled', 1);
625 $parent_has_children = ((bool) $query->execute()->fetchField()) ? 1 : 0;
626 $this->connection->update($this->table, $this->options)
627 ->fields(['has_children' => $parent_has_children])
628 ->condition('id', $link['parent'])
634 * Prepares a link by unserializing values and saving the definition.
637 * The data loaded in the query.
638 * @param bool $intersect
639 * If TRUE, filter out values that are not part of the actual definition.
642 * The prepared link data.
644 protected function prepareLink(array $link, $intersect = FALSE) {
645 foreach ($this->serializedFields() as $name) {
646 if (isset($link[$name])) {
647 $link[$name] = unserialize($link[$name]);
651 $link = array_intersect_key($link, array_flip($this->definitionFields()));
653 $this->definitions[$link['id']] = $link;
660 public function loadByProperties(array $properties) {
661 $query = $this->connection->select($this->table, $this->options);
662 $query->fields($this->table, $this->definitionFields());
663 foreach ($properties as $name => $value) {
664 if (!in_array($name, $this->definitionFields(), TRUE)) {
665 $fields = implode(', ', $this->definitionFields());
666 throw new \InvalidArgumentException("An invalid property name, $name was specified. Allowed property names are: $fields.");
668 $query->condition($name, $value);
670 $loaded = $this->safeExecuteSelect($query)->fetchAllAssoc('id', \PDO::FETCH_ASSOC);
671 foreach ($loaded as $id => $link) {
672 $loaded[$id] = $this->prepareLink($link);
680 public function loadByRoute($route_name, array $route_parameters = [], $menu_name = NULL) {
681 // Sort the route parameters so that the query string will be the same.
682 asort($route_parameters);
683 // Since this will be urlencoded, it's safe to store and match against a
685 // @todo Standardize an efficient way to load by route name and parameters
686 // in place of system path. https://www.drupal.org/node/2302139
687 $param_key = $route_parameters ? UrlHelper::buildQuery($route_parameters) : '';
688 $query = $this->connection->select($this->table, $this->options);
689 $query->fields($this->table, $this->definitionFields());
690 $query->condition('route_name', $route_name);
691 $query->condition('route_param_key', $param_key);
693 $query->condition('menu_name', $menu_name);
695 // Make the ordering deterministic.
696 $query->orderBy('depth');
697 $query->orderBy('weight');
698 $query->orderBy('id');
699 $loaded = $this->safeExecuteSelect($query)->fetchAllAssoc('id', \PDO::FETCH_ASSOC);
700 foreach ($loaded as $id => $link) {
701 $loaded[$id] = $this->prepareLink($link);
709 public function loadMultiple(array $ids) {
710 $missing_ids = array_diff($ids, array_keys($this->definitions));
713 $query = $this->connection->select($this->table, $this->options);
714 $query->fields($this->table, $this->definitionFields());
715 $query->condition('id', $missing_ids, 'IN');
716 $loaded = $this->safeExecuteSelect($query)->fetchAllAssoc('id', \PDO::FETCH_ASSOC);
717 foreach ($loaded as $id => $link) {
718 $this->definitions[$id] = $this->prepareLink($link);
721 return array_intersect_key($this->definitions, array_flip($ids));
727 public function load($id) {
728 if (isset($this->definitions[$id])) {
729 return $this->definitions[$id];
731 $loaded = $this->loadMultiple([$id]);
732 return isset($loaded[$id]) ? $loaded[$id] : FALSE;
736 * Loads all table fields, not just those that are in the plugin definition.
742 * The loaded menu link definition or an empty array if not be found.
744 protected function loadFull($id) {
745 $loaded = $this->loadFullMultiple([$id]);
746 return isset($loaded[$id]) ? $loaded[$id] : [];
750 * Loads all table fields for multiple menu link definitions by ID.
756 * The loaded menu link definitions.
758 protected function loadFullMultiple(array $ids) {
759 $query = $this->connection->select($this->table, $this->options);
760 $query->fields($this->table);
761 $query->condition('id', $ids, 'IN');
762 $loaded = $this->safeExecuteSelect($query)->fetchAllAssoc('id', \PDO::FETCH_ASSOC);
763 foreach ($loaded as &$link) {
764 foreach ($this->serializedFields() as $name) {
765 if (isset($link[$name])) {
766 $link[$name] = unserialize($link[$name]);
776 public function getRootPathIds($id) {
777 $subquery = $this->connection->select($this->table, $this->options);
778 // @todo Consider making this dynamic based on static::MAX_DEPTH or from the
779 // schema if that is generated using static::MAX_DEPTH.
780 // https://www.drupal.org/node/2302043
781 $subquery->fields($this->table, ['p1', 'p2', 'p3', 'p4', 'p5', 'p6', 'p7', 'p8', 'p9']);
782 $subquery->condition('id', $id);
783 $result = current($subquery->execute()->fetchAll(\PDO::FETCH_ASSOC));
784 $ids = array_filter($result);
786 $query = $this->connection->select($this->table, $this->options);
787 $query->fields($this->table, ['id']);
788 $query->orderBy('depth', 'DESC');
789 $query->condition('mlid', $ids, 'IN');
790 // @todo Cache this result in memory if we find it is being used more
791 // than once per page load. https://www.drupal.org/node/2302185
792 return $this->safeExecuteSelect($query)->fetchAllKeyed(0, 0);
800 public function getExpanded($menu_name, array $parents) {
801 // @todo Go back to tracking in state or some other way which menus have
802 // expanded links? https://www.drupal.org/node/2302187
804 $query = $this->connection->select($this->table, $this->options);
805 $query->fields($this->table, ['id']);
806 $query->condition('menu_name', $menu_name);
807 $query->condition('expanded', 1);
808 $query->condition('has_children', 1);
809 $query->condition('enabled', 1);
810 $query->condition('parent', $parents, 'IN');
811 $query->condition('id', $parents, 'NOT IN');
812 $result = $this->safeExecuteSelect($query)->fetchAllKeyed(0, 0);
814 } while (!empty($result));
819 * Saves menu links recursively.
823 * @param array $children
824 * An array of IDs of child links collected by parent ID.
825 * @param array $links
826 * An array of all definitions keyed by ID.
828 protected function saveRecursive($id, &$children, &$links) {
829 if (!empty($links[$id]['parent']) && empty($links[$links[$id]['parent']])) {
830 // Invalid parent ID, so remove it.
831 $links[$id]['parent'] = '';
833 $this->doSave($links[$id]);
835 if (!empty($children[$id])) {
836 foreach ($children[$id] as $next_id) {
837 $this->saveRecursive($next_id, $children, $links);
840 // Remove processed link names so we can find stragglers.
841 unset($children[$id]);
847 public function loadTreeData($menu_name, MenuTreeParameters $parameters) {
848 // Build the cache ID; sort 'expanded' and 'conditions' to prevent duplicate
850 sort($parameters->expandedParents);
851 asort($parameters->conditions);
852 $tree_cid = "tree-data:$menu_name:" . serialize($parameters);
853 $cache = $this->menuCacheBackend->get($tree_cid);
854 if ($cache && isset($cache->data)) {
855 $data = $cache->data;
856 // Cache the definitions in memory so they don't need to be loaded again.
857 $this->definitions += $data['definitions'];
858 unset($data['definitions']);
861 $links = $this->loadLinks($menu_name, $parameters);
862 $data['tree'] = $this->doBuildTreeData($links, $parameters->activeTrail, $parameters->minDepth);
863 $data['definitions'] = [];
864 $data['route_names'] = $this->collectRoutesAndDefinitions($data['tree'], $data['definitions']);
865 $this->menuCacheBackend->set($tree_cid, $data, Cache::PERMANENT, ['config:system.menu.' . $menu_name]);
866 // The definitions were already added to $this->definitions in
867 // $this->doBuildTreeData()
868 unset($data['definitions']);
874 * Loads links in the given menu, according to the given tree parameters.
876 * @param string $menu_name
878 * @param \Drupal\Core\Menu\MenuTreeParameters $parameters
879 * The parameters to determine which menu links to be loaded into a tree.
880 * This method will set the absolute minimum depth, which is used in
881 * MenuTreeStorage::doBuildTreeData().
884 * A flat array of menu links that are part of the menu. Each array element
885 * is an associative array of information about the menu link, containing
886 * the fields from the {menu_tree} table. This array must be ordered
889 protected function loadLinks($menu_name, MenuTreeParameters $parameters) {
890 $query = $this->connection->select($this->table, $this->options);
891 $query->fields($this->table);
893 // Allow a custom root to be specified for loading a menu link tree. If
894 // omitted, the default root (i.e. the actual root, '') is used.
895 if ($parameters->root !== '') {
896 $root = $this->loadFull($parameters->root);
898 // If the custom root does not exist, we cannot load the links below it.
903 // When specifying a custom root, we only want to find links whose
904 // parent IDs match that of the root; that's how we ignore the rest of the
905 // tree. In other words: we exclude everything unreachable from the
907 for ($i = 1; $i <= $root['depth']; $i++) {
908 $query->condition("p$i", $root["p$i"]);
911 // When specifying a custom root, the menu is determined by that root.
912 $menu_name = $root['menu_name'];
914 // If the custom root exists, then we must rewrite some of our
915 // parameters; parameters are relative to the root (default or custom),
916 // but the queries require absolute numbers, so adjust correspondingly.
917 if (isset($parameters->minDepth)) {
918 $parameters->minDepth += $root['depth'];
921 $parameters->minDepth = $root['depth'];
923 if (isset($parameters->maxDepth)) {
924 $parameters->maxDepth += $root['depth'];
928 // If no minimum depth is specified, then set the actual minimum depth,
929 // depending on the root.
930 if (!isset($parameters->minDepth)) {
931 if ($parameters->root !== '' && $root) {
932 $parameters->minDepth = $root['depth'];
935 $parameters->minDepth = 1;
939 for ($i = 1; $i <= $this->maxDepth(); $i++) {
940 $query->orderBy('p' . $i, 'ASC');
943 $query->condition('menu_name', $menu_name);
945 if (!empty($parameters->expandedParents)) {
946 $query->condition('parent', $parameters->expandedParents, 'IN');
948 if (isset($parameters->minDepth) && $parameters->minDepth > 1) {
949 $query->condition('depth', $parameters->minDepth, '>=');
951 if (isset($parameters->maxDepth)) {
952 $query->condition('depth', $parameters->maxDepth, '<=');
954 // Add custom query conditions, if any were passed.
955 if (!empty($parameters->conditions)) {
956 // Only allow conditions that are testing definition fields.
957 $parameters->conditions = array_intersect_key($parameters->conditions, array_flip($this->definitionFields()));
958 $serialized_fields = $this->serializedFields();
959 foreach ($parameters->conditions as $column => $value) {
960 if (is_array($value)) {
961 $operator = $value[1];
967 if (in_array($column, $serialized_fields)) {
968 $value = serialize($value);
970 $query->condition($column, $value, $operator);
974 $links = $this->safeExecuteSelect($query)->fetchAllAssoc('id', \PDO::FETCH_ASSOC);
980 * Traverses the menu tree and collects all the route names and definitions.
983 * The menu tree you wish to operate on.
984 * @param array $definitions
985 * An array to accumulate definitions by reference.
988 * Array of route names, with all values being unique.
990 protected function collectRoutesAndDefinitions(array $tree, array &$definitions) {
991 return array_values($this->doCollectRoutesAndDefinitions($tree, $definitions));
995 * Collects all the route names and definitions.
998 * A menu link tree from MenuTreeStorage::doBuildTreeData()
999 * @param array $definitions
1000 * The collected definitions which are populated by reference.
1003 * The collected route names.
1005 protected function doCollectRoutesAndDefinitions(array $tree, array &$definitions) {
1007 foreach (array_keys($tree) as $id) {
1008 $definitions[$id] = $this->definitions[$id];
1009 if (!empty($definition['route_name'])) {
1010 $route_names[$definition['route_name']] = $definition['route_name'];
1012 if ($tree[$id]['subtree']) {
1013 $route_names += $this->doCollectRoutesAndDefinitions($tree[$id]['subtree'], $definitions);
1016 return $route_names;
1022 public function loadSubtreeData($id, $max_relative_depth = NULL) {
1024 $root = $this->loadFull($id);
1028 $parameters = new MenuTreeParameters();
1029 $parameters->setRoot($id)->onlyEnabledLinks();
1030 return $this->loadTreeData($root['menu_name'], $parameters);
1036 public function menuNameInUse($menu_name) {
1037 $query = $this->connection->select($this->table, $this->options);
1038 $query->addField($this->table, 'mlid');
1039 $query->condition('menu_name', $menu_name);
1040 $query->range(0, 1);
1041 return (bool) $this->safeExecuteSelect($query);
1047 public function getMenuNames() {
1048 $query = $this->connection->select($this->table, $this->options);
1049 $query->addField($this->table, 'menu_name');
1051 return $this->safeExecuteSelect($query)->fetchAllKeyed(0, 0);
1057 public function countMenuLinks($menu_name = NULL) {
1058 $query = $this->connection->select($this->table, $this->options);
1060 $query->condition('menu_name', $menu_name);
1062 return $this->safeExecuteSelect($query->countQuery())->fetchField();
1068 public function getAllChildIds($id) {
1069 $root = $this->loadFull($id);
1073 $query = $this->connection->select($this->table, $this->options);
1074 $query->fields($this->table, ['id']);
1075 $query->condition('menu_name', $root['menu_name']);
1076 for ($i = 1; $i <= $root['depth']; $i++) {
1077 $query->condition("p$i", $root["p$i"]);
1079 // The next p column should not be empty. This excludes the root link.
1080 $query->condition("p$i", 0, '>');
1081 return $this->safeExecuteSelect($query)->fetchAllKeyed(0, 0);
1087 public function loadAllChildren($id, $max_relative_depth = NULL) {
1088 $parameters = new MenuTreeParameters();
1089 $parameters->setRoot($id)->excludeRoot()->setMaxDepth($max_relative_depth)->onlyEnabledLinks();
1090 $links = $this->loadLinks(NULL, $parameters);
1091 foreach ($links as $id => $link) {
1092 $links[$id] = $this->prepareLink($link);
1098 * Prepares the data for calling $this->treeDataRecursive().
1100 protected function doBuildTreeData(array $links, array $parents = [], $depth = 1) {
1101 // Reverse the array so we can use the more efficient array_pop() function.
1102 $links = array_reverse($links);
1103 return $this->treeDataRecursive($links, $parents, $depth);
1107 * Builds the data representing a menu tree.
1109 * The function is a bit complex because the rendering of a link depends on
1110 * the next menu link.
1112 * @param array $links
1113 * A flat array of menu links that are part of the menu. Each array element
1114 * is an associative array of information about the menu link, containing
1115 * the fields from the $this->table. This array must be ordered
1116 * depth-first. MenuTreeStorage::loadTreeData() includes a sample query.
1117 * @param array $parents
1118 * An array of the menu link ID values that are in the path from the current
1119 * page to the root of the menu tree.
1121 * The minimum depth to include in the returned menu tree.
1124 * The fully built tree.
1126 * @see \Drupal\Core\Menu\MenuTreeStorage::loadTreeData()
1128 protected function treeDataRecursive(array &$links, array $parents, $depth) {
1130 while ($tree_link_definition = array_pop($links)) {
1131 $tree[$tree_link_definition['id']] = [
1132 'definition' => $this->prepareLink($tree_link_definition, TRUE),
1133 'has_children' => $tree_link_definition['has_children'],
1134 // We need to determine if we're on the path to root so we can later
1135 // build the correct active trail.
1136 'in_active_trail' => in_array($tree_link_definition['id'], $parents),
1138 'depth' => $tree_link_definition['depth'],
1140 // Look ahead to the next link, but leave it on the array so it's
1141 // available to other recursive function calls if we return or build a
1143 $next = end($links);
1144 // Check whether the next link is the first in a new sub-tree.
1145 if ($next && $next['depth'] > $depth) {
1146 // Recursively call doBuildTreeData to build the sub-tree.
1147 $tree[$tree_link_definition['id']]['subtree'] = $this->treeDataRecursive($links, $parents, $next['depth']);
1148 // Fetch next link after filling the sub-tree.
1149 $next = end($links);
1151 // Determine if we should exit the loop and return.
1152 if (!$next || $next['depth'] < $depth) {
1160 * Checks if the tree table exists and create it if not.
1163 * TRUE if the table was created, FALSE otherwise.
1165 * @throws \Drupal\Component\Plugin\Exception\PluginException
1166 * If a database error occurs.
1168 protected function ensureTableExists() {
1170 if (!$this->connection->schema()->tableExists($this->table)) {
1171 $this->connection->schema()->createTable($this->table, static::schemaDefinition());
1175 catch (SchemaObjectExistsException $e) {
1176 // If another process has already created the config table, attempting to
1177 // recreate it will throw an exception. In this case just catch the
1178 // exception and do nothing.
1181 catch (\Exception $e) {
1182 throw new PluginException($e->getMessage(), NULL, $e);
1188 * Determines serialized fields in the storage.
1191 * A list of fields that are serialized in the database.
1193 protected function serializedFields() {
1194 if (empty($this->serializedFields)) {
1195 $schema = static::schemaDefinition();
1196 foreach ($schema['fields'] as $name => $field) {
1197 if (!empty($field['serialize'])) {
1198 $this->serializedFields[] = $name;
1202 return $this->serializedFields;
1206 * Determines fields that are part of the plugin definition.
1209 * The list of the subset of fields that are part of the plugin definition.
1211 protected function definitionFields() {
1212 return $this->definitionFields;
1216 * Defines the schema for the tree table.
1219 * The schema API definition for the SQL storage table.
1221 protected static function schemaDefinition() {
1223 'description' => 'Contains the menu tree hierarchy.',
1226 'description' => "The menu name. All links with the same menu name (such as 'tools') are part of the same menu.",
1227 'type' => 'varchar_ascii',
1233 'description' => 'The menu link ID (mlid) is the integer primary key.',
1239 'description' => 'Unique machine name: the plugin ID.',
1240 'type' => 'varchar_ascii',
1245 'description' => 'The plugin ID for the parent of this link.',
1246 'type' => 'varchar_ascii',
1252 'description' => 'The machine name of a defined Symfony Route this menu item represents.',
1253 'type' => 'varchar_ascii',
1256 'route_param_key' => [
1257 'description' => 'An encoded string of route parameters for loading by route.',
1258 'type' => 'varchar',
1261 'route_parameters' => [
1262 'description' => 'Serialized array of route parameters of this menu link.',
1265 'not null' => FALSE,
1266 'serialize' => TRUE,
1269 'description' => 'The external path this link points to (when not using a route).',
1270 'type' => 'varchar',
1276 'description' => 'The serialized title for the link. May be a TranslatableMarkup.',
1279 'not null' => FALSE,
1280 'serialize' => TRUE,
1283 'description' => 'The serialized description of this link - used for admin pages and title attribute. May be a TranslatableMarkup.',
1286 'not null' => FALSE,
1287 'serialize' => TRUE,
1290 'description' => 'The class for this link plugin.',
1292 'not null' => FALSE,
1295 'description' => 'A serialized array of URL options, such as a query string or HTML attributes.',
1298 'not null' => FALSE,
1299 'serialize' => TRUE,
1302 'description' => 'The name of the module that generated this link.',
1303 'type' => 'varchar_ascii',
1304 'length' => DRUPAL_EXTENSION_NAME_MAX_LENGTH,
1306 'default' => 'system',
1309 'description' => 'A flag for whether the link should be rendered in menus. (0 = a disabled menu item that may be shown on admin screens, 1 = a normal, visible link)',
1316 'description' => 'A flag for whether the link was discovered, so can be purged on rebuild',
1323 '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)',
1330 'description' => 'Link weight among links in the same menu at the same depth.',
1336 'description' => 'A serialized array of data that may be used by the plugin instance.',
1339 'not null' => FALSE,
1340 'serialize' => TRUE,
1343 'description' => 'Flag indicating whether any enabled links have this link as a parent (1 = enabled children exist, 0 = no enabled children).',
1350 'description' => 'The depth relative to the top level. A link with empty parent will have depth == 1.',
1357 '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.',
1364 'description' => 'The second mlid in the materialized path. See p1.',
1371 'description' => 'The third mlid in the materialized path. See p1.',
1378 'description' => 'The fourth mlid in the materialized path. See p1.',
1385 'description' => 'The fifth mlid in the materialized path. See p1.',
1392 'description' => 'The sixth mlid in the materialized path. See p1.',
1399 'description' => 'The seventh mlid in the materialized path. See p1.',
1406 'description' => 'The eighth mlid in the materialized path. See p1.',
1413 'description' => 'The ninth mlid in the materialized path. See p1.',
1420 'description' => 'meh',
1421 'type' => 'varchar',
1438 // @todo Test this index for effectiveness.
1439 // https://www.drupal.org/node/2302197
1440 'menu_parent_expand_child' => [
1441 'menu_name', 'expanded',
1447 ['route_param_key', 16],
1450 'primary key' => ['mlid'],
1460 * Find any previously discovered menu links that no longer exist.
1462 * @param array $definitions
1463 * The new menu link definitions.
1465 * A list of menu link IDs that no longer exist.
1467 protected function findNoLongerExistingLinks(array $definitions) {
1469 $query = $this->connection->select($this->table, NULL, $this->options);
1470 $query->addField($this->table, 'id');
1471 $query->condition('discovered', 1);
1472 $query->condition('id', array_keys($definitions), 'NOT IN');
1473 // Starting from links with the greatest depth will minimize the amount
1474 // of re-parenting done by the menu storage.
1475 $query->orderBy('depth', 'DESC');
1476 $result = $query->execute()->fetchCol();
1485 * Purge menu links from the database.
1488 * A list of menu link IDs to be purged.
1490 protected function doDeleteMultiple(array $ids) {
1491 $this->connection->delete($this->table, $this->options)
1492 ->condition('id', $ids, 'IN')