Auto merge of #26046 - mrobinson:arcrefcell-hoisting, r=SimonSapin

layout_2020: Use ArcRefCell to track hoisted fragments

This avoids the use of lookup tables for containing blocks when
constructing the stacking context tree.

This seems to catch some laid-out hoisted fragments that were otherwise
dropped in the previous design. The changes cause one new test to pass
and one to fail. Visual examination of the failing tests reveals that
it's a progression (list markers are appearing when they were previously
not rendered).

<!-- Please describe your changes on the following line: -->

---
<!-- Thank you for contributing to Servo! Please replace each `[ ]` by `[X]` when the step is complete, and replace `___` with appropriate data: -->
- [x] `./mach build -d` does not report any errors
- [x] `./mach test-tidy` does not report any errors
- [x] These changes fix #___ (GitHub issue number if applicable)

<!-- Either: -->
- [x] There are tests for these changes OR
- [ ] These changes do not require tests because ___

<!-- Also, please make sure that "Allow edits from maintainers" checkbox is checked, so that we can help you if you get stuck somewhere along the way.-->

<!-- Pull requests that do not address these steps are welcome, but they will require additional verification as part of the review process. -->

8 files changed, 104 insertions, 156 deletions

diff --git a/components/layout_2020/display_list/stacking_context.rs b/components/layout_2020/display_list/stacking_context.rs
index 978881147e3..82f694c5542 100644
--- a/components/layout_2020/display_list/stacking_context.rs
+++ b/components/layout_2020/display_list/stacking_context.rs
@@ -9,10 +9,8 @@ use crate::fragments::{
     AbsoluteOrFixedPositionedFragment, AnonymousFragment, BoxFragment, Fragment,
 };
 use crate::geom::PhysicalRect;
-use crate::positioned::HoistedFragmentId;
 use crate::style_ext::ComputedValuesExt;
 use euclid::default::Rect;
-use fnv::FnvHashMap;
 use gfx_traits::{combine_id_with_fragment_type, FragmentType};
 use servo_arc::Arc as ServoArc;
 use std::cmp::Ordering;
