//! Damage tracking for incremental software rendering.
//!
//! The backend remembers, per fragment, what it drew last frame — the
//! fragment's store epoch, the device transform and clip context it was
//! encountered under, and its exact device-space bounds. Each render runs a
//! cheap geometry prepass over the fragment tree; anything whose (epoch,
//! transform, clip) still match reuses its recorded bounds, anything else
//! recomputes them and contributes damage (old bounds ∪ new bounds).
//! Removed fragments contribute their old bounds. The draw pass then
//! repaints into a full-viewport scratch pixmap with exactly the draw calls
//! a full render would make for content touching the damage — bit-identical
//! by construction — and copies the damaged rects back, skipping subtrees
//! whose bounds miss every rect.
//!
//! Correctness rests on two properties: damage is a superset of every pixel
//! that can differ from the previous frame (bounds are exact or
//! conservatively larger, and epoch bumps on every mutable access), and the
//! draw pass repaints *everything* that intersects each damaged rect, in
//! paint order. Anything the prepass cannot vouch for — a fragment
//! referenced from two places, a changed viewport, a different store —
//! falls back to a full frame, which is exactly the pre-damage behavior.

use std::collections::HashMap;

use guiduck_scene::geom::{Affine, Rect};
use guiduck_scene::paint::Color;
use guiduck_scene::{DisplayItem, FragmentId, FragmentStore, RenderError, ScopeTracker};

use crate::MAX_DEPTH;
use crate::glyph::GlyphCache;

/// More damage rectangles than this collapse into their bounding box.
const MAX_DAMAGE_RECTS: usize = 16;

/// Damage covering at least this fraction of the viewport renders as a full
/// frame; the mask machinery would only add overhead.
const FULL_FRACTION: f64 = 0.9;

/// What the draw pass must repaint this frame.
pub enum Damage {
    /// Everything — exactly the pre-damage behavior, no base mask.
    Full,
    /// Only these device-space pixel rectangles (possibly none: the
    /// persistent pixmap is already correct).
    Partial(Vec<Rect>),
}

/// What the backend drew for one fragment on the previous frame.
struct Record {
    epoch: u64,
    /// Device transform the fragment was encountered under.
    transform: Affine,
    /// Device-space bbox of the clip context open at the fragment's `Child`
    /// site; `None` when unclipped.
    clip: Option<Rect>,
    /// Device bounds of the fragment's own leaf items (clip applied).
    own: Option<Rect>,
    /// `own` unioned with every child's subtree bounds.
    subtree: Option<Rect>,
    /// Whether the display list has no `Child` items (an unchanged leaf can
    /// skip its item walk entirely).
    leaf: bool,
    /// The prepass generation that last visited this record.
    stamp: u64,
}

/// Per-backend damage state, persisting across frames.
#[derive(Default)]
pub struct DamageTracker {
    records: HashMap<FragmentId, Record>,
    store_id: Option<u64>,
    root: Option<FragmentId>,
    width: u32,
    height: u32,
    scale: f64,
    base_color: Option<Color>,
    /// The store's mutation counter after the last successful prepass; when
    /// it has not advanced, nothing in the store changed and the prepass is
    /// skipped entirely.
    counter: Option<u64>,
    stamp: u64,
}

