// Copyright 2018 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package modload

import (
	"cmd/go/internal/base"
	"cmd/go/internal/cfg"
	"cmd/go/internal/mvs"
	"cmd/go/internal/par"
	"context"
	"fmt"
	"os"
	"reflect"
	"runtime"
	"runtime/debug"
	"strings"
	"sync"
	"sync/atomic"

	"golang.org/x/mod/module"
	"golang.org/x/mod/semver"
)

// capVersionSlice returns s with its cap reduced to its length.
func capVersionSlice(s []module.Version) []module.Version {
	return s[:len(s):len(s)]
}

// A Requirements represents a logically-immutable set of root module requirements.
type Requirements struct {
	// pruning is the pruning at which the requirement graph is computed.
	//
	// If unpruned, the graph includes all transitive requirements regardless
	// of whether the requiring module supports pruning.
	//
	// If pruned, the graph includes only the root modules, the explicit
	// requirements of those root modules, and the transitive requirements of only
	// the root modules that do not support pruning.
	pruning modPruning

	// rootModules is the set of module versions explicitly required by the main
	// modules, sorted and capped to length. It may contain duplicates, and may
	// contain multiple versions for a given module path.
	rootModules    []module.Version
	maxRootVersion map[string]string

	// direct is the set of module paths for which we believe the module provides
	// a package directly imported by a package or test in the main module.
	//
	// The "direct" map controls which modules are annotated with "// indirect"
	// comments in the go.mod file, and may impact which modules are listed as
	// explicit roots (vs. indirect-only dependencies). However, it should not
	// have a semantic effect on the build list overall.
	//
	// The initial direct map is populated from the existing "// indirect"
	// comments (or lack thereof) in the go.mod file. It is updated by the
	// package loader: dependencies may be promoted to direct if new
	// direct imports are observed, and may be demoted to indirect during
	// 'go mod tidy' or 'go mod vendor'.
	//
	// The direct map is keyed by module paths, not module versions. When a
	// module's selected version changes, we assume that it remains direct if the
	// previous version was a direct dependency. That assumption might not hold in
	// rare cases (such as if a dependency splits out a nested module, or merges a
	// nested module back into a parent module).
	direct map[string]bool

	graphOnce sync.Once    // guards writes to (but not reads from) graph
	graph     atomic.Value // cachedGraph
}

// A cachedGraph is a non-nil *ModuleGraph, together with any error discovered
// while loading that graph.
type cachedGraph struct {
	mg  *ModuleGraph
	err error // If err is non-nil, mg may be incomplete (but must still be non-nil).
}

// requirements is the requirement graph for the main module.
//
// It is always non-nil if the main module's go.mod file has been loaded.
//
// This variable should only be read from the loadModFile function, and should
// only be written in the loadModFile and commitRequirements functions.
// All other functions that need or produce a *Requirements should
// accept and/or return an explicit parameter.
var requirements *Requirements

// newRequirements returns a new requirement set with the given root modules.
// The dependencies of the roots will be loaded lazily at the first call to the
// Graph method.
//
// The rootModules slice must be sorted according to module.Sort.
// The caller must not modify the rootModules slice or direct map after passing
// them to newRequirements.
//
// If vendoring is in effect, the caller must invoke initVendor on the returned
// *Requirements before any other method.
func newRequirements(pruning modPruning, rootModules []module.Version, direct map[string]bool) *Requirements {
	for i, m := range rootModules {
		if m.Version == "" && MainModules.Contains(m.Path) {
			panic(fmt.Sprintf("newRequirements called with untrimmed build list: rootModules[%v] is a main module", i))
		}
		if m.Path == "" || m.Version == "" {
			panic(fmt.Sprintf("bad requirement: rootModules[%v] = %v", i, m))
		}
		if i > 0 {
			prev := rootModules[i-1]
			if prev.Path > m.Path || (prev.Path == m.Path && semver.Compare(prev.Version, m.Version) > 0) {
				panic(fmt.Sprintf("newRequirements called with unsorted roots: %v", rootModules))
			}
		}
	}

	rs := &Requirements{
		pruning:        pruning,
		rootModules:    capVersionSlice(rootModules),
		maxRootVersion: make(map[string]string, len(rootModules)),
		direct:         direct,
	}

	for _, m := range rootModules {
		if v, ok := rs.maxRootVersion[m.Path]; ok && cmpVersion(v, m.Version) >= 0 {
			continue
		}
		rs.maxRootVersion[m.Path] = m.Version
	}
	return rs
}

