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::{convert::TryInto, mem, sync::Arc};
9 use base_db::{FileId, FileRange, SourceDatabase, SourceDatabaseExt};
11 AsAssocItem, DefWithBody, HasAttrs, HasSource, InFile, ModuleSource, Semantics, Visibility,
13 use once_cell::unsync::Lazy;
14 use rustc_hash::FxHashMap;
15 use syntax::{ast, match_ast, AstNode, TextRange, TextSize};
18 defs::{Definition, NameClass, NameRefClass},
22 #[derive(Debug, Default, Clone)]
23 pub struct UsageSearchResult {
24 pub references: FxHashMap<FileId, Vec<FileReference>>,
27 impl UsageSearchResult {
28 pub fn is_empty(&self) -> bool {
29 self.references.is_empty()
32 pub fn len(&self) -> usize {
36 pub fn iter(&self) -> impl Iterator<Item = (&FileId, &[FileReference])> + '_ {
37 self.references.iter().map(|(file_id, refs)| (file_id, &**refs))
40 pub fn file_ranges(&self) -> impl Iterator<Item = FileRange> + '_ {
41 self.references.iter().flat_map(|(&file_id, refs)| {
42 refs.iter().map(move |&FileReference { range, .. }| FileRange { file_id, range })
47 impl IntoIterator for UsageSearchResult {
48 type Item = (FileId, Vec<FileReference>);
49 type IntoIter = <FxHashMap<FileId, Vec<FileReference>> as IntoIterator>::IntoIter;
51 fn into_iter(self) -> Self::IntoIter {
52 self.references.into_iter()
56 #[derive(Debug, Clone)]
57 pub struct FileReference {
59 pub name: ast::NameLike,
60 pub category: Option<ReferenceCategory>,
63 #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
64 pub enum ReferenceCategory {
65 // FIXME: Add this variant and delete the `retain_adt_literal_usages` function.
69 // FIXME: Some day should be able to search in doc comments. Would probably
70 // need to switch from enum to bitflags then?
74 /// Generally, `search_scope` returns files that might contain references for the element.
75 /// For `pub(crate)` things it's a crate, for `pub` things it's a crate and dependant crates.
76 /// In some cases, the location of the references is known to within a `TextRange`,
77 /// e.g. for things like local variables.
78 #[derive(Clone, Debug)]
79 pub struct SearchScope {
80 entries: FxHashMap<FileId, Option<TextRange>>,
84 fn new(entries: FxHashMap<FileId, Option<TextRange>>) -> SearchScope {
85 SearchScope { entries }
88 fn crate_graph(db: &RootDatabase) -> SearchScope {
89 let mut entries = FxHashMap::default();
91 let graph = db.crate_graph();
92 for krate in graph.iter() {
93 let root_file = graph[krate].root_file_id;
94 let source_root_id = db.file_source_root(root_file);
95 let source_root = db.source_root(source_root_id);
96 entries.extend(source_root.iter().map(|id| (id, None)));
98 SearchScope { entries }
101 fn reverse_dependencies(db: &RootDatabase, of: hir::Crate) -> SearchScope {
102 let mut entries = FxHashMap::default();
103 for rev_dep in of.transitive_reverse_dependencies(db) {
104 let root_file = rev_dep.root_file(db);
105 let source_root_id = db.file_source_root(root_file);
106 let source_root = db.source_root(source_root_id);
107 entries.extend(source_root.iter().map(|id| (id, None)));
109 SearchScope { entries }
112 fn krate(db: &RootDatabase, of: hir::Crate) -> SearchScope {
113 let root_file = of.root_file(db);
114 let source_root_id = db.file_source_root(root_file);
115 let source_root = db.source_root(source_root_id);
117 entries: source_root.iter().map(|id| (id, None)).collect::<FxHashMap<_, _>>(),
121 fn module(db: &RootDatabase, module: hir::Module) -> SearchScope {
122 let mut entries = FxHashMap::default();
124 let mut to_visit = vec![module];
125 let mut is_first = true;
126 while let Some(module) = to_visit.pop() {
127 let src = module.definition_source(db);
128 let file_id = src.file_id.original_file(db);
130 ModuleSource::Module(m) => {
132 let range = Some(m.syntax().text_range());
133 entries.insert(file_id, range);
135 // We have already added the enclosing file to the search scope,
139 ModuleSource::BlockExpr(b) => {
141 let range = Some(b.syntax().text_range());
142 entries.insert(file_id, range);
144 // We have already added the enclosing file to the search scope,
148 ModuleSource::SourceFile(_) => {
149 entries.insert(file_id, None);
153 to_visit.extend(module.children(db));
155 SearchScope { entries }
158 pub fn empty() -> SearchScope {
159 SearchScope::new(FxHashMap::default())
162 pub fn single_file(file: FileId) -> SearchScope {
163 SearchScope::new(std::iter::once((file, None)).collect())
166 pub fn file_range(range: FileRange) -> SearchScope {
167 SearchScope::new(std::iter::once((range.file_id, Some(range.range))).collect())
170 pub fn files(files: &[FileId]) -> SearchScope {
171 SearchScope::new(files.iter().map(|f| (*f, None)).collect())
174 pub fn intersection(&self, other: &SearchScope) -> SearchScope {
175 let (mut small, mut large) = (&self.entries, &other.entries);
176 if small.len() > large.len() {
177 mem::swap(&mut small, &mut large)
182 .filter_map(|(file_id, r1)| {
183 let r2 = large.get(file_id)?;
184 let r = intersect_ranges(*r1, *r2)?;
189 return SearchScope::new(res);
192 r1: Option<TextRange>,
193 r2: Option<TextRange>,
194 ) -> Option<Option<TextRange>> {
196 (None, r) | (r, None) => Some(r),
197 (Some(r1), Some(r2)) => {
198 let r = r1.intersect(r2)?;
206 impl IntoIterator for SearchScope {
207 type Item = (FileId, Option<TextRange>);
208 type IntoIter = std::collections::hash_map::IntoIter<FileId, Option<TextRange>>;
210 fn into_iter(self) -> Self::IntoIter {
211 self.entries.into_iter()
216 fn search_scope(&self, db: &RootDatabase) -> SearchScope {
217 let _p = profile::span("search_scope");
219 if let Definition::BuiltinType(_) = self {
220 return SearchScope::crate_graph(db);
224 // FIXME: We don't do searches for crates currently, as a crate does not actually have a single name
225 if let &Definition::Module(module) = self {
226 if module.is_crate_root(db) {
227 return SearchScope::reverse_dependencies(db, module.krate());
231 let module = match self.module(db) {
233 None => return SearchScope::empty(),
235 let InFile { file_id, value: module_source } = module.definition_source(db);
236 let file_id = file_id.original_file(db);
238 if let Definition::Local(var) = self {
239 let def = match var.parent(db) {
240 DefWithBody::Function(f) => f.source(db).map(|src| src.syntax().cloned()),
241 DefWithBody::Const(c) => c.source(db).map(|src| src.syntax().cloned()),
242 DefWithBody::Static(s) => s.source(db).map(|src| src.syntax().cloned()),
245 Some(def) => SearchScope::file_range(def.as_ref().original_file_range(db)),
246 None => SearchScope::single_file(file_id),
250 if let Definition::SelfType(impl_) = self {
251 return match impl_.source(db).map(|src| src.syntax().cloned()) {
252 Some(def) => SearchScope::file_range(def.as_ref().original_file_range(db)),
253 None => SearchScope::single_file(file_id),
257 if let Definition::GenericParam(hir::GenericParam::LifetimeParam(param)) = self {
258 let def = match param.parent(db) {
259 hir::GenericDef::Function(it) => it.source(db).map(|src| src.syntax().cloned()),
260 hir::GenericDef::Adt(it) => it.source(db).map(|src| src.syntax().cloned()),
261 hir::GenericDef::Trait(it) => it.source(db).map(|src| src.syntax().cloned()),
262 hir::GenericDef::TypeAlias(it) => it.source(db).map(|src| src.syntax().cloned()),
263 hir::GenericDef::Impl(it) => it.source(db).map(|src| src.syntax().cloned()),
264 hir::GenericDef::Variant(it) => it.source(db).map(|src| src.syntax().cloned()),
265 hir::GenericDef::Const(it) => it.source(db).map(|src| src.syntax().cloned()),
268 Some(def) => SearchScope::file_range(def.as_ref().original_file_range(db)),
269 None => SearchScope::single_file(file_id),
273 if let Definition::Macro(macro_def) = self {
274 return match macro_def.kind(db) {
275 hir::MacroKind::Declarative => {
276 if macro_def.attrs(db).by_key("macro_export").exists() {
277 SearchScope::reverse_dependencies(db, module.krate())
279 SearchScope::krate(db, module.krate())
282 hir::MacroKind::BuiltIn => SearchScope::crate_graph(db),
283 // FIXME: We don't actually see derives in derive attributes as these do not
284 // expand to something that references the derive macro in the output.
285 // We could get around this by emitting dummy `use DeriveMacroPathHere as _;` items maybe?
286 hir::MacroKind::Derive | hir::MacroKind::Attr | hir::MacroKind::ProcMacro => {
287 SearchScope::reverse_dependencies(db, module.krate())
292 let vis = self.visibility(db);
293 if let Some(Visibility::Public) = vis {
294 return SearchScope::reverse_dependencies(db, module.krate());
296 if let Some(Visibility::Module(module)) = vis {
297 return SearchScope::module(db, module.into());
300 let range = match module_source {
301 ModuleSource::Module(m) => Some(m.syntax().text_range()),
302 ModuleSource::BlockExpr(b) => Some(b.syntax().text_range()),
303 ModuleSource::SourceFile(_) => None,
306 Some(range) => SearchScope::file_range(FileRange { file_id, range }),
307 None => SearchScope::single_file(file_id),
311 pub fn usages<'a>(self, sema: &'a Semantics<RootDatabase>) -> FindUsages<'a> {
313 local_repr: match self {
314 Definition::Local(local) => Some(local.representative(sema.db)),
320 include_self_kw_refs: None,
321 search_self_mod: false,
327 pub struct FindUsages<'a> {
329 sema: &'a Semantics<'a, RootDatabase>,
330 scope: Option<SearchScope>,
331 include_self_kw_refs: Option<hir::Type>,
332 local_repr: Option<hir::Local>,
333 search_self_mod: bool,
336 impl<'a> FindUsages<'a> {
337 /// Enable searching for `Self` when the definition is a type or `self` for modules.
338 pub fn include_self_refs(mut self) -> FindUsages<'a> {
339 self.include_self_kw_refs = def_to_ty(self.sema, &self.def);
340 self.search_self_mod = true;
344 pub fn in_scope(self, scope: SearchScope) -> FindUsages<'a> {
345 self.set_scope(Some(scope))
348 pub fn set_scope(mut self, scope: Option<SearchScope>) -> FindUsages<'a> {
349 assert!(self.scope.is_none());
354 pub fn at_least_one(&self) -> bool {
355 let mut found = false;
356 self.search(&mut |_, _| {
363 pub fn all(self) -> UsageSearchResult {
364 let mut res = UsageSearchResult::default();
365 self.search(&mut |file_id, reference| {
366 res.references.entry(file_id).or_default().push(reference);
372 fn search(&self, sink: &mut dyn FnMut(FileId, FileReference) -> bool) {
373 let _p = profile::span("FindUsages:search");
374 let sema = self.sema;
377 let base = self.def.search_scope(sema.db);
380 Some(scope) => base.intersection(scope),
384 let name = match self.def {
385 // special case crate modules as these do not have a proper name
386 Definition::Module(module) if module.is_crate_root(self.sema.db) => {
387 // FIXME: This assumes the crate name is always equal to its display name when it really isn't
390 .display_name(self.sema.db)
391 .map(|crate_name| crate_name.crate_name().as_smol_str().clone())
394 let self_kw_refs = || {
395 self.include_self_kw_refs.as_ref().and_then(|ty| {
397 .map(|adt| adt.name(self.sema.db))
398 .or_else(|| ty.as_builtin().map(|builtin| builtin.name()))
401 self.def.name(sema.db).or_else(self_kw_refs).map(|it| it.to_smol_str())
404 let name = match &name {
405 Some(s) => s.as_str(),
409 // these can't be closures because rust infers the lifetimes wrong ...
410 fn match_indices<'a>(
413 search_range: TextRange,
414 ) -> impl Iterator<Item = TextSize> + 'a {
415 text.match_indices(name).filter_map(move |(idx, _)| {
416 let offset: TextSize = idx.try_into().unwrap();
417 if !search_range.contains_inclusive(offset) {
424 sema: &'a Semantics<RootDatabase>,
425 scope: &'a SearchScope,
426 ) -> impl Iterator<Item = (Arc<String>, FileId, TextRange)> + 'a {
427 scope.entries.iter().map(|(&file_id, &search_range)| {
428 let text = sema.db.file_text(file_id);
430 search_range.unwrap_or_else(|| TextRange::up_to(TextSize::of(text.as_str())));
432 (text, file_id, search_range)
436 for (text, file_id, search_range) in scope_files(sema, &search_scope) {
437 let tree = Lazy::new(move || sema.parse(file_id).syntax().clone());
439 // Search for occurrences of the items name
440 for offset in match_indices(&text, name, search_range) {
441 for name in sema.find_nodes_at_offset_with_descend(&tree, offset) {
443 ast::NameLike::NameRef(name_ref) => self.found_name_ref(&name_ref, sink),
444 ast::NameLike::Name(name) => self.found_name(&name, sink),
445 ast::NameLike::Lifetime(lifetime) => self.found_lifetime(&lifetime, sink),
451 // Search for occurrences of the `Self` referring to our type
452 if let Some(self_ty) = &self.include_self_kw_refs {
453 for offset in match_indices(&text, "Self", search_range) {
454 for name_ref in sema.find_nodes_at_offset_with_descend(&tree, offset) {
455 if self.found_self_ty_name_ref(self_ty, &name_ref, sink) {
463 // Search for `super` and `crate` resolving to our module
465 Definition::Module(module) => {
466 let scope = search_scope.intersection(&SearchScope::module(self.sema.db, module));
468 let is_crate_root = module.is_crate_root(self.sema.db);
470 for (text, file_id, search_range) in scope_files(sema, &scope) {
471 let tree = Lazy::new(move || sema.parse(file_id).syntax().clone());
473 for offset in match_indices(&text, "super", search_range) {
474 for name_ref in sema.find_nodes_at_offset_with_descend(&tree, offset) {
475 if self.found_name_ref(&name_ref, sink) {
481 for offset in match_indices(&text, "crate", search_range) {
482 for name_ref in sema.find_nodes_at_offset_with_descend(&tree, offset) {
483 if self.found_name_ref(&name_ref, sink) {
494 // search for module `self` references in our module's definition source
496 Definition::Module(module) if self.search_self_mod => {
497 let src = module.definition_source(sema.db);
498 let file_id = src.file_id.original_file(sema.db);
499 let (file_id, search_range) = match src.value {
500 ModuleSource::Module(m) => (file_id, Some(m.syntax().text_range())),
501 ModuleSource::BlockExpr(b) => (file_id, Some(b.syntax().text_range())),
502 ModuleSource::SourceFile(_) => (file_id, None),
505 let search_range = if let Some(&range) = search_scope.entries.get(&file_id) {
506 match (range, search_range) {
507 (None, range) | (range, None) => range,
508 (Some(range), Some(search_range)) => match range.intersect(search_range) {
509 Some(range) => Some(range),
517 let text = sema.db.file_text(file_id);
519 search_range.unwrap_or_else(|| TextRange::up_to(TextSize::of(text.as_str())));
521 let tree = Lazy::new(|| sema.parse(file_id).syntax().clone());
523 for offset in match_indices(&text, "self", search_range) {
524 for name_ref in sema.find_nodes_at_offset_with_descend(&tree, offset) {
525 if self.found_self_module_name_ref(&name_ref, sink) {
535 fn found_self_ty_name_ref(
538 name_ref: &ast::NameRef,
539 sink: &mut dyn FnMut(FileId, FileReference) -> bool,
541 match NameRefClass::classify(self.sema, name_ref) {
542 Some(NameRefClass::Definition(Definition::SelfType(impl_)))
543 if impl_.self_ty(self.sema.db) == *self_ty =>
545 let FileRange { file_id, range } = self.sema.original_range(name_ref.syntax());
546 let reference = FileReference {
548 name: ast::NameLike::NameRef(name_ref.clone()),
551 sink(file_id, reference)
557 fn found_self_module_name_ref(
559 name_ref: &ast::NameRef,
560 sink: &mut dyn FnMut(FileId, FileReference) -> bool,
562 match NameRefClass::classify(self.sema, name_ref) {
563 Some(NameRefClass::Definition(def @ Definition::Module(_))) if def == self.def => {
564 let FileRange { file_id, range } = self.sema.original_range(name_ref.syntax());
565 let reference = FileReference {
567 name: ast::NameLike::NameRef(name_ref.clone()),
570 sink(file_id, reference)
578 lifetime: &ast::Lifetime,
579 sink: &mut dyn FnMut(FileId, FileReference) -> bool,
581 match NameRefClass::classify_lifetime(self.sema, lifetime) {
582 Some(NameRefClass::Definition(def)) if def == self.def => {
583 let FileRange { file_id, range } = self.sema.original_range(lifetime.syntax());
584 let reference = FileReference {
586 name: ast::NameLike::Lifetime(lifetime.clone()),
589 sink(file_id, reference)
597 name_ref: &ast::NameRef,
598 sink: &mut dyn FnMut(FileId, FileReference) -> bool,
600 match NameRefClass::classify(self.sema, name_ref) {
601 Some(NameRefClass::Definition(def @ Definition::Local(local)))
603 self.local_repr, Some(repr) if repr == local.representative(self.sema.db)
606 let FileRange { file_id, range } = self.sema.original_range(name_ref.syntax());
607 let reference = FileReference {
609 name: ast::NameLike::NameRef(name_ref.clone()),
610 category: ReferenceCategory::new(&def, name_ref),
612 sink(file_id, reference)
614 Some(NameRefClass::Definition(def)) if def == self.def => {
615 let FileRange { file_id, range } = self.sema.original_range(name_ref.syntax());
616 let reference = FileReference {
618 name: ast::NameLike::NameRef(name_ref.clone()),
619 category: ReferenceCategory::new(&def, name_ref),
621 sink(file_id, reference)
623 Some(NameRefClass::Definition(def)) if self.include_self_kw_refs.is_some() => {
624 if self.include_self_kw_refs == def_to_ty(self.sema, &def) {
625 let FileRange { file_id, range } = self.sema.original_range(name_ref.syntax());
626 let reference = FileReference {
628 name: ast::NameLike::NameRef(name_ref.clone()),
629 category: ReferenceCategory::new(&def, name_ref),
631 sink(file_id, reference)
636 Some(NameRefClass::FieldShorthand { local_ref: local, field_ref: field }) => {
637 let field = Definition::Field(field);
638 let FileRange { file_id, range } = self.sema.original_range(name_ref.syntax());
639 let access = match self.def {
640 Definition::Field(_) if field == self.def => {
641 ReferenceCategory::new(&field, name_ref)
643 Definition::Local(_) if matches!(self.local_repr, Some(repr) if repr == local.representative(self.sema.db)) => {
644 ReferenceCategory::new(&Definition::Local(local), name_ref)
648 let reference = FileReference {
650 name: ast::NameLike::NameRef(name_ref.clone()),
653 sink(file_id, reference)
662 sink: &mut dyn FnMut(FileId, FileReference) -> bool,
664 match NameClass::classify(self.sema, name) {
665 Some(NameClass::PatFieldShorthand { local_def: _, field_ref })
667 self.def, Definition::Field(_) if Definition::Field(field_ref) == self.def
670 let FileRange { file_id, range } = self.sema.original_range(name.syntax());
671 let reference = FileReference {
673 name: ast::NameLike::Name(name.clone()),
674 // FIXME: mutable patterns should have `Write` access
675 category: Some(ReferenceCategory::Read),
677 sink(file_id, reference)
679 Some(NameClass::ConstReference(def)) if self.def == def => {
680 let FileRange { file_id, range } = self.sema.original_range(name.syntax());
681 let reference = FileReference {
683 name: ast::NameLike::Name(name.clone()),
686 sink(file_id, reference)
688 Some(NameClass::Definition(def @ Definition::Local(local))) if def != self.def => {
691 Some(repr) if local.representative(self.sema.db) == repr
693 let FileRange { file_id, range } = self.sema.original_range(name.syntax());
694 let reference = FileReference {
696 name: ast::NameLike::Name(name.clone()),
699 return sink(file_id, reference);
703 // Resolve trait impl function definitions to the trait definition's version if self.def is the trait definition's
704 Some(NameClass::Definition(def)) if def != self.def => {
705 /* poor man's try block */
707 let this_trait = self
709 .as_assoc_item(self.sema.db)?
710 .containing_trait_or_trait_impl(self.sema.db)?;
712 .as_assoc_item(self.sema.db)?
713 .containing_trait_or_trait_impl(self.sema.db)?;
714 (trait_ == this_trait && self.def.name(self.sema.db) == def.name(self.sema.db))
716 let FileRange { file_id, range } =
717 self.sema.original_range(name.syntax());
718 let reference = FileReference {
720 name: ast::NameLike::Name(name.clone()),
723 sink(file_id, reference)
733 fn def_to_ty(sema: &Semantics<RootDatabase>, def: &Definition) -> Option<hir::Type> {
735 Definition::Adt(adt) => Some(adt.ty(sema.db)),
736 Definition::TypeAlias(it) => Some(it.ty(sema.db)),
737 Definition::BuiltinType(it) => Some(it.ty(sema.db)),
738 Definition::SelfType(it) => Some(it.self_ty(sema.db)),
743 impl ReferenceCategory {
744 fn new(def: &Definition, r: &ast::NameRef) -> Option<ReferenceCategory> {
745 // Only Locals and Fields have accesses for now.
746 if !matches!(def, Definition::Local(_) | Definition::Field(_)) {
750 let mode = r.syntax().ancestors().find_map(|node| {
753 ast::BinExpr(expr) => {
754 if matches!(expr.op_kind()?, ast::BinaryOp::Assignment { .. }) {
755 // If the variable or field ends on the LHS's end then it's a Write (covers fields and locals).
756 // FIXME: This is not terribly accurate.
757 if let Some(lhs) = expr.lhs() {
758 if lhs.syntax().text_range().end() == r.syntax().text_range().end() {
759 return Some(ReferenceCategory::Write);
763 Some(ReferenceCategory::Read)
770 // Default Locals and Fields to read
771 mode.or(Some(ReferenceCategory::Read))