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(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.text.is_char_boundary(chunk_offset)
720 {
721 panic!("byte index {} is not a char boundary", offset);
722 }
723 Self {
724 chunks,
725 range,
726 offset,
727 reversed,
728 }
729 }
730
731 fn offset_is_valid(&self) -> bool {
732 if self.reversed {
733 if self.offset <= self.range.start || self.offset > self.range.end {
734 return false;
735 }
736 } else if self.offset < self.range.start || self.offset >= self.range.end {
737 return false;
738 }
739
740 true
741 }
742
743 pub fn offset(&self) -> usize {
744 self.offset
745 }
746
747 pub fn seek(&mut self, mut offset: usize) {
748 offset = offset.clamp(self.range.start, self.range.end);
749
750 if self.reversed {
751 if offset > self.chunks.end() {
752 self.chunks.seek_forward(&offset, Bias::Left);
753 } else if offset <= *self.chunks.start() {
754 self.chunks.seek(&offset, Bias::Left);
755 }
756 } else {
757 if offset >= self.chunks.end() {
758 self.chunks.seek_forward(&offset, Bias::Right);
759 } else if offset < *self.chunks.start() {
760 self.chunks.seek(&offset, Bias::Right);
761 }
762 };
763
764 self.offset = offset;
765 }
766
767 pub fn set_range(&mut self, range: Range<usize>) {
768 self.range = range.clone();
769 self.seek(range.start);
770 }
771
772 /// Moves this cursor to the start of the next line in the rope.
773 ///
774 /// This method advances the cursor to the beginning of the next line.
775 /// If the cursor is already at the end of the rope, this method does nothing.
776 /// Reversed chunks iterators are not currently supported and will panic.
777 ///
778 /// Returns `true` if the cursor was successfully moved to the next line start,
779 /// or `false` if the cursor was already at the end of the rope.
780 pub fn next_line(&mut self) -> bool {
781 assert!(!self.reversed);
782
783 let mut found = false;
784 if let Some(chunk) = self.peek() {
785 if let Some(newline_ix) = chunk.find('\n') {
786 self.offset += newline_ix + 1;
787 found = self.offset <= self.range.end;
788 } else {
789 self.chunks
790 .search_forward(|summary| summary.text.lines.row > 0);
791 self.offset = *self.chunks.start();
792
793 if let Some(newline_ix) = self.peek().and_then(|chunk| chunk.find('\n')) {
794 self.offset += newline_ix + 1;
795 found = self.offset <= self.range.end;
796 } else {
797 self.offset = self.chunks.end();
798 }
799 }
800
801 if self.offset == self.chunks.end() {
802 self.next();
803 }
804 }
805
806 if self.offset > self.range.end {
807 self.offset = cmp::min(self.offset, self.range.end);
808 self.chunks.seek(&self.offset, Bias::Right);
809 }
810
811 found
812 }
813
814 /// Move this cursor to the preceding position in the rope that starts a new line.
815 /// Reversed chunks iterators are not currently supported and will panic.
816 ///
817 /// If this cursor is not on the start of a line, it will be moved to the start of
818 /// its current line. Otherwise it will be moved to the start of the previous line.
819 /// It updates the cursor's position and returns true if a previous line was found,
820 /// or false if the cursor was already at the start of the rope.
821 pub fn prev_line(&mut self) -> bool {
822 assert!(!self.reversed);
823
824 let initial_offset = self.offset;
825
826 if self.offset == *self.chunks.start() {
827 self.chunks.prev();
828 }
829
830 if let Some(chunk) = self.chunks.item() {
831 let mut end_ix = self.offset - *self.chunks.start();
832 if chunk.text.as_bytes()[end_ix - 1] == b'\n' {
833 end_ix -= 1;
834 }
835
836 if let Some(newline_ix) = chunk.text[..end_ix].rfind('\n') {
837 self.offset = *self.chunks.start() + newline_ix + 1;
838 if self.offset_is_valid() {
839 return true;
840 }
841 }
842 }
843
844 self.chunks
845 .search_backward(|summary| summary.text.lines.row > 0);
846 self.offset = *self.chunks.start();
847 if let Some(chunk) = self.chunks.item()
848 && let Some(newline_ix) = chunk.text.rfind('\n')
849 {
850 self.offset += newline_ix + 1;
851 if self.offset_is_valid() {
852 if self.offset == self.chunks.end() {
853 self.chunks.next();
854 }
855
856 return true;
857 }
858 }
859
860 if !self.offset_is_valid() || self.chunks.item().is_none() {
861 self.offset = self.range.start;
862 self.chunks.seek(&self.offset, Bias::Right);
863 }
864
865 self.offset < initial_offset && self.offset == 0
866 }
867
868 pub fn peek(&self) -> Option<&'a str> {
869 if !self.offset_is_valid() {
870 return None;
871 }
872
873 let chunk = self.chunks.item()?;
874 let chunk_start = *self.chunks.start();
875 let slice_range = if self.reversed {
876 let slice_start = cmp::max(chunk_start, self.range.start) - chunk_start;
877 let slice_end = self.offset - chunk_start;
878 slice_start..slice_end
879 } else {
880 let slice_start = self.offset - chunk_start;
881 let slice_end = cmp::min(self.chunks.end(), self.range.end) - chunk_start;
882 slice_start..slice_end
883 };
884
885 Some(&chunk.text[slice_range])
886 }
887
888 /// Returns bitmaps that represent character positions and tab positions
889 pub fn peek_with_bitmaps(&self) -> Option<ChunkBitmaps<'a>> {
890 if !self.offset_is_valid() {
891 return None;
892 }
893
894 let chunk = self.chunks.item()?;
895 let chunk_start = *self.chunks.start();
896 let slice_range = if self.reversed {
897 let slice_start = cmp::max(chunk_start, self.range.start) - chunk_start;
898 let slice_end = self.offset - chunk_start;
899 slice_start..slice_end
900 } else {
901 let slice_start = self.offset - chunk_start;
902 let slice_end = cmp::min(self.chunks.end(), self.range.end) - chunk_start;
903 slice_start..slice_end
904 };
905 let chunk_start_offset = slice_range.start;
906 let slice_text = &chunk.text[slice_range];
907
908 // Shift the tabs to align with our slice window
909 let shifted_tabs = chunk.tabs() >> chunk_start_offset;
910 let shifted_chars = chunk.chars() >> chunk_start_offset;
911
912 Some(ChunkBitmaps {
913 text: slice_text,
914 chars: shifted_chars,
915 tabs: shifted_tabs,
916 })
917 }
918
919 pub fn lines(self) -> Lines<'a> {
920 let reversed = self.reversed;
921 Lines {
922 chunks: self,
923 current_line: String::new(),
924 done: false,
925 reversed,
926 }
927 }
928
929 pub fn equals_str(&self, other: &str) -> bool {
930 let chunk = self.clone();
931 if chunk.reversed {
932 let mut offset = other.len();
933 for chunk in chunk {
934 if other[0..offset].ends_with(chunk) {
935 offset -= chunk.len();
936 } else {
937 return false;
938 }
939 }
940 if offset != 0 {
941 return false;
942 }
943 } else {
944 let mut offset = 0;
945 for chunk in chunk {
946 if offset >= other.len() {
947 return false;
948 }
949 if other[offset..].starts_with(chunk) {
950 offset += chunk.len();
951 } else {
952 return false;
953 }
954 }
955 if offset != other.len() {
956 return false;
957 }
958 }
959
960 true
961 }
962}
963
964pub struct ChunkWithBitmaps<'a>(pub Chunks<'a>);
965
966impl<'a> Iterator for ChunkWithBitmaps<'a> {
967 /// text, chars bitmap, tabs bitmap
968 type Item = ChunkBitmaps<'a>;
969
970 fn next(&mut self) -> Option<Self::Item> {
971 let chunk_bitmaps = self.0.peek_with_bitmaps()?;
972 if self.0.reversed {
973 self.0.offset -= chunk_bitmaps.text.len();
974 if self.0.offset <= *self.0.chunks.start() {
975 self.0.chunks.prev();
976 }
977 } else {
978 self.0.offset += chunk_bitmaps.text.len();
979 if self.0.offset >= self.0.chunks.end() {
980 self.0.chunks.next();
981 }
982 }
983
984 Some(chunk_bitmaps)
985 }
986}
987
988impl<'a> Iterator for Chunks<'a> {
989 type Item = &'a str;
990
991 fn next(&mut self) -> Option<Self::Item> {
992 let chunk = self.peek()?;
993 if self.reversed {
994 self.offset -= chunk.len();
995 if self.offset <= *self.chunks.start() {
996 self.chunks.prev();
997 }
998 } else {
999 self.offset += chunk.len();
1000 if self.offset >= self.chunks.end() {
1001 self.chunks.next();
1002 }
1003 }
1004
1005 Some(chunk)
1006 }
1007}
1008
1009pub struct Bytes<'a> {
1010 chunks: sum_tree::Cursor<'a, 'static, Chunk, usize>,
1011 range: Range<usize>,
1012 reversed: bool,
1013}
1014
1015impl<'a> Bytes<'a> {
1016 pub fn new(rope: &'a Rope, range: Range<usize>, reversed: bool) -> Self {
1017 let mut chunks = rope.chunks.cursor(());
1018 if reversed {
1019 chunks.seek(&range.end, Bias::Left);
1020 } else {
1021 chunks.seek(&range.start, Bias::Right);
1022 }
1023 Self {
1024 chunks,
1025 range,
1026 reversed,
1027 }
1028 }
1029
1030 pub fn peek(&self) -> Option<&'a [u8]> {
1031 let chunk = self.chunks.item()?;
1032 if self.reversed && self.range.start >= self.chunks.end() {
1033 return None;
1034 }
1035 let chunk_start = *self.chunks.start();
1036 if self.range.end <= chunk_start {
1037 return None;
1038 }
1039 let start = self.range.start.saturating_sub(chunk_start);
1040 let end = self.range.end - chunk_start;
1041 Some(&chunk.text.as_bytes()[start..chunk.text.len().min(end)])
1042 }
1043}
1044
1045impl<'a> Iterator for Bytes<'a> {
1046 type Item = &'a [u8];
1047
1048 fn next(&mut self) -> Option<Self::Item> {
1049 let result = self.peek();
1050 if result.is_some() {
1051 if self.reversed {
1052 self.chunks.prev();
1053 } else {
1054 self.chunks.next();
1055 }
1056 }
1057 result
1058 }
1059}
1060
1061impl io::Read for Bytes<'_> {
1062 fn read(&mut self, buf: &mut [u8]) -> io::Result<usize> {
1063 if let Some(chunk) = self.peek() {
1064 let len = cmp::min(buf.len(), chunk.len());
1065 if self.reversed {
1066 buf[..len].copy_from_slice(&chunk[chunk.len() - len..]);
1067 buf[..len].reverse();
1068 self.range.end -= len;
1069 } else {
1070 buf[..len].copy_from_slice(&chunk[..len]);
1071 self.range.start += len;
1072 }
1073
1074 if len == chunk.len() {
1075 if self.reversed {
1076 self.chunks.prev();
1077 } else {
1078 self.chunks.next();
1079 }
1080 }
1081 Ok(len)
1082 } else {
1083 Ok(0)
1084 }
1085 }
1086}
1087
1088pub struct Lines<'a> {
1089 chunks: Chunks<'a>,
1090 current_line: String,
1091 done: bool,
1092 reversed: bool,
1093}
1094
1095impl<'a> Lines<'a> {
1096 pub fn next(&mut self) -> Option<&str> {
1097 if self.done {
1098 return None;
1099 }
1100
1101 self.current_line.clear();
1102
1103 while let Some(chunk) = self.chunks.peek() {
1104 let chunk_lines = chunk.split('\n');
1105 if self.reversed {
1106 let mut chunk_lines = chunk_lines.rev().peekable();
1107 if let Some(chunk_line) = chunk_lines.next() {
1108 let done = chunk_lines.peek().is_some();
1109 if done {
1110 self.chunks
1111 .seek(self.chunks.offset() - chunk_line.len() - "\n".len());
1112 if self.current_line.is_empty() {
1113 return Some(chunk_line);
1114 }
1115 }
1116 self.current_line.insert_str(0, chunk_line);
1117 if done {
1118 return Some(&self.current_line);
1119 }
1120 }
1121 } else {
1122 let mut chunk_lines = chunk_lines.peekable();
1123 if let Some(chunk_line) = chunk_lines.next() {
1124 let done = chunk_lines.peek().is_some();
1125 if done {
1126 self.chunks
1127 .seek(self.chunks.offset() + chunk_line.len() + "\n".len());
1128 if self.current_line.is_empty() {
1129 return Some(chunk_line);
1130 }
1131 }
1132 self.current_line.push_str(chunk_line);
1133 if done {
1134 return Some(&self.current_line);
1135 }
1136 }
1137 }
1138
1139 self.chunks.next();
1140 }
1141
1142 self.done = true;
1143 Some(&self.current_line)
1144 }
1145
1146 pub fn seek(&mut self, offset: usize) {
1147 self.chunks.seek(offset);
1148 self.current_line.clear();
1149 self.done = false;
1150 }
1151
1152 pub fn offset(&self) -> usize {
1153 self.chunks.offset()
1154 }
1155}
1156
1157impl sum_tree::Item for Chunk {
1158 type Summary = ChunkSummary;
1159
1160 fn summary(&self, _cx: ()) -> Self::Summary {
1161 ChunkSummary {
1162 text: self.as_slice().text_summary(),
1163 }
1164 }
1165}
1166
1167#[derive(Clone, Debug, Default, Eq, PartialEq)]
1168pub struct ChunkSummary {
1169 text: TextSummary,
1170}
1171
1172impl sum_tree::ContextLessSummary for ChunkSummary {
1173 fn zero() -> Self {
1174 Default::default()
1175 }
1176
1177 fn add_summary(&mut self, summary: &Self) {
1178 self.text += &summary.text;
1179 }
1180}
1181
1182/// Summary of a string of text.
1183#[derive(Copy, Clone, Debug, Default, Eq, PartialEq)]
1184pub struct TextSummary {
1185 /// Length in bytes.
1186 pub len: usize,
1187 /// Length in UTF-8.
1188 pub chars: usize,
1189 /// Length in UTF-16 code units
1190 pub len_utf16: OffsetUtf16,
1191 /// A point representing the number of lines and the length of the last line.
1192 ///
1193 /// In other words, it marks the point after the last byte in the text, (if
1194 /// EOF was a character, this would be its position).
1195 pub lines: Point,
1196 /// How many `char`s are in the first line
1197 pub first_line_chars: u32,
1198 /// How many `char`s are in the last line
1199 pub last_line_chars: u32,
1200 /// How many UTF-16 code units are in the last line
1201 pub last_line_len_utf16: u32,
1202 /// The row idx of the longest row
1203 pub longest_row: u32,
1204 /// How many `char`s are in the longest row
1205 pub longest_row_chars: u32,
1206}
1207
1208impl TextSummary {
1209 pub fn lines_utf16(&self) -> PointUtf16 {
1210 PointUtf16 {
1211 row: self.lines.row,
1212 column: self.last_line_len_utf16,
1213 }
1214 }
1215
1216 pub fn newline() -> Self {
1217 Self {
1218 len: 1,
1219 chars: 1,
1220 len_utf16: OffsetUtf16(1),
1221 first_line_chars: 0,
1222 last_line_chars: 0,
1223 last_line_len_utf16: 0,
1224 lines: Point::new(1, 0),
1225 longest_row: 0,
1226 longest_row_chars: 0,
1227 }
1228 }
1229
1230 pub fn add_newline(&mut self) {
1231 self.len += 1;
1232 self.len_utf16 += OffsetUtf16(self.len_utf16.0 + 1);
1233 self.last_line_chars = 0;
1234 self.last_line_len_utf16 = 0;
1235 self.lines += Point::new(1, 0);
1236 }
1237}
1238
1239impl<'a> From<&'a str> for TextSummary {
1240 fn from(text: &'a str) -> Self {
1241 let mut len_utf16 = OffsetUtf16(0);
1242 let mut lines = Point::new(0, 0);
1243 let mut first_line_chars = 0;
1244 let mut last_line_chars = 0;
1245 let mut last_line_len_utf16 = 0;
1246 let mut longest_row = 0;
1247 let mut longest_row_chars = 0;
1248 let mut chars = 0;
1249 for c in text.chars() {
1250 chars += 1;
1251 len_utf16.0 += c.len_utf16();
1252
1253 if c == '\n' {
1254 lines += Point::new(1, 0);
1255 last_line_len_utf16 = 0;
1256 last_line_chars = 0;
1257 } else {
1258 lines.column += c.len_utf8() as u32;
1259 last_line_len_utf16 += c.len_utf16() as u32;
1260 last_line_chars += 1;
1261 }
1262
1263 if lines.row == 0 {
1264 first_line_chars = last_line_chars;
1265 }
1266
1267 if last_line_chars > longest_row_chars {
1268 longest_row = lines.row;
1269 longest_row_chars = last_line_chars;
1270 }
1271 }
1272
1273 TextSummary {
1274 len: text.len(),
1275 chars,
1276 len_utf16,
1277 lines,
1278 first_line_chars,
1279 last_line_chars,
1280 last_line_len_utf16,
1281 longest_row,
1282 longest_row_chars,
1283 }
1284 }
1285}
1286
1287impl sum_tree::ContextLessSummary for TextSummary {
1288 fn zero() -> Self {
1289 Default::default()
1290 }
1291
1292 fn add_summary(&mut self, summary: &Self) {
1293 *self += summary;
1294 }
1295}
1296
1297impl ops::Add<Self> for TextSummary {
1298 type Output = Self;
1299
1300 fn add(mut self, rhs: Self) -> Self::Output {
1301 AddAssign::add_assign(&mut self, &rhs);
1302 self
1303 }
1304}
1305
1306impl<'a> ops::AddAssign<&'a Self> for TextSummary {
1307 fn add_assign(&mut self, other: &'a Self) {
1308 let joined_chars = self.last_line_chars + other.first_line_chars;
1309 if joined_chars > self.longest_row_chars {
1310 self.longest_row = self.lines.row;
1311 self.longest_row_chars = joined_chars;
1312 }
1313 if other.longest_row_chars > self.longest_row_chars {
1314 self.longest_row = self.lines.row + other.longest_row;
1315 self.longest_row_chars = other.longest_row_chars;
1316 }
1317
1318 if self.lines.row == 0 {
1319 self.first_line_chars += other.first_line_chars;
1320 }
1321
1322 if other.lines.row == 0 {
1323 self.last_line_chars += other.first_line_chars;
1324 self.last_line_len_utf16 += other.last_line_len_utf16;
1325 } else {
1326 self.last_line_chars = other.last_line_chars;
1327 self.last_line_len_utf16 = other.last_line_len_utf16;
1328 }
1329
1330 self.chars += other.chars;
1331 self.len += other.len;
1332 self.len_utf16 += other.len_utf16;
1333 self.lines += other.lines;
1334 }
1335}
1336
1337impl ops::AddAssign<Self> for TextSummary {
1338 fn add_assign(&mut self, other: Self) {
1339 *self += &other;
1340 }
1341}
1342
1343pub trait TextDimension:
1344 'static + Clone + Copy + Default + for<'a> Dimension<'a, ChunkSummary> + std::fmt::Debug
1345{
1346 fn from_text_summary(summary: &TextSummary) -> Self;
1347 fn from_chunk(chunk: ChunkSlice) -> Self;
1348 fn add_assign(&mut self, other: &Self);
1349}
1350
1351impl<D1: TextDimension, D2: TextDimension> TextDimension for Dimensions<D1, D2, ()> {
1352 fn from_text_summary(summary: &TextSummary) -> Self {
1353 Dimensions(
1354 D1::from_text_summary(summary),
1355 D2::from_text_summary(summary),
1356 (),
1357 )
1358 }
1359
1360 fn from_chunk(chunk: ChunkSlice) -> Self {
1361 Dimensions(D1::from_chunk(chunk), D2::from_chunk(chunk), ())
1362 }
1363
1364 fn add_assign(&mut self, other: &Self) {
1365 self.0.add_assign(&other.0);
1366 self.1.add_assign(&other.1);
1367 }
1368}
1369
1370impl<'a> sum_tree::Dimension<'a, ChunkSummary> for TextSummary {
1371 fn zero(_cx: ()) -> Self {
1372 Default::default()
1373 }
1374
1375 fn add_summary(&mut self, summary: &'a ChunkSummary, _: ()) {
1376 *self += &summary.text;
1377 }
1378}
1379
1380impl TextDimension for TextSummary {
1381 fn from_text_summary(summary: &TextSummary) -> Self {
1382 *summary
1383 }
1384
1385 fn from_chunk(chunk: ChunkSlice) -> Self {
1386 chunk.text_summary()
1387 }
1388
1389 fn add_assign(&mut self, other: &Self) {
1390 *self += other;
1391 }
1392}
1393
1394impl<'a> sum_tree::Dimension<'a, ChunkSummary> for usize {
1395 fn zero(_cx: ()) -> Self {
1396 Default::default()
1397 }
1398
1399 fn add_summary(&mut self, summary: &'a ChunkSummary, _: ()) {
1400 *self += summary.text.len;
1401 }
1402}
1403
1404impl TextDimension for usize {
1405 fn from_text_summary(summary: &TextSummary) -> Self {
1406 summary.len
1407 }
1408
1409 fn from_chunk(chunk: ChunkSlice) -> Self {
1410 chunk.len()
1411 }
1412
1413 fn add_assign(&mut self, other: &Self) {
1414 *self += other;
1415 }
1416}
1417
1418impl<'a> sum_tree::Dimension<'a, ChunkSummary> for OffsetUtf16 {
1419 fn zero(_cx: ()) -> Self {
1420 Default::default()
1421 }
1422
1423 fn add_summary(&mut self, summary: &'a ChunkSummary, _: ()) {
1424 *self += summary.text.len_utf16;
1425 }
1426}
1427
1428impl TextDimension for OffsetUtf16 {
1429 fn from_text_summary(summary: &TextSummary) -> Self {
1430 summary.len_utf16
1431 }
1432
1433 fn from_chunk(chunk: ChunkSlice) -> Self {
1434 chunk.len_utf16()
1435 }
1436
1437 fn add_assign(&mut self, other: &Self) {
1438 *self += other;
1439 }
1440}
1441
1442impl<'a> sum_tree::Dimension<'a, ChunkSummary> for Point {
1443 fn zero(_cx: ()) -> Self {
1444 Default::default()
1445 }
1446
1447 fn add_summary(&mut self, summary: &'a ChunkSummary, _: ()) {
1448 *self += summary.text.lines;
1449 }
1450}
1451
1452impl TextDimension for Point {
1453 fn from_text_summary(summary: &TextSummary) -> Self {
1454 summary.lines
1455 }
1456
1457 fn from_chunk(chunk: ChunkSlice) -> Self {
1458 chunk.lines()
1459 }
1460
1461 fn add_assign(&mut self, other: &Self) {
1462 *self += other;
1463 }
1464}
1465
1466impl<'a> sum_tree::Dimension<'a, ChunkSummary> for PointUtf16 {
1467 fn zero(_cx: ()) -> Self {
1468 Default::default()
1469 }
1470
1471 fn add_summary(&mut self, summary: &'a ChunkSummary, _: ()) {
1472 *self += summary.text.lines_utf16();
1473 }
1474}
1475
1476impl TextDimension for PointUtf16 {
1477 fn from_text_summary(summary: &TextSummary) -> Self {
1478 summary.lines_utf16()
1479 }
1480
1481 fn from_chunk(chunk: ChunkSlice) -> Self {
1482 PointUtf16 {
1483 row: chunk.lines().row,
1484 column: chunk.last_line_len_utf16(),
1485 }
1486 }
1487
1488 fn add_assign(&mut self, other: &Self) {
1489 *self += other;
1490 }
1491}
1492
1493/// A pair of text dimensions in which only the first dimension is used for comparison,
1494/// but both dimensions are updated during addition and subtraction.
1495#[derive(Clone, Copy, Debug)]
1496pub struct DimensionPair<K, V> {
1497 pub key: K,
1498 pub value: Option<V>,
1499}
1500
1501impl<K: Default, V: Default> Default for DimensionPair<K, V> {
1502 fn default() -> Self {
1503 Self {
1504 key: Default::default(),
1505 value: Some(Default::default()),
1506 }
1507 }
1508}
1509
1510impl<K, V> cmp::Ord for DimensionPair<K, V>
1511where
1512 K: cmp::Ord,
1513{
1514 fn cmp(&self, other: &Self) -> cmp::Ordering {
1515 self.key.cmp(&other.key)
1516 }
1517}
1518
1519impl<K, V> cmp::PartialOrd for DimensionPair<K, V>
1520where
1521 K: cmp::PartialOrd,
1522{
1523 fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
1524 self.key.partial_cmp(&other.key)
1525 }
1526}
1527
1528impl<K, V> cmp::PartialEq for DimensionPair<K, V>
1529where
1530 K: cmp::PartialEq,
1531{
1532 fn eq(&self, other: &Self) -> bool {
1533 self.key.eq(&other.key)
1534 }
1535}
1536
1537impl<K, V> ops::Sub for DimensionPair<K, V>
1538where
1539 K: ops::Sub<K, Output = K>,
1540 V: ops::Sub<V, Output = V>,
1541{
1542 type Output = Self;
1543
1544 fn sub(self, rhs: Self) -> Self::Output {
1545 Self {
1546 key: self.key - rhs.key,
1547 value: self.value.zip(rhs.value).map(|(a, b)| a - b),
1548 }
1549 }
1550}
1551
1552impl<K, V> cmp::Eq for DimensionPair<K, V> where K: cmp::Eq {}
1553
1554impl<'a, K, V> sum_tree::Dimension<'a, ChunkSummary> for DimensionPair<K, V>
1555where
1556 K: sum_tree::Dimension<'a, ChunkSummary>,
1557 V: sum_tree::Dimension<'a, ChunkSummary>,
1558{
1559 fn zero(_cx: ()) -> Self {
1560 Self {
1561 key: K::zero(_cx),
1562 value: Some(V::zero(_cx)),
1563 }
1564 }
1565
1566 fn add_summary(&mut self, summary: &'a ChunkSummary, _cx: ()) {
1567 self.key.add_summary(summary, _cx);
1568 if let Some(value) = &mut self.value {
1569 value.add_summary(summary, _cx);
1570 }
1571 }
1572}
1573
1574impl<K, V> TextDimension for DimensionPair<K, V>
1575where
1576 K: TextDimension,
1577 V: TextDimension,
1578{
1579 fn add_assign(&mut self, other: &Self) {
1580 self.key.add_assign(&other.key);
1581 if let Some(value) = &mut self.value {
1582 if let Some(other_value) = other.value.as_ref() {
1583 value.add_assign(other_value);
1584 } else {
1585 self.value.take();
1586 }
1587 }
1588 }
1589
1590 fn from_chunk(chunk: ChunkSlice) -> Self {
1591 Self {
1592 key: K::from_chunk(chunk),
1593 value: Some(V::from_chunk(chunk)),
1594 }
1595 }
1596
1597 fn from_text_summary(summary: &TextSummary) -> Self {
1598 Self {
1599 key: K::from_text_summary(summary),
1600 value: Some(V::from_text_summary(summary)),
1601 }
1602 }
1603}
1604
1605#[cfg(test)]
1606mod tests {
1607 use super::*;
1608 use Bias::{Left, Right};
1609 use rand::prelude::*;
1610 use std::{cmp::Ordering, env, io::Read};
1611 use util::RandomCharIter;
1612
1613 #[ctor::ctor]
1614 fn init_logger() {
1615 zlog::init_test();
1616 }
1617
1618 #[test]
1619 fn test_all_4_byte_chars() {
1620 let mut rope = Rope::new();
1621 let text = "🏀".repeat(256);
1622 rope.push(&text);
1623 assert_eq!(rope.text(), text);
1624 }
1625
1626 #[test]
1627 fn test_clip() {
1628 let rope = Rope::from("🧘");
1629
1630 assert_eq!(rope.clip_offset(1, Bias::Left), 0);
1631 assert_eq!(rope.clip_offset(1, Bias::Right), 4);
1632 assert_eq!(rope.clip_offset(5, Bias::Right), 4);
1633
1634 assert_eq!(
1635 rope.clip_point(Point::new(0, 1), Bias::Left),
1636 Point::new(0, 0)
1637 );
1638 assert_eq!(
1639 rope.clip_point(Point::new(0, 1), Bias::Right),
1640 Point::new(0, 4)
1641 );
1642 assert_eq!(
1643 rope.clip_point(Point::new(0, 5), Bias::Right),
1644 Point::new(0, 4)
1645 );
1646
1647 assert_eq!(
1648 rope.clip_point_utf16(Unclipped(PointUtf16::new(0, 1)), Bias::Left),
1649 PointUtf16::new(0, 0)
1650 );
1651 assert_eq!(
1652 rope.clip_point_utf16(Unclipped(PointUtf16::new(0, 1)), Bias::Right),
1653 PointUtf16::new(0, 2)
1654 );
1655 assert_eq!(
1656 rope.clip_point_utf16(Unclipped(PointUtf16::new(0, 3)), Bias::Right),
1657 PointUtf16::new(0, 2)
1658 );
1659
1660 assert_eq!(
1661 rope.clip_offset_utf16(OffsetUtf16(1), Bias::Left),
1662 OffsetUtf16(0)
1663 );
1664 assert_eq!(
1665 rope.clip_offset_utf16(OffsetUtf16(1), Bias::Right),
1666 OffsetUtf16(2)
1667 );
1668 assert_eq!(
1669 rope.clip_offset_utf16(OffsetUtf16(3), Bias::Right),
1670 OffsetUtf16(2)
1671 );
1672 }
1673
1674 #[test]
1675 fn test_prev_next_line() {
1676 let rope = Rope::from("abc\ndef\nghi\njkl");
1677
1678 let mut chunks = rope.chunks();
1679 assert_eq!(chunks.peek().unwrap().chars().next().unwrap(), 'a');
1680
1681 assert!(chunks.next_line());
1682 assert_eq!(chunks.peek().unwrap().chars().next().unwrap(), 'd');
1683
1684 assert!(chunks.next_line());
1685 assert_eq!(chunks.peek().unwrap().chars().next().unwrap(), 'g');
1686
1687 assert!(chunks.next_line());
1688 assert_eq!(chunks.peek().unwrap().chars().next().unwrap(), 'j');
1689
1690 assert!(!chunks.next_line());
1691 assert_eq!(chunks.peek(), None);
1692
1693 assert!(chunks.prev_line());
1694 assert_eq!(chunks.peek().unwrap().chars().next().unwrap(), 'j');
1695
1696 assert!(chunks.prev_line());
1697 assert_eq!(chunks.peek().unwrap().chars().next().unwrap(), 'g');
1698
1699 assert!(chunks.prev_line());
1700 assert_eq!(chunks.peek().unwrap().chars().next().unwrap(), 'd');
1701
1702 assert!(chunks.prev_line());
1703 assert_eq!(chunks.peek().unwrap().chars().next().unwrap(), 'a');
1704
1705 assert!(!chunks.prev_line());
1706 assert_eq!(chunks.peek().unwrap().chars().next().unwrap(), 'a');
1707
1708 // Only return true when the cursor has moved to the start of a line
1709 let mut chunks = rope.chunks_in_range(5..7);
1710 chunks.seek(6);
1711 assert!(!chunks.prev_line());
1712 assert_eq!(chunks.peek().unwrap().chars().next().unwrap(), 'e');
1713
1714 assert!(!chunks.next_line());
1715 assert_eq!(chunks.peek(), None);
1716 }
1717
1718 #[test]
1719 fn test_lines() {
1720 let rope = Rope::from("abc\ndefg\nhi");
1721 let mut lines = rope.chunks().lines();
1722 assert_eq!(lines.next(), Some("abc"));
1723 assert_eq!(lines.next(), Some("defg"));
1724 assert_eq!(lines.next(), Some("hi"));
1725 assert_eq!(lines.next(), None);
1726
1727 let rope = Rope::from("abc\ndefg\nhi\n");
1728 let mut lines = rope.chunks().lines();
1729 assert_eq!(lines.next(), Some("abc"));
1730 assert_eq!(lines.next(), Some("defg"));
1731 assert_eq!(lines.next(), Some("hi"));
1732 assert_eq!(lines.next(), Some(""));
1733 assert_eq!(lines.next(), None);
1734
1735 let rope = Rope::from("abc\ndefg\nhi");
1736 let mut lines = rope.reversed_chunks_in_range(0..rope.len()).lines();
1737 assert_eq!(lines.next(), Some("hi"));
1738 assert_eq!(lines.next(), Some("defg"));
1739 assert_eq!(lines.next(), Some("abc"));
1740 assert_eq!(lines.next(), None);
1741
1742 let rope = Rope::from("abc\ndefg\nhi\n");
1743 let mut lines = rope.reversed_chunks_in_range(0..rope.len()).lines();
1744 assert_eq!(lines.next(), Some(""));
1745 assert_eq!(lines.next(), Some("hi"));
1746 assert_eq!(lines.next(), Some("defg"));
1747 assert_eq!(lines.next(), Some("abc"));
1748 assert_eq!(lines.next(), None);
1749
1750 let rope = Rope::from("abc\nlonger line test\nhi");
1751 let mut lines = rope.chunks().lines();
1752 assert_eq!(lines.next(), Some("abc"));
1753 assert_eq!(lines.next(), Some("longer line test"));
1754 assert_eq!(lines.next(), Some("hi"));
1755 assert_eq!(lines.next(), None);
1756
1757 let rope = Rope::from("abc\nlonger line test\nhi");
1758 let mut lines = rope.reversed_chunks_in_range(0..rope.len()).lines();
1759 assert_eq!(lines.next(), Some("hi"));
1760 assert_eq!(lines.next(), Some("longer line test"));
1761 assert_eq!(lines.next(), Some("abc"));
1762 assert_eq!(lines.next(), None);
1763 }
1764
1765 #[gpui::test(iterations = 100)]
1766 fn test_random_rope(mut rng: StdRng) {
1767 let operations = env::var("OPERATIONS")
1768 .map(|i| i.parse().expect("invalid `OPERATIONS` variable"))
1769 .unwrap_or(10);
1770
1771 let mut expected = String::new();
1772 let mut actual = Rope::new();
1773 for _ in 0..operations {
1774 let end_ix = clip_offset(&expected, rng.random_range(0..=expected.len()), Right);
1775 let start_ix = clip_offset(&expected, rng.random_range(0..=end_ix), Left);
1776 let len = rng.random_range(0..=64);
1777 let new_text: String = RandomCharIter::new(&mut rng).take(len).collect();
1778
1779 let mut new_actual = Rope::new();
1780 let mut cursor = actual.cursor(0);
1781 new_actual.append(cursor.slice(start_ix));
1782 new_actual.push(&new_text);
1783 cursor.seek_forward(end_ix);
1784 new_actual.append(cursor.suffix());
1785 actual = new_actual;
1786
1787 expected.replace_range(start_ix..end_ix, &new_text);
1788
1789 assert_eq!(actual.text(), expected);
1790 log::info!("text: {:?}", expected);
1791
1792 for _ in 0..5 {
1793 let end_ix = clip_offset(&expected, rng.random_range(0..=expected.len()), Right);
1794 let start_ix = clip_offset(&expected, rng.random_range(0..=end_ix), Left);
1795
1796 let actual_text = actual.chunks_in_range(start_ix..end_ix).collect::<String>();
1797 assert_eq!(actual_text, &expected[start_ix..end_ix]);
1798
1799 let mut actual_text = String::new();
1800 actual
1801 .bytes_in_range(start_ix..end_ix)
1802 .read_to_string(&mut actual_text)
1803 .unwrap();
1804 assert_eq!(actual_text, &expected[start_ix..end_ix]);
1805
1806 assert_eq!(
1807 actual
1808 .reversed_chunks_in_range(start_ix..end_ix)
1809 .collect::<Vec<&str>>()
1810 .into_iter()
1811 .rev()
1812 .collect::<String>(),
1813 &expected[start_ix..end_ix]
1814 );
1815
1816 let mut expected_line_starts: Vec<_> = expected[start_ix..end_ix]
1817 .match_indices('\n')
1818 .map(|(index, _)| start_ix + index + 1)
1819 .collect();
1820
1821 let mut chunks = actual.chunks_in_range(start_ix..end_ix);
1822
1823 let mut actual_line_starts = Vec::new();
1824 while chunks.next_line() {
1825 actual_line_starts.push(chunks.offset());
1826 }
1827 assert_eq!(
1828 actual_line_starts,
1829 expected_line_starts,
1830 "actual line starts != expected line starts when using next_line() for {:?} ({:?})",
1831 &expected[start_ix..end_ix],
1832 start_ix..end_ix
1833 );
1834
1835 if start_ix < end_ix
1836 && (start_ix == 0 || expected.as_bytes()[start_ix - 1] == b'\n')
1837 {
1838 expected_line_starts.insert(0, start_ix);
1839 }
1840 // Remove the last index if it starts at the end of the range.
1841 if expected_line_starts.last() == Some(&end_ix) {
1842 expected_line_starts.pop();
1843 }
1844
1845 let mut actual_line_starts = Vec::new();
1846 while chunks.prev_line() {
1847 actual_line_starts.push(chunks.offset());
1848 }
1849 actual_line_starts.reverse();
1850 assert_eq!(
1851 actual_line_starts,
1852 expected_line_starts,
1853 "actual line starts != expected line starts when using prev_line() for {:?} ({:?})",
1854 &expected[start_ix..end_ix],
1855 start_ix..end_ix
1856 );
1857
1858 // Check that next_line/prev_line work correctly from random positions
1859 let mut offset = rng.random_range(start_ix..=end_ix);
1860 while !expected.is_char_boundary(offset) {
1861 offset -= 1;
1862 }
1863 chunks.seek(offset);
1864
1865 for _ in 0..5 {
1866 if rng.random() {
1867 let expected_next_line_start = expected[offset..end_ix]
1868 .find('\n')
1869 .map(|newline_ix| offset + newline_ix + 1);
1870
1871 let moved = chunks.next_line();
1872 assert_eq!(
1873 moved,
1874 expected_next_line_start.is_some(),
1875 "unexpected result from next_line after seeking to {} in range {:?} ({:?})",
1876 offset,
1877 start_ix..end_ix,
1878 &expected[start_ix..end_ix]
1879 );
1880 if let Some(expected_next_line_start) = expected_next_line_start {
1881 assert_eq!(
1882 chunks.offset(),
1883 expected_next_line_start,
1884 "invalid position after seeking to {} in range {:?} ({:?})",
1885 offset,
1886 start_ix..end_ix,
1887 &expected[start_ix..end_ix]
1888 );
1889 } else {
1890 assert_eq!(
1891 chunks.offset(),
1892 end_ix,
1893 "invalid position after seeking to {} in range {:?} ({:?})",
1894 offset,
1895 start_ix..end_ix,
1896 &expected[start_ix..end_ix]
1897 );
1898 }
1899 } else {
1900 let search_end = if offset > 0 && expected.as_bytes()[offset - 1] == b'\n' {
1901 offset - 1
1902 } else {
1903 offset
1904 };
1905
1906 let expected_prev_line_start = expected[..search_end]
1907 .rfind('\n')
1908 .and_then(|newline_ix| {
1909 let line_start_ix = newline_ix + 1;
1910 if line_start_ix >= start_ix {
1911 Some(line_start_ix)
1912 } else {
1913 None
1914 }
1915 })
1916 .or({
1917 if offset > 0 && start_ix == 0 {
1918 Some(0)
1919 } else {
1920 None
1921 }
1922 });
1923
1924 let moved = chunks.prev_line();
1925 assert_eq!(
1926 moved,
1927 expected_prev_line_start.is_some(),
1928 "unexpected result from prev_line after seeking to {} in range {:?} ({:?})",
1929 offset,
1930 start_ix..end_ix,
1931 &expected[start_ix..end_ix]
1932 );
1933 if let Some(expected_prev_line_start) = expected_prev_line_start {
1934 assert_eq!(
1935 chunks.offset(),
1936 expected_prev_line_start,
1937 "invalid position after seeking to {} in range {:?} ({:?})",
1938 offset,
1939 start_ix..end_ix,
1940 &expected[start_ix..end_ix]
1941 );
1942 } else {
1943 assert_eq!(
1944 chunks.offset(),
1945 start_ix,
1946 "invalid position after seeking to {} in range {:?} ({:?})",
1947 offset,
1948 start_ix..end_ix,
1949 &expected[start_ix..end_ix]
1950 );
1951 }
1952 }
1953
1954 assert!((start_ix..=end_ix).contains(&chunks.offset()));
1955 if rng.random() {
1956 offset = rng.random_range(start_ix..=end_ix);
1957 while !expected.is_char_boundary(offset) {
1958 offset -= 1;
1959 }
1960 chunks.seek(offset);
1961 } else {
1962 chunks.next();
1963 offset = chunks.offset();
1964 assert!((start_ix..=end_ix).contains(&chunks.offset()));
1965 }
1966 }
1967 }
1968
1969 let mut offset_utf16 = OffsetUtf16(0);
1970 let mut point = Point::new(0, 0);
1971 let mut point_utf16 = PointUtf16::new(0, 0);
1972 for (ix, ch) in expected.char_indices().chain(Some((expected.len(), '\0'))) {
1973 assert_eq!(actual.offset_to_point(ix), point, "offset_to_point({})", ix);
1974 assert_eq!(
1975 actual.offset_to_point_utf16(ix),
1976 point_utf16,
1977 "offset_to_point_utf16({})",
1978 ix
1979 );
1980 assert_eq!(
1981 actual.point_to_offset(point),
1982 ix,
1983 "point_to_offset({:?})",
1984 point
1985 );
1986 assert_eq!(
1987 actual.point_utf16_to_offset(point_utf16),
1988 ix,
1989 "point_utf16_to_offset({:?})",
1990 point_utf16
1991 );
1992 assert_eq!(
1993 actual.offset_to_offset_utf16(ix),
1994 offset_utf16,
1995 "offset_to_offset_utf16({:?})",
1996 ix
1997 );
1998 assert_eq!(
1999 actual.offset_utf16_to_offset(offset_utf16),
2000 ix,
2001 "offset_utf16_to_offset({:?})",
2002 offset_utf16
2003 );
2004 if ch == '\n' {
2005 point += Point::new(1, 0);
2006 point_utf16 += PointUtf16::new(1, 0);
2007 } else {
2008 point.column += ch.len_utf8() as u32;
2009 point_utf16.column += ch.len_utf16() as u32;
2010 }
2011 offset_utf16.0 += ch.len_utf16();
2012 }
2013
2014 let mut offset_utf16 = OffsetUtf16(0);
2015 let mut point_utf16 = Unclipped(PointUtf16::zero());
2016 for unit in expected.encode_utf16() {
2017 let left_offset = actual.clip_offset_utf16(offset_utf16, Bias::Left);
2018 let right_offset = actual.clip_offset_utf16(offset_utf16, Bias::Right);
2019 assert!(right_offset >= left_offset);
2020 // Ensure translating UTF-16 offsets to UTF-8 offsets doesn't panic.
2021 actual.offset_utf16_to_offset(left_offset);
2022 actual.offset_utf16_to_offset(right_offset);
2023
2024 let left_point = actual.clip_point_utf16(point_utf16, Bias::Left);
2025 let right_point = actual.clip_point_utf16(point_utf16, Bias::Right);
2026 assert!(right_point >= left_point);
2027 // Ensure translating valid UTF-16 points to offsets doesn't panic.
2028 actual.point_utf16_to_offset(left_point);
2029 actual.point_utf16_to_offset(right_point);
2030
2031 offset_utf16.0 += 1;
2032 if unit == b'\n' as u16 {
2033 point_utf16.0 += PointUtf16::new(1, 0);
2034 } else {
2035 point_utf16.0 += PointUtf16::new(0, 1);
2036 }
2037 }
2038
2039 for _ in 0..5 {
2040 let end_ix = clip_offset(&expected, rng.random_range(0..=expected.len()), Right);
2041 let start_ix = clip_offset(&expected, rng.random_range(0..=end_ix), Left);
2042 assert_eq!(
2043 actual.cursor(start_ix).summary::<TextSummary>(end_ix),
2044 TextSummary::from(&expected[start_ix..end_ix])
2045 );
2046 }
2047
2048 let mut expected_longest_rows = Vec::new();
2049 let mut longest_line_len = -1_isize;
2050 for (row, line) in expected.split('\n').enumerate() {
2051 let row = row as u32;
2052 assert_eq!(
2053 actual.line_len(row),
2054 line.len() as u32,
2055 "invalid line len for row {}",
2056 row
2057 );
2058
2059 let line_char_count = line.chars().count() as isize;
2060 match line_char_count.cmp(&longest_line_len) {
2061 Ordering::Less => {}
2062 Ordering::Equal => expected_longest_rows.push(row),
2063 Ordering::Greater => {
2064 longest_line_len = line_char_count;
2065 expected_longest_rows.clear();
2066 expected_longest_rows.push(row);
2067 }
2068 }
2069 }
2070
2071 let longest_row = actual.summary().longest_row;
2072 assert!(
2073 expected_longest_rows.contains(&longest_row),
2074 "incorrect longest row {}. expected {:?} with length {}",
2075 longest_row,
2076 expected_longest_rows,
2077 longest_line_len,
2078 );
2079 }
2080 }
2081
2082 #[test]
2083 fn test_chunks_equals_str() {
2084 let text = "This is a multi-chunk\n& multi-line test string!";
2085 let rope = Rope::from(text);
2086 for start in 0..text.len() {
2087 for end in start..text.len() {
2088 let range = start..end;
2089 let correct_substring = &text[start..end];
2090
2091 // Test that correct range returns true
2092 assert!(
2093 rope.chunks_in_range(range.clone())
2094 .equals_str(correct_substring)
2095 );
2096 assert!(
2097 rope.reversed_chunks_in_range(range.clone())
2098 .equals_str(correct_substring)
2099 );
2100
2101 // Test that all other ranges return false (unless they happen to match)
2102 for other_start in 0..text.len() {
2103 for other_end in other_start..text.len() {
2104 if other_start == start && other_end == end {
2105 continue;
2106 }
2107 let other_substring = &text[other_start..other_end];
2108
2109 // Only assert false if the substrings are actually different
2110 if other_substring == correct_substring {
2111 continue;
2112 }
2113 assert!(
2114 !rope
2115 .chunks_in_range(range.clone())
2116 .equals_str(other_substring)
2117 );
2118 assert!(
2119 !rope
2120 .reversed_chunks_in_range(range.clone())
2121 .equals_str(other_substring)
2122 );
2123 }
2124 }
2125 }
2126 }
2127
2128 let rope = Rope::from("");
2129 assert!(rope.chunks_in_range(0..0).equals_str(""));
2130 assert!(rope.reversed_chunks_in_range(0..0).equals_str(""));
2131 assert!(!rope.chunks_in_range(0..0).equals_str("foo"));
2132 assert!(!rope.reversed_chunks_in_range(0..0).equals_str("foo"));
2133 }
2134
2135 #[test]
2136 fn test_is_char_boundary() {
2137 let fixture = "地";
2138 let rope = Rope::from("地");
2139 for b in 0..=fixture.len() {
2140 assert_eq!(rope.is_char_boundary(b), fixture.is_char_boundary(b));
2141 }
2142 let fixture = "";
2143 let rope = Rope::from("");
2144 for b in 0..=fixture.len() {
2145 assert_eq!(rope.is_char_boundary(b), fixture.is_char_boundary(b));
2146 }
2147 let fixture = "🔴🟠🟡🟢🔵🟣⚫️⚪️🟤\n🏳️⚧️🏁🏳️🌈🏴☠️⛳️📬📭🏴🏳️🚩";
2148 let rope = Rope::from("🔴🟠🟡🟢🔵🟣⚫️⚪️🟤\n🏳️⚧️🏁🏳️🌈🏴☠️⛳️📬📭🏴🏳️🚩");
2149 for b in 0..=fixture.len() {
2150 assert_eq!(rope.is_char_boundary(b), fixture.is_char_boundary(b));
2151 }
2152 }
2153
2154 #[test]
2155 fn test_floor_char_boundary() {
2156 let fixture = "地";
2157 let rope = Rope::from("地");
2158 for b in 0..=fixture.len() {
2159 assert_eq!(rope.floor_char_boundary(b), fixture.floor_char_boundary(b));
2160 }
2161
2162 let fixture = "";
2163 let rope = Rope::from("");
2164 for b in 0..=fixture.len() {
2165 assert_eq!(rope.floor_char_boundary(b), fixture.floor_char_boundary(b));
2166 }
2167
2168 let fixture = "🔴🟠🟡🟢🔵🟣⚫️⚪️🟤\n🏳️⚧️🏁🏳️🌈🏴☠️⛳️📬📭🏴🏳️🚩";
2169 let rope = Rope::from("🔴🟠🟡🟢🔵🟣⚫️⚪️🟤\n🏳️⚧️🏁🏳️🌈🏴☠️⛳️📬📭🏴🏳️🚩");
2170 for b in 0..=fixture.len() {
2171 assert_eq!(rope.floor_char_boundary(b), fixture.floor_char_boundary(b));
2172 }
2173 }
2174
2175 #[test]
2176 fn test_ceil_char_boundary() {
2177 let fixture = "地";
2178 let rope = Rope::from("地");
2179 for b in 0..=fixture.len() {
2180 assert_eq!(rope.ceil_char_boundary(b), fixture.ceil_char_boundary(b));
2181 }
2182
2183 let fixture = "";
2184 let rope = Rope::from("");
2185 for b in 0..=fixture.len() {
2186 assert_eq!(rope.ceil_char_boundary(b), fixture.ceil_char_boundary(b));
2187 }
2188
2189 let fixture = "🔴🟠🟡🟢🔵🟣⚫️⚪️🟤\n🏳️⚧️🏁🏳️🌈🏴☠️⛳️📬📭🏴🏳️🚩";
2190 let rope = Rope::from("🔴🟠🟡🟢🔵🟣⚫️⚪️🟤\n🏳️⚧️🏁🏳️🌈🏴☠️⛳️📬📭🏴🏳️🚩");
2191 for b in 0..=fixture.len() {
2192 assert_eq!(rope.ceil_char_boundary(b), fixture.ceil_char_boundary(b));
2193 }
2194 }
2195
2196 fn clip_offset(text: &str, mut offset: usize, bias: Bias) -> usize {
2197 while !text.is_char_boundary(offset) {
2198 match bias {
2199 Bias::Left => offset -= 1,
2200 Bias::Right => offset += 1,
2201 }
2202 }
2203 offset
2204 }
2205
2206 impl Rope {
2207 fn text(&self) -> String {
2208 let mut text = String::new();
2209 for chunk in self.chunks.cursor::<()>(()) {
2210 text.push_str(&chunk.text);
2211 }
2212 text
2213 }
2214 }
2215}