Skip to content

armgit / moli

Public Imported from GitHub
0

Best headless browser for AI agents. Lite, Fast, High-Compatibility. Built in Rust

50.3 KB
Raw Blame
use std::{collections::HashMap, fmt::Debug, hash::Hash, num::NonZeroU32, sync::Arc};

use style::Atom;
use taffy::{Cache, DetailedLayoutInfo, Layout, Point, Style};

use crate::{
    LayoutCssImageReference, LayoutElementSemantics, LayoutError, LayoutPoint, LayoutPseudo,
    LayoutResolvedGridTracks, LayoutScrollbarAxis, LayoutScrollbarColors, LayoutScrollbarGutter,
    LayoutScrollbarWidth, ResolvedLayoutStyle, inline::InlineFormattingContext,
    replaced::ReplacedContext, style::LayoutOverflowMode,
};

/// Dense identifier scoped to exactly one [`LayoutWorld`].
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub struct LayoutBoxId(u32);

impl LayoutBoxId {
    pub fn index(self) -> usize {
        self.0 as usize
    }

    pub(crate) fn from_index(index: usize) -> Self {
        Self(u32::try_from(index).expect("one layout pass exceeded the u32 box limit"))
    }

    pub(crate) fn to_taffy(self) -> taffy::NodeId {
        taffy::NodeId::from(self.index())
    }

    pub(crate) fn from_taffy(node: taffy::NodeId) -> Self {
        Self::from_index(usize::from(node))
    }
}

/// Browser-level box role used by construction, diagnostics, and dispatch.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum LayoutBoxKind {
    PrincipalBlock,
    PrincipalFlowRoot,
    PrincipalFlex,
    PrincipalInlineFlex,
    PrincipalGrid,
    PrincipalInlineGrid,
    PrincipalInline,
    PrincipalInlineBlock,
    ListItem,
    InlineListItem,
    TableWrapper,
    InlineTableWrapper,
    TableCaption,
    TableRowGroup,
    TableHeaderGroup,
    TableFooterGroup,
    TableColumnGroup,
    TableColumn,
    TableRow,
    TableCell,
    FormControl,
    LineBreak,
    Replaced,
    AnonymousBlock,
    AnonymousFlexItem,
    AnonymousGridItem,
    AnonymousTableWrapper,
    AnonymousTableRowGroup,
    AnonymousTableRow,
    AnonymousTableCell,
    InlineContinuation,
    Text,
    PseudoMarker,
    PseudoBefore,
    PseudoAfter,
}

impl LayoutBoxKind {
    pub(crate) const fn is_text(self) -> bool {
        matches!(self, Self::Text)
    }

    /// Whether this box is one of CSS Display's internal table boxes.
    ///
    /// A table wrapper and its caption are deliberately excluded. Properties
    /// such as `aspect-ratio` apply to those boxes, but not to row groups,
    /// rows, columns, or cells. Anonymous repair boxes obey the same used-value
    /// boundary as their source-backed counterparts.
    pub(crate) const fn is_internal_table_box(self) -> bool {
        matches!(
            self,
            Self::TableRowGroup
                | Self::TableHeaderGroup
                | Self::TableFooterGroup
                | Self::TableColumnGroup
                | Self::TableColumn
                | Self::TableRow
                | Self::TableCell
                | Self::AnonymousTableRowGroup
                | Self::AnonymousTableRow
                | Self::AnonymousTableCell
        )
    }

    pub(crate) const fn debug_name(self) -> &'static str {
        match self {
            Self::PrincipalBlock => "principal-block",
            Self::PrincipalFlowRoot => "principal-flow-root",
            Self::PrincipalFlex => "principal-flex",
            Self::PrincipalInlineFlex => "principal-inline-flex",
            Self::PrincipalGrid => "principal-grid",
            Self::PrincipalInlineGrid => "principal-inline-grid",
            Self::PrincipalInline => "principal-inline",
            Self::PrincipalInlineBlock => "principal-inline-block",
            Self::ListItem => "list-item",
            Self::InlineListItem => "inline-list-item",
            Self::TableWrapper => "table-wrapper",
            Self::InlineTableWrapper => "inline-table-wrapper",
            Self::TableCaption => "table-caption",
            Self::TableRowGroup => "table-row-group",
            Self::TableHeaderGroup => "table-header-group",
            Self::TableFooterGroup => "table-footer-group",
            Self::TableColumnGroup => "table-column-group",
            Self::TableColumn => "table-column",
            Self::TableRow => "table-row",
            Self::TableCell => "table-cell",
            Self::FormControl => "form-control",
            Self::LineBreak => "line-break",
            Self::Replaced => "replaced",
            Self::AnonymousBlock => "anonymous-block",
            Self::AnonymousFlexItem => "anonymous-flex-item",
            Self::AnonymousGridItem => "anonymous-grid-item",
            Self::AnonymousTableWrapper => "anonymous-table-wrapper",
            Self::AnonymousTableRowGroup => "anonymous-table-row-group",
            Self::AnonymousTableRow => "anonymous-table-row",
            Self::AnonymousTableCell => "anonymous-table-cell",
            Self::InlineContinuation => "inline-continuation",
            Self::Text => "text",
            Self::PseudoMarker => "pseudo-marker",
            Self::PseudoBefore => "pseudo-before",
            Self::PseudoAfter => "pseudo-after",
        }
    }
}

/// Why a box with no DOM source was introduced by box construction.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum LayoutAnonymousReason {
    MixedFlowInlineRun,
    InlineSplitContinuation,
    FlexTextRun,
    GridTextRun,
    MissingTableParent,
    MissingTableRowGroup,
    MissingTableRow,
    MissingTableCell,
    FormControlContent,
}

impl LayoutAnonymousReason {
    pub(crate) const fn debug_name(self) -> &'static str {
        match self {
            Self::MixedFlowInlineRun => "mixed-flow-inline-run",
            Self::InlineSplitContinuation => "inline-split-continuation",
            Self::FlexTextRun => "flex-text-run",
            Self::GridTextRun => "grid-text-run",
            Self::MissingTableParent => "missing-table-parent",
            Self::MissingTableRowGroup => "missing-table-row-group",
            Self::MissingTableRow => "missing-table-row",
            Self::MissingTableCell => "missing-table-cell",
            Self::FormControlContent => "form-control-content",
        }
    }
}

