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