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