Re: Fix 380: Try to auto-detect cyclic references in header fields (issue 4951073)

[David Kastrup]

address@hidden writes:

> On 2011/09/13 18:53:55, hanwenn wrote:
>> have you thought of fixing this generically instead?
>
>> You could the hare/tortoise algorithm to detect cycles in any markup,
>> and could run that on the entry point (not the recursive function)
>> for evaluating markups to stencils.
>
> Actually, I fail to see how I can use the algorithm to detect cycles in
> markups. First, a markup is a tree and a recursive function rather tan a
> chained function application, so the algorithm would have to run on each
> branch.

You traverse a tree in a certain order, and for the purpose of loop
detection, you can consider the elements you reach as a list.  Now
traversing at two different speeds implies requiring two stacks
(coroutines anyone?), or alternatively keeping the slow traversal linear
by just letting the fast traversal push its elements into a FIFO and let
the slow traversal pop them out again.

-- 
David Kastrup