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