1use collections::BTreeMap;
2use gpui::HighlightStyle;
3use language::Chunk;
4use multi_buffer::{MultiBufferChunks, MultiBufferSnapshot, ToOffset as _};
5use std::{
6 cmp,
7 iter::{self, Peekable},
8 ops::Range,
9 vec,
10};
11
12use crate::display_map::{HighlightKey, TextHighlights};
13
14pub struct CustomHighlightsChunks<'a> {
15 buffer_chunks: MultiBufferChunks<'a>,
16 buffer_chunk: Option<Chunk<'a>>,
17 offset: usize,
18 multibuffer_snapshot: &'a MultiBufferSnapshot,
19
20 highlight_endpoints: Peekable<vec::IntoIter<HighlightEndpoint>>,
21 active_highlights: BTreeMap<HighlightKey, HighlightStyle>,
22 text_highlights: Option<&'a TextHighlights>,
23}
24
25#[derive(Debug, Copy, Clone, Eq, PartialEq)]
26struct HighlightEndpoint {
27 offset: usize,
28 tag: HighlightKey,
29 style: Option<HighlightStyle>,
30}
31
32impl<'a> CustomHighlightsChunks<'a> {
33 pub fn new(
34 range: Range<usize>,
35 language_aware: bool,
36 text_highlights: Option<&'a TextHighlights>,
37 multibuffer_snapshot: &'a MultiBufferSnapshot,
38 ) -> Self {
39 Self {
40 buffer_chunks: multibuffer_snapshot.chunks(range.clone(), language_aware),
41 buffer_chunk: None,
42 offset: range.start,
43
44 text_highlights,
45 highlight_endpoints: create_highlight_endpoints(
46 &range,
47 text_highlights,
48 multibuffer_snapshot,
49 ),
50 active_highlights: Default::default(),
51 multibuffer_snapshot,
52 }
53 }
54
55 pub fn seek(&mut self, new_range: Range<usize>) {
56 self.highlight_endpoints =
57 create_highlight_endpoints(&new_range, self.text_highlights, self.multibuffer_snapshot);
58 self.offset = new_range.start;
59 self.buffer_chunks.seek(new_range);
60 self.buffer_chunk.take();
61 self.active_highlights.clear()
62 }
63}
64
65fn create_highlight_endpoints(
66 range: &Range<usize>,
67 text_highlights: Option<&TextHighlights>,
68 buffer: &MultiBufferSnapshot,
69) -> iter::Peekable<vec::IntoIter<HighlightEndpoint>> {
70 let mut highlight_endpoints = Vec::new();
71 if let Some(text_highlights) = text_highlights {
72 let start = buffer.anchor_after(range.start);
73 let end = buffer.anchor_after(range.end);
74 for (&tag, text_highlights) in text_highlights.iter() {
75 let style = text_highlights.0;
76 let ranges = &text_highlights.1;
77
78 let start_ix = match ranges.binary_search_by(|probe| {
79 let cmp = probe.end.cmp(&start, buffer);
80 if cmp.is_gt() {
81 cmp::Ordering::Greater
82 } else {
83 cmp::Ordering::Less
84 }
85 }) {
86 Ok(i) | Err(i) => i,
87 };
88
89 for range in &ranges[start_ix..] {
90 if range.start.cmp(&end, buffer).is_ge() {
91 break;
92 }
93
94 let start = range.start.to_offset(buffer);
95 let end = range.end.to_offset(buffer);
96 if start == end {
97 continue;
98 }
99 highlight_endpoints.push(HighlightEndpoint {
100 offset: start,
101 tag,
102 style: Some(style),
103 });
104 highlight_endpoints.push(HighlightEndpoint {
105 offset: end,
106 tag,
107 style: None,
108 });
109 }
110 }
111 highlight_endpoints.sort();
112 }
113 highlight_endpoints.into_iter().peekable()
114}
115
116impl<'a> Iterator for CustomHighlightsChunks<'a> {
117 type Item = Chunk<'a>;
118
119 fn next(&mut self) -> Option<Self::Item> {
120 let mut next_highlight_endpoint = usize::MAX;
121 while let Some(endpoint) = self.highlight_endpoints.peek().copied() {
122 if endpoint.offset <= self.offset {
123 if let Some(style) = endpoint.style {
124 self.active_highlights.insert(endpoint.tag, style);
125 } else {
126 self.active_highlights.remove(&endpoint.tag);
127 }
128 self.highlight_endpoints.next();
129 } else {
130 next_highlight_endpoint = endpoint.offset;
131 break;
132 }
133 }
134
135 let chunk = self
136 .buffer_chunk
137 .get_or_insert_with(|| self.buffer_chunks.next().unwrap_or_default());
138 if chunk.text.is_empty() {
139 *chunk = self.buffer_chunks.next()?;
140 }
141
142 let split_idx = chunk.text.len().min(next_highlight_endpoint - self.offset);
143 let (prefix, suffix) = chunk.text.split_at(split_idx);
144
145 let (chars, tabs) = if split_idx == 128 {
146 let output = (chunk.chars, chunk.tabs);
147 chunk.chars = 0;
148 chunk.tabs = 0;
149 output
150 } else {
151 let mask = (1 << split_idx) - 1;
152 let output = (chunk.chars & mask, chunk.tabs & mask);
153 chunk.chars = chunk.chars >> split_idx;
154 chunk.tabs = chunk.tabs >> split_idx;
155 output
156 };
157
158 chunk.text = suffix;
159 self.offset += prefix.len();
160 let mut prefix = Chunk {
161 text: prefix,
162 chars,
163 tabs,
164 ..chunk.clone()
165 };
166 if !self.active_highlights.is_empty() {
167 prefix.highlight_style = self
168 .active_highlights
169 .values()
170 .copied()
171 .reduce(|acc, active_highlight| acc.highlight(active_highlight));
172 }
173 Some(prefix)
174 }
175}
176
177impl PartialOrd for HighlightEndpoint {
178 fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
179 Some(self.cmp(other))
180 }
181}
182
183impl Ord for HighlightEndpoint {
184 fn cmp(&self, other: &Self) -> cmp::Ordering {
185 self.offset
186 .cmp(&other.offset)
187 .then_with(|| self.style.is_some().cmp(&other.style.is_some()))
188 }
189}
190
191#[cfg(test)]
192mod tests {
193 use std::{any::TypeId, sync::Arc};
194
195 use super::*;
196 use crate::MultiBuffer;
197 use gpui::App;
198 use rand::prelude::*;
199 use util::RandomCharIter;
200
201 #[gpui::test(iterations = 100)]
202 fn test_random_chunk_bitmaps(cx: &mut App, mut rng: StdRng) {
203 // Generate random buffer using existing test infrastructure
204 let len = rng.random_range(10..10000);
205 let buffer = if rng.random() {
206 let text = RandomCharIter::new(&mut rng).take(len).collect::<String>();
207 MultiBuffer::build_simple(&text, cx)
208 } else {
209 MultiBuffer::build_random(&mut rng, cx)
210 };
211
212 let buffer_snapshot = buffer.read(cx).snapshot(cx);
213
214 // Create random highlights
215 let mut highlights = sum_tree::TreeMap::default();
216 let highlight_count = rng.random_range(1..10);
217
218 for _i in 0..highlight_count {
219 let style = HighlightStyle {
220 color: Some(gpui::Hsla {
221 h: rng.random::<f32>(),
222 s: rng.random::<f32>(),
223 l: rng.random::<f32>(),
224 a: 1.0,
225 }),
226 ..Default::default()
227 };
228
229 let mut ranges = Vec::new();
230 let range_count = rng.random_range(1..10);
231 let text = buffer_snapshot.text();
232 for _ in 0..range_count {
233 if buffer_snapshot.len() == 0 {
234 continue;
235 }
236
237 let mut start = rng.random_range(0..=buffer_snapshot.len().saturating_sub(10));
238
239 while !text.is_char_boundary(start) {
240 start = start.saturating_sub(1);
241 }
242
243 let end_end = buffer_snapshot.len().min(start + 100);
244 let mut end = rng.random_range(start..=end_end);
245 while !text.is_char_boundary(end) {
246 end = end.saturating_sub(1);
247 }
248
249 if start < end {
250 start = end;
251 }
252 let start_anchor = buffer_snapshot.anchor_before(start);
253 let end_anchor = buffer_snapshot.anchor_after(end);
254 ranges.push(start_anchor..end_anchor);
255 }
256
257 let type_id = TypeId::of::<()>(); // Simple type ID for testing
258 highlights.insert(HighlightKey::Type(type_id), Arc::new((style, ranges)));
259 }
260
261 // Get all chunks and verify their bitmaps
262 let chunks =
263 CustomHighlightsChunks::new(0..buffer_snapshot.len(), false, None, &buffer_snapshot);
264
265 for chunk in chunks {
266 let chunk_text = chunk.text;
267 let chars_bitmap = chunk.chars;
268 let tabs_bitmap = chunk.tabs;
269
270 // Check empty chunks have empty bitmaps
271 if chunk_text.is_empty() {
272 assert_eq!(
273 chars_bitmap, 0,
274 "Empty chunk should have empty chars bitmap"
275 );
276 assert_eq!(tabs_bitmap, 0, "Empty chunk should have empty tabs bitmap");
277 continue;
278 }
279
280 // Verify that chunk text doesn't exceed 128 bytes
281 assert!(
282 chunk_text.len() <= 128,
283 "Chunk text length {} exceeds 128 bytes",
284 chunk_text.len()
285 );
286
287 // Verify chars bitmap
288 let char_indices = chunk_text
289 .char_indices()
290 .map(|(i, _)| i)
291 .collect::<Vec<_>>();
292
293 for byte_idx in 0..chunk_text.len() {
294 let should_have_bit = char_indices.contains(&byte_idx);
295 let has_bit = chars_bitmap & (1 << byte_idx) != 0;
296
297 if has_bit != should_have_bit {
298 eprintln!("Chunk text bytes: {:?}", chunk_text.as_bytes());
299 eprintln!("Char indices: {:?}", char_indices);
300 eprintln!("Chars bitmap: {:#b}", chars_bitmap);
301 assert_eq!(
302 has_bit, should_have_bit,
303 "Chars bitmap mismatch at byte index {} in chunk {:?}. Expected bit: {}, Got bit: {}",
304 byte_idx, chunk_text, should_have_bit, has_bit
305 );
306 }
307 }
308
309 // Verify tabs bitmap
310 for (byte_idx, byte) in chunk_text.bytes().enumerate() {
311 let is_tab = byte == b'\t';
312 let has_bit = tabs_bitmap & (1 << byte_idx) != 0;
313
314 if has_bit != is_tab {
315 eprintln!("Chunk text bytes: {:?}", chunk_text.as_bytes());
316 eprintln!("Tabs bitmap: {:#b}", tabs_bitmap);
317 assert_eq!(
318 has_bit, is_tab,
319 "Tabs bitmap mismatch at byte index {} in chunk {:?}. Byte: {:?}, Expected bit: {}, Got bit: {}",
320 byte_idx, chunk_text, byte as char, is_tab, has_bit
321 );
322 }
323 }
324 }
325 }
326}