diff options
Diffstat (limited to 'crates/ide/src/syntax_highlighting/highlights.rs')
-rw-r--r-- | crates/ide/src/syntax_highlighting/highlights.rs | 102 |
1 files changed, 102 insertions, 0 deletions
diff --git a/crates/ide/src/syntax_highlighting/highlights.rs b/crates/ide/src/syntax_highlighting/highlights.rs new file mode 100644 index 000000000..c6f0417ec --- /dev/null +++ b/crates/ide/src/syntax_highlighting/highlights.rs | |||
@@ -0,0 +1,102 @@ | |||
1 | //! Collects a tree of highlighted ranges and flattens it. | ||
2 | use std::{cmp::Ordering, 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| 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 | } | ||
93 | |||
94 | pub(super) fn ordering(r1: TextRange, r2: TextRange) -> Ordering { | ||
95 | if r1.end() <= r2.start() { | ||
96 | Ordering::Less | ||
97 | } else if r2.end() <= r1.start() { | ||
98 | Ordering::Greater | ||
99 | } else { | ||
100 | Ordering::Equal | ||
101 | } | ||
102 | } | ||