blob: c350b9d1b5c571ed0e0754a07ad58fa3c9b26fe9 [file] [log] [blame]
// 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 (
"cmd/go/internal/mvs"
"context"
"reflect"
"sort"
"golang.org/x/mod/module"
"golang.org/x/mod/semver"
)
// 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).
//
// 3. Each module version in rs.rootModules (or rs.graph, if rs.depth is eager)
// 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.
//
// 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.
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
}
var conflicts []Conflict
for _, m := range mustSelect {
conflict, err := limiter.Select(m)
if err != nil {
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],
},
})
}
}
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.depth == eager {
// In an eager module, 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" && m.Path != Target.Path {
rootPaths = append(rootPaths, m.Path)
}
}
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
}
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)
}
}
roots, err = mvs.Req(Target, rootPaths, &mvsReqs{roots: mods})
if err != nil {
return nil, false, err
}
} else {
// In a lazy module, 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
}
}
// 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.
//
// 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.depth, roots, direct), changed, nil
}
// 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
}
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
}
}
if rs.depth == eager {
// Eager go.mod files 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)
}
} 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),
})
}
}
if err := raiseLimitsForUpgrades(ctx, maxVersion, rs.depth, 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)
}
return newVersionLimiter(rs.depth, maxVersion), nil
}
// raiseLimitsForUpgrades increases the module versions in maxVersions to the
// versions that would be needed to allow each of the modules in tryUpgrade
// (individually) 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 is lazy).
//
// 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, depth modDepth, 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
}
}
var eagerUpgrades []module.Version
if depth == eager {
eagerUpgrades = tryUpgrade
} else {
for _, m := range tryUpgrade {
if m.Path == Target.Path {
// Target is already considered to be higher than any possible m, so we
// won't be upgrading to it anyway and there is no point scanning its
// dependencies.
continue
}
summary, err := goModSummary(m)
if err != nil {
return err
}
if summary.depth == eager {
// For efficiency, we'll load all of the eager upgrades as one big
// graph, rather than loading the (potentially-overlapping) subgraph for
// each upgrade individually.
eagerUpgrades = append(eagerUpgrades, m)
continue
}
for _, r := range summary.require {
allow(r)
}
}
}
if len(eagerUpgrades) > 0 {
// Compute the max versions for eager upgrades all together.
// Since these modules are eager, 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, eager, eagerUpgrades)
if err != nil {
if go117LazyTODO {
// 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
}
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 len(mustSelect) > 0 {
mustGraph, err := readModGraph(ctx, depth, mustSelect)
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 an entry in mustSelect.
allow(r)
}
}
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
}
}
var initial []module.Version
if rs.depth == eager {
mg, err := rs.Graph(ctx)
if err != nil {
return nil, false, err
}
initial = mg.BuildList()[1:]
} else {
initial = rs.rootModules
}
for _, m := range initial {
if err := limiter.UpgradeToward(ctx, m); err != nil {
return nil, false, err
}
}
mods = make([]module.Version, 0, len(limiter.selected))
for path, v := range limiter.selected {
if v != "none" && path != Target.Path {
mods = append(mods, module.Version{Path: path, Version: v})
}
}
// 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.depth, mods)
if err != nil {
return nil, false, err
}
mods = make([]module.Version, 0, len(limiter.selected))
for path, _ := range limiter.selected {
if path != Target.Path {
if v := mg.Selected(path); v != "none" {
mods = append(mods, module.Version{Path: path, Version: v})
}
}
}
module.Sort(mods)
changed = !reflect.DeepEqual(mods, initial)
return mods, changed, err
}
// 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 {
// depth is the depth at which the dependencies of the modules passed to
// Select and UpgradeToward are loaded.
depth modDepth
// 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 is lazy).
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
// dqReason records whether and why each each encountered version is
// disqualified.
dqReason map[module.Version]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.
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
conflict module.Version // disqualified because the module (transitively) requires dep, which exceeds the maximum version constraint for its path
}
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 depth is lazy, then if a module passed to UpgradeToward or Select is
// itself lazy, its unrestricted dependencies are skipped when scanning
// requirements.
func newVersionLimiter(depth modDepth, max map[string]string) *versionLimiter {
return &versionLimiter{
depth: depth,
max: max,
selected: map[string]string{Target.Path: Target.Version},
dqReason: map[module.Version]dqState{},
requiring: map[module.Version][]module.Version{},
}
}
// UpgradeToward attempts to upgrade the selected version of m.Path as close as
// possible to m.Version without violating l's maximum version limits.
//
// If depth is lazy and m itself is lazy, the 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.depth).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
}
// 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.depth).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]
}
}
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.depth)
if !dq.isDisqualified() {
l.selected[m.Path] = m.Version
}
return dq.conflict, dq.err
}
// check determines whether m (or its transitive dependencies) would violate l's
// maximum version limits if added to the module requirement graph.
//
// If depth is lazy and m itself is lazy, then the dependencies of unrestricted
// dependencies of m will not be followed. If the lazy loading 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, depth modDepth) dqState {
if m.Version == "none" || m == Target {
// 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.depth == eager {
depth = eager
}
for _, r := range summary.require {
if depth == lazy {
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 is lazy, r's dependencies won't be followed.
continue
}
}
if dq := l.check(r, depth); dq.isDisqualified() {
return l.disqualify(m, dq)
}
// 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})
}
// 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
}