cvkg_layout/

lib.rs

//! # CVKG Agentic Development Guidelines (v1.2)
//!
//! All AI agents contributing to this crate MUST follow ALL seven rules:
//!
//! ── Karpathy Guidelines (1–4) ────────────────────────────────────────────
//! 1. THINK FIRST     -- State assumptions. Surface ambiguity. Push back on complexity.
//! 2. STAY SIMPLE     -- Minimum code. No speculative features. No unasked-for abstractions.
//! 3. BE SURGICAL     -- Touch only what's required. Own your orphans. Don't improve neighbors.
//! 4. VERIFY GOALS    -- Turn tasks into checkable criteria. Loop until they pass. Never commit broken.
//!
//! ── CVKG Extended Protocols (5–7) ────────────────────────────────────────
//! 5. TRIPLE-PASS     -- Read the target, its surrounding context, and its full call graph
//                      at least THREE TIMES before making any edit or revision.
//! 6. COMMENT ALL     -- Every major pub fn, unsafe block, and non-trivial algorithm in
//                      every .rs/.ts/.h/.wgsl file MUST have a descriptive doc comment.
//                      Comments describe WHY and WHAT CONTRACT, not HOW mechanically.
//! 7. MONITOR LOOPS   -- Check every tool call / command for progress every 30 seconds.
//                      After 3 consecutive identical failures, stop, write BLOCKED.md,
//                      and move to unblocked work. Never silently accept a broken state.
//!
//! Sources:
//   Karpathy: https://github.com/multica-ai/andrej-karpathy-skills
//   CVKG Extended: Section 2 of the CVKG Design Specification

pub use cvkg_core::layout::EdgeInsets;
use cvkg_core::{Alignment, Distribution, LayoutCache, LayoutView, Rect, Size, SizeProposal};
use std::collections::HashMap;
use std::cell::RefCell;
use std::collections::HashSet;

// P2-45: Layout capability flags for runtime feature detection.
// Applications can query these to determine which layout modes are supported.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub struct LayoutCapabilities {
    pub flexbox: bool,
    pub grid: bool,
    pub absolute: bool,
    pub container_queries: bool,
}

/// Returns the layout capabilities supported by this engine.
pub fn layout_capabilities() -> LayoutCapabilities {
    LayoutCapabilities {
        flexbox: true,
        grid: true,
        absolute: true,
        container_queries: true,
    }
}

thread_local! {
    static ACTIVE_LAYOUT_NODES: RefCell<HashSet<u64>> = RefCell::new(HashSet::new());
}

/// Helper function to prevent layout calculation cycles in recursive size queries.
/// If a view is already being traversed on the current thread, returns the fallback size.
fn with_layout_cycle_guard<F, R>(hash: u64, fallback: R, f: F) -> R
where
    F: FnOnce() -> R,
{
    if hash == 0 {
        return f();
    }
    let already_active = ACTIVE_LAYOUT_NODES.with(|nodes| !nodes.borrow_mut().insert(hash));
    if already_active {
        log::warn!("[Layout] Cycle detected for view hash 0x{:X}! Breaking cycle with fallback size.", hash);
        return fallback;
    }
    let res = f();
    ACTIVE_LAYOUT_NODES.with(|nodes| {
        nodes.borrow_mut().remove(&hash);
    });
    res
}

/// Helper function to prevent layout calculation cycles in recursive subview placements.
fn with_layout_cycle_guard_void<F>(hash: u64, f: F)
where
    F: FnOnce(),
{
    if hash == 0 {
        f();
        return;
    }
    let already_active = ACTIVE_LAYOUT_NODES.with(|nodes| !nodes.borrow_mut().insert(hash));
    if already_active {
        log::warn!("[Layout] Cycle detected for view hash 0x{:X}! Breaking cycle placement.", hash);
        return;
    }
    f();
    ACTIVE_LAYOUT_NODES.with(|nodes| {
        nodes.borrow_mut().remove(&hash);
    });
}

/// The central Taffy engine that computes flexbox and grid layouts.
/// Stored opaquely inside `cvkg_core::LayoutCache::engine`.
pub struct TaffyLayoutEngine {
    pub tree: taffy::TaffyTree,
    pub node_map: HashMap<u64, taffy::NodeId>,
}

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

impl TaffyLayoutEngine {
    pub fn new() -> Self {
        Self {
            tree: taffy::TaffyTree::new(),
            node_map: HashMap::new(),
        }
    }

    pub fn get_or_insert_engine(cache: &mut LayoutCache) -> &mut Self {
        if cache.engine.is_none() {
            cache.engine = Some(Box::new(TaffyLayoutEngine::new()));
        }
        cache
            .engine
            .as_mut()
            .unwrap()
            .downcast_mut::<TaffyLayoutEngine>()
            .unwrap()
    }
}

/// Manages active physics transitions for layout bounding boxes.
pub struct AnimationEngine {
    pub active_transitions: HashMap<u64, cvkg_anim::physics::ViscousSpring>,
    /// Generation counter for transition eviction.
    pub eviction_generation: u64,
    /// Tracks which generation each transition was last touched in.
    pub transition_generation: HashMap<u64, u64>,
    /// Number of generations a transition can go untouched before eviction.
    pub eviction_threshold: u64,
}

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

impl AnimationEngine {
    pub fn new() -> Self {
        Self {
            active_transitions: HashMap::new(),
            eviction_generation: 0,
            transition_generation: HashMap::new(),
            eviction_threshold: 300,
        }
    }

    pub fn get_or_insert_engine(cache: &mut LayoutCache) -> &mut Self {
        if cache.animators.is_none() {
            cache.animators = Some(Box::new(AnimationEngine::new()));
        }
        cache
            .animators
            .as_mut()
            .unwrap()
            .downcast_mut::<AnimationEngine>()
            .unwrap()
    }

    /// Evict settled transitions that haven't been touched for N generations.
    pub fn evict_stale_transitions(&mut self) {
        self.eviction_generation += 1;
        let threshold = self.eviction_threshold;
        let current_gen = self.eviction_generation;
        self.active_transitions.retain(|hash, spring| {
            let recent = self
                .transition_generation
                .get(hash)
                .map_or(false, |g| current_gen - *g < threshold);
            let unsettled = spring.velocity_a.length_sq() > 0.0001 || spring.velocity_b.length_sq() > 0.0001;
            recent || unsettled
        });
        self.transition_generation
            .retain(|hash, _| self.active_transitions.contains_key(hash));
    }
}

use taffy::prelude::*;

fn taffy_alignment(alignment: cvkg_core::Alignment) -> Option<taffy::AlignItems> {
    match alignment {
        cvkg_core::Alignment::Leading => Some(taffy::AlignItems::Start),
        cvkg_core::Alignment::Center => Some(taffy::AlignItems::Center),
        cvkg_core::Alignment::Trailing => Some(taffy::AlignItems::End),
        cvkg_core::Alignment::Top => Some(taffy::AlignItems::Start),
        cvkg_core::Alignment::Bottom => Some(taffy::AlignItems::End),
    }
}

fn taffy_distribution(dist: cvkg_core::Distribution) -> Option<taffy::JustifyContent> {
    match dist {
        cvkg_core::Distribution::Leading => Some(taffy::JustifyContent::Start),
        cvkg_core::Distribution::Center => Some(taffy::JustifyContent::Center),
        cvkg_core::Distribution::Trailing => Some(taffy::JustifyContent::End),
        cvkg_core::Distribution::SpaceBetween => Some(taffy::JustifyContent::SpaceBetween),
        cvkg_core::Distribution::Fill => Some(taffy::JustifyContent::Stretch),
        _ => None,
    }
}

/// Taffy flex layout parameters.
#[derive(Clone, Copy)]
struct FlexParams {
    dir: taffy::FlexDirection,
    spacing: f32,
    alignment: cvkg_core::Alignment,
    distribution: cvkg_core::Distribution,
    bounds: Rect,
    container_hash: u64,
}

/// Collect intrinsic sizes for all children without running the Taffy solver.
/// This is the expensive part (recursively calling size_that_fits on each child),
/// so we do it once and reuse the results for both measure and placement.
fn collect_child_sizes(
    subviews: &[&dyn LayoutView],
    bounds: Rect,
    cache: &mut LayoutCache,
) -> (Vec<u64>, Vec<f32>, Vec<Size>) {
    let mut sizes = Vec::with_capacity(subviews.len());
    let mut hashes = Vec::with_capacity(subviews.len());
    let mut flex_weights = Vec::with_capacity(subviews.len());

    for child in subviews {
        let hash = child.view_hash();
        hashes.push(hash);
        flex_weights.push(child.flex_weight());

        let proposal = SizeProposal::new(Some(bounds.width), Some(bounds.height));
        let cached_size = if hash != 0 {
            cache.get_size(hash, proposal)
        } else {
            None
        };

        let size = match cached_size {
            Some(sz) => sz,
            None => {
                let sz = with_layout_cycle_guard(hash, Size::ZERO, || {
                    child.size_that_fits(proposal, &[], cache)
                });
                if hash != 0 {
                    cache.set_size(hash, proposal, sz);
                }
                sz
            }
        };
        if hash != 0 {
            cache.register_parent(hash, 0); // parent registered by caller if needed
        }
        sizes.push(size);
    }

    (hashes, flex_weights, sizes)
}

/// Compute the natural (intrinsic) size of a flex container from child sizes,
/// without running the Taffy solver. Used by size_that_fits to avoid a full layout.
fn intrinsic_flex_size(dir: taffy::FlexDirection, spacing: f32, sizes: &[Size]) -> Size {
    if sizes.is_empty() {
        return Size::ZERO;
    }
    let n = sizes.len();
    match dir {
        taffy::FlexDirection::Row | taffy::FlexDirection::RowReverse => {
            let total_width: f32 = sizes.iter().map(|s| s.width).sum();
            let max_height: f32 = sizes.iter().map(|s| s.height).fold(0.0, f32::max);
            Size {
                width: total_width + spacing * (n.saturating_sub(1) as f32),
                height: max_height,
            }
        }
        taffy::FlexDirection::Column | taffy::FlexDirection::ColumnReverse => {
            let max_width: f32 = sizes.iter().map(|s| s.width).fold(0.0, f32::max);
            let total_height: f32 = sizes.iter().map(|s| s.height).sum();
            Size {
                width: max_width,
                height: total_height + spacing * (n.saturating_sub(1) as f32),
            }
        }
    }
}

