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