eui_core/

engine.rs

//! The layout ENGINE: taffy's algorithms (flexbox, grid, block) over the
//! surface's own node slots (taffy's "custom tree" API), so the core
//! controls what `TaffyTree` hides:
//!
//! - a measured leaf answers with its size AND its first BASELINE
//!   (`alignItems: baseline` aligns text by its first line, not its bottom);
//! - nodes live in STABLE SLOTS (the surface's node indices): a re-windowed
//!   list or an opened overlay touches only the slots that changed, and
//!   `mark_dirty` clears the layout cache of a node and its ancestors only;
//! - `content_size` per node (scroll containers report their scrollable
//!   extent).

use taffy::prelude::*;
use taffy::{
    compute_block_layout, compute_cached_layout, compute_flexbox_layout, compute_grid_layout, compute_hidden_layout, compute_leaf_layout,
    compute_root_layout, round_layout, CacheTree, LayoutInput, LayoutOutput, RunMode,
};

/// VAPP-103: the per-slot layout CACHE. taffy 0.12's own `Cache` keys
/// every size request on the PARENT size too, and nested flex items get
/// asked once with the parent's width known and once without: both land in
/// the same slot, evict each other, and every level re-measures its subtree
/// twice (layout time doubled per level: 20 nested Stacks = 0.6 s, 14
/// nested Cards = 160 s). The parent size only matters to a node whose OWN
/// style holds a percentage (its size, insets, margins, padding, border,
/// gap or flex basis resolve against it), so only those nodes key on it, in
/// a second bank of slots per parent-width state. A request HITS when its
/// known dimensions equal the entry's and each unknown dimension's
/// available space is roughly equal (taffy's own rule otherwise), the
/// entry answered the same AXIS or both (grid sizes items one axis at a
/// time: a width-only answer carries a meaningless height) and the same
/// SIZING MODE (a content-size answer ignores the node's own size style;
/// taffy's cache conflates the two).
#[derive(Debug, Clone, Copy)]
struct CacheEntry<T> {
    known: Size<Option<f32>>,
    available: Size<AvailableSpace>,
    parent: Size<Option<f32>>,
    axis: taffy::RequestedAxis,
    sizing: taffy::SizingMode,
    content: T,
}

impl<T> CacheEntry<T> {
    fn matches(&self, input: &LayoutInput, percent: bool) -> bool {
        let known = input.known_dimensions;
        known.width == self.known.width
            && known.height == self.known.height
            && (known.width.is_some() || self.available.width.is_roughly_equal(input.available_space.width))
            && (known.height.is_some() || self.available.height.is_roughly_equal(input.available_space.height))
            && (!percent || self.parent == input.parent_size)
            && (self.axis == input.axis || self.axis == taffy::RequestedAxis::Both)
            && self.sizing == input.sizing_mode
    }
}

/// The size slots: taffy's nine (by how many dimensions are known and
/// whether an unknown one is sized under min-content), × parent width
/// known / unknown for a percentage-sensitive node, × the sizing mode.
#[derive(Debug, Clone, Default)]
struct Cache {
    layout: Option<CacheEntry<LayoutOutput>>,
    /// Only the slots this node was asked for (most use one to three), by
    /// slot number.
    sizes: Vec<(u8, CacheEntry<Size<f32>>)>,
}

impl Cache {
    /// The slot of a size request. The sizing mode has slots of its own:
    /// an entry only answers its own mode, so sharing a slot made an
    /// inherent-size and a content-size request of one node evict each
    /// other, and nested BLOCK boxes over a wrapping text re-measured their
    /// subtree per level (2^depth: 47 nested Boxes never finished).
    fn slot(input: &LayoutInput, percent: bool) -> u8 {
        use AvailableSpace::MinContent;
        let (known, available) = (input.known_dimensions, input.available_space);
        let base = match (known.width.is_some(), known.height.is_some()) {
            (true, true) => 0,
            (true, false) => 1 + (available.height == MinContent) as u8,
            (false, true) => 3 + (available.width == MinContent) as u8,
            (false, false) => 5 + (available.height == MinContent) as u8 + 2 * (available.width == MinContent) as u8,
        };
        let parent = if percent && input.parent_size.width.is_some() { 9 } else { 0 };
        let sizing = if input.sizing_mode == taffy::SizingMode::ContentSize { 18 } else { 0 };
        base + parent + sizing
    }

