Why this works
During a Nix build, commands run in a shared directory. A Bazel or Buck2 rule gets its own sandbox. Will the compiler still produce the same object file there? genrulify tries the compile with the inputs the rule will get. The proof explains how the result of each checked rule carries through to the final archive.
One path, two versions
In the example build, the Unix command dd
copies text from one file to another. The first dd writes the line
Genrulify to /build/bundle. The second appends the line
one file, two versions to that same file. A third command copies the
finished bundle to the package output.
genrulify writes the build graph in a language called MLIR. Each
splice.exec represents a group of processes that genrulify
runs together. Here each group contains one invocation of dd. A shell
pipeline would put several commands in one group. In this example,
at 735 is the step where execve started the first dd.
%sandbox_717 = splice.literal "sandbox" at 717 -> [
#splice.entry<"/build" dir 700 mtime 1>
]
%dd_735 = splice.exec "dd" at 735(%sandbox_717) -> [
#splice.entry<"/build/bundle" file 644 mtime 1 "cb94740a…">
]
%dd_764 = splice.exec "dd" at 764(%sandbox_717, %dd_735) -> [
#splice.entry<"/build/bundle" file 644 mtime 1 "50f55425…">
]
The splice.literal supplies the recorded /build directory.
Now read the first splice.exec from right to left. The entry after the arrow
describes the file the command produced, including its path and content hash
(shortened here). The name before the equals sign, %dd_735, is how
another rule refers to that version of /build/bundle.
The parentheses list filesystem inputs. At step 764, (%sandbox_717, %dd_735)
tells the rule to recreate the /build directory and put the first
version of bundle there before starting dd. The two
commands exchange data through that file. %dd_764 names the version
containing both lines. The source text files that dd copies from are
already available at their recorded paths in the Nix store.
What the checker actually runs
The checker is the part of genrulify convert that tests each
group the generated build will run. You can also run it as genrulify check.
For the append at step 764, it stages the one-line bundle in a sandbox, runs the
recorded dd command there, and checks its exit status and the resulting
file against the recording. If the rule were missing the first version of the file,
dd could exit successfully after writing just the second line. Comparing
the file catches that mistake.
The comparison covers each result that another rule reads or that goes into the package output. For a regular file it checks the contents and mode. A scratch file that nobody uses can differ. When a group needs more inputs, the checker can retry with a larger set. If a needed result keeps changing, the build can take that result from the recording.
The file comparison in symbols
Let \(p\) be a path whose result is used. Write \(A(p)\) for the entry the group
produced in the sandbox and \(B(p)\) for the entry in the recording after the
group finished. The test is \(A(p) = B(p)\) for each such path. For the append,
\(p\) is /build/bundle and \(B(p)\) is the two-line file.
Why the checks add up
The proof assumes each group the graph will run has reproduced its used results with the inputs listed in its rule. Running the checker establishes that fact for this recording. To predict another run, we also assume that the same inputs on the same platform give the same results. Two clean replay passes provide evidence for that assumption. The generated rules check their results again at build time, so a command that later diverges fails.
Start with the directory entry from the recording. The first checked
dd produces the one-line bundle. That gives the second dd
exactly the input it had when its check passed, so it produces the two-line bundle.
The final copy carries those bytes to the output.
The same reasoning works for a larger graph. Start with the recorded entries and build each rule after its inputs. A copy preserves the file's bytes and applies the recorded metadata. Each replayed command now sees the inputs it passed its check with, so its readers also get the recorded entries. By induction, this holds all the way to the package output. Packing those entries gives the recorded Nix archive (NAR), byte for byte. Independent rules can run in either order.
Which commands can be skipped?
A mkdir can become a constant because its directory is fully described
by the recorded entry. An install that keeps the bytes of its input
can become a copy with a new path and mode. A command whose results never reach
the output can disappear. In each case the next reader still gets the same entry.
What a generated rule looks like
In GNU hello, the rule for hello.o names the rule that unpacked the
source and the rule that wrote the configuration header. Here is an excerpt from
its BUILD.bazel file in the explorer.
cc_object(
name = "s95823_gcc",
src = ":s1378_tar/build/hello-2.12.3/src/hello.c",
hdrs = [
…
":s4254_bash/build/hello-2.12.3/config.h",
…
],
out = "s95823_gcc/build/hello-2.12.3/src/hello.o",
…
)
The rule calls sandbox.sh, which puts the inputs back at the paths
GCC expects, runs the recorded command line and checks the resulting object.
What happens when a source changes?
For a live project, convert --source generates rules that read your
checkout and accept new output bytes. If an edit changes which headers GCC needs,
record the build again to update the graph.
Build and edit the C example.
The technical note gives the trace assumptions and relates file versions to the model in Build Systems à la Carte.