Source file src/pkg/cmd/go/internal/mvs/mvs.go

     1	// Copyright 2018 The Go Authors. All rights reserved.
     2	// Use of this source code is governed by a BSD-style
     3	// license that can be found in the LICENSE file.
     4	
     5	// Package mvs implements Minimal Version Selection.
     6	// See https://research.swtch.com/vgo-mvs.
     7	package mvs
     8	
     9	import (
    10		"fmt"
    11		"sort"
    12		"strings"
    13		"sync"
    14		"sync/atomic"
    15	
    16		"cmd/go/internal/module"
    17		"cmd/go/internal/par"
    18	)
    19	
    20	// A Reqs is the requirement graph on which Minimal Version Selection (MVS) operates.
    21	//
    22	// The version strings are opaque except for the special version "none"
    23	// (see the documentation for module.Version). In particular, MVS does not
    24	// assume that the version strings are semantic versions; instead, the Max method
    25	// gives access to the comparison operation.
    26	//
    27	// It must be safe to call methods on a Reqs from multiple goroutines simultaneously.
    28	// Because a Reqs may read the underlying graph from the network on demand,
    29	// the MVS algorithms parallelize the traversal to overlap network delays.
    30	type Reqs interface {
    31		// Required returns the module versions explicitly required by m itself.
    32		// The caller must not modify the returned list.
    33		Required(m module.Version) ([]module.Version, error)
    34	
    35		// Max returns the maximum of v1 and v2 (it returns either v1 or v2).
    36		//
    37		// For all versions v, Max(v, "none") must be v,
    38		// and for the target passed as the first argument to MVS functions,
    39		// Max(target, v) must be target.
    40		//
    41		// Note that v1 < v2 can be written Max(v1, v2) != v1
    42		// and similarly v1 <= v2 can be written Max(v1, v2) == v2.
    43		Max(v1, v2 string) string
    44	
    45		// Upgrade returns the upgraded version of m,
    46		// for use during an UpgradeAll operation.
    47		// If m should be kept as is, Upgrade returns m.
    48		// If m is not yet used in the build, then m.Version will be "none".
    49		// More typically, m.Version will be the version required
    50		// by some other module in the build.
    51		//
    52		// If no module version is available for the given path,
    53		// Upgrade returns a non-nil error.
    54		// TODO(rsc): Upgrade must be able to return errors,
    55		// but should "no latest version" just return m instead?
    56		Upgrade(m module.Version) (module.Version, error)
    57	
    58		// Previous returns the version of m.Path immediately prior to m.Version,
    59		// or "none" if no such version is known.
    60		Previous(m module.Version) (module.Version, error)
    61	}
    62	
    63	// BuildListError decorates an error that occurred gathering requirements
    64	// while constructing a build list. BuildListError prints the chain
    65	// of requirements to the module where the error occurred.
    66	type BuildListError struct {
    67		Err   error
    68		stack []buildListErrorElem
    69	}
    70	
    71	type buildListErrorElem struct {
    72		m module.Version
    73	
    74		// nextReason is the reason this module depends on the next module in the
    75		// stack. Typically either "requires", or "upgraded to".
    76		nextReason string
    77	}
    78	
    79	// Module returns the module where the error occurred. If the module stack
    80	// is empty, this returns a zero value.
    81	func (e *BuildListError) Module() module.Version {
    82		if len(e.stack) == 0 {
    83			return module.Version{}
    84		}
    85		return e.stack[0].m
    86	}
    87	
    88	func (e *BuildListError) Error() string {
    89		b := &strings.Builder{}
    90		stack := e.stack
    91	
    92		// Don't print modules at the beginning of the chain without a
    93		// version. These always seem to be the main module or a
    94		// synthetic module ("target@").
    95		for len(stack) > 0 && stack[len(stack)-1].m.Version == "" {
    96			stack = stack[:len(stack)-1]
    97		}
    98	
    99		for i := len(stack) - 1; i >= 1; i-- {
   100			fmt.Fprintf(b, "%s@%s %s\n\t", stack[i].m.Path, stack[i].m.Version, stack[i].nextReason)
   101		}
   102		if len(stack) == 0 {
   103			b.WriteString(e.Err.Error())
   104		} else {
   105			// Ensure that the final module path and version are included as part of the
   106			// error message.
   107			if _, ok := e.Err.(*module.ModuleError); ok {
   108				fmt.Fprintf(b, "%v", e.Err)
   109			} else {
   110				fmt.Fprintf(b, "%v", module.VersionError(stack[0].m, e.Err))
   111			}
   112		}
   113		return b.String()
   114	}
   115	
   116	// BuildList returns the build list for the target module.
   117	// The first element is the target itself, with the remainder of the list sorted by path.
   118	func BuildList(target module.Version, reqs Reqs) ([]module.Version, error) {
   119		return buildList(target, reqs, nil)
   120	}
   121	
   122	func buildList(target module.Version, reqs Reqs, upgrade func(module.Version) (module.Version, error)) ([]module.Version, error) {
   123		// Explore work graph in parallel in case reqs.Required
   124		// does high-latency network operations.
   125		type modGraphNode struct {
   126			m        module.Version
   127			required []module.Version
   128			upgrade  module.Version
   129			err      error
   130		}
   131		var (
   132			mu       sync.Mutex
   133			modGraph = map[module.Version]*modGraphNode{}
   134			min      = map[string]string{} // maps module path to minimum required version
   135			haveErr  int32
   136		)
   137		setErr := func(n *modGraphNode, err error) {
   138			n.err = err
   139			atomic.StoreInt32(&haveErr, 1)
   140		}
   141	
   142		var work par.Work
   143		work.Add(target)
   144		work.Do(10, func(item interface{}) {
   145			m := item.(module.Version)
   146	
   147			node := &modGraphNode{m: m}
   148			mu.Lock()
   149			modGraph[m] = node
   150			if v, ok := min[m.Path]; !ok || reqs.Max(v, m.Version) != v {
   151				min[m.Path] = m.Version
   152			}
   153			mu.Unlock()
   154	
   155			required, err := reqs.Required(m)
   156			if err != nil {
   157				setErr(node, err)
   158				return
   159			}
   160			node.required = required
   161			for _, r := range node.required {
   162				work.Add(r)
   163			}
   164	
   165			if upgrade != nil {
   166				u, err := upgrade(m)
   167				if err != nil {
   168					setErr(node, err)
   169					return
   170				}
   171				if u != m {
   172					node.upgrade = u
   173					work.Add(u)
   174				}
   175			}
   176		})
   177	
   178		// If there was an error, find the shortest path from the target to the
   179		// node where the error occurred so we can report a useful error message.
   180		if haveErr != 0 {
   181			// neededBy[a] = b means a was added to the module graph by b.
   182			neededBy := make(map[*modGraphNode]*modGraphNode)
   183			q := make([]*modGraphNode, 0, len(modGraph))
   184			q = append(q, modGraph[target])
   185			for len(q) > 0 {
   186				node := q[0]
   187				q = q[1:]
   188	
   189				if node.err != nil {
   190					err := &BuildListError{
   191						Err:   node.err,
   192						stack: []buildListErrorElem{{m: node.m}},
   193					}
   194					for n, prev := neededBy[node], node; n != nil; n, prev = neededBy[n], n {
   195						reason := "requires"
   196						if n.upgrade == prev.m {
   197							reason = "updating to"
   198						}
   199						err.stack = append(err.stack, buildListErrorElem{m: n.m, nextReason: reason})
   200					}
   201					return nil, err
   202				}
   203	
   204				neighbors := node.required
   205				if node.upgrade.Path != "" {
   206					neighbors = append(neighbors, node.upgrade)
   207				}
   208				for _, neighbor := range neighbors {
   209					nn := modGraph[neighbor]
   210					if neededBy[nn] != nil {
   211						continue
   212					}
   213					neededBy[nn] = node
   214					q = append(q, nn)
   215				}
   216			}
   217		}
   218	
   219		// The final list is the minimum version of each module found in the graph.
   220	
   221		if v := min[target.Path]; v != target.Version {
   222			// TODO(jayconrod): there is a special case in modload.mvsReqs.Max
   223			// that prevents us from selecting a newer version of a module
   224			// when the module has no version. This may only be the case for target.
   225			// Should we always panic when target has a version?
   226			// See golang.org/issue/31491, golang.org/issue/29773.
   227			panic(fmt.Sprintf("mistake: chose version %q instead of target %+v", v, target)) // TODO: Don't panic.
   228		}
   229	
   230		list := []module.Version{target}
   231		for path, vers := range min {
   232			if path != target.Path {
   233				list = append(list, module.Version{Path: path, Version: vers})
   234			}
   235	
   236			n := modGraph[module.Version{Path: path, Version: vers}]
   237			required := n.required
   238			for _, r := range required {
   239				v := min[r.Path]
   240				if r.Path != target.Path && reqs.Max(v, r.Version) != v {
   241					panic(fmt.Sprintf("mistake: version %q does not satisfy requirement %+v", v, r)) // TODO: Don't panic.
   242				}
   243			}
   244		}
   245	
   246		tail := list[1:]
   247		sort.Slice(tail, func(i, j int) bool {
   248			return tail[i].Path < tail[j].Path
   249		})
   250		return list, nil
   251	}
   252	
   253	// Req returns the minimal requirement list for the target module
   254	// that results in the given build list, with the constraint that all
   255	// module paths listed in base must appear in the returned list.
   256	func Req(target module.Version, list []module.Version, base []string, reqs Reqs) ([]module.Version, error) {
   257		// Note: Not running in parallel because we assume
   258		// that list came from a previous operation that paged
   259		// in all the requirements, so there's no I/O to overlap now.
   260	
   261		// Compute postorder, cache requirements.
   262		var postorder []module.Version
   263		reqCache := map[module.Version][]module.Version{}
   264		reqCache[target] = nil
   265		var walk func(module.Version) error
   266		walk = func(m module.Version) error {
   267			_, ok := reqCache[m]
   268			if ok {
   269				return nil
   270			}
   271			required, err := reqs.Required(m)
   272			if err != nil {
   273				return err
   274			}
   275			reqCache[m] = required
   276			for _, m1 := range required {
   277				if err := walk(m1); err != nil {
   278					return err
   279				}
   280			}
   281			postorder = append(postorder, m)
   282			return nil
   283		}
   284		for _, m := range list {
   285			if err := walk(m); err != nil {
   286				return nil, err
   287			}
   288		}
   289	
   290		// Walk modules in reverse post-order, only adding those not implied already.
   291		have := map[module.Version]bool{}
   292		walk = func(m module.Version) error {
   293			if have[m] {
   294				return nil
   295			}
   296			have[m] = true
   297			for _, m1 := range reqCache[m] {
   298				walk(m1)
   299			}
   300			return nil
   301		}
   302		max := map[string]string{}
   303		for _, m := range list {
   304			if v, ok := max[m.Path]; ok {
   305				max[m.Path] = reqs.Max(m.Version, v)
   306			} else {
   307				max[m.Path] = m.Version
   308			}
   309		}
   310		// First walk the base modules that must be listed.
   311		var min []module.Version
   312		for _, path := range base {
   313			m := module.Version{Path: path, Version: max[path]}
   314			min = append(min, m)
   315			walk(m)
   316		}
   317		// Now the reverse postorder to bring in anything else.
   318		for i := len(postorder) - 1; i >= 0; i-- {
   319			m := postorder[i]
   320			if max[m.Path] != m.Version {
   321				// Older version.
   322				continue
   323			}
   324			if !have[m] {
   325				min = append(min, m)
   326				walk(m)
   327			}
   328		}
   329		sort.Slice(min, func(i, j int) bool {
   330			return min[i].Path < min[j].Path
   331		})
   332		return min, nil
   333	}
   334	
   335	// UpgradeAll returns a build list for the target module
   336	// in which every module is upgraded to its latest version.
   337	func UpgradeAll(target module.Version, reqs Reqs) ([]module.Version, error) {
   338		return buildList(target, reqs, func(m module.Version) (module.Version, error) {
   339			if m.Path == target.Path {
   340				return target, nil
   341			}
   342	
   343			return reqs.Upgrade(m)
   344		})
   345	}
   346	
   347	// Upgrade returns a build list for the target module
   348	// in which the given additional modules are upgraded.
   349	func Upgrade(target module.Version, reqs Reqs, upgrade ...module.Version) ([]module.Version, error) {
   350		list, err := reqs.Required(target)
   351		if err != nil {
   352			return nil, err
   353		}
   354		// TODO: Maybe if an error is given,
   355		// rerun with BuildList(upgrade[0], reqs) etc
   356		// to find which ones are the buggy ones.
   357		list = append([]module.Version(nil), list...)
   358		list = append(list, upgrade...)
   359		return BuildList(target, &override{target, list, reqs})
   360	}
   361	
   362	// Downgrade returns a build list for the target module
   363	// in which the given additional modules are downgraded.
   364	//
   365	// The versions to be downgraded may be unreachable from reqs.Latest and
   366	// reqs.Previous, but the methods of reqs must otherwise handle such versions
   367	// correctly.
   368	func Downgrade(target module.Version, reqs Reqs, downgrade ...module.Version) ([]module.Version, error) {
   369		list, err := reqs.Required(target)
   370		if err != nil {
   371			return nil, err
   372		}
   373		max := make(map[string]string)
   374		for _, r := range list {
   375			max[r.Path] = r.Version
   376		}
   377		for _, d := range downgrade {
   378			if v, ok := max[d.Path]; !ok || reqs.Max(v, d.Version) != d.Version {
   379				max[d.Path] = d.Version
   380			}
   381		}
   382	
   383		var (
   384			added    = make(map[module.Version]bool)
   385			rdeps    = make(map[module.Version][]module.Version)
   386			excluded = make(map[module.Version]bool)
   387		)
   388		var exclude func(module.Version)
   389		exclude = func(m module.Version) {
   390			if excluded[m] {
   391				return
   392			}
   393			excluded[m] = true
   394			for _, p := range rdeps[m] {
   395				exclude(p)
   396			}
   397		}
   398		var add func(module.Version)
   399		add = func(m module.Version) {
   400			if added[m] {
   401				return
   402			}
   403			added[m] = true
   404			if v, ok := max[m.Path]; ok && reqs.Max(m.Version, v) != v {
   405				exclude(m)
   406				return
   407			}
   408			list, err := reqs.Required(m)
   409			if err != nil {
   410				// If we can't load the requirements, we couldn't load the go.mod file.
   411				// There are a number of reasons this can happen, but this usually
   412				// means an older version of the module had a missing or invalid
   413				// go.mod file. For example, if example.com/mod released v2.0.0 before
   414				// migrating to modules (v2.0.0+incompatible), then added a valid go.mod
   415				// in v2.0.1, downgrading from v2.0.1 would cause this error.
   416				//
   417				// TODO(golang.org/issue/31730, golang.org/issue/30134): if the error
   418				// is transient (we couldn't download go.mod), return the error from
   419				// Downgrade. Currently, we can't tell what kind of error it is.
   420				exclude(m)
   421			}
   422			for _, r := range list {
   423				add(r)
   424				if excluded[r] {
   425					exclude(m)
   426					return
   427				}
   428				rdeps[r] = append(rdeps[r], m)
   429			}
   430		}
   431	
   432		var out []module.Version
   433		out = append(out, target)
   434	List:
   435		for _, r := range list {
   436			add(r)
   437			for excluded[r] {
   438				p, err := reqs.Previous(r)
   439				if err != nil {
   440					// This is likely a transient error reaching the repository,
   441					// rather than a permanent error with the retrieved version.
   442					//
   443					// TODO(golang.org/issue/31730, golang.org/issue/30134):
   444					// decode what to do based on the actual error.
   445					return nil, err
   446				}
   447				// If the target version is a pseudo-version, it may not be
   448				// included when iterating over prior versions using reqs.Previous.
   449				// Insert it into the right place in the iteration.
   450				// If v is excluded, p should be returned again by reqs.Previous on the next iteration.
   451				if v := max[r.Path]; reqs.Max(v, r.Version) != v && reqs.Max(p.Version, v) != p.Version {
   452					p.Version = v
   453				}
   454				if p.Version == "none" {
   455					continue List
   456				}
   457				add(p)
   458				r = p
   459			}
   460			out = append(out, r)
   461		}
   462	
   463		return out, nil
   464	}
   465	
   466	type override struct {
   467		target module.Version
   468		list   []module.Version
   469		Reqs
   470	}
   471	
   472	func (r *override) Required(m module.Version) ([]module.Version, error) {
   473		if m == r.target {
   474			return r.list, nil
   475		}
   476		return r.Reqs.Required(m)
   477	}
   478	

View as plain text