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 = match &mut self.buffer_chunk {
136 Some(it) => it,
137 slot => slot.insert(self.buffer_chunks.next()?),
138 };
139 while chunk.text.is_empty() {
140 *chunk = self.buffer_chunks.next()?;
141 }
142
143 let split_idx = chunk.text.len().min(next_highlight_endpoint - self.offset);
144 let (prefix, suffix) = chunk.text.split_at(split_idx);
145 self.offset += prefix.len();
146
147 let mask = 1u128.unbounded_shl(split_idx as u32).wrapping_sub(1);
148 let chars = chunk.chars & mask;
149 let tabs = chunk.tabs & mask;
150 let mut prefix = Chunk {
151 text: prefix,
152 chars,
153 tabs,
154 ..chunk.clone()
155 };
156
157 chunk.chars = chunk.chars.unbounded_shr(split_idx as u32);
158 chunk.tabs = chunk.tabs.unbounded_shr(split_idx as u32);
159 chunk.text = suffix;
160 if !self.active_highlights.is_empty() {
161 prefix.highlight_style = self
162 .active_highlights
163 .values()
164 .copied()
165 .reduce(|acc, active_highlight| acc.highlight(active_highlight));
166 }
167 Some(prefix)
168 }
169}
170
171impl PartialOrd for HighlightEndpoint {
172 fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
173 Some(self.cmp(other))
174 }
175}
176
177impl Ord for HighlightEndpoint {
178 fn cmp(&self, other: &Self) -> cmp::Ordering {
179 self.offset
180 .cmp(&other.offset)
181 .then_with(|| self.style.is_some().cmp(&other.style.is_some()))
182 }
183}
184
185#[cfg(test)]
186mod tests {
187 use std::{any::TypeId, sync::Arc};
188
189 use super::*;
190 use crate::MultiBuffer;
191 use gpui::App;
192 use rand::prelude::*;
193 use util::RandomCharIter;
194
195 #[gpui::test(iterations = 100)]
196 fn test_random_chunk_bitmaps(cx: &mut App, mut rng: StdRng) {
197 // Generate random buffer using existing test infrastructure
198 let len = rng.random_range(10..10000);
199 let buffer = if rng.random() {
200 let text = RandomCharIter::new(&mut rng).take(len).collect::<String>();
201 MultiBuffer::build_simple(&text, cx)
202 } else {
203 MultiBuffer::build_random(&mut rng, cx)
204 };
205
206 let buffer_snapshot = buffer.read(cx).snapshot(cx);
207
208 // Create random highlights
209 let mut highlights = sum_tree::TreeMap::default();
210 let highlight_count = rng.random_range(1..10);
211
212 for _i in 0..highlight_count {
213 let style = HighlightStyle {
214 color: Some(gpui::Hsla {
215 h: rng.random::<f32>(),
216 s: rng.random::<f32>(),
217 l: rng.random::<f32>(),
218 a: 1.0,
219 }),
220 ..Default::default()
221 };
222
223 let mut ranges = Vec::new();
224 let range_count = rng.random_range(1..10);
225 let text = buffer_snapshot.text();
226 for _ in 0..range_count {
227 if buffer_snapshot.len() == 0 {
228 continue;
229 }
230
231 let mut start = rng.random_range(0..=buffer_snapshot.len().saturating_sub(10));
232
233 while !text.is_char_boundary(start) {
234 start = start.saturating_sub(1);
235 }
236
237 let end_end = buffer_snapshot.len().min(start + 100);
238 let mut end = rng.random_range(start..=end_end);
239 while !text.is_char_boundary(end) {
240 end = end.saturating_sub(1);
241 }
242
243 if start < end {
244 start = end;
245 }
246 let start_anchor = buffer_snapshot.anchor_before(start);
247 let end_anchor = buffer_snapshot.anchor_after(end);
248 ranges.push(start_anchor..end_anchor);
249 }
250
251 let type_id = TypeId::of::<()>(); // Simple type ID for testing
252 highlights.insert(HighlightKey::Type(type_id), Arc::new((style, ranges)));
253 }
254
255 // Get all chunks and verify their bitmaps
256 let chunks =
257 CustomHighlightsChunks::new(0..buffer_snapshot.len(), false, None, &buffer_snapshot);
258
259 for chunk in chunks {
260 let chunk_text = chunk.text;
261 let chars_bitmap = chunk.chars;
262 let tabs_bitmap = chunk.tabs;
263
264 // Check empty chunks have empty bitmaps
265 if chunk_text.is_empty() {
266 assert_eq!(
267 chars_bitmap, 0,
268 "Empty chunk should have empty chars bitmap"
269 );
270 assert_eq!(tabs_bitmap, 0, "Empty chunk should have empty tabs bitmap");
271 continue;
272 }
273
274 // Verify that chunk text doesn't exceed 128 bytes
275 assert!(
276 chunk_text.len() <= 128,
277 "Chunk text length {} exceeds 128 bytes",
278 chunk_text.len()
279 );
280
281 // Verify chars bitmap
282 let char_indices = chunk_text
283 .char_indices()
284 .map(|(i, _)| i)
285 .collect::<Vec<_>>();
286
287 for byte_idx in 0..chunk_text.len() {
288 let should_have_bit = char_indices.contains(&byte_idx);
289 let has_bit = chars_bitmap & (1 << byte_idx) != 0;
290
291 if has_bit != should_have_bit {
292 eprintln!("Chunk text bytes: {:?}", chunk_text.as_bytes());
293 eprintln!("Char indices: {:?}", char_indices);
294 eprintln!("Chars bitmap: {:#b}", chars_bitmap);
295 assert_eq!(
296 has_bit, should_have_bit,
297 "Chars bitmap mismatch at byte index {} in chunk {:?}. Expected bit: {}, Got bit: {}",
298 byte_idx, chunk_text, should_have_bit, has_bit
299 );
300 }
301 }
302
303 // Verify tabs bitmap
304 for (byte_idx, byte) in chunk_text.bytes().enumerate() {
305 let is_tab = byte == b'\t';
306 let has_bit = tabs_bitmap & (1 << byte_idx) != 0;
307
308 if has_bit != is_tab {
309 eprintln!("Chunk text bytes: {:?}", chunk_text.as_bytes());
310 eprintln!("Tabs bitmap: {:#b}", tabs_bitmap);
311 assert_eq!(
312 has_bit, is_tab,
313 "Tabs bitmap mismatch at byte index {} in chunk {:?}. Byte: {:?}, Expected bit: {}, Got bit: {}",
314 byte_idx, chunk_text, byte as char, is_tab, has_bit
315 );
316 }
317 }
318 }
319 }
320}