crates/ide/src/syntax_highlighting/highlights.rs

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