//! Deciding which display items a walk can skip.
//!
//! A fragment's display list is as large as its widget's *content*, not as
//! large as the window: a scroll area holding a hundred-page document paints
//! every page of it into one list and clips the result to the viewport. That
//! is the right shape for painting — the list is rebuilt only when the content
//! changes, and scrolling is then a transform — but a backend that hands every
//! item to the GPU pays for the whole document on every frame, and a scene
//! large enough stops being drawable at all: vello encodes each glyph's
//! outline into one buffer, and wgpu's default limits cap a binding at 128 MiB.
//!
//! Nothing outside the clip in force can affect a pixel inside it, so a walk
//! may drop those items and produce the same picture. This module is the one
//! definition of that judgement: [`ClipBounds`] carries the intersected clip
//! down a walk, and [`DisplayItem::draw_bounds`] says where an item can draw.
//!
//! Every bound here is an *over*-estimate where it is not exact, which is the
//! direction that keeps the answer sound: culling something visible would lose
//! pixels, while keeping something invisible only costs the work this module
//! exists to save.

use crate::display_list::{DisplayItem, GlyphRun};
use crate::geom::{Affine, Rect};

/// How far past a glyph's origin its ink is assumed to reach, in ems.
///
/// The display list records where each glyph in a run is *placed*, not how far
/// its outline extends from there — that is in the font, and reading it would
/// mean rasterizing the run to decide whether to rasterize the run. Three ems
/// in every direction is far past where a text face draws: it covers the last
/// glyph's own advance (one em for a full-width CJK glyph), the tallest
/// stacked diacritics, and the deepest descenders and swashes together, with
/// room to spare — including for a synthesized italic, whose lean moves the
/// top of a glyph about a quarter of an em, and a synthesized bold, which
/// grows it by a fiftieth.
const INK_REACH_EM: f64 = 3.0;

impl GlyphRun {
    /// A bound, in run-local coordinates, on the pixels this run can touch.
    ///
    /// Conservative by [`INK_REACH_EM`]: exact glyph extents live in the font.
    /// `None` for a run with no glyphs, which draws nothing at all.
    pub fn ink_bounds(&self) -> Option<Rect> {
        let mut glyphs = self.glyphs.iter();
        let first = glyphs.next()?;
        let (mut x0, mut y0, mut x1, mut y1) = (first.x, first.y, first.x, first.y);
        for glyph in glyphs {
            x0 = x0.min(glyph.x);
            y0 = y0.min(glyph.y);
            x1 = x1.max(glyph.x);
            y1 = y1.max(glyph.y);
        }
        let reach = f64::from(self.size) * INK_REACH_EM;
        Some(
            Rect::new(f64::from(x0), f64::from(y0), f64::from(x1), f64::from(y1))
                .inflate(reach, reach),
        )
    }
}

impl DisplayItem {
    /// Where this item can draw, under `transform`, or `None` if it draws
    /// nothing itself — a scope marker, or a [`Child`](DisplayItem::Child),
    /// whose extent is the child fragment's business.
    ///
    /// The rectangle is an axis-aligned bound in the transform's target space,
    /// so a rotated shape reports the box around it.
    pub fn draw_bounds(&self, transform: Affine) -> Option<Rect> {
        let local = match self {
            DisplayItem::Fill { shape, .. } => shape.bounding_box(),
            DisplayItem::Stroke { shape, style, .. } => {
                // A stroke straddles its path, and a miter join runs out
                // further still: the join's tip reaches half the width times
                // the miter limit from the corner. Taking the whole width for
                // the straddle rather than half of it leaves margin for a
                // transform that scales the two axes differently, since the
                // reach is measured in the shape's space and the bound is
                // taken in the target's.
                let reach = style.width * style.miter_limit.max(1.0);
                shape.bounding_box().inflate(reach, reach)
            }
            DisplayItem::GlyphRun(run) => run.ink_bounds()?,
            DisplayItem::Image { dest, .. } => *dest,
            DisplayItem::PushClip(_)
            | DisplayItem::PopClip
            | DisplayItem::PushLayer { .. }
            | DisplayItem::PopLayer
            | DisplayItem::PushTransform(_)
            | DisplayItem::PopTransform
            | DisplayItem::Child { .. } => return None,
        };
        Some(transform.transform_rect_bbox(local))
    }
}

/// The clip in force at a point in a display-list walk, in the walk's target
/// space.
///
/// A clip of `None` is unclipped, which is where a walk with no bound on its
/// target starts; a walk that knows its surface starts from
/// [`ClipBounds::new`] with that surface's rectangle, and everything off the
/// edge of it is then culled along with everything else.
#[derive(Clone, Debug)]
pub struct ClipBounds {
    current: Option<Rect>,
    stack: Vec<Option<Rect>>,
}

impl ClipBounds {
    /// A stack whose outermost clip is `bounds` (`None` for unclipped).
    pub fn new(bounds: Option<Rect>) -> Self {
        Self {
            current: bounds,
            stack: Vec::new(),
        }
    }

    /// The clip in force, `None` if unclipped.
    pub fn current(&self) -> Option<Rect> {
        self.current
    }

    /// Open a scope clipped to `bounds`, intersected with the clip already in
    /// force. Pairs with [`pop`](Self::pop).
    ///
    /// A clip that has closed to nothing stays closed as further scopes
    /// intersect into it, which is what lets [`any_visible`](Self::any_visible)
    /// answer for a whole subtree at once.
    pub fn push(&mut self, bounds: Rect) {
        self.stack.push(self.current);
        self.current = Some(match self.current {
            Some(clip) => clip.intersect(bounds),
            None => bounds,
        });
    }

    /// Close the innermost scope. A pop with nothing open leaves the clip
    /// alone; backends reject the unbalanced list that could cause one.
    pub fn pop(&mut self) {
        if let Some(previous) = self.stack.pop() {
            self.current = previous;
        }
    }

    /// Whether anything at all can still be drawn: false once the clip has
    /// closed to nothing, in which case a whole subtree can be skipped.
    pub fn any_visible(&self) -> bool {
        !self.current.is_some_and(is_empty)
    }

    /// Whether something bounded by `bounds` can affect a pixel inside the
    /// clip.
    pub fn visible(&self, bounds: Rect) -> bool {
        match self.current {
            Some(clip) => !is_empty(clip.intersect(bounds)),
            None => true,
        }
    }

    /// Whether `item` can affect a pixel inside the clip, under `transform`.
    /// An item that draws nothing itself is never culled: its scope still has
    /// to be tracked, and a child fragment is entered on its own terms.
    pub fn item_visible(&self, item: &DisplayItem, transform: Affine) -> bool {
        match item.draw_bounds(transform) {
            Some(bounds) => self.visible(bounds),
            None => true,
        }
    }
}

/// Whether a rectangle encloses no pixels — including one whose corners are
/// the wrong way round, which is why this is a test on the edges rather than
/// on the area.
fn is_empty(rect: Rect) -> bool {
    rect.x1 <= rect.x0 || rect.y1 <= rect.y0
}

#[cfg(test)]
mod tests;