Unnamed repository; edit this file 'description' to name the repository.
Diffstat (limited to 'crates/ide_db/src/symbol_index.rs')
| -rw-r--r-- | crates/ide_db/src/symbol_index.rs | 587 |
1 files changed, 448 insertions, 139 deletions
diff --git a/crates/ide_db/src/symbol_index.rs b/crates/ide_db/src/symbol_index.rs index 54ceafa67f..cc2b2bbb7b 100644 --- a/crates/ide_db/src/symbol_index.rs +++ b/crates/ide_db/src/symbol_index.rs @@ -30,18 +30,19 @@ use std::{ use base_db::{ salsa::{self, ParallelDatabase}, - CrateId, FileId, SourceDatabaseExt, SourceRootId, + CrateId, FileRange, SourceDatabaseExt, SourceRootId, Upcast, }; +use either::Either; use fst::{self, Streamer}; -use hir::db::DefDatabase; -use rayon::prelude::*; -use rustc_hash::{FxHashMap, FxHashSet}; -use syntax::{ - ast::{self, HasName}, - match_ast, AstNode, Parse, SmolStr, SourceFile, - SyntaxKind::*, - SyntaxNode, SyntaxNodePtr, TextRange, WalkEvent, +use hir::{ + db::{DefDatabase, HirDatabase}, + AdtId, AssocContainerId, AssocItemId, AssocItemLoc, DefHasSource, DefWithBodyId, HasSource, + HirFileId, ImplId, InFile, ItemLoc, ItemTreeNode, Lookup, MacroDef, Module, ModuleDefId, + ModuleId, Semantics, TraitId, }; +use rayon::prelude::*; +use rustc_hash::FxHashSet; +use syntax::{ast::HasName, AstNode, SmolStr, SyntaxNode, SyntaxNodePtr}; use crate::RootDatabase; @@ -92,58 +93,68 @@ impl Query { } #[salsa::query_group(SymbolsDatabaseStorage)] -pub trait SymbolsDatabase: hir::db::HirDatabase + SourceDatabaseExt { - fn file_symbols(&self, file_id: FileId) -> Arc<SymbolIndex>; - fn library_symbols(&self) -> Arc<FxHashMap<SourceRootId, SymbolIndex>>; +pub trait SymbolsDatabase: HirDatabase + SourceDatabaseExt + Upcast<dyn HirDatabase> { + /// The symbol index for a given module. These modules should only be in source roots that + /// are inside local_roots. + fn module_symbols(&self, module_id: ModuleId) -> Arc<SymbolIndex>; + + /// The symbol index for a given source root within library_roots. + fn library_symbols(&self, source_root_id: SourceRootId) -> Arc<SymbolIndex>; + /// The set of "local" (that is, from the current workspace) roots. /// Files in local roots are assumed to change frequently. #[salsa::input] fn local_roots(&self) -> Arc<FxHashSet<SourceRootId>>; + /// The set of roots for crates.io libraries. /// Files in libraries are assumed to never change. #[salsa::input] fn library_roots(&self) -> Arc<FxHashSet<SourceRootId>>; } -fn library_symbols(db: &dyn SymbolsDatabase) -> Arc<FxHashMap<SourceRootId, SymbolIndex>> { +fn library_symbols(db: &dyn SymbolsDatabase, source_root_id: SourceRootId) -> Arc<SymbolIndex> { let _p = profile::span("library_symbols"); - let roots = db.library_roots(); - let res = roots + // todo: this could be parallelized, once I figure out how to do that... + let symbols = db + .source_root_crates(source_root_id) .iter() - .map(|&root_id| { - let root = db.source_root(root_id); - let files = root - .iter() - .map(|it| (it, SourceDatabaseExt::file_text(db, it))) - .collect::<Vec<_>>(); - let symbol_index = SymbolIndex::for_files( - files.into_par_iter().map(|(file, text)| (file, SourceFile::parse(&text))), - ); - (root_id, symbol_index) - }) + .flat_map(|&krate| module_ids_for_crate(db.upcast(), krate)) + // we specifically avoid calling SymbolsDatabase::module_symbols here, even they do the same thing, + // as the index for a library is not going to really ever change, and we do not want to store each + // module's index in salsa. + .map(|module_id| SymbolCollector::collect(db, module_id)) + .flatten() .collect(); - Arc::new(res) -} - -fn file_symbols(db: &dyn SymbolsDatabase, file_id: FileId) -> Arc<SymbolIndex> { - db.unwind_if_cancelled(); - let parse = db.parse(file_id); - - let symbols = source_file_to_file_symbols(&parse.tree(), file_id); - // FIXME: add macros here + Arc::new(SymbolIndex::new(symbols)) +} +fn module_symbols(db: &dyn SymbolsDatabase, module_id: ModuleId) -> Arc<SymbolIndex> { + let _p = profile::span("module_symbols"); + let symbols = SymbolCollector::collect(db, module_id); Arc::new(SymbolIndex::new(symbols)) } /// Need to wrap Snapshot to provide `Clone` impl for `map_with` struct Snap<DB>(DB); +impl<DB: ParallelDatabase> Snap<salsa::Snapshot<DB>> { + fn new(db: &DB) -> Self { + Self(db.snapshot()) + } +} impl<DB: ParallelDatabase> Clone for Snap<salsa::Snapshot<DB>> { fn clone(&self) -> Snap<salsa::Snapshot<DB>> { Snap(self.0.snapshot()) } } +impl<DB> std::ops::Deref for Snap<DB> { + type Target = DB; + + fn deref(&self) -> &Self::Target { + &self.0 + } +} // Feature: Workspace Symbol // @@ -174,51 +185,45 @@ impl<DB: ParallelDatabase> Clone for Snap<salsa::Snapshot<DB>> { pub fn world_symbols(db: &RootDatabase, query: Query) -> Vec<FileSymbol> { let _p = profile::span("world_symbols").detail(|| query.query.clone()); - let tmp1; - let tmp2; - let buf: Vec<&SymbolIndex> = if query.libs { - tmp1 = db.library_symbols(); - tmp1.values().collect() + let indices: Vec<_> = if query.libs { + db.library_roots() + .par_iter() + .map_with(Snap::new(db), |snap, &root| snap.library_symbols(root)) + .collect() } else { - let mut files = Vec::new(); + let mut module_ids = Vec::new(); + for &root in db.local_roots().iter() { - let sr = db.source_root(root); - files.extend(sr.iter()) + let crates = db.source_root_crates(root); + for &krate in crates.iter() { + module_ids.extend(module_ids_for_crate(db, krate)); + } } - let snap = Snap(db.snapshot()); - tmp2 = files + module_ids .par_iter() - .map_with(snap, |db, &file_id| db.0.file_symbols(file_id)) - .collect::<Vec<_>>(); - tmp2.iter().map(|it| &**it).collect() + .map_with(Snap::new(db), |snap, &module_id| snap.module_symbols(module_id)) + .collect() }; - query.search(&buf) + + query.search(&indices) } pub fn crate_symbols(db: &RootDatabase, krate: CrateId, query: Query) -> Vec<FileSymbol> { let _p = profile::span("crate_symbols").detail(|| format!("{:?}", query)); - // FIXME(#4842): This now depends on DefMap, why not build the entire symbol index from - // that instead? - let def_map = db.crate_def_map(krate); - let mut files = Vec::new(); - let mut modules = vec![def_map.root()]; - while let Some(module) = modules.pop() { - let data = &def_map[module]; - files.extend(data.origin.file_id()); - modules.extend(data.children.values()); - } - - let snap = Snap(db.snapshot()); - - let buf = files + let module_ids = module_ids_for_crate(db, krate); + let indices: Vec<_> = module_ids .par_iter() - .map_with(snap, |db, &file_id| db.0.file_symbols(file_id)) - .collect::<Vec<_>>(); - let buf = buf.iter().map(|it| &**it).collect::<Vec<_>>(); + .map_with(Snap::new(db), |snap, &module_id| snap.module_symbols(module_id)) + .collect(); - query.search(&buf) + query.search(&indices) +} + +fn module_ids_for_crate(db: &dyn DefDatabase, krate: CrateId) -> Vec<ModuleId> { + let def_map = db.crate_def_map(krate); + def_map.modules().map(|(id, _)| def_map.module_id(id)).collect() } pub fn index_resolve(db: &RootDatabase, name: &str) -> Vec<FileSymbol> { @@ -297,15 +302,6 @@ impl SymbolIndex { self.map.as_fst().size() + self.symbols.len() * mem::size_of::<FileSymbol>() } - pub(crate) fn for_files( - files: impl ParallelIterator<Item = (FileId, Parse<ast::SourceFile>)>, - ) -> SymbolIndex { - let symbols = files - .flat_map(|(file_id, file)| source_file_to_file_symbols(&file.tree(), file_id)) - .collect::<Vec<_>>(); - SymbolIndex::new(symbols) - } - fn range_to_map_value(start: usize, end: usize) -> u64 { debug_assert![start <= (std::u32::MAX as usize)]; debug_assert![end <= (std::u32::MAX as usize)]; @@ -321,7 +317,7 @@ impl SymbolIndex { } impl Query { - pub(crate) fn search(self, indices: &[&SymbolIndex]) -> Vec<FileSymbol> { + pub(crate) fn search(self, indices: &[Arc<SymbolIndex>]) -> Vec<FileSymbol> { let _p = profile::span("symbol_index::Query::search"); let mut op = fst::map::OpBuilder::new(); for file_symbols in indices.iter() { @@ -364,15 +360,49 @@ impl Query { /// possible. #[derive(Debug, Clone, PartialEq, Eq, Hash)] pub struct FileSymbol { - pub file_id: FileId, pub name: SmolStr, + pub loc: DeclarationLocation, pub kind: FileSymbolKind, - pub range: TextRange, - pub ptr: SyntaxNodePtr, - pub name_range: Option<TextRange>, pub container_name: Option<SmolStr>, } +#[derive(Debug, Clone, PartialEq, Eq, Hash)] +pub struct DeclarationLocation { + /// The file id for both the `ptr` and `name_ptr`. + pub hir_file_id: HirFileId, + /// This points to the whole syntax node of the declaration. + pub ptr: SyntaxNodePtr, + /// This points to the [`syntax::ast::Name`] identifier of the declaration. + pub name_ptr: SyntaxNodePtr, +} + +impl DeclarationLocation { + pub fn syntax(&self, semantics: &Semantics<'_, RootDatabase>) -> Option<SyntaxNode> { + let root = semantics.parse_or_expand(self.hir_file_id)?; + Some(self.ptr.to_node(&root)) + } + + pub fn original_range(&self, db: &dyn HirDatabase) -> Option<FileRange> { + find_original_file_range(db, self.hir_file_id, &self.ptr) + } + + pub fn original_name_range(&self, db: &dyn HirDatabase) -> Option<FileRange> { + find_original_file_range(db, self.hir_file_id, &self.name_ptr) + } +} + +fn find_original_file_range( + db: &dyn HirDatabase, + file_id: HirFileId, + ptr: &SyntaxNodePtr, +) -> Option<FileRange> { + let root = db.parse_or_expand(file_id)?; + let node = ptr.to_node(&root); + let node = InFile::new(file_id, &node); + + Some(node.original_file_range(db.upcast())) +} + #[derive(PartialEq, Eq, Hash, Clone, Copy, Debug)] pub enum FileSymbolKind { Const, @@ -400,79 +430,358 @@ impl FileSymbolKind { } } -fn source_file_to_file_symbols(source_file: &SourceFile, file_id: FileId) -> Vec<FileSymbol> { - let mut symbols = Vec::new(); - let mut stack = Vec::new(); +/// Represents an outstanding module that the symbol collector must collect symbols from. +struct SymbolCollectorWork { + module_id: ModuleId, + parent: Option<DefWithBodyId>, +} + +struct SymbolCollector<'a> { + db: &'a dyn SymbolsDatabase, + symbols: Vec<FileSymbol>, + work: Vec<SymbolCollectorWork>, + current_container_name: Option<SmolStr>, +} + +/// Given a [`ModuleId`] and a [`SymbolsDatabase`], use the DefMap for the module's crate to collect all symbols that should be +/// indexed for the given module. +impl<'a> SymbolCollector<'a> { + fn collect(db: &dyn SymbolsDatabase, module_id: ModuleId) -> Vec<FileSymbol> { + let mut symbol_collector = SymbolCollector { + db, + symbols: Default::default(), + current_container_name: None, + // The initial work is the root module we're collecting, additional work will + // be populated as we traverse the module's definitions. + work: vec![SymbolCollectorWork { module_id, parent: None }], + }; + + while let Some(work) = symbol_collector.work.pop() { + symbol_collector.do_work(work); + } + + symbol_collector.symbols + } + + fn do_work(&mut self, work: SymbolCollectorWork) { + self.db.unwind_if_cancelled(); + + let parent_name = work.parent.and_then(|id| self.def_with_body_id_name(id)); + self.with_container_name(parent_name, |s| s.collect_from_module(work.module_id)); + } - for event in source_file.syntax().preorder() { - match event { - WalkEvent::Enter(node) => { - if let Some(mut symbol) = to_file_symbol(&node, file_id) { - symbol.container_name = stack.last().cloned(); + fn collect_from_module(&mut self, module_id: ModuleId) { + let def_map = module_id.def_map(self.db.upcast()); + let scope = &def_map[module_id.local_id].scope; - stack.push(symbol.name.clone()); - symbols.push(symbol); + for module_def_id in scope.declarations() { + match module_def_id { + ModuleDefId::ModuleId(id) => self.push_module(id), + ModuleDefId::FunctionId(id) => { + self.push_decl_assoc(id, FileSymbolKind::Function); + self.collect_from_body(id); + } + ModuleDefId::AdtId(AdtId::StructId(id)) => { + self.push_decl(id, FileSymbolKind::Struct) + } + ModuleDefId::AdtId(AdtId::EnumId(id)) => self.push_decl(id, FileSymbolKind::Enum), + ModuleDefId::AdtId(AdtId::UnionId(id)) => self.push_decl(id, FileSymbolKind::Union), + ModuleDefId::ConstId(id) => { + self.push_decl_assoc(id, FileSymbolKind::Const); + self.collect_from_body(id); + } + ModuleDefId::StaticId(id) => { + self.push_decl(id, FileSymbolKind::Static); + self.collect_from_body(id); + } + ModuleDefId::TraitId(id) => { + self.push_decl(id, FileSymbolKind::Trait); + self.collect_from_trait(id); } + ModuleDefId::TypeAliasId(id) => { + self.push_decl_assoc(id, FileSymbolKind::TypeAlias); + } + // Don't index these. + ModuleDefId::BuiltinType(_) => {} + ModuleDefId::EnumVariantId(_) => {} } + } + + for impl_id in scope.impls() { + self.collect_from_impl(impl_id); + } - WalkEvent::Leave(node) => { - if to_symbol(&node).is_some() { - stack.pop(); + for const_id in scope.unnamed_consts() { + self.collect_from_body(const_id); + } + + for macro_def_id in scope.macro_declarations() { + self.push_decl_macro(macro_def_id.into()); + } + } + + fn collect_from_body(&mut self, body_id: impl Into<DefWithBodyId>) { + let body_id = body_id.into(); + let body = self.db.body(body_id); + + // Descend into the blocks and enqueue collection of all modules within. + for (_, def_map) in body.blocks(self.db.upcast()) { + for (id, _) in def_map.modules() { + self.work.push(SymbolCollectorWork { + module_id: def_map.module_id(id), + parent: Some(body_id), + }); + } + } + } + + fn collect_from_impl(&mut self, impl_id: ImplId) { + let impl_data = self.db.impl_data(impl_id); + for &assoc_item_id in &impl_data.items { + self.push_assoc_item(assoc_item_id) + } + } + + fn collect_from_trait(&mut self, trait_id: TraitId) { + let trait_data = self.db.trait_data(trait_id); + self.with_container_name(trait_data.name.as_text(), |s| { + for &(_, assoc_item_id) in &trait_data.items { + s.push_assoc_item(assoc_item_id); + } + }); + } + + fn with_container_name(&mut self, container_name: Option<SmolStr>, f: impl FnOnce(&mut Self)) { + if let Some(container_name) = container_name { + let prev = self.current_container_name.replace(container_name); + f(self); + self.current_container_name = prev; + } else { + f(self); + } + } + + fn current_container_name(&self) -> Option<SmolStr> { + self.current_container_name.clone() + } + + fn def_with_body_id_name(&self, body_id: DefWithBodyId) -> Option<SmolStr> { + match body_id { + DefWithBodyId::FunctionId(id) => Some( + id.lookup(self.db.upcast()).source(self.db.upcast()).value.name()?.text().into(), + ), + DefWithBodyId::StaticId(id) => Some( + id.lookup(self.db.upcast()).source(self.db.upcast()).value.name()?.text().into(), + ), + DefWithBodyId::ConstId(id) => Some( + id.lookup(self.db.upcast()).source(self.db.upcast()).value.name()?.text().into(), + ), + } + } + + fn push_assoc_item(&mut self, assoc_item_id: AssocItemId) { + match assoc_item_id { + AssocItemId::FunctionId(id) => self.push_decl_assoc(id, FileSymbolKind::Function), + AssocItemId::ConstId(id) => self.push_decl_assoc(id, FileSymbolKind::Const), + AssocItemId::TypeAliasId(id) => self.push_decl_assoc(id, FileSymbolKind::TypeAlias), + } + } + + fn push_decl_assoc<L, T>(&mut self, id: L, kind: FileSymbolKind) + where + L: Lookup<Data = AssocItemLoc<T>>, + T: ItemTreeNode, + <T as ItemTreeNode>::Source: HasName, + { + fn container_name(db: &dyn HirDatabase, container: AssocContainerId) -> Option<SmolStr> { + match container { + AssocContainerId::ModuleId(module_id) => { + let module = Module::from(module_id); + module.name(db).and_then(|name| name.as_text()) } + AssocContainerId::TraitId(trait_id) => { + let trait_data = db.trait_data(trait_id); + trait_data.name.as_text() + } + AssocContainerId::ImplId(_) => None, } } + + self.push_file_symbol(|s| { + let loc = id.lookup(s.db.upcast()); + let source = loc.source(s.db.upcast()); + let name_node = source.value.name()?; + let container_name = + container_name(s.db.upcast(), loc.container).or_else(|| s.current_container_name()); + + Some(FileSymbol { + name: name_node.text().into(), + kind, + container_name, + loc: DeclarationLocation { + hir_file_id: source.file_id, + ptr: SyntaxNodePtr::new(source.value.syntax()), + name_ptr: SyntaxNodePtr::new(name_node.syntax()), + }, + }) + }) } - symbols -} + fn push_decl<L, T>(&mut self, id: L, kind: FileSymbolKind) + where + L: Lookup<Data = ItemLoc<T>>, + T: ItemTreeNode, + <T as ItemTreeNode>::Source: HasName, + { + self.push_file_symbol(|s| { + let loc = id.lookup(s.db.upcast()); + let source = loc.source(s.db.upcast()); + let name_node = source.value.name()?; + + Some(FileSymbol { + name: name_node.text().into(), + kind, + container_name: s.current_container_name(), + loc: DeclarationLocation { + hir_file_id: source.file_id, + ptr: SyntaxNodePtr::new(source.value.syntax()), + name_ptr: SyntaxNodePtr::new(name_node.syntax()), + }, + }) + }) + } + + fn push_module(&mut self, module_id: ModuleId) { + self.push_file_symbol(|s| { + let def_map = module_id.def_map(s.db.upcast()); + let module_data = &def_map[module_id.local_id]; + let declaration = module_data.origin.declaration()?; + let module = declaration.to_node(s.db.upcast()); + let name_node = module.name()?; + + Some(FileSymbol { + name: name_node.text().into(), + kind: FileSymbolKind::Module, + container_name: s.current_container_name(), + loc: DeclarationLocation { + hir_file_id: declaration.file_id, + ptr: SyntaxNodePtr::new(module.syntax()), + name_ptr: SyntaxNodePtr::new(name_node.syntax()), + }, + }) + }) + } -fn to_symbol(node: &SyntaxNode) -> Option<(SmolStr, SyntaxNodePtr, TextRange)> { - fn decl<N: HasName>(node: N) -> Option<(SmolStr, SyntaxNodePtr, TextRange)> { - let name = node.name()?; - let name_range = name.syntax().text_range(); - let name = name.text().into(); - let ptr = SyntaxNodePtr::new(node.syntax()); + fn push_decl_macro(&mut self, macro_def: MacroDef) { + self.push_file_symbol(|s| { + let name = macro_def.name(s.db.upcast())?.as_text()?; + let source = macro_def.source(s.db.upcast())?; - Some((name, ptr, name_range)) + let (ptr, name_ptr) = match source.value { + Either::Left(m) => { + (SyntaxNodePtr::new(m.syntax()), SyntaxNodePtr::new(m.name()?.syntax())) + } + Either::Right(f) => { + (SyntaxNodePtr::new(f.syntax()), SyntaxNodePtr::new(f.name()?.syntax())) + } + }; + + Some(FileSymbol { + name, + kind: FileSymbolKind::Macro, + container_name: s.current_container_name(), + loc: DeclarationLocation { hir_file_id: source.file_id, name_ptr, ptr }, + }) + }) } - match_ast! { - match node { - ast::Fn(it) => decl(it), - ast::Struct(it) => decl(it), - ast::Enum(it) => decl(it), - ast::Trait(it) => decl(it), - ast::Module(it) => decl(it), - ast::TypeAlias(it) => decl(it), - ast::Const(it) => decl(it), - ast::Static(it) => decl(it), - ast::Macro(it) => decl(it), - ast::Union(it) => decl(it), - _ => None, + + fn push_file_symbol(&mut self, f: impl FnOnce(&Self) -> Option<FileSymbol>) { + if let Some(file_symbol) = f(self) { + self.symbols.push(file_symbol); } } } -fn to_file_symbol(node: &SyntaxNode, file_id: FileId) -> Option<FileSymbol> { - to_symbol(node).map(move |(name, ptr, name_range)| FileSymbol { - name, - kind: match node.kind() { - FN => FileSymbolKind::Function, - STRUCT => FileSymbolKind::Struct, - ENUM => FileSymbolKind::Enum, - TRAIT => FileSymbolKind::Trait, - MODULE => FileSymbolKind::Module, - TYPE_ALIAS => FileSymbolKind::TypeAlias, - CONST => FileSymbolKind::Const, - STATIC => FileSymbolKind::Static, - MACRO_RULES => FileSymbolKind::Macro, - MACRO_DEF => FileSymbolKind::Macro, - UNION => FileSymbolKind::Union, - kind => unreachable!("{:?}", kind), - }, - range: node.text_range(), - ptr, - file_id, - name_range: Some(name_range), - container_name: None, - }) +#[cfg(test)] +mod tests { + + use base_db::fixture::WithFixture; + use expect_test::expect_file; + + use super::*; + + #[test] + fn test_symbol_index_collection() { + let (db, _) = RootDatabase::with_many_files( + r#" +//- /main.rs + +macro_rules! macro_rules_macro { + () => {} +}; + +macro_rules! define_struct { + () => { + struct StructFromMacro; + } +}; + +define_struct!(); + +macro Macro { } + +struct Struct; +enum Enum { + A, B +} +union Union {} + +impl Struct { + fn impl_fn() {} +} + +trait Trait { + fn trait_fn(&self); +} + +fn main() { + struct StructInFn; +} + +const CONST: u32 = 1; +static STATIC: &'static str = "2"; +type Alias = Struct; + +mod a_mod { + struct StructInModA; +} + +const _: () = { + struct StructInUnnamedConst; + + () +}; + +const CONST_WITH_INNER: () = { + struct StructInNamedConst; + + () +}; + +mod b_mod; + +//- /b_mod.rs +struct StructInModB; + "#, + ); + + let symbols: Vec<_> = module_ids_for_crate(db.upcast(), db.test_crate()) + .into_iter() + .map(|module_id| { + (module_id, SymbolCollector::collect(&db as &dyn SymbolsDatabase, module_id)) + }) + .collect(); + + expect_file!["./test_data/test_symbol_index_collection.txt"].assert_debug_eq(&symbols); + } } |