frus_widgets/

relayout.rs

//! The **relayout boundary** cache: holds, between frames, the computed rectangles
//! of each layout root, indexed by identity.
//!
//! Frus rebuilds the widget tree on every frame and, until now, re-ran taffy *from
//! scratch* at every layout root (`build_ui`, every scrollable, every screen, every
//! overlay…). Yet the geometry depends **only** on the tree's *style* and
//! *structure* and on the parent's *constraints* — not on colors or text, which
//! only affect painting. A hover, a blinking caret, an animating color → the same
//! layout.
//!
//! This cache records, per root (`WidgetId`), `(fingerprint, constraints,
//! rectangles)`. If the layout fingerprint and the constraints are unchanged, the
//! **rectangles are reused** and taffy is not called again. The output is
//! **bit-for-bit identical** to the full computation — only the performance
//! changes. It is also the foundation of the future phase system: "fingerprint
//! changed" *is* a root's "layout dirty" bit.

use std::collections::{HashMap, HashSet};
use std::hash::{Hash, Hasher};

use frus_core::{Rect, Size};
use frus_layout::Overflowing;

use crate::interaction::WidgetId;
use crate::runtime::Runtime;
use crate::ui::{build_layout, child_id, effective_style};
use crate::widget::Widget;

/// The constraints passed to taffy for a layout root. `free_x`/`free_y` leave an
/// axis **free** (the content takes its natural size) — the case of scrollable
/// content.
#[derive(Clone, Copy, Debug, PartialEq)]
pub(crate) struct Constraints {
    pub w: f32,
    pub h: f32,
    pub free_x: bool,
    pub free_y: bool,
    /// **Fill** the box rather than hug the content: an unset (`Auto`) dimension of
    /// the root becomes the available size. For content that is *given* its box —
    /// a page of a [`crate::PageView`] — rather than asked how big it wants to be.
    pub fill: bool,
    /// **Force** the constrained axes rather than merely fill them: a size the content
    /// chose for itself is overruled. What a stack layer pinned to two opposite edges
    /// asks for — see [`frus_layout::Layout::compute_tight`].
    pub tight: bool,
    /// Whether each bounded axis is filled, said per axis — for a box that hands its child
    /// the room on one axis and only allows it on the other (milestone 598). `None` leaves
    /// it to `fill`, and to the lone-axis rule of a scrollable.
    pub fill_each: Option<[bool; 2]>,
}

impl Constraints {
    /// Both axes constrained to `size` (ordinary layout).
    pub fn definite(size: Size) -> Self {
        Self {
            w: size.width,
            h: size.height,
            free_x: false,
            free_y: false,
            fill: false,
            tight: false,
            fill_each: None,
        }
    }

    /// A box the content is **handed**: constrained on both axes, and filled.
    pub fn filled(size: Size) -> Self {
        Self {
            fill: true,
            ..Self::definite(size)
        }
    }

    /// Scrollable content: each axis either constrained or free.
    pub fn scroll(w: f32, h: f32, free_x: bool, free_y: bool) -> Self {
        Self {
            w,
            h,
            free_x,
            free_y,
            fill: false,
            tight: false,
            fill_each: None,
        }
    }

    /// A box the content is **forced** into on the axes that were given, with the others
    /// left free so the content's own size comes back on them.
    pub fn pinned(w: Option<f32>, h: Option<f32>, available: Size) -> Self {
        Self {
            w: w.unwrap_or(available.width),
            h: h.unwrap_or(available.height),
            free_x: w.is_none(),
            free_y: h.is_none(),
            fill: false,
            tight: true,
            fill_each: None,
        }
    }

    /// Each axis free or bounded, and each bounded axis filled or only allowed.
    pub fn axes(w: f32, h: f32, free: [bool; 2], fill: [bool; 2]) -> Self {
        Self {
            fill_each: Some(fill),
            ..Self::scroll(w, h, free[0], free[1])
        }
    }
}

