1mod chunk;
2mod offset_utf16;
3mod point;
4mod point_utf16;
5mod unclipped;
6
7use chunk::Chunk;
8use rayon::iter::{IntoParallelIterator, ParallelIterator as _};
9use smallvec::SmallVec;
10use std::{
11 cmp, fmt, io, mem,
12 ops::{self, AddAssign, Range},
13 str,
14};
15use sum_tree::{Bias, Dimension, Dimensions, SumTree};
16
17pub use chunk::ChunkSlice;
18pub use offset_utf16::OffsetUtf16;
19pub use point::Point;
20pub use point_utf16::PointUtf16;
21pub use unclipped::Unclipped;
22
23#[derive(Clone, Default)]
24pub struct Rope {
25 chunks: SumTree<Chunk>,
26}
27
28impl Rope {
29 pub fn new() -> Self {
30 Self::default()
31 }
32
33 pub fn append(&mut self, rope: Rope) {
34 if let Some(chunk) = rope.chunks.first()
35 && (self
36 .chunks
37 .last()
38 .is_some_and(|c| c.text.len() < chunk::MIN_BASE)
39 || chunk.text.len() < chunk::MIN_BASE)
40 {
41 self.push_chunk(chunk.as_slice());
42
43 let mut chunks = rope.chunks.cursor::<()>(&());
44 chunks.next();
45 chunks.next();
46 self.chunks.append(chunks.suffix(), &());
47 self.check_invariants();
48 return;
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().div_ceil(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
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::<Dimensions<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::<Dimensions<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::<Dimensions<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::<Dimensions<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::<Dimensions<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::<Dimensions<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::<Dimensions<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::<Dimensions<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 #[inline(always)]
474 fn from(text: String) -> Self {
475 Rope::from(text.as_str())
476 }
477}
478
479impl From<&String> for Rope {
480 #[inline(always)]
481 fn from(text: &String) -> Self {
482 Rope::from(text.as_str())
483 }
484}
485
486impl fmt::Display for Rope {
487 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
488 for chunk in self.chunks() {
489 write!(f, "{}", chunk)?;
490 }
491 Ok(())
492 }
493}
494
495impl fmt::Debug for Rope {
496 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
497 use std::fmt::Write as _;
498
499 write!(f, "\"")?;
500 let mut format_string = String::new();
501 for chunk in self.chunks() {
502 write!(&mut format_string, "{:?}", chunk)?;
503 write!(f, "{}", &format_string[1..format_string.len() - 1])?;
504 format_string.clear();
505 }
506 write!(f, "\"")?;
507 Ok(())
508 }
509}
510
511pub struct Cursor<'a> {
512 rope: &'a Rope,
513 chunks: sum_tree::Cursor<'a, Chunk, usize>,
514 offset: usize,
515}
516
517impl<'a> Cursor<'a> {
518 pub fn new(rope: &'a Rope, offset: usize) -> Self {
519 let mut chunks = rope.chunks.cursor(&());
520 chunks.seek(&offset, Bias::Right);
521 Self {
522 rope,
523 chunks,
524 offset,
525 }
526 }
527
528 pub fn seek_forward(&mut self, end_offset: usize) {
529 debug_assert!(end_offset >= self.offset);
530
531 self.chunks.seek_forward(&end_offset, Bias::Right);
532 self.offset = end_offset;
533 }
534
535 pub fn slice(&mut self, end_offset: usize) -> Rope {
536 debug_assert!(
537 end_offset >= self.offset,
538 "cannot slice backwards from {} to {}",
539 self.offset,
540 end_offset
541 );
542
543 let mut slice = Rope::new();
544 if let Some(start_chunk) = self.chunks.item() {
545 let start_ix = self.offset - self.chunks.start();
546 let end_ix = cmp::min(end_offset, self.chunks.end()) - self.chunks.start();
547 slice.push_chunk(start_chunk.slice(start_ix..end_ix));
548 }
549
550 if end_offset > self.chunks.end() {
551 self.chunks.next();
552 slice.append(Rope {
553 chunks: self.chunks.slice(&end_offset, Bias::Right),
554 });
555 if let Some(end_chunk) = self.chunks.item() {
556 let end_ix = end_offset - self.chunks.start();
557 slice.push_chunk(end_chunk.slice(0..end_ix));
558 }
559 }
560
561 self.offset = end_offset;
562 slice
563 }
564
565 pub fn summary<D: TextDimension>(&mut self, end_offset: usize) -> D {
566 debug_assert!(end_offset >= self.offset);
567
568 let mut summary = D::zero(&());
569 if let Some(start_chunk) = self.chunks.item() {
570 let start_ix = self.offset - self.chunks.start();
571 let end_ix = cmp::min(end_offset, self.chunks.end()) - self.chunks.start();
572 summary.add_assign(&D::from_chunk(start_chunk.slice(start_ix..end_ix)));
573 }
574
575 if end_offset > self.chunks.end() {
576 self.chunks.next();
577 summary.add_assign(&self.chunks.summary(&end_offset, Bias::Right));
578 if let Some(end_chunk) = self.chunks.item() {
579 let end_ix = end_offset - self.chunks.start();
580 summary.add_assign(&D::from_chunk(end_chunk.slice(0..end_ix)));
581 }
582 }
583
584 self.offset = end_offset;
585 summary
586 }
587
588 pub fn suffix(mut self) -> Rope {
589 self.slice(self.rope.chunks.extent(&()))
590 }
591
592 pub fn offset(&self) -> usize {
593 self.offset
594 }
595}
596
597#[derive(Clone)]
598pub struct Chunks<'a> {
599 chunks: sum_tree::Cursor<'a, Chunk, usize>,
600 range: Range<usize>,
601 offset: usize,
602 reversed: bool,
603}
604
605impl<'a> Chunks<'a> {
606 pub fn new(rope: &'a Rope, range: Range<usize>, reversed: bool) -> Self {
607 let mut chunks = rope.chunks.cursor(&());
608 let offset = if reversed {
609 chunks.seek(&range.end, Bias::Left);
610 range.end
611 } else {
612 chunks.seek(&range.start, Bias::Right);
613 range.start
614 };
615 Self {
616 chunks,
617 range,
618 offset,
619 reversed,
620 }
621 }
622
623 fn offset_is_valid(&self) -> bool {
624 if self.reversed {
625 if self.offset <= self.range.start || self.offset > self.range.end {
626 return false;
627 }
628 } else if self.offset < self.range.start || self.offset >= self.range.end {
629 return false;
630 }
631
632 true
633 }
634
635 pub fn offset(&self) -> usize {
636 self.offset
637 }
638
639 pub fn seek(&mut self, mut offset: usize) {
640 offset = offset.clamp(self.range.start, self.range.end);
641
642 let bias = if self.reversed {
643 Bias::Left
644 } else {
645 Bias::Right
646 };
647
648 if offset >= self.chunks.end() {
649 self.chunks.seek_forward(&offset, bias);
650 } else {
651 self.chunks.seek(&offset, bias);
652 }
653
654 self.offset = offset;
655 }
656
657 pub fn set_range(&mut self, range: Range<usize>) {
658 self.range = range.clone();
659 self.seek(range.start);
660 }
661
662 /// Moves this cursor to the start of the next line in the rope.
663 ///
664 /// This method advances the cursor to the beginning of the next line.
665 /// If the cursor is already at the end of the rope, this method does nothing.
666 /// Reversed chunks iterators are not currently supported and will panic.
667 ///
668 /// Returns `true` if the cursor was successfully moved to the next line start,
669 /// or `false` if the cursor was already at the end of the rope.
670 pub fn next_line(&mut self) -> bool {
671 assert!(!self.reversed);
672
673 let mut found = false;
674 if let Some(chunk) = self.peek() {
675 if let Some(newline_ix) = chunk.find('\n') {
676 self.offset += newline_ix + 1;
677 found = self.offset <= self.range.end;
678 } else {
679 self.chunks
680 .search_forward(|summary| summary.text.lines.row > 0);
681 self.offset = *self.chunks.start();
682
683 if let Some(newline_ix) = self.peek().and_then(|chunk| chunk.find('\n')) {
684 self.offset += newline_ix + 1;
685 found = self.offset <= self.range.end;
686 } else {
687 self.offset = self.chunks.end();
688 }
689 }
690
691 if self.offset == self.chunks.end() {
692 self.next();
693 }
694 }
695
696 if self.offset > self.range.end {
697 self.offset = cmp::min(self.offset, self.range.end);
698 self.chunks.seek(&self.offset, Bias::Right);
699 }
700
701 found
702 }
703
704 /// Move this cursor to the preceding position in the rope that starts a new line.
705 /// Reversed chunks iterators are not currently supported and will panic.
706 ///
707 /// If this cursor is not on the start of a line, it will be moved to the start of
708 /// its current line. Otherwise it will be moved to the start of the previous line.
709 /// It updates the cursor's position and returns true if a previous line was found,
710 /// or false if the cursor was already at the start of the rope.
711 pub fn prev_line(&mut self) -> bool {
712 assert!(!self.reversed);
713
714 let initial_offset = self.offset;
715
716 if self.offset == *self.chunks.start() {
717 self.chunks.prev();
718 }
719
720 if let Some(chunk) = self.chunks.item() {
721 let mut end_ix = self.offset - *self.chunks.start();
722 if chunk.text.as_bytes()[end_ix - 1] == b'\n' {
723 end_ix -= 1;
724 }
725
726 if let Some(newline_ix) = chunk.text[..end_ix].rfind('\n') {
727 self.offset = *self.chunks.start() + newline_ix + 1;
728 if self.offset_is_valid() {
729 return true;
730 }
731 }
732 }
733
734 self.chunks
735 .search_backward(|summary| summary.text.lines.row > 0);
736 self.offset = *self.chunks.start();
737 if let Some(chunk) = self.chunks.item()
738 && let Some(newline_ix) = chunk.text.rfind('\n')
739 {
740 self.offset += newline_ix + 1;
741 if self.offset_is_valid() {
742 if self.offset == self.chunks.end() {
743 self.chunks.next();
744 }
745
746 return true;
747 }
748 }
749
750 if !self.offset_is_valid() || self.chunks.item().is_none() {
751 self.offset = self.range.start;
752 self.chunks.seek(&self.offset, Bias::Right);
753 }
754
755 self.offset < initial_offset && self.offset == 0
756 }
757
758 pub fn peek(&self) -> Option<&'a str> {
759 if !self.offset_is_valid() {
760 return None;
761 }
762
763 let chunk = self.chunks.item()?;
764 let chunk_start = *self.chunks.start();
765 let slice_range = if self.reversed {
766 let slice_start = cmp::max(chunk_start, self.range.start) - chunk_start;
767 let slice_end = self.offset - chunk_start;
768 slice_start..slice_end
769 } else {
770 let slice_start = self.offset - chunk_start;
771 let slice_end = cmp::min(self.chunks.end(), self.range.end) - chunk_start;
772 slice_start..slice_end
773 };
774
775 Some(&chunk.text[slice_range])
776 }
777
778 pub fn lines(self) -> Lines<'a> {
779 let reversed = self.reversed;
780 Lines {
781 chunks: self,
782 current_line: String::new(),
783 done: false,
784 reversed,
785 }
786 }
787
788 pub fn equals_str(&self, other: &str) -> bool {
789 let chunk = self.clone();
790 if chunk.reversed {
791 let mut offset = other.len();
792 for chunk in chunk {
793 if other[0..offset].ends_with(chunk) {
794 offset -= chunk.len();
795 } else {
796 return false;
797 }
798 }
799 if offset != 0 {
800 return false;
801 }
802 } else {
803 let mut offset = 0;
804 for chunk in chunk {
805 if offset >= other.len() {
806 return false;
807 }
808 if other[offset..].starts_with(chunk) {
809 offset += chunk.len();
810 } else {
811 return false;
812 }
813 }
814 if offset != other.len() {
815 return false;
816 }
817 }
818
819 true
820 }
821}
822
823impl<'a> Iterator for Chunks<'a> {
824 type Item = &'a str;
825
826 fn next(&mut self) -> Option<Self::Item> {
827 let chunk = self.peek()?;
828 if self.reversed {
829 self.offset -= chunk.len();
830 if self.offset <= *self.chunks.start() {
831 self.chunks.prev();
832 }
833 } else {
834 self.offset += chunk.len();
835 if self.offset >= self.chunks.end() {
836 self.chunks.next();
837 }
838 }
839
840 Some(chunk)
841 }
842}
843
844pub struct Bytes<'a> {
845 chunks: sum_tree::Cursor<'a, Chunk, usize>,
846 range: Range<usize>,
847 reversed: bool,
848}
849
850impl<'a> Bytes<'a> {
851 pub fn new(rope: &'a Rope, range: Range<usize>, reversed: bool) -> Self {
852 let mut chunks = rope.chunks.cursor(&());
853 if reversed {
854 chunks.seek(&range.end, Bias::Left);
855 } else {
856 chunks.seek(&range.start, Bias::Right);
857 }
858 Self {
859 chunks,
860 range,
861 reversed,
862 }
863 }
864
865 pub fn peek(&self) -> Option<&'a [u8]> {
866 let chunk = self.chunks.item()?;
867 if self.reversed && self.range.start >= self.chunks.end() {
868 return None;
869 }
870 let chunk_start = *self.chunks.start();
871 if self.range.end <= chunk_start {
872 return None;
873 }
874 let start = self.range.start.saturating_sub(chunk_start);
875 let end = self.range.end - chunk_start;
876 Some(&chunk.text.as_bytes()[start..chunk.text.len().min(end)])
877 }
878}
879
880impl<'a> Iterator for Bytes<'a> {
881 type Item = &'a [u8];
882
883 fn next(&mut self) -> Option<Self::Item> {
884 let result = self.peek();
885 if result.is_some() {
886 if self.reversed {
887 self.chunks.prev();
888 } else {
889 self.chunks.next();
890 }
891 }
892 result
893 }
894}
895
896impl io::Read for Bytes<'_> {
897 fn read(&mut self, buf: &mut [u8]) -> io::Result<usize> {
898 if let Some(chunk) = self.peek() {
899 let len = cmp::min(buf.len(), chunk.len());
900 if self.reversed {
901 buf[..len].copy_from_slice(&chunk[chunk.len() - len..]);
902 buf[..len].reverse();
903 self.range.end -= len;
904 } else {
905 buf[..len].copy_from_slice(&chunk[..len]);
906 self.range.start += len;
907 }
908
909 if len == chunk.len() {
910 if self.reversed {
911 self.chunks.prev();
912 } else {
913 self.chunks.next();
914 }
915 }
916 Ok(len)
917 } else {
918 Ok(0)
919 }
920 }
921}
922
923pub struct Lines<'a> {
924 chunks: Chunks<'a>,
925 current_line: String,
926 done: bool,
927 reversed: bool,
928}
929
930impl Lines<'_> {
931 pub fn next(&mut self) -> Option<&str> {
932 if self.done {
933 return None;
934 }
935
936 self.current_line.clear();
937
938 while let Some(chunk) = self.chunks.peek() {
939 let lines = chunk.split('\n');
940 if self.reversed {
941 let mut lines = lines.rev().peekable();
942 while let Some(line) = lines.next() {
943 self.current_line.insert_str(0, line);
944 if lines.peek().is_some() {
945 self.chunks
946 .seek(self.chunks.offset() - line.len() - "\n".len());
947 return Some(&self.current_line);
948 }
949 }
950 } else {
951 let mut lines = lines.peekable();
952 while let Some(line) = lines.next() {
953 self.current_line.push_str(line);
954 if lines.peek().is_some() {
955 self.chunks
956 .seek(self.chunks.offset() + line.len() + "\n".len());
957 return Some(&self.current_line);
958 }
959 }
960 }
961
962 self.chunks.next();
963 }
964
965 self.done = true;
966 Some(&self.current_line)
967 }
968
969 pub fn seek(&mut self, offset: usize) {
970 self.chunks.seek(offset);
971 self.current_line.clear();
972 self.done = false;
973 }
974
975 pub fn offset(&self) -> usize {
976 self.chunks.offset()
977 }
978}
979
980impl sum_tree::Item for Chunk {
981 type Summary = ChunkSummary;
982
983 fn summary(&self, _cx: &()) -> Self::Summary {
984 ChunkSummary {
985 text: self.as_slice().text_summary(),
986 }
987 }
988}
989
990#[derive(Clone, Debug, Default, Eq, PartialEq)]
991pub struct ChunkSummary {
992 text: TextSummary,
993}
994
995impl sum_tree::Summary for ChunkSummary {
996 type Context = ();
997
998 fn zero(_cx: &()) -> Self {
999 Default::default()
1000 }
1001
1002 fn add_summary(&mut self, summary: &Self, _: &()) {
1003 self.text += &summary.text;
1004 }
1005}
1006
1007/// Summary of a string of text.
1008#[derive(Copy, Clone, Debug, Default, Eq, PartialEq)]
1009pub struct TextSummary {
1010 /// Length in bytes.
1011 pub len: usize,
1012 /// Length in UTF-8.
1013 pub chars: usize,
1014 /// Length in UTF-16 code units
1015 pub len_utf16: OffsetUtf16,
1016 /// A point representing the number of lines and the length of the last line.
1017 ///
1018 /// In other words, it marks the point after the last byte in the text, (if
1019 /// EOF was a character, this would be its position).
1020 pub lines: Point,
1021 /// How many `char`s are in the first line
1022 pub first_line_chars: u32,
1023 /// How many `char`s are in the last line
1024 pub last_line_chars: u32,
1025 /// How many UTF-16 code units are in the last line
1026 pub last_line_len_utf16: u32,
1027 /// The row idx of the longest row
1028 pub longest_row: u32,
1029 /// How many `char`s are in the longest row
1030 pub longest_row_chars: u32,
1031}
1032
1033impl TextSummary {
1034 pub fn lines_utf16(&self) -> PointUtf16 {
1035 PointUtf16 {
1036 row: self.lines.row,
1037 column: self.last_line_len_utf16,
1038 }
1039 }
1040
1041 pub fn newline() -> Self {
1042 Self {
1043 len: 1,
1044 chars: 1,
1045 len_utf16: OffsetUtf16(1),
1046 first_line_chars: 0,
1047 last_line_chars: 0,
1048 last_line_len_utf16: 0,
1049 lines: Point::new(1, 0),
1050 longest_row: 0,
1051 longest_row_chars: 0,
1052 }
1053 }
1054
1055 pub fn add_newline(&mut self) {
1056 self.len += 1;
1057 self.len_utf16 += OffsetUtf16(self.len_utf16.0 + 1);
1058 self.last_line_chars = 0;
1059 self.last_line_len_utf16 = 0;
1060 self.lines += Point::new(1, 0);
1061 }
1062}
1063
1064impl<'a> From<&'a str> for TextSummary {
1065 fn from(text: &'a str) -> Self {
1066 let mut len_utf16 = OffsetUtf16(0);
1067 let mut lines = Point::new(0, 0);
1068 let mut first_line_chars = 0;
1069 let mut last_line_chars = 0;
1070 let mut last_line_len_utf16 = 0;
1071 let mut longest_row = 0;
1072 let mut longest_row_chars = 0;
1073 let mut chars = 0;
1074 for c in text.chars() {
1075 chars += 1;
1076 len_utf16.0 += c.len_utf16();
1077
1078 if c == '\n' {
1079 lines += Point::new(1, 0);
1080 last_line_len_utf16 = 0;
1081 last_line_chars = 0;
1082 } else {
1083 lines.column += c.len_utf8() as u32;
1084 last_line_len_utf16 += c.len_utf16() as u32;
1085 last_line_chars += 1;
1086 }
1087
1088 if lines.row == 0 {
1089 first_line_chars = last_line_chars;
1090 }
1091
1092 if last_line_chars > longest_row_chars {
1093 longest_row = lines.row;
1094 longest_row_chars = last_line_chars;
1095 }
1096 }
1097
1098 TextSummary {
1099 len: text.len(),
1100 chars,
1101 len_utf16,
1102 lines,
1103 first_line_chars,
1104 last_line_chars,
1105 last_line_len_utf16,
1106 longest_row,
1107 longest_row_chars,
1108 }
1109 }
1110}
1111
1112impl sum_tree::Summary for TextSummary {
1113 type Context = ();
1114
1115 fn zero(_cx: &()) -> Self {
1116 Default::default()
1117 }
1118
1119 fn add_summary(&mut self, summary: &Self, _: &Self::Context) {
1120 *self += summary;
1121 }
1122}
1123
1124impl ops::Add<Self> for TextSummary {
1125 type Output = Self;
1126
1127 fn add(mut self, rhs: Self) -> Self::Output {
1128 AddAssign::add_assign(&mut self, &rhs);
1129 self
1130 }
1131}
1132
1133impl<'a> ops::AddAssign<&'a Self> for TextSummary {
1134 fn add_assign(&mut self, other: &'a Self) {
1135 let joined_chars = self.last_line_chars + other.first_line_chars;
1136 if joined_chars > self.longest_row_chars {
1137 self.longest_row = self.lines.row;
1138 self.longest_row_chars = joined_chars;
1139 }
1140 if other.longest_row_chars > self.longest_row_chars {
1141 self.longest_row = self.lines.row + other.longest_row;
1142 self.longest_row_chars = other.longest_row_chars;
1143 }
1144
1145 if self.lines.row == 0 {
1146 self.first_line_chars += other.first_line_chars;
1147 }
1148
1149 if other.lines.row == 0 {
1150 self.last_line_chars += other.first_line_chars;
1151 self.last_line_len_utf16 += other.last_line_len_utf16;
1152 } else {
1153 self.last_line_chars = other.last_line_chars;
1154 self.last_line_len_utf16 = other.last_line_len_utf16;
1155 }
1156
1157 self.chars += other.chars;
1158 self.len += other.len;
1159 self.len_utf16 += other.len_utf16;
1160 self.lines += other.lines;
1161 }
1162}
1163
1164impl ops::AddAssign<Self> for TextSummary {
1165 fn add_assign(&mut self, other: Self) {
1166 *self += &other;
1167 }
1168}
1169
1170pub trait TextDimension:
1171 'static + Clone + Copy + Default + for<'a> Dimension<'a, ChunkSummary> + std::fmt::Debug
1172{
1173 fn from_text_summary(summary: &TextSummary) -> Self;
1174 fn from_chunk(chunk: ChunkSlice) -> Self;
1175 fn add_assign(&mut self, other: &Self);
1176}
1177
1178impl<D1: TextDimension, D2: TextDimension> TextDimension for Dimensions<D1, D2, ()> {
1179 fn from_text_summary(summary: &TextSummary) -> Self {
1180 Dimensions(
1181 D1::from_text_summary(summary),
1182 D2::from_text_summary(summary),
1183 (),
1184 )
1185 }
1186
1187 fn from_chunk(chunk: ChunkSlice) -> Self {
1188 Dimensions(D1::from_chunk(chunk), D2::from_chunk(chunk), ())
1189 }
1190
1191 fn add_assign(&mut self, other: &Self) {
1192 self.0.add_assign(&other.0);
1193 self.1.add_assign(&other.1);
1194 }
1195}
1196
1197impl<'a> sum_tree::Dimension<'a, ChunkSummary> for TextSummary {
1198 fn zero(_cx: &()) -> Self {
1199 Default::default()
1200 }
1201
1202 fn add_summary(&mut self, summary: &'a ChunkSummary, _: &()) {
1203 *self += &summary.text;
1204 }
1205}
1206
1207impl TextDimension for TextSummary {
1208 fn from_text_summary(summary: &TextSummary) -> Self {
1209 *summary
1210 }
1211
1212 fn from_chunk(chunk: ChunkSlice) -> Self {
1213 chunk.text_summary()
1214 }
1215
1216 fn add_assign(&mut self, other: &Self) {
1217 *self += other;
1218 }
1219}
1220
1221impl<'a> sum_tree::Dimension<'a, ChunkSummary> for usize {
1222 fn zero(_cx: &()) -> Self {
1223 Default::default()
1224 }
1225
1226 fn add_summary(&mut self, summary: &'a ChunkSummary, _: &()) {
1227 *self += summary.text.len;
1228 }
1229}
1230
1231impl TextDimension for usize {
1232 fn from_text_summary(summary: &TextSummary) -> Self {
1233 summary.len
1234 }
1235
1236 fn from_chunk(chunk: ChunkSlice) -> Self {
1237 chunk.len()
1238 }
1239
1240 fn add_assign(&mut self, other: &Self) {
1241 *self += other;
1242 }
1243}
1244
1245impl<'a> sum_tree::Dimension<'a, ChunkSummary> for OffsetUtf16 {
1246 fn zero(_cx: &()) -> Self {
1247 Default::default()
1248 }
1249
1250 fn add_summary(&mut self, summary: &'a ChunkSummary, _: &()) {
1251 *self += summary.text.len_utf16;
1252 }
1253}
1254
1255impl TextDimension for OffsetUtf16 {
1256 fn from_text_summary(summary: &TextSummary) -> Self {
1257 summary.len_utf16
1258 }
1259
1260 fn from_chunk(chunk: ChunkSlice) -> Self {
1261 chunk.len_utf16()
1262 }
1263
1264 fn add_assign(&mut self, other: &Self) {
1265 *self += other;
1266 }
1267}
1268
1269impl<'a> sum_tree::Dimension<'a, ChunkSummary> for Point {
1270 fn zero(_cx: &()) -> Self {
1271 Default::default()
1272 }
1273
1274 fn add_summary(&mut self, summary: &'a ChunkSummary, _: &()) {
1275 *self += summary.text.lines;
1276 }
1277}
1278
1279impl TextDimension for Point {
1280 fn from_text_summary(summary: &TextSummary) -> Self {
1281 summary.lines
1282 }
1283
1284 fn from_chunk(chunk: ChunkSlice) -> Self {
1285 chunk.lines()
1286 }
1287
1288 fn add_assign(&mut self, other: &Self) {
1289 *self += other;
1290 }
1291}
1292
1293impl<'a> sum_tree::Dimension<'a, ChunkSummary> for PointUtf16 {
1294 fn zero(_cx: &()) -> Self {
1295 Default::default()
1296 }
1297
1298 fn add_summary(&mut self, summary: &'a ChunkSummary, _: &()) {
1299 *self += summary.text.lines_utf16();
1300 }
1301}
1302
1303impl TextDimension for PointUtf16 {
1304 fn from_text_summary(summary: &TextSummary) -> Self {
1305 summary.lines_utf16()
1306 }
1307
1308 fn from_chunk(chunk: ChunkSlice) -> Self {
1309 PointUtf16 {
1310 row: chunk.lines().row,
1311 column: chunk.last_line_len_utf16(),
1312 }
1313 }
1314
1315 fn add_assign(&mut self, other: &Self) {
1316 *self += other;
1317 }
1318}
1319
1320/// A pair of text dimensions in which only the first dimension is used for comparison,
1321/// but both dimensions are updated during addition and subtraction.
1322#[derive(Clone, Copy, Debug)]
1323pub struct DimensionPair<K, V> {
1324 pub key: K,
1325 pub value: Option<V>,
1326}
1327
1328impl<K: Default, V: Default> Default for DimensionPair<K, V> {
1329 fn default() -> Self {
1330 Self {
1331 key: Default::default(),
1332 value: Some(Default::default()),
1333 }
1334 }
1335}
1336
1337impl<K, V> cmp::Ord for DimensionPair<K, V>
1338where
1339 K: cmp::Ord,
1340{
1341 fn cmp(&self, other: &Self) -> cmp::Ordering {
1342 self.key.cmp(&other.key)
1343 }
1344}
1345
1346impl<K, V> cmp::PartialOrd for DimensionPair<K, V>
1347where
1348 K: cmp::PartialOrd,
1349{
1350 fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
1351 self.key.partial_cmp(&other.key)
1352 }
1353}
1354
1355impl<K, V> cmp::PartialEq for DimensionPair<K, V>
1356where
1357 K: cmp::PartialEq,
1358{
1359 fn eq(&self, other: &Self) -> bool {
1360 self.key.eq(&other.key)
1361 }
1362}
1363
1364impl<K, V> ops::Sub for DimensionPair<K, V>
1365where
1366 K: ops::Sub<K, Output = K>,
1367 V: ops::Sub<V, Output = V>,
1368{
1369 type Output = Self;
1370
1371 fn sub(self, rhs: Self) -> Self::Output {
1372 Self {
1373 key: self.key - rhs.key,
1374 value: self.value.zip(rhs.value).map(|(a, b)| a - b),
1375 }
1376 }
1377}
1378
1379impl<K, V> cmp::Eq for DimensionPair<K, V> where K: cmp::Eq {}
1380
1381impl<'a, K, V> sum_tree::Dimension<'a, ChunkSummary> for DimensionPair<K, V>
1382where
1383 K: sum_tree::Dimension<'a, ChunkSummary>,
1384 V: sum_tree::Dimension<'a, ChunkSummary>,
1385{
1386 fn zero(_cx: &()) -> Self {
1387 Self {
1388 key: K::zero(_cx),
1389 value: Some(V::zero(_cx)),
1390 }
1391 }
1392
1393 fn add_summary(&mut self, summary: &'a ChunkSummary, _cx: &()) {
1394 self.key.add_summary(summary, _cx);
1395 if let Some(value) = &mut self.value {
1396 value.add_summary(summary, _cx);
1397 }
1398 }
1399}
1400
1401impl<K, V> TextDimension for DimensionPair<K, V>
1402where
1403 K: TextDimension,
1404 V: TextDimension,
1405{
1406 fn add_assign(&mut self, other: &Self) {
1407 self.key.add_assign(&other.key);
1408 if let Some(value) = &mut self.value {
1409 if let Some(other_value) = other.value.as_ref() {
1410 value.add_assign(other_value);
1411 } else {
1412 self.value.take();
1413 }
1414 }
1415 }
1416
1417 fn from_chunk(chunk: ChunkSlice) -> Self {
1418 Self {
1419 key: K::from_chunk(chunk),
1420 value: Some(V::from_chunk(chunk)),
1421 }
1422 }
1423
1424 fn from_text_summary(summary: &TextSummary) -> Self {
1425 Self {
1426 key: K::from_text_summary(summary),
1427 value: Some(V::from_text_summary(summary)),
1428 }
1429 }
1430}
1431
1432#[cfg(test)]
1433mod tests {
1434 use super::*;
1435 use Bias::{Left, Right};
1436 use rand::prelude::*;
1437 use std::{cmp::Ordering, env, io::Read};
1438 use util::RandomCharIter;
1439
1440 #[ctor::ctor]
1441 fn init_logger() {
1442 zlog::init_test();
1443 }
1444
1445 #[test]
1446 fn test_all_4_byte_chars() {
1447 let mut rope = Rope::new();
1448 let text = "🏀".repeat(256);
1449 rope.push(&text);
1450 assert_eq!(rope.text(), text);
1451 }
1452
1453 #[test]
1454 fn test_clip() {
1455 let rope = Rope::from("🧘");
1456
1457 assert_eq!(rope.clip_offset(1, Bias::Left), 0);
1458 assert_eq!(rope.clip_offset(1, Bias::Right), 4);
1459 assert_eq!(rope.clip_offset(5, Bias::Right), 4);
1460
1461 assert_eq!(
1462 rope.clip_point(Point::new(0, 1), Bias::Left),
1463 Point::new(0, 0)
1464 );
1465 assert_eq!(
1466 rope.clip_point(Point::new(0, 1), Bias::Right),
1467 Point::new(0, 4)
1468 );
1469 assert_eq!(
1470 rope.clip_point(Point::new(0, 5), Bias::Right),
1471 Point::new(0, 4)
1472 );
1473
1474 assert_eq!(
1475 rope.clip_point_utf16(Unclipped(PointUtf16::new(0, 1)), Bias::Left),
1476 PointUtf16::new(0, 0)
1477 );
1478 assert_eq!(
1479 rope.clip_point_utf16(Unclipped(PointUtf16::new(0, 1)), Bias::Right),
1480 PointUtf16::new(0, 2)
1481 );
1482 assert_eq!(
1483 rope.clip_point_utf16(Unclipped(PointUtf16::new(0, 3)), Bias::Right),
1484 PointUtf16::new(0, 2)
1485 );
1486
1487 assert_eq!(
1488 rope.clip_offset_utf16(OffsetUtf16(1), Bias::Left),
1489 OffsetUtf16(0)
1490 );
1491 assert_eq!(
1492 rope.clip_offset_utf16(OffsetUtf16(1), Bias::Right),
1493 OffsetUtf16(2)
1494 );
1495 assert_eq!(
1496 rope.clip_offset_utf16(OffsetUtf16(3), Bias::Right),
1497 OffsetUtf16(2)
1498 );
1499 }
1500
1501 #[test]
1502 fn test_prev_next_line() {
1503 let rope = Rope::from("abc\ndef\nghi\njkl");
1504
1505 let mut chunks = rope.chunks();
1506 assert_eq!(chunks.peek().unwrap().chars().next().unwrap(), 'a');
1507
1508 assert!(chunks.next_line());
1509 assert_eq!(chunks.peek().unwrap().chars().next().unwrap(), 'd');
1510
1511 assert!(chunks.next_line());
1512 assert_eq!(chunks.peek().unwrap().chars().next().unwrap(), 'g');
1513
1514 assert!(chunks.next_line());
1515 assert_eq!(chunks.peek().unwrap().chars().next().unwrap(), 'j');
1516
1517 assert!(!chunks.next_line());
1518 assert_eq!(chunks.peek(), None);
1519
1520 assert!(chunks.prev_line());
1521 assert_eq!(chunks.peek().unwrap().chars().next().unwrap(), 'j');
1522
1523 assert!(chunks.prev_line());
1524 assert_eq!(chunks.peek().unwrap().chars().next().unwrap(), 'g');
1525
1526 assert!(chunks.prev_line());
1527 assert_eq!(chunks.peek().unwrap().chars().next().unwrap(), 'd');
1528
1529 assert!(chunks.prev_line());
1530 assert_eq!(chunks.peek().unwrap().chars().next().unwrap(), 'a');
1531
1532 assert!(!chunks.prev_line());
1533 assert_eq!(chunks.peek().unwrap().chars().next().unwrap(), 'a');
1534
1535 // Only return true when the cursor has moved to the start of a line
1536 let mut chunks = rope.chunks_in_range(5..7);
1537 chunks.seek(6);
1538 assert!(!chunks.prev_line());
1539 assert_eq!(chunks.peek().unwrap().chars().next().unwrap(), 'e');
1540
1541 assert!(!chunks.next_line());
1542 assert_eq!(chunks.peek(), None);
1543 }
1544
1545 #[test]
1546 fn test_lines() {
1547 let rope = Rope::from("abc\ndefg\nhi");
1548 let mut lines = rope.chunks().lines();
1549 assert_eq!(lines.next(), Some("abc"));
1550 assert_eq!(lines.next(), Some("defg"));
1551 assert_eq!(lines.next(), Some("hi"));
1552 assert_eq!(lines.next(), None);
1553
1554 let rope = Rope::from("abc\ndefg\nhi\n");
1555 let mut lines = rope.chunks().lines();
1556 assert_eq!(lines.next(), Some("abc"));
1557 assert_eq!(lines.next(), Some("defg"));
1558 assert_eq!(lines.next(), Some("hi"));
1559 assert_eq!(lines.next(), Some(""));
1560 assert_eq!(lines.next(), None);
1561
1562 let rope = Rope::from("abc\ndefg\nhi");
1563 let mut lines = rope.reversed_chunks_in_range(0..rope.len()).lines();
1564 assert_eq!(lines.next(), Some("hi"));
1565 assert_eq!(lines.next(), Some("defg"));
1566 assert_eq!(lines.next(), Some("abc"));
1567 assert_eq!(lines.next(), None);
1568
1569 let rope = Rope::from("abc\ndefg\nhi\n");
1570 let mut lines = rope.reversed_chunks_in_range(0..rope.len()).lines();
1571 assert_eq!(lines.next(), Some(""));
1572 assert_eq!(lines.next(), Some("hi"));
1573 assert_eq!(lines.next(), Some("defg"));
1574 assert_eq!(lines.next(), Some("abc"));
1575 assert_eq!(lines.next(), None);
1576 }
1577
1578 #[gpui::test(iterations = 100)]
1579 fn test_random_rope(mut rng: StdRng) {
1580 let operations = env::var("OPERATIONS")
1581 .map(|i| i.parse().expect("invalid `OPERATIONS` variable"))
1582 .unwrap_or(10);
1583
1584 let mut expected = String::new();
1585 let mut actual = Rope::new();
1586 for _ in 0..operations {
1587 let end_ix = clip_offset(&expected, rng.gen_range(0..=expected.len()), Right);
1588 let start_ix = clip_offset(&expected, rng.gen_range(0..=end_ix), Left);
1589 let len = rng.gen_range(0..=64);
1590 let new_text: String = RandomCharIter::new(&mut rng).take(len).collect();
1591
1592 let mut new_actual = Rope::new();
1593 let mut cursor = actual.cursor(0);
1594 new_actual.append(cursor.slice(start_ix));
1595 new_actual.push(&new_text);
1596 cursor.seek_forward(end_ix);
1597 new_actual.append(cursor.suffix());
1598 actual = new_actual;
1599
1600 expected.replace_range(start_ix..end_ix, &new_text);
1601
1602 assert_eq!(actual.text(), expected);
1603 log::info!("text: {:?}", expected);
1604
1605 for _ in 0..5 {
1606 let end_ix = clip_offset(&expected, rng.gen_range(0..=expected.len()), Right);
1607 let start_ix = clip_offset(&expected, rng.gen_range(0..=end_ix), Left);
1608
1609 let actual_text = actual.chunks_in_range(start_ix..end_ix).collect::<String>();
1610 assert_eq!(actual_text, &expected[start_ix..end_ix]);
1611
1612 let mut actual_text = String::new();
1613 actual
1614 .bytes_in_range(start_ix..end_ix)
1615 .read_to_string(&mut actual_text)
1616 .unwrap();
1617 assert_eq!(actual_text, &expected[start_ix..end_ix]);
1618
1619 assert_eq!(
1620 actual
1621 .reversed_chunks_in_range(start_ix..end_ix)
1622 .collect::<Vec<&str>>()
1623 .into_iter()
1624 .rev()
1625 .collect::<String>(),
1626 &expected[start_ix..end_ix]
1627 );
1628
1629 let mut expected_line_starts: Vec<_> = expected[start_ix..end_ix]
1630 .match_indices('\n')
1631 .map(|(index, _)| start_ix + index + 1)
1632 .collect();
1633
1634 let mut chunks = actual.chunks_in_range(start_ix..end_ix);
1635
1636 let mut actual_line_starts = Vec::new();
1637 while chunks.next_line() {
1638 actual_line_starts.push(chunks.offset());
1639 }
1640 assert_eq!(
1641 actual_line_starts,
1642 expected_line_starts,
1643 "actual line starts != expected line starts when using next_line() for {:?} ({:?})",
1644 &expected[start_ix..end_ix],
1645 start_ix..end_ix
1646 );
1647
1648 if start_ix < end_ix
1649 && (start_ix == 0 || expected.as_bytes()[start_ix - 1] == b'\n')
1650 {
1651 expected_line_starts.insert(0, start_ix);
1652 }
1653 // Remove the last index if it starts at the end of the range.
1654 if expected_line_starts.last() == Some(&end_ix) {
1655 expected_line_starts.pop();
1656 }
1657
1658 let mut actual_line_starts = Vec::new();
1659 while chunks.prev_line() {
1660 actual_line_starts.push(chunks.offset());
1661 }
1662 actual_line_starts.reverse();
1663 assert_eq!(
1664 actual_line_starts,
1665 expected_line_starts,
1666 "actual line starts != expected line starts when using prev_line() for {:?} ({:?})",
1667 &expected[start_ix..end_ix],
1668 start_ix..end_ix
1669 );
1670
1671 // Check that next_line/prev_line work correctly from random positions
1672 let mut offset = rng.gen_range(start_ix..=end_ix);
1673 while !expected.is_char_boundary(offset) {
1674 offset -= 1;
1675 }
1676 chunks.seek(offset);
1677
1678 for _ in 0..5 {
1679 if rng.r#gen() {
1680 let expected_next_line_start = expected[offset..end_ix]
1681 .find('\n')
1682 .map(|newline_ix| offset + newline_ix + 1);
1683
1684 let moved = chunks.next_line();
1685 assert_eq!(
1686 moved,
1687 expected_next_line_start.is_some(),
1688 "unexpected result from next_line after seeking to {} in range {:?} ({:?})",
1689 offset,
1690 start_ix..end_ix,
1691 &expected[start_ix..end_ix]
1692 );
1693 if let Some(expected_next_line_start) = expected_next_line_start {
1694 assert_eq!(
1695 chunks.offset(),
1696 expected_next_line_start,
1697 "invalid position after seeking to {} in range {:?} ({:?})",
1698 offset,
1699 start_ix..end_ix,
1700 &expected[start_ix..end_ix]
1701 );
1702 } else {
1703 assert_eq!(
1704 chunks.offset(),
1705 end_ix,
1706 "invalid position after seeking to {} in range {:?} ({:?})",
1707 offset,
1708 start_ix..end_ix,
1709 &expected[start_ix..end_ix]
1710 );
1711 }
1712 } else {
1713 let search_end = if offset > 0 && expected.as_bytes()[offset - 1] == b'\n' {
1714 offset - 1
1715 } else {
1716 offset
1717 };
1718
1719 let expected_prev_line_start = expected[..search_end]
1720 .rfind('\n')
1721 .and_then(|newline_ix| {
1722 let line_start_ix = newline_ix + 1;
1723 if line_start_ix >= start_ix {
1724 Some(line_start_ix)
1725 } else {
1726 None
1727 }
1728 })
1729 .or({
1730 if offset > 0 && start_ix == 0 {
1731 Some(0)
1732 } else {
1733 None
1734 }
1735 });
1736
1737 let moved = chunks.prev_line();
1738 assert_eq!(
1739 moved,
1740 expected_prev_line_start.is_some(),
1741 "unexpected result from prev_line after seeking to {} in range {:?} ({:?})",
1742 offset,
1743 start_ix..end_ix,
1744 &expected[start_ix..end_ix]
1745 );
1746 if let Some(expected_prev_line_start) = expected_prev_line_start {
1747 assert_eq!(
1748 chunks.offset(),
1749 expected_prev_line_start,
1750 "invalid position after seeking to {} in range {:?} ({:?})",
1751 offset,
1752 start_ix..end_ix,
1753 &expected[start_ix..end_ix]
1754 );
1755 } else {
1756 assert_eq!(
1757 chunks.offset(),
1758 start_ix,
1759 "invalid position after seeking to {} in range {:?} ({:?})",
1760 offset,
1761 start_ix..end_ix,
1762 &expected[start_ix..end_ix]
1763 );
1764 }
1765 }
1766
1767 assert!((start_ix..=end_ix).contains(&chunks.offset()));
1768 if rng.r#gen() {
1769 offset = rng.gen_range(start_ix..=end_ix);
1770 while !expected.is_char_boundary(offset) {
1771 offset -= 1;
1772 }
1773 chunks.seek(offset);
1774 } else {
1775 chunks.next();
1776 offset = chunks.offset();
1777 assert!((start_ix..=end_ix).contains(&chunks.offset()));
1778 }
1779 }
1780 }
1781
1782 let mut offset_utf16 = OffsetUtf16(0);
1783 let mut point = Point::new(0, 0);
1784 let mut point_utf16 = PointUtf16::new(0, 0);
1785 for (ix, ch) in expected.char_indices().chain(Some((expected.len(), '\0'))) {
1786 assert_eq!(actual.offset_to_point(ix), point, "offset_to_point({})", ix);
1787 assert_eq!(
1788 actual.offset_to_point_utf16(ix),
1789 point_utf16,
1790 "offset_to_point_utf16({})",
1791 ix
1792 );
1793 assert_eq!(
1794 actual.point_to_offset(point),
1795 ix,
1796 "point_to_offset({:?})",
1797 point
1798 );
1799 assert_eq!(
1800 actual.point_utf16_to_offset(point_utf16),
1801 ix,
1802 "point_utf16_to_offset({:?})",
1803 point_utf16
1804 );
1805 assert_eq!(
1806 actual.offset_to_offset_utf16(ix),
1807 offset_utf16,
1808 "offset_to_offset_utf16({:?})",
1809 ix
1810 );
1811 assert_eq!(
1812 actual.offset_utf16_to_offset(offset_utf16),
1813 ix,
1814 "offset_utf16_to_offset({:?})",
1815 offset_utf16
1816 );
1817 if ch == '\n' {
1818 point += Point::new(1, 0);
1819 point_utf16 += PointUtf16::new(1, 0);
1820 } else {
1821 point.column += ch.len_utf8() as u32;
1822 point_utf16.column += ch.len_utf16() as u32;
1823 }
1824 offset_utf16.0 += ch.len_utf16();
1825 }
1826
1827 let mut offset_utf16 = OffsetUtf16(0);
1828 let mut point_utf16 = Unclipped(PointUtf16::zero());
1829 for unit in expected.encode_utf16() {
1830 let left_offset = actual.clip_offset_utf16(offset_utf16, Bias::Left);
1831 let right_offset = actual.clip_offset_utf16(offset_utf16, Bias::Right);
1832 assert!(right_offset >= left_offset);
1833 // Ensure translating UTF-16 offsets to UTF-8 offsets doesn't panic.
1834 actual.offset_utf16_to_offset(left_offset);
1835 actual.offset_utf16_to_offset(right_offset);
1836
1837 let left_point = actual.clip_point_utf16(point_utf16, Bias::Left);
1838 let right_point = actual.clip_point_utf16(point_utf16, Bias::Right);
1839 assert!(right_point >= left_point);
1840 // Ensure translating valid UTF-16 points to offsets doesn't panic.
1841 actual.point_utf16_to_offset(left_point);
1842 actual.point_utf16_to_offset(right_point);
1843
1844 offset_utf16.0 += 1;
1845 if unit == b'\n' as u16 {
1846 point_utf16.0 += PointUtf16::new(1, 0);
1847 } else {
1848 point_utf16.0 += PointUtf16::new(0, 1);
1849 }
1850 }
1851
1852 for _ in 0..5 {
1853 let end_ix = clip_offset(&expected, rng.gen_range(0..=expected.len()), Right);
1854 let start_ix = clip_offset(&expected, rng.gen_range(0..=end_ix), Left);
1855 assert_eq!(
1856 actual.cursor(start_ix).summary::<TextSummary>(end_ix),
1857 TextSummary::from(&expected[start_ix..end_ix])
1858 );
1859 }
1860
1861 let mut expected_longest_rows = Vec::new();
1862 let mut longest_line_len = -1_isize;
1863 for (row, line) in expected.split('\n').enumerate() {
1864 let row = row as u32;
1865 assert_eq!(
1866 actual.line_len(row),
1867 line.len() as u32,
1868 "invalid line len for row {}",
1869 row
1870 );
1871
1872 let line_char_count = line.chars().count() as isize;
1873 match line_char_count.cmp(&longest_line_len) {
1874 Ordering::Less => {}
1875 Ordering::Equal => expected_longest_rows.push(row),
1876 Ordering::Greater => {
1877 longest_line_len = line_char_count;
1878 expected_longest_rows.clear();
1879 expected_longest_rows.push(row);
1880 }
1881 }
1882 }
1883
1884 let longest_row = actual.summary().longest_row;
1885 assert!(
1886 expected_longest_rows.contains(&longest_row),
1887 "incorrect longest row {}. expected {:?} with length {}",
1888 longest_row,
1889 expected_longest_rows,
1890 longest_line_len,
1891 );
1892 }
1893 }
1894
1895 #[test]
1896 fn test_chunks_equals_str() {
1897 let text = "This is a multi-chunk\n& multi-line test string!";
1898 let rope = Rope::from(text);
1899 for start in 0..text.len() {
1900 for end in start..text.len() {
1901 let range = start..end;
1902 let correct_substring = &text[start..end];
1903
1904 // Test that correct range returns true
1905 assert!(
1906 rope.chunks_in_range(range.clone())
1907 .equals_str(correct_substring)
1908 );
1909 assert!(
1910 rope.reversed_chunks_in_range(range.clone())
1911 .equals_str(correct_substring)
1912 );
1913
1914 // Test that all other ranges return false (unless they happen to match)
1915 for other_start in 0..text.len() {
1916 for other_end in other_start..text.len() {
1917 if other_start == start && other_end == end {
1918 continue;
1919 }
1920 let other_substring = &text[other_start..other_end];
1921
1922 // Only assert false if the substrings are actually different
1923 if other_substring == correct_substring {
1924 continue;
1925 }
1926 assert!(
1927 !rope
1928 .chunks_in_range(range.clone())
1929 .equals_str(other_substring)
1930 );
1931 assert!(
1932 !rope
1933 .reversed_chunks_in_range(range.clone())
1934 .equals_str(other_substring)
1935 );
1936 }
1937 }
1938 }
1939 }
1940
1941 let rope = Rope::from("");
1942 assert!(rope.chunks_in_range(0..0).equals_str(""));
1943 assert!(rope.reversed_chunks_in_range(0..0).equals_str(""));
1944 assert!(!rope.chunks_in_range(0..0).equals_str("foo"));
1945 assert!(!rope.reversed_chunks_in_range(0..0).equals_str("foo"));
1946 }
1947
1948 fn clip_offset(text: &str, mut offset: usize, bias: Bias) -> usize {
1949 while !text.is_char_boundary(offset) {
1950 match bias {
1951 Bias::Left => offset -= 1,
1952 Bias::Right => offset += 1,
1953 }
1954 }
1955 offset
1956 }
1957
1958 impl Rope {
1959 fn text(&self) -> String {
1960 let mut text = String::new();
1961 for chunk in self.chunks.cursor::<()>(&()) {
1962 text.push_str(&chunk.text);
1963 }
1964 text
1965 }
1966 }
1967}