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