Refactor cell selection out of renderer

The terminal now has a `renderable_cells()` function that returns a
`RenderableCellIter` iterator. This allows reuse of the cell selection
code by multiple renderers, makes it testable, and makes it
independently optimizable.

The render API now takes an `Iterator<Item=IndexedCell>` to support both
the new renderable cells iterator and the `render_string()` method which
generates its own iterator.

The `vim_large_window_scoll` ref test was added here because it provides
a nice large and busy grid to benchmark the cell selection with.

5 files changed, 247 insertions, 112 deletions

diff --git a/src/lib.rs b/src/lib.rs
index aa9275c2..8f08303b 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -19,8 +19,8 @@
 #![feature(drop_types_in_const)]
 #![feature(unicode)]
 #![feature(step_trait)]
+#![cfg_attr(test, feature(test))]
 #![feature(core_intrinsics)]
-#![feature(test)]
 #![allow(stable_features)] // lying about question_mark because 1.14.0 isn't released!
 
 #![feature(proc_macro)]
diff --git a/src/main.rs b/src/main.rs
index fbf1eaca..aaa20953 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -361,8 +361,10 @@ impl Display {
 
                 let size_info = terminal.size_info().clone();
                 self.renderer.with_api(&size_info, |mut api| {
+                    api.clear();
+
                     // Draw the grid
-                    api.render_grid(&terminal.render_grid(), glyph_cache);
+                    api.render_grid(terminal.renderable_cells(), glyph_cache);
                 });
             }
 
diff --git a/src/meter.rs b/src/meter.rs
index b73c1004..b4bab5ff 100644
--- a/src/meter.rs
+++ b/src/meter.rs
@@ -33,7 +33,7 @@
 
 use std::time::{Instant, Duration};
 
-const NUM_SAMPLES: usize = 60;
+const NUM_SAMPLES: usize = 10;
 
 /// The meter
 pub struct Meter {
diff --git a/src/renderer/mod.rs b/src/renderer/mod.rs
index dfaf6b30..2868a226 100644
--- a/src/renderer/mod.rs
+++ b/src/renderer/mod.rs
@@ -24,10 +24,10 @@ use font::{self, Rasterizer, RasterizedGlyph, FontDesc, GlyphKey, FontKey};
 use gl::types::*;
 use gl;
 use notify::{Watcher as WatcherApi, RecommendedWatcher as Watcher, op};
+use index::{Line, Column};
 
 use config::Config;
-use grid::Grid;
-use term::{self, cell, Cell};
+use term::{self, cell, IndexedCell, Cell};
 
 use super::Rgb;
 
@@ -286,7 +286,7 @@ impl Batch {
         }
     }
 
