Section tree of unlimited nesting and URL

In this article, we will consider one of the possible approaches to generating a full path to a partition, which can have unlimited nesting in other partitions, as well as quickly getting the desired partition along a given path.

Imagine that we are programming an online store in which there should be a tree of various sections, and there should also be “pleasant” links to sections that would include all sections. Example http://example.com/catalog/category/sub-category.

Sections

The most obvious option is to create a parent parent_idrelationship through an attribute and relationship parent.

class Category extends Model
{
    public function parent()
    {
        return $this->belongsTo(self::class);
    }
}

Also, our model has an attribute slug- a stub, which reflects the section in the URL. It can be generated from the name, or manually specified by the user. Most importantly, the stub must pass the validation rule alphadash(that is, consist of letters, numbers and signs -, _), and also be unique within the parent section. For the latter, it is enough to create a unique index in the database (parent_id, slug).

To get a link to a section, you need to pull all of his parents in sequence. The URL generation function looks something like this:

public function getUrl()
{ 
    $url = $this->slug;
    $category = $this;
    while ($category = $category->parent) {
        $url = $category->slug.'/'.$url;
    }
    return 'catalog/'.$url;
}

The more the section has ancestors, the more queries will be executed in the database. But this is only part of the problem. How to create a route to the section? Let's try this:

$router->get('catalog/{category}', ...);

Feed the browser a link http://example.com/catalog/category. The route will work. Now the following link: http://example.com/catalog/category/sub-category. The route will no longer work, because backslash is a parameter delimiter. Hmm, then add another parameter and make it optional:

$router->get('catalog/{category}/{subcategory?}', ...);

This route will already work, but if you add another subsection to the URL, then nothing will work. And the problem is that the number of such subsections is not limited.

Further, in order to get the necessary section from the database, you must first find the section with the identifier category, then, if specified, the subsection subcategory, etc. All this causes inconvenience and loads the server more heavily, the number of requests is proportional to the number of subsections.

Optimization

The extension for laravel kalnoy / nestedset will help us greatly reduce the number of requests . It is designed to simplify work with trees.

Installation

Installation is very simple. First you need to install the extension through composer:

composer require kalnoy/nestedset

The model will need two additional attributes that must be added in the new migration:

Schema::table('categories', function (Blueprint $table) {
    $table->unsignedInteger('_lft');
    $table->unsignedInteger('_rgt');
});

Now you just need to delete the old relationships parentand children, if they were set, as well as add trait Kalnoy\Nestedset\NodeTrait. After the update, our model looks like this:

class Category extends Model
{
    use Kalnoy\Nestedset\NodeTrait;
}

However, the value _lftand _rgtare not filled to make things work, was the final touch:

Category::fixTree();

This code will fix the tree based on the attribute parent_id.

Simplified generation

The URL generation process looks like this:

public function getUrl()
{
    // Получаем заглушки всех предков
    $slugs = $this->ancestors()->lists('slug');
    // Добавляем заглушку самого раздела
    $slugs[] = $this->slug;
    // И склеиваем это все
    return 'catalog/'.implode('/', $slugs);
}

Much easier, right? No matter how many descendants this section has, they will all be received in one request. But the routes are not so simple. It still fails to get the chain of sections in one request.

Routes

Task number 1. How to set a route to a section indicating all its ancestors in a link?

Task number 2. How to get all the way to the desired section in one request?

Route description

The answer to the first task: use the entire path as a route parameter .

$router->get('catalog/{path}', 'CategoriesController@show')
       ->where('path', '[a-zA-Z0-9/_-]+');

We simply indicate that the parameter {path}can contain not only the usual string, but also a backslash. Thus, this parameter captures immediately the entire path that follows the control word catalog.

Now in the input controller we get only one parameter, but we can divide it into all subsections:

public function show($path)
{
    $path = explode('/', $path);
}

However, this did not simplify the task of obtaining the section indicated in the link.

A bunch of paths with a section

So how to optimize this process? Store the full path for each partition in the database .

Suppose there is such a simple tree:

- Category
-- Sub category
--- Sub sub category

The following paths will correspond to these sections:

- category
-- category/sub-category
--- category/sub-category/sub-sub-category

Then the desired category can be obtained very simply:

public function show($path)
{
    $category = Category::where('path', '=', $path)->firstOrFail();
}

Now we save in the database what was previously generated for the link, and link generation is now greatly simplified:

// Генерация пути
public function generatePath()
{
    $slugs = $this->ancestors()->lists('slug');
    $slugs[] = $this->slug;
    $this->path = implode('/', $slugs);
    return $this;
}
// Получение ссылки
public function getUrl()
{
    return 'catalog/'.$this->path;
}

If you look closely at the list of paths in the example, you will notice that the path for each model is this путь-родителя/заглушка-модели. Therefore, path generation can be further optimized:

public function generatePath()
{
    $slug = $this->slug;
    $this->path = $this->isRoot() ? $slug : $this->parent->path.'/'.$slug;
    return $this;
}

The following problem remains. When the stub of one section is updated, or the section changes the parent, the links of all its descendants should be updated. The algorithm is simple: get all descendants and generate a new path for them. The following is the descendant update method:

public function updateDescendantsPaths()
{
    // Получаем всех потомков в древовидном порядке
    $descendants = $this->descendants()->defaultOrder()->get();
    // Данный метод заполняет отношения parent и children
    $descendants->push($this)->linkNodes()->pop();
    foreach ($descendants as $model) {
        $model->generatePath()->save();
    }
}

Let's consider in more detail.

In the first line we get all the descendants (in one request). defaultOrderapplies tree sorting here. Its meaning is that in the list each section will stand after its ancestor . The path building algorithm uses the parent, so it is necessary for the parent to update its path before the path of any of its descendants is updated.

