genrulify

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.