A build graph that rolls dice

Recorded: Sept. 22, 2026, 12:09 p.m.

Original

Summarized

A build graph that rolls dice | Farid Zakaria’s Blog

Farid Zakaria

2026-09-20
·
8 min read

A build graph that rolls dice

We are right around the corner from NixCon 2026. Another year where I sadly won’t be present.
I looked at the lineup and saw quite a few talks on dynamic derivations, along with some recent other posts on the topic such as cargo-dyndrv which had me thinking about revisting the topic since my earlier posts on the subject.
I wanted to better understand the implications of dynamic derivations and how they change the build graph. Originally, I was focused on how it could replace the lang2nix style of build graph generation, but I realized that the implications are much broader than that.
The graph does not need to be known up front. It can be defined as the build progresses. 🧐
What do I mean?
Traditionally, Nix requires you to ask it to build anything and it will tell you exactly the steps it will take ahead of time as the “derivations” that comprise the build graph.
$ nix-store -q --requisites \
$(nix-instantiate '<nixpkgs>' -A hello) | grep -c '\.drv$'
196

This is an important property of Nix. It is what makes it possible to reason about builds without running them by understanding what will be built.
Many Nix tools rely on this property via nix build --dry-run.
For instance, nix-diff tells you why two closures differ without building either.
Why does dynamic derivations change this?
§Applicative, monadic, bind
In functional languages it’s very easy to get abstract and use fancy words like “applicative” and “monadic” to describe the difference between types of computation. The difference is subtle, but it is profound.
Nix traditionally was an “applicative” build system. Dynamic derivations make it a “monadic” build system. The difference is that in an applicative build system, the entire build graph is known up front, while in a monadic build system, the graph can be defined as the build progresses.11The paper Build Systems à la Carte is the defacto read on this topic.
One way to think about the difference is to look at the type signatures of the two operations that define them:
<*> apply :: f (a -> b) -> f a -> f b
>>= bind :: m a -> (a -> m b) -> m b

apply (applicative) takes f a a value known ahead of time and returns the result f b. You can see the entire graph before you run it.
bind (monadic) takes (a -> m b), a function, to return m b. You cannot see the entire graph before you run it.
Applicative can be thought of writing the shopping list before you leave the house. You read the recipe, you write down every ingredient, you drive to the store once. The list is a function of the recipe and nothing else.
Monadic is a recipe with a step that says taste it, and if it is too salty, go buy a potato. You cannot write that shopping list up front. Whether the potato is on it depends on the saltiness, and the saltiness does not exist until you have already done some of the cooking.
Nix used to be solely the former, dynamic derivations add the latter.
§Actually, nix always had bind

Okay, I guess I should have said “Nix is now monadic in the scheduler”. Nix has always had bind in the evaluator. We have been doing monadic builds for years. We call it
import from derivation.
let
inner = pkgs.runCommand "inner" {} "sleep 10; echo hi > $out";
in
pkgs.runCommand "outer" {} "echo ${builtins.readFile inner} > $out"

builtins.readFile on a derivation output is a bind in exactly the sense above: what to build next is a function of a value that does not exist yet. The Nix evaluator cannot produce the graph without that value, and the only way to get it is to stop evaluating and run a builder.
Unfortunately, this has a lot of footguns, such as causing
nix-instantiate to take ten seconds,
and why nixpkgs bans the technique outright.
Whereas import from derivation is a bind in the evaluator, dynamic derivations now adds bind in the scheduler. The difference is that the scheduler can run builders in parallel, ship them to remote machines, and it can substitute their results from a cache. The evaluator cannot do any of that.
Dynamic derivations do not add the bind. The bind was always there. What changes is which layer performs it. 🤓
§Let’s roll some dice
Many of the examples of dynamic derivations have been focused on build graph generation via lang2nix tooling, but I wanted to explore the implications of dynamic derivations in a more general sense.
In the true monadic sense, the build graph can be defined as the build progresses. The next step in the build graph can depend on the result of a previous step.
Here is a really simple example, chain.nix & step.sh, that rolls a die and either stops or continues the chain by adding a new derivation step to the build graph. The depth of the chain is random, and the result of the build is how deep we got.
Only the leftmost box exists when you run nix-instantiate. Everything to the
right of it is written by a builder, while the build is already underway.

