#Architecture Overview

This section is a source-level walkthrough of how vusys/laravel-nestedset is built — the algorithms, the SQL, and how the classes collaborate. The task-oriented sections (Tree Operations, Querying, Aggregates, Maintenance) tell you what the package does; Internals tells you how it does it, so you can read the source, debug a corruption report, or contribute with confidence.

#1. The shape of the package

Every public capability is reachable from one trait, NodeTrait (src/NodeTrait.php). A model opts in by using the trait and implementing the HasNestedSet contract:

use Illuminate\Database\Eloquent\Model;
use Vusys\NestedSet\Contracts\HasNestedSet;
use Vusys\NestedSet\NodeTrait;

class Category extends Model implements HasNestedSet
{
    use NodeTrait;
}

NodeTrait is deliberately thin — it is a composition of nine concerns, each owning one slice of behaviour, plus a handful of Eloquent overrides. The trait body is little more than a list of use statements:

trait NodeTrait
{
    use HasBulkInsert;
    use HasNestedSetAggregates;
    use HasNodeInspection;
    use HasSoftDeleteTree;
    use HasTreeExport;
    use HasTreeMutation;
    use HasTreeRelations;
    use HasTreeRepair;
    use HasTreeWalk;
    // ...
}

#1.1 The walker — src/Walker/

HasTreeWalk is thin glue; the real implementation lives in four value objects:

• SubtreeWalker is the engine. It takes a flat collection plus a root model, builds two indexes on construction (byKey: id => Model and childrenByParentKey: parentId => list<id>, both O(N)), and exposes iterative-DFS and queue-BFS generators that yield (Model, WalkContext) tuples. Both DFS strategies use an explicit task stack so deep trees do not blow PHP's call stack. The walker also implements Countable and exposes maxDepth() / leafCount() companions — all three share a single-pass index walk and memoise.
• WalkContext is the readonly value object passed as the visitor's second argument. It carries depth (relative to the walk root, not the absolute depth column), parent, sibling index/count, the derived isFirstSibling/isLastSibling flags, and a lazy pathToRoot() that walks up via the index on first call.
• WalkFilter is a final readonly triple of maxDepth, visitable, includeRoot. Named constructors (depth(), where(), compose()) and an instance andThen() cover the common shapes. The same WalkFilter plugs into every exporter's option object so a depth/predicate filter applied to ASCII output works identically against Mermaid and JSON.
• WalkSignal is a two-case enum (SkipSubtree, Stop) returned by visitor closures to steer the walk. Skip is honoured by pre-order DFS and BFS, ignored by post-order. Returning null (or void) continues.

The walker is purely a consumer of in-memory data — it never queries. When the public methods on HasTreeWalk are called without an explicit $subtree, they fall back to $this->descendants; if the relation is not loaded either, they throw UnloadedSubtreeException. The exporters use it internally to compute their visible-key set when a WalkFilter is supplied.

Models must implements HasNestedSet (src/Contracts/HasNestedSet.php). The trait supplies a default implementation of every contract method, so the interface costs nothing to satisfy — its job is to give Larastan (and your IDE) a typed surface to resolve getLft(), getBounds(), and the column-name accessors against.

#2. The layers underneath

The concerns are the API surface. They delegate the actual SQL to a layer of query builders under src/Query/:

 model (NodeTrait)
   │  appendToNode($parent)->save()
   ▼
 HasTreeMutation            ← queues a PendingOperation, dispatches on save()
   │  newTreeMutator()
   ▼
 TreeMutationBuilder        ← emits the atomic CASE WHEN UPDATE (makeGap/moveNode)
   │  new TreeExpression(...)
   ▼
 TreeExpression             ← backend-aware raw SQL fragment (no binding escaping)
   ▼
 database

• TreeBaseQueryBuilder — the package's Illuminate\Database\Query\Builder subclass; a home for SQL-execution hooks (e.g. the MariaDB optimizer_switch prefix used by fresh-aggregate reads).
• TreeQueryBuilder — the Eloquent builder returned from every NodeTrait model. Adds whereDescendantOf, whereAncestorOf, whereIsRoot, withDepth, defaultOrder, withFreshAggregates, and more.
• TreeMutationBuilder / TreeRepairBuilder — internal builders for the write and repair paths. They take a connection, table, and column names and emit the single-statement updates.
• TreeExpression — wraps a raw SQL string as an Expression so the query builder splices it into the SET clause verbatim. It is also the backend-dialect generator (LATERAL on PostgreSQL/MySQL, STRAIGHT_JOIN on MySQL, derived-table shape on MariaDB, correlated fallback on SQLite).

NodeTrait wires these in via two Eloquent overrides:

public function newEloquentBuilder($query): TreeQueryBuilder
{
    return new TreeQueryBuilder($query);
}

protected function newBaseQueryBuilder(): TreeBaseQueryBuilder
{
    $connection = $this->getConnection();

    return new TreeBaseQueryBuilder(
        $connection,
        $connection->getQueryGrammar(),
        $connection->getPostProcessor(),
    );
}

Because newEloquentBuilder() is narrowed to return TreeQueryBuilder, every Category::query() chain exposes the tree scopes with full static analysis — no macros, no @method annotations.

