Repository navigation
fix(extract): AST walker stacks grow instead of silently capping content - #2375
Merged
Merged
Conversation
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
force-pushed
the
fix/complexity-walker-no-silent-cap
branch
from
September 27, 2026 21:45
3ad76fd to
7707c9d
Compare
This was referenced Sep 27, 2026
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]>
3 of 4 tasks
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]>
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
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_complexityandcount_branching_iter(helpers.c,BRANCHING_STACK_CAP4096). These produce the cyclomatic, cognitive, loop and access metrics.extract_body_ident_tokens(extract_defs.c,BT_STACK512). 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()inhelpers.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_lexin tree-sitter-llvm's generated parser is a switch with 4654 cases.13432 is the true branch count: 8776
if+ 4654case+ 1default+ 1switch.Linux kernel:
rimob_panel_on) now sample tokens from the start of the body. That moves 11 SEMANTICALLY_RELATED edges.Tests (extraction suite), all RED on
mainand GREEN with the fix:if/whilestatements must report exact cyclomatic, cognitive and loop counts, through both the extractor andcbm_count_branching. Onmainboth report 4095.f0on. Onmainthe sample starts atf91.Companion to #2373, which removes the separate definitions-walk cap.