go/ast: add BasicLit.ValueEnd field

[adonovan]

Background: The BasicLit.End method computes the end position of a literal by adding its start position to the length of the BasicLit.Value string, which is assumed to be the complete raw text of the literal. However, for multiline raw string literals, the spec requires that carriage returns (as used in text files on Windows) are discarded, and this process occurs in the scanner, so the Value string in the syntax tree is shorter than the actual string, causing the End position to be computed incorrectly.

Proposal: We propose to record the actual end position of the token in a new field, BasicLit.ValueEnd.

	package ast // "go/ast"

	type BasicLit struct {
-		ValuePos token.Pos   // literal position
+		ValuePos, ValueEnd token.Pos   // literal position
		Kind     token.Token // token.INT, token.FLOAT, token.IMAG, token.CHAR, or token.STRING
		Value    string      // literal string; e.g. 42, 0x7f, 3.14, 1e-9, 2.4i, 'a', '\x7f', "foo" or `\m\n\o`
	}

The implementation is trivial. The only real downside is that the new field pushes the size of the struct up from 4 words to 5, and its size class from 4 words to 6 words. BasicLits are very numerous, about 10% of all tokens according to the nodecount command, so adding this field may cause ASTs to increase space usage by about 2%.

Relatively few programs use the parser and are long running (and therefore care about memory pressure and GC costs). Gopls is arguably the most important among them. We gopls maintainers are willing to pay the memory price for the AST to record the input in greater fidelity, not just as it relates to this issue, but in a number of other ways as well. The way we see it is that there will be no go/ast v2 since it defines the entire Go tooling ecosystem, so we need to make incremental improvements. Computers have also gotten bigger and faster since go/ast was designed.

cc: @griesemer @findleyr

[gabyhelp]

Related Issues

• go/ast: establish File.FileStart <= Node.Pos <= Node.End <= File.FileEnd for all Nodes in a File #73438
• proposal: go/ast: add Start token.Pos fields to BlockStmt and FieldList #73584
• go/ast: (*ast.BasicLit).End() is wrong for raw literals with carriage returns ('\r') #69861 (closed)
• go/ast: record start and end of file in File.FileStart, File.FileEnd #53202 (closed)
• proposal: go/token: add File.End method #75849
• go/ast: `(*ast.BasicLit).End()` is wrong for raw literals with carriage returns ('\r') #69860 (closed)
• proposal: go/scanner: add `(*Scanner).Pos()` #74958
• go/ast: add Range token.Pos to RangeStmt #50429 (closed)
• go/ast: the position of "range" keyword is lost during parsing #13590 (closed)
• go/parser: StructType.End() can underflow the File #66683

_{(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)}

[DanielMorsing]

Having taken a stab at the almighty #20744, and run into this issue, but with comments, I am broadly in favour of this. Would it be reasonable to define a similar field for comments too? I'm not sure about the frequency that they appear and whether the cost/benefit maths hold, but comment parsing is at least optional.

Will the .End() value change to return this new position? It would remove both an annoying inconsistency and make the behavior so much more easier to document. I'm trying to think if there's any case where code that worked before would be broken by such a change and coming up short.

[mateusz834]

I'm trying to think if there's any case where code that worked before would be broken by such a change

I assume End only returns the EndPos in case it is valid, otherwise fallbacks to the previous approach.

I guess that could somehow break code that modifies Value field of a parsed AST, since End() would not change then.

[adonovan]

Having taken a stab at the almighty #20744, and run into this issue, but with comments, I am broadly in favour of this. Would it be reasonable to define a similar field for comments too? I'm not sure about the frequency that they appear and whether the cost/benefit maths hold, but comment parsing is at least optional.

The comments problem is much deeper and any solution needs to be systematic. It will undoubtedly also increase memory usage, but how much depends on the details of the design. Some increase is justifiable by the same rationale I gave above.

Will the .End() value change to return this new position? It would remove both an annoying inconsistency and make the behavior so much more easier to document.

Yes, it will.

I'm trying to think if there's any case where code that worked before would be broken by such a change and coming up short.

No doubt such code exists (it always does), but this is not a breaking change in its usual sense, and we can fix bugs as we find them.

I assume End only returns the EndPos in case it is valid, otherwise fallbacks to the previous approach.

Exactly.

I guess that could somehow break code that modifies Value field of a parsed AST, since End() would not change then.

Modifying the tree is always fraught. End could compute min(EndPos, Pos + len(Value)) which is one-liner, and avoids any problem if the Value should increase.

[mateusz834]

End could compute min(EndPos, Pos + len(Value)) which is one-liner, and avoids any problem if the Value should increase.

But then hand-crafted *ast.BasicLits would be wrong. End would always return 0.

l := &ast.BasicLit{
    ValuePos: somePos,
    Value: "bar"
}

[adonovan]

Sorry, I meant max.

(Aside: I frequently mistake min and max, I think because max(x, y), means "use x, but requiring a minimum value of y".)

[griesemer]

Presumably, not removing the carriage returns in the scanner, but leaving it to clients of go/ast (and thus recording the literal string faithfully in a BasicLit) is going to cause significant disruptions, I assume? One could provide an accessor that removes the carriage returns, but all clients would need to know to use it.

Barring the above suggestion, which I suspect is not practical, I am ok with adding a ValueEnd field.

[findleyr]

As with others, my main concern with this proposal is inconsistency between the Value and ValueEnd fields. I don't think defining End in terms of max really solves this problem, since the value could of course decrease.

It looks like we have one similar case of prior art in the ast: ImportSpec.EndPos, and to be frank I have no idea how to use that correctly.

So I agree this is a bug, but also feel like this is liable to break arbitrary tools in subtle ways. I'm not actually sure that leaving the carriage return in BasicLit is a worse option.

Can we have a new parser mode Correct? Only partially joking.