//! Retained layer tree and damage tracking for minimal repaints. //! //! The layer tree maintains a persistent record of layout box state between //! frames. Each frame, it compares new layout boxes against previous state and //! computes damage rectangles — screen regions that need repainting. //! //! The GPU and software renderers can use these damage rects as scissor regions //! to avoid full-screen repaints when only small areas changed (e.g. cursor //! blink, hover effects). use std::collections::HashMap; use we_css::values::Color; use we_dom::NodeId; use we_layout::{LayoutBox, LayoutTree, Rect}; use we_style::computed::{Overflow, Position, Visibility}; use crate::{ build_display_list_into, node_id_from_box_type, DisplayList, PaintCommand, ScrollState, }; // --------------------------------------------------------------------------- // Damage rectangles // --------------------------------------------------------------------------- /// An axis-aligned damage rectangle in screen coordinates. #[derive(Debug, Clone, Copy, PartialEq)] pub struct DamageRect { pub x: f32, pub y: f32, pub width: f32, pub height: f32, } impl DamageRect { pub fn new(x: f32, y: f32, width: f32, height: f32) -> Self { Self { x, y, width, height, } } /// Create a damage rect from a layout `Rect`. pub fn from_rect(r: Rect) -> Self { Self { x: r.x, y: r.y, width: r.width, height: r.height, } } /// Union of two damage rects: the smallest rect containing both. pub fn union(self, other: DamageRect) -> DamageRect { let x0 = self.x.min(other.x); let y0 = self.y.min(other.y); let x1 = (self.x + self.width).max(other.x + other.width); let y1 = (self.y + self.height).max(other.y + other.height); DamageRect { x: x0, y: y0, width: x1 - x0, height: y1 - y0, } } /// Returns true if this rect has zero or negative area. pub fn is_empty(&self) -> bool { self.width <= 0.0 || self.height <= 0.0 } /// Returns true if this rect intersects with another. pub fn intersects(&self, other: &DamageRect) -> bool { self.x < other.x + other.width && self.x + self.width > other.x && self.y < other.y + other.height && self.y + self.height > other.y } /// Expand this rect by a margin on all sides. Used for merging nearby rects. pub fn expand(&self, margin: f32) -> DamageRect { DamageRect { x: self.x - margin, y: self.y - margin, width: self.width + margin * 2.0, height: self.height + margin * 2.0, } } } /// Merge a list of damage rects, coalescing nearby or overlapping ones to /// reduce draw calls. Two rects are merged if they overlap or are within /// `merge_threshold` pixels of each other. pub fn merge_damage_rects(rects: &[DamageRect], merge_threshold: f32) -> Vec { if rects.is_empty() { return Vec::new(); } let mut merged: Vec = Vec::new(); for &rect in rects { if rect.is_empty() { continue; } let mut did_merge = false; for existing in &mut merged { if existing.expand(merge_threshold).intersects(&rect) { *existing = existing.union(rect); did_merge = true; break; } } if !did_merge { merged.push(rect); } } // Second pass: merge any newly-overlapping rects created by the first pass. let mut stable = false; while !stable { stable = true; let mut i = 0; while i < merged.len() { let mut j = i + 1; while j < merged.len() { if merged[i].expand(merge_threshold).intersects(&merged[j]) { let b = merged.remove(j); merged[i] = merged[i].union(b); stable = false; } else { j += 1; } } i += 1; } } merged } // --------------------------------------------------------------------------- // Box fingerprint (for change detection) // --------------------------------------------------------------------------- /// A lightweight fingerprint of a layout box's paint-relevant properties. /// Used for fast comparison to detect changes between frames. #[derive(Debug, Clone, PartialEq)] struct BoxFingerprint { rect: Rect, background_color: Color, color: Color, opacity: f32, visibility: Visibility, overflow: Overflow, position: Position, z_index: Option, border_widths: [u32; 4], // stored as f32 bit patterns border_colors: [Color; 4], text_hash: u64, child_count: usize, content_height_bits: u32, } impl BoxFingerprint { fn from_layout_box(b: &LayoutBox) -> Self { let text_hash = b.lines.iter().fold(0u64, |acc, line| { let mut h = acc; for byte in line.text.as_bytes() { h = h.wrapping_mul(31).wrapping_add(*byte as u64); } h = h.wrapping_mul(31).wrapping_add(line.x.to_bits() as u64); h = h.wrapping_mul(31).wrapping_add(line.y.to_bits() as u64); h }); BoxFingerprint { rect: b.rect, background_color: b.background_color, color: b.color, opacity: b.opacity, visibility: b.visibility, overflow: b.overflow, position: b.position, z_index: b.z_index, border_widths: [ b.border.top.to_bits(), b.border.right.to_bits(), b.border.bottom.to_bits(), b.border.left.to_bits(), ], border_colors: b.border_colors, text_hash, child_count: b.children.len(), content_height_bits: b.content_height.to_bits(), } } /// Compute a damage rect from this fingerprint (border box approximation). fn damage_rect(&self) -> DamageRect { let bt = f32::from_bits(self.border_widths[0]); let br = f32::from_bits(self.border_widths[1]); let bb = f32::from_bits(self.border_widths[2]); let bl = f32::from_bits(self.border_widths[3]); DamageRect { x: self.rect.x - bl, y: self.rect.y - bt, width: self.rect.width + bl + br, height: self.rect.height + bt + bb, } } } // --------------------------------------------------------------------------- // Retained layer tree // --------------------------------------------------------------------------- /// Retained layer tree that persists between frames and tracks damage. /// /// On each frame, call [`update`] with the new layout tree. The layer tree /// compares the new layout against the previous frame's snapshot and produces /// a set of damage rects indicating which screen regions need repainting. /// /// For the first frame or after a full invalidation, [`damage_rects`] returns /// `None`, indicating that the entire viewport should be repainted. pub struct LayerTree { /// Previous frame's box fingerprints, keyed by NodeId. prev_fingerprints: HashMap, /// Collected damage rects from the most recent update. damage: Option>, /// Viewport dimensions. viewport_width: f32, viewport_height: f32, /// Whether this is the first frame (no previous state). first_frame: bool, /// The display list from the most recent frame. cached_display_list: DisplayList, /// Repaint metrics for debugging/testing. metrics: RepaintMetrics, } /// Metrics about what was repainted in the last frame. #[derive(Debug, Clone, Default)] pub struct RepaintMetrics { /// Number of damage rects produced. pub damage_rect_count: usize, /// Total area of damage rects (in px^2). pub damage_area: f32, /// Whether a full repaint was performed. pub full_repaint: bool, /// Number of boxes that changed between frames. pub changed_box_count: usize, } impl LayerTree { /// Create a new layer tree for the given viewport size. pub fn new(viewport_width: f32, viewport_height: f32) -> Self { Self { prev_fingerprints: HashMap::new(), damage: None, viewport_width, viewport_height, first_frame: true, cached_display_list: Vec::new(), metrics: RepaintMetrics::default(), } } /// Resize the viewport. Triggers a full repaint on the next frame. pub fn resize(&mut self, width: f32, height: f32) { if (self.viewport_width - width).abs() > 0.001 || (self.viewport_height - height).abs() > 0.001 { self.viewport_width = width; self.viewport_height = height; self.invalidate(); } } /// Force a full repaint on the next frame. pub fn invalidate(&mut self) { self.first_frame = true; self.damage = None; } /// Update the layer tree with a new layout. Computes damage rects by /// comparing the new layout against the previous frame's state. /// /// After calling this, use [`damage_rects`] to query which regions need /// repainting, and [`display_list`] to get the full display list. pub fn update(&mut self, tree: &LayoutTree, page_scroll_y: f32, scroll_state: &ScrollState) { // Reuse the display list buffer: clear and refill instead of drop and alloc. build_display_list_into( tree, page_scroll_y, scroll_state, &mut self.cached_display_list, ); if self.first_frame { let mut new_fingerprints = HashMap::new(); collect_fingerprints(&tree.root, &mut new_fingerprints); self.prev_fingerprints = new_fingerprints; self.first_frame = false; self.damage = None; self.metrics = RepaintMetrics { damage_rect_count: 0, damage_area: 0.0, full_repaint: true, changed_box_count: 0, }; return; } let mut new_fingerprints = HashMap::new(); collect_fingerprints(&tree.root, &mut new_fingerprints); let mut damage_rects = Vec::new(); let mut changed_count = 0; // Changed or new boxes. for (node_id, new_fp) in &new_fingerprints { match self.prev_fingerprints.get(node_id) { Some(old_fp) if old_fp == new_fp => {} Some(old_fp) => { changed_count += 1; let old_d = old_fp.damage_rect(); let new_d = new_fp.damage_rect(); if !old_d.is_empty() { damage_rects.push(old_d); } if !new_d.is_empty() { damage_rects.push(new_d); } } None => { changed_count += 1; let d = new_fp.damage_rect(); if !d.is_empty() { damage_rects.push(d); } } } } // Removed boxes. for (node_id, old_fp) in &self.prev_fingerprints { if !new_fingerprints.contains_key(node_id) { changed_count += 1; let d = old_fp.damage_rect(); if !d.is_empty() { damage_rects.push(d); } } } let merged = merge_damage_rects(&damage_rects, 16.0); let total_area: f32 = merged.iter().map(|r| r.width * r.height).sum(); self.metrics = RepaintMetrics { damage_rect_count: merged.len(), damage_area: total_area, full_repaint: false, changed_box_count: changed_count, }; let viewport_area = self.viewport_width * self.viewport_height; if viewport_area > 0.0 && total_area > viewport_area * 0.75 { self.metrics.full_repaint = true; self.damage = None; } else if merged.is_empty() { self.damage = Some(Vec::new()); } else { self.damage = Some(merged); } self.prev_fingerprints = new_fingerprints; } /// Get the damage rects from the most recent update. /// /// Returns `None` if a full repaint is needed (first frame, resize, or /// damage covers most of the viewport). Returns `Some(empty)` if nothing /// changed. Returns `Some(rects)` for partial damage. pub fn damage_rects(&self) -> Option<&[DamageRect]> { self.damage.as_deref() } /// Get the full display list from the most recent update. pub fn display_list(&self) -> &DisplayList { &self.cached_display_list } /// Get repaint metrics from the most recent frame. pub fn metrics(&self) -> &RepaintMetrics { &self.metrics } /// Check if any repaint is needed. Returns `false` only when zero damage. pub fn needs_repaint(&self) -> bool { match &self.damage { None => true, Some(rects) => !rects.is_empty(), } } /// Number of paint commands in the cached display list. pub fn display_list_command_count(&self) -> usize { self.cached_display_list.len() } /// Estimated heap bytes used by the layer tree. pub fn memory_usage(&self) -> usize { use std::mem::size_of; let fingerprints = self.prev_fingerprints.capacity() * (size_of::() + size_of::() + 8); let damage = self .damage .as_ref() .map_or(0, |v| v.capacity() * size_of::()); let display_list = self.cached_display_list.capacity() * size_of::(); let dl_strings: usize = self .cached_display_list .iter() .map(|cmd| match cmd { PaintCommand::DrawGlyphs { line, .. } => line.text.capacity(), _ => 0, }) .sum(); fingerprints + damage + display_list + dl_strings } } // --------------------------------------------------------------------------- // Helpers // --------------------------------------------------------------------------- /// Collect box fingerprints from the layout tree, keyed by NodeId. fn collect_fingerprints(b: &LayoutBox, out: &mut HashMap) { if let Some(id) = node_id_from_box_type(&b.box_type) { out.insert(id, BoxFingerprint::from_layout_box(b)); } for child in &b.children { collect_fingerprints(child, out); } } // --------------------------------------------------------------------------- // Tests // --------------------------------------------------------------------------- #[cfg(test)] mod tests { use super::*; // -- DamageRect tests --------------------------------------------------- #[test] fn damage_rect_union() { let a = DamageRect::new(10.0, 10.0, 20.0, 20.0); let b = DamageRect::new(25.0, 25.0, 20.0, 20.0); let u = a.union(b); assert_eq!(u.x, 10.0); assert_eq!(u.y, 10.0); assert_eq!(u.width, 35.0); assert_eq!(u.height, 35.0); } #[test] fn damage_rect_union_overlapping() { let a = DamageRect::new(0.0, 0.0, 50.0, 50.0); let b = DamageRect::new(10.0, 10.0, 20.0, 20.0); let u = a.union(b); assert_eq!(u.x, 0.0); assert_eq!(u.y, 0.0); assert_eq!(u.width, 50.0); assert_eq!(u.height, 50.0); } #[test] fn damage_rect_is_empty() { assert!(DamageRect::new(0.0, 0.0, 0.0, 10.0).is_empty()); assert!(DamageRect::new(0.0, 0.0, 10.0, 0.0).is_empty()); assert!(DamageRect::new(0.0, 0.0, -1.0, 10.0).is_empty()); assert!(!DamageRect::new(0.0, 0.0, 1.0, 1.0).is_empty()); } #[test] fn damage_rect_intersects() { let a = DamageRect::new(0.0, 0.0, 20.0, 20.0); let b = DamageRect::new(10.0, 10.0, 20.0, 20.0); assert!(a.intersects(&b)); let c = DamageRect::new(50.0, 50.0, 10.0, 10.0); assert!(!a.intersects(&c)); } #[test] fn damage_rect_expand() { let r = DamageRect::new(10.0, 10.0, 20.0, 20.0); let e = r.expand(5.0); assert_eq!(e.x, 5.0); assert_eq!(e.y, 5.0); assert_eq!(e.width, 30.0); assert_eq!(e.height, 30.0); } #[test] fn damage_rect_from_layout_rect() { let r = Rect { x: 5.0, y: 10.0, width: 100.0, height: 200.0, }; let d = DamageRect::from_rect(r); assert_eq!(d.x, 5.0); assert_eq!(d.y, 10.0); assert_eq!(d.width, 100.0); assert_eq!(d.height, 200.0); } // -- merge_damage_rects tests ------------------------------------------- #[test] fn merge_empty_rects() { let result = merge_damage_rects(&[], 16.0); assert!(result.is_empty()); } #[test] fn merge_single_rect() { let rects = vec![DamageRect::new(10.0, 10.0, 50.0, 50.0)]; let result = merge_damage_rects(&rects, 16.0); assert_eq!(result.len(), 1); assert_eq!(result[0].x, 10.0); } #[test] fn merge_overlapping_rects() { let rects = vec![ DamageRect::new(0.0, 0.0, 30.0, 30.0), DamageRect::new(20.0, 20.0, 30.0, 30.0), ]; let result = merge_damage_rects(&rects, 0.0); assert_eq!(result.len(), 1); assert_eq!(result[0].x, 0.0); assert_eq!(result[0].y, 0.0); assert_eq!(result[0].width, 50.0); assert_eq!(result[0].height, 50.0); } #[test] fn merge_nearby_rects() { let rects = vec![ DamageRect::new(0.0, 0.0, 20.0, 20.0), DamageRect::new(30.0, 0.0, 20.0, 20.0), ]; let result = merge_damage_rects(&rects, 16.0); assert_eq!(result.len(), 1); } #[test] fn merge_distant_rects_stay_separate() { let rects = vec![ DamageRect::new(0.0, 0.0, 20.0, 20.0), DamageRect::new(200.0, 200.0, 20.0, 20.0), ]; let result = merge_damage_rects(&rects, 16.0); assert_eq!(result.len(), 2); } #[test] fn merge_skips_empty_rects() { let rects = vec![ DamageRect::new(10.0, 10.0, 0.0, 0.0), DamageRect::new(20.0, 20.0, 30.0, 30.0), ]; let result = merge_damage_rects(&rects, 16.0); assert_eq!(result.len(), 1); assert_eq!(result[0].x, 20.0); } #[test] fn merge_chain_of_nearby_rects() { let rects = vec![ DamageRect::new(0.0, 0.0, 20.0, 20.0), DamageRect::new(30.0, 0.0, 20.0, 20.0), DamageRect::new(60.0, 0.0, 20.0, 20.0), ]; let result = merge_damage_rects(&rects, 16.0); assert_eq!(result.len(), 1); } // -- LayerTree tests (using real HTML parsing) -------------------------- use we_style::computed::{extract_stylesheets, resolve_styles}; use we_text::font::Font; fn test_font() -> Font { let paths = [ "/System/Library/Fonts/Geneva.ttf", "/System/Library/Fonts/Monaco.ttf", ]; for path in &paths { let p = std::path::Path::new(path); if p.exists() { return Font::from_file(p).expect("failed to parse font"); } } panic!("no test font found"); } fn layout_html(html: &str) -> LayoutTree { let font = test_font(); let doc = we_html::parse_html(html); let sheets = extract_stylesheets(&doc); let styled = resolve_styles(&doc, &sheets, (800.0, 600.0)).unwrap(); we_layout::layout( &styled, &doc, 800.0, 600.0, &font, &std::collections::HashMap::new(), ) } #[test] fn layer_tree_first_frame_full_repaint() { let lt = LayerTree::new(800.0, 600.0); assert!(lt.damage_rects().is_none()); assert!(lt.needs_repaint()); } #[test] fn layer_tree_resize_triggers_full_repaint() { let mut lt = LayerTree::new(800.0, 600.0); lt.first_frame = false; lt.damage = Some(Vec::new()); lt.resize(1024.0, 768.0); assert!(lt.damage_rects().is_none()); assert!(lt.needs_repaint()); } #[test] fn layer_tree_invalidate_triggers_full_repaint() { let mut lt = LayerTree::new(800.0, 600.0); lt.first_frame = false; lt.damage = Some(Vec::new()); lt.invalidate(); assert!(lt.damage_rects().is_none()); } #[test] fn layer_tree_identical_layout_no_damage() { let mut lt = LayerTree::new(800.0, 600.0); let scroll_state = HashMap::new(); let tree1 = layout_html("

