CODEWITHSUNDEEP
phparraysvalidationrecursionmultidimensional-array
Dorin Niscu
Dorin Niscu

Reputation: 721

Validate PHP multidimensional array (nestable) to avoid infinite loop

I am using https://github.com/dbushell/Nestable library.

Everything works fine using the library but I want to validate the request as an extra protection to avoid infinite loop if someone will force the request manually (hypothetical).

I was wondering if someone knows an elegant way to get this without doing another recursive function to check if the parent becomes a child at some point.

Example:

$data = [
    [
        "id" => 1,
    ],
    [
        *"id"       => 2,*
        "children" => [
            [
                "id" => 3,
            ],
            [
                "id" => 4,
            ],
            [
                "id"       => 5,
                "children" => [
                    [
                        "id" => 6,
                    ],
                    [
                        "id" => 7,
                    ],
                    [
                        "id" => 8,
                        "children" => [
                            [
                                *"id" => 2,*
                            ],
                            [
                                "id" => 10,
                            ],
                        ],
                    ],
                ],
            ],
            [
                "id" => 11,
            ],
            [
                "id" => 12,
            ],
        ],
    ],
    [
        "id" => 13,
    ],
    [
        "id" => 14,
    ],

];

nestableLinks($data);

/**
 * Nestable links.
 *
 * @param      $links
 * @param null $parent_id
 * @param int  $weight
 */
function nestableLinks($links, $parent_id = NULL, $weight = 0)
{
    foreach ($links as $link) {
        $weight++;

        var_dump(['id' => $link['id'], 'parent_id' => $parent_id, 'weight' => $weight]);

        if (array_key_exists('children', $link)) {
            nestableLinks($link['children'], $link['id']);
        }
    }
}

Upvotes: 0

Views: 137

Answers (3)

sevavietl
sevavietl

Reputation: 3812

You can use RecursiveArrayIterator. It has to be extended to match our needs:

class NestedRecursiveArrayIterator extends RecursiveArrayIterator
{
    public function hasChildren()
    {
        return isset($this->current()['children']);
    }

    public function getChildren()
    {
        return new static($this->current()['children']);
    }
}

Having this class we can iterate over it with RecursiveIteratorIterator:

$iterator = new RecursiveIteratorIterator(
    new NestedRecursiveArrayIterator($data),
    RecursiveIteratorIterator::SELF_FIRST
);

$ancestors = [];
foreach ($iterator as $datum) {
    if ($iterator->getDepth() === 0) {
        $ancestors = [];
    }

    if (isset($ancestors[$datum['id']])) {
        // Invalid child that will cause loop.
        var_dump($datum);
    }

    $ancestors[$datum['id']] = true;
}

Here is working demo.

Upvotes: 1

Sylwester
Sylwester

Reputation: 48745

Use an array indexed on id and insert as you walk the tree. If you find a node already in there you have a loop and return false.

When all children have returned true you return true. One false result you return that early.

This can be done recursively or you can use another array as node stack. The choice depends on how deep you expect the three to get.

Upvotes: 0

Shoaib Zafar
Shoaib Zafar

Reputation: 312

Your logic looks fine. Alternatively, you can use array_walk_recursive rather than defining your own iteration logic which will automatically iterate every array in the variable.

$data = [["id"=>1,],["id"=>2,"children"=>[["id"=>3,],["id"=>4,],["id"=>5,"children"=>[["id"=>2,],["id"=>7,],["id"=>8,],],],["id"=>9,],["id"=>10,],],],["id"=>11,],["id"=>12,],];

function test_print($item, $key) {
    echo "key $key holds: $item\n";
}
array_walk_recursive($data, 'test_print');

Upvotes: 0

Related Questions