// initVendor initializes rs.graph from the given list of vendored module
// dependencies, overriding the graph that would normally be loaded from module
// requirements.
func (rs *Requirements) initVendor(vendorList []module.Version) {
	rs.graphOnce.Do(func() {
		mg := &ModuleGraph{
			g: mvs.NewGraph(cmpVersion, MainModules.Versions()),
		}

		if MainModules.Len() != 1 {
			panic("There should be exactly one main module in Vendor mode.")
		}
		mainModule := MainModules.Versions()[0]

		if rs.pruning == pruned {
			// The roots of a pruned module should already include every module in the
			// vendor list, because the vendored modules are the same as those needed
			// for graph pruning.
			//
			// Just to be sure, we'll double-check that here.
			inconsistent := false
			for _, m := range vendorList {
				if v, ok := rs.rootSelected(m.Path); !ok || v != m.Version {
					base.Errorf("go: vendored module %v should be required explicitly in go.mod", m)
					inconsistent = true
				}
			}
			if inconsistent {
				base.Fatalf("go: %v", errGoModDirty)
			}

			// Now we can treat the rest of the module graph as effectively “pruned
			// out”, as though we are viewing the main module from outside: in vendor
			// mode, the root requirements *are* the complete module graph.
			mg.g.Require(mainModule, rs.rootModules)
		} else {
			// The transitive requirements of the main module are not in general available
			// from the vendor directory, and we don't actually know how we got from
			// the roots to the final build list.
			//
			// Instead, we'll inject a fake "vendor/modules.txt" module that provides
			// those transitive dependencies, and mark it as a dependency of the main
			// module. That allows us to elide the actual structure of the module
			// graph, but still distinguishes between direct and indirect
			// dependencies.
			vendorMod := module.Version{Path: "vendor/modules.txt", Version: ""}
			mg.g.Require(mainModule, append(rs.rootModules, vendorMod))
			mg.g.Require(vendorMod, vendorList)
		}

		rs.graph.Store(cachedGraph{mg, nil})
	})
}

// rootSelected returns the version of the root dependency with the given module
// path, or the zero module.Version and ok=false if the module is not a root
// dependency.
func (rs *Requirements) rootSelected(path string) (version string, ok bool) {
	if MainModules.Contains(path) {
		return "", true
	}
	if v, ok := rs.maxRootVersion[path]; ok {
		return v, true
	}
	return "", false
}

// hasRedundantRoot returns true if the root list contains multiple requirements
// of the same module or a requirement on any version of the main module.
// Redundant requirements should be pruned, but they may influence version
// selection.
func (rs *Requirements) hasRedundantRoot() bool {
	for i, m := range rs.rootModules {
		if MainModules.Contains(m.Path) || (i > 0 && m.Path == rs.rootModules[i-1].Path) {
			return true
		}
	}
	return false
}

// Graph returns the graph of module requirements loaded from the current
// root modules (as reported by RootModules).
//
// Graph always makes a best effort to load the requirement graph despite any
// errors, and always returns a non-nil *ModuleGraph.
//
// If the requirements of any relevant module fail to load, Graph also
// returns a non-nil error of type *mvs.BuildListError.
func (rs *Requirements) Graph(ctx context.Context) (*ModuleGraph, error) {
	rs.graphOnce.Do(func() {
		mg, mgErr := readModGraph(ctx, rs.pruning, rs.rootModules)
		rs.graph.Store(cachedGraph{mg, mgErr})
	})
	cached := rs.graph.Load().(cachedGraph)
	return cached.mg, cached.err
}

// IsDirect returns whether the given module provides a package directly
// imported by a package or test in the main module.
func (rs *Requirements) IsDirect(path string) bool {
	return rs.direct[path]
}

// A ModuleGraph represents the complete graph of module dependencies
// of a main module.
//
// If the main module is lazily loaded, the graph does not include
// transitive dependencies of non-root (implicit) dependencies.
type ModuleGraph struct {
	g         *mvs.Graph
	loadCache par.Cache // module.Version → summaryError

	buildListOnce sync.Once
	buildList     []module.Version
}

// A summaryError is either a non-nil modFileSummary or a non-nil error
// encountered while reading or parsing that summary.
type summaryError struct {
	summary *modFileSummary
	err     error
}

var readModGraphDebugOnce sync.Once

// readModGraph reads and returns the module dependency graph starting at the
// given roots.
//
// Unlike LoadModGraph, readModGraph does not attempt to diagnose or update
// inconsistent roots.
func readModGraph(ctx context.Context, pruning modPruning, roots []module.Version) (*ModuleGraph, error) {
	if pruning == pruned {
		// Enable diagnostics for lazy module loading
		// (https://golang.org/ref/mod#lazy-loading) only if the module graph is
		// pruned.
		//
		// In unpruned modules,we load the module graph much more aggressively (in
		// order to detect inconsistencies that wouldn't be feasible to spot-check),
		// so it wouldn't be useful to log when that occurs (because it happens in
		// normal operation all the time).
		readModGraphDebugOnce.Do(func() {
			for _, f := range strings.Split(os.Getenv("GODEBUG"), ",") {
				switch f {
				case "lazymod=log":
					debug.PrintStack()
					fmt.Fprintf(os.Stderr, "go: read full module graph.\n")
				case "lazymod=strict":
					debug.PrintStack()
					base.Fatalf("go: read full module graph (forbidden by GODEBUG=lazymod=strict).")
				}
			}
		})
	}

	var (
		mu       sync.Mutex // guards mg.g and hasError during loading
		hasError bool
		mg       = &ModuleGraph{
			g: mvs.NewGraph(cmpVersion, MainModules.Versions()),
		}
	)
	for _, m := range MainModules.Versions() {
		// Require all roots from all main modules.
		_ = TODOWorkspaces("This flattens a level of the module graph, adding the dependencies " +
			"of all main modules to a single requirements struct, and losing the information of which " +
			"main module required which requirement. Rework the requirements struct and change this" +
			"to reflect the structure of the main modules.")
		mg.g.Require(m, roots)
	}

	var (
		loadQueue       = par.NewQueue(runtime.GOMAXPROCS(0))
		loadingUnpruned sync.Map // module.Version → nil; the set of modules that have been or are being loaded via roots that do not support pruning
	)

	// loadOne synchronously loads the explicit requirements for module m.
	// It does not load the transitive requirements of m even if the go version in
	// m's go.mod file indicates that it supports graph pruning.
	loadOne := func(m module.Version) (*modFileSummary, error) {
		cached := mg.loadCache.Do(m, func() interface{} {
			summary, err := goModSummary(m)

			mu.Lock()
			if err == nil {
				mg.g.Require(m, summary.require)
			} else {
				hasError = true
			}
			mu.Unlock()

			return summaryError{summary, err}
		}).(summaryError)

		return cached.summary, cached.err
	}

	var enqueue func(m module.Version, pruning modPruning)
	enqueue = func(m module.Version, pruning modPruning) {
		if m.Version == "none" {
			return
		}

		if pruning == unpruned {
			if _, dup := loadingUnpruned.LoadOrStore(m, nil); dup {
				// m has already been enqueued for loading. Since unpruned loading may
				// follow cycles in the the requirement graph, we need to return early
				// to avoid making the load queue infinitely long.
				return
			}
		}

		loadQueue.Add(func() {
			summary, err := loadOne(m)
			if err != nil {
				return // findError will report the error later.
			}

			// If the version in m's go.mod file does not support pruning, then we
			// cannot assume that the explicit requirements of m (added by loadOne)
			// are sufficient to build the packages it contains. We must load its full
			// transitive dependency graph to be sure that we see all relevant
			// dependencies.
			if pruning == unpruned || summary.pruning == unpruned {
				for _, r := range summary.require {
					enqueue(r, unpruned)
				}
			}
		})
	}

	for _, m := range roots {
		enqueue(m, pruning)
	}
	<-loadQueue.Idle()

	if hasError {
		return mg, mg.findError()
	}
	return mg, nil
}

