layout/flow/
root.rs

1/* This Source Code Form is subject to the terms of the Mozilla Public
2 * License, v. 2.0. If a copy of the MPL was not distributed with this
3 * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
4
5use app_units::Au;
6use atomic_refcell::AtomicRef;
7use compositing_traits::display_list::AxesScrollSensitivity;
8use euclid::Rect;
9use euclid::default::Size2D as UntypedSize2D;
10use layout_api::wrapper_traits::{LayoutNode, ThreadSafeLayoutElement, ThreadSafeLayoutNode};
11use layout_api::{AxesOverflow, LayoutElementType, LayoutNodeType};
12use malloc_size_of_derive::MallocSizeOf;
13use script::layout_dom::{ServoLayoutNode, ServoThreadSafeLayoutNode};
14use servo_arc::Arc;
15use style::dom::{NodeInfo, TNode};
16use style::properties::ComputedValues;
17use style::values::computed::Overflow;
18use style::values::specified::box_::DisplayOutside;
19use style_traits::CSSPixel;
20
21use crate::cell::ArcRefCell;
22use crate::context::LayoutContext;
23use crate::dom::{LayoutBox, NodeExt};
24use crate::dom_traversal::{Contents, NodeAndStyleInfo, NonReplacedContents};
25use crate::flexbox::FlexLevelBox;
26use crate::flow::float::FloatBox;
27use crate::flow::inline::InlineItem;
28use crate::flow::{BlockContainer, BlockFormattingContext, BlockLevelBox};
29use crate::formatting_contexts::IndependentFormattingContext;
30use crate::fragment_tree::{FragmentFlags, FragmentTree};
31use crate::geom::{LogicalVec2, PhysicalSize};
32use crate::positioned::{AbsolutelyPositionedBox, PositioningContext};
33use crate::replaced::ReplacedContents;
34use crate::style_ext::{Display, DisplayGeneratingBox, DisplayInside};
35use crate::taffy::{TaffyItemBox, TaffyItemBoxInner};
36use crate::{DefiniteContainingBlock, PropagatedBoxTreeData};
37
38#[derive(MallocSizeOf)]
39pub struct BoxTree {
40    /// Contains typically exactly one block-level box, which was generated by the root element.
41    /// There may be zero if that element has `display: none`.
42    root: BlockFormattingContext,
43
44    /// Whether or not the viewport should be sensitive to scrolling input events in two axes
45    pub(crate) viewport_overflow: AxesOverflow,
46}
47
48impl BoxTree {
49    #[servo_tracing::instrument(name = "Box Tree Construction", skip_all)]
50    pub(crate) fn construct(context: &LayoutContext, root_element: ServoLayoutNode<'_>) -> Self {
51        let root_element = root_element.to_threadsafe();
52        let boxes = construct_for_root_element(context, root_element);
53
54        // Zero box for `:root { display: none }`, one for the root element otherwise.
55        assert!(boxes.len() <= 1);
56
57        let viewport_overflow = Self::viewport_overflow(root_element, boxes.first());
58        let contents = BlockContainer::BlockLevelBoxes(boxes);
59        let contains_floats = contents.contains_floats();
60        Self {
61            root: BlockFormattingContext {
62                contents,
63                contains_floats,
64            },
65            // From https://www.w3.org/TR/css-overflow-3/#overflow-propagation:
66            // > If visible is applied to the viewport, it must be interpreted as auto.
67            // > If clip is applied to the viewport, it must be interpreted as hidden.
68            viewport_overflow: viewport_overflow.to_scrollable(),
69        }
70    }
71
72    fn viewport_overflow(
73        root_element: ServoThreadSafeLayoutNode<'_>,
74        root_box: Option<&ArcRefCell<BlockLevelBox>>,
75    ) -> AxesOverflow {
76        // From https://www.w3.org/TR/css-overflow-3/#overflow-propagation:
77        // > UAs must apply the overflow-* values set on the root element to the viewport when the
78        // > root element’s display value is not none. However, when the root element is an [HTML]
79        // > html element (including XML syntax for HTML) whose overflow value is visible (in both
80        // > axes), and that element has as a child a body element whose display value is also not
81        // > none, user agents must instead apply the overflow-* values of the first such child
82        // > element to the viewport. The element from which the value is propagated must then have a
83        // > used overflow value of visible.
84
85        // If there is no root box, the root element has `display: none`, so don't propagate.
86        // The spec isn't very clear about what value to use, but the initial value seems fine.
87        // See https://github.com/w3c/csswg-drafts/issues/12649
88        let Some(root_box) = root_box else {
89            return AxesOverflow::default();
90        };
91
92        let propagate_from_body = || {
93            // Unlike what the spec implies, we stop iterating when we find the first <body>,
94            // even if it's not suitable because it lacks a box. This matches other browsers.
95            // See https://github.com/w3c/csswg-drafts/issues/12644
96            let body = root_element.children().find(|child| {
97                child
98                    .as_element()
99                    .is_some_and(|element| element.is_body_element_of_html_element_root())
100            })?;
101
102            // We only propagate from the <body> if it generates a box. The spec only checks for
103            // `display: none`, but other browsers don't propagate for `display: contents` either.
104            // See https://github.com/w3c/csswg-drafts/issues/12643
105            let body_layout_data = body.inner_layout_data()?;
106            let mut body_box = body_layout_data.self_box.borrow_mut();
107            body_box.as_mut()?.with_base_mut_fold(None, |accum, base| {
108                base.base_fragment_info
109                    .flags
110                    .insert(FragmentFlags::PROPAGATED_OVERFLOW_TO_VIEWPORT);
111                accum.or_else(|| Some(AxesOverflow::from(&*base.style)))
112            })
113        };
114
115        root_box.borrow_mut().with_base_mut(|base| {
116            let root_overflow = AxesOverflow::from(&*base.style);
117            if root_overflow.x == Overflow::Visible && root_overflow.y == Overflow::Visible {
118                if let Some(body_overflow) = propagate_from_body() {
119                    return body_overflow;
120                }
121            }
122            base.base_fragment_info
123                .flags
124                .insert(FragmentFlags::PROPAGATED_OVERFLOW_TO_VIEWPORT);
125            root_overflow
126        })
127    }
128
129    /// This method attempts to incrementally update the box tree from an
130    /// arbitrary node that is not necessarily the document's root element.
131    ///
132    /// If the node is not a valid candidate for incremental update, the method
133    /// loops over its parent. The only valid candidates for now are absolutely
134    /// positioned boxes which don't change their outside display mode (i.e. it
135    /// will not attempt to update from an absolutely positioned inline element
136    /// which became an absolutely positioned block element). The value `true`
137    /// is returned if an incremental update could be done, and `false`
138    /// otherwise.
139    ///
140    /// There are various pain points that need to be taken care of to extend
141    /// the set of valid candidates:
142    /// * it is not obvious how to incrementally check whether a block
143    ///   formatting context still contains floats or not;
144    /// * the propagation of text decorations towards node descendants is
145    ///   hard to do incrementally with our current representation of boxes
146    /// * how intrinsic content sizes are computed eagerly makes it hard
147    ///   to update those sizes for ancestors of the node from which we
148    ///   made an incremental update.
149    pub(crate) fn update(
150        context: &LayoutContext,
151        dirty_root_from_script: ServoLayoutNode<'_>,
152    ) -> bool {
153        let Some(box_tree_update) = IncrementalBoxTreeUpdate::find(dirty_root_from_script) else {
154            return false;
155        };
156        box_tree_update.update_from_dirty_root(context);
157        true
158    }
159}
160
161fn construct_for_root_element(
162    context: &LayoutContext,
163    root_element: ServoThreadSafeLayoutNode<'_>,
164) -> Vec<ArcRefCell<BlockLevelBox>> {
165    let info = NodeAndStyleInfo::new(
166        root_element,
167        root_element.style(&context.style_context),
168        root_element.take_restyle_damage(),
169    );
170    let box_style = info.style.get_box();
171
172    let display_inside = match Display::from(box_style.display) {
173        Display::None => {
174            root_element.unset_all_boxes();
175            return Vec::new();
176        },
177        Display::Contents => {
178            // Unreachable because the style crate adjusts the computed values:
179            // https://drafts.csswg.org/css-display-3/#transformations
180            // “'display' of 'contents' computes to 'block' on the root element”
181            unreachable!()
182        },
183        // The root element is blockified, ignore DisplayOutside
184        Display::GeneratingBox(display_generating_box) => display_generating_box.display_inside(),
185    };
186
187    let contents = ReplacedContents::for_element(root_element, context)
188        .map_or_else(|| NonReplacedContents::OfElement.into(), Contents::Replaced);
189
190    let propagated_data = PropagatedBoxTreeData::default();
191    let root_box = if box_style.position.is_absolutely_positioned() {
192        BlockLevelBox::OutOfFlowAbsolutelyPositionedBox(ArcRefCell::new(
193            AbsolutelyPositionedBox::construct(context, &info, display_inside, contents),
194        ))
195    } else if box_style.float.is_floating() {
196        BlockLevelBox::OutOfFlowFloatBox(FloatBox::construct(
197            context,
198            &info,
199            display_inside,
200            contents,
201            propagated_data,
202        ))
203    } else {
204        BlockLevelBox::Independent(IndependentFormattingContext::construct(
205            context,
206            &info,
207            display_inside,
208            contents,
209            propagated_data,
210        ))
211    };
212
213    let root_box = ArcRefCell::new(root_box);
214    root_element
215        .box_slot()
216        .set(LayoutBox::BlockLevel(root_box.clone()));
217    vec![root_box]
218}
219
220impl BoxTree {
221    #[servo_tracing::instrument(name = "Fragment Tree Construction", skip_all)]
222    pub(crate) fn layout(
223        &self,
224        layout_context: &LayoutContext,
225        viewport: UntypedSize2D<Au>,
226    ) -> FragmentTree {
227        let style = layout_context
228            .style_context
229            .stylist
230            .device()
231            .default_computed_values();
232
233        // FIXME: use the document’s mode:
234        // https://drafts.csswg.org/css-writing-modes/#principal-flow
235        let physical_containing_block: Rect<Au, CSSPixel> =
236            PhysicalSize::from_untyped(viewport).into();
237        let initial_containing_block = DefiniteContainingBlock {
238            size: LogicalVec2 {
239                inline: physical_containing_block.size.width,
240                block: physical_containing_block.size.height,
241            },
242            style,
243        };
244
245        let mut positioning_context = PositioningContext::default();
246        let independent_layout = self.root.layout(
247            layout_context,
248            &mut positioning_context,
249            &(&initial_containing_block).into(),
250        );
251
252        let mut root_fragments = independent_layout.fragments.into_iter().collect::<Vec<_>>();
253
254        // Zero box for `:root { display: none }`, one for the root element otherwise.
255        assert!(root_fragments.len() <= 1);
256
257        // There may be more fragments at the top-level
258        // (for positioned boxes whose containing is the initial containing block)
259        // but only if there was one fragment for the root element.
260        positioning_context.layout_initial_containing_block_children(
261            layout_context,
262            &initial_containing_block,
263            &mut root_fragments,
264        );
265
266        let viewport_scroll_sensitivity = AxesScrollSensitivity {
267            x: self.viewport_overflow.x.into(),
268            y: self.viewport_overflow.y.into(),
269        };
270
271        FragmentTree::new(
272            layout_context,
273            root_fragments,
274            physical_containing_block,
275            viewport_scroll_sensitivity,
276        )
277    }
278}
279
280#[allow(clippy::enum_variant_names)]
281enum DirtyRootBoxTreeNode {
282    AbsolutelyPositionedBlockLevelBox(ArcRefCell<BlockLevelBox>),
283    AbsolutelyPositionedInlineLevelBox(ArcRefCell<InlineItem>, usize),
284    AbsolutelyPositionedFlexLevelBox(ArcRefCell<FlexLevelBox>),
285    AbsolutelyPositionedTaffyLevelBox(ArcRefCell<TaffyItemBox>),
286}
287
288struct IncrementalBoxTreeUpdate<'dom> {
289    node: ServoLayoutNode<'dom>,
290    box_tree_node: DirtyRootBoxTreeNode,
291    primary_style: Arc<ComputedValues>,
292    display_inside: DisplayInside,
293}
294
295impl<'dom> IncrementalBoxTreeUpdate<'dom> {
296    fn find(dirty_root_from_script: ServoLayoutNode<'dom>) -> Option<Self> {
297        let mut maybe_dirty_root_node = Some(dirty_root_from_script);
298        while let Some(dirty_root_node) = maybe_dirty_root_node {
299            if let Some(dirty_root) = Self::new_if_valid(dirty_root_node) {
300                return Some(dirty_root);
301            }
302
303            maybe_dirty_root_node = dirty_root_node.parent_node();
304        }
305
306        None
307    }
308
309    fn new_if_valid(potential_dirty_root_node: ServoLayoutNode<'dom>) -> Option<Self> {
310        if !potential_dirty_root_node.is_element() {
311            return None;
312        }
313
314        if potential_dirty_root_node.type_id() ==
315            LayoutNodeType::Element(LayoutElementType::HTMLBodyElement)
316        {
317            // This can require changes to the canvas background.
318            return None;
319        }
320
321        // Don't update unstyled nodes or nodes that have pseudo-elements.
322        let potential_thread_safe_dirty_root_node = potential_dirty_root_node.to_threadsafe();
323        let element_data = potential_thread_safe_dirty_root_node
324            .style_data()?
325            .element_data
326            .borrow();
327        if !element_data.styles.pseudos.is_empty() {
328            return None;
329        }
330
331        let layout_data = NodeExt::inner_layout_data(&potential_thread_safe_dirty_root_node)?;
332        if !layout_data.pseudo_boxes.is_empty() {
333            return None;
334        }
335
336        let primary_style = element_data.styles.primary();
337        let box_style = primary_style.get_box();
338
339        if !box_style.position.is_absolutely_positioned() {
340            return None;
341        }
342
343        let display_inside = match Display::from(box_style.display) {
344            Display::GeneratingBox(DisplayGeneratingBox::OutsideInside { inside, .. }) => inside,
345            _ => return None,
346        };
347
348        let box_tree_node =
349            match &*AtomicRef::filter_map(layout_data.self_box.borrow(), Option::as_ref)? {
350                LayoutBox::DisplayContents(..) => return None,
351                LayoutBox::BlockLevel(block_level_box) => match &*block_level_box.borrow() {
352                    BlockLevelBox::OutOfFlowAbsolutelyPositionedBox(_)
353                        if box_style.position.is_absolutely_positioned() =>
354                    {
355                        // If the outer type of its original display changed from block to inline,
356                        // a block-level abspos needs to be placed in an inline formatting context,
357                        // see [`BlockContainerBuilder::handle_absolutely_positioned_element()`].
358                        if box_style.original_display.outside() == DisplayOutside::Inline {
359                            return None;
360                        }
361                        DirtyRootBoxTreeNode::AbsolutelyPositionedBlockLevelBox(
362                            block_level_box.clone(),
363                        )
364                    },
365                    _ => return None,
366                },
367                LayoutBox::InlineLevel(inline_level_items) => {
368                    let inline_level_box = inline_level_items.first()?;
369                    let InlineItem::OutOfFlowAbsolutelyPositionedBox(_, text_offset_index) =
370                        &*inline_level_box.borrow()
371                    else {
372                        return None;
373                    };
374                    DirtyRootBoxTreeNode::AbsolutelyPositionedInlineLevelBox(
375                        inline_level_box.clone(),
376                        *text_offset_index,
377                    )
378                },
379                LayoutBox::FlexLevel(flex_level_box) => match &*flex_level_box.borrow() {
380                    FlexLevelBox::OutOfFlowAbsolutelyPositionedBox(_)
381                        if box_style.position.is_absolutely_positioned() =>
382                    {
383                        DirtyRootBoxTreeNode::AbsolutelyPositionedFlexLevelBox(
384                            flex_level_box.clone(),
385                        )
386                    },
387                    _ => return None,
388                },
389                LayoutBox::TableLevelBox(..) => return None,
390                LayoutBox::TaffyItemBox(taffy_level_box) => {
391                    match &taffy_level_box.borrow().taffy_level_box {
392                        TaffyItemBoxInner::OutOfFlowAbsolutelyPositionedBox(_)
393                            if box_style.position.is_absolutely_positioned() =>
394                        {
395                            DirtyRootBoxTreeNode::AbsolutelyPositionedTaffyLevelBox(
396                                taffy_level_box.clone(),
397                            )
398                        },
399                        _ => return None,
400                    }
401                },
402            };
403
404        Some(Self {
405            node: potential_dirty_root_node,
406            box_tree_node,
407            primary_style: primary_style.clone(),
408            display_inside,
409        })
410    }
411
412    #[servo_tracing::instrument(name = "Box Tree Update From Dirty Root", skip_all)]
413    fn update_from_dirty_root(&self, context: &LayoutContext) {
414        let node = self.node.to_threadsafe();
415        let contents = ReplacedContents::for_element(node, context)
416            .map_or_else(|| NonReplacedContents::OfElement.into(), Contents::Replaced);
417
418        let info =
419            NodeAndStyleInfo::new(node, self.primary_style.clone(), node.take_restyle_damage());
420
421        let out_of_flow_absolutely_positioned_box = ArcRefCell::new(
422            AbsolutelyPositionedBox::construct(context, &info, self.display_inside, contents),
423        );
424        match &self.box_tree_node {
425            DirtyRootBoxTreeNode::AbsolutelyPositionedBlockLevelBox(block_level_box) => {
426                *block_level_box.borrow_mut() = BlockLevelBox::OutOfFlowAbsolutelyPositionedBox(
427                    out_of_flow_absolutely_positioned_box,
428                );
429            },
430            DirtyRootBoxTreeNode::AbsolutelyPositionedInlineLevelBox(
431                inline_level_box,
432                text_offset_index,
433            ) => {
434                *inline_level_box.borrow_mut() = InlineItem::OutOfFlowAbsolutelyPositionedBox(
435                    out_of_flow_absolutely_positioned_box,
436                    *text_offset_index,
437                );
438            },
439            DirtyRootBoxTreeNode::AbsolutelyPositionedFlexLevelBox(flex_level_box) => {
440                *flex_level_box.borrow_mut() = FlexLevelBox::OutOfFlowAbsolutelyPositionedBox(
441                    out_of_flow_absolutely_positioned_box,
442                );
443            },
444            DirtyRootBoxTreeNode::AbsolutelyPositionedTaffyLevelBox(taffy_level_box) => {
445                taffy_level_box.borrow_mut().taffy_level_box =
446                    TaffyItemBoxInner::OutOfFlowAbsolutelyPositionedBox(
447                        out_of_flow_absolutely_positioned_box,
448                    );
449            },
450        }
451
452        let mut invalidate_start_point = self.node;
453        while let Some(parent_node) = invalidate_start_point.parent_node() {
454            // Box tree reconstruction doesn't need to involve these ancestors, so their
455            // damage isn't useful for us.
456            //
457            // TODO: This isn't going to be good enough for incremental fragment tree
458            // reconstruction, as fragment tree damage might extend further up the tree.
459            parent_node.to_threadsafe().take_restyle_damage();
460
461            invalidate_start_point = parent_node;
462        }
463    }
464}