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::{HighlightConfig, 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 add_with(&mut self, config: &HighlightConfig<'_>, mut hl_range: HlRange) {
30        if super::filter_by_config(&mut hl_range.highlight, config) {
31            self.root.add(hl_range);
32        }
33    }
34
35    pub(super) fn to_vec(&self) -> Vec<HlRange> {
36        let mut res = Vec::new();
37        self.root.flatten(&mut res);
38        res
39    }
40}
41
42impl Node {
43    fn new(hl_range: HlRange) -> Node {
44        Node { hl_range, nested: Vec::new() }
45    }
46
47    fn add(&mut self, hl_range: HlRange) {
48        assert!(self.hl_range.range.contains_range(hl_range.range));
49
50        // Fast path
51        if let Some(last) = self.nested.last_mut() {
52            if last.hl_range.range.contains_range(hl_range.range) {
53                return last.add(hl_range);
54            }
55            if last.hl_range.range.end() <= hl_range.range.start() {
56                return self.nested.push(Node::new(hl_range));
57            }
58        }
59
60        let overlapping =
61            equal_range_by(&self.nested, |n| TextRange::ordering(n.hl_range.range, hl_range.range));
62
63        if overlapping.len() == 1
64            && self.nested[overlapping.start].hl_range.range.contains_range(hl_range.range)
65        {
66            return self.nested[overlapping.start].add(hl_range);
67        }
68
69        let nested = self
70            .nested
71            .splice(overlapping.clone(), iter::once(Node::new(hl_range)))
72            .collect::<Vec<_>>();
73        self.nested[overlapping.start].nested = nested;
74    }
75
76    fn flatten(&self, acc: &mut Vec<HlRange>) {
77        let mut start = self.hl_range.range.start();
78        let mut nested = self.nested.iter();
79        loop {
80            let next = nested.next();
81            let end = next.map_or(self.hl_range.range.end(), |it| it.hl_range.range.start());
82            if start < end {
83                acc.push(HlRange {
84                    range: TextRange::new(start, end),
85                    highlight: self.hl_range.highlight,
86                    binding_hash: self.hl_range.binding_hash,
87                });
88            }
89            start = match next {
90                Some(child) => {
91                    child.flatten(acc);
92                    child.hl_range.range.end()
93                }
94                None => break,
95            }
96        }
97    }
98}
ide/syntax_highlighting/highlights.rs

ide/syntax_highlighting/
highlights.rs
