👈🏾 👨‍❤️‍💋‍👨 🌟 How to make friends ltree and Laravel 🐧 🔱 ⌨️

I participate in the development of an ERP system, I will not devote you to details, this is a secret behind seven seals, but I will only say one thing, we have a lot of tree-like directories and their nesting is not limited, the number in some is several thousand, but you need to work with them as efficiently and conveniently as possible, both in terms of code and performance.

What do we need

Quickly reach any cuts of a tree and its branches, both up to the parents and down to the leaves
Also be able to reach all nodes except leaves
The tree must be consistent, i.e. have no missing nodes in the parent hierarchy
Materialized paths should be built automatically
When you move or delete a node, all child nodes are also updated and their paths are rebuilt
Learn from flat collection, quickly build a tree.
Since there are many directories, the components must be reusable.
Since it is planned to take it to the github, use abstractions and interfaces.

Since we are using Postgres, the choice fell on ltree, you can read more about what it is at the end of the article.

Installing an extension

Example migration to create an extension

<?php

use Illuminate\Database\Migrations\Migration;
use Illuminate\Support\Facades\App;
use Illuminate\Support\Facades\DB;

class CreateLtreeExtension extends Migration
{
    public function up(): void
    {
        DB::statement('CREATE EXTENSION IF NOT EXISTS LTREE');
    }

    public function down(): void
    {
        DB::statement('DROP EXTENSION IF EXISTS LTREE');
    }
}

A task

For example, we have products and we have product categories. Categories represent a tree and can have subordinate categories, the nesting level is unlimited and can be any. Let's say these will be tables.

Categories of goods (categories)

id	bigserial	PK
path	ltree
parent_id	biginteger

path ,

id: 1

path: 1

parent_id: null

id: 2

path: 1.2

parent_id: 2

..

(products)

id	bigserial	PK
category_id	biginteger

Postgres, , extension, Doctrine , , composer , :

composer require umbrellio/laravel-ltree

, Postgres

<?php

use Illuminate\Database\Migrations\Migration;
use Illuminate\Support\Facades\DB;
use Illuminate\Support\Facades\Schema;
use Umbrellio\Postgres\Schema\Blueprint;

class CreateCategoryExtension extends Migration
{
    public function up(): void
    {
        Schema::table('categories', function (Blueprint $table) {
            $table->bigIncrements('id');
            $table->bigInteger('parent_id')->nullable();
            $table->ltree('path')->nullable();

            $table
                ->foreign('parent_id')
                ->references('id')
                ->on('categories');

            $table->index(['parent_id']);
            $table->unique(['path']);
        });

        DB::statement("COMMENT ON COLUMN categories.path IS '(DC2Type:ltree)'");
    }

    public function down(): void
    {
        Schema::drop('categories');
    }
}

, , , :

SELECT * FROM categories;

, , , , . , ltree, :

SELECT * FROM categories WHERE parent_id IS NULL

, . , , , , ID :

SELECT * FROM categories WHERE parent_id = <ID>

, , , , ltree. , , , , , :

SELECT * FROM categories WHERE path @> text2ltree('<ID>')

Laravel

, ltree. , , , .. Eloquent\Model .

: LTreeInterface

<?php

namespace Umbrellio\LTree\Interfaces;

interface LTreeInterface
{
    public const AS_STRING = 1;
    public const AS_ARRAY = 2;
  
    public function getLtreeParentColumn(): string;
    public function getLtreeParentId(): ?int;
    public function getLtreePathColumn(): string;
    public function getLtreePath($mode = self::AS_ARRAY);
    public function getLtreeLevel(): int;
}

: LTreeTrait

<?php

trait LTreeTrait
{
    abstract public function getAttribute($key);
    
    public function getLtreeParentColumn(): string
    {
        return 'parent_id';
    }

    public function getLtreePathColumn(): string
    {
        return 'path';
    }

    public function getLtreeParentId(): ?int
    {
        $value = $this->getAttribute($this->getLtreeParentColumn());
        return $value ? (int) $value : null;
    }

    public function getLtreePath($mode = LTreeInterface::AS_ARRAY)
    {
        $path = $this->getAttribute($this->getLtreePathColumn());
        if ($mode === LTreeModelInterface::AS_ARRAY) {
            return $path !== null ? explode('.', $path) : [];
        }
        return (string) $path;
    }

