Background: token.FileSet is often a bottleneck in applications that process Go source code. Nearly all logic that processes abstract syntax trees (ASTs) needs a FileSet that maps the ASTs' token.Pos values to source locations. FileSet has a natural tendency to become a global variable, needed by the entire application, and to which files are added but never removed. This constraint is not viable in a long-lived application due to monotonically increasing memory usage. (The previous proposal #53200 turned out to be inadequate to solve the problem.)
In gopls, parsed ASTs live in a cache and have independent lifetimes based on invalidation events and LRU access patterns. When it is time to type-check a batch of packages, gopls needs construct a FileSet that may contain preexisting token.Files from the parse cache. The complete set of files is not known at construction time; they are added piecemeal over a sequence of operations. (Gopls takes care to divide up the "address space" to ensure that all cached files use disjoint ranges.) Currently the only way to populate a FileSet is to call AddFile to reserve a block of positions for each file, but this must be done sequentially so that the FileSet's internal table is in ascending Pos order. Therefore gopls has for some time relied on a backdoor (unsafe) version of the proposed function below.
Proposal: We propose to add a (*FileSet).AddFiles method, defined as follows:
package token
// AddFiles adds the specified files to the FileSet if they
// are not already present. The caller must ensure that no
// pair of Files that would appear in the resulting FileSet overlap.
func (fset *token.FileSet) AddFiles(files ...*token.File) {
// Implementation: combine fset.files with files, sort, de-dup, check for overlap, and update fset.files.
}
Note: the proposed name change from AddFiles to AddExistingFiles during review.
@findleyr @jba
Comment From: findleyr
This looks like the correct API, based on my experience with this in gopls. Thanks for filing this upstream.
Comment From: gopherbot
Change https://go.dev/cl/663596 mentions this issue: internal/tokeninternal: AddExistingFiles: tweaks for proposal
Comment From: acehinnnqru
Is this a feature under working? Or can I try to work on it?
Comment From: findleyr
@acehinnnqru thanks, but the implementation is straightforward, so we'll add it if/when the proposal is accepted.
Comment From: aclements
Based on the discussion above, this proposal seems like a likely accept. — aclements for the proposal review group
The proposal is given in the top comment.
Comment From: aclements
No change in consensus, so accepted. 🎉 This issue now tracks the work of implementing the proposal. — aclements for the proposal review group
The proposal is given in the top comment.
Comment From: gopherbot
Change https://go.dev/cl/672875 mentions this issue: go/token: add FileSet.AddFiles
Comment From: gopherbot
Change https://go.dev/cl/672618 mentions this issue: internal/tokeninternal: use go1.25's FileSet.AddFiles
Comment From: adonovan
@findleyr suggested during review of https://go.dev/cl/672875 that we call the new method AddExistingFiles (the name we originally used for this operation within gopls) on the grounds that it is not the plural of AddFile; and he's right. So that's the name I went with.
Comment From: findleyr
Thanks @adonovan, and sorry for missing this earlier (it is only when I was reviewing the implementation relative to AddFile that the asymmetry stared me in the face).
I think AddExistingFiles is the right name.
Comment From: adonovan
The current implementation of AddExistingFiles has a serious performance problem (it's quadratic when called repeatedly) that explains a number of reports we've had from gopls users. The benchmark in https://go.dev/cl/675875 shows the problem clearly. The fix in https://go.dev/cl/675736, which uses an ordered map (tree) instead of an array is asymptotically optimal, and runs about 1000x faster. Since this bug cannot be fixed in gopls (because it cannot change FileSet internals), I think this performance problem qualifies as a bug, and justifies landing the fix in the latter CL even during the go1.25 freeze. Any objections @dr2chase ?
Formal freeze exception request is here: https://github.com/golang/go/issues/73851
Comment From: gopherbot
Change https://go.dev/cl/675736 mentions this issue: go/token: FileSet: hold Files in a balanced tree
Comment From: gopherbot
Change https://go.dev/cl/675955 mentions this issue: internal/tokeninternal: tag AddExistingFiles for go1.24
Comment From: gopherbot
Change https://go.dev/cl/678895 mentions this issue: all: update golang.org/x dependencies
Comment From: gopherbot
Change https://go.dev/cl/679115 mentions this issue: go.mod: update tagx:ignore'd golang.org/x dependencies
Comment From: gopherbot
Change https://go.dev/cl/679037 mentions this issue: go.mod: update golang.org/x dependencies
Comment From: aclements
@adonovan , should this issue be re-closed now?