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