Adding upstream version 1.22.1.upstream/1.22.1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

4 files changed, 1454 insertions, 0 deletions

diff --git a/src/cmd/go/internal/mvs/errors.go b/src/cmd/go/internal/mvs/errors.go
new file mode 100644
index 0000000..8db65d6
--- /dev/null
+++ b/src/cmd/go/internal/mvs/errors.go
@@ -0,0 +1,105 @@
+// Copyright 2020 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package mvs
+
+import (
+	"fmt"
+	"strings"
+
+	"golang.org/x/mod/module"
+)
+
+// BuildListError decorates an error that occurred gathering requirements
+// while constructing a build list. BuildListError prints the chain
+// of requirements to the module where the error occurred.
+type BuildListError struct {
+	Err   error
+	stack []buildListErrorElem
+}
+
+type buildListErrorElem struct {
+	m module.Version
+
+	// nextReason is the reason this module depends on the next module in the
+	// stack. Typically either "requires", or "updating to".
+	nextReason string
+}
+
+// NewBuildListError returns a new BuildListError wrapping an error that
+// occurred at a module found along the given path of requirements and/or
+// upgrades, which must be non-empty.
+//
+// The isVersionChange function reports whether a path step is due to an
+// explicit upgrade or downgrade (as opposed to an existing requirement in a
+// go.mod file). A nil isVersionChange function indicates that none of the path
+// steps are due to explicit version changes.
+func NewBuildListError(err error, path []module.Version, isVersionChange func(from, to module.Version) bool) *BuildListError {
+	stack := make([]buildListErrorElem, 0, len(path))
+	for len(path) > 1 {
+		reason := "requires"
+		if isVersionChange != nil && isVersionChange(path[0], path[1]) {
+			reason = "updating to"
+		}
+		stack = append(stack, buildListErrorElem{
+			m:          path[0],
+			nextReason: reason,
+		})
+		path = path[1:]
+	}
+	stack = append(stack, buildListErrorElem{m: path[0]})
+
+	return &BuildListError{
+		Err:   err,
+		stack: stack,
+	}
+}
+
+// Module returns the module where the error occurred. If the module stack
+// is empty, this returns a zero value.
+func (e *BuildListError) Module() module.Version {
+	if len(e.stack) == 0 {
+		return module.Version{}
+	}
+	return e.stack[len(e.stack)-1].m
+}
+
+func (e *BuildListError) Error() string {
+	b := &strings.Builder{}
+	stack := e.stack
+
+	// Don't print modules at the beginning of the chain without a
+	// version. These always seem to be the main module or a
+	// synthetic module ("target@").
+	for len(stack) > 0 && stack[0].m.Version == "" {
+		stack = stack[1:]
+	}
+
+	if len(stack) == 0 {
+		b.WriteString(e.Err.Error())
+	} else {
+		for _, elem := range stack[:len(stack)-1] {
+			fmt.Fprintf(b, "%s %s\n\t", elem.m, elem.nextReason)
+		}
+		// Ensure that the final module path and version are included as part of the
+		// error message.
+		m := stack[len(stack)-1].m
+		if mErr, ok := e.Err.(*module.ModuleError); ok {
+			actual := module.Version{Path: mErr.Path, Version: mErr.Version}
+			if v, ok := mErr.Err.(*module.InvalidVersionError); ok {
+				actual.Version = v.Version
+			}
+			if actual == m {
+				fmt.Fprintf(b, "%v", e.Err)
+			} else {
+				fmt.Fprintf(b, "%s (replaced by %s): %v", m, actual, mErr.Err)
+			}
+		} else {
+			fmt.Fprintf(b, "%v", module.VersionError(m, e.Err))
+		}
+	}
+	return b.String()
+}
+
+func (e *BuildListError) Unwrap() error { return e.Err }
diff --git a/src/cmd/go/internal/mvs/graph.go b/src/cmd/go/internal/mvs/graph.go
new file mode 100644
index 0000000..56b3c60
--- /dev/null
+++ b/src/cmd/go/internal/mvs/graph.go
@@ -0,0 +1,226 @@
+// Copyright 2020 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package mvs
+
+import (
+	"fmt"
+	"slices"
+
+	"cmd/go/internal/gover"
+
+	"golang.org/x/mod/module"
+)
+
+// Graph implements an incremental version of the MVS algorithm, with the
+// requirements pushed by the caller instead of pulled by the MVS traversal.
+type Graph struct {
+	cmp   func(p, v1, v2 string) int
+	roots []module.Version
+
+	required map[module.Version][]module.Version
+
+	isRoot   map[module.Version]bool // contains true for roots and false for reachable non-roots
+	selected map[string]string       // path → version
+}
+
+// NewGraph returns an incremental MVS graph containing only a set of root
+// dependencies and using the given max function for version strings.
+//
+// The caller must ensure that the root slice is not modified while the Graph
+// may be in use.
+func NewGraph(cmp func(p, v1, v2 string) int, roots []module.Version) *Graph {
+	g := &Graph{
+		cmp:      cmp,
+		roots:    slices.Clip(roots),
+		required: make(map[module.Version][]module.Version),
+		isRoot:   make(map[module.Version]bool),
+		selected: make(map[string]string),
+	}
+
+	for _, m := range roots {
+		g.isRoot[m] = true
+		if g.cmp(m.Path, g.Selected(m.Path), m.Version) < 0 {
+			g.selected[m.Path] = m.Version
+		}
+	}
+
+	return g
+}
+
+// Require adds the information that module m requires all modules in reqs.
+// The reqs slice must not be modified after it is passed to Require.
+//
+// m must be reachable by some existing chain of requirements from g's target,
+// and Require must not have been called for it already.
+//
+// If any of the modules in reqs has the same path as g's target,
+// the target must have higher precedence than the version in req.
+func (g *Graph) Require(m module.Version, reqs []module.Version) {
+	// To help catch disconnected-graph bugs, enforce that all required versions
+	// are actually reachable from the roots (and therefore should affect the
+	// selected versions of the modules they name).
+	if _, reachable := g.isRoot[m]; !reachable {
+		panic(fmt.Sprintf("%v is not reachable from any root", m))
+	}
+
+	// Truncate reqs to its capacity to avoid aliasing bugs if it is later
+	// returned from RequiredBy and appended to.
+	reqs = slices.Clip(reqs)
+
+	if _, dup := g.required[m]; dup {
+		panic(fmt.Sprintf("requirements of %v have already been set", m))
+	}
+	g.required[m] = reqs
+
+	for _, dep := range reqs {
+		// Mark dep reachable, regardless of whether it is selected.
+		if _, ok := g.isRoot[dep]; !ok {
+			g.isRoot[dep] = false
+		}
+
+		if g.cmp(dep.Path, g.Selected(dep.Path), dep.Version) < 0 {
+			g.selected[dep.Path] = dep.Version
+		}
+	}
+}
+
+// RequiredBy returns the slice of requirements passed to Require for m, if any,
+// with its capacity reduced to its length.
+// If Require has not been called for m, RequiredBy(m) returns ok=false.
+//
+// The caller must not modify the returned slice, but may safely append to it
+// and may rely on it not to be modified.
+func (g *Graph) RequiredBy(m module.Version) (reqs []module.Version, ok bool) {
+	reqs, ok = g.required[m]
+	return reqs, ok
+}
+
+// Selected returns the selected version of the given module path.
+//
+// If no version is selected, Selected returns version "none".
+func (g *Graph) Selected(path string) (version string) {
+	v, ok := g.selected[path]
+	if !ok {
+		return "none"
+	}
+	return v
+}
+
+// BuildList returns the selected versions of all modules present in the Graph,
+// beginning with the selected versions of each module path in the roots of g.
+//
+// The order of the remaining elements in the list is deterministic
+// but arbitrary.
+func (g *Graph) BuildList() []module.Version {
+	seenRoot := make(map[string]bool, len(g.roots))
+
+	var list []module.Version
+	for _, r := range g.roots {
+		if seenRoot[r.Path] {
+			// Multiple copies of the same root, with the same or different versions,
+			// are a bit of a degenerate case: we will take the transitive
+			// requirements of both roots into account, but only the higher one can
+			// possibly be selected. However — especially given that we need the
+			// seenRoot map for later anyway — it is simpler to support this
+			// degenerate case than to forbid it.
+			continue
+		}
+
+		if v := g.Selected(r.Path); v != "none" {
+			list = append(list, module.Version{Path: r.Path, Version: v})
+		}
+		seenRoot[r.Path] = true
+	}
+	uniqueRoots := list
+
+	for path, version := range g.selected {
+		if !seenRoot[path] {
+			list = append(list, module.Version{Path: path, Version: version})
+		}
+	}
+	gover.ModSort(list[len(uniqueRoots):])
+
+	return list
+}
+
+// WalkBreadthFirst invokes f once, in breadth-first order, for each module
+// version other than "none" that appears in the graph, regardless of whether
+// that version is selected.
+func (g *Graph) WalkBreadthFirst(f func(m module.Version)) {
+	var queue []module.Version
+	enqueued := make(map[module.Version]bool)
+	for _, m := range g.roots {
+		if m.Version != "none" {
+			queue = append(queue, m)
+			enqueued[m] = true
+		}
+	}
+
+	for len(queue) > 0 {
+		m := queue[0]
+		queue = queue[1:]
+
+		f(m)
+
+		reqs, _ := g.RequiredBy(m)
+		for _, r := range reqs {
+			if !enqueued[r] && r.Version != "none" {
+				queue = append(queue, r)
+				enqueued[r] = true
+			}
+		}
+	}
+}
+
+// FindPath reports a shortest requirement path starting at one of the roots of
+// the graph and ending at a module version m for which f(m) returns true, or
+// nil if no such path exists.
+func (g *Graph) FindPath(f func(module.Version) bool) []module.Version {
+	// firstRequires[a] = b means that in a breadth-first traversal of the
+	// requirement graph, the module version a was first required by b.
+	firstRequires := make(map[module.Version]module.Version)
+
+	queue := g.roots
+	for _, m := range g.roots {
+		firstRequires[m] = module.Version{}
+	}
+
+	for len(queue) > 0 {
+		m := queue[0]
+		queue = queue[1:]
+
+		if f(m) {
+			// Construct the path reversed (because we're starting from the far
+			// endpoint), then reverse it.
+			path := []module.Version{m}
+			for {
+				m = firstRequires[m]
+				if m.Path == "" {
+					break
+				}
+				path = append(path, m)
+			}
+
+			i, j := 0, len(path)-1
+			for i < j {
+				path[i], path[j] = path[j], path[i]
+				i++
+				j--
+			}
+
+			return path
+		}
+
+		reqs, _ := g.RequiredBy(m)
+		for _, r := range reqs {
+			if _, seen := firstRequires[r]; !seen {
+				queue = append(queue, r)
+				firstRequires[r] = m
+			}
+		}
+	}
+
+	return nil
+}
diff --git a/src/cmd/go/internal/mvs/mvs.go b/src/cmd/go/internal/mvs/mvs.go
new file mode 100644
index 0000000..468a985
--- /dev/null
+++ b/src/cmd/go/internal/mvs/mvs.go
@@ -0,0 +1,488 @@
+// Copyright 2018 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package mvs implements Minimal Version Selection.
+// See https://research.swtch.com/vgo-mvs.
+package mvs
+
+import (
+	"fmt"
+	"reflect"
+	"sort"
+	"sync"
+
+	"cmd/go/internal/par"
+
+	"golang.org/x/mod/module"
+)
+
+// A Reqs is the requirement graph on which Minimal Version Selection (MVS) operates.
+//
+// The version strings are opaque except for the special version "none"
+// (see the documentation for module.Version). In particular, MVS does not
+// assume that the version strings are semantic versions; instead, the Max method
+// gives access to the comparison operation.
+//
+// It must be safe to call methods on a Reqs from multiple goroutines simultaneously.
+// Because a Reqs may read the underlying graph from the network on demand,
+// the MVS algorithms parallelize the traversal to overlap network delays.
+type Reqs interface {
+	// Required returns the module versions explicitly required by m itself.
+	// The caller must not modify the returned list.
+	Required(m module.Version) ([]module.Version, error)
+
+	// Max returns the maximum of v1 and v2 (it returns either v1 or v2)
+	// in the module with path p.
+	//
+	// For all versions v, Max(v, "none") must be v,
+	// and for the target passed as the first argument to MVS functions,
+	// Max(target, v) must be target.
+	//
+	// Note that v1 < v2 can be written Max(v1, v2) != v1
+	// and similarly v1 <= v2 can be written Max(v1, v2) == v2.
+	Max(p, v1, v2 string) string
+}
+
+// An UpgradeReqs is a Reqs that can also identify available upgrades.
+type UpgradeReqs interface {
+	Reqs
+
+	// Upgrade returns the upgraded version of m,
+	// for use during an UpgradeAll operation.
+	// If m should be kept as is, Upgrade returns m.
+	// If m is not yet used in the build, then m.Version will be "none".
+	// More typically, m.Version will be the version required
+	// by some other module in the build.
+	//
+	// If no module version is available for the given path,
+	// Upgrade returns a non-nil error.
+	// TODO(rsc): Upgrade must be able to return errors,
+	// but should "no latest version" just return m instead?
+	Upgrade(m module.Version) (module.Version, error)
+}
+
+// A DowngradeReqs is a Reqs that can also identify available downgrades.
+type DowngradeReqs interface {
+	Reqs
+
+	// Previous returns the version of m.Path immediately prior to m.Version,
+	// or "none" if no such version is known.
+	Previous(m module.Version) (module.Version, error)
+}
+
+// BuildList returns the build list for the target module.
+//
+// target is the root vertex of a module requirement graph. For cmd/go, this is
+// typically the main module, but note that this algorithm is not intended to
+// be Go-specific: module paths and versions are treated as opaque values.
+//
+// reqs describes the module requirement graph and provides an opaque method
+// for comparing versions.
+//
+// BuildList traverses the graph and returns a list containing the highest
+// version for each visited module. The first element of the returned list is
+// target itself; reqs.Max requires target.Version to compare higher than all
+// other versions, so no other version can be selected. The remaining elements
+// of the list are sorted by path.
+//
+// See https://research.swtch.com/vgo-mvs for details.
+func BuildList(targets []module.Version, reqs Reqs) ([]module.Version, error) {
+	return buildList(targets, reqs, nil)
+}
+
+func buildList(targets []module.Version, reqs Reqs, upgrade func(module.Version) (module.Version, error)) ([]module.Version, error) {
+	cmp := func(p, v1, v2 string) int {
+		if reqs.Max(p, v1, v2) != v1 {
+			return -1
+		}
+		if reqs.Max(p, v2, v1) != v2 {
+			return 1
+		}
+		return 0
+	}
+
+	var (
+		mu       sync.Mutex
+		g        = NewGraph(cmp, targets)
+		upgrades = map[module.Version]module.Version{}
+		errs     = map[module.Version]error{} // (non-nil errors only)
+	)
+
+	// Explore work graph in parallel in case reqs.Required
+	// does high-latency network operations.
+	var work par.Work[module.Version]
+	for _, target := range targets {
+		work.Add(target)
+	}
+	work.Do(10, func(m module.Version) {
+
+		var required []module.Version
+		var err error
+		if m.Version != "none" {
+			required, err = reqs.Required(m)
+		}
+
+		u := m
+		if upgrade != nil {
+			upgradeTo, upErr := upgrade(m)
+			if upErr == nil {
+				u = upgradeTo
+			} else if err == nil {
+				err = upErr
+			}
+		}
+
+		mu.Lock()
+		if err != nil {
+			errs[m] = err
+		}
+		if u != m {
+			upgrades[m] = u
+			required = append([]module.Version{u}, required...)
+		}
+		g.Require(m, required)
+		mu.Unlock()
+
+		for _, r := range required {
+			work.Add(r)
+		}
+	})
+
+	// If there was an error, find the shortest path from the target to the
+	// node where the error occurred so we can report a useful error message.
+	if len(errs) > 0 {
+		errPath := g.FindPath(func(m module.Version) bool {
+			return errs[m] != nil
+		})
+		if len(errPath) == 0 {
+			panic("internal error: could not reconstruct path to module with error")
+		}
+
+		err := errs[errPath[len(errPath)-1]]
+		isUpgrade := func(from, to module.Version) bool {
+			if u, ok := upgrades[from]; ok {
+				return u == to
+			}
+			return false
+		}
+		return nil, NewBuildListError(err, errPath, isUpgrade)
+	}
+
+	// The final list is the minimum version of each module found in the graph.
+	list := g.BuildList()
+	if vs := list[:len(targets)]; !reflect.DeepEqual(vs, targets) {
+		// target.Version will be "" for modload, the main client of MVS.
+		// "" denotes the main module, which has no version. However, MVS treats
+		// version strings as opaque, so "" is not a special value here.
+		// See golang.org/issue/31491, golang.org/issue/29773.
+		panic(fmt.Sprintf("mistake: chose versions %+v instead of targets %+v", vs, targets))
+	}
+	return list, nil
+}
+
+// Req returns the minimal requirement list for the target module,
+// with the constraint that all module paths listed in base must
+// appear in the returned list.
+func Req(mainModule module.Version, base []string, reqs Reqs) ([]module.Version, error) {
+	list, err := BuildList([]module.Version{mainModule}, reqs)
+	if err != nil {
+		return nil, err
+	}
+
+	// Note: Not running in parallel because we assume
+	// that list came from a previous operation that paged
+	// in all the requirements, so there's no I/O to overlap now.
+
+	max := map[string]string{}
+	for _, m := range list {
+		max[m.Path] = m.Version
+	}
+
+	// Compute postorder, cache requirements.
+	var postorder []module.Version
+	reqCache := map[module.Version][]module.Version{}
+	reqCache[mainModule] = nil
+
+	var walk func(module.Version) error
+	walk = func(m module.Version) error {
+		_, ok := reqCache[m]
+		if ok {
+			return nil
+		}
+		required, err := reqs.Required(m)
+		if err != nil {
+			return err
+		}
+		reqCache[m] = required
+		for _, m1 := range required {
+			if err := walk(m1); err != nil {
+				return err
+			}
+		}
+		postorder = append(postorder, m)
+		return nil
+	}
+	for _, m := range list {
+		if err := walk(m); err != nil {
+			return nil, err
+		}
+	}
+
+	// Walk modules in reverse post-order, only adding those not implied already.
+	have := map[module.Version]bool{}
+	walk = func(m module.Version) error {
+		if have[m] {
+			return nil
+		}
+		have[m] = true
+		for _, m1 := range reqCache[m] {
+			walk(m1)
+		}
+		return nil
+	}
+	// First walk the base modules that must be listed.
+	var min []module.Version
+	haveBase := map[string]bool{}
+	for _, path := range base {
+		if haveBase[path] {
+			continue
+		}
+		m := module.Version{Path: path, Version: max[path]}
+		min = append(min, m)
+		walk(m)
+		haveBase[path] = true
+	}
+	// Now the reverse postorder to bring in anything else.
+	for i := len(postorder) - 1; i >= 0; i-- {
+		m := postorder[i]
+		if max[m.Path] != m.Version {
+			// Older version.
+			continue
+		}
+		if !have[m] {
+			min = append(min, m)
+			walk(m)
+		}
+	}
+	sort.Slice(min, func(i, j int) bool {
+		return min[i].Path < min[j].Path
+	})
+	return min, nil
+}
+
+// UpgradeAll returns a build list for the target module
+// in which every module is upgraded to its latest version.
+func UpgradeAll(target module.Version, reqs UpgradeReqs) ([]module.Version, error) {
+	return buildList([]module.Version{target}, reqs, func(m module.Version) (module.Version, error) {
+		if m.Path == target.Path {
+			return target, nil
+		}
+
+		return reqs.Upgrade(m)
+	})
+}
+
+// Upgrade returns a build list for the target module
+// in which the given additional modules are upgraded.
+func Upgrade(target module.Version, reqs UpgradeReqs, upgrade ...module.Version) ([]module.Version, error) {
+	list, err := reqs.Required(target)
+	if err != nil {
+		return nil, err
+	}
+
+	pathInList := make(map[string]bool, len(list))
+	for _, m := range list {
+		pathInList[m.Path] = true
+	}
+	list = append([]module.Version(nil), list...)
+
+	upgradeTo := make(map[string]string, len(upgrade))
+	for _, u := range upgrade {
+		if !pathInList[u.Path] {
+			list = append(list, module.Version{Path: u.Path, Version: "none"})
+		}
+		if prev, dup := upgradeTo[u.Path]; dup {
+			upgradeTo[u.Path] = reqs.Max(u.Path, prev, u.Version)
+		} else {
+			upgradeTo[u.Path] = u.Version
+		}
+	}
+
+	return buildList([]module.Version{target}, &override{target, list, reqs}, func(m module.Version) (module.Version, error) {
+		if v, ok := upgradeTo[m.Path]; ok {
+			return module.Version{Path: m.Path, Version: v}, nil
+		}
+		return m, nil
+	})
+}
+
+// Downgrade returns a build list for the target module
+// in which the given additional modules are downgraded,
+// potentially overriding the requirements of the target.
+//
+// The versions to be downgraded may be unreachable from reqs.Latest and
+// reqs.Previous, but the methods of reqs must otherwise handle such versions
+// correctly.
+func Downgrade(target module.Version, reqs DowngradeReqs, downgrade ...module.Version) ([]module.Version, error) {
+	// Per https://research.swtch.com/vgo-mvs#algorithm_4:
+	// “To avoid an unnecessary downgrade to E 1.1, we must also add a new
+	// requirement on E 1.2. We can apply Algorithm R to find the minimal set of
+	// new requirements to write to go.mod.”
+	//
+	// In order to generate those new requirements, we need to identify versions
+	// for every module in the build list — not just reqs.Required(target).
+	list, err := BuildList([]module.Version{target}, reqs)
+	if err != nil {
+		return nil, err
+	}
+	list = list[1:] // remove target
+
+	max := make(map[string]string)
+	for _, r := range list {
+		max[r.Path] = r.Version
+	}
+	for _, d := range downgrade {
+		if v, ok := max[d.Path]; !ok || reqs.Max(d.Path, v, d.Version) != d.Version {
+			max[d.Path] = d.Version
+		}
+	}
+
+	var (
+		added    = make(map[module.Version]bool)
+		rdeps    = make(map[module.Version][]module.Version)
+		excluded = make(map[module.Version]bool)
+	)
+	var exclude func(module.Version)
+	exclude = func(m module.Version) {
+		if excluded[m] {
+			return
+		}
+		excluded[m] = true
+		for _, p := range rdeps[m] {
+			exclude(p)
+		}
+	}
+	var add func(module.Version)
+	add = func(m module.Version) {
+		if added[m] {
+			return
+		}
+		added[m] = true
+		if v, ok := max[m.Path]; ok && reqs.Max(m.Path, m.Version, v) != v {
+			// m would upgrade an existing dependency — it is not a strict downgrade,
+			// and because it was already present as a dependency, it could affect the
+			// behavior of other relevant packages.
+			exclude(m)
+			return
+		}
+		list, err := reqs.Required(m)
+		if err != nil {
+			// If we can't load the requirements, we couldn't load the go.mod file.
+			// There are a number of reasons this can happen, but this usually
+			// means an older version of the module had a missing or invalid
+			// go.mod file. For example, if example.com/mod released v2.0.0 before
+			// migrating to modules (v2.0.0+incompatible), then added a valid go.mod
+			// in v2.0.1, downgrading from v2.0.1 would cause this error.
+			//
+			// TODO(golang.org/issue/31730, golang.org/issue/30134): if the error
+			// is transient (we couldn't download go.mod), return the error from
+			// Downgrade. Currently, we can't tell what kind of error it is.
+			exclude(m)
+			return
+		}
+		for _, r := range list {
+			add(r)
+			if excluded[r] {
+				exclude(m)
+				return
+			}
+			rdeps[r] = append(rdeps[r], m)
+		}
+	}
+
+	downgraded := make([]module.Version, 0, len(list)+1)
+	downgraded = append(downgraded, target)
+List:
+	for _, r := range list {
+		add(r)
+		for excluded[r] {
+			p, err := reqs.Previous(r)
+			if err != nil {
+				// This is likely a transient error reaching the repository,
+				// rather than a permanent error with the retrieved version.
+				//
+				// TODO(golang.org/issue/31730, golang.org/issue/30134):
+				// decode what to do based on the actual error.
+				return nil, err
+			}
+			// If the target version is a pseudo-version, it may not be
+			// included when iterating over prior versions using reqs.Previous.
+			// Insert it into the right place in the iteration.
+			// If v is excluded, p should be returned again by reqs.Previous on the next iteration.
+			if v := max[r.Path]; reqs.Max(r.Path, v, r.Version) != v && reqs.Max(r.Path, p.Version, v) != p.Version {
+				p.Version = v
+			}
+			if p.Version == "none" {
+				continue List
+			}
+			add(p)
+			r = p
+		}
+		downgraded = append(downgraded, r)
+	}
+
+	// The downgrades we computed above only downgrade to versions enumerated by
+	// reqs.Previous. However, reqs.Previous omits some versions — such as
+	// pseudo-versions and retracted versions — that may be selected as transitive
+	// requirements of other modules.
+	//
+	// If one of those requirements pulls the version back up above the version
+	// identified by reqs.Previous, then the transitive dependencies of that that
+	// initially-downgraded version should no longer matter — in particular, we
+	// should not add new dependencies on module paths that nothing else in the
+	// updated module graph even requires.
+	//
+	// In order to eliminate those spurious dependencies, we recompute the build
+	// list with the actual versions of the downgraded modules as selected by MVS,
+	// instead of our initial downgrades.
+	// (See the downhiddenartifact and downhiddencross test cases).
+	actual, err := BuildList([]module.Version{target}, &override{
+		target: target,
+		list:   downgraded,
+		Reqs:   reqs,
+	})
+	if err != nil {
+		return nil, err
+	}
+	actualVersion := make(map[string]string, len(actual))
+	for _, m := range actual {
+		actualVersion[m.Path] = m.Version
+	}
+
+	downgraded = downgraded[:0]
+	for _, m := range list {
+		if v, ok := actualVersion[m.Path]; ok {
+			downgraded = append(downgraded, module.Version{Path: m.Path, Version: v})
+		}
+	}
+
+	return BuildList([]module.Version{target}, &override{
+		target: target,
+		list:   downgraded,
+		Reqs:   reqs,
+	})
+}
+
+type override struct {
+	target module.Version
+	list   []module.Version
+	Reqs
+}
+
+func (r *override) Required(m module.Version) ([]module.Version, error) {
+	if m == r.target {
+		return r.list, nil
+	}
+	return r.Reqs.Required(m)
+}
diff --git a/src/cmd/go/internal/mvs/mvs_test.go b/src/cmd/go/internal/mvs/mvs_test.go
new file mode 100644
index 0000000..6e1e71c
--- /dev/null
+++ b/src/cmd/go/internal/mvs/mvs_test.go
@@ -0,0 +1,635 @@
+// Copyright 2018 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package mvs
+
+import (
+	"fmt"
+	"reflect"
+	"strings"
+	"testing"
+
+	"golang.org/x/mod/module"
+)
+
+var tests = `
+# Scenario from blog.
+name: blog
+A: B1 C2
+B1: D3
+C1: D2
+C2: D4
+C3: D5
+C4: G1
+D2: E1
+D3: E2
+D4: E2 F1
+D5: E2
+G1: C4
+A2: B1 C4 D4
+build A:       A B1 C2 D4 E2 F1
+upgrade* A:    A B1 C4 D5 E2 F1 G1
+upgrade A C4:  A B1 C4 D4 E2 F1 G1
+build A2:     A2 B1 C4 D4 E2 F1 G1
+downgrade A2 D2: A2 C4 D2 E2 F1 G1
+
+name: trim
+A: B1 C2
+B1: D3
+C2: B2
+B2:
+build A: A B2 C2 D3
+
+# Cross-dependency between D and E.
+# No matter how it arises, should get result of merging all build lists via max,
+# which leads to including both D2 and E2.
+
+name: cross1
+A: B C
+B: D1
+C: D2
+D1: E2
+D2: E1
+build A: A B C D2 E2
+
+name: cross1V
+A: B2 C D2 E1
+B1:
+B2: D1
+C: D2
+D1: E2
+D2: E1
+build A: A B2 C D2 E2
+
+name: cross1U
+A: B1 C
+B1:
+B2: D1
+C: D2
+D1: E2
+D2: E1
+build A:      A B1 C D2 E1
+upgrade A B2: A B2 C D2 E2
+
+name: cross1R
+A: B C
+B: D2
+C: D1
+D1: E2
+D2: E1
+build A: A B C D2 E2
+
+name: cross1X
+A: B C
+B: D1 E2
+C: D2
+D1: E2
+D2: E1
+build A: A B C D2 E2
+
+name: cross2
+A: B D2
+B: D1
+D1: E2
+D2: E1
+build A: A B D2 E2
+
+name: cross2X
+A: B D2
+B: D1 E2
+C: D2
+D1: E2
+D2: E1
+build A: A B D2 E2
+
+name: cross3
+A: B D2 E1
+B: D1
+D1: E2
+D2: E1
+build A: A B D2 E2
+
+name: cross3X
+A: B D2 E1
+B: D1 E2
+D1: E2
+D2: E1
+build A: A B D2 E2
+
+# Should not get E2 here, because B has been updated
+# not to depend on D1 anymore.
+name: cross4
+A1: B1 D2
+A2: B2 D2
+B1: D1
+B2: D2
+D1: E2
+D2: E1
+build A1: A1 B1 D2 E2
+build A2: A2 B2 D2 E1
+
+# But the upgrade from A1 preserves the E2 dep explicitly.
+upgrade A1 B2: A1 B2 D2 E2
+upgradereq A1 B2: B2 E2
+
+name: cross5
+A: D1
+D1: E2
+D2: E1
+build A:       A D1 E2
+upgrade* A:    A D2 E2
+upgrade A D2:  A D2 E2
+upgradereq A D2: D2 E2
+
+name: cross6
+A: D2
+D1: E2
+D2: E1
+build A:      A D2 E1
+upgrade* A:   A D2 E2
+upgrade A E2: A D2 E2
+
+name: cross7
+A: B C
+B: D1
+C: E1
+D1: E2
+E1: D2
+build A: A B C D2 E2
+
+# golang.org/issue/31248:
+# Even though we select X2, the requirement on I1
+# via X1 should be preserved.
+name: cross8
+M: A1 B1
+A1: X1
+B1: X2
+X1: I1
+X2:
+build M: M A1 B1 I1 X2
+
+# Upgrade from B1 to B2 should not drop the transitive dep on D.
+name: drop
+A: B1 C1
+B1: D1
+B2:
+C2:
+D2:
+build A:    A B1 C1 D1
+upgrade* A: A B2 C2 D2
+
+name: simplify
+A: B1 C1
+B1: C2
+C1: D1
+C2:
+build A: A B1 C2 D1
+
+name: up1
+A: B1 C1
+B1:
+B2:
+B3:
+B4:
+B5.hidden:
+C2:
+C3:
+build A:    A B1 C1
+upgrade* A: A B4 C3
+
+name: up2
+A: B5.hidden C1
+B1:
+B2:
+B3:
+B4:
+B5.hidden:
+C2:
+C3:
+build A:    A B5.hidden C1
+upgrade* A: A B5.hidden C3
+
+name: down1
+A: B2
+B1: C1
+B2: C2
+build A:        A B2 C2
+downgrade A C1: A B1 C1
+
+name: down2
+A: B2 E2
+B1:
+B2: C2 F2
+C1:
+D1:
+C2: D2 E2
+D2: B2
+E2: D2
+E1:
+F1:
+build A:        A B2 C2 D2 E2 F2
+downgrade A F1: A B1 C1 D1 E1 F1
+
+# https://research.swtch.com/vgo-mvs#algorithm_4:
+# “[D]owngrades are constrained to only downgrade packages, not also upgrade
+# them; if an upgrade before downgrade is needed, the user must ask for it
+# explicitly.”
+#
+# Here, downgrading B2 to B1 upgrades C1 to C2, and C2 does not depend on D2.
+# However, C2 would be an upgrade — not a downgrade — so B1 must also be
+# rejected.
+name: downcross1
+A: B2 C1
+B1: C2
+B2: C1
+C1: D2
+C2:
+D1:
+D2:
+build A:        A B2 C1 D2
+downgrade A D1: A       D1
+
+# https://research.swtch.com/vgo-mvs#algorithm_4:
+# “Unlike upgrades, downgrades must work by removing requirements, not adding
+# them.”
+#
+# However, downgrading a requirement may introduce a new requirement on a
+# previously-unrequired module. If each dependency's requirements are complete
+# (“tidy”), that can't change the behavior of any other package whose version is
+# not also being downgraded, so we should allow it.
+name: downcross2
+A: B2
+B1: C1
+B2: D2
+C1:
+D1:
+D2:
+build A:        A B2    D2
+downgrade A D1: A B1 C1 D1
+
+name: downcycle
+A: A B2
+B2: A
+B1:
+build A:        A B2
+downgrade A B1: A B1
+
+# Both B3 and C2 require D2.
+# If we downgrade D to D1, then in isolation B3 would downgrade to B1,
+# because B2 is hidden — B1 is the next-highest version that is not hidden.
+# However, if we downgrade D, we will also downgrade C to C1.
+# And C1 requires B2.hidden, and B2.hidden also meets our requirements:
+# it is compatible with D1 and a strict downgrade from B3.
+#
+# Since neither the initial nor the final build list includes B1,
+# and the nothing in the final downgraded build list requires E at all,
+# no dependency on E1 (required by only B1) should be introduced.
+#
+name: downhiddenartifact
+A: B3 C2
+A1: B3
+B1: E1
+B2.hidden:
+B3: D2
+C1: B2.hidden
+C2: D2
+D1:
+D2:
+build A1: A1 B3 D2
+downgrade A1 D1: A1 B1 D1 E1
+build A: A B3 C2 D2
+downgrade A D1: A B2.hidden C1 D1
+
+# Both B3 and C3 require D2.
+# If we downgrade D to D1, then in isolation B3 would downgrade to B1,
+# and C3 would downgrade to C1.
+# But C1 requires B2.hidden, and B1 requires C2.hidden, so we can't
+# downgrade to either of those without pulling the other back up a little.
+#
+# B2.hidden and C2.hidden are both compatible with D1, so that still
+# meets our requirements — but then we're in an odd state in which
+# B and C have both been downgraded to hidden versions, without any
+# remaining requirements to explain how those hidden versions got there.
+#
+# TODO(bcmills): Would it be better to force downgrades to land on non-hidden
+# versions?
+# In this case, that would remove the dependencies on B and C entirely.
+#
+name: downhiddencross
+A: B3 C3
+B1: C2.hidden
+B2.hidden:
+B3: D2
+C1: B2.hidden
+C2.hidden:
+C3: D2
+D1:
+D2:
+build A: A B3 C3 D2
+downgrade A D1: A B2.hidden C2.hidden D1
+
+# golang.org/issue/25542.
+name: noprev1
+A: B4 C2
+B2.hidden:
+C2:
+build A:               A B4        C2
+downgrade A B2.hidden: A B2.hidden C2
+
+name: noprev2
+A: B4 C2
+B2.hidden:
+B1:
+C2:
+build A:               A B4        C2
+downgrade A B2.hidden: A B2.hidden C2
+
+name: noprev3
+A: B4 C2
+B3:
+B2.hidden:
+C2:
+build A:               A B4        C2
+downgrade A B2.hidden: A B2.hidden C2
+
+# Cycles involving the target.
+
+# The target must be the newest version of itself.
+name: cycle1
+A: B1
+B1: A1
+B2: A2
+B3: A3
+build A:      A B1
+upgrade A B2: A B2
+upgrade* A:   A B3
+
+# golang.org/issue/29773:
+# Requirements of older versions of the target
+# must be carried over.
+name: cycle2
+A: B1
+A1: C1
+A2: D1
+B1: A1
+B2: A2
+C1: A2
+C2:
+D2:
+build A:    A B1 C1 D1
+upgrade* A: A B2 C2 D2
+
+# Cycles with multiple possible solutions.
+# (golang.org/issue/34086)
+name: cycle3
+M: A1 C2
+A1: B1
+B1: C1
+B2: C2
+C1:
+C2: B2
+build M: M A1 B2 C2
+req M:     A1 B2
+req M A:   A1 B2
+req M C:   A1 C2
+
+# Requirement minimization.
+
+name: req1
+A: B1 C1 D1 E1 F1
+B1: C1 E1 F1
+req A:   B1    D1
+req A C: B1 C1 D1
+
+name: req2
+A: G1 H1
+G1: H1
+H1: G1
+req A:   G1
+req A G: G1
+req A H: H1
+
+name: req3
+M: A1 B1
+A1: X1
+B1: X2
+X1: I1
+X2:
+req M: A1 B1
+
+name: reqnone
+M: Anone B1 D1 E1
+B1: Cnone D1
+E1: Fnone
+build M: M B1 D1 E1
+req M:     B1    E1
+
+name: reqdup
+M: A1 B1
+A1: B1
+B1:
+req M A A: A1
+
+name: reqcross
+M: A1 B1 C1
+A1: B1 C1
+B1: C1
+C1:
+req M A B: A1 B1
+`
+
+func Test(t *testing.T) {
+	var (
+		name string
+		reqs reqsMap
+		fns  []func(*testing.T)
+	)
+	flush := func() {
+		if name != "" {
+			t.Run(name, func(t *testing.T) {
+				for _, fn := range fns {
+					fn(t)
+				}
+				if len(fns) == 0 {
+					t.Errorf("no functions tested")
+				}
+			})
+		}
+	}
+	m := func(s string) module.Version {
+		return module.Version{Path: s[:1], Version: s[1:]}
+	}
+	ms := func(list []string) []module.Version {
+		var mlist []module.Version
+		for _, s := range list {
+			mlist = append(mlist, m(s))
+		}
+		return mlist
+	}
+	checkList := func(t *testing.T, desc string, list []module.Version, err error, val string) {
+		if err != nil {
+			t.Fatalf("%s: %v", desc, err)
+		}
+		vs := ms(strings.Fields(val))
+		if !reflect.DeepEqual(list, vs) {
+			t.Errorf("%s = %v, want %v", desc, list, vs)
+		}
+	}
+
+	for _, line := range strings.Split(tests, "\n") {
+		line = strings.TrimSpace(line)
+		if strings.HasPrefix(line, "#") || line == "" {
+			continue
+		}
+		i := strings.Index(line, ":")
+		if i < 0 {
+			t.Fatalf("missing colon: %q", line)
+		}
+		key := strings.TrimSpace(line[:i])
+		val := strings.TrimSpace(line[i+1:])
+		if key == "" {
+			t.Fatalf("missing key: %q", line)
+		}
+		kf := strings.Fields(key)
+		switch kf[0] {
+		case "name":
+			if len(kf) != 1 {
+				t.Fatalf("name takes no arguments: %q", line)
+			}
+			flush()
+			reqs = make(reqsMap)
+			fns = nil
+			name = val
+			continue
+		case "build":
+			if len(kf) != 2 {
+				t.Fatalf("build takes one argument: %q", line)
+			}
+			fns = append(fns, func(t *testing.T) {
+				list, err := BuildList([]module.Version{m(kf[1])}, reqs)
+				checkList(t, key, list, err, val)
+			})
+			continue
+		case "upgrade*":
+			if len(kf) != 2 {
+				t.Fatalf("upgrade* takes one argument: %q", line)
+			}
+			fns = append(fns, func(t *testing.T) {
+				list, err := UpgradeAll(m(kf[1]), reqs)
+				checkList(t, key, list, err, val)
+			})
+			continue
+		case "upgradereq":
+			if len(kf) < 2 {
+				t.Fatalf("upgrade takes at least one argument: %q", line)
+			}
+			fns = append(fns, func(t *testing.T) {
+				list, err := Upgrade(m(kf[1]), reqs, ms(kf[2:])...)
+				if err == nil {
+					// Copy the reqs map, but substitute the upgraded requirements in
+					// place of the target's original requirements.
+					upReqs := make(reqsMap, len(reqs))
+					for m, r := range reqs {
+						upReqs[m] = r
+					}
+					upReqs[m(kf[1])] = list
+
+					list, err = Req(m(kf[1]), nil, upReqs)
+				}
+				checkList(t, key, list, err, val)
+			})
+			continue
+		case "upgrade":
+			if len(kf) < 2 {
+				t.Fatalf("upgrade takes at least one argument: %q", line)
+			}
+			fns = append(fns, func(t *testing.T) {
+				list, err := Upgrade(m(kf[1]), reqs, ms(kf[2:])...)
+				checkList(t, key, list, err, val)
+			})
+			continue
+		case "downgrade":
+			if len(kf) < 2 {
+				t.Fatalf("downgrade takes at least one argument: %q", line)
+			}
+			fns = append(fns, func(t *testing.T) {
+				list, err := Downgrade(m(kf[1]), reqs, ms(kf[1:])...)
+				checkList(t, key, list, err, val)
+			})
+			continue
+		case "req":
+			if len(kf) < 2 {
+				t.Fatalf("req takes at least one argument: %q", line)
+			}
+			fns = append(fns, func(t *testing.T) {
+				list, err := Req(m(kf[1]), kf[2:], reqs)
+				checkList(t, key, list, err, val)
+			})
+			continue
+		}
+		if len(kf) == 1 && 'A' <= key[0] && key[0] <= 'Z' {
+			var rs []module.Version
+			for _, f := range strings.Fields(val) {
+				r := m(f)
+				if reqs[r] == nil {
+					reqs[r] = []module.Version{}
+				}
+				rs = append(rs, r)
+			}
+			reqs[m(key)] = rs
+			continue
+		}
+		t.Fatalf("bad line: %q", line)
+	}
+	flush()
+}
+
+type reqsMap map[module.Version][]module.Version
+
+func (r reqsMap) Max(_, v1, v2 string) string {
+	if v1 == "none" || v2 == "" {
+		return v2
+	}
+	if v2 == "none" || v1 == "" {
+		return v1
+	}
+	if v1 < v2 {
+		return v2
+	}
+	return v1
+}
+
+func (r reqsMap) Upgrade(m module.Version) (module.Version, error) {
+	u := module.Version{Version: "none"}
+	for k := range r {
+		if k.Path == m.Path && r.Max(k.Path, u.Version, k.Version) == k.Version && !strings.HasSuffix(k.Version, ".hidden") {
+			u = k
+		}
+	}
+	if u.Path == "" {
+		return module.Version{}, fmt.Errorf("missing module: %v", module.Version{Path: m.Path})
+	}
+	return u, nil
+}
+
+func (r reqsMap) Previous(m module.Version) (module.Version, error) {
+	var p module.Version
+	for k := range r {
+		if k.Path == m.Path && p.Version < k.Version && k.Version < m.Version && !strings.HasSuffix(k.Version, ".hidden") {
+			p = k
+		}
+	}
+	if p.Path == "" {
+		return module.Version{Path: m.Path, Version: "none"}, nil
+	}
+	return p, nil
+}
+
+func (r reqsMap) Required(m module.Version) ([]module.Version, error) {
+	rr, ok := r[m]
+	if !ok {
+		return nil, fmt.Errorf("missing module: %v", m)
+	}
+	return rr, nil
+}