Registry Resolver: Versions, Backtracking, Lockfiles and Conflict Reports

Registry Resolver: Versions, Backtracking, Lockfiles and Conflict Reports

The monorepo's private package registry has a small dependency resolver in front of it. It was written for the early days, when everything was ^1.x and a greedy pick was good enough. It no longer is: teams ship pre-releases, 0.x packages, and packages that quietly disagree about their shared libraries. Platform has queued five tickets against it. You are on the hook for as many as you can land safely; the later ones build on the earlier ones.

Codebase

How your code is run

run(operations: list[list]) -> list executes the operations in order against a fresh, empty registry and returns one result per operation. Every operation is [name, *args]. Errors are returned as "error: <code>" strings, never raised. Package names match [a-z][a-z0-9-]{0,39}. A dependency list is a list of [name, constraint] pairs; its order is the declaration order and it matters.

• A wrong number of arguments, a wrong argument type, or a malformed dependency list (not a list of two-string pairs) returns "error: invalid arguments"; an unknown operation returns "error: unknown operation".
• matching on a package that was never published returns [].
• A version string is MAJOR.MINOR.PATCH or MAJOR.MINOR.PATCH-PRERELEASE. Numbers are non-negative integers without leading zeros (0 is fine, 01 is not). PRERELEASE is one or more .-separated identifiers made of [0-9A-Za-z-]; none may be empty, and an identifier made only of digits has no leading zero. Build metadata (+...), partial versions (1.2) and a v prefix are invalid.
• resolve returns every package in the solution as "name@version", sorted by name (plain string order). Roots that need nothing resolve to [].

Version precedence (one rule, used everywhere)

Compare MAJOR, then MINOR, then PATCH as numbers. If those tie, a version without a pre-release is greater than one with. Between two pre-releases compare identifiers left to right: two numeric identifiers compare as numbers; two non-numeric ones compare as ASCII strings; a numeric identifier is lower than a non-numeric one; if all shared identifiers are equal, the pre-release with more identifiers is greater. So 1.0.0-2 < 1.0.0-10 < 1.0.0-alpha < 1.0.0-alpha.1 < 1.0.0-alpha.beta < 1.0.0-beta.2 < 1.0.0-beta.11 < 1.0.0-rc.1 < 1.0.0.

Constraints

A constraint is one or more alternatives separated by || (spaces around it are optional). An alternative is one or more comparators separated by whitespace; all of them must hold. Empty alternatives (^1.0.0 ||, ||, the empty string) are invalid, and so is any token that is not a comparator (a lone |, >= 1.0.0 with a space after the operator, latest).

The version in a comparator must be a complete valid version (^1.2 is invalid). The bounds a ^ or ~ expands to are ordinary >=/< comparators; for ^1.2.3-beta.2 that means >=1.2.3-beta.2 <2.0.0.

Pre-releases are opt-in, per alternative. A version that has a pre-release tag can satisfy an alternative only if, in addition to passing every comparator, some comparator written in that alternative has a pre-release tag on the same MAJOR.MINOR.PATCH. (Tags in a different alternative do not count; the bounds a ^/~ expands to count as written only if the version you wrote had a tag.) So <2.0.0 and ^1.4.0 never match 2.0.0-rc.1, >=1.2.3-beta.1 matches 1.2.3-beta.2 but not 1.3.0-alpha, and * matches no pre-release at all.

How resolve works today

resolve(roots) decides packages in the order they are first required: the root requirements' packages in the order given, then the dependencies of each decided package in its declared order. All root constraints are in force from the start. When a package comes up, it pins the highest version that satisfies every constraint currently in force on it (a package named by two roots must satisfy both); that version's dependencies then add constraints. If a package has no matching version, or a chosen version's dependency is already decided to something that does not satisfy it, the answer is "error: no solution".

Worked example (Part 1 rules)

[["publish", "lib", "1.9.0", []],
 ["publish", "lib", "1.10.0", []],
 ["publish", "lib", "2.0.0-rc.2", []],
 ["publish", "lib", "2.0.0-rc.10", []],
 ["publish", "lib", "2.0.0", []],
 ["matching", "lib", "^1.0.0"],
 ["matching", "lib", ">=2.0.0-rc.1"],
 ["matching", "lib", "<2.0.0"],
 ["matching", "lib", "*"]]

returns

[true, true, true, true, true,
 ["1.10.0", "1.9.0"],
 ["2.0.0", "2.0.0-rc.10", "2.0.0-rc.2"],
 ["1.10.0", "1.9.0"],
 ["2.0.0", "1.10.0", "1.9.0"]]

Part 1 — Versions and constraints misbehave (PLAT-3318)

