mvs

Documentation

Overview

Package mvs implements Minimal Version Selection. See https://research.swtch.com/vgo-mvs.

Index

• func BuildList[V comparable](targets []V, reqs Reqs[V]) ([]V, error)
• func Downgrade[V comparable](target V, reqs DowngradeReqs[V], downgrade ...V) ([]V, error)
• func Req[V comparable](mainModule V, base []string, reqs Reqs[V]) ([]V, error)
• func Upgrade[V comparable](target V, reqs UpgradeReqs[V], upgrade ...V) ([]V, error)
• func UpgradeAll[V comparable](target V, reqs UpgradeReqs[V]) ([]V, error)
• type BuildListError
  • func NewBuildListError[V comparable](err error, path []V, vs Versions[V], isVersionChange func(from, to V) bool) *BuildListError[V]
  • func (e *BuildListError[V]) Error() string
  • func (e *BuildListError[V]) Module() V
• type DowngradeReqs
• type Graph
  • func NewGraph[V comparable](v Versions[V], cmp func(string, string) int, roots []V) *Graph[V]
  • func (g *Graph[V]) BuildList() []V
  • func (g *Graph[V]) FindPath(f func(V) bool) []V
  • func (g *Graph[V]) Require(m V, reqs []V)
  • func (g *Graph[V]) RequiredBy(m V) (reqs []V, ok bool)
  • func (g *Graph[V]) Selected(path string) (version string)
  • func (g *Graph[V]) WalkBreadthFirst(f func(m V))
• type Reqs
• type UpgradeReqs
• type Versions

Functions

func BuildList

func BuildList[V comparable](targets []V, reqs Reqs[V]) ([]V, error)

BuildList returns the build list for the target module.

target is the root vertex of a module requirement graph. For cmd/cue, 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 Downgrade

func Downgrade[V comparable](target V, reqs DowngradeReqs[V], downgrade ...V) ([]V, error)

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 Req

func Req[V comparable](mainModule V, base []string, reqs Reqs[V]) ([]V, error)

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 Upgrade

func Upgrade[V comparable](target V, reqs UpgradeReqs[V], upgrade ...V) ([]V, error)

Upgrade returns a build list for the target module in which the given additional modules are upgraded.

func UpgradeAll

func UpgradeAll[V comparable](target V, reqs UpgradeReqs[V]) ([]V, error)

UpgradeAll returns a build list for the target module in which every module is upgraded to its latest version.

Types

type BuildListError

type BuildListError[V comparable] struct {
	Err error
	// contains filtered or unexported fields
}

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.

func NewBuildListError

func NewBuildListError[V comparable](err error, path []V, vs Versions[V], isVersionChange func(from, to V) bool) *BuildListError[V]

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 (*BuildListError[V]) Error

func (e *BuildListError[V]) Error() string

func (*BuildListError[V]) Module

func (e *BuildListError[V]) Module() V

Module returns the module where the error occurred. If the module stack is empty, this returns a zero value.

type DowngradeReqs

type DowngradeReqs[V comparable] interface {
	Reqs[V]

	// Previous returns the version of m.Path immediately prior to m.Version,
	// or "none" if no such version is known.
	Previous(m V) (V, error)
}

A DowngradeReqs is a Reqs that can also identify available downgrades.

type Graph

type Graph[V comparable] struct {
	// contains filtered or unexported fields
}

Graph implements an incremental version of the MVS algorithm, with the requirements pushed by the caller instead of pulled by the MVS traversal.

func NewGraph

func NewGraph[V comparable](v Versions[V], cmp func(string, string) int, roots []V) *Graph[V]

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 (*Graph[V]) BuildList

func (g *Graph[V]) BuildList() []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 (*Graph[V]) FindPath

func (g *Graph[V]) FindPath(f func(V) bool) []V

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 (*Graph[V]) Require

func (g *Graph[V]) Require(m V, reqs []V)

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 (*Graph[V]) RequiredBy

func (g *Graph[V]) RequiredBy(m V) (reqs []V, ok bool)

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 (*Graph[V]) Selected

func (g *Graph[V]) Selected(path string) (version string)

Selected returns the selected version of the given module path.

If no version is selected, Selected returns version "none".

func (*Graph[V]) WalkBreadthFirst

func (g *Graph[V]) WalkBreadthFirst(f func(m V))

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.

type Reqs

type Reqs[V comparable] interface {
	Versions[V]

	// Required returns the module versions explicitly required by m itself.
	// The caller must not modify the returned list.
	Required(m V) ([]V, 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
}

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 V). 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 UpgradeReqs

type UpgradeReqs[V comparable] interface {
	Reqs[V]

	// 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 V) (V, error)
}

An UpgradeReqs is a Reqs that can also identify available upgrades.

type Versions

type Versions[V any] interface {
	// New creates a new instance of V holding the
	// given module path and version.
	New(path, version string) (V, error)
	// Path returns the path part of V.
	Path(v V) string
	// Version returns the version part of V.
	Version(v V) string
}

Versions is an interface that should be provided by implementations to define the mvs algorithm in terms of their own version type V, where a version type holds a (module path, module version) pair.