aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-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}