    fn get(&self, input: &LayoutInput, percent: bool) -> Option<LayoutOutput> {
        match input.run_mode {
            RunMode::PerformLayout => self.layout.filter(|e| e.matches(input, percent)).map(|e| e.content),
            RunMode::ComputeSize => self.sizes.iter().find(|(_, e)| e.matches(input, percent)).map(|(_, e)| LayoutOutput::from_outer_size(e.content)),
            RunMode::PerformHiddenLayout => None,
        }
    }

    fn store(&mut self, input: &LayoutInput, output: LayoutOutput, percent: bool) {
        let (known, available, parent, axis, sizing) = (input.known_dimensions, input.available_space, input.parent_size, input.axis, input.sizing_mode);
        match input.run_mode {
            RunMode::PerformLayout => self.layout = Some(CacheEntry { known, available, parent, axis, sizing, content: output }),
            RunMode::ComputeSize => {
                let entry = CacheEntry { known, available, parent, axis, sizing, content: output.size };
                let slot = Self::slot(input, percent);
                match self.sizes.iter_mut().find(|(s, _)| *s == slot) {
                    Some(held) => held.1 = entry,
                    None => self.sizes.push((slot, entry)),
                }
            }
            RunMode::PerformHiddenLayout => {}
        }
    }

    fn clear(&mut self) {
        self.layout = None;
        self.sizes.clear();
    }
}

/// Does any length of the node's OWN style resolve against its parent's size?
fn percent_sensitive(style: &Style) -> bool {
    let rect = |r: &Rect<LengthPercentage>| [r.left, r.right, r.top, r.bottom].iter().any(|v| v.into_raw().uses_percentage());
    let rect_auto = |r: &Rect<LengthPercentageAuto>| [r.left, r.right, r.top, r.bottom].iter().any(|v| v.into_raw().uses_percentage());
    let size = |s: &Size<Dimension>| s.width.into_raw().uses_percentage() || s.height.into_raw().uses_percentage();
    size(&style.size)
        || size(&style.min_size)
        || size(&style.max_size)
        || rect(&style.padding)
        || rect(&style.border)
        || rect_auto(&style.margin)
        || rect_auto(&style.inset)
        || style.flex_basis.into_raw().uses_percentage()
        || style.gap.width.into_raw().uses_percentage()
        || style.gap.height.into_raw().uses_percentage()
}

/// What a measured leaf answers for one taffy request.
#[derive(Debug, Clone, Copy, PartialEq, Default)]
pub struct LeafAnswer {
    pub size: Size<f32>,
    /// The first baseline, from the top of the border box; `None` = the
    /// bottom edge (CSS synthesizes it there).
    pub baseline: Option<f32>,
}

#[derive(Debug, Clone)]
struct ENode {
    style: Style,
    cache: Cache,
    unrounded: Layout,
    rounded: Layout,
    children: Vec<u32>,
    parent: Option<u32>,
    /// A measured leaf (its size comes from the measure callback).
    measured: bool,
    /// Its own style resolves a percentage against the parent size.
    percent: bool,
}

impl Default for ENode {
    fn default() -> Self {
        ENode {
            style: Style::default(),
            cache: Cache::default(),
            unrounded: Layout::with_order(0),
            rounded: Layout::with_order(0),
            children: Vec::new(),
            parent: None,
            measured: false,
            percent: false,
        }
    }
}

/// One tree of slots; several roots (the main tree, every overlay layer).
#[derive(Debug, Clone, Default)]
pub struct Engine {
    nodes: Vec<ENode>,
    rounding: bool,
    /// Tests only: every request misses (the differential reference).
    #[cfg(test)]
    no_cache: bool,
}

