cmd/go/internal/modload: fix spurious import resolution error

Due to a bug in CL 173017, if QueryPackages found multiple candidates
for the given package and *at least* one of those candidates was not
available to add, we would reject *all* such candidates — even those
that were still viable.

Now, we return the first viable candidate, and only return an error if
*no* candidate is viable given the current build list.

Fixes #41113

Change-Id: Idb2e77244be7c0f5dd511efb142c3059925d7336
Reviewed-on: https://go-review.googlesource.com/c/go/+/251446
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>
diff --git a/src/cmd/go/internal/modload/import.go b/src/cmd/go/internal/modload/import.go
index e04d66c..c625184 100644
--- a/src/cmd/go/internal/modload/import.go
+++ b/src/cmd/go/internal/modload/import.go
@@ -312,10 +312,10 @@
 		}
 	}
 
-	m := candidates[0].Mod
-	newMissingVersion := ""
-	for _, c := range candidates {
+	candidate0MissingVersion := ""
+	for i, c := range candidates {
 		cm := c.Mod
+		canAdd := true
 		for _, bm := range buildList {
 			if bm.Path == cm.Path && semver.Compare(bm.Version, cm.Version) > 0 {
 				// QueryPackage proposed that we add module cm to provide the package,
@@ -326,20 +326,22 @@
 				// 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
+				canAdd = false
+				if i == 0 {
+					candidate0MissingVersion = bm.Version
+				}
 				break
 			}
 		}
+		if canAdd {
+			return cm, nil
+		}
 	}
-	if newMissingVersion != "" {
-		return m, &ImportMissingError{Path: path, Module: m, newMissingVersion: newMissingVersion}
+	return module.Version{}, &ImportMissingError{
+		Path:              path,
+		Module:            candidates[0].Mod,
+		newMissingVersion: candidate0MissingVersion,
 	}
-	return m, nil
 }
 
 // maybeInModule reports whether, syntactically,
diff --git a/src/cmd/go/testdata/mod/example.com_split-incompatible_subpkg_v0.1.0.txt b/src/cmd/go/testdata/mod/example.com_split-incompatible_subpkg_v0.1.0.txt
new file mode 100644
index 0000000..8f9e491
--- /dev/null
+++ b/src/cmd/go/testdata/mod/example.com_split-incompatible_subpkg_v0.1.0.txt
@@ -0,0 +1,14 @@
+Written by hand.
+Test case for getting a package that has been moved to a nested module,
+with a +incompatible verison (and thus no go.mod file) at the root module.
+
+-- .mod --
+module example.com/split-incompatible/subpkg
+-- .info --
+{"Version": "v0.1.0"}
+-- go.mod --
+module example.com/split-incompatible/subpkg
+
+go 1.16
+-- subpkg.go --
+package subpkg
diff --git a/src/cmd/go/testdata/mod/example.com_split-incompatible_v2.0.0+incompatible.txt b/src/cmd/go/testdata/mod/example.com_split-incompatible_v2.0.0+incompatible.txt
new file mode 100644
index 0000000..35c3f27
--- /dev/null
+++ b/src/cmd/go/testdata/mod/example.com_split-incompatible_v2.0.0+incompatible.txt
@@ -0,0 +1,10 @@
+Written by hand.
+Test case for getting a package that has been moved to a nested module,
+with a +incompatible verison (and thus no go.mod file) at the root module.
+
+-- .mod --
+module example.com/split-incompatible
+-- .info --
+{"Version": "v2.0.0+incompatible"}
+-- subpkg/subpkg.go --
+package subpkg
diff --git a/src/cmd/go/testdata/mod/example.com_split-incompatible_v2.1.0-pre+incompatible.txt b/src/cmd/go/testdata/mod/example.com_split-incompatible_v2.1.0-pre+incompatible.txt
new file mode 100644
index 0000000..917fc0f
--- /dev/null
+++ b/src/cmd/go/testdata/mod/example.com_split-incompatible_v2.1.0-pre+incompatible.txt
@@ -0,0 +1,10 @@
+Written by hand.
+Test case for getting a package that has been moved to a nested module,
+with a +incompatible verison (and thus no go.mod file) at the root module.
+
+-- .mod --
+module example.com/split-incompatible
+-- .info --
+{"Version": "v2.1.0-pre+incompatible"}
+-- README.txt --
+subpkg has moved to module example.com/split-incompatible/subpkg
diff --git a/src/cmd/go/testdata/script/mod_import_issue41113.txt b/src/cmd/go/testdata/script/mod_import_issue41113.txt
new file mode 100644
index 0000000..e98ac63
--- /dev/null
+++ b/src/cmd/go/testdata/script/mod_import_issue41113.txt
@@ -0,0 +1,28 @@
+# Regression test for https://golang.org/issue/41113.
+#
+# When resolving a missing import path, the inability to add the package from
+# one module path should not interfere with adding a nested path.
+
+# Initially, our module depends on split-incompatible v2.1.0-pre+incompatible,
+# from which an imported package has been removed (and relocated to the nested
+# split-incompatible/subpkg module). modload.QueryPackage will suggest
+# split-incompatible v2.0.0+incompatible, which we cannot use (because it would
+# be an implicit downgrade), and split-incompatible/subpkg v0.1.0, which we
+# *should* use.
+
+go mod tidy
+
+go list -m all
+stdout '^example.com/split-incompatible/subpkg v0\.1\.0$'
+! stdout '^example.com/split-incompatible .*'
+
+-- go.mod --
+module golang.org/issue/41113
+
+go 1.16
+
+require example.com/split-incompatible v2.1.0-pre+incompatible
+-- x.go --
+package issue41113
+
+import _ "example.com/split-incompatible/subpkg"