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