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