impl DamageTracker {
    /// Run the geometry prepass and decide what to repaint. Always updates
    /// the per-fragment records, so the *next* frame can diff against this
    /// one even when this frame is full.
    #[allow(clippy::too_many_arguments)]
    pub fn plan(
        &mut self,
        root: FragmentId,
        store: &FragmentStore,
        width: u32,
        height: u32,
        scale: f64,
        base_color: Color,
        glyphs: &mut GlyphCache,
    ) -> Result<Damage, RenderError> {
        let full = self.store_id != Some(store.store_id())
            || self.root != Some(root)
            || self.width != width
            || self.height != height
            || self.scale != scale
            || self.base_color != Some(base_color);
        if !full && self.counter == Some(store.mutation_counter()) {
            // Not one fragment was touched since the last plan: no prepass,
            // no damage, the persistent pixmap is already this frame.
            return Ok(Damage::Partial(Vec::new()));
        }
        self.stamp += 1;
        self.counter = None;
        self.store_id = Some(store.store_id());
        self.root = Some(root);
        self.width = width;
        self.height = height;
        self.scale = scale;
        self.base_color = Some(base_color);

        let mut prepass = Prepass {
            store,
            glyphs,
            records: &mut self.records,
            stamp: self.stamp,
            damage: Vec::new(),
            dag: false,
        };
        if let Err(err) = prepass.fragment(root, Affine::scale(scale), None, 0) {
            // Half-updated records cannot be trusted; start over next frame.
            self.records.clear();
            return Err(err);
        }
        let mut damage = prepass.damage;
        let dag = prepass.dag;
        self.counter = Some(store.mutation_counter());

        // Records the prepass did not visit belong to removed fragments:
        // their old pixels are damage, their records are done.
        let stamp = self.stamp;
        self.records.retain(|_, record| {
            if record.stamp == stamp {
                true
            } else {
                if let Some(bounds) = record.subtree {
                    damage.push(bounds);
                }
                false
            }
        });

        if dag {
            // A fragment referenced from two places: one record per id can't
            // represent that, so the records are meaningless. Repaint fully
            // and re-learn from scratch next frame.
            self.records.clear();
            return Ok(Damage::Full);
        }
        if full {
            return Ok(Damage::Full);
        }

        // Pixel-align the damage: pad a pixel for anti-aliased edges and
        // round outward, so the copy back from the scratch moves whole
        // pixels.
        let viewport = Rect::new(0.0, 0.0, f64::from(width), f64::from(height));
        let mut rects: Vec<Rect> = Vec::new();
        for rect in damage {
            let rect = pad_round(rect);
            let Some(rect) = intersect(rect, viewport) else {
                continue;
            };
            if !rects.iter().any(|r| contains(*r, rect)) {
                rects.retain(|r| !contains(rect, *r));
                rects.push(rect);
            }
        }
        if rects.len() > MAX_DAMAGE_RECTS {
            let bbox = rects
                .iter()
                .copied()
                .reduce(|a, b| a.union(b))
                .expect("non-empty");
            rects = vec![bbox];
        }
        let area: f64 = rects.iter().map(|r| r.area()).sum();
        if area >= FULL_FRACTION * viewport.area() {
            return Ok(Damage::Full);
        }
        Ok(Damage::Partial(rects))
    }

    /// Whether the fragment's subtree can touch the damaged region. Unknown
    /// fragments answer yes — drawing too much is safe, skipping is not.
    pub(crate) fn subtree_intersects(&self, id: FragmentId, rects: &[Rect]) -> bool {
        match self.records.get(&id) {
            Some(record) => bounds_intersect(record.subtree, rects),
            None => true,
        }
    }

    /// Whether the fragment's own leaf items can touch the damaged region.
    pub(crate) fn own_intersects(&self, id: FragmentId, rects: &[Rect]) -> bool {
        match self.records.get(&id) {
            Some(record) => bounds_intersect(record.own, rects),
            None => true,
        }
    }
}

/// One prepass over the fragment tree: refresh records, collect damage.
struct Prepass<'a> {
    store: &'a FragmentStore,
    glyphs: &'a mut GlyphCache,
    records: &'a mut HashMap<FragmentId, Record>,
    stamp: u64,
    damage: Vec<Rect>,
    dag: bool,
}

