// Copyright 2021 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 (
	"context"
	"errors"
	"fmt"
	"maps"
	"os"
	"slices"

	"cmd/go/internal/cfg"
	"cmd/go/internal/gover"
	"cmd/go/internal/mvs"
	"cmd/internal/par"

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

// editRequirements returns an edited version of rs such that:
//
//  1. Each module version in mustSelect is selected.
//
//  2. Each module version in tryUpgrade is upgraded toward the indicated
//     version as far as can be done without violating (1).
//     (Other upgrades are also allowed if they are caused by
//     transitive requirements of versions in mustSelect or
//     tryUpgrade.)
//
//  3. Each module version in rs.rootModules (or rs.graph, if rs is unpruned)
//     is downgraded or upgraded from its original version only to the extent
//     needed to satisfy (1) and (2).
//
// Generally, the module versions in mustSelect are due to the module or a
// package within the module matching an explicit command line argument to 'go
// get', and the versions in tryUpgrade are transitive dependencies that are
// either being upgraded by 'go get -u' or being added to satisfy some
// otherwise-missing package import.
//
// If pruning is enabled, the roots of the edited requirements include an
// explicit entry for each module path in tryUpgrade, mustSelect, and the roots
// of rs, unless the selected version for the module path is "none".
func editRequirements(ld *Loader, ctx context.Context, rs *Requirements, tryUpgrade, mustSelect []module.Version) (edited *Requirements, changed bool, err error) {
	if rs.pruning == workspace {
		panic("editRequirements cannot edit workspace requirements")
	}

	orig := rs
	// If we already know what go version we will end up on after the edit, and
	// the pruning for that version is different, go ahead and apply it now.
	//
	// If we are changing from pruned to unpruned, then we MUST check the unpruned
	// graph for conflicts from the start. (Checking only for pruned conflicts
	// would miss some that would be introduced later.)
	//
	// If we are changing from unpruned to pruned, then we would like to avoid
	// unnecessary downgrades due to conflicts that would be pruned out of the
	// final graph anyway.
	//
	// Note that even if we don't find a go version in mustSelect, it is possible
	// that we will switch from unpruned to pruned (but not the other way around!)
	// after applying the edits if we find a dependency that requires a high
	// enough go version to trigger an upgrade.
	rootPruning := orig.pruning
	for _, m := range mustSelect {
		if m.Path == "go" {
			rootPruning = pruningForGoVersion(m.Version)
			break
		} else if m.Path == "toolchain" && pruningForGoVersion(gover.FromToolchain(m.Version)) == unpruned {
			// We don't know exactly what go version we will end up at, but we know
			// that it must be a version supported by the requested toolchain, and
			// that toolchain does not support pruning.
			//
			// TODO(bcmills): 'go get' ought to reject explicit toolchain versions
			// older than gover.GoStrictVersion. Once that is fixed, is this still
			// needed?
			rootPruning = unpruned
			break
		}
	}

	if rootPruning != rs.pruning {
		rs, err = convertPruning(ld, ctx, rs, rootPruning)
		if err != nil {
			return orig, false, err
		}
	}

	// selectedRoot records the edited version (possibly "none") for each module
	// path that would be a root in the edited requirements.
	var selectedRoot map[string]string // module path → edited version
	if rootPruning == pruned {
		selectedRoot = maps.Clone(rs.maxRootVersion)
	} else {
		// In a module without graph pruning, modules that provide packages imported
		// by the main module may either be explicit roots or implicit transitive
		// dependencies. To the extent possible, we want to preserve those implicit
		// dependencies, so we need to treat everything in the build list as
		// potentially relevant — that is, as what would be a “root” in a module
		// with graph pruning enabled.
		mg, err := rs.Graph(ld, ctx)
		if err != nil {
			// If we couldn't load the graph, we don't know what its requirements were
			// to begin with, so we can't edit those requirements in a coherent way.
			return orig, false, err
		}
		bl := mg.BuildList()[ld.MainModules.Len():]
		selectedRoot = make(map[string]string, len(bl))
		for _, m := range bl {
			selectedRoot[m.Path] = m.Version
		}
	}

	for _, r := range tryUpgrade {
		if v, ok := selectedRoot[r.Path]; ok && gover.ModCompare(r.Path, v, r.Version) >= 0 {
			continue
		}
		if cfg.BuildV {
			fmt.Fprintf(os.Stderr, "go: trying upgrade to %v\n", r)
		}
		selectedRoot[r.Path] = r.Version
	}

	// conflicts is a list of conflicts that we cannot resolve without violating
	// some version in mustSelect. It may be incomplete, but we want to report
	// as many conflicts as we can so that the user can solve more of them at once.
	var conflicts []Conflict

	// mustSelectVersion is an index of the versions in mustSelect.
	mustSelectVersion := make(map[string]string, len(mustSelect))
	for _, r := range mustSelect {
		if v, ok := mustSelectVersion[r.Path]; ok && v != r.Version {
			prev := module.Version{Path: r.Path, Version: v}
			if gover.ModCompare(r.Path, v, r.Version) > 0 {
				conflicts = append(conflicts, Conflict{Path: []module.Version{prev}, Constraint: r})
			} else {
				conflicts = append(conflicts, Conflict{Path: []module.Version{r}, Constraint: prev})
			}
			continue
		}

		mustSelectVersion[r.Path] = r.Version
		selectedRoot[r.Path] = r.Version
	}

	// We've indexed all of the data we need and we've computed the initial
	// versions of the roots. Now we need to load the actual module graph and
	// restore the invariant that every root is the selected version of its path.
	//
	// For 'go mod tidy' we would do that using expandGraph, which upgrades the
	// roots until their requirements are internally consistent and then drops out
	// the old roots. However, here we need to do more: we also need to make sure
	// the modules in mustSelect don't get upgraded above their intended versions.
	// To do that, we repeatedly walk the module graph, identify paths of
	// requirements that result in versions that are too high, and downgrade the
	// roots that lead to those paths. When no conflicts remain, we're done.
	//
	// Since we want to report accurate paths to each conflict, we don't drop out
	// older-than-selected roots until the process completes. That might mean that
	// we do some extra downgrades when they could be skipped, but for the benefit
	// of being able to explain the reason for every downgrade that seems
	// worthwhile.
	//
	// Graph pruning adds an extra wrinkle: a given node in the module graph
	// may be reached from a root whose dependencies are pruned, and from a root
	// whose dependencies are not pruned. It may be the case that the path from
	// the unpruned root leads to a conflict, while the path from the pruned root
	// prunes out the requirements that would lead to that conflict.
	// So we need to track the two kinds of paths independently.
	// They join back together at the roots of the graph: if a root r1 with pruned
	// requirements depends on a root r2 with unpruned requirements, then
	// selecting r1 would cause r2 to become a root and pull in all of its
	// unpruned dependencies.
	//
	// The dqTracker type implements the logic for propagating conflict paths
	// through the pruned and unpruned parts of the module graph.
	//
	// We make a best effort to fix incompatibilities, subject to two properties:
	//
	// 	1. If the user runs 'go get' with a set of mutually-compatible module
	// 	versions, we should accept those versions.
	//
	// 	2. If we end up upgrading or downgrading a module, it should be
	// 	clear why we did so.
	//
	// We don't try to find an optimal SAT solution,
	// especially given the complex interactions with graph pruning.

	var (
		roots      []module.Version // the current versions in selectedRoot, in sorted order
		rootsDirty = true           // true if roots does not match selectedRoot
	)

	// rejectedRoot records the set of module versions that have been disqualified
	// as roots of the module graph. When downgrading due to a conflict or error,
	// we skip any version that has already been rejected.
	//
	// NOTE(bcmills): I am not sure that the rejectedRoot map is really necessary,
	// since we normally only downgrade roots or accept indirect upgrades to
	// known-good versions. However, I am having trouble proving that accepting an
	// indirect upgrade never introduces a conflict that leads to further
	// downgrades. I really want to be able to prove that editRequirements
	// terminates, and the easiest way to prove it is to add this map.
	//
	// Then the proof of termination is this:
	// On every iteration where we mark the roots as dirty, we add some new module
	// version to the map. The universe of module versions is finite, so we must
	// eventually reach a state in which we do not add any version to the map.
	// In that state, we either report a conflict or succeed in the edit.
	rejectedRoot := map[module.Version]bool{}

	for rootsDirty && len(conflicts) == 0 {
		roots = roots[:0]
		for p, v := range selectedRoot {
			if v != "none" {
				roots = append(roots, module.Version{Path: p, Version: v})
			}
		}
		gover.ModSort(roots)

		// First, we extend the graph so that it includes the selected version
		// of every root. The upgraded roots are in addition to the original
		// roots, so we will have enough information to trace a path to each
		// conflict we discover from one or more of the original roots.
		mg, upgradedRoots, err := extendGraph(ld, ctx, rootPruning, roots, selectedRoot)
		if err != nil {
			if mg == nil {
				return orig, false, err
			}
			if _, ok := errors.AsType[*gover.TooNewError](err); ok {
				return orig, false, err
			}
			// We're about to walk the entire extended module graph, so we will find
			// any error then — and we will either try to resolve it by downgrading
			// something or report it as a conflict with more detail.
		}

		// extendedRootPruning is an index of the pruning used to load each root in
		// the extended module graph.
		extendedRootPruning := make(map[module.Version]modPruning, len(roots)+len(upgradedRoots))
		findPruning := func(m module.Version) modPruning {
			if rootPruning == pruned {
				summary, _ := mg.loadCache.Get(m)
				if summary != nil && summary.pruning == unpruned {
					return unpruned
				}
			}
			return rootPruning
		}
		for _, m := range roots {
			extendedRootPruning[m] = findPruning(m)
		}
		for m := range upgradedRoots {
			extendedRootPruning[m] = findPruning(m)
		}

		// Now check the resulting extended graph for errors and incompatibilities.
		t := dqTracker{extendedRootPruning: extendedRootPruning}
		mg.g.WalkBreadthFirst(func(m module.Version) {
			if max, ok := mustSelectVersion[m.Path]; ok && gover.ModCompare(m.Path, m.Version, max) > 0 {
				// m itself violates mustSelect, so it cannot appear in the module graph
				// even if its transitive dependencies would be pruned out.
				t.disqualify(m, pruned, dqState{dep: m})
				return
			}

			summary, err := mg.loadCache.Get(m)
			if err != nil && err != par.ErrCacheEntryNotFound {
				// We can't determine the requirements of m, so we don't know whether
				// they would be allowed. This may be a transient error reaching the
				// repository, rather than a permanent error with the retrieved version.
				//
				// TODO(golang.org/issue/31730, golang.org/issue/30134):
				// decide what to do based on the actual error.
				t.disqualify(m, pruned, dqState{err: err})
				return
			}

			reqs, ok := mg.RequiredBy(m)
			if !ok {
				// The dependencies of m do not appear in the module graph, so they
				// can't be causing any problems this time.
				return
			}

			if summary == nil {
				if m.Version != "" {
					panic(fmt.Sprintf("internal error: %d reqs present for %v, but summary is nil", len(reqs), m))
				}
				// m is the main module: we are editing its dependencies, so it cannot
				// become disqualified.
				return
			}

			// Before we check for problems due to transitive dependencies, first
			// check m's direct requirements. A requirement on a version r that
			// violates mustSelect disqualifies m, even if the requirements of r are
			// themselves pruned out.
			for _, r := range reqs {
				if max, ok := mustSelectVersion[r.Path]; ok && gover.ModCompare(r.Path, r.Version, max) > 0 {
					t.disqualify(m, pruned, dqState{dep: r})
					return
				}
			}
			for _, r := range reqs {
				if !t.require(m, r) {
					break
				}
			}
		})

		// We have now marked all of the versions in the graph that have conflicts,
		// with a path to each conflict from one or more roots that introduce it.
		// Now we need to identify those roots and change their versions
		// (if possible) in order to resolve the conflicts.
		rootsDirty = false
		for _, m := range roots {
			path, err := t.path(m, extendedRootPruning[m])
			if len(path) == 0 && err == nil {
				continue // Nothing wrong with m; we can keep it.
			}

			// path leads to a module with a problem: either it violates a constraint,
			// or some error prevents us from determining whether it violates a
			// constraint. We might end up logging or returning the conflict
			// information, so go ahead and fill in the details about it.
			conflict := Conflict{
				Path: path,
				Err:  err,
			}
			if err == nil {
				var last module.Version = path[len(path)-1]
				mustV, ok := mustSelectVersion[last.Path]
				if !ok {
					fmt.Fprintf(os.Stderr, "go: %v\n", conflict)
					panic("internal error: found a version conflict, but no constraint it violates")
				}
				conflict.Constraint = module.Version{
					Path:    last.Path,
					Version: mustV,
				}
			}

			if v, ok := mustSelectVersion[m.Path]; ok && v == m.Version {
				// m is in mustSelect, but is marked as disqualified due to a transitive
				// dependency.
				//
				// In theory we could try removing module paths that don't appear in
				// mustSelect (added by tryUpgrade or already present in rs) in order to
				// get graph pruning to take effect, but (a) it is likely that 'go mod
				// tidy' would re-add those roots and reintroduce unwanted upgrades,
				// causing confusion, and (b) deciding which roots to try to eliminate
				// would add a lot of complexity.
				//
				// Instead, we report the path to the conflict as an error.
				// If users want to explicitly prune out nodes from the dependency
				// graph, they can always add an explicit 'exclude' directive.
				conflicts = append(conflicts, conflict)
				continue
			}

			// If m is not the selected version of its path, we have two options: we
			// can either upgrade to the version that actually is selected (dropping m
			// itself out of the bottom of the module graph), or we can try
			// downgrading it.
			//
			// If the version we would be upgrading to is ok to use, we will just plan
			// to do that and avoid the overhead of trying to find some lower version
			// to downgrade to.
			//
			// However, it is possible that m depends on something that leads to its
			// own upgrade, so if the upgrade isn't viable we should go ahead and try
			// to downgrade (like with any other root).
			if v := mg.Selected(m.Path); v != m.Version {
				u := module.Version{Path: m.Path, Version: v}
				uPruning, ok := t.extendedRootPruning[m]
				if !ok {
					fmt.Fprintf(os.Stderr, "go: %v\n", conflict)
					panic(fmt.Sprintf("internal error: selected version of root %v is %v, but it was not expanded as a new root", m, u))
				}
				if !t.check(u, uPruning).isDisqualified() && !rejectedRoot[u] {
					// Applying the upgrade from m to u will resolve the conflict,
					// so plan to do that if there are no other conflicts to resolve.
					continue
				}
			}

			// Figure out what version of m's path was present before we started
			// the edit. We want to make sure we consider keeping it as-is,
			// even if it wouldn't normally be included. (For example, it might
			// be a pseudo-version or pre-release.)
			origMG, _ := orig.Graph(ld, ctx)
			origV := origMG.Selected(m.Path)

			if conflict.Err != nil && origV == m.Version {
				// This version of m.Path was already in the module graph before we
				// started editing, and the problem with it is that we can't load its
				// (transitive) requirements.
				//
				// If this conflict was just one step in a longer chain of downgrades,
				// then we would want to keep going past it until we find a version
				// that doesn't have that problem. However, we only want to downgrade
				// away from an *existing* requirement if we can confirm that it actually
				// conflicts with mustSelect. (For example, we don't want
				// 'go get -u ./...' to incidentally downgrade some dependency whose
				// go.mod file is unavailable or has a bad checksum.)
				conflicts = append(conflicts, conflict)
				continue
			}

			// We need to downgrade m's path to some lower version to try to resolve
			// the conflict. Find the next-lowest candidate and apply it.
			rejectedRoot[m] = true
			prev := m
			for {
				prev, err = previousVersion(ld, ctx, prev)
				if gover.ModCompare(m.Path, m.Version, origV) > 0 && (gover.ModCompare(m.Path, prev.Version, origV) < 0 || err != nil) {
					// previousVersion skipped over origV. Insert it into the order.
					prev.Version = origV
				} else if err != nil {
					// We don't know the next downgrade to try. Give up.
					return orig, false, err
				}
				if rejectedRoot[prev] {
					// We already rejected prev in a previous round.
					// To ensure that this algorithm terminates, don't try it again.
					continue
				}
				pruning := rootPruning
				if pruning == pruned {
					if summary, err := mg.loadCache.Get(m); err == nil {
						pruning = summary.pruning
					}
				}
				if t.check(prev, pruning).isDisqualified() {
					// We found a problem with prev this round that would also disqualify
					// it as a root. Don't bother trying it next round.
					rejectedRoot[prev] = true
					continue
				}
				break
			}
			selectedRoot[m.Path] = prev.Version
			rootsDirty = true

			// If this downgrade is potentially interesting, log the reason for it.
			if conflict.Err != nil || cfg.BuildV {
				var action string
				if prev.Version == "none" {
					action = fmt.Sprintf("removing %s", m)
				} else if prev.Version == origV {
					action = fmt.Sprintf("restoring %s", prev)
				} else {
					action = fmt.Sprintf("trying %s", prev)
				}
				fmt.Fprintf(os.Stderr, "go: %s\n\t%s\n", conflict.Summary(), action)
			}
		}
		if rootsDirty {
			continue
		}

		// We didn't resolve any issues by downgrading, but we may still need to
		// resolve some conflicts by locking in upgrades. Do that now.
		//
		// We don't do these upgrades until we're done downgrading because the
		// downgrade process might reveal or remove conflicts (by changing which
		// requirement edges are pruned out).
		var upgradedFrom []module.Version // for logging only
		for p, v := range selectedRoot {
			if _, ok := mustSelectVersion[p]; !ok {
				if actual := mg.Selected(p); actual != v {
					if cfg.BuildV {
						upgradedFrom = append(upgradedFrom, module.Version{Path: p, Version: v})
					}
					selectedRoot[p] = actual
					// Accepting the upgrade to m.Path might cause the selected versions
					// of other modules to fall, because they were being increased by
					// dependencies of m that are no longer present in the graph.
					//
					// TODO(bcmills): Can removing m as a root also cause the selected
					// versions of other modules to rise? I think not: we're strictly
					// removing non-root nodes from the module graph, which can't cause
					// any root to decrease (because they're roots), and the dependencies
					// of non-roots don't matter because they're either always unpruned or
					// always pruned out.
					//
					// At any rate, it shouldn't cost much to reload the module graph one
					// last time and confirm that it is stable.
					rootsDirty = true
				}
			}
		}
		if rootsDirty {
			if cfg.BuildV {
				gover.ModSort(upgradedFrom) // Make logging deterministic.
				for _, m := range upgradedFrom {
					fmt.Fprintf(os.Stderr, "go: accepting indirect upgrade from %v to %s\n", m, selectedRoot[m.Path])
				}
			}
			continue
		}
		break
	}
	if len(conflicts) > 0 {
		return orig, false, &ConstraintError{Conflicts: conflicts}
	}

	if rootPruning == unpruned {
		// An unpruned go.mod file lists only a subset of the requirements needed
		// for building packages. Figure out which requirements need to be explicit.
		var rootPaths []string

		// The modules in mustSelect are always promoted to be explicit.
		for _, m := range mustSelect {
			if m.Version != "none" && !ld.MainModules.Contains(m.Path) {
				rootPaths = append(rootPaths, m.Path)
			}
		}

		for _, m := range roots {
			if v, ok := rs.rootSelected(ld, m.Path); ok && (v == m.Version || rs.direct[m.Path]) {
				// m.Path was formerly a root, and either its version hasn't changed or
				// we believe that it provides a package directly imported by a package
				// or test in the main module. For now we'll assume that it is still
				// relevant enough to remain a root. If we actually load all of the
				// packages and tests in the main module (which we are not doing here),
				// we can revise the explicit roots at that point.
				rootPaths = append(rootPaths, m.Path)
			}
		}

		roots, err = mvs.Req(ld.MainModules.mustGetSingleMainModule(ld), rootPaths, &mvsReqs{ld: ld, roots: roots})
		if err != nil {
			return nil, false, err
		}
	}

	changed = rootPruning != orig.pruning || !slices.Equal(roots, orig.rootModules)
	if !changed {
		// Because the roots we just computed are unchanged, the entire graph must
		// be the same as it was before. Save the original rs, since we have
		// probably already loaded its requirement graph.
		return orig, false, nil
	}

	// A module that is not even in the build list necessarily cannot provide
	// any imported packages. Mark as direct only the direct modules that are
	// still in the build list. (We assume that any module path that provided a
	// direct import before the edit continues to do so after. There are a few
	// edge cases where that can change, such as if a package moves into or out of
	// a nested module or disappears entirely. If that happens, the user can run
	// 'go mod tidy' to clean up the direct/indirect annotations.)
	//
	// TODO(bcmills): Would it make more sense to leave the direct map as-is
	// but allow it to refer to modules that are no longer in the build list?
	// That might complicate updateRoots, but it may be cleaner in other ways.
	direct := make(map[string]bool, len(rs.direct))
	for _, m := range roots {
		if rs.direct[m.Path] {
			direct[m.Path] = true
		}
	}
	edited = newRequirements(ld, rootPruning, roots, direct)

	// If we ended up adding a dependency that upgrades our go version far enough
	// to activate pruning, we must convert the edited Requirements in order to
	// avoid dropping transitive dependencies from the build list the next time
	// someone uses the updated go.mod file.
	//
	// Note that it isn't possible to go in the other direction (from pruned to
	// unpruned) unless the "go" or "toolchain" module is explicitly listed in
	// mustSelect, which we already handled at the very beginning of the edit.
	// That is because the virtual "go" module only requires a "toolchain",
	// and the "toolchain" module never requires anything else, which means that
	// those two modules will never be downgraded due to a conflict with any other
	// constraint.
	if rootPruning == unpruned {
		if v, ok := edited.rootSelected(ld, "go"); ok && pruningForGoVersion(v) == pruned {
			// Since we computed the edit with the unpruned graph, and the pruned
			// graph is a strict subset of the unpruned graph, this conversion
			// preserves the exact (edited) build list that we already computed.
			//
			// However, it does that by shoving the whole build list into the roots of
			// the graph. 'go get' will check for that sort of transition and log a
			// message reminding the user how to clean up this mess we're about to
			// make. 😅
			edited, err = convertPruning(ld, ctx, edited, pruned)
			if err != nil {
				return orig, false, err
			}
		}
	}
	return edited, true, nil
}