/// The measure callback: `(slot, known size, available space) → answer`.
pub type MeasureFn<'a> = dyn FnMut(u32, Size<Option<f32>>, Size<AvailableSpace>) -> LeafAnswer + 'a;

struct View<'t, 'm> {
    engine: &'t mut Engine,
    measure: &'t mut MeasureFn<'m>,
}

pub struct ChildIter<'a>(std::slice::Iter<'a, u32>);

impl Iterator for ChildIter<'_> {
    type Item = NodeId;
    fn next(&mut self) -> Option<NodeId> {
        self.0.next().map(|i| NodeId::from(*i as usize))
    }
}

fn slot(id: NodeId) -> usize {
    usize::from(id)
}

impl taffy::TraversePartialTree for View<'_, '_> {
    type ChildIter<'a>
        = ChildIter<'a>
    where
        Self: 'a;

    fn child_ids(&self, node: NodeId) -> Self::ChildIter<'_> {
        ChildIter(self.engine.nodes[slot(node)].children.iter())
    }

    fn child_count(&self, node: NodeId) -> usize {
        self.engine.nodes[slot(node)].children.len()
    }

    fn get_child_id(&self, node: NodeId, index: usize) -> NodeId {
        NodeId::from(self.engine.nodes[slot(node)].children[index] as usize)
    }
}

impl taffy::TraverseTree for View<'_, '_> {}

impl taffy::LayoutPartialTree for View<'_, '_> {
    type CoreContainerStyle<'a>
        = &'a Style
    where
        Self: 'a;
    type CustomIdent = String;

    fn get_core_container_style(&self, node: NodeId) -> Self::CoreContainerStyle<'_> {
        &self.engine.nodes[slot(node)].style
    }

    fn set_unrounded_layout(&mut self, node: NodeId, layout: &Layout) {
        self.engine.nodes[slot(node)].unrounded = *layout;
    }

    fn resolve_calc_value(&self, _val: *const (), _basis: f32) -> f32 {
        0.0
    }

    fn compute_child_layout(&mut self, node: NodeId, inputs: LayoutInput) -> LayoutOutput {
        crate::deep(|| self.compute_child(node, inputs))
    }
}

impl View<'_, '_> {
    fn compute_child(&mut self, node: NodeId, inputs: LayoutInput) -> LayoutOutput {
        if inputs.run_mode == RunMode::PerformHiddenLayout {
            return compute_hidden_layout(self, node);
        }
        compute_cached_layout(self, node, inputs, |view, node, inputs| {
            let n = &view.engine.nodes[slot(node)];
            let display = n.style.display;
            let has_children = !n.children.is_empty();
            match (display, has_children) {
                (Display::None, _) => compute_hidden_layout(view, node),
                (Display::Block, true) => compute_block_layout(view, node, inputs, None),
                (Display::Flex, true) => compute_flexbox_layout(view, node, inputs),
                (Display::Grid, true) => compute_grid_layout(view, node, inputs),
                (_, false) => {
                    let index = slot(node) as u32;
                    let View { engine, measure } = view;
                    let n = &engine.nodes[slot(node)];
                    let measured = n.measured;
                    let ratio = n.style.aspect_ratio.filter(|r| r.is_finite() && *r > 0.0);
                    let mut baseline = None;
                    let mut output = compute_leaf_layout(inputs, &n.style, |_, _| 0.0, |known, available| {
                        // Round 2 §7: an aspect-ratio box whose width is known
                        // (stretched, flexed) takes height = width / ratio, as
                        // CSS transfers it (taffy only does for SIZED axes).
                        if let (Some(r), Some(w), None) = (ratio, known.width, known.height) {
                            return Size { width: w, height: w / r };
                        }
                        if !measured {
                            return Size::ZERO;
                        }
                        let answer = measure(index, known, available);
                        baseline = answer.baseline;
                        answer.size
                    });
                    if let Some(b) = baseline {
                        output.first_baselines.y = Some(b);
                    }
                    output
                }
            }
        })
    }
}

