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, SourceDatabaseExt, SourceRootId,
  34 };
  35 use fst::{self, Streamer};
  36 use hir::db::DefDatabase;
  37 use rayon::prelude::*;
  38 use rustc_hash::{FxHashMap, FxHashSet};
  39 use syntax::{
  40     ast::{self, NameOwner},
  41     match_ast, AstNode, Parse, SmolStr, SourceFile,
  42     SyntaxKind::*,
  43     SyntaxNode, SyntaxNodePtr, TextRange, WalkEvent,
  44 };
  45
  46 use crate::RootDatabase;
  47
  48 #[derive(Debug)]
  49 pub struct Query {
  50     query: String,
  51     lowercased: String,
  52     only_types: bool,
  53     libs: bool,
  54     exact: bool,
  55     limit: usize,
  56 }
  57
  58 impl Query {
  59     pub fn new(query: String) -> Query {
  60         let lowercased = query.to_lowercase();
  61         Query {
  62             query,
  63             lowercased,
  64             only_types: false,
  65             libs: false,
  66             exact: false,
  67             limit: usize::max_value(),
  68         }
  69     }
  70
  71     pub fn only_types(&mut self) {
  72         self.only_types = true;
  73     }
  74
  75     pub fn libs(&mut self) {
  76         self.libs = true;
  77     }
  78
  79     pub fn exact(&mut self) {
  80         self.exact = true;
  81     }
  82
  83     pub fn limit(&mut self, limit: usize) {
  84         self.limit = limit
  85     }
  86 }
  87
  88 #[salsa::query_group(SymbolsDatabaseStorage)]
  89 pub trait SymbolsDatabase: hir::db::HirDatabase + SourceDatabaseExt {
  90     fn file_symbols(&self, file_id: FileId) -> Arc<SymbolIndex>;
  91     fn library_symbols(&self) -> Arc<FxHashMap<SourceRootId, SymbolIndex>>;
  92     /// The set of "local" (that is, from the current workspace) roots.
  93     /// Files in local roots are assumed to change frequently.
  94     #[salsa::input]
  95     fn local_roots(&self) -> Arc<FxHashSet<SourceRootId>>;
  96     /// The set of roots for crates.io libraries.
  97     /// Files in libraries are assumed to never change.
  98     #[salsa::input]
  99     fn library_roots(&self) -> Arc<FxHashSet<SourceRootId>>;
 100 }
 101
 102 fn library_symbols(db: &dyn SymbolsDatabase) -> Arc<FxHashMap<SourceRootId, SymbolIndex>> {
 103     let _p = profile::span("library_symbols");
 104
 105     let roots = db.library_roots();
 106     let res = roots
 107         .iter()
 108         .map(|&root_id| {
 109             let root = db.source_root(root_id);
 110             let files = root
 111                 .iter()
 112                 .map(|it| (it, SourceDatabaseExt::file_text(db, it)))
 113                 .collect::<Vec<_>>();
 114             let symbol_index = SymbolIndex::for_files(
 115                 files.into_par_iter().map(|(file, text)| (file, SourceFile::parse(&text))),
 116             );
 117             (root_id, symbol_index)
 118         })
 119         .collect();
 120     Arc::new(res)
 121 }
 122
 123 fn file_symbols(db: &dyn SymbolsDatabase, file_id: FileId) -> Arc<SymbolIndex> {
 124     db.check_canceled();
 125     let parse = db.parse(file_id);
 126
 127     let symbols = source_file_to_file_symbols(&parse.tree(), file_id);
 128
 129     // FIXME: add macros here
 130
 131     Arc::new(SymbolIndex::new(symbols))
 132 }
 133
 134 /// Need to wrap Snapshot to provide `Clone` impl for `map_with`
 135 struct Snap<DB>(DB);
 136 impl<DB: ParallelDatabase> Clone for Snap<salsa::Snapshot<DB>> {
 137     fn clone(&self) -> Snap<salsa::Snapshot<DB>> {
 138         Snap(self.0.snapshot())
 139     }
 140 }
 141
 142 // Feature: Workspace Symbol
 143 //
 144 // Uses fuzzy-search to find types, modules and functions by name across your
 145 // project and dependencies. This is **the** most useful feature, which improves code
 146 // navigation tremendously. It mostly works on top of the built-in LSP
 147 // functionality, however `#` and `*` symbols can be used to narrow down the
 148 // search. Specifically,
 149 //
 150 // - `Foo` searches for `Foo` type in the current workspace
 151 // - `foo#` searches for `foo` function in the current workspace
 152 // - `Foo*` searches for `Foo` type among dependencies, including `stdlib`
 153 // - `foo#*` searches for `foo` function among dependencies
 154 //
 155 // That is, `#` switches from "types" to all symbols, `*` switches from the current
 156 // workspace to dependencies.
 157 //
 158 // |===
 159 // | Editor  | Shortcut
 160 //
 161 // | VS Code | kbd:[Ctrl+T]
 162 // |===
 163 pub fn world_symbols(db: &RootDatabase, query: Query) -> Vec<FileSymbol> {
 164     let _p = profile::span("world_symbols").detail(|| query.query.clone());
 165
 166     let tmp1;
 167     let tmp2;
 168     let buf: Vec<&SymbolIndex> = if query.libs {
 169         tmp1 = db.library_symbols();
 170         tmp1.values().collect()
 171     } else {
 172         let mut files = Vec::new();
 173         for &root in db.local_roots().iter() {
 174             let sr = db.source_root(root);
 175             files.extend(sr.iter())
 176         }
 177
 178         let snap = Snap(db.snapshot());
 179         tmp2 = files
 180             .par_iter()
 181             .map_with(snap, |db, &file_id| db.0.file_symbols(file_id))
 182             .collect::<Vec<_>>();
 183         tmp2.iter().map(|it| &**it).collect()
 184     };
 185     query.search(&buf)
 186 }
 187
 188 pub fn crate_symbols(db: &RootDatabase, krate: CrateId, query: Query) -> Vec<FileSymbol> {
 189     // FIXME(#4842): This now depends on CrateDefMap, why not build the entire symbol index from
 190     // that instead?
 191
 192     let def_map = db.crate_def_map(krate);
 193     let mut files = Vec::new();
 194     let mut modules = vec![def_map.root];
 195     while let Some(module) = modules.pop() {
 196         let data = &def_map[module];
 197         files.extend(data.origin.file_id());
 198         modules.extend(data.children.values());
 199     }
 200
 201     let snap = Snap(db.snapshot());
 202
 203     let buf = files
 204         .par_iter()
 205         .map_with(snap, |db, &file_id| db.0.file_symbols(file_id))
 206         .collect::<Vec<_>>();
 207     let buf = buf.iter().map(|it| &**it).collect::<Vec<_>>();
 208
 209     query.search(&buf)
 210 }
 211
 212 pub fn index_resolve(db: &RootDatabase, name: &SmolStr) -> Vec<FileSymbol> {
 213     let mut query = Query::new(name.to_string());
 214     query.exact();
 215     query.limit(4);
 216     world_symbols(db, query)
 217 }
 218
 219 #[derive(Default)]
 220 pub struct SymbolIndex {
 221     symbols: Vec<FileSymbol>,
 222     map: fst::Map<Vec<u8>>,
 223 }
 224
 225 impl fmt::Debug for SymbolIndex {
 226     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 227         f.debug_struct("SymbolIndex").field("n_symbols", &self.symbols.len()).finish()
 228     }
 229 }
 230
 231 impl PartialEq for SymbolIndex {
 232     fn eq(&self, other: &SymbolIndex) -> bool {
 233         self.symbols == other.symbols
 234     }
 235 }
 236
 237 impl Eq for SymbolIndex {}
 238
 239 impl Hash for SymbolIndex {
 240     fn hash<H: Hasher>(&self, hasher: &mut H) {
 241         self.symbols.hash(hasher)
 242     }
 243 }
 244
 245 impl SymbolIndex {
 246     fn new(mut symbols: Vec<FileSymbol>) -> SymbolIndex {
 247         fn cmp(lhs: &FileSymbol, rhs: &FileSymbol) -> Ordering {
 248             let lhs_chars = lhs.name.chars().map(|c| c.to_ascii_lowercase());
 249             let rhs_chars = rhs.name.chars().map(|c| c.to_ascii_lowercase());
 250             lhs_chars.cmp(rhs_chars)
 251         }
 252
 253         symbols.par_sort_by(cmp);
 254
 255         let mut builder = fst::MapBuilder::memory();
 256
 257         let mut last_batch_start = 0;
 258
 259         for idx in 0..symbols.len() {
 260             if let Some(next_symbol) = symbols.get(idx + 1) {
 261                 if cmp(&symbols[last_batch_start], next_symbol) == Ordering::Equal {
 262                     continue;
 263                 }
 264             }
 265
 266             let start = last_batch_start;
 267             let end = idx + 1;
 268             last_batch_start = end;
 269
 270             let key = symbols[start].name.as_str().to_ascii_lowercase();
 271             let value = SymbolIndex::range_to_map_value(start, end);
 272
 273             builder.insert(key, value).unwrap();
 274         }
 275
 276         let map = fst::Map::new(builder.into_inner().unwrap()).unwrap();
 277         SymbolIndex { symbols, map }
 278     }
 279
 280     pub fn len(&self) -> usize {
 281         self.symbols.len()
 282     }
 283
 284     pub fn memory_size(&self) -> usize {
 285         self.map.as_fst().size() + self.symbols.len() * mem::size_of::<FileSymbol>()
 286     }
 287
 288     pub(crate) fn for_files(
 289         files: impl ParallelIterator<Item = (FileId, Parse<ast::SourceFile>)>,
 290     ) -> SymbolIndex {
 291         let symbols = files
 292             .flat_map(|(file_id, file)| source_file_to_file_symbols(&file.tree(), file_id))
 293             .collect::<Vec<_>>();
 294         SymbolIndex::new(symbols)
 295     }
 296
 297     fn range_to_map_value(start: usize, end: usize) -> u64 {
 298         debug_assert![start <= (std::u32::MAX as usize)];
 299         debug_assert![end <= (std::u32::MAX as usize)];
 300
 301         ((start as u64) << 32) | end as u64
 302     }
 303
 304     fn map_value_to_range(value: u64) -> (usize, usize) {
 305         let end = value as u32 as usize;
 306         let start = (value >> 32) as usize;
 307         (start, end)
 308     }
 309 }
 310
 311 impl Query {
 312     pub(crate) fn search(self, indices: &[&SymbolIndex]) -> Vec<FileSymbol> {
 313         let mut op = fst::map::OpBuilder::new();
 314         for file_symbols in indices.iter() {
 315             let automaton = fst::automaton::Subsequence::new(&self.lowercased);
 316             op = op.add(file_symbols.map.search(automaton))
 317         }
 318         let mut stream = op.union();
 319         let mut res = Vec::new();
 320         while let Some((_, indexed_values)) = stream.next() {
 321             for indexed_value in indexed_values {
 322                 let symbol_index = &indices[indexed_value.index];
 323                 let (start, end) = SymbolIndex::map_value_to_range(indexed_value.value);
 324
 325                 for symbol in &symbol_index.symbols[start..end] {
 326                     if self.only_types && !symbol.kind.is_type() {
 327                         continue;
 328                     }
 329                     if self.exact && symbol.name != self.query {
 330                         continue;
 331                     }
 332
 333                     res.push(symbol.clone());
 334                     if res.len() >= self.limit {
 335                         return res;
 336                     }
 337                 }
 338             }
 339         }
 340         res
 341     }
 342 }
 343
 344 /// The actual data that is stored in the index. It should be as compact as
 345 /// possible.
 346 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
 347 pub struct FileSymbol {
 348     pub file_id: FileId,
 349     pub name: SmolStr,
 350     pub kind: FileSymbolKind,
 351     pub range: TextRange,
 352     pub ptr: SyntaxNodePtr,
 353     pub name_range: Option<TextRange>,
 354     pub container_name: Option<SmolStr>,
 355 }
 356
 357 #[derive(PartialEq, Eq, Hash, Clone, Copy, Debug)]
 358 pub enum FileSymbolKind {
 359     Function,
 360     Struct,
 361     Enum,
 362     Trait,
 363     Module,
 364     TypeAlias,
 365     Const,
 366     Static,
 367     Macro,
 368 }
 369
 370 impl FileSymbolKind {
 371     fn is_type(self: FileSymbolKind) -> bool {
 372         matches!(
 373             self,
 374             FileSymbolKind::Struct
 375                 | FileSymbolKind::Enum
 376                 | FileSymbolKind::Trait
 377                 | FileSymbolKind::TypeAlias
 378         )
 379     }
 380 }
 381
 382 fn source_file_to_file_symbols(source_file: &SourceFile, file_id: FileId) -> Vec<FileSymbol> {
 383     let mut symbols = Vec::new();
 384     let mut stack = Vec::new();
 385
 386     for event in source_file.syntax().preorder() {
 387         match event {
 388             WalkEvent::Enter(node) => {
 389                 if let Some(mut symbol) = to_file_symbol(&node, file_id) {
 390                     symbol.container_name = stack.last().cloned();
 391
 392                     stack.push(symbol.name.clone());
 393                     symbols.push(symbol);
 394                 }
 395             }
 396
 397             WalkEvent::Leave(node) => {
 398                 if to_symbol(&node).is_some() {
 399                     stack.pop();
 400                 }
 401             }
 402         }
 403     }
 404
 405     symbols
 406 }
 407
 408 fn to_symbol(node: &SyntaxNode) -> Option<(SmolStr, SyntaxNodePtr, TextRange)> {
 409     fn decl<N: NameOwner>(node: N) -> Option<(SmolStr, SyntaxNodePtr, TextRange)> {
 410         let name = node.name()?;
 411         let name_range = name.syntax().text_range();
 412         let name = name.text().clone();
 413         let ptr = SyntaxNodePtr::new(node.syntax());
 414
 415         Some((name, ptr, name_range))
 416     }
 417     match_ast! {
 418         match node {
 419             ast::Fn(it) => decl(it),
 420             ast::Struct(it) => decl(it),
 421             ast::Enum(it) => decl(it),
 422             ast::Trait(it) => decl(it),
 423             ast::Module(it) => decl(it),
 424             ast::TypeAlias(it) => decl(it),
 425             ast::Const(it) => decl(it),
 426             ast::Static(it) => decl(it),
 427             ast::MacroRules(it) => decl(it),
 428             _ => None,
 429         }
 430     }
 431 }
 432
 433 fn to_file_symbol(node: &SyntaxNode, file_id: FileId) -> Option<FileSymbol> {
 434     to_symbol(node).map(move |(name, ptr, name_range)| FileSymbol {
 435         name,
 436         kind: match node.kind() {
 437             FN => FileSymbolKind::Function,
 438             STRUCT => FileSymbolKind::Struct,
 439             ENUM => FileSymbolKind::Enum,
 440             TRAIT => FileSymbolKind::Trait,
 441             MODULE => FileSymbolKind::Module,
 442             TYPE_ALIAS => FileSymbolKind::TypeAlias,
 443             CONST => FileSymbolKind::Const,
 444             STATIC => FileSymbolKind::Static,
 445             MACRO_RULES => FileSymbolKind::Macro,
 446             kind => unreachable!("{:?}", kind),
 447         },
 448         range: node.text_range(),
 449         ptr,
 450         file_id,
 451         name_range: Some(name_range),
 452         container_name: None,
 453     })
 454 }