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, 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, 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, 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 Lines<'_> {
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::Summary for ChunkSummary {
1160 type Context = ();
1161
1162 fn zero(_cx: &()) -> Self {
1163 Default::default()
1164 }
1165
1166 fn add_summary(&mut self, summary: &Self, _: &()) {
1167 self.text += &summary.text;
1168 }
1169}
1170
1171/// Summary of a string of text.
1172#[derive(Copy, Clone, Debug, Default, Eq, PartialEq)]
1173pub struct TextSummary {
1174 /// Length in bytes.
1175 pub len: usize,
1176 /// Length in UTF-8.
1177 pub chars: usize,
1178 /// Length in UTF-16 code units
1179 pub len_utf16: OffsetUtf16,
1180 /// A point representing the number of lines and the length of the last line.
1181 ///
1182 /// In other words, it marks the point after the last byte in the text, (if
1183 /// EOF was a character, this would be its position).
1184 pub lines: Point,
1185 /// How many `char`s are in the first line
1186 pub first_line_chars: u32,
1187 /// How many `char`s are in the last line
1188 pub last_line_chars: u32,
1189 /// How many UTF-16 code units are in the last line
1190 pub last_line_len_utf16: u32,
1191 /// The row idx of the longest row
1192 pub longest_row: u32,
1193 /// How many `char`s are in the longest row
1194 pub longest_row_chars: u32,
1195}
1196
1197impl TextSummary {
1198 pub fn lines_utf16(&self) -> PointUtf16 {
1199 PointUtf16 {
1200 row: self.lines.row,
1201 column: self.last_line_len_utf16,
1202 }
1203 }
1204
1205 pub fn newline() -> Self {
1206 Self {
1207 len: 1,
1208 chars: 1,
1209 len_utf16: OffsetUtf16(1),
1210 first_line_chars: 0,
1211 last_line_chars: 0,
1212 last_line_len_utf16: 0,
1213 lines: Point::new(1, 0),
1214 longest_row: 0,
1215 longest_row_chars: 0,
1216 }
1217 }
1218
1219 pub fn add_newline(&mut self) {
1220 self.len += 1;
1221 self.len_utf16 += OffsetUtf16(self.len_utf16.0 + 1);
1222 self.last_line_chars = 0;
1223 self.last_line_len_utf16 = 0;
1224 self.lines += Point::new(1, 0);
1225 }
1226}
1227
1228impl<'a> From<&'a str> for TextSummary {
1229 fn from(text: &'a str) -> Self {
1230 let mut len_utf16 = OffsetUtf16(0);
1231 let mut lines = Point::new(0, 0);
1232 let mut first_line_chars = 0;
1233 let mut last_line_chars = 0;
1234 let mut last_line_len_utf16 = 0;
1235 let mut longest_row = 0;
1236 let mut longest_row_chars = 0;
1237 let mut chars = 0;
1238 for c in text.chars() {
1239 chars += 1;
1240 len_utf16.0 += c.len_utf16();
1241
1242 if c == '\n' {
1243 lines += Point::new(1, 0);
1244 last_line_len_utf16 = 0;
1245 last_line_chars = 0;
1246 } else {
1247 lines.column += c.len_utf8() as u32;
1248 last_line_len_utf16 += c.len_utf16() as u32;
1249 last_line_chars += 1;
1250 }
1251
1252 if lines.row == 0 {
1253 first_line_chars = last_line_chars;
1254 }
1255
1256 if last_line_chars > longest_row_chars {
1257 longest_row = lines.row;
1258 longest_row_chars = last_line_chars;
1259 }
1260 }
1261
1262 TextSummary {
1263 len: text.len(),
1264 chars,
1265 len_utf16,
1266 lines,
1267 first_line_chars,
1268 last_line_chars,
1269 last_line_len_utf16,
1270 longest_row,
1271 longest_row_chars,
1272 }
1273 }
1274}
1275
1276impl sum_tree::Summary for TextSummary {
1277 type Context = ();
1278
1279 fn zero(_cx: &()) -> Self {
1280 Default::default()
1281 }
1282
1283 fn add_summary(&mut self, summary: &Self, _: &Self::Context) {
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}