rust_widgets 2.9.2

// SPDX-FileCopyrightText: Copyright (c) 2026 Mike Li/Mikewolfli/Wei Li(mikewolfli@163.com)
// SPDX-License-Identifier: MIT

//! Helper for rendering only dirty regions using clip rects.

use crate::compat::Vec;
use crate::core::Rect;
use crate::performance::DirtyRegionTracker;

/// Fraction of the frame area above which repainting regions costs more than a full
/// paint.
///
/// # Why this is measured rather than counted
///
/// The previous rule was "more than 16 regions falls back", which measures the wrong
/// thing: sixteen small regions scattered over a 4K window touch a fraction of a
/// percent of its pixels, while two regions covering the whole frame touch all of
/// them. Counting regions cannot tell those apart, so the old rule both fell back
/// when it should not and skipped the fallback when it should.
///
/// # Why the threshold is a half
///
/// A partial repaint still walks the whole widget tree and re-emits its draw calls —
/// the clip just discards most of the output. Once the surviving pixels approach
/// everything, that discarded work is the entire cost and the clip buys nothing, so
/// past this point the clip-free full paint is strictly better. Half is the crossover
/// at which the discarded work equals the painted work, which is the earliest point
/// the trade is unambiguous.
pub const FULL_REPAINT_AREA_RATIO: f32 = 0.5;

/// Render only the dirty regions by bucketing one traversal into control-level clips.
///
/// # What changed, and why
///
/// The previous implementation called `render_all` **once per region**, so N damaged regions
/// meant N complete widget-tree traversals and N command streams — the dominant cost of a partial
/// repaint was the part the clip was supposed to save (G-04). This version walks the tree exactly
/// once: `RenderContext::begin_region_buckets` records every command against the bounds of the
/// control that emitted it, and the end call replays each control only into the regions it
/// touches. A control outside all damage emits no pixels; a control covering several regions is
/// replayed into each, which is what the clip is for.
///
/// # What "fall back" means here
///
/// When the damage is too large or too scattered to be worth regioning, the damage is still
/// painted — as one clip over its bounding rectangle rather than as one clip per region. That is
/// the cheapest correct answer, and it is still a single traversal.
///
/// # Allocation
///
/// This is a convenience wrapper around [`render_dirty_regions_into`] and allocates
/// the region buffer on every call. A frame loop should call the `_into` variant
/// with a `Vec` it owns, so the buffer's capacity survives across frames (G-72).
pub fn render_dirty_regions(
    tracker: &mut DirtyRegionTracker,
    ctx: &mut crate::render::RenderContext,
    render_all: impl FnMut(&mut crate::render::RenderContext),
) {
    let mut regions = Vec::new();
    render_dirty_regions_into(tracker, ctx, &mut regions, render_all);
}

/// Buffer-reusing form of [`render_dirty_regions`].
///
/// `regions` is cleared and refilled with the rectangles of the merged region set
/// before the bucketed traversal, so a frame loop can hold one `Vec` for its whole
/// lifetime and pay no per-frame region allocation (G-72). The merge/fallback
/// decision and the paint calls are identical to [`render_dirty_regions`]. When the
/// bounding-rect path is taken the buffer is left empty, because the single clip is
/// built from the bounding rectangle rather than from a region list.
pub fn render_dirty_regions_into(
    tracker: &mut DirtyRegionTracker,
    ctx: &mut crate::render::RenderContext,
    regions: &mut Vec<Rect>,
    mut render_all: impl FnMut(&mut crate::render::RenderContext),
) {
    // The buffer belongs to the caller and may still hold a previous frame's rectangles,
    // so it is emptied up front: an early return must not leave a stale list behind.
    regions.clear();

    // 1. Bound the work *before* merging (D09-RENDER-01).
    //
    // `merge` restarts its scan after each union, so its cost grows with the square of the
    // region count. A tracker holding more regions than its `max_regions` is precisely the
    // high-cardinality case that is worst at, so it is answered with a single repaint over the
    // bounding rectangle of **all** the damage — one traversal, and every damaged pixel still
    // covered, because a bounding rectangle by construction contains every region. This is
    // deliberately *not* `optimize()`: that would truncate the region list and leave the dropped
    // areas stale (see `DirtyRegionTracker::over_capacity`).
    if tracker.over_capacity() {
        paint_bounding_rect(tracker, ctx, &mut render_all);
        return;
    }

    // 2. Merge overlapping regions
    tracker.merge();

    // 3. If no dirty regions, skip
    if tracker.is_empty() {
        return;
    }

    // 4. Decide by covered *area*, not by region count. See
    //    `FULL_REPAINT_AREA_RATIO` for why the count was the wrong measure.
    let frame = ctx.size();
    let frame_area = u64::from(frame.width) * u64::from(frame.height);
    let covered: u64 = tracker
        .regions()
        .iter()
        .map(|region| u64::from(region.rect.width) * u64::from(region.rect.height))
        .sum();

    // A zero-area frame cannot happen for a mounted widget (the render entry points
    // reject an empty size), but a zero denominator would make every comparison
    // meaningless, so the bounding-rect path is taken rather than guessed at.
    let too_large =
        frame_area == 0 || (covered as f32) >= (frame_area as f32) * FULL_REPAINT_AREA_RATIO;

    if too_large {
        paint_bounding_rect(tracker, ctx, &mut render_all);
        return;
    }

    // 5. One traversal, bucketed into the merged region set. The caller's buffer is
    //    reused instead of collecting into a fresh `Vec` per call.
    regions.extend(tracker.regions().iter().map(|region| region.rect));
    ctx.begin_region_buckets(regions.as_slice());
    render_all(ctx);
    ctx.end_region_buckets();
    tracker.clear();
}

