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