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