/// Stable indication that construction succeeded but a later numeric/paint phase is deferred.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum LayoutCapabilityDiagnostic {
    ListMarkerStyleFallback,
    TextProjectionDeferred,
    PositionedStaticPositionDeferred,
    IntrinsicSizingKeywordDeferred,
    GridTemplateModeDeferred,
    GeneratedContentUnsupported,
}

/// Hypothetical position contributed by an out-of-flow placeholder in one IFC.
///
/// Coordinates are relative to the formatting-context owner's border box.
/// The record exists only for the current layout pass and is consumed before
/// Taffy's rounding traversal.
#[derive(Clone, Copy, Debug, PartialEq)]
pub(crate) struct InlineStaticPosition {
    pub(crate) owner: LayoutBoxId,
    pub(crate) point: Point<f32>,
    pub(crate) inline_level: bool,
}

impl LayoutCapabilityDiagnostic {
    pub const fn code(self) -> &'static str {
        match self {
            Self::ListMarkerStyleFallback => "list-marker-style-fallback",
            Self::TextProjectionDeferred => "text-projection-deferred",
            Self::PositionedStaticPositionDeferred => "positioned-static-position-deferred",
            Self::IntrinsicSizingKeywordDeferred => "intrinsic-sizing-keyword-deferred",
            Self::GridTemplateModeDeferred => "grid-template-mode-deferred",
            Self::GeneratedContentUnsupported => "generated-content-unsupported",
        }
    }
}

/// One box in the pass-local CSS box tree.
#[derive(Debug)]
pub struct LayoutBox<N> {
    pub(crate) source: Option<N>,
    pub(crate) owner: Option<N>,
    pub(crate) pseudo: Option<LayoutPseudo>,
    pub(crate) source_label: String,
    pub(crate) owner_label: Option<String>,
    pub(crate) element_semantics: Option<LayoutElementSemantics>,
    pub(crate) anonymous_reason: Option<LayoutAnonymousReason>,
    pub(crate) capability_diagnostics: Vec<LayoutCapabilityDiagnostic>,
    pub(crate) kind: LayoutBoxKind,
    /// Parent in the source-backed LayoutObject hierarchy, before anonymous
    /// box normalization and block-in-inline promotion.
    ///
    /// Chromium keeps this ancestry on its LayoutObject tree while fragment
    /// construction handles block-in-inline placement. Moli's normalized
    /// `parent` tree is intentionally different, so containing-block and
    /// CSSOM ancestry retain their own first-class relation here.
    pub(crate) structural_parent: Option<LayoutBoxId>,
    /// Parent in the normalized formatting tree, including anonymous wrappers
    /// and block-in-inline promotion.
    pub(crate) parent: Option<LayoutBoxId>,
    pub(crate) children: Vec<LayoutBoxId>,
    /// Parent used by the numeric layout algorithm.
    ///
    /// This differs from `parent` for absolute/fixed boxes whose containing
    /// block is not their direct box-tree parent.
    pub(crate) layout_parent: Option<LayoutBoxId>,
    pub(crate) layout_children: Vec<LayoutBoxId>,
    /// CSS containing block selected from the construction tree.
    ///
    /// This can differ from `layout_parent` when an absolutely positioned box
    /// is contained by a flattened inline box. `layout_parent` remains a real
    /// numeric-tree node; this field retains the semantic containing block.
    pub(crate) positioned_containing_block: Option<LayoutBoxId>,
    /// Static position emitted by the shared IFC's out-of-flow placeholder.
    pub(crate) inline_static_position: Option<InlineStaticPosition>,
    pub(crate) style: ResolvedLayoutStyle,
    pub(crate) text: Option<Arc<str>>,
    pub(crate) text_selection: Option<crate::LayoutTextSelection>,
    /// Shared text/inline layout owned by this formatting-context root.
    pub(crate) inline_layout: Option<InlineFormattingContext>,
    /// Outermost IFC that consumes this box as a flattened or atomic item.
    pub(crate) inline_context_owner: Option<LayoutBoxId>,
    /// Text, `<br>`, and non-atomic inline boxes are laid out by their owner IFC
    /// and therefore do not enter Taffy's child traversal independently.
    pub(crate) inline_flattened: bool,
    /// `list-style-position: outside` marker laid out beside, rather than in,
    /// the list item's principal inline formatting context.
    pub(crate) outside_list_marker: bool,
    /// Current source-owned scroll offset sampled at construction time.
    pub(crate) scroll_offset: LayoutPoint,
    /// Pass-local natural sizing retained once at box construction.
    pub(crate) replaced_context: Option<ReplacedContext>,
    pub(crate) replaced_image: Option<crate::LayoutImageResource>,
    pub(crate) css_images: crate::source::LayoutCssImageResources,
    /// Suppresses ordinary per-box border paint for parts participating in a
    /// collapsed table. Their authored borders have already entered the table
    /// owner's conflict-resolution grid.
    pub(crate) collapsed_table_border_part: bool,
    pub(crate) inline_formatting_context: bool,
    /// One-based index into the owning world's compact numeric cache storage.
    cache_slot: Option<NonZeroU32>,
    pub(crate) table_measure_cache: Option<Box<crate::table::TableMeasureCache>>,
    pub(crate) unrounded_layout: Layout,
    pub(crate) final_layout: Layout,
}

/// Layout-only initial containing block.
///
/// The CSS viewport is not a DOM box, but Taffy needs a real root node so the
/// root element can remain auto-height while fixed and root-level absolute
/// boxes resolve against the viewport rather than the root element's box.
#[derive(Debug)]
pub(crate) struct ViewportLayoutState {
    pub(crate) children: Vec<LayoutBoxId>,
    pub(crate) style: Style<Atom>,
    pub(crate) cache: Cache,
    pub(crate) unrounded_layout: Layout,
    pub(crate) final_layout: Layout,
}

/// CSS box whose overflow supplies the viewport scrolling mechanism.
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub(crate) enum ViewportDefiningBox {
    #[default]
    Root,
    Body(LayoutBoxId),
}

