1mod offset_utf16;
2mod point;
3mod point_utf16;
4mod unclipped;
5
6use arrayvec::ArrayString;
7use smallvec::SmallVec;
8use std::{
9 cmp, fmt, io, mem,
10 ops::{AddAssign, Range},
11 str,
12};
13use sum_tree::{Bias, Dimension, SumTree};
14use unicode_segmentation::GraphemeCursor;
15use util::debug_panic;
16
17pub use offset_utf16::OffsetUtf16;
18pub use point::Point;
19pub use point_utf16::PointUtf16;
20pub use unclipped::Unclipped;
21
22#[cfg(test)]
23const CHUNK_BASE: usize = 6;
24
25#[cfg(not(test))]
26const CHUNK_BASE: usize = 64;
27
28#[derive(Clone, Default)]
29pub struct Rope {
30 chunks: SumTree<Chunk>,
31}
32
33impl Rope {
34 pub fn new() -> Self {
35 Self::default()
36 }
37
38 pub fn append(&mut self, rope: Rope) {
39 let mut chunks = rope.chunks.cursor::<()>();
40 chunks.next(&());
41 if let Some(chunk) = chunks.item() {
42 if self.chunks.last().map_or(false, |c| c.0.len() < CHUNK_BASE)
43 || chunk.0.len() < CHUNK_BASE
44 {
45 self.push(&chunk.0);
46 chunks.next(&());
47 }
48 }
49
50 self.chunks.append(chunks.suffix(&()), &());
51 self.check_invariants();
52 }
53
54 pub fn replace(&mut self, range: Range<usize>, text: &str) {
55 let mut new_rope = Rope::new();
56 let mut cursor = self.cursor(0);
57 new_rope.append(cursor.slice(range.start));
58 cursor.seek_forward(range.end);
59 new_rope.push(text);
60 new_rope.append(cursor.suffix());
61 *self = new_rope;
62 }
63
64 pub fn slice(&self, range: Range<usize>) -> Rope {
65 let mut cursor = self.cursor(0);
66 cursor.seek_forward(range.start);
67 cursor.slice(range.end)
68 }
69
70 pub fn slice_rows(&self, range: Range<u32>) -> Rope {
71 // This would be more efficient with a forward advance after the first, but it's fine.
72 let start = self.point_to_offset(Point::new(range.start, 0));
73 let end = self.point_to_offset(Point::new(range.end, 0));
74 self.slice(start..end)
75 }
76
77 pub fn push(&mut self, mut text: &str) {
78 self.chunks.update_last(
79 |last_chunk| {
80 let split_ix = if last_chunk.0.len() + text.len() <= 2 * CHUNK_BASE {
81 text.len()
82 } else {
83 let mut split_ix =
84 cmp::min(CHUNK_BASE.saturating_sub(last_chunk.0.len()), text.len());
85 while !text.is_char_boundary(split_ix) {
86 split_ix += 1;
87 }
88 split_ix
89 };
90
91 let (suffix, remainder) = text.split_at(split_ix);
92 last_chunk.0.push_str(suffix);
93 text = remainder;
94 },
95 &(),
96 );
97
98 if text.len() > 2048 {
99 return self.push_large(text);
100 }
101 let mut new_chunks = SmallVec::<[_; 16]>::new();
102
103 while !text.is_empty() {
104 let mut split_ix = cmp::min(2 * CHUNK_BASE, text.len());
105 while !text.is_char_boundary(split_ix) {
106 split_ix -= 1;
107 }
108 let (chunk, remainder) = text.split_at(split_ix);
109 new_chunks.push(Chunk(ArrayString::from(chunk).unwrap()));
110 text = remainder;
111 }
112
113 #[cfg(test)]
114 const PARALLEL_THRESHOLD: usize = 4;
115 #[cfg(not(test))]
116 const PARALLEL_THRESHOLD: usize = 4 * (2 * sum_tree::TREE_BASE);
117
118 if new_chunks.len() >= PARALLEL_THRESHOLD {
119 self.chunks.par_extend(new_chunks.into_vec(), &());
120 } else {
121 self.chunks.extend(new_chunks, &());
122 }
123
124 self.check_invariants();
125 }
126
127 /// A copy of `push` specialized for working with large quantities of text.
128 fn push_large(&mut self, mut text: &str) {
129 // To avoid frequent reallocs when loading large swaths of file contents,
130 // we estimate worst-case `new_chunks` capacity;
131 // Chunk is a fixed-capacity buffer. If a character falls on
132 // chunk boundary, we push it off to the following chunk (thus leaving a small bit of capacity unfilled in current chunk).
133 // Worst-case chunk count when loading a file is then a case where every chunk ends up with that unused capacity.
134 // Since we're working with UTF-8, each character is at most 4 bytes wide. It follows then that the worst case is where
135 // a chunk ends with 3 bytes of a 4-byte character. These 3 bytes end up being stored in the following chunk, thus wasting
136 // 3 bytes of storage in current chunk.
137 // For example, a 1024-byte string can occupy between 32 (full ASCII, 1024/32) and 36 (full 4-byte UTF-8, 1024 / 29 rounded up) chunks.
138 const MIN_CHUNK_SIZE: usize = 2 * CHUNK_BASE - 3;
139
140 // We also round up the capacity up by one, for a good measure; we *really* don't want to realloc here, as we assume that the # of characters
141 // we're working with there is large.
142 let capacity = (text.len() + MIN_CHUNK_SIZE - 1) / MIN_CHUNK_SIZE;
143 let mut new_chunks = Vec::with_capacity(capacity);
144
145 while !text.is_empty() {
146 let mut split_ix = cmp::min(2 * CHUNK_BASE, text.len());
147 while !text.is_char_boundary(split_ix) {
148 split_ix -= 1;
149 }
150 let (chunk, remainder) = text.split_at(split_ix);
151 new_chunks.push(Chunk(ArrayString::from(chunk).unwrap()));
152 text = remainder;
153 }
154
155 #[cfg(test)]
156 const PARALLEL_THRESHOLD: usize = 4;
157 #[cfg(not(test))]
158 const PARALLEL_THRESHOLD: usize = 4 * (2 * sum_tree::TREE_BASE);
159
160 if new_chunks.len() >= PARALLEL_THRESHOLD {
161 self.chunks.par_extend(new_chunks, &());
162 } else {
163 self.chunks.extend(new_chunks, &());
164 }
165
166 self.check_invariants();
167 }
168 pub fn push_front(&mut self, text: &str) {
169 let suffix = mem::replace(self, Rope::from(text));
170 self.append(suffix);
171 }
172
173 fn check_invariants(&self) {
174 #[cfg(test)]
175 {
176 // Ensure all chunks except maybe the last one are not underflowing.
177 // Allow some wiggle room for multibyte characters at chunk boundaries.
178 let mut chunks = self.chunks.cursor::<()>().peekable();
179 while let Some(chunk) = chunks.next() {
180 if chunks.peek().is_some() {
181 assert!(chunk.0.len() + 3 >= CHUNK_BASE);
182 }
183 }
184 }
185 }
186
187 pub fn summary(&self) -> TextSummary {
188 self.chunks.summary().text.clone()
189 }
190
191 pub fn len(&self) -> usize {
192 self.chunks.extent(&())
193 }
194
195 pub fn is_empty(&self) -> bool {
196 self.len() == 0
197 }
198
199 pub fn max_point(&self) -> Point {
200 self.chunks.extent(&())
201 }
202
203 pub fn max_point_utf16(&self) -> PointUtf16 {
204 self.chunks.extent(&())
205 }
206
207 pub fn cursor(&self, offset: usize) -> Cursor {
208 Cursor::new(self, offset)
209 }
210
211 pub fn chars(&self) -> impl Iterator<Item = char> + '_ {
212 self.chars_at(0)
213 }
214
215 pub fn chars_at(&self, start: usize) -> impl Iterator<Item = char> + '_ {
216 self.chunks_in_range(start..self.len()).flat_map(str::chars)
217 }
218
219 pub fn reversed_chars_at(&self, start: usize) -> impl Iterator<Item = char> + '_ {
220 self.reversed_chunks_in_range(0..start)
221 .flat_map(|chunk| chunk.chars().rev())
222 }
223
224 pub fn bytes_in_range(&self, range: Range<usize>) -> Bytes {
225 Bytes::new(self, range, false)
226 }
227
228 pub fn reversed_bytes_in_range(&self, range: Range<usize>) -> Bytes {
229 Bytes::new(self, range, true)
230 }
231
232 pub fn chunks(&self) -> Chunks {
233 self.chunks_in_range(0..self.len())
234 }
235
236 pub fn chunks_in_range(&self, range: Range<usize>) -> Chunks {
237 Chunks::new(self, range, false)
238 }
239
240 pub fn reversed_chunks_in_range(&self, range: Range<usize>) -> Chunks {
241 Chunks::new(self, range, true)
242 }
243
244 pub fn offset_to_offset_utf16(&self, offset: usize) -> OffsetUtf16 {
245 if offset >= self.summary().len {
246 return self.summary().len_utf16;
247 }
248 let mut cursor = self.chunks.cursor::<(usize, OffsetUtf16)>();
249 cursor.seek(&offset, Bias::Left, &());
250 let overshoot = offset - cursor.start().0;
251 cursor.start().1
252 + cursor.item().map_or(Default::default(), |chunk| {
253 chunk.offset_to_offset_utf16(overshoot)
254 })
255 }
256
257 pub fn offset_utf16_to_offset(&self, offset: OffsetUtf16) -> usize {
258 if offset >= self.summary().len_utf16 {
259 return self.summary().len;
260 }
261 let mut cursor = self.chunks.cursor::<(OffsetUtf16, usize)>();
262 cursor.seek(&offset, Bias::Left, &());
263 let overshoot = offset - cursor.start().0;
264 cursor.start().1
265 + cursor.item().map_or(Default::default(), |chunk| {
266 chunk.offset_utf16_to_offset(overshoot)
267 })
268 }
269
270 pub fn offset_to_point(&self, offset: usize) -> Point {
271 if offset >= self.summary().len {
272 return self.summary().lines;
273 }
274 let mut cursor = self.chunks.cursor::<(usize, Point)>();
275 cursor.seek(&offset, Bias::Left, &());
276 let overshoot = offset - cursor.start().0;
277 cursor.start().1
278 + cursor
279 .item()
280 .map_or(Point::zero(), |chunk| chunk.offset_to_point(overshoot))
281 }
282
283 pub fn offset_to_point_utf16(&self, offset: usize) -> PointUtf16 {
284 if offset >= self.summary().len {
285 return self.summary().lines_utf16();
286 }
287 let mut cursor = self.chunks.cursor::<(usize, PointUtf16)>();
288 cursor.seek(&offset, Bias::Left, &());
289 let overshoot = offset - cursor.start().0;
290 cursor.start().1
291 + cursor.item().map_or(PointUtf16::zero(), |chunk| {
292 chunk.offset_to_point_utf16(overshoot)
293 })
294 }
295
296 pub fn point_to_point_utf16(&self, point: Point) -> PointUtf16 {
297 if point >= self.summary().lines {
298 return self.summary().lines_utf16();
299 }
300 let mut cursor = self.chunks.cursor::<(Point, PointUtf16)>();
301 cursor.seek(&point, Bias::Left, &());
302 let overshoot = point - cursor.start().0;
303 cursor.start().1
304 + cursor.item().map_or(PointUtf16::zero(), |chunk| {
305 chunk.point_to_point_utf16(overshoot)
306 })
307 }
308
309 pub fn point_to_offset(&self, point: Point) -> usize {
310 if point >= self.summary().lines {
311 return self.summary().len;
312 }
313 let mut cursor = self.chunks.cursor::<(Point, usize)>();
314 cursor.seek(&point, Bias::Left, &());
315 let overshoot = point - cursor.start().0;
316 cursor.start().1
317 + cursor
318 .item()
319 .map_or(0, |chunk| chunk.point_to_offset(overshoot))
320 }
321
322 pub fn point_utf16_to_offset(&self, point: PointUtf16) -> usize {
323 self.point_utf16_to_offset_impl(point, false)
324 }
325
326 pub fn unclipped_point_utf16_to_offset(&self, point: Unclipped<PointUtf16>) -> usize {
327 self.point_utf16_to_offset_impl(point.0, true)
328 }
329
330 fn point_utf16_to_offset_impl(&self, point: PointUtf16, clip: bool) -> usize {
331 if point >= self.summary().lines_utf16() {
332 return self.summary().len;
333 }
334 let mut cursor = self.chunks.cursor::<(PointUtf16, usize)>();
335 cursor.seek(&point, Bias::Left, &());
336 let overshoot = point - cursor.start().0;
337 cursor.start().1
338 + cursor
339 .item()
340 .map_or(0, |chunk| chunk.point_utf16_to_offset(overshoot, clip))
341 }
342
343 pub fn unclipped_point_utf16_to_point(&self, point: Unclipped<PointUtf16>) -> Point {
344 if point.0 >= self.summary().lines_utf16() {
345 return self.summary().lines;
346 }
347 let mut cursor = self.chunks.cursor::<(PointUtf16, Point)>();
348 cursor.seek(&point.0, Bias::Left, &());
349 let overshoot = Unclipped(point.0 - cursor.start().0);
350 cursor.start().1
351 + cursor.item().map_or(Point::zero(), |chunk| {
352 chunk.unclipped_point_utf16_to_point(overshoot)
353 })
354 }
355
356 pub fn clip_offset(&self, mut offset: usize, bias: Bias) -> usize {
357 let mut cursor = self.chunks.cursor::<usize>();
358 cursor.seek(&offset, Bias::Left, &());
359 if let Some(chunk) = cursor.item() {
360 let mut ix = offset - cursor.start();
361 while !chunk.0.is_char_boundary(ix) {
362 match bias {
363 Bias::Left => {
364 ix -= 1;
365 offset -= 1;
366 }
367 Bias::Right => {
368 ix += 1;
369 offset += 1;
370 }
371 }
372 }
373 offset
374 } else {
375 self.summary().len
376 }
377 }
378
379 pub fn clip_offset_utf16(&self, offset: OffsetUtf16, bias: Bias) -> OffsetUtf16 {
380 let mut cursor = self.chunks.cursor::<OffsetUtf16>();
381 cursor.seek(&offset, Bias::Right, &());
382 if let Some(chunk) = cursor.item() {
383 let overshoot = offset - cursor.start();
384 *cursor.start() + chunk.clip_offset_utf16(overshoot, bias)
385 } else {
386 self.summary().len_utf16
387 }
388 }
389
390 pub fn clip_point(&self, point: Point, bias: Bias) -> Point {
391 let mut cursor = self.chunks.cursor::<Point>();
392 cursor.seek(&point, Bias::Right, &());
393 if let Some(chunk) = cursor.item() {
394 let overshoot = point - cursor.start();
395 *cursor.start() + chunk.clip_point(overshoot, bias)
396 } else {
397 self.summary().lines
398 }
399 }
400
401 pub fn clip_point_utf16(&self, point: Unclipped<PointUtf16>, bias: Bias) -> PointUtf16 {
402 let mut cursor = self.chunks.cursor::<PointUtf16>();
403 cursor.seek(&point.0, Bias::Right, &());
404 if let Some(chunk) = cursor.item() {
405 let overshoot = Unclipped(point.0 - cursor.start());
406 *cursor.start() + chunk.clip_point_utf16(overshoot, bias)
407 } else {
408 self.summary().lines_utf16()
409 }
410 }
411
412 pub fn line_len(&self, row: u32) -> u32 {
413 self.clip_point(Point::new(row, u32::MAX), Bias::Left)
414 .column
415 }
416}
417
418impl<'a> From<&'a str> for Rope {
419 fn from(text: &'a str) -> Self {
420 let mut rope = Self::new();
421 rope.push(text);
422 rope
423 }
424}
425
426impl<'a> FromIterator<&'a str> for Rope {
427 fn from_iter<T: IntoIterator<Item = &'a str>>(iter: T) -> Self {
428 let mut rope = Rope::new();
429 for chunk in iter {
430 rope.push(chunk);
431 }
432 rope
433 }
434}
435
436impl From<String> for Rope {
437 fn from(text: String) -> Self {
438 Rope::from(text.as_str())
439 }
440}
441
442impl fmt::Display for Rope {
443 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
444 for chunk in self.chunks() {
445 write!(f, "{}", chunk)?;
446 }
447 Ok(())
448 }
449}
450
451impl fmt::Debug for Rope {
452 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
453 use std::fmt::Write as _;
454
455 write!(f, "\"")?;
456 let mut format_string = String::new();
457 for chunk in self.chunks() {
458 write!(&mut format_string, "{:?}", chunk)?;
459 write!(f, "{}", &format_string[1..format_string.len() - 1])?;
460 format_string.clear();
461 }
462 write!(f, "\"")?;
463 Ok(())
464 }
465}
466
467pub struct Cursor<'a> {
468 rope: &'a Rope,
469 chunks: sum_tree::Cursor<'a, Chunk, usize>,
470 offset: usize,
471}
472
473impl<'a> Cursor<'a> {
474 pub fn new(rope: &'a Rope, offset: usize) -> Self {
475 let mut chunks = rope.chunks.cursor();
476 chunks.seek(&offset, Bias::Right, &());
477 Self {
478 rope,
479 chunks,
480 offset,
481 }
482 }
483
484 pub fn seek_forward(&mut self, end_offset: usize) {
485 debug_assert!(end_offset >= self.offset);
486
487 self.chunks.seek_forward(&end_offset, Bias::Right, &());
488 self.offset = end_offset;
489 }
490
491 pub fn slice(&mut self, end_offset: usize) -> Rope {
492 debug_assert!(
493 end_offset >= self.offset,
494 "cannot slice backwards from {} to {}",
495 self.offset,
496 end_offset
497 );
498
499 let mut slice = Rope::new();
500 if let Some(start_chunk) = self.chunks.item() {
501 let start_ix = self.offset - self.chunks.start();
502 let end_ix = cmp::min(end_offset, self.chunks.end(&())) - self.chunks.start();
503 slice.push(&start_chunk.0[start_ix..end_ix]);
504 }
505
506 if end_offset > self.chunks.end(&()) {
507 self.chunks.next(&());
508 slice.append(Rope {
509 chunks: self.chunks.slice(&end_offset, Bias::Right, &()),
510 });
511 if let Some(end_chunk) = self.chunks.item() {
512 let end_ix = end_offset - self.chunks.start();
513 slice.push(&end_chunk.0[..end_ix]);
514 }
515 }
516
517 self.offset = end_offset;
518 slice
519 }
520
521 pub fn summary<D: TextDimension>(&mut self, end_offset: usize) -> D {
522 debug_assert!(end_offset >= self.offset);
523
524 let mut summary = D::default();
525 if let Some(start_chunk) = self.chunks.item() {
526 let start_ix = self.offset - self.chunks.start();
527 let end_ix = cmp::min(end_offset, self.chunks.end(&())) - self.chunks.start();
528 summary.add_assign(&D::from_text_summary(&TextSummary::from(
529 &start_chunk.0[start_ix..end_ix],
530 )));
531 }
532
533 if end_offset > self.chunks.end(&()) {
534 self.chunks.next(&());
535 summary.add_assign(&self.chunks.summary(&end_offset, Bias::Right, &()));
536 if let Some(end_chunk) = self.chunks.item() {
537 let end_ix = end_offset - self.chunks.start();
538 summary.add_assign(&D::from_text_summary(&TextSummary::from(
539 &end_chunk.0[..end_ix],
540 )));
541 }
542 }
543
544 self.offset = end_offset;
545 summary
546 }
547
548 pub fn suffix(mut self) -> Rope {
549 self.slice(self.rope.chunks.extent(&()))
550 }
551
552 pub fn offset(&self) -> usize {
553 self.offset
554 }
555}
556
557pub struct Chunks<'a> {
558 chunks: sum_tree::Cursor<'a, Chunk, usize>,
559 range: Range<usize>,
560 reversed: bool,
561}
562
563impl<'a> Chunks<'a> {
564 pub fn new(rope: &'a Rope, range: Range<usize>, reversed: bool) -> Self {
565 let mut chunks = rope.chunks.cursor();
566 if reversed {
567 chunks.seek(&range.end, Bias::Left, &());
568 } else {
569 chunks.seek(&range.start, Bias::Right, &());
570 }
571 Self {
572 chunks,
573 range,
574 reversed,
575 }
576 }
577
578 pub fn offset(&self) -> usize {
579 if self.reversed {
580 self.range.end.min(self.chunks.end(&()))
581 } else {
582 self.range.start.max(*self.chunks.start())
583 }
584 }
585
586 pub fn seek(&mut self, offset: usize) {
587 let bias = if self.reversed {
588 Bias::Left
589 } else {
590 Bias::Right
591 };
592
593 if offset >= self.chunks.end(&()) {
594 self.chunks.seek_forward(&offset, bias, &());
595 } else {
596 self.chunks.seek(&offset, bias, &());
597 }
598
599 if self.reversed {
600 self.range.end = offset;
601 } else {
602 self.range.start = offset;
603 }
604 }
605
606 pub fn peek(&self) -> Option<&'a str> {
607 let chunk = self.chunks.item()?;
608 if self.reversed && self.range.start >= self.chunks.end(&()) {
609 return None;
610 }
611 let chunk_start = *self.chunks.start();
612 if self.range.end <= chunk_start {
613 return None;
614 }
615
616 let start = self.range.start.saturating_sub(chunk_start);
617 let end = self.range.end - chunk_start;
618 Some(&chunk.0[start..chunk.0.len().min(end)])
619 }
620
621 pub fn lines(self) -> Lines<'a> {
622 let reversed = self.reversed;
623 Lines {
624 chunks: self,
625 current_line: String::new(),
626 done: false,
627 reversed,
628 }
629 }
630}
631
632impl<'a> Iterator for Chunks<'a> {
633 type Item = &'a str;
634
635 fn next(&mut self) -> Option<Self::Item> {
636 let result = self.peek();
637 if result.is_some() {
638 if self.reversed {
639 self.chunks.prev(&());
640 } else {
641 self.chunks.next(&());
642 }
643 }
644 result
645 }
646}
647
648pub struct Bytes<'a> {
649 chunks: sum_tree::Cursor<'a, Chunk, usize>,
650 range: Range<usize>,
651 reversed: bool,
652}
653
654impl<'a> Bytes<'a> {
655 pub fn new(rope: &'a Rope, range: Range<usize>, reversed: bool) -> Self {
656 let mut chunks = rope.chunks.cursor();
657 if reversed {
658 chunks.seek(&range.end, Bias::Left, &());
659 } else {
660 chunks.seek(&range.start, Bias::Right, &());
661 }
662 Self {
663 chunks,
664 range,
665 reversed,
666 }
667 }
668
669 pub fn peek(&self) -> Option<&'a [u8]> {
670 let chunk = self.chunks.item()?;
671 if self.reversed && self.range.start >= self.chunks.end(&()) {
672 return None;
673 }
674 let chunk_start = *self.chunks.start();
675 if self.range.end <= chunk_start {
676 return None;
677 }
678 let start = self.range.start.saturating_sub(chunk_start);
679 let end = self.range.end - chunk_start;
680 Some(&chunk.0.as_bytes()[start..chunk.0.len().min(end)])
681 }
682}
683
684impl<'a> Iterator for Bytes<'a> {
685 type Item = &'a [u8];
686
687 fn next(&mut self) -> Option<Self::Item> {
688 let result = self.peek();
689 if result.is_some() {
690 if self.reversed {
691 self.chunks.prev(&());
692 } else {
693 self.chunks.next(&());
694 }
695 }
696 result
697 }
698}
699
700impl<'a> io::Read for Bytes<'a> {
701 fn read(&mut self, buf: &mut [u8]) -> io::Result<usize> {
702 if let Some(chunk) = self.peek() {
703 let len = cmp::min(buf.len(), chunk.len());
704 if self.reversed {
705 buf[..len].copy_from_slice(&chunk[chunk.len() - len..]);
706 buf[..len].reverse();
707 self.range.end -= len;
708 } else {
709 buf[..len].copy_from_slice(&chunk[..len]);
710 self.range.start += len;
711 }
712
713 if len == chunk.len() {
714 if self.reversed {
715 self.chunks.prev(&());
716 } else {
717 self.chunks.next(&());
718 }
719 }
720 Ok(len)
721 } else {
722 Ok(0)
723 }
724 }
725}
726
727pub struct Lines<'a> {
728 chunks: Chunks<'a>,
729 current_line: String,
730 done: bool,
731 reversed: bool,
732}
733
734impl<'a> Lines<'a> {
735 pub fn next(&mut self) -> Option<&str> {
736 if self.done {
737 return None;
738 }
739
740 self.current_line.clear();
741
742 while let Some(chunk) = self.chunks.peek() {
743 let lines = chunk.split('\n');
744 if self.reversed {
745 let mut lines = lines.rev().peekable();
746 while let Some(line) = lines.next() {
747 self.current_line.insert_str(0, line);
748 if lines.peek().is_some() {
749 self.chunks
750 .seek(self.chunks.offset() - line.len() - "\n".len());
751 return Some(&self.current_line);
752 }
753 }
754 } else {
755 let mut lines = lines.peekable();
756 while let Some(line) = lines.next() {
757 self.current_line.push_str(line);
758 if lines.peek().is_some() {
759 self.chunks
760 .seek(self.chunks.offset() + line.len() + "\n".len());
761 return Some(&self.current_line);
762 }
763 }
764 }
765
766 self.chunks.next();
767 }
768
769 self.done = true;
770 Some(&self.current_line)
771 }
772
773 pub fn seek(&mut self, offset: usize) {
774 self.chunks.seek(offset);
775 self.current_line.clear();
776 self.done = false;
777 }
778
779 pub fn offset(&self) -> usize {
780 self.chunks.offset()
781 }
782}
783
784#[derive(Clone, Debug, Default)]
785struct Chunk(ArrayString<{ 2 * CHUNK_BASE }>);
786
787impl Chunk {
788 fn offset_to_offset_utf16(&self, target: usize) -> OffsetUtf16 {
789 let mut offset = 0;
790 let mut offset_utf16 = OffsetUtf16(0);
791 for ch in self.0.chars() {
792 if offset >= target {
793 break;
794 }
795
796 offset += ch.len_utf8();
797 offset_utf16.0 += ch.len_utf16();
798 }
799 offset_utf16
800 }
801
802 fn offset_utf16_to_offset(&self, target: OffsetUtf16) -> usize {
803 let mut offset_utf16 = OffsetUtf16(0);
804 let mut offset = 0;
805 for ch in self.0.chars() {
806 if offset_utf16 >= target {
807 break;
808 }
809
810 offset += ch.len_utf8();
811 offset_utf16.0 += ch.len_utf16();
812 }
813 offset
814 }
815
816 fn offset_to_point(&self, target: usize) -> Point {
817 let mut offset = 0;
818 let mut point = Point::new(0, 0);
819 for ch in self.0.chars() {
820 if offset >= target {
821 break;
822 }
823
824 if ch == '\n' {
825 point.row += 1;
826 point.column = 0;
827 } else {
828 point.column += ch.len_utf8() as u32;
829 }
830 offset += ch.len_utf8();
831 }
832 point
833 }
834
835 fn offset_to_point_utf16(&self, target: usize) -> PointUtf16 {
836 let mut offset = 0;
837 let mut point = PointUtf16::new(0, 0);
838 for ch in self.0.chars() {
839 if offset >= target {
840 break;
841 }
842
843 if ch == '\n' {
844 point.row += 1;
845 point.column = 0;
846 } else {
847 point.column += ch.len_utf16() as u32;
848 }
849 offset += ch.len_utf8();
850 }
851 point
852 }
853
854 fn point_to_offset(&self, target: Point) -> usize {
855 let mut offset = 0;
856 let mut point = Point::new(0, 0);
857
858 for ch in self.0.chars() {
859 if point >= target {
860 if point > target {
861 debug_panic!("point {target:?} is inside of character {ch:?}");
862 }
863 break;
864 }
865
866 if ch == '\n' {
867 point.row += 1;
868 point.column = 0;
869
870 if point.row > target.row {
871 debug_panic!(
872 "point {target:?} is beyond the end of a line with length {}",
873 point.column
874 );
875 break;
876 }
877 } else {
878 point.column += ch.len_utf8() as u32;
879 }
880
881 offset += ch.len_utf8();
882 }
883
884 offset
885 }
886
887 fn point_to_point_utf16(&self, target: Point) -> PointUtf16 {
888 let mut point = Point::zero();
889 let mut point_utf16 = PointUtf16::new(0, 0);
890 for ch in self.0.chars() {
891 if point >= target {
892 break;
893 }
894
895 if ch == '\n' {
896 point_utf16.row += 1;
897 point_utf16.column = 0;
898 point.row += 1;
899 point.column = 0;
900 } else {
901 point_utf16.column += ch.len_utf16() as u32;
902 point.column += ch.len_utf8() as u32;
903 }
904 }
905 point_utf16
906 }
907
908 fn point_utf16_to_offset(&self, target: PointUtf16, clip: bool) -> usize {
909 let mut offset = 0;
910 let mut point = PointUtf16::new(0, 0);
911
912 for ch in self.0.chars() {
913 if point == target {
914 break;
915 }
916
917 if ch == '\n' {
918 point.row += 1;
919 point.column = 0;
920
921 if point.row > target.row {
922 if !clip {
923 debug_panic!(
924 "point {target:?} is beyond the end of a line with length {}",
925 point.column
926 );
927 }
928 // Return the offset of the newline
929 return offset;
930 }
931 } else {
932 point.column += ch.len_utf16() as u32;
933 }
934
935 if point > target {
936 if !clip {
937 debug_panic!("point {target:?} is inside of codepoint {ch:?}");
938 }
939 // Return the offset of the codepoint which we have landed within, bias left
940 return offset;
941 }
942
943 offset += ch.len_utf8();
944 }
945
946 offset
947 }
948
949 fn unclipped_point_utf16_to_point(&self, target: Unclipped<PointUtf16>) -> Point {
950 let mut point = Point::zero();
951 let mut point_utf16 = PointUtf16::zero();
952
953 for ch in self.0.chars() {
954 if point_utf16 == target.0 {
955 break;
956 }
957
958 if point_utf16 > target.0 {
959 // If the point is past the end of a line or inside of a code point,
960 // return the last valid point before the target.
961 return point;
962 }
963
964 if ch == '\n' {
965 point_utf16 += PointUtf16::new(1, 0);
966 point += Point::new(1, 0);
967 } else {
968 point_utf16 += PointUtf16::new(0, ch.len_utf16() as u32);
969 point += Point::new(0, ch.len_utf8() as u32);
970 }
971 }
972
973 point
974 }
975
976 fn clip_point(&self, target: Point, bias: Bias) -> Point {
977 for (row, line) in self.0.split('\n').enumerate() {
978 if row == target.row as usize {
979 let bytes = line.as_bytes();
980 let mut column = target.column.min(bytes.len() as u32) as usize;
981 if column == 0
982 || column == bytes.len()
983 || (bytes[column - 1] < 128 && bytes[column] < 128)
984 {
985 return Point::new(row as u32, column as u32);
986 }
987
988 let mut grapheme_cursor = GraphemeCursor::new(column, bytes.len(), true);
989 loop {
990 if line.is_char_boundary(column) {
991 if grapheme_cursor.is_boundary(line, 0).unwrap_or(false) {
992 break;
993 }
994 }
995
996 match bias {
997 Bias::Left => column -= 1,
998 Bias::Right => column += 1,
999 }
1000 grapheme_cursor.set_cursor(column);
1001 }
1002 return Point::new(row as u32, column as u32);
1003 }
1004 }
1005 unreachable!()
1006 }
1007
1008 fn clip_point_utf16(&self, target: Unclipped<PointUtf16>, bias: Bias) -> PointUtf16 {
1009 for (row, line) in self.0.split('\n').enumerate() {
1010 if row == target.0.row as usize {
1011 let mut code_units = line.encode_utf16();
1012 let mut column = code_units.by_ref().take(target.0.column as usize).count();
1013 if char::decode_utf16(code_units).next().transpose().is_err() {
1014 match bias {
1015 Bias::Left => column -= 1,
1016 Bias::Right => column += 1,
1017 }
1018 }
1019 return PointUtf16::new(row as u32, column as u32);
1020 }
1021 }
1022 unreachable!()
1023 }
1024
1025 fn clip_offset_utf16(&self, target: OffsetUtf16, bias: Bias) -> OffsetUtf16 {
1026 let mut code_units = self.0.encode_utf16();
1027 let mut offset = code_units.by_ref().take(target.0).count();
1028 if char::decode_utf16(code_units).next().transpose().is_err() {
1029 match bias {
1030 Bias::Left => offset -= 1,
1031 Bias::Right => offset += 1,
1032 }
1033 }
1034 OffsetUtf16(offset)
1035 }
1036}
1037
1038impl sum_tree::Item for Chunk {
1039 type Summary = ChunkSummary;
1040
1041 fn summary(&self) -> Self::Summary {
1042 ChunkSummary::from(self.0.as_str())
1043 }
1044}
1045
1046#[derive(Clone, Debug, Default, Eq, PartialEq)]
1047pub struct ChunkSummary {
1048 text: TextSummary,
1049}
1050
1051impl<'a> From<&'a str> for ChunkSummary {
1052 fn from(text: &'a str) -> Self {
1053 Self {
1054 text: TextSummary::from(text),
1055 }
1056 }
1057}
1058
1059impl sum_tree::Summary for ChunkSummary {
1060 type Context = ();
1061
1062 fn add_summary(&mut self, summary: &Self, _: &()) {
1063 self.text += &summary.text;
1064 }
1065}
1066
1067/// Summary of a string of text.
1068#[derive(Clone, Debug, Default, Eq, PartialEq)]
1069pub struct TextSummary {
1070 /// Length in UTF-8
1071 pub len: usize,
1072 /// Length in UTF-16 code units
1073 pub len_utf16: OffsetUtf16,
1074 /// A point representing the number of lines and the length of the last line
1075 pub lines: Point,
1076 /// How many `char`s are in the first line
1077 pub first_line_chars: u32,
1078 /// How many `char`s are in the last line
1079 pub last_line_chars: u32,
1080 /// How many UTF-16 code units are in the last line
1081 pub last_line_len_utf16: u32,
1082 /// The row idx of the longest row
1083 pub longest_row: u32,
1084 /// How many `char`s are in the longest row
1085 pub longest_row_chars: u32,
1086}
1087
1088impl TextSummary {
1089 pub fn lines_utf16(&self) -> PointUtf16 {
1090 PointUtf16 {
1091 row: self.lines.row,
1092 column: self.last_line_len_utf16,
1093 }
1094 }
1095}
1096
1097impl<'a> From<&'a str> for TextSummary {
1098 fn from(text: &'a str) -> Self {
1099 let mut len_utf16 = OffsetUtf16(0);
1100 let mut lines = Point::new(0, 0);
1101 let mut first_line_chars = 0;
1102 let mut last_line_chars = 0;
1103 let mut last_line_len_utf16 = 0;
1104 let mut longest_row = 0;
1105 let mut longest_row_chars = 0;
1106 for c in text.chars() {
1107 len_utf16.0 += c.len_utf16();
1108
1109 if c == '\n' {
1110 lines += Point::new(1, 0);
1111 last_line_len_utf16 = 0;
1112 last_line_chars = 0;
1113 } else {
1114 lines.column += c.len_utf8() as u32;
1115 last_line_len_utf16 += c.len_utf16() as u32;
1116 last_line_chars += 1;
1117 }
1118
1119 if lines.row == 0 {
1120 first_line_chars = last_line_chars;
1121 }
1122
1123 if last_line_chars > longest_row_chars {
1124 longest_row = lines.row;
1125 longest_row_chars = last_line_chars;
1126 }
1127 }
1128
1129 TextSummary {
1130 len: text.len(),
1131 len_utf16,
1132 lines,
1133 first_line_chars,
1134 last_line_chars,
1135 last_line_len_utf16,
1136 longest_row,
1137 longest_row_chars,
1138 }
1139 }
1140}
1141
1142impl sum_tree::Summary for TextSummary {
1143 type Context = ();
1144
1145 fn add_summary(&mut self, summary: &Self, _: &Self::Context) {
1146 *self += summary;
1147 }
1148}
1149
1150impl std::ops::Add<Self> for TextSummary {
1151 type Output = Self;
1152
1153 fn add(mut self, rhs: Self) -> Self::Output {
1154 AddAssign::add_assign(&mut self, &rhs);
1155 self
1156 }
1157}
1158
1159impl<'a> std::ops::AddAssign<&'a Self> for TextSummary {
1160 fn add_assign(&mut self, other: &'a Self) {
1161 let joined_chars = self.last_line_chars + other.first_line_chars;
1162 if joined_chars > self.longest_row_chars {
1163 self.longest_row = self.lines.row;
1164 self.longest_row_chars = joined_chars;
1165 }
1166 if other.longest_row_chars > self.longest_row_chars {
1167 self.longest_row = self.lines.row + other.longest_row;
1168 self.longest_row_chars = other.longest_row_chars;
1169 }
1170
1171 if self.lines.row == 0 {
1172 self.first_line_chars += other.first_line_chars;
1173 }
1174
1175 if other.lines.row == 0 {
1176 self.last_line_chars += other.first_line_chars;
1177 self.last_line_len_utf16 += other.last_line_len_utf16;
1178 } else {
1179 self.last_line_chars = other.last_line_chars;
1180 self.last_line_len_utf16 = other.last_line_len_utf16;
1181 }
1182
1183 self.len += other.len;
1184 self.len_utf16 += other.len_utf16;
1185 self.lines += other.lines;
1186 }
1187}
1188
1189impl std::ops::AddAssign<Self> for TextSummary {
1190 fn add_assign(&mut self, other: Self) {
1191 *self += &other;
1192 }
1193}
1194
1195pub trait TextDimension: 'static + for<'a> Dimension<'a, ChunkSummary> {
1196 fn from_text_summary(summary: &TextSummary) -> Self;
1197 fn add_assign(&mut self, other: &Self);
1198}
1199
1200impl<D1: TextDimension, D2: TextDimension> TextDimension for (D1, D2) {
1201 fn from_text_summary(summary: &TextSummary) -> Self {
1202 (
1203 D1::from_text_summary(summary),
1204 D2::from_text_summary(summary),
1205 )
1206 }
1207
1208 fn add_assign(&mut self, other: &Self) {
1209 self.0.add_assign(&other.0);
1210 self.1.add_assign(&other.1);
1211 }
1212}
1213
1214impl<'a> sum_tree::Dimension<'a, ChunkSummary> for TextSummary {
1215 fn add_summary(&mut self, summary: &'a ChunkSummary, _: &()) {
1216 *self += &summary.text;
1217 }
1218}
1219
1220impl TextDimension for TextSummary {
1221 fn from_text_summary(summary: &TextSummary) -> Self {
1222 summary.clone()
1223 }
1224
1225 fn add_assign(&mut self, other: &Self) {
1226 *self += other;
1227 }
1228}
1229
1230impl<'a> sum_tree::Dimension<'a, ChunkSummary> for usize {
1231 fn add_summary(&mut self, summary: &'a ChunkSummary, _: &()) {
1232 *self += summary.text.len;
1233 }
1234}
1235
1236impl TextDimension for usize {
1237 fn from_text_summary(summary: &TextSummary) -> Self {
1238 summary.len
1239 }
1240
1241 fn add_assign(&mut self, other: &Self) {
1242 *self += other;
1243 }
1244}
1245
1246impl<'a> sum_tree::Dimension<'a, ChunkSummary> for OffsetUtf16 {
1247 fn add_summary(&mut self, summary: &'a ChunkSummary, _: &()) {
1248 *self += summary.text.len_utf16;
1249 }
1250}
1251
1252impl TextDimension for OffsetUtf16 {
1253 fn from_text_summary(summary: &TextSummary) -> Self {
1254 summary.len_utf16
1255 }
1256
1257 fn add_assign(&mut self, other: &Self) {
1258 *self += other;
1259 }
1260}
1261
1262impl<'a> sum_tree::Dimension<'a, ChunkSummary> for Point {
1263 fn add_summary(&mut self, summary: &'a ChunkSummary, _: &()) {
1264 *self += summary.text.lines;
1265 }
1266}
1267
1268impl TextDimension for Point {
1269 fn from_text_summary(summary: &TextSummary) -> Self {
1270 summary.lines
1271 }
1272
1273 fn add_assign(&mut self, other: &Self) {
1274 *self += other;
1275 }
1276}
1277
1278impl<'a> sum_tree::Dimension<'a, ChunkSummary> for PointUtf16 {
1279 fn add_summary(&mut self, summary: &'a ChunkSummary, _: &()) {
1280 *self += summary.text.lines_utf16();
1281 }
1282}
1283
1284impl TextDimension for PointUtf16 {
1285 fn from_text_summary(summary: &TextSummary) -> Self {
1286 summary.lines_utf16()
1287 }
1288
1289 fn add_assign(&mut self, other: &Self) {
1290 *self += other;
1291 }
1292}
1293
1294#[cfg(test)]
1295mod tests {
1296 use super::*;
1297 use rand::prelude::*;
1298 use std::{cmp::Ordering, env, io::Read};
1299 use util::RandomCharIter;
1300 use Bias::{Left, Right};
1301
1302 #[test]
1303 fn test_all_4_byte_chars() {
1304 let mut rope = Rope::new();
1305 let text = "🏀".repeat(256);
1306 rope.push(&text);
1307 assert_eq!(rope.text(), text);
1308 }
1309
1310 #[test]
1311 fn test_clip() {
1312 let rope = Rope::from("🧘");
1313
1314 assert_eq!(rope.clip_offset(1, Bias::Left), 0);
1315 assert_eq!(rope.clip_offset(1, Bias::Right), 4);
1316 assert_eq!(rope.clip_offset(5, Bias::Right), 4);
1317
1318 assert_eq!(
1319 rope.clip_point(Point::new(0, 1), Bias::Left),
1320 Point::new(0, 0)
1321 );
1322 assert_eq!(
1323 rope.clip_point(Point::new(0, 1), Bias::Right),
1324 Point::new(0, 4)
1325 );
1326 assert_eq!(
1327 rope.clip_point(Point::new(0, 5), Bias::Right),
1328 Point::new(0, 4)
1329 );
1330
1331 assert_eq!(
1332 rope.clip_point_utf16(Unclipped(PointUtf16::new(0, 1)), Bias::Left),
1333 PointUtf16::new(0, 0)
1334 );
1335 assert_eq!(
1336 rope.clip_point_utf16(Unclipped(PointUtf16::new(0, 1)), Bias::Right),
1337 PointUtf16::new(0, 2)
1338 );
1339 assert_eq!(
1340 rope.clip_point_utf16(Unclipped(PointUtf16::new(0, 3)), Bias::Right),
1341 PointUtf16::new(0, 2)
1342 );
1343
1344 assert_eq!(
1345 rope.clip_offset_utf16(OffsetUtf16(1), Bias::Left),
1346 OffsetUtf16(0)
1347 );
1348 assert_eq!(
1349 rope.clip_offset_utf16(OffsetUtf16(1), Bias::Right),
1350 OffsetUtf16(2)
1351 );
1352 assert_eq!(
1353 rope.clip_offset_utf16(OffsetUtf16(3), Bias::Right),
1354 OffsetUtf16(2)
1355 );
1356 }
1357
1358 #[test]
1359 fn test_lines() {
1360 let rope = Rope::from("abc\ndefg\nhi");
1361 let mut lines = rope.chunks().lines();
1362 assert_eq!(lines.next(), Some("abc"));
1363 assert_eq!(lines.next(), Some("defg"));
1364 assert_eq!(lines.next(), Some("hi"));
1365 assert_eq!(lines.next(), None);
1366
1367 let rope = Rope::from("abc\ndefg\nhi\n");
1368 let mut lines = rope.chunks().lines();
1369 assert_eq!(lines.next(), Some("abc"));
1370 assert_eq!(lines.next(), Some("defg"));
1371 assert_eq!(lines.next(), Some("hi"));
1372 assert_eq!(lines.next(), Some(""));
1373 assert_eq!(lines.next(), None);
1374
1375 let rope = Rope::from("abc\ndefg\nhi");
1376 let mut lines = rope.reversed_chunks_in_range(0..rope.len()).lines();
1377 assert_eq!(lines.next(), Some("hi"));
1378 assert_eq!(lines.next(), Some("defg"));
1379 assert_eq!(lines.next(), Some("abc"));
1380 assert_eq!(lines.next(), None);
1381
1382 let rope = Rope::from("abc\ndefg\nhi\n");
1383 let mut lines = rope.reversed_chunks_in_range(0..rope.len()).lines();
1384 assert_eq!(lines.next(), Some(""));
1385 assert_eq!(lines.next(), Some("hi"));
1386 assert_eq!(lines.next(), Some("defg"));
1387 assert_eq!(lines.next(), Some("abc"));
1388 assert_eq!(lines.next(), None);
1389 }
1390
1391 #[gpui::test(iterations = 100)]
1392 fn test_random_rope(mut rng: StdRng) {
1393 let operations = env::var("OPERATIONS")
1394 .map(|i| i.parse().expect("invalid `OPERATIONS` variable"))
1395 .unwrap_or(10);
1396
1397 let mut expected = String::new();
1398 let mut actual = Rope::new();
1399 for _ in 0..operations {
1400 let end_ix = clip_offset(&expected, rng.gen_range(0..=expected.len()), Right);
1401 let start_ix = clip_offset(&expected, rng.gen_range(0..=end_ix), Left);
1402 let len = rng.gen_range(0..=64);
1403 let new_text: String = RandomCharIter::new(&mut rng).take(len).collect();
1404
1405 let mut new_actual = Rope::new();
1406 let mut cursor = actual.cursor(0);
1407 new_actual.append(cursor.slice(start_ix));
1408 new_actual.push(&new_text);
1409 cursor.seek_forward(end_ix);
1410 new_actual.append(cursor.suffix());
1411 actual = new_actual;
1412
1413 expected.replace_range(start_ix..end_ix, &new_text);
1414
1415 assert_eq!(actual.text(), expected);
1416 log::info!("text: {:?}", expected);
1417
1418 for _ in 0..5 {
1419 let end_ix = clip_offset(&expected, rng.gen_range(0..=expected.len()), Right);
1420 let start_ix = clip_offset(&expected, rng.gen_range(0..=end_ix), Left);
1421
1422 let actual_text = actual.chunks_in_range(start_ix..end_ix).collect::<String>();
1423 assert_eq!(actual_text, &expected[start_ix..end_ix]);
1424
1425 let mut actual_text = String::new();
1426 actual
1427 .bytes_in_range(start_ix..end_ix)
1428 .read_to_string(&mut actual_text)
1429 .unwrap();
1430 assert_eq!(actual_text, &expected[start_ix..end_ix]);
1431
1432 assert_eq!(
1433 actual
1434 .reversed_chunks_in_range(start_ix..end_ix)
1435 .collect::<Vec<&str>>()
1436 .into_iter()
1437 .rev()
1438 .collect::<String>(),
1439 &expected[start_ix..end_ix]
1440 );
1441 }
1442
1443 let mut offset_utf16 = OffsetUtf16(0);
1444 let mut point = Point::new(0, 0);
1445 let mut point_utf16 = PointUtf16::new(0, 0);
1446 for (ix, ch) in expected.char_indices().chain(Some((expected.len(), '\0'))) {
1447 assert_eq!(actual.offset_to_point(ix), point, "offset_to_point({})", ix);
1448 assert_eq!(
1449 actual.offset_to_point_utf16(ix),
1450 point_utf16,
1451 "offset_to_point_utf16({})",
1452 ix
1453 );
1454 assert_eq!(
1455 actual.point_to_offset(point),
1456 ix,
1457 "point_to_offset({:?})",
1458 point
1459 );
1460 assert_eq!(
1461 actual.point_utf16_to_offset(point_utf16),
1462 ix,
1463 "point_utf16_to_offset({:?})",
1464 point_utf16
1465 );
1466 assert_eq!(
1467 actual.offset_to_offset_utf16(ix),
1468 offset_utf16,
1469 "offset_to_offset_utf16({:?})",
1470 ix
1471 );
1472 assert_eq!(
1473 actual.offset_utf16_to_offset(offset_utf16),
1474 ix,
1475 "offset_utf16_to_offset({:?})",
1476 offset_utf16
1477 );
1478 if ch == '\n' {
1479 point += Point::new(1, 0);
1480 point_utf16 += PointUtf16::new(1, 0);
1481 } else {
1482 point.column += ch.len_utf8() as u32;
1483 point_utf16.column += ch.len_utf16() as u32;
1484 }
1485 offset_utf16.0 += ch.len_utf16();
1486 }
1487
1488 let mut offset_utf16 = OffsetUtf16(0);
1489 let mut point_utf16 = Unclipped(PointUtf16::zero());
1490 for unit in expected.encode_utf16() {
1491 let left_offset = actual.clip_offset_utf16(offset_utf16, Bias::Left);
1492 let right_offset = actual.clip_offset_utf16(offset_utf16, Bias::Right);
1493 assert!(right_offset >= left_offset);
1494 // Ensure translating UTF-16 offsets to UTF-8 offsets doesn't panic.
1495 actual.offset_utf16_to_offset(left_offset);
1496 actual.offset_utf16_to_offset(right_offset);
1497
1498 let left_point = actual.clip_point_utf16(point_utf16, Bias::Left);
1499 let right_point = actual.clip_point_utf16(point_utf16, Bias::Right);
1500 assert!(right_point >= left_point);
1501 // Ensure translating valid UTF-16 points to offsets doesn't panic.
1502 actual.point_utf16_to_offset(left_point);
1503 actual.point_utf16_to_offset(right_point);
1504
1505 offset_utf16.0 += 1;
1506 if unit == b'\n' as u16 {
1507 point_utf16.0 += PointUtf16::new(1, 0);
1508 } else {
1509 point_utf16.0 += PointUtf16::new(0, 1);
1510 }
1511 }
1512
1513 for _ in 0..5 {
1514 let end_ix = clip_offset(&expected, rng.gen_range(0..=expected.len()), Right);
1515 let start_ix = clip_offset(&expected, rng.gen_range(0..=end_ix), Left);
1516 assert_eq!(
1517 actual.cursor(start_ix).summary::<TextSummary>(end_ix),
1518 TextSummary::from(&expected[start_ix..end_ix])
1519 );
1520 }
1521
1522 let mut expected_longest_rows = Vec::new();
1523 let mut longest_line_len = -1_isize;
1524 for (row, line) in expected.split('\n').enumerate() {
1525 let row = row as u32;
1526 assert_eq!(
1527 actual.line_len(row),
1528 line.len() as u32,
1529 "invalid line len for row {}",
1530 row
1531 );
1532
1533 let line_char_count = line.chars().count() as isize;
1534 match line_char_count.cmp(&longest_line_len) {
1535 Ordering::Less => {}
1536 Ordering::Equal => expected_longest_rows.push(row),
1537 Ordering::Greater => {
1538 longest_line_len = line_char_count;
1539 expected_longest_rows.clear();
1540 expected_longest_rows.push(row);
1541 }
1542 }
1543 }
1544
1545 let longest_row = actual.summary().longest_row;
1546 assert!(
1547 expected_longest_rows.contains(&longest_row),
1548 "incorrect longest row {}. expected {:?} with length {}",
1549 longest_row,
1550 expected_longest_rows,
1551 longest_line_len,
1552 );
1553 }
1554 }
1555
1556 fn clip_offset(text: &str, mut offset: usize, bias: Bias) -> usize {
1557 while !text.is_char_boundary(offset) {
1558 match bias {
1559 Bias::Left => offset -= 1,
1560 Bias::Right => offset += 1,
1561 }
1562 }
1563 offset
1564 }
1565
1566 impl Rope {
1567 fn text(&self) -> String {
1568 let mut text = String::new();
1569 for chunk in self.chunks.cursor::<()>() {
1570 text.push_str(&chunk.0);
1571 }
1572 text
1573 }
1574 }
1575}