From f6ad4dcef54c5ce997a4bad5a6d86de229015700 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Tue, 16 Apr 2024 21:25:22 +0200 Subject: Adding upstream version 1.22.1. Signed-off-by: Daniel Baumann --- src/cmd/go/internal/mvs/errors.go | 105 ++++++ src/cmd/go/internal/mvs/graph.go | 226 +++++++++++++ src/cmd/go/internal/mvs/mvs.go | 488 +++++++++++++++++++++++++++ src/cmd/go/internal/mvs/mvs_test.go | 635 ++++++++++++++++++++++++++++++++++++ 4 files changed, 1454 insertions(+) create mode 100644 src/cmd/go/internal/mvs/errors.go create mode 100644 src/cmd/go/internal/mvs/graph.go create mode 100644 src/cmd/go/internal/mvs/mvs.go create mode 100644 src/cmd/go/internal/mvs/mvs_test.go (limited to 'src/cmd/go/internal/mvs') 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 +} -- cgit v1.2.3