Skip to content

Commit 0210ea9

Browse files
committed
fix(ruby-lsp): search each ancestor once per method lookup
The mixin walk recursed into prepend and include at every level with only the depth cap of 16 as a bound, so a module that both prepends and includes the next one doubled the paths per level: a miss on a chain of n such modules cost 2^n visits (measured 4 -> 20,744 for n = 2..14). Each lookup is now one walk that carries the fail-closed blocked flag and a visit stamp. Ruby linearizes ancestors, so a module reached a second time in one walk was already searched and missed (a hit or a block would have ended the walk); skipping the repeat keeps every lookup linear in the ancestors the file declares. Lookup order, hits and the fail-closed rules are unchanged. The stamps live on the per-file class table, so the walk allocates nothing. The walk entries feed CBM_LSP_WORK (seam builds only; product builds compile it to nothing). rubylsp_mixin_walk_visits_each_module_once pins linear work for the doubled chain on the instance and the class side (before: 66 -> 4,098 visits for n = 6 -> 12; after: 14 -> 26) and keeps a diamond and a prepend-plus-include pair resolving exactly once. Signed-off-by: Martin Vogel <[email protected]>
1 parent 41f27cc commit 0210ea9

3 files changed

Lines changed: 214 additions & 43 deletions

File tree

‎internal/cbm/lsp/ruby_lsp.c‎

Lines changed: 92 additions & 43 deletions
Original file line numberDiff line numberDiff line change
@@ -78,6 +78,7 @@
7878
*/
7979

8080
#include "ruby_lsp.h"
81+
#include "lsp_work.h"
8182
#include "../helpers.h"
8283
#include "../arena.h"
8384
#include <ctype.h>
@@ -470,12 +471,53 @@ static const CBMRegisteredFunc *ruby_own_singleton_method(RubyLSPContext *ctx, c
470471
* from that point on no hit is trustworthy and callers must emit nothing —
471472
* including NOT falling through to a same-named top-level def or to the
472473
* Object typing fallback. Hits found BEFORE the unseen ancestor in Ruby's
473-
* lookup order are still returned. */
474+
* lookup order are still returned.
475+
*
476+
* Each lookup is one walk: the `blocked` flag plus a visit stamp. Ruby
477+
* linearizes ancestors, so a module reached a second time in one walk
478+
* (`prepend M; include M`, two includes sharing a module) was already
479+
* searched and missed: a hit or a block would have ended the walk. Skipping
480+
* the repeat keeps a lookup linear in the ancestors it can see; without it
481+
* every module that both prepends and includes the next one doubles the
482+
* paths per level. */
483+
typedef struct {
484+
bool blocked;
485+
unsigned int stamp;
486+
} RubyLookupWalk;
487+
488+
static RubyLookupWalk ruby_walk_begin(RubyLSPContext *ctx) {
489+
if (++ctx->lookup_stamp == 0) {
490+
/* Wrapped: clear every mark so no class looks visited. */
491+
for (int i = 0; i < ctx->class_count; i++) {
492+
ctx->classes[i].seen_instance = 0;
493+
ctx->classes[i].seen_singleton = 0;
494+
}
495+
ctx->lookup_stamp = 1;
496+
}
497+
RubyLookupWalk w = {false, ctx->lookup_stamp};
498+
return w;
499+
}
500+
501+
/* Marks `class_qn` searched on one side (instance or singleton) in this walk;
502+
* true when it already was. Only the file's class table is marked: mixins
503+
* and superclass refs are recorded for those classes alone, so a type outside
504+
* the table (a stdlib type) has nothing to expand and is never a repeat. */
505+
static bool ruby_walk_seen(RubyLSPContext *ctx, RubyLookupWalk *w, const char *class_qn,
506+
bool singleton) {
507+
RubyClassInfo *ci = ruby_class_by_qn(ctx, class_qn);
508+
if (!ci)
509+
return false;
510+
unsigned int *mark = singleton ? &ci->seen_singleton : &ci->seen_instance;
511+
if (*mark == w->stamp)
512+
return true;
513+
*mark = w->stamp;
514+
return false;
515+
}
474516

475517
static const CBMRegisteredFunc *ruby_lookup_instance_method_depth(RubyLSPContext *ctx,
476518
const char *class_qn,
477519
const char *method_name,
478-
int depth, bool *blocked);
520+
int depth, RubyLookupWalk *w);
479521

