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