SourceInterval for root node is wrong for start symbols with explicit EOF listed at the end of the rule
- Dominant language
- Java
- Stars
- 19k
- Forks
- 3.5k
- PR merge metrics
- No merged PRs in 30d
Description
This is something I found while duplicating the code for parse trees that computes the [SourceInterval](https://github.com/antlr/antlr4/blob/47415e33c366cd9695d5c7e2586424692492deed/runtime/CSharp/src/ParserRuleContext.cs#L363) (i.e., range of indices for token the parse tree spans; defined in [Java here](https://github.com/antlr/antlr4/blob/47415e33c366cd9695d5c7e2586424692492deed/runtime/Java/src/org/antlr/v4/runtime/ParserRuleContext.java#L307)). Note, I need to duplicate and extend all of Antlr trees in order to implement tree rewriting because Antlr does not offer editable parse trees.
Consider the grammar without EOF:
```
grammar Expression;
s : e ;
e : e ('*'|'/') e | e ('+'|'-') e | ('+'|'-') e | INT ;
INT : [0-9]+ ;
WS : [ \t\n]+ -> skip ;
```
Notice this grammar does not define the usual EOF-augmented start rule. If we parse "1+2" from `s`, the tokens and tree created with source intervals are:
```
[@0,0:0='1',<5>,1:0]
[@1,1:1='+',<3>,1:1]
[@2,2:2='2',<5>,1:2]
[@3,3:2='',<-1>,1:3]
```
```
( s int:0..2
( e int:0..2
( e int:0..0
( INT int:0..0 text:1 tt:5 chnl:DEFAULT_TOKEN_CHANNEL text:1 chnl:DEFAULT_TOKEN_CHANNEL l:1 c:0 si:0 ei:0 ti:0
) )
( int:1..1 text:+ tt:3 chnl:DEFAULT_TOKEN_CHANNEL text:+ chnl:DEFAULT_TOKEN_CHANNEL l:1 c:1 si:1 ei:1 ti:1
)
( e int:2..2
( INT int:2..2 text:2 tt:5 chnl:DEFAULT_TOKEN_CHANNEL text:2 chnl:DEFAULT_TOKEN_CHANNEL l:1 c:2 si:2 ei:2 ti:2
) ) ) )
```
So far, so good. Notice that the last token is at token index 3, which is an EOF. The parse tree SoruceInterval is [0..2]. That's good because the EOF token is not part of the tree for symbol `s`. And, it shouldn't, because the grammar never even uses the symbol. So, the root is a tree with leaves `1`, `+`, and `2`.
Now, consider the grammar modified with an explicit EOF.
```
grammar Expression;
s : e EOF ;
e : e ('*'|'/') e | e ('+'|'-') e | ('+'|'-') e | INT ;
INT : [0-9]+ ;
WS : [ \t\n]+ -> skip ;
```
The tokens and tree recognized by parsing "1+2" are:
```
[@0,0:0='1',<5>,1:0]
[@1,1:1='+',<3>,1:1]
[@2,2:2='2',<5>,1:2]
[@3,3:2='',<-1>,1:3]
```
```
( s int:0..2
( e int:0..2
( e int:0..0
( INT int:0..0 text:1 tt:5 chnl:DEFAULT_TOKEN_CHANNEL text:1 chnl:DEFAULT_TOKEN_CHANNEL l:1 c:0 si:0 ei:0 ti:0
) )
( int:1..1 text:+ tt:3 chnl:DEFAULT_TOKEN_CHANNEL text:+ chnl:DEFAULT_TOKEN_CHANNEL l:1 c:1 si:1 ei:1 ti:1
)
( e int:2..2
( INT int:2..2 text:2 tt:5 chnl:DEFAULT_TOKEN_CHANNEL text:2 chnl:DEFAULT_TOKEN_CHANNEL l:1 c:2 si:2 ei:2 ti:2
) ) )
( EOF int:3..3 text: tt:-1 chnl:DEFAULT_TOKEN_CHANNEL text: chnl:DEFAULT_TOKEN_CHANNEL l:1 c:3 si:3 ei:2 ti:3
) )
```
Notice here that we have EOF contained in the tree (2nd child of root). The token list is the same as the previous grammar/input. But, the SourceInterval of the root is 0..2, the same as the previous grammar. That is wrong because EOF is in the parse tree and the token stream.
__The EOF-token leaf node is the 2nd child of the root of the tree, and it has SourceIndex of [3..3].
If the tree has a leaf node for the EOF token, then the SourceInterval for the root of the tree should be [0..3] in order to satisfy the basic definition of the SourceInterval: for any node x, the token interval is [min, max] for the entire range of tokens the tree x spans.__
Contributor guide
Research direction
Read runtime/Java/src/org/antlr/v4/runtime/ParserRuleContext.java and runtime/CSharp/src/ParserRuleContext.cs, focusing on the SourceInterval implementations. Reproduce the two Expression grammars with and without an explicit EOF while parsing 1+2; done means a root containing an EOF leaf reports the interval [0..3], while the other root remains [0..2].
Written by the indexing model from the issue text.
Assessment
- Tech stack
- csharp, java
- Domain
- compilers
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Clearly specified
- Newbie friendliness
- 45/100