@@ -37,30 +35,13 @@ pub(crate) struct ContainingBlock {
 
     /// The physical rect of this containing block.
     rect: PhysicalRect<Length>,
-
-    /// Fragments for positioned descendants (including direct children) that were
-    /// hoisted into this containing block. They have hashed based on the
-    /// HoistedFragmentId that is generated during hoisting.
-    hoisted_children: FnvHashMap<HoistedFragmentId, ArcRefCell<Fragment>>,
 }
 
 impl ContainingBlock {
-    pub(crate) fn new(
-        rect: &PhysicalRect<Length>,
-        space_and_clip: wr::SpaceAndClipInfo,
-        children: &[ArcRefCell<Fragment>],
-    ) -> Self {
-        let mut hoisted_children = FnvHashMap::default();
-        for child in children {
-            if let Some(hoisted_fragment_id) = child.borrow().hoisted_fragment_id() {
-                hoisted_children.insert(*hoisted_fragment_id, child.clone());
-            }
-        }
-
+    pub(crate) fn new(rect: &PhysicalRect<Length>, space_and_clip: wr::SpaceAndClipInfo) -> Self {
         ContainingBlock {
             space_and_clip,
             rect: *rect,
-            hoisted_children,
         }
     }
 }
@@ -333,12 +314,14 @@ impl Fragment {
         stacking_context: &mut StackingContext,
         mode: StackingContextBuildMode,
     ) {
-        if mode == StackingContextBuildMode::SkipHoisted && self.is_hoisted() {
-            return;
-        }
-
         match self {
             Fragment::Box(fragment) => {
+                if mode == StackingContextBuildMode::SkipHoisted &&
+                    fragment.style.clone_position().is_absolutely_positioned()
+                {
+                    return;
+                }
+
                 fragment.build_stacking_context_tree(
                     fragment_ref,
                     builder,
@@ -417,7 +400,7 @@ impl BoxFragment {
         }
 
         let new_containing_block =
-            ContainingBlock::new(padding_rect, builder.current_space_and_clip, &self.children);
+            ContainingBlock::new(padding_rect, builder.current_space_and_clip);
 
         if self
             .style
@@ -750,37 +733,39 @@ impl AbsoluteOrFixedPositionedFragment {
         containing_block_info: &ContainingBlockInfo,
         stacking_context: &mut StackingContext,
     ) {
-        let mut build_for_containing_block = |containing_block: &ContainingBlock| {
-            let hoisted_child = match containing_block.hoisted_children.get(&self.0) {
-                Some(hoisted_child) => hoisted_child,
-                None => return false,
-            };
-
-            builder.clipping_and_scrolling_scope(|builder| {
-                let mut new_containing_block_info = containing_block_info.clone();
-                new_containing_block_info.rect = containing_block.rect;
-                builder.current_space_and_clip = containing_block.space_and_clip;
-                hoisted_child.borrow().build_stacking_context_tree(
-                    hoisted_child,
-                    builder,
-                    &new_containing_block_info,
-                    stacking_context,
-                    StackingContextBuildMode::IncludeHoisted,
-                );
-            });
+        let hoisted_fragment = self.hoisted_fragment.borrow();
+        let fragment_ref = match hoisted_fragment.as_ref() {
+            Some(fragment_ref) => fragment_ref,
+            None => {
+                warn!("Found hoisted box with missing fragment.");
+                return;
+            },
+        };
 
-            return true;
+        let containing_block = match self.position {
+            ComputedPosition::Fixed => &containing_block_info.containing_block_for_all_descendants,
+            ComputedPosition::Absolute => containing_block_info
+                .nearest_containing_block
+                .as_ref()
+                .unwrap_or(&containing_block_info.containing_block_for_all_descendants),
+            ComputedPosition::Static | ComputedPosition::Relative => unreachable!(
+                "Found an AbsoluteOrFixedPositionedFragment for a \
+                              non-absolutely or fixed position fragment."
+            ),
         };
 
-        if let Some(containing_block) = containing_block_info.nearest_containing_block.as_ref() {
-            if build_for_containing_block(containing_block) {
-                return;
-            }
-        }
+        builder.clipping_and_scrolling_scope(|builder| {
+            let mut new_containing_block_info = containing_block_info.clone();
+            new_containing_block_info.rect = containing_block.rect;
+            builder.current_space_and_clip = containing_block.space_and_clip;
 
-        if !build_for_containing_block(&containing_block_info.containing_block_for_all_descendants)
-        {
-            warn!("Could not find containing block of hoisted positioned child!");
-        }
+            fragment_ref.borrow().build_stacking_context_tree(
+                fragment_ref,
+                builder,
+                &new_containing_block_info,
+                stacking_context,
+                StackingContextBuildMode::IncludeHoisted,
+            );
+        });
     }
 }
diff --git a/components/layout_2020/flow/inline.rs b/components/layout_2020/flow/inline.rs
index 6b4faceea75..6588a6a3137 100644
--- a/components/layout_2020/flow/inline.rs
+++ b/components/layout_2020/flow/inline.rs
@@ -304,12 +304,15 @@ impl InlineFormattingContext {
                                 },
                             };
                         let hoisted_box = box_.clone().to_hoisted(initial_start_corner, tree_rank);
-                        let hoisted_fragment_id = hoisted_box.fragment_id;
+                        let hoisted_fragment = hoisted_box.fragment.clone();
                         ifc.push_hoisted_box_to_positioning_context(hoisted_box);
                         ifc.current_nesting_level.fragments_so_far.push(
-                            Fragment::AbsoluteOrFixedPositioned(AbsoluteOrFixedPositionedFragment(
-                                hoisted_fragment_id,
-                            )),
+                            Fragment::AbsoluteOrFixedPositioned(
+                                AbsoluteOrFixedPositionedFragment {
+                                    hoisted_fragment,
+                                    position: box_.contents.style.clone_position(),
+                                },
+                            ),
                         );
                     },
                     InlineLevelBox::OutOfFlowFloatBox(_box_) => {
@@ -492,7 +495,6 @@ impl<'box_tree> PartialInlineBoxFragment<'box_tree> {
             self.border.clone(),
             self.margin.clone(),
             CollapsedBlockMargins::zero(),
-            None, // hoisted_fragment_id
         );
         let last_fragment = self.last_box_tree_fragment && !at_line_break;
         if last_fragment {
@@ -560,7 +562,6 @@ fn layout_atomic(
                 border,
                 margin,
                 CollapsedBlockMargins::zero(),
-                None, // hoisted_fragment_id
             )
         },
         Err(non_replaced) => {
@@ -636,7 +637,6 @@ fn layout_atomic(
                 border,
                 margin,
                 CollapsedBlockMargins::zero(),
-                None, // hoisted_fragment_id
             )
         },
     };
diff --git a/components/layout_2020/flow/mod.rs b/components/layout_2020/flow/mod.rs
index 6aab3ba2be6..dcf2f9c4de3 100644
--- a/components/layout_2020/flow/mod.rs
+++ b/components/layout_2020/flow/mod.rs
@@ -315,12 +315,13 @@ impl BlockLevelBox {
                 ))
             },
             BlockLevelBox::OutOfFlowAbsolutelyPositionedBox(box_) => {
-                let hoisted_fragment = box_.clone().to_hoisted(Vec2::zero(), tree_rank);
-                let hoisted_fragment_id = hoisted_fragment.fragment_id.clone();
-                positioning_context.push(hoisted_fragment);
-                Fragment::AbsoluteOrFixedPositioned(AbsoluteOrFixedPositionedFragment(
-                    hoisted_fragment_id,
-                ))
+                let hoisted_box = box_.clone().to_hoisted(Vec2::zero(), tree_rank);
+                let hoisted_fragment = hoisted_box.fragment.clone();
+                positioning_context.push(hoisted_box);
+                Fragment::AbsoluteOrFixedPositioned(AbsoluteOrFixedPositionedFragment {
+                    hoisted_fragment,
+                    position: box_.contents.style.clone_position(),
+                })
             },
             BlockLevelBox::OutOfFlowFloatBox(_box_) => {
                 // FIXME: call layout_maybe_position_relative_fragment here
@@ -501,7 +502,6 @@ fn layout_in_flow_non_replaced_block_level(
         border,
         margin,
         block_margins_collapsed_with_children,
-        None, // hoisted_fragment_id
     )
 }
 
@@ -553,7 +553,6 @@ fn layout_in_flow_replaced_block_level<'a>(
         border,
         margin,
         block_margins_collapsed_with_children,
-        None, // hoisted_fragment_id
     )
 }
 
