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, FileRange, SourceDatabaseExt, SourceRootId, Upcast,
  34 };
  35 use either::Either;
  36 use fst::{self, Streamer};
  37 use hir::{
  38     db::{DefDatabase, HirDatabase},
  39     AdtId, AssocItemId, AssocItemLoc, DefHasSource, DefWithBodyId, HasSource, HirFileId, ImplId,
  40     InFile, ItemContainerId, ItemLoc, ItemTreeNode, Lookup, MacroDef, Module, ModuleDefId,
  41     ModuleId, Semantics, TraitId,
  42 };
  43 use rayon::prelude::*;
  44 use rustc_hash::FxHashSet;
  45 use syntax::{ast::HasName, AstNode, SmolStr, SyntaxNode, SyntaxNodePtr};
  46
  47 use crate::{RootDatabase, SymbolKind};
  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: HirDatabase + SourceDatabaseExt + Upcast<dyn HirDatabase> {
  97     /// The symbol index for a given module. These modules should only be in source roots that
  98     /// are inside local_roots.
  99     fn module_symbols(&self, module_id: ModuleId) -> Arc<SymbolIndex>;
 100
 101     /// The symbol index for a given source root within library_roots.
 102     fn library_symbols(&self, source_root_id: SourceRootId) -> Arc<SymbolIndex>;
 103
 104     /// The set of "local" (that is, from the current workspace) roots.
 105     /// Files in local roots are assumed to change frequently.
 106     #[salsa::input]
 107     fn local_roots(&self) -> Arc<FxHashSet<SourceRootId>>;
 108
 109     /// The set of roots for crates.io libraries.
 110     /// Files in libraries are assumed to never change.
 111     #[salsa::input]
 112     fn library_roots(&self) -> Arc<FxHashSet<SourceRootId>>;
 113 }
 114
 115 fn library_symbols(db: &dyn SymbolsDatabase, source_root_id: SourceRootId) -> Arc<SymbolIndex> {
 116     let _p = profile::span("library_symbols");
 117
 118     // todo: this could be parallelized, once I figure out how to do that...
 119     let symbols = db
 120         .source_root_crates(source_root_id)
 121         .iter()
 122         .flat_map(|&krate| module_ids_for_crate(db.upcast(), krate))
 123         // we specifically avoid calling SymbolsDatabase::module_symbols here, even they do the same thing,
 124         // as the index for a library is not going to really ever change, and we do not want to store each
 125         // module's index in salsa.
 126         .map(|module_id| SymbolCollector::collect(db, module_id))
 127         .flatten()
 128         .collect();
 129
 130     Arc::new(SymbolIndex::new(symbols))
 131 }
 132
 133 fn module_symbols(db: &dyn SymbolsDatabase, module_id: ModuleId) -> Arc<SymbolIndex> {
 134     let _p = profile::span("module_symbols");
 135     let symbols = SymbolCollector::collect(db, module_id);
 136     Arc::new(SymbolIndex::new(symbols))
 137 }
 138
 139 /// Need to wrap Snapshot to provide `Clone` impl for `map_with`
 140 struct Snap<DB>(DB);
 141 impl<DB: ParallelDatabase> Snap<salsa::Snapshot<DB>> {
 142     fn new(db: &DB) -> Self {
 143         Self(db.snapshot())
 144     }
 145 }
 146 impl<DB: ParallelDatabase> Clone for Snap<salsa::Snapshot<DB>> {
 147     fn clone(&self) -> Snap<salsa::Snapshot<DB>> {
 148         Snap(self.0.snapshot())
 149     }
 150 }
 151 impl<DB> std::ops::Deref for Snap<DB> {
 152     type Target = DB;
 153
 154     fn deref(&self) -> &Self::Target {
 155         &self.0
 156     }
 157 }
 158
 159 // Feature: Workspace Symbol
 160 //
 161 // Uses fuzzy-search to find types, modules and functions by name across your
 162 // project and dependencies. This is **the** most useful feature, which improves code
 163 // navigation tremendously. It mostly works on top of the built-in LSP
 164 // functionality, however `#` and `*` symbols can be used to narrow down the
 165 // search. Specifically,
 166 //
 167 // - `Foo` searches for `Foo` type in the current workspace
 168 // - `foo#` searches for `foo` function in the current workspace
 169 // - `Foo*` searches for `Foo` type among dependencies, including `stdlib`
 170 // - `foo#*` searches for `foo` function among dependencies
 171 //
 172 // That is, `#` switches from "types" to all symbols, `*` switches from the current
 173 // workspace to dependencies.
 174 //
 175 // Note that filtering does not currently work in VSCode due to the editor never
 176 // sending the special symbols to the language server. Instead, you can configure
 177 // the filtering via the `rust-analyzer.workspace.symbol.search.scope` and
 178 // `rust-analyzer.workspace.symbol.search.kind` settings.
 179 //
 180 // |===
 181 // | Editor  | Shortcut
 182 //
 183 // | VS Code | kbd:[Ctrl+T]
 184 // |===
 185 pub fn world_symbols(db: &RootDatabase, query: Query) -> Vec<FileSymbol> {
 186     let _p = profile::span("world_symbols").detail(|| query.query.clone());
 187
 188     let indices: Vec<_> = if query.libs {
 189         db.library_roots()
 190             .par_iter()
 191             .map_with(Snap::new(db), |snap, &root| snap.library_symbols(root))
 192             .collect()
 193     } else {
 194         let mut module_ids = Vec::new();
 195
 196         for &root in db.local_roots().iter() {
 197             let crates = db.source_root_crates(root);
 198             for &krate in crates.iter() {
 199                 module_ids.extend(module_ids_for_crate(db, krate));
 200             }
 201         }
 202
 203         module_ids
 204             .par_iter()
 205             .map_with(Snap::new(db), |snap, &module_id| snap.module_symbols(module_id))
 206             .collect()
 207     };
 208
 209     query.search(&indices)
 210 }
 211
 212 pub fn crate_symbols(db: &RootDatabase, krate: CrateId, query: Query) -> Vec<FileSymbol> {
 213     let _p = profile::span("crate_symbols").detail(|| format!("{:?}", query));
 214
 215     let module_ids = module_ids_for_crate(db, krate);
 216     let indices: Vec<_> = module_ids
 217         .par_iter()
 218         .map_with(Snap::new(db), |snap, &module_id| snap.module_symbols(module_id))
 219         .collect();
 220
 221     query.search(&indices)
 222 }
 223
 224 fn module_ids_for_crate(db: &dyn DefDatabase, krate: CrateId) -> Vec<ModuleId> {
 225     let def_map = db.crate_def_map(krate);
 226     def_map.modules().map(|(id, _)| def_map.module_id(id)).collect()
 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     fn range_to_map_value(start: usize, end: usize) -> u64 {
 306         debug_assert![start <= (std::u32::MAX as usize)];
 307         debug_assert![end <= (std::u32::MAX as usize)];
 308
 309         ((start as u64) << 32) | end as u64
 310     }
 311
 312     fn map_value_to_range(value: u64) -> (usize, usize) {
 313         let end = value as u32 as usize;
 314         let start = (value >> 32) as usize;
 315         (start, end)
 316     }
 317 }
 318
 319 impl Query {
 320     pub(crate) fn search(self, indices: &[Arc<SymbolIndex>]) -> Vec<FileSymbol> {
 321         let _p = profile::span("symbol_index::Query::search");
 322         let mut op = fst::map::OpBuilder::new();
 323         for file_symbols in indices.iter() {
 324             let automaton = fst::automaton::Subsequence::new(&self.lowercased);
 325             op = op.add(file_symbols.map.search(automaton))
 326         }
 327         let mut stream = op.union();
 328         let mut res = Vec::new();
 329         while let Some((_, indexed_values)) = stream.next() {
 330             for indexed_value in indexed_values {
 331                 let symbol_index = &indices[indexed_value.index];
 332                 let (start, end) = SymbolIndex::map_value_to_range(indexed_value.value);
 333
 334                 for symbol in &symbol_index.symbols[start..end] {
 335                     if self.only_types && !symbol.kind.is_type() {
 336                         continue;
 337                     }
 338                     if self.exact {
 339                         if symbol.name != self.query {
 340                             continue;
 341                         }
 342                     } else if self.case_sensitive {
 343                         if self.query.chars().any(|c| !symbol.name.contains(c)) {
 344                             continue;
 345                         }
 346                     }
 347
 348                     res.push(symbol.clone());
 349                     if res.len() >= self.limit {
 350                         return res;
 351                     }
 352                 }
 353             }
 354         }
 355         res
 356     }
 357 }
 358
 359 /// The actual data that is stored in the index. It should be as compact as
 360 /// possible.
 361 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
 362 pub struct FileSymbol {
 363     pub name: SmolStr,
 364     pub loc: DeclarationLocation,
 365     pub kind: FileSymbolKind,
 366     pub container_name: Option<SmolStr>,
 367 }
 368
 369 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
 370 pub struct DeclarationLocation {
 371     /// The file id for both the `ptr` and `name_ptr`.
 372     pub hir_file_id: HirFileId,
 373     /// This points to the whole syntax node of the declaration.
 374     pub ptr: SyntaxNodePtr,
 375     /// This points to the [`syntax::ast::Name`] identifier of the declaration.
 376     pub name_ptr: SyntaxNodePtr,
 377 }
 378
 379 impl DeclarationLocation {
 380     pub fn syntax(&self, semantics: &Semantics<'_, RootDatabase>) -> Option<SyntaxNode> {
 381         let root = semantics.parse_or_expand(self.hir_file_id)?;
 382         Some(self.ptr.to_node(&root))
 383     }
 384
 385     pub fn original_range(&self, db: &dyn HirDatabase) -> Option<FileRange> {
 386         find_original_file_range(db, self.hir_file_id, &self.ptr)
 387     }
 388
 389     pub fn original_name_range(&self, db: &dyn HirDatabase) -> Option<FileRange> {
 390         find_original_file_range(db, self.hir_file_id, &self.name_ptr)
 391     }
 392 }
 393
 394 fn find_original_file_range(
 395     db: &dyn HirDatabase,
 396     file_id: HirFileId,
 397     ptr: &SyntaxNodePtr,
 398 ) -> Option<FileRange> {
 399     let root = db.parse_or_expand(file_id)?;
 400     let node = ptr.to_node(&root);
 401     let node = InFile::new(file_id, &node);
 402
 403     Some(node.original_file_range(db.upcast()))
 404 }
 405
 406 #[derive(PartialEq, Eq, Hash, Clone, Copy, Debug)]
 407 pub enum FileSymbolKind {
 408     Const,
 409     Enum,
 410     Function,
 411     Macro,
 412     Module,
 413     Static,
 414     Struct,
 415     Trait,
 416     TypeAlias,
 417     Union,
 418 }
 419
 420 impl FileSymbolKind {
 421     fn is_type(self: FileSymbolKind) -> bool {
 422         matches!(
 423             self,
 424             FileSymbolKind::Struct
 425                 | FileSymbolKind::Enum
 426                 | FileSymbolKind::Trait
 427                 | FileSymbolKind::TypeAlias
 428                 | FileSymbolKind::Union
 429         )
 430     }
 431 }
 432
 433 impl From<FileSymbolKind> for SymbolKind {
 434     fn from(it: FileSymbolKind) -> Self {
 435         match it {
 436             FileSymbolKind::Const => SymbolKind::Const,
 437             FileSymbolKind::Enum => SymbolKind::Enum,
 438             FileSymbolKind::Function => SymbolKind::Function,
 439             FileSymbolKind::Macro => SymbolKind::Macro,
 440             FileSymbolKind::Module => SymbolKind::Module,
 441             FileSymbolKind::Static => SymbolKind::Static,
 442             FileSymbolKind::Struct => SymbolKind::Struct,
 443             FileSymbolKind::Trait => SymbolKind::Trait,
 444             FileSymbolKind::TypeAlias => SymbolKind::TypeAlias,
 445             FileSymbolKind::Union => SymbolKind::Union,
 446         }
 447     }
 448 }
 449
 450 /// Represents an outstanding module that the symbol collector must collect symbols from.
 451 struct SymbolCollectorWork {
 452     module_id: ModuleId,
 453     parent: Option<DefWithBodyId>,
 454 }
 455
 456 struct SymbolCollector<'a> {
 457     db: &'a dyn SymbolsDatabase,
 458     symbols: Vec<FileSymbol>,
 459     work: Vec<SymbolCollectorWork>,
 460     current_container_name: Option<SmolStr>,
 461 }
 462
 463 /// Given a [`ModuleId`] and a [`SymbolsDatabase`], use the DefMap for the module's crate to collect all symbols that should be
 464 /// indexed for the given module.
 465 impl<'a> SymbolCollector<'a> {
 466     fn collect(db: &dyn SymbolsDatabase, module_id: ModuleId) -> Vec<FileSymbol> {
 467         let mut symbol_collector = SymbolCollector {
 468             db,
 469             symbols: Default::default(),
 470             current_container_name: None,
 471             // The initial work is the root module we're collecting, additional work will
 472             // be populated as we traverse the module's definitions.
 473             work: vec![SymbolCollectorWork { module_id, parent: None }],
 474         };
 475
 476         while let Some(work) = symbol_collector.work.pop() {
 477             symbol_collector.do_work(work);
 478         }
 479
 480         symbol_collector.symbols
 481     }
 482
 483     fn do_work(&mut self, work: SymbolCollectorWork) {
 484         self.db.unwind_if_cancelled();
 485
 486         let parent_name = work.parent.and_then(|id| self.def_with_body_id_name(id));
 487         self.with_container_name(parent_name, |s| s.collect_from_module(work.module_id));
 488     }
 489
 490     fn collect_from_module(&mut self, module_id: ModuleId) {
 491         let def_map = module_id.def_map(self.db.upcast());
 492         let scope = &def_map[module_id.local_id].scope;
 493
 494         for module_def_id in scope.declarations() {
 495             match module_def_id {
 496                 ModuleDefId::ModuleId(id) => self.push_module(id),
 497                 ModuleDefId::FunctionId(id) => {
 498                     self.push_decl_assoc(id, FileSymbolKind::Function);
 499                     self.collect_from_body(id);
 500                 }
 501                 ModuleDefId::AdtId(AdtId::StructId(id)) => {
 502                     self.push_decl(id, FileSymbolKind::Struct)
 503                 }
 504                 ModuleDefId::AdtId(AdtId::EnumId(id)) => self.push_decl(id, FileSymbolKind::Enum),
 505                 ModuleDefId::AdtId(AdtId::UnionId(id)) => self.push_decl(id, FileSymbolKind::Union),
 506                 ModuleDefId::ConstId(id) => {
 507                     self.push_decl_assoc(id, FileSymbolKind::Const);
 508                     self.collect_from_body(id);
 509                 }
 510                 ModuleDefId::StaticId(id) => {
 511                     self.push_decl_assoc(id, FileSymbolKind::Static);
 512                     self.collect_from_body(id);
 513                 }
 514                 ModuleDefId::TraitId(id) => {
 515                     self.push_decl(id, FileSymbolKind::Trait);
 516                     self.collect_from_trait(id);
 517                 }
 518                 ModuleDefId::TypeAliasId(id) => {
 519                     self.push_decl_assoc(id, FileSymbolKind::TypeAlias);
 520                 }
 521                 // Don't index these.
 522                 ModuleDefId::BuiltinType(_) => {}
 523                 ModuleDefId::EnumVariantId(_) => {}
 524             }
 525         }
 526
 527         for impl_id in scope.impls() {
 528             self.collect_from_impl(impl_id);
 529         }
 530
 531         for const_id in scope.unnamed_consts() {
 532             self.collect_from_body(const_id);
 533         }
 534
 535         for macro_def_id in scope.macro_declarations() {
 536             self.push_decl_macro(macro_def_id.into());
 537         }
 538     }
 539
 540     fn collect_from_body(&mut self, body_id: impl Into<DefWithBodyId>) {
 541         let body_id = body_id.into();
 542         let body = self.db.body(body_id);
 543
 544         // Descend into the blocks and enqueue collection of all modules within.
 545         for (_, def_map) in body.blocks(self.db.upcast()) {
 546             for (id, _) in def_map.modules() {
 547                 self.work.push(SymbolCollectorWork {
 548                     module_id: def_map.module_id(id),
 549                     parent: Some(body_id),
 550                 });
 551             }
 552         }
 553     }
 554
 555     fn collect_from_impl(&mut self, impl_id: ImplId) {
 556         let impl_data = self.db.impl_data(impl_id);
 557         for &assoc_item_id in &impl_data.items {
 558             self.push_assoc_item(assoc_item_id)
 559         }
 560     }
 561
 562     fn collect_from_trait(&mut self, trait_id: TraitId) {
 563         let trait_data = self.db.trait_data(trait_id);
 564         self.with_container_name(trait_data.name.as_text(), |s| {
 565             for &(_, assoc_item_id) in &trait_data.items {
 566                 s.push_assoc_item(assoc_item_id);
 567             }
 568         });
 569     }
 570
 571     fn with_container_name(&mut self, container_name: Option<SmolStr>, f: impl FnOnce(&mut Self)) {
 572         if let Some(container_name) = container_name {
 573             let prev = self.current_container_name.replace(container_name);
 574             f(self);
 575             self.current_container_name = prev;
 576         } else {
 577             f(self);
 578         }
 579     }
 580
 581     fn current_container_name(&self) -> Option<SmolStr> {
 582         self.current_container_name.clone()
 583     }
 584
 585     fn def_with_body_id_name(&self, body_id: DefWithBodyId) -> Option<SmolStr> {
 586         match body_id {
 587             DefWithBodyId::FunctionId(id) => Some(
 588                 id.lookup(self.db.upcast()).source(self.db.upcast()).value.name()?.text().into(),
 589             ),
 590             DefWithBodyId::StaticId(id) => Some(
 591                 id.lookup(self.db.upcast()).source(self.db.upcast()).value.name()?.text().into(),
 592             ),
 593             DefWithBodyId::ConstId(id) => Some(
 594                 id.lookup(self.db.upcast()).source(self.db.upcast()).value.name()?.text().into(),
 595             ),
 596         }
 597     }
 598
 599     fn push_assoc_item(&mut self, assoc_item_id: AssocItemId) {
 600         match assoc_item_id {
 601             AssocItemId::FunctionId(id) => self.push_decl_assoc(id, FileSymbolKind::Function),
 602             AssocItemId::ConstId(id) => self.push_decl_assoc(id, FileSymbolKind::Const),
 603             AssocItemId::TypeAliasId(id) => self.push_decl_assoc(id, FileSymbolKind::TypeAlias),
 604         }
 605     }
 606
 607     fn push_decl_assoc<L, T>(&mut self, id: L, kind: FileSymbolKind)
 608     where
 609         L: Lookup<Data = AssocItemLoc<T>>,
 610         T: ItemTreeNode,
 611         <T as ItemTreeNode>::Source: HasName,
 612     {
 613         fn container_name(db: &dyn HirDatabase, container: ItemContainerId) -> Option<SmolStr> {
 614             match container {
 615                 ItemContainerId::ModuleId(module_id) => {
 616                     let module = Module::from(module_id);
 617                     module.name(db).and_then(|name| name.as_text())
 618                 }
 619                 ItemContainerId::TraitId(trait_id) => {
 620                     let trait_data = db.trait_data(trait_id);
 621                     trait_data.name.as_text()
 622                 }
 623                 ItemContainerId::ImplId(_) | ItemContainerId::ExternBlockId(_) => None,
 624             }
 625         }
 626
 627         self.push_file_symbol(|s| {
 628             let loc = id.lookup(s.db.upcast());
 629             let source = loc.source(s.db.upcast());
 630             let name_node = source.value.name()?;
 631             let container_name =
 632                 container_name(s.db.upcast(), loc.container).or_else(|| s.current_container_name());
 633
 634             Some(FileSymbol {
 635                 name: name_node.text().into(),
 636                 kind,
 637                 container_name,
 638                 loc: DeclarationLocation {
 639                     hir_file_id: source.file_id,
 640                     ptr: SyntaxNodePtr::new(source.value.syntax()),
 641                     name_ptr: SyntaxNodePtr::new(name_node.syntax()),
 642                 },
 643             })
 644         })
 645     }
 646
 647     fn push_decl<L, T>(&mut self, id: L, kind: FileSymbolKind)
 648     where
 649         L: Lookup<Data = ItemLoc<T>>,
 650         T: ItemTreeNode,
 651         <T as ItemTreeNode>::Source: HasName,
 652     {
 653         self.push_file_symbol(|s| {
 654             let loc = id.lookup(s.db.upcast());
 655             let source = loc.source(s.db.upcast());
 656             let name_node = source.value.name()?;
 657
 658             Some(FileSymbol {
 659                 name: name_node.text().into(),
 660                 kind,
 661                 container_name: s.current_container_name(),
 662                 loc: DeclarationLocation {
 663                     hir_file_id: source.file_id,
 664                     ptr: SyntaxNodePtr::new(source.value.syntax()),
 665                     name_ptr: SyntaxNodePtr::new(name_node.syntax()),
 666                 },
 667             })
 668         })
 669     }
 670
 671     fn push_module(&mut self, module_id: ModuleId) {
 672         self.push_file_symbol(|s| {
 673             let def_map = module_id.def_map(s.db.upcast());
 674             let module_data = &def_map[module_id.local_id];
 675             let declaration = module_data.origin.declaration()?;
 676             let module = declaration.to_node(s.db.upcast());
 677             let name_node = module.name()?;
 678
 679             Some(FileSymbol {
 680                 name: name_node.text().into(),
 681                 kind: FileSymbolKind::Module,
 682                 container_name: s.current_container_name(),
 683                 loc: DeclarationLocation {
 684                     hir_file_id: declaration.file_id,
 685                     ptr: SyntaxNodePtr::new(module.syntax()),
 686                     name_ptr: SyntaxNodePtr::new(name_node.syntax()),
 687                 },
 688             })
 689         })
 690     }
 691
 692     fn push_decl_macro(&mut self, macro_def: MacroDef) {
 693         self.push_file_symbol(|s| {
 694             let name = macro_def.name(s.db.upcast())?.as_text()?;
 695             let source = macro_def.source(s.db.upcast())?;
 696
 697             let (ptr, name_ptr) = match source.value {
 698                 Either::Left(m) => {
 699                     (SyntaxNodePtr::new(m.syntax()), SyntaxNodePtr::new(m.name()?.syntax()))
 700                 }
 701                 Either::Right(f) => {
 702                     (SyntaxNodePtr::new(f.syntax()), SyntaxNodePtr::new(f.name()?.syntax()))
 703                 }
 704             };
 705
 706             Some(FileSymbol {
 707                 name,
 708                 kind: FileSymbolKind::Macro,
 709                 container_name: s.current_container_name(),
 710                 loc: DeclarationLocation { hir_file_id: source.file_id, name_ptr, ptr },
 711             })
 712         })
 713     }
 714
 715     fn push_file_symbol(&mut self, f: impl FnOnce(&Self) -> Option<FileSymbol>) {
 716         if let Some(file_symbol) = f(self) {
 717             self.symbols.push(file_symbol);
 718         }
 719     }
 720 }
 721
 722 #[cfg(test)]
 723 mod tests {
 724
 725     use base_db::fixture::WithFixture;
 726     use expect_test::expect_file;
 727
 728     use super::*;
 729
 730     #[test]
 731     fn test_symbol_index_collection() {
 732         let (db, _) = RootDatabase::with_many_files(
 733             r#"
 734 //- /main.rs
 735
 736 macro_rules! macro_rules_macro {
 737     () => {}
 738 };
 739
 740 macro_rules! define_struct {
 741     () => {
 742         struct StructFromMacro;
 743     }
 744 };
 745
 746 define_struct!();
 747
 748 macro Macro { }
 749
 750 struct Struct;
 751 enum Enum {
 752     A, B
 753 }
 754 union Union {}
 755
 756 impl Struct {
 757     fn impl_fn() {}
 758 }
 759
 760 trait Trait {
 761     fn trait_fn(&self);
 762 }
 763
 764 fn main() {
 765     struct StructInFn;
 766 }
 767
 768 const CONST: u32 = 1;
 769 static STATIC: &'static str = "2";
 770 type Alias = Struct;
 771
 772 mod a_mod {
 773     struct StructInModA;
 774 }
 775
 776 const _: () = {
 777     struct StructInUnnamedConst;
 778
 779     ()
 780 };
 781
 782 const CONST_WITH_INNER: () = {
 783     struct StructInNamedConst;
 784
 785     ()
 786 };
 787
 788 mod b_mod;
 789
 790 //- /b_mod.rs
 791 struct StructInModB;
 792         "#,
 793         );
 794
 795         let symbols: Vec<_> = module_ids_for_crate(db.upcast(), db.test_crate())
 796             .into_iter()
 797             .map(|module_id| {
 798                 (module_id, SymbolCollector::collect(&db as &dyn SymbolsDatabase, module_id))
 799             })
 800             .collect();
 801
 802         expect_file!["./test_data/test_symbol_index_collection.txt"].assert_debug_eq(&symbols);
 803     }
 804 }