// extendGraph loads the module graph from roots, and iteratively extends it by
// unpruning the selected version of each module path that is a root in rs or in
// the roots slice until the graph reaches a fixed point.
//
// The graph is guaranteed to converge to a fixed point because unpruning a
// module version can only increase (never decrease) the selected versions,
// and the set of versions for each module is finite.
//
// The extended graph is useful for diagnosing version conflicts: for each
// selected module version, it can provide a complete path of requirements from
// some root to that version.
func extendGraph(ld *Loader, ctx context.Context, rootPruning modPruning, roots []module.Version, selectedRoot map[string]string) (mg *ModuleGraph, upgradedRoot map[module.Version]bool, err error) {
	for {
		mg, err = readModGraph(ld, ctx, rootPruning, roots, upgradedRoot)
		// We keep on going even if err is non-nil until we reach a steady state.
		// (Note that readModGraph returns a non-nil *ModuleGraph even in case of
		// errors.) The caller may be able to fix the errors by adjusting versions,
		// so we really want to return as complete a result as we can.

		if rootPruning == unpruned {
			// Everything is already unpruned, so there isn't anything we can do to
			// extend it further.
			break
		}

		nPrevRoots := len(upgradedRoot)
		for p := range selectedRoot {
			// Since p is a root path, when we fix up the module graph to be
			// consistent with the selected versions, p will be promoted to a root,
			// which will pull in its dependencies. Ensure that its dependencies are
			// included in the module graph.
			v := mg.g.Selected(p)
			if v == "none" {
				// Version “none” always has no requirements, so it doesn't need
				// an explicit node in the module graph.
				continue
			}
			m := module.Version{Path: p, Version: v}
			if _, ok := mg.g.RequiredBy(m); !ok && !upgradedRoot[m] {
				// The dependencies of the selected version of p were not loaded.
				// Mark it as an upgrade so that we will load its dependencies
				// in the next iteration.
				//
				// Note that we don't remove any of the existing roots, even if they are
				// no longer the selected version: with graph pruning in effect this may
				// leave some spurious dependencies in the graph, but it at least
				// preserves enough of the graph to explain why each upgrade occurred:
				// this way, we can report a complete path from the passed-in roots
				// to every node in the module graph.
				//
				// This process is guaranteed to reach a fixed point: since we are only
				// adding roots (never removing them), the selected version of each module
				// can only increase, never decrease, and the set of module versions in the
				// universe is finite.
				if upgradedRoot == nil {
					upgradedRoot = make(map[module.Version]bool)
				}
				upgradedRoot[m] = true
			}
		}
		if len(upgradedRoot) == nPrevRoots {
			break
		}
	}

	return mg, upgradedRoot, err
}

