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