1mod offset_utf16;
   2mod point;
   3mod point_utf16;
   4mod unclipped;
   5
   6use arrayvec::ArrayString;
   7use bromberg_sl2::HashMatrix;
   8use smallvec::SmallVec;
   9use std::{
  10    cmp, fmt, io, mem,
  11    ops::{AddAssign, Range},
  12    str,
  13};
  14use sum_tree::{Bias, Dimension, SumTree};
  15use util::debug_panic;
  16
  17pub use offset_utf16::OffsetUtf16;
  18pub use point::Point;
  19pub use point_utf16::PointUtf16;
  20pub use unclipped::Unclipped;
  21
  22#[cfg(test)]
  23const CHUNK_BASE: usize = 6;
  24
  25#[cfg(not(test))]
  26const CHUNK_BASE: usize = 16;
  27
  28/// Type alias to [HashMatrix], an implementation of a homomorphic hash function. Two [Rope] instances
  29/// containing the same text will produce the same fingerprint. This hash function is special in that
  30/// it allows us to hash individual chunks and aggregate them up the [Rope]'s tree, with the resulting
  31/// hash being equivalent to hashing all the text contained in the [Rope] at once.
  32pub type RopeFingerprint = HashMatrix;
  33
  34#[derive(Clone, Default)]
  35pub struct Rope {
  36    chunks: SumTree<Chunk>,
  37}
  38
  39impl Rope {
  40    pub fn new() -> Self {
  41        Self::default()
  42    }
  43
  44    pub fn append(&mut self, rope: Rope) {
  45        let mut chunks = rope.chunks.cursor::<()>();
  46        chunks.next(&());
  47        if let Some(chunk) = chunks.item() {
  48            if self.chunks.last().map_or(false, |c| c.0.len() < CHUNK_BASE)
  49                || chunk.0.len() < CHUNK_BASE
  50            {
  51                self.push(&chunk.0);
  52                chunks.next(&());
  53            }
  54        }
  55
  56        self.chunks.append(chunks.suffix(&()), &());
  57        self.check_invariants();
  58    }
  59
  60    pub fn replace(&mut self, range: Range<usize>, text: &str) {
  61        let mut new_rope = Rope::new();
  62        let mut cursor = self.cursor(0);
  63        new_rope.append(cursor.slice(range.start));
  64        cursor.seek_forward(range.end);
  65        new_rope.push(text);
  66        new_rope.append(cursor.suffix());
  67        *self = new_rope;
  68    }
  69
  70    pub fn slice(&self, range: Range<usize>) -> Rope {
  71        let mut cursor = self.cursor(0);
  72        cursor.seek_forward(range.start);
  73        cursor.slice(range.end)
  74    }
  75
  76    pub fn slice_rows(&self, range: Range<u32>) -> Rope {
  77        //This would be more efficient with a forward advance after the first, but it's fine
  78        let start = self.point_to_offset(Point::new(range.start, 0));
  79        let end = self.point_to_offset(Point::new(range.end, 0));
  80        self.slice(start..end)
  81    }
  82
  83    pub fn push(&mut self, text: &str) {
  84        let mut new_chunks = SmallVec::<[_; 16]>::new();
  85        let mut new_chunk = ArrayString::new();
  86        for ch in text.chars() {
  87            if new_chunk.len() + ch.len_utf8() > 2 * CHUNK_BASE {
  88                new_chunks.push(Chunk(new_chunk));
  89                new_chunk = ArrayString::new();
  90            }
  91
  92            new_chunk.push(ch);
  93        }
  94        if !new_chunk.is_empty() {
  95            new_chunks.push(Chunk(new_chunk));
  96        }
  97
  98        let mut new_chunks = new_chunks.into_iter();
  99        let mut first_new_chunk = new_chunks.next();
 100        self.chunks.update_last(
 101            |last_chunk| {
 102                if let Some(first_new_chunk_ref) = first_new_chunk.as_mut() {
 103                    if last_chunk.0.len() + first_new_chunk_ref.0.len() <= 2 * CHUNK_BASE {
 104                        last_chunk.0.push_str(&first_new_chunk.take().unwrap().0);
 105                    } else {
 106                        let mut text = ArrayString::<{ 4 * CHUNK_BASE }>::new();
 107                        text.push_str(&last_chunk.0);
 108                        text.push_str(&first_new_chunk_ref.0);
 109                        let (left, right) = text.split_at(find_split_ix(&text));
 110                        last_chunk.0.clear();
 111                        last_chunk.0.push_str(left);
 112                        first_new_chunk_ref.0.clear();
 113                        first_new_chunk_ref.0.push_str(right);
 114                    }
 115                }
 116            },
 117            &(),
 118        );
 119
 120        self.chunks
 121            .extend(first_new_chunk.into_iter().chain(new_chunks), &());
 122        self.check_invariants();
 123    }
 124
 125    pub fn push_front(&mut self, text: &str) {
 126        let suffix = mem::replace(self, Rope::from(text));
 127        self.append(suffix);
 128    }
 129
 130    fn check_invariants(&self) {
 131        #[cfg(test)]
 132        {
 133            // Ensure all chunks except maybe the last one are not underflowing.
 134            // Allow some wiggle room for multibyte characters at chunk boundaries.
 135            let mut chunks = self.chunks.cursor::<()>().peekable();
 136            while let Some(chunk) = chunks.next() {
 137                if chunks.peek().is_some() {
 138                    assert!(chunk.0.len() + 3 >= CHUNK_BASE);
 139                }
 140            }
 141        }
 142    }
 143
 144    pub fn summary(&self) -> TextSummary {
 145        self.chunks.summary().text.clone()
 146    }
 147
 148    pub fn len(&self) -> usize {
 149        self.chunks.extent(&())
 150    }
 151
 152    pub fn is_empty(&self) -> bool {
 153        self.len() == 0
 154    }
 155
 156    pub fn max_point(&self) -> Point {
 157        self.chunks.extent(&())
 158    }
 159
 160    pub fn max_point_utf16(&self) -> PointUtf16 {
 161        self.chunks.extent(&())
 162    }
 163
 164    pub fn cursor(&self, offset: usize) -> Cursor {
 165        Cursor::new(self, offset)
 166    }
 167
 168    pub fn chars(&self) -> impl Iterator<Item = char> + '_ {
 169        self.chars_at(0)
 170    }
 171
 172    pub fn chars_at(&self, start: usize) -> impl Iterator<Item = char> + '_ {
 173        self.chunks_in_range(start..self.len()).flat_map(str::chars)
 174    }
 175
 176    pub fn reversed_chars_at(&self, start: usize) -> impl Iterator<Item = char> + '_ {
 177        self.reversed_chunks_in_range(0..start)
 178            .flat_map(|chunk| chunk.chars().rev())
 179    }
 180
 181    pub fn bytes_in_range(&self, range: Range<usize>) -> Bytes {
 182        Bytes::new(self, range, false)
 183    }
 184
 185    pub fn reversed_bytes_in_range(&self, range: Range<usize>) -> Bytes {
 186        Bytes::new(self, range, true)
 187    }
 188
 189    pub fn chunks(&self) -> Chunks {
 190        self.chunks_in_range(0..self.len())
 191    }
 192
 193    pub fn chunks_in_range(&self, range: Range<usize>) -> Chunks {
 194        Chunks::new(self, range, false)
 195    }
 196
 197    pub fn reversed_chunks_in_range(&self, range: Range<usize>) -> Chunks {
 198        Chunks::new(self, range, true)
 199    }
 200
 201    pub fn offset_to_offset_utf16(&self, offset: usize) -> OffsetUtf16 {
 202        if offset >= self.summary().len {
 203            return self.summary().len_utf16;
 204        }
 205        let mut cursor = self.chunks.cursor::<(usize, OffsetUtf16)>();
 206        cursor.seek(&offset, Bias::Left, &());
 207        let overshoot = offset - cursor.start().0;
 208        cursor.start().1
 209            + cursor.item().map_or(Default::default(), |chunk| {
 210                chunk.offset_to_offset_utf16(overshoot)
 211            })
 212    }
 213
 214    pub fn offset_utf16_to_offset(&self, offset: OffsetUtf16) -> usize {
 215        if offset >= self.summary().len_utf16 {
 216            return self.summary().len;
 217        }
 218        let mut cursor = self.chunks.cursor::<(OffsetUtf16, usize)>();
 219        cursor.seek(&offset, Bias::Left, &());
 220        let overshoot = offset - cursor.start().0;
 221        cursor.start().1
 222            + cursor.item().map_or(Default::default(), |chunk| {
 223                chunk.offset_utf16_to_offset(overshoot)
 224            })
 225    }
 226
 227    pub fn offset_to_point(&self, offset: usize) -> Point {
 228        if offset >= self.summary().len {
 229            return self.summary().lines;
 230        }
 231        let mut cursor = self.chunks.cursor::<(usize, Point)>();
 232        cursor.seek(&offset, Bias::Left, &());
 233        let overshoot = offset - cursor.start().0;
 234        cursor.start().1
 235            + cursor
 236                .item()
 237                .map_or(Point::zero(), |chunk| chunk.offset_to_point(overshoot))
 238    }
 239
 240    pub fn offset_to_point_utf16(&self, offset: usize) -> PointUtf16 {
 241        if offset >= self.summary().len {
 242            return self.summary().lines_utf16();
 243        }
 244        let mut cursor = self.chunks.cursor::<(usize, PointUtf16)>();
 245        cursor.seek(&offset, Bias::Left, &());
 246        let overshoot = offset - cursor.start().0;
 247        cursor.start().1
 248            + cursor.item().map_or(PointUtf16::zero(), |chunk| {
 249                chunk.offset_to_point_utf16(overshoot)
 250            })
 251    }
 252
 253    pub fn point_to_point_utf16(&self, point: Point) -> PointUtf16 {
 254        if point >= self.summary().lines {
 255            return self.summary().lines_utf16();
 256        }
 257        let mut cursor = self.chunks.cursor::<(Point, PointUtf16)>();
 258        cursor.seek(&point, Bias::Left, &());
 259        let overshoot = point - cursor.start().0;
 260        cursor.start().1
 261            + cursor.item().map_or(PointUtf16::zero(), |chunk| {
 262                chunk.point_to_point_utf16(overshoot)
 263            })
 264    }
 265
 266    pub fn point_to_offset(&self, point: Point) -> usize {
 267        if point >= self.summary().lines {
 268            return self.summary().len;
 269        }
 270        let mut cursor = self.chunks.cursor::<(Point, usize)>();
 271        cursor.seek(&point, Bias::Left, &());
 272        let overshoot = point - cursor.start().0;
 273        cursor.start().1
 274            + cursor
 275                .item()
 276                .map_or(0, |chunk| chunk.point_to_offset(overshoot))
 277    }
 278
 279    pub fn point_utf16_to_offset(&self, point: PointUtf16) -> usize {
 280        self.point_utf16_to_offset_impl(point, false)
 281    }
 282
 283    pub fn unclipped_point_utf16_to_offset(&self, point: Unclipped<PointUtf16>) -> usize {
 284        self.point_utf16_to_offset_impl(point.0, true)
 285    }
 286
 287    fn point_utf16_to_offset_impl(&self, point: PointUtf16, clip: bool) -> usize {
 288        if point >= self.summary().lines_utf16() {
 289            return self.summary().len;
 290        }
 291        let mut cursor = self.chunks.cursor::<(PointUtf16, usize)>();
 292        cursor.seek(&point, Bias::Left, &());
 293        let overshoot = point - cursor.start().0;
 294        cursor.start().1
 295            + cursor
 296                .item()
 297                .map_or(0, |chunk| chunk.point_utf16_to_offset(overshoot, clip))
 298    }
 299
 300    pub fn unclipped_point_utf16_to_point(&self, point: Unclipped<PointUtf16>) -> Point {
 301        if point.0 >= self.summary().lines_utf16() {
 302            return self.summary().lines;
 303        }
 304        let mut cursor = self.chunks.cursor::<(PointUtf16, Point)>();
 305        cursor.seek(&point.0, Bias::Left, &());
 306        let overshoot = Unclipped(point.0 - cursor.start().0);
 307        cursor.start().1
 308            + cursor.item().map_or(Point::zero(), |chunk| {
 309                chunk.unclipped_point_utf16_to_point(overshoot)
 310            })
 311    }
 312
 313    pub fn clip_offset(&self, mut offset: usize, bias: Bias) -> usize {
 314        let mut cursor = self.chunks.cursor::<usize>();
 315        cursor.seek(&offset, Bias::Left, &());
 316        if let Some(chunk) = cursor.item() {
 317            let mut ix = offset - cursor.start();
 318            while !chunk.0.is_char_boundary(ix) {
 319                match bias {
 320                    Bias::Left => {
 321                        ix -= 1;
 322                        offset -= 1;
 323                    }
 324                    Bias::Right => {
 325                        ix += 1;
 326                        offset += 1;
 327                    }
 328                }
 329            }
 330            offset
 331        } else {
 332            self.summary().len
 333        }
 334    }
 335
 336    pub fn clip_offset_utf16(&self, offset: OffsetUtf16, bias: Bias) -> OffsetUtf16 {
 337        let mut cursor = self.chunks.cursor::<OffsetUtf16>();
 338        cursor.seek(&offset, Bias::Right, &());
 339        if let Some(chunk) = cursor.item() {
 340            let overshoot = offset - cursor.start();
 341            *cursor.start() + chunk.clip_offset_utf16(overshoot, bias)
 342        } else {
 343            self.summary().len_utf16
 344        }
 345    }
 346
 347    pub fn clip_point(&self, point: Point, bias: Bias) -> Point {
 348        let mut cursor = self.chunks.cursor::<Point>();
 349        cursor.seek(&point, Bias::Right, &());
 350        if let Some(chunk) = cursor.item() {
 351            let overshoot = point - cursor.start();
 352            *cursor.start() + chunk.clip_point(overshoot, bias)
 353        } else {
 354            self.summary().lines
 355        }
 356    }
 357
 358    pub fn clip_point_utf16(&self, point: Unclipped<PointUtf16>, bias: Bias) -> PointUtf16 {
 359        let mut cursor = self.chunks.cursor::<PointUtf16>();
 360        cursor.seek(&point.0, Bias::Right, &());
 361        if let Some(chunk) = cursor.item() {
 362            let overshoot = Unclipped(point.0 - cursor.start());
 363            *cursor.start() + chunk.clip_point_utf16(overshoot, bias)
 364        } else {
 365            self.summary().lines_utf16()
 366        }
 367    }
 368
 369    pub fn line_len(&self, row: u32) -> u32 {
 370        self.clip_point(Point::new(row, u32::MAX), Bias::Left)
 371            .column
 372    }
 373
 374    pub fn fingerprint(&self) -> RopeFingerprint {
 375        self.chunks.summary().fingerprint
 376    }
 377}
 378
 379impl<'a> From<&'a str> for Rope {
 380    fn from(text: &'a str) -> Self {
 381        let mut rope = Self::new();
 382        rope.push(text);
 383        rope
 384    }
 385}
 386
 387impl fmt::Display for Rope {
 388    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 389        for chunk in self.chunks() {
 390            write!(f, "{}", chunk)?;
 391        }
 392        Ok(())
 393    }
 394}
 395
 396impl fmt::Debug for Rope {
 397    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 398        use std::fmt::Write as _;
 399
 400        write!(f, "\"")?;
 401        let mut format_string = String::new();
 402        for chunk in self.chunks() {
 403            write!(&mut format_string, "{:?}", chunk)?;
 404            write!(f, "{}", &format_string[1..format_string.len() - 1])?;
 405            format_string.clear();
 406        }
 407        write!(f, "\"")?;
 408        Ok(())
 409    }
 410}
 411
 412pub struct Cursor<'a> {
 413    rope: &'a Rope,
 414    chunks: sum_tree::Cursor<'a, Chunk, usize>,
 415    offset: usize,
 416}
 417
 418impl<'a> Cursor<'a> {
 419    pub fn new(rope: &'a Rope, offset: usize) -> Self {
 420        let mut chunks = rope.chunks.cursor();
 421        chunks.seek(&offset, Bias::Right, &());
 422        Self {
 423            rope,
 424            chunks,
 425            offset,
 426        }
 427    }
 428
 429    pub fn seek_forward(&mut self, end_offset: usize) {
 430        debug_assert!(end_offset >= self.offset);
 431
 432        self.chunks.seek_forward(&end_offset, Bias::Right, &());
 433        self.offset = end_offset;
 434    }
 435
 436    pub fn slice(&mut self, end_offset: usize) -> Rope {
 437        debug_assert!(
 438            end_offset >= self.offset,
 439            "cannot slice backwards from {} to {}",
 440            self.offset,
 441            end_offset
 442        );
 443
 444        let mut slice = Rope::new();
 445        if let Some(start_chunk) = self.chunks.item() {
 446            let start_ix = self.offset - self.chunks.start();
 447            let end_ix = cmp::min(end_offset, self.chunks.end(&())) - self.chunks.start();
 448            slice.push(&start_chunk.0[start_ix..end_ix]);
 449        }
 450
 451        if end_offset > self.chunks.end(&()) {
 452            self.chunks.next(&());
 453            slice.append(Rope {
 454                chunks: self.chunks.slice(&end_offset, Bias::Right, &()),
 455            });
 456            if let Some(end_chunk) = self.chunks.item() {
 457                let end_ix = end_offset - self.chunks.start();
 458                slice.push(&end_chunk.0[..end_ix]);
 459            }
 460        }
 461
 462        self.offset = end_offset;
 463        slice
 464    }
 465
 466    pub fn summary<D: TextDimension>(&mut self, end_offset: usize) -> D {
 467        debug_assert!(end_offset >= self.offset);
 468
 469        let mut summary = D::default();
 470        if let Some(start_chunk) = self.chunks.item() {
 471            let start_ix = self.offset - self.chunks.start();
 472            let end_ix = cmp::min(end_offset, self.chunks.end(&())) - self.chunks.start();
 473            summary.add_assign(&D::from_text_summary(&TextSummary::from(
 474                &start_chunk.0[start_ix..end_ix],
 475            )));
 476        }
 477
 478        if end_offset > self.chunks.end(&()) {
 479            self.chunks.next(&());
 480            summary.add_assign(&self.chunks.summary(&end_offset, Bias::Right, &()));
 481            if let Some(end_chunk) = self.chunks.item() {
 482                let end_ix = end_offset - self.chunks.start();
 483                summary.add_assign(&D::from_text_summary(&TextSummary::from(
 484                    &end_chunk.0[..end_ix],
 485                )));
 486            }
 487        }
 488
 489        self.offset = end_offset;
 490        summary
 491    }
 492
 493    pub fn suffix(mut self) -> Rope {
 494        self.slice(self.rope.chunks.extent(&()))
 495    }
 496
 497    pub fn offset(&self) -> usize {
 498        self.offset
 499    }
 500}
 501
 502pub struct Chunks<'a> {
 503    chunks: sum_tree::Cursor<'a, Chunk, usize>,
 504    range: Range<usize>,
 505    reversed: bool,
 506}
 507
 508impl<'a> Chunks<'a> {
 509    pub fn new(rope: &'a Rope, range: Range<usize>, reversed: bool) -> Self {
 510        let mut chunks = rope.chunks.cursor();
 511        if reversed {
 512            chunks.seek(&range.end, Bias::Left, &());
 513        } else {
 514            chunks.seek(&range.start, Bias::Right, &());
 515        }
 516        Self {
 517            chunks,
 518            range,
 519            reversed,
 520        }
 521    }
 522
 523    pub fn offset(&self) -> usize {
 524        if self.reversed {
 525            self.range.end.min(self.chunks.end(&()))
 526        } else {
 527            self.range.start.max(*self.chunks.start())
 528        }
 529    }
 530
 531    pub fn seek(&mut self, offset: usize) {
 532        let bias = if self.reversed {
 533            Bias::Left
 534        } else {
 535            Bias::Right
 536        };
 537
 538        if offset >= self.chunks.end(&()) {
 539            self.chunks.seek_forward(&offset, bias, &());
 540        } else {
 541            self.chunks.seek(&offset, bias, &());
 542        }
 543
 544        if self.reversed {
 545            self.range.end = offset;
 546        } else {
 547            self.range.start = offset;
 548        }
 549    }
 550
 551    pub fn peek(&self) -> Option<&'a str> {
 552        let chunk = self.chunks.item()?;
 553        if self.reversed && self.range.start >= self.chunks.end(&()) {
 554            return None;
 555        }
 556        let chunk_start = *self.chunks.start();
 557        if self.range.end <= chunk_start {
 558            return None;
 559        }
 560
 561        let start = self.range.start.saturating_sub(chunk_start);
 562        let end = self.range.end - chunk_start;
 563        Some(&chunk.0[start..chunk.0.len().min(end)])
 564    }
 565}
 566
 567impl<'a> Iterator for Chunks<'a> {
 568    type Item = &'a str;
 569
 570    fn next(&mut self) -> Option<Self::Item> {
 571        let result = self.peek();
 572        if result.is_some() {
 573            if self.reversed {
 574                self.chunks.prev(&());
 575            } else {
 576                self.chunks.next(&());
 577            }
 578        }
 579        result
 580    }
 581}
 582
 583pub struct Bytes<'a> {
 584    chunks: sum_tree::Cursor<'a, Chunk, usize>,
 585    range: Range<usize>,
 586    reversed: bool,
 587}
 588
 589impl<'a> Bytes<'a> {
 590    pub fn new(rope: &'a Rope, range: Range<usize>, reversed: bool) -> Self {
 591        let mut chunks = rope.chunks.cursor();
 592        if reversed {
 593            chunks.seek(&range.end, Bias::Left, &());
 594        } else {
 595            chunks.seek(&range.start, Bias::Right, &());
 596        }
 597        Self {
 598            chunks,
 599            range,
 600            reversed,
 601        }
 602    }
 603
 604    pub fn peek(&self) -> Option<&'a [u8]> {
 605        let chunk = self.chunks.item()?;
 606        if self.reversed && self.range.start >= self.chunks.end(&()) {
 607            return None;
 608        }
 609        let chunk_start = *self.chunks.start();
 610        if self.range.end <= chunk_start {
 611            return None;
 612        }
 613        let start = self.range.start.saturating_sub(chunk_start);
 614        let end = self.range.end - chunk_start;
 615        Some(&chunk.0.as_bytes()[start..chunk.0.len().min(end)])
 616    }
 617}
 618
 619impl<'a> Iterator for Bytes<'a> {
 620    type Item = &'a [u8];
 621
 622    fn next(&mut self) -> Option<Self::Item> {
 623        let result = self.peek();
 624        if result.is_some() {
 625            if self.reversed {
 626                self.chunks.prev(&());
 627            } else {
 628                self.chunks.next(&());
 629            }
 630        }
 631        result
 632    }
 633}
 634
 635impl<'a> io::Read for Bytes<'a> {
 636    fn read(&mut self, buf: &mut [u8]) -> io::Result<usize> {
 637        if let Some(chunk) = self.peek() {
 638            let len = cmp::min(buf.len(), chunk.len());
 639            if self.reversed {
 640                buf[..len].copy_from_slice(&chunk[chunk.len() - len..]);
 641                buf[..len].reverse();
 642                self.range.end -= len;
 643            } else {
 644                buf[..len].copy_from_slice(&chunk[..len]);
 645                self.range.start += len;
 646            }
 647
 648            if len == chunk.len() {
 649                if self.reversed {
 650                    self.chunks.prev(&());
 651                } else {
 652                    self.chunks.next(&());
 653                }
 654            }
 655            Ok(len)
 656        } else {
 657            Ok(0)
 658        }
 659    }
 660}
 661
 662#[derive(Clone, Debug, Default)]
 663struct Chunk(ArrayString<{ 2 * CHUNK_BASE }>);
 664
 665impl Chunk {
 666    fn offset_to_offset_utf16(&self, target: usize) -> OffsetUtf16 {
 667        let mut offset = 0;
 668        let mut offset_utf16 = OffsetUtf16(0);
 669        for ch in self.0.chars() {
 670            if offset >= target {
 671                break;
 672            }
 673
 674            offset += ch.len_utf8();
 675            offset_utf16.0 += ch.len_utf16();
 676        }
 677        offset_utf16
 678    }
 679
 680    fn offset_utf16_to_offset(&self, target: OffsetUtf16) -> usize {
 681        let mut offset_utf16 = OffsetUtf16(0);
 682        let mut offset = 0;
 683        for ch in self.0.chars() {
 684            if offset_utf16 >= target {
 685                break;
 686            }
 687
 688            offset += ch.len_utf8();
 689            offset_utf16.0 += ch.len_utf16();
 690        }
 691        offset
 692    }
 693
 694    fn offset_to_point(&self, target: usize) -> Point {
 695        let mut offset = 0;
 696        let mut point = Point::new(0, 0);
 697        for ch in self.0.chars() {
 698            if offset >= target {
 699                break;
 700            }
 701
 702            if ch == '\n' {
 703                point.row += 1;
 704                point.column = 0;
 705            } else {
 706                point.column += ch.len_utf8() as u32;
 707            }
 708            offset += ch.len_utf8();
 709        }
 710        point
 711    }
 712
 713    fn offset_to_point_utf16(&self, target: usize) -> PointUtf16 {
 714        let mut offset = 0;
 715        let mut point = PointUtf16::new(0, 0);
 716        for ch in self.0.chars() {
 717            if offset >= target {
 718                break;
 719            }
 720
 721            if ch == '\n' {
 722                point.row += 1;
 723                point.column = 0;
 724            } else {
 725                point.column += ch.len_utf16() as u32;
 726            }
 727            offset += ch.len_utf8();
 728        }
 729        point
 730    }
 731
 732    fn point_to_offset(&self, target: Point) -> usize {
 733        let mut offset = 0;
 734        let mut point = Point::new(0, 0);
 735
 736        for ch in self.0.chars() {
 737            if point >= target {
 738                if point > target {
 739                    debug_panic!("point {target:?} is inside of character {ch:?}");
 740                }
 741                break;
 742            }
 743
 744            if ch == '\n' {
 745                point.row += 1;
 746                point.column = 0;
 747
 748                if point.row > target.row {
 749                    debug_panic!(
 750                        "point {target:?} is beyond the end of a line with length {}",
 751                        point.column
 752                    );
 753                    break;
 754                }
 755            } else {
 756                point.column += ch.len_utf8() as u32;
 757            }
 758
 759            offset += ch.len_utf8();
 760        }
 761
 762        offset
 763    }
 764
 765    fn point_to_point_utf16(&self, target: Point) -> PointUtf16 {
 766        let mut point = Point::zero();
 767        let mut point_utf16 = PointUtf16::new(0, 0);
 768        for ch in self.0.chars() {
 769            if point >= target {
 770                break;
 771            }
 772
 773            if ch == '\n' {
 774                point_utf16.row += 1;
 775                point_utf16.column = 0;
 776                point.row += 1;
 777                point.column = 0;
 778            } else {
 779                point_utf16.column += ch.len_utf16() as u32;
 780                point.column += ch.len_utf8() as u32;
 781            }
 782        }
 783        point_utf16
 784    }
 785
 786    fn point_utf16_to_offset(&self, target: PointUtf16, clip: bool) -> usize {
 787        let mut offset = 0;
 788        let mut point = PointUtf16::new(0, 0);
 789
 790        for ch in self.0.chars() {
 791            if point == target {
 792                break;
 793            }
 794
 795            if ch == '\n' {
 796                point.row += 1;
 797                point.column = 0;
 798
 799                if point.row > target.row {
 800                    if !clip {
 801                        debug_panic!(
 802                            "point {target:?} is beyond the end of a line with length {}",
 803                            point.column
 804                        );
 805                    }
 806                    // Return the offset of the newline
 807                    return offset;
 808                }
 809            } else {
 810                point.column += ch.len_utf16() as u32;
 811            }
 812
 813            if point > target {
 814                if !clip {
 815                    debug_panic!("point {target:?} is inside of codepoint {ch:?}");
 816                }
 817                // Return the offset of the codepoint which we have landed within, bias left
 818                return offset;
 819            }
 820
 821            offset += ch.len_utf8();
 822        }
 823
 824        offset
 825    }
 826
 827    fn unclipped_point_utf16_to_point(&self, target: Unclipped<PointUtf16>) -> Point {
 828        let mut point = Point::zero();
 829        let mut point_utf16 = PointUtf16::zero();
 830
 831        for ch in self.0.chars() {
 832            if point_utf16 == target.0 {
 833                break;
 834            }
 835
 836            if point_utf16 > target.0 {
 837                // If the point is past the end of a line or inside of a code point,
 838                // return the last valid point before the target.
 839                return point;
 840            }
 841
 842            if ch == '\n' {
 843                point_utf16 += PointUtf16::new(1, 0);
 844                point += Point::new(1, 0);
 845            } else {
 846                point_utf16 += PointUtf16::new(0, ch.len_utf16() as u32);
 847                point += Point::new(0, ch.len_utf8() as u32);
 848            }
 849        }
 850
 851        point
 852    }
 853
 854    fn clip_point(&self, target: Point, bias: Bias) -> Point {
 855        for (row, line) in self.0.split('\n').enumerate() {
 856            if row == target.row as usize {
 857                let mut column = target.column.min(line.len() as u32);
 858                while !line.is_char_boundary(column as usize) {
 859                    match bias {
 860                        Bias::Left => column -= 1,
 861                        Bias::Right => column += 1,
 862                    }
 863                }
 864                return Point::new(row as u32, column);
 865            }
 866        }
 867        unreachable!()
 868    }
 869
 870    fn clip_point_utf16(&self, target: Unclipped<PointUtf16>, bias: Bias) -> PointUtf16 {
 871        for (row, line) in self.0.split('\n').enumerate() {
 872            if row == target.0.row as usize {
 873                let mut code_units = line.encode_utf16();
 874                let mut column = code_units.by_ref().take(target.0.column as usize).count();
 875                if char::decode_utf16(code_units).next().transpose().is_err() {
 876                    match bias {
 877                        Bias::Left => column -= 1,
 878                        Bias::Right => column += 1,
 879                    }
 880                }
 881                return PointUtf16::new(row as u32, column as u32);
 882            }
 883        }
 884        unreachable!()
 885    }
 886
 887    fn clip_offset_utf16(&self, target: OffsetUtf16, bias: Bias) -> OffsetUtf16 {
 888        let mut code_units = self.0.encode_utf16();
 889        let mut offset = code_units.by_ref().take(target.0 as usize).count();
 890        if char::decode_utf16(code_units).next().transpose().is_err() {
 891            match bias {
 892                Bias::Left => offset -= 1,
 893                Bias::Right => offset += 1,
 894            }
 895        }
 896        OffsetUtf16(offset)
 897    }
 898}
 899
 900impl sum_tree::Item for Chunk {
 901    type Summary = ChunkSummary;
 902
 903    fn summary(&self) -> Self::Summary {
 904        ChunkSummary::from(self.0.as_str())
 905    }
 906}
 907
 908#[derive(Clone, Debug, Default, Eq, PartialEq)]
 909pub struct ChunkSummary {
 910    text: TextSummary,
 911    fingerprint: RopeFingerprint,
 912}
 913
 914impl<'a> From<&'a str> for ChunkSummary {
 915    fn from(text: &'a str) -> Self {
 916        Self {
 917            text: TextSummary::from(text),
 918            fingerprint: bromberg_sl2::hash_strict(text.as_bytes()),
 919        }
 920    }
 921}
 922
 923impl sum_tree::Summary for ChunkSummary {
 924    type Context = ();
 925
 926    fn add_summary(&mut self, summary: &Self, _: &()) {
 927        self.text += &summary.text;
 928        self.fingerprint = self.fingerprint * summary.fingerprint;
 929    }
 930}
 931
 932#[derive(Clone, Debug, Default, Eq, PartialEq)]
 933pub struct TextSummary {
 934    pub len: usize,
 935    pub len_utf16: OffsetUtf16,
 936    pub lines: Point,
 937    pub first_line_chars: u32,
 938    pub last_line_chars: u32,
 939    pub last_line_len_utf16: u32,
 940    pub longest_row: u32,
 941    pub longest_row_chars: u32,
 942}
 943
 944impl TextSummary {
 945    pub fn lines_utf16(&self) -> PointUtf16 {
 946        PointUtf16 {
 947            row: self.lines.row,
 948            column: self.last_line_len_utf16,
 949        }
 950    }
 951}
 952
 953impl<'a> From<&'a str> for TextSummary {
 954    fn from(text: &'a str) -> Self {
 955        let mut len_utf16 = OffsetUtf16(0);
 956        let mut lines = Point::new(0, 0);
 957        let mut first_line_chars = 0;
 958        let mut last_line_chars = 0;
 959        let mut last_line_len_utf16 = 0;
 960        let mut longest_row = 0;
 961        let mut longest_row_chars = 0;
 962        for c in text.chars() {
 963            len_utf16.0 += c.len_utf16();
 964
 965            if c == '\n' {
 966                lines += Point::new(1, 0);
 967                last_line_len_utf16 = 0;
 968                last_line_chars = 0;
 969            } else {
 970                lines.column += c.len_utf8() as u32;
 971                last_line_len_utf16 += c.len_utf16() as u32;
 972                last_line_chars += 1;
 973            }
 974
 975            if lines.row == 0 {
 976                first_line_chars = last_line_chars;
 977            }
 978
 979            if last_line_chars > longest_row_chars {
 980                longest_row = lines.row;
 981                longest_row_chars = last_line_chars;
 982            }
 983        }
 984
 985        TextSummary {
 986            len: text.len(),
 987            len_utf16,
 988            lines,
 989            first_line_chars,
 990            last_line_chars,
 991            last_line_len_utf16,
 992            longest_row,
 993            longest_row_chars,
 994        }
 995    }
 996}
 997
 998impl sum_tree::Summary for TextSummary {
 999    type Context = ();
1000
1001    fn add_summary(&mut self, summary: &Self, _: &Self::Context) {
1002        *self += summary;
1003    }
1004}
1005
1006impl std::ops::Add<Self> for TextSummary {
1007    type Output = Self;
1008
1009    fn add(mut self, rhs: Self) -> Self::Output {
1010        AddAssign::add_assign(&mut self, &rhs);
1011        self
1012    }
1013}
1014
1015impl<'a> std::ops::AddAssign<&'a Self> for TextSummary {
1016    fn add_assign(&mut self, other: &'a Self) {
1017        let joined_chars = self.last_line_chars + other.first_line_chars;
1018        if joined_chars > self.longest_row_chars {
1019            self.longest_row = self.lines.row;
1020            self.longest_row_chars = joined_chars;
1021        }
1022        if other.longest_row_chars > self.longest_row_chars {
1023            self.longest_row = self.lines.row + other.longest_row;
1024            self.longest_row_chars = other.longest_row_chars;
1025        }
1026
1027        if self.lines.row == 0 {
1028            self.first_line_chars += other.first_line_chars;
1029        }
1030
1031        if other.lines.row == 0 {
1032            self.last_line_chars += other.first_line_chars;
1033            self.last_line_len_utf16 += other.last_line_len_utf16;
1034        } else {
1035            self.last_line_chars = other.last_line_chars;
1036            self.last_line_len_utf16 = other.last_line_len_utf16;
1037        }
1038
1039        self.len += other.len;
1040        self.len_utf16 += other.len_utf16;
1041        self.lines += other.lines;
1042    }
1043}
1044
1045impl std::ops::AddAssign<Self> for TextSummary {
1046    fn add_assign(&mut self, other: Self) {
1047        *self += &other;
1048    }
1049}
1050
1051pub trait TextDimension: 'static + for<'a> Dimension<'a, ChunkSummary> {
1052    fn from_text_summary(summary: &TextSummary) -> Self;
1053    fn add_assign(&mut self, other: &Self);
1054}
1055
1056impl<D1: TextDimension, D2: TextDimension> TextDimension for (D1, D2) {
1057    fn from_text_summary(summary: &TextSummary) -> Self {
1058        (
1059            D1::from_text_summary(summary),
1060            D2::from_text_summary(summary),
1061        )
1062    }
1063
1064    fn add_assign(&mut self, other: &Self) {
1065        self.0.add_assign(&other.0);
1066        self.1.add_assign(&other.1);
1067    }
1068}
1069
1070impl<'a> sum_tree::Dimension<'a, ChunkSummary> for TextSummary {
1071    fn add_summary(&mut self, summary: &'a ChunkSummary, _: &()) {
1072        *self += &summary.text;
1073    }
1074}
1075
1076impl TextDimension for TextSummary {
1077    fn from_text_summary(summary: &TextSummary) -> Self {
1078        summary.clone()
1079    }
1080
1081    fn add_assign(&mut self, other: &Self) {
1082        *self += other;
1083    }
1084}
1085
1086impl<'a> sum_tree::Dimension<'a, ChunkSummary> for usize {
1087    fn add_summary(&mut self, summary: &'a ChunkSummary, _: &()) {
1088        *self += summary.text.len;
1089    }
1090}
1091
1092impl TextDimension for usize {
1093    fn from_text_summary(summary: &TextSummary) -> Self {
1094        summary.len
1095    }
1096
1097    fn add_assign(&mut self, other: &Self) {
1098        *self += other;
1099    }
1100}
1101
1102impl<'a> sum_tree::Dimension<'a, ChunkSummary> for OffsetUtf16 {
1103    fn add_summary(&mut self, summary: &'a ChunkSummary, _: &()) {
1104        *self += summary.text.len_utf16;
1105    }
1106}
1107
1108impl TextDimension for OffsetUtf16 {
1109    fn from_text_summary(summary: &TextSummary) -> Self {
1110        summary.len_utf16
1111    }
1112
1113    fn add_assign(&mut self, other: &Self) {
1114        *self += other;
1115    }
1116}
1117
1118impl<'a> sum_tree::Dimension<'a, ChunkSummary> for Point {
1119    fn add_summary(&mut self, summary: &'a ChunkSummary, _: &()) {
1120        *self += summary.text.lines;
1121    }
1122}
1123
1124impl TextDimension for Point {
1125    fn from_text_summary(summary: &TextSummary) -> Self {
1126        summary.lines
1127    }
1128
1129    fn add_assign(&mut self, other: &Self) {
1130        *self += other;
1131    }
1132}
1133
1134impl<'a> sum_tree::Dimension<'a, ChunkSummary> for PointUtf16 {
1135    fn add_summary(&mut self, summary: &'a ChunkSummary, _: &()) {
1136        *self += summary.text.lines_utf16();
1137    }
1138}
1139
1140impl TextDimension for PointUtf16 {
1141    fn from_text_summary(summary: &TextSummary) -> Self {
1142        summary.lines_utf16()
1143    }
1144
1145    fn add_assign(&mut self, other: &Self) {
1146        *self += other;
1147    }
1148}
1149
1150fn find_split_ix(text: &str) -> usize {
1151    let mut ix = text.len() / 2;
1152    while !text.is_char_boundary(ix) {
1153        if ix < 2 * CHUNK_BASE {
1154            ix += 1;
1155        } else {
1156            ix = (text.len() / 2) - 1;
1157            break;
1158        }
1159    }
1160    while !text.is_char_boundary(ix) {
1161        ix -= 1;
1162    }
1163
1164    debug_assert!(ix <= 2 * CHUNK_BASE);
1165    debug_assert!(text.len() - ix <= 2 * CHUNK_BASE);
1166    ix
1167}
1168
1169#[cfg(test)]
1170mod tests {
1171    use super::*;
1172    use rand::prelude::*;
1173    use std::{cmp::Ordering, env, io::Read};
1174    use util::RandomCharIter;
1175    use Bias::{Left, Right};
1176
1177    #[test]
1178    fn test_all_4_byte_chars() {
1179        let mut rope = Rope::new();
1180        let text = "🏀".repeat(256);
1181        rope.push(&text);
1182        assert_eq!(rope.text(), text);
1183    }
1184
1185    #[test]
1186    fn test_clip() {
1187        let rope = Rope::from("🧘");
1188
1189        assert_eq!(rope.clip_offset(1, Bias::Left), 0);
1190        assert_eq!(rope.clip_offset(1, Bias::Right), 4);
1191        assert_eq!(rope.clip_offset(5, Bias::Right), 4);
1192
1193        assert_eq!(
1194            rope.clip_point(Point::new(0, 1), Bias::Left),
1195            Point::new(0, 0)
1196        );
1197        assert_eq!(
1198            rope.clip_point(Point::new(0, 1), Bias::Right),
1199            Point::new(0, 4)
1200        );
1201        assert_eq!(
1202            rope.clip_point(Point::new(0, 5), Bias::Right),
1203            Point::new(0, 4)
1204        );
1205
1206        assert_eq!(
1207            rope.clip_point_utf16(Unclipped(PointUtf16::new(0, 1)), Bias::Left),
1208            PointUtf16::new(0, 0)
1209        );
1210        assert_eq!(
1211            rope.clip_point_utf16(Unclipped(PointUtf16::new(0, 1)), Bias::Right),
1212            PointUtf16::new(0, 2)
1213        );
1214        assert_eq!(
1215            rope.clip_point_utf16(Unclipped(PointUtf16::new(0, 3)), Bias::Right),
1216            PointUtf16::new(0, 2)
1217        );
1218
1219        assert_eq!(
1220            rope.clip_offset_utf16(OffsetUtf16(1), Bias::Left),
1221            OffsetUtf16(0)
1222        );
1223        assert_eq!(
1224            rope.clip_offset_utf16(OffsetUtf16(1), Bias::Right),
1225            OffsetUtf16(2)
1226        );
1227        assert_eq!(
1228            rope.clip_offset_utf16(OffsetUtf16(3), Bias::Right),
1229            OffsetUtf16(2)
1230        );
1231    }
1232
1233    #[gpui::test(iterations = 100)]
1234    fn test_random_rope(mut rng: StdRng) {
1235        let operations = env::var("OPERATIONS")
1236            .map(|i| i.parse().expect("invalid `OPERATIONS` variable"))
1237            .unwrap_or(10);
1238
1239        let mut expected = String::new();
1240        let mut actual = Rope::new();
1241        for _ in 0..operations {
1242            let end_ix = clip_offset(&expected, rng.gen_range(0..=expected.len()), Right);
1243            let start_ix = clip_offset(&expected, rng.gen_range(0..=end_ix), Left);
1244            let len = rng.gen_range(0..=64);
1245            let new_text: String = RandomCharIter::new(&mut rng).take(len).collect();
1246
1247            let mut new_actual = Rope::new();
1248            let mut cursor = actual.cursor(0);
1249            new_actual.append(cursor.slice(start_ix));
1250            new_actual.push(&new_text);
1251            cursor.seek_forward(end_ix);
1252            new_actual.append(cursor.suffix());
1253            actual = new_actual;
1254
1255            expected.replace_range(start_ix..end_ix, &new_text);
1256
1257            assert_eq!(actual.text(), expected);
1258            log::info!("text: {:?}", expected);
1259
1260            for _ in 0..5 {
1261                let end_ix = clip_offset(&expected, rng.gen_range(0..=expected.len()), Right);
1262                let start_ix = clip_offset(&expected, rng.gen_range(0..=end_ix), Left);
1263
1264                let actual_text = actual.chunks_in_range(start_ix..end_ix).collect::<String>();
1265                assert_eq!(actual_text, &expected[start_ix..end_ix]);
1266
1267                let mut actual_text = String::new();
1268                actual
1269                    .bytes_in_range(start_ix..end_ix)
1270                    .read_to_string(&mut actual_text)
1271                    .unwrap();
1272                assert_eq!(actual_text, &expected[start_ix..end_ix]);
1273
1274                assert_eq!(
1275                    actual
1276                        .reversed_chunks_in_range(start_ix..end_ix)
1277                        .collect::<Vec<&str>>()
1278                        .into_iter()
1279                        .rev()
1280                        .collect::<String>(),
1281                    &expected[start_ix..end_ix]
1282                );
1283            }
1284
1285            let mut offset_utf16 = OffsetUtf16(0);
1286            let mut point = Point::new(0, 0);
1287            let mut point_utf16 = PointUtf16::new(0, 0);
1288            for (ix, ch) in expected.char_indices().chain(Some((expected.len(), '\0'))) {
1289                assert_eq!(actual.offset_to_point(ix), point, "offset_to_point({})", ix);
1290                assert_eq!(
1291                    actual.offset_to_point_utf16(ix),
1292                    point_utf16,
1293                    "offset_to_point_utf16({})",
1294                    ix
1295                );
1296                assert_eq!(
1297                    actual.point_to_offset(point),
1298                    ix,
1299                    "point_to_offset({:?})",
1300                    point
1301                );
1302                assert_eq!(
1303                    actual.point_utf16_to_offset(point_utf16),
1304                    ix,
1305                    "point_utf16_to_offset({:?})",
1306                    point_utf16
1307                );
1308                assert_eq!(
1309                    actual.offset_to_offset_utf16(ix),
1310                    offset_utf16,
1311                    "offset_to_offset_utf16({:?})",
1312                    ix
1313                );
1314                assert_eq!(
1315                    actual.offset_utf16_to_offset(offset_utf16),
1316                    ix,
1317                    "offset_utf16_to_offset({:?})",
1318                    offset_utf16
1319                );
1320                if ch == '\n' {
1321                    point += Point::new(1, 0);
1322                    point_utf16 += PointUtf16::new(1, 0);
1323                } else {
1324                    point.column += ch.len_utf8() as u32;
1325                    point_utf16.column += ch.len_utf16() as u32;
1326                }
1327                offset_utf16.0 += ch.len_utf16();
1328            }
1329
1330            let mut offset_utf16 = OffsetUtf16(0);
1331            let mut point_utf16 = Unclipped(PointUtf16::zero());
1332            for unit in expected.encode_utf16() {
1333                let left_offset = actual.clip_offset_utf16(offset_utf16, Bias::Left);
1334                let right_offset = actual.clip_offset_utf16(offset_utf16, Bias::Right);
1335                assert!(right_offset >= left_offset);
1336                // Ensure translating UTF-16 offsets to UTF-8 offsets doesn't panic.
1337                actual.offset_utf16_to_offset(left_offset);
1338                actual.offset_utf16_to_offset(right_offset);
1339
1340                let left_point = actual.clip_point_utf16(point_utf16, Bias::Left);
1341                let right_point = actual.clip_point_utf16(point_utf16, Bias::Right);
1342                assert!(right_point >= left_point);
1343                // Ensure translating valid UTF-16 points to offsets doesn't panic.
1344                actual.point_utf16_to_offset(left_point);
1345                actual.point_utf16_to_offset(right_point);
1346
1347                offset_utf16.0 += 1;
1348                if unit == b'\n' as u16 {
1349                    point_utf16.0 += PointUtf16::new(1, 0);
1350                } else {
1351                    point_utf16.0 += PointUtf16::new(0, 1);
1352                }
1353            }
1354
1355            for _ in 0..5 {
1356                let end_ix = clip_offset(&expected, rng.gen_range(0..=expected.len()), Right);
1357                let start_ix = clip_offset(&expected, rng.gen_range(0..=end_ix), Left);
1358                assert_eq!(
1359                    actual.cursor(start_ix).summary::<TextSummary>(end_ix),
1360                    TextSummary::from(&expected[start_ix..end_ix])
1361                );
1362            }
1363
1364            let mut expected_longest_rows = Vec::new();
1365            let mut longest_line_len = -1_isize;
1366            for (row, line) in expected.split('\n').enumerate() {
1367                let row = row as u32;
1368                assert_eq!(
1369                    actual.line_len(row),
1370                    line.len() as u32,
1371                    "invalid line len for row {}",
1372                    row
1373                );
1374
1375                let line_char_count = line.chars().count() as isize;
1376                match line_char_count.cmp(&longest_line_len) {
1377                    Ordering::Less => {}
1378                    Ordering::Equal => expected_longest_rows.push(row),
1379                    Ordering::Greater => {
1380                        longest_line_len = line_char_count;
1381                        expected_longest_rows.clear();
1382                        expected_longest_rows.push(row);
1383                    }
1384                }
1385            }
1386
1387            let longest_row = actual.summary().longest_row;
1388            assert!(
1389                expected_longest_rows.contains(&longest_row),
1390                "incorrect longest row {}. expected {:?} with length {}",
1391                longest_row,
1392                expected_longest_rows,
1393                longest_line_len,
1394            );
1395        }
1396    }
1397
1398    fn clip_offset(text: &str, mut offset: usize, bias: Bias) -> usize {
1399        while !text.is_char_boundary(offset) {
1400            match bias {
1401                Bias::Left => offset -= 1,
1402                Bias::Right => offset += 1,
1403            }
1404        }
1405        offset
1406    }
1407
1408    impl Rope {
1409        fn text(&self) -> String {
1410            let mut text = String::new();
1411            for chunk in self.chunks.cursor::<()>() {
1412                text.push_str(&chunk.0);
1413            }
1414            text
1415        }
1416    }
1417}