// RequiredBy returns the dependencies required by module m in the graph,
// or ok=false if module m's dependencies are pruned out.
//
// The caller must not modify the returned slice, but may safely append to it
// and may rely on it not to be modified.
func (mg *ModuleGraph) RequiredBy(m module.Version) (reqs []module.Version, ok bool) {
	return mg.g.RequiredBy(m)
}

// Selected returns the selected version of the module with the given path.
//
// If no version is selected, Selected returns version "none".
func (mg *ModuleGraph) Selected(path string) (version string) {
	return mg.g.Selected(path)
}

// WalkBreadthFirst invokes f once, in breadth-first order, for each module
// version other than "none" that appears in the graph, regardless of whether
// that version is selected.
func (mg *ModuleGraph) WalkBreadthFirst(f func(m module.Version)) {
	mg.g.WalkBreadthFirst(f)
}

// BuildList returns the selected versions of all modules present in the graph,
// beginning with Target.
//
// The order of the remaining elements in the list is deterministic
// but arbitrary.
//
// The caller must not modify the returned list, but may safely append to it
// and may rely on it not to be modified.
func (mg *ModuleGraph) BuildList() []module.Version {
	mg.buildListOnce.Do(func() {
		mg.buildList = capVersionSlice(mg.g.BuildList())
	})
	return mg.buildList
}

func (mg *ModuleGraph) findError() error {
	errStack := mg.g.FindPath(func(m module.Version) bool {
		cached := mg.loadCache.Get(m)
		return cached != nil && cached.(summaryError).err != nil
	})
	if len(errStack) > 0 {
		err := mg.loadCache.Get(errStack[len(errStack)-1]).(summaryError).err
		var noUpgrade func(from, to module.Version) bool
		return mvs.NewBuildListError(err, errStack, noUpgrade)
	}

	return nil
}

func (mg *ModuleGraph) allRootsSelected() bool {
	for _, mm := range MainModules.Versions() {
		roots, _ := mg.g.RequiredBy(mm)
		for _, m := range roots {
			if mg.Selected(m.Path) != m.Version {
				return false
			}
		}
	}
	return true
}

// LoadModGraph loads and returns the graph of module dependencies of the main module,
// without loading any packages.
//
// If the goVersion string is non-empty, the returned graph is the graph
// as interpreted by the given Go version (instead of the version indicated
// in the go.mod file).
//
// Modules are loaded automatically (and lazily) in LoadPackages:
// LoadModGraph need only be called if LoadPackages is not,
// typically in commands that care about modules but no particular package.
func LoadModGraph(ctx context.Context, goVersion string) *ModuleGraph {
	rs := LoadModFile(ctx)

	if goVersion != "" {
		pruning := pruningForGoVersion(goVersion)
		if pruning == unpruned && rs.pruning != unpruned {
			// Use newRequirements instead of convertDepth because convertDepth
			// also updates roots; here, we want to report the unmodified roots
			// even though they may seem inconsistent.
			rs = newRequirements(unpruned, rs.rootModules, rs.direct)
		}

		mg, err := rs.Graph(ctx)
		if err != nil {
			base.Fatalf("go: %v", err)
		}
		return mg
	}

	rs, mg, err := expandGraph(ctx, rs)
	if err != nil {
		base.Fatalf("go: %v", err)
	}

	requirements = rs

	return mg
}

