PHP Programming - Detecting Recursion

Author

Detecting Recursion

Thomas Mlynarczyk

2005-10-18, 6:57 pm

Hi,

Say I have an array containing a reference to itself:
$myArray = array();
$myArray['self'] =& $myArray;
How can I, looping iteratively through the array, detect the fact that
$myArray['self'] will "take" me to where I have already been? The print_r()
and var_dump() functions print *RECURSION* in such a case (though only after
the "second round"). Setting a flag seems to be the only solution, but I
don't want to modify the array in question - I want to produce a visual
representation of its contents like var_dump(), but formatted to my taste. I
had considered parsing the output of var_dump(), but first, that format
might change in a future version of PHP and second, an array key might be a
string resembling part of the output (like $myArray['["myArray"]=>']), which
seems to be difficult to detect by the parsing code.

Is there another way of doing this?

Greetings,
Thomas

Henk Verhoeven

2005-10-18, 6:57 pm

Hi Thomas,

Generally, for recursion detection you use a "Set". You use a either
breadth first search or a depth first search algorithm to go through the
graph of data structures, collection and/or objects and put every node
into the Set (google for these algorithms, or for backtracking
algorithm). Before every next step you also check if the next node is
already in the Set. The Set can answer this question very fast becuase
it uses Hashing. If it is in the set, skip it.

Your problem: php has no Set. But you can use an associative array and
add unique keys for each node, with some not-null value as value.
Something like this:
$visitedKeys[getUniqueKey($node)] = true;
Now you can check wheather the node was already visited by:
isSet($visitedKeys[getUniqueKey($node)])

I bet associative arrays use hasing, just like Sets (lookup is so fast).
Of course you do have to program the getUniqueKey function to work with
your actual data ;-)

Greetings,

Henk Verhoeven,
www.phpPeanuts.org

Thomas Mlynarczyk wrote:

> Hi,
>
> Say I have an array containing a reference to itself:
> $myArray = array();
> $myArray['self'] =& $myArray;
> How can I, looping iteratively through the array, detect the fact that
> $myArray['self'] will "take" me to where I have already been? The print_r()
> and var_dump() functions print *RECURSION* in such a case (though only after
> the "second round"). Setting a flag seems to be the only solution, but I
> don't want to modify the array in question - I want to produce a visual
> representation of its contents like var_dump(), but formatted to my taste. I
> had considered parsing the output of var_dump(), but first, that format
> might change in a future version of PHP and second, an array key might be a
> string resembling part of the output (like $myArray['["myArray"]=>']), which
> seems to be difficult to detect by the parsing code.
>
> Is there another way of doing this?
>
> Greetings,
> Thomas
>
>

Thomas Mlynarczyk

2005-10-19, 6:56 pm

Also sprach Henk Verhoeven:

> Your problem: php has no Set. But you can use an associative array and
> add unique keys for each node, with some not-null value as value.
> Something like this:
> $visitedKeys[getUniqueKey($node)] = true;
> Now you can check wheather the node was already visited by:
> isSet($visitedKeys[getUniqueKey($node)])

Thank you for your suggestion. The only problem is the getUniqueKey()
function. The only way I can think of is adding another special index to
each (sub-)array, but then I would a) modify the array and b) still not know
how to find a suitable key name (must be the same for all and one that is
not used in the tree structure). It is not possible to directly access the
symbol table?

Greetings,
Thomas

Henk Verhoeven

2005-10-20, 6:56 pm

Thomas,

Maybe debug_zval_dump() can be of use for getting an unique key? See
http://www.php.net/manual/en/functi...g-zval-dump.php
(the part about refcount is confusing, but maybe you do only need the
first (string(11)) part of the output)

Greetings,

Henk Verhoeven,
www.phpPeanuts.org.

