eclipse-xtext / eclipse-xtext/xtext

ContentAssist incomplete for grammars requiring prediction multiple times

Open
#2,540 3 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

bug
Dominant language
Java
Stars
831
Forks
330
Avg merge
3d 7h
Merged PRs (30d)
12

Description

I spotted a firm bug in the error detection of the content assist that prevents the creation of valid CA proposals. The grammar need to cause Antlr to predict() twice during the FollowElement computation. Here's an exemplary grammar

Member:
    FieldDecl | MethodDecl
;

FieldDecl:
    annotations+=Annotation* modifier = ('private' | 'public')? type = Type name = ID ('=' initVal = INT)? ';'
;

MethodDecl:
    annotations+=Annotation* modifier = ('private' | 'public')? type = Type name = ID '(' ')' '{'
        (decls += FieldDecl)*
        (statements += Statement)*
    '}'
;

Type:
    {IntType} "int" | ({TypeRef} type = [Type | QualifiedName])
;

QualifiedName:
    ID ('.' ID)*
;

Statement:
    AssignmentStatement
    | {Return} 'return' ';'
;

AssignmentStatement:
    FeatureCall ({Assignment.feature = current} '=' rhs = INT)? ';'
;

FeatureCall:
    feature = [ Member | ID]
    (
        {MemberCall.owner=current} ->"." member = [ Member | ID]
    )*;

Annotation:
    '@' key=ID ('(' values+=STRING(',' values+=STRING)* ')')?
;

The first unbounded look ahead is required for distinguishing the applicability of FieldDecl vs. MethodDecl because of the * cardinality of the call of Annotation. The second one is required to check for applications of calls of FieldDecl within methods ( { }), which starts with a type reference that might consist of IDs sparated by . (QualifiedName). Alternatively, (Member)FeatureCalls being part of AssignmentStatements, which also potentially include several .s, are valid at this place, too.

It turns out that the content assist is incomplete for the following text snippet

public int y() {
    bar<|>
}

with cursor location indicated by <|>. More specifically no cross reference targets are proposed.

Surprisingly, for the inputs

int y() {
    bar<|>
}

and

public int y () { // additional white space between 'y' and '('
    bar<|>
}

the content assist works well.

I debugged the problem and figured that during the first prediction the involved DFA increases the field currentLookAhead of the input token stream based on the current value of p, see here.
Note that p is a token counter that includes hidden tokens, see e.g. here. (The class CommonTokenStream used by Xtext has been re-implemented in the meantime,
the former implementation is available as LegacyCommonTokenStream, so I link that one here.)

The first prediction starts with p == 0 and currentLookAhead == 0 and increases p to 2, 4, 5, 6, and simultaneously increases currentLookAhead to 0, 2, 4, 5, see here.

Once the prediction mode is left (p gets reset to the value before the prediction, here 0) and the ordinary consumption continues, currentLookAhead gets decreased non-hidden token by non-hidden token. In detail, consuming the tokens public, int, y, (, ), and { yields the values
of 4, 3, 2, 1, 0, and -1 to be assigned to currentLookAhead. So far so good, no problem here.
However, note the discrepancy to the above proceeding of increasing currentLookAhead based on the amount of non-hidden and hidden tokens.

Now the second prediction starts, investigating whether to apply FieldDecl starting with a potentially qualified type reference, or whether to proceed to the call of Statement.
In the follow token computation attempt were the input is cropped after {, i.e. with input being set public int y() {, DFA.predict() terminates immediately
by throwing an exception via noViableAlt().

However, xtext.ide...DFA hooks in there.
It sets failedPredicateAtEOF to true because of currentLookAhead == -1 still holds.

This side effect, however, blocks the creation of further follow elements here.
Although the subsequent calls of Statement -> AssignmentStatement -> FeatureCall no further follow elements are added because of failedPredicateAtEOF == true.

In contrast, in the first good case currentLookAhead is increased to 3 in the first prediction, and subsequently decreased to -2 while consuming the 5 subsequent non-hidden tokens.
Again, the second prediction fails immediately. However, the hook of xtext.ide...DFA
doesn't cause any affect as the condition of the second if is not satisfied. failedPredicateAtEOF stays equal to false.

In the subsequent look ahead checking the applicability of Statement again EOF is hit, but follow elements are created since failedPredicateAtEOF == false holds.

In the second good case currentLookAhead is increased to 6 in the first prediction (public + 2 additional hidden tokens), and subsequently decreased to 0 while consuming the 6 subsequent non-hidden tokens.
Again, the second prediction fails immediately and, again, the hook of xtext.ide...DFA
doesn't cause any affect as the condition of the second if is not satisfied, since currentLookAhead == 0 and lookAheadAddOn == 0, too. failedPredicateAtEOF stays equal to false.

In the subsequent look ahead checking the applicability of Statement again EOF is hit, but follow elements are created here since failedPredicateAtEOF == false holds like in good case 1.

I will push the implementation of the test language on a branch and a corresponding test shortly.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with XtextTokenStream.java, the content-assist DFA.java, and BaseInternalContentAssistParser.java, then trace currentLookAhead and failedPredicateAtEOF across both predictions. Reproduce the supplied grammar and cursor examples once the implementation test language is available; done means valid cross-reference proposals are produced for the affected input without breaking the working whitespace variants.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
compilers, tooling
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.