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