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