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