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