commit e54596bdb09b87c46e0f184abaccc0a42e803bc8
parent 2fbb8b5957a5c3cd1b7ad6f178fec2e4c6fff6ae
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Thu, 18 Jun 2026 07:52:04 -0700
Promote build coordinator spec
Diffstat:
10 files changed, 819 insertions(+), 840 deletions(-)
diff --git a/doc/BUILD_COORDINATOR.md b/doc/BUILD_COORDINATOR.md
@@ -0,0 +1,780 @@
+# Content-addressed build coordinator
+
+This document specifies kit's user-facing, content-addressed build coordinator:
+the `<kit/build_coord.h>` public API, the `kit build` driver command, the
+configuration model, the on-disk storage state machine, the caching algorithm,
+the recipe protocol, and the trace-sharing model. The implementation lives in
+`src/build/`, is composed through `src/api/build_coord.c`, and is gated by
+`KIT_BUILD_ENABLED` / `KIT_TOOL_BUILD_ENABLED`.
+
+This is distinct from [BUILD.md](BUILD.md), which describes how kit itself is
+built (Makefile products, `KIT_*_ENABLED` component gating, and the staged
+self-build). The coordinator described here builds arbitrary projects by running
+declared recipes and caching their output trees by content.
+
+Historical implementation notes remain in
+[plan/BUILD_INTERNALS.md](plan/BUILD_INTERNALS.md) and
+[plan/BUILD_TESTING.md](plan/BUILD_TESTING.md); this document is the durable
+feature spec.
+
+## What it is
+
+A **build coordinator** is a long-lived process that turns a *build request*
+(target `T` under configuration `C`) into a materialized **output tree** on disk,
+doing the least work necessary. It does this by running **recipes** — opaque
+executables, typically shell scripts — that produce output directories, and by
+caching every recipe result keyed by the exact set of inputs that produced it. A
+second request whose inputs are unchanged returns the cached output without
+re-running anything; a request whose *direct dependencies'* outputs are unchanged
+(even if some deep source changed) can still skip its own recipe.
+
+The whole design rests on two properties:
+
+- **Content identity.** Every input and every output has a stable id: the
+ BLAKE2b-256 of its bytes (`kit_blob_info`, `kit_cas_*`). Sameness is hash
+ equality, never timestamps.
+- **Determinism.** A recipe is assumed to be a pure function of its *declared*
+ inputs: identical declared inputs ⇒ byte-identical output tree. Caching is only
+ as correct as this assumption (see [Determinism](#determinism-and-hermeticity)).
+
+It reuses the existing CAS for self-verifying content: source-file bytes, output
+trees, config snapshots, argv vectors, and deepset nodes. Trace bodies are
+content-addressed claims stored under `build/trace/`. The coordinator adds two
+things the content store does not have — a *mutable* per-target trace index and
+the resolution algorithm that drives it.
+
+## Concepts and vocabulary
+
+| Term | Meaning |
+|------|---------|
+| **Target** `T` | A named unit of work, e.g. `//app:server`. A build definition maps each target name to one recipe; the target's local argv comes from the build request (empty if none). |
+| **Recipe** | The executable the coordinator runs to produce a target's output. Identified by `recipe-id` = `BLAKE2b(recipe file bytes)`. |
+| **Configuration** | Tunables a recipe reads (target triple, opt level, feature flags). Two scopes — *propagated* (a key→value map, `config-id`) and *local* (the argv vector, `argv-id`) — see [below](#configuration-model). Both content-addressed: `config-id`/`argv-id` = `BLAKE2b(canonical bytes)`. |
+| **Output tree** | The directory a recipe produces, captured as a CAS tree (`tree-id`). The unit a build request returns. |
+| **Base inputs** | The *leaves* of the dependency graph, dynamically requested by recipes: **config values**, **source files**, and **globs**. |
+| **Target dep** | A dependency of one target on the *output tree* of another. The graph's interior edges, created by `need`. |
+| **Shallow trace** | A record of one build: its direct base inputs + its direct target deps (by output `tree-id`) → its output `tree-id`. |
+| **Deep trace** | A record of one build: `(root config-id, argv)` + a pointer to the transitive input closure (a **deepset**) → its output `tree-id`. |
+| **Deepset** | One node of the transitive input-closure DAG (`deep-set-id` = `BLAKE2b(canonical body)`): a target's recipe-id + its direct source/glob leaves + its children's `deep-set-id`s. A self-verifying CAS blob; shared structurally across ancestors. |
+| **Tree cache** | On-disk *materialized* output directories, keyed by `tree-id`, ready to hand back as a filesystem path. |
+
+The three base-input kinds are exactly the dynamically-requested leaves: a recipe
+asks the coordinator for a config value, the bytes of a source file, or the
+expansion of a glob, and each request is logged as a dependency so a later
+rebuild knows precisely what to re-check.
+
+## Build definitions
+
+A workspace is rooted by `KitBuildOptions.workspace_root` (`kit build --root`,
+default `.`) and has a build definition at `KitBuildOptions.build_def_path`
+(`kit build --def`, default `BUILD.kit`). The definition is strict canonical
+text:
+
+```
+kit-build 1
+[target //app:server]
+recipe recipes/app.sh
+[target //lib:core]
+recipe recipes/lib.sh
+```
+
+Target stanzas are sorted by target name and unique. Target names are non-empty
+tokens (no whitespace or newlines). Recipe paths are workspace-relative paths:
+absolute paths, `.` / `..` path elements, backslashes, and drive-prefix syntax
+are rejected. The definition supplies only the target-to-recipe mapping. It does
+not supply argv, default config, or dependency edges; those are request-time or
+dynamically discovered through the recipe protocol.
+
+The live definition is consulted when a target is resolved. The only
+definition-derived input recorded in traces is the resolved recipe's content id
+(`recipe-id`), not a hash of the whole definition file.
+
+## Configuration model
+
+Configuration has two scopes, distinguished by visibility:
+
+- **Propagated configuration** flows down the whole subtree. The top-level
+ request supplies it; a recipe reads a value with `config-get <key>` (logged as a
+ config dep); and a `need` may **overlay** it for the sub-build it triggers. A
+ target's *effective* propagated config = its inherited config with overlays
+ applied along the `need` path from the root. It is canonicalized to byte-stable
+ text and content-addressed: `config-id = BLAKE2b(canonical map)`, stored as a
+ CAS blob so any recorded `config-id` resolves back to the actual map.
+
+- **Local configuration** is the target's **argv**, supplied entirely by the
+ build request (both the top-level request and a `need` carry an optional argv);
+ when none is given it is the **empty** argv. The build definition carries no
+ argv. It is visible *only* to that one target's recipe (delivered as the
+ process's actual argv) and is **not** propagated to deps. Treating argv as
+ config keeps the model uniform: everything a recipe sees is configuration, some
+ inherited, some local. Local config is not part of `config-id`; it is serialized
+ to its own canonical CAS blob, `argv-id`, and — unlike propagated config —
+ `argv-id` *is* a first-class component of the resolution identity (below).
+
+**Serialized for replay, not just hashed.** Both the effective config map and the
+argv vector are persisted *by value* as canonical, content-addressed CAS blobs
+(`config-id`, `argv-id`) — never reduced to an opaque one-way hash. A trace
+references them by id, and they are part of its reachable closure (GC-rooted, and
+bundled with [shared traces](#shared-traces-trusted-as-signed-packages)). This is
+what lets the shallow path **replay every `need` request exactly** — reconstruct
+the dep's target name, its full effective config with overlays applied, and its
+argv — even when driving from an imported shallow trace with no access to the
+original build definition or workspace. Source files and globs are the opposite
+case: kept by hash only, because they are *verified* (did this still hash the
+same?), never replayed, and their bytes already live in the CAS.
+
+The **resolution identity** of a build is therefore the triple
+`(target-name, config-id, argv-id)`, where `config-id` is the effective
+*propagated* config and `argv-id` is the effective *local* argv (the request's
+argv, or the empty argv when none is supplied — the build definition carries no
+argv). The target name is just an identifier — argv is not encoded in it; it is
+supplied by the request and then content-addressed. Two requests that differ in the propagated
+config **or** the argv — `(T, C1, A)` and `(T, C2, A)`, or `(T, C, A1)` and
+`(T, C, A2)` — are genuinely distinct builds; any number may be in flight at once.
+
+`recipe-id` covers only the recipe *file bytes*. *Which* recipe a target maps to
+lives in the **build definition**, which the coordinator reads to resolve `T`.
+The only definition-derived input recorded for `T` is its **resolved recipe-id**
+(a per-node scalar), refreshed by recomputing it through the *live* definition —
+not a hash of the whole definition file. So repointing `T` to a different-content
+recipe busts it; repointing to a same-content recipe does not (it is the same
+build); and editing an *unrelated* target's stanza leaves `defn_find(T)`
+unchanged, so it does not bust `T`. The *mapping* is not an independent input —
+only the resolved recipe content is. (argv is *not* in the definition — it comes
+from the request, and a different argv is a different `argv-id`, hence a distinct
+build.)
+
+### Why two trace kinds
+
+The deep trace answers *"is this exact configuration unchanged and has any input
+moved?"* by refreshing the deepset closure — a DAG walk with structural sharing
+and an id-equality short-circuit, not a re-resolution. When it matches, the output
+is determined and we skip straight to materialization. It is the inner dev-loop
+fast path: edit code, rebuild under the same config.
+
+The shallow trace handles everything the deep path defers — a changed source that
+might not actually move a dep's output, and *any* configuration or argv change. It
+rebuilds the *direct* deps (cheaply, via their own traces, threading the new
+config and argv down through `need`), compares their resulting `tree-id`s against what it
+recorded, and if they match, the recipe is still skipped. This is the payoff of
+recording deps by *output* identity rather than by input identity: a subtree that
+ignores a changed config key, or absorbs a comment-only edit, produces the same
+output tree and short-circuits its parent's recipe.
+
+## On-disk storage
+
+The build store sits beside (or contains) a CAS. Everything content-addressed is
+immutable and self-verifying; exactly one class of object is mutable.
+
+```
+<store>/
+ cas/ # the shared content store, per DISTRIBUTE.md
+ blob/<pp>/<blob-id> # raw bytes: sources, config maps, argv vectors, deepset nodes
+ tree/<pp>/<tree-id> # canonical directory manifests (output trees)
+ ... # (chunk/, index/ as in DISTRIBUTE.md)
+ build/
+ trace/<pp>/<trace-id> # IMMUTABLE canonical trace bodies (deep + shallow) — CLAIMS
+ target/<pp>/<target-key> # MUTABLE per-target trace set (the only mutable state)
+ cache/<pp>/<tree-id>/ # tree cache: materialized output directories
+ tmp/ # staging for atomic writes + recipe sandboxes
+```
+
+`<pp>` is the first two lowercase hex chars of the relevant id (the DISTRIBUTE.md
+convention). `trace-id` = `BLAKE2b` of the canonical trace body.
+`target-key` = `BLAKE2b("kit build target v1" ‖ target-name)` — note it depends
+on the target *name only*, never on config, argv, or recipe-id, so a target's
+index entry is a stable handle holding candidate traces across every
+`(config, argv)` it was recently built under, while its inputs churn.
+
+The line that sorts `cas/` from `build/` is **self-verifiability, not
+content-addressedness**. Config maps, argv vectors, and **deepset closure nodes**
+(below) are self-verifying content — hand over the bytes and the recipient
+recomputes the id and transitively checks every reference — so they are ordinary
+CAS blobs (trustless, fetchable from an untrusted mirror, bundled as plain
+blobs). A **trace body**, though equally content-addressed, is a *claim*
+(`inputs ⇒ output`) that cannot be verified without re-running the recipe, so it
+lives in `build/trace/` and is shared only as a *signed* bundle. Only `target/`
+records and the `cache/` materializations are otherwise build-specific.
+
+### Trace bodies (immutable, content-addressed)
+
+Both kinds are strict, byte-stable, INI-style text in the family of
+`kit-tree 1` / `kit-package 3`: a version line, ordered scalar fields, then
+sorted sections. Unknown keys/sections, duplicate rows, and non-canonical
+ordering are parse errors (a parse error is treated as *absent*, never as a
+match — fail safe). All ids are lowercase hex. Config values, source bytes, and
+glob expansions are stored *by hash*, never inline, so a body's size is
+independent of its inputs' sizes.
+
+**Shallow trace** — direct inputs and direct deps, for fine-grained rechecking:
+
+```
+kit-build-shallow 1
+target //app:server
+recipe <recipe-id>
+output <output-tree-id>
+config <config-id> ; this target's effective propagated config (full map blob)
+argv <argv-id> ; this target's local config (serialized vector blob)
+[config] ; CONSUMED propagated key NAMES, sorted (values live in the map)
+opt
+[source] ; sorted by path ("<path> -" marks an absent read)
+src/main.c <blob-id>
+[glob] ; sorted by pattern
+src/*.c <glob-result-hash>
+[dep] ; sorted by (dep-name, dep-config-id, dep-argv-id) — each row replays one `need`
+//lib:core <dep-config-id> <dep-argv-id> <dep-output-tree-id>
+```
+
+The `recipe <recipe-id>` scalar is the only definition-derived input (recomputed
+through the live definition on refresh); the definition file itself is *not* a
+source leaf, so editing an unrelated target's stanza does not bust this trace.
+
+**Deep trace** — the `(root config-id, argv)` binding to an output, plus a single
+pointer to the transitive input closure (held as a **deepset** DAG, below), *no*
+`[dep]` and *no* per-key `[config]` section:
+
+```
+kit-build-deep 1
+target //app:server
+recipe <recipe-id>
+output <output-tree-id>
+root-config <config-id> ; this target's effective propagated config (full map blob)
+argv <argv-id> ; local config (serialized vector blob)
+deepset <deep-set-id> ; the transitive input closure, as a deepset DAG (a CAS blob)
+```
+
+**Deepset** — one node of the transitive input-closure DAG, a CAS blob. The deep
+trace inlines none of the closure; it points at the root deepset, and each node
+points at its children. A subtree reached through many parents is *one* node
+(structural sharing, like the CAS), so the closure is never re-listed per
+ancestor:
+
+```
+kit-build-deepset 1
+target //app:server ; carried so refresh can recompute this node's recipe-id
+recipe <recipe-id> ; the node's recipe content-hash (the only definition-derived input)
+[source] ; this node's DIRECT source leaves, sorted by path
+src/main.c <blob-id>
+config.h - ; an ABSENT leaf: "-" = the path was absent when read
+[glob] ; this node's DIRECT glob leaves, sorted by pattern
+src/*.c <glob-result-hash>
+[child] ; direct deps' deep-set-ids, sorted
+<deep-set-id of //lib:core's node>
+```
+
+`deep-set-id = BLAKE2b(canonical deepset body)`, which is exactly its CAS blob id.
+
+- `config <config-id>` and `argv <argv-id>` reference the **serialized** effective
+ config map and argv vector — canonical CAS blobs, kept by value and bundled with
+ shared traces — so the target's invocation and every `need` it issues replay
+ *exactly*, not merely check (see [Configuration model](#configuration-model)).
+- `[config]` lists the **names** of consumed propagated keys (consumed whether set
+ *or* unset); the values live in the `config-id` map this trace references. A key
+ *absent* from that map was consumed while unset, so later *adding* it busts the
+ trace — no sentinel value needed. Matching compares, for each consumed key, the
+ request's value against the built map's value (absent == unset).
+- `<blob-id>` = the source file's CAS blob id (`kit_blob_info`); source and glob
+ leaves are kept by hash because they are *verified*, never replayed. An absent
+ source is recorded as `<path> -` (a lone `-`), so *creating* the file later
+ busts the trace — the source analogue of a consumed-while-unset config key.
+- `recipe <recipe-id>` (on the shallow trace and on every deepset node) is the
+ target's **only** definition-derived input: `BLAKE2b` of the recipe *file*
+ bytes, refreshed by recomputing it through the *live* definition
+ (`defn_find(target) → recipe path → hash`). That catches a recipe edit *or* a
+ repoint to a different-content recipe at any depth, treats a repoint to a
+ same-content recipe as unchanged, and — because it goes through `defn_find` —
+ is unaffected by edits to *unrelated* stanzas. There is no whole-definition
+ source leaf.
+- `deepset <deep-set-id>` is the root of the closure DAG. Phase 1 loads it and
+ its children from the CAS to refresh; if any deepset blob is absent (e.g.
+ GC'd), the deep trace is treated as absent and resolution falls through
+ (fail-safe).
+- `<glob-result-hash>` = `BLAKE2b` of the canonical `(path, blob-id)` listing the
+ pattern matched (sorted by path). It changes if any matched file is added,
+ removed, or edited — so one glob row covers the existence *and* content of its
+ whole match set, and files read through a glob need no separate `[source]` rows.
+- `[dep]` rows carry the **dep's config-id and argv-id** (and output `tree-id`);
+ together with the dep's own serialized config/argv blobs this re-resolves each
+ dep under the exact propagated config *and* argv it used, overlays included.
+
+**Why the deep trace needs only `root-config` + the deepset closure.** If the
+request's `config-id` equals `root-config`, its `argv-id` equals the recorded
+`argv`, *and* refreshing the deepset finds nothing moved — every source/glob leaf
+still matches the live workspace **and** every node's `recipe-id` still recomputes
+the same through the live definition — then every recipe in the closure has
+byte-identical inputs *and* identical code, so every `need` overlay it computes is
+identical, every effective config downstream is identical, and by determinism the
+output is identical. Any input that could perturb a downstream overlay (a source a
+recipe branches on, a config value) is itself either a recorded source/glob leaf,
+a per-node `recipe-id`, or folded into `root-config`, so nothing escapes the
+check. Using the whole `root-config` (rather than just
+consumed keys) is a deliberate, conservative simplification: an *unconsumed*
+config change busts the deep fast path, but the [shallow path](#resolution-algorithm)
+recovers — it re-runs only the recipes whose output actually changed, so unrelated
+subtrees re-verify by hash without re-running.
+
+### Target record (mutable, the only mutable object)
+
+`build/target/<pp>/<target-key>` lists this target's candidate traces,
+newest-first, capped:
+
+```
+kit-build-record 1
+target //app:server
+deep <trace-id>
+deep <trace-id>
+shallow <trace-id>
+shallow <trace-id>
+```
+
+Each row points at a trace body in `build/trace/`. On every successful resolution
+the coordinator prepends the fresh trace, de-duplicates, and truncates each kind
+to a small cap (`KIT_BUILD_RECORD_CAP`, e.g. 8) — a bounded MRU window. Older
+traces age out and become GC-eligible. Multiple candidates exist because the same
+target may have been built under several distinct input, config, and argv
+combinations recently (e.g. two config values flipped back and forth, or two
+different argvs).
+
+### Storage state machine (atomicity and crash safety)
+
+The store must never hand back a wrong output after a crash. The rules:
+
+1. **Content objects** (`cas/blob`, `cas/tree`, `build/trace`, config maps, and a
+ materialized `build/cache/<tree-id>/`) are written into `build/tmp/`, fsync'd,
+ then **atomically renamed** to their final content-keyed path. A half-written
+ object only ever exists under `tmp/` and is orphaned, never under its content
+ key. Re-deriving the same content re-creates the identical path — writes are
+ idempotent, so a racing or retried producer is harmless.
+
+2. **The target record is the only ordering-sensitive state**, updated by
+ **read-modify-write into `tmp/` then atomic rename**. A reader always sees a
+ complete prior or complete next version, never a torn one. A crash loses *at
+ most* the most recent record update; losing a record entry is *safe* — the next
+ build re-derives and rewrites it. A corrupt record (failed `kit-build-record 1`
+ parse) is treated as empty.
+
+3. **Recipe sandboxes** live in `build/tmp/run-<n>/`. On success the output subdir
+ is ingested into the CAS (`kit_cas_add_tree_from_dir`) and the sandbox is
+ removed; on failure or crash it is orphaned and swept later.
+
+**Invariant.** Anything reachable under a content key (`blob/`, `tree/`,
+`trace/`) is complete and matches its key. A target record may *dangle* — point at
+a trace that GC removed — and readers tolerate that by treating the missing
+candidate as absent. The store degrades toward "rebuild," never toward "wrong
+answer."
+
+**Concurrency.** Two coordinators sharing a store are safe for content writes
+(idempotent atomic renames). Target-record updates are last-writer-wins; both
+writers wrote *valid* records, so the only loss is MRU ordering, costing at most a
+rebuild. An optional per-target-key advisory lock around the read-modify-write
+removes even that.
+
+## Build coordinator state and caching
+
+### In-memory state
+
+All state hangs off one `KitBuildCoordinator` context (no globals — the project
+rule). For the life of the process it memoizes every base-input probe and every
+target resolution, so a diamond in the graph is built once and a source file is
+hashed once:
+
+| Field | Contents | Notes |
+|-------|----------|-------|
+| `source_hashes` | `path → blob-id` (+ stat). | Per-process memo. |
+| `glob_results` | `pattern → (sorted paths, glob-result-hash)`. | Per-process memo. |
+| `config_maps` | `config-id → map`, and overlay results. | Immutable; content-addressed. |
+| `deepsets` | `deep-set-id → (interned node, refresh-valid?)`. | Shares subtrees; skips unchanged ones by id. |
+| `targets` | `(target-name, config-id, argv-id) → future` of `{output-tree-id, deepset node, path}`. | Memo **and** in-flight dedup. |
+| `cas` | Open `KitCas*` handle over `cas/`. | Plus optional remote (below). |
+| `store` | Paths + target-record reader/writer over `build/`. | — |
+| `jobs` | Semaphore bounding concurrent recipe processes. | The global parallelism limit. |
+
+"Cached over the life of the coordinator process" means exactly these memo
+tables: the coordinator assumes the workspace does not change *under it*
+mid-build.
+
+The `targets` table is keyed by the full `(target-name, config-id, argv-id)` and
+holds a **future**, not a flag — so concurrent `need`s of the same
+`(T, config-id, argv-id)` await one resolution rather than racing (see
+[Parallelism](#parallelism)). A resolved
+build yields the **output `tree-id`** (to satisfy a `need`), a materialized
+**path**, and its **deepset node** (the root of its transitive input-closure DAG,
+to fold into a parent's deepset).
+
+### Cycle detection
+
+The `targets` memo alone cannot catch a cycle — a self-dependent target would
+simply await its own unresolved future and deadlock. So each resolution carries an
+explicit **build chain**: the ordered list of `(target-name, config-id, argv-id)`
+frames from the root request down to here. A `need` whose
+`(dep, config-id, argv-id)` already appears on the chain is a dependency cycle;
+the chain *is* the error message (`//a → //b → //a`). The chain is per-path and
+distinct from the cross-path memo: the same `(T, config-id, argv-id)` may appear
+in many chains (a shared dep) but never twice in one.
+
+### Resolution algorithm
+
+A request is `resolve(T, cfg, argv, chain)` where `cfg` is the effective
+propagated config (with `cfg.id` its config-id) and `argv` is the effective local
+argv (with `argv.id` its argv-id — the request's argv, or empty when none is
+supplied). The config/argv-dependence is recorded in and verified against the
+traces; the *deep* path checks whole-config-id and argv-id equality, the *shallow*
+path checks consumed keys and argv-id.
+
+```
+resolve(T, cfg, argv, chain):
+ key = (T, cfg.id, argv.id)
+ if key in chain: error cycle(chain + key)
+ if key in targets: return await targets[key] # cross-path memo / in-flight dedup
+ targets[key] = new future ; chain' = chain + key
+
+ if record(T) is empty and trace_remotes configured: # clean checkout: try shared traces
+ pull_once(T) # verify+install signed bundle, then re-scan
+
+ # ---- Phase 1: deep fast path (same config+argv, did anything move?) ---
+ for D in deep_traces(T), newest-first:
+ if D.root_config == cfg.id and D.argv == argv.id:
+ node = deepset_load(D.deepset) # load DAG from CAS; absent => skip (fail-safe)
+ if node and refresh(node) all match live: # rehash/reglob + recompute recipe-id, memoized
+ p = materialize(D.output) # pure: cache -> CAS -> remote; ERR => fall through
+ if p ok: return done(D.output, p, node)
+
+ # ---- Phase 2: shallow path (config, argv, and/or sources moved) ------
+ for S in shallow_traces(T), newest-first:
+ if S.recipe != recipe_id(T): continue # recipe edit/repoint (live defn)
+ if S.argv != argv.id: continue # local config
+ M = config_by_id(S.config) # the built map (serialized blob)
+ if any consumed key in S.config-keys differs between cfg and M: continue
+ if any direct source/glob leaf of S changed: continue
+ ok = true ; child_nodes = []
+ for (dep, dep_cfg_id, dep_argv_id, recorded_tree) in S.deps: # may run in parallel
+ r = resolve(dep, config_by_id(dep_cfg_id), argv_by_id(dep_argv_id), chain') # replay the need by id
+ if r.output != recorded_tree: ok = false; break
+ child_nodes.push(r.leafset)
+ if ok:
+ node = union(direct{recipe_id, source/glob leaves} of S, child_nodes) # builds+stores the deepset
+ write_deep_trace(T, cfg.id, argv.id, node.id, S.output) # refresh the deep trace
+ p = materialize(S.output) # pure; ERR => fall through
+ if p ok: return done(S.output, p, node)
+
+ # ---- Phase 3: run the recipe ----------------------------------------
+ return run_recipe(T, cfg, argv, chain')
+```
+
+with the materialization ladder shared by every cache hit — a **pure locator**
+that never runs a recipe:
+
+```
+materialize(tree-id) -> path | MISS:
+ if tree-id in build/cache/ : return that path # already on disk
+ if tree-id in cas/ : restore into build/cache/, return path
+ if remote configured : fetch tree-id (+ blobs) into cas/, verify, restore
+ else : MISS # bytes gone everywhere
+```
+
+On `MISS` the caller does not return — it falls through to the next candidate
+and ultimately Phase 3, which rebuilds and records the correct output. Keeping
+`materialize` recipe-free is what lets a cache hit's recorded `tree-id` always
+describe the bytes it returns (no rebuild can silently substitute a different
+tree), and removes the resolve→runner edge.
+
+This is the brief's flow, sharpened by config:
+
+- *Phase 1* is the deep fast path: identical config-id **and argv-id** and an
+ all-clear deepset refresh — every source/glob leaf unchanged **and** every
+ node's `recipe-id` still recomputing the same — ⇒ reuse. `refresh` hits the
+ per-process memos and the deep-set-id validity cache, so a shared subtree is
+ checked once and an unchanged subtree is skipped by id equality.
+- *Phase 2* is the shallow path, taken when Phase 1 finds nothing (config or argv
+ changed, or a source moved). It guards on the target's own argv-id, consumed
+ config, and direct leaves, then re-resolves each recorded dep **under the dep's
+ recorded config-id and argv-id** and compares outputs. Re-using the recorded
+ `(dep_cfg_id, dep_argv_id)` is correct: if the parent's consumed config or argv
+ were different, the guards above would have failed first and the parent would
+ re-run, recomputing its `need` overlays.
+- A Phase-2 hit also writes a *fresh* deep trace from the now-known closure, so the
+ next request gets the Phase-1 fast path back.
+- *Phase 3* runs the recipe only when no trace holds, or when a hit's bytes were
+ evicted and no remote can supply them.
+
+The non-obvious win is **Phase 2 succeeding after an input changed.** A changed
+source busts the deep trace (Phase 1 gives up), but if that source only feeds a dep
+whose recipe maps it to an unchanged output (`tree-id` identical), the dep compare
+passes and `T`'s recipe is skipped. The deep trace is the cheap "nothing moved"
+check; the shallow trace is the "did the churn actually reach me?" check.
+
+### Running a recipe
+
+```
+run_recipe(T, cfg, argv, chain):
+ acquire jobs # global parallelism limit
+ sandbox = build/tmp/run-<n>/ ; out = sandbox/out/
+ spawn recipe (process argv = argv, the request's argv or empty when none given) with a
+ CLEAN env (host inherits nothing): { KIT_BUILD_SOCK, KIT_BUILD_OUT=out,
+ KIT_BUILD_TARGET=T, workspace root } + cfg's `env.*` keys as declared env vars
+ service the recipe's protocol requests, logging each as a dep (next section);
+ config-get reads cfg; source returns the live workspace path + pinned blob-id;
+ need releases this recipe's job slot, recurses resolve(...) under cfg ⊕ overrides
+ and the need's own effective argv, then reacquires the slot (so a chain deeper
+ than `jobs` cannot deadlock)
+ release jobs
+ on nonzero exit: propagate failure, write NO trace
+ on success:
+ output = kit_cas_add_tree_from_dir(out)
+ put serialized cfg map (cfg.id) and argv vector (argv.id) into the CAS
+ node = union(direct{recipe_id, source/glob/absent leaves}, child deepset nodes)
+ # builds + stores the root deepset as a CAS blob, yields its deep-set-id
+ write_shallow_trace(T, recipe_id, argv.id, cfg.id, consumed key names,
+ direct leaves, dep edges with their config-ids and argv-ids, output)
+ write_deep_trace (T, cfg.id, argv.id, node.id, output) # references the deepset
+ prepend both to T's target record (dedup, truncate to cap)
+ install out in build/cache/<output>/
+ return done({output, path}, node)
+```
+
+Writing *both* trace kinds on every real build is what lets a later request take
+whichever path fits the change it sees.
+
+### Parallelism
+
+The coordinator owns all parallelism: it is the single process that launches and
+manages every recipe, so the overall job limit is configured in it (the `jobs`
+semaphore). Parallelism comes from two places: **independent targets** (sibling
+deps, multi-target requests, Phase-2 dep re-resolution) and **a single recipe's
+fan-out** — a recipe issues `need-submit` for each dependency, the coordinator
+dispatches them onto workers concurrently, and the recipe `need-await`s the
+tokens. Both reduce to one primitive: a fresh `(T, config-id, argv-id)` is
+*dispatched* (driven on a worker thread), and the `targets` futures guarantee it
+is built once even when many parents request it at the same instant — a
+duplicate awaits the in-flight future rather than racing. The semaphore bounds
+*actively running* recipes, not in-flight ones: a recipe blocked in a `need`
+(or `need-await`) releases its slot and reacquires when the sub-build returns, so
+a chain deeper than `jobs` cannot deadlock. Cycle detection composes with
+concurrency through the per-path build chain (a parent-linked cactus stack, so
+each dispatched need extends a shared read-only prefix without copying): the
+global memo handles dedup, the chain handles cycles.
+
+## Recipe protocol
+
+Recipes communicate back over a **transport the driver defines** and the library
+abstracts behind a host vtable — the same "host supplies all side effects"
+principle the rest of kit follows. The library defines the *command set* and the
+length-prefixed request/response framing; the host supplies connect/read/write.
+
+```c
+typedef struct KitBuildTransport {
+ /* Server: create a uniquely-named endpoint for one recipe (its name, written
+ * into name_out, is passed to the child in $KIT_BUILD_SOCK); accept the
+ * recipe's one connection on it; tear the endpoint down when done. Per-recipe
+ * endpoints are what let many recipes run concurrently. */
+ int (*listen)(void* user, char* name_out, size_t cap, KitBuildListener** out);
+ int (*accept)(void* user, KitBuildListener* lst, KitBuildConn** out);
+ void (*close_listener)(void* user, KitBuildListener* lst);
+ /* Client: dial the endpoint named in $KIT_BUILD_SOCK; read/write length-
+ * prefixed frames; close. */
+ int (*dial)(void* user, KitSlice endpoint, KitBuildConn** out);
+ int (*read_frame)(void* user, KitBuildConn*, uint8_t* buf, size_t cap, size_t* n);
+ int (*write_frame)(void* user, KitBuildConn*, const uint8_t* buf, size_t n);
+ void (*close)(void* user, KitBuildConn*);
+ void* user;
+} KitBuildTransport;
+```
+
+Defaults and portability: a **unix-domain socket** (Linux, macOS, FreeBSD, and
+Windows 10+, which all support `AF_UNIX`) named in `$KIT_BUILD_SOCK`, or an
+**anonymous pipe pair** on inherited fds where a socket is undesirable; Windows
+may instead use a **named pipe**. An **in-process** transport (a direct callback
+table) serves recipes that are kit library calls rather than subprocesses. The
+command set is identical across all of them.
+
+Every request both **returns a value** and **logs a dependency**. The logged
+dependency is what lands in the shallow trace and (after expansion) the deep
+trace. The contract that makes caching correct: **an input the recipe reads but
+does not request is invisible to the cache** — so every input must flow through a
+command.
+
+| Command | Returns | Dependency logged |
+|---------|---------|-------------------|
+| `config-get <key>` | the propagated value (or *unset*) | config dep: key recorded as consumed; its value is the one in the effective `config-id` map (absent = unset) |
+| `source <path>` | `blob-id` (or *absent*) + a path to read | source dep: `(path, blob-id)`, or `(path, absent)` |
+| `glob <pattern>` | sorted list of matching paths (streamed) | glob dep: `(pattern, glob-result-hash)` |
+| `need <target> [k=v…] [argv…]` | the dep's output `tree-id` + a path (blocks) | target dep edge: `(dep, dep-config-id, dep-argv-id, output-tree-id)` |
+| `need-submit <target> [k=v…] [argv…]` | a **token** (does not block) | *(nothing yet — logged on await)* |
+| `need-await <token>` | the submitted dep's output `tree-id` + a path | target dep edge: `(dep, dep-config-id, dep-argv-id, output-tree-id)` |
+
+- **`config-get`** reads the target's *effective propagated* config and records the
+ value's hash, so changing a consumed key invalidates while changing an unconsumed
+ key does not. If a changed consumed key makes the recipe branch and request a
+ *new* key next time, the old trace already fails to match on the changed key, so
+ the new key-set is discovered on the rebuild — self-correcting, never needing to
+ predict the input set ahead of time. Local config (argv) is *not* read here; it
+ arrives as the process's argv. **Environment** is config too: keys under the
+ `env.` prefix (e.g. `env.PATH`) become the recipe's environment variables, so a
+ recipe's env is tracked, hermetic, and propagates like any config — the spawned
+ process otherwise gets a *clean* environment (nothing ambient inherited).
+- **`source`** hands back a path inside the **live workspace** (not a staged
+ copy) plus the blob-id the read is pinned to; an absent path is reported and
+ recorded as an *absent* leaf (creating it later busts the trace). Returning the
+ live path makes workspace immutability for the build's duration load-bearing
+ for soundness — see [Determinism](#determinism-and-hermeticity).
+- **`glob`** records the whole match set's content via `glob-result-hash`; the
+ recipe then reads the returned paths without further declaration. Matches are
+ **streamed** across as many frames as needed, so an arbitrarily large match set
+ is not bounded by a single frame.
+- **`need`** is the dynamic-dependency primitive. The optional `k=v` pairs
+ **overlay** propagated config for that sub-build; an optional argv vector sets
+ the dep's **local argv** (omitted ⇒ the empty argv; local argv never
+ propagates). The coordinator resolves `(dep, cfg ⊕ overrides, argv)`
+ recursively, returns its output `tree-id` and a readable path, and records the
+ edge with the dep's `config-id` and `argv-id` so the shallow path can re-resolve
+ identically. `need` is also where cycles are caught.
+- **`need-submit` / `need-await`** are the *future-based* form of `need`, for
+ building a recipe's deps **concurrently**. `need-submit` resolves nothing
+ inline — it dispatches `(dep, cfg ⊕ overrides, argv)` onto the coordinator's
+ workers and returns a **token** immediately (failing fast only on a cycle or
+ unknown target); the recipe submits its whole fan-out, then `need-await`s each
+ token to collect results. `need` is exactly `submit` + `await` fused into one
+ blocking round-trip (cheaper for the one-dep-at-a-time case, no worker
+ hand-off). Two rules keep the cache sound:
+ - **The dep edge is recorded on `await`, not `submit`.** A submitted-but-never-
+ awaited need is speculative (its output never reached the recipe), so it is
+ *not* a dependency; it is cancelled when the recipe exits.
+ - **`await` is always for a specific token** — there is deliberately no "await
+ whichever finishes first." Concurrency is a performance property only; the set
+ of needs a recipe awaits (hence its dependencies and output) must stay a
+ deterministic function of its inputs, never of completion order, or two runs
+ would record different dependencies. The recorded `[dep]` section is sorted,
+ so the trace is byte-identical regardless of submit/await order.
+- **Outputs** need no command: the recipe writes under `$KIT_BUILD_OUT` and the
+ coordinator snapshots that directory on exit.
+
+## Remote CAS and shared traces
+
+Two independent network capabilities, split along the DISTRIBUTE.md line —
+**content is trustless (hash-verified); claims are trusted (signed).**
+
+### Remote object fetch (trustless, via a fetch recipe)
+
+The coordinator performs no network I/O itself. When `materialize` (or a blob
+restore) needs an object that is absent locally and a remote is configured, it
+invokes a user-provided **fetch recipe** — an executable or command template, e.g.
+`curl -fsS -o "$KIT_FETCH_OUT" "https://cache.example/{kind}/{pp}/{id}"`, rendered
+with `{kind}` ∈ `blob`/`tree`, `{pp}`, `{id}` exactly like DISTRIBUTE.md's
+external-fetch templates. The fetched bytes land in `build/tmp/` and are
+**verified against the requested content id** before being installed into the
+local CAS; a corrupt or malicious mirror fails the hash check and is discarded. So
+the remote and the fetch recipe are *untrusted* — the existing self-verifying CAS
+makes that safe. This adds one rung to the materialization ladder (tree cache →
+local CAS → remote fetch) and lets a clean checkout *download* an output instead
+of rebuilding it. A **deepset** node needed during a deep refresh is fetched the
+same way — it is a CAS blob (`{kind}=blob`), so no separate kind is required.
+
+### Shared traces (trusted, as signed packages)
+
+A trace is a **claim**: "these inputs ⇒ this output tree." Unlike content, it is
+**not self-verifying** — confirming it means re-running the (assumed-deterministic)
+recipe, which is exactly the work we are trying to avoid. To safely import someone
+else's trace we must **trust the claimant**. Traces are therefore shared as
+**signed trace bundles**, reusing the DISTRIBUTE.md package + minisign + trust
+machinery wholesale:
+
+- A bundle is a signed manifest (`kit-build-traces 1`, signed exactly like a
+ `kit-package` manifest) listing `(target-name, kind, trace-id, output-tree-id)`
+ claims, carried in a `.kpkg` (portable tar.gz or native kpkg) alongside the
+ trace bodies and the CAS blobs they reference — the **serialized config-map and
+ argv blobs** (required, else an imported shallow trace cannot replay its
+ `need`s) and the **deepset closure blobs** a deep trace points at (required,
+ else an imported deep trace cannot refresh) — plus, optionally, the referenced
+ output trees/blobs.
+- Trust is the DISTRIBUTE.md model unchanged: verify the minisign signature
+ against the trusted-keys file (`-p KEY`, the anchor file, or `--tofu`); the
+ signed trusted comment binds the signature to the manifest hash.
+- Import: verify signature → anchor key → install the trace bodies into
+ `build/trace/` and prepend them to the relevant target records. Output bytes come
+ from the bundle or from the remote CAS — either way **hash-verified** on use.
+
+The result is a precise security split: a local build can now deep/shallow-**hit**
+on a remote builder's trace — obtaining the output *without running the recipe* —
+while trusting only the *signed claim*; the output bytes themselves remain
+trustless (verified by `tree-id`/`blob-id`). Trusting a trace signer is exactly
+like trusting a package signer in DISTRIBUTE.md: it is trust in their build
+outputs, gated by the trusted-keys allowlist, and auditable by re-running under
+[verify mode](#determinism-and-hermeticity).
+
+## Determinism and hermeticity
+
+Cache correctness is exactly the assumption *output = f(declared inputs)*,
+deterministically.
+
+- **Declared-inputs-are-complete.** Reading an undeclared file is a hermeticity
+ violation. The protocol makes declaration the only *intended* way to get an
+ input, but **enforcement is deferred** (see below): for now it is a contract
+ recipes must honor. The recipe runs with a **clean environment** (only the
+ KIT_BUILD_* vars and the build's declared `env.*` config), so ambient
+ PATH/locale/etc. cannot leak in as undeclared, untracked inputs.
+- **Workspace immutability is load-bearing.** `source` returns a live workspace
+ path, so the bytes a recipe reads are the bytes on disk *at read time*, not a
+ snapshot of what was hashed. If the workspace mutates mid-build the recorded
+ input hash and the bytes actually consumed can disagree, making a trace's claim
+ false — *unsound*, not merely stale. The coordinator therefore assumes the
+ workspace does not change for a build's duration; verify mode is the audit.
+- **Determinism.** Timestamps, RNG, and unpinned network fetches break the model —
+ a second build's captured tree differs from the recorded output, and the cache
+ would serve a stale-but-believed-current result. Mitigations: declare such
+ inputs (a "now" config value, a pinned URL+hash), or mark a target **no-cache**
+ so it always runs Phase 3.
+- **Verify mode.** A diagnostic mode re-runs a recipe whose trace says "unchanged"
+ and compares the fresh `tree-id` to the recorded one; a mismatch flags a
+ nondeterministic or under-declared recipe — the recommended audit before
+ trusting (or signing and sharing) traces.
+
+## Worked example
+
+`//app:server` depends on `//lib:core`; the recipe globs `src/*.c`, reads
+`src/main.c`, and consumes config `opt`. The request is under config `C0` (so
+`config-id = c0`). Neither request supplies argv, so every build's argv is empty
+(argv-id `a0`), held constant throughout; the full resolution key is the triple
+`(target, config-id, argv-id)`.
+
+1. **Cold build.** No record. Phase 3 runs both recipes. `//lib:core` builds →
+ `tree L0`. `//app:server` logs `config opt`, `glob src/*.c`, `source src/main.c`,
+ `need //lib:core` (under `c0` → `(//lib:core, c0, a0)`); yields `tree A0`.
+ Both trace kinds written for both targets. `build/cache/A0/` materialized, path
+ returned.
+2. **No-op rebuild (same `C0`).** Phase 1: `//app:server`'s deep trace has
+ `root-config c0` and `argv a0` (both match) and refreshes `opt` via config-id, `src/*.c`,
+ `src/main.c`, and the folded `lib/core.c` — all memoized, all match. `A0` is in
+ the tree cache. Returns instantly, nothing re-run, no graph walk.
+3. **Comment-only edit to `lib/core.c`.** `lib/core.c`'s blob-id moved → the deep
+ trace fails Phase 1 (a folded source leaf changed). Phase 2: direct leaves
+ (`opt`, `src/*.c`, `src/main.c`) unchanged, so probe the one dep —
+ `resolve(//lib:core, c0, a0)`. Its recipe re-runs (its source moved) but emits a
+ byte-identical `L0` (comment stripped). `L0 == L0` ⇒ `//app:server`'s recipe is
+ **skipped**, `A0` restored, a refreshed deep trace written so step 2's fast path
+ returns next time.
+4. **Flip `opt` (now `C1`, `config-id = c1`).** Phase 1 is skipped outright:
+ `//app:server`'s deep trace has `root-config c0 ≠ c1`. Phase 2 under `c1`:
+ `opt` is a consumed key whose value differs between `c1` and the trace's built
+ map → no shallow trace holds → Phase 3 re-runs `//app:server`. Its `need //lib:core` carries no `opt` override,
+ so the dep resolves as `(//lib:core, c1, a0)`; but `//lib:core` never
+ consumes `opt`, so its shallow trace under `c1` matches by argv-id (`a0`),
+ consumed-keys (empty), and direct leaves, and `L0` is reused without
+ re-running. Only the one recipe that actually depends on `opt` re-ran.
+
+## Limits and deferred work
+
+- **Hermeticity enforcement.** The protocol defines the contract, but the
+ coordinator does not yet deny or trace undeclared filesystem reads. Recipes
+ must request every cache-visible input through `config-get`, `source`, `glob`,
+ or `need`.
+- **Workspace snapshots.** `source` returns live workspace paths rather than a
+ staged immutable snapshot. The workspace must not change during one build.
+- **Scheduler breadth.** The public API has `KitBuildSched` and the resolver has
+ futures for in-flight target dedup. Hosts without a scheduler run sequentially;
+ the current `kit build` hosted path uses that sequential mode.
+- **No-cache policy.** The model describes when a target should always run, but
+ the current build definition format has no target-level no-cache flag.
+- **GC.** Build-store garbage collection is not implemented. The intended sweep
+ roots at live target records, follows trace bodies to referenced output
+ trees/blobs, config maps, argv vectors, and deepset closure blobs, then removes
+ unreachable `build/trace/`, `cas/`, and `build/cache/` entries.
diff --git a/doc/DESIGN.md b/doc/DESIGN.md
@@ -221,6 +221,7 @@ unless an API states otherwise.
| [CBACKEND.md](CBACKEND.md) | The portable C-source backend (`src/arch/c_target/`). |
| [WASM.md](WASM.md) | The WebAssembly backend, object form, and host-import binding. |
| [DISTRIBUTE.md](DISTRIBUTE.md) | Signed `.kpkg` packaging and the content-addressed store (`src/dist/`, `<kit/cas.h>` / `<kit/package.h>`, `cas`/`pkg` tools). |
+| [BUILD_COORDINATOR.md](BUILD_COORDINATOR.md) | The content-addressed build coordinator: `<kit/build_coord.h>`, `kit build`, trace/deepset caching, recipe protocol, and shared traces. |
| [RELEASE.md](RELEASE.md) | Releasing and updating kit itself: `VERSION`/`kit --version`, `make dist` + `scripts/release.sh` signed artifacts, the `kit-release` channel index, and `kit update`. |
| [DRIVER.md](DRIVER.md) | The multi-call binary, tool registry, and command-line policy. |
| [RUNTIME.md](RUNTIME.md) | The freestanding headers and compiler-rt/libc-style support in `rt/`. |
diff --git a/doc/plan/BUILD.md b/doc/plan/BUILD.md
@@ -1,796 +0,0 @@
-# Content-addressed build coordinator
-
-> **Status: design, not yet built.** This is a forward-looking roadmap for a new
-> subsystem layered on the content store in [../DISTRIBUTE.md](../DISTRIBUTE.md)
-> (`<kit/cas.h>`). It specifies the configuration model, the on-disk storage
-> state machine, the coordinator's in-memory state and caching algorithm, the
-> command protocol recipes use to talk back, and how builds share work over a
-> network (remote CAS + signed traces).
->
-> **Naming, to avoid confusion:** this is *not* [../BUILD.md](../BUILD.md), which
-> documents how kit itself is built (the Makefile, `KIT_*_ENABLED` component
-> gating, and the 3-stage bootstrap). This doc designs a *user-facing*,
-> Bazel/Nix-style incremental build engine that compiles arbitrary projects by
-> running recipes and caching their outputs by content. The two are unrelated
-> beyond sharing the word "build."
->
-> **Implementation breakdown:** [BUILD_INTERNALS.md](BUILD_INTERNALS.md) carves
-> this design into the `src/build/` modules — their responsibilities, dependency
-> graph, and pseudocode sketches — for parallel implementation.
-> **Testing strategy:** [BUILD_TESTING.md](BUILD_TESTING.md) specifies the
-> harness, per-module plan, integration scenarios, and cross-cutting property
-> tests (byte-stability, fail-safe parsing, minimal-rebuild, crash-safety).
-
-## What it is
-
-A **build coordinator** is a long-lived process that turns a *build request*
-(target `T` under configuration `C`) into a materialized **output tree** on disk,
-doing the least work necessary. It does this by running **recipes** — opaque
-executables, typically shell scripts — that produce output directories, and by
-caching every recipe result keyed by the exact set of inputs that produced it. A
-second request whose inputs are unchanged returns the cached output without
-re-running anything; a request whose *direct dependencies'* outputs are unchanged
-(even if some deep source changed) can still skip its own recipe.
-
-The whole design rests on two properties:
-
-- **Content identity.** Every input and every output has a stable id: the
- BLAKE2b-256 of its bytes (`kit_blob_info`, `kit_cas_*`). Sameness is hash
- equality, never timestamps.
-- **Determinism.** A recipe is assumed to be a pure function of its *declared*
- inputs: identical declared inputs ⇒ byte-identical output tree. Caching is only
- as correct as this assumption (see [Determinism](#determinism-and-hermeticity)).
-
-It reuses the existing CAS wholesale: source-file bytes, output directories,
-config snapshots, and trace bodies are all CAS blobs and trees. The coordinator
-adds two things the content store does not have — a *mutable* per-target trace
-index, and the resolution algorithm that drives it.
-
-## Concepts and vocabulary
-
-| Term | Meaning |
-|------|---------|
-| **Target** `T` | A named unit of work, e.g. `//app:server`. A build definition maps each target name to one recipe; the target's local argv comes from the build request (empty if none). |
-| **Recipe** | The executable the coordinator runs to produce a target's output. Identified by `recipe-id` = `BLAKE2b(recipe file bytes)`. |
-| **Configuration** | Tunables a recipe reads (target triple, opt level, feature flags). Two scopes — *propagated* (a key→value map, `config-id`) and *local* (the argv vector, `argv-id`) — see [below](#configuration-model). Both content-addressed: `config-id`/`argv-id` = `BLAKE2b(canonical bytes)`. |
-| **Output tree** | The directory a recipe produces, captured as a CAS tree (`tree-id`). The unit a build request returns. |
-| **Base inputs** | The *leaves* of the dependency graph, dynamically requested by recipes: **config values**, **source files**, and **globs**. |
-| **Target dep** | A dependency of one target on the *output tree* of another. The graph's interior edges, created by `need`. |
-| **Shallow trace** | A record of one build: its direct base inputs + its direct target deps (by output `tree-id`) → its output `tree-id`. |
-| **Deep trace** | A record of one build: `(root config-id, argv)` + a pointer to the transitive input closure (a **deepset**) → its output `tree-id`. |
-| **Deepset** | One node of the transitive input-closure DAG (`deep-set-id` = `BLAKE2b(canonical body)`): a target's recipe-id + its direct source/glob leaves + its children's `deep-set-id`s. A self-verifying CAS blob; shared structurally across ancestors. |
-| **Tree cache** | On-disk *materialized* output directories, keyed by `tree-id`, ready to hand back as a filesystem path. |
-
-The three base-input kinds are exactly the dynamically-requested leaves: a recipe
-asks the coordinator for a config value, the bytes of a source file, or the
-expansion of a glob, and each request is logged as a dependency so a later
-rebuild knows precisely what to re-check.
-
-## Configuration model
-
-Configuration has two scopes, distinguished by visibility:
-
-- **Propagated configuration** flows down the whole subtree. The top-level
- request supplies it; a recipe reads a value with `config-get <key>` (logged as a
- config dep); and a `need` may **overlay** it for the sub-build it triggers. A
- target's *effective* propagated config = its inherited config with overlays
- applied along the `need` path from the root. It is canonicalized to byte-stable
- text and content-addressed: `config-id = BLAKE2b(canonical map)`, stored as a
- CAS blob so any recorded `config-id` resolves back to the actual map.
-
-- **Local configuration** is the target's **argv**, supplied entirely by the
- build request (both the top-level request and a `need` carry an optional argv);
- when none is given it is the **empty** argv. The build definition carries no
- argv. It is visible *only* to that one target's recipe (delivered as the
- process's actual argv) and is **not** propagated to deps. Treating argv as
- config keeps the model uniform: everything a recipe sees is configuration, some
- inherited, some local. Local config is not part of `config-id`; it is serialized
- to its own canonical CAS blob, `argv-id`, and — unlike propagated config —
- `argv-id` *is* a first-class component of the resolution identity (below).
-
-**Serialized for replay, not just hashed.** Both the effective config map and the
-argv vector are persisted *by value* as canonical, content-addressed CAS blobs
-(`config-id`, `argv-id`) — never reduced to an opaque one-way hash. A trace
-references them by id, and they are part of its reachable closure (GC-rooted, and
-bundled with [shared traces](#shared-traces-trusted-as-signed-packages)). This is
-what lets the shallow path **replay every `need` request exactly** — reconstruct
-the dep's target name, its full effective config with overlays applied, and its
-argv — even when driving from an imported shallow trace with no access to the
-original build definition or workspace. Source files and globs are the opposite
-case: kept by hash only, because they are *verified* (did this still hash the
-same?), never replayed, and their bytes already live in the CAS.
-
-The **resolution identity** of a build is therefore the triple
-`(target-name, config-id, argv-id)`, where `config-id` is the effective
-*propagated* config and `argv-id` is the effective *local* argv (the request's
-argv, or the empty argv when none is supplied — the build definition carries no
-argv). The target name is just an identifier — argv is not encoded in it; it is
-supplied by the request and then content-addressed. Two requests that differ in the propagated
-config **or** the argv — `(T, C1, A)` and `(T, C2, A)`, or `(T, C, A1)` and
-`(T, C, A2)` — are genuinely distinct builds; any number may be in flight at once.
-
-`recipe-id` covers only the recipe *file bytes*. *Which* recipe a target maps to
-lives in the **build definition**, which the coordinator reads to resolve `T`.
-The only definition-derived input recorded for `T` is its **resolved recipe-id**
-(a per-node scalar), refreshed by recomputing it through the *live* definition —
-not a hash of the whole definition file. So repointing `T` to a different-content
-recipe busts it; repointing to a same-content recipe does not (it is the same
-build); and editing an *unrelated* target's stanza leaves `defn_find(T)`
-unchanged, so it does not bust `T`. The *mapping* is not an independent input —
-only the resolved recipe content is. (argv is *not* in the definition — it comes
-from the request, and a different argv is a different `argv-id`, hence a distinct
-build.)
-
-### Why two trace kinds
-
-The deep trace answers *"is this exact configuration unchanged and has any input
-moved?"* by refreshing the deepset closure — a DAG walk with structural sharing
-and an id-equality short-circuit, not a re-resolution. When it matches, the output
-is determined and we skip straight to materialization. It is the inner dev-loop
-fast path: edit code, rebuild under the same config.
-
-The shallow trace handles everything the deep path defers — a changed source that
-might not actually move a dep's output, and *any* configuration or argv change. It
-rebuilds the *direct* deps (cheaply, via their own traces, threading the new
-config and argv down through `need`), compares their resulting `tree-id`s against what it
-recorded, and if they match, the recipe is still skipped. This is the payoff of
-recording deps by *output* identity rather than by input identity: a subtree that
-ignores a changed config key, or absorbs a comment-only edit, produces the same
-output tree and short-circuits its parent's recipe.
-
-## On-disk storage
-
-The build store sits beside (or contains) a CAS. Everything content-addressed is
-immutable and self-verifying; exactly one class of object is mutable.
-
-```
-<store>/
- cas/ # the shared content store, per DISTRIBUTE.md
- blob/<pp>/<blob-id> # raw bytes: sources, config maps, argv vectors, deepset nodes
- tree/<pp>/<tree-id> # canonical directory manifests (output trees)
- ... # (chunk/, index/ as in DISTRIBUTE.md)
- build/
- trace/<pp>/<trace-id> # IMMUTABLE canonical trace bodies (deep + shallow) — CLAIMS
- target/<pp>/<target-key> # MUTABLE per-target trace set (the only mutable state)
- cache/<pp>/<tree-id>/ # tree cache: materialized output directories
- tmp/ # staging for atomic writes + recipe sandboxes
-```
-
-`<pp>` is the first two lowercase hex chars of the relevant id (the DISTRIBUTE.md
-convention). `trace-id` = `BLAKE2b` of the canonical trace body.
-`target-key` = `BLAKE2b("kit build target v1" ‖ target-name)` — note it depends
-on the target *name only*, never on config, argv, or recipe-id, so a target's
-index entry is a stable handle holding candidate traces across every
-`(config, argv)` it was recently built under, while its inputs churn.
-
-The line that sorts `cas/` from `build/` is **self-verifiability, not
-content-addressedness**. Config maps, argv vectors, and **deepset closure nodes**
-(below) are self-verifying content — hand over the bytes and the recipient
-recomputes the id and transitively checks every reference — so they are ordinary
-CAS blobs (trustless, fetchable from an untrusted mirror, bundled as plain
-blobs). A **trace body**, though equally content-addressed, is a *claim*
-(`inputs ⇒ output`) that cannot be verified without re-running the recipe, so it
-lives in `build/trace/` and is shared only as a *signed* bundle. Only `target/`
-records and the `cache/` materializations are otherwise build-specific.
-
-### Trace bodies (immutable, content-addressed)
-
-Both kinds are strict, byte-stable, INI-style text in the family of
-`kit-tree 1` / `kit-package 3`: a version line, ordered scalar fields, then
-sorted sections. Unknown keys/sections, duplicate rows, and non-canonical
-ordering are parse errors (a parse error is treated as *absent*, never as a
-match — fail safe). All ids are lowercase hex. Config values, source bytes, and
-glob expansions are stored *by hash*, never inline, so a body's size is
-independent of its inputs' sizes.
-
-**Shallow trace** — direct inputs and direct deps, for fine-grained rechecking:
-
-```
-kit-build-shallow 1
-target //app:server
-recipe <recipe-id>
-output <output-tree-id>
-config <config-id> ; this target's effective propagated config (full map blob)
-argv <argv-id> ; this target's local config (serialized vector blob)
-[config] ; CONSUMED propagated key NAMES, sorted (values live in the map)
-opt
-[source] ; sorted by path ("<path> -" marks an absent read)
-src/main.c <blob-id>
-[glob] ; sorted by pattern
-src/*.c <glob-result-hash>
-[dep] ; sorted by (dep-name, dep-config-id, dep-argv-id) — each row replays one `need`
-//lib:core <dep-config-id> <dep-argv-id> <dep-output-tree-id>
-```
-
-The `recipe <recipe-id>` scalar is the only definition-derived input (recomputed
-through the live definition on refresh); the definition file itself is *not* a
-source leaf, so editing an unrelated target's stanza does not bust this trace.
-
-**Deep trace** — the `(root config-id, argv)` binding to an output, plus a single
-pointer to the transitive input closure (held as a **deepset** DAG, below), *no*
-`[dep]` and *no* per-key `[config]` section:
-
-```
-kit-build-deep 1
-target //app:server
-recipe <recipe-id>
-output <output-tree-id>
-root-config <config-id> ; this target's effective propagated config (full map blob)
-argv <argv-id> ; local config (serialized vector blob)
-deepset <deep-set-id> ; the transitive input closure, as a deepset DAG (a CAS blob)
-```
-
-**Deepset** — one node of the transitive input-closure DAG, a CAS blob. The deep
-trace inlines none of the closure; it points at the root deepset, and each node
-points at its children. A subtree reached through many parents is *one* node
-(structural sharing, like the CAS), so the closure is never re-listed per
-ancestor:
-
-```
-kit-build-deepset 1
-target //app:server ; carried so refresh can recompute this node's recipe-id
-recipe <recipe-id> ; the node's recipe content-hash (the only definition-derived input)
-[source] ; this node's DIRECT source leaves, sorted by path
-src/main.c <blob-id>
-config.h - ; an ABSENT leaf: "-" = the path was absent when read
-[glob] ; this node's DIRECT glob leaves, sorted by pattern
-src/*.c <glob-result-hash>
-[child] ; direct deps' deep-set-ids, sorted
-<deep-set-id of //lib:core's node>
-```
-
-`deep-set-id = BLAKE2b(canonical deepset body)`, which is exactly its CAS blob id.
-
-- `config <config-id>` and `argv <argv-id>` reference the **serialized** effective
- config map and argv vector — canonical CAS blobs, kept by value and bundled with
- shared traces — so the target's invocation and every `need` it issues replay
- *exactly*, not merely check (see [Configuration model](#configuration-model)).
-- `[config]` lists the **names** of consumed propagated keys (consumed whether set
- *or* unset); the values live in the `config-id` map this trace references. A key
- *absent* from that map was consumed while unset, so later *adding* it busts the
- trace — no sentinel value needed. Matching compares, for each consumed key, the
- request's value against the built map's value (absent == unset).
-- `<blob-id>` = the source file's CAS blob id (`kit_blob_info`); source and glob
- leaves are kept by hash because they are *verified*, never replayed. An absent
- source is recorded as `<path> -` (a lone `-`), so *creating* the file later
- busts the trace — the source analogue of a consumed-while-unset config key.
-- `recipe <recipe-id>` (on the shallow trace and on every deepset node) is the
- target's **only** definition-derived input: `BLAKE2b` of the recipe *file*
- bytes, refreshed by recomputing it through the *live* definition
- (`defn_find(target) → recipe path → hash`). That catches a recipe edit *or* a
- repoint to a different-content recipe at any depth, treats a repoint to a
- same-content recipe as unchanged, and — because it goes through `defn_find` —
- is unaffected by edits to *unrelated* stanzas. There is no whole-definition
- source leaf.
-- `deepset <deep-set-id>` is the root of the closure DAG. Phase 1 loads it and
- its children from the CAS to refresh; if any deepset blob is absent (e.g.
- GC'd), the deep trace is treated as absent and resolution falls through
- (fail-safe).
-- `<glob-result-hash>` = `BLAKE2b` of the canonical `(path, blob-id)` listing the
- pattern matched (sorted by path). It changes if any matched file is added,
- removed, or edited — so one glob row covers the existence *and* content of its
- whole match set, and files read through a glob need no separate `[source]` rows.
-- `[dep]` rows carry the **dep's config-id and argv-id** (and output `tree-id`);
- together with the dep's own serialized config/argv blobs this re-resolves each
- dep under the exact propagated config *and* argv it used, overlays included.
-
-**Why the deep trace needs only `root-config` + the deepset closure.** If the
-request's `config-id` equals `root-config`, its `argv-id` equals the recorded
-`argv`, *and* refreshing the deepset finds nothing moved — every source/glob leaf
-still matches the live workspace **and** every node's `recipe-id` still recomputes
-the same through the live definition — then every recipe in the closure has
-byte-identical inputs *and* identical code, so every `need` overlay it computes is
-identical, every effective config downstream is identical, and by determinism the
-output is identical. Any input that could perturb a downstream overlay (a source a
-recipe branches on, a config value) is itself either a recorded source/glob leaf,
-a per-node `recipe-id`, or folded into `root-config`, so nothing escapes the
-check. Using the whole `root-config` (rather than just
-consumed keys) is a deliberate, conservative simplification: an *unconsumed*
-config change busts the deep fast path, but the [shallow path](#resolution-algorithm)
-recovers — it re-runs only the recipes whose output actually changed, so unrelated
-subtrees re-verify by hash without re-running.
-
-### Target record (mutable, the only mutable object)
-
-`build/target/<pp>/<target-key>` lists this target's candidate traces,
-newest-first, capped:
-
-```
-kit-build-record 1
-target //app:server
-deep <trace-id>
-deep <trace-id>
-shallow <trace-id>
-shallow <trace-id>
-```
-
-Each row points at a trace body in `build/trace/`. On every successful resolution
-the coordinator prepends the fresh trace, de-duplicates, and truncates each kind
-to a small cap (`KIT_BUILD_RECORD_CAP`, e.g. 8) — a bounded MRU window. Older
-traces age out and become GC-eligible. Multiple candidates exist because the same
-target may have been built under several distinct input, config, and argv
-combinations recently (e.g. two config values flipped back and forth, or two
-different argvs).
-
-### Storage state machine (atomicity and crash safety)
-
-The store must never hand back a wrong output after a crash. The rules:
-
-1. **Content objects** (`cas/blob`, `cas/tree`, `build/trace`, config maps, and a
- materialized `build/cache/<tree-id>/`) are written into `build/tmp/`, fsync'd,
- then **atomically renamed** to their final content-keyed path. A half-written
- object only ever exists under `tmp/` and is orphaned, never under its content
- key. Re-deriving the same content re-creates the identical path — writes are
- idempotent, so a racing or retried producer is harmless.
-
-2. **The target record is the only ordering-sensitive state**, updated by
- **read-modify-write into `tmp/` then atomic rename**. A reader always sees a
- complete prior or complete next version, never a torn one. A crash loses *at
- most* the most recent record update; losing a record entry is *safe* — the next
- build re-derives and rewrites it. A corrupt record (failed `kit-build-record 1`
- parse) is treated as empty.
-
-3. **Recipe sandboxes** live in `build/tmp/run-<n>/`. On success the output subdir
- is ingested into the CAS (`kit_cas_add_tree_from_dir`) and the sandbox is
- removed; on failure or crash it is orphaned and swept later.
-
-**Invariant.** Anything reachable under a content key (`blob/`, `tree/`,
-`trace/`) is complete and matches its key. A target record may *dangle* — point at
-a trace that GC removed — and readers tolerate that by treating the missing
-candidate as absent. The store degrades toward "rebuild," never toward "wrong
-answer."
-
-**Concurrency.** Two coordinators sharing a store are safe for content writes
-(idempotent atomic renames). Target-record updates are last-writer-wins; both
-writers wrote *valid* records, so the only loss is MRU ordering, costing at most a
-rebuild. An optional per-target-key advisory lock around the read-modify-write
-removes even that.
-
-## Build coordinator state and caching
-
-### In-memory state
-
-All state hangs off one `KitBuildCoordinator` context (no globals — the project
-rule). For the life of the process it memoizes every base-input probe and every
-target resolution, so a diamond in the graph is built once and a source file is
-hashed once:
-
-| Field | Contents | Notes |
-|-------|----------|-------|
-| `source_hashes` | `path → blob-id` (+ stat). | Per-process memo. |
-| `glob_results` | `pattern → (sorted paths, glob-result-hash)`. | Per-process memo. |
-| `config_maps` | `config-id → map`, and overlay results. | Immutable; content-addressed. |
-| `deepsets` | `deep-set-id → (interned node, refresh-valid?)`. | Shares subtrees; skips unchanged ones by id. |
-| `targets` | `(target-name, config-id, argv-id) → future` of `{output-tree-id, deepset node, path}`. | Memo **and** in-flight dedup. |
-| `cas` | Open `KitCas*` handle over `cas/`. | Plus optional remote (below). |
-| `store` | Paths + target-record reader/writer over `build/`. | — |
-| `jobs` | Semaphore bounding concurrent recipe processes. | The global parallelism limit. |
-
-"Cached over the life of the coordinator process" means exactly these memo
-tables: the coordinator assumes the workspace does not change *under it*
-mid-build.
-
-The `targets` table is keyed by the full `(target-name, config-id, argv-id)` and
-holds a **future**, not a flag — so concurrent `need`s of the same
-`(T, config-id, argv-id)` await one resolution rather than racing (see
-[Parallelism](#parallelism)). A resolved
-build yields the **output `tree-id`** (to satisfy a `need`), a materialized
-**path**, and its **deepset node** (the root of its transitive input-closure DAG,
-to fold into a parent's deepset).
-
-### Cycle detection
-
-The `targets` memo alone cannot catch a cycle — a self-dependent target would
-simply await its own unresolved future and deadlock. So each resolution carries an
-explicit **build chain**: the ordered list of `(target-name, config-id, argv-id)`
-frames from the root request down to here. A `need` whose
-`(dep, config-id, argv-id)` already appears on the chain is a dependency cycle;
-the chain *is* the error message (`//a → //b → //a`). The chain is per-path and
-distinct from the cross-path memo: the same `(T, config-id, argv-id)` may appear
-in many chains (a shared dep) but never twice in one.
-
-### Resolution algorithm
-
-A request is `resolve(T, cfg, argv, chain)` where `cfg` is the effective
-propagated config (with `cfg.id` its config-id) and `argv` is the effective local
-argv (with `argv.id` its argv-id — the request's argv, or empty when none is
-supplied). The config/argv-dependence is recorded in and verified against the
-traces; the *deep* path checks whole-config-id and argv-id equality, the *shallow*
-path checks consumed keys and argv-id.
-
-```
-resolve(T, cfg, argv, chain):
- key = (T, cfg.id, argv.id)
- if key in chain: error cycle(chain + key)
- if key in targets: return await targets[key] # cross-path memo / in-flight dedup
- targets[key] = new future ; chain' = chain + key
-
- if record(T) is empty and trace_remotes configured: # clean checkout: try shared traces
- pull_once(T) # verify+install signed bundle, then re-scan
-
- # ---- Phase 1: deep fast path (same config+argv, did anything move?) ---
- for D in deep_traces(T), newest-first:
- if D.root_config == cfg.id and D.argv == argv.id:
- node = deepset_load(D.deepset) # load DAG from CAS; absent => skip (fail-safe)
- if node and refresh(node) all match live: # rehash/reglob + recompute recipe-id, memoized
- p = materialize(D.output) # pure: cache -> CAS -> remote; ERR => fall through
- if p ok: return done(D.output, p, node)
-
- # ---- Phase 2: shallow path (config, argv, and/or sources moved) ------
- for S in shallow_traces(T), newest-first:
- if S.recipe != recipe_id(T): continue # recipe edit/repoint (live defn)
- if S.argv != argv.id: continue # local config
- M = config_by_id(S.config) # the built map (serialized blob)
- if any consumed key in S.config-keys differs between cfg and M: continue
- if any direct source/glob leaf of S changed: continue
- ok = true ; child_nodes = []
- for (dep, dep_cfg_id, dep_argv_id, recorded_tree) in S.deps: # may run in parallel
- r = resolve(dep, config_by_id(dep_cfg_id), argv_by_id(dep_argv_id), chain') # replay the need by id
- if r.output != recorded_tree: ok = false; break
- child_nodes.push(r.leafset)
- if ok:
- node = union(direct{recipe_id, source/glob leaves} of S, child_nodes) # builds+stores the deepset
- write_deep_trace(T, cfg.id, argv.id, node.id, S.output) # refresh the deep trace
- p = materialize(S.output) # pure; ERR => fall through
- if p ok: return done(S.output, p, node)
-
- # ---- Phase 3: run the recipe ----------------------------------------
- return run_recipe(T, cfg, argv, chain')
-```
-
-with the materialization ladder shared by every cache hit — a **pure locator**
-that never runs a recipe:
-
-```
-materialize(tree-id) -> path | MISS:
- if tree-id in build/cache/ : return that path # already on disk
- if tree-id in cas/ : restore into build/cache/, return path
- if remote configured : fetch tree-id (+ blobs) into cas/, verify, restore
- else : MISS # bytes gone everywhere
-```
-
-On `MISS` the caller does not return — it falls through to the next candidate
-and ultimately Phase 3, which rebuilds and records the correct output. Keeping
-`materialize` recipe-free is what lets a cache hit's recorded `tree-id` always
-describe the bytes it returns (no rebuild can silently substitute a different
-tree), and removes the resolve→runner edge.
-
-This is the brief's flow, sharpened by config:
-
-- *Phase 1* is the deep fast path: identical config-id **and argv-id** and an
- all-clear deepset refresh — every source/glob leaf unchanged **and** every
- node's `recipe-id` still recomputing the same — ⇒ reuse. `refresh` hits the
- per-process memos and the deep-set-id validity cache, so a shared subtree is
- checked once and an unchanged subtree is skipped by id equality.
-- *Phase 2* is the shallow path, taken when Phase 1 finds nothing (config or argv
- changed, or a source moved). It guards on the target's own argv-id, consumed
- config, and direct leaves, then re-resolves each recorded dep **under the dep's
- recorded config-id and argv-id** and compares outputs. Re-using the recorded
- `(dep_cfg_id, dep_argv_id)` is correct: if the parent's consumed config or argv
- were different, the guards above would have failed first and the parent would
- re-run, recomputing its `need` overlays.
-- A Phase-2 hit also writes a *fresh* deep trace from the now-known closure, so the
- next request gets the Phase-1 fast path back.
-- *Phase 3* runs the recipe only when no trace holds, or when a hit's bytes were
- evicted and no remote can supply them.
-
-The non-obvious win is **Phase 2 succeeding after an input changed.** A changed
-source busts the deep trace (Phase 1 gives up), but if that source only feeds a dep
-whose recipe maps it to an unchanged output (`tree-id` identical), the dep compare
-passes and `T`'s recipe is skipped. The deep trace is the cheap "nothing moved"
-check; the shallow trace is the "did the churn actually reach me?" check.
-
-### Running a recipe
-
-```
-run_recipe(T, cfg, argv, chain):
- acquire jobs # global parallelism limit
- sandbox = build/tmp/run-<n>/ ; out = sandbox/out/
- spawn recipe (process argv = argv, the request's argv or empty when none given) with a
- CLEAN env (host inherits nothing): { KIT_BUILD_SOCK, KIT_BUILD_OUT=out,
- KIT_BUILD_TARGET=T, workspace root } + cfg's `env.*` keys as declared env vars
- service the recipe's protocol requests, logging each as a dep (next section);
- config-get reads cfg; source returns the live workspace path + pinned blob-id;
- need releases this recipe's job slot, recurses resolve(...) under cfg ⊕ overrides
- and the need's own effective argv, then reacquires the slot (so a chain deeper
- than `jobs` cannot deadlock)
- release jobs
- on nonzero exit: propagate failure, write NO trace
- on success:
- output = kit_cas_add_tree_from_dir(out)
- put serialized cfg map (cfg.id) and argv vector (argv.id) into the CAS
- node = union(direct{recipe_id, source/glob/absent leaves}, child deepset nodes)
- # builds + stores the root deepset as a CAS blob, yields its deep-set-id
- write_shallow_trace(T, recipe_id, argv.id, cfg.id, consumed key names,
- direct leaves, dep edges with their config-ids and argv-ids, output)
- write_deep_trace (T, cfg.id, argv.id, node.id, output) # references the deepset
- prepend both to T's target record (dedup, truncate to cap)
- install out in build/cache/<output>/
- return done({output, path}, node)
-```
-
-Writing *both* trace kinds on every real build is what lets a later request take
-whichever path fits the change it sees.
-
-### Parallelism
-
-The coordinator owns all parallelism: it is the single process that launches and
-manages every recipe, so the overall job limit is configured in it (the `jobs`
-semaphore). Parallelism comes from two places: **independent targets** (sibling
-deps, multi-target requests, Phase-2 dep re-resolution) and **a single recipe's
-fan-out** — a recipe issues `need-submit` for each dependency, the coordinator
-dispatches them onto workers concurrently, and the recipe `need-await`s the
-tokens. Both reduce to one primitive: a fresh `(T, config-id, argv-id)` is
-*dispatched* (driven on a worker thread), and the `targets` futures guarantee it
-is built once even when many parents request it at the same instant — a
-duplicate awaits the in-flight future rather than racing. The semaphore bounds
-*actively running* recipes, not in-flight ones: a recipe blocked in a `need`
-(or `need-await`) releases its slot and reacquires when the sub-build returns, so
-a chain deeper than `jobs` cannot deadlock. Cycle detection composes with
-concurrency through the per-path build chain (a parent-linked cactus stack, so
-each dispatched need extends a shared read-only prefix without copying): the
-global memo handles dedup, the chain handles cycles.
-
-## Recipe protocol
-
-Recipes communicate back over a **transport the driver defines** and the library
-abstracts behind a host vtable — the same "host supplies all side effects"
-principle the rest of kit follows. The library defines the *command set* and the
-length-prefixed request/response framing; the host supplies connect/read/write.
-
-```c
-typedef struct KitBuildTransport {
- /* Server: create a uniquely-named endpoint for one recipe (its name, written
- * into name_out, is passed to the child in $KIT_BUILD_SOCK); accept the
- * recipe's one connection on it; tear the endpoint down when done. Per-recipe
- * endpoints are what let many recipes run concurrently. */
- int (*listen)(void* user, char* name_out, size_t cap, KitBuildListener** out);
- int (*accept)(void* user, KitBuildListener* lst, KitBuildConn** out);
- void (*close_listener)(void* user, KitBuildListener* lst);
- /* Client: dial the endpoint named in $KIT_BUILD_SOCK; read/write length-
- * prefixed frames; close. */
- int (*dial)(void* user, KitSlice endpoint, KitBuildConn** out);
- int (*read_frame)(void* user, KitBuildConn*, uint8_t* buf, size_t cap, size_t* n);
- int (*write_frame)(void* user, KitBuildConn*, const uint8_t* buf, size_t n);
- void (*close)(void* user, KitBuildConn*);
- void* user;
-} KitBuildTransport;
-```
-
-Defaults and portability: a **unix-domain socket** (Linux, macOS, FreeBSD, and
-Windows 10+, which all support `AF_UNIX`) named in `$KIT_BUILD_SOCK`, or an
-**anonymous pipe pair** on inherited fds where a socket is undesirable; Windows
-may instead use a **named pipe**. An **in-process** transport (a direct callback
-table) serves recipes that are kit library calls rather than subprocesses. The
-command set is identical across all of them.
-
-Every request both **returns a value** and **logs a dependency**. The logged
-dependency is what lands in the shallow trace and (after expansion) the deep
-trace. The contract that makes caching correct: **an input the recipe reads but
-does not request is invisible to the cache** — so every input must flow through a
-command.
-
-| Command | Returns | Dependency logged |
-|---------|---------|-------------------|
-| `config-get <key>` | the propagated value (or *unset*) | config dep: key recorded as consumed; its value is the one in the effective `config-id` map (absent = unset) |
-| `source <path>` | `blob-id` (or *absent*) + a path to read | source dep: `(path, blob-id)`, or `(path, absent)` |
-| `glob <pattern>` | sorted list of matching paths (streamed) | glob dep: `(pattern, glob-result-hash)` |
-| `need <target> [k=v…] [argv…]` | the dep's output `tree-id` + a path (blocks) | target dep edge: `(dep, dep-config-id, dep-argv-id, output-tree-id)` |
-| `need-submit <target> [k=v…] [argv…]` | a **token** (does not block) | *(nothing yet — logged on await)* |
-| `need-await <token>` | the submitted dep's output `tree-id` + a path | target dep edge: `(dep, dep-config-id, dep-argv-id, output-tree-id)` |
-
-- **`config-get`** reads the target's *effective propagated* config and records the
- value's hash, so changing a consumed key invalidates while changing an unconsumed
- key does not. If a changed consumed key makes the recipe branch and request a
- *new* key next time, the old trace already fails to match on the changed key, so
- the new key-set is discovered on the rebuild — self-correcting, never needing to
- predict the input set ahead of time. Local config (argv) is *not* read here; it
- arrives as the process's argv. **Environment** is config too: keys under the
- `env.` prefix (e.g. `env.PATH`) become the recipe's environment variables, so a
- recipe's env is tracked, hermetic, and propagates like any config — the spawned
- process otherwise gets a *clean* environment (nothing ambient inherited).
-- **`source`** hands back a path inside the **live workspace** (not a staged
- copy) plus the blob-id the read is pinned to; an absent path is reported and
- recorded as an *absent* leaf (creating it later busts the trace). Returning the
- live path makes workspace immutability for the build's duration load-bearing
- for soundness — see [Determinism](#determinism-and-hermeticity).
-- **`glob`** records the whole match set's content via `glob-result-hash`; the
- recipe then reads the returned paths without further declaration. Matches are
- **streamed** across as many frames as needed, so an arbitrarily large match set
- is not bounded by a single frame.
-- **`need`** is the dynamic-dependency primitive. The optional `k=v` pairs
- **overlay** propagated config for that sub-build; an optional argv vector sets
- the dep's **local argv** (omitted ⇒ the empty argv; local argv never
- propagates). The coordinator resolves `(dep, cfg ⊕ overrides, argv)`
- recursively, returns its output `tree-id` and a readable path, and records the
- edge with the dep's `config-id` and `argv-id` so the shallow path can re-resolve
- identically. `need` is also where cycles are caught.
-- **`need-submit` / `need-await`** are the *future-based* form of `need`, for
- building a recipe's deps **concurrently**. `need-submit` resolves nothing
- inline — it dispatches `(dep, cfg ⊕ overrides, argv)` onto the coordinator's
- workers and returns a **token** immediately (failing fast only on a cycle or
- unknown target); the recipe submits its whole fan-out, then `need-await`s each
- token to collect results. `need` is exactly `submit` + `await` fused into one
- blocking round-trip (cheaper for the one-dep-at-a-time case, no worker
- hand-off). Two rules keep the cache sound:
- - **The dep edge is recorded on `await`, not `submit`.** A submitted-but-never-
- awaited need is speculative (its output never reached the recipe), so it is
- *not* a dependency; it is cancelled when the recipe exits.
- - **`await` is always for a specific token** — there is deliberately no "await
- whichever finishes first." Concurrency is a performance property only; the set
- of needs a recipe awaits (hence its dependencies and output) must stay a
- deterministic function of its inputs, never of completion order, or two runs
- would record different dependencies. The recorded `[dep]` section is sorted,
- so the trace is byte-identical regardless of submit/await order.
-- **Outputs** need no command: the recipe writes under `$KIT_BUILD_OUT` and the
- coordinator snapshots that directory on exit.
-
-## Remote CAS and shared traces
-
-Two independent network capabilities, split along the DISTRIBUTE.md line —
-**content is trustless (hash-verified); claims are trusted (signed).**
-
-### Remote object fetch (trustless, via a fetch recipe)
-
-The coordinator performs no network I/O itself. When `materialize` (or a blob
-restore) needs an object that is absent locally and a remote is configured, it
-invokes a user-provided **fetch recipe** — an executable or command template, e.g.
-`curl -fsS -o "$KIT_FETCH_OUT" "https://cache.example/{kind}/{pp}/{id}"`, rendered
-with `{kind}` ∈ `blob`/`tree`, `{pp}`, `{id}` exactly like DISTRIBUTE.md's
-external-fetch templates. The fetched bytes land in `build/tmp/` and are
-**verified against the requested content id** before being installed into the
-local CAS; a corrupt or malicious mirror fails the hash check and is discarded. So
-the remote and the fetch recipe are *untrusted* — the existing self-verifying CAS
-makes that safe. This adds one rung to the materialization ladder (tree cache →
-local CAS → remote fetch) and lets a clean checkout *download* an output instead
-of rebuilding it. A **deepset** node needed during a deep refresh is fetched the
-same way — it is a CAS blob (`{kind}=blob`), so no separate kind is required.
-
-### Shared traces (trusted, as signed packages)
-
-A trace is a **claim**: "these inputs ⇒ this output tree." Unlike content, it is
-**not self-verifying** — confirming it means re-running the (assumed-deterministic)
-recipe, which is exactly the work we are trying to avoid. To safely import someone
-else's trace we must **trust the claimant**. Traces are therefore shared as
-**signed trace bundles**, reusing the DISTRIBUTE.md package + minisign + trust
-machinery wholesale:
-
-- A bundle is a signed manifest (`kit-build-traces 1`, signed exactly like a
- `kit-package` manifest) listing `(target-name, kind, trace-id, output-tree-id)`
- claims, carried in a `.kpkg` (portable tar.gz or native kpkg) alongside the
- trace bodies and the CAS blobs they reference — the **serialized config-map and
- argv blobs** (required, else an imported shallow trace cannot replay its
- `need`s) and the **deepset closure blobs** a deep trace points at (required,
- else an imported deep trace cannot refresh) — plus, optionally, the referenced
- output trees/blobs.
-- Trust is the DISTRIBUTE.md model unchanged: verify the minisign signature
- against the trusted-keys file (`-p KEY`, the anchor file, or `--tofu`); the
- signed trusted comment binds the signature to the manifest hash.
-- Import: verify signature → anchor key → install the trace bodies into
- `build/trace/` and prepend them to the relevant target records. Output bytes come
- from the bundle or from the remote CAS — either way **hash-verified** on use.
-
-The result is a precise security split: a local build can now deep/shallow-**hit**
-on a remote builder's trace — obtaining the output *without running the recipe* —
-while trusting only the *signed claim*; the output bytes themselves remain
-trustless (verified by `tree-id`/`blob-id`). Trusting a trace signer is exactly
-like trusting a package signer in DISTRIBUTE.md: it is trust in their build
-outputs, gated by the trusted-keys allowlist, and auditable by re-running under
-[verify mode](#determinism-and-hermeticity).
-
-## Determinism and hermeticity
-
-Cache correctness is exactly the assumption *output = f(declared inputs)*,
-deterministically.
-
-- **Declared-inputs-are-complete.** Reading an undeclared file is a hermeticity
- violation. The protocol makes declaration the only *intended* way to get an
- input, but **enforcement is deferred** (see below): for now it is a contract
- recipes must honor. The recipe runs with a **clean environment** (only the
- KIT_BUILD_* vars and the build's declared `env.*` config), so ambient
- PATH/locale/etc. cannot leak in as undeclared, untracked inputs.
-- **Workspace immutability is load-bearing.** `source` returns a live workspace
- path, so the bytes a recipe reads are the bytes on disk *at read time*, not a
- snapshot of what was hashed. If the workspace mutates mid-build the recorded
- input hash and the bytes actually consumed can disagree, making a trace's claim
- false — *unsound*, not merely stale. The coordinator therefore assumes the
- workspace does not change for a build's duration; verify mode is the audit.
-- **Determinism.** Timestamps, RNG, and unpinned network fetches break the model —
- a second build's captured tree differs from the recorded output, and the cache
- would serve a stale-but-believed-current result. Mitigations: declare such
- inputs (a "now" config value, a pinned URL+hash), or mark a target **no-cache**
- so it always runs Phase 3.
-- **Verify mode.** A diagnostic mode re-runs a recipe whose trace says "unchanged"
- and compares the fresh `tree-id` to the recorded one; a mismatch flags a
- nondeterministic or under-declared recipe — the recommended audit before
- trusting (or signing and sharing) traces.
-
-## Worked example
-
-`//app:server` depends on `//lib:core`; the recipe globs `src/*.c`, reads
-`src/main.c`, and consumes config `opt`. The request is under config `C0` (so
-`config-id = c0`). Neither request supplies argv, so every build's argv is empty
-(argv-id `a0`), held constant throughout; the full resolution key is the triple
-`(target, config-id, argv-id)`.
-
-1. **Cold build.** No record. Phase 3 runs both recipes. `//lib:core` builds →
- `tree L0`. `//app:server` logs `config opt`, `glob src/*.c`, `source src/main.c`,
- `need //lib:core` (under `c0` → `(//lib:core, c0, a0)`); yields `tree A0`.
- Both trace kinds written for both targets. `build/cache/A0/` materialized, path
- returned.
-2. **No-op rebuild (same `C0`).** Phase 1: `//app:server`'s deep trace has
- `root-config c0` and `argv a0` (both match) and refreshes `opt` via config-id, `src/*.c`,
- `src/main.c`, and the folded `lib/core.c` — all memoized, all match. `A0` is in
- the tree cache. Returns instantly, nothing re-run, no graph walk.
-3. **Comment-only edit to `lib/core.c`.** `lib/core.c`'s blob-id moved → the deep
- trace fails Phase 1 (a folded source leaf changed). Phase 2: direct leaves
- (`opt`, `src/*.c`, `src/main.c`) unchanged, so probe the one dep —
- `resolve(//lib:core, c0, a0)`. Its recipe re-runs (its source moved) but emits a
- byte-identical `L0` (comment stripped). `L0 == L0` ⇒ `//app:server`'s recipe is
- **skipped**, `A0` restored, a refreshed deep trace written so step 2's fast path
- returns next time.
-4. **Flip `opt` (now `C1`, `config-id = c1`).** Phase 1 is skipped outright:
- `//app:server`'s deep trace has `root-config c0 ≠ c1`. Phase 2 under `c1`:
- `opt` is a consumed key whose value differs between `c1` and the trace's built
- map → no shallow trace holds → Phase 3 re-runs `//app:server`. Its `need //lib:core` carries no `opt` override,
- so the dep resolves as `(//lib:core, c1, a0)`; but `//lib:core` never
- consumes `opt`, so its shallow trace under `c1` matches by argv-id (`a0`),
- consumed-keys (empty), and direct leaves, and `L0` is reused without
- re-running. Only the one recipe that actually depends on `opt` re-ran.
-
-## Decided / deferred / open
-
-**Decided.**
-
-- **Transport** is abstracted behind a host vtable the driver defines; defaults are
- a unix socket or anonymous pipe, with a Windows named-pipe fallback and an
- in-process variant. Supported hosts: Linux, macOS, Windows, FreeBSD.
-- **Parallelism** lives in the coordinator (the `jobs` semaphore); futures dedup
- shared targets; the per-path chain detects cycles.
-- **Remote CAS** delegates fetching to a user-provided fetch recipe and verifies by
- content id (trustless).
-- **Trace sharing** ships traces as signed `.kpkg` bundles over the DISTRIBUTE.md
- trust model (trusted), because traces are claims, not self-verifying content.
- Self-verifying content (sources, output trees, config/argv blobs, **deepset
- nodes**) lives in `cas/`; only claims live in `build/trace/`.
-- **Structural deepset closure (adopted).** The transitive closure is a Merkle
- DAG of **deepset** nodes — `{ target, recipe-id, direct source/glob leaves,
- [child-deep-set-id…] }`, `deep-set-id = BLAKE2b(canonical body)` — each a
- self-verifying **CAS blob** (`deep-set-id` == blob-id). A deep trace inlines
- none of the closure; it points at the root deepset, and a subtree reached
- through many parents is one node (structural sharing like the CAS). Building a
- parent is "concat direct leaves + child ids, hash" — the union *is* the
- construction, never an N-way merge. Refresh memoizes `deep-set-id → valid?`, so
- a shared subtree is checked once and an unchanged subtree is skipped by id
- equality at its root without descending — change detection is O(changed
- frontier), not O(closure). The cost accepted: refresh walks the DAG (rather than
- one flat list) and the child deepset blobs must be present (GC-rooted; bundled
- with shared traces; an absent one makes Phase 1 fall through, fail-safe).
-- **Recipe identity is content-only.** The sole definition-derived input is a
- target's resolved `recipe-id` (a per-node scalar), refreshed by recomputing it
- through the live definition. No whole-definition source leaf; the target→recipe
- *mapping* is not an independent input.
-- **Recipe environment is clean** and declared via the `env.*` config namespace
- (tracked); `source` reads are live (workspace immutability is load-bearing);
- large globs stream across frames; `materialize` is a pure locator (no rebuild
- rung); a clean-checkout miss tries one lazy signed-trace pull before Phase 3.
-- **Public surface** is a public header `<kit/build_coord.h>` plus a `kit build` driver
- command, gated by `KIT_BUILD_ENABLED` (the `kit/cas.h` + `kit cas` precedent). A
- thin CLI parses flags and supplies the transport/host vtables; the coordinator
- and trace model live in the library.
-
-**Deferred.**
-
-- **Hermeticity enforcement.** No sandbox-deny or FS-trace at first; the protocol
- defines the contract, enforcement comes later (deny undeclared reads, or
- `strace`/FUSE detection that warns).
-- **In-process recipes** run on a `KitBuildSched` thread (the framed protocol
- needs the recipe to run concurrently with the service loop, which a subprocess
- gives for free). This is a supported configuration — it is the substrate for
- the integration test harness ([BUILD_TESTING.md](BUILD_TESTING.md)). Only the
- *sequential* (`sched == NULL`) in-process case is deferred; it would need a
- direct-dispatch bypass of the service loop.
-- **GC.** Deferred. When built: mark-and-sweep rooted at live target records →
- reachable trace bodies → referenced output trees/blobs, config-maps, argv
- vectors, **and the deepset-closure blobs**; sweep unreachable `trace/`, `cas/`,
- and `cache/`, with LRU size bounds on the (re-derivable) tree cache and CAS.
diff --git a/doc/plan/BUILD_INTERNALS.md b/doc/plan/BUILD_INTERNALS.md
@@ -1,9 +1,10 @@
-# Build coordinator — internal module design
+# Build coordinator — internal module notes
-> **Status: design, not yet built.** Companion to [BUILD.md](BUILD.md), which
-> specifies *what* the content-addressed build coordinator does (the trace model,
+> Historical implementation notes. The durable feature spec is
+> [../BUILD_COORDINATOR.md](../BUILD_COORDINATOR.md), which specifies *what* the
+> content-addressed build coordinator does (the trace model,
> the storage state machine, the resolution algorithm, the recipe protocol). This
-> doc specifies *how* the implementation is carved into modules under `src/build/`:
+> doc records *how* the implementation is carved into modules under `src/build/`:
> for each module, what it is responsible for, which other modules it depends on,
> and a pseudocode sketch dense enough to prove the interfaces in the `src/build/*.h`
> spike are sufficient to implement every module **in parallel**. Where a sketch
@@ -794,7 +795,8 @@ int build_runner_record_traces(c, T, cfg, argv, log, output[32], &out_node):
with `jobs < max-chain-depth` deadlocks (parent holds the only slot; child can never
acquire one). The fix is the release/reacquire around `build_resolve` shown above —
the jobs semaphore bounds *actively running* recipes, not *in-flight* ones. In
- sequential mode `jobs_*` are no-ops so this is free. This belongs in BUILD.md's
+ sequential mode `jobs_*` are no-ops so this is free. This belongs in
+ BUILD_COORDINATOR.md's
Parallelism section too.
- `runner.c` includes `protocol.h`; `runner.h` doesn't need to (no protocol types in
its signatures). The leafset interning (so `out->leafset` lives for the process) is a
@@ -933,7 +935,7 @@ KitStatus kit_build(coord, req, out):
## Interface findings
Concrete adjustments the pseudocode surfaced. **All applied** to the `src/build/*.h`
-spike, the public `<kit/build_coord.h>`, and `BUILD.md` as of this revision; the entries
+spike, the public `<kit/build_coord.h>`, and `BUILD_COORDINATOR.md` as of this revision; the entries
below are the rationale of record. None block starting the L0/L1 modules.
1. **`client` module ownership.** The recipe-side `kit_build_client_*` need a real
@@ -957,7 +959,7 @@ below are the rationale of record. None block starting the L0/L1 modules.
`accept(user, KitBuildListener*, KitBuildConn** out)`, `close_listener`. Concurrent
recipes each get a uniquely-named endpoint; the client `dial` side was already there.
6. **Jobs slot released while blocked on `need`.** *(Applied — `coord.h`, `runner.h`,
- `BUILD.md §Parallelism` + the `run_recipe` sketch.)* The semaphore bounds *actively
+ `BUILD_COORDINATOR.md §Parallelism` + the `run_recipe` sketch.)* The semaphore bounds *actively
running* recipes; a recipe blocked on a `need` yields its slot, preventing a
`jobs < chain-depth` deadlock.
7. **`build_coord_leafset_intern`.** *(Applied — `coord.h`.)* `runner`/`resolve` hand
@@ -966,7 +968,7 @@ below are the rationale of record. None block starting the L0/L1 modules.
leaking heap ownership upward.
**Design-review decisions** (a second pass that pressed on correctness and seams;
-all applied to the spike headers, `<kit/build_coord.h>`, and `BUILD.md`):
+all applied to the spike headers, `<kit/build_coord.h>`, and `BUILD_COORDINATOR.md`):
8. **Deep-trace soundness vs. recipe changes.** *(Applied — `trace.h`, `coord.h`,
`resolve.h`, `defn.h`.)* The flat deep trace checked source/glob leaves but never
@@ -1017,7 +1019,7 @@ all applied to the spike headers, `<kit/build_coord.h>`, and `BUILD.md`):
- **Source reads stay live.** *(Decision, not a code change.)* `source` returns the
live workspace path (no staging); workspace immutability for a build's duration is
- therefore load-bearing for *soundness*, documented in `BUILD.md §Determinism`.
+ therefore load-bearing for *soundness*, documented in `BUILD_COORDINATOR.md §Determinism`.
- **In-process recipes run on a `sched` thread.** *(Supported — the integration
test substrate; see [BUILD_TESTING.md](BUILD_TESTING.md).)* The framed protocol
needs the recipe to run concurrently with the service loop; an in-process recipe
@@ -1047,7 +1049,7 @@ spike headers.
- **Wave D (on C):** `resolve` then `runner` together (they share the recursion seam,
findings #2/#6) and `bundle`. End-to-end smoke via the in-process transport: cold
build → no-op rebuild → comment-edit (Phase 2 hit) → config flip — exactly the
- [worked example](BUILD.md#worked-example).
+ [worked example](../BUILD_COORDINATOR.md#worked-example).
- **Wave E:** `src/api/build.c` composition + the `kit build` driver command +
`KIT_BUILD_ENABLED` gating, then the Makefile test targets.
diff --git a/doc/plan/BUILD_TESTING.md b/doc/plan/BUILD_TESTING.md
@@ -1,7 +1,8 @@
# Build coordinator — testing strategy
-> **Status: design, not yet built.** Companion to [BUILD.md](BUILD.md) (the
-> design) and [BUILD_INTERNALS.md](BUILD_INTERNALS.md) (the module breakdown).
+> Historical testing notes. Companion to
+> [../BUILD_COORDINATOR.md](../BUILD_COORDINATOR.md) (the feature spec) and
+> [BUILD_INTERNALS.md](BUILD_INTERNALS.md) (the module breakdown).
> This doc specifies *how the subsystem is tested* — the shared harness, the
> per-module plan, the integration scenarios, and the cross-cutting properties
> (byte-stability, fail-safe parsing, minimal-rebuild, crash-safety,
@@ -82,7 +83,7 @@ harness (decision below).
### The scenario spine
-The [worked example](BUILD.md#worked-example) is the backbone. Each step asserts
+The [worked example](../BUILD_COORDINATOR.md#worked-example) is the backbone. Each step asserts
**(output tree-id, `KitBuildStats` delta)** — the stats diff names the path taken:
1. **cold** → `recipes_run += 2`;
@@ -153,7 +154,7 @@ design — each maps to a [finding](BUILD_INTERNALS.md#interface-findings):
- **Sequential degrade.** The same scenario suite runs with `sched == NULL`:
`jobs_*` no-op, futures complete inline, no thread spawned — identical outputs
and stats. (In-process *recipes* still need a thread, so the sequential suite
- uses subprocess or pre-seeded traces; see BUILD.md §Deferred.)
+ uses subprocess or pre-seeded traces; see BUILD_COORDINATOR.md §Limits.)
## Observability — `KitBuildStats`
diff --git a/doc/plan/README.md b/doc/plan/README.md
@@ -18,7 +18,6 @@ shrinks to whatever remains open (and is deleted once nothing remains open).
| [ARM32.md](ARM32.md) | 32-bit ARM (`arm-none-eabi`, ARMv7-M/ARMv7E-M Thumb-2, Cortex-M3/M4/M7) freestanding backend: Phase 1 (walking skeleton) is landed; Phase 2 tracks the remaining ops, the -O1 known-frame path, 64-bit, atomics, TLS, and the `qemu-system-arm` cross-test lane. | [../ARCH.md](../ARCH.md), [../PORT.md](../PORT.md) |
| [MCU.md](MCU.md) | Microcontroller development workflow for STM32 Cortex-M (ARMv7-M/E-M) and Espressif RISC-V (ESP32-C/H/P): the last-mile gaps over the working backends — `objcopy` ihex/srec, reusable startup/vector-table + starter linker script, the rv32 soft-float-default footgun, SDK interop, and on-target debug. Assessment stage; references ARM32.md for ARM-core follow-ons. ARMv6-M/Cortex-M0 and Xtensa are out of scope. | [ARM32.md](ARM32.md), [../RUNTIME.md](../RUNTIME.md), [LINKER.md](LINKER.md) |
| [SYSROOTS.md](SYSROOTS.md) | Cross-compile sysroot packaging: minimal per-target stubs/headers/CRT objects distributed via `.kpkg` for the support set. Design complete, implementation not yet started. | — |
-| [BUILD.md](BUILD.md) | A new content-addressed build coordinator (Bazel/Nix-style incremental builds layered on the CAS) — storage state machine, caching algorithm, recipe protocol. Design, not yet built. Distinct from `../BUILD.md` (kit's own Makefile build). | — (new subsystem) |
| [TODO.md](TODO.md) | Open deferred fixes and code smells, plus terse backlog folded from retired plan docs (arch-backend parity, Wasm object backend, Windows x64 self-host, bootstrap breadth). Completed items are removed instead of checked off. A current backlog, not a roadmap. | — |
Speculative, not-committed designs (no code, parked) live in [`../ideas/`](../ideas/)
@@ -31,6 +30,8 @@ worklist and frontend/CG redesigns (→ [../OPT.md](../OPT.md),
image pipeline (→ [../KERNEL.md](../KERNEL.md)); the bootstrap fixed point
(→ [../BUILD.md](../BUILD.md)); aarch64 Windows self-host (→ [../WINDOWS.md](../WINDOWS.md));
the portability test surface (→ [../PORT.md](../PORT.md)); the compile-speed/
-code-size benchmarking methodology (→ [../BENCHMARKING.md](../BENCHMARKING.md)); and
+code-size benchmarking methodology (→ [../BENCHMARKING.md](../BENCHMARKING.md));
ELF shared library production — DSO output mode, dynamic tags, exports/imports,
-PIC codegen, and driver enablement (→ [../LINK.md](../LINK.md), [../OBJ.md](../OBJ.md)).
+PIC codegen, and driver enablement (→ [../LINK.md](../LINK.md), [../OBJ.md](../OBJ.md));
+and the content-addressed build coordinator (→
+[../BUILD_COORDINATOR.md](../BUILD_COORDINATOR.md)).
diff --git a/doc/plan/RELEASE.md b/doc/plan/RELEASE.md
@@ -15,7 +15,7 @@ the subsystem docs and roadmaps linked from `doc/DESIGN.md` and
against system libraries and platform frameworks.
- Optimization: `-O0` and `-O1` only. `-O2` is not a release feature.
- LTO / whole-program optimization, enabled explicitly and able to run at `-O1`.
-- Content-addressed build coordinator (`kit build` / `<kit/build.h>`), layered on
+- Content-addressed build coordinator (`kit build` / `<kit/build_coord.h>`), layered on
CAS and package/trust infrastructure.
- Runtime: target `libkit_rt.a`, freestanding headers/libc subset, compiler-rt
helpers, atomics, setjmp, and coroutines for the release support set.
@@ -140,27 +140,16 @@ landed). Remaining:
## Build coordinator
-- [ ] Bring the build-coordinator branch up to current main before merging; avoid
- losing current `build-exe`/`build-lib`/`build-obj`, RV32, and Wasm work.
-- [ ] Implement the public surface: `<kit/build.h>`, `KIT_BUILD_ENABLED`,
- `KIT_TOOL_BUILD_ENABLED`, and `kit build`.
-- [ ] Implement the internal modules from the build design: config/argv,
- definition parser, protocol, trace/deepset, store, remote, coordinator,
- resolver, runner, bundle import/export, and API composition.
-- [ ] Keep all build state hanging off explicit coordinator/store/client
- contexts; no global state.
-- [ ] Add hermetic tests for byte-stable config/argv/trace/deepset emission and
- fail-safe parsing.
+The coordinator implementation is on main; the durable spec is
+[../BUILD_COORDINATOR.md](../BUILD_COORDINATOR.md). Remaining:
+
- [ ] Add store crash-safety/fault-injection tests.
-- [ ] Add minimal-rebuild tests: no-op rebuild, source edit absorbed by a dep,
- config changes, recipe edits, absent file creation, materialize miss, and
- diamond deepset sharing.
-- [ ] Add concurrency tests for jobs limits, future dedup, cancellation, and
- cycle detection.
-- [ ] Add `kit build` CLI smoke tests with real recipes and release packaging
- integration.
-- [ ] Move shipped design details from `doc/plan/BUILD*.md` into durable design
- docs once implemented; leave only remaining roadmap items in `doc/plan/`.
+- [ ] Add broader scheduler/concurrency tests for jobs limits, future dedup, and
+ cancellation once the hosted `kit build` path grows a scheduler.
+- [ ] Add release packaging integration coverage for signed trace bundles and
+ object/trace remotes.
+- [ ] Decide whether v1 needs hermeticity enforcement or ships with the documented
+ recipe contract only.
## WebAssembly and WASI
diff --git a/include/kit/build_coord.h b/include/kit/build_coord.h
@@ -11,13 +11,14 @@
* Content-addressed build coordinator. A long-lived object that turns a build
* request (target T under configuration C) into a materialized output tree on
* disk, doing the least work necessary by caching every recipe result keyed by
- * the exact set of inputs that produced it. See doc/plan/BUILD.md.
+ * the exact set of inputs that produced it. See doc/BUILD_COORDINATOR.md.
*
* Layering. The coordinator is built entirely on the public kit surface: the
* content store (<kit/cas.h>) holds source bytes, output trees, config maps,
- * argv vectors, and trace bodies; signed packages (<kit/package.h>) carry
- * shared trace bundles; digests (<kit/hash.h>) key the mutable index. The only
- * mutable state the coordinator adds over the CAS is a per-target trace index.
+ * argv vectors, and deepset nodes; build/trace holds content-addressed trace
+ * claims; signed packages (<kit/package.h>) carry shared trace bundles;
+ * digests (<kit/hash.h>) key the mutable index. The only mutable state the
+ * coordinator adds over the CAS is a per-target trace index.
*
* Side effects via the host. As elsewhere in kit, the library sources no
* entropy and performs no I/O, process control, or concurrency itself: every
diff --git a/src/build/build.h b/src/build/build.h
@@ -9,7 +9,7 @@
/*
* Shared substrate for the content-addressed build coordinator
- * (`<kit/build_coord.h>`, `kit build`). See doc/plan/BUILD.md for the design.
+ * (`<kit/build_coord.h>`, `kit build`). See doc/BUILD_COORDINATOR.md.
*
* This layer sits *on top of* the public content store (`<kit/cas.h>`), the
* digest surface (`<kit/hash.h>`), and the signed-package machinery
diff --git a/src/build/resolve.h b/src/build/resolve.h
@@ -11,7 +11,7 @@
/*
* The resolution algorithm: resolve(T, cfg, chain) -> {output-tree, path,
- * leafset}, doing the least work necessary. Three phases (see doc/plan/BUILD.md
+ * leafset}, doing the least work necessary. Three phases (see doc/BUILD_COORDINATOR.md
* §Resolution algorithm):
*
* Phase 1 deep fast path - same config-id AND argv-id, and an all-clear
