1use super::{
2 buffer, Anchor, AnchorRangeExt, Buffer, DisplayPoint, Edit, Point, TextSummary, ToOffset,
3};
4use crate::{
5 sum_tree::{self, Cursor, SumTree},
6 util::find_insertion_index,
7};
8use anyhow::{anyhow, Result};
9use gpui::{AppContext, ModelHandle};
10use std::{
11 cmp::{self, Ordering},
12 iter::Take,
13 ops::Range,
14};
15use sum_tree::{Dimension, SeekBias};
16
17pub struct FoldMap {
18 buffer: ModelHandle<Buffer>,
19 transforms: SumTree<Transform>,
20 folds: Vec<Range<Anchor>>,
21}
22
23impl FoldMap {
24 pub fn new(buffer: ModelHandle<Buffer>, app: &AppContext) -> Self {
25 let text_summary = buffer.read(app).text_summary();
26 Self {
27 buffer,
28 folds: Vec::new(),
29 transforms: SumTree::from_item(Transform {
30 summary: TransformSummary {
31 buffer: text_summary.clone(),
32 display: text_summary,
33 },
34 display_text: None,
35 }),
36 }
37 }
38
39 pub fn buffer_rows(&self, start_row: u32) -> Result<BufferRows> {
40 if start_row > self.transforms.summary().display.lines.row {
41 return Err(anyhow!("invalid display row {}", start_row));
42 }
43
44 let display_point = Point::new(start_row, 0);
45 let mut cursor = self.transforms.cursor();
46 cursor.seek(&DisplayPoint(display_point), SeekBias::Left);
47
48 Ok(BufferRows {
49 display_point,
50 cursor,
51 })
52 }
53
54 pub fn len(&self) -> usize {
55 self.transforms.summary().display.chars
56 }
57
58 pub fn line_len(&self, row: u32, ctx: &AppContext) -> Result<u32> {
59 let line_start = self.to_display_offset(DisplayPoint::new(row, 0), ctx)?.0;
60 let line_end = if row >= self.max_point().row() {
61 self.len()
62 } else {
63 self.to_display_offset(DisplayPoint::new(row + 1, 0), ctx)?
64 .0
65 - 1
66 };
67
68 Ok((line_end - line_start) as u32)
69 }
70
71 pub fn chars_at<'a>(&'a self, point: DisplayPoint, app: &'a AppContext) -> Result<Chars<'a>> {
72 let offset = self.to_display_offset(point, app)?;
73 let mut cursor = self.transforms.cursor();
74 cursor.seek(&offset, SeekBias::Right);
75 let buffer = self.buffer.read(app);
76 Ok(Chars {
77 cursor,
78 offset: offset.0,
79 buffer,
80 buffer_chars: None,
81 })
82 }
83
84 pub fn max_point(&self) -> DisplayPoint {
85 DisplayPoint(self.transforms.summary().display.lines)
86 }
87
88 pub fn rightmost_point(&self) -> DisplayPoint {
89 DisplayPoint(self.transforms.summary().display.rightmost_point)
90 }
91
92 pub fn fold<T: ToOffset>(
93 &mut self,
94 ranges: impl IntoIterator<Item = Range<T>>,
95 app: &AppContext,
96 ) -> Result<()> {
97 let mut edits = Vec::new();
98 let buffer = self.buffer.read(app);
99 for range in ranges.into_iter() {
100 let start = range.start.to_offset(buffer)?;
101 let end = range.end.to_offset(buffer)?;
102 edits.push(Edit {
103 old_range: start..end,
104 new_range: start..end,
105 });
106
107 let fold = buffer.anchor_after(start)?..buffer.anchor_before(end)?;
108 let ix = find_insertion_index(&self.folds, |probe| probe.cmp(&fold, buffer))?;
109 self.folds.insert(ix, fold);
110 }
111 edits.sort_unstable_by(|a, b| {
112 a.old_range
113 .start
114 .cmp(&b.old_range.start)
115 .then_with(|| b.old_range.end.cmp(&a.old_range.end))
116 });
117
118 self.apply_edits(&edits, app)?;
119 Ok(())
120 }
121
122 pub fn unfold<T: ToOffset>(
123 &mut self,
124 ranges: impl IntoIterator<Item = Range<T>>,
125 app: &AppContext,
126 ) -> Result<()> {
127 let buffer = self.buffer.read(app);
128
129 let mut edits = Vec::new();
130 for range in ranges.into_iter() {
131 let start = buffer.anchor_before(range.start.to_offset(buffer)?)?;
132 let end = buffer.anchor_after(range.end.to_offset(buffer)?)?;
133
134 // Remove intersecting folds and add their ranges to edits that are passed to apply_edits
135 self.folds.retain(|fold| {
136 if fold.start.cmp(&end, buffer).unwrap() > Ordering::Equal
137 || fold.end.cmp(&start, buffer).unwrap() < Ordering::Equal
138 {
139 true
140 } else {
141 let offset_range =
142 fold.start.to_offset(buffer).unwrap()..fold.end.to_offset(buffer).unwrap();
143 edits.push(Edit {
144 old_range: offset_range.clone(),
145 new_range: offset_range,
146 });
147 false
148 }
149 });
150 }
151
152 self.apply_edits(&edits, app)?;
153 Ok(())
154 }
155
156 pub fn is_line_folded(&self, display_row: u32) -> bool {
157 let mut cursor = self.transforms.cursor::<DisplayPoint, DisplayPoint>();
158 cursor.seek(&DisplayPoint::new(display_row, 0), SeekBias::Right);
159 while let Some(transform) = cursor.item() {
160 if transform.display_text.is_some() {
161 return true;
162 }
163 if cursor.end().row() == display_row {
164 cursor.next()
165 } else {
166 break;
167 }
168 }
169 false
170 }
171
172 pub fn to_display_offset(
173 &self,
174 point: DisplayPoint,
175 app: &AppContext,
176 ) -> Result<DisplayOffset> {
177 let mut cursor = self.transforms.cursor::<DisplayPoint, TransformSummary>();
178 cursor.seek(&point, SeekBias::Right);
179 let overshoot = point.0 - cursor.start().display.lines;
180 let mut offset = cursor.start().display.chars;
181 if !overshoot.is_zero() {
182 let transform = cursor
183 .item()
184 .ok_or_else(|| anyhow!("display point {:?} is out of range", point))?;
185 assert!(transform.display_text.is_none());
186 let end_buffer_offset =
187 (cursor.start().buffer.lines + overshoot).to_offset(self.buffer.read(app))?;
188 offset += end_buffer_offset - cursor.start().buffer.chars;
189 }
190 Ok(DisplayOffset(offset))
191 }
192
193 pub fn to_buffer_point(&self, display_point: DisplayPoint) -> Point {
194 let mut cursor = self.transforms.cursor::<DisplayPoint, TransformSummary>();
195 cursor.seek(&display_point, SeekBias::Right);
196 let overshoot = display_point.0 - cursor.start().display.lines;
197 cursor.start().buffer.lines + overshoot
198 }
199
200 pub fn to_display_point(&self, point: Point) -> DisplayPoint {
201 let mut cursor = self.transforms.cursor::<Point, TransformSummary>();
202 cursor.seek(&point, SeekBias::Right);
203 let overshoot = point - cursor.start().buffer.lines;
204 DisplayPoint(cmp::min(
205 cursor.start().display.lines + overshoot,
206 cursor.end().display.lines,
207 ))
208 }
209
210 pub fn apply_edits(&mut self, edits: &[Edit], app: &AppContext) -> Result<()> {
211 let buffer = self.buffer.read(app);
212 let mut edits = edits.iter().cloned().peekable();
213
214 let mut new_transforms = SumTree::new();
215 let mut cursor = self.transforms.cursor::<usize, usize>();
216 cursor.seek(&0, SeekBias::Right);
217
218 while let Some(mut edit) = edits.next() {
219 new_transforms.push_tree(cursor.slice(&edit.old_range.start, SeekBias::Left));
220 edit.new_range.start -= edit.old_range.start - cursor.start();
221 edit.old_range.start = *cursor.start();
222
223 cursor.seek(&edit.old_range.end, SeekBias::Right);
224 cursor.next();
225
226 let mut delta = edit.delta();
227 loop {
228 edit.old_range.end = *cursor.start();
229
230 if let Some(next_edit) = edits.peek() {
231 if next_edit.old_range.start > edit.old_range.end {
232 break;
233 }
234
235 let next_edit = edits.next().unwrap();
236 delta += next_edit.delta();
237
238 if next_edit.old_range.end > edit.old_range.end {
239 edit.old_range.end = next_edit.old_range.end;
240 cursor.seek(&edit.old_range.end, SeekBias::Right);
241 cursor.next();
242 }
243 } else {
244 break;
245 }
246 }
247
248 edit.new_range.end =
249 ((edit.new_range.start + edit.old_extent()) as isize + delta) as usize;
250
251 let anchor = buffer.anchor_before(edit.new_range.start)?;
252 let folds_start =
253 find_insertion_index(&self.folds, |probe| probe.start.cmp(&anchor, buffer))?;
254 let mut folds = self.folds[folds_start..]
255 .iter()
256 .map(|fold| {
257 fold.start.to_offset(buffer).unwrap()..fold.end.to_offset(buffer).unwrap()
258 })
259 .peekable();
260
261 while folds
262 .peek()
263 .map_or(false, |fold| fold.start < edit.new_range.end)
264 {
265 let mut fold = folds.next().unwrap();
266 let sum = new_transforms.summary();
267
268 assert!(fold.start >= sum.buffer.chars);
269
270 while folds
271 .peek()
272 .map_or(false, |next_fold| next_fold.start <= fold.end)
273 {
274 let next_fold = folds.next().unwrap();
275 if next_fold.end > fold.end {
276 fold.end = next_fold.end;
277 }
278 }
279
280 if fold.start > sum.buffer.chars {
281 let text_summary = buffer.text_summary_for_range(sum.buffer.chars..fold.start);
282 new_transforms.push(Transform {
283 summary: TransformSummary {
284 display: text_summary.clone(),
285 buffer: text_summary,
286 },
287 display_text: None,
288 });
289 }
290
291 if fold.end > fold.start {
292 new_transforms.push(Transform {
293 summary: TransformSummary {
294 display: TextSummary {
295 chars: 1,
296 bytes: '…'.len_utf8(),
297 lines: Point::new(0, 1),
298 first_line_len: 1,
299 rightmost_point: Point::new(0, 1),
300 },
301 buffer: buffer.text_summary_for_range(fold.start..fold.end),
302 },
303 display_text: Some('…'),
304 });
305 }
306 }
307
308 let sum = new_transforms.summary();
309 if sum.buffer.chars < edit.new_range.end {
310 let text_summary =
311 buffer.text_summary_for_range(sum.buffer.chars..edit.new_range.end);
312 new_transforms.push(Transform {
313 summary: TransformSummary {
314 display: text_summary.clone(),
315 buffer: text_summary,
316 },
317 display_text: None,
318 });
319 }
320 }
321
322 new_transforms.push_tree(cursor.suffix());
323 if new_transforms.is_empty() {
324 let text_summary = buffer.text_summary();
325 new_transforms.push(Transform {
326 summary: TransformSummary {
327 display: text_summary.clone(),
328 buffer: text_summary,
329 },
330 display_text: None,
331 });
332 }
333
334 drop(cursor);
335 self.transforms = new_transforms;
336
337 Ok(())
338 }
339}
340
341#[derive(Clone, Debug, Default, Eq, PartialEq)]
342struct Transform {
343 summary: TransformSummary,
344 display_text: Option<char>,
345}
346
347#[derive(Clone, Debug, Default, Eq, PartialEq)]
348struct TransformSummary {
349 display: TextSummary,
350 buffer: TextSummary,
351}
352
353impl sum_tree::Item for Transform {
354 type Summary = TransformSummary;
355
356 fn summary(&self) -> Self::Summary {
357 self.summary.clone()
358 }
359}
360
361impl<'a> std::ops::AddAssign<&'a Self> for TransformSummary {
362 fn add_assign(&mut self, other: &'a Self) {
363 self.buffer += &other.buffer;
364 self.display += &other.display;
365 }
366}
367
368impl<'a> Dimension<'a, TransformSummary> for TransformSummary {
369 fn add_summary(&mut self, summary: &'a TransformSummary) {
370 *self += summary;
371 }
372}
373
374pub struct BufferRows<'a> {
375 cursor: Cursor<'a, Transform, DisplayPoint, TransformSummary>,
376 display_point: Point,
377}
378
379impl<'a> Iterator for BufferRows<'a> {
380 type Item = u32;
381
382 fn next(&mut self) -> Option<Self::Item> {
383 while self.display_point > self.cursor.end().display.lines {
384 self.cursor.next();
385 if self.cursor.item().is_none() {
386 // TODO: Return a bool from next?
387 break;
388 }
389 }
390
391 if self.cursor.item().is_some() {
392 let overshoot = self.display_point - self.cursor.start().display.lines;
393 let buffer_point = self.cursor.start().buffer.lines + overshoot;
394 self.display_point.row += 1;
395 Some(buffer_point.row)
396 } else {
397 None
398 }
399 }
400}
401
402pub struct Chars<'a> {
403 cursor: Cursor<'a, Transform, DisplayOffset, TransformSummary>,
404 offset: usize,
405 buffer: &'a Buffer,
406 buffer_chars: Option<Take<buffer::CharIter<'a>>>,
407}
408
409impl<'a> Iterator for Chars<'a> {
410 type Item = char;
411
412 fn next(&mut self) -> Option<Self::Item> {
413 if let Some(c) = self.buffer_chars.as_mut().and_then(|chars| chars.next()) {
414 self.offset += 1;
415 return Some(c);
416 }
417
418 if self.offset == self.cursor.end().display.chars {
419 self.cursor.next();
420 }
421
422 self.cursor.item().and_then(|transform| {
423 if let Some(c) = transform.display_text {
424 self.offset += 1;
425 Some(c)
426 } else {
427 let overshoot = self.offset - self.cursor.start().display.chars;
428 let buffer_start = self.cursor.start().buffer.chars + overshoot;
429 let char_count = self.cursor.end().buffer.chars - buffer_start;
430 self.buffer_chars =
431 Some(self.buffer.chars_at(buffer_start).unwrap().take(char_count));
432 self.next()
433 }
434 })
435 }
436}
437
438impl<'a> Dimension<'a, TransformSummary> for DisplayPoint {
439 fn add_summary(&mut self, summary: &'a TransformSummary) {
440 self.0 += &summary.display.lines;
441 }
442}
443
444#[derive(Copy, Clone, Debug, Default, Eq, Ord, PartialOrd, PartialEq)]
445pub struct DisplayOffset(usize);
446
447impl<'a> Dimension<'a, TransformSummary> for DisplayOffset {
448 fn add_summary(&mut self, summary: &'a TransformSummary) {
449 self.0 += &summary.display.chars;
450 }
451}
452
453impl<'a> Dimension<'a, TransformSummary> for Point {
454 fn add_summary(&mut self, summary: &'a TransformSummary) {
455 *self += &summary.buffer.lines;
456 }
457}
458
459impl<'a> Dimension<'a, TransformSummary> for usize {
460 fn add_summary(&mut self, summary: &'a TransformSummary) {
461 *self += &summary.buffer.chars;
462 }
463}
464
465#[cfg(test)]
466mod tests {
467 use super::*;
468 use crate::test::sample_text;
469 use gpui::App;
470
471 #[test]
472 fn test_basic_folds() {
473 App::test((), |app| {
474 let buffer = app.add_model(|_| Buffer::new(0, sample_text(5, 6)));
475 let mut map = FoldMap::new(buffer.clone(), app.as_ref());
476
477 map.fold(
478 vec![
479 Point::new(0, 2)..Point::new(2, 2),
480 Point::new(2, 4)..Point::new(4, 1),
481 ],
482 app.as_ref(),
483 )
484 .unwrap();
485 assert_eq!(map.text(app.as_ref()), "aa…cc…eeeee");
486
487 let edits = buffer.update(app, |buffer, ctx| {
488 let start_version = buffer.version.clone();
489 buffer
490 .edit(
491 vec![
492 Point::new(0, 0)..Point::new(0, 1),
493 Point::new(2, 3)..Point::new(2, 3),
494 ],
495 "123",
496 Some(ctx),
497 )
498 .unwrap();
499 buffer.edits_since(start_version).collect::<Vec<_>>()
500 });
501
502 map.apply_edits(&edits, app.as_ref()).unwrap();
503 assert_eq!(map.text(app.as_ref()), "123a…c123c…eeeee");
504
505 let edits = buffer.update(app, |buffer, ctx| {
506 let start_version = buffer.version.clone();
507 buffer
508 .edit(Some(Point::new(2, 6)..Point::new(4, 3)), "456", Some(ctx))
509 .unwrap();
510 buffer.edits_since(start_version).collect::<Vec<_>>()
511 });
512
513 map.apply_edits(&edits, app.as_ref()).unwrap();
514 assert_eq!(map.text(app.as_ref()), "123a…c123456eee");
515
516 map.unfold(Some(Point::new(0, 4)..Point::new(0, 4)), app.as_ref())
517 .unwrap();
518 assert_eq!(map.text(app.as_ref()), "123aaaaa\nbbbbbb\nccc123456eee");
519 });
520 }
521
522 #[test]
523 fn test_overlapping_folds() {
524 App::test((), |app| {
525 let buffer = app.add_model(|_| Buffer::new(0, sample_text(5, 6)));
526 let mut map = FoldMap::new(buffer.clone(), app.as_ref());
527 map.fold(
528 vec![
529 Point::new(0, 2)..Point::new(2, 2),
530 Point::new(0, 4)..Point::new(1, 0),
531 Point::new(1, 2)..Point::new(3, 2),
532 Point::new(3, 1)..Point::new(4, 1),
533 ],
534 app.as_ref(),
535 )
536 .unwrap();
537 assert_eq!(map.text(app.as_ref()), "aa…eeeee");
538 })
539 }
540
541 #[test]
542 fn test_merging_folds_via_edit() {
543 App::test((), |app| {
544 let buffer = app.add_model(|_| Buffer::new(0, sample_text(5, 6)));
545 let mut map = FoldMap::new(buffer.clone(), app.as_ref());
546
547 map.fold(
548 vec![
549 Point::new(0, 2)..Point::new(2, 2),
550 Point::new(3, 1)..Point::new(4, 1),
551 ],
552 app.as_ref(),
553 )
554 .unwrap();
555 assert_eq!(map.text(app.as_ref()), "aa…cccc\nd…eeeee");
556
557 let edits = buffer.update(app, |buffer, ctx| {
558 let start_version = buffer.version.clone();
559 buffer
560 .edit(Some(Point::new(2, 2)..Point::new(3, 1)), "", Some(ctx))
561 .unwrap();
562 buffer.edits_since(start_version).collect::<Vec<_>>()
563 });
564
565 map.apply_edits(&edits, app.as_ref()).unwrap();
566 assert_eq!(map.text(app.as_ref()), "aa…eeeee");
567 });
568 }
569
570 #[test]
571 fn test_random_folds() {
572 use crate::editor::ToPoint;
573 use crate::util::RandomCharIter;
574 use rand::prelude::*;
575 use std::env;
576
577 let iterations = env::var("ITERATIONS")
578 .map(|i| i.parse().expect("invalid `ITERATIONS` variable"))
579 .unwrap_or(100);
580 let seed_range = if let Ok(seed) = env::var("SEED") {
581 let seed = seed.parse().expect("invalid `SEED` variable");
582 seed..seed + 1
583 } else {
584 0..iterations
585 };
586
587 for seed in seed_range {
588 println!("{:?}", seed);
589 let mut rng = StdRng::seed_from_u64(seed);
590
591 App::test((), |app| {
592 let buffer = app.add_model(|_| {
593 let len = rng.gen_range(0..10);
594 let text = RandomCharIter::new(&mut rng).take(len).collect::<String>();
595 Buffer::new(0, text)
596 });
597 let mut map = FoldMap::new(buffer.clone(), app.as_ref());
598
599 {
600 let buffer = buffer.read(app);
601
602 let fold_count = rng.gen_range(0..10);
603 let mut fold_ranges: Vec<Range<usize>> = Vec::new();
604 for _ in 0..fold_count {
605 let end = rng.gen_range(0..buffer.len() + 1);
606 let start = rng.gen_range(0..end + 1);
607 fold_ranges.push(start..end);
608 }
609
610 map.fold(fold_ranges, app.as_ref()).unwrap();
611
612 let mut expected_text = buffer.text();
613 for fold_range in map.merged_fold_ranges(app.as_ref()).into_iter().rev() {
614 expected_text.replace_range(fold_range.start..fold_range.end, "…");
615 }
616
617 assert_eq!(map.text(app.as_ref()), expected_text);
618
619 for fold_range in map.merged_fold_ranges(app.as_ref()) {
620 let display_point =
621 map.to_display_point(fold_range.start.to_point(buffer).unwrap());
622 assert!(map.is_line_folded(display_point.row()));
623 }
624 }
625
626 let edits = buffer.update(app, |buffer, ctx| {
627 let start_version = buffer.version.clone();
628 let edit_count = rng.gen_range(1..10);
629 buffer.randomly_edit(&mut rng, edit_count, Some(ctx));
630 buffer.edits_since(start_version).collect::<Vec<_>>()
631 });
632
633 map.apply_edits(&edits, app.as_ref()).unwrap();
634
635 let buffer = map.buffer.read(app);
636 let mut expected_text = buffer.text();
637 let mut expected_buffer_rows = Vec::new();
638 let mut next_row = buffer.max_point().row;
639 for fold_range in map.merged_fold_ranges(app.as_ref()).into_iter().rev() {
640 let fold_start = buffer.point_for_offset(fold_range.start).unwrap();
641 let fold_end = buffer.point_for_offset(fold_range.end).unwrap();
642 expected_buffer_rows.extend((fold_end.row + 1..=next_row).rev());
643 next_row = fold_start.row;
644
645 expected_text.replace_range(fold_range.start..fold_range.end, "…");
646 }
647 expected_buffer_rows.extend((0..=next_row).rev());
648 expected_buffer_rows.reverse();
649
650 assert_eq!(map.text(app.as_ref()), expected_text);
651
652 for (idx, buffer_row) in expected_buffer_rows.iter().enumerate() {
653 let display_row = map.to_display_point(Point::new(*buffer_row, 0)).row();
654 assert_eq!(
655 map.buffer_rows(display_row).unwrap().collect::<Vec<_>>(),
656 expected_buffer_rows[idx..],
657 );
658 }
659 });
660 }
661 }
662
663 #[test]
664 fn test_buffer_rows() {
665 App::test((), |app| {
666 let text = sample_text(6, 6) + "\n";
667 let buffer = app.add_model(|_| Buffer::new(0, text));
668
669 let mut map = FoldMap::new(buffer.clone(), app.as_ref());
670
671 map.fold(
672 vec![
673 Point::new(0, 2)..Point::new(2, 2),
674 Point::new(3, 1)..Point::new(4, 1),
675 ],
676 app.as_ref(),
677 )
678 .unwrap();
679
680 assert_eq!(map.text(app.as_ref()), "aa…cccc\nd…eeeee\nffffff\n");
681 assert_eq!(
682 map.buffer_rows(0).unwrap().collect::<Vec<_>>(),
683 vec![0, 3, 5, 6]
684 );
685 assert_eq!(map.buffer_rows(3).unwrap().collect::<Vec<_>>(), vec![6]);
686 });
687 }
688
689 impl FoldMap {
690 fn text(&self, app: &AppContext) -> String {
691 self.chars_at(DisplayPoint(Point::zero()), app)
692 .unwrap()
693 .collect()
694 }
695
696 fn merged_fold_ranges(&self, app: &AppContext) -> Vec<Range<usize>> {
697 let buffer = self.buffer.read(app);
698 let mut fold_ranges = self
699 .folds
700 .iter()
701 .map(|fold| {
702 fold.start.to_offset(buffer).unwrap()..fold.end.to_offset(buffer).unwrap()
703 })
704 .peekable();
705
706 let mut merged_ranges = Vec::new();
707 while let Some(mut fold_range) = fold_ranges.next() {
708 while let Some(next_range) = fold_ranges.peek() {
709 if fold_range.end >= next_range.start {
710 if next_range.end > fold_range.end {
711 fold_range.end = next_range.end;
712 }
713 fold_ranges.next();
714 } else {
715 break;
716 }
717 }
718 if fold_range.end > fold_range.start {
719 merged_ranges.push(fold_range);
720 }
721 }
722 merged_ranges
723 }
724 }
725}