guido 0.12.0

//! Arena-based widget storage for efficient partial layout.
//!
//! The Tree provides centralized widget storage using a sparse-set architecture
//! with generational indices, enabling efficient partial layout by only
//! re-laying out dirty subtrees.
//!
//! ## Key Features
//!
//! - **Generational Indices**: WidgetId contains index + generation to prevent
//!   ABA problems (detecting stale references to reallocated slots).
//!
//! - **Dense Storage**: Widgets stored contiguously for cache-friendly iteration
//!   during layout and paint passes.
//!
//! - **Sparse Map**: O(1) lookup from stable WidgetId to dense array index.
//!
//! - **Swap-Remove**: O(1) removal without creating holes in dense storage.
//!
//! - **Layout Metadata**: Each widget has associated metadata tracking
//!   parent/child relationships, dirty state, and cached constraints/size.
//!
//! - **Partial Layout**: When a widget is marked dirty, the dirty flag
//!   bubbles up to the nearest relayout boundary, which is added to the
//!   layout queue. Only dirty subtrees are re-laid out.

use smallvec::SmallVec;

use crate::layout::{Constraints, Size};
use crate::reactive::{CursorIcon, Prop};
use crate::transform::Transform;
use crate::widgets::{Rect, Widget};

/// Inline capacity for children. Most widgets have 0–4 children,
/// so this avoids a heap allocation for the common case.
type ChildrenVec = SmallVec<[WidgetId; 4]>;

/// Accumulated damage region for a frame.
#[derive(Debug, Clone)]
pub enum DamageRegion {
    /// No damage — nothing changed.
    None,
    /// Partial damage — only the given rect needs redraw.
    Partial(Rect),
    /// Full damage — the entire surface needs redraw.
    Full,
}

/// Unique identifier for a widget in the tree.
///
/// Uses a generational index design:
/// - `index`: Position in the sparse array (reusable after removal)
/// - `generation`: Version counter that increments when a slot is reused
///
/// This prevents ABA problems where a stale ID might accidentally refer
/// to a new widget that was allocated in the same slot.
#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
pub struct WidgetId {
    index: u32,
    generation: u32,
}

impl WidgetId {
    /// Create a new WidgetId with the given index and generation.
    /// This is internal - users get IDs from Tree::register().
    fn new(index: u32, generation: u32) -> Self {
        Self { index, generation }
    }

    /// Convert to a u64 for external use (e.g., render layer IDs).
    /// Combines generation (high bits) with index (low bits).
    pub fn as_u64(self) -> u64 {
        ((self.generation as u64) << 32) | (self.index as u64)
    }

    /// Reconstruct a WidgetId from a u64 (reverse of `as_u64`).
    pub fn from_u64(val: u64) -> Self {
        Self {
            index: val as u32,
            generation: (val >> 32) as u32,
        }
    }
}

/// Slot in the sparse map, pointing to a dense array slot.
///
/// The generation survives vacancy: it is bumped when the slot is reused,
/// so a stale `WidgetId` can never alias a widget that later recycled the
/// same index.
struct SparseSlot {
    /// Index into the dense array; `None` while the slot is vacant
    dense_index: Option<usize>,
    /// Generation of this slot (for validation)
    generation: u32,
}

/// One widget's slot in the arena: the widget itself plus everything the tree
/// knows about it.
///
/// Called a slot rather than a node because "node" already means two other
/// things here — the render tree's `RenderNode`, and informally any widget.
/// This is neither: it is the arena record, and a widget composed but not yet
/// registered has none.
struct Slot {
    /// The widget stored at this node
    widget: Box<dyn Widget>,
    /// Parent widget ID (None for root)
    parent: Option<WidgetId>,
    /// Child widget IDs (inline for ≤4 children to avoid heap allocation)
    children: ChildrenVec,
    /// Whether this widget needs layout
    needs_layout: bool,
    /// Whether this widget, or something below it, has asked to be painted.
    ///
    /// An ask and not a guarantee, and the difference is what #319 was: a
    /// widget the frame culled keeps it set, because nothing clears the flag
    /// of a widget that never painted, while the parent that skipped it is
    /// cleared by painting. So a widget's own flag says nothing about whether
    /// its ancestors know, and [`mark_needs_paint`](Tree::mark_needs_paint)
    /// must never stop on it — only on an ancestor's.
    needs_paint: bool,
    /// Whether this widget is a relayout boundary
    is_relayout_boundary: bool,
    /// What the last layout that ran was asked for, and what it answered,
    /// with the pass it ran in — because a measure and a layout can want
    /// different answers from the same widget and neither may be handed the
    /// other's. One entry, not one per pass: a layout that runs replaces what
    /// either pass left, so a second entry was only ever empty.
    cached: Option<CachedLayout>,
    /// Cached size from last layout
    cached_size: Option<Size>,
    /// Widget origin (set after layout by parent)
    origin: (f32, f32),
    /// Back-pointer to sparse array index (for swap-remove fixup)
    sparse_index: u32,
    /// Cached paint output from last frame
    cached_paint: Option<std::rc::Rc<crate::renderer::RenderNode>>,
    /// The interaction unit this node declares, if it is one. Descendants walk
    /// up to the nearest, and resolve hover, press and focus from it.
    control: Option<crate::widgets::Control>,
    /// Distance from this widget's top edge to the baseline of its first line
    /// of text, if it has one. Reported by leaves during layout and read by a
    /// parent aligning on `CrossAlignment::Baseline`.
    baseline: Option<f32>,
    /// How far this widget's *own* painting lands outside its bounds — its
    /// shadow, and where its transform can carry it. Published by the widget.
    own_paint_reach: f32,

    /// How far anything its children draw stands outside its box.
    ///
    /// Kept apart from `own_paint_reach` so the two can be maintained on
    /// different schedules: the widget republishes its own on every Paint job,
    /// which must stay cheap, while this one is a fact about a list and is
    /// re-measured only when that list is walked anyway.
    children_outset: f32,

    /// Whether this widget clips its children to its own edges.
    ///
    /// A scroller's content runs far past its viewport by design, and what the
    /// scroller paints is its own box however far the column inside it runs. So
    /// the overhang stops here: it is not gathered into this widget, and
    /// nothing above it hears about it either.
    ///
    /// Kept on the slot rather than asked of the widget because the gather runs
    /// from `set_own_paint_reach`, which has a tree and an id and no widget —
    /// and a one-shot clear at layout would be undone by the next descendant
    /// whose reach moves.
    clips_children: bool,

    /// The widest reach among this widget's children.
    ///
    /// Cached here rather than walked at paint, because the search that reads
    /// it is O(log n) and walking the children to feed it would be O(n) — the
    /// cost that search exists to avoid.
    ///
    /// Kept true between layouts on the two schedules `gather_reach_upward`
    /// describes: a reach that grew widens this by comparison, and one that
    /// shrank re-measures the siblings, because the child that shrank may have
    /// been the widest and the new answer is whatever the others say.
    children_reach: f32,
}

/// Central tree for widget storage using arena-based sparse-set architecture.
///
/// The tree stores all widgets in a dense Vec for cache-friendly iteration,
/// with a sparse map for O(1) lookup by WidgetId. Generational indices
/// prevent use-after-free bugs.
/// Which pass is laying a widget out.
///
/// A measure and a real layout ask the same widget different questions — a
/// measure reads where an animation is going, and runs before the surface
/// exists — so what a widget answers, and what may be reused from its cache,
/// belong to the pass that asked.
///
/// It travels with the call rather than in a thread-local: `MEASURE_FINAL` was
/// set and cleared around `measure_natural_size` with no drop guard, and
/// `DIFFERS_BETWEEN_PASSES` existed only because one shared cache entry could
/// not tell the two apart.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum LayoutPass {
    /// The layout that places what is on screen.
    Layout,
    /// The measure that reports a natural size, reading where animations are
    /// going rather than where they are — what a content-sized surface is
    /// configured from.
    Measure,
}

impl LayoutPass {
    /// Whether this pass reads where an animation is going rather than where
    /// it is now.
    pub fn is_measure(self) -> bool {
        matches!(self, LayoutPass::Measure)
    }
}

/// What one pass asked a widget for, and what it answered.
#[derive(Clone, Copy)]
struct CachedLayout {
    /// The pass that ran it.
    pass: LayoutPass,
    constraints: Constraints,
    size: Size,
    /// The least it could be, as the layout recorded it with
    /// [`LayoutCtx::set_minimum`] — or its size, when it recorded nothing.
    minimum: Size,
    /// Whether this answer belongs to the pass that asked — because something
    /// below was in flight, or a measure placed a value without spending its
    /// appearance. A settled subtree is neither, and either pass may read it.
    pass_dependent: bool,
}

/// Publish how far `widget` paints outside its own box, inside *its* own
/// Paint scope.
///
/// The scope is the point, and it is why this is one function rather than two
/// call sites. What the answer is read from — a transform — is a paint
/// property, so a write to it must repaint that widget and reflow nothing.
/// Read under no scope at all, which is what this was before #319, those reads
/// subscribed to nothing, and a widget culled before it ever painted could
/// never be told to come back.
///
/// Both passes that can be the last to run call it: the Paint job in `jobs`,
/// and [`Tree::layout_widget`] once its Layout scope has closed.
pub(crate) fn refresh_paint_reach(widget: &dyn Widget, tree: &mut Tree, id: WidgetId) {
    crate::reactive::with_signal_tracking(id, crate::jobs::JobType::Paint, || {
        widget.refresh_paint_bounds(tree, id)
    });
}

/// A child a container offered a positioned event to through its window: the
/// container, the child's place among its children, and the child.
#[derive(Clone, Copy)]
struct Offered {
    /// The surface root the offer was dispatched from: the tree holds every
    /// surface, and each keeps its own.
    root: WidgetId,
    parent: WidgetId,
    index: u32,
    child: WidgetId,
}

/// Which widgets the pointer still owes an event to, outside the window an
/// event is offered through.
///
/// A container offers a positioned event to the children that can be under
/// the point, and nothing else (#584). Two kinds of widget need more than that.
/// One the pointer has just left has to see the move that takes its hover
/// away, however far the pointer went. One a press landed on has to see the
/// moves and the release, wherever they land, because that is what a drag is.
/// Both were reached before by the walk over every child. Now they are
/// remembered instead.
///
/// It is what Flutter keeps for the same two reasons: `MouseTracker` remembers
/// what the last event hit, to send exits; `GestureBinding` keeps each
/// pointer's hit path from down to up. The DOM keeps a hover chain and an
/// implicit capture. Here the record is *offers* rather than hits, a superset
/// that needs no widget to report anything.
#[derive(Default)]
struct PointerRecord {
    /// What the event being dispatched offered by position.
    offering: Vec<Offered>,
    /// The containers that event reached. What the record owes in a container
    /// it did not reach — one whose parent clipped the point away, one covered by
    /// the sibling the walk stopped at and owed nothing — stays owed.
    reached: Vec<WidgetId>,
    /// What the last positioned event to reach each container offered by
    /// position. Sorted by container, so each finds its own with a search.
    last: Vec<Offered>,
    /// What the first press of a chord offered by position, until the last
    /// button is released. Sorted the same.
    pressed: Vec<Offered>,
    /// The chord that holds `pressed`: the surface root its first press
    /// entered at, and the buttons still down. One route per chord, as
    /// Pointer Events, X11's active grab and Flutter's button bitmask have it
    /// (#625). Tied to the root because a surface closed under the pointer is
    /// never sent the release, and its buttons must not hold another
    /// surface's next press.
    chord: Option<(WidgetId, u8)>,
    /// The event being dispatched is a press or release that neither opens nor
    /// closes the chord. It travels the press route alone: it is not
    /// hit-tested, and the hover record is neither told nor rewritten by it.
    chorded: bool,
    /// A container above is offering a point it clipped away. Below it nothing
    /// is under that point: only the owed are told, and only the press keeps
    /// the point, which its drag and its release need.
    withholding: bool,
    /// The surface root the event being dispatched entered at.
    root: Option<WidgetId>,
}

/// An `on_hover` a pointer event owes, held until the dispatch that carried
/// the event returns. See [`Tree::hover_changed`].
struct HoverChange {
    id: WidgetId,
    /// How far down the tree the widget stands: one at the root.
    depth: u32,
    hovered: bool,
    callback: crate::widgets::container::HoverCallback,
}

/// The bit a button holds in a chord.
fn button_bit(button: crate::widgets::MouseButton) -> u8 {
    1 << button as u8
}

/// The key the record is sorted by.
fn by_parent(entry: &Offered) -> u64 {
    entry.parent.as_u64()
}

/// Drop what nothing above still leads to.
///
/// An event reaches a container through its parent, so an entry is only worth
/// keeping while its container is itself recorded under one that is — down
/// from `root`. An entry carried because the event did not reach its
/// container is otherwise kept forever once the rows above it scroll away and
/// nothing reaches them either, and the record grows with every row the
/// pointer has crossed.
fn keep_what_the_root_reaches(record: &mut Vec<Offered>, root: WidgetId) {
    let mut reachable: SmallVec<[WidgetId; 32]> = SmallVec::new();
    reachable.push(root);
    // Another surface's entries are that surface's business.
    let mut kept: SmallVec<[bool; 64]> = record.iter().map(|entry| entry.root != root).collect();
    let mut next = 0;
    while let Some(&parent) = reachable.get(next) {
        next += 1;
        let key = parent.as_u64();
        let start = record.partition_point(|entry| by_parent(entry) < key);
        for (offset, entry) in record[start..].iter().enumerate() {
            if entry.parent != parent {
                break;
            }
            if !kept[start + offset] {
                kept[start + offset] = true;
                reachable.push(entry.child);
            }
        }
    }
    let mut index = 0;
    record.retain(|_| {
        index += 1;
        kept[index - 1]
    });
}

/// The children an event is offered to, the one drawn on top first: a window
/// of them, and the few outside it the pointer record owes one or a bounds
/// test found under the point.
///
/// Paint draws them in the order they stand, so the last stands on top, and a
/// point is asked of what covers it before what it covers — as Flutter's
/// `defaultHitTestChildren` walks from `lastChild`, and GTK's pick from the
/// last child (#636).
pub(crate) struct PointerTargets {
    window: std::ops::Range<usize>,
    /// Ascending, and taken from the end.
    owed: SmallVec<[usize; 4]>,
    /// Owed and offered without the event's position: the children a clipped
    /// point is owed to for anything but the press holding them.
    blind: SmallVec<[usize; 4]>,
}

impl PointerTargets {
    /// Every child: what an event the pointer did not send is offered to.
    fn every(len: usize) -> Self {
        Self {
            window: 0..len,
            owed: SmallVec::new(),
            blind: SmallVec::new(),
        }
    }

    /// The children at `indices`, given in ascending order: a route through
    /// them.
    fn only(indices: SmallVec<[usize; 4]>) -> Self {
        Self {
            window: 0..0,
            owed: indices,
            blind: SmallVec::new(),
        }
    }
}

impl Iterator for PointerTargets {
    /// A child, and whether it is offered the event's position.
    type Item = (usize, bool);

    /// The two merged, from the last index down. The owed ones lie outside
    /// the window, so nothing comes out twice.
    fn next(&mut self) -> Option<(usize, bool)> {
        let index = match self.owed.last() {
            Some(&owed) if self.window.is_empty() || owed >= self.window.end => self.owed.pop(),
            _ => self.window.next_back(),
        }?;
        Some((index, !self.blind.contains(&index)))
    }
}

pub struct Tree {
    /// Dense array of nodes (widgets + metadata)
    dense: Vec<Slot>,
    /// Sparse map from index to dense position + generation
    sparse: Vec<SparseSlot>,
    /// Free list of reusable sparse indices
    free_indices: Vec<u32>,
    /// Accumulated damage region for the current frame, keyed by the
    /// surface's root widget. Per-surface so that one surface's render
    /// cannot consume (or misreport) damage accumulated by another.
    damage: rustc_hash::FxHashMap<WidgetId, DamageRegion>,
    /// What time it is, for the pass currently running.
    ///
    /// A frame advances every animation in it, and asking the clock once per
    /// animation makes one frame several instants a few microseconds apart.
    /// More to the point, a widget that asks the clock cannot be asked about
    /// the middle of an animation: a test can only sleep and assert a band
    /// wide enough to survive a loaded machine, which is a band both a linear
    /// and an eased curve fit inside.
    ///
    /// `render_surface` writes it, around the three passes a frame is made of:
    /// the jobs advance the animations, layout measures what they produced,
    /// paint draws it. `None` between frames, where nobody should be reading
    /// it.
    frame_instant: Option<std::time::Instant>,
    /// Which pass is laying out, for as long as one is. Written by the one
    /// entry point every layout goes through and put back when it returns, so
    /// a measure nested inside a layout — the popup path — restores the outer
    /// pass on its way out.
    pass: LayoutPass,
    /// Raised while a widget lays out, by a read whose answer the pass
    /// decided: a value in flight, or one a measure placed without letting it
    /// appear. Read by the cache write, which is what makes a settled subtree
    /// reusable by the pass that did not lay it out.
    pass_dependent: bool,
    /// When the event now being dispatched happened.
    ///
    /// Not the same question as `frame_instant`: a frame advances what is
    /// already moving, an event says something started. They are different
    /// moments, and an event's is the older of the two — it was queued when the
    /// compositor sent it and is read when the frame runs.
    ///
    /// `dispatch_events` writes it, once per event, because it delivers them one
    /// at a time. `None` outside a dispatch, where nobody should be reading it.
    event_instant: Option<std::time::Instant>,

