cmd/go/internal/modload: rework import resolution

modload.Import previously performed two otherwise-separable tasks:

1. Identify which module in the build list contains the requested
   package.

2. If no such module exists, search available modules to try to find
   the missing package.

This change splits those two tasks into two separate unexported
functions, and reports import-resolution errors by attaching them to
the package rather than emitting them directly to stderr. That allows
'list' to report the errors, but 'list -e' to ignore them.

With the two tasks now separate, it will be easier to avoid the
overhead of resolving missing packages during lazy loading if we
discover that some existing dependency needs to be promoted to the top
level (potentially altering the main module's selected versions, and
thus suppling packages that were previously missing).

For #36460
Updates #26909

Change-Id: I32bd853b266d7cd231d1f45f92b0650d95c4bcbd
Reviewed-on: https://go-review.googlesource.com/c/go/+/251445
Run-TryBot: Bryan C. Mills <bcmills@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Jay Conrod <jayconrod@google.com>
Reviewed-by: Michael Matloob <matloob@golang.org>

8 files changed, 158 insertions, 80 deletions

diff --git a/src/cmd/go/internal/list/list.go b/src/cmd/go/internal/list/list.go
index 6d81c1cad1..65003dc883 100644
--- a/src/cmd/go/internal/list/list.go
+++ b/src/cmd/go/internal/list/list.go
@@ -545,7 +545,7 @@ func runList(ctx context.Context, cmd *base.Command, args []string) {
 		// Note that -deps is applied after -test,
 		// so that you only get descriptions of tests for the things named
 		// explicitly on the command line, not for all dependencies.
-		pkgs = load.PackageList(pkgs)
+		pkgs = loadPackageList(pkgs)
 	}
 
 	// Do we need to run a build to gather information?
@@ -580,7 +580,7 @@ func runList(ctx context.Context, cmd *base.Command, args []string) {
 	if *listTest {
 		all := pkgs
 		if !*listDeps {
-			all = load.PackageList(pkgs)
+			all = loadPackageList(pkgs)
 		}
 		// Update import paths to distinguish the real package p
 		// from p recompiled for q.test.
@@ -697,6 +697,23 @@ func runList(ctx context.Context, cmd *base.Command, args []string) {
 	}
 }
 
+// loadPackageList is like load.PackageList, but prints error messages and exits
+// with nonzero status if listE is not set and any package in the expanded list
+// has errors.
+func loadPackageList(roots []*load.Package) []*load.Package {
+	pkgs := load.PackageList(roots)
+
+	if !*listE {
+		for _, pkg := range pkgs {
+			if pkg.Error != nil {
+				base.Errorf("%v", pkg.Error)
+			}
+		}
+	}
+
+	return pkgs
+}
+
 // TrackingWriter tracks the last byte written on every write so
 // we can avoid printing a newline if one was already written or
 // if there is no output at all.
diff --git a/src/cmd/go/internal/modload/import.go b/src/cmd/go/internal/modload/import.go
index 6459e716b7..e04d66c5b1 100644
--- a/src/cmd/go/internal/modload/import.go
+++ b/src/cmd/go/internal/modload/import.go
@@ -26,6 +26,8 @@ import (
 	"golang.org/x/mod/semver"
 )
 
+var errImportMissing = errors.New("import missing")
+
 type ImportMissingError struct {
 	Path     string
 	Module   module.Version
@@ -48,6 +50,11 @@ func (e *ImportMissingError) Error() string {
 		}
 		return "cannot find module providing package " + e.Path
 	}
+
+	if e.newMissingVersion != "" {
+		return fmt.Sprintf("package %s provided by %s at latest version %s but not at required version %s", e.Path, e.Module.Path, e.Module.Version, e.newMissingVersion)
+	}
+
 	return fmt.Sprintf("missing module for import: %s@%s provides %s", e.Module.Path, e.Module.Version, e.Path)
 }
 