// expandGraph loads the complete module graph from rs.
//
// If the complete graph reveals that some root of rs is not actually the
// selected version of its path, expandGraph computes a new set of roots that
// are consistent. (With a pruned module graph, this may result in upgrades to
// other modules due to requirements that were previously pruned out.)
//
// expandGraph returns the updated roots, along with the module graph loaded
// from those roots and any error encountered while loading that graph.
// expandGraph returns non-nil requirements and a non-nil graph regardless of
// errors. On error, the roots might not be updated to be consistent.
func expandGraph(ctx context.Context, rs *Requirements) (*Requirements, *ModuleGraph, error) {
	mg, mgErr := rs.Graph(ctx)
	if mgErr != nil {
		// Without the graph, we can't update the roots: we don't know which
		// versions of transitive dependencies would be selected.
		return rs, mg, mgErr
	}

	if !mg.allRootsSelected() {
		// The roots of rs are not consistent with the rest of the graph. Update
		// them. In an unpruned module this is a no-op for the build list as a whole —
		// it just promotes what were previously transitive requirements to be
		// roots — but in a pruned module it may pull in previously-irrelevant
		// transitive dependencies.

		newRS, rsErr := updateRoots(ctx, rs.direct, rs, nil, nil, false)
		if rsErr != nil {
			// Failed to update roots, perhaps because of an error in a transitive
			// dependency needed for the update. Return the original Requirements
			// instead.
			return rs, mg, rsErr
		}
		rs = newRS
		mg, mgErr = rs.Graph(ctx)
	}

	return rs, mg, mgErr
}

// EditBuildList edits the global build list by first adding every module in add
// to the existing build list, then adjusting versions (and adding or removing
// requirements as needed) until every module in mustSelect is selected at the
// given version.
//
// (Note that the newly-added modules might not be selected in the resulting
// build list: they could be lower than existing requirements or conflict with
// versions in mustSelect.)
//
// If the versions listed in mustSelect are mutually incompatible (due to one of
// the listed modules requiring a higher version of another), EditBuildList
// returns a *ConstraintError and leaves the build list in its previous state.
//
// On success, EditBuildList reports whether the selected version of any module
// in the build list may have been changed (possibly to or from "none") as a
// result.
func EditBuildList(ctx context.Context, add, mustSelect []module.Version) (changed bool, err error) {
	rs, changed, err := editRequirements(ctx, LoadModFile(ctx), add, mustSelect)
	if err != nil {
		return false, err
	}
	requirements = rs
	return changed, err
}

// A ConstraintError describes inconsistent constraints in EditBuildList
type ConstraintError struct {
	// Conflict lists the source of the conflict for each version in mustSelect
	// that could not be selected due to the requirements of some other version in
	// mustSelect.
	Conflicts []Conflict
}

func (e *ConstraintError) Error() string {
	b := new(strings.Builder)
	b.WriteString("version constraints conflict:")
	for _, c := range e.Conflicts {
		fmt.Fprintf(b, "\n\t%v requires %v, but %v is requested", c.Source, c.Dep, c.Constraint)
	}
	return b.String()
}

// A Conflict documents that Source requires Dep, which conflicts with Constraint.
// (That is, Dep has the same module path as Constraint but a higher version.)
type Conflict struct {
	Source     module.Version
	Dep        module.Version
	Constraint module.Version
}

// tidyRoots trims the root dependencies to the minimal requirements needed to
// both retain the same versions of all packages in pkgs and satisfy the
// graph-pruning invariants (if applicable).
func tidyRoots(ctx context.Context, rs *Requirements, pkgs []*loadPkg) (*Requirements, error) {
	mainModule := MainModules.mustGetSingleMainModule()
	if rs.pruning == unpruned {
		return tidyUnprunedRoots(ctx, mainModule, rs.direct, pkgs)
	}
	return tidyPrunedRoots(ctx, mainModule, rs.direct, pkgs)
}

func updateRoots(ctx context.Context, direct map[string]bool, rs *Requirements, pkgs []*loadPkg, add []module.Version, rootsImported bool) (*Requirements, error) {
	if rs.pruning == unpruned {
		return updateUnprunedRoots(ctx, direct, rs, add)
	}
	return updatePrunedRoots(ctx, direct, rs, pkgs, add, rootsImported)
}