    /// Whether the press being dispatched was claimed by the focus it landed
    /// on, and so must not release it.
    ///
    /// A container that draws the focus it holds *is* the focused field to the
    /// person looking at it — its padding, its border, the gap beside the caret
    /// — so a press there is not a press on nothing. Only the widget can say
    /// so: by the time an event reaches it the point has been rebased through
    /// every ancestor, the scroll offset applied and the transform undone, and
    /// none of that can be redone from outside without walking the tree again.
    ///
    /// It used to say it by returning `EventResponse::Handled`, which also
    /// means "consumed" — so an outer clickable row never saw the press, and
    /// whether it worked depended on where the keyboard was (#308). The two are
    /// different sentences, and this is the channel for the one `Handled` was
    /// never meant to carry. The web splits them the same way: `preventDefault`
    /// cancels what the event would otherwise cause, `stopPropagation` stops it
    /// travelling, and a mousedown's default action is the focus change.
    ///
    /// `dispatch_events` clears it before each event and reads it after.
    /// Cleared going in rather than coming out, so nothing that returns early
    /// can leave it set for the next press.
    focus_claimed_the_press: bool,
    /// Whether a scroller has taken the move being dispatched as a drag of its
    /// content.
    ///
    /// The other sentence `Handled` cannot carry, and for the mirror-image
    /// reason: a scroller claims its drag *after* its children, so that a list
    /// inside a page takes the finger before the page does — but "a child
    /// handled it" is not "a scroller took it", and an ancestor that read it
    /// that way would let a text input extending a selection keep the list
    /// around it from scrolling. So the scroller that took the gesture says
    /// exactly that, and the ancestors that were watching the same press stop
    /// watching it (#437).
    ///
    /// Android says it the other way round and at the same seam: a nested
    /// scroller calls `requestDisallowInterceptTouchEvent`, and the
    /// `ScrollView` above it declines to intercept for the rest of the
    /// sequence.
    ///
    /// Cleared before every event, like the claim above it, so what it means
    /// is *this* move.
    drag_claimed_by_a_scroller: bool,
    /// The cursor the widget under the point of the event being dispatched
    /// declares, if any widget there declares one.
    ///
    /// Said on the way down by every widget the point is inside, and a widget
    /// is always asked before its children — so the last to say it is the
    /// innermost one, and the resolution needs no walk of its own: it is the
    /// dispatch's hit test, read at the end. CSS resolves `cursor` from the
    /// hit-test target up through its ancestors, which is the same answer.
    ///
    /// Where siblings overlap it still is: the one drawn on top is asked
    /// first, and a container that declares a cursor is hit wherever the point
    /// is inside it, so the walk stops there and the one beneath never gets to
    /// say anything (#636).
    ///
    /// Cleared before every event, like the two claims above it.
    cursor_under_the_point: Prop<CursorIcon>,
    /// Who the pointer still owes an event to. See [`PointerRecord`].
    pointer: PointerRecord,
    /// The `on_hover` calls the event being dispatched owes. Empty outside a
    /// dispatch.
    hover_changes: Vec<HoverChange>,
    /// The containers that declared `on_key_down` or `on_key_up`: a key nobody
    /// on the focus path took goes to them, without the tree being walked to
    /// find them.
    key_listeners: Vec<WidgetId>,
    /// The widgets a key or a focus change is being routed through: the focus
    /// path, or the way down to the listeners. Empty outside such a dispatch.
    key_route: SmallVec<[WidgetId; 16]>,
    /// The focus path a key has already gone up, while it goes down to the
    /// listeners: a listener on it let the key through once, and the way down
    /// to a listener inside it passes it again. `None` otherwise.
    key_heard_by: Option<crate::reactive::focus::FocusPath>,
    /// The widgets Tab stops at: the text inputs, and the containers that
    /// declared `focusable(true)`. Each with the turn it joined in, which is
    /// the order two of them in the same place are visited in. A map, so
    /// joining and leaving cost the same with five thousand of them as with
    /// five.
    tab_stops: rustc_hash::FxHashMap<WidgetId, u64>,
    /// The turn the next widget to become a Tab stop joins in.
    tab_stop_turn: u64,
    /// The `visible` each container that declared one was given, so Tab can
    /// pass over what is inside a hidden one without asking the widgets, and
    /// an animation inside one can stop and be queued again when it is shown
    /// (#666).
    declared_visible: rustc_hash::FxHashMap<WidgetId, Prop<bool>>,
    /// Which surface has the keyboard, as `FocusIn` and `FocusOut` said. A
    /// surface without it keeps its focus, and a field holding that focus
    /// draws no caret until the keyboard is back (#726).
    keyboard: KeyboardAt,
}

/// Where the keyboard is. One surface at most, as `wl_keyboard` has it.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
enum KeyboardAt {
    /// Nothing has said yet. Every surface counts as having it, which is what
    /// a tree driven without a compositor wants.
    #[default]
    Unknown,
    /// On the surface with this root.
    On(WidgetId),
    /// Left, and not entered anywhere since.
    Nowhere,
}

impl Tree {
    /// Create a new empty tree.
    pub fn new() -> Self {
        Self {
            dense: Vec::new(),
            sparse: Vec::new(),
            free_indices: Vec::new(),
            damage: rustc_hash::FxHashMap::default(),
            frame_instant: None,
            pass: LayoutPass::Layout,
            pass_dependent: false,
            event_instant: None,
            focus_claimed_the_press: false,
            drag_claimed_by_a_scroller: false,
            cursor_under_the_point: Prop::Unset,
            pointer: PointerRecord::default(),
            hover_changes: Vec::new(),
            key_listeners: Vec::new(),
            key_route: SmallVec::new(),
            key_heard_by: None,
            tab_stops: rustc_hash::FxHashMap::default(),
            tab_stop_turn: 0,
            declared_visible: rustc_hash::FxHashMap::default(),
            keyboard: KeyboardAt::Unknown,
        }
    }

    /// What time it is for the pass now running.
    ///
    /// Falls back to the clock for a call that arrives outside a pass — the
    /// behaviour every caller had before there was a frame instant at all,
    /// kept so a widget asking the time between passes gets a usable number
    /// rather than a panic on somebody's bar. A debug build says so first,
    /// naming the call site and the other clock.
    #[track_caller]
    pub fn frame_instant(&self) -> crate::clock::FrameInstant {
        Self::in_pass(
            self.frame_instant,
            "frame_instant",
            "a frame",
            "event_instant",
        )
    }

    /// When the event being dispatched happened.
    ///
    /// Falls back to the clock outside a dispatch, and says so, exactly as
    /// [`Self::frame_instant`] does.
    #[track_caller]
    pub fn event_instant(&self) -> crate::clock::EventInstant {
        Self::in_pass(
            self.event_instant,
            "event_instant",
            "a dispatch",
            "frame_instant",
        )
    }

    /// The moment a pass declared, or the wall clock and a word about it.
    ///
    /// `#[track_caller]` all the way down, and no closure in between: the
    /// message names the site that asked, and the rate limit is keyed on that
    /// site — so a `unwrap_or_else` here would collapse every caller in the
    /// application onto one key and silence all but the first.
    #[track_caller]
    fn in_pass<T: From<std::time::Instant>>(
        declared: Option<std::time::Instant>,
        read: &'static str,
        owner: &'static str,
        other: &'static str,
    ) -> T {
        match declared {
            Some(at) => at.into(),
            None => {
                crate::reactive::diagnostics::clock_outside_its_pass(read, owner, other);
                std::time::Instant::now().into()
            }
        }
    }

    /// Say that the press being dispatched landed on the focus, and so must not
    /// take it away.
    ///
    /// Called by a widget that draws the focus it is holding, from its own
    /// event handling, where the point is already in its coordinates. Reset for
    /// every event by `dispatch_events`.
    pub fn keep_the_focus_this_press_landed_on(&mut self) {
        self.focus_claimed_the_press = true;
    }

    /// Whether anything claimed the focus during the event just dispatched.
    ///
    /// `dispatch_events` is the only caller there should ever be: it is the one
    /// place that knows a press went unclaimed, which is the only question this
    /// answers. The setter beside it is public because a widget written outside
    /// this crate has to be able to say it; this one has no such caller.
    pub(crate) fn focus_claimed_the_press(&self) -> bool {
        self.focus_claimed_the_press
    }

    /// Say that the finger move being dispatched is scrolling this container's
    /// content, so that nothing above it claims the same gesture.
    ///
    /// Said by the scroller the gesture belongs to, on every move it belongs
    /// to it for — not only the one that won it, because an ancestor that
    /// re-armed on a later press would otherwise be watching a gesture already
    /// spoken for.
    pub(crate) fn a_scroller_is_dragging_its_content(&mut self) {
        self.drag_claimed_by_a_scroller = true;
    }

    /// Whether a scroller below the one asking has already taken this move.
    ///
    /// Only an ancestor asks, and only from the claim it makes after its
    /// children: a scroller checks this before it takes the gesture, and says
    /// [`a_scroller_is_dragging_its_content`](Self::a_scroller_is_dragging_its_content)
    /// after it has.
    pub(crate) fn a_scroller_below_took_the_drag(&self) -> bool {
        self.drag_claimed_by_a_scroller
    }

    /// Say which cursor the point of the event being dispatched should show,
    /// because it is inside this widget.
    ///
    /// Called from a widget's own event handling, where the point is already
    /// in its coordinates, and only for a point inside it. Whoever says it last
    /// wins, and the dispatch order makes that the innermost widget — see
    /// [`cursor_under_the_point`](Self::cursor_under_the_point). Public for
    /// the same reason
    /// [`keep_the_focus_this_press_landed_on`](Self::keep_the_focus_this_press_landed_on)
    /// is: a widget written outside this crate has to be able to say it.
    pub fn point_shows_cursor(&mut self, cursor: Prop<CursorIcon>) {
        self.cursor_under_the_point = cursor;
    }

    /// The cursor the innermost widget under the point declared during the
    /// event just dispatched, or `Unset` where nothing there declares one.
    ///
    /// `dispatch_events` reads it after every positioned pointer event and
    /// hands it to the loop; a test driving a tree without one reads it
    /// directly.
    pub fn cursor_under_the_point(&self) -> Prop<CursorIcon> {
        self.cursor_under_the_point
    }

    /// Declare when the event about to be dispatched happened, or `None` when
    /// the dispatch is over.
    ///
    /// `dispatch_events` is the caller in the loop; a test that wants to place
    /// an event in time is the other one.
    ///
    /// It also forgets what the previous event was claimed by — the focus, a
    /// scroller dragging its content, and the cursor under its point — which
    /// is what makes a claim mean *this* one. See
    /// [`keep_the_focus_this_press_landed_on`](Self::keep_the_focus_this_press_landed_on).
    pub fn set_event_instant(&mut self, at: Option<std::time::Instant>) {
        self.event_instant = at;
        self.focus_claimed_the_press = false;
        self.drag_claimed_by_a_scroller = false;
        self.cursor_under_the_point = Prop::Unset;
    }

    /// Declare the instant of the frame about to run, or `None` when it is
    /// over.
    ///
    /// The loop calls it twice: `render_surface` around a frame, and
    /// `ManagedSurface::layout_widget` around a surface's first layout, which
    /// is a pass of its own and the one every enter animation is seeded in.
    /// The other caller is a test — including a test of a widget written
    /// outside this crate, which is why this is public: a widget that can read
    /// the frame's instant is a widget whose behaviour over time can be asked
    /// about, and that needs somebody able to name the moment.
    pub fn set_frame_instant(&mut self, now: Option<std::time::Instant>) {
        self.frame_instant = now;
    }

    /// Register a widget in the tree and return its unique ID.
    ///
    /// This stores the widget and creates metadata for it.
    /// Parent-child relationships are set separately via `set_parent`.
    pub fn register(&mut self, widget: Box<dyn Widget>) -> WidgetId {
        // Allocate a sparse index (reuse from free list or allocate new)
        let (sparse_index, generation) = if let Some(idx) = self.free_indices.pop() {
            // Reuse a freed slot - increment the surviving generation so
            // stale IDs from the previous occupant can never match
            let generation = self.sparse[idx as usize].generation.wrapping_add(1);
            (idx, generation)
        } else {
            // Allocate new slot
            let idx = self.sparse.len() as u32;
            self.sparse.push(SparseSlot {
                dense_index: None,
                generation: 0,
            });
            (idx, 0)
        };

        let dense_index = self.dense.len();

        // Create the widget ID
        let id = WidgetId::new(sparse_index, generation);

        // Create the node (widget ID is passed to methods, not stored in widget)
        self.dense.push(Slot {
            widget,
            parent: None,
            children: ChildrenVec::new(),
            needs_layout: false,
            needs_paint: true,
            is_relayout_boundary: false,
            cached: None,
            cached_size: None,
            origin: (0.0, 0.0),
            sparse_index,
            cached_paint: None,
            control: None,
            baseline: None,
            own_paint_reach: 0.0,
            children_outset: 0.0,
            clips_children: false,
            children_reach: 0.0,
        });

        // Update sparse map
        self.sparse[sparse_index as usize] = SparseSlot {
            dense_index: Some(dense_index),
            generation,
        };

        id
    }

    /// Remove a widget from the tree.
    ///
    /// Uses swap-remove to maintain dense storage without holes.
    /// Also removes the widget from its parent's children list.
    pub fn unregister(&mut self, id: WidgetId) {
        // Validate and get dense index
        let dense_index = match self.get_dense_index(id) {
            Some(idx) => idx,
            None => return, // Invalid or stale ID
        };

        // A widget leaving the tree takes the focus with it. The focus path is
        // stored state, so unlike the bare generational id it used to be, it
        // does not stop matching on its own: its ancestors would go on
        // answering "the focus is inside me" for a widget that is gone.
        crate::reactive::release_focus_if_within(id);

        self.key_listeners.retain(|&listener| listener != id);
        self.tab_stops.remove(&id);
        self.declared_visible.remove(&id);

        // A surface root leaving takes its pointer record with it: a surface
        // closed under the pointer is never sent the leave that would.
        if self.dense[dense_index].parent.is_none() {
            self.pointer.last.retain(|entry| entry.root != id);
            self.pointer.pressed.retain(|entry| entry.root != id);
            if self.keyboard == KeyboardAt::On(id) {
                self.keyboard = KeyboardAt::Nowhere;
            }
            crate::reactive::focus::forget_surface(id);
        }

        // First, remove from parent's children list (before modifying dense array)
        if let Some(parent_id) = self.dense[dense_index].parent
            && let Some(parent_dense) = self.get_dense_index(parent_id)
        {
            self.dense[parent_dense].children.retain(|c| *c != id);
        }

        // Take ownership of the widget to drop it AFTER fixing up indices
        // This is critical for recursive unregistration during Drop
        let last_dense_index = self.dense.len() - 1;

        // Swap-remove: move last element to this position
        let removed_node = self.dense.swap_remove(dense_index);

        // Fix up the moved node's sparse entry (if we didn't remove the last element)
        if dense_index != last_dense_index && !self.dense.is_empty() {
            let moved_sparse_idx = self.dense[dense_index].sparse_index;
            self.sparse[moved_sparse_idx as usize].dense_index = Some(dense_index);
        }

        // Vacate the sparse slot, keeping its generation for the next allocation
        self.sparse[id.index as usize].dense_index = None;
        self.free_indices.push(id.index);

        // Now drop the removed widget (may trigger recursive unregisters)
        drop(removed_node);
    }

    /// Get the dense array index for a WidgetId, validating generation.
    fn get_dense_index(&self, id: WidgetId) -> Option<usize> {
        self.sparse
            .get(id.index as usize)
            .filter(|slot| slot.generation == id.generation)
            .and_then(|slot| slot.dense_index)
    }

    /// Access a widget via a closure.
    pub fn with_widget<R>(&self, id: WidgetId, f: impl FnOnce(&dyn Widget) -> R) -> Option<R> {
        self.get_dense_index(id)
            .map(|idx| f(&*self.dense[idx].widget))
    }

    /// Paint `id` into `node`. The root's way in, as
    /// [`layout_widget`](Self::layout_widget) is layout's.
    ///
    /// It opens the widget's own `JobType::Paint` scope, so what the widget
    /// reads while drawing belongs to it. Below the root that is
    /// [`PaintContext::paint_child`](crate::renderer::PaintContext::paint_child)'s
    /// job, and there is no third way: a widget never calls another's `paint`.
    ///
    /// `scale_factor` is the scale of the frame being painted, which every
    /// context below this one answers
    /// [`PaintContext::scale_factor`](crate::renderer::PaintContext::scale_factor)
    /// with. The loop passes its surface's; a paint outside a frame, as in a
    /// test, passes 1.
    pub fn paint_widget(
        &self,
        id: WidgetId,
        node: &mut crate::renderer::RenderNode,
        scale_factor: f32,
    ) {
        self.with_widget(id, |widget| {
            let mut ctx = crate::renderer::PaintContext::new(node, self, id, scale_factor);
            crate::reactive::with_signal_tracking(id, crate::jobs::JobType::Paint, || {
                widget.paint(&mut ctx)
            });
        });
    }

