1 //! Implementation of find-usages functionality.
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
7 use std::{mem, sync::Arc};
9 use base_db::{FileId, FileRange, SourceDatabase, SourceDatabaseExt};
10 use hir::{DefWithBody, HasAttrs, HasSource, InFile, ModuleSource, Semantics, Visibility};
11 use once_cell::unsync::Lazy;
12 use rustc_hash::FxHashMap;
13 use syntax::{ast, match_ast, AstNode, TextRange, TextSize};
16 defs::{Definition, NameClass, NameRefClass},
17 traits::{as_trait_assoc_def, convert_to_def_in_trait},
21 #[derive(Debug, Default, Clone)]
22 pub struct UsageSearchResult {
23 pub references: FxHashMap<FileId, Vec<FileReference>>,
26 impl UsageSearchResult {
27 pub fn is_empty(&self) -> bool {
28 self.references.is_empty()
31 pub fn len(&self) -> usize {
35 pub fn iter(&self) -> impl Iterator<Item = (&FileId, &[FileReference])> + '_ {
36 self.references.iter().map(|(file_id, refs)| (file_id, &**refs))
39 pub fn file_ranges(&self) -> impl Iterator<Item = FileRange> + '_ {
40 self.references.iter().flat_map(|(&file_id, refs)| {
41 refs.iter().map(move |&FileReference { range, .. }| FileRange { file_id, range })
46 impl IntoIterator for UsageSearchResult {
47 type Item = (FileId, Vec<FileReference>);
48 type IntoIter = <FxHashMap<FileId, Vec<FileReference>> as IntoIterator>::IntoIter;
50 fn into_iter(self) -> Self::IntoIter {
51 self.references.into_iter()
55 #[derive(Debug, Clone)]
56 pub struct FileReference {
57 /// The range of the reference in the original file
59 /// The node of the reference in the (macro-)file
60 pub name: ast::NameLike,
61 pub category: Option<ReferenceCategory>,
64 #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
65 pub enum ReferenceCategory {
66 // FIXME: Add this variant and delete the `retain_adt_literal_usages` function.
70 // FIXME: Some day should be able to search in doc comments. Would probably
71 // need to switch from enum to bitflags then?
75 /// Generally, `search_scope` returns files that might contain references for the element.
76 /// For `pub(crate)` things it's a crate, for `pub` things it's a crate and dependant crates.
77 /// In some cases, the location of the references is known to within a `TextRange`,
78 /// e.g. for things like local variables.
79 #[derive(Clone, Debug)]
80 pub struct SearchScope {
81 entries: FxHashMap<FileId, Option<TextRange>>,
85 fn new(entries: FxHashMap<FileId, Option<TextRange>>) -> SearchScope {
86 SearchScope { entries }
89 /// Build a search scope spanning the entire crate graph of files.
90 fn crate_graph(db: &RootDatabase) -> SearchScope {
91 let mut entries = FxHashMap::default();
93 let graph = db.crate_graph();
94 for krate in graph.iter() {
95 let root_file = graph[krate].root_file_id;
96 let source_root_id = db.file_source_root(root_file);
97 let source_root = db.source_root(source_root_id);
98 entries.extend(source_root.iter().map(|id| (id, None)));
100 SearchScope { entries }
103 /// Build a search scope spanning all the reverse dependencies of the given crate.
104 fn reverse_dependencies(db: &RootDatabase, of: hir::Crate) -> SearchScope {
105 let mut entries = FxHashMap::default();
106 for rev_dep in of.transitive_reverse_dependencies(db) {
107 let root_file = rev_dep.root_file(db);
108 let source_root_id = db.file_source_root(root_file);
109 let source_root = db.source_root(source_root_id);
110 entries.extend(source_root.iter().map(|id| (id, None)));
112 SearchScope { entries }
115 /// Build a search scope spanning the given crate.
116 fn krate(db: &RootDatabase, of: hir::Crate) -> SearchScope {
117 let root_file = of.root_file(db);
118 let source_root_id = db.file_source_root(root_file);
119 let source_root = db.source_root(source_root_id);
121 entries: source_root.iter().map(|id| (id, None)).collect::<FxHashMap<_, _>>(),
125 /// Build a search scope spanning the given module and all its submodules.
126 fn module_and_children(db: &RootDatabase, module: hir::Module) -> SearchScope {
127 let mut entries = FxHashMap::default();
129 let (file_id, range) = {
130 let InFile { file_id, value } = module.definition_source(db);
131 if let Some((file_id, call_source)) = file_id.original_call_node(db) {
132 (file_id, Some(call_source.text_range()))
135 file_id.original_file(db),
137 ModuleSource::SourceFile(_) => None,
138 ModuleSource::Module(it) => Some(it.syntax().text_range()),
139 ModuleSource::BlockExpr(it) => Some(it.syntax().text_range()),
144 entries.insert(file_id, range);
146 let mut to_visit: Vec<_> = module.children(db).collect();
147 while let Some(module) = to_visit.pop() {
148 if let InFile { file_id, value: ModuleSource::SourceFile(_) } =
149 module.definition_source(db)
151 entries.insert(file_id.original_file(db), None);
153 to_visit.extend(module.children(db));
155 SearchScope { entries }
158 /// Build an empty search scope.
159 pub fn empty() -> SearchScope {
160 SearchScope::new(FxHashMap::default())
163 /// Build a empty search scope spanning the given file.
164 pub fn single_file(file: FileId) -> SearchScope {
165 SearchScope::new(std::iter::once((file, None)).collect())
168 /// Build a empty search scope spanning the text range of the given file.
169 pub fn file_range(range: FileRange) -> SearchScope {
170 SearchScope::new(std::iter::once((range.file_id, Some(range.range))).collect())
173 /// Build a empty search scope spanning the given files.
174 pub fn files(files: &[FileId]) -> SearchScope {
175 SearchScope::new(files.iter().map(|f| (*f, None)).collect())
178 pub fn intersection(&self, other: &SearchScope) -> SearchScope {
179 let (mut small, mut large) = (&self.entries, &other.entries);
180 if small.len() > large.len() {
181 mem::swap(&mut small, &mut large)
184 let intersect_ranges =
185 |r1: Option<TextRange>, r2: Option<TextRange>| -> Option<Option<TextRange>> {
187 (None, r) | (r, None) => Some(r),
188 (Some(r1), Some(r2)) => r1.intersect(r2).map(Some),
193 .filter_map(|(&file_id, &r1)| {
194 let &r2 = large.get(&file_id)?;
195 let r = intersect_ranges(r1, r2)?;
200 SearchScope::new(res)
204 impl IntoIterator for SearchScope {
205 type Item = (FileId, Option<TextRange>);
206 type IntoIter = std::collections::hash_map::IntoIter<FileId, Option<TextRange>>;
208 fn into_iter(self) -> Self::IntoIter {
209 self.entries.into_iter()
214 fn search_scope(&self, db: &RootDatabase) -> SearchScope {
215 let _p = profile::span("search_scope");
217 if let Definition::BuiltinType(_) = self {
218 return SearchScope::crate_graph(db);
222 // FIXME: We don't do searches for crates currently, as a crate does not actually have a single name
223 if let &Definition::Module(module) = self {
224 if module.is_crate_root(db) {
225 return SearchScope::reverse_dependencies(db, module.krate());
229 let module = match self.module(db) {
231 None => return SearchScope::empty(),
233 let InFile { file_id, value: module_source } = module.definition_source(db);
234 let file_id = file_id.original_file(db);
236 if let Definition::Local(var) = self {
237 let def = match var.parent(db) {
238 DefWithBody::Function(f) => f.source(db).map(|src| src.syntax().cloned()),
239 DefWithBody::Const(c) => c.source(db).map(|src| src.syntax().cloned()),
240 DefWithBody::Static(s) => s.source(db).map(|src| src.syntax().cloned()),
243 Some(def) => SearchScope::file_range(def.as_ref().original_file_range(db)),
244 None => SearchScope::single_file(file_id),
248 if let Definition::SelfType(impl_) = self {
249 return match impl_.source(db).map(|src| src.syntax().cloned()) {
250 Some(def) => SearchScope::file_range(def.as_ref().original_file_range(db)),
251 None => SearchScope::single_file(file_id),
255 if let Definition::GenericParam(hir::GenericParam::LifetimeParam(param)) = self {
256 let def = match param.parent(db) {
257 hir::GenericDef::Function(it) => it.source(db).map(|src| src.syntax().cloned()),
258 hir::GenericDef::Adt(it) => it.source(db).map(|src| src.syntax().cloned()),
259 hir::GenericDef::Trait(it) => it.source(db).map(|src| src.syntax().cloned()),
260 hir::GenericDef::TypeAlias(it) => it.source(db).map(|src| src.syntax().cloned()),
261 hir::GenericDef::Impl(it) => it.source(db).map(|src| src.syntax().cloned()),
262 hir::GenericDef::Variant(it) => it.source(db).map(|src| src.syntax().cloned()),
263 hir::GenericDef::Const(it) => it.source(db).map(|src| src.syntax().cloned()),
266 Some(def) => SearchScope::file_range(def.as_ref().original_file_range(db)),
267 None => SearchScope::single_file(file_id),
271 if let Definition::Macro(macro_def) = self {
272 return match macro_def.kind(db) {
273 hir::MacroKind::Declarative => {
274 if macro_def.attrs(db).by_key("macro_export").exists() {
275 SearchScope::reverse_dependencies(db, module.krate())
277 SearchScope::krate(db, module.krate())
280 hir::MacroKind::BuiltIn => SearchScope::crate_graph(db),
281 hir::MacroKind::Derive | hir::MacroKind::Attr | hir::MacroKind::ProcMacro => {
282 SearchScope::reverse_dependencies(db, module.krate())
287 if let Definition::DeriveHelper(_) = self {
288 return SearchScope::reverse_dependencies(db, module.krate());
291 let vis = self.visibility(db);
292 if let Some(Visibility::Public) = vis {
293 return SearchScope::reverse_dependencies(db, module.krate());
295 if let Some(Visibility::Module(module)) = vis {
296 return SearchScope::module_and_children(db, module.into());
299 let range = match module_source {
300 ModuleSource::Module(m) => Some(m.syntax().text_range()),
301 ModuleSource::BlockExpr(b) => Some(b.syntax().text_range()),
302 ModuleSource::SourceFile(_) => None,
305 Some(range) => SearchScope::file_range(FileRange { file_id, range }),
306 None => SearchScope::single_file(file_id),
310 pub fn usages<'a>(self, sema: &'a Semantics<'_, RootDatabase>) -> FindUsages<'a> {
312 local_repr: match self {
313 Definition::Local(local) => Some(local.representative(sema.db)),
317 trait_assoc_def: as_trait_assoc_def(sema.db, self),
320 include_self_kw_refs: None,
321 search_self_mod: false,
327 pub struct FindUsages<'a> {
329 /// If def is an assoc item from a trait or trait impl, this is the corresponding item of the trait definition
330 trait_assoc_def: Option<Definition>,
331 sema: &'a Semantics<'a, RootDatabase>,
332 scope: Option<SearchScope>,
333 include_self_kw_refs: Option<hir::Type>,
334 local_repr: Option<hir::Local>,
335 search_self_mod: bool,
338 impl<'a> FindUsages<'a> {
339 /// Enable searching for `Self` when the definition is a type or `self` for modules.
340 pub fn include_self_refs(mut self) -> FindUsages<'a> {
341 self.include_self_kw_refs = def_to_ty(self.sema, &self.def);
342 self.search_self_mod = true;
346 /// Limit the search to a given [`SearchScope`].
347 pub fn in_scope(self, scope: SearchScope) -> FindUsages<'a> {
348 self.set_scope(Some(scope))
351 /// Limit the search to a given [`SearchScope`].
352 pub fn set_scope(mut self, scope: Option<SearchScope>) -> FindUsages<'a> {
353 assert!(self.scope.is_none());
358 pub fn at_least_one(&self) -> bool {
359 let mut found = false;
360 self.search(&mut |_, _| {
367 pub fn all(self) -> UsageSearchResult {
368 let mut res = UsageSearchResult::default();
369 self.search(&mut |file_id, reference| {
370 res.references.entry(file_id).or_default().push(reference);
376 fn search(&self, sink: &mut dyn FnMut(FileId, FileReference) -> bool) {
377 let _p = profile::span("FindUsages:search");
378 let sema = self.sema;
381 let base = self.trait_assoc_def.unwrap_or(self.def).search_scope(sema.db);
384 Some(scope) => base.intersection(scope),
388 let name = match self.def {
389 // special case crate modules as these do not have a proper name
390 Definition::Module(module) if module.is_crate_root(self.sema.db) => {
391 // FIXME: This assumes the crate name is always equal to its display name when it really isn't
394 .display_name(self.sema.db)
395 .map(|crate_name| crate_name.crate_name().as_smol_str().clone())
398 let self_kw_refs = || {
399 self.include_self_kw_refs.as_ref().and_then(|ty| {
401 .map(|adt| adt.name(self.sema.db))
402 .or_else(|| ty.as_builtin().map(|builtin| builtin.name()))
405 // We need to unescape the name in case it is written without "r#" in earlier
406 // editions of Rust where it isn't a keyword.
407 self.def.name(sema.db).or_else(self_kw_refs).map(|it| it.unescaped().to_smol_str())
410 let name = match &name {
411 Some(s) => s.as_str(),
415 // these can't be closures because rust infers the lifetimes wrong ...
416 fn match_indices<'a>(
419 search_range: TextRange,
420 ) -> impl Iterator<Item = TextSize> + 'a {
421 text.match_indices(name).filter_map(move |(idx, _)| {
422 let offset: TextSize = idx.try_into().unwrap();
423 if !search_range.contains_inclusive(offset) {
431 sema: &'a Semantics<'_, RootDatabase>,
432 scope: &'a SearchScope,
433 ) -> impl Iterator<Item = (Arc<String>, FileId, TextRange)> + 'a {
434 scope.entries.iter().map(|(&file_id, &search_range)| {
435 let text = sema.db.file_text(file_id);
437 search_range.unwrap_or_else(|| TextRange::up_to(TextSize::of(text.as_str())));
439 (text, file_id, search_range)
443 // FIXME: There should be optimization potential here
444 // Currently we try to descend everything we find which
445 // means we call `Semantics::descend_into_macros` on
446 // every textual hit. That function is notoriously
447 // expensive even for things that do not get down mapped
449 for (text, file_id, search_range) in scope_files(sema, &search_scope) {
450 let tree = Lazy::new(move || sema.parse(file_id).syntax().clone());
452 // Search for occurrences of the items name
453 for offset in match_indices(&text, name, search_range) {
454 for name in sema.find_nodes_at_offset_with_descend(&tree, offset) {
456 ast::NameLike::NameRef(name_ref) => self.found_name_ref(&name_ref, sink),
457 ast::NameLike::Name(name) => self.found_name(&name, sink),
458 ast::NameLike::Lifetime(lifetime) => self.found_lifetime(&lifetime, sink),
464 // Search for occurrences of the `Self` referring to our type
465 if let Some(self_ty) = &self.include_self_kw_refs {
466 for offset in match_indices(&text, "Self", search_range) {
467 for name_ref in sema.find_nodes_at_offset_with_descend(&tree, offset) {
468 if self.found_self_ty_name_ref(self_ty, &name_ref, sink) {
476 // Search for `super` and `crate` resolving to our module
478 Definition::Module(module) => {
479 let scope = search_scope
480 .intersection(&SearchScope::module_and_children(self.sema.db, module));
482 let is_crate_root = module.is_crate_root(self.sema.db);
484 for (text, file_id, search_range) in scope_files(sema, &scope) {
485 let tree = Lazy::new(move || sema.parse(file_id).syntax().clone());
487 for offset in match_indices(&text, "super", search_range) {
488 for name_ref in sema.find_nodes_at_offset_with_descend(&tree, offset) {
489 if self.found_name_ref(&name_ref, sink) {
495 for offset in match_indices(&text, "crate", search_range) {
496 for name_ref in sema.find_nodes_at_offset_with_descend(&tree, offset) {
497 if self.found_name_ref(&name_ref, sink) {
508 // search for module `self` references in our module's definition source
510 Definition::Module(module) if self.search_self_mod => {
511 let src = module.definition_source(sema.db);
512 let file_id = src.file_id.original_file(sema.db);
513 let (file_id, search_range) = match src.value {
514 ModuleSource::Module(m) => (file_id, Some(m.syntax().text_range())),
515 ModuleSource::BlockExpr(b) => (file_id, Some(b.syntax().text_range())),
516 ModuleSource::SourceFile(_) => (file_id, None),
519 let search_range = if let Some(&range) = search_scope.entries.get(&file_id) {
520 match (range, search_range) {
521 (None, range) | (range, None) => range,
522 (Some(range), Some(search_range)) => match range.intersect(search_range) {
523 Some(range) => Some(range),
531 let text = sema.db.file_text(file_id);
533 search_range.unwrap_or_else(|| TextRange::up_to(TextSize::of(text.as_str())));
535 let tree = Lazy::new(|| sema.parse(file_id).syntax().clone());
537 for offset in match_indices(&text, "self", search_range) {
538 for name_ref in sema.find_nodes_at_offset_with_descend(&tree, offset) {
539 if self.found_self_module_name_ref(&name_ref, sink) {
549 fn found_self_ty_name_ref(
552 name_ref: &ast::NameRef,
553 sink: &mut dyn FnMut(FileId, FileReference) -> bool,
555 match NameRefClass::classify(self.sema, name_ref) {
556 Some(NameRefClass::Definition(Definition::SelfType(impl_)))
557 if impl_.self_ty(self.sema.db) == *self_ty =>
559 let FileRange { file_id, range } = self.sema.original_range(name_ref.syntax());
560 let reference = FileReference {
562 name: ast::NameLike::NameRef(name_ref.clone()),
565 sink(file_id, reference)
571 fn found_self_module_name_ref(
573 name_ref: &ast::NameRef,
574 sink: &mut dyn FnMut(FileId, FileReference) -> bool,
576 match NameRefClass::classify(self.sema, name_ref) {
577 Some(NameRefClass::Definition(def @ Definition::Module(_))) if def == self.def => {
578 let FileRange { file_id, range } = self.sema.original_range(name_ref.syntax());
579 let reference = FileReference {
581 name: ast::NameLike::NameRef(name_ref.clone()),
584 sink(file_id, reference)
592 lifetime: &ast::Lifetime,
593 sink: &mut dyn FnMut(FileId, FileReference) -> bool,
595 match NameRefClass::classify_lifetime(self.sema, lifetime) {
596 Some(NameRefClass::Definition(def)) if def == self.def => {
597 let FileRange { file_id, range } = self.sema.original_range(lifetime.syntax());
598 let reference = FileReference {
600 name: ast::NameLike::Lifetime(lifetime.clone()),
603 sink(file_id, reference)
611 name_ref: &ast::NameRef,
612 sink: &mut dyn FnMut(FileId, FileReference) -> bool,
614 match NameRefClass::classify(self.sema, name_ref) {
615 Some(NameRefClass::Definition(def @ Definition::Local(local)))
617 self.local_repr, Some(repr) if repr == local.representative(self.sema.db)
620 let FileRange { file_id, range } = self.sema.original_range(name_ref.syntax());
621 let reference = FileReference {
623 name: ast::NameLike::NameRef(name_ref.clone()),
624 category: ReferenceCategory::new(&def, name_ref),
626 sink(file_id, reference)
628 Some(NameRefClass::Definition(def))
629 if match self.trait_assoc_def {
630 Some(trait_assoc_def) => {
631 // we have a trait assoc item, so force resolve all assoc items to their trait version
632 convert_to_def_in_trait(self.sema.db, def) == trait_assoc_def
634 None => self.def == def,
637 let FileRange { file_id, range } = self.sema.original_range(name_ref.syntax());
638 let reference = FileReference {
640 name: ast::NameLike::NameRef(name_ref.clone()),
641 category: ReferenceCategory::new(&def, name_ref),
643 sink(file_id, reference)
645 Some(NameRefClass::Definition(def)) if self.include_self_kw_refs.is_some() => {
646 if self.include_self_kw_refs == def_to_ty(self.sema, &def) {
647 let FileRange { file_id, range } = self.sema.original_range(name_ref.syntax());
648 let reference = FileReference {
650 name: ast::NameLike::NameRef(name_ref.clone()),
651 category: ReferenceCategory::new(&def, name_ref),
653 sink(file_id, reference)
658 Some(NameRefClass::FieldShorthand { local_ref: local, field_ref: field }) => {
659 let field = Definition::Field(field);
660 let FileRange { file_id, range } = self.sema.original_range(name_ref.syntax());
661 let access = match self.def {
662 Definition::Field(_) if field == self.def => {
663 ReferenceCategory::new(&field, name_ref)
665 Definition::Local(_) if matches!(self.local_repr, Some(repr) if repr == local.representative(self.sema.db)) => {
666 ReferenceCategory::new(&Definition::Local(local), name_ref)
670 let reference = FileReference {
672 name: ast::NameLike::NameRef(name_ref.clone()),
675 sink(file_id, reference)
684 sink: &mut dyn FnMut(FileId, FileReference) -> bool,
686 match NameClass::classify(self.sema, name) {
687 Some(NameClass::PatFieldShorthand { local_def: _, field_ref })
689 self.def, Definition::Field(_) if Definition::Field(field_ref) == self.def
692 let FileRange { file_id, range } = self.sema.original_range(name.syntax());
693 let reference = FileReference {
695 name: ast::NameLike::Name(name.clone()),
696 // FIXME: mutable patterns should have `Write` access
697 category: Some(ReferenceCategory::Read),
699 sink(file_id, reference)
701 Some(NameClass::ConstReference(def)) if self.def == def => {
702 let FileRange { file_id, range } = self.sema.original_range(name.syntax());
703 let reference = FileReference {
705 name: ast::NameLike::Name(name.clone()),
708 sink(file_id, reference)
710 Some(NameClass::Definition(def @ Definition::Local(local))) if def != self.def => {
713 Some(repr) if local.representative(self.sema.db) == repr
715 let FileRange { file_id, range } = self.sema.original_range(name.syntax());
716 let reference = FileReference {
718 name: ast::NameLike::Name(name.clone()),
721 return sink(file_id, reference);
725 Some(NameClass::Definition(def)) if def != self.def => {
726 // if the def we are looking for is a trait (impl) assoc item, we'll have to resolve the items to trait definition assoc item
728 self.trait_assoc_def,
729 Some(trait_assoc_def)
730 if convert_to_def_in_trait(self.sema.db, def) == trait_assoc_def
734 let FileRange { file_id, range } = self.sema.original_range(name.syntax());
735 let reference = FileReference {
737 name: ast::NameLike::Name(name.clone()),
740 sink(file_id, reference)
747 fn def_to_ty(sema: &Semantics<'_, RootDatabase>, def: &Definition) -> Option<hir::Type> {
749 Definition::Adt(adt) => Some(adt.ty(sema.db)),
750 Definition::TypeAlias(it) => Some(it.ty(sema.db)),
751 Definition::BuiltinType(it) => Some(it.ty(sema.db)),
752 Definition::SelfType(it) => Some(it.self_ty(sema.db)),
757 impl ReferenceCategory {
758 fn new(def: &Definition, r: &ast::NameRef) -> Option<ReferenceCategory> {
759 // Only Locals and Fields have accesses for now.
760 if !matches!(def, Definition::Local(_) | Definition::Field(_)) {
764 let mode = r.syntax().ancestors().find_map(|node| {
767 ast::BinExpr(expr) => {
768 if matches!(expr.op_kind()?, ast::BinaryOp::Assignment { .. }) {
769 // If the variable or field ends on the LHS's end then it's a Write (covers fields and locals).
770 // FIXME: This is not terribly accurate.
771 if let Some(lhs) = expr.lhs() {
772 if lhs.syntax().text_range().end() == r.syntax().text_range().end() {
773 return Some(ReferenceCategory::Write);
777 Some(ReferenceCategory::Read)
784 // Default Locals and Fields to read
785 mode.or(Some(ReferenceCategory::Read))