gruel_lsp/
goto.rs

1//! Goto-definition (ADR-0091 Phase 4).
2//!
3//! Given a cursor position, find the identifier under it and walk the AST
4//! to locate the *defining* occurrence (function, struct, enum, const,
5//! field, variant, method). Phase 4 covers definitions visible in the
6//! merged AST: type names referenced in type-position resolve to their
7//! struct/enum/interface/derive declaration; identifiers in expression
8//! position resolve when they name a top-level function, constant, or
9//! local binding within the enclosing function.
10//!
11//! Field accesses across `@import` boundaries and cross-file imports are
12//! deferred to later phases (they need sema-level symbol resolution).
13
14use gruel_parser::ast::{
15    AssignTarget, Ast, BlockExpr, Expr, Function, Ident, Item, MatchArm, Method, Pattern,
16    Statement, TypeExpr,
17};
18use gruel_util::{FileId, Span};
19use lasso::ThreadedRodeo;
20
21/// Find the defining span for the identifier under the cursor, if any.
22pub fn definition_at(
23    ast: &Ast,
24    interner: &ThreadedRodeo,
25    file_id: FileId,
26    byte: u32,
27) -> Option<Span> {
28    let target = find_ident_at(ast, file_id, byte)?;
29    resolve_definition(ast, interner, target)
30}
31
32/// Walk the AST and find the identifier whose span contains `byte`.
33fn find_ident_at(ast: &Ast, file_id: FileId, byte: u32) -> Option<Ident> {
34    let mut finder = IdentFinder::new(file_id, byte);
35    for item in &ast.items {
36        finder.visit_item(item);
37    }
38    finder.result
39}
40
41struct IdentFinder {
42    file_id: FileId,
43    byte: u32,
44    result: Option<Ident>,
45    best_size: u32,
46}
47
48impl IdentFinder {
49    fn new(file_id: FileId, byte: u32) -> Self {
50        Self {
51            file_id,
52            byte,
53            result: None,
54            best_size: u32::MAX,
55        }
56    }
57
58    fn consider(&mut self, ident: Ident) {
59        let span = ident.span;
60        if span.file_id != self.file_id {
61            return;
62        }
63        if self.byte < span.start || self.byte >= span.end {
64            return;
65        }
66        let size = span.end.saturating_sub(span.start);
67        if size <= self.best_size {
68            self.best_size = size;
69            self.result = Some(ident);
70        }
71    }
72
73    fn visit_item(&mut self, item: &Item) {
74        match item {
75            Item::Function(f) => {
76                self.consider(f.name);
77                for p in &f.params {
78                    self.consider(p.name);
79                    self.visit_type(&p.ty);
80                }
81                if let Some(rt) = &f.return_type {
82                    self.visit_type(rt);
83                }
84                self.visit_expr(&f.body);
85            }
86            Item::Struct(s) => {
87                self.consider(s.name);
88                for field in &s.fields {
89                    self.consider(field.name);
90                    self.visit_type(&field.ty);
91                }
92                for m in &s.methods {
93                    self.visit_method(m);
94                }
95            }
96            Item::Enum(e) => {
97                self.consider(e.name);
98                for v in &e.variants {
99                    self.consider(v.name);
100                }
101                for m in &e.methods {
102                    self.visit_method(m);
103                }
104            }
105            Item::Interface(i) => {
106                self.consider(i.name);
107                for sig in &i.methods {
108                    self.consider(sig.name);
109                    for p in &sig.params {
110                        self.consider(p.name);
111                        self.visit_type(&p.ty);
112                    }
113                    if let Some(rt) = &sig.return_type {
114                        self.visit_type(rt);
115                    }
116                }
117            }
118            Item::Derive(d) => {
119                self.consider(d.name);
120                for m in &d.methods {
121                    self.visit_method(m);
122                }
123            }
124            Item::Const(c) => {
125                self.consider(c.name);
126                if let Some(ty) = &c.ty {
127                    self.visit_type(ty);
128                }
129                self.visit_expr(&c.init);
130            }
131            Item::LinkExtern(b) => {
132                for ext in &b.items {
133                    self.consider(ext.name);
134                    for p in &ext.params {
135                        self.consider(p.name);
136                        self.visit_type(&p.ty);
137                    }
138                    if let Some(rt) = &ext.return_type {
139                        self.visit_type(rt);
140                    }
141                }
142            }
143            Item::Error(_) => {}
144        }
145    }
146
147    fn visit_method(&mut self, m: &Method) {
148        self.consider(m.name);
149        for p in &m.params {
150            self.consider(p.name);
151            self.visit_type(&p.ty);
152        }
153        if let Some(rt) = &m.return_type {
154            self.visit_type(rt);
155        }
156        self.visit_expr(&m.body);
157    }
158
159    fn visit_type(&mut self, ty: &TypeExpr) {
160        match ty {
161            TypeExpr::Named(ident) => self.consider(*ident),
162            TypeExpr::TypeCall { callee, args, .. } => {
163                self.consider(*callee);
164                for a in args {
165                    self.visit_type(a);
166                }
167            }
168            TypeExpr::Array { element, .. } => self.visit_type(element),
169            TypeExpr::Tuple { elems, .. } => {
170                for e in elems {
171                    self.visit_type(e);
172                }
173            }
174            _ => {}
175        }
176    }
177
178    fn visit_expr(&mut self, expr: &Expr) {
179        match expr {
180            Expr::Ident(ident) => self.consider(*ident),
181            Expr::Block(b) => self.visit_block(b),
182            Expr::Call(c) => {
183                self.consider(c.name);
184                for arg in &c.args {
185                    self.visit_expr(&arg.expr);
186                }
187            }
188            Expr::MethodCall(m) => {
189                self.visit_expr(&m.receiver);
190                self.consider(m.method);
191                for arg in &m.args {
192                    self.visit_expr(&arg.expr);
193                }
194            }
195            Expr::Field(f) => {
196                self.visit_expr(&f.base);
197                self.consider(f.field);
198            }
199            Expr::Binary(b) => {
200                self.visit_expr(&b.left);
201                self.visit_expr(&b.right);
202            }
203            Expr::Unary(u) => self.visit_expr(&u.operand),
204            Expr::Paren(p) => self.visit_expr(&p.inner),
205            Expr::If(i) => {
206                self.visit_expr(&i.cond);
207                self.visit_block(&i.then_block);
208                if let Some(b) = &i.else_block {
209                    self.visit_block(b);
210                }
211            }
212            Expr::While(w) => {
213                self.visit_expr(&w.cond);
214                self.visit_block(&w.body);
215            }
216            Expr::For(f) => {
217                self.consider(f.binding);
218                self.visit_expr(&f.iterable);
219                self.visit_block(&f.body);
220            }
221            Expr::Loop(l) => self.visit_block(&l.body),
222            Expr::Match(m) => {
223                self.visit_expr(&m.scrutinee);
224                for arm in &m.arms {
225                    self.visit_match_arm(arm);
226                }
227            }
228            Expr::Return(r) => {
229                if let Some(e) = &r.value {
230                    self.visit_expr(e);
231                }
232            }
233            Expr::Tuple(t) => {
234                for e in &t.elems {
235                    self.visit_expr(e);
236                }
237            }
238            Expr::TupleIndex(t) => self.visit_expr(&t.base),
239            Expr::Index(i) => {
240                self.visit_expr(&i.base);
241                self.visit_expr(&i.index);
242            }
243            Expr::StructLit(s) => {
244                if let Some(base) = &s.base {
245                    self.visit_expr(base);
246                }
247                self.consider(s.name);
248                for fi in &s.fields {
249                    self.consider(fi.name);
250                    self.visit_expr(&fi.value);
251                }
252            }
253            Expr::EnumStructLit(_) => {}
254            Expr::Path(p) => {
255                if let Some(b) = &p.base {
256                    self.visit_expr(b);
257                }
258                self.consider(p.type_name);
259                self.consider(p.variant);
260            }
261            Expr::AssocFnCall(_) => {}
262            Expr::IntrinsicCall(c) => {
263                self.consider(c.name);
264                for a in &c.args {
265                    if let gruel_parser::ast::IntrinsicArg::Expr(e) = a {
266                        self.visit_expr(e);
267                    }
268                }
269            }
270            Expr::ArrayLit(a) => {
271                for e in &a.elements {
272                    self.visit_expr(e);
273                }
274            }
275            Expr::Range(r) => {
276                if let Some(e) = &r.lo {
277                    self.visit_expr(e);
278                }
279                if let Some(e) = &r.hi {
280                    self.visit_expr(e);
281                }
282            }
283            Expr::AnonFn(f) => {
284                for p in &f.params {
285                    self.consider(p.name);
286                    self.visit_type(&p.ty);
287                }
288                self.visit_block(&f.body);
289            }
290            Expr::Comptime(_) => {}
291            Expr::ComptimeUnrollFor(_) => {}
292            Expr::Checked(_) => {}
293            _ => {}
294        }
295    }
296
297    fn visit_block(&mut self, b: &BlockExpr) {
298        for stmt in &b.statements {
299            self.visit_statement(stmt);
300        }
301        self.visit_expr(&b.expr);
302    }
303
304    fn visit_statement(&mut self, stmt: &Statement) {
305        match stmt {
306            Statement::Let(l) => {
307                self.consider_pattern(&l.pattern);
308                if let Some(ty) = &l.ty {
309                    self.visit_type(ty);
310                }
311                self.visit_expr(&l.init);
312            }
313            Statement::Assign(a) => {
314                match &a.target {
315                    AssignTarget::Var(i) => self.consider(*i),
316                    AssignTarget::Field(f) => {
317                        self.visit_expr(&f.base);
318                        self.consider(f.field);
319                    }
320                    AssignTarget::Index(i) => {
321                        self.visit_expr(&i.base);
322                        self.visit_expr(&i.index);
323                    }
324                }
325                self.visit_expr(&a.value);
326            }
327            Statement::Expr(e) => self.visit_expr(e),
328        }
329    }
330
331    fn consider_pattern(&mut self, p: &Pattern) {
332        if let Pattern::Ident { name, .. } = p {
333            self.consider(*name);
334        }
335    }
336
337    fn visit_match_arm(&mut self, arm: &MatchArm) {
338        self.visit_expr(&arm.body);
339    }
340}
341
342/// Resolve the identifier to its defining span by scanning top-level
343/// items and the bodies that introduced it.
344fn resolve_definition(ast: &Ast, _interner: &ThreadedRodeo, target: Ident) -> Option<Span> {
345    // Top-level matches.
346    for item in &ast.items {
347        let span = match item {
348            Item::Function(f) if f.name.name == target.name => Some(f.name.span),
349            Item::Struct(s) if s.name.name == target.name => Some(s.name.span),
350            Item::Enum(e) if e.name.name == target.name => Some(e.name.span),
351            Item::Interface(i) if i.name.name == target.name => Some(i.name.span),
352            Item::Derive(d) if d.name.name == target.name => Some(d.name.span),
353            Item::Const(c) if c.name.name == target.name => Some(c.name.span),
354            _ => None,
355        };
356        if let Some(s) = span {
357            return Some(s);
358        }
359    }
360    // Locals and params live inside a specific function body.
361    if let Some(span) = resolve_in_function_bodies(ast, target) {
362        return Some(span);
363    }
364    None
365}
366
367fn resolve_in_function_bodies(ast: &Ast, target: Ident) -> Option<Span> {
368    for item in &ast.items {
369        match item {
370            Item::Function(f) => {
371                if let Some(s) = resolve_in_function(f, target) {
372                    return Some(s);
373                }
374            }
375            Item::Struct(s) => {
376                for m in &s.methods {
377                    if let Some(s) = resolve_in_method(m, target) {
378                        return Some(s);
379                    }
380                }
381            }
382            Item::Enum(e) => {
383                for m in &e.methods {
384                    if let Some(s) = resolve_in_method(m, target) {
385                        return Some(s);
386                    }
387                }
388            }
389            Item::Derive(d) => {
390                for m in &d.methods {
391                    if let Some(s) = resolve_in_method(m, target) {
392                        return Some(s);
393                    }
394                }
395            }
396            _ => {}
397        }
398    }
399    None
400}
401
402fn resolve_in_function(f: &Function, target: Ident) -> Option<Span> {
403    if !expr_contains_target(&f.body, target) {
404        return None;
405    }
406    for p in &f.params {
407        if p.name.name == target.name {
408            return Some(p.name.span);
409        }
410    }
411    find_local_def_in_expr(&f.body, target)
412}
413
414fn resolve_in_method(m: &Method, target: Ident) -> Option<Span> {
415    if !expr_contains_target(&m.body, target) {
416        return None;
417    }
418    for p in &m.params {
419        if p.name.name == target.name {
420            return Some(p.name.span);
421        }
422    }
423    find_local_def_in_expr(&m.body, target)
424}
425
426#[allow(dead_code)]
427fn block_contains(b: &BlockExpr, target: Ident) -> bool {
428    target.span.start >= b.span.start && target.span.end <= b.span.end
429}
430
431fn expr_contains_target(e: &Expr, target: Ident) -> bool {
432    let span = match e {
433        Expr::Block(b) => b.span,
434        _ => return false,
435    };
436    target.span.start >= span.start && target.span.end <= span.end
437}
438
439fn find_local_def_in_expr(expr: &Expr, target: Ident) -> Option<Span> {
440    let mut found: Option<Span> = None;
441    walk_expr_for_let(expr, target, &mut found);
442    found
443}
444
445fn walk_block_for_let(block: &BlockExpr, target: Ident, found: &mut Option<Span>) {
446    for stmt in &block.statements {
447        match stmt {
448            Statement::Let(l) => {
449                if let Pattern::Ident { name, .. } = &l.pattern {
450                    if name.name == target.name && name.span.start <= target.span.start {
451                        *found = Some(name.span);
452                    }
453                }
454                walk_expr_for_let(&l.init, target, found);
455            }
456            Statement::Assign(a) => {
457                walk_expr_for_let(&a.value, target, found);
458            }
459            Statement::Expr(e) => {
460                walk_expr_for_let(e, target, found);
461            }
462        }
463    }
464    walk_expr_for_let(&block.expr, target, found);
465}
466
467fn walk_expr_for_let(expr: &Expr, target: Ident, found: &mut Option<Span>) {
468    match expr {
469        Expr::Block(b) => walk_block_for_let(b, target, found),
470        Expr::If(i) => {
471            walk_block_for_let(&i.then_block, target, found);
472            if let Some(b) = &i.else_block {
473                walk_block_for_let(b, target, found);
474            }
475        }
476        Expr::While(w) => walk_block_for_let(&w.body, target, found),
477        Expr::For(f) => {
478            if f.binding.name == target.name && f.binding.span.start <= target.span.start {
479                *found = Some(f.binding.span);
480            }
481            walk_block_for_let(&f.body, target, found);
482        }
483        Expr::Loop(l) => walk_block_for_let(&l.body, target, found),
484        Expr::Match(m) => {
485            for arm in &m.arms {
486                walk_expr_for_let(&arm.body, target, found);
487            }
488        }
489        _ => {}
490    }
491}
492
493#[cfg(test)]
494mod tests {
495    use super::*;
496    use gruel_compiler::{
497        PreviewFeatures, SourceFile, merge_symbols, parse_all_files_with_preview,
498    };
499
500    fn parse(source: &str) -> (Ast, ThreadedRodeo) {
501        let sources = vec![SourceFile::new("main.gruel", source, FileId::new(1))];
502        let parsed = parse_all_files_with_preview(&sources, &PreviewFeatures::default()).unwrap();
503        let merged = merge_symbols(parsed).unwrap();
504        (merged.ast, merged.interner)
505    }
506
507    #[test]
508    fn goto_function_reference() {
509        let src = "fn foo() -> i32 { 0 }\nfn main() -> i32 { foo() }";
510        let (ast, interner) = parse(src);
511        let foo_call = src.rfind("foo").unwrap() as u32;
512        let def = definition_at(&ast, &interner, FileId::new(1), foo_call + 1).unwrap();
513        assert_eq!(def.start, src.find("foo").unwrap() as u32);
514    }
515
516    #[test]
517    fn goto_struct_reference_in_type_position() {
518        let src = "struct Point { x: i32 }\nfn make() -> Point { Point { x: 0 } }";
519        let (ast, interner) = parse(src);
520        let pos = src.find("-> Point").unwrap() as u32 + 3;
521        let def = definition_at(&ast, &interner, FileId::new(1), pos).unwrap();
522        assert_eq!(def.start, src.find("Point").unwrap() as u32);
523    }
524
525    #[test]
526    fn goto_local_variable() {
527        let src = "fn main() -> i32 { let x = 42; x }";
528        let (ast, interner) = parse(src);
529        let pos = src.rfind('x').unwrap() as u32;
530        let def = definition_at(&ast, &interner, FileId::new(1), pos).unwrap();
531        // `let x` → x position
532        assert_eq!(def.start, src.find("x =").unwrap() as u32);
533    }
534
535    #[test]
536    fn goto_function_param() {
537        let src = "fn id(x: i32) -> i32 { x }";
538        let (ast, interner) = parse(src);
539        let pos = src.rfind('x').unwrap() as u32;
540        let def = definition_at(&ast, &interner, FileId::new(1), pos).unwrap();
541        assert_eq!(def.start, src.find("x:").unwrap() as u32);
542    }
543}
gruel_lsp/goto.rs

gruel_lsp/
goto.rs
