eclipse-xtext / eclipse-xtext/xtext
ContentAssist incomplete for grammars requiring prediction multiple times
Nobody has claimed this yet.
- 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
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- 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