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.go101
-rw-r--r--src/cmd/go/internal/mvs/mvs.go481
-rw-r--r--src/cmd/go/internal/mvs/mvs_test.go525
3 files changed, 1107 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..5564965
--- /dev/null
+++ b/src/cmd/go/internal/mvs/errors.go
@@ -0,0 +1,101 @@
+// 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 isUpgrade function reports whether a path step is due to an upgrade.
+// A nil isUpgrade function indicates that none of the path steps are due to upgrades.
+func NewBuildListError(err error, path []module.Version, isUpgrade func(from, to module.Version) bool) *BuildListError {
+ stack := make([]buildListErrorElem, 0, len(path))
+ for len(path) > 1 {
+ reason := "requires"
+ if isUpgrade != nil && isUpgrade(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/mvs.go b/src/cmd/go/internal/mvs/mvs.go
new file mode 100644
index 0000000..b630b61
--- /dev/null
+++ b/src/cmd/go/internal/mvs/mvs.go
@@ -0,0 +1,481 @@
+// 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"
+ "sort"
+ "sync"
+ "sync/atomic"
+
+ "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
+
+ // 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)
+
+ // 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(target module.Version, reqs Reqs) ([]module.Version, error) {
+ return buildList(target, reqs, nil)
+}
+
+func buildList(target module.Version, reqs Reqs, upgrade func(module.Version) (module.Version, error)) ([]module.Version, error) {
+ // Explore work graph in parallel in case reqs.Required
+ // does high-latency network operations.
+ type modGraphNode struct {
+ m module.Version
+ required []module.Version
+ upgrade module.Version
+ err error
+ }
+ var (
+ mu sync.Mutex
+ modGraph = map[module.Version]*modGraphNode{}
+ min = map[string]string{} // maps module path to minimum required version
+ haveErr int32
+ )
+ setErr := func(n *modGraphNode, err error) {
+ n.err = err
+ atomic.StoreInt32(&haveErr, 1)
+ }
+
+ var work par.Work
+ work.Add(target)
+ work.Do(10, func(item interface{}) {
+ m := item.(module.Version)
+
+ node := &modGraphNode{m: m}
+ mu.Lock()
+ modGraph[m] = node
+ if m.Version != "none" {
+ if v, ok := min[m.Path]; !ok || reqs.Max(v, m.Version) != v {
+ min[m.Path] = m.Version
+ }
+ }
+ mu.Unlock()
+
+ if m.Version != "none" {
+ required, err := reqs.Required(m)
+ if err != nil {
+ setErr(node, err)
+ return
+ }
+ node.required = required
+ for _, r := range node.required {
+ work.Add(r)
+ }
+ }
+
+ if upgrade != nil {
+ u, err := upgrade(m)
+ if err != nil {
+ setErr(node, err)
+ return
+ }
+ if u != m {
+ node.upgrade = u
+ work.Add(u)
+ }
+ }
+ })
+
+ // 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 haveErr != 0 {
+ // neededBy[a] = b means a was added to the module graph by b.
+ neededBy := make(map[*modGraphNode]*modGraphNode)
+ q := make([]*modGraphNode, 0, len(modGraph))
+ q = append(q, modGraph[target])
+ for len(q) > 0 {
+ node := q[0]
+ q = q[1:]
+
+ if node.err != nil {
+ pathUpgrade := map[module.Version]module.Version{}
+
+ // Construct the error path reversed (from the error to the main module),
+ // then reverse it to obtain the usual order (from the main module to
+ // the error).
+ errPath := []module.Version{node.m}
+ for n, prev := neededBy[node], node; n != nil; n, prev = neededBy[n], n {
+ if n.upgrade == prev.m {
+ pathUpgrade[n.m] = prev.m
+ }
+ errPath = append(errPath, n.m)
+ }
+ i, j := 0, len(errPath)-1
+ for i < j {
+ errPath[i], errPath[j] = errPath[j], errPath[i]
+ i++
+ j--
+ }
+
+ isUpgrade := func(from, to module.Version) bool {
+ return pathUpgrade[from] == to
+ }
+
+ return nil, NewBuildListError(node.err, errPath, isUpgrade)
+ }
+
+ neighbors := node.required
+ if node.upgrade.Path != "" {
+ neighbors = append(neighbors, node.upgrade)
+ }
+ for _, neighbor := range neighbors {
+ nn := modGraph[neighbor]
+ if neededBy[nn] != nil {
+ continue
+ }
+ neededBy[nn] = node
+ q = append(q, nn)
+ }
+ }
+ }
+
+ // The final list is the minimum version of each module found in the graph.
+
+ if v := min[target.Path]; v != target.Version {
+ // 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 version %q instead of target %+v", v, target)) // TODO: Don't panic.
+ }
+
+ list := []module.Version{target}
+ for path, vers := range min {
+ if path != target.Path {
+ list = append(list, module.Version{Path: path, Version: vers})
+ }
+
+ n := modGraph[module.Version{Path: path, Version: vers}]
+ required := n.required
+ for _, r := range required {
+ if r.Version == "none" {
+ continue
+ }
+ v := min[r.Path]
+ if r.Path != target.Path && reqs.Max(v, r.Version) != v {
+ panic(fmt.Sprintf("mistake: version %q does not satisfy requirement %+v", v, r)) // TODO: Don't panic.
+ }
+ }
+ }
+
+ tail := list[1:]
+ sort.Slice(tail, func(i, j int) bool {
+ return tail[i].Path < tail[j].Path
+ })
+ 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(target module.Version, base []string, reqs Reqs) ([]module.Version, error) {
+ list, err := BuildList(target, 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.
+
+ // Compute postorder, cache requirements.
+ var postorder []module.Version
+ reqCache := map[module.Version][]module.Version{}
+ reqCache[target] = 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
+ }
+ max := map[string]string{}
+ for _, m := range list {
+ if v, ok := max[m.Path]; ok {
+ max[m.Path] = reqs.Max(m.Version, v)
+ } else {
+ max[m.Path] = m.Version
+ }
+ }
+ // First walk the base modules that must be listed.
+ var min []module.Version
+ for _, path := range base {
+ m := module.Version{Path: path, Version: max[path]}
+ min = append(min, m)
+ walk(m)
+ }
+ // 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 Reqs) ([]module.Version, error) {
+ return buildList(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 Reqs, 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(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 Reqs, downgrade ...module.Version) ([]module.Version, error) {
+ list, err := reqs.Required(target)
+ if err != nil {
+ return nil, err
+ }
+ 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 {
+ 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)
+ }
+ for _, r := range list {
+ add(r)
+ if excluded[r] {
+ exclude(m)
+ return
+ }
+ rdeps[r] = append(rdeps[r], m)
+ }
+ }
+
+ var out []module.Version
+ out = append(out, 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
+ }
+ out = append(out, r)
+ }
+
+ return out, nil
+}
+
+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..721cd96
--- /dev/null
+++ b/src/cmd/go/internal/mvs/mvs_test.go
@@ -0,0 +1,525 @@
+// 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
+downgrade A2 D2: A2 C4 D2
+
+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
+
+name: down2
+A: B2 E2
+B1:
+B2: C2 F2
+C1:
+D1:
+C2: D2 E2
+D2: B2
+E2: D2
+E1:
+F1:
+downgrade A F1: A B1 E1
+
+name: downcycle
+A: A B2
+B2: A
+B1:
+downgrade A B1: A B1
+
+# golang.org/issue/25542.
+name: noprev1
+A: B4 C2
+B2.hidden:
+C2:
+downgrade A B2.hidden: A B2.hidden C2
+
+name: noprev2
+A: B4 C2
+B2.hidden:
+B1:
+C2:
+downgrade A B2.hidden: A B2.hidden C2
+
+name: noprev3
+A: B4 C2
+B3:
+B2.hidden:
+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
+`
+
+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(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-09-27 07:27:43 +0000