Build Systems

The previous topic measured whom a resource is left with on exit — who ends up holding a block once its owner is done with it. This lesson carries the same question from a source file to a compiled program: when a header file changes, does that change actually reach every target that depends on it? If it doesn’t, the target keeps carrying a copy of its old self, unaware of the newer version sitting in the hands of whoever wrote it.

A rule-based build system makes this decision with a single comparison: is the timestamp of every input a target depends on newer than the timestamp of the target’s own last production? If so, the target is rebuilt. For this rule to work correctly, the target’s dependency list has to be complete — an entry that isn’t in the list is never even asked about, no matter how much it has changed.

This decision doesn’t stop at a single target. A program is usually built from several targets, and those targets can depend on one another: a source file can depend on a header, and that header can depend on another header. A rule-based system follows this chain transitively — a single change at the bottom of the chain puts every target in between onto the rebuild list, one after another. If a target in the middle of the chain has an incomplete dependency list, everything after it inherits that same gap; the gap doesn’t stay confined to one target, it reaches the whole subtree hanging off it.

The Timestamp and Dependency Decision

The model below holds a build target’s state: the timestamp of when it was last produced, and the version number embedded in it at that moment. The decision is gathered into a single function.

// target.h — a build target's production timestamp and dependency check
#ifndef TARGET_H
#define TARGET_H

struct Target {
    int build_time;
    int built_version;
};

/* check_dependency compares a header's timestamp against the target's last
   build time. If the header's timestamp is newer than the target's, the
   target is rebuilt and built_version is updated to header_version. If this
   call never happens at all — that is, if the dependency was never written
   into the list — the target keeps its old state unchanged. */
void check_dependency(struct Target *t, int header_time, int header_version);

#endif

The rule lives in exactly one place; a rebuild happens whenever the header’s timestamp is newer than the target’s own.

// target.c — the decision comes from a single rule: is the dependency newer than the target
#include "target.h"

void check_dependency(struct Target *t, int header_time, int header_version) {
    if (header_time > t->build_time) {
        t->built_version = header_version;
        t->build_time = header_time;
    }
}

Now two targets with the same starting state are compared. For the written target, check_dependency is called with the header’s current timestamp and version — the dependency is present in the list, and the build system knows the header changed. For the unwritten target, this call never happens at all, as if the header never appeared in that target’s dependency list in the first place. The header itself advanced to version 2 in exactly the same way for both targets; the only difference is whether the build system knew about it.

// measurement.c — the written/unwritten decision and the three-link chain's decision in one run
#include <stdio.h>
#include "target.h"

int main(void) {
    struct Target written = { 10, 1 };     /* build_time=10, version=1 */
    struct Target unwritten = { 10, 1 };   /* same starting state */

    /* the header actually advanced to version 2, timestamp 20 */
    check_dependency(&written, 20, 2);
    /* this line is missing for unwritten -- the dependency never appears in its list */

    printf("written dependency built_version: %d\n", written.built_version);
    printf("unwritten dependency built_version: %d\n", unwritten.built_version);

    /* Three-link chain: base -> middle -> last. In the complete version, middle
       declares its dependency on base and updates its own record; last then
       inherits the updated record because it depends on middle. In the
       incomplete version, middle never declares its dependency on base, so
       even though last is properly linked to middle, there's no updated
       record for it to inherit. */
    struct Target mid_written = { 10, 1 };
    struct Target last_written = { 10, 1 };
    struct Target mid_unwritten = { 10, 1 };
    struct Target last_unwritten = { 10, 1 };

    check_dependency(&mid_written, 20, 2);
    check_dependency(&last_written, mid_written.build_time, mid_written.built_version);

    /* check_dependency is never called for mid_unwritten */
    check_dependency(&last_unwritten, mid_unwritten.build_time, mid_unwritten.built_version);

    printf("full chain last built_version: %d\n", last_written.built_version);
    printf("missing chain last built_version: %d\n", last_unwritten.built_version);
    return 0;
}

written dependency built_version: 2
unwritten dependency built_version: 1
full chain last built_version: 2
missing chain last built_version: 1

PI1. Timestamps are represented here as plain integer counters, not the calendar value a real filesystem would carry. The comparison’s outcome doesn’t change, because the rule only ever looks at ordering — which of the two integers is greater.

