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