layout: Enable using cached fragments when there is a BoxTree update point (#36404)

This starts to enable the fragment cache for all layout modes, except
grid. The main tricky bit here is that update points are absolutes and
these need to be laid out again in their containing blocks. We punt a
little bit on this, by forcing ancestors of update points to rebuild
their Fragments. This is just the first step.

Testing: We do not currently have layout performance tests, but will try
to run some tests manually later. Behavior is covered by the WPT.

Co-authored-by: Oriol Brufau <obrufau@igalia.com>
Signed-off-by: Martin Robinson <mrobinson@igalia.com>

Signed-off-by: Martin Robinson <mrobinson@igalia.com>
Co-authored-by: Oriol Brufau <obrufau@igalia.com>

11 files changed, 187 insertions, 47 deletions

diff --git a/components/layout_2020/dom.rs b/components/layout_2020/dom.rs
index 2e8a823c11e..8ea718c4bec 100644
--- a/components/layout_2020/dom.rs
+++ b/components/layout_2020/dom.rs
@@ -46,6 +46,26 @@ pub(super) enum LayoutBox {
     TaffyItemBox(ArcRefCell<TaffyItemBox>),
 }
 
+impl LayoutBox {
+    fn invalidate_cached_fragment(&self) {
+        match self {
+            LayoutBox::DisplayContents => {},
+            LayoutBox::BlockLevel(block_level_box) => {
+                block_level_box.borrow().invalidate_cached_fragment()
+            },
+            LayoutBox::InlineLevel(inline_item) => {
+                inline_item.borrow().invalidate_cached_fragment()
+            },
+            LayoutBox::FlexLevel(flex_level_box) => {
+                flex_level_box.borrow().invalidate_cached_fragment()
+            },
+            LayoutBox::TaffyItemBox(taffy_item_box) => {
+                taffy_item_box.borrow_mut().invalidate_cached_fragment()
+            },
+        }
+    }
+}
+
 /// A wrapper for [`InnerDOMLayoutData`]. This is necessary to give the entire data
 /// structure interior mutability, as we will need to mutate the layout data of
 /// non-mutable DOM nodes.
@@ -114,6 +134,8 @@ pub(crate) trait NodeExt<'dom>: 'dom + LayoutNode<'dom> {
 
     /// Remove boxes for the element itself, and its `:before` and `:after` if any.
     fn unset_all_boxes(self);
+
+    fn invalidate_cached_fragment(self);
 }
 
 impl<'dom, LayoutNodeType> NodeExt<'dom> for LayoutNodeType
@@ -255,4 +277,11 @@ where
         // Stylo already takes care of removing all layout data
         // for DOM descendants of elements with `display: none`.
     }
+
+    fn invalidate_cached_fragment(self) {
+        let data = self.layout_data_mut();
+        if let Some(data) = data.self_box.borrow_mut().as_mut() {
+            data.invalidate_cached_fragment();
+        }
+    }
 }
diff --git a/components/layout_2020/flexbox/layout.rs b/components/layout_2020/flexbox/layout.rs
index 28466f32efa..4720b5f9d74 100644
--- a/components/layout_2020/flexbox/layout.rs
+++ b/components/layout_2020/flexbox/layout.rs
@@ -1934,7 +1934,7 @@ impl FlexItem<'_> {
                     }
                 }
 
