diff options
Diffstat (limited to 'src/cmd/go/internal/modload')
-rw-r--r-- | src/cmd/go/internal/modload/buildlist.go | 110 | ||||
-rw-r--r-- | src/cmd/go/internal/modload/edit.go | 1148 | ||||
-rw-r--r-- | src/cmd/go/internal/modload/modfile.go | 14 | ||||
-rw-r--r-- | src/cmd/go/internal/modload/mvs.go | 9 |
4 files changed, 759 insertions, 522 deletions
diff --git a/src/cmd/go/internal/modload/buildlist.go b/src/cmd/go/internal/modload/buildlist.go index 1b4d6b99d0..def9c489e9 100644 --- a/src/cmd/go/internal/modload/buildlist.go +++ b/src/cmd/go/internal/modload/buildlist.go @@ -145,6 +145,11 @@ func newRequirements(pruning modPruning, rootModules []module.Version, direct ma return rs } +// String returns a string describing the Requirements for debugging. +func (rs *Requirements) String() string { + return fmt.Sprintf("{%v %v}", rs.pruning, rs.rootModules) +} + // initVendor initializes rs.graph from the given list of vendored module // dependencies, overriding the graph that would normally be loaded from module // requirements. @@ -235,7 +240,7 @@ func (rs *Requirements) hasRedundantRoot() bool { // 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) + mg, mgErr := readModGraph(ctx, rs.pruning, rs.rootModules, nil) rs.graph.Store(&cachedGraph{mg, mgErr}) }) cached := rs.graph.Load() @@ -266,9 +271,12 @@ var readModGraphDebugOnce sync.Once // readModGraph reads and returns the module dependency graph starting at the // given roots. // +// The requirements of the module versions found in the unprune map are included +// in the graph even if they would normally be pruned out. +// // Unlike LoadModGraph, readModGraph does not attempt to diagnose or update // inconsistent roots. -func readModGraph(ctx context.Context, pruning modPruning, roots []module.Version) (*ModuleGraph, error) { +func readModGraph(ctx context.Context, pruning modPruning, roots []module.Version, unprune map[module.Version]bool) (*ModuleGraph, error) { if pruning == pruned { // Enable diagnostics for lazy module loading // (https://golang.org/ref/mod#lazy-loading) only if the module graph is @@ -355,13 +363,14 @@ func readModGraph(ctx context.Context, pruning modPruning, roots []module.Versio // 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 != pruned || summary.pruning == unpruned { - nextPruning := summary.pruning - if pruning == unpruned { - nextPruning = unpruned - } - for _, r := range summary.require { + // dependencies. In addition, we must load the requirements of any module + // that is explicitly marked as unpruned. + nextPruning := summary.pruning + if pruning == unpruned { + nextPruning = unpruned + } + for _, r := range summary.require { + if pruning != pruned || summary.pruning == unpruned || unprune[r] { enqueue(r, nextPruning) } } @@ -607,17 +616,90 @@ 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) + fmt.Fprintf(b, "\n\t%s", c.Summary()) } 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.) +// A Conflict is a path of requirements starting at a root or proposed root in +// the requirement graph, explaining why that root either causes a module passed +// in the mustSelect list to EditBuildList to be unattainable, or introduces an +// unresolvable error in loading the requirement graph. type Conflict struct { - Source module.Version - Dep module.Version + // Path is a path of requirements starting at some module version passed in + // the mustSelect argument and ending at a module whose requirements make that + // version unacceptable. (Path always has len ≥ 1.) + Path []module.Version + + // If Err is nil, Constraint is a module version passed in the mustSelect + // argument that has the same module path as, and a lower version than, + // the last element of the Path slice. Constraint module.Version + + // If Constraint is unset, Err is an error encountered when loading the + // requirements of the last element in Path. + Err error +} + +// UnwrapModuleError returns c.Err, but unwraps it if it is a module.ModuleError +// with a version and path matching the last entry in the Path slice. +func (c Conflict) UnwrapModuleError() error { + me, ok := c.Err.(*module.ModuleError) + if ok && len(c.Path) > 0 { + last := c.Path[len(c.Path)-1] + if me.Path == last.Path && me.Version == last.Version { + return me.Err + } + } + return c.Err +} + +// Summary returns a string that describes only the first and last modules in +// the conflict path. +func (c Conflict) Summary() string { + if len(c.Path) == 0 { + return "(internal error: invalid Conflict struct)" + } + first := c.Path[0] + last := c.Path[len(c.Path)-1] + if len(c.Path) == 1 { + if c.Err != nil { + return fmt.Sprintf("%s: %v", first, c.UnwrapModuleError()) + } + return fmt.Sprintf("%s is above %s", first, c.Constraint.Version) + } + + adverb := "" + if len(c.Path) > 2 { + adverb = "indirectly " + } + if c.Err != nil { + return fmt.Sprintf("%s %srequires %s: %v", first, adverb, last, c.UnwrapModuleError()) + } + return fmt.Sprintf("%s %srequires %s, but %s is requested", first, adverb, last, c.Constraint.Version) +} + +// String returns a string that describes the full conflict path. +func (c Conflict) String() string { + if len(c.Path) == 0 { + return "(internal error: invalid Conflict struct)" + } + b := new(strings.Builder) + fmt.Fprintf(b, "%v", c.Path[0]) + if len(c.Path) == 1 { + fmt.Fprintf(b, " found") + } else { + for _, r := range c.Path[1:] { + fmt.Fprintf(b, " requires\n\t%v", r) + } + } + if c.Constraint != (module.Version{}) { + fmt.Fprintf(b, ", but %v is requested", c.Constraint.Version) + } + if c.Err != nil { + fmt.Fprintf(b, ": %v", c.UnwrapModuleError()) + } + return b.String() } // tidyRoots trims the root dependencies to the minimal requirements needed to diff --git a/src/cmd/go/internal/modload/edit.go b/src/cmd/go/internal/modload/edit.go index f6937a48b4..8e81dd18a2 100644 --- a/src/cmd/go/internal/modload/edit.go +++ b/src/cmd/go/internal/modload/edit.go @@ -5,13 +5,16 @@ package modload import ( + "cmd/go/internal/cfg" "cmd/go/internal/mvs" + "cmd/go/internal/par" "context" - "reflect" - "sort" + "fmt" + "maps" + "os" + "slices" "golang.org/x/mod/module" - "golang.org/x/mod/semver" ) // editRequirements returns an edited version of rs such that: @@ -20,436 +23,603 @@ import ( // // 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 from its original version only to the extent needed to -// satisfy (1), or upgraded only to the extent needed to satisfy (1) and -// (2). -// -// 4. No module is upgraded above the maximum version of its path found in the -// dependency graph of rs, the combined dependency graph of the versions in -// mustSelect, or the dependencies of each individual module version in -// tryUpgrade. +// 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(ctx context.Context, rs *Requirements, tryUpgrade, mustSelect []module.Version) (edited *Requirements, changed bool, err error) { - limiter, err := limiterForEdit(ctx, rs, tryUpgrade, mustSelect) - if err != nil { - return rs, false, err + if rs.pruning == workspace { + panic("editRequirements cannot edit workspace requirements") } - var conflicts []Conflict - for _, m := range mustSelect { - conflict, err := limiter.Select(m) + // 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 rs.pruning == 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(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 rs, false, err } - if conflict.Path != "" { - conflicts = append(conflicts, Conflict{ - Source: m, - Dep: conflict, - Constraint: module.Version{ - Path: conflict.Path, - Version: limiter.max[conflict.Path], - }, - }) + bl := mg.BuildList()[MainModules.Len():] + selectedRoot = make(map[string]string, len(bl)) + for _, m := range bl { + selectedRoot[m.Path] = m.Version } } - if len(conflicts) > 0 { - return rs, false, &ConstraintError{Conflicts: conflicts} - } - - mods, changed, err := selectPotentiallyImportedModules(ctx, limiter, rs, tryUpgrade) - if err != nil { - return rs, false, err - } - var roots []module.Version - if rs.pruning == unpruned { - // In a module without graph pruning, modules that provide packages imported - // by the main module may either be explicit roots or implicit transitive - // dependencies. We promote the modules in mustSelect to be explicit - // requirements. - var rootPaths []string - for _, m := range mustSelect { - if m.Version != "none" && !MainModules.Contains(m.Path) { - rootPaths = append(rootPaths, m.Path) - } + for _, r := range tryUpgrade { + if v, ok := selectedRoot[r.Path]; ok && cmpVersion(v, r.Version) >= 0 { + continue } - if !changed && len(rootPaths) == 0 { - // The build list hasn't changed and we have no new roots to add. - // We don't need to recompute the minimal roots for the module. - return rs, false, nil + if cfg.BuildV { + fmt.Fprintf(os.Stderr, "go: trying upgrade to %v\n", r) } + selectedRoot[r.Path] = r.Version + } - for _, m := range mods { - if v, ok := rs.rootSelected(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) + // 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 cmpVersion(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 } - roots, err = mvs.Req(MainModules.mustGetSingleMainModule(), rootPaths, &mvsReqs{roots: mods}) - if err != nil { - return nil, false, err - } - } else { - // In a module with a pruned graph, every module that provides a package - // imported by the main module must be retained as a root. - roots = mods - 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 rs, false, nil - } + mustSelectVersion[r.Path] = r.Version + selectedRoot[r.Path] = r.Version } - // 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'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. // - // 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 - } - } - return newRequirements(rs.pruning, roots, direct), changed, nil -} + // 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. -// limiterForEdit returns a versionLimiter with its max versions set such that -// the max version for every module path in mustSelect is the version listed -// there, and the max version for every other module path is the maximum version -// of its path found in the dependency graph of rs, the combined dependency -// graph of the versions in mustSelect, or the dependencies of each individual -// module version in tryUpgrade. -func limiterForEdit(ctx context.Context, rs *Requirements, tryUpgrade, mustSelect []module.Version) (*versionLimiter, error) { - mg, err := rs.Graph(ctx) - if err != nil { - return nil, err - } + var ( + roots []module.Version // the current versions in selectedRoot, in sorted order + rootsDirty = true // true if roots does not match selectedRoot + ) - maxVersion := map[string]string{} // module path → version - restrictTo := func(m module.Version) { - v, ok := maxVersion[m.Path] - if !ok || cmpVersion(v, m.Version) > 0 { - maxVersion[m.Path] = m.Version + // 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}) + } } - } + module.Sort(roots) - if rs.pruning == unpruned { - // go.mod files that do not support graph pruning don't indicate which - // transitive dependencies are actually relevant to the main module, so we - // have to assume that any module that could have provided any package — - // that is, any module whose selected version was not "none" — may be - // relevant. - for _, m := range mg.BuildList() { - restrictTo(m) + // 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(ctx, rs, roots, selectedRoot) + if err != nil { + if mg == nil { + return rs, 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 rs.pruning == pruned { + summary, _ := mg.loadCache.Get(m) + if summary != nil && summary.pruning == unpruned { + return unpruned + } + } + return rs.pruning } - } else { - // The go.mod file explicitly records every module that provides a package - // imported by the main module. - // - // If we need to downgrade an existing root or a new root found in - // tryUpgrade, we don't want to allow that downgrade to incidentally upgrade - // a module imported by the main module to some arbitrary version. - // However, we don't particularly care about arbitrary upgrades to modules - // that are (at best) only providing packages imported by tests of - // dependencies outside the main module. - for _, m := range rs.rootModules { - restrictTo(module.Version{ - Path: m.Path, - Version: mg.Selected(m.Path), - }) + for _, m := range roots { + extendedRootPruning[m] = findPruning(m) + } + for m := range upgradedRoots { + extendedRootPruning[m] = findPruning(m) } - } - - if err := raiseLimitsForUpgrades(ctx, maxVersion, rs.pruning, tryUpgrade, mustSelect); err != nil { - return nil, err - } - // The versions in mustSelect override whatever we would naively select — - // we will downgrade other modules as needed in order to meet them. - for _, m := range mustSelect { - restrictTo(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 && cmpVersion(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 + } - return newVersionLimiter(rs.pruning, maxVersion), nil -} + 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 + } -// raiseLimitsForUpgrades increases the module versions in maxVersions to the -// versions that would be needed to allow each of the modules in tryUpgrade -// (individually or in any combination) and all of the modules in mustSelect -// (simultaneously) to be added as roots. -// -// Versions not present in maxVersion are unrestricted, and it is assumed that -// they will not be promoted to root requirements (and thus will not contribute -// their own dependencies if the main module supports graph pruning). -// -// These limits provide an upper bound on how far a module may be upgraded as -// part of an incidental downgrade, if downgrades are needed in order to select -// the versions in mustSelect. -func raiseLimitsForUpgrades(ctx context.Context, maxVersion map[string]string, pruning modPruning, tryUpgrade []module.Version, mustSelect []module.Version) error { - // allow raises the limit for m.Path to at least m.Version. - // If m.Path was already unrestricted, it remains unrestricted. - allow := func(m module.Version) { - v, ok := maxVersion[m.Path] - if !ok { - return // m.Path is unrestricted. - } - if cmpVersion(v, m.Version) < 0 { - maxVersion[m.Path] = m.Version - } - } + 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 + } - var ( - unprunedUpgrades []module.Version - isPrunedRootPath map[string]bool - ) - if pruning == unpruned { - unprunedUpgrades = tryUpgrade - } else { - isPrunedRootPath = make(map[string]bool, len(maxVersion)) - for p := range maxVersion { - isPrunedRootPath[p] = true - } - for _, m := range tryUpgrade { - isPrunedRootPath[m.Path] = true - } - for _, m := range mustSelect { - isPrunedRootPath[m.Path] = true - } + 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 + } - allowedRoot := map[module.Version]bool{} + // 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 && cmpVersion(r.Version, max) > 0 { + t.disqualify(m, pruned, dqState{dep: r}) + return + } + } + for _, r := range reqs { + if !t.require(m, r) { + break + } + } + }) - var allowRoot func(m module.Version) error - allowRoot = func(m module.Version) error { - if allowedRoot[m] { - return nil + // 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. } - allowedRoot[m] = true - if MainModules.Contains(m.Path) { - // The main module versions are already considered to be higher than any - // possible m, so m cannot be selected as a root and there is no point - // scanning its dependencies. - return nil + // 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, + } } - allow(m) + 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 + } - summary, err := goModSummary(m) - if err != nil { - return err + // 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 + } } - if summary.pruning == unpruned { - // For efficiency, we'll load all of the unpruned upgrades as one big - // graph, rather than loading the (potentially-overlapping) subgraph for - // each upgrade individually. - unprunedUpgrades = append(unprunedUpgrades, m) - return nil + + // 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, _ := rs.Graph(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 } - for _, r := range summary.require { - if isPrunedRootPath[r.Path] { - // r could become a root as the result of an upgrade or downgrade, - // in which case its dependencies will not be pruned out. - // We need to allow those dependencies to be upgraded too. - if err := allowRoot(r); err != nil { - return err + + // 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(ctx, prev) + if cmpVersion(m.Version, origV) > 0 && (cmpVersion(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 rs, 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 := rs.pruning + 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 { - // r will not become a root, so its dependencies don't matter. - // Allow only r itself. - allow(r) + action = fmt.Sprintf("trying %s", prev) } + fmt.Fprintf(os.Stderr, "go: %s\n\t%s\n", conflict.Summary(), action) } - return nil } - - for _, m := range tryUpgrade { - allowRoot(m) + if rootsDirty { + continue } - } - if len(unprunedUpgrades) > 0 { - // Compute the max versions for unpruned upgrades all together. - // Since these modules are unpruned, we'll end up scanning all of their - // transitive dependencies no matter which versions end up selected, - // and since we have a large dependency graph to scan we might get - // a significant benefit from not revisiting dependencies that are at - // common versions among multiple upgrades. - upgradeGraph, err := readModGraph(ctx, unpruned, unprunedUpgrades) - if err != nil { - // Compute the requirement path from a module path in tryUpgrade to the - // error, and the requirement path (if any) from rs.rootModules to the - // tryUpgrade module path. Return a *mvs.BuildListError showing the - // concatenation of the paths (with an upgrade in the middle). - return err + // 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 + } + } } - - for _, r := range upgradeGraph.BuildList() { - // Upgrading to m would upgrade to r, and the caller requested that we - // try to upgrade to m, so it's ok to upgrade to r. - allow(r) + if rootsDirty { + if cfg.BuildV { + module.Sort(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 rs, false, &ConstraintError{Conflicts: conflicts} } - // Explicitly allow any (transitive) upgrades implied by mustSelect. - nextRoots := append([]module.Version(nil), mustSelect...) - for nextRoots != nil { - module.Sort(nextRoots) - rs := newRequirements(pruning, nextRoots, nil) - nextRoots = nil - - rs, mustGraph, err := expandGraph(ctx, rs) - if err != nil { - return err - } - - for _, r := range mustGraph.BuildList() { - // Some module in mustSelect requires r, so we must allow at least - // r.Version (unless it conflicts with another entry in mustSelect, in - // which case we will error out either way). - allow(r) - - if isPrunedRootPath[r.Path] { - if v, ok := rs.rootSelected(r.Path); ok && r.Version == v { - // r is already a root, so its requirements are already included in - // the build list. - continue - } + if rs.pruning == 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 dependencies in mustSelect may upgrade (or downgrade) an existing - // root to match r, which will remain as a root. However, since r is not - // a root of rs, its dependencies have been pruned out of this build - // list. We need to add it back explicitly so that we allow any - // transitive upgrades that r will pull in. - if nextRoots == nil { - nextRoots = rs.rootModules // already capped - } - nextRoots = append(nextRoots, r) + // The modules in mustSelect are always promoted to be explicit. + for _, m := range mustSelect { + if m.Version != "none" && !MainModules.Contains(m.Path) { + rootPaths = append(rootPaths, m.Path) } } - } - - return nil -} -// selectPotentiallyImportedModules increases the limiter-selected version of -// every module in rs that potentially provides a package imported (directly or -// indirectly) by the main module, and every module in tryUpgrade, toward the -// highest version seen in rs or tryUpgrade, but not above the maximums enforced -// by the limiter. -// -// It returns the list of module versions selected by the limiter, sorted by -// path, along with a boolean indicating whether that list is different from the -// list of modules read from rs. -func selectPotentiallyImportedModules(ctx context.Context, limiter *versionLimiter, rs *Requirements, tryUpgrade []module.Version) (mods []module.Version, changed bool, err error) { - for _, m := range tryUpgrade { - if err := limiter.UpgradeToward(ctx, m); err != nil { - return nil, false, err + for _, m := range roots { + if v, ok := rs.rootSelected(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) + } } - } - var initial []module.Version - if rs.pruning == unpruned { - mg, err := rs.Graph(ctx) + roots, err = mvs.Req(MainModules.mustGetSingleMainModule(), rootPaths, &mvsReqs{roots: roots}) if err != nil { return nil, false, err } - initial = mg.BuildList()[MainModules.Len():] - } else { - initial = rs.rootModules } - for _, m := range initial { - if err := limiter.UpgradeToward(ctx, m); err != nil { - return nil, false, err - } + + changed = !slices.Equal(roots, rs.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 rs, false, nil } - mods = make([]module.Version, 0, len(limiter.selected)) - for path, v := range limiter.selected { - if v != "none" && !MainModules.Contains(path) { - mods = append(mods, module.Version{Path: path, Version: v}) + // 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 } } + return newRequirements(rs.pruning, roots, direct), changed, nil +} - // We've identified acceptable versions for each of the modules, but those - // versions are not necessarily consistent with each other: one upgraded or - // downgraded module may require a higher (but still allowed) version of - // another. The lower version may require extraneous dependencies that aren't - // actually relevant, so we need to compute the actual selected versions. - mg, err := readModGraph(ctx, rs.pruning, mods) - if err != nil { - return nil, false, err - } - mods = make([]module.Version, 0, len(limiter.selected)) - for path, _ := range limiter.selected { - if !MainModules.Contains(path) { - if v := mg.Selected(path); v != "none" { - mods = append(mods, module.Version{Path: path, Version: v}) +// 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(ctx context.Context, rs *Requirements, roots []module.Version, selectedRoot map[string]string) (mg *ModuleGraph, upgradedRoot map[module.Version]bool, err error) { + for { + mg, err = readModGraph(ctx, rs.pruning, 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 rs.pruning == 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 + } } - module.Sort(mods) - changed = !reflect.DeepEqual(mods, initial) + return mg, upgradedRoot, err +} - return mods, changed, err +type perPruning[T any] struct { + pruned T + unpruned T } -// A versionLimiter tracks the versions that may be selected for each module -// subject to constraints on the maximum versions of transitive dependencies. -type versionLimiter struct { - // pruning is the pruning at which the dependencies of the modules passed to - // Select and UpgradeToward are loaded. - pruning modPruning +func (pp perPruning[T]) from(p modPruning) T { + if p == unpruned { + return pp.unpruned + } + return pp.pruned +} - // max maps each module path to the maximum version that may be selected for - // that path. - // - // Paths with no entry are unrestricted, and we assume that they will not be - // promoted to root dependencies (so will not contribute dependencies if the - // main module supports graph pruning). - max map[string]string - - // selected maps each module path to a version of that path (if known) whose - // transitive dependencies do not violate any max version. The version kept - // is the highest one found during any call to UpgradeToward for the given - // module path. - // - // If a higher acceptable version is found during a call to UpgradeToward for - // some *other* module path, that does not update the selected version. - // Ignoring those versions keeps the downgrades computed for two modules - // together close to the individual downgrades that would be computed for each - // module in isolation. (The only way one module can affect another is if the - // final downgraded version of the one module explicitly requires a higher - // version of the other.) - // - // Version "none" of every module is always known not to violate any max - // version, so paths at version "none" are omitted. - selected map[string]string +// 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 each encountered version is - // disqualified. - dqReason map[module.Version]dqState + // 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 directly require it. If that version becomes disqualified, the - // disqualification will be propagated to all of the versions in the list. + // 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 } @@ -460,178 +630,152 @@ type versionLimiter struct { // 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 - conflict module.Version // disqualified because the module (transitively) requires dep, which exceeds the maximum version constraint for its path + 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{} } -// newVersionLimiter returns a versionLimiter that restricts the module paths -// that appear as keys in max. -// -// max maps each module path to its maximum version; paths that are not present -// in the map are unrestricted. The limiter assumes that unrestricted paths will -// not be promoted to root dependencies. -// -// If module graph pruning is in effect, then if a module passed to -// UpgradeToward or Select supports pruning, its unrestricted dependencies are -// skipped when scanning requirements. -func newVersionLimiter(pruning modPruning, max map[string]string) *versionLimiter { - selected := make(map[string]string) - for _, m := range MainModules.Versions() { - selected[m.Path] = m.Version +func (dq dqState) String() string { + if dq.err != nil { + return dq.err.Error() } - return &versionLimiter{ - pruning: pruning, - max: max, - selected: selected, - dqReason: map[module.Version]dqState{}, - requiring: map[module.Version][]module.Version{}, + if dq.dep != (module.Version{}) { + return dq.dep.String() } + return "(no conflict)" } -// UpgradeToward attempts to upgrade the selected version of m.Path as close as -// possible to m.Version without violating l's maximum version limits. +// 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 module graph pruning is in effect and m itself supports pruning, the -// dependencies of unrestricted dependencies of m will not be followed. -func (l *versionLimiter) UpgradeToward(ctx context.Context, m module.Version) error { - selected, ok := l.selected[m.Path] - if ok { - if cmpVersion(selected, m.Version) >= 0 { - // The selected version is already at least m, so no upgrade is needed. - return nil - } - } else { - selected = "none" - } - - if l.check(m, l.pruning).isDisqualified() { - candidates, _, err := versions(ctx, m.Path, CheckAllowed) - if err != nil { - // This is likely a transient error reaching the repository, - // rather than a permanent error with the retrieved version. - // - // TODO(golang.org/issue/31730, golang.org/issue/30134): - // decode what to do based on the actual error. - return err - } +// 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 dependant 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 +} - // Skip to candidates < m.Version. - i := sort.Search(len(candidates), func(i int) bool { - return semver.Compare(candidates[i], m.Version) >= 0 - }) - candidates = candidates[:i] - - for l.check(m, l.pruning).isDisqualified() { - n := len(candidates) - if n == 0 || cmpVersion(selected, candidates[n-1]) >= 0 { - // We couldn't find a suitable candidate above the already-selected version. - // Retain that version unmodified. - return nil - } - m.Version, candidates = candidates[n-1], candidates[:n-1] +// 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) } - - l.selected[m.Path] = m.Version - return nil } -// Select attempts to set the selected version of m.Path to exactly m.Version. -func (l *versionLimiter) Select(m module.Version) (conflict module.Version, err error) { - dq := l.check(m, l.pruning) - if !dq.isDisqualified() { - l.selected[m.Path] = m.Version - } - return dq.conflict, dq.err +// 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) } -// check determines whether m (or its transitive dependencies) would violate l's -// maximum version limits if added to the module requirement graph. +// 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 pruning is in effect and m itself supports graph pruning, the dependencies -// of unrestricted dependencies of m will not be followed. If the graph-pruning -// invariants hold for the main module up to this point, the packages in those -// modules are at best only imported by tests of dependencies that are -// themselves loaded from outside modules. Although we would like to keep -// 'go test all' as reproducible as is feasible, we don't want to retain test -// dependencies that are only marginally relevant at best. -func (l *versionLimiter) check(m module.Version, pruning modPruning) dqState { - if m.Version == "none" || m == MainModules.mustGetSingleMainModule() { - // version "none" has no requirements, and the dependencies of Target are - // tautological. - return dqState{} - } - - if dq, seen := l.dqReason[m]; seen { - return dq - } - l.dqReason[m] = dqState{} - - if max, ok := l.max[m.Path]; ok && cmpVersion(m.Version, max) > 0 { - return l.disqualify(m, dqState{conflict: m}) - } - - summary, err := goModSummary(m) - if err != nil { - // If we can't load the requirements, we couldn't load the go.mod file. - // There are a number of reasons this can happen, but this usually - // means an older version of the module had a missing or invalid - // go.mod file. For example, if example.com/mod released v2.0.0 before - // migrating to modules (v2.0.0+incompatible), then added a valid go.mod - // in v2.0.1, downgrading from v2.0.1 would cause this error. - // - // TODO(golang.org/issue/31730, golang.org/issue/30134): if the error - // is transient (we couldn't download go.mod), return the error from - // Downgrade. Currently, we can't tell what kind of error it is. - return l.disqualify(m, dqState{err: err}) - } - - if summary.pruning == unpruned { - pruning = unpruned - } - for _, r := range summary.require { - if pruning == pruned { - if _, restricted := l.max[r.Path]; !restricted { - // r.Path is unrestricted, so we don't care at what version it is - // selected. We assume that r.Path will not become a root dependency, so - // since m supports pruning, r's dependencies won't be followed. - continue - } +// If m is not disqualified, path returns (nil, nil). +func (t *dqTracker) path(m module.Version, pruning modPruning) (path []module.Version, err error) { + for { + dq := t.dqReason[m].from(pruning) + if !dq.isDisqualified() { + return path, nil } - - if dq := l.check(r, pruning); dq.isDisqualified() { - return l.disqualify(m, dq) + path = append(path, m) + if dq.err != nil || dq.dep == m { + return path, dq.err // m itself is the conflict. } - - // r and its dependencies are (perhaps provisionally) ok. - // - // However, if there are cycles in the requirement graph, we may have only - // checked a portion of the requirement graph so far, and r (and thus m) may - // yet be disqualified by some path we have not yet visited. Remember this edge - // so that we can disqualify m and its dependents if that occurs. - l.requiring[r] = append(l.requiring[r], m) - } - - return dqState{} -} - -// disqualify records that m (or one of its transitive dependencies) -// violates l's maximum version limits. -func (l *versionLimiter) disqualify(m module.Version, dq dqState) dqState { - if dq := l.dqReason[m]; dq.isDisqualified() { - return dq - } - l.dqReason[m] = dq - - for _, p := range l.requiring[m] { - l.disqualify(p, dqState{conflict: m}) + m = dq.dep } - // Now that we have disqualified the modules that depend on m, we can forget - // about them — we won't need to disqualify them again. - delete(l.requiring, m) - return dq } diff --git a/src/cmd/go/internal/modload/modfile.go b/src/cmd/go/internal/modload/modfile.go index 79ec530caa..8e8622982d 100644 --- a/src/cmd/go/internal/modload/modfile.go +++ b/src/cmd/go/internal/modload/modfile.go @@ -130,6 +130,19 @@ const ( workspace // pruned to the union of modules in the workspace ) +func (p modPruning) String() string { + switch p { + case pruned: + return "pruned" + case unpruned: + return "unpruned" + case workspace: + return "workspace" + default: + return fmt.Sprintf("%T(%d)", p, p) + } +} + func pruningForGoVersion(goVersion string) modPruning { if semver.Compare("v"+goVersion, ExplicitIndirectVersionV) < 0 { // The go.mod file does not duplicate relevant information about transitive @@ -661,7 +674,6 @@ func goModSummary(m module.Version) (*modFileSummary, error) { // its dependencies. // // rawGoModSummary cannot be used on the Target module. - func rawGoModSummary(m module.Version) (*modFileSummary, error) { if m.Path == "" && MainModules.Contains(m.Path) { panic("internal error: rawGoModSummary called on the Target module") diff --git a/src/cmd/go/internal/modload/mvs.go b/src/cmd/go/internal/modload/mvs.go index ea1c21b4f1..b4d0cf23a6 100644 --- a/src/cmd/go/internal/modload/mvs.go +++ b/src/cmd/go/internal/modload/mvs.go @@ -111,14 +111,12 @@ func versions(ctx context.Context, path string, allowed AllowedFunc) (versions [ // // Since the version of a main module is not found in the version list, // it has no previous version. -func previousVersion(m module.Version) (module.Version, error) { - // TODO(golang.org/issue/38714): thread tracing context through MVS. - +func previousVersion(ctx context.Context, m module.Version) (module.Version, error) { if m.Version == "" && MainModules.Contains(m.Path) { return module.Version{Path: m.Path, Version: "none"}, nil } - list, _, err := versions(context.TODO(), m.Path, CheckAllowed) + list, _, err := versions(ctx, m.Path, CheckAllowed) if err != nil { if errors.Is(err, os.ErrNotExist) { return module.Version{Path: m.Path, Version: "none"}, nil @@ -133,5 +131,6 @@ func previousVersion(m module.Version) (module.Version, error) { } func (*mvsReqs) Previous(m module.Version) (module.Version, error) { - return previousVersion(m) + // TODO(golang.org/issue/38714): thread tracing context through MVS. + return previousVersion(context.TODO(), m) } |