Render underline/strikethrough as rects

Support for strikethrough has been added by inserting and removing a
`STRIKE_THROUGH` flag on the cell.

Now all strikethrough and underline drawing is also done through the
rectangle renderer. So no glyphs are used to render underlines and
strikethrough.
The position is taken from the font metrics and should be accurate for
linux, however is not yet tested on macos.

It works by checking the underline state for each cell and then drawing
from the start until the last position whenever an underline ended. This
adds a few checks even if no underline is rendered but I was not able to
measure any significant performance impact.

Fixes jwilm/alacritty#806.
Fixes jwilm/alacritty#31.

7 files changed, 200 insertions, 62 deletions

diff --git a/font/src/darwin/mod.rs b/font/src/darwin/mod.rs
index 14381113..89858f77 100644
--- a/font/src/darwin/mod.rs
+++ b/font/src/darwin/mod.rs
@@ -422,11 +422,15 @@ impl Font {
         let descent = self.ct_font.descent() as f64;
         let leading = self.ct_font.leading() as f64;
         let line_height = (ascent + descent + leading + 0.5).floor();
+        let underline_position = self.ct_font.underline_position() as f32;
+        let underline_thickness = self.ct_font.underline_thickness() as f32;
 
         Metrics {
             average_advance: average_advance,
             line_height: line_height,
             descent: -(self.ct_font.descent() as f32),
+            underline_position,
+            underline_thickness,
         }
     }
 
diff --git a/font/src/ft/mod.rs b/font/src/ft/mod.rs
index 68d2faf3..6d77a61c 100644
--- a/font/src/ft/mod.rs
+++ b/font/src/ft/mod.rs
@@ -86,15 +86,24 @@ impl ::Rasterize for FreeTypeRasterizer {
     }
 
     fn metrics(&self, key: FontKey) -> Result<Metrics, Error> {
+        let face = self.faces
+            .get(&key)
+            .ok_or(Error::FontNotLoaded)?;
         let full = self.full_metrics(key)?;
 
         let height = (full.size_metrics.height / 64) as f64;
         let descent = (full.size_metrics.descender / 64) as f32;
+        let underline_position =
+            (f32::from(face.ft_face.underline_position()) / 64.).round();
+        let underline_thickness =
+            (f32::from(face.ft_face.underline_thickness()) / 64.).round();
 
         Ok(Metrics {
             average_advance: full.cell_width,
             line_height: height,
             descent: descent,
+            underline_position,
+            underline_thickness,
         })
     }
 
