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