impl CacheTree for View<'_, '_> {
    fn cache_get(&self, node: NodeId, input: &LayoutInput) -> Option<LayoutOutput> {
        #[cfg(test)]
        if self.engine.no_cache {
            return None;
        }
        let n = &self.engine.nodes[slot(node)];
        n.cache.get(input, n.percent)
    }

    fn cache_store(&mut self, node: NodeId, input: &LayoutInput, output: LayoutOutput) {
        let n = &mut self.engine.nodes[slot(node)];
        n.cache.store(input, output, n.percent)
    }

    fn cache_clear(&mut self, node: NodeId) {
        self.engine.nodes[slot(node)].cache.clear();
    }
}

impl taffy::LayoutFlexboxContainer for View<'_, '_> {
    type FlexboxContainerStyle<'a>
        = &'a Style
    where
        Self: 'a;
    type FlexboxItemStyle<'a>
        = &'a Style
    where
        Self: 'a;

    fn get_flexbox_container_style(&self, node: NodeId) -> Self::FlexboxContainerStyle<'_> {
        &self.engine.nodes[slot(node)].style
    }

    fn get_flexbox_child_style(&self, child: NodeId) -> Self::FlexboxItemStyle<'_> {
        &self.engine.nodes[slot(child)].style
    }
}

impl taffy::LayoutGridContainer for View<'_, '_> {
    type GridContainerStyle<'a>
        = &'a Style
    where
        Self: 'a;
    type GridItemStyle<'a>
        = &'a Style
    where
        Self: 'a;

    fn get_grid_container_style(&self, node: NodeId) -> Self::GridContainerStyle<'_> {
        &self.engine.nodes[slot(node)].style
    }

    fn get_grid_child_style(&self, child: NodeId) -> Self::GridItemStyle<'_> {
        &self.engine.nodes[slot(child)].style
    }
}

impl taffy::LayoutBlockContainer for View<'_, '_> {
    type BlockContainerStyle<'a>
        = &'a Style
    where
        Self: 'a;
    type BlockItemStyle<'a>
        = &'a Style
    where
        Self: 'a;

    fn get_block_container_style(&self, node: NodeId) -> Self::BlockContainerStyle<'_> {
        &self.engine.nodes[slot(node)].style
    }

    fn get_block_child_style(&self, child: NodeId) -> Self::BlockItemStyle<'_> {
        &self.engine.nodes[slot(child)].style
    }
}

impl taffy::RoundTree for View<'_, '_> {
    fn get_unrounded_layout(&self, node: NodeId) -> Layout {
        self.engine.nodes[slot(node)].unrounded
    }

    fn set_final_layout(&mut self, node: NodeId, layout: &Layout) {
        self.engine.nodes[slot(node)].rounded = *layout;
    }
}

impl Engine {
    pub fn new() -> Engine {
        Engine::default()
    }

    /// Off = fractional frames (the default).
    pub fn set_rounding(&mut self, on: bool) {
        self.rounding = on;
    }

    pub fn len(&self) -> usize {
        self.nodes.len()
    }

    pub fn is_empty(&self) -> bool {
        self.nodes.is_empty()
    }

    /// Grow (or shrink) to `n` slots; new slots are empty leaves.
    pub fn resize(&mut self, n: usize) {
        self.nodes.resize_with(n, ENode::default);
    }

    pub fn clear(&mut self) {
        self.nodes.clear();
    }

    /// Replace a slot's style; its cache and its ancestors' are cleared when
    /// the style differs.
    pub fn set_style(&mut self, i: u32, style: Style) -> bool {
        if self.nodes[i as usize].style == style {
            return false;
        }
        self.nodes[i as usize].percent = percent_sensitive(&style);
        self.nodes[i as usize].style = style;
        self.mark_dirty(i);
        true
    }

    pub fn style(&self, i: u32) -> &Style {
        &self.nodes[i as usize].style
    }

