Fix update_lines performance issues

This resolves performance issues with the `update_lines` method that
were caused by excessive updates without underlines or strikeout
present.

This also resolves a bug that was causing the underline and strikeout to
extend beyond the end of line in some rare cases.

This fixes #114.

4 files changed, 64 insertions, 55 deletions

diff --git a/src/display.rs b/src/display.rs
index 58c58e3a..25c4855a 100644
--- a/src/display.rs
+++ b/src/display.rs
@@ -415,7 +415,7 @@ impl Display {
                 pty_size.height -= pty_size.cell_height * message.text(&size).len() as f32;
             }
 
-            if previous_cols != size.cols() || previous_lines != size.lines()  {
+            if previous_cols != size.cols() || previous_lines != size.lines() {
                 pty_resize_handle.on_resize(&pty_size);
             }
 
@@ -489,7 +489,7 @@ impl Display {
                     // Iterate over all non-empty cells in the grid
                     for cell in grid_cells {
                         // Update underline/strikeout
-                        rects.update_lines(&cell);
+                        rects.update_lines(&size_info, &cell);
 
                         // Draw the cell
                         api.render_cell(cell, glyph_cache);
diff --git a/src/index.rs b/src/index.rs
index 0351c0ee..f6ea4ad3 100644
--- a/src/index.rs
+++ b/src/index.rs
@@ -19,6 +19,8 @@ use std::cmp::{Ord, Ordering};
 use std::fmt;
 use std::ops::{self, Add, AddAssign, Deref, Range, RangeInclusive, Sub, SubAssign};
 
+use crate::term::RenderableCell;
+
 /// The side of a cell
 #[derive(Debug, Copy, Clone, Eq, PartialEq)]
 pub enum Side {
@@ -69,6 +71,12 @@ impl From<Point> for Point<usize> {
     }
 }
 
+impl From<&RenderableCell> for Point<Line> {
+    fn from(cell: &RenderableCell) -> Self {
+        Point::new(cell.line, cell.column)
+    }
+}
+
 /// A line
 ///
 /// Newtype to avoid passing values incorrectly
diff --git a/src/renderer/rects.rs b/src/renderer/rects.rs
index e6a45639..2e5cd85b 100644
--- a/src/renderer/rects.rs
+++ b/src/renderer/rects.rs
@@ -11,12 +11,12 @@
 // 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.
-use std::collections::HashMap;
+use font::Metrics;
 
+use crate::index::Point;
 use crate::term::cell::Flags;
 use crate::term::color::Rgb;
 use crate::term::{RenderableCell, SizeInfo};
-use font::Metrics;
 
 #[derive(Debug, Copy, Clone)]
 pub struct Rect<T> {
@@ -32,87 +32,84 @@ impl<T> Rect<T> {
     }
 }
 
+#[derive(Debug)]
+struct Line {
+    flag: Flags,
+    range: Option<(RenderableCell, Point)>,
+}
+
+impl Line {
+    fn new(flag: Flags) -> Self {
+        Self { flag, range: None }
+    }
+}
+
 /// Rects for underline, strikeout and more.
 pub struct Rects<'a> {
     inner: Vec<(Rect<f32>, Rgb)>,
-    last_starts: HashMap<Flags, Option<RenderableCell>>,
-    last_cell: Option<RenderableCell>,
+    active_lines: Vec<Line>,
     metrics: &'a Metrics,
     size: &'a SizeInfo,
 }
 
 impl<'a> Rects<'a> {
     pub fn new(metrics: &'a Metrics, size: &'a SizeInfo) -> Self {
-        let mut last_starts = HashMap::new();
-        last_starts.insert(Flags::UNDERLINE, None);
-        last_starts.insert(Flags::STRIKEOUT, None);
-
-        Self { inner: Vec::new(), last_cell: None, last_starts, metrics, size }
+        let active_lines = vec![Line::new(Flags::UNDERLINE), Line::new(Flags::STRIKEOUT)];
+        Self { inner: Vec::new(), active_lines, metrics, size }
     }
 
     /// Convert the stored rects to rectangles for the renderer.
-    pub fn rects(mut self) -> Vec<(Rect<f32>, Rgb)> {
-        // If there's still a line pending, draw it until the last cell
-        for (flag, start_cell) in self.last_starts.iter_mut() {
-            if let Some(start) = start_cell {
-                self.inner.push(create_rect(
-                    &start,
-                    &self.last_cell.unwrap(),
-                    *flag,
-                    &self.metrics,
-                    &self.size,
-                ));
-            }
-        }
-
-        self.inner
+    pub fn rects(&self) -> &Vec<(Rect<f32>, Rgb)> {
+        &self.inner
     }
 
     /// Update the stored lines with the next cell info.
-    pub fn update_lines(&mut self, cell: &RenderableCell) {
-        for (flag, start_cell) in self.last_starts.iter_mut() {
-            let flag = *flag;
-            *start_cell = match *start_cell {
+    pub fn update_lines(&mut self, size_info: &SizeInfo, cell: &RenderableCell) {
+        for line in self.active_lines.iter_mut() {
+            match line.range {
                 // Check for end if line is present
-                Some(ref mut start) => {
-                    let last_cell = self.last_cell.unwrap();
-
+                Some((ref mut start, ref mut end)) => {
                     // No change in line
                     if cell.line == start.line
-                        && cell.flags.contains(flag)
+                        && cell.flags.contains(line.flag)
                         && cell.fg == start.fg
-                        && cell.column == last_cell.column + 1
+                        && cell.column == end.col + 1
                     {
+                        if size_info.cols() == cell.column && size_info.lines() == cell.line {
+                            // Add the last rect if we've reached the end of the terminal
+                            self.inner.push(create_rect(
+                                &start,
+                                cell.into(),
+                                line.flag,
+                                &self.metrics,
+                                &self.size,
+                            ));
+                        } else {
+                            // Update the length of the line
+                            *end = cell.into();
+                        }
+
                         continue;
                     }
 
-                    self.inner.push(create_rect(
-                        &start,
-                        &last_cell,
-                        flag,
-                        &self.metrics,
-                        &self.size,
-                    ));
+                    self.inner.push(create_rect(start, *end, line.flag, &self.metrics, &self.size));
 
                     // Start a new line if the flag is present
-                    if cell.flags.contains(flag) {
-                        Some(*cell)
+                    if cell.flags.contains(line.flag) {
+                        *start = *cell;
+                        *end = cell.into();
                     } else {
-                        None
+                        line.range = None;
                     }
                 },
                 // Check for new start of line
                 None => {
-                    if cell.flags.contains(flag) {
-                        Some(*cell)
-                    } else {
-                        None
+                    if cell.flags.contains(line.flag) {
+                        line.range = Some((*cell, cell.into()));
                     }
                 },
             };
         }
-
-        self.last_cell = Some(*cell);
     }
 
     // Add a rectangle
@@ -125,13 +122,13 @@ impl<'a> Rects<'a> {
 /// of `end`, based on the given flag and size metrics.
 fn create_rect(
     start: &RenderableCell,
-    end: &RenderableCell,
+    end: Point,
     flag: Flags,
     metrics: &Metrics,
     size: &SizeInfo,
 ) -> (Rect<f32>, Rgb) {
     let start_x = start.column.0 as f32 * size.cell_width;
-    let end_x = (end.column.0 + 1) as f32 * size.cell_width;
+    let end_x = (end.col.0 + 1) as f32 * size.cell_width;
     let width = end_x - start_x;
 
     let (position, mut height) = match flag {
diff --git a/src/term/mod.rs b/src/term/mod.rs
index 3178de4c..48eedef1 100644
--- a/src/term/mod.rs
+++ b/src/term/mod.rs
@@ -1318,7 +1318,9 @@ impl Term {
         lines = min(lines, self.scroll_region.end - origin);
 
         // Scroll between origin and bottom
-        self.grid.scroll_down(&(origin..self.scroll_region.end), lines, &self.cursor.template);
+        let mut template = self.cursor.template;
+        template.flags = Flags::empty();
+        self.grid.scroll_down(&(origin..self.scroll_region.end), lines, &template);
     }
 
     /// Scroll screen up
@@ -1331,7 +1333,9 @@ impl Term {
         let lines = min(lines, self.scroll_region.end - self.scroll_region.start);
 
         // Scroll from origin to bottom less number of lines
-        self.grid.scroll_up(&(origin..self.scroll_region.end), lines, &self.cursor.template);
+        let mut template = self.cursor.template;
+        template.flags = Flags::empty();
+        self.grid.scroll_up(&(origin..self.scroll_region.end), lines, &template);
     }
 
     fn deccolm(&mut self) {