Fix incorrect grid.len() and grid.history_size()

2 files changed, 120 insertions, 175 deletions

diff --git a/alacritty_terminal/src/grid/mod.rs b/alacritty_terminal/src/grid/mod.rs
index 1db5b748..d1ccd320 100644
--- a/alacritty_terminal/src/grid/mod.rs
+++ b/alacritty_terminal/src/grid/mod.rs
@@ -32,8 +32,6 @@ mod tests;
 mod storage;
 use self::storage::Storage;
 
-const MIN_INIT_SIZE: usize = 1_000;
-
 /// Bidirection iterator
 pub trait BidirectionalIterator: Iterator {
     fn prev(&mut self) -> Option<Self::Item>;
@@ -62,7 +60,6 @@ impl<T: PartialEq> ::std::cmp::PartialEq for Grid<T> {
             && self.cols.eq(&other.cols)
             && self.lines.eq(&other.lines)
             && self.display_offset.eq(&other.display_offset)
-            && self.scroll_limit.eq(&other.scroll_limit)
             && self.selection.eq(&other.selection)
     }
 }
@@ -86,11 +83,11 @@ pub trait GridCell {
 /// │                         │
 /// │      UNINITIALIZED      │
 /// │                         │
-/// ├─────────────────────────┤  <-- raw.len()
+/// ├─────────────────────────┤  <-- self.raw.inner.len()
 /// │                         │
 /// │      RESIZE BUFFER      │
 /// │                         │
-/// ├─────────────────────────┤  <-- scroll_limit + lines
+/// ├─────────────────────────┤  <-- self.history_size() + lines
 /// │                         │
 /// │     SCROLLUP REGION     │
 /// │                         │
@@ -112,26 +109,24 @@ pub struct Grid<T> {
     /// columns in that row.
     raw: Storage<T>,
 
-    /// Number of columns
+    /// Number of columns.
     cols: Column,
 
     /// Number of visible lines.
     lines: Line,
 
-    /// Offset of displayed area
+    /// Offset of displayed area.
     ///
     /// If the displayed region isn't at the bottom of the screen, it stays
     /// stationary while more text is emitted. The scrolling implementation
     /// updates this offset accordingly.
     display_offset: usize,
 
-    /// An limit on how far back it's possible to scroll
-    scroll_limit: usize,
-
-    /// Selected region
+    /// Selected region.
     #[serde(skip)]
     pub selection: Option<Selection>,
 
+    /// Maximum number of lines in history.
     max_scroll_limit: usize,
 }
 
@@ -147,15 +142,7 @@ pub enum Scroll {
 impl<T: GridCell + PartialEq + Copy> Grid<T> {
     pub fn new(lines: Line, cols: Column, scrollback: usize, template: T) -> Grid<T> {
         let raw = Storage::with_capacity(lines, Row::new(cols, &template));
-        Grid {
-            raw,
-            cols,
-            lines,
-            display_offset: 0,
-            scroll_limit: 0,
-            selection: None,
-            max_scroll_limit: scrollback,
-        }
+        Grid { raw, cols, lines, display_offset: 0, selection: None, max_scroll_limit: scrollback }
     }
 
     pub fn buffer_to_visible(&self, point: impl Into<Point<usize>>) -> Option<Point<usize>> {
@@ -179,11 +166,13 @@ impl<T: GridCell + PartialEq + Copy> Grid<T> {
     }
 
     /// Update the size of the scrollback history
-    pub fn update_history(&mut self, history_size: usize, template: &T) {
-        self.raw.update_history(history_size, Row::new(self.cols, &template));
+    pub fn update_history(&mut self, history_size: usize) {
+        let current_history_size = self.history_size();
+        if current_history_size > history_size {
+            self.raw.shrink_lines(current_history_size - history_size);
+        }
+        self.display_offset = min(self.display_offset, history_size);
         self.max_scroll_limit = history_size;
-        self.scroll_limit = min(self.scroll_limit, history_size);
-        self.display_offset = min(self.display_offset, self.scroll_limit);
     }
 
     pub fn scroll_display(&mut self, scroll: Scroll) {
@@ -191,16 +180,16 @@ impl<T: GridCell + PartialEq + Copy> Grid<T> {
             Scroll::Lines(count) => {
                 self.display_offset = min(
                     max((self.display_offset as isize) + count, 0isize) as usize,
-                    self.scroll_limit,
+                    self.history_size(),
                 );
             },
             Scroll::PageUp => {
-                self.display_offset = min(self.display_offset + self.lines.0, self.scroll_limit);
+                self.display_offset = min(self.display_offset + self.lines.0, self.history_size());
             },
             Scroll::PageDown => {
                 self.display_offset -= min(self.display_offset, self.lines.0);
             },
-            Scroll::Top => self.display_offset = self.scroll_limit,
+            Scroll::Top => self.display_offset = self.history_size(),
             Scroll::Bottom => self.display_offset = 0,
         }
     }
@@ -232,21 +221,17 @@ impl<T: GridCell + PartialEq + Copy> Grid<T> {
     }
 
     fn increase_scroll_limit(&mut self, count: usize, template: &T) {
-        self.scroll_limit = min(self.scroll_limit + count, self.max_scroll_limit);
-
-        // Initialize new lines when the history buffer is smaller than the scroll limit
-        let history_size = self.raw.len().saturating_sub(*self.lines);
-        if history_size < self.scroll_limit {
-            let new = min(
-                max(self.scroll_limit - history_size, MIN_INIT_SIZE),
-                self.max_scroll_limit - history_size,
-            );
-            self.raw.initialize(new, Row::new(self.cols, template));
+        let count = min(count, self.max_scroll_limit - self.history_size());
+        if count != 0 {
+            self.raw.initialize(count, template, self.cols);
         }
     }
 
     fn decrease_scroll_limit(&mut self, count: usize) {
-        self.scroll_limit = self.scroll_limit.saturating_sub(count);
+        let count = min(count, self.history_size());
+        if count != 0 {
+            self.raw.shrink_lines(min(count, self.history_size()));
+        }
     }
 
     /// Add lines to the visible area
@@ -262,12 +247,12 @@ impl<T: GridCell + PartialEq + Copy> Grid<T> {
         self.lines = new_line_count;
 
         // Move existing lines up if there is no scrollback to fill new lines
-        if lines_added.0 > self.scroll_limit {
-            let scroll_lines = lines_added - self.scroll_limit;
-            self.scroll_up(&(Line(0)..new_line_count), scroll_lines, template);
+        let history_size = self.history_size();
+        if lines_added.0 > history_size {
+            self.scroll_up(&(Line(0)..new_line_count), lines_added - history_size, template);
         }
 
-        self.scroll_limit = self.scroll_limit.saturating_sub(*lines_added);
+        self.decrease_scroll_limit(*lines_added);
         self.display_offset = self.display_offset.saturating_sub(*lines_added);
     }
 
@@ -326,22 +311,13 @@ impl<T: GridCell + PartialEq + Copy> Grid<T> {
             last_row.append(&mut cells);
 
             if row.is_empty() {
-                let raw_len = i + 1 + reversed.len();
-                if raw_len < self.lines.0 || self.scroll_limit == 0 {
+                if i + reversed.len() < self.lines.0 {
                     // Add new line and move lines up if we can't pull from history
                     cursor_pos.line = Line(cursor_pos.line.saturating_sub(1));
                     new_empty_lines += 1;
-                } else {
-                    // Make sure viewport doesn't move if line is outside of the visible
-                    // area
-                    if i < self.display_offset {
-                        self.display_offset = self.display_offset.saturating_sub(1);
-                    }
-
-                    // Remove one line from scrollback, since we just moved it to the
-                    // viewport
-                    self.scroll_limit = self.scroll_limit.saturating_sub(1);
-                    self.display_offset = min(self.display_offset, self.scroll_limit);
+                } else if i < self.display_offset {
+                    // Keep viewport in place if line is outside of the visible area
+                    self.display_offset = self.display_offset.saturating_sub(1);
                 }
 
                 // Don't push line into the new buffer
@@ -368,6 +344,7 @@ impl<T: GridCell + PartialEq + Copy> Grid<T> {
 
         self.raw.replace_inner(new_raw);
 
+        self.display_offset = min(self.display_offset, self.history_size());
         self.cols = cols;
     }
 
@@ -450,9 +427,6 @@ impl<T: GridCell + PartialEq + Copy> Grid<T> {
                         wrapped.append(&mut vec![*template; cols.0 - occ]);
                     }
                     row = Row::from_vec(wrapped, occ);
-
-                    // Increase scrollback history
-                    self.scroll_limit = min(self.scroll_limit + 1, self.max_scroll_limit);
                 }
             }
         }
@@ -643,6 +617,7 @@ impl<T> Grid<T> {
         self.lines
     }
 
+    #[inline]
     pub fn display_iter(&self) -> DisplayIter<'_, T> {
         DisplayIter::new(self)
     }
@@ -652,16 +627,10 @@ impl<T> Grid<T> {
         self.cols
     }
 
+    #[inline]
     pub fn clear_history(&mut self) {
         // Explicitly purge all lines from history
-        let shrinkage = self.raw.len() - self.lines.0;
-        self.raw.shrink_lines(shrinkage);
-        self.scroll_limit = 0;
-    }
-
-    #[inline]
-    pub fn scroll_limit(&self) -> usize {
-        self.scroll_limit
+        self.raw.shrink_lines(self.history_size());
     }
 
     /// Total number of lines in the buffer, this includes scrollback + visible lines
@@ -672,23 +641,29 @@ impl<T> Grid<T> {
 
     #[inline]
     pub fn history_size(&self) -> usize {
-        self.raw.len().saturating_sub(*self.lines)
+        self.raw.len() - *self.lines
     }
 
     /// This is used only for initializing after loading ref-tests
+    #[inline]
     pub fn initialize_all(&mut self, template: &T)
     where
         T: Copy + GridCell,
     {
-        let history_size = self.raw.len().saturating_sub(*self.lines);
-        self.raw.initialize(self.max_scroll_limit - history_size, Row::new(self.cols, template));
+        // Remove all cached lines to clear them of any content
+        self.truncate();
+
+        // Initialize everything with empty new lines
+        self.raw.initialize(self.max_scroll_limit - self.history_size(), template, self.cols);
     }
 
     /// This is used only for truncating before saving ref-tests
+    #[inline]
     pub fn truncate(&mut self) {
         self.raw.truncate();
     }
 
+    #[inline]
     pub fn iter_from(&self, point: Point<usize>) -> GridIterator<'_, T> {
         GridIterator { grid: self, cur: point }
     }
diff --git a/alacritty_terminal/src/grid/storage.rs b/alacritty_terminal/src/grid/storage.rs
index 3182da57..145e302b 100644
--- a/alacritty_terminal/src/grid/storage.rs
+++ b/alacritty_terminal/src/grid/storage.rs
@@ -1,14 +1,15 @@
-use std::cmp::{Ordering, PartialEq};
+use std::cmp::{max, PartialEq};
 use std::ops::{Index, IndexMut};
 use std::vec::Drain;
 
 use serde::{Deserialize, Serialize};
 
 use super::Row;
-use crate::index::Line;
+use crate::grid::GridCell;
+use crate::index::{Column, Line};
 
-/// Maximum number of invisible lines before buffer is resized
-const TRUNCATE_STEP: usize = 100;
+/// Maximum number of buffered lines outside of the grid for performance optimization.
+const MAX_CACHE_SIZE: usize = 1_000;
 
 /// A ring buffer for optimizing indexing and rotation.
 ///
@@ -37,7 +38,7 @@ pub struct Storage<T> {
     /// ring buffer. It represents the bottommost line of the terminal.
     zero: usize,
 
-    /// An index separating the visible and scrollback regions.
+    /// Number of visible lines.
     visible_lines: Line,
 
     /// Total number of lines currently active in the terminal (scrollback + visible)
@@ -51,81 +52,40 @@ pub struct Storage<T> {
 
 impl<T: PartialEq> PartialEq for Storage<T> {
     fn eq(&self, other: &Self) -> bool {
-        // Make sure length is equal
-        if self.inner.len() != other.inner.len() {
-            return false;
-        }
-
-        // Check which vec has the bigger zero
-        let (ref bigger, ref smaller) =
-            if self.zero >= other.zero { (self, other) } else { (other, self) };
+        // Both storage buffers need to be truncated and zeroed
+        assert_eq!(self.zero, 0);
+        assert_eq!(other.zero, 0);
 
-        // Calculate the actual zero offset
-        let bigger_zero = bigger.zero;
-        let smaller_zero = smaller.zero;
-
-        // Compare the slices in chunks
-        // Chunks:
-        //   - Bigger zero to the end
-        //   - Remaining lines in smaller zero vec
-        //   - Beginning of smaller zero vec
-        //
-        // Example:
-        //   Bigger Zero (6):
-        //     4  5  6  | 7  8  9  | 0  1  2  3
-        //     C2 C2 C2 | C3 C3 C3 | C1 C1 C1 C1
-        //   Smaller Zero (3):
-        //     7  8  9  | 0  1  2  3  | 4  5  6
-        //     C3 C3 C3 | C1 C1 C1 C1 | C2 C2 C2
-        let len = self.inner.len();
-        bigger.inner[bigger_zero..]
-            == smaller.inner[smaller_zero..smaller_zero + (len - bigger_zero)]
-            && bigger.inner[..bigger_zero - smaller_zero]
-                == smaller.inner[smaller_zero + (len - bigger_zero)..]
-            && bigger.inner[bigger_zero - smaller_zero..bigger_zero]
-                == smaller.inner[..smaller_zero]
+        self.inner == other.inner && self.len == other.len
     }
 }
 
 impl<T> Storage<T> {
     #[inline]
-    pub fn with_capacity(lines: Line, template: Row<T>) -> Storage<T>
+    pub fn with_capacity(visible_lines: Line, template: Row<T>) -> Storage<T>
     where
         T: Clone,
     {
         // Initialize visible lines, the scrollback buffer is initialized dynamically
-        let inner = vec![template; lines.0];
+        let inner = vec![template; visible_lines.0];
 
-        Storage { inner, zero: 0, visible_lines: lines - 1, len: lines.0 }
+        Storage { inner, zero: 0, visible_lines, len: visible_lines.0 }
     }
 
-    /// Update the size of the scrollback history
-    pub fn update_history(&mut self, history_size: usize, template_row: Row<T>)
-    where
-        T: Clone,
-    {
-        let current_history = self.len - (self.visible_lines.0 + 1);
-        match history_size.cmp(&current_history) {
-            Ordering::Greater => self.grow_lines(history_size - current_history, template_row),
-            Ordering::Less => self.shrink_lines(current_history - history_size),
-            _ => (),
-        }
-    }
-
-    /// Increase the number of lines in the buffer
+    /// Increase the number of lines in the buffer.
     pub fn grow_visible_lines(&mut self, next: Line, template_row: Row<T>)
     where
         T: Clone,
     {
         // Number of lines the buffer needs to grow
-        let growage = (next - (self.visible_lines + 1)).0;
-        self.grow_lines(growage, template_row);
+        let growage = next - self.visible_lines;
+        self.grow_lines(growage.0, template_row);
 
         // Update visible lines
-        self.visible_lines = next - 1;
+        self.visible_lines = next;
     }
 
-    /// Grow the number of lines in the buffer, filling new lines with the template
+    /// Grow the number of lines in the buffer, filling new lines with the template.
     fn grow_lines(&mut self, growage: usize, template_row: Row<T>)
     where
         T: Clone,
@@ -152,14 +112,14 @@ impl<T> Storage<T> {
         self.len += growage;
     }
 
-    /// Decrease the number of lines in the buffer
+    /// Decrease the number of lines in the buffer.
     pub fn shrink_visible_lines(&mut self, next: Line) {
         // Shrink the size without removing any lines
-        let shrinkage = (self.visible_lines - (next - 1)).0;
-        self.shrink_lines(shrinkage);
+        let shrinkage = self.visible_lines - next;
+        self.shrink_lines(shrinkage.0);
 
         // Update visible lines
-        self.visible_lines = next - 1;
+        self.visible_lines = next;
     }
 
     // Shrink the number of lines in the buffer
@@ -167,12 +127,12 @@ impl<T> Storage<T> {
         self.len -= shrinkage;
 
         // Free memory
-        if self.inner.len() > self.len() + TRUNCATE_STEP {
+        if self.inner.len() > self.len + MAX_CACHE_SIZE {
             self.truncate();
         }
     }
 
-    /// Truncate the invisible elements from the raw buffer
+    /// Truncate the invisible elements from the raw buffer.
     pub fn truncate(&mut self) {
         self.inner.rotate_left(self.zero);
         self.inner.truncate(self.len);
@@ -180,19 +140,22 @@ impl<T> Storage<T> {
         self.zero = 0;
     }
 
-    /// Dynamically grow the storage buffer at runtime
-    pub fn initialize(&mut self, num_rows: usize, template_row: Row<T>)
+    /// Dynamically grow the storage buffer at runtime.
+    #[inline]
+    pub fn initialize(&mut self, additional_rows: usize, template: &T, cols: Column)
     where
-        T: Clone,
+        T: GridCell + Copy,
     {
-        let mut new = vec![template_row; num_rows];
-
-        let mut split = self.inner.split_off(self.zero);
-        self.inner.append(&mut new);
-        self.inner.append(&mut split);
+        if self.len + additional_rows > self.inner.len() {
+            let realloc_size = max(additional_rows, MAX_CACHE_SIZE);
+            let mut new = vec![Row::new(cols, template); realloc_size];
+            let mut split = self.inner.split_off(self.zero);
+            self.inner.append(&mut new);
+            self.inner.append(&mut split);
+            self.zero += realloc_size;
+        }
 
-        self.zero += num_rows;
-        self.len += num_rows;
+        self.len += additional_rows;
     }
 
     #[inline]
@@ -219,7 +182,7 @@ impl<T> Storage<T> {
     }
 
     pub fn swap_lines(&mut self, a: Line, b: Line) {
-        let offset = self.inner.len() + self.zero + *self.visible_lines;
+        let offset = self.inner.len() + self.zero + *self.visible_lines - 1;
         let a = (offset - *a) % self.inner.len();
         let b = (offset - *b) % self.inner.len();
         self.inner.swap(a, b);
@@ -311,7 +274,7 @@ impl<T> Index<Line> for Storage<T> {
 
     #[inline]
     fn index(&self, index: Line) -> &Self::Output {
-        let index = self.visible_lines - index;
+        let index = self.visible_lines - 1 - index;
         &self[*index]
     }
 }
@@ -319,7 +282,7 @@ impl<T> Index<Line> for Storage<T> {
 impl<T> IndexMut<Line> for Storage<T> {
     #[inline]
     fn index_mut(&mut self, index: Line) -> &mut Self::Output {
-        let index = self.visible_lines - index;
+        let index = self.visible_lines - 1 - index;
         &mut self[*index]
     }
 }
@@ -327,7 +290,7 @@ impl<T> IndexMut<Line> for Storage<T> {
 #[cfg(test)]
 mod test {
     use crate::grid::row::Row;
-    use crate::grid::storage::Storage;
+    use crate::grid::storage::{Storage, MAX_CACHE_SIZE};
     use crate::grid::GridCell;
     use crate::index::{Column, Line};
     use crate::term::cell::Flags;
@@ -357,7 +320,7 @@ mod test {
         assert_eq!(storage.inner.len(), 3);
         assert_eq!(storage.len, 3);
         assert_eq!(storage.zero, 0);
-        assert_eq!(storage.visible_lines, Line(2));
+        assert_eq!(storage.visible_lines, Line(3));
     }
 
     #[test]
@@ -418,7 +381,7 @@ mod test {
                 Row::new(Column(1), &'-'),
             ],
             zero: 0,
-            visible_lines: Line(2),
+            visible_lines: Line(3),
             len: 3,
         };
 
@@ -434,9 +397,10 @@ mod test {
                 Row::new(Column(1), &'-'),
             ],
             zero: 1,
-            visible_lines: Line(0),
+            visible_lines: Line(4),
             len: 4,
         };
+        assert_eq!(storage.visible_lines, expected.visible_lines);
         assert_eq!(storage.inner, expected.inner);
         assert_eq!(storage.zero, expected.zero);
         assert_eq!(storage.len, expected.len);
@@ -463,7 +427,7 @@ mod test {
                 Row::new(Column(1), &'1'),
             ],
             zero: 1,
-            visible_lines: Line(2),
+            visible_lines: Line(3),
             len: 3,
         };
 
@@ -479,9 +443,10 @@ mod test {
                 Row::new(Column(1), &'1'),
             ],
             zero: 2,
-            visible_lines: Line(0),
+            visible_lines: Line(4),
             len: 4,
         };
+        assert_eq!(storage.visible_lines, expected.visible_lines);
         assert_eq!(storage.inner, expected.inner);
         assert_eq!(storage.zero, expected.zero);
         assert_eq!(storage.len, expected.len);
@@ -507,7 +472,7 @@ mod test {
                 Row::new(Column(1), &'1'),
             ],
             zero: 1,
-            visible_lines: Line(2),
+            visible_lines: Line(3),
             len: 3,
         };
 
@@ -522,9 +487,10 @@ mod test {
                 Row::new(Column(1), &'1'),
             ],
             zero: 1,
-            visible_lines: Line(0),
+            visible_lines: Line(2),
             len: 2,
         };
+        assert_eq!(storage.visible_lines, expected.visible_lines);
         assert_eq!(storage.inner, expected.inner);
         assert_eq!(storage.zero, expected.zero);
         assert_eq!(storage.len, expected.len);
@@ -550,7 +516,7 @@ mod test {
                 Row::new(Column(1), &'2'),
             ],
             zero: 0,
-            visible_lines: Line(2),
+            visible_lines: Line(3),
             len: 3,
         };
 
@@ -565,9 +531,10 @@ mod test {
                 Row::new(Column(1), &'2'),
             ],
             zero: 0,
-            visible_lines: Line(0),
+            visible_lines: Line(2),
             len: 2,
         };
+        assert_eq!(storage.visible_lines, expected.visible_lines);
         assert_eq!(storage.inner, expected.inner);
         assert_eq!(storage.zero, expected.zero);
         assert_eq!(storage.len, expected.len);
@@ -602,7 +569,7 @@ mod test {
                 Row::new(Column(1), &'3'),
             ],
             zero: 2,
-            visible_lines: Line(5),
+            visible_lines: Line(6),
             len: 6,
         };
 
@@ -620,9 +587,10 @@ mod test {
                 Row::new(Column(1), &'3'),
             ],
             zero: 2,
-            visible_lines: Line(0),
+            visible_lines: Line(2),
             len: 2,
         };
+        assert_eq!(storage.visible_lines, expected.visible_lines);
         assert_eq!(storage.inner, expected.inner);
         assert_eq!(storage.zero, expected.zero);
         assert_eq!(storage.len, expected.len);
@@ -815,28 +783,30 @@ mod test {
         };
 
         // Initialize additional lines
-        storage.initialize(3, Row::new(Column(1), &'-'));
+        let init_size = 3;
+        storage.initialize(init_size, &'-', Column(1));
 
         // Make sure the lines are present and at the right location
-        let shrinking_expected = Storage {
-            inner: vec![
-                Row::new(Column(1), &'4'),
-                Row::new(Column(1), &'5'),
-                Row::new(Column(1), &'-'),
-                Row::new(Column(1), &'-'),
-                Row::new(Column(1), &'-'),
-                Row::new(Column(1), &'0'),
-                Row::new(Column(1), &'1'),
-                Row::new(Column(1), &'2'),
-                Row::new(Column(1), &'3'),
-            ],
-            zero: 5,
+
+        let expected_init_size = std::cmp::max(init_size, MAX_CACHE_SIZE);
+        let mut expected_inner = vec![Row::new(Column(1), &'4'), Row::new(Column(1), &'5')];
+        expected_inner.append(&mut vec![Row::new(Column(1), &'-'); expected_init_size]);
+        expected_inner.append(&mut vec![
+            Row::new(Column(1), &'0'),
+            Row::new(Column(1), &'1'),
+            Row::new(Column(1), &'2'),
+            Row::new(Column(1), &'3'),
+        ]);
+        let expected_storage = Storage {
+            inner: expected_inner,
+            zero: 2 + expected_init_size,
             visible_lines: Line(0),
             len: 9,
         };
-        assert_eq!(storage.inner, shrinking_expected.inner);
-        assert_eq!(storage.zero, shrinking_expected.zero);
-        assert_eq!(storage.len, shrinking_expected.len);
+
+        assert_eq!(storage.inner, expected_storage.inner);
+        assert_eq!(storage.zero, expected_storage.zero);
+        assert_eq!(storage.len, expected_storage.len);
     }
 
     #[test]