diff options
Diffstat (limited to 'crates/ra_ssr/src/search.rs')
-rw-r--r-- | crates/ra_ssr/src/search.rs | 282 |
1 files changed, 0 insertions, 282 deletions
diff --git a/crates/ra_ssr/src/search.rs b/crates/ra_ssr/src/search.rs deleted file mode 100644 index 8509cfa4d..000000000 --- a/crates/ra_ssr/src/search.rs +++ /dev/null | |||
@@ -1,282 +0,0 @@ | |||
1 | //! Searching for matches. | ||
2 | |||
3 | use crate::{ | ||
4 | matching, | ||
5 | resolving::{ResolvedPath, ResolvedPattern, ResolvedRule}, | ||
6 | Match, MatchFinder, | ||
7 | }; | ||
8 | use base_db::{FileId, FileRange}; | ||
9 | use ide_db::{ | ||
10 | defs::Definition, | ||
11 | search::{Reference, SearchScope}, | ||
12 | }; | ||
13 | use rustc_hash::FxHashSet; | ||
14 | use syntax::{ast, AstNode, SyntaxKind, SyntaxNode}; | ||
15 | use 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)] | ||
22 | pub(crate) struct UsageCache { | ||
23 | usages: Vec<(Definition, Vec<Reference>)>, | ||
24 | } | ||
25 | |||
26 | impl<'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(¤t_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(¯o_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. | ||
234 | fn 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. | ||
244 | fn 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 | |||
252 | impl 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. | ||
268 | fn 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 | } | ||