/// Independent style for the viewport scrolling mechanism.
///
/// Box construction copies overflow from the selected root/body box, while
/// scrollbar appearance continues to come from the root. The selected body's
/// authored style remains untouched; its exact box identity tells later
/// phases that those overflow properties have already transferred here.
#[derive(Clone, Copy, Debug, PartialEq)]
pub(crate) struct ViewportScrollPolicy {
    pub(crate) defining_box: ViewportDefiningBox,
    pub(crate) effective_overflow: [LayoutOverflowMode; 2],
    scrollbar_style: ViewportScrollbarStyle,
    embedder_allows_user_scroll: bool,
    embedder_allows_scrollbar_controls: bool,
    revealed_scrollbar_x: bool,
    revealed_scrollbar_y: bool,
}

/// Authored scrollbar geometry remains available even when the embedder
/// suppresses the viewport controls. Stable gutters use this hypothetical
/// thickness independently of the actual control state.
#[derive(Clone, Copy, Debug, PartialEq)]
struct ViewportScrollbarStyle {
    width: LayoutScrollbarWidth,
    gutter: LayoutScrollbarGutter,
    colors: Option<LayoutScrollbarColors>,
    horizontal_writing_mode: bool,
}

impl Default for ViewportScrollPolicy {
    fn default() -> Self {
        Self::new(
            ViewportDefiningBox::Root,
            [LayoutOverflowMode::Auto; 2],
            LayoutScrollbarWidth::Auto,
            LayoutScrollbarGutter::Auto,
            None,
            true,
            false,
        )
    }
}

impl ViewportScrollPolicy {
    pub(crate) const fn new(
        defining_box: ViewportDefiningBox,
        effective_overflow: [LayoutOverflowMode; 2],
        scrollbar_width: LayoutScrollbarWidth,
        scrollbar_gutter: LayoutScrollbarGutter,
        scrollbar_colors: Option<LayoutScrollbarColors>,
        horizontal_writing_mode: bool,
        user_scrolling_disabled: bool,
    ) -> Self {
        Self {
            defining_box,
            effective_overflow,
            scrollbar_style: ViewportScrollbarStyle {
                width: scrollbar_width,
                gutter: scrollbar_gutter,
                colors: scrollbar_colors,
                horizontal_writing_mode,
            },
            embedder_allows_user_scroll: !user_scrolling_disabled,
            embedder_allows_scrollbar_controls: !user_scrolling_disabled,
            revealed_scrollbar_x: false,
            revealed_scrollbar_y: false,
        }
    }

    pub(crate) const fn defining_body(self) -> Option<LayoutBoxId> {
        match self.defining_box {
            ViewportDefiningBox::Root => None,
            ViewportDefiningBox::Body(body) => Some(body),
        }
    }

    pub(crate) fn prepare_scrollbar_layout(&mut self, scrollbars_hidden: bool) {
        let allowed = !scrollbars_hidden && self.allows_scrollbar_controls();
        self.revealed_scrollbar_x =
            allowed && self.effective_overflow[0] == LayoutOverflowMode::Scroll;
        self.revealed_scrollbar_y =
            allowed && self.effective_overflow[1] == LayoutOverflowMode::Scroll;
    }

    pub(crate) fn reveal_auto_scrollbar(
        &mut self,
        axis: LayoutScrollbarAxis,
        overflowing: bool,
    ) -> bool {
        if !overflowing
            || !self.allows_scrollbar_controls()
            || self.overflow_mode(axis) != LayoutOverflowMode::Auto
        {
            return false;
        }
        let revealed = match axis {
            LayoutScrollbarAxis::Horizontal => &mut self.revealed_scrollbar_x,
            LayoutScrollbarAxis::Vertical => &mut self.revealed_scrollbar_y,
        };
        if *revealed {
            return false;
        }
        *revealed = true;
        true
    }

    pub(crate) const fn overflow_mode(self, axis: LayoutScrollbarAxis) -> LayoutOverflowMode {
        match axis {
            LayoutScrollbarAxis::Horizontal => self.effective_overflow[0],
            LayoutScrollbarAxis::Vertical => self.effective_overflow[1],
        }
    }

    pub(crate) fn establishes_scroll_container(self) -> bool {
        self.effective_overflow
            .into_iter()
            .any(LayoutOverflowMode::creates_scroll_container)
    }

    pub(crate) fn allows_user_scroll(self, axis: LayoutScrollbarAxis) -> bool {
        self.embedder_allows_user_scroll && self.overflow_mode(axis).allows_user_scroll()
    }

    pub(crate) fn clips_overflow(self) -> bool {
        self.effective_overflow
            .into_iter()
            .any(|mode| mode != LayoutOverflowMode::Visible)
    }

    pub(crate) fn has_scrollbar(self, axis: LayoutScrollbarAxis, overflowing: bool) -> bool {
        if !self.allows_scrollbar_controls() {
            return false;
        }
        match self.overflow_mode(axis) {
            LayoutOverflowMode::Scroll => true,
            LayoutOverflowMode::Auto => overflowing,
            LayoutOverflowMode::Visible | LayoutOverflowMode::Clip | LayoutOverflowMode::Hidden => {
                false
            }
        }
    }

    pub(crate) const fn scrollbar_control_thickness(self) -> f32 {
        if self.allows_scrollbar_controls() {
            self.scrollbar_style.width.thickness()
        } else {
            0.0
        }
    }

    pub(crate) const fn scrollbar_colors(self) -> Option<LayoutScrollbarColors> {
        self.scrollbar_style.colors
    }

    const fn allows_scrollbar_controls(self) -> bool {
        self.embedder_allows_scrollbar_controls
            && !matches!(self.scrollbar_style.width, LayoutScrollbarWidth::None)
    }

    pub(crate) fn scrollbar_gutter_thickness(self, axis: LayoutScrollbarAxis) -> f32 {
        let insets = self.scrollbar_layout_insets();
        match axis {
            LayoutScrollbarAxis::Horizontal => insets.top + insets.bottom,
            LayoutScrollbarAxis::Vertical => insets.left + insets.right,
        }
    }

    pub(crate) fn scrollbar_leading_gutter_thickness(self, axis: LayoutScrollbarAxis) -> f32 {
        let insets = self.scrollbar_layout_insets();
        match axis {
            LayoutScrollbarAxis::Horizontal => insets.top,
            LayoutScrollbarAxis::Vertical => insets.left,
        }
    }

