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