1use crate::PointUtf16;
2
3use super::Point;
4use arrayvec::ArrayString;
5use smallvec::SmallVec;
6use std::{cmp, fmt, 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_at(&self, start: usize) -> impl Iterator<Item = u8> + '_ {
141 self.chunks_in_range(start..self.len()).flat_map(str::bytes)
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_offset(&self, point: Point) -> usize {
183 if point >= self.summary().lines {
184 return self.summary().bytes;
185 }
186 let mut cursor = self.chunks.cursor::<(Point, usize)>();
187 cursor.seek(&point, Bias::Left, &());
188 let overshoot = point - cursor.start().0;
189 cursor.start().1
190 + cursor
191 .item()
192 .map_or(0, |chunk| chunk.point_to_offset(overshoot))
193 }
194
195 pub fn point_utf16_to_offset(&self, point: PointUtf16) -> usize {
196 if point >= self.summary().lines_utf16 {
197 return self.summary().bytes;
198 }
199 let mut cursor = self.chunks.cursor::<(PointUtf16, 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_utf16_to_offset(overshoot))
206 }
207
208 pub fn clip_offset(&self, mut offset: usize, bias: Bias) -> usize {
209 let mut cursor = self.chunks.cursor::<usize>();
210 cursor.seek(&offset, Bias::Left, &());
211 if let Some(chunk) = cursor.item() {
212 let mut ix = offset - cursor.start();
213 while !chunk.0.is_char_boundary(ix) {
214 match bias {
215 Bias::Left => {
216 ix -= 1;
217 offset -= 1;
218 }
219 Bias::Right => {
220 ix += 1;
221 offset += 1;
222 }
223 }
224 }
225 offset
226 } else {
227 self.summary().bytes
228 }
229 }
230
231 pub fn clip_point(&self, point: Point, bias: Bias) -> Point {
232 let mut cursor = self.chunks.cursor::<Point>();
233 cursor.seek(&point, Bias::Right, &());
234 if let Some(chunk) = cursor.item() {
235 let overshoot = point - cursor.start();
236 *cursor.start() + chunk.clip_point(overshoot, bias)
237 } else {
238 self.summary().lines
239 }
240 }
241
242 pub fn clip_point_utf16(&self, point: PointUtf16, bias: Bias) -> PointUtf16 {
243 let mut cursor = self.chunks.cursor::<PointUtf16>();
244 cursor.seek(&point, Bias::Right, &());
245 if let Some(chunk) = cursor.item() {
246 let overshoot = point - cursor.start();
247 *cursor.start() + chunk.clip_point_utf16(overshoot, bias)
248 } else {
249 self.summary().lines_utf16
250 }
251 }
252}
253
254impl<'a> From<&'a str> for Rope {
255 fn from(text: &'a str) -> Self {
256 let mut rope = Self::new();
257 rope.push(text);
258 rope
259 }
260}
261
262impl fmt::Display for Rope {
263 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
264 for chunk in self.chunks() {
265 write!(f, "{}", chunk)?;
266 }
267 Ok(())
268 }
269}
270
271pub struct Cursor<'a> {
272 rope: &'a Rope,
273 chunks: sum_tree::Cursor<'a, Chunk, usize>,
274 offset: usize,
275}
276
277impl<'a> Cursor<'a> {
278 pub fn new(rope: &'a Rope, offset: usize) -> Self {
279 let mut chunks = rope.chunks.cursor();
280 chunks.seek(&offset, Bias::Right, &());
281 Self {
282 rope,
283 chunks,
284 offset,
285 }
286 }
287
288 pub fn seek_forward(&mut self, end_offset: usize) {
289 debug_assert!(end_offset >= self.offset);
290
291 self.chunks.seek_forward(&end_offset, Bias::Right, &());
292 self.offset = end_offset;
293 }
294
295 pub fn slice(&mut self, end_offset: usize) -> Rope {
296 debug_assert!(
297 end_offset >= self.offset,
298 "cannot slice backwards from {} to {}",
299 self.offset,
300 end_offset
301 );
302
303 let mut slice = Rope::new();
304 if let Some(start_chunk) = self.chunks.item() {
305 let start_ix = self.offset - self.chunks.start();
306 let end_ix = cmp::min(end_offset, self.chunks.end(&())) - self.chunks.start();
307 slice.push(&start_chunk.0[start_ix..end_ix]);
308 }
309
310 if end_offset > self.chunks.end(&()) {
311 self.chunks.next(&());
312 slice.append(Rope {
313 chunks: self.chunks.slice(&end_offset, Bias::Right, &()),
314 });
315 if let Some(end_chunk) = self.chunks.item() {
316 let end_ix = end_offset - self.chunks.start();
317 slice.push(&end_chunk.0[..end_ix]);
318 }
319 }
320
321 self.offset = end_offset;
322 slice
323 }
324
325 pub fn summary<D: TextDimension<'a>>(&mut self, end_offset: usize) -> D {
326 debug_assert!(end_offset >= self.offset);
327
328 let mut summary = D::default();
329 if let Some(start_chunk) = self.chunks.item() {
330 let start_ix = self.offset - self.chunks.start();
331 let end_ix = cmp::min(end_offset, self.chunks.end(&())) - self.chunks.start();
332 summary.add_assign(&D::from_text_summary(&TextSummary::from(
333 &start_chunk.0[start_ix..end_ix],
334 )));
335 }
336
337 if end_offset > self.chunks.end(&()) {
338 self.chunks.next(&());
339 summary.add_assign(&self.chunks.summary(&end_offset, Bias::Right, &()));
340 if let Some(end_chunk) = self.chunks.item() {
341 let end_ix = end_offset - self.chunks.start();
342 summary.add_assign(&D::from_text_summary(&TextSummary::from(
343 &end_chunk.0[..end_ix],
344 )));
345 }
346 }
347
348 self.offset = end_offset;
349 summary
350 }
351
352 pub fn suffix(mut self) -> Rope {
353 self.slice(self.rope.chunks.extent(&()))
354 }
355
356 pub fn offset(&self) -> usize {
357 self.offset
358 }
359}
360
361pub struct Chunks<'a> {
362 chunks: sum_tree::Cursor<'a, Chunk, usize>,
363 range: Range<usize>,
364 reversed: bool,
365}
366
367impl<'a> Chunks<'a> {
368 pub fn new(rope: &'a Rope, range: Range<usize>, reversed: bool) -> Self {
369 let mut chunks = rope.chunks.cursor();
370 if reversed {
371 chunks.seek(&range.end, Bias::Left, &());
372 } else {
373 chunks.seek(&range.start, Bias::Right, &());
374 }
375 Self {
376 chunks,
377 range,
378 reversed,
379 }
380 }
381
382 pub fn offset(&self) -> usize {
383 if self.reversed {
384 self.range.end.min(self.chunks.end(&()))
385 } else {
386 self.range.start.max(*self.chunks.start())
387 }
388 }
389
390 pub fn seek(&mut self, offset: usize) {
391 let bias = if self.reversed {
392 Bias::Left
393 } else {
394 Bias::Right
395 };
396
397 if offset >= self.chunks.end(&()) {
398 self.chunks.seek_forward(&offset, bias, &());
399 } else {
400 self.chunks.seek(&offset, bias, &());
401 }
402
403 if self.reversed {
404 self.range.end = offset;
405 } else {
406 self.range.start = offset;
407 }
408 }
409
410 pub fn peek(&self) -> Option<&'a str> {
411 let chunk = self.chunks.item()?;
412 if self.reversed && self.range.start >= self.chunks.end(&()) {
413 return None;
414 }
415 let chunk_start = *self.chunks.start();
416 if self.range.end <= chunk_start {
417 return None;
418 }
419
420 let start = self.range.start.saturating_sub(chunk_start);
421 let end = self.range.end - chunk_start;
422 Some(&chunk.0[start..chunk.0.len().min(end)])
423 }
424}
425
426impl<'a> Iterator for Chunks<'a> {
427 type Item = &'a str;
428
429 fn next(&mut self) -> Option<Self::Item> {
430 let result = self.peek();
431 if result.is_some() {
432 if self.reversed {
433 self.chunks.prev(&());
434 } else {
435 self.chunks.next(&());
436 }
437 }
438 result
439 }
440}
441
442#[derive(Clone, Debug, Default)]
443struct Chunk(ArrayString<{ 2 * CHUNK_BASE }>);
444
445impl Chunk {
446 fn offset_to_point(&self, target: usize) -> Point {
447 let mut offset = 0;
448 let mut point = Point::new(0, 0);
449 for ch in self.0.chars() {
450 if offset >= target {
451 break;
452 }
453
454 if ch == '\n' {
455 point.row += 1;
456 point.column = 0;
457 } else {
458 point.column += ch.len_utf8() as u32;
459 }
460 offset += ch.len_utf8();
461 }
462 point
463 }
464
465 fn offset_to_point_utf16(&self, target: usize) -> PointUtf16 {
466 let mut offset = 0;
467 let mut point = PointUtf16::new(0, 0);
468 for ch in self.0.chars() {
469 if offset >= target {
470 break;
471 }
472
473 if ch == '\n' {
474 point.row += 1;
475 point.column = 0;
476 } else {
477 point.column += ch.len_utf16() as u32;
478 }
479 offset += ch.len_utf8();
480 }
481 point
482 }
483
484 fn point_to_offset(&self, target: Point) -> usize {
485 let mut offset = 0;
486 let mut point = Point::new(0, 0);
487 for ch in self.0.chars() {
488 if point >= target {
489 if point > target {
490 panic!("point {:?} is inside of character {:?}", target, ch);
491 }
492 break;
493 }
494
495 if ch == '\n' {
496 point.row += 1;
497 point.column = 0;
498 } else {
499 point.column += ch.len_utf8() as u32;
500 }
501 offset += ch.len_utf8();
502 }
503 offset
504 }
505
506 fn point_utf16_to_offset(&self, target: PointUtf16) -> usize {
507 let mut offset = 0;
508 let mut point = PointUtf16::new(0, 0);
509 for ch in self.0.chars() {
510 if point >= target {
511 if point > target {
512 panic!("point {:?} is inside of character {:?}", target, ch);
513 }
514 break;
515 }
516
517 if ch == '\n' {
518 point.row += 1;
519 point.column = 0;
520 } else {
521 point.column += ch.len_utf16() as u32;
522 }
523 offset += ch.len_utf8();
524 }
525 offset
526 }
527
528 fn clip_point(&self, target: Point, bias: Bias) -> Point {
529 for (row, line) in self.0.split('\n').enumerate() {
530 if row == target.row as usize {
531 let mut column = target.column.min(line.len() as u32);
532 while !line.is_char_boundary(column as usize) {
533 match bias {
534 Bias::Left => column -= 1,
535 Bias::Right => column += 1,
536 }
537 }
538 return Point::new(row as u32, column);
539 }
540 }
541 unreachable!()
542 }
543
544 fn clip_point_utf16(&self, target: PointUtf16, bias: Bias) -> PointUtf16 {
545 for (row, line) in self.0.split('\n').enumerate() {
546 if row == target.row as usize {
547 let mut code_units = line.encode_utf16();
548 let mut column = code_units.by_ref().take(target.column as usize).count();
549 if char::decode_utf16(code_units).next().transpose().is_err() {
550 match bias {
551 Bias::Left => column -= 1,
552 Bias::Right => column += 1,
553 }
554 }
555 return PointUtf16::new(row as u32, column as u32);
556 }
557 }
558 unreachable!()
559 }
560}
561
562impl sum_tree::Item for Chunk {
563 type Summary = TextSummary;
564
565 fn summary(&self) -> Self::Summary {
566 TextSummary::from(self.0.as_str())
567 }
568}
569
570#[derive(Clone, Debug, Default, Eq, PartialEq)]
571pub struct TextSummary {
572 pub bytes: usize,
573 pub lines: Point,
574 pub lines_utf16: PointUtf16,
575 pub first_line_chars: u32,
576 pub last_line_chars: u32,
577 pub longest_row: u32,
578 pub longest_row_chars: u32,
579}
580
581impl<'a> From<&'a str> for TextSummary {
582 fn from(text: &'a str) -> Self {
583 let mut lines = Point::new(0, 0);
584 let mut lines_utf16 = PointUtf16::new(0, 0);
585 let mut first_line_chars = 0;
586 let mut last_line_chars = 0;
587 let mut longest_row = 0;
588 let mut longest_row_chars = 0;
589 for c in text.chars() {
590 if c == '\n' {
591 lines += Point::new(1, 0);
592 lines_utf16 += PointUtf16::new(1, 0);
593 last_line_chars = 0;
594 } else {
595 lines.column += c.len_utf8() as u32;
596 lines_utf16.column += c.len_utf16() as u32;
597 last_line_chars += 1;
598 }
599
600 if lines.row == 0 {
601 first_line_chars = last_line_chars;
602 }
603
604 if last_line_chars > longest_row_chars {
605 longest_row = lines.row;
606 longest_row_chars = last_line_chars;
607 }
608 }
609
610 TextSummary {
611 bytes: text.len(),
612 lines,
613 lines_utf16,
614 first_line_chars,
615 last_line_chars,
616 longest_row,
617 longest_row_chars,
618 }
619 }
620}
621
622impl sum_tree::Summary for TextSummary {
623 type Context = ();
624
625 fn add_summary(&mut self, summary: &Self, _: &Self::Context) {
626 *self += summary;
627 }
628}
629
630impl<'a> std::ops::AddAssign<&'a Self> for TextSummary {
631 fn add_assign(&mut self, other: &'a Self) {
632 let joined_chars = self.last_line_chars + other.first_line_chars;
633 if joined_chars > self.longest_row_chars {
634 self.longest_row = self.lines.row;
635 self.longest_row_chars = joined_chars;
636 }
637 if other.longest_row_chars > self.longest_row_chars {
638 self.longest_row = self.lines.row + other.longest_row;
639 self.longest_row_chars = other.longest_row_chars;
640 }
641
642 if self.lines.row == 0 {
643 self.first_line_chars += other.first_line_chars;
644 }
645
646 if other.lines.row == 0 {
647 self.last_line_chars += other.first_line_chars;
648 } else {
649 self.last_line_chars = other.last_line_chars;
650 }
651
652 self.bytes += other.bytes;
653 self.lines += other.lines;
654 self.lines_utf16 += other.lines_utf16;
655 }
656}
657
658impl std::ops::AddAssign<Self> for TextSummary {
659 fn add_assign(&mut self, other: Self) {
660 *self += &other;
661 }
662}
663
664pub trait TextDimension<'a>: Dimension<'a, TextSummary> {
665 fn from_text_summary(summary: &TextSummary) -> Self;
666 fn add_assign(&mut self, other: &Self);
667}
668
669impl<'a, D1: TextDimension<'a>, D2: TextDimension<'a>> TextDimension<'a> for (D1, D2) {
670 fn from_text_summary(summary: &TextSummary) -> Self {
671 (
672 D1::from_text_summary(summary),
673 D2::from_text_summary(summary),
674 )
675 }
676
677 fn add_assign(&mut self, other: &Self) {
678 self.0.add_assign(&other.0);
679 self.1.add_assign(&other.1);
680 }
681}
682
683impl<'a> TextDimension<'a> for TextSummary {
684 fn from_text_summary(summary: &TextSummary) -> Self {
685 summary.clone()
686 }
687
688 fn add_assign(&mut self, other: &Self) {
689 *self += other;
690 }
691}
692
693impl<'a> sum_tree::Dimension<'a, TextSummary> for usize {
694 fn add_summary(&mut self, summary: &'a TextSummary, _: &()) {
695 *self += summary.bytes;
696 }
697}
698
699impl<'a> TextDimension<'a> for usize {
700 fn from_text_summary(summary: &TextSummary) -> Self {
701 summary.bytes
702 }
703
704 fn add_assign(&mut self, other: &Self) {
705 *self += other;
706 }
707}
708
709impl<'a> sum_tree::Dimension<'a, TextSummary> for Point {
710 fn add_summary(&mut self, summary: &'a TextSummary, _: &()) {
711 *self += summary.lines;
712 }
713}
714
715impl<'a> TextDimension<'a> for Point {
716 fn from_text_summary(summary: &TextSummary) -> Self {
717 summary.lines
718 }
719
720 fn add_assign(&mut self, other: &Self) {
721 *self += other;
722 }
723}
724
725impl<'a> sum_tree::Dimension<'a, TextSummary> for PointUtf16 {
726 fn add_summary(&mut self, summary: &'a TextSummary, _: &()) {
727 *self += summary.lines_utf16;
728 }
729}
730
731impl<'a> TextDimension<'a> for PointUtf16 {
732 fn from_text_summary(summary: &TextSummary) -> Self {
733 summary.lines_utf16
734 }
735
736 fn add_assign(&mut self, other: &Self) {
737 *self += other;
738 }
739}
740
741fn find_split_ix(text: &str) -> usize {
742 let mut ix = text.len() / 2;
743 while !text.is_char_boundary(ix) {
744 if ix < 2 * CHUNK_BASE {
745 ix += 1;
746 } else {
747 ix = (text.len() / 2) - 1;
748 break;
749 }
750 }
751 while !text.is_char_boundary(ix) {
752 ix -= 1;
753 }
754
755 debug_assert!(ix <= 2 * CHUNK_BASE);
756 debug_assert!(text.len() - ix <= 2 * CHUNK_BASE);
757 ix
758}
759
760#[cfg(test)]
761mod tests {
762 use super::*;
763 use crate::random_char_iter::RandomCharIter;
764 use rand::prelude::*;
765 use std::env;
766 use Bias::{Left, Right};
767
768 #[test]
769 fn test_all_4_byte_chars() {
770 let mut rope = Rope::new();
771 let text = "🏀".repeat(256);
772 rope.push(&text);
773 assert_eq!(rope.text(), text);
774 }
775
776 #[test]
777 fn test_clip() {
778 let rope = Rope::from("🧘");
779
780 assert_eq!(rope.clip_offset(1, Bias::Left), 0);
781 assert_eq!(rope.clip_offset(1, Bias::Right), 4);
782 assert_eq!(rope.clip_offset(5, Bias::Right), 4);
783
784 assert_eq!(
785 rope.clip_point(Point::new(0, 1), Bias::Left),
786 Point::new(0, 0)
787 );
788 assert_eq!(
789 rope.clip_point(Point::new(0, 1), Bias::Right),
790 Point::new(0, 4)
791 );
792 assert_eq!(
793 rope.clip_point(Point::new(0, 5), Bias::Right),
794 Point::new(0, 4)
795 );
796
797 assert_eq!(
798 rope.clip_point_utf16(PointUtf16::new(0, 1), Bias::Left),
799 PointUtf16::new(0, 0)
800 );
801 assert_eq!(
802 rope.clip_point_utf16(PointUtf16::new(0, 1), Bias::Right),
803 PointUtf16::new(0, 2)
804 );
805 assert_eq!(
806 rope.clip_point_utf16(PointUtf16::new(0, 3), Bias::Right),
807 PointUtf16::new(0, 2)
808 );
809 }
810
811 #[gpui::test(iterations = 100)]
812 fn test_random(mut rng: StdRng) {
813 let operations = env::var("OPERATIONS")
814 .map(|i| i.parse().expect("invalid `OPERATIONS` variable"))
815 .unwrap_or(10);
816
817 let mut expected = String::new();
818 let mut actual = Rope::new();
819 for _ in 0..operations {
820 let end_ix = clip_offset(&expected, rng.gen_range(0..=expected.len()), Right);
821 let start_ix = clip_offset(&expected, rng.gen_range(0..=end_ix), Left);
822 let len = rng.gen_range(0..=64);
823 let new_text: String = RandomCharIter::new(&mut rng).take(len).collect();
824
825 let mut new_actual = Rope::new();
826 let mut cursor = actual.cursor(0);
827 new_actual.append(cursor.slice(start_ix));
828 new_actual.push(&new_text);
829 cursor.seek_forward(end_ix);
830 new_actual.append(cursor.suffix());
831 actual = new_actual;
832
833 expected.replace_range(start_ix..end_ix, &new_text);
834
835 assert_eq!(actual.text(), expected);
836 log::info!("text: {:?}", expected);
837
838 for _ in 0..5 {
839 let end_ix = clip_offset(&expected, rng.gen_range(0..=expected.len()), Right);
840 let start_ix = clip_offset(&expected, rng.gen_range(0..=end_ix), Left);
841 assert_eq!(
842 actual.chunks_in_range(start_ix..end_ix).collect::<String>(),
843 &expected[start_ix..end_ix]
844 );
845
846 assert_eq!(
847 actual
848 .reversed_chunks_in_range(start_ix..end_ix)
849 .collect::<Vec<&str>>()
850 .into_iter()
851 .rev()
852 .collect::<String>(),
853 &expected[start_ix..end_ix]
854 );
855 }
856
857 let mut point = Point::new(0, 0);
858 let mut point_utf16 = PointUtf16::new(0, 0);
859 for (ix, ch) in expected.char_indices().chain(Some((expected.len(), '\0'))) {
860 assert_eq!(actual.offset_to_point(ix), point, "offset_to_point({})", ix);
861 assert_eq!(
862 actual.offset_to_point_utf16(ix),
863 point_utf16,
864 "offset_to_point_utf16({})",
865 ix
866 );
867 assert_eq!(
868 actual.point_to_offset(point),
869 ix,
870 "point_to_offset({:?})",
871 point
872 );
873 assert_eq!(
874 actual.point_utf16_to_offset(point_utf16),
875 ix,
876 "point_utf16_to_offset({:?})",
877 point_utf16
878 );
879 if ch == '\n' {
880 point += Point::new(1, 0);
881 point_utf16 += PointUtf16::new(1, 0);
882 } else {
883 point.column += ch.len_utf8() as u32;
884 point_utf16.column += ch.len_utf16() as u32;
885 }
886 }
887
888 for _ in 0..5 {
889 let end_ix = clip_offset(&expected, rng.gen_range(0..=expected.len()), Right);
890 let start_ix = clip_offset(&expected, rng.gen_range(0..=end_ix), Left);
891 assert_eq!(
892 actual.cursor(start_ix).summary::<TextSummary>(end_ix),
893 TextSummary::from(&expected[start_ix..end_ix])
894 );
895 }
896 }
897 }
898
899 fn clip_offset(text: &str, mut offset: usize, bias: Bias) -> usize {
900 while !text.is_char_boundary(offset) {
901 match bias {
902 Bias::Left => offset -= 1,
903 Bias::Right => offset += 1,
904 }
905 }
906 offset
907 }
908
909 impl Rope {
910 fn text(&self) -> String {
911 let mut text = String::new();
912 for chunk in self.chunks.cursor::<()>() {
913 text.push_str(&chunk.0);
914 }
915 text
916 }
917 }
918}