Repository: microsoft/edit
File: src/buffer/line_cache.rs (Rust)

Code before:
                off += 1;
            }

            offset += text.len();
        }
    }

    /// Updates the cache after a deletion.
    /// `range` is the deleted byte range, and `text` is the content that was deleted.
    pub fn delete(&mut self, range: Range<usize>, text: &Vec<u8>) {
        let mut newlines = 0;
        for c in text {
            if *c == b'\n' {
                newlines += 1;
            }
        }

        if self.cache.len() == 0 { return; }
        
        let len = text.len();
        let mut i = self.cache.len() - 1;
        loop {
            let (ref mut off, ref mut line) = self.cache[i];
            if *off > range.start {
                if *off < range.end {
                    self.cache.remove(i); // cache point is within the deleted range
                } else {
                    *off -= len;
                    *line -= newlines;
                }
            }
            if i == 0 {
                break;
            }
            i -= 1;
        }
    }

    /// Updates the cache after an insertion.
    /// `offset` is where the insertion occurs, and `text` is the inserted content.
    pub fn insert(&mut self, offset: usize, text: &[u8]) {
        // Count how many newlines were inserted
        let mut newlines = 0;
        for c in text {
            if *c == b'\n' {
                newlines += 1;
            }
        }

        let len = text.len();
        for &mut (ref mut off, ref mut line) in &mut self.cache {

Review comment (performance):
This is O(n^2) worst case if the user deletes the contents between the start of the file and the middle of it, if I'm reading this right. It would be better for us to first find the offset of the `range.start` item, then find the offset of the `range.end` item, and then delete all items in that range in a single `.drain()` call.

Code after:
                off = memchr2(b'\n', b'\n', text, off);
                if off == text.len() { break; }

                if line % CACHE_EVERY == 0 {
                    self.cache.push(CachePoint { index: offset+off, line });
                }
                line += 1;
                off += 1;
            }

            offset += text.len();
        }
    }

    /// Updates the cache after a deletion.
    /// `range` is the deleted byte range, and `text` is the content that was deleted.
    pub fn delete(&mut self, range: Range<usize>, text: &Vec<u8>) {
        let mut newlines = 0;
        for c in text {
            if *c == b'\n' {
                newlines += 1;
            }
        }

        let mut beg_del = None;
        let mut end_del = None;
        for (i, point) in self.cache.iter_mut().enumerate() {
            if point.index >= range.start {
                if point.index < range.end {
                    // cache point is within the deleted range
                    if beg_del.is_none() { beg_del = Some(i); }
                    end_del = Some(i + 1);
                }
                else {
                    point.index -= text.len();
                    point.line -= newlines;
                }
            }
        }

        if let (Some(beg), Some(end)) = (beg_del, end_del) {
            self.cache.drain(beg..end);
        }
    }

    /// Updates the cache after an insertion.
    /// `offset` is where the insertion occurs, and `text` is the inserted content.
    pub fn insert(&mut self, offset: usize, text: &[u8]) {
        // Count how many newlines were inserted
        let mut newlines = 0;
        for c in text {