From 73df946d56c74384511a194dd01dbe099584fd1a Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 28 Apr 2024 15:14:23 +0200 Subject: Adding upstream version 1.16.10. Signed-off-by: Daniel Baumann --- src/cmd/go/internal/mvs/errors.go | 101 +++++++ src/cmd/go/internal/mvs/mvs.go | 481 +++++++++++++++++++++++++++++++++ src/cmd/go/internal/mvs/mvs_test.go | 525 ++++++++++++++++++++++++++++++++++++ 3 files changed, 1107 insertions(+) create mode 100644 src/cmd/go/internal/mvs/errors.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..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 +} -- cgit v1.2.3