Skip to content

fix(extract): AST walker stacks grow instead of silently capping content - #2375

Merged
DeusData merged 1 commit into
mainfrom
fix/complexity-walker-no-silent-cap
Sep 28, 2026
Merged

DeusData merged 1 commit into
mainfrom
fix/complexity-walker-no-silent-cap

Conversation

@DeusData

Copy link
Copy Markdown
Owner

What

Three iterative AST walkers kept their pending nodes in fixed-size stacks and silently stopped pushing children once the stack was full:

  • cbm_compute_complexity and count_branching_iter (helpers.c, BRANCHING_STACK_CAP 4096). These produce the cyclomatic, cognitive, loop and access metrics.
  • extract_body_ident_tokens (extract_defs.c, BT_STACK 512). This produces the body-token sample behind semantic search and SEMANTICALLY_RELATED.

Children are pushed last-to-first, so a full stack dropped a wide body's first children. The metrics undercounted, and the token sampler read a window from the middle of the body instead of its first identifiers. A work cap was deciding graph content.

Fix

cbm_walk_stack_reserve() / cbm_walk_stack_release() in helpers.c. Each walker keeps a small first chunk on the stack (512 frames) and spills to the heap through the memory core (cbm_alloc/cbm_realloc/cbm_free, class EXTRACT) only for deep or wide trees. Traversal order is unchanged.

If the stack cannot grow, the failure is logged (extract.walk_stack_alloc_failed). The walker then returns a documented sentinel instead of a truncated result: CBM_WALK_METRIC_UNAVAILABLE (-1) for the metrics, or no token sample.

The sampler's 128-identifier and 2048-byte limits are its sampling contract, so they stay. The 512-entry stack was never part of that contract, because it broke the "first identifiers in source order" property.

Proof

Real input: ts_lex in tree-sitter-llvm's generated parser is a switch with 4654 cases.

main fix
cyclomatic 11133 13432
cognitive 29303 35639

13432 is the true branch count: 8776 if + 4654 case + 1 default + 1 switch.

Linux kernel:

  • No function reaches the old 4096 cap, so complexity is byte-identical for every function.
  • Three functions with more than 512 pending nodes (for example rimob_panel_on) now sample tokens from the start of the body. That moves 11 SEMANTICALLY_RELATED edges.
  • Index time is unchanged within noise: main 214.4 s and 207.9 s, fix 197.6 s and 192.2 s.

Tests (extraction suite), all RED on main and GREEN with the fix:

  • A C function with 5000 top-level if/while statements must report exact cyclomatic, cognitive and loop counts, through both the extractor and cbm_count_branching. On main both report 4095.
  • A body with 600 calls must sample from f0 on. On main the sample starts at f91.

Companion to #2373, which removes the separate definitions-walk cap.

Three iterative AST walkers kept their pending nodes in fixed-size stacks
and silently stopped pushing children once full:

  - cbm_compute_complexity and count_branching_iter (helpers.c,
    BRANCHING_STACK_CAP 4096) -> cyclomatic, cognitive, loop and access
    metrics
  - extract_body_ident_tokens (extract_defs.c, BT_STACK 512) -> the
    body-token sample that feeds semantic search / SEMANTICALLY_RELATED

Children are pushed last-to-first, so a full stack dropped a wide body's
FIRST children. The metrics undercounted, and the token sampler read a
mid-body window instead of the first identifiers. That let a work cap decide
graph content.

Real input: tree-sitter-llvm's generated ts_lex (a 4654-case switch)
reported cyclomatic 11133 / cognitive 29303. It really has 8776 if + 4654
case + 1 default + 1 switch = 13432 branches, which is what it reports now
(cognitive 35639). On the Linux kernel no function reaches the old 4096 cap,
so complexity is byte-identical for every function. Three functions with
bodies over 512 pending nodes now sample their tokens from the start of the
body (for example rimob_panel_on), which moves 11 SEMANTICALLY_RELATED edges.
Index time is unchanged within noise (main 214.4/207.9 s, fix 197.6/192.2 s).

Fix: cbm_walk_stack_reserve()/cbm_walk_stack_release() in helpers.c. Each
walker keeps a small on-stack first chunk (512 frames) and spills to the heap
through the memory core (cbm_alloc/cbm_realloc/cbm_free, class EXTRACT) only
for deep or wide trees. Traversal order is unchanged. If the stack cannot
grow, the failure is logged ("extract.walk_stack_alloc_failed") and the
walker returns a documented sentinel instead of a truncated result:
CBM_WALK_METRIC_UNAVAILABLE (-1) for the metrics, or no token sample.

