Best headless browser for AI agents. Lite, Fast, High-Compatibility. Built in Rust
Rust ai-agentsai-toolsbrowserbrowser-automationcloud-browserheadlessheadless-browserkitesurfplaywrightpuppeteerrustservoweb-crawlerweb-crawlingweb-scraperweb-scraping
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);
}
}