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 DefWithBody, HasAttrs, HasSource, InFile, ModuleDef, 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, &Vec<FileReference>)> + '_ {
37 self.references.iter()
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 access: Option<ReferenceAccess>,
63 #[derive(Debug, Copy, Clone, PartialEq)]
64 pub enum ReferenceAccess {
69 /// Generally, `search_scope` returns files that might contain references for the element.
70 /// For `pub(crate)` things it's a crate, for `pub` things it's a crate and dependant crates.
71 /// In some cases, the location of the references is known to within a `TextRange`,
72 /// e.g. for things like local variables.
73 pub struct SearchScope {
74 entries: FxHashMap<FileId, Option<TextRange>>,
78 fn new(entries: FxHashMap<FileId, Option<TextRange>>) -> SearchScope {
79 SearchScope { entries }
82 fn crate_graph(db: &RootDatabase) -> SearchScope {
83 let mut entries = FxHashMap::default();
85 let graph = db.crate_graph();
86 for krate in graph.iter() {
87 let root_file = graph[krate].root_file_id;
88 let source_root_id = db.file_source_root(root_file);
89 let source_root = db.source_root(source_root_id);
90 entries.extend(source_root.iter().map(|id| (id, None)));
92 SearchScope { entries }
95 fn reverse_dependencies(db: &RootDatabase, of: hir::Crate) -> SearchScope {
96 let mut entries = FxHashMap::default();
97 for rev_dep in of.transitive_reverse_dependencies(db) {
98 let root_file = rev_dep.root_file(db);
99 let source_root_id = db.file_source_root(root_file);
100 let source_root = db.source_root(source_root_id);
101 entries.extend(source_root.iter().map(|id| (id, None)));
103 SearchScope { entries }
106 fn krate(db: &RootDatabase, of: hir::Crate) -> SearchScope {
107 let root_file = of.root_file(db);
108 let source_root_id = db.file_source_root(root_file);
109 let source_root = db.source_root(source_root_id);
111 entries: source_root.iter().map(|id| (id, None)).collect::<FxHashMap<_, _>>(),
115 fn module(db: &RootDatabase, module: hir::Module) -> SearchScope {
116 let mut entries = FxHashMap::default();
118 let mut to_visit = vec![module];
119 let mut is_first = true;
120 while let Some(module) = to_visit.pop() {
121 let src = module.definition_source(db);
122 let file_id = src.file_id.original_file(db);
124 ModuleSource::Module(m) => {
126 let range = Some(m.syntax().text_range());
127 entries.insert(file_id, range);
129 // We have already added the enclosing file to the search scope,
133 ModuleSource::BlockExpr(b) => {
135 let range = Some(b.syntax().text_range());
136 entries.insert(file_id, range);
138 // We have already added the enclosing file to the search scope,
142 ModuleSource::SourceFile(_) => {
143 entries.insert(file_id, None);
147 to_visit.extend(module.children(db));
149 SearchScope { entries }
152 pub fn empty() -> SearchScope {
153 SearchScope::new(FxHashMap::default())
156 pub fn single_file(file: FileId) -> SearchScope {
157 SearchScope::new(std::iter::once((file, None)).collect())
160 pub fn file_range(range: FileRange) -> SearchScope {
161 SearchScope::new(std::iter::once((range.file_id, Some(range.range))).collect())
164 pub fn files(files: &[FileId]) -> SearchScope {
165 SearchScope::new(files.iter().map(|f| (*f, None)).collect())
168 pub fn intersection(&self, other: &SearchScope) -> SearchScope {
169 let (mut small, mut large) = (&self.entries, &other.entries);
170 if small.len() > large.len() {
171 mem::swap(&mut small, &mut large)
176 .filter_map(|(file_id, r1)| {
177 let r2 = large.get(file_id)?;
178 let r = intersect_ranges(*r1, *r2)?;
183 return SearchScope::new(res);
186 r1: Option<TextRange>,
187 r2: Option<TextRange>,
188 ) -> Option<Option<TextRange>> {
190 (None, r) | (r, None) => Some(r),
191 (Some(r1), Some(r2)) => {
192 let r = r1.intersect(r2)?;
200 impl IntoIterator for SearchScope {
201 type Item = (FileId, Option<TextRange>);
202 type IntoIter = std::collections::hash_map::IntoIter<FileId, Option<TextRange>>;
204 fn into_iter(self) -> Self::IntoIter {
205 self.entries.into_iter()
210 fn search_scope(&self, db: &RootDatabase) -> SearchScope {
211 let _p = profile::span("search_scope");
213 if let Definition::ModuleDef(hir::ModuleDef::BuiltinType(_)) = self {
214 return SearchScope::crate_graph(db);
217 let module = match self.module(db) {
219 None => return SearchScope::empty(),
221 let InFile { file_id, value: module_source } = module.definition_source(db);
222 let file_id = file_id.original_file(db);
224 if let Definition::Local(var) = self {
225 let range = match var.parent(db) {
226 DefWithBody::Function(f) => f.source(db).map(|src| src.value.syntax().text_range()),
227 DefWithBody::Const(c) => c.source(db).map(|src| src.value.syntax().text_range()),
228 DefWithBody::Static(s) => s.source(db).map(|src| src.value.syntax().text_range()),
231 Some(range) => SearchScope::file_range(FileRange { file_id, range }),
232 None => SearchScope::single_file(file_id),
236 if let Definition::GenericParam(hir::GenericParam::LifetimeParam(param)) = self {
237 let range = match param.parent(db) {
238 hir::GenericDef::Function(it) => {
239 it.source(db).map(|src| src.value.syntax().text_range())
241 hir::GenericDef::Adt(it) => match it {
242 hir::Adt::Struct(it) => {
243 it.source(db).map(|src| src.value.syntax().text_range())
245 hir::Adt::Union(it) => it.source(db).map(|src| src.value.syntax().text_range()),
246 hir::Adt::Enum(it) => it.source(db).map(|src| src.value.syntax().text_range()),
248 hir::GenericDef::Trait(it) => {
249 it.source(db).map(|src| src.value.syntax().text_range())
251 hir::GenericDef::TypeAlias(it) => {
252 it.source(db).map(|src| src.value.syntax().text_range())
254 hir::GenericDef::Impl(it) => {
255 it.source(db).map(|src| src.value.syntax().text_range())
257 hir::GenericDef::Variant(it) => {
258 it.source(db).map(|src| src.value.syntax().text_range())
260 hir::GenericDef::Const(it) => {
261 it.source(db).map(|src| src.value.syntax().text_range())
265 Some(range) => SearchScope::file_range(FileRange { file_id, range }),
266 None => SearchScope::single_file(file_id),
270 if let Definition::Macro(macro_def) = self {
271 if macro_def.kind() == hir::MacroKind::Declarative {
272 return if macro_def.attrs(db).by_key("macro_export").exists() {
273 SearchScope::reverse_dependencies(db, module.krate())
275 SearchScope::krate(db, module.krate())
280 let vis = self.visibility(db);
281 if let Some(Visibility::Public) = vis {
282 return SearchScope::reverse_dependencies(db, module.krate());
284 if let Some(Visibility::Module(module)) = vis {
285 return SearchScope::module(db, module.into());
288 let range = match module_source {
289 ModuleSource::Module(m) => Some(m.syntax().text_range()),
290 ModuleSource::BlockExpr(b) => Some(b.syntax().text_range()),
291 ModuleSource::SourceFile(_) => None,
294 Some(range) => SearchScope::file_range(FileRange { file_id, range }),
295 None => SearchScope::single_file(file_id),
299 pub fn usages<'a>(&'a self, sema: &'a Semantics<RootDatabase>) -> FindUsages<'a> {
300 FindUsages { def: self, sema, scope: None, include_self_kw_refs: false }
304 pub struct FindUsages<'a> {
306 sema: &'a Semantics<'a, RootDatabase>,
307 scope: Option<SearchScope>,
308 include_self_kw_refs: bool,
311 impl<'a> FindUsages<'a> {
312 pub fn include_self_kw_refs(mut self, include: bool) -> FindUsages<'a> {
313 self.include_self_kw_refs = include;
317 pub fn in_scope(self, scope: SearchScope) -> FindUsages<'a> {
318 self.set_scope(Some(scope))
321 pub fn set_scope(mut self, scope: Option<SearchScope>) -> FindUsages<'a> {
322 assert!(self.scope.is_none());
327 pub fn at_least_one(self) -> bool {
328 let mut found = false;
329 self.search(&mut |_, _| {
336 pub fn all(self) -> UsageSearchResult {
337 let mut res = UsageSearchResult::default();
338 self.search(&mut |file_id, reference| {
339 res.references.entry(file_id).or_default().push(reference);
345 fn search(self, sink: &mut dyn FnMut(FileId, FileReference) -> bool) {
346 let _p = profile::span("FindUsages:search");
347 let sema = self.sema;
350 let base = self.def.search_scope(sema.db);
353 Some(scope) => base.intersection(scope),
357 let name = match self.def.name(sema.db) {
358 Some(it) => it.to_string(),
362 let pat = name.as_str();
363 let search_for_self = self.include_self_kw_refs;
365 for (file_id, search_range) in search_scope {
366 let text = sema.db.file_text(file_id);
368 search_range.unwrap_or_else(|| TextRange::up_to(TextSize::of(text.as_str())));
370 let tree = Lazy::new(|| sema.parse(file_id).syntax().clone());
372 let mut handle_match = |idx: usize| -> bool {
373 let offset: TextSize = idx.try_into().unwrap();
374 if !search_range.contains_inclusive(offset) {
378 if let Some(name) = sema.find_node_at_offset_with_descend(&tree, offset) {
380 ast::NameLike::NameRef(name_ref) => {
381 if self.found_name_ref(&name_ref, sink) {
385 ast::NameLike::Name(name) => {
386 if self.found_name(&name, sink) {
390 ast::NameLike::Lifetime(lifetime) => {
391 if self.found_lifetime(&lifetime, sink) {
401 for (idx, _) in text.match_indices(pat) {
402 if handle_match(idx) {
408 for (idx, _) in text.match_indices("Self") {
409 if handle_match(idx) {
419 lifetime: &ast::Lifetime,
420 sink: &mut dyn FnMut(FileId, FileReference) -> bool,
422 match NameRefClass::classify_lifetime(self.sema, lifetime) {
423 Some(NameRefClass::Definition(def)) if &def == self.def => {
424 let FileRange { file_id, range } = self.sema.original_range(lifetime.syntax());
425 let reference = FileReference {
427 name: ast::NameLike::Lifetime(lifetime.clone()),
430 sink(file_id, reference)
432 _ => false, // not a usage
438 name_ref: &ast::NameRef,
439 sink: &mut dyn FnMut(FileId, FileReference) -> bool,
441 match NameRefClass::classify(self.sema, &name_ref) {
442 Some(NameRefClass::Definition(def)) if &def == self.def => {
443 let FileRange { file_id, range } = self.sema.original_range(name_ref.syntax());
444 let reference = FileReference {
446 name: ast::NameLike::NameRef(name_ref.clone()),
447 access: reference_access(&def, &name_ref),
449 sink(file_id, reference)
451 Some(NameRefClass::Definition(Definition::SelfType(impl_))) => {
452 let ty = impl_.self_ty(self.sema.db);
454 if let Some(adt) = ty.as_adt() {
455 if &Definition::ModuleDef(ModuleDef::Adt(adt)) == self.def {
456 let FileRange { file_id, range } =
457 self.sema.original_range(name_ref.syntax());
458 let reference = FileReference {
460 name: ast::NameLike::NameRef(name_ref.clone()),
463 return sink(file_id, reference);
469 Some(NameRefClass::FieldShorthand { local_ref: local, field_ref: field }) => {
470 let FileRange { file_id, range } = self.sema.original_range(name_ref.syntax());
471 let reference = match self.def {
472 Definition::Field(_) if &field == self.def => FileReference {
474 name: ast::NameLike::NameRef(name_ref.clone()),
475 access: reference_access(&field, &name_ref),
477 Definition::Local(l) if &local == l => FileReference {
479 name: ast::NameLike::NameRef(name_ref.clone()),
480 access: reference_access(&Definition::Local(local), &name_ref),
482 _ => return false, // not a usage
484 sink(file_id, reference)
486 _ => false, // not a usage
493 sink: &mut dyn FnMut(FileId, FileReference) -> bool,
495 match NameClass::classify(self.sema, name) {
496 Some(NameClass::PatFieldShorthand { local_def: _, field_ref })
498 self.def, Definition::Field(_) if &field_ref == self.def
501 let FileRange { file_id, range } = self.sema.original_range(name.syntax());
502 let reference = FileReference {
504 name: ast::NameLike::Name(name.clone()),
505 // FIXME: mutable patterns should have `Write` access
506 access: Some(ReferenceAccess::Read),
508 sink(file_id, reference)
510 Some(NameClass::ConstReference(def)) if *self.def == def => {
511 let FileRange { file_id, range } = self.sema.original_range(name.syntax());
513 FileReference { range, name: ast::NameLike::Name(name.clone()), access: None };
514 sink(file_id, reference)
516 _ => false, // not a usage
521 fn reference_access(def: &Definition, name_ref: &ast::NameRef) -> Option<ReferenceAccess> {
522 // Only Locals and Fields have accesses for now.
523 if !matches!(def, Definition::Local(_) | Definition::Field(_)) {
527 let mode = name_ref.syntax().ancestors().find_map(|node| {
530 ast::BinExpr(expr) => {
531 if expr.op_kind()?.is_assignment() {
532 // If the variable or field ends on the LHS's end then it's a Write (covers fields and locals).
533 // FIXME: This is not terribly accurate.
534 if let Some(lhs) = expr.lhs() {
535 if lhs.syntax().text_range().end() == name_ref.syntax().text_range().end() {
536 return Some(ReferenceAccess::Write);
540 Some(ReferenceAccess::Read)
547 // Default Locals and Fields to read
548 mode.or(Some(ReferenceAccess::Read))