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