Skip to content

Commit 214a9ac

Browse files
committed
fix(ruby-lsp): build constant paths in one pass
ruby_const_path recursed once per :: segment and re-formatted the growing prefix at every level, so an A::B::C path cost one stack frame per segment and quadratic bytes in the per-file arena. It now follows the scope fields in a loop: one pass measures the segments, a second copies them right to left into a single buffer. The result is the same string as before, including a leading ::Foo and a scope that is not a constant path. rubylsp_const_path_is_linear pins the arena bytes for an 800 vs a 1,600 segment path (before: 494,520 -> 1,660,520 bytes already at 400 -> 800 segments; after: 136,248 -> 150,848 at 800 -> 1,600) and the exact class QN for a five-level path and for a rooted ::Top::Inner. Signed-off-by: Martin Vogel <[email protected]>
1 parent 0210ea9 commit 214a9ac

2 files changed

Lines changed: 135 additions & 11 deletions

File tree

‎internal/cbm/lsp/ruby_lsp.c‎

Lines changed: 66 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -114,10 +114,52 @@ static char *ruby_node_text(RubyLSPContext *ctx, TSNode node) {
114114
return cbm_node_text(ctx->arena, node, ctx->source);
115115
}
116116

117+
/* Byte length of a node's source text (0 for an empty node). */
118+
static size_t ruby_node_len(TSNode node) {
119+
uint32_t start = ts_node_start_byte(node);
120+
uint32_t end = ts_node_end_byte(node);
121+
return end > start ? (size_t)(end - start) : 0;
122+
}
123+
124+
/* One step left along a constant path. `*cur` is a scope_resolution whose
125+
* own segment has been taken; on success `*seg` is the next segment to its
126+
* left and `*cur` the node to continue from. The path ends at a missing
127+
* scope (`::Foo`), at a scope that is not a constant path (`expr::Foo`),
128+
* and at an empty segment. A plain `constant` has no scope field, so it is
129+
* always the last segment. */
130+
static bool ruby_const_step(TSNode *cur, TSNode *seg) {
131+
TSNode scope = ts_node_child_by_field_name(*cur, "scope", 5);
132+
if (ts_node_is_null(scope))
133+
return false;
134+
const char *k = ts_node_type(scope);
135+
if (strcmp(k, "constant") == 0) {
136+
if (ruby_node_len(scope) == 0)
137+
return false;
138+
*seg = scope;
139+
*cur = scope;
140+
return true;
141+
}
142+
if (strcmp(k, "scope_resolution") != 0)
143+
return false;
144+
TSNode name = ts_node_child_by_field_name(scope, "name", 4);
145+
if (ts_node_is_null(name) || ruby_node_len(name) == 0)
146+
return false;
147+
*seg = name;
148+
*cur = scope;
149+
return true;
150+
}
151+
117152
/* Convert a constant expression node (constant | scope_resolution) into a
118153
* dotted path ("Foo", "A.B.C"). Returns NULL for anything else. A leading
119154
* "::Foo" (scope_resolution without a scope) yields "Foo" — the resolver's
120-
* table probe covers the top-level meaning. */
155+
* table probe covers the top-level meaning. A scope that is not itself a
156+
* constant path (`expr::Foo`) contributes nothing.
157+
*
158+
* `A::B::C` nests to the LEFT (scope_resolution(scope_resolution(A, B), C)),
159+
* so the path is read from the outermost node along the `scope` fields: one
160+
* pass measures the segments, a second copies them right to left into one
161+
* buffer. No recursion and no re-formatting of a growing prefix, so neither
162+
* stack depth nor bytes grow faster than the path itself. */
121163
static const char *ruby_const_path(RubyLSPContext *ctx, TSNode node) {
122164
if (ts_node_is_null(node))
123165
return NULL;
@@ -126,19 +168,32 @@ static const char *ruby_const_path(RubyLSPContext *ctx, TSNode node) {
126168
return ruby_node_text(ctx, node);
127169
if (strcmp(k, "scope_resolution") != 0)
128170
return NULL;
129-
TSNode scope = ts_node_child_by_field_name(node, "scope", 5);
130171
TSNode name = ts_node_child_by_field_name(node, "name", 4);
131-
if (ts_node_is_null(name))
172+
if (ts_node_is_null(name) || ruby_node_len(name) == 0)
132173
return NULL;
133-
char *nm = ruby_node_text(ctx, name);
134-
if (!nm || !nm[0])
174+
175+
size_t total = 0;
176+
TSNode cur = node;
177+
TSNode seg = name;
178+
do {
179+
total += ruby_node_len(seg) + 1; /* segment + its '.' (or the NUL) */
180+
} while (ruby_const_step(&cur, &seg));
181+
182+
char *out = (char *)cbm_arena_alloc(ctx->arena, total);
183+
if (!out)
135184
return NULL;
136-
if (ts_node_is_null(scope))
137-
return nm; /* ::Foo */
138-
const char *sp = ruby_const_path(ctx, scope);
139-
if (!sp || !sp[0])
140-
return nm;
141-
return cbm_arena_sprintf(ctx->arena, "%s.%s", sp, nm);
185+
size_t pos = total - 1;
186+
out[pos] = '\0';
187+
cur = node;
188+
seg = name;
189+
do {
190+
size_t len = ruby_node_len(seg);
191+
pos -= len;
192+
memcpy(out + pos, ctx->source + ts_node_start_byte(seg), len);
193+
if (pos > 0)
194+
out[--pos] = '.';
195+
} while (ruby_const_step(&cur, &seg));
196+
return out;
142197
}
143198

144199
/* Join two dotted path fragments; either side may be empty/NULL. */

‎tests/test_ruby_lsp.c‎

Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1430,6 +1430,74 @@ TEST(rubylsp_mixin_walk_visits_each_module_once) {
14301430
PASS();
14311431
}
14321432

1433+
/* `class Probe; def run; S0::S1::...::S<n-1>.new; end; end` */
1434+
static char *rubylsp_deep_const_src(int n) {
1435+
size_t cap = (size_t)n * 12 + 128;
1436+
char *src = (char *)malloc(cap);
1437+
if (!src)
1438+
return NULL;
1439+
size_t off = (size_t)snprintf(src, cap, "class Probe\n def run\n ");
1440+
for (int i = 0; i < n; i++)
1441+
off += (size_t)snprintf(src + off, cap - off, i ? "::S%d" : "S%d", i);
1442+
(void)snprintf(src + off, cap - off, ".new\n end\nend\n");
1443+
return src;
1444+
}
1445+
1446+
static size_t rubylsp_deep_const_bytes(int n) {
1447+
char *src = rubylsp_deep_const_src(n);
1448+
if (!src)
1449+
return 0;
1450+
size_t bytes = 0;
1451+
(void)rubylsp_counted_work(src, &bytes);
1452+
free(src);
1453+
return bytes;
1454+
}
1455+
1456+
/* Review ask (b): a constant path is built in one pass. Recursing once per
1457+
* `::` and re-formatting the growing prefix at every level costs one stack
1458+
* frame per segment and quadratic bytes; the loop has no recursion and
1459+
* writes the path once. The positive control pins the exact class QN for a
1460+
* deep path and for a leading `::`. */
1461+
TEST(rubylsp_const_path_is_linear) {
1462+
size_t b_n = rubylsp_deep_const_bytes(800);
1463+
size_t b_2n = rubylsp_deep_const_bytes(1600);
1464+
printf(" const path arena bytes: n=800 %zu, n=1600 %zu\n", b_n, b_2n);
1465+
ASSERT(b_n > 0);
1466+
ASSERT(b_2n <= 3 * b_n);
1467+
1468+
const char *src = "module L0\n"
1469+
" module L1\n"
1470+
" module L2\n"
1471+
" module L3\n"
1472+
" module L4\n"
1473+
" class Leaf\n"
1474+
" end\n"
1475+
" end\n"
1476+
" end\n"
1477+
" end\n"
1478+
" end\n"
1479+
"end\n"
1480+
"class Top\n"
1481+
" class Inner\n"
1482+
" end\n"
1483+
"end\n"
1484+
"class Caller\n"
1485+
" def deep\n"
1486+
" L0::L1::L2::L3::L4::Leaf.new\n"
1487+
" end\n"
1488+
" def rooted\n"
1489+
" ::Top::Inner.new\n"
1490+
" end\n"
1491+
"end\n";
1492+
CBMFileResult *r = extract_ruby(src);
1493+
ASSERT(r);
1494+
ASSERT(require_resolved_exact(r, "test.main.Caller.deep", "test.main.L0.L1.L2.L3.L4.Leaf") >=
1495+
0);
1496+
ASSERT(require_resolved_exact(r, "test.main.Caller.rooted", "test.main.Top.Inner") >= 0);
1497+
cbm_free_result(r);
1498+
PASS();
1499+
}
1500+
14331501
/* ── suite ──────────────────────────────────────────────────────── */
14341502

14351503
void suite_ruby_lsp(void) {
@@ -1467,4 +1535,5 @@ void suite_ruby_lsp(void) {
14671535
RUN_TEST(rubylsp_dynamic_dispatch_family_no_edge);
14681536
RUN_TEST(rubylsp_self_rebinding_blocks_no_edge);
14691537
RUN_TEST(rubylsp_mixin_walk_visits_each_module_once);
1538+
RUN_TEST(rubylsp_const_path_is_linear);
14701539
}

0 commit comments

Comments
 (0)