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

[David Kastrup]

Reinhold Kainhofer <address@hidden> writes:

> Am Thursday, 15. September 2011, 01:50:34 schrieb 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.
>
> The only problem is that we never get to the elements' values.

Who is interested in the values?  They are not required for loop
detection.

> We never even really have a tree to traverse. The elements are only
> created by interpret-markup, which will already cause the infinite
> loop.

I don't get your point.  Whether the tree is explicit or implicit, the
nodes are recognizable before evaluation.

> Without running interpret-markup on a markup we don't know anything
> about its contents (because the markup function might create anything
> it wants), and as soon as we are running interpret-markup on a markup,
> we might end up in a cycle.

And the topic of this issue is detecting this cycle.

> So, I wouldn't characterize this as a loop detection, but rather
> determining whether an arbitrary recursion ever terminates...

"cycle" and "loop" are two different names for the same thing.

-- 
David Kastrup