CoolCMS API

TreeTrait

Nested-set operations on a tree (raw set-based SQL). The mapper resolves properties to columns and passes ready names plus the scope (column => value).

The scope is added to the WHERE of every query (null-safe <=>), so a move touches only the selected tree. Several trees in one table (for example menu_id) share lft/rgt numbering from 1, and without the scope the renumbering would spill into foreign trees.

IMPORTANT: every write operation runs under an advisory tree lock (inTreeLock(), GET_LOCK per table plus scope) and reads bounds with a locking read (FOR UPDATE). Both are required:

the lock serializes writes into one tree and gives the second operation a clean TREE_LOCKED instead of waiting on row locks or a deadlock,
FOR UPDATE reads the latest committed state, not the transaction snapshot (repeatable read). Without it an operation nested in an earlier transaction (save() -> insertTreeNode(), snapshot taken when the entity was loaded) would compute shifts from stale bounds even under the lock. It also covers the window between releasing the lock and the outer commit: the next operation waits on row locks until the outer transaction ends.

Properties

$treeLockTimeout : int: Timeout of `GET_LOCK` in seconds. A move on about 10 000 nodes takes tens of ms, so 10 s covers a queue of several operations; beyond it the result is `TREE_LOCKED`.

Methods

buildTreeLockName() : string: Returns the advisory tree lock name: `tree:<table truncated to 26 chars>:<md5(table + scope)>`.
closeTreeGap() : Result: Closes the numbering gap after a deleted subtree: all bounds after the right bound of the deleted node shift left by its width. Ancestors (lft before the gap) only lose `rgt`, nodes after the gap lose both bounds.
computeChildrenReorder() : Result: Computes the bound shifts of child subtrees for a new order; a pure function ({@see reorderTreeChildren()}) testable without a database ({@see \Tests\Unit\Api\TreeReorderChildrenTest}).
degenerateTreeNodeResult() : Result|null: Guard contract for a degenerate node: a valid nested-set node has width `W = rgt - lft + 1 >= 2` (leaf = `lft`, `rgt = lft + 1`). Anything smaller (typically `lft = rgt = 0` on a node whose bounds were never computed) is a corrupted node, and a tree operation on it must fail, not "repair" the tree by shifting foreign intervals.
getTreeSubtree() : Result: Loads the subtree of a node for deletion: ids of all nodes (including the subtree root) plus the `lft`/`rgt` bounds for closing the gap afterwards ({@see closeTreeGap()}).
insertTreeNode() : Result: Computes `lft`/`rgt`/`level` of a newly inserted node (after `save()`, when the DB already has its `parent_id` but `lft`/`rgt` are zero). It is inserted as the last sibling:
inTreeLock() : Result: Runs the operation under the advisory tree lock (table plus scope) and releases it in `finally`.
moveSubtree() : Result: Moves the subtree of a node under another parent. Processes the whole subtree (not only the root), updating `lft`/`rgt`/`level` of every subtree node and `parent_id` of the root.
moveTreeNode() : Result: Swaps a node with its adjacent sibling (move up/down). Shifts the whole subtrees of both siblings; each node keeps its width `rgt - lft`.
reorderTreeChildren() : Result: Reorders the direct children of a parent into the given order (whole subtrees) in one operation under the tree lock with one UPDATE limited to the parent interval.
setTreeLockTimeout() : void: Changes the tree lock timeout; for concurrency tests and the CLI, not for normal operation.
buildScopeCondition() : array{0: string, 1: array}: Turns the scope filter into an SQL fragment (`AND col <=> :scope_col`) plus parameters.
checkMoveExpectation() : Result|null: Verifies the move contract against the current tree state; called under the lock with locking reads, so the verified state is the state the write is computed from.
closeTreeGapUnderLock() : Result
fetchExpectedSiblingLft() : int|null: Returns `lft` of the expected sibling if it is a child of `$parentId` today; otherwise `null` (deleted, moved under another parent, outside the scope).
fetchNodeLevel() : int: Returns the level of a node by id (helper for {@see insertTreeNode()}).
insertTreeNodeUnderLock() : Result
moveSubtreeUnderLock() : Result
moveTreeNodeUnderLock() : Result
quoteIdentifier() : string
releaseTreeLock() : void: Releases one level of the tree lock. A failure is only logged: a failed release must not overwrite the operation result; the connection lock disappears with the connection anyway.
reorderTreeChildrenUnderLock() : Result
siblingWindow() : array{0: string, 1: array}|Result: Returns the SQL window between the expected neighbors (`lft` of the previous and the next one), or `TREE_STALE` when they do not follow each other. `null` means no neighbor on that side (start/end of the parent).

