ide/syntax_highlighting/
highlights.rs

1//! Collects a tree of highlighted ranges and flattens it.
2use std::iter;
3
4use stdx::equal_range_by;
5use syntax::TextRange;
6
7use crate::{HlRange, HlTag};
8
9pub(super) struct Highlights {
10    root: Node,
11}
12
13struct Node {
14    hl_range: HlRange,
15    nested: Vec<Node>,
16}
17
18impl 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
36impl 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}
ide/syntax_highlighting/highlights.rs

ide/syntax_highlighting/
highlights.rs
