How Dependency Resolvers Turn Version Ranges into a Fixed Graph

A dependency manifest does not name the software that will be installed. It names a set of acceptable software. The line ^1.4.2 admits every version from 1.4.2 up to but not including 2.0.0, and a manifest with forty such lines admits a combinatorial space of possible installations. Something has to collapse that space to one point before a build can run, and whatever does the collapsing determines, in a very direct sense, which bytes execute on the machine.

That collapsing step is resolution, and its output is usually cached in a lockfile. The two are worth understanding together because the security properties of a build depend on both: resolution decides which versions are candidates, and the lockfile decides which of them are fetched on the next install.

A range is a set, an installation is a point

Version ranges in the common ecosystems are interval predicates over an ordered version space. The ordering is defined by Semantic Versioning, which gives each version three numeric components and an optional prerelease suffix. Precedence compares major, then minor, then patch numerically. A version with a prerelease suffix has lower precedence than the corresponding release, and prerelease identifiers are compared field by field: numeric identifiers numerically, alphanumeric identifiers in ASCII order, with numeric identifiers ranking below alphanumeric ones. Build metadata after a + is ignored entirely for ordering, which means two versions that differ only in build metadata are equal in precedence and cannot be distinguished by a range.

The consequence is that “latest” is not a property of a version in isolation. It is a property of a version relative to the constraint set, and a range like >=1.2 <2 excludes prereleases unless the range itself mentions one. npm’s rule is stricter: a prerelease version only satisfies a comparator if that comparator has a prerelease part with the same major, minor, and patch triple. A resolver that ignores this and simply takes the maximum matching version will pull prerelease builds into production trees.

Ranges also compose in ways that are not locally visible. Two manifests can each be individually satisfiable and jointly unsatisfiable: one requires foo >=2, another requires foo <2. The resolver discovers this only after it has committed to a version of some third package whose own constraints narrow foo. This is the structural reason resolution is a search and not a lookup.

Backtracking over the version space

A resolver maintains a partial assignment: a map from package name to chosen version, plus the set of constraints that have been derived so far. It repeatedly picks an unassigned package, orders its candidate versions from highest to lowest, and tries the first one. Each choice adds that version’s own dependencies as new constraints, which may eliminate candidates for packages already assigned. When a constraint eliminates the chosen version of an already-assigned package, the resolver must undo the decision that led there and try the next candidate.

The naive form of this is depth-first search with chronological backtracking, and its worst case is exponential in the number of packages, because the search tree branches once per candidate version. Modern resolvers cut the tree with conflict-driven learning: when a conflict is found, the resolver derives the minimal set of decisions that caused it and records that combination as impossible, so the same conflict is never re-explored. PubGrub, the algorithm behind several package managers, is the clearest published example of this approach and reports human-readable derivations of conflicts as a side effect.

An alternative design sidesteps the search entirely. npm before version 7 built a nested tree rather than a flat assignment: if two dependents needed incompatible versions of the same package, both were installed, one inside the other’s node_modules directory. This makes resolution a local operation with no backtracking, at the cost of duplicate copies on disk and the possibility of two instances of a library that expects to be a singleton. The switch to a hoisted, deduplicated tree moved npm toward the same conflict problem every other resolver has, and made peer dependency conflicts visible as errors rather than silently duplicated installs.

The ordering heuristic matters more than the algorithm name suggests. Choosing the package with the fewest remaining candidates first, and trying the highest version first, both reduce the expected number of backtracks dramatically on real graphs, which are shallow: the median depth of a dependency graph is small even when the total node count is in the hundreds.

What the lockfile records, and what it fixes

A lockfile is the serialized result of one successful resolution. Its essential contents are, per package: the exact version, the URL the artifact is fetched from, a content hash of that artifact, and the edges to its own dependencies. npm’s lockfile additionally records the physical layout of the tree, because the hoisting decision affects where files land. Cargo’s lockfile records checksums and the resolved set but not the fetch URL, since the registry is configured separately.

Three properties follow from this structure.

