ide/
static_index.rs

1//! This module provides `StaticIndex` which is used for powering
2//! read-only code browsers and emitting LSIF
3
4use arrayvec::ArrayVec;
5use either::Either;
6use hir::{Crate, Module, Semantics, db::HirDatabase};
7use ide_db::{
8    FileId, FileRange, FxHashMap, FxHashSet, RootDatabase,
9    base_db::{SourceDatabase, VfsPath},
10    defs::{Definition, IdentClass},
11    documentation::Documentation,
12    famous_defs::FamousDefs,
13    ra_fixture::RaFixtureConfig,
14};
15use syntax::{AstNode, AstToken, NodeOrToken, SyntaxKind, SyntaxNode, SyntaxToken, TextRange, ast};
16
17use crate::navigation_target::UpmappingResult;
18use crate::{
19    Analysis, Fold, HoverConfig, HoverResult, TryToNav,
20    hover::{SubstTyLen, hover_for_definition},
21    moniker::{MonikerResult, SymbolInformationKind, def_to_kind, def_to_moniker},
22    parent_module::crates_for,
23};
24
25/// A static representation of fully analyzed source code.
26///
27/// The intended use-case is powering read-only code browsers and emitting LSIF/SCIP.
28#[derive(Debug)]
29pub struct StaticIndex<'a> {
30    pub files: Vec<StaticIndexedFile>,
31    pub tokens: TokenStore,
32    analysis: &'a Analysis,
33    db: &'a RootDatabase,
34    def_map: FxHashMap<Definition<'a>, TokenId>,
35}
36
37#[derive(Debug)]
38pub struct ReferenceData {
39    pub range: FileRange,
40    pub is_definition: bool,
41}
42
43#[derive(Debug)]
44pub struct TokenStaticData {
45    // FIXME: Make this have the lifetime of the database.
46    pub documentation: Option<Documentation<'static>>,
47    pub hover: Option<HoverResult>,
48    /// The position of the token itself.
49    ///
50    /// For example, in `fn foo() {}` this is the position of `foo`.
51    pub definition: Option<FileRange>,
52    /// The position of the entire definition that this token belongs to.
53    ///
54    /// For example, in `fn foo() {}` this is the position from `fn`
55    /// to the closing brace.
56    ///
57    /// This excludes trivia (whitespace/comments) other than doc
58    /// comments. This differs from LSP, which includes trivia.
59    ///
60    /// SCIP:
61    ///
62    /// > source range of the nearest non-trivial enclosing AST node.
63    ///
64    /// <https://github.com/scip-code/scip/blob/20459645420419b3c2a10d6a9f57436abeeb273b/scip.proto#L747-L796>
65    ///
66    /// LSP:
67    ///
68    /// > range enclosing this symbol not including leading/trailing
69    /// > whitespace but everything else like comments.
70    ///
71    /// <https://microsoft.github.io/language-server-protocol/specifications/lsp/3.18/specification/#locationLink>
72    pub definition_body: Option<FileRange>,
73    pub references: Vec<ReferenceData>,
74    pub moniker: Option<MonikerResult>,
75    pub display_name: Option<String>,
76    pub signature: Option<String>,
77    pub kind: SymbolInformationKind,
78}
79
80#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
81pub struct TokenId(usize);
82
83impl TokenId {
84    pub fn raw(self) -> usize {
85        self.0
86    }
87}
88
89#[derive(Default, Debug)]
90pub struct TokenStore(Vec<TokenStaticData>);
91
92impl TokenStore {
93    pub fn insert(&mut self, data: TokenStaticData) -> TokenId {
94        let id = TokenId(self.0.len());
95        self.0.push(data);
96        id
97    }
98
99    pub fn get_mut(&mut self, id: TokenId) -> Option<&mut TokenStaticData> {
100        self.0.get_mut(id.0)
101    }
102
103    pub fn get(&self, id: TokenId) -> Option<&TokenStaticData> {
104        self.0.get(id.0)
105    }
106
107    pub fn iter(self) -> impl Iterator<Item = (TokenId, TokenStaticData)> {
108        self.0.into_iter().enumerate().map(|(id, data)| (TokenId(id), data))
109    }
110}
111
112#[derive(Debug)]
113pub struct StaticIndexedFile {
114    pub file_id: FileId,
115    pub folds: Vec<Fold>,
116    pub tokens: Vec<(TextRange, TokenId)>,
117}
118
119fn all_modules(db: &dyn HirDatabase) -> Vec<Module> {
120    let mut worklist: Vec<_> =
121        Crate::all(db).into_iter().map(|krate| krate.root_module(db)).collect();
122    let mut modules = Vec::new();
123
124    while let Some(module) = worklist.pop() {
125        modules.push(module);
126        worklist.extend(module.children(db));
127    }
128
129    modules
130}
131
132fn documentation_for_definition(
133    sema: &Semantics<'_, RootDatabase>,
134    def: Definition<'_>,
135    scope_node: &SyntaxNode,
136) -> Option<Documentation<'static>> {
137    let famous_defs = match &def {
138        Definition::BuiltinType(_) => Some(FamousDefs(sema, sema.scope(scope_node)?.krate())),
139        _ => None,
140    };
141
142    def.docs(sema.db, famous_defs.as_ref(), def.krate(sema.db)?.to_display_target(sema.db))
143        .map(Documentation::into_owned)
144}
145
146// FIXME: This is a weird function
147fn get_definitions<'db>(
148    sema: &Semantics<'db, RootDatabase>,
149    token: SyntaxToken,
150) -> Option<ArrayVec<(Definition<'db>, Option<hir::GenericSubstitution<'db>>), 2>> {
151    for token in sema.descend_into_macros_exact(token) {
152        let def = IdentClass::classify_token(sema, &token).map(IdentClass::definitions);
153        if let Some(defs) = def
154            && !defs.is_empty()
155        {
156            return Some(defs);
157        }
158    }
159    None
160}
161
162pub enum VendoredLibrariesConfig<'a> {
163    Included { workspace_root: &'a VfsPath },
164    Excluded,
165}
166
167impl<'a> StaticIndex<'a> {
168    fn add_file(&mut self, file_id: FileId) {
169        let current_crate = crates_for(self.db, file_id).pop().map(Into::into);
170        let folds = self.analysis.folding_ranges(file_id, true).unwrap();
171        // hovers
172        let sema = hir::Semantics::new(self.db);
173        let root = sema.parse_guess_edition(file_id).syntax().clone();
174        let edition = sema.attach_first_edition(file_id).edition(sema.db);
175        let display_target = match sema.first_crate(file_id) {
176            Some(krate) => krate.to_display_target(sema.db),
177            None => return,
178        };
179        let tokens = root.descendants_with_tokens().filter_map(|it| match it {
180            syntax::NodeOrToken::Node(_) => None,
181            syntax::NodeOrToken::Token(it) => Some(it),
182        });
183        let hover_config = HoverConfig {
184            links_in_hover: true,
185            memory_layout: None,
186            documentation: true,
187            keywords: true,
188            format: crate::HoverDocFormat::Markdown,
189            max_trait_assoc_items_count: None,
190            max_fields_count: Some(5),
191            max_enum_variants_count: Some(5),
192            max_subst_ty_len: SubstTyLen::Unlimited,
193            show_drop_glue: true,
194            ra_fixture: RaFixtureConfig::default(),
195        };
196        let mut result = StaticIndexedFile { file_id, folds, tokens: vec![] };
197
198        let mut add_token = |def: Definition<'a>, range: TextRange, scope_node: &SyntaxNode| {
199            let id = if let Some(it) = self.def_map.get(&def) {
200                *it
201            } else {
202                let nav = def.try_to_nav(&sema).map(UpmappingResult::call_site);
203                let it = self.tokens.insert(TokenStaticData {
204                    documentation: documentation_for_definition(&sema, def, scope_node),
205                    hover: Some(hover_for_definition(
206                        &sema,
207                        file_id,
208                        def,
209                        None,
210                        scope_node,
211                        None,
212                        false,
213                        &hover_config,
214                        edition,
215                        display_target,
216                    )),
217                    definition: nav.as_ref().map(|it| FileRange {
218                        file_id: it.file_id,
219                        range: it.focus_or_full_range(),
220                    }),
221                    definition_body: nav.as_ref().map(|it| FileRange {
222                        file_id: it.file_id,
223                        range: definition_range_excluding_trivia(&sema, it.file_id, it.full_range),
224                    }),
225                    references: vec![],
226                    moniker: current_crate.and_then(|cc| def_to_moniker(self.db, def, cc)),
227                    display_name: def
228                        .name(self.db)
229                        .map(|name| name.display(self.db, edition).to_string()),
230                    signature: Some(def.label(self.db, display_target)),
231                    kind: def_to_kind(self.db, def),
232                });
233                self.def_map.insert(def, it);
234                it
235            };
236            let token = self.tokens.get_mut(id).unwrap();
237            token.references.push(ReferenceData {
238                range: FileRange { range, file_id },
239                is_definition: match def.try_to_nav(&sema).map(UpmappingResult::call_site) {
240                    Some(it) => it.file_id == file_id && it.focus_or_full_range() == range,
241                    None => false,
242                },
243            });
244            result.tokens.push((range, id));
245        };
246
247        if let Some(module) = sema.file_to_module_def(file_id) {
248            let def = Definition::Module(module);
249            let range = root.text_range();
250            add_token(def, range, &root);
251        }
252
253        for token in tokens {
254            let range = token.text_range();
255            let node = token.parent().unwrap();
256            match hir::attach_db(self.db, || get_definitions(&sema, token.clone())) {
257                Some(defs) => {
258                    for (def, _) in defs {
259                        add_token(def, range, &node);
260                    }
261                }
262                None => continue,
263            };
264        }
265        self.files.push(result);
266    }
267
268    pub fn compute(
269        analysis: &'a Analysis,
270        vendored_libs_config: VendoredLibrariesConfig<'_>,
271    ) -> StaticIndex<'a> {
272        let db = &analysis.db;
273        hir::attach_db(db, || {
274            let work = all_modules(db).into_iter().filter(|module| {
275                let file_id = module.definition_source_file_id(db).original_file(db);
276                let source_root =
277                    db.file_source_root(file_id.file_id(&analysis.db)).source_root_id(db);
278                let source_root = db.source_root(source_root).source_root(db);
279                let is_vendored = match vendored_libs_config {
280                    VendoredLibrariesConfig::Included { workspace_root } => source_root
281                        .path_for_file(&file_id.file_id(&analysis.db))
282                        .is_some_and(|module_path| module_path.starts_with(workspace_root)),
283                    VendoredLibrariesConfig::Excluded => false,
284                };
285
286                !source_root.is_library || is_vendored
287            });
288            let mut this = StaticIndex {
289                files: vec![],
290                tokens: Default::default(),
291                analysis,
292                db,
293                def_map: Default::default(),
294            };
295            let mut visited_files = FxHashSet::default();
296            for module in work {
297                let file_id =
298                    module.definition_source_file_id(db).original_file(db).file_id(&analysis.db);
299                if visited_files.contains(&file_id) {
300                    continue;
301                }
302                this.add_file(file_id);
303                visited_files.insert(file_id);
304            }
305            this
306        })
307    }
308}
309
310fn definition_range_excluding_trivia(
311    sema: &Semantics<'_, RootDatabase>,
312    file_id: FileId,
313    range: TextRange,
314) -> TextRange {
315    let root = sema.parse_guess_edition(file_id).syntax().clone();
316    if range == root.text_range() {
317        return range;
318    }
319    if !root.text_range().contains_range(range) {
320        return range;
321    }
322
323    let element = root.covering_element(range);
324    let tokens = match element {
325        NodeOrToken::Node(node) => Either::Left(node.descendants_with_tokens().filter_map(|it| {
326            let token = it.into_token()?;
327            range.contains_range(token.text_range()).then_some(token)
328        })),
329        NodeOrToken::Token(token) => Either::Right(std::iter::once(token)),
330    };
331
332    let mut first = None;
333    let mut last = None;
334    for token in tokens {
335        if first.is_none() && !is_leading_trivia_excluding_docs(&token) {
336            first = Some(token.clone());
337        }
338        if !is_trailing_trivia(&token) {
339            last = Some(token);
340        }
341    }
342
343    match (first, last) {
344        (Some(first), Some(last)) => {
345            TextRange::new(first.text_range().start(), last.text_range().end())
346        }
347        _ => range,
348    }
349}
350
351fn is_leading_trivia_excluding_docs(token: &SyntaxToken) -> bool {
352    match token.kind() {
353        SyntaxKind::WHITESPACE => true,
354        SyntaxKind::COMMENT => ast::Comment::cast(token.clone()).is_none_or(|it| !it.is_outer()),
355        _ => false,
356    }
357}
358
359fn is_trailing_trivia(token: &SyntaxToken) -> bool {
360    matches!(token.kind(), SyntaxKind::WHITESPACE | SyntaxKind::COMMENT)
361}
362
363#[cfg(test)]
364mod tests {
365    use crate::{StaticIndex, fixture};
366    use ide_db::{FileRange, FxHashMap, FxHashSet, base_db::VfsPath};
367    use syntax::TextSize;
368
369    use super::VendoredLibrariesConfig;
370
371    fn check_all_ranges(
372        #[rust_analyzer::rust_fixture] ra_fixture: &str,
373        vendored_libs_config: VendoredLibrariesConfig<'_>,
374    ) {
375        let (analysis, ranges) = fixture::annotations_without_marker(ra_fixture);
376        let s = StaticIndex::compute(&analysis, vendored_libs_config);
377        let mut range_set: FxHashSet<_> = ranges.iter().map(|it| it.0).collect();
378        for f in s.files {
379            for (range, _) in f.tokens {
380                if range.start() == TextSize::from(0) {
381                    // ignore whole file range corresponding to module definition
382                    continue;
383                }
384                let it = FileRange { file_id: f.file_id, range };
385                if !range_set.contains(&it) {
386                    panic!("additional range {it:?}");
387                }
388                range_set.remove(&it);
389            }
390        }
391        if !range_set.is_empty() {
392            panic!("unfound ranges {range_set:?}");
393        }
394    }
395
396    #[track_caller]
397    fn check_definitions(
398        #[rust_analyzer::rust_fixture] ra_fixture: &str,
399        vendored_libs_config: VendoredLibrariesConfig<'_>,
400    ) {
401        let (analysis, ranges) = fixture::annotations_without_marker(ra_fixture);
402        let s = StaticIndex::compute(&analysis, vendored_libs_config);
403        let mut range_set: FxHashSet<_> = ranges.iter().map(|it| it.0).collect();
404        for (_, t) in s.tokens.iter() {
405            if let Some(t) = t.definition {
406                if t.range.start() == TextSize::from(0) {
407                    // ignore definitions that are whole of file
408                    continue;
409                }
410                if !range_set.contains(&t) {
411                    panic!("additional definition {t:?}");
412                }
413                range_set.remove(&t);
414            }
415        }
416        if !range_set.is_empty() {
417            panic!("unfound definitions {range_set:?}");
418        }
419    }
420
421    #[track_caller]
422    fn check_references(
423        #[rust_analyzer::rust_fixture] ra_fixture: &str,
424        vendored_libs_config: VendoredLibrariesConfig<'_>,
425    ) {
426        let (analysis, ranges) = fixture::annotations_without_marker(ra_fixture);
427        let s = StaticIndex::compute(&analysis, vendored_libs_config);
428        let mut range_set: FxHashMap<_, i32> = ranges.iter().map(|it| (it.0, 0)).collect();
429
430        // Make sure that all references have at least one range. We use a HashMap instead of a
431        // a HashSet so that we can have more than one reference at the same range.
432        for (_, t) in s.tokens.iter() {
433            for r in &t.references {
434                if r.is_definition {
435                    continue;
436                }
437                if r.range.range.start() == TextSize::from(0) {
438                    // ignore whole file range corresponding to module definition
439                    continue;
440                }
441                match range_set.entry(r.range) {
442                    std::collections::hash_map::Entry::Occupied(mut entry) => {
443                        let count = entry.get_mut();
444                        *count += 1;
445                    }
446                    std::collections::hash_map::Entry::Vacant(_) => {
447                        panic!("additional reference {r:?}");
448                    }
449                }
450            }
451        }
452        for (range, count) in range_set.iter() {
453            if *count == 0 {
454                panic!("unfound reference {range:?}");
455            }
456        }
457    }
458
459    #[test]
460    fn field_initialization() {
461        check_references(
462            r#"
463struct Point {
464    x: f64,
465     //^^^
466    y: f64,
467     //^^^
468}
469    fn foo() {
470        let x = 5.;
471        let y = 10.;
472        let mut p = Point { x, y };
473                  //^^^^^   ^  ^
474        p.x = 9.;
475      //^ ^
476        p.y = 10.;
477      //^ ^
478    }
479"#,
480            VendoredLibrariesConfig::Included {
481                workspace_root: &VfsPath::new_virtual_path("/workspace".to_owned()),
482            },
483        );
484    }
485
486    #[test]
487    fn struct_and_enum() {
488        check_all_ranges(
489            r#"
490struct Foo;
491     //^^^
492enum E { X(Foo) }
493   //^   ^ ^^^
494"#,
495            VendoredLibrariesConfig::Included {
496                workspace_root: &VfsPath::new_virtual_path("/workspace".to_owned()),
497            },
498        );
499        check_definitions(
500            r#"
501struct Foo;
502     //^^^
503enum E { X(Foo) }
504   //^   ^
505"#,
506            VendoredLibrariesConfig::Included {
507                workspace_root: &VfsPath::new_virtual_path("/workspace".to_owned()),
508            },
509        );
510
511        check_references(
512            r#"
513struct Foo;
514enum E { X(Foo) }
515   //      ^^^
516"#,
517            VendoredLibrariesConfig::Included {
518                workspace_root: &VfsPath::new_virtual_path("/workspace".to_owned()),
519            },
520        );
521    }
522
523    #[test]
524    fn multi_crate() {
525        check_definitions(
526            r#"
527//- /workspace/main.rs crate:main deps:foo
528
529
530use foo::func;
531
532fn main() {
533 //^^^^
534    func();
535}
536//- /workspace/foo/lib.rs crate:foo
537
538pub func() {
539
540}
541"#,
542            VendoredLibrariesConfig::Included {
543                workspace_root: &VfsPath::new_virtual_path("/workspace".to_owned()),
544            },
545        );
546    }
547
548    #[test]
549    fn vendored_crate() {
550        check_all_ranges(
551            r#"
552//- /workspace/main.rs crate:main deps:external,vendored
553struct Main(i32);
554     //^^^^ ^^^
555
556//- /external/lib.rs new_source_root:library crate:external@0.1.0,https://a.b/foo.git library
557struct ExternalLibrary(i32);
558
559//- /workspace/vendored/lib.rs new_source_root:library crate:vendored@0.1.0,https://a.b/bar.git library
560struct VendoredLibrary(i32);
561     //^^^^^^^^^^^^^^^ ^^^
562"#,
563            VendoredLibrariesConfig::Included {
564                workspace_root: &VfsPath::new_virtual_path("/workspace".to_owned()),
565            },
566        );
567    }
568
569    #[test]
570    fn vendored_crate_excluded() {
571        check_all_ranges(
572            r#"
573//- /workspace/main.rs crate:main deps:external,vendored
574struct Main(i32);
575     //^^^^ ^^^
576
577//- /external/lib.rs new_source_root:library crate:external@0.1.0,https://a.b/foo.git library
578struct ExternalLibrary(i32);
579
580//- /workspace/vendored/lib.rs new_source_root:library crate:vendored@0.1.0,https://a.b/bar.git library
581struct VendoredLibrary(i32);
582"#,
583            VendoredLibrariesConfig::Excluded,
584        )
585    }
586
587    #[test]
588    fn derives() {
589        check_all_ranges(
590            r#"
591//- minicore:derive
592#[rustc_builtin_macro]
593//^^^^^^^^^^^^^^^^^^^
594pub macro Copy {}
595        //^^^^
596#[derive(Copy)]
597//^^^^^^ ^^^^
598struct Hello(i32);
599     //^^^^^ ^^^
600"#,
601            VendoredLibrariesConfig::Included {
602                workspace_root: &VfsPath::new_virtual_path("/workspace".to_owned()),
603            },
604        );
605    }
606}
ide/static_index.rs

ide/
static_index.rs
