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