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 5package modload 6 7import ( 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. 27func 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. 32type 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. 82type 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. 95var 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. 107func 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. 155func (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. 209func (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. 223func (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. 240func (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. 251func (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. 260type 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. 270type summaryError struct { 271 summary *modFileSummary 272 err error 273} 274 275var 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. 282func 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 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 if hasError { 390 return mg, mg.findError() 391 } 392 return mg, nil 393} 394 395// RequiredBy returns the dependencies required by module m in the graph, 396// or ok=false if module m's dependencies are pruned out. 397// 398// The caller must not modify the returned slice, but may safely append to it 399// and may rely on it not to be modified. 400func (mg *ModuleGraph) RequiredBy(m module.Version) (reqs []module.Version, ok bool) { 401 return mg.g.RequiredBy(m) 402} 403 404// Selected returns the selected version of the module with the given path. 405// 406// If no version is selected, Selected returns version "none". 407func (mg *ModuleGraph) Selected(path string) (version string) { 408 return mg.g.Selected(path) 409} 410 411// WalkBreadthFirst invokes f once, in breadth-first order, for each module 412// version other than "none" that appears in the graph, regardless of whether 413// that version is selected. 414func (mg *ModuleGraph) WalkBreadthFirst(f func(m module.Version)) { 415 mg.g.WalkBreadthFirst(f) 416} 417 418// BuildList returns the selected versions of all modules present in the graph, 419// beginning with Target. 420// 421// The order of the remaining elements in the list is deterministic 422// but arbitrary. 423// 424// The caller must not modify the returned list, but may safely append to it 425// and may rely on it not to be modified. 426func (mg *ModuleGraph) BuildList() []module.Version { 427 mg.buildListOnce.Do(func() { 428 mg.buildList = capVersionSlice(mg.g.BuildList()) 429 }) 430 return mg.buildList 431} 432 433func (mg *ModuleGraph) findError() error { 434 errStack := mg.g.FindPath(func(m module.Version) bool { 435 cached := mg.loadCache.Get(m) 436 return cached != nil && cached.(summaryError).err != nil 437 }) 438 if len(errStack) > 0 { 439 err := mg.loadCache.Get(errStack[len(errStack)-1]).(summaryError).err 440 var noUpgrade func(from, to module.Version) bool 441 return mvs.NewBuildListError(err, errStack, noUpgrade) 442 } 443 444 return nil 445} 446 447func (mg *ModuleGraph) allRootsSelected() bool { 448 var roots []module.Version 449 if inWorkspaceMode() { 450 roots = MainModules.Versions() 451 } else { 452 roots, _ = mg.g.RequiredBy(MainModules.mustGetSingleMainModule()) 453 } 454 for _, m := range roots { 455 if mg.Selected(m.Path) != m.Version { 456 return false 457 } 458 } 459 return true 460} 461 462// LoadModGraph loads and returns the graph of module dependencies of the main module, 463// without loading any packages. 464// 465// If the goVersion string is non-empty, the returned graph is the graph 466// as interpreted by the given Go version (instead of the version indicated 467// in the go.mod file). 468// 469// Modules are loaded automatically (and lazily) in LoadPackages: 470// LoadModGraph need only be called if LoadPackages is not, 471// typically in commands that care about modules but no particular package. 472func LoadModGraph(ctx context.Context, goVersion string) *ModuleGraph { 473 rs := LoadModFile(ctx) 474 475 if goVersion != "" { 476 pruning := pruningForGoVersion(goVersion) 477 if pruning == unpruned && rs.pruning != unpruned { 478 // Use newRequirements instead of convertDepth because convertDepth 479 // also updates roots; here, we want to report the unmodified roots 480 // even though they may seem inconsistent. 481 rs = newRequirements(unpruned, rs.rootModules, rs.direct) 482 } 483 484 mg, err := rs.Graph(ctx) 485 if err != nil { 486 base.Fatalf("go: %v", err) 487 } 488 return mg 489 } 490 491 rs, mg, err := expandGraph(ctx, rs) 492 if err != nil { 493 base.Fatalf("go: %v", err) 494 } 495 496 requirements = rs 497 498 return mg 499} 500 501// expandGraph loads the complete module graph from rs. 502// 503// If the complete graph reveals that some root of rs is not actually the 504// selected version of its path, expandGraph computes a new set of roots that 505// are consistent. (With a pruned module graph, this may result in upgrades to 506// other modules due to requirements that were previously pruned out.) 507// 508// expandGraph returns the updated roots, along with the module graph loaded 509// from those roots and any error encountered while loading that graph. 510// expandGraph returns non-nil requirements and a non-nil graph regardless of 511// errors. On error, the roots might not be updated to be consistent. 512func expandGraph(ctx context.Context, rs *Requirements) (*Requirements, *ModuleGraph, error) { 513 mg, mgErr := rs.Graph(ctx) 514 if mgErr != nil { 515 // Without the graph, we can't update the roots: we don't know which 516 // versions of transitive dependencies would be selected. 517 return rs, mg, mgErr 518 } 519 520 if !mg.allRootsSelected() { 521 // The roots of rs are not consistent with the rest of the graph. Update 522 // them. In an unpruned module this is a no-op for the build list as a whole — 523 // it just promotes what were previously transitive requirements to be 524 // roots — but in a pruned module it may pull in previously-irrelevant 525 // transitive dependencies. 526 527 newRS, rsErr := updateRoots(ctx, rs.direct, rs, nil, nil, false) 528 if rsErr != nil { 529 // Failed to update roots, perhaps because of an error in a transitive 530 // dependency needed for the update. Return the original Requirements 531 // instead. 532 return rs, mg, rsErr 533 } 534 rs = newRS 535 mg, mgErr = rs.Graph(ctx) 536 } 537 538 return rs, mg, mgErr 539} 540 541// EditBuildList edits the global build list by first adding every module in add 542// to the existing build list, then adjusting versions (and adding or removing 543// requirements as needed) until every module in mustSelect is selected at the 544// given version. 545// 546// (Note that the newly-added modules might not be selected in the resulting 547// build list: they could be lower than existing requirements or conflict with 548// versions in mustSelect.) 549// 550// If the versions listed in mustSelect are mutually incompatible (due to one of 551// the listed modules requiring a higher version of another), EditBuildList 552// returns a *ConstraintError and leaves the build list in its previous state. 553// 554// On success, EditBuildList reports whether the selected version of any module 555// in the build list may have been changed (possibly to or from "none") as a 556// result. 557func EditBuildList(ctx context.Context, add, mustSelect []module.Version) (changed bool, err error) { 558 rs, changed, err := editRequirements(ctx, LoadModFile(ctx), add, mustSelect) 559 if err != nil { 560 return false, err 561 } 562 requirements = rs 563 return changed, err 564} 565 566// A ConstraintError describes inconsistent constraints in EditBuildList 567type ConstraintError struct { 568 // Conflict lists the source of the conflict for each version in mustSelect 569 // that could not be selected due to the requirements of some other version in 570 // mustSelect. 571 Conflicts []Conflict 572} 573 574func (e *ConstraintError) Error() string { 575 b := new(strings.Builder) 576 b.WriteString("version constraints conflict:") 577 for _, c := range e.Conflicts { 578 fmt.Fprintf(b, "\n\t%v requires %v, but %v is requested", c.Source, c.Dep, c.Constraint) 579 } 580 return b.String() 581} 582 583// A Conflict documents that Source requires Dep, which conflicts with Constraint. 584// (That is, Dep has the same module path as Constraint but a higher version.) 585type Conflict struct { 586 Source module.Version 587 Dep module.Version 588 Constraint module.Version 589} 590 591// tidyRoots trims the root dependencies to the minimal requirements needed to 592// both retain the same versions of all packages in pkgs and satisfy the 593// graph-pruning invariants (if applicable). 594func tidyRoots(ctx context.Context, rs *Requirements, pkgs []*loadPkg) (*Requirements, error) { 595 mainModule := MainModules.mustGetSingleMainModule() 596 if rs.pruning == unpruned { 597 return tidyUnprunedRoots(ctx, mainModule, rs.direct, pkgs) 598 } 599 return tidyPrunedRoots(ctx, mainModule, rs.direct, pkgs) 600} 601 602func updateRoots(ctx context.Context, direct map[string]bool, rs *Requirements, pkgs []*loadPkg, add []module.Version, rootsImported bool) (*Requirements, error) { 603 switch rs.pruning { 604 case unpruned: 605 return updateUnprunedRoots(ctx, direct, rs, add) 606 case pruned: 607 return updatePrunedRoots(ctx, direct, rs, pkgs, add, rootsImported) 608 case workspace: 609 return updateWorkspaceRoots(ctx, rs, add) 610 default: 611 panic(fmt.Sprintf("unsupported pruning mode: %v", rs.pruning)) 612 } 613} 614 615func updateWorkspaceRoots(ctx context.Context, rs *Requirements, add []module.Version) (*Requirements, error) { 616 if len(add) != 0 { 617 // add should be empty in workspace mode because workspace mode implies 618 // -mod=readonly, which in turn implies no new requirements. The code path 619 // that would result in add being non-empty returns an error before it 620 // reaches this point: The set of modules to add comes from 621 // resolveMissingImports, which in turn resolves each package by calling 622 // queryImport. But queryImport explicitly checks for -mod=readonly, and 623 // return an error. 624 panic("add is not empty") 625 } 626 return rs, nil 627} 628 629// tidyPrunedRoots returns a minimal set of root requirements that maintains the 630// invariants of the go.mod file needed to support graph pruning for the given 631// packages: 632// 633// 1. For each package marked with pkgInAll, the module path that provided that 634// package is included as a root. 635// 2. For all packages, the module that provided that package either remains 636// selected at the same version or is upgraded by the dependencies of a 637// root. 638// 639// If any module that provided a package has been upgraded above its previous 640// version, the caller may need to reload and recompute the package graph. 641// 642// To ensure that the loading process eventually converges, the caller should 643// add any needed roots from the tidy root set (without removing existing untidy 644// roots) until the set of roots has converged. 645func tidyPrunedRoots(ctx context.Context, mainModule module.Version, direct map[string]bool, pkgs []*loadPkg) (*Requirements, error) { 646 var ( 647 roots []module.Version 648 pathIncluded = map[string]bool{mainModule.Path: true} 649 ) 650 // We start by adding roots for every package in "all". 651 // 652 // Once that is done, we may still need to add more roots to cover upgraded or 653 // otherwise-missing test dependencies for packages in "all". For those test 654 // dependencies, we prefer to add roots for packages with shorter import 655 // stacks first, on the theory that the module requirements for those will 656 // tend to fill in the requirements for their transitive imports (which have 657 // deeper import stacks). So we add the missing dependencies for one depth at 658 // a time, starting with the packages actually in "all" and expanding outwards 659 // until we have scanned every package that was loaded. 660 var ( 661 queue []*loadPkg 662 queued = map[*loadPkg]bool{} 663 ) 664 for _, pkg := range pkgs { 665 if !pkg.flags.has(pkgInAll) { 666 continue 667 } 668 if pkg.fromExternalModule() && !pathIncluded[pkg.mod.Path] { 669 roots = append(roots, pkg.mod) 670 pathIncluded[pkg.mod.Path] = true 671 } 672 queue = append(queue, pkg) 673 queued[pkg] = true 674 } 675 module.Sort(roots) 676 tidy := newRequirements(pruned, roots, direct) 677 678 for len(queue) > 0 { 679 roots = tidy.rootModules 680 mg, err := tidy.Graph(ctx) 681 if err != nil { 682 return nil, err 683 } 684 685 prevQueue := queue 686 queue = nil 687 for _, pkg := range prevQueue { 688 m := pkg.mod 689 if m.Path == "" { 690 continue 691 } 692 for _, dep := range pkg.imports { 693 if !queued[dep] { 694 queue = append(queue, dep) 695 queued[dep] = true 696 } 697 } 698 if pkg.test != nil && !queued[pkg.test] { 699 queue = append(queue, pkg.test) 700 queued[pkg.test] = true 701 } 702 if !pathIncluded[m.Path] { 703 if s := mg.Selected(m.Path); cmpVersion(s, m.Version) < 0 { 704 roots = append(roots, m) 705 } 706 pathIncluded[m.Path] = true 707 } 708 } 709 710 if len(roots) > len(tidy.rootModules) { 711 module.Sort(roots) 712 tidy = newRequirements(pruned, roots, tidy.direct) 713 } 714 } 715 716 _, err := tidy.Graph(ctx) 717 if err != nil { 718 return nil, err 719 } 720 return tidy, nil 721} 722 723// updatePrunedRoots returns a set of root requirements that maintains the 724// invariants of the go.mod file needed to support graph pruning: 725// 726// 1. The selected version of the module providing each package marked with 727// either pkgInAll or pkgIsRoot is included as a root. 728// Note that certain root patterns (such as '...') may explode the root set 729// to contain every module that provides any package imported (or merely 730// required) by any other module. 731// 2. Each root appears only once, at the selected version of its path 732// (if rs.graph is non-nil) or at the highest version otherwise present as a 733// root (otherwise). 734// 3. Every module path that appears as a root in rs remains a root. 735// 4. Every version in add is selected at its given version unless upgraded by 736// (the dependencies of) an existing root or another module in add. 737// 738// The packages in pkgs are assumed to have been loaded from either the roots of 739// rs or the modules selected in the graph of rs. 740// 741// The above invariants together imply the graph-pruning invariants for the 742// go.mod file: 743// 744// 1. (The import invariant.) Every module that provides a package transitively 745// imported by any package or test in the main module is included as a root. 746// This follows by induction from (1) and (3) above. Transitively-imported 747// packages loaded during this invocation are marked with pkgInAll (1), 748// and by hypothesis any transitively-imported packages loaded in previous 749// invocations were already roots in rs (3). 750// 751// 2. (The argument invariant.) Every module that provides a package matching 752// an explicit package pattern is included as a root. This follows directly 753// from (1): packages matching explicit package patterns are marked with 754// pkgIsRoot. 755// 756// 3. (The completeness invariant.) Every module that contributed any package 757// to the build is required by either the main module or one of the modules 758// it requires explicitly. This invariant is left up to the caller, who must 759// not load packages from outside the module graph but may add roots to the 760// graph, but is facilited by (3). If the caller adds roots to the graph in 761// order to resolve missing packages, then updatePrunedRoots will retain them, 762// the selected versions of those roots cannot regress, and they will 763// eventually be written back to the main module's go.mod file. 764// 765// (See https://golang.org/design/36460-lazy-module-loading#invariants for more 766// detail.) 767func updatePrunedRoots(ctx context.Context, direct map[string]bool, rs *Requirements, pkgs []*loadPkg, add []module.Version, rootsImported bool) (*Requirements, error) { 768 roots := rs.rootModules 769 rootsUpgraded := false 770 771 spotCheckRoot := map[module.Version]bool{} 772 773 // “The selected version of the module providing each package marked with 774 // either pkgInAll or pkgIsRoot is included as a root.” 775 needSort := false 776 for _, pkg := range pkgs { 777 if !pkg.fromExternalModule() { 778 // pkg was not loaded from a module dependency, so we don't need 779 // to do anything special to maintain that dependency. 780 continue 781 } 782 783 switch { 784 case pkg.flags.has(pkgInAll): 785 // pkg is transitively imported by a package or test in the main module. 786 // We need to promote the module that maintains it to a root: if some 787 // other module depends on the main module, and that other module also 788 // uses a pruned module graph, it will expect to find all of our 789 // transitive dependencies by reading just our go.mod file, not the go.mod 790 // files of everything we depend on. 791 // 792 // (This is the “import invariant” that makes graph pruning possible.) 793 794 case rootsImported && pkg.flags.has(pkgFromRoot): 795 // pkg is a transitive dependency of some root, and we are treating the 796 // roots as if they are imported by the main module (as in 'go get'). 797 798 case pkg.flags.has(pkgIsRoot): 799 // pkg is a root of the package-import graph. (Generally this means that 800 // it matches a command-line argument.) We want future invocations of the 801 // 'go' command — such as 'go test' on the same package — to continue to 802 // use the same versions of its dependencies that we are using right now. 803 // So we need to bring this package's dependencies inside the pruned 804 // module graph. 805 // 806 // Making the module containing this package a root of the module graph 807 // does exactly that: if the module containing the package supports graph 808 // pruning then it should satisfy the import invariant itself, so all of 809 // its dependencies should be in its go.mod file, and if the module 810 // containing the package does not support pruning then if we make it a 811 // root we will load all of its (unpruned) transitive dependencies into 812 // the module graph. 813 // 814 // (This is the “argument invariant”, and is important for 815 // reproducibility.) 816 817 default: 818 // pkg is a dependency of some other package outside of the main module. 819 // As far as we know it's not relevant to the main module (and thus not 820 // relevant to consumers of the main module either), and its dependencies 821 // should already be in the module graph — included in the dependencies of 822 // the package that imported it. 823 continue 824 } 825 826 if _, ok := rs.rootSelected(pkg.mod.Path); ok { 827 // It is possible that the main module's go.mod file is incomplete or 828 // otherwise erroneous — for example, perhaps the author forgot to 'git 829 // add' their updated go.mod file after adding a new package import, or 830 // perhaps they made an edit to the go.mod file using a third-party tool 831 // ('git merge'?) that doesn't maintain consistency for module 832 // dependencies. If that happens, ideally we want to detect the missing 833 // requirements and fix them up here. 834 // 835 // However, we also need to be careful not to be too aggressive. For 836 // transitive dependencies of external tests, the go.mod file for the 837 // module containing the test itself is expected to provide all of the 838 // relevant dependencies, and we explicitly don't want to pull in 839 // requirements on *irrelevant* requirements that happen to occur in the 840 // go.mod files for these transitive-test-only dependencies. (See the test 841 // in mod_lazy_test_horizon.txt for a concrete example. 842 // 843 // The “goldilocks zone” seems to be to spot-check exactly the same 844 // modules that we promote to explicit roots: namely, those that provide 845 // packages transitively imported by the main module, and those that 846 // provide roots of the package-import graph. That will catch erroneous 847 // edits to the main module's go.mod file and inconsistent requirements in 848 // dependencies that provide imported packages, but will ignore erroneous 849 // or misleading requirements in dependencies that aren't obviously 850 // relevant to the packages in the main module. 851 spotCheckRoot[pkg.mod] = true 852 } else { 853 roots = append(roots, pkg.mod) 854 rootsUpgraded = true 855 // The roots slice was initially sorted because rs.rootModules was sorted, 856 // but the root we just added could be out of order. 857 needSort = true 858 } 859 } 860 861 for _, m := range add { 862 if v, ok := rs.rootSelected(m.Path); !ok || cmpVersion(v, m.Version) < 0 { 863 roots = append(roots, m) 864 rootsUpgraded = true 865 needSort = true 866 } 867 } 868 if needSort { 869 module.Sort(roots) 870 } 871 872 // "Each root appears only once, at the selected version of its path ….” 873 for { 874 var mg *ModuleGraph 875 if rootsUpgraded { 876 // We've added or upgraded one or more roots, so load the full module 877 // graph so that we can update those roots to be consistent with other 878 // requirements. 879 if mustHaveCompleteRequirements() { 880 // Our changes to the roots may have moved dependencies into or out of 881 // the graph-pruning horizon, which could in turn change the selected 882 // versions of other modules. (For pruned modules adding or removing an 883 // explicit root is a semantic change, not just a cosmetic one.) 884 return rs, errGoModDirty 885 } 886 887 rs = newRequirements(pruned, roots, direct) 888 var err error 889 mg, err = rs.Graph(ctx) 890 if err != nil { 891 return rs, err 892 } 893 } else { 894 // Since none of the roots have been upgraded, we have no reason to 895 // suspect that they are inconsistent with the requirements of any other 896 // roots. Only look at the full module graph if we've already loaded it; 897 // otherwise, just spot-check the explicit requirements of the roots from 898 // which we loaded packages. 899 if rs.graph.Load() != nil { 900 // We've already loaded the full module graph, which includes the 901 // requirements of all of the root modules — even the transitive 902 // requirements, if they are unpruned! 903 mg, _ = rs.Graph(ctx) 904 } else if cfg.BuildMod == "vendor" { 905 // We can't spot-check the requirements of other modules because we 906 // don't in general have their go.mod files available in the vendor 907 // directory. (Fortunately this case is impossible, because mg.graph is 908 // always non-nil in vendor mode!) 909 panic("internal error: rs.graph is unexpectedly nil with -mod=vendor") 910 } else if !spotCheckRoots(ctx, rs, spotCheckRoot) { 911 // We spot-checked the explicit requirements of the roots that are 912 // relevant to the packages we've loaded. Unfortunately, they're 913 // inconsistent in some way; we need to load the full module graph 914 // so that we can fix the roots properly. 915 var err error 916 mg, err = rs.Graph(ctx) 917 if err != nil { 918 return rs, err 919 } 920 } 921 } 922 923 roots = make([]module.Version, 0, len(rs.rootModules)) 924 rootsUpgraded = false 925 inRootPaths := make(map[string]bool, len(rs.rootModules)+1) 926 for _, mm := range MainModules.Versions() { 927 inRootPaths[mm.Path] = true 928 } 929 for _, m := range rs.rootModules { 930 if inRootPaths[m.Path] { 931 // This root specifies a redundant path. We already retained the 932 // selected version of this path when we saw it before, so omit the 933 // redundant copy regardless of its version. 934 // 935 // When we read the full module graph, we include the dependencies of 936 // every root even if that root is redundant. That better preserves 937 // reproducibility if, say, some automated tool adds a redundant 938 // 'require' line and then runs 'go mod tidy' to try to make everything 939 // consistent, since the requirements of the older version are carried 940 // over. 941 // 942 // So omitting a root that was previously present may *reduce* the 943 // selected versions of non-roots, but merely removing a requirement 944 // cannot *increase* the selected versions of other roots as a result — 945 // we don't need to mark this change as an upgrade. (This particular 946 // change cannot invalidate any other roots.) 947 continue 948 } 949 950 var v string 951 if mg == nil { 952 v, _ = rs.rootSelected(m.Path) 953 } else { 954 v = mg.Selected(m.Path) 955 } 956 roots = append(roots, module.Version{Path: m.Path, Version: v}) 957 inRootPaths[m.Path] = true 958 if v != m.Version { 959 rootsUpgraded = true 960 } 961 } 962 // Note that rs.rootModules was already sorted by module path and version, 963 // and we appended to the roots slice in the same order and guaranteed that 964 // each path has only one version, so roots is also sorted by module path 965 // and (trivially) version. 966 967 if !rootsUpgraded { 968 if cfg.BuildMod != "mod" { 969 // The only changes to the root set (if any) were to remove duplicates. 970 // The requirements are consistent (if perhaps redundant), so keep the 971 // original rs to preserve its ModuleGraph. 972 return rs, nil 973 } 974 // The root set has converged: every root going into this iteration was 975 // already at its selected version, although we have have removed other 976 // (redundant) roots for the same path. 977 break 978 } 979 } 980 981 if rs.pruning == pruned && reflect.DeepEqual(roots, rs.rootModules) && reflect.DeepEqual(direct, rs.direct) { 982 // The root set is unchanged and rs was already pruned, so keep rs to 983 // preserve its cached ModuleGraph (if any). 984 return rs, nil 985 } 986 return newRequirements(pruned, roots, direct), nil 987} 988 989// spotCheckRoots reports whether the versions of the roots in rs satisfy the 990// explicit requirements of the modules in mods. 991func spotCheckRoots(ctx context.Context, rs *Requirements, mods map[module.Version]bool) bool { 992 ctx, cancel := context.WithCancel(ctx) 993 defer cancel() 994 995 work := par.NewQueue(runtime.GOMAXPROCS(0)) 996 for m := range mods { 997 m := m 998 work.Add(func() { 999 if ctx.Err() != nil { 1000 return 1001 } 1002 1003 summary, err := goModSummary(m) 1004 if err != nil { 1005 cancel() 1006 return 1007 } 1008 1009 for _, r := range summary.require { 1010 if v, ok := rs.rootSelected(r.Path); ok && cmpVersion(v, r.Version) < 0 { 1011 cancel() 1012 return 1013 } 1014 } 1015 }) 1016 } 1017 <-work.Idle() 1018 1019 if ctx.Err() != nil { 1020 // Either we failed a spot-check, or the caller no longer cares about our 1021 // answer anyway. 1022 return false 1023 } 1024 1025 return true 1026} 1027 1028// tidyUnprunedRoots returns a minimal set of root requirements that maintains 1029// the selected version of every module that provided or lexically could have 1030// provided a package in pkgs, and includes the selected version of every such 1031// module in direct as a root. 1032func tidyUnprunedRoots(ctx context.Context, mainModule module.Version, direct map[string]bool, pkgs []*loadPkg) (*Requirements, error) { 1033 var ( 1034 // keep is a set of of modules that provide packages or are needed to 1035 // disambiguate imports. 1036 keep []module.Version 1037 keptPath = map[string]bool{} 1038 1039 // rootPaths is a list of module paths that provide packages directly 1040 // imported from the main module. They should be included as roots. 1041 rootPaths []string 1042 inRootPaths = map[string]bool{} 1043 1044 // altMods is a set of paths of modules that lexically could have provided 1045 // imported packages. It may be okay to remove these from the list of 1046 // explicit requirements if that removes them from the module graph. If they 1047 // are present in the module graph reachable from rootPaths, they must not 1048 // be at a lower version. That could cause a missing sum error or a new 1049 // import ambiguity. 1050 // 1051 // For example, suppose a developer rewrites imports from example.com/m to 1052 // example.com/m/v2, then runs 'go mod tidy'. Tidy may delete the 1053 // requirement on example.com/m if there is no other transitive requirement 1054 // on it. However, if example.com/m were downgraded to a version not in 1055 // go.sum, when package example.com/m/v2/p is loaded, we'd get an error 1056 // trying to disambiguate the import, since we can't check example.com/m 1057 // without its sum. See #47738. 1058 altMods = map[string]string{} 1059 ) 1060 for _, pkg := range pkgs { 1061 if !pkg.fromExternalModule() { 1062 continue 1063 } 1064 if m := pkg.mod; !keptPath[m.Path] { 1065 keep = append(keep, m) 1066 keptPath[m.Path] = true 1067 if direct[m.Path] && !inRootPaths[m.Path] { 1068 rootPaths = append(rootPaths, m.Path) 1069 inRootPaths[m.Path] = true 1070 } 1071 } 1072 for _, m := range pkg.altMods { 1073 altMods[m.Path] = m.Version 1074 } 1075 } 1076 1077 // Construct a build list with a minimal set of roots. 1078 // This may remove or downgrade modules in altMods. 1079 reqs := &mvsReqs{roots: keep} 1080 min, err := mvs.Req(mainModule, rootPaths, reqs) 1081 if err != nil { 1082 return nil, err 1083 } 1084 buildList, err := mvs.BuildList([]module.Version{mainModule}, reqs) 1085 if err != nil { 1086 return nil, err 1087 } 1088 1089 // Check if modules in altMods were downgraded but not removed. 1090 // If so, add them to roots, which will retain an "// indirect" requirement 1091 // in go.mod. See comment on altMods above. 1092 keptAltMod := false 1093 for _, m := range buildList { 1094 if v, ok := altMods[m.Path]; ok && semver.Compare(m.Version, v) < 0 { 1095 keep = append(keep, module.Version{Path: m.Path, Version: v}) 1096 keptAltMod = true 1097 } 1098 } 1099 if keptAltMod { 1100 // We must run mvs.Req again instead of simply adding altMods to min. 1101 // It's possible that a requirement in altMods makes some other 1102 // explicit indirect requirement unnecessary. 1103 reqs.roots = keep 1104 min, err = mvs.Req(mainModule, rootPaths, reqs) 1105 if err != nil { 1106 return nil, err 1107 } 1108 } 1109 1110 return newRequirements(unpruned, min, direct), nil 1111} 1112 1113// updateUnprunedRoots returns a set of root requirements that includes the selected 1114// version of every module path in direct as a root, and maintains the selected 1115// version of every module selected in the graph of rs. 1116// 1117// The roots are updated such that: 1118// 1119// 1. The selected version of every module path in direct is included as a root 1120// (if it is not "none"). 1121// 2. Each root is the selected version of its path. (We say that such a root 1122// set is “consistent”.) 1123// 3. Every version selected in the graph of rs remains selected unless upgraded 1124// by a dependency in add. 1125// 4. Every version in add is selected at its given version unless upgraded by 1126// (the dependencies of) an existing root or another module in add. 1127func updateUnprunedRoots(ctx context.Context, direct map[string]bool, rs *Requirements, add []module.Version) (*Requirements, error) { 1128 mg, err := rs.Graph(ctx) 1129 if err != nil { 1130 // We can't ignore errors in the module graph even if the user passed the -e 1131 // flag to try to push past them. If we can't load the complete module 1132 // dependencies, then we can't reliably compute a minimal subset of them. 1133 return rs, err 1134 } 1135 1136 if mustHaveCompleteRequirements() { 1137 // Instead of actually updating the requirements, just check that no updates 1138 // are needed. 1139 if rs == nil { 1140 // We're being asked to reconstruct the requirements from scratch, 1141 // but we aren't even allowed to modify them. 1142 return rs, errGoModDirty 1143 } 1144 for _, m := range rs.rootModules { 1145 if m.Version != mg.Selected(m.Path) { 1146 // The root version v is misleading: the actual selected version is higher. 1147 return rs, errGoModDirty 1148 } 1149 } 1150 for _, m := range add { 1151 if m.Version != mg.Selected(m.Path) { 1152 return rs, errGoModDirty 1153 } 1154 } 1155 for mPath := range direct { 1156 if _, ok := rs.rootSelected(mPath); !ok { 1157 // Module m is supposed to be listed explicitly, but isn't. 1158 // 1159 // Note that this condition is also detected (and logged with more 1160 // detail) earlier during package loading, so it shouldn't actually be 1161 // possible at this point — this is just a defense in depth. 1162 return rs, errGoModDirty 1163 } 1164 } 1165 1166 // No explicit roots are missing and all roots are already at the versions 1167 // we want to keep. Any other changes we would make are purely cosmetic, 1168 // such as pruning redundant indirect dependencies. Per issue #34822, we 1169 // ignore cosmetic changes when we cannot update the go.mod file. 1170 return rs, nil 1171 } 1172 1173 var ( 1174 rootPaths []string // module paths that should be included as roots 1175 inRootPaths = map[string]bool{} 1176 ) 1177 for _, root := range rs.rootModules { 1178 // If the selected version of the root is the same as what was already 1179 // listed in the go.mod file, retain it as a root (even if redundant) to 1180 // avoid unnecessary churn. (See https://golang.org/issue/34822.) 1181 // 1182 // We do this even for indirect requirements, since we don't know why they 1183 // were added and they could become direct at any time. 1184 if !inRootPaths[root.Path] && mg.Selected(root.Path) == root.Version { 1185 rootPaths = append(rootPaths, root.Path) 1186 inRootPaths[root.Path] = true 1187 } 1188 } 1189 1190 // “The selected version of every module path in direct is included as a root.” 1191 // 1192 // This is only for convenience and clarity for end users: in an unpruned module, 1193 // the choice of explicit vs. implicit dependency has no impact on MVS 1194 // selection (for itself or any other module). 1195 keep := append(mg.BuildList()[MainModules.Len():], add...) 1196 for _, m := range keep { 1197 if direct[m.Path] && !inRootPaths[m.Path] { 1198 rootPaths = append(rootPaths, m.Path) 1199 inRootPaths[m.Path] = true 1200 } 1201 } 1202 1203 var roots []module.Version 1204 for _, mainModule := range MainModules.Versions() { 1205 min, err := mvs.Req(mainModule, rootPaths, &mvsReqs{roots: keep}) 1206 if err != nil { 1207 return rs, err 1208 } 1209 roots = append(roots, min...) 1210 } 1211 if MainModules.Len() > 1 { 1212 module.Sort(roots) 1213 } 1214 if rs.pruning == unpruned && reflect.DeepEqual(roots, rs.rootModules) && reflect.DeepEqual(direct, rs.direct) { 1215 // The root set is unchanged and rs was already unpruned, so keep rs to 1216 // preserve its cached ModuleGraph (if any). 1217 return rs, nil 1218 } 1219 1220 return newRequirements(unpruned, roots, direct), nil 1221} 1222 1223// convertPruning returns a version of rs with the given pruning behavior. 1224// If rs already has the given pruning, convertPruning returns rs unmodified. 1225func convertPruning(ctx context.Context, rs *Requirements, pruning modPruning) (*Requirements, error) { 1226 if rs.pruning == pruning { 1227 return rs, nil 1228 } else if rs.pruning == workspace || pruning == workspace { 1229 panic("attempthing to convert to/from workspace pruning and another pruning type") 1230 } 1231 1232 if pruning == unpruned { 1233 // We are converting a pruned module to an unpruned one. The roots of a 1234 // ppruned module graph are a superset of the roots of an unpruned one, so 1235 // we don't need to add any new roots — we just need to drop the ones that 1236 // are redundant, which is exactly what updateUnprunedRoots does. 1237 return updateUnprunedRoots(ctx, rs.direct, rs, nil) 1238 } 1239 1240 // We are converting an unpruned module to a pruned one. 1241 // 1242 // An unpruned module graph includes the transitive dependencies of every 1243 // module in the build list. As it turns out, we can express that as a pruned 1244 // root set! “Include the transitive dependencies of every module in the build 1245 // list” is exactly what happens in a pruned module if we promote every module 1246 // in the build list to a root. 1247 mg, err := rs.Graph(ctx) 1248 if err != nil { 1249 return rs, err 1250 } 1251 return newRequirements(pruned, mg.BuildList()[MainModules.Len():], rs.direct), nil 1252} 1253