impl Prepass<'_> {
    /// Visit one fragment occurrence; returns its subtree device bounds.
    fn fragment(
        &mut self,
        id: FragmentId,
        base: Affine,
        clip: Option<Rect>,
        depth: usize,
    ) -> Result<Option<Rect>, RenderError> {
        if depth > MAX_DEPTH {
            return Err(RenderError::ExcessiveDepth(id));
        }
        let fragment = self.store.get(id).ok_or(RenderError::MissingFragment(id))?;
        let epoch = self.store.epoch(id).expect("fragment exists");

        let mut unchanged = false;
        let mut old_subtree = None;
        let mut recorded_own = None;
        if let Some(prior) = self.records.get_mut(&id) {
            if prior.stamp == self.stamp {
                // Second encounter this frame: the fragment graph is a DAG.
                self.dag = true;
                return Ok(prior.subtree);
            }
            unchanged = prior.epoch == epoch && prior.transform == base && prior.clip == clip;
            old_subtree = prior.subtree;
            recorded_own = prior.own;
            if unchanged && prior.leaf {
                // Nothing inside an unchanged leaf can differ.
                prior.stamp = self.stamp;
                return Ok(prior.subtree);
            }
        }

        let mut transform = base;
        let mut transform_stack: Vec<Affine> = Vec::new();
        let mut clip_stack: Vec<Option<Rect>> = Vec::new();
        let mut current_clip = clip;
        let mut scopes = ScopeTracker::default();
        let unbalanced = || RenderError::UnbalancedFragment(id);
        let mut own: Option<Rect> = None;
        let mut children: Option<Rect> = None;
        let mut leaf = true;

        for item in &fragment.items {
            if !scopes.apply(item) {
                return Err(unbalanced());
            }
            match item {
                DisplayItem::Fill { shape, .. } => {
                    if !unchanged {
                        let bounds = transform.transform_rect_bbox(shape.bounding_box());
                        own = union_clipped(own, bounds, current_clip);
                    }
                }
                DisplayItem::Stroke { shape, style, .. } => {
                    if !unchanged {
                        // Conservative: strokes extend past the shape by the
                        // cap radius or the miter extension, in local units.
                        let reach =
                            style.width * style.miter_limit.max(2.0) * transform_norm(transform);
                        let bounds = transform
                            .transform_rect_bbox(shape.bounding_box())
                            .inflate(reach, reach);
                        own = union_clipped(own, bounds, current_clip);
                    }
                }
                DisplayItem::GlyphRun(run) => {
                    if !unchanged
                        && let Some(bounds) =
                            crate::glyph::run_device_bounds(run, transform, self.glyphs)?
                    {
                        own = union_clipped(own, bounds, current_clip);
                    }
                }
                DisplayItem::Image { dest, .. } => {
                    if !unchanged {
                        let bounds = transform.transform_rect_bbox(*dest);
                        own = union_clipped(own, bounds, current_clip);
                    }
                }
                DisplayItem::PushClip(shape) => {
                    clip_stack.push(current_clip);
                    let bounds = transform.transform_rect_bbox(shape.bounding_box());
                    current_clip = Some(match current_clip {
                        Some(clip) => intersect(clip, bounds).unwrap_or(Rect::ZERO),
                        None => bounds,
                    });
                }
                DisplayItem::PushLayer { bounds, .. } => {
                    // Layer contents composite masked to the layer bounds, so
                    // for damage geometry a layer clips like a clip.
                    clip_stack.push(current_clip);
                    let bounds = transform.transform_rect_bbox(bounds.bounding_box());
                    current_clip = Some(match current_clip {
                        Some(clip) => intersect(clip, bounds).unwrap_or(Rect::ZERO),
                        None => bounds,
                    });
                }
                DisplayItem::PopClip | DisplayItem::PopLayer => {
                    current_clip = clip_stack.pop().ok_or_else(unbalanced)?;
                }
                DisplayItem::PushTransform(t) => {
                    transform_stack.push(transform);
                    transform *= *t;
                }
                DisplayItem::PopTransform => {
                    transform = transform_stack.pop().ok_or_else(unbalanced)?;
                }
                DisplayItem::Child {
                    transform: placement,
                    fragment,
                } => {
                    leaf = false;
                    let subtree =
                        self.fragment(*fragment, transform * *placement, current_clip, depth + 1)?;
                    children = union_bounds(children, subtree);
                }
            }
        }
        if !scopes.is_closed() || !transform_stack.is_empty() {
            return Err(unbalanced());
        }

        let own = if unchanged { recorded_own } else { own };
        let subtree = union_bounds(own, children);
        if !unchanged {
            if let Some(bounds) = old_subtree {
                self.damage.push(bounds);
            }
            if let Some(bounds) = subtree {
                self.damage.push(bounds);
            }
        }
        self.records.insert(
            id,
            Record {
                epoch,
                transform: base,
                clip,
                own,
                subtree,
                leaf,
                stamp: self.stamp,
            },
        );
        Ok(subtree)
    }
}

/// Union `bounds ∩ clip` into `acc`.
fn union_clipped(acc: Option<Rect>, bounds: Rect, clip: Option<Rect>) -> Option<Rect> {
    let clipped = match clip {
        Some(clip) => match intersect(bounds, clip) {
            Some(rect) => rect,
            None => return acc,
        },
        None => bounds,
    };
    union_bounds(acc, Some(clipped))
}

