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