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                 for node_to_match in self.find_nodes_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_nodes_to_match(
  73         &self,
  74         resolved_path: &ResolvedPath,
  75         file_range: FileRange,
  76     ) -> Vec<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
  81         let mut paths = self
  82             .sema
  83             .find_nodes_at_offset_with_descend::<ast::Path>(file.syntax(), offset)
  84             .peekable();
  85
  86         if paths.peek().is_some() {
  87             paths
  88                 .filter_map(|path| {
  89                     self.sema.ancestors_with_macros(path.syntax().clone()).nth(depth)
  90                 })
  91                 .collect::<Vec<_>>()
  92         } else {
  93             self.sema
  94                 .find_nodes_at_offset_with_descend::<ast::MethodCallExpr>(file.syntax(), offset)
  95                 .filter_map(|path| {
  96                     // If the pattern contained a path and we found a reference to that path that wasn't
  97                     // itself a path, but was a method call, then we need to adjust how far up to try
  98                     // matching by how deep the path was within a CallExpr. The structure would have been
  99                     // CallExpr, PathExpr, Path - i.e. a depth offset of 2. We don't need to check if the
 100                     // path was part of a CallExpr because if it wasn't then all that will happen is we'll
 101                     // fail to match, which is the desired behavior.
 102                     const PATH_DEPTH_IN_CALL_EXPR: usize = 2;
 103                     if depth < PATH_DEPTH_IN_CALL_EXPR {
 104                         return None;
 105                     }
 106                     self.sema
 107                         .ancestors_with_macros(path.syntax().clone())
 108                         .nth(depth - PATH_DEPTH_IN_CALL_EXPR)
 109                 })
 110                 .collect::<Vec<_>>()
 111         }
 112     }
 113
 114     fn find_usages<'a>(
 115         &self,
 116         usage_cache: &'a mut UsageCache,
 117         definition: Definition,
 118     ) -> &'a UsageSearchResult {
 119         // Logically if a lookup succeeds we should just return it. Unfortunately returning it would
 120         // extend the lifetime of the borrow, then we wouldn't be able to do the insertion on a
 121         // cache miss. This is a limitation of NLL and is fixed with Polonius. For now we do two
 122         // lookups in the case of a cache hit.
 123         if usage_cache.find(&definition).is_none() {
 124             let usages = definition.usages(&self.sema).in_scope(self.search_scope()).all();
 125             usage_cache.usages.push((definition, usages));
 126             return &usage_cache.usages.last().unwrap().1;
 127         }
 128         usage_cache.find(&definition).unwrap()
 129     }
 130
 131     /// Returns the scope within which we want to search. We don't want un unrestricted search
 132     /// scope, since we don't want to find references in external dependencies.
 133     fn search_scope(&self) -> SearchScope {
 134         // FIXME: We should ideally have a test that checks that we edit local roots and not library
 135         // roots. This probably would require some changes to fixtures, since currently everything
 136         // seems to get put into a single source root.
 137         let mut files = Vec::new();
 138         self.search_files_do(|file_id| {
 139             files.push(file_id);
 140         });
 141         SearchScope::files(&files)
 142     }
 143
 144     fn slow_scan(&self, rule: &ResolvedRule, matches_out: &mut Vec<Match>) {
 145         self.search_files_do(|file_id| {
 146             let file = self.sema.parse(file_id);
 147             let code = file.syntax();
 148             self.slow_scan_node(code, rule, &None, matches_out);
 149         })
 150     }
 151
 152     fn search_files_do(&self, mut callback: impl FnMut(FileId)) {
 153         if self.restrict_ranges.is_empty() {
 154             // Unrestricted search.
 155             use ide_db::base_db::SourceDatabaseExt;
 156             use ide_db::symbol_index::SymbolsDatabase;
 157             for &root in self.sema.db.local_roots().iter() {
 158                 let sr = self.sema.db.source_root(root);
 159                 for file_id in sr.iter() {
 160                     callback(file_id);
 161                 }
 162             }
 163         } else {
 164             // Search is restricted, deduplicate file IDs (generally only one).
 165             let mut files = FxHashSet::default();
 166             for range in &self.restrict_ranges {
 167                 if files.insert(range.file_id) {
 168                     callback(range.file_id);
 169                 }
 170             }
 171         }
 172     }
 173
 174     fn slow_scan_node(
 175         &self,
 176         code: &SyntaxNode,
 177         rule: &ResolvedRule,
 178         restrict_range: &Option<FileRange>,
 179         matches_out: &mut Vec<Match>,
 180     ) {
 181         if !is_search_permitted(code) {
 182             return;
 183         }
 184         self.try_add_match(rule, code, restrict_range, matches_out);
 185         // If we've got a macro call, we already tried matching it pre-expansion, which is the only
 186         // way to match the whole macro, now try expanding it and matching the expansion.
 187         if let Some(macro_call) = ast::MacroCall::cast(code.clone()) {
 188             if let Some(expanded) = self.sema.expand(&macro_call) {
 189                 if let Some(tt) = macro_call.token_tree() {
 190                     // When matching within a macro expansion, we only want to allow matches of
 191                     // nodes that originated entirely from within the token tree of the macro call.
 192                     // i.e. we don't want to match something that came from the macro itself.
 193                     self.slow_scan_node(
 194                         &expanded,
 195                         rule,
 196                         &Some(self.sema.original_range(tt.syntax())),
 197                         matches_out,
 198                     );
 199                 }
 200             }
 201         }
 202         for child in code.children() {
 203             self.slow_scan_node(&child, rule, restrict_range, matches_out);
 204         }
 205     }
 206
 207     fn try_add_match(
 208         &self,
 209         rule: &ResolvedRule,
 210         code: &SyntaxNode,
 211         restrict_range: &Option<FileRange>,
 212         matches_out: &mut Vec<Match>,
 213     ) {
 214         if !self.within_range_restrictions(code) {
 215             cov_mark::hit!(replace_nonpath_within_selection);
 216             return;
 217         }
 218         if let Ok(m) = matching::get_match(false, rule, code, restrict_range, &self.sema) {
 219             matches_out.push(m);
 220         }
 221     }
 222
 223     /// Returns whether `code` is within one of our range restrictions if we have any. No range
 224     /// restrictions is considered unrestricted and always returns true.
 225     fn within_range_restrictions(&self, code: &SyntaxNode) -> bool {
 226         if self.restrict_ranges.is_empty() {
 227             // There is no range restriction.
 228             return true;
 229         }
 230         let node_range = self.sema.original_range(code);
 231         for range in &self.restrict_ranges {
 232             if range.file_id == node_range.file_id && range.range.contains_range(node_range.range) {
 233                 return true;
 234             }
 235         }
 236         false
 237     }
 238 }
 239
 240 /// Returns whether we support matching within `node` and all of its ancestors.
 241 fn is_search_permitted_ancestors(node: &SyntaxNode) -> bool {
 242     if let Some(parent) = node.parent() {
 243         if !is_search_permitted_ancestors(&parent) {
 244             return false;
 245         }
 246     }
 247     is_search_permitted(node)
 248 }
 249
 250 /// Returns whether we support matching within this kind of node.
 251 fn is_search_permitted(node: &SyntaxNode) -> bool {
 252     // FIXME: Properly handle use declarations. At the moment, if our search pattern is `foo::bar`
 253     // and the code is `use foo::{baz, bar}`, we'll match `bar`, since it resolves to `foo::bar`.
 254     // However we'll then replace just the part we matched `bar`. We probably need to instead remove
 255     // `bar` and insert a new use declaration.
 256     node.kind() != SyntaxKind::USE
 257 }
 258
 259 impl UsageCache {
 260     fn find(&mut self, definition: &Definition) -> Option<&UsageSearchResult> {
 261         // We expect a very small number of cache entries (generally 1), so a linear scan should be
 262         // fast enough and avoids the need to implement Hash for Definition.
 263         for (d, refs) in &self.usages {
 264             if d == definition {
 265                 return Some(refs);
 266             }
 267         }
 268         None
 269     }
 270 }
 271
 272 /// Returns a path that's suitable for path resolution. We exclude builtin types, since they aren't
 273 /// something that we can find references to. We then somewhat arbitrarily pick the path that is the
 274 /// longest as this is hopefully more likely to be less common, making it faster to find.
 275 fn pick_path_for_usages(pattern: &ResolvedPattern) -> Option<&ResolvedPath> {
 276     // FIXME: Take the scope of the resolved path into account. e.g. if there are any paths that are
 277     // private to the current module, then we definitely would want to pick them over say a path
 278     // from std. Possibly we should go further than this and intersect the search scopes for all
 279     // resolved paths then search only in that scope.
 280     pattern
 281         .resolved_paths
 282         .iter()
 283         .filter(|(_, p)| {
 284             !matches!(p.resolution, hir::PathResolution::Def(hir::ModuleDef::BuiltinType(_)))
 285         })
 286         .map(|(node, resolved)| (node.text().len(), resolved))
 287         .max_by(|(a, _), (b, _)| a.cmp(b))
 288         .map(|(_, resolved)| resolved)
 289 }