Demand-Driven Build Graph¶

Build process — instantiates Demand-Triggered Deferred Evaluation

Models work as a dependency graph and, given a requested output, realizes only the subgraph that output depends on and whose inputs have changed.

A Demand-Driven Build Graph turns a body of work into an explicit dependency graph and drives it backwards from a request. You ask for one output; the system walks the graph to find exactly the transitive inputs that output depends on, and rebuilds only those whose own inputs have changed since last time — everything else is reused, and everything the request does not depend on is never touched. Its distinguishing element is the dependency map as the unit of laziness: the graph, not a single value, is what decides what gets realized, which lets demand and change-detection compose across a whole project. This is the coarse, artifact-producing member of the family — where a lazy evaluator threads demand through expressions, a build graph threads it through targets, and its correctness rests entirely on the graph being a truthful account of what actually depends on what.

Example¶

An engineer asks a build system to produce one service binary out of a monorepo containing thousands of targets. Rather than compile everything, the tool starts from that binary and walks its dependency edges: this binary needs these three libraries, which need those protobufs and that shared util. It rebuilds only targets in that closure whose inputs changed since the last build — say two files were edited — and pulls the rest from cache. A sibling service the request never mentioned is not built at all.

Two graph-level guarantees make this safe. Before building, the tool checks for a dependency cycle — target A needing B needing A — and refuses rather than looping forever. And when someone asks "why did this rebuild?", it can print the realization trace: the exact targets it decided to rebuild and the changed input that triggered each. Because a regenerated library that produces byte-identical output can stop the rebuild from propagating further (early cutoff), a whitespace-only change often rebuilds one target and halts.^[1]

How it works¶

Model work as a graph. Every target declares its inputs and its dependencies; the edges are the dependency map that drives everything.
Pull from the request. Realization starts at the requested output and visits only its transitive closure — unrequested targets are never considered.
Rebuild on change, reuse otherwise. For each visited target, compare current inputs against the last build; rebuild only on change, and stop propagation when an output is unchanged (early cutoff).
Guard and trace. Detect dependency cycles before running, and record what was rebuilt and why so the decision is inspectable.

Tuning parameters¶

Dependency granularity — file-level vs. target-level vs. function-level nodes. Finer nodes rebuild less per change but cost more to track and can miss coarse-grained effects.
Change-detection signal — timestamps vs. content hashes. Hashes enable early cutoff and are order-independent but cost a hash per input; timestamps are cheap but fragile across restores and clock skew.
Caching scope — local only vs. shared/remote artifact cache. A shared cache reuses others' builds but demands hermetic, reproducible targets to be safe.
Strictness of dependency declaration — enforced sandboxing vs. trusted hand-declared inputs. Enforcement catches undeclared inputs (the main correctness risk) at the cost of setup and speed.

When it helps, and when it misleads¶

The graph pays off on large, incremental workloads where any one request touches a small slice: monorepo builds, data pipelines, dependency-driven task runners. It makes a small change cost like a small change, and it turns "rebuild the world" into "rebuild the closure of what you asked for."

It misleads exactly when the graph lies. The central failure is an under-approximated dependency map: an undeclared input means the tool does not know to rebuild when that input changes, so it serves a stale artifact that looks freshly built — a "clean build fixes it" bug that erodes trust in every incremental result. Over-declaration is the milder opposite, rebuilding too much and forfeiting the speedup. And a graph with an undetected cycle either loops or wedges. The classic misuse is leaning on incremental builds while quietly tolerating undeclared inputs, so correctness silently depends on how often someone does a full rebuild. The discipline: make the dependency graph complete and enforced (sandboxing or hermetic inputs), prefer content hashes so change detection is exact, and keep the realization trace so any stale or surprising rebuild can be traced to a declared edge.

How it implements the components¶

deferred_dependency_map — the explicit graph of targets and their inputs; the map is the unit of laziness that decides what gets realized from a request.
cycle_and_nontermination_guard — cycle detection over the graph that refuses a circular dependency rather than looping or wedging.
demand_and_realization_trace — the inspectable record of which targets were rebuilt and which changed input triggered each.

It does NOT itself cache individual target results keyed on inputs (memoized_result_store — that build cache is an instance of Memoization) or decide a human go/no-go on a stage (need_predicate — that's the Conditional Workflow Gate); it computes the dependency closure to realize and tracks what actually ran.

Instantiates: Demand-Triggered Deferred Evaluation — the build graph realizes only the demanded, changed portion of a project's work.
Consumes: Memoization — the per-target build cache keyed on inputs, which the graph reuses when a target's inputs are unchanged.
Sibling mechanisms: Memoization · Conditional Workflow Gate · Just-in-Time Compilation · Predicate Pushdown · Demand Paging · On-Demand Report Generation

Notes¶

Correctness and speed pull against declaration effort here. The faster and more aggressive the incremental reuse, the more it depends on the dependency map being complete — every real input declared. Sandboxed or hermetic builds enforce that completeness by making undeclared inputs unavailable at build time, which is why serious build systems invest in enforcement rather than trusting hand-written dependency lists.

References¶

[1] Early cutoff is the optimization where a rebuilt target that produces output identical to before halts further rebuilding of things that depend on it — a formatting-only change need not cascade. It requires content-based change detection (hashes) rather than timestamps, and it is a hallmark of correct, minimal incremental build systems. ↩