Excess token consumption during recovery

[michaelpj]

The method recoverInline in ANTLRErrorStrategy returns a Token, however, in my generated parsers, I see it used like this:

        try {
            enterOuterAlt(_localctx, 1);
            {
            setState(479);
            _la = _input.LA(1);
            if ( !(_la==TKminus || _la==TKplus) ) {
            _errHandler.recoverInline(this);
            }
            consume();
            }
        }

That is, the Token produced from recoverInline is ignored.

This can lead to excess token consumption, as the DefaultErrorStrategy will call consume if it deletes a token, returning the matched token. (It calls it first in singleTokenDeletion to delete the token, but then again in recoverInline). But then the parser will consume once again, so we also consume the token after the one we wanted.

Needless to say, this can really mess up error recovery.

It's not clear to me from the documentation of recoverInline whether a successful return indicates that the token has been consumed or not. I suspect it does, since singleTokenInsertion does not in fact insert a token into the stream that could later be consumed. Hence, the fix is probably just to put the generated consume in an else block.

[michaelpj]

This is with 4.4 - I haven't tried with 4.5 RC1 yet.

[parrt]

The goal of in-line recovery is to modify the token stream such that there is a chance the parser can continue from the current error. Can you give me the grammar fragment? It still looks okay because if the current input symbol is not a plus or minus, the recovery will consume tokens until it sees one in look ahead (not consumed), which will then be consumed by the mechanism afterwards. We have not seen any bugs related to this. Is this merely an efficiency issue?

[sharwell]

The result of recoverInline is assigned to the label variable if your token in the grammar is labeled.

There are three different behaviors the default implementation of recoverInline gives. Suppose you are trying to match a token Y followed by Z.

1. If the input sequence is LA(1)=X, LA(2)=Y, (i.e. skipping X will allow the parser to match Y), then we call consume to skip X and then return LT(1). This code path should work fine. When the call returns, LA(1)=Y which means we should call consume (which it does). See below
2. If the input sequence is LA(1)=Z, then assume the Y is missing, and we construct a new token Y. When the call returns, LA(1)=Z which means we should not call consume. This code appears to have a bug.
3. If neither of the above work, then throw an InputMismatchException. This code path should work fine.

[michaelpj]

Here's a more complete fragment:

    public final SimpleIdContext simpleId() throws RecognitionException {
        SimpleIdContext _localctx = new SimpleIdContext(_ctx, getState());
        enterRule(_localctx, 50, RULE_simpleId);
        int _la;
        try {
            enterOuterAlt(_localctx, 1);
            {
            setState(457);
            _la = _input.LA(1);
            if ( !(_la==Lowerid || _la==Upperid) ) {
            _errHandler.recoverInline(this);
            }
            consume();
            }
        }
        catch (RecognitionException re) {
            _localctx.exception = re;
            _errHandler.reportError(this, re);
            _errHandler.recover(this, re);
        }
        finally {
            exitRule();
        }
        return _localctx;
    }

This is generated from the rule:

simpleId : Lowerid 
         | Upperid 
         ;

I think we're on the same page as to what recovery is supposed to do, but I don't think that lines up with what the DefaultErrorStrategy does.

Notably, here we're in your case 1., Sam. But we see that we've already deleted the offending token, and then we consume again. I think that means we actually consume Y as well before we return. In that case it's not safe to call consume.

I think you're correct that path 2. has a bug as well, but that wasn't the one I hit ;)

[michaelpj]

(Crucially, singleTokenDeletion already consumes the token we want to skip.)

[michaelpj]

And apologies for the red herring - whether the return value of recoverInline gets used is irrelevant. The problem is just the unconditional consume in the parser.

[sharwell]

So the solution is putting the generated call to consume in an else block.

Edit: Which is exactly what you said.

[michaelpj]

I believe so - that fixes the bug in path 1., and I think it also fixes the bug in path 2. singleTokenInsertion doesn't actually add a new Token to the stream, so we never want to call consume after we do that.

Path 3. is of course okay as we're in an exceptional control flow at that point.

[sharwell]

👍 Nice analysis here.

[michaelpj]

Alright, I'll see if I can whip up a test case and send a PR your way.

[parrt]

cool. I'll integrate for 4.5 if you can get it to me quickly. thanks very much Michael! Don't forget to add yourself to the contributors list as part of the pull request.