Source file src/cmd/go/internal/modload/edit.go
1 // Copyright 2021 The Go Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style 3 // license that can be found in the LICENSE file. 4 5 package modload 6 7 import ( 8 "cmd/go/internal/mvs" 9 "context" 10 "reflect" 11 "sort" 12 13 "golang.org/x/mod/module" 14 "golang.org/x/mod/semver" 15 ) 16 17 // editRequirements returns an edited version of rs such that: 18 // 19 // 1. Each module version in mustSelect is selected. 20 // 21 // 2. Each module version in tryUpgrade is upgraded toward the indicated 22 // version as far as can be done without violating (1). 23 // 24 // 3. Each module version in rs.rootModules (or rs.graph, if rs is unpruned) 25 // is downgraded from its original version only to the extent needed to 26 // satisfy (1), or upgraded only to the extent needed to satisfy (1) and 27 // (2). 28 // 29 // 4. No module is upgraded above the maximum version of its path found in the 30 // dependency graph of rs, the combined dependency graph of the versions in 31 // mustSelect, or the dependencies of each individual module version in 32 // tryUpgrade. 33 // 34 // Generally, the module versions in mustSelect are due to the module or a 35 // package within the module matching an explicit command line argument to 'go 36 // get', and the versions in tryUpgrade are transitive dependencies that are 37 // either being upgraded by 'go get -u' or being added to satisfy some 38 // otherwise-missing package import. 39 func editRequirements(ctx context.Context, rs *Requirements, tryUpgrade, mustSelect []module.Version) (edited *Requirements, changed bool, err error) { 40 limiter, err := limiterForEdit(ctx, rs, tryUpgrade, mustSelect) 41 if err != nil { 42 return rs, false, err 43 } 44 45 var conflicts []Conflict 46 for _, m := range mustSelect { 47 conflict, err := limiter.Select(m) 48 if err != nil { 49 return rs, false, err 50 } 51 if conflict.Path != "" { 52 conflicts = append(conflicts, Conflict{ 53 Source: m, 54 Dep: conflict, 55 Constraint: module.Version{ 56 Path: conflict.Path, 57 Version: limiter.max[conflict.Path], 58 }, 59 }) 60 } 61 } 62 if len(conflicts) > 0 { 63 return rs, false, &ConstraintError{Conflicts: conflicts} 64 } 65 66 mods, changed, err := selectPotentiallyImportedModules(ctx, limiter, rs, tryUpgrade) 67 if err != nil { 68 return rs, false, err 69 } 70 71 var roots []module.Version 72 if rs.pruning == unpruned { 73 // In a module without graph pruning, modules that provide packages imported 74 // by the main module may either be explicit roots or implicit transitive 75 // dependencies. We promote the modules in mustSelect to be explicit 76 // requirements. 77 var rootPaths []string 78 for _, m := range mustSelect { 79 if m.Version != "none" && !MainModules.Contains(m.Path) { 80 rootPaths = append(rootPaths, m.Path) 81 } 82 } 83 if !changed && len(rootPaths) == 0 { 84 // The build list hasn't changed and we have no new roots to add. 85 // We don't need to recompute the minimal roots for the module. 86 return rs, false, nil 87 } 88 89 for _, m := range mods { 90 if v, ok := rs.rootSelected(m.Path); ok && (v == m.Version || rs.direct[m.Path]) { 91 // m.Path was formerly a root, and either its version hasn't changed or 92 // we believe that it provides a package directly imported by a package 93 // or test in the main module. For now we'll assume that it is still 94 // relevant enough to remain a root. If we actually load all of the 95 // packages and tests in the main module (which we are not doing here), 96 // we can revise the explicit roots at that point. 97 rootPaths = append(rootPaths, m.Path) 98 } 99 } 100 101 roots, err = mvs.Req(MainModules.mustGetSingleMainModule(), rootPaths, &mvsReqs{roots: mods}) 102 if err != nil { 103 return nil, false, err 104 } 105 } else { 106 // In a module with a pruned graph, every module that provides a package 107 // imported by the main module must be retained as a root. 108 roots = mods 109 if !changed { 110 // Because the roots we just computed are unchanged, the entire graph must 111 // be the same as it was before. Save the original rs, since we have 112 // probably already loaded its requirement graph. 113 return rs, false, nil 114 } 115 } 116 117 // A module that is not even in the build list necessarily cannot provide 118 // any imported packages. Mark as direct only the direct modules that are 119 // still in the build list. 120 // 121 // TODO(bcmills): Would it make more sense to leave the direct map as-is 122 // but allow it to refer to modules that are no longer in the build list? 123 // That might complicate updateRoots, but it may be cleaner in other ways. 124 direct := make(map[string]bool, len(rs.direct)) 125 for _, m := range roots { 126 if rs.direct[m.Path] { 127 direct[m.Path] = true 128 } 129 } 130 return newRequirements(rs.pruning, roots, direct), changed, nil 131 } 132 133 // limiterForEdit returns a versionLimiter with its max versions set such that 134 // the max version for every module path in mustSelect is the version listed 135 // there, and the max version for every other module path is the maximum version 136 // of its path found in the dependency graph of rs, the combined dependency 137 // graph of the versions in mustSelect, or the dependencies of each individual 138 // module version in tryUpgrade. 139 func limiterForEdit(ctx context.Context, rs *Requirements, tryUpgrade, mustSelect []module.Version) (*versionLimiter, error) { 140 mg, err := rs.Graph(ctx) 141 if err != nil { 142 return nil, err 143 } 144 145 maxVersion := map[string]string{} // module path → version 146 restrictTo := func(m module.Version) { 147 v, ok := maxVersion[m.Path] 148 if !ok || cmpVersion(v, m.Version) > 0 { 149 maxVersion[m.Path] = m.Version 150 } 151 } 152 153 if rs.pruning == unpruned { 154 // go.mod files that do not support graph pruning don't indicate which 155 // transitive dependencies are actually relevant to the main module, so we 156 // have to assume that any module that could have provided any package — 157 // that is, any module whose selected version was not "none" — may be 158 // relevant. 159 for _, m := range mg.BuildList() { 160 restrictTo(m) 161 } 162 } else { 163 // The go.mod file explicitly records every module that provides a package 164 // imported by the main module. 165 // 166 // If we need to downgrade an existing root or a new root found in 167 // tryUpgrade, we don't want to allow that downgrade to incidentally upgrade 168 // a module imported by the main module to some arbitrary version. 169 // However, we don't particularly care about arbitrary upgrades to modules 170 // that are (at best) only providing packages imported by tests of 171 // dependencies outside the main module. 172 for _, m := range rs.rootModules { 173 restrictTo(module.Version{ 174 Path: m.Path, 175 Version: mg.Selected(m.Path), 176 }) 177 } 178 } 179 180 if err := raiseLimitsForUpgrades(ctx, maxVersion, rs.pruning, tryUpgrade, mustSelect); err != nil { 181 return nil, err 182 } 183 184 // The versions in mustSelect override whatever we would naively select — 185 // we will downgrade other modules as needed in order to meet them. 186 for _, m := range mustSelect { 187 restrictTo(m) 188 } 189 190 return newVersionLimiter(rs.pruning, maxVersion), nil 191 } 192 193 // raiseLimitsForUpgrades increases the module versions in maxVersions to the 194 // versions that would be needed to allow each of the modules in tryUpgrade 195 // (individually or in any combination) and all of the modules in mustSelect 196 // (simultaneously) to be added as roots. 197 // 198 // Versions not present in maxVersion are unrestricted, and it is assumed that 199 // they will not be promoted to root requirements (and thus will not contribute 200 // their own dependencies if the main module supports graph pruning). 201 // 202 // These limits provide an upper bound on how far a module may be upgraded as 203 // part of an incidental downgrade, if downgrades are needed in order to select 204 // the versions in mustSelect. 205 func raiseLimitsForUpgrades(ctx context.Context, maxVersion map[string]string, pruning modPruning, tryUpgrade []module.Version, mustSelect []module.Version) error { 206 // allow raises the limit for m.Path to at least m.Version. 207 // If m.Path was already unrestricted, it remains unrestricted. 208 allow := func(m module.Version) { 209 v, ok := maxVersion[m.Path] 210 if !ok { 211 return // m.Path is unrestricted. 212 } 213 if cmpVersion(v, m.Version) < 0 { 214 maxVersion[m.Path] = m.Version 215 } 216 } 217 218 var ( 219 unprunedUpgrades []module.Version 220 isPrunedRootPath map[string]bool 221 ) 222 if pruning == unpruned { 223 unprunedUpgrades = tryUpgrade 224 } else { 225 isPrunedRootPath = make(map[string]bool, len(maxVersion)) 226 for p := range maxVersion { 227 isPrunedRootPath[p] = true 228 } 229 for _, m := range tryUpgrade { 230 isPrunedRootPath[m.Path] = true 231 } 232 for _, m := range mustSelect { 233 isPrunedRootPath[m.Path] = true 234 } 235 236 allowedRoot := map[module.Version]bool{} 237 238 var allowRoot func(m module.Version) error 239 allowRoot = func(m module.Version) error { 240 if allowedRoot[m] { 241 return nil 242 } 243 allowedRoot[m] = true 244 245 if MainModules.Contains(m.Path) { 246 // The main module versions are already considered to be higher than any 247 // possible m, so m cannot be selected as a root and there is no point 248 // scanning its dependencies. 249 return nil 250 } 251 252 allow(m) 253 254 summary, err := goModSummary(m) 255 if err != nil { 256 return err 257 } 258 if summary.pruning == unpruned { 259 // For efficiency, we'll load all of the unpruned upgrades as one big 260 // graph, rather than loading the (potentially-overlapping) subgraph for 261 // each upgrade individually. 262 unprunedUpgrades = append(unprunedUpgrades, m) 263 return nil 264 } 265 for _, r := range summary.require { 266 if isPrunedRootPath[r.Path] { 267 // r could become a root as the result of an upgrade or downgrade, 268 // in which case its dependencies will not be pruned out. 269 // We need to allow those dependencies to be upgraded too. 270 if err := allowRoot(r); err != nil { 271 return err 272 } 273 } else { 274 // r will not become a root, so its dependencies don't matter. 275 // Allow only r itself. 276 allow(r) 277 } 278 } 279 return nil 280 } 281 282 for _, m := range tryUpgrade { 283 allowRoot(m) 284 } 285 } 286 287 if len(unprunedUpgrades) > 0 { 288 // Compute the max versions for unpruned upgrades all together. 289 // Since these modules are unpruned, we'll end up scanning all of their 290 // transitive dependencies no matter which versions end up selected, 291 // and since we have a large dependency graph to scan we might get 292 // a significant benefit from not revisiting dependencies that are at 293 // common versions among multiple upgrades. 294 upgradeGraph, err := readModGraph(ctx, unpruned, unprunedUpgrades) 295 if err != nil { 296 // Compute the requirement path from a module path in tryUpgrade to the 297 // error, and the requirement path (if any) from rs.rootModules to the 298 // tryUpgrade module path. Return a *mvs.BuildListError showing the 299 // concatenation of the paths (with an upgrade in the middle). 300 return err 301 } 302 303 for _, r := range upgradeGraph.BuildList() { 304 // Upgrading to m would upgrade to r, and the caller requested that we 305 // try to upgrade to m, so it's ok to upgrade to r. 306 allow(r) 307 } 308 } 309 310 // Explicitly allow any (transitive) upgrades implied by mustSelect. 311 nextRoots := append([]module.Version(nil), mustSelect...) 312 for nextRoots != nil { 313 module.Sort(nextRoots) 314 rs := newRequirements(pruning, nextRoots, nil) 315 nextRoots = nil 316 317 rs, mustGraph, err := expandGraph(ctx, rs) 318 if err != nil { 319 return err 320 } 321 322 for _, r := range mustGraph.BuildList() { 323 // Some module in mustSelect requires r, so we must allow at least 324 // r.Version (unless it conflicts with another entry in mustSelect, in 325 // which case we will error out either way). 326 allow(r) 327 328 if isPrunedRootPath[r.Path] { 329 if v, ok := rs.rootSelected(r.Path); ok && r.Version == v { 330 // r is already a root, so its requirements are already included in 331 // the build list. 332 continue 333 } 334 335 // The dependencies in mustSelect may upgrade (or downgrade) an existing 336 // root to match r, which will remain as a root. However, since r is not 337 // a root of rs, its dependencies have been pruned out of this build 338 // list. We need to add it back explicitly so that we allow any 339 // transitive upgrades that r will pull in. 340 if nextRoots == nil { 341 nextRoots = rs.rootModules // already capped 342 } 343 nextRoots = append(nextRoots, r) 344 } 345 } 346 } 347 348 return nil 349 } 350 351 // selectPotentiallyImportedModules increases the limiter-selected version of 352 // every module in rs that potentially provides a package imported (directly or 353 // indirectly) by the main module, and every module in tryUpgrade, toward the 354 // highest version seen in rs or tryUpgrade, but not above the maximums enforced 355 // by the limiter. 356 // 357 // It returns the list of module versions selected by the limiter, sorted by 358 // path, along with a boolean indicating whether that list is different from the 359 // list of modules read from rs. 360 func selectPotentiallyImportedModules(ctx context.Context, limiter *versionLimiter, rs *Requirements, tryUpgrade []module.Version) (mods []module.Version, changed bool, err error) { 361 for _, m := range tryUpgrade { 362 if err := limiter.UpgradeToward(ctx, m); err != nil { 363 return nil, false, err 364 } 365 } 366 367 var initial []module.Version 368 if rs.pruning == unpruned { 369 mg, err := rs.Graph(ctx) 370 if err != nil { 371 return nil, false, err 372 } 373 initial = mg.BuildList()[MainModules.Len():] 374 } else { 375 initial = rs.rootModules 376 } 377 for _, m := range initial { 378 if err := limiter.UpgradeToward(ctx, m); err != nil { 379 return nil, false, err 380 } 381 } 382 383 mods = make([]module.Version, 0, len(limiter.selected)) 384 for path, v := range limiter.selected { 385 if v != "none" && !MainModules.Contains(path) { 386 mods = append(mods, module.Version{Path: path, Version: v}) 387 } 388 } 389 390 // We've identified acceptable versions for each of the modules, but those 391 // versions are not necessarily consistent with each other: one upgraded or 392 // downgraded module may require a higher (but still allowed) version of 393 // another. The lower version may require extraneous dependencies that aren't 394 // actually relevant, so we need to compute the actual selected versions. 395 mg, err := readModGraph(ctx, rs.pruning, mods) 396 if err != nil { 397 return nil, false, err 398 } 399 mods = make([]module.Version, 0, len(limiter.selected)) 400 for path, _ := range limiter.selected { 401 if !MainModules.Contains(path) { 402 if v := mg.Selected(path); v != "none" { 403 mods = append(mods, module.Version{Path: path, Version: v}) 404 } 405 } 406 } 407 module.Sort(mods) 408 409 changed = !reflect.DeepEqual(mods, initial) 410 411 return mods, changed, err 412 } 413 414 // A versionLimiter tracks the versions that may be selected for each module 415 // subject to constraints on the maximum versions of transitive dependencies. 416 type versionLimiter struct { 417 // pruning is the pruning at which the dependencies of the modules passed to 418 // Select and UpgradeToward are loaded. 419 pruning modPruning 420 421 // max maps each module path to the maximum version that may be selected for 422 // that path. 423 // 424 // Paths with no entry are unrestricted, and we assume that they will not be 425 // promoted to root dependencies (so will not contribute dependencies if the 426 // main module supports graph pruning). 427 max map[string]string 428 429 // selected maps each module path to a version of that path (if known) whose 430 // transitive dependencies do not violate any max version. The version kept 431 // is the highest one found during any call to UpgradeToward for the given 432 // module path. 433 // 434 // If a higher acceptable version is found during a call to UpgradeToward for 435 // some *other* module path, that does not update the selected version. 436 // Ignoring those versions keeps the downgrades computed for two modules 437 // together close to the individual downgrades that would be computed for each 438 // module in isolation. (The only way one module can affect another is if the 439 // final downgraded version of the one module explicitly requires a higher 440 // version of the other.) 441 // 442 // Version "none" of every module is always known not to violate any max 443 // version, so paths at version "none" are omitted. 444 selected map[string]string 445 446 // dqReason records whether and why each each encountered version is 447 // disqualified. 448 dqReason map[module.Version]dqState 449 450 // requiring maps each not-yet-disqualified module version to the versions 451 // that directly require it. If that version becomes disqualified, the 452 // disqualification will be propagated to all of the versions in the list. 453 requiring map[module.Version][]module.Version 454 } 455 456 // A dqState indicates whether and why a module version is “disqualified” from 457 // being used in a way that would incorporate its requirements. 458 // 459 // The zero dqState indicates that the module version is not known to be 460 // disqualified, either because it is ok or because we are currently traversing 461 // a cycle that includes it. 462 type dqState struct { 463 err error // if non-nil, disqualified because the requirements of the module could not be read 464 conflict module.Version // disqualified because the module (transitively) requires dep, which exceeds the maximum version constraint for its path 465 } 466 467 func (dq dqState) isDisqualified() bool { 468 return dq != dqState{} 469 } 470 471 // newVersionLimiter returns a versionLimiter that restricts the module paths 472 // that appear as keys in max. 473 // 474 // max maps each module path to its maximum version; paths that are not present 475 // in the map are unrestricted. The limiter assumes that unrestricted paths will 476 // not be promoted to root dependencies. 477 // 478 // If module graph pruning is in effect, then if a module passed to 479 // UpgradeToward or Select supports pruning, its unrestricted dependencies are 480 // skipped when scanning requirements. 481 func newVersionLimiter(pruning modPruning, max map[string]string) *versionLimiter { 482 selected := make(map[string]string) 483 for _, m := range MainModules.Versions() { 484 selected[m.Path] = m.Version 485 } 486 return &versionLimiter{ 487 pruning: pruning, 488 max: max, 489 selected: selected, 490 dqReason: map[module.Version]dqState{}, 491 requiring: map[module.Version][]module.Version{}, 492 } 493 } 494 495 // UpgradeToward attempts to upgrade the selected version of m.Path as close as 496 // possible to m.Version without violating l's maximum version limits. 497 // 498 // If module graph pruning is in effect and m itself supports pruning, the 499 // dependencies of unrestricted dependencies of m will not be followed. 500 func (l *versionLimiter) UpgradeToward(ctx context.Context, m module.Version) error { 501 selected, ok := l.selected[m.Path] 502 if ok { 503 if cmpVersion(selected, m.Version) >= 0 { 504 // The selected version is already at least m, so no upgrade is needed. 505 return nil 506 } 507 } else { 508 selected = "none" 509 } 510 511 if l.check(m, l.pruning).isDisqualified() { 512 candidates, err := versions(ctx, m.Path, CheckAllowed) 513 if err != nil { 514 // This is likely a transient error reaching the repository, 515 // rather than a permanent error with the retrieved version. 516 // 517 // TODO(golang.org/issue/31730, golang.org/issue/30134): 518 // decode what to do based on the actual error. 519 return err 520 } 521 522 // Skip to candidates < m.Version. 523 i := sort.Search(len(candidates), func(i int) bool { 524 return semver.Compare(candidates[i], m.Version) >= 0 525 }) 526 candidates = candidates[:i] 527 528 for l.check(m, l.pruning).isDisqualified() { 529 n := len(candidates) 530 if n == 0 || cmpVersion(selected, candidates[n-1]) >= 0 { 531 // We couldn't find a suitable candidate above the already-selected version. 532 // Retain that version unmodified. 533 return nil 534 } 535 m.Version, candidates = candidates[n-1], candidates[:n-1] 536 } 537 } 538 539 l.selected[m.Path] = m.Version 540 return nil 541 } 542 543 // Select attempts to set the selected version of m.Path to exactly m.Version. 544 func (l *versionLimiter) Select(m module.Version) (conflict module.Version, err error) { 545 dq := l.check(m, l.pruning) 546 if !dq.isDisqualified() { 547 l.selected[m.Path] = m.Version 548 } 549 return dq.conflict, dq.err 550 } 551 552 // check determines whether m (or its transitive dependencies) would violate l's 553 // maximum version limits if added to the module requirement graph. 554 // 555 // If pruning is in effect and m itself supports graph pruning, the dependencies 556 // of unrestricted dependencies of m will not be followed. If the graph-pruning 557 // invariants hold for the main module up to this point, the packages in those 558 // modules are at best only imported by tests of dependencies that are 559 // themselves loaded from outside modules. Although we would like to keep 560 // 'go test all' as reproducible as is feasible, we don't want to retain test 561 // dependencies that are only marginally relevant at best. 562 func (l *versionLimiter) check(m module.Version, pruning modPruning) dqState { 563 if m.Version == "none" || m == MainModules.mustGetSingleMainModule() { 564 // version "none" has no requirements, and the dependencies of Target are 565 // tautological. 566 return dqState{} 567 } 568 569 if dq, seen := l.dqReason[m]; seen { 570 return dq 571 } 572 l.dqReason[m] = dqState{} 573 574 if max, ok := l.max[m.Path]; ok && cmpVersion(m.Version, max) > 0 { 575 return l.disqualify(m, dqState{conflict: m}) 576 } 577 578 summary, err := goModSummary(m) 579 if err != nil { 580 // If we can't load the requirements, we couldn't load the go.mod file. 581 // There are a number of reasons this can happen, but this usually 582 // means an older version of the module had a missing or invalid 583 // go.mod file. For example, if example.com/mod released v2.0.0 before 584 // migrating to modules (v2.0.0+incompatible), then added a valid go.mod 585 // in v2.0.1, downgrading from v2.0.1 would cause this error. 586 // 587 // TODO(golang.org/issue/31730, golang.org/issue/30134): if the error 588 // is transient (we couldn't download go.mod), return the error from 589 // Downgrade. Currently, we can't tell what kind of error it is. 590 return l.disqualify(m, dqState{err: err}) 591 } 592 593 if summary.pruning == unpruned { 594 pruning = unpruned 595 } 596 for _, r := range summary.require { 597 if pruning == pruned { 598 if _, restricted := l.max[r.Path]; !restricted { 599 // r.Path is unrestricted, so we don't care at what version it is 600 // selected. We assume that r.Path will not become a root dependency, so 601 // since m supports pruning, r's dependencies won't be followed. 602 continue 603 } 604 } 605 606 if dq := l.check(r, pruning); dq.isDisqualified() { 607 return l.disqualify(m, dq) 608 } 609 610 // r and its dependencies are (perhaps provisionally) ok. 611 // 612 // However, if there are cycles in the requirement graph, we may have only 613 // checked a portion of the requirement graph so far, and r (and thus m) may 614 // yet be disqualified by some path we have not yet visited. Remember this edge 615 // so that we can disqualify m and its dependents if that occurs. 616 l.requiring[r] = append(l.requiring[r], m) 617 } 618 619 return dqState{} 620 } 621 622 // disqualify records that m (or one of its transitive dependencies) 623 // violates l's maximum version limits. 624 func (l *versionLimiter) disqualify(m module.Version, dq dqState) dqState { 625 if dq := l.dqReason[m]; dq.isDisqualified() { 626 return dq 627 } 628 l.dqReason[m] = dq 629 630 for _, p := range l.requiring[m] { 631 l.disqualify(p, dqState{conflict: m}) 632 } 633 // Now that we have disqualified the modules that depend on m, we can forget 634 // about them — we won't need to disqualify them again. 635 delete(l.requiring, m) 636 return dq 637 } 638