Follow-up correcting d8a78e8, whose message claimed a broken merge cap
crashes "within the first second" so the 10s alarm could not mask it.
Falsification disproved that claim AND found the guard was vacuous on
POSIX from the start:
- With CBM_TS_STACK_MERGE_MAX_DEPTH deleted outright, the ORIGINAL
unbounded test stayed GREEN (220s full grind, no crash) on macOS ASan.
- Small thread stacks (2 MB, then 512 KB) did not change that.
- Instrumenting the vendored recursion showed why: the recursive merge
path is NEVER ENTERED for this input in the observable window — max
depth stays 0. There is nothing for a stack bound to catch here.
So the cap-regression DETECTION lives in the Windows in-process branch
(real ~1 MB native stack, where #913 actually manifested — exercised by
the windows CI leg). The POSIX branch is, and always was, a bounded
no-crash smoke of the pathological parse; the 10s alarm makes it
deterministic (12-15s across three runs, was 2-218s machine-dependent)
without any detection loss, because there was no POSIX detection to
lose. The experimental pthread machinery is dropped; the test comment
now carries the falsification data so no future reader mistakes the
POSIX branch for a cap guard.
Signed-off-by: Martin Vogel <martin.vogel.tech@gmail.com>
perl_glr_deep_parse_recursion_capped wandered between 2s and 218s for the
IDENTICAL input: past the merge cap the ambiguity-exploded GLR parse grinds
at an environment-dependent rate (allocator/scheduler state in the forked
child), and the test paid for however long that grind ran. It was the
critical path of every parallel run and the dominant chunk of the
sequential one.
The guard's actual signal is the CRASH, not the grind: when
CBM_TS_STACK_MERGE_MAX_DEPTH regresses, the recursive stack-merge
overflows within the first second at this depth (same profile as the
sibling pre-guard probe, rc=139 in under a second). The forked child now
arms a 10s alarm whose handler exits cleanly — a real SIGSEGV/SIGBUS
still terminates the child by signal first and stays visible to
WIFSIGNALED, so the RED path is untouched; only the pointless remainder
of the grind is skipped. Windows (in-process branch) is unchanged.
Suite b: 13s across three consecutive runs (was 2-218s). Full parallel
run: 97s wall, 6,374 passed / 0 failed / 1 skipped, union guard clean —
vs 351s sequential on the same machine (3.6x).
Signed-off-by: Martin Vogel <martin.vogel.tech@gmail.com>
The runner executed all 104 suites sequentially (~10 min locally, the bulk
of every CI test leg). The suites are process-isolated already (per-process
mkdtemp HOME sentinel; two full parallel runs produced zero cross-suite
failures), so the serialization was pure convention.
- test-runner --list-suites: prints every registered suite, one per line,
emitted by the SAME macro table that executes suites — the list cannot
drift from the run set by construction.
- scripts/run-tests-parallel.sh: runs each suite as its own process
(jobs = CPU count; CBM_TEST_PAR_JOBS overrides) under a ZERO-LOSS
CONTRACT: a union guard fails the gate if the set of suites that
produced a result differs from --list-suites (nothing can be silently
dropped, a newly added suite is picked up automatically); per-suite
pass/fail/skip are summed into the sequential runner's exact summary
format; any suite crash, failure, or omission exits nonzero. Per-suite
wall times are printed for balance tracking.
- make test-par: the parallel target. make test (sequential) is unchanged
and remains the escape hatch (CBM_TEST_SEQUENTIAL=1 in test.sh).
- scripts/test.sh: builds, then routes through test-par — every CI test
leg gets the speedup with zero workflow-topology change (same jobs,
same gates, same billing; the legs just finish sooner).
- The stack_overflow suite is split into a/b/c (7+6+7 of its 20 tests,
pure re-registration): as one suite it was the wall-clock critical path
of any parallel run — every other suite finished underneath its ~4
minutes.
Measured locally (Apple Silicon, ASan runner): sequential ~10 min vs
parallel 232 s, totals identical (6,361 passed / 0 failed / 1 skipped),
union guard clean. The TSan leg keeps its dedicated subset runner
(sequential) — out of scope here.
Signed-off-by: Martin Vogel <martin.vogel.tech@gmail.com>
tree-sitter's GLR parser merges ambiguous parse-stack heads recursively in
stack_node_add_link (internal/cbm/vendored/ts_runtime/src/stack.c), once per
nesting level. On pathologically nested input whose grammar is ambiguous
(Perl's paren-optional calls, f(f(f(...)))), that recursion overflows the
native stack during the parse — a small ~1 MB Windows thread stack, and even
an 8 MB POSIX stack at extreme depth — before any extraction runs. Grammars
that are unambiguous here (Java, C++) never trigger the recursive merge.
Cap the recursive merge at CBM_TS_STACK_MERGE_MAX_DEPTH (512) via a
depth-tracked inner worker; the public stack_node_add_link is a thin wrapper
seeding depth 0, so every existing call site is unchanged. Past the cap the
ambiguity is left on the GLR stack instead of merged — a valid parse, never a
wrong one. 512 frames is well within a 1 MB stack while far exceeding any
realistic source nesting.
Add perl_glr_deep_parse_recursion_capped: a crash-isolating regression that
parses deep ambiguous Perl directly (a forked child on POSIX, in-process on
Windows), bypassing cbm_extract_file's CBM_PERL_MAX_PARSE_NESTING pre-parse
guard so the vendored cap itself is exercised rather than the guard.
Narrow vendored-runtime change; no other parsing behavior is affected. The
higher-level Perl pre-parse guard (issue #913 context) stays in place and can
be retired in a follow-up once this cap is proven in the field.
Signed-off-by: Shane McCarron <shane.mccarron@corvexconnect.com>
A deeply nested Perl call chain f(f(f(...))) overflowed the stack while
parsing on small-stack platforms: tree-sitter's GLR parser recurses once
per nesting level in stack_node_add_link (vendored ts_runtime/src/stack.c)
merging the ambiguous parse-stack heads that Perl's f(...) grammar produces.
The overflow happens during ts_parser_parse, before any LSP walk runs, so
the CBM_LSP_PERL_MAX_WALK_DEPTH guards can never fire. This crashed
test-windows (CLANG64) with an AddressSanitizer stack-overflow and hung
test-unix (ubuntu-24.04-arm) to a 4h timeout on lsp_perl_deep_expression_no_crash.
Add cbm_source_nesting_exceeds(): an O(n) early-exit bracket-depth scan, and
skip extraction (clean has_error, zero edges) for Perl input whose nesting
exceeds CBM_PERL_MAX_PARSE_NESTING (128) before it reaches tree-sitter.
Scoped to Perl because only its ambiguous call grammar drives the GLR
recursion to the nesting depth; C/Java/Python parse the same shape with a
single stack head. 128 is ~10x above any real Perl nesting and well below
the depth where the parser overflows a 1MB stack.
Correct the lsp_perl_deep_expression_no_crash comment to describe the actual
mechanism (parser recursion, not the LSP walk).
Signed-off-by: Shane McCarron <shane.mccarron@corvexconnect.com>
F1: dot the Exporter import target so seeded CPAN exported subs resolve.
perl_collect_qw_imports built colon-form targets (Scalar::Util::blessed)
but the stdlib registry keys curated CPAN subs in dotted form
(Scalar.Util.blessed) and lookup is exact-match. Wire in perl_pkg_to_dot
to dot the module portion and drop the now-unnecessary (void) cast.
F2: add a recursion-depth guard (CBM_LSP_PERL_MAX_WALK_DEPTH=512) to both
AST walkers (perl_resolve_calls_in_node, perl_pass1_scan) via a depth-
guarded wrapper + inner split, mirroring java_lsp's JAVA_LSP_MAX_WALK_DEPTH.
Past the cap a subtree is skipped (graceful degradation, no wrong edge),
preventing stack overflow on pathologically nested input.
F3: lock the shared last-"::"-segment normalization in lsp_resolve.h with a
direct regression test over cbm_pipeline_find_lsp_resolution: a qualified
static call still resolves AND the cross-namespace mis-attribution edge case
is bounded by caller-QN equality + the confidence floor.
F4: implement SUPER:: dispatch. Populate enclosing_parent_qn from the
enclosing package's first @ISA parent and resolve $self->SUPER::method() to
that parent's method (strategy perl_method_super). No known parent or
unresolved method emits no edge (zero-edge guarantee preserved).
Tests: perllsp_cpan_exported_function, perllsp_super_dispatch,
perllsp_super_no_parent_no_edge, lsp_perl_deep_expression_no_crash,
lsp_resolve_qualified_static_call_normalizes_colons,
lsp_resolve_misattribution_is_bounded.
Signed-off-by: Shane McCarron <shane.mccarron@corvexconnect.com>
py_eval_expr_type evaluated a call node's attribute receiver twice (once
in the container special-case, once in the general attribute path), so an
N-link chained call cost O(2^N) evaluations — real-world ~65-link builder
chains hung indexing for hours (#710). The evaluator also recursed once
per expression nesting level with no depth guard, so a pathologically deep
expression overflowed the native stack (#720).
Three guard layers, mirroring c_eval_expr_type's design in c_lsp.c:
1. Memoization: py_eval_expr_type is now a wrapper around the renamed
py_eval_expr_type_uncached. Results are cached per node in an
open-addressing table on PyLSPContext (arena-allocated, cold per file),
keyed by node identity (TSNode.id) — NOT the start byte, since every
leftmost descendant of a chain shares it and byte-keyed entries alias
distinct nodes into silently wrong resolutions. Entries carry a scope
generation; every scope bind/restore bumps it (O(1) whole-cache flush),
so re-evaluation under changed bindings (lambda re-walks, isinstance
narrowing) behaves exactly as before. Inserts are load-bounded (<75%)
and rejected when growth fails, so a full table can never spin.
2. Depth cap: PY_LSP_MAX_EVAL_DEPTH 256 (same as C_EVAL_DEPTH_LIMIT);
past the cap the evaluator returns unknown instead of overflowing the
stack. Truncated results — including any ancestor of a truncation —
are never cached, so a depth- or budget-limited `unknown` cannot
poison post-truncation reuse.
3. Step budget: PY_EVAL_MAX_STEPS_PER_FILE 10000 (mirrors
C_EVAL_MAX_STEPS_PER_FILE); pathological files degrade to unknown
instead of stalling indexing. Cache hits don't consume budget.
Distills PR #732 (memoization; fixed the start-byte cache key and the
missing staleness handling) and PR #758 (depth cap; raised 64 -> 256 to
match the sibling LSPs, added the never-cache-truncated ordering), and
adds the step budget plus reproduce-first tests: a 40-link chain that
must resolve its final link, a heterogeneous-receiver chain that fails
under byte keying, a 30k-deep expression crash guard, and a budget
degradation guard.
Fixes#710. Fixes#720.
Co-authored-by: LA-10 <lashuha@uwaterloo.com>
Co-authored-by: Dustin Persek <dustin.persek@protonmail.com>
Signed-off-by: Martin Vogel <martin.vogel.tech@gmail.com>
The per-language "resolve calls in AST node" walkers recurse once per nesting
level. Four of them — Python (py_resolve_calls_in), Go (resolve_calls_in_node),
PHP (php_resolve_calls_in_node), Kotlin (kt_resolve_calls_in_node) — had no depth
guard, so a deeply-nested or cyclic file could drive them into a native stack
overflow (SIGSEGV) that takes down the whole index run. C and Java already guard
this (C_LSP_MAX_WALK_DEPTH / JAVA_LSP_MAX_WALK_DEPTH).
Add the same wrapper/inner depth guard to all four, backed by a shared,
env-configurable cap: CBM_LSP_MAX_WALK_DEPTH (default 512) in scope.h. Past the
cap the wrapper skips the subtree — those calls stay unresolved (graceful
degradation, not a crash). The walk_depth-- runs after the inner body returns, so
early returns can't leak the counter.
Reproduce-first: lsp_{python,go,php,kotlin}_deep_nesting_no_crash (30000-deep
nested calls, run under a forked child + WIFSIGNALED). RED without the cap (the
child SIGSEGVs — verified by raising CBM_LSP_MAX_WALK_DEPTH to 100M), GREEN with
it. Full suite 5752/0, no ASan/leak.
Part of the resilient-indexing effort (Track B prevention layer). Refs #668.
Signed-off-by: Martin Vogel <martin.vogel.tech@gmail.com>
bind_lambda_args and the method-reference arity path indexed the resolved method signature's NULL-terminated param_types array by the CALL-SITE argument index. A call with more arguments than the resolved overload declares (overload mismatch, varargs) read past the terminator and dereferenced whatever followed in the arena as a CBMType* - SIGSEGV while indexing elasticsearch (same out-of-bounds family as #427 and the bitcoin targs fix). Both sites now bound the index by the walked param count. Reproduce-first: 6-line fixture - run(Runnable) invoked with six lambdas - crashed rc=134 pre-fix; fork+exit-signal regression test lsp_java_lambda_args_exceed_params_no_crash added; suite 5574/0.
Indexing large OSS during the perf sweep crashed three LSP resolvers, all by stack overflow in their recursive resolve walks (macOS crash reports): elasticsearch — SIGSEGV in bind_lambda_args under deep recursive java_resolve_calls_in_node frames; bitcoin — SIGSEGV in cbm_type_substitute via c_adl_resolve under deep c_resolve_calls_in_node frames; microsoft/TypeScript — SIGBUS under an unbounded lookup_member_type cycle (cyclic type graph in reallyLargeFile.ts). The expression-eval guards (eval_depth) did not cover these walks. Each resolver now has a depth-guarded entry (walk_depth cap 512 for the Java/C AST walks, member_depth cap 64 for TS member lookup); past the cap the subtree resolves as unknown — graceful degradation instead of a crash. Reproduce-first: prod CLI probes crashed pre-fix (nested-call Java rc=139, nested-call C++ rc=139); fork+exit-signal regression tests added (TS cyclic shape needs a real cross-file registry, so it is verified at the real-repo tier — microsoft/TypeScript now indexes clean). Side-finding documented in the sweep report: Java BLOCK nesting >=3000 is minutes-slow (separate pathology, not this fix).
Root cause (corrected from the report): not a tree-sitter null-subtree sentinel — 0xffffffffffffffff is a freed/heap-corrupted pointer. The vendored ts runtime allocates via its overridable ts_current_malloc/free; under the prod build's MI_OVERRIDE=1, the Windows static-MinGW link (--allow-multiple-definition) resolves ts_malloc to mimalloc but ts_free can resolve to the CRT free (or vice-versa), corrupting the heap freelist and crashing mid-parse on large templated C++ headers (scales with parse churn, not syntax). cbm_init now calls ts_set_allocator(mi_malloc, mi_calloc, mi_realloc, mi_free) so ts allocate+free go through one allocator on every platform. Guarded to CFLAGS_PROD (MI_OVERRIDE=1); the test build stays CRT+ASan to avoid an alloc/free mismatch there. Tests in test_stack_overflow.c: allocator-binding mechanism + large-templated-C++ extraction guard (the C++ gap noted in #424).
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.
Pedro Ramos