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.