Trees (nested set)#

How the model layer keeps tree data: categories, regions, menu items, pages, discussion posts. This chapter is for anyone creating a new tree entity, writing a form that changes the parent, or looking into why a move returned an error. How a tree looks in the administration is described in DataGrid.

How a tree is built and changed#

A row carries parent_id and the bounds lft/rgt/level. Nobody writes the bounds by hand: they are computed by set-based SQL in Repositories\TreeTrait, with three thin layers on top (service → mapper → repository). The mapper turns the property names from TreeConfig (lft, rgt, parentId, level and the scope) into columns using Doctrine metadata. An unknown property is an error; a name from the request never reaches the SQL.

Operation	Manager method	What it does
insert	`save()` itself	after the flush it calls `insertTreeNode()` inside the `save()` transaction: the node goes after the last sibling, without siblings right after the parent's `lft`, a root after the last root; `level` = parent + 1, root 1
move among siblings	`moveUp()` / `moveDown()`	swaps the node with its neighbour, both subtrees included; without a neighbour `TREE_NO_SIBLING`
new parent	`moveSubtree($id, $parentId)`	the whole subtree under the new parent as its last child (`null` = root level)
new parent and position	`moveSubtreeTo($id, $parentId, $afterId, …, $expectation)`	`$afterId`: `-1` = first child, `0` = last, `>0` = after the sibling with this id
reorder children	`reorderChildren($parentId, $orderedIds)`	one `UPDATE` inside the parent's interval; `data.changed` = number of children that moved
delete	`deleteNode($id)`	deletes the whole subtree and closes the gap in the bounds

Several trees in one table#

Menu items share a table, but each menu has its own numbering from 1. They are told apart by the scope: the entity implements ScopedTreeNodeInterface and getTreeScope() returns the properties that delimit the tree (MenuItem: ['menuId' => $this->menuId]). The manager takes the scope by itself (treeConfigForEntity()), also when saving from the administration, where the admin variant of the entity is persisted. A table with a single tree (pages, blog categories) does not implement the interface and runs with an empty scope.

The scope goes into the WHERE of every query (null-safe <=>) and into the lock name.

The scope belongs on the entity, not in an overridden manager method

Without the scope the renumbering spills into foreign trees of the same table. It shows up as a scrambled order in another menu, not as an error.

Changing the parent from a form#

A form does not call the move itself. It sends the new parent in $meta and the manager performs the move in afterSave(), that is in the same transaction as the parent_id save:

protected function afterSave(bool $isInsert, MenuItem &$entity, ?Result $result = null, array &$meta = []): ?Result
{
    if ($result === null || !$result->isSuccess()) {
        return null;
    }

    return $this->applyMetaSubtreeMove($isInsert, $entity, $entity->getId(), $meta);
}

Key in `$meta`	Meaning
`TreeTrait::META_MOVE_SUBTREE_PARENT` (`moveSubtreeToParentId`)	new parent; `null` or `0` = root. Without the key nothing is moved
`TreeMovePlan::META_AFTER_ID` (`moveSubtreeAfterId`)	position among siblings; without it the node goes last
`TreeMovePlan::META_NEIGHBOURS` (`moveSubtreeNeighbours`)	the `prevId`/`nextId` neighbours as the form rendered them; on mismatch `TREE_STALE`

On insert nothing is moved: a new node gets its bounds already in save().

A move as a separate step after save() breaks the tree

If the move fails after a successful save, the database keeps the new parent_id with unrecomputed lft/rgt, and the tree cannot be repaired from the administration. From afterSave() the failure comes back as a Result and SaveTrait also rolls back the parent_id.

A manager whose derived data depend on the path in the tree (regions and their addresses) overrides afterMoveSubtree($id, $result). It runs inside the transaction and under the move lock, so its failure also rolls back the move. Reordering children does not change the path and does not call it.

Region slugs#

A region href is the path of its parents in the same language. The rule is computed only by App\UI\Api\System\Models\Helpers\RegionHrefBuilder (no I/O) and written by RegionManager::rebuildSubtreeHrefs():

