1mod offset_utf16;
2mod point;
3mod point_utf16;
4mod unclipped;
5
6use arrayvec::ArrayString;
7use bromberg_sl2::HashMatrix;
8use smallvec::SmallVec;
9use std::{
10 cmp, fmt, io, mem,
11 ops::{AddAssign, Range},
12 str,
13};
14use sum_tree::{Bias, Dimension, SumTree};
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 = 16;
27
28/// Type alias to [HashMatrix], an implementation of a homomorphic hash function. Two [Rope] instances
29/// containing the same text will produce the same fingerprint. This hash function is special in that
30/// it allows us to hash individual chunks and aggregate them up the [Rope]'s tree, with the resulting
31/// hash being equivalent to hashing all the text contained in the [Rope] at once.
32pub type RopeFingerprint = HashMatrix;
33
34#[derive(Clone, Default)]
35pub struct Rope {
36 chunks: SumTree<Chunk>,
37}
38
39impl Rope {
40 pub fn new() -> Self {
41 Self::default()
42 }
43
44 pub fn append(&mut self, rope: Rope) {
45 let mut chunks = rope.chunks.cursor::<()>();
46 chunks.next(&());
47 if let Some(chunk) = chunks.item() {
48 if self.chunks.last().map_or(false, |c| c.0.len() < CHUNK_BASE)
49 || chunk.0.len() < CHUNK_BASE
50 {
51 self.push(&chunk.0);
52 chunks.next(&());
53 }
54 }
55
56 self.chunks.push_tree(chunks.suffix(&()), &());
57 self.check_invariants();
58 }
59
60 pub fn replace(&mut self, range: Range<usize>, text: &str) {
61 let mut new_rope = Rope::new();
62 let mut cursor = self.cursor(0);
63 new_rope.append(cursor.slice(range.start));
64 cursor.seek_forward(range.end);
65 new_rope.push(text);
66 new_rope.append(cursor.suffix());
67 *self = new_rope;
68 }
69
70 pub fn slice(&self, range: Range<usize>) -> Rope {
71 let mut cursor = self.cursor(0);
72 cursor.seek_forward(range.start);
73 cursor.slice(range.end)
74 }
75
76 pub fn slice_rows(&self, range: Range<u32>) -> Rope {
77 //This would be more efficient with a forward advance after the first, but it's fine
78 let start = self.point_to_offset(Point::new(range.start, 0));
79 let end = self.point_to_offset(Point::new(range.end, 0));
80 self.slice(start..end)
81 }
82
83 pub fn push(&mut self, text: &str) {
84 let mut new_chunks = SmallVec::<[_; 16]>::new();
85 let mut new_chunk = ArrayString::new();
86 for ch in text.chars() {
87 if new_chunk.len() + ch.len_utf8() > 2 * CHUNK_BASE {
88 new_chunks.push(Chunk(new_chunk));
89 new_chunk = ArrayString::new();
90 }
91
92 new_chunk.push(ch);
93 }
94 if !new_chunk.is_empty() {
95 new_chunks.push(Chunk(new_chunk));
96 }
97
98 let mut new_chunks = new_chunks.into_iter();
99 let mut first_new_chunk = new_chunks.next();
100 self.chunks.update_last(
101 |last_chunk| {
102 if let Some(first_new_chunk_ref) = first_new_chunk.as_mut() {
103 if last_chunk.0.len() + first_new_chunk_ref.0.len() <= 2 * CHUNK_BASE {
104 last_chunk.0.push_str(&first_new_chunk.take().unwrap().0);
105 } else {
106 let mut text = ArrayString::<{ 4 * CHUNK_BASE }>::new();
107 text.push_str(&last_chunk.0);
108 text.push_str(&first_new_chunk_ref.0);
109 let (left, right) = text.split_at(find_split_ix(&text));
110 last_chunk.0.clear();
111 last_chunk.0.push_str(left);
112 first_new_chunk_ref.0.clear();
113 first_new_chunk_ref.0.push_str(right);
114 }
115 }
116 },
117 &(),
118 );
119
120 self.chunks
121 .extend(first_new_chunk.into_iter().chain(new_chunks), &());
122 self.check_invariants();
123 }
124
125 pub fn push_front(&mut self, text: &str) {
126 let suffix = mem::replace(self, Rope::from(text));
127 self.append(suffix);
128 }
129
130 fn check_invariants(&self) {
131 #[cfg(test)]
132 {
133 // Ensure all chunks except maybe the last one are not underflowing.
134 // Allow some wiggle room for multibyte characters at chunk boundaries.
135 let mut chunks = self.chunks.cursor::<()>().peekable();
136 while let Some(chunk) = chunks.next() {
137 if chunks.peek().is_some() {
138 assert!(chunk.0.len() + 3 >= CHUNK_BASE);
139 }
140 }
141 }
142 }
143
144 pub fn summary(&self) -> TextSummary {
145 self.chunks.summary().text.clone()
146 }
147
148 pub fn len(&self) -> usize {
149 self.chunks.extent(&())
150 }
151
152 pub fn is_empty(&self) -> bool {
153 self.len() == 0
154 }
155
156 pub fn max_point(&self) -> Point {
157 self.chunks.extent(&())
158 }
159
160 pub fn max_point_utf16(&self) -> PointUtf16 {
161 self.chunks.extent(&())
162 }
163
164 pub fn cursor(&self, offset: usize) -> Cursor {
165 Cursor::new(self, offset)
166 }
167
168 pub fn chars(&self) -> impl Iterator<Item = char> + '_ {
169 self.chars_at(0)
170 }
171
172 pub fn chars_at(&self, start: usize) -> impl Iterator<Item = char> + '_ {
173 self.chunks_in_range(start..self.len()).flat_map(str::chars)
174 }
175
176 pub fn reversed_chars_at(&self, start: usize) -> impl Iterator<Item = char> + '_ {
177 self.reversed_chunks_in_range(0..start)
178 .flat_map(|chunk| chunk.chars().rev())
179 }
180
181 pub fn bytes_in_range(&self, range: Range<usize>) -> Bytes {
182 Bytes::new(self, range)
183 }
184
185 pub fn chunks(&self) -> Chunks {
186 self.chunks_in_range(0..self.len())
187 }
188
189 pub fn chunks_in_range(&self, range: Range<usize>) -> Chunks {
190 Chunks::new(self, range, false)
191 }
192
193 pub fn reversed_chunks_in_range(&self, range: Range<usize>) -> Chunks {
194 Chunks::new(self, range, true)
195 }
196
197 pub fn offset_to_offset_utf16(&self, offset: usize) -> OffsetUtf16 {
198 if offset >= self.summary().len {
199 return self.summary().len_utf16;
200 }
201 let mut cursor = self.chunks.cursor::<(usize, OffsetUtf16)>();
202 cursor.seek(&offset, Bias::Left, &());
203 let overshoot = offset - cursor.start().0;
204 cursor.start().1
205 + cursor.item().map_or(Default::default(), |chunk| {
206 chunk.offset_to_offset_utf16(overshoot)
207 })
208 }
209
210 pub fn offset_utf16_to_offset(&self, offset: OffsetUtf16) -> usize {
211 if offset >= self.summary().len_utf16 {
212 return self.summary().len;
213 }
214 let mut cursor = self.chunks.cursor::<(OffsetUtf16, usize)>();
215 cursor.seek(&offset, Bias::Left, &());
216 let overshoot = offset - cursor.start().0;
217 cursor.start().1
218 + cursor.item().map_or(Default::default(), |chunk| {
219 chunk.offset_utf16_to_offset(overshoot)
220 })
221 }
222
223 pub fn offset_to_point(&self, offset: usize) -> Point {
224 if offset >= self.summary().len {
225 return self.summary().lines;
226 }
227 let mut cursor = self.chunks.cursor::<(usize, Point)>();
228 cursor.seek(&offset, Bias::Left, &());
229 let overshoot = offset - cursor.start().0;
230 cursor.start().1
231 + cursor
232 .item()
233 .map_or(Point::zero(), |chunk| chunk.offset_to_point(overshoot))
234 }
235
236 pub fn offset_to_point_utf16(&self, offset: usize) -> PointUtf16 {
237 if offset >= self.summary().len {
238 return self.summary().lines_utf16();
239 }
240 let mut cursor = self.chunks.cursor::<(usize, PointUtf16)>();
241 cursor.seek(&offset, Bias::Left, &());
242 let overshoot = offset - cursor.start().0;
243 cursor.start().1
244 + cursor.item().map_or(PointUtf16::zero(), |chunk| {
245 chunk.offset_to_point_utf16(overshoot)
246 })
247 }
248
249 pub fn point_to_point_utf16(&self, point: Point) -> PointUtf16 {
250 if point >= self.summary().lines {
251 return self.summary().lines_utf16();
252 }
253 let mut cursor = self.chunks.cursor::<(Point, PointUtf16)>();
254 cursor.seek(&point, Bias::Left, &());
255 let overshoot = point - cursor.start().0;
256 cursor.start().1
257 + cursor.item().map_or(PointUtf16::zero(), |chunk| {
258 chunk.point_to_point_utf16(overshoot)
259 })
260 }
261
262 pub fn point_to_offset(&self, point: Point) -> usize {
263 if point >= self.summary().lines {
264 return self.summary().len;
265 }
266 let mut cursor = self.chunks.cursor::<(Point, usize)>();
267 cursor.seek(&point, Bias::Left, &());
268 let overshoot = point - cursor.start().0;
269 cursor.start().1
270 + cursor
271 .item()
272 .map_or(0, |chunk| chunk.point_to_offset(overshoot))
273 }
274
275 pub fn point_utf16_to_offset(&self, point: PointUtf16) -> usize {
276 self.point_utf16_to_offset_impl(point, false)
277 }
278
279 pub fn unclipped_point_utf16_to_offset(&self, point: Unclipped<PointUtf16>) -> usize {
280 self.point_utf16_to_offset_impl(point.0, true)
281 }
282
283 fn point_utf16_to_offset_impl(&self, point: PointUtf16, clip: bool) -> usize {
284 if point >= self.summary().lines_utf16() {
285 return self.summary().len;
286 }
287 let mut cursor = self.chunks.cursor::<(PointUtf16, usize)>();
288 cursor.seek(&point, Bias::Left, &());
289 let overshoot = point - cursor.start().0;
290 cursor.start().1
291 + cursor
292 .item()
293 .map_or(0, |chunk| chunk.point_utf16_to_offset(overshoot, clip))
294 }
295
296 pub fn unclipped_point_utf16_to_point(&self, point: Unclipped<PointUtf16>) -> Point {
297 if point.0 >= self.summary().lines_utf16() {
298 return self.summary().lines;
299 }
300 let mut cursor = self.chunks.cursor::<(PointUtf16, Point)>();
301 cursor.seek(&point.0, Bias::Left, &());
302 let overshoot = Unclipped(point.0 - cursor.start().0);
303 cursor.start().1
304 + cursor.item().map_or(Point::zero(), |chunk| {
305 chunk.unclipped_point_utf16_to_point(overshoot)
306 })
307 }
308
309 pub fn clip_offset(&self, mut offset: usize, bias: Bias) -> usize {
310 let mut cursor = self.chunks.cursor::<usize>();
311 cursor.seek(&offset, Bias::Left, &());
312 if let Some(chunk) = cursor.item() {
313 let mut ix = offset - cursor.start();
314 while !chunk.0.is_char_boundary(ix) {
315 match bias {
316 Bias::Left => {
317 ix -= 1;
318 offset -= 1;
319 }
320 Bias::Right => {
321 ix += 1;
322 offset += 1;
323 }
324 }
325 }
326 offset
327 } else {
328 self.summary().len
329 }
330 }
331
332 pub fn clip_offset_utf16(&self, offset: OffsetUtf16, bias: Bias) -> OffsetUtf16 {
333 let mut cursor = self.chunks.cursor::<OffsetUtf16>();
334 cursor.seek(&offset, Bias::Right, &());
335 if let Some(chunk) = cursor.item() {
336 let overshoot = offset - cursor.start();
337 *cursor.start() + chunk.clip_offset_utf16(overshoot, bias)
338 } else {
339 self.summary().len_utf16
340 }
341 }
342
343 pub fn clip_point(&self, point: Point, bias: Bias) -> Point {
344 let mut cursor = self.chunks.cursor::<Point>();
345 cursor.seek(&point, Bias::Right, &());
346 if let Some(chunk) = cursor.item() {
347 let overshoot = point - cursor.start();
348 *cursor.start() + chunk.clip_point(overshoot, bias)
349 } else {
350 self.summary().lines
351 }
352 }
353
354 pub fn clip_point_utf16(&self, point: Unclipped<PointUtf16>, bias: Bias) -> PointUtf16 {
355 let mut cursor = self.chunks.cursor::<PointUtf16>();
356 cursor.seek(&point.0, Bias::Right, &());
357 if let Some(chunk) = cursor.item() {
358 let overshoot = Unclipped(point.0 - cursor.start());
359 *cursor.start() + chunk.clip_point_utf16(overshoot, bias)
360 } else {
361 self.summary().lines_utf16()
362 }
363 }
364
365 pub fn line_len(&self, row: u32) -> u32 {
366 self.clip_point(Point::new(row, u32::MAX), Bias::Left)
367 .column
368 }
369
370 pub fn fingerprint(&self) -> RopeFingerprint {
371 self.chunks.summary().fingerprint
372 }
373}
374
375impl<'a> From<&'a str> for Rope {
376 fn from(text: &'a str) -> Self {
377 let mut rope = Self::new();
378 rope.push(text);
379 rope
380 }
381}
382
383impl fmt::Display for Rope {
384 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
385 for chunk in self.chunks() {
386 write!(f, "{}", chunk)?;
387 }
388 Ok(())
389 }
390}
391
392impl fmt::Debug for Rope {
393 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
394 use std::fmt::Write as _;
395
396 write!(f, "\"")?;
397 let mut format_string = String::new();
398 for chunk in self.chunks() {
399 write!(&mut format_string, "{:?}", chunk)?;
400 write!(f, "{}", &format_string[1..format_string.len() - 1])?;
401 format_string.clear();
402 }
403 write!(f, "\"")?;
404 Ok(())
405 }
406}
407
408pub struct Cursor<'a> {
409 rope: &'a Rope,
410 chunks: sum_tree::Cursor<'a, Chunk, usize>,
411 offset: usize,
412}
413
414impl<'a> Cursor<'a> {
415 pub fn new(rope: &'a Rope, offset: usize) -> Self {
416 let mut chunks = rope.chunks.cursor();
417 chunks.seek(&offset, Bias::Right, &());
418 Self {
419 rope,
420 chunks,
421 offset,
422 }
423 }
424
425 pub fn seek_forward(&mut self, end_offset: usize) {
426 debug_assert!(end_offset >= self.offset);
427
428 self.chunks.seek_forward(&end_offset, Bias::Right, &());
429 self.offset = end_offset;
430 }
431
432 pub fn slice(&mut self, end_offset: usize) -> Rope {
433 debug_assert!(
434 end_offset >= self.offset,
435 "cannot slice backwards from {} to {}",
436 self.offset,
437 end_offset
438 );
439
440 let mut slice = Rope::new();
441 if let Some(start_chunk) = self.chunks.item() {
442 let start_ix = self.offset - self.chunks.start();
443 let end_ix = cmp::min(end_offset, self.chunks.end(&())) - self.chunks.start();
444 slice.push(&start_chunk.0[start_ix..end_ix]);
445 }
446
447 if end_offset > self.chunks.end(&()) {
448 self.chunks.next(&());
449 slice.append(Rope {
450 chunks: self.chunks.slice(&end_offset, Bias::Right, &()),
451 });
452 if let Some(end_chunk) = self.chunks.item() {
453 let end_ix = end_offset - self.chunks.start();
454 slice.push(&end_chunk.0[..end_ix]);
455 }
456 }
457
458 self.offset = end_offset;
459 slice
460 }
461
462 pub fn summary<D: TextDimension>(&mut self, end_offset: usize) -> D {
463 debug_assert!(end_offset >= self.offset);
464
465 let mut summary = D::default();
466 if let Some(start_chunk) = self.chunks.item() {
467 let start_ix = self.offset - self.chunks.start();
468 let end_ix = cmp::min(end_offset, self.chunks.end(&())) - self.chunks.start();
469 summary.add_assign(&D::from_text_summary(&TextSummary::from(
470 &start_chunk.0[start_ix..end_ix],
471 )));
472 }
473
474 if end_offset > self.chunks.end(&()) {
475 self.chunks.next(&());
476 summary.add_assign(&self.chunks.summary(&end_offset, Bias::Right, &()));
477 if let Some(end_chunk) = self.chunks.item() {
478 let end_ix = end_offset - self.chunks.start();
479 summary.add_assign(&D::from_text_summary(&TextSummary::from(
480 &end_chunk.0[..end_ix],
481 )));
482 }
483 }
484
485 self.offset = end_offset;
486 summary
487 }
488
489 pub fn suffix(mut self) -> Rope {
490 self.slice(self.rope.chunks.extent(&()))
491 }
492
493 pub fn offset(&self) -> usize {
494 self.offset
495 }
496}
497
498pub struct Chunks<'a> {
499 chunks: sum_tree::Cursor<'a, Chunk, usize>,
500 range: Range<usize>,
501 reversed: bool,
502}
503
504impl<'a> Chunks<'a> {
505 pub fn new(rope: &'a Rope, range: Range<usize>, reversed: bool) -> Self {
506 let mut chunks = rope.chunks.cursor();
507 if reversed {
508 chunks.seek(&range.end, Bias::Left, &());
509 } else {
510 chunks.seek(&range.start, Bias::Right, &());
511 }
512 Self {
513 chunks,
514 range,
515 reversed,
516 }
517 }
518
519 pub fn offset(&self) -> usize {
520 if self.reversed {
521 self.range.end.min(self.chunks.end(&()))
522 } else {
523 self.range.start.max(*self.chunks.start())
524 }
525 }
526
527 pub fn seek(&mut self, offset: usize) {
528 let bias = if self.reversed {
529 Bias::Left
530 } else {
531 Bias::Right
532 };
533
534 if offset >= self.chunks.end(&()) {
535 self.chunks.seek_forward(&offset, bias, &());
536 } else {
537 self.chunks.seek(&offset, bias, &());
538 }
539
540 if self.reversed {
541 self.range.end = offset;
542 } else {
543 self.range.start = offset;
544 }
545 }
546
547 pub fn peek(&self) -> Option<&'a str> {
548 let chunk = self.chunks.item()?;
549 if self.reversed && self.range.start >= self.chunks.end(&()) {
550 return None;
551 }
552 let chunk_start = *self.chunks.start();
553 if self.range.end <= chunk_start {
554 return None;
555 }
556
557 let start = self.range.start.saturating_sub(chunk_start);
558 let end = self.range.end - chunk_start;
559 Some(&chunk.0[start..chunk.0.len().min(end)])
560 }
561}
562
563impl<'a> Iterator for Chunks<'a> {
564 type Item = &'a str;
565
566 fn next(&mut self) -> Option<Self::Item> {
567 let result = self.peek();
568 if result.is_some() {
569 if self.reversed {
570 self.chunks.prev(&());
571 } else {
572 self.chunks.next(&());
573 }
574 }
575 result
576 }
577}
578
579pub struct Bytes<'a> {
580 chunks: sum_tree::Cursor<'a, Chunk, usize>,
581 range: Range<usize>,
582}
583
584impl<'a> Bytes<'a> {
585 pub fn new(rope: &'a Rope, range: Range<usize>) -> Self {
586 let mut chunks = rope.chunks.cursor();
587 chunks.seek(&range.start, Bias::Right, &());
588 Self { chunks, range }
589 }
590
591 pub fn peek(&self) -> Option<&'a [u8]> {
592 let chunk = self.chunks.item()?;
593 let chunk_start = *self.chunks.start();
594 if self.range.end <= chunk_start {
595 return None;
596 }
597
598 let start = self.range.start.saturating_sub(chunk_start);
599 let end = self.range.end - chunk_start;
600 Some(&chunk.0.as_bytes()[start..chunk.0.len().min(end)])
601 }
602}
603
604impl<'a> Iterator for Bytes<'a> {
605 type Item = &'a [u8];
606
607 fn next(&mut self) -> Option<Self::Item> {
608 let result = self.peek();
609 if result.is_some() {
610 self.chunks.next(&());
611 }
612 result
613 }
614}
615
616impl<'a> io::Read for Bytes<'a> {
617 fn read(&mut self, buf: &mut [u8]) -> io::Result<usize> {
618 if let Some(chunk) = self.peek() {
619 let len = cmp::min(buf.len(), chunk.len());
620 buf[..len].copy_from_slice(&chunk[..len]);
621 self.range.start += len;
622 if len == chunk.len() {
623 self.chunks.next(&());
624 }
625 Ok(len)
626 } else {
627 Ok(0)
628 }
629 }
630}
631
632#[derive(Clone, Debug, Default)]
633struct Chunk(ArrayString<{ 2 * CHUNK_BASE }>);
634
635impl Chunk {
636 fn offset_to_offset_utf16(&self, target: usize) -> OffsetUtf16 {
637 let mut offset = 0;
638 let mut offset_utf16 = OffsetUtf16(0);
639 for ch in self.0.chars() {
640 if offset >= target {
641 break;
642 }
643
644 offset += ch.len_utf8();
645 offset_utf16.0 += ch.len_utf16();
646 }
647 offset_utf16
648 }
649
650 fn offset_utf16_to_offset(&self, target: OffsetUtf16) -> usize {
651 let mut offset_utf16 = OffsetUtf16(0);
652 let mut offset = 0;
653 for ch in self.0.chars() {
654 if offset_utf16 >= target {
655 break;
656 }
657
658 offset += ch.len_utf8();
659 offset_utf16.0 += ch.len_utf16();
660 }
661 offset
662 }
663
664 fn offset_to_point(&self, target: usize) -> Point {
665 let mut offset = 0;
666 let mut point = Point::new(0, 0);
667 for ch in self.0.chars() {
668 if offset >= target {
669 break;
670 }
671
672 if ch == '\n' {
673 point.row += 1;
674 point.column = 0;
675 } else {
676 point.column += ch.len_utf8() as u32;
677 }
678 offset += ch.len_utf8();
679 }
680 point
681 }
682
683 fn offset_to_point_utf16(&self, target: usize) -> PointUtf16 {
684 let mut offset = 0;
685 let mut point = PointUtf16::new(0, 0);
686 for ch in self.0.chars() {
687 if offset >= target {
688 break;
689 }
690
691 if ch == '\n' {
692 point.row += 1;
693 point.column = 0;
694 } else {
695 point.column += ch.len_utf16() as u32;
696 }
697 offset += ch.len_utf8();
698 }
699 point
700 }
701
702 fn point_to_offset(&self, target: Point) -> usize {
703 let mut offset = 0;
704 let mut point = Point::new(0, 0);
705
706 for ch in self.0.chars() {
707 if point >= target {
708 if point > target {
709 debug_panic!("point {target:?} is inside of character {ch:?}");
710 }
711 break;
712 }
713
714 if ch == '\n' {
715 point.row += 1;
716 point.column = 0;
717
718 if point.row > target.row {
719 debug_panic!(
720 "point {target:?} is beyond the end of a line with length {}",
721 point.column
722 );
723 break;
724 }
725 } else {
726 point.column += ch.len_utf8() as u32;
727 }
728
729 offset += ch.len_utf8();
730 }
731
732 offset
733 }
734
735 fn point_to_point_utf16(&self, target: Point) -> PointUtf16 {
736 let mut point = Point::zero();
737 let mut point_utf16 = PointUtf16::new(0, 0);
738 for ch in self.0.chars() {
739 if point >= target {
740 break;
741 }
742
743 if ch == '\n' {
744 point_utf16.row += 1;
745 point_utf16.column = 0;
746 point.row += 1;
747 point.column = 0;
748 } else {
749 point_utf16.column += ch.len_utf16() as u32;
750 point.column += ch.len_utf8() as u32;
751 }
752 }
753 point_utf16
754 }
755
756 fn point_utf16_to_offset(&self, target: PointUtf16, clip: bool) -> usize {
757 let mut offset = 0;
758 let mut point = PointUtf16::new(0, 0);
759
760 for ch in self.0.chars() {
761 if point == target {
762 break;
763 }
764
765 if ch == '\n' {
766 point.row += 1;
767 point.column = 0;
768
769 if point.row > target.row {
770 if !clip {
771 debug_panic!(
772 "point {target:?} is beyond the end of a line with length {}",
773 point.column
774 );
775 }
776 // Return the offset of the newline
777 return offset;
778 }
779 } else {
780 point.column += ch.len_utf16() as u32;
781 }
782
783 if point > target {
784 if !clip {
785 debug_panic!("point {target:?} is inside of codepoint {ch:?}");
786 }
787 // Return the offset of the codepoint which we have landed within, bias left
788 return offset;
789 }
790
791 offset += ch.len_utf8();
792 }
793
794 offset
795 }
796
797 fn unclipped_point_utf16_to_point(&self, target: Unclipped<PointUtf16>) -> Point {
798 let mut point = Point::zero();
799 let mut point_utf16 = PointUtf16::zero();
800
801 for ch in self.0.chars() {
802 if point_utf16 == target.0 {
803 break;
804 }
805
806 if point_utf16 > target.0 {
807 // If the point is past the end of a line or inside of a code point,
808 // return the last valid point before the target.
809 return point;
810 }
811
812 if ch == '\n' {
813 point_utf16 += PointUtf16::new(1, 0);
814 point += Point::new(1, 0);
815 } else {
816 point_utf16 += PointUtf16::new(0, ch.len_utf16() as u32);
817 point += Point::new(0, ch.len_utf8() as u32);
818 }
819 }
820
821 point
822 }
823
824 fn clip_point(&self, target: Point, bias: Bias) -> Point {
825 for (row, line) in self.0.split('\n').enumerate() {
826 if row == target.row as usize {
827 let mut column = target.column.min(line.len() as u32);
828 while !line.is_char_boundary(column as usize) {
829 match bias {
830 Bias::Left => column -= 1,
831 Bias::Right => column += 1,
832 }
833 }
834 return Point::new(row as u32, column);
835 }
836 }
837 unreachable!()
838 }
839
840 fn clip_point_utf16(&self, target: Unclipped<PointUtf16>, bias: Bias) -> PointUtf16 {
841 for (row, line) in self.0.split('\n').enumerate() {
842 if row == target.0.row as usize {
843 let mut code_units = line.encode_utf16();
844 let mut column = code_units.by_ref().take(target.0.column as usize).count();
845 if char::decode_utf16(code_units).next().transpose().is_err() {
846 match bias {
847 Bias::Left => column -= 1,
848 Bias::Right => column += 1,
849 }
850 }
851 return PointUtf16::new(row as u32, column as u32);
852 }
853 }
854 unreachable!()
855 }
856
857 fn clip_offset_utf16(&self, target: OffsetUtf16, bias: Bias) -> OffsetUtf16 {
858 let mut code_units = self.0.encode_utf16();
859 let mut offset = code_units.by_ref().take(target.0 as usize).count();
860 if char::decode_utf16(code_units).next().transpose().is_err() {
861 match bias {
862 Bias::Left => offset -= 1,
863 Bias::Right => offset += 1,
864 }
865 }
866 OffsetUtf16(offset)
867 }
868}
869
870impl sum_tree::Item for Chunk {
871 type Summary = ChunkSummary;
872
873 fn summary(&self) -> Self::Summary {
874 ChunkSummary::from(self.0.as_str())
875 }
876}
877
878#[derive(Clone, Debug, Default, Eq, PartialEq)]
879pub struct ChunkSummary {
880 text: TextSummary,
881 fingerprint: RopeFingerprint,
882}
883
884impl<'a> From<&'a str> for ChunkSummary {
885 fn from(text: &'a str) -> Self {
886 Self {
887 text: TextSummary::from(text),
888 fingerprint: bromberg_sl2::hash_strict(text.as_bytes()),
889 }
890 }
891}
892
893impl sum_tree::Summary for ChunkSummary {
894 type Context = ();
895
896 fn add_summary(&mut self, summary: &Self, _: &()) {
897 self.text += &summary.text;
898 self.fingerprint = self.fingerprint * summary.fingerprint;
899 }
900}
901
902#[derive(Clone, Debug, Default, Eq, PartialEq)]
903pub struct TextSummary {
904 pub len: usize,
905 pub len_utf16: OffsetUtf16,
906 pub lines: Point,
907 pub first_line_chars: u32,
908 pub last_line_chars: u32,
909 pub last_line_len_utf16: u32,
910 pub longest_row: u32,
911 pub longest_row_chars: u32,
912}
913
914impl TextSummary {
915 pub fn lines_utf16(&self) -> PointUtf16 {
916 PointUtf16 {
917 row: self.lines.row,
918 column: self.last_line_len_utf16,
919 }
920 }
921}
922
923impl<'a> From<&'a str> for TextSummary {
924 fn from(text: &'a str) -> Self {
925 let mut len_utf16 = OffsetUtf16(0);
926 let mut lines = Point::new(0, 0);
927 let mut first_line_chars = 0;
928 let mut last_line_chars = 0;
929 let mut last_line_len_utf16 = 0;
930 let mut longest_row = 0;
931 let mut longest_row_chars = 0;
932 for c in text.chars() {
933 len_utf16.0 += c.len_utf16();
934
935 if c == '\n' {
936 lines += Point::new(1, 0);
937 last_line_len_utf16 = 0;
938 last_line_chars = 0;
939 } else {
940 lines.column += c.len_utf8() as u32;
941 last_line_len_utf16 += c.len_utf16() as u32;
942 last_line_chars += 1;
943 }
944
945 if lines.row == 0 {
946 first_line_chars = last_line_chars;
947 }
948
949 if last_line_chars > longest_row_chars {
950 longest_row = lines.row;
951 longest_row_chars = last_line_chars;
952 }
953 }
954
955 TextSummary {
956 len: text.len(),
957 len_utf16,
958 lines,
959 first_line_chars,
960 last_line_chars,
961 last_line_len_utf16,
962 longest_row,
963 longest_row_chars,
964 }
965 }
966}
967
968impl sum_tree::Summary for TextSummary {
969 type Context = ();
970
971 fn add_summary(&mut self, summary: &Self, _: &Self::Context) {
972 *self += summary;
973 }
974}
975
976impl std::ops::Add<Self> for TextSummary {
977 type Output = Self;
978
979 fn add(mut self, rhs: Self) -> Self::Output {
980 AddAssign::add_assign(&mut self, &rhs);
981 self
982 }
983}
984
985impl<'a> std::ops::AddAssign<&'a Self> for TextSummary {
986 fn add_assign(&mut self, other: &'a Self) {
987 let joined_chars = self.last_line_chars + other.first_line_chars;
988 if joined_chars > self.longest_row_chars {
989 self.longest_row = self.lines.row;
990 self.longest_row_chars = joined_chars;
991 }
992 if other.longest_row_chars > self.longest_row_chars {
993 self.longest_row = self.lines.row + other.longest_row;
994 self.longest_row_chars = other.longest_row_chars;
995 }
996
997 if self.lines.row == 0 {
998 self.first_line_chars += other.first_line_chars;
999 }
1000
1001 if other.lines.row == 0 {
1002 self.last_line_chars += other.first_line_chars;
1003 self.last_line_len_utf16 += other.last_line_len_utf16;
1004 } else {
1005 self.last_line_chars = other.last_line_chars;
1006 self.last_line_len_utf16 = other.last_line_len_utf16;
1007 }
1008
1009 self.len += other.len;
1010 self.len_utf16 += other.len_utf16;
1011 self.lines += other.lines;
1012 }
1013}
1014
1015impl std::ops::AddAssign<Self> for TextSummary {
1016 fn add_assign(&mut self, other: Self) {
1017 *self += &other;
1018 }
1019}
1020
1021pub trait TextDimension: 'static + for<'a> Dimension<'a, ChunkSummary> {
1022 fn from_text_summary(summary: &TextSummary) -> Self;
1023 fn add_assign(&mut self, other: &Self);
1024}
1025
1026impl<D1: TextDimension, D2: TextDimension> TextDimension for (D1, D2) {
1027 fn from_text_summary(summary: &TextSummary) -> Self {
1028 (
1029 D1::from_text_summary(summary),
1030 D2::from_text_summary(summary),
1031 )
1032 }
1033
1034 fn add_assign(&mut self, other: &Self) {
1035 self.0.add_assign(&other.0);
1036 self.1.add_assign(&other.1);
1037 }
1038}
1039
1040impl<'a> sum_tree::Dimension<'a, ChunkSummary> for TextSummary {
1041 fn add_summary(&mut self, summary: &'a ChunkSummary, _: &()) {
1042 *self += &summary.text;
1043 }
1044}
1045
1046impl TextDimension for TextSummary {
1047 fn from_text_summary(summary: &TextSummary) -> Self {
1048 summary.clone()
1049 }
1050
1051 fn add_assign(&mut self, other: &Self) {
1052 *self += other;
1053 }
1054}
1055
1056impl<'a> sum_tree::Dimension<'a, ChunkSummary> for usize {
1057 fn add_summary(&mut self, summary: &'a ChunkSummary, _: &()) {
1058 *self += summary.text.len;
1059 }
1060}
1061
1062impl TextDimension for usize {
1063 fn from_text_summary(summary: &TextSummary) -> Self {
1064 summary.len
1065 }
1066
1067 fn add_assign(&mut self, other: &Self) {
1068 *self += other;
1069 }
1070}
1071
1072impl<'a> sum_tree::Dimension<'a, ChunkSummary> for OffsetUtf16 {
1073 fn add_summary(&mut self, summary: &'a ChunkSummary, _: &()) {
1074 *self += summary.text.len_utf16;
1075 }
1076}
1077
1078impl TextDimension for OffsetUtf16 {
1079 fn from_text_summary(summary: &TextSummary) -> Self {
1080 summary.len_utf16
1081 }
1082
1083 fn add_assign(&mut self, other: &Self) {
1084 *self += other;
1085 }
1086}
1087
1088impl<'a> sum_tree::Dimension<'a, ChunkSummary> for Point {
1089 fn add_summary(&mut self, summary: &'a ChunkSummary, _: &()) {
1090 *self += summary.text.lines;
1091 }
1092}
1093
1094impl TextDimension for Point {
1095 fn from_text_summary(summary: &TextSummary) -> Self {
1096 summary.lines
1097 }
1098
1099 fn add_assign(&mut self, other: &Self) {
1100 *self += other;
1101 }
1102}
1103
1104impl<'a> sum_tree::Dimension<'a, ChunkSummary> for PointUtf16 {
1105 fn add_summary(&mut self, summary: &'a ChunkSummary, _: &()) {
1106 *self += summary.text.lines_utf16();
1107 }
1108}
1109
1110impl TextDimension for PointUtf16 {
1111 fn from_text_summary(summary: &TextSummary) -> Self {
1112 summary.lines_utf16()
1113 }
1114
1115 fn add_assign(&mut self, other: &Self) {
1116 *self += other;
1117 }
1118}
1119
1120fn find_split_ix(text: &str) -> usize {
1121 let mut ix = text.len() / 2;
1122 while !text.is_char_boundary(ix) {
1123 if ix < 2 * CHUNK_BASE {
1124 ix += 1;
1125 } else {
1126 ix = (text.len() / 2) - 1;
1127 break;
1128 }
1129 }
1130 while !text.is_char_boundary(ix) {
1131 ix -= 1;
1132 }
1133
1134 debug_assert!(ix <= 2 * CHUNK_BASE);
1135 debug_assert!(text.len() - ix <= 2 * CHUNK_BASE);
1136 ix
1137}
1138
1139#[cfg(test)]
1140mod tests {
1141 use super::*;
1142 use rand::prelude::*;
1143 use std::{cmp::Ordering, env, io::Read};
1144 use util::RandomCharIter;
1145 use Bias::{Left, Right};
1146
1147 #[test]
1148 fn test_all_4_byte_chars() {
1149 let mut rope = Rope::new();
1150 let text = "🏀".repeat(256);
1151 rope.push(&text);
1152 assert_eq!(rope.text(), text);
1153 }
1154
1155 #[test]
1156 fn test_clip() {
1157 let rope = Rope::from("🧘");
1158
1159 assert_eq!(rope.clip_offset(1, Bias::Left), 0);
1160 assert_eq!(rope.clip_offset(1, Bias::Right), 4);
1161 assert_eq!(rope.clip_offset(5, Bias::Right), 4);
1162
1163 assert_eq!(
1164 rope.clip_point(Point::new(0, 1), Bias::Left),
1165 Point::new(0, 0)
1166 );
1167 assert_eq!(
1168 rope.clip_point(Point::new(0, 1), Bias::Right),
1169 Point::new(0, 4)
1170 );
1171 assert_eq!(
1172 rope.clip_point(Point::new(0, 5), Bias::Right),
1173 Point::new(0, 4)
1174 );
1175
1176 assert_eq!(
1177 rope.clip_point_utf16(Unclipped(PointUtf16::new(0, 1)), Bias::Left),
1178 PointUtf16::new(0, 0)
1179 );
1180 assert_eq!(
1181 rope.clip_point_utf16(Unclipped(PointUtf16::new(0, 1)), Bias::Right),
1182 PointUtf16::new(0, 2)
1183 );
1184 assert_eq!(
1185 rope.clip_point_utf16(Unclipped(PointUtf16::new(0, 3)), Bias::Right),
1186 PointUtf16::new(0, 2)
1187 );
1188
1189 assert_eq!(
1190 rope.clip_offset_utf16(OffsetUtf16(1), Bias::Left),
1191 OffsetUtf16(0)
1192 );
1193 assert_eq!(
1194 rope.clip_offset_utf16(OffsetUtf16(1), Bias::Right),
1195 OffsetUtf16(2)
1196 );
1197 assert_eq!(
1198 rope.clip_offset_utf16(OffsetUtf16(3), Bias::Right),
1199 OffsetUtf16(2)
1200 );
1201 }
1202
1203 #[gpui::test(iterations = 100)]
1204 fn test_random_rope(mut rng: StdRng) {
1205 let operations = env::var("OPERATIONS")
1206 .map(|i| i.parse().expect("invalid `OPERATIONS` variable"))
1207 .unwrap_or(10);
1208
1209 let mut expected = String::new();
1210 let mut actual = Rope::new();
1211 for _ in 0..operations {
1212 let end_ix = clip_offset(&expected, rng.gen_range(0..=expected.len()), Right);
1213 let start_ix = clip_offset(&expected, rng.gen_range(0..=end_ix), Left);
1214 let len = rng.gen_range(0..=64);
1215 let new_text: String = RandomCharIter::new(&mut rng).take(len).collect();
1216
1217 let mut new_actual = Rope::new();
1218 let mut cursor = actual.cursor(0);
1219 new_actual.append(cursor.slice(start_ix));
1220 new_actual.push(&new_text);
1221 cursor.seek_forward(end_ix);
1222 new_actual.append(cursor.suffix());
1223 actual = new_actual;
1224
1225 expected.replace_range(start_ix..end_ix, &new_text);
1226
1227 assert_eq!(actual.text(), expected);
1228 log::info!("text: {:?}", expected);
1229
1230 for _ in 0..5 {
1231 let end_ix = clip_offset(&expected, rng.gen_range(0..=expected.len()), Right);
1232 let start_ix = clip_offset(&expected, rng.gen_range(0..=end_ix), Left);
1233
1234 let actual_text = actual.chunks_in_range(start_ix..end_ix).collect::<String>();
1235 assert_eq!(actual_text, &expected[start_ix..end_ix]);
1236
1237 let mut actual_text = String::new();
1238 actual
1239 .bytes_in_range(start_ix..end_ix)
1240 .read_to_string(&mut actual_text)
1241 .unwrap();
1242 assert_eq!(actual_text, &expected[start_ix..end_ix]);
1243
1244 assert_eq!(
1245 actual
1246 .reversed_chunks_in_range(start_ix..end_ix)
1247 .collect::<Vec<&str>>()
1248 .into_iter()
1249 .rev()
1250 .collect::<String>(),
1251 &expected[start_ix..end_ix]
1252 );
1253 }
1254
1255 let mut offset_utf16 = OffsetUtf16(0);
1256 let mut point = Point::new(0, 0);
1257 let mut point_utf16 = PointUtf16::new(0, 0);
1258 for (ix, ch) in expected.char_indices().chain(Some((expected.len(), '\0'))) {
1259 assert_eq!(actual.offset_to_point(ix), point, "offset_to_point({})", ix);
1260 assert_eq!(
1261 actual.offset_to_point_utf16(ix),
1262 point_utf16,
1263 "offset_to_point_utf16({})",
1264 ix
1265 );
1266 assert_eq!(
1267 actual.point_to_offset(point),
1268 ix,
1269 "point_to_offset({:?})",
1270 point
1271 );
1272 assert_eq!(
1273 actual.point_utf16_to_offset(point_utf16),
1274 ix,
1275 "point_utf16_to_offset({:?})",
1276 point_utf16
1277 );
1278 assert_eq!(
1279 actual.offset_to_offset_utf16(ix),
1280 offset_utf16,
1281 "offset_to_offset_utf16({:?})",
1282 ix
1283 );
1284 assert_eq!(
1285 actual.offset_utf16_to_offset(offset_utf16),
1286 ix,
1287 "offset_utf16_to_offset({:?})",
1288 offset_utf16
1289 );
1290 if ch == '\n' {
1291 point += Point::new(1, 0);
1292 point_utf16 += PointUtf16::new(1, 0);
1293 } else {
1294 point.column += ch.len_utf8() as u32;
1295 point_utf16.column += ch.len_utf16() as u32;
1296 }
1297 offset_utf16.0 += ch.len_utf16();
1298 }
1299
1300 let mut offset_utf16 = OffsetUtf16(0);
1301 let mut point_utf16 = Unclipped(PointUtf16::zero());
1302 for unit in expected.encode_utf16() {
1303 let left_offset = actual.clip_offset_utf16(offset_utf16, Bias::Left);
1304 let right_offset = actual.clip_offset_utf16(offset_utf16, Bias::Right);
1305 assert!(right_offset >= left_offset);
1306 // Ensure translating UTF-16 offsets to UTF-8 offsets doesn't panic.
1307 actual.offset_utf16_to_offset(left_offset);
1308 actual.offset_utf16_to_offset(right_offset);
1309
1310 let left_point = actual.clip_point_utf16(point_utf16, Bias::Left);
1311 let right_point = actual.clip_point_utf16(point_utf16, Bias::Right);
1312 assert!(right_point >= left_point);
1313 // Ensure translating valid UTF-16 points to offsets doesn't panic.
1314 actual.point_utf16_to_offset(left_point);
1315 actual.point_utf16_to_offset(right_point);
1316
1317 offset_utf16.0 += 1;
1318 if unit == b'\n' as u16 {
1319 point_utf16.0 += PointUtf16::new(1, 0);
1320 } else {
1321 point_utf16.0 += PointUtf16::new(0, 1);
1322 }
1323 }
1324
1325 for _ in 0..5 {
1326 let end_ix = clip_offset(&expected, rng.gen_range(0..=expected.len()), Right);
1327 let start_ix = clip_offset(&expected, rng.gen_range(0..=end_ix), Left);
1328 assert_eq!(
1329 actual.cursor(start_ix).summary::<TextSummary>(end_ix),
1330 TextSummary::from(&expected[start_ix..end_ix])
1331 );
1332 }
1333
1334 let mut expected_longest_rows = Vec::new();
1335 let mut longest_line_len = -1_isize;
1336 for (row, line) in expected.split('\n').enumerate() {
1337 let row = row as u32;
1338 assert_eq!(
1339 actual.line_len(row),
1340 line.len() as u32,
1341 "invalid line len for row {}",
1342 row
1343 );
1344
1345 let line_char_count = line.chars().count() as isize;
1346 match line_char_count.cmp(&longest_line_len) {
1347 Ordering::Less => {}
1348 Ordering::Equal => expected_longest_rows.push(row),
1349 Ordering::Greater => {
1350 longest_line_len = line_char_count;
1351 expected_longest_rows.clear();
1352 expected_longest_rows.push(row);
1353 }
1354 }
1355 }
1356
1357 let longest_row = actual.summary().longest_row;
1358 assert!(
1359 expected_longest_rows.contains(&longest_row),
1360 "incorrect longest row {}. expected {:?} with length {}",
1361 longest_row,
1362 expected_longest_rows,
1363 longest_line_len,
1364 );
1365 }
1366 }
1367
1368 fn clip_offset(text: &str, mut offset: usize, bias: Bias) -> usize {
1369 while !text.is_char_boundary(offset) {
1370 match bias {
1371 Bias::Left => offset -= 1,
1372 Bias::Right => offset += 1,
1373 }
1374 }
1375 offset
1376 }
1377
1378 impl Rope {
1379 fn text(&self) -> String {
1380 let mut text = String::new();
1381 for chunk in self.chunks.cursor::<()>() {
1382 text.push_str(&chunk.0);
1383 }
1384 text
1385 }
1386 }
1387}