1 files changed, 140 insertions, 0 deletions
diff --git a/gopls/internal/lsp/source/known_packages.go b/gopls/internal/lsp/source/known_packages.go
new file mode 100644
index 000000000..07b4c30a8
--- /dev/null
+++ b/gopls/internal/lsp/source/known_packages.go
@@ -0,0 +1,140 @@
+// 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"
+	"fmt"
+	"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.
+
+	// Find a Metadata containing the file.
+	metas, err := snapshot.MetadataForFile(ctx, fh.URI())
+	if err != nil {
+		return nil, err // e.g. context cancelled
+	}
+	if len(metas) == 0 {
+		return nil, fmt.Errorf("no loaded package contain file %s", fh.URI())
+	}
+	current := metas[0] // pick one arbitrarily (they should all have the same package path)
+
+	// Parse the file's imports so we can compute which
+	// PackagePaths are imported by this specific file.
+	src, err := fh.Read()
+	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 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(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
+}