Source file src/cmd/go/internal/modload/buildlist.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 modload
     6  
     7  import (
     8  	"context"
     9  	"errors"
    10  	"fmt"
    11  	"maps"
    12  	"os"
    13  	"runtime"
    14  	"runtime/debug"
    15  	"slices"
    16  	"strings"
    17  	"sync"
    18  	"sync/atomic"
    19  
    20  	"cmd/go/internal/base"
    21  	"cmd/go/internal/cfg"
    22  	"cmd/go/internal/gover"
    23  	"cmd/go/internal/mvs"
    24  	"cmd/go/internal/par"
    25  
    26  	"golang.org/x/mod/module"
    27  )
    28  
    29  // A Requirements represents a logically-immutable set of root module requirements.
    30  type Requirements struct {
    31  	// pruning is the pruning at which the requirement graph is computed.
    32  	//
    33  	// If unpruned, the graph includes all transitive requirements regardless
    34  	// of whether the requiring module supports pruning.
    35  	//
    36  	// If pruned, the graph includes only the root modules, the explicit
    37  	// requirements of those root modules, and the transitive requirements of only
    38  	// the root modules that do not support pruning.
    39  	//
    40  	// If workspace, the graph includes only the workspace modules, the explicit
    41  	// requirements of the workspace modules, and the transitive requirements of
    42  	// the workspace modules that do not support pruning.
    43  	pruning modPruning
    44  
    45  	// rootModules is the set of root modules of the graph, sorted and capped to
    46  	// length. It may contain duplicates, and may contain multiple versions for a
    47  	// given module path. The root modules of the graph are the set of main
    48  	// modules in workspace mode, and the main module's direct requirements
    49  	// outside workspace mode.
    50  	//
    51  	// The roots are always expected to contain an entry for the "go" module,
    52  	// indicating the Go language version in use.
    53  	rootModules    []module.Version
    54  	maxRootVersion map[string]string
    55  
    56  	// direct is the set of module paths for which we believe the module provides
    57  	// a package directly imported by a package or test in the main module.
    58  	//
    59  	// The "direct" map controls which modules are annotated with "// indirect"
    60  	// comments in the go.mod file, and may impact which modules are listed as
    61  	// explicit roots (vs. indirect-only dependencies). However, it should not
    62  	// have a semantic effect on the build list overall.
    63  	//
    64  	// The initial direct map is populated from the existing "// indirect"
    65  	// comments (or lack thereof) in the go.mod file. It is updated by the
    66  	// package loader: dependencies may be promoted to direct if new
    67  	// direct imports are observed, and may be demoted to indirect during
    68  	// 'go mod tidy' or 'go mod vendor'.
    69  	//
    70  	// The direct map is keyed by module paths, not module versions. When a
    71  	// module's selected version changes, we assume that it remains direct if the
    72  	// previous version was a direct dependency. That assumption might not hold in
    73  	// rare cases (such as if a dependency splits out a nested module, or merges a
    74  	// nested module back into a parent module).
    75  	direct map[string]bool
    76  
    77  	graphOnce sync.Once // guards writes to (but not reads from) graph
    78  	graph     atomic.Pointer[cachedGraph]
    79  }
    80  
    81  // A cachedGraph is a non-nil *ModuleGraph, together with any error discovered
    82  // while loading that graph.
    83  type cachedGraph struct {
    84  	mg  *ModuleGraph
    85  	err error // If err is non-nil, mg may be incomplete (but must still be non-nil).
    86  }
    87  
    88  // requirements is the requirement graph for the main module.
    89  //
    90  // It is always non-nil if the main module's go.mod file has been loaded.
    91  //
    92  // This variable should only be read from the loadModFile function, and should
    93  // only be written in the loadModFile and commitRequirements functions.
    94  // All other functions that need or produce a *Requirements should
    95  // accept and/or return an explicit parameter.
    96  var requirements *Requirements
    97  
    98  func mustHaveGoRoot(roots []module.Version) {
    99  	for _, m := range roots {
   100  		if m.Path == "go" {
   101  			return
   102  		}
   103  	}
   104  	panic("go: internal error: missing go root module")
   105  }
   106  
   107  // newRequirements returns a new requirement set with the given root modules.
   108  // The dependencies of the roots will be loaded lazily at the first call to the
   109  // Graph method.
   110  //
   111  // The rootModules slice must be sorted according to gover.ModSort.
   112  // The caller must not modify the rootModules slice or direct map after passing
   113  // them to newRequirements.
   114  //
   115  // If vendoring is in effect, the caller must invoke initVendor on the returned
   116  // *Requirements before any other method.
   117  func newRequirements(pruning modPruning, rootModules []module.Version, direct map[string]bool) *Requirements {
   118  	mustHaveGoRoot(rootModules)
   119  
   120  	if pruning != workspace {
   121  		if workFilePath != "" {
   122  			panic("in workspace mode, but pruning is not workspace in newRequirements")
   123  		}
   124  	}
   125  
   126  	if pruning != workspace {
   127  		if workFilePath != "" {
   128  			panic("in workspace mode, but pruning is not workspace in newRequirements")
   129  		}
   130  		for i, m := range rootModules {
   131  			if m.Version == "" && MainModules.Contains(m.Path) {
   132  				panic(fmt.Sprintf("newRequirements called with untrimmed build list: rootModules[%v] is a main module", i))
   133  			}
   134  			if m.Path == "" || m.Version == "" {
   135  				panic(fmt.Sprintf("bad requirement: rootModules[%v] = %v", i, m))
   136  			}
   137  		}
   138  	}
   139  
   140  	rs := &Requirements{
   141  		pruning:        pruning,
   142  		rootModules:    rootModules,
   143  		maxRootVersion: make(map[string]string, len(rootModules)),
   144  		direct:         direct,
   145  	}
   146  
   147  	for i, m := range rootModules {
   148  		if i > 0 {
   149  			prev := rootModules[i-1]
   150  			if prev.Path > m.Path || (prev.Path == m.Path && gover.ModCompare(m.Path, prev.Version, m.Version) > 0) {
   151  				panic(fmt.Sprintf("newRequirements called with unsorted roots: %v", rootModules))
   152  			}
   153  		}
   154  
   155  		if v, ok := rs.maxRootVersion[m.Path]; ok && gover.ModCompare(m.Path, v, m.Version) >= 0 {
   156  			continue
   157  		}
   158  		rs.maxRootVersion[m.Path] = m.Version
   159  	}
   160  
   161  	if rs.maxRootVersion["go"] == "" {
   162  		panic(`newRequirements called without a "go" version`)
   163  	}
   164  	return rs
   165  }
   166  
   167  // String returns a string describing the Requirements for debugging.
   168  func (rs *Requirements) String() string {
   169  	return fmt.Sprintf("{%v %v}", rs.pruning, rs.rootModules)
   170  }
   171  
   172  // initVendor initializes rs.graph from the given list of vendored module
   173  // dependencies, overriding the graph that would normally be loaded from module
   174  // requirements.
   175  func (rs *Requirements) initVendor(vendorList []module.Version) {
   176  	rs.graphOnce.Do(func() {
   177  		roots := MainModules.Versions()
   178  		if inWorkspaceMode() {
   179  			// Use rs.rootModules to pull in the go and toolchain roots
   180  			// from the go.work file and preserve the invariant that all
   181  			// of rs.rootModules are in mg.g.
   182  			roots = rs.rootModules
   183  		}
   184  		mg := &ModuleGraph{
   185  			g: mvs.NewGraph(cmpVersion, roots),
   186  		}
   187  
   188  		if rs.pruning == pruned {
   189  			mainModule := MainModules.mustGetSingleMainModule()
   190  			// The roots of a single pruned module should already include every module in the
   191  			// vendor list, because the vendored modules are the same as those needed
   192  			// for graph pruning.
   193  			//
   194  			// Just to be sure, we'll double-check that here.
   195  			inconsistent := false
   196  			for _, m := range vendorList {
   197  				if v, ok := rs.rootSelected(m.Path); !ok || v != m.Version {
   198  					base.Errorf("go: vendored module %v should be required explicitly in go.mod", m)
   199  					inconsistent = true
   200  				}
   201  			}
   202  			if inconsistent {
   203  				base.Fatal(errGoModDirty)
   204  			}
   205  
   206  			// Now we can treat the rest of the module graph as effectively “pruned
   207  			// out”, as though we are viewing the main module from outside: in vendor
   208  			// mode, the root requirements *are* the complete module graph.
   209  			mg.g.Require(mainModule, rs.rootModules)
   210  		} else {
   211  			// The transitive requirements of the main module are not in general available
   212  			// from the vendor directory, and we don't actually know how we got from
   213  			// the roots to the final build list.
   214  			//
   215  			// Instead, we'll inject a fake "vendor/modules.txt" module that provides
   216  			// those transitive dependencies, and mark it as a dependency of the main
   217  			// module. That allows us to elide the actual structure of the module
   218  			// graph, but still distinguishes between direct and indirect
   219  			// dependencies.
   220  			vendorMod := module.Version{Path: "vendor/modules.txt", Version: ""}
   221  			if inWorkspaceMode() {
   222  				for _, m := range MainModules.Versions() {
   223  					reqs, _ := rootsFromModFile(m, MainModules.ModFile(m), omitToolchainRoot)
   224  					mg.g.Require(m, append(reqs, vendorMod))
   225  				}
   226  				mg.g.Require(vendorMod, vendorList)
   227  
   228  			} else {
   229  				mainModule := MainModules.mustGetSingleMainModule()
   230  				mg.g.Require(mainModule, append(rs.rootModules, vendorMod))
   231  				mg.g.Require(vendorMod, vendorList)
   232  			}
   233  		}
   234  
   235  		rs.graph.Store(&cachedGraph{mg, nil})
   236  	})
   237  }
   238  
   239  // GoVersion returns the Go language version for the Requirements.
   240  func (rs *Requirements) GoVersion() string {
   241  	v, _ := rs.rootSelected("go")
   242  	if v == "" {
   243  		panic("internal error: missing go version in modload.Requirements")
   244  	}
   245  	return v
   246  }
   247  
   248  // rootSelected returns the version of the root dependency with the given module
   249  // path, or the zero module.Version and ok=false if the module is not a root
   250  // dependency.
   251  func (rs *Requirements) rootSelected(path string) (version string, ok bool) {
   252  	if MainModules.Contains(path) {
   253  		return "", true
   254  	}
   255  	if v, ok := rs.maxRootVersion[path]; ok {
   256  		return v, true
   257  	}
   258  	return "", false
   259  }
   260  
   261  // hasRedundantRoot returns true if the root list contains multiple requirements
   262  // of the same module or a requirement on any version of the main module.
   263  // Redundant requirements should be pruned, but they may influence version
   264  // selection.
   265  func (rs *Requirements) hasRedundantRoot() bool {
   266  	for i, m := range rs.rootModules {
   267  		if MainModules.Contains(m.Path) || (i > 0 && m.Path == rs.rootModules[i-1].Path) {
   268  			return true
   269  		}
   270  	}
   271  	return false
   272  }
   273  
   274  // Graph returns the graph of module requirements loaded from the current
   275  // root modules (as reported by RootModules).
   276  //
   277  // Graph always makes a best effort to load the requirement graph despite any
   278  // errors, and always returns a non-nil *ModuleGraph.
   279  //
   280  // If the requirements of any relevant module fail to load, Graph also
   281  // returns a non-nil error of type *mvs.BuildListError.
   282  func (rs *Requirements) Graph(ctx context.Context) (*ModuleGraph, error) {
   283  	rs.graphOnce.Do(func() {
   284  		mg, mgErr := readModGraph(ctx, rs.pruning, rs.rootModules, nil)
   285  		rs.graph.Store(&cachedGraph{mg, mgErr})
   286  	})
   287  	cached := rs.graph.Load()
   288  	return cached.mg, cached.err
   289  }
   290  
   291  // IsDirect returns whether the given module provides a package directly
   292  // imported by a package or test in the main module.
   293  func (rs *Requirements) IsDirect(path string) bool {
   294  	return rs.direct[path]
   295  }
   296  
   297  // A ModuleGraph represents the complete graph of module dependencies
   298  // of a main module.
   299  //
   300  // If the main module supports module graph pruning, the graph does not include
   301  // transitive dependencies of non-root (implicit) dependencies.
   302  type ModuleGraph struct {
   303  	g         *mvs.Graph
   304  	loadCache par.ErrCache[module.Version, *modFileSummary]
   305  
   306  	buildListOnce sync.Once
   307  	buildList     []module.Version
   308  }
   309  
   310  var readModGraphDebugOnce sync.Once
   311  
   312  // readModGraph reads and returns the module dependency graph starting at the
   313  // given roots.
   314  //
   315  // The requirements of the module versions found in the unprune map are included
   316  // in the graph even if they would normally be pruned out.
   317  //
   318  // Unlike LoadModGraph, readModGraph does not attempt to diagnose or update
   319  // inconsistent roots.
   320  func readModGraph(ctx context.Context, pruning modPruning, roots []module.Version, unprune map[module.Version]bool) (*ModuleGraph, error) {
   321  	mustHaveGoRoot(roots)
   322  	if pruning == pruned {
   323  		// Enable diagnostics for lazy module loading
   324  		// (https://golang.org/ref/mod#lazy-loading) only if the module graph is
   325  		// pruned.
   326  		//
   327  		// In unpruned modules,we load the module graph much more aggressively (in
   328  		// order to detect inconsistencies that wouldn't be feasible to spot-check),
   329  		// so it wouldn't be useful to log when that occurs (because it happens in
   330  		// normal operation all the time).
   331  		readModGraphDebugOnce.Do(func() {
   332  			for _, f := range strings.Split(os.Getenv("GODEBUG"), ",") {
   333  				switch f {
   334  				case "lazymod=log":
   335  					debug.PrintStack()
   336  					fmt.Fprintf(os.Stderr, "go: read full module graph.\n")
   337  				case "lazymod=strict":
   338  					debug.PrintStack()
   339  					base.Fatalf("go: read full module graph (forbidden by GODEBUG=lazymod=strict).")
   340  				}
   341  			}
   342  		})
   343  	}
   344  
   345  	var graphRoots []module.Version
   346  	if inWorkspaceMode() {
   347  		graphRoots = roots
   348  	} else {
   349  		graphRoots = MainModules.Versions()
   350  	}
   351  	var (
   352  		mu       sync.Mutex // guards mg.g and hasError during loading
   353  		hasError bool
   354  		mg       = &ModuleGraph{
   355  			g: mvs.NewGraph(cmpVersion, graphRoots),
   356  		}
   357  	)
   358  
   359  	if pruning != workspace {
   360  		if inWorkspaceMode() {
   361  			panic("pruning is not workspace in workspace mode")
   362  		}
   363  		mg.g.Require(MainModules.mustGetSingleMainModule(), roots)
   364  	}
   365  
   366  	type dedupKey struct {
   367  		m       module.Version
   368  		pruning modPruning
   369  	}
   370  	var (
   371  		loadQueue = par.NewQueue(runtime.GOMAXPROCS(0))
   372  		loading   sync.Map // dedupKey → nil; the set of modules that have been or are being loaded
   373  	)
   374  
   375  	// loadOne synchronously loads the explicit requirements for module m.
   376  	// It does not load the transitive requirements of m even if the go version in
   377  	// m's go.mod file indicates that it supports graph pruning.
   378  	loadOne := func(m module.Version) (*modFileSummary, error) {
   379  		return mg.loadCache.Do(m, func() (*modFileSummary, error) {
   380  			summary, err := goModSummary(m)
   381  
   382  			mu.Lock()
   383  			if err == nil {
   384  				mg.g.Require(m, summary.require)
   385  			} else {
   386  				hasError = true
   387  			}
   388  			mu.Unlock()
   389  
   390  			return summary, err
   391  		})
   392  	}
   393  
   394  	var enqueue func(m module.Version, pruning modPruning)
   395  	enqueue = func(m module.Version, pruning modPruning) {
   396  		if m.Version == "none" {
   397  			return
   398  		}
   399  
   400  		if _, dup := loading.LoadOrStore(dedupKey{m, pruning}, nil); dup {
   401  			// m has already been enqueued for loading. Since unpruned loading may
   402  			// follow cycles in the requirement graph, we need to return early
   403  			// to avoid making the load queue infinitely long.
   404  			return
   405  		}
   406  
   407  		loadQueue.Add(func() {
   408  			summary, err := loadOne(m)
   409  			if err != nil {
   410  				return // findError will report the error later.
   411  			}
   412  
   413  			// If the version in m's go.mod file does not support pruning, then we
   414  			// cannot assume that the explicit requirements of m (added by loadOne)
   415  			// are sufficient to build the packages it contains. We must load its full
   416  			// transitive dependency graph to be sure that we see all relevant
   417  			// dependencies. In addition, we must load the requirements of any module
   418  			// that is explicitly marked as unpruned.
   419  			nextPruning := summary.pruning
   420  			if pruning == unpruned {
   421  				nextPruning = unpruned
   422  			}
   423  			for _, r := range summary.require {
   424  				if pruning != pruned || summary.pruning == unpruned || unprune[r] {
   425  					enqueue(r, nextPruning)
   426  				}
   427  			}
   428  		})
   429  	}
   430  
   431  	mustHaveGoRoot(roots)
   432  	for _, m := range roots {
   433  		enqueue(m, pruning)
   434  	}
   435  	<-loadQueue.Idle()
   436  
   437  	// Reload any dependencies of the main modules which are not
   438  	// at their selected versions at workspace mode, because the
   439  	// requirements don't accurately reflect the transitive imports.
   440  	if pruning == workspace {
   441  		// hasDepsInAll contains the set of modules that need to be loaded
   442  		// at workspace pruning because any of their dependencies may
   443  		// provide packages in all.
   444  		hasDepsInAll := make(map[string]bool)
   445  		seen := map[module.Version]bool{}
   446  		for _, m := range roots {
   447  			hasDepsInAll[m.Path] = true
   448  		}
   449  		// This loop will terminate because it will call enqueue on each version of
   450  		// each dependency of the modules in hasDepsInAll at most once (and only
   451  		// calls enqueue on successively increasing versions of each dependency).
   452  		for {
   453  			needsEnqueueing := map[module.Version]bool{}
   454  			for p := range hasDepsInAll {
   455  				m := module.Version{Path: p, Version: mg.g.Selected(p)}
   456  				if !seen[m] {
   457  					needsEnqueueing[m] = true
   458  					continue
   459  				}
   460  				reqs, _ := mg.g.RequiredBy(m)
   461  				for _, r := range reqs {
   462  					s := module.Version{Path: r.Path, Version: mg.g.Selected(r.Path)}
   463  					if gover.ModCompare(r.Path, s.Version, r.Version) > 0 && !seen[s] {
   464  						needsEnqueueing[s] = true
   465  					}
   466  				}
   467  			}
   468  			// add all needs enqueueing to paths we care about
   469  			if len(needsEnqueueing) == 0 {
   470  				break
   471  			}
   472  
   473  			for p := range needsEnqueueing {
   474  				enqueue(p, workspace)
   475  				seen[p] = true
   476  				hasDepsInAll[p.Path] = true
   477  			}
   478  			<-loadQueue.Idle()
   479  		}
   480  	}
   481  
   482  	if hasError {
   483  		return mg, mg.findError()
   484  	}
   485  	return mg, nil
   486  }
   487  
   488  // RequiredBy returns the dependencies required by module m in the graph,
   489  // or ok=false if module m's dependencies are pruned out.
   490  //
   491  // The caller must not modify the returned slice, but may safely append to it
   492  // and may rely on it not to be modified.
   493  func (mg *ModuleGraph) RequiredBy(m module.Version) (reqs []module.Version, ok bool) {
   494  	return mg.g.RequiredBy(m)
   495  }
   496  
   497  // Selected returns the selected version of the module with the given path.
   498  //
   499  // If no version is selected, Selected returns version "none".
   500  func (mg *ModuleGraph) Selected(path string) (version string) {
   501  	return mg.g.Selected(path)
   502  }
   503  
   504  // WalkBreadthFirst invokes f once, in breadth-first order, for each module
   505  // version other than "none" that appears in the graph, regardless of whether
   506  // that version is selected.
   507  func (mg *ModuleGraph) WalkBreadthFirst(f func(m module.Version)) {
   508  	mg.g.WalkBreadthFirst(f)
   509  }
   510  
   511  // BuildList returns the selected versions of all modules present in the graph,
   512  // beginning with the main modules.
   513  //
   514  // The order of the remaining elements in the list is deterministic
   515  // but arbitrary.
   516  //
   517  // The caller must not modify the returned list, but may safely append to it
   518  // and may rely on it not to be modified.
   519  func (mg *ModuleGraph) BuildList() []module.Version {
   520  	mg.buildListOnce.Do(func() {
   521  		mg.buildList = slices.Clip(mg.g.BuildList())
   522  	})
   523  	return mg.buildList
   524  }
   525  
   526  func (mg *ModuleGraph) findError() error {
   527  	errStack := mg.g.FindPath(func(m module.Version) bool {
   528  		_, err := mg.loadCache.Get(m)
   529  		return err != nil && err != par.ErrCacheEntryNotFound
   530  	})
   531  	if len(errStack) > 0 {
   532  		_, err := mg.loadCache.Get(errStack[len(errStack)-1])
   533  		var noUpgrade func(from, to module.Version) bool
   534  		return mvs.NewBuildListError(err, errStack, noUpgrade)
   535  	}
   536  
   537  	return nil
   538  }
   539  
   540  func (mg *ModuleGraph) allRootsSelected() bool {
   541  	var roots []module.Version
   542  	if inWorkspaceMode() {
   543  		roots = MainModules.Versions()
   544  	} else {
   545  		roots, _ = mg.g.RequiredBy(MainModules.mustGetSingleMainModule())
   546  	}
   547  	for _, m := range roots {
   548  		if mg.Selected(m.Path) != m.Version {
   549  			return false
   550  		}
   551  	}
   552  	return true
   553  }
   554  
   555  // LoadModGraph loads and returns the graph of module dependencies of the main module,
   556  // without loading any packages.
   557  //
   558  // If the goVersion string is non-empty, the returned graph is the graph
   559  // as interpreted by the given Go version (instead of the version indicated
   560  // in the go.mod file).
   561  //
   562  // Modules are loaded automatically (and lazily) in LoadPackages:
   563  // LoadModGraph need only be called if LoadPackages is not,
   564  // typically in commands that care about modules but no particular package.
   565  func LoadModGraph(ctx context.Context, goVersion string) (*ModuleGraph, error) {
   566  	rs, err := loadModFile(ctx, nil)
   567  	if err != nil {
   568  		return nil, err
   569  	}
   570  
   571  	if goVersion != "" {
   572  		v, _ := rs.rootSelected("go")
   573  		if gover.Compare(v, gover.GoStrictVersion) >= 0 && gover.Compare(goVersion, v) < 0 {
   574  			return nil, fmt.Errorf("requested Go version %s cannot load module graph (requires Go >= %s)", goVersion, v)
   575  		}
   576  
   577  		pruning := pruningForGoVersion(goVersion)
   578  		if pruning == unpruned && rs.pruning != unpruned {
   579  			// Use newRequirements instead of convertDepth because convertDepth
   580  			// also updates roots; here, we want to report the unmodified roots
   581  			// even though they may seem inconsistent.
   582  			rs = newRequirements(unpruned, rs.rootModules, rs.direct)
   583  		}
   584  
   585  		return rs.Graph(ctx)
   586  	}
   587  
   588  	rs, mg, err := expandGraph(ctx, rs)
   589  	if err != nil {
   590  		return nil, err
   591  	}
   592  	requirements = rs
   593  	return mg, err
   594  }
   595  
   596  // expandGraph loads the complete module graph from rs.
   597  //
   598  // If the complete graph reveals that some root of rs is not actually the
   599  // selected version of its path, expandGraph computes a new set of roots that
   600  // are consistent. (With a pruned module graph, this may result in upgrades to
   601  // other modules due to requirements that were previously pruned out.)
   602  //
   603  // expandGraph returns the updated roots, along with the module graph loaded
   604  // from those roots and any error encountered while loading that graph.
   605  // expandGraph returns non-nil requirements and a non-nil graph regardless of
   606  // errors. On error, the roots might not be updated to be consistent.
   607  func expandGraph(ctx context.Context, rs *Requirements) (*Requirements, *ModuleGraph, error) {
   608  	mg, mgErr := rs.Graph(ctx)
   609  	if mgErr != nil {
   610  		// Without the graph, we can't update the roots: we don't know which
   611  		// versions of transitive dependencies would be selected.
   612  		return rs, mg, mgErr
   613  	}
   614  
   615  	if !mg.allRootsSelected() {
   616  		// The roots of rs are not consistent with the rest of the graph. Update
   617  		// them. In an unpruned module this is a no-op for the build list as a whole —
   618  		// it just promotes what were previously transitive requirements to be
   619  		// roots — but in a pruned module it may pull in previously-irrelevant
   620  		// transitive dependencies.
   621  
   622  		newRS, rsErr := updateRoots(ctx, rs.direct, rs, nil, nil, false)
   623  		if rsErr != nil {
   624  			// Failed to update roots, perhaps because of an error in a transitive
   625  			// dependency needed for the update. Return the original Requirements
   626  			// instead.
   627  			return rs, mg, rsErr
   628  		}
   629  		rs = newRS
   630  		mg, mgErr = rs.Graph(ctx)
   631  	}
   632  
   633  	return rs, mg, mgErr
   634  }
   635  
   636  // EditBuildList edits the global build list by first adding every module in add
   637  // to the existing build list, then adjusting versions (and adding or removing
   638  // requirements as needed) until every module in mustSelect is selected at the
   639  // given version.
   640  //
   641  // (Note that the newly-added modules might not be selected in the resulting
   642  // build list: they could be lower than existing requirements or conflict with
   643  // versions in mustSelect.)
   644  //
   645  // If the versions listed in mustSelect are mutually incompatible (due to one of
   646  // the listed modules requiring a higher version of another), EditBuildList
   647  // returns a *ConstraintError and leaves the build list in its previous state.
   648  //
   649  // On success, EditBuildList reports whether the selected version of any module
   650  // in the build list may have been changed (possibly to or from "none") as a
   651  // result.
   652  func EditBuildList(ctx context.Context, add, mustSelect []module.Version) (changed bool, err error) {
   653  	rs, changed, err := editRequirements(ctx, LoadModFile(ctx), add, mustSelect)
   654  	if err != nil {
   655  		return false, err
   656  	}
   657  	requirements = rs
   658  	return changed, err
   659  }
   660  
   661  // OverrideRoots edits the global requirement roots by replacing the specific module versions.
   662  func OverrideRoots(ctx context.Context, replace []module.Version) {
   663  	requirements = overrideRoots(ctx, requirements, replace)
   664  }
   665  
   666  func overrideRoots(ctx context.Context, rs *Requirements, replace []module.Version) *Requirements {
   667  	drop := make(map[string]bool)
   668  	for _, m := range replace {
   669  		drop[m.Path] = true
   670  	}
   671  	var roots []module.Version
   672  	for _, m := range rs.rootModules {
   673  		if !drop[m.Path] {
   674  			roots = append(roots, m)
   675  		}
   676  	}
   677  	roots = append(roots, replace...)
   678  	gover.ModSort(roots)
   679  	return newRequirements(rs.pruning, roots, rs.direct)
   680  }
   681  
   682  // A ConstraintError describes inconsistent constraints in EditBuildList
   683  type ConstraintError struct {
   684  	// Conflict lists the source of the conflict for each version in mustSelect
   685  	// that could not be selected due to the requirements of some other version in
   686  	// mustSelect.
   687  	Conflicts []Conflict
   688  }
   689  
   690  func (e *ConstraintError) Error() string {
   691  	b := new(strings.Builder)
   692  	b.WriteString("version constraints conflict:")
   693  	for _, c := range e.Conflicts {
   694  		fmt.Fprintf(b, "\n\t%s", c.Summary())
   695  	}
   696  	return b.String()
   697  }
   698  
   699  // A Conflict is a path of requirements starting at a root or proposed root in
   700  // the requirement graph, explaining why that root either causes a module passed
   701  // in the mustSelect list to EditBuildList to be unattainable, or introduces an
   702  // unresolvable error in loading the requirement graph.
   703  type Conflict struct {
   704  	// Path is a path of requirements starting at some module version passed in
   705  	// the mustSelect argument and ending at a module whose requirements make that
   706  	// version unacceptable. (Path always has len ≥ 1.)
   707  	Path []module.Version
   708  
   709  	// If Err is nil, Constraint is a module version passed in the mustSelect
   710  	// argument that has the same module path as, and a lower version than,
   711  	// the last element of the Path slice.
   712  	Constraint module.Version
   713  
   714  	// If Constraint is unset, Err is an error encountered when loading the
   715  	// requirements of the last element in Path.
   716  	Err error
   717  }
   718  
   719  // UnwrapModuleError returns c.Err, but unwraps it if it is a module.ModuleError
   720  // with a version and path matching the last entry in the Path slice.
   721  func (c Conflict) UnwrapModuleError() error {
   722  	me, ok := c.Err.(*module.ModuleError)
   723  	if ok && len(c.Path) > 0 {
   724  		last := c.Path[len(c.Path)-1]
   725  		if me.Path == last.Path && me.Version == last.Version {
   726  			return me.Err
   727  		}
   728  	}
   729  	return c.Err
   730  }
   731  
   732  // Summary returns a string that describes only the first and last modules in
   733  // the conflict path.
   734  func (c Conflict) Summary() string {
   735  	if len(c.Path) == 0 {
   736  		return "(internal error: invalid Conflict struct)"
   737  	}
   738  	first := c.Path[0]
   739  	last := c.Path[len(c.Path)-1]
   740  	if len(c.Path) == 1 {
   741  		if c.Err != nil {
   742  			return fmt.Sprintf("%s: %v", first, c.UnwrapModuleError())
   743  		}
   744  		return fmt.Sprintf("%s is above %s", first, c.Constraint.Version)
   745  	}
   746  
   747  	adverb := ""
   748  	if len(c.Path) > 2 {
   749  		adverb = "indirectly "
   750  	}
   751  	if c.Err != nil {
   752  		return fmt.Sprintf("%s %srequires %s: %v", first, adverb, last, c.UnwrapModuleError())
   753  	}
   754  	return fmt.Sprintf("%s %srequires %s, but %s is requested", first, adverb, last, c.Constraint.Version)
   755  }
   756  
   757  // String returns a string that describes the full conflict path.
   758  func (c Conflict) String() string {
   759  	if len(c.Path) == 0 {
   760  		return "(internal error: invalid Conflict struct)"
   761  	}
   762  	b := new(strings.Builder)
   763  	fmt.Fprintf(b, "%v", c.Path[0])
   764  	if len(c.Path) == 1 {
   765  		fmt.Fprintf(b, " found")
   766  	} else {
   767  		for _, r := range c.Path[1:] {
   768  			fmt.Fprintf(b, " requires\n\t%v", r)
   769  		}
   770  	}
   771  	if c.Constraint != (module.Version{}) {
   772  		fmt.Fprintf(b, ", but %v is requested", c.Constraint.Version)
   773  	}
   774  	if c.Err != nil {
   775  		fmt.Fprintf(b, ": %v", c.UnwrapModuleError())
   776  	}
   777  	return b.String()
   778  }
   779  
   780  // tidyRoots trims the root dependencies to the minimal requirements needed to
   781  // both retain the same versions of all packages in pkgs and satisfy the
   782  // graph-pruning invariants (if applicable).
   783  func tidyRoots(ctx context.Context, rs *Requirements, pkgs []*loadPkg) (*Requirements, error) {
   784  	mainModule := MainModules.mustGetSingleMainModule()
   785  	if rs.pruning == unpruned {
   786  		return tidyUnprunedRoots(ctx, mainModule, rs, pkgs)
   787  	}
   788  	return tidyPrunedRoots(ctx, mainModule, rs, pkgs)
   789  }
   790  
   791  func updateRoots(ctx context.Context, direct map[string]bool, rs *Requirements, pkgs []*loadPkg, add []module.Version, rootsImported bool) (*Requirements, error) {
   792  	switch rs.pruning {
   793  	case unpruned:
   794  		return updateUnprunedRoots(ctx, direct, rs, add)
   795  	case pruned:
   796  		return updatePrunedRoots(ctx, direct, rs, pkgs, add, rootsImported)
   797  	case workspace:
   798  		return updateWorkspaceRoots(ctx, direct, rs, add)
   799  	default:
   800  		panic(fmt.Sprintf("unsupported pruning mode: %v", rs.pruning))
   801  	}
   802  }
   803  
   804  func updateWorkspaceRoots(ctx context.Context, direct map[string]bool, rs *Requirements, add []module.Version) (*Requirements, error) {
   805  	if len(add) != 0 {
   806  		// add should be empty in workspace mode because workspace mode implies
   807  		// -mod=readonly, which in turn implies no new requirements. The code path
   808  		// that would result in add being non-empty returns an error before it
   809  		// reaches this point: The set of modules to add comes from
   810  		// resolveMissingImports, which in turn resolves each package by calling
   811  		// queryImport. But queryImport explicitly checks for -mod=readonly, and
   812  		// return an error.
   813  		panic("add is not empty")
   814  	}
   815  	return newRequirements(workspace, rs.rootModules, direct), nil
   816  }
   817  
   818  // tidyPrunedRoots returns a minimal set of root requirements that maintains the
   819  // invariants of the go.mod file needed to support graph pruning for the given
   820  // packages:
   821  //
   822  //  1. For each package marked with pkgInAll, the module path that provided that
   823  //     package is included as a root.
   824  //  2. For all packages, the module that provided that package either remains
   825  //     selected at the same version or is upgraded by the dependencies of a
   826  //     root.
   827  //
   828  // If any module that provided a package has been upgraded above its previous
   829  // version, the caller may need to reload and recompute the package graph.
   830  //
   831  // To ensure that the loading process eventually converges, the caller should
   832  // add any needed roots from the tidy root set (without removing existing untidy
   833  // roots) until the set of roots has converged.
   834  func tidyPrunedRoots(ctx context.Context, mainModule module.Version, old *Requirements, pkgs []*loadPkg) (*Requirements, error) {
   835  	var (
   836  		roots      []module.Version
   837  		pathIsRoot = map[string]bool{mainModule.Path: true}
   838  	)
   839  	if v, ok := old.rootSelected("go"); ok {
   840  		roots = append(roots, module.Version{Path: "go", Version: v})
   841  		pathIsRoot["go"] = true
   842  	}
   843  	if v, ok := old.rootSelected("toolchain"); ok {
   844  		roots = append(roots, module.Version{Path: "toolchain", Version: v})
   845  		pathIsRoot["toolchain"] = true
   846  	}
   847  	// We start by adding roots for every package in "all".
   848  	//
   849  	// Once that is done, we may still need to add more roots to cover upgraded or
   850  	// otherwise-missing test dependencies for packages in "all". For those test
   851  	// dependencies, we prefer to add roots for packages with shorter import
   852  	// stacks first, on the theory that the module requirements for those will
   853  	// tend to fill in the requirements for their transitive imports (which have
   854  	// deeper import stacks). So we add the missing dependencies for one depth at
   855  	// a time, starting with the packages actually in "all" and expanding outwards
   856  	// until we have scanned every package that was loaded.
   857  	var (
   858  		queue  []*loadPkg
   859  		queued = map[*loadPkg]bool{}
   860  	)
   861  	for _, pkg := range pkgs {
   862  		if !pkg.flags.has(pkgInAll) {
   863  			continue
   864  		}
   865  		if pkg.fromExternalModule() && !pathIsRoot[pkg.mod.Path] {
   866  			roots = append(roots, pkg.mod)
   867  			pathIsRoot[pkg.mod.Path] = true
   868  		}
   869  		queue = append(queue, pkg)
   870  		queued[pkg] = true
   871  	}
   872  	gover.ModSort(roots)
   873  	tidy := newRequirements(pruned, roots, old.direct)
   874  
   875  	for len(queue) > 0 {
   876  		roots = tidy.rootModules
   877  		mg, err := tidy.Graph(ctx)
   878  		if err != nil {
   879  			return nil, err
   880  		}
   881  
   882  		prevQueue := queue
   883  		queue = nil
   884  		for _, pkg := range prevQueue {
   885  			m := pkg.mod
   886  			if m.Path == "" {
   887  				continue
   888  			}
   889  			for _, dep := range pkg.imports {
   890  				if !queued[dep] {
   891  					queue = append(queue, dep)
   892  					queued[dep] = true
   893  				}
   894  			}
   895  			if pkg.test != nil && !queued[pkg.test] {
   896  				queue = append(queue, pkg.test)
   897  				queued[pkg.test] = true
   898  			}
   899  
   900  			if !pathIsRoot[m.Path] {
   901  				if s := mg.Selected(m.Path); gover.ModCompare(m.Path, s, m.Version) < 0 {
   902  					roots = append(roots, m)
   903  					pathIsRoot[m.Path] = true
   904  				}
   905  			}
   906  		}
   907  
   908  		if len(roots) > len(tidy.rootModules) {
   909  			gover.ModSort(roots)
   910  			tidy = newRequirements(pruned, roots, tidy.direct)
   911  		}
   912  	}
   913  
   914  	roots = tidy.rootModules
   915  	_, err := tidy.Graph(ctx)
   916  	if err != nil {
   917  		return nil, err
   918  	}
   919  
   920  	// We try to avoid adding explicit requirements for test-only dependencies of
   921  	// packages in external modules. However, if we drop the explicit
   922  	// requirements, that may change an import from unambiguous (due to lazy
   923  	// module loading) to ambiguous (because lazy module loading no longer
   924  	// disambiguates it). For any package that has become ambiguous, we try
   925  	// to fix it by promoting its module to an explicit root.
   926  	// (See https://go.dev/issue/60313.)
   927  	q := par.NewQueue(runtime.GOMAXPROCS(0))
   928  	for {
   929  		var disambiguateRoot sync.Map
   930  		for _, pkg := range pkgs {
   931  			if pkg.mod.Path == "" || pathIsRoot[pkg.mod.Path] {
   932  				// Lazy module loading will cause pkg.mod to be checked before any other modules
   933  				// that are only indirectly required. It is as unambiguous as possible.
   934  				continue
   935  			}
   936  			pkg := pkg
   937  			q.Add(func() {
   938  				skipModFile := true
   939  				_, _, _, _, err := importFromModules(ctx, pkg.path, tidy, nil, skipModFile)
   940  				if aie := (*AmbiguousImportError)(nil); errors.As(err, &aie) {
   941  					disambiguateRoot.Store(pkg.mod, true)
   942  				}
   943  			})
   944  		}
   945  		<-q.Idle()
   946  
   947  		disambiguateRoot.Range(func(k, _ any) bool {
   948  			m := k.(module.Version)
   949  			roots = append(roots, m)
   950  			pathIsRoot[m.Path] = true
   951  			return true
   952  		})
   953  
   954  		if len(roots) > len(tidy.rootModules) {
   955  			module.Sort(roots)
   956  			tidy = newRequirements(pruned, roots, tidy.direct)
   957  			_, err = tidy.Graph(ctx)
   958  			if err != nil {
   959  				return nil, err
   960  			}
   961  			// Adding these roots may have pulled additional modules into the module
   962  			// graph, causing additional packages to become ambiguous. Keep iterating
   963  			// until we reach a fixed point.
   964  			continue
   965  		}
   966  
   967  		break
   968  	}
   969  
   970  	return tidy, nil
   971  }
   972  
   973  // updatePrunedRoots returns a set of root requirements that maintains the
   974  // invariants of the go.mod file needed to support graph pruning:
   975  //
   976  //  1. The selected version of the module providing each package marked with
   977  //     either pkgInAll or pkgIsRoot is included as a root.
   978  //     Note that certain root patterns (such as '...') may explode the root set
   979  //     to contain every module that provides any package imported (or merely
   980  //     required) by any other module.
   981  //  2. Each root appears only once, at the selected version of its path
   982  //     (if rs.graph is non-nil) or at the highest version otherwise present as a
   983  //     root (otherwise).
   984  //  3. Every module path that appears as a root in rs remains a root.
   985  //  4. Every version in add is selected at its given version unless upgraded by
   986  //     (the dependencies of) an existing root or another module in add.
   987  //
   988  // The packages in pkgs are assumed to have been loaded from either the roots of
   989  // rs or the modules selected in the graph of rs.
   990  //
   991  // The above invariants together imply the graph-pruning invariants for the
   992  // go.mod file:
   993  //
   994  //  1. (The import invariant.) Every module that provides a package transitively
   995  //     imported by any package or test in the main module is included as a root.
   996  //     This follows by induction from (1) and (3) above. Transitively-imported
   997  //     packages loaded during this invocation are marked with pkgInAll (1),
   998  //     and by hypothesis any transitively-imported packages loaded in previous
   999  //     invocations were already roots in rs (3).
  1000  //
  1001  //  2. (The argument invariant.) Every module that provides a package matching
  1002  //     an explicit package pattern is included as a root. This follows directly
  1003  //     from (1): packages matching explicit package patterns are marked with
  1004  //     pkgIsRoot.
  1005  //
  1006  //  3. (The completeness invariant.) Every module that contributed any package
  1007  //     to the build is required by either the main module or one of the modules
  1008  //     it requires explicitly. This invariant is left up to the caller, who must
  1009  //     not load packages from outside the module graph but may add roots to the
  1010  //     graph, but is facilitated by (3). If the caller adds roots to the graph in
  1011  //     order to resolve missing packages, then updatePrunedRoots will retain them,
  1012  //     the selected versions of those roots cannot regress, and they will
  1013  //     eventually be written back to the main module's go.mod file.
  1014  //
  1015  // (See https://golang.org/design/36460-lazy-module-loading#invariants for more
  1016  // detail.)
  1017  func updatePrunedRoots(ctx context.Context, direct map[string]bool, rs *Requirements, pkgs []*loadPkg, add []module.Version, rootsImported bool) (*Requirements, error) {
  1018  	roots := rs.rootModules
  1019  	rootsUpgraded := false
  1020  
  1021  	spotCheckRoot := map[module.Version]bool{}
  1022  
  1023  	// “The selected version of the module providing each package marked with
  1024  	// either pkgInAll or pkgIsRoot is included as a root.”
  1025  	needSort := false
  1026  	for _, pkg := range pkgs {
  1027  		if !pkg.fromExternalModule() {
  1028  			// pkg was not loaded from a module dependency, so we don't need
  1029  			// to do anything special to maintain that dependency.
  1030  			continue
  1031  		}
  1032  
  1033  		switch {
  1034  		case pkg.flags.has(pkgInAll):
  1035  			// pkg is transitively imported by a package or test in the main module.
  1036  			// We need to promote the module that maintains it to a root: if some
  1037  			// other module depends on the main module, and that other module also
  1038  			// uses a pruned module graph, it will expect to find all of our
  1039  			// transitive dependencies by reading just our go.mod file, not the go.mod
  1040  			// files of everything we depend on.
  1041  			//
  1042  			// (This is the “import invariant” that makes graph pruning possible.)
  1043  
  1044  		case rootsImported && pkg.flags.has(pkgFromRoot):
  1045  			// pkg is a transitive dependency of some root, and we are treating the
  1046  			// roots as if they are imported by the main module (as in 'go get').
  1047  
  1048  		case pkg.flags.has(pkgIsRoot):
  1049  			// pkg is a root of the package-import graph. (Generally this means that
  1050  			// it matches a command-line argument.) We want future invocations of the
  1051  			// 'go' command — such as 'go test' on the same package — to continue to
  1052  			// use the same versions of its dependencies that we are using right now.
  1053  			// So we need to bring this package's dependencies inside the pruned
  1054  			// module graph.
  1055  			//
  1056  			// Making the module containing this package a root of the module graph
  1057  			// does exactly that: if the module containing the package supports graph
  1058  			// pruning then it should satisfy the import invariant itself, so all of
  1059  			// its dependencies should be in its go.mod file, and if the module
  1060  			// containing the package does not support pruning then if we make it a
  1061  			// root we will load all of its (unpruned) transitive dependencies into
  1062  			// the module graph.
  1063  			//
  1064  			// (This is the “argument invariant”, and is important for
  1065  			// reproducibility.)
  1066  
  1067  		default:
  1068  			// pkg is a dependency of some other package outside of the main module.
  1069  			// As far as we know it's not relevant to the main module (and thus not
  1070  			// relevant to consumers of the main module either), and its dependencies
  1071  			// should already be in the module graph — included in the dependencies of
  1072  			// the package that imported it.
  1073  			continue
  1074  		}
  1075  
  1076  		if _, ok := rs.rootSelected(pkg.mod.Path); ok {
  1077  			// It is possible that the main module's go.mod file is incomplete or
  1078  			// otherwise erroneous — for example, perhaps the author forgot to 'git
  1079  			// add' their updated go.mod file after adding a new package import, or
  1080  			// perhaps they made an edit to the go.mod file using a third-party tool
  1081  			// ('git merge'?) that doesn't maintain consistency for module
  1082  			// dependencies. If that happens, ideally we want to detect the missing
  1083  			// requirements and fix them up here.
  1084  			//
  1085  			// However, we also need to be careful not to be too aggressive. For
  1086  			// transitive dependencies of external tests, the go.mod file for the
  1087  			// module containing the test itself is expected to provide all of the
  1088  			// relevant dependencies, and we explicitly don't want to pull in
  1089  			// requirements on *irrelevant* requirements that happen to occur in the
  1090  			// go.mod files for these transitive-test-only dependencies. (See the test
  1091  			// in mod_lazy_test_horizon.txt for a concrete example).
  1092  			//
  1093  			// The “goldilocks zone” seems to be to spot-check exactly the same
  1094  			// modules that we promote to explicit roots: namely, those that provide
  1095  			// packages transitively imported by the main module, and those that
  1096  			// provide roots of the package-import graph. That will catch erroneous
  1097  			// edits to the main module's go.mod file and inconsistent requirements in
  1098  			// dependencies that provide imported packages, but will ignore erroneous
  1099  			// or misleading requirements in dependencies that aren't obviously
  1100  			// relevant to the packages in the main module.
  1101  			spotCheckRoot[pkg.mod] = true
  1102  		} else {
  1103  			roots = append(roots, pkg.mod)
  1104  			rootsUpgraded = true
  1105  			// The roots slice was initially sorted because rs.rootModules was sorted,
  1106  			// but the root we just added could be out of order.
  1107  			needSort = true
  1108  		}
  1109  	}
  1110  
  1111  	for _, m := range add {
  1112  		if v, ok := rs.rootSelected(m.Path); !ok || gover.ModCompare(m.Path, v, m.Version) < 0 {
  1113  			roots = append(roots, m)
  1114  			rootsUpgraded = true
  1115  			needSort = true
  1116  		}
  1117  	}
  1118  	if needSort {
  1119  		gover.ModSort(roots)
  1120  	}
  1121  
  1122  	// "Each root appears only once, at the selected version of its path ….”
  1123  	for {
  1124  		var mg *ModuleGraph
  1125  		if rootsUpgraded {
  1126  			// We've added or upgraded one or more roots, so load the full module
  1127  			// graph so that we can update those roots to be consistent with other
  1128  			// requirements.
  1129  			if mustHaveCompleteRequirements() {
  1130  				// Our changes to the roots may have moved dependencies into or out of
  1131  				// the graph-pruning horizon, which could in turn change the selected
  1132  				// versions of other modules. (For pruned modules adding or removing an
  1133  				// explicit root is a semantic change, not just a cosmetic one.)
  1134  				return rs, errGoModDirty
  1135  			}
  1136  
  1137  			rs = newRequirements(pruned, roots, direct)
  1138  			var err error
  1139  			mg, err = rs.Graph(ctx)
  1140  			if err != nil {
  1141  				return rs, err
  1142  			}
  1143  		} else {
  1144  			// Since none of the roots have been upgraded, we have no reason to
  1145  			// suspect that they are inconsistent with the requirements of any other
  1146  			// roots. Only look at the full module graph if we've already loaded it;
  1147  			// otherwise, just spot-check the explicit requirements of the roots from
  1148  			// which we loaded packages.
  1149  			if rs.graph.Load() != nil {
  1150  				// We've already loaded the full module graph, which includes the
  1151  				// requirements of all of the root modules — even the transitive
  1152  				// requirements, if they are unpruned!
  1153  				mg, _ = rs.Graph(ctx)
  1154  			} else if cfg.BuildMod == "vendor" {
  1155  				// We can't spot-check the requirements of other modules because we
  1156  				// don't in general have their go.mod files available in the vendor
  1157  				// directory. (Fortunately this case is impossible, because mg.graph is
  1158  				// always non-nil in vendor mode!)
  1159  				panic("internal error: rs.graph is unexpectedly nil with -mod=vendor")
  1160  			} else if !spotCheckRoots(ctx, rs, spotCheckRoot) {
  1161  				// We spot-checked the explicit requirements of the roots that are
  1162  				// relevant to the packages we've loaded. Unfortunately, they're
  1163  				// inconsistent in some way; we need to load the full module graph
  1164  				// so that we can fix the roots properly.
  1165  				var err error
  1166  				mg, err = rs.Graph(ctx)
  1167  				if err != nil {
  1168  					return rs, err
  1169  				}
  1170  			}
  1171  		}
  1172  
  1173  		roots = make([]module.Version, 0, len(rs.rootModules))
  1174  		rootsUpgraded = false
  1175  		inRootPaths := make(map[string]bool, len(rs.rootModules)+1)
  1176  		for _, mm := range MainModules.Versions() {
  1177  			inRootPaths[mm.Path] = true
  1178  		}
  1179  		for _, m := range rs.rootModules {
  1180  			if inRootPaths[m.Path] {
  1181  				// This root specifies a redundant path. We already retained the
  1182  				// selected version of this path when we saw it before, so omit the
  1183  				// redundant copy regardless of its version.
  1184  				//
  1185  				// When we read the full module graph, we include the dependencies of
  1186  				// every root even if that root is redundant. That better preserves
  1187  				// reproducibility if, say, some automated tool adds a redundant
  1188  				// 'require' line and then runs 'go mod tidy' to try to make everything
  1189  				// consistent, since the requirements of the older version are carried
  1190  				// over.
  1191  				//
  1192  				// So omitting a root that was previously present may *reduce* the
  1193  				// selected versions of non-roots, but merely removing a requirement
  1194  				// cannot *increase* the selected versions of other roots as a result —
  1195  				// we don't need to mark this change as an upgrade. (This particular
  1196  				// change cannot invalidate any other roots.)
  1197  				continue
  1198  			}
  1199  
  1200  			var v string
  1201  			if mg == nil {
  1202  				v, _ = rs.rootSelected(m.Path)
  1203  			} else {
  1204  				v = mg.Selected(m.Path)
  1205  			}
  1206  			roots = append(roots, module.Version{Path: m.Path, Version: v})
  1207  			inRootPaths[m.Path] = true
  1208  			if v != m.Version {
  1209  				rootsUpgraded = true
  1210  			}
  1211  		}
  1212  		// Note that rs.rootModules was already sorted by module path and version,
  1213  		// and we appended to the roots slice in the same order and guaranteed that
  1214  		// each path has only one version, so roots is also sorted by module path
  1215  		// and (trivially) version.
  1216  
  1217  		if !rootsUpgraded {
  1218  			if cfg.BuildMod != "mod" {
  1219  				// The only changes to the root set (if any) were to remove duplicates.
  1220  				// The requirements are consistent (if perhaps redundant), so keep the
  1221  				// original rs to preserve its ModuleGraph.
  1222  				return rs, nil
  1223  			}
  1224  			// The root set has converged: every root going into this iteration was
  1225  			// already at its selected version, although we have have removed other
  1226  			// (redundant) roots for the same path.
  1227  			break
  1228  		}
  1229  	}
  1230  
  1231  	if rs.pruning == pruned && slices.Equal(roots, rs.rootModules) && maps.Equal(direct, rs.direct) {
  1232  		// The root set is unchanged and rs was already pruned, so keep rs to
  1233  		// preserve its cached ModuleGraph (if any).
  1234  		return rs, nil
  1235  	}
  1236  	return newRequirements(pruned, roots, direct), nil
  1237  }
  1238  
  1239  // spotCheckRoots reports whether the versions of the roots in rs satisfy the
  1240  // explicit requirements of the modules in mods.
  1241  func spotCheckRoots(ctx context.Context, rs *Requirements, mods map[module.Version]bool) bool {
  1242  	ctx, cancel := context.WithCancel(ctx)
  1243  	defer cancel()
  1244  
  1245  	work := par.NewQueue(runtime.GOMAXPROCS(0))
  1246  	for m := range mods {
  1247  		m := m
  1248  		work.Add(func() {
  1249  			if ctx.Err() != nil {
  1250  				return
  1251  			}
  1252  
  1253  			summary, err := goModSummary(m)
  1254  			if err != nil {
  1255  				cancel()
  1256  				return
  1257  			}
  1258  
  1259  			for _, r := range summary.require {
  1260  				if v, ok := rs.rootSelected(r.Path); ok && gover.ModCompare(r.Path, v, r.Version) < 0 {
  1261  					cancel()
  1262  					return
  1263  				}
  1264  			}
  1265  		})
  1266  	}
  1267  	<-work.Idle()
  1268  
  1269  	if ctx.Err() != nil {
  1270  		// Either we failed a spot-check, or the caller no longer cares about our
  1271  		// answer anyway.
  1272  		return false
  1273  	}
  1274  
  1275  	return true
  1276  }
  1277  
  1278  // tidyUnprunedRoots returns a minimal set of root requirements that maintains
  1279  // the selected version of every module that provided or lexically could have
  1280  // provided a package in pkgs, and includes the selected version of every such
  1281  // module in direct as a root.
  1282  func tidyUnprunedRoots(ctx context.Context, mainModule module.Version, old *Requirements, pkgs []*loadPkg) (*Requirements, error) {
  1283  	var (
  1284  		// keep is a set of of modules that provide packages or are needed to
  1285  		// disambiguate imports.
  1286  		keep     []module.Version
  1287  		keptPath = map[string]bool{}
  1288  
  1289  		// rootPaths is a list of module paths that provide packages directly
  1290  		// imported from the main module. They should be included as roots.
  1291  		rootPaths   []string
  1292  		inRootPaths = map[string]bool{}
  1293  
  1294  		// altMods is a set of paths of modules that lexically could have provided
  1295  		// imported packages. It may be okay to remove these from the list of
  1296  		// explicit requirements if that removes them from the module graph. If they
  1297  		// are present in the module graph reachable from rootPaths, they must not
  1298  		// be at a lower version. That could cause a missing sum error or a new
  1299  		// import ambiguity.
  1300  		//
  1301  		// For example, suppose a developer rewrites imports from example.com/m to
  1302  		// example.com/m/v2, then runs 'go mod tidy'. Tidy may delete the
  1303  		// requirement on example.com/m if there is no other transitive requirement
  1304  		// on it. However, if example.com/m were downgraded to a version not in
  1305  		// go.sum, when package example.com/m/v2/p is loaded, we'd get an error
  1306  		// trying to disambiguate the import, since we can't check example.com/m
  1307  		// without its sum. See #47738.
  1308  		altMods = map[string]string{}
  1309  	)
  1310  	if v, ok := old.rootSelected("go"); ok {
  1311  		keep = append(keep, module.Version{Path: "go", Version: v})
  1312  		keptPath["go"] = true
  1313  	}
  1314  	if v, ok := old.rootSelected("toolchain"); ok {
  1315  		keep = append(keep, module.Version{Path: "toolchain", Version: v})
  1316  		keptPath["toolchain"] = true
  1317  	}
  1318  	for _, pkg := range pkgs {
  1319  		if !pkg.fromExternalModule() {
  1320  			continue
  1321  		}
  1322  		if m := pkg.mod; !keptPath[m.Path] {
  1323  			keep = append(keep, m)
  1324  			keptPath[m.Path] = true
  1325  			if old.direct[m.Path] && !inRootPaths[m.Path] {
  1326  				rootPaths = append(rootPaths, m.Path)
  1327  				inRootPaths[m.Path] = true
  1328  			}
  1329  		}
  1330  		for _, m := range pkg.altMods {
  1331  			altMods[m.Path] = m.Version
  1332  		}
  1333  	}
  1334  
  1335  	// Construct a build list with a minimal set of roots.
  1336  	// This may remove or downgrade modules in altMods.
  1337  	reqs := &mvsReqs{roots: keep}
  1338  	min, err := mvs.Req(mainModule, rootPaths, reqs)
  1339  	if err != nil {
  1340  		return nil, err
  1341  	}
  1342  	buildList, err := mvs.BuildList([]module.Version{mainModule}, reqs)
  1343  	if err != nil {
  1344  		return nil, err
  1345  	}
  1346  
  1347  	// Check if modules in altMods were downgraded but not removed.
  1348  	// If so, add them to roots, which will retain an "// indirect" requirement
  1349  	// in go.mod. See comment on altMods above.
  1350  	keptAltMod := false
  1351  	for _, m := range buildList {
  1352  		if v, ok := altMods[m.Path]; ok && gover.ModCompare(m.Path, m.Version, v) < 0 {
  1353  			keep = append(keep, module.Version{Path: m.Path, Version: v})
  1354  			keptAltMod = true
  1355  		}
  1356  	}
  1357  	if keptAltMod {
  1358  		// We must run mvs.Req again instead of simply adding altMods to min.
  1359  		// It's possible that a requirement in altMods makes some other
  1360  		// explicit indirect requirement unnecessary.
  1361  		reqs.roots = keep
  1362  		min, err = mvs.Req(mainModule, rootPaths, reqs)
  1363  		if err != nil {
  1364  			return nil, err
  1365  		}
  1366  	}
  1367  
  1368  	return newRequirements(unpruned, min, old.direct), nil
  1369  }
  1370  
  1371  // updateUnprunedRoots returns a set of root requirements that includes the selected
  1372  // version of every module path in direct as a root, and maintains the selected
  1373  // version of every module selected in the graph of rs.
  1374  //
  1375  // The roots are updated such that:
  1376  //
  1377  //  1. The selected version of every module path in direct is included as a root
  1378  //     (if it is not "none").
  1379  //  2. Each root is the selected version of its path. (We say that such a root
  1380  //     set is “consistent”.)
  1381  //  3. Every version selected in the graph of rs remains selected unless upgraded
  1382  //     by a dependency in add.
  1383  //  4. Every version in add is selected at its given version unless upgraded by
  1384  //     (the dependencies of) an existing root or another module in add.
  1385  func updateUnprunedRoots(ctx context.Context, direct map[string]bool, rs *Requirements, add []module.Version) (*Requirements, error) {
  1386  	mg, err := rs.Graph(ctx)
  1387  	if err != nil {
  1388  		// We can't ignore errors in the module graph even if the user passed the -e
  1389  		// flag to try to push past them. If we can't load the complete module
  1390  		// dependencies, then we can't reliably compute a minimal subset of them.
  1391  		return rs, err
  1392  	}
  1393  
  1394  	if mustHaveCompleteRequirements() {
  1395  		// Instead of actually updating the requirements, just check that no updates
  1396  		// are needed.
  1397  		if rs == nil {
  1398  			// We're being asked to reconstruct the requirements from scratch,
  1399  			// but we aren't even allowed to modify them.
  1400  			return rs, errGoModDirty
  1401  		}
  1402  		for _, m := range rs.rootModules {
  1403  			if m.Version != mg.Selected(m.Path) {
  1404  				// The root version v is misleading: the actual selected version is higher.
  1405  				return rs, errGoModDirty
  1406  			}
  1407  		}
  1408  		for _, m := range add {
  1409  			if m.Version != mg.Selected(m.Path) {
  1410  				return rs, errGoModDirty
  1411  			}
  1412  		}
  1413  		for mPath := range direct {
  1414  			if _, ok := rs.rootSelected(mPath); !ok {
  1415  				// Module m is supposed to be listed explicitly, but isn't.
  1416  				//
  1417  				// Note that this condition is also detected (and logged with more
  1418  				// detail) earlier during package loading, so it shouldn't actually be
  1419  				// possible at this point — this is just a defense in depth.
  1420  				return rs, errGoModDirty
  1421  			}
  1422  		}
  1423  
  1424  		// No explicit roots are missing and all roots are already at the versions
  1425  		// we want to keep. Any other changes we would make are purely cosmetic,
  1426  		// such as pruning redundant indirect dependencies. Per issue #34822, we
  1427  		// ignore cosmetic changes when we cannot update the go.mod file.
  1428  		return rs, nil
  1429  	}
  1430  
  1431  	var (
  1432  		rootPaths   []string // module paths that should be included as roots
  1433  		inRootPaths = map[string]bool{}
  1434  	)
  1435  	for _, root := range rs.rootModules {
  1436  		// If the selected version of the root is the same as what was already
  1437  		// listed in the go.mod file, retain it as a root (even if redundant) to
  1438  		// avoid unnecessary churn. (See https://golang.org/issue/34822.)
  1439  		//
  1440  		// We do this even for indirect requirements, since we don't know why they
  1441  		// were added and they could become direct at any time.
  1442  		if !inRootPaths[root.Path] && mg.Selected(root.Path) == root.Version {
  1443  			rootPaths = append(rootPaths, root.Path)
  1444  			inRootPaths[root.Path] = true
  1445  		}
  1446  	}
  1447  
  1448  	// “The selected version of every module path in direct is included as a root.”
  1449  	//
  1450  	// This is only for convenience and clarity for end users: in an unpruned module,
  1451  	// the choice of explicit vs. implicit dependency has no impact on MVS
  1452  	// selection (for itself or any other module).
  1453  	keep := append(mg.BuildList()[MainModules.Len():], add...)
  1454  	for _, m := range keep {
  1455  		if direct[m.Path] && !inRootPaths[m.Path] {
  1456  			rootPaths = append(rootPaths, m.Path)
  1457  			inRootPaths[m.Path] = true
  1458  		}
  1459  	}
  1460  
  1461  	var roots []module.Version
  1462  	for _, mainModule := range MainModules.Versions() {
  1463  		min, err := mvs.Req(mainModule, rootPaths, &mvsReqs{roots: keep})
  1464  		if err != nil {
  1465  			return rs, err
  1466  		}
  1467  		roots = append(roots, min...)
  1468  	}
  1469  	if MainModules.Len() > 1 {
  1470  		gover.ModSort(roots)
  1471  	}
  1472  	if rs.pruning == unpruned && slices.Equal(roots, rs.rootModules) && maps.Equal(direct, rs.direct) {
  1473  		// The root set is unchanged and rs was already unpruned, so keep rs to
  1474  		// preserve its cached ModuleGraph (if any).
  1475  		return rs, nil
  1476  	}
  1477  
  1478  	return newRequirements(unpruned, roots, direct), nil
  1479  }
  1480  
  1481  // convertPruning returns a version of rs with the given pruning behavior.
  1482  // If rs already has the given pruning, convertPruning returns rs unmodified.
  1483  func convertPruning(ctx context.Context, rs *Requirements, pruning modPruning) (*Requirements, error) {
  1484  	if rs.pruning == pruning {
  1485  		return rs, nil
  1486  	} else if rs.pruning == workspace || pruning == workspace {
  1487  		panic("attempting to convert to/from workspace pruning and another pruning type")
  1488  	}
  1489  
  1490  	if pruning == unpruned {
  1491  		// We are converting a pruned module to an unpruned one. The roots of a
  1492  		// pruned module graph are a superset of the roots of an unpruned one, so
  1493  		// we don't need to add any new roots — we just need to drop the ones that
  1494  		// are redundant, which is exactly what updateUnprunedRoots does.
  1495  		return updateUnprunedRoots(ctx, rs.direct, rs, nil)
  1496  	}
  1497  
  1498  	// We are converting an unpruned module to a pruned one.
  1499  	//
  1500  	// An unpruned module graph includes the transitive dependencies of every
  1501  	// module in the build list. As it turns out, we can express that as a pruned
  1502  	// root set! “Include the transitive dependencies of every module in the build
  1503  	// list” is exactly what happens in a pruned module if we promote every module
  1504  	// in the build list to a root.
  1505  	mg, err := rs.Graph(ctx)
  1506  	if err != nil {
  1507  		return rs, err
  1508  	}
  1509  	return newRequirements(pruned, mg.BuildList()[MainModules.Len():], rs.direct), nil
  1510  }
  1511  

View as plain text