$treeLockTimeout

Timeout of `GET_LOCK` in seconds. A move on about 10 000 nodes takes tens of ms, so 10 s covers a queue of several operations; beyond it the result is `TREE_LOCKED`.


        private
            int
    $treeLockTimeout
     = 10

buildTreeLockName()

Returns the advisory tree lock name: `tree:<table truncated to 26 chars>:<md5(table + scope)>`.


    public
            static        buildTreeLockName(string $table, array<string, scalar|null> $scope) : string

The hash also carries the whole table name, so truncating the readable part (the lock name limit is 64 chars) cannot merge two trees. The scope is normalized (key order, values as strings) so that ['menu_id' => 5] and ['menu_id' => '5'] from an HTTP payload lock the same tree.

Parameters

$table : string
$scope : array<string, scalar|null>

Return values

string

closeTreeGap()

Closes the numbering gap after a deleted subtree: all bounds after the right bound of the deleted node shift left by its width. Ancestors (lft before the gap) only lose `rgt`, nodes after the gap lose both bounds.


    public
                    closeTreeGap(string $table, array{left: string, right: string} $columns, int $lft, int $rgt[, array<string, scalar|null> $scope = [] ]) : Result

Parameters

$table : string: table name
$columns : array{left: string, right: string}: column names
$lft : int: left bound of the deleted subtree
$rgt : int: right bound of the deleted subtree
$scope : array<string, scalar|null> = []: column => value (scope filter)

Return values

Result

computeChildrenReorder()

Computes the bound shifts of child subtrees for a new order; a pure function ({@see reorderTreeChildren()}) testable without a database ({@see \Tests\Unit\Api\TreeReorderChildrenTest}).


    public
            static        computeChildrenReorder(array<int, array{id: int, lft: int, rgt: int}> $children, array<int, int> $orderedIds, int $firstLft) : Result

The children must fill the interval contiguously (first.lft = $firstLft, each next one starts after the previous). A child's new place is $firstLft plus the sum of widths of the children placed before it in the new order; the shift of its whole subtree is new lft minus old lft.

Parameters

$children : array<int, array{id: int, lft: int, rgt: int}>: children in the current lft order
$orderedIds : array<int, int>: child ids in the new order
$firstLft : int

Return values

Result —

data: array{shifts: array<int, array{lft: int, rgt: int, shift: int}>} only children with a non-zero shift; TREE_STALE = the id set does not match, TREE_NODE_CORRUPTED = children are not contiguous or degenerate

degenerateTreeNodeResult()

Guard contract for a degenerate node: a valid nested-set node has width `W = rgt - lft + 1 >= 2` (leaf = `lft`, `rgt = lft + 1`). Anything smaller (typically `lft = rgt = 0` on a node whose bounds were never computed) is a corrupted node, and a tree operation on it must fail, not "repair" the tree by shifting foreign intervals.


    public
            static        degenerateTreeNodeResult(int $id, int $lft, int $rgt) : Result|null

Returns null when the node is fine; otherwise a failed Result (ResultCode::TREE_NODE_CORRUPTED, messages in the results domain).

A pure function without a database, testable from the contract (TreeDegenerateNodeGuardTest).

Parameters

$id : int
$lft : int
$rgt : int

Return values

Result|null

getTreeSubtree()

Loads the subtree of a node for deletion: ids of all nodes (including the subtree root) plus the `lft`/`rgt` bounds for closing the gap afterwards ({@see closeTreeGap()}).


    public
                    getTreeSubtree(string $table, array{id: string, left: string, right: string} $columns, int $id[, array<string, scalar|null> $scope = [] ]) : Result

Ids are ordered by rgt ascending: a descendant always has a smaller rgt than its ancestor, so deleting in this order goes from the leaves and does not violate a self-reference FK (parent_id).

IMPORTANT: it takes no lock itself. The bounds must stay valid until closeTreeGap(), so the whole delete is locked by the service (TreeTrait::deleteTreeNode()). The read is locking so that the bounds do not come from a stale transaction snapshot.

Parameters

$table : string: table name
$columns : array{id: string, left: string, right: string}: column names
$id : int
$scope : array<string, scalar|null> = []: column => value (scope filter)

Return values

Result —

data: array{ids: int[], lft: int, rgt: int}

insertTreeNode()

Computes `lft`/`rgt`/`level` of a newly inserted node (after `save()`, when the DB already has its `parent_id` but `lft`/`rgt` are zero). It is inserted as the last sibling:


    public
                    insertTreeNode(string $table, array{id: string, left: string, right: string, parent: string, level: string} $columns, int $id[, array<string, scalar|null> $scope = [] ]) : Result

find the largest rgt among siblings (same parent_id) and place the node right after it: lft = maxRgt + 1, rgt = maxRgt + 2,
without siblings: under a parent right after its lft (first child), at the root after the last root (max rgt of the whole scope tree),
before placing, open a gap of width 2 in the numbering (everything with lft/rgt

= the new lft shifts by 2) to keep the nested set contiguous,
level = parent level + 1 (root = 1).

Parameters

$table : string: table name
$columns : array{id: string, left: string, right: string, parent: string, level: string}: column names
$id : int
$scope : array<string, scalar|null> = []: column => value (scope filter)

Return values

Result

inTreeLock()

Runs the operation under the advisory tree lock (table plus scope) and releases it in `finally`.


    public
                    inTreeLock(string $table, array<string, scalar|null> $scope, callable(): Result $operation) : Result

Re-entrance: MariaDB (since 10.0.2) holds GET_LOCK recursively with a per-connection counter, so a repeated GET_LOCK of the same name on the same connection returns 1 immediately, and another connection gets the lock only after the same number of RELEASE_LOCK calls (checked by tests/Manual/System/tree_move_subtree_harness.php). A nested call (manager -> repository, service deleteTreeNode() -> closeTreeGap()) therefore needs no PHP counter, acquire and release only have to be paired strictly. A PHP counter would add state outside the connection (after a reconnect it would "hold" a lock the server already dropped).

A nested operation releases its level at its own end even while the outer transaction still runs (typically save() -> insertTreeNode()). Consistency until the commit is held by the locking read (see the trait docblock); standalone manager operations hold the lock across the commit (TreeTrait::treeTransaction()).

Parameters

$table : string
$scope : array<string, scalar|null>: column => value
$operation : callable(): Result

Return values

Result

moveSubtree()

Moves the subtree of a node under another parent. Processes the whole subtree (not only the root), updating `lft`/`rgt`/`level` of every subtree node and `parent_id` of the root.


    public
                    moveSubtree(string $table, array{id: string, left: string, right: string, parent: string, level: string} $columns, int $id, int|null $newParentId[, array<string, scalar|null> $scope = [] ][, int|null $afterSiblingId = null ][, TreeMoveExpectation|null $expectation = null ]) : Result

Algorithm (temporary offset):

extract the subtree (lft/rgt += BIG),
close the gap at the original position,
open space at the new parent,
place the subtree (shift back + level diff).

Must run in a transaction (held by the manager).

With $expectation the repository verifies under the lock, before the first write, that the node is still under the expected parent and that prev/next are today's neighbors under newParentId; on mismatch it returns TREE_STALE and writes nothing. Without it the move runs unchecked.

Parameters

$table : string: table name
$columns : array{id: string, left: string, right: string, parent: string, level: string}: column names
$id : int
$newParentId : int|null: null moves to the root level (after the other roots)
$scope : array<string, scalar|null> = []: column => value
$afterSiblingId : int|null = null: null = as last child, 0 = as first child, >0 = after that sibling
$expectation : TreeMoveExpectation|null = null

Return values

Result

moveTreeNode()

Swaps a node with its adjacent sibling (move up/down). Shifts the whole subtrees of both siblings; each node keeps its width `rgt - lft`.


    public
                    moveTreeNode(string $table, array{id: string, left: string, right: string, parent: string} $columns, int $id, int $direction[, array<string, scalar|null> $scope = [] ]) : Result

Parameters

