cmd/go: prune more dependencies in 'go get'

Prior to this change, 'go get' pulled in every version of each module
whose path is explicitly listed in the go.mod file. When graph pruning
is enabled (that is, when the main module is at 'go 1.17' or higher),
that pulled in transitive dependencies of older-than-selected versions
of dependencies, which are normally pruned out by other 'go' commands
(including 'go mod tidy' and 'go mod graph').

To make matters worse, different parts of `go get` were making
different assumptions about which kinds of conflicts would be
reported: the modget package assumed that any conflict is necessarily
due to some explicit constraint, but 'go get' was imposing an
additional constraint that modules could not be incidentally upgraded
in the course of a downgrade. When that additional constraint failed,
the modload package reported the failure as though it were a real
(caller-supplied) constraint, confusing the caller (which couldn't
identify any specific package or argument that caused the failure).

This change fixes both of those problems by replacing the
modload.EditRequirements algorithm with a different one.

The new algorithm is, roughly, as follows.

1. Propose a list of “root requirements” to be written to the updated
   go.mod file.

2. Load the module graph from those requirements mostly as usual, but
   if any root is upgraded due to transitive dependencies, retain the
   original roots and the paths leading from those roots to the
   upgrades. (This forms an “extended graph”, in which we can trace a
   path from to each version that appears in the graph starting at one
   or more of the original roots.)

3. Identify which roots caused any module path to be upgraded above
   its passed-in version constraint. For each such root, either report
   an unresolvable conflict (if the root itself is constrained to a
   specific version) or identify an updated version to propose: either
   a downgrade to the next-highest version, or an upgrade to the
   actually-selected version of the root (if that version is allowed).
   To avoid looping forever or devolving into an NP-complete search,
   we never propose a version that was already rejected previously,
   regardless of what other roots were present alongside it at the
   time.

4. If the version of any root was changed, repeat from (1).

This algorithm is guaranteed to terminate, because there are finitely
many root versions and we permanently reject at least one each time we
downgrade its path to a lower version.

In addition, this change implements support for the '-v' flag to log
more information about version changes at each iteration.

Fixes #56494.
Fixes #55955.

Change-Id: Iebc17dd7586594d5732e228043c3c4c6da230f44
Reviewed-on: https://go-review.googlesource.com/c/go/+/471595
TryBot-Result: Gopher Robot <gobot@golang.org>
Auto-Submit: Bryan Mills <bcmills@google.com>
Run-TryBot: Bryan Mills <bcmills@google.com>
Reviewed-by: Michael Matloob <matloob@golang.org>

1 files changed, 51 insertions, 3 deletions

diff --git a/src/cmd/go/testdata/script/mod_get_downup_indirect.txt b/src/cmd/go/testdata/script/mod_get_downup_indirect.txt
index 3a46a774ce..432e626003 100644
--- a/src/cmd/go/testdata/script/mod_get_downup_indirect.txt
+++ b/src/cmd/go/testdata/script/mod_get_downup_indirect.txt
@@ -19,17 +19,31 @@
 #
 # If we downgrade module d to version 1, we must downgrade b as well.
 # If that downgrade selects b version 1, we will upgrade module c to version 2.
-# So 'go get d@1' should instead downgrade both b and c to "none".
 
 cp go.mod go.mod.orig
 go mod tidy
 cmp go.mod.orig go.mod
 
+# Downgrading d to version 1 downgrades b, which upgrades c.
 go get example.com/d@v0.1.0
 go list -m all
-! stdout '^example.com/b '
-! stdout '^example.com/c '
+stdout '^example.com/b v0.1.0 '
+stdout '^example.com/c v0.2.0 '
 stdout '^example.com/d v0.1.0 '
+cmp go.mod go.mod.down1
+
+# Restoring c to version 1 upgrades d to meet c's requirements.
+go get example.com/c@v0.1.0
+go list -m all
+! stdout '^example.com/b '
+stdout '^example.com/c v0.1.0 '
+stdout '^example.com/d v0.2.0 '
+cmp go.mod go.mod.down2
+
+# If a user explicitly requests the incompatible versions together,
+# 'go get' should explain why they are not compatible.
+! go get example.com/c@v0.1.0 example.com/d@v0.1.0
+stderr '^go: example\.com/c@v0\.1\.0 requires example\.com/d@v0\.2\.0, not example\.com/d@v0\.1\.0'
 
 -- go.mod --
 module example.com/a
@@ -49,6 +63,40 @@ replace (
 	example.com/d v0.1.0 => ./d
 	example.com/d v0.2.0 => ./d
 )
+-- go.mod.down1 --
+module example.com/a
+
+go 1.15
+
+require (
+	example.com/b v0.1.0
+	example.com/c v0.2.0
+	example.com/d v0.1.0 // indirect
+)
+
+replace (
+	example.com/b v0.1.0 => ./b1
+	example.com/b v0.2.0 => ./b2
+	example.com/c v0.1.0 => ./c1
+	example.com/c v0.2.0 => ./c2
+	example.com/d v0.1.0 => ./d
+	example.com/d v0.2.0 => ./d
+)
+-- go.mod.down2 --
+module example.com/a
+
+go 1.15
+
+require example.com/c v0.1.0
+
+replace (
+	example.com/b v0.1.0 => ./b1
+	example.com/b v0.2.0 => ./b2
+	example.com/c v0.1.0 => ./c1
+	example.com/c v0.2.0 => ./c2
+	example.com/d v0.1.0 => ./d
+	example.com/d v0.2.0 => ./d
+)
 -- a.go --
 package a