Goal: make version ordering, version parsing and constraint matching follow the rules above, so that publish, matching and resolve agree with them.

Reports from teams:

1. "1.0.0-rc.1 was installed even though 1.0.0 was published." and "rc.10 is treated as older than rc.2."
2. "^0.2.3 let 0.9.1 through." (^0.0.3 has the same kind of problem.)
3. "A 2.0.0-alpha got installed for ^1.4.0." and ">=1.0.0-beta accepted 1.5.0-alpha."
4. "^1.0.0 | ^2.0.0 and ^1.0.0 || are accepted but should not be."
5. "I published 01.2.3 and 1.0.0-01 and the registry took them."

Everything in the section above is the specification; the reports are just symptoms. No operation or error code changes in this Part.

Part 2 — Resolve with real backtracking (PLAT-3341)

Goal: resolve must find a solution whenever one exists, instead of giving up at the first dead end. This replaces the greedy behaviour described above.

A solution assigns exactly one version to every package that is needed, such that each root constraint and each chosen version's dependencies are satisfied. Nothing outside the requirement graph is pinned, and yanked versions (Part 3) are never chosen.

Several solutions may exist, and the answer must be the one the following search reaches first.

Search order

1. Packages are decided in the order they are first required (roots in the order given, then the dependencies of each already-decided package in decision order, each in declared order). A package is queued once, at its first mention. "Next package" always means the first queued package that is still undecided.
2. The candidates for a package are the versions satisfying every constraint currently in force on it (from the roots and from the versions chosen so far), highest first.
3. A candidate is rejected immediately if one of its dependencies names an already-decided package whose chosen version does not satisfy the dependency. Otherwise it is chosen, and its dependencies are added to the constraints in force and to the queue.
4. If a package has no candidate left, undo the most recent decision, including everything it added (its constraints and the packages it queued), and try that package's next candidate. If the very first package runs out, the answer is "error: no solution".
5. The answer is the first complete assignment found. Chronological backtracking is enough to get it right for now; Part 5 is about doing it fast.

Worked example

[["publish", "core", "1.5.0", []],
 ["publish", "core", "2.1.0", []],
 ["publish", "ui", "1.1.0", [["core", "^1.0.0"]]],
 ["publish", "ui", "1.2.0", [["core", "^2.0.0"]]],
 ["publish", "db", "1.0.0", [["core", "^1.0.0"]]],
 ["publish", "app", "1.0.0", [["ui", "^1.0.0"], ["db", "^1.0.0"]]],
 ["resolve", [["app", "^1.0.0"]]]]

returns [true, true, true, true, true, true, ["app@1.0.0", "core@1.5.0", "db@1.0.0", "ui@1.1.0"]]: ui@1.2.0 needs core ^2.0.0, db then needs core ^1.0.0, core has no candidate, so the search undoes db and ui@1.2.0 and retries ui@1.1.0. The greedy resolver says no solution here.

Part 3 — Lockfiles and yanked versions (PLAT-3377)

Goal: resolve accepts an optional second argument, a lock: an object mapping package names to version strings pinned by a previous resolution. Re-resolving should keep what was pinned and move as little as the new requirements force. Separately, teams can yank a bad release.

Lock rules

1. A lock is a preference, never a constraint. Constraints, rejection and backtracking work exactly as in Part 2. Only the *order in which a package's candidates are tried* changes.
2. For a locked package with locked version L, the candidates are tried in this order: L itself (if it satisfies the constraints in force), then every candidate above L from the lowest up (the smallest upgrade first), then every candidate below L from the highest down (the smallest downgrade first). L need not be a published version; it is just the anchor.
3. A package that is not locked still tries its candidates highest first. Lock entries for packages that end up not needed are ignored; they may even name packages the registry has never seen.
4. The lock must be an object, otherwise "error: invalid arguments". Each value must be a valid version string, otherwise "error: invalid version". Checks on the roots (invalid name, invalid constraint) come first.

Yank rules

