Improve the resizing implementation

Until now the resizing implementation with scrollback has been really
inefficient because it made use of APIs like `Vec::insert`. This has
been rewored with this commit.

A `len` property has been added to the `Storage` struct which keeps
track of the actual length of the raw buffer. This has changed both
shrinking and growing implementations.

With shrinking, no more lines are removed, only the `len` property is
updated to set all lines shrunk to an "invisible" state which cannot be
accessed from the outside, this effectively changes it to a O(1)
operation. The only issue with this would be memory consumption, but
since the maximum shrinkage is the number of lines on one screen, it
should be a rather small impacte (probabl <100 lines usually). If
desired it would be possible to change this to shrink the raw inner
buffer whenever there are more than X lines hidden.

Growing now works in a similar way to shrinking, if the "invisible"
lines are enough, no new lines are inserted but rather the invisible
buffer is made visible again. Otherwise the amount of lines that still
needs to be inserted is added to the raw buffer, but instead of the
inefficient `Vec::insert`, the `Vec::push` API is used now.

This fixes #1271.

2 files changed, 62 insertions, 48 deletions

diff --git a/src/grid/mod.rs b/src/grid/mod.rs
index f3c8ea79..87ac3d05 100644
--- a/src/grid/mod.rs
+++ b/src/grid/mod.rs
@@ -125,7 +125,7 @@ impl<T: Copy + Clone> Grid<T> {
         // TODO (jwilm) Allocating each line at this point is expensive and
         // delays startup. A nice solution might be having `Row` delay
         // allocation until it's actually used.
-        for _ in 0..raw.capacity() {
+        for _ in 0..raw.len() {
             raw.push(Row::new(cols, &template));
         }
 
diff --git a/src/grid/storage.rs b/src/grid/storage.rs
index 323d8ec4..a50e8076 100644
--- a/src/grid/storage.rs
+++ b/src/grid/storage.rs
@@ -20,6 +20,8 @@ pub struct Storage<T> {
     inner: Vec<T>,
     zero: usize,
     visible_lines: Line,
+    #[serde(skip)]
+    len: usize,
 }
 
 impl<T: PartialEq> ::std::cmp::PartialEq for Storage<T> {
@@ -70,58 +72,49 @@ impl<T> Storage<T> {
             inner: Vec::with_capacity(cap),
             zero: 0,
             visible_lines: lines - 1,
+            len: cap,
         }
     }
 
-    #[inline]
-    pub fn capacity(&self) -> usize {
-        self.inner.capacity()
-    }
-
     /// Increase the number of lines in the buffer
     pub fn grow_visible_lines(&mut self, next: Line, template_row: T)
     where
         T: Clone,
     {
-        // Calculate insert position (before the first line)
-        let offset = self.zero % self.inner.len();
-
-        // Insert new template row for every line grown
+        // Number of lines the buffer needs to grow
         let lines_to_grow = (next - (self.visible_lines + 1)).0;
-        for _ in 0..lines_to_grow {
-            self.inner.insert(offset, template_row.clone());
-        }
 
-        // Set zero to old zero + lines grown
-        self.zero = offset + lines_to_grow;
+        // Only grow if there are not enough lines still hidden
+        if lines_to_grow > (self.inner.len() - self.len) {
+            // Lines to grow additionally to invisible lines
+            let new_lines_to_grow = lines_to_grow - (self.inner.len() - self.len);
 
-        // Update visible lines
-        self.visible_lines = next - 1;
-    }
+            // Get the position of the start of the buffer
+            let offset = self.zero % self.inner.len();
 
-    /// Decrease the number of lines in the buffer
-    pub fn shrink_visible_lines(&mut self, next: Line) {
-        // Calculate shrinkage and last line of buffer
-        let shrinkage = (self.visible_lines + 1 - next).0;
-        let offset = (self.zero + self.inner.len() - 1) % self.inner.len();
+            // Split off the beginning of the raw inner buffer
+            let mut start_buffer = self.inner.split_off(offset);
 
-        // Generate range of lines that have to be deleted before the zero line
-        let start = offset.saturating_sub(shrinkage - 1);
-        let shrink_before = start..(offset + 1);
+            // Insert new template rows at the end of the raw inner buffer
+            let mut new_lines = vec![template_row; new_lines_to_grow];
+            self.inner.append(&mut new_lines);
 
-        // Generate range of lines that have to be deleted after the zero line
-        let shrink_after = (self.inner.len() + offset + 1 - shrinkage)..self.inner.len();
+            // Add the start to the raw inner buffer again
+            self.inner.append(&mut start_buffer);
 
-        // Delete all lines in reverse order
-        for i in shrink_before.chain(shrink_after).rev() {
-            self.inner.remove(i);
+            // Update the zero to after the lines we just inserted
+            self.zero = offset + lines_to_grow;
         }
 
-        // Check if zero has moved (not the first line in the buffer)
-        if self.zero % (self.inner.len() + shrinkage) != 0 {
-            // Set zero to the first deleted line in the buffer
-            self.zero = start;
-        }
+        // Update visible lines and raw buffer length
+        self.len += lines_to_grow;
+        self.visible_lines = next - 1;
+    }
+
+    /// Decrease the number of lines in the buffer
+    pub fn shrink_visible_lines(&mut self, next: Line) {
+        // Shrink the size without removing any lines
+        self.len -= (self.visible_lines - (next - 1)).0;
 
         // Update visible lines
         self.visible_lines = next - 1;
@@ -134,17 +127,17 @@ impl<T> Storage<T> {
 
     #[inline]
     pub fn len(&self) -> usize {
-        self.inner.len()
+        self.len
     }
 
     /// Compute actual index in underlying storage given the requested index.
     #[inline]
     fn compute_index(&self, requested: usize) -> usize {
-        (requested + self.zero) % self.len()
+        (requested + self.zero) % self.inner.len()
     }
 
     fn compute_line_index(&self, requested: Line) -> usize {
-        ((self.len() + self.zero + *self.visible_lines) - *requested) % self.len()
+        ((self.inner.len() + self.zero + *self.visible_lines) - *requested) % self.inner.len()
     }
 
     pub fn swap_lines(&mut self, a: Line, b: Line) {
@@ -158,14 +151,14 @@ impl<T> Storage<T> {
     }
 
     pub fn rotate(&mut self, count: isize) {
-        let len = self.len();
+        let len = self.inner.len();
         assert!(count.abs() as usize <= len);
         self.zero += (count + len as isize) as usize % len;
     }
 
     // Fast path
     pub fn rotate_up(&mut self, count: usize) {
-        self.zero = (self.zero + count) % self.len();
+        self.zero = (self.zero + count) % self.inner.len();
     }
 }
 
@@ -243,6 +236,7 @@ fn grow_after_zero() {
         inner: vec!["0", "1", "-"],
         zero: 0,
         visible_lines: Line(2),
+        len: 3,
     };
 
     // Grow buffer
@@ -253,9 +247,11 @@ fn grow_after_zero() {
         inner: vec!["-", "0", "1", "-"],
         zero: 1,
         visible_lines: Line(0),
+        len: 4,
     };
     assert_eq!(storage.inner, expected.inner);
     assert_eq!(storage.zero, expected.zero);
+    assert_eq!(storage.len, expected.len);
 }
 
 /// Grow the buffer one line at the start of the buffer
@@ -276,6 +272,7 @@ fn grow_before_zero() {
         inner: vec!["-", "0", "1"],
         zero: 1,
         visible_lines: Line(2),
+        len: 3,
     };
 
     // Grow buffer
@@ -286,9 +283,11 @@ fn grow_before_zero() {
         inner: vec!["-", "-", "0", "1"],
         zero: 2,
         visible_lines: Line(0),
+        len: 4,
     };
     assert_eq!(storage.inner, expected.inner);
     assert_eq!(storage.zero, expected.zero);
+    assert_eq!(storage.len, expected.len);
 }
 
 /// Shrink the buffer one line at the start of the buffer
@@ -298,6 +297,7 @@ fn grow_before_zero() {
 ///   1: 0 <- Zero
 ///   2: 1
 /// After:
+///   0: 2 <- Hidden
 ///   0: 0 <- Zero
 ///   1: 1
 #[test]
@@ -307,6 +307,7 @@ fn shrink_before_zero() {
         inner: vec!["2", "0", "1"],
         zero: 1,
         visible_lines: Line(2),
+        len: 3,
     };
 
     // Shrink buffer
@@ -314,12 +315,14 @@ fn shrink_before_zero() {
 
     // Make sure the result is correct
     let expected = Storage {
-        inner: vec!["0", "1"],
-        zero: 0,
+        inner: vec!["2", "0", "1"],
+        zero: 1,
         visible_lines: Line(0),
+        len: 2,
     };
     assert_eq!(storage.inner, expected.inner);
     assert_eq!(storage.zero, expected.zero);
+    assert_eq!(storage.len, expected.len);
 }
 
 /// Shrink the buffer one line at the end of the buffer
@@ -331,6 +334,7 @@ fn shrink_before_zero() {
 /// After:
 ///   0: 0 <- Zero
 ///   1: 1
+///   2: 2 <- Hidden
 #[test]
 fn shrink_after_zero() {
     // Setup storage area
@@ -338,6 +342,7 @@ fn shrink_after_zero() {
         inner: vec!["0", "1", "2"],
         zero: 0,
         visible_lines: Line(2),
+        len: 3,
     };
 
     // Shrink buffer
@@ -345,12 +350,14 @@ fn shrink_after_zero() {
 
     // Make sure the result is correct
     let expected = Storage {
-        inner: vec!["0", "1"],
+        inner: vec!["0", "1", "2"],
         zero: 0,
         visible_lines: Line(0),
+        len: 2,
     };
     assert_eq!(storage.inner, expected.inner);
     assert_eq!(storage.zero, expected.zero);
+    assert_eq!(storage.len, expected.len);
 }
 
 /// Shrink the buffer at the start and end of the buffer
@@ -363,8 +370,12 @@ fn shrink_after_zero() {
 ///   4: 2
 ///   5: 3
 /// After:
-///   0: 0 <- Zero
-///   1: 1
+///   0: 4 <- Hidden
+///   1: 5 <- Hidden
+///   2: 0 <- Zero
+///   3: 1
+///   4: 2 <- Hidden
+///   5: 3 <- Hidden
 #[test]
 fn shrink_before_and_after_zero() {
     // Setup storage area
@@ -372,6 +383,7 @@ fn shrink_before_and_after_zero() {
         inner: vec!["4", "5", "0", "1", "2", "3"],
         zero: 2,
         visible_lines: Line(5),
+        len: 6,
     };
 
     // Shrink buffer
@@ -379,10 +391,12 @@ fn shrink_before_and_after_zero() {
 
     // Make sure the result is correct
     let expected = Storage {
-        inner: vec!["0", "1"],
-        zero: 0,
+        inner: vec!["4", "5", "0", "1", "2", "3"],
+        zero: 2,
         visible_lines: Line(0),
+        len: 2,
     };
     assert_eq!(storage.inner, expected.inner);
     assert_eq!(storage.zero, expected.zero);
+    assert_eq!(storage.len, expected.len);
 }