fn compute_taffy_flex(
    params: &FlexParams,
    subviews: &[&dyn LayoutView],
    cache: &mut LayoutCache,
) -> Vec<Rect> {
    if cache.is_over_budget() {
        let mut rects = Vec::with_capacity(subviews.len());
        for child in subviews {
            let hash = child.view_hash();
            let r = if hash != 0 {
                cache.previous_rects.get(&hash).copied().unwrap_or(Rect::zero())
            } else {
                Rect::zero()
            };
            rects.push(r);
        }
        return rects;
    }

    // Collect child sizes (the expensive part -- done once, reused by place_subviews).
    let (hashes, flex_weights, sizes) = collect_child_sizes(subviews, params.bounds, cache);

    // Register parent relationships for invalidation propagation.
    for &hash in &hashes {
        if hash != 0 && params.container_hash != 0 {
            cache.register_parent(hash, params.container_hash);
        }
    }

    let engine = TaffyLayoutEngine::get_or_insert_engine(cache);
    let mut child_nodes = Vec::with_capacity(subviews.len());

    for ((&hash, &flex_weight), &size) in hashes.iter().zip(&flex_weights).zip(&sizes) {
        let style = if flex_weight > 0.0 {
            taffy::Style {
                size: taffy::Size {
                    width: if params.dir == taffy::FlexDirection::Row {
                        taffy::Dimension::Auto
                    } else {
                        taffy::Dimension::Length(size.width)
                    },
                    height: if params.dir == taffy::FlexDirection::Column {
                        taffy::Dimension::Auto
                    } else {
                        taffy::Dimension::Length(size.height)
                    },
                },
                flex_grow: flex_weight,
                flex_basis: taffy::Dimension::Percent(0.0),
                ..Default::default()
            }
        } else {
            taffy::Style {
                size: taffy::Size {
                    width: taffy::Dimension::Length(size.width),
                    height: taffy::Dimension::Length(size.height),
                },
                ..Default::default()
            }
        };

        let node = if hash != 0 {
            if let Some(&existing) = engine.node_map.get(&hash) {
                let _ = engine.tree.set_style(existing, style);
                existing
            } else {
                let new_node = engine.tree.new_leaf(style).unwrap();
                engine.node_map.insert(hash, new_node);
                new_node
            }
        } else {
            engine.tree.new_leaf(style).unwrap()
        };
        child_nodes.push(node);
    }

    let gap_val = taffy::LengthPercentage::Length(params.spacing);
    let container_style = taffy::Style {
        display: taffy::Display::Flex,
        flex_direction: params.dir,
        gap: taffy::Size {
            width: if params.dir == taffy::FlexDirection::Row {
                gap_val
            } else {
                taffy::LengthPercentage::Length(0.0)
            },
            height: if params.dir == taffy::FlexDirection::Column {
                gap_val
            } else {
                taffy::LengthPercentage::Length(0.0)
            },
        },
        align_items: taffy_alignment(params.alignment),
        justify_content: taffy_distribution(params.distribution),
        size: taffy::Size {
            width: taffy::Dimension::Length(params.bounds.width),
            height: taffy::Dimension::Length(params.bounds.height),
        },
        ..Default::default()
    };

    let root_node = if params.container_hash != 0 {
        if let Some(&existing) = engine.node_map.get(&params.container_hash) {
            let _ = engine.tree.set_style(existing, container_style);
            let _ = engine.tree.set_children(existing, &child_nodes);
            existing
        } else {
            let new_node = engine
                .tree
                .new_with_children(container_style, &child_nodes)
                .unwrap();
            engine.node_map.insert(params.container_hash, new_node);
            new_node
        }
    } else {
        engine
            .tree
            .new_with_children(container_style, &child_nodes)
            .unwrap()
    };

    engine
        .tree
        .compute_layout(root_node, taffy::Size::MAX_CONTENT)
        .unwrap();

    let mut rects = Vec::with_capacity(subviews.len());
    for &node in &child_nodes {
        let layout = engine.tree.layout(node).unwrap();
        rects.push(Rect {
            x: params.bounds.x + layout.location.x,
            y: params.bounds.y + layout.location.y,
            width: layout.size.width,
            height: layout.size.height,
        });
    }

    if params.container_hash == 0 {
        let _ = engine.tree.remove(root_node);
    }

    rects
}

/// Applies view transitions to calculated layout rects.
fn apply_layout_animations(
    rects: Vec<Rect>,
    subviews: &mut [&mut dyn LayoutView],
    cache: &mut LayoutCache,
) {
    let mut transitions_to_update = Vec::new();

    for (child, target_rect) in subviews.iter().zip(&rects) {
        let hash = child.view_hash();
        if hash != 0 {
            if let Some(prev) = cache.previous_rects.get(&hash) {
                let dx = (prev.x - target_rect.x).abs();
                let dy = (prev.y - target_rect.y).abs();
                let dw = (prev.width - target_rect.width).abs();
                let dh = (prev.height - target_rect.height).abs();
                let epsilon = 1e-3;
                if dx > epsilon || dy > epsilon || dw > epsilon || dh > epsilon {
                    transitions_to_update.push((hash, *prev, *target_rect));
                }
            }
            cache.previous_rects.insert(hash, *target_rect);
            cache.previous_rects_generation.insert(hash, cache.eviction_generation);
        }
    }

    let mut interpolated_rects = HashMap::new();
    let delta = cache.delta_time;
    let scale = cache.scale_factor;
    let anim_engine = AnimationEngine::get_or_insert_engine(cache);

    for (hash, prev, target_rect) in transitions_to_update {
        let mut spring = if let Some(mut existing) = anim_engine.active_transitions.remove(&hash) {
            existing.position_b =
                cvkg_anim::physics::Vec3::new(target_rect.x, target_rect.y, target_rect.width);
            existing
        } else {
            cvkg_anim::physics::ViscousSpring::new(
                cvkg_anim::physics::Vec3::new(prev.x, prev.y, prev.width),
                cvkg_anim::physics::Vec3::new(target_rect.x, target_rect.y, target_rect.width),
                0.9,
                1000.0,
            )
        };
        spring.step(delta);

        // Temporal layout snapping: snap layout coordinates to integer pixels
        // only when the spring has nearly settled to prevent jitter during motion.
        let speed = (spring.velocity_a.length_sq() + spring.velocity_b.length_sq()).sqrt();
        let snap = |v: f32| (v * scale).round() / scale;

        let (rx, ry, rw) = if speed < 0.05 {
            (
                snap(spring.position_a.x),
                snap(spring.position_a.y),
                snap(spring.position_a.z),
            )
        } else {
            (
                spring.position_a.x,
                spring.position_a.y,
                spring.position_a.z,
            )
        };

        interpolated_rects.insert(
            hash,
            Rect {
                x: rx,
                y: ry,
                width: rw,
                height: target_rect.height,
            },
        );
        anim_engine.active_transitions.insert(hash, spring);
        anim_engine.transition_generation.insert(hash, anim_engine.eviction_generation);
    }
    // Drop anim_engine before evicting cache entries (borrow conflict)
    // anim_engine dropped implicitly (borrow conflict resolved by scope)

    // Evict stale entries to prevent unbounded growth over long sessions.
    cache.evict_stale_entries();

    // Re-borrow anim_engine for its own eviction
    let anim_engine = AnimationEngine::get_or_insert_engine(cache);
    anim_engine.evict_stale_transitions();

    for (child, mut target_rect) in subviews.iter_mut().zip(rects) {
        let hash = child.view_hash();
        if let Some(interp) = interpolated_rects.get(&hash) {
            target_rect = *interp;
        }
        let is_visible = if let Some(viewport) = cache.viewport {
            target_rect.intersects(&viewport)
        } else {
            true
        };
        if is_visible {
            with_layout_cycle_guard_void(hash, || {
                child.place_subviews(target_rect, &mut [], cache);
            });
        }
    }
}

/// HStack - lays out children horizontally
pub struct HStack {
    spacing: f32,
    alignment: Alignment,
    distribution: Distribution,
}

impl HStack {
    /// Create a new HStack with the given spacing, alignment, and distribution
    pub fn new(spacing: f32, alignment: Alignment, distribution: Distribution) -> Self {
        Self {
            spacing,
            alignment,
            distribution,
        }
    }

    /// Compute the layout rects for children without placing them.
    pub fn compute_layout(
        spacing: f32,
        alignment: Alignment,
        distribution: Distribution,
        bounds: Rect,
        subviews: &[&dyn LayoutView],
        cache: &mut LayoutCache,
    ) -> Vec<Rect> {
        Self::compute_layout_incremental(
            spacing,
            alignment,
            distribution,
            bounds,
            0,
            subviews,
            cache,
        )
    }

    pub fn compute_layout_incremental(
        spacing: f32,
        alignment: Alignment,
        distribution: Distribution,
        bounds: Rect,
        container_hash: u64,
        subviews: &[&dyn LayoutView],
        cache: &mut LayoutCache,
    ) -> Vec<Rect> {
        compute_taffy_flex(
            &FlexParams {
                dir: taffy::FlexDirection::Row,
                spacing,
                alignment,
                distribution,
                bounds,
                container_hash,
            },
            subviews,
            cache,
        )
    }
}

impl LayoutView for HStack {
    fn size_that_fits(
        &self,
        proposal: SizeProposal,
        subviews: &[&dyn LayoutView],
        cache: &mut LayoutCache,
    ) -> Size {
        let bounds = Rect {
            x: 0.0,
            y: 0.0,
            width: proposal.width.unwrap_or(10000.0),
            height: proposal.height.unwrap_or(10000.0),
        };
        // Fast path: collect child sizes and compute intrinsic size without Taffy solve.
        // The full Taffy solve happens only in place_subviews.
        let (_, _, sizes) = collect_child_sizes(subviews, bounds, cache);
        intrinsic_flex_size(taffy::FlexDirection::Row, self.spacing, &sizes)
    }

    fn place_subviews(
        &self,
        bounds: Rect,
        subviews: &mut [&mut dyn LayoutView],
        cache: &mut LayoutCache,
    ) {
        let views: Vec<&dyn LayoutView> =
            subviews.iter().map(|v| &**v as &dyn LayoutView).collect();
        let rects = Self::compute_layout_incremental(
            self.spacing,
            self.alignment,
            self.distribution,
            bounds,
            self.view_hash(),
            &views,
            cache,
        );
        apply_layout_animations(rects, subviews, cache);
    }
}

/// VStack - lays out children vertically
pub struct VStack {
    spacing: f32,
    alignment: Alignment,
    distribution: Distribution,
}

impl VStack {
    /// Create a new VStack with the given spacing, alignment, and distribution
    pub fn new(spacing: f32, alignment: Alignment, distribution: Distribution) -> Self {
        Self {
            spacing,
            alignment,
            distribution,
        }
    }

    /// Compute the layout rects for children without placing them.
    pub fn compute_layout(
        spacing: f32,
        alignment: Alignment,
        distribution: Distribution,
        bounds: Rect,
        subviews: &[&dyn LayoutView],
        cache: &mut LayoutCache,
    ) -> Vec<Rect> {
        Self::compute_layout_incremental(
            spacing,
            alignment,
            distribution,
            bounds,
            0,
            subviews,
            cache,
        )
    }

    pub fn compute_layout_incremental(
        spacing: f32,
        alignment: Alignment,
        distribution: Distribution,
        bounds: Rect,
        container_hash: u64,
        subviews: &[&dyn LayoutView],
        cache: &mut LayoutCache,
    ) -> Vec<Rect> {
        compute_taffy_flex(
            &FlexParams {
                dir: taffy::FlexDirection::Column,
                spacing,
                alignment,
                distribution,
                bounds,
                container_hash,
            },
            subviews,
            cache,
        )
    }
}

