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