kit

kit
git clone https://git.ryansepassi.com/git/kit.git
Log | Files | Refs | README

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, 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.

The kit repository also carries a coordinator-based build for the host kit binary itself as a Makefile alternative. From the repository root, build //:kit with an existing kit binary that has the build tool enabled:

build/kit build --store build/buildkit-store --root . --def BUILD.kit \
  --env KIT=./build/kit //:kit

The target graph is intentionally limited to the kit binary path, not the test suites: //:libkit builds libkit.a, //:driver builds the hosted driver objects, and //:kit links them into an output tree containing kit, libkit.a, and a regular-file support/rt runtime tree.

Historical implementation notes remain in plan/BUILD_INTERNALS.md and 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:

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 or @zlib//:lib. A target is a canonical label [@repo]//package:name; the repo and package path select the workspace root and BUILD.kit file that resolve the local 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. 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.
Exports Optional package-config-style metadata a recipe publishes by writing a canonical .kit/exports file inside its output tree. Dependents query it through ordinary need edges, so no trace shape changes.
External repo A hash-pinned workspace archive named by the root workspace manifest and addressed in labels as @name//pkg:target. It is fetched by blob/package id, verified, unpacked into the external-repo cache, then resolved like any workspace root.
Test target request A request to execute a target as a test (kit build test ...). It uses the same recipe protocol and dependency discovery as a build request, but returns a typed test result.
Test result tree The directory a test recipe produces, plus coordinator-injected stdout and stderr files, captured as a CAS tree (result-tree-id).
PASS-only test trace A test trace is a cacheable claim only when the recipe exits 0. Nonzero exits return FAIL results for inspection but write no reusable trace.
Base inputs The leaves of the dependency graph, dynamically requested by recipes: config values, source files, globs, and hash-pinned fetch blobs.
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: (argv) + a pointer to the transitive input closure (a deepset) → its output tree-id. Config matching is driven by the deepset's scope-projected config observations, not by whole-config equality.
Deepset One node of the transitive input-closure DAG (deep-set-id = BLAKE2b(canonical body)): a target's recipe-id + its direct config/source/glob/blob leaves + its children's deep-set-ids. 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 base-input kinds are exactly the dynamically-requested leaves: a recipe asks the coordinator for a config value, the bytes of a source file, the expansion of a glob, or a hash-pinned blob dependency, and each request is logged as a dependency so a later rebuild knows precisely what to re-check.

Build packages and recipe resolution

A workspace is rooted by KitBuildOptions.workspace_root (kit build --root, default .). Build definitions are package-local BUILD.kit files rooted at workspace-relative directories. A canonical in-workspace target label has the form //package:name:

The CLI and helper commands may accept Bazel-style shorthand, but the resolver normalizes before cache lookup or protocol logging: //pkg means //pkg:pkg, :name means //<current-package>:name, and bare name is accepted only where the command grammar unambiguously expects a local target name.

External targets add a repository prefix: @zlib//:lib, @platform//include:headers. Repository names are local to the workspace whose recipe issued the request; before a target enters trace bodies or target-record keys, the resolver expands it to a canonical repo instance selected by the live workspace manifest. The user-facing spelling remains @name//pkg:target, but resolution always knows which verified external workspace root that name denotes.

Package paths use forward slashes, are relative to the workspace root, and reject empty components, ., .., backslashes, and drive-prefix syntax. A package exists only when its directory contains a BUILD.kit file; labels do not search ancestor directories. A nested BUILD.kit starts a nested package, so files below that directory belong to the nested package for discovery and generated-target listing purposes.

Each BUILD.kit is strict canonical text. The v1 form remains the minimal exact mapping:

kit-build 1
[target server]
recipe recipes/app.sh
[target core]
recipe recipes/lib.sh

Target stanzas are sorted by local target name and unique within the package. Local names are non-empty tokens (no whitespace, slash, colon, or newlines). Recipe paths are resolved relative to the package directory unless explicitly prefixed with //, in which case they are workspace-relative; absolute paths, . / .. path elements, backslashes, and drive-prefix syntax are rejected.

The package file supplies recipe-resolution metadata only. It does not supply argv, propagated config, or dependency edges; those are request-time or dynamically discovered through the recipe protocol.

Target catalog

The resolver should grow beyond explicit exact targets without changing the coordinator's cache or recipe protocol. A package-local catalog may contain:

One possible canonical v2 shape:

kit-build 2

[default c.object]
recipe //recipes/c-object.sh

