If you have not seen my previous posts, I have been working on nixpkgs-multiverse. It is a tool that lets you pin any package to any version it ever shipped, from one flake input.11nixpkgs-multiverse sitis a nice website that makes the data browseable.
You can specify a set of pins by release, commit or version. By version is particularly useful because it lets you pin packages to a version you might not want to update while still getting the latest of everything else.
multiverse.pins = {
ripgrep = "13.0.0";
fd = "8.7.0";
jq = "1.6";
hello = "2.12.1";
};
In the worst case, each of those resolves on its own, against whichever revision last shipped that version. They are four different revisions, so that configuration is four Nixpkgs trees fetched and evaluated.
The cost of the multiverse has never been per package. It is per revision touched. Asking for five packages out of one revision only costs the one revision; asking for five packages out of five revisions and you pay five times.
It would be useful however to minimize the number of Nixpkgs revisions fetched and evaluated. I thought this was a SAT problem (NP-Complete) however the problem turns out to be simpler and solvable in polynomial time, with a small caveat.
§Pins are intervals
A version is not a point in Nixpkgs history, it is a stretch. ripgrep was at 13.0.0 from June 2021 until November 2023 throughout 541 consecutive channel bumps where pkgs.ripgrep.version returned exactly that string.
Every pin is a contiguous block on one axis, and a revision serves a pin if it lands inside that pin’s block.
What is the fewest points that touch every block?
In the example above, six pins require at a minimum two revisions. The dashed lines are the Nixpkgs that actually get fetched, the dots are where each pin ends up, and the red blocks are the two pins that decided it.
§The sweep
Turns out the algorithm is relatively simple once we visualize it. It is the opposite to interval partitioning (i.e. fewest meeting rooms), we are doing activity selection.
We sort the pins by where their block ends. Walk them in that order. If the last revision you placed does not reach the block in front of you, place a new one at that block’s end.
# blocks[i] = (first, last), one pin's stretch of revisions
SWEEP(blocks):
order = indices 0..n, sorted by blocks[i].last ascending
# the revisions we will actually fetch
chosen = []
for i in order:
(first, last) = blocks[i]
if chosen and chosen[-1] >= first:
# a revision we already placed falls inside this pin's block
continue
# unserved, place a revision at the end of its block
chosen.append(last)
return chosen
The algorithm is effectively a sort plus one pass: O(n log n). Happily we did not need a solver, z3, or backtracking. It is not approximation either, we get the optimal solution.
How much can this help?
Here is a simulation of the sweep over random pin sets of various sizes, drawn from the real index. The sweep is run three times: once with one revision per pin, once minimised over any era, and once minimised over recent versions.
We are able to reduce the number of Nixpkgs revisions fetched from thirty to ten for thirty pins of recent versions. The same thirty package versions, but only ten revisions fetched and evaluated.
Tip This matters much less if you are on the fast path. A pin the store-path index knows costs no fetch at all as it is immediately substituted from cache.nixos.org.
§The Receipt
Every revision the sweep places was placed because of one specific pin, the one it could not reach. Those pins are pairwise disjoint, meaning they never overlap. k disjoint pins need k distinct revisions.
We expose this information via a “plan” that is viewable from
the mvs CLI or the Nix API. It is a certificate that the solution is optimal, and it is also useful for debugging.
$ mvs solve jq@1.6 fd@8.7.0 ripgrep@13.0.0 \
hello@2.12.1 neovim@0.10.4 helix@25.01.1
2 revisions · minimal
5 of 6 pins served by the store-path index
ATTR VERSION REVISION DATE MOVED
jq 1.6 6500b4580c2a 2023-09-25
fd 8.7.0 6500b4580c2a 2023-09-25 24 days (9 revs)
ripgrep 13.0.0 6500b4580c2a 2023-09-25 59 days (20 revs)
hello 2.12.1 698214a32beb 2025-03-25 56 days (27 revs)
neovim 0.10.4 698214a32beb 2025-03-25
helix 25.01.1 698214a32beb 2025-03-25 111 days (47 revs)
minimal: jq 1.6.x and neovim 0.10.4.x never overlapped
The sweep might place a particular version earlier than the last revision that shipped it which is highlighted by the MOVED column.
§The caveat
The problem is solvable in polynomial time, but only if every pin is contiguous. If a pin has holes in it, the problem becomes NP-Complete.
In practice though versions do have holes. A package gets dropped from Nixpkgs and comes back at the same version albeit very uncommon.22About 1.7% of all (attribute, version) pairs in the index have such holes. The sweep above does not know which stretch to use, and it is possible that the wrong choice will force a second revision.
A hole turns one decision into two:
- which revisions do we place?
- which stretch of each pin do we aim at?
For instance, suppose foo shipped 1.0, lost it, and got it back later for two stretches. bar 2.0 was only ever current during the first of them.
Depending on which stretch of foo you choose, the plan is either one or two revisions. The choice of which stretch to use cannot be made by looking at foo alone, only by looking at bar.
This turns each decision into two, causing the algorithmic complexity to become exponential in the number of holed pins. The problem is NP-Complete, and it is equivalent to vertex cover.
This is the part I got wrong. I looked at the problem and saw constraints being satisfied, which I pattern-matched to SAT.
Turns out by by not having a second choice, we get to stay in polynomial time. The fix is to not have a second choice. A pin is defined to take the newest of its stretches and only that one which simplifies our problem. Our greedy algorithm is now optimal.
§Minor footgun
Grouping pins pulls some of them backwards. From our example above: helix 25.01.1 is picked earlier than the last revision that shipped it in order to group with neovim 0.10.4.
What does this mean in practice?
Although a version is a stretch, it is technically not the same throughout. Dependencies and build inputs can change, so the closure of a package at one revision is not guaranteed to be the same as the closure of that same package at another revision, even if the version string is identical.
You may be missing improvements or fixes to the closure of a package despite the version string being the same.
§Using it
mvs solve answers the fewest revisions necessary to serve a set of pins.
# the plan, as JSON, with the certificate
$ mvs solve --json python3@3.8 nodejs@14 | jq .why
"one revision serves every pin"
# if you need exactly one Nixpkgs, assert it -- the plan already knows
$ mvs solve --json python3@3.8 nodejs@14 | jq -e '.revisions == 1'
An existing lock file can be optimized in place:
$ mvs lock minimize
4 pins · 4 revisions → 1 · minimal
ATTR VERSION REVISION DATE OLDER BY
fd 8.7.0 6500b4580c2a 2023-09-25 24 days
hello 2.12.1 6500b4580c2a 2023-09-25 603 days
ripgrep 13.0.0 6500b4580c2a 2023-09-25 59 days
minimal: one revision serves every pin
# report and refuse to write, for CI
$ mvs lock minimize --check
On the Nix side, the whole set resolves at once:
mv.solvePins { ripgrep = "13.0.0"; fd = "8.7.0"; jq = "1.6"; }
# => { ripgrep = <drv>; fd = <drv>; jq = <drv>; }
# all three out of 2023-09-25-6500b4580c2a
You can customize this behavior through the modules. It is on by default:
{
multiverse.pins = {
python3 = "3.8.9";
nodejs = "14.17.3";
};
# `plan` is computed from the index without
# fetching anything, so you can
# demand a single Nixpkgs and fail the
# build if you cannot have one.
assertions = [
{
assertion = config.multiverse.plan.revisions == 1;
message = config.multiverse.plan.why;
}
];
}
You can find the full design and API documentation on the nixpkgs-multiverse website.