First, installation becomes a lookup rather than a search. Given a lockfile, the client fetches exactly the named artifacts and verifies each against the recorded hash, with no version selection at all. This is why npm ci and cargo build --locked exist as distinct operations: they fail rather than re-resolve when the lockfile and manifest disagree.

Second, the lockfile is a security-relevant document. It names the URL and the hash of every artifact the build will consume, so a diff to a lockfile is a diff to the set of bytes that will execute. A review process that reads manifest changes but not lockfile changes is reading the wrong file, and the article on integrity hashes in package metadata covers what those hashes do and do not establish.

Third, the lockfile is only as good as the resolution that produced it. A lockfile regenerated from scratch may pick entirely different versions if any range in the manifest has widened, and it may pick versions that no human ever reviewed. The common practice of committing lockfiles for applications and omitting them for libraries follows from this: an application wants a fixed graph, a library wants to be tested against the range it claims to support.

Minimum version selection, the other philosophy

Go modules resolve differently. Each module declares the minimum version of each dependency it needs, and the build list is computed as the maximum over all such minimums, transitively. There is no backtracking because there is no search: the answer is a single pass over the requirement graph, taking the highest minimum encountered for each module path. Upper bounds in a dependency’s own go.mod are ignored when that dependency is not the main module, which is why the ecosystem’s guidance is to specify minimums only.

The trade is explicit. Minimum version selection is deterministic, linear, and produces the same answer regardless of the order in which requirements are discovered. It also means a build can end up on a version of a library that the library’s own author never tested against, because nothing forces the graph down to a mutually verified combination. Backtracking resolution produces a combination that satisfies every declared constraint, which is a stronger local property and a much more expensive global one.

Neither approach says anything about whether the selected versions are free of known vulnerabilities. Resolution satisfies constraints; it does not optimize for safety, and the version that satisfies the most constraints is frequently an old one that a dependent pinned years ago.

Where resolution breaks

Several failure modes recur across ecosystems and are worth recognizing by shape rather than by tool.

Optional and platform-specific dependencies make a single lockfile describe several machines. A lockfile that records only the dependencies applicable to the current platform will be regenerated with a different result on another platform, so lockfiles generally record all variants and the installer filters at install time. The failure appears when a lockfile generated on one platform is committed and then silently amended by an install on another.

Resolver version changes alter results without any manifest change. Cargo’s resolver v2 changed how features are unified across build targets and dev-dependencies, so the same manifest resolved by two toolchain versions can produce different feature sets and different transitive graphs. Lockfiles protect against this only if the lockfile format is stable across the toolchain versions in use.

Peer dependencies express a constraint between two packages that must share an instance rather than a version range alone. When the constraint cannot be met, the honest outcomes are an error or an explicit override; the dishonest outcome, duplication, produces a program where two modules believe they are the same module.

Finally, resolution assumes the registry’s version list is honest and complete. A registry that omits versions, or that lets an attacker publish a version number ahead of the real one, changes the search space itself. This is the mechanism behind the namespace attacks described in dependency confusion and registry precedence, and it is why the set of registries a resolver consults is part of the trust boundary.

# SemVer 2.0.0 precedence, including prerelease ordering (semver.org item 11).
def parse(v):
    core, _, build = v.partition("+")
    main, _, pre = core.partition("-")
    nums = tuple(int(p) for p in main.split("."))
    return nums, (pre.split(".") if pre else None)

def key(v):
    nums, pre = parse(v)
    if pre is None:
        return (nums, 1, ())          # a release outranks any prerelease
    ids = tuple((0, int(p), "") if p.isdigit() else (1, 0, p) for p in pre)
    return (nums, 0, ids)             # numeric identifiers sort below alphanumeric

print(key("1.0.0-alpha") < key("1.0.0-alpha.1") < key("1.0.0") < key("1.0.1"))

The comparison function above is what a resolver uses to order candidates; it deliberately ignores build metadata, which is why 1.0.0+a and 1.0.0+b are indistinguishable to every range predicate and to every lockfile keyed by version string alone. The practical implication is that a registry which permits two artifacts under versions differing only in build metadata has created an ambiguity the client cannot resolve, and the client’s only defense is the artifact hash rather than the version label.