diff --git a/font/src/lib.rs b/font/src/lib.rs
index 330ed362..7a8ac7a7 100644
--- a/font/src/lib.rs
+++ b/font/src/lib.rs
@@ -314,6 +314,8 @@ pub struct Metrics {
     pub average_advance: f64,
     pub line_height: f64,
     pub descent: f32,
+    pub underline_position: f32,
+    pub underline_thickness: f32,
 }
 
 pub trait Rasterize {
diff --git a/src/display.rs b/src/display.rs
index 826916ce..3537adb7 100644
--- a/src/display.rs
+++ b/src/display.rs
@@ -21,11 +21,11 @@ use parking_lot::{MutexGuard};
 use Rgb;
 use cli;
 use config::Config;
-use font::{self, Rasterize};
+use font::{self, Rasterize, Metrics};
 use meter::Meter;
-use renderer::{self, GlyphCache, QuadRenderer};
+use renderer::{self, GlyphCache, QuadRenderer, Rect};
 use selection::Selection;
-use term::{Term, SizeInfo};
+use term::{cell, Term, SizeInfo, RenderableCell};
 
 use window::{self, Size, Pixels, Window, SetInnerSize};
 
@@ -346,6 +346,8 @@ impl Display {
 
         {
             let glyph_cache = &mut self.glyph_cache;
+            let metrics = glyph_cache.font_metrics();
+            let mut cell_line_rects = Vec::new();
 
             // Draw grid
             {
@@ -363,17 +365,74 @@ impl Display {
                         api.clear(background_color);
                     }
 
-                    // Draw the grid
-                    api.render_cells(
-                        terminal.renderable_cells(config, selection, window_focused),
-                        glyph_cache,
-                    );
+                    // Store underline/strikethrough information beyond current cell
+                    let mut last_cell = None;
+                    let mut start_underline: Option<RenderableCell> = None;
+                    let mut start_strikethrough: Option<RenderableCell> = None;
+
+                    // Iterate over all non-empty cells in the grid
+                    for cell in terminal.renderable_cells(config, selection, window_focused) {
+                        // Check if there is a new underline
+                        if let Some(underline) = calculate_cell_line_state(
+                            cell,
+                            &mut start_underline,
+                            &last_cell,
+                            &metrics,
+                            &size_info,
+                            cell::Flags::UNDERLINE,
+                        ) {
+                            cell_line_rects.push(underline);
+                        }
+
+                        // Check if there is a new strikethrough
+                        if let Some(strikethrough) = calculate_cell_line_state(
+                            cell,
+                            &mut start_strikethrough,
+                            &last_cell,
+                            &metrics,
+                            &size_info,
+                            cell::Flags::STRIKE_THROUGH,
+                        ) {
+                            cell_line_rects.push(strikethrough);
+                        }
+
+                        // Change the last checked cell for underline/strikethrough
+                        last_cell = Some(cell);
+
+                        // Draw the cell
+                        api.render_cell(cell, glyph_cache);
+                    }
+
+                    // If underline hasn't been reset, draw until the last cell
+                    if let Some(start) = start_underline {
+                        cell_line_rects.push(
+                            cell_line_rect(
+                                &start,
+                                &last_cell.unwrap(),
+                                &metrics, &size_info,
+                                cell::Flags::UNDERLINE
+                            )
+                        );
+                    }
+
+                    // If strikethrough hasn't been reset, draw until the last cell
+                    if let Some(start) = start_strikethrough {
+                        let flag = cell::Flags::STRIKE_THROUGH;
+                        cell_line_rects.push(
+                            cell_line_rect(
+                                &start,
+                                &last_cell.unwrap(),
+                                &metrics, &size_info,
+                                cell::Flags::STRIKE_THROUGH
+                            )
+                        );
+                    }
                 });
             }
 
             // Draw rectangles
             let visual_bell_intensity = terminal.visual_bell.intensity();
-            self.renderer.draw_rects(config, &size_info, visual_bell_intensity);
+            self.renderer.draw_rects(config, &size_info, visual_bell_intensity, cell_line_rects);
 
             // Draw render timer
             if self.render_timer {
@@ -423,3 +482,75 @@ impl Display {
         self.window().send_xim_spot(nspot_x, nspot_y);
     }
 }
+
+// Check if the underline/strikethrough state has changed
+// This returns a new rectangle whenever an underline/strikethrough ends
+fn calculate_cell_line_state(
+    cell: RenderableCell,
+    start_cell_line: &mut Option<RenderableCell>,
+    last_cell: &Option<RenderableCell>,
+    metrics: &Metrics,
+    size_info: &SizeInfo,
+    flag: cell::Flags,
+) -> Option<(Rect<u32>, Rgb)> {
+    match *start_cell_line {
+        // If line is already started, check for end
+        Some(start) => {
+            // No change in line
+            if cell.line == start.line
+                && cell.flags.contains(flag)
+                && cell.fg == start.fg
+            {
+                return None;
+            }
+
+            // Check if we need to start a new line
+            // because the cell color has changed
+            *start_cell_line = if cell.fg != start.fg && cell.flags.contains(flag) {
+                // Start a new line
+                Some(cell)
+            } else {
+                // Disable line
+                None
+            };
+
+            return Some(
+                cell_line_rect(&start, &last_cell.unwrap(), metrics, size_info, flag)
+            );
+        },
+        // Check for new start of line
+        None => if cell.flags.contains(flag) {
+            *start_cell_line = Some(cell);
+        },
+    }
+    None
+}
+
+// Create a colored rectangle for an underline/strikethrough based on two cells
+fn cell_line_rect(
+    start: &RenderableCell,
+    end: &RenderableCell,
+    metrics: &Metrics,
+    size: &SizeInfo,
+    flag: cell::Flags,
+) -> (Rect<u32>, Rgb) {
+    let x = (start.column.0 as f64 * metrics.average_advance) as u32;
+    let end_x = ((end.column.0 + 1) as f64 * metrics.average_advance) as u32;
+    let width = end_x - x;
+
+    let y = match flag {
+        cell::Flags::UNDERLINE => {
+            ((start.line.0 as f32 + 1.) * metrics.line_height as f32 + metrics.descent - metrics.underline_position) as u32
+        },
+        cell::Flags::STRIKE_THROUGH => {
+            ((start.line.0 as f32 + 0.5) * metrics.line_height as f32) as u32
+        },
+        _ => panic!("Invalid flag for cell line drawing specified"),
+    };
+    let height = metrics.underline_thickness as u32;
+
+    let rect = Rect::new(x + size.padding_x as u32, y + size.padding_y as u32, width, height);
+    let color = start.fg;
+
+    (rect, color)
+}
diff --git a/src/renderer/mod.rs b/src/renderer/mod.rs
index 7c3328f9..c6e884b4 100644
--- a/src/renderer/mod.rs
+++ b/src/renderer/mod.rs
@@ -668,7 +668,8 @@ impl QuadRenderer {
         &mut self,
         config: &Config,
         props: &term::SizeInfo,
-        visual_bell_intensity: f64)
+        visual_bell_intensity: f64,
+        cell_line_rects: Vec<(Rect<u32>, Rgb)>)
     {
         // Swap to rectangle rendering program
         unsafe {
@@ -701,6 +702,11 @@ impl QuadRenderer {
         let rect = Rect::new(0, 0, *size.width, *size.height);
         self.render_rect(&rect, color, visual_bell_intensity as f32, size);
 
+        // Draw underlines and strikethroughs
+        for cell_line_rect in cell_line_rects {
+            self.render_rect(&cell_line_rect.0, cell_line_rect.1, 255., size);
+        }
+
         // Deactivate rectangle program again
         unsafe {
             // Reset blending strategy
@@ -865,7 +871,8 @@ impl QuadRenderer {
     }
 }
 
-struct Rect<T> {
+#[derive(Debug, Copy, Clone)]
+pub struct Rect<T> {
     x: T,
     y: T,
     width: T,
@@ -873,7 +880,7 @@ struct Rect<T> {
 }
 
 impl<T> Rect<T> {
-    fn new(x: T, y: T, width: T, height: T) -> Self {
+    pub fn new(x: T, y: T, width: T, height: T) -> Self {
         Rect { x, y, width, height }
     }
 }
@@ -943,7 +950,9 @@ impl<'a> RenderApi<'a> {
             })
             .collect::<Vec<_>>();
 
-        self.render_cells(cells.into_iter(), glyph_cache);
+        for cell in cells {
+            self.render_cell(cell, glyph_cache);
+        }
     }
 
     #[inline]
@@ -961,48 +970,27 @@ impl<'a> RenderApi<'a> {
         }
     }
 
-    pub fn render_cells<I>(
-        &mut self,
-        cells: I,
-        glyph_cache: &mut GlyphCache
-    )
-        where I: Iterator<Item=RenderableCell>
+    pub fn render_cell(&mut self, cell: RenderableCell, glyph_cache: &mut GlyphCache)
     {
-        for cell in cells {
-            // Get font key for cell
-            // FIXME this is super inefficient.
-            let mut font_key = glyph_cache.font_key;
-            if cell.flags.contains(cell::Flags::BOLD) {
-                font_key = glyph_cache.bold_key;
-            } else if cell.flags.contains(cell::Flags::ITALIC) {
-                font_key = glyph_cache.italic_key;
-            }
-
-            let glyph_key = GlyphKey {
-                font_key: font_key,
-                size: glyph_cache.font_size,
-                c: cell.c
-            };
+        // Get font key for cell
+        // FIXME this is super inefficient.
+        let mut font_key = glyph_cache.font_key;
+        if cell.flags.contains(cell::Flags::BOLD) {
+            font_key = glyph_cache.bold_key;
+        } else if cell.flags.contains(cell::Flags::ITALIC) {
+            font_key = glyph_cache.italic_key;
+        }
 
-            // Add cell to batch
-            {
-                let glyph = glyph_cache.get(&glyph_key, self);
-                self.add_render_item(&cell, glyph);
-            }
+        let glyph_key = GlyphKey {
+            font_key: font_key,
+            size: glyph_cache.font_size,
+            c: cell.c
+        };
 
-            // FIXME This is a super hacky way to do underlined text. During
-            //       a time crunch to release 0.1, this seemed like a really
-            //       easy, clean hack.
-            if cell.flags.contains(cell::Flags::UNDERLINE) {
-                let glyph_key = GlyphKey {
-                    font_key: font_key,
-                    size: glyph_cache.font_size,
-                    c: '_'
-                };
-
-                let underscore = glyph_cache.get(&glyph_key, self);
-                self.add_render_item(&cell, underscore);
-            }
+        // Add cell to batch
+        {
+            let glyph = glyph_cache.get(&glyph_key, self);
+            self.add_render_item(&cell, glyph);
         }
     }
 }
diff --git a/src/term/cell.rs b/src/term/cell.rs
index 16e08cba..75bbdb85 100644
--- a/src/term/cell.rs
+++ b/src/term/cell.rs
@@ -18,15 +18,16 @@ use index::Column;
 bitflags! {
     #[derive(Serialize, Deserialize)]
     pub struct Flags: u32 {
-        const INVERSE           = 0b0000_0001;
-        const BOLD              = 0b0000_0010;
-        const ITALIC            = 0b0000_0100;
-        const UNDERLINE         = 0b0000_1000;
-        const WRAPLINE          = 0b0001_0000;
-        const WIDE_CHAR         = 0b0010_0000;
-        const WIDE_CHAR_SPACER  = 0b0100_0000;
-        const DIM               = 0b1000_0000;
-        const DIM_BOLD          = 0b1000_0010;
+        const INVERSE           = 0b0_0000_0001;
+        const BOLD              = 0b0_0000_0010;
+        const ITALIC            = 0b0_0000_0100;
+        const UNDERLINE         = 0b0_0000_1000;
+        const WRAPLINE          = 0b0_0001_0000;
+        const WIDE_CHAR         = 0b0_0010_0000;
+        const WIDE_CHAR_SPACER  = 0b0_0100_0000;
+        const DIM               = 0b0_1000_0000;
+        const DIM_BOLD          = 0b0_1000_0010;
+        const STRIKE_THROUGH    = 0b1_0000_0000;
     }
 }
 
@@ -103,7 +104,7 @@ impl Cell {
     pub fn is_empty(&self) -> bool {
         self.c == ' ' &&
             self.bg == Color::Named(NamedColor::Background) &&
-            !self.flags.intersects(Flags::INVERSE | Flags::UNDERLINE)
+            !self.flags.intersects(Flags::INVERSE | Flags::UNDERLINE | Flags::STRIKE_THROUGH)
     }
 
     #[inline]
diff --git a/src/term/mod.rs b/src/term/mod.rs
index 79101540..12e665e2 100644
--- a/src/term/mod.rs
+++ b/src/term/mod.rs
@@ -317,6 +317,7 @@ impl<'a> RenderableCellsIter<'a> {
     }
 }
 
+#[derive(Copy, Clone)]
 pub struct RenderableCell {
     pub line: Line,
     pub column: Column,
@@ -1808,6 +1809,8 @@ impl ansi::Handler for Term {
             Attr::CancelItalic => self.cursor.template.flags.remove(cell::Flags::ITALIC),
             Attr::Underscore => self.cursor.template.flags.insert(cell::Flags::UNDERLINE),
             Attr::CancelUnderline => self.cursor.template.flags.remove(cell::Flags::UNDERLINE),
+            Attr::Strike => self.cursor.template.flags.insert(cell::Flags::STRIKE_THROUGH),
+            Attr::CancelStrike => self.cursor.template.flags.remove(cell::Flags::STRIKE_THROUGH),
             _ => {
                 debug!("Term got unhandled attr: {:?}", attr);
             }