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 debug_assert!(end_offset >= self.offset);
697
698 self.chunks.seek_forward(&end_offset, Bias::Right);
699 self.offset = end_offset;
700 }
701
702 pub fn slice(&mut self, end_offset: usize) -> Rope {
703 debug_assert!(
704 end_offset >= self.offset,
705 "cannot slice backwards from {} to {}",
706 self.offset,
707 end_offset
708 );
709
710 let mut slice = Rope::new();
711 if let Some(start_chunk) = self.chunks.item() {
712 let start_ix = self.offset - self.chunks.start();
713 let end_ix = cmp::min(end_offset, self.chunks.end()) - self.chunks.start();
714 slice.push_chunk(start_chunk.slice(start_ix..end_ix));
715 }
716
717 if end_offset > self.chunks.end() {
718 self.chunks.next();
719 slice.append(Rope {
720 chunks: self.chunks.slice(&end_offset, Bias::Right),
721 });
722 if let Some(end_chunk) = self.chunks.item() {
723 let end_ix = end_offset - self.chunks.start();
724 slice.push_chunk(end_chunk.slice(0..end_ix));
725 }
726 }
727
728 self.offset = end_offset;
729 slice
730 }
731
732 pub fn summary<D: TextDimension>(&mut self, end_offset: usize) -> D {
733 debug_assert!(end_offset >= self.offset);
734
735 let mut summary = D::zero(());
736 if let Some(start_chunk) = self.chunks.item() {
737 let start_ix = self.offset - self.chunks.start();
738 let end_ix = cmp::min(end_offset, self.chunks.end()) - self.chunks.start();
739 summary.add_assign(&D::from_chunk(start_chunk.slice(start_ix..end_ix)));
740 }
741
742 if end_offset > self.chunks.end() {
743 self.chunks.next();
744 summary.add_assign(&self.chunks.summary(&end_offset, Bias::Right));
745 if let Some(end_chunk) = self.chunks.item() {
746 let end_ix = end_offset - self.chunks.start();
747 summary.add_assign(&D::from_chunk(end_chunk.slice(0..end_ix)));
748 }
749 }
750
751 self.offset = end_offset;
752 summary
753 }
754
755 pub fn suffix(mut self) -> Rope {
756 self.slice(self.rope.chunks.extent(()))
757 }
758
759 pub fn offset(&self) -> usize {
760 self.offset
761 }
762}
763
764pub struct ChunkBitmaps<'a> {
765 /// A slice of text up to 128 bytes in size
766 pub text: &'a str,
767 /// Bitmap of character locations in text. LSB ordered
768 pub chars: Bitmap,
769 /// Bitmap of tab locations in text. LSB ordered
770 pub tabs: Bitmap,
771 /// Bitmap of newlines location in text. LSB ordered
772 pub newlines: Bitmap,
773}
774
775#[derive(Clone)]
776pub struct Chunks<'a> {
777 chunks: sum_tree::Cursor<'a, 'static, Chunk, usize>,
778 range: Range<usize>,
779 offset: usize,
780 reversed: bool,
781}
782
783impl<'a> Chunks<'a> {
784 pub fn new(rope: &'a Rope, range: Range<usize>, reversed: bool) -> Self {
785 let mut chunks = rope.chunks.cursor(());
786 let offset = if reversed {
787 chunks.seek(&range.end, Bias::Left);
788 range.end
789 } else {
790 chunks.seek(&range.start, Bias::Right);
791 range.start
792 };
793 let chunk_offset = offset - chunks.start();
794 if let Some(chunk) = chunks.item() {
795 chunk.assert_char_boundary::<true>(chunk_offset);
796 }
797 Self {
798 chunks,
799 range,
800 offset,
801 reversed,
802 }
803 }
804
805 fn offset_is_valid(&self) -> bool {
806 if self.reversed {
807 if self.offset <= self.range.start || self.offset > self.range.end {
808 return false;
809 }
810 } else if self.offset < self.range.start || self.offset >= self.range.end {
811 return false;
812 }
813
814 true
815 }
816
817 pub fn offset(&self) -> usize {
818 self.offset
819 }
820
821 pub fn seek(&mut self, mut offset: usize) {
822 offset = offset.clamp(self.range.start, self.range.end);
823
824 if self.reversed {
825 if offset > self.chunks.end() {
826 self.chunks.seek_forward(&offset, Bias::Left);
827 } else if offset <= *self.chunks.start() {
828 self.chunks.seek(&offset, Bias::Left);
829 }
830 } else {
831 if offset >= self.chunks.end() {
832 self.chunks.seek_forward(&offset, Bias::Right);
833 } else if offset < *self.chunks.start() {
834 self.chunks.seek(&offset, Bias::Right);
835 }
836 };
837
838 self.offset = offset;
839 }
840
841 pub fn set_range(&mut self, range: Range<usize>) {
842 self.range = range.clone();
843 self.seek(range.start);
844 }
845
846 /// Moves this cursor to the start of the next line in the rope.
847 ///
848 /// This method advances the cursor to the beginning of the next line.
849 /// If the cursor is already at the end of the rope, this method does nothing.
850 /// Reversed chunks iterators are not currently supported and will panic.
851 ///
852 /// Returns `true` if the cursor was successfully moved to the next line start,
853 /// or `false` if the cursor was already at the end of the rope.
854 pub fn next_line(&mut self) -> bool {
855 assert!(!self.reversed);
856
857 let mut found = false;
858 if let Some(chunk) = self.peek() {
859 if let Some(newline_ix) = chunk.find('\n') {
860 self.offset += newline_ix + 1;
861 found = self.offset <= self.range.end;
862 } else {
863 self.chunks
864 .search_forward(|summary| summary.text.lines.row > 0);
865 self.offset = *self.chunks.start();
866
867 if let Some(newline_ix) = self.peek().and_then(|chunk| chunk.find('\n')) {
868 self.offset += newline_ix + 1;
869 found = self.offset <= self.range.end;
870 } else {
871 self.offset = self.chunks.end();
872 }
873 }
874
875 if self.offset == self.chunks.end() {
876 self.next();
877 }
878 }
879
880 if self.offset > self.range.end {
881 self.offset = cmp::min(self.offset, self.range.end);
882 self.chunks.seek(&self.offset, Bias::Right);
883 }
884
885 found
886 }
887
888 /// Move this cursor to the preceding position in the rope that starts a new line.
889 /// Reversed chunks iterators are not currently supported and will panic.
890 ///
891 /// If this cursor is not on the start of a line, it will be moved to the start of
892 /// its current line. Otherwise it will be moved to the start of the previous line.
893 /// It updates the cursor's position and returns true if a previous line was found,
894 /// or false if the cursor was already at the start of the rope.
895 pub fn prev_line(&mut self) -> bool {
896 assert!(!self.reversed);
897
898 let initial_offset = self.offset;
899
900 if self.offset == *self.chunks.start() {
901 self.chunks.prev();
902 }
903
904 if let Some(chunk) = self.chunks.item() {
905 let mut end_ix = self.offset - *self.chunks.start();
906 if chunk.text.as_bytes()[end_ix - 1] == b'\n' {
907 end_ix -= 1;
908 }
909
910 if let Some(newline_ix) = chunk.text[..end_ix].rfind('\n') {
911 self.offset = *self.chunks.start() + newline_ix + 1;
912 if self.offset_is_valid() {
913 return true;
914 }
915 }
916 }
917
918 self.chunks
919 .search_backward(|summary| summary.text.lines.row > 0);
920 self.offset = *self.chunks.start();
921 if let Some(chunk) = self.chunks.item()
922 && let Some(newline_ix) = chunk.text.rfind('\n')
923 {
924 self.offset += newline_ix + 1;
925 if self.offset_is_valid() {
926 if self.offset == self.chunks.end() {
927 self.chunks.next();
928 }
929
930 return true;
931 }
932 }
933
934 if !self.offset_is_valid() || self.chunks.item().is_none() {
935 self.offset = self.range.start;
936 self.chunks.seek(&self.offset, Bias::Right);
937 }
938
939 self.offset < initial_offset && self.offset == 0
940 }
941
942 pub fn peek(&self) -> Option<&'a str> {
943 if !self.offset_is_valid() {
944 return None;
945 }
946
947 let chunk = self.chunks.item()?;
948 let chunk_start = *self.chunks.start();
949 let slice_range = if self.reversed {
950 let slice_start = cmp::max(chunk_start, self.range.start) - chunk_start;
951 let slice_end = self.offset - chunk_start;
952 slice_start..slice_end
953 } else {
954 let slice_start = self.offset - chunk_start;
955 let slice_end = cmp::min(self.chunks.end(), self.range.end) - chunk_start;
956 slice_start..slice_end
957 };
958
959 Some(&chunk.text[slice_range])
960 }
961
962 /// Returns bitmaps that represent character positions and tab positions
963 pub fn peek_with_bitmaps(&self) -> Option<ChunkBitmaps<'a>> {
964 if !self.offset_is_valid() {
965 return None;
966 }
967
968 let chunk = self.chunks.item()?;
969 let chunk_start = *self.chunks.start();
970 let slice_range = if self.reversed {
971 let slice_start = cmp::max(chunk_start, self.range.start) - chunk_start;
972 let slice_end = self.offset - chunk_start;
973 slice_start..slice_end
974 } else {
975 let slice_start = self.offset - chunk_start;
976 let slice_end = cmp::min(self.chunks.end(), self.range.end) - chunk_start;
977 slice_start..slice_end
978 };
979 let chunk_start_offset = slice_range.start;
980 let slice_text = &chunk.text[slice_range];
981
982 // Shift the tabs to align with our slice window
983 let shifted_tabs = chunk.tabs() >> chunk_start_offset;
984 let shifted_chars = chunk.chars() >> chunk_start_offset;
985 let shifted_newlines = chunk.newlines() >> chunk_start_offset;
986
987 Some(ChunkBitmaps {
988 text: slice_text,
989 chars: shifted_chars,
990 tabs: shifted_tabs,
991 newlines: shifted_newlines,
992 })
993 }
994
995 pub fn lines(self) -> Lines<'a> {
996 let reversed = self.reversed;
997 Lines {
998 chunks: self,
999 current_line: String::new(),
1000 done: false,
1001 reversed,
1002 }
1003 }
1004
1005 pub fn equals_str(&self, other: &str) -> bool {
1006 let chunk = self.clone();
1007 if chunk.reversed {
1008 let mut offset = other.len();
1009 for chunk in chunk {
1010 if other[0..offset].ends_with(chunk) {
1011 offset -= chunk.len();
1012 } else {
1013 return false;
1014 }
1015 }
1016 if offset != 0 {
1017 return false;
1018 }
1019 } else {
1020 let mut offset = 0;
1021 for chunk in chunk {
1022 if offset >= other.len() {
1023 return false;
1024 }
1025 if other[offset..].starts_with(chunk) {
1026 offset += chunk.len();
1027 } else {
1028 return false;
1029 }
1030 }
1031 if offset != other.len() {
1032 return false;
1033 }
1034 }
1035
1036 true
1037 }
1038}
1039
1040pub struct ChunkWithBitmaps<'a>(pub Chunks<'a>);
1041
1042impl<'a> Iterator for ChunkWithBitmaps<'a> {
1043 /// text, chars bitmap, tabs bitmap
1044 type Item = ChunkBitmaps<'a>;
1045
1046 fn next(&mut self) -> Option<Self::Item> {
1047 let chunk_bitmaps = self.0.peek_with_bitmaps()?;
1048 if self.0.reversed {
1049 self.0.offset -= chunk_bitmaps.text.len();
1050 if self.0.offset <= *self.0.chunks.start() {
1051 self.0.chunks.prev();
1052 }
1053 } else {
1054 self.0.offset += chunk_bitmaps.text.len();
1055 if self.0.offset >= self.0.chunks.end() {
1056 self.0.chunks.next();
1057 }
1058 }
1059
1060 Some(chunk_bitmaps)
1061 }
1062}
1063
1064impl<'a> Iterator for Chunks<'a> {
1065 type Item = &'a str;
1066
1067 fn next(&mut self) -> Option<Self::Item> {
1068 let chunk = self.peek()?;
1069 if self.reversed {
1070 self.offset -= chunk.len();
1071 if self.offset <= *self.chunks.start() {
1072 self.chunks.prev();
1073 }
1074 } else {
1075 self.offset += chunk.len();
1076 if self.offset >= self.chunks.end() {
1077 self.chunks.next();
1078 }
1079 }
1080
1081 Some(chunk)
1082 }
1083}
1084
1085pub struct Bytes<'a> {
1086 chunks: sum_tree::Cursor<'a, 'static, Chunk, usize>,
1087 range: Range<usize>,
1088 reversed: bool,
1089}
1090
1091impl<'a> Bytes<'a> {
1092 pub fn new(rope: &'a Rope, range: Range<usize>, reversed: bool) -> Self {
1093 let mut chunks = rope.chunks.cursor(());
1094 if reversed {
1095 chunks.seek(&range.end, Bias::Left);
1096 } else {
1097 chunks.seek(&range.start, Bias::Right);
1098 }
1099 Self {
1100 chunks,
1101 range,
1102 reversed,
1103 }
1104 }
1105
1106 pub fn peek(&self) -> Option<&'a [u8]> {
1107 let chunk = self.chunks.item()?;
1108 if self.reversed && self.range.start >= self.chunks.end() {
1109 return None;
1110 }
1111 let chunk_start = *self.chunks.start();
1112 if self.range.end <= chunk_start {
1113 return None;
1114 }
1115 let start = self.range.start.saturating_sub(chunk_start);
1116 let end = self.range.end - chunk_start;
1117 Some(&chunk.text.as_bytes()[start..chunk.text.len().min(end)])
1118 }
1119}
1120
1121impl<'a> Iterator for Bytes<'a> {
1122 type Item = &'a [u8];
1123
1124 fn next(&mut self) -> Option<Self::Item> {
1125 let result = self.peek();
1126 if result.is_some() {
1127 if self.reversed {
1128 self.chunks.prev();
1129 } else {
1130 self.chunks.next();
1131 }
1132 }
1133 result
1134 }
1135}
1136
1137impl io::Read for Bytes<'_> {
1138 fn read(&mut self, buf: &mut [u8]) -> io::Result<usize> {
1139 if let Some(chunk) = self.peek() {
1140 let len = cmp::min(buf.len(), chunk.len());
1141 if self.reversed {
1142 buf[..len].copy_from_slice(&chunk[chunk.len() - len..]);
1143 buf[..len].reverse();
1144 self.range.end -= len;
1145 } else {
1146 buf[..len].copy_from_slice(&chunk[..len]);
1147 self.range.start += len;
1148 }
1149
1150 if len == chunk.len() {
1151 if self.reversed {
1152 self.chunks.prev();
1153 } else {
1154 self.chunks.next();
1155 }
1156 }
1157 Ok(len)
1158 } else {
1159 Ok(0)
1160 }
1161 }
1162}
1163
1164pub struct Lines<'a> {
1165 chunks: Chunks<'a>,
1166 current_line: String,
1167 done: bool,
1168 reversed: bool,
1169}
1170
1171impl<'a> Lines<'a> {
1172 pub fn next(&mut self) -> Option<&str> {
1173 if self.done {
1174 return None;
1175 }
1176
1177 self.current_line.clear();
1178
1179 while let Some(chunk) = self.chunks.peek() {
1180 let chunk_lines = chunk.split('\n');
1181 if self.reversed {
1182 let mut chunk_lines = chunk_lines.rev().peekable();
1183 if let Some(chunk_line) = chunk_lines.next() {
1184 let done = chunk_lines.peek().is_some();
1185 if done {
1186 self.chunks
1187 .seek(self.chunks.offset() - chunk_line.len() - "\n".len());
1188 if self.current_line.is_empty() {
1189 return Some(chunk_line);
1190 }
1191 }
1192 self.current_line.insert_str(0, chunk_line);
1193 if done {
1194 return Some(&self.current_line);
1195 }
1196 }
1197 } else {
1198 let mut chunk_lines = chunk_lines.peekable();
1199 if let Some(chunk_line) = chunk_lines.next() {
1200 let done = chunk_lines.peek().is_some();
1201 if done {
1202 self.chunks
1203 .seek(self.chunks.offset() + chunk_line.len() + "\n".len());
1204 if self.current_line.is_empty() {
1205 return Some(chunk_line);
1206 }
1207 }
1208 self.current_line.push_str(chunk_line);
1209 if done {
1210 return Some(&self.current_line);
1211 }
1212 }
1213 }
1214
1215 self.chunks.next();
1216 }
1217
1218 self.done = true;
1219 Some(&self.current_line)
1220 }
1221
1222 pub fn seek(&mut self, offset: usize) {
1223 self.chunks.seek(offset);
1224 self.current_line.clear();
1225 self.done = false;
1226 }
1227
1228 pub fn offset(&self) -> usize {
1229 self.chunks.offset()
1230 }
1231}
1232
1233impl sum_tree::Item for Chunk {
1234 type Summary = ChunkSummary;
1235
1236 fn summary(&self, _cx: ()) -> Self::Summary {
1237 ChunkSummary {
1238 text: self.as_slice().text_summary(),
1239 }
1240 }
1241}
1242
1243#[derive(Clone, Debug, Default, Eq, PartialEq)]
1244pub struct ChunkSummary {
1245 text: TextSummary,
1246}
1247
1248impl sum_tree::ContextLessSummary for ChunkSummary {
1249 fn zero() -> Self {
1250 Default::default()
1251 }
1252
1253 fn add_summary(&mut self, summary: &Self) {
1254 self.text += &summary.text;
1255 }
1256}
1257
1258/// Summary of a string of text.
1259#[derive(Copy, Clone, Debug, Default, Eq, PartialEq)]
1260pub struct TextSummary {
1261 /// Length in bytes.
1262 pub len: usize,
1263 /// Length in UTF-8.
1264 pub chars: usize,
1265 /// Length in UTF-16 code units
1266 pub len_utf16: OffsetUtf16,
1267 /// A point representing the number of lines and the length of the last line.
1268 ///
1269 /// In other words, it marks the point after the last byte in the text, (if
1270 /// EOF was a character, this would be its position).
1271 pub lines: Point,
1272 /// How many `char`s are in the first line
1273 pub first_line_chars: u32,
1274 /// How many `char`s are in the last line
1275 pub last_line_chars: u32,
1276 /// How many UTF-16 code units are in the last line
1277 pub last_line_len_utf16: u32,
1278 /// The row idx of the longest row
1279 pub longest_row: u32,
1280 /// How many `char`s are in the longest row
1281 pub longest_row_chars: u32,
1282}
1283
1284impl TextSummary {
1285 pub fn lines_utf16(&self) -> PointUtf16 {
1286 PointUtf16 {
1287 row: self.lines.row,
1288 column: self.last_line_len_utf16,
1289 }
1290 }
1291
1292 pub fn newline() -> Self {
1293 Self {
1294 len: 1,
1295 chars: 1,
1296 len_utf16: OffsetUtf16(1),
1297 first_line_chars: 0,
1298 last_line_chars: 0,
1299 last_line_len_utf16: 0,
1300 lines: Point::new(1, 0),
1301 longest_row: 0,
1302 longest_row_chars: 0,
1303 }
1304 }
1305
1306 pub fn add_newline(&mut self) {
1307 self.len += 1;
1308 self.len_utf16 += OffsetUtf16(self.len_utf16.0 + 1);
1309 self.last_line_chars = 0;
1310 self.last_line_len_utf16 = 0;
1311 self.lines += Point::new(1, 0);
1312 }
1313}
1314
1315impl<'a> From<&'a str> for TextSummary {
1316 fn from(text: &'a str) -> Self {
1317 let mut len_utf16 = OffsetUtf16(0);
1318 let mut lines = Point::new(0, 0);
1319 let mut first_line_chars = 0;
1320 let mut last_line_chars = 0;
1321 let mut last_line_len_utf16 = 0;
1322 let mut longest_row = 0;
1323 let mut longest_row_chars = 0;
1324 let mut chars = 0;
1325 for c in text.chars() {
1326 chars += 1;
1327 len_utf16.0 += c.len_utf16();
1328
1329 if c == '\n' {
1330 lines += Point::new(1, 0);
1331 last_line_len_utf16 = 0;
1332 last_line_chars = 0;
1333 } else {
1334 lines.column += c.len_utf8() as u32;
1335 last_line_len_utf16 += c.len_utf16() as u32;
1336 last_line_chars += 1;
1337 }
1338
1339 if lines.row == 0 {
1340 first_line_chars = last_line_chars;
1341 }
1342
1343 if last_line_chars > longest_row_chars {
1344 longest_row = lines.row;
1345 longest_row_chars = last_line_chars;
1346 }
1347 }
1348
1349 TextSummary {
1350 len: text.len(),
1351 chars,
1352 len_utf16,
1353 lines,
1354 first_line_chars,
1355 last_line_chars,
1356 last_line_len_utf16,
1357 longest_row,
1358 longest_row_chars,
1359 }
1360 }
1361}
1362
1363impl sum_tree::ContextLessSummary for TextSummary {
1364 fn zero() -> Self {
1365 Default::default()
1366 }
1367
1368 fn add_summary(&mut self, summary: &Self) {
1369 *self += summary;
1370 }
1371}
1372
1373impl ops::Add<Self> for TextSummary {
1374 type Output = Self;
1375
1376 fn add(mut self, rhs: Self) -> Self::Output {
1377 AddAssign::add_assign(&mut self, &rhs);
1378 self
1379 }
1380}
1381
1382impl<'a> ops::AddAssign<&'a Self> for TextSummary {
1383 fn add_assign(&mut self, other: &'a Self) {
1384 let joined_chars = self.last_line_chars + other.first_line_chars;
1385 if joined_chars > self.longest_row_chars {
1386 self.longest_row = self.lines.row;
1387 self.longest_row_chars = joined_chars;
1388 }
1389 if other.longest_row_chars > self.longest_row_chars {
1390 self.longest_row = self.lines.row + other.longest_row;
1391 self.longest_row_chars = other.longest_row_chars;
1392 }
1393
1394 if self.lines.row == 0 {
1395 self.first_line_chars += other.first_line_chars;
1396 }
1397
1398 if other.lines.row == 0 {
1399 self.last_line_chars += other.first_line_chars;
1400 self.last_line_len_utf16 += other.last_line_len_utf16;
1401 } else {
1402 self.last_line_chars = other.last_line_chars;
1403 self.last_line_len_utf16 = other.last_line_len_utf16;
1404 }
1405
1406 self.chars += other.chars;
1407 self.len += other.len;
1408 self.len_utf16 += other.len_utf16;
1409 self.lines += other.lines;
1410 }
1411}
1412
1413impl ops::AddAssign<Self> for TextSummary {
1414 fn add_assign(&mut self, other: Self) {
1415 *self += &other;
1416 }
1417}
1418
1419pub trait TextDimension:
1420 'static + Clone + Copy + Default + for<'a> Dimension<'a, ChunkSummary> + std::fmt::Debug
1421{
1422 fn from_text_summary(summary: &TextSummary) -> Self;
1423 fn from_chunk(chunk: ChunkSlice) -> Self;
1424 fn add_assign(&mut self, other: &Self);
1425}
1426
1427impl<D1: TextDimension, D2: TextDimension> TextDimension for Dimensions<D1, D2, ()> {
1428 fn from_text_summary(summary: &TextSummary) -> Self {
1429 Dimensions(
1430 D1::from_text_summary(summary),
1431 D2::from_text_summary(summary),
1432 (),
1433 )
1434 }
1435
1436 fn from_chunk(chunk: ChunkSlice) -> Self {
1437 Dimensions(D1::from_chunk(chunk), D2::from_chunk(chunk), ())
1438 }
1439
1440 fn add_assign(&mut self, other: &Self) {
1441 self.0.add_assign(&other.0);
1442 self.1.add_assign(&other.1);
1443 }
1444}
1445
1446impl<'a> sum_tree::Dimension<'a, ChunkSummary> for TextSummary {
1447 fn zero(_cx: ()) -> Self {
1448 Default::default()
1449 }
1450
1451 fn add_summary(&mut self, summary: &'a ChunkSummary, _: ()) {
1452 *self += &summary.text;
1453 }
1454}
1455
1456impl TextDimension for TextSummary {
1457 fn from_text_summary(summary: &TextSummary) -> Self {
1458 *summary
1459 }
1460
1461 fn from_chunk(chunk: ChunkSlice) -> Self {
1462 chunk.text_summary()
1463 }
1464
1465 fn add_assign(&mut self, other: &Self) {
1466 *self += other;
1467 }
1468}
1469
1470impl<'a> sum_tree::Dimension<'a, ChunkSummary> for usize {
1471 fn zero(_cx: ()) -> Self {
1472 Default::default()
1473 }
1474
1475 fn add_summary(&mut self, summary: &'a ChunkSummary, _: ()) {
1476 *self += summary.text.len;
1477 }
1478}
1479
1480impl TextDimension for usize {
1481 fn from_text_summary(summary: &TextSummary) -> Self {
1482 summary.len
1483 }
1484
1485 fn from_chunk(chunk: ChunkSlice) -> Self {
1486 chunk.len()
1487 }
1488
1489 fn add_assign(&mut self, other: &Self) {
1490 *self += other;
1491 }
1492}
1493
1494impl<'a> sum_tree::Dimension<'a, ChunkSummary> for OffsetUtf16 {
1495 fn zero(_cx: ()) -> Self {
1496 Default::default()
1497 }
1498
1499 fn add_summary(&mut self, summary: &'a ChunkSummary, _: ()) {
1500 *self += summary.text.len_utf16;
1501 }
1502}
1503
1504impl TextDimension for OffsetUtf16 {
1505 fn from_text_summary(summary: &TextSummary) -> Self {
1506 summary.len_utf16
1507 }
1508
1509 fn from_chunk(chunk: ChunkSlice) -> Self {
1510 chunk.len_utf16()
1511 }
1512
1513 fn add_assign(&mut self, other: &Self) {
1514 *self += other;
1515 }
1516}
1517
1518impl<'a> sum_tree::Dimension<'a, ChunkSummary> for Point {
1519 fn zero(_cx: ()) -> Self {
1520 Default::default()
1521 }
1522
1523 fn add_summary(&mut self, summary: &'a ChunkSummary, _: ()) {
1524 *self += summary.text.lines;
1525 }
1526}
1527
1528impl TextDimension for Point {
1529 fn from_text_summary(summary: &TextSummary) -> Self {
1530 summary.lines
1531 }
1532
1533 fn from_chunk(chunk: ChunkSlice) -> Self {
1534 chunk.lines()
1535 }
1536
1537 fn add_assign(&mut self, other: &Self) {
1538 *self += other;
1539 }
1540}
1541
1542impl<'a> sum_tree::Dimension<'a, ChunkSummary> for PointUtf16 {
1543 fn zero(_cx: ()) -> Self {
1544 Default::default()
1545 }
1546
1547 fn add_summary(&mut self, summary: &'a ChunkSummary, _: ()) {
1548 *self += summary.text.lines_utf16();
1549 }
1550}
1551
1552impl TextDimension for PointUtf16 {
1553 fn from_text_summary(summary: &TextSummary) -> Self {
1554 summary.lines_utf16()
1555 }
1556
1557 fn from_chunk(chunk: ChunkSlice) -> Self {
1558 PointUtf16 {
1559 row: chunk.lines().row,
1560 column: chunk.last_line_len_utf16(),
1561 }
1562 }
1563
1564 fn add_assign(&mut self, other: &Self) {
1565 *self += other;
1566 }
1567}
1568
1569/// A pair of text dimensions in which only the first dimension is used for comparison,
1570/// but both dimensions are updated during addition and subtraction.
1571#[derive(Clone, Copy, Debug)]
1572pub struct DimensionPair<K, V> {
1573 pub key: K,
1574 pub value: Option<V>,
1575}
1576
1577impl<K: Default, V: Default> Default for DimensionPair<K, V> {
1578 fn default() -> Self {
1579 Self {
1580 key: Default::default(),
1581 value: Some(Default::default()),
1582 }
1583 }
1584}
1585
1586impl<K, V> cmp::Ord for DimensionPair<K, V>
1587where
1588 K: cmp::Ord,
1589{
1590 fn cmp(&self, other: &Self) -> cmp::Ordering {
1591 self.key.cmp(&other.key)
1592 }
1593}
1594
1595impl<K, V> cmp::PartialOrd for DimensionPair<K, V>
1596where
1597 K: cmp::PartialOrd,
1598{
1599 fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
1600 self.key.partial_cmp(&other.key)
1601 }
1602}
1603
1604impl<K, V> cmp::PartialEq for DimensionPair<K, V>
1605where
1606 K: cmp::PartialEq,
1607{
1608 fn eq(&self, other: &Self) -> bool {
1609 self.key.eq(&other.key)
1610 }
1611}
1612
1613impl<R, R2, K, V> ops::Sub for DimensionPair<K, V>
1614where
1615 K: ops::Sub<K, Output = R>,
1616 V: ops::Sub<V, Output = R2>,
1617{
1618 type Output = DimensionPair<R, R2>;
1619
1620 fn sub(self, rhs: Self) -> Self::Output {
1621 DimensionPair {
1622 key: self.key - rhs.key,
1623 value: self.value.zip(rhs.value).map(|(a, b)| a - b),
1624 }
1625 }
1626}
1627
1628impl<R, R2, K, V> ops::AddAssign<DimensionPair<R, R2>> for DimensionPair<K, V>
1629where
1630 K: ops::AddAssign<R>,
1631 V: ops::AddAssign<R2>,
1632{
1633 fn add_assign(&mut self, rhs: DimensionPair<R, R2>) {
1634 self.key += rhs.key;
1635 if let Some(value) = &mut self.value {
1636 if let Some(other_value) = rhs.value {
1637 *value += other_value;
1638 } else {
1639 self.value.take();
1640 }
1641 }
1642 }
1643}
1644
1645impl<D> std::ops::AddAssign<DimensionPair<Point, D>> for Point {
1646 fn add_assign(&mut self, rhs: DimensionPair<Point, D>) {
1647 *self += rhs.key;
1648 }
1649}
1650
1651impl<K, V> cmp::Eq for DimensionPair<K, V> where K: cmp::Eq {}
1652
1653impl<'a, K, V, S> sum_tree::Dimension<'a, S> for DimensionPair<K, V>
1654where
1655 S: sum_tree::Summary,
1656 K: sum_tree::Dimension<'a, S>,
1657 V: sum_tree::Dimension<'a, S>,
1658{
1659 fn zero(cx: S::Context<'_>) -> Self {
1660 Self {
1661 key: K::zero(cx),
1662 value: Some(V::zero(cx)),
1663 }
1664 }
1665
1666 fn add_summary(&mut self, summary: &'a S, cx: S::Context<'_>) {
1667 self.key.add_summary(summary, cx);
1668 if let Some(value) = &mut self.value {
1669 value.add_summary(summary, cx);
1670 }
1671 }
1672}
1673
1674impl<K, V> TextDimension for DimensionPair<K, V>
1675where
1676 K: TextDimension,
1677 V: TextDimension,
1678{
1679 fn add_assign(&mut self, other: &Self) {
1680 self.key.add_assign(&other.key);
1681 if let Some(value) = &mut self.value {
1682 if let Some(other_value) = other.value.as_ref() {
1683 value.add_assign(other_value);
1684 } else {
1685 self.value.take();
1686 }
1687 }
1688 }
1689
1690 fn from_chunk(chunk: ChunkSlice) -> Self {
1691 Self {
1692 key: K::from_chunk(chunk),
1693 value: Some(V::from_chunk(chunk)),
1694 }
1695 }
1696
1697 fn from_text_summary(summary: &TextSummary) -> Self {
1698 Self {
1699 key: K::from_text_summary(summary),
1700 value: Some(V::from_text_summary(summary)),
1701 }
1702 }
1703}
1704
1705#[cfg(test)]
1706mod tests {
1707 use super::*;
1708 use Bias::{Left, Right};
1709 use rand::prelude::*;
1710 use std::{cmp::Ordering, env, io::Read};
1711 use util::RandomCharIter;
1712
1713 #[ctor::ctor]
1714 fn init_logger() {
1715 zlog::init_test();
1716 }
1717
1718 #[test]
1719 fn test_all_4_byte_chars() {
1720 let mut rope = Rope::new();
1721 let text = "🏀".repeat(256);
1722 rope.push(&text);
1723 assert_eq!(rope.text(), text);
1724 }
1725
1726 #[test]
1727 fn test_clip() {
1728 let rope = Rope::from("🧘");
1729
1730 assert_eq!(rope.clip_offset(1, Bias::Left), 0);
1731 assert_eq!(rope.clip_offset(1, Bias::Right), 4);
1732 assert_eq!(rope.clip_offset(5, Bias::Right), 4);
1733
1734 assert_eq!(
1735 rope.clip_point(Point::new(0, 1), Bias::Left),
1736 Point::new(0, 0)
1737 );
1738 assert_eq!(
1739 rope.clip_point(Point::new(0, 1), Bias::Right),
1740 Point::new(0, 4)
1741 );
1742 assert_eq!(
1743 rope.clip_point(Point::new(0, 5), Bias::Right),
1744 Point::new(0, 4)
1745 );
1746
1747 assert_eq!(
1748 rope.clip_point_utf16(Unclipped(PointUtf16::new(0, 1)), Bias::Left),
1749 PointUtf16::new(0, 0)
1750 );
1751 assert_eq!(
1752 rope.clip_point_utf16(Unclipped(PointUtf16::new(0, 1)), Bias::Right),
1753 PointUtf16::new(0, 2)
1754 );
1755 assert_eq!(
1756 rope.clip_point_utf16(Unclipped(PointUtf16::new(0, 3)), Bias::Right),
1757 PointUtf16::new(0, 2)
1758 );
1759
1760 assert_eq!(
1761 rope.clip_offset_utf16(OffsetUtf16(1), Bias::Left),
1762 OffsetUtf16(0)
1763 );
1764 assert_eq!(
1765 rope.clip_offset_utf16(OffsetUtf16(1), Bias::Right),
1766 OffsetUtf16(2)
1767 );
1768 assert_eq!(
1769 rope.clip_offset_utf16(OffsetUtf16(3), Bias::Right),
1770 OffsetUtf16(2)
1771 );
1772 }
1773
1774 #[test]
1775 fn test_prev_next_line() {
1776 let rope = Rope::from("abc\ndef\nghi\njkl");
1777
1778 let mut chunks = rope.chunks();
1779 assert_eq!(chunks.peek().unwrap().chars().next().unwrap(), 'a');
1780
1781 assert!(chunks.next_line());
1782 assert_eq!(chunks.peek().unwrap().chars().next().unwrap(), 'd');
1783
1784 assert!(chunks.next_line());
1785 assert_eq!(chunks.peek().unwrap().chars().next().unwrap(), 'g');
1786
1787 assert!(chunks.next_line());
1788 assert_eq!(chunks.peek().unwrap().chars().next().unwrap(), 'j');
1789
1790 assert!(!chunks.next_line());
1791 assert_eq!(chunks.peek(), None);
1792
1793 assert!(chunks.prev_line());
1794 assert_eq!(chunks.peek().unwrap().chars().next().unwrap(), 'j');
1795
1796 assert!(chunks.prev_line());
1797 assert_eq!(chunks.peek().unwrap().chars().next().unwrap(), 'g');
1798
1799 assert!(chunks.prev_line());
1800 assert_eq!(chunks.peek().unwrap().chars().next().unwrap(), 'd');
1801
1802 assert!(chunks.prev_line());
1803 assert_eq!(chunks.peek().unwrap().chars().next().unwrap(), 'a');
1804
1805 assert!(!chunks.prev_line());
1806 assert_eq!(chunks.peek().unwrap().chars().next().unwrap(), 'a');
1807
1808 // Only return true when the cursor has moved to the start of a line
1809 let mut chunks = rope.chunks_in_range(5..7);
1810 chunks.seek(6);
1811 assert!(!chunks.prev_line());
1812 assert_eq!(chunks.peek().unwrap().chars().next().unwrap(), 'e');
1813
1814 assert!(!chunks.next_line());
1815 assert_eq!(chunks.peek(), None);
1816 }
1817
1818 #[test]
1819 fn test_lines() {
1820 let rope = Rope::from("abc\ndefg\nhi");
1821 let mut lines = rope.chunks().lines();
1822 assert_eq!(lines.next(), Some("abc"));
1823 assert_eq!(lines.next(), Some("defg"));
1824 assert_eq!(lines.next(), Some("hi"));
1825 assert_eq!(lines.next(), None);
1826
1827 let rope = Rope::from("abc\ndefg\nhi\n");
1828 let mut lines = rope.chunks().lines();
1829 assert_eq!(lines.next(), Some("abc"));
1830 assert_eq!(lines.next(), Some("defg"));
1831 assert_eq!(lines.next(), Some("hi"));
1832 assert_eq!(lines.next(), Some(""));
1833 assert_eq!(lines.next(), None);
1834
1835 let rope = Rope::from("abc\ndefg\nhi");
1836 let mut lines = rope.reversed_chunks_in_range(0..rope.len()).lines();
1837 assert_eq!(lines.next(), Some("hi"));
1838 assert_eq!(lines.next(), Some("defg"));
1839 assert_eq!(lines.next(), Some("abc"));
1840 assert_eq!(lines.next(), None);
1841
1842 let rope = Rope::from("abc\ndefg\nhi\n");
1843 let mut lines = rope.reversed_chunks_in_range(0..rope.len()).lines();
1844 assert_eq!(lines.next(), Some(""));
1845 assert_eq!(lines.next(), Some("hi"));
1846 assert_eq!(lines.next(), Some("defg"));
1847 assert_eq!(lines.next(), Some("abc"));
1848 assert_eq!(lines.next(), None);
1849
1850 let rope = Rope::from("abc\nlonger line test\nhi");
1851 let mut lines = rope.chunks().lines();
1852 assert_eq!(lines.next(), Some("abc"));
1853 assert_eq!(lines.next(), Some("longer line test"));
1854 assert_eq!(lines.next(), Some("hi"));
1855 assert_eq!(lines.next(), None);
1856
1857 let rope = Rope::from("abc\nlonger line test\nhi");
1858 let mut lines = rope.reversed_chunks_in_range(0..rope.len()).lines();
1859 assert_eq!(lines.next(), Some("hi"));
1860 assert_eq!(lines.next(), Some("longer line test"));
1861 assert_eq!(lines.next(), Some("abc"));
1862 assert_eq!(lines.next(), None);
1863 }
1864
1865 #[gpui::test(iterations = 100)]
1866 fn test_random_rope(mut rng: StdRng) {
1867 let operations = env::var("OPERATIONS")
1868 .map(|i| i.parse().expect("invalid `OPERATIONS` variable"))
1869 .unwrap_or(10);
1870
1871 let mut expected = String::new();
1872 let mut actual = Rope::new();
1873 for _ in 0..operations {
1874 let end_ix = clip_offset(&expected, rng.random_range(0..=expected.len()), Right);
1875 let start_ix = clip_offset(&expected, rng.random_range(0..=end_ix), Left);
1876 let len = rng.random_range(0..=64);
1877 let new_text: String = RandomCharIter::new(&mut rng).take(len).collect();
1878
1879 let mut new_actual = Rope::new();
1880 let mut cursor = actual.cursor(0);
1881 new_actual.append(cursor.slice(start_ix));
1882 new_actual.push(&new_text);
1883 cursor.seek_forward(end_ix);
1884 new_actual.append(cursor.suffix());
1885 actual = new_actual;
1886
1887 expected.replace_range(start_ix..end_ix, &new_text);
1888
1889 assert_eq!(actual.text(), expected);
1890 log::info!("text: {:?}", expected);
1891
1892 for _ in 0..5 {
1893 let end_ix = clip_offset(&expected, rng.random_range(0..=expected.len()), Right);
1894 let start_ix = clip_offset(&expected, rng.random_range(0..=end_ix), Left);
1895
1896 let actual_text = actual.chunks_in_range(start_ix..end_ix).collect::<String>();
1897 assert_eq!(actual_text, &expected[start_ix..end_ix]);
1898
1899 let mut actual_text = String::new();
1900 actual
1901 .bytes_in_range(start_ix..end_ix)
1902 .read_to_string(&mut actual_text)
1903 .unwrap();
1904 assert_eq!(actual_text, &expected[start_ix..end_ix]);
1905
1906 assert_eq!(
1907 actual
1908 .reversed_chunks_in_range(start_ix..end_ix)
1909 .collect::<Vec<&str>>()
1910 .into_iter()
1911 .rev()
1912 .collect::<String>(),
1913 &expected[start_ix..end_ix]
1914 );
1915
1916 let mut expected_line_starts: Vec<_> = expected[start_ix..end_ix]
1917 .match_indices('\n')
1918 .map(|(index, _)| start_ix + index + 1)
1919 .collect();
1920
1921 let mut chunks = actual.chunks_in_range(start_ix..end_ix);
1922
1923 let mut actual_line_starts = Vec::new();
1924 while chunks.next_line() {
1925 actual_line_starts.push(chunks.offset());
1926 }
1927 assert_eq!(
1928 actual_line_starts,
1929 expected_line_starts,
1930 "actual line starts != expected line starts when using next_line() for {:?} ({:?})",
1931 &expected[start_ix..end_ix],
1932 start_ix..end_ix
1933 );
1934
1935 if start_ix < end_ix
1936 && (start_ix == 0 || expected.as_bytes()[start_ix - 1] == b'\n')
1937 {
1938 expected_line_starts.insert(0, start_ix);
1939 }
1940 // Remove the last index if it starts at the end of the range.
1941 if expected_line_starts.last() == Some(&end_ix) {
1942 expected_line_starts.pop();
1943 }
1944
1945 let mut actual_line_starts = Vec::new();
1946 while chunks.prev_line() {
1947 actual_line_starts.push(chunks.offset());
1948 }
1949 actual_line_starts.reverse();
1950 assert_eq!(
1951 actual_line_starts,
1952 expected_line_starts,
1953 "actual line starts != expected line starts when using prev_line() for {:?} ({:?})",
1954 &expected[start_ix..end_ix],
1955 start_ix..end_ix
1956 );
1957
1958 // Check that next_line/prev_line work correctly from random positions
1959 let mut offset = rng.random_range(start_ix..=end_ix);
1960 while !expected.is_char_boundary(offset) {
1961 offset -= 1;
1962 }
1963 chunks.seek(offset);
1964
1965 for _ in 0..5 {
1966 if rng.random() {
1967 let expected_next_line_start = expected[offset..end_ix]
1968 .find('\n')
1969 .map(|newline_ix| offset + newline_ix + 1);
1970
1971 let moved = chunks.next_line();
1972 assert_eq!(
1973 moved,
1974 expected_next_line_start.is_some(),
1975 "unexpected result from next_line after seeking to {} in range {:?} ({:?})",
1976 offset,
1977 start_ix..end_ix,
1978 &expected[start_ix..end_ix]
1979 );
1980 if let Some(expected_next_line_start) = expected_next_line_start {
1981 assert_eq!(
1982 chunks.offset(),
1983 expected_next_line_start,
1984 "invalid position after seeking to {} in range {:?} ({:?})",
1985 offset,
1986 start_ix..end_ix,
1987 &expected[start_ix..end_ix]
1988 );
1989 } else {
1990 assert_eq!(
1991 chunks.offset(),
1992 end_ix,
1993 "invalid position after seeking to {} in range {:?} ({:?})",
1994 offset,
1995 start_ix..end_ix,
1996 &expected[start_ix..end_ix]
1997 );
1998 }
1999 } else {
2000 let search_end = if offset > 0 && expected.as_bytes()[offset - 1] == b'\n' {
2001 offset - 1
2002 } else {
2003 offset
2004 };
2005
2006 let expected_prev_line_start = expected[..search_end]
2007 .rfind('\n')
2008 .and_then(|newline_ix| {
2009 let line_start_ix = newline_ix + 1;
2010 if line_start_ix >= start_ix {
2011 Some(line_start_ix)
2012 } else {
2013 None
2014 }
2015 })
2016 .or({
2017 if offset > 0 && start_ix == 0 {
2018 Some(0)
2019 } else {
2020 None
2021 }
2022 });
2023
2024 let moved = chunks.prev_line();
2025 assert_eq!(
2026 moved,
2027 expected_prev_line_start.is_some(),
2028 "unexpected result from prev_line after seeking to {} in range {:?} ({:?})",
2029 offset,
2030 start_ix..end_ix,
2031 &expected[start_ix..end_ix]
2032 );
2033 if let Some(expected_prev_line_start) = expected_prev_line_start {
2034 assert_eq!(
2035 chunks.offset(),
2036 expected_prev_line_start,
2037 "invalid position after seeking to {} in range {:?} ({:?})",
2038 offset,
2039 start_ix..end_ix,
2040 &expected[start_ix..end_ix]
2041 );
2042 } else {
2043 assert_eq!(
2044 chunks.offset(),
2045 start_ix,
2046 "invalid position after seeking to {} in range {:?} ({:?})",
2047 offset,
2048 start_ix..end_ix,
2049 &expected[start_ix..end_ix]
2050 );
2051 }
2052 }
2053
2054 assert!((start_ix..=end_ix).contains(&chunks.offset()));
2055 if rng.random() {
2056 offset = rng.random_range(start_ix..=end_ix);
2057 while !expected.is_char_boundary(offset) {
2058 offset -= 1;
2059 }
2060 chunks.seek(offset);
2061 } else {
2062 chunks.next();
2063 offset = chunks.offset();
2064 assert!((start_ix..=end_ix).contains(&chunks.offset()));
2065 }
2066 }
2067 }
2068
2069 let mut offset_utf16 = OffsetUtf16(0);
2070 let mut point = Point::new(0, 0);
2071 let mut point_utf16 = PointUtf16::new(0, 0);
2072 for (ix, ch) in expected.char_indices().chain(Some((expected.len(), '\0'))) {
2073 assert_eq!(actual.offset_to_point(ix), point, "offset_to_point({})", ix);
2074 assert_eq!(
2075 actual.offset_to_point_utf16(ix),
2076 point_utf16,
2077 "offset_to_point_utf16({})",
2078 ix
2079 );
2080 assert_eq!(
2081 actual.point_to_offset(point),
2082 ix,
2083 "point_to_offset({:?})",
2084 point
2085 );
2086 assert_eq!(
2087 actual.point_utf16_to_offset(point_utf16),
2088 ix,
2089 "point_utf16_to_offset({:?})",
2090 point_utf16
2091 );
2092 assert_eq!(
2093 actual.offset_to_offset_utf16(ix),
2094 offset_utf16,
2095 "offset_to_offset_utf16({:?})",
2096 ix
2097 );
2098 assert_eq!(
2099 actual.offset_utf16_to_offset(offset_utf16),
2100 ix,
2101 "offset_utf16_to_offset({:?})",
2102 offset_utf16
2103 );
2104 if ch == '\n' {
2105 point += Point::new(1, 0);
2106 point_utf16 += PointUtf16::new(1, 0);
2107 } else {
2108 point.column += ch.len_utf8() as u32;
2109 point_utf16.column += ch.len_utf16() as u32;
2110 }
2111 offset_utf16.0 += ch.len_utf16();
2112 }
2113
2114 let mut offset_utf16 = OffsetUtf16(0);
2115 let mut point_utf16 = Unclipped(PointUtf16::zero());
2116 for unit in expected.encode_utf16() {
2117 let left_offset = actual.clip_offset_utf16(offset_utf16, Bias::Left);
2118 let right_offset = actual.clip_offset_utf16(offset_utf16, Bias::Right);
2119 assert!(right_offset >= left_offset);
2120 // Ensure translating UTF-16 offsets to UTF-8 offsets doesn't panic.
2121 actual.offset_utf16_to_offset(left_offset);
2122 actual.offset_utf16_to_offset(right_offset);
2123
2124 let left_point = actual.clip_point_utf16(point_utf16, Bias::Left);
2125 let right_point = actual.clip_point_utf16(point_utf16, Bias::Right);
2126 assert!(right_point >= left_point);
2127 // Ensure translating valid UTF-16 points to offsets doesn't panic.
2128 actual.point_utf16_to_offset(left_point);
2129 actual.point_utf16_to_offset(right_point);
2130
2131 offset_utf16.0 += 1;
2132 if unit == b'\n' as u16 {
2133 point_utf16.0 += PointUtf16::new(1, 0);
2134 } else {
2135 point_utf16.0 += PointUtf16::new(0, 1);
2136 }
2137 }
2138
2139 for _ in 0..5 {
2140 let end_ix = clip_offset(&expected, rng.random_range(0..=expected.len()), Right);
2141 let start_ix = clip_offset(&expected, rng.random_range(0..=end_ix), Left);
2142 assert_eq!(
2143 actual.cursor(start_ix).summary::<TextSummary>(end_ix),
2144 TextSummary::from(&expected[start_ix..end_ix])
2145 );
2146 }
2147
2148 let mut expected_longest_rows = Vec::new();
2149 let mut longest_line_len = -1_isize;
2150 for (row, line) in expected.split('\n').enumerate() {
2151 let row = row as u32;
2152 assert_eq!(
2153 actual.line_len(row),
2154 line.len() as u32,
2155 "invalid line len for row {}",
2156 row
2157 );
2158
2159 let line_char_count = line.chars().count() as isize;
2160 match line_char_count.cmp(&longest_line_len) {
2161 Ordering::Less => {}
2162 Ordering::Equal => expected_longest_rows.push(row),
2163 Ordering::Greater => {
2164 longest_line_len = line_char_count;
2165 expected_longest_rows.clear();
2166 expected_longest_rows.push(row);
2167 }
2168 }
2169 }
2170
2171 let longest_row = actual.summary().longest_row;
2172 assert!(
2173 expected_longest_rows.contains(&longest_row),
2174 "incorrect longest row {}. expected {:?} with length {}",
2175 longest_row,
2176 expected_longest_rows,
2177 longest_line_len,
2178 );
2179 }
2180 }
2181
2182 #[test]
2183 fn test_chunks_equals_str() {
2184 let text = "This is a multi-chunk\n& multi-line test string!";
2185 let rope = Rope::from(text);
2186 for start in 0..text.len() {
2187 for end in start..text.len() {
2188 let range = start..end;
2189 let correct_substring = &text[start..end];
2190
2191 // Test that correct range returns true
2192 assert!(
2193 rope.chunks_in_range(range.clone())
2194 .equals_str(correct_substring)
2195 );
2196 assert!(
2197 rope.reversed_chunks_in_range(range.clone())
2198 .equals_str(correct_substring)
2199 );
2200
2201 // Test that all other ranges return false (unless they happen to match)
2202 for other_start in 0..text.len() {
2203 for other_end in other_start..text.len() {
2204 if other_start == start && other_end == end {
2205 continue;
2206 }
2207 let other_substring = &text[other_start..other_end];
2208
2209 // Only assert false if the substrings are actually different
2210 if other_substring == correct_substring {
2211 continue;
2212 }
2213 assert!(
2214 !rope
2215 .chunks_in_range(range.clone())
2216 .equals_str(other_substring)
2217 );
2218 assert!(
2219 !rope
2220 .reversed_chunks_in_range(range.clone())
2221 .equals_str(other_substring)
2222 );
2223 }
2224 }
2225 }
2226 }
2227
2228 let rope = Rope::from("");
2229 assert!(rope.chunks_in_range(0..0).equals_str(""));
2230 assert!(rope.reversed_chunks_in_range(0..0).equals_str(""));
2231 assert!(!rope.chunks_in_range(0..0).equals_str("foo"));
2232 assert!(!rope.reversed_chunks_in_range(0..0).equals_str("foo"));
2233 }
2234
2235 #[test]
2236 fn test_starts_with() {
2237 let text = "Hello, world! 🌍🌎🌏";
2238 let rope = Rope::from(text);
2239
2240 assert!(rope.starts_with(""));
2241 assert!(rope.starts_with("H"));
2242 assert!(rope.starts_with("Hello"));
2243 assert!(rope.starts_with("Hello, world! 🌍🌎🌏"));
2244 assert!(!rope.starts_with("ello"));
2245 assert!(!rope.starts_with("Hello, world! 🌍🌎🌏!"));
2246
2247 let empty_rope = Rope::from("");
2248 assert!(empty_rope.starts_with(""));
2249 assert!(!empty_rope.starts_with("a"));
2250 }
2251
2252 #[test]
2253 fn test_ends_with() {
2254 let text = "Hello, world! 🌍🌎🌏";
2255 let rope = Rope::from(text);
2256
2257 assert!(rope.ends_with(""));
2258 assert!(rope.ends_with("🌏"));
2259 assert!(rope.ends_with("🌍🌎🌏"));
2260 assert!(rope.ends_with("Hello, world! 🌍🌎🌏"));
2261 assert!(!rope.ends_with("🌎"));
2262 assert!(!rope.ends_with("!Hello, world! 🌍🌎🌏"));
2263
2264 let empty_rope = Rope::from("");
2265 assert!(empty_rope.ends_with(""));
2266 assert!(!empty_rope.ends_with("a"));
2267 }
2268
2269 #[test]
2270 fn test_starts_with_ends_with_random() {
2271 let mut rng = StdRng::seed_from_u64(0);
2272 for _ in 0..100 {
2273 let len = rng.random_range(0..100);
2274 let text: String = RandomCharIter::new(&mut rng).take(len).collect();
2275 let rope = Rope::from(text.as_str());
2276
2277 for _ in 0..10 {
2278 let start = rng.random_range(0..=text.len());
2279 let start = text.ceil_char_boundary(start);
2280 let end = rng.random_range(start..=text.len());
2281 let end = text.ceil_char_boundary(end);
2282 let prefix = &text[..end];
2283 let suffix = &text[start..];
2284
2285 assert_eq!(
2286 rope.starts_with(prefix),
2287 text.starts_with(prefix),
2288 "starts_with mismatch for {:?} in {:?}",
2289 prefix,
2290 text
2291 );
2292 assert_eq!(
2293 rope.ends_with(suffix),
2294 text.ends_with(suffix),
2295 "ends_with mismatch for {:?} in {:?}",
2296 suffix,
2297 text
2298 );
2299 }
2300 }
2301 }
2302
2303 #[test]
2304 fn test_is_char_boundary() {
2305 let fixture = "地";
2306 let rope = Rope::from("地");
2307 for b in 0..=fixture.len() {
2308 assert_eq!(rope.is_char_boundary(b), fixture.is_char_boundary(b));
2309 }
2310 let fixture = "";
2311 let rope = Rope::from("");
2312 for b in 0..=fixture.len() {
2313 assert_eq!(rope.is_char_boundary(b), fixture.is_char_boundary(b));
2314 }
2315 let fixture = "🔴🟠🟡🟢🔵🟣⚫️⚪️🟤\n🏳️⚧️🏁🏳️🌈🏴☠️⛳️📬📭🏴🏳️🚩";
2316 let rope = Rope::from("🔴🟠🟡🟢🔵🟣⚫️⚪️🟤\n🏳️⚧️🏁🏳️🌈🏴☠️⛳️📬📭🏴🏳️🚩");
2317 for b in 0..=fixture.len() {
2318 assert_eq!(rope.is_char_boundary(b), fixture.is_char_boundary(b));
2319 }
2320 }
2321
2322 #[test]
2323 fn test_floor_char_boundary() {
2324 let fixture = "地";
2325 let rope = Rope::from("地");
2326 for b in 0..=fixture.len() {
2327 assert_eq!(rope.floor_char_boundary(b), fixture.floor_char_boundary(b));
2328 }
2329
2330 let fixture = "";
2331 let rope = Rope::from("");
2332 for b in 0..=fixture.len() {
2333 assert_eq!(rope.floor_char_boundary(b), fixture.floor_char_boundary(b));
2334 }
2335
2336 let fixture = "🔴🟠🟡🟢🔵🟣⚫️⚪️🟤\n🏳️⚧️🏁🏳️🌈🏴☠️⛳️📬📭🏴🏳️🚩";
2337 let rope = Rope::from("🔴🟠🟡🟢🔵🟣⚫️⚪️🟤\n🏳️⚧️🏁🏳️🌈🏴☠️⛳️📬📭🏴🏳️🚩");
2338 for b in 0..=fixture.len() {
2339 assert_eq!(rope.floor_char_boundary(b), fixture.floor_char_boundary(b));
2340 }
2341 }
2342
2343 #[test]
2344 fn test_ceil_char_boundary() {
2345 let fixture = "地";
2346 let rope = Rope::from("地");
2347 for b in 0..=fixture.len() {
2348 assert_eq!(rope.ceil_char_boundary(b), fixture.ceil_char_boundary(b));
2349 }
2350
2351 let fixture = "";
2352 let rope = Rope::from("");
2353 for b in 0..=fixture.len() {
2354 assert_eq!(rope.ceil_char_boundary(b), fixture.ceil_char_boundary(b));
2355 }
2356
2357 let fixture = "🔴🟠🟡🟢🔵🟣⚫️⚪️🟤\n🏳️⚧️🏁🏳️🌈🏴☠️⛳️📬📭🏴🏳️🚩";
2358 let rope = Rope::from("🔴🟠🟡🟢🔵🟣⚫️⚪️🟤\n🏳️⚧️🏁🏳️🌈🏴☠️⛳️📬📭🏴🏳️🚩");
2359 for b in 0..=fixture.len() {
2360 assert_eq!(rope.ceil_char_boundary(b), fixture.ceil_char_boundary(b));
2361 }
2362 }
2363
2364 #[test]
2365 fn test_push_front_empty_text_on_empty_rope() {
2366 let mut rope = Rope::new();
2367 rope.push_front("");
2368 assert_eq!(rope.text(), "");
2369 assert_eq!(rope.len(), 0);
2370 }
2371
2372 #[test]
2373 fn test_push_front_empty_text_on_nonempty_rope() {
2374 let mut rope = Rope::from("hello");
2375 rope.push_front("");
2376 assert_eq!(rope.text(), "hello");
2377 }
2378
2379 #[test]
2380 fn test_push_front_on_empty_rope() {
2381 let mut rope = Rope::new();
2382 rope.push_front("hello");
2383 assert_eq!(rope.text(), "hello");
2384 assert_eq!(rope.len(), 5);
2385 assert_eq!(rope.max_point(), Point::new(0, 5));
2386 }
2387
2388 #[test]
2389 fn test_push_front_single_space() {
2390 let mut rope = Rope::from("hint");
2391 rope.push_front(" ");
2392 assert_eq!(rope.text(), " hint");
2393 assert_eq!(rope.len(), 5);
2394 }
2395
2396 #[gpui::test(iterations = 50)]
2397 fn test_push_front_random(mut rng: StdRng) {
2398 let initial_len = rng.random_range(0..=64);
2399 let initial_text: String = RandomCharIter::new(&mut rng).take(initial_len).collect();
2400 let mut rope = Rope::from(initial_text.as_str());
2401
2402 let mut expected = initial_text;
2403
2404 for _ in 0..rng.random_range(1..=10) {
2405 let prefix_len = rng.random_range(0..=32);
2406 let prefix: String = RandomCharIter::new(&mut rng).take(prefix_len).collect();
2407
2408 rope.push_front(&prefix);
2409 expected.insert_str(0, &prefix);
2410
2411 assert_eq!(
2412 rope.text(),
2413 expected,
2414 "text mismatch after push_front({:?})",
2415 prefix
2416 );
2417 assert_eq!(rope.len(), expected.len());
2418
2419 let actual_summary = rope.summary();
2420 let expected_summary = TextSummary::from(expected.as_str());
2421 assert_eq!(
2422 actual_summary.len, expected_summary.len,
2423 "len mismatch for {:?}",
2424 expected
2425 );
2426 assert_eq!(
2427 actual_summary.lines, expected_summary.lines,
2428 "lines mismatch for {:?}",
2429 expected
2430 );
2431 assert_eq!(
2432 actual_summary.chars, expected_summary.chars,
2433 "chars mismatch for {:?}",
2434 expected
2435 );
2436 assert_eq!(
2437 actual_summary.longest_row, expected_summary.longest_row,
2438 "longest_row mismatch for {:?}",
2439 expected
2440 );
2441
2442 // Verify offset-to-point and point-to-offset round-trip at boundaries.
2443 for (ix, _) in expected.char_indices().chain(Some((expected.len(), '\0'))) {
2444 assert_eq!(
2445 rope.point_to_offset(rope.offset_to_point(ix)),
2446 ix,
2447 "offset round-trip failed at {} for {:?}",
2448 ix,
2449 expected
2450 );
2451 }
2452 }
2453 }
2454
2455 #[gpui::test(iterations = 50)]
2456 fn test_push_front_large_prefix(mut rng: StdRng) {
2457 let initial_len = rng.random_range(0..=32);
2458 let initial_text: String = RandomCharIter::new(&mut rng).take(initial_len).collect();
2459 let mut rope = Rope::from(initial_text.as_str());
2460
2461 let prefix_len = rng.random_range(64..=256);
2462 let prefix: String = RandomCharIter::new(&mut rng).take(prefix_len).collect();
2463
2464 rope.push_front(&prefix);
2465 let expected = format!("{}{}", prefix, initial_text);
2466
2467 assert_eq!(rope.text(), expected);
2468 assert_eq!(rope.len(), expected.len());
2469
2470 let actual_summary = rope.summary();
2471 let expected_summary = TextSummary::from(expected.as_str());
2472 assert_eq!(actual_summary.len, expected_summary.len);
2473 assert_eq!(actual_summary.lines, expected_summary.lines);
2474 assert_eq!(actual_summary.chars, expected_summary.chars);
2475 }
2476
2477 fn clip_offset(text: &str, mut offset: usize, bias: Bias) -> usize {
2478 while !text.is_char_boundary(offset) {
2479 match bias {
2480 Bias::Left => offset -= 1,
2481 Bias::Right => offset += 1,
2482 }
2483 }
2484 offset
2485 }
2486
2487 impl Rope {
2488 fn text(&self) -> String {
2489 let mut text = String::new();
2490 for chunk in self.chunks.cursor::<()>(()) {
2491 text.push_str(&chunk.text);
2492 }
2493 text
2494 }
2495 }
2496}