Node	Href
country (`type = country`) and root	manual, empty = the name slug; descendants inherit it
district	`href(region)-okres-slug(name without "Okres ")` → `cr-stredocesky-kraj-okres-nymburk`
municipality, region, untyped node	`href(parent)-slug(name)` → `…-okres-nymburk-nymburk` (repetition is not skipped)
collision within a language	suffix `-{official_code}`, otherwise `-{region_id}`; the bare href stays with the node closest to the root, a tie on the same level = a suffix for all

After a region is saved its subtree is regenerated (a changed name, a changed manual country href, a new node); on a move afterMoveSubtree() does it. Both run in the same transaction, so a failure rolls back the save too. The result does not depend on order: regenerating one municipality gives the same as regenerating the whole country.

Procedure: regenerating slugs in bulk (import, a changed country abbreviation)

php bin/regions-rebuild-hrefs.php --region=<id> — a dry run, lists the changes and writes nothing.
Set the country abbreviation with --href=<region>:<language>=<href> (only on a country or root).
Run again with --apply; each --region runs in its own transaction and the region cache tags are bumped after the commit.
A second run must change nothing.

Old addresses are not redirected

A changed href changes the URLs of region filters and listings. Indexed and shared links then lead to an unknown slug. Do not change hrefs in bulk on a live site without redirects.

cms_system_regions are not payment regions

The script and the rule work only with the geographic tree; cms_system_payment_regions is not touched.

Procedure: node position in an admin form#

Do not hand-write the "where under the parent" choice and the $meta building. The TreePosition component shares it with the grid's "Move to…" modal, and TreePositionHostTrait brings it into the presenter (10 presenters have it today: pages, menus, regions, the categories of Blog, Bazaar, Comcat, Company, Discussion and the e-shop, and discussion posts; counted by grep -l TreePositionHostTrait app/UI/Admin/*/Presenters/*.php).

In the presenter, use TreePositionHostTrait; and implement treePositionConfig() (manager, label, edited node, scope). The method must be pure, the AJAX signal siblings! calls it too.
In the form, call $this->addTreePositionFields($form) next to the hidden parentId.
When saving an existing node, take $meta from $this->buildTreeMoveMeta($values, $id, $originalParent, $newParent). null means an invalid choice (the flash is already set), return false; [] means nothing moves.
On a failed save(), call $this->flashTreeMoveFailure($result, $meta). It returns true when it printed the message of a tree reason (TREE_STALE, TREE_LOCKED, invalid target, corrupted node); on false set your own generic message.
Put {control treePosition} into the template under the parent picker. It is not rendered for a new node.

Without a choice ("keep the current place") a parent change appends the node as the last child.

Concurrency: tree lock and locking reads#

Every write operation runs under an advisory tree lock (GET_LOCK, name from the table and the scope) and reads the bounds with FOR UPDATE. Both are needed:

Safeguard	Against what
tree lock	a second operation on the same tree waits and after 10 s gets `TREE_LOCKED` instead of a deadlock
`FOR UPDATE`	an operation nested in an older transaction (`save()` → `insertTreeNode()`) would otherwise compute from the transaction snapshot, that is from stale bounds

The manager wraps a standalone operation in the lock and a transaction and releases the lock only after the commit. When a transaction is already running (a move from afterSave()), it opens none and only returns the result: the caller commits or rolls back, and the user gets the concrete reason, not a generic "save failed".

The lock is re-entrant per connection (MariaDB keeps GET_LOCK with a counter), so a nested call (manager → repository, delete → gap closing) only pairs acquire and release. The lock name normalizes the scope, so ['menu_id' => 5] and ['menu_id' => '5'] from HTTP lock the same tree.

Results a tree operation returns#

