gopls/internal/lsp/cache: evaluate imports lazily in TypeCheck Now that we do not need a static importMap for importing, and do not need to eagerly parse or load export data, we can evaluate imported packages lazily during type-checking, thereby avoiding importing packages that will not be used. This has a mild beneficial impact on benchmarks (because iimporting is already cheap). The other direction -- avoiding invalidating packages that are unaffected by changes -- should have a more significant impact. For golang/go#57987 Change-Id: I894656af9ca8dea286b6be55f83c4b6bffaaf110 Reviewed-on: https://go-review.googlesource.com/c/tools/+/473166 TryBot-Result: Gopher Robot <gobot@golang.org> Reviewed-by: Alan Donovan <adonovan@google.com> gopls-CI: kokoro <noreply+kokoro@google.com> Run-TryBot: Robert Findley <rfindley@google.com>
diff --git a/gopls/internal/lsp/cache/check.go b/gopls/internal/lsp/cache/check.go index 529940a..a717268 100644 --- a/gopls/internal/lsp/cache/check.go +++ b/gopls/internal/lsp/cache/check.go
@@ -11,7 +11,6 @@ "go/ast" "go/token" "go/types" - "log" "regexp" "runtime" "sort" @@ -64,8 +63,8 @@ // In fact, parsedFiles may be counter-productive due to pinning all files in // memory during large operations. parsedFiles map[span.URI]*source.ParsedGoFile // parsed files necessary for type-checking - imports map[PackageID]pkgOrErr // types.Packages to use for importing packages map[PackageID]*Package + errors map[PackageID]error // lazily allocated } type pkgOrErr struct { @@ -85,14 +84,12 @@ func (s *snapshot) TypeCheck(ctx context.Context, ids ...PackageID) ([]source.Package, error) { // Shared state for efficient type-checking. b := &typeCheckBatch{ - fset: fileSetWithBase(reservedForParsing), - parseCache: s.parseCache, - cpulimit: make(chan struct{}, runtime.GOMAXPROCS(0)), - needSyntax: make(map[PackageID]bool), - - parsedFiles: make(map[span.URI]*source.ParsedGoFile), + fset: fileSetWithBase(reservedForParsing), + parseCache: s.parseCache, + cpulimit: make(chan struct{}, runtime.GOMAXPROCS(0)), + needSyntax: make(map[PackageID]bool), promises: make(map[PackageID]*memoize.Promise), - imports: make(map[PackageID]pkgOrErr), + parsedFiles: make(map[span.URI]*source.ParsedGoFile), packages: make(map[PackageID]*Package), } @@ -155,11 +152,15 @@ debugName := fmt.Sprintf("check(%s)", id) b.promises[id] = memoize.NewPromise(debugName, func(ctx context.Context, _ interface{}) interface{} { pkg, err := b.processPackage(ctx, ph) - - b.mu.Lock() - b.imports[m.ID] = pkgOrErr{pkg, err} - b.mu.Unlock() - return nil + if err != nil { + b.mu.Lock() + if b.errors == nil { + b.errors = make(map[PackageID]error) + } + b.errors[id] = err + b.mu.Unlock() + } + return pkgOrErr{pkg, err} }) return nil } @@ -169,16 +170,14 @@ // -- await type-checking. -- // - // Start a single goroutine for each promise. + // Start a single goroutine for each syntax package. + // + // Other promises are reached recursively, and will not be evaluated if they + // are not needed. { var g errgroup.Group - // TODO(rfindley): find a good way to limit concurrency of type-checking, - // which is CPU bound at this point. - // - // (calling g.SetLimit here is mostly ineffective, as promises are - // recursively concurrent.) - for _, promise := range b.promises { - promise := promise + for id := range b.needSyntax { + promise := b.promises[id] g.Go(func() error { _, err := promise.Get(ctx, nil) return err @@ -195,7 +194,7 @@ if pkgs[i] != nil { continue } - if err := b.imports[id].err; err != nil { + if err := b.errors[id]; err != nil { if firstErr == nil { firstErr = err } @@ -258,24 +257,29 @@ // type-checking for syntax, depending on the requested syntax packages and // available export data. func (b *typeCheckBatch) processPackage(ctx context.Context, ph *packageHandle) (*types.Package, error) { - if err := b.awaitPredecessors(ctx, ph.m); err != nil { - return nil, err - } - - // Wait to acquire CPU token. + // Type-check at most b.cpulimit syntax packages concurrently. // - // Note: it is important to acquire this token only after awaiting - // predecessors, to avoid a starvation lock. - select { - case <-ctx.Done(): - return nil, ctx.Err() - case b.cpulimit <- struct{}{}: - defer func() { - <-b.cpulimit // release CPU token - }() - } - + // (For a non-syntax package, it is not necessary to await all + // predecessors because decoding export data typically only + // demands a small subset of all possible dependencies.) if b.needSyntax[ph.m.ID] { + if err := b.awaitPredecessors(ctx, ph.m); err != nil { + return nil, err + } + + // Wait to acquire CPU token. + // + // Note: it is important to acquire this token only after awaiting + // predecessors, to avoid a starvation lock. + select { + case <-ctx.Done(): + return nil, ctx.Err() + case b.cpulimit <- struct{}{}: + defer func() { + <-b.cpulimit // release CPU token + }() + } + // We need a syntax package. syntaxPkg, err := b.checkPackage(ctx, ph) if err != nil { @@ -306,18 +310,43 @@ // importPackage loads the given package from its export data in p.exportData // (which must already be populated). func (b *typeCheckBatch) importPackage(ctx context.Context, m *source.Metadata, data []byte) (*types.Package, error) { - impMap, errMap := b.importMap(m.ID) - // Any failure to populate an import will cause confusing errors from - // IImportShallow below. - for path, err := range errMap { - return nil, fmt.Errorf("error importing %q for %q: %v", path, m.ID, err) + impMap := b.importMap(m.ID) + + var firstErr error + thisPackage := types.NewPackage(string(m.PkgPath), string(m.Name)) + getPackage := func(path, name string) *types.Package { + if path == string(m.PkgPath) { + return thisPackage + } + + promise := impMap[path] + v, err := promise.Get(ctx, nil) + if err == nil { + result := v.(pkgOrErr) + err = result.err + if err == nil { + return result.pkg + } + } + // inv: err != nil + if firstErr == nil { + firstErr = err + } + + // Context cancellation, or a very bad error such as a file permission + // error. + // + // Returning nil here will cause the import to fail (and panic if + // gcimporter.debug is set), but that is preferable to the confusing errors + // produced when shallow import encounters an empty package. + return nil } // TODO(rfindley): collect "deep" hashes here using the provided // callback, for precise pruning. - imported, err := gcimporter.IImportShallow(b.fset, gcimporter.GetPackageFromMap(impMap), data, string(m.PkgPath), func(*types.Package, string) {}) + imported, err := gcimporter.IImportShallow(b.fset, getPackage, data, string(m.PkgPath), func(*types.Package, string) {}) if err != nil { - return nil, bug.Errorf("invalid export data for %q: %v", m.ID, err) + return nil, fmt.Errorf("import failed for %q: %v", m.ID, err) } return imported, nil } @@ -325,16 +354,16 @@ // checkPackageForImport type checks, but skips function bodies and does not // record syntax information. func (b *typeCheckBatch) checkPackageForImport(ctx context.Context, ph *packageHandle) (*types.Package, error) { - impMap, errMap := b.importMap(ph.inputs.id) onError := func(e error) { // Ignore errors for exporting. } - cfg := b.typesConfig(ph.inputs, onError, impMap, errMap) + cfg := b.typesConfig(ctx, ph.inputs, onError) + cfg.IgnoreFuncBodies = true + pgfs, err := b.parseFiles(ctx, ph.inputs.compiledGoFiles) if err != nil { return nil, err } - cfg.IgnoreFuncBodies = true pkg := types.NewPackage(string(ph.inputs.pkgPath), string(ph.inputs.name)) check := types.NewChecker(cfg, b.fset, pkg, nil) @@ -404,32 +433,25 @@ // error if awaiting failed due to context cancellation or if there was an // unrecoverable error loading export data. func (b *typeCheckBatch) awaitPredecessors(ctx context.Context, m *source.Metadata) error { + // await predecessors concurrently, as some of them may be non-syntax + // packages, and therefore will not have been started by the type-checking + // batch. + var g errgroup.Group for _, depID := range m.DepsByPkgPath { - depID := depID if p, ok := b.promises[depID]; ok { - if _, err := p.Get(ctx, nil); err != nil { + g.Go(func() error { + _, err := p.Get(ctx, nil) return err - } + }) } } - return nil + return g.Wait() } // importMap returns an import map for the given package ID, populated with -// type-checked packages for its dependencies. It is intended for compatibility -// with gcimporter.IImportShallow, so the first result uses the map signature -// of that API, where keys are package path strings. -// -// importMap must only be used once all promises for dependencies of id have -// been awaited. -// -// For any missing packages, importMap returns an entry in the resulting errMap -// reporting the error for that package. -// -// Invariant: for all recursive dependencies, either impMap[path] or -// errMap[path] is set. -func (b *typeCheckBatch) importMap(id PackageID) (impMap map[string]*types.Package, errMap map[PackagePath]error) { - impMap = make(map[string]*types.Package) +// promises keyed by package path for its dependencies. +func (b *typeCheckBatch) importMap(id PackageID) map[string]*memoize.Promise { + impMap := make(map[string]*memoize.Promise) outerID := id var populateDepsOf func(m *source.Metadata) populateDepsOf = func(parent *source.Metadata) { @@ -438,35 +460,17 @@ if _, ok := impMap[string(m.PkgPath)]; ok { continue } - if _, ok := errMap[m.PkgPath]; ok { - continue - } - b.mu.Lock() - result, ok := b.imports[m.ID] - b.mu.Unlock() + promise, ok := b.promises[m.ID] if !ok { panic(fmt.Sprintf("import map for %q missing package data for %q", outerID, m.ID)) } - // We may fail to produce a package due to e.g. context cancellation - // (handled elsewhere), or some catastrophic failure such as a package with - // no files. - switch { - case result.err != nil: - if errMap == nil { - errMap = make(map[PackagePath]error) - } - errMap[m.PkgPath] = result.err - case result.pkg != nil: - impMap[string(m.PkgPath)] = result.pkg - default: - panic("invalid import for " + id) - } + impMap[string(m.PkgPath)] = promise populateDepsOf(m) } } m := b.meta.metadata[id] populateDepsOf(m) - return impMap, errMap + return impMap } // packageData holds binary data (e.g. types, xrefs) extracted from a syntax @@ -862,7 +866,6 @@ var goVersionRx = regexp.MustCompile(`^go([1-9][0-9]*)\.(0|[1-9][0-9]*)$`) func doTypeCheck(ctx context.Context, b *typeCheckBatch, inputs typeCheckInputs) (*syntaxPackage, error) { - impMap, errMap := b.importMap(inputs.id) pkg := &syntaxPackage{ id: inputs.id, fset: b.fset, // must match parse call below @@ -875,7 +878,6 @@ Selections: make(map[*ast.SelectorExpr]*types.Selection), Scopes: make(map[ast.Node]*types.Scope), }, - importMap: impMap, } typeparams.InitInstanceInfo(pkg.typesInfo) @@ -916,7 +918,7 @@ onError := func(e error) { pkg.typeErrors = append(pkg.typeErrors, e.(types.Error)) } - cfg := b.typesConfig(inputs, onError, impMap, errMap) + cfg := b.typesConfig(ctx, inputs, onError) check := types.NewChecker(cfg, pkg.fset, pkg.types, pkg.typesInfo) @@ -933,10 +935,26 @@ if ctx.Err() != nil { return nil, ctx.Err() } + + // Collect imports by package path for the DependencyTypes API. + pkg.importMap = make(map[PackagePath]*types.Package) + var collectDeps func(*types.Package) + collectDeps = func(p *types.Package) { + pkgPath := PackagePath(p.Path()) + if _, ok := pkg.importMap[pkgPath]; ok { + return + } + pkg.importMap[pkgPath] = p + for _, imp := range p.Imports() { + collectDeps(imp) + } + } + collectDeps(pkg.types) + return pkg, nil } -func (b *typeCheckBatch) typesConfig(inputs typeCheckInputs, onError func(e error), impMap map[string]*types.Package, errMap map[PackagePath]error) *types.Config { +func (b *typeCheckBatch) typesConfig(ctx context.Context, inputs typeCheckInputs, onError func(e error)) *types.Config { cfg := &types.Config{ Sizes: inputs.sizes, Error: onError, @@ -960,15 +978,19 @@ if !source.IsValidImport(inputs.pkgPath, depPH.m.PkgPath) { return nil, fmt.Errorf("invalid use of internal package %q", path) } - pkg, ok := impMap[string(depPH.m.PkgPath)] + promise, ok := b.promises[id] if !ok { - err := errMap[depPH.m.PkgPath] - if err == nil { - log.Fatalf("neither pkg nor error is set") - } + panic("missing import") + } + v, err := promise.Get(ctx, nil) + if err != nil { + // Context cancellation: note that this could lead to non-deterministic + // results in the type-checker, so it is important that we don't use + // any type-checking results in the case where ctx is cancelled. return nil, err } - return pkg, nil + res := v.(pkgOrErr) + return res.pkg, res.err }), }
diff --git a/gopls/internal/lsp/cache/pkg.go b/gopls/internal/lsp/cache/pkg.go index 910aeeb..cb7b2dc 100644 --- a/gopls/internal/lsp/cache/pkg.go +++ b/gopls/internal/lsp/cache/pkg.go
@@ -51,9 +51,9 @@ typeErrors []types.Error types *types.Package typesInfo *types.Info - importMap map[string]*types.Package // keys are PackagePaths - hasFixedFiles bool // if true, AST was sufficiently mangled that we should hide type errors - analyses memoize.Store // maps analyzer.Name to Promise[actionResult] + importMap map[PackagePath]*types.Package + hasFixedFiles bool // if true, AST was sufficiently mangled that we should hide type errors + analyses memoize.Store // maps analyzer.Name to Promise[actionResult] xrefs []byte methodsets *methodsets.Index } @@ -129,10 +129,7 @@ // dependencies of p, or if no symbols from that package were // referenced during the type-checking of p. func (p *Package) DependencyTypes(path source.PackagePath) *types.Package { - if path == p.m.PkgPath { - return p.pkg.types - } - return p.pkg.importMap[string(path)] + return p.pkg.importMap[path] } func (p *Package) HasParseErrors() bool {
diff --git a/internal/gcimporter/iexport.go b/internal/gcimporter/iexport.go index bcb715a..a0dc0b5 100644 --- a/internal/gcimporter/iexport.go +++ b/internal/gcimporter/iexport.go
@@ -44,12 +44,12 @@ return out.Bytes(), err } -// IImportShallow decodes "shallow" types.Package data encoded by IExportShallow -// in the same executable. This function cannot import data from +// IImportShallow decodes "shallow" types.Package data encoded by +// IExportShallow in the same executable. This function cannot import data from // cmd/compile or gcexportdata.Write. -func IImportShallow(fset *token.FileSet, importFunc func(path, name string) *types.Package, data []byte, path string, insert InsertType) (*types.Package, error) { +func IImportShallow(fset *token.FileSet, getPackage GetPackageFunc, data []byte, path string, insert InsertType) (*types.Package, error) { const bundle = false - pkgs, err := iimportCommon(fset, importFunc, data, bundle, path, insert) + pkgs, err := iimportCommon(fset, getPackage, data, bundle, path, insert) if err != nil { return nil, err }
diff --git a/internal/gcimporter/iimport.go b/internal/gcimporter/iimport.go index 22698a0..be6dace 100644 --- a/internal/gcimporter/iimport.go +++ b/internal/gcimporter/iimport.go
@@ -97,12 +97,13 @@ return iimportCommon(fset, GetPackageFromMap(imports), data, true, "", nil) } -// A GetPackageFunc is a function that gets the package with -// the given path from the importer state, creating it -// (with the specified name) if necessary. +// A GetPackageFunc is a function that gets the package with the given path +// from the importer state, creating it (with the specified name) if necessary. // It is an abstraction of the map historically used to memoize package creation. // // Two calls with the same path must return the same package. +// +// If the given getPackage func returns nil, the import will fail. type GetPackageFunc = func(path, name string) *types.Package // GetPackageFromMap returns a GetPackageFunc that retrieves packages from the @@ -119,10 +120,6 @@ } } -// iimportCommon implements the core of the import algorithm. -// -// The given getPackage func must always return a non-nil package -// (see ImportFromMap for an example). func iimportCommon(fset *token.FileSet, getPackage GetPackageFunc, data []byte, bundle bool, path string, insert InsertType) (pkgs []*types.Package, err error) { const currentVersion = iexportVersionCurrent version := int64(-1)