Thomas Mlynarczyk wrote:
> Also sprach Henk Verhoeven:
>
>
>
>
> Thank you for your suggestion. The only problem is the getUniqueKey()
> function. The only way I can think of is adding another special index to
> each (sub-)array, but then I would a) modify the array and b) still not know
> how to find a suitable key name (must be the same for all and one that is
> not used in the tree structure). It is not possible to directly access the
> symbol table?
>
> Greetings,
> Thomas
>
>

Thomas Mlynarczyk

2005-10-21, 6:56 pm

Also sprach Henk Verhoeven:

> Maybe debug_zval_dump() can be of use for getting an unique key? See
> http://www.php.net/manual/en/functi...g-zval-dump.php
> (the part about refcount is confusing, but maybe you do only need the
> first (string(11)) part of the output)

An interesting function - especially because of the refcount. I do not quite
see yet how I could use it for getting a unique key (the point being to get
different values for different things even if they are identical copies),
but I will have a closer look at this function. Thanks for the suggestion.

Greetings,
Thomas

Henk Verhoeven

2005-10-23, 6:56 pm

Thomas,

If the reference count does not help you, I think you have two options
here:

1) under each non-unique key, put another array and put all copies in
that array. To check if a node is already visited, get its key, then
search sequentially through the array that is under the key to see if
one of the nodes in there is identical to the currently visited one.
However, you need a way to distinguish copies from references. AFAIK you
can only do this in php4 by changing the value of one variable and see
if the other variable changes too. But then you have to put (or change)
the original value back, and all this without copying (i have not
figured out how to do that, don't know if it can be done at all). In php
5 you can use === with objects, but not with arrays. Of course if you
have many copies of some of the nodes, the sequential searching can
become very resource-consuming (exponentially slower with the number of
copies of the same node).

2) *make* the copies different. As described on the manual page, values
that are formally copies are actually kept as references as long as they
are unchanged. Assuming only arrays and objects can serve as nodes in
the graph, if you can change each node and then change it back to its
original state, php will create a real copy for each, and probably not
undo that if you change it back to its original state. Real copies
probably have different first parts of the debug_zval_dump() values. So
after you have modified each node, you can store its unique key for
lookup to detect recursion. Of course this will be expensive (slow) if
there are many copies to be "realized", but the slowdonwn will be liniar
with the number of copies to realize, so with large searches with many
copies of the same node this will be a lot faster then option 1)

Maybe you can even combine these strategies, but that may complicate
things more then you like.

Hope this helps.

Greetings,

Henk Verhoeven,
www.phpPeanuts.org.

Thomas Mlynarczyk wrote:
> Also sprach Henk Verhoeven:
>
>
>
>
> An interesting function - especially because of the refcount. I do not quite
> see yet how I could use it for getting a unique key (the point being to get
> different values for different things even if they are identical copies),
> but I will have a closer look at this function. Thanks for the suggestion.
>
> Greetings,
> Thomas
>
>

Thomas Mlynarczyk

2005-10-26, 7:55 am

Also sprach Henk Verhoeven:

> 1) under each non-unique key, put another array and put all copies in
> that array. To check if a node is already visited, get its key, then
> search sequentially through the array that is under the key to see if
> one of the nodes in there is identical to the currently visited one.

Sounds like a lot of trouble for a recursion check. :-(

> However, you need a way to distinguish copies from references.

Ay, there's the rub.

> you can only do this in php4 by changing the value of one variable
> and see if the other variable changes too.

Actually, I'd have to check more or less *all* variables to see if there's
one that changes accordingly.

> In php 5 you can use === with objects,

Like "===" would mean "is_reference" and "!==" would mean "is_copy"? That's
great news! :-)

> but not with arrays.

I knew there was a catch... :-(

Hm, so it seems there is no real quick & easy solution for this problem. For
the moment, I think I will stick with a workaround: Limiting the maximum
nesting level while going through the data. At least this will prevent
system hangs. Later I can try to improve my script using your suggestions.

Thanks again for your help!

Greetings,
Thomas

Sponsored Links