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