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 OffsetUtf16(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.0 >= 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_point(&self, point: Point, bias: Bias) -> Point {
295 let mut cursor = self.chunks.cursor::<Point>();
296 cursor.seek(&point, Bias::Right, &());
297 if let Some(chunk) = cursor.item() {
298 let overshoot = point - cursor.start();
299 *cursor.start() + chunk.clip_point(overshoot, bias)
300 } else {
301 self.summary().lines
302 }
303 }
304
305 pub fn clip_point_utf16(&self, point: PointUtf16, bias: Bias) -> PointUtf16 {
306 let mut cursor = self.chunks.cursor::<PointUtf16>();
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_utf16(overshoot, bias)
311 } else {
312 self.summary().lines_utf16
313 }
314 }
315
316 pub fn line_len(&self, row: u32) -> u32 {
317 self.clip_point(Point::new(row, u32::MAX), Bias::Left)
318 .column
319 }
320
321 pub fn fingerprint(&self) -> String {
322 self.chunks.summary().fingerprint.to_hex()
323 }
324}
325
326impl<'a> From<&'a str> for Rope {
327 fn from(text: &'a str) -> Self {
328 let mut rope = Self::new();
329 rope.push(text);
330 rope
331 }
332}
333
334impl fmt::Display for Rope {
335 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
336 for chunk in self.chunks() {
337 write!(f, "{}", chunk)?;
338 }
339 Ok(())
340 }
341}
342
343pub struct Cursor<'a> {
344 rope: &'a Rope,
345 chunks: sum_tree::Cursor<'a, Chunk, usize>,
346 offset: usize,
347}
348
349impl<'a> Cursor<'a> {
350 pub fn new(rope: &'a Rope, offset: usize) -> Self {
351 let mut chunks = rope.chunks.cursor();
352 chunks.seek(&offset, Bias::Right, &());
353 Self {
354 rope,
355 chunks,
356 offset,
357 }
358 }
359
360 pub fn seek_forward(&mut self, end_offset: usize) {
361 debug_assert!(end_offset >= self.offset);
362
363 self.chunks.seek_forward(&end_offset, Bias::Right, &());
364 self.offset = end_offset;
365 }
366
367 pub fn slice(&mut self, end_offset: usize) -> Rope {
368 debug_assert!(
369 end_offset >= self.offset,
370 "cannot slice backwards from {} to {}",
371 self.offset,
372 end_offset
373 );
374
375 let mut slice = Rope::new();
376 if let Some(start_chunk) = self.chunks.item() {
377 let start_ix = self.offset - self.chunks.start();
378 let end_ix = cmp::min(end_offset, self.chunks.end(&())) - self.chunks.start();
379 slice.push(&start_chunk.0[start_ix..end_ix]);
380 }
381
382 if end_offset > self.chunks.end(&()) {
383 self.chunks.next(&());
384 slice.append(Rope {
385 chunks: self.chunks.slice(&end_offset, Bias::Right, &()),
386 });
387 if let Some(end_chunk) = self.chunks.item() {
388 let end_ix = end_offset - self.chunks.start();
389 slice.push(&end_chunk.0[..end_ix]);
390 }
391 }
392
393 self.offset = end_offset;
394 slice
395 }
396
397 pub fn summary<D: TextDimension>(&mut self, end_offset: usize) -> D {
398 debug_assert!(end_offset >= self.offset);
399
400 let mut summary = D::default();
401 if let Some(start_chunk) = self.chunks.item() {
402 let start_ix = self.offset - self.chunks.start();
403 let end_ix = cmp::min(end_offset, self.chunks.end(&())) - self.chunks.start();
404 summary.add_assign(&D::from_text_summary(&TextSummary::from(
405 &start_chunk.0[start_ix..end_ix],
406 )));
407 }
408
409 if end_offset > self.chunks.end(&()) {
410 self.chunks.next(&());
411 summary.add_assign(&self.chunks.summary(&end_offset, Bias::Right, &()));
412 if let Some(end_chunk) = self.chunks.item() {
413 let end_ix = end_offset - self.chunks.start();
414 summary.add_assign(&D::from_text_summary(&TextSummary::from(
415 &end_chunk.0[..end_ix],
416 )));
417 }
418 }
419
420 self.offset = end_offset;
421 summary
422 }
423
424 pub fn suffix(mut self) -> Rope {
425 self.slice(self.rope.chunks.extent(&()))
426 }
427
428 pub fn offset(&self) -> usize {
429 self.offset
430 }
431}
432
433pub struct Chunks<'a> {
434 chunks: sum_tree::Cursor<'a, Chunk, usize>,
435 range: Range<usize>,
436 reversed: bool,
437}
438
439impl<'a> Chunks<'a> {
440 pub fn new(rope: &'a Rope, range: Range<usize>, reversed: bool) -> Self {
441 let mut chunks = rope.chunks.cursor();
442 if reversed {
443 chunks.seek(&range.end, Bias::Left, &());
444 } else {
445 chunks.seek(&range.start, Bias::Right, &());
446 }
447 Self {
448 chunks,
449 range,
450 reversed,
451 }
452 }
453
454 pub fn offset(&self) -> usize {
455 if self.reversed {
456 self.range.end.min(self.chunks.end(&()))
457 } else {
458 self.range.start.max(*self.chunks.start())
459 }
460 }
461
462 pub fn seek(&mut self, offset: usize) {
463 let bias = if self.reversed {
464 Bias::Left
465 } else {
466 Bias::Right
467 };
468
469 if offset >= self.chunks.end(&()) {
470 self.chunks.seek_forward(&offset, bias, &());
471 } else {
472 self.chunks.seek(&offset, bias, &());
473 }
474
475 if self.reversed {
476 self.range.end = offset;
477 } else {
478 self.range.start = offset;
479 }
480 }
481
482 pub fn peek(&self) -> Option<&'a str> {
483 let chunk = self.chunks.item()?;
484 if self.reversed && self.range.start >= self.chunks.end(&()) {
485 return None;
486 }
487 let chunk_start = *self.chunks.start();
488 if self.range.end <= chunk_start {
489 return None;
490 }
491
492 let start = self.range.start.saturating_sub(chunk_start);
493 let end = self.range.end - chunk_start;
494 Some(&chunk.0[start..chunk.0.len().min(end)])
495 }
496}
497
498impl<'a> Iterator for Chunks<'a> {
499 type Item = &'a str;
500
501 fn next(&mut self) -> Option<Self::Item> {
502 let result = self.peek();
503 if result.is_some() {
504 if self.reversed {
505 self.chunks.prev(&());
506 } else {
507 self.chunks.next(&());
508 }
509 }
510 result
511 }
512}
513
514pub struct Bytes<'a> {
515 chunks: sum_tree::Cursor<'a, Chunk, usize>,
516 range: Range<usize>,
517}
518
519impl<'a> Bytes<'a> {
520 pub fn new(rope: &'a Rope, range: Range<usize>) -> Self {
521 let mut chunks = rope.chunks.cursor();
522 chunks.seek(&range.start, Bias::Right, &());
523 Self { chunks, range }
524 }
525
526 pub fn peek(&self) -> Option<&'a [u8]> {
527 let chunk = self.chunks.item()?;
528 let chunk_start = *self.chunks.start();
529 if self.range.end <= chunk_start {
530 return None;
531 }
532
533 let start = self.range.start.saturating_sub(chunk_start);
534 let end = self.range.end - chunk_start;
535 Some(&chunk.0.as_bytes()[start..chunk.0.len().min(end)])
536 }
537}
538
539impl<'a> Iterator for Bytes<'a> {
540 type Item = &'a [u8];
541
542 fn next(&mut self) -> Option<Self::Item> {
543 let result = self.peek();
544 if result.is_some() {
545 self.chunks.next(&());
546 }
547 result
548 }
549}
550
551impl<'a> io::Read for Bytes<'a> {
552 fn read(&mut self, buf: &mut [u8]) -> io::Result<usize> {
553 if let Some(chunk) = self.peek() {
554 let len = cmp::min(buf.len(), chunk.len());
555 buf[..len].copy_from_slice(&chunk[..len]);
556 self.range.start += len;
557 if len == chunk.len() {
558 self.chunks.next(&());
559 }
560 Ok(len)
561 } else {
562 Ok(0)
563 }
564 }
565}
566
567#[derive(Clone, Debug, Default)]
568struct Chunk(ArrayString<{ 2 * CHUNK_BASE }>);
569
570impl Chunk {
571 fn offset_to_offset_utf16(&self, target: usize) -> OffsetUtf16 {
572 let mut offset = 0;
573 let mut offset_utf16 = OffsetUtf16(0);
574 for ch in self.0.chars() {
575 if offset >= target {
576 break;
577 }
578
579 offset += ch.len_utf8();
580 offset_utf16.0 += ch.len_utf16();
581 }
582 offset_utf16
583 }
584
585 fn offset_utf16_to_offset(&self, target: OffsetUtf16) -> usize {
586 let mut offset_utf16 = OffsetUtf16(0);
587 let mut offset = 0;
588 for ch in self.0.chars() {
589 if offset_utf16 >= target {
590 break;
591 }
592
593 offset += ch.len_utf8();
594 offset_utf16.0 += ch.len_utf16();
595 }
596 offset
597 }
598
599 fn offset_to_point(&self, target: usize) -> Point {
600 let mut offset = 0;
601 let mut point = Point::new(0, 0);
602 for ch in self.0.chars() {
603 if offset >= target {
604 break;
605 }
606
607 if ch == '\n' {
608 point.row += 1;
609 point.column = 0;
610 } else {
611 point.column += ch.len_utf8() as u32;
612 }
613 offset += ch.len_utf8();
614 }
615 point
616 }
617
618 fn offset_to_point_utf16(&self, target: usize) -> PointUtf16 {
619 let mut offset = 0;
620 let mut point = PointUtf16::new(0, 0);
621 for ch in self.0.chars() {
622 if offset >= target {
623 break;
624 }
625
626 if ch == '\n' {
627 point.row += 1;
628 point.column = 0;
629 } else {
630 point.column += ch.len_utf16() as u32;
631 }
632 offset += ch.len_utf8();
633 }
634 point
635 }
636
637 fn point_to_offset(&self, target: Point) -> usize {
638 let mut offset = 0;
639 let mut point = Point::new(0, 0);
640 for ch in self.0.chars() {
641 if point >= target {
642 if point > target {
643 panic!("point {:?} is inside of character {:?}", target, ch);
644 }
645 break;
646 }
647
648 if ch == '\n' {
649 point.row += 1;
650 if point.row > target.row {
651 panic!(
652 "point {:?} is beyond the end of a line with length {}",
653 target, point.column
654 );
655 }
656 point.column = 0;
657 } else {
658 point.column += ch.len_utf8() as u32;
659 }
660 offset += ch.len_utf8();
661 }
662 offset
663 }
664
665 fn point_to_point_utf16(&self, target: Point) -> PointUtf16 {
666 let mut point = Point::zero();
667 let mut point_utf16 = PointUtf16::new(0, 0);
668 for ch in self.0.chars() {
669 if point >= target {
670 break;
671 }
672
673 if ch == '\n' {
674 point_utf16.row += 1;
675 point_utf16.column = 0;
676 point.row += 1;
677 point.column = 0;
678 } else {
679 point_utf16.column += ch.len_utf16() as u32;
680 point.column += ch.len_utf8() as u32;
681 }
682 }
683 point_utf16
684 }
685
686 fn point_utf16_to_offset(&self, target: PointUtf16) -> usize {
687 let mut offset = 0;
688 let mut point = PointUtf16::new(0, 0);
689 for ch in self.0.chars() {
690 if point >= target {
691 if point > target {
692 panic!("point {:?} is inside of character {:?}", target, ch);
693 }
694 break;
695 }
696
697 if ch == '\n' {
698 point.row += 1;
699 if point.row > target.row {
700 panic!(
701 "point {:?} is beyond the end of a line with length {}",
702 target, point.column
703 );
704 }
705 point.column = 0;
706 } else {
707 point.column += ch.len_utf16() as u32;
708 }
709 offset += ch.len_utf8();
710 }
711 offset
712 }
713
714 fn point_utf16_to_point(&self, target: PointUtf16) -> Point {
715 let mut point = Point::zero();
716 let mut point_utf16 = PointUtf16::zero();
717 for ch in self.0.chars() {
718 if point_utf16 >= target {
719 if point_utf16 > target {
720 panic!("point {:?} is inside of character {:?}", target, ch);
721 }
722 break;
723 }
724
725 if ch == '\n' {
726 point_utf16 += PointUtf16::new(1, 0);
727 point += Point::new(1, 0);
728 } else {
729 point_utf16 += PointUtf16::new(0, ch.len_utf16() as u32);
730 point += Point::new(0, ch.len_utf8() as u32);
731 }
732 }
733 point
734 }
735
736 fn clip_point(&self, target: Point, bias: Bias) -> Point {
737 for (row, line) in self.0.split('\n').enumerate() {
738 if row == target.row as usize {
739 let mut column = target.column.min(line.len() as u32);
740 while !line.is_char_boundary(column as usize) {
741 match bias {
742 Bias::Left => column -= 1,
743 Bias::Right => column += 1,
744 }
745 }
746 return Point::new(row as u32, column);
747 }
748 }
749 unreachable!()
750 }
751
752 fn clip_point_utf16(&self, target: PointUtf16, bias: Bias) -> PointUtf16 {
753 for (row, line) in self.0.split('\n').enumerate() {
754 if row == target.row as usize {
755 let mut code_units = line.encode_utf16();
756 let mut column = code_units.by_ref().take(target.column as usize).count();
757 if char::decode_utf16(code_units).next().transpose().is_err() {
758 match bias {
759 Bias::Left => column -= 1,
760 Bias::Right => column += 1,
761 }
762 }
763 return PointUtf16::new(row as u32, column as u32);
764 }
765 }
766 unreachable!()
767 }
768}
769
770impl sum_tree::Item for Chunk {
771 type Summary = ChunkSummary;
772
773 fn summary(&self) -> Self::Summary {
774 ChunkSummary::from(self.0.as_str())
775 }
776}
777
778#[derive(Clone, Debug, Default, Eq, PartialEq)]
779pub struct ChunkSummary {
780 text: TextSummary,
781 fingerprint: HashMatrix,
782}
783
784impl<'a> From<&'a str> for ChunkSummary {
785 fn from(text: &'a str) -> Self {
786 Self {
787 text: TextSummary::from(text),
788 fingerprint: bromberg_sl2::hash_strict(text.as_bytes()),
789 }
790 }
791}
792
793impl sum_tree::Summary for ChunkSummary {
794 type Context = ();
795
796 fn add_summary(&mut self, summary: &Self, _: &()) {
797 self.text += &summary.text;
798 self.fingerprint = self.fingerprint * summary.fingerprint;
799 }
800}
801
802#[derive(Clone, Debug, Default, Eq, PartialEq)]
803pub struct TextSummary {
804 pub len: usize,
805 pub len_utf16: usize,
806 pub lines: Point,
807 pub lines_utf16: PointUtf16,
808 pub first_line_chars: u32,
809 pub last_line_chars: u32,
810 pub longest_row: u32,
811 pub longest_row_chars: u32,
812}
813
814impl<'a> From<&'a str> for TextSummary {
815 fn from(text: &'a str) -> Self {
816 let mut len_utf16 = 0;
817 let mut lines = Point::new(0, 0);
818 let mut lines_utf16 = PointUtf16::new(0, 0);
819 let mut first_line_chars = 0;
820 let mut last_line_chars = 0;
821 let mut longest_row = 0;
822 let mut longest_row_chars = 0;
823 for c in text.chars() {
824 len_utf16 += c.len_utf16();
825
826 if c == '\n' {
827 lines += Point::new(1, 0);
828 lines_utf16 += PointUtf16::new(1, 0);
829 last_line_chars = 0;
830 } else {
831 lines.column += c.len_utf8() as u32;
832 lines_utf16.column += c.len_utf16() as u32;
833 last_line_chars += 1;
834 }
835
836 if lines.row == 0 {
837 first_line_chars = last_line_chars;
838 }
839
840 if last_line_chars > longest_row_chars {
841 longest_row = lines.row;
842 longest_row_chars = last_line_chars;
843 }
844 }
845
846 TextSummary {
847 len: text.len(),
848 len_utf16,
849 lines,
850 lines_utf16,
851 first_line_chars,
852 last_line_chars,
853 longest_row,
854 longest_row_chars,
855 }
856 }
857}
858
859impl sum_tree::Summary for TextSummary {
860 type Context = ();
861
862 fn add_summary(&mut self, summary: &Self, _: &Self::Context) {
863 *self += summary;
864 }
865}
866
867impl<'a> std::ops::Add<Self> for TextSummary {
868 type Output = Self;
869
870 fn add(mut self, rhs: Self) -> Self::Output {
871 self.add_assign(&rhs);
872 self
873 }
874}
875
876impl<'a> std::ops::AddAssign<&'a Self> for TextSummary {
877 fn add_assign(&mut self, other: &'a Self) {
878 let joined_chars = self.last_line_chars + other.first_line_chars;
879 if joined_chars > self.longest_row_chars {
880 self.longest_row = self.lines.row;
881 self.longest_row_chars = joined_chars;
882 }
883 if other.longest_row_chars > self.longest_row_chars {
884 self.longest_row = self.lines.row + other.longest_row;
885 self.longest_row_chars = other.longest_row_chars;
886 }
887
888 if self.lines.row == 0 {
889 self.first_line_chars += other.first_line_chars;
890 }
891
892 if other.lines.row == 0 {
893 self.last_line_chars += other.first_line_chars;
894 } else {
895 self.last_line_chars = other.last_line_chars;
896 }
897
898 self.len += other.len;
899 self.len_utf16 += other.len_utf16;
900 self.lines += other.lines;
901 self.lines_utf16 += other.lines_utf16;
902 }
903}
904
905impl std::ops::AddAssign<Self> for TextSummary {
906 fn add_assign(&mut self, other: Self) {
907 *self += &other;
908 }
909}
910
911pub trait TextDimension: 'static + for<'a> Dimension<'a, ChunkSummary> {
912 fn from_text_summary(summary: &TextSummary) -> Self;
913 fn add_assign(&mut self, other: &Self);
914}
915
916impl<'a, D1: TextDimension, D2: TextDimension> TextDimension for (D1, D2) {
917 fn from_text_summary(summary: &TextSummary) -> Self {
918 (
919 D1::from_text_summary(summary),
920 D2::from_text_summary(summary),
921 )
922 }
923
924 fn add_assign(&mut self, other: &Self) {
925 self.0.add_assign(&other.0);
926 self.1.add_assign(&other.1);
927 }
928}
929
930impl<'a> sum_tree::Dimension<'a, ChunkSummary> for TextSummary {
931 fn add_summary(&mut self, summary: &'a ChunkSummary, _: &()) {
932 *self += &summary.text;
933 }
934}
935
936impl TextDimension for TextSummary {
937 fn from_text_summary(summary: &TextSummary) -> Self {
938 summary.clone()
939 }
940
941 fn add_assign(&mut self, other: &Self) {
942 *self += other;
943 }
944}
945
946impl<'a> sum_tree::Dimension<'a, ChunkSummary> for usize {
947 fn add_summary(&mut self, summary: &'a ChunkSummary, _: &()) {
948 *self += summary.text.len;
949 }
950}
951
952impl TextDimension for usize {
953 fn from_text_summary(summary: &TextSummary) -> Self {
954 summary.len
955 }
956
957 fn add_assign(&mut self, other: &Self) {
958 *self += other;
959 }
960}
961
962impl<'a> sum_tree::Dimension<'a, ChunkSummary> for OffsetUtf16 {
963 fn add_summary(&mut self, summary: &'a ChunkSummary, _: &()) {
964 self.0 += summary.text.len_utf16;
965 }
966}
967
968impl TextDimension for OffsetUtf16 {
969 fn from_text_summary(summary: &TextSummary) -> Self {
970 Self(summary.len_utf16)
971 }
972
973 fn add_assign(&mut self, other: &Self) {
974 *self += other;
975 }
976}
977
978impl<'a> sum_tree::Dimension<'a, ChunkSummary> for Point {
979 fn add_summary(&mut self, summary: &'a ChunkSummary, _: &()) {
980 *self += summary.text.lines;
981 }
982}
983
984impl TextDimension for Point {
985 fn from_text_summary(summary: &TextSummary) -> Self {
986 summary.lines
987 }
988
989 fn add_assign(&mut self, other: &Self) {
990 *self += other;
991 }
992}
993
994impl<'a> sum_tree::Dimension<'a, ChunkSummary> for PointUtf16 {
995 fn add_summary(&mut self, summary: &'a ChunkSummary, _: &()) {
996 *self += summary.text.lines_utf16;
997 }
998}
999
1000impl TextDimension for PointUtf16 {
1001 fn from_text_summary(summary: &TextSummary) -> Self {
1002 summary.lines_utf16
1003 }
1004
1005 fn add_assign(&mut self, other: &Self) {
1006 *self += other;
1007 }
1008}
1009
1010fn find_split_ix(text: &str) -> usize {
1011 let mut ix = text.len() / 2;
1012 while !text.is_char_boundary(ix) {
1013 if ix < 2 * CHUNK_BASE {
1014 ix += 1;
1015 } else {
1016 ix = (text.len() / 2) - 1;
1017 break;
1018 }
1019 }
1020 while !text.is_char_boundary(ix) {
1021 ix -= 1;
1022 }
1023
1024 debug_assert!(ix <= 2 * CHUNK_BASE);
1025 debug_assert!(text.len() - ix <= 2 * CHUNK_BASE);
1026 ix
1027}
1028
1029#[cfg(test)]
1030mod tests {
1031 use super::*;
1032 use crate::random_char_iter::RandomCharIter;
1033 use rand::prelude::*;
1034 use std::{cmp::Ordering, env, io::Read};
1035 use Bias::{Left, Right};
1036
1037 #[test]
1038 fn test_all_4_byte_chars() {
1039 let mut rope = Rope::new();
1040 let text = "🏀".repeat(256);
1041 rope.push(&text);
1042 assert_eq!(rope.text(), text);
1043 }
1044
1045 #[test]
1046 fn test_clip() {
1047 let rope = Rope::from("🧘");
1048
1049 assert_eq!(rope.clip_offset(1, Bias::Left), 0);
1050 assert_eq!(rope.clip_offset(1, Bias::Right), 4);
1051 assert_eq!(rope.clip_offset(5, Bias::Right), 4);
1052
1053 assert_eq!(
1054 rope.clip_point(Point::new(0, 1), Bias::Left),
1055 Point::new(0, 0)
1056 );
1057 assert_eq!(
1058 rope.clip_point(Point::new(0, 1), Bias::Right),
1059 Point::new(0, 4)
1060 );
1061 assert_eq!(
1062 rope.clip_point(Point::new(0, 5), Bias::Right),
1063 Point::new(0, 4)
1064 );
1065
1066 assert_eq!(
1067 rope.clip_point_utf16(PointUtf16::new(0, 1), Bias::Left),
1068 PointUtf16::new(0, 0)
1069 );
1070 assert_eq!(
1071 rope.clip_point_utf16(PointUtf16::new(0, 1), Bias::Right),
1072 PointUtf16::new(0, 2)
1073 );
1074 assert_eq!(
1075 rope.clip_point_utf16(PointUtf16::new(0, 3), Bias::Right),
1076 PointUtf16::new(0, 2)
1077 );
1078 }
1079
1080 #[gpui::test(iterations = 100)]
1081 fn test_random_rope(mut rng: StdRng) {
1082 let operations = env::var("OPERATIONS")
1083 .map(|i| i.parse().expect("invalid `OPERATIONS` variable"))
1084 .unwrap_or(10);
1085
1086 let mut expected = String::new();
1087 let mut actual = Rope::new();
1088 for _ in 0..operations {
1089 let end_ix = clip_offset(&expected, rng.gen_range(0..=expected.len()), Right);
1090 let start_ix = clip_offset(&expected, rng.gen_range(0..=end_ix), Left);
1091 let len = rng.gen_range(0..=64);
1092 let new_text: String = RandomCharIter::new(&mut rng).take(len).collect();
1093
1094 let mut new_actual = Rope::new();
1095 let mut cursor = actual.cursor(0);
1096 new_actual.append(cursor.slice(start_ix));
1097 new_actual.push(&new_text);
1098 cursor.seek_forward(end_ix);
1099 new_actual.append(cursor.suffix());
1100 actual = new_actual;
1101
1102 expected.replace_range(start_ix..end_ix, &new_text);
1103
1104 assert_eq!(actual.text(), expected);
1105 log::info!("text: {:?}", expected);
1106
1107 for _ in 0..5 {
1108 let end_ix = clip_offset(&expected, rng.gen_range(0..=expected.len()), Right);
1109 let start_ix = clip_offset(&expected, rng.gen_range(0..=end_ix), Left);
1110
1111 let actual_text = actual.chunks_in_range(start_ix..end_ix).collect::<String>();
1112 assert_eq!(actual_text, &expected[start_ix..end_ix]);
1113
1114 let mut actual_text = String::new();
1115 actual
1116 .bytes_in_range(start_ix..end_ix)
1117 .read_to_string(&mut actual_text)
1118 .unwrap();
1119 assert_eq!(actual_text, &expected[start_ix..end_ix]);
1120
1121 assert_eq!(
1122 actual
1123 .reversed_chunks_in_range(start_ix..end_ix)
1124 .collect::<Vec<&str>>()
1125 .into_iter()
1126 .rev()
1127 .collect::<String>(),
1128 &expected[start_ix..end_ix]
1129 );
1130 }
1131
1132 let mut offset_utf16 = OffsetUtf16(0);
1133 let mut point = Point::new(0, 0);
1134 let mut point_utf16 = PointUtf16::new(0, 0);
1135 for (ix, ch) in expected.char_indices().chain(Some((expected.len(), '\0'))) {
1136 assert_eq!(actual.offset_to_point(ix), point, "offset_to_point({})", ix);
1137 assert_eq!(
1138 actual.offset_to_point_utf16(ix),
1139 point_utf16,
1140 "offset_to_point_utf16({})",
1141 ix
1142 );
1143 assert_eq!(
1144 actual.point_to_offset(point),
1145 ix,
1146 "point_to_offset({:?})",
1147 point
1148 );
1149 assert_eq!(
1150 actual.point_utf16_to_offset(point_utf16),
1151 ix,
1152 "point_utf16_to_offset({:?})",
1153 point_utf16
1154 );
1155 assert_eq!(
1156 actual.offset_to_offset_utf16(ix),
1157 offset_utf16,
1158 "offset_to_offset_utf16({:?})",
1159 ix
1160 );
1161 assert_eq!(
1162 actual.offset_utf16_to_offset(offset_utf16),
1163 ix,
1164 "offset_utf16_to_offset({:?})",
1165 offset_utf16
1166 );
1167 if ch == '\n' {
1168 point += Point::new(1, 0);
1169 point_utf16 += PointUtf16::new(1, 0);
1170 } else {
1171 point.column += ch.len_utf8() as u32;
1172 point_utf16.column += ch.len_utf16() as u32;
1173 }
1174 offset_utf16.0 += ch.len_utf16();
1175 }
1176
1177 let mut point_utf16 = PointUtf16::zero();
1178 for unit in expected.encode_utf16() {
1179 let left_point = actual.clip_point_utf16(point_utf16, Bias::Left);
1180 let right_point = actual.clip_point_utf16(point_utf16, Bias::Right);
1181 assert!(right_point >= left_point);
1182 // Ensure translating UTF-16 points to offsets doesn't panic.
1183 actual.point_utf16_to_offset(left_point);
1184 actual.point_utf16_to_offset(right_point);
1185
1186 if unit == b'\n' as u16 {
1187 point_utf16 += PointUtf16::new(1, 0);
1188 } else {
1189 point_utf16 += PointUtf16::new(0, 1);
1190 }
1191 }
1192
1193 for _ in 0..5 {
1194 let end_ix = clip_offset(&expected, rng.gen_range(0..=expected.len()), Right);
1195 let start_ix = clip_offset(&expected, rng.gen_range(0..=end_ix), Left);
1196 assert_eq!(
1197 actual.cursor(start_ix).summary::<TextSummary>(end_ix),
1198 TextSummary::from(&expected[start_ix..end_ix])
1199 );
1200 }
1201
1202 let mut expected_longest_rows = Vec::new();
1203 let mut longest_line_len = -1_isize;
1204 for (row, line) in expected.split('\n').enumerate() {
1205 let row = row as u32;
1206 assert_eq!(
1207 actual.line_len(row),
1208 line.len() as u32,
1209 "invalid line len for row {}",
1210 row
1211 );
1212
1213 let line_char_count = line.chars().count() as isize;
1214 match line_char_count.cmp(&longest_line_len) {
1215 Ordering::Less => {}
1216 Ordering::Equal => expected_longest_rows.push(row),
1217 Ordering::Greater => {
1218 longest_line_len = line_char_count;
1219 expected_longest_rows.clear();
1220 expected_longest_rows.push(row);
1221 }
1222 }
1223 }
1224
1225 let longest_row = actual.summary().longest_row;
1226 assert!(
1227 expected_longest_rows.contains(&longest_row),
1228 "incorrect longest row {}. expected {:?} with length {}",
1229 longest_row,
1230 expected_longest_rows,
1231 longest_line_len,
1232 );
1233 }
1234 }
1235
1236 fn clip_offset(text: &str, mut offset: usize, bias: Bias) -> usize {
1237 while !text.is_char_boundary(offset) {
1238 match bias {
1239 Bias::Left => offset -= 1,
1240 Bias::Right => offset += 1,
1241 }
1242 }
1243 offset
1244 }
1245
1246 impl Rope {
1247 fn text(&self) -> String {
1248 let mut text = String::new();
1249 for chunk in self.chunks.cursor::<()>() {
1250 text.push_str(&chunk.0);
1251 }
1252 text
1253 }
1254 }
1255}