type perPruning[T any] struct {
	pruned   T
	unpruned T
}

func (pp perPruning[T]) from(p modPruning) T {
	if p == unpruned {
		return pp.unpruned
	}
	return pp.pruned
}

// A dqTracker tracks and propagates the reason that each module version
// cannot be included in the module graph.
type dqTracker struct {
	// extendedRootPruning is the modPruning given the go.mod file for each root
	// in the extended module graph.
	extendedRootPruning map[module.Version]modPruning

	// dqReason records whether and why each encountered version is
	// disqualified in a pruned or unpruned context.
	dqReason map[module.Version]perPruning[dqState]

	// requiring maps each not-yet-disqualified module version to the versions
	// that would cause that module's requirements to be included in a pruned or
	// unpruned context. If that version becomes disqualified, the
	// disqualification will be propagated to all of the versions in the
	// corresponding list.
	//
	// This map is similar to the module requirement graph, but includes more
	// detail about whether a given dependency edge appears in a pruned or
	// unpruned context. (Other commands do not need this level of detail.)
	requiring map[module.Version][]module.Version
}

// A dqState indicates whether and why a module version is “disqualified” from
// being used in a way that would incorporate its requirements.
//
// The zero dqState indicates that the module version is not known to be
// disqualified, either because it is ok or because we are currently traversing
// a cycle that includes it.
type dqState struct {
	err error          // if non-nil, disqualified because the requirements of the module could not be read
	dep module.Version // disqualified because the module is or requires dep
}

