Buildstypical

The Build Dependency Graph

A build is a directed acyclic graph of artifacts. A change to a node may or may not require rebuilding its dependents, and which one it is depends on *what* changed — a body or a signature.

The question

When I change one file, how does the build decide what else has to be rebuilt?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute

What the program is here

The program is a directed acyclic graph whose nodes are artifacts — source files, interface files, object files, archives, the final binary — and whose edges mean "was an input to". The graph exists to answer exactly one question: given a set of changed nodes, which other nodes can no longer be trusted? Everything else about a build system is machinery for computing that answer quickly and correctly.

What this phase may assume or do

Reusing a cached artifact preserves correctness only if every input that could have influenced it is unchanged, which requires the edge set to be *complete*. A missing edge licenses the build to reuse an artifact whose input did change; a spurious edge merely costs time. The asymmetry is the whole reason build systems err towards over-approximating dependencies: the failure modes of the two errors are not comparable.

Key points

A build is a DAG of artifacts; build order is a topological sort of it and the minimum build time is its critical path.
What a change invalidates depends on what changed: body changes usually stop at the interface, signature and layout changes propagate.
The interface node is where fan-out lives, so interface stability, not file count, decides how expensive an edit is.
Publishing inlinable bodies converts body changes into interface changes — the build-graph price of cross-module inlining.
A missing dependency edge produces a stale artifact and a build that does not match a clean one; a spurious edge only costs time, which is why over-approximating is the safe error.

A → B → C, and the question nobody asks precisely enough

Take three units where A depends on B and B depends on C. Change C. The naive answer is "rebuild C, then B, then A", and it is usually wrong — it is the *upper bound*, not the answer. What must actually be rebuilt depends on which part of C changed and on what B consumed.

If you changed the body of a function in C without touching its signature, C's interface artifact is byte-identical and B is unaffected. If you changed a signature, B must be recompiled — and then the same question is asked again at B: did B's interface change? Frequently it did not, and the cascade stops there. This is early cut-off applied to a graph, and it is why real rebuild sets are far smaller than the transitive closure suggests.

The exception that matters: if C's interface publishes an inlinable body, then a body change *is* an interface change, and B genuinely must be rebuilt. That is not a flaw in the analysis — it is the cost of cross-module inlining, made visible in the build graph. See [[interface-files]].

What a change to C actually invalidatestypical

Change to C	C rebuilt?	B rebuilt?	Why
Comment or formatting	Yes (or cut off by hashing)	No	The interface is identical, so B's inputs did not change
Function body, not published	Yes	No	B was compiled against a signature that still holds
Function body, published as inlinable	Yes	Yes	B may have inlined the old body; the interface really did change
Function signature	Yes	Yes	B's type-checking inputs changed and its calls may need different code
Layout of an exported struct	Yes	Yes, and so must anything that stores it by value	Offsets are baked into B's machine code
A private type C never exports	Yes	No	Nothing outside C can name it
A compiler flag	Yes	Yes	Flags are inputs to every node; a build that does not model this is unsound

Why it is a DAG, and what a cycle costs

The graph must be acyclic, because the build order comes from a topological sort of it — DSA owns the algorithm and the structure, as topological-sort and dag. A cycle means two artifacts each need the other to exist first, which has no schedule.

Languages differ on whether source-level cycles are allowed. Go forbids import cycles outright; Rust forbids cycles between crates but permits them between modules within a crate, because the crate is the unit; C and C++ permit them freely, and pay by needing forward declarations and by having header-inclusion cycles that only include guards make survivable. The pattern is consistent: whatever the compilation unit is, cycles *between* units are forbidden and cycles *inside* one are fine, because inside a unit the compiler sees everything at once.

The graph is also where parallelism comes from. Any two nodes with no path between them can be built simultaneously, so the minimum build time is the longest path through the graph — the critical path — no matter how many cores you own. A dependency chain ten deep cannot be built in less than ten sequential steps, which is why "add more cores" stops helping long before the graph is wide.

A small build graph, read as a schedule

c_srcc.rsentry
```
source
```
c_ifacec.rmeta
```
interface
```
The cut-off node: if this is unchanged, nothing above it is affected.
c_objc.o
```
object
```
b_srcb.rs
```
source
```
b_ifaceb.rmeta
```
interface
```
b_objb.o
```
object
```
a_obja.o
```
object
```
binapp
```
link
```

Edges