The body-token sampler's caps of 128 identifiers and a 2048-byte buffer are
its sampling contract and stay. The 512-entry stack was never part of that
contract, because it broke the "first identifiers in source order" property.

Tests (extraction suite): a C function with 5000 top-level if/while
statements must report exact cyclomatic/cognitive/loop counts through both
the extractor and cbm_count_branching, and a 600-call body must sample from
f0 on. All three are RED on main (4095 / 4095 / sample starting at f91) and
GREEN with the fix.

Signed-off-by: Martin Vogel <[email protected]>
@DeusData
DeusData force-pushed the fix/complexity-walker-no-silent-cap branch from 3ad76fd to 7707c9d Compare September 27, 2026 21:45
@DeusData
DeusData merged commit 1771812 into main Sep 28, 2026
40 checks passed
DeusData added a commit to CaptainMittens/codebase-memory-mcp that referenced this pull request Oct 20, 2026
Follow-up to the review of DeusData#2091, on top of the contributor's change.

The three ts_lsp.c walks (infer_return_type_from_body,
rebuild_signatures_from_ast, convert_signature_type_params) now keep
their first 256 slots on the C stack, as the old fixed arrays did, and
grow on the heap through cbm_walk_stack_reserve / cbm_walk_stack_release
(DeusData#2375) instead of cutting TSNodeStack storage from ctx->arena:

- Scratch lifetime: ctx->arena in the per-file pass is the result
  arena, kept until the result cache is freed, and the return walk runs
  once per untyped top-level function. The heap chunk is now released
  when each walk ends.
- No silent drop: when the stack cannot grow, cbm_walk_stack_reserve
  logs extract.walk_stack_alloc_failed and the walk stops. The return
  walk then answers "unknown"; the signature walks leave the
  declarations not yet reached as extract_defs registered them.
- Traversal order: children are filled in cursor order (still one O(N)
  pass) and popped last-child first, exactly as main's walks did, so of
  several returns the later one is still tried first.
  tslsp_return_walk_order_prefers_later_return pins it; it fails under
  a first-child-first walk.

The TSNodeStack arena initializer in extract_node_stack.h is no longer
needed and is dropped, so that header is unchanged from main. The two
stack-cap tests now fail instead of passing when their buffer
allocation fails.

Co-authored-by: Joshua Richter <[email protected]>
Signed-off-by: Martin Vogel <[email protected]>
DeusData pushed a commit that referenced this pull request Oct 28, 2026
walk_yaml_mapping (dotted key paths, 256 frames) and
scan_yaml_for_infra_bindings (512 nodes) kept their pending nodes in
fixed-size stacks and stopped pushing once full. A mapping with more than
256 nested sibling mappings lost the full key_path of every leaf past the
cap: `k299.url` was only recorded as the shorter path that the walk of a
nested block emits on its own.

The infra Route pass decides on those paths. A `data:` payload block with
300 entries lost `data.svcN.webhook_url` for N >= 256, the payload deny
never saw those values, and 44 of them were minted as infra Route nodes.

Both walkers now start on the same-sized on-stack chunk and grow through
cbm_walk_stack_reserve / cbm_walk_stack_release (#2375). If the stack
cannot grow, the failure is logged as extract.walk_stack_alloc_failed and
the walk stops, instead of truncating silently.

Part of #2388.

Signed-off-by: Gaurav Dubey <[email protected]>
DeusData added a commit to henry-hz/codebase-memory-mcp that referenced this pull request Oct 31, 2026
elixir_compute_complexity kept its pending frames in one fixed 4096-entry
array (48 bytes each, 196,608 bytes in a single stack frame) and stopped
pushing children once it was full. Children are pushed last to first, so a
wider body lost its FIRST children and the function reported a lower
complexity with no signal, on exactly the largest functions. Worker threads
do not get the 8 MB main-thread stack, so the array was a risk of its own.

It now uses the walker pattern cbm_compute_complexity has used since DeusData#2375:
a 512-frame on-stack first chunk that spills to the heap through
cbm_walk_stack_reserve (memory core, class EXTRACT) and is released with
cbm_walk_stack_release. If the stack cannot grow, every metric reports
CBM_WALK_METRIC_UNAVAILABLE instead of an undercount. This answers items 2
and 3 of the 2026-08-20 review.

The new test builds a 5000-statement body of alternating if and for. The
fixed stack reports complexity 4095 for it instead of 5000.

Signed-off-by: Martin Vogel <[email protected]>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

1 participant