cmd/go/internal/modload: fuse upgrading with downgrading in EditBuildList

Previosly, EditBuildList performed an mvs.Upgrade followed by an
mvs.Downgrade, with the Downgrade building on the result of the
Upgrade. Unfortunately, that approach potentially folds in irrelevant
dependencies from the first Upgrade, which are then preserved
unnecessarily by the Downgrade (see mod_get_downup_artifact.txt).

Now, we use the initial Upgrade only to compute the maximum allowed
versions of transitive dependencies, and apply the module upgrades and
downgrades together in a single operation.

For #36460

Change-Id: I7590c137111fed4a3b06531c88d90efd49e6943a
Reviewed-on: https://go-review.googlesource.com/c/go/+/290770
Trust: Bryan C. Mills <bcmills@google.com>
Run-TryBot: Bryan C. Mills <bcmills@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Michael Matloob <matloob@golang.org>

1 files changed, 281 insertions, 0 deletions

diff --git a/src/cmd/go/internal/modload/edit.go b/src/cmd/go/internal/modload/edit.go
new file mode 100644
index 0000000000..4d1f3c7826
--- /dev/null
+++ b/src/cmd/go/internal/modload/edit.go
@@ -0,0 +1,281 @@
+// Copyright 2021 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package modload
+
+import (
+	"context"
+	"sort"
+
+	"cmd/go/internal/mvs"
+
+	"golang.org/x/mod/module"
+	"golang.org/x/mod/semver"
+)
+
+// editBuildList returns an edited version of initial such that:
+//
+// 	1. Each module version in mustSelect is selected, unless it is upgraded
+// 	   by the transitive requirements of another version in mustSelect.
+//
+// 	2. Each module version in tryUpgrade is upgraded toward the indicated
+// 	   version as far as can be done without violating (1).
+//
+// 	3. Each module version in initial is downgraded from its original version
+// 	   only to the extent needed to satisfy (1), or upgraded only to the extent
+// 	   needed to satisfy (1) and (2).
+//
+// 	4. No module is upgraded above the maximum version of its path found in the
+// 	   combined dependency graph of list, tryUpgrade, and mustSelect.
+func editBuildList(ctx context.Context, initial, tryUpgrade, mustSelect []module.Version) ([]module.Version, error) {
+	// Per https://research.swtch.com/vgo-mvs#algorithm_4:
+	// “To avoid an unnecessary downgrade to E 1.1, we must also add a new
+	// requirement on E 1.2. We can apply Algorithm R to find the minimal set of
+	// new requirements to write to go.mod.”
+	//
+	// In order to generate those new requirements, we need consider versions for
+	// every module in the existing build list, plus every module being directly
+	// added by the edit. However, modules added only as dependencies of tentative
+	// versions should not be retained if they end up being upgraded or downgraded
+	// away due to versions in mustSelect.
+
+	// When we downgrade modules in order to reach mustSelect, we don't want to
+	// upgrade any existing module above the version that would be selected if we
+	// just added all of the new requirements and *didn't* downgrade.
+	//
+	// So we'll do exactly that: just add all of the new requirements and not
+	// downgrade, and return the resulting versions as an upper bound. This
+	// intentionally limits our solution space so that edits that the user
+	// percieves as “downgrades” will not also result in upgrades.
+	max := make(map[string]string)
+	maxes, err := mvs.Upgrade(Target, &mvsReqs{
+		buildList: append(capVersionSlice(initial), mustSelect...),
+	}, tryUpgrade...)
+	if err != nil {
+		return nil, err
+	}
+	for _, m := range maxes {
+		max[m.Path] = m.Version
+	}
+	// The versions in mustSelect override whatever we would naively select —
+	// we will downgrade other modules as needed in order to meet them.
+	for _, m := range mustSelect {
+		max[m.Path] = m.Version
+	}
+
+	limiter := newVersionLimiter(max)
+
+	// Force the selected versions in mustSelect, even if they conflict.
+	//
+	// TODO(bcmills): Instead of forcing these versions, record conflicts
+	// so that the caller doesn't have to recompute them.
+	for _, m := range mustSelect {
+		limiter.selected[m.Path] = m.Version
+	}
+
+	// For each module, we want to get as close as we can to either the upgrade
+	// version or the previously-selected version in the build list, whichever is
+	// higher. We can compute those in either order, but the upgrades will tend to
+	// be higher than the build list, so we arbitrarily start with those.
+	for _, m := range tryUpgrade {
+		if err := limiter.upgradeToward(ctx, m); err != nil {
+			return nil, err
+		}
+	}
+	for _, m := range initial {
+		if err := limiter.upgradeToward(ctx, m); err != nil {
+			return nil, err
+		}
+	}
+
+	// We've identified acceptable versions for each of the modules, but those
+	// versions are not necessarily consistent with each other: one upgraded or
+	// downgraded module may require a higher (but still allowed) version of
+	// another. The lower version may require extraneous dependencies that aren't
+	// actually relevant, so we need to compute the actual selected versions.
+	adjusted := make([]module.Version, 0, len(maxes))
+	for _, m := range maxes {
+		if v, ok := limiter.selected[m.Path]; ok {
+			adjusted = append(adjusted, module.Version{Path: m.Path, Version: v})
+		}
+	}
+	consistent, err := mvs.BuildList(Target, &mvsReqs{buildList: adjusted})
+	if err != nil {
+		return nil, err
+	}
+
+	// We have the correct selected versions. Now we need to re-run MVS with only
+	// the actually-selected versions in order to eliminate extraneous
+	// dependencies from lower-than-selected ones.
+	compacted := consistent[:0]
+	for _, m := range consistent {
+		if _, ok := limiter.selected[m.Path]; ok {
+			// The fact that the limiter has a version for m.Path indicates that we
+			// care about retaining that path, even if the version was upgraded for
+			// consistency.
+			compacted = append(compacted, m)
+		}
+	}
+
+	return mvs.BuildList(Target, &mvsReqs{buildList: compacted})
+}
+
+// A versionLimiter tracks the versions that may be selected for each module
+// subject to constraints on the maximum versions of transitive dependencies.
+type versionLimiter struct {
+	// max maps each module path to the maximum version that may be selected for
+	// that path. Paths with no entry are unrestricted.
+	max map[string]string
+
+	// selected maps each module path to a version of that path (if known) whose
+	// transitive dependencies do not violate any max version. The version kept
+	// is the highest one found during any call to upgradeToward for the given
+	// module path.
+	//
+	// If a higher acceptable version is found during a call to upgradeToward for
+	// some *other* module path, that does not update the selected version.
+	// Ignoring those versions keeps the downgrades computed for two modules
+	// together close to the individual downgrades that would be computed for each
+	// module in isolation. (The only way one module can affect another is if the
+	// final downgraded version of the one module explicitly requires a higher
+	// version of the other.)
+	//
+	// Version "none" of every module is always known not to violate any max
+	// version, so paths at version "none" are omitted.
+	selected map[string]string
+
+	// disqualified maps each encountered version to either true (if that version
+	// is known to be disqualified due to a conflict with a max version) or false
+	// (if that version is not known to be disqualified, either because it is ok
+	// or because we are currently traversing a cycle that includes it).
+	disqualified map[module.Version]bool
+
+	// requiredBy maps each not-yet-disqualified module version to the versions
+	// that directly require it. If that version becomes disqualified, the
+	// disqualification will be propagated to all of the versions in the list.
+	requiredBy map[module.Version][]module.Version
+}
+
+func newVersionLimiter(max map[string]string) *versionLimiter {
+	return &versionLimiter{
+		selected:     map[string]string{Target.Path: Target.Version},
+		max:          max,
+		disqualified: map[module.Version]bool{Target: false},
+		requiredBy:   map[module.Version][]module.Version{},
+	}
+}
+
+// upgradeToward attempts to upgrade the selected version of m.Path as close as
+// possible to m.Version without violating l's maximum version limits.
+func (l *versionLimiter) upgradeToward(ctx context.Context, m module.Version) error {
+	selected, ok := l.selected[m.Path]
+	if ok {
+		if cmpVersion(selected, m.Version) >= 0 {
+			// The selected version is already at least m, so no upgrade is needed.
+			return nil
+		}
+	} else {
+		selected = "none"
+	}
+
+	if l.isDisqualified(m) {
+		candidates, err := versions(ctx, m.Path, CheckAllowed)
+		if err != nil {
+			// This is likely a transient error reaching the repository,
+			// rather than a permanent error with the retrieved version.
+			//
+			// TODO(golang.org/issue/31730, golang.org/issue/30134):
+			// decode what to do based on the actual error.
+			return err
+		}
+
+		// Skip to candidates < m.Version.
+		i := sort.Search(len(candidates), func(i int) bool {
+			return semver.Compare(candidates[i], m.Version) >= 0
+		})
+		candidates = candidates[:i]
+
+		for l.isDisqualified(m) {
+			n := len(candidates)
+			if n == 0 || cmpVersion(selected, candidates[n-1]) >= 0 {
+				// We couldn't find a suitable candidate above the already-selected version.
+				// Retain that version unmodified.
+				return nil
+			}
+			m.Version, candidates = candidates[n-1], candidates[:n-1]
+		}
+	}
+
+	l.selected[m.Path] = m.Version
+	return nil
+}
+
+// isDisqualified reports whether m (or its transitive dependencies) would
+// violate l's maximum version limits if added to the module requirement graph.
+func (l *versionLimiter) isDisqualified(m module.Version) bool {
+	if m.Version == "none" || m == Target {
+		// version "none" has no requirements, and the dependencies of Target are
+		// tautological.
+		return false
+	}
+
+	if dq, seen := l.disqualified[m]; seen {
+		return dq
+	}
+	l.disqualified[m] = false
+
+	if max, ok := l.max[m.Path]; ok && cmpVersion(m.Version, max) > 0 {
+		l.disqualify(m)
+		return true
+	}
+
+	summary, err := goModSummary(m)
+	if err != nil {
+		// If we can't load the requirements, we couldn't load the go.mod file.
+		// There are a number of reasons this can happen, but this usually
+		// means an older version of the module had a missing or invalid
+		// go.mod file. For example, if example.com/mod released v2.0.0 before
+		// migrating to modules (v2.0.0+incompatible), then added a valid go.mod
+		// in v2.0.1, downgrading from v2.0.1 would cause this error.
+		//
+		// TODO(golang.org/issue/31730, golang.org/issue/30134): if the error
+		// is transient (we couldn't download go.mod), return the error from
+		// Downgrade. Currently, we can't tell what kind of error it is.
+		l.disqualify(m)
+		return true
+	}
+
+	for _, r := range summary.require {
+		if l.isDisqualified(r) {
+			l.disqualify(m)
+			return true
+		}
+
+		// r and its dependencies are (perhaps provisionally) ok.
+		//
+		// However, if there are cycles in the requirement graph, we may have only
+		// checked a portion of the requirement graph so far, and r (and thus m) may
+		// yet be disqualified by some path we have not yet visited. Remember this edge
+		// so that we can disqualify m and its dependents if that occurs.
+		l.requiredBy[r] = append(l.requiredBy[r], m)
+	}
+
+	return false
+}
+
+// disqualify records that m (or one of its transitive dependencies)
+// violates l's maximum version limits.
+func (l *versionLimiter) disqualify(m module.Version) {
+	if l.disqualified[m] {
+		return
+	}
+	l.disqualified[m] = true
+
+	for _, p := range l.requiredBy[m] {
+		l.disqualify(p)
+	}
+	// Now that we have disqualified the modules that depend on m, we can forget
+	// about them — we won't need to disqualify them again.
+	delete(l.requiredBy, m)
+}