mod chunk;mod offset_utf16;mod point;mod point_utf16;mod unclipped; use chunk::{Chunk, ChunkSlice};use rayon::iter::{IntoParallelIterator, ParallelIterator as _};use smallvec::SmallVec;use std::{    cmp, fmt, io, mem,    ops::{AddAssign, Range},    str,};use sum_tree::{Bias, Dimension, SumTree}; pub use offset_utf16::OffsetUtf16;pub use point::Point;pub use point_utf16::PointUtf16;pub use unclipped::Unclipped; #[derive(Clone, Default)]pub struct Rope {    chunks: SumTree<Chunk>,} impl Rope {    pub fn new() -> Self {        Self::default()    }     pub fn append(&mut self, rope: Rope) {        if let Some(chunk) = rope.chunks.first() {            if self                .chunks                .last()                .map_or(false, |c| c.text.len() < chunk::MIN_BASE)                || chunk.text.len() < chunk::MIN_BASE            {                self.push_chunk(chunk.as_slice());                 let mut chunks = rope.chunks.cursor::<()>(&());                chunks.next(&());                chunks.next(&());                self.chunks.append(chunks.suffix(&()), &());                self.check_invariants();                return;            }        }         self.chunks.append(rope.chunks.clone(), &());        self.check_invariants();    }     pub fn replace(&mut self, range: Range<usize>, text: &str) {        let mut new_rope = Rope::new();        let mut cursor = self.cursor(0);        new_rope.append(cursor.slice(range.start));        cursor.seek_forward(range.end);        new_rope.push(text);        new_rope.append(cursor.suffix());        *self = new_rope;    }     pub fn slice(&self, range: Range<usize>) -> Rope {        let mut cursor = self.cursor(0);        cursor.seek_forward(range.start);        cursor.slice(range.end)    }     pub fn slice_rows(&self, range: Range<u32>) -> Rope {        // This would be more efficient with a forward advance after the first, but it's fine.        let start = self.point_to_offset(Point::new(range.start, 0));        let end = self.point_to_offset(Point::new(range.end, 0));        self.slice(start..end)    }     pub fn push(&mut self, mut text: &str) {        self.chunks.update_last(            |last_chunk| {                let split_ix = if last_chunk.text.len() + text.len() <= chunk::MAX_BASE {                    text.len()                } else {                    let mut split_ix = cmp::min(                        chunk::MIN_BASE.saturating_sub(last_chunk.text.len()),                        text.len(),                    );                    while !text.is_char_boundary(split_ix) {                        split_ix += 1;                    }                    split_ix                };                 let (suffix, remainder) = text.split_at(split_ix);                last_chunk.push_str(suffix);                text = remainder;            },            &(),        );         if text.len() > 2048 {            return self.push_large(text);        }        let mut new_chunks = SmallVec::<[_; 16]>::new();         while !text.is_empty() {            let mut split_ix = cmp::min(chunk::MAX_BASE, text.len());            while !text.is_char_boundary(split_ix) {                split_ix -= 1;            }            let (chunk, remainder) = text.split_at(split_ix);            new_chunks.push(chunk);            text = remainder;        }         #[cfg(test)]        const PARALLEL_THRESHOLD: usize = 4;        #[cfg(not(test))]        const PARALLEL_THRESHOLD: usize = 4 * (2 * sum_tree::TREE_BASE);         if new_chunks.len() >= PARALLEL_THRESHOLD {            self.chunks                .par_extend(new_chunks.into_vec().into_par_iter().map(Chunk::new), &());        } else {            self.chunks                .extend(new_chunks.into_iter().map(Chunk::new), &());        }         self.check_invariants();    }     /// A copy of `push` specialized for working with large quantities of text.    fn push_large(&mut self, mut text: &str) {        // To avoid frequent reallocs when loading large swaths of file contents,        // we estimate worst-case `new_chunks` capacity;        // Chunk is a fixed-capacity buffer. If a character falls on        // chunk boundary, we push it off to the following chunk (thus leaving a small bit of capacity unfilled in current chunk).        // Worst-case chunk count when loading a file is then a case where every chunk ends up with that unused capacity.        // Since we're working with UTF-8, each character is at most 4 bytes wide. It follows then that the worst case is where        // a chunk ends with 3 bytes of a 4-byte character. These 3 bytes end up being stored in the following chunk, thus wasting        // 3 bytes of storage in current chunk.        // For example, a 1024-byte string can occupy between 32 (full ASCII, 1024/32) and 36 (full 4-byte UTF-8, 1024 / 29 rounded up) chunks.        const MIN_CHUNK_SIZE: usize = chunk::MAX_BASE - 3;         // We also round up the capacity up by one, for a good measure; we *really* don't want to realloc here, as we assume that the # of characters        // we're working with there is large.        let capacity = (text.len() + MIN_CHUNK_SIZE - 1) / MIN_CHUNK_SIZE;        let mut new_chunks = Vec::with_capacity(capacity);         while !text.is_empty() {            let mut split_ix = cmp::min(chunk::MAX_BASE, text.len());            while !text.is_char_boundary(split_ix) {                split_ix -= 1;            }            let (chunk, remainder) = text.split_at(split_ix);            new_chunks.push(chunk);            text = remainder;        }         #[cfg(test)]        const PARALLEL_THRESHOLD: usize = 4;        #[cfg(not(test))]        const PARALLEL_THRESHOLD: usize = 4 * (2 * sum_tree::TREE_BASE);         if new_chunks.len() >= PARALLEL_THRESHOLD {            self.chunks                .par_extend(new_chunks.into_par_iter().map(Chunk::new), &());        } else {            self.chunks                .extend(new_chunks.into_iter().map(Chunk::new), &());        }         self.check_invariants();    }     fn push_chunk(&mut self, mut chunk: ChunkSlice) {        self.chunks.update_last(            |last_chunk| {                let split_ix = if last_chunk.text.len() + chunk.len() <= chunk::MAX_BASE {                    chunk.len()                } else {                    let mut split_ix = cmp::min(                        chunk::MIN_BASE.saturating_sub(last_chunk.text.len()),                        chunk.len(),                    );                    while !chunk.is_char_boundary(split_ix) {                        split_ix += 1;                    }                    split_ix                };                 let (suffix, remainder) = chunk.split_at(split_ix);                last_chunk.append(suffix);                chunk = remainder;            },            &(),        );         if !chunk.is_empty() {            self.chunks.push(chunk.into(), &());        }    }     pub fn push_front(&mut self, text: &str) {        let suffix = mem::replace(self, Rope::from(text));        self.append(suffix);    }     fn check_invariants(&self) {        #[cfg(test)]        {            // Ensure all chunks except maybe the last one are not underflowing.            // Allow some wiggle room for multibyte characters at chunk boundaries.            let mut chunks = self.chunks.cursor::<()>(&()).peekable();            while let Some(chunk) = chunks.next() {                if chunks.peek().is_some() {                    assert!(chunk.text.len() + 3 >= chunk::MIN_BASE);                }            }        }    }     pub fn summary(&self) -> TextSummary {        self.chunks.summary().text.clone()    }     pub fn len(&self) -> usize {        self.chunks.extent(&())    }     pub fn is_empty(&self) -> bool {        self.len() == 0    }     pub fn max_point(&self) -> Point {        self.chunks.extent(&())    }     pub fn max_point_utf16(&self) -> PointUtf16 {        self.chunks.extent(&())    }     pub fn cursor(&self, offset: usize) -> Cursor {        Cursor::new(self, offset)    }     pub fn chars(&self) -> impl Iterator<Item = char> + '_ {        self.chars_at(0)    }     pub fn chars_at(&self, start: usize) -> impl Iterator<Item = char> + '_ {        self.chunks_in_range(start..self.len()).flat_map(str::chars)    }     pub fn reversed_chars_at(&self, start: usize) -> impl Iterator<Item = char> + '_ {        self.reversed_chunks_in_range(0..start)            .flat_map(|chunk| chunk.chars().rev())    }     pub fn bytes_in_range(&self, range: Range<usize>) -> Bytes {        Bytes::new(self, range, false)    }     pub fn reversed_bytes_in_range(&self, range: Range<usize>) -> Bytes {        Bytes::new(self, range, true)    }     pub fn chunks(&self) -> Chunks {        self.chunks_in_range(0..self.len())    }     pub fn chunks_in_range(&self, range: Range<usize>) -> Chunks {        Chunks::new(self, range, false)    }     pub fn reversed_chunks_in_range(&self, range: Range<usize>) -> Chunks {        Chunks::new(self, range, true)    }     pub fn offset_to_offset_utf16(&self, offset: usize) -> OffsetUtf16 {        if offset >= self.summary().len {            return self.summary().len_utf16;        }        let mut cursor = self.chunks.cursor::<(usize, OffsetUtf16)>(&());        cursor.seek(&offset, Bias::Left, &());        let overshoot = offset - cursor.start().0;        cursor.start().1            + cursor.item().map_or(Default::default(), |chunk| {                chunk.as_slice().offset_to_offset_utf16(overshoot)            })    }     pub fn offset_utf16_to_offset(&self, offset: OffsetUtf16) -> usize {        if offset >= self.summary().len_utf16 {            return self.summary().len;        }        let mut cursor = self.chunks.cursor::<(OffsetUtf16, usize)>(&());        cursor.seek(&offset, Bias::Left, &());        let overshoot = offset - cursor.start().0;        cursor.start().1            + cursor.item().map_or(Default::default(), |chunk| {                chunk.as_slice().offset_utf16_to_offset(overshoot)            })    }     pub fn offset_to_point(&self, offset: usize) -> Point {        if offset >= self.summary().len {            return self.summary().lines;        }        let mut cursor = self.chunks.cursor::<(usize, Point)>(&());        cursor.seek(&offset, Bias::Left, &());        let overshoot = offset - cursor.start().0;        cursor.start().1            + cursor.item().map_or(Point::zero(), |chunk| {                chunk.as_slice().offset_to_point(overshoot)            })    }     pub fn offset_to_point_utf16(&self, offset: usize) -> PointUtf16 {        if offset >= self.summary().len {            return self.summary().lines_utf16();        }        let mut cursor = self.chunks.cursor::<(usize, PointUtf16)>(&());        cursor.seek(&offset, Bias::Left, &());        let overshoot = offset - cursor.start().0;        cursor.start().1            + cursor.item().map_or(PointUtf16::zero(), |chunk| {                chunk.as_slice().offset_to_point_utf16(overshoot)            })    }     pub fn point_to_point_utf16(&self, point: Point) -> PointUtf16 {        if point >= self.summary().lines {            return self.summary().lines_utf16();        }        let mut cursor = self.chunks.cursor::<(Point, PointUtf16)>(&());        cursor.seek(&point, Bias::Left, &());        let overshoot = point - cursor.start().0;        cursor.start().1            + cursor.item().map_or(PointUtf16::zero(), |chunk| {                chunk.as_slice().point_to_point_utf16(overshoot)            })    }     pub fn point_to_offset(&self, point: Point) -> usize {        if point >= self.summary().lines {            return self.summary().len;        }        let mut cursor = self.chunks.cursor::<(Point, usize)>(&());        cursor.seek(&point, Bias::Left, &());        let overshoot = point - cursor.start().0;        cursor.start().1            + cursor                .item()                .map_or(0, |chunk| chunk.as_slice().point_to_offset(overshoot))    }     pub fn point_utf16_to_offset(&self, point: PointUtf16) -> usize {        self.point_utf16_to_offset_impl(point, false)    }     pub fn unclipped_point_utf16_to_offset(&self, point: Unclipped<PointUtf16>) -> usize {        self.point_utf16_to_offset_impl(point.0, true)    }     fn point_utf16_to_offset_impl(&self, point: PointUtf16, clip: bool) -> usize {        if point >= self.summary().lines_utf16() {            return self.summary().len;        }        let mut cursor = self.chunks.cursor::<(PointUtf16, usize)>(&());        cursor.seek(&point, Bias::Left, &());        let overshoot = point - cursor.start().0;        cursor.start().1            + cursor.item().map_or(0, |chunk| {                chunk.as_slice().point_utf16_to_offset(overshoot, clip)            })    }     pub fn unclipped_point_utf16_to_point(&self, point: Unclipped<PointUtf16>) -> Point {        if point.0 >= self.summary().lines_utf16() {            return self.summary().lines;        }        let mut cursor = self.chunks.cursor::<(PointUtf16, Point)>(&());        cursor.seek(&point.0, Bias::Left, &());        let overshoot = Unclipped(point.0 - cursor.start().0);        cursor.start().1            + cursor.item().map_or(Point::zero(), |chunk| {                chunk.as_slice().unclipped_point_utf16_to_point(overshoot)            })    }     pub fn clip_offset(&self, mut offset: usize, bias: Bias) -> usize {        let mut cursor = self.chunks.cursor::<usize>(&());        cursor.seek(&offset, Bias::Left, &());        if let Some(chunk) = cursor.item() {            let mut ix = offset - cursor.start();            while !chunk.text.is_char_boundary(ix) {                match bias {                    Bias::Left => {                        ix -= 1;                        offset -= 1;                    }                    Bias::Right => {                        ix += 1;                        offset += 1;                    }                }            }            offset        } else {            self.summary().len        }    }     pub fn clip_offset_utf16(&self, offset: OffsetUtf16, bias: Bias) -> OffsetUtf16 {        let mut cursor = self.chunks.cursor::<OffsetUtf16>(&());        cursor.seek(&offset, Bias::Right, &());        if let Some(chunk) = cursor.item() {            let overshoot = offset - cursor.start();            *cursor.start() + chunk.as_slice().clip_offset_utf16(overshoot, bias)        } else {            self.summary().len_utf16        }    }     pub fn clip_point(&self, point: Point, bias: Bias) -> Point {        let mut cursor = self.chunks.cursor::<Point>(&());        cursor.seek(&point, Bias::Right, &());        if let Some(chunk) = cursor.item() {            let overshoot = point - cursor.start();            *cursor.start() + chunk.as_slice().clip_point(overshoot, bias)        } else {            self.summary().lines        }    }     pub fn clip_point_utf16(&self, point: Unclipped<PointUtf16>, bias: Bias) -> PointUtf16 {        let mut cursor = self.chunks.cursor::<PointUtf16>(&());        cursor.seek(&point.0, Bias::Right, &());        if let Some(chunk) = cursor.item() {            let overshoot = Unclipped(point.0 - cursor.start());            *cursor.start() + chunk.as_slice().clip_point_utf16(overshoot, bias)        } else {            self.summary().lines_utf16()        }    }     pub fn line_len(&self, row: u32) -> u32 {        self.clip_point(Point::new(row, u32::MAX), Bias::Left)            .column    }} impl<'a> From<&'a str> for Rope {    fn from(text: &'a str) -> Self {        let mut rope = Self::new();        rope.push(text);        rope    }} impl<'a> FromIterator<&'a str> for Rope {    fn from_iter<T: IntoIterator<Item = &'a str>>(iter: T) -> Self {        let mut rope = Rope::new();        for chunk in iter {            rope.push(chunk);        }        rope    }} impl From<String> for Rope {    fn from(text: String) -> Self {        Rope::from(text.as_str())    }} impl fmt::Display for Rope {    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {        for chunk in self.chunks() {            write!(f, "{}", chunk)?;        }        Ok(())    }} impl fmt::Debug for Rope {    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {        use std::fmt::Write as _;         write!(f, "\"")?;        let mut format_string = String::new();        for chunk in self.chunks() {            write!(&mut format_string, "{:?}", chunk)?;            write!(f, "{}", &format_string[1..format_string.len() - 1])?;            format_string.clear();        }        write!(f, "\"")?;        Ok(())    }

Lines 1–500 of 1727. Load more