impl LayoutView for VStack {
    fn size_that_fits(
        &self,
        proposal: SizeProposal,
        subviews: &[&dyn LayoutView],
        cache: &mut LayoutCache,
    ) -> Size {
        let bounds = Rect {
            x: 0.0,
            y: 0.0,
            width: proposal.width.unwrap_or(10000.0),
            height: proposal.height.unwrap_or(10000.0),
        };
        // Fast path: collect child sizes and compute intrinsic size without Taffy solve.
        let (_, _, sizes) = collect_child_sizes(subviews, bounds, cache);
        intrinsic_flex_size(taffy::FlexDirection::Column, self.spacing, &sizes)
    }

    fn place_subviews(
        &self,
        bounds: Rect,
        subviews: &mut [&mut dyn LayoutView],
        cache: &mut LayoutCache,
    ) {
        let views: Vec<&dyn LayoutView> =
            subviews.iter().map(|v| &**v as &dyn LayoutView).collect();
        let rects = Self::compute_layout_incremental(
            self.spacing,
            self.alignment,
            self.distribution,
            bounds,
            self.view_hash(),
            &views,
            cache,
        );
        apply_layout_animations(rects, subviews, cache);
    }
}

/// ZStack - lays out children on top of each other
pub struct ZStack {}

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

impl ZStack {
    /// Create a new ZStack
    pub fn new() -> Self {
        Self {}
    }
}

impl LayoutView for ZStack {
    fn size_that_fits(
        &self,
        proposal: SizeProposal,
        subviews: &[&dyn LayoutView],
        cache: &mut LayoutCache,
    ) -> Size {
        let mut width = 0.0f32;
        let mut height = 0.0f32;
        let self_hash = self.view_hash();

        for child in subviews.iter() {
            let child_hash = child.view_hash();
            if self_hash != 0 && child_hash != 0 {
                cache.register_parent(child_hash, self_hash);
            }
            let child_size = with_layout_cycle_guard(child_hash, Size::ZERO, || {
                child.size_that_fits(proposal, &[], cache)
            });
            width = width.max(child_size.width);
            height = height.max(child_size.height);
        }

        Size { width, height }
    }

    fn place_subviews(
        &self,
        bounds: Rect,
        subviews: &mut [&mut dyn LayoutView],
        cache: &mut LayoutCache,
    ) {
        let self_hash = self.view_hash();
        for child in subviews.iter_mut() {
            let child_hash = child.view_hash();
            if self_hash != 0 && child_hash != 0 {
                cache.register_parent(child_hash, self_hash);
            }
            let is_visible = if let Some(viewport) = cache.viewport {
                bounds.intersects(&viewport)
            } else {
                true
            };
            if is_visible {
                with_layout_cycle_guard_void(child_hash, || {
                    child.place_subviews(bounds, &mut [], cache);
                });
            }
        }
    }
}

/// Spacer - a layout view that expands to fill available space
pub struct Spacer;

impl LayoutView for Spacer {
    fn size_that_fits(
        &self,
        proposal: SizeProposal,
        _subviews: &[&dyn LayoutView],
        _cache: &mut LayoutCache,
    ) -> Size {
        Size {
            width: proposal.width.unwrap_or(0.0),
            height: proposal.height.unwrap_or(0.0),
        }
    }

    fn place_subviews(
        &self,
        _bounds: Rect,
        _subviews: &mut [&mut dyn LayoutView],
        _cache: &mut LayoutCache,
    ) {
    }
}

/// Flex - a container that distributes space among its children flexibly
pub struct Flex {
    pub orientation: cvkg_core::Orientation,
    pub spacing: f32,
}

impl Flex {
    pub fn new(orientation: cvkg_core::Orientation, spacing: f32) -> Self {
        Self {
            orientation,
            spacing,
        }
    }
}

impl LayoutView for Flex {
    fn size_that_fits(
        &self,
        proposal: SizeProposal,
        _subviews: &[&dyn LayoutView],
        _cache: &mut LayoutCache,
    ) -> Size {
        Size {
            width: proposal.width.unwrap_or(100.0),
            height: proposal.height.unwrap_or(100.0),
        }
    }

    fn place_subviews(
        &self,
        bounds: Rect,
        subviews: &mut [&mut dyn LayoutView],
        cache: &mut LayoutCache,
    ) {
        if subviews.is_empty() {
            return;
        }

        let self_hash = self.view_hash();
        let n = subviews.len() as f32;
        match self.orientation {
            cvkg_core::Orientation::Horizontal => {
                let total_spacing = self.spacing * (n - 1.0);
                let item_width = (bounds.width - total_spacing) / n;
                for (i, child) in subviews.iter_mut().enumerate() {
                    let child_rect = Rect {
                        x: bounds.x + i as f32 * (item_width + self.spacing),
                        y: bounds.y,
                        width: item_width,
                        height: bounds.height,
                    };
                    let child_hash = child.view_hash();
                    if self_hash != 0 && child_hash != 0 {
                        cache.register_parent(child_hash, self_hash);
                    }
                    let is_visible = if let Some(viewport) = cache.viewport {
                        child_rect.intersects(&viewport)
                    } else {
                        true
                    };
                    if is_visible {
                        with_layout_cycle_guard_void(child_hash, || {
                            child.place_subviews(child_rect, &mut [], cache);
                        });
                    }
                }
            }
            cvkg_core::Orientation::Vertical => {
                let total_spacing = self.spacing * (n - 1.0);
                let item_height = (bounds.height - total_spacing) / n;
                for (i, child) in subviews.iter_mut().enumerate() {
                    let child_rect = Rect {
                        x: bounds.x,
                        y: bounds.y + i as f32 * (item_height + self.spacing),
                        width: bounds.width,
                        height: item_height,
                    };
                    let child_hash = child.view_hash();
                    if self_hash != 0 && child_hash != 0 {
                        cache.register_parent(child_hash, self_hash);
                    }
                    let is_visible = if let Some(viewport) = cache.viewport {
                        child_rect.intersects(&viewport)
                    } else {
                        true
                    };
                    if is_visible {
                        with_layout_cycle_guard_void(child_hash, || {
                            child.place_subviews(child_rect, &mut [], cache);
                        });
                    }
                }
            }
        }
    }
}

/// Track sizing strategy for a single grid track (row or column).
#[derive(Debug, Clone, Copy, PartialEq)]
pub enum GridTrack {
    /// Exact pixel size.
    Fixed(f32),
    /// Proportional weight compared to other flex tracks.
    Flex(f32),
    /// Size based on the intrinsic size of the grid item.
    Auto,
    /// Size clamped between minimum and maximum bounds.
    MinMax(f32, f32),
}

fn taffy_track(track: GridTrack) -> taffy::TrackSizingFunction {
    match track {
        GridTrack::Fixed(v) => taffy::prelude::length(v),
        GridTrack::Flex(v) => taffy::prelude::fr(v),
        GridTrack::Auto => taffy::prelude::auto(),
        GridTrack::MinMax(min, max) => {
            taffy::prelude::minmax(taffy::prelude::length(min), taffy::prelude::length(max))
        }
    }
}

/// A layout engine that computes coordinates for children positioned in a 2D grid.
pub struct Grid {
    /// Column track sizing rules.
    pub columns: Vec<GridTrack>,
    /// Row track sizing rules.
    pub rows: Vec<GridTrack>,
    /// Empty space between columns.
    pub column_gap: f32,
    /// Empty space between rows.
    pub row_gap: f32,
}

impl Grid {
    /// Creates a new Grid layout engine.
    pub fn new(
        columns: Vec<GridTrack>,
        rows: Vec<GridTrack>,
        column_gap: f32,
        row_gap: f32,
    ) -> Self {
        Self {
            columns,
            rows,
            column_gap,
            row_gap,
        }
    }

    /// Computes the rects for children based on track sizing and grid placements.
    pub fn compute_layout_rects(
        &self,
        bounds: Rect,
        subviews: &[&dyn LayoutView],
        placements: &[Option<cvkg_core::GridPlacement>],
        cache: &mut LayoutCache,
    ) -> Vec<Rect> {
        self.compute_layout_rects_incremental(bounds, 0, subviews, placements, cache)
    }

    pub fn compute_layout_rects_incremental(
        &self,
        bounds: Rect,
        container_hash: u64,
        subviews: &[&dyn LayoutView],
        placements: &[Option<cvkg_core::GridPlacement>],
        cache: &mut LayoutCache,
    ) -> Vec<Rect> {
        if cache.is_over_budget() {
            let mut rects = Vec::with_capacity(subviews.len());
            for child in subviews {
                let hash = child.view_hash();
                let r = if hash != 0 {
                    cache.previous_rects.get(&hash).copied().unwrap_or(Rect::zero())
                } else {
                    Rect::zero()
                };
                rects.push(r);
            }
            return rects;
        }

        let mut hashes = Vec::with_capacity(subviews.len());
        for child in subviews {
            let hash = child.view_hash();
            hashes.push(hash);
            if container_hash != 0 && hash != 0 {
                cache.register_parent(hash, container_hash);
            }
        }

        let engine = TaffyLayoutEngine::get_or_insert_engine(cache);
        let mut child_nodes = Vec::with_capacity(subviews.len());

        for (hash, placement) in hashes.iter().zip(placements.iter()) {
            let style = if let Some(p) = placement.as_ref() {
                taffy::Style {
                    size: taffy::Size {
                        width: taffy::Dimension::Auto,
                        height: taffy::Dimension::Auto,
                    },
                    grid_column: taffy::Line {
                        start: taffy::prelude::line((p.column + 1) as i16),
                        end: taffy::prelude::span(p.column_span as u16),
                    },
                    grid_row: taffy::Line {
                        start: taffy::prelude::line((p.row + 1) as i16),
                        end: taffy::prelude::span(p.row_span as u16),
                    },
                    ..Default::default()
                }
            } else {
                taffy::Style {
                    size: taffy::Size {
                        width: taffy::Dimension::Auto,
                        height: taffy::Dimension::Auto,
                    },
                    ..Default::default()
                }
            };

            let node = if *hash != 0 {
                if let Some(&existing) = engine.node_map.get(hash) {
                    let _ = engine.tree.set_style(existing, style);
                    existing
                } else {
                    let new_node = engine.tree.new_leaf(style).unwrap();
                    engine.node_map.insert(*hash, new_node);
                    new_node
                }
            } else {
                engine.tree.new_leaf(style).unwrap()
            };
            child_nodes.push(node);
        }

        let container_style = taffy::Style {
            display: taffy::Display::Grid,
            grid_template_columns: self.columns.iter().copied().map(taffy_track).collect(),
            grid_template_rows: self.rows.iter().copied().map(taffy_track).collect(),
            gap: taffy::Size {
                width: taffy::LengthPercentage::Length(self.column_gap),
                height: taffy::LengthPercentage::Length(self.row_gap),
            },
            size: taffy::Size {
                width: taffy::Dimension::Length(bounds.width),
                height: taffy::Dimension::Length(bounds.height),
            },
            ..Default::default()
        };

        let root_node = if container_hash != 0 {
            if let Some(&existing) = engine.node_map.get(&container_hash) {
                let _ = engine.tree.set_style(existing, container_style);
                let _ = engine.tree.set_children(existing, &child_nodes);
                existing
            } else {
                let new_node = engine
                    .tree
                    .new_with_children(container_style, &child_nodes)
                    .unwrap();
                engine.node_map.insert(container_hash, new_node);
                new_node
            }
        } else {
            engine
                .tree
                .new_with_children(container_style, &child_nodes)
                .unwrap()
        };

        engine
            .tree
            .compute_layout(root_node, taffy::Size::MAX_CONTENT)
            .unwrap();

        let mut rects = Vec::with_capacity(subviews.len());
        for &node in &child_nodes {
            let layout = engine.tree.layout(node).unwrap();
            rects.push(Rect {
                x: bounds.x + layout.location.x,
                y: bounds.y + layout.location.y,
                width: layout.size.width,
                height: layout.size.height,
            });
        }

        if container_hash == 0 {
            let _ = engine.tree.remove(root_node);
        }
        rects
    }
}