c_src→c_iface
c_src→c_obj
c_iface→b_ifacetype-check input
c_iface→b_objtype-check input
b_src→b_iface
b_src→b_obj
b_iface→a_objtype-check input
c_obj→bin
b_obj→bin
a_obj→bin

Read it asNotice that c.o has no edge to anything but the link. Object files are consumed by the linker and by nobody else, which is why a body-only change is cheap: it regenerates a leaf. The interface node is the one with the fan-out, and it is the node whose stability decides how much of the graph an edit disturbs.

The edges you did not declare

The graph is only as good as its edge set, and the edges that cause trouble are the implicit ones. A compiler flag is an input to every compile action. The compiler binary itself is an input. A generated header is an input that does not exist until another action has run. An environment variable read by a build script is an input that most build systems cannot see at all.

C-family builds get most of their edges from the compiler: -MMD makes the compiler write out the list of headers it actually opened, and the build system reads that back. This is reliable precisely because it is observed rather than declared — the compiler cannot forget a file it read. Systems that require the developer to declare includes by hand accumulate missing edges until someone notices that a clean build differs from an incremental one.

Declared edges are wrong when a human forgets one; observed edges are right by construction but need the tool to report them.
Flags, the compiler version and the target triple are inputs to every action and must be part of every cache key — see [[target-triples]].
Generated sources add ordering edges that do not exist in the source tree and are the usual cause of race-flaky parallel builds.
A missing edge is a stale artifact; a spurious edge is wasted time. Build systems deliberately prefer the second.
Hermetic builds are the discipline of making the edge set complete — see [[hermetic-compilation]].

How it works

The steps, in the order the compiler takes them.

Each build action declares its inputs and outputs, forming edges from input artifacts to output artifacts.
The compiler contributes observed edges — the header list from -MMD, the interfaces it read — which the build system folds into the graph.
A change to any artifact marks it dirty; dirtiness propagates along edges towards dependents.
For each dirty node the build re-runs its action, then compares the new output against the previous one.
If the output is unchanged, propagation stops there and dependents keep their cached artifacts — early cut-off on the graph.
Independent nodes are dispatched in parallel; the schedule is a topological order and the wall-clock floor is the critical path.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

A stale object file is linked because an undeclared header changed, and the program behaves as though a change you made never happened — the reliable symptom of a missing edge.
A parallel build fails intermittently and succeeds on retry, because a generated file was consumed before the action that produced it had finished.
A one-character edit rebuilds thousands of targets, because the changed file sits at the root of the graph and nothing cuts off.
Adding cores stops helping past four, because the graph is a deep chain rather than a wide fan and the critical path is the limit.
An incremental build and a clean build produce different binaries, which is the graph telling you its edge set is incomplete.

When it helps

Diagnosing why a rebuild is bigger than expected: find the changed node with the highest fan-out and look at whether its interface really needed to change.
Restructuring for build speed. Splitting a widely-depended-on file, or moving a volatile definition out of an interface, is a graph edit with a measurable effect.
Understanding why a build is not getting faster with more parallelism — the critical path is a property of the graph, not of the machine.

When it hurts

Small projects, where the whole graph fits in a few seconds of compilation and reasoning about it is not worth the time.
Codebases with pervasive generated code, where the graph is partly dynamic and the static reasoning above holds only after the generators have run.

What it costs

Every one of these is paid by something.

A fine-grained graph buys precise invalidation and pays with more nodes to track, more actions to schedule, and per-action overhead that can exceed the compile it protects.
Observed dependencies buy completeness and pay by requiring the tool to report what it read, plus a second pass to fold the report back into the graph — which means the first build of a node is always pessimistic.
Over-approximating dependencies buys safety against staleness and pays in unnecessary rebuilds, which is the trade every mainstream build system deliberately makes.
Flattening the graph to shorten the critical path buys parallelism and costs modularity: fewer layers means larger units and more coupling.

What else you could do

What a different compiler or language does instead, and when that is better.

No graph at all: rebuild everything every time. Always correct, and the only viable option when the build is small or the toolchain cannot report dependencies.
Timestamp-ordered rebuilding, as classic make does, which approximates the graph analysis with a cheap comparison and inherits both false negatives and false positives — see [[build-system-interface]].
Content-addressed action graphs, as in Bazel, Buck and Nix, where each node is keyed by a hash of its full input set so results can be shared between machines.
Moving the graph inside the compiler as a query graph, which gives much finer granularity at the cost of being machine-local and version-fragile — see [[incremental-compilation]].

