cmd/go/internal/modget: resolve paths at the requested versions

Previously, we resolved each argument to 'go get' to a package path or
module path based on what was in the build list at existing versions,
even if the argument specified a different version explicitly. That
resulted in bugs like #37438, in which we variously resolved the wrong
version or guessed the wrong argument type for what is unambiguously a
package argument at the requested version.

We were also using a two-step upgrade/downgrade algorithm, which could
not only upgrade more that is strictly necessary, but could also
unintentionally upgrade *above* the requested versions during the
downgrade step.

This change instead uses an iterative approach, with an explicit
disambiguation step for the (rare) cases where an argument could match
the same package path in multiple modules. We use a hook in the
package loader to halt package loading as soon as an incorrect version
is found — preventing over-resolving — and verify that the result
after applying downgrades successfully obtained the requested versions
of all modules.

Making 'go get' be correct and usable is especially important now that
we are defaulting to read-only mode (#40728), for which we are
recommending 'go get' more heavily.

While I'm in here refactoring, I'm also reworking the API boundary
between the modget and modload packages. Previously, the modget
package edited the build list directly, and the modload package
accepted the edited build list without validation. For lazy loading
(#36460), the modload package will need to maintain additional
metadata about the requirement graph, so it needs tighter control over
the changes to the build list.

As of this change, modget no longer invokes MVS directly, but instead
goes through the modload package. The resulting API gives clearer
reasons in case of updates, which we can use to emit more useful
errors.

Fixes #37438
Updates #36460
Updates #40728

Change-Id: I596f0020f3795870dec258147e6fc26a3292c93a
Reviewed-on: https://go-review.googlesource.com/c/go/+/263267
Trust: Bryan C. Mills <bcmills@google.com>
Trust: Jay Conrod <jayconrod@google.com>
Run-TryBot: Bryan C. Mills <bcmills@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Russ Cox <rsc@golang.org>

1 files changed, 152 insertions, 5 deletions

diff --git a/src/cmd/go/internal/modload/buildlist.go b/src/cmd/go/internal/modload/buildlist.go
index 4a183d6881..4aaaa8d206 100644
--- a/src/cmd/go/internal/modload/buildlist.go
+++ b/src/cmd/go/internal/modload/buildlist.go
@@ -12,6 +12,7 @@ import (
 	"context"
 	"fmt"
 	"os"
+	"strings"
 
 	"golang.org/x/mod/module"
 )
@@ -27,6 +28,11 @@ import (
 //
 var buildList []module.Version
 
+// capVersionSlice returns s with its cap reduced to its length.
+func capVersionSlice(s []module.Version) []module.Version {
+	return s[:len(s):len(s)]
+}
+
 // LoadAllModules loads and returns the list of modules matching the "all"
 // module pattern, starting with the Target module and in a deterministic
 // (stable) order, without loading any packages.
@@ -35,21 +41,21 @@ var buildList []module.Version
 // LoadAllModules need only be called if LoadPackages is not,
 // typically in commands that care about modules but no particular package.
 //
-// The caller must not modify the returned list.
+// The caller must not modify the returned list, but may append to it.
 func LoadAllModules(ctx context.Context) []module.Version {
 	LoadModFile(ctx)
 	ReloadBuildList()
 	WriteGoMod()
-	return buildList
+	return capVersionSlice(buildList)
 }
 
 // LoadedModules returns the list of module requirements loaded or set by a
 // previous call (typically LoadAllModules or LoadPackages), starting with the
 // Target module and in a deterministic (stable) order.
 //
-// The caller must not modify the returned list.
+// The caller must not modify the returned list, but may append to it.
 func LoadedModules() []module.Version {
-	return buildList
+	return capVersionSlice(buildList)
 }
 
 // Selected returns the selected version of the module with the given path, or
@@ -74,6 +80,147 @@ func SetBuildList(list []module.Version) {
 	buildList = append([]module.Version{}, list...)
 }
 
+// EditBuildList edits the global build list by first adding every module in add
+// to the existing build list, then adjusting versions (and adding or removing
+// requirements as needed) until every module in mustSelect is selected at the
+// given version.
+//
+// (Note that the newly-added modules might not be selected in the resulting
+// build list: they could be lower than existing requirements or conflict with
+// versions in mustSelect.)
+//
+// After performing the requested edits, EditBuildList returns the updated build
+// list.
+//
+// If the versions listed in mustSelect are mutually incompatible (due to one of
+// the listed modules requiring a higher version of another), EditBuildList
+// returns a *ConstraintError and leaves the build list in its previous state.
+func EditBuildList(ctx context.Context, add, mustSelect []module.Version) error {
+	var upgraded = capVersionSlice(buildList)
+	if len(add) > 0 {
+		// First, upgrade the build list with any additions.
+		// In theory we could just append the additions to the build list and let
+		// mvs.Downgrade take care of resolving the upgrades too, but the
+		// diagnostics from Upgrade are currently much better in case of errors.
+		var err error
+		upgraded, err = mvs.Upgrade(Target, &mvsReqs{buildList: upgraded}, add...)
+		if err != nil {
+			return err
+		}
+	}
+
+	downgraded, err := mvs.Downgrade(Target, &mvsReqs{buildList: append(upgraded, mustSelect...)}, mustSelect...)
+	if err != nil {
+		return err
+	}
+
+	final, err := mvs.Upgrade(Target, &mvsReqs{buildList: downgraded}, mustSelect...)
+	if err != nil {
+		return err
+	}
+
+	selected := make(map[string]module.Version, len(final))
+	for _, m := range final {
+		selected[m.Path] = m
+	}
+	inconsistent := false
+	for _, m := range mustSelect {
+		s, ok := selected[m.Path]
+		if !ok {
+			if m.Version != "none" {
+				panic(fmt.Sprintf("internal error: mvs.BuildList lost %v", m))
+			}
+			continue
+		}
+		if s.Version != m.Version {
+			inconsistent = true
+			break
+		}
+	}
+
+	if !inconsistent {
+		buildList = final
+		return nil
+	}
+
+	// We overshot one or more of the modules in mustSelected, which means that
+	// Downgrade removed something in mustSelect because it conflicted with
+	// something else in mustSelect.
+	//
+	// Walk the requirement graph to find the conflict.
+	//
+	// TODO(bcmills): Ideally, mvs.Downgrade (or a replacement for it) would do
+	// this directly.
+
+	reqs := &mvsReqs{buildList: final}
+	reason := map[module.Version]module.Version{}
+	for _, m := range mustSelect {
+		reason[m] = m
+	}
+	queue := mustSelect[:len(mustSelect):len(mustSelect)]
+	for len(queue) > 0 {
+		var m module.Version
+		m, queue = queue[0], queue[1:]
+		required, err := reqs.Required(m)
+		if err != nil {
+			return err
+		}
+		for _, r := range required {
+			if _, ok := reason[r]; !ok {
+				reason[r] = reason[m]
+				queue = append(queue, r)
+			}
+		}
+	}
+
+	var conflicts []Conflict
+	for _, m := range mustSelect {
+		s, ok := selected[m.Path]
+		if !ok {
+			if m.Version != "none" {
+				panic(fmt.Sprintf("internal error: mvs.BuildList lost %v", m))
+			}
+			continue
+		}
+		if s.Version != m.Version {
+			conflicts = append(conflicts, Conflict{
+				Source:     reason[s],
+				Dep:        s,
+				Constraint: m,
+			})
+		}
+	}
+
+	return &ConstraintError{
+		Conflicts: conflicts,
+	}
+}
+
+// A ConstraintError describes inconsistent constraints in EditBuildList
+type ConstraintError struct {
+	// Conflict lists the source of the conflict for each version in mustSelect
+	// that could not be selected due to the requirements of some other version in
+	// mustSelect.
+	Conflicts []Conflict
+}
+
+func (e *ConstraintError) Error() string {
+	b := new(strings.Builder)
+	b.WriteString("version constraints conflict:")
+	for _, c := range e.Conflicts {
+		fmt.Fprintf(b, "\n\t%v requires %v, but %v is requested", c.Source, c.Dep, c.Constraint)
+	}
+	return b.String()
+}
+
+// A Conflict documents that Source requires Dep, which conflicts with Constraint.
+// (That is, Dep has the same module path as Constraint but a higher version.)
+type Conflict struct {
+	Source     module.Version
+	Dep        module.Version
+	Constraint module.Version
+}
+
 // ReloadBuildList resets the state of loaded packages, then loads and returns
 // the build list set in SetBuildList.
 func ReloadBuildList() []module.Version {
@@ -84,7 +231,7 @@ func ReloadBuildList() []module.Version {
 		listRoots:          func() []string { return nil },
 		allClosesOverTests: index.allPatternClosesOverTests(), // but doesn't matter because the root list is empty.
 	})
-	return buildList
+	return capVersionSlice(buildList)
 }
 
 // TidyBuildList trims the build list to the minimal requirements needed to