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