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/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, nil
   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, nil
   659  }
   660  
   661  func overrideRoots(ctx context.Context, rs *Requirements, replace []module.Version) *Requirements {
   662  	drop := make(map[string]bool)
   663  	for _, m := range replace {
   664  		drop[m.Path] = true
   665  	}
   666  	var roots []module.Version
   667  	for _, m := range rs.rootModules {
   668  		if !drop[m.Path] {
   669  			roots = append(roots, m)
   670  		}
   671  	}
   672  	roots = append(roots, replace...)
   673  	gover.ModSort(roots)
   674  	return newRequirements(rs.pruning, roots, rs.direct)
   675  }
   676  
   677  // A ConstraintError describes inconsistent constraints in EditBuildList
   678  type ConstraintError struct {
   679  	// Conflict lists the source of the conflict for each version in mustSelect
   680  	// that could not be selected due to the requirements of some other version in
   681  	// mustSelect.
   682  	Conflicts []Conflict
   683  }
   684  
   685  func (e *ConstraintError) Error() string {
   686  	b := new(strings.Builder)
   687  	b.WriteString("version constraints conflict:")
   688  	for _, c := range e.Conflicts {
   689  		fmt.Fprintf(b, "\n\t%s", c.Summary())
   690  	}
   691  	return b.String()
   692  }
   693  
   694  // A Conflict is a path of requirements starting at a root or proposed root in
   695  // the requirement graph, explaining why that root either causes a module passed
   696  // in the mustSelect list to EditBuildList to be unattainable, or introduces an
   697  // unresolvable error in loading the requirement graph.
   698  type Conflict struct {
   699  	// Path is a path of requirements starting at some module version passed in
   700  	// the mustSelect argument and ending at a module whose requirements make that
   701  	// version unacceptable. (Path always has len ≥ 1.)
   702  	Path []module.Version
   703  
   704  	// If Err is nil, Constraint is a module version passed in the mustSelect
   705  	// argument that has the same module path as, and a lower version than,
   706  	// the last element of the Path slice.
   707  	Constraint module.Version
   708  
   709  	// If Constraint is unset, Err is an error encountered when loading the
   710  	// requirements of the last element in Path.
   711  	Err error
   712  }
   713  
   714  // UnwrapModuleError returns c.Err, but unwraps it if it is a module.ModuleError
   715  // with a version and path matching the last entry in the Path slice.
   716  func (c Conflict) UnwrapModuleError() error {
   717  	me, ok := c.Err.(*module.ModuleError)
   718  	if ok && len(c.Path) > 0 {
   719  		last := c.Path[len(c.Path)-1]
   720  		if me.Path == last.Path && me.Version == last.Version {
   721  			return me.Err
   722  		}
   723  	}
   724  	return c.Err
   725  }
   726  
   727  // Summary returns a string that describes only the first and last modules in
   728  // the conflict path.
   729  func (c Conflict) Summary() string {
   730  	if len(c.Path) == 0 {
   731  		return "(internal error: invalid Conflict struct)"
   732  	}
   733  	first := c.Path[0]
   734  	last := c.Path[len(c.Path)-1]
   735  	if len(c.Path) == 1 {
   736  		if c.Err != nil {
   737  			return fmt.Sprintf("%s: %v", first, c.UnwrapModuleError())
   738  		}
   739  		return fmt.Sprintf("%s is above %s", first, c.Constraint.Version)
   740  	}
   741  
   742  	adverb := ""
   743  	if len(c.Path) > 2 {
   744  		adverb = "indirectly "
   745  	}
   746  	if c.Err != nil {
   747  		return fmt.Sprintf("%s %srequires %s: %v", first, adverb, last, c.UnwrapModuleError())
   748  	}
   749  	return fmt.Sprintf("%s %srequires %s, but %s is requested", first, adverb, last, c.Constraint.Version)
   750  }
   751  
   752  // String returns a string that describes the full conflict path.
   753  func (c Conflict) String() string {
   754  	if len(c.Path) == 0 {
   755  		return "(internal error: invalid Conflict struct)"
   756  	}
   757  	b := new(strings.Builder)
   758  	fmt.Fprintf(b, "%v", c.Path[0])
   759  	if len(c.Path) == 1 {
   760  		fmt.Fprintf(b, " found")
   761  	} else {
   762  		for _, r := range c.Path[1:] {
   763  			fmt.Fprintf(b, " requires\n\t%v", r)
   764  		}
   765  	}
   766  	if c.Constraint != (module.Version{}) {
   767  		fmt.Fprintf(b, ", but %v is requested", c.Constraint.Version)
   768  	}
   769  	if c.Err != nil {
   770  		fmt.Fprintf(b, ": %v", c.UnwrapModuleError())
   771  	}
   772  	return b.String()
   773  }
   774  
   775  // tidyRoots trims the root dependencies to the minimal requirements needed to
   776  // both retain the same versions of all packages in pkgs and satisfy the
   777  // graph-pruning invariants (if applicable).
   778  func tidyRoots(ctx context.Context, rs *Requirements, pkgs []*loadPkg) (*Requirements, error) {
   779  	mainModule := MainModules.mustGetSingleMainModule()
   780  	if rs.pruning == unpruned {
   781  		return tidyUnprunedRoots(ctx, mainModule, rs, pkgs)
   782  	}
   783  	return tidyPrunedRoots(ctx, mainModule, rs, pkgs)
   784  }
   785  
   786  func updateRoots(ctx context.Context, direct map[string]bool, rs *Requirements, pkgs []*loadPkg, add []module.Version, rootsImported bool) (*Requirements, error) {
   787  	switch rs.pruning {
   788  	case unpruned:
   789  		return updateUnprunedRoots(ctx, direct, rs, add)
   790  	case pruned:
   791  		return updatePrunedRoots(ctx, direct, rs, pkgs, add, rootsImported)
   792  	case workspace:
   793  		return updateWorkspaceRoots(ctx, direct, rs, add)
   794  	default:
   795  		panic(fmt.Sprintf("unsupported pruning mode: %v", rs.pruning))
   796  	}
   797  }
   798  
   799  func updateWorkspaceRoots(ctx context.Context, direct map[string]bool, rs *Requirements, add []module.Version) (*Requirements, error) {
   800  	if len(add) != 0 {
   801  		// add should be empty in workspace mode because workspace mode implies
   802  		// -mod=readonly, which in turn implies no new requirements. The code path
   803  		// that would result in add being non-empty returns an error before it
   804  		// reaches this point: The set of modules to add comes from
   805  		// resolveMissingImports, which in turn resolves each package by calling
   806  		// queryImport. But queryImport explicitly checks for -mod=readonly, and
   807  		// return an error.
   808  		panic("add is not empty")
   809  	}
   810  	return newRequirements(workspace, rs.rootModules, direct), nil
   811  }
   812  
   813  // tidyPrunedRoots returns a minimal set of root requirements that maintains the
   814  // invariants of the go.mod file needed to support graph pruning for the given
   815  // packages:
   816  //
   817  //  1. For each package marked with pkgInAll, the module path that provided that
   818  //     package is included as a root.
   819  //  2. For all packages, the module that provided that package either remains
   820  //     selected at the same version or is upgraded by the dependencies of a
   821  //     root.
   822  //
   823  // If any module that provided a package has been upgraded above its previous
   824  // version, the caller may need to reload and recompute the package graph.
   825  //
   826  // To ensure that the loading process eventually converges, the caller should
   827  // add any needed roots from the tidy root set (without removing existing untidy
   828  // roots) until the set of roots has converged.
   829  func tidyPrunedRoots(ctx context.Context, mainModule module.Version, old *Requirements, pkgs []*loadPkg) (*Requirements, error) {
   830  	var (
   831  		roots      []module.Version
   832  		pathIsRoot = map[string]bool{mainModule.Path: true}
   833  	)
   834  	if v, ok := old.rootSelected("go"); ok {
   835  		roots = append(roots, module.Version{Path: "go", Version: v})
   836  		pathIsRoot["go"] = true
   837  	}
   838  	if v, ok := old.rootSelected("toolchain"); ok {
   839  		roots = append(roots, module.Version{Path: "toolchain", Version: v})
   840  		pathIsRoot["toolchain"] = true
   841  	}
   842  	// We start by adding roots for every package in "all".
   843  	//
   844  	// Once that is done, we may still need to add more roots to cover upgraded or
   845  	// otherwise-missing test dependencies for packages in "all". For those test
   846  	// dependencies, we prefer to add roots for packages with shorter import
   847  	// stacks first, on the theory that the module requirements for those will
   848  	// tend to fill in the requirements for their transitive imports (which have
   849  	// deeper import stacks). So we add the missing dependencies for one depth at
   850  	// a time, starting with the packages actually in "all" and expanding outwards
   851  	// until we have scanned every package that was loaded.
   852  	var (
   853  		queue  []*loadPkg
   854  		queued = map[*loadPkg]bool{}
   855  	)
   856  	for _, pkg := range pkgs {
   857  		if !pkg.flags.has(pkgInAll) {
   858  			continue
   859  		}
   860  		if pkg.fromExternalModule() && !pathIsRoot[pkg.mod.Path] {
   861  			roots = append(roots, pkg.mod)
   862  			pathIsRoot[pkg.mod.Path] = true
   863  		}
   864  		queue = append(queue, pkg)
   865  		queued[pkg] = true
   866  	}
   867  	gover.ModSort(roots)
   868  	tidy := newRequirements(pruned, roots, old.direct)
   869  
   870  	for len(queue) > 0 {
   871  		roots = tidy.rootModules
   872  		mg, err := tidy.Graph(ctx)
   873  		if err != nil {
   874  			return nil, err
   875  		}
   876  
   877  		prevQueue := queue
   878  		queue = nil
   879  		for _, pkg := range prevQueue {
   880  			m := pkg.mod
   881  			if m.Path == "" {
   882  				continue
   883  			}
   884  			for _, dep := range pkg.imports {
   885  				if !queued[dep] {
   886  					queue = append(queue, dep)
   887  					queued[dep] = true
   888  				}
   889  			}
   890  			if pkg.test != nil && !queued[pkg.test] {
   891  				queue = append(queue, pkg.test)
   892  				queued[pkg.test] = true
   893  			}
   894  
   895  			if !pathIsRoot[m.Path] {
   896  				if s := mg.Selected(m.Path); gover.ModCompare(m.Path, s, m.Version) < 0 {
   897  					roots = append(roots, m)
   898  					pathIsRoot[m.Path] = true
   899  				}
   900  			}
   901  		}
   902  
   903  		if len(roots) > len(tidy.rootModules) {
   904  			gover.ModSort(roots)
   905  			tidy = newRequirements(pruned, roots, tidy.direct)
   906  		}
   907  	}
   908  
   909  	roots = tidy.rootModules
   910  	_, err := tidy.Graph(ctx)
   911  	if err != nil {
   912  		return nil, err
   913  	}
   914  
   915  	// We try to avoid adding explicit requirements for test-only dependencies of
   916  	// packages in external modules. However, if we drop the explicit
   917  	// requirements, that may change an import from unambiguous (due to lazy
   918  	// module loading) to ambiguous (because lazy module loading no longer
   919  	// disambiguates it). For any package that has become ambiguous, we try
   920  	// to fix it by promoting its module to an explicit root.
   921  	// (See https://go.dev/issue/60313.)
   922  	q := par.NewQueue(runtime.GOMAXPROCS(0))
   923  	for {
   924  		var disambiguateRoot sync.Map
   925  		for _, pkg := range pkgs {
   926  			if pkg.mod.Path == "" || pathIsRoot[pkg.mod.Path] {
   927  				// Lazy module loading will cause pkg.mod to be checked before any other modules
   928  				// that are only indirectly required. It is as unambiguous as possible.
   929  				continue
   930  			}
   931  			pkg := pkg
   932  			q.Add(func() {
   933  				skipModFile := true
   934  				_, _, _, _, err := importFromModules(ctx, pkg.path, tidy, nil, skipModFile)
   935  				if aie := (*AmbiguousImportError)(nil); errors.As(err, &aie) {
   936  					disambiguateRoot.Store(pkg.mod, true)
   937  				}
   938  			})
   939  		}
   940  		<-q.Idle()
   941  
   942  		disambiguateRoot.Range(func(k, _ any) bool {
   943  			m := k.(module.Version)
   944  			roots = append(roots, m)
   945  			pathIsRoot[m.Path] = true
   946  			return true
   947  		})
   948  
   949  		if len(roots) > len(tidy.rootModules) {
   950  			module.Sort(roots)
   951  			tidy = newRequirements(pruned, roots, tidy.direct)
   952  			_, err = tidy.Graph(ctx)
   953  			if err != nil {
   954  				return nil, err
   955  			}
   956  			// Adding these roots may have pulled additional modules into the module
   957  			// graph, causing additional packages to become ambiguous. Keep iterating
   958  			// until we reach a fixed point.
   959  			continue
   960  		}
   961  
   962  		break
   963  	}
   964  
   965  	return tidy, nil
   966  }
   967  
   968  // updatePrunedRoots returns a set of root requirements that maintains the
   969  // invariants of the go.mod file needed to support graph pruning:
   970  //
   971  //  1. The selected version of the module providing each package marked with
   972  //     either pkgInAll or pkgIsRoot is included as a root.
   973  //     Note that certain root patterns (such as '...') may explode the root set
   974  //     to contain every module that provides any package imported (or merely
   975  //     required) by any other module.
   976  //  2. Each root appears only once, at the selected version of its path
   977  //     (if rs.graph is non-nil) or at the highest version otherwise present as a
   978  //     root (otherwise).
   979  //  3. Every module path that appears as a root in rs remains a root.
   980  //  4. Every version in add is selected at its given version unless upgraded by
   981  //     (the dependencies of) an existing root or another module in add.
   982  //
   983  // The packages in pkgs are assumed to have been loaded from either the roots of
   984  // rs or the modules selected in the graph of rs.
   985  //
   986  // The above invariants together imply the graph-pruning invariants for the
   987  // go.mod file:
   988  //
   989  //  1. (The import invariant.) Every module that provides a package transitively
   990  //     imported by any package or test in the main module is included as a root.
   991  //     This follows by induction from (1) and (3) above. Transitively-imported
   992  //     packages loaded during this invocation are marked with pkgInAll (1),
   993  //     and by hypothesis any transitively-imported packages loaded in previous
   994  //     invocations were already roots in rs (3).
   995  //
   996  //  2. (The argument invariant.) Every module that provides a package matching
   997  //     an explicit package pattern is included as a root. This follows directly
   998  //     from (1): packages matching explicit package patterns are marked with
   999  //     pkgIsRoot.
  1000  //
  1001  //  3. (The completeness invariant.) Every module that contributed any package
  1002  //     to the build is required by either the main module or one of the modules
  1003  //     it requires explicitly. This invariant is left up to the caller, who must
  1004  //     not load packages from outside the module graph but may add roots to the
  1005  //     graph, but is facilitated by (3). If the caller adds roots to the graph in
  1006  //     order to resolve missing packages, then updatePrunedRoots will retain them,
  1007  //     the selected versions of those roots cannot regress, and they will
  1008  //     eventually be written back to the main module's go.mod file.
  1009  //
  1010  // (See https://golang.org/design/36460-lazy-module-loading#invariants for more
  1011  // detail.)
  1012  func updatePrunedRoots(ctx context.Context, direct map[string]bool, rs *Requirements, pkgs []*loadPkg, add []module.Version, rootsImported bool) (*Requirements, error) {
  1013  	roots := rs.rootModules
  1014  	rootsUpgraded := false
  1015  
  1016  	spotCheckRoot := map[module.Version]bool{}
  1017  
  1018  	// “The selected version of the module providing each package marked with
  1019  	// either pkgInAll or pkgIsRoot is included as a root.”
  1020  	needSort := false
  1021  	for _, pkg := range pkgs {
  1022  		if !pkg.fromExternalModule() {
  1023  			// pkg was not loaded from a module dependency, so we don't need
  1024  			// to do anything special to maintain that dependency.
  1025  			continue
  1026  		}
  1027  
  1028  		switch {
  1029  		case pkg.flags.has(pkgInAll):
  1030  			// pkg is transitively imported by a package or test in the main module.
  1031  			// We need to promote the module that maintains it to a root: if some
  1032  			// other module depends on the main module, and that other module also
  1033  			// uses a pruned module graph, it will expect to find all of our
  1034  			// transitive dependencies by reading just our go.mod file, not the go.mod
  1035  			// files of everything we depend on.
  1036  			//
  1037  			// (This is the “import invariant” that makes graph pruning possible.)
  1038  
  1039  		case rootsImported && pkg.flags.has(pkgFromRoot):
  1040  			// pkg is a transitive dependency of some root, and we are treating the
  1041  			// roots as if they are imported by the main module (as in 'go get').
  1042  
  1043  		case pkg.flags.has(pkgIsRoot):
  1044  			// pkg is a root of the package-import graph. (Generally this means that
  1045  			// it matches a command-line argument.) We want future invocations of the
  1046  			// 'go' command — such as 'go test' on the same package — to continue to
  1047  			// use the same versions of its dependencies that we are using right now.
  1048  			// So we need to bring this package's dependencies inside the pruned
  1049  			// module graph.
  1050  			//
  1051  			// Making the module containing this package a root of the module graph
  1052  			// does exactly that: if the module containing the package supports graph
  1053  			// pruning then it should satisfy the import invariant itself, so all of
  1054  			// its dependencies should be in its go.mod file, and if the module
  1055  			// containing the package does not support pruning then if we make it a
  1056  			// root we will load all of its (unpruned) transitive dependencies into
  1057  			// the module graph.
  1058  			//
  1059  			// (This is the “argument invariant”, and is important for
  1060  			// reproducibility.)
  1061  
  1062  		default:
  1063  			// pkg is a dependency of some other package outside of the main module.
  1064  			// As far as we know it's not relevant to the main module (and thus not
  1065  			// relevant to consumers of the main module either), and its dependencies
  1066  			// should already be in the module graph — included in the dependencies of
  1067  			// the package that imported it.
  1068  			continue
  1069  		}
  1070  
  1071  		if _, ok := rs.rootSelected(pkg.mod.Path); ok {
  1072  			// It is possible that the main module's go.mod file is incomplete or
  1073  			// otherwise erroneous — for example, perhaps the author forgot to 'git
  1074  			// add' their updated go.mod file after adding a new package import, or
  1075  			// perhaps they made an edit to the go.mod file using a third-party tool
  1076  			// ('git merge'?) that doesn't maintain consistency for module
  1077  			// dependencies. If that happens, ideally we want to detect the missing
  1078  			// requirements and fix them up here.
  1079  			//
  1080  			// However, we also need to be careful not to be too aggressive. For
  1081  			// transitive dependencies of external tests, the go.mod file for the
  1082  			// module containing the test itself is expected to provide all of the
  1083  			// relevant dependencies, and we explicitly don't want to pull in
  1084  			// requirements on *irrelevant* requirements that happen to occur in the
  1085  			// go.mod files for these transitive-test-only dependencies. (See the test
  1086  			// in mod_lazy_test_horizon.txt for a concrete example).
  1087  			//
  1088  			// The “goldilocks zone” seems to be to spot-check exactly the same
  1089  			// modules that we promote to explicit roots: namely, those that provide
  1090  			// packages transitively imported by the main module, and those that
  1091  			// provide roots of the package-import graph. That will catch erroneous
  1092  			// edits to the main module's go.mod file and inconsistent requirements in
  1093  			// dependencies that provide imported packages, but will ignore erroneous
  1094  			// or misleading requirements in dependencies that aren't obviously
  1095  			// relevant to the packages in the main module.
  1096  			spotCheckRoot[pkg.mod] = true
  1097  		} else {
  1098  			roots = append(roots, pkg.mod)
  1099  			rootsUpgraded = true
  1100  			// The roots slice was initially sorted because rs.rootModules was sorted,
  1101  			// but the root we just added could be out of order.
  1102  			needSort = true
  1103  		}
  1104  	}
  1105  
  1106  	for _, m := range add {
  1107  		if v, ok := rs.rootSelected(m.Path); !ok || gover.ModCompare(m.Path, v, m.Version) < 0 {
  1108  			roots = append(roots, m)
  1109  			rootsUpgraded = true
  1110  			needSort = true
  1111  		}
  1112  	}
  1113  	if needSort {
  1114  		gover.ModSort(roots)
  1115  	}
  1116  
  1117  	// "Each root appears only once, at the selected version of its path ….”
  1118  	for {
  1119  		var mg *ModuleGraph
  1120  		if rootsUpgraded {
  1121  			// We've added or upgraded one or more roots, so load the full module
  1122  			// graph so that we can update those roots to be consistent with other
  1123  			// requirements.
  1124  			if mustHaveCompleteRequirements() {
  1125  				// Our changes to the roots may have moved dependencies into or out of
  1126  				// the graph-pruning horizon, which could in turn change the selected
  1127  				// versions of other modules. (For pruned modules adding or removing an
  1128  				// explicit root is a semantic change, not just a cosmetic one.)
  1129  				return rs, errGoModDirty
  1130  			}
  1131  
  1132  			rs = newRequirements(pruned, roots, direct)
  1133  			var err error
  1134  			mg, err = rs.Graph(ctx)
  1135  			if err != nil {
  1136  				return rs, err
  1137  			}
  1138  		} else {
  1139  			// Since none of the roots have been upgraded, we have no reason to
  1140  			// suspect that they are inconsistent with the requirements of any other
  1141  			// roots. Only look at the full module graph if we've already loaded it;
  1142  			// otherwise, just spot-check the explicit requirements of the roots from
  1143  			// which we loaded packages.
  1144  			if rs.graph.Load() != nil {
  1145  				// We've already loaded the full module graph, which includes the
  1146  				// requirements of all of the root modules — even the transitive
  1147  				// requirements, if they are unpruned!
  1148  				mg, _ = rs.Graph(ctx)
  1149  			} else if cfg.BuildMod == "vendor" {
  1150  				// We can't spot-check the requirements of other modules because we
  1151  				// don't in general have their go.mod files available in the vendor
  1152  				// directory. (Fortunately this case is impossible, because mg.graph is
  1153  				// always non-nil in vendor mode!)
  1154  				panic("internal error: rs.graph is unexpectedly nil with -mod=vendor")
  1155  			} else if !spotCheckRoots(ctx, rs, spotCheckRoot) {
  1156  				// We spot-checked the explicit requirements of the roots that are
  1157  				// relevant to the packages we've loaded. Unfortunately, they're
  1158  				// inconsistent in some way; we need to load the full module graph
  1159  				// so that we can fix the roots properly.
  1160  				var err error
  1161  				mg, err = rs.Graph(ctx)
  1162  				if err != nil {
  1163  					return rs, err
  1164  				}
  1165  			}
  1166  		}
  1167  
  1168  		roots = make([]module.Version, 0, len(rs.rootModules))
  1169  		rootsUpgraded = false
  1170  		inRootPaths := make(map[string]bool, len(rs.rootModules)+1)
  1171  		for _, mm := range MainModules.Versions() {
  1172  			inRootPaths[mm.Path] = true
  1173  		}
  1174  		for _, m := range rs.rootModules {
  1175  			if inRootPaths[m.Path] {
  1176  				// This root specifies a redundant path. We already retained the
  1177  				// selected version of this path when we saw it before, so omit the
  1178  				// redundant copy regardless of its version.
  1179  				//
  1180  				// When we read the full module graph, we include the dependencies of
  1181  				// every root even if that root is redundant. That better preserves
  1182  				// reproducibility if, say, some automated tool adds a redundant
  1183  				// 'require' line and then runs 'go mod tidy' to try to make everything
  1184  				// consistent, since the requirements of the older version are carried
  1185  				// over.
  1186  				//
  1187  				// So omitting a root that was previously present may *reduce* the
  1188  				// selected versions of non-roots, but merely removing a requirement
  1189  				// cannot *increase* the selected versions of other roots as a result —
  1190  				// we don't need to mark this change as an upgrade. (This particular
  1191  				// change cannot invalidate any other roots.)
  1192  				continue
  1193  			}
  1194  
  1195  			var v string
  1196  			if mg == nil {
  1197  				v, _ = rs.rootSelected(m.Path)
  1198  			} else {
  1199  				v = mg.Selected(m.Path)
  1200  			}
  1201  			roots = append(roots, module.Version{Path: m.Path, Version: v})
  1202  			inRootPaths[m.Path] = true
  1203  			if v != m.Version {
  1204  				rootsUpgraded = true
  1205  			}
  1206  		}
  1207  		// Note that rs.rootModules was already sorted by module path and version,
  1208  		// and we appended to the roots slice in the same order and guaranteed that
  1209  		// each path has only one version, so roots is also sorted by module path
  1210  		// and (trivially) version.
  1211  
  1212  		if !rootsUpgraded {
  1213  			if cfg.BuildMod != "mod" {
  1214  				// The only changes to the root set (if any) were to remove duplicates.
  1215  				// The requirements are consistent (if perhaps redundant), so keep the
  1216  				// original rs to preserve its ModuleGraph.
  1217  				return rs, nil
  1218  			}
  1219  			// The root set has converged: every root going into this iteration was
  1220  			// already at its selected version, although we have removed other
  1221  			// (redundant) roots for the same path.
  1222  			break
  1223  		}
  1224  	}
  1225  
  1226  	if rs.pruning == pruned && slices.Equal(roots, rs.rootModules) && maps.Equal(direct, rs.direct) {
  1227  		// The root set is unchanged and rs was already pruned, so keep rs to
  1228  		// preserve its cached ModuleGraph (if any).
  1229  		return rs, nil
  1230  	}
  1231  	return newRequirements(pruned, roots, direct), nil
  1232  }
  1233  
  1234  // spotCheckRoots reports whether the versions of the roots in rs satisfy the
  1235  // explicit requirements of the modules in mods.
  1236  func spotCheckRoots(ctx context.Context, rs *Requirements, mods map[module.Version]bool) bool {
  1237  	ctx, cancel := context.WithCancel(ctx)
  1238  	defer cancel()
  1239  
  1240  	work := par.NewQueue(runtime.GOMAXPROCS(0))
  1241  	for m := range mods {
  1242  		m := m
  1243  		work.Add(func() {
  1244  			if ctx.Err() != nil {
  1245  				return
  1246  			}
  1247  
  1248  			summary, err := goModSummary(m)
  1249  			if err != nil {
  1250  				cancel()
  1251  				return
  1252  			}
  1253  
  1254  			for _, r := range summary.require {
  1255  				if v, ok := rs.rootSelected(r.Path); ok && gover.ModCompare(r.Path, v, r.Version) < 0 {
  1256  					cancel()
  1257  					return
  1258  				}
  1259  			}
  1260  		})
  1261  	}
  1262  	<-work.Idle()
  1263  
  1264  	if ctx.Err() != nil {
  1265  		// Either we failed a spot-check, or the caller no longer cares about our
  1266  		// answer anyway.
  1267  		return false
  1268  	}
  1269  
  1270  	return true
  1271  }
  1272  
  1273  // tidyUnprunedRoots returns a minimal set of root requirements that maintains
  1274  // the selected version of every module that provided or lexically could have
  1275  // provided a package in pkgs, and includes the selected version of every such
  1276  // module in direct as a root.
  1277  func tidyUnprunedRoots(ctx context.Context, mainModule module.Version, old *Requirements, pkgs []*loadPkg) (*Requirements, error) {
  1278  	var (
  1279  		// keep is a set of modules that provide packages or are needed to
  1280  		// disambiguate imports.
  1281  		keep     []module.Version
  1282  		keptPath = map[string]bool{}
  1283  
  1284  		// rootPaths is a list of module paths that provide packages directly
  1285  		// imported from the main module. They should be included as roots.
  1286  		rootPaths   []string
  1287  		inRootPaths = map[string]bool{}
  1288  
  1289  		// altMods is a set of paths of modules that lexically could have provided
  1290  		// imported packages. It may be okay to remove these from the list of
  1291  		// explicit requirements if that removes them from the module graph. If they
  1292  		// are present in the module graph reachable from rootPaths, they must not
  1293  		// be at a lower version. That could cause a missing sum error or a new
  1294  		// import ambiguity.
  1295  		//
  1296  		// For example, suppose a developer rewrites imports from example.com/m to
  1297  		// example.com/m/v2, then runs 'go mod tidy'. Tidy may delete the
  1298  		// requirement on example.com/m if there is no other transitive requirement
  1299  		// on it. However, if example.com/m were downgraded to a version not in
  1300  		// go.sum, when package example.com/m/v2/p is loaded, we'd get an error
  1301  		// trying to disambiguate the import, since we can't check example.com/m
  1302  		// without its sum. See #47738.
  1303  		altMods = map[string]string{}
  1304  	)
  1305  	if v, ok := old.rootSelected("go"); ok {
  1306  		keep = append(keep, module.Version{Path: "go", Version: v})
  1307  		keptPath["go"] = true
  1308  	}
  1309  	if v, ok := old.rootSelected("toolchain"); ok {
  1310  		keep = append(keep, module.Version{Path: "toolchain", Version: v})
  1311  		keptPath["toolchain"] = true
  1312  	}
  1313  	for _, pkg := range pkgs {
  1314  		if !pkg.fromExternalModule() {
  1315  			continue
  1316  		}
  1317  		if m := pkg.mod; !keptPath[m.Path] {
  1318  			keep = append(keep, m)
  1319  			keptPath[m.Path] = true
  1320  			if old.direct[m.Path] && !inRootPaths[m.Path] {
  1321  				rootPaths = append(rootPaths, m.Path)
  1322  				inRootPaths[m.Path] = true
  1323  			}
  1324  		}
  1325  		for _, m := range pkg.altMods {
  1326  			altMods[m.Path] = m.Version
  1327  		}
  1328  	}
  1329  
  1330  	// Construct a build list with a minimal set of roots.
  1331  	// This may remove or downgrade modules in altMods.
  1332  	reqs := &mvsReqs{roots: keep}
  1333  	min, err := mvs.Req(mainModule, rootPaths, reqs)
  1334  	if err != nil {
  1335  		return nil, err
  1336  	}
  1337  	buildList, err := mvs.BuildList([]module.Version{mainModule}, reqs)
  1338  	if err != nil {
  1339  		return nil, err
  1340  	}
  1341  
  1342  	// Check if modules in altMods were downgraded but not removed.
  1343  	// If so, add them to roots, which will retain an "// indirect" requirement
  1344  	// in go.mod. See comment on altMods above.
  1345  	keptAltMod := false
  1346  	for _, m := range buildList {
  1347  		if v, ok := altMods[m.Path]; ok && gover.ModCompare(m.Path, m.Version, v) < 0 {
  1348  			keep = append(keep, module.Version{Path: m.Path, Version: v})
  1349  			keptAltMod = true
  1350  		}
  1351  	}
  1352  	if keptAltMod {
  1353  		// We must run mvs.Req again instead of simply adding altMods to min.
  1354  		// It's possible that a requirement in altMods makes some other
  1355  		// explicit indirect requirement unnecessary.
  1356  		reqs.roots = keep
  1357  		min, err = mvs.Req(mainModule, rootPaths, reqs)
  1358  		if err != nil {
  1359  			return nil, err
  1360  		}
  1361  	}
  1362  
  1363  	return newRequirements(unpruned, min, old.direct), nil
  1364  }
  1365  
  1366  // updateUnprunedRoots returns a set of root requirements that includes the selected
  1367  // version of every module path in direct as a root, and maintains the selected
  1368  // version of every module selected in the graph of rs.
  1369  //
  1370  // The roots are updated such that:
  1371  //
  1372  //  1. The selected version of every module path in direct is included as a root
  1373  //     (if it is not "none").
  1374  //  2. Each root is the selected version of its path. (We say that such a root
  1375  //     set is “consistent”.)
  1376  //  3. Every version selected in the graph of rs remains selected unless upgraded
  1377  //     by a dependency in add.
  1378  //  4. Every version in add is selected at its given version unless upgraded by
  1379  //     (the dependencies of) an existing root or another module in add.
  1380  func updateUnprunedRoots(ctx context.Context, direct map[string]bool, rs *Requirements, add []module.Version) (*Requirements, error) {
  1381  	mg, err := rs.Graph(ctx)
  1382  	if err != nil {
  1383  		// We can't ignore errors in the module graph even if the user passed the -e
  1384  		// flag to try to push past them. If we can't load the complete module
  1385  		// dependencies, then we can't reliably compute a minimal subset of them.
  1386  		return rs, err
  1387  	}
  1388  
  1389  	if mustHaveCompleteRequirements() {
  1390  		// Instead of actually updating the requirements, just check that no updates
  1391  		// are needed.
  1392  		if rs == nil {
  1393  			// We're being asked to reconstruct the requirements from scratch,
  1394  			// but we aren't even allowed to modify them.
  1395  			return rs, errGoModDirty
  1396  		}
  1397  		for _, m := range rs.rootModules {
  1398  			if m.Version != mg.Selected(m.Path) {
  1399  				// The root version v is misleading: the actual selected version is higher.
  1400  				return rs, errGoModDirty
  1401  			}
  1402  		}
  1403  		for _, m := range add {
  1404  			if m.Version != mg.Selected(m.Path) {
  1405  				return rs, errGoModDirty
  1406  			}
  1407  		}
  1408  		for mPath := range direct {
  1409  			if _, ok := rs.rootSelected(mPath); !ok {
  1410  				// Module m is supposed to be listed explicitly, but isn't.
  1411  				//
  1412  				// Note that this condition is also detected (and logged with more
  1413  				// detail) earlier during package loading, so it shouldn't actually be
  1414  				// possible at this point — this is just a defense in depth.
  1415  				return rs, errGoModDirty
  1416  			}
  1417  		}
  1418  
  1419  		// No explicit roots are missing and all roots are already at the versions
  1420  		// we want to keep. Any other changes we would make are purely cosmetic,
  1421  		// such as pruning redundant indirect dependencies. Per issue #34822, we
  1422  		// ignore cosmetic changes when we cannot update the go.mod file.
  1423  		return rs, nil
  1424  	}
  1425  
  1426  	var (
  1427  		rootPaths   []string // module paths that should be included as roots
  1428  		inRootPaths = map[string]bool{}
  1429  	)
  1430  	for _, root := range rs.rootModules {
  1431  		// If the selected version of the root is the same as what was already
  1432  		// listed in the go.mod file, retain it as a root (even if redundant) to
  1433  		// avoid unnecessary churn. (See https://golang.org/issue/34822.)
  1434  		//
  1435  		// We do this even for indirect requirements, since we don't know why they
  1436  		// were added and they could become direct at any time.
  1437  		if !inRootPaths[root.Path] && mg.Selected(root.Path) == root.Version {
  1438  			rootPaths = append(rootPaths, root.Path)
  1439  			inRootPaths[root.Path] = true
  1440  		}
  1441  	}
  1442  
  1443  	// “The selected version of every module path in direct is included as a root.”
  1444  	//
  1445  	// This is only for convenience and clarity for end users: in an unpruned module,
  1446  	// the choice of explicit vs. implicit dependency has no impact on MVS
  1447  	// selection (for itself or any other module).
  1448  	keep := append(mg.BuildList()[MainModules.Len():], add...)
  1449  	for _, m := range keep {
  1450  		if direct[m.Path] && !inRootPaths[m.Path] {
  1451  			rootPaths = append(rootPaths, m.Path)
  1452  			inRootPaths[m.Path] = true
  1453  		}
  1454  	}
  1455  
  1456  	var roots []module.Version
  1457  	for _, mainModule := range MainModules.Versions() {
  1458  		min, err := mvs.Req(mainModule, rootPaths, &mvsReqs{roots: keep})
  1459  		if err != nil {
  1460  			return rs, err
  1461  		}
  1462  		roots = append(roots, min...)
  1463  	}
  1464  	if MainModules.Len() > 1 {
  1465  		gover.ModSort(roots)
  1466  	}
  1467  	if rs.pruning == unpruned && slices.Equal(roots, rs.rootModules) && maps.Equal(direct, rs.direct) {
  1468  		// The root set is unchanged and rs was already unpruned, so keep rs to
  1469  		// preserve its cached ModuleGraph (if any).
  1470  		return rs, nil
  1471  	}
  1472  
  1473  	return newRequirements(unpruned, roots, direct), nil
  1474  }
  1475  
  1476  // convertPruning returns a version of rs with the given pruning behavior.
  1477  // If rs already has the given pruning, convertPruning returns rs unmodified.
  1478  func convertPruning(ctx context.Context, rs *Requirements, pruning modPruning) (*Requirements, error) {
  1479  	if rs.pruning == pruning {
  1480  		return rs, nil
  1481  	} else if rs.pruning == workspace || pruning == workspace {
  1482  		panic("attempting to convert to/from workspace pruning and another pruning type")
  1483  	}
  1484  
  1485  	if pruning == unpruned {
  1486  		// We are converting a pruned module to an unpruned one. The roots of a
  1487  		// pruned module graph are a superset of the roots of an unpruned one, so
  1488  		// we don't need to add any new roots — we just need to drop the ones that
  1489  		// are redundant, which is exactly what updateUnprunedRoots does.
  1490  		return updateUnprunedRoots(ctx, rs.direct, rs, nil)
  1491  	}
  1492  
  1493  	// We are converting an unpruned module to a pruned one.
  1494  	//
  1495  	// An unpruned module graph includes the transitive dependencies of every
  1496  	// module in the build list. As it turns out, we can express that as a pruned
  1497  	// root set! “Include the transitive dependencies of every module in the build
  1498  	// list” is exactly what happens in a pruned module if we promote every module
  1499  	// in the build list to a root.
  1500  	mg, err := rs.Graph(ctx)
  1501  	if err != nil {
  1502  		return rs, err
  1503  	}
  1504  	return newRequirements(pruned, mg.BuildList()[MainModules.Len():], rs.direct), nil
  1505  }
  1506  

View as plain text