unbounded recursion in LexerStream.next()

[jwilk]

This test program

from rply import LexerGenerator
lg = LexerGenerator()
lg.ignore(r'\s')
for token in lg.build().lex(' ' * 1000):
    pass

makes the Python interpreter sad:

Traceback (most recent call last):
  File "test.py", line 4, in <module>
    for token in lg.build().lex(' ' * 1000):
  File "/usr/lib/python3/dist-packages/rply/lexer.py", line 56, in __next__
    return self.next()
  File "/usr/lib/python3/dist-packages/rply/lexer.py", line 41, in next
    return self.next()
...
  File "/usr/lib/python3/dist-packages/rply/lexer.py", line 41, in next
    return self.next()
  File "/usr/lib/python3/dist-packages/rply/lexer.py", line 38, in next
    match = rule.matches(self.s, self.idx)
  File "/usr/lib/python3/dist-packages/rply/lexergenerator.py", line 33, in matches
    return Match(*m.span(0)) if m is not None else None
RecursionError: maximum recursion depth exceeded

[alex]

I'm not sure I understand why this causes unbound recursion :-(

[jwilk]

The relevant code is:

def next(self):
    if self.idx >= len(self.s):
        raise StopIteration
    for rule in self.lexer.ignore_rules:
        match = rule.matches(self.s, self.idx)
        if match:
            self._update_pos(match)
            return self.next()
    ...

CPython doesn't do tail recursion elimination, so if there's N consecutive ignorable tokens in the input, N stack frames will be consumed.
If N is big enough (1000 in my reproducer), you get a recursion error.
To fix this, use a while loop instead of recursion:

def next(self):
    while True:
        if self.idx >= len(self.s):
            raise StopIteration
        for rule in self.lexer.ignore_rules:
            match = rule.matches(self.s, self.idx)
            if match:
                self._update_pos(match)
                break
        else:
            break
    ...

(untested, sorry!)

[alex]

Ugh, right, I forgot how I implemented ignores. Will try to fix this
tonight.

On Wed, Feb 24, 2016 at 9:39 AM, Jakub Wilk notifications@github.com
wrote:

The relevant code is:

def next(self):
if self.idx >= len(self.s):
raise StopIteration
for rule in self.lexer.ignore_rules:
match = rule.matches(self.s, self.idx)
if match:
self._update_pos(match)
return self.next()
...

CPython doesn't do tail recursion elimination, so if there's N consecutive
ignorable tokens in the input, N stack frames will be consumed.
If N is big enough (1000 in my reproducer), you get a recursion error.
To fix this, use a while loop instead of recursion:

def next(self):
while True:
if self.idx >= len(self.s):
raise StopIteration
for rule in self.lexer.ignore_rules:
match = rule.matches(self.s, self.idx)
if match:
self._update_pos(match)
break
else:
break
...

(untested, sorry!)

—
Reply to this email directly or view it on GitHub
#52 (comment).

"I disapprove of what you say, but I will defend to the death your right to
say it." -- Evelyn Beatrice Hall (summarizing Voltaire)
"The people's good is the highest law." -- Cicero
GPG Key fingerprint: 125F 5C67 DFE9 4084