commit 2fbb8b5957a5c3cd1b7ad6f178fec2e4c6fff6ae
parent c24b9e0300ad0eb206cd9dec61b78ad83e49800f
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Thu, 18 Jun 2026 07:42:46 -0700
buildcoord: memoize inputs and support globstar
Diffstat:
3 files changed, 238 insertions(+), 17 deletions(-)
diff --git a/src/build/coord.c b/src/build/coord.c
@@ -25,6 +25,21 @@ struct BuildPulledSet {
struct BuildPulledSet* next;
};
+struct BuildSourceMemo {
+ char path[BUILD_PATH_MAX];
+ uint8_t blob[BUILD_HASH_LEN];
+ int present;
+ struct BuildSourceMemo* next;
+};
+
+struct BuildGlobMemo {
+ char pattern[BUILD_PATTERN_MAX];
+ uint8_t result_hash[BUILD_HASH_LEN];
+ BuildPathBlob* entries;
+ size_t n_entries;
+ struct BuildGlobMemo* next;
+};
+
typedef struct BuildDeepSetMemo {
BuildLeafSet leaf;
BuildSourceLeaf* sources;
@@ -66,6 +81,13 @@ static int path_join2(char* out, size_t cap, const char* a, const char* b) {
return BUILD_OK;
}
+static int slice_copy(char* out, size_t cap, KitSlice s) {
+ if (!out || cap == 0u || !s.s || s.len + 1u > cap) return BUILD_ERR;
+ memcpy(out, s.s, s.len);
+ out[s.len] = '\0';
+ return BUILD_OK;
+}
+
static int rel_path_safe(KitSlice s) {
size_t i, start = 0;
if (!s.s || s.len == 0u || s.len >= BUILD_PATH_MAX) return 0;
@@ -125,20 +147,34 @@ static int glob_match_range(const char* pat, size_t pn, const char* text,
return pi == pn;
}
+static int glob_segment_double_star(const char* pat, size_t start,
+ size_t end) {
+ return end == start + 2u && pat[start] == '*' && pat[start + 1u] == '*';
+}
+
+static int glob_match_segments(const char* pat, size_t pn, size_t pp,
+ const char* text, size_t tn, size_t tp) {
+ size_t pe = pp, te = tp;
+ if (pp == pn) return tp == tn;
+ while (pe < pn && pat[pe] != '/') ++pe;
+ if (glob_segment_double_star(pat, pp, pe)) {
+ size_t next_pp = pe < pn ? pe + 1u : pn;
+ if (glob_match_segments(pat, pn, next_pp, text, tn, tp)) return 1;
+ if (tp == tn) return 0;
+ while (te < tn && text[te] != '/') ++te;
+ return glob_match_segments(pat, pn, pp, text, tn,
+ te < tn ? te + 1u : tn);
+ }
+ if (tp == tn) return 0;
+ while (te < tn && text[te] != '/') ++te;
+ if (!glob_match_range(pat + pp, pe - pp, text + tp, te - tp)) return 0;
+ if (pe == pn || te == tn) return pe == pn && te == tn;
+ return glob_match_segments(pat, pn, pe + 1u, text, tn, te + 1u);
+}
+
static int glob_match_path(KitSlice pattern, const char* path) {
- size_t pp = 0, tp = 0, tlen;
if (!pattern.s || !path) return 0;
- tlen = strlen(path);
- for (;;) {
- size_t pe = pp, te = tp;
- while (pe < pattern.len && pattern.s[pe] != '/') ++pe;
- while (te < tlen && path[te] != '/') ++te;
- if (!glob_match_range(pattern.s + pp, pe - pp, path + tp, te - tp))
- return 0;
- if (pe == pattern.len || te == tlen) return pe == pattern.len && te == tlen;
- pp = pe + 1u;
- tp = te + 1u;
- }
+ return glob_match_segments(pattern.s, pattern.len, 0, path, strlen(path), 0);
}
static int path_blob_cmp_qsort(const void* a, const void* b) {
@@ -255,6 +291,33 @@ static void free_pulled(KitBuildCoordinator* c) {
c->pulled = NULL;
}
+static void free_sources(KitBuildCoordinator* c) {
+ BuildSourceMemo* n;
+ if (!c || !c->ctx || !c->ctx->heap) return;
+ n = c->sources;
+ while (n) {
+ BuildSourceMemo* next = n->next;
+ c->ctx->heap->free(c->ctx->heap, n, sizeof *n);
+ n = next;
+ }
+ c->sources = NULL;
+}
+
+static void free_globs(KitBuildCoordinator* c) {
+ BuildGlobMemo* n;
+ if (!c || !c->ctx || !c->ctx->heap) return;
+ n = c->globs;
+ while (n) {
+ BuildGlobMemo* next = n->next;
+ if (n->entries)
+ c->ctx->heap->free(c->ctx->heap, n->entries,
+ n->n_entries * sizeof *n->entries);
+ c->ctx->heap->free(c->ctx->heap, n, sizeof *n);
+ n = next;
+ }
+ c->globs = NULL;
+}
+
void build_coord_stat_bump(KitBuildCoordinator* c, BuildStatField f) {
if (!c) return;
switch (f) {
@@ -377,6 +440,8 @@ void build_coord_close(KitBuildCoordinator* c) {
h = c->ctx->heap;
free_targets(c);
free_pulled(c);
+ free_sources(c);
+ free_globs(c);
free_deepsets(c);
release_defn(c);
if (c->defn.targets)
@@ -389,31 +454,58 @@ void build_coord_close(KitBuildCoordinator* c) {
int build_coord_source_hash(KitBuildCoordinator* c, KitSlice path,
uint8_t out_blob[BUILD_HASH_LEN], int* present) {
char full[BUILD_PATH_MAX];
+ char rel[BUILD_PATH_MAX];
KitFileData fd;
KitBlobInfo info;
+ BuildSourceMemo* memo;
+ BuildSourceMemo* fresh = NULL;
if (!c || !out_blob || !present || !rel_path_safe(path)) return BUILD_ERR;
+ if (slice_copy(rel, sizeof rel, path) != BUILD_OK) return BUILD_ERR;
+ for (memo = c->sources; memo; memo = memo->next) {
+ if (strcmp(memo->path, rel) == 0) {
+ memcpy(out_blob, memo->blob, BUILD_HASH_LEN);
+ *present = memo->present;
+ return BUILD_OK;
+ }
+ }
+ fresh = (BuildSourceMemo*)c->ctx->heap->alloc(c->ctx->heap, sizeof *fresh,
+ _Alignof(BuildSourceMemo));
+ if (!fresh) return BUILD_ERR;
+ memset(fresh, 0, sizeof *fresh);
+ snprintf(fresh->path, sizeof fresh->path, "%s", rel);
*present = 0;
- if (path_join2(full, sizeof full, c->workspace_root, path.s) !=
- BUILD_OK)
- return BUILD_ERR;
+ if (path_join2(full, sizeof full, c->workspace_root, rel) != BUILD_OK)
+ goto err;
fd.data = NULL;
fd.size = 0;
fd.token = NULL;
if (c->host.cas_host->file_io->read_all(c->host.cas_host->file_io->user, full,
&fd) != KIT_OK) {
memset(out_blob, 0, BUILD_HASH_LEN);
+ memset(fresh->blob, 0, BUILD_HASH_LEN);
+ fresh->present = 0;
+ fresh->next = c->sources;
+ c->sources = fresh;
return BUILD_OK;
}
if (kit_cas_add_blob(c->cas, fd.data, fd.size, &info) != KIT_OK) {
if (c->host.cas_host->file_io->release)
c->host.cas_host->file_io->release(c->host.cas_host->file_io->user, &fd);
- return BUILD_ERR;
+ goto err;
}
memcpy(out_blob, info.id, BUILD_HASH_LEN);
+ memcpy(fresh->blob, info.id, BUILD_HASH_LEN);
*present = 1;
+ fresh->present = 1;
if (c->host.cas_host->file_io->release)
c->host.cas_host->file_io->release(c->host.cas_host->file_io->user, &fd);
+ fresh->next = c->sources;
+ c->sources = fresh;
return BUILD_OK;
+
+err:
+ if (fresh) c->ctx->heap->free(c->ctx->heap, fresh, sizeof *fresh);
+ return BUILD_ERR;
}
int build_coord_glob(KitBuildCoordinator* c, KitSlice pattern,
@@ -421,9 +513,24 @@ int build_coord_glob(KitBuildCoordinator* c, KitSlice pattern,
BuildCoordGlobFn cb, void* cb_user) {
BuildGlobExpand g;
size_t i, out_n = 0;
+ char pat[BUILD_PATTERN_MAX];
+ BuildGlobMemo* memo;
+ BuildGlobMemo* fresh = NULL;
if (!c || !out_result_hash || !glob_pattern_safe(pattern) ||
!c->host.cas_host || !c->host.cas_host->walk_regular_files)
return BUILD_ERR;
+ if (slice_copy(pat, sizeof pat, pattern) != BUILD_OK) return BUILD_ERR;
+ for (memo = c->globs; memo; memo = memo->next) {
+ if (strcmp(memo->pattern, pat) == 0) {
+ memcpy(out_result_hash, memo->result_hash, BUILD_HASH_LEN);
+ if (cb) {
+ for (i = 0; i < memo->n_entries; ++i) {
+ if (cb(cb_user, memo->entries[i].path, memo->entries[i].blob)) break;
+ }
+ }
+ return BUILD_OK;
+ }
+ }
memset(&g, 0, sizeof g);
g.c = c;
g.pattern = pattern;
@@ -445,6 +552,22 @@ int build_coord_glob(KitBuildCoordinator* c, KitSlice pattern,
if (build_glob_result_hash(c->ctx->heap, g.entries, out_n,
out_result_hash) != BUILD_OK)
goto err;
+ fresh = (BuildGlobMemo*)c->ctx->heap->alloc(c->ctx->heap, sizeof *fresh,
+ _Alignof(BuildGlobMemo));
+ if (!fresh) goto err;
+ memset(fresh, 0, sizeof *fresh);
+ snprintf(fresh->pattern, sizeof fresh->pattern, "%s", pat);
+ memcpy(fresh->result_hash, out_result_hash, BUILD_HASH_LEN);
+ if (out_n) {
+ fresh->entries = (BuildPathBlob*)c->ctx->heap->alloc(
+ c->ctx->heap, out_n * sizeof *fresh->entries, _Alignof(BuildPathBlob));
+ if (!fresh->entries) goto err;
+ memcpy(fresh->entries, g.entries, out_n * sizeof *fresh->entries);
+ fresh->n_entries = out_n;
+ }
+ fresh->next = c->globs;
+ c->globs = fresh;
+ fresh = NULL;
if (cb) {
for (i = 0; i < out_n; ++i) {
if (cb(cb_user, g.entries[i].path, g.entries[i].blob)) break;
@@ -455,6 +578,12 @@ int build_coord_glob(KitBuildCoordinator* c, KitSlice pattern,
return BUILD_OK;
err:
+ if (fresh) {
+ if (fresh->entries)
+ c->ctx->heap->free(c->ctx->heap, fresh->entries,
+ fresh->n_entries * sizeof *fresh->entries);
+ c->ctx->heap->free(c->ctx->heap, fresh, sizeof *fresh);
+ }
if (g.entries)
c->ctx->heap->free(c->ctx->heap, g.entries, g.cap * sizeof *g.entries);
return BUILD_ERR;
diff --git a/src/build/runner.c b/src/build/runner.c
@@ -48,8 +48,19 @@ static int append_config_key(BuildDepLog* log, KitSlice key) {
static int append_source(BuildDepLog* log, KitSlice path,
const uint8_t blob[BUILD_HASH_LEN], int present) {
BuildSourceLeaf* row;
+ size_t i;
if (!log || !path.s || path.len == 0u || path.len >= BUILD_PATH_MAX)
return BUILD_ERR;
+ for (i = 0; i < log->n_sources; ++i) {
+ row = &log->sources[i];
+ if (strlen(row->path) == path.len &&
+ memcmp(row->path, path.s, path.len) == 0) {
+ int absent = present ? 0 : 1;
+ if (row->absent != absent) return BUILD_ERR;
+ if (!row->absent && !build_id_eq(row->blob, blob)) return BUILD_ERR;
+ return BUILD_OK;
+ }
+ }
if (log->n_sources >= log->cap_sources) return BUILD_ERR;
row = &log->sources[log->n_sources++];
memcpy(row->path, path.s, path.len);
@@ -65,9 +76,18 @@ static int append_source(BuildDepLog* log, KitSlice path,
static int append_glob(BuildDepLog* log, KitSlice pattern,
const uint8_t result_hash[BUILD_HASH_LEN]) {
BuildGlobLeaf* row;
+ size_t i;
if (!log || !pattern.s || pattern.len == 0u ||
pattern.len >= BUILD_PATTERN_MAX || !result_hash)
return BUILD_ERR;
+ for (i = 0; i < log->n_globs; ++i) {
+ row = &log->globs[i];
+ if (strlen(row->pattern) == pattern.len &&
+ memcmp(row->pattern, pattern.s, pattern.len) == 0) {
+ if (!build_id_eq(row->result_hash, result_hash)) return BUILD_ERR;
+ return BUILD_OK;
+ }
+ }
if (log->n_globs >= log->cap_globs) return BUILD_ERR;
row = &log->globs[log->n_globs++];
memcpy(row->pattern, pattern.s, pattern.len);
diff --git a/test/buildcoord/run.sh b/test/buildcoord/run.sh
@@ -22,7 +22,7 @@ kit_report_init
ws="$work/ws"
store="$work/store"
-mkdir -p "$ws/recipes" "$ws/src/globset" "$store"
+mkdir -p "$ws/recipes" "$ws/src/globset" "$ws/src/tree/nested/deeper" "$store"
cat > "$ws/BUILD.kit" <<'EOF'
kit-build 1
@@ -50,6 +50,8 @@ recipe recipes/env_probe.sh
recipe recipes/fail.sh
[target //globset:probe]
recipe recipes/globset.sh
+[target //globstar:probe]
+recipe recipes/globstar.sh
[target //lib:data]
recipe recipes/lib.sh
[target //material:probe]
@@ -60,6 +62,8 @@ recipe recipes/needargv.sh
recipe recipes/nondet.sh
[target //recipe:stamp]
recipe recipes/recipe.sh
+[target //repeat:probe]
+recipe recipes/repeat.sh
[target //scope:leaf]
recipe recipes/scope_leaf.sh
[target //scope:parent-inherit]
@@ -88,6 +92,15 @@ EOF
cat > "$ws/src/globset/one.txt" <<'EOF'
one
EOF
+cat > "$ws/src/tree/root.txt" <<'EOF'
+root
+EOF
+cat > "$ws/src/tree/nested/mid.txt" <<'EOF'
+mid
+EOF
+cat > "$ws/src/tree/nested/deeper/leaf.txt" <<'EOF'
+leaf
+EOF
cat > "$ws/recipes/lib.sh" <<'EOF'
#!/bin/sh
@@ -224,6 +237,15 @@ for p in $("$KIT" build glob 'src/globset/*.txt'); do
done > "$KIT_BUILD_OUT/files.txt"
EOF
+cat > "$ws/recipes/globstar.sh" <<'EOF'
+#!/bin/sh
+set -eu
+mkdir -p "$KIT_BUILD_OUT"
+"$KIT" build glob 'src/tree/**/*.txt' > "$KIT_BUILD_OUT/all.txt"
+"$KIT" build glob 'src/tree/**/leaf.txt' > "$KIT_BUILD_OUT/leaf.txt"
+"$KIT" build glob 'src/tree/**/root.txt' > "$KIT_BUILD_OUT/root.txt"
+EOF
+
cat > "$ws/recipes/needargv.sh" <<'EOF'
#!/bin/sh
set -eu
@@ -239,6 +261,18 @@ mkdir -p "$KIT_BUILD_OUT"
printf 'recipe:v1\n' > "$KIT_BUILD_OUT/stamp.txt"
EOF
+cat > "$ws/recipes/repeat.sh" <<'EOF'
+#!/bin/sh
+set -eu
+mkdir -p "$KIT_BUILD_OUT"
+p1=$("$KIT" build source src/a.txt)
+p2=$("$KIT" build source src/a.txt)
+cat "$p1" > "$KIT_BUILD_OUT/source1.txt"
+cat "$p2" > "$KIT_BUILD_OUT/source2.txt"
+"$KIT" build glob 'src/*.txt' > "$KIT_BUILD_OUT/glob1.txt"
+"$KIT" build glob 'src/*.txt' > "$KIT_BUILD_OUT/glob2.txt"
+EOF
+
cat > "$ws/recipes/material.sh" <<'EOF'
#!/bin/sh
set -eu
@@ -480,6 +514,24 @@ else
not_ok "buildcoord-recipe-edit-new-tree" "$work/recipe-tree.diag"
fi
+build_assert_ok buildcoord-repeat-inputs-cold --stats //repeat:probe
+contains "buildcoord-repeat-inputs-cold-run" \
+ "$work/buildcoord-repeat-inputs-cold.err" "recipes_run=1"
+repeat_path=$(tree_path_from "$work/buildcoord-repeat-inputs-cold.out")
+contains "buildcoord-repeat-source-first" "$repeat_path/source1.txt" "alpha"
+contains "buildcoord-repeat-source-second" "$repeat_path/source2.txt" "alpha"
+if cmp -s "$repeat_path/glob1.txt" "$repeat_path/glob2.txt"; then
+ ok "buildcoord-repeat-glob-stable"
+else
+ printf 'glob outputs differ\n' > "$work/repeat-glob.diag"
+ not_ok "buildcoord-repeat-glob-stable" "$work/repeat-glob.diag"
+fi
+build_assert_ok buildcoord-repeat-inputs-deep --stats //repeat:probe
+contains "buildcoord-repeat-inputs-deep-hit" \
+ "$work/buildcoord-repeat-inputs-deep.err" "deep_hits=1"
+contains "buildcoord-repeat-inputs-deep-no-run" \
+ "$work/buildcoord-repeat-inputs-deep.err" "recipes_run=0"
+
build_assert_ok buildcoord-stats-cold --stats //stable:parent
contains "buildcoord-stats-cold-recipes" "$work/buildcoord-stats-cold.err" \
"recipes_run=2"
@@ -697,6 +749,26 @@ globset_remove_path=$(tree_path_from "$work/buildcoord-globset-remove.out")
contains "buildcoord-globset-remove-output" "$globset_remove_path/files.txt" \
"two"
+build_assert_ok buildcoord-globstar-cold --stats //globstar:probe
+contains "buildcoord-globstar-cold-run" "$work/buildcoord-globstar-cold.err" \
+ "recipes_run=1"
+globstar_path=$(tree_path_from "$work/buildcoord-globstar-cold.out")
+contains "buildcoord-globstar-root" "$globstar_path/all.txt" \
+ "src/tree/root.txt"
+contains "buildcoord-globstar-mid" "$globstar_path/all.txt" \
+ "src/tree/nested/mid.txt"
+contains "buildcoord-globstar-leaf" "$globstar_path/all.txt" \
+ "src/tree/nested/deeper/leaf.txt"
+contains "buildcoord-globstar-specific-leaf" "$globstar_path/leaf.txt" \
+ "src/tree/nested/deeper/leaf.txt"
+contains "buildcoord-globstar-zero-depth" "$globstar_path/root.txt" \
+ "src/tree/root.txt"
+build_assert_ok buildcoord-globstar-deep --stats //globstar:probe
+contains "buildcoord-globstar-deep-hit" "$work/buildcoord-globstar-deep.err" \
+ "deep_hits=1"
+contains "buildcoord-globstar-deep-no-run" "$work/buildcoord-globstar-deep.err" \
+ "recipes_run=0"
+
run_fail "buildcoord-failure-first-fails" \
"$KIT" build --store "$store" --root "$ws" --def BUILD.kit \
--config "env.KIT=$KIT" //fail:probe
