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