One function
ForestToParseTree in lark-parser/lark
The author described this change as “Fix an SPPF cycle edge case (Issue #820)”. It counts as a record because the check below fails on the code as it stood at 9379161aa and passes on e88646b58, with nothing else changed between the two runs.
Projectlark-parser/lark
Fix saved2021-01-26
Sharing licenceMIT · LICENSE
Change size+3 −3
What the code was meant to do, written into the code itself as a docstring
Used by the earley parser when ambiguity equals 'resolve' or 'explicit'. Transforms an SPPF into an (ambiguous) parse tree. tree_class: The tree class to use for construction callbacks: A dictionary of rules to functions that output a tree prioritizer: A `ForestVisitor` that manipulates the priorities of ForestNodes resolve_ambiguity: If True, ambiguities will be resolved based on priorities. Otherwise, `_ambig` nodes will be in the resulting tree.
The change
| 30 | 30 | ||
| 31 | 31 | def _check_cycle(self, node): | |
| 32 | 32 | if self._on_cycle_retreat: | |
| 33 | - | if id(node) == id(self._cycle_node): | |
| 33 | + | if id(node) == id(self._cycle_node) or id(node) in self._successful_visits: | |
| 34 | 34 | self._cycle_node = None | |
| 35 | 35 | self._on_cycle_retreat = False | |
| 36 | 36 | return | |
| ⋯ | |||
| 64 | 64 | def transform_symbol_node(self, node, data): | |
| 65 | 65 | if id(node) not in self._successful_visits: | |
| 66 | 66 | raise Discard() | |
| 67 | - | self._successful_visits.remove(id(node)) | |
| 68 | 67 | self._check_cycle(node) | |
| 68 | + | self._successful_visits.remove(id(node)) | |
| 69 | 69 | data = self._collapse_ambig(data) | |
| 70 | 70 | return self._call_ambig_func(node, data) | |
| 71 | 71 | ||
| 72 | 72 | def transform_intermediate_node(self, node, data): | |
| 73 | 73 | if id(node) not in self._successful_visits: | |
| 74 | 74 | raise Discard() | |
| 75 | - | self._successful_visits.remove(id(node)) | |
| 76 | 75 | self._check_cycle(node) | |
| 76 | + | self._successful_visits.remove(id(node)) | |
| 77 | 77 | if len(data) > 1: | |
| 78 | 78 | children = [self.tree_class('_inter', c) for c in data] | |
| 79 | 79 | return self.tree_class('_iambig', children) | |
The check that tells the two apart
fail→pass·tests/test_parser.py::TestFullEarleyDynamic::test_cycle2
Check file tests/test_parser.py, taken without changes from the fix and copied onto the older code, so the exact same check runs against both versions.
Origin and history
The code before it9379161aad48994302251803ef7e932cbbd3c4ba
Broken version dated2021-01-25
Modulelark.parsers.earley_forest
Units changedForestToParseTree
Fingerprint9e8bc9f7c5f9889b
Checked2026-08-18 by goldset/0.1
Every field above is generated by our program. None of it is written by hand.
Other bugs found in lark-parser/lark
- 2026-07-08Fix lexer_callbacks silently dropped for keyword terminals
- 2026-06-24Transformer_NonRecursive
- 2026-06-04Raise GrammarError for non-terminal names in %declare
- 2026-06-02Fix empty SPPF node from xearley ignore carry-over (fixes #1598)
- 2026-05-24fix: raise GrammarError for template usage inside terminals
- 2024-10-25Adjust behaviour in #1481 to raise a NotImplementedError