diff options
Diffstat (limited to 'crates/ide/src/syntax_highlighting/highlights.rs')
-rw-r--r-- | crates/ide/src/syntax_highlighting/highlights.rs | 100 |
1 files changed, 100 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..11c11ed28 --- /dev/null +++ b/crates/ide/src/syntax_highlighting/highlights.rs | |||
@@ -0,0 +1,100 @@ | |||
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 (start, len) = | ||
55 | equal_range_by(&self.nested, |n| ordering(n.hl_range.range, hl_range.range)); | ||
56 | |||
57 | if len == 1 && self.nested[start].hl_range.range.contains_range(hl_range.range) { | ||
58 | return self.nested[start].add(hl_range); | ||
59 | } | ||
60 | |||
61 | let nested = self | ||
62 | .nested | ||
63 | .splice(start..start + len, iter::once(Node::new(hl_range))) | ||
64 | .collect::<Vec<_>>(); | ||
65 | self.nested[start].nested = nested; | ||
66 | } | ||
67 | |||
68 | fn flatten(&self, acc: &mut Vec<HlRange>) { | ||
69 | let mut start = self.hl_range.range.start(); | ||
70 | let mut nested = self.nested.iter(); | ||
71 | loop { | ||
72 | let next = nested.next(); | ||
73 | let end = next.map_or(self.hl_range.range.end(), |it| it.hl_range.range.start()); | ||
74 | if start < end { | ||
75 | acc.push(HlRange { | ||
76 | range: TextRange::new(start, end), | ||
77 | highlight: self.hl_range.highlight, | ||
78 | binding_hash: self.hl_range.binding_hash, | ||
79 | }); | ||
80 | } | ||
81 | start = match next { | ||
82 | Some(child) => { | ||
83 | child.flatten(acc); | ||
84 | child.hl_range.range.end() | ||
85 | } | ||
86 | None => break, | ||
87 | } | ||
88 | } | ||
89 | } | ||
90 | } | ||
91 | |||
92 | pub(super) fn ordering(r1: TextRange, r2: TextRange) -> Ordering { | ||
93 | if r1.end() <= r2.start() { | ||
94 | Ordering::Less | ||
95 | } else if r2.end() <= r1.start() { | ||
96 | Ordering::Greater | ||
97 | } else { | ||
98 | Ordering::Equal | ||
99 | } | ||
100 | } | ||