// tidyPrunedRoots returns a minimal set of root requirements that maintains the
// invariants of the go.mod file needed to support graph pruning for the given
// packages:
//
// 	1. For each package marked with pkgInAll, the module path that provided that
// 	   package is included as a root.
// 	2. For all packages, the module that provided that package either remains
// 	   selected at the same version or is upgraded by the dependencies of a
// 	   root.
//
// If any module that provided a package has been upgraded above its previous
// version, the caller may need to reload and recompute the package graph.
//
// To ensure that the loading process eventually converges, the caller should
// add any needed roots from the tidy root set (without removing existing untidy
// roots) until the set of roots has converged.
func tidyPrunedRoots(ctx context.Context, mainModule module.Version, direct map[string]bool, pkgs []*loadPkg) (*Requirements, error) {
	var (
		roots        []module.Version
		pathIncluded = map[string]bool{mainModule.Path: true}
	)
	// We start by adding roots for every package in "all".
	//
	// Once that is done, we may still need to add more roots to cover upgraded or
	// otherwise-missing test dependencies for packages in "all". For those test
	// dependencies, we prefer to add roots for packages with shorter import
	// stacks first, on the theory that the module requirements for those will
	// tend to fill in the requirements for their transitive imports (which have
	// deeper import stacks). So we add the missing dependencies for one depth at
	// a time, starting with the packages actually in "all" and expanding outwards
	// until we have scanned every package that was loaded.
	var (
		queue  []*loadPkg
		queued = map[*loadPkg]bool{}
	)
	for _, pkg := range pkgs {
		if !pkg.flags.has(pkgInAll) {
			continue
		}
		if pkg.fromExternalModule() && !pathIncluded[pkg.mod.Path] {
			roots = append(roots, pkg.mod)
			pathIncluded[pkg.mod.Path] = true
		}
		queue = append(queue, pkg)
		queued[pkg] = true
	}
	module.Sort(roots)
	tidy := newRequirements(pruned, roots, direct)

	for len(queue) > 0 {
		roots = tidy.rootModules
		mg, err := tidy.Graph(ctx)
		if err != nil {
			return nil, err
		}

		prevQueue := queue
		queue = nil
		for _, pkg := range prevQueue {
			m := pkg.mod
			if m.Path == "" {
				continue
			}
			for _, dep := range pkg.imports {
				if !queued[dep] {
					queue = append(queue, dep)
					queued[dep] = true
				}
			}
			if pkg.test != nil && !queued[pkg.test] {
				queue = append(queue, pkg.test)
				queued[pkg.test] = true
			}
			if !pathIncluded[m.Path] {
				if s := mg.Selected(m.Path); cmpVersion(s, m.Version) < 0 {
					roots = append(roots, m)
				}
				pathIncluded[m.Path] = true
			}
		}

		if len(roots) > len(tidy.rootModules) {
			module.Sort(roots)
			tidy = newRequirements(pruned, roots, tidy.direct)
		}
	}

	_, err := tidy.Graph(ctx)
	if err != nil {
		return nil, err
	}
	return tidy, nil
}