The written target saw the header’s new version, and its built_version field was updated to 2. The unwritten target stayed at 1: the header genuinely changed, but that relationship was never written into the build system’s dependency list, so the comparison was never even run. The unwritten.built_version field, entirely unaware of the new value the writing side left behind, keeps carrying a copy of the old version. This one comparison places the decisions of two different write patterns side by side: starting from the same initial state, from the same real change, and diverging into two different outcomes purely on whether that change was written into the dependency list.

PI2. The three-link chain is represented here with three separate struct Target variables; in a real build system this relationship is held in a dependency graph, and the chain’s length isn’t fixed. What the model measures — a missing link spreading its gap to the rest of the chain — doesn’t depend on the size of the graph.

mid_written and last_written carry the base’s update forward in two steps: mid_written declares that it depends on the base, and last_written declares that it depends on mid_written. mid_unwritten, on the other hand, never declares its dependency on the base, so its own record stays frozen at 1; even though last_unwritten‘s dependency on mid_unwritten is written completely, there’s no new record left for it to inherit — last_unwritten.build_time and mid_unwritten.build_time come out equal, so the comparison header_time > t->build_time never holds in the first place. This makes concrete why a single missing record in the middle of a chain affects not just its own target but the whole subtree hanging off it: even though the last link wrote its own dependency correctly, it has no way to compensate for the gap in the link before it.

In a real source tree the chain isn’t limited to three links, and it isn’t linear either: a middle target can have dozens of leaf targets depending on it, and all of them inherit the same gap at the same time. In the mid_unwritten example there was a single last_unwritten; in a real tree this means every target depending on mid_unwritten stays out of date — the effect of the gap doesn’t show up in one target, it shows up in every target attached to it at once. This spread makes finding a gap in the middle of a chain both more consequential and, in a way, easier: seeing several targets stay stale at the same time in the same pattern is a much more visible signature than a single target staying stale in isolation, and it usually points debugging straight at the common ancestor — mid_unwritten itself.

Some build systems derive this list from a generator instead of writing it by hand: it scans the source files itself, works out which header was included by which target, and produces the dependency list automatically (model). What a generator-based approach buys is a lower chance the list gets forgotten — the rule itself stays the same, only who writes the list changes.

The difference between the two approaches is that a hand-written list is static, while a generated list is re-derived before every build. A hand-written list stays incomplete if it isn’t updated when a source file gains a new header; a generator structurally rules this forgetting out, because it looks at the source itself on every run and rebuilds the list from scratch. The price is that the generator step itself now has to work correctly — if a generator skips a header, the result falls into the same class as a hand-written incomplete list, only the source of the gap is the generator rather than a person.

Broadly, a generator-based approach works like this: the compiler (or a separate tool that accompanies it) already sees which headers were actually included while it processes a source file — because the preprocessor stage opens every #include line anyway. Instead of discarding this information, it’s written to a separate record file: the source file’s name and the list of every header it’s transitively dependent on. This record file is read before the next build and folded into the build system’s dependency list. The result is a list derived from the source’s own real content rather than written by hand; when a source file gains a new header, the generator catches this change on its own at the next build and updates the record file. In a small source tree a hand-written list might not cause any trouble — a handful of files, a handful of headers, all visible at a glance. As the tree grows, the requirement that every new #include line also be added to the list by hand somewhere doesn’t scale: forgetting to add it becomes easier than writing the code itself, because updating the list doesn’t happen with the same attention, at the same moment, as changing the source file.

A generator-based approach carries its own cost: the record file is the output of the previous build, so on the very first build — before any record file exists yet — the build system has to start without a dependency list at all. This is why many rule-based systems run in two passes: first they read whatever record files already exist (if any) and build the dependency graph, then they order the actual build against that graph. If a record file is missing or corrupt, the system stays on the safe side and rebuilds that target anyway — it reads missing information as “unknown, so build it” rather than “unchanged.” This is the structural advantage a generator-based approach has over the risk of a hand-written list staying silently incomplete: when something goes wrong, the usual result is an unnecessary rebuild, not a silently skipped one.

The Bounding Measurement