    pub(crate) fn scrollbar_layout_insets(self) -> taffy::Rect<f32> {
        let actual = self.actual_scrollbar_insets();
        let reserved = self.stable_gutter_insets();
        taffy::Rect {
            left: actual.left.max(reserved.left),
            right: actual.right.max(reserved.right),
            top: actual.top.max(reserved.top),
            bottom: actual.bottom.max(reserved.bottom),
        }
    }

    fn actual_scrollbar_insets(self) -> taffy::Rect<f32> {
        let thickness = self.scrollbar_control_thickness();
        taffy::Rect {
            left: 0.0,
            // Chromium keeps the viewport's vertical control on the physical
            // right, including RTL and vertical writing modes.
            right: if self.revealed_scrollbar_y {
                thickness
            } else {
                0.0
            },
            top: 0.0,
            bottom: if self.revealed_scrollbar_x {
                thickness
            } else {
                0.0
            },
        }
    }

    fn stable_gutter_insets(self) -> taffy::Rect<f32> {
        let mut insets = taffy::Rect::ZERO;
        if self.scrollbar_style.gutter == LayoutScrollbarGutter::Auto {
            return insets;
        }
        let thickness = self.scrollbar_style.width.thickness();
        let both_edges = self.scrollbar_style.gutter == LayoutScrollbarGutter::StableBothEdges;
        if self.scrollbar_style.horizontal_writing_mode
            && self.effective_overflow[1].creates_scroll_container()
        {
            insets.right = thickness;
            if both_edges {
                insets.left = thickness;
            }
        } else if !self.scrollbar_style.horizontal_writing_mode
            && self.effective_overflow[0].creates_scroll_container()
        {
            insets.bottom = thickness;
            if both_edges {
                insets.top = thickness;
            }
        }
        insets
    }
}

impl Default for ViewportLayoutState {
    fn default() -> Self {
        Self {
            children: Vec::new(),
            style: Style::default(),
            cache: Cache::new(),
            unrounded_layout: Layout::with_order(0),
            final_layout: Layout::with_order(0),
        }
    }
}

impl<N> LayoutBox<N> {
    pub fn kind(&self) -> LayoutBoxKind {
        self.kind
    }

    pub fn source(&self) -> Option<N>
    where
        N: Copy,
    {
        self.source
    }

    pub fn owner(&self) -> Option<N>
    where
        N: Copy,
    {
        self.owner
    }

    pub fn pseudo(&self) -> Option<LayoutPseudo> {
        self.pseudo
    }

    pub fn element_semantics(&self) -> Option<&LayoutElementSemantics> {
        self.element_semantics.as_ref()
    }

    pub fn anonymous_reason(&self) -> Option<LayoutAnonymousReason> {
        self.anonymous_reason
    }

    pub fn capability_diagnostics(&self) -> &[LayoutCapabilityDiagnostic] {
        &self.capability_diagnostics
    }

    pub fn source_label(&self) -> &str {
        &self.source_label
    }

    pub fn children(&self) -> &[LayoutBoxId] {
        &self.children
    }

    /// Returns the parent in the source-backed LayoutObject hierarchy.
    pub fn structural_parent(&self) -> Option<LayoutBoxId> {
        self.structural_parent
    }

    pub fn style(&self) -> &ResolvedLayoutStyle {
        &self.style
    }

    pub fn text(&self) -> Option<&str> {
        self.text.as_deref()
    }

    pub fn establishes_inline_formatting_context(&self) -> bool {
        self.inline_formatting_context
    }

    pub fn final_layout(&self) -> Layout {
        self.final_layout
    }

    pub(crate) fn is_replaced(&self) -> bool {
        self.element_semantics
            .as_ref()
            .is_some_and(LayoutElementSemantics::is_replaced)
    }

    /// Resolve the used ratio at the layout-node boundary, after both authored
    /// style and natural replaced-element sizing are available.
    pub(crate) fn resolved_aspect_ratio(&self) -> Option<taffy::ResolvedAspectRatio> {
        if self.kind.is_internal_table_box() {
            return None;
        }
        let natural_ratio = self
            .replaced_context
            .and_then(|context| context.inherent_ratio());
        self.style.resolved_aspect_ratio(natural_ratio)
    }
}

/// Entire short-lived sidecar used for one construction/layout demand.
#[derive(Debug)]
pub struct LayoutWorld<N>
where
    N: Copy + Debug + Eq + Hash,
{
    pub(crate) boxes: Vec<LayoutBox<N>>,
    /// Pass-local numeric caches, created only for boxes with actual stores.
    /// Flattened text boxes need no empty Taffy measurement arrays.
    pub(crate) box_caches: Vec<Cache>,
    /// Winning collapsed-table edges, computed and consumed in this pass.
    /// Empty slots are not embedded in boxes that do not own a table.
    pub(crate) collapsed_table_borders: HashMap<LayoutBoxId, crate::table::CollapsedTableBorders>,
    /// Used Grid tracks for actual owners. Their canonical result is frozen
    /// for CSSOM before this pass-local map is released.
    pub(crate) resolved_grid_tracks: HashMap<LayoutBoxId, LayoutResolvedGridTracks>,
    /// Native track positions and names read by Taffy's out-of-flow pass.
    pub(crate) native_grid_details: HashMap<LayoutBoxId, DetailedLayoutInfo<Atom>>,
    pub(crate) source_mapping: HashMap<N, LayoutBoxId>,
    pub(crate) display_contents_mapping: HashMap<N, Vec<LayoutBoxId>>,
    pub(crate) root: LayoutBoxId,
    /// The root is the document element only for a complete document source.
    /// Subtree and synthetic sources still use the same internal root slot.
    pub(crate) root_is_document_element: bool,
    pub(crate) quirks_mode: style::context::QuirksMode,
    pub(crate) environment: crate::LayoutEnvironment,
    pub(crate) viewport_scroll_policy: ViewportScrollPolicy,
    pub(crate) viewport_layout: ViewportLayoutState,
    pub(crate) css_image_references: Vec<LayoutCssImageReference<N>>,
    /// Full numeric measurement retains baselines without publishing layouts.
    pub(crate) measure_baselines: bool,
    /// The active table cell's used height need not be a percentage guarantee.
    pub(crate) table_cell_percentage_height: Option<(LayoutBoxId, bool)>,
    numeric_layout_tracking: bool,
    numeric_layout_touched: Vec<LayoutBoxId>,
    numeric_layout_touched_marks: Vec<bool>,
}

