Build Graph Construction and Topological Ordering

Every build system is, at bottom, a program that maintains a directed graph and walks it. The vertices are units of work (a compilation, a link, a code-generation step) or the files those units consume and produce. The edges are the reasons one unit must finish before another may start. Incrementality, sandboxing, caching, remote execution, and parallelism are all queries or transformations over that graph, so the graph’s shape and its ordering constraints determine what the rest of the system can promise.

Vertices as files, vertices as actions

Two representations dominate. In a file-based graph, vertices are paths and an edge from a.h to a.o means the second cannot be produced until the first exists. GNU Make uses this model: a rule such as app.o: app.c util.h is literally an edge declaration, and the manual’s language of “prerequisites” and “targets” is the language of graph construction. In an action-based graph, vertices are commands and edges connect a producing action to a consuming action, with files attached to the edges rather than to the vertices. Ninja’s build files are closer to the second model: each build statement names a rule, a list of inputs, and a list of outputs, and the executor works on those statements directly.

The distinction matters when more than one rule claims to produce the same path. A file-based tool must decide which rule owns the path; GNU Make warns that a target has been given a recipe twice and keeps one of them. An action-based tool can reject the situation outright, because the invariant it wants is one producing action per output path. That invariant is what makes a build graph a function from outputs to producers, and without it caching and parallelism both lose their footing: two producers for one path means the content recorded for that path depends on which action happened to run.

Not every edge carries the same meaning. GNU Make supports order-only prerequisites, written after a vertical bar, which express “this must exist first, but a newer version of it does not make the target stale”. Directory-creation prerequisites are the canonical use. Formally, the graph’s edges are split into two relations: a change relation that drives incrementality and a happens-before relation that drives scheduling. Conflating them produces builds that rebuild far too much, which is the usual cost of modelling a directory as a normal prerequisite.

Granularity is a further choice. A vertex may be a single object file, an entire library archive, or a whole package. Coarser vertices reduce graph size and tool overhead but make incrementality blunt, since a change anywhere inside a package invalidates everything the package feeds. Fine vertices increase the number of process spawns, and process spawn cost is often the dominant term for small actions.

Where the edges come from

The graph is not usually written by hand in full. It is produced by one of three mechanisms, and they differ in when they are usable.

Static declaration is the simplest: the build file states all edges before anything runs. This is what a Makefile or a Ninja file is, and it means the graph can be checked and ordered before the first compiler starts.

Generated declaration inserts a program in front of that. A meta-build system computes a richer model of targets, properties, configurations, and transitive dependencies, then emits a flat Makefile or Ninja file. The emitted file is the graph the executor sees; the generator’s model is the graph a human maintains. Errors in the generator surface as missing edges downstream, which is why two-level systems are hard to debug at the seam.

Discovery defers edges until execution. A C compiler cannot know which headers a translation unit includes until it preprocesses it, so the graph must be amended after the fact. The standard mechanism is a dependency file: the compiler is asked to emit the make-rule form of the include list alongside the object file, and the build tool reads those files at the start of the next invocation. This is covered in more detail in Discovered Dependencies and Depfile Header Tracking. Lazy evaluation is the other extreme: a graph may be materialised only as far as the requested outputs require, with unreferenced subgraphs never instantiated at all.

Cycle detection

A cycle in the dependency relation means no valid execution order exists, and every tool must detect it rather than loop. The classical method is depth-first search with three vertex colours: unvisited, on the current stack, and finished. Encountering an edge to an on-stack vertex is a back edge and proves a cycle. Kahn’s algorithm reaches the same conclusion without recursion.

def topo_order(nodes, deps):
    # deps[n] = list of nodes that must precede n
    indeg = {n: 0 for n in nodes}
    for n in nodes:
        for d in deps[n]:
            indeg[n] += 1          # count only edges into n
    ready = [n for n in nodes if indeg[n] == 0]
    order = []
    while ready:
        n = ready.pop()
        order.append(n)
        for m in nodes:
            if n in deps[m]:
                indeg[m] -= 1
                if indeg[m] == 0:
                    ready.append(m)
    if len(order) != len(nodes):
        raise ValueError("dependency cycle among " +
                         ", ".join(n for n in nodes if n not in order))
    return order

Both approaches run in time proportional to vertices plus edges, which for a graph of a hundred thousand edges is negligible against the cost of running a single compiler. Cycle detection is therefore essentially free, and a build system that hangs or loops forever on a cyclic graph has a reporting bug, not a performance problem.

The interesting part is the response. GNU Make breaks the offending edge, prints a warning naming the two files involved, and proceeds with the rest of the graph, so the build may still succeed in a partially wrong way. Tools that require a strictly acyclic graph reject the invocation. Neither behaviour is unreasonable; they optimise for different failure modes. Make’s choice keeps large legacy trees building after an accidental cycle, at the price of a possibly incomplete build. A hard failure is louder and easier to attribute.

Most cycles are modelling errors rather than genuine circular requirements. A rule whose output is listed among its own inputs creates a self-loop, usually because a code generator writes back into the directory it reads. Real circular requirements do occur, as when a parser generator’s generated parser is needed to rebuild the grammar or a compiler bootstraps itself, but the standard resolution is to split the graph into stages, with the previously generated artefact treated as a fixed input to the earlier stage.

Ordering is not scheduling

A topological sort yields a linear extension of a partial order, and unless the graph is a chain there are many valid extensions. The sort constrains the executor only in one respect: a vertex may not start until all its incoming edges are satisfied. Which of the currently ready vertices runs next is a separate decision, made by the scheduler.

That decision has a large effect on wall-clock time. Executors commonly prioritise by the length of the longest remaining path to a requested output, because the total build time cannot be less than that path’s duration; finishing it early exposes the next actions on it. Others prioritise depth-first traversal, which keeps a working set of recently touched files small and is friendlier to the page cache and to any content-addressed cache that is still warm. The parallel work available at any instant is bounded by the graph’s width, and a chain of dependent actions such as generate, compile, and link gives no parallelism at all no matter how many cores are offered. This is the subject of Scheduling Actions Across a Dependency Graph.

The graph is a claim, and claims can be wrong

Every edge in the graph is an assertion by the build author that the dependency exists. Missing edges make the graph acyclic and schedulable while the real system is not: two actions that both read and write a generated header may be declared independent, and the resulting failures appear only when scheduling changes, which is why they are intermittent. Extra edges are safe but slow, and each unnecessary edge adds a rebuild trigger under the timestamp and hash schemes described in Timestamp-Based Incrementality and Its Failure Modes.

Checking the claim mechanically requires running actions in an environment where undeclared inputs are unavailable, so that a missing edge becomes a hard error rather than a subtle race. The property being tested is hermeticity, discussed in Hermetic Actions and Undeclared Inputs, and it is the only reliable way to distinguish a graph that is correct from one that merely happens to work.