[release-branch.go1.19] cmd/go: retain extra roots to disambiguate imports in 'go mod tidy'

We don't normally keep explicit requirements for test dependencies of
packages loaded from other modules when the required version is
already the selected version in the module graph. However, in some
cases we may need to keep an explicit requirement in order to make use
of lazy module loading to disambiguate an otherwise-ambiguous import.

Note that there is no Go version guard for this change: in the cases
where the behavior of 'go mod tidy' has changed, previous versions of
Go would produce go.mod files that break successive calls to
'go mod tidy'. Given that, I suspect that any existing user in the
wild affected by this bug either already has a workaround in place
using redundant import statements (in which case the change does not
affect them) or is running 'go mod tidy -e' to force past the error
(in which case a change in behavior to a non-error should not be
surprising).

Updates #60313.
Fixes #60351.

Change-Id: Idf294f72cbe3904b871290d79e4493595a0c7bfc
Reviewed-on: https://go-review.googlesource.com/c/go/+/496635
Auto-Submit: Bryan Mills <bcmills@google.com>
Run-TryBot: Bryan Mills <bcmills@google.com>
Reviewed-by: Russ Cox <rsc@golang.org>
TryBot-Result: Gopher Robot <gobot@golang.org>
(cherry picked from commit 2ed6a54a39339ca37e9da4530b3f37a9d29b7c84)
Reviewed-on: https://go-review.googlesource.com/c/go/+/499636
TryBot-Bypass: Bryan Mills <bcmills@google.com>
Auto-Submit: Dmitri Shuralyov <dmitshur@google.com>
Reviewed-by: Michael Matloob <matloob@golang.org>

2 files changed, 129 insertions, 6 deletions

