Error recovery should create missing tokens for first path to recovery point

[sharwell]

Currently, error recovery does not create tree nodes or tokens for grammar elements that appear between the point where recovery efforts start and where they finally succeed. The skipped tokens are simply skipped. This causes problems for listeners and visitors which expect the parse tree to return non-null values for element accessors for required references.

For example, consider the following:

someElement
  : first second third
  ;

In this code, it is clear that someElement can never parse in a way that first, second, or third is missing. Therefore, it is reasonable to expect that the corresponding accessors in code, first(), second(), and third(), will all return non-null trees. We can ensure these conditions are met by modifying the error recovery to follow the first path to the end of a rule, manufacturing rule and terminal nodes as necessary to ensure the resulting parse tree contains a minimally-correct structure.

• Take "First path to end"
  • Do not loop back for + or * blocks
  • Do not enter * or ? blocks
  • Otherwise take the first alternative for decisions
• Create a context node when following a RuleTransition
• Create a zero-width TerminalNode when traversing a match transition

Background

It's straightforward to see how this could improve the ability of users to reason about the shape of a parse tree without constantly worrying about what happens if/when an error occurs. The shape will be valid even if the content is not, which improves over the current situation where visitors and listeners that operate on trees produced by erroneous code must worry about both potentially being invalid.

However, this became a particularly obvious usability problem during the implementation of the TypeScript target. TypeScript's type system has distinct representations of null (we used undefined uniformly), which impacted the generated accessors:

someElement
  : element // This accessor returns a non-null type
  ;

someOptionalElement
  : element? // This accessor returns a nullable type
  ;

In order to ensure the accessor methods behaved accurately with respect to the type system, the accessor generated for SomeElementContext.element() throws in the TypeScript target instead of returning a null value. However, if the error recovery effort traversing through someElement actually ensured that it contained an ElementContext child, the type system would be accurate and users would not need to worry about exceptions except in cases where they truly failed to write code matching a form appearing in the original grammar.

[mike-lischke]

@sharwell Can you show me please how a test for the existance of a token would look like then in code? If you always create an error context node instead of just leaving out a missing token how can I know then it was missing?

Also, how would I distinguish between the case where the first path was taken as part of error handling or just because the input dictated that?

And finally, checking for the existance of a token is not always related to error recovery (and that's an aspect you ignored so far). Take this rule:

rule: a | b;

In a listener I want to see which path was taken there. Since all of the subrules are mandatory all their accessors return non-null types. How can I determine (using the accessors) if a or b was matched if not the one that was not matched returns null? In an error case even both a and b could be unassigned (assume a more complex rule where other parts before a and b have been matched successfully). With your new implementation I would always get back something (what actually, a context with an error token?) and, if I get this right, it would force me to check every sub context whether it is an error context or not.

[sharwell]

Can you show me please how a test for the existance of a token would look like then in code?

At minimum, the token would have an empty source span. Depending on the implementation, it may also have additional properties for examining the skipped tokens or otherwise checking to see what went wrong.

And finally, checking for the existance of a token is not always related to error recovery (and that's an aspect you ignored so far).

The TypeScript target already handles this case by emitting the accessor a() to return AContext | undefined instead of AContext¹. Originally, ANTLR differentiated only between "0 or 1" and "0 or more". In #1576 and #1582, I expanded on the tool's analysis process to differentiate between "0 or 1", "0 or more", and "exactly 1". For your example, both a and b would be matched "0 or 1" times.

¹ If this statement is not correct, then there is a bug either in the code generation tool or in the TypeScript templates.

[sharwell]

Also, how would I distinguish between the case where the first path was taken as part of error handling or just because the input dictated that?

The first path would not be taken in the generated code. It would only be an ATN traversal within the internals of the error recovery process, at the same time as skipping tokens to resynchronize the input. In other words, the traversal would not be observable within the generated code, but only in the fact that the parse tree contains one or more "manufactured" tokens.

[Endeavourl]

Hi. Is this issue relevant to my parse contexts containing null child nodes, even though corresponding subrules in the grammar are mandatory (i.e. should never be null)? This happens sometimes when parser encounter an error.

A fix for this would be appreciated, otherwise i'd have to wrap every single parse-tree traversal step with null checks.

Maybe such "broken" contexts should not be added to the final tree at all when the parser fails to create all mandatory child nodes using given input?

[ericvergnaud]

Hi Parsing with antlr4 is always successful i.e. it always produces a parse tree regardless of whether the tree is valid or not. This is desirable because it is often easier to handle errors after parsing than during parsing, especially when interacting with users. So the null child nodes is the expectedly behavior. You can alter this by providing your own error strategy. Envoyé de mon iPhone

…

Le 27 nov. 2017 à 23:15, Alexander Levsha ***@***.***> a écrit : Hi. Is this issue relevant to my parse contexts containing null child nodes, even though corresponding subrules in the grammar are mandatory (i.e. should never be null)? This happens sometimes when parser encounter an error. A fix for this would be appreciated, otherwise i'd have to wrap every single parse-tree traversal step with null checks. Maybe such "broken" contexts should not be added to the final tree at all when the parser fails to create all mandatory child nodes using given input? — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub, or mute the thread.

[KvanTTT]

This is desirable because it is often easier to handle errors after parsing than during parsing, especially when interacting with users. So the null child nodes is the expectedly behavior.

Null child is expected behavior even if this node marked with question operator: node?. Otherwise, it brings a lot of NRE bugs during the processing of parse tree with errors and breaks type system if not null reference types feature is available. Moreover, skipping of error nodes disallows the building of a full-fidelity parse tree that useful in refactoring applications.

Also, ANTLR already has ErrorNodeImpl, but it does not work for all cases, including the abovementioned.

[ericvergnaud]

Not an issue, closing.

[KvanTTT]

Sorry, but I disagree. Why is it not an issue? It's quite valid issue, at least it can be moved to Discussions.

[ericvergnaud]

Yes it's worth a discussion, but the current behavior is not a bug, is it ?