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