Build Graphs: How Build Systems Know What to Rebuild

You change one file in a large repository and run the build.

The build system does not start over.

A few source files compile. Others are untouched. Some work happens simultaneously. A library may be recreated. An executable may be relinked. Hundreds or thousands of files that exist in the repository never participate at all.

That raises a deceptively simple engineering question:

What must be rebuilt?

A compiler cannot answer it by itself. A compiler knows how to transform source into some output. A linker knows how to combine compiled artifacts. A code generator knows how to turn one representation into another.

None of those tools inherently knows which of those operations became necessary because you changed one file somewhere else in the repository.

That is the build system's problem.

And beneath a surprising amount of modern build machinery is one of software engineering's oldest uses of a dependency graph.

The important idea is not simply that builds happen in a particular order. A useful build graph captures enough information to answer several related questions at once:

What has to exist before this target can be produced? Which previously produced artifacts might now be stale? Which work is independent enough to happen in parallel? And which supposedly valid outputs can no longer be trusted after an input changes?

Once those relationships are explicit, these stop being questions about remembering a sequence of commands.

They become graph problems.

1. The Problem: From Commands to Relationships

Consider a small compiled program. You could build it manually by running a series of commands:

generate configuration header
compile parser
compile renderer
compile main
link application

For a tiny program, remembering that sequence is not difficult.

The problem appears when the project changes.

Suppose only main.c changes. Generating the configuration again would be unnecessary. Recompiling the parser and renderer would also be unnecessary. Only main.o needs to be replaced before the application is relinked.

Now suppose the configuration file changes instead. The generated header must change first. Anything compiled against that header may need to be rebuilt. The final executable may then need to be relinked.

The correct sequence of operations therefore depends on both what depends on what and what changed.

Scale that from five files to fifty thousand and a handwritten sequence of build commands is no longer a useful model.

In Stuart Feldman's 1979 paper describing Make, the motivation was already recognizable: software projects are composed of pieces processed through different tools, changes can require a complex sequence of follow-up actions, and mistakes occur when developers fail to keep those pieces consistent. Make was designed to track relationships between those pieces and issue the commands needed to restore consistency after something changed.

The lasting abstraction was not a particular command syntax. It was the relationship.

Instead of saying only:

run command A
then command B
then command C

a build description can say:

B requires the output of A
C requires the output of B

The first describes one execution sequence. The second describes the constraints that any valid execution sequence must obey.

That difference is what turns a build script into a dependency model.

2. The Graph Model

For this article, we will use a deliberately simple convention:

A → B means A is a prerequisite of B.

If a generated header must exist before parser.o can be compiled, we draw:

generated/config.h → parser.o

If parser.o is then one of the inputs used to create the application:

generated/config.h → parser.o → app

Real build systems may model different kinds of entities and may draw dependency direction differently. Nodes can represent files, targets, actions, generated artifacts, packages, or other build-system concepts. Bazel, for example, distinguishes between declared target dependencies and other graph-oriented views of the work required by a build.

The exact representation varies. The engineering idea does not: a build graph describes constraints between things that must be available, up to date, or executed before other things can be considered valid.

Consider this small project:

config.yaml ──→ generated/config.h

parser.c ─────────────┐
                       ├──→ parser.o ──────┐
generated/config.h ────┘                   │
                                            │
renderer.c ────────────┐                   │
                        ├──→ renderer.o ────┼──→ app
generated/config.h ─────┘                   │
                                            │
main.c ─────────────────→ main.o ──────────┘

This graph tells us that generated/config.h cannot be produced until config.yaml is available, that both parser.o and renderer.o depend on that generated header, that main.o does not, and that app cannot be produced until all three object files are ready.

Notice what it does not say: whether parser.o must be compiled before renderer.o. There is no edge between them. That absence matters.

From Make to modern builds

The underlying idea survived because repositories became larger faster than the problem disappeared. Make associated targets with prerequisites and commands; modern systems add increasingly sophisticated mechanisms for discovering dependencies, detecting changed inputs, caching outputs, scheduling parallel work, and sometimes executing that work on other machines.

Ninja makes the graph model unusually explicit — its documentation describes build statements as defining the project's dependency graph, deliberately optimized to perform the minimum work necessary during incremental builds. Bazel similarly uses explicit dependency declarations to construct a project dependency graph, and its documentation goes one useful step further by distinguishing between actual dependencies and declared dependencies — a distinction that will become important later.

