cmd/go: make go.mod exclude directives deterministic

[jayconrod]

Background

exclude directives in go.mod files prevent the go command from loading specific module versions. When an excluded version would normally be loaded, the go command instead loads the next higher semantic version that is not excluded. Both release and pre-release versions may be considered the next higher version, but not pseudo-versions. If there is no higher version, the go command fails with an error.

Problem

The "next" higher version depends on the list of available versions and may change over time. When the go command encounters an excluded version, it always requests a list of versions from a proxy or the origin repository. Unlike other requests, version lists aren't cached, since versions may be added and removed over time. As a result, these fetches are expensive, and they may not work at all if the user is offline or has GOPROXY=off set.

This behavior also makes the build non-deterministic. Since the "next" version may change, the build list may vary depending on when the build was run and which proxy was used. A malicious proxy may selectively show and hide versions, but if the checksum database is being used, a proxy can't introduce a version that wasn't created by the module author without being detected.

If an excluded version is required in the main module's go.mod file, the go command will update the requirement with the version chosen by MVS (typically the "next" version, but possibly something higher). However, excluded versions may still be required transitively, so they may still be loaded. Consider the example below:

module example.com/m

go 1.13

require (
	example.com/a v1.1.0
	example.com/b v1.0.0
)

exclude example.com/a v1.0.0

Suppose that example.com/b@v1.0.0 has this go.mod file:

module example.com/b

go 1.13

require example.com/a v1.0.0

In this example, example.com/m still transtively references the excluded version example.com/a@v1.0.0 via example.com/b@v1.0.0.

This appears to be the root cause of #36453.

Proposed solution

1. If a module version is excluded, and a higher version of the same module is required in the main module's go.mod, the go command should use the required version instead of fetching the next version.
2. When the go command looks up the next version for an excluded module version (because (1) does not apply), it should add a requirement on that version to the main module's go.mod file if one is not already present.

Together, these changes prevent the go command from fetching versions more than once after an exclude directive is added to the go.mod file. The behavior in (2) causes the go command to record the next version. The behavior in (1) ensures the go command acts determinisitically after this information is recorded.

In the above example, the go command would act as if example.com/b required example.com/a@v1.1.0 instead of example.com/a@v1.0.0. The requirement on example.com/a@v1.1.0 would be added to the main module's go.mod file if it weren't already present.

Impact

exclude directives are lightly used in publically visible modules. @heschik did an analysis a few weeks ago and found ~1000 module versions using exclude. Many of these were versions of the same modules or forks. We found ~50 distinct modules using exclude at any version.

exclude directives are likely more common in top-level modules (as opposed to open source libraries).

cc @rsc @bcmills @matloob @heschik @FiloSottile

[bcmills]

I think (2) is important.

As an alternative to (1), we could instead ignore the excluded requirement entirely. (If we know that the main module already has a dependency on a higher version anyway, then replacing the lower version with the higher one has the same effect as dropping the lower one entirely.)

That would drop the excluded edges from go mod graph instead of replacing them with phantom edges, which I suspect would be more in line with users' intuitions about what exclude means.

[rsc]

Yes, we should always write down a choice if we decide we have to make a choice.

[ianlancetaylor]

I'm guessing that nothing happened for 1.15, so rolling forward to 1.16.

[bcmills]

I'm deep in the guts of the module loader for #36460 anyway, so I'm going to implement the behavior described in #36465 (comment). We will ignore requirements on excluded versions whenever they are encountered, with the result that we will either downgrade to the highest non-excluded version found in the requirement graph or re-resolve the latest version of the module (if needed to satisfy package imports).

That approach is deterministic: if we do not need to re-resolve, it always yields the same subgraph of the original requirement graph, and if we do need to re-resolve we will record the resulting version as a new requirement (even if it is lower than the excluded version).

It also has the nice benefit of enabling users to exclude too-high versions that are already in their requirement graph, while (unlike replace) still allowing MVS to select among the remaining requirements (and, unlike a replace directive in most cases, to upgrade as those requirements change).