Allow overlapping graphics.

If a graphic is added over another one, the implementation now checks if new
graphic has transparent pixels in every cell. If so, the graphic is appended to
the cell, instead of replacing the previous one.

SmallVec is used to prevent heap allocation when the cell only contains a single
graphic. This should be the most common scenario.

The GPU will store up to 100 textures. If another texture is added when there
are 100, the oldest one is deleted.

10 files changed, 178 insertions, 39 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 45407391..22d61dfc 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -37,6 +37,7 @@ dependencies = [
  "serde",
  "serde_json",
  "serde_yaml",
+ "smallvec",
  "unicode-width",
  "wayland-client",
  "winapi 0.3.9",
@@ -78,6 +79,7 @@ dependencies = [
  "serde_yaml",
  "signal-hook",
  "signal-hook-mio",
+ "smallvec",
  "unicode-width",
  "vte",
  "winapi 0.3.9",
@@ -1528,9 +1530,9 @@ checksum = "eb703cfe953bccee95685111adeedb76fabe4e97549a58d16f03ea7b9367bb32"
 
 [[package]]
 name = "smallvec"
-version = "1.8.0"
+version = "1.9.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "f2dd574626839106c320a323308629dcb1acfc96e32a8cba364ddc61ac23ee83"
+checksum = "2fd0db749597d91ff862fd1d55ea87f7855a744a8425a64695b6fca237d1dad1"
 
 [[package]]
 name = "smithay-client-toolkit"
diff --git a/alacritty/Cargo.toml b/alacritty/Cargo.toml
index e93723bc..73510e2d 100644
--- a/alacritty/Cargo.toml
+++ b/alacritty/Cargo.toml
@@ -36,6 +36,7 @@ bitflags = "1"
 memoffset = "0.6.4"
 dirs = "4.0.0"
 once_cell = "1.12"
+smallvec = { version = "1.9.0", default-features = false }
 
 [build-dependencies]
 gl_generator = "0.14.0"
diff --git a/alacritty/src/display/content.rs b/alacritty/src/display/content.rs
index 9e179009..82644018 100644
--- a/alacritty/src/display/content.rs
+++ b/alacritty/src/display/content.rs
@@ -19,6 +19,8 @@ use crate::display::hint::{self, HintState};
 use crate::display::Display;
 use crate::event::SearchState;
 
+use smallvec::SmallVec;
+
 /// Minimum contrast between a fixed cursor color and the cell's background.
 pub const MIN_CURSOR_CONTRAST: f64 = 1.5;
 
@@ -209,7 +211,7 @@ pub struct RenderableGraphicCell {
 pub struct RenderableCellExtra {
     pub zerowidth: Option<Vec<char>>,
     pub hyperlink: Option<Hyperlink>,
-    pub graphic: Option<RenderableGraphicCell>,
+    pub graphics: Option<SmallVec<[RenderableGraphicCell; 1]>>,
 }
 
 impl RenderableCell {
@@ -282,17 +284,22 @@ impl RenderableCell {
         let zerowidth = cell.zerowidth();
         let hyperlink = cell.hyperlink();
 
-        let graphic = cell.graphic().map(|graphic| RenderableGraphicCell {
-            id: graphic.texture.id,
-            offset_x: graphic.offset_x,
-            offset_y: graphic.offset_y,
+        let graphics = cell.graphics().map(|graphics| {
+            graphics
+                .iter()
+                .map(|graphic| RenderableGraphicCell {
+                    id: graphic.texture.id,
+                    offset_x: graphic.offset_x,
+                    offset_y: graphic.offset_y,
+                })
+                .collect::<_>()
         });
 
         let extra = (zerowidth.is_some() || hyperlink.is_some()).then(|| {
             Box::new(RenderableCellExtra {
                 zerowidth: zerowidth.map(|zerowidth| zerowidth.to_vec()),
                 hyperlink,
-                graphic,
+                graphics,
             })
         });
 
diff --git a/alacritty/src/renderer/graphics/draw.rs b/alacritty/src/renderer/graphics/draw.rs
index f9207823..5f04a267 100644
--- a/alacritty/src/renderer/graphics/draw.rs
+++ b/alacritty/src/renderer/graphics/draw.rs
@@ -44,25 +44,27 @@ impl RenderList {
     /// The graphic is added only the first time it is found in a cell.
     #[inline]
     pub fn update(&mut self, cell: &RenderableCell, show_hint: bool) {
-        let graphic = match cell.extra.as_ref().and_then(|cell| cell.graphic.as_ref()) {
-            Some(graphic) => graphic,
+        let graphics = match cell.extra.as_ref().and_then(|cell| cell.graphics.as_ref()) {
+            Some(graphics) => graphics,
             _ => return,
         };
 
-        if self.items.contains_key(&graphic.id) {
-            return;
-        }
+        for graphic in graphics {
+            if self.items.contains_key(&graphic.id) {
+                continue;
+            }
 
-        let render_item = RenderPosition {
-            column: cell.point.column,
-            line: cell.point.line,
-            offset_x: graphic.offset_x,
-            offset_y: graphic.offset_y,
-            cell_color: cell.fg,
-            show_hint,
-        };
+            let render_item = RenderPosition {
+                column: cell.point.column,
+                line: cell.point.line,
+                offset_x: graphic.offset_x,
+                offset_y: graphic.offset_y,
+                cell_color: cell.fg,
+                show_hint,
+            };
 
-        self.items.insert(graphic.id, render_item);
+            self.items.insert(graphic.id, render_item);
+        }
     }
 
     /// Returns `true` if there are no items to render.
diff --git a/alacritty/src/renderer/graphics/mod.rs b/alacritty/src/renderer/graphics/mod.rs
index cb6a1c9e..5a6c59a7 100644
--- a/alacritty/src/renderer/graphics/mod.rs
+++ b/alacritty/src/renderer/graphics/mod.rs
@@ -22,6 +22,9 @@ use std::ffi::CStr;
 mod draw;
 mod shader;
 
+/// Max. number of textures stored in the GPU.
+const MAX_TEXTURES_COUNT: usize = 100;
+
 pub use draw::RenderList;
 
 bitflags::bitflags! {
@@ -125,11 +128,9 @@ impl GraphicsRenderer {
         graphics: Vec<GraphicData>,
         size_info: &SizeInfo,
     ) -> UpdateResult {
-        let result = if graphics.is_empty() {
-            UpdateResult::SUCCESS
-        } else {
-            UpdateResult::NEED_RESET_ACTIVE_TEX
-        };
+        if graphics.is_empty() {
+            return UpdateResult::SUCCESS;
+        }
 
         for graphic in graphics {
             let mut texture = 0;
@@ -176,7 +177,15 @@ impl GraphicsRenderer {
             self.graphic_textures.insert(graphic.id, graphic_texture);
         }
 
-        result
+        // If we exceed the textures limit, discard the oldest ones.
+        while self.graphic_textures.len() > MAX_TEXTURES_COUNT {
+            match self.graphic_textures.keys().min().copied() {
+                Some(id) => self.graphic_textures.remove(&id),
+                None => unreachable!(),
+            };
+        }
+
+        UpdateResult::NEED_RESET_ACTIVE_TEX
     }
 
     /// Update textures in the GPU to clear specific subregions.
diff --git a/alacritty_terminal/Cargo.toml b/alacritty_terminal/Cargo.toml
index e758009c..f1c1e50f 100644
--- a/alacritty_terminal/Cargo.toml
+++ b/alacritty_terminal/Cargo.toml
@@ -27,6 +27,7 @@ unicode-width = "0.1"
 base64 = "0.13.0"
 regex-automata = "0.1.9"
 dirs = "4.0.0"
+smallvec = { version = "1.9.0", default-features = false }
 
 [target.'cfg(unix)'.dependencies]
 nix = "0.22.0"
diff --git a/alacritty_terminal/src/graphics/mod.rs b/alacritty_terminal/src/graphics/mod.rs
index 846d866c..175dce77 100644
--- a/alacritty_terminal/src/graphics/mod.rs
+++ b/alacritty_terminal/src/graphics/mod.rs
@@ -8,6 +8,7 @@ use std::sync::{Arc, Weak};
 
 use parking_lot::Mutex;
 use serde::{Deserialize, Serialize};
+use smallvec::SmallVec;
 
 use crate::grid::Dimensions;
 use crate::term::color::Rgb;
@@ -49,6 +50,9 @@ impl Drop for TextureRef {
     }
 }
 
+/// A list of graphics in a single cell.
+pub type GraphicsCell = SmallVec<[GraphicCell; 1]>;
+
 /// Graphic data stored in a single cell.
 #[derive(Clone, Debug)]
 pub struct GraphicCell {
@@ -123,6 +127,39 @@ pub struct GraphicData {
 
     /// Pixels data.
     pub pixels: Vec<u8>,
+
+    /// Indicate if there are no transparent pixels.
+    pub is_opaque: bool,
+}
+
+impl GraphicData {
+    /// Check if all pixels under a region are opaque.
+    pub fn is_filled(&self, x: usize, y: usize, width: usize, height: usize) -> bool {
+        // If there are pixels outside the picture we assume that the region is
+        // not filled.
+        if x + width >= self.width || y + height > self.height {
+            return false;
+        }
+
+        // Don't check actual pixels if the image does not contain an alpha
+        // channel.
+        if self.is_opaque || self.color_type == ColorType::Rgb {
+            return true;
+        }
+
+        debug_assert!(self.color_type == ColorType::Rgba);
+
+        for offset_y in y..y + height {
+            let offset = offset_y * self.width * 4;
+            let row = &self.pixels[offset..offset + width * 4];
+
+            if row.chunks_exact(4).any(|pixel| pixel.last() != Some(&255)) {
+                return false;
+            }
+        }
+
+        true
+    }
 }
 
 /// Operation to clear a subregion in an existing graphic.
@@ -226,3 +263,40 @@ impl Graphics {
         self.cell_width = size.cell_width();
     }
 }
+
+#[test]
+fn check_opaque_region() {
+    let graphic = GraphicData {
+        id: GraphicId(0),
+        width: 10,
+        height: 10,
+        color_type: ColorType::Rgb,
+        pixels: vec![255; 10 * 10 * 3],
+        is_opaque: true,
+    };
+
+    assert_eq!(graphic.is_filled(1, 1, 3, 3), true);
+    assert_eq!(graphic.is_filled(8, 8, 10, 10), false);
+
+    let pixels = {
+        // Put a transparent 3x3 box inside the picture.
+        let mut data = vec![255; 10 * 10 * 4];
+        for y in 3..6 {
+            let offset = y * 10 * 4;
+            data[offset..offset + 3 * 4].fill(0);
+        }
+        data
+    };
+
+    let graphic = GraphicData {
+        id: GraphicId(0),
+        pixels,
+        width: 10,
+        height: 10,
+        color_type: ColorType::Rgba,
+        is_opaque: false,
+    };
+
+    assert_eq!(graphic.is_filled(0, 0, 3, 3), true);
+    assert_eq!(graphic.is_filled(1, 1, 4, 4), false);
+}
diff --git a/alacritty_terminal/src/graphics/sixel.rs b/alacritty_terminal/src/graphics/sixel.rs
index c243501b..a3a13886 100644
--- a/alacritty_terminal/src/graphics/sixel.rs
+++ b/alacritty_terminal/src/graphics/sixel.rs
@@ -485,9 +485,12 @@ impl Parser {
 
         let mut rgba_pixels = Vec::with_capacity(self.pixels.len() * 4);
 
+        let mut is_opaque = true;
+
         for &register in &self.pixels {
             let pixel = {
                 if register == REG_TRANSPARENT {
+                    is_opaque = false;
                     [0; 4]
                 } else {
                     match self.color_registers.get(register.0 as usize) {
@@ -506,6 +509,7 @@ impl Parser {
             width: self.width,
             color_type: ColorType::Rgba,
             pixels: rgba_pixels,
+            is_opaque,
         };
 
         Ok((data, self.color_registers))
@@ -699,6 +703,9 @@ mod tests {
             }
         }
 
+        let graphics = parser.finish()?.0;
+        assert_eq!(graphics.is_opaque, false);
+
         Ok(())
     }
 
@@ -770,6 +777,7 @@ mod tests {
             };
 
             assert_eq!(graphics.pixels, expected_rgba);
+            assert_eq!(graphics.is_opaque, true);
         }
     }
 }
diff --git a/alacritty_terminal/src/term/cell.rs b/alacritty_terminal/src/term/cell.rs
index 99b7eef4..7756bfa0 100644
--- a/alacritty_terminal/src/term/cell.rs
+++ b/alacritty_terminal/src/term/cell.rs
@@ -5,7 +5,7 @@ use bitflags::bitflags;
 use serde::{Deserialize, Serialize};
 
 use crate::ansi::{Color, NamedColor};
-use crate::graphics::GraphicCell;
+use crate::graphics::GraphicsCell;
 use crate::grid::{self, GridCell};
 use crate::index::Column;
 
@@ -115,7 +115,7 @@ pub struct CellExtra {
     hyperlink: Option<Hyperlink>,
 
     #[serde(skip)]
-    graphic: Option<Box<GraphicCell>>,
+    graphics: Option<GraphicsCell>,
 }
 
 /// Content and attributes of a single cell in the terminal grid.
@@ -157,15 +157,27 @@ impl Cell {
 
     /// Graphic present in the cell.
     #[inline]
-    pub fn graphic(&self) -> Option<&GraphicCell> {
-        self.extra.as_deref().and_then(|extra| extra.graphic.as_deref())
+    pub fn graphics(&self) -> Option<&GraphicsCell> {
+        self.extra.as_deref().and_then(|extra| extra.graphics.as_ref())
+    }
+
+    /// Extract the graphics value from the cell.
+    #[inline]
+    pub fn take_graphics(&mut self) -> Option<GraphicsCell> {
+        if let Some(extra) = &mut self.extra {
+            if extra.graphics.is_some() {
+                return Arc::make_mut(extra).graphics.take();
+            }
+        }
+
+        None
     }
 
     /// Write the graphic data in the cell.
     #[inline]
-    pub fn set_graphic(&mut self, graphic_cell: GraphicCell) {
+    pub fn set_graphics(&mut self, graphics_cell: GraphicsCell) {
         let extra = self.extra.get_or_insert_with(Default::default);
-        Arc::make_mut(extra).graphic = Some(Box::new(graphic_cell));
+        Arc::make_mut(extra).graphics = Some(graphics_cell);
 
         self.flags_mut().insert(Flags::GRAPHICS);
     }
diff --git a/alacritty_terminal/src/term/mod.rs b/alacritty_terminal/src/term/mod.rs
index 65ced9ee..5de2695d 100644
--- a/alacritty_terminal/src/term/mod.rs
+++ b/alacritty_terminal/src/term/mod.rs
@@ -2053,9 +2053,7 @@ impl<T: EventListener> Handler for Term<T> {
             return;
         }
 
-        // Add the graphic data to the pending queue.
         let graphic_id = self.graphics.next_id();
-        self.graphics.pending.push(GraphicData { id: graphic_id, ..graphic });
 
         // If SIXEL_DISPLAY is disabled, the start of the graphic is the
         // cursor position, and the grid can be scrolled if the graphic is
@@ -2107,12 +2105,34 @@ impl<T: EventListener> Handler for Term<T> {
                     offset_y,
                     texture_operations,
                 };
+
                 let mut cell = self.grid.cursor.template.clone();
-                cell.set_graphic(graphic_cell);
-                self.grid[line][Column(left)] = cell;
+                let cell_ref = &mut self.grid[line][Column(left)];
+
+                // If the cell contains any graphics, and the region of the cell
+                // is not fully filled by the new graphic, the old graphics are
+                // kept in the cell
+                let graphics = loop {
+                    if let Some(mut old_graphics) = cell_ref.take_graphics() {
+                        if !graphic.is_filled(
+                            offset_x as usize,
+                            offset_y as usize,
+                            cell_width as usize,
+                            cell_height as usize,
+                        ) {
+                            old_graphics.push(graphic_cell);
+                            break old_graphics;
+                        }
+                    }
+
+                    break smallvec::smallvec![graphic_cell];
+                };
+
+                cell.set_graphics(graphics);
+                *cell_ref = cell;
             }
 
-            if scrolling && offset_y < height - cell_height as u16 {
+            if scrolling && offset_y < height.saturating_sub(cell_height as u16) {
                 self.linefeed();
             }
         }
@@ -2124,6 +2144,9 @@ impl<T: EventListener> Handler for Term<T> {
             self.linefeed();
             self.carriage_return();
         }
+
+        // Add the graphic data to the pending queue.
+        self.graphics.pending.push(GraphicData { id: graphic_id, ..graphic });
     }
 }