Incremental Correctness Under Source Mutation

An incremental build reads the state of the source tree, decides what is stale, and executes. Between the read and the last action there is a window measured in the duration of the build, and during that window nothing prevents the tree from changing. Editors save files, a version control operation rewrites many at once, a code generator writes into the tree, and a colleague on a shared filesystem edits a header. A build that assumes otherwise is correct only while its assumption holds, and the assumption is easier to break than the tools that depend on it usually admit.

Two reads of the same file

Consider the ordinary dependency discovery described in Discovered Dependencies and Depfile Header Tracking. A build reads the recorded dependency list for a source, decides the object is stale, and schedules a compile. The compile reads the source and every header the preprocessor reaches, at a moment strictly after the decision. If the source changed in between, the object is built from the new content while the graph’s edge set reflects the old one: in particular, a header newly added by the edit is missing from the recorded list, so future invocations will not know the object depends on it.

The result is a build that is internally coherent as a sequence of compilations and externally wrong as a description of the tree. Every artefact it produced can be traced to some version of some input, but not all to the same version. Linking them together asserts that the parts form a whole, and that assertion is false.

The same double-read appears wherever a decision precedes a read. A hash-based tool computes an action key from the digests of its inputs, then runs the action, which reads the files again. When the file changed in between, the result is stored under a key that does not describe its actual inputs, which means a cache entry that is wrong for everyone. That is a strictly worse outcome than a locally stale object, because the corruption is now shareable.

What the filesystem allows

Whether a reader can observe a partially written file depends on how the writer writes. A tool that opens a file, truncates it, and writes the new content in place exposes an interval during which a concurrent reader sees a prefix of the new content, or a mixture. POSIX constrains the ordering that a reader must observe, in that a read which can be shown to occur after a write must reflect that write, but it does not make a multi-byte write appear instantaneously, and a reader racing with a writer can see intermediate states.

The standard escape is to write a complete temporary file and rename it over the target. Renaming within a filesystem is atomic with respect to observers: a reader sees either the old file or the new one, never a mixture, because the directory entry is replaced rather than the content rewritten. Editors and generators that follow this discipline make single-file replacement safe; they do not make a multi-file update atomic, because there is no primitive that renames several paths in one indivisible step.

So the tree can be inconsistent at a coarser granularity even when every individual write is atomic. An edit that changes a header and the source that defines a matching macro produces, for a short interval, a tree in which the two disagree. A build reading both during that interval produces an object file compiled against a mismatch, and the failure surfaces as a compile error that does not reproduce, or worse, as code that compiles and behaves incorrectly.

Detection

Because prevention is only partially available, most tools detect. The mechanism is to record, for each input, an identity that can be re-checked after the action completes: the modification time and size in a timestamp-based system, the digest in a content-addressed one. Re-checking every input after every action costs one metadata call per input, which for a compile with a few hundred headers is a few hundred syscalls, which is negligible against the compilation and a real cost only for large graphs of trivial actions.

# Capture an input's identity before the action and compare it afterwards.
before=$(stat -c '%s %Y %n' src/unit.c)
cc -c src/unit.c -o unit.o
after=$(stat -c '%s %Y %n' src/unit.c)
[ "$before" = "$after" ] || echo "input moved while the action ran"

The detection threshold determines how much is caught. Re-checking after the action finds mutations that happened during it. It misses a mutation that landed after the decision but before the action started, unless the check also happens before. And it misses a mutation that landed and then reverted to identical content, though a content-based check treats that as harmless because the bytes the action saw are the bytes now on disk. This asymmetry is one of the practical arguments for digests over timestamps: a timestamp check reports a change that did not happen, and a content check does not.

The response to a detected mutation varies. A build can invalidate the affected outputs and re-run the actions, which converges if the tree has stopped changing and loops if it has not. It can fail the build with a message naming the file, which is honest but annoying on machines where an editor keeps saving. It can simply continue and record the inconsistency, deferring the problem. Systems that build from an immutable copy of the sources eliminate the question entirely, at the cost of copying or hard-linking the tree before the build begins.

Watching for changes rather than re-checking on demand is the other approach, using the kernel’s notification interface on Linux or the equivalent elsewhere. Event-based notification is efficient because it needs no polling, but it reports what the kernel observed, which may be a coalesced summary rather than every intermediate state, and it requires the watcher to exist before the change happens. A change that arrives between the snapshot of the graph and the registration of the watch is invisible to the watcher and visible to a re-check.

Getting staleness to stop propagating

There is a related correctness question that looks like mutation handling but is not. An action may run, produce an output, and be judged successful while the output’s content is identical to what was there before, meaning that the action re-ran and changed nothing. From the graph’s point of view the action happened, so its consumers are stale. From the content’s point of view nothing changed, so they are not.

Comparing output digests before and after the action as described in Content-Hash Caching and Early Cutoff answers this at the level of the whole output. A finer version compares modification times: if the action ran but the output’s timestamp is unchanged, propagation can stop. This is the behaviour behind some build tools’ explicit support for actions that update an output only when its content would differ, where the tool is trusted to say so and the build system uses the unchanged timestamp as evidence. Trusting an action to report itself is a reasonable trade, but a wrong report is a missed rebuild, so the option is opt-in per rule rather than universal.

The interaction with mutation is direct: an output whose timestamp is not updated because the content matched is indistinguishable, at the file level, from an output that the build never touched. Anything that reasons about the build’s progress from timestamps alone is now reasoning about a signal that has a second meaning. Recording the decision explicitly, rather than inferring it from the filesystem, is what keeps the two cases apart.

The snapshot approach

The cleanest resolution is to make the source tree immutable for the duration of the build. Copy or hard-link the tree into a location the build owns, compute the graph against that copy, and execute. Edits to the original tree then affect the next build rather than the current one, and the double-read problem disappears because the copy cannot change.

Copying a large tree is expensive; hard-linking it is cheap and still fails to isolate content, because a writer that modifies a file in place writes through both links. Hard-link snapshots work only when combined with the discipline that every write is a rename, which replaces the link rather than mutating the inode. Copying with reflinks, where the filesystem supports them, gives physical isolation at low cost, and it is the technique that makes snapshot-per-build affordable on modern filesystems.

The alternative to a physical snapshot is to evaluate the tree to a set of digests first, and build from a content-addressed copy of those. An edit after evaluation does not change what is being built, because the build was already defined in terms of digests that no longer correspond to the working tree. The consequence is that a build can be correct and simultaneously not describe the tree the developer is looking at, which is a trade of one confusion for another; a build that reports which input digests it used resolves it. The property that makes digests the right handle here is the same one that makes them the right handle everywhere else in a build system: identity by content does not change underneath a reader.