aboutsummaryrefslogtreecommitdiff
path: root/crates/ssr/src/nester.rs
diff options
context:
space:
mode:
Diffstat (limited to 'crates/ssr/src/nester.rs')
-rw-r--r--crates/ssr/src/nester.rs94
1 files changed, 94 insertions, 0 deletions
diff --git a/crates/ssr/src/nester.rs b/crates/ssr/src/nester.rs
new file mode 100644
index 000000000..6ac355dfc
--- /dev/null
+++ b/crates/ssr/src/nester.rs
@@ -0,0 +1,94 @@
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 rustc_hash::FxHashMap;
12use syntax::SyntaxNode;
13
14pub(crate) fn nest_and_remove_collisions(
15 mut matches: Vec<Match>,
16 sema: &hir::Semantics<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<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(m: Match, existing: &mut Match, sema: &hir::Semantics<ide_db::RootDatabase>) {
57 for p in existing.placeholder_values.values_mut() {
58 // Note, no need to check if p.range.file is equal to m.range.file, since we
59 // already know we're within `existing`.
60 if p.range.range.contains_range(m.range.range) {
61 // Convert the inner matches in `p` into a temporary MatchCollector. When
62 // we're done, we then convert it back into an SsrMatches. If we expected
63 // lots of inner matches, it might be worthwhile keeping a MatchCollector
64 // around for each placeholder match. However we expect most placeholder
65 // will have 0 and a few will have 1. More than that should hopefully be
66 // exceptional.
67 let mut collector = MatchCollector::default();
68 for m in std::mem::replace(&mut p.inner_matches.matches, Vec::new()) {
69 collector.matches_by_node.insert(m.matched_node.clone(), m);
70 }
71 collector.add_match(m, sema);
72 p.inner_matches = collector.into();
73 break;
74 }
75 }
76}
77
78impl From<MatchCollector> for SsrMatches {
79 fn from(mut match_collector: MatchCollector) -> Self {
80 let mut matches = SsrMatches::default();
81 for (_, m) in match_collector.matches_by_node.drain() {
82 matches.matches.push(m);
83 }
84 matches.matches.sort_by(|a, b| {
85 // Order matches by file_id then by start range. This should be sufficient since ranges
86 // shouldn't be overlapping.
87 a.range
88 .file_id
89 .cmp(&b.range.file_id)
90 .then_with(|| a.range.range.start().cmp(&b.range.range.start()))
91 });
92 matches
93 }
94}