Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
100.00%
208 / 208
100.00%
39 / 39
 CRAP
100.00%
1 / 1
BelongsToTree
100.00%
208 / 208
100.00%
39 / 39
 69
100.00%
1 / 1
 bootBelongsToTree
100.00%
15 / 15
100.00%
1 / 1
 3
 getParentForeignKeyName
100.00%
1 / 1
100.00%
1 / 1
 2
 getClosureTable
100.00%
1 / 1
100.00%
1 / 1
 2
 deleteNode
100.00%
8 / 8
100.00%
1 / 1
 2
 deleteTree
100.00%
5 / 5
100.00%
1 / 1
 1
 parent
100.00%
1 / 1
100.00%
1 / 1
 1
 children
100.00%
1 / 1
100.00%
1 / 1
 1
 ancestors
100.00%
11 / 11
100.00%
1 / 1
 1
 descendants
100.00%
11 / 11
100.00%
1 / 1
 1
 setRelation
100.00%
7 / 7
100.00%
1 / 1
 3
 setChildrenFromDescendants
100.00%
15 / 15
100.00%
1 / 1
 5
 setParentsFromAncestors
100.00%
10 / 10
100.00%
1 / 1
 4
 isRoot
100.00%
2 / 2
100.00%
1 / 1
 1
 isLeaf
100.00%
1 / 1
100.00%
1 / 1
 1
 hasChildren
100.00%
1 / 1
100.00%
1 / 1
 1
 isChildOf
100.00%
2 / 2
100.00%
1 / 1
 1
 isParentOf
100.00%
1 / 1
100.00%
1 / 1
 1
 isDescendantOf
100.00%
1 / 1
100.00%
1 / 1
 1
 isAncestorOf
100.00%
1 / 1
100.00%
1 / 1
 1
 isSiblingOf
100.00%
2 / 2
100.00%
1 / 1
 1
 findCommonAncestorWith
100.00%
5 / 5
100.00%
1 / 1
 1
 getDistanceTo
100.00%
7 / 7
100.00%
1 / 1
 2
 getDepth
100.00%
1 / 1
100.00%
1 / 1
 1
 getSubtreeDepth
100.00%
1 / 1
100.00%
1 / 1
 1
 scopeWithClosure
100.00%
6 / 6
100.00%
1 / 1
 3
 scopeWithAncestors
100.00%
1 / 1
100.00%
1 / 1
 1
 scopeWithDescendants
100.00%
1 / 1
100.00%
1 / 1
 1
 scopeWithDepth
100.00%
1 / 1
100.00%
1 / 1
 1
 scopeWhereIsRoot
100.00%
1 / 1
100.00%
1 / 1
 2
 scopeWhereIsLeaf
100.00%
3 / 3
100.00%
1 / 1
 2
 scopeWhereHasChildren
100.00%
1 / 1
100.00%
1 / 1
 1
 scopeWhereIsDescendantOf
100.00%
15 / 15
100.00%
1 / 1
 4
 scopeWhereIsAncestorOf
100.00%
15 / 15
100.00%
1 / 1
 4
 getTree
100.00%
1 / 1
100.00%
1 / 1
 1
 getTreeDepth
100.00%
2 / 2
100.00%
1 / 1
 1
 checkIfParentIdIsValid
100.00%
8 / 8
100.00%
1 / 1
 4
 deleteClosures
100.00%
9 / 9
100.00%
1 / 1
 1
 refreshClosures
100.00%
31 / 31
100.00%
1 / 1
 3
 deleteClosuresForLeaf
100.00%
2 / 2
100.00%
1 / 1
 1