$table : string: table name
$columns : array{id: string, left: string, right: string, parent: string}: column names
$id : int
$direction : int: -1 = up (before the previous sibling), +1 = down
$scope : array<string, scalar|null> = []: column => value (scope filter)

Return values

Result

reorderTreeChildren()

Reorders the direct children of a parent into the given order (whole subtrees) in one operation under the tree lock with one UPDATE limited to the parent interval.


    public
                    reorderTreeChildren(string $table, array{id: string, left: string, right: string, parent: string} $columns, int|null $parentId, array<int, int> $orderedIds[, array<string, scalar|null> $scope = [] ]) : Result

The parent width does not change (children only swap places), so ancestors, siblings of the parent and the rest of the tree are untouched; level and parent_id do not change either. It replaces N calls of moveSubtree() (for 200 municipalities of a district that would be 200 moves with five UPDATEs each across the whole table).

Under the lock it verifies that the set of children of the parent is exactly $orderedIds (otherwise TREE_STALE: a child was added, removed or moved in the meantime) and that the children fill the parent interval contiguously (otherwise TREE_NODE_CORRUPTED: a broken tree is not reordered). When the order does not change nothing is written. The result carries data.changed (number of children that changed place).

Parameters

$table : string
$columns : array{id: string, left: string, right: string, parent: string}: column names
$parentId : int|null: null is the root level of the scope tree
$orderedIds : array<int, int>: child ids in the new order
$scope : array<string, scalar|null> = []: column => value (scope filter)

Return values

Result

setTreeLockTimeout()

Changes the tree lock timeout; for concurrency tests and the CLI, not for normal operation.


    public
                    setTreeLockTimeout(int $seconds) : void

Parameters

$seconds : int

buildScopeCondition()

Turns the scope filter into an SQL fragment (`AND col <=> :scope_col`) plus parameters.


    private
                    buildScopeCondition(array<string, scalar|null> $scope) : array{0: string, 1: array}

Parameters

$scope : array<string, scalar|null>

Return values

array{0: string, 1: array}

checkMoveExpectation()

Verifies the move contract against the current tree state; called under the lock with locking reads, so the verified state is the state the write is computed from.


    private
                    checkMoveExpectation(Connection $conn, string $t, string $idCol, string $leftCol, string $parentCol, string $scopeSql, array<string, scalar|null> $scopeParams, int $id, int|null $currentParentId, int|null $newParentId, TreeMoveExpectation $expectation) : Result|null

Adjacency is verified by sibling ORDER (no sibling under newParentId with lft between prev and next), not by the arithmetic prev.rgt + 1 == next.lft: it is just as strict on a healthy tree, the moved node excludes itself (id <> :drag, also for a move within the same parent), and the edges need no special case for the root level (start = no sibling before next, end = no sibling after prev).

Returns null when the contract holds; otherwise INVALID_ARGUMENT (nonsensical input combination) or TREE_STALE (state changed or the client saw an incomplete list).

Parameters

$conn : Connection
$t : string
$idCol : string
$leftCol : string
$parentCol : string
$scopeSql : string
$scopeParams : array<string, scalar|null>
$id : int
$currentParentId : int|null
$newParentId : int|null
$expectation : TreeMoveExpectation

Return values

Result|null

closeTreeGapUnderLock()


    private
                    closeTreeGapUnderLock(string $table, array{left: string, right: string} $columns, int $lft, int $rgt, array<string, scalar|null> $scope) : Result

Parameters

$table : string
$columns : array{left: string, right: string}
$lft : int
$rgt : int
$scope : array<string, scalar|null>

Return values

Result

fetchExpectedSiblingLft()

Returns `lft` of the expected sibling if it is a child of `$parentId` today; otherwise `null` (deleted, moved under another parent, outside the scope).


    private
                    fetchExpectedSiblingLft(Connection $conn, string $t, string $idCol, string $leftCol, string $parentCol, string $scopeSql, array<string, scalar|null> $scopeParams, int $siblingId, int|null $parentId) : int|null

Parameters

$conn : Connection
$t : string
$idCol : string
$leftCol : string
$parentCol : string
$scopeSql : string
$scopeParams : array<string, scalar|null>
$siblingId : int
$parentId : int|null

Return values

int|null

fetchNodeLevel()

