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