    /// Lay a widget out, as the pass that is already running.
    ///
    /// The root of the entry point every layout goes through — `LayoutCtx::
    /// layout_child` is the same call, from a parent. What happens around a
    /// widget's `layout` belongs here rather than inside each widget: the skip
    /// when there is nothing to redo, the tracking scope that attributes what
    /// the widget reads to the widget, and the cache write afterwards.
    ///
    /// Returns the size, or `None` for an id the tree cannot answer for.
    pub fn layout_widget(&mut self, id: WidgetId, constraints: Constraints) -> Option<Size> {
        let dirty = self.needs_layout(id);
        let cached = self.cached_for_pass(id, constraints);

        // Whether *this* subtree's answer belongs to the pass that asked is
        // the question the reads below answer; whatever the subtree around it
        // has already said is put back when this one is done.
        let enclosing = std::mem::replace(&mut self.pass_dependent, false);

        // Nothing to redo: this pass asked the same question last time and
        // nothing has marked the widget since.
        if let Some(entry) = cached
            && !dirty
        {
            crate::render_stats::record_layout_skipped();
            // A skipped subtree read nothing this pass, and still answers what
            // it answered last time.
            self.pass_dependent = enclosing || entry.pass_dependent;
            return Some(entry.size);
        }
        crate::render_stats::record_layout_executed_with_reasons(
            crate::render_stats::LayoutReasons {
                constraints_changed: cached.is_none(),
                reactive_changed: dirty,
            },
        );

        let laid_out = self.with_widget_mut(id, |widget, id, tree| {
            // A baseline is an answer of this layout, like the size: one the
            // widget does not give again — hidden, or its text gone — is one
            // it no longer has.
            tree.forget_baseline(id);
            let mut ctx = LayoutCtx {
                tree,
                id,
                clips_children: false,
                minimum: None,
            };
            // The scope is the widget's own, so what it reads while laying out
            // belongs to it — including a widget from outside the crate, which
            // used to have to know to open one, and was attributed to its
            // nearest ancestor when it did not.
            let size =
                crate::reactive::with_signal_tracking(id, crate::jobs::JobType::Layout, || {
                    widget.layout(&mut ctx, constraints)
                });
            let clips = ctx.clips_children;
            // Never more than the size: a box held under its content by a
            // declared maximum is as small as it is.
            let minimum = ctx.minimum.map_or(size, |least| {
                Size::new(least.width.min(size.width), least.height.min(size.height))
            });
            tree.cache_answer(id, constraints, size, minimum);
            tree.clear_needs_layout(id);
            // What its children paint, and how far past its own box this one
            // does — both measured against the size it has just answered with,
            // which is why they are here rather than inside the widget: from in
            // there the only size to measure against was the one it had last
            // time.
            tree.set_clips_children(id, clips, size);
            if !clips {
                tree.remeasure_children(id, size);
            }
            // What this widget paints outside its own box, published from the
            // size it has just answered with — which is why it is here rather
            // than inside the widget: the walk it starts reads that size, and
            // a widget publishing from inside its own layout was publishing
            // against the box it had last time.
            //
            // On either pass, because either may be the last one that ran: a
            // popup is measured before it is ever laid out, and the layout
            // after it reads that answer back where the subtree is settled.
            refresh_paint_reach(&*widget, tree, id);
            size
        });

        // Upward, to whatever is laying this one out — on both ways out, so an
        // id the tree cannot answer for does not drop what the widget around
        // it has already said.
        self.pass_dependent |= enclosing;
        laid_out
    }

    /// The same, as a measure: animations read where they are going, and what
    /// it caches is kept apart from what the layout caches.
    pub fn measure_widget(&mut self, id: WidgetId, constraints: Constraints) -> Option<Size> {
        self.with_pass(LayoutPass::Measure, |tree| {
            tree.layout_widget(id, constraints)
        })
    }

    /// Whether the running pass reads where animations are going rather than
    /// where they are.
    pub fn measuring(&self) -> bool {
        self.pass.is_measure()
    }

    /// Run `f` under `pass`, and put back whatever pass was running.
    fn with_pass<R>(&mut self, pass: LayoutPass, f: impl FnOnce(&mut Tree) -> R) -> R {
        let previous = std::mem::replace(&mut self.pass, pass);
        let out = f(self);
        self.pass = previous;
        out
    }

    /// Mutate a widget via a closure.
    ///
    /// The closure receives the widget ID, mutable access to the widget, and the tree,
    /// allowing operations that need all three (like calling layout on children).
    ///
    /// The widget is temporarily extracted from the tree during the closure execution.
    /// Returns `None` if the widget is not found (invalid or stale ID).
    pub fn with_widget_mut<R>(
        &mut self,
        id: WidgetId,
        f: impl FnOnce(&mut dyn Widget, WidgetId, &mut Tree) -> R,
    ) -> Option<R> {
        let dense_index = self.get_dense_index(id)?;

        // Placeholder widget for extraction
        struct PlaceholderWidget;
        impl Widget for PlaceholderWidget {
            fn layout(&mut self, _: &mut LayoutCtx, _: Constraints) -> Size {
                Size::zero()
            }
            fn paint(&self, _: &mut crate::renderer::PaintContext) {}
        }

        // Extract widget
        let mut widget = std::mem::replace(
            &mut self.dense[dense_index].widget,
            Box::new(PlaceholderWidget),
        );

        // Run closure with &mut dyn Widget, WidgetId, and &mut Tree
        let result = f(&mut *widget, id, self);

        // Restore widget
        if let Some(idx) = self.get_dense_index(id) {
            self.dense[idx].widget = widget;
        }

        Some(result)
    }

    /// Check if a widget is registered.
    pub fn contains(&self, id: WidgetId) -> bool {
        self.get_dense_index(id).is_some()
    }

    /// Set the parent of a widget.
    ///
    /// Also adds the widget to the parent's children list.
    pub fn set_parent(&mut self, child_id: WidgetId, parent_id: WidgetId) {
        // Update child's parent reference
        if let Some(child_dense) = self.get_dense_index(child_id) {
            self.dense[child_dense].parent = Some(parent_id);
        }

        // Add to parent's children list (if not already present)
        if let Some(parent_dense) = self.get_dense_index(parent_id) {
            let children = &mut self.dense[parent_dense].children;
            if !children.contains(&child_id) {
                children.push(child_id);
            }
        }
    }

    /// Get the parent of a widget.
    pub fn get_parent(&self, id: WidgetId) -> Option<WidgetId> {
        self.get_dense_index(id)
            .and_then(|idx| self.dense[idx].parent)
    }

    /// Record that this node is an interaction unit.
    ///
    /// Containers call this as they enter the tree, exactly like the style
    /// declarations beside it.
    pub(crate) fn set_control(&mut self, id: WidgetId, control: Option<crate::widgets::Control>) {
        if let Some(idx) = self.get_dense_index(id) {
            self.dense[idx].control = control;
        }
    }

    /// The interaction unit a widget belongs to: itself if it is one,
    /// otherwise the nearest ancestor that is.
    ///
    /// Returns a handle holding signals, not values, on the same contract as
    /// the style walks: reading them is what subscribes, so the caller must do
    /// it inside its own tracking scope.
    pub fn nearest_control(&self, id: WidgetId) -> Option<crate::widgets::Control> {
        let mut cursor = Some(id);
        while let Some(node) = cursor {
            let idx = self.get_dense_index(node)?;
            if let Some(control) = self.dense[idx].control {
                return Some(control);
            }
            cursor = self.dense[idx].parent;
        }
        None
    }

    /// Declare how far this widget paints outside its own bounds.
    ///
    /// Widgets that cast a shadow or stroke set this during layout; it widens
    /// the damage they report without touching the size they occupy.
    /// Report where this widget's text sits on its baseline.
    ///
    /// Only leaves that draw text have one. A parent aligning on
    /// `CrossAlignment::Baseline` shifts its children so these coincide;
    /// anything without a baseline is aligned by its bottom edge, as CSS does.
    pub fn set_baseline(&mut self, id: WidgetId, baseline: f32) {
        if let Some(idx) = self.get_dense_index(id) {
            self.dense[idx].baseline = Some(baseline);
        }
    }

    /// Drop what the widget reported last time, ahead of a layout that may
    /// report nothing.
    fn forget_baseline(&mut self, id: WidgetId) {
        if let Some(idx) = self.get_dense_index(id) {
            self.dense[idx].baseline = None;
        }
    }

    /// The widget's baseline, if it reported one.
    pub fn baseline(&self, id: WidgetId) -> Option<f32> {
        self.get_dense_index(id)
            .and_then(|idx| self.dense[idx].baseline)
    }

    /// Record how far this widget's own painting lands outside its bounds.
    ///
    /// Named for the half it writes, because `paint_overflow` returns the union
    /// of that with what the children add, and a setter and getter that are not
    /// inverses should not share a name.
    ///
    /// What a widget draws also includes what its descendants draw, and that
    /// half is `children_outset`, gathered upward here when the union a parent
    /// can see actually moves. Without it a row holding a box that a transform
    /// carried outside it reports nothing, an ancestor narrowing by laid-out
    /// bounds drops the row, and the visible box goes with it. Flutter and
    /// Blink union descendant paint bounds up the tree for the same reason.
    ///
    /// A reach that shrinks damages the ring it is vacating before it goes, on
    /// the same contract as `set_origin`: the rect a repaint reports is built
    /// from the reach the widget has *now*, so nothing else would ever name
    /// the pixels it painted a frame ago.
    pub fn set_own_paint_reach(&mut self, id: WidgetId, reach: f32) {
        let Some(idx) = self.get_dense_index(id) else {
            return;
        };
        let reach = reach.max(0.0);
        if self.dense[idx].own_paint_reach == reach {
            return;
        }
        // Against the union, not against the half being written: an ancestor
        // reads `paint_overflow`, so a widget whose children already reach
        // further has moved nothing anyone can see, and the walk above it —
        // whose shrink path re-measures siblings — is pure cost.
        let before = self.paint_overflow_from(self.dense[idx].own_paint_reach, idx);
        let after = self.paint_overflow_from(reach, idx);
        // A reach that shrinks vacates the ring between the two, and the rect
        // built from the new one stops short of it. Damaged before the write,
        // while the old reach is still what this widget answers — the same
        // shape `set_origin` uses for the geometry it owns, and for the same
        // reason. A reach that *grows* needs none of it: the mark that follows
        // builds a rect from the wider value, and it contains the narrower one.
        if after < before
            && let Some((root, vacated)) = self.surface_relative_damage_and_root(id)
        {
            self.expand_damage_rect(root, vacated);
        }
        self.dense[idx].own_paint_reach = reach;
        if before == after {
            return;
        }
        self.gather_reach_upward(id, before, after > before);
    }

    /// Carry a change in a child's reach into the ancestors it affects.
    ///
    /// A reach that **grew** only ever widens, so each ancestor is compared and
    /// the walk stops at the first one already wide enough — nothing above it
    /// can be narrow either. O(depth), no walk over siblings.
    ///
    /// A reach that **shrank** cannot be answered by comparison: this child may
    /// have been the widest, and the new maximum is whatever the others say. So
    /// that path re-measures — but only where it has to. A child that was not
    /// the maximum on either axis cannot have changed one by getting smaller,
    /// which is the common case and the one that matters: the return leg of a
    /// spring shrinks on *every frame*, so a fold over the siblings there would
    /// be an O(children) walk per frame, and a staggered list of them O(n²).
    fn gather_reach_upward(&mut self, from: WidgetId, was: f32, grew: bool) {
        let mut child = from;
        let mut was = was;
        while let Some(parent) = self.get_parent(child) {
            let Some(parent_idx) = self.get_dense_index(parent) else {
                return;
            };
            let (had_outset, had_reach) = (
                self.dense[parent_idx].children_outset,
                self.dense[parent_idx].children_reach,
            );
            if self.dense[parent_idx].clips_children {
                // The overhang stops here. The search below this widget still
                // wants to know how far its children reach, so that is carried;
                // what this widget paints is its own box, so nothing above it
                // learns anything and the walk is done.
                let (_, widest) = self.measure_children(parent, None);
                self.dense[parent_idx].children_reach = widest;
                self.dense[parent_idx].children_outset = 0.0;
                return;
            }
            let (outset, widest) = if grew {
                (
                    had_outset.max(self.child_paint_outset(child, parent)),
                    had_reach.max(self.paint_overflow(child)),
                )
            } else if was < had_reach && self.child_outset_from(was, child, parent) < had_outset {
                // Not the widest on either axis before it shrank, so neither
                // maximum can have moved, and nothing above can have either.
                return;
            } else {
                self.measure_children(parent, None)
            };

            if (outset, widest) == (had_outset, had_reach) {
                // Nothing moved here, so nothing above it moved either.
                return;
            }
            // What this parent's own reach *was*, which is what the guard on
            // the next level up needs — the child's previous `paint_overflow`,
            // not the maximum over its siblings. The two differ wherever a
            // node's children reach less far than they stand outside its box,
            // which is every scroller.
            was = self.dense[parent_idx].own_paint_reach.max(had_outset);
            self.dense[parent_idx].children_outset = outset;
            self.dense[parent_idx].children_reach = widest;
            child = parent;
        }
    }

    /// How far what `child` draws stands outside `parent`'s own box.
    fn child_paint_outset(&self, child: WidgetId, parent: WidgetId) -> f32 {
        self.child_outset_from(self.paint_overflow(child), child, parent)
    }

    /// The same, for a reach the caller names — which is how the shrink path
    /// asks what a child's outset *was* without having kept the rect.
    fn child_outset_from(&self, reach: f32, child: WidgetId, parent: WidgetId) -> f32 {
        let (Some(child_box), Some(parent_box)) = (self.get_bounds(child), self.get_bounds(parent))
        else {
            return 0.0;
        };
        // A child's bounds are relative to its parent, whose own box therefore
        // starts at the origin.
        child_box
            .outset(reach)
            .outset_beyond(crate::widgets::Rect::from_size(crate::layout::Size::new(
                parent_box.width,
                parent_box.height,
            )))
    }

    /// Both facts a narrowing needs about a widget's children: how far the
    /// furthest of them stands outside the box, and the widest reach any of
    /// them has.
    ///
    /// One walk and one lookup per child — the sparse-then-dense resolve is the
    /// expensive half, and every number below comes off the slot it lands on.
    fn measure_children(&self, id: WidgetId, own_size: Option<Size>) -> (f32, f32) {
        // The size this pass just measured, where the caller has it: the cache
        // is written when the widget's layout *returns*, so a container asking
        // in the middle of its own would otherwise be measuring its children
        // against the box it had last time — or, on a first layout, against
        // none at all.
        let Some(parent_box) = own_size
            .or_else(|| self.get_bounds(id).map(|b| Size::new(b.width, b.height)))
            .map(crate::widgets::Rect::from_size)
        else {
            return (0.0, 0.0);
        };
        self.get_children(id)
            .iter()
            .filter_map(|&child| self.get_dense_index(child))
            .fold((0.0f32, 0.0f32), |(outset, widest), idx| {
                let slot = &self.dense[idx];
                // The reach counts whether or not the child has been laid out
                // — the grow path in `gather_reach_upward` folds it
                // unconditionally, and the two have to answer the same. Only
                // the outset needs a box to be measured against.
                let reach = slot.own_paint_reach.max(slot.children_outset);
                let widest = widest.max(reach);
                let Some(size) = slot.cached_size else {
                    return (outset, widest);
                };
                let drawn = crate::widgets::Rect::new(
                    slot.origin.0,
                    slot.origin.1,
                    size.width,
                    size.height,
                )
                .outset(reach);
                (
                    outset.max(drawn.outset_beyond(parent_box)),
                    widest.max(reach),
                )
            })
    }

    /// Republish both, as this widget's own layout has just measured them.
    /// Replaces rather than grows, which is what un-sticks a reach that shrank.
    ///
    /// Gathers upward when the union it feeds actually moved — see the body
    /// for why bottom-up layout is not enough on its own.
    fn remeasure_children(&mut self, id: WidgetId, own_size: Size) {
        let (outset, widest) = self.measure_children(id, Some(own_size));
        let Some(idx) = self.get_dense_index(id) else {
            return;
        };
        let before = self.paint_overflow(id);
        self.dense[idx].children_outset = outset;
        self.dense[idx].children_reach = widest;
        let after = self.paint_overflow(id);
        if before != after {
            // Layout is bottom-up, so an ancestor inside the same pass will
            // measure this for itself — but a widget with a fixed size is its
            // own relayout boundary and the pass starts there, with no ancestor
            // to follow. Then this is the only thing that tells them.
            self.gather_reach_upward(id, before, after > before);
        }
    }

    /// Record whether this widget clips its children to its own edges, and
    /// forget any overhang already gathered into it.
    ///
    /// The widest *reach* is kept: the search that narrows the children still
    /// needs it, because a child inside the clip can still draw outside its own
    /// bounds and into view.
    fn set_clips_children(&mut self, id: WidgetId, clips: bool, own_size: Size) {
        let Some(idx) = self.get_dense_index(id) else {
            return;
        };
        self.dense[idx].clips_children = clips;
        if clips {
            self.dense[idx].children_outset = 0.0;
            let (_, widest) = self.measure_children(id, Some(own_size));
            self.dense[idx].children_reach = widest;
        }
    }

    /// How far the furthest of this widget's children stands outside its box.
    #[cfg(test)]
    pub(crate) fn children_outset(&self, id: WidgetId) -> f32 {
        self.get_dense_index(id)
            .map_or(0.0, |idx| self.dense[idx].children_outset)
    }

    /// The children of a widget, ordered along `axis`, whose laid-out span —
    /// grown by `reach` — can overlap `near..far` on that axis.
    ///
    /// Paint asks it with the rect it can see, and event dispatch with the
    /// point under the pointer, so the two narrow by the one rule: a child paint
    /// would draw is a child an event can reach. One either side for the
    /// boundary: the predicates compare edges with `<=` and `<`, so a child
    /// whose edge lands exactly on `near` or `far` can fall either way under
    /// float rounding. What a child's own transform does to where it draws is
    /// `reach`, measured rather than guessed at one child's width.
    pub(crate) fn window_of(
        &self,
        children: &[WidgetId],
        axis: crate::layout::Axis,
        (near, far): (f32, f32),
        reach: f32,
    ) -> std::ops::Range<usize> {
        let (near, far) = (near - reach, far + reach);
        let span = |cid: WidgetId| self.get_bounds(cid).map(|b| b.span(axis));
        let first = children.partition_point(|&cid| span(cid).is_some_and(|(_, f)| f <= near));
        // From `first`, so `last` cannot come out below it however degenerate
        // the span is, and the range is well formed by construction.
        let last = first
            + children[first..].partition_point(|&cid| span(cid).is_some_and(|(n, _)| n < far));
        first.saturating_sub(1)..(last + 1).min(children.len())
    }

