diff options
author | David Lattimore <[email protected]> | 2020-07-22 05:01:21 +0100 |
---|---|---|
committer | David Lattimore <[email protected]> | 2020-07-24 12:34:00 +0100 |
commit | 63f500b0ee55443a52f078060004c911a7532a14 (patch) | |
tree | 7944b776eea1eb69e4d822f5c004d5f082acd9b8 /crates/ra_ssr/src/search.rs | |
parent | 757f755c29e041fd319af466d7d0418f54cb090a (diff) |
SSR: Use Definition::find_usages to speed up matching.
When the search pattern contains a path, this substantially speeds up finding matches, especially if the path references a private item.
Diffstat (limited to 'crates/ra_ssr/src/search.rs')
-rw-r--r-- | crates/ra_ssr/src/search.rs | 131 |
1 files changed, 126 insertions, 5 deletions
diff --git a/crates/ra_ssr/src/search.rs b/crates/ra_ssr/src/search.rs index ccc2d544a..9a4e35e96 100644 --- a/crates/ra_ssr/src/search.rs +++ b/crates/ra_ssr/src/search.rs | |||
@@ -1,17 +1,106 @@ | |||
1 | //! Searching for matches. | 1 | //! Searching for matches. |
2 | 2 | ||
3 | use crate::{matching, resolving::ResolvedRule, Match, MatchFinder}; | 3 | use crate::{ |
4 | matching, | ||
5 | resolving::{ResolvedPath, ResolvedPattern, ResolvedRule}, | ||
6 | Match, MatchFinder, | ||
7 | }; | ||
4 | use ra_db::FileRange; | 8 | use ra_db::FileRange; |
9 | use ra_ide_db::{ | ||
10 | defs::Definition, | ||
11 | search::{Reference, SearchScope}, | ||
12 | }; | ||
5 | use ra_syntax::{ast, AstNode, SyntaxNode}; | 13 | use ra_syntax::{ast, AstNode, SyntaxNode}; |
6 | 14 | ||
15 | /// A cache for the results of find_usages. This is for when we have multiple patterns that have the | ||
16 | /// same path. e.g. if the pattern was `foo::Bar` that can parse as a path, an expression, a type | ||
17 | /// and as a pattern. In each, the usages of `foo::Bar` are the same and we'd like to avoid finding | ||
18 | /// them more than once. | ||
19 | #[derive(Default)] | ||
20 | pub(crate) struct UsageCache { | ||
21 | usages: Vec<(Definition, Vec<Reference>)>, | ||
22 | } | ||
23 | |||
7 | impl<'db> MatchFinder<'db> { | 24 | impl<'db> MatchFinder<'db> { |
8 | /// Adds all matches for `rule` to `matches_out`. Matches may overlap in ways that make | 25 | /// Adds all matches for `rule` to `matches_out`. Matches may overlap in ways that make |
9 | /// replacement impossible, so further processing is required in order to properly nest matches | 26 | /// replacement impossible, so further processing is required in order to properly nest matches |
10 | /// and remove overlapping matches. This is done in the `nesting` module. | 27 | /// and remove overlapping matches. This is done in the `nesting` module. |
11 | pub(crate) fn find_matches_for_rule(&self, rule: &ResolvedRule, matches_out: &mut Vec<Match>) { | 28 | pub(crate) fn find_matches_for_rule( |
12 | // FIXME: Use resolved paths in the pattern to find places to search instead of always | 29 | &self, |
13 | // scanning every node. | 30 | rule: &ResolvedRule, |
14 | self.slow_scan(rule, matches_out); | 31 | usage_cache: &mut UsageCache, |
32 | matches_out: &mut Vec<Match>, | ||
33 | ) { | ||
34 | if pick_path_for_usages(&rule.pattern).is_none() { | ||
35 | self.slow_scan(rule, matches_out); | ||
36 | return; | ||
37 | } | ||
38 | self.find_matches_for_pattern_tree(rule, &rule.pattern, usage_cache, matches_out); | ||
39 | } | ||
40 | |||
41 | fn find_matches_for_pattern_tree( | ||
42 | &self, | ||
43 | rule: &ResolvedRule, | ||
44 | pattern: &ResolvedPattern, | ||
45 | usage_cache: &mut UsageCache, | ||
46 | matches_out: &mut Vec<Match>, | ||
47 | ) { | ||
48 | if let Some(first_path) = pick_path_for_usages(pattern) { | ||
49 | let definition: Definition = first_path.resolution.clone().into(); | ||
50 | for reference in self.find_usages(usage_cache, definition) { | ||
51 | let file = self.sema.parse(reference.file_range.file_id); | ||
52 | if let Some(path) = self.sema.find_node_at_offset_with_descend::<ast::Path>( | ||
53 | file.syntax(), | ||
54 | reference.file_range.range.start(), | ||
55 | ) { | ||
56 | if let Some(node_to_match) = self | ||
57 | .sema | ||
58 | .ancestors_with_macros(path.syntax().clone()) | ||
59 | .skip(first_path.depth as usize) | ||
60 | .next() | ||
61 | { | ||
62 | if let Ok(m) = | ||
63 | matching::get_match(false, rule, &node_to_match, &None, &self.sema) | ||
64 | { | ||
65 | matches_out.push(m); | ||
66 | } | ||
67 | } | ||
68 | } | ||
69 | } | ||
70 | } | ||
71 | } | ||
72 | |||
73 | fn find_usages<'a>( | ||
74 | &self, | ||
75 | usage_cache: &'a mut UsageCache, | ||
76 | definition: Definition, | ||
77 | ) -> &'a [Reference] { | ||
78 | // Logically if a lookup succeeds we should just return it. Unfortunately returning it would | ||
79 | // extend the lifetime of the borrow, then we wouldn't be able to do the insertion on a | ||
80 | // cache miss. This is a limitation of NLL and is fixed with Polonius. For now we do two | ||
81 | // lookups in the case of a cache hit. | ||
82 | if usage_cache.find(&definition).is_none() { | ||
83 | let usages = definition.find_usages(&self.sema, Some(self.search_scope())); | ||
84 | usage_cache.usages.push((definition, usages)); | ||
85 | return &usage_cache.usages.last().unwrap().1; | ||
86 | } | ||
87 | usage_cache.find(&definition).unwrap() | ||
88 | } | ||
89 | |||
90 | /// Returns the scope within which we want to search. We don't want un unrestricted search | ||
91 | /// scope, since we don't want to find references in external dependencies. | ||
92 | fn search_scope(&self) -> SearchScope { | ||
93 | // FIXME: We should ideally have a test that checks that we edit local roots and not library | ||
94 | // roots. This probably would require some changes to fixtures, since currently everything | ||
95 | // seems to get put into a single source root. | ||
96 | use ra_db::SourceDatabaseExt; | ||
97 | use ra_ide_db::symbol_index::SymbolsDatabase; | ||
98 | let mut files = Vec::new(); | ||
99 | for &root in self.sema.db.local_roots().iter() { | ||
100 | let sr = self.sema.db.source_root(root); | ||
101 | files.extend(sr.iter()); | ||
102 | } | ||
103 | SearchScope::files(&files) | ||
15 | } | 104 | } |
16 | 105 | ||
17 | fn slow_scan(&self, rule: &ResolvedRule, matches_out: &mut Vec<Match>) { | 106 | fn slow_scan(&self, rule: &ResolvedRule, matches_out: &mut Vec<Match>) { |
@@ -59,3 +148,35 @@ impl<'db> MatchFinder<'db> { | |||
59 | } | 148 | } |
60 | } | 149 | } |
61 | } | 150 | } |
151 | |||
152 | impl UsageCache { | ||
153 | fn find(&mut self, definition: &Definition) -> Option<&[Reference]> { | ||
154 | // We expect a very small number of cache entries (generally 1), so a linear scan should be | ||
155 | // fast enough and avoids the need to implement Hash for Definition. | ||
156 | for (d, refs) in &self.usages { | ||
157 | if d == definition { | ||
158 | return Some(refs); | ||
159 | } | ||
160 | } | ||
161 | None | ||
162 | } | ||
163 | } | ||
164 | |||
165 | /// Returns a path that's suitable for path resolution. We exclude builtin types, since they aren't | ||
166 | /// something that we can find references to. We then somewhat arbitrarily pick the path that is the | ||
167 | /// longest as this is hopefully more likely to be less common, making it faster to find. | ||
168 | fn pick_path_for_usages(pattern: &ResolvedPattern) -> Option<&ResolvedPath> { | ||
169 | // FIXME: Take the scope of the resolved path into account. e.g. if there are any paths that are | ||
170 | // private to the current module, then we definitely would want to pick them over say a path | ||
171 | // from std. Possibly we should go further than this and intersect the search scopes for all | ||
172 | // resolved paths then search only in that scope. | ||
173 | pattern | ||
174 | .resolved_paths | ||
175 | .iter() | ||
176 | .filter(|(_, p)| { | ||
177 | !matches!(p.resolution, hir::PathResolution::Def(hir::ModuleDef::BuiltinType(_))) | ||
178 | }) | ||
179 | .map(|(node, resolved)| (node.text().len(), resolved)) | ||
180 | .max_by(|(a, _), (b, _)| a.cmp(b)) | ||
181 | .map(|(_, resolved)| resolved) | ||
182 | } | ||