Validate PHP multidimensional array (nestable) to avoid infinite loop

Question

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']);
        }
    }
}

sevavietl · Accepted Answer · 2017-09-20 09:44:32Z

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.

Shoaib Zafar · Accepted Answer · 2017-09-20 07:43:34Z

0

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');

answered Sep 20, 2017 at 7:43

Shoaib Zafar

3122 silver badges8 bronze badges

Comments

Sylwester · Accepted Answer · 2017-09-20 07:46:56Z

0

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.

answered Sep 20, 2017 at 7:46

Sylwester

48.9k4 gold badges52 silver badges83 bronze badges

Collectives™ on Stack Overflow

Validate PHP multidimensional array (nestable) to avoid infinite loop

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related