Discovered Dependencies and Depfile Header Tracking

A build file can declare that an object file depends on a source file, because a human wrote both names. It cannot practically declare that the object also depends on the dozens of headers the source transitively includes: the list depends on conditional compilation, on include search paths, on the contents of files that are themselves generated, and on the compiler’s view of the file. The list is knowable only after preprocessing, so any accurate graph has to be amended after the compile has already happened.

Two passes in one invocation

The mechanism that resolves this is a compiler flag that makes the preprocessor emit a make-compatible rule rather than the preprocessed text. The dependency rule names the object file as a target and every header reached during preprocessing as prerequisites. The same invocation can still compile, writing the object and the dependency file side by side.

With GNU or Clang-style drivers there are two axes to the choice of flags. The -M family writes the rule and stops before compiling; adding a D to make -MD or -MMD writes the rule as a side effect of a normal compile. And the single-M forms list system headers in the rule while the double-M forms omit them, on the grounds that a change to a system header is a toolchain change rather than a source change. A further flag names the output file for the rule instead of sending it to standard output, and one more emits an empty phony target for every prerequisite, which matters later.

The result for one translation unit looks like this:

unit.o: unit.c config.h util.h internal/arena.h
config.h: util.h
internal/arena.h:

The first line is the real rule; the object depends on the source and on every header reached. The trailing empty rules exist so that a header deleted from disk does not become a target with prerequisites and no recipe, which would otherwise stop the build with an error about a missing rule rather than rebuilding the consumer. Emitting those empty rules is the effect of the flag mentioned above, and it converts a hard failure into a rebuild.

Attaching the discovered rule to the graph

The dependency file is not read until the next invocation, at which point the build tool includes it as if it were part of the build file. GNU Make provides both a hard include and a soft -include; the soft form ignores files that do not exist, which is what allows the first build in a new tree to proceed with no dependency information at all. Conventional usage collects the dependency file names from the object file names, includes them all with the soft form, and lets the rules they contain add edges to the graph that Build Graph Construction and Topological Ordering describes.

Ninja takes the same information but parses it itself, configured per rule: a rule can declare a dependency file whose path is given by a variable, and Ninja will read it after the edge runs and merge the discovered inputs into the graph. There is also a mode where the compiler’s dependency information is written to standard output and parsed from there rather than from a file, and a separate prefix convention for tools whose dependency output has a different shape. In all cases the merge happens after the edge completes, which means the discovered inputs influence subsequent invocations rather than the current one.

Ordering deserves attention. The dependency file is produced by the same command that produces the object, so the tool must not read a stale dependency file as though it described the current run. Two hazards follow: a failed compile that leaves the previous dependency file in place, and a compile that writes its object before writing the dependency file and is then interrupted. Implementations differ in whether they delete the dependency file before invoking the command, and in whether they treat an absent dependency file for an existing object as a miss. Treating it as a miss is the conservative choice, re-running the action even when nothing changed, and it is much cheaper than the alternative, which is trusting a dependency list that no longer matches the source.

Why the whole scheme is unsound without care

The discovered edges are only sound if they are complete. If a dependency file is missing, truncated, or describes a previous version of the source, the graph has fewer edges than reality, and the failure mode is an object file compiled against headers that have since changed, silently linked into the final binary. A timestamp comparison, as described in Timestamp-Based Incrementality and Its Failure Modes, cannot see it, because the object file is newer than every dependency the graph knows about. The build succeeds, the tests may pass, and the error surfaces later as behaviour that does not match the source tree. This is the most serious failure mode in the whole incremental-build story because everything downstream of it is wrong and nothing reports it.

Three concrete ways the list goes stale:

A header is added to a source file but the compile that would have recorded it is skipped, because a previously correct dependency list said the object was up to date. This cannot happen if the dependency data is maintained per source and updated on every compilation of that source. It can happen if the tool keys the dependency data on something coarser, such as a directory, and a change inside the directory does not trigger the compile that would refresh it.

A conditional include is resolved differently because a macro definition or a search path changed, so the set of headers reached differs from the recorded set. Dependency recording captures the resolution that happened, which is correct for that configuration and wrong for another. Build configurations that share a build directory are a standing invitation to this class of error; separate output directories per configuration exist largely to prevent it.

A header is reached through a computed path, an include that names a file whose name is assembled at preprocessing time. These are rare and are often resolved by the preprocessor before being recorded, but a tool that generates includes at runtime, or that reads a list of names from a generated file, can produce a graph the naive recording misses. The same difficulty appears with generated sources: the recorded dependency points at the generated header, and the graph then needs an edge from the generating action, which the dependency scan cannot infer. Build-file authors must declare that edge by hand, and it is one of the most commonly omitted edges in practice.

Scanning ahead of time instead

An alternative to recording is to predict. A pre-pass over every source file can extract the quoted-include directives and resolve them against the search paths, building the header graph without running the preprocessor. The advantage is that the graph is available before any compilation, so the first build is ordered correctly and the schedule can be computed in full. The cost is that a textual scan cannot evaluate conditional compilation, so it must either over-approximate, treating a header as a dependency where the preprocessor would not have included it, or under-approximate and miss conditional includes. Over-approximation is safe for correctness and produces needless rebuilds; under-approximation reintroduces the stale-object failure.

Which failure is worse depends on the cost of a rebuild relative to the cost of a wrong result, and that is why several build systems offer both: a fast text scan for the common case, with a compiler-recorded dependency file as the authority, and a check that the two agree. The compiler-recorded form is also the one that extends to languages with richer module systems, where the front end knows the dependency graph exactly and can emit it in a machine-readable form rather than as a make rule. The parsing burden in that direction is smaller, since the format is structured, but the graph is then only available from toolchains that support it.

The general lesson is that a build graph over languages whose dependencies are discovered rather than declared is always a two-phase structure: an approximate graph that is enough to start work, refined after each action runs by information only that action could produce. Keeping the two phases consistent is the whole difficulty, and inconsistencies show up as either missed rebuilds or as rebuilds that never stop.