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