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

ide/
static_index.rs