fn union_bounds(a: Option<Rect>, b: Option<Rect>) -> Option<Rect> {
    match (a, b) {
        (Some(a), Some(b)) => Some(a.union(b)),
        (Some(a), None) => Some(a),
        (None, b) => b,
    }
}

/// Rect intersection, `None` when empty.
fn intersect(a: Rect, b: Rect) -> Option<Rect> {
    let rect = a.intersect(b);
    (rect.width() > 0.0 && rect.height() > 0.0).then_some(rect)
}

fn contains(outer: Rect, inner: Rect) -> bool {
    outer.x0 <= inner.x0 && outer.y0 <= inner.y0 && outer.x1 >= inner.x1 && outer.y1 >= inner.y1
}

/// Pad a pixel for anti-aliasing and round outward to the pixel grid.
fn pad_round(rect: Rect) -> Rect {
    Rect::new(
        (rect.x0 - 1.0).floor(),
        (rect.y0 - 1.0).floor(),
        (rect.x1 + 1.0).ceil(),
        (rect.y1 + 1.0).ceil(),
    )
}

/// An upper bound on how much the transform can scale any direction (the
/// Frobenius norm bounds the largest singular value).
fn transform_norm(t: Affine) -> f64 {
    let [xx, yx, xy, yy, ..] = t.as_coeffs();
    (xx * xx + yx * yx + xy * xy + yy * yy).sqrt()
}

/// Whether recorded bounds (inflated a pixel for AA) touch any damage rect.
fn bounds_intersect(bounds: Option<Rect>, rects: &[Rect]) -> bool {
    let Some(bounds) = bounds else {
        return false;
    };
    let bounds = bounds.inflate(1.0, 1.0);
    rects.iter().any(|rect| intersect(bounds, *rect).is_some())
}

#[cfg(test)]
mod tests {
    use guiduck_scene::Fragment;
    use guiduck_scene::paint::color::palette::css;

    use super::*;

    fn fill_fragment(rect: Rect) -> Fragment {
        let mut fragment = Fragment::new();
        fragment.fill(rect, css::REBECCA_PURPLE);
        fragment
    }

    fn plan(
        tracker: &mut DamageTracker,
        root: FragmentId,
        store: &FragmentStore,
        glyphs: &mut GlyphCache,
    ) -> Damage {
        tracker
            .plan(root, store, 200, 100, 1.0, Color::WHITE, glyphs)
            .expect("plan succeeds")
    }

    #[test]
    fn unchanged_store_needs_no_repaint() {
        let mut store = FragmentStore::new();
        let child = store.insert(fill_fragment(Rect::new(0.0, 0.0, 10.0, 10.0)));
        let mut root = Fragment::new();
        root.fill(Rect::new(0.0, 0.0, 200.0, 100.0), css::WHITE);
        root.child(Affine::translate((20.0, 20.0)), child);
        let root = store.insert(root);

        let mut tracker = DamageTracker::default();
        let mut glyphs = GlyphCache::default();
        assert!(matches!(
            plan(&mut tracker, root, &store, &mut glyphs),
            Damage::Full
        ));
        let Damage::Partial(rects) = plan(&mut tracker, root, &store, &mut glyphs) else {
            panic!("unchanged frame should be partial");
        };
        assert!(rects.is_empty(), "no damage expected, got {rects:?}");
    }

    #[test]
    fn moved_content_damages_old_and_new_bounds() {
        let mut store = FragmentStore::new();
        let child = store.insert(fill_fragment(Rect::new(0.0, 0.0, 10.0, 10.0)));
        let mut root = Fragment::new();
        root.child(Affine::translate((20.0, 20.0)), child);
        let root_id = store.insert(root);

        let mut tracker = DamageTracker::default();
        let mut glyphs = GlyphCache::default();
        plan(&mut tracker, root_id, &store, &mut glyphs);

        // Move the child to the other side of the viewport.
        let fragment = store.get_mut(root_id).expect("root exists");
        fragment.clear();
        fragment.child(Affine::translate((150.0, 60.0)), child);

        let Damage::Partial(rects) = plan(&mut tracker, root_id, &store, &mut glyphs) else {
            panic!("expected partial damage");
        };
        let covers = |x: f64, y: f64| {
            rects
                .iter()
                .any(|r| r.contains(guiduck_scene::geom::Point::new(x, y)))
        };
        assert!(covers(25.0, 25.0), "old position damaged: {rects:?}");
        assert!(covers(155.0, 65.0), "new position damaged: {rects:?}");
        assert!(
            !covers(100.0, 50.0),
            "untouched middle undamaged: {rects:?}"
        );
    }