/// Repaints once, clipped to the bounding rectangle of every tracked region, then clears.
///
/// The single-pass answer for damage that is too large or too scattered to region: one widget
/// traversal under one clip that still covers all the damage. A no-op when nothing is tracked
/// (the bounding rectangle is `None`), which keeps the empty case consistent with the per-region
/// path. (D09-RENDER-01)
fn paint_bounding_rect(
    tracker: &mut DirtyRegionTracker,
    ctx: &mut crate::render::RenderContext,
    render_all: &mut impl FnMut(&mut crate::render::RenderContext),
) {
    if let Some(bounding) = tracker.get_bounding_rect() {
        let regions = [bounding];
        ctx.begin_region_buckets(&regions);
        render_all(ctx);
        ctx.end_region_buckets();
    }
    tracker.clear();
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::core::{Color, Rect, Size};
    use crate::render::RenderContext;
    use crate::render::SoftwarePaintBackend;
    // `begin_frame` is a `PaintBackend` method, so the trait must be in scope.
    use crate::render::PaintBackend as _;

    /// How a dirty-region pass behaved, as observable facts rather than a return value.
    ///
    /// `traversals` is how many times the widget tree was walked — the number this change is
    /// about (G-04). `region_clips` is how many clips the pass issued, which is what distinguishes
    /// the per-region answer from the one-pass bounding fallback.
    struct Passes {
        traversals: usize,
        region_clips: usize,
    }

    fn passes_for(regions: &[Rect], frame: Size) -> Passes {
        let mut tracker = DirtyRegionTracker::new();
        for rect in regions {
            tracker.add(*rect);
        }
        let mut backend = SoftwarePaintBackend::new(frame, 1.0);
        backend.begin_frame(Color::rgb(0, 0, 0));
        let mut traversals = 0usize;
        let region_clips;
        {
            let mut ctx = RenderContext::new(&mut backend);
            render_dirty_regions(&mut tracker, &mut ctx, |_| {
                traversals += 1;
            });
            region_clips = ctx.region_bucket_passes();
        }
        Passes { traversals, region_clips }
    }

    #[test]
    fn test_dirty_region_tracker() {
        let mut tracker = DirtyRegionTracker::new();
        tracker.add(Rect::new(0, 0, 100, 100));
        tracker.add(Rect::new(50, 50, 100, 100));
        tracker.merge();
        // The two overlapping rects merge into a single dirty region.
        assert_eq!(tracker.len(), 1);
        assert!(!tracker.is_empty());
    }

    /// No damage means no paint at all: the loop must not run once "just in case".
    #[test]
    fn no_damage_paints_nothing() {
        let pass = passes_for(&[], Size::new(800, 600));
        assert_eq!(pass.traversals, 0, "no damage means no traversal");
        assert_eq!(pass.region_clips, 0);
    }

    /// A few small regions over a large frame are painted as separate regions, one
    /// pass each. Under the old count-based rule this also held, but for the wrong
    /// reason; here it holds because the *area* is small.
    #[test]
    fn small_regions_in_a_large_frame_are_painted_separately() {
        let regions =
            [Rect::new(0, 0, 16, 16), Rect::new(100, 100, 16, 16), Rect::new(200, 200, 16, 16)];
        let pass = passes_for(&regions, Size::new(2000, 2000));
        assert_eq!(pass.traversals, 1, "three regions must still mean one tree traversal");
        assert_eq!(pass.region_clips, 3, "but each region keeps its own clip");
    }

    /// Damage covering most of the frame collapses to a single pass, even when it
    /// arrives as two separate rectangles that do *not* overlap.
    ///
    /// This is the case the old count-based rule got wrong in the other direction:
    /// two regions is well under sixteen, so it would have painted them separately,
    /// when together they cover the frame and a single pass is cheaper.
    #[test]
    fn damage_covering_the_frame_collapses_to_one_pass() {
        let regions = [Rect::new(0, 0, 800, 400), Rect::new(0, 400, 800, 300)];
        let pass = passes_for(&regions, Size::new(800, 700));
        assert_eq!(pass.traversals, 1, "the covering repaint is still a single traversal");
        assert_eq!(
            pass.region_clips, 1,
            "two non-overlapping regions that together fill the frame must merge into one pass"
        );
    }

    /// The boundary itself: exactly at the documented ratio the fallback applies.
    ///
    /// # Why the fixture uses two disjoint regions
    ///
    /// The boundary must be measured on an input whose two sides produce
    /// *different* observable outcomes, or the test cannot see which branch ran.
    /// A single region is useless here: `too_large` picks the bounding-rect
    /// branch, and `!(too_large)` picks the per-region branch, but both paint a
    /// single region exactly once — so `>=` and `>` are indistinguishable, which
    /// is precisely the off-by-one this test is meant to pin.
    ///
    /// Two *non-touching* regions that the tracker cannot merge separate the
    /// branches: above the threshold they collapse to one bounding pass (paint
    /// count 1), below it they stay separate (paint count 2). The region areas
    /// are integral, so both sides are exactly `frame_area * 0.5`-comparable:
    /// each region is `1/4` of the 1000x1000 frame, so two cover exactly `1/2`.
    #[test]
    fn the_fallback_applies_at_the_documented_ratio() {
        let frame = Size::new(1000, 1000);
        assert_eq!(
            FULL_REPAINT_AREA_RATIO, 0.5,
            "the fixture below steps the covered fraction by exactly 1/1000 of the frame; a different ratio needs a rebuilt fixture"
        );

        // Exactly half the frame: two 1/4 regions. `>= 0.5` must take the
        // bounding-rect branch, painting once.
        let exactly_half = [Rect::new(0, 0, 500, 500), Rect::new(500, 500, 500, 500)];
        let pass = passes_for(&exactly_half, frame);
        assert_eq!(pass.traversals, 1);
        assert_eq!(
            pass.region_clips, 1,
            "two disjoint regions covering exactly half the frame must collapse to the one-pass bounding fallback"
        );

        // Just under half the frame, same two-region shape. `> 0.5` would be
        // false here *and* at the value above, so a count of 2 here is what
        // proves the comparison is `>=`, not `>`.
        let just_under = [Rect::new(0, 0, 499, 500), Rect::new(500, 500, 500, 500)];
        let pass = passes_for(&just_under, frame);
        assert_eq!(pass.traversals, 1);
        assert_eq!(
            pass.region_clips, 2,
            "one pixel of area below the ratio must keep the two regions separate (one pass each)"
        );
    }

    /// Many tiny regions stay separate: the rule must not degrade into "lots of
    /// regions means fall back", which is what it replaced.
    #[test]
    fn many_small_regions_do_not_trigger_the_fallback() {
        let regions: Vec<Rect> = (0..40).map(|i| Rect::new(i * 10, 0, 5, 5)).collect();
        let pass = passes_for(&regions, Size::new(1000, 1000));
        assert_eq!(pass.traversals, 1);
        assert_eq!(
            pass.region_clips,
            regions.len(),
            "forty regions covering 1000 px of a 1_000_000 px frame must not fall back"
        );
    }

    /// Over the tracker's capacity the paint collapses to a single covering pass, and no damage
    /// is dropped. (D09-RENDER-01)
    ///
    /// # Why this pins the *bound* and not just the count
    ///
    /// The defect was that `max_regions` only took effect in `optimize()`, which the runtime
    /// never called, so a high-cardinality frame did up to one full widget-tree traversal per
    /// region — hundreds of traversals for hundreds of tiny rects. The assertion is that the
    /// number of paint passes is bounded (one), regardless of how many regions arrived.
    #[test]
    fn high_cardinality_damage_collapses_to_a_bounded_number_of_passes() {
        // Well over the default `max_regions` (100).
        let regions: Vec<Rect> = (0..500).map(|i| Rect::new(i, 0, 2, 2)).collect();
        let pass = passes_for(&regions, Size::new(4000, 4000));
        assert_eq!(pass.traversals, 1, "the bound is one traversal, not one per region");
        assert_eq!(
            pass.region_clips, 1,
            "more regions than the tracker's capacity must paint once, not once per region"
        );
    }

    /// A tracker under capacity still regions, so the bound is a threshold and not a blanket
    /// "always one pass". (D09-RENDER-01)
    #[test]
    fn at_capacity_still_regions_separately() {
        // Exactly the default capacity: `over_capacity` is `>`, so this stays on the per-region
        // path and the count is preserved.
        let regions: Vec<Rect> = (0..100).map(|i| Rect::new(i * 10, 0, 2, 2)).collect();
        let pass = passes_for(&regions, Size::new(4000, 4000));
        assert_eq!(pass.traversals, 1);
        assert_eq!(pass.region_clips, 100);
    }

    /// High-cardinality damage must paint every damaged pixel — the bounded path covers all the
    /// damage, it does not drop any. (D09-RENDER-01)
    #[test]
    fn high_cardinality_damage_paints_every_damaged_pixel() {
        let frame = Size::new(64, 64);
        let clear = Color::rgb(0, 0, 0);
        let ink = Color::rgb(255, 255, 255);

        // The damage is 300 single-pixel regions scattered across the frame — over capacity, and
        // spread wider than any single row, so covering them in one pass requires a bounding
        // rectangle rather than a clever clip.
        let damaged: Vec<Rect> = (0..300)
            .map(|i| {
                let x = i % 60;
                let y = (i / 60) * 4;
                Rect::new(x, y, 1, 1)
            })
            .collect();

        // The bounding rectangle of the damage: what the single covering pass is clipped to.
        let mut bounding = damaged[0];
        for rect in &damaged[1..] {
            bounding = bounding.union(rect);
        }

        // Reference: an unclipped paint of the ink, then read only inside the bounding rect.
        let mut reference = SoftwarePaintBackend::new(frame, 1.0);
        reference.begin_frame(clear);
        let mut ref_ctx = RenderContext::new(&mut reference);
        ref_ctx.fill_rect(bounding, ink);
        drop(ref_ctx);
        reference.end_frame();
        let expected = reference.frame_rgba().to_vec();

        // Under the capacity-bounded path: seed a black frame, then render the damage.
        let mut backend = SoftwarePaintBackend::new(frame, 1.0);
        backend.begin_frame(clear);
        let mut tracker = DirtyRegionTracker::new();
        for rect in &damaged {
            tracker.add(*rect);
        }
        let mut painted = 0usize;
        {
            let mut ctx = RenderContext::new(&mut backend);
            render_dirty_regions(&mut tracker, &mut ctx, |ctx| {
                painted += 1;
                // The closure is what a widget would do: paint its area.
                ctx.fill_rect(Rect::new(0, 0, frame.width, frame.height), ink);
            });
        }
        backend.end_frame();

        assert_eq!(painted, 1, "the bounded path paints once");
        assert_eq!(
            backend.frame_rgba(),
            expected.as_slice(),
            "every pixel inside the covering clip must match a full repaint: damage must not be dropped"
        );
        // And, explicitly, each damaged pixel is now the ink rather than the stale clear colour.
        let stride = frame.width as usize * 4;
        let got = backend.frame_rgba();
        for rect in &damaged {
            let at = rect.y as usize * stride + rect.x as usize * 4;
            assert_eq!(
                &got[at..at + 4],
                &[255, 255, 255, 255],
                "damage at {rect:?} was not repainted"
            );
        }
        assert!(tracker.is_empty(), "the damage is consumed");
    }

    /// The buffer-reusing entry point fills the caller's vector with the rectangles it
    /// rendered and leaves it empty on a pass that paints nothing, so a frame loop can
    /// keep one `Vec` and never observe a stale region list (G-72).
    #[test]
    fn the_region_buffer_is_reused_and_never_left_stale() {
        let mut tracker = DirtyRegionTracker::new();
        tracker.add(Rect::new(0, 0, 10, 10));
        tracker.add(Rect::new(200, 200, 10, 10));
        let mut backend = SoftwarePaintBackend::new(Size::new(400, 400), 1.0);
        backend.begin_frame(Color::rgb(0, 0, 0));
        let mut regions = Vec::new();
        {
            let mut ctx = RenderContext::new(&mut backend);
            render_dirty_regions_into(&mut tracker, &mut ctx, &mut regions, |_| {});
            assert_eq!(ctx.region_bucket_passes(), 2, "both small regions are painted separately");
        }
        assert_eq!(regions.len(), 2, "the caller's buffer holds the rendered region rectangles");
        let capacity = regions.capacity();

        // A pass with no damage must empty the buffer, not leave the previous list for a caller
        // that inspects it, while keeping the allocation for the next frame.
        {
            let mut ctx = RenderContext::new(&mut backend);
            render_dirty_regions_into(&mut tracker, &mut ctx, &mut regions, |_| {});
            assert_eq!(ctx.region_bucket_passes(), 0);
        }
        assert!(regions.is_empty(), "an empty tracker leaves the buffer empty");
        assert_eq!(regions.capacity(), capacity, "the allocation survives across calls");
        backend.end_frame();
    }
}