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