diff --git a/components/layout_2020/flow/root.rs b/components/layout_2020/flow/root.rs
index 6e3617f739d..975d5470636 100644
--- a/components/layout_2020/flow/root.rs
+++ b/components/layout_2020/flow/root.rs
@@ -147,48 +147,47 @@ impl BoxTreeRoot {
         let dummy_tree_rank = 0;
         let mut positioning_context =
             PositioningContext::new_for_containing_block_for_all_descendants();
-        let mut independent_layout = self.0.layout(
+        let independent_layout = self.0.layout(
             layout_context,
             &mut positioning_context,
             &(&initial_containing_block).into(),
             dummy_tree_rank,
         );
 
+        let mut children = independent_layout
+            .fragments
+            .into_iter()
+            .map(|fragment| ArcRefCell::new(fragment))
+            .collect();
         positioning_context.layout_initial_containing_block_children(
             layout_context,
             &initial_containing_block,
-            &mut independent_layout.fragments,
+            &mut children,
         );
 
-        let scrollable_overflow =
-            independent_layout
-                .fragments
-                .iter()
-                .fold(PhysicalRect::zero(), |acc, child| {
-                    let child_overflow = child.scrollable_overflow(&physical_containing_block);
+        let scrollable_overflow = children.iter().fold(PhysicalRect::zero(), |acc, child| {
+            let child_overflow = child
+                .borrow()
+                .scrollable_overflow(&physical_containing_block);
 
-                    // https://drafts.csswg.org/css-overflow/#scrolling-direction
-                    // We want to clip scrollable overflow on box-start and inline-start
-                    // sides of the scroll container.
-                    //
-                    // FIXME(mrobinson, bug 25564): This should take into account writing
-                    // mode.
-                    let child_overflow = PhysicalRect::new(
-                        euclid::Point2D::zero(),
-                        euclid::Size2D::new(
-                            child_overflow.size.width + child_overflow.origin.x,
-                            child_overflow.size.height + child_overflow.origin.y,
-                        ),
-                    );
-                    acc.union(&child_overflow)
-                });
+            // https://drafts.csswg.org/css-overflow/#scrolling-direction
+            // We want to clip scrollable overflow on box-start and inline-start
+            // sides of the scroll container.
+            //
+            // FIXME(mrobinson, bug 25564): This should take into account writing
+            // mode.
+            let child_overflow = PhysicalRect::new(
+                euclid::Point2D::zero(),
+                euclid::Size2D::new(
+                    child_overflow.size.width + child_overflow.origin.x,
+                    child_overflow.size.height + child_overflow.origin.y,
+                ),
+            );
+            acc.union(&child_overflow)
+        });
 
         FragmentTreeRoot {
-            children: independent_layout
-                .fragments
-                .into_iter()
-                .map(|fragment| ArcRefCell::new(fragment))
-                .collect(),
+            children,
             scrollable_overflow,
             initial_containing_block: physical_containing_block,
         }
@@ -206,7 +205,6 @@ impl FragmentTreeRoot {
                 containing_block_for_all_descendants: ContainingBlock::new(
                     &self.initial_containing_block,
                     stacking_context_builder.current_space_and_clip,
-                    &self.children,
                 ),
             };
 
diff --git a/components/layout_2020/fragments.rs b/components/layout_2020/fragments.rs
index 72e6549c7be..35c21e6dace 100644
--- a/components/layout_2020/fragments.rs
+++ b/components/layout_2020/fragments.rs
@@ -7,7 +7,6 @@ use crate::geom::flow_relative::{Rect, Sides};
 use crate::geom::{PhysicalPoint, PhysicalRect};
 #[cfg(debug_assertions)]
 use crate::layout_debug;
-use crate::positioned::HoistedFragmentId;
 use gfx::font::FontMetrics as GfxFontMetrics;
 use gfx::text::glyph::GlyphStore;
 use gfx_traits::print_tree::PrintTree;
@@ -16,6 +15,7 @@ use serde::ser::{Serialize, Serializer};
 use servo_arc::Arc as ServoArc;
 use std::sync::Arc;
 use style::computed_values::overflow_x::T as ComputedOverflow;
+use style::computed_values::position::T as ComputedPosition;
 use style::dom::OpaqueNode;
 use style::logical_geometry::WritingMode;
 use style::properties::ComputedValues;
@@ -34,7 +34,10 @@ pub(crate) enum Fragment {
 }
 
 #[derive(Serialize)]
-pub(crate) struct AbsoluteOrFixedPositionedFragment(pub HoistedFragmentId);
+pub(crate) struct AbsoluteOrFixedPositionedFragment {
+    pub position: ComputedPosition,
+    pub hoisted_fragment: ArcRefCell<Option<ArcRefCell<Fragment>>>,
+}
 
 #[derive(Serialize)]
 pub(crate) struct BoxFragment {
@@ -57,11 +60,6 @@ pub(crate) struct BoxFragment {
 
     /// The scrollable overflow of this box fragment.
     pub scrollable_overflow_from_children: PhysicalRect<Length>,
-
-    /// If this fragment was laid out from a hoisted box, this id corresponds to the id stored in
-    /// the AbsoluteOrFixedPositionedFragment left as a placeholder in the tree position of the
-    /// box.
-    pub hoisted_fragment_id: Option<HoistedFragmentId>,
 }
 
 #[derive(Serialize)]
@@ -177,20 +175,6 @@ impl Fragment {
         }
     }
 
-    pub fn is_hoisted(&self) -> bool {
-        match self {
-            Fragment::Box(fragment) if fragment.hoisted_fragment_id.is_some() => true,
-            _ => false,
-        }
-    }
-
-    pub fn hoisted_fragment_id(&self) -> Option<&HoistedFragmentId> {
-        match self {
-            Fragment::Box(fragment) => fragment.hoisted_fragment_id.as_ref(),
-            _ => None,
-        }
-    }
-
     pub(crate) fn find<T>(
         &self,
         containing_block: &PhysicalRect<Length>,
@@ -228,7 +212,7 @@ impl Fragment {
 
 impl AbsoluteOrFixedPositionedFragment {
     pub fn print(&self, tree: &mut PrintTree) {
-        tree.add_item(format!("AbsoluteOrFixedPositionedFragment({:?})", self.0));
+        tree.add_item(format!("AbsoluteOrFixedPositionedFragment"));
     }
 }
 
@@ -292,7 +276,6 @@ impl BoxFragment {
         border: Sides<Length>,
         margin: Sides<Length>,
         block_margins_collapsed_with_children: CollapsedBlockMargins,
-        hoisted_fragment_id: Option<HoistedFragmentId>,
     ) -> BoxFragment {
         // FIXME(mrobinson, bug 25564): We should be using the containing block
         // here to properly convert scrollable overflow to physical geometry.
@@ -315,7 +298,6 @@ impl BoxFragment {
             margin,
             block_margins_collapsed_with_children,
             scrollable_overflow_from_children,
-            hoisted_fragment_id,
         }
     }
 
@@ -354,8 +336,7 @@ impl BoxFragment {
                 \nborder rect={:?}\
                 \nscrollable_overflow={:?}\
                 \noverflow={:?} / {:?}\
-                \nstyle={:p}\
-                \nhoisted_id={:?}",
+                \nstyle={:p}",
             self.content_rect,
             self.padding_rect(),
             self.border_rect(),
@@ -363,7 +344,6 @@ impl BoxFragment {
             self.style.get_box().overflow_x,
             self.style.get_box().overflow_y,
             self.style,
-            self.hoisted_fragment_id,
         ));
 
         for child in &self.children {
diff --git a/components/layout_2020/positioned.rs b/components/layout_2020/positioned.rs
index df8b75557b4..2806611e3a8 100644
--- a/components/layout_2020/positioned.rs
+++ b/components/layout_2020/positioned.rs
@@ -14,25 +14,12 @@ use crate::{ContainingBlock, DefiniteContainingBlock};
 use rayon::iter::{IntoParallelRefIterator, ParallelExtend};
 use rayon_croissant::ParallelIteratorExt;
 use servo_arc::Arc;
-use std::sync::atomic::{AtomicUsize, Ordering};
 use style::computed_values::position::T as Position;
 use style::properties::ComputedValues;
 use style::values::computed::{Length, LengthOrAuto, LengthPercentage, LengthPercentageOrAuto};
 use style::values::specified::text::TextDecorationLine;
 use style::Zero;
 
-static HOISTED_FRAGMENT_ID_COUNTER: AtomicUsize = AtomicUsize::new(0);
-
-#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq, Serialize)]
-pub(crate) struct HoistedFragmentId(u16);
-
-impl HoistedFragmentId {
-    pub fn new() -> HoistedFragmentId {
-        let new_id = HOISTED_FRAGMENT_ID_COUNTER.fetch_add(1, Ordering::SeqCst) as u16;
-        HoistedFragmentId(new_id)
-    }
-}
-
 #[derive(Debug, Serialize)]
 pub(crate) struct AbsolutelyPositionedBox {
     pub contents: IndependentFormattingContext,
@@ -47,7 +34,6 @@ pub(crate) struct PositioningContext {
     for_nearest_containing_block_for_all_descendants: Vec<HoistedAbsolutelyPositionedBox>,
 }
 
-#[derive(Debug)]
 pub(crate) struct HoistedAbsolutelyPositionedBox {
     absolutely_positioned_box: Arc<AbsolutelyPositionedBox>,
 
@@ -58,10 +44,10 @@ pub(crate) struct HoistedAbsolutelyPositionedBox {
 
     box_offsets: Vec2<AbsoluteBoxOffsets>,
 
-    /// The id which is shared between this HoistedAbsolutelyPositionedBox and its
-    /// placeholder AbsoluteOrFixedPositionedFragment in its original tree position.
+    /// A reference to a Fragment which is shared between this `HoistedAbsolutelyPositionedBox`
+    /// and its placeholder `AbsoluteOrFixedPositionedFragment` in the original tree position.
     /// This will be used later in order to paint this hoisted box in tree order.
-    pub fragment_id: HoistedFragmentId,
+    pub fragment: ArcRefCell<Option<ArcRefCell<Fragment>>>,
 }
 
 #[derive(Clone, Debug)]
@@ -148,7 +134,7 @@ impl AbsolutelyPositionedBox {
                     box_offsets.block_end.clone(),
                 ),
             },
-            fragment_id: HoistedFragmentId::new(),
+            fragment: ArcRefCell::new(None),
         }
     }
 }
@@ -286,11 +272,7 @@ impl PositioningContext {
             hoisted_boxes = take_hoisted_boxes_pending_layout(self);
         }
 
-        new_fragment.children.extend(
-            laid_out_child_fragments
-                .into_iter()
-                .map(|fragment| ArcRefCell::new(fragment)),
-        );
+        new_fragment.children.extend(laid_out_child_fragments);
     }
 
     pub(crate) fn push(&mut self, box_: HoistedAbsolutelyPositionedBox) {
@@ -359,7 +341,7 @@ impl PositioningContext {
         &mut self,
         layout_context: &LayoutContext,
         initial_containing_block: &DefiniteContainingBlock,
-        fragments: &mut Vec<Fragment>,
+        fragments: &mut Vec<ArcRefCell<Fragment>>,
     ) {
         debug_assert!(self.for_nearest_positioned_ancestor.is_none());
 
@@ -384,7 +366,7 @@ impl HoistedAbsolutelyPositionedBox {
     pub(crate) fn layout_many(
         layout_context: &LayoutContext,
         boxes: &[Self],
-        fragments: &mut Vec<Fragment>,
+        fragments: &mut Vec<ArcRefCell<Fragment>>,
         for_nearest_containing_block_for_all_descendants: &mut Vec<HoistedAbsolutelyPositionedBox>,
         containing_block: &DefiniteContainingBlock,
     ) {
@@ -392,22 +374,27 @@ impl HoistedAbsolutelyPositionedBox {
             fragments.par_extend(boxes.par_iter().mapfold_reduce_into(
                 for_nearest_containing_block_for_all_descendants,
                 |for_nearest_containing_block_for_all_descendants, box_| {
-                    Fragment::Box(box_.layout(
+                    let new_fragment = ArcRefCell::new(Fragment::Box(box_.layout(
                         layout_context,
                         for_nearest_containing_block_for_all_descendants,
                         containing_block,
-                    ))
+                    )));
+
+                    *box_.fragment.borrow_mut() = Some(new_fragment.clone());
+                    new_fragment
                 },
                 Vec::new,
                 vec_append_owned,
             ))
         } else {
             fragments.extend(boxes.iter().map(|box_| {
-                Fragment::Box(box_.layout(
+                let new_fragment = ArcRefCell::new(Fragment::Box(box_.layout(
                     layout_context,
                     for_nearest_containing_block_for_all_descendants,
                     containing_block,
-                ))
+                )));
+                *box_.fragment.borrow_mut() = Some(new_fragment.clone());
+                new_fragment
             }))
         }
     }
@@ -567,7 +554,6 @@ impl HoistedAbsolutelyPositionedBox {
                     border,
                     margin,
                     CollapsedBlockMargins::zero(),
-                    Some(self.fragment_id),
                 )
             },
         )
diff --git a/tests/wpt/mozilla/meta-layout-2020/css/absolute_hypothetical_with_intervening_inline_block_a.html.ini b/tests/wpt/mozilla/meta-layout-2020/css/absolute_hypothetical_with_intervening_inline_block_a.html.ini
deleted file mode 100644
index 4ea853c0158..00000000000
--- a/tests/wpt/mozilla/meta-layout-2020/css/absolute_hypothetical_with_intervening_inline_block_a.html.ini
+++ /dev/null
@@ -1,2 +0,0 @@
-[absolute_hypothetical_with_intervening_inline_block_a.html]
-  expected: FAIL
diff --git a/tests/wpt/mozilla/meta-layout-2020/css/list_item_marker_around_float.html.ini b/tests/wpt/mozilla/meta-layout-2020/css/list_item_marker_around_float.html.ini
new file mode 100644
index 00000000000..70e3d2c12e8
--- /dev/null
+++ b/tests/wpt/mozilla/meta-layout-2020/css/list_item_marker_around_float.html.ini
@@ -0,0 +1,2 @@
+[list_item_marker_around_float.html]
+  expected: FAIL