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