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, 02:33:59 schrieb David Kastrup:
>> Reinhold Kainhofer <address@hidden> writes:
>> > 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.
>
> Huh? So, you are saying that you can determine in g() whether the evaluation 
> of f will terminate, without evaluating f?
>
> int g(int i) {
>   // Please determine here, whether this call will result in a 
>   // loop or terminate, without evaluating f:
>   return f(i);
> }
>
> int f(int i) {
>   if (i==1) 
>     return 1;
>   else if (i%2 == 0)
>     return g(i/2);
>   else 
>     return g(3*i+1);
> }

No, since f or g do _not_ traverse a structure.

> This is exactly the situation with markup interpretation: g is in
> lilypond the interpret-markup function, while f can be any markup
> function, which might call interpret-markup again for sub-markups.

And?  The point is that interpret-markup is called on markups, and you
can just take note on what markups and partial markups you get called,
and if you reach them again, you abort.

> If we don't want to modify all markup functions, we can only adjust g.
> However, due to the recursion, I don't see how we can step through the
> nodes with two different speeds.

We don't.  We just push each node as we pass it into a FIFO, and every
second push, we take one value out of the FIFO, and if it would be the
same as the one we were going to push, we abort.

> What makes the situation in lilypond even worse is that a markup
> function can invoke interpret-markup multiple times, so we have a call
> tree. And in markup functions we have more than one argument
> i. Rather, we have three arguments (layout, props, markup), which
> might or might not influence the result.

I don't think we really need to check more than markup: a recursion
terminated by property changes is too clever to really be required to
work.  In fact, if properties stack up in synch with markup, the
probabily that we don't have an infinite recursion on our hand is rather
low, even though it never passes the same property set twice and could,
in theory, decide for a certain property set that it reached recursion
bottom.

>> "cycle" and "loop" are two different names for the same thing.
>
> Actually, I was also thinking about cases where we are not in a loop,
> but which still don't terminate.

See above: infinite descent with changing values is impossible to
interpret.

-- 
David Kastrup