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