Re: [LPeg] intermittent stack exhaustion

[Roberto Ierusalimschy <roberto@...>]

> A couple of options I can think about:
> 
> 1) the way verifygrammar and verifyrule works, with an int
> passed[MAXRULES], and npassed as a counter to keep track of the
> visited rules. (I think 'passed' can be short ints, since keys are
> short ints, if we want to save stack space).
> 
> 2) reserve a bit in each TTree node (e.g., the upper most bit of tag)
> to use as a 'visited' flag and perform the depth first search. If
> encountering a node with the bit set, we know that the graph is
> cyclic. Would require clearing the bits later if it's to be done more
> than once. Could maybe be used for verifygrammar, verifyrule too.
> 
> 3) use a strongly connected component (SCC) algorithm, e.g., Tarjan's
> SCC. Maybe overkill.
> 
> 4) use a lua table as a set, with keys being the addresses to the
> visited nodes. Perform a DFS, for each TRule node: if the address is
> in the set, the graph is cyclic. I'm thinking about the case where we
> have TCall -> TRule, I don't know if there's any other nodes that can
> lead to cycles.

I opted for (2), using 'key' itself as a flag. (I change it to 0 when
visiting the call, and restore it before returning.)

-- Roberto