    /// Deliver `event` to the surface root `root`, keeping the pointer record.
    ///
    /// The one way an event enters a tree: the loop's dispatch, and every test
    /// that hands a root an event, go through here. What the containers below
    /// offered a positioned event through their windows is what the next event
    /// is owed as well, so a widget the pointer left sees it go; and what they
    /// offered the first press of a chord is owed every event until the last
    /// button is up, so a drag reaches the widget it started on wherever it
    /// goes. A press or release of another button in between goes along that
    /// route alone, without a new hit test (#625).
    pub fn dispatch(
        &mut self,
        root: WidgetId,
        event: &crate::widgets::Event,
    ) -> Option<crate::widgets::EventResponse> {
        use crate::widgets::Event;
        if event.follows_the_focus() {
            // The focus stays through the keyboard leaving; coming back, the
            // surface has whatever it had focused when the focus went to
            // another — the popup it opened, say, whose field has since gone.
            // A leave can arrive after the enter on the surface the keyboard
            // went to, so it speaks only for a surface that had it.
            match event {
                Event::FocusOut
                    if matches!(self.keyboard, KeyboardAt::Unknown)
                        || self.keyboard == KeyboardAt::On(root) =>
                {
                    self.keyboard = KeyboardAt::Nowhere;
                }
                Event::FocusIn => {
                    self.keyboard = KeyboardAt::On(root);
                    crate::reactive::focus::give_back_kept_focus(self, root);
                }
                _ => {}
            }
            // A container disabled under the pointer gives up its hover to
            // whatever event reaches it, a key included.
            let response = self.dispatch_key(root, event);
            self.deliver_hover_changes();
            return response;
        }
        self.pointer.offering.clear();
        self.pointer.reached.clear();
        self.pointer.withholding = false;
        self.pointer.root = Some(root);
        let held = match self.pointer.chord {
            Some((chord_root, held)) if chord_root == root => held,
            _ => 0,
        };
        let (after, press_or_release) = match event {
            Event::MouseDown { button, .. } => (held | button_bit(*button), true),
            Event::MouseUp { button, .. } => (held & !button_bit(*button), true),
            _ => (held, false),
        };
        self.pointer.chorded = press_or_release && held != 0 && after != 0;
        let response = self.with_widget_mut(root, |widget, id, tree| widget.event(tree, id, event));
        let record = &mut self.pointer;
        if event.coords().is_some() && !record.chorded {
            let PointerRecord {
                offering,
                last,
                reached,
                ..
            } = record;
            reached.sort_unstable_by_key(|id| id.as_u64());
            last.retain(|entry| {
                reached
                    .binary_search_by_key(&by_parent(entry), |id| id.as_u64())
                    .is_err()
            });
            last.append(offering);
            last.sort_unstable_by_key(by_parent);
            keep_what_the_root_reaches(last, root);
        }
        match event {
            Event::MouseDown { .. } if !record.chorded => {
                record.pressed.clear();
                record
                    .pressed
                    .extend(record.last.iter().filter(|entry| entry.root == root));
            }
            Event::MouseUp { .. } if after == 0 => record.pressed.clear(),
            Event::MouseLeave => {
                record.pressed.clear();
                record.chord = None;
                record.last.retain(|entry| entry.root != root);
            }
            _ => {}
        }
        if press_or_release {
            record.chord = (after != 0).then_some((root, after));
        }
        self.deliver_hover_changes();
        response
    }

    /// Owe `callback` the hover `id` just took on, until the dispatch carrying
    /// the event returns.
    ///
    /// The walk visits a parent before its children and the sibling drawn on
    /// top first, which is neither order a hover callback is owed in. So the
    /// state changes where the walk finds it and the callback waits: when the
    /// dispatch returns, [`Self::deliver_hover_changes`] says every leave
    /// before any enter (#657).
    ///
    /// A widget whose hover flips back within the same event — a scroller
    /// taking back a press its child had just been told about — changed
    /// nothing, and hears nothing.
    pub(crate) fn hover_changed(
        &mut self,
        id: WidgetId,
        hovered: bool,
        callback: &crate::widgets::container::HoverCallback,
    ) {
        if let Some(index) = self.hover_changes.iter().position(|c| c.id == id) {
            self.hover_changes.remove(index);
            return;
        }
        let depth = self.ancestors(id).count() as u32;
        self.hover_changes.push(HoverChange {
            id,
            depth,
            hovered,
            callback: std::rc::Rc::clone(callback),
        });
    }

    /// Say what [`Self::hover_changed`] held: every leave, innermost first,
    /// then every enter, outermost first, with widgets at the same depth in
    /// the order the walk reached them.
    ///
    /// The order the DOM, Chromium's `BoundaryEventDispatcher`, Flutter's
    /// `MouseTracker`, GTK and Qt each give: the widget the pointer left hears
    /// it first, the widget it reached hears it last, and a container holding
    /// both was never told anything.
    pub(crate) fn deliver_hover_changes(&mut self) {
        if self.hover_changes.is_empty() {
            return;
        }
        let mut changes = std::mem::take(&mut self.hover_changes);
        changes.sort_by(|a, b| {
            a.hovered.cmp(&b.hovered).then(if a.hovered {
                a.depth.cmp(&b.depth)
            } else {
                b.depth.cmp(&a.depth)
            })
        });
        for change in changes.drain(..) {
            (change.callback)(change.hovered);
        }
        self.hover_changes = changes;
    }

    /// Whether the surface rooted at `root` has the keyboard. Before the
    /// first `FocusIn` or `FocusOut`, every surface does.
    pub(crate) fn has_keyboard(&self, root: WidgetId) -> bool {
        match self.keyboard {
            KeyboardAt::Unknown => true,
            KeyboardAt::On(at) => at == root,
            KeyboardAt::Nowhere => false,
        }
    }

    /// Whether a `FocusIn` said the keyboard is on the surface rooted at
    /// `root`. Unlike [`has_keyboard`](Self::has_keyboard), not knowing is no.
    pub(crate) fn keyboard_is_on(&self, root: WidgetId) -> bool {
        self.keyboard == KeyboardAt::On(root)
    }

    /// Route a key, or the surface gaining or losing the keyboard, the way
    /// Flutter's `FocusManager` does: down to the focused widget, which has it
    /// first, and up through its ancestors until one takes it. A key nobody on
    /// that path took then goes down to the containers listening for keys —
    /// the innermost first, as the walk over every widget used to have it —
    /// which is what lets a menu close on Escape with nothing focused. Nothing
    /// else is asked. A Tab neither route took then moves the focus — see
    /// [`Self::next_tab_stop`].
    ///
    /// Down from the root rather than to each widget directly, so a hidden or
    /// disabled container still stops what is routed through it.
    fn dispatch_key(
        &mut self,
        root: WidgetId,
        event: &crate::widgets::Event,
    ) -> Option<crate::widgets::EventResponse> {
        use crate::widgets::{Event, EventResponse};
        let focus = crate::reactive::focus::focus_path_untracked();

        // Nobody routed to is the root ignoring it; `None` is a root that is
        // not there.
        self.get_dense_index(root)?;
        let mut response = Some(EventResponse::Ignored);
        if focus.root() == Some(root) {
            self.key_route.clear();
            self.key_route.extend_from_slice(focus.chain());
            response = self.route_through(root, event);
        }
        // A key, repeats included; gaining or losing the keyboard stays on
        // the focus path.
        if response != Some(EventResponse::Handled)
            && matches!(event, Event::KeyDown { .. } | Event::KeyUp { .. })
        {
            let mut route = std::mem::take(&mut self.key_route);
            route.clear();
            for &listener in &self.key_listeners {
                if focus.contains(listener) {
                    continue;
                }
                // Up to the root, or to where another listener's way down
                // already runs; a walk that ends anywhere else is another
                // surface's, and is taken back.
                let mark = route.len();
                let mut reached = false;
                for id in self.ancestors(listener) {
                    if route.contains(&id) {
                        reached = true;
                        break;
                    }
                    route.push(id);
                    if id == root {
                        reached = true;
                        break;
                    }
                }
                if !reached {
                    route.truncate(mark);
                }
            }
            self.key_route = route;
            if !self.key_route.is_empty() {
                self.key_heard_by = Some(focus.clone());
                response = self.route_through(root, event);
                self.key_heard_by = None;
            }
        }
        self.key_route.clear();

        // What Tab does by default, once nothing on either route took it: the
        // DOM's default action, run after dispatch, and Flutter's root
        // `Shortcuts`, reached only after the focused chain.
        if response != Some(EventResponse::Handled)
            && let Event::KeyDown {
                key: crate::widgets::Key::Tab,
                modifiers,
                ..
            } = event
            && !(modifiers.ctrl || modifiers.alt || modifiers.logo)
        {
            let from = focus.widget().filter(|_| focus.root() == Some(root));
            if let Some(next) = self.next_tab_stop(root, from, modifiers.shift) {
                crate::reactive::focus::request_focus_by_keyboard(self, next);
                response = Some(EventResponse::Handled);
            }
        }
        response
    }

    /// Where Tab — or Shift+Tab, `backwards` — takes the focus from `from` on
    /// the surface rooted at `root`.
    ///
    /// The stops in reading order, as GTK's `focus_sort_tab` has it: by the
    /// vertical centre of the box each was laid out in, then the horizontal
    /// one, ties in the order they joined the tree. A stop that is hidden,
    /// disabled or playing its exit is not one. The ends wrap. With nothing
    /// focused here, Tab takes the first and Shift+Tab the last; from a
    /// widget that is not a stop, the next stop after where it stands.
    fn next_tab_stop(
        &self,
        root: WidgetId,
        from: Option<WidgetId>,
        backwards: bool,
    ) -> Option<WidgetId> {
        let reading_place = |id: WidgetId| {
            let (its_root, laid_out) = self.surface_relative_layout_and_root(id)?;
            (its_root == root).then(|| {
                (
                    laid_out.y + laid_out.height / 2.0,
                    laid_out.x + laid_out.width / 2.0,
                )
            })
        };
        let in_reading_order =
            |a: &(f32, f32), b: &(f32, f32)| a.0.total_cmp(&b.0).then(a.1.total_cmp(&b.1));
        let mut stops: SmallVec<[_; 16]> = self
            .tab_stops
            .iter()
            .filter_map(|(&id, &turn)| Some((reading_place(id)?, turn, id)))
            .filter(|&(_, _, id)| self.takes_tab(id))
            .collect();
        // A tie goes to the stop that joined the tree first.
        stops.sort_unstable_by(|a, b| in_reading_order(&a.0, &b.0).then(a.1.cmp(&b.1)));
        let round = if backwards {
            stops.last()
        } else {
            stops.first()
        }?
        .2;
        let Some(from) = from else {
            return Some(round);
        };
        let next = match stops.iter().position(|&(_, _, id)| id == from) {
            Some(at) if backwards => at.checked_sub(1).map(|at| stops[at].2),
            Some(at) => stops.get(at + 1).map(|&(_, _, id)| id),
            // A widget with no laid-out place of its own stands nowhere, and
            // Tab from it goes round as from nothing focused.
            None => reading_place(from).and_then(|place| {
                if backwards {
                    stops
                        .iter()
                        .rev()
                        .find(|(p, _, _)| in_reading_order(p, &place).is_lt())
                } else {
                    stops
                        .iter()
                        .find(|(p, _, _)| in_reading_order(p, &place).is_gt())
                }
                .map(|&(_, _, id)| id)
            }),
        };
        Some(next.unwrap_or(round))
    }

    /// Whether Tab can stop at `id`: it is not playing its exit, and nothing
    /// it is in is hidden or disabled.
    fn takes_tab(&self, id: WidgetId) -> bool {
        !crate::reactive::invalidation::is_detached(id)
            && !self.any_declared_hidden(self.ancestors(id), Prop::get_or_untracked)
            && self
                .nearest_control(id)
                .is_none_or(|control| control.enabled_prop().get_or_untracked(true))
    }

    /// Make `id` a place Tab stops at. See [`Self::next_tab_stop`].
    pub(crate) fn make_tab_stop(&mut self, id: WidgetId) {
        let turn = self.tab_stop_turn;
        if let std::collections::hash_map::Entry::Vacant(stop) = self.tab_stops.entry(id) {
            stop.insert(turn);
            self.tab_stop_turn += 1;
        }
    }

    /// Whether a container `id` sits inside has declared itself hidden.
    ///
    /// Reads tracked: `process_jobs` asks it under the widget's Animation job,
    /// so a flip of any of those back to visible queues the job again (#666).
    pub(crate) fn inside_a_hidden_container(&self, id: WidgetId) -> bool {
        self.any_declared_hidden(self.ancestors(id).skip(1), Prop::get_or)
    }

    /// Whether any of `ids` is a container that declared itself hidden, each
    /// `visible` read with `read`. The one rule Tab and animations both ask.
    fn any_declared_hidden(
        &self,
        mut ids: impl Iterator<Item = WidgetId>,
        read: fn(&Prop<bool>, bool) -> bool,
    ) -> bool {
        ids.any(|id| {
            self.declared_visible
                .get(&id)
                .is_some_and(|visible| !read(visible, true))
        })
    }

    /// Record the `visible` a container declared, for Tab and animations to
    /// read.
    pub(crate) fn declare_visible(&mut self, id: WidgetId, visible: Prop<bool>) {
        self.declared_visible.insert(id, visible);
    }

    /// Whether the key being routed already went through `id` on the focus
    /// path, so a listener there is not asked a second time on the way down
    /// to another.
    pub(crate) fn heard_this_key(&self, id: WidgetId) -> bool {
        self.key_heard_by
            .as_ref()
            .is_some_and(|path| path.contains(id))
    }

    /// Hand `event` to `root`, to travel the key route set beside it.
    fn route_through(
        &mut self,
        root: WidgetId,
        event: &crate::widgets::Event,
    ) -> Option<crate::widgets::EventResponse> {
        self.with_widget_mut(root, |widget, id, tree| widget.event(tree, id, event))
    }

