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