See it for yourself

The flag, dump or tool that shows you this directly.

make -d prints why make decided to rebuild each target, one comparison at a time.
bazel query "deps(//app:bin)" and bazel aquery print the target graph and the concrete action graph, which are not the same graph.
ninja -t graph | dot -Tsvg renders the real build graph; ninja -t deps shows the dependency records the compiler reported.
cargo build --timings produces an HTML view of crate units, their durations and their overlap, which makes the critical path visible directly.
clang -MMD -MF out.d writes the header list for one unit — a single node's observed in-edges, in a readable file.

Plausible wrong readings

Stated the way a confident engineer states them.

"If A depends on B and B changes, A must be rebuilt." Only if B's *interface* changed. Most edits do not change it, which is why real rebuild sets are small.
"The build graph is the include graph." The include graph is one source of edges. Flags, the compiler binary, generated files and the target are edges too, and forgetting them is the standard cause of stale builds.
"More cores will fix the build." Not past the critical path. A deep chain of dependencies has a serial floor no amount of hardware removes.
"Declaring dependencies by hand is fine if you are careful." Every codebase that tried this has missing edges. The compiler already knows what it read; use that.

Misconceptions

The claim, and what is actually true.

The dependency graph is the file inclusion graph.

Inclusion supplies some edges. Flags, the compiler binary, generated sources, the target and the standard library version are all inputs, and each one is an edge into every action that used it.

Cycles are a code smell but the build can handle them.

The build cannot schedule a cycle at all. Languages either forbid cycles between units or make the unit large enough that the cycle is inside it.

A rebuild set is the transitive closure of the change.

That is the upper bound. Early cut-off at interface artifacts routinely reduces it by an order of magnitude.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

A build is a set of files that produce other files. Draw an arrow from each input to each output and you have the build graph. Change something, and the build follows the arrows to find what might be affected. It is a DAG, so there is always an order to build things in, and things that do not depend on each other can be built at the same time.

practical

Two habits pay off. First, when a small change causes a big rebuild, find the node with the fan-out — usually a header or a widely-imported module — and ask whether its public surface really needed to change. Second, when a build is mysteriously stale, suspect a missing edge before suspecting the compiler; make -d or ninja -t deps will show what the build believed the inputs were, and the answer is almost always a file nobody declared.

advanced

The subtle property is that the graph has two kinds of node with very different fan-out, and good build performance comes from separating them. Object files are leaves: consumed only by the link, so regenerating one is cheap no matter how central the code is. Interface artifacts are hubs: consumed by every dependent, so their stability governs everything. Any architectural change that moves volatility from a hub to a leaf — moving an implementation detail out of a header, marking a function NOINLINE so it stops being published, introducing a stable façade in front of a churning subsystem — buys build time in proportion to the fan-out it removed. This is the same reasoning as decoupling for design purposes, arriving at the same advice from a completely different direction.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

typicalMainstream build systems over-approximate dependencies deliberately, because a spurious rebuild costs time and a missing one costs correctness. Some hermetic systems go further and sandbox each action so an undeclared read fails immediately rather than silently succeeding; that changes the failure from stale output to a build error, which is a different and better trade.

implementationWhether a body change alters an interface artifact depends on the compiler's publication heuristics — GHC unfoldings, Go's inlining budget, rustc's handling of generics — and these change between releases. The same edit can cut off on one compiler version and cascade on the next.

targetThe target triple and ABI are inputs to every compile action. Two builds of identical source for different targets share no artifacts, and a cache key that omits the target will hand an AArch64 object to an x86-64 link, which fails loudly on some linkers and produces nonsense on others.

If you were asked this in an interview

A depends on B depends on C. You change C. What has to be rebuilt, and what does the answer depend on?
Why do build systems prefer to over-declare dependencies rather than under-declare them?
Your build stopped getting faster past eight cores. What would you look at?

Connections

DSAdag topological-sort dfs adjacency-list

Performancecritical-path

Domains that do not exist yet

DevOps / Production Engineering — CI pipelines, remote build execution and shared artifact caches
Once the graph is content-addressed, its nodes can be built on other machines and shared between developers, which turns a compiler question into an infrastructure one. Scheduling, cache trust and pipeline design belong there; we own only what the edges mean and when an artifact may be reused.