Returns the level of a node by id (helper for {@see insertTreeNode()}).


    private
                    fetchNodeLevel(Connection $conn, string $table, string $levelCol, string $idCol, string $scopeSql, array<string, scalar|null> $scopeParams, int $id) : int

Parameters

$conn : Connection
$table : string
$levelCol : string
$idCol : string
$scopeSql : string
$scopeParams : array<string, scalar|null>
$id : int

Return values

int

insertTreeNodeUnderLock()


    private
                    insertTreeNodeUnderLock(string $table, array{id: string, left: string, right: string, parent: string, level: string} $columns, int $id, array<string, scalar|null> $scope) : Result

Parameters

$table : string
$columns : array{id: string, left: string, right: string, parent: string, level: string}
$id : int
$scope : array<string, scalar|null>

Return values

Result

moveSubtreeUnderLock()


    private
                    moveSubtreeUnderLock(string $table, array{id: string, left: string, right: string, parent: string, level: string} $columns, int $id, int|null $newParentId, array<string, scalar|null> $scope, int|null $afterSiblingId, TreeMoveExpectation|null $expectation) : Result

Parameters

$table : string
$columns : array{id: string, left: string, right: string, parent: string, level: string}
$id : int
$newParentId : int|null
$scope : array<string, scalar|null>
$afterSiblingId : int|null
$expectation : TreeMoveExpectation|null

Return values

Result

moveTreeNodeUnderLock()


    private
                    moveTreeNodeUnderLock(string $table, array{id: string, left: string, right: string, parent: string} $columns, int $id, int $direction, array<string, scalar|null> $scope) : Result

Parameters

$table : string
$columns : array{id: string, left: string, right: string, parent: string}
$id : int
$direction : int
$scope : array<string, scalar|null>

Return values

Result

quoteIdentifier()


    private
                    quoteIdentifier(string $identifier) : string

Parameters

$identifier : string

Return values

string

releaseTreeLock()

Releases one level of the tree lock. A failure is only logged: a failed release must not overwrite the operation result; the connection lock disappears with the connection anyway.


    private
                    releaseTreeLock(string $name) : void

Parameters

$name : string

reorderTreeChildrenUnderLock()


    private
                    reorderTreeChildrenUnderLock(string $table, array{id: string, left: string, right: string, parent: string} $columns, int|null $parentId, array<int, int> $orderedIds, array<string, scalar|null> $scope) : Result

Parameters

$table : string
$columns : array{id: string, left: string, right: string, parent: string}
$parentId : int|null
$orderedIds : array<int, int>
$scope : array<string, scalar|null>

Return values

Result

siblingWindow()

Returns the SQL window between the expected neighbors (`lft` of the previous and the next one), or `TREE_STALE` when they do not follow each other. `null` means no neighbor on that side (start/end of the parent).


    private
                    siblingWindow(string $leftCol, int|null $prevLft, int|null $nextLft, int $prevId, int $nextId) : array{0: string, 1: array}|Result

Parameters

$leftCol : string
$prevLft : int|null
$nextLft : int|null
$prevId : int
$nextId : int

Return values

array{0: string, 1: array}|Result

TreeTrait

Table of Contents

Properties

Methods

Properties

$treeLockTimeout

Methods

buildTreeLockName()

Parameters

Return values

closeTreeGap()

Parameters

Return values

computeChildrenReorder()

Parameters

Return values

degenerateTreeNodeResult()

Parameters

Return values

getTreeSubtree()

Parameters

Return values

insertTreeNode()

Parameters

Return values

inTreeLock()

Parameters

Return values

moveSubtree()

Parameters

Return values

moveTreeNode()

Parameters

Return values

reorderTreeChildren()

Parameters

Return values

setTreeLockTimeout()

Parameters

buildScopeCondition()

Parameters

Return values

checkMoveExpectation()

Parameters

Return values

closeTreeGapUnderLock()

Parameters

Return values

fetchExpectedSiblingLft()

Parameters

Return values

fetchNodeLevel()

Parameters

Return values

insertTreeNodeUnderLock()

Parameters

Return values

moveSubtreeUnderLock()

Parameters

Return values

moveTreeNodeUnderLock()

Parameters

Return values

quoteIdentifier()

Parameters

Return values

releaseTreeLock()

Parameters

reorderTreeChildrenUnderLock()

Parameters

Return values

siblingWindow()

Parameters

Return values