1use super::wrap_map::{self, Edit as WrapEdit, Snapshot as WrapSnapshot, WrapPoint};
2use buffer::{rope, Anchor, Bias, Edit, Point, Rope, ToOffset, ToPoint as _};
3use gpui::{fonts::HighlightStyle, AppContext, ModelHandle};
4use language::{Buffer, Chunk};
5use parking_lot::Mutex;
6use std::{
7 cmp::{self, Ordering},
8 collections::HashSet,
9 iter,
10 ops::Range,
11 slice,
12 sync::{
13 atomic::{AtomicUsize, Ordering::SeqCst},
14 Arc,
15 },
16};
17use sum_tree::SumTree;
18use theme::SyntaxTheme;
19
20pub struct BlockMap {
21 buffer: ModelHandle<Buffer>,
22 next_block_id: AtomicUsize,
23 wrap_snapshot: Mutex<WrapSnapshot>,
24 blocks: Vec<Arc<Block>>,
25 transforms: Mutex<SumTree<Transform>>,
26}
27
28pub struct BlockMapWriter<'a>(&'a mut BlockMap);
29
30pub struct BlockSnapshot {
31 wrap_snapshot: WrapSnapshot,
32 transforms: SumTree<Transform>,
33}
34
35#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
36pub struct BlockId(usize);
37
38#[derive(Copy, Clone, Debug, Default, Eq, Ord, PartialOrd, PartialEq)]
39pub struct BlockPoint(pub super::Point);
40
41#[derive(Copy, Clone, Debug, Default, Eq, Ord, PartialOrd, PartialEq)]
42struct BlockRow(u32);
43
44#[derive(Copy, Clone, Debug, Default, Eq, Ord, PartialOrd, PartialEq)]
45struct WrapRow(u32);
46
47#[derive(Debug)]
48struct Block {
49 id: BlockId,
50 position: Anchor,
51 text: Rope,
52 runs: Vec<(usize, HighlightStyle)>,
53 disposition: BlockDisposition,
54}
55
56#[derive(Clone)]
57pub struct BlockProperties<P, T>
58where
59 P: Clone,
60 T: Clone,
61{
62 pub position: P,
63 pub text: T,
64 pub runs: Vec<(usize, HighlightStyle)>,
65 pub disposition: BlockDisposition,
66}
67
68#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
69pub enum BlockDisposition {
70 Above,
71 Below,
72}
73
74#[derive(Clone, Debug)]
75struct Transform {
76 summary: TransformSummary,
77 block: Option<Arc<Block>>,
78}
79
80#[derive(Clone, Debug, Default)]
81struct TransformSummary {
82 input_rows: u32,
83 output_rows: u32,
84 longest_row_in_block: u32,
85 longest_row_in_block_chars: u32,
86}
87
88pub struct Chunks<'a> {
89 transforms: sum_tree::Cursor<'a, Transform, (BlockRow, WrapRow)>,
90 input_chunks: wrap_map::Chunks<'a>,
91 input_chunk: Chunk<'a>,
92 block_chunks: Option<BlockChunks<'a>>,
93 output_row: u32,
94 max_output_row: u32,
95}
96
97struct BlockChunks<'a> {
98 chunks: rope::Chunks<'a>,
99 runs: iter::Peekable<slice::Iter<'a, (usize, HighlightStyle)>>,
100 chunk: Option<&'a str>,
101 run_start: usize,
102 offset: usize,
103}
104
105pub struct BufferRows<'a> {
106 transforms: sum_tree::Cursor<'a, Transform, (BlockRow, WrapRow)>,
107 input_buffer_rows: wrap_map::BufferRows<'a>,
108 output_row: u32,
109 started: bool,
110}
111
112impl BlockMap {
113 pub fn new(buffer: ModelHandle<Buffer>, wrap_snapshot: WrapSnapshot) -> Self {
114 Self {
115 buffer,
116 next_block_id: AtomicUsize::new(0),
117 blocks: Vec::new(),
118 transforms: Mutex::new(SumTree::from_item(
119 Transform::isomorphic(wrap_snapshot.text_summary().lines.row + 1),
120 &(),
121 )),
122 wrap_snapshot: Mutex::new(wrap_snapshot),
123 }
124 }
125
126 pub fn read(
127 &self,
128 wrap_snapshot: WrapSnapshot,
129 edits: Vec<WrapEdit>,
130 cx: &AppContext,
131 ) -> BlockSnapshot {
132 self.sync(&wrap_snapshot, edits, cx);
133 *self.wrap_snapshot.lock() = wrap_snapshot.clone();
134 BlockSnapshot {
135 wrap_snapshot,
136 transforms: self.transforms.lock().clone(),
137 }
138 }
139
140 pub fn write(
141 &mut self,
142 wrap_snapshot: WrapSnapshot,
143 edits: Vec<WrapEdit>,
144 cx: &AppContext,
145 ) -> BlockMapWriter {
146 self.sync(&wrap_snapshot, edits, cx);
147 *self.wrap_snapshot.lock() = wrap_snapshot;
148 BlockMapWriter(self)
149 }
150
151 pub fn sync(&self, wrap_snapshot: &WrapSnapshot, edits: Vec<WrapEdit>, cx: &AppContext) {
152 if edits.is_empty() {
153 return;
154 }
155
156 let buffer = self.buffer.read(cx);
157 let mut transforms = self.transforms.lock();
158 let mut new_transforms = SumTree::new();
159 let old_row_count = transforms.summary().input_rows;
160 let new_row_count = wrap_snapshot.max_point().row() + 1;
161 let mut cursor = transforms.cursor::<WrapRow>();
162 let mut last_block_ix = 0;
163 let mut blocks_in_edit = Vec::new();
164 let mut edits = edits.into_iter().peekable();
165
166 while let Some(edit) = edits.next() {
167 // Preserve any old transforms that precede this edit.
168 let old_start = WrapRow(edit.old.start);
169 let new_start = WrapRow(edit.new.start);
170 new_transforms.push_tree(cursor.slice(&old_start, Bias::Left, &()), &());
171 if let Some(transform) = cursor.item() {
172 if transform.is_isomorphic() && old_start == cursor.end(&()) {
173 new_transforms.push(transform.clone(), &());
174 cursor.next(&());
175 while let Some(transform) = cursor.item() {
176 if transform
177 .block
178 .as_ref()
179 .map_or(false, |b| b.disposition.is_below())
180 {
181 new_transforms.push(transform.clone(), &());
182 cursor.next(&());
183 } else {
184 break;
185 }
186 }
187 }
188 }
189
190 // Preserve any portion of an old transform that precedes this edit.
191 let extent_before_edit = old_start.0 - cursor.start().0;
192 push_isomorphic(&mut new_transforms, extent_before_edit);
193
194 // Skip over any old transforms that intersect this edit.
195 let mut old_end = WrapRow(edit.old.end);
196 let mut new_end = WrapRow(edit.new.end);
197 cursor.seek(&old_end, Bias::Left, &());
198 cursor.next(&());
199 if old_end == *cursor.start() {
200 while let Some(transform) = cursor.item() {
201 if transform
202 .block
203 .as_ref()
204 .map_or(false, |b| b.disposition.is_below())
205 {
206 cursor.next(&());
207 } else {
208 break;
209 }
210 }
211 }
212
213 // Combine this edit with any subsequent edits that intersect the same transform.
214 while let Some(next_edit) = edits.peek() {
215 if next_edit.old.start <= cursor.start().0 {
216 old_end = WrapRow(next_edit.old.end);
217 new_end = WrapRow(next_edit.new.end);
218 cursor.seek(&old_end, Bias::Left, &());
219 cursor.next(&());
220 if old_end == *cursor.start() {
221 while let Some(transform) = cursor.item() {
222 if transform
223 .block
224 .as_ref()
225 .map_or(false, |b| b.disposition.is_below())
226 {
227 cursor.next(&());
228 } else {
229 break;
230 }
231 }
232 }
233 edits.next();
234 } else {
235 break;
236 }
237 }
238
239 // Find the blocks within this edited region.
240 let new_start = wrap_snapshot.to_point(WrapPoint::new(new_start.0, 0), Bias::Left);
241 let start_anchor = buffer.anchor_before(new_start);
242 let start_block_ix = match self.blocks[last_block_ix..].binary_search_by(|probe| {
243 probe
244 .position
245 .cmp(&start_anchor, buffer)
246 .unwrap()
247 .then(Ordering::Greater)
248 }) {
249 Ok(ix) | Err(ix) => last_block_ix + ix,
250 };
251 let end_block_ix = if new_end.0 > wrap_snapshot.max_point().row() {
252 self.blocks.len()
253 } else {
254 let new_end = wrap_snapshot.to_point(WrapPoint::new(new_end.0, 0), Bias::Left);
255 let end_anchor = buffer.anchor_before(new_end);
256 match self.blocks[start_block_ix..].binary_search_by(|probe| {
257 probe
258 .position
259 .cmp(&end_anchor, buffer)
260 .unwrap()
261 .then(Ordering::Greater)
262 }) {
263 Ok(ix) | Err(ix) => start_block_ix + ix,
264 }
265 };
266 last_block_ix = end_block_ix;
267 blocks_in_edit.clear();
268 blocks_in_edit.extend(
269 self.blocks[start_block_ix..end_block_ix]
270 .iter()
271 .map(|block| {
272 let mut position = block.position.to_point(buffer);
273 match block.disposition {
274 BlockDisposition::Above => position.column = 0,
275 BlockDisposition::Below => {
276 position.column = buffer.line_len(position.row)
277 }
278 }
279 let position = wrap_snapshot.from_point(position, Bias::Left);
280 (position.row(), block)
281 }),
282 );
283 blocks_in_edit.sort_unstable_by_key(|(row, block)| (*row, block.disposition, block.id));
284
285 // For each of these blocks, insert a new isomorphic transform preceding the block,
286 // and then insert the block itself.
287 for (block_row, block) in blocks_in_edit.iter().copied() {
288 let insertion_row = match block.disposition {
289 BlockDisposition::Above => block_row,
290 BlockDisposition::Below => block_row + 1,
291 };
292 let extent_before_block = insertion_row - new_transforms.summary().input_rows;
293 push_isomorphic(&mut new_transforms, extent_before_block);
294 new_transforms.push(Transform::block(block.clone()), &());
295 }
296
297 old_end = WrapRow(old_end.0.min(old_row_count));
298 new_end = WrapRow(new_end.0.min(new_row_count));
299
300 // Insert an isomorphic transform after the final block.
301 let extent_after_last_block = new_end.0 - new_transforms.summary().input_rows;
302 push_isomorphic(&mut new_transforms, extent_after_last_block);
303
304 // Preserve any portion of the old transform after this edit.
305 let extent_after_edit = cursor.start().0 - old_end.0;
306 push_isomorphic(&mut new_transforms, extent_after_edit);
307 }
308
309 new_transforms.push_tree(cursor.suffix(&()), &());
310 debug_assert_eq!(
311 new_transforms.summary().input_rows,
312 wrap_snapshot.max_point().row() + 1
313 );
314
315 drop(cursor);
316 *transforms = new_transforms;
317 }
318}
319
320fn push_isomorphic(tree: &mut SumTree<Transform>, rows: u32) {
321 if rows == 0 {
322 return;
323 }
324
325 let mut extent = Some(rows);
326 tree.update_last(
327 |last_transform| {
328 if last_transform.is_isomorphic() {
329 let extent = extent.take().unwrap();
330 last_transform.summary.input_rows += extent;
331 last_transform.summary.output_rows += extent;
332 }
333 },
334 &(),
335 );
336 if let Some(extent) = extent {
337 tree.push(Transform::isomorphic(extent), &());
338 }
339}
340
341impl BlockPoint {
342 pub fn new(row: u32, column: u32) -> Self {
343 Self(Point::new(row, column))
344 }
345}
346
347impl std::ops::Deref for BlockPoint {
348 type Target = Point;
349
350 fn deref(&self) -> &Self::Target {
351 &self.0
352 }
353}
354
355impl std::ops::DerefMut for BlockPoint {
356 fn deref_mut(&mut self) -> &mut Self::Target {
357 &mut self.0
358 }
359}
360
361impl<'a> BlockMapWriter<'a> {
362 pub fn insert<P, T>(
363 &mut self,
364 blocks: impl IntoIterator<Item = BlockProperties<P, T>>,
365 cx: &AppContext,
366 ) -> Vec<BlockId>
367 where
368 P: ToOffset + Clone,
369 T: Into<Rope> + Clone,
370 {
371 let buffer = self.0.buffer.read(cx);
372 let mut ids = Vec::new();
373 let mut edits = Vec::<Edit<u32>>::new();
374 let wrap_snapshot = &*self.0.wrap_snapshot.lock();
375
376 for block in blocks {
377 let id = BlockId(self.0.next_block_id.fetch_add(1, SeqCst));
378 ids.push(id);
379
380 let position = buffer.anchor_before(block.position);
381 let point = position.to_point(buffer);
382 let start_row = wrap_snapshot
383 .from_point(Point::new(point.row, 0), Bias::Left)
384 .row();
385 let end_row = if point.row == buffer.max_point().row {
386 wrap_snapshot.max_point().row() + 1
387 } else {
388 wrap_snapshot
389 .from_point(Point::new(point.row + 1, 0), Bias::Left)
390 .row()
391 };
392
393 let block_ix = match self
394 .0
395 .blocks
396 .binary_search_by(|probe| probe.position.cmp(&position, buffer).unwrap())
397 {
398 Ok(ix) | Err(ix) => ix,
399 };
400 self.0.blocks.insert(
401 block_ix,
402 Arc::new(Block {
403 id,
404 position,
405 text: block.text.into(),
406 runs: block.runs,
407 disposition: block.disposition,
408 }),
409 );
410
411 if let Err(edit_ix) = edits.binary_search_by_key(&start_row, |edit| edit.old.start) {
412 edits.insert(
413 edit_ix,
414 Edit {
415 old: start_row..end_row,
416 new: start_row..end_row,
417 },
418 );
419 }
420 }
421
422 self.0.sync(wrap_snapshot, edits, cx);
423 ids
424 }
425
426 pub fn remove(&mut self, block_ids: HashSet<BlockId>, cx: &AppContext) {
427 let buffer = self.0.buffer.read(cx);
428 let wrap_snapshot = &*self.0.wrap_snapshot.lock();
429 let mut edits = Vec::new();
430 let mut last_block_buffer_row = None;
431 self.0.blocks.retain(|block| {
432 if block_ids.contains(&block.id) {
433 let buffer_row = block.position.to_point(buffer).row;
434 if last_block_buffer_row != Some(buffer_row) {
435 last_block_buffer_row = Some(buffer_row);
436 let start_row = wrap_snapshot
437 .from_point(Point::new(buffer_row, 0), Bias::Left)
438 .row();
439 let end_row = wrap_snapshot
440 .from_point(
441 Point::new(buffer_row, buffer.line_len(buffer_row)),
442 Bias::Left,
443 )
444 .row()
445 + 1;
446 edits.push(Edit {
447 old: start_row..end_row,
448 new: start_row..end_row,
449 })
450 }
451 false
452 } else {
453 true
454 }
455 });
456 self.0.sync(wrap_snapshot, edits, cx);
457 }
458}
459
460impl BlockSnapshot {
461 #[cfg(test)]
462 fn text(&mut self) -> String {
463 self.chunks(0..self.transforms.summary().output_rows, None)
464 .map(|chunk| chunk.text)
465 .collect()
466 }
467
468 pub fn chunks<'a>(&'a self, rows: Range<u32>, theme: Option<&'a SyntaxTheme>) -> Chunks<'a> {
469 let max_output_row = cmp::min(rows.end, self.transforms.summary().output_rows);
470 let mut cursor = self.transforms.cursor::<(BlockRow, WrapRow)>();
471 let input_end = {
472 cursor.seek(&BlockRow(rows.end), Bias::Right, &());
473 let overshoot = if cursor
474 .item()
475 .map_or(false, |transform| transform.is_isomorphic())
476 {
477 rows.end - cursor.start().0 .0
478 } else {
479 0
480 };
481 cursor.start().1 .0 + overshoot
482 };
483 let input_start = {
484 cursor.seek(&BlockRow(rows.start), Bias::Right, &());
485 let overshoot = if cursor
486 .item()
487 .map_or(false, |transform| transform.is_isomorphic())
488 {
489 rows.start - cursor.start().0 .0
490 } else {
491 0
492 };
493 cursor.start().1 .0 + overshoot
494 };
495 Chunks {
496 input_chunks: self.wrap_snapshot.chunks(input_start..input_end, theme),
497 input_chunk: Default::default(),
498 block_chunks: None,
499 transforms: cursor,
500 output_row: rows.start,
501 max_output_row,
502 }
503 }
504
505 pub fn buffer_rows(&self, start_row: u32) -> BufferRows {
506 let mut cursor = self.transforms.cursor::<(BlockRow, WrapRow)>();
507 cursor.seek(&BlockRow(start_row), Bias::Right, &());
508 let (input_start, output_start) = cursor.start();
509 let overshoot = if cursor.item().map_or(false, |t| t.is_isomorphic()) {
510 start_row - output_start.0
511 } else {
512 0
513 };
514 let input_start_row = input_start.0 + overshoot;
515 BufferRows {
516 transforms: cursor,
517 input_buffer_rows: self.wrap_snapshot.buffer_rows(input_start_row),
518 output_row: start_row,
519 started: false,
520 }
521 }
522
523 pub fn max_point(&self) -> BlockPoint {
524 let row = self.transforms.summary().output_rows - 1;
525 BlockPoint::new(row, self.line_len(row))
526 }
527
528 pub fn longest_row(&self) -> u32 {
529 let input_row = self.wrap_snapshot.longest_row();
530 let input_row_chars = self.wrap_snapshot.line_char_count(input_row);
531 let TransformSummary {
532 longest_row_in_block: block_row,
533 longest_row_in_block_chars: block_row_chars,
534 ..
535 } = &self.transforms.summary();
536
537 if *block_row_chars > input_row_chars {
538 *block_row
539 } else {
540 self.to_block_point(WrapPoint::new(input_row, 0)).row
541 }
542 }
543
544 pub fn line_len(&self, row: u32) -> u32 {
545 let mut cursor = self.transforms.cursor::<(BlockRow, WrapRow)>();
546 cursor.seek(&BlockRow(row), Bias::Right, &());
547 if let Some(transform) = cursor.item() {
548 let (output_start, input_start) = cursor.start();
549 let overshoot = row - output_start.0;
550 if let Some(block) = &transform.block {
551 block.text.line_len(overshoot)
552 } else {
553 self.wrap_snapshot.line_len(input_start.0 + overshoot)
554 }
555 } else {
556 panic!("row out of range");
557 }
558 }
559
560 pub fn is_block_line(&self, row: u32) -> bool {
561 let mut cursor = self.transforms.cursor::<(BlockRow, WrapRow)>();
562 cursor.seek(&BlockRow(row), Bias::Right, &());
563 cursor.item().map_or(false, |t| t.block.is_some())
564 }
565
566 pub fn clip_point(&self, point: BlockPoint, bias: Bias) -> BlockPoint {
567 let mut cursor = self.transforms.cursor::<(BlockRow, WrapRow)>();
568 cursor.seek(&BlockRow(point.row), Bias::Right, &());
569
570 let max_input_row = WrapRow(self.transforms.summary().input_rows);
571 let search_left =
572 (bias == Bias::Left && cursor.start().1 .0 > 0) || cursor.end(&()).1 == max_input_row;
573
574 loop {
575 if let Some(transform) = cursor.item() {
576 if transform.is_isomorphic() {
577 let (output_start_row, input_start_row) = cursor.start();
578 let (output_end_row, input_end_row) = cursor.end(&());
579
580 if point.row >= output_end_row.0 {
581 return BlockPoint::new(
582 output_end_row.0 - 1,
583 self.wrap_snapshot.line_len(input_end_row.0 - 1),
584 );
585 }
586
587 let output_start = Point::new(output_start_row.0, 0);
588 if point.0 > output_start {
589 let output_overshoot = point.0 - output_start;
590 let input_start = Point::new(input_start_row.0, 0);
591 let input_point = self
592 .wrap_snapshot
593 .clip_point(WrapPoint(input_start + output_overshoot), bias);
594 let input_overshoot = input_point.0 - input_start;
595 return BlockPoint(output_start + input_overshoot);
596 } else {
597 return BlockPoint(output_start);
598 }
599 } else if search_left {
600 cursor.prev(&());
601 } else {
602 cursor.next(&());
603 }
604 } else {
605 return self.max_point();
606 }
607 }
608 }
609
610 pub fn to_block_point(&self, wrap_point: WrapPoint) -> BlockPoint {
611 let mut cursor = self.transforms.cursor::<(WrapRow, BlockRow)>();
612 cursor.seek(&WrapRow(wrap_point.row()), Bias::Right, &());
613 if let Some(transform) = cursor.item() {
614 debug_assert!(transform.is_isomorphic());
615 } else {
616 return self.max_point();
617 }
618
619 let (input_start_row, output_start_row) = cursor.start();
620 let input_start = Point::new(input_start_row.0, 0);
621 let output_start = Point::new(output_start_row.0, 0);
622 let input_overshoot = wrap_point.0 - input_start;
623 BlockPoint(output_start + input_overshoot)
624 }
625
626 pub fn to_wrap_point(&self, block_point: BlockPoint) -> WrapPoint {
627 let mut cursor = self.transforms.cursor::<(BlockRow, WrapRow)>();
628 cursor.seek(&BlockRow(block_point.row), Bias::Right, &());
629 if let Some(transform) = cursor.item() {
630 match transform.block.as_ref().map(|b| b.disposition) {
631 Some(BlockDisposition::Above) => WrapPoint::new(cursor.start().1 .0, 0),
632 Some(BlockDisposition::Below) => {
633 let wrap_row = cursor.start().1 .0 - 1;
634 WrapPoint::new(wrap_row, self.wrap_snapshot.line_len(wrap_row))
635 }
636 None => {
637 let overshoot = block_point.row - cursor.start().0 .0;
638 let wrap_row = cursor.start().1 .0 + overshoot;
639 WrapPoint::new(wrap_row, block_point.column)
640 }
641 }
642 } else {
643 self.wrap_snapshot.max_point()
644 }
645 }
646}
647
648impl Transform {
649 fn isomorphic(rows: u32) -> Self {
650 Self {
651 summary: TransformSummary {
652 input_rows: rows,
653 output_rows: rows,
654 longest_row_in_block: 0,
655 longest_row_in_block_chars: 0,
656 },
657 block: None,
658 }
659 }
660
661 fn block(block: Arc<Block>) -> Self {
662 let text_summary = block.text.summary();
663 Self {
664 summary: TransformSummary {
665 input_rows: 0,
666 output_rows: text_summary.lines.row + 1,
667 longest_row_in_block: text_summary.longest_row,
668 longest_row_in_block_chars: text_summary.longest_row_chars,
669 },
670 block: Some(block),
671 }
672 }
673
674 fn is_isomorphic(&self) -> bool {
675 self.block.is_none()
676 }
677}
678
679impl<'a> Iterator for Chunks<'a> {
680 type Item = Chunk<'a>;
681
682 fn next(&mut self) -> Option<Self::Item> {
683 if self.output_row >= self.max_output_row {
684 return None;
685 }
686
687 if let Some(block_chunks) = self.block_chunks.as_mut() {
688 if let Some(block_chunk) = block_chunks.next() {
689 self.output_row += block_chunk.text.matches('\n').count() as u32;
690 return Some(block_chunk);
691 } else {
692 self.block_chunks.take();
693 self.output_row += 1;
694 if self.output_row < self.max_output_row {
695 return Some(Chunk {
696 text: "\n",
697 ..Default::default()
698 });
699 } else {
700 return None;
701 }
702 }
703 }
704
705 let transform = self.transforms.item()?;
706 if let Some(block) = transform.block.as_ref() {
707 let block_start = self.transforms.start().0 .0;
708 let block_end = self.transforms.end(&()).0 .0;
709 let start_in_block = self.output_row - block_start;
710 let end_in_block = cmp::min(self.max_output_row, block_end) - block_start;
711 self.transforms.next(&());
712 self.block_chunks = Some(BlockChunks::new(block, start_in_block..end_in_block));
713 return self.next();
714 }
715
716 if self.input_chunk.text.is_empty() {
717 if let Some(input_chunk) = self.input_chunks.next() {
718 self.input_chunk = input_chunk;
719 } else {
720 self.output_row += 1;
721 if self.output_row < self.max_output_row {
722 self.transforms.next(&());
723 return Some(Chunk {
724 text: "\n",
725 ..Default::default()
726 });
727 } else {
728 return None;
729 }
730 }
731 }
732
733 let transform_end = self.transforms.end(&()).0 .0;
734 let (prefix_rows, prefix_bytes) =
735 offset_for_row(self.input_chunk.text, transform_end - self.output_row);
736 self.output_row += prefix_rows;
737 let (prefix, suffix) = self.input_chunk.text.split_at(prefix_bytes);
738 self.input_chunk.text = suffix;
739 if self.output_row == transform_end {
740 self.transforms.next(&());
741 }
742
743 Some(Chunk {
744 text: prefix,
745 ..self.input_chunk
746 })
747 }
748}
749
750impl<'a> BlockChunks<'a> {
751 fn new(block: &'a Block, rows: Range<u32>) -> Self {
752 let offset_range = block.text.point_to_offset(Point::new(rows.start, 0))
753 ..block.text.point_to_offset(Point::new(rows.end, 0));
754
755 let mut runs = block.runs.iter().peekable();
756 let mut run_start = 0;
757 while let Some((run_len, _)) = runs.peek() {
758 let run_end = run_start + run_len;
759 if run_end <= offset_range.start {
760 run_start = run_end;
761 runs.next();
762 } else {
763 break;
764 }
765 }
766
767 Self {
768 chunk: None,
769 run_start,
770 chunks: block.text.chunks_in_range(offset_range.clone()),
771 runs,
772 offset: offset_range.start,
773 }
774 }
775}
776
777impl<'a> Iterator for BlockChunks<'a> {
778 type Item = Chunk<'a>;
779
780 fn next(&mut self) -> Option<Self::Item> {
781 if self.chunk.is_none() {
782 self.chunk = self.chunks.next();
783 }
784
785 let chunk = self.chunk?;
786 let mut chunk_len = chunk.len();
787 let mut highlight_style = None;
788 if let Some((run_len, style)) = self.runs.peek() {
789 highlight_style = Some(style.clone());
790 let run_end_in_chunk = self.run_start + run_len - self.offset;
791 if run_end_in_chunk <= chunk_len {
792 chunk_len = run_end_in_chunk;
793 self.run_start += run_len;
794 self.runs.next();
795 }
796 }
797
798 self.offset += chunk_len;
799 let (chunk, suffix) = chunk.split_at(chunk_len);
800 self.chunk = if suffix.is_empty() {
801 None
802 } else {
803 Some(suffix)
804 };
805
806 Some(Chunk {
807 text: chunk,
808 highlight_style,
809 diagnostic: None,
810 })
811 }
812}
813
814impl<'a> Iterator for BufferRows<'a> {
815 type Item = Option<u32>;
816
817 fn next(&mut self) -> Option<Self::Item> {
818 if self.started {
819 self.output_row += 1;
820 } else {
821 self.started = true;
822 }
823
824 if self.output_row >= self.transforms.end(&()).0 .0 {
825 self.transforms.next(&());
826 }
827
828 let transform = self.transforms.item()?;
829 if transform.is_isomorphic() {
830 Some(self.input_buffer_rows.next().unwrap())
831 } else {
832 Some(None)
833 }
834 }
835}
836
837impl sum_tree::Item for Transform {
838 type Summary = TransformSummary;
839
840 fn summary(&self) -> Self::Summary {
841 self.summary.clone()
842 }
843}
844
845impl sum_tree::Summary for TransformSummary {
846 type Context = ();
847
848 fn add_summary(&mut self, summary: &Self, _: &()) {
849 if summary.longest_row_in_block_chars > self.longest_row_in_block_chars {
850 self.longest_row_in_block_chars = summary.longest_row_in_block_chars;
851 self.longest_row_in_block = self.output_rows + summary.longest_row_in_block;
852 }
853
854 self.input_rows += summary.input_rows;
855 self.output_rows += summary.output_rows;
856 }
857}
858
859impl<'a> sum_tree::Dimension<'a, TransformSummary> for WrapRow {
860 fn add_summary(&mut self, summary: &'a TransformSummary, _: &()) {
861 self.0 += summary.input_rows;
862 }
863}
864
865impl<'a> sum_tree::Dimension<'a, TransformSummary> for BlockRow {
866 fn add_summary(&mut self, summary: &'a TransformSummary, _: &()) {
867 self.0 += summary.output_rows;
868 }
869}
870
871impl BlockDisposition {
872 fn is_below(&self) -> bool {
873 matches!(self, BlockDisposition::Below)
874 }
875}
876
877// Count the number of bytes prior to a target point. If the string doesn't contain the target
878// point, return its total extent. Otherwise return the target point itself.
879fn offset_for_row(s: &str, target: u32) -> (u32, usize) {
880 let mut row = 0;
881 let mut offset = 0;
882 for (ix, line) in s.split('\n').enumerate() {
883 if ix > 0 {
884 row += 1;
885 offset += 1;
886 }
887 if row >= target {
888 break;
889 }
890 offset += line.len() as usize;
891 }
892 (row, offset)
893}
894
895#[cfg(test)]
896mod tests {
897 use super::*;
898 use crate::display_map::{fold_map::FoldMap, tab_map::TabMap, wrap_map::WrapMap};
899 use buffer::RandomCharIter;
900 use language::Buffer;
901 use rand::prelude::*;
902 use std::env;
903
904 #[gpui::test]
905 fn test_offset_for_row() {
906 assert_eq!(offset_for_row("", 0), (0, 0));
907 assert_eq!(offset_for_row("", 1), (0, 0));
908 assert_eq!(offset_for_row("abcd", 0), (0, 0));
909 assert_eq!(offset_for_row("abcd", 1), (0, 4));
910 assert_eq!(offset_for_row("\n", 0), (0, 0));
911 assert_eq!(offset_for_row("\n", 1), (1, 1));
912 assert_eq!(offset_for_row("abc\ndef\nghi", 0), (0, 0));
913 assert_eq!(offset_for_row("abc\ndef\nghi", 1), (1, 4));
914 assert_eq!(offset_for_row("abc\ndef\nghi", 2), (2, 8));
915 assert_eq!(offset_for_row("abc\ndef\nghi", 3), (2, 11));
916 }
917
918 #[gpui::test]
919 fn test_basic_blocks(cx: &mut gpui::MutableAppContext) {
920 let family_id = cx.font_cache().load_family(&["Helvetica"]).unwrap();
921 let font_id = cx
922 .font_cache()
923 .select_font(family_id, &Default::default())
924 .unwrap();
925
926 let text = "aaa\nbbb\nccc\nddd";
927
928 let buffer = cx.add_model(|cx| Buffer::new(0, text, cx));
929 let (fold_map, folds_snapshot) = FoldMap::new(buffer.clone(), cx);
930 let (tab_map, tabs_snapshot) = TabMap::new(folds_snapshot.clone(), 1);
931 let (wrap_map, wraps_snapshot) = WrapMap::new(tabs_snapshot, font_id, 14.0, None, cx);
932 let mut block_map = BlockMap::new(buffer.clone(), wraps_snapshot.clone());
933
934 let mut writer = block_map.write(wraps_snapshot.clone(), vec![], cx);
935 writer.insert(
936 vec![
937 BlockProperties {
938 position: Point::new(1, 0),
939 text: "BLOCK 1",
940 disposition: BlockDisposition::Above,
941 runs: vec![],
942 },
943 BlockProperties {
944 position: Point::new(1, 2),
945 text: "BLOCK 2",
946 disposition: BlockDisposition::Above,
947 runs: vec![],
948 },
949 BlockProperties {
950 position: Point::new(3, 2),
951 text: "BLOCK 3",
952 disposition: BlockDisposition::Below,
953 runs: vec![],
954 },
955 ],
956 cx,
957 );
958
959 let mut snapshot = block_map.read(wraps_snapshot, vec![], cx);
960 assert_eq!(
961 snapshot.text(),
962 "aaa\nBLOCK 1\nBLOCK 2\nbbb\nccc\nddd\nBLOCK 3"
963 );
964 assert_eq!(
965 snapshot.to_block_point(WrapPoint::new(0, 3)),
966 BlockPoint::new(0, 3)
967 );
968 assert_eq!(
969 snapshot.to_block_point(WrapPoint::new(1, 0)),
970 BlockPoint::new(3, 0)
971 );
972 assert_eq!(
973 snapshot.to_block_point(WrapPoint::new(3, 3)),
974 BlockPoint::new(5, 3)
975 );
976
977 assert_eq!(
978 snapshot.to_wrap_point(BlockPoint::new(0, 3)),
979 WrapPoint::new(0, 3)
980 );
981 assert_eq!(
982 snapshot.to_wrap_point(BlockPoint::new(1, 0)),
983 WrapPoint::new(1, 0)
984 );
985 assert_eq!(
986 snapshot.to_wrap_point(BlockPoint::new(3, 0)),
987 WrapPoint::new(1, 0)
988 );
989 assert_eq!(
990 snapshot.to_wrap_point(BlockPoint::new(6, 0)),
991 WrapPoint::new(3, 3)
992 );
993
994 assert_eq!(
995 snapshot.clip_point(BlockPoint::new(1, 0), Bias::Left),
996 BlockPoint::new(0, 3)
997 );
998 assert_eq!(
999 snapshot.clip_point(BlockPoint::new(1, 0), Bias::Right),
1000 BlockPoint::new(3, 0)
1001 );
1002 assert_eq!(
1003 snapshot.clip_point(BlockPoint::new(1, 1), Bias::Left),
1004 BlockPoint::new(0, 3)
1005 );
1006 assert_eq!(
1007 snapshot.clip_point(BlockPoint::new(1, 1), Bias::Right),
1008 BlockPoint::new(3, 0)
1009 );
1010 assert_eq!(
1011 snapshot.clip_point(BlockPoint::new(3, 0), Bias::Left),
1012 BlockPoint::new(3, 0)
1013 );
1014 assert_eq!(
1015 snapshot.clip_point(BlockPoint::new(3, 0), Bias::Right),
1016 BlockPoint::new(3, 0)
1017 );
1018 assert_eq!(
1019 snapshot.clip_point(BlockPoint::new(5, 3), Bias::Left),
1020 BlockPoint::new(5, 3)
1021 );
1022 assert_eq!(
1023 snapshot.clip_point(BlockPoint::new(5, 3), Bias::Right),
1024 BlockPoint::new(5, 3)
1025 );
1026 assert_eq!(
1027 snapshot.clip_point(BlockPoint::new(6, 0), Bias::Left),
1028 BlockPoint::new(5, 3)
1029 );
1030 assert_eq!(
1031 snapshot.clip_point(BlockPoint::new(6, 0), Bias::Right),
1032 BlockPoint::new(5, 3)
1033 );
1034
1035 assert_eq!(
1036 snapshot.buffer_rows(0).collect::<Vec<_>>(),
1037 &[Some(0), None, None, Some(1), Some(2), Some(3), None]
1038 );
1039
1040 // Insert a line break, separating two block decorations into separate
1041 // lines.
1042 buffer.update(cx, |buffer, cx| {
1043 buffer.edit([Point::new(1, 1)..Point::new(1, 1)], "!!!\n", cx)
1044 });
1045
1046 let (folds_snapshot, fold_edits) = fold_map.read(cx);
1047 let (tabs_snapshot, tab_edits) = tab_map.sync(folds_snapshot, fold_edits);
1048 let (wraps_snapshot, wrap_edits) = wrap_map.update(cx, |wrap_map, cx| {
1049 wrap_map.sync(tabs_snapshot, tab_edits, cx)
1050 });
1051 let mut snapshot = block_map.read(wraps_snapshot, wrap_edits, cx);
1052 assert_eq!(
1053 snapshot.text(),
1054 "aaa\nBLOCK 1\nb!!!\nBLOCK 2\nbb\nccc\nddd\nBLOCK 3"
1055 );
1056 }
1057
1058 #[gpui::test]
1059 fn test_blocks_on_wrapped_lines(cx: &mut gpui::MutableAppContext) {
1060 let family_id = cx.font_cache().load_family(&["Helvetica"]).unwrap();
1061 let font_id = cx
1062 .font_cache()
1063 .select_font(family_id, &Default::default())
1064 .unwrap();
1065
1066 let text = "one two three\nfour five six\nseven eight";
1067
1068 let buffer = cx.add_model(|cx| Buffer::new(0, text, cx));
1069 let (_, folds_snapshot) = FoldMap::new(buffer.clone(), cx);
1070 let (_, tabs_snapshot) = TabMap::new(folds_snapshot.clone(), 1);
1071 let (_, wraps_snapshot) = WrapMap::new(tabs_snapshot, font_id, 14.0, Some(60.), cx);
1072 let mut block_map = BlockMap::new(buffer.clone(), wraps_snapshot.clone());
1073
1074 let mut writer = block_map.write(wraps_snapshot.clone(), vec![], cx);
1075 writer.insert(
1076 vec![
1077 BlockProperties {
1078 position: Point::new(1, 12),
1079 text: "<BLOCK 1",
1080 disposition: BlockDisposition::Above,
1081 runs: vec![],
1082 },
1083 BlockProperties {
1084 position: Point::new(1, 1),
1085 text: ">BLOCK 2",
1086 disposition: BlockDisposition::Below,
1087 runs: vec![],
1088 },
1089 ],
1090 cx,
1091 );
1092
1093 // Blocks with an 'above' disposition go above their corresponding buffer line.
1094 // Blocks with a 'below' disposition go below their corresponding buffer line.
1095 let mut snapshot = block_map.read(wraps_snapshot, vec![], cx);
1096 assert_eq!(
1097 snapshot.text(),
1098 "one two \nthree\n<BLOCK 1\nfour five \nsix\n>BLOCK 2\nseven \neight"
1099 );
1100 }
1101
1102 #[gpui::test(iterations = 100)]
1103 fn test_random_blocks(cx: &mut gpui::MutableAppContext, mut rng: StdRng) {
1104 let operations = env::var("OPERATIONS")
1105 .map(|i| i.parse().expect("invalid `OPERATIONS` variable"))
1106 .unwrap_or(10);
1107
1108 let wrap_width = if rng.gen_bool(0.2) {
1109 None
1110 } else {
1111 Some(rng.gen_range(0.0..=100.0))
1112 };
1113 let tab_size = 1;
1114 let family_id = cx.font_cache().load_family(&["Helvetica"]).unwrap();
1115 let font_id = cx
1116 .font_cache()
1117 .select_font(family_id, &Default::default())
1118 .unwrap();
1119 let font_size = 14.0;
1120
1121 log::info!("Wrap width: {:?}", wrap_width);
1122
1123 let buffer = cx.add_model(|cx| {
1124 let len = rng.gen_range(0..10);
1125 let text = RandomCharIter::new(&mut rng).take(len).collect::<String>();
1126 log::info!("initial buffer text: {:?}", text);
1127 Buffer::new(0, text, cx)
1128 });
1129 let (fold_map, folds_snapshot) = FoldMap::new(buffer.clone(), cx);
1130 let (tab_map, tabs_snapshot) = TabMap::new(folds_snapshot.clone(), tab_size);
1131 let (wrap_map, wraps_snapshot) =
1132 WrapMap::new(tabs_snapshot, font_id, font_size, wrap_width, cx);
1133 let mut block_map = BlockMap::new(buffer.clone(), wraps_snapshot);
1134 let mut expected_blocks = Vec::new();
1135
1136 for _ in 0..operations {
1137 match rng.gen_range(0..=100) {
1138 0..=19 => {
1139 let wrap_width = if rng.gen_bool(0.2) {
1140 None
1141 } else {
1142 Some(rng.gen_range(0.0..=100.0))
1143 };
1144 log::info!("Setting wrap width to {:?}", wrap_width);
1145 wrap_map.update(cx, |map, cx| map.set_wrap_width(wrap_width, cx));
1146 }
1147 20..=39 => {
1148 let block_count = rng.gen_range(1..=1);
1149 let block_properties = (0..block_count)
1150 .map(|_| {
1151 let buffer = buffer.read(cx);
1152 let position = buffer.anchor_before(
1153 buffer.clip_offset(rng.gen_range(0..=buffer.len()), Bias::Left),
1154 );
1155
1156 let len = rng.gen_range(0..10);
1157 let mut text = Rope::from(
1158 RandomCharIter::new(&mut rng)
1159 .take(len)
1160 .collect::<String>()
1161 .to_uppercase()
1162 .as_str(),
1163 );
1164 let disposition = if rng.gen() {
1165 text.push_front("<");
1166 BlockDisposition::Above
1167 } else {
1168 text.push_front(">");
1169 BlockDisposition::Below
1170 };
1171 log::info!(
1172 "inserting block {:?} {:?} with text {:?}",
1173 disposition,
1174 position.to_point(buffer),
1175 text.to_string()
1176 );
1177 BlockProperties {
1178 position,
1179 text,
1180 runs: Vec::<(usize, HighlightStyle)>::new(),
1181 disposition,
1182 }
1183 })
1184 .collect::<Vec<_>>();
1185
1186 let (folds_snapshot, fold_edits) = fold_map.read(cx);
1187 let (tabs_snapshot, tab_edits) = tab_map.sync(folds_snapshot, fold_edits);
1188 let (wraps_snapshot, wrap_edits) = wrap_map.update(cx, |wrap_map, cx| {
1189 wrap_map.sync(tabs_snapshot, tab_edits, cx)
1190 });
1191 let mut block_map = block_map.write(wraps_snapshot, wrap_edits, cx);
1192 let block_ids = block_map.insert(block_properties.clone(), cx);
1193 for (block_id, props) in block_ids.into_iter().zip(block_properties) {
1194 expected_blocks.push((block_id, props));
1195 }
1196 }
1197 40..=59 if !expected_blocks.is_empty() => {
1198 let block_count = rng.gen_range(1..=4.min(expected_blocks.len()));
1199 let block_ids_to_remove = (0..block_count)
1200 .map(|_| {
1201 expected_blocks
1202 .remove(rng.gen_range(0..expected_blocks.len()))
1203 .0
1204 })
1205 .collect();
1206
1207 let (folds_snapshot, fold_edits) = fold_map.read(cx);
1208 let (tabs_snapshot, tab_edits) = tab_map.sync(folds_snapshot, fold_edits);
1209 let (wraps_snapshot, wrap_edits) = wrap_map.update(cx, |wrap_map, cx| {
1210 wrap_map.sync(tabs_snapshot, tab_edits, cx)
1211 });
1212 let mut block_map = block_map.write(wraps_snapshot, wrap_edits, cx);
1213 block_map.remove(block_ids_to_remove, cx);
1214 }
1215 _ => {
1216 buffer.update(cx, |buffer, _| {
1217 buffer.randomly_edit(&mut rng, 1);
1218 log::info!("buffer text: {:?}", buffer.text());
1219 });
1220 }
1221 }
1222
1223 let (folds_snapshot, fold_edits) = fold_map.read(cx);
1224 let (tabs_snapshot, tab_edits) = tab_map.sync(folds_snapshot, fold_edits);
1225 let (wraps_snapshot, wrap_edits) = wrap_map.update(cx, |wrap_map, cx| {
1226 wrap_map.sync(tabs_snapshot, tab_edits, cx)
1227 });
1228 let mut blocks_snapshot = block_map.read(wraps_snapshot.clone(), wrap_edits, cx);
1229 assert_eq!(
1230 blocks_snapshot.transforms.summary().input_rows,
1231 wraps_snapshot.max_point().row() + 1
1232 );
1233 log::info!("blocks text: {:?}", blocks_snapshot.text());
1234
1235 let buffer = buffer.read(cx);
1236 let mut sorted_blocks = expected_blocks
1237 .iter()
1238 .cloned()
1239 .map(|(id, block)| {
1240 let mut position = block.position.to_point(buffer);
1241 match block.disposition {
1242 BlockDisposition::Above => {
1243 position.column = 0;
1244 }
1245 BlockDisposition::Below => {
1246 position.column = buffer.line_len(position.row);
1247 }
1248 };
1249 let row = wraps_snapshot.from_point(position, Bias::Left).row();
1250 (
1251 id,
1252 BlockProperties {
1253 position: row,
1254 text: block.text,
1255 runs: block.runs,
1256 disposition: block.disposition,
1257 },
1258 )
1259 })
1260 .collect::<Vec<_>>();
1261 sorted_blocks
1262 .sort_unstable_by_key(|(id, block)| (block.position, block.disposition, *id));
1263 let mut sorted_blocks = sorted_blocks.into_iter().peekable();
1264
1265 let mut expected_buffer_rows = Vec::new();
1266 let mut expected_text = String::new();
1267 let input_text = wraps_snapshot.text();
1268 for (row, input_line) in input_text.split('\n').enumerate() {
1269 let row = row as u32;
1270 if row > 0 {
1271 expected_text.push('\n');
1272 }
1273
1274 let buffer_row = wraps_snapshot
1275 .to_point(WrapPoint::new(row, 0), Bias::Left)
1276 .row;
1277
1278 while let Some((_, block)) = sorted_blocks.peek() {
1279 if block.position == row && block.disposition == BlockDisposition::Above {
1280 let text = block.text.to_string();
1281 expected_text.push_str(&text);
1282 expected_text.push('\n');
1283 for _ in text.split('\n') {
1284 expected_buffer_rows.push(None);
1285 }
1286 sorted_blocks.next();
1287 } else {
1288 break;
1289 }
1290 }
1291
1292 let soft_wrapped = wraps_snapshot.to_tab_point(WrapPoint::new(row, 0)).column() > 0;
1293 expected_buffer_rows.push(if soft_wrapped { None } else { Some(buffer_row) });
1294 expected_text.push_str(input_line);
1295
1296 while let Some((_, block)) = sorted_blocks.peek() {
1297 if block.position == row && block.disposition == BlockDisposition::Below {
1298 let text = block.text.to_string();
1299 expected_text.push('\n');
1300 expected_text.push_str(&text);
1301 for _ in text.split('\n') {
1302 expected_buffer_rows.push(None);
1303 }
1304 sorted_blocks.next();
1305 } else {
1306 break;
1307 }
1308 }
1309 }
1310
1311 let expected_lines = expected_text.split('\n').collect::<Vec<_>>();
1312 let expected_row_count = expected_lines.len();
1313 for start_row in 0..expected_row_count {
1314 let expected_text = expected_lines[start_row..].join("\n");
1315 let actual_text = blocks_snapshot
1316 .chunks(start_row as u32..expected_row_count as u32, None)
1317 .map(|chunk| chunk.text)
1318 .collect::<String>();
1319 assert_eq!(
1320 actual_text, expected_text,
1321 "incorrect text starting from row {}",
1322 start_row
1323 );
1324 }
1325
1326 let mut expected_longest_rows = Vec::new();
1327 let mut longest_line_len = -1_isize;
1328 for (row, line) in expected_lines.iter().enumerate() {
1329 let row = row as u32;
1330
1331 assert_eq!(
1332 blocks_snapshot.line_len(row),
1333 line.len() as u32,
1334 "invalid line len for row {}",
1335 row
1336 );
1337
1338 let line_char_count = line.chars().count() as isize;
1339 match line_char_count.cmp(&longest_line_len) {
1340 Ordering::Less => {}
1341 Ordering::Equal => expected_longest_rows.push(row),
1342 Ordering::Greater => {
1343 longest_line_len = line_char_count;
1344 expected_longest_rows.clear();
1345 expected_longest_rows.push(row);
1346 }
1347 }
1348 }
1349
1350 log::info!("getting longest row >>>>>>>>>>>>>>>>>>>>>>>>");
1351 let longest_row = blocks_snapshot.longest_row();
1352 assert!(
1353 expected_longest_rows.contains(&longest_row),
1354 "incorrect longest row {}. expected {:?} with length {}",
1355 longest_row,
1356 expected_longest_rows,
1357 longest_line_len,
1358 );
1359
1360 for row in 0..=blocks_snapshot.wrap_snapshot.max_point().row() {
1361 let wrap_point = WrapPoint::new(row, 0);
1362 let block_point = blocks_snapshot.to_block_point(wrap_point);
1363 assert_eq!(blocks_snapshot.to_wrap_point(block_point), wrap_point);
1364 }
1365 assert_eq!(
1366 blocks_snapshot.buffer_rows(0).collect::<Vec<_>>(),
1367 expected_buffer_rows
1368 );
1369
1370 let mut block_point = BlockPoint::new(0, 0);
1371 for c in expected_text.chars() {
1372 let left_point = blocks_snapshot.clip_point(block_point, Bias::Left);
1373 let right_point = blocks_snapshot.clip_point(block_point, Bias::Right);
1374
1375 assert_eq!(
1376 blocks_snapshot.to_block_point(blocks_snapshot.to_wrap_point(left_point)),
1377 left_point
1378 );
1379 assert_eq!(
1380 blocks_snapshot.to_block_point(blocks_snapshot.to_wrap_point(right_point)),
1381 right_point
1382 );
1383
1384 if c == '\n' {
1385 block_point.0 += Point::new(1, 0);
1386 } else {
1387 block_point.column += c.len_utf8() as u32;
1388 }
1389 }
1390 }
1391 }
1392}