// updatePrunedRoots returns a set of root requirements that maintains the
// invariants of the go.mod file needed to support graph pruning:
//
// 	1. The selected version of the module providing each package marked with
// 	   either pkgInAll or pkgIsRoot is included as a root.
// 	   Note that certain root patterns (such as '...') may explode the root set
// 	   to contain every module that provides any package imported (or merely
// 	   required) by any other module.
// 	2. Each root appears only once, at the selected version of its path
// 	   (if rs.graph is non-nil) or at the highest version otherwise present as a
// 	   root (otherwise).
// 	3. Every module path that appears as a root in rs remains a root.
// 	4. Every version in add is selected at its given version unless upgraded by
// 	   (the dependencies of) an existing root or another module in add.
//
// The packages in pkgs are assumed to have been loaded from either the roots of
// rs or the modules selected in the graph of rs.
//
// The above invariants together imply the graph-pruning invariants for the
// go.mod file:
//
// 	1. (The import invariant.) Every module that provides a package transitively
// 	   imported by any package or test in the main module is included as a root.
// 	   This follows by induction from (1) and (3) above. Transitively-imported
// 	   packages loaded during this invocation are marked with pkgInAll (1),
// 	   and by hypothesis any transitively-imported packages loaded in previous
// 	   invocations were already roots in rs (3).
//
// 	2. (The argument invariant.) Every module that provides a package matching
// 	   an explicit package pattern is included as a root. This follows directly
// 	   from (1): packages matching explicit package patterns are marked with
// 	   pkgIsRoot.
//
// 	3. (The completeness invariant.) Every module that contributed any package
// 	   to the build is required by either the main module or one of the modules
// 	   it requires explicitly. This invariant is left up to the caller, who must
// 	   not load packages from outside the module graph but may add roots to the
// 	   graph, but is facilited by (3). If the caller adds roots to the graph in
// 	   order to resolve missing packages, then updatePrunedRoots will retain them,
// 	   the selected versions of those roots cannot regress, and they will
// 	   eventually be written back to the main module's go.mod file.
//
// (See https://golang.org/design/36460-lazy-module-loading#invariants for more
// detail.)
func updatePrunedRoots(ctx context.Context, direct map[string]bool, rs *Requirements, pkgs []*loadPkg, add []module.Version, rootsImported bool) (*Requirements, error) {
	roots := rs.rootModules
	rootsUpgraded := false

	spotCheckRoot := map[module.Version]bool{}

	// “The selected version of the module providing each package marked with
	// either pkgInAll or pkgIsRoot is included as a root.”
	needSort := false
	for _, pkg := range pkgs {
		if !pkg.fromExternalModule() {
			// pkg was not loaded from a module dependency, so we don't need
			// to do anything special to maintain that dependency.
			continue
		}

		switch {
		case pkg.flags.has(pkgInAll):
			// pkg is transitively imported by a package or test in the main module.
			// We need to promote the module that maintains it to a root: if some
			// other module depends on the main module, and that other module also
			// uses a pruned module graph, it will expect to find all of our
			// transitive dependencies by reading just our go.mod file, not the go.mod
			// files of everything we depend on.
			//
			// (This is the “import invariant” that makes graph pruning possible.)

		case rootsImported && pkg.flags.has(pkgFromRoot):
			// pkg is a transitive dependency of some root, and we are treating the
			// roots as if they are imported by the main module (as in 'go get').

		case pkg.flags.has(pkgIsRoot):
			// pkg is a root of the package-import graph. (Generally this means that
			// it matches a command-line argument.) We want future invocations of the
			// 'go' command — such as 'go test' on the same package — to continue to
			// use the same versions of its dependencies that we are using right now.
			// So we need to bring this package's dependencies inside the pruned
			// module graph.
			//
			// Making the module containing this package a root of the module graph
			// does exactly that: if the module containing the package supports graph
			// pruning then it should satisfy the import invariant itself, so all of
			// its dependencies should be in its go.mod file, and if the module
			// containing the package does not support pruning then if we make it a
			// root we will load all of its (unpruned) transitive dependencies into
			// the module graph.
			//
			// (This is the “argument invariant”, and is important for
			// reproducibility.)

		default:
			// pkg is a dependency of some other package outside of the main module.
			// As far as we know it's not relevant to the main module (and thus not
			// relevant to consumers of the main module either), and its dependencies
			// should already be in the module graph — included in the dependencies of
			// the package that imported it.
			continue
		}

		if _, ok := rs.rootSelected(pkg.mod.Path); ok {
			// It is possible that the main module's go.mod file is incomplete or
			// otherwise erroneous — for example, perhaps the author forgot to 'git
			// add' their updated go.mod file after adding a new package import, or
			// perhaps they made an edit to the go.mod file using a third-party tool
			// ('git merge'?) that doesn't maintain consistency for module
			// dependencies. If that happens, ideally we want to detect the missing
			// requirements and fix them up here.
			//
			// However, we also need to be careful not to be too aggressive. For
			// transitive dependencies of external tests, the go.mod file for the
			// module containing the test itself is expected to provide all of the
			// relevant dependencies, and we explicitly don't want to pull in
			// requirements on *irrelevant* requirements that happen to occur in the
			// go.mod files for these transitive-test-only dependencies. (See the test
			// in mod_lazy_test_horizon.txt for a concrete example.
			//
			// The “goldilocks zone” seems to be to spot-check exactly the same
			// modules that we promote to explicit roots: namely, those that provide
			// packages transitively imported by the main module, and those that
			// provide roots of the package-import graph. That will catch erroneous
			// edits to the main module's go.mod file and inconsistent requirements in
			// dependencies that provide imported packages, but will ignore erroneous
			// or misleading requirements in dependencies that aren't obviously
			// relevant to the packages in the main module.
			spotCheckRoot[pkg.mod] = true
		} else {
			roots = append(roots, pkg.mod)
			rootsUpgraded = true
			// The roots slice was initially sorted because rs.rootModules was sorted,
			// but the root we just added could be out of order.
			needSort = true
		}
	}

	for _, m := range add {
		if v, ok := rs.rootSelected(m.Path); !ok || cmpVersion(v, m.Version) < 0 {
			roots = append(roots, m)
			rootsUpgraded = true
			needSort = true
		}
	}
	if needSort {
		module.Sort(roots)
	}

	// "Each root appears only once, at the selected version of its path ….”
	for {
		var mg *ModuleGraph
		if rootsUpgraded {
			// We've added or upgraded one or more roots, so load the full module
			// graph so that we can update those roots to be consistent with other
			// requirements.
			if mustHaveCompleteRequirements() {
				// Our changes to the roots may have moved dependencies into or out of
				// the graph-pruning horizon, which could in turn change the selected
				// versions of other modules. (For pruned modules adding or removing an
				// explicit root is a semantic change, not just a cosmetic one.)
				return rs, errGoModDirty
			}

			rs = newRequirements(pruned, roots, direct)
			var err error
			mg, err = rs.Graph(ctx)
			if err != nil {
				return rs, err
			}
		} else {
			// Since none of the roots have been upgraded, we have no reason to
			// suspect that they are inconsistent with the requirements of any other
			// roots. Only look at the full module graph if we've already loaded it;
			// otherwise, just spot-check the explicit requirements of the roots from
			// which we loaded packages.
			if rs.graph.Load() != nil {
				// We've already loaded the full module graph, which includes the
				// requirements of all of the root modules — even the transitive
				// requirements, if they are unpruned!
				mg, _ = rs.Graph(ctx)
			} else if cfg.BuildMod == "vendor" {
				// We can't spot-check the requirements of other modules because we
				// don't in general have their go.mod files available in the vendor
				// directory. (Fortunately this case is impossible, because mg.graph is
				// always non-nil in vendor mode!)
				panic("internal error: rs.graph is unexpectedly nil with -mod=vendor")
			} else if !spotCheckRoots(ctx, rs, spotCheckRoot) {
				// We spot-checked the explicit requirements of the roots that are
				// relevant to the packages we've loaded. Unfortunately, they're
				// inconsistent in some way; we need to load the full module graph
				// so that we can fix the roots properly.
				var err error
				mg, err = rs.Graph(ctx)
				if err != nil {
					return rs, err
				}
			}
		}

		roots = make([]module.Version, 0, len(rs.rootModules))
		rootsUpgraded = false
		inRootPaths := make(map[string]bool, len(rs.rootModules)+1)
		for _, mm := range MainModules.Versions() {
			inRootPaths[mm.Path] = true
		}
		for _, m := range rs.rootModules {
			if inRootPaths[m.Path] {
				// This root specifies a redundant path. We already retained the
				// selected version of this path when we saw it before, so omit the
				// redundant copy regardless of its version.
				//
				// When we read the full module graph, we include the dependencies of
				// every root even if that root is redundant. That better preserves
				// reproducibility if, say, some automated tool adds a redundant
				// 'require' line and then runs 'go mod tidy' to try to make everything
				// consistent, since the requirements of the older version are carried
				// over.
				//
				// So omitting a root that was previously present may *reduce* the
				// selected versions of non-roots, but merely removing a requirement
				// cannot *increase* the selected versions of other roots as a result —
				// we don't need to mark this change as an upgrade. (This particular
				// change cannot invalidate any other roots.)
				continue
			}

			var v string
			if mg == nil {
				v, _ = rs.rootSelected(m.Path)
			} else {
				v = mg.Selected(m.Path)
			}
			roots = append(roots, module.Version{Path: m.Path, Version: v})
			inRootPaths[m.Path] = true
			if v != m.Version {
				rootsUpgraded = true
			}
		}
		// Note that rs.rootModules was already sorted by module path and version,
		// and we appended to the roots slice in the same order and guaranteed that
		// each path has only one version, so roots is also sorted by module path
		// and (trivially) version.

		if !rootsUpgraded {
			if cfg.BuildMod != "mod" {
				// The only changes to the root set (if any) were to remove duplicates.
				// The requirements are consistent (if perhaps redundant), so keep the
				// original rs to preserve its ModuleGraph.
				return rs, nil
			}
			// The root set has converged: every root going into this iteration was
			// already at its selected version, although we have have removed other
			// (redundant) roots for the same path.
			break
		}
	}

	if rs.pruning == pruned && reflect.DeepEqual(roots, rs.rootModules) && reflect.DeepEqual(direct, rs.direct) {
		// The root set is unchanged and rs was already pruned, so keep rs to
		// preserve its cached ModuleGraph (if any).
		return rs, nil
	}
	return newRequirements(pruned, roots, direct), nil
}

