Version Ranges as Sets of Versions

A dependency declaration almost never names a version. It names a condition, and the condition is written in a small language whose meaning is easy to guess and surprisingly hard to pin down. The resolver cannot work with the surface syntax at all; its first act is to translate each declaration into a set of concrete versions drawn from the registry. Everything downstream — backtracking, conflict reporting, lockfile contents — operates on those sets, so the precision of the translation determines how often the resolver makes a decision a human would call wrong.

A range is a predicate, not an interval

Semantic Versioning defines precedence in clause 11: compare the major, minor, and patch numbers numerically, left to right; a version carrying a prerelease suffix has lower precedence than the same major.minor.patch without one; build metadata is ignored entirely when precedence is computed. That gives a total preorder over the version strings a registry publishes, and because build metadata makes distinct strings compare equal, it is a preorder rather than a strict total order.

With an order in hand, the common range forms expand mechanically. In the syntax popularised by npm, ^1.2.3 means “at least 1.2.3, below 2.0.0”, ~1.2.3 means “at least 1.2.3, below 1.3.0”, 1.x means “at least 1.0.0, below 2.0.0”, and a hyphen form 1.2.3 - 2.3.4 is an inclusive pair of bounds. Cargo’s caret is the default for a bare version and applies a special rule below 1.0: ^0.2.3 allows >=0.2.3, <0.3.0, while ^0.0.3 allows only >=0.0.3, <0.0.4. The intent is that the leftmost non-zero component marks the compatibility boundary, so a 0.x release can break between minor versions without violating the declaration.

The result of expansion is better described as a predicate than as an interval, because the syntactic forms compose by union and intersection and the underlying version set is discrete and sparse. A range like 1.x || >=3 is a union of two pieces. A registry that has published 1.0.0, 1.1.0, and 3.2.0 satisfies it with three versions and nothing in between. The interval arithmetic view — bounds in, bounds out — remains useful for pruning, but the final answer to “does version v satisfy range r” is a comparison sequence, not a containment test over reals.

Intersecting two constraints

When two packages require the same dependency, the resolver intersects their ranges and asks the registry for versions in the result. Intersection distributes over union: intersect every disjunct of the first range with every disjunct of the second, then discard empty results. Two conjunctive comparator sets intersect by concatenating their comparators and checking consistency, which reduces to comparing the tightest lower bound against the tightest upper bound. A set such as >=2.0.0 <2.0.0 is empty by inspection; >2.0.0 <2.0.1 is non-empty in the abstract ordering but contains no release, only prereleases of 2.0.1, which the default rules exclude.

This is the first place where two different kinds of emptiness appear, and conflating them produces bad error messages. A constraint can be unsatisfiable in the algebra — no version whatsoever could satisfy it — or it can be unsatisfiable against the registry, meaning the published set has a gap where the constraint expects a version. The first is a manifest bug that no registry change will fix. The second is a normal event: a package declares a dependency on a version that was yanked, or on a version that only exists in a private registry the client cannot see. Resolvers that report both as “no matching version found” leave the user guessing which of the two situations applies.

The cost of the intersection itself is small. With k comparators across the operands, sorting and comparing bounds is O(k log k), and in practice k is a handful. The expense of resolution lies almost entirely in the number of intersections that must be tried, not in any single one.

Prereleases break the interval model

Every major ecosystem adds a rule that a version with a prerelease suffix is not a normal candidate. The rule in node-semver is stated precisely: a version with a prerelease tag can satisfy a comparator set only if at least one comparator in that set carries a prerelease tag on the same major.minor.patch tuple. So >=1.0.0 does not admit 2.0.0-beta.1, and neither does <3.0.0, and the intersection of the two rejects it as well. The rule is compositional for that example, which makes it look like a filter applied at the end.

It is not. Consider >=1.0.0-beta. This admits 1.0.0-beta and 1.0.0, and it admits 1.5.0 and 2.0.0. It does not admit 1.5.0-beta or 2.0.0-beta, because neither of those carries the tuple 1.0.0 that the comparator mentions. The admitted set therefore contains a point at its lower edge, excludes prereleases strictly above that point, and includes all releases. No interval with two endpoints describes that shape; the predicate does. The practical consequence is that candidate evaluation cannot be reduced to a bounds check. The usual implementation sorts candidates in descending order and tests each one, taking the first that satisfies, which is O(n) comparisons per query rather than O(log n).

