layout/flow/

root.rs

/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at https://mozilla.org/MPL/2.0/. */

use app_units::Au;
use atomic_refcell::AtomicRef;
use euclid::Rect;
use euclid::default::Size2D as UntypedSize2D;
use layout_api::wrapper_traits::{LayoutNode, ThreadSafeLayoutElement, ThreadSafeLayoutNode};
use layout_api::{AxesOverflow, LayoutElementType, LayoutNodeType};
use malloc_size_of_derive::MallocSizeOf;
use paint_api::display_list::AxesScrollSensitivity;
use script::layout_dom::{ServoLayoutNode, ServoThreadSafeLayoutNode};
use servo_arc::Arc;
use style::dom::{NodeInfo, TNode};
use style::properties::ComputedValues;
use style::values::computed::Overflow;
use style::values::specified::box_::DisplayOutside;
use style_traits::CSSPixel;

use crate::cell::ArcRefCell;
use crate::context::LayoutContext;
use crate::dom::{LayoutBox, NodeExt};
use crate::dom_traversal::{Contents, NodeAndStyleInfo};
use crate::flexbox::FlexLevelBox;
use crate::flow::float::FloatBox;
use crate::flow::inline::InlineItem;
use crate::flow::{BlockContainer, BlockFormattingContext, BlockLevelBox};
use crate::formatting_contexts::IndependentFormattingContext;
use crate::fragment_tree::{FragmentFlags, FragmentTree};
use crate::geom::{LogicalVec2, PhysicalSize};
use crate::positioned::{AbsolutelyPositionedBox, PositioningContext};
use crate::style_ext::{Display, DisplayGeneratingBox, DisplayInside};
use crate::taffy::{TaffyItemBox, TaffyItemBoxInner};
use crate::{DefiniteContainingBlock, PropagatedBoxTreeData};

#[derive(MallocSizeOf)]
pub struct BoxTree {
    /// Contains typically exactly one block-level box, which was generated by the root element.
    /// There may be zero if that element has `display: none`.
    root: BlockFormattingContext,

    /// Whether or not the viewport should be sensitive to scrolling input events in two axes
    pub(crate) viewport_overflow: AxesOverflow,
}

impl BoxTree {
    #[servo_tracing::instrument(name = "Box Tree Construction", skip_all)]
    pub(crate) fn construct(context: &LayoutContext, root_element: ServoLayoutNode<'_>) -> Self {
        let root_element = root_element.to_threadsafe();
        let boxes = construct_for_root_element(context, root_element);

        // Zero box for `:root { display: none }`, one for the root element otherwise.
        assert!(boxes.len() <= 1);

        let viewport_overflow = Self::viewport_overflow(root_element, boxes.first());
        let contents = BlockContainer::BlockLevelBoxes(boxes);
        let contains_floats = contents.contains_floats();
        Self {
            root: BlockFormattingContext {
                contents,
                contains_floats,
            },
            // From https://www.w3.org/TR/css-overflow-3/#overflow-propagation:
            // > If visible is applied to the viewport, it must be interpreted as auto.
            // > If clip is applied to the viewport, it must be interpreted as hidden.
            viewport_overflow: viewport_overflow.to_scrollable(),
        }
    }

    fn viewport_overflow(
        root_element: ServoThreadSafeLayoutNode<'_>,
        root_box: Option<&ArcRefCell<BlockLevelBox>>,
    ) -> AxesOverflow {
        // From https://www.w3.org/TR/css-overflow-3/#overflow-propagation:
        // > UAs must apply the overflow-* values set on the root element to the viewport when the
        // > root element’s display value is not none. However, when the root element is an [HTML]
        // > html element (including XML syntax for HTML) whose overflow value is visible (in both
        // > axes), and that element has as a child a body element whose display value is also not
        // > none, user agents must instead apply the overflow-* values of the first such child
        // > element to the viewport. The element from which the value is propagated must then have a
        // > used overflow value of visible.

        // If there is no root box, the root element has `display: none`, so don't propagate.
        // The spec isn't very clear about what value to use, but the initial value seems fine.
        // See https://github.com/w3c/csswg-drafts/issues/12649
        let Some(root_box) = root_box else {
            return AxesOverflow::default();
        };

        let propagate_from_body = || {
            // Unlike what the spec implies, we stop iterating when we find the first <body>,
            // even if it's not suitable because it lacks a box. This matches other browsers.
            // See https://github.com/w3c/csswg-drafts/issues/12644
            let body = root_element.children().find(|child| {
                child
                    .as_element()
                    .is_some_and(|element| element.is_body_element_of_html_element_root())
            })?;

            // We only propagate from the <body> if it generates a box. The spec only checks for
            // `display: none`, but other browsers don't propagate for `display: contents` either.
            // See https://github.com/w3c/csswg-drafts/issues/12643
            let body_layout_data = body.inner_layout_data()?;
            let mut body_box = body_layout_data.self_box.borrow_mut();
            body_box.as_mut()?.with_base_mut(|base| {
                base.base_fragment_info
                    .flags
                    .insert(FragmentFlags::PROPAGATED_OVERFLOW_TO_VIEWPORT);
                AxesOverflow::from(&*base.style)
            })
        };

        root_box.borrow_mut().with_base_mut(|base| {
            let root_overflow = AxesOverflow::from(&*base.style);
            if root_overflow.x == Overflow::Visible && root_overflow.y == Overflow::Visible {
                if let Some(body_overflow) = propagate_from_body() {
                    return body_overflow;
                }
            }
            base.base_fragment_info
                .flags
                .insert(FragmentFlags::PROPAGATED_OVERFLOW_TO_VIEWPORT);
            root_overflow
        })
    }

