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, SourceDatabase, SourceDatabaseExt};
  10 use hir::{
  11     DefWithBody, HasAttrs, HasSource, InFile, ModuleDef, ModuleSource, Semantics, Visibility,
  12 };
  13 use once_cell::unsync::Lazy;
  14 use rustc_hash::FxHashMap;
  15 use syntax::{ast, match_ast, AstNode, TextRange, TextSize};
  16
  17 use crate::{
  18     defs::{Definition, NameClass, NameRefClass},
  19     RootDatabase,
  20 };
  21
  22 #[derive(Debug, Default, Clone)]
  23 pub struct UsageSearchResult {
  24     pub references: FxHashMap<FileId, Vec<FileReference>>,
  25 }
  26
  27 impl UsageSearchResult {
  28     pub fn is_empty(&self) -> bool {
  29         self.references.is_empty()
  30     }
  31
  32     pub fn len(&self) -> usize {
  33         self.references.len()
  34     }
  35
  36     pub fn iter(&self) -> impl Iterator<Item = (&FileId, &Vec<FileReference>)> + '_ {
  37         self.references.iter()
  38     }
  39
  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 })
  43         })
  44     }
  45 }
  46
  47 impl IntoIterator for UsageSearchResult {
  48     type Item = (FileId, Vec<FileReference>);
  49     type IntoIter = <FxHashMap<FileId, Vec<FileReference>> as IntoIterator>::IntoIter;
  50
  51     fn into_iter(self) -> Self::IntoIter {
  52         self.references.into_iter()
  53     }
  54 }
  55
  56 #[derive(Debug, Clone)]
  57 pub struct FileReference {
  58     pub range: TextRange,
  59     pub name: ast::NameLike,
  60     pub access: Option<ReferenceAccess>,
  61 }
  62
  63 #[derive(Debug, Copy, Clone, PartialEq)]
  64 pub enum ReferenceAccess {
  65     Read,
  66     Write,
  67 }
  68
  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>>,
  75 }
  76
  77 impl SearchScope {
  78     fn new(entries: FxHashMap<FileId, Option<TextRange>>) -> SearchScope {
  79         SearchScope { entries }
  80     }
  81
  82     fn crate_graph(db: &RootDatabase) -> SearchScope {
  83         let mut entries = FxHashMap::default();
  84
  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)));
  91         }
  92         SearchScope { entries }
  93     }
  94
  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)));
 102         }
 103         SearchScope { entries }
 104     }
 105
 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);
 110         SearchScope {
 111             entries: source_root.iter().map(|id| (id, None)).collect::<FxHashMap<_, _>>(),
 112         }
 113     }
 114
 115     fn module(db: &RootDatabase, module: hir::Module) -> SearchScope {
 116         let mut entries = FxHashMap::default();
 117
 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);
 123             match src.value {
 124                 ModuleSource::Module(m) => {
 125                     if is_first {
 126                         let range = Some(m.syntax().text_range());
 127                         entries.insert(file_id, range);
 128                     } else {
 129                         // We have already added the enclosing file to the search scope,
 130                         // so do nothing.
 131                     }
 132                 }
 133                 ModuleSource::BlockExpr(b) => {
 134                     if is_first {
 135                         let range = Some(b.syntax().text_range());
 136                         entries.insert(file_id, range);
 137                     } else {
 138                         // We have already added the enclosing file to the search scope,
 139                         // so do nothing.
 140                     }
 141                 }
 142                 ModuleSource::SourceFile(_) => {
 143                     entries.insert(file_id, None);
 144                 }
 145             };
 146             is_first = false;
 147             to_visit.extend(module.children(db));
 148         }
 149         SearchScope { entries }
 150     }
 151
 152     pub fn empty() -> SearchScope {
 153         SearchScope::new(FxHashMap::default())
 154     }
 155
 156     pub fn single_file(file: FileId) -> SearchScope {
 157         SearchScope::new(std::iter::once((file, None)).collect())
 158     }
 159
 160     pub fn file_range(range: FileRange) -> SearchScope {
 161         SearchScope::new(std::iter::once((range.file_id, Some(range.range))).collect())
 162     }
 163
 164     pub fn files(files: &[FileId]) -> SearchScope {
 165         SearchScope::new(files.iter().map(|f| (*f, None)).collect())
 166     }
 167
 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)
 172         }
 173
 174         let res = small
 175             .iter()
 176             .filter_map(|(file_id, r1)| {
 177                 let r2 = large.get(file_id)?;
 178                 let r = intersect_ranges(*r1, *r2)?;
 179                 Some((*file_id, r))
 180             })
 181             .collect();
 182
 183         return SearchScope::new(res);
 184
 185         fn intersect_ranges(
 186             r1: Option<TextRange>,
 187             r2: Option<TextRange>,
 188         ) -> Option<Option<TextRange>> {
 189             match (r1, r2) {
 190                 (None, r) | (r, None) => Some(r),
 191                 (Some(r1), Some(r2)) => {
 192                     let r = r1.intersect(r2)?;
 193                     Some(Some(r))
 194                 }
 195             }
 196         }
 197     }
 198 }
 199
 200 impl IntoIterator for SearchScope {
 201     type Item = (FileId, Option<TextRange>);
 202     type IntoIter = std::collections::hash_map::IntoIter<FileId, Option<TextRange>>;
 203
 204     fn into_iter(self) -> Self::IntoIter {
 205         self.entries.into_iter()
 206     }
 207 }
 208
 209 impl Definition {
 210     fn search_scope(&self, db: &RootDatabase) -> SearchScope {
 211         let _p = profile::span("search_scope");
 212
 213         if let Definition::ModuleDef(hir::ModuleDef::BuiltinType(_)) = self {
 214             return SearchScope::crate_graph(db);
 215         }
 216
 217         let module = match self.module(db) {
 218             Some(it) => it,
 219             None => return SearchScope::empty(),
 220         };
 221         let InFile { file_id, value: module_source } = module.definition_source(db);
 222         let file_id = file_id.original_file(db);
 223
 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()),
 229             };
 230             return match range {
 231                 Some(range) => SearchScope::file_range(FileRange { file_id, range }),
 232                 None => SearchScope::single_file(file_id),
 233             };
 234         }
 235
 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())
 240                 }
 241                 hir::GenericDef::Adt(it) => match it {
 242                     hir::Adt::Struct(it) => {
 243                         it.source(db).map(|src| src.value.syntax().text_range())
 244                     }
 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()),
 247                 },
 248                 hir::GenericDef::Trait(it) => {
 249                     it.source(db).map(|src| src.value.syntax().text_range())
 250                 }
 251                 hir::GenericDef::TypeAlias(it) => {
 252                     it.source(db).map(|src| src.value.syntax().text_range())
 253                 }
 254                 hir::GenericDef::Impl(it) => {
 255                     it.source(db).map(|src| src.value.syntax().text_range())
 256                 }
 257                 hir::GenericDef::Variant(it) => {
 258                     it.source(db).map(|src| src.value.syntax().text_range())
 259                 }
 260                 hir::GenericDef::Const(it) => {
 261                     it.source(db).map(|src| src.value.syntax().text_range())
 262                 }
 263             };
 264             return match range {
 265                 Some(range) => SearchScope::file_range(FileRange { file_id, range }),
 266                 None => SearchScope::single_file(file_id),
 267             };
 268         }
 269
 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())
 274                 } else {
 275                     SearchScope::krate(db, module.krate())
 276                 };
 277             }
 278         }
 279
 280         let vis = self.visibility(db);
 281         if let Some(Visibility::Public) = vis {
 282             return SearchScope::reverse_dependencies(db, module.krate());
 283         }
 284         if let Some(Visibility::Module(module)) = vis {
 285             return SearchScope::module(db, module.into());
 286         }
 287
 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,
 292         };
 293         match range {
 294             Some(range) => SearchScope::file_range(FileRange { file_id, range }),
 295             None => SearchScope::single_file(file_id),
 296         }
 297     }
 298
 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 }
 301     }
 302 }
 303
 304 pub struct FindUsages<'a> {
 305     def: &'a Definition,
 306     sema: &'a Semantics<'a, RootDatabase>,
 307     scope: Option<SearchScope>,
 308     include_self_kw_refs: bool,
 309 }
 310
 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;
 314         self
 315     }
 316
 317     pub fn in_scope(self, scope: SearchScope) -> FindUsages<'a> {
 318         self.set_scope(Some(scope))
 319     }
 320
 321     pub fn set_scope(mut self, scope: Option<SearchScope>) -> FindUsages<'a> {
 322         assert!(self.scope.is_none());
 323         self.scope = scope;
 324         self
 325     }
 326
 327     pub fn at_least_one(self) -> bool {
 328         let mut found = false;
 329         self.search(&mut |_, _| {
 330             found = true;
 331             true
 332         });
 333         found
 334     }
 335
 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);
 340             false
 341         });
 342         res
 343     }
 344
 345     fn search(self, sink: &mut dyn FnMut(FileId, FileReference) -> bool) {
 346         let _p = profile::span("FindUsages:search");
 347         let sema = self.sema;
 348
 349         let search_scope = {
 350             let base = self.def.search_scope(sema.db);
 351             match &self.scope {
 352                 None => base,
 353                 Some(scope) => base.intersection(scope),
 354             }
 355         };
 356
 357         let name = match self.def.name(sema.db) {
 358             Some(it) => it.to_string(),
 359             None => return,
 360         };
 361
 362         let pat = name.as_str();
 363         let search_for_self = self.include_self_kw_refs;
 364
 365         for (file_id, search_range) in search_scope {
 366             let text = sema.db.file_text(file_id);
 367             let search_range =
 368                 search_range.unwrap_or_else(|| TextRange::up_to(TextSize::of(text.as_str())));
 369
 370             let tree = Lazy::new(|| sema.parse(file_id).syntax().clone());
 371
 372             let mut handle_match = |idx: usize| -> bool {
 373                 let offset: TextSize = idx.try_into().unwrap();
 374                 if !search_range.contains_inclusive(offset) {
 375                     return false;
 376                 }
 377
 378                 if let Some(name) = sema.find_node_at_offset_with_descend(&tree, offset) {
 379                     match name {
 380                         ast::NameLike::NameRef(name_ref) => {
 381                             if self.found_name_ref(&name_ref, sink) {
 382                                 return true;
 383                             }
 384                         }
 385                         ast::NameLike::Name(name) => {
 386                             if self.found_name(&name, sink) {
 387                                 return true;
 388                             }
 389                         }
 390                         ast::NameLike::Lifetime(lifetime) => {
 391                             if self.found_lifetime(&lifetime, sink) {
 392                                 return true;
 393                             }
 394                         }
 395                     }
 396                 }
 397
 398                 return false;
 399             };
 400
 401             for (idx, _) in text.match_indices(pat) {
 402                 if handle_match(idx) {
 403                     return;
 404                 }
 405             }
 406
 407             if search_for_self {
 408                 for (idx, _) in text.match_indices("Self") {
 409                     if handle_match(idx) {
 410                         return;
 411                     }
 412                 }
 413             }
 414         }
 415     }
 416
 417     fn found_lifetime(
 418         &self,
 419         lifetime: &ast::Lifetime,
 420         sink: &mut dyn FnMut(FileId, FileReference) -> bool,
 421     ) -> 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 {
 426                     range,
 427                     name: ast::NameLike::Lifetime(lifetime.clone()),
 428                     access: None,
 429                 };
 430                 sink(file_id, reference)
 431             }
 432             _ => false, // not a usage
 433         }
 434     }
 435
 436     fn found_name_ref(
 437         &self,
 438         name_ref: &ast::NameRef,
 439         sink: &mut dyn FnMut(FileId, FileReference) -> bool,
 440     ) -> 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 {
 445                     range,
 446                     name: ast::NameLike::NameRef(name_ref.clone()),
 447                     access: reference_access(&def, &name_ref),
 448                 };
 449                 sink(file_id, reference)
 450             }
 451             Some(NameRefClass::Definition(Definition::SelfType(impl_))) => {
 452                 let ty = impl_.self_ty(self.sema.db);
 453
 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 {
 459                             range,
 460                             name: ast::NameLike::NameRef(name_ref.clone()),
 461                             access: None,
 462                         };
 463                         return sink(file_id, reference);
 464                     }
 465                 }
 466
 467                 false
 468             }
 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 {
 473                         range,
 474                         name: ast::NameLike::NameRef(name_ref.clone()),
 475                         access: reference_access(&field, &name_ref),
 476                     },
 477                     Definition::Local(l) if &local == l => FileReference {
 478                         range,
 479                         name: ast::NameLike::NameRef(name_ref.clone()),
 480                         access: reference_access(&Definition::Local(local), &name_ref),
 481                     },
 482                     _ => return false, // not a usage
 483                 };
 484                 sink(file_id, reference)
 485             }
 486             _ => false, // not a usage
 487         }
 488     }
 489
 490     fn found_name(
 491         &self,
 492         name: &ast::Name,
 493         sink: &mut dyn FnMut(FileId, FileReference) -> bool,
 494     ) -> bool {
 495         match NameClass::classify(self.sema, name) {
 496             Some(NameClass::PatFieldShorthand { local_def: _, field_ref })
 497                 if matches!(
 498                     self.def, Definition::Field(_) if &field_ref == self.def
 499                 ) =>
 500             {
 501                 let FileRange { file_id, range } = self.sema.original_range(name.syntax());
 502                 let reference = FileReference {
 503                     range,
 504                     name: ast::NameLike::Name(name.clone()),
 505                     // FIXME: mutable patterns should have `Write` access
 506                     access: Some(ReferenceAccess::Read),
 507                 };
 508                 sink(file_id, reference)
 509             }
 510             Some(NameClass::ConstReference(def)) if *self.def == def => {
 511                 let FileRange { file_id, range } = self.sema.original_range(name.syntax());
 512                 let reference =
 513                     FileReference { range, name: ast::NameLike::Name(name.clone()), access: None };
 514                 sink(file_id, reference)
 515             }
 516             _ => false, // not a usage
 517         }
 518     }
 519 }
 520
 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(_)) {
 524         return None;
 525     }
 526
 527     let mode = name_ref.syntax().ancestors().find_map(|node| {
 528         match_ast! {
 529             match (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);
 537                             }
 538                         }
 539                     }
 540                     Some(ReferenceAccess::Read)
 541                 },
 542                 _ => None
 543             }
 544         }
 545     });
 546
 547     // Default Locals and Fields to read
 548     mode.or(Some(ReferenceAccess::Read))
 549 }