1. yank name version marks a published version as yanked and returns true; yanking an already yanked version also returns true. Errors: invalid name, invalid version, unknown version.
2. A yanked version stays published: it still occupies its number (publish of it returns version exists), but it is not offered to anyone. matching no longer lists it (this changes Part 1's matching), and resolve never chooses it, with one exception: a yanked version that is the exact lock entry for its package may still be chosen if it satisfies the constraints in force (existing installs keep working). It is then tried first, like any locked version; other yanked versions are never candidates, whatever their distance from the lock.

Worked example

[["publish", "lib", "1.4.0", []], ["publish", "lib", "1.5.0", []], ["publish", "lib", "1.6.0", []],
 ["publish", "lib", "1.9.0", []], ["publish", "lib", "2.0.0", []],
 ["publish", "app", "1.0.0", [["lib", ">=1.5.0"]]],
 ["resolve", [["app", "^1.0.0"]]],
 ["resolve", [["app", "^1.0.0"]], {"lib": "1.4.0"}],
 ["resolve", [["app", "^1.0.0"]], {"lib": "1.9.0"}],
 ["yank", "lib", "1.5.0"],
 ["resolve", [["app", "^1.0.0"]], {"lib": "1.4.0"}],
 ["resolve", [["app", "^1.0.0"]], {"lib": "1.5.0"}],
 ["matching", "lib", ">=1.5.0"]]

returns

[true, true, true, true, true, true,
 ["app@1.0.0", "lib@2.0.0"],
 ["app@1.0.0", "lib@1.5.0"],
 ["app@1.0.0", "lib@1.9.0"],
 true,
 ["app@1.0.0", "lib@1.6.0"],
 ["app@1.0.0", "lib@1.5.0"],
 ["2.0.0", "1.9.0", "1.6.0"]]

The lock 1.4.0 violates >=1.5.0, so the smallest upgrade wins, not the newest. After the yank, 1.5.0 is skipped unless it is the lock entry.

Part 4 — Say why it failed (PLAT-3402)

Goal: explain(roots) answers *why* a resolution is impossible, as a short list of requirements that cannot all be met together. It never uses a lock.

1. If resolve(roots) (without a lock) would succeed, return "error: resolvable". Argument errors are as for resolve.
2. Otherwise build the requirement list, in this order: the root requirements in the order given; then, for every package in name order (plain string order), every version of it that is not yanked from newest to oldest, and for each version its dependencies in declared order. A requirement is one entry in one of those lists.
3. Walk that list from the bottom to the top. For each requirement, remove it (as if it had not been declared; the version that declared it stays published) if the problem is still unsolvable with the requirements removed so far also gone; otherwise keep it. What is kept is the conflict.
4. Return a list: first "no solution; conflicting requirements:", then one line per kept requirement in list order: "- root requires <name> <constraint>" for a root requirement and "- <name>@<version> requires <dependency> <constraint>" for a declared dependency. The constraint is printed exactly as it was written.

Worked example

[["publish", "lib", "1.0.0", []],
 ["publish", "lib", "2.0.0", []],
 ["publish", "log", "1.0.0", []],
 ["publish", "app", "1.0.0", [["lib", ">=2.0.0"]]],
 ["publish", "plug", "1.0.0", [["lib", "<2.0.0"], ["log", "*"]]],
 ["explain", [["app", "^1.0.0"], ["plug", "^1.0.0"], ["log", "*"]]]]

returns

[true, true, true, true, true,
 ["no solution; conflicting requirements:",
  "- root requires app ^1.0.0",
  "- root requires plug ^1.0.0",
  "- app@1.0.0 requires lib >=2.0.0",
  "- plug@1.0.0 requires lib <2.0.0"]]

The log requirements are removed because the problem stays unsolvable without them. Every requirement left is needed: remove any one and a solution appears.

Part 5 — Resolution at scale (stretch, PLAT-3420)

Goal: a resolution must finish quickly even when a late dead end has nothing to do with the decisions made just before it. The answer must still be exactly the one the Part 2 and Part 3 search order defines.

generate publishes a synthetic registry (see pkgres/synthetic.py, known-good). With {"family": "thrash", "independent": N, "versions": V, "gate": "fixable" | "hopeless"} it publishes N*V + 6 versions (gate defaults to "fixable") and returns that count. With roots that list the N packages ind-00 ... first and app last, the highest hub always fails, and with plain chronological backtracking the search tries every combination of the ind-* versions before it revisits hub. Hidden tests use N and V large enough that this is hopeless within a few seconds: both resolve (with and without a lock) and explain must stay fast.

Example

[["generate", {"family": "thrash", "independent": 2, "versions": 2}],
 ["resolve", [["ind-00", "^1.0.0"], ["ind-01", "^1.0.0"], ["app", "^1.0.0"]]]]

returns [10, ["app@1.0.0", "gate@2.0.0", "hub@2.0.0", "ind-00@1.1.0", "ind-01@1.1.0"]].

Notes

• names.py, registry.py publish validation, errors.py, config.py and synthetic.py are known-good.
• You may use the AI assistant freely; you are expected to verify what it produces.
• Later parts must not break earlier ones; hidden tests re-check earlier behaviour (for example matching after a yank, or the Part 1 constraint rules inside a locked resolution).
• Parts 1-3 is a strong result. Parts 4 and 5 are a stretch.