/// One cache entry: the fingerprint of the last root computed under this identity,
/// its constraints, and the rectangles produced (in prefix order).
struct Entry {
    signature: u64,
    constraints: Constraints,
    rects: Vec<Rect>,
    /// Boxes in this root whose children did not fit. Cached alongside the rectangles
    /// because it is computed from the same taffy pass and would otherwise need a
    /// second one on every cache hit.
    overflows: Vec<Overflowing>,
}

/// The relayout cache, retained in the [`crate::Runtime`] from one frame to the next.
#[derive(Default)]
pub struct LayoutCache {
    entries: HashMap<WidgetId, Entry>,
    /// Roots touched during the current frame (to evict the vanished ones).
    touched: HashSet<WidgetId>,
    /// Diagnostic: reuses and recomputations of the **last** frame.
    last_hits: u32,
    last_misses: u32,
    hits: u32,
    misses: u32,
}

impl LayoutCache {
    /// The rectangles (prefix order) of root `key` under constraints `c`. Reuses
    /// the cache if the layout fingerprint **and** the constraints are unchanged;
    /// otherwise re-runs taffy and records the result.
    pub(crate) fn rects<Msg>(
        &mut self,
        key: WidgetId,
        root: &dyn Widget<Msg>,
        runtime: &Runtime,
        theme: &crate::theme::Theme,
        c: Constraints,
    ) -> (Vec<Rect>, Vec<Overflowing>) {
        self.touched.insert(key);
        let (signature, volatile) = signature_of(root, key, runtime, theme);
        if !volatile {
            if let Some(entry) = self.entries.get(&key) {
                if entry.signature == signature && entry.constraints == c {
                    self.hits += 1;
                    return (entry.rects.clone(), entry.overflows.clone());
                }
            }
        }
        self.misses += 1;
        let (rects, overflows) = compute_rects(root, key, runtime, theme, c);
        if volatile {
            // Nothing is stored either: an entry that can never be trusted would only
            // sit there being evicted and re-made.
            self.entries.remove(&key);
            return (rects, overflows);
        }
        self.entries.insert(
            key,
            Entry {
                signature,
                constraints: c,
                rects: rects.clone(),
                overflows: overflows.clone(),
            },
        );
        (rects, overflows)
    }

    /// To be called at the end of a frame: forgets untouched roots (vanished
    /// widgets) and freezes the frame's diagnostic counters.
    pub(crate) fn end_frame(&mut self) {
        let touched = std::mem::take(&mut self.touched);
        self.entries.retain(|id, _| touched.contains(id));
        self.last_hits = self.hits;
        self.last_misses = self.misses;
        self.hits = 0;
        self.misses = 0;
    }

    /// Reuses and recomputations of the last completed frame (diagnostic).
    pub fn last_frame_stats(&self) -> (u32, u32) {
        (self.last_hits, self.last_misses)
    }
}

/// Computes a root's absolute rectangles — the "full" path (build + taffy +
/// collect), taken on every cache *miss*.
fn compute_rects<Msg>(
    root: &dyn Widget<Msg>,
    key: WidgetId,
    runtime: &Runtime,
    theme: &crate::theme::Theme,
    c: Constraints,
) -> (Vec<Rect>, Vec<Overflowing>) {
    let mut layout = frus_layout::Layout::new();
    let node = build_layout(root, key, runtime, theme, &mut layout);
    // `compute_scroll(_, _, false, false)` is equivalent to `compute` (both axes
    // `Definite`): a single path covers both cases.
    if c.tight {
        layout.compute_tight(node, c.w, c.h, c.free_x, c.free_y);
    } else if let Some(fill) = c.fill_each {
        layout.compute_axes(node, c.w, c.h, [c.free_x, c.free_y], fill);
    } else if c.fill {
        layout.compute_filled(node, c.w, c.h);
    } else {
        layout.compute_scroll(node, c.w, c.h, c.free_x, c.free_y);
    }
    let rects = layout
        .absolute_rects(node)
        .into_iter()
        .map(|(rect, _)| rect)
        .collect();
    (rects, layout.overflows(node))
}

