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.

60 files changed, 629 insertions, 598 deletions

diff --git a/CHANGELOG.md b/CHANGELOG.md
index 35d3b92f..9b0b17a9 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -36,6 +36,8 @@ The format is based on [Keep a Changelog](https://keepachangelog.com/en/1.0.0/).
 - Use yellow/red from the config for error and warning messages instead of fixed colors
 - Existing CLI parameters are now passed to instances spawned using `SpawnNewInstance`
 - Wayland's Client side decorations now use the search bar colors
+- Reduce memory usage by up to at least 30% with a full scrollback buffer
+- The number of zerowidth characters per cell is no longer limited to 5
 
 ### Fixed
 
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);
diff --git a/alacritty_terminal/src/grid/mod.rs b/alacritty_terminal/src/grid/mod.rs
index 5ab25c78..70dbc936 100644
--- a/alacritty_terminal/src/grid/mod.rs
+++ b/alacritty_terminal/src/grid/mod.rs
@@ -7,7 +7,7 @@ use serde::{Deserialize, Serialize};
 
 use crate::ansi::{CharsetIndex, StandardCharset};
 use crate::index::{Column, IndexRange, Line, Point};
-use crate::term::cell::{Cell, Flags};
+use crate::term::cell::{Flags, ResetDiscriminant};
 
 pub mod resize;
 mod row;
@@ -49,25 +49,24 @@ impl<T: PartialEq> ::std::cmp::PartialEq for Grid<T> {
     }
 }
 
-pub trait GridCell {
+pub trait GridCell: Sized {
+    /// Check if the cell contains any content.
     fn is_empty(&self) -> bool;
+
+    /// Perform an opinionated cell reset based on a template cell.
+    fn reset(&mut self, template: &Self);
+
     fn flags(&self) -> &Flags;
     fn flags_mut(&mut self) -> &mut Flags;
-
-    /// Fast equality approximation.
-    ///
-    /// This is a faster alternative to [`PartialEq`],
-    /// but might report unequal cells as equal.
-    fn fast_eq(&self, other: Self) -> bool;
 }
 
-#[derive(Debug, Default, Copy, Clone, PartialEq, Eq)]
-pub struct Cursor {
+#[derive(Debug, Default, Clone, PartialEq, Eq)]
+pub struct Cursor<T> {
     /// The location of this cursor.
     pub point: Point,
 
     /// Template cell when using this cursor.
-    pub template: Cell,
+    pub template: T,
 
     /// Currently configured graphic character sets.
     pub charsets: Charsets,
@@ -131,11 +130,11 @@ impl IndexMut<CharsetIndex> for Charsets {
 pub struct Grid<T> {
     /// Current cursor for writing data.
     #[serde(skip)]
-    pub cursor: Cursor,
+    pub cursor: Cursor<T>,
 
     /// Last saved cursor.
     #[serde(skip)]
-    pub saved_cursor: Cursor,
+    pub saved_cursor: Cursor<T>,
 
     /// Lines in the grid. Each row holds a list of cells corresponding to the
     /// columns in that row.
@@ -167,10 +166,10 @@ pub enum Scroll {
     Bottom,
 }
 
-impl<T: GridCell + Default + PartialEq + Copy> Grid<T> {
-    pub fn new(lines: Line, cols: Column, max_scroll_limit: usize, template: T) -> Grid<T> {
+impl<T: GridCell + Default + PartialEq + Clone> Grid<T> {
+    pub fn new(lines: Line, cols: Column, max_scroll_limit: usize) -> Grid<T> {
         Grid {
-            raw: Storage::with_capacity(lines, Row::new(cols, template)),
+            raw: Storage::with_capacity(lines, cols),
             max_scroll_limit,
             display_offset: 0,
             saved_cursor: Cursor::default(),
@@ -203,10 +202,10 @@ impl<T: GridCell + Default + PartialEq + Copy> Grid<T> {
         };
     }
 
-    fn increase_scroll_limit(&mut self, count: usize, template: T) {
+    fn increase_scroll_limit(&mut self, count: usize) {
         let count = min(count, self.max_scroll_limit - self.history_size());
         if count != 0 {
-            self.raw.initialize(count, template, self.cols);
+            self.raw.initialize(count, self.cols);
         }
     }
 
@@ -219,7 +218,11 @@ impl<T: GridCell + Default + PartialEq + Copy> Grid<T> {
     }
 
     #[inline]
-    pub fn scroll_down(&mut self, region: &Range<Line>, positions: Line, template: T) {
+    pub fn scroll_down<D>(&mut self, region: &Range<Line>, positions: Line)
+    where
+        T: ResetDiscriminant<D>,
+        D: PartialEq,
+    {
         // Whether or not there is a scrolling region active, as long as it
         // starts at the top, we can do a full rotation which just involves
         // changing the start index.
@@ -238,7 +241,7 @@ impl<T: GridCell + Default + PartialEq + Copy> Grid<T> {
 
             // Finally, reset recycled lines.
             for i in IndexRange(Line(0)..positions) {
-                self.raw[i].reset(template);
+                self.raw[i].reset(&self.cursor.template);
             }
         } else {
             // Subregion rotation.
@@ -247,7 +250,7 @@ impl<T: GridCell + Default + PartialEq + Copy> Grid<T> {
             }
 
             for line in