aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDavid Lattimore <[email protected]>2020-07-22 07:48:12 +0100
committerDavid Lattimore <[email protected]>2020-07-24 12:34:00 +0100
commit02fc3d50ee4d179cc5a443a790544c2a5e439cb0 (patch)
treeebef46263fa32fc04f1838b8b6a5191ce8809184
parent699619a65cf816b927fffa77b2b38f611d8460bc (diff)
SSR: Refactor to not rely on recursive search for nesting of matches
Previously, submatches were handled simply by searching in placeholders for more matches. That only works if we search all nodes in the tree recursively. In a subsequent commit, I intend to make search not always be recursive recursive. This commit prepares for that by finding all matches, even if they overlap, then nesting them and removing overlapping matches.
-rw-r--r--crates/ra_ssr/src/lib.rs7
-rw-r--r--crates/ra_ssr/src/matching.rs4
-rw-r--r--crates/ra_ssr/src/nester.rs98
-rw-r--r--crates/ra_ssr/src/search.rs38
4 files changed, 120 insertions, 27 deletions
diff --git a/crates/ra_ssr/src/lib.rs b/crates/ra_ssr/src/lib.rs
index 7b6409806..6d578610b 100644
--- a/crates/ra_ssr/src/lib.rs
+++ b/crates/ra_ssr/src/lib.rs
@@ -4,6 +4,7 @@
4//! based on a template. 4//! based on a template.
5 5
6mod matching; 6mod matching;
7mod nester;
7mod parsing; 8mod parsing;
8mod replacing; 9mod replacing;
9mod search; 10mod search;
@@ -90,8 +91,10 @@ impl<'db> MatchFinder<'db> {
90 /// Returns matches for all added rules. 91 /// Returns matches for all added rules.
91 pub fn matches(&self) -> SsrMatches { 92 pub fn matches(&self) -> SsrMatches {
92 let mut matches = Vec::new(); 93 let mut matches = Vec::new();
93 self.find_all_matches(&mut matches); 94 for rule in &self.rules {
94 SsrMatches { matches } 95 self.find_matches_for_rule(rule, &mut matches);
96 }
97 nester::nest_and_remove_collisions(matches, &self.sema)
95 } 98 }
96 99
97 /// Finds all nodes in `file_id` whose text is exactly equal to `snippet` and attempts to match 100 /// Finds all nodes in `file_id` whose text is exactly equal to `snippet` and attempts to match
diff --git a/crates/ra_ssr/src/matching.rs b/crates/ra_ssr/src/matching.rs
index 064e3a204..005569f6f 100644
--- a/crates/ra_ssr/src/matching.rs
+++ b/crates/ra_ssr/src/matching.rs
@@ -49,6 +49,8 @@ pub struct Match {
49 pub(crate) placeholder_values: FxHashMap<Var, PlaceholderMatch>, 49 pub(crate) placeholder_values: FxHashMap<Var, PlaceholderMatch>,
50 pub(crate) ignored_comments: Vec<ast::Comment>, 50 pub(crate) ignored_comments: Vec<ast::Comment>,
51 pub(crate) rule_index: usize, 51 pub(crate) rule_index: usize,
52 /// The depth of matched_node.
53 pub(crate) depth: usize,
52} 54}
53 55
54/// Represents a `$var` in an SSR query. 56/// Represents a `$var` in an SSR query.
@@ -130,10 +132,12 @@ impl<'db, 'sema> Matcher<'db, 'sema> {
130 placeholder_values: FxHashMap::default(), 132 placeholder_values: FxHashMap::default(),
131 ignored_comments: Vec::new(), 133 ignored_comments: Vec::new(),
132 rule_index: rule.index, 134 rule_index: rule.index,
135 depth: 0,
133 }; 136 };
134 // Second matching pass, where we record placeholder matches, ignored comments and maybe do 137 // Second matching pass, where we record placeholder matches, ignored comments and maybe do
135 // any other more expensive checks that we didn't want to do on the first pass. 138 // any other more expensive checks that we didn't want to do on the first pass.
136 match_state.attempt_match_node(&mut Phase::Second(&mut the_match), &rule.pattern, code)?; 139 match_state.attempt_match_node(&mut Phase::Second(&mut the_match), &rule.pattern, code)?;
140 the_match.depth = sema.ancestors_with_macros(the_match.matched_node.clone()).count();
137 Ok(the_match) 141 Ok(the_match)
138 } 142 }
139 143
diff --git a/crates/ra_ssr/src/nester.rs b/crates/ra_ssr/src/nester.rs
new file mode 100644
index 000000000..b3e20579b
--- /dev/null
+++ b/crates/ra_ssr/src/nester.rs
@@ -0,0 +1,98 @@
1//! Converts a flat collection of matches into a nested form suitable for replacement. When there
2//! are multiple matches for a node, or that overlap, priority is given to the earlier rule. Nested
3//! matches are only permitted if the inner match is contained entirely within a placeholder of an
4//! outer match.
5//!
6//! For example, if our search pattern is `foo(foo($a))` and the code had `foo(foo(foo(foo(42))))`,
7//! then we'll get 3 matches, however only the outermost and innermost matches can be accepted. The
8//! middle match would take the second `foo` from the outer match.
9
10use crate::{Match, SsrMatches};
11use ra_syntax::SyntaxNode;
12use rustc_hash::FxHashMap;
13
14pub(crate) fn nest_and_remove_collisions(
15 mut matches: Vec<Match>,
16 sema: &hir::Semantics<ra_ide_db::RootDatabase>,
17) -> SsrMatches {
18 // We sort the matches by depth then by rule index. Sorting by depth means that by the time we
19 // see a match, any parent matches or conflicting matches will have already been seen. Sorting
20 // by rule_index means that if there are two matches for the same node, the rule added first
21 // will take precedence.
22 matches.sort_by(|a, b| a.depth.cmp(&b.depth).then_with(|| a.rule_index.cmp(&b.rule_index)));
23 let mut collector = MatchCollector::default();
24 for m in matches {
25 collector.add_match(m, sema);
26 }
27 collector.into()
28}
29
30#[derive(Default)]
31struct MatchCollector {
32 matches_by_node: FxHashMap<SyntaxNode, Match>,
33}
34
35impl MatchCollector {
36 /// Attempts to add `m` to matches. If it conflicts with an existing match, it is discarded. If
37 /// it is entirely within the a placeholder of an existing match, then it is added as a child
38 /// match of the existing match.
39 fn add_match(&mut self, m: Match, sema: &hir::Semantics<ra_ide_db::RootDatabase>) {
40 let matched_node = m.matched_node.clone();
41 if let Some(existing) = self.matches_by_node.get_mut(&matched_node) {
42 try_add_sub_match(m, existing, sema);
43 return;
44 }
45 for ancestor in sema.ancestors_with_macros(m.matched_node.clone()) {
46 if let Some(existing) = self.matches_by_node.get_mut(&ancestor) {
47 try_add_sub_match(m, existing, sema);
48 return;
49 }
50 }
51 self.matches_by_node.insert(matched_node, m);
52 }
53}
54
55/// Attempts to add `m` as a sub-match of `existing`.
56fn try_add_sub_match(
57 m: Match,
58 existing: &mut Match,
59 sema: &hir::Semantics<ra_ide_db::RootDatabase>,
60) {
61 for p in existing.placeholder_values.values_mut() {
62 // Note, no need to check if p.range.file is equal to m.range.file, since we
63 // already know we're within `existing`.
64 if p.range.range.contains_range(m.range.range) {
65 // Convert the inner matches in `p` into a temporary MatchCollector. When
66 // we're done, we then convert it back into an SsrMatches. If we expected
67 // lots of inner matches, it might be worthwhile keeping a MatchCollector
68 // around for each placeholder match. However we expect most placeholder
69 // will have 0 and a few will have 1. More than that should hopefully be
70 // exceptional.
71 let mut collector = MatchCollector::default();
72 for m in std::mem::replace(&mut p.inner_matches.matches, Vec::new()) {
73 collector.matches_by_node.insert(m.matched_node.clone(), m);
74 }
75 collector.add_match(m, sema);
76 p.inner_matches = collector.into();
77 break;
78 }
79 }
80}
81
82impl From<MatchCollector> for SsrMatches {
83 fn from(mut match_collector: MatchCollector) -> Self {
84 let mut matches = SsrMatches::default();
85 for (_, m) in match_collector.matches_by_node.drain() {
86 matches.matches.push(m);
87 }
88 matches.matches.sort_by(|a, b| {
89 // Order matches by file_id then by start range. This should be sufficient since ranges
90 // shouldn't be overlapping.
91 a.range
92 .file_id
93 .cmp(&b.range.file_id)
94 .then_with(|| a.range.range.start().cmp(&b.range.range.start()))
95 });
96 matches
97 }
98}
diff --git a/crates/ra_ssr/src/search.rs b/crates/ra_ssr/src/search.rs
index ec3addcf8..a28e9f341 100644
--- a/crates/ra_ssr/src/search.rs
+++ b/crates/ra_ssr/src/search.rs
@@ -1,17 +1,20 @@
1//! Searching for matches. 1//! Searching for matches.
2 2
3use crate::{matching, Match, MatchFinder}; 3use crate::{matching, parsing::ParsedRule, Match, MatchFinder};
4use ra_db::FileRange; 4use ra_db::FileRange;
5use ra_syntax::{ast, AstNode, SyntaxNode}; 5use ra_syntax::{ast, AstNode, SyntaxNode};
6 6
7impl<'db> MatchFinder<'db> { 7impl<'db> MatchFinder<'db> {
8 pub(crate) fn find_all_matches(&self, matches_out: &mut Vec<Match>) { 8 /// 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
10 /// and remove overlapping matches. This is done in the `nesting` module.
11 pub(crate) fn find_matches_for_rule(&self, rule: &ParsedRule, matches_out: &mut Vec<Match>) {
9 // FIXME: Use resolved paths in the pattern to find places to search instead of always 12 // FIXME: Use resolved paths in the pattern to find places to search instead of always
10 // scanning every node. 13 // scanning every node.
11 self.slow_scan(matches_out); 14 self.slow_scan(rule, matches_out);
12 } 15 }
13 16
14 fn slow_scan(&self, matches_out: &mut Vec<Match>) { 17 fn slow_scan(&self, rule: &ParsedRule, matches_out: &mut Vec<Match>) {
15 use ra_db::SourceDatabaseExt; 18 use ra_db::SourceDatabaseExt;
16 use ra_ide_db::symbol_index::SymbolsDatabase; 19 use ra_ide_db::symbol_index::SymbolsDatabase;
17 for &root in self.sema.db.local_roots().iter() { 20 for &root in self.sema.db.local_roots().iter() {
@@ -19,7 +22,7 @@ impl<'db> MatchFinder<'db> {
19 for file_id in sr.iter() { 22 for file_id in sr.iter() {
20 let file = self.sema.parse(file_id); 23 let file = self.sema.parse(file_id);
21 let code = file.syntax(); 24 let code = file.syntax();
22 self.slow_scan_node(code, &None, matches_out); 25 self.slow_scan_node(code, rule, &None, matches_out);
23 } 26 }
24 } 27 }
25 } 28 }
@@ -27,28 +30,12 @@ impl<'db> MatchFinder<'db> {
27 fn slow_scan_node( 30 fn slow_scan_node(
28 &self, 31 &self,
29 code: &SyntaxNode, 32 code: &SyntaxNode,
33 rule: &ParsedRule,
30 restrict_range: &Option<FileRange>, 34 restrict_range: &Option<FileRange>,
31 matches_out: &mut Vec<Match>, 35 matches_out: &mut Vec<Match>,
32 ) { 36 ) {
33 for rule in &self.rules { 37 if let Ok(m) = matching::get_match(false, rule, &code, restrict_range, &self.sema) {
34 if let Ok(mut m) = matching::get_match(false, rule, &code, restrict_range, &self.sema) { 38 matches_out.push(m);
35 // Continue searching in each of our placeholders.
36 for placeholder_value in m.placeholder_values.values_mut() {
37 if let Some(placeholder_node) = &placeholder_value.node {
38 // Don't search our placeholder if it's the entire matched node, otherwise we'd
39 // find the same match over and over until we got a stack overflow.
40 if placeholder_node != code {
41 self.slow_scan_node(
42 placeholder_node,
43 restrict_range,
44 &mut placeholder_value.inner_matches.matches,
45 );
46 }
47 }
48 }
49 matches_out.push(m);
50 return;
51 }
52 } 39 }
53 // If we've got a macro call, we already tried matching it pre-expansion, which is the only 40 // If we've got a macro call, we already tried matching it pre-expansion, which is the only
54 // way to match the whole macro, now try expanding it and matching the expansion. 41 // way to match the whole macro, now try expanding it and matching the expansion.
@@ -60,6 +47,7 @@ impl<'db> MatchFinder<'db> {
60 // i.e. we don't want to match something that came from the macro itself. 47 // i.e. we don't want to match something that came from the macro itself.
61 self.slow_scan_node( 48 self.slow_scan_node(
62 &expanded, 49 &expanded,
50 rule,
63 &Some(self.sema.original_range(tt.syntax())), 51 &Some(self.sema.original_range(tt.syntax())),
64 matches_out, 52 matches_out,
65 ); 53 );
@@ -67,7 +55,7 @@ impl<'db> MatchFinder<'db> {
67 } 55 }
68 } 56 }
69 for child in code.children() { 57 for child in code.children() {
70 self.slow_scan_node(&child, restrict_range, matches_out); 58 self.slow_scan_node(&child, rule, restrict_range, matches_out);
71 } 59 }
72 } 60 }
73} 61}