/// A 64-bit fingerprint of a subtree's **layout** — styles + structure, following
/// **exactly** the branching of [`build_layout`] (scrollable/navigator/list/stack = a
/// leaf; portal = the anchor alone), with colours, texts and messages excluded because
/// they only affect painting — and whether that fingerprint can be **trusted between
/// frames**.
///
/// A `LayoutBuilder`'s box is the size of what its closure built, and a closure cannot be
/// fingerprinted: two frames whose styles and structure are identical can still want
/// different geometry, because the application changed what it builds. So a root holding
/// one is marked *volatile* and recomputed every frame — the cache's contract is that a
/// hit is **bit-for-bit** what the full computation would have produced, and the only
/// honest way to keep that here is to take the miss.
fn signature_of<Msg>(
    root: &dyn Widget<Msg>,
    id: WidgetId,
    runtime: &Runtime,
    theme: &crate::theme::Theme,
) -> (u64, bool) {
    let mut hasher = std::collections::hash_map::DefaultHasher::new();
    // The **reader's font size**, once, at the root. Every measured box in the tree is
    // resolved against it, so a reader who changes the system setting changes every
    // geometry below — and a fingerprint blind to it would answer the new frame with the
    // old layout and nothing would move.
    frus_core::text_scale().to_bits().hash(&mut hasher);
    let mut volatile = false;
    hash_node(root, id, runtime, theme, &mut hasher, &mut volatile);
    (hasher.finish(), volatile)
}

