Header Dependency Discovery: Why the Compiler Records Includes, Not the Build Tool

A C source file depends on more than itself. Change a struct field in a header and every translation unit that includes it must be recompiled, and any build system that does not know the header list will happily reuse stale objects. The obvious fix is to scan the source for #include lines and record what they name. That fix is wrong in a way that produces silent miscompiles rather than errors, because the set of files a translation unit actually reads is decided by the preprocessor at expansion time, not by the text pattern at the top of the file.

The correct source of the dependency list is the compiler front end, which opened exactly those files and no others. All the major C and C++ front ends can emit that list as a side effect of an ordinary compilation, and the format they emit is designed to be included directly by a makefile. Understanding why the scan approach fails is the fastest route to understanding what the emitted file contains.

Four ways a text scan disagrees with the preprocessor

The first failure is conditional compilation. A file that reads

#ifdef USE_OPENSSL
#  include <openssl/ssl.h>
#else
#  include "tls_stub.h"
#endif

has one #include line of interest per branch, and which one is live depends on flags that the build system, not the source file, controls. A scanner must reimplement the conditional logic, including the macro environment, to decide. It will get the answer wrong whenever a macro is defined by another header, by a command-line definition, or by a generated configuration file.

The second failure is computed includes. The preprocessor accepts a macro in include position when the macro expands to a header name in either the quoted or the angle-bracket form. A table-driven design that includes one header per entry, generated by macro expansion, is invisible to a scanner: there is no filename in the text at all.

The third failure is that includes nest. A scanner that resolves the direct includes must then resolve theirs, recursively, with the same conditional logic at every level, and with the same include search path rules. Getting the search order right is itself subtle: quoted includes search the directory of the including file first, angle-bracket includes do not, and both then walk the configured directory list in order. A file with the same name in two directories resolves differently depending on which form was used and which file did the including.

The fourth failure is #include_next, which exists specifically to let a header in one directory chain to a same-named header later in the search path. Its meaning depends on the position of the including file within the search path, so a scanner would need to model the search path as a stateful sequence rather than a set.

Any of these can be handled by a sufficiently determined scanner. None of them are handled by the simple scanner people actually write, and the failure mode is not a build error: the stale object file is simply reused, and the resulting binary disagrees with the source in a way that shows up much later.

What the front end emits and why the format is a makefile

The front end, while preprocessing, records every file it opens. Given the right flag it writes that list to a file in make syntax: the object file as the target, and every source and header as a prerequisite.

hello.o: hello.c /usr/include/stdio.h /usr/include/x86_64-linux-gnu/bits/types.h \
         /usr/include/string.h

Three properties of that output matter more than its contents. It is a complete rule, so a makefile can include it verbatim and gain the dependency edges without any translation step. It is produced during the compilation that was going to happen anyway, so it costs one extra file write and no extra process. And it is written from the front end’s own record of opened files, so it agrees with reality by construction rather than by reimplementation. The front end that writes it is one process in the chain the driver started, as described in How a Compiler Driver Dispatches Work.

There is a family of flags rather than one, and the differences are worth knowing because choosing wrongly either omits system headers or pollutes the build with them. One form lists all headers including system ones; a second form omits system headers, which is usually what a project wants because system headers change only when the toolchain is upgraded. A third form writes the dependency information as a side file while still compiling normally, which is the form a real build wants: one invocation, object file plus dependency file. A fourth lets the dependency output path be specified explicitly, which is necessary when the object file is not written next to the source. And a fifth appends phony targets for each prerequisite, so that a deleted header produces a clear “no rule to make target” error instead of a confusing “no such file” from make’s own dependency graph.

# Compile and emit hello.d alongside hello.o, omitting system headers
cc -MMD -MF hello.d -c hello.c -o hello.o

The phony-target flag deserves a note. Without it, deleting a header that some object depended on leaves the makefile with a prerequisite that does not exist and no rule to build it. Make then stops with an error naming the header, because it has no way to make a prerequisite it cannot find. With it, the generated fragment lists each prerequisite as a target with no prerequisites and no recipe, which make treats as always up to date, so the recompile goes ahead and the failure comes from the compiler instead: a missing-header error that names the source line which included the deleted file.

Storing the fragments without corrupting the build

A dependency fragment is only valid for the exact translation unit and the exact command line that produced it. Change a macro definition and the set of opened headers changes, so a fragment from the previous configuration can list headers that are no longer read and omit headers that are. This is the reason build systems regenerate the fragment on every compilation rather than caching it: the fragment is a byproduct, not an artifact to be reused.

The classic make idiom uses an optional include, so that the first build of a tree does not fail for want of fragments that do not exist yet, and a second rule that produces the fragment. That idiom is workable but has a sharp edge: if the compilation fails before the front end writes the fragment, the old fragment survives and describes a dependency set that may no longer be right. Deleting the fragment before compiling, or writing it to a temporary path and renaming on success, closes that hole.

Two further edges matter at scale. Fragments grow with the transitive include closure, which for a C++ translation unit that pulls in the standard library can be hundreds of paths, so parsing them is not free, and the cost scales with the number of targets in the tree. And paths in the fragment are whatever the front end saw, which for a build that runs in a different directory than the one the fragment was generated in will be wrong. Build systems that relocate their working directory either generate fragments with relative paths or rewrite them, and a fragment with absolute paths baked in is a common cause of a build that works in one checkout and not another.

Where the dependency list ends and the rest of the graph begins

Header dependencies are one kind of edge. Generated sources are another: a .c file produced by a code generator has no static dependency on the generator’s input, and the build must express that edge by hand. Link-time dependencies are a third: the linker reads object files and libraries, and the object’s own list of undefined symbols is a dependency that no preprocessor can report.

The common mistake is to treat the header fragment as the whole graph. It is one layer, the layer that the compiler can observe from the inside. Builds that mix hand-written edges, generated edges, and compiler-emitted edges need all three in one graph before scheduling can be correct, and the scheduler’s job is to order that combined graph. A parallel build then has to respect the same edges while keeping cores busy, which is a scheduling problem rather than a discovery problem, covered in Scheduling a Parallel Build from a Dependency Graph.

There is also a cost that the fragment does not capture: a header that changes forces every dependent translation unit to recompile, and a header included by nearly everything forces nearly everything. Reducing that fan-out is a source-level design activity, not a toolchain one, but the dependency fragments are the measurement that identifies which header is expensive. Counting how many objects name a given path in their fragments is a cheap and honest proxy for the blast radius of an edit, and it is available for free from files the compiler was already writing.