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/cfg" 9 "cmd/go/internal/gover" 10 "cmd/go/internal/mvs" 11 "cmd/go/internal/par" 12 "context" 13 "errors" 14 "fmt" 15 "maps" 16 "os" 17 "slices" 18 19 "golang.org/x/mod/module" 20 ) 21 22 // editRequirements returns an edited version of rs such that: 23 // 24 // 1. Each module version in mustSelect is selected. 25 // 26 // 2. Each module version in tryUpgrade is upgraded toward the indicated 27 // version as far as can be done without violating (1). 28 // (Other upgrades are also allowed if they are caused by 29 // transitive requirements of versions in mustSelect or 30 // tryUpgrade.) 31 // 32 // 3. Each module version in rs.rootModules (or rs.graph, if rs is unpruned) 33 // is downgraded or upgraded from its original version only to the extent 34 // needed to satisfy (1) and (2). 35 // 36 // Generally, the module versions in mustSelect are due to the module or a 37 // package within the module matching an explicit command line argument to 'go 38 // get', and the versions in tryUpgrade are transitive dependencies that are 39 // either being upgraded by 'go get -u' or being added to satisfy some 40 // otherwise-missing package import. 41 // 42 // If pruning is enabled, the roots of the edited requirements include an 43 // explicit entry for each module path in tryUpgrade, mustSelect, and the roots 44 // of rs, unless the selected version for the module path is "none". 45 func editRequirements(ctx context.Context, rs *Requirements, tryUpgrade, mustSelect []module.Version) (edited *Requirements, changed bool, err error) { 46 if rs.pruning == workspace { 47 panic("editRequirements cannot edit workspace requirements") 48 } 49 50 orig := rs 51 // If we already know what go version we will end up on after the edit, and 52 // the pruning for that version is different, go ahead and apply it now. 53 // 54 // If we are changing from pruned to unpruned, then we MUST check the unpruned 55 // graph for conflicts from the start. (Checking only for pruned conflicts 56 // would miss some that would be introduced later.) 57 // 58 // If we are changing from unpruned to pruned, then we would like to avoid 59 // unnecessary downgrades due to conflicts that would be pruned out of the 60 // final graph anyway. 61 // 62 // Note that even if we don't find a go version in mustSelect, it is possible 63 // that we will switch from unpruned to pruned (but not the other way around!) 64 // after applying the edits if we find a dependency that requires a high 65 // enough go version to trigger an upgrade. 66 rootPruning := orig.pruning 67 for _, m := range mustSelect { 68 if m.Path == "go" { 69 rootPruning = pruningForGoVersion(m.Version) 70 break 71 } else if m.Path == "toolchain" && pruningForGoVersion(gover.FromToolchain(m.Version)) == unpruned { 72 // We don't know exactly what go version we will end up at, but we know 73 // that it must be a version supported by the requested toolchain, and 74 // that toolchain does not support pruning. 75 // 76 // TODO(bcmills): 'go get' ought to reject explicit toolchain versions 77 // older than gover.GoStrictVersion. Once that is fixed, is this still 78 // needed? 79 rootPruning = unpruned 80 break 81 } 82 } 83 84 if rootPruning != rs.pruning { 85 rs, err = convertPruning(ctx, rs, rootPruning) 86 if err != nil { 87 return orig, false, err 88 } 89 } 90 91 // selectedRoot records the edited version (possibly "none") for each module 92 // path that would be a root in the edited requirements. 93 var selectedRoot map[string]string // module path → edited version 94 if rootPruning == pruned { 95 selectedRoot = maps.Clone(rs.maxRootVersion) 96 } else { 97 // In a module without graph pruning, modules that provide packages imported 98 // by the main module may either be explicit roots or implicit transitive 99 // dependencies. To the extent possible, we want to preserve those implicit 100 // dependencies, so we need to treat everything in the build list as 101 // potentially relevant — that is, as what would be a “root” in a module 102 // with graph pruning enabled. 103 mg, err := rs.Graph(ctx) 104 if err != nil { 105 // If we couldn't load the graph, we don't know what its requirements were 106 // to begin with, so we can't edit those requirements in a coherent way. 107 return orig, false, err 108 } 109 bl := mg.BuildList()[MainModules.Len():] 110 selectedRoot = make(map[string]string, len(bl)) 111 for _, m := range bl { 112 selectedRoot[m.Path] = m.Version 113 } 114 } 115 116 for _, r := range tryUpgrade { 117 if v, ok := selectedRoot[r.Path]; ok && gover.ModCompare(r.Path, v, r.Version) >= 0 { 118 continue 119 } 120 if cfg.BuildV { 121 fmt.Fprintf(os.Stderr, "go: trying upgrade to %v\n", r) 122 } 123 selectedRoot[r.Path] = r.Version 124 } 125 126 // conflicts is a list of conflicts that we cannot resolve without violating 127 // some version in mustSelect. It may be incomplete, but we want to report 128 // as many conflicts as we can so that the user can solve more of them at once. 129 var conflicts []Conflict 130 131 // mustSelectVersion is an index of the versions in mustSelect. 132 mustSelectVersion := make(map[string]string, len(mustSelect)) 133 for _, r := range mustSelect { 134 if v, ok := mustSelectVersion[r.Path]; ok && v != r.Version { 135 prev := module.Version{Path: r.Path, Version: v} 136 if gover.ModCompare(r.Path, v, r.Version) > 0 { 137 conflicts = append(conflicts, Conflict{Path: []module.Version{prev}, Constraint: r}) 138 } else { 139 conflicts = append(conflicts, Conflict{Path: []module.Version{r}, Constraint: prev}) 140 } 141 continue 142 } 143 144 mustSelectVersion[r.Path] = r.Version 145 selectedRoot[r.Path] = r.Version 146 } 147 148 // We've indexed all of the data we need and we've computed the initial 149 // versions of the roots. Now we need to load the actual module graph and 150 // restore the invariant that every root is the selected version of its path. 151 // 152 // For 'go mod tidy' we would do that using expandGraph, which upgrades the 153 // roots until their requirements are internally consistent and then drops out 154 // the old roots. However, here we need to do more: we also need to make sure 155 // the modules in mustSelect don't get upgraded above their intended versions. 156 // To do that, we repeatedly walk the module graph, identify paths of 157 // requirements that result in versions that are too high, and downgrade the 158 // roots that lead to those paths. When no conflicts remain, we're done. 159 // 160 // Since we want to report accurate paths to each conflict, we don't drop out 161 // older-than-selected roots until the process completes. That might mean that 162 // we do some extra downgrades when they could be skipped, but for the benefit 163 // of being able to explain the reason for every downgrade that seems 164 // worthwhile. 165 // 166 // Graph pruning adds an extra wrinkle: a given node in the module graph 167 // may be reached from a root whose dependencies are pruned, and from a root 168 // whose dependencies are not pruned. It may be the case that the path from 169 // the unpruned root leads to a conflict, while the path from the pruned root 170 // prunes out the requirements that would lead to that conflict. 171 // So we need to track the two kinds of paths independently. 172 // They join back together at the roots of the graph: if a root r1 with pruned 173 // requirements depends on a root r2 with unpruned requirements, then 174 // selecting r1 would cause r2 to become a root and pull in all of its 175 // unpruned dependencies. 176 // 177 // The dqTracker type implements the logic for propagating conflict paths 178 // through the pruned and unpruned parts of the module graph. 179 // 180 // We make a best effort to fix incompatibilities, subject to two properties: 181 // 182 // 1. If the user runs 'go get' with a set of mutually-compatible module 183 // versions, we should accept those versions. 184 // 185 // 2. If we end up upgrading or downgrading a module, it should be 186 // clear why we did so. 187 // 188 // We don't try to find an optimal SAT solution, 189 // especially given the complex interactions with graph pruning. 190 191 var ( 192 roots []module.Version // the current versions in selectedRoot, in sorted order 193 rootsDirty = true // true if roots does not match selectedRoot 194 ) 195 196 // rejectedRoot records the set of module versions that have been disqualified 197 // as roots of the module graph. When downgrading due to a conflict or error, 198 // we skip any version that has already been rejected. 199 // 200 // NOTE(bcmills): I am not sure that the rejectedRoot map is really necessary, 201 // since we normally only downgrade roots or accept indirect upgrades to 202 // known-good versions. However, I am having trouble proving that accepting an 203 // indirect upgrade never introduces a conflict that leads to further 204 // downgrades. I really want to be able to prove that editRequirements 205 // terminates, and the easiest way to prove it is to add this map. 206 // 207 // Then the proof of termination is this: 208 // On every iteration where we mark the roots as dirty, we add some new module 209 // version to the map. The universe of module versions is finite, so we must 210 // eventually reach a state in which we do not add any version to the map. 211 // In that state, we either report a conflict or succeed in the edit. 212 rejectedRoot := map[module.Version]bool{} 213 214 for rootsDirty && len(conflicts) == 0 { 215 roots = roots[:0] 216 for p, v := range selectedRoot { 217 if v != "none" { 218 roots = append(roots, module.Version{Path: p, Version: v}) 219 } 220 } 221 gover.ModSort(roots) 222 223 // First, we extend the graph so that it includes the selected version 224 // of every root. The upgraded roots are in addition to the original 225 // roots, so we will have enough information to trace a path to each 226 // conflict we discover from one or more of the original roots. 227 mg, upgradedRoots, err := extendGraph(ctx, rootPruning, roots, selectedRoot) 228 if err != nil { 229 var tooNew *gover.TooNewError 230 if mg == nil || errors.As(err, &tooNew) { 231 return orig, false, err 232 } 233 // We're about to walk the entire extended module graph, so we will find 234 // any error then — and we will either try to resolve it by downgrading 235 // something or report it as a conflict with more detail. 236 } 237 238 // extendedRootPruning is an index of the pruning used to load each root in 239 // the extended module graph. 240 extendedRootPruning := make(map[module.Version]modPruning, len(roots)+len(upgradedRoots)) 241 findPruning := func(m module.Version) modPruning { 242 if rootPruning == pruned { 243 summary, _ := mg.loadCache.Get(m) 244 if summary != nil && summary.pruning == unpruned { 245 return unpruned 246 } 247 } 248 return rootPruning 249 } 250 for _, m := range roots { 251 extendedRootPruning[m] = findPruning(m) 252 } 253 for m := range upgradedRoots { 254 extendedRootPruning[m] = findPruning(m) 255 } 256 257 // Now check the resulting extended graph for errors and incompatibilities. 258 t := dqTracker{extendedRootPruning: extendedRootPruning} 259 mg.g.WalkBreadthFirst(func(m module.Version) { 260 if max, ok := mustSelectVersion[m.Path]; ok && gover.ModCompare(m.Path, m.Version, max) > 0 { 261 // m itself violates mustSelect, so it cannot appear in the module graph 262 // even if its transitive dependencies would be pruned out. 263 t.disqualify(m, pruned, dqState{dep: m}) 264 return 265 } 266 267 summary, err := mg.loadCache.Get(m) 268 if err != nil && err != par.ErrCacheEntryNotFound { 269 // We can't determine the requirements of m, so we don't know whether 270 // they would be allowed. This may be a transient error reaching the 271 // repository, rather than a permanent error with the retrieved version. 272 // 273 // TODO(golang.org/issue/31730, golang.org/issue/30134): 274 // decide what to do based on the actual error. 275 t.disqualify(m, pruned, dqState{err: err}) 276 return 277 } 278 279 reqs, ok := mg.RequiredBy(m) 280 if !ok { 281 // The dependencies of m do not appear in the module graph, so they 282 // can't be causing any problems this time. 283 return 284 } 285 286 if summary == nil { 287 if m.Version != "" { 288 panic(fmt.Sprintf("internal error: %d reqs present for %v, but summary is nil", len(reqs), m)) 289 } 290 // m is the main module: we are editing its dependencies, so it cannot 291 // become disqualified. 292 return 293 } 294 295 // Before we check for problems due to transitive dependencies, first 296 // check m's direct requirements. A requirement on a version r that 297 // violates mustSelect disqualifies m, even if the requirements of r are 298 // themselves pruned out. 299 for _, r := range reqs { 300 if max, ok := mustSelectVersion[r.Path]; ok && gover.ModCompare(r.Path, r.Version, max) > 0 { 301 t.disqualify(m, pruned, dqState{dep: r}) 302 return 303 } 304 } 305 for _, r := range reqs { 306 if !t.require(m, r) { 307 break 308 } 309 } 310 }) 311 312 // We have now marked all of the versions in the graph that have conflicts, 313 // with a path to each conflict from one or more roots that introduce it. 314 // Now we need to identify those roots and change their versions 315 // (if possible) in order to resolve the conflicts. 316 rootsDirty = false 317 for _, m := range roots { 318 path, err := t.path(m, extendedRootPruning[m]) 319 if len(path) == 0 && err == nil { 320 continue // Nothing wrong with m; we can keep it. 321 } 322 323 // path leads to a module with a problem: either it violates a constraint, 324 // or some error prevents us from determining whether it violates a 325 // constraint. We might end up logging or returning the conflict 326 // information, so go ahead and fill in the details about it. 327 conflict := Conflict{ 328 Path: path, 329 Err: err, 330 } 331 if err == nil { 332 var last module.Version = path[len(path)-1] 333 mustV, ok := mustSelectVersion[last.Path] 334 if !ok { 335 fmt.Fprintf(os.Stderr, "go: %v\n", conflict) 336 panic("internal error: found a version conflict, but no constraint it violates") 337 } 338 conflict.Constraint = module.Version{ 339 Path: last.Path, 340 Version: mustV, 341 } 342 } 343 344 if v, ok := mustSelectVersion[m.Path]; ok && v == m.Version { 345 // m is in mustSelect, but is marked as disqualified due to a transitive 346 // dependency. 347 // 348 // In theory we could try removing module paths that don't appear in 349 // mustSelect (added by tryUpgrade or already present in rs) in order to 350 // get graph pruning to take effect, but (a) it is likely that 'go mod 351 // tidy' would re-add those roots and reintroduce unwanted upgrades, 352 // causing confusion, and (b) deciding which roots to try to eliminate 353 // would add a lot of complexity. 354 // 355 // Instead, we report the path to the conflict as an error. 356 // If users want to explicitly prune out nodes from the dependency 357 // graph, they can always add an explicit 'exclude' directive. 358 conflicts = append(conflicts, conflict) 359 continue 360 } 361 362 // If m is not the selected version of its path, we have two options: we 363 // can either upgrade to the version that actually is selected (dropping m 364 // itself out of the bottom of the module graph), or we can try 365 // downgrading it. 366 // 367 // If the version we would be upgrading to is ok to use, we will just plan 368 // to do that and avoid the overhead of trying to find some lower version 369 // to downgrade to. 370 // 371 // However, it is possible that m depends on something that leads to its 372 // own upgrade, so if the upgrade isn't viable we should go ahead and try 373 // to downgrade (like with any other root). 374 if v := mg.Selected(m.Path); v != m.Version { 375 u := module.Version{Path: m.Path, Version: v} 376 uPruning, ok := t.extendedRootPruning[m] 377 if !ok { 378 fmt.Fprintf(os.Stderr, "go: %v\n", conflict) 379 panic(fmt.Sprintf("internal error: selected version of root %v is %v, but it was not expanded as a new root", m, u)) 380 } 381 if !t.check(u, uPruning).isDisqualified() && !rejectedRoot[u] { 382 // Applying the upgrade from m to u will resolve the conflict, 383 // so plan to do that if there are no other conflicts to resolve. 384 continue 385 } 386 } 387 388 // Figure out what version of m's path was present before we started 389 // the edit. We want to make sure we consider keeping it as-is, 390 // even if it wouldn't normally be included. (For example, it might 391 // be a pseudo-version or pre-release.) 392 origMG, _ := orig.Graph(ctx) 393 origV := origMG.Selected(m.Path) 394 395 if conflict.Err != nil && origV == m.Version { 396 // This version of m.Path was already in the module graph before we 397 // started editing, and the problem with it is that we can't load its 398 // (transitive) requirements. 399 // 400 // If this conflict was just one step in a longer chain of downgrades, 401 // then we would want to keep going past it until we find a version 402 // that doesn't have that problem. However, we only want to downgrade 403 // away from an *existing* requirement if we can confirm that it actually 404 // conflicts with mustSelect. (For example, we don't want 405 // 'go get -u ./...' to incidentally downgrade some dependency whose 406 // go.mod file is unavailable or has a bad checksum.) 407 conflicts = append(conflicts, conflict) 408 continue 409 } 410 411 // We need to downgrade m's path to some lower version to try to resolve 412 // the conflict. Find the next-lowest candidate and apply it. 413 rejectedRoot[m] = true 414 prev := m 415 for { 416 prev, err = previousVersion(ctx, prev) 417 if gover.ModCompare(m.Path, m.Version, origV) > 0 && (gover.ModCompare(m.Path, prev.Version, origV) < 0 || err != nil) { 418 // previousVersion skipped over origV. Insert it into the order. 419 prev.Version = origV 420 } else if err != nil { 421 // We don't know the next downgrade to try. Give up. 422 return orig, false, err 423 } 424 if rejectedRoot[prev] { 425 // We already rejected prev in a previous round. 426 // To ensure that this algorithm terminates, don't try it again. 427 continue 428 } 429 pruning := rootPruning 430 if pruning == pruned { 431 if summary, err := mg.loadCache.Get(m); err == nil { 432 pruning = summary.pruning 433 } 434 } 435 if t.check(prev, pruning).isDisqualified() { 436 // We found a problem with prev this round that would also disqualify 437 // it as a root. Don't bother trying it next round. 438 rejectedRoot[prev] = true 439 continue 440 } 441 break 442 } 443 selectedRoot[m.Path] = prev.Version 444 rootsDirty = true 445 446 // If this downgrade is potentially interesting, log the reason for it. 447 if conflict.Err != nil || cfg.BuildV { 448 var action string 449 if prev.Version == "none" { 450 action = fmt.Sprintf("removing %s", m) 451 } else if prev.Version == origV { 452 action = fmt.Sprintf("restoring %s", prev) 453 } else { 454 action = fmt.Sprintf("trying %s", prev) 455 } 456 fmt.Fprintf(os.Stderr, "go: %s\n\t%s\n", conflict.Summary(), action) 457 } 458 } 459 if rootsDirty { 460 continue 461 } 462 463 // We didn't resolve any issues by downgrading, but we may still need to 464 // resolve some conflicts by locking in upgrades. Do that now. 465 // 466 // We don't do these upgrades until we're done downgrading because the 467 // downgrade process might reveal or remove conflicts (by changing which 468 // requirement edges are pruned out). 469 var upgradedFrom []module.Version // for logging only 470 for p, v := range selectedRoot { 471 if _, ok := mustSelectVersion[p]; !ok { 472 if actual := mg.Selected(p); actual != v { 473 if cfg.BuildV { 474 upgradedFrom = append(upgradedFrom, module.Version{Path: p, Version: v}) 475 } 476 selectedRoot[p] = actual 477 // Accepting the upgrade to m.Path might cause the selected versions 478 // of other modules to fall, because they were being increased by 479 // dependencies of m that are no longer present in the graph. 480 // 481 // TODO(bcmills): Can removing m as a root also cause the selected 482 // versions of other modules to rise? I think not: we're strictly 483 // removing non-root nodes from the module graph, which can't cause 484 // any root to decrease (because they're roots), and the dependencies 485 // of non-roots don't matter because they're either always unpruned or 486 // always pruned out. 487 // 488 // At any rate, it shouldn't cost much to reload the module graph one 489 // last time and confirm that it is stable. 490 rootsDirty = true 491 } 492 } 493 } 494 if rootsDirty { 495 if cfg.BuildV { 496 gover.ModSort(upgradedFrom) // Make logging deterministic. 497 for _, m := range upgradedFrom { 498 fmt.Fprintf(os.Stderr, "go: accepting indirect upgrade from %v to %s\n", m, selectedRoot[m.Path]) 499 } 500 } 501 continue 502 } 503 break 504 } 505 if len(conflicts) > 0 { 506 return orig, false, &ConstraintError{Conflicts: conflicts} 507 } 508 509 if rootPruning == unpruned { 510 // An unpruned go.mod file lists only a subset of the requirements needed 511 // for building packages. Figure out which requirements need to be explicit. 512 var rootPaths []string 513 514 // The modules in mustSelect are always promoted to be explicit. 515 for _, m := range mustSelect { 516 if m.Version != "none" && !MainModules.Contains(m.Path) { 517 rootPaths = append(rootPaths, m.Path) 518 } 519 } 520 521 for _, m := range roots { 522 if v, ok := rs.rootSelected(m.Path); ok && (v == m.Version || rs.direct[m.Path]) { 523 // m.Path was formerly a root, and either its version hasn't changed or 524 // we believe that it provides a package directly imported by a package 525 // or test in the main module. For now we'll assume that it is still 526 // relevant enough to remain a root. If we actually load all of the 527 // packages and tests in the main module (which we are not doing here), 528 // we can revise the explicit roots at that point. 529 rootPaths = append(rootPaths, m.Path) 530 } 531 } 532 533 roots, err = mvs.Req(MainModules.mustGetSingleMainModule(), rootPaths, &mvsReqs{roots: roots}) 534 if err != nil { 535 return nil, false, err 536 } 537 } 538 539 changed = rootPruning != orig.pruning || !slices.Equal(roots, orig.rootModules) 540 if !changed { 541 // Because the roots we just computed are unchanged, the entire graph must 542 // be the same as it was before. Save the original rs, since we have 543 // probably already loaded its requirement graph. 544 return orig, false, nil 545 } 546 547 // A module that is not even in the build list necessarily cannot provide 548 // any imported packages. Mark as direct only the direct modules that are 549 // still in the build list. (We assume that any module path that provided a 550 // direct import before the edit continues to do so after. There are a few 551 // edge cases where that can change, such as if a package moves into or out of 552 // a nested module or disappears entirely. If that happens, the user can run 553 // 'go mod tidy' to clean up the direct/indirect annotations.) 554 // 555 // TODO(bcmills): Would it make more sense to leave the direct map as-is 556 // but allow it to refer to modules that are no longer in the build list? 557 // That might complicate updateRoots, but it may be cleaner in other ways. 558 direct := make(map[string]bool, len(rs.direct)) 559 for _, m := range roots { 560 if rs.direct[m.Path] { 561 direct[m.Path] = true 562 } 563 } 564 edited = newRequirements(rootPruning, roots, direct) 565 566 // If we ended up adding a dependency that upgrades our go version far enough 567 // to activate pruning, we must convert the edited Requirements in order to 568 // avoid dropping transitive dependencies from the build list the next time 569 // someone uses the updated go.mod file. 570 // 571 // Note that it isn't possible to go in the other direction (from pruned to 572 // unpruned) unless the "go" or "toolchain" module is explicitly listed in 573 // mustSelect, which we already handled at the very beginning of the edit. 574 // That is because the virtual "go" module only requires a "toolchain", 575 // and the "toolchain" module never requires anything else, which means that 576 // those two modules will never be downgraded due to a conflict with any other 577 // constraint. 578 if rootPruning == unpruned { 579 if v, ok := edited.rootSelected("go"); ok && pruningForGoVersion(v) == pruned { 580 // Since we computed the edit with the unpruned graph, and the pruned 581 // graph is a strict subset of the unpruned graph, this conversion 582 // preserves the exact (edited) build list that we already computed. 583 // 584 // However, it does that by shoving the whole build list into the roots of 585 // the graph. 'go get' will check for that sort of transition and log a 586 // message reminding the user how to clean up this mess we're about to 587 // make. 😅 588 edited, err = convertPruning(ctx, edited, pruned) 589 if err != nil { 590 return orig, false, err 591 } 592 } 593 } 594 return edited, true, nil 595 } 596 597 // extendGraph loads the module graph from roots, and iteratively extends it by 598 // unpruning the selected version of each module path that is a root in rs or in 599 // the roots slice until the graph reaches a fixed point. 600 // 601 // The graph is guaranteed to converge to a fixed point because unpruning a 602 // module version can only increase (never decrease) the selected versions, 603 // and the set of versions for each module is finite. 604 // 605 // The extended graph is useful for diagnosing version conflicts: for each 606 // selected module version, it can provide a complete path of requirements from 607 // some root to that version. 608 func extendGraph(ctx context.Context, rootPruning modPruning, roots []module.Version, selectedRoot map[string]string) (mg *ModuleGraph, upgradedRoot map[module.Version]bool, err error) { 609 for { 610 mg, err = readModGraph(ctx, rootPruning, roots, upgradedRoot) 611 // We keep on going even if err is non-nil until we reach a steady state. 612 // (Note that readModGraph returns a non-nil *ModuleGraph even in case of 613 // errors.) The caller may be able to fix the errors by adjusting versions, 614 // so we really want to return as complete a result as we can. 615 616 if rootPruning == unpruned { 617 // Everything is already unpruned, so there isn't anything we can do to 618 // extend it further. 619 break 620 } 621 622 nPrevRoots := len(upgradedRoot) 623 for p := range selectedRoot { 624 // Since p is a root path, when we fix up the module graph to be 625 // consistent with the selected versions, p will be promoted to a root, 626 // which will pull in its dependencies. Ensure that its dependencies are 627 // included in the module graph. 628 v := mg.g.Selected(p) 629 if v == "none" { 630 // Version “none” always has no requirements, so it doesn't need 631 // an explicit node in the module graph. 632 continue 633 } 634 m := module.Version{Path: p, Version: v} 635 if _, ok := mg.g.RequiredBy(m); !ok && !upgradedRoot[m] { 636 // The dependencies of the selected version of p were not loaded. 637 // Mark it as an upgrade so that we will load its dependencies 638 // in the next iteration. 639 // 640 // Note that we don't remove any of the existing roots, even if they are 641 // no longer the selected version: with graph pruning in effect this may 642 // leave some spurious dependencies in the graph, but it at least 643 // preserves enough of the graph to explain why each upgrade occurred: 644 // this way, we can report a complete path from the passed-in roots 645 // to every node in the module graph. 646 // 647 // This process is guaranteed to reach a fixed point: since we are only 648 // adding roots (never removing them), the selected version of each module 649 // can only increase, never decrease, and the set of module versions in the 650 // universe is finite. 651 if upgradedRoot == nil { 652 upgradedRoot = make(map[module.Version]bool) 653 } 654 upgradedRoot[m] = true 655 } 656 } 657 if len(upgradedRoot) == nPrevRoots { 658 break 659 } 660 } 661 662 return mg, upgradedRoot, err 663 } 664 665 type perPruning[T any] struct { 666 pruned T 667 unpruned T 668 } 669 670 func (pp perPruning[T]) from(p modPruning) T { 671 if p == unpruned { 672 return pp.unpruned 673 } 674 return pp.pruned 675 } 676 677 // A dqTracker tracks and propagates the reason that each module version 678 // cannot be included in the module graph. 679 type dqTracker struct { 680 // extendedRootPruning is the modPruning given the go.mod file for each root 681 // in the extended module graph. 682 extendedRootPruning map[module.Version]modPruning 683 684 // dqReason records whether and why each each encountered version is 685 // disqualified in a pruned or unpruned context. 686 dqReason map[module.Version]perPruning[dqState] 687 688 // requiring maps each not-yet-disqualified module version to the versions 689 // that would cause that module's requirements to be included in a pruned or 690 // unpruned context. If that version becomes disqualified, the 691 // disqualification will be propagated to all of the versions in the 692 // corresponding list. 693 // 694 // This map is similar to the module requirement graph, but includes more 695 // detail about whether a given dependency edge appears in a pruned or 696 // unpruned context. (Other commands do not need this level of detail.) 697 requiring map[module.Version][]module.Version 698 } 699 700 // A dqState indicates whether and why a module version is “disqualified” from 701 // being used in a way that would incorporate its requirements. 702 // 703 // The zero dqState indicates that the module version is not known to be 704 // disqualified, either because it is ok or because we are currently traversing 705 // a cycle that includes it. 706 type dqState struct { 707 err error // if non-nil, disqualified because the requirements of the module could not be read 708 dep module.Version // disqualified because the module is or requires dep 709 } 710 711 func (dq dqState) isDisqualified() bool { 712 return dq != dqState{} 713 } 714 715 func (dq dqState) String() string { 716 if dq.err != nil { 717 return dq.err.Error() 718 } 719 if dq.dep != (module.Version{}) { 720 return dq.dep.String() 721 } 722 return "(no conflict)" 723 } 724 725 // require records that m directly requires r, in case r becomes disqualified. 726 // (These edges are in the opposite direction from the edges in an mvs.Graph.) 727 // 728 // If r is already disqualified, require propagates the disqualification to m 729 // and returns the reason for the disqualification. 730 func (t *dqTracker) require(m, r module.Version) (ok bool) { 731 rdq := t.dqReason[r] 732 rootPruning, isRoot := t.extendedRootPruning[r] 733 if isRoot && rdq.from(rootPruning).isDisqualified() { 734 // When we pull in m's dependencies, we will have an edge from m to r, and r 735 // is disqualified (it is a root, which causes its problematic dependencies 736 // to always be included). So we cannot pull in m's dependencies at all: 737 // m is completely disqualified. 738 t.disqualify(m, pruned, dqState{dep: r}) 739 return false 740 } 741 742 if dq := rdq.from(unpruned); dq.isDisqualified() { 743 t.disqualify(m, unpruned, dqState{dep: r}) 744 if _, ok := t.extendedRootPruning[m]; !ok { 745 // Since m is not a root, its dependencies can't be included in the pruned 746 // part of the module graph, and will never be disqualified from a pruned 747 // reason. We've already disqualified everything that matters. 748 return false 749 } 750 } 751 752 // Record that m is a dependant of r, so that if r is later disqualified 753 // m will be disqualified as well. 754 if t.requiring == nil { 755 t.requiring = make(map[module.Version][]module.Version) 756 } 757 t.requiring[r] = append(t.requiring[r], m) 758 return true 759 } 760 761 // disqualify records why the dependencies of m cannot be included in the module 762 // graph if reached from a part of the graph with the given pruning. 763 // 764 // Since the pruned graph is a subgraph of the unpruned graph, disqualifying a 765 // module from a pruned part of the graph also disqualifies it in the unpruned 766 // parts. 767 func (t *dqTracker) disqualify(m module.Version, fromPruning modPruning, reason dqState) { 768 if !reason.isDisqualified() { 769 panic("internal error: disqualify called with a non-disqualifying dqState") 770 } 771 772 dq := t.dqReason[m] 773 if dq.from(fromPruning).isDisqualified() { 774 return // Already disqualified for some other reason; don't overwrite it. 775 } 776 rootPruning, isRoot := t.extendedRootPruning[m] 777 if fromPruning == pruned { 778 dq.pruned = reason 779 if !dq.unpruned.isDisqualified() { 780 // Since the pruned graph of m is a subgraph of the unpruned graph, if it 781 // is disqualified due to something in the pruned graph, it is certainly 782 // disqualified in the unpruned graph from the same reason. 783 dq.unpruned = reason 784 } 785 } else { 786 dq.unpruned = reason 787 if dq.pruned.isDisqualified() { 788 panic(fmt.Sprintf("internal error: %v is marked as disqualified when pruned, but not when unpruned", m)) 789 } 790 if isRoot && rootPruning == unpruned { 791 // Since m is a root that is always unpruned, any other roots — even 792 // pruned ones! — that cause it to be selected would also cause the reason 793 // for is disqualification to be included in the module graph. 794 dq.pruned = reason 795 } 796 } 797 if t.dqReason == nil { 798 t.dqReason = make(map[module.Version]perPruning[dqState]) 799 } 800 t.dqReason[m] = dq 801 802 if isRoot && (fromPruning == pruned || rootPruning == unpruned) { 803 // Either m is disqualified even when its dependencies are pruned, 804 // or m's go.mod file causes its dependencies to *always* be unpruned. 805 // Everything that depends on it must be disqualified. 806 for _, p := range t.requiring[m] { 807 t.disqualify(p, pruned, dqState{dep: m}) 808 // Note that since the pruned graph is a subset of the unpruned graph, 809 // disqualifying p in the pruned graph also disqualifies it in the 810 // unpruned graph. 811 } 812 // Everything in t.requiring[m] is now fully disqualified. 813 // We won't need to use it again. 814 delete(t.requiring, m) 815 return 816 } 817 818 // Either m is not a root, or it is a pruned root but only being disqualified 819 // when reached from the unpruned parts of the module graph. 820 // Either way, the reason for this disqualification is only visible to the 821 // unpruned parts of the module graph. 822 for _, p := range t.requiring[m] { 823 t.disqualify(p, unpruned, dqState{dep: m}) 824 } 825 if !isRoot { 826 // Since m is not a root, its dependencies can't be included in the pruned 827 // part of the module graph, and will never be disqualified from a pruned 828 // reason. We've already disqualified everything that matters. 829 delete(t.requiring, m) 830 } 831 } 832 833 // check reports whether m is disqualified in the given pruning context. 834 func (t *dqTracker) check(m module.Version, pruning modPruning) dqState { 835 return t.dqReason[m].from(pruning) 836 } 837 838 // path returns the path from m to the reason it is disqualified, which may be 839 // either a module that violates constraints or an error in loading 840 // requirements. 841 // 842 // If m is not disqualified, path returns (nil, nil). 843 func (t *dqTracker) path(m module.Version, pruning modPruning) (path []module.Version, err error) { 844 for { 845 dq := t.dqReason[m].from(pruning) 846 if !dq.isDisqualified() { 847 return path, nil 848 } 849 path = append(path, m) 850 if dq.err != nil || dq.dep == m { 851 return path, dq.err // m itself is the conflict. 852 } 853 m = dq.dep 854 } 855 } 856