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};
9 use base_db::{FileId, FileRange, SourceDatabase, SourceDatabaseExt};
11 AsAssocItem, DefWithBody, HasAttrs, HasSource, InFile, ModuleDef, ModuleSource, Semantics,
14 use once_cell::unsync::Lazy;
15 use rustc_hash::FxHashMap;
16 use syntax::{ast, match_ast, AstNode, TextRange, TextSize};
19 defs::{Definition, NameClass, NameRefClass},
23 #[derive(Debug, Default, Clone)]
24 pub struct UsageSearchResult {
25 pub references: FxHashMap<FileId, Vec<FileReference>>,
28 impl UsageSearchResult {
29 pub fn is_empty(&self) -> bool {
30 self.references.is_empty()
33 pub fn len(&self) -> usize {
37 pub fn iter(&self) -> impl Iterator<Item = (&FileId, &Vec<FileReference>)> + '_ {
38 self.references.iter()
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 })
48 impl IntoIterator for UsageSearchResult {
49 type Item = (FileId, Vec<FileReference>);
50 type IntoIter = <FxHashMap<FileId, Vec<FileReference>> as IntoIterator>::IntoIter;
52 fn into_iter(self) -> Self::IntoIter {
53 self.references.into_iter()
57 #[derive(Debug, Clone)]
58 pub struct FileReference {
60 pub name: ast::NameLike,
61 pub access: Option<ReferenceAccess>,
64 #[derive(Debug, Copy, Clone, PartialEq)]
65 pub enum ReferenceAccess {
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>>,
79 fn new(entries: FxHashMap<FileId, Option<TextRange>>) -> SearchScope {
80 SearchScope { entries }
83 fn crate_graph(db: &RootDatabase) -> SearchScope {
84 let mut entries = FxHashMap::default();
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)));
93 SearchScope { entries }
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)));
104 SearchScope { entries }
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);
112 entries: source_root.iter().map(|id| (id, None)).collect::<FxHashMap<_, _>>(),
116 fn module(db: &RootDatabase, module: hir::Module) -> SearchScope {
117 let mut entries = FxHashMap::default();
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);
125 ModuleSource::Module(m) => {
127 let range = Some(m.syntax().text_range());
128 entries.insert(file_id, range);
130 // We have already added the enclosing file to the search scope,
134 ModuleSource::BlockExpr(b) => {
136 let range = Some(b.syntax().text_range());
137 entries.insert(file_id, range);
139 // We have already added the enclosing file to the search scope,
143 ModuleSource::SourceFile(_) => {
144 entries.insert(file_id, None);
148 to_visit.extend(module.children(db));
150 SearchScope { entries }
153 pub fn empty() -> SearchScope {
154 SearchScope::new(FxHashMap::default())
157 pub fn single_file(file: FileId) -> SearchScope {
158 SearchScope::new(std::iter::once((file, None)).collect())
161 pub fn file_range(range: FileRange) -> SearchScope {
162 SearchScope::new(std::iter::once((range.file_id, Some(range.range))).collect())
165 pub fn files(files: &[FileId]) -> SearchScope {
166 SearchScope::new(files.iter().map(|f| (*f, None)).collect())
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)
177 .filter_map(|(file_id, r1)| {
178 let r2 = large.get(file_id)?;
179 let r = intersect_ranges(*r1, *r2)?;
184 return SearchScope::new(res);
187 r1: Option<TextRange>,
188 r2: Option<TextRange>,
189 ) -> Option<Option<TextRange>> {
191 (None, r) | (r, None) => Some(r),
192 (Some(r1), Some(r2)) => {
193 let r = r1.intersect(r2)?;
201 impl IntoIterator for SearchScope {
202 type Item = (FileId, Option<TextRange>);
203 type IntoIter = std::collections::hash_map::IntoIter<FileId, Option<TextRange>>;
205 fn into_iter(self) -> Self::IntoIter {
206 self.entries.into_iter()
211 fn search_scope(&self, db: &RootDatabase) -> SearchScope {
212 let _p = profile::span("search_scope");
214 if let Definition::ModuleDef(hir::ModuleDef::BuiltinType(_)) = self {
215 return SearchScope::crate_graph(db);
218 let module = match self.module(db) {
220 None => return SearchScope::empty(),
222 let InFile { file_id, value: module_source } = module.definition_source(db);
223 let file_id = file_id.original_file(db);
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()),
232 Some(range) => SearchScope::file_range(FileRange { file_id, range }),
233 None => SearchScope::single_file(file_id),
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),
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())
249 hir::GenericDef::Adt(it) => match it {
250 hir::Adt::Struct(it) => {
251 it.source(db).map(|src| src.value.syntax().text_range())
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()),
256 hir::GenericDef::Trait(it) => {
257 it.source(db).map(|src| src.value.syntax().text_range())
259 hir::GenericDef::TypeAlias(it) => {
260 it.source(db).map(|src| src.value.syntax().text_range())
262 hir::GenericDef::Impl(it) => {
263 it.source(db).map(|src| src.value.syntax().text_range())
265 hir::GenericDef::Variant(it) => {
266 it.source(db).map(|src| src.value.syntax().text_range())
268 hir::GenericDef::Const(it) => {
269 it.source(db).map(|src| src.value.syntax().text_range())
273 Some(range) => SearchScope::file_range(FileRange { file_id, range }),
274 None => SearchScope::single_file(file_id),
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())
283 SearchScope::krate(db, module.krate())
288 let vis = self.visibility(db);
289 if let Some(Visibility::Public) = vis {
290 return SearchScope::reverse_dependencies(db, module.krate());
292 if let Some(Visibility::Module(module)) = vis {
293 return SearchScope::module(db, module.into());
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,
302 Some(range) => SearchScope::file_range(FileRange { file_id, range }),
303 None => SearchScope::single_file(file_id),
307 pub fn usages<'a>(self, sema: &'a Semantics<RootDatabase>) -> FindUsages<'a> {
312 include_self_kw_refs: None,
313 search_self_mod: false,
318 pub struct FindUsages<'a> {
320 sema: &'a Semantics<'a, RootDatabase>,
321 scope: Option<SearchScope>,
322 include_self_kw_refs: Option<hir::Type>,
323 search_self_mod: bool,
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;
334 pub fn in_scope(self, scope: SearchScope) -> FindUsages<'a> {
335 self.set_scope(Some(scope))
338 pub fn set_scope(mut self, scope: Option<SearchScope>) -> FindUsages<'a> {
339 assert!(self.scope.is_none());
344 pub fn at_least_one(self) -> bool {
345 let mut found = false;
346 self.search(&mut |_, _| {
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);
362 fn search(self, sink: &mut dyn FnMut(FileId, FileReference) -> bool) {
363 let _p = profile::span("FindUsages:search");
364 let sema = self.sema;
367 let base = self.def.search_scope(sema.db);
370 Some(scope) => base.intersection(scope),
374 let name = self.def.name(sema.db).or_else(|| {
375 self.include_self_kw_refs.as_ref().and_then(|ty| {
377 .map(|adt| adt.name(self.sema.db))
378 .or_else(|| ty.as_builtin().map(|builtin| builtin.name()))
381 let name = match name {
382 Some(name) => name.to_string(),
385 let name = name.as_str();
387 for (file_id, search_range) in search_scope {
388 let text = sema.db.file_text(file_id);
390 search_range.unwrap_or_else(|| TextRange::up_to(TextSize::of(text.as_str())));
392 let tree = Lazy::new(|| sema.parse(file_id).syntax().clone());
394 for (idx, _) in text.match_indices(name) {
395 let offset: TextSize = idx.try_into().unwrap();
396 if !search_range.contains_inclusive(offset) {
400 if let Some(name) = sema.find_node_at_offset_with_descend(&tree, offset) {
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),
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) {
417 if let Some(ast::NameLike::NameRef(name_ref)) =
418 sema.find_node_at_offset_with_descend(&tree, offset)
420 if self.found_self_ty_name_ref(self_ty, &name_ref, sink) {
428 // search for module `self` references in our module's definition source
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),
439 let text = sema.db.file_text(file_id);
441 search_range.unwrap_or_else(|| TextRange::up_to(TextSize::of(text.as_str())));
443 let tree = Lazy::new(|| sema.parse(file_id).syntax().clone());
445 for (idx, _) in text.match_indices("self") {
446 let offset: TextSize = idx.try_into().unwrap();
447 if !search_range.contains_inclusive(offset) {
451 if let Some(ast::NameLike::NameRef(name_ref)) =
452 sema.find_node_at_offset_with_descend(&tree, offset)
454 if self.found_self_module_name_ref(&name_ref, sink) {
464 fn found_self_ty_name_ref(
467 name_ref: &ast::NameRef,
468 sink: &mut dyn FnMut(FileId, FileReference) -> 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 =>
474 let FileRange { file_id, range } = self.sema.original_range(name_ref.syntax());
475 let reference = FileReference {
477 name: ast::NameLike::NameRef(name_ref.clone()),
480 sink(file_id, reference)
486 fn found_self_module_name_ref(
488 name_ref: &ast::NameRef,
489 sink: &mut dyn FnMut(FileId, FileReference) -> 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 {
496 name: ast::NameLike::NameRef(name_ref.clone()),
499 sink(file_id, reference)
507 lifetime: &ast::Lifetime,
508 sink: &mut dyn FnMut(FileId, FileReference) -> 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 {
515 name: ast::NameLike::Lifetime(lifetime.clone()),
518 sink(file_id, reference)
526 name_ref: &ast::NameRef,
527 sink: &mut dyn FnMut(FileId, FileReference) -> 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 {
534 name: ast::NameLike::NameRef(name_ref.clone()),
535 access: reference_access(&def, name_ref),
537 sink(file_id, reference)
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 {
544 name: ast::NameLike::NameRef(name_ref.clone()),
545 access: reference_access(&def, name_ref),
547 sink(file_id, reference)
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)
562 FileReference { range, name: ast::NameLike::NameRef(name_ref.clone()), access };
563 sink(file_id, reference)
572 sink: &mut dyn FnMut(FileId, FileReference) -> bool,
574 match NameClass::classify(self.sema, name) {
575 Some(NameClass::PatFieldShorthand { local_def: _, field_ref })
577 self.def, Definition::Field(_) if field_ref == self.def
580 let FileRange { file_id, range } = self.sema.original_range(name.syntax());
581 let reference = FileReference {
583 name: ast::NameLike::Name(name.clone()),
584 // FIXME: mutable patterns should have `Write` access
585 access: Some(ReferenceAccess::Read),
587 sink(file_id, reference)
589 Some(NameClass::ConstReference(def)) if self.def == def => {
590 let FileRange { file_id, range } = self.sema.original_range(name.syntax());
592 FileReference { range, name: ast::NameLike::Name(name.clone()), access: None };
593 sink(file_id, reference)
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 */
599 let this = match self.def {
600 Definition::ModuleDef(this) if this != mod_def => this,
603 let this_trait = this
604 .as_assoc_item(self.sema.db)?
605 .containing_trait_or_trait_impl(self.sema.db)?;
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))
612 let FileRange { file_id, range } = self.sema.original_range(name.syntax());
613 let reference = FileReference {
615 name: ast::NameLike::Name(name.clone()),
618 sink(file_id, reference)
628 fn def_to_ty(sema: &Semantics<RootDatabase>, def: &Definition) -> Option<hir::Type> {
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))
642 Definition::SelfType(it) => Some(it.self_ty(sema.db)),
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(_)) {
653 let mode = name_ref.syntax().ancestors().find_map(|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);
666 Some(ReferenceAccess::Read)
673 // Default Locals and Fields to read
674 mode.or(Some(ReferenceAccess::Read))