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