    /// This method attempts to incrementally update the box tree from an
    /// arbitrary node that is not necessarily the document's root element.
    ///
    /// If the node is not a valid candidate for incremental update, the method
    /// loops over its parent. The only valid candidates for now are absolutely
    /// positioned boxes which don't change their outside display mode (i.e. it
    /// will not attempt to update from an absolutely positioned inline element
    /// which became an absolutely positioned block element). The value `true`
    /// is returned if an incremental update could be done, and `false`
    /// otherwise.
    ///
    /// There are various pain points that need to be taken care of to extend
    /// the set of valid candidates:
    /// * it is not obvious how to incrementally check whether a block
    ///   formatting context still contains floats or not;
    /// * the propagation of text decorations towards node descendants is
    ///   hard to do incrementally with our current representation of boxes
    /// * how intrinsic content sizes are computed eagerly makes it hard
    ///   to update those sizes for ancestors of the node from which we
    ///   made an incremental update.
    pub(crate) fn update(
        context: &LayoutContext,
        dirty_root_from_script: ServoLayoutNode<'_>,
    ) -> bool {
        let Some(box_tree_update) = IncrementalBoxTreeUpdate::find(dirty_root_from_script) else {
            return false;
        };
        box_tree_update.update_from_dirty_root(context);
        true
    }
}

fn construct_for_root_element(
    context: &LayoutContext,
    root_element: ServoThreadSafeLayoutNode<'_>,
) -> Vec<ArcRefCell<BlockLevelBox>> {
    let info = NodeAndStyleInfo::new(
        root_element,
        root_element.style(&context.style_context),
        root_element.take_restyle_damage(),
    );
    let box_style = info.style.get_box();

    let display_inside = match Display::from(box_style.display) {
        Display::None => {
            root_element.unset_all_boxes();
            return Vec::new();
        },
        Display::Contents => {
            // Unreachable because the style crate adjusts the computed values:
            // https://drafts.csswg.org/css-display-3/#transformations
            // “'display' of 'contents' computes to 'block' on the root element”
            unreachable!()
        },
        // The root element is blockified, ignore DisplayOutside
        Display::GeneratingBox(display_generating_box) => display_generating_box.display_inside(),
    };

    let contents = Contents::for_element(root_element, context);

    let propagated_data = PropagatedBoxTreeData::default();
    let root_box = if box_style.position.is_absolutely_positioned() {
        BlockLevelBox::OutOfFlowAbsolutelyPositionedBox(ArcRefCell::new(
            AbsolutelyPositionedBox::construct(context, &info, display_inside, contents),
        ))
    } else if box_style.float.is_floating() {
        BlockLevelBox::OutOfFlowFloatBox(FloatBox::construct(
            context,
            &info,
            display_inside,
            contents,
            propagated_data,
        ))
    } else {
        BlockLevelBox::Independent(IndependentFormattingContext::construct(
            context,
            &info,
            display_inside,
            contents,
            propagated_data,
        ))
    };

    let root_box = ArcRefCell::new(root_box);
    root_element
        .box_slot()
        .set(LayoutBox::BlockLevel(root_box.clone()));
    vec![root_box]
}

