veridian_kernel/browser/
incremental.rs

1//! Incremental Layout and Rendering
2//!
3//! Tracks dirty nodes and damage regions to avoid full re-layout and
4//! re-paint on every DOM change. Uses per-node dirty flags and
5//! rectangular damage regions.
6
7#![allow(dead_code)]
8
9use alloc::{collections::BTreeMap, vec::Vec};
10
11use super::events::NodeId;
12
13// ---------------------------------------------------------------------------
14// Dirty flags
15// ---------------------------------------------------------------------------
16
17/// Dirty state of a node, ordered by severity
18#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Default)]
19pub enum DirtyFlag {
20    /// No changes needed
21    #[default]
22    Clean = 0,
23    /// Only painting is out of date (e.g., color changed)
24    PaintDirty = 1,
25    /// Layout needs recomputation (size/position changed)
26    LayoutDirty = 2,
27    /// Style needs resolution (class/attribute changed)
28    StyleDirty = 3,
29}
30
31// ---------------------------------------------------------------------------
32// Dirty tracker
33// ---------------------------------------------------------------------------
34
35/// Tracks per-node dirty state for incremental updates
36pub struct DirtyTracker {
37    /// Per-node dirty flags
38    flags: BTreeMap<NodeId, DirtyFlag>,
39    /// Parent map for propagating dirty state upward
40    parents: BTreeMap<NodeId, NodeId>,
41    /// Number of dirty nodes
42    dirty_count: usize,
43}
44
45impl Default for DirtyTracker {
46    fn default() -> Self {
47        Self::new()
48    }
49}
50
51impl DirtyTracker {
52    pub fn new() -> Self {
53        Self {
54            flags: BTreeMap::new(),
55            parents: BTreeMap::new(),
56            dirty_count: 0,
57        }
58    }
59
60    /// Register a parent relationship
61    pub(crate) fn set_parent(&mut self, child: NodeId, parent: NodeId) {
62        self.parents.insert(child, parent);
63    }
64
65    /// Remove a node from tracking
66    pub(crate) fn remove_node(&mut self, node: NodeId) {
67        if let Some(flag) = self.flags.remove(&node) {
68            if flag != DirtyFlag::Clean {
69                self.dirty_count = self.dirty_count.saturating_sub(1);
70            }
71        }
72        self.parents.remove(&node);
73    }
74
75    /// Mark a node as dirty with the given severity.
76    /// Propagates LayoutDirty/StyleDirty upward to ancestors.
77    pub(crate) fn mark_dirty(&mut self, node: NodeId, flag: DirtyFlag) {
78        if flag == DirtyFlag::Clean {
79            return;
80        }
81
82        // Set or upgrade the flag
83        let current = self.flags.get(&node).copied().unwrap_or(DirtyFlag::Clean);
84        if flag > current {
85            if current == DirtyFlag::Clean {
86                self.dirty_count += 1;
87            }
88            self.flags.insert(node, flag);
89        }
90
91        // Propagate upward: ancestors need at least LayoutDirty
92        if flag >= DirtyFlag::LayoutDirty {
93            let mut current_node = node;
94            while let Some(&parent) = self.parents.get(&current_node) {
95                let parent_flag = self.flags.get(&parent).copied().unwrap_or(DirtyFlag::Clean);
96                if parent_flag >= DirtyFlag::LayoutDirty {
97                    break; // Already dirty enough
98                }
99                if parent_flag == DirtyFlag::Clean {
100                    self.dirty_count += 1;
101                }
102                self.flags.insert(parent, DirtyFlag::LayoutDirty);
103                current_node = parent;
104            }
105        }
106    }
107
108    /// Mark a node as style-dirty (strongest)
109    pub(crate) fn mark_style_dirty(&mut self, node: NodeId) {
110        self.mark_dirty(node, DirtyFlag::StyleDirty);
111    }
112
113    /// Mark a node as layout-dirty
114    pub(crate) fn mark_layout_dirty(&mut self, node: NodeId) {
115        self.mark_dirty(node, DirtyFlag::LayoutDirty);
116    }
117
118    /// Mark a node as paint-dirty
119    pub(crate) fn mark_paint_dirty(&mut self, node: NodeId) {
120        self.mark_dirty(node, DirtyFlag::PaintDirty);
121    }
122
123    /// Get the dirty flag for a node
124    pub(crate) fn get_flag(&self, node: NodeId) -> DirtyFlag {
125        self.flags.get(&node).copied().unwrap_or(DirtyFlag::Clean)
126    }
127
128    /// Whether a node needs restyle
129    pub(crate) fn needs_restyle(&self, node: NodeId) -> bool {
130        self.get_flag(node) >= DirtyFlag::StyleDirty
131    }
132
133    /// Whether a node needs relayout
134    pub(crate) fn needs_relayout(&self, node: NodeId) -> bool {
135        self.get_flag(node) >= DirtyFlag::LayoutDirty
136    }
137
138    /// Whether a node needs repaint
139    pub(crate) fn needs_repaint(&self, node: NodeId) -> bool {
140        self.get_flag(node) >= DirtyFlag::PaintDirty
141    }
142
143    /// Clear a specific node's dirty flag
144    pub(crate) fn clear(&mut self, node: NodeId) {
145        if let Some(flag) = self.flags.get_mut(&node) {
146            if *flag != DirtyFlag::Clean {
147                *flag = DirtyFlag::Clean;
148                self.dirty_count = self.dirty_count.saturating_sub(1);
149            }
150        }
151    }
152
153    /// Clear all dirty flags
154    pub(crate) fn clear_all(&mut self) {
155        for flag in self.flags.values_mut() {
156            *flag = DirtyFlag::Clean;
157        }
158        self.dirty_count = 0;
159    }
160
161    /// Whether any nodes are dirty
162    pub(crate) fn has_dirty_nodes(&self) -> bool {
163        self.dirty_count > 0
164    }
165
166    /// Number of dirty nodes
167    pub(crate) fn dirty_node_count(&self) -> usize {
168        self.dirty_count
169    }
170
171    /// Get all nodes with at least the given dirty level, sorted by node ID
172    pub(crate) fn dirty_nodes(&self, min_flag: DirtyFlag) -> Vec<NodeId> {
173        self.flags
174            .iter()
175            .filter(|(_, &flag)| flag >= min_flag)
176            .map(|(&node, _)| node)
177            .collect()
178    }
179
180    /// Find the highest dirty ancestor of a node (the subtree root to
181    /// re-process)
182    pub(crate) fn highest_dirty_ancestor(&self, node: NodeId, min_flag: DirtyFlag) -> NodeId {
183        let mut highest = node;
184        let mut current = node;
185        while let Some(&parent) = self.parents.get(&current) {
186            if self.get_flag(parent) >= min_flag {
187                highest = parent;
188            }
189            current = parent;
190        }
191        highest
192    }
193}
194
195// ---------------------------------------------------------------------------
196// Damage region
197// ---------------------------------------------------------------------------
198
199/// A rectangular damage region in pixel coordinates
200#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
201pub struct DamageRegion {
202    pub x: i32,
203    pub y: i32,
204    pub width: i32,
205    pub height: i32,
206}
207
208impl DamageRegion {
209    pub fn new(x: i32, y: i32, width: i32, height: i32) -> Self {
210        Self {
211            x,
212            y,
213            width: width.max(0),
214            height: height.max(0),
215        }
216    }
217
218    /// Whether this region is empty (zero area)
219    pub(crate) fn is_empty(&self) -> bool {
220        self.width <= 0 || self.height <= 0
221    }
222
223    /// Right edge
224    pub(crate) fn right(&self) -> i32 {
225        self.x + self.width
226    }
227
228    /// Bottom edge
229    pub(crate) fn bottom(&self) -> i32 {
230        self.y + self.height
231    }
232
233    /// Area in pixels
234    pub(crate) fn area(&self) -> i64 {
235        self.width as i64 * self.height as i64
236    }
237
238    /// Union with another region (bounding box)
239    pub(crate) fn union(&self, other: &DamageRegion) -> DamageRegion {
240        if self.is_empty() {
241            return *other;
242        }
243        if other.is_empty() {
244            return *self;
245        }
246        let x = self.x.min(other.x);
247        let y = self.y.min(other.y);
248        let r = self.right().max(other.right());
249        let b = self.bottom().max(other.bottom());
250        DamageRegion::new(x, y, r - x, b - y)
251    }
252
253    /// Intersection with another region
254    pub(crate) fn intersect(&self, other: &DamageRegion) -> DamageRegion {
255        let x = self.x.max(other.x);
256        let y = self.y.max(other.y);
257        let r = self.right().min(other.right());
258        let b = self.bottom().min(other.bottom());
259        if r <= x || b <= y {
260            DamageRegion::default()
261        } else {
262            DamageRegion::new(x, y, r - x, b - y)
263        }
264    }
265
266    /// Whether this region fully contains another
267    pub(crate) fn contains(&self, other: &DamageRegion) -> bool {
268        self.x <= other.x
269            && self.y <= other.y
270            && self.right() >= other.right()
271            && self.bottom() >= other.bottom()
272    }
273
274    /// Whether this region contains a point
275    pub(crate) fn contains_point(&self, px: i32, py: i32) -> bool {
276        px >= self.x && px < self.right() && py >= self.y && py < self.bottom()
277    }
278}
279
280// ---------------------------------------------------------------------------
281// Damage list (accumulator of damage regions)
282// ---------------------------------------------------------------------------
283
284/// Accumulates damage regions and merges them
285pub struct DamageList {
286    /// Individual damage regions
287    regions: Vec<DamageRegion>,
288    /// Bounding box of all damage
289    bounds: DamageRegion,
290    /// Maximum number of regions before merging all into bounding box
291    max_regions: usize,
292}
293
294impl Default for DamageList {
295    fn default() -> Self {
296        Self::new()
297    }
298}
299
300impl DamageList {
301    pub fn new() -> Self {
302        Self {
303            regions: Vec::new(),
304            bounds: DamageRegion::default(),
305            max_regions: 32,
306        }
307    }
308
309    /// Add a damage region
310    pub(crate) fn add(&mut self, region: DamageRegion) {
311        if region.is_empty() {
312            return;
313        }
314        self.bounds = self.bounds.union(&region);
315        self.regions.push(region);
316
317        // Merge if too many regions
318        if self.regions.len() > self.max_regions {
319            self.merge_all();
320        }
321    }
322
323    /// Merge all regions into a single bounding box
324    pub(crate) fn merge_all(&mut self) {
325        if !self.regions.is_empty() {
326            self.regions.clear();
327            self.regions.push(self.bounds);
328        }
329    }
330
331    /// Get the bounding box of all damage
332    pub(crate) fn bounding_box(&self) -> DamageRegion {
333        self.bounds
334    }
335
336    /// Get individual damage regions
337    pub(crate) fn regions(&self) -> &[DamageRegion] {
338        &self.regions
339    }
340
341    /// Whether there is any damage
342    pub(crate) fn has_damage(&self) -> bool {
343        !self.regions.is_empty()
344    }
345
346    /// Clear all damage
347    pub(crate) fn clear(&mut self) {
348        self.regions.clear();
349        self.bounds = DamageRegion::default();
350    }
351
352    /// Check if a rectangle overlaps with any damage region
353    pub(crate) fn overlaps(&self, region: &DamageRegion) -> bool {
354        // Quick check against bounding box first
355        if self.bounds.intersect(region).is_empty() {
356            return false;
357        }
358        self.regions.iter().any(|r| !r.intersect(region).is_empty())
359    }
360}
361
362// ---------------------------------------------------------------------------
363// Incremental layout engine
364// ---------------------------------------------------------------------------
365
366/// Coordinates incremental restyle, relayout, and repaint
367pub struct IncrementalLayout {
368    /// Dirty tracker
369    pub tracker: DirtyTracker,
370    /// Accumulated damage regions
371    pub damage: DamageList,
372    /// Node-to-rect mapping (filled during layout)
373    node_rects: BTreeMap<NodeId, DamageRegion>,
374}
375
376impl Default for IncrementalLayout {
377    fn default() -> Self {
378        Self::new()
379    }
380}
381
382impl IncrementalLayout {
383    pub fn new() -> Self {
384        Self {
385            tracker: DirtyTracker::new(),
386            damage: DamageList::new(),
387            node_rects: BTreeMap::new(),
388        }
389    }
390
391    /// Register a node's layout rectangle (called after layout pass)
392    pub(crate) fn set_node_rect(&mut self, node: NodeId, x: i32, y: i32, w: i32, h: i32) {
393        self.node_rects.insert(node, DamageRegion::new(x, y, w, h));
394    }
395
396    /// Get a node's layout rectangle
397    pub(crate) fn node_rect(&self, node: NodeId) -> Option<DamageRegion> {
398        self.node_rects.get(&node).copied()
399    }
400
401    /// Remove a node's rect
402    pub(crate) fn remove_node_rect(&mut self, node: NodeId) {
403        self.node_rects.remove(&node);
404    }
405
406    /// Get nodes that need restyle, returning the highest dirty ancestors
407    /// to minimize redundant work
408    pub(crate) fn restyle_roots(&self) -> Vec<NodeId> {
409        let dirty = self.tracker.dirty_nodes(DirtyFlag::StyleDirty);
410        let mut roots = Vec::new();
411        for &node in &dirty {
412            let root = self
413                .tracker
414                .highest_dirty_ancestor(node, DirtyFlag::StyleDirty);
415            if !roots.contains(&root) {
416                roots.push(root);
417            }
418        }
419        roots
420    }
421
422    /// Get subtree roots that need relayout
423    pub(crate) fn relayout_roots(&self) -> Vec<NodeId> {
424        let dirty = self.tracker.dirty_nodes(DirtyFlag::LayoutDirty);
425        let mut roots = Vec::new();
426        for &node in &dirty {
427            let root = self
428                .tracker
429                .highest_dirty_ancestor(node, DirtyFlag::LayoutDirty);
430            if !roots.contains(&root) {
431                roots.push(root);
432            }
433        }
434        roots
435    }
436
437    /// Mark damage for all nodes that need repaint
438    pub(crate) fn compute_damage(&mut self) {
439        let paint_dirty = self.tracker.dirty_nodes(DirtyFlag::PaintDirty);
440        for &node in &paint_dirty {
441            if let Some(rect) = self.node_rects.get(&node) {
442                self.damage.add(*rect);
443            }
444        }
445    }
446
447    /// After processing: clear dirty flags for processed nodes and damage
448    pub(crate) fn finish_update(&mut self) {
449        self.tracker.clear_all();
450        self.damage.clear();
451    }
452
453    /// Full update cycle: compute damage, return regions, clear state.
454    /// Returns the bounding box of all damage (if any).
455    pub(crate) fn flush(&mut self) -> Option<DamageRegion> {
456        self.compute_damage();
457        if self.damage.has_damage() {
458            let bbox = self.damage.bounding_box();
459            self.finish_update();
460            Some(bbox)
461        } else {
462            self.tracker.clear_all();
463            None
464        }
465    }
466}
467
468// ---------------------------------------------------------------------------
469// Tests
470// ---------------------------------------------------------------------------
471
472#[cfg(test)]
473mod tests {
474    #[allow(unused_imports)]
475    use alloc::vec;
476
477    use super::*;
478
479    #[test]
480    fn test_dirty_flag_ordering() {
481        assert!(DirtyFlag::Clean < DirtyFlag::PaintDirty);
482        assert!(DirtyFlag::PaintDirty < DirtyFlag::LayoutDirty);
483        assert!(DirtyFlag::LayoutDirty < DirtyFlag::StyleDirty);
484    }
485
486    #[test]
487    fn test_dirty_tracker_mark_and_get() {
488        let mut t = DirtyTracker::new();
489        assert_eq!(t.get_flag(1), DirtyFlag::Clean);
490        t.mark_paint_dirty(1);
491        assert_eq!(t.get_flag(1), DirtyFlag::PaintDirty);
492        assert!(t.needs_repaint(1));
493        assert!(!t.needs_relayout(1));
494    }
495
496    #[test]
497    fn test_dirty_upgrade() {
498        let mut t = DirtyTracker::new();
499        t.mark_paint_dirty(1);
500        t.mark_layout_dirty(1);
501        assert_eq!(t.get_flag(1), DirtyFlag::LayoutDirty);
502        // Cannot downgrade
503        t.mark_paint_dirty(1);
504        assert_eq!(t.get_flag(1), DirtyFlag::LayoutDirty);
505    }
506
507    #[test]
508    fn test_dirty_propagation() {
509        let mut t = DirtyTracker::new();
510        t.set_parent(1, 0);
511        t.set_parent(2, 1);
512        t.mark_layout_dirty(2);
513        // Should propagate to ancestors
514        assert!(t.needs_relayout(1));
515        assert!(t.needs_relayout(0));
516    }
517
518    #[test]
519    fn test_dirty_no_propagation_for_paint() {
520        let mut t = DirtyTracker::new();
521        t.set_parent(1, 0);
522        t.mark_paint_dirty(1);
523        assert!(!t.needs_repaint(0));
524    }
525
526    #[test]
527    fn test_dirty_clear() {
528        let mut t = DirtyTracker::new();
529        t.mark_style_dirty(1);
530        assert_eq!(t.dirty_node_count(), 1);
531        t.clear(1);
532        assert_eq!(t.get_flag(1), DirtyFlag::Clean);
533        assert_eq!(t.dirty_node_count(), 0);
534    }
535
536    #[test]
537    fn test_dirty_clear_all() {
538        let mut t = DirtyTracker::new();
539        t.mark_paint_dirty(1);
540        t.mark_layout_dirty(2);
541        t.clear_all();
542        assert!(!t.has_dirty_nodes());
543    }
544
545    #[test]
546    fn test_dirty_nodes_filter() {
547        let mut t = DirtyTracker::new();
548        t.mark_paint_dirty(1);
549        t.mark_layout_dirty(2);
550        t.mark_style_dirty(3);
551        let layout_dirty = t.dirty_nodes(DirtyFlag::LayoutDirty);
552        assert_eq!(layout_dirty.len(), 2); // 2 and 3
553        assert!(layout_dirty.contains(&2));
554        assert!(layout_dirty.contains(&3));
555    }
556
557    #[test]
558    fn test_highest_dirty_ancestor() {
559        let mut t = DirtyTracker::new();
560        t.set_parent(1, 0);
561        t.set_parent(2, 1);
562        t.mark_layout_dirty(2);
563        let root = t.highest_dirty_ancestor(2, DirtyFlag::LayoutDirty);
564        assert_eq!(root, 0);
565    }
566
567    #[test]
568    fn test_damage_region_basic() {
569        let r = DamageRegion::new(10, 20, 100, 50);
570        assert_eq!(r.right(), 110);
571        assert_eq!(r.bottom(), 70);
572        assert!(!r.is_empty());
573        assert_eq!(r.area(), 5000);
574    }
575
576    #[test]
577    fn test_damage_region_empty() {
578        let r = DamageRegion::new(0, 0, 0, 0);
579        assert!(r.is_empty());
580    }
581
582    #[test]
583    fn test_damage_union() {
584        let a = DamageRegion::new(0, 0, 50, 50);
585        let b = DamageRegion::new(30, 30, 50, 50);
586        let u = a.union(&b);
587        assert_eq!(u.x, 0);
588        assert_eq!(u.y, 0);
589        assert_eq!(u.width, 80);
590        assert_eq!(u.height, 80);
591    }
592
593    #[test]
594    fn test_damage_intersect() {
595        let a = DamageRegion::new(0, 0, 50, 50);
596        let b = DamageRegion::new(30, 30, 50, 50);
597        let i = a.intersect(&b);
598        assert_eq!(i.x, 30);
599        assert_eq!(i.y, 30);
600        assert_eq!(i.width, 20);
601        assert_eq!(i.height, 20);
602    }
603
604    #[test]
605    fn test_damage_intersect_disjoint() {
606        let a = DamageRegion::new(0, 0, 10, 10);
607        let b = DamageRegion::new(20, 20, 10, 10);
608        let i = a.intersect(&b);
609        assert!(i.is_empty());
610    }
611
612    #[test]
613    fn test_damage_contains() {
614        let a = DamageRegion::new(0, 0, 100, 100);
615        let b = DamageRegion::new(10, 10, 50, 50);
616        assert!(a.contains(&b));
617        assert!(!b.contains(&a));
618    }
619
620    #[test]
621    fn test_damage_contains_point() {
622        let r = DamageRegion::new(10, 10, 20, 20);
623        assert!(r.contains_point(15, 15));
624        assert!(!r.contains_point(5, 5));
625        assert!(!r.contains_point(30, 30));
626    }
627
628    #[test]
629    fn test_damage_list() {
630        let mut dl = DamageList::new();
631        assert!(!dl.has_damage());
632        dl.add(DamageRegion::new(0, 0, 10, 10));
633        dl.add(DamageRegion::new(50, 50, 20, 20));
634        assert!(dl.has_damage());
635        assert_eq!(dl.regions().len(), 2);
636        let bbox = dl.bounding_box();
637        assert_eq!(bbox.x, 0);
638        assert_eq!(bbox.width, 70);
639    }
640
641    #[test]
642    fn test_damage_list_clear() {
643        let mut dl = DamageList::new();
644        dl.add(DamageRegion::new(0, 0, 10, 10));
645        dl.clear();
646        assert!(!dl.has_damage());
647    }
648
649    #[test]
650    fn test_damage_list_overlaps() {
651        let mut dl = DamageList::new();
652        dl.add(DamageRegion::new(10, 10, 20, 20));
653        let query = DamageRegion::new(15, 15, 5, 5);
654        assert!(dl.overlaps(&query));
655        let query2 = DamageRegion::new(100, 100, 5, 5);
656        assert!(!dl.overlaps(&query2));
657    }
658
659    #[test]
660    fn test_incremental_layout_restyle_roots() {
661        let mut il = IncrementalLayout::new();
662        il.tracker.set_parent(1, 0);
663        il.tracker.set_parent(2, 1);
664        il.tracker.mark_style_dirty(2);
665        let roots = il.restyle_roots();
666        // Node 2 style-dirty, propagated to 1 and 0 as layout-dirty
667        // Highest style-dirty ancestor of 2 is 2 itself
668        assert_eq!(roots, vec![2]);
669    }
670
671    #[test]
672    fn test_incremental_layout_flush() {
673        let mut il = IncrementalLayout::new();
674        il.tracker.mark_paint_dirty(1);
675        il.set_node_rect(1, 10, 10, 50, 50);
676        let bbox = il.flush();
677        assert!(bbox.is_some());
678        let bbox = bbox.unwrap();
679        assert_eq!(bbox.x, 10);
680        assert_eq!(bbox.width, 50);
681        assert!(!il.tracker.has_dirty_nodes());
682    }
683
684    #[test]
685    fn test_incremental_layout_no_damage() {
686        let mut il = IncrementalLayout::new();
687        let bbox = il.flush();
688        assert!(bbox.is_none());
689    }
690
691    #[test]
692    fn test_remove_node() {
693        let mut t = DirtyTracker::new();
694        t.mark_layout_dirty(5);
695        assert_eq!(t.dirty_node_count(), 1);
696        t.remove_node(5);
697        assert_eq!(t.dirty_node_count(), 0);
698    }
699}
veridian_kernel/browser/incremental.rs

veridian_kernel/browser/
incremental.rs
