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