crates/ide_ssr/src/search.rs

   1 //! Searching for matches.
   2
   3 use crate::{
   4     matching,
   5     resolving::{ResolvedPath, ResolvedPattern, ResolvedRule},
   6     Match, MatchFinder,
   7 };
   8 use ide_db::{
   9     base_db::{FileId, FileRange},
  10     defs::Definition,
  11     search::{SearchScope, UsageSearchResult},
  12 };
  13 use rustc_hash::FxHashSet;
  14 use syntax::{ast, AstNode, SyntaxKind, SyntaxNode};
  15
  16 /// A cache for the results of find_usages. This is for when we have multiple patterns that have the
  17 /// same path. e.g. if the pattern was `foo::Bar` that can parse as a path, an expression, a type
  18 /// and as a pattern. In each, the usages of `foo::Bar` are the same and we'd like to avoid finding
  19 /// them more than once.
  20 #[derive(Default)]
  21 pub(crate) struct UsageCache {
  22     usages: Vec<(Definition, UsageSearchResult)>,
  23 }
  24
  25 impl<'db> MatchFinder<'db> {
  26     /// Adds all matches for `rule` to `matches_out`. Matches may overlap in ways that make
  27     /// replacement impossible, so further processing is required in order to properly nest matches
  28     /// and remove overlapping matches. This is done in the `nesting` module.
  29     pub(crate) fn find_matches_for_rule(
  30         &self,
  31         rule: &ResolvedRule,
  32         usage_cache: &mut UsageCache,
  33         matches_out: &mut Vec<Match>,
  34     ) {
  35         if rule.pattern.contains_self {
  36             // If the pattern contains `self` we restrict the scope of the search to just the
  37             // current method. No other method can reference the same `self`. This makes the
  38             // behavior of `self` consistent with other variables.
  39             if let Some(current_function) = self.resolution_scope.current_function() {
  40                 self.slow_scan_node(&current_function, rule, &None, matches_out);
  41             }
  42             return;
  43         }
  44         if pick_path_for_usages(&rule.pattern).is_none() {
  45             self.slow_scan(rule, matches_out);
  46             return;
  47         }
  48         self.find_matches_for_pattern_tree(rule, &rule.pattern, usage_cache, matches_out);
  49     }
  50
  51     fn find_matches_for_pattern_tree(
  52         &self,
  53         rule: &ResolvedRule,
  54         pattern: &ResolvedPattern,
  55         usage_cache: &mut UsageCache,
  56         matches_out: &mut Vec<Match>,
  57     ) {
  58         if let Some(resolved_path) = pick_path_for_usages(pattern) {
  59             let definition: Definition = resolved_path.resolution.clone().into();
  60             for file_range in self.find_usages(usage_cache, definition).file_ranges() {
  61                 if let Some(node_to_match) = self.find_node_to_match(resolved_path, file_range) {
  62                     if !is_search_permitted_ancestors(&node_to_match) {
  63                         cov_mark::hit!(use_declaration_with_braces);
  64                         continue;
  65                     }
  66                     self.try_add_match(rule, &node_to_match, &None, matches_out);
  67                 }
  68             }
  69         }
  70     }
  71
  72     fn find_node_to_match(
  73         &self,
  74         resolved_path: &ResolvedPath,
  75         file_range: FileRange,
  76     ) -> Option<SyntaxNode> {
  77         let file = self.sema.parse(file_range.file_id);
  78         let depth = resolved_path.depth as usize;
  79         let offset = file_range.range.start();
  80         if let Some(path) =
  81             self.sema.find_node_at_offset_with_descend::<ast::Path>(file.syntax(), offset)
  82         {
  83             self.sema.ancestors_with_macros(path.syntax().clone()).skip(depth).next()
  84         } else if let Some(path) =
  85             self.sema.find_node_at_offset_with_descend::<ast::MethodCallExpr>(file.syntax(), offset)
  86         {
  87             // If the pattern contained a path and we found a reference to that path that wasn't
  88             // itself a path, but was a method call, then we need to adjust how far up to try
  89             // matching by how deep the path was within a CallExpr. The structure would have been
  90             // CallExpr, PathExpr, Path - i.e. a depth offset of 2. We don't need to check if the
  91             // path was part of a CallExpr because if it wasn't then all that will happen is we'll
  92             // fail to match, which is the desired behavior.
  93             const PATH_DEPTH_IN_CALL_EXPR: usize = 2;
  94             if depth < PATH_DEPTH_IN_CALL_EXPR {
  95                 return None;
  96             }
  97             self.sema
  98                 .ancestors_with_macros(path.syntax().clone())
  99                 .skip(depth - PATH_DEPTH_IN_CALL_EXPR)
 100                 .next()
 101         } else {
 102             None
 103         }
 104     }
 105
 106     fn find_usages<'a>(
 107         &self,
 108         usage_cache: &'a mut UsageCache,
 109         definition: Definition,
 110     ) -> &'a UsageSearchResult {
 111         // Logically if a lookup succeeds we should just return it. Unfortunately returning it would
 112         // extend the lifetime of the borrow, then we wouldn't be able to do the insertion on a
 113         // cache miss. This is a limitation of NLL and is fixed with Polonius. For now we do two
 114         // lookups in the case of a cache hit.
 115         if usage_cache.find(&definition).is_none() {
 116             let usages = definition.usages(&self.sema).in_scope(self.search_scope()).all();
 117             usage_cache.usages.push((definition, usages));
 118             return &usage_cache.usages.last().unwrap().1;
 119         }
 120         usage_cache.find(&definition).unwrap()
 121     }
 122
 123     /// Returns the scope within which we want to search. We don't want un unrestricted search
 124     /// scope, since we don't want to find references in external dependencies.
 125     fn search_scope(&self) -> SearchScope {
 126         // FIXME: We should ideally have a test that checks that we edit local roots and not library
 127         // roots. This probably would require some changes to fixtures, since currently everything
 128         // seems to get put into a single source root.
 129         let mut files = Vec::new();
 130         self.search_files_do(|file_id| {
 131             files.push(file_id);
 132         });
 133         SearchScope::files(&files)
 134     }
 135
 136     fn slow_scan(&self, rule: &ResolvedRule, matches_out: &mut Vec<Match>) {
 137         self.search_files_do(|file_id| {
 138             let file = self.sema.parse(file_id);
 139             let code = file.syntax();
 140             self.slow_scan_node(code, rule, &None, matches_out);
 141         })
 142     }
 143
 144     fn search_files_do(&self, mut callback: impl FnMut(FileId)) {
 145         if self.restrict_ranges.is_empty() {
 146             // Unrestricted search.
 147             use ide_db::base_db::SourceDatabaseExt;
 148             use ide_db::symbol_index::SymbolsDatabase;
 149             for &root in self.sema.db.local_roots().iter() {
 150                 let sr = self.sema.db.source_root(root);
 151                 for file_id in sr.iter() {
 152                     callback(file_id);
 153                 }
 154             }
 155         } else {
 156             // Search is restricted, deduplicate file IDs (generally only one).
 157             let mut files = FxHashSet::default();
 158             for range in &self.restrict_ranges {
 159                 if files.insert(range.file_id) {
 160                     callback(range.file_id);
 161                 }
 162             }
 163         }
 164     }
 165
 166     fn slow_scan_node(
 167         &self,
 168         code: &SyntaxNode,
 169         rule: &ResolvedRule,
 170         restrict_range: &Option<FileRange>,
 171         matches_out: &mut Vec<Match>,
 172     ) {
 173         if !is_search_permitted(code) {
 174             return;
 175         }
 176         self.try_add_match(rule, code, restrict_range, matches_out);
 177         // If we've got a macro call, we already tried matching it pre-expansion, which is the only
 178         // way to match the whole macro, now try expanding it and matching the expansion.
 179         if let Some(macro_call) = ast::MacroCall::cast(code.clone()) {
 180             if let Some(expanded) = self.sema.expand(&macro_call) {
 181                 if let Some(tt) = macro_call.token_tree() {
 182                     // When matching within a macro expansion, we only want to allow matches of
 183                     // nodes that originated entirely from within the token tree of the macro call.
 184                     // i.e. we don't want to match something that came from the macro itself.
 185                     self.slow_scan_node(
 186                         &expanded,
 187                         rule,
 188                         &Some(self.sema.original_range(tt.syntax())),
 189                         matches_out,
 190                     );
 191                 }
 192             }
 193         }
 194         for child in code.children() {
 195             self.slow_scan_node(&child, rule, restrict_range, matches_out);
 196         }
 197     }
 198
 199     fn try_add_match(
 200         &self,
 201         rule: &ResolvedRule,
 202         code: &SyntaxNode,
 203         restrict_range: &Option<FileRange>,
 204         matches_out: &mut Vec<Match>,
 205     ) {
 206         if !self.within_range_restrictions(code) {
 207             cov_mark::hit!(replace_nonpath_within_selection);
 208             return;
 209         }
 210         if let Ok(m) = matching::get_match(false, rule, code, restrict_range, &self.sema) {
 211             matches_out.push(m);
 212         }
 213     }
 214
 215     /// Returns whether `code` is within one of our range restrictions if we have any. No range
 216     /// restrictions is considered unrestricted and always returns true.
 217     fn within_range_restrictions(&self, code: &SyntaxNode) -> bool {
 218         if self.restrict_ranges.is_empty() {
 219             // There is no range restriction.
 220             return true;
 221         }
 222         let node_range = self.sema.original_range(code);
 223         for range in &self.restrict_ranges {
 224             if range.file_id == node_range.file_id && range.range.contains_range(node_range.range) {
 225                 return true;
 226             }
 227         }
 228         false
 229     }
 230 }
 231
 232 /// Returns whether we support matching within `node` and all of its ancestors.
 233 fn is_search_permitted_ancestors(node: &SyntaxNode) -> bool {
 234     if let Some(parent) = node.parent() {
 235         if !is_search_permitted_ancestors(&parent) {
 236             return false;
 237         }
 238     }
 239     is_search_permitted(node)
 240 }
 241
 242 /// Returns whether we support matching within this kind of node.
 243 fn is_search_permitted(node: &SyntaxNode) -> bool {
 244     // FIXME: Properly handle use declarations. At the moment, if our search pattern is `foo::bar`
 245     // and the code is `use foo::{baz, bar}`, we'll match `bar`, since it resolves to `foo::bar`.
 246     // However we'll then replace just the part we matched `bar`. We probably need to instead remove
 247     // `bar` and insert a new use declaration.
 248     node.kind() != SyntaxKind::USE
 249 }
 250
 251 impl UsageCache {
 252     fn find(&mut self, definition: &Definition) -> Option<&UsageSearchResult> {
 253         // We expect a very small number of cache entries (generally 1), so a linear scan should be
 254         // fast enough and avoids the need to implement Hash for Definition.
 255         for (d, refs) in &self.usages {
 256             if d == definition {
 257                 return Some(refs);
 258             }
 259         }
 260         None
 261     }
 262 }
 263
 264 /// Returns a path that's suitable for path resolution. We exclude builtin types, since they aren't
 265 /// something that we can find references to. We then somewhat arbitrarily pick the path that is the
 266 /// longest as this is hopefully more likely to be less common, making it faster to find.
 267 fn pick_path_for_usages(pattern: &ResolvedPattern) -> Option<&ResolvedPath> {
 268     // FIXME: Take the scope of the resolved path into account. e.g. if there are any paths that are
 269     // private to the current module, then we definitely would want to pick them over say a path
 270     // from std. Possibly we should go further than this and intersect the search scopes for all
 271     // resolved paths then search only in that scope.
 272     pattern
 273         .resolved_paths
 274         .iter()
 275         .filter(|(_, p)| {
 276             !matches!(p.resolution, hir::PathResolution::Def(hir::ModuleDef::BuiltinType(_)))
 277         })
 278         .map(|(node, resolved)| (node.text().len(), resolved))
 279         .max_by(|(a, _), (b, _)| a.cmp(b))
 280         .map(|(_, resolved)| resolved)
 281 }