1<?php
2
3namespace Baril\Bonsai\Concerns;
4
5use Baril\Bonsai\Relations\Closure;
6use Baril\Bonsai\TreeException;
7use Illuminate\Database\Eloquent\Model;
8use Illuminate\Support\Str;
9
10trait BelongsToTree
11{
12    // protected $parentForeignKey Name of the foreign key for the "parent/children" relation (defaults to parent_id)
13    // protected $closureTable Name of the closure table (defaults to [snake_cased_model_name]_tree)
14
15    public static function bootBelongsToTree()
16    {
17        static::saving(function ($item) {
18            $item->checkIfParentIdIsValid();
19        });
20        static::created(function ($item) {
21            $item->refreshClosures(false);
22        });
23        static::updated(function ($item) {
24            if ($item->isDirty($item->getParentForeignKeyName())) {
25                $item->refreshClosures(true);
26            }
27        });
28        static::deleting(function ($item) {
29            if ($item->children()->exists()) {
30                throw new TreeException('Can\'t delete an item with children!');
31            }
32            $item->deleteClosuresForLeaf();
33        });
34    }
35
36    /**
37     * Returns the name of the "parent_id" column.
38     *
39     * @return string
40     */
41    public function getParentForeignKeyName()
42    {
43        return property_exists($this, 'parentForeignKey') ? $this->parentForeignKey : 'parent_id';
44    }
45
46    /**
47     * Returns the name of the closure table.
48     *
49     * @return string
50     */
51    public function getClosureTable()
52    {
53        return isset($this->closureTable) ? $this->closureTable : Str::snake(class_basename($this)) . '_tree';
54    }
55
56    /**
57     * Deletes the model after having attached its children to its parent.
58     *
59     * @return bool|null
60     *
61     * @throws \Exception
62     */
63    public function deleteNode()
64    {
65        $parent = $this->parent;
66        if ($parent) {
67            $parent->children()->saveMany($this->children);
68        } else {
69            $this->children->each(function ($child) {
70                $child->parent()->dissociate();
71                $child->save();
72            });
73        }
74        return $this->delete();
75    }
76
77    /**
78     * Deletes the model and its descendants from the database.
79     *
80     * @return bool|null
81     *
82     * @throws \Exception
83     */
84    public function deleteTree()
85    {
86        $this->getConnection()->transaction(function () {
87            $this->descendants()->includingSelf()->update([$this->getParentForeignKeyName() => null]);
88            $this->descendants()->includingSelf()->delete();
89            $this->deleteClosures();
90        });
91    }
92
93    // =========================================================================
94    // RELATIONS
95    // =========================================================================
96
97    /**
98     *
99     * @return \Illuminate\Database\Eloquent\Relations\BelongsTo
100     */
101    public function parent()
102    {
103        return $this->belongsTo(static::class, $this->getParentForeignKeyName());
104    }
105
106    // /**
107    //  * Requires the package baril/octopus.
108    //  *
109    //  * @return \Baril\Octopus\Relations\HasManySiblings
110    //  */
111    // public function siblings()
112    // {
113    //     $parentForeignKey = $this->getParentForeignKeyName();
114    //     return new \Baril\Octopus\Relations\HasManySiblings(
115    //         $this->newInstance()->newQuery(),
116    //         $this,
117    //         $this->table . '.' . $parentForeignKey,
118    //         $parentForeignKey
119    //     );
120    // }
121
122    /**
123     *
124     * @return \Illuminate\Database\Eloquent\Relations\HasMany
125     */
126    public function children()
127    {
128        return $this->hasMany(static::class, $this->getParentForeignKeyName());
129    }
130
131    /**
132     * @return \Illuminate\Database\Eloquent\Relations\BelongsToMany
133     */
134    public function ancestors()
135    {
136        $instance = $this->newRelatedInstance(static::class);
137        return (new Closure(
138            $instance->newQuery(),
139            $this,
140            $this->getClosureTable(),
141            'descendant_id',
142            'ancestor_id',
143            $this->getKeyName(),
144            $instance->getKeyName(),
145            'ancestors'
146        ))->as('closure')->withPivot('depth')->excludingSelf();
147    }
148
149    /**
150     * @return \Illuminate\Database\Eloquent\Relations\BelongsToMany
151     */
152    public function descendants()
153    {
154        $instance = $this->newRelatedInstance(static::class);
155        return (new Closure(
156            $instance->newQuery(),
157            $this,
158            $this->getClosureTable(),
159            'ancestor_id',
160            'descendant_id',
161            $this->getKeyName(),
162            $instance->getKeyName(),
163            'descendants'
164        ))->as('closure')->withPivot('depth')->excludingSelf();
165    }
166
167    /**
168     *
169     * @param string $relation
170     * @param mixed $value
171     * @return $this
172     */
173    public function setRelation($relation, $value)
174    {
175        switch ($relation) {
176            case 'descendants':
177                $this->setChildrenFromDescendants($value);
178                break;
179            case 'ancestors':
180                $this->setParentsFromAncestors($value);
181                break;
182        }
183        return parent::setRelation($relation, $value);
184    }
185
186    /**
187     * Automatically sets the "children" (for the current object and each of
188     * its loaded descendants) when the "descendants" relationship is loaded.
189     *
190     * @param \Illuminate\Database\Eloquent\Collection $descendants
191     * @return $this
192     */
193    protected function setChildrenFromDescendants($descendants)
194    {
195        $descendants = $descendants->keyBy($this->primaryKey);
196        $parentKey = $this->getParentForeignKeyName();
197
198        $descendants->each(function ($item, $key) use ($descendants, $parentKey) {
199            if ($descendants->has($item->$parentKey)) {
200                if (!$descendants[$item->$parentKey]->relationLoaded('children')) {
201                    $descendants[$item->$parentKey]->setRelation('children', collect([]));
202                }
203                $descendants[$item->$parentKey]->children->push($item);
204            }
205        });
206
207        // Prevents an unneeded query in case we try to access the children of a leaf.
208        $descendants->each(function ($item, $key) {
209            if (!$item->relationLoaded('children') && $item->closure->_remaining_depth !== 0) {
210                $item->setRelation('children', collect([]));
211            }
212        });
213
214        return $this->setRelation('children', $descendants->values()->filter(function ($item) use ($parentKey) {
215            return $item->$parentKey == $this->getKey();
216        })->values());
217    }
218
219    /**
220     * Automatically sets the "parent" (for the current object and each of
221     * its loaded ancestors) when the "ancestors" relationship is loaded.
222     *
223     * @param \Illuminate\Database\Eloquent\Collection $ancestors
224     * @return $this
225     */
226    protected function setParentsFromAncestors($ancestors)
227    {
228        if (!$ancestors->count()) {
229            return;
230        }
231
232        $parentKey = $this->getParentForeignKeyName();
233        $keyedAncestors = $ancestors->keyBy($this->primaryKey);
234
235        $ancestors->merge([$this])->each(function ($model) use ($keyedAncestors, $parentKey) {
236            if (null === $model->$parentKey) {
237                $model->setRelation('parent', null);
238            } elseif ($keyedAncestors->has($model->$parentKey)) {
239                $model->setRelation('parent', $keyedAncestors->get($model->$parentKey));
240            }
241        });
242    }
243
244    // =========================================================================
245    // MODEL METHODS
246    // =========================================================================
247
248    /**
249     *
250     * @return bool
251     */
252    public function isRoot()
253    {
254        $parentKey = $this->getParentForeignKeyName();
255        return $this->$parentKey === null;
256    }
257
258    /**
259     *
260     * @return bool
261     */
262    public function isLeaf()
263    {
264        return !$this->children()->exists();
265    }
266
267    /**
268     *
269     * @return bool
270     */
271    public function hasChildren()
272    {
273        return $this->children()->exists();
274    }
275
276    /**
277     *
278     * @return bool
279     */
280    public function isChildOf($item)
281    {
282        $parentKey = $this->getParentForeignKeyName();
283        return $item->getKey() == $this->$parentKey;
284    }
285
286    /**
287     *
288     * @param static $item
289     * @return bool
290     */
291    public function isParentOf($item)
292    {
293        return $item->isChildOf($this);
294    }
295
296    /**
297     *
298     * @param static $item
299     * @return bool
300     */
301    public function isDescendantOf($item)
302    {
303        return $this->ancestors()->whereKey($item->getKey())->exists();
304    }
305
306    /**
307     *
308     * @param static $item
309     * @return bool
310     */
311    public function isAncestorOf($item)
312    {
313        return $item->isDescendantOf($this);
314    }
315
316    /**
317     *
318     * @param static $item
319     * @return bool
320     */
321    public function isSiblingOf($item)
322    {
323        $parentKey = $this->getParentForeignKeyName();
324        return $item->$parentKey == $this->$parentKey;
325    }
326
327    /**
328     * Returns the closest common ancestor with the provided $item.
329     * May return null if the tree has multiple roots and the 2 items have no
330     * common ancestor.
331     *
332     * @param static $item
333     * @return static|null
334     */
335    public function findCommonAncestorWith($item)
336    {
337        return $this->ancestors()
338            ->includingSelf()
339            ->whereIsAncestorOf($item->getKey(), null, true)
340            ->orderByDepth()
341            ->first();
342    }
343
344    /**
345     * Returns the distance between $this and another $item.
346     * May throw an exception if the tree has multiple roots and the 2 items
347     * have no common ancestor.
348     *
349     * @param static $item
350     * @return int
351     * @throws TreeException
352     */
353    public function getDistanceTo($item)
354    {
355        $commonAncestor = $this->findCommonAncestorWith($item);
356        if (!$commonAncestor) {
357            throw new TreeException('The items have no common ancestor!');
358        }
359        $depths = $commonAncestor->descendants()->includingSelf()->whereKey([$this->getKey(), $item->getKey()])
360                ->toBase()->select($this->getClosureTable() . '.depth')
361                ->get()->pluck('depth');
362        return $depths->sum();
363    }
364
365    /**
366     * Return the depth of $this in the tree (0 is $this is a root).
367     *
368     * @return int
369     */
370    public function getDepth()
371    {
372        return $this->ancestors()->count();
373    }
374
375    /**
376     * Returns the depth of the subtree of which $this is a root.
377     *
378     * @return int
379     */
380    public function getSubtreeDepth()
381    {
382        return (int) $this->descendants()->orderByDepth('desc')->value('depth');
383    }
384
385
386    // =========================================================================
387    // QUERY SCOPES
388    // =========================================================================
389
390    protected function scopeWithClosure($query, $relation, $depth = null, $constraints = null)
391    {
392        $query->with([$relation => function ($query) use ($depth, $constraints) {
393            if ($depth !== null) {
394                $query->upToDepth($depth)->orderByDepth();
395            }
396            if ($constraints !== null) {
397                $constraints($query);
398            }
399        }]);
400    }
401
402    public function scopeWithAncestors($query, $depth = null, $constraints = null)
403    {
404        $this->scopeWithClosure($query, 'ancestors', $depth, $constraints);
405    }
406
407    public function scopeWithDescendants($query, $depth = null, $constraints = null)
408    {
409        $this->scopeWithClosure($query, 'descendants', $depth, $constraints);
410    }
411
412    public function scopeWithDepth($query, $as = 'depth')
413    {
414        $query->withCount('ancestors as ' . $as);
415    }
416
417    public function scopeWhereIsRoot($query, $bool = true)
418    {
419        $query->where($this->getParentForeignKeyName(), ($bool ? '=' : '!='), null);
420    }
421
422    public function scopeWhereIsLeaf($query, $bool = true)
423    {
424        if ($bool) {
425            $query->has('descendants', '=', 0);
426        } else {
427            $query->has('descendants');
428        }
429    }
430
431    public function scopeWhereHasChildren($query, $bool = true)
432    {
433        $this->scopeWhereIsLeaf($query, !$bool);
434    }
435
436    public function scopeWhereIsDescendantOf($query, $ancestor, $maxDepth = null, $includingSelf = false)
437    {
438        $ancestorId = ($ancestor instanceof Model) ? $ancestor->getKey() : $ancestor;
439        $closureTable = $this->getClosureTable();
440        $alias = $closureTable . uniqid();
441        $query->join(
442            $closureTable . ' as ' . $alias,
443            function ($join) use ($ancestorId, $maxDepth, $alias, $includingSelf) {
444                $join->on($alias . '.descendant_id', '=', $this->getQualifiedKeyName());
445                $join->where($alias . '.ancestor_id', '=', $ancestorId);
446                if (!$includingSelf) {
447                    $join->where($alias . '.depth', '>', 0);
448                }
449                if ($maxDepth !== null) {
450                    $join->where($alias . '.depth', '<=', $maxDepth);
451                }
452            }
453        );
454        $query->where($alias . '.ancestor_id', '!=', null);
455    }
456
457    public function scopeWhereIsAncestorOf($query, $descendant, $maxDepth = null, $includingSelf = false)
458    {
459        $descendantId = ($descendant instanceof Model) ? $descendant->getKey() : $descendant;
460        $closureTable = $this->getClosureTable();
461        $alias = $closureTable . uniqid();
462        $query->join(
463            $closureTable . ' as ' . $alias,
464            function ($join) use ($descendantId, $maxDepth, $alias, $includingSelf) {
465                $join->on($alias . '.ancestor_id', '=', $this->getQualifiedKeyName());
466                $join->where($alias . '.descendant_id', '=', $descendantId);
467                if (!$includingSelf) {
468                    $join->where($alias . '.depth', '>', 0);
469                }
470                if ($maxDepth !== null) {
471                    $join->where($alias . '.depth', '<=', $maxDepth);
472                }
473            }
474        );
475        $query->where($alias . '.ancestor_id', '!=', null);
476    }
477
478    // =========================================================================
479    // ADDITIONAL USEFUL METHODS
480    // =========================================================================
481
482    /**
483     * Shortcut method that returns a collection of the tree roots, with their
484     * eager-loaded descendants.
485     *
486     * @param int $depth
487     * @return \Illuminate\Database\Eloquent\Collection
488     */
489    public static function getTree($depth = null)
490    {
491        return static::query()->whereIsRoot()->withDescendants($depth)->get();
492    }
493
494    /**
495     * Return the depth of the tree (0 if the tree is flat).
496     *
497     * @return int
498     */
499    public static function getTreeDepth()
500    {
501        $instance = new static();
502        return $instance->getConnection()->table($instance->getClosureTable())->max('depth');
503    }
504
505    // =========================================================================
506    // INSERTING AND UPDATING CLOSURES
507    // =========================================================================
508
509    /**
510     * Check if the parent_id points to a descendant of the current object
511     * (and trigger an exception if it's the case).
512     *
513     * @throws TreeException
514     * @return void
515     */
516    protected function checkIfParentIdIsValid()
517    {
518        $parentKey = $this->getParentForeignKeyName();
519
520        if (is_null($this->$parentKey)) {
521            return;
522        }
523        if (
524            $this->$parentKey == $this->getKey()
525            || $this->newQuery()->whereKey($this->$parentKey)->whereIsDescendantOf($this->getKey())->exists()
526        ) {
527            throw new TreeException(
528                'Redundancy error! The item\'s parent can\'t be the item itself or one of its descendants.'
529            );
530        }
531    }
532
533    /**
534     * @param  bool  $preserveSubtree
535     * @return int
536     */
537    protected function deleteClosures($preserveSubtree = false)
538    {
539        $closureTable = $this->getClosureTable();
540        $id = $this->getKey();
541
542        return $this->getConnection()->table($closureTable, 'closures')
543            ->join("$closureTable as descendants", 'closures.descendant_id', '=', 'descendants.descendant_id')
544            ->where('descendants.ancestor_id', $id)
545            ->when($preserveSubtree, function ($query) {
546                $query->whereColumn('closures.depth', '>', 'descendants.depth');
547            })
548            ->delete();
549    }
550
551    /**
552     * Re-calculate the closures when the parent_id has changed on a single item.
553     *
554     * @param bool $deleteOldClosures Can be set to false if it's a new item
555     */
556    public function refreshClosures($deleteOldClosures = true)
557    {
558        $connection = $this->getConnection();
559        $grammar = $connection->getQueryGrammar();
560
561        $connection->transaction(function () use ($deleteOldClosures, $connection, $grammar) {
562
563            $closureTable = $this->getClosureTable();
564            $parentKey = $this->getParentForeignKeyName();
565            $id = $this->getKey();
566            $newParentId = $this->$parentKey;
567
568            // Delete old closures:
569            if ($deleteOldClosures) {
570                $this->deleteClosures(true);
571            }
572
573            // Create self-closure if needed:
574            $connection->table($closureTable)->insertOrIgnore([
575                'ancestor_id' => $id,
576                'descendant_id' => $id,
577                'depth' => 0,
578            ]);
579
580            // Create new closures:
581            if ($newParentId) {
582                // INSERT INTO $closureTable (ancestor_id, descendant_id, depth)
583                // SELECT ancestors.ancestor_id, descendants.descendant_id, ancestors.depth + descendants.depth + 1
584                //     FROM $closureTable AS ancestors
585                //     CROSS JOIN $closureTable AS descendants
586                //     WHERE ancestors.descendant_id = $newParentId
587                //         AND descendants.ancestor_id = $id
588                $select = $connection
589                    ->table($closureTable, 'ancestors')
590                    ->crossJoin("$closureTable AS descendants")
591                    ->where('ancestors.descendant_id', '=', $newParentId)
592                    ->where('descendants.ancestor_id', '=', $id)
593                    ->select(
594                        'ancestors.ancestor_id',
595                        'descendants.descendant_id',
596                        $connection->raw(sprintf(
597                            '%s + %s + 1',
598                            $grammar->wrap('ancestors.depth'),
599                            $grammar->wrap('descendants.depth')
600                        ))
601                    );
602                $connection->table($closureTable)->insertUsing(['ancestor_id', 'descendant_id', 'depth'], $select);
603            }
604        });
605    }
606
607    /**
608     * Deletes the closures for the item. Assumes that the item has no children.
609     */
610    protected function deleteClosuresForLeaf()
611    {
612        $closureTable = $this->getClosureTable();
613        $this->getConnection()->table($closureTable)->where('descendant_id', $this->getKey())->delete();
614    }
615}