1use crate::PointUtf16;
2
3use super::Point;
4use arrayvec::ArrayString;
5use smallvec::SmallVec;
6use std::{cmp, fmt, io, 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_in_range(&self, range: Range<usize>) -> Bytes {
141 Bytes::new(self, range)
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>(&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
447pub struct Bytes<'a> {
448 chunks: sum_tree::Cursor<'a, Chunk, usize>,
449 range: Range<usize>,
450}
451
452impl<'a> Bytes<'a> {
453 pub fn new(rope: &'a Rope, range: Range<usize>) -> Self {
454 let mut chunks = rope.chunks.cursor();
455 chunks.seek(&range.start, Bias::Right, &());
456 Self { chunks, range }
457 }
458
459 pub fn peek(&self) -> Option<&'a [u8]> {
460 let chunk = self.chunks.item()?;
461 let chunk_start = *self.chunks.start();
462 if self.range.end <= chunk_start {
463 return None;
464 }
465
466 let start = self.range.start.saturating_sub(chunk_start);
467 let end = self.range.end - chunk_start;
468 Some(&chunk.0.as_bytes()[start..chunk.0.len().min(end)])
469 }
470}
471
472impl<'a> Iterator for Bytes<'a> {
473 type Item = &'a [u8];
474
475 fn next(&mut self) -> Option<Self::Item> {
476 let result = self.peek();
477 if result.is_some() {
478 self.chunks.next(&());
479 }
480 result
481 }
482}
483
484impl<'a> io::Read for Bytes<'a> {
485 fn read(&mut self, buf: &mut [u8]) -> io::Result<usize> {
486 if let Some(chunk) = self.peek() {
487 let len = cmp::min(buf.len(), chunk.len());
488 buf[..len].copy_from_slice(&chunk[..len]);
489 self.range.start += len;
490 if len == chunk.len() {
491 self.chunks.next(&());
492 }
493 Ok(len)
494 } else {
495 Ok(0)
496 }
497 }
498}
499
500#[derive(Clone, Debug, Default)]
501struct Chunk(ArrayString<{ 2 * CHUNK_BASE }>);
502
503impl Chunk {
504 fn offset_to_point(&self, target: usize) -> Point {
505 let mut offset = 0;
506 let mut point = Point::new(0, 0);
507 for ch in self.0.chars() {
508 if offset >= target {
509 break;
510 }
511
512 if ch == '\n' {
513 point.row += 1;
514 point.column = 0;
515 } else {
516 point.column += ch.len_utf8() as u32;
517 }
518 offset += ch.len_utf8();
519 }
520 point
521 }
522
523 fn offset_to_point_utf16(&self, target: usize) -> PointUtf16 {
524 let mut offset = 0;
525 let mut point = PointUtf16::new(0, 0);
526 for ch in self.0.chars() {
527 if offset >= target {
528 break;
529 }
530
531 if ch == '\n' {
532 point.row += 1;
533 point.column = 0;
534 } else {
535 point.column += ch.len_utf16() as u32;
536 }
537 offset += ch.len_utf8();
538 }
539 point
540 }
541
542 fn point_to_offset(&self, target: Point) -> usize {
543 let mut offset = 0;
544 let mut point = Point::new(0, 0);
545 for ch in self.0.chars() {
546 if point >= target {
547 if point > target {
548 panic!("point {:?} is inside of character {:?}", target, ch);
549 }
550 break;
551 }
552
553 if ch == '\n' {
554 point.row += 1;
555 point.column = 0;
556 } else {
557 point.column += ch.len_utf8() as u32;
558 }
559 offset += ch.len_utf8();
560 }
561 offset
562 }
563
564 fn point_utf16_to_offset(&self, target: PointUtf16) -> usize {
565 let mut offset = 0;
566 let mut point = PointUtf16::new(0, 0);
567 for ch in self.0.chars() {
568 if point >= target {
569 if point > target {
570 panic!("point {:?} is inside of character {:?}", target, ch);
571 }
572 break;
573 }
574
575 if ch == '\n' {
576 point.row += 1;
577 point.column = 0;
578 } else {
579 point.column += ch.len_utf16() as u32;
580 }
581 offset += ch.len_utf8();
582 }
583 offset
584 }
585
586 fn clip_point(&self, target: Point, bias: Bias) -> Point {
587 for (row, line) in self.0.split('\n').enumerate() {
588 if row == target.row as usize {
589 let mut column = target.column.min(line.len() as u32);
590 while !line.is_char_boundary(column as usize) {
591 match bias {
592 Bias::Left => column -= 1,
593 Bias::Right => column += 1,
594 }
595 }
596 return Point::new(row as u32, column);
597 }
598 }
599 unreachable!()
600 }
601
602 fn clip_point_utf16(&self, target: PointUtf16, bias: Bias) -> PointUtf16 {
603 for (row, line) in self.0.split('\n').enumerate() {
604 if row == target.row as usize {
605 let mut code_units = line.encode_utf16();
606 let mut column = code_units.by_ref().take(target.column as usize).count();
607 if char::decode_utf16(code_units).next().transpose().is_err() {
608 match bias {
609 Bias::Left => column -= 1,
610 Bias::Right => column += 1,
611 }
612 }
613 return PointUtf16::new(row as u32, column as u32);
614 }
615 }
616 unreachable!()
617 }
618}
619
620impl sum_tree::Item for Chunk {
621 type Summary = TextSummary;
622
623 fn summary(&self) -> Self::Summary {
624 TextSummary::from(self.0.as_str())
625 }
626}
627
628#[derive(Clone, Debug, Default, Eq, PartialEq)]
629pub struct TextSummary {
630 pub bytes: usize,
631 pub lines: Point,
632 pub lines_utf16: PointUtf16,
633 pub first_line_chars: u32,
634 pub last_line_chars: u32,
635 pub longest_row: u32,
636 pub longest_row_chars: u32,
637}
638
639impl<'a> From<&'a str> for TextSummary {
640 fn from(text: &'a str) -> Self {
641 let mut lines = Point::new(0, 0);
642 let mut lines_utf16 = PointUtf16::new(0, 0);
643 let mut first_line_chars = 0;
644 let mut last_line_chars = 0;
645 let mut longest_row = 0;
646 let mut longest_row_chars = 0;
647 for c in text.chars() {
648 if c == '\n' {
649 lines += Point::new(1, 0);
650 lines_utf16 += PointUtf16::new(1, 0);
651 last_line_chars = 0;
652 } else {
653 lines.column += c.len_utf8() as u32;
654 lines_utf16.column += c.len_utf16() as u32;
655 last_line_chars += 1;
656 }
657
658 if lines.row == 0 {
659 first_line_chars = last_line_chars;
660 }
661
662 if last_line_chars > longest_row_chars {
663 longest_row = lines.row;
664 longest_row_chars = last_line_chars;
665 }
666 }
667
668 TextSummary {
669 bytes: text.len(),
670 lines,
671 lines_utf16,
672 first_line_chars,
673 last_line_chars,
674 longest_row,
675 longest_row_chars,
676 }
677 }
678}
679
680impl sum_tree::Summary for TextSummary {
681 type Context = ();
682
683 fn add_summary(&mut self, summary: &Self, _: &Self::Context) {
684 *self += summary;
685 }
686}
687
688impl<'a> std::ops::Add<Self> for TextSummary {
689 type Output = Self;
690
691 fn add(mut self, rhs: Self) -> Self::Output {
692 self.add_assign(&rhs);
693 self
694 }
695}
696
697impl<'a> std::ops::AddAssign<&'a Self> for TextSummary {
698 fn add_assign(&mut self, other: &'a Self) {
699 let joined_chars = self.last_line_chars + other.first_line_chars;
700 if joined_chars > self.longest_row_chars {
701 self.longest_row = self.lines.row;
702 self.longest_row_chars = joined_chars;
703 }
704 if other.longest_row_chars > self.longest_row_chars {
705 self.longest_row = self.lines.row + other.longest_row;
706 self.longest_row_chars = other.longest_row_chars;
707 }
708
709 if self.lines.row == 0 {
710 self.first_line_chars += other.first_line_chars;
711 }
712
713 if other.lines.row == 0 {
714 self.last_line_chars += other.first_line_chars;
715 } else {
716 self.last_line_chars = other.last_line_chars;
717 }
718
719 self.bytes += other.bytes;
720 self.lines += other.lines;
721 self.lines_utf16 += other.lines_utf16;
722 }
723}
724
725impl std::ops::AddAssign<Self> for TextSummary {
726 fn add_assign(&mut self, other: Self) {
727 *self += &other;
728 }
729}
730
731pub trait TextDimension: 'static + for<'a> Dimension<'a, TextSummary> {
732 fn from_text_summary(summary: &TextSummary) -> Self;
733 fn add_assign(&mut self, other: &Self);
734}
735
736impl<'a, D1: TextDimension, D2: TextDimension> TextDimension for (D1, D2) {
737 fn from_text_summary(summary: &TextSummary) -> Self {
738 (
739 D1::from_text_summary(summary),
740 D2::from_text_summary(summary),
741 )
742 }
743
744 fn add_assign(&mut self, other: &Self) {
745 self.0.add_assign(&other.0);
746 self.1.add_assign(&other.1);
747 }
748}
749
750impl TextDimension for TextSummary {
751 fn from_text_summary(summary: &TextSummary) -> Self {
752 summary.clone()
753 }
754
755 fn add_assign(&mut self, other: &Self) {
756 *self += other;
757 }
758}
759
760impl<'a> sum_tree::Dimension<'a, TextSummary> for usize {
761 fn add_summary(&mut self, summary: &'a TextSummary, _: &()) {
762 *self += summary.bytes;
763 }
764}
765
766impl TextDimension for usize {
767 fn from_text_summary(summary: &TextSummary) -> Self {
768 summary.bytes
769 }
770
771 fn add_assign(&mut self, other: &Self) {
772 *self += other;
773 }
774}
775
776impl<'a> sum_tree::Dimension<'a, TextSummary> for Point {
777 fn add_summary(&mut self, summary: &'a TextSummary, _: &()) {
778 *self += summary.lines;
779 }
780}
781
782impl TextDimension for Point {
783 fn from_text_summary(summary: &TextSummary) -> Self {
784 summary.lines
785 }
786
787 fn add_assign(&mut self, other: &Self) {
788 *self += other;
789 }
790}
791
792impl<'a> sum_tree::Dimension<'a, TextSummary> for PointUtf16 {
793 fn add_summary(&mut self, summary: &'a TextSummary, _: &()) {
794 *self += summary.lines_utf16;
795 }
796}
797
798impl TextDimension for PointUtf16 {
799 fn from_text_summary(summary: &TextSummary) -> Self {
800 summary.lines_utf16
801 }
802
803 fn add_assign(&mut self, other: &Self) {
804 *self += other;
805 }
806}
807
808fn find_split_ix(text: &str) -> usize {
809 let mut ix = text.len() / 2;
810 while !text.is_char_boundary(ix) {
811 if ix < 2 * CHUNK_BASE {
812 ix += 1;
813 } else {
814 ix = (text.len() / 2) - 1;
815 break;
816 }
817 }
818 while !text.is_char_boundary(ix) {
819 ix -= 1;
820 }
821
822 debug_assert!(ix <= 2 * CHUNK_BASE);
823 debug_assert!(text.len() - ix <= 2 * CHUNK_BASE);
824 ix
825}
826
827#[cfg(test)]
828mod tests {
829 use super::*;
830 use crate::random_char_iter::RandomCharIter;
831 use rand::prelude::*;
832 use std::{cmp::Ordering, env, io::Read};
833 use Bias::{Left, Right};
834
835 #[test]
836 fn test_all_4_byte_chars() {
837 let mut rope = Rope::new();
838 let text = "🏀".repeat(256);
839 rope.push(&text);
840 assert_eq!(rope.text(), text);
841 }
842
843 #[test]
844 fn test_clip() {
845 let rope = Rope::from("🧘");
846
847 assert_eq!(rope.clip_offset(1, Bias::Left), 0);
848 assert_eq!(rope.clip_offset(1, Bias::Right), 4);
849 assert_eq!(rope.clip_offset(5, Bias::Right), 4);
850
851 assert_eq!(
852 rope.clip_point(Point::new(0, 1), Bias::Left),
853 Point::new(0, 0)
854 );
855 assert_eq!(
856 rope.clip_point(Point::new(0, 1), Bias::Right),
857 Point::new(0, 4)
858 );
859 assert_eq!(
860 rope.clip_point(Point::new(0, 5), Bias::Right),
861 Point::new(0, 4)
862 );
863
864 assert_eq!(
865 rope.clip_point_utf16(PointUtf16::new(0, 1), Bias::Left),
866 PointUtf16::new(0, 0)
867 );
868 assert_eq!(
869 rope.clip_point_utf16(PointUtf16::new(0, 1), Bias::Right),
870 PointUtf16::new(0, 2)
871 );
872 assert_eq!(
873 rope.clip_point_utf16(PointUtf16::new(0, 3), Bias::Right),
874 PointUtf16::new(0, 2)
875 );
876 }
877
878 #[gpui::test(iterations = 100)]
879 fn test_random_rope(mut rng: StdRng) {
880 let operations = env::var("OPERATIONS")
881 .map(|i| i.parse().expect("invalid `OPERATIONS` variable"))
882 .unwrap_or(10);
883
884 let mut expected = String::new();
885 let mut actual = Rope::new();
886 for _ in 0..operations {
887 let end_ix = clip_offset(&expected, rng.gen_range(0..=expected.len()), Right);
888 let start_ix = clip_offset(&expected, rng.gen_range(0..=end_ix), Left);
889 let len = rng.gen_range(0..=64);
890 let new_text: String = RandomCharIter::new(&mut rng).take(len).collect();
891
892 let mut new_actual = Rope::new();
893 let mut cursor = actual.cursor(0);
894 new_actual.append(cursor.slice(start_ix));
895 new_actual.push(&new_text);
896 cursor.seek_forward(end_ix);
897 new_actual.append(cursor.suffix());
898 actual = new_actual;
899
900 expected.replace_range(start_ix..end_ix, &new_text);
901
902 assert_eq!(actual.text(), expected);
903 log::info!("text: {:?}", expected);
904
905 for _ in 0..5 {
906 let end_ix = clip_offset(&expected, rng.gen_range(0..=expected.len()), Right);
907 let start_ix = clip_offset(&expected, rng.gen_range(0..=end_ix), Left);
908
909 let actual_text = actual.chunks_in_range(start_ix..end_ix).collect::<String>();
910 assert_eq!(actual_text, &expected[start_ix..end_ix]);
911
912 let mut actual_text = String::new();
913 actual
914 .bytes_in_range(start_ix..end_ix)
915 .read_to_string(&mut actual_text)
916 .unwrap();
917 assert_eq!(actual_text, &expected[start_ix..end_ix]);
918
919 assert_eq!(
920 actual
921 .reversed_chunks_in_range(start_ix..end_ix)
922 .collect::<Vec<&str>>()
923 .into_iter()
924 .rev()
925 .collect::<String>(),
926 &expected[start_ix..end_ix]
927 );
928 }
929
930 let mut point = Point::new(0, 0);
931 let mut point_utf16 = PointUtf16::new(0, 0);
932 for (ix, ch) in expected.char_indices().chain(Some((expected.len(), '\0'))) {
933 assert_eq!(actual.offset_to_point(ix), point, "offset_to_point({})", ix);
934 assert_eq!(
935 actual.offset_to_point_utf16(ix),
936 point_utf16,
937 "offset_to_point_utf16({})",
938 ix
939 );
940 assert_eq!(
941 actual.point_to_offset(point),
942 ix,
943 "point_to_offset({:?})",
944 point
945 );
946 assert_eq!(
947 actual.point_utf16_to_offset(point_utf16),
948 ix,
949 "point_utf16_to_offset({:?})",
950 point_utf16
951 );
952 if ch == '\n' {
953 point += Point::new(1, 0);
954 point_utf16 += PointUtf16::new(1, 0);
955 } else {
956 point.column += ch.len_utf8() as u32;
957 point_utf16.column += ch.len_utf16() as u32;
958 }
959 }
960
961 let mut point_utf16 = PointUtf16::zero();
962 for unit in expected.encode_utf16() {
963 let left_point = actual.clip_point_utf16(point_utf16, Bias::Left);
964 let right_point = actual.clip_point_utf16(point_utf16, Bias::Right);
965 assert!(right_point >= left_point);
966 // Ensure translating UTF-16 points to offsets doesn't panic.
967 actual.point_utf16_to_offset(left_point);
968 actual.point_utf16_to_offset(right_point);
969
970 if unit == b'\n' as u16 {
971 point_utf16 += PointUtf16::new(1, 0);
972 } else {
973 point_utf16 += PointUtf16::new(0, 1);
974 }
975 }
976
977 for _ in 0..5 {
978 let end_ix = clip_offset(&expected, rng.gen_range(0..=expected.len()), Right);
979 let start_ix = clip_offset(&expected, rng.gen_range(0..=end_ix), Left);
980 assert_eq!(
981 actual.cursor(start_ix).summary::<TextSummary>(end_ix),
982 TextSummary::from(&expected[start_ix..end_ix])
983 );
984 }
985
986 let mut expected_longest_rows = Vec::new();
987 let mut longest_line_len = -1_isize;
988 for (row, line) in expected.split('\n').enumerate() {
989 let row = row as u32;
990 assert_eq!(
991 actual.line_len(row),
992 line.len() as u32,
993 "invalid line len for row {}",
994 row
995 );
996
997 let line_char_count = line.chars().count() as isize;
998 match line_char_count.cmp(&longest_line_len) {
999 Ordering::Less => {}
1000 Ordering::Equal => expected_longest_rows.push(row),
1001 Ordering::Greater => {
1002 longest_line_len = line_char_count;
1003 expected_longest_rows.clear();
1004 expected_longest_rows.push(row);
1005 }
1006 }
1007 }
1008
1009 let longest_row = actual.summary().longest_row;
1010 assert!(
1011 expected_longest_rows.contains(&longest_row),
1012 "incorrect longest row {}. expected {:?} with length {}",
1013 longest_row,
1014 expected_longest_rows,
1015 longest_line_len,
1016 );
1017 }
1018 }
1019
1020 fn clip_offset(text: &str, mut offset: usize, bias: Bias) -> usize {
1021 while !text.is_char_boundary(offset) {
1022 match bias {
1023 Bias::Left => offset -= 1,
1024 Bias::Right => offset += 1,
1025 }
1026 }
1027 offset
1028 }
1029
1030 impl Rope {
1031 fn text(&self) -> String {
1032 let mut text = String::new();
1033 for chunk in self.chunks.cursor::<()>() {
1034 text.push_str(&chunk.0);
1035 }
1036 text
1037 }
1038 }
1039}