The problem restated

A build is a graph of computations. To build app you must first build lib, which needs a.o and b.o, which need their sources. The catch that makes this hard: you often don't know a computation's dependencies until you start computing it. Reading a BUILD file tells you what a target depends on — but you only learn that by reading the file, which is itself a computation with its own dependencies. The dependency graph is not handed to you; it is discovered as you evaluate.

Build systems still expose loading, analysis, and execution as distinct concepts. Skyframe gives computations within those concepts a uniform protocol: loading a package, resolving a configuration, and executing an action can each be represented by a key whose function asks for other keys. This is an incremental-computation graph, not the target dependency graph or action graph with a new name.

Three types, and that's nearly all

Read src/main/java/com/google/devtools/build/skyframe/ and the whole framework hangs from three interfaces.

A SkyValue is the immutable result of a computation — a marker interface. There is no hashing here: the engine compares values with plain equals(), which is all it needs to cache them and to notice when one stops changing.

A SkyKey names a computation: a function name plus its arguments. PACKAGE:foo, FILE:bar.c, ACTION:link-app. Keys are interned so identity comparison is cheap.

A SkyFunction is the computation itself. Here is its entire contract, from SkyFunction.java:

SkyValue compute(SkyKey skyKey, Environment env)
    throws SkyFunctionException, InterruptedException;

You are handed your key and an Environment. You produce a value. To reach a dependency, you ask the environment for it by key: env.getValue(someKey). That's the surface. The depth is in what happens when the thing you asked for isn't ready yet.

The trick: return null, get restarted

Here is the mechanism, quoted from the source, because no paraphrase does it justice:

The implementation can request arbitrary values using Environment#getValue. If the values are not ready, the call will return null; in that case the implementation should just return null, in which case the missing dependencies will be computed and the compute method will be started again.

That re-invocation has a name in the codebase: a Skyframe restart. Your function ran partway, discovered it needed FILE:b.c, found it wasn't computed yet, returned null — and Skyframe went off, computed b.c (and anything it needed, recursively), and then called your function again from the beginning, this time with b.c sitting ready in the environment.

The first time you meet this, it reads like a performance disaster: you're re-running compute functions repeatedly, throwing away partial work. But look at what it buys.

Step through it yourself:

The function never has to declare its dependencies up front — it discovers them by demanding them, and the act of demanding is the act of recording the edge. Skyframe learns its computation graph as a side-effect of evaluation. Within a SkyFunction, there is no separate declaration of computation dependencies to keep in sync with the calls that use them: asking for a key both records the edge and requests its value. This is not a claim that Bazel's loading, analysis, and execution phases disappear; it is a claim about one dependency-tracking protocol used across them.

And the re-runs are cheaper than they look. A restart happens at most once per newly discovered batch of dependencies, not per dependency; well-written functions request what they can in parallel so the environment can compute a whole frontier at once before restarting. The partial work thrown away is usually the cheap part — the expensive part (building b.c) is done exactly once and cached. Usually is doing honest work in that sentence: for functions whose pre-restart work is genuinely expensive (loading a large package, resolving hundreds of dependencies), Bazel later added an escape hatch — SkyFunction.Environment#getState, which lets a function carry partial state across restarts. The restart is a beautiful default, not a free one.

There's a compact way to say all of that. Write $\text{env}_i$ for what the environment holds the $i$-th time your function runs. Each restart strictly grows it —

$$\text{env}_0 \,\subset\, \text{env}_1 \,\subset\, \cdots \,\subset\, \text{env}_k$$

— because a restart only ever fires after at least one newly demanded dependency has been computed and added. For a successful request with a finite dependency closure, the chain can't run forever; if those dependencies form a cycle, Skyframe reports the cycle instead of finding a value. The API does not make an arbitrary Java SkyFunction terminate. Under the finite, acyclic precondition, batched demands make its length $k$ track the depth of the function's dependency graph — how many rounds of "I need that first" — not the count of its edges: a handful of restarts against hundreds of dependencies. Evaluation stops at the first environment rich enough that compute returns a value instead of null — the least fixed point of demanding, reached from below.

Incrementality: dirty, or changed

The restart trick builds the graph. The second half of Skyframe is what makes a re-build fast: deciding which cached nodes are still good.

When something changes, Skyframe marks affected nodes — but it distinguishes two kinds of staleness, and the distinction is the whole game. In NodeEntry.java, a node can be made DIRTY or CHANGED. A changed node must be recomputed no matter what — its input changed directly. A dirty node only might need recomputing: one of its dependencies is dirty, so on re-evaluation Skyframe walks that node's recorded dependencies and checks whether any actually produced a different value.

This is the payoff of comparing values, not timestamps or change events. Bazel's glossary calls the mechanism change pruning, and the comparison is exactly what it sounds like — DirtyBuildingState.java documents it as:

Returns true if newValue.equals the value from the last time this node was built.

If a dependency was dirtied but recomputes to an equal value — you changed a comment, or touched a file's mtime without changing its bytes — the node that depends on it is marked clean without re-running. (Skyframe even keeps the old value object on a match, preferring =​== identity to a fresh-but-equal copy.) Staleness stops propagating the moment a value is unchanged. A one-character edit deep in a header does not blindly invalidate everything above it; it invalidates exactly as far up as the values actually differ.

