crates/ide_ssr/src/nester.rs

   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 crate::{Match, SsrMatches};
  11 use rustc_hash::FxHashMap;
  12 use syntax::SyntaxNode;
  13
  14 pub(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)]
  31 struct MatchCollector {
  32     matches_by_node: FxHashMap<SyntaxNode, Match>,
  33 }
  34
  35 impl 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`.
  56 fn 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::take(&mut p.inner_matches.matches) {
  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
  78 impl 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 }