diff options
Diffstat (limited to 'crates/ra_ssr/src/search.rs')
-rw-r--r-- | crates/ra_ssr/src/search.rs | 232 |
1 files changed, 232 insertions, 0 deletions
diff --git a/crates/ra_ssr/src/search.rs b/crates/ra_ssr/src/search.rs new file mode 100644 index 000000000..bcf0f0468 --- /dev/null +++ b/crates/ra_ssr/src/search.rs | |||
@@ -0,0 +1,232 @@ | |||
1 | //! Searching for matches. | ||
2 | |||
3 | use crate::{ | ||
4 | matching, | ||
5 | resolving::{ResolvedPath, ResolvedPattern, ResolvedRule}, | ||
6 | Match, MatchFinder, | ||
7 | }; | ||
8 | use ra_db::FileRange; | ||
9 | use ra_ide_db::{ | ||
10 | defs::Definition, | ||
11 | search::{Reference, SearchScope}, | ||
12 | }; | ||
13 | use ra_syntax::{ast, AstNode, SyntaxKind, SyntaxNode}; | ||
14 | use test_utils::mark; | ||
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, Vec<Reference>)>, | ||
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 pick_path_for_usages(&rule.pattern).is_none() { | ||
36 | self.slow_scan(rule, matches_out); | ||
37 | return; | ||
38 | } | ||
39 | self.find_matches_for_pattern_tree(rule, &rule.pattern, usage_cache, matches_out); | ||
40 | } | ||
41 | |||
42 | fn find_matches_for_pattern_tree( | ||
43 | &self, | ||
44 | rule: &ResolvedRule, | ||
45 | pattern: &ResolvedPattern, | ||
46 | usage_cache: &mut UsageCache, | ||
47 | matches_out: &mut Vec<Match>, | ||
48 | ) { | ||
49 | if let Some(resolved_path) = pick_path_for_usages(pattern) { | ||
50 | let definition: Definition = resolved_path.resolution.clone().into(); | ||
51 | for reference in self.find_usages(usage_cache, definition) { | ||
52 | if let Some(node_to_match) = self.find_node_to_match(resolved_path, reference) { | ||
53 | if !is_search_permitted_ancestors(&node_to_match) { | ||
54 | mark::hit!(use_declaration_with_braces); | ||
55 | continue; | ||
56 | } | ||
57 | if let Ok(m) = | ||
58 | matching::get_match(false, rule, &node_to_match, &None, &self.sema) | ||
59 | { | ||
60 | matches_out.push(m); | ||
61 | } | ||
62 | } | ||
63 | } | ||
64 | } | ||
65 | } | ||
66 | |||
67 | fn find_node_to_match( | ||
68 | &self, | ||
69 | resolved_path: &ResolvedPath, | ||
70 | reference: &Reference, | ||
71 | ) -> Option<SyntaxNode> { | ||
72 | let file = self.sema.parse(reference.file_range.file_id); | ||
73 | let depth = resolved_path.depth as usize; | ||
74 | let offset = reference.file_range.range.start(); | ||
75 | if let Some(path) = | ||
76 | self.sema.find_node_at_offset_with_descend::<ast::Path>(file.syntax(), offset) | ||
77 | { | ||
78 | self.sema.ancestors_with_macros(path.syntax().clone()).skip(depth).next() | ||
79 | } else if let Some(path) = | ||
80 | self.sema.find_node_at_offset_with_descend::<ast::MethodCallExpr>(file.syntax(), offset) | ||
81 | { | ||
82 | // If the pattern contained a path and we found a reference to that path that wasn't | ||
83 | // itself a path, but was a method call, then we need to adjust how far up to try | ||
84 | // matching by how deep the path was within a CallExpr. The structure would have been | ||
85 | // CallExpr, PathExpr, Path - i.e. a depth offset of 2. We don't need to check if the | ||
86 | // path was part of a CallExpr because if it wasn't then all that will happen is we'll | ||
87 | // fail to match, which is the desired behavior. | ||
88 | const PATH_DEPTH_IN_CALL_EXPR: usize = 2; | ||
89 | if depth < PATH_DEPTH_IN_CALL_EXPR { | ||
90 | return None; | ||
91 | } | ||
92 | self.sema | ||
93 | .ancestors_with_macros(path.syntax().clone()) | ||
94 | .skip(depth - PATH_DEPTH_IN_CALL_EXPR) | ||
95 | .next() | ||
96 | } else { | ||
97 | None | ||
98 | } | ||
99 | } | ||
100 | |||
101 | fn find_usages<'a>( | ||
102 | &self, | ||
103 | usage_cache: &'a mut UsageCache, | ||
104 | definition: Definition, | ||
105 | ) -> &'a [Reference] { | ||
106 | // Logically if a lookup succeeds we should just return it. Unfortunately returning it would | ||
107 | // extend the lifetime of the borrow, then we wouldn't be able to do the insertion on a | ||
108 | // cache miss. This is a limitation of NLL and is fixed with Polonius. For now we do two | ||
109 | // lookups in the case of a cache hit. | ||
110 | if usage_cache.find(&definition).is_none() { | ||
111 | let usages = definition.find_usages(&self.sema, Some(self.search_scope())); | ||
112 | usage_cache.usages.push((definition, usages)); | ||
113 | return &usage_cache.usages.last().unwrap().1; | ||
114 | } | ||
115 | usage_cache.find(&definition).unwrap() | ||
116 | } | ||
117 | |||
118 | /// Returns the scope within which we want to search. We don't want un unrestricted search | ||
119 | /// scope, since we don't want to find references in external dependencies. | ||
120 | fn search_scope(&self) -> SearchScope { | ||
121 | // FIXME: We should ideally have a test that checks that we edit local roots and not library | ||
122 | // roots. This probably would require some changes to fixtures, since currently everything | ||
123 | // seems to get put into a single source root. | ||
124 | use ra_db::SourceDatabaseExt; | ||
125 | use ra_ide_db::symbol_index::SymbolsDatabase; | ||
126 | let mut files = Vec::new(); | ||
127 | for &root in self.sema.db.local_roots().iter() { | ||
128 | let sr = self.sema.db.source_root(root); | ||
129 | files.extend(sr.iter()); | ||
130 | } | ||
131 | SearchScope::files(&files) | ||
132 | } | ||
133 | |||
134 | fn slow_scan(&self, rule: &ResolvedRule, matches_out: &mut Vec<Match>) { | ||
135 | use ra_db::SourceDatabaseExt; | ||
136 | use ra_ide_db::symbol_index::SymbolsDatabase; | ||
137 | for &root in self.sema.db.local_roots().iter() { | ||
138 | let sr = self.sema.db.source_root(root); | ||
139 | for file_id in sr.iter() { | ||
140 | let file = self.sema.parse(file_id); | ||
141 | let code = file.syntax(); | ||
142 | self.slow_scan_node(code, rule, &None, matches_out); | ||
143 | } | ||
144 | } | ||
145 | } | ||
146 | |||
147 | fn slow_scan_node( | ||
148 | &self, | ||
149 | code: &SyntaxNode, | ||
150 | rule: &ResolvedRule, | ||
151 | restrict_range: &Option<FileRange>, | ||
152 | matches_out: &mut Vec<Match>, | ||
153 | ) { | ||
154 | if !is_search_permitted(code) { | ||
155 | return; | ||
156 | } | ||
157 | if let Ok(m) = matching::get_match(false, rule, &code, restrict_range, &self.sema) { | ||
158 | matches_out.push(m); | ||
159 | } | ||
160 | // If we've got a macro call, we already tried matching it pre-expansion, which is the only | ||
161 | // way to match the whole macro, now try expanding it and matching the expansion. | ||
162 | if let Some(macro_call) = ast::MacroCall::cast(code.clone()) { | ||
163 | if let Some(expanded) = self.sema.expand(¯o_call) { | ||
164 | if let Some(tt) = macro_call.token_tree() { | ||
165 | // When matching within a macro expansion, we only want to allow matches of | ||
166 | // nodes that originated entirely from within the token tree of the macro call. | ||
167 | // i.e. we don't want to match something that came from the macro itself. | ||
168 | self.slow_scan_node( | ||
169 | &expanded, | ||
170 | rule, | ||
171 | &Some(self.sema.original_range(tt.syntax())), | ||
172 | matches_out, | ||
173 | ); | ||
174 | } | ||
175 | } | ||
176 | } | ||
177 | for child in code.children() { | ||
178 | self.slow_scan_node(&child, rule, restrict_range, matches_out); | ||
179 | } | ||
180 | } | ||
181 | } | ||
182 | |||
183 | /// Returns whether we support matching within `node` and all of its ancestors. | ||
184 | fn is_search_permitted_ancestors(node: &SyntaxNode) -> bool { | ||
185 | if let Some(parent) = node.parent() { | ||
186 | if !is_search_permitted_ancestors(&parent) { | ||
187 | return false; | ||
188 | } | ||
189 | } | ||
190 | is_search_permitted(node) | ||
191 | } | ||
192 | |||
193 | /// Returns whether we support matching within this kind of node. | ||
194 | fn is_search_permitted(node: &SyntaxNode) -> bool { | ||
195 | // FIXME: Properly handle use declarations. At the moment, if our search pattern is `foo::bar` | ||
196 | // and the code is `use foo::{baz, bar}`, we'll match `bar`, since it resolves to `foo::bar`. | ||
197 | // However we'll then replace just the part we matched `bar`. We probably need to instead remove | ||
198 | // `bar` and insert a new use declaration. | ||
199 | node.kind() != SyntaxKind::USE_ITEM | ||
200 | } | ||
201 | |||
202 | impl UsageCache { | ||
203 | fn find(&mut self, definition: &Definition) -> Option<&[Reference]> { | ||
204 | // We expect a very small number of cache entries (generally 1), so a linear scan should be | ||
205 | // fast enough and avoids the need to implement Hash for Definition. | ||
206 | for (d, refs) in &self.usages { | ||
207 | if d == definition { | ||
208 | return Some(refs); | ||
209 | } | ||
210 | } | ||
211 | None | ||
212 | } | ||
213 | } | ||
214 | |||
215 | /// Returns a path that's suitable for path resolution. We exclude builtin types, since they aren't | ||
216 | /// something that we can find references to. We then somewhat arbitrarily pick the path that is the | ||
217 | /// longest as this is hopefully more likely to be less common, making it faster to find. | ||
218 | fn pick_path_for_usages(pattern: &ResolvedPattern) -> Option<&ResolvedPath> { | ||
219 | // FIXME: Take the scope of the resolved path into account. e.g. if there are any paths that are | ||
220 | // private to the current module, then we definitely would want to pick them over say a path | ||
221 | // from std. Possibly we should go further than this and intersect the search scopes for all | ||
222 | // resolved paths then search only in that scope. | ||
223 | pattern | ||
224 | .resolved_paths | ||
225 | .iter() | ||
226 | .filter(|(_, p)| { | ||
227 | !matches!(p.resolution, hir::PathResolution::Def(hir::ModuleDef::BuiltinType(_))) | ||
228 | }) | ||
229 | .map(|(node, resolved)| (node.text().len(), resolved)) | ||
230 | .max_by(|(a, _), (b, _)| a.cmp(b)) | ||
231 | .map(|(_, resolved)| resolved) | ||
232 | } | ||