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