1 //! Collects a tree of highlighted ranges and flattens it.
2 use std::{cmp::Ordering, iter};
4 use stdx::equal_range_by;
7 use crate::{HighlightTag, HighlightedRange};
9 pub(super) struct Highlights {
14 highlighted_range: HighlightedRange,
19 pub(super) fn new(range: TextRange) -> Highlights {
21 root: Node::new(HighlightedRange {
23 highlight: HighlightTag::None.into(),
29 pub(super) fn add(&mut self, highlighted_range: HighlightedRange) {
30 self.root.add(highlighted_range);
33 pub(super) fn to_vec(self) -> Vec<HighlightedRange> {
34 let mut res = Vec::new();
35 self.root.flatten(&mut res);
41 fn new(highlighted_range: HighlightedRange) -> Node {
42 Node { highlighted_range, nested: Vec::new() }
45 fn add(&mut self, highlighted_range: HighlightedRange) {
46 assert!(self.highlighted_range.range.contains_range(highlighted_range.range));
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);
53 if last.highlighted_range.range.end() <= highlighted_range.range.start() {
54 return self.nested.push(Node::new(highlighted_range));
58 let (start, len) = equal_range_by(&self.nested, |n| {
59 ordering(n.highlighted_range.range, highlighted_range.range)
63 && self.nested[start].highlighted_range.range.contains_range(highlighted_range.range)
65 return self.nested[start].add(highlighted_range);
70 .splice(start..start + len, iter::once(Node::new(highlighted_range)))
72 self.nested[start].nested = nested;
75 fn flatten(&self, acc: &mut Vec<HighlightedRange>) {
76 let mut start = self.highlighted_range.range.start();
77 let mut nested = self.nested.iter();
79 let next = nested.next();
80 let end = next.map_or(self.highlighted_range.range.end(), |it| {
81 it.highlighted_range.range.start()
84 acc.push(HighlightedRange {
85 range: TextRange::new(start, end),
86 highlight: self.highlighted_range.highlight,
87 binding_hash: self.highlighted_range.binding_hash,
93 child.highlighted_range.range.end()
101 pub(super) fn ordering(r1: TextRange, r2: TextRange) -> Ordering {
102 if r1.end() <= r2.start() {
104 } else if r2.end() <= r1.start() {