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