]> git.lizzy.rs Git - rust.git/blob - crates/ide_db/src/search.rs
7be76dca107bb34a59bc5dfea5bb066a8d7c3391
[rust.git] / crates / ide_db / src / search.rs
1 //! Implementation of find-usages functionality.
2 //!
3 //! It is based on the standard ide trick: first, we run a fast text search to
4 //! get a super-set of matches. Then, we we confirm each match using precise
5 //! name resolution.
6
7 use std::{convert::TryInto, mem};
8
9 use base_db::{FileId, FileRange, SourceDatabase, SourceDatabaseExt};
10 use hir::{
11     AsAssocItem, DefWithBody, HasAttrs, HasSource, InFile, ModuleDef, ModuleSource, Semantics,
12     Visibility,
13 };
14 use once_cell::unsync::Lazy;
15 use rustc_hash::FxHashMap;
16 use syntax::{ast, match_ast, AstNode, TextRange, TextSize};
17
18 use crate::{
19     defs::{Definition, NameClass, NameRefClass},
20     RootDatabase,
21 };
22
23 #[derive(Debug, Default, Clone)]
24 pub struct UsageSearchResult {
25     pub references: FxHashMap<FileId, Vec<FileReference>>,
26 }
27
28 impl UsageSearchResult {
29     pub fn is_empty(&self) -> bool {
30         self.references.is_empty()
31     }
32
33     pub fn len(&self) -> usize {
34         self.references.len()
35     }
36
37     pub fn iter(&self) -> impl Iterator<Item = (&FileId, &Vec<FileReference>)> + '_ {
38         self.references.iter()
39     }
40
41     pub fn file_ranges(&self) -> impl Iterator<Item = FileRange> + '_ {
42         self.references.iter().flat_map(|(&file_id, refs)| {
43             refs.iter().map(move |&FileReference { range, .. }| FileRange { file_id, range })
44         })
45     }
46 }
47
48 impl IntoIterator for UsageSearchResult {
49     type Item = (FileId, Vec<FileReference>);
50     type IntoIter = <FxHashMap<FileId, Vec<FileReference>> as IntoIterator>::IntoIter;
51
52     fn into_iter(self) -> Self::IntoIter {
53         self.references.into_iter()
54     }
55 }
56
57 #[derive(Debug, Clone)]
58 pub struct FileReference {
59     pub range: TextRange,
60     pub name: ast::NameLike,
61     pub access: Option<ReferenceAccess>,
62 }
63
64 #[derive(Debug, Copy, Clone, PartialEq)]
65 pub enum ReferenceAccess {
66     Read,
67     Write,
68 }
69
70 /// Generally, `search_scope` returns files that might contain references for the element.
71 /// For `pub(crate)` things it's a crate, for `pub` things it's a crate and dependant crates.
72 /// In some cases, the location of the references is known to within a `TextRange`,
73 /// e.g. for things like local variables.
74 pub struct SearchScope {
75     entries: FxHashMap<FileId, Option<TextRange>>,
76 }
77
78 impl SearchScope {
79     fn new(entries: FxHashMap<FileId, Option<TextRange>>) -> SearchScope {
80         SearchScope { entries }
81     }
82
83     fn crate_graph(db: &RootDatabase) -> SearchScope {
84         let mut entries = FxHashMap::default();
85
86         let graph = db.crate_graph();
87         for krate in graph.iter() {
88             let root_file = graph[krate].root_file_id;
89             let source_root_id = db.file_source_root(root_file);
90             let source_root = db.source_root(source_root_id);
91             entries.extend(source_root.iter().map(|id| (id, None)));
92         }
93         SearchScope { entries }
94     }
95
96     fn reverse_dependencies(db: &RootDatabase, of: hir::Crate) -> SearchScope {
97         let mut entries = FxHashMap::default();
98         for rev_dep in of.transitive_reverse_dependencies(db) {
99             let root_file = rev_dep.root_file(db);
100             let source_root_id = db.file_source_root(root_file);
101             let source_root = db.source_root(source_root_id);
102             entries.extend(source_root.iter().map(|id| (id, None)));
103         }
104         SearchScope { entries }
105     }
106
107     fn krate(db: &RootDatabase, of: hir::Crate) -> SearchScope {
108         let root_file = of.root_file(db);
109         let source_root_id = db.file_source_root(root_file);
110         let source_root = db.source_root(source_root_id);
111         SearchScope {
112             entries: source_root.iter().map(|id| (id, None)).collect::<FxHashMap<_, _>>(),
113         }
114     }
115
116     fn module(db: &RootDatabase, module: hir::Module) -> SearchScope {
117         let mut entries = FxHashMap::default();
118
119         let mut to_visit = vec![module];
120         let mut is_first = true;
121         while let Some(module) = to_visit.pop() {
122             let src = module.definition_source(db);
123             let file_id = src.file_id.original_file(db);
124             match src.value {
125                 ModuleSource::Module(m) => {
126                     if is_first {
127                         let range = Some(m.syntax().text_range());
128                         entries.insert(file_id, range);
129                     } else {
130                         // We have already added the enclosing file to the search scope,
131                         // so do nothing.
132                     }
133                 }
134                 ModuleSource::BlockExpr(b) => {
135                     if is_first {
136                         let range = Some(b.syntax().text_range());
137                         entries.insert(file_id, range);
138                     } else {
139                         // We have already added the enclosing file to the search scope,
140                         // so do nothing.
141                     }
142                 }
143                 ModuleSource::SourceFile(_) => {
144                     entries.insert(file_id, None);
145                 }
146             };
147             is_first = false;
148             to_visit.extend(module.children(db));
149         }
150         SearchScope { entries }
151     }
152
153     pub fn empty() -> SearchScope {
154         SearchScope::new(FxHashMap::default())
155     }
156
157     pub fn single_file(file: FileId) -> SearchScope {
158         SearchScope::new(std::iter::once((file, None)).collect())
159     }
160
161     pub fn file_range(range: FileRange) -> SearchScope {
162         SearchScope::new(std::iter::once((range.file_id, Some(range.range))).collect())
163     }
164
165     pub fn files(files: &[FileId]) -> SearchScope {
166         SearchScope::new(files.iter().map(|f| (*f, None)).collect())
167     }
168
169     pub fn intersection(&self, other: &SearchScope) -> SearchScope {
170         let (mut small, mut large) = (&self.entries, &other.entries);
171         if small.len() > large.len() {
172             mem::swap(&mut small, &mut large)
173         }
174
175         let res = small
176             .iter()
177             .filter_map(|(file_id, r1)| {
178                 let r2 = large.get(file_id)?;
179                 let r = intersect_ranges(*r1, *r2)?;
180                 Some((*file_id, r))
181             })
182             .collect();
183
184         return SearchScope::new(res);
185
186         fn intersect_ranges(
187             r1: Option<TextRange>,
188             r2: Option<TextRange>,
189         ) -> Option<Option<TextRange>> {
190             match (r1, r2) {
191                 (None, r) | (r, None) => Some(r),
192                 (Some(r1), Some(r2)) => {
193                     let r = r1.intersect(r2)?;
194                     Some(Some(r))
195                 }
196             }
197         }
198     }
199 }
200
201 impl IntoIterator for SearchScope {
202     type Item = (FileId, Option<TextRange>);
203     type IntoIter = std::collections::hash_map::IntoIter<FileId, Option<TextRange>>;
204
205     fn into_iter(self) -> Self::IntoIter {
206         self.entries.into_iter()
207     }
208 }
209
210 impl Definition {
211     fn search_scope(&self, db: &RootDatabase) -> SearchScope {
212         let _p = profile::span("search_scope");
213
214         if let Definition::ModuleDef(hir::ModuleDef::BuiltinType(_)) = self {
215             return SearchScope::crate_graph(db);
216         }
217
218         let module = match self.module(db) {
219             Some(it) => it,
220             None => return SearchScope::empty(),
221         };
222         let InFile { file_id, value: module_source } = module.definition_source(db);
223         let file_id = file_id.original_file(db);
224
225         if let Definition::Local(var) = self {
226             let range = match var.parent(db) {
227                 DefWithBody::Function(f) => f.source(db).map(|src| src.value.syntax().text_range()),
228                 DefWithBody::Const(c) => c.source(db).map(|src| src.value.syntax().text_range()),
229                 DefWithBody::Static(s) => s.source(db).map(|src| src.value.syntax().text_range()),
230             };
231             return match range {
232                 Some(range) => SearchScope::file_range(FileRange { file_id, range }),
233                 None => SearchScope::single_file(file_id),
234             };
235         }
236
237         if let Definition::SelfType(impl_) = self {
238             return match impl_.source(db).map(|src| src.value.syntax().text_range()) {
239                 Some(range) => SearchScope::file_range(FileRange { file_id, range }),
240                 None => SearchScope::single_file(file_id),
241             };
242         }
243
244         if let Definition::GenericParam(hir::GenericParam::LifetimeParam(param)) = self {
245             let range = match param.parent(db) {
246                 hir::GenericDef::Function(it) => {
247                     it.source(db).map(|src| src.value.syntax().text_range())
248                 }
249                 hir::GenericDef::Adt(it) => match it {
250                     hir::Adt::Struct(it) => {
251                         it.source(db).map(|src| src.value.syntax().text_range())
252                     }
253                     hir::Adt::Union(it) => it.source(db).map(|src| src.value.syntax().text_range()),
254                     hir::Adt::Enum(it) => it.source(db).map(|src| src.value.syntax().text_range()),
255                 },
256                 hir::GenericDef::Trait(it) => {
257                     it.source(db).map(|src| src.value.syntax().text_range())
258                 }
259                 hir::GenericDef::TypeAlias(it) => {
260                     it.source(db).map(|src| src.value.syntax().text_range())
261                 }
262                 hir::GenericDef::Impl(it) => {
263                     it.source(db).map(|src| src.value.syntax().text_range())
264                 }
265                 hir::GenericDef::Variant(it) => {
266                     it.source(db).map(|src| src.value.syntax().text_range())
267                 }
268                 hir::GenericDef::Const(it) => {
269                     it.source(db).map(|src| src.value.syntax().text_range())
270                 }
271             };
272             return match range {
273                 Some(range) => SearchScope::file_range(FileRange { file_id, range }),
274                 None => SearchScope::single_file(file_id),
275             };
276         }
277
278         if let Definition::Macro(macro_def) = self {
279             if macro_def.kind() == hir::MacroKind::Declarative {
280                 return if macro_def.attrs(db).by_key("macro_export").exists() {
281                     SearchScope::reverse_dependencies(db, module.krate())
282                 } else {
283                     SearchScope::krate(db, module.krate())
284                 };
285             }
286         }
287
288         let vis = self.visibility(db);
289         if let Some(Visibility::Public) = vis {
290             return SearchScope::reverse_dependencies(db, module.krate());
291         }
292         if let Some(Visibility::Module(module)) = vis {
293             return SearchScope::module(db, module.into());
294         }
295
296         let range = match module_source {
297             ModuleSource::Module(m) => Some(m.syntax().text_range()),
298             ModuleSource::BlockExpr(b) => Some(b.syntax().text_range()),
299             ModuleSource::SourceFile(_) => None,
300         };
301         match range {
302             Some(range) => SearchScope::file_range(FileRange { file_id, range }),
303             None => SearchScope::single_file(file_id),
304         }
305     }
306
307     pub fn usages<'a>(self, sema: &'a Semantics<RootDatabase>) -> FindUsages<'a> {
308         FindUsages {
309             def: self,
310             sema,
311             scope: None,
312             include_self_kw_refs: None,
313             search_self_mod: false,
314         }
315     }
316 }
317
318 pub struct FindUsages<'a> {
319     def: Definition,
320     sema: &'a Semantics<'a, RootDatabase>,
321     scope: Option<SearchScope>,
322     include_self_kw_refs: Option<hir::Type>,
323     search_self_mod: bool,
324 }
325
326 impl<'a> FindUsages<'a> {
327     /// Enable searching for `Self` when the definition is a type or `self` for modules.
328     pub fn include_self_refs(mut self) -> FindUsages<'a> {
329         self.include_self_kw_refs = def_to_ty(self.sema, &self.def);
330         self.search_self_mod = true;
331         self
332     }
333
334     pub fn in_scope(self, scope: SearchScope) -> FindUsages<'a> {
335         self.set_scope(Some(scope))
336     }
337
338     pub fn set_scope(mut self, scope: Option<SearchScope>) -> FindUsages<'a> {
339         assert!(self.scope.is_none());
340         self.scope = scope;
341         self
342     }
343
344     pub fn at_least_one(self) -> bool {
345         let mut found = false;
346         self.search(&mut |_, _| {
347             found = true;
348             true
349         });
350         found
351     }
352
353     pub fn all(self) -> UsageSearchResult {
354         let mut res = UsageSearchResult::default();
355         self.search(&mut |file_id, reference| {
356             res.references.entry(file_id).or_default().push(reference);
357             false
358         });
359         res
360     }
361
362     fn search(self, sink: &mut dyn FnMut(FileId, FileReference) -> bool) {
363         let _p = profile::span("FindUsages:search");
364         let sema = self.sema;
365
366         let search_scope = {
367             let base = self.def.search_scope(sema.db);
368             match &self.scope {
369                 None => base,
370                 Some(scope) => base.intersection(scope),
371             }
372         };
373
374         let name = self.def.name(sema.db).or_else(|| {
375             self.include_self_kw_refs.as_ref().and_then(|ty| {
376                 ty.as_adt()
377                     .map(|adt| adt.name(self.sema.db))
378                     .or_else(|| ty.as_builtin().map(|builtin| builtin.name()))
379             })
380         });
381         let name = match name {
382             Some(name) => name.to_string(),
383             None => return,
384         };
385         let name = name.as_str();
386
387         for (file_id, search_range) in search_scope {
388             let text = sema.db.file_text(file_id);
389             let search_range =
390                 search_range.unwrap_or_else(|| TextRange::up_to(TextSize::of(text.as_str())));
391
392             let tree = Lazy::new(|| sema.parse(file_id).syntax().clone());
393
394             for (idx, _) in text.match_indices(name) {
395                 let offset: TextSize = idx.try_into().unwrap();
396                 if !search_range.contains_inclusive(offset) {
397                     continue;
398                 }
399
400                 if let Some(name) = sema.find_node_at_offset_with_descend(&tree, offset) {
401                     if match name {
402                         ast::NameLike::NameRef(name_ref) => self.found_name_ref(&name_ref, sink),
403                         ast::NameLike::Name(name) => self.found_name(&name, sink),
404                         ast::NameLike::Lifetime(lifetime) => self.found_lifetime(&lifetime, sink),
405                     } {
406                         return;
407                     }
408                 }
409             }
410             if let Some(self_ty) = &self.include_self_kw_refs {
411                 for (idx, _) in text.match_indices("Self") {
412                     let offset: TextSize = idx.try_into().unwrap();
413                     if !search_range.contains_inclusive(offset) {
414                         continue;
415                     }
416
417                     if let Some(ast::NameLike::NameRef(name_ref)) =
418                         sema.find_node_at_offset_with_descend(&tree, offset)
419                     {
420                         if self.found_self_ty_name_ref(self_ty, &name_ref, sink) {
421                             return;
422                         }
423                     }
424                 }
425             }
426         }
427
428         // search for module `self` references in our module's definition source
429         match self.def {
430             Definition::ModuleDef(hir::ModuleDef::Module(module)) if self.search_self_mod => {
431                 let src = module.definition_source(sema.db);
432                 let file_id = src.file_id.original_file(sema.db);
433                 let (file_id, search_range) = match src.value {
434                     ModuleSource::Module(m) => (file_id, Some(m.syntax().text_range())),
435                     ModuleSource::BlockExpr(b) => (file_id, Some(b.syntax().text_range())),
436                     ModuleSource::SourceFile(_) => (file_id, None),
437                 };
438
439                 let text = sema.db.file_text(file_id);
440                 let search_range =
441                     search_range.unwrap_or_else(|| TextRange::up_to(TextSize::of(text.as_str())));
442
443                 let tree = Lazy::new(|| sema.parse(file_id).syntax().clone());
444
445                 for (idx, _) in text.match_indices("self") {
446                     let offset: TextSize = idx.try_into().unwrap();
447                     if !search_range.contains_inclusive(offset) {
448                         continue;
449                     }
450
451                     if let Some(ast::NameLike::NameRef(name_ref)) =
452                         sema.find_node_at_offset_with_descend(&tree, offset)
453                     {
454                         if self.found_self_module_name_ref(&name_ref, sink) {
455                             return;
456                         }
457                     }
458                 }
459             }
460             _ => {}
461         }
462     }
463
464     fn found_self_ty_name_ref(
465         &self,
466         self_ty: &hir::Type,
467         name_ref: &ast::NameRef,
468         sink: &mut dyn FnMut(FileId, FileReference) -> bool,
469     ) -> bool {
470         match NameRefClass::classify(self.sema, name_ref) {
471             Some(NameRefClass::Definition(Definition::SelfType(impl_)))
472                 if impl_.self_ty(self.sema.db) == *self_ty =>
473             {
474                 let FileRange { file_id, range } = self.sema.original_range(name_ref.syntax());
475                 let reference = FileReference {
476                     range,
477                     name: ast::NameLike::NameRef(name_ref.clone()),
478                     access: None,
479                 };
480                 sink(file_id, reference)
481             }
482             _ => false,
483         }
484     }
485
486     fn found_self_module_name_ref(
487         &self,
488         name_ref: &ast::NameRef,
489         sink: &mut dyn FnMut(FileId, FileReference) -> bool,
490     ) -> bool {
491         match NameRefClass::classify(self.sema, name_ref) {
492             Some(NameRefClass::Definition(def @ Definition::ModuleDef(_))) if def == self.def => {
493                 let FileRange { file_id, range } = self.sema.original_range(name_ref.syntax());
494                 let reference = FileReference {
495                     range,
496                     name: ast::NameLike::NameRef(name_ref.clone()),
497                     access: None,
498                 };
499                 sink(file_id, reference)
500             }
501             _ => false,
502         }
503     }
504
505     fn found_lifetime(
506         &self,
507         lifetime: &ast::Lifetime,
508         sink: &mut dyn FnMut(FileId, FileReference) -> bool,
509     ) -> bool {
510         match NameRefClass::classify_lifetime(self.sema, lifetime) {
511             Some(NameRefClass::Definition(def)) if def == self.def => {
512                 let FileRange { file_id, range } = self.sema.original_range(lifetime.syntax());
513                 let reference = FileReference {
514                     range,
515                     name: ast::NameLike::Lifetime(lifetime.clone()),
516                     access: None,
517                 };
518                 sink(file_id, reference)
519             }
520             _ => false,
521         }
522     }
523
524     fn found_name_ref(
525         &self,
526         name_ref: &ast::NameRef,
527         sink: &mut dyn FnMut(FileId, FileReference) -> bool,
528     ) -> bool {
529         match NameRefClass::classify(self.sema, name_ref) {
530             Some(NameRefClass::Definition(def)) if def == self.def => {
531                 let FileRange { file_id, range } = self.sema.original_range(name_ref.syntax());
532                 let reference = FileReference {
533                     range,
534                     name: ast::NameLike::NameRef(name_ref.clone()),
535                     access: reference_access(&def, name_ref),
536                 };
537                 sink(file_id, reference)
538             }
539             Some(NameRefClass::Definition(def)) if self.include_self_kw_refs.is_some() => {
540                 if self.include_self_kw_refs == def_to_ty(self.sema, &def) {
541                     let FileRange { file_id, range } = self.sema.original_range(name_ref.syntax());
542                     let reference = FileReference {
543                         range,
544                         name: ast::NameLike::NameRef(name_ref.clone()),
545                         access: reference_access(&def, name_ref),
546                     };
547                     sink(file_id, reference)
548                 } else {
549                     false
550                 }
551             }
552             Some(NameRefClass::FieldShorthand { local_ref: local, field_ref: field }) => {
553                 let FileRange { file_id, range } = self.sema.original_range(name_ref.syntax());
554                 let access = match self.def {
555                     Definition::Field(_) if field == self.def => reference_access(&field, name_ref),
556                     Definition::Local(l) if local == l => {
557                         reference_access(&Definition::Local(local), name_ref)
558                     }
559                     _ => return false,
560                 };
561                 let reference =
562                     FileReference { range, name: ast::NameLike::NameRef(name_ref.clone()), access };
563                 sink(file_id, reference)
564             }
565             _ => false,
566         }
567     }
568
569     fn found_name(
570         &self,
571         name: &ast::Name,
572         sink: &mut dyn FnMut(FileId, FileReference) -> bool,
573     ) -> bool {
574         match NameClass::classify(self.sema, name) {
575             Some(NameClass::PatFieldShorthand { local_def: _, field_ref })
576                 if matches!(
577                     self.def, Definition::Field(_) if field_ref == self.def
578                 ) =>
579             {
580                 let FileRange { file_id, range } = self.sema.original_range(name.syntax());
581                 let reference = FileReference {
582                     range,
583                     name: ast::NameLike::Name(name.clone()),
584                     // FIXME: mutable patterns should have `Write` access
585                     access: Some(ReferenceAccess::Read),
586                 };
587                 sink(file_id, reference)
588             }
589             Some(NameClass::ConstReference(def)) if self.def == def => {
590                 let FileRange { file_id, range } = self.sema.original_range(name.syntax());
591                 let reference =
592                     FileReference { range, name: ast::NameLike::Name(name.clone()), access: None };
593                 sink(file_id, reference)
594             }
595             // Resolve trait impl function definitions to the trait definition's version if self.def is the trait definition's
596             Some(NameClass::Definition(Definition::ModuleDef(mod_def))) => {
597                 /* poor man's try block */
598                 (|| {
599                     let this = match self.def {
600                         Definition::ModuleDef(this) if this != mod_def => this,
601                         _ => return None,
602                     };
603                     let this_trait = this
604                         .as_assoc_item(self.sema.db)?
605                         .containing_trait_or_trait_impl(self.sema.db)?;
606                     let trait_ = mod_def
607                         .as_assoc_item(self.sema.db)?
608                         .containing_trait_or_trait_impl(self.sema.db)?;
609                     (trait_ == this_trait
610                         && self.def.name(self.sema.db) == mod_def.name(self.sema.db))
611                     .then(|| {
612                         let FileRange { file_id, range } = self.sema.original_range(name.syntax());
613                         let reference = FileReference {
614                             range,
615                             name: ast::NameLike::Name(name.clone()),
616                             access: None,
617                         };
618                         sink(file_id, reference)
619                     })
620                 })()
621                 .unwrap_or(false)
622             }
623             _ => false,
624         }
625     }
626 }
627
628 fn def_to_ty(sema: &Semantics<RootDatabase>, def: &Definition) -> Option<hir::Type> {
629     match def {
630         Definition::ModuleDef(def) => match def {
631             ModuleDef::Adt(adt) => Some(adt.ty(sema.db)),
632             ModuleDef::TypeAlias(it) => Some(it.ty(sema.db)),
633             ModuleDef::BuiltinType(it) => {
634                 let graph = sema.db.crate_graph();
635                 let krate = graph.iter().next()?;
636                 let root_file = graph[krate].root_file_id;
637                 let module = sema.to_module_def(root_file)?;
638                 Some(it.ty(sema.db, module))
639             }
640             _ => None,
641         },
642         Definition::SelfType(it) => Some(it.self_ty(sema.db)),
643         _ => None,
644     }
645 }
646
647 fn reference_access(def: &Definition, name_ref: &ast::NameRef) -> Option<ReferenceAccess> {
648     // Only Locals and Fields have accesses for now.
649     if !matches!(def, Definition::Local(_) | Definition::Field(_)) {
650         return None;
651     }
652
653     let mode = name_ref.syntax().ancestors().find_map(|node| {
654         match_ast! {
655             match (node) {
656                 ast::BinExpr(expr) => {
657                     if expr.op_kind()?.is_assignment() {
658                         // If the variable or field ends on the LHS's end then it's a Write (covers fields and locals).
659                         // FIXME: This is not terribly accurate.
660                         if let Some(lhs) = expr.lhs() {
661                             if lhs.syntax().text_range().end() == name_ref.syntax().text_range().end() {
662                                 return Some(ReferenceAccess::Write);
663                             }
664                         }
665                     }
666                     Some(ReferenceAccess::Read)
667                 },
668                 _ => None
669             }
670         }
671     });
672
673     // Default Locals and Fields to read
674     mode.or(Some(ReferenceAccess::Read))
675 }