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