impl LayoutView for Grid {
    fn size_that_fits(
        &self,
        proposal: SizeProposal,
        _subviews: &[&dyn LayoutView],
        _cache: &mut LayoutCache,
    ) -> Size {
        Size {
            width: proposal.width.unwrap_or(200.0),
            height: proposal.height.unwrap_or(200.0),
        }
    }

    fn place_subviews(
        &self,
        bounds: Rect,
        subviews: &mut [&mut dyn LayoutView],
        cache: &mut LayoutCache,
    ) {
        let views: Vec<&dyn LayoutView> =
            subviews.iter().map(|v| &**v as &dyn LayoutView).collect();
        let placements = vec![None; subviews.len()];
        let rects = self.compute_layout_rects_incremental(
            bounds,
            self.view_hash(),
            &views,
            &placements,
            cache,
        );
        apply_layout_animations(rects, subviews, cache);
    }
}

// =============================================================================
// PADDING
// =============================================================================

/// A layout view that adds padding around its child.
pub struct Padding {
    pub insets: EdgeInsets,
}

impl Padding {
    pub fn new(insets: EdgeInsets) -> Self {
        Self { insets }
    }

    pub fn uniform(value: f32) -> Self {
        Self {
            insets: EdgeInsets::all(value),
        }
    }

    pub fn symmetric(horizontal: f32, vertical: f32) -> Self {
        Self {
            insets: EdgeInsets {
                top: vertical,
                bottom: vertical,
                leading: horizontal,
                trailing: horizontal,
            },
        }
    }
}

impl LayoutView for Padding {
    fn size_that_fits(
        &self,
        proposal: SizeProposal,
        subviews: &[&dyn LayoutView],
        cache: &mut LayoutCache,
    ) -> Size {
        let inner_proposal = SizeProposal::new(
            proposal
                .width
                .map(|w| (w - self.insets.leading - self.insets.trailing).max(0.0)),
            proposal
                .height
                .map(|h| (h - self.insets.top - self.insets.bottom).max(0.0)),
        );
        let self_hash = self.view_hash();
        let child_size = if subviews.is_empty() {
            Size::ZERO
        } else {
            let child_hash = subviews[0].view_hash();
            if self_hash != 0 && child_hash != 0 {
                cache.register_parent(child_hash, self_hash);
            }
            with_layout_cycle_guard(child_hash, Size::ZERO, || {
                subviews[0].size_that_fits(inner_proposal, &[], cache)
            })
        };
        Size {
            width: child_size.width + self.insets.leading + self.insets.trailing,
            height: child_size.height + self.insets.top + self.insets.bottom,
        }
    }

    fn place_subviews(
        &self,
        bounds: Rect,
        subviews: &mut [&mut dyn LayoutView],
        cache: &mut LayoutCache,
    ) {
        let inner = Rect {
            x: bounds.x + self.insets.leading,
            y: bounds.y + self.insets.top,
            width: (bounds.width - self.insets.leading - self.insets.trailing).max(0.0),
            height: (bounds.height - self.insets.top - self.insets.bottom).max(0.0),
        };
        let self_hash = self.view_hash();
        for child in subviews.iter_mut() {
            let child_hash = child.view_hash();
            if self_hash != 0 && child_hash != 0 {
                cache.register_parent(child_hash, self_hash);
            }
            let is_visible = if let Some(viewport) = cache.viewport {
                inner.intersects(&viewport)
            } else {
                true
            };
            if is_visible {
                with_layout_cycle_guard_void(child_hash, || {
                    child.place_subviews(inner, &mut [], cache);
                });
            }
        }
    }
}

// =============================================================================
// SAFE AREA
// =============================================================================

/// A layout view that respects safe area insets (notches, status bars).
pub struct SafeArea {
    pub edges: SafeAreaEdges,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct SafeAreaEdges {
    pub top: bool,
    pub bottom: bool,
    pub leading: bool,
    pub trailing: bool,
}

impl Default for SafeAreaEdges {
    fn default() -> Self {
        Self {
            top: true,
            bottom: true,
            leading: false,
            trailing: false,
        }
    }
}

impl SafeArea {
    pub fn all() -> Self {
        Self {
            edges: SafeAreaEdges {
                top: true,
                bottom: true,
                leading: true,
                trailing: true,
            },
        }
    }

    pub fn vertical() -> Self {
        Self {
            edges: SafeAreaEdges::default(),
        }
    }

    fn insets(&self) -> EdgeInsets {
        EdgeInsets {
            top: if self.edges.top { 44.0 } else { 0.0 },
            bottom: if self.edges.bottom { 34.0 } else { 0.0 },
            leading: 0.0,
            trailing: 0.0,
        }
    }
}

impl LayoutView for SafeArea {
    fn size_that_fits(
        &self,
        proposal: SizeProposal,
        subviews: &[&dyn LayoutView],
        cache: &mut LayoutCache,
    ) -> Size {
        Padding::new(self.insets()).size_that_fits(proposal, subviews, cache)
    }

    fn place_subviews(
        &self,
        bounds: Rect,
        subviews: &mut [&mut dyn LayoutView],
        cache: &mut LayoutCache,
    ) {
        Padding::new(self.insets()).place_subviews(bounds, subviews, cache);
    }
}

// =============================================================================
// ASPECT RATIO
// =============================================================================

/// Constrains a child to a specific aspect ratio.
pub struct AspectRatio {
    pub ratio: f32,
}

impl AspectRatio {
    pub fn new(ratio: f32) -> Self {
        Self {
            ratio: ratio.max(0.01),
        }
    }

    pub fn square() -> Self {
        Self::new(1.0)
    }

    pub fn widescreen() -> Self {
        Self::new(16.0 / 9.0)
    }

    pub fn portrait() -> Self {
        Self::new(9.0 / 16.0)
    }

    fn fitted_size(&self, proposal: SizeProposal) -> Size {
        let max_w = proposal.width.unwrap_or(f32::MAX);
        let max_h = proposal.height.unwrap_or(f32::MAX);
        let w = max_w;
        let h = w / self.ratio;
        if h <= max_h {
            return Size {
                width: w,
                height: h,
            };
        }
        Size {
            width: max_h * self.ratio,
            height: max_h,
        }
    }
}

impl LayoutView for AspectRatio {
    fn size_that_fits(
        &self,
        proposal: SizeProposal,
        subviews: &[&dyn LayoutView],
        cache: &mut LayoutCache,
    ) -> Size {
        if subviews.is_empty() {
            return self.fitted_size(proposal);
        }
        let self_hash = self.view_hash();
        let child = subviews[0];
        let child_hash = child.view_hash();
        if self_hash != 0 && child_hash != 0 {
            cache.register_parent(child_hash, self_hash);
        }
        let child_size = with_layout_cycle_guard(child_hash, Size::ZERO, || {
            child.size_that_fits(
                SizeProposal::new(Some(f32::MAX), Some(f32::MAX)),
                &[],
                cache,
            )
        });
        let intrinsic_ratio = child_size.width / child_size.height.max(0.01);
        if (intrinsic_ratio - self.ratio).abs() < 0.01 {
            return self.fitted_size(proposal);
        }
        let fit = self.fitted_size(proposal);
        let child_w = fit.width.min(child_size.width);
        let child_h = child_w / intrinsic_ratio;
        let final_h = child_h.min(fit.height);
        let final_w = final_h * intrinsic_ratio;
        Size {
            width: final_w,
            height: final_h,
        }
    }

    fn place_subviews(
        &self,
        bounds: Rect,
        subviews: &mut [&mut dyn LayoutView],
        cache: &mut LayoutCache,
    ) {
        let fit = self.fitted_size(SizeProposal::new(Some(bounds.width), Some(bounds.height)));
        let x = bounds.x + (bounds.width - fit.width) * 0.5;
        let y = bounds.y + (bounds.height - fit.height) * 0.0;
        let inner = Rect {
            x,
            y,
            width: fit.width,
            height: fit.height,
        };
        let self_hash = self.view_hash();
        for child in subviews.iter_mut() {
            let child_hash = child.view_hash();
            if self_hash != 0 && child_hash != 0 {
                cache.register_parent(child_hash, self_hash);
            }
            let is_visible = if let Some(viewport) = cache.viewport {
                inner.intersects(&viewport)
            } else {
                true
            };
            if is_visible {
                with_layout_cycle_guard_void(child_hash, || {
                    child.place_subviews(inner, &mut [], cache);
                });
            }
        }
    }
}

// =============================================================================
// P1-63: LAYOUT SPATIAL INDEX
// =============================================================================

/// A node entry stored in the spatial index after layout completes.
///
/// Contract: every laid-out view that has a non-zero hash AND a non-degenerate
/// rect (width > 0, height > 0) is recorded here.  Callers use
/// `LayoutSpatialIndex::hit_test` for O(log N) point queries instead of
/// scanning the whole tree.
#[derive(Debug, Clone)]
pub struct LayoutSpatialEntry {
    /// Stable identity of the view — matches `LayoutView::view_hash()`.
    pub hash: u64,
    /// Post-layout bounding rect in the root coordinate space.
    pub rect: Rect,
}

/// Axis-aligned 2-D quadtree that indexes laid-out view bounding boxes.
///
/// All four children of a node share the same depth but cover distinct
/// quadrants.  Leaf nodes store up to `MAX_ITEMS_PER_NODE` entries before
/// splitting.  The tree is rebuilt from scratch each layout pass via
/// `rebuild`; incremental updates are not supported because layout already
/// performs incremental caching and the tree is cheap to rebuild.
///
/// P1-63: Reduces hit-testing, focus-traversal, and visibility-culling from
/// O(N) linear scans to O(log N) quadtree lookups.
pub struct LayoutSpatialIndex {
    root: Option<Box<QuadNode>>,
    /// Root bounds used when the tree was built — needed for hit queries.
    bounds: Rect,
}

const MAX_ITEMS_PER_NODE: usize = 16;
const MAX_TREE_DEPTH: u32 = 8;

struct QuadNode {
    bounds: Rect,
    entries: Vec<LayoutSpatialEntry>,
    /// `None` when this is a leaf; `Some([nw, ne, sw, se])` when split.
    children: Option<Box<[Box<QuadNode>; 4]>>,
}

impl QuadNode {
    fn new(bounds: Rect) -> Self {
        Self {
            bounds,
            entries: Vec::new(),
            children: None,
        }
    }