Code	When
`TREE_LOCKED`	another operation has held the tree lock for more than 10 s; nothing started
`TREE_STALE`	the client saw a different state: the old parent, the neighbours or the set of children do not match; nothing was written
`TREE_NODE_CORRUPTED`	the node has `rgt <= lft` (typically `0/0`, its bounds were never computed) or the children do not fill the parent's interval contiguously
`TREE_NO_SIBLING`	`moveUp()`/`moveDown()` at the edge
`INVALID_ARGUMENT`	`afterId` does not match `prevId` in the move expectation

A corrupted node is not repaired by shifting

An operation on a node with zero or negative width fails on purpose. If it "repaired" the node, it would shift the intervals of foreign nodes and break the whole tree.

Rebuilding the page tree from `parent_id`#

The page tree can be recomputed as a whole: the manual job /cron/system/page-tree/rebuild (PageManager::rebuildTree() → PageRepository::rebuildTree()). Under the page tree lock (the same GET_LOCK as move, insert and delete) it loads page_id and parent_id of all pages, walks them depth-first in PHP (a nested set cannot be computed by one set-based UPDATE) and writes the new lft, rgt and level in one transaction. It returns pages (the count), orphans (top pages of subtrees whose parent does not exist) and cycles (pages in or under a parent_id cycle). Both are placed as roots and parent_id stays. After a success it bumps the Page tag version, so menus, routing and breadcrumbs refresh. Repeated runs give the same result. When another operation holds the tree, the job ends with 409 (TREE_LOCKED) and writes nothing.

The rebuild discards the manual order of siblings

Siblings are ordered by page_id ascending. Pages reordered by tree operations (moving among siblings, drag and drop) return to the order they were created in. Run it only after a bulk change of parent_id outside tree operations, not as routine maintenance.

The rebuild works around a cycle in parent_id but does not fix it

The walk remembers visited pages, so a cycle cannot loop it. Pages in the cycle are placed as roots, returned in cycles and logged as a warning to warning.log. parent_id is not changed: fix the parents by hand and run the job again.

Procedure: adding a tree entity#

Entity implements TreeNodeInterface (getParentId(), getLft(), getRgt(), getLevel()). Several trees in a table: ScopedTreeNodeInterface with getTreeScope().
Repository gets Repositories\TreeTrait.
Mapper gets Mappers\TreeTrait and implements TreeMapperInterface.
Service gets Services\TreeTrait and implements TreeServiceInterface.
Manager gets Managers\TreeTrait. If a form changes the parent, call applyMetaSubtreeMove() in afterSave().
Verify the insert (the new node has non-zero lft/rgt), a move under another parent and deleting a node with children.

A missing trait on one layer fails the save

Tree traits are not inherited from the base classes. An entity with TreeNodeInterface without insertTreeNode() on the service throws a LogicException and save() is rolled back. This is on purpose: otherwise the node would silently stay with lft = rgt = 0 and the tree would break only at the first move.

Delete and move run neither hooks nor the usual cache invalidation

deleteNode() deletes through deleteAll(), so afterDelete() does not run (see Manager lifecycle). The manager releases the subtree images itself if it declares ownedAssetIds(). The cache invalidates the class tag after the commit; return a tag that does not depend on the entity from classCacheTags(), see Cache.

Where to look#

I want	Where
public operations, transaction and lock	`app/Core/Traits/Api/Models/Managers/TreeTrait.php`
bound computation in SQL, lock, result codes	`app/Core/Traits/Api/Models/Repositories/TreeTrait.php`
property to column mapping	`app/Core/Traits/Api/Models/Mappers/TreeTrait.php`
subtree deletion	`app/Core/Traits/Api/Models/Services/TreeTrait.php`
property names and scope	`app/Core/Utils/ValueObjects/TreeConfig.php`
position and neighbours from a form	`app/Core/Utils/ValueObjects/TreeMovePlan.php`, `TreeMoveExpectation.php`
a tree with scope	`app/Core/Base/Shared/System/Models/Entities/MenuItem.php`, `app/UI/Api/System/Models/Managers/MenuItemManager.php`
lock concurrency and re-entrance test	`tests/Manual/System/tree_move_subtree_harness.php`

Related chapters: DataGrid · Picker · Manager lifecycle · Cache

Cookie settings