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