1mod chunk;
2mod offset_utf16;
3mod point;
4mod point_utf16;
5mod unclipped;
6
7use arrayvec::ArrayVec;
8use rayon::iter::{IntoParallelIterator, ParallelIterator as _};
9use std::{
10 cmp, fmt, io, mem,
11 ops::{self, AddAssign, Range},
12 str,
13};
14use sum_tree::{Bias, Dimension, Dimensions, SumTree};
15use ztracing::instrument;
16
17pub use chunk::{Chunk, ChunkSlice};
18pub use offset_utf16::OffsetUtf16;
19pub use point::Point;
20pub use point_utf16::PointUtf16;
21pub use unclipped::Unclipped;
22
23use crate::chunk::Bitmap;
24
25#[derive(Clone, Default)]
26pub struct Rope {
27 chunks: SumTree<Chunk>,
28}
29
30impl Rope {
31 pub fn new() -> Self {
32 Self::default()
33 }
34
35 /// Checks that `index`-th byte is the first byte in a UTF-8 code point
36 /// sequence or the end of the string.
37 ///
38 /// The start and end of the string (when `index == self.len()`) are
39 /// considered to be boundaries.
40 ///
41 /// Returns `false` if `index` is greater than `self.len()`.
42 pub fn is_char_boundary(&self, offset: usize) -> bool {
43 if self.chunks.is_empty() {
44 return offset == 0;
45 }
46 let (start, _, item) = self.chunks.find::<usize, _>((), &offset, Bias::Left);
47 let chunk_offset = offset - start;
48 item.map(|chunk| chunk.is_char_boundary(chunk_offset))
49 .unwrap_or(false)
50 }
51
52 #[track_caller]
53 #[inline(always)]
54 pub fn assert_char_boundary<const PANIC: bool>(&self, offset: usize) -> bool {
55 if self.chunks.is_empty() && offset == 0 {
56 return true;
57 }
58 let (start, _, item) = self.chunks.find::<usize, _>((), &offset, Bias::Left);
59 match item {
60 Some(chunk) => {
61 let chunk_offset = offset - start;
62 chunk.assert_char_boundary::<PANIC>(chunk_offset)
63 }
64 None if PANIC => {
65 panic!(
66 "byte index {} is out of bounds of rope (length: {})",
67 offset,
68 self.len()
69 );
70 }
71 None => {
72 log::error!(
73 "byte index {} is out of bounds of rope (length: {})",
74 offset,
75 self.len()
76 );
77 false
78 }
79 }
80 }
81
82 pub fn floor_char_boundary(&self, index: usize) -> usize {
83 if index >= self.len() {
84 self.len()
85 } else {
86 let (start, _, item) = self.chunks.find::<usize, _>((), &index, Bias::Left);
87 let chunk_offset = index - start;
88 let lower_idx = item.map(|chunk| chunk.text.floor_char_boundary(chunk_offset));
89 lower_idx.map_or_else(|| self.len(), |idx| start + idx)
90 }
91 }
92
93 pub fn ceil_char_boundary(&self, index: usize) -> usize {
94 if index > self.len() {
95 self.len()
96 } else {
97 let (start, _, item) = self.chunks.find::<usize, _>((), &index, Bias::Left);
98 let chunk_offset = index - start;
99 let upper_idx = item.map(|chunk| chunk.text.ceil_char_boundary(chunk_offset));
100 upper_idx.map_or_else(|| self.len(), |idx| start + idx)
101 }
102 }
103
104 pub fn append(&mut self, rope: Rope) {
105 if let Some(chunk) = rope.chunks.first()
106 && (self
107 .chunks
108 .last()
109 .is_some_and(|c| c.text.len() < chunk::MIN_BASE)
110 || chunk.text.len() < chunk::MIN_BASE)
111 {
112 self.push_chunk(chunk.as_slice());
113
114 let mut chunks = rope.chunks.cursor::<()>(());
115 chunks.next();
116 chunks.next();
117 self.chunks.append(chunks.suffix(), ());
118 } else {
119 self.chunks.append(rope.chunks, ());
120 }
121 self.check_invariants();
122 }
123
124 pub fn replace(&mut self, range: Range<usize>, text: &str) {
125 let mut new_rope = Rope::new();
126 let mut cursor = self.cursor(0);
127 new_rope.append(cursor.slice(range.start));
128 cursor.seek_forward(range.end);
129 new_rope.push(text);
130 new_rope.append(cursor.suffix());
131 *self = new_rope;
132 }
133
134 pub fn slice(&self, range: Range<usize>) -> Rope {
135 let mut cursor = self.cursor(0);
136 cursor.seek_forward(range.start);
137 cursor.slice(range.end)
138 }
139
140 pub fn slice_rows(&self, range: Range<u32>) -> Rope {
141 // This would be more efficient with a forward advance after the first, but it's fine.
142 let start = self.point_to_offset(Point::new(range.start, 0));
143 let end = self.point_to_offset(Point::new(range.end, 0));
144 self.slice(start..end)
145 }
146
147 pub fn push(&mut self, mut text: &str) {
148 self.chunks.update_last(
149 |last_chunk| {
150 let split_ix = if last_chunk.text.len() + text.len() <= chunk::MAX_BASE {
151 text.len()
152 } else {
153 let mut split_ix = cmp::min(
154 chunk::MIN_BASE.saturating_sub(last_chunk.text.len()),
155 text.len(),
156 );
157 while !text.is_char_boundary(split_ix) {
158 split_ix += 1;
159 }
160 split_ix
161 };
162
163 let (suffix, remainder) = text.split_at(split_ix);
164 last_chunk.push_str(suffix);
165 text = remainder;
166 },
167 (),
168 );
169
170 if text.is_empty() {
171 self.check_invariants();
172 return;
173 }
174
175 #[cfg(all(test, not(rust_analyzer)))]
176 const NUM_CHUNKS: usize = 16;
177 #[cfg(not(all(test, not(rust_analyzer))))]
178 const NUM_CHUNKS: usize = 4;
179
180 // We accommodate for NUM_CHUNKS chunks of size MAX_BASE
181 // but given the chunk boundary can land within a character
182 // we need to accommodate for the worst case where every chunk gets cut short by up to 4 bytes
183 if text.len() > NUM_CHUNKS * chunk::MAX_BASE - NUM_CHUNKS * 4 {
184 return self.push_large(text);
185 }
186 // 16 is enough as otherwise we will hit the branch above
187 let mut new_chunks = ArrayVec::<_, NUM_CHUNKS>::new();
188
189 while !text.is_empty() {
190 let mut split_ix = cmp::min(chunk::MAX_BASE, text.len());
191 while !text.is_char_boundary(split_ix) {
192 split_ix -= 1;
193 }
194 let (chunk, remainder) = text.split_at(split_ix);
195 new_chunks.push(chunk);
196 text = remainder;
197 }
198 self.chunks
199 .extend(new_chunks.into_iter().map(Chunk::new), ());
200
201 self.check_invariants();
202 }
203
204 /// A copy of `push` specialized for working with large quantities of text.
205 fn push_large(&mut self, mut text: &str) {
206 // To avoid frequent reallocs when loading large swaths of file contents,
207 // we estimate worst-case `new_chunks` capacity;
208 // Chunk is a fixed-capacity buffer. If a character falls on
209 // chunk boundary, we push it off to the following chunk (thus leaving a small bit of capacity unfilled in current chunk).
210 // Worst-case chunk count when loading a file is then a case where every chunk ends up with that unused capacity.
211 // Since we're working with UTF-8, each character is at most 4 bytes wide. It follows then that the worst case is where
212 // a chunk ends with 3 bytes of a 4-byte character. These 3 bytes end up being stored in the following chunk, thus wasting
213 // 3 bytes of storage in current chunk.
214 // 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.
215 const MIN_CHUNK_SIZE: usize = chunk::MAX_BASE - 3;
216
217 // 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
218 // we're working with there is large.
219 let capacity = text.len().div_ceil(MIN_CHUNK_SIZE);
220 let mut new_chunks = Vec::with_capacity(capacity);
221
222 while !text.is_empty() {
223 let mut split_ix = cmp::min(chunk::MAX_BASE, text.len());
224 while !text.is_char_boundary(split_ix) {
225 split_ix -= 1;
226 }
227 let (chunk, remainder) = text.split_at(split_ix);
228 new_chunks.push(chunk);
229 text = remainder;
230 }
231
232 #[cfg(all(test, not(rust_analyzer)))]
233 const PARALLEL_THRESHOLD: usize = 4;
234 #[cfg(not(all(test, not(rust_analyzer))))]
235 const PARALLEL_THRESHOLD: usize = 84 * (2 * sum_tree::TREE_BASE);
236
237 if new_chunks.len() >= PARALLEL_THRESHOLD {
238 self.chunks
239 .par_extend(new_chunks.into_par_iter().map(Chunk::new), ());
240 } else {
241 self.chunks
242 .extend(new_chunks.into_iter().map(Chunk::new), ());
243 }
244
245 self.check_invariants();
246 }
247
248 fn push_chunk(&mut self, mut chunk: ChunkSlice) {
249 self.chunks.update_last(
250 |last_chunk| {
251 let split_ix = if last_chunk.text.len() + chunk.len() <= chunk::MAX_BASE {
252 chunk.len()
253 } else {
254 let mut split_ix = cmp::min(
255 chunk::MIN_BASE.saturating_sub(last_chunk.text.len()),
256 chunk.len(),
257 );
258 while !chunk.is_char_boundary(split_ix) {
259 split_ix += 1;
260 }
261 split_ix
262 };
263
264 let (suffix, remainder) = chunk.split_at(split_ix);
265 last_chunk.append(suffix);
266 chunk = remainder;
267 },
268 (),
269 );
270
271 if !chunk.is_empty() {
272 self.chunks.push(chunk.into(), ());
273 }
274 }
275
276 pub fn push_front(&mut self, text: &str) {
277 if text.is_empty() {
278 return;
279 }
280 if self.is_empty() {
281 self.push(text);
282 return;
283 }
284 if self
285 .chunks
286 .first()
287 .is_some_and(|c| c.text.len() + text.len() <= chunk::MAX_BASE)
288 {
289 self.chunks
290 .update_first(|first_chunk| first_chunk.prepend_str(text), ());
291 self.check_invariants();
292 return;
293 }
294 let suffix = mem::replace(self, Rope::from(text));
295 self.append(suffix);
296 }
297
298 fn check_invariants(&self) {
299 #[cfg(test)]
300 {
301 // Ensure all chunks except maybe the last one are not underflowing.
302 // Allow some wiggle room for multibyte characters at chunk boundaries.
303 let mut chunks = self.chunks.cursor::<()>(()).peekable();
304 while let Some(chunk) = chunks.next() {
305 if chunks.peek().is_some() {
306 assert!(chunk.text.len() + 3 >= chunk::MIN_BASE);
307 }
308 }
309 }
310 }
311
312 pub fn summary(&self) -> TextSummary {
313 self.chunks.summary().text
314 }
315
316 pub fn len(&self) -> usize {
317 self.chunks.extent(())
318 }
319
320 pub fn is_empty(&self) -> bool {
321 self.len() == 0
322 }
323
324 pub fn max_point(&self) -> Point {
325 self.chunks.extent(())
326 }
327
328 pub fn max_point_utf16(&self) -> PointUtf16 {
329 self.chunks.extent(())
330 }
331
332 pub fn cursor(&self, offset: usize) -> Cursor<'_> {
333 Cursor::new(self, offset)
334 }
335
336 pub fn chars(&self) -> impl Iterator<Item = char> + '_ {
337 self.chars_at(0)
338 }
339
340 pub fn chars_at(&self, start: usize) -> impl Iterator<Item = char> + '_ {
341 self.chunks_in_range(start..self.len()).flat_map(str::chars)
342 }
343
344 pub fn reversed_chars_at(&self, start: usize) -> impl Iterator<Item = char> + '_ {
345 self.reversed_chunks_in_range(0..start)
346 .flat_map(|chunk| chunk.chars().rev())
347 }
348
349 pub fn bytes_in_range(&self, range: Range<usize>) -> Bytes<'_> {
350 Bytes::new(self, range, false)
351 }
352
353 pub fn reversed_bytes_in_range(&self, range: Range<usize>) -> Bytes<'_> {
354 Bytes::new(self, range, true)
355 }
356
357 pub fn chunks(&self) -> Chunks<'_> {
358 self.chunks_in_range(0..self.len())
359 }
360
361 pub fn chunks_in_range(&self, range: Range<usize>) -> Chunks<'_> {
362 Chunks::new(self, range, false)
363 }
364
365 pub fn reversed_chunks_in_range(&self, range: Range<usize>) -> Chunks<'_> {
366 Chunks::new(self, range, true)
367 }
368
369 pub fn offset_to_offset_utf16(&self, offset: usize) -> OffsetUtf16 {
370 if offset >= self.summary().len {
371 return self.summary().len_utf16;
372 }
373 let (start, _, item) =
374 self.chunks
375 .find::<Dimensions<usize, OffsetUtf16>, _>((), &offset, Bias::Left);
376 let overshoot = offset - start.0;
377 start.1
378 + item.map_or(Default::default(), |chunk| {
379 chunk.as_slice().offset_to_offset_utf16(overshoot)
380 })
381 }
382
383 pub fn offset_utf16_to_offset(&self, offset: OffsetUtf16) -> usize {
384 if offset >= self.summary().len_utf16 {
385 return self.summary().len;
386 }
387 let (start, _, item) =
388 self.chunks
389 .find::<Dimensions<OffsetUtf16, usize>, _>((), &offset, Bias::Left);
390 let overshoot = offset - start.0;
391 start.1
392 + item.map_or(Default::default(), |chunk| {
393 chunk.as_slice().offset_utf16_to_offset(overshoot)
394 })
395 }
396
397 pub fn offset_to_point(&self, offset: usize) -> Point {
398 if offset >= self.summary().len {
399 return self.summary().lines;
400 }
401 let (start, _, item) =
402 self.chunks
403 .find::<Dimensions<usize, Point>, _>((), &offset, Bias::Left);
404 let overshoot = offset - start.0;
405 start.1
406 + item.map_or(Point::zero(), |chunk| {
407 chunk.as_slice().offset_to_point(overshoot)
408 })
409 }
410
411 pub fn offset_to_point_utf16(&self, offset: usize) -> PointUtf16 {
412 if offset >= self.summary().len {
413 return self.summary().lines_utf16();
414 }
415 let (start, _, item) =
416 self.chunks
417 .find::<Dimensions<usize, PointUtf16>, _>((), &offset, Bias::Left);
418 let overshoot = offset - start.0;
419 start.1
420 + item.map_or(PointUtf16::zero(), |chunk| {
421 chunk.as_slice().offset_to_point_utf16(overshoot)
422 })
423 }
424
425 pub fn point_to_point_utf16(&self, point: Point) -> PointUtf16 {
426 if point >= self.summary().lines {
427 return self.summary().lines_utf16();
428 }
429 let (start, _, item) =
430 self.chunks
431 .find::<Dimensions<Point, PointUtf16>, _>((), &point, Bias::Left);
432 let overshoot = point - start.0;
433 start.1
434 + item.map_or(PointUtf16::zero(), |chunk| {
435 chunk.as_slice().point_to_point_utf16(overshoot)
436 })
437 }
438
439 pub fn point_utf16_to_point(&self, point: PointUtf16) -> Point {
440 if point >= self.summary().lines_utf16() {
441 return self.summary().lines;
442 }
443 let mut cursor = self.chunks.cursor::<Dimensions<PointUtf16, Point>>(());
444 cursor.seek(&point, Bias::Left);
445 let overshoot = point - cursor.start().0;
446 cursor.start().1
447 + cursor.item().map_or(Point::zero(), |chunk| {
448 chunk
449 .as_slice()
450 .offset_to_point(chunk.as_slice().point_utf16_to_offset(overshoot, false))
451 })
452 }
453
454 #[instrument(skip_all)]
455 pub fn point_to_offset(&self, point: Point) -> usize {
456 if point >= self.summary().lines {
457 return self.summary().len;
458 }
459 let (start, _, item) =
460 self.chunks
461 .find::<Dimensions<Point, usize>, _>((), &point, Bias::Left);
462 let overshoot = point - start.0;
463 start.1 + item.map_or(0, |chunk| chunk.as_slice().point_to_offset(overshoot))
464 }
465
466 pub fn point_to_offset_utf16(&self, point: Point) -> OffsetUtf16 {
467 if point >= self.summary().lines {
468 return self.summary().len_utf16;
469 }
470 let mut cursor = self.chunks.cursor::<Dimensions<Point, OffsetUtf16>>(());
471 cursor.seek(&point, Bias::Left);
472 let overshoot = point - cursor.start().0;
473 cursor.start().1
474 + cursor.item().map_or(OffsetUtf16(0), |chunk| {
475 chunk.as_slice().point_to_offset_utf16(overshoot)
476 })
477 }
478
479 pub fn point_utf16_to_offset(&self, point: PointUtf16) -> usize {
480 self.point_utf16_to_offset_impl(point, false)
481 }
482
483 pub fn point_utf16_to_offset_utf16(&self, point: PointUtf16) -> OffsetUtf16 {
484 self.point_utf16_to_offset_utf16_impl(point, false)
485 }
486
487 pub fn unclipped_point_utf16_to_offset(&self, point: Unclipped<PointUtf16>) -> usize {
488 self.point_utf16_to_offset_impl(point.0, true)
489 }
490
491 fn point_utf16_to_offset_impl(&self, point: PointUtf16, clip: bool) -> usize {
492 if point >= self.summary().lines_utf16() {
493 return self.summary().len;
494 }
495 let (start, _, item) =
496 self.chunks
497 .find::<Dimensions<PointUtf16, usize>, _>((), &point, Bias::Left);
498 let overshoot = point - start.0;
499 start.1
500 + item.map_or(0, |chunk| {
501 chunk.as_slice().point_utf16_to_offset(overshoot, clip)
502 })
503 }
504
505 fn point_utf16_to_offset_utf16_impl(&self, point: PointUtf16, clip: bool) -> OffsetUtf16 {
506 if point >= self.summary().lines_utf16() {
507 return self.summary().len_utf16;
508 }
509 let mut cursor = self
510 .chunks
511 .cursor::<Dimensions<PointUtf16, OffsetUtf16>>(());
512 cursor.seek(&point, Bias::Left);
513 let overshoot = point - cursor.start().0;
514 cursor.start().1
515 + cursor.item().map_or(OffsetUtf16(0), |chunk| {
516 chunk
517 .as_slice()
518 .offset_to_offset_utf16(chunk.as_slice().point_utf16_to_offset(overshoot, clip))
519 })
520 }
521
522 pub fn unclipped_point_utf16_to_point(&self, point: Unclipped<PointUtf16>) -> Point {
523 if point.0 >= self.summary().lines_utf16() {
524 return self.summary().lines;
525 }
526 let (start, _, item) =
527 self.chunks
528 .find::<Dimensions<PointUtf16, Point>, _>((), &point.0, Bias::Left);
529 let overshoot = Unclipped(point.0 - start.0);
530 start.1
531 + item.map_or(Point::zero(), |chunk| {
532 chunk.as_slice().unclipped_point_utf16_to_point(overshoot)
533 })
534 }
535
536 pub fn clip_offset(&self, offset: usize, bias: Bias) -> usize {
537 match bias {
538 Bias::Left => self.floor_char_boundary(offset),
539 Bias::Right => self.ceil_char_boundary(offset),
540 }
541 }
542
543 pub fn clip_offset_utf16(&self, offset: OffsetUtf16, bias: Bias) -> OffsetUtf16 {
544 let (start, _, item) = self.chunks.find::<OffsetUtf16, _>((), &offset, Bias::Right);
545 if let Some(chunk) = item {
546 let overshoot = offset - start;
547 start + chunk.as_slice().clip_offset_utf16(overshoot, bias)
548 } else {
549 self.summary().len_utf16
550 }
551 }
552
553 pub fn clip_point(&self, point: Point, bias: Bias) -> Point {
554 let (start, _, item) = self.chunks.find::<Point, _>((), &point, Bias::Right);
555 if let Some(chunk) = item {
556 let overshoot = point - start;
557 start + chunk.as_slice().clip_point(overshoot, bias)
558 } else {
559 self.summary().lines
560 }
561 }
562
563 pub fn clip_point_utf16(&self, point: Unclipped<PointUtf16>, bias: Bias) -> PointUtf16 {
564 let (start, _, item) = self.chunks.find::<PointUtf16, _>((), &point.0, Bias::Right);
565 if let Some(chunk) = item {
566 let overshoot = Unclipped(point.0 - start);
567 start + chunk.as_slice().clip_point_utf16(overshoot, bias)
568 } else {
569 self.summary().lines_utf16()
570 }
571 }
572
573 pub fn starts_with(&self, pattern: &str) -> bool {
574 if pattern.len() > self.len() {
575 return false;
576 }
577 let mut remaining = pattern;
578 for chunk in self.chunks_in_range(0..self.len()) {
579 let Some(chunk) = chunk.get(..remaining.len().min(chunk.len())) else {
580 return false;
581 };
582 if remaining.starts_with(chunk) {
583 remaining = &remaining[chunk.len()..];
584 if remaining.is_empty() {
585 return true;
586 }
587 } else {
588 return false;
589 }
590 }
591 remaining.is_empty()
592 }
593
594 pub fn ends_with(&self, pattern: &str) -> bool {
595 if pattern.len() > self.len() {
596 return false;
597 }
598 let mut remaining = pattern;
599 for chunk in self.reversed_chunks_in_range(0..self.len()) {
600 let Some(chunk) = chunk.get(chunk.len() - remaining.len().min(chunk.len())..) else {
601 return false;
602 };
603 if remaining.ends_with(chunk) {
604 remaining = &remaining[..remaining.len() - chunk.len()];
605 if remaining.is_empty() {
606 return true;
607 }
608 } else {
609 return false;
610 }
611 }
612 remaining.is_empty()
613 }
614
615 pub fn line_len(&self, row: u32) -> u32 {
616 self.clip_point(Point::new(row, u32::MAX), Bias::Left)
617 .column
618 }
619}
620
621impl<'a> From<&'a str> for Rope {
622 fn from(text: &'a str) -> Self {
623 let mut rope = Self::new();
624 rope.push(text);
625 rope
626 }
627}
628
629impl<'a> FromIterator<&'a str> for Rope {
630 fn from_iter<T: IntoIterator<Item = &'a str>>(iter: T) -> Self {
631 let mut rope = Rope::new();
632 for chunk in iter {
633 rope.push(chunk);
634 }
635 rope
636 }
637}
638
639impl From<String> for Rope {
640 #[inline(always)]
641 fn from(text: String) -> Self {
642 Rope::from(text.as_str())
643 }
644}
645
646impl From<&String> for Rope {
647 #[inline(always)]
648 fn from(text: &String) -> Self {
649 Rope::from(text.as_str())
650 }
651}
652
653impl fmt::Display for Rope {
654 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
655 for chunk in self.chunks() {
656 write!(f, "{}", chunk)?;
657 }
658 Ok(())
659 }
660}
661
662impl fmt::Debug for Rope {
663 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
664 use std::fmt::Write as _;
665
666 write!(f, "\"")?;
667 let mut format_string = String::new();
668 for chunk in self.chunks() {
669 write!(&mut format_string, "{:?}", chunk)?;
670 write!(f, "{}", &format_string[1..format_string.len() - 1])?;
671 format_string.clear();
672 }
673 write!(f, "\"")?;
674 Ok(())
675 }
676}
677
678pub struct Cursor<'a> {
679 rope: &'a Rope,
680 chunks: sum_tree::Cursor<'a, 'static, Chunk, usize>,
681 offset: usize,
682}
683
684impl<'a> Cursor<'a> {
685 pub fn new(rope: &'a Rope, offset: usize) -> Self {
686 let mut chunks = rope.chunks.cursor(());
687 chunks.seek(&offset, Bias::Right);
688 Self {
689 rope,
690 chunks,
691 offset,
692 }
693 }
694
695 pub fn seek_forward(&mut self, end_offset: usize) {
696 assert!(
697 end_offset >= self.offset,
698 "cannot seek backward from {} to {}",
699 self.offset,
700 end_offset
701 );
702
703 self.chunks.seek_forward(&end_offset, Bias::Right);
704 self.offset = end_offset;
705 }
706
707 pub fn slice(&mut self, end_offset: usize) -> Rope {
708 assert!(
709 end_offset >= self.offset,
710 "cannot slice backward from {} to {}",
711 self.offset,
712 end_offset
713 );
714
715 let mut slice = Rope::new();
716 if let Some(start_chunk) = self.chunks.item() {
717 let start_ix = self.offset - self.chunks.start();
718 let end_ix = cmp::min(end_offset, self.chunks.end()) - self.chunks.start();
719 slice.push_chunk(start_chunk.slice(start_ix..end_ix));
720 }
721
722 if end_offset > self.chunks.end() {
723 self.chunks.next();
724 slice.append(Rope {
725 chunks: self.chunks.slice(&end_offset, Bias::Right),
726 });
727 if let Some(end_chunk) = self.chunks.item() {
728 let end_ix = end_offset - self.chunks.start();
729 slice.push_chunk(end_chunk.slice(0..end_ix));
730 }
731 }
732
733 self.offset = end_offset;
734 slice
735 }
736
737 pub fn summary<D: TextDimension>(&mut self, end_offset: usize) -> D {
738 assert!(
739 end_offset >= self.offset,
740 "cannot summarize backward from {} to {}",
741 self.offset,
742 end_offset
743 );
744
745 let mut summary = D::zero(());
746 if let Some(start_chunk) = self.chunks.item() {
747 let start_ix = self.offset - self.chunks.start();
748 let end_ix = cmp::min(end_offset, self.chunks.end()) - self.chunks.start();
749 summary.add_assign(&D::from_chunk(start_chunk.slice(start_ix..end_ix)));
750 }
751
752 if end_offset > self.chunks.end() {
753 self.chunks.next();
754 summary.add_assign(&self.chunks.summary(&end_offset, Bias::Right));
755 if let Some(end_chunk) = self.chunks.item() {
756 let end_ix = end_offset - self.chunks.start();
757 summary.add_assign(&D::from_chunk(end_chunk.slice(0..end_ix)));
758 }
759 }
760
761 self.offset = end_offset;
762 summary
763 }
764
765 pub fn suffix(mut self) -> Rope {
766 self.slice(self.rope.chunks.extent(()))
767 }
768
769 pub fn offset(&self) -> usize {
770 self.offset
771 }
772}
773
774pub struct ChunkBitmaps<'a> {
775 /// A slice of text up to 128 bytes in size
776 pub text: &'a str,
777 /// Bitmap of character locations in text. LSB ordered
778 pub chars: Bitmap,
779 /// Bitmap of tab locations in text. LSB ordered
780 pub tabs: Bitmap,
781 /// Bitmap of newlines location in text. LSB ordered
782 pub newlines: Bitmap,
783}
784
785#[derive(Clone)]
786pub struct Chunks<'a> {
787 chunks: sum_tree::Cursor<'a, 'static, Chunk, usize>,
788 range: Range<usize>,
789 offset: usize,
790 reversed: bool,
791}
792
793impl<'a> Chunks<'a> {
794 pub fn new(rope: &'a Rope, range: Range<usize>, reversed: bool) -> Self {
795 let mut chunks = rope.chunks.cursor(());
796 let offset = if reversed {
797 chunks.seek(&range.end, Bias::Left);
798 range.end
799 } else {
800 chunks.seek(&range.start, Bias::Right);
801 range.start
802 };
803 let chunk_offset = offset - chunks.start();
804 if let Some(chunk) = chunks.item() {
805 chunk.assert_char_boundary::<true>(chunk_offset);
806 }
807 Self {
808 chunks,
809 range,
810 offset,
811 reversed,
812 }
813 }
814
815 fn offset_is_valid(&self) -> bool {
816 if self.reversed {
817 if self.offset <= self.range.start || self.offset > self.range.end {
818 return false;
819 }
820 } else if self.offset < self.range.start || self.offset >= self.range.end {
821 return false;
822 }
823
824 true
825 }
826
827 pub fn offset(&self) -> usize {
828 self.offset
829 }
830
831 pub fn seek(&mut self, mut offset: usize) {
832 offset = offset.clamp(self.range.start, self.range.end);
833
834 if self.reversed {
835 if offset > self.chunks.end() {
836 self.chunks.seek_forward(&offset, Bias::Left);
837 } else if offset <= *self.chunks.start() {
838 self.chunks.seek(&offset, Bias::Left);
839 }
840 } else {
841 if offset >= self.chunks.end() {
842 self.chunks.seek_forward(&offset, Bias::Right);
843 } else if offset < *self.chunks.start() {
844 self.chunks.seek(&offset, Bias::Right);
845 }
846 };
847
848 self.offset = offset;
849 }
850
851 pub fn set_range(&mut self, range: Range<usize>) {
852 self.range = range.clone();
853 self.seek(range.start);
854 }
855
856 /// Moves this cursor to the start of the next line in the rope.
857 ///
858 /// This method advances the cursor to the beginning of the next line.
859 /// If the cursor is already at the end of the rope, this method does nothing.
860 /// Reversed chunks iterators are not currently supported and will panic.
861 ///
862 /// Returns `true` if the cursor was successfully moved to the next line start,
863 /// or `false` if the cursor was already at the end of the rope.
864 pub fn next_line(&mut self) -> bool {
865 assert!(!self.reversed);
866
867 let mut found = false;
868 if let Some(chunk) = self.peek() {
869 if let Some(newline_ix) = chunk.find('\n') {
870 self.offset += newline_ix + 1;
871 found = self.offset <= self.range.end;
872 } else {
873 self.chunks
874 .search_forward(|summary| summary.text.lines.row > 0);
875 self.offset = *self.chunks.start();
876
877 if let Some(newline_ix) = self.peek().and_then(|chunk| chunk.find('\n')) {
878 self.offset += newline_ix + 1;
879 found = self.offset <= self.range.end;
880 } else {
881 self.offset = self.chunks.end();
882 }
883 }
884
885 if self.offset == self.chunks.end() {
886 self.next();
887 }
888 }
889
890 if self.offset > self.range.end {
891 self.offset = cmp::min(self.offset, self.range.end);
892 self.chunks.seek(&self.offset, Bias::Right);
893 }
894
895 found
896 }
897
898 /// Move this cursor to the preceding position in the rope that starts a new line.
899 /// Reversed chunks iterators are not currently supported and will panic.
900 ///
901 /// If this cursor is not on the start of a line, it will be moved to the start of
902 /// its current line. Otherwise it will be moved to the start of the previous line.
903 /// It updates the cursor's position and returns true if a previous line was found,
904 /// or false if the cursor was already at the start of the rope.
905 pub fn prev_line(&mut self) -> bool {
906 assert!(!self.reversed);
907
908 let initial_offset = self.offset;
909
910 if self.offset == *self.chunks.start() {
911 self.chunks.prev();
912 }
913
914 if let Some(chunk) = self.chunks.item() {
915 let mut end_ix = self.offset - *self.chunks.start();
916 if chunk.text.as_bytes()[end_ix - 1] == b'\n' {
917 end_ix -= 1;
918 }
919
920 if let Some(newline_ix) = chunk.text[..end_ix].rfind('\n') {
921 self.offset = *self.chunks.start() + newline_ix + 1;
922 if self.offset_is_valid() {
923 return true;
924 }
925 }
926 }
927
928 self.chunks
929 .search_backward(|summary| summary.text.lines.row > 0);
930 self.offset = *self.chunks.start();
931 if let Some(chunk) = self.chunks.item()
932 && let Some(newline_ix) = chunk.text.rfind('\n')
933 {
934 self.offset += newline_ix + 1;
935 if self.offset_is_valid() {
936 if self.offset == self.chunks.end() {
937 self.chunks.next();
938 }
939
940 return true;
941 }
942 }
943
944 if !self.offset_is_valid() || self.chunks.item().is_none() {
945 self.offset = self.range.start;
946 self.chunks.seek(&self.offset, Bias::Right);
947 }
948
949 self.offset < initial_offset && self.offset == 0
950 }
951
952 pub fn peek(&self) -> Option<&'a str> {
953 if !self.offset_is_valid() {
954 return None;
955 }
956
957 let chunk = self.chunks.item()?;
958 let chunk_start = *self.chunks.start();
959 let slice_range = if self.reversed {
960 let slice_start = cmp::max(chunk_start, self.range.start) - chunk_start;
961 let slice_end = self.offset - chunk_start;
962 slice_start..slice_end
963 } else {
964 let slice_start = self.offset - chunk_start;
965 let slice_end = cmp::min(self.chunks.end(), self.range.end) - chunk_start;
966 slice_start..slice_end
967 };
968
969 Some(&chunk.text[slice_range])
970 }
971
972 /// Returns bitmaps that represent character positions and tab positions
973 pub fn peek_with_bitmaps(&self) -> Option<ChunkBitmaps<'a>> {
974 if !self.offset_is_valid() {
975 return None;
976 }
977
978 let chunk = self.chunks.item()?;
979 let chunk_start = *self.chunks.start();
980 let slice_range = if self.reversed {
981 let slice_start = cmp::max(chunk_start, self.range.start) - chunk_start;
982 let slice_end = self.offset - chunk_start;
983 slice_start..slice_end
984 } else {
985 let slice_start = self.offset - chunk_start;
986 let slice_end = cmp::min(self.chunks.end(), self.range.end) - chunk_start;
987 slice_start..slice_end
988 };
989 let chunk_start_offset = slice_range.start;
990 let slice_text = &chunk.text[slice_range];
991
992 // Shift the tabs to align with our slice window
993 let shifted_tabs = chunk.tabs() >> chunk_start_offset;
994 let shifted_chars = chunk.chars() >> chunk_start_offset;
995 let shifted_newlines = chunk.newlines() >> chunk_start_offset;
996
997 Some(ChunkBitmaps {
998 text: slice_text,
999 chars: shifted_chars,
1000 tabs: shifted_tabs,
1001 newlines: shifted_newlines,
1002 })
1003 }
1004
1005 pub fn lines(self) -> Lines<'a> {
1006 let reversed = self.reversed;
1007 Lines {
1008 chunks: self,
1009 current_line: String::new(),
1010 done: false,
1011 reversed,
1012 }
1013 }
1014
1015 pub fn equals_str(&self, other: &str) -> bool {
1016 let chunk = self.clone();
1017 if chunk.reversed {
1018 let mut offset = other.len();
1019 for chunk in chunk {
1020 if other[0..offset].ends_with(chunk) {
1021 offset -= chunk.len();
1022 } else {
1023 return false;
1024 }
1025 }
1026 if offset != 0 {
1027 return false;
1028 }
1029 } else {
1030 let mut offset = 0;
1031 for chunk in chunk {
1032 if offset >= other.len() {
1033 return false;
1034 }
1035 if other[offset..].starts_with(chunk) {
1036 offset += chunk.len();
1037 } else {
1038 return false;
1039 }
1040 }
1041 if offset != other.len() {
1042 return false;
1043 }
1044 }
1045
1046 true
1047 }
1048}
1049
1050pub struct ChunkWithBitmaps<'a>(pub Chunks<'a>);
1051
1052impl<'a> Iterator for ChunkWithBitmaps<'a> {
1053 /// text, chars bitmap, tabs bitmap
1054 type Item = ChunkBitmaps<'a>;
1055
1056 fn next(&mut self) -> Option<Self::Item> {
1057 let chunk_bitmaps = self.0.peek_with_bitmaps()?;
1058 if self.0.reversed {
1059 self.0.offset -= chunk_bitmaps.text.len();
1060 if self.0.offset <= *self.0.chunks.start() {
1061 self.0.chunks.prev();
1062 }
1063 } else {
1064 self.0.offset += chunk_bitmaps.text.len();
1065 if self.0.offset >= self.0.chunks.end() {
1066 self.0.chunks.next();
1067 }
1068 }
1069
1070 Some(chunk_bitmaps)
1071 }
1072}
1073
1074impl<'a> Iterator for Chunks<'a> {
1075 type Item = &'a str;
1076
1077 fn next(&mut self) -> Option<Self::Item> {
1078 let chunk = self.peek()?;
1079 if self.reversed {
1080 self.offset -= chunk.len();
1081 if self.offset <= *self.chunks.start() {
1082 self.chunks.prev();
1083 }
1084 } else {
1085 self.offset += chunk.len();
1086 if self.offset >= self.chunks.end() {
1087 self.chunks.next();
1088 }
1089 }
1090
1091 Some(chunk)
1092 }
1093}
1094
1095pub struct Bytes<'a> {
1096 chunks: sum_tree::Cursor<'a, 'static, Chunk, usize>,
1097 range: Range<usize>,
1098 reversed: bool,
1099}
1100
1101impl<'a> Bytes<'a> {
1102 pub fn new(rope: &'a Rope, range: Range<usize>, reversed: bool) -> Self {
1103 let mut chunks = rope.chunks.cursor(());
1104 if reversed {
1105 chunks.seek(&range.end, Bias::Left);
1106 } else {
1107 chunks.seek(&range.start, Bias::Right);
1108 }
1109 Self {
1110 chunks,
1111 range,
1112 reversed,
1113 }
1114 }
1115
1116 pub fn peek(&self) -> Option<&'a [u8]> {
1117 let chunk = self.chunks.item()?;
1118 if self.reversed && self.range.start >= self.chunks.end() {
1119 return None;
1120 }
1121 let chunk_start = *self.chunks.start();
1122 if self.range.end <= chunk_start {
1123 return None;
1124 }
1125 let start = self.range.start.saturating_sub(chunk_start);
1126 let end = self.range.end - chunk_start;
1127 Some(&chunk.text.as_bytes()[start..chunk.text.len().min(end)])
1128 }
1129}
1130
1131impl<'a> Iterator for Bytes<'a> {
1132 type Item = &'a [u8];
1133
1134 fn next(&mut self) -> Option<Self::Item> {
1135 let result = self.peek();
1136 if result.is_some() {
1137 if self.reversed {
1138 self.chunks.prev();
1139 } else {
1140 self.chunks.next();
1141 }
1142 }
1143 result
1144 }
1145}
1146
1147impl io::Read for Bytes<'_> {
1148 fn read(&mut self, buf: &mut [u8]) -> io::Result<usize> {
1149 if let Some(chunk) = self.peek() {
1150 let len = cmp::min(buf.len(), chunk.len());
1151 if self.reversed {
1152 buf[..len].copy_from_slice(&chunk[chunk.len() - len..]);
1153 buf[..len].reverse();
1154 self.range.end -= len;
1155 } else {
1156 buf[..len].copy_from_slice(&chunk[..len]);
1157 self.range.start += len;
1158 }
1159
1160 if len == chunk.len() {
1161 if self.reversed {
1162 self.chunks.prev();
1163 } else {
1164 self.chunks.next();
1165 }
1166 }
1167 Ok(len)
1168 } else {
1169 Ok(0)
1170 }
1171 }
1172}
1173
1174pub struct Lines<'a> {
1175 chunks: Chunks<'a>,
1176 current_line: String,
1177 done: bool,
1178 reversed: bool,
1179}
1180
1181impl<'a> Lines<'a> {
1182 pub fn next(&mut self) -> Option<&str> {
1183 if self.done {
1184 return None;
1185 }
1186
1187 self.current_line.clear();
1188
1189 while let Some(chunk) = self.chunks.peek() {
1190 let chunk_lines = chunk.split('\n');
1191 if self.reversed {
1192 let mut chunk_lines = chunk_lines.rev().peekable();
1193 if let Some(chunk_line) = chunk_lines.next() {
1194 let done = chunk_lines.peek().is_some();
1195 if done {
1196 self.chunks
1197 .seek(self.chunks.offset() - chunk_line.len() - "\n".len());
1198 if self.current_line.is_empty() {
1199 return Some(chunk_line);
1200 }
1201 }
1202 self.current_line.insert_str(0, chunk_line);
1203 if done {
1204 return Some(&self.current_line);
1205 }
1206 }
1207 } else {
1208 let mut chunk_lines = chunk_lines.peekable();
1209 if let Some(chunk_line) = chunk_lines.next() {
1210 let done = chunk_lines.peek().is_some();
1211 if done {
1212 self.chunks
1213 .seek(self.chunks.offset() + chunk_line.len() + "\n".len());
1214 if self.current_line.is_empty() {
1215 return Some(chunk_line);
1216 }
1217 }
1218 self.current_line.push_str(chunk_line);
1219 if done {
1220 return Some(&self.current_line);
1221 }
1222 }
1223 }
1224
1225 self.chunks.next();
1226 }
1227
1228 self.done = true;
1229 Some(&self.current_line)
1230 }
1231
1232 pub fn seek(&mut self, offset: usize) {
1233 self.chunks.seek(offset);
1234 self.current_line.clear();
1235 self.done = false;
1236 }
1237
1238 pub fn offset(&self) -> usize {
1239 self.chunks.offset()
1240 }
1241}
1242
1243impl sum_tree::Item for Chunk {
1244 type Summary = ChunkSummary;
1245
1246 fn summary(&self, _cx: ()) -> Self::Summary {
1247 ChunkSummary {
1248 text: self.as_slice().text_summary(),
1249 }
1250 }
1251}
1252
1253#[derive(Clone, Debug, Default, Eq, PartialEq)]
1254pub struct ChunkSummary {
1255 text: TextSummary,
1256}
1257
1258impl sum_tree::ContextLessSummary for ChunkSummary {
1259 fn zero() -> Self {
1260 Default::default()
1261 }
1262
1263 fn add_summary(&mut self, summary: &Self) {
1264 self.text += &summary.text;
1265 }
1266}
1267
1268/// Summary of a string of text.
1269#[derive(Copy, Clone, Debug, Default, Eq, PartialEq)]
1270pub struct TextSummary {
1271 /// Length in bytes.
1272 pub len: usize,
1273 /// Length in UTF-8.
1274 pub chars: usize,
1275 /// Length in UTF-16 code units
1276 pub len_utf16: OffsetUtf16,
1277 /// A point representing the number of lines and the length of the last line.
1278 ///
1279 /// In other words, it marks the point after the last byte in the text, (if
1280 /// EOF was a character, this would be its position).
1281 pub lines: Point,
1282 /// How many `char`s are in the first line
1283 pub first_line_chars: u32,
1284 /// How many `char`s are in the last line
1285 pub last_line_chars: u32,
1286 /// How many UTF-16 code units are in the last line
1287 pub last_line_len_utf16: u32,
1288 /// The row idx of the longest row
1289 pub longest_row: u32,
1290 /// How many `char`s are in the longest row
1291 pub longest_row_chars: u32,
1292}
1293
1294impl TextSummary {
1295 pub fn lines_utf16(&self) -> PointUtf16 {
1296 PointUtf16 {
1297 row: self.lines.row,
1298 column: self.last_line_len_utf16,
1299 }
1300 }
1301
1302 pub fn newline() -> Self {
1303 Self {
1304 len: 1,
1305 chars: 1,
1306 len_utf16: OffsetUtf16(1),
1307 first_line_chars: 0,
1308 last_line_chars: 0,
1309 last_line_len_utf16: 0,
1310 lines: Point::new(1, 0),
1311 longest_row: 0,
1312 longest_row_chars: 0,
1313 }
1314 }
1315
1316 pub fn add_newline(&mut self) {
1317 self.len += 1;
1318 self.len_utf16 += OffsetUtf16(self.len_utf16.0 + 1);
1319 self.last_line_chars = 0;
1320 self.last_line_len_utf16 = 0;
1321 self.lines += Point::new(1, 0);
1322 }
1323}
1324
1325impl<'a> From<&'a str> for TextSummary {
1326 fn from(text: &'a str) -> Self {
1327 let mut len_utf16 = OffsetUtf16(0);
1328 let mut lines = Point::new(0, 0);
1329 let mut first_line_chars = 0;
1330 let mut last_line_chars = 0;
1331 let mut last_line_len_utf16 = 0;
1332 let mut longest_row = 0;
1333 let mut longest_row_chars = 0;
1334 let mut chars = 0;
1335 for c in text.chars() {
1336 chars += 1;
1337 len_utf16.0 += c.len_utf16();
1338
1339 if c == '\n' {
1340 lines += Point::new(1, 0);
1341 last_line_len_utf16 = 0;
1342 last_line_chars = 0;
1343 } else {
1344 lines.column += c.len_utf8() as u32;
1345 last_line_len_utf16 += c.len_utf16() as u32;
1346 last_line_chars += 1;
1347 }
1348
1349 if lines.row == 0 {
1350 first_line_chars = last_line_chars;
1351 }
1352
1353 if last_line_chars > longest_row_chars {
1354 longest_row = lines.row;
1355 longest_row_chars = last_line_chars;
1356 }
1357 }
1358
1359 TextSummary {
1360 len: text.len(),
1361 chars,
1362 len_utf16,
1363 lines,
1364 first_line_chars,
1365 last_line_chars,
1366 last_line_len_utf16,
1367 longest_row,
1368 longest_row_chars,
1369 }
1370 }
1371}
1372
1373impl sum_tree::ContextLessSummary for TextSummary {
1374 fn zero() -> Self {
1375 Default::default()
1376 }
1377
1378 fn add_summary(&mut self, summary: &Self) {
1379 *self += summary;
1380 }
1381}
1382
1383impl ops::Add<Self> for TextSummary {
1384 type Output = Self;
1385
1386 fn add(mut self, rhs: Self) -> Self::Output {
1387 AddAssign::add_assign(&mut self, &rhs);
1388 self
1389 }
1390}
1391
1392impl<'a> ops::AddAssign<&'a Self> for TextSummary {
1393 fn add_assign(&mut self, other: &'a Self) {
1394 let joined_chars = self.last_line_chars + other.first_line_chars;
1395 if joined_chars > self.longest_row_chars {
1396 self.longest_row = self.lines.row;
1397 self.longest_row_chars = joined_chars;
1398 }
1399 if other.longest_row_chars > self.longest_row_chars {
1400 self.longest_row = self.lines.row + other.longest_row;
1401 self.longest_row_chars = other.longest_row_chars;
1402 }
1403
1404 if self.lines.row == 0 {
1405 self.first_line_chars += other.first_line_chars;
1406 }
1407
1408 if other.lines.row == 0 {
1409 self.last_line_chars += other.first_line_chars;
1410 self.last_line_len_utf16 += other.last_line_len_utf16;
1411 } else {
1412 self.last_line_chars = other.last_line_chars;
1413 self.last_line_len_utf16 = other.last_line_len_utf16;
1414 }
1415
1416 self.chars += other.chars;
1417 self.len += other.len;
1418 self.len_utf16 += other.len_utf16;
1419 self.lines += other.lines;
1420 }
1421}
1422
1423impl ops::AddAssign<Self> for TextSummary {
1424 fn add_assign(&mut self, other: Self) {
1425 *self += &other;
1426 }
1427}
1428
1429pub trait TextDimension:
1430 'static + Clone + Copy + Default + for<'a> Dimension<'a, ChunkSummary> + std::fmt::Debug
1431{
1432 fn from_text_summary(summary: &TextSummary) -> Self;
1433 fn from_chunk(chunk: ChunkSlice) -> Self;
1434 fn add_assign(&mut self, other: &Self);
1435}
1436
1437impl<D1: TextDimension, D2: TextDimension> TextDimension for Dimensions<D1, D2, ()> {
1438 fn from_text_summary(summary: &TextSummary) -> Self {
1439 Dimensions(
1440 D1::from_text_summary(summary),
1441 D2::from_text_summary(summary),
1442 (),
1443 )
1444 }
1445
1446 fn from_chunk(chunk: ChunkSlice) -> Self {
1447 Dimensions(D1::from_chunk(chunk), D2::from_chunk(chunk), ())
1448 }
1449
1450 fn add_assign(&mut self, other: &Self) {
1451 self.0.add_assign(&other.0);
1452 self.1.add_assign(&other.1);
1453 }
1454}
1455
1456impl<'a> sum_tree::Dimension<'a, ChunkSummary> for TextSummary {
1457 fn zero(_cx: ()) -> Self {
1458 Default::default()
1459 }
1460
1461 fn add_summary(&mut self, summary: &'a ChunkSummary, _: ()) {
1462 *self += &summary.text;
1463 }
1464}
1465
1466impl TextDimension for TextSummary {
1467 fn from_text_summary(summary: &TextSummary) -> Self {
1468 *summary
1469 }
1470
1471 fn from_chunk(chunk: ChunkSlice) -> Self {
1472 chunk.text_summary()
1473 }
1474
1475 fn add_assign(&mut self, other: &Self) {
1476 *self += other;
1477 }
1478}
1479
1480impl<'a> sum_tree::Dimension<'a, ChunkSummary> for usize {
1481 fn zero(_cx: ()) -> Self {
1482 Default::default()
1483 }
1484
1485 fn add_summary(&mut self, summary: &'a ChunkSummary, _: ()) {
1486 *self += summary.text.len;
1487 }
1488}
1489
1490impl TextDimension for usize {
1491 fn from_text_summary(summary: &TextSummary) -> Self {
1492 summary.len
1493 }
1494
1495 fn from_chunk(chunk: ChunkSlice) -> Self {
1496 chunk.len()
1497 }
1498
1499 fn add_assign(&mut self, other: &Self) {
1500 *self += other;
1501 }
1502}
1503
1504impl<'a> sum_tree::Dimension<'a, ChunkSummary> for OffsetUtf16 {
1505 fn zero(_cx: ()) -> Self {
1506 Default::default()
1507 }
1508
1509 fn add_summary(&mut self, summary: &'a ChunkSummary, _: ()) {
1510 *self += summary.text.len_utf16;
1511 }
1512}
1513
1514impl TextDimension for OffsetUtf16 {
1515 fn from_text_summary(summary: &TextSummary) -> Self {
1516 summary.len_utf16
1517 }
1518
1519 fn from_chunk(chunk: ChunkSlice) -> Self {
1520 chunk.len_utf16()
1521 }
1522
1523 fn add_assign(&mut self, other: &Self) {
1524 *self += other;
1525 }
1526}
1527
1528impl<'a> sum_tree::Dimension<'a, ChunkSummary> for Point {
1529 fn zero(_cx: ()) -> Self {
1530 Default::default()
1531 }
1532
1533 fn add_summary(&mut self, summary: &'a ChunkSummary, _: ()) {
1534 *self += summary.text.lines;
1535 }
1536}
1537
1538impl TextDimension for Point {
1539 fn from_text_summary(summary: &TextSummary) -> Self {
1540 summary.lines
1541 }
1542
1543 fn from_chunk(chunk: ChunkSlice) -> Self {
1544 chunk.lines()
1545 }
1546
1547 fn add_assign(&mut self, other: &Self) {
1548 *self += other;
1549 }
1550}
1551
1552impl<'a> sum_tree::Dimension<'a, ChunkSummary> for PointUtf16 {
1553 fn zero(_cx: ()) -> Self {
1554 Default::default()
1555 }
1556
1557 fn add_summary(&mut self, summary: &'a ChunkSummary, _: ()) {
1558 *self += summary.text.lines_utf16();
1559 }
1560}
1561
1562impl TextDimension for PointUtf16 {
1563 fn from_text_summary(summary: &TextSummary) -> Self {
1564 summary.lines_utf16()
1565 }
1566
1567 fn from_chunk(chunk: ChunkSlice) -> Self {
1568 PointUtf16 {
1569 row: chunk.lines().row,
1570 column: chunk.last_line_len_utf16(),
1571 }
1572 }
1573
1574 fn add_assign(&mut self, other: &Self) {
1575 *self += other;
1576 }
1577}
1578
1579/// A pair of text dimensions in which only the first dimension is used for comparison,
1580/// but both dimensions are updated during addition and subtraction.
1581#[derive(Clone, Copy, Debug)]
1582pub struct DimensionPair<K, V> {
1583 pub key: K,
1584 pub value: Option<V>,
1585}
1586
1587impl<K: Default, V: Default> Default for DimensionPair<K, V> {
1588 fn default() -> Self {
1589 Self {
1590 key: Default::default(),
1591 value: Some(Default::default()),
1592 }
1593 }
1594}
1595
1596impl<K, V> cmp::Ord for DimensionPair<K, V>
1597where
1598 K: cmp::Ord,
1599{
1600 fn cmp(&self, other: &Self) -> cmp::Ordering {
1601 self.key.cmp(&other.key)
1602 }
1603}
1604
1605impl<K, V> cmp::PartialOrd for DimensionPair<K, V>
1606where
1607 K: cmp::PartialOrd,
1608{
1609 fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
1610 self.key.partial_cmp(&other.key)
1611 }
1612}
1613
1614impl<K, V> cmp::PartialEq for DimensionPair<K, V>
1615where
1616 K: cmp::PartialEq,
1617{
1618 fn eq(&self, other: &Self) -> bool {
1619 self.key.eq(&other.key)
1620 }
1621}
1622
1623impl<R, R2, K, V> ops::Sub for DimensionPair<K, V>
1624where
1625 K: ops::Sub<K, Output = R>,
1626 V: ops::Sub<V, Output = R2>,
1627{
1628 type Output = DimensionPair<R, R2>;
1629
1630 fn sub(self, rhs: Self) -> Self::Output {
1631 DimensionPair {
1632 key: self.key - rhs.key,
1633 value: self.value.zip(rhs.value).map(|(a, b)| a - b),
1634 }
1635 }
1636}
1637
1638impl<R, R2, K, V> ops::AddAssign<DimensionPair<R, R2>> for DimensionPair<K, V>
1639where
1640 K: ops::AddAssign<R>,
1641 V: ops::AddAssign<R2>,
1642{
1643 fn add_assign(&mut self, rhs: DimensionPair<R, R2>) {
1644 self.key += rhs.key;
1645 if let Some(value) = &mut self.value {
1646 if let Some(other_value) = rhs.value {
1647 *value += other_value;
1648 } else {
1649 self.value.take();
1650 }
1651 }
1652 }
1653}
1654
1655impl<D> std::ops::AddAssign<DimensionPair<Point, D>> for Point {
1656 fn add_assign(&mut self, rhs: DimensionPair<Point, D>) {
1657 *self += rhs.key;
1658 }
1659}
1660
1661impl<K, V> cmp::Eq for DimensionPair<K, V> where K: cmp::Eq {}
1662
1663impl<'a, K, V, S> sum_tree::Dimension<'a, S> for DimensionPair<K, V>
1664where
1665 S: sum_tree::Summary,
1666 K: sum_tree::Dimension<'a, S>,
1667 V: sum_tree::Dimension<'a, S>,
1668{
1669 fn zero(cx: S::Context<'_>) -> Self {
1670 Self {
1671 key: K::zero(cx),
1672 value: Some(V::zero(cx)),
1673 }
1674 }
1675
1676 fn add_summary(&mut self, summary: &'a S, cx: S::Context<'_>) {
1677 self.key.add_summary(summary, cx);
1678 if let Some(value) = &mut self.value {
1679 value.add_summary(summary, cx);
1680 }
1681 }
1682}
1683
1684impl<K, V> TextDimension for DimensionPair<K, V>
1685where
1686 K: TextDimension,
1687 V: TextDimension,
1688{
1689 fn add_assign(&mut self, other: &Self) {
1690 self.key.add_assign(&other.key);
1691 if let Some(value) = &mut self.value {
1692 if let Some(other_value) = other.value.as_ref() {
1693 value.add_assign(other_value);
1694 } else {
1695 self.value.take();
1696 }
1697 }
1698 }
1699
1700 fn from_chunk(chunk: ChunkSlice) -> Self {
1701 Self {
1702 key: K::from_chunk(chunk),
1703 value: Some(V::from_chunk(chunk)),
1704 }
1705 }
1706
1707 fn from_text_summary(summary: &TextSummary) -> Self {
1708 Self {
1709 key: K::from_text_summary(summary),
1710 value: Some(V::from_text_summary(summary)),
1711 }
1712 }
1713}
1714
1715#[cfg(test)]
1716mod tests {
1717 use super::*;
1718 use Bias::{Left, Right};
1719 use rand::prelude::*;
1720 use std::{cmp::Ordering, env, io::Read};
1721 use util::RandomCharIter;
1722
1723 #[ctor::ctor]
1724 fn init_logger() {
1725 zlog::init_test();
1726 }
1727
1728 #[test]
1729 fn test_all_4_byte_chars() {
1730 let mut rope = Rope::new();
1731 let text = "🏀".repeat(256);
1732 rope.push(&text);
1733 assert_eq!(rope.text(), text);
1734 }
1735
1736 #[test]
1737 fn test_clip() {
1738 let rope = Rope::from("🧘");
1739
1740 assert_eq!(rope.clip_offset(1, Bias::Left), 0);
1741 assert_eq!(rope.clip_offset(1, Bias::Right), 4);
1742 assert_eq!(rope.clip_offset(5, Bias::Right), 4);
1743
1744 assert_eq!(
1745 rope.clip_point(Point::new(0, 1), Bias::Left),
1746 Point::new(0, 0)
1747 );
1748 assert_eq!(
1749 rope.clip_point(Point::new(0, 1), Bias::Right),
1750 Point::new(0, 4)
1751 );
1752 assert_eq!(
1753 rope.clip_point(Point::new(0, 5), Bias::Right),
1754 Point::new(0, 4)
1755 );
1756
1757 assert_eq!(
1758 rope.clip_point_utf16(Unclipped(PointUtf16::new(0, 1)), Bias::Left),
1759 PointUtf16::new(0, 0)
1760 );
1761 assert_eq!(
1762 rope.clip_point_utf16(Unclipped(PointUtf16::new(0, 1)), Bias::Right),
1763 PointUtf16::new(0, 2)
1764 );
1765 assert_eq!(
1766 rope.clip_point_utf16(Unclipped(PointUtf16::new(0, 3)), Bias::Right),
1767 PointUtf16::new(0, 2)
1768 );
1769
1770 assert_eq!(
1771 rope.clip_offset_utf16(OffsetUtf16(1), Bias::Left),
1772 OffsetUtf16(0)
1773 );
1774 assert_eq!(
1775 rope.clip_offset_utf16(OffsetUtf16(1), Bias::Right),
1776 OffsetUtf16(2)
1777 );
1778 assert_eq!(
1779 rope.clip_offset_utf16(OffsetUtf16(3), Bias::Right),
1780 OffsetUtf16(2)
1781 );
1782 }
1783
1784 #[test]
1785 fn test_prev_next_line() {
1786 let rope = Rope::from("abc\ndef\nghi\njkl");
1787
1788 let mut chunks = rope.chunks();
1789 assert_eq!(chunks.peek().unwrap().chars().next().unwrap(), 'a');
1790
1791 assert!(chunks.next_line());
1792 assert_eq!(chunks.peek().unwrap().chars().next().unwrap(), 'd');
1793
1794 assert!(chunks.next_line());
1795 assert_eq!(chunks.peek().unwrap().chars().next().unwrap(), 'g');
1796
1797 assert!(chunks.next_line());
1798 assert_eq!(chunks.peek().unwrap().chars().next().unwrap(), 'j');
1799
1800 assert!(!chunks.next_line());
1801 assert_eq!(chunks.peek(), None);
1802
1803 assert!(chunks.prev_line());
1804 assert_eq!(chunks.peek().unwrap().chars().next().unwrap(), 'j');
1805
1806 assert!(chunks.prev_line());
1807 assert_eq!(chunks.peek().unwrap().chars().next().unwrap(), 'g');
1808
1809 assert!(chunks.prev_line());
1810 assert_eq!(chunks.peek().unwrap().chars().next().unwrap(), 'd');
1811
1812 assert!(chunks.prev_line());
1813 assert_eq!(chunks.peek().unwrap().chars().next().unwrap(), 'a');
1814
1815 assert!(!chunks.prev_line());
1816 assert_eq!(chunks.peek().unwrap().chars().next().unwrap(), 'a');
1817
1818 // Only return true when the cursor has moved to the start of a line
1819 let mut chunks = rope.chunks_in_range(5..7);
1820 chunks.seek(6);
1821 assert!(!chunks.prev_line());
1822 assert_eq!(chunks.peek().unwrap().chars().next().unwrap(), 'e');
1823
1824 assert!(!chunks.next_line());
1825 assert_eq!(chunks.peek(), None);
1826 }
1827
1828 #[test]
1829 fn test_lines() {
1830 let rope = Rope::from("abc\ndefg\nhi");
1831 let mut lines = rope.chunks().lines();
1832 assert_eq!(lines.next(), Some("abc"));
1833 assert_eq!(lines.next(), Some("defg"));
1834 assert_eq!(lines.next(), Some("hi"));
1835 assert_eq!(lines.next(), None);
1836
1837 let rope = Rope::from("abc\ndefg\nhi\n");
1838 let mut lines = rope.chunks().lines();
1839 assert_eq!(lines.next(), Some("abc"));
1840 assert_eq!(lines.next(), Some("defg"));
1841 assert_eq!(lines.next(), Some("hi"));
1842 assert_eq!(lines.next(), Some(""));
1843 assert_eq!(lines.next(), None);
1844
1845 let rope = Rope::from("abc\ndefg\nhi");
1846 let mut lines = rope.reversed_chunks_in_range(0..rope.len()).lines();
1847 assert_eq!(lines.next(), Some("hi"));
1848 assert_eq!(lines.next(), Some("defg"));
1849 assert_eq!(lines.next(), Some("abc"));
1850 assert_eq!(lines.next(), None);
1851
1852 let rope = Rope::from("abc\ndefg\nhi\n");
1853 let mut lines = rope.reversed_chunks_in_range(0..rope.len()).lines();
1854 assert_eq!(lines.next(), Some(""));
1855 assert_eq!(lines.next(), Some("hi"));
1856 assert_eq!(lines.next(), Some("defg"));
1857 assert_eq!(lines.next(), Some("abc"));
1858 assert_eq!(lines.next(), None);
1859
1860 let rope = Rope::from("abc\nlonger line test\nhi");
1861 let mut lines = rope.chunks().lines();
1862 assert_eq!(lines.next(), Some("abc"));
1863 assert_eq!(lines.next(), Some("longer line test"));
1864 assert_eq!(lines.next(), Some("hi"));
1865 assert_eq!(lines.next(), None);
1866
1867 let rope = Rope::from("abc\nlonger line test\nhi");
1868 let mut lines = rope.reversed_chunks_in_range(0..rope.len()).lines();
1869 assert_eq!(lines.next(), Some("hi"));
1870 assert_eq!(lines.next(), Some("longer line test"));
1871 assert_eq!(lines.next(), Some("abc"));
1872 assert_eq!(lines.next(), None);
1873 }
1874
1875 #[gpui::test(iterations = 100)]
1876 fn test_random_rope(mut rng: StdRng) {
1877 let operations = env::var("OPERATIONS")
1878 .map(|i| i.parse().expect("invalid `OPERATIONS` variable"))
1879 .unwrap_or(10);
1880
1881 let mut expected = String::new();
1882 let mut actual = Rope::new();
1883 for _ in 0..operations {
1884 let end_ix = clip_offset(&expected, rng.random_range(0..=expected.len()), Right);
1885 let start_ix = clip_offset(&expected, rng.random_range(0..=end_ix), Left);
1886 let len = rng.random_range(0..=64);
1887 let new_text: String = RandomCharIter::new(&mut rng).take(len).collect();
1888
1889 let mut new_actual = Rope::new();
1890 let mut cursor = actual.cursor(0);
1891 new_actual.append(cursor.slice(start_ix));
1892 new_actual.push(&new_text);
1893 cursor.seek_forward(end_ix);
1894 new_actual.append(cursor.suffix());
1895 actual = new_actual;
1896
1897 expected.replace_range(start_ix..end_ix, &new_text);
1898
1899 assert_eq!(actual.text(), expected);
1900 log::info!("text: {:?}", expected);
1901
1902 for _ in 0..5 {
1903 let end_ix = clip_offset(&expected, rng.random_range(0..=expected.len()), Right);
1904 let start_ix = clip_offset(&expected, rng.random_range(0..=end_ix), Left);
1905
1906 let actual_text = actual.chunks_in_range(start_ix..end_ix).collect::<String>();
1907 assert_eq!(actual_text, &expected[start_ix..end_ix]);
1908
1909 let mut actual_text = String::new();
1910 actual
1911 .bytes_in_range(start_ix..end_ix)
1912 .read_to_string(&mut actual_text)
1913 .unwrap();
1914 assert_eq!(actual_text, &expected[start_ix..end_ix]);
1915
1916 assert_eq!(
1917 actual
1918 .reversed_chunks_in_range(start_ix..end_ix)
1919 .collect::<Vec<&str>>()
1920 .into_iter()
1921 .rev()
1922 .collect::<String>(),
1923 &expected[start_ix..end_ix]
1924 );
1925
1926 let mut expected_line_starts: Vec<_> = expected[start_ix..end_ix]
1927 .match_indices('\n')
1928 .map(|(index, _)| start_ix + index + 1)
1929 .collect();
1930
1931 let mut chunks = actual.chunks_in_range(start_ix..end_ix);
1932
1933 let mut actual_line_starts = Vec::new();
1934 while chunks.next_line() {
1935 actual_line_starts.push(chunks.offset());
1936 }
1937 assert_eq!(
1938 actual_line_starts,
1939 expected_line_starts,
1940 "actual line starts != expected line starts when using next_line() for {:?} ({:?})",
1941 &expected[start_ix..end_ix],
1942 start_ix..end_ix
1943 );
1944
1945 if start_ix < end_ix
1946 && (start_ix == 0 || expected.as_bytes()[start_ix - 1] == b'\n')
1947 {
1948 expected_line_starts.insert(0, start_ix);
1949 }
1950 // Remove the last index if it starts at the end of the range.
1951 if expected_line_starts.last() == Some(&end_ix) {
1952 expected_line_starts.pop();
1953 }
1954
1955 let mut actual_line_starts = Vec::new();
1956 while chunks.prev_line() {
1957 actual_line_starts.push(chunks.offset());
1958 }
1959 actual_line_starts.reverse();
1960 assert_eq!(
1961 actual_line_starts,
1962 expected_line_starts,
1963 "actual line starts != expected line starts when using prev_line() for {:?} ({:?})",
1964 &expected[start_ix..end_ix],
1965 start_ix..end_ix
1966 );
1967
1968 // Check that next_line/prev_line work correctly from random positions
1969 let mut offset = rng.random_range(start_ix..=end_ix);
1970 while !expected.is_char_boundary(offset) {
1971 offset -= 1;
1972 }
1973 chunks.seek(offset);
1974
1975 for _ in 0..5 {
1976 if rng.random() {
1977 let expected_next_line_start = expected[offset..end_ix]
1978 .find('\n')
1979 .map(|newline_ix| offset + newline_ix + 1);
1980
1981 let moved = chunks.next_line();
1982 assert_eq!(
1983 moved,
1984 expected_next_line_start.is_some(),
1985 "unexpected result from next_line after seeking to {} in range {:?} ({:?})",
1986 offset,
1987 start_ix..end_ix,
1988 &expected[start_ix..end_ix]
1989 );
1990 if let Some(expected_next_line_start) = expected_next_line_start {
1991 assert_eq!(
1992 chunks.offset(),
1993 expected_next_line_start,
1994 "invalid position after seeking to {} in range {:?} ({:?})",
1995 offset,
1996 start_ix..end_ix,
1997 &expected[start_ix..end_ix]
1998 );
1999 } else {
2000 assert_eq!(
2001 chunks.offset(),
2002 end_ix,
2003 "invalid position after seeking to {} in range {:?} ({:?})",
2004 offset,
2005 start_ix..end_ix,
2006 &expected[start_ix..end_ix]
2007 );
2008 }
2009 } else {
2010 let search_end = if offset > 0 && expected.as_bytes()[offset - 1] == b'\n' {
2011 offset - 1
2012 } else {
2013 offset
2014 };
2015
2016 let expected_prev_line_start = expected[..search_end]
2017 .rfind('\n')
2018 .and_then(|newline_ix| {
2019 let line_start_ix = newline_ix + 1;
2020 if line_start_ix >= start_ix {
2021 Some(line_start_ix)
2022 } else {
2023 None
2024 }
2025 })
2026 .or({
2027 if offset > 0 && start_ix == 0 {
2028 Some(0)
2029 } else {
2030 None
2031 }
2032 });
2033
2034 let moved = chunks.prev_line();
2035 assert_eq!(
2036 moved,
2037 expected_prev_line_start.is_some(),
2038 "unexpected result from prev_line after seeking to {} in range {:?} ({:?})",
2039 offset,
2040 start_ix..end_ix,
2041 &expected[start_ix..end_ix]
2042 );
2043 if let Some(expected_prev_line_start) = expected_prev_line_start {
2044 assert_eq!(
2045 chunks.offset(),
2046 expected_prev_line_start,
2047 "invalid position after seeking to {} in range {:?} ({:?})",
2048 offset,
2049 start_ix..end_ix,
2050 &expected[start_ix..end_ix]
2051 );
2052 } else {
2053 assert_eq!(
2054 chunks.offset(),
2055 start_ix,
2056 "invalid position after seeking to {} in range {:?} ({:?})",
2057 offset,
2058 start_ix..end_ix,
2059 &expected[start_ix..end_ix]
2060 );
2061 }
2062 }
2063
2064 assert!((start_ix..=end_ix).contains(&chunks.offset()));
2065 if rng.random() {
2066 offset = rng.random_range(start_ix..=end_ix);
2067 while !expected.is_char_boundary(offset) {
2068 offset -= 1;
2069 }
2070 chunks.seek(offset);
2071 } else {
2072 chunks.next();
2073 offset = chunks.offset();
2074 assert!((start_ix..=end_ix).contains(&chunks.offset()));
2075 }
2076 }
2077 }
2078
2079 let mut offset_utf16 = OffsetUtf16(0);
2080 let mut point = Point::new(0, 0);
2081 let mut point_utf16 = PointUtf16::new(0, 0);
2082 for (ix, ch) in expected.char_indices().chain(Some((expected.len(), '\0'))) {
2083 assert_eq!(actual.offset_to_point(ix), point, "offset_to_point({})", ix);
2084 assert_eq!(
2085 actual.offset_to_point_utf16(ix),
2086 point_utf16,
2087 "offset_to_point_utf16({})",
2088 ix
2089 );
2090 assert_eq!(
2091 actual.point_to_offset(point),
2092 ix,
2093 "point_to_offset({:?})",
2094 point
2095 );
2096 assert_eq!(
2097 actual.point_utf16_to_offset(point_utf16),
2098 ix,
2099 "point_utf16_to_offset({:?})",
2100 point_utf16
2101 );
2102 assert_eq!(
2103 actual.offset_to_offset_utf16(ix),
2104 offset_utf16,
2105 "offset_to_offset_utf16({:?})",
2106 ix
2107 );
2108 assert_eq!(
2109 actual.offset_utf16_to_offset(offset_utf16),
2110 ix,
2111 "offset_utf16_to_offset({:?})",
2112 offset_utf16
2113 );
2114 if ch == '\n' {
2115 point += Point::new(1, 0);
2116 point_utf16 += PointUtf16::new(1, 0);
2117 } else {
2118 point.column += ch.len_utf8() as u32;
2119 point_utf16.column += ch.len_utf16() as u32;
2120 }
2121 offset_utf16.0 += ch.len_utf16();
2122 }
2123
2124 let mut offset_utf16 = OffsetUtf16(0);
2125 let mut point_utf16 = Unclipped(PointUtf16::zero());
2126 for unit in expected.encode_utf16() {
2127 let left_offset = actual.clip_offset_utf16(offset_utf16, Bias::Left);
2128 let right_offset = actual.clip_offset_utf16(offset_utf16, Bias::Right);
2129 assert!(right_offset >= left_offset);
2130 // Ensure translating UTF-16 offsets to UTF-8 offsets doesn't panic.
2131 actual.offset_utf16_to_offset(left_offset);
2132 actual.offset_utf16_to_offset(right_offset);
2133
2134 let left_point = actual.clip_point_utf16(point_utf16, Bias::Left);
2135 let right_point = actual.clip_point_utf16(point_utf16, Bias::Right);
2136 assert!(right_point >= left_point);
2137 // Ensure translating valid UTF-16 points to offsets doesn't panic.
2138 actual.point_utf16_to_offset(left_point);
2139 actual.point_utf16_to_offset(right_point);
2140
2141 offset_utf16.0 += 1;
2142 if unit == b'\n' as u16 {
2143 point_utf16.0 += PointUtf16::new(1, 0);
2144 } else {
2145 point_utf16.0 += PointUtf16::new(0, 1);
2146 }
2147 }
2148
2149 for _ in 0..5 {
2150 let end_ix = clip_offset(&expected, rng.random_range(0..=expected.len()), Right);
2151 let start_ix = clip_offset(&expected, rng.random_range(0..=end_ix), Left);
2152 assert_eq!(
2153 actual.cursor(start_ix).summary::<TextSummary>(end_ix),
2154 TextSummary::from(&expected[start_ix..end_ix])
2155 );
2156 }
2157
2158 let mut expected_longest_rows = Vec::new();
2159 let mut longest_line_len = -1_isize;
2160 for (row, line) in expected.split('\n').enumerate() {
2161 let row = row as u32;
2162 assert_eq!(
2163 actual.line_len(row),
2164 line.len() as u32,
2165 "invalid line len for row {}",
2166 row
2167 );
2168
2169 let line_char_count = line.chars().count() as isize;
2170 match line_char_count.cmp(&longest_line_len) {
2171 Ordering::Less => {}
2172 Ordering::Equal => expected_longest_rows.push(row),
2173 Ordering::Greater => {
2174 longest_line_len = line_char_count;
2175 expected_longest_rows.clear();
2176 expected_longest_rows.push(row);
2177 }
2178 }
2179 }
2180
2181 let longest_row = actual.summary().longest_row;
2182 assert!(
2183 expected_longest_rows.contains(&longest_row),
2184 "incorrect longest row {}. expected {:?} with length {}",
2185 longest_row,
2186 expected_longest_rows,
2187 longest_line_len,
2188 );
2189 }
2190 }
2191
2192 #[test]
2193 fn test_chunks_equals_str() {
2194 let text = "This is a multi-chunk\n& multi-line test string!";
2195 let rope = Rope::from(text);
2196 for start in 0..text.len() {
2197 for end in start..text.len() {
2198 let range = start..end;
2199 let correct_substring = &text[start..end];
2200
2201 // Test that correct range returns true
2202 assert!(
2203 rope.chunks_in_range(range.clone())
2204 .equals_str(correct_substring)
2205 );
2206 assert!(
2207 rope.reversed_chunks_in_range(range.clone())
2208 .equals_str(correct_substring)
2209 );
2210
2211 // Test that all other ranges return false (unless they happen to match)
2212 for other_start in 0..text.len() {
2213 for other_end in other_start..text.len() {
2214 if other_start == start && other_end == end {
2215 continue;
2216 }
2217 let other_substring = &text[other_start..other_end];
2218
2219 // Only assert false if the substrings are actually different
2220 if other_substring == correct_substring {
2221 continue;
2222 }
2223 assert!(
2224 !rope
2225 .chunks_in_range(range.clone())
2226 .equals_str(other_substring)
2227 );
2228 assert!(
2229 !rope
2230 .reversed_chunks_in_range(range.clone())
2231 .equals_str(other_substring)
2232 );
2233 }
2234 }
2235 }
2236 }
2237
2238 let rope = Rope::from("");
2239 assert!(rope.chunks_in_range(0..0).equals_str(""));
2240 assert!(rope.reversed_chunks_in_range(0..0).equals_str(""));
2241 assert!(!rope.chunks_in_range(0..0).equals_str("foo"));
2242 assert!(!rope.reversed_chunks_in_range(0..0).equals_str("foo"));
2243 }
2244
2245 #[test]
2246 fn test_starts_with() {
2247 let text = "Hello, world! 🌍🌎🌏";
2248 let rope = Rope::from(text);
2249
2250 assert!(rope.starts_with(""));
2251 assert!(rope.starts_with("H"));
2252 assert!(rope.starts_with("Hello"));
2253 assert!(rope.starts_with("Hello, world! 🌍🌎🌏"));
2254 assert!(!rope.starts_with("ello"));
2255 assert!(!rope.starts_with("Hello, world! 🌍🌎🌏!"));
2256
2257 let empty_rope = Rope::from("");
2258 assert!(empty_rope.starts_with(""));
2259 assert!(!empty_rope.starts_with("a"));
2260 }
2261
2262 #[test]
2263 fn test_ends_with() {
2264 let text = "Hello, world! 🌍🌎🌏";
2265 let rope = Rope::from(text);
2266
2267 assert!(rope.ends_with(""));
2268 assert!(rope.ends_with("🌏"));
2269 assert!(rope.ends_with("🌍🌎🌏"));
2270 assert!(rope.ends_with("Hello, world! 🌍🌎🌏"));
2271 assert!(!rope.ends_with("🌎"));
2272 assert!(!rope.ends_with("!Hello, world! 🌍🌎🌏"));
2273
2274 let empty_rope = Rope::from("");
2275 assert!(empty_rope.ends_with(""));
2276 assert!(!empty_rope.ends_with("a"));
2277 }
2278
2279 #[test]
2280 fn test_starts_with_ends_with_random() {
2281 let mut rng = StdRng::seed_from_u64(0);
2282 for _ in 0..100 {
2283 let len = rng.random_range(0..100);
2284 let text: String = RandomCharIter::new(&mut rng).take(len).collect();
2285 let rope = Rope::from(text.as_str());
2286
2287 for _ in 0..10 {
2288 let start = rng.random_range(0..=text.len());
2289 let start = text.ceil_char_boundary(start);
2290 let end = rng.random_range(start..=text.len());
2291 let end = text.ceil_char_boundary(end);
2292 let prefix = &text[..end];
2293 let suffix = &text[start..];
2294
2295 assert_eq!(
2296 rope.starts_with(prefix),
2297 text.starts_with(prefix),
2298 "starts_with mismatch for {:?} in {:?}",
2299 prefix,
2300 text
2301 );
2302 assert_eq!(
2303 rope.ends_with(suffix),
2304 text.ends_with(suffix),
2305 "ends_with mismatch for {:?} in {:?}",
2306 suffix,
2307 text
2308 );
2309 }
2310 }
2311 }
2312
2313 #[test]
2314 fn test_is_char_boundary() {
2315 let fixture = "地";
2316 let rope = Rope::from("地");
2317 for b in 0..=fixture.len() {
2318 assert_eq!(rope.is_char_boundary(b), fixture.is_char_boundary(b));
2319 }
2320 let fixture = "";
2321 let rope = Rope::from("");
2322 for b in 0..=fixture.len() {
2323 assert_eq!(rope.is_char_boundary(b), fixture.is_char_boundary(b));
2324 }
2325 let fixture = "🔴🟠🟡🟢🔵🟣⚫️⚪️🟤\n🏳️⚧️🏁🏳️🌈🏴☠️⛳️📬📭🏴🏳️🚩";
2326 let rope = Rope::from("🔴🟠🟡🟢🔵🟣⚫️⚪️🟤\n🏳️⚧️🏁🏳️🌈🏴☠️⛳️📬📭🏴🏳️🚩");
2327 for b in 0..=fixture.len() {
2328 assert_eq!(rope.is_char_boundary(b), fixture.is_char_boundary(b));
2329 }
2330 }
2331
2332 #[test]
2333 fn test_floor_char_boundary() {
2334 let fixture = "地";
2335 let rope = Rope::from("地");
2336 for b in 0..=fixture.len() {
2337 assert_eq!(rope.floor_char_boundary(b), fixture.floor_char_boundary(b));
2338 }
2339
2340 let fixture = "";
2341 let rope = Rope::from("");
2342 for b in 0..=fixture.len() {
2343 assert_eq!(rope.floor_char_boundary(b), fixture.floor_char_boundary(b));
2344 }
2345
2346 let fixture = "🔴🟠🟡🟢🔵🟣⚫️⚪️🟤\n🏳️⚧️🏁🏳️🌈🏴☠️⛳️📬📭🏴🏳️🚩";
2347 let rope = Rope::from("🔴🟠🟡🟢🔵🟣⚫️⚪️🟤\n🏳️⚧️🏁🏳️🌈🏴☠️⛳️📬📭🏴🏳️🚩");
2348 for b in 0..=fixture.len() {
2349 assert_eq!(rope.floor_char_boundary(b), fixture.floor_char_boundary(b));
2350 }
2351 }
2352
2353 #[test]
2354 fn test_ceil_char_boundary() {
2355 let fixture = "地";
2356 let rope = Rope::from("地");
2357 for b in 0..=fixture.len() {
2358 assert_eq!(rope.ceil_char_boundary(b), fixture.ceil_char_boundary(b));
2359 }
2360
2361 let fixture = "";
2362 let rope = Rope::from("");
2363 for b in 0..=fixture.len() {
2364 assert_eq!(rope.ceil_char_boundary(b), fixture.ceil_char_boundary(b));
2365 }
2366
2367 let fixture = "🔴🟠🟡🟢🔵🟣⚫️⚪️🟤\n🏳️⚧️🏁🏳️🌈🏴☠️⛳️📬📭🏴🏳️🚩";
2368 let rope = Rope::from("🔴🟠🟡🟢🔵🟣⚫️⚪️🟤\n🏳️⚧️🏁🏳️🌈🏴☠️⛳️📬📭🏴🏳️🚩");
2369 for b in 0..=fixture.len() {
2370 assert_eq!(rope.ceil_char_boundary(b), fixture.ceil_char_boundary(b));
2371 }
2372 }
2373
2374 #[test]
2375 fn test_push_front_empty_text_on_empty_rope() {
2376 let mut rope = Rope::new();
2377 rope.push_front("");
2378 assert_eq!(rope.text(), "");
2379 assert_eq!(rope.len(), 0);
2380 }
2381
2382 #[test]
2383 fn test_push_front_empty_text_on_nonempty_rope() {
2384 let mut rope = Rope::from("hello");
2385 rope.push_front("");
2386 assert_eq!(rope.text(), "hello");
2387 }
2388
2389 #[test]
2390 fn test_push_front_on_empty_rope() {
2391 let mut rope = Rope::new();
2392 rope.push_front("hello");
2393 assert_eq!(rope.text(), "hello");
2394 assert_eq!(rope.len(), 5);
2395 assert_eq!(rope.max_point(), Point::new(0, 5));
2396 }
2397
2398 #[test]
2399 fn test_push_front_single_space() {
2400 let mut rope = Rope::from("hint");
2401 rope.push_front(" ");
2402 assert_eq!(rope.text(), " hint");
2403 assert_eq!(rope.len(), 5);
2404 }
2405
2406 #[gpui::test(iterations = 50)]
2407 fn test_push_front_random(mut rng: StdRng) {
2408 let initial_len = rng.random_range(0..=64);
2409 let initial_text: String = RandomCharIter::new(&mut rng).take(initial_len).collect();
2410 let mut rope = Rope::from(initial_text.as_str());
2411
2412 let mut expected = initial_text;
2413
2414 for _ in 0..rng.random_range(1..=10) {
2415 let prefix_len = rng.random_range(0..=32);
2416 let prefix: String = RandomCharIter::new(&mut rng).take(prefix_len).collect();
2417
2418 rope.push_front(&prefix);
2419 expected.insert_str(0, &prefix);
2420
2421 assert_eq!(
2422 rope.text(),
2423 expected,
2424 "text mismatch after push_front({:?})",
2425 prefix
2426 );
2427 assert_eq!(rope.len(), expected.len());
2428
2429 let actual_summary = rope.summary();
2430 let expected_summary = TextSummary::from(expected.as_str());
2431 assert_eq!(
2432 actual_summary.len, expected_summary.len,
2433 "len mismatch for {:?}",
2434 expected
2435 );
2436 assert_eq!(
2437 actual_summary.lines, expected_summary.lines,
2438 "lines mismatch for {:?}",
2439 expected
2440 );
2441 assert_eq!(
2442 actual_summary.chars, expected_summary.chars,
2443 "chars mismatch for {:?}",
2444 expected
2445 );
2446 assert_eq!(
2447 actual_summary.longest_row, expected_summary.longest_row,
2448 "longest_row mismatch for {:?}",
2449 expected
2450 );
2451
2452 // Verify offset-to-point and point-to-offset round-trip at boundaries.
2453 for (ix, _) in expected.char_indices().chain(Some((expected.len(), '\0'))) {
2454 assert_eq!(
2455 rope.point_to_offset(rope.offset_to_point(ix)),
2456 ix,
2457 "offset round-trip failed at {} for {:?}",
2458 ix,
2459 expected
2460 );
2461 }
2462 }
2463 }
2464
2465 #[gpui::test(iterations = 50)]
2466 fn test_push_front_large_prefix(mut rng: StdRng) {
2467 let initial_len = rng.random_range(0..=32);
2468 let initial_text: String = RandomCharIter::new(&mut rng).take(initial_len).collect();
2469 let mut rope = Rope::from(initial_text.as_str());
2470
2471 let prefix_len = rng.random_range(64..=256);
2472 let prefix: String = RandomCharIter::new(&mut rng).take(prefix_len).collect();
2473
2474 rope.push_front(&prefix);
2475 let expected = format!("{}{}", prefix, initial_text);
2476
2477 assert_eq!(rope.text(), expected);
2478 assert_eq!(rope.len(), expected.len());
2479
2480 let actual_summary = rope.summary();
2481 let expected_summary = TextSummary::from(expected.as_str());
2482 assert_eq!(actual_summary.len, expected_summary.len);
2483 assert_eq!(actual_summary.lines, expected_summary.lines);
2484 assert_eq!(actual_summary.chars, expected_summary.chars);
2485 }
2486
2487 fn clip_offset(text: &str, mut offset: usize, bias: Bias) -> usize {
2488 while !text.is_char_boundary(offset) {
2489 match bias {
2490 Bias::Left => offset -= 1,
2491 Bias::Right => offset += 1,
2492 }
2493 }
2494 offset
2495 }
2496
2497 impl Rope {
2498 fn text(&self) -> String {
2499 let mut text = String::new();
2500 for chunk in self.chunks.cursor::<()>(()) {
2501 text.push_str(&chunk.text);
2502 }
2503 text
2504 }
2505 }
2506}