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

[Reinhold Kainhofer]

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

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.

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

I don't see any way to solve this generically, short of doing fundamental 
changes in how markups are defined and/or evaluated.

Cheers,
Reinhold
-- 
------------------------------------------------------------------
Reinhold Kainhofer, address@hidden, http://reinhold.kainhofer.com/
 * Financial & Actuarial Math., Vienna Univ. of Technology, Austria
 * http://www.fam.tuwien.ac.at/, DVR: 0005886
 * LilyPond, Music typesetting, http://www.lilypond.org