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_chars = self.wrap_snapshot.line_char_count(input_row);
532 let TransformSummary {
533 longest_row_in_block: block_row,
534 longest_row_in_block_chars: block_row_chars,
535 ..
536 } = &self.transforms.summary();
537
538 if *block_row_chars > input_row_chars {
539 *block_row
540 } else {
541 self.to_block_point(WrapPoint::new(input_row, 0)).row
542 }
543 }
544
545 pub fn line_len(&self, row: u32) -> u32 {
546 let mut cursor = self.transforms.cursor::<(BlockRow, WrapRow)>();
547 cursor.seek(&BlockRow(row), Bias::Right, &());
548 if let Some(transform) = cursor.item() {
549 let (output_start, input_start) = cursor.start();
550 let overshoot = row - output_start.0;
551 if let Some(block) = &transform.block {
552 block.text.line_len(overshoot)
553 } else {
554 self.wrap_snapshot.line_len(input_start.0 + overshoot)
555 }
556 } else {
557 panic!("row out of range");
558 }
559 }
560
561 pub fn is_block_line(&self, row: u32) -> bool {
562 let mut cursor = self.transforms.cursor::<(BlockRow, WrapRow)>();
563 cursor.seek(&BlockRow(row), Bias::Right, &());
564 cursor.item().map_or(false, |t| t.block.is_some())
565 }
566
567 pub fn clip_point(&self, point: BlockPoint, bias: Bias) -> BlockPoint {
568 let mut cursor = self.transforms.cursor::<(BlockRow, WrapRow)>();
569 cursor.seek(&BlockRow(point.row), Bias::Right, &());
570
571 let max_input_row = WrapRow(self.transforms.summary().input_rows);
572 let search_left =
573 (bias == Bias::Left && cursor.start().1 .0 > 0) || cursor.end(&()).1 == max_input_row;
574
575 loop {
576 if let Some(transform) = cursor.item() {
577 if transform.is_isomorphic() {
578 let (output_start_row, input_start_row) = cursor.start();
579 let (output_end_row, input_end_row) = cursor.end(&());
580
581 if point.row >= output_end_row.0 {
582 return BlockPoint::new(
583 output_end_row.0 - 1,
584 self.wrap_snapshot.line_len(input_end_row.0 - 1),
585 );
586 }
587
588 let output_start = Point::new(output_start_row.0, 0);
589 if point.0 > output_start {
590 let output_overshoot = point.0 - output_start;
591 let input_start = Point::new(input_start_row.0, 0);
592 let input_point = self
593 .wrap_snapshot
594 .clip_point(WrapPoint(input_start + output_overshoot), bias);
595 let input_overshoot = input_point.0 - input_start;
596 return BlockPoint(output_start + input_overshoot);
597 } else {
598 return BlockPoint(output_start);
599 }
600 } else if search_left {
601 cursor.prev(&());
602 } else {
603 cursor.next(&());
604 }
605 } else {
606 return self.max_point();
607 }
608 }
609 }
610
611 pub fn to_block_point(&self, wrap_point: WrapPoint) -> BlockPoint {
612 let mut cursor = self.transforms.cursor::<(WrapRow, BlockRow)>();
613 cursor.seek(&WrapRow(wrap_point.row()), Bias::Right, &());
614 if let Some(transform) = cursor.item() {
615 debug_assert!(transform.is_isomorphic());
616 } else {
617 return self.max_point();
618 }
619
620 let (input_start_row, output_start_row) = cursor.start();
621 let input_start = Point::new(input_start_row.0, 0);
622 let output_start = Point::new(output_start_row.0, 0);
623 let input_overshoot = wrap_point.0 - input_start;
624 BlockPoint(output_start + input_overshoot)
625 }
626
627 pub fn to_wrap_point(&self, block_point: BlockPoint) -> WrapPoint {
628 let mut cursor = self.transforms.cursor::<(BlockRow, WrapRow)>();
629 cursor.seek(&BlockRow(block_point.row), Bias::Right, &());
630 if let Some(transform) = cursor.item() {
631 match transform.block.as_ref().map(|b| b.disposition) {
632 Some(BlockDisposition::Above) => WrapPoint::new(cursor.start().1 .0, 0),
633 Some(BlockDisposition::Below) => {
634 let wrap_row = cursor.start().1 .0 - 1;
635 WrapPoint::new(wrap_row, self.wrap_snapshot.line_len(wrap_row))
636 }
637 None => {
638 let overshoot = block_point.row - cursor.start().0 .0;
639 let wrap_row = cursor.start().1 .0 + overshoot;
640 WrapPoint::new(wrap_row, block_point.column)
641 }
642 }
643 } else {
644 self.wrap_snapshot.max_point()
645 }
646 }
647}
648
649impl Transform {
650 fn isomorphic(rows: u32) -> Self {
651 Self {
652 summary: TransformSummary {
653 input_rows: rows,
654 output_rows: rows,
655 longest_row_in_block: 0,
656 longest_row_in_block_chars: 0,
657 },
658 block: None,
659 }
660 }
661
662 fn block(block: Arc<Block>) -> Self {
663 let text_summary = block.text.summary();
664 Self {
665 summary: TransformSummary {
666 input_rows: 0,
667 output_rows: text_summary.lines.row + 1,
668 longest_row_in_block: text_summary.longest_row,
669 longest_row_in_block_chars: text_summary.longest_row_chars,
670 },
671 block: Some(block),
672 }
673 }
674
675 fn is_isomorphic(&self) -> bool {
676 self.block.is_none()
677 }
678}
679
680impl<'a> Iterator for Chunks<'a> {
681 type Item = Chunk<'a>;
682
683 fn next(&mut self) -> Option<Self::Item> {
684 if self.output_row >= self.max_output_row {
685 return None;
686 }
687
688 if let Some(block_chunks) = self.block_chunks.as_mut() {
689 if let Some(block_chunk) = block_chunks.next() {
690 self.output_row += block_chunk.text.matches('\n').count() as u32;
691 return Some(block_chunk);
692 } else {
693 self.block_chunks.take();
694 self.output_row += 1;
695 if self.output_row < self.max_output_row {
696 return Some(Chunk {
697 text: "\n",
698 ..Default::default()
699 });
700 } else {
701 return None;
702 }
703 }
704 }
705
706 let transform = self.transforms.item()?;
707 if let Some(block) = transform.block.as_ref() {
708 let block_start = self.transforms.start().0 .0;
709 let block_end = self.transforms.end(&()).0 .0;
710 let start_in_block = self.output_row - block_start;
711 let end_in_block = cmp::min(self.max_output_row, block_end) - block_start;
712 self.transforms.next(&());
713 self.block_chunks = Some(BlockChunks::new(block, start_in_block..end_in_block));
714 return self.next();
715 }
716
717 if self.input_chunk.text.is_empty() {
718 if let Some(input_chunk) = self.input_chunks.next() {
719 self.input_chunk = input_chunk;
720 } else {
721 self.output_row += 1;
722 if self.output_row < self.max_output_row {
723 self.transforms.next(&());
724 return Some(Chunk {
725 text: "\n",
726 ..Default::default()
727 });
728 } else {
729 return None;
730 }
731 }
732 }
733
734 let transform_end = self.transforms.end(&()).0 .0;
735 let (prefix_rows, prefix_bytes) =
736 offset_for_row(self.input_chunk.text, transform_end - self.output_row);
737 self.output_row += prefix_rows;
738 let (prefix, suffix) = self.input_chunk.text.split_at(prefix_bytes);
739 self.input_chunk.text = suffix;
740 if self.output_row == transform_end {
741 self.transforms.next(&());
742 }
743
744 Some(Chunk {
745 text: prefix,
746 ..self.input_chunk
747 })
748 }
749}
750
751impl<'a> BlockChunks<'a> {
752 fn new(block: &'a Block, rows: Range<u32>) -> Self {
753 let offset_range = block.text.point_to_offset(Point::new(rows.start, 0))
754 ..block.text.point_to_offset(Point::new(rows.end, 0));
755
756 let mut runs = block.runs.iter().peekable();
757 let mut run_start = 0;
758 while let Some((run_len, _)) = runs.peek() {
759 let run_end = run_start + run_len;
760 if run_end <= offset_range.start {
761 run_start = run_end;
762 runs.next();
763 } else {
764 break;
765 }
766 }
767
768 Self {
769 chunk: None,
770 run_start,
771 chunks: block.text.chunks_in_range(offset_range.clone()),
772 runs,
773 offset: offset_range.start,
774 }
775 }
776}
777
778impl<'a> Iterator for BlockChunks<'a> {
779 type Item = Chunk<'a>;
780
781 fn next(&mut self) -> Option<Self::Item> {
782 if self.chunk.is_none() {
783 self.chunk = self.chunks.next();
784 }
785
786 let chunk = self.chunk?;
787 let mut chunk_len = chunk.len();
788 // let mut highlight_style = None;
789 if let Some((run_len, _)) = self.runs.peek() {
790 // highlight_style = Some(style.clone());
791 let run_end_in_chunk = self.run_start + run_len - self.offset;
792 if run_end_in_chunk <= chunk_len {
793 chunk_len = run_end_in_chunk;
794 self.run_start += run_len;
795 self.runs.next();
796 }
797 }
798
799 self.offset += chunk_len;
800 let (chunk, suffix) = chunk.split_at(chunk_len);
801 self.chunk = if suffix.is_empty() {
802 None
803 } else {
804 Some(suffix)
805 };
806
807 Some(Chunk {
808 text: chunk,
809 highlight_id: Default::default(),
810 diagnostic: None,
811 })
812 }
813}
814
815impl<'a> Iterator for BufferRows<'a> {
816 type Item = Option<u32>;
817
818 fn next(&mut self) -> Option<Self::Item> {
819 if self.started {
820 self.output_row += 1;
821 } else {
822 self.started = true;
823 }
824
825 if self.output_row >= self.transforms.end(&()).0 .0 {
826 self.transforms.next(&());
827 }
828
829 let transform = self.transforms.item()?;
830 if transform.is_isomorphic() {
831 Some(self.input_buffer_rows.next().unwrap())
832 } else {
833 Some(None)
834 }
835 }
836}
837
838impl sum_tree::Item for Transform {
839 type Summary = TransformSummary;
840
841 fn summary(&self) -> Self::Summary {
842 self.summary.clone()
843 }
844}
845
846impl sum_tree::Summary for TransformSummary {
847 type Context = ();
848
849 fn add_summary(&mut self, summary: &Self, _: &()) {
850 if summary.longest_row_in_block_chars > self.longest_row_in_block_chars {
851 self.longest_row_in_block_chars = summary.longest_row_in_block_chars;
852 self.longest_row_in_block = self.output_rows + summary.longest_row_in_block;
853 }
854
855 self.input_rows += summary.input_rows;
856 self.output_rows += summary.output_rows;
857 }
858}
859
860impl<'a> sum_tree::Dimension<'a, TransformSummary> for WrapRow {
861 fn add_summary(&mut self, summary: &'a TransformSummary, _: &()) {
862 self.0 += summary.input_rows;
863 }
864}
865
866impl<'a> sum_tree::Dimension<'a, TransformSummary> for BlockRow {
867 fn add_summary(&mut self, summary: &'a TransformSummary, _: &()) {
868 self.0 += summary.output_rows;
869 }
870}
871
872impl BlockDisposition {
873 fn is_below(&self) -> bool {
874 matches!(self, BlockDisposition::Below)
875 }
876}
877
878// Count the number of bytes prior to a target point. If the string doesn't contain the target
879// point, return its total extent. Otherwise return the target point itself.
880fn offset_for_row(s: &str, target: u32) -> (u32, usize) {
881 let mut row = 0;
882 let mut offset = 0;
883 for (ix, line) in s.split('\n').enumerate() {
884 if ix > 0 {
885 row += 1;
886 offset += 1;
887 }
888 if row >= target {
889 break;
890 }
891 offset += line.len() as usize;
892 }
893 (row, offset)
894}
895
896#[cfg(test)]
897mod tests {
898 use super::*;
899 use crate::display_map::{fold_map::FoldMap, tab_map::TabMap, wrap_map::WrapMap};
900 use buffer::RandomCharIter;
901 use language::Buffer;
902 use rand::prelude::*;
903 use std::env;
904
905 #[gpui::test]
906 fn test_offset_for_row() {
907 assert_eq!(offset_for_row("", 0), (0, 0));
908 assert_eq!(offset_for_row("", 1), (0, 0));
909 assert_eq!(offset_for_row("abcd", 0), (0, 0));
910 assert_eq!(offset_for_row("abcd", 1), (0, 4));
911 assert_eq!(offset_for_row("\n", 0), (0, 0));
912 assert_eq!(offset_for_row("\n", 1), (1, 1));
913 assert_eq!(offset_for_row("abc\ndef\nghi", 0), (0, 0));
914 assert_eq!(offset_for_row("abc\ndef\nghi", 1), (1, 4));
915 assert_eq!(offset_for_row("abc\ndef\nghi", 2), (2, 8));
916 assert_eq!(offset_for_row("abc\ndef\nghi", 3), (2, 11));
917 }
918
919 #[gpui::test]
920 fn test_basic_blocks(cx: &mut gpui::MutableAppContext) {
921 let family_id = cx.font_cache().load_family(&["Helvetica"]).unwrap();
922 let font_id = cx
923 .font_cache()
924 .select_font(family_id, &Default::default())
925 .unwrap();
926
927 let text = "aaa\nbbb\nccc\nddd";
928
929 let buffer = cx.add_model(|cx| Buffer::new(0, text, cx));
930 let (fold_map, folds_snapshot) = FoldMap::new(buffer.clone(), cx);
931 let (tab_map, tabs_snapshot) = TabMap::new(folds_snapshot.clone(), 1);
932 let (wrap_map, wraps_snapshot) = WrapMap::new(tabs_snapshot, font_id, 14.0, None, cx);
933 let mut block_map = BlockMap::new(buffer.clone(), wraps_snapshot.clone());
934
935 let mut writer = block_map.write(wraps_snapshot.clone(), vec![], cx);
936 writer.insert(
937 vec![
938 BlockProperties {
939 position: Point::new(1, 0),
940 text: "BLOCK 1",
941 disposition: BlockDisposition::Above,
942 runs: vec![],
943 },
944 BlockProperties {
945 position: Point::new(1, 2),
946 text: "BLOCK 2",
947 disposition: BlockDisposition::Above,
948 runs: vec![],
949 },
950 BlockProperties {
951 position: Point::new(3, 2),
952 text: "BLOCK 3",
953 disposition: BlockDisposition::Below,
954 runs: vec![],
955 },
956 ],
957 cx,
958 );
959
960 let mut snapshot = block_map.read(wraps_snapshot, vec![], cx);
961 assert_eq!(
962 snapshot.text(),
963 "aaa\nBLOCK 1\nBLOCK 2\nbbb\nccc\nddd\nBLOCK 3"
964 );
965 assert_eq!(
966 snapshot.to_block_point(WrapPoint::new(0, 3)),
967 BlockPoint::new(0, 3)
968 );
969 assert_eq!(
970 snapshot.to_block_point(WrapPoint::new(1, 0)),
971 BlockPoint::new(3, 0)
972 );
973 assert_eq!(
974 snapshot.to_block_point(WrapPoint::new(3, 3)),
975 BlockPoint::new(5, 3)
976 );
977
978 assert_eq!(
979 snapshot.to_wrap_point(BlockPoint::new(0, 3)),
980 WrapPoint::new(0, 3)
981 );
982 assert_eq!(
983 snapshot.to_wrap_point(BlockPoint::new(1, 0)),
984 WrapPoint::new(1, 0)
985 );
986 assert_eq!(
987 snapshot.to_wrap_point(BlockPoint::new(3, 0)),
988 WrapPoint::new(1, 0)
989 );
990 assert_eq!(
991 snapshot.to_wrap_point(BlockPoint::new(6, 0)),
992 WrapPoint::new(3, 3)
993 );
994
995 assert_eq!(
996 snapshot.clip_point(BlockPoint::new(1, 0), Bias::Left),
997 BlockPoint::new(0, 3)
998 );
999 assert_eq!(
1000 snapshot.clip_point(BlockPoint::new(1, 0), Bias::Right),
1001 BlockPoint::new(3, 0)
1002 );
1003 assert_eq!(
1004 snapshot.clip_point(BlockPoint::new(1, 1), Bias::Left),
1005 BlockPoint::new(0, 3)
1006 );
1007 assert_eq!(
1008 snapshot.clip_point(BlockPoint::new(1, 1), Bias::Right),
1009 BlockPoint::new(3, 0)
1010 );
1011 assert_eq!(
1012 snapshot.clip_point(BlockPoint::new(3, 0), Bias::Left),
1013 BlockPoint::new(3, 0)
1014 );
1015 assert_eq!(
1016 snapshot.clip_point(BlockPoint::new(3, 0), Bias::Right),
1017 BlockPoint::new(3, 0)
1018 );
1019 assert_eq!(
1020 snapshot.clip_point(BlockPoint::new(5, 3), Bias::Left),
1021 BlockPoint::new(5, 3)
1022 );
1023 assert_eq!(
1024 snapshot.clip_point(BlockPoint::new(5, 3), Bias::Right),
1025 BlockPoint::new(5, 3)
1026 );
1027 assert_eq!(
1028 snapshot.clip_point(BlockPoint::new(6, 0), Bias::Left),
1029 BlockPoint::new(5, 3)
1030 );
1031 assert_eq!(
1032 snapshot.clip_point(BlockPoint::new(6, 0), Bias::Right),
1033 BlockPoint::new(5, 3)
1034 );
1035
1036 assert_eq!(
1037 snapshot.buffer_rows(0).collect::<Vec<_>>(),
1038 &[Some(0), None, None, Some(1), Some(2), Some(3), None]
1039 );
1040
1041 // Insert a line break, separating two block decorations into separate
1042 // lines.
1043 buffer.update(cx, |buffer, cx| {
1044 buffer.edit([Point::new(1, 1)..Point::new(1, 1)], "!!!\n", cx)
1045 });
1046
1047 let (folds_snapshot, fold_edits) = fold_map.read(cx);
1048 let (tabs_snapshot, tab_edits) = tab_map.sync(folds_snapshot, fold_edits);
1049 let (wraps_snapshot, wrap_edits) = wrap_map.update(cx, |wrap_map, cx| {
1050 wrap_map.sync(tabs_snapshot, tab_edits, cx)
1051 });
1052 let mut snapshot = block_map.read(wraps_snapshot, wrap_edits, cx);
1053 assert_eq!(
1054 snapshot.text(),
1055 "aaa\nBLOCK 1\nb!!!\nBLOCK 2\nbb\nccc\nddd\nBLOCK 3"
1056 );
1057 }
1058
1059 #[gpui::test]
1060 fn test_blocks_on_wrapped_lines(cx: &mut gpui::MutableAppContext) {
1061 let family_id = cx.font_cache().load_family(&["Helvetica"]).unwrap();
1062 let font_id = cx
1063 .font_cache()
1064 .select_font(family_id, &Default::default())
1065 .unwrap();
1066
1067 let text = "one two three\nfour five six\nseven eight";
1068
1069 let buffer = cx.add_model(|cx| Buffer::new(0, text, cx));
1070 let (_, folds_snapshot) = FoldMap::new(buffer.clone(), cx);
1071 let (_, tabs_snapshot) = TabMap::new(folds_snapshot.clone(), 1);
1072 let (_, wraps_snapshot) = WrapMap::new(tabs_snapshot, font_id, 14.0, Some(60.), cx);
1073 let mut block_map = BlockMap::new(buffer.clone(), wraps_snapshot.clone());
1074
1075 let mut writer = block_map.write(wraps_snapshot.clone(), vec![], cx);
1076 writer.insert(
1077 vec![
1078 BlockProperties {
1079 position: Point::new(1, 12),
1080 text: "<BLOCK 1",
1081 disposition: BlockDisposition::Above,
1082 runs: vec![],
1083 },
1084 BlockProperties {
1085 position: Point::new(1, 1),
1086 text: ">BLOCK 2",
1087 disposition: BlockDisposition::Below,
1088 runs: vec![],
1089 },
1090 ],
1091 cx,
1092 );
1093
1094 // Blocks with an 'above' disposition go above their corresponding buffer line.
1095 // Blocks with a 'below' disposition go below their corresponding buffer line.
1096 let mut snapshot = block_map.read(wraps_snapshot, vec![], cx);
1097 assert_eq!(
1098 snapshot.text(),
1099 "one two \nthree\n<BLOCK 1\nfour five \nsix\n>BLOCK 2\nseven \neight"
1100 );
1101 }
1102
1103 #[gpui::test(iterations = 100)]
1104 fn test_random_blocks(cx: &mut gpui::MutableAppContext, mut rng: StdRng) {
1105 let operations = env::var("OPERATIONS")
1106 .map(|i| i.parse().expect("invalid `OPERATIONS` variable"))
1107 .unwrap_or(10);
1108
1109 let wrap_width = if rng.gen_bool(0.2) {
1110 None
1111 } else {
1112 Some(rng.gen_range(0.0..=100.0))
1113 };
1114 let tab_size = 1;
1115 let family_id = cx.font_cache().load_family(&["Helvetica"]).unwrap();
1116 let font_id = cx
1117 .font_cache()
1118 .select_font(family_id, &Default::default())
1119 .unwrap();
1120 let font_size = 14.0;
1121
1122 log::info!("Wrap width: {:?}", wrap_width);
1123
1124 let buffer = cx.add_model(|cx| {
1125 let len = rng.gen_range(0..10);
1126 let text = RandomCharIter::new(&mut rng).take(len).collect::<String>();
1127 log::info!("initial buffer text: {:?}", text);
1128 Buffer::new(0, text, cx)
1129 });
1130 let (fold_map, folds_snapshot) = FoldMap::new(buffer.clone(), cx);
1131 let (tab_map, tabs_snapshot) = TabMap::new(folds_snapshot.clone(), tab_size);
1132 let (wrap_map, wraps_snapshot) =
1133 WrapMap::new(tabs_snapshot, font_id, font_size, wrap_width, cx);
1134 let mut block_map = BlockMap::new(buffer.clone(), wraps_snapshot);
1135 let mut expected_blocks = Vec::new();
1136
1137 for _ in 0..operations {
1138 match rng.gen_range(0..=100) {
1139 0..=19 => {
1140 let wrap_width = if rng.gen_bool(0.2) {
1141 None
1142 } else {
1143 Some(rng.gen_range(0.0..=100.0))
1144 };
1145 log::info!("Setting wrap width to {:?}", wrap_width);
1146 wrap_map.update(cx, |map, cx| map.set_wrap_width(wrap_width, cx));
1147 }
1148 20..=39 => {
1149 let block_count = rng.gen_range(1..=1);
1150 let block_properties = (0..block_count)
1151 .map(|_| {
1152 let buffer = buffer.read(cx);
1153 let position = buffer.anchor_before(
1154 buffer.clip_offset(rng.gen_range(0..=buffer.len()), Bias::Left),
1155 );
1156
1157 let len = rng.gen_range(0..10);
1158 let mut text = Rope::from(
1159 RandomCharIter::new(&mut rng)
1160 .take(len)
1161 .collect::<String>()
1162 .to_uppercase()
1163 .as_str(),
1164 );
1165 let disposition = if rng.gen() {
1166 text.push_front("<");
1167 BlockDisposition::Above
1168 } else {
1169 text.push_front(">");
1170 BlockDisposition::Below
1171 };
1172 log::info!(
1173 "inserting block {:?} {:?} with text {:?}",
1174 disposition,
1175 position.to_point(buffer),
1176 text.to_string()
1177 );
1178 BlockProperties {
1179 position,
1180 text,
1181 runs: Vec::<(usize, HighlightStyle)>::new(),
1182 disposition,
1183 }
1184 })
1185 .collect::<Vec<_>>();
1186
1187 let (folds_snapshot, fold_edits) = fold_map.read(cx);
1188 let (tabs_snapshot, tab_edits) = tab_map.sync(folds_snapshot, fold_edits);
1189 let (wraps_snapshot, wrap_edits) = wrap_map.update(cx, |wrap_map, cx| {
1190 wrap_map.sync(tabs_snapshot, tab_edits, cx)
1191 });
1192 let mut block_map = block_map.write(wraps_snapshot, wrap_edits, cx);
1193 let block_ids = block_map.insert(block_properties.clone(), cx);
1194 for (block_id, props) in block_ids.into_iter().zip(block_properties) {
1195 expected_blocks.push((block_id, props));
1196 }
1197 }
1198 40..=59 if !expected_blocks.is_empty() => {
1199 let block_count = rng.gen_range(1..=4.min(expected_blocks.len()));
1200 let block_ids_to_remove = (0..block_count)
1201 .map(|_| {
1202 expected_blocks
1203 .remove(rng.gen_range(0..expected_blocks.len()))
1204 .0
1205 })
1206 .collect();
1207
1208 let (folds_snapshot, fold_edits) = fold_map.read(cx);
1209 let (tabs_snapshot, tab_edits) = tab_map.sync(folds_snapshot, fold_edits);
1210 let (wraps_snapshot, wrap_edits) = wrap_map.update(cx, |wrap_map, cx| {
1211 wrap_map.sync(tabs_snapshot, tab_edits, cx)
1212 });
1213 let mut block_map = block_map.write(wraps_snapshot, wrap_edits, cx);
1214 block_map.remove(block_ids_to_remove, cx);
1215 }
1216 _ => {
1217 buffer.update(cx, |buffer, _| {
1218 buffer.randomly_edit(&mut rng, 1);
1219 log::info!("buffer text: {:?}", buffer.text());
1220 });
1221 }
1222 }
1223
1224 let (folds_snapshot, fold_edits) = fold_map.read(cx);
1225 let (tabs_snapshot, tab_edits) = tab_map.sync(folds_snapshot, fold_edits);
1226 let (wraps_snapshot, wrap_edits) = wrap_map.update(cx, |wrap_map, cx| {
1227 wrap_map.sync(tabs_snapshot, tab_edits, cx)
1228 });
1229 let mut blocks_snapshot = block_map.read(wraps_snapshot.clone(), wrap_edits, cx);
1230 assert_eq!(
1231 blocks_snapshot.transforms.summary().input_rows,
1232 wraps_snapshot.max_point().row() + 1
1233 );
1234 log::info!("blocks text: {:?}", blocks_snapshot.text());
1235
1236 let buffer = buffer.read(cx);
1237 let mut sorted_blocks = expected_blocks
1238 .iter()
1239 .cloned()
1240 .map(|(id, block)| {
1241 let mut position = block.position.to_point(buffer);
1242 match block.disposition {
1243 BlockDisposition::Above => {
1244 position.column = 0;
1245 }
1246 BlockDisposition::Below => {
1247 position.column = buffer.line_len(position.row);
1248 }
1249 };
1250 let row = wraps_snapshot.from_point(position, Bias::Left).row();
1251 (
1252 id,
1253 BlockProperties {
1254 position: row,
1255 text: block.text,
1256 runs: block.runs,
1257 disposition: block.disposition,
1258 },
1259 )
1260 })
1261 .collect::<Vec<_>>();
1262 sorted_blocks
1263 .sort_unstable_by_key(|(id, block)| (block.position, block.disposition, *id));
1264 let mut sorted_blocks = sorted_blocks.into_iter().peekable();
1265
1266 let mut expected_buffer_rows = Vec::new();
1267 let mut expected_text = String::new();
1268 let input_text = wraps_snapshot.text();
1269 for (row, input_line) in input_text.split('\n').enumerate() {
1270 let row = row as u32;
1271 if row > 0 {
1272 expected_text.push('\n');
1273 }
1274
1275 let buffer_row = wraps_snapshot
1276 .to_point(WrapPoint::new(row, 0), Bias::Left)
1277 .row;
1278
1279 while let Some((_, block)) = sorted_blocks.peek() {
1280 if block.position == row && block.disposition == BlockDisposition::Above {
1281 let text = block.text.to_string();
1282 expected_text.push_str(&text);
1283 expected_text.push('\n');
1284 for _ in text.split('\n') {
1285 expected_buffer_rows.push(None);
1286 }
1287 sorted_blocks.next();
1288 } else {
1289 break;
1290 }
1291 }
1292
1293 let soft_wrapped = wraps_snapshot.to_tab_point(WrapPoint::new(row, 0)).column() > 0;
1294 expected_buffer_rows.push(if soft_wrapped { None } else { Some(buffer_row) });
1295 expected_text.push_str(input_line);
1296
1297 while let Some((_, block)) = sorted_blocks.peek() {
1298 if block.position == row && block.disposition == BlockDisposition::Below {
1299 let text = block.text.to_string();
1300 expected_text.push('\n');
1301 expected_text.push_str(&text);
1302 for _ in text.split('\n') {
1303 expected_buffer_rows.push(None);
1304 }
1305 sorted_blocks.next();
1306 } else {
1307 break;
1308 }
1309 }
1310 }
1311
1312 let expected_lines = expected_text.split('\n').collect::<Vec<_>>();
1313 let expected_row_count = expected_lines.len();
1314 for start_row in 0..expected_row_count {
1315 let expected_text = expected_lines[start_row..].join("\n");
1316 let actual_text = blocks_snapshot
1317 .chunks(start_row as u32..expected_row_count as u32, false)
1318 .map(|chunk| chunk.text)
1319 .collect::<String>();
1320 assert_eq!(
1321 actual_text, expected_text,
1322 "incorrect text starting from row {}",
1323 start_row
1324 );
1325 }
1326
1327 let mut expected_longest_rows = Vec::new();
1328 let mut longest_line_len = -1_isize;
1329 for (row, line) in expected_lines.iter().enumerate() {
1330 let row = row as u32;
1331
1332 assert_eq!(
1333 blocks_snapshot.line_len(row),
1334 line.len() as u32,
1335 "invalid line len for row {}",
1336 row
1337 );
1338
1339 let line_char_count = line.chars().count() as isize;
1340 match line_char_count.cmp(&longest_line_len) {
1341 Ordering::Less => {}
1342 Ordering::Equal => expected_longest_rows.push(row),
1343 Ordering::Greater => {
1344 longest_line_len = line_char_count;
1345 expected_longest_rows.clear();
1346 expected_longest_rows.push(row);
1347 }
1348 }
1349 }
1350
1351 log::info!("getting longest row >>>>>>>>>>>>>>>>>>>>>>>>");
1352 let longest_row = blocks_snapshot.longest_row();
1353 assert!(
1354 expected_longest_rows.contains(&longest_row),
1355 "incorrect longest row {}. expected {:?} with length {}",
1356 longest_row,
1357 expected_longest_rows,
1358 longest_line_len,
1359 );
1360
1361 for row in 0..=blocks_snapshot.wrap_snapshot.max_point().row() {
1362 let wrap_point = WrapPoint::new(row, 0);
1363 let block_point = blocks_snapshot.to_block_point(wrap_point);
1364 assert_eq!(blocks_snapshot.to_wrap_point(block_point), wrap_point);
1365 }
1366 assert_eq!(
1367 blocks_snapshot.buffer_rows(0).collect::<Vec<_>>(),
1368 expected_buffer_rows
1369 );
1370
1371 let mut block_point = BlockPoint::new(0, 0);
1372 for c in expected_text.chars() {
1373 let left_point = blocks_snapshot.clip_point(block_point, Bias::Left);
1374 let right_point = blocks_snapshot.clip_point(block_point, Bias::Right);
1375
1376 assert_eq!(
1377 blocks_snapshot.to_block_point(blocks_snapshot.to_wrap_point(left_point)),
1378 left_point
1379 );
1380 assert_eq!(
1381 blocks_snapshot.to_block_point(blocks_snapshot.to_wrap_point(right_point)),
1382 right_point
1383 );
1384
1385 if c == '\n' {
1386 block_point.0 += Point::new(1, 0);
1387 } else {
1388 block_point.column += c.len_utf8() as u32;
1389 }
1390 }
1391 }
1392 }
1393}