Skip to content

Commit 060b56a

Browse files
committed
fix(ts): keep uncapped signature walks linear
Signed-off-by: Martin Vogel <[email protected]>
1 parent 7e95a5f commit 060b56a

3 files changed

Lines changed: 213 additions & 36 deletions

File tree

‎internal/cbm/lsp/ts_lsp.c‎

Lines changed: 144 additions & 36 deletions
Original file line numberDiff line numberDiff line change
@@ -20,7 +20,7 @@
2020
* cbm_batch_ts_lsp_cross.
2121
*
2222
* Conventions (mirrors c_lsp / go_lsp):
23-
* - All allocations go through ctx->arena; no malloc / free.
23+
* - Persistent results use ctx->arena; temporary walk/index buffers use tracked allocations.
2424
* - ts_emit_resolved_call requires a non-NULL enclosing_func_qn — calls outside any
2525
* function (module top-level) are not emitted.
2626
* - eval_depth caps at TS_LSP_MAX_EVAL_DEPTH to defend against pathological recursion.
@@ -29,6 +29,9 @@
2929
#include "ts_lsp.h"
3030
#include "../../../src/foundation/platform.h"
3131
#include "../helpers.h"
32+
#include "../../../src/foundation/log.h"
33+
#include "../../../src/foundation/mem_core.h"
34+
#include <limits.h>
3235
#include <stdatomic.h>
3336
#include <stdio.h>
3437
#include <stdlib.h>
@@ -61,6 +64,7 @@ void cbm_ts_full_registry_builds_reset(void) {
6164
static _Thread_local long g_ts_type_budget = -1;
6265
static _Thread_local bool g_ts_type_budget_warned;
6366
#ifdef CBM_ENABLE_TEST_SEAMS
67+
static _Thread_local unsigned long g_ts_signature_lookup_work;
6468
static _Thread_local int g_ts_max_member_lookup_steps;
6569
static _Thread_local int g_ts_max_method_lookup_steps;
6670
#endif
@@ -175,6 +179,9 @@ long cbm_ts_lsp_test_budget_remaining(void) {
175179
bool cbm_ts_lsp_test_budget_warned(void) {
176180
return g_ts_type_budget_warned;
177181
}
182+
unsigned long cbm_ts_lsp_test_signature_lookup_work(void) {
183+
return g_ts_signature_lookup_work;
184+
}
178185
int cbm_ts_lsp_test_max_member_lookup_steps(void) {
179186
return g_ts_max_member_lookup_steps;
180187
}
@@ -3957,6 +3964,7 @@ void ts_lsp_init(TSLSPContext *ctx, CBMArena *arena, const char *source, int sou
39573964
if (!ctx)
39583965
return;
39593966
#ifdef CBM_ENABLE_TEST_SEAMS
3967+
g_ts_signature_lookup_work = 0;
39603968
g_ts_max_member_lookup_steps = 0;
39613969
g_ts_max_method_lookup_steps = 0;
39623970
#endif
@@ -4814,6 +4822,22 @@ static void register_file_defs(CBMArena *arena, CBMTypeRegistry *reg, CBMFileRes
48144822
// return walk short of returns it had never reached (#2388).
48154823
enum { TS_WALK_STACK_INLINE = 256 };
48164824

4825+
static int ts_walk_pending_count(int top, uint32_t count, const char *walker) {
4826+
if (top < 0 || count > (uint32_t)(INT_MAX - top)) {
4827+
char pending[24];
4828+
snprintf(pending, sizeof(pending), "%llu", (unsigned long long)count + (unsigned)top);
4829+
cbm_log_error("extract.walk_stack_alloc_failed", "walker", walker, "pending", pending);
4830+
return -1;
4831+
}
4832+
return top + (int)count;
4833+
}
4834+
4835+
#ifdef CBM_ENABLE_TEST_SEAMS
4836+
int cbm_ts_lsp_test_walk_pending_count(int top, uint32_t count) {
4837+
return ts_walk_pending_count(top, count, "ts_lsp_test");
4838+
}
4839+
#endif
4840+
48174841
// Push every child of n in cursor order (one O(N) pass). The walk pops the stack,
48184842
// so children are visited last-child first: the order these walks have always
48194843
// used. False means the stack could not grow; cbm_walk_stack_reserve has logged it.
@@ -4822,8 +4846,9 @@ static bool ts_walk_push_children(TSNode **stack, int *cap, int *top, TSNode n,
48224846
uint32_t count = ts_node_child_count(n);
48234847
if (count == 0)
48244848
return true;
4825-
if (!cbm_walk_stack_reserve((void **)stack, cap, *top + (int)count, sizeof(TSNode), inline_buf,
4826-
walker))
4849+
int need = ts_walk_pending_count(*top, count, walker);
4850+
if (need < 0 ||
4851+
!cbm_walk_stack_reserve((void **)stack, cap, need, sizeof(TSNode), inline_buf, walker))
48274852
return false;
48284853
TSTreeCursor cursor = ts_tree_cursor_new(n);
48294854
if (ts_tree_cursor_goto_first_child(&cursor)) {
@@ -4839,7 +4864,9 @@ static bool ts_walk_push_children(TSNode **stack, int *cap, int *top, TSNode n,
48394864

48404865
static bool ts_walk_push(TSNode **stack, int *cap, int *top, TSNode n, const TSNode *inline_buf,
48414866
const char *walker) {
4842-
if (!cbm_walk_stack_reserve((void **)stack, cap, *top + 1, sizeof(TSNode), inline_buf, walker))
4867+
int need = ts_walk_pending_count(*top, 1, walker);
4868+
if (need < 0 ||
4869+
!cbm_walk_stack_reserve((void **)stack, cap, need, sizeof(TSNode), inline_buf, walker))
48434870
return false;
48444871
(*stack)[(*top)++] = n;
48454872
return true;
@@ -4891,14 +4918,98 @@ static const CBMType *infer_return_type_from_body(TSLSPContext *ctx, TSNode body
48914918
return found;
48924919
}
48934920

4921+
// These two AST passes patch the FIRST matching local registration, even when
4922+
// the general registry index prefers the last duplicate. Do not follow fallback
4923+
// or copy its entries into the overlay. The snapshot lives only across these
4924+
// passes, which mutate signatures but never append or rename registered funcs.
4925+
typedef struct {
4926+
CBMRegisteredFunc **slots;
4927+
size_t capacity;
4928+
} TSSignatureIndex;
4929+
4930+
static void ts_signature_work(void) {
4931+
#ifdef CBM_ENABLE_TEST_SEAMS
4932+
g_ts_signature_lookup_work++;
4933+
#endif
4934+
}
4935+
4936+
static size_t ts_signature_slot(const TSSignatureIndex *index, const char *qn) {
4937+
uint64_t hash = 0xcbf29ce484222325ULL;
4938+
for (const unsigned char *p = (const unsigned char *)qn; *p; p++) {
4939+
hash ^= *p;
4940+
hash *= 0x100000001b3ULL;
4941+
}
4942+
size_t slot = (size_t)hash & (index->capacity - 1);
4943+
for (;;) {
4944+
ts_signature_work();
4945+
if (!index->slots[slot] || strcmp(index->slots[slot]->qualified_name, qn) == 0)
4946+
return slot;
4947+
slot = (slot + 1) & (index->capacity - 1);
4948+
}
4949+
}
4950+
4951+
static TSSignatureIndex ts_signature_index(CBMTypeRegistry *reg) {
4952+
TSSignatureIndex index = {0};
4953+
if (reg->func_count <= 0 || (size_t)reg->func_count > SIZE_MAX / 2)
4954+
return index;
4955+
size_t capacity = 16;
4956+
while (capacity < (size_t)reg->func_count * 2) {
4957+
if (capacity > SIZE_MAX / 2)
4958+
return index;
4959+
capacity *= 2;
4960+
}
4961+
if (capacity > SIZE_MAX / sizeof(*index.slots))
4962+
return index;
4963+
index.slots = cbm_alloc(CBM_MEM_CLASS_EXTRACT, capacity * sizeof(*index.slots));
4964+
if (!index.slots)
4965+
return index; // Preserve the original lookup on allocation failure.
4966+
index.capacity = capacity;
4967+
memset(index.slots, 0, capacity * sizeof(*index.slots));
4968+
for (int i = 0; i < reg->func_count; i++) {
4969+
ts_signature_work();
4970+
CBMRegisteredFunc *func = &reg->funcs[i];
4971+
if (!func->qualified_name)
4972+
continue;
4973+
size_t slot = ts_signature_slot(&index, func->qualified_name);
4974+
if (!index.slots[slot])
4975+
index.slots[slot] = func;
4976+
}
4977+
return index;
4978+
}
4979+
4980+
static CBMRegisteredFunc *ts_signature_func(CBMTypeRegistry *reg, const TSSignatureIndex *index,
4981+
const char *qn) {
4982+
if (!qn)
4983+
return NULL;
4984+
if (index->slots)
4985+
return index->slots[ts_signature_slot(index, qn)];
4986+
for (int i = 0; i < reg->func_count; i++) {
4987+
ts_signature_work();
4988+
if (reg->funcs[i].qualified_name && strcmp(reg->funcs[i].qualified_name, qn) == 0)
4989+
return &reg->funcs[i];
4990+
}
4991+
return NULL;
4992+
}
4993+
4994+
#ifdef CBM_ENABLE_TEST_SEAMS
4995+
int cbm_ts_lsp_test_signature_func_index(CBMTypeRegistry *reg, const char *qn) {
4996+
TSSignatureIndex index = ts_signature_index(reg);
4997+
CBMRegisteredFunc *func = ts_signature_func(reg, &index, qn);
4998+
int result = func ? (int)(func - reg->funcs) : -1;
4999+
cbm_free(CBM_MEM_CLASS_EXTRACT, index.slots);
5000+
return result;
5001+
}
5002+
#endif
5003+
48945004
// Rebuild a function's CBMRegisteredFunc signature from the AST directly. extract_defs
48955005
// only handles type_identifier / generic_type / predefined_type for params, so function
48965006
// types (`(x: Foo) => void`), object types, tuple types etc. are missing from
48975007
// def->param_types. This pass walks the AST and rebuilds signatures from scratch.
48985008
//
48995009
// Called after `register_file_defs` so the func entries already exist; we only mutate
49005010
// in place.
4901-
static void rebuild_signatures_from_ast(TSLSPContext *ctx, TSNode root, CBMTypeRegistry *reg) {
5011+
static void rebuild_signatures_from_ast(TSLSPContext *ctx, TSNode root, CBMTypeRegistry *reg,
5012+
const TSSignatureIndex *index) {
49025013
if (ts_node_is_null(root) || !reg || !ctx->module_qn)
49035014
return;
49045015

@@ -5039,23 +5150,17 @@ static void rebuild_signatures_from_ast(TSLSPContext *ctx, TSNode root, CBMTypeR
50395150
// Build new signature and patch in registry.
50405151
const CBMType *rets[2] = {ret, NULL};
50415152
const CBMType *new_sig = cbm_type_func(ctx->arena, p_names, p_types, rets);
5042-
for (int fi = 0; fi < reg->func_count; fi++) {
5043-
if (!reg->funcs[fi].qualified_name)
5044-
continue;
5045-
if (strcmp(reg->funcs[fi].qualified_name, fqn) != 0)
5046-
continue;
5153+
CBMRegisteredFunc *func = ts_signature_func(reg, index, fqn);
5154+
if (func) {
50475155
// Preserve the ret type if AST gave UNKNOWN but the existing reg sig had one.
5048-
if (cbm_type_is_unknown(ret) && reg->funcs[fi].signature &&
5049-
reg->funcs[fi].signature->kind == CBM_TYPE_FUNC &&
5050-
reg->funcs[fi].signature->data.func.return_types &&
5051-
reg->funcs[fi].signature->data.func.return_types[0] &&
5052-
!cbm_type_is_unknown(reg->funcs[fi].signature->data.func.return_types[0])) {
5053-
const CBMType *preserved[2] = {reg->funcs[fi].signature->data.func.return_types[0],
5054-
NULL};
5156+
if (cbm_type_is_unknown(ret) && func->signature &&
5157+
func->signature->kind == CBM_TYPE_FUNC && func->signature->data.func.return_types &&
5158+
func->signature->data.func.return_types[0] &&
5159+
!cbm_type_is_unknown(func->signature->data.func.return_types[0])) {
5160+
const CBMType *preserved[2] = {func->signature->data.func.return_types[0], NULL};
50555161
new_sig = cbm_type_func(ctx->arena, p_names, p_types, preserved);
50565162
}
5057-
reg->funcs[fi].signature = new_sig;
5058-
break;
5163+
func->signature = new_sig;
50595164
}
50605165
}
50615166
cbm_walk_stack_release(stack, inline_stack);
@@ -5064,7 +5169,8 @@ static void rebuild_signatures_from_ast(TSLSPContext *ctx, TSNode root, CBMTypeR
50645169
// Convert NAMED references to TYPE_PARAM for any function whose declaration has a
50655170
// `type_parameters` block. Without this, generic functions like `function id<T>(x: T): T`
50665171
// register T as NAMED("module.T") instead of TYPE_PARAM("T"), defeating substitution.
5067-
static void convert_signature_type_params(TSLSPContext *ctx, TSNode root, CBMTypeRegistry *reg) {
5172+
static void convert_signature_type_params(TSLSPContext *ctx, TSNode root, CBMTypeRegistry *reg,
5173+
const TSSignatureIndex *index) {
50685174
if (ts_node_is_null(root) || !reg || !ctx->module_qn)
50695175
return;
50705176

@@ -5171,32 +5277,37 @@ static void convert_signature_type_params(TSLSPContext *ctx, TSNode root, CBMTyp
51715277
}
51725278

51735279
// Patch the registered func's signature: rewrite NAMED → TYPE_PARAM.
5174-
for (int fi = 0; fi < reg->func_count; fi++) {
5175-
if (!reg->funcs[fi].qualified_name)
5176-
continue;
5177-
if (strcmp(reg->funcs[fi].qualified_name, fqn) != 0)
5178-
continue;
5179-
const CBMType *old_sig = reg->funcs[fi].signature;
5280+
CBMRegisteredFunc *func = ts_signature_func(reg, index, fqn);
5281+
if (func) {
5282+
const CBMType *old_sig = func->signature;
51805283
if (!old_sig)
5181-
break;
5284+
continue;
51825285
const CBMType *new_sig = cbm_type_substitute(ctx->arena, old_sig, names, args);
51835286
if (new_sig)
5184-
reg->funcs[fi].signature = new_sig;
5287+
func->signature = new_sig;
51855288
// Also store the type_param_names for later overload-by-types use.
51865289
const char **stored = (const char **)cbm_arena_alloc(
51875290
ctx->arena, (size_t)(tpc + 1) * sizeof(const char *));
51885291
if (stored) {
51895292
for (int ti = 0; ti < tpc; ti++)
51905293
stored[ti] = names[ti];
51915294
stored[tpc] = NULL;
5192-
reg->funcs[fi].type_param_names = stored;
5295+
func->type_param_names = stored;
51935296
}
5194-
break;
51955297
}
51965298
}
51975299
cbm_walk_stack_release(stack, inline_stack);
51985300
}
51995301

5302+
// Build once after shape registration, then release before later passes may
5303+
// grow the registry. This keeps per-file lookup storage out of the result arena.
5304+
static void refine_ast_signatures(TSLSPContext *ctx, TSNode root, CBMTypeRegistry *reg) {
5305+
TSSignatureIndex index = ts_signature_index(reg);
5306+
rebuild_signatures_from_ast(ctx, root, reg, &index);
5307+
convert_signature_type_params(ctx, root, reg, &index);
5308+
cbm_free(CBM_MEM_CLASS_EXTRACT, index.slots);
5309+
}
5310+
52005311
// Parse a JSDoc comment block for `@param {T} name` and `@returns {T}` tags. For each
52015312
// match, returns the type as a parsed CBMType. Used in `js_mode` to infer signatures
52025313
// for JavaScript files where there are no inline type annotations.
@@ -5839,8 +5950,7 @@ void cbm_run_ts_lsp(CBMArena *arena, CBMFileResult *result, const char *source,
58395950
}
58405951

58415952
ast_sweep_shapes(&ctx, root, &reg);
5842-
rebuild_signatures_from_ast(&ctx, root, &reg);
5843-
convert_signature_type_params(&ctx, root, &reg);
5953+
refine_ast_signatures(&ctx, root, &reg);
58445954
apply_jsdoc_signatures(&ctx, root, &reg);
58455955
infer_implicit_returns(&ctx, root, &reg);
58465956

@@ -6093,8 +6203,7 @@ void cbm_run_ts_lsp_cross_with_registry(CBMArena *arena, const char *source, int
60936203
}
60946204

60956205
ast_sweep_shapes(&ctx, root, &overlay);
6096-
rebuild_signatures_from_ast(&ctx, root, &overlay);
6097-
convert_signature_type_params(&ctx, root, &overlay);
6206+
refine_ast_signatures(&ctx, root, &overlay);
60986207
apply_jsdoc_signatures(&ctx, root, &overlay);
60996208
infer_implicit_returns(&ctx, root, &overlay);
61006209

@@ -6309,8 +6418,7 @@ void cbm_run_ts_lsp_cross(CBMArena *arena, const char *source, int source_len,
63096418
}
63106419

63116420
ast_sweep_shapes(&ctx, root, &reg);
6312-
rebuild_signatures_from_ast(&ctx, root, &reg);
6313-
convert_signature_type_params(&ctx, root, &reg);
6421+
refine_ast_signatures(&ctx, root, &reg);
63146422
apply_jsdoc_signatures(&ctx, root, &reg);
63156423
infer_implicit_returns(&ctx, root, &reg);
63166424

‎internal/cbm/lsp/ts_lsp.h‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -72,6 +72,11 @@ typedef struct {
7272
// for the calling thread, valid after a cbm_run_ts_lsp on the same thread.
7373
long cbm_ts_lsp_test_budget_remaining(void);
7474
bool cbm_ts_lsp_test_budget_warned(void);
75+
// Registry entries/probes visited by the two AST signature passes in the last run.
76+
unsigned long cbm_ts_lsp_test_signature_lookup_work(void);
77+
// Inspect signature-index selection and checked walker addition without huge ASTs.
78+
int cbm_ts_lsp_test_signature_func_index(CBMTypeRegistry *reg, const char *qn);
79+
int cbm_ts_lsp_test_walk_pending_count(int top, uint32_t count);
7580
// Maximum recursive calls in one member/method lookup during the last TS LSP run,
7681
// including attempts rejected by the depth or visited-type guard.
7782
int cbm_ts_lsp_test_max_member_lookup_steps(void);

0 commit comments

Comments
 (0)