Use dynamic storage for zerowidth characters

The zerowidth characters were conventionally stored in a [char; 5].
This creates problems both by limiting the maximum number of zerowidth
characters and by increasing the cell size beyond what is necessary even
when no zerowidth characters are used.

Instead of storing zerowidth characters as a slice, a new CellExtra
struct is introduced which can store arbitrary optional cell data that
is rarely required. Since this is stored behind an optional pointer
(Option<Box<CellExtra>>), the initialization and dropping in the case
of no extra data are extremely cheap and the size penalty to cells
without this extra data is limited to 8 instead of 20 bytes.

The most noticible difference with this PR should be a reduction in
memory size of up to at least 30% (1.06G -> 733M, 100k scrollback, 72
lines, 280 columns). Since the zerowidth characters are now stored
dynamically, the limit of 5 per cell is also no longer present.

5 files changed, 48 insertions, 59 deletions

diff --git a/alacritty/src/display.rs b/alacritty/src/display.rs
index 600ce2a4..6d683336 100644
--- a/alacritty/src/display.rs
+++ b/alacritty/src/display.rs
@@ -473,10 +473,10 @@ impl Display {
                 // Iterate over all non-empty cells in the grid.
                 for cell in grid_cells {
                     // Update URL underlines.
-                    urls.update(size_info.cols(), cell);
+                    urls.update(size_info.cols(), &cell);
 
                     // Update underline/strikeout.
-                    lines.update(cell);
+                    lines.update(&cell);
 
                     // Draw the cell.
                     api.render_cell(cell, glyph_cache);
diff --git a/alacritty/src/event.rs b/alacritty/src/event.rs
index 6c5318f6..0f9c24a5 100644
--- a/alacritty/src/event.rs
+++ b/alacritty/src/event.rs
@@ -34,7 +34,6 @@ use alacritty_terminal::grid::{Dimensions, Scroll};
 use alacritty_terminal::index::{Boundary, Column, Direction, Line, Point, Side};
 use alacritty_terminal::selection::{Selection, SelectionType};
 use alacritty_terminal::sync::FairMutex;
-use alacritty_terminal::term::cell::Cell;
 use alacritty_terminal::term::{ClipboardType, SizeInfo, Term, TermMode};
 #[cfg(not(windows))]
 use alacritty_terminal::tty;
@@ -1174,7 +1173,7 @@ impl<N: Notify + OnResize> Processor<N> {
     fn write_ref_test_results<T>(&self, terminal: &Term<T>) {
         // Dump grid state.
         let mut grid = terminal.grid().clone();
-        grid.initialize_all(Cell::default());
+        grid.initialize_all();
         grid.truncate();
 
         let serialized_grid = json::to_string(&grid).expect("serialize grid");
diff --git a/alacritty/src/renderer/mod.rs b/alacritty/src/renderer/mod.rs
index e97ac025..f628d24f 100644
--- a/alacritty/src/renderer/mod.rs
+++ b/alacritty/src/renderer/mod.rs
@@ -19,7 +19,7 @@ use notify::{watcher, DebouncedEvent, RecursiveMode, Watcher};
 
 use alacritty_terminal::config::Cursor;
 use alacritty_terminal::index::{Column, Line};
-use alacritty_terminal::term::cell::{self, Flags};
+use alacritty_terminal::term::cell::Flags;
 use alacritty_terminal::term::color::Rgb;
 use alacritty_terminal::term::{CursorKey, RenderableCell, RenderableCellContent, SizeInfo};
 use alacritty_terminal::thread;
@@ -436,7 +436,7 @@ impl Batch {
         Self { tex: 0, instances: Vec::with_capacity(BATCH_MAX) }
     }
 
-    pub fn add_item(&mut self, cell: RenderableCell, glyph: &Glyph) {
+    pub fn add_item(&mut self, cell: &RenderableCell, glyph: &Glyph) {
         if self.is_empty() {
             self.tex = glyph.tex_id;
         }
@@ -953,11 +953,7 @@ impl<'a> RenderApi<'a> {
             .map(|(i, c)| RenderableCell {
                 line,
                 column: Column(i),
-                inner: RenderableCellContent::Chars({
-                    let mut chars = [' '; cell::MAX_ZEROWIDTH_CHARS + 1];
-                    chars[0] = c;
-                    chars
-                }),
+                inner: RenderableCellContent::Chars((c, None)),
                 flags: Flags::empty(),
                 bg_alpha,
                 fg,
@@ -971,7 +967,7 @@ impl<'a> RenderApi<'a> {
     }
 
     #[inline]
-    fn add_render_item(&mut self, cell: RenderableCell, glyph: &Glyph) {
+    fn add_render_item(&mut self, cell: &RenderableCell, glyph: &Glyph) {
         // Flush batch if tex changing.
         if !self.batch.is_empty() && self.batch.tex != glyph.tex_id {
             self.render_batch();
@@ -985,8 +981,8 @@ impl<'a> RenderApi<'a> {
         }
     }
 
-    pub fn render_cell(&mut self, cell: RenderableCell, glyph_cache: &mut GlyphCache) {
-        let chars = match cell.inner {
+    pub fn render_cell(&mut self, mut cell: RenderableCell, glyph_cache: &mut GlyphCache) {
+        let (mut c, zerowidth) = match cell.inner {
             RenderableCellContent::Cursor(cursor_key) => {
                 // Raw cell pixel buffers like cursors don't need to go through font lookup.
                 let metrics = glyph_cache.metrics;
@@ -1000,10 +996,10 @@ impl<'a> RenderApi<'a> {
                         self.cursor_config.thickness(),
                     ))
                 });
-                self.add_render_item(cell, glyph);
+                self.add_render_item(&cell, glyph);
                 return;
             },
-            RenderableCellContent::Chars(chars) => chars,
+            RenderableCellContent::Chars((c, ref mut zerowidth)) => (c, zerowidth.take()),
         };
 
         // Get font key for cell.
@@ -1014,37 +1010,33 @@ impl<'a> RenderApi<'a> {
             _ => glyph_cache.font_key,
         };
 
-        // Don't render text of HIDDEN cells.
-        let mut chars = if cell.flags.contains(Flags::HIDDEN) {
-            [' '; cell::MAX_ZEROWIDTH_CHARS + 1]
-        } else {
-            chars
-        };
-
-        // Render tabs as spaces in case the font doesn't support it.
-        if chars[0] == '\t' {
-            chars[0] = ' ';
+        // Ignore hidden cells and render tabs as spaces to prevent font issues.
+        let hidden = cell.flags.contains(Flags::HIDDEN);
+        if c == '\t' || hidden {
+            c = ' ';
         }
 
-        let mut glyph_key = GlyphKey { font_key, size: glyph_cache.font_size, c: chars[0] };
+        let mut glyph_key = GlyphKey { font_key, size: glyph_cache.font_size, c };
 
         // Add cell to batch.
         let glyph = glyph_cache.get(glyph_key, self);
-        self.add_render_item(cell, glyph);
-
-        // Render zero-width characters.
-        for c in (&chars[1..]).iter().filter(|c| **c != ' ') {
-            glyph_key.c = *c;
-            let mut glyph = *glyph_cache.get(glyph_key, self);
-
-            // The metrics of zero-width characters are based on rendering
-            // the character after the current cell, with the anchor at the
-            // right side of the preceding character. Since we render the
-            // zero-width characters inside the preceding character, the
-            // anchor has been moved to the right by one cell.
-            glyph.left += glyph_cache.metrics.average_advance as i16;
-
-            self.add_render_item(cell, &glyph);
+        self.add_render_item(&cell, glyph);
+
+        // Render visible zero-width characters.
+        if let Some(zerowidth) = zerowidth.filter(|_| !hidden) {
+            for c in zerowidth {
+                glyph_key.c = c;
+                let mut glyph = *glyph_cache.get(glyph_key, self);
+
+                // The metrics of zero-width characters are based on rendering
+                // the character after the current cell, with the anchor at the
+                // right side of the preceding character. Since we render the
+                // zero-width characters inside the preceding character, the
+                // anchor has been moved to the right by one cell.
+                glyph.left += glyph_cache.metrics.average_advance as i16;
+
+                self.add_render_item(&cell, &glyph);
+            }
         }
     }
 }
diff --git a/alacritty/src/renderer/rects.rs b/alacritty/src/renderer/rects.rs
index 31e8b82a..fcd8c82e 100644
--- a/alacritty/src/renderer/rects.rs
+++ b/alacritty/src/renderer/rects.rs
@@ -150,14 +150,14 @@ impl RenderLines {
 
     /// Update the stored lines with the next cell info.
     #[inline]
-    pub fn update(&mut self, cell: RenderableCell) {
-        self.update_flag(cell, Flags::UNDERLINE);
-        self.update_flag(cell, Flags::DOUBLE_UNDERLINE);
-        self.update_flag(cell, Flags::STRIKEOUT);
+    pub fn update(&mut self, cell: &RenderableCell) {
+        self.update_flag(&cell, Flags::UNDERLINE);
+        self.update_flag(&cell, Flags::DOUBLE_UNDERLINE);
+        self.update_flag(&cell, Flags::STRIKEOUT);
     }
 
     /// Update the lines for a specific flag.
-    fn update_flag(&mut self, cell: RenderableCell, flag: Flags) {
+    fn update_flag(&mut self, cell: &RenderableCell, flag: Flags) {
         if !cell.flags.contains(flag) {
             return;
         }
diff --git a/alacritty/src/url.rs b/alacritty/src/url.rs
index f969c7af..f3f60dd3 100644
--- a/alacritty/src/url.rs
+++ b/alacritty/src/url.rs
@@ -48,7 +48,7 @@ impl Url {
 pub struct Urls {
     locator: UrlLocator,
     urls: Vec<Url>,
-    scheme_buffer: Vec<RenderableCell>,
+    scheme_buffer: Vec<(Point, Rgb)>,
     last_point: Option<Point>,
     state: UrlLocation,
 }
@@ -71,10 +71,10 @@ impl Urls {
     }
 
     // Update tracked URLs.
-    pub fn update(&mut self, num_cols: Column, cell: RenderableCell) {
+    pub fn update(&mut self, num_cols: Column, cell: &RenderableCell) {
         // Convert cell to character.
-        let c = match cell.inner {
-            RenderableCellContent::Chars(chars) => chars[0],
+        let c = match &cell.inner {
+            RenderableCellContent::Chars((c, _zerowidth)) => *c,
             RenderableCellContent::Cursor(_) => return,
         };
 
@@ -109,9 +109,8 @@ impl Urls {
                 self.urls.push(Url { lines: Vec::new(), end_offset, num_cols });
 
                 // Push schemes into URL.
-                for scheme_cell in self.scheme_buffer.split_off(0) {
-                    let point = scheme_cell.into();
-                    self.extend_url(point, point, scheme_cell.fg, end_offset);
+                for (scheme_point, scheme_fg) in self.scheme_buffer.split_off(0) {
+                    self.extend_url(scheme_point, scheme_point, scheme_fg, end_offset);
                 }
 
                 // Push the new cell into URL.
@@ -120,7 +119,7 @@ impl Urls {
             (UrlLocation::Url(_length, end_offset), UrlLocation::Url(..)) => {
                 self.extend_url(point, end, cell.fg, end_offset);
             },
-            (UrlLocation::Scheme, _) => self.scheme_buffer.push(cell),
+            (UrlLocation::Scheme, _) => self.scheme_buffer.push((cell.into(), cell.fg)),
             (UrlLocation::Reset, _) => self.reset(),
             _ => (),
         }
@@ -196,13 +195,12 @@ mod tests {
     use super::*;
 
     use alacritty_terminal::index::{Column, Line};
-    use alacritty_terminal::term::cell::MAX_ZEROWIDTH_CHARS;
 
     fn text_to_cells(text: &str) -> Vec<RenderableCell> {
         text.chars()
             .enumerate()
             .map(|(i, c)| RenderableCell {
-                inner: RenderableCellContent::Chars([c; MAX_ZEROWIDTH_CHARS + 1]),
+                inner: RenderableCellContent::Chars((c, None)),
                 line: Line(0),
                 column: Column(i),
                 fg: Default::default(),
@@ -223,7 +221,7 @@ mod tests {
         let mut urls = Urls::new();
 
         for cell in input {
-            urls.update(Column(num_cols), cell);
+            urls.update(Column(num_cols), &cell);
         }
 
         let url = urls.urls.first().unwrap();
@@ -239,7 +237,7 @@ mod tests {
         let mut urls = Urls::new();
 
         for cell in input {
-            urls.update(Column(num_cols), cell);
+            urls.update(Column(num_cols), &cell);
         }
 
         assert_eq!(urls.urls.len(), 3);