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