func (dq dqState) isDisqualified() bool {
	return dq != dqState{}
}

func (dq dqState) String() string {
	if dq.err != nil {
		return dq.err.Error()
	}
	if dq.dep != (module.Version{}) {
		return dq.dep.String()
	}
	return "(no conflict)"
}

// require records that m directly requires r, in case r becomes disqualified.
// (These edges are in the opposite direction from the edges in an mvs.Graph.)
//
// If r is already disqualified, require propagates the disqualification to m
// and returns the reason for the disqualification.
func (t *dqTracker) require(m, r module.Version) (ok bool) {
	rdq := t.dqReason[r]
	rootPruning, isRoot := t.extendedRootPruning[r]
	if isRoot && rdq.from(rootPruning).isDisqualified() {
		// When we pull in m's dependencies, we will have an edge from m to r, and r
		// is disqualified (it is a root, which causes its problematic dependencies
		// to always be included). So we cannot pull in m's dependencies at all:
		// m is completely disqualified.
		t.disqualify(m, pruned, dqState{dep: r})
		return false
	}

	if dq := rdq.from(unpruned); dq.isDisqualified() {
		t.disqualify(m, unpruned, dqState{dep: r})
		if _, ok := t.extendedRootPruning[m]; !ok {
			// Since m is not a root, its dependencies can't be included in the pruned
			// part of the module graph, and will never be disqualified from a pruned
			// reason. We've already disqualified everything that matters.
			return false
		}
	}

	// Record that m is a dependent of r, so that if r is later disqualified
	// m will be disqualified as well.
	if t.requiring == nil {
		t.requiring = make(map[module.Version][]module.Version)
	}
	t.requiring[r] = append(t.requiring[r], m)
	return true
}