#3. Lifecycle wiring — bootNodeTrait()

The trait hooks into the Eloquent model lifecycle in bootNodeTrait() (src/NodeTrait.php). This single method is the spine of the whole package: the mutation engine, the aggregate maintenance, and the cascade logic all hang off these standard model events.

Each aggregate hook runs inside runAggregateHook(), a try/catch that dispatches an AggregateMaintenanceFailed event before re-throwing — so a failing rollup surfaces to Sentry/Bugsnag while still rolling back the wrapping transaction.

A detail worth internalising early: the saving hook guards against the most common footgun — calling Model::create([...]) or ->save() on a node that was never placed in the tree:

if (! $node->exists
    && method_exists($node, 'isPlacedInTree')
    && ! $node->isPlacedInTree()
) {
    throw new UnplacedNodeException(/* ... */);
}

Without this, the row would land with lft = rgt = 0 (the migration default) and create an invalid_bounds corruption. The package fails loudly instead.

#4. The aggregates subsystem

src/Aggregates/ is a self-contained subsystem the lifecycle hooks call into. There are three kinds of aggregate column, all sharing the same hooks:

• SQL aggregates — declared via #[NestedSetAggregate]; SUM/COUNT/AVG/ MIN/MAX (and variance, bitwise, bool, geometric/harmonic mean, …) over a source column with optional filters.
• Listener aggregates — declared via #[NestedSetAggregateListener]; a PHP contribution(Model $node) method computes each row's value.
• Ad-hoc fresh aggregates — withFreshAggregates([...]); no stored column, recomputed on read via a correlated subquery.

Maintenance picks one of two strategies per column — Strategy/DeltaMaintenance (a signed delta applied to ancestors) or Strategy/RecomputeMaintenance (a SELECT-then-UPDATE of the invalidated subset) — depending on whether the change can be expressed as a delta. The full machinery is covered in Aggregate Maintenance.

#5. Scoping (multi-tree tables)

A single table can hold many independent trees ("scopes"). Declare the partition column(s) with #[NestedSetScope('menu_id')] or a getScopeAttributes() method. NestedSetScopeResolver (src/Scope/) derives the scope; every builder constrains its writes to the scope, and HasTreeMutation rejects cross-scope writes with ScopeViolationException. Scoped repair methods (fixTree, fixAggregates) require an anchor node so a repair stays inside one tree rather than walking a multi-million-row table. See Scoped Trees.

#6. The service provider — schema macros

NestedSetServiceProvider (src/NestedSetServiceProvider.php) registers four Blueprint macros plus a per-connection hook:

• $table->nestedSet(scope, cover, parentIdType) — adds the four columns (lft/rgt unsigned bigint, parent_id nullable, depth unsigned int) and one composite index.
• $table->dropNestedSet(...) — the inverse.
• $table->nestedSetAggregate('column', type: ...) — adds an aggregate storage column plus its companion columns (see Aggregate Maintenance).
• $table->dropNestedSetAggregate(...) — the inverse, dropping companions too.

The composite index column order is set by nestedSetIndexColumns():

return [
    ...self::toColumnList($scope),   // scope columns first
    $lft,
    $rgt,
    $parentId,
    ...self::toColumnList($cover),   // covering columns last
];

Scope first means each tree occupies its own contiguous slice of the index; the cover tail lets subtree-aggregate subqueries (WHERE inner.lft >= outer.lft AND inner.rgt <= outer.rgt) run as covering scans with no heap visits. The provider also installs SQLite user-defined BIT_OR/BIT_AND/BIT_XOR aggregates on every fresh connection so the same native-aggregate SQL runs on all four backends.

#7. Configuration

config/nestedset.php is small and worth reading in full once:

• columns.* — override the four structural column names.
• auto_transaction (default true) — wrap every mutation in a transaction.
• aggregate_locking (auto / always / never) — control FOR UPDATE locking on the recompute path. See Concurrency & Transactions.
• queue.* — connection/queue routing for queueFixAggregates().
• events_enabled (default true) — short-circuit every telemetry firing site.

#8. Load-bearing design decisions

These five choices explain most of why the code looks the way it does. Keep them in mind while reading the rest of this section.

#8.1 parent_id is the source of truth

lft/rgt/depth are a derived index. fixTree() rebuilds the index from a parent_id walk — never the reverse. A corrupted index is always recoverable as long as parent_id is intact. → Integrity & Repair

#8.2 Every shift is one atomic CASE WHEN UPDATE

Inserts, moves, and bulk repairs renumber many rows in a single statement, so the on-disk state never passes through an invariant-violating intermediate. → The Mutation Engine

#8.3 depth is stored, not computed

It is maintained on every mutation, which makes level queries and aggregate ancestry scans cheap.

#8.4 Mutations are queued, then dispatched on save()

appendToNode($parent) only records a PendingOperation; the write happens in the saving hook, so the gap, the INSERT/UPDATE, and the aggregate hooks share one transaction.

#8.5 Telemetry is observable but optional

Every meaningful operation fires a typed event, gated by events_enabled and a per-event listener check so an unobserved event costs nothing. → Concurrency & Transactions

#9. Where to go next

Read The Nested-Set Model first — it establishes the encoding and invariants every other page assumes. From there, the pages can be read in any order.