Source file src/cmd/go/internal/modload/edit.go

     1  // Copyright 2021 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/cfg"
     9  	"cmd/go/internal/gover"
    10  	"cmd/go/internal/mvs"
    11  	"cmd/go/internal/par"
    12  	"context"
    13  	"errors"
    14  	"fmt"
    15  	"maps"
    16  	"os"
    17  	"slices"
    18  
    19  	"golang.org/x/mod/module"
    20  )
    21  
    22  // editRequirements returns an edited version of rs such that:
    23  //
    24  //  1. Each module version in mustSelect is selected.
    25  //
    26  //  2. Each module version in tryUpgrade is upgraded toward the indicated
    27  //     version as far as can be done without violating (1).
    28  //     (Other upgrades are also allowed if they are caused by
    29  //     transitive requirements of versions in mustSelect or
    30  //     tryUpgrade.)
    31  //
    32  //  3. Each module version in rs.rootModules (or rs.graph, if rs is unpruned)
    33  //     is downgraded or upgraded from its original version only to the extent
    34  //     needed to satisfy (1) and (2).
    35  //
    36  // Generally, the module versions in mustSelect are due to the module or a
    37  // package within the module matching an explicit command line argument to 'go
    38  // get', and the versions in tryUpgrade are transitive dependencies that are
    39  // either being upgraded by 'go get -u' or being added to satisfy some
    40  // otherwise-missing package import.
    41  //
    42  // If pruning is enabled, the roots of the edited requirements include an
    43  // explicit entry for each module path in tryUpgrade, mustSelect, and the roots
    44  // of rs, unless the selected version for the module path is "none".
    45  func editRequirements(ctx context.Context, rs *Requirements, tryUpgrade, mustSelect []module.Version) (edited *Requirements, changed bool, err error) {
    46  	if rs.pruning == workspace {
    47  		panic("editRequirements cannot edit workspace requirements")
    48  	}
    49  
    50  	orig := rs
    51  	// If we already know what go version we will end up on after the edit, and
    52  	// the pruning for that version is different, go ahead and apply it now.
    53  	//
    54  	// If we are changing from pruned to unpruned, then we MUST check the unpruned
    55  	// graph for conflicts from the start. (Checking only for pruned conflicts
    56  	// would miss some that would be introduced later.)
    57  	//
    58  	// If we are changing from unpruned to pruned, then we would like to avoid
    59  	// unnecessary downgrades due to conflicts that would be pruned out of the
    60  	// final graph anyway.
    61  	//
    62  	// Note that even if we don't find a go version in mustSelect, it is possible
    63  	// that we will switch from unpruned to pruned (but not the other way around!)
    64  	// after applying the edits if we find a dependency that requires a high
    65  	// enough go version to trigger an upgrade.
    66  	rootPruning := orig.pruning
    67  	for _, m := range mustSelect {
    68  		if m.Path == "go" {
    69  			rootPruning = pruningForGoVersion(m.Version)
    70  			break
    71  		} else if m.Path == "toolchain" && pruningForGoVersion(gover.FromToolchain(m.Version)) == unpruned {
    72  			// We don't know exactly what go version we will end up at, but we know
    73  			// that it must be a version supported by the requested toolchain, and
    74  			// that toolchain does not support pruning.
    75  			//
    76  			// TODO(bcmills): 'go get' ought to reject explicit toolchain versions
    77  			// older than gover.GoStrictVersion. Once that is fixed, is this still
    78  			// needed?
    79  			rootPruning = unpruned
    80  			break
    81  		}
    82  	}
    83  
    84  	if rootPruning != rs.pruning {
    85  		rs, err = convertPruning(ctx, rs, rootPruning)
    86  		if err != nil {
    87  			return orig, false, err
    88  		}
    89  	}
    90  
    91  	// selectedRoot records the edited version (possibly "none") for each module
    92  	// path that would be a root in the edited requirements.
    93  	var selectedRoot map[string]string // module path → edited version
    94  	if rootPruning == pruned {
    95  		selectedRoot = maps.Clone(rs.maxRootVersion)
    96  	} else {
    97  		// In a module without graph pruning, modules that provide packages imported
    98  		// by the main module may either be explicit roots or implicit transitive
    99  		// dependencies. To the extent possible, we want to preserve those implicit
   100  		// dependencies, so we need to treat everything in the build list as
   101  		// potentially relevant — that is, as what would be a “root” in a module
   102  		// with graph pruning enabled.
   103  		mg, err := rs.Graph(ctx)
   104  		if err != nil {
   105  			// If we couldn't load the graph, we don't know what its requirements were
   106  			// to begin with, so we can't edit those requirements in a coherent way.
   107  			return orig, false, err
   108  		}
   109  		bl := mg.BuildList()[MainModules.Len():]
   110  		selectedRoot = make(map[string]string, len(bl))
   111  		for _, m := range bl {
   112  			selectedRoot[m.Path] = m.Version
   113  		}
   114  	}
   115  
   116  	for _, r := range tryUpgrade {
   117  		if v, ok := selectedRoot[r.Path]; ok && gover.ModCompare(r.Path, v, r.Version) >= 0 {
   118  			continue
   119  		}
   120  		if cfg.BuildV {
   121  			fmt.Fprintf(os.Stderr, "go: trying upgrade to %v\n", r)
   122  		}
   123  		selectedRoot[r.Path] = r.Version
   124  	}
   125  
   126  	// conflicts is a list of conflicts that we cannot resolve without violating
   127  	// some version in mustSelect. It may be incomplete, but we want to report
   128  	// as many conflicts as we can so that the user can solve more of them at once.
   129  	var conflicts []Conflict
   130  
   131  	// mustSelectVersion is an index of the versions in mustSelect.
   132  	mustSelectVersion := make(map[string]string, len(mustSelect))
   133  	for _, r := range mustSelect {
   134  		if v, ok := mustSelectVersion[r.Path]; ok && v != r.Version {
   135  			prev := module.Version{Path: r.Path, Version: v}
   136  			if gover.ModCompare(r.Path, v, r.Version) > 0 {
   137  				conflicts = append(conflicts, Conflict{Path: []module.Version{prev}, Constraint: r})
   138  			} else {
   139  				conflicts = append(conflicts, Conflict{Path: []module.Version{r}, Constraint: prev})
   140  			}
   141  			continue
   142  		}
   143  
   144  		mustSelectVersion[r.Path] = r.Version
   145  		selectedRoot[r.Path] = r.Version
   146  	}
   147  
   148  	// We've indexed all of the data we need and we've computed the initial
   149  	// versions of the roots. Now we need to load the actual module graph and
   150  	// restore the invariant that every root is the selected version of its path.
   151  	//
   152  	// For 'go mod tidy' we would do that using expandGraph, which upgrades the
   153  	// roots until their requirements are internally consistent and then drops out
   154  	// the old roots. However, here we need to do more: we also need to make sure
   155  	// the modules in mustSelect don't get upgraded above their intended versions.
   156  	// To do that, we repeatedly walk the module graph, identify paths of
   157  	// requirements that result in versions that are too high, and downgrade the
   158  	// roots that lead to those paths. When no conflicts remain, we're done.
   159  	//
   160  	// Since we want to report accurate paths to each conflict, we don't drop out
   161  	// older-than-selected roots until the process completes. That might mean that
   162  	// we do some extra downgrades when they could be skipped, but for the benefit
   163  	// of being able to explain the reason for every downgrade that seems
   164  	// worthwhile.
   165  	//
   166  	// Graph pruning adds an extra wrinkle: a given node in the module graph
   167  	// may be reached from a root whose dependencies are pruned, and from a root
   168  	// whose dependencies are not pruned. It may be the case that the path from
   169  	// the unpruned root leads to a conflict, while the path from the pruned root
   170  	// prunes out the requirements that would lead to that conflict.
   171  	// So we need to track the two kinds of paths independently.
   172  	// They join back together at the roots of the graph: if a root r1 with pruned
   173  	// requirements depends on a root r2 with unpruned requirements, then
   174  	// selecting r1 would cause r2 to become a root and pull in all of its
   175  	// unpruned dependencies.
   176  	//
   177  	// The dqTracker type implements the logic for propagating conflict paths
   178  	// through the pruned and unpruned parts of the module graph.
   179  	//
   180  	// We make a best effort to fix incompatibilities, subject to two properties:
   181  	//
   182  	// 	1. If the user runs 'go get' with a set of mutually-compatible module
   183  	// 	versions, we should accept those versions.
   184  	//
   185  	// 	2. If we end up upgrading or downgrading a module, it should be
   186  	// 	clear why we did so.
   187  	//
   188  	// We don't try to find an optimal SAT solution,
   189  	// especially given the complex interactions with graph pruning.
   190  
   191  	var (
   192  		roots      []module.Version // the current versions in selectedRoot, in sorted order
   193  		rootsDirty = true           // true if roots does not match selectedRoot
   194  	)
   195  
   196  	// rejectedRoot records the set of module versions that have been disqualified
   197  	// as roots of the module graph. When downgrading due to a conflict or error,
   198  	// we skip any version that has already been rejected.
   199  	//
   200  	// NOTE(bcmills): I am not sure that the rejectedRoot map is really necessary,
   201  	// since we normally only downgrade roots or accept indirect upgrades to
   202  	// known-good versions. However, I am having trouble proving that accepting an
   203  	// indirect upgrade never introduces a conflict that leads to further
   204  	// downgrades. I really want to be able to prove that editRequirements
   205  	// terminates, and the easiest way to prove it is to add this map.
   206  	//
   207  	// Then the proof of termination is this:
   208  	// On every iteration where we mark the roots as dirty, we add some new module
   209  	// version to the map. The universe of module versions is finite, so we must
   210  	// eventually reach a state in which we do not add any version to the map.
   211  	// In that state, we either report a conflict or succeed in the edit.
   212  	rejectedRoot := map[module.Version]bool{}
   213  
   214  	for rootsDirty && len(conflicts) == 0 {
   215  		roots = roots[:0]
   216  		for p, v := range selectedRoot {
   217  			if v != "none" {
   218  				roots = append(roots, module.Version{Path: p, Version: v})
   219  			}
   220  		}
   221  		gover.ModSort(roots)
   222  
   223  		// First, we extend the graph so that it includes the selected version
   224  		// of every root. The upgraded roots are in addition to the original
   225  		// roots, so we will have enough information to trace a path to each
   226  		// conflict we discover from one or more of the original roots.
   227  		mg, upgradedRoots, err := extendGraph(ctx, rootPruning, roots, selectedRoot)
   228  		if err != nil {
   229  			var tooNew *gover.TooNewError
   230  			if mg == nil || errors.As(err, &tooNew) {
   231  				return orig, false, err
   232  			}
   233  			// We're about to walk the entire extended module graph, so we will find
   234  			// any error then — and we will either try to resolve it by downgrading
   235  			// something or report it as a conflict with more detail.
   236  		}
   237  
   238  		// extendedRootPruning is an index of the pruning used to load each root in
   239  		// the extended module graph.
   240  		extendedRootPruning := make(map[module.Version]modPruning, len(roots)+len(upgradedRoots))
   241  		findPruning := func(m module.Version) modPruning {
   242  			if rootPruning == pruned {
   243  				summary, _ := mg.loadCache.Get(m)
   244  				if summary != nil && summary.pruning == unpruned {
   245  					return unpruned
   246  				}
   247  			}
   248  			return rootPruning
   249  		}
   250  		for _, m := range roots {
   251  			extendedRootPruning[m] = findPruning(m)
   252  		}
   253  		for m := range upgradedRoots {
   254  			extendedRootPruning[m] = findPruning(m)
   255  		}
   256  
   257  		// Now check the resulting extended graph for errors and incompatibilities.
   258  		t := dqTracker{extendedRootPruning: extendedRootPruning}
   259  		mg.g.WalkBreadthFirst(func(m module.Version) {
   260  			if max, ok := mustSelectVersion[m.Path]; ok && gover.ModCompare(m.Path, m.Version, max) > 0 {
   261  				// m itself violates mustSelect, so it cannot appear in the module graph
   262  				// even if its transitive dependencies would be pruned out.
   263  				t.disqualify(m, pruned, dqState{dep: m})
   264  				return
   265  			}
   266  
   267  			summary, err := mg.loadCache.Get(m)
   268  			if err != nil && err != par.ErrCacheEntryNotFound {
   269  				// We can't determine the requirements of m, so we don't know whether
   270  				// they would be allowed. This may be a transient error reaching the
   271  				// repository, rather than a permanent error with the retrieved version.
   272  				//
   273  				// TODO(golang.org/issue/31730, golang.org/issue/30134):
   274  				// decide what to do based on the actual error.
   275  				t.disqualify(m, pruned, dqState{err: err})
   276  				return
   277  			}
   278  
   279  			reqs, ok := mg.RequiredBy(m)
   280  			if !ok {
   281  				// The dependencies of m do not appear in the module graph, so they
   282  				// can't be causing any problems this time.
   283  				return
   284  			}
   285  
   286  			if summary == nil {
   287  				if m.Version != "" {
   288  					panic(fmt.Sprintf("internal error: %d reqs present for %v, but summary is nil", len(reqs), m))
   289  				}
   290  				// m is the main module: we are editing its dependencies, so it cannot
   291  				// become disqualified.
   292  				return
   293  			}
   294  
   295  			// Before we check for problems due to transitive dependencies, first
   296  			// check m's direct requirements. A requirement on a version r that
   297  			// violates mustSelect disqualifies m, even if the requirements of r are
   298  			// themselves pruned out.
   299  			for _, r := range reqs {
   300  				if max, ok := mustSelectVersion[r.Path]; ok && gover.ModCompare(r.Path, r.Version, max) > 0 {
   301  					t.disqualify(m, pruned, dqState{dep: r})
   302  					return
   303  				}
   304  			}
   305  			for _, r := range reqs {
   306  				if !t.require(m, r) {
   307  					break
   308  				}
   309  			}
   310  		})
   311  
   312  		// We have now marked all of the versions in the graph that have conflicts,
   313  		// with a path to each conflict from one or more roots that introduce it.
   314  		// Now we need to identify those roots and change their versions
   315  		// (if possible) in order to resolve the conflicts.
   316  		rootsDirty = false
   317  		for _, m := range roots {
   318  			path, err := t.path(m, extendedRootPruning[m])
   319  			if len(path) == 0 && err == nil {
   320  				continue // Nothing wrong with m; we can keep it.
   321  			}
   322  
   323  			// path leads to a module with a problem: either it violates a constraint,
   324  			// or some error prevents us from determining whether it violates a
   325  			// constraint. We might end up logging or returning the conflict
   326  			// information, so go ahead and fill in the details about it.
   327  			conflict := Conflict{
   328  				Path: path,
   329  				Err:  err,
   330  			}
   331  			if err == nil {
   332  				var last module.Version = path[len(path)-1]
   333  				mustV, ok := mustSelectVersion[last.Path]
   334  				if !ok {
   335  					fmt.Fprintf(os.Stderr, "go: %v\n", conflict)
   336  					panic("internal error: found a version conflict, but no constraint it violates")
   337  				}
   338  				conflict.Constraint = module.Version{
   339  					Path:    last.Path,
   340  					Version: mustV,
   341  				}
   342  			}
   343  
   344  			if v, ok := mustSelectVersion[m.Path]; ok && v == m.Version {
   345  				// m is in mustSelect, but is marked as disqualified due to a transitive
   346  				// dependency.
   347  				//
   348  				// In theory we could try removing module paths that don't appear in
   349  				// mustSelect (added by tryUpgrade or already present in rs) in order to
   350  				// get graph pruning to take effect, but (a) it is likely that 'go mod
   351  				// tidy' would re-add those roots and reintroduce unwanted upgrades,
   352  				// causing confusion, and (b) deciding which roots to try to eliminate
   353  				// would add a lot of complexity.
   354  				//
   355  				// Instead, we report the path to the conflict as an error.
   356  				// If users want to explicitly prune out nodes from the dependency
   357  				// graph, they can always add an explicit 'exclude' directive.
   358  				conflicts = append(conflicts, conflict)
   359  				continue
   360  			}
   361  
   362  			// If m is not the selected version of its path, we have two options: we
   363  			// can either upgrade to the version that actually is selected (dropping m
   364  			// itself out of the bottom of the module graph), or we can try
   365  			// downgrading it.
   366  			//
   367  			// If the version we would be upgrading to is ok to use, we will just plan
   368  			// to do that and avoid the overhead of trying to find some lower version
   369  			// to downgrade to.
   370  			//
   371  			// However, it is possible that m depends on something that leads to its
   372  			// own upgrade, so if the upgrade isn't viable we should go ahead and try
   373  			// to downgrade (like with any other root).
   374  			if v := mg.Selected(m.Path); v != m.Version {
   375  				u := module.Version{Path: m.Path, Version: v}
   376  				uPruning, ok := t.extendedRootPruning[m]
   377  				if !ok {
   378  					fmt.Fprintf(os.Stderr, "go: %v\n", conflict)
   379  					panic(fmt.Sprintf("internal error: selected version of root %v is %v, but it was not expanded as a new root", m, u))
   380  				}
   381  				if !t.check(u, uPruning).isDisqualified() && !rejectedRoot[u] {
   382  					// Applying the upgrade from m to u will resolve the conflict,
   383  					// so plan to do that if there are no other conflicts to resolve.
   384  					continue
   385  				}
   386  			}
   387  
   388  			// Figure out what version of m's path was present before we started
   389  			// the edit. We want to make sure we consider keeping it as-is,
   390  			// even if it wouldn't normally be included. (For example, it might
   391  			// be a pseudo-version or pre-release.)
   392  			origMG, _ := orig.Graph(ctx)
   393  			origV := origMG.Selected(m.Path)
   394  
   395  			if conflict.Err != nil && origV == m.Version {
   396  				// This version of m.Path was already in the module graph before we
   397  				// started editing, and the problem with it is that we can't load its
   398  				// (transitive) requirements.
   399  				//
   400  				// If this conflict was just one step in a longer chain of downgrades,
   401  				// then we would want to keep going past it until we find a version
   402  				// that doesn't have that problem. However, we only want to downgrade
   403  				// away from an *existing* requirement if we can confirm that it actually
   404  				// conflicts with mustSelect. (For example, we don't want
   405  				// 'go get -u ./...' to incidentally downgrade some dependency whose
   406  				// go.mod file is unavailable or has a bad checksum.)
   407  				conflicts = append(conflicts, conflict)
   408  				continue
   409  			}
   410  
   411  			// We need to downgrade m's path to some lower version to try to resolve
   412  			// the conflict. Find the next-lowest candidate and apply it.
   413  			rejectedRoot[m] = true
   414  			prev := m
   415  			for {
   416  				prev, err = previousVersion(ctx, prev)
   417  				if gover.ModCompare(m.Path, m.Version, origV) > 0 && (gover.ModCompare(m.Path, prev.Version, origV) < 0 || err != nil) {
   418  					// previousVersion skipped over origV. Insert it into the order.
   419  					prev.Version = origV
   420  				} else if err != nil {
   421  					// We don't know the next downgrade to try. Give up.
   422  					return orig, false, err
   423  				}
   424  				if rejectedRoot[prev] {
   425  					// We already rejected prev in a previous round.
   426  					// To ensure that this algorithm terminates, don't try it again.
   427  					continue
   428  				}
   429  				pruning := rootPruning
   430  				if pruning == pruned {
   431  					if summary, err := mg.loadCache.Get(m); err == nil {
   432  						pruning = summary.pruning
   433  					}
   434  				}
   435  				if t.check(prev, pruning).isDisqualified() {
   436  					// We found a problem with prev this round that would also disqualify
   437  					// it as a root. Don't bother trying it next round.
   438  					rejectedRoot[prev] = true
   439  					continue
   440  				}
   441  				break
   442  			}
   443  			selectedRoot[m.Path] = prev.Version
   444  			rootsDirty = true
   445  
   446  			// If this downgrade is potentially interesting, log the reason for it.
   447  			if conflict.Err != nil || cfg.BuildV {
   448  				var action string
   449  				if prev.Version == "none" {
   450  					action = fmt.Sprintf("removing %s", m)
   451  				} else if prev.Version == origV {
   452  					action = fmt.Sprintf("restoring %s", prev)
   453  				} else {
   454  					action = fmt.Sprintf("trying %s", prev)
   455  				}
   456  				fmt.Fprintf(os.Stderr, "go: %s\n\t%s\n", conflict.Summary(), action)
   457  			}
   458  		}
   459  		if rootsDirty {
   460  			continue
   461  		}
   462  
   463  		// We didn't resolve any issues by downgrading, but we may still need to
   464  		// resolve some conflicts by locking in upgrades. Do that now.
   465  		//
   466  		// We don't do these upgrades until we're done downgrading because the
   467  		// downgrade process might reveal or remove conflicts (by changing which
   468  		// requirement edges are pruned out).
   469  		var upgradedFrom []module.Version // for logging only
   470  		for p, v := range selectedRoot {
   471  			if _, ok := mustSelectVersion[p]; !ok {
   472  				if actual := mg.Selected(p); actual != v {
   473  					if cfg.BuildV {
   474  						upgradedFrom = append(upgradedFrom, module.Version{Path: p, Version: v})
   475  					}
   476  					selectedRoot[p] = actual
   477  					// Accepting the upgrade to m.Path might cause the selected versions
   478  					// of other modules to fall, because they were being increased by
   479  					// dependencies of m that are no longer present in the graph.
   480  					//
   481  					// TODO(bcmills): Can removing m as a root also cause the selected
   482  					// versions of other modules to rise? I think not: we're strictly
   483  					// removing non-root nodes from the module graph, which can't cause
   484  					// any root to decrease (because they're roots), and the dependencies
   485  					// of non-roots don't matter because they're either always unpruned or
   486  					// always pruned out.
   487  					//
   488  					// At any rate, it shouldn't cost much to reload the module graph one
   489  					// last time and confirm that it is stable.
   490  					rootsDirty = true
   491  				}
   492  			}
   493  		}
   494  		if rootsDirty {
   495  			if cfg.BuildV {
   496  				gover.ModSort(upgradedFrom) // Make logging deterministic.
   497  				for _, m := range upgradedFrom {
   498  					fmt.Fprintf(os.Stderr, "go: accepting indirect upgrade from %v to %s\n", m, selectedRoot[m.Path])
   499  				}
   500  			}
   501  			continue
   502  		}
   503  		break
   504  	}
   505  	if len(conflicts) > 0 {
   506  		return orig, false, &ConstraintError{Conflicts: conflicts}
   507  	}
   508  
   509  	if rootPruning == unpruned {
   510  		// An unpruned go.mod file lists only a subset of the requirements needed
   511  		// for building packages. Figure out which requirements need to be explicit.
   512  		var rootPaths []string
   513  
   514  		// The modules in mustSelect are always promoted to be explicit.
   515  		for _, m := range mustSelect {
   516  			if m.Version != "none" && !MainModules.Contains(m.Path) {
   517  				rootPaths = append(rootPaths, m.Path)
   518  			}
   519  		}
   520  
   521  		for _, m := range roots {
   522  			if v, ok := rs.rootSelected(m.Path); ok && (v == m.Version || rs.direct[m.Path]) {
   523  				// m.Path was formerly a root, and either its version hasn't changed or
   524  				// we believe that it provides a package directly imported by a package
   525  				// or test in the main module. For now we'll assume that it is still
   526  				// relevant enough to remain a root. If we actually load all of the
   527  				// packages and tests in the main module (which we are not doing here),
   528  				// we can revise the explicit roots at that point.
   529  				rootPaths = append(rootPaths, m.Path)
   530  			}
   531  		}
   532  
   533  		roots, err = mvs.Req(MainModules.mustGetSingleMainModule(), rootPaths, &mvsReqs{roots: roots})
   534  		if err != nil {
   535  			return nil, false, err
   536  		}
   537  	}
   538  
   539  	changed = rootPruning != orig.pruning || !slices.Equal(roots, orig.rootModules)
   540  	if !changed {
   541  		// Because the roots we just computed are unchanged, the entire graph must
   542  		// be the same as it was before. Save the original rs, since we have
   543  		// probably already loaded its requirement graph.
   544  		return orig, false, nil
   545  	}
   546  
   547  	// A module that is not even in the build list necessarily cannot provide
   548  	// any imported packages. Mark as direct only the direct modules that are
   549  	// still in the build list. (We assume that any module path that provided a
   550  	// direct import before the edit continues to do so after. There are a few
   551  	// edge cases where that can change, such as if a package moves into or out of
   552  	// a nested module or disappears entirely. If that happens, the user can run
   553  	// 'go mod tidy' to clean up the direct/indirect annotations.)
   554  	//
   555  	// TODO(bcmills): Would it make more sense to leave the direct map as-is
   556  	// but allow it to refer to modules that are no longer in the build list?
   557  	// That might complicate updateRoots, but it may be cleaner in other ways.
   558  	direct := make(map[string]bool, len(rs.direct))
   559  	for _, m := range roots {
   560  		if rs.direct[m.Path] {
   561  			direct[m.Path] = true
   562  		}
   563  	}
   564  	edited = newRequirements(rootPruning, roots, direct)
   565  
   566  	// If we ended up adding a dependency that upgrades our go version far enough
   567  	// to activate pruning, we must convert the edited Requirements in order to
   568  	// avoid dropping transitive dependencies from the build list the next time
   569  	// someone uses the updated go.mod file.
   570  	//
   571  	// Note that it isn't possible to go in the other direction (from pruned to
   572  	// unpruned) unless the "go" or "toolchain" module is explicitly listed in
   573  	// mustSelect, which we already handled at the very beginning of the edit.
   574  	// That is because the virtual "go" module only requires a "toolchain",
   575  	// and the "toolchain" module never requires anything else, which means that
   576  	// those two modules will never be downgraded due to a conflict with any other
   577  	// constraint.
   578  	if rootPruning == unpruned {
   579  		if v, ok := edited.rootSelected("go"); ok && pruningForGoVersion(v) == pruned {
   580  			// Since we computed the edit with the unpruned graph, and the pruned
   581  			// graph is a strict subset of the unpruned graph, this conversion
   582  			// preserves the exact (edited) build list that we already computed.
   583  			//
   584  			// However, it does that by shoving the whole build list into the roots of
   585  			// the graph. 'go get' will check for that sort of transition and log a
   586  			// message reminding the user how to clean up this mess we're about to
   587  			// make. 😅
   588  			edited, err = convertPruning(ctx, edited, pruned)
   589  			if err != nil {
   590  				return orig, false, err
   591  			}
   592  		}
   593  	}
   594  	return edited, true, nil
   595  }
   596  
   597  // extendGraph loads the module graph from roots, and iteratively extends it by
   598  // unpruning the selected version of each module path that is a root in rs or in
   599  // the roots slice until the graph reaches a fixed point.
   600  //
   601  // The graph is guaranteed to converge to a fixed point because unpruning a
   602  // module version can only increase (never decrease) the selected versions,
   603  // and the set of versions for each module is finite.
   604  //
   605  // The extended graph is useful for diagnosing version conflicts: for each
   606  // selected module version, it can provide a complete path of requirements from
   607  // some root to that version.
   608  func extendGraph(ctx context.Context, rootPruning modPruning, roots []module.Version, selectedRoot map[string]string) (mg *ModuleGraph, upgradedRoot map[module.Version]bool, err error) {
   609  	for {
   610  		mg, err = readModGraph(ctx, rootPruning, roots, upgradedRoot)
   611  		// We keep on going even if err is non-nil until we reach a steady state.
   612  		// (Note that readModGraph returns a non-nil *ModuleGraph even in case of
   613  		// errors.) The caller may be able to fix the errors by adjusting versions,
   614  		// so we really want to return as complete a result as we can.
   615  
   616  		if rootPruning == unpruned {
   617  			// Everything is already unpruned, so there isn't anything we can do to
   618  			// extend it further.
   619  			break
   620  		}
   621  
   622  		nPrevRoots := len(upgradedRoot)
   623  		for p := range selectedRoot {
   624  			// Since p is a root path, when we fix up the module graph to be
   625  			// consistent with the selected versions, p will be promoted to a root,
   626  			// which will pull in its dependencies. Ensure that its dependencies are
   627  			// included in the module graph.
   628  			v := mg.g.Selected(p)
   629  			if v == "none" {
   630  				// Version “none” always has no requirements, so it doesn't need
   631  				// an explicit node in the module graph.
   632  				continue
   633  			}
   634  			m := module.Version{Path: p, Version: v}
   635  			if _, ok := mg.g.RequiredBy(m); !ok && !upgradedRoot[m] {
   636  				// The dependencies of the selected version of p were not loaded.
   637  				// Mark it as an upgrade so that we will load its dependencies
   638  				// in the next iteration.
   639  				//
   640  				// Note that we don't remove any of the existing roots, even if they are
   641  				// no longer the selected version: with graph pruning in effect this may
   642  				// leave some spurious dependencies in the graph, but it at least
   643  				// preserves enough of the graph to explain why each upgrade occurred:
   644  				// this way, we can report a complete path from the passed-in roots
   645  				// to every node in the module graph.
   646  				//
   647  				// This process is guaranteed to reach a fixed point: since we are only
   648  				// adding roots (never removing them), the selected version of each module
   649  				// can only increase, never decrease, and the set of module versions in the
   650  				// universe is finite.
   651  				if upgradedRoot == nil {
   652  					upgradedRoot = make(map[module.Version]bool)
   653  				}
   654  				upgradedRoot[m] = true
   655  			}
   656  		}
   657  		if len(upgradedRoot) == nPrevRoots {
   658  			break
   659  		}
   660  	}
   661  
   662  	return mg, upgradedRoot, err
   663  }
   664  
   665  type perPruning[T any] struct {
   666  	pruned   T
   667  	unpruned T
   668  }
   669  
   670  func (pp perPruning[T]) from(p modPruning) T {
   671  	if p == unpruned {
   672  		return pp.unpruned
   673  	}
   674  	return pp.pruned
   675  }
   676  
   677  // A dqTracker tracks and propagates the reason that each module version
   678  // cannot be included in the module graph.
   679  type dqTracker struct {
   680  	// extendedRootPruning is the modPruning given the go.mod file for each root
   681  	// in the extended module graph.
   682  	extendedRootPruning map[module.Version]modPruning
   683  
   684  	// dqReason records whether and why each each encountered version is
   685  	// disqualified in a pruned or unpruned context.
   686  	dqReason map[module.Version]perPruning[dqState]
   687  
   688  	// requiring maps each not-yet-disqualified module version to the versions
   689  	// that would cause that module's requirements to be included in a pruned or
   690  	// unpruned context. If that version becomes disqualified, the
   691  	// disqualification will be propagated to all of the versions in the
   692  	// corresponding list.
   693  	//
   694  	// This map is similar to the module requirement graph, but includes more
   695  	// detail about whether a given dependency edge appears in a pruned or
   696  	// unpruned context. (Other commands do not need this level of detail.)
   697  	requiring map[module.Version][]module.Version
   698  }
   699  
   700  // A dqState indicates whether and why a module version is “disqualified” from
   701  // being used in a way that would incorporate its requirements.
   702  //
   703  // The zero dqState indicates that the module version is not known to be
   704  // disqualified, either because it is ok or because we are currently traversing
   705  // a cycle that includes it.
   706  type dqState struct {
   707  	err error          // if non-nil, disqualified because the requirements of the module could not be read
   708  	dep module.Version // disqualified because the module is or requires dep
   709  }
   710  
   711  func (dq dqState) isDisqualified() bool {
   712  	return dq != dqState{}
   713  }
   714  
   715  func (dq dqState) String() string {
   716  	if dq.err != nil {
   717  		return dq.err.Error()
   718  	}
   719  	if dq.dep != (module.Version{}) {
   720  		return dq.dep.String()
   721  	}
   722  	return "(no conflict)"
   723  }
   724  
   725  // require records that m directly requires r, in case r becomes disqualified.
   726  // (These edges are in the opposite direction from the edges in an mvs.Graph.)
   727  //
   728  // If r is already disqualified, require propagates the disqualification to m
   729  // and returns the reason for the disqualification.
   730  func (t *dqTracker) require(m, r module.Version) (ok bool) {
   731  	rdq := t.dqReason[r]
   732  	rootPruning, isRoot := t.extendedRootPruning[r]
   733  	if isRoot && rdq.from(rootPruning).isDisqualified() {
   734  		// When we pull in m's dependencies, we will have an edge from m to r, and r
   735  		// is disqualified (it is a root, which causes its problematic dependencies
   736  		// to always be included). So we cannot pull in m's dependencies at all:
   737  		// m is completely disqualified.
   738  		t.disqualify(m, pruned, dqState{dep: r})
   739  		return false
   740  	}
   741  
   742  	if dq := rdq.from(unpruned); dq.isDisqualified() {
   743  		t.disqualify(m, unpruned, dqState{dep: r})
   744  		if _, ok := t.extendedRootPruning[m]; !ok {
   745  			// Since m is not a root, its dependencies can't be included in the pruned
   746  			// part of the module graph, and will never be disqualified from a pruned
   747  			// reason. We've already disqualified everything that matters.
   748  			return false
   749  		}
   750  	}
   751  
   752  	// Record that m is a dependant of r, so that if r is later disqualified
   753  	// m will be disqualified as well.
   754  	if t.requiring == nil {
   755  		t.requiring = make(map[module.Version][]module.Version)
   756  	}
   757  	t.requiring[r] = append(t.requiring[r], m)
   758  	return true
   759  }
   760  
   761  // disqualify records why the dependencies of m cannot be included in the module
   762  // graph if reached from a part of the graph with the given pruning.
   763  //
   764  // Since the pruned graph is a subgraph of the unpruned graph, disqualifying a
   765  // module from a pruned part of the graph also disqualifies it in the unpruned
   766  // parts.
   767  func (t *dqTracker) disqualify(m module.Version, fromPruning modPruning, reason dqState) {
   768  	if !reason.isDisqualified() {
   769  		panic("internal error: disqualify called with a non-disqualifying dqState")
   770  	}
   771  
   772  	dq := t.dqReason[m]
   773  	if dq.from(fromPruning).isDisqualified() {
   774  		return // Already disqualified for some other reason; don't overwrite it.
   775  	}
   776  	rootPruning, isRoot := t.extendedRootPruning[m]
   777  	if fromPruning == pruned {
   778  		dq.pruned = reason
   779  		if !dq.unpruned.isDisqualified() {
   780  			// Since the pruned graph of m is a subgraph of the unpruned graph, if it
   781  			// is disqualified due to something in the pruned graph, it is certainly
   782  			// disqualified in the unpruned graph from the same reason.
   783  			dq.unpruned = reason
   784  		}
   785  	} else {
   786  		dq.unpruned = reason
   787  		if dq.pruned.isDisqualified() {
   788  			panic(fmt.Sprintf("internal error: %v is marked as disqualified when pruned, but not when unpruned", m))
   789  		}
   790  		if isRoot && rootPruning == unpruned {
   791  			// Since m is a root that is always unpruned, any other roots — even
   792  			// pruned ones! — that cause it to be selected would also cause the reason
   793  			// for is disqualification to be included in the module graph.
   794  			dq.pruned = reason
   795  		}
   796  	}
   797  	if t.dqReason == nil {
   798  		t.dqReason = make(map[module.Version]perPruning[dqState])
   799  	}
   800  	t.dqReason[m] = dq
   801  
   802  	if isRoot && (fromPruning == pruned || rootPruning == unpruned) {
   803  		// Either m is disqualified even when its dependencies are pruned,
   804  		// or m's go.mod file causes its dependencies to *always* be unpruned.
   805  		// Everything that depends on it must be disqualified.
   806  		for _, p := range t.requiring[m] {
   807  			t.disqualify(p, pruned, dqState{dep: m})
   808  			// Note that since the pruned graph is a subset of the unpruned graph,
   809  			// disqualifying p in the pruned graph also disqualifies it in the
   810  			// unpruned graph.
   811  		}
   812  		// Everything in t.requiring[m] is now fully disqualified.
   813  		// We won't need to use it again.
   814  		delete(t.requiring, m)
   815  		return
   816  	}
   817  
   818  	// Either m is not a root, or it is a pruned root but only being disqualified
   819  	// when reached from the unpruned parts of the module graph.
   820  	// Either way, the reason for this disqualification is only visible to the
   821  	// unpruned parts of the module graph.
   822  	for _, p := range t.requiring[m] {
   823  		t.disqualify(p, unpruned, dqState{dep: m})
   824  	}
   825  	if !isRoot {
   826  		// Since m is not a root, its dependencies can't be included in the pruned
   827  		// part of the module graph, and will never be disqualified from a pruned
   828  		// reason. We've already disqualified everything that matters.
   829  		delete(t.requiring, m)
   830  	}
   831  }
   832  
   833  // check reports whether m is disqualified in the given pruning context.
   834  func (t *dqTracker) check(m module.Version, pruning modPruning) dqState {
   835  	return t.dqReason[m].from(pruning)
   836  }
   837  
   838  // path returns the path from m to the reason it is disqualified, which may be
   839  // either a module that violates constraints or an error in loading
   840  // requirements.
   841  //
   842  // If m is not disqualified, path returns (nil, nil).
   843  func (t *dqTracker) path(m module.Version, pruning modPruning) (path []module.Version, err error) {
   844  	for {
   845  		if rootPruning, isRoot := t.extendedRootPruning[m]; isRoot && rootPruning == unpruned {
   846  			// Since m is a root, any other module that requires it would cause
   847  			// its full unpruned dependencies to be included in the module graph.
   848  			// Those dependencies must also be considered as part of the path to the conflict.
   849  			pruning = unpruned
   850  		}
   851  		dq := t.dqReason[m].from(pruning)
   852  		if !dq.isDisqualified() {
   853  			return path, nil
   854  		}
   855  		path = append(path, m)
   856  		if dq.err != nil || dq.dep == m {
   857  			return path, dq.err // m itself is the conflict.
   858  		}
   859  		m = dq.dep
   860  	}
   861  }
   862  

View as plain text