1use super::Point;
   2use crate::{OffsetUtf16, PointUtf16};
   3use arrayvec::ArrayString;
   4use bromberg_sl2::{DigestString, HashMatrix};
   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 slice(&self, range: Range<usize>) -> Rope {
  52        let mut cursor = self.cursor(0);
  53        cursor.seek_forward(range.start);
  54        cursor.slice(range.end)
  55    }
  56
  57    pub fn push(&mut self, text: &str) {
  58        let mut new_chunks = SmallVec::<[_; 16]>::new();
  59        let mut new_chunk = ArrayString::new();
  60        for ch in text.chars() {
  61            if new_chunk.len() + ch.len_utf8() > 2 * CHUNK_BASE {
  62                new_chunks.push(Chunk(new_chunk));
  63                new_chunk = ArrayString::new();
  64            }
  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_offset_utf16(&self, offset: usize) -> OffsetUtf16 {
 168        if offset >= self.summary().len {
 169            return self.summary().len_utf16;
 170        }
 171        let mut cursor = self.chunks.cursor::<(usize, OffsetUtf16)>();
 172        cursor.seek(&offset, Bias::Left, &());
 173        let overshoot = offset - cursor.start().0;
 174        cursor.start().1
 175            + cursor.item().map_or(Default::default(), |chunk| {
 176                chunk.offset_to_offset_utf16(overshoot)
 177            })
 178    }
 179
 180    pub fn offset_utf16_to_offset(&self, offset: OffsetUtf16) -> usize {
 181        if offset >= self.summary().len_utf16 {
 182            return self.summary().len;
 183        }
 184        let mut cursor = self.chunks.cursor::<(OffsetUtf16, usize)>();
 185        cursor.seek(&offset, Bias::Left, &());
 186        let overshoot = offset - cursor.start().0;
 187        cursor.start().1
 188            + cursor.item().map_or(Default::default(), |chunk| {
 189                chunk.offset_utf16_to_offset(overshoot)
 190            })
 191    }
 192
 193    pub fn offset_to_point(&self, offset: usize) -> Point {
 194        if offset >= self.summary().len {
 195            return self.summary().lines;
 196        }
 197        let mut cursor = self.chunks.cursor::<(usize, Point)>();
 198        cursor.seek(&offset, Bias::Left, &());
 199        let overshoot = offset - cursor.start().0;
 200        cursor.start().1
 201            + cursor
 202                .item()
 203                .map_or(Point::zero(), |chunk| chunk.offset_to_point(overshoot))
 204    }
 205
 206    pub fn offset_to_point_utf16(&self, offset: usize) -> PointUtf16 {
 207        if offset >= self.summary().len {
 208            return self.summary().lines_utf16;
 209        }
 210        let mut cursor = self.chunks.cursor::<(usize, PointUtf16)>();
 211        cursor.seek(&offset, Bias::Left, &());
 212        let overshoot = offset - cursor.start().0;
 213        cursor.start().1
 214            + cursor.item().map_or(PointUtf16::zero(), |chunk| {
 215                chunk.offset_to_point_utf16(overshoot)
 216            })
 217    }
 218
 219    pub fn point_to_point_utf16(&self, point: Point) -> PointUtf16 {
 220        if point >= self.summary().lines {
 221            return self.summary().lines_utf16;
 222        }
 223        let mut cursor = self.chunks.cursor::<(Point, PointUtf16)>();
 224        cursor.seek(&point, Bias::Left, &());
 225        let overshoot = point - cursor.start().0;
 226        cursor.start().1
 227            + cursor.item().map_or(PointUtf16::zero(), |chunk| {
 228                chunk.point_to_point_utf16(overshoot)
 229            })
 230    }
 231
 232    pub fn point_to_offset(&self, point: Point) -> usize {
 233        if point >= self.summary().lines {
 234            return self.summary().len;
 235        }
 236        let mut cursor = self.chunks.cursor::<(Point, usize)>();
 237        cursor.seek(&point, Bias::Left, &());
 238        let overshoot = point - cursor.start().0;
 239        cursor.start().1
 240            + cursor
 241                .item()
 242                .map_or(0, |chunk| chunk.point_to_offset(overshoot))
 243    }
 244
 245    pub fn point_utf16_to_offset(&self, point: PointUtf16) -> usize {
 246        if point >= self.summary().lines_utf16 {
 247            return self.summary().len;
 248        }
 249        let mut cursor = self.chunks.cursor::<(PointUtf16, usize)>();
 250        cursor.seek(&point, Bias::Left, &());
 251        let overshoot = point - cursor.start().0;
 252        cursor.start().1
 253            + cursor
 254                .item()
 255                .map_or(0, |chunk| chunk.point_utf16_to_offset(overshoot))
 256    }
 257
 258    pub fn point_utf16_to_point(&self, point: PointUtf16) -> Point {
 259        if point >= self.summary().lines_utf16 {
 260            return self.summary().lines;
 261        }
 262        let mut cursor = self.chunks.cursor::<(PointUtf16, Point)>();
 263        cursor.seek(&point, Bias::Left, &());
 264        let overshoot = point - cursor.start().0;
 265        cursor.start().1
 266            + cursor
 267                .item()
 268                .map_or(Point::zero(), |chunk| chunk.point_utf16_to_point(overshoot))
 269    }
 270
 271    pub fn clip_offset(&self, mut offset: usize, bias: Bias) -> usize {
 272        let mut cursor = self.chunks.cursor::<usize>();
 273        cursor.seek(&offset, Bias::Left, &());
 274        if let Some(chunk) = cursor.item() {
 275            let mut ix = offset - cursor.start();
 276            while !chunk.0.is_char_boundary(ix) {
 277                match bias {
 278                    Bias::Left => {
 279                        ix -= 1;
 280                        offset -= 1;
 281                    }
 282                    Bias::Right => {
 283                        ix += 1;
 284                        offset += 1;
 285                    }
 286                }
 287            }
 288            offset
 289        } else {
 290            self.summary().len
 291        }
 292    }
 293
 294    pub fn clip_offset_utf16(&self, offset: OffsetUtf16, bias: Bias) -> OffsetUtf16 {
 295        let mut cursor = self.chunks.cursor::<OffsetUtf16>();
 296        cursor.seek(&offset, Bias::Right, &());
 297        if let Some(chunk) = cursor.item() {
 298            let overshoot = offset - cursor.start();
 299            *cursor.start() + chunk.clip_offset_utf16(overshoot, bias)
 300        } else {
 301            self.summary().len_utf16
 302        }
 303    }
 304
 305    pub fn clip_point(&self, point: Point, bias: Bias) -> Point {
 306        let mut cursor = self.chunks.cursor::<Point>();
 307        cursor.seek(&point, Bias::Right, &());
 308        if let Some(chunk) = cursor.item() {
 309            let overshoot = point - cursor.start();
 310            *cursor.start() + chunk.clip_point(overshoot, bias)
 311        } else {
 312            self.summary().lines
 313        }
 314    }
 315
 316    pub fn clip_point_utf16(&self, point: PointUtf16, bias: Bias) -> PointUtf16 {
 317        let mut cursor = self.chunks.cursor::<PointUtf16>();
 318        cursor.seek(&point, Bias::Right, &());
 319        if let Some(chunk) = cursor.item() {
 320            let overshoot = point - cursor.start();
 321            *cursor.start() + chunk.clip_point_utf16(overshoot, bias)
 322        } else {
 323            self.summary().lines_utf16
 324        }
 325    }
 326
 327    pub fn line_len(&self, row: u32) -> u32 {
 328        self.clip_point(Point::new(row, u32::MAX), Bias::Left)
 329            .column
 330    }
 331
 332    pub fn fingerprint(&self) -> String {
 333        self.chunks.summary().fingerprint.to_hex()
 334    }
 335}
 336
 337impl<'a> From<&'a str> for Rope {
 338    fn from(text: &'a str) -> Self {
 339        let mut rope = Self::new();
 340        rope.push(text);
 341        rope
 342    }
 343}
 344
 345impl fmt::Display for Rope {
 346    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 347        for chunk in self.chunks() {
 348            write!(f, "{}", chunk)?;
 349        }
 350        Ok(())
 351    }
 352}
 353
 354pub struct Cursor<'a> {
 355    rope: &'a Rope,
 356    chunks: sum_tree::Cursor<'a, Chunk, usize>,
 357    offset: usize,
 358}
 359
 360impl<'a> Cursor<'a> {
 361    pub fn new(rope: &'a Rope, offset: usize) -> Self {
 362        let mut chunks = rope.chunks.cursor();
 363        chunks.seek(&offset, Bias::Right, &());
 364        Self {
 365            rope,
 366            chunks,
 367            offset,
 368        }
 369    }
 370
 371    pub fn seek_forward(&mut self, end_offset: usize) {
 372        debug_assert!(end_offset >= self.offset);
 373
 374        self.chunks.seek_forward(&end_offset, Bias::Right, &());
 375        self.offset = end_offset;
 376    }
 377
 378    pub fn slice(&mut self, end_offset: usize) -> Rope {
 379        debug_assert!(
 380            end_offset >= self.offset,
 381            "cannot slice backwards from {} to {}",
 382            self.offset,
 383            end_offset
 384        );
 385
 386        let mut slice = Rope::new();
 387        if let Some(start_chunk) = self.chunks.item() {
 388            let start_ix = self.offset - self.chunks.start();
 389            let end_ix = cmp::min(end_offset, self.chunks.end(&())) - self.chunks.start();
 390            slice.push(&start_chunk.0[start_ix..end_ix]);
 391        }
 392
 393        if end_offset > self.chunks.end(&()) {
 394            self.chunks.next(&());
 395            slice.append(Rope {
 396                chunks: self.chunks.slice(&end_offset, Bias::Right, &()),
 397            });
 398            if let Some(end_chunk) = self.chunks.item() {
 399                let end_ix = end_offset - self.chunks.start();
 400                slice.push(&end_chunk.0[..end_ix]);
 401            }
 402        }
 403
 404        self.offset = end_offset;
 405        slice
 406    }
 407
 408    pub fn summary<D: TextDimension>(&mut self, end_offset: usize) -> D {
 409        debug_assert!(end_offset >= self.offset);
 410
 411        let mut summary = D::default();
 412        if let Some(start_chunk) = self.chunks.item() {
 413            let start_ix = self.offset - self.chunks.start();
 414            let end_ix = cmp::min(end_offset, self.chunks.end(&())) - self.chunks.start();
 415            summary.add_assign(&D::from_text_summary(&TextSummary::from(
 416                &start_chunk.0[start_ix..end_ix],
 417            )));
 418        }
 419
 420        if end_offset > self.chunks.end(&()) {
 421            self.chunks.next(&());
 422            summary.add_assign(&self.chunks.summary(&end_offset, Bias::Right, &()));
 423            if let Some(end_chunk) = self.chunks.item() {
 424                let end_ix = end_offset - self.chunks.start();
 425                summary.add_assign(&D::from_text_summary(&TextSummary::from(
 426                    &end_chunk.0[..end_ix],
 427                )));
 428            }
 429        }
 430
 431        self.offset = end_offset;
 432        summary
 433    }
 434
 435    pub fn suffix(mut self) -> Rope {
 436        self.slice(self.rope.chunks.extent(&()))
 437    }
 438
 439    pub fn offset(&self) -> usize {
 440        self.offset
 441    }
 442}
 443
 444pub struct Chunks<'a> {
 445    chunks: sum_tree::Cursor<'a, Chunk, usize>,
 446    range: Range<usize>,
 447    reversed: bool,
 448}
 449
 450impl<'a> Chunks<'a> {
 451    pub fn new(rope: &'a Rope, range: Range<usize>, reversed: bool) -> Self {
 452        let mut chunks = rope.chunks.cursor();
 453        if reversed {
 454            chunks.seek(&range.end, Bias::Left, &());
 455        } else {
 456            chunks.seek(&range.start, Bias::Right, &());
 457        }
 458        Self {
 459            chunks,
 460            range,
 461            reversed,
 462        }
 463    }
 464
 465    pub fn offset(&self) -> usize {
 466        if self.reversed {
 467            self.range.end.min(self.chunks.end(&()))
 468        } else {
 469            self.range.start.max(*self.chunks.start())
 470        }
 471    }
 472
 473    pub fn seek(&mut self, offset: usize) {
 474        let bias = if self.reversed {
 475            Bias::Left
 476        } else {
 477            Bias::Right
 478        };
 479
 480        if offset >= self.chunks.end(&()) {
 481            self.chunks.seek_forward(&offset, bias, &());
 482        } else {
 483            self.chunks.seek(&offset, bias, &());
 484        }
 485
 486        if self.reversed {
 487            self.range.end = offset;
 488        } else {
 489            self.range.start = offset;
 490        }
 491    }
 492
 493    pub fn peek(&self) -> Option<&'a str> {
 494        let chunk = self.chunks.item()?;
 495        if self.reversed && self.range.start >= self.chunks.end(&()) {
 496            return None;
 497        }
 498        let chunk_start = *self.chunks.start();
 499        if self.range.end <= chunk_start {
 500            return None;
 501        }
 502
 503        let start = self.range.start.saturating_sub(chunk_start);
 504        let end = self.range.end - chunk_start;
 505        Some(&chunk.0[start..chunk.0.len().min(end)])
 506    }
 507}
 508
 509impl<'a> Iterator for Chunks<'a> {
 510    type Item = &'a str;
 511
 512    fn next(&mut self) -> Option<Self::Item> {
 513        let result = self.peek();
 514        if result.is_some() {
 515            if self.reversed {
 516                self.chunks.prev(&());
 517            } else {
 518                self.chunks.next(&());
 519            }
 520        }
 521        result
 522    }
 523}
 524
 525pub struct Bytes<'a> {
 526    chunks: sum_tree::Cursor<'a, Chunk, usize>,
 527    range: Range<usize>,
 528}
 529
 530impl<'a> Bytes<'a> {
 531    pub fn new(rope: &'a Rope, range: Range<usize>) -> Self {
 532        let mut chunks = rope.chunks.cursor();
 533        chunks.seek(&range.start, Bias::Right, &());
 534        Self { chunks, range }
 535    }
 536
 537    pub fn peek(&self) -> Option<&'a [u8]> {
 538        let chunk = self.chunks.item()?;
 539        let chunk_start = *self.chunks.start();
 540        if self.range.end <= chunk_start {
 541            return None;
 542        }
 543
 544        let start = self.range.start.saturating_sub(chunk_start);
 545        let end = self.range.end - chunk_start;
 546        Some(&chunk.0.as_bytes()[start..chunk.0.len().min(end)])
 547    }
 548}
 549
 550impl<'a> Iterator for Bytes<'a> {
 551    type Item = &'a [u8];
 552
 553    fn next(&mut self) -> Option<Self::Item> {
 554        let result = self.peek();
 555        if result.is_some() {
 556            self.chunks.next(&());
 557        }
 558        result
 559    }
 560}
 561
 562impl<'a> io::Read for Bytes<'a> {
 563    fn read(&mut self, buf: &mut [u8]) -> io::Result<usize> {
 564        if let Some(chunk) = self.peek() {
 565            let len = cmp::min(buf.len(), chunk.len());
 566            buf[..len].copy_from_slice(&chunk[..len]);
 567            self.range.start += len;
 568            if len == chunk.len() {
 569                self.chunks.next(&());
 570            }
 571            Ok(len)
 572        } else {
 573            Ok(0)
 574        }
 575    }
 576}
 577
 578#[derive(Clone, Debug, Default)]
 579struct Chunk(ArrayString<{ 2 * CHUNK_BASE }>);
 580
 581impl Chunk {
 582    fn offset_to_offset_utf16(&self, target: usize) -> OffsetUtf16 {
 583        let mut offset = 0;
 584        let mut offset_utf16 = OffsetUtf16(0);
 585        for ch in self.0.chars() {
 586            if offset >= target {
 587                break;
 588            }
 589
 590            offset += ch.len_utf8();
 591            offset_utf16.0 += ch.len_utf16();
 592        }
 593        offset_utf16
 594    }
 595
 596    fn offset_utf16_to_offset(&self, target: OffsetUtf16) -> usize {
 597        let mut offset_utf16 = OffsetUtf16(0);
 598        let mut offset = 0;
 599        for ch in self.0.chars() {
 600            if offset_utf16 >= target {
 601                break;
 602            }
 603
 604            offset += ch.len_utf8();
 605            offset_utf16.0 += ch.len_utf16();
 606        }
 607        offset
 608    }
 609
 610    fn offset_to_point(&self, target: usize) -> Point {
 611        let mut offset = 0;
 612        let mut point = Point::new(0, 0);
 613        for ch in self.0.chars() {
 614            if offset >= target {
 615                break;
 616            }
 617
 618            if ch == '\n' {
 619                point.row += 1;
 620                point.column = 0;
 621            } else {
 622                point.column += ch.len_utf8() as u32;
 623            }
 624            offset += ch.len_utf8();
 625        }
 626        point
 627    }
 628
 629    fn offset_to_point_utf16(&self, target: usize) -> PointUtf16 {
 630        let mut offset = 0;
 631        let mut point = PointUtf16::new(0, 0);
 632        for ch in self.0.chars() {
 633            if offset >= target {
 634                break;
 635            }
 636
 637            if ch == '\n' {
 638                point.row += 1;
 639                point.column = 0;
 640            } else {
 641                point.column += ch.len_utf16() as u32;
 642            }
 643            offset += ch.len_utf8();
 644        }
 645        point
 646    }
 647
 648    fn point_to_offset(&self, target: Point) -> usize {
 649        let mut offset = 0;
 650        let mut point = Point::new(0, 0);
 651        for ch in self.0.chars() {
 652            if point >= target {
 653                if point > target {
 654                    panic!("point {:?} is inside of character {:?}", target, ch);
 655                }
 656                break;
 657            }
 658
 659            if ch == '\n' {
 660                point.row += 1;
 661                if point.row > target.row {
 662                    panic!(
 663                        "point {:?} is beyond the end of a line with length {}",
 664                        target, point.column
 665                    );
 666                }
 667                point.column = 0;
 668            } else {
 669                point.column += ch.len_utf8() as u32;
 670            }
 671            offset += ch.len_utf8();
 672        }
 673        offset
 674    }
 675
 676    fn point_to_point_utf16(&self, target: Point) -> PointUtf16 {
 677        let mut point = Point::zero();
 678        let mut point_utf16 = PointUtf16::new(0, 0);
 679        for ch in self.0.chars() {
 680            if point >= target {
 681                break;
 682            }
 683
 684            if ch == '\n' {
 685                point_utf16.row += 1;
 686                point_utf16.column = 0;
 687                point.row += 1;
 688                point.column = 0;
 689            } else {
 690                point_utf16.column += ch.len_utf16() as u32;
 691                point.column += ch.len_utf8() as u32;
 692            }
 693        }
 694        point_utf16
 695    }
 696
 697    fn point_utf16_to_offset(&self, target: PointUtf16) -> usize {
 698        let mut offset = 0;
 699        let mut point = PointUtf16::new(0, 0);
 700        for ch in self.0.chars() {
 701            if point >= target {
 702                if point > target {
 703                    panic!("point {:?} is inside of character {:?}", target, ch);
 704                }
 705                break;
 706            }
 707
 708            if ch == '\n' {
 709                point.row += 1;
 710                if point.row > target.row {
 711                    panic!(
 712                        "point {:?} is beyond the end of a line with length {}",
 713                        target, point.column
 714                    );
 715                }
 716                point.column = 0;
 717            } else {
 718                point.column += ch.len_utf16() as u32;
 719            }
 720            offset += ch.len_utf8();
 721        }
 722        offset
 723    }
 724
 725    fn point_utf16_to_point(&self, target: PointUtf16) -> Point {
 726        let mut point = Point::zero();
 727        let mut point_utf16 = PointUtf16::zero();
 728        for ch in self.0.chars() {
 729            if point_utf16 >= target {
 730                if point_utf16 > target {
 731                    panic!("point {:?} is inside of character {:?}", target, ch);
 732                }
 733                break;
 734            }
 735
 736            if ch == '\n' {
 737                point_utf16 += PointUtf16::new(1, 0);
 738                point += Point::new(1, 0);
 739            } else {
 740                point_utf16 += PointUtf16::new(0, ch.len_utf16() as u32);
 741                point += Point::new(0, ch.len_utf8() as u32);
 742            }
 743        }
 744        point
 745    }
 746
 747    fn clip_point(&self, target: Point, bias: Bias) -> Point {
 748        for (row, line) in self.0.split('\n').enumerate() {
 749            if row == target.row as usize {
 750                let mut column = target.column.min(line.len() as u32);
 751                while !line.is_char_boundary(column as usize) {
 752                    match bias {
 753                        Bias::Left => column -= 1,
 754                        Bias::Right => column += 1,
 755                    }
 756                }
 757                return Point::new(row as u32, column);
 758            }
 759        }
 760        unreachable!()
 761    }
 762
 763    fn clip_point_utf16(&self, target: PointUtf16, bias: Bias) -> PointUtf16 {
 764        for (row, line) in self.0.split('\n').enumerate() {
 765            if row == target.row as usize {
 766                let mut code_units = line.encode_utf16();
 767                let mut column = code_units.by_ref().take(target.column as usize).count();
 768                if char::decode_utf16(code_units).next().transpose().is_err() {
 769                    match bias {
 770                        Bias::Left => column -= 1,
 771                        Bias::Right => column += 1,
 772                    }
 773                }
 774                return PointUtf16::new(row as u32, column as u32);
 775            }
 776        }
 777        unreachable!()
 778    }
 779
 780    fn clip_offset_utf16(&self, target: OffsetUtf16, bias: Bias) -> OffsetUtf16 {
 781        let mut code_units = self.0.encode_utf16();
 782        let mut offset = code_units.by_ref().take(target.0 as usize).count();
 783        if char::decode_utf16(code_units).next().transpose().is_err() {
 784            match bias {
 785                Bias::Left => offset -= 1,
 786                Bias::Right => offset += 1,
 787            }
 788        }
 789        OffsetUtf16(offset)
 790    }
 791}
 792
 793impl sum_tree::Item for Chunk {
 794    type Summary = ChunkSummary;
 795
 796    fn summary(&self) -> Self::Summary {
 797        ChunkSummary::from(self.0.as_str())
 798    }
 799}
 800
 801#[derive(Clone, Debug, Default, Eq, PartialEq)]
 802pub struct ChunkSummary {
 803    text: TextSummary,
 804    fingerprint: HashMatrix,
 805}
 806
 807impl<'a> From<&'a str> for ChunkSummary {
 808    fn from(text: &'a str) -> Self {
 809        Self {
 810            text: TextSummary::from(text),
 811            fingerprint: bromberg_sl2::hash_strict(text.as_bytes()),
 812        }
 813    }
 814}
 815
 816impl sum_tree::Summary for ChunkSummary {
 817    type Context = ();
 818
 819    fn add_summary(&mut self, summary: &Self, _: &()) {
 820        self.text += &summary.text;
 821        self.fingerprint = self.fingerprint * summary.fingerprint;
 822    }
 823}
 824
 825#[derive(Clone, Debug, Default, Eq, PartialEq)]
 826pub struct TextSummary {
 827    pub len: usize,
 828    pub len_utf16: OffsetUtf16,
 829    pub lines: Point,
 830    pub lines_utf16: PointUtf16,
 831    pub first_line_chars: u32,
 832    pub last_line_chars: u32,
 833    pub longest_row: u32,
 834    pub longest_row_chars: u32,
 835}
 836
 837impl<'a> From<&'a str> for TextSummary {
 838    fn from(text: &'a str) -> Self {
 839        let mut len_utf16 = OffsetUtf16(0);
 840        let mut lines = Point::new(0, 0);
 841        let mut lines_utf16 = PointUtf16::new(0, 0);
 842        let mut first_line_chars = 0;
 843        let mut last_line_chars = 0;
 844        let mut longest_row = 0;
 845        let mut longest_row_chars = 0;
 846        for c in text.chars() {
 847            len_utf16.0 += c.len_utf16();
 848
 849            if c == '\n' {
 850                lines += Point::new(1, 0);
 851                lines_utf16 += PointUtf16::new(1, 0);
 852                last_line_chars = 0;
 853            } else {
 854                lines.column += c.len_utf8() as u32;
 855                lines_utf16.column += c.len_utf16() as u32;
 856                last_line_chars += 1;
 857            }
 858
 859            if lines.row == 0 {
 860                first_line_chars = last_line_chars;
 861            }
 862
 863            if last_line_chars > longest_row_chars {
 864                longest_row = lines.row;
 865                longest_row_chars = last_line_chars;
 866            }
 867        }
 868
 869        TextSummary {
 870            len: text.len(),
 871            len_utf16,
 872            lines,
 873            lines_utf16,
 874            first_line_chars,
 875            last_line_chars,
 876            longest_row,
 877            longest_row_chars,
 878        }
 879    }
 880}
 881
 882impl sum_tree::Summary for TextSummary {
 883    type Context = ();
 884
 885    fn add_summary(&mut self, summary: &Self, _: &Self::Context) {
 886        *self += summary;
 887    }
 888}
 889
 890impl<'a> std::ops::Add<Self> for TextSummary {
 891    type Output = Self;
 892
 893    fn add(mut self, rhs: Self) -> Self::Output {
 894        self.add_assign(&rhs);
 895        self
 896    }
 897}
 898
 899impl<'a> std::ops::AddAssign<&'a Self> for TextSummary {
 900    fn add_assign(&mut self, other: &'a Self) {
 901        let joined_chars = self.last_line_chars + other.first_line_chars;
 902        if joined_chars > self.longest_row_chars {
 903            self.longest_row = self.lines.row;
 904            self.longest_row_chars = joined_chars;
 905        }
 906        if other.longest_row_chars > self.longest_row_chars {
 907            self.longest_row = self.lines.row + other.longest_row;
 908            self.longest_row_chars = other.longest_row_chars;
 909        }
 910
 911        if self.lines.row == 0 {
 912            self.first_line_chars += other.first_line_chars;
 913        }
 914
 915        if other.lines.row == 0 {
 916            self.last_line_chars += other.first_line_chars;
 917        } else {
 918            self.last_line_chars = other.last_line_chars;
 919        }
 920
 921        self.len += other.len;
 922        self.len_utf16 += other.len_utf16;
 923        self.lines += other.lines;
 924        self.lines_utf16 += other.lines_utf16;
 925    }
 926}
 927
 928impl std::ops::AddAssign<Self> for TextSummary {
 929    fn add_assign(&mut self, other: Self) {
 930        *self += &other;
 931    }
 932}
 933
 934pub trait TextDimension: 'static + for<'a> Dimension<'a, ChunkSummary> {
 935    fn from_text_summary(summary: &TextSummary) -> Self;
 936    fn add_assign(&mut self, other: &Self);
 937}
 938
 939impl<'a, D1: TextDimension, D2: TextDimension> TextDimension for (D1, D2) {
 940    fn from_text_summary(summary: &TextSummary) -> Self {
 941        (
 942            D1::from_text_summary(summary),
 943            D2::from_text_summary(summary),
 944        )
 945    }
 946
 947    fn add_assign(&mut self, other: &Self) {
 948        self.0.add_assign(&other.0);
 949        self.1.add_assign(&other.1);
 950    }
 951}
 952
 953impl<'a> sum_tree::Dimension<'a, ChunkSummary> for TextSummary {
 954    fn add_summary(&mut self, summary: &'a ChunkSummary, _: &()) {
 955        *self += &summary.text;
 956    }
 957}
 958
 959impl TextDimension for TextSummary {
 960    fn from_text_summary(summary: &TextSummary) -> Self {
 961        summary.clone()
 962    }
 963
 964    fn add_assign(&mut self, other: &Self) {
 965        *self += other;
 966    }
 967}
 968
 969impl<'a> sum_tree::Dimension<'a, ChunkSummary> for usize {
 970    fn add_summary(&mut self, summary: &'a ChunkSummary, _: &()) {
 971        *self += summary.text.len;
 972    }
 973}
 974
 975impl TextDimension for usize {
 976    fn from_text_summary(summary: &TextSummary) -> Self {
 977        summary.len
 978    }
 979
 980    fn add_assign(&mut self, other: &Self) {
 981        *self += other;
 982    }
 983}
 984
 985impl<'a> sum_tree::Dimension<'a, ChunkSummary> for OffsetUtf16 {
 986    fn add_summary(&mut self, summary: &'a ChunkSummary, _: &()) {
 987        *self += summary.text.len_utf16;
 988    }
 989}
 990
 991impl TextDimension for OffsetUtf16 {
 992    fn from_text_summary(summary: &TextSummary) -> Self {
 993        summary.len_utf16
 994    }
 995
 996    fn add_assign(&mut self, other: &Self) {
 997        *self += other;
 998    }
 999}