    /// Set a slot's children (parent pointers follow); dirty when changed.
    pub fn set_children(&mut self, i: u32, children: &[u32]) {
        if self.nodes[i as usize].children == children {
            return;
        }
        for c in std::mem::take(&mut self.nodes[i as usize].children) {
            if self.nodes[c as usize].parent == Some(i) {
                self.nodes[c as usize].parent = None;
            }
        }
        for &c in children {
            self.nodes[c as usize].parent = Some(i);
        }
        self.nodes[i as usize].children = children.to_vec();
        self.mark_dirty(i);
    }

    pub fn children(&self, i: u32) -> &[u32] {
        &self.nodes[i as usize].children
    }

    pub fn set_measured(&mut self, i: u32, measured: bool) {
        if self.nodes[i as usize].measured != measured {
            self.nodes[i as usize].measured = measured;
            self.mark_dirty(i);
        }
    }

    /// Forget the cached layout of `i` and every ancestor.
    pub fn mark_dirty(&mut self, i: u32) {
        let mut cur = Some(i);
        while let Some(n) = cur {
            let node = &mut self.nodes[n as usize];
            node.cache.clear();
            cur = node.parent;
        }
    }

    pub fn mark_all_dirty(&mut self) {
        for n in &mut self.nodes {
            n.cache.clear();
        }
    }

    /// Lay out the tree under `root` against the available space.
    pub fn compute(&mut self, root: u32, available: Size<AvailableSpace>, measure: &mut MeasureFn) {
        let rounding = self.rounding;
        let mut view = View { engine: self, measure };
        compute_root_layout(&mut view, NodeId::from(root as usize), available);
        if rounding {
            round_layout(&mut view, NodeId::from(root as usize));
        }
    }