cluster_eval

in chain.nix

cluster_run

written by step.sh, mid-build

step

step-N
roll a d6

res

dice-result
echo N > $out

step->res

six

pass

passthrough-N
cp $inner $out

step->pass

anything else

step-N+1
depth + 1

pass->next

input: ^out^out

more
…

next->more

Show chain.nix
{ depth ? 1
, pkgs ? import <nixpkgs> { }
, bash ? pkgs.bash
, coreutils ? pkgs.coreutils
, nix ? pkgs.nixVersions.latest
, chain ? ./chain.nix
, step ? ./step.sh
}:
let
roller = derivation {
name = "step-${toString depth}.drv";
system = builtins.currentSystem;
builder = "${bash}/bin/bash";
args = [ "-e" "${step}" ];

DEPTH = toString depth;
BASHPKG = "${bash}";
COREUTILS = "${coreutils}";
NIXPKG = "${nix}";
CHAIN = "${chain}";
STEP = "${step}";
PATH = "${coreutils}/bin:${nix}/bin";

# The builder instantiates derivations, so it needs a store to talk to.
requiredSystemFeatures = [ "recursive-nix" ];

# This derivation's output is a .drv file. That is what makes it dynamic.
__contentAddressed = true;
outputHashMode = "text";
outputHashAlgo = "sha256";
};
in
builtins.outputOf roller.outPath "out"

Show step.sh
set -eu
export NIX_CONFIG='experimental-features = nix-command ca-derivations dynamic-derivations'

roll=$(( $(od -An -N1 -tu1 < /dev/urandom) % 6 + 1 ))
echo "depth $DEPTH rolled a $roll"

if [ "$roll" -eq 6 ]; then
# Six. Stop. The answer is how deep we got.
cat > answer.nix <<NIX
let bash = builtins.storePath $BASHPKG; in
derivation {
name = "dice-result";
system = builtins.currentSystem;
builder = "\${bash}/bin/bash";
args = [ "-c" "echo $DEPTH > \$out" ];
__contentAddressed = true;
outputHashMode = "recursive";
outputHashAlgo = "sha256";
}
NIX
else
# Not a six. My answer is whatever the next level answers.
cat > answer.nix <<NIX
let
bash = builtins.storePath $BASHPKG;
coreutils = builtins.storePath $COREUTILS;

# This is the bind. Asking chain.nix for the next depth neither builds it
# nor evaluates it here: it yields a placeholder standing for "whatever
# depth $(( DEPTH + 1 )) eventually answers".
inner = import (builtins.storePath $CHAIN) {
inherit bash coreutils;
depth = $(( DEPTH + 1 ));
nix = builtins.storePath $NIXPKG;
chain = builtins.storePath $CHAIN;
step = builtins.storePath $STEP;
};
in
derivation {
name = "dice-passthrough";
system = builtins.currentSystem;
builder = "\${bash}/bin/bash";
args = [ "-c" "cp \$inner \$out" ];
PATH = "\${coreutils}/bin";
inherit inner;
__contentAddressed = true;
outputHashMode = "recursive";
outputHashAlgo = "sha256";
}
NIX
fi

cp "$(nix-instantiate answer.nix)" "$out"

The general idea of this derivation is:

roll a six and we write a derivation that echoes the depth. Ordinary, nothing dynamic about it. This terminates the build graph.
roll anything else and we write a passthrough: a derivation whose only job is cp $inner $out, where inner is import chain.nix { depth = n + 1; }.

Either way the file copied into $out is a .drv, so builtins.outputOf works the same on a chain that stopped and a chain that kept going.22We actually need a depth parameter to avoid infinite recursion and so that the store-path of the derivations are different since they are content-addressed.
We can see the build graph grow in the denominator as the build progresses.

If we try to introspect the graph with --dry-run or nix-store -q --tree, we get nothing. Since the graph is not known yet, our tools cannot see it.
$ nix build --store /tmp/dice -f ./default.nix --dry-run
warning: Ignoring dynamic derivation /nix/store/vnm4l32g…-step-1.drv.drv^out
while querying missing paths; not yet implemented

