Skip to content

Commit aa6df6b

Browse files
Ahmed MohammedMartin Vogel
authored andcommitted
fix(extraction): replace fixed traversal stacks with growable arena-allocated stacks (#217)
AST traversal functions used fixed-size TSNode stack[] arrays. When the DFS stack filled up, the child-push loop exited silently, dropping entire subtrees without warning (e.g. 600 TS imports → 511, 130 Express routes capped at 512). Reported in #199; also addresses #213 (large TypeScript files producing zero nodes from stack exhaustion) and #215 (SEGV in template calls from stack overflow). Adds ts_node_stack.h — a growable stack backed by the existing arena allocator. Initial capacity matches previous fixed caps so small files allocate no extra memory; doubles on overflow instead of truncating. Old blocks are abandoned in the arena and freed on arena_destroy at the end of file extraction (no realloc, no mixed lifetimes). Applied to all 14 TSNode fixed stacks across 9 extraction files (extract_calls, extract_channels, extract_defs, extract_env_accesses, extract_imports, extract_semantic, extract_type_assigns, extract_type_refs, extract_usages). walk_defs (uses walk_defs_frame_t, different struct type) deliberately left as-is. 7 regression tests in tests/test_stack_overflow.c cover TS imports >512, JS/Python calls >512, Go calls >1024, Express routes >150, deeply nested calls, and YAML vars >256. Cherry-picked from #217 with merge-conflict resolution against post-#206/#207 main: - Makefile.cbm: keep TEST_STACK_OVERFLOW_SRCS plus main's new TEST_ZSTD_SRCS / TEST_ARTIFACT_SRCS. - extract_channels.c: keep main's scan_string_consts_js name (main also added scan_string_consts_python after the PR was opened); declare CHAN_STACK_CAP in the enum block. - test_stack_overflow.c: replace sprintf with snprintf using the actual remaining buffer size, since macOS clang rejects sprintf and naive snprintf with sizeof(p) on a char* fails -Wformat-truncation. Closes #199, #213, #215. Closes #217.
1 parent a20d551 commit aa6df6b

13 files changed

Lines changed: 503 additions & 127 deletions

‎Makefile.cbm‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -326,7 +326,9 @@ TEST_YAML_SRCS = tests/test_yaml.c
326326

327327
TEST_SIMHASH_SRCS = tests/test_simhash.c
328328

329-
ALL_TEST_SRCS = $(TEST_FOUNDATION_SRCS) $(TEST_EXTRACTION_SRCS) $(TEST_STORE_SRCS) $(TEST_CYPHER_SRCS) $(TEST_MCP_SRCS) $(TEST_DISCOVER_SRCS) $(TEST_GRAPH_BUFFER_SRCS) $(TEST_PIPELINE_SRCS) $(TEST_WATCHER_SRCS) $(TEST_LZ4_SRCS) $(TEST_ZSTD_SRCS) $(TEST_ARTIFACT_SRCS) $(TEST_SQLITE_WRITER_SRCS) $(TEST_GO_LSP_SRCS) $(TEST_C_LSP_SRCS) $(TEST_TRACES_SRCS) $(TEST_CLI_SRCS) $(TEST_MEM_SRCS) $(TEST_UI_SRCS) $(TEST_SECURITY_SRCS) $(TEST_YAML_SRCS) $(TEST_SIMHASH_SRCS) $(TEST_INTEGRATION_SRCS)
329+
TEST_STACK_OVERFLOW_SRCS = tests/test_stack_overflow.c
330+
331+
ALL_TEST_SRCS = $(TEST_FOUNDATION_SRCS) $(TEST_EXTRACTION_SRCS) $(TEST_STORE_SRCS) $(TEST_CYPHER_SRCS) $(TEST_MCP_SRCS) $(TEST_DISCOVER_SRCS) $(TEST_GRAPH_BUFFER_SRCS) $(TEST_PIPELINE_SRCS) $(TEST_WATCHER_SRCS) $(TEST_LZ4_SRCS) $(TEST_ZSTD_SRCS) $(TEST_ARTIFACT_SRCS) $(TEST_SQLITE_WRITER_SRCS) $(TEST_GO_LSP_SRCS) $(TEST_C_LSP_SRCS) $(TEST_TRACES_SRCS) $(TEST_CLI_SRCS) $(TEST_MEM_SRCS) $(TEST_UI_SRCS) $(TEST_SECURITY_SRCS) $(TEST_YAML_SRCS) $(TEST_SIMHASH_SRCS) $(TEST_STACK_OVERFLOW_SRCS) $(TEST_INTEGRATION_SRCS)
330332

331333

332334
# ── Build directories ────────────────────────────────────────────

‎internal/cbm/extract_calls.c‎

Lines changed: 8 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -4,6 +4,7 @@
44
#include "lang_specs.h"
55
#include "extract_unified.h"
66
#include "foundation/constants.h"
7+
#include "ts_node_stack.h"
78
#include "tree_sitter/api.h" // TSNode, ts_node_*
89
#include <stdint.h> // uint32_t
910
#include <string.h>
@@ -396,14 +397,13 @@ static const char *extract_first_string_arg(CBMExtractCtx *ctx, TSNode args) {
396397
}
397398

398399
// Walk AST for call nodes (iterative)
399-
#define CALLS_STACK_CAP CBM_SZ_512
400400
static void walk_calls(CBMExtractCtx *ctx, TSNode root, const CBMLangSpec *spec) {
401-
TSNode stack[CALLS_STACK_CAP];
402-
int top = 0;
403-
stack[top++] = root;
401+
TSNodeStack stack;
402+
ts_nstack_init(&stack, ctx->arena, CBM_SZ_512);
403+
ts_nstack_push(&stack, ctx->arena, root);
404404

405-
while (top > 0) {
406-
TSNode node = stack[--top];
405+
while (stack.count > 0) {
406+
TSNode node = ts_nstack_pop(&stack);
407407
const char *kind = ts_node_type(node);
408408

409409
if (cbm_kind_in_set(node, spec->call_node_types)) {
@@ -430,8 +430,8 @@ static void walk_calls(CBMExtractCtx *ctx, TSNode root, const CBMLangSpec *spec)
430430

431431
uint32_t count = ts_node_child_count(node);
432432
enum { LAST_IDX_OFFSET = 1 };
433-
for (int i = (int)(count - LAST_IDX_OFFSET); i >= 0 && top < CALLS_STACK_CAP; i--) {
434-
stack[top++] = ts_node_child(node, (uint32_t)i);
433+
for (int i = (int)(count - LAST_IDX_OFFSET); i >= 0; i--) {
434+
ts_nstack_push(&stack, ctx->arena, ts_node_child(node, (uint32_t)i));
435435
}
436436
}
437437
}

‎internal/cbm/extract_channels.c‎

Lines changed: 22 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -24,14 +24,15 @@
2424
#include "arena.h"
2525
#include "helpers.h"
2626
#include "foundation/constants.h"
27+
#include "ts_node_stack.h"
2728
#include "tree_sitter/api.h"
2829
#include <stdint.h>
2930
#include <string.h>
3031

3132
enum {
3233
CHAN_CONST_CAP = 256, /* max tracked identifiers per file */
33-
CHAN_STACK_CAP = 4096, /* tree-walk stack */
3434
CHAN_IDENT_MAX = 128, /* max identifier length tracked */
35+
CHAN_STACK_CAP = 4096, /* traversal stack depth per walk */
3536
CHAN_DIR_UNKNOWN = -1, /* unrecognized method → no channel */
3637
};
3738

@@ -93,15 +94,18 @@ static const char *literal_from_first_child(CBMExtractCtx *ctx, TSNode node) {
9394

9495
/* ── Constant resolution table ──────────────────────────────────── */
9596

96-
/* Walk the whole tree once and collect constant string bindings so later
97-
* passes can resolve bare-identifier channel arguments. */
97+
/* Walk the whole tree once and collect `const IDENT = "value"` bindings so
98+
* later passes can resolve bare-identifier channel arguments. Only scalar
99+
* string literals are tracked — template literals and expressions are left
100+
* unresolved. This is a flat lookup; scope boundaries are ignored (a single
101+
* const table per file is sufficient for the common Socket.IO pattern). */
98102
static void scan_string_consts_js(CBMExtractCtx *ctx, chan_const_table_t *tbl) {
99-
TSNode stack[CHAN_STACK_CAP];
100-
int top = 0;
101-
stack[top++] = ctx->root;
103+
TSNodeStack stack;
104+
ts_nstack_init(&stack, ctx->arena, CHAN_STACK_CAP);
105+
ts_nstack_push(&stack, ctx->arena, ctx->root);
102106

103-
while (top > 0 && tbl->count < CHAN_CONST_CAP) {
104-
TSNode node = stack[--top];
107+
while (stack.count > 0 && tbl->count < CHAN_CONST_CAP) {
108+
TSNode node = ts_nstack_pop(&stack);
105109
const char *kind = ts_node_type(node);
106110

107111
if (strcmp(kind, "variable_declarator") == 0) {
@@ -125,8 +129,8 @@ static void scan_string_consts_js(CBMExtractCtx *ctx, chan_const_table_t *tbl) {
125129
}
126130

127131
uint32_t count = ts_node_child_count(node);
128-
for (int i = (int)count - SKIP_ONE; i >= 0 && top < CHAN_STACK_CAP; i--) {
129-
stack[top++] = ts_node_child(node, (uint32_t)i);
132+
for (int i = (int)count - SKIP_ONE; i >= 0; i--) {
133+
ts_nstack_push(&stack, ctx->arena, ts_node_child(node, (uint32_t)i));
130134
}
131135
}
132136
}
@@ -370,18 +374,19 @@ static void extract_channels_js(CBMExtractCtx *ctx) {
370374
chan_const_table_t consts = {0};
371375
scan_string_consts_js(ctx, &consts);
372376

373-
TSNode stack[CHAN_STACK_CAP];
374-
int top = 0;
375-
stack[top++] = ctx->root;
377+
/* Second pass: walk the tree looking for call_expression nodes. */
378+
TSNodeStack stack;
379+
ts_nstack_init(&stack, ctx->arena, CHAN_STACK_CAP);
380+
ts_nstack_push(&stack, ctx->arena, ctx->root);
376381

377-
while (top > 0) {
378-
TSNode node = stack[--top];
382+
while (stack.count > 0) {
383+
TSNode node = ts_nstack_pop(&stack);
379384
if (strcmp(ts_node_type(node), "call_expression") == 0) {
380385
js_process_call(ctx, node, &consts);
381386
}
382387
uint32_t count = ts_node_child_count(node);
383-
for (int i = (int)count - SKIP_ONE; i >= 0 && top < CHAN_STACK_CAP; i--) {
384-
stack[top++] = ts_node_child(node, (uint32_t)i);
388+
for (int i = (int)count - SKIP_ONE; i >= 0; i--) {
389+
ts_nstack_push(&stack, ctx->arena, ts_node_child(node, (uint32_t)i));
385390
}
386391
}
387392
}

‎internal/cbm/extract_defs.c‎

Lines changed: 24 additions & 29 deletions
Original file line numberDiff line numberDiff line change
@@ -3,6 +3,7 @@
33
#include "helpers.h"
44
#include "lang_specs.h"
55
#include "foundation/constants.h"
6+
#include "ts_node_stack.h"
67
#include "simhash/minhash.h"
78
#include "semantic/ast_profile.h"
89
#include "tree_sitter/api.h" // TSNode, ts_node_*
@@ -2299,15 +2300,14 @@ static TSNode emit_elixir_module_class(CBMExtractCtx *ctx, TSNode cur) {
22992300

23002301
// Process Elixir call nodes iteratively — handles defmodule/def/defp/defmacro
23012302
// without recursion between extract_elixir_call ↔ extract_elixir_module_def.
2302-
#define ELIXIR_STACK_CAP CBM_SZ_64
23032303
static void extract_elixir_call(CBMExtractCtx *ctx, TSNode node, const CBMLangSpec *spec) {
23042304
(void)spec;
2305-
TSNode stack[ELIXIR_STACK_CAP];
2306-
int top = 0;
2307-
stack[top++] = node;
2305+
TSNodeStack stack;
2306+
ts_nstack_init(&stack, ctx->arena, CBM_SZ_64);
2307+
ts_nstack_push(&stack, ctx->arena, node);
23082308

2309-
while (top > 0) {
2310-
TSNode cur = stack[--top];
2309+
while (stack.count > 0) {
2310+
TSNode cur = ts_nstack_pop(&stack);
23112311
CBMArena *a = ctx->arena;
23122312

23132313
if (ts_node_child_count(cur) == 0) {
@@ -2329,10 +2329,10 @@ static void extract_elixir_call(CBMExtractCtx *ctx, TSNode node, const CBMLangSp
23292329
TSNode do_block = emit_elixir_module_class(ctx, cur);
23302330
if (!ts_node_is_null(do_block)) {
23312331
uint32_t dbc = ts_node_child_count(do_block);
2332-
for (int di = (int)dbc - SKIP_CHAR; di >= 0 && top < ELIXIR_STACK_CAP; di--) {
2332+
for (int di = (int)dbc - SKIP_CHAR; di >= 0; di--) {
23332333
TSNode dchild = ts_node_child(do_block, (uint32_t)di);
23342334
if (!ts_node_is_null(dchild) && strcmp(ts_node_type(dchild), "call") == 0) {
2335-
stack[top++] = dchild;
2335+
ts_nstack_push(&stack, ctx->arena, dchild);
23362336
}
23372337
}
23382338
}
@@ -3051,14 +3051,13 @@ static void extract_var_names(CBMExtractCtx *ctx, TSNode node, const CBMLangSpec
30513051

30523052
// Iterative variable walker for config languages with nested structure.
30533053
// Used by YAML, TOML, INI, JSON.
3054-
#define VAR_WALK_STACK_CAP CBM_SZ_256
30553054
static void walk_variables_iter(CBMExtractCtx *ctx, TSNode root, const CBMLangSpec *spec) {
3056-
TSNode stack[VAR_WALK_STACK_CAP];
3057-
int top = 0;
3058-
stack[top++] = root;
3055+
TSNodeStack stack;
3056+
ts_nstack_init(&stack, ctx->arena, CBM_SZ_256);
3057+
ts_nstack_push(&stack, ctx->arena, root);
30593058

3060-
while (top > 0) {
3061-
TSNode node = stack[--top];
3059+
while (stack.count > 0) {
3060+
TSNode node = ts_nstack_pop(&stack);
30623061
uint32_t count = ts_node_child_count(node);
30633062
for (int i = (int)count - SKIP_CHAR; i >= 0; i--) {
30643063
TSNode child = ts_node_child(node, (uint32_t)i);
@@ -3077,9 +3076,7 @@ static void walk_variables_iter(CBMExtractCtx *ctx, TSNode root, const CBMLangSp
30773076
strcmp(ck, "section") == 0 || strcmp(ck, "object") == 0 ||
30783077
strcmp(ck, "array") == 0 || strcmp(ck, "pair") == 0 || strcmp(ck, "element") == 0 ||
30793078
strcmp(ck, "content") == 0) {
3080-
if (top < VAR_WALK_STACK_CAP) {
3081-
stack[top++] = child;
3082-
}
3079+
ts_nstack_push(&stack, ctx->arena, child);
30833080
}
30843081
}
30853082
}
@@ -3275,13 +3272,13 @@ typedef struct {
32753272
// Push nested class nodes from a class body container onto the defs stack.
32763273
// Iteratively walks into wrapper nodes (field_declaration, template_declaration).
32773274
static void push_nested_class_nodes(TSNode body, const CBMLangSpec *spec, walk_defs_frame_t *stack,
3278-
int *top, const char *enclosing_qn) {
3279-
TSNode nc_stack[NESTED_CLASS_STACK_CAP];
3280-
int nc_top = 0;
3281-
nc_stack[nc_top++] = body;
3275+
int *top, const char *enclosing_qn, CBMArena *arena) {
3276+
TSNodeStack nc_stack;
3277+
ts_nstack_init(&nc_stack, arena, NESTED_CLASS_STACK_CAP);
3278+
ts_nstack_push(&nc_stack, arena, body);
32823279

3283-
while (nc_top > 0) {
3284-
TSNode cur = nc_stack[--nc_top];
3280+
while (nc_stack.count > 0) {
3281+
TSNode cur = ts_nstack_pop(&nc_stack);
32853282
uint32_t nc = ts_node_child_count(cur);
32863283
for (int i = (int)nc - SKIP_CHAR; i >= 0; i--) {
32873284
TSNode child = ts_node_child(cur, (uint32_t)i);
@@ -3293,9 +3290,7 @@ static void push_nested_class_nodes(TSNode body, const CBMLangSpec *spec, walk_d
32933290
const char *ck = ts_node_type(child);
32943291
if (strcmp(ck, "field_declaration") == 0 ||
32953292
strcmp(ck, "template_declaration") == 0 || strcmp(ck, "declaration") == 0) {
3296-
if (nc_top < NESTED_CLASS_STACK_CAP) {
3297-
nc_stack[nc_top++] = child;
3298-
}
3293+
ts_nstack_push(&nc_stack, arena, child);
32993294
}
33003295
}
33013296
}
@@ -3342,15 +3337,15 @@ static const char *compute_class_qn(CBMExtractCtx *ctx, TSNode node, const char
33423337

33433338
// Push nested class children from a class body container onto the walk stack.
33443339
static void push_class_body_children(TSNode node, const CBMLangSpec *spec, walk_defs_frame_t *stack,
3345-
int *top, const char *new_enclosing) {
3340+
int *top, const char *new_enclosing, CBMArena *arena) {
33463341
uint32_t nc = ts_node_child_count(node);
33473342
for (uint32_t ci = 0; ci < nc; ci++) {
33483343
TSNode child = ts_node_child(node, ci);
33493344
const char *ck = ts_node_type(child);
33503345
if (strcmp(ck, "field_declaration_list") == 0 || strcmp(ck, "class_body") == 0 ||
33513346
strcmp(ck, "declaration_list") == 0 || strcmp(ck, "body") == 0 ||
33523347
strcmp(ck, "block") == 0 || strcmp(ck, "suite") == 0) {
3353-
push_nested_class_nodes(child, spec, stack, top, new_enclosing);
3348+
push_nested_class_nodes(child, spec, stack, top, new_enclosing, arena);
33543349
return;
33553350
}
33563351
}
@@ -3394,7 +3389,7 @@ static void walk_defs(CBMExtractCtx *ctx, TSNode root, const CBMLangSpec *spec,
33943389
if (cbm_kind_in_set(node, spec->class_node_types)) {
33953390
extract_class_def(ctx, node, spec);
33963391
const char *new_enclosing = compute_class_qn(ctx, node, frame.enclosing_class_qn);
3397-
push_class_body_children(node, spec, stack, &top, new_enclosing);
3392+
push_class_body_children(node, spec, stack, &top, new_enclosing, ctx->arena);
33983393
continue;
33993394
}
34003395

‎internal/cbm/extract_env_accesses.c‎

Lines changed: 8 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -4,6 +4,7 @@
44
#include "lang_specs.h"
55
#include "extract_unified.h"
66
#include "foundation/constants.h"
7+
#include "ts_node_stack.h"
78
#include "tree_sitter/api.h" // TSNode, ts_node_*
89
#include <stdint.h> // uint32_t
910
#include <string.h>
@@ -137,14 +138,13 @@ static bool is_env_var_name(const char *s) {
137138
}
138139

139140
// Iterative env access walker — explicit stack
140-
#define ENV_STACK_CAP 4096
141141
static void walk_env_accesses(CBMExtractCtx *ctx, TSNode root, const CBMLangSpec *spec) {
142-
TSNode stack[ENV_STACK_CAP];
143-
int top = 0;
144-
stack[top++] = root;
142+
TSNodeStack stack;
143+
ts_nstack_init(&stack, ctx->arena, 4096);
144+
ts_nstack_push(&stack, ctx->arena, root);
145145

146-
while (top > 0) {
147-
TSNode node = stack[--top];
146+
while (stack.count > 0) {
147+
TSNode node = ts_nstack_pop(&stack);
148148
const char *kind = ts_node_type(node);
149149
const char *env_key = NULL;
150150

@@ -165,8 +165,8 @@ static void walk_env_accesses(CBMExtractCtx *ctx, TSNode root, const CBMLangSpec
165165

166166
uint32_t count = ts_node_child_count(node);
167167
enum { LAST_IDX = 1 };
168-
for (int i = (int)count - LAST_IDX; i >= 0 && top < ENV_STACK_CAP; i--) {
169-
stack[top++] = ts_node_child(node, (uint32_t)i);
168+
for (int i = (int)count - LAST_IDX; i >= 0; i--) {
169+
ts_nstack_push(&stack, ctx->arena, ts_node_child(node, (uint32_t)i));
170170
}
171171
}
172172
}

‎internal/cbm/extract_imports.c‎

Lines changed: 15 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -3,6 +3,7 @@
33
#include "helpers.h"
44
#include "tree_sitter/api.h" // TSNode, ts_node_*
55
#include "foundation/constants.h"
6+
#include "ts_node_stack.h"
67
#include <stdint.h> // uint32_t
78
#include <string.h>
89
#include <ctype.h>
@@ -411,14 +412,13 @@ static bool process_commonjs_require(CBMExtractCtx *ctx, TSNode call) {
411412
return true;
412413
}
413414

414-
#define ES_IMPORT_STACK_CAP CBM_SZ_512
415415
static void walk_es_imports(CBMExtractCtx *ctx, TSNode root) {
416-
TSNode stack[ES_IMPORT_STACK_CAP];
417-
int top = 0;
418-
stack[top++] = root;
416+
TSNodeStack stack;
417+
ts_nstack_init(&stack, ctx->arena, CBM_SZ_512);
418+
ts_nstack_push(&stack, ctx->arena, root);
419419

420-
while (top > 0) {
421-
TSNode node = stack[--top];
420+
while (stack.count > 0) {
421+
TSNode node = ts_nstack_pop(&stack);
422422
const char *kind = ts_node_type(node);
423423
bool push_children = true;
424424

@@ -436,8 +436,8 @@ static void walk_es_imports(CBMExtractCtx *ctx, TSNode root) {
436436

437437
if (push_children) {
438438
uint32_t count = ts_node_child_count(node);
439-
for (int i = (int)count - SKIP_ONE; i >= 0 && top < ES_IMPORT_STACK_CAP; i--) {
440-
stack[top++] = ts_node_child(node, (uint32_t)i);
439+
for (int i = (int)count - SKIP_ONE; i >= 0; i--) {
440+
ts_nstack_push(&stack, ctx->arena, ts_node_child(node, (uint32_t)i));
441441
}
442442
}
443443
}
@@ -820,14 +820,13 @@ static void process_wolfram_needs(CBMExtractCtx *ctx, TSNode node) {
820820
}
821821
}
822822

823-
#define WOLFRAM_IMPORT_STACK_CAP CBM_SZ_512
824823
static void walk_wolfram_imports(CBMExtractCtx *ctx, TSNode root) {
825-
TSNode stack[WOLFRAM_IMPORT_STACK_CAP];
826-
int top = 0;
827-
stack[top++] = root;
824+
TSNodeStack stack;
825+
ts_nstack_init(&stack, ctx->arena, CBM_SZ_512);
826+
ts_nstack_push(&stack, ctx->arena, root);
828827

829-
while (top > 0) {
830-
TSNode node = stack[--top];
828+
while (stack.count > 0) {
829+
TSNode node = ts_nstack_pop(&stack);
831830
const char *kind = ts_node_type(node);
832831

833832
if (strcmp(kind, "get_top") == 0) {
@@ -837,8 +836,8 @@ static void walk_wolfram_imports(CBMExtractCtx *ctx, TSNode root) {
837836
}
838837

839838
uint32_t count = ts_node_child_count(node);
840-
for (int i = (int)count - SKIP_ONE; i >= 0 && top < WOLFRAM_IMPORT_STACK_CAP; i--) {
841-
stack[top++] = ts_node_child(node, (uint32_t)i);
839+
for (int i = (int)count - SKIP_ONE; i >= 0; i--) {
840+
ts_nstack_push(&stack, ctx->arena, ts_node_child(node, (uint32_t)i));
842841
}
843842
}
844843
}

0 commit comments

Comments
 (0)