Build-System Fundamentals

What this module covers

What is a build system?

Targets, inputs, outputs, prerequisites, actions, and dependencies

Dependency graphs and directed acyclic graphs (DAGs) Topological ordering and parallel execution

Incremental builds and timestamp-based decisions Clean builds, dirty builds, and stale artifacts

Deterministic versus nondeterministic builds Declarative versus imperative build descriptions Build orchestration versus compilation Common failure modes and diagnosis

2.1 Core vocabulary

Target: a requested result or named task, such as app, test, or install.

Input: a source, configuration, dependency, or other file consumed by a task.

Output: a file or artifact produced by a task.

Prerequisite/dependency: something that must be available or updated before a target is built.

Recipe/action: the command or operation that creates the result.

Dependency graph: a graph describing which outputs depend on which inputs.

Incremental build: rebuild only the parts affected by changed inputs.

Clean build: build from a state without previously generated outputs.

Cache: stored results reused when a task's inputs and identity match.

Toolchain: compiler, linker, assembler, libraries, and related tools.

2.2 Dependency graph

If math.h changes, both main.o and math.o may need rebuilding. If only main.c changes, main.o and the final application may need rebuilding, while math.o can remain valid.

A build engine should schedule prerequisites before dependents. Independent targets can often run in parallel.

Scheduling the graph: topological order and parallel waves Output (CPython 3.13.1):

Everything in one wave can run in parallel; a wave starts only when every prerequisite has finished. make -j and Ninja perform this scheduling continuously rather than in strict waves, but the ordering constraint is the same.

Try it: dependency graph explorer

main.c -----> main.o ----\
                         +----> application
math.c -----> math.o ----/
math.h -----> math.o
math.h -----> main.o

from collections import defaultdict

# edges: prerequisite -> dependent (the graph above)
edges = [("main.c", "main.o"), ("math.c", "math.o"), ("math.h", "main.o"),
         ("math.h", "math.o"), ("main.o", "application"), ("math.o", "application")]

dependents = defaultdict(list)
indegree = defaultdict(int)
nodes = set()
for pre, dep in edges:
    dependents[pre].append(dep)
    indegree[dep] += 1
    nodes |= {pre, dep}

wave = sorted(n for n in nodes if indegree[n] == 0)
level = 0
while wave:
    print(f"wave {level}: {', '.join(wave)}")
    nxt = []
    for n in wave:
        for d in dependents[n]:
            indegree[d] -= 1
            if indegree[d] == 0:
                nxt.append(d)
    wave, level = sorted(nxt), level + 1

wave 0: main.c, math.c, math.h
wave 1: main.o, math.o
wave 2: application

2.3 Declarative versus imperative descriptions

An imperative script says what commands to run in a sequence:

A dependency-oriented description declares relationships and commands. A tool can then determine what is stale and what can run concurrently.

Declarative build descriptions are not automatically correct: missing dependencies can cause stale outputs or race conditions.

cc -c main.c -o main.o
cc -c math.c -o math.o
cc main.o math.o -o app

2.4 Incremental build correctness

A target is valid only if all inputs that can affect it are represented in the dependency model or task identity. Dependencies may include source files, headers, compiler flags, environment variables, toolchain versions, generated configuration, and external tools.

Common bug: a generated header changes, but the build graph does not know that an object file depends on it. The old object file remains and the result is incorrect.

The common bug, reproduced Below, the Makefile from Module 4 has been edited to omit math.h from both object rules — exactly the missing-dependency bug described above. A real run with GNU Make 4.4.1:

Terminal session (GNU Make 4.4.1, GCC 11.2, Ubuntu 22.04 on WSL2):

After the header changed, Make reported nothing to do and the program kept printing the old value. Only a clean build revealed the change — which is why “it works after make clean” is a symptom to investigate, not a fix.

$ grep -n '^main.o\|^math.o' Makefile
11:main.o: main.c
14:math.o: math.c
$ make -s && ./app
scale 10, result 50
$ sed -i 's/#define SCALE 10/#define SCALE 100/' math.h
$ make
make: Nothing to be done for 'all'.
$ ./app
scale 10, result 50
$ make clean -s && make -s && ./app
scale 100, result 500

2.5 Timestamp-based versus content-based decisions

Some tools use modification timestamps. Others can use hashes of input content, declared tools, and configuration. Timestamp-based approaches are efficient but can be confused by copied files, clock differences, or missing dependency declarations. Content-addressed approaches can be more robust but require accurate input modeling and cache infrastructure.

2.6 Determinism

A deterministic task produces the same output from the same declared inputs. Hidden inputs—current time, random values, machine-specific paths, network responses, locale, filesystem ordering, or unpinned tools—can make results differ.

Exercise

Draw a dependency graph for a program with main.c, sensor.c, sensor.h, a generated version.h, a static library, and unit tests. Mark which outputs should be invalidated when each input changes.

Quiz

? `math.h` changes and the build graph lists it as a prerequisite of `main.o` and `math.o`. What must be rebuilt?
- Only `math.o` :: `main.o` also includes `math.h`.
+ `main.o`, `math.o` and the final application :: Both objects depend on the header, and the application depends on both objects.
- Nothing, because `.h` files are not compiled :: Headers are compiled as part of every file that includes them.
- Everything in the repository :: Only dependents of the changed input need rebuilding.

? Why did the run with the incomplete Makefile print the old value?
+ Make did not know `main.o` depended on `math.h`, so it treated `main.o` as up to date. :: Missing edges produce stale outputs.
- Make caches program output. :: Make does not run your program.
- The compiler ignored the header. :: The compiler was never invoked.
- Timestamps were wrong. :: The timestamps were correct; the dependency was missing.

? Which are hidden inputs that make builds nondeterministic? (select all that apply)
+ The current time embedded with `__DATE__`/`__TIME__` :: Module 8 shows two builds one second apart differing.
+ Absolute build paths in debug information :: Module 8 shows two directories producing
…