impl BoxTree {
    #[servo_tracing::instrument(name = "Fragment Tree Construction", skip_all)]
    pub(crate) fn layout(
        &self,
        layout_context: &LayoutContext,
        viewport: UntypedSize2D<Au>,
    ) -> FragmentTree {
        let style = layout_context
            .style_context
            .stylist
            .device()
            .default_computed_values();

        // FIXME: use the document’s mode:
        // https://drafts.csswg.org/css-writing-modes/#principal-flow
        let physical_containing_block: Rect<Au, CSSPixel> =
            PhysicalSize::from_untyped(viewport).into();
        let initial_containing_block = DefiniteContainingBlock {
            size: LogicalVec2 {
                inline: physical_containing_block.size.width,
                block: physical_containing_block.size.height,
            },
            style,
        };

        let mut positioning_context = PositioningContext::default();
        let independent_layout = self.root.layout(
            layout_context,
            &mut positioning_context,
            &(&initial_containing_block).into(),
        );

        let mut root_fragments = independent_layout.fragments.into_iter().collect::<Vec<_>>();

        // Zero box for `:root { display: none }`, one for the root element otherwise.
        assert!(root_fragments.len() <= 1);

        // There may be more fragments at the top-level
        // (for positioned boxes whose containing is the initial containing block)
        // but only if there was one fragment for the root element.
        positioning_context.layout_initial_containing_block_children(
            layout_context,
            &initial_containing_block,
            &mut root_fragments,
        );

        let viewport_scroll_sensitivity = AxesScrollSensitivity {
            x: self.viewport_overflow.x.into(),
            y: self.viewport_overflow.y.into(),
        };

        FragmentTree::new(
            layout_context,
            root_fragments,
            physical_containing_block,
            viewport_scroll_sensitivity,
        )
    }
}

#[expect(clippy::enum_variant_names)]
enum DirtyRootBoxTreeNode {
    AbsolutelyPositionedBlockLevelBox(ArcRefCell<BlockLevelBox>),
    AbsolutelyPositionedInlineLevelBox(InlineItem, usize),
    AbsolutelyPositionedFlexLevelBox(ArcRefCell<FlexLevelBox>),
    AbsolutelyPositionedTaffyLevelBox(ArcRefCell<TaffyItemBox>),
}

struct IncrementalBoxTreeUpdate<'dom> {
    node: ServoLayoutNode<'dom>,
    box_tree_node: DirtyRootBoxTreeNode,
    primary_style: Arc<ComputedValues>,
    display_inside: DisplayInside,
}

impl<'dom> IncrementalBoxTreeUpdate<'dom> {
    fn find(dirty_root_from_script: ServoLayoutNode<'dom>) -> Option<Self> {
        let mut maybe_dirty_root_node = Some(dirty_root_from_script);
        while let Some(dirty_root_node) = maybe_dirty_root_node {
            if let Some(dirty_root) = Self::new_if_valid(dirty_root_node) {
                return Some(dirty_root);
            }

            maybe_dirty_root_node = dirty_root_node.parent_node();
        }

        None
    }

