Recursive Relationship

[tteze]

Hi I made a Recursive Relation. I can use eager loading and whereHas methods on all parents or children of a model.

Exemple : If I have a table with this four tuples (id, parent_id) (1, null) (2, 1) (3, 2) (4, null)

MyModel::find(3)->parents will return models with ids [1, 2] MyModel::find(1)->children will return models with ids [2, 3]

Actually I'm declaring my relation like this :

  /**
   * @codeCoverageIgnore
   */
   public function parents()
   {
       return new BelongsToRecursive($this->newQuery(), $this, 'parent_id', 'id');
   }

   /**
    * @codeCoverageIgnore
    */
    public function children()
    {
        return new BelongsToRecursive($this->newQuery(), $this, 'id', 'parent_id');
    }

then I'm able to do $model->parents, $model->parents()->..., MyModel::with('parents'), MyModel::whereHas('parents', function ($query) {...}), etc...

It's not perfect and I think many things can be discuss but it may be usefull when dealing with recursive models.

Here's the class declaration :

<?php

namespace App\Relations;

use Illuminate\Database\Eloquent\Builder;
use Illuminate\Database\Eloquent\Collection;
use Illuminate\Database\Eloquent\Model;
use Illuminate\Database\Eloquent\Relations\Relation;
use Illuminate\Support\Str;

class BelongsToRecursive extends Relation
{
    /**
     * The foreign key of the parent model.
     *
     * @var string
     */
    protected $foreignKey;

    /**
     * The local key of the parent model.
     *
     * @var string
     */
    protected $key;

    /**
     * Used for unique table names in the recursive query
     *
     * @var int
     */
    protected static $selfJoinCount = 0;

    /**
     * Create a new has one or many relationship instance.
     *
     * @param  \Illuminate\Database\Eloquent\Builder  $query
     * @param  \Illuminate\Database\Eloquent\Model  $parent
     * @param  string  $foreignKey
     * @param  string  $key
     * @return void
     */
    public function __construct(Builder $query, Model $parent, $foreignKey, $key)
    {
        $this->key = $key;
        $this->foreignKey = $foreignKey;

        parent::__construct($query, $parent);
    }

    /**
     * Set the base constraints on the relation query.
     *
     * @return void
     */
    public function addConstraints()
    {
        if (static::$constraints) {
            $this->whereChildren([$this->getChildKey()]);
        }
    }

    /**
     * @param array $ids
     */
    public function whereChildren(array $ids)
    {
        $rec = $this->related->newQuery()->select('father.*')
            ->fromRaw("{$this->parent->getTable()} as father, cte as child")
            ->whereColumn("child.$this->foreignKey", "father.$this->key");

        $rec = $this->related->newQuery()->whereIn($this->key, $ids)->union($rec->getQuery());

        $query = $this->related->newQueryWithoutScopes()->fromRaw(
            "(with recursive cte as ({$rec->toSql()}) select * from cte) as rec",
            $rec->getBindings()
        )->select($this->key);

        $this->query->whereIn($this->key, $query);
    }

    /**
     * Set the constraints for an eager load of the relation.
     *
     * @param array $models
     * @return void
     */
    public function addEagerConstraints(array $models)
    {
        $this->whereChildren($this->getKeys($models, $this->foreignKey));
    }

    /**
     * Initialize the relation on a set of models.
     *
     * @param array $models
     * @param string $relation
     * @return array
     */
    public function initRelation(array $models, $relation)
    {
        foreach ($models as $model) {
            $model->setRelation($relation, $this->related->newCollection());
        }

        return $models;
    }

    /**
     * Match the eagerly loaded results to their parents.
     *
     * @param array $models
     * @param \Illuminate\Database\Eloquent\Collection $results
     * @param string $relation
     * @return array
     */
    public function match(array $models, Collection $results, $relation)
    {
        $dictionnary = $results->keyBy($this->key);

        foreach ($models as $model) {
            $parents = $this->related->newCollection($this->getParents($model, $dictionnary));
            $model->setRelation($relation, $parents);
        }

        return $models;
    }

    /**
     * @param $model
     * @param $dictionnary
     * @return array
     */
    private function getParents(Model $model, Collection $dictionnary)
    {
        $parent = $dictionnary->get($model->{$this->foreignKey});
        return $parent ? $this->getParents($parent, $dictionnary) + [$parent] : [];
    }

    /**
     * Get the results of the relationship.
     *
     * @return mixed
     */
    public function getResults()
    {
        return ! is_null($this->getChildKey())
            ? $this->query->get()
            : $this->related->newCollection();
    }

    /**
     * Get the key value of the parent's local key.
     *
     * @return mixed
     */
    public function getChildKey()
    {
        return $this->parent->getAttribute($this->foreignKey);
    }

