Improve rendering performance

This PR combines a couple of optimizations to drastically reduce the
time it takes to gather everything necessary for rendering Alacritty's
terminal grid.

To help with the iteration over the grid, the `DisplayIter` which made
heavy use of dynamic dispatch has been replaced with a simple addition
to the `GridIterator` which also had the benefit of making the code a
little easier to understand.

The hints/search check for each cell was always performing an array
lookup before figuring out that the cell is not part of a hint or
search. Since the general case is that the cell is neither part of hints
or search, they've been wrapped in an `Option` to make verifying their
activity a simple `is_some()` check.

For some reason the compiler was also struggling with the `cursor`
method of the `RenderableContent`. Since the iterator is explicitly
drained, the performance took a hit of multiple milliseconds for a
single branch. Our implementation does never reach the case where
draining the iterator would be necessary, so this sanity check has just
been replaced with a `debug_assert`.

Overall this has managed to reduce the time it takes to collect all
renderable content from ~7-8ms in my large grid test to just ~3-4ms.

3 files changed, 29 insertions, 24 deletions

diff --git a/alacritty_terminal/src/grid/mod.rs b/alacritty_terminal/src/grid/mod.rs
index 06af3bea..df83d7e3 100644
--- a/alacritty_terminal/src/grid/mod.rs
+++ b/alacritty_terminal/src/grid/mod.rs
@@ -1,7 +1,6 @@
 //! A specialized 2D grid implementation optimized for use in a terminal.
 
 use std::cmp::{max, min};
-use std::iter::TakeWhile;
 use std::ops::{Bound, Deref, Index, IndexMut, Range, RangeBounds};
 
 use serde::{Deserialize, Serialize};
@@ -398,22 +397,25 @@ impl<T> Grid<T> {
         self.raw.truncate();
     }
 
+    /// Iterate over all cells in the grid starting at a specific point.
     #[inline]
     pub fn iter_from(&self, point: Point) -> GridIterator<'_, T> {
-        GridIterator { grid: self, point }
+        let end = Point::new(self.bottommost_line(), self.last_column());
+        GridIterator { grid: self, point, end }
     }
 
-    /// Iterator over all visible cells.
+    /// Iterate over all visible cells.
+    ///
+    /// This is slightly more optimized than calling `Grid::iter_from` in combination with
+    /// `Iterator::take_while`.
     #[inline]
-    pub fn display_iter(&self) -> DisplayIter<'_, T> {
-        let start = Point::new(Line(-(self.display_offset as i32) - 1), self.last_column());
-        let end = Point::new(start.line + self.lines, Column(self.columns));
-
-        let iter = GridIterator { grid: self, point: start };
+    pub fn display_iter(&self) -> GridIterator<'_, T> {
+        let last_column = self.last_column();
+        let start = Point::new(Line(-(self.display_offset() as i32) - 1), last_column);
+        let end_line = min(start.line + self.screen_lines(), self.bottommost_line());
+        let end = Point::new(end_line, last_column);
 
-        let take_while: DisplayIterTakeFun<'_, T> =
-            Box::new(move |indexed: &Indexed<&T>| indexed.point <= end);
-        iter.take_while(take_while)
+        GridIterator { grid: self, point: start, end }
     }
 
     #[inline]
@@ -560,6 +562,9 @@ pub struct GridIterator<'a, T> {
 
     /// Current position of the iterator within the grid.
     point: Point,
+
+    /// Last cell included in the iterator.
+    end: Point,
 }
 
 impl<'a, T> GridIterator<'a, T> {
@@ -578,15 +583,13 @@ impl<'a, T> Iterator for GridIterator<'a, T> {
     type Item = Indexed<&'a T>;
 
     fn next(&mut self) -> Option<Self::Item> {
-        let last_column = self.grid.last_column();
-
         // Stop once we've reached the end of the grid.
-        if self.point == Point::new(self.grid.bottommost_line(), last_column) {
+        if self.point >= self.end {
             return None;
         }
 
         match self.point {
-            Point { column, .. } if column == last_column => {
+            Point { column, .. } if column == self.grid.last_column() => {
                 self.point.column = Column(0);
                 self.point.line += 1;
             },
@@ -623,6 +626,3 @@ impl<'a, T> BidirectionalIterator for GridIterator<'a, T> {
         Some(Indexed { cell: &self.grid[self.point], point: self.point })
     }
 }
-
-pub type DisplayIter<'a, T> = TakeWhile<GridIterator<'a, T>, DisplayIterTakeFun<'a, T>>;
-type DisplayIterTakeFun<'a, T> = Box<dyn Fn(&Indexed<&'a T>) -> bool>;
diff --git a/alacritty_terminal/src/selection.rs b/alacritty_terminal/src/selection.rs
index 428b3f0e..47a49910 100644
--- a/alacritty_terminal/src/selection.rs
+++ b/alacritty_terminal/src/selection.rs
@@ -13,7 +13,7 @@ use crate::ansi::CursorShape;
 use crate::grid::{Dimensions, GridCell, Indexed};
 use crate::index::{Boundary, Column, Line, Point, Side};
 use crate::term::cell::{Cell, Flags};
-use crate::term::{RenderableCursor, Term};
+use crate::term::Term;
 
 /// A Point and side within that point.
 #[derive(Debug, Copy, Clone, PartialEq)]
@@ -56,10 +56,15 @@ impl SelectionRange {
     }
 
     /// Check if the cell at a point is part of the selection.
-    pub fn contains_cell(&self, indexed: &Indexed<&Cell>, cursor: RenderableCursor) -> bool {
+    pub fn contains_cell(
+        &self,
+        indexed: &Indexed<&Cell>,
+        point: Point,
+        shape: CursorShape,
+    ) -> bool {
         // Do not invert block cursor at selection boundaries.
-        if cursor.shape == CursorShape::Block
-            && cursor.point == indexed.point
+        if shape == CursorShape::Block
+            && point == indexed.point
             && (self.start == indexed.point
                 || self.end == indexed.point
                 || (self.is_block
diff --git a/alacritty_terminal/src/term/mod.rs b/alacritty_terminal/src/term/mod.rs
index 409d4ebe..2fb4da34 100644
--- a/alacritty_terminal/src/term/mod.rs
+++ b/alacritty_terminal/src/term/mod.rs
@@ -15,7 +15,7 @@ use crate::ansi::{
 };
 use crate::config::Config;
 use crate::event::{Event, EventListener};
-use crate::grid::{Dimensions, DisplayIter, Grid, Scroll};
+use crate::grid::{Dimensions, Grid, GridIterator, Scroll};
 use crate::index::{self, Boundary, Column, Direction, Line, Point, Side};
 use crate::selection::{Selection, SelectionRange};
 use crate::term::cell::{Cell, Flags, LineLength};
@@ -1828,7 +1828,7 @@ impl RenderableCursor {
 ///
 /// This contains all content required to render the current terminal view.
 pub struct RenderableContent<'a> {
-    pub display_iter: DisplayIter<'a, Cell>,
+    pub display_iter: GridIterator<'a, Cell>,
     pub selection: Option<SelectionRange>,
     pub cursor: RenderableCursor,
     pub display_offset: usize,