impl<N> LayoutWorld<N>
where
    N: Copy + Debug + Eq + Hash,
{
    pub(crate) fn new(root: LayoutBox<N>, root_is_document_element: bool) -> Self {
        Self {
            boxes: vec![root],
            box_caches: Vec::new(),
            collapsed_table_borders: HashMap::new(),
            resolved_grid_tracks: HashMap::new(),
            native_grid_details: HashMap::new(),
            source_mapping: HashMap::new(),
            display_contents_mapping: HashMap::new(),
            root: LayoutBoxId::from_index(0),
            root_is_document_element,
            quirks_mode: style::context::QuirksMode::NoQuirks,
            environment: crate::LayoutEnvironment::default(),
            viewport_scroll_policy: ViewportScrollPolicy::default(),
            viewport_layout: ViewportLayoutState::default(),
            css_image_references: Vec::new(),
            measure_baselines: false,
            table_cell_percentage_height: None,
            numeric_layout_tracking: false,
            numeric_layout_touched: Vec::new(),
            numeric_layout_touched_marks: vec![false],
        }
    }

    pub(crate) fn clear_layout_caches(&mut self, id: LayoutBoxId) {
        let layout_box = &mut self.boxes[id.index()];
        if let Some(slot) = layout_box.cache_slot {
            self.box_caches[(slot.get() - 1) as usize].clear();
        }
        if let Some(cache) = &mut layout_box.table_measure_cache {
            cache.clear();
        }
    }

    pub(crate) fn numeric_cache(&mut self, id: LayoutBoxId) -> Option<&mut Cache> {
        let slot = self.boxes.get(id.index())?.cache_slot?;
        self.box_caches.get_mut((slot.get() - 1) as usize)
    }

    pub(crate) fn numeric_cache_mut(&mut self, id: LayoutBoxId) -> &mut Cache {
        let slot = if let Some(slot) = self.boxes[id.index()].cache_slot {
            slot
        } else {
            if self.box_caches.is_empty() {
                // Bound the first allocation without scanning construction
                // boxes or reserving caches for boxes that may never store.
                self.box_caches.reserve_exact(self.boxes.len().min(4));
            }
            let slot = u32::try_from(self.box_caches.len())
                .ok()
                .and_then(|index| index.checked_add(1))
                .and_then(NonZeroU32::new)
                .expect("one layout pass exceeded the u32 cache limit");
            self.box_caches.push(Cache::new());
            self.boxes[id.index()].cache_slot = Some(slot);
            slot
        };
        &mut self.box_caches[(slot.get() - 1) as usize]
    }

    pub fn root(&self) -> LayoutBoxId {
        self.root
    }

    pub(crate) fn is_viewport_defining_body(&self, id: LayoutBoxId) -> bool {
        self.viewport_scroll_policy.defining_body() == Some(id)
    }

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

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

    pub fn box_by_id(&self, id: LayoutBoxId) -> Option<&LayoutBox<N>> {
        self.boxes.get(id.index())
    }

    pub fn source_box(&self, source: N) -> Option<LayoutBoxId> {
        self.source_mapping.get(&source).copied()
    }

    pub(crate) fn box_by_id_mut(&mut self, id: LayoutBoxId) -> Option<&mut LayoutBox<N>> {
        self.boxes.get_mut(id.index())
    }

    pub(crate) fn viewport_taffy_node(&self) -> taffy::NodeId {
        taffy::NodeId::from(self.boxes.len())
    }

    pub(crate) fn is_viewport_taffy_node(&self, node: taffy::NodeId) -> bool {
        usize::from(node) == self.boxes.len()
    }

    /// Resolves every numeric layout origin in one preorder forest traversal.
    ///
    /// Calling the former single-box helper for every output box repeatedly
    /// walked shared ancestor chains and became quadratic for a deep document.
    /// The intrusive child links below avoid one allocation per parent in a
    /// deeply nested tree while still covering detached numeric roots.
    pub(crate) fn global_layout_origins(&self) -> Vec<LayoutPoint> {
        let count = self.boxes.len();
        let mut first_child = vec![None; count];
        let mut next_sibling = vec![None; count];
        let mut roots = Vec::new();
        for index in (0..count).rev() {
            let id = LayoutBoxId::from_index(index);
            if let Some(parent) = self.boxes[index].layout_parent {
                assert!(
                    parent.index() < count,
                    "numeric layout parent must belong to this world"
                );
                next_sibling[index] = first_child[parent.index()];
                first_child[parent.index()] = Some(id);
            } else {
                roots.push(id);
            }
        }

        let mut origins = vec![LayoutPoint::ZERO; count];
        let mut visited = vec![false; count];
        let mut stack = roots
            .into_iter()
            .map(|root| (root, LayoutPoint::ZERO))
            .collect::<Vec<_>>();
        let mut resolved = 0usize;
        while let Some((id, parent_origin)) = stack.pop() {
            assert!(
                !visited[id.index()],
                "numeric layout parents must form an acyclic forest"
            );
            visited[id.index()] = true;
            resolved = resolved.saturating_add(1);
            let location = self.boxes[id.index()].final_layout.location;
            let origin =
                LayoutPoint::new(parent_origin.x + location.x, parent_origin.y + location.y);
            origins[id.index()] = origin;

            let mut child = first_child[id.index()];
            while let Some(child_id) = child {
                stack.push((child_id, origin));
                child = next_sibling[child_id.index()];
            }
        }
        assert_eq!(
            resolved, count,
            "numeric layout parents must form an acyclic forest"
        );
        origins
    }

    pub(crate) fn begin_numeric_layout_tracking(&mut self) {
        assert!(
            !self.numeric_layout_tracking,
            "numeric layout tracking cannot be nested"
        );
        assert!(self.numeric_layout_touched.is_empty());
        self.numeric_layout_touched_marks
            .resize(self.boxes.len(), false);
        self.numeric_layout_tracking = true;
    }

    pub(crate) fn record_numeric_layout_touch(&mut self, id: LayoutBoxId) {
        if !self.numeric_layout_tracking || self.numeric_layout_touched_marks[id.index()] {
            return;
        }
        self.numeric_layout_touched_marks[id.index()] = true;
        self.numeric_layout_touched.push(id);
    }

    pub(crate) fn finish_numeric_layout_tracking(&mut self) -> Vec<LayoutBoxId> {
        assert!(
            self.numeric_layout_tracking,
            "numeric layout tracking must be active"
        );
        self.numeric_layout_tracking = false;
        let touched = std::mem::take(&mut self.numeric_layout_touched);
        for id in touched.iter().copied() {
            self.numeric_layout_touched_marks[id.index()] = false;
        }
        touched
    }

    pub(crate) fn allocate(&mut self, layout_box: LayoutBox<N>) -> LayoutBoxId {
        let id = LayoutBoxId::from_index(self.boxes.len());
        self.boxes.push(layout_box);
        self.numeric_layout_touched_marks.push(false);
        id
    }

    pub(crate) fn map_source(&mut self, source: N, id: LayoutBoxId) {
        self.source_mapping.entry(source).or_insert(id);
    }

    pub(crate) fn map_display_contents_source(&mut self, source: N, child_boxes: &[LayoutBoxId]) {
        self.display_contents_mapping
            .entry(source)
            .or_default()
            .extend_from_slice(child_boxes);
    }

    pub(crate) fn is_document_element(&self, id: LayoutBoxId) -> bool {
        self.root_is_document_element && id == self.root
    }

    pub(crate) fn replace_children(
        &mut self,
        parent: LayoutBoxId,
        children: Vec<LayoutBoxId>,
    ) -> Result<(), LayoutError> {
        let Some(parent_box) = self.box_by_id_mut(parent) else {
            return Err(LayoutError::InvalidBoxReference {
                index: parent.index(),
            });
        };
        parent_box.children = children.clone();
        for child in children {
            let Some(child_box) = self.box_by_id_mut(child) else {
                return Err(LayoutError::InvalidBoxReference {
                    index: child.index(),
                });
            };
            // Raw source ownership is recorded before normalization. Boxes
            // synthesized by normalization have no earlier owner, so their
            // first formatting attachment is also their structural parent.
            child_box.structural_parent.get_or_insert(parent);
            child_box.parent = Some(parent);
        }
        Ok(())
    }

    /// Attaches one newly synthesized box through the same ownership seam as
    /// construction-time children.
    pub(crate) fn append_synthesized_child(
        &mut self,
        parent: LayoutBoxId,
        child: LayoutBoxId,
    ) -> Result<(), LayoutError> {
        let Some(parent_box) = self.box_by_id(parent) else {
            return Err(LayoutError::InvalidBoxReference {
                index: parent.index(),
            });
        };
        let mut children = parent_box.children.clone();
        children.push(child);
        self.replace_children(parent, children)
    }

    /// Records source/LayoutObject ownership before formatting normalization
    /// is allowed to wrap or promote any child.
    ///
    /// The first owner deliberately wins. A split inline returns its promoted
    /// block in an ancestor's child stream later, but that reattachment must
    /// not erase the inline LayoutObject that originally owned the block.
    pub(crate) fn record_structural_children(
        &mut self,
        parent: LayoutBoxId,
        children: &[LayoutBoxId],
    ) -> Result<(), LayoutError> {
        if self.box_by_id(parent).is_none() {
            return Err(LayoutError::InvalidBoxReference {
                index: parent.index(),
            });
        }
        for child in children {
            let Some(child_box) = self.box_by_id_mut(*child) else {
                return Err(LayoutError::InvalidBoxReference {
                    index: child.index(),
                });
            };
            child_box.structural_parent.get_or_insert(parent);
        }
        Ok(())
    }

    pub(crate) fn compact_reachable(&mut self) {
        let mut reachable = vec![false; self.boxes.len()];
        let mut stack = vec![self.root];
        while let Some(id) = stack.pop() {
            if std::mem::replace(&mut reachable[id.index()], true) {
                continue;
            }
            stack.extend(self.boxes[id.index()].children.iter().copied());
        }

        // Most trees do not discard any construction boxes. Their IDs already
        // form the final dense mapping; keep the pass-local allocation instead
        // of moving every box and rebuilding every child vector unchanged.
        if reachable.iter().all(|is_reachable| *is_reachable) {
            self.display_contents_mapping
                .retain(|_, ids| !ids.is_empty());
            return;
        }

        let mut remap = vec![None; self.boxes.len()];
        let mut next_index = 0;
        for (index, is_reachable) in reachable.iter().copied().enumerate() {
            if is_reachable {
                remap[index] = Some(LayoutBoxId::from_index(next_index));
                next_index += 1;
            }
        }

        let mut compacted = Vec::with_capacity(next_index);
        for (index, mut layout_box) in self.boxes.drain(..).enumerate() {
            if !reachable[index] {
                continue;
            }
            layout_box.structural_parent = layout_box
                .structural_parent
                .and_then(|parent| remap[parent.index()]);
            layout_box.parent = layout_box.parent.and_then(|parent| remap[parent.index()]);
            layout_box.children = layout_box
                .children
                .into_iter()
                .filter_map(|child| remap[child.index()])
                .collect();
            compacted.push(layout_box);
        }
        self.boxes = compacted;
        self.root = remap[self.root.index()].expect("the layout root is always reachable");
        self.source_mapping.retain(|_, id| {
            let Some(remapped) = remap[id.index()] else {
                return false;
            };
            *id = remapped;
            true
        });
        self.display_contents_mapping.retain(|_, ids| {
            *ids = ids.iter().filter_map(|id| remap[id.index()]).collect();
            !ids.is_empty()
        });
    }

    /// Validates graph ownership invariants without relying on allocator IDs.
    pub fn validate_invariants(&self) -> Result<(), LayoutError> {
        let mut reachable = vec![false; self.boxes.len()];
        let mut stack = vec![self.root];
        while let Some(id) = stack.pop() {
            let Some(layout_box) = self.box_by_id(id) else {
                return Err(LayoutError::InvalidBoxReference { index: id.index() });
            };
            if std::mem::replace(&mut reachable[id.index()], true) {
                return Err(LayoutError::SourceCycle {
                    source_label: layout_box.source_label.clone(),
                });
            }
            for child in layout_box.children.iter().rev().copied() {
                let Some(child_box) = self.box_by_id(child) else {
                    return Err(LayoutError::InvalidBoxReference {
                        index: child.index(),
                    });
                };
                if child_box.parent != Some(id) {
                    return Err(LayoutError::InvalidBoxReference {
                        index: child.index(),
                    });
                }
                stack.push(child);
            }
        }
        if let Some(index) = reachable.iter().position(|reachable| !reachable) {
            return Err(LayoutError::InvalidBoxReference { index });
        }
        if let Some(body) = self.viewport_scroll_policy.defining_body() {
            let Some(body_box) = self.box_by_id(body) else {
                return Err(LayoutError::InvalidBoxReference {
                    index: body.index(),
                });
            };
            if body == self.root
                || !body_box
                    .element_semantics()
                    .is_some_and(|element| element.is_html_element("body"))
            {
                return Err(LayoutError::source_contract(
                    &body_box.source_label,
                    "viewport-defining body identity must name a principal HTML body box",
                ));
            }
        }
        for (index, layout_box) in self.boxes.iter().enumerate() {
            let id = LayoutBoxId::from_index(index);
            self.validate_box_provenance(id, layout_box)?;
            self.validate_table_parentage(id, layout_box)?;
        }
        Ok(())
    }

    fn validate_box_provenance(
        &self,
        id: LayoutBoxId,
        layout_box: &LayoutBox<N>,
    ) -> Result<(), LayoutError> {
        if id == self.root {
            if layout_box.structural_parent.is_some() {
                return Err(LayoutError::InvalidBoxReference { index: id.index() });
            }
        } else if layout_box.structural_parent.is_none() {
            return Err(LayoutError::InvalidBoxReference { index: id.index() });
        }
        if let Some(parent) = layout_box.structural_parent
            && (parent == id || self.box_by_id(parent).is_none())
        {
            return Err(LayoutError::InvalidBoxReference {
                index: parent.index(),
            });
        }
        if let Some(source) = layout_box.source {
            if layout_box.owner.is_some()
                || layout_box.pseudo.is_some()
                || layout_box.anonymous_reason.is_some()
            {
                return Err(LayoutError::source_contract(
                    &layout_box.source_label,
                    "a source-backed box cannot also be pseudo/anonymous-owned",
                ));
            }
            if self.source_mapping.get(&source) != Some(&id) {
                return Err(LayoutError::source_contract(
                    &layout_box.source_label,
                    "source mapping does not point to its source-backed box",
                ));
            }
        }
        if layout_box.pseudo.is_some()
            && (layout_box.source.is_some() || layout_box.owner.is_none())
        {
            return Err(LayoutError::source_contract(
                &layout_box.source_label,
                "a pseudo box must have an owner and no DOM source",
            ));
        }
        if layout_box.anonymous_reason.is_some()
            && (layout_box.source.is_some() || layout_box.owner.is_none())
        {
            return Err(LayoutError::source_contract(
                &layout_box.source_label,
                "an anonymous box must have an owner and no DOM source",
            ));
        }
        Ok(())
    }

    fn validate_table_parentage(
        &self,
        id: LayoutBoxId,
        layout_box: &LayoutBox<N>,
    ) -> Result<(), LayoutError> {
        let role = table_role(layout_box.style.display());
        if id != self.root
            && let Some(role) = role
        {
            let parent = layout_box
                .parent
                .and_then(|parent| self.box_by_id(parent))
                .and_then(|parent| table_role(parent.style.display()));
            let valid = match role {
                TableInvariantRole::Root => true,
                TableInvariantRole::Caption
                | TableInvariantRole::RowGroup
                | TableInvariantRole::ColumnGroup => parent == Some(TableInvariantRole::Root),
                TableInvariantRole::Column => matches!(
                    parent,
                    Some(TableInvariantRole::Root | TableInvariantRole::ColumnGroup)
                ),
                TableInvariantRole::Row => parent == Some(TableInvariantRole::RowGroup),
                TableInvariantRole::Cell => parent == Some(TableInvariantRole::Row),
            };
            if !valid {
                return Err(LayoutError::source_contract(
                    &layout_box.source_label,
                    format!(
                        "table role {} has invalid parent role {}",
                        role.debug_name(),
                        parent.map_or("non-table", TableInvariantRole::debug_name)
                    ),
                ));
            }
        }

        let children_are_valid = match role {
            Some(TableInvariantRole::Root) => layout_box.children.iter().all(|child| {
                self.box_by_id(*child)
                    .and_then(|child| table_role(child.style.display()))
                    .is_some_and(TableInvariantRole::is_direct_root_child)
            }),
            Some(TableInvariantRole::RowGroup) => layout_box.children.iter().all(|child| {
                self.box_by_id(*child).is_some_and(|child| {
                    table_role(child.style.display()) == Some(TableInvariantRole::Row)
                })
            }),
            Some(TableInvariantRole::Row) => layout_box.children.iter().all(|child| {
                self.box_by_id(*child).is_some_and(|child| {
                    table_role(child.style.display()) == Some(TableInvariantRole::Cell)
                })
            }),
            Some(TableInvariantRole::ColumnGroup) => layout_box.children.iter().all(|child| {
                self.box_by_id(*child).is_some_and(|child| {
                    table_role(child.style.display()) == Some(TableInvariantRole::Column)
                })
            }),
            Some(TableInvariantRole::Column) => layout_box.children.is_empty(),
            Some(TableInvariantRole::Caption | TableInvariantRole::Cell) | None => true,
        };
        if !children_are_valid {
            return Err(LayoutError::source_contract(
                &layout_box.source_label,
                format!(
                    "table role {} has an invalid direct child",
                    role.expect("only table roles validate table children")
                        .debug_name()
                ),
            ));
        }
        Ok(())
    }

    pub(crate) fn new_box(
        source: Option<N>,
        owner: Option<N>,
        pseudo: Option<LayoutPseudo>,
        source_label: String,
        owner_label: Option<String>,
        element_semantics: Option<LayoutElementSemantics>,
        anonymous_reason: Option<LayoutAnonymousReason>,
        kind: LayoutBoxKind,
        mut style: ResolvedLayoutStyle,
        text: Option<Arc<str>>,
    ) -> LayoutBox<N> {
        if kind.is_internal_table_box() {
            // Keep the authored/computed value in `preferred_aspect_ratio`.
            // Only the numeric backend projection is suppressed: CSS Sizing
            // excludes internal table boxes from `aspect-ratio`, and the table
            // formatter supplies their used track and cell sizes. Chromium
            // represents the same boundary with its table-cell constraint
            // space before generic block-size resolution.
            style.taffy.aspect_ratio = None;
        }
        let capability_diagnostics =
            default_capability_diagnostics(kind, element_semantics.as_ref(), &style);
        LayoutBox {
            source,
            owner,
            pseudo,
            source_label,
            owner_label,
            element_semantics,
            anonymous_reason,
            capability_diagnostics,
            kind,
            structural_parent: None,
            parent: None,
            children: Vec::new(),
            layout_parent: None,
            layout_children: Vec::new(),
            positioned_containing_block: None,
            inline_static_position: None,
            style,
            text,
            text_selection: None,
            inline_layout: None,
            inline_context_owner: None,
            inline_flattened: false,
            outside_list_marker: false,
            scroll_offset: LayoutPoint::ZERO,
            replaced_context: None,
            replaced_image: None,
            css_images: crate::source::LayoutCssImageResources::default(),
            collapsed_table_border_part: false,
            inline_formatting_context: false,
            cache_slot: None,
            table_measure_cache: None,
            unrounded_layout: Layout::with_order(0),
            final_layout: Layout::with_order(0),
        }
    }
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum TableInvariantRole {
    Root,
    Caption,
    RowGroup,
    ColumnGroup,
    Column,
    Row,
    Cell,
}

impl TableInvariantRole {
    const fn is_direct_root_child(self) -> bool {
        matches!(
            self,
            Self::Caption | Self::RowGroup | Self::ColumnGroup | Self::Column
        )
    }

    const fn debug_name(self) -> &'static str {
        match self {
            Self::Root => "table-root",
            Self::Caption => "table-caption",
            Self::RowGroup => "table-row-group",
            Self::ColumnGroup => "table-column-group",
            Self::Column => "table-column",
            Self::Row => "table-row",
            Self::Cell => "table-cell",
        }
    }
}

