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