    /// `id`, then its parent, and so on up to its surface root.
    pub(crate) fn ancestors(&self, id: WidgetId) -> impl Iterator<Item = WidgetId> + '_ {
        std::iter::successors(Some(id), |&id| self.get_parent(id))
    }

    /// Whether the last pointer event was offered to what is under its point.
    /// A press or release inside a chord goes along the press route alone, so
    /// it has nothing to say about the cursor there.
    pub(crate) fn asked_under_the_point(&self) -> bool {
        !self.pointer.chorded
    }

    /// Hear the keys nobody on the focus path takes. See [`Self::dispatch`].
    pub(crate) fn listen_for_keys(&mut self, id: WidgetId) {
        if !self.key_listeners.contains(&id) {
            self.key_listeners.push(id);
        }
    }

    /// Which of `parent`'s children `event` is offered to, the one drawn on
    /// top first.
    ///
    /// A key or a focus change goes to the children on the key route — see
    /// `dispatch_key` — and a paste, handed straight to one widget, is never
    /// routed through a container at all. A pointer event
    /// goes to the children that can be under `at` — those ordered along
    /// `sorted` narrowed to the window paint uses, those in no order tested
    /// against their reach — and to those the pointer record owes one. With no
    /// point to narrow to — the event has none, or the container clipped it
    /// away and passes `None` — only the owed are told: a widget the pointer
    /// was over learns it left, a press that it was given up or that its drag
    /// went on outside, and nothing else can be under a point that is nowhere.
    ///
    /// What the event offered by position is owed the next one. The children
    /// it was owed are not: having had it, they are owed nothing more unless
    /// the press holds them.
    pub(crate) fn event_targets(
        &mut self,
        parent: WidgetId,
        children: &[WidgetId],
        event: &crate::widgets::Event,
        at: Option<crate::widgets::Point>,
        sorted: Option<crate::layout::Axis>,
    ) -> PointerTargets {
        if event.follows_the_focus() {
            // The route's ids under this container — usually one — and where
            // each stands among its children.
            let mut indices: SmallVec<[usize; 4]> = self
                .key_route
                .iter()
                .filter(|&&id| self.get_parent(id) == Some(parent))
                .filter_map(|id| children.iter().position(|child| child == id))
                .collect();
            indices.sort_unstable();
            return PointerTargets::only(indices);
        }
        // A paste is handed straight to the widget that asked for it
        // (`clipboard.rs`), which holds no children to pass it to: what is
        // returned here is never used to route one.
        if let crate::widgets::Event::Pasted(_) = event {
            return PointerTargets::every(children.len());
        }
        let withholding = self.pointer.withholding;
        let chorded = self.pointer.chorded;
        let at = at.filter(|_| !withholding && !chorded);
        let reach = self.children_reach(parent);
        let mut owed: SmallVec<[usize; 4]> = SmallVec::new();
        let mut blind: SmallVec<[usize; 4]> = SmallVec::new();
        let window = match (at, sorted) {
            (Some(at), Some(axis)) => {
                let along = at.along(axis);
                let window = self.window_of(children, axis, (along, along), reach);
                crate::render_stats::record_event_window(
                    children.len() as u64,
                    window.len() as u64,
                );
                window
            }
            (Some(at), None) => {
                owed.extend((0..children.len()).filter(|&index| {
                    self.get_bounds(children[index])
                        .is_some_and(|b| b.outset(reach).contains(at.x, at.y))
                }));
                0..0
            }
            (None, _) => 0..0,
        };
        let record = &mut self.pointer;
        record.reached.push(parent);
        let root = record.root.unwrap_or(parent);
        record.offering.extend(
            window
                .clone()
                .chain(owed.iter().copied())
                .map(|index| Offered {
                    root,
                    parent,
                    index: index as u32,
                    child: children[index],
                }),
        );

        let key = parent.as_u64();
        for (held, list) in [(false, &mut record.last), (true, &mut record.pressed)] {
            if chorded && !held {
                continue;
            }
            let start = list.partition_point(|entry| by_parent(entry) < key);
            let end = start + list[start..].partition_point(|entry| by_parent(entry) == key);
            for entry in &mut list[start..end] {
                // A reconcile can have moved the child since it was offered;
                // the id is what is owed, and the index only the quick way to
                // it. The index is put right once, so a drag over a list that
                // changed looks again once rather than on every move.
                let index = match children.get(entry.index as usize) {
                    Some(&child) if child == entry.child => Some(entry.index as usize),
                    _ => children.iter().position(|&child| child == entry.child),
                };
                match index {
                    Some(index) => {
                        entry.index = index as u32;
                        if !window.contains(&index) {
                            owed.push(index);
                        }
                        if withholding && !held {
                            blind.push(index);
                        }
                    }
                    // Gone from the container: nothing is owed to it here.
                    None => entry.index = u32::MAX,
                }
            }
        }
        record.pressed.retain(|entry| entry.index != u32::MAX);
        owed.sort_unstable();
        owed.dedup();
        // A child the press holds keeps the position even where the last
        // event's offer would have made it blind.
        if withholding {
            let pressed = &record.pressed;
            let start = pressed.partition_point(|entry| by_parent(entry) < key);
            let held = &pressed[start..];
            blind.retain(|index| {
                !held
                    .iter()
                    .take_while(|entry| entry.parent == parent)
                    .any(|entry| entry.index as usize == *index)
            });
        }
        PointerTargets {
            window,
            owed,
            blind,
        }
    }

    /// Whether the pointer record owes the event being dispatched to one of
    /// `parent`'s children below `top`: what a sibling drawn over them has to
    /// tell them. Read after [`Self::event_targets`] has put the record's
    /// indices right for `parent`.
    pub(crate) fn owes_a_child_below(&self, parent: WidgetId, top: usize) -> bool {
        let key = parent.as_u64();
        [&self.pointer.last, &self.pointer.pressed]
            .into_iter()
            .any(|list| {
                let start = list.partition_point(|entry| by_parent(entry) < key);
                list[start..]
                    .iter()
                    .take_while(|entry| entry.parent == parent)
                    .any(|entry| (entry.index as usize) < top)
            })
    }

    /// Offer what follows as a point a container above clipped away, until
    /// the returned value is handed back to [`Self::end_withholding`].
    pub(crate) fn begin_withholding(&mut self) -> bool {
        std::mem::replace(&mut self.pointer.withholding, true)
    }

    /// Put back what [`Self::begin_withholding`] returned.
    pub(crate) fn end_withholding(&mut self, was: bool) {
        self.pointer.withholding = was;
    }

    /// The widest reach among this widget's children.
    pub(crate) fn children_reach(&self, id: WidgetId) -> f32 {
        self.get_dense_index(id)
            .map_or(0.0, |idx| self.dense[idx].children_reach)
    }

    /// How far this widget's paint reaches beyond its bounds — a shadow's
    /// falloff, or the distance its own transform can move what it draws.
    ///
    /// Read by damage, so a repaint covers the shadow it moved, and by the two
    /// narrowings in `paint_children`, so neither drops a widget that draws
    /// somewhere other than where it was laid out.
    pub(crate) fn paint_overflow(&self, id: WidgetId) -> f32 {
        self.get_dense_index(id).map_or(0.0, |idx| {
            self.paint_overflow_from(self.dense[idx].own_paint_reach, idx)
        })
    }

    /// The same, for a reach the caller names — which is how a write asks what
    /// its own answer is about to become while the old one is still standing.
    fn paint_overflow_from(&self, reach: f32, idx: usize) -> f32 {
        reach.max(self.dense[idx].children_outset)
    }

    /// Get the children of a widget (returns a slice to avoid heap allocation).
    pub fn get_children(&self, id: WidgetId) -> &[WidgetId] {
        self.get_dense_index(id)
            .map(|idx| self.dense[idx].children.as_slice())
            .unwrap_or(&[])
    }

    /// Collect a subtree in post-order (children before parents).
    ///
    /// Used for surface teardown: unregistering in this order means each
    /// widget's Drop finds its children already gone, so the deferred
    /// Unregister jobs it schedules become no-ops.
    pub fn collect_subtree_post_order(&self, root: WidgetId) -> Vec<WidgetId> {
        let mut ordered = Vec::new();
        // Pre-order DFS, then reverse: yields children before parents
        let mut stack = vec![root];
        while let Some(id) = stack.pop() {
            if self.get_dense_index(id).is_none() {
                continue;
            }
            ordered.push(id);
            stack.extend_from_slice(self.get_children(id));
        }
        ordered.reverse();
        ordered
    }

    /// Mark a widget as needing layout, returning the layout root.
    ///
    /// The needs_layout flag bubbles up to the nearest relayout boundary
    /// *above* the widget, or the root. Returns `Some(root_id)` if a layout
    /// root was found and should be queued, `None` if an ancestor already
    /// needed layout (its boundary is already queued).
    ///
    /// The widget itself is never the boundary its own walk stops at: a
    /// boundary's size does not depend on its children, but it does depend on
    /// its own properties, and placing it is its parent's job (#670). Blink's
    /// `MarkContainerChainForLayout` starts at the container too. Nor does the
    /// widget being marked already stop the walk: a descendant's walk marks a
    /// boundary without telling its parent.
    ///
    /// Stopping at a marked ancestor requires all widgets to call
    /// `clear_needs_layout` after completing layout.
    pub fn mark_needs_layout(&mut self, widget_id: WidgetId) -> Option<WidgetId> {
        let mut idx = self.get_dense_index(widget_id)?;
        self.dense[idx].needs_layout = true;

        let mut current = widget_id;
        while let Some(parent) = self.dense[idx].parent {
            idx = self.get_dense_index(parent)?;
            if self.dense[idx].needs_layout {
                return None;
            }
            self.dense[idx].needs_layout = true;
            if self.dense[idx].is_relayout_boundary {
                return Some(parent);
            }
            current = parent;
        }
        Some(current)
    }

    /// Clear the needs-layout flag for a widget.
    pub fn clear_needs_layout(&mut self, id: WidgetId) {
        if let Some(idx) = self.get_dense_index(id) {
            self.dense[idx].needs_layout = false;
        }
    }

    /// Check if a widget needs layout.
    pub fn needs_layout(&self, id: WidgetId) -> bool {
        self.get_dense_index(id)
            .map(|idx| self.dense[idx].needs_layout)
            .unwrap_or(false)
    }

    /// Mark a widget as needing paint, propagating up to the root.
    ///
    /// Similar to `mark_needs_layout`, this bubbles the paint-dirty flag
    /// upward so that ancestors know to repaint. The walk up stops at the
    /// first *ancestor* already marked, because that one was told by a walk
    /// that went all the way — but never on the widget's own flag, which a
    /// frame that culled it leaves set forever (#319).
    ///
    /// Also accumulates the widget's surface-relative bounds into the
    /// damage region for Wayland damage reporting.
    pub fn mark_needs_paint(&mut self, widget_id: WidgetId) {
        // The damage walk comes before the flag early-out below, and the order
        // is load-bearing. `cache_layout` damages the rect a widget vacated and
        // then delegates the *new* one here — so an early-out on an
        // already-set flag would drop the new rect whenever a resize follows a
        // paint mark, which is most resizes. Moving the early-out first looks
        // like a free saving and is not.

        // Accumulate damage for the actual dirty widget (before propagation),
        // attributed to the widget's surface root
        let surface_root = self.surface_relative_damage_and_root(widget_id);
        if let Some((root, bounds)) = surface_root {
            self.expand_damage_rect(root, bounds);
        }

        let Some(idx) = self.get_dense_index(widget_id) else {
            return;
        };
        self.dense[idx].needs_paint = true;

        // From the *parent*, never from the widget itself. A widget the frame
        // culled is left marked — nothing clears a flag for a widget that
        // never painted — so its own flag says nothing about whether its
        // ancestors know. Stopping on it is what kept a culled widget from
        // ever causing a frame again (#319).
        let mut current = self.dense[idx].parent;
        while let Some(id) = current {
            let Some(dense_idx) = self.get_dense_index(id) else {
                break;
            };
            // An ancestor that already says so needs no telling, and neither
            // does anything above it — `break`, not `return`, because the
            // root still does, below.
            if self.dense[dense_idx].needs_paint {
                break;
            }
            self.dense[dense_idx].needs_paint = true;
            current = self.dense[dense_idx].parent;
        }

        // And the surface root, whatever the walk did. The walk stops at the
        // first ancestor that already says so, and a widget the frame skipped
        // says so for ever — so on a subtree the frame has been culling, the
        // announcement can die below the root. The root is what
        // `paint_and_present` gates the frame on, so it has to hear every
        // time; the walk above is what makes the frame *descend* to the right
        // place once it runs.
        //
        // Free: the root is the one the damage above already resolved, and
        // marking a root that is already marked is a flag write.
        if let Some((root, _)) = surface_root
            && let Some(root_idx) = self.get_dense_index(root)
        {
            self.dense[root_idx].needs_paint = true;
        }
    }

    /// Clear the needs-paint flag for a widget.
    pub fn clear_needs_paint(&mut self, id: WidgetId) {
        if let Some(idx) = self.get_dense_index(id) {
            self.dense[idx].needs_paint = false;
        }
    }

    /// Whether this widget or anything below it needs painting.
    ///
    /// What decides whether a frame is worth drawing, and whether a subtree is
    /// worth descending into.
    pub fn needs_paint(&self, id: WidgetId) -> bool {
        self.get_dense_index(id)
            .map(|idx| self.dense[idx].needs_paint)
            .unwrap_or(true) // Default to true for unknown widgets
    }

    /// Mark a widget and all its descendants as needing paint.
    ///
    /// Sets full damage for the widget's surface since the entire subtree
    /// is being repainted.
    pub fn mark_subtree_needs_paint(&mut self, widget_id: WidgetId) {
        if let Some(root) = self.surface_root_of(widget_id) {
            self.damage.insert(root, DamageRegion::Full);
        }
        self.mark_subtree_needs_paint_inner(widget_id);
        // Ancestors must learn a descendant is dirty: the per-surface
        // skip check reads the surface root's flag and paint-cache reuse
        // consults each ancestor. Without this, a reconcile-only update
        // (a closure child whose signals no paint pass ever tracked, e.g.
        // a calendar month grid) relaid out its subtree and then the
        // frame was skipped forever — widgets current, screen stale.
        let mut current = widget_id;
        loop {
            let Some(dense_idx) = self.get_dense_index(current) else {
                return;
            };
            let Some(parent) = self.dense[dense_idx].parent else {
                return;
            };
            let Some(parent_idx) = self.get_dense_index(parent) else {
                return;
            };
            if self.dense[parent_idx].needs_paint {
                return; // Already marked — its ancestors are too
            }
            self.dense[parent_idx].needs_paint = true;
            current = parent;
        }
    }

    fn mark_subtree_needs_paint_inner(&mut self, widget_id: WidgetId) {
        // Iterative DFS to avoid cloning children SmallVecs for borrow checker
        let mut stack = vec![widget_id];
        while let Some(id) = stack.pop() {
            let Some(dense_idx) = self.get_dense_index(id) else {
                continue;
            };
            self.dense[dense_idx].needs_paint = true;
            stack.extend_from_slice(&self.dense[dense_idx].children);
        }
    }

    // -------------------------------------------------------------------------
    // Surface-relative position
    // -------------------------------------------------------------------------

    /// Where a widget is drawn, relative to its surface: the box it was laid
    /// out in, carried by the scroll offset of every container it is in and by
    /// every transform on the way down, its own included. Under a rotation that
    /// is the axis-aligned box around the result, taken once at the end. What
    /// it paints outside that box — a shadow — is not part of it; that is what
    /// damage grows by, from the laid-out box below.
    ///
    /// This is what [`WidgetRef::rect`](crate::widget_ref::WidgetRef::rect)
    /// reports. Each widget on the way up is asked its
    /// [`placement`](crate::widgets::Widget::placement), so it reads what they
    /// paint with; inside a reactive scope, those reads subscribe it.
    ///
    /// Not for a scroller's own scrollbar track and handle: the container
    /// places those itself, clear of its scroll offset, and no ref can be
    /// attached to them.
    pub fn get_surface_relative_bounds(&self, id: WidgetId) -> Option<Rect> {
        let placement_of = |id: WidgetId| self.with_widget(id, |widget| widget.placement(self, id));
        let size = self.cached_size(id)?;
        let mut current = id;
        let mut placement = placement_of(id)?;
        // From the widget's own coordinates to those of the one `current` is
        // laid out in, built up one ancestor at a time.
        let mut placed = Transform::IDENTITY;
        loop {
            let (x, y) = self.get_origin(current)?;
            let parent = self.get_parent(current);
            let above = match parent {
                Some(parent) => Some(placement_of(parent)?),
                None => None,
            };
            let scroll = above.map_or((0.0, 0.0), |above| above.scroll);
            placed = Transform::translate(x - scroll.0, y - scroll.1)
                .then(&placement.own)
                .then(&placed);
            match (parent, above) {
                (Some(parent), Some(above)) => (current, placement) = (parent, above),
                _ => break,
            }
        }
        Some(placed.map_rect(Rect::new(0.0, 0.0, size.width, size.height)))
    }

    /// Walk to the surface root, returning it together with the widget's
    /// laid-out box relative to the surface: origins summed along the chain,
    /// with no scroll and no transform. What damage is measured from.
    fn surface_relative_layout_and_root(&self, id: WidgetId) -> Option<(WidgetId, Rect)> {
        let idx = self.get_dense_index(id)?;
        let size = self.dense[idx].cached_size?;
        let mut x = 0.0f32;
        let mut y = 0.0f32;
        let mut current = id;
        loop {
            let dense_idx = self.get_dense_index(current)?;
            x += self.dense[dense_idx].origin.0;
            y += self.dense[dense_idx].origin.1;
            match self.dense[dense_idx].parent {
                Some(parent) => current = parent,
                None => break,
            }
        }
        Some((current, Rect::new(x, y, size.width, size.height)))
    }

    // -------------------------------------------------------------------------
    // Damage Region Tracking
    // -------------------------------------------------------------------------

    /// The same, widened by whatever the widget paints outside itself, so a
    /// shadow is re-composited along with the thing that cast it — and so is a
    /// widget its own transform has carried off its laid-out box. What damage
    /// is measured from, and not what the widget's bounds are.
    fn surface_relative_damage_and_root(&self, id: WidgetId) -> Option<(WidgetId, Rect)> {
        let (root, laid_out) = self.surface_relative_layout_and_root(id)?;
        Some((root, laid_out.outset(self.paint_overflow(id))))
    }

    /// Find the surface root (topmost ancestor) of a widget.
    pub(crate) fn surface_root_of(&self, id: WidgetId) -> Option<WidgetId> {
        let mut current = id;
        loop {
            let dense_idx = self.get_dense_index(current)?;
            match self.dense[dense_idx].parent {
                Some(parent) => current = parent,
                None => return Some(current),
            }
        }
    }

    /// Union a rect into the damage region of the given surface root.
    fn expand_damage_rect(&mut self, root: WidgetId, rect: Rect) {
        let entry = self.damage.entry(root).or_insert(DamageRegion::None);
        *entry = match entry {
            DamageRegion::None => DamageRegion::Partial(rect),
            DamageRegion::Partial(existing) => {
                let min_x = existing.x.min(rect.x);
                let min_y = existing.y.min(rect.y);
                let max_x = (existing.x + existing.width).max(rect.x + rect.width);
                let max_y = (existing.y + existing.height).max(rect.y + rect.height);
                DamageRegion::Partial(Rect::new(min_x, min_y, max_x - min_x, max_y - min_y))
            }
            DamageRegion::Full => DamageRegion::Full,
        };
    }

    /// Set full-surface damage for a surface root (e.g., on resize,
    /// initialization, or a failed present that must be retried).
    pub fn set_full_damage(&mut self, root: WidgetId) {
        self.damage.insert(root, DamageRegion::Full);
    }

    /// Take the accumulated damage region for a surface root, resetting it.
    pub fn take_damage(&mut self, root: WidgetId) -> DamageRegion {
        self.damage.remove(&root).unwrap_or(DamageRegion::None)
    }

    /// Set whether a widget is a relayout boundary.
    pub fn set_relayout_boundary(&mut self, id: WidgetId, is_boundary: bool) {
        if let Some(idx) = self.get_dense_index(id) {
            self.dense[idx].is_relayout_boundary = is_boundary;
        }
    }

    /// Check if a widget is a relayout boundary.
    pub fn is_relayout_boundary(&self, id: WidgetId) -> bool {
        self.get_dense_index(id)
            .map(|idx| self.dense[idx].is_relayout_boundary)
            .unwrap_or(false)
    }

    /// Cache the constraints and size for a widget, and invalidate its paint.
    ///
    /// This is only reached by a widget that actually ran its layout — the
    /// ones that hit the early-out (clean, same constraints) return before
    /// getting here — so it is the point where the layout pass tells paint
    /// what it touched. Same rule as Flutter, whose `RenderObject.layout()`
    /// ends in `markNeedsPaint()` for the objects that laid out; everything
    /// the pass skipped keeps its cached paint.
    ///
    /// Running layout is the invalidation signal, not a size change: a
    /// widget's painted output can depend on state it refreshes during
    /// layout (a `Text` re-reads its content there and paints from the
    /// cached copy), so a clock going from `15:23` to `15:24` at the very
    /// same width still has to be redrawn.
    ///
    /// When the size changes, the damage covers both the rectangle the
    /// widget used to occupy and the one it occupies now.
    pub fn cache_layout(&mut self, id: WidgetId, constraints: Constraints, size: Size) {
        self.cache_answer(id, constraints, size, size);
    }

    /// [`cache_layout`](Self::cache_layout), with the minimum the layout
    /// recorded beside the size.
    fn cache_answer(&mut self, id: WidgetId, constraints: Constraints, size: Size, minimum: Size) {
        let Some(idx) = self.get_dense_index(id) else {
            return;
        };
        let previous_size = self.dense[idx].cached_size;
        if previous_size.is_some_and(|prev| prev != size)
            && let Some((root, vacated)) = self.surface_relative_damage_and_root(id)
        {
            self.expand_damage_rect(root, vacated);
        }
        let idx = self.get_dense_index(id).expect("checked above");
        // A subtree answers the passes differently when something in it is in
        // flight, or when a measure placed a value without letting it appear.
        // The reads say so as they happen, and each child folded its own
        // subtree's answer into the same flag on its way out — so this is the
        // whole subtree's, and there is nothing to walk.
        let pass_dependent = self.pass_dependent;
        let pass = self.pass;
        self.dense[idx].cached = Some(CachedLayout {
            pass,
            constraints,
            size,
            minimum,
            pass_dependent,
        });
        self.dense[idx].cached_size = Some(size);
        // Damages the new rect and marks the ancestors, which have to redraw
        // to re-emit this widget at its new geometry.
        self.mark_needs_paint(id);
    }

    /// What this widget was last asked for *by the pass that is running*, and
    /// what it answered.
    ///
    /// Per pass, because the two do not answer the same question: a measure
    /// reads where an animation is going, a layout reads where it is now, and
    /// a measure runs before a surface exists so an appearance must not be
    /// spent in one. One shared entry meant a skip across the passes handed
    /// back the other pass's size, or never placed what a measure declined to.
    fn cached_for_pass(&self, id: WidgetId, constraints: Constraints) -> Option<CachedLayout> {
        // This pass's own answer, or the other pass's — which may be read only
        // where nothing below would have answered differently. Without that, a
        // measure re-lays out a settled tree it could have read off the layout
        // before it; with it, a value in flight, or an enter a measure declined
        // to spend, is never handed across.
        self.dense[self.get_dense_index(id)?]
            .cached
            .filter(|entry| {
                entry.constraints == constraints
                    && (entry.pass == self.pass || !entry.pass_dependent)
            })
    }

    /// The constraints a real layout last ran this widget under, whichever
    /// pass is asking.
    ///
    /// For the loop, which restarts a layout at a boundary and needs the
    /// constraints that boundary was placed under — a question about the tree
    /// on screen rather than about the pass asking.
    pub(crate) fn last_layout_constraints(&self, id: WidgetId) -> Option<Constraints> {
        self.dense[self.get_dense_index(id)?]
            .cached
            .filter(|entry| entry.pass == LayoutPass::Layout)
            .map(|entry| entry.constraints)
    }

    /// The least `id` can be on each axis, as its last layout recorded it:
    /// what a flex whose children do not fit takes it down to and no further.
    /// Never more than the size it was laid out at, and that size itself for
    /// a widget that recorded nothing — nothing shrinks it.
    ///
    /// Recorded with the size, so a layout that is skipped as clean still
    /// answers the minimum it recorded, and a layout that runs replaces it.
    pub fn minimum(&self, id: WidgetId) -> Option<Size> {
        self.dense[self.get_dense_index(id)?]
            .cached
            .map(|entry| entry.minimum)
    }

    pub fn cached_size(&self, id: WidgetId) -> Option<Size> {
        self.get_dense_index(id)
            .and_then(|idx| self.dense[idx].cached_size)
    }

    /// Set the origin (position) for a widget.
    ///
    /// A widget that moves damages the pixels it leaves behind as well as the
    /// ones it now covers. It does not need repainting for that: its painted
    /// content is position-independent and the parent re-emits it at the new
    /// offset (paint-cache reuse re-parents the cached node). The parent is
    /// already marked, since moving a child means it ran its own layout.
    pub fn set_origin(&mut self, id: WidgetId, x: f32, y: f32) {
        let Some(idx) = self.get_dense_index(id) else {
            return;
        };
        if self.dense[idx].origin == (x, y) {
            return;
        }
        if let Some((root, vacated)) = self.surface_relative_damage_and_root(id) {
            self.expand_damage_rect(root, vacated);
        }
        let idx = self.get_dense_index(id).expect("checked above");
        self.dense[idx].origin = (x, y);
        if let Some((root, occupied)) = self.surface_relative_damage_and_root(id) {
            self.expand_damage_rect(root, occupied);
        }
    }

    /// Get the origin (position) for a widget.
    pub fn get_origin(&self, id: WidgetId) -> Option<(f32, f32)> {
        self.get_dense_index(id).map(|idx| self.dense[idx].origin)
    }

    /// Get the bounds (origin + cached size) for a widget.
    pub fn get_bounds(&self, id: WidgetId) -> Option<crate::widgets::Rect> {
        let idx = self.get_dense_index(id)?;
        let node = &self.dense[idx];
        let size = node.cached_size?;
        Some(crate::widgets::Rect::new(
            node.origin.0,
            node.origin.1,
            size.width,
            size.height,
        ))
    }

    /// Cache a widget's paint output. The node is Rc-shared with the frame's
    /// render tree, so this is a refcount bump, not a deep clone.
    pub fn cache_paint(&mut self, id: WidgetId, node: std::rc::Rc<crate::renderer::RenderNode>) {
        if let Some(idx) = self.get_dense_index(id) {
            self.dense[idx].cached_paint = Some(node);
        }
    }

    /// Get a widget's cached paint output.
    pub fn cached_paint(&self, id: WidgetId) -> Option<&std::rc::Rc<crate::renderer::RenderNode>> {
        self.get_dense_index(id)
            .and_then(|idx| self.dense[idx].cached_paint.as_ref())
    }

    /// Drop a widget's cached paint output, so the next frame paints it in
    /// full. What a paint that could not be cached has to do with the entry
    /// the last one left: it is a picture of this widget as it no longer is.
    pub fn clear_cached_paint(&mut self, id: WidgetId) {
        if let Some(idx) = self.get_dense_index(id) {
            self.dense[idx].cached_paint = None;
        }
    }

    /// Clear all widgets and metadata.
    pub fn clear(&mut self) {
        self.dense.clear();
        self.sparse.clear();
        self.free_indices.clear();
        self.damage.clear();
    }

    /// Get the number of registered widgets.
    pub fn widget_count(&self) -> usize {
        self.dense.len()
    }
}