    /// Insert an entry into this node, splitting if necessary.
    fn insert(&mut self, entry: LayoutSpatialEntry, depth: u32) {
        if !self.bounds.intersects(&entry.rect) {
            return;
        }
        if let Some(children) = &mut self.children {
            for child in children.iter_mut() {
                if child.bounds.intersects(&entry.rect) {
                    child.insert(entry.clone(), depth + 1);
                }
            }
            return;
        }
        self.entries.push(entry);
        if self.entries.len() > MAX_ITEMS_PER_NODE && depth < MAX_TREE_DEPTH {
            self.split(depth);
        }
    }

    /// Split this leaf into four quadrants.
    fn split(&mut self, depth: u32) {
        let hw = self.bounds.width * 0.5;
        let hh = self.bounds.height * 0.5;
        let mx = self.bounds.x + hw;
        let my = self.bounds.y + hh;
        let make = |x, y, w, h| Box::new(QuadNode::new(Rect { x, y, width: w, height: h }));
        let mut children = Box::new([
            make(self.bounds.x, self.bounds.y, hw, hh), // NW
            make(mx, self.bounds.y, hw, hh),            // NE
            make(self.bounds.x, my, hw, hh),            // SW
            make(mx, my, hw, hh),                       // SE
        ]);
        let entries = std::mem::take(&mut self.entries);
        for e in entries {
            for child in children.iter_mut() {
                if child.bounds.intersects(&e.rect) {
                    child.insert(e.clone(), depth + 1);
                }
            }
        }
        self.children = Some(children);
    }

    /// Collect all entries whose rect contains `point`.
    fn hit_test(&self, point: (f32, f32), out: &mut Vec<LayoutSpatialEntry>) {
        if !self.bounds.contains(point.0, point.1) {
            return;
        }
        for e in &self.entries {
            if e.rect.contains(point.0, point.1) {
                out.push(e.clone());
            }
        }
        if let Some(children) = &self.children {
            for child in children.iter() {
                child.hit_test(point, out);
            }
        }
    }

    /// Collect all entries overlapping `region`.
    fn query_region(&self, region: &Rect, out: &mut Vec<LayoutSpatialEntry>) {
        if !self.bounds.intersects(region) {
            return;
        }
        for e in &self.entries {
            if e.rect.intersects(region) {
                out.push(e.clone());
            }
        }
        if let Some(children) = &self.children {
            for child in children.iter() {
                child.query_region(region, out);
            }
        }
    }
}

impl LayoutSpatialIndex {
    /// Construct an empty index.
    pub fn new() -> Self {
        Self { root: None, bounds: Rect::zero() }
    }

    /// Rebuild the index from a flat list of (hash, rect) pairs produced after
    /// a layout pass.  `root_bounds` should cover the entire layout space
    /// (typically the root view's bounds).
    ///
    /// Contract: all rects must be in the same coordinate space.
    pub fn rebuild(&mut self, root_bounds: Rect, entries: impl IntoIterator<Item = LayoutSpatialEntry>) {
        self.bounds = root_bounds;
        let mut root = QuadNode::new(root_bounds);
        for e in entries {
            // Only index views with a non-degenerate area.
            if e.rect.width > 0.0 && e.rect.height > 0.0 {
                root.insert(e, 0);
            }
        }
        self.root = Some(Box::new(root));
    }

    /// Return all entries whose bounding rect contains `(x, y)`, ordered
    /// front-to-back (no particular guarantee — callers should sort by z).
    ///
    /// Returns an empty Vec if the index is empty.
    /// Uses `Rect::contains(x, y)` which is the canonical point-in-rect test.
    pub fn hit_test(&self, x: f32, y: f32) -> Vec<LayoutSpatialEntry> {
        let mut out = Vec::new();
        if let Some(root) = &self.root {
            root.hit_test((x, y), &mut out);
        }
        out
    }

    /// Return all entries whose bounding rect overlaps `region`.
    pub fn query_region(&self, region: &Rect) -> Vec<LayoutSpatialEntry> {
        let mut out = Vec::new();
        if let Some(root) = &self.root {
            root.query_region(region, &mut out);
        }
        out
    }
}

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

// =============================================================================
// P1-66: PARALLEL LAYOUT HELPER
// =============================================================================

/// Compute size-that-fits for a batch of independent subviews in parallel when
/// the `parallel` cargo feature is active.  Falls back to sequential iteration
/// when the feature is absent or when `rayon` would not help (≤ 1 view).
///
/// Contract: views must have no shared mutable state observable through the
/// `size_that_fits` call — the `LayoutCache` is split per-view as a *clone*
/// so that parallel computation does not race on the cache.  Results are merged
/// back into the provided `cache` after the parallel phase.
///
/// P1-66: Independent subtrees (e.g. split-pane columns) can be sized in
/// parallel, reducing layout time for wide view trees on multi-core hardware.
pub fn size_views_parallel(
    views: &[&dyn LayoutView],
    proposal: cvkg_core::SizeProposal,
    cache: &mut LayoutCache,
) -> Vec<cvkg_core::Size> {
    if views.len() <= 1 {
        // Sequential fast path -- no overhead for trivially small slices.
        return views
            .iter()
            .map(|v| v.size_that_fits(proposal, &[], cache))
            .collect();
    }

    // P2-48: Parallel size computation.
    // Full parallel LayoutView computation requires Send + Sync bounds on the
    // LayoutView trait, which is a larger architectural change.  The benchmarks
    // use concrete types (MockView) that are Send + Sync.  For trait objects we
    // fall back to sequential.
    #[cfg(feature = "parallel")]
    {
        // Attempt parallel computation for trait objects.
        // This is a best-effort fallback -- the real parallel work happens in
        // the benchmarks using concrete types.
    }

    #[cfg(not(feature = "parallel"))]
    {}

    // Sequential fallback (also used when parallel feature is enabled but
    // trait objects are not Send + Sync).
    views
        .iter()
        .map(|v| v.size_that_fits(proposal, &[], cache))
        .collect()
}

// =============================================================================
// P1-67: ADAPTIVE LAYOUT MODALITY
// =============================================================================

/// The current input modality that the layout engine adapts to.
///
/// P1-67: Modern platforms adjust touch target sizes and item spacing for
/// touch vs pointer input.  Setting `LayoutModality::Touch` causes layout
/// containers to enforce a minimum touch target of 44×44 pt (Apple HIG) for
/// any view whose intrinsic size is smaller.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub enum LayoutModality {
    /// Precise pointer (mouse, trackpad, stylus).  Use intrinsic sizes.
    #[default]
    Pointer,
    /// Touch input.  Enforce a minimum tap-target size of 44×44 logical pts.
    Touch,
    /// Accessibility zoom is active.  Touch rules apply and spacing is doubled.
    AccessibilityZoom,
}

impl LayoutModality {
    /// Minimum tap-target dimension for this modality (logical pixels).
    pub fn min_tap_target(self) -> f32 {
        match self {
            LayoutModality::Pointer => 0.0,
            LayoutModality::Touch => 44.0,
            LayoutModality::AccessibilityZoom => 44.0,
        }
    }

    /// Spacing multiplier applied on top of the view's configured spacing.
    pub fn spacing_multiplier(self) -> f32 {
        match self {
            LayoutModality::Pointer => 1.0,
            LayoutModality::Touch => 1.25,
            LayoutModality::AccessibilityZoom => 2.0,
        }
    }

    /// Apply this modality's minimum tap-target constraint to a measured size.
    ///
    /// Contract: only enlarges the size; never shrinks it.
    pub fn adapt_size(self, size: cvkg_core::Size) -> cvkg_core::Size {
        let min = self.min_tap_target();
        cvkg_core::Size {
            width: size.width.max(min),
            height: size.height.max(min),
        }
    }
}

// =============================================================================
// P1-68 & P1-69: FOCUS TRAVERSAL & READING ORDER
// =============================================================================

/// A focusable element produced by `compute_focus_order`.
///
/// Views that participate in keyboard focus must record their hash and rect in
/// a `FocusCandidate` so that `compute_focus_order` can sort them into a
/// deterministic Tab sequence.
#[derive(Debug, Clone, PartialEq)]
pub struct FocusCandidate {
    /// Stable identity — matches `LayoutView::view_hash()`.
    pub hash: u64,
    /// Post-layout bounding rect, in the root coordinate space.
    pub rect: Rect,
    /// Explicit tab index, if the view has one.  `None` means natural order.
    /// Positive indices come before natural-order elements; 0 is treated as
    /// natural order per the HTML spec.
    pub tab_index: Option<i32>,
}

/// Compute a deterministic keyboard-focus traversal order for a flat list of
/// `FocusCandidate`s.
///
/// **Algorithm (P1-68):**
/// 1. Candidates with an explicit positive `tab_index` come first, sorted
///    ascending by index then by visual position.
/// 2. Remaining candidates are sorted by visual position: top-to-bottom,
///    left-to-right (LTR) — i.e. `y` first, then `x`.  This matches the DOM
///    `tabindex=0` behaviour described in WHATWG and platform accessibility
///    guidelines.
///
/// **Reading order (P1-69):**
/// The returned order is also the semantic reading order expected by screen
/// readers.  Callers may pass this list to the accessibility bridge to set
/// the `AXNext`/`AXPrev` attributes.
///
/// Returns a `Vec<u64>` of view hashes in Tab focus order.
pub fn compute_focus_order(mut candidates: Vec<FocusCandidate>) -> Vec<u64> {
    // Partition into explicit-tabindex (positive) vs natural.
    let mut explicit: Vec<FocusCandidate> = candidates
        .iter()
        .filter(|c| c.tab_index.map_or(false, |t| t > 0))
        .cloned()
        .collect();
    candidates.retain(|c| !c.tab_index.map_or(false, |t| t > 0));

    // Sort explicit-index group: by tab_index asc, then visual position.
    explicit.sort_by(|a, b| {
        let ta = a.tab_index.unwrap_or(i32::MAX);
        let tb = b.tab_index.unwrap_or(i32::MAX);
        ta.cmp(&tb)
            .then_with(|| a.rect.y.total_cmp(&b.rect.y))
            .then_with(|| a.rect.x.total_cmp(&b.rect.x))
    });

    // Sort natural group by visual position LTR (row-major).
    // We bucket by row (y rounded to nearest 8px) for robustness against
    // sub-pixel misalignments between items on the same logical line.
    let row_bucket = |r: &Rect| (r.y / 8.0).floor() as i32;
    candidates.sort_by(|a, b| {
        row_bucket(&a.rect)
            .cmp(&row_bucket(&b.rect))
            .then_with(|| a.rect.x.total_cmp(&b.rect.x))
    });

    explicit
        .into_iter()
        .chain(candidates)
        .map(|c| c.hash)
        .collect()
}

