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