// spotCheckRoots reports whether the versions of the roots in rs satisfy the
// explicit requirements of the modules in mods.
func spotCheckRoots(ctx context.Context, rs *Requirements, mods map[module.Version]bool) bool {
	ctx, cancel := context.WithCancel(ctx)
	defer cancel()

	work := par.NewQueue(runtime.GOMAXPROCS(0))
	for m := range mods {
		m := m
		work.Add(func() {
			if ctx.Err() != nil {
				return
			}

			summary, err := goModSummary(m)
			if err != nil {
				cancel()
				return
			}

			for _, r := range summary.require {
				if v, ok := rs.rootSelected(r.Path); ok && cmpVersion(v, r.Version) < 0 {
					cancel()
					return
				}
			}
		})
	}
	<-work.Idle()

	if ctx.Err() != nil {
		// Either we failed a spot-check, or the caller no longer cares about our
		// answer anyway.
		return false
	}

	return true
}

// tidyUnprunedRoots returns a minimal set of root requirements that maintains
// the selected version of every module that provided or lexically could have
// provided a package in pkgs, and includes the selected version of every such
// module in direct as a root.
func tidyUnprunedRoots(ctx context.Context, mainModule module.Version, direct map[string]bool, pkgs []*loadPkg) (*Requirements, error) {
	var (
		// keep is a set of of modules that provide packages or are needed to
		// disambiguate imports.
		keep     []module.Version
		keptPath = map[string]bool{}

		// rootPaths is a list of module paths that provide packages directly
		// imported from the main module. They should be included as roots.
		rootPaths   []string
		inRootPaths = map[string]bool{}

		// altMods is a set of paths of modules that lexically could have provided
		// imported packages. It may be okay to remove these from the list of
		// explicit requirements if that removes them from the module graph. If they
		// are present in the module graph reachable from rootPaths, they must not
		// be at a lower version. That could cause a missing sum error or a new
		// import ambiguity.
		//
		// For example, suppose a developer rewrites imports from example.com/m to
		// example.com/m/v2, then runs 'go mod tidy'. Tidy may delete the
		// requirement on example.com/m if there is no other transitive requirement
		// on it. However, if example.com/m were downgraded to a version not in
		// go.sum, when package example.com/m/v2/p is loaded, we'd get an error
		// trying to disambiguate the import, since we can't check example.com/m
		// without its sum. See #47738.
		altMods = map[string]string{}
	)
	for _, pkg := range pkgs {
		if !pkg.fromExternalModule() {
			continue
		}
		if m := pkg.mod; !keptPath[m.Path] {
			keep = append(keep, m)
			keptPath[m.Path] = true
			if direct[m.Path] && !inRootPaths[m.Path] {
				rootPaths = append(rootPaths, m.Path)
				inRootPaths[m.Path] = true
			}
		}
		for _, m := range pkg.altMods {
			altMods[m.Path] = m.Version
		}
	}

	// Construct a build list with a minimal set of roots.
	// This may remove or downgrade modules in altMods.
	reqs := &mvsReqs{roots: keep}
	min, err := mvs.Req(mainModule, rootPaths, reqs)
	if err != nil {
		return nil, err
	}
	buildList, err := mvs.BuildList([]module.Version{mainModule}, reqs)
	if err != nil {
		return nil, err
	}

	// Check if modules in altMods were downgraded but not removed.
	// If so, add them to roots, which will retain an "// indirect" requirement
	// in go.mod. See comment on altMods above.
	keptAltMod := false
	for _, m := range buildList {
		if v, ok := altMods[m.Path]; ok && semver.Compare(m.Version, v) < 0 {
			keep = append(keep, module.Version{Path: m.Path, Version: v})
			keptAltMod = true
		}
	}
	if keptAltMod {
		// We must run mvs.Req again instead of simply adding altMods to min.
		// It's possible that a requirement in altMods makes some other
		// explicit indirect requirement unnecessary.
		reqs.roots = keep
		min, err = mvs.Req(mainModule, rootPaths, reqs)
		if err != nil {
			return nil, err
		}
	}

	return newRequirements(unpruned, min, direct), nil
}

