Repository navigation
fix: grow the ts_lsp AST walk stacks so wide files keep every declaration - #2091
Conversation
…tion Three walks in internal/cbm/lsp/ts_lsp.c held at most 256 AST nodes in a fixed array and stopped pushing when it filled. Nothing reported the stop, so the passes answered as if they had seen the whole file. In rebuild_signatures_from_ast and convert_signature_type_params the seeding loop alone can fill all 256 slots, because it pushes every top-level child of the file. A file with more than 256 top-level declarations therefore skipped every declaration past that point: each one kept whatever signature the first extraction pass had guessed, and a generic function past the cap kept NAMED instead of TYPE_PARAM, so calls through it stopped resolving. In infer_return_type_from_body the same cap made a wide function body answer "unknown return type" for a return the walk had never reached. The repo already carries the module that solves this: internal/cbm/extract_node_stack.h, written for GitHub issue DeusData#199 to replace fixed TSNode stack[] arrays that silently drop subtrees. Nine extract files use it; ts_lsp.c was never converted. This converts it. The header gains ts_nstack_init_arena, which takes an arena directly, because the LSP passes hold a TSLSPContext rather than a CBMExtractCtx. ts_nstack_init keeps its context argument, which is what makes handing over the wrong arena a type error, and now delegates to the new function. Traversal order changes from last-child-first to first-child-first, because ts_nstack_push_children reverses on push. That also drops an O(N^2) ts_node_child(n, i) loop for one cursor pass. For infer_return_type_from_body the new order matches the comment the function already carried: it finds the first return, where the old code found the last. New test tslsp_stress_declarations_past_stack_cap makes the same claim as tslsp_generic_identity_inference, 300 declarations deeper in the file. Without this change it fails with "MISSING resolved call: caller~.go -> callee~use"; with it the ts_lsp suite is 304 passed, 0 failed. Signed-off-by: Joshua Richter <[email protected]>
|
Thanks for opening this — it has been seen, and it is queued. This note is automated, but it is not a brush-off: it exists so you know where your PR stands instead of having to guess from silence. Current review status: working through a backlog. What that means for this PR, concretely:
Things that will genuinely speed it up whenever review does happen:
If this fixes a bug, a reproduction we can run is worth more than a description of the symptom. Thanks for contributing, and sorry in advance for the wait. |
The first commit converted three walks in ts_lsp.c but tested only two of them. infer_return_type_from_body was changed without a test of its own. tslsp_stress_return_past_stack_cap makes the same claim as the existing tslsp_return_inferred_local, with the return placed after 300 statements — more than the 256 slots the old fixed array held, so the walk used to stop before reaching it and answer "unknown return type". Without the fix the suite is 303 passed, 2 failed, the second failure being this test. With it, 305 passed. Signed-off-by: Joshua Richter <[email protected]>
|
Three things say it is unrelated:
I cannot re-run the job myself ( |
DeusData
added
bug
|
Thank you for isolating these walks and supplying the before/after regressions. The capped pushes are still present on main, so this addresses a concrete omission. Please make allocation failure fail the two new tests rather than pass, and pin the acknowledged return-traversal-order change with a focused multiple-return case or preserve the previous order. The Windows guard result still needs maintainer attribution; it is not a reason to request unrelated source changes from you. |
|
Thanks again, @CaptainMittens. This is a careful fix, and the before/after tests plus the "Which arena" write-up made it easy to verify. The capped walks are still on Still open from the 19 September review:
One suggestion now that #2375 exists: once it lands, please rebase onto it and use its
The red Windows guard job is the #2057 cold-storm race you identified. That one's ours to attribute, and nothing on your side depends on it. Thanks for your patience with the queue! |
|
Thanks again for the wide-file regressions. Following up on the last review: allocation failure must fail the tests, and the walker update needs explicit traversal-order and scratch-lifetime handling. The reserve/release suggestion in that review is still the recorded path to evaluate; Windows guard attribution remains on the maintainer side. |
Brings the branch up to date with main a222715. One conflict, in the include block of internal/cbm/lsp/ts_lsp.c: main added "../../../src/foundation/platform.h" where this branch added "extract_node_stack.h". Resolved by keeping both; the next commit replaces the second. Signed-off-by: Martin Vogel <[email protected]>
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]>
|
Thank you, @CaptainMittens. This was a careful fix: you found that the seeding loop alone fills the old 256-slot stacks on a wide file, you pinned both observable sites with tests that fail on the old code, and the "Which arena" write-up made the review easy. Since the review points were already settled and we can push to your branch, we finished them here instead of asking you for another round. What we changed, on top of your two commits (which are untouched):
How we checked it: both of your tests fail on the old code and pass now; the full We will merge once CI is green on the new head. Thank you again for the patience, and for a fix that was easy to build on. |
Signed-off-by: Martin Vogel <[email protected]>
Signed-off-by: Martin Vogel <[email protected]>
|
Thanks @CaptainMittens for fixing the truncated TypeScript walks and adding the wide-file regressions! I added a small follow-up in 060b56a: the two signature passes now share a temporary lookup index, so visiting every declaration no longer repeats a full registry scan. It preserves the first local match and traversal order, and adds checked stack-size arithmetic. The deterministic 300/600-declaration test failed on the original implementation, passed with the fix, and failed again when the index was reverted. The final TypeScript LSP suite passed all 318 tests on macOS arm64 with ASan/UBSan. Thanks again for the contribution—this keeps the larger walks complete without the extra lookup cost. |
|
I also merged current main in 22f41f1 to bring in the shared CI fixes and obtain a fresh hosted result. The PR patch relative to main is byte-for-byte unchanged by that merge, and all of your commits remain intact. Thanks @CaptainMittens! The required GitHub checks are the remaining gate. |
|
Thank you again for the wide-file TypeScript regressions. The October updates record the traversal, allocation-failure, and lookup-cost updates as completed on our side, so no repeat contributor work is requested. Sorry for the delay in the remaining maintainer follow-up—I’ll follow up soon. |
|
Merged -- thank you, @CaptainMittens! You found that the seeding loop alone fills the old 256-slot stacks on any file with more than 256 top-level declarations, so everything past that point was silently skipped, and you pinned both observable sites with regressions that fail on the old code. That made the fix easy to verify and easy to build on. What landed, for the record:
Before merging we also indexed the TypeScript compiler's own src/ (709 files, including compiler/utilities.ts with roughly 890 top-level declarations) with and without the change: the graph came out identical, node for node and edge for edge, so nothing that already resolved has moved. Thanks again for a careful fix and for your patience with the queue! |
The problem
Three AST walks in
internal/cbm/lsp/ts_lsp.cheld at most 256 nodes in a fixedTSNode stack[256]and stopped pushing when it filled. Nothing reported the stop, so each pass answered as if it had seen the whole file.In
rebuild_signatures_from_astandconvert_signature_type_paramsthe seeding loop alone can fill all 256 slots, because it pushes every top-level child of the file. A file with more than 256 top-level declarations therefore skipped every declaration past that point. Each one kept whatever signature the first extraction pass had guessed, and a generic function past the cap keptNAMEDwhere it neededTYPE_PARAM, so calls through it stopped resolving.In
infer_return_type_from_bodythe same cap made a wide function body answer "unknown return type" for areturnthe walk had never reached.The fix
The repo already carries the module that solves this:
internal/cbm/extract_node_stack.h, written for #199 to replace fixedTSNode stack[]arrays that silently drop AST subtrees. Nine extract files use it.ts_lsp.cwas never converted. This converts it.The header gains
ts_nstack_init_arena, which takes an arena directly, because the LSP passes hold aTSLSPContextrather than aCBMExtractCtx.ts_nstack_initkeeps its context argument — that argument is what makes handing over the wrong arena a type error — and now delegates to the new function, so its behaviour is unchanged.Two things follow from using the shared module:
ts_nstack_push_childrenreverses on push. Forinfer_return_type_from_bodythe new order matches the comment the function already carried: it finds the firstreturn, where the old code found the last.O(N^2)loop goes away.ts_nstack_push_childrendoes a single cursor pass instead ofts_node_child(n, i)per child.Which arena
The stacks are cut from
ctx->arena.collect_childrenatts_lsp.c:201already allocates the same kind of per-file scratch from that arena, and the per-file scratch arena added in #1997 never reachescbm_run_ts_lsp—cbm.c:1690passesa. Threading a second arena into this file would touch every allocation in it, which is a larger change than this fix needs.Test
Two tests, one per observable site. Each repeats an existing passing test's claim, moved past the old cap:
tslsp_stress_declarations_past_stack_cap— the claim oftslsp_generic_identity_inference, 300 top-level declarations deeper. Coversconvert_signature_type_params.tslsp_stress_return_past_stack_cap— the claim oftslsp_return_inferred_local, with thereturnbehind 300 statements. Coversinfer_return_type_from_body.Without this change the suite is
303 passed, 2 failed, both failures being these two. With it,305 passed, 0 failed.rebuild_signatures_from_asthas no test of its own: it shares the seeding shape withconvert_signature_type_params, and I could not find an observable difference it produces alone that the first test does not already cover.The full local suite is
7949 passed, 2 failed, 7 skipped. Both failures aresubprocess_run_cleanandsubprocess_run_exit_nonzero, which returnCBM_PROC_SPAWN_FAILEDbecause my local sandbox blocksfork/execof/bin/sh. Nothing in this diff reachesforkorexec, so they are unrelated to it; I did not re-run the full suite on the reverted tree, only thets_lspsuite.