cmd/go/internal/mvs: Minimal Version Selection
diff --git a/vendor/cmd/go/internal/mvs/mvs.go b/vendor/cmd/go/internal/mvs/mvs.go
new file mode 100644
index 0000000..c7ddb6f
--- /dev/null
+++ b/vendor/cmd/go/internal/mvs/mvs.go
@@ -0,0 +1,301 @@
+// 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/vgo3.
+package mvs
+
+import (
+ "fmt"
+ "sort"
+
+ "cmd/go/internal/module"
+)
+
+type Reqs interface {
+ Required(m module.Version) ([]module.Version, error)
+ Max(v1, v2 string) string
+ Latest(path string) (module.Version, error)
+ Previous(m module.Version) (module.Version, error)
+}
+
+type MissingModuleError struct {
+ Module module.Version
+}
+
+func (e *MissingModuleError) Error() string {
+ return fmt.Sprintf("missing module: %v", e.Module)
+}
+
+// BuildList returns the build list for the target module.
+func BuildList(target module.Version, reqs Reqs) ([]module.Version, error) {
+ return buildList(target, reqs, nil, nil)
+}
+
+func buildList(target module.Version, reqs Reqs, uses map[module.Version][]module.Version, vers map[string]string) ([]module.Version, error) {
+ var (
+ min = map[string]string{target.Path: target.Version}
+ todo = []module.Version{target}
+ seen = map[module.Version]bool{target: true}
+ )
+ for len(todo) > 0 {
+ m := todo[len(todo)-1]
+ todo = todo[:len(todo)-1]
+ required, _ := reqs.Required(m)
+ for _, r := range required {
+ if uses != nil {
+ uses[r] = append(uses[r], m)
+ }
+ if !seen[r] {
+ if v, ok := min[r.Path]; !ok {
+ min[r.Path] = r.Version
+ } else if max := reqs.Max(v, r.Version); max != v {
+ min[r.Path] = max
+ }
+ todo = append(todo, r)
+ seen[r] = true
+ }
+ }
+ }
+
+ if min[target.Path] != target.Version {
+ panic("unbuildable") // TODO
+ }
+
+ if vers == nil {
+ vers = make(map[string]string)
+ }
+ list := []module.Version{target}
+ for i := 0; i < len(list); i++ {
+ m := list[i]
+ required, err := reqs.Required(m)
+ if err != nil {
+ // TODO: Check error is decent.
+ return nil, err
+ }
+ for _, r := range required {
+ v := min[r.Path]
+ if reqs.Max(v, r.Version) != v {
+ panic("mistake") // TODO
+ }
+ if _, ok := vers[r.Path]; !ok {
+ vers[r.Path] = v
+ list = append(list, module.Version{r.Path, v})
+ }
+ }
+ }
+ 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
+// that result in the given build list.
+func Req(target module.Version, list []module.Version, reqs Reqs) ([]module.Version, error) {
+ // 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[string]string{}
+ walk = func(m module.Version) error {
+ if v, ok := have[m.Path]; ok && reqs.Max(m.Version, v) == v {
+ return nil
+ }
+ have[m.Path] = m.Version
+ for _, m1 := range reqCache[m] {
+ walk(m1)
+ }
+ return nil
+ }
+ max := map[string]string{}
+ for _, m := range list {
+ if max[m.Path] == "" {
+ max[m.Path] = m.Version
+ } else {
+ max[m.Path] = reqs.Max(m.Version, max[m.Path])
+ }
+ }
+ var min []module.Version
+ for i := len(postorder) - 1; i >= 0; i-- {
+ m := postorder[i]
+ if max[m.Path] != m.Version {
+ // Older version.
+ continue
+ }
+ if have[m.Path] != m.Version {
+ 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) {
+ have := map[string]bool{target.Path: true}
+ list := []module.Version{target}
+ for i := 0; i < len(list); i++ {
+ m := list[i]
+ required, err := reqs.Required(m)
+ if err != nil {
+ panic(err) // TODO
+ }
+ for _, r := range required {
+ latest, err := reqs.Latest(r.Path)
+ if err != nil {
+ panic(err) // TODO
+ }
+ if reqs.Max(latest.Version, r.Version) != latest.Version {
+ panic("mistake") // TODO
+ }
+ if !have[r.Path] {
+ have[r.Path] = true
+ list = append(list, module.Version{r.Path, latest.Version})
+ }
+ }
+ }
+ tail := list[1:]
+ sort.Slice(tail, func(i, j int) bool {
+ return tail[i].Path < tail[j].Path
+ })
+ return list, nil
+}
+
+// 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 {
+ panic(err) // TODO
+ }
+ // TODO: Maybe if an error is given,
+ // rerun with BuildList(upgrade[0], reqs) etc
+ // to find which ones are the buggy ones.
+ list = append([]module.Version(nil), list...)
+ list = append(list, upgrade...)
+ return BuildList(target, &override{target, list, reqs})
+}
+
+// Downgrade returns a build list for the target module
+// in which the given additional modules are downgraded.
+func Downgrade(target module.Version, reqs Reqs, downgrade ...module.Version) ([]module.Version, error) {
+ list, err := reqs.Required(target)
+ if err != nil {
+ panic(err) // TODO
+ }
+ 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 {
+ panic(err) // TODO
+ }
+ 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 {
+ return nil, err // TODO
+ }
+ 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/vendor/cmd/go/internal/mvs/mvs_test.go b/vendor/cmd/go/internal/mvs/mvs_test.go
new file mode 100644
index 0000000..26b2305
--- /dev/null
+++ b/vendor/cmd/go/internal/mvs/mvs_test.go
@@ -0,0 +1,343 @@
+// 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 (
+ "reflect"
+ "strings"
+ "testing"
+
+ "cmd/go/internal/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 G1
+upgrade A C4: A B1 C4 D4 E2 F1 G1
+downgrade A2 D2: A2 C4 D2
+
+# 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
+
+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: down3
+A:
+`
+
+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)
+ }
+ })
+ }
+ }
+ m := func(s string) module.Version {
+ return module.Version{s[:1], 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 arguments: %q", line)
+ }
+ fns = append(fns, func(t *testing.T) {
+ list, err := Upgrade(m(kf[1]), reqs, ms(kf[2:])...)
+ if err == nil {
+ list, err = Req(m(kf[1]), list, reqs)
+ }
+ checkList(t, key, list, err, val)
+ })
+ continue
+ case "upgrade":
+ if len(kf) < 2 {
+ t.Fatalf("upgrade takes at least one arguments: %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 arguments: %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
+ }
+ 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 < v2 {
+ return v2
+ }
+ return v1
+}
+
+func (r reqsMap) Latest(path string) (module.Version, error) {
+ var m module.Version
+ for k := range r {
+ if k.Path == path && m.Version < k.Version {
+ m = k
+ }
+ }
+ if m.Path == "" {
+ return module.Version{}, &MissingModuleError{module.Version{path, ""}}
+ }
+ return m, 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 {
+ p = k
+ }
+ }
+ if p.Path == "" {
+ return module.Version{m.Path, "none"}, nil
+ }
+ return p, nil
+}
+
+func (r reqsMap) Required(m module.Version) ([]module.Version, error) {
+ rr, ok := r[m]
+ if !ok {
+ return nil, &MissingModuleError{m}
+ }
+ return rr, nil
+}
