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