The rule also has a consequence for the resolver’s search rather than for a single check. Because prerelease admission depends on the exact tuple named in a comparator, two ranges that are individually satisfied by a prerelease are not necessarily jointly satisfied by it after intersection unless some comparator in the combined set still names that tuple. Intersection must preserve the prerelease comparators rather than reduce them to numeric bounds, or the combined range will silently change meaning.

Ordering is registry-specific

Semantic Versioning is not the only ordering in use, and a resolver’s range semantics are defined relative to the ordering its registry uses. PEP 440 defines a richer version grammar: an epoch prefix before an exclamation mark, pre-release spellings including a, b, rc, post-releases, development releases, and local version labels after +. Its ordering places .devN releases before the corresponding release, treats post-releases as later, and gives === as an arbitrary-equality operator for versions that do not follow the scheme at all.

Debian’s version comparison sorts a tilde before everything, including the empty string, which gives maintainers a way to make 1.0~rc1 sort below 1.0. A resolver that assumed semver ordering while reading Debian metadata would order those two backwards and could select a release candidate as an upgrade over the final release. The mechanism is the same in all cases — a total order plus a predicate language — but the order is a property of the ecosystem, not of the word “version”.

Bounds the language cannot express

Two things a range language generally cannot say are worth naming, because they push work into the resolver. The first is a negative constraint on a specific version. The common comparator sets offer >, >=, <, <=, and equality; expressing “any 1.x except 1.4.0” requires a union of two ranges, and expressing “except 1.4.0 and 1.4.1 and 1.4.2” grows linearly with the exclusions. A range language with set difference would compress this, at the cost of a more complex intersection algorithm.

The second is any constraint that relates two packages rather than bounding one. “The same version of the parser and the code generator” is a statement about the solution, not about either package’s admissible set, and it cannot be attached to a single declaration. Such constraints appear in practice as peer dependencies and as resolution overrides, and they change the shape of the search rather than the shape of a range. The graph the ranges hang off, and the identity of its nodes, is the subject of Building the Dependency Graph from Manifests; the artifact that freezes one chosen assignment is described in What a Lockfile Records.

Evaluating a candidate cheaply

A resolver evaluates the same ranges thousands of times, so the translation from syntax to predicate is normally done once and cached. The expansion produces a normalised list of comparator sets, each an ordered list of bounds plus the prerelease tuples that were mentioned. Testing a candidate walks the comparators of each set in order of selectivity and stops at the first failure. Because most candidates fail on the first comparator, the average cost is close to constant even though the worst case is linear in the number of comparators.

def parse(v):
    core, _, pre = v.partition('+')[0].partition('-')
    parts = [int(x) for x in core.split('.')]
    return (parts + [0, 0, 0])[:3], pre

def cmp_pre(a, b):
    # A normal version outranks any prerelease of the same tuple.
    if a == b: return 0
    if not a: return 1
    if not b: return -1
    for x, y in zip(a.split('.'), b.split('.')):
        if x.isdigit() and y.isdigit():
            if int(x) != int(y): return -1 if int(x) < int(y) else 1
        elif x.isdigit():
            return -1          # numeric identifiers rank below alphanumeric ones
        elif y.isdigit():
            return 1
        elif x != y:
            return -1 if x < y else 1
    return (len(a.split('.')) > len(b.split('.'))) - (len(a.split('.')) < len(b.split('.')))

def compare(u, v):
    (un, up), (vn, vp) = parse(u), parse(v)
    if un != vn:
        return -1 if un < vn else 1
    return cmp_pre(up, vp)

The remaining piece the snippet leaves out is the interesting one: a comparison alone does not answer satisfaction, because the prerelease rule needs the tuple and the suffix separately. That is the same distinction between ordering and admissibility that makes the algebra more than interval arithmetic.

Sorting a registry’s version list once with this comparison gives the resolver a stable candidate order, and “highest satisfying version” becomes a scan of that list. That policy is a choice, not a theorem. Ecosystems that select the lowest admissible version, or the maximum of declared minimums, get different answers from the same ranges, and the difference is large enough that it changes what package authors must guarantee about compatibility.