    fn new_if_valid(potential_dirty_root_node: ServoLayoutNode<'dom>) -> Option<Self> {
        if !potential_dirty_root_node.is_element() {
            return None;
        }

        if potential_dirty_root_node.type_id() ==
            LayoutNodeType::Element(LayoutElementType::HTMLBodyElement)
        {
            // This can require changes to the canvas background.
            return None;
        }

        // Don't update unstyled nodes or nodes that have pseudo-elements.
        let potential_thread_safe_dirty_root_node = potential_dirty_root_node.to_threadsafe();
        let element_data = potential_thread_safe_dirty_root_node
            .style_data()?
            .element_data
            .borrow();
        if !element_data.styles.pseudos.is_empty() {
            return None;
        }

        let layout_data = NodeExt::inner_layout_data(&potential_thread_safe_dirty_root_node)?;
        if !layout_data.pseudo_boxes.is_empty() {
            return None;
        }

        let primary_style = element_data.styles.primary();
        let box_style = primary_style.get_box();

        if !box_style.position.is_absolutely_positioned() {
            return None;
        }

        let display_inside = match Display::from(box_style.display) {
            Display::GeneratingBox(DisplayGeneratingBox::OutsideInside { inside, .. }) => inside,
            _ => return None,
        };

        let box_tree_node =
            match &*AtomicRef::filter_map(layout_data.self_box.borrow(), Option::as_ref)? {
                LayoutBox::DisplayContents(..) => return None,
                LayoutBox::BlockLevel(block_level_box) => match &*block_level_box.borrow() {
                    BlockLevelBox::OutOfFlowAbsolutelyPositionedBox(_)
                        if box_style.position.is_absolutely_positioned() =>
                    {
                        // If the outer type of its original display changed from block to inline,
                        // a block-level abspos needs to be placed in an inline formatting context,
                        // see [`BlockContainerBuilder::handle_absolutely_positioned_element()`].
                        if box_style.original_display.outside() == DisplayOutside::Inline {
                            return None;
                        }
                        DirtyRootBoxTreeNode::AbsolutelyPositionedBlockLevelBox(
                            block_level_box.clone(),
                        )
                    },
                    _ => return None,
                },
                LayoutBox::InlineLevel(inline_level_box) => {
                    let InlineItem::OutOfFlowAbsolutelyPositionedBox(_, text_offset_index) =
                        inline_level_box
                    else {
                        return None;
                    };
                    DirtyRootBoxTreeNode::AbsolutelyPositionedInlineLevelBox(
                        inline_level_box.clone(),
                        *text_offset_index,
                    )
                },
                LayoutBox::FlexLevel(flex_level_box) => match &*flex_level_box.borrow() {
                    FlexLevelBox::OutOfFlowAbsolutelyPositionedBox(_)
                        if box_style.position.is_absolutely_positioned() =>
                    {
                        DirtyRootBoxTreeNode::AbsolutelyPositionedFlexLevelBox(
                            flex_level_box.clone(),
                        )
                    },
                    _ => return None,
                },
                LayoutBox::TableLevelBox(..) => return None,
                LayoutBox::TaffyItemBox(taffy_level_box) => {
                    match &taffy_level_box.borrow().taffy_level_box {
                        TaffyItemBoxInner::OutOfFlowAbsolutelyPositionedBox(_)
                            if box_style.position.is_absolutely_positioned() =>
                        {
                            DirtyRootBoxTreeNode::AbsolutelyPositionedTaffyLevelBox(
                                taffy_level_box.clone(),
                            )
                        },
                        _ => return None,
                    }
                },
            };

        Some(Self {
            node: potential_dirty_root_node,
            box_tree_node,
            primary_style: primary_style.clone(),
            display_inside,
        })
    }

    #[servo_tracing::instrument(name = "Box Tree Update From Dirty Root", skip_all)]
    fn update_from_dirty_root(&self, context: &LayoutContext) {
        let node = self.node.to_threadsafe();
        let contents = Contents::for_element(node, context);

        let info =
            NodeAndStyleInfo::new(node, self.primary_style.clone(), node.take_restyle_damage());

        let out_of_flow_absolutely_positioned_box =
            AbsolutelyPositionedBox::construct(context, &info, self.display_inside, contents);
        match &self.box_tree_node {
            DirtyRootBoxTreeNode::AbsolutelyPositionedBlockLevelBox(block_level_box) => {
                *block_level_box.borrow_mut() = BlockLevelBox::OutOfFlowAbsolutelyPositionedBox(
                    ArcRefCell::new(out_of_flow_absolutely_positioned_box),
                );
            },
            DirtyRootBoxTreeNode::AbsolutelyPositionedInlineLevelBox(
                inline_level_box,
                text_offset_index,
            ) => match inline_level_box {
                InlineItem::OutOfFlowAbsolutelyPositionedBox(positioned_box, offset_in_text) => {
                    *positioned_box.borrow_mut() = out_of_flow_absolutely_positioned_box;
                    assert_eq!(
                        *offset_in_text, *text_offset_index,
                        "The offset of the dirty root shouldn't have changed"
                    );
                },
                _ => unreachable!("The dirty root should be absolutely positioned"),
            },
            DirtyRootBoxTreeNode::AbsolutelyPositionedFlexLevelBox(flex_level_box) => {
                *flex_level_box.borrow_mut() = FlexLevelBox::OutOfFlowAbsolutelyPositionedBox(
                    ArcRefCell::new(out_of_flow_absolutely_positioned_box),
                );
            },
            DirtyRootBoxTreeNode::AbsolutelyPositionedTaffyLevelBox(taffy_level_box) => {
                taffy_level_box.borrow_mut().taffy_level_box =
                    TaffyItemBoxInner::OutOfFlowAbsolutelyPositionedBox(ArcRefCell::new(
                        out_of_flow_absolutely_positioned_box,
                    ));
            },
        }

        let mut invalidate_start_point = self.node;
        while let Some(parent_node) = invalidate_start_point.parent_node() {
            // Box tree reconstruction doesn't need to involve these ancestors, so their
            // damage isn't useful for us.
            //
            // TODO: This isn't going to be good enough for incremental fragment tree
            // reconstruction, as fragment tree damage might extend further up the tree.
            parent_node.to_threadsafe().take_restyle_damage();

            invalidate_start_point = parent_node;
        }
    }
}