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