1use crate::PointUtf16;
   2
   3use super::Point;
   4use arrayvec::ArrayString;
   5use smallvec::SmallVec;
   6use std::{cmp, fmt, io, mem, ops::Range, str};
   7use sum_tree::{Bias, Dimension, SumTree};
   8
   9#[cfg(test)]
  10const CHUNK_BASE: usize = 6;
  11
  12#[cfg(not(test))]
  13const CHUNK_BASE: usize = 16;
  14
  15#[derive(Clone, Default, Debug)]
  16pub struct Rope {
  17    chunks: SumTree<Chunk>,
  18}
  19
  20impl Rope {
  21    pub fn new() -> Self {
  22        Self::default()
  23    }
  24
  25    pub fn append(&mut self, rope: Rope) {
  26        let mut chunks = rope.chunks.cursor::<()>();
  27        chunks.next(&());
  28        if let Some(chunk) = chunks.item() {
  29            if self.chunks.last().map_or(false, |c| c.0.len() < CHUNK_BASE)
  30                || chunk.0.len() < CHUNK_BASE
  31            {
  32                self.push(&chunk.0);
  33                chunks.next(&());
  34            }
  35        }
  36
  37        self.chunks.push_tree(chunks.suffix(&()), &());
  38        self.check_invariants();
  39    }
  40
  41    pub fn replace(&mut self, range: Range<usize>, text: &str) {
  42        let mut new_rope = Rope::new();
  43        let mut cursor = self.cursor(0);
  44        new_rope.append(cursor.slice(range.start));
  45        cursor.seek_forward(range.end);
  46        new_rope.push(text);
  47        new_rope.append(cursor.suffix());
  48        *self = new_rope;
  49    }
  50
  51    pub fn push(&mut self, text: &str) {
  52        let mut new_chunks = SmallVec::<[_; 16]>::new();
  53        let mut new_chunk = ArrayString::new();
  54        for ch in text.chars() {
  55            if new_chunk.len() + ch.len_utf8() > 2 * CHUNK_BASE {
  56                new_chunks.push(Chunk(new_chunk));
  57                new_chunk = ArrayString::new();
  58            }
  59            new_chunk.push(ch);
  60        }
  61        if !new_chunk.is_empty() {
  62            new_chunks.push(Chunk(new_chunk));
  63        }
  64
  65        let mut new_chunks = new_chunks.into_iter();
  66        let mut first_new_chunk = new_chunks.next();
  67        self.chunks.update_last(
  68            |last_chunk| {
  69                if let Some(first_new_chunk_ref) = first_new_chunk.as_mut() {
  70                    if last_chunk.0.len() + first_new_chunk_ref.0.len() <= 2 * CHUNK_BASE {
  71                        last_chunk.0.push_str(&first_new_chunk.take().unwrap().0);
  72                    } else {
  73                        let mut text = ArrayString::<{ 4 * CHUNK_BASE }>::new();
  74                        text.push_str(&last_chunk.0);
  75                        text.push_str(&first_new_chunk_ref.0);
  76                        let (left, right) = text.split_at(find_split_ix(&text));
  77                        last_chunk.0.clear();
  78                        last_chunk.0.push_str(left);
  79                        first_new_chunk_ref.0.clear();
  80                        first_new_chunk_ref.0.push_str(right);
  81                    }
  82                }
  83            },
  84            &(),
  85        );
  86
  87        self.chunks
  88            .extend(first_new_chunk.into_iter().chain(new_chunks), &());
  89        self.check_invariants();
  90    }
  91
  92    pub fn push_front(&mut self, text: &str) {
  93        let suffix = mem::replace(self, Rope::from(text));
  94        self.append(suffix);
  95    }
  96
  97    fn check_invariants(&self) {
  98        #[cfg(test)]
  99        {
 100            // Ensure all chunks except maybe the last one are not underflowing.
 101            // Allow some wiggle room for multibyte characters at chunk boundaries.
 102            let mut chunks = self.chunks.cursor::<()>().peekable();
 103            while let Some(chunk) = chunks.next() {
 104                if chunks.peek().is_some() {
 105                    assert!(chunk.0.len() + 3 >= CHUNK_BASE);
 106                }
 107            }
 108        }
 109    }
 110
 111    pub fn summary(&self) -> TextSummary {
 112        self.chunks.summary()
 113    }
 114
 115    pub fn len(&self) -> usize {
 116        self.chunks.extent(&())
 117    }
 118
 119    pub fn max_point(&self) -> Point {
 120        self.chunks.extent(&())
 121    }
 122
 123    pub fn cursor(&self, offset: usize) -> Cursor {
 124        Cursor::new(self, offset)
 125    }
 126
 127    pub fn chars(&self) -> impl Iterator<Item = char> + '_ {
 128        self.chars_at(0)
 129    }
 130
 131    pub fn chars_at(&self, start: usize) -> impl Iterator<Item = char> + '_ {
 132        self.chunks_in_range(start..self.len()).flat_map(str::chars)
 133    }
 134
 135    pub fn reversed_chars_at(&self, start: usize) -> impl Iterator<Item = char> + '_ {
 136        self.reversed_chunks_in_range(0..start)
 137            .flat_map(|chunk| chunk.chars().rev())
 138    }
 139
 140    pub fn bytes_in_range(&self, range: Range<usize>) -> Bytes {
 141        Bytes::new(self, range)
 142    }
 143
 144    pub fn chunks<'a>(&'a self) -> Chunks<'a> {
 145        self.chunks_in_range(0..self.len())
 146    }
 147
 148    pub fn chunks_in_range(&self, range: Range<usize>) -> Chunks {
 149        Chunks::new(self, range, false)
 150    }
 151
 152    pub fn reversed_chunks_in_range(&self, range: Range<usize>) -> Chunks {
 153        Chunks::new(self, range, true)
 154    }
 155
 156    pub fn offset_to_point(&self, offset: usize) -> Point {
 157        if offset >= self.summary().bytes {
 158            return self.summary().lines;
 159        }
 160        let mut cursor = self.chunks.cursor::<(usize, Point)>();
 161        cursor.seek(&offset, Bias::Left, &());
 162        let overshoot = offset - cursor.start().0;
 163        cursor.start().1
 164            + cursor
 165                .item()
 166                .map_or(Point::zero(), |chunk| chunk.offset_to_point(overshoot))
 167    }
 168
 169    pub fn offset_to_point_utf16(&self, offset: usize) -> PointUtf16 {
 170        if offset >= self.summary().bytes {
 171            return self.summary().lines_utf16;
 172        }
 173        let mut cursor = self.chunks.cursor::<(usize, PointUtf16)>();
 174        cursor.seek(&offset, Bias::Left, &());
 175        let overshoot = offset - cursor.start().0;
 176        cursor.start().1
 177            + cursor.item().map_or(PointUtf16::zero(), |chunk| {
 178                chunk.offset_to_point_utf16(overshoot)
 179            })
 180    }
 181
 182    pub fn point_to_offset(&self, point: Point) -> usize {
 183        if point >= self.summary().lines {
 184            return self.summary().bytes;
 185        }
 186        let mut cursor = self.chunks.cursor::<(Point, usize)>();
 187        cursor.seek(&point, Bias::Left, &());
 188        let overshoot = point - cursor.start().0;
 189        cursor.start().1
 190            + cursor
 191                .item()
 192                .map_or(0, |chunk| chunk.point_to_offset(overshoot))
 193    }
 194
 195    pub fn point_utf16_to_offset(&self, point: PointUtf16) -> usize {
 196        if point >= self.summary().lines_utf16 {
 197            return self.summary().bytes;
 198        }
 199        let mut cursor = self.chunks.cursor::<(PointUtf16, usize)>();
 200        cursor.seek(&point, Bias::Left, &());
 201        let overshoot = point - cursor.start().0;
 202        cursor.start().1
 203            + cursor
 204                .item()
 205                .map_or(0, |chunk| chunk.point_utf16_to_offset(overshoot))
 206    }
 207
 208    pub fn point_utf16_to_point(&self, point: PointUtf16) -> Point {
 209        if point >= self.summary().lines_utf16 {
 210            return self.summary().lines;
 211        }
 212        let mut cursor = self.chunks.cursor::<(PointUtf16, Point)>();
 213        cursor.seek(&point, Bias::Left, &());
 214        let overshoot = point - cursor.start().0;
 215        cursor.start().1
 216            + cursor
 217                .item()
 218                .map_or(Point::zero(), |chunk| chunk.point_utf16_to_point(overshoot))
 219    }
 220
 221    pub fn clip_offset(&self, mut offset: usize, bias: Bias) -> usize {
 222        let mut cursor = self.chunks.cursor::<usize>();
 223        cursor.seek(&offset, Bias::Left, &());
 224        if let Some(chunk) = cursor.item() {
 225            let mut ix = offset - cursor.start();
 226            while !chunk.0.is_char_boundary(ix) {
 227                match bias {
 228                    Bias::Left => {
 229                        ix -= 1;
 230                        offset -= 1;
 231                    }
 232                    Bias::Right => {
 233                        ix += 1;
 234                        offset += 1;
 235                    }
 236                }
 237            }
 238            offset
 239        } else {
 240            self.summary().bytes
 241        }
 242    }
 243
 244    pub fn clip_point(&self, point: Point, bias: Bias) -> Point {
 245        let mut cursor = self.chunks.cursor::<Point>();
 246        cursor.seek(&point, Bias::Right, &());
 247        if let Some(chunk) = cursor.item() {
 248            let overshoot = point - cursor.start();
 249            *cursor.start() + chunk.clip_point(overshoot, bias)
 250        } else {
 251            self.summary().lines
 252        }
 253    }
 254
 255    pub fn clip_point_utf16(&self, point: PointUtf16, bias: Bias) -> PointUtf16 {
 256        let mut cursor = self.chunks.cursor::<PointUtf16>();
 257        cursor.seek(&point, Bias::Right, &());
 258        if let Some(chunk) = cursor.item() {
 259            let overshoot = point - cursor.start();
 260            *cursor.start() + chunk.clip_point_utf16(overshoot, bias)
 261        } else {
 262            self.summary().lines_utf16
 263        }
 264    }
 265
 266    pub fn line_len(&self, row: u32) -> u32 {
 267        self.clip_point(Point::new(row, u32::MAX), Bias::Left)
 268            .column
 269    }
 270}
 271
 272impl<'a> From<&'a str> for Rope {
 273    fn from(text: &'a str) -> Self {
 274        let mut rope = Self::new();
 275        rope.push(text);
 276        rope
 277    }
 278}
 279
 280impl fmt::Display for Rope {
 281    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 282        for chunk in self.chunks() {
 283            write!(f, "{}", chunk)?;
 284        }
 285        Ok(())
 286    }
 287}
 288
 289pub struct Cursor<'a> {
 290    rope: &'a Rope,
 291    chunks: sum_tree::Cursor<'a, Chunk, usize>,
 292    offset: usize,
 293}
 294
 295impl<'a> Cursor<'a> {
 296    pub fn new(rope: &'a Rope, offset: usize) -> Self {
 297        let mut chunks = rope.chunks.cursor();
 298        chunks.seek(&offset, Bias::Right, &());
 299        Self {
 300            rope,
 301            chunks,
 302            offset,
 303        }
 304    }
 305
 306    pub fn seek_forward(&mut self, end_offset: usize) {
 307        debug_assert!(end_offset >= self.offset);
 308
 309        self.chunks.seek_forward(&end_offset, Bias::Right, &());
 310        self.offset = end_offset;
 311    }
 312
 313    pub fn slice(&mut self, end_offset: usize) -> Rope {
 314        debug_assert!(
 315            end_offset >= self.offset,
 316            "cannot slice backwards from {} to {}",
 317            self.offset,
 318            end_offset
 319        );
 320
 321        let mut slice = Rope::new();
 322        if let Some(start_chunk) = self.chunks.item() {
 323            let start_ix = self.offset - self.chunks.start();
 324            let end_ix = cmp::min(end_offset, self.chunks.end(&())) - self.chunks.start();
 325            slice.push(&start_chunk.0[start_ix..end_ix]);
 326        }
 327
 328        if end_offset > self.chunks.end(&()) {
 329            self.chunks.next(&());
 330            slice.append(Rope {
 331                chunks: self.chunks.slice(&end_offset, Bias::Right, &()),
 332            });
 333            if let Some(end_chunk) = self.chunks.item() {
 334                let end_ix = end_offset - self.chunks.start();
 335                slice.push(&end_chunk.0[..end_ix]);
 336            }
 337        }
 338
 339        self.offset = end_offset;
 340        slice
 341    }
 342
 343    pub fn summary<D: TextDimension>(&mut self, end_offset: usize) -> D {
 344        debug_assert!(end_offset >= self.offset);
 345
 346        let mut summary = D::default();
 347        if let Some(start_chunk) = self.chunks.item() {
 348            let start_ix = self.offset - self.chunks.start();
 349            let end_ix = cmp::min(end_offset, self.chunks.end(&())) - self.chunks.start();
 350            summary.add_assign(&D::from_text_summary(&TextSummary::from(
 351                &start_chunk.0[start_ix..end_ix],
 352            )));
 353        }
 354
 355        if end_offset > self.chunks.end(&()) {
 356            self.chunks.next(&());
 357            summary.add_assign(&self.chunks.summary(&end_offset, Bias::Right, &()));
 358            if let Some(end_chunk) = self.chunks.item() {
 359                let end_ix = end_offset - self.chunks.start();
 360                summary.add_assign(&D::from_text_summary(&TextSummary::from(
 361                    &end_chunk.0[..end_ix],
 362                )));
 363            }
 364        }
 365
 366        self.offset = end_offset;
 367        summary
 368    }
 369
 370    pub fn suffix(mut self) -> Rope {
 371        self.slice(self.rope.chunks.extent(&()))
 372    }
 373
 374    pub fn offset(&self) -> usize {
 375        self.offset
 376    }
 377}
 378
 379pub struct Chunks<'a> {
 380    chunks: sum_tree::Cursor<'a, Chunk, usize>,
 381    range: Range<usize>,
 382    reversed: bool,
 383}
 384
 385impl<'a> Chunks<'a> {
 386    pub fn new(rope: &'a Rope, range: Range<usize>, reversed: bool) -> Self {
 387        let mut chunks = rope.chunks.cursor();
 388        if reversed {
 389            chunks.seek(&range.end, Bias::Left, &());
 390        } else {
 391            chunks.seek(&range.start, Bias::Right, &());
 392        }
 393        Self {
 394            chunks,
 395            range,
 396            reversed,
 397        }
 398    }
 399
 400    pub fn offset(&self) -> usize {
 401        if self.reversed {
 402            self.range.end.min(self.chunks.end(&()))
 403        } else {
 404            self.range.start.max(*self.chunks.start())
 405        }
 406    }
 407
 408    pub fn seek(&mut self, offset: usize) {
 409        let bias = if self.reversed {
 410            Bias::Left
 411        } else {
 412            Bias::Right
 413        };
 414
 415        if offset >= self.chunks.end(&()) {
 416            self.chunks.seek_forward(&offset, bias, &());
 417        } else {
 418            self.chunks.seek(&offset, bias, &());
 419        }
 420
 421        if self.reversed {
 422            self.range.end = offset;
 423        } else {
 424            self.range.start = offset;
 425        }
 426    }
 427
 428    pub fn peek(&self) -> Option<&'a str> {
 429        let chunk = self.chunks.item()?;
 430        if self.reversed && self.range.start >= self.chunks.end(&()) {
 431            return None;
 432        }
 433        let chunk_start = *self.chunks.start();
 434        if self.range.end <= chunk_start {
 435            return None;
 436        }
 437
 438        let start = self.range.start.saturating_sub(chunk_start);
 439        let end = self.range.end - chunk_start;
 440        Some(&chunk.0[start..chunk.0.len().min(end)])
 441    }
 442}
 443
 444impl<'a> Iterator for Chunks<'a> {
 445    type Item = &'a str;
 446
 447    fn next(&mut self) -> Option<Self::Item> {
 448        let result = self.peek();
 449        if result.is_some() {
 450            if self.reversed {
 451                self.chunks.prev(&());
 452            } else {
 453                self.chunks.next(&());
 454            }
 455        }
 456        result
 457    }
 458}
 459
 460pub struct Bytes<'a> {
 461    chunks: sum_tree::Cursor<'a, Chunk, usize>,
 462    range: Range<usize>,
 463}
 464
 465impl<'a> Bytes<'a> {
 466    pub fn new(rope: &'a Rope, range: Range<usize>) -> Self {
 467        let mut chunks = rope.chunks.cursor();
 468        chunks.seek(&range.start, Bias::Right, &());
 469        Self { chunks, range }
 470    }
 471
 472    pub fn peek(&self) -> Option<&'a [u8]> {
 473        let chunk = self.chunks.item()?;
 474        let chunk_start = *self.chunks.start();
 475        if self.range.end <= chunk_start {
 476            return None;
 477        }
 478
 479        let start = self.range.start.saturating_sub(chunk_start);
 480        let end = self.range.end - chunk_start;
 481        Some(&chunk.0.as_bytes()[start..chunk.0.len().min(end)])
 482    }
 483}
 484
 485impl<'a> Iterator for Bytes<'a> {
 486    type Item = &'a [u8];
 487
 488    fn next(&mut self) -> Option<Self::Item> {
 489        let result = self.peek();
 490        if result.is_some() {
 491            self.chunks.next(&());
 492        }
 493        result
 494    }
 495}
 496
 497impl<'a> io::Read for Bytes<'a> {
 498    fn read(&mut self, buf: &mut [u8]) -> io::Result<usize> {
 499        if let Some(chunk) = self.peek() {
 500            let len = cmp::min(buf.len(), chunk.len());
 501            buf[..len].copy_from_slice(&chunk[..len]);
 502            self.range.start += len;
 503            if len == chunk.len() {
 504                self.chunks.next(&());
 505            }
 506            Ok(len)
 507        } else {
 508            Ok(0)
 509        }
 510    }
 511}
 512
 513#[derive(Clone, Debug, Default)]
 514struct Chunk(ArrayString<{ 2 * CHUNK_BASE }>);
 515
 516impl Chunk {
 517    fn offset_to_point(&self, target: usize) -> Point {
 518        let mut offset = 0;
 519        let mut point = Point::new(0, 0);
 520        for ch in self.0.chars() {
 521            if offset >= target {
 522                break;
 523            }
 524
 525            if ch == '\n' {
 526                point.row += 1;
 527                point.column = 0;
 528            } else {
 529                point.column += ch.len_utf8() as u32;
 530            }
 531            offset += ch.len_utf8();
 532        }
 533        point
 534    }
 535
 536    fn offset_to_point_utf16(&self, target: usize) -> PointUtf16 {
 537        let mut offset = 0;
 538        let mut point = PointUtf16::new(0, 0);
 539        for ch in self.0.chars() {
 540            if offset >= target {
 541                break;
 542            }
 543
 544            if ch == '\n' {
 545                point.row += 1;
 546                point.column = 0;
 547            } else {
 548                point.column += ch.len_utf16() as u32;
 549            }
 550            offset += ch.len_utf8();
 551        }
 552        point
 553    }
 554
 555    fn point_to_offset(&self, target: Point) -> usize {
 556        let mut offset = 0;
 557        let mut point = Point::new(0, 0);
 558        for ch in self.0.chars() {
 559            if point >= target {
 560                if point > target {
 561                    panic!("point {:?} is inside of character {:?}", target, ch);
 562                }
 563                break;
 564            }
 565
 566            if ch == '\n' {
 567                point.row += 1;
 568                if point.row > target.row {
 569                    panic!(
 570                        "point {:?} is beyond the end of a line with length {}",
 571                        target, point.column
 572                    );
 573                }
 574                point.column = 0;
 575            } else {
 576                point.column += ch.len_utf8() as u32;
 577            }
 578            offset += ch.len_utf8();
 579        }
 580        offset
 581    }
 582
 583    fn point_utf16_to_offset(&self, target: PointUtf16) -> usize {
 584        let mut offset = 0;
 585        let mut point = PointUtf16::new(0, 0);
 586        for ch in self.0.chars() {
 587            if point >= target {
 588                if point > target {
 589                    panic!("point {:?} is inside of character {:?}", target, ch);
 590                }
 591                break;
 592            }
 593
 594            if ch == '\n' {
 595                point.row += 1;
 596                if point.row > target.row {
 597                    panic!(
 598                        "point {:?} is beyond the end of a line with length {}",
 599                        target, point.column
 600                    );
 601                }
 602                point.column = 0;
 603            } else {
 604                point.column += ch.len_utf16() as u32;
 605            }
 606            offset += ch.len_utf8();
 607        }
 608        offset
 609    }
 610
 611    fn point_utf16_to_point(&self, target: PointUtf16) -> Point {
 612        let mut point = Point::zero();
 613        let mut point_utf16 = PointUtf16::zero();
 614        for ch in self.0.chars() {
 615            if point_utf16 >= target {
 616                if point_utf16 > target {
 617                    panic!("point {:?} is inside of character {:?}", target, ch);
 618                }
 619                break;
 620            }
 621
 622            if ch == '\n' {
 623                point_utf16 += PointUtf16::new(1, 0);
 624                point += Point::new(1, 0);
 625            } else {
 626                point_utf16 += PointUtf16::new(0, ch.len_utf16() as u32);
 627                point += Point::new(0, ch.len_utf8() as u32);
 628            }
 629        }
 630        point
 631    }
 632
 633    fn clip_point(&self, target: Point, bias: Bias) -> Point {
 634        for (row, line) in self.0.split('\n').enumerate() {
 635            if row == target.row as usize {
 636                let mut column = target.column.min(line.len() as u32);
 637                while !line.is_char_boundary(column as usize) {
 638                    match bias {
 639                        Bias::Left => column -= 1,
 640                        Bias::Right => column += 1,
 641                    }
 642                }
 643                return Point::new(row as u32, column);
 644            }
 645        }
 646        unreachable!()
 647    }
 648
 649    fn clip_point_utf16(&self, target: PointUtf16, bias: Bias) -> PointUtf16 {
 650        for (row, line) in self.0.split('\n').enumerate() {
 651            if row == target.row as usize {
 652                let mut code_units = line.encode_utf16();
 653                let mut column = code_units.by_ref().take(target.column as usize).count();
 654                if char::decode_utf16(code_units).next().transpose().is_err() {
 655                    match bias {
 656                        Bias::Left => column -= 1,
 657                        Bias::Right => column += 1,
 658                    }
 659                }
 660                return PointUtf16::new(row as u32, column as u32);
 661            }
 662        }
 663        unreachable!()
 664    }
 665}
 666
 667impl sum_tree::Item for Chunk {
 668    type Summary = TextSummary;
 669
 670    fn summary(&self) -> Self::Summary {
 671        TextSummary::from(self.0.as_str())
 672    }
 673}
 674
 675#[derive(Clone, Debug, Default, Eq, PartialEq)]
 676pub struct TextSummary {
 677    pub bytes: usize,
 678    pub lines: Point,
 679    pub lines_utf16: PointUtf16,
 680    pub first_line_chars: u32,
 681    pub last_line_chars: u32,
 682    pub longest_row: u32,
 683    pub longest_row_chars: u32,
 684}
 685
 686impl<'a> From<&'a str> for TextSummary {
 687    fn from(text: &'a str) -> Self {
 688        let mut lines = Point::new(0, 0);
 689        let mut lines_utf16 = PointUtf16::new(0, 0);
 690        let mut first_line_chars = 0;
 691        let mut last_line_chars = 0;
 692        let mut longest_row = 0;
 693        let mut longest_row_chars = 0;
 694        for c in text.chars() {
 695            if c == '\n' {
 696                lines += Point::new(1, 0);
 697                lines_utf16 += PointUtf16::new(1, 0);
 698                last_line_chars = 0;
 699            } else {
 700                lines.column += c.len_utf8() as u32;
 701                lines_utf16.column += c.len_utf16() as u32;
 702                last_line_chars += 1;
 703            }
 704
 705            if lines.row == 0 {
 706                first_line_chars = last_line_chars;
 707            }
 708
 709            if last_line_chars > longest_row_chars {
 710                longest_row = lines.row;
 711                longest_row_chars = last_line_chars;
 712            }
 713        }
 714
 715        TextSummary {
 716            bytes: text.len(),
 717            lines,
 718            lines_utf16,
 719            first_line_chars,
 720            last_line_chars,
 721            longest_row,
 722            longest_row_chars,
 723        }
 724    }
 725}
 726
 727impl sum_tree::Summary for TextSummary {
 728    type Context = ();
 729
 730    fn add_summary(&mut self, summary: &Self, _: &Self::Context) {
 731        *self += summary;
 732    }
 733}
 734
 735impl<'a> std::ops::Add<Self> for TextSummary {
 736    type Output = Self;
 737
 738    fn add(mut self, rhs: Self) -> Self::Output {
 739        self.add_assign(&rhs);
 740        self
 741    }
 742}
 743
 744impl<'a> std::ops::AddAssign<&'a Self> for TextSummary {
 745    fn add_assign(&mut self, other: &'a Self) {
 746        let joined_chars = self.last_line_chars + other.first_line_chars;
 747        if joined_chars > self.longest_row_chars {
 748            self.longest_row = self.lines.row;
 749            self.longest_row_chars = joined_chars;
 750        }
 751        if other.longest_row_chars > self.longest_row_chars {
 752            self.longest_row = self.lines.row + other.longest_row;
 753            self.longest_row_chars = other.longest_row_chars;
 754        }
 755
 756        if self.lines.row == 0 {
 757            self.first_line_chars += other.first_line_chars;
 758        }
 759
 760        if other.lines.row == 0 {
 761            self.last_line_chars += other.first_line_chars;
 762        } else {
 763            self.last_line_chars = other.last_line_chars;
 764        }
 765
 766        self.bytes += other.bytes;
 767        self.lines += other.lines;
 768        self.lines_utf16 += other.lines_utf16;
 769    }
 770}
 771
 772impl std::ops::AddAssign<Self> for TextSummary {
 773    fn add_assign(&mut self, other: Self) {
 774        *self += &other;
 775    }
 776}
 777
 778pub trait TextDimension: 'static + for<'a> Dimension<'a, TextSummary> {
 779    fn from_text_summary(summary: &TextSummary) -> Self;
 780    fn add_assign(&mut self, other: &Self);
 781}
 782
 783impl<'a, D1: TextDimension, D2: TextDimension> TextDimension for (D1, D2) {
 784    fn from_text_summary(summary: &TextSummary) -> Self {
 785        (
 786            D1::from_text_summary(summary),
 787            D2::from_text_summary(summary),
 788        )
 789    }
 790
 791    fn add_assign(&mut self, other: &Self) {
 792        self.0.add_assign(&other.0);
 793        self.1.add_assign(&other.1);
 794    }
 795}
 796
 797impl TextDimension for TextSummary {
 798    fn from_text_summary(summary: &TextSummary) -> Self {
 799        summary.clone()
 800    }
 801
 802    fn add_assign(&mut self, other: &Self) {
 803        *self += other;
 804    }
 805}
 806
 807impl<'a> sum_tree::Dimension<'a, TextSummary> for usize {
 808    fn add_summary(&mut self, summary: &'a TextSummary, _: &()) {
 809        *self += summary.bytes;
 810    }
 811}
 812
 813impl TextDimension for usize {
 814    fn from_text_summary(summary: &TextSummary) -> Self {
 815        summary.bytes
 816    }
 817
 818    fn add_assign(&mut self, other: &Self) {
 819        *self += other;
 820    }
 821}
 822
 823impl<'a> sum_tree::Dimension<'a, TextSummary> for Point {
 824    fn add_summary(&mut self, summary: &'a TextSummary, _: &()) {
 825        *self += summary.lines;
 826    }
 827}
 828
 829impl TextDimension for Point {
 830    fn from_text_summary(summary: &TextSummary) -> Self {
 831        summary.lines
 832    }
 833
 834    fn add_assign(&mut self, other: &Self) {
 835        *self += other;
 836    }
 837}
 838
 839impl<'a> sum_tree::Dimension<'a, TextSummary> for PointUtf16 {
 840    fn add_summary(&mut self, summary: &'a TextSummary, _: &()) {
 841        *self += summary.lines_utf16;
 842    }
 843}
 844
 845impl TextDimension for PointUtf16 {
 846    fn from_text_summary(summary: &TextSummary) -> Self {
 847        summary.lines_utf16
 848    }
 849
 850    fn add_assign(&mut self, other: &Self) {
 851        *self += other;
 852    }
 853}
 854
 855fn find_split_ix(text: &str) -> usize {
 856    let mut ix = text.len() / 2;
 857    while !text.is_char_boundary(ix) {
 858        if ix < 2 * CHUNK_BASE {
 859            ix += 1;
 860        } else {
 861            ix = (text.len() / 2) - 1;
 862            break;
 863        }
 864    }
 865    while !text.is_char_boundary(ix) {
 866        ix -= 1;
 867    }
 868
 869    debug_assert!(ix <= 2 * CHUNK_BASE);
 870    debug_assert!(text.len() - ix <= 2 * CHUNK_BASE);
 871    ix
 872}
 873
 874#[cfg(test)]
 875mod tests {
 876    use super::*;
 877    use crate::random_char_iter::RandomCharIter;
 878    use rand::prelude::*;
 879    use std::{cmp::Ordering, env, io::Read};
 880    use Bias::{Left, Right};
 881
 882    #[test]
 883    fn test_all_4_byte_chars() {
 884        let mut rope = Rope::new();
 885        let text = "🏀".repeat(256);
 886        rope.push(&text);
 887        assert_eq!(rope.text(), text);
 888    }
 889
 890    #[test]
 891    fn test_clip() {
 892        let rope = Rope::from("🧘");
 893
 894        assert_eq!(rope.clip_offset(1, Bias::Left), 0);
 895        assert_eq!(rope.clip_offset(1, Bias::Right), 4);
 896        assert_eq!(rope.clip_offset(5, Bias::Right), 4);
 897
 898        assert_eq!(
 899            rope.clip_point(Point::new(0, 1), Bias::Left),
 900            Point::new(0, 0)
 901        );
 902        assert_eq!(
 903            rope.clip_point(Point::new(0, 1), Bias::Right),
 904            Point::new(0, 4)
 905        );
 906        assert_eq!(
 907            rope.clip_point(Point::new(0, 5), Bias::Right),
 908            Point::new(0, 4)
 909        );
 910
 911        assert_eq!(
 912            rope.clip_point_utf16(PointUtf16::new(0, 1), Bias::Left),
 913            PointUtf16::new(0, 0)
 914        );
 915        assert_eq!(
 916            rope.clip_point_utf16(PointUtf16::new(0, 1), Bias::Right),
 917            PointUtf16::new(0, 2)
 918        );
 919        assert_eq!(
 920            rope.clip_point_utf16(PointUtf16::new(0, 3), Bias::Right),
 921            PointUtf16::new(0, 2)
 922        );
 923    }
 924
 925    #[gpui::test(iterations = 100)]
 926    fn test_random_rope(mut rng: StdRng) {
 927        let operations = env::var("OPERATIONS")
 928            .map(|i| i.parse().expect("invalid `OPERATIONS` variable"))
 929            .unwrap_or(10);
 930
 931        let mut expected = String::new();
 932        let mut actual = Rope::new();
 933        for _ in 0..operations {
 934            let end_ix = clip_offset(&expected, rng.gen_range(0..=expected.len()), Right);
 935            let start_ix = clip_offset(&expected, rng.gen_range(0..=end_ix), Left);
 936            let len = rng.gen_range(0..=64);
 937            let new_text: String = RandomCharIter::new(&mut rng).take(len).collect();
 938
 939            let mut new_actual = Rope::new();
 940            let mut cursor = actual.cursor(0);
 941            new_actual.append(cursor.slice(start_ix));
 942            new_actual.push(&new_text);
 943            cursor.seek_forward(end_ix);
 944            new_actual.append(cursor.suffix());
 945            actual = new_actual;
 946
 947            expected.replace_range(start_ix..end_ix, &new_text);
 948
 949            assert_eq!(actual.text(), expected);
 950            log::info!("text: {:?}", expected);
 951
 952            for _ in 0..5 {
 953                let end_ix = clip_offset(&expected, rng.gen_range(0..=expected.len()), Right);
 954                let start_ix = clip_offset(&expected, rng.gen_range(0..=end_ix), Left);
 955
 956                let actual_text = actual.chunks_in_range(start_ix..end_ix).collect::<String>();
 957                assert_eq!(actual_text, &expected[start_ix..end_ix]);
 958
 959                let mut actual_text = String::new();
 960                actual
 961                    .bytes_in_range(start_ix..end_ix)
 962                    .read_to_string(&mut actual_text)
 963                    .unwrap();
 964                assert_eq!(actual_text, &expected[start_ix..end_ix]);
 965
 966                assert_eq!(
 967                    actual
 968                        .reversed_chunks_in_range(start_ix..end_ix)
 969                        .collect::<Vec<&str>>()
 970                        .into_iter()
 971                        .rev()
 972                        .collect::<String>(),
 973                    &expected[start_ix..end_ix]
 974                );
 975            }
 976
 977            let mut point = Point::new(0, 0);
 978            let mut point_utf16 = PointUtf16::new(0, 0);
 979            for (ix, ch) in expected.char_indices().chain(Some((expected.len(), '\0'))) {
 980                assert_eq!(actual.offset_to_point(ix), point, "offset_to_point({})", ix);
 981                assert_eq!(
 982                    actual.offset_to_point_utf16(ix),
 983                    point_utf16,
 984                    "offset_to_point_utf16({})",
 985                    ix
 986                );
 987                assert_eq!(
 988                    actual.point_to_offset(point),
 989                    ix,
 990                    "point_to_offset({:?})",
 991                    point
 992                );
 993                assert_eq!(
 994                    actual.point_utf16_to_offset(point_utf16),
 995                    ix,
 996                    "point_utf16_to_offset({:?})",
 997                    point_utf16
 998                );
 999                if ch == '\n' {
1000                    point += Point::new(1, 0);
1001                    point_utf16 += PointUtf16::new(1, 0);
1002                } else {
1003                    point.column += ch.len_utf8() as u32;
1004                    point_utf16.column += ch.len_utf16() as u32;
1005                }
1006            }
1007
1008            let mut point_utf16 = PointUtf16::zero();
1009            for unit in expected.encode_utf16() {
1010                let left_point = actual.clip_point_utf16(point_utf16, Bias::Left);
1011                let right_point = actual.clip_point_utf16(point_utf16, Bias::Right);
1012                assert!(right_point >= left_point);
1013                // Ensure translating UTF-16 points to offsets doesn't panic.
1014                actual.point_utf16_to_offset(left_point);
1015                actual.point_utf16_to_offset(right_point);
1016
1017                if unit == b'\n' as u16 {
1018                    point_utf16 += PointUtf16::new(1, 0);
1019                } else {
1020                    point_utf16 += PointUtf16::new(0, 1);
1021                }
1022            }
1023
1024            for _ in 0..5 {
1025                let end_ix = clip_offset(&expected, rng.gen_range(0..=expected.len()), Right);
1026                let start_ix = clip_offset(&expected, rng.gen_range(0..=end_ix), Left);
1027                assert_eq!(
1028                    actual.cursor(start_ix).summary::<TextSummary>(end_ix),
1029                    TextSummary::from(&expected[start_ix..end_ix])
1030                );
1031            }
1032
1033            let mut expected_longest_rows = Vec::new();
1034            let mut longest_line_len = -1_isize;
1035            for (row, line) in expected.split('\n').enumerate() {
1036                let row = row as u32;
1037                assert_eq!(
1038                    actual.line_len(row),
1039                    line.len() as u32,
1040                    "invalid line len for row {}",
1041                    row
1042                );
1043
1044                let line_char_count = line.chars().count() as isize;
1045                match line_char_count.cmp(&longest_line_len) {
1046                    Ordering::Less => {}
1047                    Ordering::Equal => expected_longest_rows.push(row),
1048                    Ordering::Greater => {
1049                        longest_line_len = line_char_count;
1050                        expected_longest_rows.clear();
1051                        expected_longest_rows.push(row);
1052                    }
1053                }
1054            }
1055
1056            let longest_row = actual.summary().longest_row;
1057            assert!(
1058                expected_longest_rows.contains(&longest_row),
1059                "incorrect longest row {}. expected {:?} with length {}",
1060                longest_row,
1061                expected_longest_rows,
1062                longest_line_len,
1063            );
1064        }
1065    }
1066
1067    fn clip_offset(text: &str, mut offset: usize, bias: Bias) -> usize {
1068        while !text.is_char_boundary(offset) {
1069            match bias {
1070                Bias::Left => offset -= 1,
1071                Bias::Right => offset += 1,
1072            }
1073        }
1074        offset
1075    }
1076
1077    impl Rope {
1078        fn text(&self) -> String {
1079            let mut text = String::new();
1080            for chunk in self.chunks.cursor::<()>() {
1081                text.push_str(&chunk.0);
1082            }
1083            text
1084        }
1085    }
1086}