Minimal Version Selection and Its Compatibility Assumption

Most resolvers search. They choose a version, propagate consequences, discover a contradiction, and choose again. Go’s module system does not search at all: it computes a maximum. The rule is that each module declares the minimum version of each dependency it needs, and the version actually used is the largest minimum declared by any module in the build. There is no candidate ordering to try, no conflict to resolve, and no possibility of the answer depending on the order in which the graph was walked.

The rule in one line

Given a set of root modules and, for each module version, the minimum versions it requires of its dependencies, the build list assigns to each module the maximum of the versions required of it, over every module reachable in the graph. If the root requires A at least 1.3, and A at 1.3 requires B at least 1.1, and the root also requires B at least 1.4, then B is 1.4 and A is 1.3.

Two properties follow immediately. First, the answer is a function of the requirement graph alone, so two machines with the same go.mod files compute the same list without coordinating. Second, adding a requirement can only raise a version, never lower one. That monotonicity is the reason the computation terminates and the reason no backtracking is needed: a choice once raised is never revisited downward, so there is nothing to undo.

Contrast this with a policy that selects the newest admissible version. There, choosing a newer version of A can introduce a requirement that invalidates an earlier choice, and the resolver must be able to retreat. Under MVS, a newer A can only raise the minima of its dependencies, and a raised minimum is still satisfied by taking the higher version. There is no upper bound to violate, because the language cannot express one.

Why the language forbids upper bounds

The absence of upper bounds is the load-bearing design decision, not an oversight. Suppose a module could declare “B at least 1.2, below 1.5”. Then a diamond in which another module requires B at least 1.6 would be unsatisfiable, and the resolver would need to search for a combination of older versions that avoids the conflict — the same problem every other ecosystem solves with backtracking, using the richer constraint language described in Version Ranges as Sets of Versions. By allowing only lower bounds, the designer makes the largest requirement always satisfiable by taking it, at the cost of giving up the ability to say “my code does not work with the next major version”.

That cost is paid in the compatibility contract. A module author cannot fence off a future breaking change; the ecosystem’s substitute is that a breaking change must arrive as a new import path — a new major version encoded in the module path — so that the old path continues to designate the old API. Consumers move by changing their import statements rather than by relying on the resolver to keep two majors apart. This is why module paths for versions at 2 and above carry a suffix such as /v2: the path is part of the module’s identity, so v1 and v2 are different modules rather than two versions of one, and the single-version-per-path rule does not force a choice between them.

The other half of the contract is the compatibility promise for the standard library, which states that programs that work with one Go 1 release continue to work with later ones. MVS is only safe because the language and its library behave monotonically across versions. A policy that always raises to the maximum is sound exactly to the extent that raising is harmless.

The graph is read at the selected versions

A detail that makes MVS more than a single pass is that a module’s requirements depend on which version of it is selected. If the build list raises A from 1.3 to 1.5 because another module requires that, then the requirements read from A change too: A 1.5 may require C where A 1.3 did not.

The computation is therefore a fixed point. Start with the roots, read their requirements, raise the build list, and whenever a selection rises, re-read that module’s requirements and propagate again. Termination follows from the finite version set and the monotonicity of the updates: every assignment only moves upward, and each module has finitely many versions above its current one. In the worst case the number of updates is bounded by the number of edges times the number of versions along each module’s upgrade path, which in practice is small because requirement graphs are shallow.

def version_lt(a, b):
    """Stand-in for the ecosystem's ordering; correct for plain major.minor.patch."""
    return tuple(int(p) for p in a.split('.')) < tuple(int(p) for p in b.split('.'))

def mvs(roots, require):
    """roots: {module: min_version}; require(mod, ver) -> {dep: min_version}."""
    selected = dict(roots)
    changed = True
    while changed:
        changed = False
        for mod, ver in list(selected.items()):
            for dep, minv in require(mod, ver).items():
                cur = selected.get(dep)
                # Versions need the ecosystem's ordering, not string order.
                if cur is None or version_lt(cur, minv):
                    selected[dep] = minv
                    changed = True
    return selected

