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