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