// updateUnprunedRoots returns a set of root requirements that includes the selected
// version of every module path in direct as a root, and maintains the selected
// version of every module selected in the graph of rs.
//
// The roots are updated such that:
//
// 	1. The selected version of every module path in direct is included as a root
// 	   (if it is not "none").
// 	2. Each root is the selected version of its path. (We say that such a root
// 	   set is “consistent”.)
// 	3. Every version selected in the graph of rs remains selected unless upgraded
// 	   by a dependency in add.
// 	4. Every version in add is selected at its given version unless upgraded by
// 	   (the dependencies of) an existing root or another module in add.
func updateUnprunedRoots(ctx context.Context, direct map[string]bool, rs *Requirements, add []module.Version) (*Requirements, error) {
	mg, err := rs.Graph(ctx)
	if err != nil {
		// We can't ignore errors in the module graph even if the user passed the -e
		// flag to try to push past them. If we can't load the complete module
		// dependencies, then we can't reliably compute a minimal subset of them.
		return rs, err
	}

	if mustHaveCompleteRequirements() {
		// Instead of actually updating the requirements, just check that no updates
		// are needed.
		if rs == nil {
			// We're being asked to reconstruct the requirements from scratch,
			// but we aren't even allowed to modify them.
			return rs, errGoModDirty
		}
		for _, m := range rs.rootModules {
			if m.Version != mg.Selected(m.Path) {
				// The root version v is misleading: the actual selected version is higher.
				return rs, errGoModDirty
			}
		}
		for _, m := range add {
			if m.Version != mg.Selected(m.Path) {
				return rs, errGoModDirty
			}
		}
		for mPath := range direct {
			if _, ok := rs.rootSelected(mPath); !ok {
				// Module m is supposed to be listed explicitly, but isn't.
				//
				// Note that this condition is also detected (and logged with more
				// detail) earlier during package loading, so it shouldn't actually be
				// possible at this point — this is just a defense in depth.
				return rs, errGoModDirty
			}
		}

		// No explicit roots are missing and all roots are already at the versions
		// we want to keep. Any other changes we would make are purely cosmetic,
		// such as pruning redundant indirect dependencies. Per issue #34822, we
		// ignore cosmetic changes when we cannot update the go.mod file.
		return rs, nil
	}

	var (
		rootPaths   []string // module paths that should be included as roots
		inRootPaths = map[string]bool{}
	)
	for _, root := range rs.rootModules {
		// If the selected version of the root is the same as what was already
		// listed in the go.mod file, retain it as a root (even if redundant) to
		// avoid unnecessary churn. (See https://golang.org/issue/34822.)
		//
		// We do this even for indirect requirements, since we don't know why they
		// were added and they could become direct at any time.
		if !inRootPaths[root.Path] && mg.Selected(root.Path) == root.Version {
			rootPaths = append(rootPaths, root.Path)
			inRootPaths[root.Path] = true
		}
	}

	// “The selected version of every module path in direct is included as a root.”
	//
	// This is only for convenience and clarity for end users: in an unpruned module,
	// the choice of explicit vs. implicit dependency has no impact on MVS
	// selection (for itself or any other module).
	keep := append(mg.BuildList()[MainModules.Len():], add...)
	for _, m := range keep {
		if direct[m.Path] && !inRootPaths[m.Path] {
			rootPaths = append(rootPaths, m.Path)
			inRootPaths[m.Path] = true
		}
	}

	// TODO(matloob): Make roots into a map.
	var roots []module.Version
	for _, mainModule := range MainModules.Versions() {
		min, err := mvs.Req(mainModule, rootPaths, &mvsReqs{roots: keep})
		if err != nil {
			return rs, err
		}
		roots = append(roots, min...)
	}
	if MainModules.Len() > 1 {
		module.Sort(roots)
	}
	if rs.pruning == unpruned && reflect.DeepEqual(roots, rs.rootModules) && reflect.DeepEqual(direct, rs.direct) {
		// The root set is unchanged and rs was already unpruned, so keep rs to
		// preserve its cached ModuleGraph (if any).
		return rs, nil
	}

	return newRequirements(unpruned, roots, direct), nil
}

// convertPruning returns a version of rs with the given pruning behavior.
// If rs already has the given pruning, convertPruning returns rs unmodified.
func convertPruning(ctx context.Context, rs *Requirements, pruning modPruning) (*Requirements, error) {
	if rs.pruning == pruning {
		return rs, nil
	}

	if pruning == unpruned {
		// We are converting a pruned module to an unpruned one. The roots of a
		// ppruned module graph are a superset of the roots of an unpruned one, so
		// we don't need to add any new roots — we just need to drop the ones that
		// are redundant, which is exactly what updateUnprunedRoots does.
		return updateUnprunedRoots(ctx, rs.direct, rs, nil)
	}

	// We are converting an unpruned module to a pruned one.
	//
	// An unpruned module graph includes the transitive dependencies of every
	// module in the build list. As it turns out, we can express that as a pruned
	// root set! “Include the transitive dependencies of every module in the build
	// list” is exactly what happens in a pruned module if we promote every module
	// in the build list to a root.
	mg, err := rs.Graph(ctx)
	if err != nil {
		return rs, err
	}
	return newRequirements(pruned, mg.BuildList()[MainModules.Len():], rs.direct), nil
}