The changed loop is the fixed point. A worklist implementation that re-enqueues only the modules whose selection rose computes the same answer with less repeated work; the naive form is easier to check against the definition, which is why the specification states the result rather than an algorithm.

The oldest-version consequence

Because the selected version is the maximum of the declared minimums, it is usually the oldest version anyone said they needed. A module that works with 1.1 declares 1.1, and unless another module in the build requires something newer, 1.1 is what gets compiled. Bug fixes published in 1.2, 1.3, and 1.4 are not picked up by anyone who did not ask for them.

This is the opposite of the newest-satisfying policy, and the difference is visible in day-to-day work. Under a newest policy, a fresh install drifts forward as the registry publishes, and the lockfile exists to stop that drift. Under MVS, the requirement file itself is the pin, and there is no drift to stop: the same go.mod files produce the same list forever, and updating requires an explicit command that rewrites them.

The price is that the tested configuration can lag the published one. If everyone builds against their declared minimums, then nobody is exercising the newest release of a dependency in combination with everything else, and a bug that only appears at the maximum can survive until a user upgrades. The ecosystem’s answer is a workflow rather than a resolver feature: raise the requirements periodically, run the test suite, and commit the result. A resolver cannot substitute for that, because the information it would need — which combinations actually work — is not in any manifest.

The benefit is that upgrades are explicit and reviewable. A change to a go.mod requirement is a small, meaningful diff, and the build list follows from it mechanically. Under a search-based resolver, a one-line range change can shift dozens of versions, and the resulting lockfile diff is where the real review happens.

Pruning the graph without changing the answer

Computing the build list requires the requirement lists of every module version in the graph, which in an old-style module graph meant fetching the go.mod of every transitive dependency, including versions that would never be selected. For a large graph that is a lot of small network requests, and each one is a potential failure.

The solution adopted by the module system is to have each go.mod file record not only its direct requirements but every module version needed to build it, at the versions in its own build list. With those records present, a consumer can compute the build list from a bounded neighbourhood rather than traversing the whole graph, and the selected versions are unchanged: the extra entries are consequences of the same maximum rule, so including them cannot raise anything above what the full graph would produce. The go directive in each file marks whether the module’s requirements are recorded in the pruned form, which lets tooling treat older modules conservatively.

Pruning is a change to the representation, not to the selection rule, and that separation is the reason it could be adopted without invalidating existing builds. It does make the file larger and the diff noisier, since a requirement change can add indirect entries that the author did not write by hand. Tools that rewrite the file are doing the fixed-point computation and recording its result, which is why the indirect entries are marked as such.

Where the policy meets reality

Two escape hatches exist because the monotone rule cannot express every real situation. A module can be excluded at a specific version, which removes it from consideration without removing the requirement; and a requirement can be replaced by a different module or version, which redirects the identity. Both break the pure computation, because the replacement is not derivable from the requirements and must therefore be recorded as input. A build that uses a replacement is not reproducible from the requirements alone, which is the price of the escape hatch.

Within the pure rule, the interesting failure is a missing module rather than a conflict: if a required version does not exist, or its go.mod is unreadable, the computation cannot proceed, and the error names the requirement that pulled it in. There is no search to blame and no alternative assignment to try, which makes the diagnostic simpler than a resolver’s derivation chain but also means the tool has no fallback. The build either has the module or it does not.

Seen from the other side, MVS is a bet that a graph with one node per module path and only lower bounds is expressive enough for a language ecosystem, and that the resulting simplicity — no duplicates, no backtracking, no lockfile distinct from the requirement file — is worth more than the flexibility of ranges with upper bounds. The bet is not universal. Ecosystems whose libraries routinely break within a major version need the upper bounds, and with them the search that Dependency Resolution as a Satisfiability Problem describes. The trade is between a resolver that can say yes to more combinations and one whose answer is a maximum instead of a search result.