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