Source file src/cmd/go/internal/modload/buildlist.go
1 // Copyright 2018 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 "runtime" 14 "runtime/debug" 15 "slices" 16 "strings" 17 "sync" 18 "sync/atomic" 19 20 "cmd/go/internal/base" 21 "cmd/go/internal/cfg" 22 "cmd/go/internal/gover" 23 "cmd/go/internal/mvs" 24 "cmd/internal/par" 25 26 "golang.org/x/mod/module" 27 ) 28 29 // A Requirements represents a logically-immutable set of root module requirements. 30 type Requirements struct { 31 // pruning is the pruning at which the requirement graph is computed. 32 // 33 // If unpruned, the graph includes all transitive requirements regardless 34 // of whether the requiring module supports pruning. 35 // 36 // If pruned, the graph includes only the root modules, the explicit 37 // requirements of those root modules, and the transitive requirements of only 38 // the root modules that do not support pruning. 39 // 40 // If workspace, the graph includes only the workspace modules, the explicit 41 // requirements of the workspace modules, and the transitive requirements of 42 // the workspace modules that do not support pruning. 43 pruning modPruning 44 45 // rootModules is the set of root modules of the graph, sorted and capped to 46 // length. It may contain duplicates, and may contain multiple versions for a 47 // given module path. The root modules of the graph are the set of main 48 // modules in workspace mode, and the main module's direct requirements 49 // outside workspace mode. 50 // 51 // The roots are always expected to contain an entry for the "go" module, 52 // indicating the Go language version in use. 53 rootModules []module.Version 54 maxRootVersion map[string]string 55 56 // direct is the set of module paths for which we believe the module provides 57 // a package directly imported by a package or test in the main module. 58 // 59 // The "direct" map controls which modules are annotated with "// indirect" 60 // comments in the go.mod file, and may impact which modules are listed as 61 // explicit roots (vs. indirect-only dependencies). However, it should not 62 // have a semantic effect on the build list overall. 63 // 64 // The initial direct map is populated from the existing "// indirect" 65 // comments (or lack thereof) in the go.mod file. It is updated by the 66 // package loader: dependencies may be promoted to direct if new 67 // direct imports are observed, and may be demoted to indirect during 68 // 'go mod tidy' or 'go mod vendor'. 69 // 70 // The direct map is keyed by module paths, not module versions. When a 71 // module's selected version changes, we assume that it remains direct if the 72 // previous version was a direct dependency. That assumption might not hold in 73 // rare cases (such as if a dependency splits out a nested module, or merges a 74 // nested module back into a parent module). 75 direct map[string]bool 76 77 graphOnce sync.Once // guards writes to (but not reads from) graph 78 graph atomic.Pointer[cachedGraph] 79 } 80 81 // A cachedGraph is a non-nil *ModuleGraph, together with any error discovered 82 // while loading that graph. 83 type cachedGraph struct { 84 mg *ModuleGraph 85 err error // If err is non-nil, mg may be incomplete (but must still be non-nil). 86 } 87 88 func mustHaveGoRoot(roots []module.Version) { 89 for _, m := range roots { 90 if m.Path == "go" { 91 return 92 } 93 } 94 panic("go: internal error: missing go root module") 95 } 96 97 // newRequirements returns a new requirement set with the given root modules. 98 // The dependencies of the roots will be loaded lazily at the first call to the 99 // Graph method. 100 // 101 // The rootModules slice must be sorted according to gover.ModSort. 102 // The caller must not modify the rootModules slice or direct map after passing 103 // them to newRequirements. 104 // 105 // If vendoring is in effect, the caller must invoke initVendor on the returned 106 // *Requirements before any other method. 107 func newRequirements(loaderstate *State, pruning modPruning, rootModules []module.Version, direct map[string]bool) *Requirements { 108 mustHaveGoRoot(rootModules) 109 110 if pruning != workspace { 111 if loaderstate.workFilePath != "" { 112 panic("in workspace mode, but pruning is not workspace in newRequirements") 113 } 114 } 115 116 if pruning != workspace { 117 if loaderstate.workFilePath != "" { 118 panic("in workspace mode, but pruning is not workspace in newRequirements") 119 } 120 for i, m := range rootModules { 121 if m.Version == "" && loaderstate.MainModules.Contains(m.Path) { 122 panic(fmt.Sprintf("newRequirements called with untrimmed build list: rootModules[%v] is a main module", i)) 123 } 124 if m.Path == "" || m.Version == "" { 125 panic(fmt.Sprintf("bad requirement: rootModules[%v] = %v", i, m)) 126 } 127 } 128 } 129 130 rs := &Requirements{ 131 pruning: pruning, 132 rootModules: rootModules, 133 maxRootVersion: make(map[string]string, len(rootModules)), 134 direct: direct, 135 } 136 137 for i, m := range rootModules { 138 if i > 0 { 139 prev := rootModules[i-1] 140 if prev.Path > m.Path || (prev.Path == m.Path && gover.ModCompare(m.Path, prev.Version, m.Version) > 0) { 141 panic(fmt.Sprintf("newRequirements called with unsorted roots: %v", rootModules)) 142 } 143 } 144 145 if v, ok := rs.maxRootVersion[m.Path]; ok && gover.ModCompare(m.Path, v, m.Version) >= 0 { 146 continue 147 } 148 rs.maxRootVersion[m.Path] = m.Version 149 } 150 151 if rs.maxRootVersion["go"] == "" { 152 panic(`newRequirements called without a "go" version`) 153 } 154 return rs 155 } 156 157 // String returns a string describing the Requirements for debugging. 158 func (rs *Requirements) String() string { 159 return fmt.Sprintf("{%v %v}", rs.pruning, rs.rootModules) 160 } 161 162 // initVendor initializes rs.graph from the given list of vendored module 163 // dependencies, overriding the graph that would normally be loaded from module 164 // requirements. 165 func (rs *Requirements) initVendor(loaderstate *State, vendorList []module.Version) { 166 rs.graphOnce.Do(func() { 167 roots := loaderstate.MainModules.Versions() 168 if loaderstate.inWorkspaceMode() { 169 // Use rs.rootModules to pull in the go and toolchain roots 170 // from the go.work file and preserve the invariant that all 171 // of rs.rootModules are in mg.g. 172 roots = rs.rootModules 173 } 174 mg := &ModuleGraph{ 175 g: mvs.NewGraph(cmpVersion, roots), 176 } 177 178 if rs.pruning == pruned { 179 mainModule := loaderstate.MainModules.mustGetSingleMainModule(loaderstate) 180 // The roots of a single pruned module should already include every module in the 181 // vendor list, because the vendored modules are the same as those needed 182 // for graph pruning. 183 // 184 // Just to be sure, we'll double-check that here. 185 inconsistent := false 186 for _, m := range vendorList { 187 if v, ok := rs.rootSelected(loaderstate, m.Path); !ok || v != m.Version { 188 base.Errorf("go: vendored module %v should be required explicitly in go.mod", m) 189 inconsistent = true 190 } 191 } 192 if inconsistent { 193 base.Fatal(errGoModDirty) 194 } 195 196 // Now we can treat the rest of the module graph as effectively “pruned 197 // out”, as though we are viewing the main module from outside: in vendor 198 // mode, the root requirements *are* the complete module graph. 199 mg.g.Require(mainModule, rs.rootModules) 200 } else { 201 // The transitive requirements of the main module are not in general available 202 // from the vendor directory, and we don't actually know how we got from 203 // the roots to the final build list. 204 // 205 // Instead, we'll inject a fake "vendor/modules.txt" module that provides 206 // those transitive dependencies, and mark it as a dependency of the main 207 // module. That allows us to elide the actual structure of the module 208 // graph, but still distinguishes between direct and indirect 209 // dependencies. 210 vendorMod := module.Version{Path: "vendor/modules.txt", Version: ""} 211 if loaderstate.inWorkspaceMode() { 212 for _, m := range loaderstate.MainModules.Versions() { 213 reqs, _ := rootsFromModFile(loaderstate, m, loaderstate.MainModules.ModFile(m), omitToolchainRoot) 214 mg.g.Require(m, append(reqs, vendorMod)) 215 } 216 mg.g.Require(vendorMod, vendorList) 217 218 } else { 219 mainModule := loaderstate.MainModules.mustGetSingleMainModule(loaderstate) 220 mg.g.Require(mainModule, append(rs.rootModules, vendorMod)) 221 mg.g.Require(vendorMod, vendorList) 222 } 223 } 224 225 rs.graph.Store(&cachedGraph{mg, nil}) 226 }) 227 } 228 229 // GoVersion returns the Go language version for the Requirements. 230 func (rs *Requirements) GoVersion(loaderstate *State) string { 231 v, _ := rs.rootSelected(loaderstate, "go") 232 if v == "" { 233 panic("internal error: missing go version in modload.Requirements") 234 } 235 return v 236 } 237 238 // rootSelected returns the version of the root dependency with the given module 239 // path, or the zero module.Version and ok=false if the module is not a root 240 // dependency. 241 func (rs *Requirements) rootSelected(loaderstate *State, path string) (version string, ok bool) { 242 if loaderstate.MainModules.Contains(path) { 243 return "", true 244 } 245 if v, ok := rs.maxRootVersion[path]; ok { 246 return v, true 247 } 248 return "", false 249 } 250 251 // hasRedundantRoot returns true if the root list contains multiple requirements 252 // of the same module or a requirement on any version of the main module. 253 // Redundant requirements should be pruned, but they may influence version 254 // selection. 255 func (rs *Requirements) hasRedundantRoot(loaderstate *State) bool { 256 for i, m := range rs.rootModules { 257 if loaderstate.MainModules.Contains(m.Path) || (i > 0 && m.Path == rs.rootModules[i-1].Path) { 258 return true 259 } 260 } 261 return false 262 } 263 264 // Graph returns the graph of module requirements loaded from the current 265 // root modules (as reported by RootModules). 266 // 267 // Graph always makes a best effort to load the requirement graph despite any 268 // errors, and always returns a non-nil *ModuleGraph. 269 // 270 // If the requirements of any relevant module fail to load, Graph also 271 // returns a non-nil error of type *mvs.BuildListError. 272 func (rs *Requirements) Graph(loaderstate *State, ctx context.Context) (*ModuleGraph, error) { 273 rs.graphOnce.Do(func() { 274 mg, mgErr := readModGraph(loaderstate, ctx, rs.pruning, rs.rootModules, nil) 275 rs.graph.Store(&cachedGraph{mg, mgErr}) 276 }) 277 cached := rs.graph.Load() 278 return cached.mg, cached.err 279 } 280 281 // IsDirect returns whether the given module provides a package directly 282 // imported by a package or test in the main module. 283 func (rs *Requirements) IsDirect(path string) bool { 284 return rs.direct[path] 285 } 286 287 // A ModuleGraph represents the complete graph of module dependencies 288 // of a main module. 289 // 290 // If the main module supports module graph pruning, the graph does not include 291 // transitive dependencies of non-root (implicit) dependencies. 292 type ModuleGraph struct { 293 g *mvs.Graph 294 loadCache par.ErrCache[module.Version, *modFileSummary] 295 296 buildListOnce sync.Once 297 buildList []module.Version 298 } 299 300 var readModGraphDebugOnce sync.Once 301 302 // readModGraph reads and returns the module dependency graph starting at the 303 // given roots. 304 // 305 // The requirements of the module versions found in the unprune map are included 306 // in the graph even if they would normally be pruned out. 307 // 308 // Unlike LoadModGraph, readModGraph does not attempt to diagnose or update 309 // inconsistent roots. 310 func readModGraph(loaderstate *State, ctx context.Context, pruning modPruning, roots []module.Version, unprune map[module.Version]bool) (*ModuleGraph, error) { 311 mustHaveGoRoot(roots) 312 if pruning == pruned { 313 // Enable diagnostics for lazy module loading 314 // (https://golang.org/ref/mod#lazy-loading) only if the module graph is 315 // pruned. 316 // 317 // In unpruned modules,we load the module graph much more aggressively (in 318 // order to detect inconsistencies that wouldn't be feasible to spot-check), 319 // so it wouldn't be useful to log when that occurs (because it happens in 320 // normal operation all the time). 321 readModGraphDebugOnce.Do(func() { 322 for f := range strings.SplitSeq(os.Getenv("GODEBUG"), ",") { 323 switch f { 324 case "lazymod=log": 325 debug.PrintStack() 326 fmt.Fprintf(os.Stderr, "go: read full module graph.\n") 327 case "lazymod=strict": 328 debug.PrintStack() 329 base.Fatalf("go: read full module graph (forbidden by GODEBUG=lazymod=strict).") 330 } 331 } 332 }) 333 } 334 335 var graphRoots []module.Version 336 if loaderstate.inWorkspaceMode() { 337 graphRoots = roots 338 } else { 339 graphRoots = loaderstate.MainModules.Versions() 340 } 341 var ( 342 mu sync.Mutex // guards mg.g and hasError during loading 343 hasError bool 344 mg = &ModuleGraph{ 345 g: mvs.NewGraph(cmpVersion, graphRoots), 346 } 347 ) 348 349 if pruning != workspace { 350 if loaderstate.inWorkspaceMode() { 351 panic("pruning is not workspace in workspace mode") 352 } 353 mg.g.Require(loaderstate.MainModules.mustGetSingleMainModule(loaderstate), roots) 354 } 355 356 type dedupKey struct { 357 m module.Version 358 pruning modPruning 359 } 360 var ( 361 loadQueue = par.NewQueue(runtime.GOMAXPROCS(0)) 362 loading sync.Map // dedupKey → nil; the set of modules that have been or are being loaded 363 ) 364 365 // loadOne synchronously loads the explicit requirements for module m. 366 // It does not load the transitive requirements of m even if the go version in 367 // m's go.mod file indicates that it supports graph pruning. 368 loadOne := func(m module.Version) (*modFileSummary, error) { 369 return mg.loadCache.Do(m, func() (*modFileSummary, error) { 370 summary, err := goModSummary(loaderstate, m) 371 372 mu.Lock() 373 if err == nil { 374 mg.g.Require(m, summary.require) 375 } else { 376 hasError = true 377 } 378 mu.Unlock() 379 380 return summary, err 381 }) 382 } 383 384 var enqueue func(m module.Version, pruning modPruning) 385 enqueue = func(m module.Version, pruning modPruning) { 386 if m.Version == "none" { 387 return 388 } 389 390 if _, dup := loading.LoadOrStore(dedupKey{m, pruning}, nil); dup { 391 // m has already been enqueued for loading. Since unpruned loading may 392 // follow cycles in the requirement graph, we need to return early 393 // to avoid making the load queue infinitely long. 394 return 395 } 396 397 loadQueue.Add(func() { 398 summary, err := loadOne(m) 399 if err != nil { 400 return // findError will report the error later. 401 } 402 403 // If the version in m's go.mod file does not support pruning, then we 404 // cannot assume that the explicit requirements of m (added by loadOne) 405 // are sufficient to build the packages it contains. We must load its full 406 // transitive dependency graph to be sure that we see all relevant 407 // dependencies. In addition, we must load the requirements of any module 408 // that is explicitly marked as unpruned. 409 nextPruning := summary.pruning 410 if pruning == unpruned { 411 nextPruning = unpruned 412 } 413 for _, r := range summary.require { 414 if pruning != pruned || summary.pruning == unpruned || unprune[r] { 415 enqueue(r, nextPruning) 416 } 417 } 418 }) 419 } 420 421 mustHaveGoRoot(roots) 422 for _, m := range roots { 423 enqueue(m, pruning) 424 } 425 <-loadQueue.Idle() 426 427 // Reload any dependencies of the main modules which are not 428 // at their selected versions at workspace mode, because the 429 // requirements don't accurately reflect the transitive imports. 430 if pruning == workspace { 431 // hasDepsInAll contains the set of modules that need to be loaded 432 // at workspace pruning because any of their dependencies may 433 // provide packages in all. 434 hasDepsInAll := make(map[string]bool) 435 seen := map[module.Version]bool{} 436 for _, m := range roots { 437 hasDepsInAll[m.Path] = true 438 } 439 // This loop will terminate because it will call enqueue on each version of 440 // each dependency of the modules in hasDepsInAll at most once (and only 441 // calls enqueue on successively increasing versions of each dependency). 442 for { 443 needsEnqueueing := map[module.Version]bool{} 444 for p := range hasDepsInAll { 445 m := module.Version{Path: p, Version: mg.g.Selected(p)} 446 if !seen[m] { 447 needsEnqueueing[m] = true 448 continue 449 } 450 reqs, _ := mg.g.RequiredBy(m) 451 for _, r := range reqs { 452 s := module.Version{Path: r.Path, Version: mg.g.Selected(r.Path)} 453 if gover.ModCompare(r.Path, s.Version, r.Version) > 0 && !seen[s] { 454 needsEnqueueing[s] = true 455 } 456 } 457 } 458 // add all needs enqueueing to paths we care about 459 if len(needsEnqueueing) == 0 { 460 break 461 } 462 463 for p := range needsEnqueueing { 464 enqueue(p, workspace) 465 seen[p] = true 466 hasDepsInAll[p.Path] = true 467 } 468 <-loadQueue.Idle() 469 } 470 } 471 472 if hasError { 473 return mg, mg.findError() 474 } 475 return mg, nil 476 } 477 478 // RequiredBy returns the dependencies required by module m in the graph, 479 // or ok=false if module m's dependencies are pruned out. 480 // 481 // The caller must not modify the returned slice, but may safely append to it 482 // and may rely on it not to be modified. 483 func (mg *ModuleGraph) RequiredBy(m module.Version) (reqs []module.Version, ok bool) { 484 return mg.g.RequiredBy(m) 485 } 486 487 // Selected returns the selected version of the module with the given path. 488 // 489 // If no version is selected, Selected returns version "none". 490 func (mg *ModuleGraph) Selected(path string) (version string) { 491 return mg.g.Selected(path) 492 } 493 494 // WalkBreadthFirst invokes f once, in breadth-first order, for each module 495 // version other than "none" that appears in the graph, regardless of whether 496 // that version is selected. 497 func (mg *ModuleGraph) WalkBreadthFirst(f func(m module.Version)) { 498 mg.g.WalkBreadthFirst(f) 499 } 500 501 // BuildList returns the selected versions of all modules present in the graph, 502 // beginning with the main modules. 503 // 504 // The order of the remaining elements in the list is deterministic 505 // but arbitrary. 506 // 507 // The caller must not modify the returned list, but may safely append to it 508 // and may rely on it not to be modified. 509 func (mg *ModuleGraph) BuildList() []module.Version { 510 mg.buildListOnce.Do(func() { 511 mg.buildList = slices.Clip(mg.g.BuildList()) 512 }) 513 return mg.buildList 514 } 515 516 func (mg *ModuleGraph) findError() error { 517 errStack := mg.g.FindPath(func(m module.Version) bool { 518 _, err := mg.loadCache.Get(m) 519 return err != nil && err != par.ErrCacheEntryNotFound 520 }) 521 if len(errStack) > 0 { 522 _, err := mg.loadCache.Get(errStack[len(errStack)-1]) 523 var noUpgrade func(from, to module.Version) bool 524 return mvs.NewBuildListError(err, errStack, noUpgrade) 525 } 526 527 return nil 528 } 529 530 func (mg *ModuleGraph) allRootsSelected(loaderstate *State) bool { 531 var roots []module.Version 532 if loaderstate.inWorkspaceMode() { 533 roots = loaderstate.MainModules.Versions() 534 } else { 535 roots, _ = mg.g.RequiredBy(loaderstate.MainModules.mustGetSingleMainModule(loaderstate)) 536 } 537 for _, m := range roots { 538 if mg.Selected(m.Path) != m.Version { 539 return false 540 } 541 } 542 return true 543 } 544 545 // LoadModGraph loads and returns the graph of module dependencies of the main module, 546 // without loading any packages. 547 // 548 // If the goVersion string is non-empty, the returned graph is the graph 549 // as interpreted by the given Go version (instead of the version indicated 550 // in the go.mod file). 551 // 552 // Modules are loaded automatically (and lazily) in LoadPackages: 553 // LoadModGraph need only be called if LoadPackages is not, 554 // typically in commands that care about modules but no particular package. 555 func LoadModGraph(loaderstate *State, ctx context.Context, goVersion string) (*ModuleGraph, error) { 556 rs, err := loadModFile(loaderstate, ctx, nil) 557 if err != nil { 558 return nil, err 559 } 560 561 if goVersion != "" { 562 v, _ := rs.rootSelected(loaderstate, "go") 563 if gover.Compare(v, gover.GoStrictVersion) >= 0 && gover.Compare(goVersion, v) < 0 { 564 return nil, fmt.Errorf("requested Go version %s cannot load module graph (requires Go >= %s)", goVersion, v) 565 } 566 567 pruning := pruningForGoVersion(goVersion) 568 if pruning == unpruned && rs.pruning != unpruned { 569 // Use newRequirements instead of convertDepth because convertDepth 570 // also updates roots; here, we want to report the unmodified roots 571 // even though they may seem inconsistent. 572 rs = newRequirements(loaderstate, unpruned, rs.rootModules, rs.direct) 573 } 574 575 return rs.Graph(loaderstate, ctx) 576 } 577 578 rs, mg, err := expandGraph(loaderstate, ctx, rs) 579 if err != nil { 580 return nil, err 581 } 582 loaderstate.requirements = rs 583 return mg, nil 584 } 585 586 // expandGraph loads the complete module graph from rs. 587 // 588 // If the complete graph reveals that some root of rs is not actually the 589 // selected version of its path, expandGraph computes a new set of roots that 590 // are consistent. (With a pruned module graph, this may result in upgrades to 591 // other modules due to requirements that were previously pruned out.) 592 // 593 // expandGraph returns the updated roots, along with the module graph loaded 594 // from those roots and any error encountered while loading that graph. 595 // expandGraph returns non-nil requirements and a non-nil graph regardless of 596 // errors. On error, the roots might not be updated to be consistent. 597 func expandGraph(loaderstate *State, ctx context.Context, rs *Requirements) (*Requirements, *ModuleGraph, error) { 598 mg, mgErr := rs.Graph(loaderstate, ctx) 599 if mgErr != nil { 600 // Without the graph, we can't update the roots: we don't know which 601 // versions of transitive dependencies would be selected. 602 return rs, mg, mgErr 603 } 604 605 if !mg.allRootsSelected(loaderstate) { 606 // The roots of rs are not consistent with the rest of the graph. Update 607 // them. In an unpruned module this is a no-op for the build list as a whole — 608 // it just promotes what were previously transitive requirements to be 609 // roots — but in a pruned module it may pull in previously-irrelevant 610 // transitive dependencies. 611 612 newRS, rsErr := updateRoots(loaderstate, ctx, rs.direct, rs, nil, nil, false) 613 if rsErr != nil { 614 // Failed to update roots, perhaps because of an error in a transitive 615 // dependency needed for the update. Return the original Requirements 616 // instead. 617 return rs, mg, rsErr 618 } 619 rs = newRS 620 mg, mgErr = rs.Graph(loaderstate, ctx) 621 } 622 623 return rs, mg, mgErr 624 } 625 626 // EditBuildList edits the global build list by first adding every module in add 627 // to the existing build list, then adjusting versions (and adding or removing 628 // requirements as needed) until every module in mustSelect is selected at the 629 // given version. 630 // 631 // (Note that the newly-added modules might not be selected in the resulting 632 // build list: they could be lower than existing requirements or conflict with 633 // versions in mustSelect.) 634 // 635 // If the versions listed in mustSelect are mutually incompatible (due to one of 636 // the listed modules requiring a higher version of another), EditBuildList 637 // returns a *ConstraintError and leaves the build list in its previous state. 638 // 639 // On success, EditBuildList reports whether the selected version of any module 640 // in the build list may have been changed (possibly to or from "none") as a 641 // result. 642 func EditBuildList(loaderstate *State, ctx context.Context, add, mustSelect []module.Version) (changed bool, err error) { 643 rs, changed, err := editRequirements(loaderstate, ctx, LoadModFile(loaderstate, ctx), add, mustSelect) 644 if err != nil { 645 return false, err 646 } 647 loaderstate.requirements = rs 648 return changed, nil 649 } 650 651 func overrideRoots(loaderstate *State, ctx context.Context, rs *Requirements, replace []module.Version) *Requirements { 652 drop := make(map[string]bool) 653 for _, m := range replace { 654 drop[m.Path] = true 655 } 656 var roots []module.Version 657 for _, m := range rs.rootModules { 658 if !drop[m.Path] { 659 roots = append(roots, m) 660 } 661 } 662 roots = append(roots, replace...) 663 gover.ModSort(roots) 664 return newRequirements(loaderstate, rs.pruning, roots, rs.direct) 665 } 666 667 // A ConstraintError describes inconsistent constraints in EditBuildList 668 type ConstraintError struct { 669 // Conflict lists the source of the conflict for each version in mustSelect 670 // that could not be selected due to the requirements of some other version in 671 // mustSelect. 672 Conflicts []Conflict 673 } 674 675 func (e *ConstraintError) Error() string { 676 b := new(strings.Builder) 677 b.WriteString("version constraints conflict:") 678 for _, c := range e.Conflicts { 679 fmt.Fprintf(b, "\n\t%s", c.Summary()) 680 } 681 return b.String() 682 } 683 684 // A Conflict is a path of requirements starting at a root or proposed root in 685 // the requirement graph, explaining why that root either causes a module passed 686 // in the mustSelect list to EditBuildList to be unattainable, or introduces an 687 // unresolvable error in loading the requirement graph. 688 type Conflict struct { 689 // Path is a path of requirements starting at some module version passed in 690 // the mustSelect argument and ending at a module whose requirements make that 691 // version unacceptable. (Path always has len ≥ 1.) 692 Path []module.Version 693 694 // If Err is nil, Constraint is a module version passed in the mustSelect 695 // argument that has the same module path as, and a lower version than, 696 // the last element of the Path slice. 697 Constraint module.Version 698 699 // If Constraint is unset, Err is an error encountered when loading the 700 // requirements of the last element in Path. 701 Err error 702 } 703 704 // UnwrapModuleError returns c.Err, but unwraps it if it is a module.ModuleError 705 // with a version and path matching the last entry in the Path slice. 706 func (c Conflict) UnwrapModuleError() error { 707 me, ok := c.Err.(*module.ModuleError) 708 if ok && len(c.Path) > 0 { 709 last := c.Path[len(c.Path)-1] 710 if me.Path == last.Path && me.Version == last.Version { 711 return me.Err 712 } 713 } 714 return c.Err 715 } 716 717 // Summary returns a string that describes only the first and last modules in 718 // the conflict path. 719 func (c Conflict) Summary() string { 720 if len(c.Path) == 0 { 721 return "(internal error: invalid Conflict struct)" 722 } 723 first := c.Path[0] 724 last := c.Path[len(c.Path)-1] 725 if len(c.Path) == 1 { 726 if c.Err != nil { 727 return fmt.Sprintf("%s: %v", first, c.UnwrapModuleError()) 728 } 729 return fmt.Sprintf("%s is above %s", first, c.Constraint.Version) 730 } 731 732 adverb := "" 733 if len(c.Path) > 2 { 734 adverb = "indirectly " 735 } 736 if c.Err != nil { 737 return fmt.Sprintf("%s %srequires %s: %v", first, adverb, last, c.UnwrapModuleError()) 738 } 739 return fmt.Sprintf("%s %srequires %s, but %s is requested", first, adverb, last, c.Constraint.Version) 740 } 741 742 // String returns a string that describes the full conflict path. 743 func (c Conflict) String() string { 744 if len(c.Path) == 0 { 745 return "(internal error: invalid Conflict struct)" 746 } 747 b := new(strings.Builder) 748 fmt.Fprintf(b, "%v", c.Path[0]) 749 if len(c.Path) == 1 { 750 fmt.Fprintf(b, " found") 751 } else { 752 for _, r := range c.Path[1:] { 753 fmt.Fprintf(b, " requires\n\t%v", r) 754 } 755 } 756 if c.Constraint != (module.Version{}) { 757 fmt.Fprintf(b, ", but %v is requested", c.Constraint.Version) 758 } 759 if c.Err != nil { 760 fmt.Fprintf(b, ": %v", c.UnwrapModuleError()) 761 } 762 return b.String() 763 } 764 765 // tidyRoots trims the root dependencies to the minimal requirements needed to 766 // both retain the same versions of all packages in pkgs and satisfy the 767 // graph-pruning invariants (if applicable). 768 func tidyRoots(loaderstate *State, ctx context.Context, rs *Requirements, pkgs []*loadPkg) (*Requirements, error) { 769 mainModule := loaderstate.MainModules.mustGetSingleMainModule(loaderstate) 770 if rs.pruning == unpruned { 771 return tidyUnprunedRoots(loaderstate, ctx, mainModule, rs, pkgs) 772 } 773 return tidyPrunedRoots(loaderstate, ctx, mainModule, rs, pkgs) 774 } 775 776 func updateRoots(loaderstate *State, ctx context.Context, direct map[string]bool, rs *Requirements, pkgs []*loadPkg, add []module.Version, rootsImported bool) (*Requirements, error) { 777 switch rs.pruning { 778 case unpruned: 779 return updateUnprunedRoots(loaderstate, ctx, direct, rs, add) 780 case pruned: 781 return updatePrunedRoots(loaderstate, ctx, direct, rs, pkgs, add, rootsImported) 782 case workspace: 783 return updateWorkspaceRoots(loaderstate, ctx, direct, rs, add) 784 default: 785 panic(fmt.Sprintf("unsupported pruning mode: %v", rs.pruning)) 786 } 787 } 788 789 func updateWorkspaceRoots(loaderstate *State, ctx context.Context, direct map[string]bool, rs *Requirements, add []module.Version) (*Requirements, error) { 790 if len(add) != 0 { 791 // add should be empty in workspace mode because workspace mode implies 792 // -mod=readonly, which in turn implies no new requirements. The code path 793 // that would result in add being non-empty returns an error before it 794 // reaches this point: The set of modules to add comes from 795 // resolveMissingImports, which in turn resolves each package by calling 796 // queryImport. But queryImport explicitly checks for -mod=readonly, and 797 // return an error. 798 panic("add is not empty") 799 } 800 return newRequirements(loaderstate, workspace, rs.rootModules, direct), nil 801 } 802 803 // tidyPrunedRoots returns a minimal set of root requirements that maintains the 804 // invariants of the go.mod file needed to support graph pruning for the given 805 // packages: 806 // 807 // 1. For each package marked with pkgInAll, the module path that provided that 808 // package is included as a root. 809 // 2. For all packages, the module that provided that package either remains 810 // selected at the same version or is upgraded by the dependencies of a 811 // root. 812 // 813 // If any module that provided a package has been upgraded above its previous 814 // version, the caller may need to reload and recompute the package graph. 815 // 816 // To ensure that the loading process eventually converges, the caller should 817 // add any needed roots from the tidy root set (without removing existing untidy 818 // roots) until the set of roots has converged. 819 func tidyPrunedRoots(loaderstate *State, ctx context.Context, mainModule module.Version, old *Requirements, pkgs []*loadPkg) (*Requirements, error) { 820 var ( 821 roots []module.Version 822 pathIsRoot = map[string]bool{mainModule.Path: true} 823 ) 824 if v, ok := old.rootSelected(loaderstate, "go"); ok { 825 roots = append(roots, module.Version{Path: "go", Version: v}) 826 pathIsRoot["go"] = true 827 } 828 if v, ok := old.rootSelected(loaderstate, "toolchain"); ok { 829 roots = append(roots, module.Version{Path: "toolchain", Version: v}) 830 pathIsRoot["toolchain"] = true 831 } 832 // We start by adding roots for every package in "all". 833 // 834 // Once that is done, we may still need to add more roots to cover upgraded or 835 // otherwise-missing test dependencies for packages in "all". For those test 836 // dependencies, we prefer to add roots for packages with shorter import 837 // stacks first, on the theory that the module requirements for those will 838 // tend to fill in the requirements for their transitive imports (which have 839 // deeper import stacks). So we add the missing dependencies for one depth at 840 // a time, starting with the packages actually in "all" and expanding outwards 841 // until we have scanned every package that was loaded. 842 var ( 843 queue []*loadPkg 844 queued = map[*loadPkg]bool{} 845 ) 846 for _, pkg := range pkgs { 847 if !pkg.flags.has(pkgInAll) { 848 continue 849 } 850 if pkg.fromExternalModule(loaderstate) && !pathIsRoot[pkg.mod.Path] { 851 roots = append(roots, pkg.mod) 852 pathIsRoot[pkg.mod.Path] = true 853 } 854 queue = append(queue, pkg) 855 queued[pkg] = true 856 } 857 gover.ModSort(roots) 858 tidy := newRequirements(loaderstate, pruned, roots, old.direct) 859 860 for len(queue) > 0 { 861 roots = tidy.rootModules 862 mg, err := tidy.Graph(loaderstate, ctx) 863 if err != nil { 864 return nil, err 865 } 866 867 prevQueue := queue 868 queue = nil 869 for _, pkg := range prevQueue { 870 m := pkg.mod 871 if m.Path == "" { 872 continue 873 } 874 for _, dep := range pkg.imports { 875 if !queued[dep] { 876 queue = append(queue, dep) 877 queued[dep] = true 878 } 879 } 880 if pkg.test != nil && !queued[pkg.test] { 881 queue = append(queue, pkg.test) 882 queued[pkg.test] = true 883 } 884 885 if !pathIsRoot[m.Path] { 886 if s := mg.Selected(m.Path); gover.ModCompare(m.Path, s, m.Version) < 0 { 887 roots = append(roots, m) 888 pathIsRoot[m.Path] = true 889 } 890 } 891 } 892 893 if len(roots) > len(tidy.rootModules) { 894 gover.ModSort(roots) 895 tidy = newRequirements(loaderstate, pruned, roots, tidy.direct) 896 } 897 } 898 899 roots = tidy.rootModules 900 _, err := tidy.Graph(loaderstate, ctx) 901 if err != nil { 902 return nil, err 903 } 904 905 // We try to avoid adding explicit requirements for test-only dependencies of 906 // packages in external modules. However, if we drop the explicit 907 // requirements, that may change an import from unambiguous (due to lazy 908 // module loading) to ambiguous (because lazy module loading no longer 909 // disambiguates it). For any package that has become ambiguous, we try 910 // to fix it by promoting its module to an explicit root. 911 // (See https://go.dev/issue/60313.) 912 q := par.NewQueue(runtime.GOMAXPROCS(0)) 913 for { 914 var disambiguateRoot sync.Map 915 for _, pkg := range pkgs { 916 if pkg.mod.Path == "" || pathIsRoot[pkg.mod.Path] { 917 // Lazy module loading will cause pkg.mod to be checked before any other modules 918 // that are only indirectly required. It is as unambiguous as possible. 919 continue 920 } 921 pkg := pkg 922 q.Add(func() { 923 skipModFile := true 924 _, _, _, _, err := importFromModules(loaderstate, ctx, pkg.path, tidy, nil, skipModFile) 925 if _, ok := errors.AsType[*AmbiguousImportError](err); ok { 926 disambiguateRoot.Store(pkg.mod, true) 927 } 928 }) 929 } 930 <-q.Idle() 931 932 disambiguateRoot.Range(func(k, _ any) bool { 933 m := k.(module.Version) 934 roots = append(roots, m) 935 pathIsRoot[m.Path] = true 936 return true 937 }) 938 939 if len(roots) > len(tidy.rootModules) { 940 module.Sort(roots) 941 tidy = newRequirements(loaderstate, pruned, roots, tidy.direct) 942 _, err = tidy.Graph(loaderstate, ctx) 943 if err != nil { 944 return nil, err 945 } 946 // Adding these roots may have pulled additional modules into the module 947 // graph, causing additional packages to become ambiguous. Keep iterating 948 // until we reach a fixed point. 949 continue 950 } 951 952 break 953 } 954 955 return tidy, nil 956 } 957 958 // updatePrunedRoots returns a set of root requirements that maintains the 959 // invariants of the go.mod file needed to support graph pruning: 960 // 961 // 1. The selected version of the module providing each package marked with 962 // either pkgInAll or pkgIsRoot is included as a root. 963 // Note that certain root patterns (such as '...') may explode the root set 964 // to contain every module that provides any package imported (or merely 965 // required) by any other module. 966 // 2. Each root appears only once, at the selected version of its path 967 // (if rs.graph is non-nil) or at the highest version otherwise present as a 968 // root (otherwise). 969 // 3. Every module path that appears as a root in rs remains a root. 970 // 4. Every version in add is selected at its given version unless upgraded by 971 // (the dependencies of) an existing root or another module in add. 972 // 973 // The packages in pkgs are assumed to have been loaded from either the roots of 974 // rs or the modules selected in the graph of rs. 975 // 976 // The above invariants together imply the graph-pruning invariants for the 977 // go.mod file: 978 // 979 // 1. (The import invariant.) Every module that provides a package transitively 980 // imported by any package or test in the main module is included as a root. 981 // This follows by induction from (1) and (3) above. Transitively-imported 982 // packages loaded during this invocation are marked with pkgInAll (1), 983 // and by hypothesis any transitively-imported packages loaded in previous 984 // invocations were already roots in rs (3). 985 // 986 // 2. (The argument invariant.) Every module that provides a package matching 987 // an explicit package pattern is included as a root. This follows directly 988 // from (1): packages matching explicit package patterns are marked with 989 // pkgIsRoot. 990 // 991 // 3. (The completeness invariant.) Every module that contributed any package 992 // to the build is required by either the main module or one of the modules 993 // it requires explicitly. This invariant is left up to the caller, who must 994 // not load packages from outside the module graph but may add roots to the 995 // graph, but is facilitated by (3). If the caller adds roots to the graph in 996 // order to resolve missing packages, then updatePrunedRoots will retain them, 997 // the selected versions of those roots cannot regress, and they will 998 // eventually be written back to the main module's go.mod file. 999 // 1000 // (See https://golang.org/design/36460-lazy-module-loading#invariants for more 1001 // detail.) 1002 func updatePrunedRoots(loaderstate *State, ctx context.Context, direct map[string]bool, rs *Requirements, pkgs []*loadPkg, add []module.Version, rootsImported bool) (*Requirements, error) { 1003 roots := rs.rootModules 1004 rootsUpgraded := false 1005 1006 spotCheckRoot := map[module.Version]bool{} 1007 1008 // “The selected version of the module providing each package marked with 1009 // either pkgInAll or pkgIsRoot is included as a root.” 1010 needSort := false 1011 for _, pkg := range pkgs { 1012 if !pkg.fromExternalModule(loaderstate) { 1013 // pkg was not loaded from a module dependency, so we don't need 1014 // to do anything special to maintain that dependency. 1015 continue 1016 } 1017 1018 switch { 1019 case pkg.flags.has(pkgInAll): 1020 // pkg is transitively imported by a package or test in the main module. 1021 // We need to promote the module that maintains it to a root: if some 1022 // other module depends on the main module, and that other module also 1023 // uses a pruned module graph, it will expect to find all of our 1024 // transitive dependencies by reading just our go.mod file, not the go.mod 1025 // files of everything we depend on. 1026 // 1027 // (This is the “import invariant” that makes graph pruning possible.) 1028 1029 case rootsImported && pkg.flags.has(pkgFromRoot): 1030 // pkg is a transitive dependency of some root, and we are treating the 1031 // roots as if they are imported by the main module (as in 'go get'). 1032 1033 case pkg.flags.has(pkgIsRoot): 1034 // pkg is a root of the package-import graph. (Generally this means that 1035 // it matches a command-line argument.) We want future invocations of the 1036 // 'go' command — such as 'go test' on the same package — to continue to 1037 // use the same versions of its dependencies that we are using right now. 1038 // So we need to bring this package's dependencies inside the pruned 1039 // module graph. 1040 // 1041 // Making the module containing this package a root of the module graph 1042 // does exactly that: if the module containing the package supports graph 1043 // pruning then it should satisfy the import invariant itself, so all of 1044 // its dependencies should be in its go.mod file, and if the module 1045 // containing the package does not support pruning then if we make it a 1046 // root we will load all of its (unpruned) transitive dependencies into 1047 // the module graph. 1048 // 1049 // (This is the “argument invariant”, and is important for 1050 // reproducibility.) 1051 1052 default: 1053 // pkg is a dependency of some other package outside of the main module. 1054 // As far as we know it's not relevant to the main module (and thus not 1055 // relevant to consumers of the main module either), and its dependencies 1056 // should already be in the module graph — included in the dependencies of 1057 // the package that imported it. 1058 continue 1059 } 1060 1061 if _, ok := rs.rootSelected(loaderstate, pkg.mod.Path); ok { 1062 // It is possible that the main module's go.mod file is incomplete or 1063 // otherwise erroneous — for example, perhaps the author forgot to 'git 1064 // add' their updated go.mod file after adding a new package import, or 1065 // perhaps they made an edit to the go.mod file using a third-party tool 1066 // ('git merge'?) that doesn't maintain consistency for module 1067 // dependencies. If that happens, ideally we want to detect the missing 1068 // requirements and fix them up here. 1069 // 1070 // However, we also need to be careful not to be too aggressive. For 1071 // transitive dependencies of external tests, the go.mod file for the 1072 // module containing the test itself is expected to provide all of the 1073 // relevant dependencies, and we explicitly don't want to pull in 1074 // requirements on *irrelevant* requirements that happen to occur in the 1075 // go.mod files for these transitive-test-only dependencies. (See the test 1076 // in mod_lazy_test_horizon.txt for a concrete example). 1077 // 1078 // The “goldilocks zone” seems to be to spot-check exactly the same 1079 // modules that we promote to explicit roots: namely, those that provide 1080 // packages transitively imported by the main module, and those that 1081 // provide roots of the package-import graph. That will catch erroneous 1082 // edits to the main module's go.mod file and inconsistent requirements in 1083 // dependencies that provide imported packages, but will ignore erroneous 1084 // or misleading requirements in dependencies that aren't obviously 1085 // relevant to the packages in the main module. 1086 spotCheckRoot[pkg.mod] = true 1087 } else { 1088 roots = append(roots, pkg.mod) 1089 rootsUpgraded = true 1090 // The roots slice was initially sorted because rs.rootModules was sorted, 1091 // but the root we just added could be out of order. 1092 needSort = true 1093 } 1094 } 1095 1096 for _, m := range add { 1097 if v, ok := rs.rootSelected(loaderstate, m.Path); !ok || gover.ModCompare(m.Path, v, m.Version) < 0 { 1098 roots = append(roots, m) 1099 rootsUpgraded = true 1100 needSort = true 1101 } 1102 } 1103 if needSort { 1104 gover.ModSort(roots) 1105 } 1106 1107 // "Each root appears only once, at the selected version of its path ….” 1108 for { 1109 var mg *ModuleGraph 1110 if rootsUpgraded { 1111 // We've added or upgraded one or more roots, so load the full module 1112 // graph so that we can update those roots to be consistent with other 1113 // requirements. 1114 if mustHaveCompleteRequirements(loaderstate) { 1115 // Our changes to the roots may have moved dependencies into or out of 1116 // the graph-pruning horizon, which could in turn change the selected 1117 // versions of other modules. (For pruned modules adding or removing an 1118 // explicit root is a semantic change, not just a cosmetic one.) 1119 return rs, errGoModDirty 1120 } 1121 1122 rs = newRequirements(loaderstate, pruned, roots, direct) 1123 var err error 1124 mg, err = rs.Graph(loaderstate, ctx) 1125 if err != nil { 1126 return rs, err 1127 } 1128 } else { 1129 // Since none of the roots have been upgraded, we have no reason to 1130 // suspect that they are inconsistent with the requirements of any other 1131 // roots. Only look at the full module graph if we've already loaded it; 1132 // otherwise, just spot-check the explicit requirements of the roots from 1133 // which we loaded packages. 1134 if rs.graph.Load() != nil { 1135 // We've already loaded the full module graph, which includes the 1136 // requirements of all of the root modules — even the transitive 1137 // requirements, if they are unpruned! 1138 mg, _ = rs.Graph(loaderstate, ctx) 1139 } else if cfg.BuildMod == "vendor" { 1140 // We can't spot-check the requirements of other modules because we 1141 // don't in general have their go.mod files available in the vendor 1142 // directory. (Fortunately this case is impossible, because mg.graph is 1143 // always non-nil in vendor mode!) 1144 panic("internal error: rs.graph is unexpectedly nil with -mod=vendor") 1145 } else if !spotCheckRoots(loaderstate, ctx, rs, spotCheckRoot) { 1146 // We spot-checked the explicit requirements of the roots that are 1147 // relevant to the packages we've loaded. Unfortunately, they're 1148 // inconsistent in some way; we need to load the full module graph 1149 // so that we can fix the roots properly. 1150 var err error 1151 mg, err = rs.Graph(loaderstate, ctx) 1152 if err != nil { 1153 return rs, err 1154 } 1155 } 1156 } 1157 1158 roots = make([]module.Version, 0, len(rs.rootModules)) 1159 rootsUpgraded = false 1160 inRootPaths := make(map[string]bool, len(rs.rootModules)+1) 1161 for _, mm := range loaderstate.MainModules.Versions() { 1162 inRootPaths[mm.Path] = true 1163 } 1164 for _, m := range rs.rootModules { 1165 if inRootPaths[m.Path] { 1166 // This root specifies a redundant path. We already retained the 1167 // selected version of this path when we saw it before, so omit the 1168 // redundant copy regardless of its version. 1169 // 1170 // When we read the full module graph, we include the dependencies of 1171 // every root even if that root is redundant. That better preserves 1172 // reproducibility if, say, some automated tool adds a redundant 1173 // 'require' line and then runs 'go mod tidy' to try to make everything 1174 // consistent, since the requirements of the older version are carried 1175 // over. 1176 // 1177 // So omitting a root that was previously present may *reduce* the 1178 // selected versions of non-roots, but merely removing a requirement 1179 // cannot *increase* the selected versions of other roots as a result — 1180 // we don't need to mark this change as an upgrade. (This particular 1181 // change cannot invalidate any other roots.) 1182 continue 1183 } 1184 1185 var v string 1186 if mg == nil { 1187 v, _ = rs.rootSelected(loaderstate, m.Path) 1188 } else { 1189 v = mg.Selected(m.Path) 1190 } 1191 roots = append(roots, module.Version{Path: m.Path, Version: v}) 1192 inRootPaths[m.Path] = true 1193 if v != m.Version { 1194 rootsUpgraded = true 1195 } 1196 } 1197 // Note that rs.rootModules was already sorted by module path and version, 1198 // and we appended to the roots slice in the same order and guaranteed that 1199 // each path has only one version, so roots is also sorted by module path 1200 // and (trivially) version. 1201 1202 if !rootsUpgraded { 1203 if cfg.BuildMod != "mod" { 1204 // The only changes to the root set (if any) were to remove duplicates. 1205 // The requirements are consistent (if perhaps redundant), so keep the 1206 // original rs to preserve its ModuleGraph. 1207 return rs, nil 1208 } 1209 // The root set has converged: every root going into this iteration was 1210 // already at its selected version, although we have removed other 1211 // (redundant) roots for the same path. 1212 break 1213 } 1214 } 1215 1216 if rs.pruning == pruned && slices.Equal(roots, rs.rootModules) && maps.Equal(direct, rs.direct) { 1217 // The root set is unchanged and rs was already pruned, so keep rs to 1218 // preserve its cached ModuleGraph (if any). 1219 return rs, nil 1220 } 1221 return newRequirements(loaderstate, pruned, roots, direct), nil 1222 } 1223 1224 // spotCheckRoots reports whether the versions of the roots in rs satisfy the 1225 // explicit requirements of the modules in mods. 1226 func spotCheckRoots(loaderstate *State, ctx context.Context, rs *Requirements, mods map[module.Version]bool) bool { 1227 ctx, cancel := context.WithCancel(ctx) 1228 defer cancel() 1229 1230 work := par.NewQueue(runtime.GOMAXPROCS(0)) 1231 for m := range mods { 1232 m := m 1233 work.Add(func() { 1234 if ctx.Err() != nil { 1235 return 1236 } 1237 1238 summary, err := goModSummary(loaderstate, m) 1239 if err != nil { 1240 cancel() 1241 return 1242 } 1243 1244 for _, r := range summary.require { 1245 if v, ok := rs.rootSelected(loaderstate, r.Path); ok && gover.ModCompare(r.Path, v, r.Version) < 0 { 1246 cancel() 1247 return 1248 } 1249 } 1250 }) 1251 } 1252 <-work.Idle() 1253 1254 if ctx.Err() != nil { 1255 // Either we failed a spot-check, or the caller no longer cares about our 1256 // answer anyway. 1257 return false 1258 } 1259 1260 return true 1261 } 1262 1263 // tidyUnprunedRoots returns a minimal set of root requirements that maintains 1264 // the selected version of every module that provided or lexically could have 1265 // provided a package in pkgs, and includes the selected version of every such 1266 // module in direct as a root. 1267 func tidyUnprunedRoots(loaderstate *State, ctx context.Context, mainModule module.Version, old *Requirements, pkgs []*loadPkg) (*Requirements, error) { 1268 var ( 1269 // keep is a set of modules that provide packages or are needed to 1270 // disambiguate imports. 1271 keep []module.Version 1272 keptPath = map[string]bool{} 1273 1274 // rootPaths is a list of module paths that provide packages directly 1275 // imported from the main module. They should be included as roots. 1276 rootPaths []string 1277 inRootPaths = map[string]bool{} 1278 1279 // altMods is a set of paths of modules that lexically could have provided 1280 // imported packages. It may be okay to remove these from the list of 1281 // explicit requirements if that removes them from the module graph. If they 1282 // are present in the module graph reachable from rootPaths, they must not 1283 // be at a lower version. That could cause a missing sum error or a new 1284 // import ambiguity. 1285 // 1286 // For example, suppose a developer rewrites imports from example.com/m to 1287 // example.com/m/v2, then runs 'go mod tidy'. Tidy may delete the 1288 // requirement on example.com/m if there is no other transitive requirement 1289 // on it. However, if example.com/m were downgraded to a version not in 1290 // go.sum, when package example.com/m/v2/p is loaded, we'd get an error 1291 // trying to disambiguate the import, since we can't check example.com/m 1292 // without its sum. See #47738. 1293 altMods = map[string]string{} 1294 ) 1295 if v, ok := old.rootSelected(loaderstate, "go"); ok { 1296 keep = append(keep, module.Version{Path: "go", Version: v}) 1297 keptPath["go"] = true 1298 } 1299 if v, ok := old.rootSelected(loaderstate, "toolchain"); ok { 1300 keep = append(keep, module.Version{Path: "toolchain", Version: v}) 1301 keptPath["toolchain"] = true 1302 } 1303 for _, pkg := range pkgs { 1304 if !pkg.fromExternalModule(loaderstate) { 1305 continue 1306 } 1307 if m := pkg.mod; !keptPath[m.Path] { 1308 keep = append(keep, m) 1309 keptPath[m.Path] = true 1310 if old.direct[m.Path] && !inRootPaths[m.Path] { 1311 rootPaths = append(rootPaths, m.Path) 1312 inRootPaths[m.Path] = true 1313 } 1314 } 1315 for _, m := range pkg.altMods { 1316 altMods[m.Path] = m.Version 1317 } 1318 } 1319 1320 // Construct a build list with a minimal set of roots. 1321 // This may remove or downgrade modules in altMods. 1322 reqs := &mvsReqs{loaderstate: loaderstate, roots: keep} 1323 min, err := mvs.Req(mainModule, rootPaths, reqs) 1324 if err != nil { 1325 return nil, err 1326 } 1327 buildList, err := mvs.BuildList([]module.Version{mainModule}, reqs) 1328 if err != nil { 1329 return nil, err 1330 } 1331 1332 // Check if modules in altMods were downgraded but not removed. 1333 // If so, add them to roots, which will retain an "// indirect" requirement 1334 // in go.mod. See comment on altMods above. 1335 keptAltMod := false 1336 for _, m := range buildList { 1337 if v, ok := altMods[m.Path]; ok && gover.ModCompare(m.Path, m.Version, v) < 0 { 1338 keep = append(keep, module.Version{Path: m.Path, Version: v}) 1339 keptAltMod = true 1340 } 1341 } 1342 if keptAltMod { 1343 // We must run mvs.Req again instead of simply adding altMods to min. 1344 // It's possible that a requirement in altMods makes some other 1345 // explicit indirect requirement unnecessary. 1346 reqs.roots = keep 1347 min, err = mvs.Req(mainModule, rootPaths, reqs) 1348 if err != nil { 1349 return nil, err 1350 } 1351 } 1352 1353 return newRequirements(loaderstate, unpruned, min, old.direct), nil 1354 } 1355 1356 // updateUnprunedRoots returns a set of root requirements that includes the selected 1357 // version of every module path in direct as a root, and maintains the selected 1358 // version of every module selected in the graph of rs. 1359 // 1360 // The roots are updated such that: 1361 // 1362 // 1. The selected version of every module path in direct is included as a root 1363 // (if it is not "none"). 1364 // 2. Each root is the selected version of its path. (We say that such a root 1365 // set is “consistent”.) 1366 // 3. Every version selected in the graph of rs remains selected unless upgraded 1367 // by a dependency in add. 1368 // 4. Every version in add is selected at its given version unless upgraded by 1369 // (the dependencies of) an existing root or another module in add. 1370 func updateUnprunedRoots(loaderstate *State, ctx context.Context, direct map[string]bool, rs *Requirements, add []module.Version) (*Requirements, error) { 1371 mg, err := rs.Graph(loaderstate, ctx) 1372 if err != nil { 1373 // We can't ignore errors in the module graph even if the user passed the -e 1374 // flag to try to push past them. If we can't load the complete module 1375 // dependencies, then we can't reliably compute a minimal subset of them. 1376 return rs, err 1377 } 1378 1379 if mustHaveCompleteRequirements(loaderstate) { 1380 // Instead of actually updating the requirements, just check that no updates 1381 // are needed. 1382 if rs == nil { 1383 // We're being asked to reconstruct the requirements from scratch, 1384 // but we aren't even allowed to modify them. 1385 return rs, errGoModDirty 1386 } 1387 for _, m := range rs.rootModules { 1388 if m.Version != mg.Selected(m.Path) { 1389 // The root version v is misleading: the actual selected version is higher. 1390 return rs, errGoModDirty 1391 } 1392 } 1393 for _, m := range add { 1394 if m.Version != mg.Selected(m.Path) { 1395 return rs, errGoModDirty 1396 } 1397 } 1398 for mPath := range direct { 1399 if _, ok := rs.rootSelected(loaderstate, mPath); !ok { 1400 // Module m is supposed to be listed explicitly, but isn't. 1401 // 1402 // Note that this condition is also detected (and logged with more 1403 // detail) earlier during package loading, so it shouldn't actually be 1404 // possible at this point — this is just a defense in depth. 1405 return rs, errGoModDirty 1406 } 1407 } 1408 1409 // No explicit roots are missing and all roots are already at the versions 1410 // we want to keep. Any other changes we would make are purely cosmetic, 1411 // such as pruning redundant indirect dependencies. Per issue #34822, we 1412 // ignore cosmetic changes when we cannot update the go.mod file. 1413 return rs, nil 1414 } 1415 1416 var ( 1417 rootPaths []string // module paths that should be included as roots 1418 inRootPaths = map[string]bool{} 1419 ) 1420 for _, root := range rs.rootModules { 1421 // If the selected version of the root is the same as what was already 1422 // listed in the go.mod file, retain it as a root (even if redundant) to 1423 // avoid unnecessary churn. (See https://golang.org/issue/34822.) 1424 // 1425 // We do this even for indirect requirements, since we don't know why they 1426 // were added and they could become direct at any time. 1427 if !inRootPaths[root.Path] && mg.Selected(root.Path) == root.Version { 1428 rootPaths = append(rootPaths, root.Path) 1429 inRootPaths[root.Path] = true 1430 } 1431 } 1432 1433 // “The selected version of every module path in direct is included as a root.” 1434 // 1435 // This is only for convenience and clarity for end users: in an unpruned module, 1436 // the choice of explicit vs. implicit dependency has no impact on MVS 1437 // selection (for itself or any other module). 1438 keep := append(mg.BuildList()[loaderstate.MainModules.Len():], add...) 1439 for _, m := range keep { 1440 if direct[m.Path] && !inRootPaths[m.Path] { 1441 rootPaths = append(rootPaths, m.Path) 1442 inRootPaths[m.Path] = true 1443 } 1444 } 1445 1446 var roots []module.Version 1447 for _, mainModule := range loaderstate.MainModules.Versions() { 1448 min, err := mvs.Req(mainModule, rootPaths, &mvsReqs{loaderstate: loaderstate, roots: keep}) 1449 if err != nil { 1450 return rs, err 1451 } 1452 roots = append(roots, min...) 1453 } 1454 if loaderstate.MainModules.Len() > 1 { 1455 gover.ModSort(roots) 1456 } 1457 if rs.pruning == unpruned && slices.Equal(roots, rs.rootModules) && maps.Equal(direct, rs.direct) { 1458 // The root set is unchanged and rs was already unpruned, so keep rs to 1459 // preserve its cached ModuleGraph (if any). 1460 return rs, nil 1461 } 1462 1463 return newRequirements(loaderstate, unpruned, roots, direct), nil 1464 } 1465 1466 // convertPruning returns a version of rs with the given pruning behavior. 1467 // If rs already has the given pruning, convertPruning returns rs unmodified. 1468 func convertPruning(loaderstate *State, ctx context.Context, rs *Requirements, pruning modPruning) (*Requirements, error) { 1469 if rs.pruning == pruning { 1470 return rs, nil 1471 } else if rs.pruning == workspace || pruning == workspace { 1472 panic("attempting to convert to/from workspace pruning and another pruning type") 1473 } 1474 1475 if pruning == unpruned { 1476 // We are converting a pruned module to an unpruned one. The roots of a 1477 // pruned module graph are a superset of the roots of an unpruned one, so 1478 // we don't need to add any new roots — we just need to drop the ones that 1479 // are redundant, which is exactly what updateUnprunedRoots does. 1480 return updateUnprunedRoots(loaderstate, ctx, rs.direct, rs, nil) 1481 } 1482 1483 // We are converting an unpruned module to a pruned one. 1484 // 1485 // An unpruned module graph includes the transitive dependencies of every 1486 // module in the build list. As it turns out, we can express that as a pruned 1487 // root set! “Include the transitive dependencies of every module in the build 1488 // list” is exactly what happens in a pruned module if we promote every module 1489 // in the build list to a root. 1490 mg, err := rs.Graph(loaderstate, ctx) 1491 if err != nil { 1492 return rs, err 1493 } 1494 return newRequirements(loaderstate, pruned, mg.BuildList()[loaderstate.MainModules.Len():], rs.direct), nil 1495 } 1496