[dev.cmdgo] all: merge master (c2f96e6) into dev.cmdgo

[gostls13.git] / src / cmd / go / internal / modload / buildlist.go

// 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 {
        // depth is the depth at which the requirement graph is computed.
        //
        // If eager, the graph includes all transitive requirements regardless of depth.
        //
        // If lazy, the graph includes only the root modules, the explicit
        // requirements of those root modules, and the transitive requirements of only
        // the *non-lazy* root modules.
        depth modDepth

        // 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(depth modDepth, 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{
                depth:          depth,
                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 moudle in Vendor mode.")
                }
                mainModule := MainModules.Versions()[0]

                if rs.depth == lazy {
                        // The roots of a lazy module should already include every module in the
                        // vendor list, because the vendored modules are the same as those
                        // maintained as roots by the lazy loading “import invariant”.
                        //
                        // 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”, like a more aggressive version of lazy loading: 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.depth, 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, depth modDepth, roots []module.Version) (*ModuleGraph, error) {
        if depth == lazy {
                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 isn't the correct behavior. " +
                        "Fix this when the requirements struct is updated to reflect the struct of the module graph.")
                mg.g.Require(m, roots)
        }

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

        // 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 eager loading.
        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, depth modDepth)
        enqueue = func(m module.Version, depth modDepth) {
                if m.Version == "none" {
                        return
                }

                if depth == eager {
                        if _, dup := loadingEager.LoadOrStore(m, nil); dup {
                                // m has already been enqueued for loading. Since eager 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 implies eager loading, 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 depth == eager || summary.depth == eager {
                                for _, r := range summary.require {
                                        enqueue(r, eager)
                                }
                        }
                })
        }

        for _, m := range roots {
                enqueue(m, depth)
        }
        <-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 not relevant (such as if they
// are pruned out by lazy loading).
//
// 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 != "" {
                depth := modDepthFromGoVersion(goVersion)
                if depth == eager && rs.depth != eager {
                        // 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(eager, 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)
        }

        commitRequirements(ctx, modFileGoVersion(), 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. (When lazy loading is implemented, 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 eager 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 lazy 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
        }
        commitRequirements(ctx, modFileGoVersion(), 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
// lazy loading invariants (if applicable).
func tidyRoots(ctx context.Context, rs *Requirements, pkgs []*loadPkg) (*Requirements, error) {
        mainModule := MainModules.mustGetSingleMainModule()
        if rs.depth == eager {
                return tidyEagerRoots(ctx, mainModule, rs.direct, pkgs)
        }
        return tidyLazyRoots(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.depth == eager {
                return updateEagerRoots(ctx, direct, rs, add)
        }
        return updateLazyRoots(ctx, direct, rs, pkgs, add, rootsImported)
}

// tidyLazyRoots returns a minimal set of root requirements that maintains the
// "lazy loading" invariants of the go.mod file 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 tidyLazyRoots(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(lazy, 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(lazy, roots, tidy.direct)
                }
        }

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

// updateLazyRoots returns a set of root requirements that maintains the “lazy
// loading” invariants of the go.mod file:
//
//      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 “lazy loading” 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 updateLazyRoots 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 updateLazyRoots(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 lazy loading, 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 lazy loading 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 lazy-loading
                        // horizon.
                        //
                        // Making the module containing this package a root of the module graph
                        // does exactly that: if the module containing the package is lazy 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
                        // is eager then if we make it a root we will load all of its transitive
                        // dependencies into the module graph.
                        //
                        // (This is the “argument invariant” of lazy loading, 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 lazy-loading horizon, which could in turn change the selected
                                // versions of other modules. (Unlike for eager modules, for lazy
                                // modules adding or removing an explicit root is a semantic change, not
                                // just a cosmetic one.)
                                return rs, errGoModDirty
                        }

                        rs = newRequirements(lazy, 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 eager!
                                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.depth == lazy && reflect.DeepEqual(roots, rs.rootModules) && reflect.DeepEqual(direct, rs.direct) {
                // The root set is unchanged and rs was already lazy, so keep rs to
                // preserve its cached ModuleGraph (if any).
                return rs, nil
        }
        return newRequirements(lazy, 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
}

// tidyEagerRoots returns a minimal set of root requirements that maintains the
// selected version of every module that provided a package in pkgs, and
// includes the selected version of every such module in direct as a root.
func tidyEagerRoots(ctx context.Context, mainModule module.Version, direct map[string]bool, pkgs []*loadPkg) (*Requirements, error) {
        var (
                keep     []module.Version
                keptPath = map[string]bool{}
        )
        var (
                rootPaths   []string // module paths that should be included as roots
                inRootPaths = map[string]bool{}
        )
        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
                        }
                }
        }

        min, err := mvs.Req(mainModule, rootPaths, &mvsReqs{roots: keep})
        if err != nil {
                return nil, err
        }
        return newRequirements(eager, min, direct), nil
}

// updateEagerRoots 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 updateEagerRoots(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 eager 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.depth == eager && reflect.DeepEqual(roots, rs.rootModules) && reflect.DeepEqual(direct, rs.direct) {
                // The root set is unchanged and rs was already eager, so keep rs to
                // preserve its cached ModuleGraph (if any).
                return rs, nil
        }

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

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

        if depth == eager {
                // We are converting a lazy module to an eager one. The roots of an eager
                // module graph are a superset of the roots of a lazy graph, so we don't
                // need to add any new roots — we just need to prune away the ones that are
                // redundant given eager loading, which is exactly what updateEagerRoots
                // does.
                return updateEagerRoots(ctx, rs.direct, rs, nil)
        }

        // We are converting an eager module to a lazy one. The module graph of an
        // eager module includes the transitive dependencies of every module in the
        // build list.
        //
        // Hey, we can express that as a lazy root set! “Include the transitive
        // dependencies of every module in the build list” is exactly what happens in
        // a lazy 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(lazy, mg.BuildList()[MainModules.Len():], rs.direct), nil
}