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