The second line looks a little strange. Its meaning is that it fills the relation parent, which is used in the path generation algorithm. If you do not use this optimization, then each call generatePathwill execute a request to get the value of the relationship parent. WhereinlinkNodesIt works with a collection of partitions and does not make any queries to the database. Therefore, for this to work for the immediate children of the current section, you need to add it to the collection. Add the current section, bind all sections to each other and remove it.

Well, at the end, pass through all descendants and update their paths.

It remains only to decide when to call this method. Events are great for this:

1. Before saving the model, we check whether the attributes slugor changed parent_id. If changed, then call the method generatePath;
   
   
2. After the model has been successfully saved, we check whether the attribute has not changed path, and, if changed, we call the method updateDescendantsPaths.

protected static function boot()
{
    static::saving(function (self $model) {
        if ($model->isDirty('slug', 'parent_id')) {
            $model->generatePath();
        }
    });
    static::saved(function (self $model) {
        // Данная переменная нужна для того, чтобы потомки не начали вызывать 
        // метод, т.к. для них путь также изменится
        static $updating = false;
        if ( ! $updating && $model->isDirty('path')) {
            $updating = true;
            $model->updateDescendantsPaths();
            $updating = false;
        }
    });
}

results

The advantages of this approach:

• Generate section link instantly
• Quickly get a section along the way

Disadvantages:

• The paths are stored in the database, which slightly increases the size of the table
• Changing the stub of one section entails updating the paths of all descendants

In fact, the advantages far outweigh the shortcomings in view of the fact that you need to generate links and get sections much more often than updating stubs; and the overspending of space in ways is scanty.

Goods

Consider approaches to generating product links that include a section path. For example: http://example.com/catalog/category/sub-catagory/product. The main problem here is to form the correct route.

The product, like the section, has a stub that can be specified manually, or generated based on the name. It is important that this stub must be unique within the partition so that there are no conflicts. It is best to create a unique index in the database (category_id, slug).

Let's try the simplest option and consider the following routes:

// Маршрут до раздела
$router->get('catalog/{path}', function ($path) {
    return 'category = '.$path;
})->where('path', '[a-zA-Z0-9\-/_]+');
// Маршрут до товара
$router->get('catalog/{category}/{product}', function ($category, $product) {
    return 'category = '.$category.'
product = '.$product;
})->where('category', '[a-zA-Z0-9\-/_]+');

The first route should already be familiar - this is the section output route. The second route is almost the same, only at the end is added another parameter that should indicate a specific product in this section. If we try to enter the above example into the browser line, we get the following:

category = category/sub-category/product

The first route worked; not quite what was expected to be received. That's because the first route will fire for any line that starts with a keyword catalog. Need to swap routes. Then we get:

category = category/sub-category
product = product

Excellent! This is already better, but that’s not all. Let's try this the URL: http://example.com/catalog/category/sub-category. We get the following:

category = category
product = sub-category

Now only the route to the goods is triggered. It is necessary to clearly separate the product stub from the stub section. To do this, you can use some kind of prefix / postfix. For example, add at the end or at the beginning of the stub of a product its numerical identifier: It

http://example.com/catalog/category/sub-category/123-product

remains only to add a restriction on the parameter {product}:

$router->get(...)->where('product', '[0-9]+-[a-zA-Z0-9_-]+');

In this case, the generation of the product stub looks like this:

$product->slug = $product->id.'-'.str_slug($product->name);

Link Generation:

$url = 'catalog/'.$product->category->path.'/'.$product->slug;

Receiving goods in the controller:

public function show($categoryPath, $productSlug)
{
    // Сначала находим раздел по пути
    $category = Category::where('path', '=', $categoryPath)->firstOrFail();
    // Затем в этом разделе ищем товар с указанной заглушкой
    $product = $category->products()
                        ->where('slug', '=', $productSlug)
                        ->firstOrFail();
}

Here, however, a condition arises: stub sections should not begin with a number. Otherwise, the route to the goods will be triggered, instead of the route to the section.

You can use some kind of static prefix, for example p-:

http://example.com/catalog/category/sub-category/p-product

$router->get('catalog/{category}/p-{product}', ...);

$product->slug = str_slug($product->name);

$url = 'catalog/'.$product->category->path.'/p-'.$product->slug;

The controller code remains as in the previous case.

The last option is the most difficult. Its essence is to store links to sections and products in a separate table.

The model looks something like this:

class Url extends Model
{
    // Полиморфное отношение
    public function model()
    {
        return $this->morphTo();
    }
}

With this approach, only one route is enough:

$router->get('catalog/{path}', function ($path) {
    $url = Url::findOrFail($path);
    // Извлекаем модель используя отношение
    $model = $url->model;
    if ($model instanceof Product) {
        return $this->renderProduct($model);
    }
    return $this->renderCategory($model);
})
->where('path', '[a-zA-Z0-9\-/_]+');

The model Urlhas a polymorphic relationship with other models and stores full paths to them. What does it give:

• No prefixes / postfixes needed for product
• You can store previous versions of URLs and redirect them to new ones, i.e. SEO does not suffer when changing page address
• It is not necessary to be limited only to sections / goods, you can store any other resource

This approach is described very conditionally as food for thought. Perhaps it will even pull on a separate extension.

conclusions

In this article, we examined the main expansion options kalnoy/nestedset, as well as approaches to forming links to sections and products in the case where the depth of sections is not limited.

As a result, a method was obtained that allows you to generate links without making queries in the database, as well as receive sections from the link in one request.

As an alternative to storing paths in the database, you can use the caching of generated links. Then there is no need to update links and just reset the cache.