Re: [LPeg] intermittent stack exhaustion

[Sebastian Cato <seb.cato@...>]

Ah, that's better than what I thought of. Out of curiosity, did you
pass along the lua_State* to hascaptures to raise an error in case a
cyclical reference is encountered, or is it sufficient to return zero
at that point? Also, will there be a new release soon?

I'll take this opportunity to thank you for a very good piece of
software, and after today's debugging session and e-mail conversation
I appreciate it even more than I did before. Thank you.

//Sebastian Cato

On Tue, Sep 13, 2016 at 6:33 PM, Roberto Ierusalimschy
<roberto@inf.puc-rio.br> wrote:
>> 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
>