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