1 //! This module handles fuzzy-searching of functions, structs and other symbols
2 //! by name across the whole workspace and dependencies.
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
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
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
32 salsa::{self, ParallelDatabase},
33 SourceDatabaseExt, SourceRootId, Upcast,
35 use fst::{self, Streamer};
38 symbols::{FileSymbol, SymbolCollector},
41 use rayon::prelude::*;
42 use rustc_hash::FxHashSet;
44 use crate::RootDatabase;
58 pub fn new(query: String) -> Query {
59 let lowercased = query.to_lowercase();
66 case_sensitive: false,
67 limit: usize::max_value(),
71 pub fn only_types(&mut self) {
72 self.only_types = true;
75 pub fn libs(&mut self) {
79 pub fn exact(&mut self) {
83 pub fn case_sensitive(&mut self) {
84 self.case_sensitive = true;
87 pub fn limit(&mut self, limit: usize) {
92 #[salsa::query_group(SymbolsDatabaseStorage)]
93 pub trait SymbolsDatabase: HirDatabase + SourceDatabaseExt + Upcast<dyn HirDatabase> {
94 /// The symbol index for a given module. These modules should only be in source roots that
95 /// are inside local_roots.
96 fn module_symbols(&self, module: Module) -> Arc<SymbolIndex>;
98 /// The symbol index for a given source root within library_roots.
99 fn library_symbols(&self, source_root_id: SourceRootId) -> Arc<SymbolIndex>;
101 /// The set of "local" (that is, from the current workspace) roots.
102 /// Files in local roots are assumed to change frequently.
104 fn local_roots(&self) -> Arc<FxHashSet<SourceRootId>>;
106 /// The set of roots for crates.io libraries.
107 /// Files in libraries are assumed to never change.
109 fn library_roots(&self) -> Arc<FxHashSet<SourceRootId>>;
112 fn library_symbols(db: &dyn SymbolsDatabase, source_root_id: SourceRootId) -> Arc<SymbolIndex> {
113 let _p = profile::span("library_symbols");
115 // todo: this could be parallelized, once I figure out how to do that...
117 .source_root_crates(source_root_id)
119 .flat_map(|&krate| Crate::from(krate).modules(db.upcast()))
120 // we specifically avoid calling SymbolsDatabase::module_symbols here, even they do the same thing,
121 // as the index for a library is not going to really ever change, and we do not want to store each
122 // module's index in salsa.
123 .flat_map(|module| SymbolCollector::collect(db.upcast(), module))
126 Arc::new(SymbolIndex::new(symbols))
129 fn module_symbols(db: &dyn SymbolsDatabase, module: Module) -> Arc<SymbolIndex> {
130 let _p = profile::span("module_symbols");
131 let symbols = SymbolCollector::collect(db.upcast(), module);
132 Arc::new(SymbolIndex::new(symbols))
135 /// Need to wrap Snapshot to provide `Clone` impl for `map_with`
137 impl<DB: ParallelDatabase> Snap<salsa::Snapshot<DB>> {
138 fn new(db: &DB) -> Self {
142 impl<DB: ParallelDatabase> Clone for Snap<salsa::Snapshot<DB>> {
143 fn clone(&self) -> Snap<salsa::Snapshot<DB>> {
144 Snap(self.0.snapshot())
147 impl<DB> std::ops::Deref for Snap<DB> {
150 fn deref(&self) -> &Self::Target {
155 // Feature: Workspace Symbol
157 // Uses fuzzy-search to find types, modules and functions by name across your
158 // project and dependencies. This is **the** most useful feature, which improves code
159 // navigation tremendously. It mostly works on top of the built-in LSP
160 // functionality, however `#` and `*` symbols can be used to narrow down the
161 // search. Specifically,
163 // - `Foo` searches for `Foo` type in the current workspace
164 // - `foo#` searches for `foo` function in the current workspace
165 // - `Foo*` searches for `Foo` type among dependencies, including `stdlib`
166 // - `foo#*` searches for `foo` function among dependencies
168 // That is, `#` switches from "types" to all symbols, `*` switches from the current
169 // workspace to dependencies.
171 // Note that filtering does not currently work in VSCode due to the editor never
172 // sending the special symbols to the language server. Instead, you can configure
173 // the filtering via the `rust-analyzer.workspace.symbol.search.scope` and
174 // `rust-analyzer.workspace.symbol.search.kind` settings.
177 // | Editor | Shortcut
179 // | VS Code | kbd:[Ctrl+T]
181 pub fn world_symbols(db: &RootDatabase, query: Query) -> Vec<FileSymbol> {
182 let _p = profile::span("world_symbols").detail(|| query.query.clone());
184 let indices: Vec<_> = if query.libs {
187 .map_with(Snap::new(db), |snap, &root| snap.library_symbols(root))
190 let mut modules = Vec::new();
192 for &root in db.local_roots().iter() {
193 let crates = db.source_root_crates(root);
194 for &krate in crates.iter() {
195 modules.extend(Crate::from(krate).modules(db));
201 .map_with(Snap::new(db), |snap, &module| snap.module_symbols(module))
205 query.search(&indices)
208 pub fn crate_symbols(db: &RootDatabase, krate: Crate, query: Query) -> Vec<FileSymbol> {
209 let _p = profile::span("crate_symbols").detail(|| format!("{:?}", query));
211 let modules = krate.modules(db);
212 let indices: Vec<_> = modules
214 .map_with(Snap::new(db), |snap, &module| snap.module_symbols(module))
217 query.search(&indices)
221 pub struct SymbolIndex {
222 symbols: Vec<FileSymbol>,
223 map: fst::Map<Vec<u8>>,
226 impl fmt::Debug for SymbolIndex {
227 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
228 f.debug_struct("SymbolIndex").field("n_symbols", &self.symbols.len()).finish()
232 impl PartialEq for SymbolIndex {
233 fn eq(&self, other: &SymbolIndex) -> bool {
234 self.symbols == other.symbols
238 impl Eq for SymbolIndex {}
240 impl Hash for SymbolIndex {
241 fn hash<H: Hasher>(&self, hasher: &mut H) {
242 self.symbols.hash(hasher)
247 fn new(mut symbols: Vec<FileSymbol>) -> SymbolIndex {
248 fn cmp(lhs: &FileSymbol, rhs: &FileSymbol) -> Ordering {
249 let lhs_chars = lhs.name.chars().map(|c| c.to_ascii_lowercase());
250 let rhs_chars = rhs.name.chars().map(|c| c.to_ascii_lowercase());
251 lhs_chars.cmp(rhs_chars)
254 symbols.par_sort_by(cmp);
256 let mut builder = fst::MapBuilder::memory();
258 let mut last_batch_start = 0;
260 for idx in 0..symbols.len() {
261 if let Some(next_symbol) = symbols.get(idx + 1) {
262 if cmp(&symbols[last_batch_start], next_symbol) == Ordering::Equal {
267 let start = last_batch_start;
269 last_batch_start = end;
271 let key = symbols[start].name.as_str().to_ascii_lowercase();
272 let value = SymbolIndex::range_to_map_value(start, end);
274 builder.insert(key, value).unwrap();
277 let map = fst::Map::new(builder.into_inner().unwrap()).unwrap();
278 SymbolIndex { symbols, map }
281 pub fn len(&self) -> usize {
285 pub fn memory_size(&self) -> usize {
286 self.map.as_fst().size() + self.symbols.len() * mem::size_of::<FileSymbol>()
289 fn range_to_map_value(start: usize, end: usize) -> u64 {
290 debug_assert![start <= (std::u32::MAX as usize)];
291 debug_assert![end <= (std::u32::MAX as usize)];
293 ((start as u64) << 32) | end as u64
296 fn map_value_to_range(value: u64) -> (usize, usize) {
297 let end = value as u32 as usize;
298 let start = (value >> 32) as usize;
304 pub(crate) fn search(self, indices: &[Arc<SymbolIndex>]) -> Vec<FileSymbol> {
305 let _p = profile::span("symbol_index::Query::search");
306 let mut op = fst::map::OpBuilder::new();
307 for file_symbols in indices.iter() {
308 let automaton = fst::automaton::Subsequence::new(&self.lowercased);
309 op = op.add(file_symbols.map.search(automaton))
311 let mut stream = op.union();
312 let mut res = Vec::new();
313 while let Some((_, indexed_values)) = stream.next() {
314 for indexed_value in indexed_values {
315 let symbol_index = &indices[indexed_value.index];
316 let (start, end) = SymbolIndex::map_value_to_range(indexed_value.value);
318 for symbol in &symbol_index.symbols[start..end] {
319 if self.only_types && !symbol.kind.is_type() {
323 if symbol.name != self.query {
326 } else if self.case_sensitive {
327 if self.query.chars().any(|c| !symbol.name.contains(c)) {
332 res.push(symbol.clone());
333 if res.len() >= self.limit {
346 use base_db::fixture::WithFixture;
347 use expect_test::expect_file;
348 use hir::symbols::SymbolCollector;
353 fn test_symbol_index_collection() {
354 let (db, _) = RootDatabase::with_many_files(
358 macro_rules! macro_rules_macro {
362 macro_rules! define_struct {
364 struct StructFromMacro;
390 const CONST: u32 = 1;
391 static STATIC: &'static str = "2";
399 struct StructInUnnamedConst;
404 const CONST_WITH_INNER: () = {
405 struct StructInNamedConst;
417 let symbols: Vec<_> = Crate::from(db.test_crate())
421 let mut symbols = SymbolCollector::collect(&db, module_id);
422 symbols.sort_by_key(|it| it.name.clone());
427 expect_file!["./test_data/test_symbol_index_collection.txt"].assert_debug_eq(&symbols);