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