1use super::wrap_map::{self, Edit as WrapEdit, Snapshot as WrapSnapshot, WrapPoint};
2use buffer::{rope, Anchor, Bias, Point, Rope, ToOffset};
3use gpui::fonts::HighlightStyle;
4use language::HighlightedChunk;
5use parking_lot::Mutex;
6use std::{cmp, collections::HashSet, iter, ops::Range, slice, sync::Arc};
7use sum_tree::SumTree;
8
9struct BlockMap {
10 blocks: Vec<(BlockId, Arc<Block>)>,
11 transforms: Mutex<SumTree<Transform>>,
12}
13
14struct BlockMapWriter<'a>(&'a mut BlockMap);
15
16struct BlockSnapshot {
17 wrap_snapshot: WrapSnapshot,
18 transforms: SumTree<Transform>,
19}
20
21#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
22struct BlockId(usize);
23
24#[derive(Copy, Clone, Debug, Default, Eq, Ord, PartialOrd, PartialEq)]
25pub struct BlockPoint(super::Point);
26
27struct Block {
28 id: BlockId,
29 position: Anchor,
30 text: Rope,
31 runs: Vec<(usize, HighlightStyle)>,
32 disposition: BlockDisposition,
33}
34
35#[derive(Clone)]
36struct BlockProperties<P, T>
37where
38 P: Clone,
39 T: Clone,
40{
41 position: P,
42 text: T,
43 runs: Vec<(usize, HighlightStyle)>,
44 disposition: BlockDisposition,
45}
46
47#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
48enum BlockDisposition {
49 Above,
50 Below,
51}
52
53#[derive(Clone)]
54struct Transform {
55 summary: TransformSummary,
56 block: Option<Arc<Block>>,
57}
58
59#[derive(Copy, Clone, Debug, Default)]
60struct TransformSummary {
61 input_rows: u32,
62 output_rows: u32,
63}
64
65struct HighlightedChunks<'a> {
66 transforms: sum_tree::Cursor<'a, Transform, (OutputRow, InputRow)>,
67 input_chunks: wrap_map::HighlightedChunks<'a>,
68 input_chunk: HighlightedChunk<'a>,
69 block_chunks: Option<BlockChunks<'a>>,
70 output_row: u32,
71 max_output_row: u32,
72}
73
74struct BlockChunks<'a> {
75 chunks: rope::Chunks<'a>,
76 runs: iter::Peekable<slice::Iter<'a, (usize, HighlightStyle)>>,
77 chunk: Option<&'a str>,
78 run_start: usize,
79 offset: usize,
80}
81
82#[derive(Copy, Clone, Default, Debug, PartialEq, Eq, PartialOrd, Ord)]
83struct InputRow(u32);
84
85#[derive(Copy, Clone, Default, Debug, PartialEq, Eq, PartialOrd, Ord)]
86struct OutputRow(u32);
87
88impl BlockMap {
89 fn new(wrap_snapshot: WrapSnapshot) -> Self {
90 Self {
91 blocks: Vec::new(),
92 transforms: Mutex::new(SumTree::from_item(
93 Transform::isomorphic(wrap_snapshot.max_point().row() + 1),
94 &(),
95 )),
96 }
97 }
98
99 fn read(&self, wrap_snapshot: WrapSnapshot, edits: Vec<WrapEdit>) -> BlockSnapshot {
100 self.sync(&wrap_snapshot, edits);
101 BlockSnapshot {
102 wrap_snapshot,
103 transforms: self.transforms.lock().clone(),
104 }
105 }
106
107 fn write(&mut self, wrap_snapshot: WrapSnapshot, edits: Vec<WrapEdit>) -> BlockMapWriter {
108 self.sync(&wrap_snapshot, edits);
109 BlockMapWriter(self)
110 }
111
112 fn sync(&self, wrap_snapshot: &WrapSnapshot, edits: Vec<WrapEdit>) {
113 let mut transforms = self.transforms.lock();
114 let mut new_transforms = SumTree::new();
115 let mut cursor = transforms.cursor::<InputRow>();
116 let mut edits = edits.into_iter().peekable();
117 while let Some(mut edit) = edits.next() {
118 new_transforms.push_tree(
119 cursor.slice(&InputRow(edit.old.start), Bias::Left, &()),
120 &(),
121 );
122
123 let transform_start = cursor.start().0;
124 edit.new.start -= edit.old.start - transform_start;
125 edit.old.start = transform_start;
126
127 loop {
128 if edit.old.end > cursor.start().0 {
129 cursor.seek(&InputRow(edit.old.end), Bias::Left, &());
130 cursor.next(&());
131 let transform_end = cursor.start().0;
132 edit.new.end += transform_end - edit.old.end;
133 edit.old.end = transform_end;
134 }
135
136 if let Some(next_edit) = edits.peek() {
137 if edit.old.end >= next_edit.old.start {
138 let delta = next_edit.new.len() as i32 - next_edit.old.len() as i32;
139 edit.old.end = cmp::max(next_edit.old.end, edit.old.end);
140 edit.new.end = (edit.new.end as i32 + delta) as u32;
141 edits.next();
142 } else {
143 break;
144 }
145 } else {
146 break;
147 }
148 }
149
150 // TODO: process injections
151
152 let new_transforms_end = new_transforms.summary().input_rows;
153 if new_transforms_end < edit.new.end {
154 new_transforms.push(
155 Transform::isomorphic(edit.new.end - new_transforms_end),
156 &(),
157 );
158 }
159 }
160 new_transforms.push_tree(cursor.suffix(&()), &());
161 drop(cursor);
162 *transforms = new_transforms;
163 }
164}
165
166impl BlockPoint {
167 fn row(&self) -> u32 {
168 self.0.row
169 }
170
171 fn row_mut(&mut self) -> &mut u32 {
172 &mut self.0.row
173 }
174
175 fn column(&self) -> u32 {
176 self.0.column
177 }
178
179 fn column_mut(&mut self) -> &mut u32 {
180 &mut self.0.column
181 }
182}
183
184impl<'a> BlockMapWriter<'a> {
185 pub fn insert<P, T>(
186 &self,
187 blocks: impl IntoIterator<Item = BlockProperties<P, T>>,
188 ) -> Vec<BlockId>
189 where
190 P: ToOffset + Clone,
191 T: Into<Rope> + Clone,
192 {
193 vec![]
194 }
195
196 pub fn remove(&self, ids: HashSet<BlockId>) {
197 //
198 }
199}
200
201impl BlockSnapshot {
202 #[cfg(test)]
203 fn text(&mut self) -> String {
204 self.highlighted_chunks_for_rows(0..(self.max_point().0.row + 1))
205 .map(|chunk| chunk.text)
206 .collect()
207 }
208
209 pub fn highlighted_chunks_for_rows(&mut self, rows: Range<u32>) -> HighlightedChunks {
210 let mut cursor = self.transforms.cursor::<(OutputRow, InputRow)>();
211 cursor.seek(&OutputRow(rows.start), Bias::Right, &());
212 let (input_start, output_start) = cursor.start();
213 let row_overshoot = rows.start - output_start.0;
214 let input_start_row = input_start.0 + row_overshoot;
215 let input_end_row = self
216 .to_wrap_point(BlockPoint(Point::new(rows.end, 0)))
217 .row();
218 let input_chunks = self
219 .wrap_snapshot
220 .highlighted_chunks_for_rows(input_start_row..input_end_row);
221 HighlightedChunks {
222 input_chunks,
223 input_chunk: Default::default(),
224 block_chunks: None,
225 transforms: cursor,
226 output_row: rows.start,
227 max_output_row: rows.end,
228 }
229 }
230
231 pub fn max_point(&self) -> BlockPoint {
232 self.to_block_point(self.wrap_snapshot.max_point())
233 }
234
235 pub fn to_block_point(&self, wrap_point: WrapPoint) -> BlockPoint {
236 let mut cursor = self.transforms.cursor::<(InputRow, OutputRow)>();
237 cursor.seek(&InputRow(wrap_point.row()), Bias::Left, &());
238 while let Some(item) = cursor.item() {
239 if item.is_isomorphic() {
240 break;
241 }
242 cursor.next(&());
243 }
244 let (input_start, output_start) = cursor.start();
245 let row_overshoot = wrap_point.row() - input_start.0;
246 BlockPoint(Point::new(
247 output_start.0 + row_overshoot,
248 wrap_point.column(),
249 ))
250 }
251
252 pub fn to_wrap_point(&self, block_point: BlockPoint) -> WrapPoint {
253 let mut cursor = self.transforms.cursor::<(OutputRow, InputRow)>();
254 cursor.seek(&OutputRow(block_point.0.row), Bias::Right, &());
255 let (output_start, input_start) = cursor.start();
256 let row_overshoot = block_point.0.row - output_start.0;
257 WrapPoint::new(input_start.0 + row_overshoot, block_point.0.column)
258 }
259}
260
261impl Transform {
262 fn isomorphic(rows: u32) -> Self {
263 Self {
264 summary: TransformSummary {
265 input_rows: rows,
266 output_rows: rows,
267 },
268 block: None,
269 }
270 }
271
272 fn is_isomorphic(&self) -> bool {
273 self.block.is_none()
274 }
275}
276
277impl<'a> Iterator for HighlightedChunks<'a> {
278 type Item = HighlightedChunk<'a>;
279
280 fn next(&mut self) -> Option<Self::Item> {
281 if self.output_row >= self.max_output_row {
282 return None;
283 }
284
285 if let Some(block_chunks) = self.block_chunks.as_mut() {
286 if let Some(mut block_chunk) = block_chunks.next() {
287 self.output_row += block_chunk.text.matches('\n').count() as u32;
288 return Some(block_chunk);
289 } else {
290 self.block_chunks.take();
291 }
292 }
293
294 let transform = self.transforms.item()?;
295 if let Some(block) = transform.block.as_ref() {
296 let block_start = self.transforms.start().0 .0;
297 let block_end = self.transforms.end(&()).0 .0;
298 let start_row_in_block = self.output_row - block_start;
299 let end_row_in_block = cmp::min(self.max_output_row, block_end) - block_start;
300 self.transforms.next(&());
301 let mut block_chunks = BlockChunks::new(block, start_row_in_block..end_row_in_block);
302 if let Some(block_chunk) = block_chunks.next() {
303 self.output_row += block_chunk.text.matches('\n').count() as u32;
304 return Some(block_chunk);
305 }
306 }
307
308 if self.input_chunk.text.is_empty() {
309 self.input_chunk = self.input_chunks.next().unwrap();
310 }
311
312 let transform_end = self.transforms.end(&()).0 .0;
313 let (prefix_rows, prefix_bytes) =
314 offset_for_row(self.input_chunk.text, transform_end - self.output_row);
315 self.output_row += prefix_rows;
316 let (prefix, suffix) = self.input_chunk.text.split_at(prefix_bytes);
317
318 self.input_chunk.text = suffix;
319 Some(HighlightedChunk {
320 text: prefix,
321 ..self.input_chunk
322 })
323 }
324}
325
326impl<'a> BlockChunks<'a> {
327 fn new(block: &'a Block, row_range: Range<u32>) -> Self {
328 let point_range = Point::new(row_range.start, 0)..Point::new(row_range.end, 0);
329 let offset_range = block.text.point_to_offset(point_range.start)
330 ..block.text.point_to_offset(point_range.end);
331
332 let mut runs = block.runs.iter().peekable();
333 let mut run_start = 0;
334 while let Some((run_len, _)) = runs.peek() {
335 let run_end = run_start + run_len;
336 if run_end <= offset_range.start {
337 run_start = run_end;
338 runs.next();
339 } else {
340 break;
341 }
342 }
343
344 Self {
345 chunk: None,
346 run_start,
347 chunks: block.text.chunks_in_range(offset_range.clone()),
348 runs,
349 offset: offset_range.start,
350 }
351 }
352}
353
354impl<'a> Iterator for BlockChunks<'a> {
355 type Item = HighlightedChunk<'a>;
356
357 fn next(&mut self) -> Option<Self::Item> {
358 if self.chunk.is_none() {
359 self.chunk = self.chunks.next();
360 }
361
362 let chunk = self.chunk?;
363 let mut chunk_len = chunk.len();
364 let mut highlight_style = None;
365 if let Some((run_len, style)) = self.runs.peek() {
366 highlight_style = Some(style.clone());
367 let run_end_in_chunk = self.run_start + run_len - self.offset;
368 if run_end_in_chunk <= chunk_len {
369 chunk_len = run_end_in_chunk;
370 self.run_start += run_len;
371 self.runs.next();
372 }
373 }
374
375 self.offset += chunk_len;
376 let (chunk, suffix) = chunk.split_at(chunk_len);
377 self.chunk = if suffix.is_empty() {
378 None
379 } else {
380 Some(suffix)
381 };
382
383 Some(HighlightedChunk {
384 text: chunk,
385 highlight_id: Default::default(),
386 diagnostic: None,
387 })
388 }
389}
390
391impl sum_tree::Item for Transform {
392 type Summary = TransformSummary;
393
394 fn summary(&self) -> Self::Summary {
395 self.summary
396 }
397}
398
399impl sum_tree::Summary for TransformSummary {
400 type Context = ();
401
402 fn add_summary(&mut self, summary: &Self, _: &()) {
403 self.input_rows += summary.input_rows;
404 self.output_rows += summary.output_rows;
405 }
406}
407
408impl<'a> sum_tree::Dimension<'a, TransformSummary> for InputRow {
409 fn add_summary(&mut self, summary: &'a TransformSummary, _: &()) {
410 self.0 += summary.input_rows;
411 }
412}
413
414impl<'a> sum_tree::Dimension<'a, TransformSummary> for OutputRow {
415 fn add_summary(&mut self, summary: &'a TransformSummary, _: &()) {
416 self.0 += summary.output_rows;
417 }
418}
419
420// Count the number of bytes prior to a target row.
421// If the string doesn't contain the target row, return the total number of rows it does contain.
422// Otherwise return the target row itself.
423fn offset_for_row(s: &str, target_row: u32) -> (u32, usize) {
424 assert!(target_row > 0);
425 let mut row = 0;
426 let mut offset = 0;
427 for (ix, line) in s.split('\n').enumerate() {
428 if ix > 0 {
429 row += 1;
430 offset += 1;
431 if row as u32 >= target_row {
432 break;
433 }
434 }
435 offset += line.len();
436 }
437 (row, offset)
438}
439
440#[cfg(test)]
441mod tests {
442 use super::*;
443 use crate::display_map::{fold_map::FoldMap, tab_map::TabMap, wrap_map::WrapMap};
444 use buffer::{RandomCharIter, ToPoint as _};
445 use language::Buffer;
446 use rand::prelude::*;
447 use std::env;
448
449 #[gpui::test(iterations = 100)]
450 fn test_random(cx: &mut gpui::MutableAppContext, mut rng: StdRng) {
451 let operations = env::var("OPERATIONS")
452 .map(|i| i.parse().expect("invalid `OPERATIONS` variable"))
453 .unwrap_or(10);
454
455 let wrap_width = Some(rng.gen_range(0.0..=1000.0));
456 let tab_size = 1;
457 let family_id = cx.font_cache().load_family(&["Helvetica"]).unwrap();
458 let font_id = cx
459 .font_cache()
460 .select_font(family_id, &Default::default())
461 .unwrap();
462 let font_size = 14.0;
463
464 log::info!("Tab size: {}", tab_size);
465 log::info!("Wrap width: {:?}", wrap_width);
466
467 let buffer = cx.add_model(|cx| {
468 let len = rng.gen_range(0..10);
469 let text = RandomCharIter::new(&mut rng).take(len).collect::<String>();
470 Buffer::new(0, text, cx)
471 });
472 let (fold_map, folds_snapshot) = FoldMap::new(buffer.clone(), cx);
473 let (tab_map, tabs_snapshot) = TabMap::new(folds_snapshot.clone(), tab_size);
474 let (wrap_map, wraps_snapshot) =
475 WrapMap::new(tabs_snapshot, font_id, font_size, wrap_width, cx);
476 let mut block_map = BlockMap::new(wraps_snapshot);
477 let mut expected_blocks = Vec::new();
478
479 for _ in 0..operations {
480 match rng.gen_range(0..=100) {
481 0..=19 => {
482 let wrap_width = if rng.gen_bool(0.2) {
483 None
484 } else {
485 Some(rng.gen_range(0.0..=1000.0))
486 };
487 log::info!("Setting wrap width to {:?}", wrap_width);
488 wrap_map.update(cx, |map, cx| map.set_wrap_width(wrap_width, cx));
489 }
490 20..=39 => {
491 let block_count = rng.gen_range(1..=4);
492 let block_properties = (0..block_count)
493 .map(|_| {
494 let buffer = buffer.read(cx);
495 let position = buffer.anchor_before(rng.gen_range(0..=buffer.len()));
496
497 let len = rng.gen_range(0..10);
498 let text = Rope::from(
499 RandomCharIter::new(&mut rng)
500 .take(len)
501 .collect::<String>()
502 .as_str(),
503 );
504 BlockProperties {
505 position,
506 text,
507 runs: Vec::<(usize, HighlightStyle)>::new(),
508 disposition: if rng.gen() {
509 BlockDisposition::Above
510 } else {
511 BlockDisposition::Below
512 },
513 }
514 })
515 .collect::<Vec<_>>();
516
517 let (folds_snapshot, fold_edits) = fold_map.read(cx);
518 let (tabs_snapshot, tab_edits) = tab_map.sync(folds_snapshot, fold_edits);
519 let (wraps_snapshot, wrap_edits) = wrap_map.update(cx, |wrap_map, cx| {
520 wrap_map.sync(tabs_snapshot, tab_edits, cx)
521 });
522 let block_map = block_map.write(wraps_snapshot, wrap_edits);
523
524 expected_blocks.extend(
525 block_map
526 .insert(block_properties.clone())
527 .into_iter()
528 .zip(block_properties),
529 );
530 }
531 40..=59 => {
532 let block_count = rng.gen_range(1..=4.min(expected_blocks.len()));
533 let block_ids_to_remove = (0..block_count)
534 .map(|_| {
535 expected_blocks
536 .remove(rng.gen_range(0..expected_blocks.len()))
537 .0
538 })
539 .collect();
540
541 let (folds_snapshot, fold_edits) = fold_map.read(cx);
542 let (tabs_snapshot, tab_edits) = tab_map.sync(folds_snapshot, fold_edits);
543 let (wraps_snapshot, wrap_edits) = wrap_map.update(cx, |wrap_map, cx| {
544 wrap_map.sync(tabs_snapshot, tab_edits, cx)
545 });
546 let block_map = block_map.write(wraps_snapshot, wrap_edits);
547
548 block_map.remove(block_ids_to_remove);
549 }
550 _ => {
551 buffer.update(cx, |buffer, _| buffer.randomly_edit(&mut rng, 5));
552 }
553 }
554
555 let (folds_snapshot, fold_edits) = fold_map.read(cx);
556 let (tabs_snapshot, tab_edits) = tab_map.sync(folds_snapshot, fold_edits);
557 let (wraps_snapshot, wrap_edits) = wrap_map.update(cx, |wrap_map, cx| {
558 wrap_map.sync(tabs_snapshot, tab_edits, cx)
559 });
560 let mut blocks_snapshot = block_map.read(wraps_snapshot.clone(), wrap_edits);
561 assert_eq!(
562 blocks_snapshot.transforms.summary().input_rows,
563 wraps_snapshot.max_point().row() + 1
564 );
565
566 let buffer = buffer.read(cx);
567 let mut sorted_blocks = expected_blocks
568 .iter()
569 .cloned()
570 .map(|(_, block)| BlockProperties {
571 position: block.position.to_point(buffer),
572 text: block.text,
573 runs: block.runs,
574 disposition: block.disposition,
575 })
576 .collect::<Vec<_>>();
577 sorted_blocks.sort_unstable_by_key(|block| (block.position.row, block.disposition));
578 let mut sorted_blocks = sorted_blocks.into_iter().peekable();
579
580 let mut expected_text = String::new();
581 let input_text = wraps_snapshot.text();
582 for (row, input_line) in input_text.split('\n').enumerate() {
583 let row = row as u32;
584 if row > 0 {
585 expected_text.push('\n');
586 }
587
588 while let Some(block) = sorted_blocks.peek() {
589 if block.position.row == row && block.disposition == BlockDisposition::Above {
590 expected_text.extend(block.text.chunks());
591 expected_text.push('\n');
592 sorted_blocks.next();
593 } else {
594 break;
595 }
596 }
597
598 expected_text.push_str(input_line);
599
600 while let Some(block) = sorted_blocks.peek() {
601 if block.position.row == row && block.disposition == BlockDisposition::Below {
602 expected_text.push('\n');
603 expected_text.extend(block.text.chunks());
604 sorted_blocks.next();
605 } else {
606 break;
607 }
608 }
609 }
610
611 assert_eq!(blocks_snapshot.text(), expected_text);
612 }
613 }
614}