The tools changed substantially. The graph remained. And as execution became more sophisticated, the accuracy of that graph became more important, not less: a dependency declaration that once helped a developer avoid forgetting a compilation step can now influence whether an action runs, whether a previous result can be reused, whether several actions can execute simultaneously, and whether work can safely be dispatched somewhere else.

3. How to Traverse a Build Graph

Once the dependencies are represented, several build decisions reduce to different ways of traversing the same graph. The first is ordering.

Topological ordering: what can run next?

Imagine this simpler graph:

        generated/config.h
             ↙       ↘
        parser.o   renderer.o
             ↘       ↙
                 app

app has to come after both object files. Both object files have to come after the generated header. But the graph does not require parser.o to come before renderer.o, or vice versa. One valid execution order is generated/config.h, parser.o, renderer.o, app; another is generated/config.h, renderer.o, parser.o, app. Both satisfy the graph.

Conceptually, this is what a topological ordering gives us: an ordering of the nodes that never places a dependent before one of its prerequisites. The important word is not ordering. It is constraints — a dependency graph usually defines a partial order, not one mandatory sequence.

A real scheduler does not need to flatten the entire build into a single line and obediently execute it top to bottom. It can repeatedly identify work whose prerequisites are satisfied and schedule that work wherever capacity is available. That is how the same graph exposes parallelism.

Consider a pure chain:

A → B → C → D → E

Very little can overlap here. B waits for A, C waits for B, D waits for C. Now compare it with:

        A
      ↙ ↓ ↘
     B  C  D
      ↘ ↓ ↙
        E

Once A finishes, B, C, and D are independent according to the graph. They can potentially run at the same time; E waits for all three.

This is where the visual language from Reading the Graph connects directly to build behavior. A Chain is not merely a shape in a build graph — a long prerequisite chain can become a sequential constraint on the build's critical path. Branching structures, by contrast, may expose work that can proceed concurrently.

The graph is therefore answering more than what comes first? It is also answering what does not have to wait for something else? That negative information is one of the reasons accurate dependency models matter for performance: too few edges can make a build incorrect, too many edges can make it unnecessarily sequential.

Forward reachability: what did this change invalidate?

Ordering answers what must precede what. But our original question was what must be rebuilt? — a different traversal: start with a changed input and follow its edges forward.

If main.c changes, the affected region is small (main.c → main.o → app); there is no path to parser.o or renderer.o, so the graph gives us no reason to consider those outputs invalid. If parser.c changes instead, the reachable region is similarly localized.

But change config.yaml:

config.yaml
    ↓
generated/config.h
    ├──→ parser.o ──────┐
    │                    │
    └──→ renderer.o ─────┼──→ app
                          │
              main.o ─────┘

The changed input now reaches two compilation outputs and, through them, the final application. That is the essential graph operation behind change propagation in an incremental build: start from what changed and identify the dependent region reachable from it.

One qualification matters here. Reachability identifies the region whose validity may depend on the change — it does not mean every reachable node must blindly execute again. Modern build systems may compare timestamps, content digests, command lines, environment information, or cached results before deciding whether an action truly needs to rerun. So it's worth separating two ideas: the dependency graph identifies where a change can matter; the build system's invalidation and caching rules determine which work actually needs to execute. Related problems, not identical ones.

4. A Small Missing Edge With Large Consequences

Return to our original graph, and assume both parser.c and renderer.c actually include generated/config.h. Now accidentally omit one dependency from the build description — the edge generated/config.h → renderer.o.

The source code still has the dependency. The graph does not. The declared graph now looks like this:

config.yaml ──→ generated/config.h
                    │
                    ▼
                 parser.o ────┐
                               │
renderer.c ─────→ renderer.o ─┼──→ app
                               │
main.c ─────────→ main.o ──────┘

From the build system's perspective, changing config.yaml reaches generated/config.h, then parser.o, then app. There is no path to renderer.o — so why should it rebuild? According to the graph, it should not.

This is the point where incremental builds can become dangerous in a way that full rebuilds sometimes hide. Suppose yesterday's renderer.o was compiled using an old version of the generated configuration. Today, config.yaml changes. The header is regenerated. The parser is recompiled. The renderer is not. The application is linked using object files compiled against two different versions of what was logically the same configuration.

The build may finish successfully. The graph was traversed correctly. The result can still be wrong.