-    pub fn add_item(&mut self, row: f32, col: f32, cell: &Cell, glyph: &Glyph) {
+    pub fn add_item(&mut self, cell: &IndexedCell, glyph: &Glyph) {
         if self.is_empty() {
             self.tex = glyph.tex_id;
         }
@@ -310,9 +310,9 @@ impl Batch {
             ::term::cell::Color::Ansi(ansi) => self.colors[ansi as usize],
         };
 
-        let mut instance = InstanceData {
-            col: col,
-            row: row,
+        self.instances.push(InstanceData {
+            col: cell.column.0 as f32,
+            row: cell.line.0 as f32,
 
             top: glyph.top,
             left: glyph.left,
@@ -331,19 +331,7 @@ impl Batch {
             bg_r: bg.r as f32,
             bg_g: bg.g as f32,
             bg_b: bg.b as f32,
-        };
-
-        if cell.flags.contains(cell::INVERSE) {
-            instance.r = bg.r as f32;
-            instance.g = bg.g as f32;
-            instance.b = bg.b as f32;
-
-            instance.bg_r = fg.r as f32;
-            instance.bg_g = fg.g as f32;
-            instance.bg_b = fg.b as f32;
-        }
-
-        self.instances.push(instance);
+        });
     }
 
     #[inline]
@@ -631,6 +619,19 @@ impl QuadRenderer {
 }
 
 impl<'a> RenderApi<'a> {
+    pub fn clear(&self) {
+        let color = self.colors[::ansi::Color::Background as usize];
+        unsafe {
+            gl::ClearColor(
+                color.r as f32 / 255.0,
+                color.g as f32 / 255.0,
+                color.b as f32 / 255.0,
+                1.0
+                );
+            gl::Clear(gl::COLOR_BUFFER_BIT);
+        }
+    }
+
     fn render_batch(&mut self) {
         unsafe {
             gl::BufferSubData(gl::ARRAY_BUFFER, 0, self.batch.size() as isize,
@@ -663,36 +664,32 @@ impl<'a> RenderApi<'a> {
     /// optimization.
     pub fn render_string(
         &mut self,
-        s: &str,
+        string: &str,
         glyph_cache: &mut GlyphCache,
         color: &::term::cell::Color,
     ) {
-        let row = 40.0;
-        let mut col = 100.0;
-
-        for c in s.chars() {
-            let glyph_key = GlyphKey {
-                font_key: glyph_cache.font_key,
-                size: glyph_cache.font_size,
-                c: c
-            };
-
-            if let Some(glyph) = glyph_cache.get(&glyph_key, self) {
-                let cell = Cell {
+        let line = Line(23);
+        let col = Column(0);
+
+        let cells = string.chars()
+            .enumerate()
+            .map(|(i, c)| IndexedCell {
+                line: line,
+                column: col + i,
+                inner: Cell {
                     c: c,
-                    fg: color.clone(),
-                    bg: cell::Color::Rgb(Rgb { r: 0, g: 0, b: 0}),
-                    flags: cell::INVERSE,
-                };
-                self.add_render_item(row, col, &cell, glyph);
-            }
+                    bg: *color,
+                    fg: cell::Color::Rgb(Rgb { r: 0, g: 0, b: 0}),
+                    flags: cell::Flags::empty(),
+                }
+            })
+            .collect::<Vec<_>>();
 
-            col += 1.0;
-        }
+        self.render_grid(cells.into_iter(), glyph_cache);
     }
 
     #[inline]
-    fn add_render_item(&mut self, row: f32, col: f32, cell: &Cell, glyph: &Glyph) {
+    fn add_render_item(&mut self, cell: &IndexedCell, glyph: &Glyph) {
         // Flush batch if tex changing
         if !self.batch.is_empty() {
             if self.batch.tex != glyph.tex_id {
@@ -700,7 +697,7 @@ impl<'a> RenderApi<'a> {
             }
         }
 
-        self.batch.add_item(row, col, cell, glyph);
+        self.batch.add_item(cell, glyph);
 
         // Render batch and clear if it's full
         if self.batch.full() {
@@ -708,51 +705,32 @@ impl<'a> RenderApi<'a> {
         }
     }
 
-    pub fn render_grid(
+    pub fn render_grid<I>(
         &mut self,
-        grid: &Grid<Cell>,
+        occupied_cells: I,
         glyph_cache: &mut GlyphCache
-    ) {
-        // TODO should be built into renderer
-        let color = self.colors[::ansi::Color::Background as usize];
-        unsafe {
-            gl::ClearColor(
-                color.r as f32 / 255.0,
-                color.g as f32 / 255.0,
-                color.b as f32 / 255.0,
-                1.0
-                );
-            gl::Clear(gl::COLOR_BUFFER_BIT);
-        }
-
-        for (i, line) in grid.lines().enumerate() {
-            for (j, cell) in line.cells().enumerate() {
-                // Skip empty cells
-                if cell.c == ' ' && cell.bg == cell::Color::Ansi(::ansi::Color::Background) &&
-                   !cell.flags.contains(cell::INVERSE)
-                {
-                    continue;
-                }
-
-                // Get font key for cell
-                // FIXME this is super inefficient.
-                let mut font_key = glyph_cache.font_key;
-                if cell.flags.contains(cell::BOLD) {
-                    font_key = glyph_cache.bold_key;
-                } else if cell.flags.contains(cell::ITALIC) {
-                    font_key = glyph_cache.italic_key;
-                }
+    )
+        where I: Iterator<Item=::term::IndexedCell>
+    {
+        for cell in occupied_cells {
+            // Get font key for cell
+            // FIXME this is super inefficient.
+            let mut font_key = glyph_cache.font_key;
+            if cell.flags.contains(cell::BOLD) {
+                font_key = glyph_cache.bold_key;
+            } else if cell.flags.contains(cell::ITALIC) {
+                font_key = glyph_cache.italic_key;
+            }
 
-                let glyph_key = GlyphKey {
-                    font_key: font_key,
-                    size: glyph_cache.font_size,
-                    c: cell.c
-                };
+            let glyph_key = GlyphKey {
+                font_key: font_key,
+                size: glyph_cache.font_size,
+                c: cell.c
+            };
 
-                // Add cell to batch if glyph available
-                if let Some(glyph) = glyph_cache.get(&glyph_key, self) {
-                    self.add_render_item(i as f32, j as f32, cell, glyph);
-                }
+            // Add cell to batch if glyph available
+            if let Some(glyph) = glyph_cache.get(&glyph_key, self) {
+                self.add_render_item(&cell, glyph);
             }
         }
     }
diff --git a/src/term.rs b/src/term.rs
index 430a68ea..a877d260 100644
--- a/src/term.rs
+++ b/src/term.rs
@@ -13,7 +13,6 @@
 // limitations under the License.
 //
 //! Exports the `Term` type which is a high-level API for the Grid
-use std::mem;
 use std::ops::{Deref, Range};
 use std::ptr;
 use std::cmp;
@@ -23,45 +22,129 @@ use grid::{Grid, ClearRegion};
 use index::{Cursor, Column, Line};
 use ansi::Color;
 
-/// RAII type which manages grid state for render
+/// Iterator that yields cells needing render
+///
+/// Yields cells that require work to be displayed (that is, not a an empty
+/// background cell). Additionally, this manages some state of the grid only
+/// relevant for rendering like temporarily changing the cell with the cursor.
 ///
 /// This manages the cursor during a render. The cursor location is inverted to
 /// draw it, and reverted after drawing to maintain state.
-pub struct RenderGrid<'a> {
-    inner: &'a mut Grid<Cell>,
+pub struct RenderableCellsIter<'a> {
+    grid: &'a mut Grid<Cell>,
     cursor: &'a Cursor,
     mode: TermMode,
+    line: Line,
+    column: Column,
 }
 
-impl<'a> RenderGrid<'a> {
-    fn new<'b>(grid: &'b mut Grid<Cell>, cursor: &'b Cursor, mode: TermMode) -> RenderGrid<'b> {
-        if mode.contains(mode::SHOW_CURSOR) && grid.contains(cursor) {
-            let cell = &mut grid[cursor];
-            mem::swap(&mut cell.fg, &mut cell.bg);
-        }
 
-        RenderGrid {
-            inner: grid,
+impl<'a> RenderableCellsIter<'a> {
+    /// Create the renderable cells iterator
+    ///
+    /// The cursor and terminal mode are required for properly displaying the
+    /// cursor.
+    fn new<'b>(
+        grid: &'b mut Grid<Cell>,
+        cursor: &'b Cursor,
+        mode: TermMode
+    ) -> RenderableCellsIter<'b> {
+        RenderableCellsIter {
+            grid: grid,
             cursor: cursor,
             mode: mode,
+            line: Line(0),
+            column: Column(0),
+        }.initialize()
+    }
+
+    fn initialize(self) -> Self {
+        if self.cursor_is_visible() {
+            self.grid[self.cursor].swap_fg_and_bg();
         }
+
+        self
+    }
+
+    /// Check if the cursor should be rendered.
+    #[inline]
+    fn cursor_is_visible(&self) -> bool {
+        self.mode.contains(mode::SHOW_CURSOR) && self.grid.contains(self.cursor)
     }
 }
 
-impl<'a> Drop for RenderGrid<'a> {
+impl<'a> Drop for RenderableCellsIter<'a> {
+    /// Resets temporary render state on the grid
     fn drop(&mut self) {
-        if self.mode.contains(mode::SHOW_CURSOR) && self.inner.contains(self.cursor) {
-            let cell = &mut self.inner[self.cursor];
-            mem::swap(&mut cell.fg, &mut cell.bg);
+        if self.cursor_is_visible() {
+            self.grid[self.cursor].swap_fg_and_bg();
         }
     }
 }
 
-impl<'a> Deref for RenderGrid<'a> {
-    type Target = Grid<Cell>;
+pub struct IndexedCell {
+    pub line: Line,
+    pub column: Column,
+    pub inner: Cell
+}
 
-    fn deref(&self) -> &Self::Target {
-        self.inner
+impl Deref for IndexedCell {
+    type Target = Cell;
+
+    #[inline(always)]
+    fn deref(&self) -> &Cell {
+        &self.inner
+    }
+}
+
+impl<'a> Iterator for RenderableCellsIter<'a> {
+    type Item = IndexedCell;
+
+    /// Gets the next renderable cell
+    ///
+    /// Skips empty (background) cells and applies any flags to the cell state
+    /// (eg. invert fg and bg colors).
+    #[inline(always)]
+    fn next(&mut self) -> Option<Self::Item> {
+        while self.line < self.grid.num_lines() {
+            while self.column < self.grid.num_cols() {
+                // Grab current state for this iteration
+                let line = self.line;
+                let column = self.column;
+                let cell = &self.grid[line][column];
+
+                // Update state for next iteration
+                self.column += 1;
+
+                // Skip empty cells
+                if cell.is_empty() {
+                    continue;
+                }
+
+                // fg, bg are dependent on INVERSE flag
+                let (fg, bg) = if cell.flags.contains(cell::INVERSE) {
+                    (&cell.bg, &cell.fg)
+                } else {
+                    (&cell.fg, &cell.bg)
+                };
+
+                return Some(IndexedCell {
+                    line: line,
+                    column: column,
+                    inner: Cell {
+                        flags: cell.flags,
+                        c: cell.c,
+                        fg: *fg,
+                        bg: *bg,
+                    }
+                })
+            }
+
+            self.column = Column(0);
+            self.line += 1;
+        }
+
+        None
     }
 }
 
@@ -72,6 +155,9 @@ fn limit<T: PartialOrd + Ord>(val: T, min: T, max: T) -> T {
 }
 
 pub mod cell {
+    use std::mem;
+
+    use ansi;
     use ::Rgb;
 
     bitflags! {
@@ -84,10 +170,10 @@ pub mod cell {
         }
     }
 
-    #[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
+    #[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
     pub enum Color {
         Rgb(Rgb),
-        Ansi(::ansi::Color),
+        Ansi(ansi::Color),
     }
 
     #[derive(Clone, Debug, Serialize, Deserialize, Eq, PartialEq)]
@@ -113,10 +199,22 @@ pub mod cell {
         }
 
         #[inline]
+        pub fn is_empty(&self) -> bool {
+            self.c == ' ' &&
+                self.bg == Color::Ansi(ansi::Color::Background) &&
+                !self.flags.contains(INVERSE)
+        }
+
+        #[inline]
         pub fn reset(&mut self, template: &Cell) {
             // memcpy template to self
             *self = template.clone();
         }
+
+        #[inline]
+        pub fn swap_fg_and_bg(&mut self) {
+            mem::swap(&mut self.fg, &mut self.bg);
+        }
     }
 
     #[cfg(test)]
@@ -256,8 +354,6 @@ impl Term {
         let num_cols = size.cols();
         let num_lines = size.lines();
 
-        println!("num_cols, num_lines = {}, {}", num_cols, num_lines);
-
         let grid = Grid::new(num_lines, num_cols, &template);
 
         let mut tabs = (Column(0)..grid.num_cols())
@@ -307,8 +403,8 @@ impl Term {
         &self.grid
     }
 
-    pub fn render_grid<'a>(&'a mut self) -> RenderGrid<'a> {
-        RenderGrid::new(&mut self.grid, &self.cursor, self.mode)
+    pub fn renderable_cells<'a>(&'a mut self) -> RenderableCellsIter<'a> {
+        RenderableCellsIter::new(&mut self.grid, &self.cursor, self.mode)
     }
 
     /// Resize terminal to new dimensions
@@ -910,3 +1006,62 @@ mod tests {
         assert_eq!(limit(5, 1, 4), 4);
     }
 }
+
+#[cfg(test)]
+mod bench {
+    extern crate test;
+    extern crate serde_json as json;
+
+    use std::io::Read;
+    use std::fs::File;
+    use std::mem;
+    use std::path::Path;
+
+    use grid::Grid;
+
+    use super::{SizeInfo, Term};
+    use super::cell::Cell;
+
+    fn read_string<P>(path: P) -> String
+        where P: AsRef<Path>
+    {
+        let mut res = String::new();
+        File::open(path.as_ref()).unwrap()
+            .read_to_string(&mut res).unwrap();
+
+        res
+    }
+
+    /// Benchmark for the renderable cells iterator
+    ///
+    /// The renderable cells iterator yields cells that require work to be displayed (that is, not a
+    /// an empty background cell). This benchmark measures how long it takes to process the whole
+    /// iterator.
+    ///
+    /// When this benchmark was first added, it averaged ~78usec on my macbook pro. The total
+    /// render time for this grid is anywhere between ~1500 and ~2000usec (measured imprecisely with
+    /// the visual meter).
+    #[bench]
+    fn render_iter(b: &mut test::Bencher) {
+        // Need some realistic grid state; using one of the ref files.
+        let serialized_grid = read_string(
+            concat!(env!("CARGO_MANIFEST_DIR"), "/tests/ref/vim_large_window_scroll/grid.json")
+        );
+        let serialized_size = read_string(
+            concat!(env!("CARGO_MANIFEST_DIR"), "/tests/ref/vim_large_window_scroll/size.json")
+        );
+
+        let mut grid: Grid<Cell> = json::from_str(&serialized_grid).unwrap();
+        let size: SizeInfo = json::from_str(&serialized_size).unwrap();
+
+        let mut terminal = Term::new(size);
+        mem::swap(&mut terminal.grid, &mut grid);
+
+        b.iter(|| {
+            let iter = terminal.renderable_cells();
+            for cell in iter {
+                test::black_box(cell);
+            }
+        })
+    }
+}