[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
**Subject**: **Re: [LPeg] intermittent stack exhaustion**
**From**: Roberto Ierusalimschy <roberto@...>
**Date**: Tue, 13 Sep 2016 11:26:11 -0300

> >> If I understand things correctly (and I may not), it seems that the
> >> "Q" rule references itself instead of "P" (call key: 2 instead of call
> >> key: 1 in the failing tree above). This leads to infinite
> >> recursion/stack exhaustion during compilation.
> >
> > This is correct. The 'key' there is the index in the ktable (shown
> > in the beginning of the tree) of the key of the rule being called.
> > In that table, "2 = P", which means that the rule is calling "P"
> > (which is correct).
>
> Ah, so the tree itself is correct?
>
> > [1 = P 2 = P 3 = Line ]
> > grammar 3
> > rule n: 0 key: 3
> > seq
> > char 'x'
> > capture cap: 5 key: 0 n: 0
> > call key: 1
> > rule n: 1 key: 2
> > char 'a'
> > rule n: 2 key: 0
> > call key: 2
>
> rule 0 says "char 'x' followed by the capture of rule ktable[1]
> rule 1 says "char 'a'"
> rule 2 says "rule ktable[2]"
Yes. The tree is fine.
> and rules are zero indexed and the ktable is indexed from 1. Am I
> understanding it correctly?
Yes.
The bug is a stupid one in 'hascaptures'. It follows calls without
checking for cycles. (It is rare because 'hascaptures' is only used for
patterns with fixed length.) It also follows "next rule", to be able
to traverse an entire grammar looking for captures. So, rule 2 calls
rule 1, which has rule 2 as its next rule, etc.
-- Roberto