vendor/cmd/go/internal/mvs/mvs.go - vgo - Git at Google

 // 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"

 	"cmd/go/internal/module"
 	"cmd/go/internal/par"
 )

 // A Reqs is the requirement graph on which Minimal Version Selection (MVS) operates.
 //
 // The version strings are opaque except for the special versions "" and "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.
 	// TODO(rsc,bcmills): For all versions v, Max(v, "") must be "" ? Maybe.
 	//
 	// 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

 	// Latest returns the latest known version of the module at path
 	// (the one to use during UpgradeAll).
 	//
 	// Latest never returns version "none": if no module exists at the given path,
 	// it returns a non-nil error instead.
 	//
 	// TODO(bcmills): If path is the current module, must Latest return version
 	// "", or the most recent prior version?
 	Latest(path string) (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)
 }

 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) {
 	// Explore work graph in parallel in case reqs.Required
 	// does high-latency network operations.
 	var work par.Work
 	work.Add(target)
 	var (
 		mu  sync.Mutex
 		min = map[string]string{target.Path: target.Version}
 	)
 	work.Do(10, func(item interface{}) {
 		m := item.(module.Version)
 		required, _ := reqs.Required(m)

 		for _, r := range required {
 			work.Add(r)
 		}

 		mu.Lock()
 		defer mu.Unlock()
 		for _, r := range required {
 			if uses != nil {
 				uses[r] = append(uses[r], m)
 			}
 			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
 			}
 		}
 	})

 	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{Path: r.Path, Version: 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 results in the given build list.
 func Req(target module.Version, list []module.Version, reqs Reqs) ([]module.Version, error) {
 	// 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[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) {
 	// Explore work graph in parallel, like in buildList,
 	// but here the work item is only a path, not a path+version pair,
 	// because we always take the latest of any path.
 	var work par.Work
 	work.Add(target.Path)
 	var (
 		mu   sync.Mutex
 		list []module.Version
 		min  = map[string]string{target.Path: ""}
 	)
 	work.Do(10, func(item interface{}) {
 		path := item.(string)
 		m := module.Version{Path: path}
 		if path != target.Path {
 			latest, err := reqs.Latest(path)
 			if err != nil {
 				panic(err) // TODO
 			}
 			m.Version = latest.Version
 		}

 		required, err := reqs.Required(m)
 		if err != nil {
 			panic("TODO")
 		}

 		mu.Lock()
 		// Important: must append to list before calling work.Add (below).
 		// We expect the first work item (target) to be first in list.
 		list = append(list, m)
 		for _, r := range required {
 			if v, ok := min[r.Path]; !ok {
 				min[r.Path] = r.Version
 			} else {
 				min[r.Path] = reqs.Max(v, r.Version)
 			}
 		}
 		mu.Unlock()

 		for _, r := range required {
 			work.Add(r.Path)
 		}
 	})

 	for _, m := range list {
 		if reqs.Max(m.Version, min[m.Path]) != m.Version {
 			panic("mistake") // TODO
 		}
 	}

 	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.
 //
 // 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 {
 		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 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)
 }
	// 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"

	"cmd/go/internal/module"
	"cmd/go/internal/par"
	)

	// A Reqs is the requirement graph on which Minimal Version Selection (MVS) operates.
	//
	// The version strings are opaque except for the special versions "" and "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.
	// TODO(rsc,bcmills): For all versions v, Max(v, "") must be "" ? Maybe.
	//
	// 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

	// Latest returns the latest known version of the module at path
	// (the one to use during UpgradeAll).
	//
	// Latest never returns version "none": if no module exists at the given path,
	// it returns a non-nil error instead.
	//
	// TODO(bcmills): If path is the current module, must Latest return version
	// "", or the most recent prior version?
	Latest(path string) (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)
	}

	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) {
	// Explore work graph in parallel in case reqs.Required
	// does high-latency network operations.
	var work par.Work
	work.Add(target)
	var (
	mu sync.Mutex
	min = map[string]string{target.Path: target.Version}
	)
	work.Do(10, func(item interface{}) {
	m := item.(module.Version)
	required, _ := reqs.Required(m)

	for _, r := range required {
	work.Add(r)
	}

	mu.Lock()
	defer mu.Unlock()
	for _, r := range required {
	if uses != nil {
	uses[r] = append(uses[r], m)
	}
	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
	}
	}
	})

	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{Path: r.Path, Version: 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 results in the given build list.
	func Req(target module.Version, list []module.Version, reqs Reqs) ([]module.Version, error) {
	// 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[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) {
	// Explore work graph in parallel, like in buildList,
	// but here the work item is only a path, not a path+version pair,
	// because we always take the latest of any path.
	var work par.Work
	work.Add(target.Path)
	var (
	mu sync.Mutex
	list []module.Version
	min = map[string]string{target.Path: ""}
	)
	work.Do(10, func(item interface{}) {
	path := item.(string)
	m := module.Version{Path: path}
	if path != target.Path {
	latest, err := reqs.Latest(path)
	if err != nil {
	panic(err) // TODO
	}
	m.Version = latest.Version
	}

	required, err := reqs.Required(m)
	if err != nil {
	panic("TODO")
	}

	mu.Lock()
	// Important: must append to list before calling work.Add (below).
	// We expect the first work item (target) to be first in list.
	list = append(list, m)
	for _, r := range required {
	if v, ok := min[r.Path]; !ok {
	min[r.Path] = r.Version
	} else {
	min[r.Path] = reqs.Max(v, r.Version)
	}
	}
	mu.Unlock()

	for _, r := range required {
	work.Add(r.Path)
	}
	})

	for _, m := range list {
	if reqs.Max(m.Version, min[m.Path]) != m.Version {
	panic("mistake") // TODO
	}
	}

	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.
	//
	// 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 {
	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 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)
	}