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