impl Default for Tree {
    fn default() -> Self {
        Self::new()
    }
}

#[cfg(test)]
mod tests {

    use super::*;

    /// Every widget in every tree is a slot, so a field on it is paid by all
    /// of them. It held a second layout-cache entry that was always empty,
    /// and gave it back: what a minimum costs is a size inside the one entry
    /// there is, not a field of its own.
    #[test]
    fn a_slot_is_no_larger_than_its_one_cache_entry_leaves_it() {
        assert!(
            size_of::<Slot>() <= 192,
            "a slot is {} bytes",
            size_of::<Slot>()
        );
    }

    /// A hover that flips and flips back within one event changed nothing, so
    /// its callback hears nothing.
    #[test]
    fn a_hover_taken_back_within_one_event_is_not_heard() {
        let mut tree = Tree::new();
        let id = tree.register(Box::new(MockWidget::new()));
        let heard = std::rc::Rc::new(std::cell::RefCell::new(Vec::new()));
        let sink = heard.clone();
        let callback: crate::widgets::container::HoverCallback =
            std::rc::Rc::new(move |hovered| sink.borrow_mut().push(hovered));

        tree.hover_changed(id, true, &callback);
        tree.hover_changed(id, false, &callback);
        tree.deliver_hover_changes();

        assert!(heard.borrow().is_empty(), "heard {:?}", heard.borrow());
    }

    /// A container leaving the tree stops listening for keys, and the others
    /// go on listening.
    #[test]
    fn a_key_listener_leaving_the_tree_takes_only_itself_off_the_list() {
        let mut tree = Tree::new();
        let leaving = tree.register(Box::new(MockWidget::new()));
        let staying = tree.register(Box::new(MockWidget::new()));
        tree.listen_for_keys(leaving);
        tree.listen_for_keys(staying);

        tree.unregister(leaving);

        assert_eq!(tree.key_listeners, [staying]);
    }

    /// A surface closed while the pointer is on it hears no leave — the
    /// compositor's arrives for a surface that is gone — so its root leaving
    /// the tree is what takes its record with it: a popup closed by a click on
    /// one of its items must not stay in the record for the life of the bar.
    #[test]
    fn a_surface_root_leaving_the_tree_takes_its_pointer_record() {
        let mut tree = Tree::new();
        let closed = tree.register(Box::new(MockWidget::new()));
        let open = tree.register(Box::new(MockWidget::new()));
        let child = tree.register(Box::new(MockWidget::new()));
        for root in [closed, open] {
            let entry = Offered {
                root,
                parent: root,
                index: 0,
                child,
            };
            tree.pointer.last.push(entry);
            tree.pointer.pressed.push(entry);
        }

        tree.unregister(closed);

        let roots = |list: &Vec<Offered>| list.iter().map(|e| e.root).collect::<Vec<_>>();
        assert_eq!(roots(&tree.pointer.last), [open]);
        assert_eq!(roots(&tree.pointer.pressed), [open]);
    }

    /// The record keeps what the root still leads to, and nothing an event
    /// can no longer reach: an entry under a container nothing recorded leads
    /// to is gone, however long it was carried.
    #[test]
    fn the_pointer_record_keeps_only_what_the_root_reaches() {
        let id = |n| WidgetId::from_u64(n);
        let offered = |root: u64, parent: u64, child: u64| Offered {
            root: id(root),
            parent: id(parent),
            index: 0,
            child: id(child),
        };
        // root 1 → 2 → 3 is a path; 7 → 8 was carried under a row that has
        // scrolled away; 20 → 21 is another surface's, and stays.
        let mut record = vec![
            offered(1, 1, 2),
            offered(1, 2, 3),
            offered(1, 7, 8),
            offered(20, 20, 21),
        ];
        record.sort_unstable_by_key(by_parent);

        keep_what_the_root_reaches(&mut record, id(1));

        let kept: Vec<_> = record.iter().map(|e| (e.parent, e.child)).collect();
        assert_eq!(kept, [(id(1), id(2)), (id(2), id(3)), (id(20), id(21))]);
    }

    // Mock widget for testing
    struct MockWidget;

    impl MockWidget {
        fn new() -> Self {
            Self
        }
    }

    impl Widget for MockWidget {
        fn layout(&mut self, _ctx: &mut LayoutCtx, constraints: Constraints) -> Size {
            Size::new(constraints.max_width, constraints.max_height)
        }

        fn paint(&self, _ctx: &mut crate::renderer::PaintContext) {}
    }

    #[test]
    fn test_tree_register_unregister() {
        let mut tree = Tree::new();
        let id = tree.register(Box::new(MockWidget::new()));
        assert!(tree.contains(id));

        tree.unregister(id);
        assert!(!tree.contains(id));
    }

    #[test]
    fn test_tree_generational_index() {
        let mut tree = Tree::new();

        // Register and unregister a widget
        let id1 = tree.register(Box::new(MockWidget::new()));
        tree.unregister(id1);

        // Register a new widget (should reuse the slot)
        let id2 = tree.register(Box::new(MockWidget::new()));

        // id1 should be invalid (different generation)
        assert!(!tree.contains(id1));
        assert!(tree.contains(id2));

        // They should have the same index but different generations
        assert_eq!(id1.index, id2.index);
        assert_ne!(id1.generation, id2.generation);
    }

    /// Regression test: the generation must keep advancing across repeated
    /// recycles of the same slot. The old implementation read the generation
    /// from a sparse entry that `unregister` had already cleared, so every
    /// reuse produced generation 1 and a stale ID from cycle N aliased the
    /// live widget of cycle N+2.
    #[test]
    fn test_tree_generation_advances_across_recycles() {
        let mut tree = Tree::new();

        let mut previous_ids = Vec::new();
        let mut current = tree.register(Box::new(MockWidget::new()));

        for _ in 0..5 {
            tree.unregister(current);
            let next = tree.register(Box::new(MockWidget::new()));
            assert_eq!(next.index, current.index, "slot should be recycled");
            previous_ids.push(current);
            current = next;

            // No previously issued ID may resolve to the new widget
            for stale in &previous_ids {
                assert!(
                    !tree.contains(*stale),
                    "stale id {stale:?} aliases live widget {current:?}"
                );
            }
            assert!(tree.contains(current));
        }
    }

    #[test]
    fn test_tree_parent_child() {
        let mut tree = Tree::new();
        let parent_id = tree.register(Box::new(MockWidget::new()));
        let child_id = tree.register(Box::new(MockWidget::new()));

        tree.set_parent(child_id, parent_id);

        assert_eq!(tree.get_parent(child_id), Some(parent_id));
        assert_eq!(tree.get_children(parent_id), &[child_id]);
    }

    #[test]
    fn test_tree_needs_layout_propagation() {
        let mut tree = Tree::new();
        let root_id = tree.register(Box::new(MockWidget::new()));
        let child_id = tree.register(Box::new(MockWidget::new()));
        let grandchild_id = tree.register(Box::new(MockWidget::new()));

        // Build tree: root -> child -> grandchild
        tree.set_parent(child_id, root_id);
        tree.set_parent(grandchild_id, child_id);

        // Mark grandchild needs_layout - should bubble to root and return root
        let layout_root = tree.mark_needs_layout(grandchild_id);

        assert!(tree.needs_layout(grandchild_id));
        assert!(tree.needs_layout(child_id));
        assert!(tree.needs_layout(root_id));

        // Root should be returned as the layout root
        assert_eq!(layout_root, Some(root_id));
    }

    #[test]
    fn test_tree_relayout_boundary_stops_propagation() {
        let mut tree = Tree::new();
        let root_id = tree.register(Box::new(MockWidget::new()));
        let boundary_id = tree.register(Box::new(MockWidget::new()));
        let leaf_id = tree.register(Box::new(MockWidget::new()));

        // Build tree: root -> boundary (relayout) -> leaf
        tree.set_parent(boundary_id, root_id);
        tree.set_parent(leaf_id, boundary_id);

        // Mark boundary as relayout boundary
        tree.set_relayout_boundary(boundary_id, true);

        // Mark leaf needs_layout - should stop at boundary and return boundary
        let layout_root = tree.mark_needs_layout(leaf_id);

        assert!(tree.needs_layout(leaf_id));
        assert!(tree.needs_layout(boundary_id));
        assert!(!tree.needs_layout(root_id)); // Root should NOT need layout

        // Boundary should be returned as the layout root, not root
        assert_eq!(layout_root, Some(boundary_id));
    }

    /// A boundary absorbs what changes below it, not what changes in itself:
    /// its own size is its parent's to place, so its own mark walks on to the
    /// parent's boundary (#670). Blink's `MarkContainerChainForLayout` starts
    /// at the container for the same reason.
    #[test]
    fn test_tree_relayout_boundary_own_mark_reaches_the_parent() {
        let mut tree = Tree::new();
        let root_id = tree.register(Box::new(MockWidget::new()));
        let outer_id = tree.register(Box::new(MockWidget::new()));
        let inner_id = tree.register(Box::new(MockWidget::new()));
        let leaf_id = tree.register(Box::new(MockWidget::new()));

        // root -> outer (boundary) -> inner (boundary) -> leaf
        tree.set_parent(outer_id, root_id);
        tree.set_parent(inner_id, outer_id);
        tree.set_parent(leaf_id, inner_id);
        tree.set_relayout_boundary(outer_id, true);
        tree.set_relayout_boundary(inner_id, true);

        assert_eq!(tree.mark_needs_layout(inner_id), Some(outer_id));
        assert!(tree.needs_layout(inner_id) && tree.needs_layout(outer_id));
        assert!(!tree.needs_layout(root_id));

        for id in [outer_id, inner_id] {
            tree.clear_needs_layout(id);
        }

        // A descendant's mark still stops at the nearest boundary...
        assert_eq!(tree.mark_needs_layout(leaf_id), Some(inner_id));
        assert!(!tree.needs_layout(outer_id));

        // ...and the boundary it stopped at, already marked by that walk, still
        // tells its parent when it changes itself.
        assert_eq!(tree.mark_needs_layout(inner_id), Some(outer_id));
        assert!(tree.needs_layout(outer_id));
    }