    #[test]
    fn removed_content_damages_its_parent_but_not_unrelated_subtrees() {
        // root → left(child), right(keeper): removing `child` rewrites
        // `left`, so `left`'s region is damage — `right`'s is not.
        let mut store = FragmentStore::new();
        let child = store.insert(fill_fragment(Rect::new(0.0, 0.0, 10.0, 10.0)));
        let keeper = store.insert(fill_fragment(Rect::new(0.0, 0.0, 10.0, 10.0)));
        let mut left = Fragment::new();
        left.child(Affine::translate((0.0, 0.0)), child);
        let left = store.insert(left);
        let mut right = Fragment::new();
        right.child(Affine::translate((0.0, 0.0)), keeper);
        let right = store.insert(right);
        let mut root = Fragment::new();
        root.child(Affine::translate((20.0, 20.0)), left);
        root.child(Affine::translate((150.0, 60.0)), right);
        let root_id = store.insert(root);

        let mut tracker = DamageTracker::default();
        let mut glyphs = GlyphCache::default();
        plan(&mut tracker, root_id, &store, &mut glyphs);

        let fragment = store.get_mut(left).expect("left exists");
        fragment.clear();
        store.remove(child);

        let Damage::Partial(rects) = plan(&mut tracker, root_id, &store, &mut glyphs) else {
            panic!("expected partial damage");
        };
        assert!(
            rects
                .iter()
                .any(|r| r.contains(guiduck_scene::geom::Point::new(25.0, 25.0))),
            "removed child's old position damaged: {rects:?}"
        );
        assert!(
            !rects
                .iter()
                .any(|r| r.contains(guiduck_scene::geom::Point::new(155.0, 65.0))),
            "unrelated subtree undamaged: {rects:?}"
        );
    }

    #[test]
    fn different_store_forces_full_repaint() {
        let mut store_a = FragmentStore::new();
        let root_a = store_a.insert(fill_fragment(Rect::new(0.0, 0.0, 10.0, 10.0)));
        let mut store_b = FragmentStore::new();
        let root_b = store_b.insert(fill_fragment(Rect::new(0.0, 0.0, 10.0, 10.0)));

        let mut tracker = DamageTracker::default();
        let mut glyphs = GlyphCache::default();
        plan(&mut tracker, root_a, &store_a, &mut glyphs);
        assert!(matches!(
            plan(&mut tracker, root_b, &store_b, &mut glyphs),
            Damage::Full
        ));
        assert!(matches!(
            plan(&mut tracker, root_a, &store_a, &mut glyphs),
            Damage::Full
        ));
    }

    #[test]
    fn dag_input_forces_full_repaint() {
        let mut store = FragmentStore::new();
        let shared = store.insert(fill_fragment(Rect::new(0.0, 0.0, 10.0, 10.0)));
        let mut root = Fragment::new();
        root.child(Affine::translate((20.0, 20.0)), shared);
        root.child(Affine::translate((60.0, 20.0)), shared);
        let root_id = store.insert(root);

        let mut tracker = DamageTracker::default();
        let mut glyphs = GlyphCache::default();
        assert!(matches!(
            plan(&mut tracker, root_id, &store, &mut glyphs),
            Damage::Full
        ));
        // An untouched store needs no repaint even after a DAG frame — the
        // pixmap already holds a correct full render.
        let Damage::Partial(rects) = plan(&mut tracker, root_id, &store, &mut glyphs) else {
            panic!("unchanged store should skip repainting");
        };
        assert!(rects.is_empty());
        // But any mutation goes back to full: one record per id cannot
        // describe two occurrences, so the tracker never trusts a DAG.
        store
            .get_mut(shared)
            .expect("shared exists")
            .fill(Rect::new(0.0, 0.0, 5.0, 5.0), css::WHITE);
        assert!(matches!(
            plan(&mut tracker, root_id, &store, &mut glyphs),
            Damage::Full
        ));
    }
}