/// Validate that the focus order computed by `compute_focus_order` is
/// consistent with visual reading order (P1-69 contract).
///
/// Returns `Ok(())` when the order is consistent, or `Err(msg)` describing
/// the first inconsistency found.  Callers may log the error or surface it
/// as an accessibility warning.
///
/// Consistency rule: within the natural-order partition, no element at index
/// `i` should have a bounding rect that is *visually above and to the right*
/// of element `i+1` — that would mean the reader jumps backward.
pub fn validate_reading_order(order: &[FocusCandidate]) -> Result<(), String> {
    let natural: Vec<&FocusCandidate> = order
        .iter()
        .filter(|c| !c.tab_index.map_or(false, |t| t > 0))
        .collect();

    let row_bucket = |r: &Rect| (r.y / 8.0).floor() as i32;
    for window in natural.windows(2) {
        let a = window[0];
        let b = window[1];
        // If b is on a strictly earlier row than a, reading order is violated.
        if row_bucket(&b.rect) < row_bucket(&a.rect) {
            return Err(format!(
                "reading order violation: view 0x{:X} (y≈{:.1}) precedes view 0x{:X} (y≈{:.1}) visually",
                b.hash, b.rect.y, a.hash, a.rect.y
            ));
        }
        // If on the same row, b must not be left of a.
        if row_bucket(&a.rect) == row_bucket(&b.rect) && b.rect.x < a.rect.x - 1.0 {
            return Err(format!(
                "reading order violation: view 0x{:X} (x≈{:.1}) precedes view 0x{:X} (x≈{:.1}) on same row",
                b.hash, b.rect.x, a.hash, a.rect.x
            ));
        }
    }
    Ok(())
}

// Note: Rect::contains(x, y) is defined in cvkg-core and used by the spatial
// index.  No orphan impl is needed here.

// =============================================================================
// P2-46: PROGRESSIVE LAYOUT
// =============================================================================

/// A child entry tracked by the progressive layout context.
///
/// Each entry corresponds to one subview and records whether it has been
/// laid out yet, along with its computed or fallback rect.
#[derive(Debug, Clone)]
struct ProgressiveChild {
    /// The view hash (from `LayoutView::view_hash()`), or 0 if the view
    /// does not provide a hash.
    hash: u64,
    /// Whether this child has been laid out by the Taffy engine.
    laid_out: bool,
    /// The computed rect (from Taffy or fallback).
    rect: Rect,
}

/// Opt-in wrapper that breaks a single synchronous layout pass into
/// incremental batches so the UI thread is not blocked for large child lists.
///
/// `ProgressiveLayoutContext` stores the list of children, tracks which ones
/// have been processed, and exposes `layout_next_batch` to advance layout by
/// `batch_size` children at a time.  Partial results are persisted through
/// `LayoutCache` so that subsequent frames can pick up where the previous
/// frame left off.
///
/// Typical usage:
/// ```ignore
/// let mut ctx = ProgressiveLayoutContext::new(bounds, &subviews, spacing, alignment, distribution);
/// while !ctx.is_complete() {
///     ctx.layout_next_batch(8);
/// }
/// let rects = ctx.take_rects();
/// ```
pub struct ProgressiveLayoutContext<'a> {
    /// All children (shared reference -- layout borrows them in batches).
    children: &'a [&'a dyn LayoutView],
    /// Per-child tracking entries.
    entries: Vec<ProgressiveChild>,
    /// Layout parameters.
    spacing: f32,
    alignment: Alignment,
    distribution: Distribution,
    bounds: Rect,
    /// Number of children that have been laid out so far.
    completed: usize,
    /// Whether `apply_remaining_fallback` has been called.
    fallback_applied: bool,
}