    #[test]
    fn test_tree_needs_layout_optimization() {
        let mut tree = Tree::new();
        let root_id = tree.register(Box::new(MockWidget::new()));
        let child_id = tree.register(Box::new(MockWidget::new()));

        tree.set_parent(child_id, root_id);

        // Mark child needs_layout - root should be returned
        let layout_root = tree.mark_needs_layout(child_id);
        assert!(tree.needs_layout(child_id));
        assert!(tree.needs_layout(root_id));
        assert_eq!(layout_root, Some(root_id));

        // Simulate layout running: clear ALL needs_layout flags
        // (this is what widgets should do after layout)
        tree.clear_needs_layout(root_id);
        tree.clear_needs_layout(child_id);

        // Mark child again - should return root again
        let layout_root = tree.mark_needs_layout(child_id);
        assert_eq!(layout_root, Some(root_id));

        // Mark child again before layout runs - should return None, because
        // the walk meets the root already marked, and so already queued
        let layout_root = tree.mark_needs_layout(child_id);
        assert_eq!(layout_root, None);
    }

    #[test]
    fn test_tree_with_widget() {
        let mut tree = Tree::new();
        let id = tree.register(Box::new(MockWidget::new()));

        // Test that we can access widget through with_widget
        let exists = tree.with_widget(id, |_w| true);
        assert!(exists.is_some());
    }

    #[test]
    fn test_tree_swap_remove_fixup() {
        let mut tree = Tree::new();

        // Register three widgets
        let id1 = tree.register(Box::new(MockWidget::new()));
        let id2 = tree.register(Box::new(MockWidget::new()));
        let id3 = tree.register(Box::new(MockWidget::new()));

        // Remove the first one - id3 should be moved to its position
        tree.unregister(id1);

        // id1 should be invalid
        assert!(!tree.contains(id1));

        // id2 and id3 should still be valid
        assert!(tree.contains(id2));
        assert!(tree.contains(id3));

        // We should still be able to access them
        assert!(tree.with_widget(id2, |_| ()).is_some());
        assert!(tree.with_widget(id3, |_| ()).is_some());
    }

    #[test]
    fn test_widget_id_from_u64_roundtrip() {
        let id = WidgetId::new(42, 7);
        let val = id.as_u64();
        let id2 = WidgetId::from_u64(val);
        assert_eq!(id, id2);
    }

    #[test]
    fn test_new_widget_needs_paint() {
        let mut tree = Tree::new();
        let id = tree.register(Box::new(MockWidget::new()));
        assert!(tree.needs_paint(id));
    }

    /// A widget the frame skipped keeps its own request, and that must not
    /// stop the next mark reaching the root.
    ///
    /// The shape culling leaves behind, and the reason the two flags are two:
    /// a parent paints and clears itself while the child it never painted
    /// keeps a request nothing will clear. With one flag for both meanings the
    /// walk stopped at that child and no ancestor ever learned again — a
    /// widget culled from its first frame could not bring itself back (#319).
    #[test]
    fn a_skipped_widget_does_not_swallow_the_next_mark() {
        let mut tree = Tree::new();
        let root_id = tree.register(Box::new(MockWidget::new()));
        let culled = tree.register(Box::new(MockWidget::new()));
        tree.set_parent(culled, root_id);

        // The frame paints the parent and skips the child, which is what a
        // cull is: the parent is settled, the child still wants painting.
        tree.clear_needs_paint(root_id);
        assert!(
            tree.needs_paint(culled),
            "the skipped child still wants painting"
        );
        assert!(!tree.needs_paint(root_id), "and its parent is settled");

        tree.mark_needs_paint(culled);

        assert!(
            tree.needs_paint(root_id),
            "the mark stopped at the child, so no frame will ever be drawn for \
             it: this is #319"
        );
    }

    #[test]
    fn test_needs_paint_propagation() {
        let mut tree = Tree::new();
        let root_id = tree.register(Box::new(MockWidget::new()));
        let child_id = tree.register(Box::new(MockWidget::new()));
        let grandchild_id = tree.register(Box::new(MockWidget::new()));

        tree.set_parent(child_id, root_id);
        tree.set_parent(grandchild_id, child_id);

        // Clear all paint flags
        tree.clear_needs_paint(root_id);
        tree.clear_needs_paint(child_id);
        tree.clear_needs_paint(grandchild_id);

        assert!(!tree.needs_paint(root_id));
        assert!(!tree.needs_paint(child_id));
        assert!(!tree.needs_paint(grandchild_id));

        // Mark grandchild - should propagate to root
        tree.mark_needs_paint(grandchild_id);
        assert!(tree.needs_paint(grandchild_id));
        assert!(tree.needs_paint(child_id));
        assert!(tree.needs_paint(root_id));
    }

    #[test]
    fn test_needs_paint_early_exit() {
        let mut tree = Tree::new();
        let root_id = tree.register(Box::new(MockWidget::new()));
        let child_id = tree.register(Box::new(MockWidget::new()));

        tree.set_parent(child_id, root_id);

        // Clear all
        tree.clear_needs_paint(root_id);
        tree.clear_needs_paint(child_id);

        // Mark child → root marked
        tree.mark_needs_paint(child_id);
        assert!(tree.needs_paint(root_id));

        // Clear child but leave root marked
        tree.clear_needs_paint(child_id);

        // Mark child again — should early-exit at root (already marked)
        tree.mark_needs_paint(child_id);
        assert!(tree.needs_paint(child_id));
        assert!(tree.needs_paint(root_id));
    }

    #[test]
    fn test_mark_subtree_needs_paint() {
        let mut tree = Tree::new();
        let root_id = tree.register(Box::new(MockWidget::new()));
        let child1_id = tree.register(Box::new(MockWidget::new()));
        let child2_id = tree.register(Box::new(MockWidget::new()));
        let grandchild_id = tree.register(Box::new(MockWidget::new()));

        tree.set_parent(child1_id, root_id);
        tree.set_parent(child2_id, root_id);
        tree.set_parent(grandchild_id, child1_id);

        // Clear all
        tree.clear_needs_paint(root_id);
        tree.clear_needs_paint(child1_id);
        tree.clear_needs_paint(child2_id);
        tree.clear_needs_paint(grandchild_id);

        // Mark subtree at root — all should be marked
        tree.mark_subtree_needs_paint(root_id);
        assert!(tree.needs_paint(root_id));
        assert!(tree.needs_paint(child1_id));
        assert!(tree.needs_paint(child2_id));
        assert!(tree.needs_paint(grandchild_id));
    }

    /// Regression test: marking a subtree must also inform the ANCESTORS —
    /// the per-surface skip check reads the surface root's flag, so a
    /// reconcile-only update (partial layout root deep in the tree, no
    /// paint-tracked signals anywhere on the path) would otherwise relayout
    /// its subtree and then never produce a frame: widgets current, screen
    /// permanently stale.
    #[test]
    fn test_mark_subtree_needs_paint_propagates_to_ancestors() {
        let mut tree = Tree::new();
        let root_id = tree.register(Box::new(MockWidget::new()));
        let child_id = tree.register(Box::new(MockWidget::new()));
        let grandchild_id = tree.register(Box::new(MockWidget::new()));
        let leaf_id = tree.register(Box::new(MockWidget::new()));

        tree.set_parent(child_id, root_id);
        tree.set_parent(grandchild_id, child_id);
        tree.set_parent(leaf_id, grandchild_id);

        tree.clear_needs_paint(root_id);
        tree.clear_needs_paint(child_id);
        tree.clear_needs_paint(grandchild_id);
        tree.clear_needs_paint(leaf_id);

        // Mark a subtree deep in the tree: the surface root must see it
        tree.mark_subtree_needs_paint(grandchild_id);
        assert!(tree.needs_paint(grandchild_id));
        assert!(tree.needs_paint(leaf_id));
        assert!(
            tree.needs_paint(child_id),
            "parent of the marked subtree must be marked"
        );
        assert!(
            tree.needs_paint(root_id),
            "surface root must see the dirty descendant or the frame is skipped"
        );
    }

    /// The damage rect a surface root is holding, which every question about
    /// damage below is asked of.
    fn partial_damage(tree: &mut Tree, root: WidgetId) -> Rect {
        match tree.take_damage(root) {
            DamageRegion::Partial(rect) => rect,
            other => panic!("expected partial damage, got {other:?}"),
        }
    }

    /// Build `root -> [a, b]`, both laid out and clean.
    fn two_children_tree() -> (Tree, WidgetId, WidgetId, WidgetId) {
        let mut tree = Tree::new();
        let root = tree.register(Box::new(MockWidget::new()));
        let a = tree.register(Box::new(MockWidget::new()));
        let b = tree.register(Box::new(MockWidget::new()));
        tree.set_parent(a, root);
        tree.set_parent(b, root);

        let c = Constraints::new(0.0, 0.0, 100.0, 100.0);
        tree.cache_layout(root, c, Size::new(100.0, 100.0));
        tree.cache_layout(a, c, Size::new(40.0, 20.0));
        tree.set_origin(a, 0.0, 0.0);
        tree.cache_layout(b, c, Size::new(40.0, 20.0));
        tree.set_origin(b, 0.0, 20.0);
        for id in [root, a, b] {
            tree.clear_needs_paint(id);
        }
        let _ = tree.take_damage(root);
        (tree, root, a, b)
    }

    /// The point of incremental invalidation: re-laying out one subtree must
    /// leave its siblings' paint caches alone. Marking the layout root's whole
    /// subtree instead (the old behaviour) repainted every widget under it,
    /// which in a content-sized tree is the entire surface.
    #[test]
    fn relayout_of_one_child_leaves_its_sibling_paintable_from_cache() {
        let (mut tree, root, a, b) = two_children_tree();

        // `a` re-runs its layout; `b` is untouched
        tree.cache_layout(
            a,
            Constraints::new(0.0, 0.0, 100.0, 100.0),
            Size::new(60.0, 20.0),
        );

        assert!(tree.needs_paint(a), "the widget that laid out repaints");
        assert!(
            tree.needs_paint(root),
            "its ancestors repaint to re-emit it at the new geometry"
        );
        assert!(
            !tree.needs_paint(b),
            "an untouched sibling must keep its cached paint"
        );
    }

    /// A widget can run layout and come out the same size while painting
    /// something else — a clock going from `15:23` to `15:24` refreshes its
    /// glyphs during layout. Running layout is the invalidation signal.
    #[test]
    fn running_layout_repaints_even_when_the_size_is_unchanged() {
        let (mut tree, _root, a, _b) = two_children_tree();
        let same = tree.cached_size(a).unwrap();

        tree.cache_layout(a, Constraints::new(0.0, 0.0, 100.0, 100.0), same);

        assert!(tree.needs_paint(a));
    }

    /// Shrinking must damage the rectangle the widget stops covering, or the
    /// compositor keeps showing the pixels it left behind.
    #[test]
    fn shrinking_damages_the_vacated_rectangle() {
        let (mut tree, root, a, _b) = two_children_tree();

        tree.cache_layout(
            a,
            Constraints::new(0.0, 0.0, 100.0, 100.0),
            Size::new(10.0, 20.0),
        );

        let rect = partial_damage(&mut tree, root);
        assert!(
            rect.width >= 40.0,
            "damage must cover the old 40px-wide box, got {rect:?}"
        );
    }

    /// Moving a widget damages both where it was and where it lands. Its own
    /// paint stays valid — the parent re-emits it at the new offset.
    #[test]
    fn moving_a_widget_damages_both_positions() {
        let (mut tree, root, a, _b) = two_children_tree();

        tree.set_origin(a, 0.0, 60.0);

        let rect = partial_damage(&mut tree, root);
        assert!(
            rect.y <= 0.0,
            "damage must reach the old position, got {rect:?}"
        );
        assert!(
            rect.y + rect.height >= 80.0,
            "damage must reach the new position, got {rect:?}"
        );
        assert!(
            !tree.needs_paint(a),
            "a widget that only moved keeps its cached paint"
        );
    }

    /// Whatever a widget paints outside its own bounds — a box shadow, a glyph
    /// shadow — has to be inside the damage it reports, or repainting
    /// it re-composites a rect that stops short and the old one stays on
    /// screen as a fringe.
    #[test]
    fn damage_covers_what_a_widget_paints_outside_its_bounds() {
        let (mut tree, root, a, _b) = two_children_tree();
        tree.set_own_paint_reach(a, 8.0);

        tree.mark_needs_paint(a);

        let rect = partial_damage(&mut tree, root);
        assert!(
            rect.x <= -8.0 && rect.y <= -8.0,
            "damage must reach above and left of the widget, got {rect:?}"
        );
        assert!(
            rect.width >= 40.0 + 16.0 && rect.height >= 20.0 + 16.0,
            "and past its far edges, got {rect:?}"
        );
    }

    /// The widest child shrinking is the case the prune must not skip.
    ///
    /// The guard asks whether this child *was* the maximum and skips the
    /// re-measure when it was not. Equality is the boundary and it belongs on
    /// the re-measuring side: a child exactly as wide as the maximum is the one
    /// holding it up, and nothing else knows what it falls to.
    ///
    /// The two children are chosen so the guard's halves disagree — one stands
    /// furthest outside the box, the other reaches furthest — because when both
    /// halves sit on their boundary together the second rescues the first and a
    /// wrong comparison in either is invisible.
    #[test]
    fn the_widest_child_shrinking_is_not_pruned_away() {
        let mut tree = Tree::new();
        let root = tree.register(Box::new(MockWidget::new()));
        // At the corner, so what it reaches lands outside the box.
        let overhanging = tree.register(Box::new(MockWidget::new()));
        // In the middle, so it reaches further and stands outside less.
        let far_reaching = tree.register(Box::new(MockWidget::new()));
        tree.set_parent(overhanging, root);
        tree.set_parent(far_reaching, root);

        let cons = Constraints::new(0.0, 0.0, 100.0, 100.0);
        tree.cache_layout(root, cons, Size::new(100.0, 100.0));
        tree.cache_layout(overhanging, cons, Size::new(20.0, 20.0));
        tree.cache_layout(far_reaching, cons, Size::new(20.0, 20.0));
        tree.set_origin(overhanging, 0.0, 0.0);
        tree.set_origin(far_reaching, 40.0, 40.0);

        tree.set_own_paint_reach(overhanging, 30.0);
        tree.set_own_paint_reach(far_reaching, 40.0);
        assert_eq!(
            tree.children_reach(root),
            40.0,
            "the far-reaching one leads"
        );
        assert_eq!(tree.children_outset(root), 30.0, "the overhanging one does");

        tree.set_own_paint_reach(far_reaching, 5.0);
        assert_eq!(
            tree.children_reach(root),
            30.0,
            "the parent kept the width of a child that has let go of it"
        );
    }

    /// And a child that was never the widest costs nothing to shrink.
    ///
    /// This is the prune earning its place: the return leg of a spring shrinks
    /// on every frame, so a fold over the siblings here would be an O(children)
    /// walk per frame and a staggered list of them O(n squared).
    #[test]
    fn a_child_that_was_not_the_widest_leaves_the_parent_alone() {
        let mut tree = Tree::new();
        let root = tree.register(Box::new(MockWidget::new()));
        let wide = tree.register(Box::new(MockWidget::new()));
        let small = tree.register(Box::new(MockWidget::new()));
        tree.set_parent(wide, root);
        tree.set_parent(small, root);

        let cons = Constraints::new(0.0, 0.0, 100.0, 100.0);
        tree.cache_layout(root, cons, Size::new(100.0, 100.0));
        tree.cache_layout(wide, cons, Size::new(20.0, 20.0));
        tree.cache_layout(small, cons, Size::new(20.0, 20.0));
        tree.set_origin(wide, 40.0, 40.0);
        tree.set_origin(small, 40.0, 40.0);

        tree.set_own_paint_reach(wide, 50.0);
        tree.set_own_paint_reach(small, 10.0);
        assert_eq!(tree.children_reach(root), 50.0);

        tree.set_own_paint_reach(small, 1.0);
        assert_eq!(
            tree.children_reach(root),
            50.0,
            "the widest child still reaches 50, so the parent must not have moved"
        );
    }

    /// But a child that leads on the *other* axis is not "not the widest".
    ///
    /// The guard has two halves because a parent keeps two maxima, and a child
    /// can hold up either. One that reaches less far than its sibling can still
    /// be the one standing furthest outside the box — it only has to sit nearer
    /// the edge — and pruning it on the reach alone leaves the outset stale.
    #[test]
    fn a_child_that_leads_on_outset_alone_is_not_pruned_away() {
        let mut tree = Tree::new();
        let root = tree.register(Box::new(MockWidget::new()));
        let at_the_edge = tree.register(Box::new(MockWidget::new()));
        let in_the_middle = tree.register(Box::new(MockWidget::new()));
        tree.set_parent(at_the_edge, root);
        tree.set_parent(in_the_middle, root);

        let cons = Constraints::new(0.0, 0.0, 100.0, 100.0);
        tree.cache_layout(root, cons, Size::new(100.0, 100.0));
        tree.cache_layout(at_the_edge, cons, Size::new(20.0, 20.0));
        tree.cache_layout(in_the_middle, cons, Size::new(20.0, 20.0));
        tree.set_origin(at_the_edge, 0.0, 0.0);
        tree.set_origin(in_the_middle, 40.0, 40.0);

        tree.set_own_paint_reach(in_the_middle, 40.0);
        tree.set_own_paint_reach(at_the_edge, 30.0);
        assert_eq!(
            tree.children_reach(root),
            40.0,
            "the middle one reaches most"
        );
        assert_eq!(
            tree.children_outset(root),
            30.0,
            "the edge one stands out most"
        );

        // Shrinks the one that was never the widest by reach, but was the only
        // thing holding the outset up.
        tree.set_own_paint_reach(at_the_edge, 1.0);
        // Its remaining 1px of reach, and nothing of the 30 it used to hold.
        assert_eq!(
            tree.children_outset(root),
            1.0,
            "the parent kept an overhang no child has any more"
        );
    }

