Repository: neogeny/TatSu

Issue:
Parser drops part of input
Grammar:
```
identifier = /\w+/ ;
start = '{' start '}' | start '->' identifier | identifier ;
```

Input:
```
{ size }
test
```

Expected output: `['{', 'size', '}']`
Actual output: `test`

Removing the (left recursive) rule `start '->' identifier` fixes the problem.

Discussion:

Patch:
diff --git a/tatsu/contexts.py b/tatsu/contexts.py
index 6c79fcf..c5dfa78 100644
--- a/tatsu/contexts.py
+++ b/tatsu/contexts.py
@@ -14,6 +14,7 @@ from ._unicode_characters import (
 )
 from tatsu.util import notnone, ustr, prune_dict, is_list, info, safe_name
 from tatsu.util import left_assoc, right_assoc
+from tatsu.util import debug  # noqa
 from tatsu import buffering
 from tatsu import color
 from tatsu.infos import (
@@ -461,6 +462,10 @@ class ParseContext(object):
             self._memos[key] = memo
         return memo
 
+    def _forget(self, key):
+        self._memos.pop(key, None)
+        self._results.pop(key, None)
+
     def _memo_for(self, key):
         memo = self._memos.get(key)
 
@@ -479,13 +484,19 @@ class ParseContext(object):
         self._results[key] = self._mkresult(node)
 
     def _is_recursive(self, name):
-        return name in self._recursive_rules
+        return self.left_recursion and name in self._recursive_rules
 
     def _set_recursive(self, name):
-        self._recursive_rules.add(name)
+        if self.left_recursion:
+            # add rules that are mutually recursive
+            i = self._rule_stack.index(name)
+            for rule in reversed(self._rule_stack[i:]):
+                if rule not in self._recursive_rules:
+                    print('left', rule)
+                self._recursive_rules.add(rule)
 
     def _unset_recursive(self, name):
-        self._recursive_rules.remove(name)
+        self._recursive_rules -= {name}
 
     def _set_left_recursion_guard(self, key):
         ex = self._make_exception(key.name, exclass=FailedLeftRecursion)
@@ -520,37 +531,49 @@ class ParseContext(object):
         finally:
             self._rule_stack.pop()
 
+    def _clear_recursion_errors(self):
+        def filter(key, value):
+            return isinstance(value, FailedLeftRecursion)
+
+        prune_dict(self._memos, filter)
+
     def _recursive_call(self, ruleinfo):
+        pos = self._pos
         key = self.memokey
-        memo = self._memo_for(key)
-
-        if isinstance(memo, Exception):
-            raise memo
-        elif memo:
-            return memo
 
-        self._set_left_recursion_guard(key)
-        result = self._invoke_rule(ruleinfo)
+        if key in self._results:
+            return self._results[key]
+        result = self._invoke_rule(ruleinfo, pos, key)
 
-        if not self.left_recursion:
-            return result
         if not self._is_recursive(ruleinfo.name):
             return result
 
-        self._next_token(ruleinfo)
-        key = self.memokey
-        self._save_result(key, result.node)
-        try:
-            result = self._recursive_call(ruleinfo)
-        except FailedParse:
-            pass
+        while True:
+            self._forget(key)
+            self._save_result(key, result.node)
+            self._clear_recursion_errors()
+            self._goto(pos)
+            try:
+                new_result = self._invoke_rule(ruleinfo, pos, key)
+            except FailedParse:
+                break
+            if self._pos <= result.newpos:
+                break
+            result = new_result
 
+        del self._results[key]
+        self._forget(key)
         return result
 
-    def _invoke_rule(self, ruleinfo):
-        key = self.memokey
+    def _invoke_rule(self, ruleinfo, pos, key):
+        memo = self._memo_for(key)
+        if isinstance(memo, Exception):
+            raise memo
+        elif memo:
+            return memo
+        self._set_left_recursion_guard(key)
+
         self._push_ast()
-        pos = self._pos
         try:
             try:
                 self._next_token(ruleinfo)


Test patch:
diff --git a/test/grammar/left_recursion_test.py b/test/grammar/left_recursion_test.py
index 2c81e0a..0dced21 100644
--- a/test/grammar/left_recursion_test.py
+++ b/test/grammar/left_recursion_test.py
@@ -60,50 +60,85 @@ class LeftRecursionTests(unittest.TestCase):
         print(ast)
         self.assertEqual([['5', '-', '87'], '-', '32'], ast)
 
+    @unittest.skip('uncertain if grammar is correct')
     def test_indirect_left_recursion_complex(self, trace=False):
         grammar = '''
             @@left_recursion :: True
-            start = Primary $ ;
-            Primary = PrimaryNoNewArray ;
-
-            PrimaryNoNewArray =
-              ClassInstanceCreationExpression
-            | MethodInvocation
-            | FieldAccess
-            | ArrayAccess
-            | 'this' ;
-
-            ClassInstanceCreationExpression =
-              'new' ClassOrInterfaceType '(' ')'
-            | Primary '.new' Identifier '()' ;
-
-            MethodInvocation =
-              Primary '.' MethodName '()'
-            | MethodName '()' ;
-
-            FieldAccess =
-              Primary '.' Identifier
-            | 'super.' Identifier ;
-
-            ArrayAccess =
-              Primary '[' Expression ']'
-            | ExpressionName '[' Expression ']' ;
-
-            ClassOrInterfaceType =
-              ClassName
-            | InterfaceTypeName ;
-
-            ClassName = 'C' | 'D' ;
-            InterfaceTypeName = 'I' | 'J' ;
-            Identifier = 'x' | 'y' | ClassOrInterfaceType ;
+            start
+                =
+                Primary $
+                ;
+
+            Primary
+                =
+                PrimaryNoNewArray
+                ;
+
+            PrimaryNoNewArray
+                =
+                | ClassInstanceCreationExpression
+                | MethodInvocation
+                | FieldAccess
+                | ArrayAccess
+                | 'this'
+                ;
+
+            ClassInstanceCreationExpression
+                =
+                | 'new' ClassOrInterfaceType '(' ')'
+                | Primary '.new' Identifier '()'
+                ;
+
+            MethodInvocation
+                =
+                | MethodName '()'
+                | Primary '.' MethodName '()'
+                ;
+
+            FieldAccess
+                =
+                | Primary '.' Identifier
+                | 'super.' Identifier
+                ;
+
+            ArrayAccess
+                =
+                | Primary '[' Expression ']'
+                | ExpressionName '[' Expression ']'
+                ;
+
+            ClassOrInterfaceType
+                =
+                | ClassName
+                | InterfaceTypeName
+                ;
+
+            ClassName
+                =
+                'C' | 'D'
+                ;
+
+            InterfaceTypeName
+                =
+                'I' | 'J'
+                ;
+
+            Identifier
+                =
+                | 'x' | 'y'
+                | ClassOrInterfaceType
+                ;
+
             MethodName = 'm' | 'n' ;
+
             ExpressionName = Identifier ;
+
             Expression = 'i' | 'j' ;
         '''
         model = compile(grammar, "test")
         ast = model.parse("this", trace=trace, colorize=True)
         self.assertEqual('this', ast)
-        ast = model.parse("this.x", trace=trace, colorize=True)
+        ast = model.parse("this.x", trace=True, colorize=True)
         self.assertEqual(['this', '.', 'x'], ast)
         ast = model.parse("this.x.y", trace=trace, colorize=True)
         self.assertEqual([['this', '.', 'x'], '.', 'y'], ast)
@@ -139,7 +174,7 @@ class LeftRecursionTests(unittest.TestCase):
         model.parse("1*2+3*5", trace=trace, colorize=True)
         try:
             model.parse("1*2+3*5", left_recursion=False, trace=trace, colorize=True)
-            self.Fail('expected left recursion failure')
+            self.fail('expected left recursion failure')
         except FailedParse:
             pass
 
@@ -170,7 +205,7 @@ class LeftRecursionTests(unittest.TestCase):
         ast = model_b.parse("(((1+2)))", trace=trace, colorize=True)
         self.assertEqual(['1', '+', '2'], ast)
 
-    def test_left_recursion_bug(self, trace=True):
+    def test_left_recursion_bug(self, trace=False):
         grammar = '''\
             @@grammar :: Minus
             @@left_recursion :: True
@@ -197,7 +232,7 @@ class LeftRecursionTests(unittest.TestCase):
         '''
         model = compile(grammar=grammar)
         model.parse('3', trace=trace, colorize=True)
-        model.parse('3 - 2', trace=trace, colorize=True)
+        model.parse('3 - 2', trace=True, colorize=True)
         model.parse('(3 - 2)', trace=trace, colorize=True)
         model.parse('(3 - 2) - 1', trace=trace, colorize=True)
         model.parse('3 - 2 - 1', trace=trace, colorize=True)
@@ -215,3 +250,62 @@ class LeftRecursionTests(unittest.TestCase):
         model = compile(grammar, "test")
         ast = model.parse("1+2+3", trace=trace, colorize=True)
         self.assertEqual(['1', '+', ['2', '+', '3']], ast)
+
+    def test_partial_input_bug(self, trace=False):
+        grammar = '''
+            start
+                =
+                expre
+                ;
+
+            expre
+                =
+                | '{' expre '}'
+                | expre '->' identifier
+                | identifier
+                ;
+
+            identifier
+                =
+                /\w+/
+                ;
+        '''
+
+        input = '''
+            { size } test
+        '''
+
+        model = compile(grammar)
+        ast = model.parse(input, trace=trace, colorize=True)
+        assert ['{', 'size', '}'] == ast
+
+    def test_dropped_input_bug(self, trace=False):
+        grammar = '''
+            @@left_recursion :: True
+
+            start
+                =
+                expr
+                ;
+
+            expr
+                =
+                | expr ',' expr
+                | identifier
+                ;
+
+            identifier
+                =
+                /\w+/
+                ;
+        '''
+        model = compile(grammar)
+
+        ast = model.parse('foo', trace=trace, colorize=True)
+        self.assertEqual('foo', ast)
+
+        ast = model.parse('foo bar', trace=trace, colorize=True)
+        self.assertEqual('foo', ast)
+
+        ast = model.parse('foo, bar', trace=trace, colorize=True)
+        self.assertEqual(['foo', ',', 'bar'], ast)