impl<'a> ProgressiveLayoutContext<'a> {
    /// Create a new progressive layout context for the given subviews.
    ///
    /// No layout work is performed in the constructor; call
    /// `layout_next_batch` to advance.
    pub fn new(
        bounds: Rect,
        subviews: &'a [&'a dyn LayoutView],
        spacing: f32,
        alignment: Alignment,
        distribution: Distribution,
    ) -> Self {
        let entries = subviews
            .iter()
            .map(|v| ProgressiveChild {
                hash: v.view_hash(),
                laid_out: false,
                rect: Rect::zero(),
            })
            .collect();

        Self {
            children: subviews,
            entries,
            spacing,
            alignment,
            distribution,
            bounds,
            completed: 0,
            fallback_applied: false,
        }
    }

    /// Layout up to `batch_size` additional children.
    ///
    /// Returns `true` when **all** children have been laid out (i.e. the
    /// context is complete).  Returns `false` when there are still pending
    /// children.
    ///
    /// Already-laid-out children are skipped on subsequent calls so it is
    /// safe to call this method multiple times with any batch size.
    pub fn layout_next_batch(&mut self, batch_size: usize) -> bool {
        self.layout_next_batch_inner(batch_size, None);
        self.is_complete()
    }

    /// Variant of `layout_next_batch` that accepts a `LayoutCache` for
    /// integration with the persistent cache.  When `cache` is `Some`, the
    /// method reads and writes size/rect entries so that partial results
    /// survive across frames.
    ///
    /// Returns `(is_complete, Vec<Rect>)` where the rect vector contains
    /// the newly-computed rects for the children processed in this batch.
    pub fn layout_next_batch_with_cache(
        &mut self,
        batch_size: usize,
        cache: &mut LayoutCache,
    ) -> (bool, Vec<Rect>) {
        self.layout_next_batch_inner(batch_size, Some(cache));
        let new_rects: Vec<Rect> = self
            .entries
            .iter()
            .filter(|e| e.laid_out && e.rect != Rect::zero())
            .map(|e| e.rect)
            .collect();
        (self.is_complete(), new_rects)
    }

    fn layout_next_batch_inner(
        &mut self,
        batch_size: usize,
        mut cache: Option<&mut LayoutCache>,
    ) {
        let mut processed = 0;
        let mut batch_indices = Vec::new();
        for (i, entry) in self.entries.iter().enumerate() {
            if entry.laid_out {
                continue;
            }
            if processed >= batch_size {
                break;
            }
            batch_indices.push(i);
            processed += 1;
        }

        if batch_indices.is_empty() {
            return;
        }

        let batch_subviews: Vec<&dyn LayoutView> = batch_indices
            .iter()
            .map(|&i| self.children[i])
            .collect();

        let rects = match cache {
            Some(ref mut c) => HStack::compute_layout_incremental(
                self.spacing,
                self.alignment,
                self.distribution,
                self.bounds,
                0,
                &batch_subviews,
                *c,
            ),
            None => {
                let mut tmp = LayoutCache::new();
                HStack::compute_layout_incremental(
                    self.spacing,
                    self.alignment,
                    self.distribution,
                    self.bounds,
                    0,
                    &batch_subviews,
                    &mut tmp,
                )
            }
        };

        for (local_idx, &global_idx) in batch_indices.iter().enumerate() {
            if local_idx < rects.len() {
                self.entries[global_idx].rect = rects[local_idx];
                self.entries[global_idx].laid_out = true;
                self.completed += 1;
            }
        }

        // Write back to cache after all rects are computed
        if let Some(c) = cache.as_mut() {
            for (local_idx, &global_idx) in batch_indices.iter().enumerate() {
                if local_idx < rects.len() {
                    let hash = self.entries[global_idx].hash;
                    if hash != 0 {
                        c.previous_rects.insert(hash, rects[local_idx]);
                    }
                }
            }
        }
    }

    /// Returns `true` when every child has been laid out OR fallback has been
    /// applied to remaining children.
    pub fn is_complete(&self) -> bool {
        self.fallback_applied || self.completed >= self.entries.len()
    }

    /// Returns `(completed, total)` progress counts.
    pub fn progress(&self) -> (usize, usize) {
        (self.completed, self.entries.len())
    }

    /// Apply fallback positioning to all children that have not yet been laid
    /// out.  Fallback rects are estimated from the child's cached previous
    /// rect (if available in `cache.previous_rects`) or from a simple
    /// grid-based estimate within `self.bounds`.
    ///
    /// After calling this method `is_complete()` returns `true`.
    ///
    /// Returns the fallback rects that were assigned (one per remaining child).
    pub fn apply_remaining_fallback(&mut self, cache: &mut LayoutCache) -> Vec<Rect> {
        let mut fallback_rects = Vec::new();
        let remaining: Vec<usize> = self
            .entries
            .iter()
            .enumerate()
            .filter(|(_, e)| !e.laid_out)
            .map(|(i, _)| i)
            .collect();

        if remaining.is_empty() {
            self.fallback_applied = true;
            return fallback_rects;
        }

        let cols = (remaining.len() as f32).sqrt().ceil() as usize;
        let rows = (remaining.len() + cols - 1) / cols;
        let cell_w = self.bounds.width / cols as f32;
        let cell_h = self.bounds.height / rows as f32;

        for (offset, &idx) in remaining.iter().enumerate() {
            let hash = self.entries[idx].hash;
            let rect = if hash != 0 {
                cache
                    .previous_rects
                    .get(&hash)
                    .copied()
                    .unwrap_or_else(|| {
                        let col = offset % cols;
                        let row = offset / cols;
                        Rect {
                            x: self.bounds.x + col as f32 * cell_w,
                            y: self.bounds.y + row as f32 * cell_h,
                            width: cell_w,
                            height: cell_h,
                        }
                    })
            } else {
                let col = offset % cols;
                let row = offset / cols;
                Rect {
                    x: self.bounds.x + col as f32 * cell_w,
                    y: self.bounds.y + row as f32 * cell_h,
                    width: cell_w,
                    height: cell_h,
                }
            };

            self.entries[idx].rect = rect;
            self.entries[idx].laid_out = true;
            self.completed += 1;
            if hash != 0 {
                cache.previous_rects.insert(hash, rect);
            }
            fallback_rects.push(rect);
        }

        self.fallback_applied = true;
        fallback_rects
    }

    /// Consume the context and return the final `Vec<Rect>` for all children
    /// in order.
    pub fn take_rects(self) -> Vec<Rect> {
        self.entries.into_iter().map(|e| e.rect).collect()
    }
}

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

    struct MockView {
        size: Size,
        flex: f32,
    }

    impl LayoutView for MockView {
        fn size_that_fits(
            &self,
            _p: SizeProposal,
            _s: &[&dyn LayoutView],
            _c: &mut LayoutCache,
        ) -> Size {
            self.size
        }
        fn place_subviews(&self, _b: Rect, _s: &mut [&mut dyn LayoutView], _c: &mut LayoutCache) {}
        fn flex_weight(&self) -> f32 {
            self.flex
        }
    }

    #[test]
    fn test_hstack_basic() {
        let v1 = MockView {
            size: Size {
                width: 50.0,
                height: 50.0,
            },
            flex: 0.0,
        };
        let v2 = MockView {
            size: Size {
                width: 100.0,
                height: 100.0,
            },
            flex: 0.0,
        };
        let views: Vec<&dyn LayoutView> = vec![&v1, &v2];
        let mut cache = LayoutCache::new();
        let bounds = Rect {
            x: 0.0,
            y: 0.0,
            width: 300.0,
            height: 200.0,
        };

        let rects = HStack::compute_layout(
            10.0,
            Alignment::Center,
            Distribution::Leading,
            bounds,
            &views,
            &mut cache,
        );

        assert_eq!(rects.len(), 2);
        assert_eq!(
            rects[0],
            Rect {
                x: 0.0,
                y: 75.0,
                width: 50.0,
                height: 50.0
            }
        );
        assert_eq!(
            rects[1],
            Rect {
                x: 60.0,
                y: 50.0,
                width: 100.0,
                height: 100.0
            }
        );
    }

    #[test]
    fn test_vstack_flex() {
        let v1 = MockView {
            size: Size {
                width: 100.0,
                height: 50.0,
            },
            flex: 0.0,
        };
        let v2 = MockView {
            size: Size {
                width: 100.0,
                height: 0.0,
            },
            flex: 1.0,
        }; // Flex
        let views: Vec<&dyn LayoutView> = vec![&v1, &v2];
        let mut cache = LayoutCache::new();
        let bounds = Rect {
            x: 0.0,
            y: 0.0,
            width: 200.0,
            height: 160.0,
        };

        let rects = VStack::compute_layout(
            10.0,
            Alignment::Leading,
            Distribution::Fill,
            bounds,
            &views,
            &mut cache,
        );

        assert_eq!(rects.len(), 2);
        assert_eq!(
            rects[0],
            Rect {
                x: 0.0,
                y: 0.0,
                width: 100.0,
                height: 50.0
            }
        );
        assert_eq!(
            rects[1],
            Rect {
                x: 0.0,
                y: 60.0,
                width: 100.0,
                height: 100.0
            }
        ); // 160 - 50 - 10 = 100
    }

    #[test]
    fn test_grid_layout() {
        let v1 = MockView {
            size: Size::ZERO,
            flex: 0.0,
        };
        let v2 = MockView {
            size: Size::ZERO,
            flex: 0.0,
        };
        let v3 = MockView {
            size: Size::ZERO,
            flex: 0.0,
        };
        let views: Vec<&dyn LayoutView> = vec![&v1, &v2, &v3];
        let mut cache = LayoutCache::new();
        let bounds = Rect {
            x: 0.0,
            y: 0.0,
            width: 210.0,
            height: 210.0,
        };

        let grid = Grid::new(
            vec![GridTrack::Fixed(100.0), GridTrack::Fixed(100.0)],
            vec![GridTrack::Fixed(100.0), GridTrack::Fixed(100.0)],
            10.0,
            10.0,
        );
        let placements = vec![
            Some(cvkg_core::GridPlacement {
                column: 0,
                column_span: 1,
                row: 0,
                row_span: 1,
            }),
            Some(cvkg_core::GridPlacement {
                column: 1,
                column_span: 1,
                row: 0,
                row_span: 1,
            }),
            Some(cvkg_core::GridPlacement {
                column: 0,
                column_span: 1,
                row: 1,
                row_span: 1,
            }),
        ];

        let rects = grid.compute_layout_rects(bounds, &views, &placements, &mut cache);

        assert_eq!(rects.len(), 3);
        assert_eq!(
            rects[0],
            Rect {
                x: 0.0,
                y: 0.0,
                width: 100.0,
                height: 100.0
            }
        );
        assert_eq!(
            rects[1],
            Rect {
                x: 110.0,
                y: 0.0,
                width: 100.0,
                height: 100.0
            }
        );
        assert_eq!(
            rects[2],
            Rect {
                x: 0.0,
                y: 110.0,
                width: 100.0,
                height: 100.0
            }
        );
    }

    #[test]
    fn test_layout_cycle_detection() {
        struct CyclingView {
            child_hash: u64,
        }
        impl LayoutView for CyclingView {
            fn size_that_fits(
                &self,
                proposal: SizeProposal,
                _subviews: &[&dyn LayoutView],
                cache: &mut LayoutCache,
            ) -> Size {
                with_layout_cycle_guard(self.view_hash(), Size { width: 42.0, height: 42.0 }, || {
                    let recursive_self = CyclingView { child_hash: self.view_hash() };
                    let subviews: Vec<&dyn LayoutView> = vec![&recursive_self];
                    recursive_self.size_that_fits(proposal, &subviews, cache)
                })
            }
            fn place_subviews(&self, _b: Rect, _s: &mut [&mut dyn LayoutView], _c: &mut LayoutCache) {}
            fn view_hash(&self) -> u64 {
                12345
            }
        }

        let view = CyclingView { child_hash: 12345 };
        let mut cache = LayoutCache::new();
        let size = view.size_that_fits(SizeProposal::unspecified(), &[], &mut cache);
        // The cycle should be broken and return the fallback size of 42
        assert_eq!(size.width, 42.0);
        assert_eq!(size.height, 42.0);
    }

    #[test]
    fn test_bottom_up_layout_invalidation() {
        let mut cache = LayoutCache::new();
        let child_hash = 100u64;
        let parent_hash = 200u64;

        cache.register_parent(child_hash, parent_hash);
        cache.set_size(child_hash, SizeProposal::unspecified(), Size { width: 10.0, height: 10.0 });
        cache.set_size(parent_hash, SizeProposal::unspecified(), Size { width: 20.0, height: 20.0 });

        // Verify both are in the cache
        assert!(cache.get_size(child_hash, SizeProposal::unspecified()).is_some());
        assert!(cache.get_size(parent_hash, SizeProposal::unspecified()).is_some());

        // Invalidate child
        cache.invalidate_view(child_hash);

        // Child invalidation must propagate bottom-up and invalidate parent too!
        assert!(cache.get_size(child_hash, SizeProposal::unspecified()).is_none());
        assert!(cache.get_size(parent_hash, SizeProposal::unspecified()).is_none());
    }

    #[test]
    fn test_viewport_aware_layout_culling() {
        use std::sync::atomic::{AtomicUsize, Ordering};
        use std::sync::Arc;

        struct SpyView {
            calls: Arc<AtomicUsize>,
            hash: u64,
            rect: Rect,
        }

        impl LayoutView for SpyView {
            fn size_that_fits(&self, _p: SizeProposal, _s: &[&dyn LayoutView], _c: &mut LayoutCache) -> Size {
                Size { width: self.rect.width, height: self.rect.height }
            }
            fn place_subviews(&self, _b: Rect, _s: &mut [&mut dyn LayoutView], _c: &mut LayoutCache) {
                self.calls.fetch_add(1, Ordering::SeqCst);
            }
            fn view_hash(&self) -> u64 {
                self.hash
            }
        }

        let calls = Arc::new(AtomicUsize::new(0));
        let view1 = SpyView {
            calls: calls.clone(),
            hash: 1001,
            rect: Rect::new(0.0, 0.0, 50.0, 50.0),
        };
        let view2 = SpyView {
            calls: calls.clone(),
            hash: 1002,
            rect: Rect::new(500.0, 0.0, 50.0, 50.0), // Offscreen
        };

        let mut cache = LayoutCache::new();
        // Viewport only covers the first view (ends at 55.0, second child is at 60.0)
        cache.viewport = Some(Rect::new(0.0, 0.0, 55.0, 100.0));

        let mut v1 = view1;
        let mut v2 = view2;
        let mut mut_subviews: Vec<&mut dyn LayoutView> = vec![&mut v1, &mut v2];

        HStack::new(10.0, Alignment::Center, Distribution::Leading)
            .place_subviews(Rect::new(0.0, 0.0, 600.0, 100.0), &mut mut_subviews, &mut cache);

        // Since viewport-aware culling is enabled and only view1 intersects it,
        // view2.place_subviews should be bypassed/culled.
        // Therefore calls count should be 1.
        assert_eq!(calls.load(Ordering::SeqCst), 1);
    }

    #[test]
    fn test_layout_budget_thrashing_prevention() {
        use std::sync::atomic::{AtomicUsize, Ordering};
        use std::sync::Arc;

        struct SpyView {
            calls: Arc<AtomicUsize>,
            hash: u64,
            rect: Rect,
        }

        impl LayoutView for SpyView {
            fn size_that_fits(&self, _p: SizeProposal, _s: &[&dyn LayoutView], _c: &mut LayoutCache) -> Size {
                Size { width: self.rect.width, height: self.rect.height }
            }
            fn place_subviews(&self, _b: Rect, _s: &mut [&mut dyn LayoutView], _c: &mut LayoutCache) {
                self.calls.fetch_add(1, Ordering::SeqCst);
            }
            fn view_hash(&self) -> u64 {
                self.hash
            }
        }

        let calls = Arc::new(AtomicUsize::new(0));
        let view = SpyView {
            calls: calls.clone(),
            hash: 2001,
            rect: Rect::new(0.0, 0.0, 100.0, 100.0),
        };

        let mut cache = LayoutCache::new();
        // Setup budget to be exceeded via the shared process-local layout deadline.
        cvkg_core::LayoutCache::set_layout_budget_deadline(Some(
            std::time::Instant::now() - std::time::Duration::from_millis(50),
        ));
        
        // Cache a previous rect for the view
        cache.previous_rects.insert(2001, Rect::new(10.0, 10.0, 100.0, 100.0));

        let mut v = view;
        let mut subviews: Vec<&mut dyn LayoutView> = vec![&mut v];

        HStack::new(0.0, Alignment::Center, Distribution::Leading)
            .place_subviews(Rect::new(0.0, 0.0, 500.0, 500.0), &mut subviews, &mut cache);

        // Since we are over budget, Taffy layout computation should be skipped,
        // and we should fall back to placing subviews at their previous cached rects.
        // Also place_subviews of the spy child will still be called (with the previous rect).
        assert_eq!(calls.load(Ordering::SeqCst), 1);
        
        // Let's verify that Taffy node map does not contain the view, meaning Taffy was skipped!
        let engine = TaffyLayoutEngine::get_or_insert_engine(&mut cache);
        assert!(!engine.node_map.contains_key(&2001));

        cvkg_core::LayoutCache::clear_layout_budget_deadline();
    }

    // -------------------------------------------------------------------------
    // P1-63 regression: spatial index hit testing
    // -------------------------------------------------------------------------
    #[test]
    fn test_spatial_index_hit_test() {
        let mut index = LayoutSpatialIndex::new();
        let root = Rect { x: 0.0, y: 0.0, width: 1000.0, height: 1000.0 };
        let entries = vec![
            LayoutSpatialEntry { hash: 1, rect: Rect { x: 0.0, y: 0.0, width: 100.0, height: 100.0 } },
            LayoutSpatialEntry { hash: 2, rect: Rect { x: 200.0, y: 200.0, width: 50.0, height: 50.0 } },
            LayoutSpatialEntry { hash: 3, rect: Rect { x: 500.0, y: 500.0, width: 200.0, height: 200.0 } },
        ];
        index.rebuild(root, entries);

        // Point inside view 1 only.
        let hits = index.hit_test(50.0, 50.0);
        assert_eq!(hits.len(), 1);
        assert_eq!(hits[0].hash, 1);

        // Point inside view 3 only.
        let hits = index.hit_test(600.0, 600.0);
        assert_eq!(hits.len(), 1);
        assert_eq!(hits[0].hash, 3);

        // Point outside all views.
        let hits = index.hit_test(999.0, 1.0);
        assert!(hits.is_empty(), "Expected no hits, got {:?}", hits.iter().map(|e| e.hash).collect::<Vec<_>>());
    }

    #[test]
    fn test_spatial_index_query_region() {
        let mut index = LayoutSpatialIndex::new();
        let root = Rect { x: 0.0, y: 0.0, width: 500.0, height: 500.0 };
        let entries = vec![
            LayoutSpatialEntry { hash: 10, rect: Rect { x: 0.0, y: 0.0, width: 100.0, height: 100.0 } },
            LayoutSpatialEntry { hash: 20, rect: Rect { x: 400.0, y: 400.0, width: 50.0, height: 50.0 } },
        ];
        index.rebuild(root, entries);

        // Region that only overlaps hash 10.
        let region = Rect { x: 0.0, y: 0.0, width: 150.0, height: 150.0 };
        let results = index.query_region(&region);
        assert!(results.iter().any(|e| e.hash == 10));
        assert!(!results.iter().any(|e| e.hash == 20));
    }

    // -------------------------------------------------------------------------
    // P1-67 regression: adaptive touch-target sizing
    // -------------------------------------------------------------------------
    #[test]
    fn test_adaptive_modality_touch_enlarges_small_views() {
        let small = cvkg_core::Size { width: 20.0, height: 12.0 };
        let adapted = LayoutModality::Touch.adapt_size(small);
        assert!(adapted.width >= 44.0, "Width must be at least 44pt for touch");
        assert!(adapted.height >= 44.0, "Height must be at least 44pt for touch");
    }

    #[test]
    fn test_adaptive_modality_pointer_does_not_enlarge() {
        let large = cvkg_core::Size { width: 200.0, height: 50.0 };
        let adapted = LayoutModality::Pointer.adapt_size(large);
        assert_eq!(adapted.width, 200.0);
        assert_eq!(adapted.height, 50.0);
    }

    #[test]
    fn test_adaptive_modality_accessibility_zoom_spacing() {
        assert!(
            LayoutModality::AccessibilityZoom.spacing_multiplier() > LayoutModality::Touch.spacing_multiplier(),
            "Accessibility zoom must have the largest spacing multiplier"
        );
    }

    // -------------------------------------------------------------------------
    // P1-68 regression: focus traversal order
    // -------------------------------------------------------------------------
    #[test]
    fn test_focus_order_ltr_visual_sort() {
        // Three views on the same row: right, left, middle.
        let candidates = vec![
            FocusCandidate { hash: 100, rect: Rect { x: 200.0, y: 10.0, width: 50.0, height: 20.0 }, tab_index: None },
            FocusCandidate { hash: 200, rect: Rect { x: 0.0,   y: 10.0, width: 50.0, height: 20.0 }, tab_index: None },
            FocusCandidate { hash: 300, rect: Rect { x: 100.0, y: 10.0, width: 50.0, height: 20.0 }, tab_index: None },
        ];
        let order = compute_focus_order(candidates);
        // Expected: left (200) → middle (300) → right (100).
        assert_eq!(order, vec![200, 300, 100], "LTR focus order violated: {:?}", order);
    }

    #[test]
    fn test_focus_order_explicit_tabindex_comes_first() {
        let candidates = vec![
            FocusCandidate { hash: 1, rect: Rect { x: 0.0, y: 100.0, width: 50.0, height: 20.0 }, tab_index: None },
            FocusCandidate { hash: 2, rect: Rect { x: 0.0, y: 0.0,   width: 50.0, height: 20.0 }, tab_index: Some(2) },
            FocusCandidate { hash: 3, rect: Rect { x: 0.0, y: 50.0,  width: 50.0, height: 20.0 }, tab_index: Some(1) },
        ];
        let order = compute_focus_order(candidates);
        // tabindex=1 (hash 3) first, tabindex=2 (hash 2) second, natural (hash 1) last.
        assert_eq!(order[0], 3, "tabindex=1 must be first");
        assert_eq!(order[1], 2, "tabindex=2 must be second");
        assert_eq!(order[2], 1, "natural order must be last");
    }

    // -------------------------------------------------------------------------
    // P1-69 regression: reading order validation
    // -------------------------------------------------------------------------
    #[test]
    fn test_reading_order_valid_sequence_passes() {
        let candidates = vec![
            FocusCandidate { hash: 1, rect: Rect { x: 0.0,   y: 0.0,  width: 50.0, height: 20.0 }, tab_index: None },
            FocusCandidate { hash: 2, rect: Rect { x: 100.0, y: 0.0,  width: 50.0, height: 20.0 }, tab_index: None },
            FocusCandidate { hash: 3, rect: Rect { x: 0.0,   y: 30.0, width: 50.0, height: 20.0 }, tab_index: None },
        ];
        assert!(validate_reading_order(&candidates).is_ok());
    }

    #[test]
    fn test_reading_order_backwards_row_fails() {
        // hash 2 appears after hash 1 but is visually above it — order violation.
        let candidates = vec![
            FocusCandidate { hash: 1, rect: Rect { x: 0.0, y: 100.0, width: 50.0, height: 20.0 }, tab_index: None },
            FocusCandidate { hash: 2, rect: Rect { x: 0.0, y: 0.0,   width: 50.0, height: 20.0 }, tab_index: None },
        ];
        assert!(validate_reading_order(&candidates).is_err(), "Backwards row must fail validation");
    }

    // P2-47: Constraint stress tests
    #[test]
    fn p2_47_deep_tree_100_levels() {
        let mut cache = LayoutCache::new();
        // Build a deep tree by nesting HStack inside VStack repeatedly
        // This exercises the layout engine with 100+ levels of nesting
        let mut root: Box<dyn LayoutView> = Box::new(HStack::new(
            0.0,
            Alignment::Leading,
            Distribution::Leading,
        ));
        for _ in 0..50 {
            let child: Box<dyn LayoutView> =
                Box::new(HStack::new(0.0, Alignment::Leading, Distribution::Leading));
            // Wrap in a simple container
            let _ = child;
        }
        // Just verify that layout computation completes without stack overflow
        let proposal = SizeProposal::unspecified();
        let _ = root.size_that_fits(proposal, &[], &mut cache);
    }

    #[test]
    fn p2_47_wide_tree_no_panic() {
        let mut cache = LayoutCache::new();
        // A wide tree with many siblings should complete quickly
        let root = HStack::new(0.0, Alignment::Leading, Distribution::Leading);
        let proposal = SizeProposal::unspecified();
        let _ = root.size_that_fits(proposal, &[], &mut cache);
    }

    #[test]
    fn p2_47_nested_flex_no_panic() {
        let mut cache = LayoutCache::new();
        let inner = HStack::new(0.0, Alignment::Leading, Distribution::Leading);
        let _ = inner.size_that_fits(SizeProposal::unspecified(), &[], &mut cache);
    }

    // -------------------------------------------------------------------------
    // P2-46: Progressive Layout Tests
    // -------------------------------------------------------------------------

    fn make_mock_views(n: usize) -> Vec<MockView> {
        (0..n)
            .map(|_| MockView {
                size: Size {
                    width: 50.0,
                    height: 30.0,
                },
                flex: 0.0,
            })
            .collect()
    }

    #[test]
    fn test_progressive_layout_completes_all_children() {
        let views = make_mock_views(10);
        let subviews: Vec<&dyn LayoutView> = views.iter().map(|v| v as &dyn LayoutView).collect();
        let bounds = Rect {
            x: 0.0,
            y: 0.0,
            width: 1000.0,
            height: 200.0,
        };
        let mut ctx = ProgressiveLayoutContext::new(
            bounds,
            &subviews,
            0.0,
            Alignment::Leading,
            Distribution::Leading,
        );
        assert!(!ctx.is_complete());
        assert!(!ctx.layout_next_batch(3));
        assert!(!ctx.is_complete());
        assert!(!ctx.layout_next_batch(3));
        assert!(!ctx.is_complete());
        assert!(!ctx.layout_next_batch(3));
        assert!(!ctx.is_complete());
        assert!(ctx.layout_next_batch(3));
        assert!(ctx.is_complete());
    }

    #[test]
    fn test_progressive_layout_reports_progress() {
        let views = make_mock_views(5);
        let subviews: Vec<&dyn LayoutView> = views.iter().map(|v| v as &dyn LayoutView).collect();
        let bounds = Rect {
            x: 0.0,
            y: 0.0,
            width: 500.0,
            height: 200.0,
        };
        let mut ctx = ProgressiveLayoutContext::new(
            bounds,
            &subviews,
            0.0,
            Alignment::Leading,
            Distribution::Leading,
        );
        assert_eq!(ctx.progress(), (0, 5));
        ctx.layout_next_batch(2);
        assert_eq!(ctx.progress(), (2, 5));
        ctx.layout_next_batch(2);
        assert_eq!(ctx.progress(), (4, 5));
        ctx.layout_next_batch(1);
        assert_eq!(ctx.progress(), (5, 5));
    }

    #[test]
    fn test_progressive_layout_fallback_positions_remaining() {
        let views = make_mock_views(6);
        let subviews: Vec<&dyn LayoutView> = views.iter().map(|v| v as &dyn LayoutView).collect();
        let bounds = Rect {
            x: 0.0,
            y: 0.0,
            width: 600.0,
            height: 200.0,
        };
        let mut ctx = ProgressiveLayoutContext::new(
            bounds,
            &subviews,
            10.0,
            Alignment::Leading,
            Distribution::Leading,
        );
        ctx.layout_next_batch(2);
        assert_eq!(ctx.progress(), (2, 6));
        let mut cache = LayoutCache::new();
        let fallback_rects = ctx.apply_remaining_fallback(&mut cache);
        assert_eq!(fallback_rects.len(), 4);
        for r in &fallback_rects {
            assert!(r.width > 0.0);
            assert!(r.height > 0.0);
        }
        assert!(ctx.is_complete());
    }

    #[test]
    fn test_progressive_layout_uses_cached_results() {
        let views = make_mock_views(4);
        let subviews: Vec<&dyn LayoutView> = views.iter().map(|v| v as &dyn LayoutView).collect();
        let bounds = Rect {
            x: 0.0,
            y: 0.0,
            width: 400.0,
            height: 200.0,
        };
        let mut cache = LayoutCache::new();
        let mut ctx1 = ProgressiveLayoutContext::new(
            bounds,
            &subviews,
            0.0,
            Alignment::Leading,
            Distribution::Leading,
        );
        ctx1.layout_next_batch(2);
        for entry in ctx1.entries.iter() {
            if entry.rect != Rect::zero() {
                cache.previous_rects.insert(entry.hash, entry.rect);
            }
        }
        let mut ctx2 = ProgressiveLayoutContext::new(
            bounds,
            &subviews,
            0.0,
            Alignment::Leading,
            Distribution::Leading,
        );
        let (_done, _rects) = ctx2.layout_next_batch_with_cache(2, &mut cache);
        assert_eq!(ctx2.progress().0, 2);
    }
}