    /// A re-measure that moves the union tells the ancestors too.
    ///
    /// Layout is bottom-up, so an ancestor inside the same pass measures this
    /// for itself and the gather is redundant — except that a widget with a
    /// fixed size is its own relayout boundary and the pass *starts* there,
    /// with no ancestor to follow. Then this is the only thing that carries it.
    ///
    /// The case is a child growing under a parent that does not: the parent's
    /// own reach never moves, so `set_own_paint_reach` returns early and cannot
    /// be what tells anyone.
    #[test]
    fn a_re_measure_that_moves_the_union_reaches_the_ancestors() {
        let mut tree = Tree::new();
        let outer = tree.register(Box::new(MockWidget::new()));
        let boundary = tree.register(Box::new(MockWidget::new()));
        let child = tree.register(Box::new(MockWidget::new()));
        tree.set_parent(boundary, outer);
        tree.set_parent(child, boundary);

        let cons = Constraints::new(0.0, 0.0, 100.0, 100.0);
        tree.cache_layout(outer, cons, Size::new(100.0, 100.0));
        tree.cache_layout(boundary, cons, Size::new(100.0, 100.0));
        tree.cache_layout(child, cons, Size::new(100.0, 100.0));
        tree.remeasure_children(boundary, tree.cached_size(boundary).unwrap_or_default());
        tree.remeasure_children(outer, tree.cached_size(outer).unwrap_or_default());
        assert_eq!(tree.children_reach(outer), 0.0, "nothing hangs out yet");

        // The child outgrows the box it sits in. Its own reach is still zero,
        // so nothing publishes; only the re-measure knows.
        tree.cache_layout(child, cons, Size::new(100.0, 400.0));
        tree.remeasure_children(boundary, tree.cached_size(boundary).unwrap_or_default());

        assert_eq!(
            tree.children_reach(outer),
            300.0,
            "the boundary took on 300px of overhang and its parent never heard, \
             so the search that narrows it would drop a box that is on screen"
        );
    }

    /// A reach that shrinks lets go all the way up, not one level.
    ///
    /// The shrink path prunes when the child that shrank was not the widest,
    /// and that guard needs the child's own previous `paint_overflow`. Carrying
    /// the parent's widest *child* instead stops the walk wherever the two
    /// differ — which is any node whose children stand further outside it than
    /// they themselves reach, i.e. every scroller over a longer column. The
    /// middle box here is smaller than what it holds, so its outset and its
    /// widest-child are different numbers and the mistake is visible.
    #[test]
    fn a_reach_that_shrinks_releases_every_ancestor() {
        let mut tree = Tree::new();
        let g = tree.register(Box::new(MockWidget::new()));
        let p = tree.register(Box::new(MockWidget::new()));
        let c = tree.register(Box::new(MockWidget::new()));
        tree.set_parent(p, g);
        tree.set_parent(c, p);

        let cons = Constraints::new(0.0, 0.0, 100.0, 100.0);
        tree.cache_layout(g, cons, Size::new(100.0, 100.0));
        tree.cache_layout(p, cons, Size::new(100.0, 100.0));
        tree.cache_layout(c, cons, Size::new(100.0, 500.0));

        tree.set_own_paint_reach(c, 70.0);
        let held = tree.paint_overflow(g);
        assert!(held > 0.0, "nothing to let go of");

        tree.set_own_paint_reach(c, 0.0);
        assert!(
            tree.paint_overflow(g) < held,
            "the grandparent stayed at {held} after its grandchild's reach went \
             to nothing, so the walk stopped one level short"
        );
    }

    /// And by *its own* reach, not by whatever the surface root happens to
    /// report.
    ///
    /// The test above cannot tell the two apart: its widget is a direct child
    /// of the root, so its reach gathers straight into the root's and both
    /// spellings give the same number. A widget sitting well inside its
    /// ancestors — a card with room around it — is where they differ, and where
    /// the shadow is left on screen as a fringe.
    #[test]
    fn damage_is_grown_by_the_widget_s_own_reach_not_the_root_s() {
        let mut tree = Tree::new();
        let root = tree.register(Box::new(MockWidget::new()));
        let card = tree.register(Box::new(MockWidget::new()));
        tree.set_parent(card, root);

        let c = Constraints::new(0.0, 0.0, 200.0, 200.0);
        tree.cache_layout(root, c, Size::new(200.0, 200.0));
        tree.cache_layout(card, c, Size::new(40.0, 20.0));
        tree.set_origin(card, 80.0, 80.0);
        for id in [root, card] {
            tree.clear_needs_paint(id);
        }
        let _ = tree.take_damage(root);

        // Inset far enough that the shadow stays inside the root, so nothing of
        // this reach reaches the root's own numbers.
        tree.set_own_paint_reach(card, 20.0);
        assert_eq!(
            tree.paint_overflow(root),
            0.0,
            "the root should not have taken this on, which is what makes the \
             distinction visible"
        );

        tree.mark_needs_paint(card);
        let rect = partial_damage(&mut tree, root);
        assert!(
            rect.x <= 60.0 && rect.y <= 60.0 && rect.width >= 80.0 && rect.height >= 60.0,
            "the card's shadow is outside the damage rect, so it is left on \
             screen as a fringe: got {rect:?}"
        );
    }

    #[test]
    fn a_widget_with_no_overflow_damages_exactly_its_bounds() {
        let (mut tree, root, a, _b) = two_children_tree();

        tree.mark_needs_paint(a);

        let rect = partial_damage(&mut tree, root);
        assert_eq!((rect.x, rect.y), (0.0, 0.0));
        assert_eq!((rect.width, rect.height), (40.0, 20.0));
    }

    /// A 50x50 child inset in a 200x200 root, with its damage taken and its
    /// paint flags cleared — the shape both questions below are asked of.
    fn inset_child() -> (Tree, WidgetId, WidgetId) {
        let mut tree = Tree::new();
        let root = tree.register(Box::new(MockWidget::new()));
        let child = tree.register(Box::new(MockWidget::new()));
        tree.set_parent(child, root);

        let c = Constraints::new(0.0, 0.0, 200.0, 200.0);
        tree.cache_layout(root, c, Size::new(200.0, 200.0));
        tree.cache_layout(child, c, Size::new(50.0, 50.0));
        tree.set_origin(child, 10.0, 10.0);
        for id in [root, child] {
            tree.clear_needs_paint(id);
        }
        let _ = tree.take_damage(root);
        (tree, root, child)
    }

    /// A reach that shrinks without moving the union vacates nothing, and so
    /// damages nothing.
    ///
    /// The guard is `after < before`, and equality is the boundary it turns on.
    /// A widget whose children already reach further than it does can drop its
    /// own reach to nothing without a pixel changing hands — `paint_overflow`
    /// answers the children's number before and after — so a rect damaged here
    /// would be a rect re-composited for no reason, on every frame of the
    /// return leg of every spring under a wider sibling.
    ///
    /// Reading `<=` instead is what this refuses. Nothing else does: the two
    /// spellings agree everywhere except exactly here.
    #[test]
    fn a_reach_that_shrinks_under_its_children_damages_nothing() {
        let (mut tree, root, child) = inset_child();

        // The child reaches 90 past the root's own box, so the root's union is
        // the child's from here on.
        tree.set_own_paint_reach(child, 100.0);
        assert_eq!(tree.children_outset(root), 90.0, "the setup, not the claim");
        tree.set_own_paint_reach(root, 30.0);
        let _ = tree.take_damage(root);

        let held = tree.paint_overflow(root);
        tree.set_own_paint_reach(root, 10.0);
        assert_eq!(
            tree.paint_overflow(root),
            held,
            "the union has to be the children's on both sides, or this asks \
             nothing"
        );

        assert!(
            matches!(tree.take_damage(root), DamageRegion::None),
            "nothing was vacated, so nothing should have been damaged"
        );
    }

    /// A transform carries a widget away from its box and then back, and the
    /// frame it comes back on has to name the pixels it is leaving.
    ///
    /// The outbound frame damages where the widget went, because the reach is
    /// refreshed before the rect is built and the rect is built from the reach.
    /// The return frame is refreshed the same way and reports the widget's own
    /// 50x50 box — so the pixels at its old position are never handed to
    /// `wl_surface.damage_buffer` and the compositor leaves the widget there.
    #[test]
    fn damage_covers_where_a_transform_came_back_from() {
        let (mut tree, root, child) = inset_child();

        // Out: a translate of 100 reaches 100 past every edge.
        tree.set_own_paint_reach(child, 100.0);
        tree.mark_needs_paint(child);
        let went = partial_damage(&mut tree, root);
        assert_eq!(
            Rect::new(10.0, 110.0, 50.0, 50.0).outset_beyond(went),
            0.0,
            "the outbound frame does not even cover where it went: {went:?}"
        );

        tree.clear_needs_paint(child);
        tree.clear_needs_paint(root);

        // Back to rest, on the frame after.
        tree.set_own_paint_reach(child, 0.0);
        tree.mark_needs_paint(child);
        let came_back = partial_damage(&mut tree, root);
        assert_eq!(
            went.outset_beyond(came_back),
            0.0,
            "the return frame damages {came_back:?}, which leaves the pixels \
             the widget occupied at {went:?} on screen as a fringe"
        );
    }

    /// The same defect without a transform anywhere near it.
    ///
    /// A shadow falling to nothing shrinks the same reach by the same route,
    /// and predates transforms contributing to it at all. Here so the fix is
    /// not made transform-shaped when the defect is not.
    #[test]
    fn damage_covers_the_ring_a_shrinking_shadow_leaves_behind() {
        let (mut tree, root, child) = inset_child();

        tree.set_own_paint_reach(child, 8.0);
        tree.mark_needs_paint(child);
        let with_shadow = partial_damage(&mut tree, root);

        tree.clear_needs_paint(child);
        tree.clear_needs_paint(root);

        tree.set_own_paint_reach(child, 0.0);
        tree.mark_needs_paint(child);
        let without = partial_damage(&mut tree, root);
        assert_eq!(
            with_shadow.outset_beyond(without),
            0.0,
            "the frame that drops the shadow damages {without:?}, so the ring \
             it cast at {with_shadow:?} stays on screen"
        );
    }

    /// A widget's bounds are not grown by what it or its children paint
    /// outside it: how far that reaches is damage's question, and
    /// `WidgetRef::rect` reads these. A reach of 20 carries the child past the
    /// root's edge, so the root's own overflow grows too. Neither widget here
    /// moves what it draws, so the bounds are the boxes they were laid out in.
    #[test]
    fn a_widgets_bounds_leave_out_what_is_painted_outside_it() {
        let (mut tree, root, child) = inset_child();
        tree.set_own_paint_reach(child, 20.0);
        assert_eq!(
            tree.get_surface_relative_bounds(child),
            Some(Rect::new(10.0, 10.0, 50.0, 50.0)),
            "its own shadow is not its bounds"
        );
        assert_eq!(
            tree.get_surface_relative_bounds(root),
            Some(Rect::new(0.0, 0.0, 200.0, 200.0)),
            "and neither is its child's"
        );
    }
}

/// Reading a clock outside the pass that owns it.
///
/// Both getters answer with the wall clock when their pass is not running, so
/// the reader gets a plausible number rather than an error — deliberately, and
/// #265 is not about removing that. It is about the number being plausible in
/// silence: an animation that read the event clock advanced by the age of the
/// input, and a widget that read either between passes measured against
/// whenever it happened to ask.
#[cfg(all(test, debug_assertions))]
mod clock_diagnostics {
    use std::time::Instant;

    use super::*;
    use crate::reactive::diagnostics::report_count;

    #[test]
    fn reading_the_frame_clock_outside_a_frame_is_reported() {
        let tree = Tree::new();

        let before = report_count();
        let _ = tree.frame_instant();

        assert_eq!(
            report_count(),
            before + 1,
            "the wall clock came back where the frame's instant was asked for, \
             and nothing said so"
        );
    }

    #[test]
    fn reading_the_event_clock_outside_a_dispatch_is_reported() {
        let tree = Tree::new();

        let before = report_count();
        let _ = tree.event_instant();

        assert_eq!(
            report_count(),
            before + 1,
            "the wall clock came back where the event's instant was asked for, \
             and nothing said so"
        );
    }

    /// The message names the call site, so each site has to be its own entry
    /// in the rate limit: with one key for the whole getter, the first misuse
    /// anywhere in an application silences every other one for good, and the
    /// location it printed was the diagnostic's own.
    #[test]
    fn every_call_site_reports_once_and_the_next_site_still_reports() {
        let tree = Tree::new();

        let before = report_count();
        for _ in 0..3 {
            let _ = tree.frame_instant();
        }
        assert_eq!(
            report_count(),
            before + 1,
            "one site, however often it is read, says it once"
        );

        let _ = tree.frame_instant();
        assert_eq!(
            report_count(),
            before + 2,
            "and the next site is a different site, not the same one again"
        );
    }

    /// The rate limit is per call site and lasts for the life of the process,
    /// so the reset that wipes the reactive state between `App`s has to wipe it
    /// too: the second application on this thread makes the same mistakes as
    /// the first, and would be told nothing.
    ///
    /// Named by the mutation job — deleting the body of `diagnostics::reset`
    /// changed nothing any test could see.
    #[test]
    fn a_reset_forgets_the_sites_that_have_already_reported() {
        let tree = Tree::new();
        // One site, read twice: a closure so both reads are the same line.
        let read_outside_a_frame = || {
            let _ = tree.frame_instant();
        };

        read_outside_a_frame();
        assert_eq!(report_count(), 1, "the site said it once");

        crate::reactive::reset_reactive();

        assert_eq!(
            report_count(),
            0,
            "the reset forgets what has been reported, counter included"
        );
        read_outside_a_frame();
        assert_eq!(
            report_count(),
            1,
            "and the site is free to say it to the next application"
        );
    }

    #[test]
    fn each_clock_is_quiet_inside_the_pass_that_owns_it() {
        let mut tree = Tree::new();
        let now = Instant::now();

        tree.set_frame_instant(Some(now));
        let before = report_count();
        assert_eq!(tree.frame_instant(), now.into());
        tree.set_frame_instant(None);

        tree.set_event_instant(Some(now));
        assert_eq!(tree.event_instant(), now.into());
        tree.set_event_instant(None);

        assert_eq!(
            report_count(),
            before,
            "a clock read inside its own pass is the ordinary case and says \
             nothing"
        );
    }
}

/// What a widget is handed while it lays itself out: the tree, its own id, and
/// the way to lay out a child.
///
/// A parent used to call a child's `layout` itself, through
/// `Tree::with_widget_mut`, so everything that should happen around every
/// layout was left to each widget to remember — the skip check, the tracking
/// scope, which pass is running, the cache write.
/// [`layout_child`](Self::layout_child) is that call, once, for everybody.
pub struct LayoutCtx<'a> {
    tree: &'a mut Tree,
    id: WidgetId,
    /// Whether this widget bounds what its children paint. Recorded rather
    /// than published, because what follows from it is measured against the
    /// size the widget has not answered with yet.
    clips_children: bool,
    /// The least this widget can be, recorded during its layout. Cached
    /// with the size it answers, which is why it waits here.
    minimum: Option<Size>,
}

impl LayoutCtx<'_> {
    /// The widget being laid out.
    pub fn id(&self) -> WidgetId {
        self.id
    }

    /// The tree, for the geometry a layout writes: origins, baselines, and
    /// what a widget declares about its own paint.
    pub fn tree(&mut self) -> &mut Tree {
        self.tree
    }

    /// The tree, to read.
    pub fn tree_ref(&self) -> &Tree {
        self.tree
    }

    /// Say that what was just read would have answered the other pass
    /// differently — a value in flight, or one this measure placed without
    /// letting it appear.
    ///
    /// Called by the value reads themselves, which is the only place that
    /// knows. What it decides is whether the pass that did *not* run may read
    /// this subtree's answer: a settled one may, and one that said this may
    /// not.
    pub fn answer_depends_on_the_pass(&mut self) {
        self.tree.pass_dependent = true;
    }

    /// Whether this pass reads where animations are going rather than where
    /// they are — true while a natural size is being measured.
    pub fn measuring(&self) -> bool {
        self.tree.measuring()
    }

    /// Say that what this widget's children paint is bounded by its own edges
    /// — a scroller, or an `Overflow::Hidden` box.
    ///
    /// Published when the layout returns, because the reach it recomputes is
    /// measured against the size this layout is about to answer with.
    pub fn clips_children(&mut self, clips: bool) {
        self.clips_children = clips;
    }

    /// Record the least this widget can be on each axis: how far a flex
    /// whose children do not fit may take it down. A widget that records
    /// nothing is never shrunk. A layout records the least its children can
    /// be arranged in, which the container holding it reads back with
    /// [`minimum`](Self::minimum) and records its own over.
    pub fn set_minimum(&mut self, minimum: Size) {
        self.minimum = Some(minimum);
    }

    /// What this layout has recorded with [`set_minimum`](Self::set_minimum)
    /// so far.
    pub fn minimum(&self) -> Option<Size> {
        self.minimum
    }

    /// A context for the tests of what a layout *reads*, which are about the
    /// values rather than about any widget: a layout pass, over a tree, with
    /// nothing in it.
    #[cfg(test)]
    pub(crate) fn detached(tree: &mut Tree) -> LayoutCtx<'_> {
        LayoutCtx {
            id: WidgetId::new(0, 0),
            tree,
            clips_children: false,
            minimum: None,
        }
    }

    /// Lay a child out under `constraints`, and answer with its size.
    ///
    /// The one place a child's layout is reached from. It skips a child that
    /// has nothing to redo, opens the child's own tracking scope, runs it in
    /// the pass that is running, and writes what it answered into the cache.
    pub fn layout_child(&mut self, child: WidgetId, constraints: Constraints) -> Option<Size> {
        self.tree.layout_widget(child, constraints)
    }
}