Hello

"); lt.update(&tree1, 0.0, &scroll_state); assert!(lt.metrics().full_repaint); let tree2 = layout_html("

Hello

"); lt.update(&tree2, 0.0, &scroll_state); assert!(!lt.metrics().full_repaint); assert_eq!(lt.metrics().changed_box_count, 0); assert!(!lt.needs_repaint()); } #[test] fn layer_tree_detects_text_change() { let mut lt = LayerTree::new(800.0, 600.0); let scroll_state = HashMap::new(); let tree1 = layout_html("

Hello

"); lt.update(&tree1, 0.0, &scroll_state); let tree2 = layout_html("

World

"); lt.update(&tree2, 0.0, &scroll_state); assert!(lt.needs_repaint()); assert!(lt.metrics().changed_box_count >= 1); } #[test] fn layer_tree_detects_style_change() { let mut lt = LayerTree::new(800.0, 600.0); let scroll_state = HashMap::new(); let tree1 = layout_html( "

", ); lt.update(&tree1, 0.0, &scroll_state); let tree2 = layout_html( "

", ); lt.update(&tree2, 0.0, &scroll_state); assert!(lt.needs_repaint()); assert!(lt.metrics().changed_box_count >= 1); } #[test] fn layer_tree_detects_added_element() { let mut lt = LayerTree::new(800.0, 600.0); let scroll_state = HashMap::new(); let tree1 = layout_html("