    /// The final layout of a slot (relative to its parent).
    pub fn layout(&self, i: u32) -> &Layout {
        let n = &self.nodes[i as usize];
        if self.rounding {
            &n.rounded
        } else {
            &n.unrounded
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn baseline_alignment_uses_the_measured_first_baseline() {
        let mut e = Engine::new();
        e.resize(3);
        e.set_style(0, Style { display: Display::Flex, align_items: Some(AlignItems::BASELINE), ..Style::default() });
        e.set_children(0, &[1, 2]);
        e.set_measured(1, true);
        e.set_measured(2, true);
        // A 40 px control whose text baseline sits at 26, beside a 20 px
        // text line whose baseline is 15: the text moves down by 11.
        let mut measure = |i: u32, _k: Size<Option<f32>>, _a: Size<AvailableSpace>| match i {
            1 => LeafAnswer { size: Size { width: 80.0, height: 40.0 }, baseline: Some(26.0) },
            _ => LeafAnswer { size: Size { width: 50.0, height: 20.0 }, baseline: Some(15.0) },
        };
        e.compute(0, Size { width: AvailableSpace::Definite(300.0), height: AvailableSpace::MaxContent }, &mut measure);
        assert_eq!(e.layout(1).location.y, 0.0);
        assert_eq!(e.layout(2).location.y, 11.0);
        // Without baselines the bottoms align (CSS synthesizes them there).
        let mut bottoms = |i: u32, _k: Size<Option<f32>>, _a: Size<AvailableSpace>| match i {
            1 => LeafAnswer { size: Size { width: 80.0, height: 40.0 }, baseline: None },
            _ => LeafAnswer { size: Size { width: 50.0, height: 20.0 }, baseline: None },
        };
        e.mark_all_dirty();
        e.compute(0, Size { width: AvailableSpace::Definite(300.0), height: AvailableSpace::MaxContent }, &mut bottoms);
        assert_eq!(e.layout(2).location.y, 20.0);
    }

    #[test]
    fn dirty_marking_climbs_to_the_root_only() {
        let mut e = Engine::new();
        e.resize(4);
        e.set_style(0, Style { display: Display::Flex, flex_direction: FlexDirection::Column, ..Style::default() });
        e.set_children(0, &[1, 2]);
        e.set_style(2, Style { display: Display::Flex, ..Style::default() });
        e.set_children(2, &[3]);
        for i in [1, 3] {
            e.set_measured(i, true);
        }
        let calls = std::cell::Cell::new(0);
        let mut measure = |_i: u32, _k: Size<Option<f32>>, _a: Size<AvailableSpace>| {
            calls.set(calls.get() + 1);
            LeafAnswer { size: Size { width: 10.0, height: 10.0 }, baseline: None }
        };
        e.compute(0, Size { width: AvailableSpace::Definite(100.0), height: AvailableSpace::MaxContent }, &mut measure);
        let first = calls.get();
        e.compute(0, Size { width: AvailableSpace::Definite(100.0), height: AvailableSpace::MaxContent }, &mut measure);
        assert_eq!(calls.get(), first, "a clean tree answers from its caches");
        e.mark_dirty(3);
        e.compute(0, Size { width: AvailableSpace::Definite(100.0), height: AvailableSpace::MaxContent }, &mut measure);
        assert!(calls.get() > first, "the dirty leaf is measured again");
    }
}


#[cfg(test)]
mod cache_tests {
    use super::*;

    /// VAPP-103: nested flex columns measure their leaf a constant number
    /// of times at any depth (taffy 0.12's cache made it 2^depth), with and
    /// without percentages in every level's own style.
    #[test]
    fn nested_flex_columns_measure_the_leaf_a_constant_number_of_times() {
        for percent in [false, true] {
            for depth in [4usize, 30, 50] {
                let mut e = Engine::new();
                e.resize(depth + 1);
                for i in 0..depth {
                    let mut style = Style { display: Display::Flex, flex_direction: FlexDirection::Column, ..Style::default() };
                    if percent {
                        style.size.width = Dimension::percent(1.0);
                        style.padding.left = LengthPercentage::percent(0.01);
                    }
                    e.set_style(i as u32, style);
                    e.set_children(i as u32, &[(i + 1) as u32]);
                }
                e.set_measured(depth as u32, true);
                let calls = std::cell::Cell::new(0);
                let mut measure = |_i: u32, _k: Size<Option<f32>>, _a: Size<AvailableSpace>| {
                    calls.set(calls.get() + 1);
                    LeafAnswer { size: Size { width: 10.0, height: 10.0 }, baseline: None }
                };
                e.compute(0, Size { width: AvailableSpace::Definite(400.0), height: AvailableSpace::MaxContent }, &mut measure);
                assert!(calls.get() <= 8, "depth {depth} (percent {percent}): {} measures", calls.get());
                assert_eq!(e.layout(depth as u32).size.height, 10.0);
            }
        }
    }

    /// Nested BLOCK boxes over a WRAPPING leaf (its height follows the
    /// width it gets) measure it a constant number of times at any depth:
    /// a content-size and an inherent-size request no longer evict each
    /// other's slot (47 nested Boxes over a sentence used to never finish).
    #[test]
    fn nested_block_boxes_over_a_wrapping_leaf_measure_it_a_constant_number_of_times() {
        for display in [Display::Block, Display::Flex] {
            for depth in [4usize, 30, 50] {
                let mut e = Engine::new();
                e.resize(depth + 1);
                for i in 0..depth {
                    e.set_style(i as u32, Style { display, flex_direction: FlexDirection::Column, ..Style::default() });
                    e.set_children(i as u32, &[(i + 1) as u32]);
                }
                e.set_measured(depth as u32, true);
                let calls = std::cell::Cell::new(0);
                let mut measure = |_i: u32, k: Size<Option<f32>>, a: Size<AvailableSpace>| {
                    calls.set(calls.get() + 1);
                    let width = k.width.unwrap_or(match a.width {
                        AvailableSpace::Definite(w) => w.min(300.0),
                        AvailableSpace::MinContent => 60.0,
                        AvailableSpace::MaxContent => 300.0,
                    });
                    LeafAnswer { size: Size { width, height: k.height.unwrap_or((300.0 / width).ceil() * 16.0) }, baseline: None }
                };
                e.compute(0, Size { width: AvailableSpace::Definite(200.0), height: AvailableSpace::MaxContent }, &mut measure);
                assert!(calls.get() <= 12, "{display:?} depth {depth}: {} measures", calls.get());
                assert_eq!(e.layout(depth as u32).size.height, 32.0);
            }
        }
    }
}

#[cfg(test)]
mod differential_tests {
    use super::*;

    struct Rng(u64);
    impl Rng {
        fn n(&mut self, m: u64) -> u64 {
            self.0 = self.0.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407);
            (self.0 >> 33) % m
        }
    }

    fn dim(r: &mut Rng) -> Dimension {
        match r.n(4) {
            0 => Dimension::length((r.n(20) * 10) as f32),
            1 => Dimension::percent((r.n(10) as f32 + 1.0) / 10.0),
            _ => Dimension::auto(),
        }
    }

    fn lp(r: &mut Rng) -> LengthPercentage {
        match r.n(3) {
            0 => LengthPercentage::length(r.n(8) as f32),
            1 => LengthPercentage::percent(r.n(5) as f32 / 100.0),
            _ => LengthPercentage::length(0.0),
        }
    }

    fn style(r: &mut Rng, leaf: bool) -> Style {
        let mut s = Style::default();
        s.display = if leaf {
            Display::Flex
        } else {
            match r.n(3) {
                0 => Display::Block,
                1 => Display::Grid,
                _ => Display::Flex,
            }
        };
        s.flex_direction = if r.n(2) == 0 { FlexDirection::Row } else { FlexDirection::Column };
        if r.n(3) == 0 {
            s.flex_wrap = FlexWrap::Wrap;
        }
        s.size = Size { width: dim(r), height: if r.n(3) == 0 { dim(r) } else { Dimension::auto() } };
        if r.n(4) == 0 {
            s.min_size.width = dim(r);
        }
        if r.n(4) == 0 {
            s.max_size.width = dim(r);
        }
        s.padding = Rect { left: lp(r), right: lp(r), top: lp(r), bottom: lp(r) };
        s.flex_grow = r.n(3) as f32;
        s.flex_shrink = if r.n(4) == 0 { 0.0 } else { 1.0 };
        if r.n(4) == 0 {
            s.flex_basis = dim(r);
        }
        if r.n(4) == 0 {
            s.align_items = Some(AlignItems::FLEX_START);
        }
        if r.n(5) == 0 {
            s.gap = Size { width: lp(r), height: lp(r) };
        }
        s
    }

    /// A wrapping text leaf: `words` 13 px words on 16 px lines.
    fn text(words: u32, known: Size<Option<f32>>, avail: Size<AvailableSpace>) -> Size<f32> {
        let total = words as f32 * 13.0;
        let w = known.width.unwrap_or(match avail.width {
            AvailableSpace::Definite(w) => w.min(total).max(13.0),
            AvailableSpace::MinContent => 13.0,
            AvailableSpace::MaxContent => total,
        });
        let per = (w / 13.0).floor().max(1.0);
        Size { width: w, height: known.height.unwrap_or((words as f32 / per).ceil() * 16.0) }
    }

    fn build(styles: &[Style], kids: &[Vec<u32>], no_cache: bool) -> Engine {
        let mut e = Engine::new();
        e.no_cache = no_cache;
        e.resize(styles.len());
        for i in 0..styles.len() {
            e.set_style(i as u32, styles[i].clone());
            e.set_children(i as u32, &kids[i]);
            if kids[i].is_empty() {
                e.set_measured(i as u32, true);
            }
        }
        e
    }

    /// VAPP-103 rfix: a grid sizes its items one axis at a time; a
    /// width-only cache answer must never serve a height request (the box
    /// holding a 160 px child got height 0 and the next item overlapped it).
    #[test]
    fn grid_items_keep_their_heights_under_the_cache() {
        let grid = Style { display: Display::Grid, ..Style::default() };
        let a = Style { size: Size { width: Dimension::length(180.0), height: Dimension::auto() }, ..Style::default() };
        let tall = Style { size: Size { width: Dimension::auto(), height: Dimension::length(160.0) }, ..Style::default() };
        let styles = vec![grid, a, tall, Style::default()];
        let kids = vec![vec![1, 3], vec![2], vec![], vec![]];
        let mut e = build(&styles, &kids, false);
        e.set_measured(2, false);
        let mut m = |_i: u32, k: Size<Option<f32>>, a: Size<AvailableSpace>| LeafAnswer { size: text(5, k, a), baseline: None };
        e.compute(0, Size { width: AvailableSpace::Definite(400.0), height: AvailableSpace::MaxContent }, &mut m);
        assert_eq!(e.layout(1).size.height, 160.0);
        assert_eq!(e.layout(3).location.y, 160.0);
    }

    /// The cache never changes a layout: random flex/grid/block trees with
    /// percentages, laid out over a changing viewport by ONE cached engine,
    /// equal a fresh uncached engine at every pass.
    #[test]
    fn cached_layout_equals_uncached_layout_on_random_trees() {
        let viewports = [(400.0f32, None), (250.0, Some(300.0)), (400.0, None), (137.0, Some(300.0)), (400.0, Some(90.0))];
        for seed in 0..1000u64 {
            let mut r = Rng(seed * 7919 + 1);
            let n = if seed % 2 == 0 { 2 + r.n(4) as usize } else { 3 + r.n(25) as usize };
            let mut kids: Vec<Vec<u32>> = vec![vec![]; n];
            for i in 1..n {
                kids[r.n(i as u64) as usize].push(i as u32);
            }
            let styles: Vec<Style> = (0..n).map(|i| style(&mut r, kids[i].is_empty())).collect();
            let words: Vec<u32> = (0..n).map(|_| 1 + r.n(30) as u32).collect();
            let mut cached = build(&styles, &kids, false);
            for (pass, &(w, h)) in viewports.iter().enumerate() {
                let avail = Size { width: AvailableSpace::Definite(w), height: h.map_or(AvailableSpace::MaxContent, AvailableSpace::Definite) };
                let mut m = |i: u32, k: Size<Option<f32>>, a: Size<AvailableSpace>| LeafAnswer { size: text(words[i as usize], k, a), baseline: None };
                cached.compute(0, avail, &mut m);
                let mut reference = build(&styles, &kids, true);
                reference.compute(0, avail, &mut m);
                for i in 0..n as u32 {
                    let (a, b) = (cached.layout(i), reference.layout(i));
                    let d = (a.size.width - b.size.width).abs()
                        + (a.size.height - b.size.height).abs()
                        + (a.location.x - b.location.x).abs()
                        + (a.location.y - b.location.y).abs();
                    assert!(d <= 0.01, "seed {seed} pass {pass} node {i}: cached {:?}@{:?} uncached {:?}@{:?}", a.size, a.location, b.size, b.location);
                }
            }
        }
    }

    /// The depth bench: nested grid and block columns measure their leaf a
    /// bounded number of times at depth 30 (the axis key must not bring
    /// back the per-level doubling).
    #[test]
    fn nested_grid_and_block_measure_the_leaf_a_bounded_number_of_times() {
        for display in [Display::Grid, Display::Block, Display::Flex] {
            let depth = 30usize;
            let mut e = Engine::new();
            e.resize(depth + 1);
            for i in 0..depth {
                e.set_style(i as u32, Style { display, flex_direction: FlexDirection::Column, ..Style::default() });
                e.set_children(i as u32, &[(i + 1) as u32]);
            }
            e.set_measured(depth as u32, true);
            let calls = std::cell::Cell::new(0u64);
            let mut measure = |_i: u32, _k: Size<Option<f32>>, _a: Size<AvailableSpace>| {
                calls.set(calls.get() + 1);
                LeafAnswer { size: Size { width: 10.0, height: 10.0 }, baseline: None }
            };
            e.compute(0, Size { width: AvailableSpace::Definite(400.0), height: AvailableSpace::MaxContent }, &mut measure);
            assert!(calls.get() <= 16, "{display:?} depth {depth}: {} measures", calls.get());
            assert_eq!(e.layout(depth as u32).size.height, 10.0);
        }
    }
}