crates/ide_db/src/symbol_index.rs

   1 //! This module handles fuzzy-searching of functions, structs and other symbols
   2 //! by name across the whole workspace and dependencies.
   3 //!
   4 //! It works by building an incrementally-updated text-search index of all
   5 //! symbols. The backbone of the index is the **awesome** `fst` crate by
   6 //! @BurntSushi.
   7 //!
   8 //! In a nutshell, you give a set of strings to `fst`, and it builds a
   9 //! finite state machine describing this set of strings. The strings which
  10 //! could fuzzy-match a pattern can also be described by a finite state machine.
  11 //! What is freaking cool is that you can now traverse both state machines in
  12 //! lock-step to enumerate the strings which are both in the input set and
  13 //! fuzz-match the query. Or, more formally, given two languages described by
  14 //! FSTs, one can build a product FST which describes the intersection of the
  15 //! languages.
  16 //!
  17 //! `fst` does not support cheap updating of the index, but it supports unioning
  18 //! of state machines. So, to account for changing source code, we build an FST
  19 //! for each library (which is assumed to never change) and an FST for each Rust
  20 //! file in the current workspace, and run a query against the union of all
  21 //! those FSTs.
  22
  23 use std::{
  24     cmp::Ordering,
  25     fmt,
  26     hash::{Hash, Hasher},
  27     mem,
  28     sync::Arc,
  29 };
  30
  31 use base_db::{
  32     salsa::{self, ParallelDatabase},
  33     CrateId, FileId, FileRange, SourceDatabaseExt, SourceRootId, Upcast,
  34 };
  35 use fst::{self, Streamer};
  36 use hir::{
  37     db::DefDatabase, AdtId, AssocContainerId, AssocItemLoc, DefHasSource, DefWithBodyId, HirFileId,
  38     InFile, ItemLoc, ItemScope, ItemTreeNode, Lookup, ModuleData, ModuleDefId, ModuleId, Semantics,
  39 };
  40 use rayon::prelude::*;
  41 use rustc_hash::{FxHashMap, FxHashSet};
  42 use syntax::{
  43     ast::{self, HasName},
  44     AstNode, Parse, SmolStr, SourceFile, SyntaxNode, SyntaxNodePtr,
  45 };
  46
  47 use crate::RootDatabase;
  48
  49 #[derive(Debug)]
  50 pub struct Query {
  51     query: String,
  52     lowercased: String,
  53     only_types: bool,
  54     libs: bool,
  55     exact: bool,
  56     case_sensitive: bool,
  57     limit: usize,
  58 }
  59
  60 impl Query {
  61     pub fn new(query: String) -> Query {
  62         let lowercased = query.to_lowercase();
  63         Query {
  64             query,
  65             lowercased,
  66             only_types: false,
  67             libs: false,
  68             exact: false,
  69             case_sensitive: false,
  70             limit: usize::max_value(),
  71         }
  72     }
  73
  74     pub fn only_types(&mut self) {
  75         self.only_types = true;
  76     }
  77
  78     pub fn libs(&mut self) {
  79         self.libs = true;
  80     }
  81
  82     pub fn exact(&mut self) {
  83         self.exact = true;
  84     }
  85
  86     pub fn case_sensitive(&mut self) {
  87         self.case_sensitive = true;
  88     }
  89
  90     pub fn limit(&mut self, limit: usize) {
  91         self.limit = limit
  92     }
  93 }
  94
  95 #[salsa::query_group(SymbolsDatabaseStorage)]
  96 pub trait SymbolsDatabase: hir::db::HirDatabase + SourceDatabaseExt {
  97     fn module_symbols(&self, module_id: ModuleId) -> Arc<SymbolIndex>;
  98     fn library_symbols(&self) -> Arc<FxHashMap<SourceRootId, SymbolIndex>>;
  99     /// The set of "local" (that is, from the current workspace) roots.
 100     /// Files in local roots are assumed to change frequently.
 101     #[salsa::input]
 102     fn local_roots(&self) -> Arc<FxHashSet<SourceRootId>>;
 103     /// The set of roots for crates.io libraries.
 104     /// Files in libraries are assumed to never change.
 105     #[salsa::input]
 106     fn library_roots(&self) -> Arc<FxHashSet<SourceRootId>>;
 107 }
 108
 109 fn library_symbols(db: &dyn SymbolsDatabase) -> Arc<FxHashMap<SourceRootId, SymbolIndex>> {
 110     let _p = profile::span("library_symbols");
 111
 112     let roots = db.library_roots();
 113     let res = roots
 114         .iter()
 115         .map(|&root_id| {
 116             let root = db.source_root(root_id);
 117             let files = root
 118                 .iter()
 119                 .map(|it| (it, SourceDatabaseExt::file_text(db, it)))
 120                 .collect::<Vec<_>>();
 121             let symbol_index = SymbolIndex::for_files(
 122                 files.into_par_iter().map(|(file, text)| (file, SourceFile::parse(&text))),
 123             );
 124             (root_id, symbol_index)
 125         })
 126         .collect();
 127     Arc::new(res)
 128 }
 129
 130 fn module_symbols(db: &dyn SymbolsDatabase, module_id: ModuleId) -> Arc<SymbolIndex> {
 131     db.unwind_if_cancelled();
 132
 133     let def_map = module_id.def_map(db.upcast());
 134     let module_data = &def_map[module_id.local_id];
 135
 136     let symbols = module_data_to_file_symbols(db.upcast(), module_data);
 137
 138     Arc::new(SymbolIndex::new(symbols))
 139 }
 140
 141 /// Need to wrap Snapshot to provide `Clone` impl for `map_with`
 142 struct Snap<DB>(DB);
 143 impl<DB: ParallelDatabase> Clone for Snap<salsa::Snapshot<DB>> {
 144     fn clone(&self) -> Snap<salsa::Snapshot<DB>> {
 145         Snap(self.0.snapshot())
 146     }
 147 }
 148
 149 // Feature: Workspace Symbol
 150 //
 151 // Uses fuzzy-search to find types, modules and functions by name across your
 152 // project and dependencies. This is **the** most useful feature, which improves code
 153 // navigation tremendously. It mostly works on top of the built-in LSP
 154 // functionality, however `#` and `*` symbols can be used to narrow down the
 155 // search. Specifically,
 156 //
 157 // - `Foo` searches for `Foo` type in the current workspace
 158 // - `foo#` searches for `foo` function in the current workspace
 159 // - `Foo*` searches for `Foo` type among dependencies, including `stdlib`
 160 // - `foo#*` searches for `foo` function among dependencies
 161 //
 162 // That is, `#` switches from "types" to all symbols, `*` switches from the current
 163 // workspace to dependencies.
 164 //
 165 // Note that filtering does not currently work in VSCode due to the editor never
 166 // sending the special symbols to the language server. Instead, you can configure
 167 // the filtering via the `rust-analyzer.workspace.symbol.search.scope` and
 168 // `rust-analyzer.workspace.symbol.search.kind` settings.
 169 //
 170 // |===
 171 // | Editor  | Shortcut
 172 //
 173 // | VS Code | kbd:[Ctrl+T]
 174 // |===
 175 pub fn world_symbols(db: &RootDatabase, query: Query) -> Vec<FileSymbol> {
 176     let _p = profile::span("world_symbols").detail(|| query.query.clone());
 177
 178     let tmp1;
 179     let tmp2;
 180     let buf: Vec<&SymbolIndex> = if query.libs {
 181         tmp1 = db.library_symbols();
 182         tmp1.values().collect()
 183     } else {
 184         let mut module_ids = Vec::new();
 185
 186         for &root in db.local_roots().iter() {
 187             let crates = db.source_root_crates(root);
 188             for &krate in crates.iter() {
 189                 module_ids.extend(module_ids_for_crate(db, krate));
 190             }
 191         }
 192
 193         let snap = Snap(db.snapshot());
 194         tmp2 = module_ids
 195             .par_iter()
 196             .map_with(snap, |snap, &module_id| snap.0.module_symbols(module_id))
 197             .collect::<Vec<_>>();
 198         tmp2.iter().map(|it| &**it).collect()
 199     };
 200     query.search(&buf)
 201 }
 202
 203 pub fn crate_symbols(db: &RootDatabase, krate: CrateId, query: Query) -> Vec<FileSymbol> {
 204     let _p = profile::span("crate_symbols").detail(|| format!("{:?}", query));
 205
 206     let module_ids = module_ids_for_crate(db, krate);
 207     let snap = Snap(db.snapshot());
 208     let buf: Vec<_> = module_ids
 209         .par_iter()
 210         .map_with(snap, |snap, &module_id| snap.0.module_symbols(module_id))
 211         .collect();
 212     let buf = buf.iter().map(|it| &**it).collect::<Vec<_>>();
 213     query.search(&buf)
 214 }
 215
 216 fn module_ids_for_crate(db: &RootDatabase, krate: CrateId) -> Vec<ModuleId> {
 217     let def_map = db.crate_def_map(krate);
 218     let mut module_ids = Vec::new();
 219     let mut modules = vec![def_map.root()];
 220     while let Some(module) = modules.pop() {
 221         let data = &def_map[module];
 222         module_ids.push(def_map.module_id(module));
 223         modules.extend(data.children.values());
 224     }
 225
 226     module_ids
 227 }
 228
 229 pub fn index_resolve(db: &RootDatabase, name: &str) -> Vec<FileSymbol> {
 230     let mut query = Query::new(name.to_string());
 231     query.exact();
 232     query.limit(4);
 233     world_symbols(db, query)
 234 }
 235
 236 #[derive(Default)]
 237 pub struct SymbolIndex {
 238     symbols: Vec<FileSymbol>,
 239     map: fst::Map<Vec<u8>>,
 240 }
 241
 242 impl fmt::Debug for SymbolIndex {
 243     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 244         f.debug_struct("SymbolIndex").field("n_symbols", &self.symbols.len()).finish()
 245     }
 246 }
 247
 248 impl PartialEq for SymbolIndex {
 249     fn eq(&self, other: &SymbolIndex) -> bool {
 250         self.symbols == other.symbols
 251     }
 252 }
 253
 254 impl Eq for SymbolIndex {}
 255
 256 impl Hash for SymbolIndex {
 257     fn hash<H: Hasher>(&self, hasher: &mut H) {
 258         self.symbols.hash(hasher)
 259     }
 260 }
 261
 262 impl SymbolIndex {
 263     fn new(mut symbols: Vec<FileSymbol>) -> SymbolIndex {
 264         fn cmp(lhs: &FileSymbol, rhs: &FileSymbol) -> Ordering {
 265             let lhs_chars = lhs.name.chars().map(|c| c.to_ascii_lowercase());
 266             let rhs_chars = rhs.name.chars().map(|c| c.to_ascii_lowercase());
 267             lhs_chars.cmp(rhs_chars)
 268         }
 269
 270         symbols.par_sort_by(cmp);
 271
 272         let mut builder = fst::MapBuilder::memory();
 273
 274         let mut last_batch_start = 0;
 275
 276         for idx in 0..symbols.len() {
 277             if let Some(next_symbol) = symbols.get(idx + 1) {
 278                 if cmp(&symbols[last_batch_start], next_symbol) == Ordering::Equal {
 279                     continue;
 280                 }
 281             }
 282
 283             let start = last_batch_start;
 284             let end = idx + 1;
 285             last_batch_start = end;
 286
 287             let key = symbols[start].name.as_str().to_ascii_lowercase();
 288             let value = SymbolIndex::range_to_map_value(start, end);
 289
 290             builder.insert(key, value).unwrap();
 291         }
 292
 293         let map = fst::Map::new(builder.into_inner().unwrap()).unwrap();
 294         SymbolIndex { symbols, map }
 295     }
 296
 297     pub fn len(&self) -> usize {
 298         self.symbols.len()
 299     }
 300
 301     pub fn memory_size(&self) -> usize {
 302         self.map.as_fst().size() + self.symbols.len() * mem::size_of::<FileSymbol>()
 303     }
 304
 305     pub(crate) fn for_files(
 306         files: impl ParallelIterator<Item = (FileId, Parse<ast::SourceFile>)>,
 307     ) -> SymbolIndex {
 308         let symbols = files
 309             .flat_map(|(file_id, file)| source_file_to_file_symbols(&file.tree(), file_id))
 310             .collect::<Vec<_>>();
 311         SymbolIndex::new(symbols)
 312     }
 313
 314     fn range_to_map_value(start: usize, end: usize) -> u64 {
 315         debug_assert![start <= (std::u32::MAX as usize)];
 316         debug_assert![end <= (std::u32::MAX as usize)];
 317
 318         ((start as u64) << 32) | end as u64
 319     }
 320
 321     fn map_value_to_range(value: u64) -> (usize, usize) {
 322         let end = value as u32 as usize;
 323         let start = (value >> 32) as usize;
 324         (start, end)
 325     }
 326 }
 327
 328 impl Query {
 329     pub(crate) fn search(self, indices: &[&SymbolIndex]) -> Vec<FileSymbol> {
 330         let _p = profile::span("symbol_index::Query::search");
 331         let mut op = fst::map::OpBuilder::new();
 332         for file_symbols in indices.iter() {
 333             let automaton = fst::automaton::Subsequence::new(&self.lowercased);
 334             op = op.add(file_symbols.map.search(automaton))
 335         }
 336         let mut stream = op.union();
 337         let mut res = Vec::new();
 338         while let Some((_, indexed_values)) = stream.next() {
 339             for indexed_value in indexed_values {
 340                 let symbol_index = &indices[indexed_value.index];
 341                 let (start, end) = SymbolIndex::map_value_to_range(indexed_value.value);
 342
 343                 for symbol in &symbol_index.symbols[start..end] {
 344                     if self.only_types && !symbol.kind.is_type() {
 345                         continue;
 346                     }
 347                     if self.exact {
 348                         if symbol.name != self.query {
 349                             continue;
 350                         }
 351                     } else if self.case_sensitive {
 352                         if self.query.chars().any(|c| !symbol.name.contains(c)) {
 353                             continue;
 354                         }
 355                     }
 356
 357                     res.push(symbol.clone());
 358                     if res.len() >= self.limit {
 359                         return res;
 360                     }
 361                 }
 362             }
 363         }
 364         res
 365     }
 366 }
 367
 368 /// The actual data that is stored in the index. It should be as compact as
 369 /// possible.
 370 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
 371 pub struct FileSymbol {
 372     pub name: SmolStr,
 373     pub loc: DeclarationLocation,
 374     pub kind: FileSymbolKind,
 375     pub container_name: Option<SmolStr>,
 376 }
 377
 378 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
 379 pub struct DeclarationLocation {
 380     /// The file id for both the `ptr` and `name_ptr`.
 381     pub hir_file_id: HirFileId,
 382     /// This points to the whole syntax node of the declaration.
 383     pub ptr: SyntaxNodePtr,
 384     /// This points to the [`syntax::ast::Name`] identifier of the declaration.
 385     pub name_ptr: SyntaxNodePtr,
 386 }
 387
 388 impl DeclarationLocation {
 389     pub fn syntax(&self, semantics: &Semantics<'_, RootDatabase>) -> Option<SyntaxNode> {
 390         let root = semantics.parse_or_expand(self.hir_file_id)?;
 391         Some(self.ptr.to_node(&root))
 392     }
 393
 394     pub fn original_range(&self, semantics: &Semantics<'_, RootDatabase>) -> Option<FileRange> {
 395         find_original_file_range(semantics, self.hir_file_id, &self.ptr)
 396     }
 397
 398     pub fn original_name_range(
 399         &self,
 400         semantics: &Semantics<'_, RootDatabase>,
 401     ) -> Option<FileRange> {
 402         find_original_file_range(semantics, self.hir_file_id, &self.name_ptr)
 403     }
 404 }
 405
 406 fn find_original_file_range(
 407     semantics: &Semantics<'_, RootDatabase>,
 408     file_id: HirFileId,
 409     ptr: &SyntaxNodePtr,
 410 ) -> Option<FileRange> {
 411     let root = semantics.parse_or_expand(file_id)?;
 412     let node = ptr.to_node(&root);
 413     let node = InFile::new(file_id, &node);
 414
 415     Some(node.original_file_range(semantics.db.upcast()))
 416 }
 417
 418 #[derive(PartialEq, Eq, Hash, Clone, Copy, Debug)]
 419 pub enum FileSymbolKind {
 420     Const,
 421     Enum,
 422     Function,
 423     Macro,
 424     Module,
 425     Static,
 426     Struct,
 427     Trait,
 428     TypeAlias,
 429     Union,
 430 }
 431
 432 impl FileSymbolKind {
 433     fn is_type(self: FileSymbolKind) -> bool {
 434         matches!(
 435             self,
 436             FileSymbolKind::Struct
 437                 | FileSymbolKind::Enum
 438                 | FileSymbolKind::Trait
 439                 | FileSymbolKind::TypeAlias
 440                 | FileSymbolKind::Union
 441         )
 442     }
 443 }
 444
 445 fn source_file_to_file_symbols(_source_file: &SourceFile, _file_id: FileId) -> Vec<FileSymbol> {
 446     // todo: delete this.
 447     vec![]
 448 }
 449
 450 fn module_data_to_file_symbols(db: &dyn DefDatabase, module_data: &ModuleData) -> Vec<FileSymbol> {
 451     let mut symbols = Vec::new();
 452     collect_symbols_from_item_scope(db, &mut symbols, &module_data.scope);
 453     // todo: collect macros from scope.macros().
 454     symbols
 455 }
 456
 457 fn collect_symbols_from_item_scope(
 458     db: &dyn DefDatabase,
 459     symbols: &mut Vec<FileSymbol>,
 460     scope: &ItemScope,
 461 ) {
 462     fn container_name(db: &dyn DefDatabase, container: AssocContainerId) -> Option<SmolStr> {
 463         match container {
 464             AssocContainerId::ModuleId(module_id) => {
 465                 let def_map = module_id.def_map(db);
 466                 let module_data = &def_map[module_id.local_id];
 467                 module_data
 468                     .origin
 469                     .declaration()
 470                     .and_then(|s| s.to_node(db.upcast()).name().map(|n| n.text().into()))
 471             }
 472             AssocContainerId::TraitId(trait_id) => {
 473                 let loc = trait_id.lookup(db);
 474                 let source = loc.source(db);
 475                 source.value.name().map(|n| n.text().into())
 476             }
 477             AssocContainerId::ImplId(_) => None,
 478         }
 479     }
 480
 481     fn decl_assoc<L, T>(db: &dyn DefDatabase, id: L, kind: FileSymbolKind) -> Option<FileSymbol>
 482     where
 483         L: Lookup<Data = AssocItemLoc<T>>,
 484         T: ItemTreeNode,
 485         <T as ItemTreeNode>::Source: HasName,
 486     {
 487         let loc = id.lookup(db);
 488         let source = loc.source(db);
 489         let name_node = source.value.name()?;
 490         let container_name = container_name(db, loc.container);
 491
 492         Some(FileSymbol {
 493             name: name_node.text().into(),
 494             kind,
 495             container_name,
 496             loc: DeclarationLocation {
 497                 hir_file_id: source.file_id,
 498                 ptr: SyntaxNodePtr::new(source.value.syntax()),
 499                 name_ptr: SyntaxNodePtr::new(name_node.syntax()),
 500             },
 501         })
 502     }
 503
 504     fn decl<L, T>(db: &dyn DefDatabase, id: L, kind: FileSymbolKind) -> Option<FileSymbol>
 505     where
 506         L: Lookup<Data = ItemLoc<T>>,
 507         T: ItemTreeNode,
 508         <T as ItemTreeNode>::Source: HasName,
 509     {
 510         let loc = id.lookup(db);
 511         let source = loc.source(db);
 512         let name_node = source.value.name()?;
 513
 514         Some(FileSymbol {
 515             name: name_node.text().into(),
 516             kind,
 517             container_name: None,
 518             loc: DeclarationLocation {
 519                 hir_file_id: source.file_id,
 520                 ptr: SyntaxNodePtr::new(source.value.syntax()),
 521                 name_ptr: SyntaxNodePtr::new(name_node.syntax()),
 522             },
 523         })
 524     }
 525
 526     fn decl_module(db: &dyn DefDatabase, module_id: ModuleId) -> Option<FileSymbol> {
 527         let def_map = module_id.def_map(db);
 528         let module_data = &def_map[module_id.local_id];
 529         let declaration = module_data.origin.declaration()?;
 530         let module = declaration.to_node(db.upcast());
 531         let name_node = module.name()?;
 532
 533         Some(FileSymbol {
 534             name: name_node.text().into(),
 535             kind: FileSymbolKind::Module,
 536             container_name: None,
 537             loc: DeclarationLocation {
 538                 hir_file_id: declaration.file_id,
 539                 ptr: SyntaxNodePtr::new(module.syntax()),
 540                 name_ptr: SyntaxNodePtr::new(name_node.syntax()),
 541             },
 542         })
 543     }
 544
 545     let collect_symbols_from_scope =
 546         |scope: &ItemScope,
 547          symbols: &mut Vec<FileSymbol>,
 548          bodies_to_traverse: &mut Vec<DefWithBodyId>| {
 549             let symbols_iter =
 550                 scope.declarations().filter_map(|module_def_id| match module_def_id {
 551                     ModuleDefId::ModuleId(module_id) => decl_module(db, module_id),
 552                     ModuleDefId::FunctionId(function_id) => {
 553                         bodies_to_traverse.push(function_id.into());
 554                         decl_assoc(db, function_id, FileSymbolKind::Function)
 555                     }
 556                     ModuleDefId::AdtId(AdtId::StructId(struct_id)) => {
 557                         decl(db, struct_id, FileSymbolKind::Struct)
 558                     }
 559                     ModuleDefId::AdtId(AdtId::EnumId(enum_id)) => {
 560                         decl(db, enum_id, FileSymbolKind::Enum)
 561                     }
 562                     ModuleDefId::AdtId(AdtId::UnionId(union_id)) => {
 563                         decl(db, union_id, FileSymbolKind::Union)
 564                     }
 565                     ModuleDefId::ConstId(const_id) => {
 566                         bodies_to_traverse.push(const_id.into());
 567                         decl_assoc(db, const_id, FileSymbolKind::Const)
 568                     }
 569                     ModuleDefId::StaticId(static_id) => {
 570                         bodies_to_traverse.push(static_id.into());
 571                         decl(db, static_id, FileSymbolKind::Static)
 572                     }
 573                     ModuleDefId::TraitId(trait_id) => decl(db, trait_id, FileSymbolKind::Trait),
 574                     ModuleDefId::TypeAliasId(alias_id) => {
 575                         decl_assoc(db, alias_id, FileSymbolKind::TypeAlias)
 576                     }
 577                     ModuleDefId::BuiltinType(_) => None,
 578                     ModuleDefId::EnumVariantId(_) => None,
 579                 });
 580
 581             symbols.extend(symbols_iter);
 582
 583             for const_id in scope.unnamed_consts() {
 584                 bodies_to_traverse.push(const_id.into())
 585             }
 586         };
 587
 588     let mut bodies_to_traverse = Vec::new();
 589     collect_symbols_from_scope(scope, symbols, &mut bodies_to_traverse);
 590
 591     while let Some(body) = bodies_to_traverse.pop() {
 592         let body = db.body(body);
 593
 594         for (_, block_def_map) in body.blocks(db) {
 595             for (_, module_data) in block_def_map.modules() {
 596                 collect_symbols_from_scope(&module_data.scope, symbols, &mut bodies_to_traverse);
 597             }
 598         }
 599     }
 600 }