Skip to main content

layout/
traversal.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 std::sync::Arc;
6
7use layout_api::{
8    DangerousStyleElement, DangerousStyleNode, LayoutDamage, LayoutElement, LayoutNode,
9};
10use script::layout_dom::ServoLayoutNode;
11use style::context::{SharedStyleContext, StyleContext};
12use style::dom::{NodeInfo, TElement, TNode};
13use style::selector_parser::RestyleDamage;
14use style::traversal::{DomTraversal, recalc_style_at};
15
16use crate::BoxTree;
17use crate::context::LayoutContext;
18use crate::dom::{DOMLayoutData, NodeExt};
19use crate::layout_root::LayoutRoot;
20
21pub struct RecalcStyle<'a> {
22    context: &'a LayoutContext<'a>,
23}
24
25impl<'a> RecalcStyle<'a> {
26    pub(crate) fn new(context: &'a LayoutContext<'a>) -> Self {
27        RecalcStyle { context }
28    }
29
30    pub(crate) fn context(&self) -> &LayoutContext<'a> {
31        self.context
32    }
33}
34
35impl<'dom, E> DomTraversal<E> for RecalcStyle<'_>
36where
37    E: DangerousStyleElement<'dom> + TElement,
38    E::ConcreteNode: 'dom + DangerousStyleNode<'dom>,
39{
40    fn process_preorder<F>(
41        &self,
42        context: &mut StyleContext<E>,
43        node: E::ConcreteNode,
44        note_child: F,
45    ) where
46        F: FnMut(E::ConcreteNode),
47    {
48        let Some(dangerous_style_element) = node.as_element() else {
49            return;
50        };
51
52        let layout_element = dangerous_style_element.layout_element();
53        let had_style_data = layout_element.style_data().is_some();
54        layout_element.initialize_style_and_layout_data::<DOMLayoutData>();
55        layout_element.ensure_presentational_hints();
56
57        let mut element_data = dangerous_style_element.mutate_data().unwrap();
58        if !had_style_data {
59            element_data.damage = RestyleDamage::reconstruct();
60        }
61
62        recalc_style_at(
63            self,
64            context,
65            dangerous_style_element,
66            &mut element_data,
67            note_child,
68        );
69    }
70
71    #[inline]
72    fn needs_postorder_traversal() -> bool {
73        false
74    }
75
76    fn process_postorder(&self, _style_context: &mut StyleContext<E>, _node: E::ConcreteNode) {
77        panic!("this should never be called")
78    }
79
80    fn shared_context(&self) -> &SharedStyleContext<'_> {
81        &self.context.style_context
82    }
83}
84
85#[servo_tracing::instrument(skip_all)]
86pub(crate) fn compute_damage_and_rebuild_box_tree<'dom>(
87    box_tree: &mut Option<Arc<BoxTree>>,
88    layout_context: &LayoutContext,
89    dirty_root: ServoLayoutNode<'dom>,
90    root_node: ServoLayoutNode<'dom>,
91    damage_from_environment: LayoutDamage,
92    layout_roots: &mut Vec<LayoutRoot<'dom>>,
93) -> LayoutDamage {
94    // First process damage below the dirty root, returning the damage that
95    // should be propagated upward into the clean part of the tree.
96    let layout_damage = compute_damage_and_rebuild_box_tree_below_dirty_root(
97        layout_context,
98        dirty_root,
99        damage_from_environment,
100        layout_roots,
101    );
102
103    // If there was no box tree at all at this point, a full box tree / fragment
104    // tree layout is necessary and there is no point processing any other damage.
105    if box_tree.is_none() {
106        *box_tree = Some(Arc::new(BoxTree::construct(layout_context, root_node)));
107        return layout_damage;
108    }
109
110    // Propagate the damage from the dirty part of the tree upward. In this part of
111    // the traversal no elements can add damage, but they might isolate damage being
112    // propagated upward between the dirty root and the root of the DOM.
113    let layout_damage = compute_damage_and_rebuild_box_tree_above_dirty_root(
114        layout_context,
115        dirty_root,
116        layout_damage,
117        layout_roots,
118    );
119
120    // We could not find a place in the middle of the tree to run box tree reconstruction,
121    // so just rebuild the whole tree.
122    if layout_damage.contains(LayoutDamage::DescendantHasBoxDamage) {
123        *box_tree = Some(Arc::new(BoxTree::construct(layout_context, root_node)));
124    }
125
126    layout_damage
127}
128
129#[expect(unsafe_code)]
130#[servo_tracing::instrument(skip_all)]
131pub(crate) fn compute_damage_and_rebuild_box_tree_above_dirty_root<'dom>(
132    layout_context: &LayoutContext,
133    dirty_root: ServoLayoutNode<'dom>,
134    layout_damage: LayoutDamage,
135    layout_roots: &mut Vec<LayoutRoot<'dom>>,
136) -> LayoutDamage {
137    // Cases where propagating damage up the tree is necessary:
138    //
139    // 1. Box tree layout of the dirty root is necessary, in which case we
140    //    search for a place to re-run box tree layout and also invalidate
141    //    all fragments and fragment caches to the root.
142    // 2. Fragment tree layout needs to run again, in which case fragments
143    //    and fragment caches need to be invalidated.
144    // 3. Overflow is dirty, in which case overflow needs to be cleared.
145    //
146    // In every other case, just return early.
147    let needs_fragment_tree_rebuild = layout_damage.contains(LayoutDamage::Relayout);
148    let needs_overflow_recalculation = layout_damage.contains(LayoutDamage::RecalculateOverflow);
149    if !needs_fragment_tree_rebuild && !needs_overflow_recalculation {
150        assert!(!layout_damage.contains(LayoutDamage::DescendantCollectedAsLayoutRoot));
151        return layout_damage;
152    }
153
154    let mut damage_for_parent = layout_damage;
155    let mut maybe_parent_node = unsafe { dirty_root.dangerous_flat_tree_parent() };
156    while let Some(parent_node) = maybe_parent_node {
157        let damage_set = ElementDamageSet {
158            node: parent_node,
159            from_parent: LayoutDamage::empty(),
160            on_element: LayoutDamage::empty(),
161            from_children: damage_for_parent,
162            // Ancestors above the dirty root do not have damage, so will never subsume
163            // any existing layout roots, but they may isolate upward flowing fragment
164            // tree damage.
165            incoming_layout_root_count: layout_roots.len(),
166        };
167
168        damage_for_parent = damage_set.apply_damage(layout_context, layout_roots);
169        maybe_parent_node = unsafe { parent_node.dangerous_flat_tree_parent() };
170    }
171
172    damage_for_parent
173}
174
175pub(crate) fn compute_damage_and_rebuild_box_tree_below_dirty_root<'dom>(
176    layout_context: &LayoutContext,
177    node: ServoLayoutNode<'dom>,
178    damage_from_parent: LayoutDamage,
179    layout_roots: &mut Vec<LayoutRoot<'dom>>,
180) -> LayoutDamage {
181    // Don't do any kind of damage propagation or box tree construction for non-Element
182    // nodes, such as text and comments.
183    let Some(element) = node.as_element() else {
184        return damage_from_parent;
185    };
186
187    let (element_damage, is_display_none) = {
188        let mut element_data = element.element_data_mut();
189        (
190            LayoutDamage::from(std::mem::take(&mut element_data.damage)),
191            element_data.styles.is_display_none(),
192        )
193    };
194
195    let has_dirty_descendants;
196    #[expect(unsafe_code)]
197    unsafe {
198        let dangerous_style_element = element.dangerous_style_element();
199        has_dirty_descendants = dangerous_style_element.has_dirty_descendants();
200        dangerous_style_element.unset_dirty_descendants();
201    };
202
203    if is_display_none {
204        node.unset_all_boxes();
205        return element_damage | damage_from_parent;
206    }
207
208    let mut damage_set = ElementDamageSet {
209        node,
210        from_parent: damage_from_parent,
211        on_element: element_damage,
212        from_children: LayoutDamage::empty(),
213        incoming_layout_root_count: layout_roots.len(),
214    };
215
216    // Depending on the incoming damage, it can be isolated, meaning that some damage
217    // doesn't get passed down to children.
218    let damage_for_children = damage_set.isolate_incoming_damage();
219
220    // Propagate damage to children and gather the resulting damage into `from_children`.
221    damage_set.propagate_damage_to_children(
222        layout_context,
223        has_dirty_descendants,
224        damage_for_children,
225        layout_roots,
226    );
227
228    // Apply the calculated damage to this element (perhaps triggering box tree layout),
229    // and propagate resulting damage to ancestors.
230    damage_set.apply_damage(layout_context, layout_roots)
231}
232
233enum BoxDamageAction<'a> {
234    RebuildAncestor,
235    TryRebuild,
236    InvalidateFragmentTreeBelowLayoutRoot,
237    CollectLayoutRoot(LayoutRoot<'a>),
238    InvalidateFragmentTreeAboveLayoutRoot,
239    InvalidateScrollableOverflow,
240    None,
241}
242
243impl BoxDamageAction<'_> {
244    fn rebuilds_box(&self) -> bool {
245        matches!(self, Self::RebuildAncestor | Self::TryRebuild)
246    }
247}
248
249pub(crate) struct ElementDamageSet<'a> {
250    node: ServoLayoutNode<'a>,
251    pub from_parent: LayoutDamage,
252    pub on_element: LayoutDamage,
253    pub from_children: LayoutDamage,
254    pub incoming_layout_root_count: usize,
255}
256
257impl<'a> ElementDamageSet<'a> {
258    /// Given the damage on the element and damage from parents, determine which damage
259    /// should be passed to children, returning that value.
260    fn isolate_incoming_damage(&mut self) -> LayoutDamage {
261        // Children only receive layout mode damage from their parents, except when an ancestor
262        // needs to be completely rebuilt. In that case, descendants are rebuilt down to the
263        // first independent formatting context, which should isolate that tree from further
264        // box damage.
265        let mut damage_for_children = (self.on_element | self.from_parent).only_layout_modes();
266        let rebuild_children = self.on_element.contains(LayoutDamage::BoxDamage) ||
267            (self.from_parent.contains(LayoutDamage::BoxDamage) &&
268                !self.node.isolates_damage_for_damage_propagation());
269
270        if rebuild_children {
271            damage_for_children.insert(LayoutDamage::BoxDamage);
272        } else if self.from_parent.contains(LayoutDamage::Relayout) &&
273            !self.on_element.contains(LayoutDamage::Relayout) &&
274            self.node.isolates_damage_for_damage_propagation()
275        {
276            // If not rebuilding the boxes for this node, but fragments need to be laid out
277            // only because of an ancestor, fragment layout caches should still be valid when
278            // crossing down into new independent formatting contexts.
279            damage_for_children.remove(LayoutDamage::Relayout);
280            self.from_parent.remove(LayoutDamage::Relayout);
281        }
282
283        damage_for_children
284    }
285
286    /// Given the damage the damage to children and whether or not this element had any
287    /// dirty descendants, conditionally propagated damage to children and set the resulting
288    /// damage from children on this [`ElementDamageSet`].
289    fn propagate_damage_to_children(
290        &mut self,
291        layout_context: &LayoutContext<'_>,
292        has_dirty_descendants: bool,
293        damage_for_children: LayoutDamage,
294        layout_roots: &mut Vec<LayoutRoot<'a>>,
295    ) {
296        // Propagate damage into children, but only if:
297        //  1. There is a descendant that was dirty / possibly restyled.
298        //  2. We detected that we need to rebuild child boxes.
299        //  3. An ancestor will be laid out and children need to have their fragment caches cleared.
300        //
301        // In other situations, such as when layout will not run at all or when we are
302        // guaranteed that children are undamaged, we can skip traversing children entirely.
303        if has_dirty_descendants ||
304            damage_for_children.intersects(LayoutDamage::BoxDamage | LayoutDamage::Relayout)
305        {
306            for child in self.node.flat_tree_children() {
307                if child.is_element() {
308                    self.from_children |= compute_damage_and_rebuild_box_tree_below_dirty_root(
309                        layout_context,
310                        child,
311                        damage_for_children,
312                        layout_roots,
313                    );
314                }
315            }
316        }
317    }
318
319    /// Given the damage from this element, the parent, and children, determine what action to
320    /// take for this element's boxes and return the damage that should be propagated to parents.
321    fn apply_damage(
322        self,
323        layout_context: &LayoutContext<'_>,
324        layout_roots: &mut Vec<LayoutRoot<'a>>,
325    ) -> LayoutDamage {
326        let only_layout_mode_damage =
327            (self.from_parent | self.on_element | self.from_children).only_layout_modes();
328
329        let invalidate_for_rebuild = || {
330            self.node.unset_all_boxes();
331            LayoutDamage::DescendantHasBoxDamage | LayoutDamage::Relayout
332        };
333
334        // This removes any dirty layout roots from descendants.
335        let discard_any_descendant_layout_roots = |layout_roots: &mut Vec<LayoutRoot>| {
336            layout_roots.truncate(self.incoming_layout_root_count);
337        };
338
339        let action = self.box_damage_action();
340        let will_rebuild_box = action.rebuilds_box();
341        let damage_for_parent = match action {
342            BoxDamageAction::TryRebuild => {
343                discard_any_descendant_layout_roots(layout_roots);
344
345                if self
346                    .node
347                    .rebuild_box_tree_from_independent_formatting_context(layout_context)
348                {
349                    // In this case, we have rebuilt the box tree from this point and we do not
350                    // have to propagate rebuild box tree damage up the tree any further.
351                    LayoutDamage::Relayout | LayoutDamage::RecomputeInlineContentSizes
352                } else {
353                    // A descendant needs to be rebuilt, but couldn't be rebuilt here,
354                    // because this node was an not a rebuild-compatible independent
355                    // formatting context. In this case do the same thing as if we needed
356                    // to rebuild an ancestor.
357                    invalidate_for_rebuild()
358                }
359            },
360            BoxDamageAction::RebuildAncestor => {
361                // In this case an ancestor needs to be completely rebuilt.
362                //
363                // This means that this box is no longer valid and also needs to be rebuilt
364                // (perhaps some of its descendants do not though). In this case, unset all existing
365                // boxes for the node and ensure that the appropriate rebuild-type damage
366                // propagates up the tree.
367                discard_any_descendant_layout_roots(layout_roots);
368                invalidate_for_rebuild()
369            },
370            BoxDamageAction::InvalidateFragmentTreeBelowLayoutRoot => {
371                // In this case, this node's boxes are preserved! It's possible that we still need
372                // to run fragment tree layout in this subtree due to an ancestor, this node, or a
373                // descendant changing style. In that case, we ask the `LayoutBoxBase` to clear
374                // any cached information that cannot be used.
375                discard_any_descendant_layout_roots(layout_roots);
376
377                let mut damage_for_parent =
378                    (self.on_element | self.from_children) | self.from_parent.only_layout_modes();
379
380                // This node also needed new fragment tree layout, so if any descendant
381                // was collected as a layout root, it's now discarded. This means we
382                // should also clear the damage (though harmless as Relayout takes
383                // precedence) indicating that there was a collected layout root.
384                damage_for_parent.remove(LayoutDamage::DescendantCollectedAsLayoutRoot);
385
386                let mut inline_size_depends_on_content = false;
387                self.node.with_layout_box_base_including_pseudos(|base| {
388                    inline_size_depends_on_content |=
389                        base.invalidate_caches_for_fragment_tree_layout(&self);
390                });
391
392                self.adjust_inline_content_size_damage(
393                    &mut damage_for_parent,
394                    inline_size_depends_on_content,
395                );
396
397                damage_for_parent
398            },
399            BoxDamageAction::CollectLayoutRoot(layout_root) => {
400                // A layout root should only be collected if a parent node does not
401                // produce damage requiring a fragment tree layout. This is essential
402                // to ensure the invariant that layout roots are only collected when
403                // they isolate damage from ancestors. If an ancestor has damage, a
404                // layout root's final position depends on that ancestor's layout
405                // and should never be a collected layout root.
406                debug_assert!(!self.from_parent.contains(LayoutDamage::Relayout));
407
408                // This removes any dirty layout roots from descendants and then adds this
409                // node as a dirty layout root. As this node itself as a dirty layout
410                // root, it subsumes all dirty descendant layout roots.
411                discard_any_descendant_layout_roots(layout_roots);
412                layout_roots.push(layout_root);
413
414                self.node.with_layout_box_base_including_pseudos(|base| {
415                    base.invalidate_caches(&self);
416                    base.mark_fragments_as_descendants_changed();
417                });
418                LayoutDamage::RecalculateOverflow |
419                    LayoutDamage::DescendantCollectedAsLayoutRoot |
420                    LayoutDamage::RecomputeInlineContentSizes
421            },
422            BoxDamageAction::InvalidateFragmentTreeAboveLayoutRoot => {
423                // Damage propagation works exactly the same at the point the layout root is collected
424                // and above it. Layout caches are invalidated and damage is adjusted, maybe limited
425                // inline content size recalculation.
426                let mut damage_for_parent = LayoutDamage::RecalculateOverflow |
427                    LayoutDamage::DescendantCollectedAsLayoutRoot;
428
429                let mut inline_size_depends_on_content = false;
430                self.node.with_layout_box_base_including_pseudos(|base| {
431                    inline_size_depends_on_content |= base.invalidate_caches(&self);
432                    base.mark_fragments_as_descendants_changed();
433                });
434                self.adjust_inline_content_size_damage(
435                    &mut damage_for_parent,
436                    inline_size_depends_on_content,
437                );
438
439                damage_for_parent
440            },
441            BoxDamageAction::InvalidateScrollableOverflow => {
442                // In this case the node's fragments are preserved, but it or one of its descendants
443                // had scrollable overflow damage, which means that scrollable overflow should be
444                // cleared. This causes it to be recalculated the next time it's queried.
445                self.node.with_layout_box_base_including_pseudos(|base| {
446                    base.clear_scrollable_overflow_all_on_fragments();
447                });
448                only_layout_mode_damage
449            },
450            BoxDamageAction::None => only_layout_mode_damage,
451        };
452
453        // If this element's boxes are preserved and its style has changed, whether or not
454        // we run fragment tree layout, we need to update any preserved layout data
455        // structures' style references.
456        if !self.on_element.is_empty() && !will_rebuild_box {
457            self.node.repair_style(&layout_context.style_context);
458        }
459
460        damage_for_parent
461    }
462
463    fn box_damage_action(&self) -> BoxDamageAction<'a> {
464        // When a parent box is going to be reconstructed, that overrides everything else.
465        if self
466            .from_parent
467            .contains(LayoutDamage::DescendantHasBoxDamage)
468        {
469            return BoxDamageAction::RebuildAncestor;
470        }
471
472        // When this element or one of its descendants needs to be reconstructed, try to
473        // rebuild it here. If that fails, an ancestor box will be reconstructed instead.
474        let element_and_children_damage = self.on_element | self.from_children;
475        if element_and_children_damage.contains(LayoutDamage::DescendantHasBoxDamage) {
476            return BoxDamageAction::TryRebuild;
477        }
478
479        if element_and_children_damage.contains(LayoutDamage::Relayout) &&
480            !self.from_parent.contains(LayoutDamage::Relayout) &&
481            let Ok(layout_root) = LayoutRoot::try_from(self.node)
482        {
483            return BoxDamageAction::CollectLayoutRoot(layout_root);
484        }
485
486        // If this element needs a new fragment layout, then invalidate fragment caches
487        // clear the resulting fragments, and clear scrollable overflow.
488        if (self.from_parent | element_and_children_damage).contains(LayoutDamage::Relayout) {
489            return BoxDamageAction::InvalidateFragmentTreeBelowLayoutRoot;
490        }
491
492        // If one of this element's descendants was collected as a layout root, then
493        // invalidate fragment caches and clear scrollable overflow.
494        if self
495            .from_children
496            .contains(LayoutDamage::DescendantCollectedAsLayoutRoot)
497        {
498            return BoxDamageAction::InvalidateFragmentTreeAboveLayoutRoot;
499        }
500
501        // If the scrollable overflow of this element has changed, invalidate the
502        // scrollable overflow.
503        if element_and_children_damage.contains(LayoutDamage::RecalculateOverflow) {
504            return BoxDamageAction::InvalidateScrollableOverflow;
505        }
506
507        BoxDamageAction::None
508    }
509
510    fn adjust_inline_content_size_damage(
511        &self,
512        damage_for_parent: &mut LayoutDamage,
513        inline_size_depends_on_content: bool,
514    ) {
515        let children_need_inline_content_size_recalculation = self
516            .from_children
517            .contains(LayoutDamage::RecomputeInlineContentSizes) &&
518            inline_size_depends_on_content;
519        damage_for_parent.set(
520            LayoutDamage::RecomputeInlineContentSizes,
521            !self.on_element.is_empty() || children_need_inline_content_size_recalculation,
522        );
523    }
524}