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