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
10 use ide_db::FxHashMap;
11 use syntax::SyntaxNode;
12
13 use crate::{Match, SsrMatches};
14
nest_and_remove_collisions( mut matches: Vec<Match>, sema: &hir::Semantics<'_, ide_db::RootDatabase>, ) -> SsrMatches15 pub(crate) fn nest_and_remove_collisions(
16 mut matches: Vec<Match>,
17 sema: &hir::Semantics<'_, ide_db::RootDatabase>,
18 ) -> SsrMatches {
19 // We sort the matches by depth then by rule index. Sorting by depth means that by the time we
20 // see a match, any parent matches or conflicting matches will have already been seen. Sorting
21 // by rule_index means that if there are two matches for the same node, the rule added first
22 // will take precedence.
23 matches.sort_by(|a, b| a.depth.cmp(&b.depth).then_with(|| a.rule_index.cmp(&b.rule_index)));
24 let mut collector = MatchCollector::default();
25 for m in matches {
26 collector.add_match(m, sema);
27 }
28 collector.into()
29 }
30
31 #[derive(Default)]
32 struct MatchCollector {
33 matches_by_node: FxHashMap<SyntaxNode, Match>,
34 }
35
36 impl MatchCollector {
37 /// Attempts to add `m` to matches. If it conflicts with an existing match, it is discarded. If
38 /// it is entirely within the a placeholder of an existing match, then it is added as a child
39 /// match of the existing match.
add_match(&mut self, m: Match, sema: &hir::Semantics<'_, ide_db::RootDatabase>)40 fn add_match(&mut self, m: Match, sema: &hir::Semantics<'_, ide_db::RootDatabase>) {
41 let matched_node = m.matched_node.clone();
42 if let Some(existing) = self.matches_by_node.get_mut(&matched_node) {
43 try_add_sub_match(m, existing, sema);
44 return;
45 }
46 for ancestor in sema.ancestors_with_macros(m.matched_node.clone()) {
47 if let Some(existing) = self.matches_by_node.get_mut(&ancestor) {
48 try_add_sub_match(m, existing, sema);
49 return;
50 }
51 }
52 self.matches_by_node.insert(matched_node, m);
53 }
54 }
55
56 /// Attempts to add `m` as a sub-match of `existing`.
try_add_sub_match( m: Match, existing: &mut Match, sema: &hir::Semantics<'_, ide_db::RootDatabase>, )57 fn try_add_sub_match(
58 m: Match,
59 existing: &mut Match,
60 sema: &hir::Semantics<'_, ide_db::RootDatabase>,
61 ) {
62 for p in existing.placeholder_values.values_mut() {
63 // Note, no need to check if p.range.file is equal to m.range.file, since we
64 // already know we're within `existing`.
65 if p.range.range.contains_range(m.range.range) {
66 // Convert the inner matches in `p` into a temporary MatchCollector. When
67 // we're done, we then convert it back into an SsrMatches. If we expected
68 // lots of inner matches, it might be worthwhile keeping a MatchCollector
69 // around for each placeholder match. However we expect most placeholder
70 // will have 0 and a few will have 1. More than that should hopefully be
71 // exceptional.
72 let mut collector = MatchCollector::default();
73 for m in std::mem::take(&mut p.inner_matches.matches) {
74 collector.matches_by_node.insert(m.matched_node.clone(), m);
75 }
76 collector.add_match(m, sema);
77 p.inner_matches = collector.into();
78 break;
79 }
80 }
81 }
82
83 impl From<MatchCollector> for SsrMatches {
from(mut match_collector: MatchCollector) -> Self84 fn from(mut match_collector: MatchCollector) -> Self {
85 let mut matches = SsrMatches::default();
86 for (_, m) in match_collector.matches_by_node.drain() {
87 matches.matches.push(m);
88 }
89 matches.matches.sort_by(|a, b| {
90 // Order matches by file_id then by start range. This should be sufficient since ranges
91 // shouldn't be overlapping.
92 a.range
93 .file_id
94 .cmp(&b.range.file_id)
95 .then_with(|| a.range.range.start().cmp(&b.range.range.start()))
96 });
97 matches
98 }
99 }
100