One

"); lt.update(&tree1, 0.0, &scroll_state); let tree2 = layout_html("

One

Two

"); lt.update(&tree2, 0.0, &scroll_state); assert!(lt.needs_repaint()); assert!(lt.metrics().changed_box_count >= 1); } #[test] fn layer_tree_detects_removed_element() { let mut lt = LayerTree::new(800.0, 600.0); let scroll_state = HashMap::new(); let tree1 = layout_html("

One

Two

"); lt.update(&tree1, 0.0, &scroll_state); let tree2 = layout_html("

One

"); lt.update(&tree2, 0.0, &scroll_state); assert!(lt.needs_repaint()); assert!(lt.metrics().changed_box_count >= 1); } #[test] fn layer_tree_display_list_always_available() { let mut lt = LayerTree::new(800.0, 600.0); let scroll_state = HashMap::new(); let tree = layout_html("

Test

"); lt.update(&tree, 0.0, &scroll_state); assert!(!lt.display_list().is_empty()); } #[test] fn layer_tree_damage_covers_changed_region() { let mut lt = LayerTree::new(800.0, 600.0); let scroll_state = HashMap::new(); // Two distinct divs at known positions. let tree1 = layout_html(concat!( "", "

", "

", "" )); lt.update(&tree1, 0.0, &scroll_state); // Change only the second div's background. let tree2 = layout_html(concat!( "", "

", "

", "" )); lt.update(&tree2, 0.0, &scroll_state); assert!(lt.needs_repaint()); let rects = lt.damage_rects(); // Should have damage, not a full repaint for this small change. assert!(rects.is_some()); } #[test] fn layer_tree_metrics_accurate_on_no_change() { let mut lt = LayerTree::new(800.0, 600.0); let scroll_state = HashMap::new(); let tree = layout_html("Static"); lt.update(&tree, 0.0, &scroll_state); assert!(lt.metrics().full_repaint); let tree2 = layout_html("Static"); lt.update(&tree2, 0.0, &scroll_state); assert!(!lt.metrics().full_repaint); assert_eq!(lt.metrics().damage_rect_count, 0); assert_eq!(lt.metrics().damage_area, 0.0); } }