// disqualify records why the dependencies of m cannot be included in the module
// graph if reached from a part of the graph with the given pruning.
//
// Since the pruned graph is a subgraph of the unpruned graph, disqualifying a
// module from a pruned part of the graph also disqualifies it in the unpruned
// parts.
func (t *dqTracker) disqualify(m module.Version, fromPruning modPruning, reason dqState) {
	if !reason.isDisqualified() {
		panic("internal error: disqualify called with a non-disqualifying dqState")
	}

	dq := t.dqReason[m]
	if dq.from(fromPruning).isDisqualified() {
		return // Already disqualified for some other reason; don't overwrite it.
	}
	rootPruning, isRoot := t.extendedRootPruning[m]
	if fromPruning == pruned {
		dq.pruned = reason
		if !dq.unpruned.isDisqualified() {
			// Since the pruned graph of m is a subgraph of the unpruned graph, if it
			// is disqualified due to something in the pruned graph, it is certainly
			// disqualified in the unpruned graph from the same reason.
			dq.unpruned = reason
		}
	} else {
		dq.unpruned = reason
		if dq.pruned.isDisqualified() {
			panic(fmt.Sprintf("internal error: %v is marked as disqualified when pruned, but not when unpruned", m))
		}
		if isRoot && rootPruning == unpruned {
			// Since m is a root that is always unpruned, any other roots — even
			// pruned ones! — that cause it to be selected would also cause the reason
			// for is disqualification to be included in the module graph.
			dq.pruned = reason
		}
	}
	if t.dqReason == nil {
		t.dqReason = make(map[module.Version]perPruning[dqState])
	}
	t.dqReason[m] = dq

	if isRoot && (fromPruning == pruned || rootPruning == unpruned) {
		// Either m is disqualified even when its dependencies are pruned,
		// or m's go.mod file causes its dependencies to *always* be unpruned.
		// Everything that depends on it must be disqualified.
		for _, p := range t.requiring[m] {
			t.disqualify(p, pruned, dqState{dep: m})
			// Note that since the pruned graph is a subset of the unpruned graph,
			// disqualifying p in the pruned graph also disqualifies it in the
			// unpruned graph.
		}
		// Everything in t.requiring[m] is now fully disqualified.
		// We won't need to use it again.
		delete(t.requiring, m)
		return
	}

	// Either m is not a root, or it is a pruned root but only being disqualified
	// when reached from the unpruned parts of the module graph.
	// Either way, the reason for this disqualification is only visible to the
	// unpruned parts of the module graph.
	for _, p := range t.requiring[m] {
		t.disqualify(p, unpruned, dqState{dep: m})
	}
	if !isRoot {
		// Since m is not a root, its dependencies can't be included in the pruned
		// part of the module graph, and will never be disqualified from a pruned
		// reason. We've already disqualified everything that matters.
		delete(t.requiring, m)
	}
}

// check reports whether m is disqualified in the given pruning context.
func (t *dqTracker) check(m module.Version, pruning modPruning) dqState {
	return t.dqReason[m].from(pruning)
}

// path returns the path from m to the reason it is disqualified, which may be
// either a module that violates constraints or an error in loading
// requirements.
//
// If m is not disqualified, path returns (nil, nil).
func (t *dqTracker) path(m module.Version, pruning modPruning) (path []module.Version, err error) {
	for {
		if rootPruning, isRoot := t.extendedRootPruning[m]; isRoot && rootPruning == unpruned {
			// Since m is a root, any other module that requires it would cause
			// its full unpruned dependencies to be included in the module graph.
			// Those dependencies must also be considered as part of the path to the conflict.
			pruning = unpruned
		}
		dq := t.dqReason[m].from(pruning)
		if !dq.isDisqualified() {
			return path, nil
		}
		path = append(path, m)
		if dq.err != nil || dq.dep == m {
			return path, dq.err // m itself is the conflict.
		}
		m = dq.dep
	}
}