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