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