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