| // Copyright 2020 The Go Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style |
| // license that can be found in the LICENSE file. |
| |
| package source |
| |
| import ( |
| "context" |
| "go/parser" |
| "go/token" |
| "sort" |
| "strings" |
| "sync" |
| "time" |
| |
| "golang.org/x/tools/internal/event" |
| "golang.org/x/tools/internal/imports" |
| ) |
| |
| // KnownPackagePaths returns a new list of package paths of all known |
| // packages in the package graph that could potentially be imported by |
| // the given file. The list is ordered lexicographically, except that |
| // all dot-free paths (standard packages) appear before dotful ones. |
| // |
| // It is part of the gopls.list_known_packages command. |
| func KnownPackagePaths(ctx context.Context, snapshot Snapshot, fh FileHandle) ([]PackagePath, error) { |
| // This algorithm is expressed in terms of Metadata, not Packages, |
| // so it doesn't cause or wait for type checking. |
| |
| current, err := NarrowestMetadataForFile(ctx, snapshot, fh.URI()) |
| if err != nil { |
| return nil, err // e.g. context cancelled |
| } |
| |
| // Parse the file's imports so we can compute which |
| // PackagePaths are imported by this specific file. |
| src, err := fh.Content() |
| if err != nil { |
| return nil, err |
| } |
| file, err := parser.ParseFile(token.NewFileSet(), fh.URI().Filename(), src, parser.ImportsOnly) |
| if err != nil { |
| return nil, err |
| } |
| imported := make(map[PackagePath]bool) |
| for _, imp := range file.Imports { |
| if id := current.DepsByImpPath[UnquoteImportPath(imp)]; id != "" { |
| if m := snapshot.Metadata(id); m != nil { |
| imported[m.PkgPath] = true |
| } |
| } |
| } |
| |
| // Now find candidates among all known packages. |
| knownPkgs, err := snapshot.AllMetadata(ctx) |
| if err != nil { |
| return nil, err |
| } |
| seen := make(map[PackagePath]bool) |
| for _, knownPkg := range knownPkgs { |
| // package main cannot be imported |
| if knownPkg.Name == "main" { |
| continue |
| } |
| // test packages cannot be imported |
| if knownPkg.ForTest != "" { |
| continue |
| } |
| // No need to import what the file already imports. |
| // This check is based on PackagePath, not PackageID, |
| // so that all test variants are filtered out too. |
| if imported[knownPkg.PkgPath] { |
| continue |
| } |
| // make sure internal packages are importable by the file |
| if !IsValidImport(current.PkgPath, knownPkg.PkgPath) { |
| continue |
| } |
| // naive check on cyclical imports |
| if isDirectlyCyclical(current, knownPkg) { |
| continue |
| } |
| // AllMetadata may have multiple variants of a pkg. |
| seen[knownPkg.PkgPath] = true |
| } |
| |
| // Augment the set by invoking the goimports algorithm. |
| if err := snapshot.RunProcessEnvFunc(ctx, func(ctx context.Context, o *imports.Options) error { |
| ctx, cancel := context.WithTimeout(ctx, time.Millisecond*80) |
| defer cancel() |
| var seenMu sync.Mutex |
| wrapped := func(ifix imports.ImportFix) { |
| seenMu.Lock() |
| defer seenMu.Unlock() |
| // TODO(adonovan): what if the actual package path has a vendor/ prefix? |
| seen[PackagePath(ifix.StmtInfo.ImportPath)] = true |
| } |
| return imports.GetAllCandidates(ctx, wrapped, "", fh.URI().Filename(), string(current.Name), o.Env) |
| }); err != nil { |
| // If goimports failed, proceed with just the candidates from the metadata. |
| event.Error(ctx, "imports.GetAllCandidates", err) |
| } |
| |
| // Sort lexicographically, but with std before non-std packages. |
| paths := make([]PackagePath, 0, len(seen)) |
| for path := range seen { |
| paths = append(paths, path) |
| } |
| sort.Slice(paths, func(i, j int) bool { |
| importI, importJ := paths[i], paths[j] |
| iHasDot := strings.Contains(string(importI), ".") |
| jHasDot := strings.Contains(string(importJ), ".") |
| if iHasDot != jHasDot { |
| return jHasDot // dot-free paths (standard packages) compare less |
| } |
| return importI < importJ |
| }) |
| |
| return paths, nil |
| } |
| |
| // isDirectlyCyclical checks if imported directly imports pkg. |
| // It does not (yet) offer a full cyclical check because showing a user |
| // a list of importable packages already generates a very large list |
| // and having a few false positives in there could be worth the |
| // performance snappiness. |
| // |
| // TODO(adonovan): ensure that metadata graph is always cyclic! |
| // Many algorithms will get confused or even stuck in the |
| // presence of cycles. Then replace this function by 'false'. |
| func isDirectlyCyclical(pkg, imported *Metadata) bool { |
| _, ok := imported.DepsByPkgPath[pkg.PkgPath] |
| return ok |
| } |