summaryrefslogtreecommitdiffstats
path: root/src/cmd/go/internal/mvs
diff options
context:
space:
mode:
Diffstat (limited to 'src/cmd/go/internal/mvs')
-rw-r--r--src/cmd/go/internal/mvs/errors.go103
-rw-r--r--src/cmd/go/internal/mvs/graph.go223
-rw-r--r--src/cmd/go/internal/mvs/mvs.go488
-rw-r--r--src/cmd/go/internal/mvs/mvs_test.go635
4 files changed, 1449 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..bf183ce
--- /dev/null
+++ b/src/cmd/go/internal/mvs/errors.go
@@ -0,0 +1,103 @@
+// 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()
+}
diff --git a/src/cmd/go/internal/mvs/graph.go b/src/cmd/go/internal/mvs/graph.go
new file mode 100644
index 0000000..c5de486
--- /dev/null
+++ b/src/cmd/go/internal/mvs/graph.go
@@ -0,0 +1,223 @@
+// 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"
+
+ "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(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(v1, v2 string) int, roots []module.Version) *Graph {
+ g := &Graph{
+ cmp: cmp,
+ roots: roots[:len(roots):len(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(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 = reqs[:len(reqs):len(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(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})
+ }
+ }
+ module.Sort(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..eb33ebd
--- /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).
+ //
+ // 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(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(v1, v2 string) int {
+ if reqs.Max(v1, v2) != v1 {
+ return -1
+ }
+ if reqs.Max(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
+ for _, target := range targets {
+ work.Add(target)
+ }
+ work.Do(10, func(item any) {
+ m := item.(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(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(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.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(v, r.Version) != v && reqs.Max(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..26d004f
--- /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(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
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-28 11:24:57 +0000