trace.h (10289B)
1 #ifndef KIT_BUILD_TRACE_H 2 #define KIT_BUILD_TRACE_H 3 4 #include <kit/core.h> 5 #include <stddef.h> 6 #include <stdint.h> 7 8 #include "build.h" 9 10 /* 11 * Trace bodies and the per-target record: the immutable, content-addressed 12 * heart of the cache. Pure byte-level logic (emit / parse / id), no I/O — the 13 * store persists and loads these; resolution matches against them. 14 * 15 * Both trace kinds are strict, byte-stable, INI-style text (a version line, 16 * ordered scalar fields, then sorted sections). Unknown keys/sections, 17 * duplicate rows, and non-canonical ordering are PARSE ERRORS, and a parse 18 * error is treated as ABSENT, never as a match — fail safe. All ids are 19 * lowercase hex; config values, source bytes, and glob expansions are stored by 20 * hash, never inline, so a body's size is independent of its inputs' sizes. 21 * 22 * The variable-length sections hang off caller-provided, growable buffers (the 23 * DistTree pattern): no VLAs, and the api layer owns sizing. 24 */ 25 26 /* One source leaf: a file read directly, kept BY HASH (verified, never 27 * replayed). Sorted by path in a body. `absent` records that the path did NOT 28 * exist when read (a legitimate, cacheable observation): `blob` is unused and 29 * creating the file later busts the trace, mirroring config-consumed-while-unset. 30 * On the wire an absent leaf is "<path> -" (the blob field a lone '-'). */ 31 typedef struct BuildSourceLeaf { 32 char path[BUILD_PATH_MAX]; 33 uint8_t blob[BUILD_HASH_LEN]; 34 int absent; /* 1 => path was absent; blob ignored */ 35 } BuildSourceLeaf; 36 37 /* One glob leaf: a pattern and the BLAKE2b of its canonical (path, blob-id) 38 * listing. One row covers the existence AND content of the whole match set, so 39 * files read through a glob need no separate source rows. Sorted by pattern. */ 40 typedef struct BuildGlobLeaf { 41 char pattern[BUILD_PATTERN_MAX]; 42 uint8_t result_hash[BUILD_HASH_LEN]; 43 } BuildGlobLeaf; 44 45 /* One blob dependency leaf: a hash-pinned external object requested through 46 * `fetch`. URLs are transport hints only and are not cache identity; the blob id 47 * is the dependency. Sorted by blob id. */ 48 typedef struct BuildBlobLeaf { 49 uint8_t blob[BUILD_HASH_LEN]; 50 } BuildBlobLeaf; 51 52 /* One target-dep edge (shallow only): replays one `need`. Carries the explicit 53 * need overlay-id, the dep's effective argv-id, and the output tree-id it 54 * produced. Shallow replay recomputes the dep config as the current parent 55 * config overlaid by the map recovered through overlay-id, so the effective 56 * config-id is not stored: it is derived from the current request and carries 57 * no independent replay information. Sorted by 58 * (name, overlay-id, argv-id). */ 59 typedef struct BuildDepEdge { 60 char name[BUILD_TARGET_MAX]; 61 uint8_t overlay_id[BUILD_HASH_LEN]; 62 uint8_t argv_id[BUILD_HASH_LEN]; 63 uint8_t output_tree[BUILD_HASH_LEN]; 64 } BuildDepEdge; 65 66 /* One observed propagated config lookup. `present` records whether the key was 67 * set in the underlying propagated config, and is part of the cache match: an 68 * explicit value is not equivalent to an unset key returning the same default. 69 * `has_default` records whether the recipe supplied a default. `value_hash` is 70 * the returned value hash: actual value when present, default value when absent 71 * with a default, otherwise unused. `default_hash` is meaningful only when 72 * has_default. Sorted by key. */ 73 typedef struct BuildConfigLeaf { 74 char key[BUILD_KEY_MAX]; 75 uint8_t value_hash[BUILD_HASH_LEN]; 76 uint8_t default_hash[BUILD_HASH_LEN]; 77 int present; 78 int has_default; 79 } BuildConfigLeaf; 80 81 /* The shallow trace: direct inputs + direct deps, for fine-grained rechecking. 82 * Propagated config is represented only by the consumed observations below; 83 * `argv` is the target's serialized local-config blob id. */ 84 typedef struct BuildShallowTrace { 85 char target[BUILD_TARGET_MAX]; 86 uint8_t recipe[BUILD_HASH_LEN]; 87 uint8_t output[BUILD_HASH_LEN]; 88 uint8_t argv[BUILD_HASH_LEN]; 89 BuildConfigLeaf* configs; /* [config] section */ 90 size_t n_configs; 91 size_t cap_configs; 92 BuildSourceLeaf* sources; /* [source] section */ 93 size_t n_sources; 94 size_t cap_sources; 95 BuildGlobLeaf* globs; /* [glob] section */ 96 size_t n_globs; 97 size_t cap_globs; 98 BuildBlobLeaf* blobs; /* [blob] section */ 99 size_t n_blobs; 100 size_t cap_blobs; 101 BuildDepEdge* deps; /* [dep] section */ 102 size_t n_deps; 103 size_t cap_deps; 104 } BuildShallowTrace; 105 106 /* The deep trace: the argv binding to an output, plus a single pointer to the 107 * TRANSITIVE input closure, held structurally as a deepset DAG 108 * (below) rather than inlined. If the request's argv-id equals `argv`, and 109 * refreshing the `deepset` closure finds nothing moved (every config/source/ 110 * glob/blob leaf still matches AND every node's recipe-id still recomputes the 111 * same), determinism makes the output identical — no recipe runs. 112 * The deepset blob must be present to refresh; if absent (GC'd), the trace is 113 * treated as absent and resolution falls through (fail-safe). */ 114 typedef struct BuildDeepTrace { 115 char target[BUILD_TARGET_MAX]; 116 uint8_t recipe[BUILD_HASH_LEN]; 117 uint8_t output[BUILD_HASH_LEN]; 118 uint8_t argv[BUILD_HASH_LEN]; 119 uint8_t deepset[BUILD_HASH_LEN]; /* deep-set-id of the closure (a CAS blob) */ 120 } BuildDeepTrace; 121 122 /* One node of the transitive input-closure DAG — the structural form of the old 123 * flat leafset ("compact deep traces"). One node per target build: its DIRECT 124 * source/glob/blob leaves, its recipe-id, its target-scope projected config 125 * observations, and the deep-set-ids of its DIRECT deps. The fully-flattened 126 * source/glob/blob closure is the recursive union, NEVER materialized: a 127 * subtree reached through many parents is one node, stored once — a Merkle DAG 128 * that structurally shares like the CAS. Building a parent is "concat my direct 129 * leaves + projected config leaves + child ids, hash"; that IS the union. 130 * deep-set-id = BLAKE2b(canonical 131 * body), which is exactly a CAS blob id: a deepset is SELF-VERIFYING content, 132 * stored in cas/blob/ (trustless, fetchable, bundled as a plain blob), unlike a 133 * trace, which is a CLAIM in build/trace/. `target` is carried so refresh can 134 * recompute the node's recipe-id through the live definition — catching a dep 135 * repointed to a different-content recipe, while treating same-content as 136 * unchanged. Sorted: [config] by observation row, [source] by path, [glob] by 137 * pattern, [blob] by blob id, [child] by id. */ 138 typedef struct BuildDeepSet { 139 char target[BUILD_TARGET_MAX]; 140 uint8_t recipe[BUILD_HASH_LEN]; 141 BuildConfigLeaf* configs; /* this node's target-scope config observations */ 142 size_t n_configs; 143 size_t cap_configs; 144 BuildSourceLeaf* sources; /* this node's DIRECT source leaves */ 145 size_t n_sources; 146 size_t cap_sources; 147 BuildGlobLeaf* globs; /* this node's DIRECT glob leaves */ 148 size_t n_globs; 149 size_t cap_globs; 150 BuildBlobLeaf* blobs; /* this node's DIRECT blob dependencies */ 151 size_t n_blobs; 152 size_t cap_blobs; 153 uint8_t (*children)[BUILD_HASH_LEN]; /* direct deps' deep-set-ids, sorted */ 154 size_t n_children; 155 size_t cap_children; 156 } BuildDeepSet; 157 158 /* One row of the mutable target record. */ 159 typedef struct BuildRecordRow { 160 uint8_t kind; /* BuildTraceKind */ 161 uint8_t trace_id[BUILD_HASH_LEN]; 162 } BuildRecordRow; 163 164 /* The mutable per-target trace set: candidates newest-first, each kind capped 165 * at KIT_BUILD_RECORD_CAP. Points at trace bodies in build/trace/; a row may 166 * dangle (point at a GC'd body) and readers treat that as absent. */ 167 typedef struct BuildTargetRecord { 168 char target[BUILD_TARGET_MAX]; 169 BuildRecordRow* rows; 170 size_t n_rows; 171 size_t cap_rows; 172 } BuildTargetRecord; 173 174 /* Emit canonical bytes. Sorting/dedup/validation of the sections happens here; 175 * a malformed trace (e.g. a path that fails validation) returns BUILD_ERR with 176 * detail in err. */ 177 int build_shallow_emit(const BuildShallowTrace*, KitWriter* out, char* err, 178 size_t errcap); 179 int build_deep_emit(const BuildDeepTrace*, KitWriter* out, char* err, 180 size_t errcap); 181 int build_test_shallow_emit(const BuildShallowTrace*, KitWriter* out, char* err, 182 size_t errcap); 183 int build_test_deep_emit(const BuildDeepTrace*, KitWriter* out, char* err, 184 size_t errcap); 185 int build_deepset_emit(const BuildDeepSet*, KitWriter* out, char* err, 186 size_t errcap); 187 int build_record_emit(const BuildTargetRecord*, KitWriter* out, char* err, 188 size_t errcap); 189 190 /* Parse canonical bytes into a value (sections fill the caller-provided 191 * buffers). Non-canonical input is a parse error -> BUILD_ERR (treated as 192 * absent by callers). */ 193 int build_shallow_parse(const uint8_t* data, size_t len, BuildShallowTrace* out, 194 char* err, size_t errcap); 195 int build_deep_parse(const uint8_t* data, size_t len, BuildDeepTrace* out, 196 char* err, size_t errcap); 197 int build_test_shallow_parse(const uint8_t* data, size_t len, 198 BuildShallowTrace* out, char* err, 199 size_t errcap); 200 int build_test_deep_parse(const uint8_t* data, size_t len, BuildDeepTrace* out, 201 char* err, size_t errcap); 202 int build_deepset_parse(const uint8_t* data, size_t len, BuildDeepSet* out, 203 char* err, size_t errcap); 204 int build_record_parse(const uint8_t* data, size_t len, BuildTargetRecord* out, 205 char* err, size_t errcap); 206 207 /* trace-id = BLAKE2b(canonical trace body). The deep-set-id is the same hash 208 * over a deepset body — and equals the CAS blob id of those bytes, since a 209 * deepset is stored as an ordinary CAS blob (build_deepset_id is provided for 210 * symmetry; kit_blob_info over the emitted body yields the identical id). */ 211 void build_trace_id(const uint8_t* body, size_t len, 212 uint8_t out[BUILD_HASH_LEN]); 213 void build_deepset_id(const uint8_t* body, size_t len, 214 uint8_t out[BUILD_HASH_LEN]); 215 216 /* Prepend `row` to `rec` (newest-first), drop a duplicate of the same 217 * (kind, trace_id), and truncate that kind to KIT_BUILD_RECORD_CAP. Used by the 218 * record read-modify-write. */ 219 int build_record_prepend(BuildTargetRecord* rec, const BuildRecordRow* row); 220 221 #endif