    /**
     * @param Builder $query
     * @param Builder $parentQuery
     * @param array $columns
     * @return Builder|\Illuminate\Database\Query\Builder
     */
    public function getRelationExistenceQuery(Builder $query, Builder $parentQuery, $columns = ['*'])
    {
        $rec = $parentQuery->getModel()->newQuery()
            ->select(['children.*', "fathers.ancestor"])
            ->fromRaw("{$this->parent->getTable()} as children, cte as fathers")
            ->whereColumn("children.$this->key", "fathers.$this->foreignKey");

        $rec = $this->parent->newQuery()
            ->select(['*', "$this->foreignKey as ancestor"])
            ->fromRaw("{$this->parent->getTable()} as related")
            ->union($rec->getQuery());

        $hash = 'related_self_' . static::$selfJoinCount++;

        $asRec = "(with recursive cte as ({$rec->toSql()}) select * from cte) as $hash";

        $query->whereColumn("$hash.ancestor", "{$this->parent->getTable()}.$this->foreignKey")
            ->getModel()
            ->setTable($hash);

        return $query->select($columns)->fromRaw($asRec, $rec->getBindings());
    }
}

and here unit tests :

<?php

namespace Tests\Unit\Relations;

use App\Relations\BelongsToRecursive;
use Illuminate\Database\Eloquent\Builder;
use Illuminate\Database\Eloquent\Collection;
use Illuminate\Database\Eloquent\Relations\Relation;
use Tests\Fake\FakeModel;
use Tests\TestCase;

/**
 * @coversDefaultClass \App\Relations\BelongsToRecursive
 */
class BelongsToRecursiveTest extends TestCase
{
    /**
     * @var Builder
     */
    private $query;

    protected function setUp(): void
    {
        parent::setUp();

        $this->query = FakeModel::query();
    }

    /**
     * @covers ::addConstraints
     * @covers ::whereChildren
     */
    public function testAddConstraints()
    {
        $this->newRelation()->select('col');

        $this->assertEquals($this->getWhereChildrenQuery(), $this->query->toSql());
    }

    /**
     * @covers ::addEagerConstraints
     * @covers ::whereChildren
     */
    public function testAddEagerConstraints()
    {
        Relation::noConstraints(function () {
            $this->newRelation()->select('col')->addEagerConstraints([$this->query->getModel()]);
        });

        $this->assertEquals($this->getWhereChildrenQuery(), $this->query->toSql());
    }

    /**
     * @covers ::initRelation
     */
    public function testInitRelation()
    {
        $model = new FakeModel();

        $this->newRelation()->initRelation([$model], 'test');

        $this->assertInstanceOf(Collection::class, $model->getRelation('test'));
    }

    /**
     * @covers ::match
     * @covers ::getParents
     */
    public function testMatch()
    {
        $model = (new FakeModel())->setAttribute('id', 1);

        $related = (new FakeModel())->setAttribute('parent_id', 1);

        $this->newRelation()->match([$model], Collection::make([$related]), 'test');

        $this->assertInstanceOf(Collection::class, $model->getRelation('test'));
    }

    /**
     * @covers ::getResults
     */
    public function testGetResults()
    {
        $this->assertInstanceOf(Collection::class, $this->newRelation()->getResults());
    }

    /**
     * @covers ::getChildKey
     */
    public function testGetChildKey()
    {
        $relation = $this->newRelation();

        $relation->getModel()->setAttribute('parent_id', 1);

        $this->assertEquals(1, $relation->getChildKey());
    }

    /**
     * @covers ::getRelationExistenceQuery
     */
    public function testGetRelationExistenceQuery()
    {
        $whereHas = FakeModel::query()->where('col_a', 1);

        $sql = "select `col` from (with recursive cte as ((select *, `parent_id` as `ancestor` from fake_models as related)"
            ." union (select `children`.*, `fathers`.`ancestor` from fake_models as children, cte as fathers where `children`.`id` = `fathers`.`parent_id`))"
            ." select * from cte) as related_self_0 where `col_a` = ? and `related_self_0`.`ancestor` = `fake_models`.`parent_id`";

        $this->assertEquals($sql, $this->newRelation()->getRelationExistenceQuery($whereHas, FakeModel::query(), 'col')->toSql());
    }

    /**
     * @return string
     */
    private function getWhereChildrenQuery()
    {
        return "select `col` from `fake_models` where `id` in (select `id` from (with recursive cte as ((select * from `fake_models` where `id` in (?))"
            . " union (select `father`.* from fake_models as father, cte as child where `child`.`parent_id` = `father`.`id`)) select * from cte) as rec)";
    }

    /**
     * @return BelongsToRecursive
     */
    private function newRelation()
    {
        return new BelongsToRecursive($this->query, $this->query->getModel(), 'parent_id', 'id');
    }
}

[staudenmeir]

I've also created a package for recursive relationships: https://github.com/staudenmeir/laravel-adjacency-list