[default c.library]
recipe //recipes/c-library.sh

[target core]
type c.library

[targets c.object]
list src/*.c -> {stem}.o

[rule c-object]
match *.o
type c.object
list src/*.c -> {stem}.o

[redo-defaults]
enabled true
search . do
walk-parents true

Resolution of //pkg:name is deterministic:

  1. Load <root>/pkg/BUILD.kit.
  2. Prefer an exact [target name] stanza.
  3. Otherwise evaluate package-local [rule ...] matchers against name.
  4. Reject duplicate exact definitions or ambiguous same-priority rule matches.
  5. If no exact target or rule matched, try redo-style recipe-file discovery when enabled for the package.
  6. Determine the target type, if the matching target/rule/default supplied one.
  7. Select the recipe: target recipe override, then rule recipe override, then discovered redo-style recipe, then package/default recipe for the type, then built-in default recipe for the type. If no recipe is found, resolution fails.

Redo-style discovery is deterministic but not limited to the target package. It builds an ordered list of search roots, then probes a suffix list within each root. For target //lib/math:foo.test.o, with search . do and walk-parents true, search roots are:

lib/math/
lib/math/do/
lib/
lib/do/
./
do/

Within each root, the local target name foo.test.o probes:

foo.test.o.do
default.test.o.do
default.o.do
default.do

The first present executable file wins. search entries are workspace-relative or package-relative directories (. means the package/ancestor directory at the current walk step); they reject absolute paths, ., .. path elements other than the single . search token, backslashes, and drive-prefix syntax. walk-parents false restricts the search to the target package's roots. The root package is always the last ancestor when parent walking is enabled.

The selected recipe path is normalized to a workspace-relative path and still produces a normal recipe-id by hashing that file's bytes; the fact that it was selected by suffix discovery is not separately recorded in traces. Adding a more-specific default later changes only targets whose live resolution now selects different recipe bytes. A same-content replacement remains a cache no-op. Because first-hit wins, broad defaults should live high in the tree (or in a configured do/ root) and package-specific overrides should live near the package that needs them.

kit build list //pkg/... lists the package's exact targets plus generated targets from finite list projections. A rule without a finite listing projection, or a target resolved only by redo-style default discovery, may still resolve a direct request, but it is not discoverable unless a listing projection enumerates it. Listing descends into child packages by finding nested BUILD.kit files; a package's rules do not list targets inside nested packages, and redo defaults still need explicit listing projections to contribute discoverable targets.

BUILD.kit is therefore still useful alongside .do files: it is the package's index, not necessarily the place where every recipe body lives. It can declare many targets compactly through grouped target-list stanzas and projections, while the recipes themselves live in shared .do files:

[targets c.object]
list src/*.c -> {stem}.o

[targets c.test]
list test/*_test.c -> {stem}

[rule c-object]
match *.o
type c.object

Grouped target stanzas are pure catalog entries. They expand to local target names for listing, and those expanded names behave like generated exact targets for resolution: exact target metadata, then any recipe override, then matching rule, redo-style discovered recipe, and type default. The projection must be finite and deterministic: it may use package-relative globs, sorted by path, with template variables derived only from the matched path ({stem}, {base}, {dir}, {ext}).

For convenience, kit build list --scan-do //pkg/... may also enumerate targets implied by concrete .do filenames found in the redo search roots. This scan is best-effort discovery only: foo.o.do can list //pkg:foo.o, but default.o.do cannot know all possible .o names without a projection, so it is reported as a default provider rather than expanded into targets. The default plain kit build list should stay projection-based and deterministic; --scan-do is useful for humans auditing recipe coverage.

Relative labels are client ergonomics only. The wire protocol and trace bodies store canonical labels. Recipe helper commands may expand :local relative to $KIT_BUILD_PACKAGE; //other:target means the current repo's other package; and @repo//other:target selects an external repo through the current repo's workspace manifest before issuing a need request.

The live package definition is consulted when a target is resolved. The only catalog-derived input recorded in traces is the resolved recipe's content id (recipe-id), not a hash of the whole package file or workspace catalog. Changing a rule or exact target so the same canonical label selects different recipe bytes busts via recipe-id; editing unrelated targets, defaults, or listing metadata does not. Any target metadata that a default recipe uses to choose sources, flags, outputs, or dependencies must still be consumed through tracked inputs (source, glob, config-get, need, or a future equivalent); the resolver itself remains a client-side organization layer, not hidden cache identity.

Reusable language defaults should therefore be ordinary recipe libraries, not implicit catalog semantics. For example, a generic C .do recipe can implement the mechanics of compiling, archiving, linking, depfile logging, and profile flag merging, while project-local shell hooks compute the actual sources, target-level flags, dependency labels, and outputs by using source, glob, config-get, and need. The coordinator-provided target pieces (KIT_BUILD_REPO, KIT_BUILD_PACKAGE, KIT_BUILD_LOCAL) keep such shell rule libraries from reparsing labels themselves.

Workspace manifest, defaults, and external repositories

A workspace may also have a root WORKSPACE.kit manifest. BUILD.kit files describe packages; WORKSPACE.kit describes the workspace as a consumable unit, names external repositories, and carries workspace-wide build defaults. There is no separate build-config file in v1: settings that are stable enough to check in belong here, while per-invocation choices remain CLI --config values. The manifest is canonical text and optional for single-workspace builds:

kit-workspace 1
name myapp
version 0.1.0
def-name BUILD.kit

[config default]
target x86_64-linux
opt debug

[config release]
inherits default
opt release

[external zlib]
format tar.gz
archive <blob-id>
url https://example.org/zlib-1.3.1.tar.gz
strip-prefix zlib-1.3.1

[external platform]
format kpkg
archive <blob-id>
package <package-id>
url https://cache.example/platform-2026.kpkg

[config default] supplies propagated configuration entries for every top-level request in that workspace. Named config profiles are optional overlays selected by the CLI (--profile release) or by a future package policy. Profile inheritance is explicit and acyclic; later entries in the selected profile override inherited entries. Final top-level propagated config is:

WORKSPACE.kit [config default]
  ⊕ selected [config PROFILE] overlays
  ⊕ CLI --config / --env entries

The resulting map is hashed as the ordinary config-id; traces do not record that full map or which profile names produced it. Changing a workspace default therefore affects only targets whose recipes actually consume the changed keys, by the same config-observation rules as CLI config. def-name selects the package build-file basename for this workspace unless overridden by --def-name; it is not part of cache identity except through the recipe selected by live catalog resolution.

External repository entries are hash-pinned. archive is the BLAKE2b blob id of the exact archive bytes; url rows are untrusted fetch hints and are not cache identity. For format tar.gz, the coordinator fetches the archive blob if needed, verifies the blob id, unpacks it with strict path validation, applies strip-prefix if present, and treats the resulting directory as a read-only workspace root. For format kpkg, the archive blob is a signed kit package. The current hosted coordinator verifies it with the package layer's TOFU state, checks the optional package id when present, and materializes its default output tree as the external workspace root. Applications embedding the coordinator can impose a different acquisition policy before admitting an archive to their CAS.

External workspaces are cached under the build store by content, e.g. build/external/<repo-key>/, where <repo-key> is derived from (format, archive-id, package-id-or-empty, strip-prefix). Fetching or unpacking the same repo twice is idempotent. The unpacked tree is read-only to recipes; outputs still go to the recipe sandbox. Labels inside an external repo resolve against that repo's own BUILD.kit and optional WORKSPACE.kit. If an external recipe needs @foo//..., @foo is looked up in that external workspace's manifest, not in the root workspace, unless an explicit future repo-mapping feature says otherwise.

Changing a root WORKSPACE.kit external entry is not recorded as a whole-file input. Instead, live resolution of @name//pkg:target selects a different verified workspace root when the pinned archive/package id changes. Existing traces then refresh through that root: recipe ids and source/glob leaves are recomputed against the new external workspace. Same-content repins remain cache no-ops; different content busts through the existing recipe-id, source, glob, and dep-output checks.

The driver provides repository-management commands that update WORKSPACE.kit without hand-editing hashes:

kit build repo add NAME URL [--format tar.gz|kpkg] [--strip-prefix DIR]
kit build repo fetch NAME
kit build repo list

The current repo add command accepts a local path or file:// URL, hashes the archive, and records its blob id and URL in WORKSPACE.kit. It does not yet download remote URLs or derive the optional package-id. repo fetch currently checks that a configured name exists; actual verified fetching and materialization happen lazily when an @repo//... label is resolved. repo list prints the configured name, format, and archive id.

To make a workspace consumable by another workspace, package the source workspace as a deterministic kit package whose default output tree is the workspace root. The package must include WORKSPACE.kit, package BUILD.kit files, recipes, source files, and any files needed by package listing/resolution; it must exclude the build store, transient sandboxes, and VCS metadata unless explicitly included. A workspace package is then referenced from another workspace's WORKSPACE.kit as an external repo, normally with format kpkg. This reuses the existing kit pkg trust model: content bytes are hash-verified, and the package manifest is trusted only when its signer is trusted.

Published target exports

Targets may publish package-config-style metadata for dependents by placing a canonical exports file in their output tree:

$KIT_BUILD_OUT/.kit/exports

The file is strict canonical text. It maps variable names to ordered string vectors:

kit-build-exports 1
[var cflags]
-Iinclude
-DKIT_USE_ZLIB=1
[var libs]
-Llib
-lz

Variable names are sorted by byte order. Values inside one variable keep recipe order because flag order may be semantically meaningful. Values are raw text lines without NUL or newline bytes. Unknown sections, duplicate variable sections, or non-canonical ordering are malformed. Recipes may write this file directly or use a helper:

kit build export-set cflags -- -Iinclude -DKIT_USE_ZLIB=1
kit build export-set libs -- -Llib -lz

Exports are part of the output tree, so they are already covered by tree-id. A dependent that wants exports first performs a normal need of the provider target, then reads .kit/exports from the materialized output path. The helper commands are convenience wrappers around that rule:

kit build export-get TARGET VAR
kit build export-collect VAR TARGET...

export-get is equivalent to need TARGET followed by parsing the target's exports and printing the selected variable. export-collect repeats that for several targets in argument order. The dependency recorded in the trace is still only the ordinary target dep edge (dep, dep-overlay-id, dep-argv-id, output-tree-id): if the provider's exports change, its output tree changes, so the dependent's shallow dep-output comparison fails and the dependent recipe runs again. There is no separate exports trace section, no ambient package-config database, and no hidden cache identity.

This is intentionally conservative. If a provider changes an unrelated output file but preserves identical exports, dependents that queried exports still see the provider's tree-id change and may re-run. A later optimization could split exports into a named sub-tree or metadata id and record that id on dep edges, but v1 keeps the cache model simple and sound.

Configuration model

Configuration has two scopes, distinguished by visibility:

Serialized for replay, not just hashed. A need's explicit overlay map and local argv vector are persisted by value as canonical, content-addressed CAS blobs (overlay-id, argv-id). A shallow trace references those ids, and they are part of its reachable closure (GC-rooted and bundled with shared traces). Replay reconstructs the dep request as the target name plus the current parent's effective config overlaid by the recovered map, and the recovered argv. The parent's complete effective config is deliberately not persisted: its consumed values are verified through [config] observations, while the current request supplies inherited values for replay. Source files and globs are kept by hash because they are verified, 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 package catalog 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 package catalog, which the coordinator reads to resolve T. The only catalog-derived input recorded for T is its resolved recipe-id (a per-node scalar), refreshed by recomputing it through the live catalog — not a hash of the whole package file or target listing. 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, rule, or listing entry leaves catalog_resolve(T)'s recipe 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 catalog — 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 "are the config values this closure read from this request's config scope unchanged, and has any other 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 relevant 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-ids 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, need overlays, 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. Test records use a separate domain, BLAKE2b("kit build test target v1" ‖ target-name), so build output traces and test result traces cannot collide or satisfy each other.

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>
argv <argv-id>                 ; this target's local config (serialized vector blob)
[config]                       ; consumed propagated observations, sorted
opt present <value-hash> -
[source]                       ; sorted by path ("<path> -" marks an absent read)
src/main.c <blob-id>
[glob]                         ; sorted by pattern
src/*.c <glob-result-hash>
[blob]                         ; sorted by blob id
<blob-id>
[dep]                          ; sorted by (dep-name, dep-overlay-id, dep-argv-id) — each row replays one `need`
//lib:core <dep-overlay-id> <dep-argv-id> <dep-output-tree-id>

The recipe <recipe-id> scalar is the only catalog-derived input (recomputed through the live package catalog on refresh); the package file itself is not a source leaf, so editing an unrelated target, rule, or listing entry does not bust this trace.

Deep trace — the (argv) binding to an output, plus a single pointer to the transitive input closure (held as a deepset DAG, below), no [dep] and no inline per-key [config] section. Config observations live on deepset nodes so they can be checked with the correct propagated-config scope:

kit-build-deep 1
target //app:server
recipe <recipe-id>
output <output-tree-id>
argv <argv-id>                 ; local config (serialized vector blob)
deepset <deep-set-id>          ; the transitive input closure, as a deepset DAG (a CAS blob)

Test traces use the same sections and matching inputs, but distinct magics and a result scalar instead of output:

kit-build-test-shallow 1
target //pkg:unit
recipe <recipe-id>
result <result-tree-id>
argv <argv-id>
[config]
...
[source]
...
[glob]
...
[dep]
...

kit-build-test-deep 1
target //pkg:unit
recipe <recipe-id>
result <result-tree-id>
argv <argv-id>
deepset <deep-set-id>

Test deepsets reuse kit-build-deepset 1, because the input-closure semantics are unchanged. Test target records use the same kit-build-record 1 body shape but are stored under the test-record key domain described above.

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 catalog-derived input)
[config]                       ; this node's scope-projected propagated config observations
opt <present|unset/default...> <value-hash-or->
[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>
[blob]                         ; this node's DIRECT blob dependencies, sorted by blob id
<blob-id>
[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.

Why the deep trace needs argv + the deepset closure. At Phase 1 query time the coordinator has only the requested target's effective propagated config and local argv; it has not re-run the recipe, so it cannot recompute dynamic need overlays. A deep match is valid when the request's argv-id equals the recorded argv, and refreshing the deepset finds nothing moved: every source/glob/blob leaf still matches the live workspace, every node's recipe-id still recomputes the same through the live definition, and every scope-projected config observation still matches the current root config. Then every root-scope value that could perturb a recipe branch or downstream overlay is unchanged. Values introduced by recorded need overlays are not compared to the parent's root config; their stability follows from the unchanged recipe code and unchanged inputs that generated those overlays. By determinism, every effective downstream config is identical where it matters, so the output is identical.

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, need-overlay maps, argv vectors, 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 needs of the same (T, config-id, argv-id) await one resolution rather than racing (see 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 argv-id plus the deepset's scope-projected config observations, while 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 argv, did any observed input move?) ---
  for D in deep_traces(T), newest-first:
     if D.argv == argv.id:
        node = deepset_load(D.deepset)                  # load DAG from CAS; absent => skip (fail-safe)
        if node and refresh(node, cfg) all match live:  # config observations + rehash/reglob + recipe-id
           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
     if any config observation in S differs from cfg:                  continue
     if any direct source/glob/blob leaf of S changed:               continue
     ok = true ; child_nodes = []
     for (dep, overlay_id, dep_argv_id, recorded_tree) in S.deps:     # may run in parallel
        dep_cfg = overlay(cfg, config_by_id(overlay_id))              # replay the need overlay
        r = resolve(dep, dep_cfg, argv_by_id(dep_argv_id), chain')
        if r.output != recorded_tree: ok = false; break
        child_nodes.push(r.leafset)
     if ok:
        node = union(direct{recipe_id, config/source/glob/blob leaves} of S, S.deps, child_nodes)
        write_deep_trace(T, 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:

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.

Diagnostic resolution trace

Tests sometimes need to assert which target took which resolution path, not just aggregate counters. A diagnostic trace mode should emit a stable, line-oriented event stream describing resolution decisions. It is not cache identity, not bundled, and not intended for normal quiet builds; it is an assertion/debug surface for humans and tests.

The implemented target-level events are:

resolve-start action=<build|test> target=<T> root=<0|1> config=<config-id> argv=<argv-id>
deep-candidate target=<T> trace=<trace-id>
deep-miss target=<T> reason=<no-match|malformed>
deep-hit target=<T> output=<tree-id>
shallow-candidate target=<T> trace=<trace-id>
shallow-miss target=<T> reason=<no-match>
shallow-hit target=<T> output=<tree-id>
recipe-run target=<T>

When implementing the scope-projected deep config logic, extend the trace so deep config checks make scope projection visible:

deep-config target=<T> key=<K> scope=root result=<match|mismatch>
deep-config target=<T> child=<U> key=<K> scope=overlay-shielded overlay=<overlay-config-id>

This lets tests distinguish "the requested target deep-hit" from "a child deep-hit while the requested target shallow-hit", which aggregate deep_hits/shallow_hits cannot express.

Expected event shapes for the config-scope cases:

Test caching

kit build test is first-class test execution in the coordinator, not a separate task runner. A test target uses the same package catalog, recipe protocol, dependency discovery, config/argv identity, deepset refresh, materialization, remotes, and verify mode as kit build; the difference is the result type and record namespace.

Test execution policy:

Deep and shallow matching are identical to build matching, except that only test traces are considered and hits materialize a result tree. A shallow test hit may skip the test recipe after a dependency's inputs changed if every recorded dep still resolves to the same output tree. Verify mode audits cached PASS claims by re-running the test and comparing the fresh result tree with the cached result-tree-id; a FAIL or different result tree reports a verify mismatch.

Task-runner policy (test selection expressions, sharding, retries, report aggregation) is deliberately deferred. Target discovery for tests uses the same package catalog listing as build targets, but the v1 execution surface is one target request at a time: kit build test ... TARGET [-- ARG...].

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, KIT_BUILD_REPO=<repo>, KIT_BUILD_PACKAGE=<package>,
     KIT_BUILD_LOCAL=<local-name> } + 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 current-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 the serialized argv vector (argv.id) and each need-overlay map into the CAS
     node = union(direct{recipe_id, config/source/glob/blob/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, config observations,
                         direct leaves, dep edges with overlay-ids and argv-ids, output)
     write_deep_trace   (T, 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-awaits 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.

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)
fetch <blob-id> <url>... the verified blob-id + a local CAS path blob dep: blob-id
need <target> [k=v…] [env…] [argv…] the dep's output tree-id + a path (blocks) target dep edge: (dep, dep-overlay-id, dep-argv-id, output-tree-id)
need-submit <target> [k=v…] [env…] [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-overlay-id, dep-argv-id, output-tree-id)

The shell helper also provides depfile [--lines] FILE, which is not a separate wire command. It parses Make/GCC-style depfiles (or one path per line with --lines) and submits every prerequisite through source, so each prerequisite is logged as an ordinary source dependency.

CLI

Build execution:

kit build [--store DIR] [--root DIR] [--def FILE]
          [--profile NAME] [--config K=V|env.NAME]... [--env NAME[=V]]...
          [--verify] [--stats] [--trace] TARGET [-- ARG...]
kit build [--root DIR] [--def FILE] list [--scan-do] [//PACKAGE[/...]]
kit build [--root DIR] repo {add|fetch|list} ...
kit build [--root DIR] workspace package [--format tar.gz] -o OUT

Test execution:

kit build test [--store DIR] [--root DIR] [--def FILE]
               [--profile NAME] [--config K=V|env.NAME]... [--env NAME[=V]]...
               [--verify] [--stats] [--trace] TARGET [-- ARG...]

kit build prints <output-tree-hex> <path> and exits 0 on success. kit build test prints <status> <result-tree-hex> <path>, where status is PASS or FAIL; it exits 0 for PASS, 1 for FAIL, and 2 for bad CLI usage. Infrastructure errors also exit nonzero and print diagnostics on stderr. --stats prints cumulative coordinator counters, including test_runs, test_cache_hits, and test_failures, to stderr. --trace prints target-level resolution decisions to stderr, using the diagnostic resolution trace event names. --def (also accepted as --def-name) selects the package build-file basename, overriding WORKSPACE.kit's def-name; when neither is present it defaults to BUILD.kit. It must be a single filename, not a path, so package lookup remains <workspace>/<package>/<def-name>.

workspace package currently emits only tar.gz through a hosted system tar. Use kit pkg create when a signed .kpkg or portable signed package is required.

Recipe-side shell helper commands are available as kit build <verb> ... inside a running recipe ($KIT_BUILD_SOCK set). kit build --client <verb> ... selects the same mode explicitly, but still requires the coordinator environment established for a running recipe:

kit build config-get [--default VALUE] KEY
kit build source [--optional] [--format path|id|id-path] PATH
kit build fetch [--format path|id|id-path] BLOB URL...
kit build depfile [--lines] FILE
kit build glob PATTERN
kit build export-set VAR -- VALUE...
kit build export-get TARGET VAR
kit build export-collect VAR TARGET...
kit build need [--format path|id|id-path]
               [--config K=V|env.NAME]... [--env NAME[=V]]...
               TARGET [-- ARG...]
kit build need-submit [--config K=V|env.NAME]... [--env NAME[=V]]...
                      TARGET [-- ARG...]
kit build need-await [--format path|id|id-path] TOKEN

The default helper output is the readable path where a path exists. --format id prints the blob/tree id, and --format id-path prints both as <hex> <path>. config-get --default VALUE exits 0 and prints VALUE when a key is unset. source --optional exits 0 with no output when the source is absent, while still recording the absent-source dependency.

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:

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

Cache correctness is exactly the assumption output = f(declared inputs), deterministically.

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 argv a0 and refreshes the root-scope opt observation, 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 loads the deep trace because argv a0 still matches, then fails while refreshing the root-scope opt observation. 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