diff --git a/src/cmd/go/internal/modload/buildlist.go b/src/cmd/go/internal/modload/buildlist.go
index cde4953afa..9b42644660 100644
--- a/src/cmd/go/internal/modload/buildlist.go
+++ b/src/cmd/go/internal/modload/buildlist.go
@@ -10,6 +10,7 @@ import (
 	"cmd/go/internal/mvs"
 	"cmd/go/internal/par"
 	"context"
+	"errors"
 	"fmt"
 	"os"
 	"reflect"
@@ -689,8 +690,8 @@ func updateWorkspaceRoots(ctx context.Context, rs *Requirements, add []module.Ve
 // roots) until the set of roots has converged.
 func tidyPrunedRoots(ctx context.Context, mainModule module.Version, direct map[string]bool, pkgs []*loadPkg) (*Requirements, error) {
 	var (
-		roots        []module.Version
-		pathIncluded = map[string]bool{mainModule.Path: true}
+		roots      []module.Version
+		pathIsRoot = map[string]bool{mainModule.Path: true}
 	)
 	// We start by adding roots for every package in "all".
 	//
@@ -710,9 +711,9 @@ func tidyPrunedRoots(ctx context.Context, mainModule module.Version, direct map[
 		if !pkg.flags.has(pkgInAll) {
 			continue
 		}
-		if pkg.fromExternalModule() && !pathIncluded[pkg.mod.Path] {
+		if pkg.fromExternalModule() && !pathIsRoot[pkg.mod.Path] {
 			roots = append(roots, pkg.mod)
-			pathIncluded[pkg.mod.Path] = true
+			pathIsRoot[pkg.mod.Path] = true
 		}
 		queue = append(queue, pkg)
 		queued[pkg] = true
@@ -744,11 +745,12 @@ func tidyPrunedRoots(ctx context.Context, mainModule module.Version, direct map[
 				queue = append(queue, pkg.test)
 				queued[pkg.test] = true
 			}
-			if !pathIncluded[m.Path] {
+
+			if !pathIsRoot[m.Path] {
 				if s := mg.Selected(m.Path); cmpVersion(s, m.Version) < 0 {
 					roots = append(roots, m)
+					pathIsRoot[m.Path] = true
 				}
-				pathIncluded[m.Path] = true
 			}
 		}
 
@@ -758,10 +760,62 @@ func tidyPrunedRoots(ctx context.Context, mainModule module.Version, direct map[
 		}
 	}
 
+	roots = tidy.rootModules
 	_, err := tidy.Graph(ctx)
 	if err != nil {
 		return nil, err
 	}
+
+	// We try to avoid adding explicit requirements for test-only dependencies of
+	// packages in external modules. However, if we drop the explicit
+	// requirements, that may change an import from unambiguous (due to lazy
+	// module loading) to ambiguous (because lazy module loading no longer
+	// disambiguates it). For any package that has become ambiguous, we try
+	// to fix it by promoting its module to an explicit root.
+	// (See https://go.dev/issue/60313.)
+	q := par.NewQueue(runtime.GOMAXPROCS(0))
+	for {
+		var disambiguateRoot sync.Map
+		for _, pkg := range pkgs {
+			if pkg.mod.Path == "" || pathIsRoot[pkg.mod.Path] {
+				// Lazy module loading will cause pkg.mod to be checked before any other modules
+				// that are only indirectly required. It is as unambiguous as possible.
+				continue
+			}
+			pkg := pkg
+			q.Add(func() {
+				skipModFile := true
+				_, _, _, _, err := importFromModules(ctx, pkg.path, tidy, nil, skipModFile)
+				if aie := (*AmbiguousImportError)(nil); errors.As(err, &aie) {
+					disambiguateRoot.Store(pkg.mod, true)
+				}
+			})
+		}
+		<-q.Idle()
+
+		disambiguateRoot.Range(func(k, _ any) bool {
+			m := k.(module.Version)
+			roots = append(roots, m)
+			pathIsRoot[m.Path] = true
+			return true
+		})
+
+		if len(roots) > len(tidy.rootModules) {
+			module.Sort(roots)
+			tidy = newRequirements(pruned, roots, tidy.direct)
+			_, err = tidy.Graph(ctx)
+			if err != nil {
+				return nil, err
+			}
+			// Adding these roots may have pulled additional modules into the module
+			// graph, causing additional packages to become ambiguous. Keep iterating
+			// until we reach a fixed point.
+			continue
+		}
+
+		break
+	}
+
 	return tidy, nil
 }
 
diff --git a/src/cmd/go/testdata/script/mod_tidy_issue60313.txt b/src/cmd/go/testdata/script/mod_tidy_issue60313.txt
new file mode 100644
index 0000000000..642366926c
--- /dev/null
+++ b/src/cmd/go/testdata/script/mod_tidy_issue60313.txt
@@ -0,0 +1,69 @@
+# Regression test for https://go.dev/issue/60313: 'go mod tidy' did not preserve
+# dependencies needed to prevent 'ambiguous import' errors in external test
+# dependencies.
+
+cp go.mod go.mod.orig
+go mod tidy
+cmp go.mod go.mod.orig
+
+-- go.mod --
+module example
+
+go 1.19
+
+require (
+	example.net/a v0.1.0
+	example.net/b v0.1.0
+)
+
+require example.net/outer/inner v0.1.0 // indirect
+
+replace (
+	example.net/a v0.1.0 => ./a
+	example.net/b v0.1.0 => ./b
+	example.net/outer v0.1.0 => ./outer
+	example.net/outer/inner v0.1.0 => ./inner
+)
+-- example.go --
+package example
+
+import (
+	_ "example.net/a"
+	_ "example.net/b"
+)
+-- a/go.mod --
+module example.net/a
+
+go 1.19
+
+require example.net/outer/inner v0.1.0
+-- a/a.go --
+package a
+-- a/a_test.go --
+package a_test
+
+import _ "example.net/outer/inner"
+-- b/go.mod --
+module example.net/b
+
+go 1.19
+
+require example.net/outer v0.1.0
+-- b/b.go --
+package b
+-- b/b_test.go --
+package b_test
+
+import _ "example.net/outer/inner"
+-- inner/go.mod --
+module example.net/outer/inner
+
+go 1.19
+-- inner/inner.go --
+package inner
+-- outer/go.mod --
+module example.net/outer
+
+go 1.19
+-- outer/inner/inner.go --
+package inner