The rule the engine applies fits on one line. Write $v(d)$ for the value a dependency had last build and $v'(d)$ for what it recomputes to; a dirty node $n$ re-runs only if

$$\exists\, d \in \text{deps}(n) : v'(d) \neq v(d)$$

— some recorded dependency's value actually moved. If every $v'(d) = v(d)$, the node is marked clean untouched. Staleness travels along value inequality, not along edges; the edge only says where to look.

Watch the two cases run on the same graph. Edit a.c is a real code change: every node above it re-runs and produces a changed value, all the way to app. Reformat BUILD re-runs only parse — which returns an equal value, so everything above it is marked clean without re-running.

This is the "cost proportional to the change" promise from the survey, made mechanical. The cost isn't proportional to what might have been affected (the transitive closure); it's proportional to what was — the nodes whose recorded inputs genuinely changed value. As sets, what re-runs sits inside what's reachable — $\text{recomputed} \subseteq \text{reach}(\Delta)$ — and usually far inside it: the reformat scenario above re-ran $1$ node of the $5$ the edit could reach.

Hermeticity is a property of the function

One more detail worth pulling out, because it's where the elegance becomes a contract. Each SkyFunctionName carries a hermeticity flag — createHermetic, createNonHermetic, createSemiHermetic in the source.

A hermetic function is a pure function of its declared dependencies — $v(n) = f\big(v(\text{deps}(n))\big)$ and nothing else — so if they're unchanged, its value cannot change, and Skyframe is free to skip it entirely. A non-hermetic one might change even with identical dependencies (it reads the wall clock, or the filesystem outside the graph — a hidden argument the equation doesn't show), so it can't be trusted to stay clean.

This is why hermeticity matters beyond reproducibility. It's not a virtue you bolt on for its own sake — it's the precondition that lets the engine not run your function. Every non-hermetic node is a node Skyframe must pessimistically reconsider. Purity is what makes the incremental graph trustworthy.

What Skyframe actually is

Step back and the shape is clean. Skyframe is a general demand-driven incremental computation engine that happens to be aimed at builds. Functions discover their dependencies by asking for them; the asking records the graph; change pruning lets staleness die the moment a value stops changing; purity lets whole subgraphs be skipped. The "restart" that looked like a bug is what unifies dependency discovery and computation in one protocol that cannot fall out of sync.

It generalizes well past Bazel — the same pattern (a computation that requests inputs and suspends when they're missing) is how reactive build systems, query engines like Rust's salsa, and incremental compilers all work. The PL literature had the idea before Bazel shipped it: Umut Acar's self-adjusting computation (2005), made demand-driven in Adapton (PLDI 2014) — Skyframe is that idea, engineered at monorepo scale. Once you've seen the restart trick, you start seeing it everywhere: it is what demand-driven incrementality looks like when you write it down honestly.

The next piece looks at the system that took this idea and collapsed Bazel's remaining phases into one graph — Buck2's DICE — and asks why Meta decided to rebuild rather than adopt.

Lessons

• Skyframe is a general demand-driven incremental computation engine: a function discovers its dependencies by asking for them, and the asking records the computation edge — so dependency discovery and use cannot fall out of sync. Bazel's larger build phases remain distinct.
• Returning null and being restarted looks wasteful but isn't: the expensive work is done once and cached; only cheap partial evaluation is re-run.
• Change pruning — comparing a recomputed value with equals() against the cached one — makes staleness stop the moment a value recomputes unchanged; a dirtied dependency that produces an equal value doesn't propagate.
• Hermeticity isn't decoration: a pure function of its inputs is one the engine can safely skip. Purity is what makes the incremental graph trustworthy.

Practice

References

1. “Bazel glossary: Skyframe.” Bazel. — · the Skyframe source
2. “Hermeticity in Bazel.” Bazel.
3. Hammer, Khoo, Hicks & Foster. “Adapton: Composable, Demand-Driven Incremental Computation.” PLDI, 2014. — the demand-driven lineage Skyframe belongs to; Umut Acar's Self-Adjusting Computation (CMU thesis, 2005) is its root
4. “salsa.” — the same demand-driven pattern as a general Rust framework
5. “Incremental computing.” — for the broader idea

Mangalapilly, Y. J. (2026, June). The Build That Restarts Itself. Saṃhitā Notes. https://yesudeep.com/blog/the-build-that-restarts-itself/

@online{mangalapilly2026the,
  author  = {Yesudeep Jose Mangalapilly},
  title   = {The Build That Restarts Itself},
  journal = {Sa\d{m}hit\=a Notes},
  year    = {2026},
  month   = {June},
  url     = {https://yesudeep.com/blog/the-build-that-restarts-itself/},
  urldate = {2026-07-12},
}

Yesudeep Jose Mangalapilly. “The Build That Restarts Itself.” Saṃhitā Notes, 2026. https://yesudeep.com/blog/the-build-that-restarts-itself/.

TY  - ELEC
AU  - Mangalapilly, Yesudeep Jose
TI  - The Build That Restarts Itself
T2  - Saṃhitā Notes
PY  - 2026
UR  - https://yesudeep.com/blog/the-build-that-restarts-itself/
Y2  - 2026-07-12
ER  -