Add damage tracking and reporting to compatible compositors

This allows compositors to only process damaged (that is, updated)
regions of our window buffer, which for larger window sizes (think 4k)
should significantly reduce compositing workload under compositors that
support/honor it, which is good for performance, battery life and lower
latency over remote connections like VNC.

On Wayland, clients are expected to always report correct damage, so
this makes us a good citizen there. It can also aid remote desktop
(waypipe, rdp, vnc, ...) and other types of screencopy by having damage
bubble up correctly.

Fixes #3186.

1 files changed, 86 insertions, 0 deletions

diff --git a/alacritty/src/display/damage.rs b/alacritty/src/display/damage.rs
new file mode 100644
index 00000000..d6a69a2d
--- /dev/null
+++ b/alacritty/src/display/damage.rs
@@ -0,0 +1,86 @@
+use std::cmp;
+use std::iter::Peekable;
+
+use glutin::Rect;
+
+use alacritty_terminal::term::{LineDamageBounds, SizeInfo, TermDamageIterator};
+
+/// Iterator which converts `alacritty_terminal` damage information into renderer damaged rects.
+pub struct RenderDamageIterator<'a> {
+    damaged_lines: Peekable<TermDamageIterator<'a>>,
+    size_info: SizeInfo<u32>,
+}
+
+impl<'a> RenderDamageIterator<'a> {
+    pub fn new(damaged_lines: TermDamageIterator<'a>, size_info: SizeInfo<u32>) -> Self {
+        Self { damaged_lines: damaged_lines.peekable(), size_info }
+    }
+
+    #[inline]
+    fn rect_for_line(&self, line_damage: LineDamageBounds) -> Rect {
+        let size_info = &self.size_info;
+        let y_top = size_info.height() - size_info.padding_y();
+        let x = size_info.padding_x() + line_damage.left as u32 * size_info.cell_width();
+        let y = y_top - (line_damage.line + 1) as u32 * size_info.cell_height();
+        let width = (line_damage.right - line_damage.left + 1) as u32 * size_info.cell_width();
+        Rect { x, y, height: size_info.cell_height(), width }
+    }
+
+    // Make sure to damage near cells to include wide chars.
+    #[inline]
+    fn overdamage(&self, mut rect: Rect) -> Rect {
+        let size_info = &self.size_info;
+        rect.x = rect.x.saturating_sub(size_info.cell_width());
+        rect.width = cmp::min(size_info.width() - rect.x, rect.width + 2 * size_info.cell_width());
+        rect.y = rect.y.saturating_sub(size_info.cell_height() / 2);
+        rect.height = cmp::min(size_info.height() - rect.y, rect.height + size_info.cell_height());
+
+        rect
+    }
+}
+
+impl<'a> Iterator for RenderDamageIterator<'a> {
+    type Item = Rect;
+
+    fn next(&mut self) -> Option<Rect> {
+        let line = self.damaged_lines.next()?;
+        let mut total_damage_rect = self.overdamage(self.rect_for_line(line));
+
+        // Merge rectangles which overlap with each other.
+        while let Some(line) = self.damaged_lines.peek().copied() {
+            let next_rect = self.overdamage(self.rect_for_line(line));
+            if !rects_overlap(total_damage_rect, next_rect) {
+                break;
+            }
+
+            total_damage_rect = merge_rects(total_damage_rect, next_rect);
+            let _ = self.damaged_lines.next();
+        }
+
+        Some(total_damage_rect)
+    }
+}
+
+/// Check if two given [`glutin::Rect`] overlap.
+fn rects_overlap(lhs: Rect, rhs: Rect) -> bool {
+    !(
+        // `lhs` is left of `rhs`.
+        lhs.x + lhs.width < rhs.x
+        // `lhs` is right of `rhs`.
+        || rhs.x + rhs.width < lhs.x
+        // `lhs` is below `rhs`.
+        || lhs.y + lhs.height < rhs.y
+        // `lhs` is above `rhs`.
+        || rhs.y + rhs.height < lhs.y
+    )
+}
+
+/// Merge two [`glutin::Rect`] by producing the smallest rectangle that contains both.
+#[inline]
+fn merge_rects(lhs: Rect, rhs: Rect) -> Rect {
+    let left_x = cmp::min(lhs.x, rhs.x);
+    let right_x = cmp::max(lhs.x + lhs.width, rhs.x + rhs.width);
+    let y_top = cmp::max(lhs.y + lhs.height, rhs.y + rhs.height);
+    let y_bottom = cmp::min(lhs.y, rhs.y);
+    Rect { x: left_x, y: y_bottom, width: right_x - left_x, height: y_top - y_bottom }
+}