nova_resolver/
index.rs

1//! The index of name occurrences the language server reads (spec
2//! `docs/superpowers/specs/2026-10-10-phase-3-4a-navigation-design.md` §3).
3//!
4//! The resolver records imports into it and the type checker everything
5//! else. Neither reads it: it is written for the server alone.
6
7use std::collections::{HashMap, HashSet};
8
9use nova_diagnostics::{FileId, Span};
10
11use crate::{Builtin, DefId, DefKind, Definitions, ModuleId};
12
13/// Whether an occurrence declares its target or uses it.
14#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
15pub enum Role {
16    Declaration,
17    Use,
18}
19
20/// What a name means (spec §3.1).
21#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
22pub enum Target {
23    /// A function, extern function, const, record, sum type, trait, impl
24    /// method or associated type.
25    Def(DefId),
26    Variant(DefId, u32),
27    Field(DefId, u32),
28    /// A trait's method, by its index in the checker's list of the trait's
29    /// methods.
30    TraitMethod(DefId, u32),
31    /// A local or parameter, named by its declaration's span.
32    Local(Span),
33    /// A type parameter, named by its declaration's span.
34    TypeParam(Span),
35    Module(ModuleId),
36    Builtin(Builtin),
37    /// An array's `len`.
38    BuiltinMethod(&'static str),
39    /// `Int`, `Float`, `Bool`, `Char`, `String`, `Bytes` or `Future`.
40    Primitive(&'static str),
41}
42
43/// How a local was declared, for semantic tokens (spec 3.4b §7.2).
44#[derive(Debug, Clone, Copy, PartialEq, Eq)]
45pub struct LocalFlags {
46    pub parameter: bool,
47    pub mutable: bool,
48}
49
50/// One name in the source.
51#[derive(Debug, Clone, PartialEq, Eq)]
52pub struct Occurrence {
53    /// The name's own token, not the expression around it.
54    pub span: Span,
55    pub role: Role,
56    pub target: Target,
57    /// A shorthand field `{ x }`, which is a field and a value at once.
58    pub shorthand: bool,
59}
60
61/// Every name an analysis resolved (spec §3.1).
62#[derive(Debug, Clone, Default)]
63pub struct Index {
64    pub occurrences: Vec<Occurrence>,
65    /// Each impl method that implements a trait's method.
66    pub implements: Vec<(DefId, (DefId, u32))>,
67    /// Each local's type as hover shows it, by declaration span.
68    pub types: HashMap<Span, String>,
69    /// Each local's declaration span: whether it is a parameter and whether
70    /// it is `mut` (spec 3.4b §4.6, §7.2). Recorded with the index only.
71    pub locals: HashMap<Span, LocalFlags>,
72    /// What `occurrences` holds, so a record is kept once (decision 28).
73    seen: HashSet<(Span, Role, Target)>,
74}
75
76impl Index {
77    /// Record an occurrence, unless the same one is already recorded.
78    pub fn record(&mut self, span: Span, role: Role, target: Target) {
79        if self.seen.insert((span, role, target)) {
80            self.occurrences.push(Occurrence {
81                span,
82                role,
83                target,
84                shorthand: false,
85            });
86        }
87    }
88
89    /// Mark every occurrence at `span` as a shorthand field's.
90    pub fn mark_shorthand(&mut self, span: Span) {
91        for o in self.occurrences.iter_mut().filter(|o| o.span == span) {
92            o.shorthand = true;
93        }
94    }
95
96    pub fn has(&self, span: Span, role: Role, target: Target) -> bool {
97        self.seen.contains(&(span, role, target))
98    }
99
100    /// Record that `method`, an impl's, implements `trait_method`.
101    pub fn implement(&mut self, method: DefId, trait_method: (DefId, u32)) {
102        if !self.implements.contains(&(method, trait_method)) {
103            self.implements.push((method, trait_method));
104        }
105    }
106
107    /// Record each of `occurrences`, as [`Index::record`] does.
108    pub fn extend(&mut self, occurrences: impl IntoIterator<Item = Occurrence>) {
109        for o in occurrences {
110            self.record(o.span, o.role, o.target);
111            if o.shorthand {
112                self.mark_shorthand(o.span);
113            }
114        }
115    }
116
117    /// The occurrence at byte `offset` of `file`: one whose span holds it,
118    /// or else one that ends there (spec §3.1). On a shared span the
119    /// value's wins, then the type's, then the trait's, then a field's.
120    pub fn at(&self, defs: &Definitions, file: FileId, offset: u32) -> Option<&Occurrence> {
121        let holding: Vec<&Occurrence> = self
122            .occurrences
123            .iter()
124            .filter(|o| o.span.file == file && o.span.start <= offset && offset < o.span.end)
125            .collect();
126        let found = if holding.is_empty() {
127            self.occurrences
128                .iter()
129                .filter(|o| o.span.file == file && o.span.end == offset)
130                .collect()
131        } else {
132            holding
133        };
134        found.into_iter().min_by_key(|o| rank(defs, &o.target))
135    }
136
137    /// Every occurrence of `target`, in recording order.
138    pub fn of(&self, target: &Target) -> Vec<&Occurrence> {
139        self.occurrences
140            .iter()
141            .filter(|o| &o.target == target)
142            .collect()
143    }
144
145    pub fn declaration(&self, target: &Target) -> Option<&Occurrence> {
146        self.occurrences
147            .iter()
148            .find(|o| &o.target == target && o.role == Role::Declaration)
149    }
150
151    /// `target`'s family (spec §3.1): a trait method and the impl methods
152    /// that implement it, the trait's first; any other target alone.
153    pub fn family(&self, target: &Target) -> Vec<Target> {
154        let trait_method = match target {
155            Target::TraitMethod(t, i) => Some((*t, *i)),
156            Target::Def(m) => self
157                .implements
158                .iter()
159                .find(|(d, _)| d == m)
160                .map(|(_, tm)| *tm),
161            _ => None,
162        };
163        let Some((t, i)) = trait_method else {
164            return vec![*target];
165        };
166        let mut out = vec![Target::TraitMethod(t, i)];
167        for (d, tm) in &self.implements {
168            if *tm == (t, i) {
169                out.push(Target::Def(*d));
170            }
171        }
172        out
173    }
174}
175
176/// Which of several occurrences on one span a request means: lower first.
177pub fn rank(defs: &Definitions, target: &Target) -> u8 {
178    match target {
179        Target::Field(..) => 3,
180        Target::Def(id) => match defs.defs().get(id.0 as usize).map(|d| &d.kind) {
181            Some(DefKind::Record { .. } | DefKind::Sum { .. } | DefKind::AssocType { .. }) => 1,
182            Some(DefKind::Trait { .. }) => 2,
183            _ => 0,
184        },
185        Target::TypeParam(_) | Target::Primitive(_) => 1,
186        _ => 0,
187    }
188}
189
190#[cfg(test)]
191mod tests {
192    use super::*;
193    use nova_diagnostics::FileDb;
194
195    fn files() -> (FileId, FileId) {
196        let mut db = FileDb::new();
197        (db.add("a.nova", "a"), db.add("b.nova", "b"))
198    }
199
200    fn span(file: FileId, start: u32, end: u32) -> Span {
201        Span::new(start, end, file)
202    }
203
204    #[test]
205    fn a_repeated_record_is_kept_once() {
206        let (a, _) = files();
207        let mut index = Index::default();
208        let s = span(a, 4, 9);
209        index.record(s, Role::Use, Target::Local(span(a, 0, 1)));
210        index.record(s, Role::Use, Target::Local(span(a, 0, 1)));
211        index.record(s, Role::Declaration, Target::Local(span(a, 0, 1)));
212        assert_eq!(index.occurrences.len(), 2);
213        assert!(index.has(s, Role::Use, Target::Local(span(a, 0, 1))));
214    }
215
216    #[test]
217    fn a_cursor_inside_or_at_the_end_of_a_name_finds_it() {
218        let (a, b) = files();
219        let defs = Definitions::default();
220        let mut index = Index::default();
221        let target = Target::Local(span(a, 0, 5));
222        index.record(span(a, 10, 15), Role::Use, target);
223        for offset in [10, 12, 14, 15] {
224            let found = index.at(&defs, a, offset).map(|o| o.span);
225            assert_eq!(found, Some(span(a, 10, 15)), "offset {offset}");
226        }
227        assert_eq!(index.at(&defs, a, 9).map(|o| o.span), None);
228        assert_eq!(index.at(&defs, a, 16).map(|o| o.span), None);
229        assert_eq!(index.at(&defs, b, 12).map(|o| o.span), None);
230    }
231
232    #[test]
233    fn a_cursor_between_two_names_finds_the_one_it_touches() {
234        // Review Focus 5: `a+b`. Just after `a` is `a`'s end; just before
235        // `b` is inside `b`, which wins over an end.
236        let (f, _) = files();
237        let defs = Definitions::default();
238        let mut index = Index::default();
239        let a = Target::Local(span(f, 100, 101));
240        let b = Target::Local(span(f, 200, 201));
241        index.record(span(f, 0, 1), Role::Use, a);
242        index.record(span(f, 2, 3), Role::Use, b);
243        assert_eq!(index.at(&defs, f, 1).map(|o| o.target), Some(a));
244        assert_eq!(index.at(&defs, f, 2).map(|o| o.target), Some(b));
245        // `a.b`'s shape: `a` ends where the `.` starts.
246        index.record(span(f, 10, 11), Role::Use, a);
247        index.record(span(f, 12, 13), Role::Use, b);
248        assert_eq!(index.at(&defs, f, 11).map(|o| o.target), Some(a));
249        assert_eq!(index.at(&defs, f, 12).map(|o| o.target), Some(b));
250    }
251
252    #[test]
253    fn at_a_shorthand_the_value_wins() {
254        let (f, _) = files();
255        let defs = Definitions::default();
256        let mut index = Index::default();
257        let x = span(f, 20, 21);
258        let field = Target::Field(DefId(3), 0);
259        let local = Target::Local(span(f, 2, 3));
260        index.record(x, Role::Use, field);
261        index.record(x, Role::Use, local);
262        index.mark_shorthand(x);
263        let found = index.at(&defs, f, 20).unwrap();
264        assert_eq!(found.target, local);
265        assert!(index.occurrences.iter().all(|o| o.shorthand));
266    }
267
268    #[test]
269    fn of_and_declaration_find_a_targets_occurrences() {
270        let (f, _) = files();
271        let mut index = Index::default();
272        let t = Target::Def(DefId(7));
273        index.record(span(f, 0, 3), Role::Declaration, t);
274        index.record(span(f, 10, 13), Role::Use, t);
275        index.record(span(f, 20, 23), Role::Use, Target::Def(DefId(8)));
276        assert_eq!(index.of(&t).len(), 2);
277        assert_eq!(index.declaration(&t).map(|o| o.span), Some(span(f, 0, 3)));
278        assert!(index.declaration(&Target::Def(DefId(8))).is_none());
279    }
280
281    #[test]
282    fn a_family_holds_a_trait_method_and_its_impls() {
283        let mut index = Index::default();
284        index.implement(DefId(10), (DefId(2), 1));
285        index.implement(DefId(11), (DefId(2), 1));
286        index.implement(DefId(11), (DefId(2), 1));
287        index.implement(DefId(12), (DefId(2), 0));
288        let family = vec![
289            Target::TraitMethod(DefId(2), 1),
290            Target::Def(DefId(10)),
291            Target::Def(DefId(11)),
292        ];
293        assert_eq!(index.family(&Target::TraitMethod(DefId(2), 1)), family);
294        assert_eq!(index.family(&Target::Def(DefId(11))), family);
295        assert_eq!(index.implements.len(), 3);
296        assert_eq!(
297            index.family(&Target::Def(DefId(99))),
298            vec![Target::Def(DefId(99))]
299        );
300    }
301
302    #[test]
303    fn extend_records_through_the_set() {
304        let (f, _) = files();
305        let mut index = Index::default();
306        let o = Occurrence {
307            span: span(f, 0, 1),
308            role: Role::Use,
309            target: Target::Module(ModuleId(1)),
310            shorthand: false,
311        };
312        index.extend([o.clone(), o]);
313        assert_eq!(index.occurrences.len(), 1);
314    }
315}
nova_resolver/index.rs

nova_resolver/
index.rs
