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