1000
1001impl<'a> sum_tree::Dimension<'a, ChunkSummary> for Point {
1002    fn add_summary(&mut self, summary: &'a ChunkSummary, _: &()) {
1003        *self += summary.text.lines;
1004    }
1005}
1006
1007impl TextDimension for Point {
1008    fn from_text_summary(summary: &TextSummary) -> Self {
1009        summary.lines
1010    }
1011
1012    fn add_assign(&mut self, other: &Self) {
1013        *self += other;
1014    }
1015}
1016
1017impl<'a> sum_tree::Dimension<'a, ChunkSummary> for PointUtf16 {
1018    fn add_summary(&mut self, summary: &'a ChunkSummary, _: &()) {
1019        *self += summary.text.lines_utf16;
1020    }
1021}
1022
1023impl TextDimension for PointUtf16 {
1024    fn from_text_summary(summary: &TextSummary) -> Self {
1025        summary.lines_utf16
1026    }
1027
1028    fn add_assign(&mut self, other: &Self) {
1029        *self += other;
1030    }
1031}
1032
1033fn find_split_ix(text: &str) -> usize {
1034    let mut ix = text.len() / 2;
1035    while !text.is_char_boundary(ix) {
1036        if ix < 2 * CHUNK_BASE {
1037            ix += 1;
1038        } else {
1039            ix = (text.len() / 2) - 1;
1040            break;
1041        }
1042    }
1043    while !text.is_char_boundary(ix) {
1044        ix -= 1;
1045    }
1046
1047    debug_assert!(ix <= 2 * CHUNK_BASE);
1048    debug_assert!(text.len() - ix <= 2 * CHUNK_BASE);
1049    ix
1050}
1051
1052#[cfg(test)]
1053mod tests {
1054    use super::*;
1055    use crate::random_char_iter::RandomCharIter;
1056    use rand::prelude::*;
1057    use std::{cmp::Ordering, env, io::Read};
1058    use Bias::{Left, Right};
1059
1060    #[test]
1061    fn test_all_4_byte_chars() {
1062        let mut rope = Rope::new();
1063        let text = "🏀".repeat(256);
1064        rope.push(&text);
1065        assert_eq!(rope.text(), text);
1066    }
1067
1068    #[test]
1069    fn test_clip() {
1070        let rope = Rope::from("🧘");
1071
1072        assert_eq!(rope.clip_offset(1, Bias::Left), 0);
1073        assert_eq!(rope.clip_offset(1, Bias::Right), 4);
1074        assert_eq!(rope.clip_offset(5, Bias::Right), 4);
1075
1076        assert_eq!(
1077            rope.clip_point(Point::new(0, 1), Bias::Left),
1078            Point::new(0, 0)
1079        );
1080        assert_eq!(
1081            rope.clip_point(Point::new(0, 1), Bias::Right),
1082            Point::new(0, 4)
1083        );
1084        assert_eq!(
1085            rope.clip_point(Point::new(0, 5), Bias::Right),
1086            Point::new(0, 4)
1087        );
1088
1089        assert_eq!(
1090            rope.clip_point_utf16(PointUtf16::new(0, 1), Bias::Left),
1091            PointUtf16::new(0, 0)
1092        );
1093        assert_eq!(
1094            rope.clip_point_utf16(PointUtf16::new(0, 1), Bias::Right),
1095            PointUtf16::new(0, 2)
1096        );
1097        assert_eq!(
1098            rope.clip_point_utf16(PointUtf16::new(0, 3), Bias::Right),
1099            PointUtf16::new(0, 2)
1100        );
1101
1102        assert_eq!(
1103            rope.clip_offset_utf16(OffsetUtf16(1), Bias::Left),
1104            OffsetUtf16(0)
1105        );
1106        assert_eq!(
1107            rope.clip_offset_utf16(OffsetUtf16(1), Bias::Right),
1108            OffsetUtf16(2)
1109        );
1110        assert_eq!(
1111            rope.clip_offset_utf16(OffsetUtf16(3), Bias::Right),
1112            OffsetUtf16(2)
1113        );
1114    }
1115
1116    #[gpui::test(iterations = 100)]
1117    fn test_random_rope(mut rng: StdRng) {
1118        let operations = env::var("OPERATIONS")
1119            .map(|i| i.parse().expect("invalid `OPERATIONS` variable"))
1120            .unwrap_or(10);
1121
1122        let mut expected = String::new();
1123        let mut actual = Rope::new();
1124        for _ in 0..operations {
1125            let end_ix = clip_offset(&expected, rng.gen_range(0..=expected.len()), Right);
1126            let start_ix = clip_offset(&expected, rng.gen_range(0..=end_ix), Left);
1127            let len = rng.gen_range(0..=64);
1128            let new_text: String = RandomCharIter::new(&mut rng).take(len).collect();
1129
1130            let mut new_actual = Rope::new();
1131            let mut cursor = actual.cursor(0);
1132            new_actual.append(cursor.slice(start_ix));
1133            new_actual.push(&new_text);
1134            cursor.seek_forward(end_ix);
1135            new_actual.append(cursor.suffix());
1136            actual = new_actual;
1137
1138            expected.replace_range(start_ix..end_ix, &new_text);
1139
1140            assert_eq!(actual.text(), expected);
1141            log::info!("text: {:?}", expected);
1142
1143            for _ in 0..5 {
1144                let end_ix = clip_offset(&expected, rng.gen_range(0..=expected.len()), Right);
1145                let start_ix = clip_offset(&expected, rng.gen_range(0..=end_ix), Left);
1146
1147                let actual_text = actual.chunks_in_range(start_ix..end_ix).collect::<String>();
1148                assert_eq!(actual_text, &expected[start_ix..end_ix]);
1149
1150                let mut actual_text = String::new();
1151                actual
1152                    .bytes_in_range(start_ix..end_ix)
1153                    .read_to_string(&mut actual_text)
1154                    .unwrap();
1155                assert_eq!(actual_text, &expected[start_ix..end_ix]);
1156
1157                assert_eq!(
1158                    actual
1159                        .reversed_chunks_in_range(start_ix..end_ix)
1160                        .collect::<Vec<&str>>()
1161                        .into_iter()
1162                        .rev()
1163                        .collect::<String>(),
1164                    &expected[start_ix..end_ix]
1165                );
1166            }
1167
1168            let mut offset_utf16 = OffsetUtf16(0);
1169            let mut point = Point::new(0, 0);
1170            let mut point_utf16 = PointUtf16::new(0, 0);
1171            for (ix, ch) in expected.char_indices().chain(Some((expected.len(), '\0'))) {
1172                assert_eq!(actual.offset_to_point(ix), point, "offset_to_point({})", ix);
1173                assert_eq!(
1174                    actual.offset_to_point_utf16(ix),
1175                    point_utf16,
1176                    "offset_to_point_utf16({})",
1177                    ix
1178                );
1179                assert_eq!(
1180                    actual.point_to_offset(point),
1181                    ix,
1182                    "point_to_offset({:?})",
1183                    point
1184                );
1185                assert_eq!(
1186                    actual.point_utf16_to_offset(point_utf16),
1187                    ix,
1188                    "point_utf16_to_offset({:?})",
1189                    point_utf16
1190                );
1191                assert_eq!(
1192                    actual.offset_to_offset_utf16(ix),
1193                    offset_utf16,
1194                    "offset_to_offset_utf16({:?})",
1195                    ix
1196                );
1197                assert_eq!(
1198                    actual.offset_utf16_to_offset(offset_utf16),
1199                    ix,
1200                    "offset_utf16_to_offset({:?})",
1201                    offset_utf16
1202                );
1203                if ch == '\n' {
1204                    point += Point::new(1, 0);
1205                    point_utf16 += PointUtf16::new(1, 0);
1206                } else {
1207                    point.column += ch.len_utf8() as u32;
1208                    point_utf16.column += ch.len_utf16() as u32;
1209                }
1210                offset_utf16.0 += ch.len_utf16();
1211            }
1212
1213            let mut offset_utf16 = OffsetUtf16(0);
1214            let mut point_utf16 = PointUtf16::zero();
1215            for unit in expected.encode_utf16() {
1216                let left_offset = actual.clip_offset_utf16(offset_utf16, Bias::Left);
1217                let right_offset = actual.clip_offset_utf16(offset_utf16, Bias::Right);
1218                assert!(right_offset >= left_offset);
1219                // Ensure translating UTF-16 offsets to UTF-8 offsets doesn't panic.
1220                actual.offset_utf16_to_offset(left_offset);
1221                actual.offset_utf16_to_offset(right_offset);
1222
1223                let left_point = actual.clip_point_utf16(point_utf16, Bias::Left);
1224                let right_point = actual.clip_point_utf16(point_utf16, Bias::Right);
1225                assert!(right_point >= left_point);
1226                // Ensure translating UTF-16 points to offsets doesn't panic.
1227                actual.point_utf16_to_offset(left_point);
1228                actual.point_utf16_to_offset(right_point);
1229
1230                offset_utf16.0 += 1;
1231                if unit == b'\n' as u16 {
1232                    point_utf16 += PointUtf16::new(1, 0);
1233                } else {
1234                    point_utf16 += PointUtf16::new(0, 1);
1235                }
1236            }
1237
1238            for _ in 0..5 {
1239                let end_ix = clip_offset(&expected, rng.gen_range(0..=expected.len()), Right);
1240                let start_ix = clip_offset(&expected, rng.gen_range(0..=end_ix), Left);
1241                assert_eq!(
1242                    actual.cursor(start_ix).summary::<TextSummary>(end_ix),
1243                    TextSummary::from(&expected[start_ix..end_ix])
1244                );
1245            }
1246
1247            let mut expected_longest_rows = Vec::new();
1248            let mut longest_line_len = -1_isize;
1249            for (row, line) in expected.split('\n').enumerate() {
1250                let row = row as u32;
1251                assert_eq!(
1252                    actual.line_len(row),
1253                    line.len() as u32,
1254                    "invalid line len for row {}",
1255                    row
1256                );
1257
1258                let line_char_count = line.chars().count() as isize;
1259                match line_char_count.cmp(&longest_line_len) {
1260                    Ordering::Less => {}
1261                    Ordering::Equal => expected_longest_rows.push(row),
1262                    Ordering::Greater => {
1263                        longest_line_len = line_char_count;
1264                        expected_longest_rows.clear();
1265                        expected_longest_rows.push(row);
1266                    }
1267                }
1268            }
1269
1270            let longest_row = actual.summary().longest_row;
1271            assert!(
1272                expected_longest_rows.contains(&longest_row),
1273                "incorrect longest row {}. expected {:?} with length {}",
1274                longest_row,
1275                expected_longest_rows,
1276                longest_line_len,
1277            );
1278        }
1279    }
1280
1281    fn clip_offset(text: &str, mut offset: usize, bias: Bias) -> usize {
1282        while !text.is_char_boundary(offset) {
1283            match bias {
1284                Bias::Left => offset -= 1,
1285                Bias::Right => offset += 1,
1286            }
1287        }
1288        offset
1289    }
1290
1291    impl Rope {
1292        fn text(&self) -> String {
1293            let mut text = String::new();
1294            for chunk in self.chunks.cursor::<()>() {
1295                text.push_str(&chunk.0);
1296            }
1297            text
1298        }
1299    }
1300}