480522
/* True when the class declares a superclass the finalize step could not
481523
* resolve (stdlib-seeded conventions like ApplicationRecord DO resolve). */
@@ -489,18 +531,18 @@ static bool ruby_superclass_unresolved(RubyLSPContext *ctx, const char *class_qn
489531
* before any hit blocks the walk. */
490532
static const CBMRegisteredFunc *ruby_lookup_in_mixins(RubyLSPContext *ctx, const char *owner_qn,
491533
RubyMixinKind kind, const char *method_name,
492-
int depth, bool *blocked) {
534+
int depth, RubyLookupWalk *w) {
493535
for (int i = ctx->mixin_count - 1; i >= 0; i--) {
494536
RubyMixinInfo *mi = &ctx->mixins[i];
495537
if (mi->kind != kind || strcmp(mi->owner_qn, owner_qn) != 0)
496538
continue;
497539
if (!mi->module_qn) {
498-
*blocked = true; /* unseen module — it may define/shadow the method */
540+
w->blocked = true; /* unseen module — it may define/shadow the method */
499541
return NULL;
500542
}
501543
const CBMRegisteredFunc *f =
502-
ruby_lookup_instance_method_depth(ctx, mi->module_qn, method_name, depth + 1, blocked);
503-
if (f || *blocked)
544+
ruby_lookup_instance_method_depth(ctx, mi->module_qn, method_name, depth + 1, w);
545+
if (f || w->blocked)
504546
return f;
505547
}
506548
return NULL;
@@ -509,29 +551,32 @@ static const CBMRegisteredFunc *ruby_lookup_in_mixins(RubyLSPContext *ctx, const
509551
static const CBMRegisteredFunc *ruby_lookup_instance_method_depth(RubyLSPContext *ctx,
510552
const char *class_qn,
511553
const char *method_name,
512-
int depth, bool *blocked) {
554+
int depth, RubyLookupWalk *w) {
513555
if (!ctx || !class_qn || !method_name || depth > RUBY_LOOKUP_MAX_DEPTH)
514556
return NULL;
557+
CBM_LSP_WORK(1);
558+
if (ruby_walk_seen(ctx, w, class_qn, false))
559+
return NULL; /* searched earlier in this walk: a repeat can only miss */
515560
/* Prepended modules shadow the class's own methods — an unresolved
516561
* prepend therefore blocks even an own-method hit. */
517562
const CBMRegisteredFunc *f =
518-
ruby_lookup_in_mixins(ctx, class_qn, RUBY_MIXIN_PREPEND, method_name, depth, blocked);
519-
if (f || *blocked)
563+
ruby_lookup_in_mixins(ctx, class_qn, RUBY_MIXIN_PREPEND, method_name, depth, w);
564+
if (f || w->blocked)
520565
return f;
521566
f = ruby_own_instance_method(ctx, class_qn, method_name);
522567
if (f)
523568
return f;
524569
/* An unresolved include stops the walk before the superclass chain. */
525-
f = ruby_lookup_in_mixins(ctx, class_qn, RUBY_MIXIN_INCLUDE, method_name, depth, blocked);
526-
if (f || *blocked)
570+
f = ruby_lookup_in_mixins(ctx, class_qn, RUBY_MIXIN_INCLUDE, method_name, depth, w);
571+
if (f || w->blocked)
527572
return f;
528573
if (ruby_superclass_unresolved(ctx, class_qn)) {
529-
*blocked = true;
574+
w->blocked = true;
530575
return NULL;
531576
}
532577
const char *sup = ruby_superclass_qn(ctx, class_qn);
533578
if (sup && strcmp(sup, class_qn) != 0)
534-
return ruby_lookup_instance_method_depth(ctx, sup, method_name, depth + 1, blocked);
579+
return ruby_lookup_instance_method_depth(ctx, sup, method_name, depth + 1, w);
535580
return NULL;
536581
}
537582

@@ -540,10 +585,10 @@ static const CBMRegisteredFunc *ruby_lookup_instance_method_depth(RubyLSPContext
540585
static const CBMRegisteredFunc *ruby_lookup_instance_method_b(RubyLSPContext *ctx,
541586
const char *class_qn,
542587
const char *method_name,
543-
bool *blocked) {
588+
RubyLookupWalk *w) {
544589
const CBMRegisteredFunc *f =
545-
ruby_lookup_instance_method_depth(ctx, class_qn, method_name, 0, blocked);
546-
if (f || *blocked)
590+
ruby_lookup_instance_method_depth(ctx, class_qn, method_name, 0, w);
591+
if (f || w->blocked)
547592
return f;
548593
/* Universal receiver fallback (Object / ActiveSupport predicates) —
549594
* typing only; Object methods are stdlib entries, never project defs. */
@@ -554,37 +599,44 @@ static const CBMRegisteredFunc *ruby_lookup_instance_method_b(RubyLSPContext *ct
554599

555600
const CBMRegisteredFunc *ruby_lookup_instance_method(RubyLSPContext *ctx, const char *class_qn,
556601
const char *method_name) {
557-
bool blocked = false;
558-
return ruby_lookup_instance_method_b(ctx, class_qn, method_name, &blocked);
602+
if (!ctx)
603+
return NULL;
604+
RubyLookupWalk w = ruby_walk_begin(ctx);
605+
return ruby_lookup_instance_method_b(ctx, class_qn, method_name, &w);
559606
}
560607

561608
static const CBMRegisteredFunc *ruby_lookup_singleton_method_depth(RubyLSPContext *ctx,
562609
const char *class_qn,
563610
const char *method_name,
564-
int depth, bool *blocked) {
611+
int depth, RubyLookupWalk *w) {
565612
if (!ctx || !class_qn || !method_name || depth > RUBY_LOOKUP_MAX_DEPTH)
566613
return NULL;
614+
CBM_LSP_WORK(1);
615+
if (ruby_walk_seen(ctx, w, class_qn, true))
616+
return NULL; /* searched earlier in this walk: a repeat can only miss */
567617
const CBMRegisteredFunc *f = ruby_own_singleton_method(ctx, class_qn, method_name);
568618
if (f)
569619
return f;
570620
/* `extend Mod` adds Mod's instance methods class-side. */
571-
f = ruby_lookup_in_mixins(ctx, class_qn, RUBY_MIXIN_EXTEND, method_name, depth, blocked);
572-
if (f || *blocked)
621+
f = ruby_lookup_in_mixins(ctx, class_qn, RUBY_MIXIN_EXTEND, method_name, depth, w);
622+
if (f || w->blocked)
573623
return f;
574624
if (ruby_superclass_unresolved(ctx, class_qn)) {
575-
*blocked = true;
625+
w->blocked = true;
576626
return NULL;
577627
}
578628
const char *sup = ruby_superclass_qn(ctx, class_qn);
579629
if (sup && strcmp(sup, class_qn) != 0)
580-
return ruby_lookup_singleton_method_depth(ctx, sup, method_name, depth + 1, blocked);
630+
return ruby_lookup_singleton_method_depth(ctx, sup, method_name, depth + 1, w);
581631
return NULL;
582632
}
583633

584634
const CBMRegisteredFunc *ruby_lookup_singleton_method(RubyLSPContext *ctx, const char *class_qn,
585635
const char *method_name) {
586-
bool blocked = false;
587-
return ruby_lookup_singleton_method_depth(ctx, class_qn, method_name, 0, &blocked);
636+
if (!ctx)
637+
return NULL;
638+
RubyLookupWalk w = ruby_walk_begin(ctx);
639+
return ruby_lookup_singleton_method_depth(ctx, class_qn, method_name, 0, &w);
588640
}
589641

590642
/* ── ActiveRecord model detection (typing special case) ─────────── */
@@ -878,13 +930,11 @@ static const CBMType *ruby_eval_call_type(RubyLSPContext *ctx, TSNode call, bool
878930
if (ctx->self_unknown)
879931
return cbm_type_unknown(); /* receiver is a rebound self — zero-edge */
880932
if (ctx->enclosing_class_qn) {
881-
bool blocked = false;
933+
RubyLookupWalk w = ruby_walk_begin(ctx);
882934
const CBMRegisteredFunc *f =
883935
ctx->in_singleton_method
884-
? ruby_lookup_singleton_method_depth(ctx, ctx->enclosing_class_qn, mname, 0,
885-
&blocked)
886-
: ruby_lookup_instance_method_depth(ctx, ctx->enclosing_class_qn, mname, 0,
887-
&blocked);
936+
? ruby_lookup_singleton_method_depth(ctx, ctx->enclosing_class_qn, mname, 0, &w)
937+
: ruby_lookup_instance_method_depth(ctx, ctx->enclosing_class_qn, mname, 0, &w);
888938
if (f) {
889939
if (emit)
890940
ruby_emit_resolved(ctx, f->qualified_name, "ruby_self_dispatch", RUBY_CONF_HIGH,
@@ -893,7 +943,7 @@ static const CBMType *ruby_eval_call_type(RubyLSPContext *ctx, TSNode call, bool
893943
}
894944
/* An unseen ancestor may define this method: do NOT fall through
895945
* to a same-named top-level def. */
896-
if (blocked)
946+
if (w.blocked)
897947
return cbm_type_unknown();
898948
}
899949
const CBMRegisteredFunc *f =
@@ -915,12 +965,11 @@ static const CBMType *ruby_eval_call_type(RubyLSPContext *ctx, TSNode call, bool
915965
if (strcmp(rk, "self") == 0) {
916966
if (!ctx->enclosing_class_qn || ctx->self_unknown)
917967
return cbm_type_unknown();
918-
bool blocked = false;
919-
const CBMRegisteredFunc *f = ctx->in_singleton_method
920-
? ruby_lookup_singleton_method_depth(
921-
ctx, ctx->enclosing_class_qn, mname, 0, &blocked)
922-
: ruby_lookup_instance_method_depth(
923-
ctx, ctx->enclosing_class_qn, mname, 0, &blocked);
968+
RubyLookupWalk w = ruby_walk_begin(ctx);
969+
const CBMRegisteredFunc *f =
970+
ctx->in_singleton_method
971+
? ruby_lookup_singleton_method_depth(ctx, ctx->enclosing_class_qn, mname, 0, &w)
972+
: ruby_lookup_instance_method_depth(ctx, ctx->enclosing_class_qn, mname, 0, &w);
924973
if (f) {
925974
if (emit)
926975
ruby_emit_resolved(ctx, f->qualified_name, "ruby_self_dispatch", RUBY_CONF_HIGH,
@@ -967,22 +1016,22 @@ static void ruby_resolve_super(RubyLSPContext *ctx, TSNode site) {
9671016
const char *mname = strrchr(fq, '.');
9681017
mname = mname ? mname + 1 : fq;
9691018
const CBMRegisteredFunc *f = NULL;
970-
bool blocked = false;
1019+
RubyLookupWalk w = ruby_walk_begin(ctx);
9711020
/* Search order mirrors Ruby: includes of the class, then superclass
9721021
* chain — the class's OWN def is the caller and must be skipped. An
9731022
* unresolved mixin or superclass on the way blocks the walk. */
9741023
f = ruby_lookup_in_mixins(ctx, ctx->enclosing_class_qn,
9751024
ctx->in_singleton_method ? RUBY_MIXIN_EXTEND : RUBY_MIXIN_INCLUDE,
976-
mname, 0, &blocked);
977-
if (!f && !blocked && !ruby_superclass_unresolved(ctx, ctx->enclosing_class_qn)) {
1025+
mname, 0, &w);
1026+
if (!f && !w.blocked && !ruby_superclass_unresolved(ctx, ctx->enclosing_class_qn)) {
9781027
const char *sup = ruby_superclass_qn(ctx, ctx->enclosing_class_qn);
9791028
if (sup) {
9801029
f = ctx->in_singleton_method
981-
? ruby_lookup_singleton_method_depth(ctx, sup, mname, 0, &blocked)
982-
: ruby_lookup_instance_method_depth(ctx, sup, mname, 0, &blocked);
1030+
? ruby_lookup_singleton_method_depth(ctx, sup, mname, 0, &w)
1031+
: ruby_lookup_instance_method_depth(ctx, sup, mname, 0, &w);
9831032
}
9841033
}
985-
if (f && !blocked)
1034+
if (f && !w.blocked)
9861035
ruby_emit_resolved(ctx, f->qualified_name, "ruby_method_super", RUBY_CONF_HIGH, site);
9871036
/* No known parent or unresolved — zero-edge guarantee. */
9881037
}

‎internal/cbm/lsp/ruby_lsp.h‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -33,6 +33,10 @@ typedef struct {
3333
const char *superclass_ref; /* raw dotted superclass spelling, or NULL */
3434
const char *superclass_qn; /* resolved QN (table/stdlib), or NULL */
3535
bool is_module; /* `module` (mixin source) vs `class` */
36+
/* Method-lookup visit marks: the stamp of the last walk that searched
37+
* this class on the instance / singleton side (ruby_walk_seen). */
38+
unsigned int seen_instance;
39+
unsigned int seen_singleton;
3640
} RubyClassInfo;
3741

3842
/* One `include`/`prepend`/`extend` record: owner class QN → module ref. */
@@ -129,6 +133,10 @@ typedef struct {
129133
int eval_depth;
130134
int walk_depth;
131135

136+
/* Stamp of the current method-lookup walk; each walk takes a fresh one
137+
* so marks left by earlier walks never match. */
138+
unsigned int lookup_stamp;
139+
132140
/* Debug mode (CBM_LSP_DEBUG env). */
133141
bool debug;
134142
} RubyLSPContext;

0 commit comments

Comments
 (0)