aboutsummaryrefslogtreecommitdiff
path: root/crates
diff options
context:
space:
mode:
authorDavid Lattimore <[email protected]>2020-07-22 05:01:21 +0100
committerDavid Lattimore <[email protected]>2020-07-24 12:34:00 +0100
commit63f500b0ee55443a52f078060004c911a7532a14 (patch)
tree7944b776eea1eb69e4d822f5c004d5f082acd9b8 /crates
parent757f755c29e041fd319af466d7d0418f54cb090a (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')
-rw-r--r--crates/ra_ide_db/src/defs.rs35
-rw-r--r--crates/ra_ide_db/src/search.rs4
-rw-r--r--crates/ra_ssr/src/lib.rs3
-rw-r--r--crates/ra_ssr/src/resolving.rs8
-rw-r--r--crates/ra_ssr/src/search.rs131
5 files changed, 157 insertions, 24 deletions
diff --git a/crates/ra_ide_db/src/defs.rs b/crates/ra_ide_db/src/defs.rs
index e06b189a0..f391a8e43 100644
--- a/crates/ra_ide_db/src/defs.rs
+++ b/crates/ra_ide_db/src/defs.rs
@@ -290,20 +290,25 @@ pub fn classify_name_ref(
290 290
291 let path = name_ref.syntax().ancestors().find_map(ast::Path::cast)?; 291 let path = name_ref.syntax().ancestors().find_map(ast::Path::cast)?;
292 let resolved = sema.resolve_path(&path)?; 292 let resolved = sema.resolve_path(&path)?;
293 let res = match resolved { 293 Some(NameRefClass::Definition(resolved.into()))
294 PathResolution::Def(def) => Definition::ModuleDef(def), 294}
295 PathResolution::AssocItem(item) => { 295
296 let def = match item { 296impl From<PathResolution> for Definition {
297 hir::AssocItem::Function(it) => it.into(), 297 fn from(path_resolution: PathResolution) -> Self {
298 hir::AssocItem::Const(it) => it.into(), 298 match path_resolution {
299 hir::AssocItem::TypeAlias(it) => it.into(), 299 PathResolution::Def(def) => Definition::ModuleDef(def),
300 }; 300 PathResolution::AssocItem(item) => {
301 Definition::ModuleDef(def) 301 let def = match item {
302 hir::AssocItem::Function(it) => it.into(),
303 hir::AssocItem::Const(it) => it.into(),
304 hir::AssocItem::TypeAlias(it) => it.into(),
305 };
306 Definition::ModuleDef(def)
307 }
308 PathResolution::Local(local) => Definition::Local(local),
309 PathResolution::TypeParam(par) => Definition::TypeParam(par),
310 PathResolution::Macro(def) => Definition::Macro(def),
311 PathResolution::SelfType(impl_def) => Definition::SelfType(impl_def),
302 } 312 }
303 PathResolution::Local(local) => Definition::Local(local), 313 }
304 PathResolution::TypeParam(par) => Definition::TypeParam(par),
305 PathResolution::Macro(def) => Definition::Macro(def),
306 PathResolution::SelfType(impl_def) => Definition::SelfType(impl_def),
307 };
308 Some(NameRefClass::Definition(res))
309} 314}
diff --git a/crates/ra_ide_db/src/search.rs b/crates/ra_ide_db/src/search.rs
index 81553150b..a7cae37b0 100644
--- a/crates/ra_ide_db/src/search.rs
+++ b/crates/ra_ide_db/src/search.rs
@@ -60,6 +60,10 @@ impl SearchScope {
60 SearchScope::new(std::iter::once((file, None)).collect()) 60 SearchScope::new(std::iter::once((file, None)).collect())
61 } 61 }
62 62
63 pub fn files(files: &[FileId]) -> SearchScope {
64 SearchScope::new(files.iter().map(|f| (*f, None)).collect())
65 }
66
63 pub fn intersection(&self, other: &SearchScope) -> SearchScope { 67 pub fn intersection(&self, other: &SearchScope) -> SearchScope {
64 let (mut small, mut large) = (&self.entries, &other.entries); 68 let (mut small, mut large) = (&self.entries, &other.entries);
65 if small.len() > large.len() { 69 if small.len() > large.len() {
diff --git a/crates/ra_ssr/src/lib.rs b/crates/ra_ssr/src/lib.rs
index 286619f59..5a71d4f31 100644
--- a/crates/ra_ssr/src/lib.rs
+++ b/crates/ra_ssr/src/lib.rs
@@ -151,8 +151,9 @@ impl<'db> MatchFinder<'db> {
151 /// Returns matches for all added rules. 151 /// Returns matches for all added rules.
152 pub fn matches(&self) -> SsrMatches { 152 pub fn matches(&self) -> SsrMatches {
153 let mut matches = Vec::new(); 153 let mut matches = Vec::new();
154 let mut usage_cache = search::UsageCache::default();
154 for rule in &self.rules { 155 for rule in &self.rules {
155 self.find_matches_for_rule(rule, &mut matches); 156 self.find_matches_for_rule(rule, &mut usage_cache, &mut matches);
156 } 157 }
157 nester::nest_and_remove_collisions(matches, &self.sema) 158 nester::nest_and_remove_collisions(matches, &self.sema)
158 } 159 }
diff --git a/crates/ra_ssr/src/resolving.rs b/crates/ra_ssr/src/resolving.rs
index e9d052111..63fd217ce 100644
--- a/crates/ra_ssr/src/resolving.rs
+++ b/crates/ra_ssr/src/resolving.rs
@@ -22,6 +22,7 @@ pub(crate) struct ResolvedPattern {
22 22
23pub(crate) struct ResolvedPath { 23pub(crate) struct ResolvedPath {
24 pub(crate) resolution: hir::PathResolution, 24 pub(crate) resolution: hir::PathResolution,
25 pub(crate) depth: u32,
25} 26}
26 27
27impl ResolvedRule { 28impl ResolvedRule {
@@ -62,7 +63,7 @@ struct Resolver<'a, 'db> {
62impl Resolver<'_, '_> { 63impl Resolver<'_, '_> {
63 fn resolve_pattern_tree(&self, pattern: SyntaxNode) -> Result<ResolvedPattern, SsrError> { 64 fn resolve_pattern_tree(&self, pattern: SyntaxNode) -> Result<ResolvedPattern, SsrError> {
64 let mut resolved_paths = FxHashMap::default(); 65 let mut resolved_paths = FxHashMap::default();
65 self.resolve(pattern.clone(), &mut resolved_paths)?; 66 self.resolve(pattern.clone(), 0, &mut resolved_paths)?;
66 Ok(ResolvedPattern { 67 Ok(ResolvedPattern {
67 node: pattern, 68 node: pattern,
68 resolved_paths, 69 resolved_paths,
@@ -73,6 +74,7 @@ impl Resolver<'_, '_> {
73 fn resolve( 74 fn resolve(
74 &self, 75 &self,
75 node: SyntaxNode, 76 node: SyntaxNode,
77 depth: u32,
76 resolved_paths: &mut FxHashMap<SyntaxNode, ResolvedPath>, 78 resolved_paths: &mut FxHashMap<SyntaxNode, ResolvedPath>,
77 ) -> Result<(), SsrError> { 79 ) -> Result<(), SsrError> {
78 use ra_syntax::ast::AstNode; 80 use ra_syntax::ast::AstNode;
@@ -86,12 +88,12 @@ impl Resolver<'_, '_> {
86 let resolution = self 88 let resolution = self
87 .resolve_path(&path) 89 .resolve_path(&path)
88 .ok_or_else(|| error!("Failed to resolve path `{}`", node.text()))?; 90 .ok_or_else(|| error!("Failed to resolve path `{}`", node.text()))?;
89 resolved_paths.insert(node, ResolvedPath { resolution }); 91 resolved_paths.insert(node, ResolvedPath { resolution, depth });
90 return Ok(()); 92 return Ok(());
91 } 93 }
92 } 94 }
93 for node in node.children() { 95 for node in node.children() {
94 self.resolve(node, resolved_paths)?; 96 self.resolve(node, depth + 1, resolved_paths)?;
95 } 97 }
96 Ok(()) 98 Ok(())
97 } 99 }
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
3use crate::{matching, resolving::ResolvedRule, Match, MatchFinder}; 3use crate::{
4 matching,
5 resolving::{ResolvedPath, ResolvedPattern, ResolvedRule},
6 Match, MatchFinder,
7};
4use ra_db::FileRange; 8use ra_db::FileRange;
9use ra_ide_db::{
10 defs::Definition,
11 search::{Reference, SearchScope},
12};
5use ra_syntax::{ast, AstNode, SyntaxNode}; 13use 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)]
20pub(crate) struct UsageCache {
21 usages: Vec<(Definition, Vec<Reference>)>,
22}
23
7impl<'db> MatchFinder<'db> { 24impl<'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
152impl 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.
168fn 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}