Open hudson-ai opened 1 month ago
All modified and coverable lines are covered by tests :white_check_mark:
Project coverage is 60.33%. Comparing base (
15ff21d
) to head (867adbe
). Report is 1 commits behind head on main.
:exclamation: Your organization needs to install the Codecov GitHub app to enable full functionality.
:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.
Currently, my fix is to avoid infinitely recursing over children, but I suspect that it might be nicer to prevent accepting parses that have infinitely looping children to begin with. That being said, the behavior seems correct (in that captures are correctly being... captured).
@slundberg I would really appreciate some input from you on this as well as what the correct semantics of partial captures should be (I tried to preserve existing behavior, but I'm not entirely clear on whether that behavior was the intended one).
Computing the parse tree (needed for getting captures) previously caused an infinite loop if the grammar has loops of nullable rules, where a nullable rule is any rule where every symbol on the RHS is nullable.
E.g., the grammar
has nullable rules
and there is a loop in these rules formed by
A -> B
andB -> A
.For a deeper discussion on this, see section "One Last Trap" of https://loup-vaillant.fr/tutorials/earley-parsing/parser
This PR solves the issue by keeping a set of visited nodes when computing the parse tree (or getting captures) and skipping any node that has already been seen. AFAIK, the only way this can happen is when we have these nullable loops, but admittedly I still have a lot to learn about the parser (so more eyes on this would be really helpful!)
This closes #863