    public function getLtreeLevel(): int
    {
        return is_array($path = $this->getLtreePath()) ? count($path) : 1;

, LTreeInterface: Category

<?php

final class Category extends Model implements LTreeInterface
{
    use LTreeTrait;

    protected $table = 'categories';
    protected $fillable = ['parent_id', 'path'];
    protected $timestamps = false;
}

, :

: LTreeTrait

<?php

use Illuminate\Database\Eloquent\Builder;
use Illuminate\Database\Eloquent\Model;
use Illuminate\Database\Eloquent\Relations\BelongsTo;
use Illuminate\Database\Eloquent\Relations\HasMany;
use Illuminate\Database\Eloquent\SoftDeletes;
use Umbrellio\LTree\Collections\LTreeCollection;
use Umbrellio\LTree\Interfaces\LTreeModelInterface;

trait LTreeTrait
{
    //...
  
		public function scopeParentsOf(Builder $query, array $paths): Builder
    {
        return $query->whereRaw(sprintf(
            "%s @> array['%s']::ltree[]",
            $this->getLtreePathColumn(),
            implode("', '", $paths)
        ));
    }

    public function scopeRoot(Builder $query): Builder
    {
        return $query->whereRaw(sprintf('nlevel(%s) = 1', $this->getLtreePathColumn()));
    }

    public function scopeDescendantsOf(Builder $query, LTreeModelInterface $model): Builder
    {
        return $query->whereRaw(sprintf(
            "({$this->getLtreePathColumn()} <@ text2ltree('%s')) = true",
            $model->getLtreePath(LTreeModelInterface::AS_STRING),
        ));
    }

    public function scopeAncestorsOf(Builder $query, LTreeModelInterface $model): Builder
    {
        return $query->whereRaw(sprintf(
            "({$this->getLtreePathColumn()} @> text2ltree('%s')) = true",
            $model->getLtreePath(LTreeModelInterface::AS_STRING),
        ));
    }

    public function scopeWithoutSelf(Builder $query, int $id): Builder
    {
        return $query->whereRaw(sprintf('%s <> %s', $this->getKeyName(), $id));
    }

scopeAncestorsOf - ( )
scopeDescendantsOf - ( )
scopeWithoutSelf -
scopeRoot - 1-
scopeParentsOf - scopeAncestorsOf, .

.. , , , .

, , . - , , . , .

, , , :

<?php

// ID  () = 15

$categories = Category::ancestorsOf(15)->get()->pluck('id')->toArray();
$products = Product::whereIn('category_id', $caregories)->get();

, , , .

, 1 , :

SELECT * FROM categories;

, , , , - :

<?php

$a = [
  [1, '1', null],
  [2, '1.2', 1],
  [3, '1.2.3', 2],
  [4, '4', null],
  [5, '1.2.5', 2],
  [6, '4.6', 4],
  // ...
];

<?php

$a = [
    0 => [
        'id' => 1,
        'level' => 1,
        'children' => [
            0 => [
                'id' => 2,
                'level' => 2,
                'children' => [
                    0 => [
                        'id' => 3,
                        'level' => 3,
                        'children' => [],
                    ],
                    1 => [
                        'id' => 5,
                        'level' => 3,
                        'children' => [],
                    ],
                ]
            ]
        ]
   ],
   1 => [
       'id' => 4,
       'level' => 1,
       'children' => [
            0 => [
                'id' => 6,
                'level' => 2,
                'children' => [],
            ]
       ]
   ]
];

, , , :

<?php

$categories = Category::all()->toTree(); // Collection

function renderTree(Collection $collection) {
   /** @var LTreeNode $item */
   foreach ($collection as $item) {
      if ($item->children->isNotEmpty()) {
         renderTree($item->children);
         return;
      }
   }
   
   echo str_pad($item->id, $item->level - 1, "---", STR_PAD_LEFT) . PHP_EOL;
}

, , :

<?php

trait LTreeTrait
{
    //...

    public function newCollection(array $models = []): LTreeCollection
    {
        return new LTreeCollection($models);
    }

    public function ltreeParent(): BelongsTo
    {
        return $this->belongsTo(static::class, $this->getLtreeParentColumn());
    }

    public function ltreeChildren(): HasMany
    {
        return $this->hasMany(static::class, $this->getLtreeParentColumn());
    }
}

, , , .

: LTreeCollection

<?php

use Illuminate\Database\Eloquent\Collection;
use Illuminate\Database\Eloquent\Model;
use Umbrellio\LTree\Helpers\LTreeBuilder;
use Umbrellio\LTree\Helpers\LTreeNode;
use Umbrellio\LTree\Interfaces\HasLTreeRelations;
use Umbrellio\LTree\Interfaces\LTreeInterface;
use Umbrellio\LTree\Interfaces\ModelInterface;
use Umbrellio\LTree\Traits\LTreeModelTrait;

class LTreeCollection extends Collection
{
    private $withLeaves = true;

    public function toTree(bool $usingSort = true, bool $loadMissing = true): LTreeNode
    {
        if (!$model = $this->first()) {
            return new LTreeNode();
        }

        if ($loadMissing) {
            $this->loadMissingNodes($model);
        }

        if (!$this->withLeaves) {
            $this->excludeLeaves();
        }

        $builder = new LTreeBuilder(
            $model->getLtreePathColumn(),
            $model->getKeyName(),
            $model->getLtreeParentColumn()
        );

        return $builder->build($collection ?? $this, $usingSort);
    }

    public function withLeaves(bool $state = true): self
    {
        $this->withLeaves = $state;

        return $this;
    }

    private function loadMissingNodes($model): self
    {
        if ($this->hasMissingNodes($model)) {
            $this->appendAncestors($model);
        }

        return $this;
    }

    private function excludeLeaves(): void
    {
        foreach ($this->items as $key => $item) {
            if ($item->ltreeChildren->isEmpty()) {
                $this->forget($key);
            }
        }
    }

    private function hasMissingNodes($model): bool
    {
        $paths = collect();

        foreach ($this->items as $item) {
            $paths = $paths->merge($item->getLtreePath());
        }

        return $paths
            ->unique()
            ->diff($this->pluck($model->getKeyName()))
            ->isNotEmpty();
    }
  
    private function appendAncestors($model): void
    {
        $paths = $this
            ->pluck($model->getLtreePathColumn())
            ->toArray();
        $ids = $this
            ->pluck($model->getKeyName())
            ->toArray();

        $parents = $model::parentsOf($paths)
            ->whereKeyNot($ids)
            ->get();

        foreach ($parents as $item) {
            $this->add($item);
        }
    }
}

Laravel, .. . toTree, , , children - .

, , :

<?php

$categories = Category::ancestorsOf(15)->get()->toTree();

, , - , ( ):

LTreeNode

<?php

use Illuminate\Database\Eloquent\Collection;
use Illuminate\Database\Eloquent\Model;
use InvalidArgumentException;
use Umbrellio\Common\Contracts\AbstractPresenter;
use Umbrellio\LTree\Collections\LTreeCollection;
use Umbrellio\LTree\Interfaces\LTreeInterface;
use Umbrellio\LTree\Interfaces\ModelInterface;

class LTreeNode extends AbstractPresenter
{
    protected $parent;
    protected $children;

    public function __construct($model = null)
    {
        parent::__construct($model);
    }

    public function isRoot(): bool
    {
        return $this->model === null;
    }

    public function getParent(): ?self
    {
        return $this->parent;
    }

    public function setParent(?self $parent): void
    {
        $this->parent = $parent;
    }

    public function addChild(self $node): void
    {
        $this
            ->getChildren()
            ->add($node);
        $node->setParent($this);
    }

    public function getChildren(): Collection
    {
        if (!$this->children) {
            $this->children = new Collection();
        }
        return $this->children;
    }

    public function countDescendants(): int
    {
        return $this
            ->getChildren()
            ->reduce(
                static function (int $count, self $node) {
                    return $count + $node->countDescendants();
                },
                $this
                    ->getChildren()
                    ->count()
            );
    }

    public function findInTree(int $id): ?self
    {
        if (!$this->isRoot() && $this->model->getKey() === $id) {
            return $this;
        }
        foreach ($this->getChildren() as $child) {
            $result = $child->findInTree($id);
            if ($result !== null) {
                return $result;
            }
        }
        return null;
    }

    public function each(callable $callback): void
    {
        if (!$this->isRoot()) {
            $callback($this);
        }
        $this
            ->getChildren()
            ->each(static function (self $node) use ($callback) {
                $node->each($callback);
            });
    }

    public function toCollection(): LTreeCollection
    {
        $collection = new LTreeCollection();
        $this->each(static function (self $item) use ($collection) {
            $collection->add($item->model);
        });
        return $collection;
    }

    public function pathAsString()
    {
        return $this->model ? $this->model->getLtreePath(LTreeInterface::AS_STRING) : null;
    }

    public function toTreeArray(callable $callback)
    {
        return $this->fillTreeArray($this->getChildren(), $callback);
    }

    /**
     * Usage sortTree(['name' =>'asc', 'category'=>'desc'])
     * or callback with arguments ($a, $b) and return -1 | 0 | 1
     * @param array|callable $options
     */
    public function sortTree($options)
    {
        $children = $this->getChildren();
        $callback = $options;
        if (!is_callable($options)) {
            $callback = $this->optionsToCallback($options);
        }
        $children->each(static function ($child) use ($callback) {
            $child->sortTree($callback);
        });
        $this->children = $children
            ->sort($callback)
            ->values();
    }

    private function fillTreeArray(iterable $nodes, callable $callback)
    {
        $data = [];
        foreach ($nodes as $node) {
            $item = $callback($node);
            $children = $this->fillTreeArray($node->getChildren(), $callback);
            $item['children'] = $children;
            $data[] = $item;
        }
        return $data;
    }

    private function optionsToCallback(array $options): callable
    {
        return function ($a, $b) use ($options) {
            foreach ($options as $property => $sort) {
                if (!in_array(strtolower($sort), ['asc', 'desc'], true)) {
                    throw new InvalidArgumentException("Order '${sort}'' must be asc or desc");
                }
                $order = strtolower($sort) === 'desc' ? -1 : 1;
                $result = $a->{$property} <=> $b->{$property};
                if ($result !== 0) {
                    return $result * $order;
                }
            }
            return 0;
        };
    }
}

LTreeBuilder

<?php

class LTreeBuilder
{
    private $pathField;
    private $idField;
    private $parentIdField;
    private $nodes = [];
    private $root = null;

    public function __construct(string $pathField, string $idField, string $parentIdField)
    {
        $this->pathField = $pathField;
        $this->idField = $idField;
        $this->parentIdField = $parentIdField;
    }

    public function build(LTreeCollection $items, bool $usingSort = true): LTreeNode
    {
        if ($usingSort === true) {
            $items = $items->sortBy($this->pathField, SORT_STRING);
        }

        $this->root = new LTreeNode();

        foreach ($items as $item) {
            $node = new LTreeNode($item);

            [$id, $parentId] = $this->getNodeIds($item);

            $parentNode = $this->getNode($parentId);
            $parentNode->addChild($node);

            $this->nodes[$id] = $node;
        }
        return $this->root;
    }

    private function getNodeIds($item): array
    {
        $parentId = $item->{$this->parentIdField};
        $id = $item->{$this->idField};

        if ($id === $parentId) {
            throw new LTreeReflectionException($id);
        }
        return [$id, $parentId];
    }

    private function getNode(?int $id): LTreeNode
    {
        if ($id === null) {
            return $this->root;
        }
        if (!isset($this->nodes[$id])) {
            throw new LTreeUndefinedNodeException($id);
        }
        return $this->nodes[$id];
    }
}

AbstractLTreeResource

<?php

namespace Umbrellio\LTree\Resources;

use Illuminate\Http\Resources\Json\ResourceCollection;
use Illuminate\Support\Collection;
use Umbrellio\LTree\Collections\LTreeCollection;

abstract class LTreeResourceCollection extends ResourceCollection
{
    /**
     * @param LTreeCollection|Collection $resource
     */
    public function __construct($resource, $sort = null, bool $usingSort = true, bool $loadMissing = true)
    {
        $collection = $resource->toTree($usingSort, $loadMissing);

        if ($sort) {
            $collection->sortTree($sort);
        }

        parent::__construct($collection->getChildren());
    }
}

AbstractLTreeResourceCollection

<?php

namespace Umbrellio\LTree\Resources;

use Illuminate\Http\Resources\Json\JsonResource;
use Umbrellio\LTree\Helpers\LTreeNode;
use Umbrellio\LTree\Interfaces\LTreeInterface;

/**
 * @property LTreeNode $resource
 */
abstract class LTreeResource extends JsonResource
{
    final public function toArray($request)
    {
        return array_merge($this->toTreeArray($request, $this->resource->model), [
            'children' => static::collection($this->resource->getChildren())->toArray($request),
        ]);
    }

    /**
     * @param LTreeInterface $model
     */
    abstract protected function toTreeArray($request, $model);
}

, JsonResource:

CategoryResource

<?php

use Umbrellio\LTree\Helpers\LTreeNode;
use Umbrellio\LTree\Resources\LTreeResource;

class CategoryResource extends LTreeResource
{
    public function toTreeArray($request, LTreeNode $model)
    {
        return [
            'id' => $model->id,
            'level' => $model->getLtreeLevel(),
        ];
    }
}

CategoryResourceCollection

<?php

use Umbrellio\LTree\Resources\LTreeResourceCollection;

class CategoryResourceCollection extends LTreeResourceCollection
{
    public $collects = CategoryResource::class;
}

, CategoryController data json:

<?php

use Illuminate\Routing\Controller;
use Illuminate\Http\Request;

class CategoryController extends Controller
{
    //...
  
    public function data(Request $request)
    {
        return response()->json(
            new CategoryResourceCollection(
                Category::all(),
                ['id' => 'asc']
            )
        );
    } 
}

, toTree, .. Eloquent\Builder- (get, all, first ) LtreeInterface LtreeCollection, , , .

,

, , , .

, , .

, :

id	input
parent_id	select

.. , , parent_id , . path id parent_id.

, .

path

<?php

namespace Umbrellio\LTree\Services;

use Illuminate\Database\Eloquent\Model;
use Umbrellio\LTree\Helpers\LTreeHelper;
use Umbrellio\LTree\Interfaces\LTreeModelInterface;
use Umbrellio\LTree\Interfaces\LTreeServiceInterface;

final class LTreeService implements LTreeServiceInterface
{
    private $helper;

    public function __construct(LTreeHelper $helper)
    {
        $this->helper = $helper;
    }

    public function createPath(LTreeModelInterface $model): void
    {
        $this->helper->buildPath($model);
    }

    public function updatePath(LTreeModelInterface $model): void
    {
        $columns = array_intersect_key($model->getAttributes(), array_flip($model->getLtreeProxyUpdateColumns()));

        $this->helper->moveNode($model, $model->ltreeParent, $columns);
        $this->helper->buildPath($model);
    }

    public function dropDescendants(LTreeModelInterface $model): void
    {
        $columns = array_intersect_key($model->getAttributes(), array_flip($model->getLtreeProxyDeleteColumns()));

        $this->helper->dropDescendants($model, $columns);
    }
}

createPath - path ,
updatePath - path . , path , , , .. 1000 - UPDATE - .

.. , .
dropDescendants - , , , , , , , .

getLtreeProxyDeleteColumns getLtreeProxyUpdateColumns - deleted_at, updated_at, editor_id , .

<?php

class CategoryService
{
   private LTreeService $service;
  
   public function __construct (LTreeService $service)
   {
      $this->service = $service; 
   }
  
   public function create (array $data): void
   {
       $model = App::make(Category::class);
       $model->fill($data);
       $model->save();
     
       //     
       $this->service->createPath($model);
   }
}

, , , , , , + , - Deadlock.

Postgres / PHP / Laravel (, ), , , .

composer: umbrellio/laravel-ltree
ltree ( parent_id path -)
LTreeModelInterface LTreeModelTrait Eloquent\Model-.
LTreeService /
Use LTreeResource and LTreeResourceCollection resources if you have a SPA

Resources for learning

https://postgrespro.ru/docs/postgresql/13/ltree - here descriptions of the Postgres extension, with examples and in Russian
https://www.postgresql.org/docs/13/ltree.html - for those who like to read manuals in the original

Thanks for attention.

How to make friends ltree and Laravel

What do we need

Installing an extension

A task

Laravel

,

Resources for learning

More articles: