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::{HlRange, HlTag};
9 pub(super) struct Highlights {
19 pub(super) fn new(range: TextRange) -> Highlights {
21 root: Node::new(HlRange { range, highlight: HlTag::None.into(), binding_hash: None }),
25 pub(super) fn add(&mut self, hl_range: HlRange) {
26 self.root.add(hl_range);
29 pub(super) fn to_vec(self) -> Vec<HlRange> {
30 let mut res = Vec::new();
31 self.root.flatten(&mut res);
37 fn new(hl_range: HlRange) -> Node {
38 Node { hl_range, nested: Vec::new() }
41 fn add(&mut self, hl_range: HlRange) {
42 assert!(self.hl_range.range.contains_range(hl_range.range));
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);
49 if last.hl_range.range.end() <= hl_range.range.start() {
50 return self.nested.push(Node::new(hl_range));
55 equal_range_by(&self.nested, |n| ordering(n.hl_range.range, hl_range.range));
57 if overlapping.len() == 1
58 && self.nested[overlapping.start].hl_range.range.contains_range(hl_range.range)
60 return self.nested[overlapping.start].add(hl_range);
65 .splice(overlapping.clone(), iter::once(Node::new(hl_range)))
67 self.nested[overlapping.start].nested = nested;
70 fn flatten(&self, acc: &mut Vec<HlRange>) {
71 let mut start = self.hl_range.range.start();
72 let mut nested = self.nested.iter();
74 let next = nested.next();
75 let end = next.map_or(self.hl_range.range.end(), |it| it.hl_range.range.start());
78 range: TextRange::new(start, end),
79 highlight: self.hl_range.highlight,
80 binding_hash: self.hl_range.binding_hash,
86 child.hl_range.range.end()
94 pub(super) fn ordering(r1: TextRange, r2: TextRange) -> Ordering {
95 if r1.end() <= r2.start() {
97 } else if r2.end() <= r1.start() {