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