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

Documentation: cmd/go/internal/mvs

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

View as plain text