Truncate invisible lines before storing ref-tests

Because there is no good way to store invisible lines in a backwards-
and forwards-compatible way, they buffer now gets truncated before
dumping the state of a grid when creating a ref-test.

This involved a few workaround of which a few required adding additional
methods which are only used in ref-tests, these should be minimal
though.

Since this required the creation of a truncation method anyways, some
logic has been added which automatically truncates the invisible buffer
when there are more than X (set to 100) invisible lines. This should not
impact performance because it rarely occurs, but it could save a bit of
memory when the history size is shrunk during runtime (see #1293).

This also adds an optional `config.json` file to the ref-test output
where it is possible to manually specify variables which should override
config defaults, this has been used only for history_size so far.

Creating a new ref-test does also still work, so there was no regression
here, if history size is altered, the config.json just has to be created
manually with the content `{"history_size":HIST_SIZE}`, where
`HIST_SIZE` is the desired history size.

6 files changed, 133 insertions, 11 deletions

diff --git a/src/event.rs b/src/event.rs
index 4d50efda..1cdf1302 100644
--- a/src/event.rs
+++ b/src/event.rs
@@ -267,7 +267,8 @@ impl<N: Notify> Processor<N> {
                     Closed => {
                         if ref_test {
                             // dump grid state
-                            let grid = processor.ctx.terminal.grid();
+                            let mut grid = processor.ctx.terminal.grid().clone();
+                            grid.truncate();
 
                             let serialized_grid = json::to_string(&grid)
                                 .expect("serialize grid");
diff --git a/src/grid/mod.rs b/src/grid/mod.rs
index 803f1e6e..0eea4201 100644
--- a/src/grid/mod.rs
+++ b/src/grid/mod.rs
@@ -407,6 +407,11 @@ impl<T> Grid<T> {
         self.raw.len()
     }
 
+    /// This is used only for truncating before saving ref-tests
+    pub fn truncate(&mut self) {
+        self.raw.truncate();
+    }
+
     pub fn iter_from(&self, point: Point<usize>) -> GridIterator<T> {
         GridIterator {
             grid: self,
diff --git a/src/grid/storage.rs b/src/grid/storage.rs
index f59b01b7..885cb94c 100644
--- a/src/grid/storage.rs
+++ b/src/grid/storage.rs
@@ -15,6 +15,9 @@ use std::ops::{Index, IndexMut};
 
 use index::Line;
 
+/// Maximum number of invisible lines before buffer is resized
+const TRUNCATE_STEP: usize = 100;
+
 #[derive(Clone, Debug, Deserialize, Serialize)]
 pub struct Storage<T> {
     inner: Vec<T>,
@@ -134,6 +137,32 @@ impl<T> Storage<T> {
 
         // Update visible lines
         self.visible_lines = next - 1;
+
+        // Free memory
+        if self.inner.len() > self.len() + TRUNCATE_STEP {
+            self.truncate();
+        }
+    }
+
+    /// Truncate the invisible elements from the raw buffer
+    pub fn truncate(&mut self) {
+        // Calculate shrinkage/offset for indexing
+        let offset = self.zero % self.inner.len();
+        let shrinkage = self.inner.len() - self.len;
+        let shrinkage_start = ::std::cmp::min(offset, shrinkage);
+
+        // Create two vectors with correct ordering
+        let mut split = self.inner.split_off(offset);
+
+        // Truncate the buffers
+        let len = self.inner.len();
+        let split_len = split.len();
+        self.inner.truncate(len - shrinkage_start);
+        split.truncate(split_len - (shrinkage - shrinkage_start));
+
+        // Merge buffers again and reset zero
+        self.zero = self.inner.len();
+        self.inner.append(&mut split);
     }
 
     #[inline]
@@ -411,3 +440,76 @@ fn shrink_before_and_after_zero() {
     assert_eq!(storage.zero, expected.zero);
     assert_eq!(storage.len, expected.len);
 }
+
+/// Check that when truncating all hidden lines are removed from the raw buffer
+///
+/// Before:
+///   0: 4 <- Hidden
+///   1: 5 <- Hidden
+///   2: 0 <- Zero
+///   3: 1
+///   4: 2 <- Hidden
+///   5: 3 <- Hidden
+/// After:
+///   0: 0 <- Zero
+///   1: 1
+#[test]
+fn truncate_invisible_lines() {
+    // Setup storage area
+    let mut storage = Storage {
+        inner: vec!["4", "5", "0", "1", "2", "3"],
+        zero: 2,
+        visible_lines: Line(1),
+        len: 2,
+    };
+
+    // Truncate buffer
+    storage.truncate();
+
+    // Make sure the result is correct
+    let expected = Storage {
+        inner: vec!["0", "1"],
+        zero: 0,
+        visible_lines: Line(1),
+        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);
+}
+
+/// Truncate buffer only at the beginning
+///
+/// Before:
+///   0: 1
+///   1: 2 <- Hidden
+///   2: 0 <- Zero
+/// After:
+///   0: 1
+///   0: 0 <- Zero
+#[test]
+fn truncate_invisible_lines_beginning() {
+    // Setup storage area
+    let mut storage = Storage {
+        inner: vec!["1", "2", "0"],
+        zero: 2,
+        visible_lines: Line(1),
+        len: 2,
+    };
+
+    // Truncate buffer
+    storage.truncate();
+
+    // Make sure the result is correct
+    let expected = Storage {
+        inner: vec!["1", "0"],
+        zero: 1,
+        visible_lines: Line(1),
+        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);
+}
diff --git a/tests/ref.rs b/tests/ref.rs
index 9ea0b80c..74cac6fa 100644
--- a/tests/ref.rs
+++ b/tests/ref.rs
@@ -1,5 +1,7 @@
-extern crate alacritty;
+#[macro_use]
+extern crate serde_derive;
 extern crate serde_json as json;
+extern crate alacritty;
 
 use std::fs::File;
 use std::io::{self, Read};
@@ -61,26 +63,32 @@ fn read_u8<P>(path: P) -> Vec<u8>
     res
 }
 
-fn read_string<P>(path: P) -> String
+fn read_string<P>(path: P) -> Result<String, ::std::io::Error>
     where P: AsRef<Path>
 {
     let mut res = String::new();
-    File::open(path.as_ref()).unwrap()
-        .read_to_string(&mut res).unwrap();
+    File::open(path.as_ref()).and_then(|mut f| f.read_to_string(&mut res))?;
 
-    res
+    Ok(res)
+}
+
+#[derive(Deserialize, Default)]
+struct RefConfig {
+    history_size: u32,
 }
 
 fn ref_test(dir: &Path) {
     let recording = read_u8(dir.join("alacritty.recording"));
-    let serialized_size = read_string(dir.join("size.json"));
-    let serialized_grid = read_string(dir.join("grid.json"));
+    let serialized_size = read_string(dir.join("size.json")).unwrap();
+    let serialized_grid = read_string(dir.join("grid.json")).unwrap();
+    let serialized_cfg = read_string(dir.join("config.json")).unwrap_or_default();
 
     let size: SizeInfo = json::from_str(&serialized_size).unwrap();
     let grid: Grid<Cell> = json::from_str(&serialized_grid).unwrap();
+    let ref_config: RefConfig = json::from_str(&serialized_cfg).unwrap_or_default();
 
     let mut config: Config = Default::default();
-    config.set_history((grid.len() - grid.num_lines().0) as u32);
+    config.set_history(ref_config.history_size);
 
     let mut terminal = Term::new(&config, size);
     let mut parser = ansi::Processor::new();
@@ -89,7 +97,11 @@ fn ref_test(dir: &Path) {
         parser.advance(&mut terminal, byte, &mut io::sink());
     }
 
-    if grid != *terminal.grid() {
+    // Truncate invisible lines from the grid
+    let mut term_grid = terminal.grid().clone();
+    term_grid.truncate();
+
+    if grid != term_grid {
         for i in 0..grid.len() {
             for j in 0..grid.num_cols().0 {
                 let cell = terminal.grid()[i][Column(j)];
@@ -104,5 +116,5 @@ fn ref_test(dir: &Path) {
         panic!("Ref test failed; grid doesn't match");
     }
 
-    assert_eq!(grid, *terminal.grid());
+    assert_eq!(grid, term_grid);
 }
diff --git a/tests/ref/grid_reset/config.json b/tests/ref/grid_reset/config.json
new file mode 100644
index 00000000..e794493c
--- /dev/null
+++ b/tests/ref/grid_reset/config.json
@@ -0,0 +1 @@
+{"history_size":100}
diff --git a/tests/ref/history/config.json b/tests/ref/history/config.json
new file mode 100644
index 00000000..5cca8022
--- /dev/null
+++ b/tests/ref/history/config.json
@@ -0,0 +1 @@
+{"history_size":1000}