const fn table_role(display: crate::LayoutDisplay) -> Option<TableInvariantRole> {
    use crate::LayoutDisplay as Display;
    match display {
        Display::Table | Display::InlineTable => Some(TableInvariantRole::Root),
        Display::TableCaption => Some(TableInvariantRole::Caption),
        Display::TableRowGroup | Display::TableHeaderGroup | Display::TableFooterGroup => {
            Some(TableInvariantRole::RowGroup)
        }
        Display::TableColumnGroup => Some(TableInvariantRole::ColumnGroup),
        Display::TableColumn => Some(TableInvariantRole::Column),
        Display::TableRow => Some(TableInvariantRole::Row),
        Display::TableCell => Some(TableInvariantRole::Cell),
        Display::None
        | Display::Contents
        | Display::Block
        | Display::FlowRoot
        | Display::Inline
        | Display::InlineBlock
        | Display::Flex
        | Display::InlineFlex
        | Display::Grid
        | Display::InlineGrid
        | Display::BlockListItem
        | Display::InlineListItem => None,
    }
}

fn default_capability_diagnostics(
    kind: LayoutBoxKind,
    _semantics: Option<&LayoutElementSemantics>,
    style: &ResolvedLayoutStyle,
) -> Vec<LayoutCapabilityDiagnostic> {
    use LayoutBoxKind as Kind;
    let mut diagnostics = Vec::new();
    let kind_diagnostic = match kind {
        Kind::TableWrapper
        | Kind::InlineTableWrapper
        | Kind::TableCaption
        | Kind::TableRowGroup
        | Kind::TableHeaderGroup
        | Kind::TableFooterGroup
        | Kind::TableColumnGroup
        | Kind::TableColumn
        | Kind::TableRow
        | Kind::TableCell
        | Kind::AnonymousTableWrapper
        | Kind::AnonymousTableRowGroup
        | Kind::AnonymousTableRow
        | Kind::AnonymousTableCell
        | Kind::ListItem
        | Kind::InlineListItem
        | Kind::PseudoMarker
        | Kind::FormControl => None,
        Kind::LineBreak => None,
        Kind::Replaced => None,
        Kind::PrincipalBlock
        | Kind::PrincipalFlowRoot
        | Kind::PrincipalFlex
        | Kind::PrincipalInlineFlex
        | Kind::PrincipalGrid
        | Kind::PrincipalInlineGrid
        | Kind::PrincipalInline
        | Kind::PrincipalInlineBlock
        | Kind::AnonymousBlock
        | Kind::AnonymousFlexItem
        | Kind::AnonymousGridItem
        | Kind::InlineContinuation
        | Kind::Text
        | Kind::PseudoBefore
        | Kind::PseudoAfter => None,
    };
    if let Some(diagnostic) = kind_diagnostic {
        push_diagnostic(&mut diagnostics, diagnostic);
    }
    if style.has_deferred_text_projection() {
        push_diagnostic(
            &mut diagnostics,
            LayoutCapabilityDiagnostic::TextProjectionDeferred,
        );
    }
    if style.has_deferred_intrinsic_sizing() {
        push_diagnostic(
            &mut diagnostics,
            LayoutCapabilityDiagnostic::IntrinsicSizingKeywordDeferred,
        );
    }
    if style.has_deferred_grid_template_mode() {
        push_diagnostic(
            &mut diagnostics,
            LayoutCapabilityDiagnostic::GridTemplateModeDeferred,
        );
    }
    diagnostics
}

fn push_diagnostic(
    diagnostics: &mut Vec<LayoutCapabilityDiagnostic>,
    diagnostic: LayoutCapabilityDiagnostic,
) {
    if !diagnostics.contains(&diagnostic) {
        diagnostics.push(diagnostic);
    }
}