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