crates/ide/src/syntax_highlighting/highlights.rs

   1 //! Collects a tree of highlighted ranges and flattens it.
   2 use std::{cmp::Ordering, iter};
   3
   4 use stdx::equal_range_by;
   5 use syntax::TextRange;
   6
   7 use crate::{HighlightedRange, HlTag};
   8
   9 pub(super) struct Highlights {
  10     root: Node,
  11 }
  12
  13 struct Node {
  14     highlighted_range: HighlightedRange,
  15     nested: Vec<Node>,
  16 }
  17
  18 impl Highlights {
  19     pub(super) fn new(range: TextRange) -> Highlights {
  20         Highlights {
  21             root: Node::new(HighlightedRange {
  22                 range,
  23                 highlight: HlTag::None.into(),
  24                 binding_hash: None,
  25             }),
  26         }
  27     }
  28
  29     pub(super) fn add(&mut self, highlighted_range: HighlightedRange) {
  30         self.root.add(highlighted_range);
  31     }
  32
  33     pub(super) fn to_vec(self) -> Vec<HighlightedRange> {
  34         let mut res = Vec::new();
  35         self.root.flatten(&mut res);
  36         res
  37     }
  38 }
  39
  40 impl Node {
  41     fn new(highlighted_range: HighlightedRange) -> Node {
  42         Node { highlighted_range, nested: Vec::new() }
  43     }
  44
  45     fn add(&mut self, highlighted_range: HighlightedRange) {
  46         assert!(self.highlighted_range.range.contains_range(highlighted_range.range));
  47
  48         // Fast path
  49         if let Some(last) = self.nested.last_mut() {
  50             if last.highlighted_range.range.contains_range(highlighted_range.range) {
  51                 return last.add(highlighted_range);
  52             }
  53             if last.highlighted_range.range.end() <= highlighted_range.range.start() {
  54                 return self.nested.push(Node::new(highlighted_range));
  55             }
  56         }
  57
  58         let (start, len) = equal_range_by(&self.nested, |n| {
  59             ordering(n.highlighted_range.range, highlighted_range.range)
  60         });
  61
  62         if len == 1
  63             && self.nested[start].highlighted_range.range.contains_range(highlighted_range.range)
  64         {
  65             return self.nested[start].add(highlighted_range);
  66         }
  67
  68         let nested = self
  69             .nested
  70             .splice(start..start + len, iter::once(Node::new(highlighted_range)))
  71             .collect::<Vec<_>>();
  72         self.nested[start].nested = nested;
  73     }
  74
  75     fn flatten(&self, acc: &mut Vec<HighlightedRange>) {
  76         let mut start = self.highlighted_range.range.start();
  77         let mut nested = self.nested.iter();
  78         loop {
  79             let next = nested.next();
  80             let end = next.map_or(self.highlighted_range.range.end(), |it| {
  81                 it.highlighted_range.range.start()
  82             });
  83             if start < end {
  84                 acc.push(HighlightedRange {
  85                     range: TextRange::new(start, end),
  86                     highlight: self.highlighted_range.highlight,
  87                     binding_hash: self.highlighted_range.binding_hash,
  88                 });
  89             }
  90             start = match next {
  91                 Some(child) => {
  92                     child.flatten(acc);
  93                     child.highlighted_range.range.end()
  94                 }
  95                 None => break,
  96             }
  97         }
  98     }
  99 }
 100
 101 pub(super) fn ordering(r1: TextRange, r2: TextRange) -> Ordering {
 102     if r1.end() <= r2.start() {
 103         Ordering::Less
 104     } else if r2.end() <= r1.start() {
 105         Ordering::Greater
 106     } else {
 107         Ordering::Equal
 108     }
 109 }