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