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    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    matches!(
353        token.kind(),
354        SyntaxKind::WHITESPACE | SyntaxKind::COMMENT | SyntaxKind::INNER_DOC_COMMENT
355    )
356}
357
358fn is_trailing_trivia(token: &SyntaxToken) -> bool {
359    matches!(
360        token.kind(),
361        SyntaxKind::WHITESPACE
362            | SyntaxKind::COMMENT
363            | SyntaxKind::INNER_DOC_COMMENT
364            | SyntaxKind::OUTER_DOC_COMMENT
365    )
366}
367
368#[cfg(test)]
369mod tests {
370    use crate::{StaticIndex, fixture};
371    use ide_db::{FileRange, FxHashMap, FxHashSet, base_db::VfsPath};
372    use syntax::TextSize;
373
374    use super::VendoredLibrariesConfig;
375
376    fn check_all_ranges(
377        #[rust_analyzer::rust_fixture] ra_fixture: &str,
378        vendored_libs_config: VendoredLibrariesConfig<'_>,
379    ) {
380        let (analysis, ranges) = fixture::annotations_without_marker(ra_fixture);
381        let s = StaticIndex::compute(&analysis, vendored_libs_config);
382        let mut range_set: FxHashSet<_> = ranges.iter().map(|it| it.0).collect();
383        for f in s.files {
384            for (range, _) in f.tokens {
385                if range.start() == TextSize::from(0) {
386                    // ignore whole file range corresponding to module definition
387                    continue;
388                }
389                let it = FileRange { file_id: f.file_id, range };
390                if !range_set.contains(&it) {
391                    panic!("additional range {it:?}");
392                }
393                range_set.remove(&it);
394            }
395        }
396        if !range_set.is_empty() {
397            panic!("unfound ranges {range_set:?}");
398        }
399    }
400
401    #[track_caller]
402    fn check_definitions(
403        #[rust_analyzer::rust_fixture] ra_fixture: &str,
404        vendored_libs_config: VendoredLibrariesConfig<'_>,
405    ) {
406        let (analysis, ranges) = fixture::annotations_without_marker(ra_fixture);
407        let s = StaticIndex::compute(&analysis, vendored_libs_config);
408        let mut range_set: FxHashSet<_> = ranges.iter().map(|it| it.0).collect();
409        for (_, t) in s.tokens.iter() {
410            if let Some(t) = t.definition {
411                if t.range.start() == TextSize::from(0) {
412                    // ignore definitions that are whole of file
413                    continue;
414                }
415                if !range_set.contains(&t) {
416                    panic!("additional definition {t:?}");
417                }
418                range_set.remove(&t);
419            }
420        }
421        if !range_set.is_empty() {
422            panic!("unfound definitions {range_set:?}");
423        }
424    }
425
426    #[track_caller]
427    fn check_references(
428        #[rust_analyzer::rust_fixture] ra_fixture: &str,
429        vendored_libs_config: VendoredLibrariesConfig<'_>,
430    ) {
431        let (analysis, ranges) = fixture::annotations_without_marker(ra_fixture);
432        let s = StaticIndex::compute(&analysis, vendored_libs_config);
433        let mut range_set: FxHashMap<_, i32> = ranges.iter().map(|it| (it.0, 0)).collect();
434
435        // Make sure that all references have at least one range. We use a HashMap instead of a
436        // a HashSet so that we can have more than one reference at the same range.
437        for (_, t) in s.tokens.iter() {
438            for r in &t.references {
439                if r.is_definition {
440                    continue;
441                }
442                if r.range.range.start() == TextSize::from(0) {
443                    // ignore whole file range corresponding to module definition
444                    continue;
445                }
446                match range_set.entry(r.range) {
447                    std::collections::hash_map::Entry::Occupied(mut entry) => {
448                        let count = entry.get_mut();
449                        *count += 1;
450                    }
451                    std::collections::hash_map::Entry::Vacant(_) => {
452                        panic!("additional reference {r:?}");
453                    }
454                }
455            }
456        }
457        for (range, count) in range_set.iter() {
458            if *count == 0 {
459                panic!("unfound reference {range:?}");
460            }
461        }
462    }
463
464    #[test]
465    fn field_initialization() {
466        check_references(
467            r#"
468struct Point {
469    x: f64,
470     //^^^
471    y: f64,
472     //^^^
473}
474    fn foo() {
475        let x = 5.;
476        let y = 10.;
477        let mut p = Point { x, y };
478                  //^^^^^   ^  ^
479        p.x = 9.;
480      //^ ^
481        p.y = 10.;
482      //^ ^
483    }
484"#,
485            VendoredLibrariesConfig::Included {
486                workspace_root: &VfsPath::new_virtual_path("/workspace".to_owned()),
487            },
488        );
489    }
490
491    #[test]
492    fn struct_and_enum() {
493        check_all_ranges(
494            r#"
495struct Foo;
496     //^^^
497enum E { X(Foo) }
498   //^   ^ ^^^
499"#,
500            VendoredLibrariesConfig::Included {
501                workspace_root: &VfsPath::new_virtual_path("/workspace".to_owned()),
502            },
503        );
504        check_definitions(
505            r#"
506struct Foo;
507     //^^^
508enum E { X(Foo) }
509   //^   ^
510"#,
511            VendoredLibrariesConfig::Included {
512                workspace_root: &VfsPath::new_virtual_path("/workspace".to_owned()),
513            },
514        );
515
516        check_references(
517            r#"
518struct Foo;
519enum E { X(Foo) }
520   //      ^^^
521"#,
522            VendoredLibrariesConfig::Included {
523                workspace_root: &VfsPath::new_virtual_path("/workspace".to_owned()),
524            },
525        );
526    }
527
528    #[test]
529    fn multi_crate() {
530        check_definitions(
531            r#"
532//- /workspace/main.rs crate:main deps:foo
533
534
535use foo::func;
536
537fn main() {
538 //^^^^
539    func();
540}
541//- /workspace/foo/lib.rs crate:foo
542
543pub func() {
544
545}
546"#,
547            VendoredLibrariesConfig::Included {
548                workspace_root: &VfsPath::new_virtual_path("/workspace".to_owned()),
549            },
550        );
551    }
552
553    #[test]
554    fn vendored_crate() {
555        check_all_ranges(
556            r#"
557//- /workspace/main.rs crate:main deps:external,vendored
558struct Main(i32);
559     //^^^^ ^^^
560
561//- /external/lib.rs new_source_root:library crate:external@0.1.0,https://a.b/foo.git library
562struct ExternalLibrary(i32);
563
564//- /workspace/vendored/lib.rs new_source_root:library crate:vendored@0.1.0,https://a.b/bar.git library
565struct VendoredLibrary(i32);
566     //^^^^^^^^^^^^^^^ ^^^
567"#,
568            VendoredLibrariesConfig::Included {
569                workspace_root: &VfsPath::new_virtual_path("/workspace".to_owned()),
570            },
571        );
572    }
573
574    #[test]
575    fn vendored_crate_excluded() {
576        check_all_ranges(
577            r#"
578//- /workspace/main.rs crate:main deps:external,vendored
579struct Main(i32);
580     //^^^^ ^^^
581
582//- /external/lib.rs new_source_root:library crate:external@0.1.0,https://a.b/foo.git library
583struct ExternalLibrary(i32);
584
585//- /workspace/vendored/lib.rs new_source_root:library crate:vendored@0.1.0,https://a.b/bar.git library
586struct VendoredLibrary(i32);
587"#,
588            VendoredLibrariesConfig::Excluded,
589        )
590    }
591
592    #[test]
593    fn derives() {
594        check_all_ranges(
595            r#"
596//- minicore:derive
597#[rustc_builtin_macro]
598//^^^^^^^^^^^^^^^^^^^
599pub macro Copy {}
600        //^^^^
601#[derive(Copy)]
602//^^^^^^ ^^^^
603struct Hello(i32);
604     //^^^^^ ^^^
605"#,
606            VendoredLibrariesConfig::Included {
607                workspace_root: &VfsPath::new_virtual_path("/workspace".to_owned()),
608            },
609        );
610    }
611}
ide/static_index.rs

ide/
static_index.rs