-                let layout = non_replaced.layout_with_caching(
+                let layout = non_replaced.layout(
                     flex_context.layout_context,
                     &mut positioning_context,
                     &item_as_containing_block,
@@ -2686,7 +2686,7 @@ impl FlexItemBox {
                 };
                 let mut content_block_size = || {
                     non_replaced
-                        .layout_with_caching(
+                        .layout(
                             flex_context.layout_context,
                             &mut positioning_context,
                             &item_as_containing_block,
diff --git a/components/layout_2020/flexbox/mod.rs b/components/layout_2020/flexbox/mod.rs
index 46d7a2387a8..a69a9af5898 100644
--- a/components/layout_2020/flexbox/mod.rs
+++ b/components/layout_2020/flexbox/mod.rs
@@ -143,6 +143,22 @@ pub(crate) enum FlexLevelBox {
     OutOfFlowAbsolutelyPositionedBox(ArcRefCell<AbsolutelyPositionedBox>),
 }
 
+impl FlexLevelBox {
+    pub(crate) fn invalidate_cached_fragment(&self) {
+        match self {
+            FlexLevelBox::FlexItem(flex_item_box) => flex_item_box
+                .independent_formatting_context
+                .base
+                .invalidate_cached_fragment(),
+            FlexLevelBox::OutOfFlowAbsolutelyPositionedBox(positioned_box) => positioned_box
+                .borrow()
+                .context
+                .base
+                .invalidate_cached_fragment(),
+        }
+    }
+}
+
 pub(crate) struct FlexItemBox {
     independent_formatting_context: IndependentFormattingContext,
 }
diff --git a/components/layout_2020/flow/inline/mod.rs b/components/layout_2020/flow/inline/mod.rs
index e9007ce2e45..ec77842854a 100644
--- a/components/layout_2020/flow/inline/mod.rs
+++ b/components/layout_2020/flow/inline/mod.rs
@@ -196,6 +196,30 @@ pub(crate) enum InlineItem {
     ),
 }
 
+impl InlineItem {
+    pub(crate) fn invalidate_cached_fragment(&self) {
+        match self {
+            InlineItem::StartInlineBox(..) | InlineItem::EndInlineBox | InlineItem::TextRun(..) => {
+            },
+            InlineItem::OutOfFlowAbsolutelyPositionedBox(positioned_box, ..) => {
+                positioned_box
+                    .borrow()
+                    .context
+                    .base
+                    .invalidate_cached_fragment();
+            },
+            InlineItem::OutOfFlowFloatBox(float_box) => {
+                float_box.contents.base.invalidate_cached_fragment()
+            },
+            InlineItem::Atomic(independent_formatting_context, ..) => {
+                independent_formatting_context
+                    .base
+                    .invalidate_cached_fragment();
+            },
+        }
+    }
+}
+
 /// Information about the current line under construction for a particular
 /// [`InlineFormattingContextLayout`]. This tracks position and size information while
 /// [`LineItem`]s are collected and is used as input when those [`LineItem`]s are
diff --git a/components/layout_2020/flow/mod.rs b/components/layout_2020/flow/mod.rs
index fd3c1de800d..8ddbddee507 100644
--- a/components/layout_2020/flow/mod.rs
+++ b/components/layout_2020/flow/mod.rs
@@ -90,6 +90,26 @@ pub(crate) enum BlockLevelBox {
 }
 
 impl BlockLevelBox {
+    pub(crate) fn invalidate_cached_fragment(&self) {
+        match self {
+            BlockLevelBox::Independent(independent_formatting_context) => {
+                &independent_formatting_context.base
+            },
+            BlockLevelBox::OutOfFlowAbsolutelyPositionedBox(positioned_box) => {
+                positioned_box
+                    .borrow()
+                    .context
+                    .base
+                    .invalidate_cached_fragment();
+                return;
+            },
+            BlockLevelBox::OutOfFlowFloatBox(float_box) => &float_box.contents.base,
+            BlockLevelBox::OutsideMarker(outside_marker) => &outside_marker.base,
+            BlockLevelBox::SameFormattingContextBlock { base, .. } => base,
+        }
+        .invalidate_cached_fragment();
+    }
+
     fn contains_floats(&self) -> bool {
         match self {
             BlockLevelBox::SameFormattingContextBlock {
@@ -1140,6 +1160,7 @@ impl IndependentNonReplacedContents {
             positioning_context,
             &containing_block_for_children,
             containing_block,
+            base,
             false, /* depends_on_block_constraints */
         );
 
@@ -1327,6 +1348,7 @@ impl IndependentNonReplacedContents {
                     style,
                 },
                 containing_block,
+                base,
                 false, /* depends_on_block_constraints */
             );
 
@@ -1391,6 +1413,7 @@ impl IndependentNonReplacedContents {
                         style,
                     },
                     containing_block,
+                    base,
                     false, /* depends_on_block_constraints */
                 );
 
@@ -2281,6 +2304,7 @@ impl IndependentFormattingContext {
                     child_positioning_context,
                     &containing_block_for_children,
                     containing_block,
+                    &self.base,
                     false, /* depends_on_block_constraints */
                 );
                 let inline_size = independent_layout
diff --git a/components/layout_2020/flow/root.rs b/components/layout_2020/flow/root.rs
index d784082e196..390850841bb 100644
--- a/components/layout_2020/flow/root.rs
+++ b/components/layout_2020/flow/root.rs
@@ -228,50 +228,72 @@ impl BoxTree {
         }
 
         loop {
-            if let Some((primary_style, display_inside, update_point)) = update_point(dirty_node) {
-                let contents = ReplacedContents::for_element(dirty_node, context)
-                    .map_or_else(|| NonReplacedContents::OfElement.into(), Contents::Replaced);
-                let info = NodeAndStyleInfo::new(dirty_node, Arc::clone(&primary_style));
-                let out_of_flow_absolutely_positioned_box = ArcRefCell::new(
-                    AbsolutelyPositionedBox::construct(context, &info, display_inside, contents),
-                );
-                match update_point {
-                    UpdatePoint::AbsolutelyPositionedBlockLevelBox(block_level_box) => {
-                        *block_level_box.borrow_mut() =
-                            BlockLevelBox::OutOfFlowAbsolutelyPositionedBox(
-                                out_of_flow_absolutely_positioned_box,
-                            );
-                    },
-                    UpdatePoint::AbsolutelyPositionedInlineLevelBox(
-                        inline_level_box,
+            let Some((primary_style, display_inside, update_point)) = update_point(dirty_node)
+            else {
+                dirty_node = match dirty_node.parent_node() {
+                    Some(parent) => parent,
+                    None => return false,
+                };
+                continue;
+            };
+
+            let contents = ReplacedContents::for_element(dirty_node, context)
+                .map_or_else(|| NonReplacedContents::OfElement.into(), Contents::Replaced);
+            let info = NodeAndStyleInfo::new(dirty_node, Arc::clone(&primary_style));
+            let out_of_flow_absolutely_positioned_box = ArcRefCell::new(
+                AbsolutelyPositionedBox::construct(context, &info, display_inside, contents),
+            );
+            match update_point {
+                UpdatePoint::AbsolutelyPositionedBlockLevelBox(block_level_box) => {
+                    *block_level_box.borrow_mut() = BlockLevelBox::OutOfFlowAbsolutelyPositionedBox(
+                        out_of_flow_absolutely_positioned_box,
+                    );
+                },
+                UpdatePoint::AbsolutelyPositionedInlineLevelBox(
+                    inline_level_box,
+                    text_offset_index,
+                ) => {
+                    *inline_level_box.borrow_mut() = InlineItem::OutOfFlowAbsolutelyPositionedBox(
+                        out_of_flow_absolutely_positioned_box,
                         text_offset_index,
-                    ) => {
-                        *inline_level_box.borrow_mut() =
-                            InlineItem::OutOfFlowAbsolutelyPositionedBox(
-                                out_of_flow_absolutely_positioned_box,
-                                text_offset_index,
-                            );
-                    },
-                    UpdatePoint::AbsolutelyPositionedFlexLevelBox(flex_level_box) => {
-                        *flex_level_box.borrow_mut() =
-                            FlexLevelBox::OutOfFlowAbsolutelyPositionedBox(
-                                out_of_flow_absolutely_positioned_box,
-                            );
-                    },
-                    UpdatePoint::AbsolutelyPositionedTaffyLevelBox(taffy_level_box) => {
-                        taffy_level_box.borrow_mut().taffy_level_box =
-                            TaffyItemBoxInner::OutOfFlowAbsolutelyPositionedBox(
-                                out_of_flow_absolutely_positioned_box,
-                            );
-                    },
-                }
-                return true;
+                    );
+                },
+                UpdatePoint::AbsolutelyPositionedFlexLevelBox(flex_level_box) => {
+                    *flex_level_box.borrow_mut() = FlexLevelBox::OutOfFlowAbsolutelyPositionedBox(
+                        out_of_flow_absolutely_positioned_box,
+                    );
+                },
+                UpdatePoint::AbsolutelyPositionedTaffyLevelBox(taffy_level_box) => {
+                    taffy_level_box.borrow_mut().taffy_level_box =
+                        TaffyItemBoxInner::OutOfFlowAbsolutelyPositionedBox(
+                            out_of_flow_absolutely_positioned_box,
+                        );
+                },
             }
-            dirty_node = match dirty_node.parent_node() {
-                Some(parent) => parent,
-                None => return false,
-            };
+            break;
+        }
+
+        // We are going to rebuild the box tree from the update point downward, but this update
+        // point is an absolute, which means that it needs to be laid out again in the containing
+        // block for absolutes, which is established by one of its ancestors. In addition,
+        // absolutes, when laid out, can produce more absolutes (either fixed or absolutely
+        // positioned) elements, so there may be yet more layout that has to happen in this
+        // ancestor.
+        //
+        // We do not know which ancestor is the one that established the containing block for this
+        // update point, so just invalidate the fragment cache of all ancestors, meaning that even
+        // though the box tree is preserved, the fragment tree from the root to the update point and
+        // all of its descendants will need to be rebuilt. This isn't as bad as it seems, because
+        // siblings and siblings of ancestors of this path through the tree will still have cached
+        // fragments.
+        //
+        // TODO: Do better. This is still a very crude way to do incremental layout.
+        while let Some(parent_node) = dirty_node.parent_node() {
+            parent_node.invalidate_cached_fragment();
+            dirty_node = parent_node;
         }
+
+        true
     }
 }
 
diff --git a/components/layout_2020/formatting_contexts.rs b/components/layout_2020/formatting_contexts.rs
index 573e9100cec..94b1cb0523a 100644
--- a/components/layout_2020/formatting_contexts.rs
+++ b/components/layout_2020/formatting_contexts.rs
@@ -219,7 +219,7 @@ impl IndependentFormattingContext {
 }
 
 impl IndependentNonReplacedContents {
-    pub fn layout(
+    pub(crate) fn layout_without_caching(
         &self,
         layout_context: &LayoutContext,
         positioning_context: &mut PositioningContext,
@@ -265,7 +265,7 @@ impl IndependentNonReplacedContents {
             level = "trace",
         )
     )]
-    pub fn layout_with_caching(
+    pub fn layout(
         &self,
         layout_context: &LayoutContext,
         positioning_context: &mut PositioningContext,
@@ -297,7 +297,7 @@ impl IndependentNonReplacedContents {
             positioning_context.collects_for_nearest_positioned_ancestor(),
         );
 
-        let result = self.layout(
+        let result = self.layout_without_caching(
             layout_context,
             &mut child_positioning_context,
             containing_block_for_children,
diff --git a/components/layout_2020/layout_box_base.rs b/components/layout_2020/layout_box_base.rs
index bb2d37698f1..885ff0d26d3 100644
--- a/components/layout_2020/layout_box_base.rs
+++ b/components/layout_2020/layout_box_base.rs
@@ -63,6 +63,10 @@ impl LayoutBoxBase {
         *cache = Some((constraint_space.block_size, result));
         result
     }
+
+    pub(crate) fn invalidate_cached_fragment(&self) {
+        let _ = self.cached_layout_result.borrow_mut().take();
+    }
 }
 
 impl Debug for LayoutBoxBase {
diff --git a/components/layout_2020/positioned.rs b/components/layout_2020/positioned.rs
index 238eb1e3b2a..7bff43d18d7 100644
--- a/components/layout_2020/positioned.rs
+++ b/components/layout_2020/positioned.rs
@@ -629,6 +629,7 @@ impl HoistedAbsolutelyPositionedBox {
                         &mut positioning_context,
                         &containing_block_for_children,
                         containing_block,
+                        &context.base,
                         false, /* depends_on_block_constraints */
                     );
 
diff --git a/components/layout_2020/taffy/layout.rs b/components/layout_2020/taffy/layout.rs
index 6c1b931599c..69ea7ddfd58 100644
--- a/components/layout_2020/taffy/layout.rs
+++ b/components/layout_2020/taffy/layout.rs
@@ -259,7 +259,7 @@ impl taffy::LayoutPartialTree for TaffyContainerContext<'_> {
                                     )
                                 });
 
-                            let layout = non_replaced.layout(
+                            let layout = non_replaced.layout_without_caching(
                                 self.layout_context,
                                 &mut child_positioning_context,
                                 &content_box_size_override,
diff --git a/components/layout_2020/taffy/mod.rs b/components/layout_2020/taffy/mod.rs
index 626704874d2..81f2f347fe9 100644
--- a/components/layout_2020/taffy/mod.rs
+++ b/components/layout_2020/taffy/mod.rs
@@ -111,6 +111,26 @@ impl TaffyItemBox {
             taffy_level_box: inner,
         }
     }
+
+    pub(crate) fn invalidate_cached_fragment(&mut self) {
+        self.taffy_layout = Default::default();
+        self.positioning_context =
+            PositioningContext::new_for_containing_block_for_all_descendants();
+        match self.taffy_level_box {
+            TaffyItemBoxInner::InFlowBox(ref independent_formatting_context) => {
+                independent_formatting_context
+                    .base
+                    .invalidate_cached_fragment()
+            },
+            TaffyItemBoxInner::OutOfFlowAbsolutelyPositionedBox(ref positioned_box) => {
+                positioned_box
+                    .borrow()
+                    .context
+                    .base
+                    .invalidate_cached_fragment()
+            },
+        }
+    }
 }
 
 /// Details from Taffy grid layout that will be stored