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