@@ -100,18 +107,20 @@ func (e *AmbiguousImportError) Error() string {
 
 var _ load.ImportPathError = &AmbiguousImportError{}
 
-// Import finds the module and directory in the build list
-// containing the package with the given import path.
-// The answer must be unique: Import returns an error
-// if multiple modules attempt to provide the same package.
-// Import can return a module with an empty m.Path, for packages in the standard library.
-// Import can return an empty directory string, for fake packages like "C" and "unsafe".
+// importFromBuildList finds the module and directory in the build list
+// containing the package with the given import path. The answer must be unique:
+// importFromBuildList returns an error if multiple modules attempt to provide
+// the same package.
+//
+// importFromBuildList can return a module with an empty m.Path, for packages in
+// the standard library.
+//
+// importFromBuildList can return an empty directory string, for fake packages
+// like "C" and "unsafe".
 //
 // If the package cannot be found in the current build list,
-// Import returns an ImportMissingError as the error.
-// If Import can identify a module that could be added to supply the package,
-// the ImportMissingError records that module.
-func Import(ctx context.Context, path string) (m module.Version, dir string, err error) {
+// importFromBuildList returns errImportMissing as the error.
+func importFromBuildList(ctx context.Context, path string) (m module.Version, dir string, err error) {
 	if strings.Contains(path, "@") {
 		return module.Version{}, "", fmt.Errorf("import path should not have @version")
 	}
@@ -190,8 +199,14 @@ func Import(ctx context.Context, path string) (m module.Version, dir string, err
 		return module.Version{}, "", &AmbiguousImportError{importPath: path, Dirs: dirs, Modules: mods}
 	}
 
-	// Look up module containing the package, for addition to the build list.
-	// Goal is to determine the module, download it to dir, and return m, dir, ErrMissing.
+	return module.Version{}, "", errImportMissing
+}
+
+// queryImport attempts to locate a module that can be added to the current
+// build list to provide the package with the given import path.
+func queryImport(ctx context.Context, path string) (module.Version, error) {
+	pathIsStd := search.IsStandardImportPath(path)
+
 	if cfg.BuildMod == "readonly" {
 		var queryErr error
 		if !pathIsStd {
@@ -201,10 +216,10 @@ func Import(ctx context.Context, path string) (m module.Version, dir string, err
 				queryErr = fmt.Errorf("import lookup disabled by -mod=%s\n\t(%s)", cfg.BuildMod, cfg.BuildModReason)
 			}
 		}
-		return module.Version{}, "", &ImportMissingError{Path: path, QueryErr: queryErr}
+		return module.Version{}, &ImportMissingError{Path: path, QueryErr: queryErr}
 	}
 	if modRoot == "" && !allowMissingModuleImports {
-		return module.Version{}, "", &ImportMissingError{
+		return module.Version{}, &ImportMissingError{
 			Path:     path,
 			QueryErr: errors.New("working directory is not part of a module"),
 		}
@@ -226,7 +241,7 @@ func Import(ctx context.Context, path string) (m module.Version, dir string, err
 			}
 		}
 
-		mods = make([]module.Version, 0, len(latest))
+		mods := make([]module.Version, 0, len(latest))
 		for p, v := range latest {
 			// If the replacement didn't specify a version, synthesize a
 			// pseudo-version with an appropriate major version and a timestamp below
@@ -252,19 +267,19 @@ func Import(ctx context.Context, path string) (m module.Version, dir string, err
 			root, isLocal, err := fetch(ctx, m)
 			if err != nil {
 				// Report fetch error as above.
-				return module.Version{}, "", err
+				return module.Version{}, err
 			}
 			if _, ok, err := dirInModule(path, m.Path, root, isLocal); err != nil {
-				return m, "", err
+				return m, err
 			} else if ok {
-				return m, "", &ImportMissingError{Path: path, Module: m}
+				return m, nil
 			}
 		}
 		if len(mods) > 0 && module.CheckPath(path) != nil {
 			// The package path is not valid to fetch remotely,
 			// so it can only exist if in a replaced module,
 			// and we know from the above loop that it is not.
-			return module.Version{}, "", &PackageNotInModuleError{
+			return module.Version{}, &PackageNotInModuleError{
 				Mod:         mods[0],
 				Query:       "latest",
 				Pattern:     path,
@@ -281,7 +296,7 @@ func Import(ctx context.Context, path string) (m module.Version, dir string, err
 		// QueryPackage cannot possibly find a module containing this package.
 		//
 		// Instead of trying QueryPackage, report an ImportMissingError immediately.
-		return module.Version{}, "", &ImportMissingError{Path: path}
+		return module.Version{}, &ImportMissingError{Path: path}
 	}
 
 	fmt.Fprintf(os.Stderr, "go: finding module for package %s\n", path)
@@ -291,12 +306,13 @@ func Import(ctx context.Context, path string) (m module.Version, dir string, err
 		if errors.Is(err, os.ErrNotExist) {
 			// Return "cannot find module providing package […]" instead of whatever
 			// low-level error QueryPackage produced.
-			return module.Version{}, "", &ImportMissingError{Path: path, QueryErr: err}
+			return module.Version{}, &ImportMissingError{Path: path, QueryErr: err}
 		} else {
-			return module.Version{}, "", err
+			return module.Version{}, err
 		}
 	}
-	m = candidates[0].Mod
+
+	m := candidates[0].Mod
 	newMissingVersion := ""
 	for _, c := range candidates {
 		cm := c.Mod
@@ -310,13 +326,20 @@ func Import(ctx context.Context, path string) (m module.Version, dir string, err
 				// version (e.g., v1.0.0) of a module, but we have a newer version
 				// of the same module in the build list (e.g., v1.0.1-beta), and
 				// the package is not present there.
+				//
+				// TODO(#41113): This is probably incorrect when there are multiple
+				// candidates, such as when a nested module is split out but only one
+				// half of the split is tagged.
 				m = cm
 				newMissingVersion = bm.Version
 				break
 			}
 		}
 	}
-	return m, "", &ImportMissingError{Path: path, Module: m, newMissingVersion: newMissingVersion}
+	if newMissingVersion != "" {
+		return m, &ImportMissingError{Path: path, Module: m, newMissingVersion: newMissingVersion}
+	}
+	return m, nil
 }
 
 // maybeInModule reports whether, syntactically,
diff --git a/src/cmd/go/internal/modload/import_test.go b/src/cmd/go/internal/modload/import_test.go
index 47ce89a084..22d5b82e21 100644
--- a/src/cmd/go/internal/modload/import_test.go
+++ b/src/cmd/go/internal/modload/import_test.go
@@ -10,15 +10,20 @@ import (
 	"regexp"
 	"strings"
 	"testing"
+
+	"golang.org/x/mod/module"
 )
 
 var importTests = []struct {
 	path string
+	m    module.Version
 	err  string
 }{
 	{
 		path: "golang.org/x/net/context",
-		err:  "missing module for import: golang.org/x/net@.* provides golang.org/x/net/context",
+		m: module.Version{
+			Path: "golang.org/x/net",
+		},
 	},
 	{
 		path: "golang.org/x/net",
@@ -26,15 +31,23 @@ var importTests = []struct {
 	},
 	{
 		path: "golang.org/x/text",
-		err:  "missing module for import: golang.org/x/text@.* provides golang.org/x/text",
+		m: module.Version{
+			Path: "golang.org/x/text",
+		},
 	},
 	{
 		path: "github.com/rsc/quote/buggy",
-		err:  "missing module for import: github.com/rsc/quote@v1.5.2 provides github.com/rsc/quote/buggy",
+		m: module.Version{
+			Path:    "github.com/rsc/quote",
+			Version: "v1.5.2",
+		},
 	},
 	{
 		path: "github.com/rsc/quote",
-		err:  "missing module for import: github.com/rsc/quote@v1.5.2 provides github.com/rsc/quote",
+		m: module.Version{
+			Path:    "github.com/rsc/quote",
+			Version: "v1.5.2",
+		},
 	},
 	{
 		path: "golang.org/x/foo/bar",
@@ -42,7 +55,7 @@ var importTests = []struct {
 	},
 }
 
-func TestImport(t *testing.T) {
+func TestQueryImport(t *testing.T) {
 	testenv.MustHaveExternalNetwork(t)
 	testenv.MustHaveExecPath(t, "git")
 	defer func(old bool) {
@@ -55,12 +68,23 @@ func TestImport(t *testing.T) {
 	for _, tt := range importTests {
 		t.Run(strings.ReplaceAll(tt.path, "/", "_"), func(t *testing.T) {
 			// Note that there is no build list, so Import should always fail.
-			m, dir, err := Import(ctx, tt.path)
-			if err == nil {
-				t.Fatalf("Import(%q) = %v, %v, nil; expected error", tt.path, m, dir)
+			m, err := queryImport(ctx, tt.path)
+
+			if tt.err == "" {
+				if err != nil {
+					t.Fatalf("queryImport(_, %q): %v", tt.path, err)
+				}
+			} else {
+				if err == nil {
+					t.Fatalf("queryImport(_, %q) = %v, nil; expected error", tt.path, m)
+				}
+				if !regexp.MustCompile(tt.err).MatchString(err.Error()) {
+					t.Fatalf("queryImport(_, %q): error %q, want error matching %#q", tt.path, err, tt.err)
+				}
 			}
-			if !regexp.MustCompile(tt.err).MatchString(err.Error()) {
-				t.Fatalf("Import(%q): error %q, want error matching %#q", tt.path, err, tt.err)
+
+			if m.Path != tt.m.Path || (tt.m.Version != "" && m.Version != tt.m.Version) {
+				t.Errorf("queryImport(_, %q) = %v, _; want %v", tt.path, m, tt.m)
 			}
 		})
 	}
diff --git a/src/cmd/go/internal/modload/load.go b/src/cmd/go/internal/modload/load.go
index 8a3af534a5..2096dfb636 100644
--- a/src/cmd/go/internal/modload/load.go
+++ b/src/cmd/go/internal/modload/load.go
@@ -881,7 +881,7 @@ func loadFromRoots(params loaderParams) *loader {
 
 		ld.buildStacks()
 
-		modAddedBy := resolveMissingImports(addedModuleFor, ld.pkgs)
+		modAddedBy := ld.resolveMissingImports(addedModuleFor)
 		if len(modAddedBy) == 0 {
 			break
 		}
@@ -937,38 +937,45 @@ func loadFromRoots(params loaderParams) *loader {
 // The newly-resolved packages are added to the addedModuleFor map, and
 // resolveMissingImports returns a map from each newly-added module version to
 // the first package for which that module was added.
-func resolveMissingImports(addedModuleFor map[string]bool, pkgs []*loadPkg) (modAddedBy map[module.Version]*loadPkg) {
-	haveMod := make(map[module.Version]bool)
-	for _, m := range buildList {
-		haveMod[m] = true
-	}
-
-	modAddedBy = make(map[module.Version]*loadPkg)
-	for _, pkg := range pkgs {
+func (ld *loader) resolveMissingImports(addedModuleFor map[string]bool) (modAddedBy map[module.Version]*loadPkg) {
+	var needPkgs []*loadPkg
+	for _, pkg := range ld.pkgs {
 		if pkg.isTest() {
 			// If we are missing a test, we are also missing its non-test version, and
 			// we should only add the missing import once.
 			continue
 		}
-		if err, ok := pkg.err.(*ImportMissingError); ok && err.Module.Path != "" {
-			if err.newMissingVersion != "" {
-				base.Fatalf("go: %s: package provided by %s at latest version %s but not at required version %s", pkg.stackText(), err.Module.Path, err.Module.Version, err.newMissingVersion)
-			}
-			fmt.Fprintf(os.Stderr, "go: found %s in %s %s\n", pkg.path, err.Module.Path, err.Module.Version)
-			if addedModuleFor[pkg.path] {
-				base.Fatalf("go: %s: looping trying to add package", pkg.stackText())
-			}
-			addedModuleFor[pkg.path] = true
-			if !haveMod[err.Module] {
-				haveMod[err.Module] = true
-				modAddedBy[err.Module] = pkg
-				buildList = append(buildList, err.Module)
-			}
+		if pkg.err != errImportMissing {
+			// Leave other errors for Import or load.Packages to report.
 			continue
 		}
-		// Leave other errors for Import or load.Packages to report.
+
+		needPkgs = append(needPkgs, pkg)
+
+		pkg := pkg
+		ld.work.Add(func() {
+			pkg.mod, pkg.err = queryImport(context.TODO(), pkg.path)
+		})
+	}
+	<-ld.work.Idle()
+
+	modAddedBy = map[module.Version]*loadPkg{}
+	for _, pkg := range needPkgs {
+		if pkg.err != nil {
+			continue
+		}
+
+		fmt.Fprintf(os.Stderr, "go: found %s in %s %s\n", pkg.path, pkg.mod.Path, pkg.mod.Version)
+		if addedModuleFor[pkg.path] {
+			// TODO(bcmills): This should only be an error if pkg.mod is the same
+			// version we already tried to add previously.
+			base.Fatalf("go: %s: looping trying to add package", pkg.stackText())
+		}
+		if modAddedBy[pkg.mod] == nil {
+			modAddedBy[pkg.mod] = pkg
+			buildList = append(buildList, pkg.mod)
+		}
 	}
-	base.ExitIfErrors()
 
 	return modAddedBy
 }
@@ -1079,7 +1086,7 @@ func (ld *loader) load(pkg *loadPkg) {
 		return
 	}
 
-	pkg.mod, pkg.dir, pkg.err = Import(context.TODO(), pkg.path)
+	pkg.mod, pkg.dir, pkg.err = importFromBuildList(context.TODO(), pkg.path)
 	if pkg.dir == "" {
 		return
 	}
diff --git a/src/cmd/go/testdata/script/list_bad_import.txt b/src/cmd/go/testdata/script/list_bad_import.txt
index b8f9d586f3..dbec35069c 100644
--- a/src/cmd/go/testdata/script/list_bad_import.txt
+++ b/src/cmd/go/testdata/script/list_bad_import.txt
@@ -15,10 +15,11 @@ stdout 'incomplete'
 stdout 'bad dep: .*example.com[/\\]notfound'
 
 # Listing with -deps should also fail.
-# BUG: Today, it does not.
-# ! go list -deps example.com/direct
-# stderr example.com[/\\]notfound
-go list -deps example.com/direct
+! go list -deps example.com/direct
+stderr example.com[/\\]notfound
+
+# But -e -deps should succeed.
+go list -e -deps example.com/direct
 stdout example.com/notfound
 
 
@@ -31,10 +32,11 @@ stdout incomplete
 stdout 'bad dep: .*example.com[/\\]notfound'
 
 # Again, -deps should fail.
-# BUG: Again, it does not.
-# ! go list -deps example.com/indirect
-# stderr example.com[/\\]notfound
-go list -deps example.com/indirect
+! go list -deps example.com/indirect
+stderr example.com[/\\]notfound
+
+# But -deps -e should succeed.
+go list -e -deps example.com/indirect
 stdout example.com/notfound
 
 
diff --git a/src/cmd/go/testdata/script/list_test_err.txt b/src/cmd/go/testdata/script/list_test_err.txt
index a174b5e9ad..c6f1ecf400 100644
--- a/src/cmd/go/testdata/script/list_test_err.txt
+++ b/src/cmd/go/testdata/script/list_test_err.txt
@@ -22,6 +22,9 @@ go list -e -test -deps -f '{{.ImportPath}} {{.Error | printf "%q"}}' syntaxerr
 stdout 'pkgdep <nil>'
 stdout 'testdep_a <nil>'
 stdout 'testdep_b <nil>'
+stdout 'syntaxerr <nil>'
+stdout 'syntaxerr \[syntaxerr.test\] <nil>'
+stdout 'syntaxerr_test \[syntaxerr.test\] <nil>'
 stdout 'syntaxerr\.test "[^"]*expected declaration'
 ! stderr 'expected declaration'
 
diff --git a/src/cmd/go/testdata/script/mod_list_bad_import.txt b/src/cmd/go/testdata/script/mod_list_bad_import.txt
index 8a66e0b72a..b3e2fff67d 100644
--- a/src/cmd/go/testdata/script/mod_list_bad_import.txt
+++ b/src/cmd/go/testdata/script/mod_list_bad_import.txt
@@ -12,10 +12,11 @@ stdout 'incomplete'
 stdout 'bad dep: .*example.com/notfound'
 
 # Listing with -deps should also fail.
-# BUG: Today, it does not.
-# ! go list -deps example.com/direct
-# stderr example.com/notfound
-go list -deps example.com/direct
+! go list -deps example.com/direct
+stderr example.com/notfound
+
+# But -e -deps should succeed.
+go list -e -deps example.com/direct
 stdout example.com/notfound
 
 
@@ -28,10 +29,11 @@ stdout incomplete
 stdout 'bad dep: .*example.com/notfound'
 
 # Again, -deps should fail.
-# BUG: Again, it does not.
-# ! go list -deps example.com/indirect
-# stderr example.com/notfound
-go list -deps example.com/indirect
+! go list -deps example.com/indirect
+stderr example.com/notfound
+
+# But -e -deps should succeed.
+go list -e -deps example.com/indirect
 stdout example.com/notfound
 
 
diff --git a/src/cmd/go/testdata/script/mod_missingpkg_prerelease.txt b/src/cmd/go/testdata/script/mod_missingpkg_prerelease.txt
index 319ff85587..1ba8d3d22a 100644
--- a/src/cmd/go/testdata/script/mod_missingpkg_prerelease.txt
+++ b/src/cmd/go/testdata/script/mod_missingpkg_prerelease.txt
@@ -1,7 +1,7 @@
 env GO111MODULE=on
 
-! go list use.go
-stderr 'example.com/missingpkg/deprecated: package provided by example.com/missingpkg at latest version v1.0.0 but not at required version v1.0.1-beta'
+! go list -deps use.go
+stderr '^use.go:4:2: package example.com/missingpkg/deprecated provided by example.com/missingpkg at latest version v1.0.0 but not at required version v1.0.1-beta$'
 
 -- go.mod --
 module m