The same missing edge can cause a different failure during a clean or highly parallel build: if renderer.o needs the generated header but the scheduler does not know that, the renderer compilation may be considered ready before the header-generation action finishes — producing a failure, or a build whose success depends on stale files left behind by an earlier run.

This is why certain build failures seem almost superstitious:

• The build works after running it twice.
• It works on one developer's machine but not another.
• It works incrementally but fails from a clean checkout.
• It works with one job but fails under parallel execution.
• Deleting the output directory changes the result.

The scheduler may not be behaving nondeterministically at all. It may be making perfectly reasonable scheduling decisions from an incomplete dependency model. Missing and redundant dependency declarations remain a recognized source of correctness and efficiency problems in incremental builds, precisely because a build tool's correctness depends on knowing the relationships that actually constrain its work.

This also explains why modern build systems invest so much in dependency discovery. C and C++ headers are an obvious example: requiring developers to manually maintain every header dependency would be error-prone, so compilers and build tools cooperate to discover them — Ninja supports compiler-generated dependency information specifically so header relationships can become part of the build's dependency model. Some build systems go further, distinguishing explicit, implicit, order-only, or dynamically discovered relationships, because not every prerequisite means exactly the same thing. The purpose remains the same: make the graph resemble the real build closely enough that scheduling and invalidation decisions stay trustworthy.

5. What the Graph Cannot Prove

A correct build graph is powerful. It is not a proof that the build is correct — and that distinction is easy to lose, because the graph makes very strong statements about the model it contains. If the graph is acyclic, we can find a valid ordering. If two actions have no prerequisite relationship, the graph may permit them to run concurrently. If a changed node cannot reach a particular output, the graph tells us that output is unaffected — according to the represented dependencies. The qualification matters.

It cannot prove that every dependency was declared

Bazel's documentation makes a useful distinction between the graph of actual dependencies and the graph of declared dependencies. A target can depend on something in reality even when that relationship is missing from its build declaration — our missing generated/config.h → renderer.o edge is exactly that situation. The build system can reason perfectly over the declared graph and still reach the wrong engineering conclusion, because reality contains an edge the graph does not.

It cannot prove that every input is visible

Files in the repository are not the only possible build inputs. A build action might depend on a compiler version, an environment variable, a system library, a configuration file outside the workspace, the current working directory, a network resource, locale settings, or a tool found through PATH. If those influences aren't captured by the build's model and cache keys, the output can depend on state invisible to the graph. This is one reason hermeticity matters to modern build systems: a build becomes easier to cache, reproduce, and distribute when an action's relevant inputs are explicit and controlled rather than leaking in from the surrounding machine.

It cannot prove determinism

Even if every dependency is known and every action executes in the correct order, an action may produce different results from the same inputs — it might embed a timestamp, depend on nondeterministic iteration order, fetch something mutable from a remote service, or use randomness. Dependency correctness and deterministic execution are separate properties. This is also why saying a build graph by itself "makes software reproducible" goes too far — the graph is part of the foundation for reliable incremental execution, but reproducibility requires additional guarantees about inputs, environment, tools, and action behavior.

And it cannot prove that the software works

Finally, the most mundane limitation is also the most important. A build system can correctly determine every prerequisite, schedule every action in a valid order, avoid every unnecessary recompilation, reuse every valid cached artifact — and the resulting program can still contain a bug. The build graph answers questions about production relationships between artifacts and actions. It does not prove the semantics of the program those actions produce.

That boundary is not a weakness of dependency graphs. It is what makes their interpretation precise. A graph becomes useful when we know which question it is capable of answering.

The Graph Under the Build

Today's build infrastructure can look very different from the systems that first automated compilation. A large build may contain thousands of actions running across many machines; some actions may not execute at all because an equivalent output already exists in a cache; dependency information may be partly declared by developers and partly discovered by compilers or other tools.

But beneath that machinery is still the same structural problem: what depends on what? Once those relationships are explicit, the build system can reason about what must happen first, what changed inputs can affect, and what work is independent enough to proceed at the same time.

That is why dependency graphs became such a natural model for builds. They turn a growing pile of commands into a set of constraints. They turn "rebuild everything" into a reachability problem. They turn unused processor capacity into a scheduling opportunity. And they turn a surprisingly large class of mysterious build failures into a simpler diagnostic question:

Is the graph missing a relationship that exists in reality?

When the answer is yes, the build system is not necessarily making the wrong decision. It may be making the right decision from the wrong graph.

That is both the power and the limit of a dependency model.