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, SourceDatabaseExt};
  10 use hir::{DefWithBody, HasSource, Module, ModuleSource, Semantics, Visibility};
  11 use once_cell::unsync::Lazy;
  12 use rustc_hash::FxHashMap;
  13 use syntax::{ast, match_ast, AstNode, TextRange, TextSize};
  14
  15 use crate::defs::NameClass;
  16 use crate::{
  17     defs::{Definition, NameRefClass},
  18     RootDatabase,
  19 };
  20
  21 #[derive(Debug, Default, Clone)]
  22 pub struct UsageSearchResult {
  23     pub references: FxHashMap<FileId, Vec<FileReference>>,
  24 }
  25
  26 impl UsageSearchResult {
  27     pub fn is_empty(&self) -> bool {
  28         self.references.is_empty()
  29     }
  30
  31     pub fn len(&self) -> usize {
  32         self.references.len()
  33     }
  34
  35     pub fn iter(&self) -> impl Iterator<Item = (&FileId, &Vec<FileReference>)> + '_ {
  36         self.references.iter()
  37     }
  38
  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 })
  42         })
  43     }
  44 }
  45
  46 impl IntoIterator for UsageSearchResult {
  47     type Item = (FileId, Vec<FileReference>);
  48     type IntoIter = <FxHashMap<FileId, Vec<FileReference>> as IntoIterator>::IntoIter;
  49
  50     fn into_iter(self) -> Self::IntoIter {
  51         self.references.into_iter()
  52     }
  53 }
  54
  55 #[derive(Debug, Clone)]
  56 pub enum NameLike {
  57     NameRef(ast::NameRef),
  58     Name(ast::Name),
  59     Lifetime(ast::Lifetime),
  60 }
  61
  62 impl NameLike {
  63     pub fn as_name_ref(&self) -> Option<&ast::NameRef> {
  64         match self {
  65             NameLike::NameRef(name_ref) => Some(name_ref),
  66             _ => None,
  67         }
  68     }
  69 }
  70
  71 mod __ {
  72     use super::{
  73         ast::{Lifetime, Name, NameRef},
  74         NameLike,
  75     };
  76     stdx::impl_from!(NameRef, Name, Lifetime for NameLike);
  77 }
  78
  79 #[derive(Debug, Clone)]
  80 pub struct FileReference {
  81     pub range: TextRange,
  82     pub name: NameLike,
  83     pub access: Option<ReferenceAccess>,
  84 }
  85
  86 #[derive(Debug, Copy, Clone, PartialEq)]
  87 pub enum ReferenceAccess {
  88     Read,
  89     Write,
  90 }
  91
  92 /// Generally, `search_scope` returns files that might contain references for the element.
  93 /// For `pub(crate)` things it's a crate, for `pub` things it's a crate and dependant crates.
  94 /// In some cases, the location of the references is known to within a `TextRange`,
  95 /// e.g. for things like local variables.
  96 pub struct SearchScope {
  97     entries: FxHashMap<FileId, Option<TextRange>>,
  98 }
  99
 100 impl SearchScope {
 101     fn new(entries: FxHashMap<FileId, Option<TextRange>>) -> SearchScope {
 102         SearchScope { entries }
 103     }
 104
 105     pub fn empty() -> SearchScope {
 106         SearchScope::new(FxHashMap::default())
 107     }
 108
 109     pub fn single_file(file: FileId) -> SearchScope {
 110         SearchScope::new(std::iter::once((file, None)).collect())
 111     }
 112
 113     pub fn files(files: &[FileId]) -> SearchScope {
 114         SearchScope::new(files.iter().map(|f| (*f, None)).collect())
 115     }
 116
 117     pub fn intersection(&self, other: &SearchScope) -> SearchScope {
 118         let (mut small, mut large) = (&self.entries, &other.entries);
 119         if small.len() > large.len() {
 120             mem::swap(&mut small, &mut large)
 121         }
 122
 123         let res = small
 124             .iter()
 125             .filter_map(|(file_id, r1)| {
 126                 let r2 = large.get(file_id)?;
 127                 let r = intersect_ranges(*r1, *r2)?;
 128                 Some((*file_id, r))
 129             })
 130             .collect();
 131
 132         return SearchScope::new(res);
 133
 134         fn intersect_ranges(
 135             r1: Option<TextRange>,
 136             r2: Option<TextRange>,
 137         ) -> Option<Option<TextRange>> {
 138             match (r1, r2) {
 139                 (None, r) | (r, None) => Some(r),
 140                 (Some(r1), Some(r2)) => {
 141                     let r = r1.intersect(r2)?;
 142                     Some(Some(r))
 143                 }
 144             }
 145         }
 146     }
 147 }
 148
 149 impl IntoIterator for SearchScope {
 150     type Item = (FileId, Option<TextRange>);
 151     type IntoIter = std::collections::hash_map::IntoIter<FileId, Option<TextRange>>;
 152
 153     fn into_iter(self) -> Self::IntoIter {
 154         self.entries.into_iter()
 155     }
 156 }
 157
 158 impl Definition {
 159     fn search_scope(&self, db: &RootDatabase) -> SearchScope {
 160         let _p = profile::span("search_scope");
 161         let module = match self.module(db) {
 162             Some(it) => it,
 163             None => return SearchScope::empty(),
 164         };
 165         let module_src = module.definition_source(db);
 166         let file_id = module_src.file_id.original_file(db);
 167
 168         if let Definition::Local(var) = self {
 169             let range = match var.parent(db) {
 170                 DefWithBody::Function(f) => {
 171                     f.source(db).and_then(|src| Some(src.value.syntax().text_range()))
 172                 }
 173                 DefWithBody::Const(c) => {
 174                     c.source(db).and_then(|src| Some(src.value.syntax().text_range()))
 175                 }
 176                 DefWithBody::Static(s) => {
 177                     s.source(db).and_then(|src| Some(src.value.syntax().text_range()))
 178                 }
 179             };
 180             let mut res = FxHashMap::default();
 181             res.insert(file_id, range);
 182             return SearchScope::new(res);
 183         }
 184
 185         if let Definition::GenericParam(hir::GenericParam::LifetimeParam(param)) = self {
 186             let range = match param.parent(db) {
 187                 hir::GenericDef::Function(it) => {
 188                     it.source(db).and_then(|src| Some(src.value.syntax().text_range()))
 189                 }
 190                 hir::GenericDef::Adt(it) => match it {
 191                     hir::Adt::Struct(it) => {
 192                         it.source(db).and_then(|src| Some(src.value.syntax().text_range()))
 193                     }
 194                     hir::Adt::Union(it) => {
 195                         it.source(db).and_then(|src| Some(src.value.syntax().text_range()))
 196                     }
 197                     hir::Adt::Enum(it) => {
 198                         it.source(db).and_then(|src| Some(src.value.syntax().text_range()))
 199                     }
 200                 },
 201                 hir::GenericDef::Trait(it) => {
 202                     it.source(db).and_then(|src| Some(src.value.syntax().text_range()))
 203                 }
 204                 hir::GenericDef::TypeAlias(it) => {
 205                     it.source(db).and_then(|src| Some(src.value.syntax().text_range()))
 206                 }
 207                 hir::GenericDef::Impl(it) => {
 208                     it.source(db).and_then(|src| Some(src.value.syntax().text_range()))
 209                 }
 210                 hir::GenericDef::Variant(it) => {
 211                     it.source(db).and_then(|src| Some(src.value.syntax().text_range()))
 212                 }
 213                 hir::GenericDef::Const(it) => {
 214                     it.source(db).and_then(|src| Some(src.value.syntax().text_range()))
 215                 }
 216             };
 217             let mut res = FxHashMap::default();
 218             res.insert(file_id, range);
 219             return SearchScope::new(res);
 220         }
 221
 222         let vis = self.visibility(db);
 223
 224         if let Some(Visibility::Module(module)) = vis.and_then(|it| it.into()) {
 225             let module: Module = module.into();
 226             let mut res = FxHashMap::default();
 227
 228             let mut to_visit = vec![module];
 229             let mut is_first = true;
 230             while let Some(module) = to_visit.pop() {
 231                 let src = module.definition_source(db);
 232                 let file_id = src.file_id.original_file(db);
 233                 match src.value {
 234                     ModuleSource::Module(m) => {
 235                         if is_first {
 236                             let range = Some(m.syntax().text_range());
 237                             res.insert(file_id, range);
 238                         } else {
 239                             // We have already added the enclosing file to the search scope,
 240                             // so do nothing.
 241                         }
 242                     }
 243                     ModuleSource::BlockExpr(b) => {
 244                         if is_first {
 245                             let range = Some(b.syntax().text_range());
 246                             res.insert(file_id, range);
 247                         } else {
 248                             // We have already added the enclosing file to the search scope,
 249                             // so do nothing.
 250                         }
 251                     }
 252                     ModuleSource::SourceFile(_) => {
 253                         res.insert(file_id, None);
 254                     }
 255                 };
 256                 is_first = false;
 257                 to_visit.extend(module.children(db));
 258             }
 259
 260             return SearchScope::new(res);
 261         }
 262
 263         if let Some(Visibility::Public) = vis {
 264             let source_root_id = db.file_source_root(file_id);
 265             let source_root = db.source_root(source_root_id);
 266             let mut res = source_root.iter().map(|id| (id, None)).collect::<FxHashMap<_, _>>();
 267
 268             let krate = module.krate();
 269             for rev_dep in krate.reverse_dependencies(db) {
 270                 let root_file = rev_dep.root_file(db);
 271                 let source_root_id = db.file_source_root(root_file);
 272                 let source_root = db.source_root(source_root_id);
 273                 res.extend(source_root.iter().map(|id| (id, None)));
 274             }
 275             return SearchScope::new(res);
 276         }
 277
 278         let mut res = FxHashMap::default();
 279         let range = match module_src.value {
 280             ModuleSource::Module(m) => Some(m.syntax().text_range()),
 281             ModuleSource::BlockExpr(b) => Some(b.syntax().text_range()),
 282             ModuleSource::SourceFile(_) => None,
 283         };
 284         res.insert(file_id, range);
 285         SearchScope::new(res)
 286     }
 287
 288     pub fn usages<'a>(&'a self, sema: &'a Semantics<RootDatabase>) -> FindUsages<'a> {
 289         FindUsages { def: self, sema, scope: None }
 290     }
 291 }
 292
 293 pub struct FindUsages<'a> {
 294     def: &'a Definition,
 295     sema: &'a Semantics<'a, RootDatabase>,
 296     scope: Option<SearchScope>,
 297 }
 298
 299 impl<'a> FindUsages<'a> {
 300     pub fn in_scope(self, scope: SearchScope) -> FindUsages<'a> {
 301         self.set_scope(Some(scope))
 302     }
 303     pub fn set_scope(mut self, scope: Option<SearchScope>) -> FindUsages<'a> {
 304         assert!(self.scope.is_none());
 305         self.scope = scope;
 306         self
 307     }
 308
 309     pub fn at_least_one(self) -> bool {
 310         let mut found = false;
 311         self.search(&mut |_, _| {
 312             found = true;
 313             true
 314         });
 315         found
 316     }
 317
 318     pub fn all(self) -> UsageSearchResult {
 319         let mut res = UsageSearchResult::default();
 320         self.search(&mut |file_id, reference| {
 321             res.references.entry(file_id).or_default().push(reference);
 322             false
 323         });
 324         res
 325     }
 326
 327     fn search(self, sink: &mut dyn FnMut(FileId, FileReference) -> bool) {
 328         let _p = profile::span("FindUsages:search");
 329         let sema = self.sema;
 330
 331         let search_scope = {
 332             let base = self.def.search_scope(sema.db);
 333             match &self.scope {
 334                 None => base,
 335                 Some(scope) => base.intersection(scope),
 336             }
 337         };
 338
 339         let name = match self.def.name(sema.db) {
 340             Some(it) => it.to_string(),
 341             None => return,
 342         };
 343
 344         let pat = name.as_str();
 345         for (file_id, search_range) in search_scope {
 346             let text = sema.db.file_text(file_id);
 347             let search_range =
 348                 search_range.unwrap_or(TextRange::up_to(TextSize::of(text.as_str())));
 349
 350             let tree = Lazy::new(|| sema.parse(file_id).syntax().clone());
 351
 352             for (idx, _) in text.match_indices(pat) {
 353                 let offset: TextSize = idx.try_into().unwrap();
 354                 if !search_range.contains_inclusive(offset) {
 355                     continue;
 356                 }
 357
 358                 if let Some(name_ref) = sema.find_node_at_offset_with_descend(&tree, offset) {
 359                     if self.found_name_ref(&name_ref, sink) {
 360                         return;
 361                     }
 362                 } else if let Some(name) = sema.find_node_at_offset_with_descend(&tree, offset) {
 363                     if self.found_name(&name, sink) {
 364                         return;
 365                     }
 366                 } else if let Some(lifetime) = sema.find_node_at_offset_with_descend(&tree, offset)
 367                 {
 368                     if self.found_lifetime(&lifetime, sink) {
 369                         return;
 370                     }
 371                 }
 372             }
 373         }
 374     }
 375
 376     fn found_lifetime(
 377         &self,
 378         lifetime: &ast::Lifetime,
 379         sink: &mut dyn FnMut(FileId, FileReference) -> bool,
 380     ) -> bool {
 381         match NameRefClass::classify_lifetime(self.sema, lifetime) {
 382             Some(NameRefClass::Definition(def)) if &def == self.def => {
 383                 let FileRange { file_id, range } = self.sema.original_range(lifetime.syntax());
 384                 let reference = FileReference {
 385                     range,
 386                     name: NameLike::Lifetime(lifetime.clone()),
 387                     access: None,
 388                 };
 389                 sink(file_id, reference)
 390             }
 391             _ => false, // not a usage
 392         }
 393     }
 394
 395     fn found_name_ref(
 396         &self,
 397         name_ref: &ast::NameRef,
 398         sink: &mut dyn FnMut(FileId, FileReference) -> bool,
 399     ) -> bool {
 400         match NameRefClass::classify(self.sema, &name_ref) {
 401             Some(NameRefClass::Definition(def)) if &def == self.def => {
 402                 let FileRange { file_id, range } = self.sema.original_range(name_ref.syntax());
 403                 let reference = FileReference {
 404                     range,
 405                     name: NameLike::NameRef(name_ref.clone()),
 406                     access: reference_access(&def, &name_ref),
 407                 };
 408                 sink(file_id, reference)
 409             }
 410             Some(NameRefClass::FieldShorthand { local_ref: local, field_ref: field }) => {
 411                 let FileRange { file_id, range } = self.sema.original_range(name_ref.syntax());
 412                 let reference = match self.def {
 413                     Definition::Field(_) if &field == self.def => FileReference {
 414                         range,
 415                         name: NameLike::NameRef(name_ref.clone()),
 416                         access: reference_access(&field, &name_ref),
 417                     },
 418                     Definition::Local(l) if &local == l => FileReference {
 419                         range,
 420                         name: NameLike::NameRef(name_ref.clone()),
 421                         access: reference_access(&Definition::Local(local), &name_ref),
 422                     },
 423                     _ => return false, // not a usage
 424                 };
 425                 sink(file_id, reference)
 426             }
 427             _ => false, // not a usage
 428         }
 429     }
 430
 431     fn found_name(
 432         &self,
 433         name: &ast::Name,
 434         sink: &mut dyn FnMut(FileId, FileReference) -> bool,
 435     ) -> bool {
 436         match NameClass::classify(self.sema, name) {
 437             Some(NameClass::PatFieldShorthand { local_def: _, field_ref }) => {
 438                 if !matches!(self.def, Definition::Field(_) if &field_ref == self.def) {
 439                     return false;
 440                 }
 441                 let FileRange { file_id, range } = self.sema.original_range(name.syntax());
 442                 let reference = FileReference {
 443                     range,
 444                     name: NameLike::Name(name.clone()),
 445                     // FIXME: mutable patterns should have `Write` access
 446                     access: Some(ReferenceAccess::Read),
 447                 };
 448                 sink(file_id, reference)
 449             }
 450             _ => false, // not a usage
 451         }
 452     }
 453 }
 454
 455 fn reference_access(def: &Definition, name_ref: &ast::NameRef) -> Option<ReferenceAccess> {
 456     // Only Locals and Fields have accesses for now.
 457     if !matches!(def, Definition::Local(_) | Definition::Field(_)) {
 458         return None;
 459     }
 460
 461     let mode = name_ref.syntax().ancestors().find_map(|node| {
 462         match_ast! {
 463             match (node) {
 464                 ast::BinExpr(expr) => {
 465                     if expr.op_kind()?.is_assignment() {
 466                         // If the variable or field ends on the LHS's end then it's a Write (covers fields and locals).
 467                         // FIXME: This is not terribly accurate.
 468                         if let Some(lhs) = expr.lhs() {
 469                             if lhs.syntax().text_range().end() == name_ref.syntax().text_range().end() {
 470                                 return Some(ReferenceAccess::Write);
 471                             }
 472                         }
 473                     }
 474                     Some(ReferenceAccess::Read)
 475                 },
 476                 _ => None
 477             }
 478         }
 479     });
 480
 481     // Default Locals and Fields to read
 482     mode.or(Some(ReferenceAccess::Read))
 483 }