fn hash_node<Msg, H: Hasher>(
    widget: &dyn Widget<Msg>,
    id: WidgetId,
    runtime: &Runtime,
    theme: &crate::theme::Theme,
    hasher: &mut H,
    volatile: &mut bool,
) {
    // A themed subtree, exactly as `build_layout` sees it: its styles are resolved
    // against its own theme, so the fingerprint is taken against that one too. A
    // fingerprint that skipped the swap would hash one geometry and the cache would
    // store another.
    let scoped = crate::ui::scoped_theme(widget, id, runtime, theme);
    let theme = scoped.as_deref().unwrap_or(theme);
    // The same for the **surface**: a scoped description changes what the subtree measures
    // with, so it has to be in force here as well — and hashed, or two different surfaces
    // would share one fingerprint and the cache would keep the first one's geometry.
    let surface = widget.media_override(crate::MediaQuery::of());
    let _surface = surface.map(crate::MediaQuery::install);
    if let Some(mq) = surface {
        mq.measure_hash(hasher);
    }
    // And the **shell** (milestone 422), hashed for the same reason: whether there is a
    // drawer decides whether a bar composes a menu button, and a button is a different row.
    let shell = widget.scaffold_override();
    if let Some(info) = &shell {
        info.shape_hash(hasher);
    }
    let _shell = shell.map(crate::ScaffoldInfo::install);
    // And the scroll behaviour (milestone 616): it decides whether a scrollable lays out
    // a scrollbar.
    let scrolling = widget.scroll_behavior_override();
    if let Some(behavior) = &scrolling {
        behavior.shape_hash(hasher);
    }
    let _scrolling = scrolling.map(crate::ScrollConfiguration::install);
    // The cache exists to **skip** `build_layout`, so this walk can be the first one down
    // the tree: a deferred subtree has to be composed here too, or the fingerprint would
    // be taken of a node with no children and the cache would agree with itself forever.
    widget.build_in(id, runtime, theme);
    // These branches must stay aligned with `build_layout`: the shape of the taffy
    // tree (and therefore the number and order of the rectangles) depends on it.
    // The **effective** style is hashed (animated size injected) — the same source
    // as `build_layout`, so the fingerprint changes while the size moves.
    // `RotatedBox`: its box depends on the child's **natural** size (swapped for an
    // odd quarter), so the fingerprint must include the child; otherwise a modified
    // child would leave a stale box in the cache.
    if let Some(q) = widget.rotated_quarter_turns() {
        4u8.hash(hasher);
        q.hash(hasher);
        effective_style(widget, id, runtime, theme).layout_hash(hasher);
        if let Some(child) = widget.children().first() {
            hash_node(
                child.as_ref(),
                child_id(id, 0, child.as_ref()),
                runtime,
                theme,
                hasher,
                volatile,
            );
        }
        return;
    }
    if widget.scroll_content().is_some()
        || widget.interactive().is_some()
        || widget.fitted().is_some()
        || widget.navigator().is_some()
        // Only *whether*, never *what*: this asks if the widget windows its
        // children at all, and a size it will not read is the honest argument.
        || widget.virtual_list(frus_core::Size::ZERO).is_some()
        || widget.page_view().is_some()
        || widget.overflow_box().is_some()
        || widget.stack()
        || widget.custom_layout().is_some()
    {
        1u8.hash(hasher);
        effective_style(widget, id, runtime, theme).layout_hash(hasher);
        return;
    }
    // A box that transforms its constraints is sized from its child, laid out in a tree of
    // its own, under a rule that is **data**: the rule and the child are hashed, and the
    // entry can be trusted (milestone 593). It used to poison the entry as a
    // `LayoutBuilder` does, and every root holding one was laid out again every frame.
    if let Some(transform) = widget.constraints_transform() {
        5u8.hash(hasher);
        transform.layout_hash(hasher);
        let fills = widget.fill_axes(theme);
        (fills.horizontal, fills.vertical).hash(hasher);
        // A box that is a fraction of its child is a different box at every fraction
        // (milestone 596).
        if let Some((across, down)) = widget.size_factor() {
            across.to_bits().hash(hasher);
            down.to_bits().hash(hasher);
        }
        // A box following its child's size is a different geometry at every step of the
        // move, and the same one once it has arrived (milestone 594).
        if widget.animated_size().is_some() {
            if let Some((now, to)) = runtime.size_anims.borrow_mut().fingerprint(id) {
                for v in [now.width, now.height, to.width, to.height] {
                    v.to_bits().hash(hasher);
                }
            }
        }
        effective_style(widget, id, runtime, theme).layout_hash(hasher);
        if let Some(child) = widget.children().first() {
            hash_node(
                child.as_ref(),
                child_id(id, 0, child.as_ref()),
                runtime,
                theme,
                hasher,
                volatile,
            );
        }
        return;
    }
    // A `LayoutBuilder` hashes like a leaf and poisons the entry: its box comes from a
    // closure, and a closure cannot be hashed. Two frames whose trees fingerprint alike
    // could build two different children.
    if widget.layout_builder().is_some() {
        1u8.hash(hasher);
        effective_style(widget, id, runtime, theme).layout_hash(hasher);
        *volatile = true;
        return;
    }
    if widget.overlay().is_some() {
        2u8.hash(hasher);
        effective_style(widget, id, runtime, theme).layout_hash(hasher);
        let anchor = widget.children()[0].as_ref();
        hash_node(
            anchor,
            child_id(id, 0, anchor),
            runtime,
            theme,
            hasher,
            volatile,
        );
        return;
    }
    let children = widget.children();
    3u8.hash(hasher);
    effective_style(widget, id, runtime, theme).layout_hash(hasher);
    // A measured leaf: its **content** (text…) affects the geometry without going
    // through the style — without this fingerprint, two different contents would
    // be conflated and the cache would keep an old layout.
    widget.measure_key(theme).hash(hasher);
    // Filling the parent is resolved during the walk rather than written into the style,
    // so the style hash alone would conflate a run that fills with one that shrink-wraps.
    let fills = widget.fill_axes(theme);
    (fills.horizontal, fills.vertical).hash(hasher);
    widget.main_axis_floor(theme).map(f32::to_bits).hash(hasher);
    widget.tile_shape().map(f32::to_bits).hash(hasher);
    children.len().hash(hasher);
    for (i, child) in children.iter().enumerate() {
        hash_node(
            child.as_ref(),
            child_id(id, i, child.as_ref()),
            runtime,
            theme,
            hasher,
            volatile,
        );
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::{Container, Flex};

    fn sig<Msg>(w: &dyn Widget<Msg>) -> u64 {
        signature_of(
            w,
            WidgetId::ROOT,
            &Runtime::default(),
            &crate::theme::Theme::default(),
        )
        .0
    }

    #[test]
    fn identical_trees_share_a_signature() {
        let a: Container<()> = Container::new().width(100.0).height(40.0);
        let b: Container<()> = Container::new().width(100.0).height(40.0);
        assert_eq!(sig(&a), sig(&b));
    }

    #[test]
    fn a_size_change_changes_the_signature() {
        let a: Container<()> = Container::new().width(100.0).height(40.0);
        let b: Container<()> = Container::new().width(101.0).height(40.0);
        assert_ne!(sig(&a), sig(&b));
    }

    #[test]
    fn child_count_changes_the_signature() {
        let one: Flex<()> = Flex::row().child(Container::new());
        let two: Flex<()> = Flex::row().child(Container::new()).child(Container::new());
        assert_ne!(sig(&one), sig(&two));
    }

    /// Filling the parent is resolved during the walk and never reaches the style, so
    /// the fingerprint has to ask for it separately — otherwise a row that fills and one
    /// that shrink-wraps are the same tree as far as the cache is concerned, and the
    /// second one silently gets the first one's layout.
    #[test]
    fn a_change_of_main_axis_size_changes_the_signature() {
        let fills: crate::Row<()> = crate::Row::new().child(Container::new());
        let hugs: crate::Row<()> = crate::Row::new().shrink_wrap().child(Container::new());
        assert_ne!(sig(&fills), sig(&hugs));
    }

    /// **A root holding an unconstrained box is reused** when nothing in it changed
    /// (milestone 593), and laid out again when its child or its rule did.
    #[test]
    fn a_measured_box_can_be_reused_and_still_notices_a_change() {
        let rt = Runtime::default();
        let theme = crate::theme::Theme::default();
        let c = Constraints::definite(Size::new(300.0, 200.0));
        let page = |label: &'static str, rule: crate::constraints::AxisConstraint| -> Flex<()> {
            Flex::column()
                // A spacer with a width of its own: an empty container takes the width on
                // offer (milestone 633), and this test is about the label's.
                .child(Container::new().width(10.0).height(20.0))
                .child(crate::ConstraintsTransformBox::new(crate::Text::new(label)).width(rule))
        };
        let unbounded = crate::constraints::AxisConstraint::Unbounded;
        let mut cache = LayoutCache::default();
        let first = cache.rects(WidgetId::ROOT, &page("one", unbounded), &rt, &theme, c);
        let again = cache.rects(WidgetId::ROOT, &page("one", unbounded), &rt, &theme, c);
        assert_eq!(first, again);
        assert_eq!(
            (cache.hits, cache.misses),
            (1, 1),
            "the second frame is reused"
        );

        // One thing at a time, each against the entry just before it.
        let longer = page("a much longer label", unbounded);
        let changed = cache.rects(WidgetId::ROOT, &longer, &rt, &theme, c);
        assert_eq!(cache.misses, 2, "a different child is a different box");
        assert!(changed.0.last().unwrap().width > first.0.last().unwrap().width);

        let fixed = page(
            "a much longer label",
            crate::constraints::AxisConstraint::Fixed(250.0),
        );
        let ruled = cache.rects(WidgetId::ROOT, &fixed, &rt, &theme, c);
        assert_eq!(cache.misses, 3, "a different rule is a different box");
        assert_eq!(ruled.0.last().unwrap().width, 250.0);

        let wider = page(
            "a much longer label",
            crate::constraints::AxisConstraint::Fixed(280.0),
        );
        let rewidth = cache.rects(WidgetId::ROOT, &wider, &rt, &theme, c);
        assert_eq!(cache.misses, 4, "a different number is a different rule");
        assert_eq!(rewidth.0.last().unwrap().width, 280.0);
    }

    /// A `LayoutBuilder` still cannot be trusted between frames.
    #[test]
    fn a_layout_builder_still_poisons_its_root() {
        let rt = Runtime::default();
        let theme = crate::theme::Theme::default();
        let c = Constraints::definite(Size::new(300.0, 200.0));
        let tree: crate::LayoutBuilder<()> = crate::LayoutBuilder::new(|_| Container::new());
        let mut cache = LayoutCache::default();
        cache.rects(WidgetId::ROOT, &tree, &rt, &theme, c);
        cache.rects(WidgetId::ROOT, &tree, &rt, &theme, c);
        assert_eq!((cache.hits, cache.misses), (0, 2));
    }

    #[test]
    fn cache_hits_on_repeated_identical_root() {
        let mut cache = LayoutCache::default();
        let rt = Runtime::default();
        let key = WidgetId::ROOT;
        let c = Constraints::definite(Size::new(200.0, 100.0));

        let tree: Container<()> = Container::new().width(200.0).height(100.0);
        let first = cache.rects(key, &tree, &rt, &crate::theme::Theme::default(), c);
        let second = cache.rects(key, &tree, &rt, &crate::theme::Theme::default(), c);
        assert_eq!(first, second, "the same rectangles");
        // 1 miss (computed), then 1 hit (reused).
        assert_eq!((cache.hits, cache.misses), (1, 1));
    }

    #[test]
    fn changed_constraints_miss() {
        let mut cache = LayoutCache::default();
        let rt = Runtime::default();
        let key = WidgetId::ROOT;
        let tree: Container<()> = Container::new();
        let theme = crate::theme::Theme::default();
        cache.rects(
            key,
            &tree,
            &rt,
            &theme,
            Constraints::definite(Size::new(200.0, 100.0)),
        );
        cache.rects(
            key,
            &tree,
            &rt,
            &theme,
            Constraints::definite(Size::new(300.0, 100.0)),
        );
        assert_eq!(
            (cache.hits, cache.misses),
            (0, 2),
            "size changed → recomputed"
        );
    }

    #[test]
    fn end_frame_evicts_untouched_roots() {
        let mut cache = LayoutCache::default();
        let rt = Runtime::default();
        let c = Constraints::definite(Size::new(10.0, 10.0));
        let tree: Container<()> = Container::new();
        cache.rects(
            WidgetId::ROOT,
            &tree,
            &rt,
            &crate::theme::Theme::default(),
            c,
        );
        cache.rects(
            WidgetId::ROOT.child(0),
            &tree,
            &rt,
            &crate::theme::Theme::default(),
            c,
        );
        cache.end_frame();
        assert_eq!(cache.entries.len(), 2);

        // Next frame: only one root touched → the other is evicted.
        cache.rects(
            WidgetId::ROOT,
            &tree,
            &rt,
            &crate::theme::Theme::default(),
            c,
        );
        cache.end_frame();
        assert_eq!(cache.entries.len(), 1);
        assert!(cache.entries.contains_key(&WidgetId::ROOT));
    }

    /// **A style in flight moves the fingerprint.** The same tree twice, at two points of
    /// one movement: nothing differs but the runtime.
    ///
    /// This is the cache's half of milestone 498, and it is not a formality. A font size
    /// reaches *layout* — the box a run of words is measured into — so a fingerprint
    /// blind to the style the theme swap put in force would answer every frame of the
    /// movement with the first frame's geometry. The words would grow inside a box that
    /// did not, and the layout would snap into place at the end. That failure is exactly
    /// what this cache's contract forbids: a hit must be bit-for-bit what the full
    /// computation would have produced.
    #[test]
    fn a_text_style_in_flight_moves_the_signature() {
        let tree = |size: f32| {
            crate::AnimatedDefaultTextStyle::<()>::new(
                0.10,
                frus_core::Curve::Linear,
                frus_core::TextStyle::NONE.size(size),
                crate::Text::new("Ag"),
            )
        };
        let theme = crate::theme::Theme::default();
        let mut rt = Runtime::default();
        rt.advance_text_styles(&tree(24.0), 1.0);
        rt.advance_text_styles(&tree(12.0), 0.02);
        let early = signature_of(&tree(12.0), WidgetId::ROOT, &rt, &theme).0;
        rt.advance_text_styles(&tree(12.0), 0.04);
        let later = signature_of(&tree(12.0), WidgetId::ROOT, &rt, &theme).0;
        assert_ne!(
            early, later,
            "the same tree at two points of one movement must not share a fingerprint"
        );
    }
}