Dynamic derivations introduce a second graph that exists only after the build, and the ecosystem has no
way to introspect it yet.
I ran the build 900 times and logged the length of the chain. Rolling a six-sided die is one of the most classic ways to simulate geometric decay and we can see the results in the histogram below. The mean is 6.18, median 4, longest 46.

1980-01-01T00:00:00+00:00
image/svg+xml

Matplotlib v3.10.5, https://matplotlib.org/

100

150

derivations in the chain

runs out of 900

The math maths.
§Beyond lang2nix
Every dynamic derivations demo so far, mine included, has been a build system:
MakeNix for C,
NpmNix for node,
cargo-dyndrv for Rust,
nix-ninja for ninja. That is a reasonable place to start but it does not capture the full power of the primitive. What other ideas can we explore?
Mario. In Super Mario Derivations
the attribute path is the button sequence and I have to supply the press count.
The dynamic version emulates until Mario dies. The stopping condition is data,
discovered mid-build, and the run is however long it turns out to be.
Searching a state space. Swap the die for a predicate and you have a search
where each frontier node is a derivation. Model checking, puzzle solvers, a
fuzzer that only expands inputs which found new coverage. States you reach twice
collapse onto one store path, and they survive a reboot.
Crawling. Fetch a page, parse the links, emit one derivation per link. The
frontier is discovered rather than declared, the crawl resumes because the store
remembers every page already fetched, and the dependency graph of the result is
the link graph.
What are the bounds of this primitive? I don’t know.
The size of the graph now is only limited by whether Nix stops emitting successors. There is no depth limit for the store layer, no max-call-depth equivalent. My longest honest chain in the die-roll was 46 deep, but I had rigged examples that went to 500. How far can it go?
I am so brainwashed to thinking about making a plan before I start for my build systems, that the idea of making it up as I go is a little scary. 😨

Improve this pageEdit @ bc0131e

·
Text is CC BY-SA
·

RSS

/nix/store/r75sl1al4pxsnpaz3yv77rmj3lxvwd44-fzakaria.com

Farid Zakaria explores the implications of dynamic derivations on the structure of the build graph within the Nix ecosystem, focusing on the shift from an applicative to a monadic style of build systems. Traditionally, Nix operated as an applicative build system, meaning the entire build graph, defined by the derivations, was known upfront. This characteristic allowed for reasoning about builds before execution, as the system determined all necessary steps ahead of time. This is conceptually similar to writing a complete shopping list before leaving home.

Dynamic derivations introduce the monadic aspect by allowing the build graph to be defined incrementally as the build progresses. This change is fundamentally rooted in the difference between the applicative operation apply and the monadic operation bind. The applicative approach, exemplified by apply, requires all information to be known beforehand, whereas the monadic approach, exemplified by bind, permits the definition of subsequent steps based on results that are determined during execution. In the context of Nix, while the system always possessed the bind operation within the evaluator (the ability to sequence operations based on existing values), dynamic derivations fundamentally change *where* this sequencing occurs.

The critical distinction lies in which layer performs the binding. In traditional Nix, the bind operation existed in the evaluator, meaning the full graph was established before running the evaluation. However, dynamic derivations introduce bind into the scheduler, enabling features like parallel execution, shipping builders to remote machines, and utilizing caching based on results, capabilities that the evaluator alone cannot provide. This means dynamic derivations add a layer of dynamic dependency management to the execution environment, rather than redefining the core binding mechanism itself.

Zakaria illustrates this dynamic growth using an example involving a chain build where the next step in the graph depends on a random outcome. This demonstrates how dynamic derivations allow the build graph to evolve mid-process. In the die-roll example, the structure of the build graph grows dynamically based on the outcome, simulating a process where the graph is not static but emerges during execution. Although this dynamic growth presents challenges for introspection—as tools like nix build dry-run cannot immediately see the entire dynamically generated graph—the resulting process allows for explorations into potential broader applications.

Beyond specific build system tooling, the author suggests exploring the general potential of dynamic derivations in areas utilizing state space exploration, such as model checking, puzzle solving, and fuzzing, where the search frontier is discovered rather than predetermined. Other potential applications include crawling, where dependencies are discovered through fetching web pages, leading to an emergent dependency graph. The scope of this primitive is constrained primarily by the stopping conditions implemented by the build; there is no inherent depth limit for the store layer, allowing for potentially very long, dynamically generated dependency chains.