Merge branch 'master' into glutin-0.17-upgrade

4 files changed, 1774 insertions, 0 deletions

diff --git a/src/grid/mod.rs b/src/grid/mod.rs
new file mode 100644
index 00000000..680aa7bd
--- /dev/null
+++ b/src/grid/mod.rs
@@ -0,0 +1,780 @@
+// Copyright 2016 Joe Wilm, The Alacritty Project Contributors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+//! A specialized 2d grid implementation optimized for use in a terminal.
+
+use std::cmp::{min, max, Ordering};
+use std::ops::{Deref, Range, Index, IndexMut, RangeTo, RangeFrom, RangeFull};
+
+use index::{self, Point, Line, Column, IndexRange};
+use selection::Selection;
+
+mod row;
+pub use self::row::Row;
+
+#[cfg(test)]
+mod tests;
+
+mod storage;
+use self::storage::Storage;
+
+/// Bidirection iterator
+pub trait BidirectionalIterator: Iterator {
+    fn prev(&mut self) -> Option<Self::Item>;
+}
+
+/// An item in the grid along with its Line and Column.
+pub struct Indexed<T> {
+    pub inner: T,
+    pub line: Line,
+    pub column: Column,
+}
+
+impl<T> Deref for Indexed<T> {
+    type Target = T;
+
+    #[inline]
+    fn deref(&self) -> &T {
+        &self.inner
+    }
+}
+
+impl<T: PartialEq> ::std::cmp::PartialEq for Grid<T> {
+    fn eq(&self, other: &Self) -> bool {
+        // Compare struct fields and check result of grid comparison
+        self.raw.eq(&other.raw) &&
+            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)
+    }
+}
+
+/// Represents the terminal display contents
+#[derive(Clone, Debug, Deserialize, Serialize)]
+pub struct Grid<T> {
+    /// Lines in the grid. Each row holds a list of cells corresponding to the
+    /// columns in that row.
+    raw: Storage<T>,
+
+    /// Number of columns
+    cols: index::Column,
+
+    /// Number of lines.
+    ///
+    /// Invariant: lines is equivalent to raw.len()
+    lines: index::Line,
+
+    /// 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.
+    #[serde(default)]
+    display_offset: usize,
+
+    /// An limit on how far back it's possible to scroll
+    #[serde(default)]
+    scroll_limit: usize,
+
+    /// Selected region
+    #[serde(skip)]
+    pub selection: Option<Selection>,
+}
+
+pub struct GridIterator<'a, T: 'a> {
+    /// Immutable grid reference
+    grid: &'a Grid<T>,
+
+    /// Current position of the iterator within the grid.
+    pub cur: Point<usize>,
+}
+
+#[derive(Copy, Clone)]
+pub enum Scroll {
+    Lines(isize),
+    PageUp,
+    PageDown,
+    Top,
+    Bottom,
+}
+
+impl<T: Copy + Clone> Grid<T> {
+    pub fn new(lines: index::Line, cols: index::Column, scrollback: usize, template: T) -> Grid<T> {
+        let raw = Storage::with_capacity(*lines + scrollback, lines, Row::new(cols, &template));
+        Grid {
+            raw,
+            cols,
+            lines,
+            display_offset: 0,
+            scroll_limit: 0,
+            selection: None,
+        }
+    }
+
+    pub fn visible_to_buffer(&self, point: Point) -> Point<usize> {
+        Point {
+            line: self.visible_line_to_buffer(point.line),
+            col: point.col
+        }
+    }
+
+    pub fn buffer_to_visible(&self, point: Point<usize>) -> Point {
+        Point {
+            line: self.buffer_line_to_visible(point.line).expect("Line not visible"),
+            col: point.col
+        }
+    }
+
+    pub fn buffer_line_to_visible(&self, line: usize) -> Option<Line> {
+        if line >= self.display_offset {
+            self.offset_to_line(line - self.display_offset)
+        } else {
+            None
+        }
+    }
+
+    pub fn visible_line_to_buffer(&self, line: Line) -> usize {
+        self.line_to_offset(line) + self.display_offset
+    }
+
+    /// 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));
+        self.scroll_limit = min(self.scroll_limit, history_size);
+    }
+
+    pub fn scroll_display(&mut self, scroll: Scroll) {
+        match scroll {
+            Scroll::Lines(count) => {
+                self.display_offset = min(
+                    max((self.display_offset as isize) + count, 0isize) as usize,
+                    self.scroll_limit
+                );
+            },
+            Scroll::PageUp => {
+                self.display_offset = min(
+                    self.display_offset + self.lines.0,
+                    self.scroll_limit
+                );
+            },
+            Scroll::PageDown => {
+                self.display_offset -= min(
+                    self.display_offset,
+                    self.lines.0
+                );
+            },
+            Scroll::Top => self.display_offset = self.scroll_limit,
+            Scroll::Bottom => self.display_offset = 0,
+        }
+    }
+
+    pub fn resize(
+        &mut self,
+        lines: index::Line,
+        cols: index::Column,
+        template: &T,
+    ) {
+        // Check that there's actually work to do and return early if not
+        if lines == self.lines && cols == self.cols {
+            return;
+        }
+
+        match self.lines.cmp(&lines) {
+            Ordering::Less => self.grow_lines(lines, template),
+            Ordering::Greater => self.shrink_lines(lines),
+            Ordering::Equal => (),
+        }
+
+        match self.cols.cmp(&cols) {
+            Ordering::Less => self.grow_cols(cols, template),
+            Ordering::Greater => self.shrink_cols(cols),
+            Ordering::Equal => (),
+        }
+    }
+
+    fn increase_scroll_limit(&mut self, count: usize) {
+        self.scroll_limit = min(
+            self.scroll_limit + count,
+            self.raw.len().saturating_sub(*self.lines),
+        );
+    }
+
+    fn decrease_scroll_limit(&mut self, count: usize) {
+        self.scroll_limit = self.scroll_limit.saturating_sub(count);
+    }
+
+    /// Add lines to the visible area
+    ///
+    /// Alacritty keeps the cursor at the bottom of the terminal as long as there
+    /// is scrollback available. Once scrollback is exhausted, new lines are
+    /// simply added to the bottom of the screen.
+    fn grow_lines(
+        &mut self,
+        new_line_count: index::Line,
+        template: &T,
+    ) {
+        let lines_added = new_line_count - self.lines;
+
+        // Need to "resize" before updating buffer
+        self.raw.grow_visible_lines(new_line_count, Row::new(self.cols, template));
+        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);
+        }
+
+        self.scroll_limit = self.scroll_limit.saturating_sub(*lines_added);
+    }
+
+    fn grow_cols(&mut self, cols: index::Column, template: &T) {
+        for row in self.raw.iter_mut_raw() {
+            row.grow(cols, template);
+        }
+
+        // Update self cols
+        self.cols = cols;
+    }
+
+    fn shrink_cols(&mut self, cols: index::Column) {
+        for row in self.raw.iter_mut_raw() {
+            row.shrink(cols);
+        }
+
+        self.cols = cols;
+    }
+
+    /// Remove lines from the visible area
+    ///
+    /// The behavior in Terminal.app and iTerm.app is to keep the cursor at the
+    /// bottom of the screen. This is achieved by pushing history "out the top"
+    /// of the terminal window.
+    ///
+    /// Alacritty takes the same approach.
+    fn shrink_lines(&mut self, target: index::Line) {
+        let prev = self.lines;
+
+        self.selection = None;
+        self.raw.rotate(*prev as isize - *target as isize);
+        self.raw.shrink_visible_lines(target);
+        self.lines = target;
+    }
+
+    /// Convert a Line index (active region) to a buffer offset
+    ///
+    /// # Panics
+    ///
+    /// This method will panic if `Line` is larger than the grid dimensions
+    pub fn line_to_offset(&self, line: index::Line) -> usize {
+        assert!(line < self.num_lines());
+
+        *(self.num_lines() - line - 1)
+    }
+
+    pub fn offset_to_line(&self, offset: usize) -> Option<Line> {
+        if offset < *self.num_lines() {
+            Some(self.lines - offset - 1)
+        } else {
+            None
+        }
+    }
+
+    #[inline]
+    pub fn scroll_down(
+        &mut self,
+        region: &Range<index::Line>,
+        positions: index::Line,
+        template: &T,
+    ) {
+        // Whether or not there is a scrolling region active, as long as it
+        // starts at the top, we can do a full rotation which just involves
+        // changing the start index.
+        //
+        // To accomodate scroll regions, rows are reordered at the end.
+        if region.start == Line(0) {
+            // Rotate the entire line buffer. If there's a scrolling region
+            // active, the bottom lines are restored in the next step.
+            self.raw.rotate_up(*positions);
+            if let Some(ref mut selection) = self.selection {
+                selection.rotate(-(*positions as isize));
+            }
+
+            self.decrease_scroll_limit(*positions);
+
+            // Now, restore any scroll region lines
+            let lines = self.lines;
+            for i in IndexRange(region.end .. lines) {
+                self.raw.swap_lines(i, i + positions);
+            }
+
+            // Finally, reset recycled lines
+            for i in IndexRange(Line(0)..positions) {
+                self.raw[i].reset(&template);
+            }
+        } else {
+            // Subregion rotation
+            for line in IndexRange((region.start + positions)..region.end).rev() {
+                self.raw.swap_lines(line, line - positions);
+            }
+
+            for line in IndexRange(region.start .. (region.start + positions)) {
+                self.raw[line].reset(&template);
+            }
+        }
+    }
+
+    /// scroll_up moves lines at the bottom towards the top
+    ///
+    /// This is the performance-sensitive part of scrolling.
+    pub fn scroll_up(
+        &mut self,
+        region: &Range<index::Line>,
+        positions: index::Line,
+        template: &T
+    ) {
+        if region.start == Line(0) {
+            // Update display offset when not pinned to active area
+            if self.display_offset != 0 {
+                self.display_offset = min(
+                    self.display_offset + *positions,
+                    self.len() - self.num_lines().0,
+                );
+            }
+
+            self.increase_scroll_limit(*positions);
+
+            // Rotate the entire line buffer. If there's a scrolling region
+            // active, the bottom lines are restored in the next step.
+            self.raw.rotate(-(*positions as isize));
+            if let Some(ref mut selection) = self.selection {
+                selection.rotate(*positions as isize);
+            }
+
+            // // This next loop swaps "fixed" lines outside of a scroll region
+            // // back into place after the rotation. The work is done in buffer-
+            // // space rather than terminal-space to avoid redundant
+            // // transformations.
+            let fixed_lines = *self.num_lines() - *region.end;
+
+            for i in 0..fixed_lines {
+                self.raw.swap(i, i + *positions);
+            }
+
+            // Finally, reset recycled lines
+            //
+            // Recycled lines are just above the end of the scrolling region.
+            for i in 0..*positions {
+                self.raw[i + fixed_lines].reset(&template);
+            }
+        } else {
+            // Subregion rotation
+            for line in IndexRange(region.start..(region.end - positions)) {
+                self.raw.swap_lines(line, line + positions);
+            }
+
+            // Clear reused lines
+            for line in IndexRange((region.end - positions) .. region.end) {
+                self.raw[line].reset(&template);
+            }
+        }
+    }
+}
+
+#[cfg_attr(feature = "cargo-clippy", allow(len_without_is_empty))]
+impl<T> Grid<T> {
+    #[inline]
+    pub fn num_lines(&self) -> index::Line {
+        self.lines
+    }
+
+    pub fn display_iter(&self) -> DisplayIter<T> {
+        DisplayIter::new(self)
+    }
+
+    #[inline]
+    pub fn num_cols(&self) -> index::Column {
+        self.cols
+    }
+
+    pub fn clear_history(&mut self) {
+        self.scroll_limit = 0;
+    }
+
+    #[inline]
+    pub fn scroll_limit(&self) -> usize {
+        self.scroll_limit
+    }
+
+    /// Total number of lines in the buffer, this includes scrollback + visible lines
+    #[inline]
+    pub fn len(&self) -> usize {
+        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,
+            cur: point,
+        }
+    }
+
+    #[inline]
+    pub fn contains(&self, point: &Point) -> bool {
+        self.lines > point.line && self.cols > point.col
+    }
+}
+
+impl<'a, T> Iterator for GridIterator<'a, T> {
+    type Item = &'a T;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        let last_col = self.grid.num_cols() - Column(1);
+        match self.cur {
+            Point { line, col } if line == 0 && col == last_col => None,
+            Point { col, .. } if
+                (col == last_col) => {
+                self.cur.line -= 1;
+                self.cur.col = Column(0);
+                Some(&self.grid[self.cur.line][self.cur.col])
+            },
+            _ => {
+                self.cur.col += Column(1);
+                Some(&self.grid[self.cur.line][self.cur.col])
+            }
+        }
+    }
+}
+
+impl<'a, T> BidirectionalIterator for GridIterator<'a, T> {
+    fn prev(&mut self) -> Option<Self::Item> {
+        let num_cols = self.grid.num_cols();
+
+        match self.cur {
+            Point { line, col: Column(0) } if line == self.grid.len() - 1 => None,
+            Point { col: Column(0), .. } => {
+                self.cur.line += 1;
+                self.cur.col = num_cols - Column(1);
+                Some(&self.grid[self.cur.line][self.cur.col])
+            },
+            _ => {
+                self.cur.col -= Column(1);
+                Some(&self.grid[self.cur.line][self.cur.col])
+            }
+        }
+    }
+}
+
+/// Index active region by line
+impl<T> Index<index::Line> for Grid<T> {
+    type Output = Row<T>;
+
+    #[inline]
+    fn index(&self, index: index::Line) -> &Row<T> {
+        &self.raw[index]
+    }
+}
+
+/// Index with buffer offset
+impl<T> Index<usize> for Grid<T> {
+    type Output = Row<T>;
+
+    #[inline]
+    fn index(&self, index: usize) -> &Row<T> {
+        &self.raw[index]
+    }
+}
+
+impl<T> IndexMut<index::Line> for Grid<T> {
+    #[inline]
+    fn index_mut(&mut self, index: index::Line) -> &mut Row<T> {
+        &mut self.raw[index]
+    }
+}
+
+impl<'point, T> Index<&'point Point> for Grid<T> {
+    type Output = T;
+
+    #[inline]
+    fn index<'a>(&'a self, point: &Point) -> &'a T {
+        &self[point.line][point.col]
+    }
+}
+
+impl<'point, T> IndexMut<&'point Point> for Grid<T> {
+    #[inline]
+    fn index_mut<'a, 'b>(&'a mut self, point: &'b Point) -> &'a mut T {
+        &mut self[point.line][point.col]
+    }
+}
+
+// -------------------------------------------------------------------------------------------------
+// REGIONS
+// -------------------------------------------------------------------------------------------------
+
+/// A subset of lines in the grid
+///
+/// May be constructed using Grid::region(..)
+pub struct Region<'a, T: 'a> {
+    start: Line,
+    end: Line,
+    raw: &'a Storage<T>,
+}
+
+/// A mutable subset of lines in the grid
+///
+/// May be constructed using Grid::region_mut(..)
+pub struct RegionMut<'a, T: 'a> {
+    start: Line,
+    end: Line,
+    raw: &'a mut Storage<T>,
+}
+
+impl<'a, T> RegionMut<'a, T> {
+    /// Call the provided function for every item in this region
+    pub fn each<F: Fn(&mut T)>(self, func: F) {
+        for row in self {
+            for item in row {
+                func(item)
+            }
+        }
+    }
+}
+
+pub trait IndexRegion<I, T> {
+    /// Get an immutable region of Self
+    fn region(&self, _: I) -> Region<T>;
+
+    /// Get a mutable region of Self
+    fn region_mut(&mut self, _: I) -> RegionMut<T>;
+}
+
+impl<T> IndexRegion<Range<Line>, T> for Grid<T> {
+    fn region(&self, index: Range<Line>) -> Region<T> {
+        assert!(index.start < self.num_lines());
+        assert!(index.end <= self.num_lines());
+        assert!(index.start <= index.end);
+        Region {
+            start: index.start,
+            end: index.end,
+            raw: &self.raw
+        }
+    }
+    fn region_mut(&mut self, index: Range<Line>) -> RegionMut<T> {
+        assert!(index.start < self.num_lines());
+        assert!(index.end <= self.num_lines());
+        assert!(index.start <= index.end);
+        RegionMut {
+            start: index.start,
+            end: index.end,
+            raw: &mut self.raw
+        }
+    }
+}
+
+impl<T> IndexRegion<RangeTo<Line>, T> for Grid<T> {
+    fn region(&self, index: RangeTo<Line>) -> Region<T> {
+        assert!(index.end <= self.num_lines());
+        Region {
+            start: Line(0),
+            end: index.end,
+            raw: &self.raw
+        }
+    }
+    fn region_mut(&mut self, index: RangeTo<Line>) -> RegionMut<T> {
+        assert!(index.end <= self.num_lines());
+        RegionMut {
+            start: Line(0),
+            end: index.end,
+            raw: &mut self.raw
+        }
+    }
+}
+
+impl<T> IndexRegion<RangeFrom<Line>, T> for Grid<T> {
+    fn region(&self, index: RangeFrom<Line>) -> Region<T> {
+        assert!(index.start < self.num_lines());
+        Region {
+            start: index.start,
+            end: self.num_lines(),
+            raw: &self.raw
+        }
+    }
+    fn region_mut(&mut self, index: RangeFrom<Line>) -> RegionMut<T> {
+        assert!(index.start < self.num_lines());
+        RegionMut {
+            start: index.start,
+            end: self.num_lines(),
+            raw: &mut self.raw
+        }
+    }
+}
+
+impl<T> IndexRegion<RangeFull, T> for Grid<T> {
+    fn region(&self, _: RangeFull) -> Region<T> {
+        Region {
+            start: Line(0),
+            end: self.num_lines(),
+            raw: &self.raw
+        }
+    }
+
+    fn region_mut(&mut self, _: RangeFull) -> RegionMut<T> {
+        RegionMut {
+            start: Line(0),
+            end: self.num_lines(),
+            raw: &mut self.raw
+        }
+    }
+}
+
+pub struct RegionIter<'a, T: 'a> {
+    end: Line,
+    cur: Line,
+    raw: &'a Storage<T>,
+}
+
+pub struct RegionIterMut<'a, T: 'a> {
+    end: Line,
+    cur: Line,
+    raw: &'a mut Storage<T>,
+}
+
+impl<'a, T> IntoIterator for Region<'a, T> {
+    type Item = &'a Row<T>;
+    type IntoIter = RegionIter<'a, T>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        RegionIter {
+            end: self.end,
+            cur: self.start,
+            raw: self.raw
+        }
+    }
+}
+
+impl<'a, T> IntoIterator for RegionMut<'a, T> {
+    type Item = &'a mut Row<T>;
+    type IntoIter = RegionIterMut<'a, T>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        RegionIterMut {
+            end: self.end,
+            cur: self.start,
+            raw: self.raw
+        }
+    }
+}
+
+impl<'a, T> Iterator for RegionIter<'a, T> {
+    type Item = &'a Row<T>;
+    fn next(&mut self) -> Option<Self::Item> {
+        if self.cur < self.end {
+            let index = self.cur;
+            self.cur += 1;
+            Some(&self.raw[index])
+        } else {
+            None
+        }
+    }
+}
+
+impl<'a, T> Iterator for RegionIterMut<'a, T> {
+    type Item = &'a mut Row<T>;
+    fn next(&mut self) -> Option<Self::Item> {
+        if self.cur < self.end {
+            let index = self.cur;
+            self.cur += 1;
+            unsafe {
+                Some(&mut *(&mut self.raw[index] as *mut _))
+            }
+        } else {
+            None
+        }
+    }
+}
+
+// -------------------------------------------------------------------------------------------------
+// DISPLAY ITERATOR
+// -------------------------------------------------------------------------------------------------
+
+/// Iterates over the visible area accounting for buffer transform
+pub struct DisplayIter<'a, T: 'a> {
+    grid: &'a Grid<T>,
+    offset: usize,
+    limit: usize,
+    col: Column,
+    line: Line,
+}
+
+impl<'a, T: 'a> DisplayIter<'a, T> {
+    pub fn new(grid: &'a Grid<T>) -> DisplayIter<'a, T> {
+        let offset = grid.display_offset + *grid.num_lines() - 1;
+        let limit =  grid.display_offset;
+        let col = Column(0);
+        let line = Line(0);
+
+        DisplayIter { grid, offset, col, limit, line }
+    }
+
+    pub fn offset(&self) -> usize {
+        self.offset
+    }
+
+    pub fn column(&self) -> Column {
+        self.col
+    }
+
+    pub fn line(&self) -> Line {
+        self.line
+    }
+}
+
+impl<'a, T: Copy + 'a> Iterator for DisplayIter<'a, T> {
+    type Item = Indexed<T>;
+
+    #[inline]
+    fn next(&mut self) -> Option<Self::Item> {
+        // Return None if we've reached the end.
+        if self.offset == self.limit && self.grid.num_cols() == self.col {
+            return None;
+        }
+
+        // Get the next item.
+        let item = Some(Indexed {
+            inner: self.grid.raw[self.offset][self.col],
+            line: self.line,
+            column: self.col
+        });
+
+        // Update line/col to point to next item
+        self.col += 1;
+        if self.col == self.grid.num_cols() && self.offset != self.limit {
+            self.offset -= 1;
+
+            self.col = Column(0);
+            self.line = Line(*self.grid.lines - 1 - (self.offset - self.limit));
+        }
+
+        item
+    }
+}
diff --git a/src/grid/row.rs b/src/grid/row.rs
new file mode 100644
index 00000000..69a4f2b2
--- /dev/null
+++ b/src/grid/row.rs
@@ -0,0 +1,202 @@
+// Copyright 2016 Joe Wilm, The Alacritty Project Contributors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+//! Defines the Row type which makes up lines in the grid
+
+use std::ops::{Index, IndexMut};
+use std::ops::{Range, RangeTo, RangeFrom, RangeFull};
+use std::cmp::{max, min};
+use std::slice;
+
+use index::Column;
+
+/// A row in the grid
+#[derive(Default, Clone, Debug, Serialize, Deserialize)]
+pub struct Row<T> {
+    inner: Vec<T>,
+
+    /// occupied entries
+    ///
+    /// Semantically, this value can be understood as the **end** of an
+    /// Exclusive Range. Thus,
+    ///
+    /// - Zero means there are no occupied entries
+    /// - 1 means there is a value at index zero, but nowhere else
+    /// - `occ == inner.len` means every value is occupied
+    pub(crate) occ: usize,
+}
+
+impl<T: PartialEq> PartialEq for Row<T> {
+    fn eq(&self, other: &Self) -> bool {
+        self.inner == other.inner
+    }
+}
+
+impl<T: Copy + Clone> Row<T> {
+    pub fn new(columns: Column, template: &T) -> Row<T> {
+        Row {
+            inner: vec![*template; *columns],
+            occ: 0,
+        }
+    }
+
+    pub fn grow(&mut self, cols: Column, template: &T) {
+        assert!(self.len() < * cols);
+
+        while self.len() != *cols {
+            self.inner.push(*template);
+        }
+    }
+
+    /// Resets contents to the contents of `other`
+    #[inline(never)]
+    pub fn reset(&mut self, other: &T) {
+        let occ = self.occ;
+        for item in &mut self.inner[..occ] {
+            *item = *other;
+        }
+
+        self.occ = 0;
+    }
+}
+
+#[cfg_attr(feature = "cargo-clippy", allow(len_without_is_empty))]
+impl<T> Row<T> {
+    pub fn shrink(&mut self, cols: Column) {
+        while self.len() != *cols {
+            self.inner.pop();
+        }
+
+        self.occ = min(self.occ, *cols);
+    }
+
+    pub fn len(&self) -> usize {
+        self.inner.len()
+    }
+
+    pub fn iter(&self) -> slice::Iter<T> {
+        self.inner.iter()
+    }
+}
+
+
+impl<'a, T> IntoIterator for &'a Row<T> {
+    type Item = &'a T;
+    type IntoIter = slice::Iter<'a, T>;
+
+    #[inline]
+    fn into_iter(self) -> slice::Iter<'a, T> {
+        self.iter()
+    }
+}
+
+impl<'a, T> IntoIterator for &'a mut Row<T> {
+    type Item = &'a mut T;
+    type IntoIter = slice::IterMut<'a, T>;
+
+    #[inline]
+    fn into_iter(self) -> slice::IterMut<'a, T> {
+        self.occ = self.len();
+        self.inner.iter_mut()
+    }
+}
+
+impl<T> Index<Column> for Row<T> {
+    type Output = T;
+
+    #[inline]
+    fn index(&self, index: Column) -> &T {
+        &self.inner[index.0]
+    }
+}
+
+impl<T> IndexMut<Column> for Row<T> {
+    #[inline]
+    fn index_mut(&mut self, index: Column) -> &mut T {
+        self.occ = max(self.occ, *index + 1);
+        &mut self.inner[index.0]
+    }
+}
+
+// -----------------------------------------------------------------------------
+// Index ranges of columns
+// -----------------------------------------------------------------------------
+
+impl<T> Index<Range<Column>> for Row<T> {
+    type Output = [T];
+
+    #[inline]
+    fn index(&self, index: Range<Column>) -> &[T] {
+        &self.inner[(index.start.0)..(index.end.0)]
+    }
+}
+
+impl<T> IndexMut<Range<Column>> for Row<T> {
+    #[inline]
+    fn index_mut(&mut self, index: Range<Column>) -> &mut [T] {
+        self.occ = max(self.occ, *index.end);
+        &mut self.inner[(index.start.0)..(index.end.0)]
+    }
+}
+
+impl<T> Index<RangeTo<Column>> for Row<T> {
+    type Output = [T];
+
+    #[inline]
+    fn index(&self, index: RangeTo<Column>) -> &[T] {
+        &self.inner[..(index.end.0)]
+    }
+}
+
+impl<T> IndexMut<RangeTo<Column>> for Row<T> {
+    #[inline]
+    fn index_mut(&mut self, index: RangeTo<Column>) -> &mut [T] {
+        self.occ = max(self.occ, *index.end);
+        &mut self.inner[..(index.end.0)]
+    }
+}
+
+impl<T> Index<RangeFrom<Column>> for Row<T> {
+    type Output = [T];
+
+    #[inline]
+    fn index(&self, index: RangeFrom<Column>) -> &[T] {
+        &self.inner[(index.start.0)..]
+    }
+}
+
+impl<T> IndexMut<RangeFrom<Column>> for Row<T> {
+    #[inline]
+    fn index_mut(&mut self, index: RangeFrom<Column>) -> &mut [T] {
+        self.occ = self.len();
+        &mut self.inner[(index.start.0)..]
+    }
+}
+
+impl<T> Index<RangeFull> for Row<T> {
+    type Output = [T];
+
+    #[inline]
+    fn index(&self, _: RangeFull) -> &[T] {
+        &self.inner[..]
+    }
+}
+
+impl<T> IndexMut<RangeFull> for Row<T> {
+    #[inline]
+    fn index_mut(&mut self, _: RangeFull) -> &mut [T] {
+        self.occ = self.len();
+        &mut self.inner[..]
+    }
+}
diff --git a/src/grid/storage.rs b/src/grid/storage.rs
new file mode 100644
index 00000000..ad94cf2b
--- /dev/null
+++ b/src/grid/storage.rs
@@ -0,0 +1,651 @@
+/// Wrapper around Vec which supports fast indexing and rotation
+///
+/// The rotation implemented by grid::Storage is a simple integer addition.
+/// Compare with standard library rotation which requires rearranging items in
+/// memory.
+///
+/// As a consequence, the indexing operators need to be reimplemented for this
+/// type to account for the 0th element not always being at the start of the
+/// allocation.
+///
+/// Because certain Vec operations are no longer valid on this type, no Deref
+/// implementation is provided. Anything from Vec that should be exposed must be
+/// done so manually.
+use std::ops::{Index, IndexMut};
+use std::slice;
+
+use index::Line;
+use super::Row;
+
+/// 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<Row<T>>,
+    zero: usize,
+    visible_lines: Line,
+
+    /// Total number of lines currently active in the terminal (scrollback + visible)
+    ///
+    /// Shrinking this length allows reducing the number of lines in the scrollback buffer without
+    /// having to truncate the raw `inner` buffer.
+    /// As long as `len` is bigger than `inner`, it is also possible to grow the scrollback buffer
+    /// without any additional insertions.
+    #[serde(skip)]
+    len: usize,
+}
+
+impl<T: PartialEq> ::std::cmp::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)
+        };
+
+        // Calculate the actual zero offset
+        let len = self.inner.len();
+        let bigger_zero = bigger.zero % len;
+        let smaller_zero = smaller.zero % len;
+
+        // 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
+        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]
+    }
+}
+
+impl<T> Storage<T> {
+    #[inline]
+    pub fn with_capacity(cap: usize, lines: Line, template: Row<T>) -> Storage<T>
+    where
+        T: Clone,
+    {
+        // Allocate all lines in the buffer, including scrollback history
+        let inner = vec![template; cap];
+
+        Storage {
+            inner,
+            zero: 0,
+            visible_lines: lines - 1,
+            len: cap,
+        }
+    }
+
+    /// 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);
+        if history_size > current_history {
+            self.grow_lines(history_size - current_history, template_row);
+        } else if history_size < current_history {
+            self.shrink_lines(current_history - history_size);
+        }
+    }
+
+    /// 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);
+
+        // Update visible lines
+        self.visible_lines = next - 1;
+    }
+
+    /// 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,
+    {
+        // Only grow if there are not enough lines still hidden
+        let mut new_growage = 0;
+        if growage > (self.inner.len() - self.len) {
+            // Lines to grow additionally to invisible lines
+            new_growage = growage - (self.inner.len() - self.len);
+
+            // Split off the beginning of the raw inner buffer
+            let mut start_buffer = self.inner.split_off(self.zero);
+
+            // Insert new template rows at the end of the raw inner buffer
+            let mut new_lines = vec![template_row; new_growage];
+            self.inner.append(&mut new_lines);
+
+            // Add the start to the raw inner buffer again
+            self.inner.append(&mut start_buffer);
+        }
+
+        // Update raw buffer length and zero offset
+        self.zero = (self.zero + new_growage) % self.inner.len();
+        self.len += growage;
+    }
+
+    /// 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);
+
+        // Update visible lines
+        self.visible_lines = next - 1;
+    }
+
+    // Shrink the number of lines in the buffer
+    fn shrink_lines(&mut self, shrinkage: usize) {
+        self.len -= shrinkage;
+
+        // 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 shrinkage = self.inner.len() - self.len;
+        let shrinkage_start = ::std::cmp::min(self.zero, shrinkage);
+
+        // Create two vectors with correct ordering
+        let mut split = self.inner.split_off(self.zero);
+
+        // 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
+        split.append(&mut self.inner);
+        self.inner = split;
+        self.zero = 0;
+    }
+
+    #[inline]
+    pub fn len(&self) -> usize {
+        self.len
+    }
+
+    /// Compute actual index in underlying storage given the requested index.
+    fn compute_index(&self, requested: usize) -> usize {
+        debug_assert!(requested < self.len);
+        let zeroed = requested + self.zero;
+
+        // This part is critical for performance,
+        // so an if/else is used here instead of a moludo operation
+        if zeroed >= self.inner.len() {
+            zeroed - self.inner.len()
+        } else {
+            zeroed
+        }
+    }
+
+    pub fn swap_lines(&mut self, a: Line, b: Line) {
+        let offset = self.inner.len() + self.zero + *self.visible_lines;
+        let a = (offset - *a) % self.inner.len();
+        let b = (offset - *b) % self.inner.len();
+        self.inner.swap(a, b);
+    }
+
+    /// Swap implementation for Row<T>.
+    ///
+    /// Exploits the known size of Row<T> to produce a slightly more efficient
+    /// swap than going through slice::swap.
+    ///
+    /// The default implementation from swap generates 8 movups and 4 movaps
+    /// instructions. This implementation achieves the swap in only 8 movups
+    /// instructions.
+    pub fn swap(&mut self, a: usize, b: usize) {
+        assert_eq_size!(Row<T>, [u32; 8]);
+
+        let a = self.compute_index(a);
+        let b = self.compute_index(b);
+
+        unsafe {
+            // Cast to a qword array to opt out of copy restrictions and avoid
+            // drop hazards. Byte array is no good here since for whatever
+            // reason LLVM won't optimized it.
+            let a_ptr = self.inner.as_mut_ptr().offset(a as isize) as *mut u64;
+            let b_ptr = self.inner.as_mut_ptr().offset(b as isize) as *mut u64;
+
+            // Copy 1 qword at a time
+            //
+            // The optimizer unrolls this loop and vectorizes it.
+            let mut tmp: u64;
+            for i in 0..4 {
+                tmp = *a_ptr.offset(i);
+                *a_ptr.offset(i) = *b_ptr.offset(i);
+                *b_ptr.offset(i) = tmp;
+            }
+        }
+    }
+
+    /// Iterate over *all* entries in the underlying buffer
+    ///
+    /// This includes hidden entries.
+    ///
+    /// XXX This suggests that Storage is a leaky abstraction. Ultimately, this
+    ///     is needed because of the grow lines functionality implemented on
+    ///     this type, and maybe that's where the leak is necessitating this
+    ///     accessor.
+    pub fn iter_mut_raw<'a>(&'a mut self) -> slice::IterMut<'a, Row<T>> {
+        self.inner.iter_mut()
+    }
+
+    pub fn rotate(&mut self, count: isize) {
+        debug_assert!(count.abs() as usize <= self.inner.len());
+
+        let len = self.inner.len();
+        self.zero = (self.zero as isize + count + len as isize) as usize % len;
+    }
+
+    // Fast path
+    pub fn rotate_up(&mut self, count: usize) {
+        self.zero = (self.zero + count) % self.inner.len();
+    }
+}
+
+impl<T> Index<usize> for Storage<T> {
+    type Output = Row<T>;
+    #[inline]
+    fn index(&self, index: usize) -> &Self::Output {
+        let index = self.compute_index(index); // borrowck
+        &self.inner[index]
+    }
+}
+
+impl<T> IndexMut<usize> for Storage<T> {
+    #[inline]
+    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
+        let index = self.compute_index(index); // borrowck
+        &mut self.inner[index]
+    }
+}
+
+impl<T> Index<Line> for Storage<T> {
+    type Output = Row<T>;
+    #[inline]
+    fn index(&self, index: Line) -> &Self::Output {
+        let index = self.visible_lines - index;
+        &self[*index]
+    }
+}
+
+impl<T> IndexMut<Line> for Storage<T> {
+    #[inline]
+    fn index_mut(&mut self, index: Line) -> &mut Self::Output {
+        let index = self.visible_lines - index;
+        &mut self[*index]
+    }
+}
+
+#[cfg(test)]
+use index::Column;
+
+/// Grow the buffer one line at the end of the buffer
+///
+/// Before:
+///   0: 0 <- Zero
+///   1: 1
+///   2: -
+/// After:
+///   0: -
+///   1: 0 <- Zero
+///   2: 1
+///   3: -
+#[test]
+fn grow_after_zero() {
+    // Setup storage area
+    let mut storage = Storage {
+        inner: vec![Row::new(Column(1), &'0'), Row::new(Column(1), &'1'), Row::new(Column(1), &'-')],
+        zero: 0,
+        visible_lines: Line(2),
+        len: 3,
+    };
+
+    // Grow buffer
+    storage.grow_visible_lines(Line(4), Row::new(Column(1), &'-'));
+
+    // Make sure the result is correct
+    let expected = Storage {
+        inner: vec![Row::new(Column(1), &'-'), Row::new(Column(1), &'0'), Row::new(Column(1), &'1'), Row::new(Column(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
+///
+/// Before:
+///   0: -
+///   1: 0 <- Zero
+///   2: 1
+/// After:
+///   0: -
+///   1: -
+///   2: 0 <- Zero
+///   3: 1
+#[test]
+fn grow_before_zero() {
+    // Setup storage area
+    let mut storage = Storage {
+        inner: vec![Row::new(Column(1), &'-'), Row::new(Column(1), &'0'), Row::new(Column(1), &'1')],
+        zero: 1,
+        visible_lines: Line(2),
+        len: 3,
+    };
+
+    // Grow buffer
+    storage.grow_visible_lines(Line(4), Row::new(Column(1), &'-'));
+
+    // Make sure the result is correct
+    let expected = Storage {
+        inner: vec![Row::new(Column(1), &'-'), Row::new(Column(1), &'-'), Row::new(Column(1), &'0'), Row::new(Column(1), &'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
+///
+/// Before:
+///   0: 2
+///   1: 0 <- Zero
+///   2: 1
+/// After:
+///   0: 2 <- Hidden
+///   0: 0 <- Zero
+///   1: 1
+#[test]
+fn shrink_before_zero() {
+    // Setup storage area
+    let mut storage = Storage {
+        inner: vec![Row::new(Column(1), &'2'), Row::new(Column(1), &'0'), Row::new(Column(1), &'1')],
+        zero: 1,
+        visible_lines: Line(2),
+        len: 3,
+    };
+
+    // Shrink buffer
+    storage.shrink_visible_lines(Line(2));
+
+    // Make sure the result is correct
+    let expected = Storage {
+        inner: vec![Row::new(Column(1), &'2'), Row::new(Column(1), &'0'), Row::new(Column(1), &'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
+///
+/// Before:
+///   0: 0 <- Zero
+///   1: 1
+///   2: 2
+/// After:
+///   0: 0 <- Zero
+///   1: 1
+///   2: 2 <- Hidden
+#[test]
+fn shrink_after_zero() {
+    // Setup storage area
+    let mut storage = Storage {
+        inner: vec![Row::new(Column(1), &'0'), Row::new(Column(1), &'1'), Row::new(Column(1), &'2')],
+        zero: 0,
+        visible_lines: Line(2),
+        len: 3,
+    };
+
+    // Shrink buffer
+    storage.shrink_visible_lines(Line(2));
+
+    // Make sure the result is correct
+    let expected = Storage {
+        inner: vec![Row::new(Column(1), &'0'), Row::new(Column(1), &'1'), Row::new(Column(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
+///
+/// Before:
+///   0: 4
+///   1: 5
+///   2: 0 <- Zero
+///   3: 1
+///   4: 2
+///   5: 3
+/// After:
+///   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
+    let mut storage = Storage {
+        inner: vec![Row::new(Column(1), &'4'), Row::new(Column(1), &'5'), Row::new(Column(1), &'0'), Row::new(Column(1), &'1'), Row::new(Column(1), &'2'), Row::new(Column(1), &'3')],
+        zero: 2,
+        visible_lines: Line(5),
+        len: 6,
+    };
+
+    // Shrink buffer
+    storage.shrink_visible_lines(Line(2));
+
+    // Make sure the result is correct
+    let expected = Storage {
+        inner: vec![Row::new(Column(1), &'4'), Row::new(Column(1), &'5'), Row::new(Column(1), &'0'), Row::new(Column(1), &'1'), Row::new(Column(1), &'2'), Row::new(Column(1), &'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);
+}
+
+/// 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![Row::new(Column(1), &'4'), Row::new(Column(1), &'5'), Row::new(Column(1), &'0'), Row::new(Column(1), &'1'), Row::new(Column(1), &'2'), Row::new(Column(1), &'3')],
+        zero: 2,
+        visible_lines: Line(1),
+        len: 2,
+    };
+
+    // Truncate buffer
+    storage.truncate();
+
+    // Make sure the result is correct
+    let expected = Storage {
+        inner: vec![Row::new(Column(1), &'0'), Row::new(Column(1), &'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![Row::new(Column(1), &'1'), Row::new(Column(1), &'2'), Row::new(Column(1), &'0')],
+        zero: 2,
+        visible_lines: Line(1),
+        len: 2,
+    };
+
+    // Truncate buffer
+    storage.truncate();
+
+    // Make sure the result is correct
+    let expected = Storage {
+        inner: vec![Row::new(Column(1), &'0'), Row::new(Column(1), &'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);
+}
+
+/// First shrink the buffer and then grow it again
+///
+/// Before:
+///   0: 4
+///   1: 5
+///   2: 0 <- Zero
+///   3: 1
+///   4: 2
+///   5: 3
+/// After Shrinking:
+///   0: 4 <- Hidden
+///   1: 5 <- Hidden
+///   2: 0 <- Zero
+///   3: 1
+///   4: 2
+///   5: 3 <- Hidden
+/// After Growing:
+///   0: 4
+///   1: 5
+///   2: -
+///   3: 0 <- Zero
+///   4: 1
+///   5: 2
+///   6: 3
+#[test]
+fn shrink_then_grow() {
+    // Setup storage area
+    let mut storage = Storage {
+        inner: vec![
+            Row::new(Column(1), &'4'),
+            Row::new(Column(1), &'5'),
+            Row::new(Column(1), &'0'),
+            Row::new(Column(1), &'1'),
+            Row::new(Column(1), &'2'),
+            Row::new(Column(1), &'3'),
+        ],
+        zero: 2,
+        visible_lines: Line(0),
+        len: 6,
+    };
+
+    // Shrink buffer
+    storage.shrink_lines(3);
+
+    // Make sure the result after shrinking is correct
+    let shrinking_expected = Storage {
+        inner: vec![
+            Row::new(Column(1), &'4'),
+            Row::new(Column(1), &'5'),
+            Row::new(Column(1), &'0'),
+            Row::new(Column(1), &'1'),
+            Row::new(Column(1), &'2'),
+            Row::new(Column(1), &'3'),
+        ],
+        zero: 2,
+        visible_lines: Line(0),
+        len: 3,
+    };
+    assert_eq!(storage.inner, shrinking_expected.inner);
+    assert_eq!(storage.zero, shrinking_expected.zero);
+    assert_eq!(storage.len, shrinking_expected.len);
+
+    // Grow buffer
+    storage.grow_lines(4, Row::new(Column(1), &'-'));
+
+    // Make sure the result after shrinking is correct
+    let growing_expected = Storage {
+        inner: vec![
+            Row::new(Column(1), &'4'),
+            Row::new(Column(1), &'5'),
+            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: 3,
+        visible_lines: Line(0),
+        len: 7,
+    };
+    assert_eq!(storage.inner, growing_expected.inner);
+    assert_eq!(storage.zero, growing_expected.zero);
+    assert_eq!(storage.len, growing_expected.len);
+}
diff --git a/src/grid/tests.rs b/src/grid/tests.rs
new file mode 100644
index 00000000..e136e3b3
--- /dev/null
+++ b/src/grid/tests.rs
@@ -0,0 +1,141 @@
+// Copyright 2016 Joe Wilm, The Alacritty Project Contributors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+//! Tests for the Gird
+
+use super::{Grid, BidirectionalIterator};
+use index::{Point, Line, Column};
+
+// Scroll up moves lines upwards
+#[test]
+fn scroll_up() {
+    println!();
+
+    let mut grid = Grid::new(Line(10), Column(1), 0, 0);
+    for i in 0..10 {
+        grid[Line(i)][Column(0)] = i;
+    }
+
+    println!("grid: {:?}", grid);
+
+    grid.scroll_up(&(Line(0)..Line(10)), Line(2), &0);
+
+    println!("grid: {:?}", grid);
+
+    assert_eq!(grid[Line(0)][Column(0)], 2);
+    assert_eq!(grid[Line(0)].occ, 1);
+    assert_eq!(grid[Line(1)][Column(0)], 3);
+    assert_eq!(grid[Line(1)].occ, 1);
+    assert_eq!(grid[Line(2)][Column(0)], 4);
+    assert_eq!(grid[Line(2)].occ, 1);
+    assert_eq!(grid[Line(3)][Column(0)], 5);
+    assert_eq!(grid[Line(3)].occ, 1);
+    assert_eq!(grid[Line(4)][Column(0)], 6);
+    assert_eq!(grid[Line(4)].occ, 1);
+    assert_eq!(grid[Line(5)][Column(0)], 7);
+    assert_eq!(grid[Line(5)].occ, 1);
+    assert_eq!(grid[Line(6)][Column(0)], 8);
+    assert_eq!(grid[Line(6)].occ, 1);
+    assert_eq!(grid[Line(7)][Column(0)], 9);
+    assert_eq!(grid[Line(7)].occ, 1);
+    assert_eq!(grid[Line(8)][Column(0)], 0); // was 0
+    assert_eq!(grid[Line(8)].occ, 0);
+    assert_eq!(grid[Line(9)][Column(0)], 0); // was 1
+    assert_eq!(grid[Line(9)].occ, 0);
+}
+
+// Scroll down moves lines downwards
+#[test]
+fn scroll_down() {
+    println!();
+
+    let mut grid = Grid::new(Line(10), Column(1), 0, 0);
+    for i in 0..10 {
+        grid[Line(i)][Column(0)] = i;
+    }
+
+    println!("grid: {:?}", grid);
+
+    grid.scroll_down(&(Line(0)..Line(10)), Line(2), &0);
+
+    println!("grid: {:?}", grid);
+
+    assert_eq!(grid[Line(0)][Column(0)], 0); // was 8
+    assert_eq!(grid[Line(0)].occ, 0);
+    assert_eq!(grid[Line(1)][Column(0)], 0); // was 9
+    assert_eq!(grid[Line(1)].occ, 0);
+    assert_eq!(grid[Line(2)][Column(0)], 0);
+    assert_eq!(grid[Line(2)].occ, 1);
+    assert_eq!(grid[Line(3)][Column(0)], 1);
+    assert_eq!(grid[Line(3)].occ, 1);
+    assert_eq!(grid[Line(4)][Column(0)], 2);
+    assert_eq!(grid[Line(4)].occ, 1);
+    assert_eq!(grid[Line(5)][Column(0)], 3);
+    assert_eq!(grid[Line(5)].occ, 1);
+    assert_eq!(grid[Line(6)][Column(0)], 4);
+    assert_eq!(grid[Line(6)].occ, 1);
+    assert_eq!(grid[Line(7)][Column(0)], 5);
+    assert_eq!(grid[Line(7)].occ, 1);
+    assert_eq!(grid[Line(8)][Column(0)], 6);
+    assert_eq!(grid[Line(8)].occ, 1);
+    assert_eq!(grid[Line(9)][Column(0)], 7);
+    assert_eq!(grid[Line(9)].occ, 1);
+}
+
+// Test that GridIterator works
+#[test]
+fn test_iter() {
+    info!("");
+
+    let mut grid = Grid::new(Line(5), Column(5), 0, 0);
+    for i in 0..5 {
+        for j in 0..5 {
+            grid[Line(i)][Column(j)] = i*5 + j;
+        }
+    }
+
+    info!("grid: {:?}", grid);
+
+    let mut iter = grid.iter_from(Point {
+        line: 4,
+        col: Column(0),
+    });
+
+    assert_eq!(None, iter.prev());
+    assert_eq!(Some(&1), iter.next());
+    assert_eq!(Column(1), iter.cur.col);
+    assert_eq!(4, iter.cur.line);
+
+    assert_eq!(Some(&2), iter.next());
+    assert_eq!(Some(&3), iter.next());
+    assert_eq!(Some(&4), iter.next());
+
+    // test linewrapping
+    assert_eq!(Some(&5), iter.next());
+    assert_eq!(Column(0), iter.cur.col);
+    assert_eq!(3, iter.cur.line);
+
+    assert_eq!(Some(&4), iter.prev());
+    assert_eq!(Column(4), iter.cur.col);
+    assert_eq!(4, iter.cur.line);
+
+
+    // test that iter ends at end of grid
+    let mut final_iter = grid.iter_from(Point {
+        line: 0,
+        col: Column(4),
+    });
+    assert_eq!(None, final_iter.next());
+    assert_eq!(Some(&23), final_iter.prev());
+}