This model only sees the dependency relationship the build system knows about, not whether the header’s content was actually read. As long as check_dependency isn’t called, the model produces the same result as if it assumed the header never changed at all — even though the header genuinely has changed. What’s being measured is the correctness of the dependency record, not the correctness of the source itself. This distinction matters because two different classes of failure shouldn’t be confused: the record itself can be broken (this lesson’s subject), or the record can be correct while the compiler’s use of that record is broken — for instance, a case that falls under the previous module’s staging question. Both produce the same symptom in the end — “the target behaves more out of date than expected” — but their roots are entirely separate, and so are their fixes: the first is fixed by adding the missing line to the dependency list, the second by re-examining the stage involved (preprocessor, compiler, or linker).

The previous module asked at which stage a change becomes visible: preprocessor, compiler, linker, or runtime. The question here sits on a different axis entirely — a unit whose header changed but that never got rebuilt is, from the staging question’s point of view, an ordinary preprocessor input; from the visibility question’s point of view, it is a copy, because the target never saw the change at all.

The independence of these two axes means clarifying which question is actually being asked when debugging a failure. A target behaving more out of date than expected can come from two different causes: either the source file never went through the right stage (the preprocessor didn’t expand a macro, the compiler reused a stale object file), or the source file went through the right stages but the build system never rebuilt it at all. This model only measures the second cause — which value reaches the target’s built_version field, not how that value gets processed afterward. A build system log is the most direct way to tell these two situations apart: which targets got rebuilt and which were left completely untouched is visible in the log, and an unexpectedly untouched target is a concrete symptom of the class this lesson measures.

The chain example shows both axes at once. last_unwritten staying at its old version traces back to a single missing record — mid_unwritten never declaring its dependency on the base — but where that gap becomes visible is at the end of the chain. Someone debugging last_unwritten first checks its own dependency list, finds it correct (last_unwritten correctly declares its dependency on mid_unwritten), and doesn’t look for the problem there; the real gap sits one link earlier. This shows why debugging a transitive chain doesn’t end at looking at one target — the problem is found by tracing backward through the chain itself, not from the visible end of it. In a large source tree this tracing can involve too many links to follow by hand, which is why a generator-based approach’s record files also double as a diagnostic tool — a way to confirm which target is really tied to which headers by looking at a file instead of relying on memory.

Summary

• A rule-based build system compares the timestamp of every input a target depends on against the target’s own production time.
• When the dependency list is incomplete, a change that isn’t in the list is never even asked about, and the target keeps its old output.
• The unwritten target’s built_version field is a copy of the value the writing side left stale, entirely independent of the header’s real version — the class this lesson measures is copy.
• A generator-based approach reduces the chance of forgetting by deriving the dependency list automatically; it doesn’t change the rule itself.
• The visibility question is an axis independent of the previous module’s staging question.
• A dependency chain is transitive: a missing record in the middle of the chain leaves the whole subtree hanging off it stale too — the fault should be looked for at the link holding the missing record, not at the visible end of the chain; because generator-based systems read missing information as “unknown” rather than “unchanged,” they stay on the safe side and rebuild, so the margin for error leans toward unnecessary rebuilding rather than silently skipping one.

In practice there are a few typical reasons a dependency ends up left out of the list. When a source file gets refactored and split into a new header, updating the old list is a separate step, and it can be skipped. When a file moves from one directory to another, the path in the list can keep pointing at the old location; the rule then either never matches anything or tracks the wrong file. A new target created by copy-pasting an existing one also copies its source’s dependency list, which may not reflect the new target’s actual dependencies — headers specific to the new target never make it into the list at all. All three cases arrive at the same outcome: the list carries a snapshot of a previous edit rather than the source’s real current state. What a generator-based approach closes is exactly this gap — the list never needing to be maintained by hand as a structure separate from the source at all.

Next Step

Even a correctly built target doesn’t turn into a program on its own — it usually gets linked with other units. That linking carries its own timestamp question: when a library is updated, when does the program linked against it see that update — right away, at the next rebuild, or never? The next lesson measures how two different ways of linking against a library decide which version the program sees once that library is updated; it’s the linking-stage counterpart of this lesson’s “was it written into the list or not” question.