1use crate::PointUtf16;
2
3use super::Point;
4use arrayvec::ArrayString;
5use smallvec::SmallVec;
6use std::{cmp, fmt, io, mem, ops::Range, str};
7use sum_tree::{Bias, Dimension, SumTree};
8
9#[cfg(test)]
10const CHUNK_BASE: usize = 6;
11
12#[cfg(not(test))]
13const CHUNK_BASE: usize = 16;
14
15#[derive(Clone, Default, Debug)]
16pub struct Rope {
17 chunks: SumTree<Chunk>,
18}
19
20impl Rope {
21 pub fn new() -> Self {
22 Self::default()
23 }
24
25 pub fn append(&mut self, rope: Rope) {
26 let mut chunks = rope.chunks.cursor::<()>();
27 chunks.next(&());
28 if let Some(chunk) = chunks.item() {
29 if self.chunks.last().map_or(false, |c| c.0.len() < CHUNK_BASE)
30 || chunk.0.len() < CHUNK_BASE
31 {
32 self.push(&chunk.0);
33 chunks.next(&());
34 }
35 }
36
37 self.chunks.push_tree(chunks.suffix(&()), &());
38 self.check_invariants();
39 }
40
41 pub fn replace(&mut self, range: Range<usize>, text: &str) {
42 let mut new_rope = Rope::new();
43 let mut cursor = self.cursor(0);
44 new_rope.append(cursor.slice(range.start));
45 cursor.seek_forward(range.end);
46 new_rope.push(text);
47 new_rope.append(cursor.suffix());
48 *self = new_rope;
49 }
50
51 pub fn slice(&self, range: Range<usize>) -> Rope {
52 let mut cursor = self.cursor(0);
53 cursor.seek_forward(range.start);
54 cursor.slice(range.end)
55 }
56
57 pub fn push(&mut self, text: &str) {
58 let mut new_chunks = SmallVec::<[_; 16]>::new();
59 let mut new_chunk = ArrayString::new();
60 for ch in text.chars() {
61 if new_chunk.len() + ch.len_utf8() > 2 * CHUNK_BASE {
62 new_chunks.push(Chunk(new_chunk));
63 new_chunk = ArrayString::new();
64 }
65 new_chunk.push(ch);
66 }
67 if !new_chunk.is_empty() {
68 new_chunks.push(Chunk(new_chunk));
69 }
70
71 let mut new_chunks = new_chunks.into_iter();
72 let mut first_new_chunk = new_chunks.next();
73 self.chunks.update_last(
74 |last_chunk| {
75 if let Some(first_new_chunk_ref) = first_new_chunk.as_mut() {
76 if last_chunk.0.len() + first_new_chunk_ref.0.len() <= 2 * CHUNK_BASE {
77 last_chunk.0.push_str(&first_new_chunk.take().unwrap().0);
78 } else {
79 let mut text = ArrayString::<{ 4 * CHUNK_BASE }>::new();
80 text.push_str(&last_chunk.0);
81 text.push_str(&first_new_chunk_ref.0);
82 let (left, right) = text.split_at(find_split_ix(&text));
83 last_chunk.0.clear();
84 last_chunk.0.push_str(left);
85 first_new_chunk_ref.0.clear();
86 first_new_chunk_ref.0.push_str(right);
87 }
88 }
89 },
90 &(),
91 );
92
93 self.chunks
94 .extend(first_new_chunk.into_iter().chain(new_chunks), &());
95 self.check_invariants();
96 }
97
98 pub fn push_front(&mut self, text: &str) {
99 let suffix = mem::replace(self, Rope::from(text));
100 self.append(suffix);
101 }
102
103 fn check_invariants(&self) {
104 #[cfg(test)]
105 {
106 // Ensure all chunks except maybe the last one are not underflowing.
107 // Allow some wiggle room for multibyte characters at chunk boundaries.
108 let mut chunks = self.chunks.cursor::<()>().peekable();
109 while let Some(chunk) = chunks.next() {
110 if chunks.peek().is_some() {
111 assert!(chunk.0.len() + 3 >= CHUNK_BASE);
112 }
113 }
114 }
115 }
116
117 pub fn summary(&self) -> TextSummary {
118 self.chunks.summary().clone()
119 }
120
121 pub fn len(&self) -> usize {
122 self.chunks.extent(&())
123 }
124
125 pub fn max_point(&self) -> Point {
126 self.chunks.extent(&())
127 }
128
129 pub fn max_point_utf16(&self) -> PointUtf16 {
130 self.chunks.extent(&())
131 }
132
133 pub fn cursor(&self, offset: usize) -> Cursor {
134 Cursor::new(self, offset)
135 }
136
137 pub fn chars(&self) -> impl Iterator<Item = char> + '_ {
138 self.chars_at(0)
139 }
140
141 pub fn chars_at(&self, start: usize) -> impl Iterator<Item = char> + '_ {
142 self.chunks_in_range(start..self.len()).flat_map(str::chars)
143 }
144
145 pub fn reversed_chars_at(&self, start: usize) -> impl Iterator<Item = char> + '_ {
146 self.reversed_chunks_in_range(0..start)
147 .flat_map(|chunk| chunk.chars().rev())
148 }
149
150 pub fn bytes_in_range(&self, range: Range<usize>) -> Bytes {
151 Bytes::new(self, range)
152 }
153
154 pub fn chunks<'a>(&'a self) -> Chunks<'a> {
155 self.chunks_in_range(0..self.len())
156 }
157
158 pub fn chunks_in_range(&self, range: Range<usize>) -> Chunks {
159 Chunks::new(self, range, false)
160 }
161
162 pub fn reversed_chunks_in_range(&self, range: Range<usize>) -> Chunks {
163 Chunks::new(self, range, true)
164 }
165
166 pub fn offset_to_point(&self, offset: usize) -> Point {
167 if offset >= self.summary().bytes {
168 return self.summary().lines;
169 }
170 let mut cursor = self.chunks.cursor::<(usize, Point)>();
171 cursor.seek(&offset, Bias::Left, &());
172 let overshoot = offset - cursor.start().0;
173 cursor.start().1
174 + cursor
175 .item()
176 .map_or(Point::zero(), |chunk| chunk.offset_to_point(overshoot))
177 }
178
179 pub fn offset_to_point_utf16(&self, offset: usize) -> PointUtf16 {
180 if offset >= self.summary().bytes {
181 return self.summary().lines_utf16;
182 }
183 let mut cursor = self.chunks.cursor::<(usize, PointUtf16)>();
184 cursor.seek(&offset, Bias::Left, &());
185 let overshoot = offset - cursor.start().0;
186 cursor.start().1
187 + cursor.item().map_or(PointUtf16::zero(), |chunk| {
188 chunk.offset_to_point_utf16(overshoot)
189 })
190 }
191
192 pub fn point_to_point_utf16(&self, point: Point) -> PointUtf16 {
193 if point >= self.summary().lines {
194 return self.summary().lines_utf16;
195 }
196 let mut cursor = self.chunks.cursor::<(Point, PointUtf16)>();
197 cursor.seek(&point, Bias::Left, &());
198 let overshoot = point - cursor.start().0;
199 cursor.start().1
200 + cursor.item().map_or(PointUtf16::zero(), |chunk| {
201 chunk.point_to_point_utf16(overshoot)
202 })
203 }
204
205 pub fn point_to_offset(&self, point: Point) -> usize {
206 if point >= self.summary().lines {
207 return self.summary().bytes;
208 }
209 let mut cursor = self.chunks.cursor::<(Point, usize)>();
210 cursor.seek(&point, Bias::Left, &());
211 let overshoot = point - cursor.start().0;
212 cursor.start().1
213 + cursor
214 .item()
215 .map_or(0, |chunk| chunk.point_to_offset(overshoot))
216 }
217
218 pub fn point_utf16_to_offset(&self, point: PointUtf16) -> usize {
219 if point >= self.summary().lines_utf16 {
220 return self.summary().bytes;
221 }
222 let mut cursor = self.chunks.cursor::<(PointUtf16, usize)>();
223 cursor.seek(&point, Bias::Left, &());
224 let overshoot = point - cursor.start().0;
225 cursor.start().1
226 + cursor
227 .item()
228 .map_or(0, |chunk| chunk.point_utf16_to_offset(overshoot))
229 }
230
231 pub fn point_utf16_to_point(&self, point: PointUtf16) -> Point {
232 if point >= self.summary().lines_utf16 {
233 return self.summary().lines;
234 }
235 let mut cursor = self.chunks.cursor::<(PointUtf16, Point)>();
236 cursor.seek(&point, Bias::Left, &());
237 let overshoot = point - cursor.start().0;
238 cursor.start().1
239 + cursor
240 .item()
241 .map_or(Point::zero(), |chunk| chunk.point_utf16_to_point(overshoot))
242 }
243
244 pub fn clip_offset(&self, mut offset: usize, bias: Bias) -> usize {
245 let mut cursor = self.chunks.cursor::<usize>();
246 cursor.seek(&offset, Bias::Left, &());
247 if let Some(chunk) = cursor.item() {
248 let mut ix = offset - cursor.start();
249 while !chunk.0.is_char_boundary(ix) {
250 match bias {
251 Bias::Left => {
252 ix -= 1;
253 offset -= 1;
254 }
255 Bias::Right => {
256 ix += 1;
257 offset += 1;
258 }
259 }
260 }
261 offset
262 } else {
263 self.summary().bytes
264 }
265 }
266
267 pub fn clip_point(&self, point: Point, bias: Bias) -> Point {
268 let mut cursor = self.chunks.cursor::<Point>();
269 cursor.seek(&point, Bias::Right, &());
270 if let Some(chunk) = cursor.item() {
271 let overshoot = point - cursor.start();
272 *cursor.start() + chunk.clip_point(overshoot, bias)
273 } else {
274 self.summary().lines
275 }
276 }
277
278 pub fn clip_point_utf16(&self, point: PointUtf16, bias: Bias) -> PointUtf16 {
279 let mut cursor = self.chunks.cursor::<PointUtf16>();
280 cursor.seek(&point, Bias::Right, &());
281 if let Some(chunk) = cursor.item() {
282 let overshoot = point - cursor.start();
283 *cursor.start() + chunk.clip_point_utf16(overshoot, bias)
284 } else {
285 self.summary().lines_utf16
286 }
287 }
288
289 pub fn line_len(&self, row: u32) -> u32 {
290 self.clip_point(Point::new(row, u32::MAX), Bias::Left)
291 .column
292 }
293}
294
295impl<'a> From<&'a str> for Rope {
296 fn from(text: &'a str) -> Self {
297 let mut rope = Self::new();
298 rope.push(text);
299 rope
300 }
301}
302
303impl fmt::Display for Rope {
304 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
305 for chunk in self.chunks() {
306 write!(f, "{}", chunk)?;
307 }
308 Ok(())
309 }
310}
311
312pub struct Cursor<'a> {
313 rope: &'a Rope,
314 chunks: sum_tree::Cursor<'a, Chunk, usize>,
315 offset: usize,
316}
317
318impl<'a> Cursor<'a> {
319 pub fn new(rope: &'a Rope, offset: usize) -> Self {
320 let mut chunks = rope.chunks.cursor();
321 chunks.seek(&offset, Bias::Right, &());
322 Self {
323 rope,
324 chunks,
325 offset,
326 }
327 }
328
329 pub fn seek_forward(&mut self, end_offset: usize) {
330 debug_assert!(end_offset >= self.offset);
331
332 self.chunks.seek_forward(&end_offset, Bias::Right, &());
333 self.offset = end_offset;
334 }
335
336 pub fn slice(&mut self, end_offset: usize) -> Rope {
337 debug_assert!(
338 end_offset >= self.offset,
339 "cannot slice backwards from {} to {}",
340 self.offset,
341 end_offset
342 );
343
344 let mut slice = Rope::new();
345 if let Some(start_chunk) = self.chunks.item() {
346 let start_ix = self.offset - self.chunks.start();
347 let end_ix = cmp::min(end_offset, self.chunks.end(&())) - self.chunks.start();
348 slice.push(&start_chunk.0[start_ix..end_ix]);
349 }
350
351 if end_offset > self.chunks.end(&()) {
352 self.chunks.next(&());
353 slice.append(Rope {
354 chunks: self.chunks.slice(&end_offset, Bias::Right, &()),
355 });
356 if let Some(end_chunk) = self.chunks.item() {
357 let end_ix = end_offset - self.chunks.start();
358 slice.push(&end_chunk.0[..end_ix]);
359 }
360 }
361
362 self.offset = end_offset;
363 slice
364 }
365
366 pub fn summary<D: TextDimension>(&mut self, end_offset: usize) -> D {
367 debug_assert!(end_offset >= self.offset);
368
369 let mut summary = D::default();
370 if let Some(start_chunk) = self.chunks.item() {
371 let start_ix = self.offset - self.chunks.start();
372 let end_ix = cmp::min(end_offset, self.chunks.end(&())) - self.chunks.start();
373 summary.add_assign(&D::from_text_summary(&TextSummary::from(
374 &start_chunk.0[start_ix..end_ix],
375 )));
376 }
377
378 if end_offset > self.chunks.end(&()) {
379 self.chunks.next(&());
380 summary.add_assign(&self.chunks.summary(&end_offset, Bias::Right, &()));
381 if let Some(end_chunk) = self.chunks.item() {
382 let end_ix = end_offset - self.chunks.start();
383 summary.add_assign(&D::from_text_summary(&TextSummary::from(
384 &end_chunk.0[..end_ix],
385 )));
386 }
387 }
388
389 self.offset = end_offset;
390 summary
391 }
392
393 pub fn suffix(mut self) -> Rope {
394 self.slice(self.rope.chunks.extent(&()))
395 }
396
397 pub fn offset(&self) -> usize {
398 self.offset
399 }
400}
401
402pub struct Chunks<'a> {
403 chunks: sum_tree::Cursor<'a, Chunk, usize>,
404 range: Range<usize>,
405 reversed: bool,
406}
407
408impl<'a> Chunks<'a> {
409 pub fn new(rope: &'a Rope, range: Range<usize>, reversed: bool) -> Self {
410 let mut chunks = rope.chunks.cursor();
411 if reversed {
412 chunks.seek(&range.end, Bias::Left, &());
413 } else {
414 chunks.seek(&range.start, Bias::Right, &());
415 }
416 Self {
417 chunks,
418 range,
419 reversed,
420 }
421 }
422
423 pub fn offset(&self) -> usize {
424 if self.reversed {
425 self.range.end.min(self.chunks.end(&()))
426 } else {
427 self.range.start.max(*self.chunks.start())
428 }
429 }
430
431 pub fn seek(&mut self, offset: usize) {
432 let bias = if self.reversed {
433 Bias::Left
434 } else {
435 Bias::Right
436 };
437
438 if offset >= self.chunks.end(&()) {
439 self.chunks.seek_forward(&offset, bias, &());
440 } else {
441 self.chunks.seek(&offset, bias, &());
442 }
443
444 if self.reversed {
445 self.range.end = offset;
446 } else {
447 self.range.start = offset;
448 }
449 }
450
451 pub fn peek(&self) -> Option<&'a str> {
452 let chunk = self.chunks.item()?;
453 if self.reversed && self.range.start >= self.chunks.end(&()) {
454 return None;
455 }
456 let chunk_start = *self.chunks.start();
457 if self.range.end <= chunk_start {
458 return None;
459 }
460
461 let start = self.range.start.saturating_sub(chunk_start);
462 let end = self.range.end - chunk_start;
463 Some(&chunk.0[start..chunk.0.len().min(end)])
464 }
465}
466
467impl<'a> Iterator for Chunks<'a> {
468 type Item = &'a str;
469
470 fn next(&mut self) -> Option<Self::Item> {
471 let result = self.peek();
472 if result.is_some() {
473 if self.reversed {
474 self.chunks.prev(&());
475 } else {
476 self.chunks.next(&());
477 }
478 }
479 result
480 }
481}
482
483pub struct Bytes<'a> {
484 chunks: sum_tree::Cursor<'a, Chunk, usize>,
485 range: Range<usize>,
486}
487
488impl<'a> Bytes<'a> {
489 pub fn new(rope: &'a Rope, range: Range<usize>) -> Self {
490 let mut chunks = rope.chunks.cursor();
491 chunks.seek(&range.start, Bias::Right, &());
492 Self { chunks, range }
493 }
494
495 pub fn peek(&self) -> Option<&'a [u8]> {
496 let chunk = self.chunks.item()?;
497 let chunk_start = *self.chunks.start();
498 if self.range.end <= chunk_start {
499 return None;
500 }
501
502 let start = self.range.start.saturating_sub(chunk_start);
503 let end = self.range.end - chunk_start;
504 Some(&chunk.0.as_bytes()[start..chunk.0.len().min(end)])
505 }
506}
507
508impl<'a> Iterator for Bytes<'a> {
509 type Item = &'a [u8];
510
511 fn next(&mut self) -> Option<Self::Item> {
512 let result = self.peek();
513 if result.is_some() {
514 self.chunks.next(&());
515 }
516 result
517 }
518}
519
520impl<'a> io::Read for Bytes<'a> {
521 fn read(&mut self, buf: &mut [u8]) -> io::Result<usize> {
522 if let Some(chunk) = self.peek() {
523 let len = cmp::min(buf.len(), chunk.len());
524 buf[..len].copy_from_slice(&chunk[..len]);
525 self.range.start += len;
526 if len == chunk.len() {
527 self.chunks.next(&());
528 }
529 Ok(len)
530 } else {
531 Ok(0)
532 }
533 }
534}
535
536#[derive(Clone, Debug, Default)]
537struct Chunk(ArrayString<{ 2 * CHUNK_BASE }>);
538
539impl Chunk {
540 fn offset_to_point(&self, target: usize) -> Point {
541 let mut offset = 0;
542 let mut point = Point::new(0, 0);
543 for ch in self.0.chars() {
544 if offset >= target {
545 break;
546 }
547
548 if ch == '\n' {
549 point.row += 1;
550 point.column = 0;
551 } else {
552 point.column += ch.len_utf8() as u32;
553 }
554 offset += ch.len_utf8();
555 }
556 point
557 }
558
559 fn offset_to_point_utf16(&self, target: usize) -> PointUtf16 {
560 let mut offset = 0;
561 let mut point = PointUtf16::new(0, 0);
562 for ch in self.0.chars() {
563 if offset >= target {
564 break;
565 }
566
567 if ch == '\n' {
568 point.row += 1;
569 point.column = 0;
570 } else {
571 point.column += ch.len_utf16() as u32;
572 }
573 offset += ch.len_utf8();
574 }
575 point
576 }
577
578 fn point_to_offset(&self, target: Point) -> usize {
579 let mut offset = 0;
580 let mut point = Point::new(0, 0);
581 for ch in self.0.chars() {
582 if point >= target {
583 if point > target {
584 panic!("point {:?} is inside of character {:?}", target, ch);
585 }
586 break;
587 }
588
589 if ch == '\n' {
590 point.row += 1;
591 if point.row > target.row {
592 panic!(
593 "point {:?} is beyond the end of a line with length {}",
594 target, point.column
595 );
596 }
597 point.column = 0;
598 } else {
599 point.column += ch.len_utf8() as u32;
600 }
601 offset += ch.len_utf8();
602 }
603 offset
604 }
605
606 fn point_to_point_utf16(&self, target: Point) -> PointUtf16 {
607 let mut point = Point::zero();
608 let mut point_utf16 = PointUtf16::new(0, 0);
609 for ch in self.0.chars() {
610 if point >= target {
611 break;
612 }
613
614 if ch == '\n' {
615 point_utf16.row += 1;
616 point_utf16.column = 0;
617 point.row += 1;
618 point.column = 0;
619 } else {
620 point_utf16.column += ch.len_utf16() as u32;
621 point.column += ch.len_utf8() as u32;
622 }
623 }
624 point_utf16
625 }
626
627 fn point_utf16_to_offset(&self, target: PointUtf16) -> usize {
628 let mut offset = 0;
629 let mut point = PointUtf16::new(0, 0);
630 for ch in self.0.chars() {
631 if point >= target {
632 if point > target {
633 panic!("point {:?} is inside of character {:?}", target, ch);
634 }
635 break;
636 }
637
638 if ch == '\n' {
639 point.row += 1;
640 if point.row > target.row {
641 panic!(
642 "point {:?} is beyond the end of a line with length {}",
643 target, point.column
644 );
645 }
646 point.column = 0;
647 } else {
648 point.column += ch.len_utf16() as u32;
649 }
650 offset += ch.len_utf8();
651 }
652 offset
653 }
654
655 fn point_utf16_to_point(&self, target: PointUtf16) -> Point {
656 let mut point = Point::zero();
657 let mut point_utf16 = PointUtf16::zero();
658 for ch in self.0.chars() {
659 if point_utf16 >= target {
660 if point_utf16 > target {
661 panic!("point {:?} is inside of character {:?}", target, ch);
662 }
663 break;
664 }
665
666 if ch == '\n' {
667 point_utf16 += PointUtf16::new(1, 0);
668 point += Point::new(1, 0);
669 } else {
670 point_utf16 += PointUtf16::new(0, ch.len_utf16() as u32);
671 point += Point::new(0, ch.len_utf8() as u32);
672 }
673 }
674 point
675 }
676
677 fn clip_point(&self, target: Point, bias: Bias) -> Point {
678 for (row, line) in self.0.split('\n').enumerate() {
679 if row == target.row as usize {
680 let mut column = target.column.min(line.len() as u32);
681 while !line.is_char_boundary(column as usize) {
682 match bias {
683 Bias::Left => column -= 1,
684 Bias::Right => column += 1,
685 }
686 }
687 return Point::new(row as u32, column);
688 }
689 }
690 unreachable!()
691 }
692
693 fn clip_point_utf16(&self, target: PointUtf16, bias: Bias) -> PointUtf16 {
694 for (row, line) in self.0.split('\n').enumerate() {
695 if row == target.row as usize {
696 let mut code_units = line.encode_utf16();
697 let mut column = code_units.by_ref().take(target.column as usize).count();
698 if char::decode_utf16(code_units).next().transpose().is_err() {
699 match bias {
700 Bias::Left => column -= 1,
701 Bias::Right => column += 1,
702 }
703 }
704 return PointUtf16::new(row as u32, column as u32);
705 }
706 }
707 unreachable!()
708 }
709}
710
711impl sum_tree::Item for Chunk {
712 type Summary = TextSummary;
713
714 fn summary(&self) -> Self::Summary {
715 TextSummary::from(self.0.as_str())
716 }
717}
718
719#[derive(Clone, Debug, Default, Eq, PartialEq)]
720pub struct TextSummary {
721 pub bytes: usize,
722 pub lines: Point,
723 pub lines_utf16: PointUtf16,
724 pub first_line_chars: u32,
725 pub last_line_chars: u32,
726 pub longest_row: u32,
727 pub longest_row_chars: u32,
728}
729
730impl<'a> From<&'a str> for TextSummary {
731 fn from(text: &'a str) -> Self {
732 let mut lines = Point::new(0, 0);
733 let mut lines_utf16 = PointUtf16::new(0, 0);
734 let mut first_line_chars = 0;
735 let mut last_line_chars = 0;
736 let mut longest_row = 0;
737 let mut longest_row_chars = 0;
738 for c in text.chars() {
739 if c == '\n' {
740 lines += Point::new(1, 0);
741 lines_utf16 += PointUtf16::new(1, 0);
742 last_line_chars = 0;
743 } else {
744 lines.column += c.len_utf8() as u32;
745 lines_utf16.column += c.len_utf16() as u32;
746 last_line_chars += 1;
747 }
748
749 if lines.row == 0 {
750 first_line_chars = last_line_chars;
751 }
752
753 if last_line_chars > longest_row_chars {
754 longest_row = lines.row;
755 longest_row_chars = last_line_chars;
756 }
757 }
758
759 TextSummary {
760 bytes: text.len(),
761 lines,
762 lines_utf16,
763 first_line_chars,
764 last_line_chars,
765 longest_row,
766 longest_row_chars,
767 }
768 }
769}
770
771impl sum_tree::Summary for TextSummary {
772 type Context = ();
773
774 fn add_summary(&mut self, summary: &Self, _: &Self::Context) {
775 *self += summary;
776 }
777}
778
779impl<'a> std::ops::Add<Self> for TextSummary {
780 type Output = Self;
781
782 fn add(mut self, rhs: Self) -> Self::Output {
783 self.add_assign(&rhs);
784 self
785 }
786}
787
788impl<'a> std::ops::AddAssign<&'a Self> for TextSummary {
789 fn add_assign(&mut self, other: &'a Self) {
790 let joined_chars = self.last_line_chars + other.first_line_chars;
791 if joined_chars > self.longest_row_chars {
792 self.longest_row = self.lines.row;
793 self.longest_row_chars = joined_chars;
794 }
795 if other.longest_row_chars > self.longest_row_chars {
796 self.longest_row = self.lines.row + other.longest_row;
797 self.longest_row_chars = other.longest_row_chars;
798 }
799
800 if self.lines.row == 0 {
801 self.first_line_chars += other.first_line_chars;
802 }
803
804 if other.lines.row == 0 {
805 self.last_line_chars += other.first_line_chars;
806 } else {
807 self.last_line_chars = other.last_line_chars;
808 }
809
810 self.bytes += other.bytes;
811 self.lines += other.lines;
812 self.lines_utf16 += other.lines_utf16;
813 }
814}
815
816impl std::ops::AddAssign<Self> for TextSummary {
817 fn add_assign(&mut self, other: Self) {
818 *self += &other;
819 }
820}
821
822pub trait TextDimension: 'static + for<'a> Dimension<'a, TextSummary> {
823 fn from_text_summary(summary: &TextSummary) -> Self;
824 fn add_assign(&mut self, other: &Self);
825}
826
827impl<'a, D1: TextDimension, D2: TextDimension> TextDimension for (D1, D2) {
828 fn from_text_summary(summary: &TextSummary) -> Self {
829 (
830 D1::from_text_summary(summary),
831 D2::from_text_summary(summary),
832 )
833 }
834
835 fn add_assign(&mut self, other: &Self) {
836 self.0.add_assign(&other.0);
837 self.1.add_assign(&other.1);
838 }
839}
840
841impl TextDimension for TextSummary {
842 fn from_text_summary(summary: &TextSummary) -> Self {
843 summary.clone()
844 }
845
846 fn add_assign(&mut self, other: &Self) {
847 *self += other;
848 }
849}
850
851impl<'a> sum_tree::Dimension<'a, TextSummary> for usize {
852 fn add_summary(&mut self, summary: &'a TextSummary, _: &()) {
853 *self += summary.bytes;
854 }
855}
856
857impl TextDimension for usize {
858 fn from_text_summary(summary: &TextSummary) -> Self {
859 summary.bytes
860 }
861
862 fn add_assign(&mut self, other: &Self) {
863 *self += other;
864 }
865}
866
867impl<'a> sum_tree::Dimension<'a, TextSummary> for Point {
868 fn add_summary(&mut self, summary: &'a TextSummary, _: &()) {
869 *self += summary.lines;
870 }
871}
872
873impl TextDimension for Point {
874 fn from_text_summary(summary: &TextSummary) -> Self {
875 summary.lines
876 }
877
878 fn add_assign(&mut self, other: &Self) {
879 *self += other;
880 }
881}
882
883impl<'a> sum_tree::Dimension<'a, TextSummary> for PointUtf16 {
884 fn add_summary(&mut self, summary: &'a TextSummary, _: &()) {
885 *self += summary.lines_utf16;
886 }
887}
888
889impl TextDimension for PointUtf16 {
890 fn from_text_summary(summary: &TextSummary) -> Self {
891 summary.lines_utf16
892 }
893
894 fn add_assign(&mut self, other: &Self) {
895 *self += other;
896 }
897}
898
899fn find_split_ix(text: &str) -> usize {
900 let mut ix = text.len() / 2;
901 while !text.is_char_boundary(ix) {
902 if ix < 2 * CHUNK_BASE {
903 ix += 1;
904 } else {
905 ix = (text.len() / 2) - 1;
906 break;
907 }
908 }
909 while !text.is_char_boundary(ix) {
910 ix -= 1;
911 }
912
913 debug_assert!(ix <= 2 * CHUNK_BASE);
914 debug_assert!(text.len() - ix <= 2 * CHUNK_BASE);
915 ix
916}
917
918#[cfg(test)]
919mod tests {
920 use super::*;
921 use crate::random_char_iter::RandomCharIter;
922 use rand::prelude::*;
923 use std::{cmp::Ordering, env, io::Read};
924 use Bias::{Left, Right};
925
926 #[test]
927 fn test_all_4_byte_chars() {
928 let mut rope = Rope::new();
929 let text = "🏀".repeat(256);
930 rope.push(&text);
931 assert_eq!(rope.text(), text);
932 }
933
934 #[test]
935 fn test_clip() {
936 let rope = Rope::from("🧘");
937
938 assert_eq!(rope.clip_offset(1, Bias::Left), 0);
939 assert_eq!(rope.clip_offset(1, Bias::Right), 4);
940 assert_eq!(rope.clip_offset(5, Bias::Right), 4);
941
942 assert_eq!(
943 rope.clip_point(Point::new(0, 1), Bias::Left),
944 Point::new(0, 0)
945 );
946 assert_eq!(
947 rope.clip_point(Point::new(0, 1), Bias::Right),
948 Point::new(0, 4)
949 );
950 assert_eq!(
951 rope.clip_point(Point::new(0, 5), Bias::Right),
952 Point::new(0, 4)
953 );
954
955 assert_eq!(
956 rope.clip_point_utf16(PointUtf16::new(0, 1), Bias::Left),
957 PointUtf16::new(0, 0)
958 );
959 assert_eq!(
960 rope.clip_point_utf16(PointUtf16::new(0, 1), Bias::Right),
961 PointUtf16::new(0, 2)
962 );
963 assert_eq!(
964 rope.clip_point_utf16(PointUtf16::new(0, 3), Bias::Right),
965 PointUtf16::new(0, 2)
966 );
967 }
968
969 #[gpui::test(iterations = 100)]
970 fn test_random_rope(mut rng: StdRng) {
971 let operations = env::var("OPERATIONS")
972 .map(|i| i.parse().expect("invalid `OPERATIONS` variable"))
973 .unwrap_or(10);
974
975 let mut expected = String::new();
976 let mut actual = Rope::new();
977 for _ in 0..operations {
978 let end_ix = clip_offset(&expected, rng.gen_range(0..=expected.len()), Right);
979 let start_ix = clip_offset(&expected, rng.gen_range(0..=end_ix), Left);
980 let len = rng.gen_range(0..=64);
981 let new_text: String = RandomCharIter::new(&mut rng).take(len).collect();
982
983 let mut new_actual = Rope::new();
984 let mut cursor = actual.cursor(0);
985 new_actual.append(cursor.slice(start_ix));
986 new_actual.push(&new_text);
987 cursor.seek_forward(end_ix);
988 new_actual.append(cursor.suffix());
989 actual = new_actual;
990
991 expected.replace_range(start_ix..end_ix, &new_text);
992
993 assert_eq!(actual.text(), expected);
994 log::info!("text: {:?}", expected);
995
996 for _ in 0..5 {
997 let end_ix = clip_offset(&expected, rng.gen_range(0..=expected.len()), Right);
998 let start_ix = clip_offset(&expected, rng.gen_range(0..=end_ix), Left);
999
1000 let actual_text = actual.chunks_in_range(start_ix..end_ix).collect::<String>();
1001 assert_eq!(actual_text, &expected[start_ix..end_ix]);
1002
1003 let mut actual_text = String::new();
1004 actual
1005 .bytes_in_range(start_ix..end_ix)
1006 .read_to_string(&mut actual_text)
1007 .unwrap();
1008 assert_eq!(actual_text, &expected[start_ix..end_ix]);
1009
1010 assert_eq!(
1011 actual
1012 .reversed_chunks_in_range(start_ix..end_ix)
1013 .collect::<Vec<&str>>()
1014 .into_iter()
1015 .rev()
1016 .collect::<String>(),
1017 &expected[start_ix..end_ix]
1018 );
1019 }
1020
1021 let mut point = Point::new(0, 0);
1022 let mut point_utf16 = PointUtf16::new(0, 0);
1023 for (ix, ch) in expected.char_indices().chain(Some((expected.len(), '\0'))) {
1024 assert_eq!(actual.offset_to_point(ix), point, "offset_to_point({})", ix);
1025 assert_eq!(
1026 actual.offset_to_point_utf16(ix),
1027 point_utf16,
1028 "offset_to_point_utf16({})",
1029 ix
1030 );
1031 assert_eq!(
1032 actual.point_to_offset(point),
1033 ix,
1034 "point_to_offset({:?})",
1035 point
1036 );
1037 assert_eq!(
1038 actual.point_utf16_to_offset(point_utf16),
1039 ix,
1040 "point_utf16_to_offset({:?})",
1041 point_utf16
1042 );
1043 if ch == '\n' {
1044 point += Point::new(1, 0);
1045 point_utf16 += PointUtf16::new(1, 0);
1046 } else {
1047 point.column += ch.len_utf8() as u32;
1048 point_utf16.column += ch.len_utf16() as u32;
1049 }
1050 }
1051
1052 let mut point_utf16 = PointUtf16::zero();
1053 for unit in expected.encode_utf16() {
1054 let left_point = actual.clip_point_utf16(point_utf16, Bias::Left);
1055 let right_point = actual.clip_point_utf16(point_utf16, Bias::Right);
1056 assert!(right_point >= left_point);
1057 // Ensure translating UTF-16 points to offsets doesn't panic.
1058 actual.point_utf16_to_offset(left_point);
1059 actual.point_utf16_to_offset(right_point);
1060
1061 if unit == b'\n' as u16 {
1062 point_utf16 += PointUtf16::new(1, 0);
1063 } else {
1064 point_utf16 += PointUtf16::new(0, 1);
1065 }
1066 }
1067
1068 for _ in 0..5 {
1069 let end_ix = clip_offset(&expected, rng.gen_range(0..=expected.len()), Right);
1070 let start_ix = clip_offset(&expected, rng.gen_range(0..=end_ix), Left);
1071 assert_eq!(
1072 actual.cursor(start_ix).summary::<TextSummary>(end_ix),
1073 TextSummary::from(&expected[start_ix..end_ix])
1074 );
1075 }
1076
1077 let mut expected_longest_rows = Vec::new();
1078 let mut longest_line_len = -1_isize;
1079 for (row, line) in expected.split('\n').enumerate() {
1080 let row = row as u32;
1081 assert_eq!(
1082 actual.line_len(row),
1083 line.len() as u32,
1084 "invalid line len for row {}",
1085 row
1086 );
1087
1088 let line_char_count = line.chars().count() as isize;
1089 match line_char_count.cmp(&longest_line_len) {
1090 Ordering::Less => {}
1091 Ordering::Equal => expected_longest_rows.push(row),
1092 Ordering::Greater => {
1093 longest_line_len = line_char_count;
1094 expected_longest_rows.clear();
1095 expected_longest_rows.push(row);
1096 }
1097 }
1098 }
1099
1100 let longest_row = actual.summary().longest_row;
1101 assert!(
1102 expected_longest_rows.contains(&longest_row),
1103 "incorrect longest row {}. expected {:?} with length {}",
1104 longest_row,
1105 expected_longest_rows,
1106 longest_line_len,
1107 );
1108 }
1109 }
1110
1111 fn clip_offset(text: &str, mut offset: usize, bias: Bias) -> usize {
1112 while !text.is_char_boundary(offset) {
1113 match bias {
1114 Bias::Left => offset -= 1,
1115 Bias::Right => offset += 1,
1116 }
1117 }
1118 offset
1119 }
1120
1121 impl Rope {
1122 fn text(&self) -> String {
1123 let mut text = String::new();
1124 for chunk in self.chunks.cursor::<()>() {
1125 text.push_str(&chunk.0);
1126 }
1127 text
1128 }
1129 }
1130}