layout_2020: Paint hoisted positioned fragments in tree order

Instead of painting hoisted position fragments in the order to which
they are hoisted, paint them in tree order and properly incorporate them
into the stacking context.

We do this by creating a placeholder fragment in the original tree position
of hoisted fragments. The ghost fragment contains an atomic id which
links back to the hoisted fragment in the containing block.

While building the stacking context, we keep track of containing blocks
and their children. When encountering a placeholder fragment we look at
the containing block's hoisted children in order to properly paint the
hoisted fragment.

One notable design modification in this change is that hoisted fragments
no longer need an AnonymousFragment as their parent. Instead they are
now direct children of the fragment that establishes their containing block.

10 files changed, 375 insertions, 103 deletions

diff --git a/components/layout_2020/Cargo.toml b/components/layout_2020/Cargo.toml
index 7d2f9e3311e..a4cbe4c4ea1 100644
--- a/components/layout_2020/Cargo.toml
+++ b/components/layout_2020/Cargo.toml
@@ -25,6 +25,7 @@ gfx_traits = {path = "../gfx_traits"}
 html5ever = "0.25"
 ipc-channel = "0.14"
 libc = "0.2"
+log = "0.4"
 msg = {path = "../msg"}
 mitochondria = "1.1.2"
 net_traits = {path = "../net_traits"}
diff --git a/components/layout_2020/display_list/mod.rs b/components/layout_2020/display_list/mod.rs
index 1d2bb10c838..e8361ce5e9f 100644
--- a/components/layout_2020/display_list/mod.rs
+++ b/components/layout_2020/display_list/mod.rs
@@ -40,9 +40,6 @@ pub struct DisplayListBuilder<'a> {
     /// The current SpatialId and ClipId information for this `DisplayListBuilder`.
     current_space_and_clip: wr::SpaceAndClipInfo,
 
-    /// The id of the nearest ancestor reference frame for this `DisplayListBuilder`.
-    nearest_reference_frame: wr::SpatialId,
-
     pub context: &'a LayoutContext<'a>,
     pub wr: wr::DisplayListBuilder,
 
@@ -61,7 +58,6 @@ impl<'a> DisplayListBuilder<'a> {
     ) -> Self {
         Self {
             current_space_and_clip: wr::SpaceAndClipInfo::root_scroll(pipeline_id),
-            nearest_reference_frame: wr::SpatialId::root_reference_frame(pipeline_id),
             is_contentful: false,
             context,
             wr: wr::DisplayListBuilder::new(pipeline_id, viewport_size),
@@ -72,18 +68,6 @@ impl<'a> DisplayListBuilder<'a> {
         // TODO(gw): Make use of the WR backface visibility functionality.
         wr::CommonItemProperties::new(clip_rect, self.current_space_and_clip)
     }
-
-    fn clipping_and_scrolling_scope<R>(&mut self, f: impl FnOnce(&mut Self) -> R) -> R {
-        let previous_space_and_clip = self.current_space_and_clip;
-        let previous_nearest_reference_frame = self.nearest_reference_frame;
-
-        let result = f(self);
-
-        self.current_space_and_clip = previous_space_and_clip;
-        self.nearest_reference_frame = previous_nearest_reference_frame;
-
-        result
-    }
 }
 
 impl Fragment {
@@ -94,6 +78,7 @@ impl Fragment {
     ) {
         match self {
             Fragment::Box(b) => BuilderForBoxFragment::new(b, containing_block).build(builder),
+            Fragment::AbsoluteOrFixedPositioned(_) => {},
             Fragment::Anonymous(_) => {},
             Fragment::Text(t) => {
                 builder.is_contentful = true;
diff --git a/components/layout_2020/display_list/stacking_context.rs b/components/layout_2020/display_list/stacking_context.rs
index 83299a38b52..87a170f499e 100644
--- a/components/layout_2020/display_list/stacking_context.rs
+++ b/components/layout_2020/display_list/stacking_context.rs
@@ -4,10 +4,14 @@
 
 use crate::display_list::conversions::ToWebRender;
 use crate::display_list::DisplayListBuilder;
-use crate::fragments::{AnonymousFragment, BoxFragment, Fragment};
+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 std::cmp::Ordering;
 use std::mem;
@@ -22,6 +26,90 @@ use style::values::specified::box_::DisplayOutside;
 use webrender_api as wr;
 use webrender_api::units::{LayoutPoint, LayoutTransform, LayoutVector2D};
 
+#[derive(Clone)]
+pub(crate) struct ContainingBlock<'a> {
+    /// The SpaceAndClipInfo that contains the children of the fragment that
+    /// established this containing block.
+    space_and_clip: wr::SpaceAndClipInfo,
+
+    /// 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, &'a Fragment>,
+}
+
+impl<'a> ContainingBlock<'a> {
+    pub(crate) fn new(
+        rect: &PhysicalRect<Length>,
+        space_and_clip: wr::SpaceAndClipInfo,
+        children: &'a Vec<Fragment>,
+    ) -> Self {
+        let mut hoisted_children = FnvHashMap::default();
+        for child in children {
+            if let Some(hoisted_fragment_id) = child.hoisted_fragment_id() {
+                hoisted_children.insert(*hoisted_fragment_id, child);
+            }
+        }
+
+        ContainingBlock {
+            space_and_clip,
+            rect: *rect,
+            hoisted_children,
+        }
+    }
+}
+
+#[derive(Clone)]
+pub(crate) struct ContainingBlockInfo<'a> {
+    /// The positioning rectangle established by the parent. This is sometimes
+    /// called the "containing block" in layout_2020.
+    pub rect: PhysicalRect<Length>,
+
+    /// The nearest real containing block at this point in the construction of
+    /// the stacking context tree.
+    pub nearest_containing_block: Option<ContainingBlock<'a>>,
+
+    /// The nearest containing block for all descendants at this point in the
+    /// stacking context tree. This containing blocks contains fixed position
+    /// elements.
+    pub containing_block_for_all_descendants: ContainingBlock<'a>,
+}
+
+pub(crate) struct StackingContextBuilder<'a> {
+    /// The current SpatialId and ClipId information for this `DisplayListBuilder`.
+    pub current_space_and_clip: wr::SpaceAndClipInfo,
+
+    /// The id of the nearest ancestor reference frame for this `DisplayListBuilder`.
+    nearest_reference_frame: wr::SpatialId,
+
+    wr: &'a mut wr::DisplayListBuilder,
+}
+
+impl<'a> StackingContextBuilder<'a> {
+    pub fn new(wr: &'a mut wr::DisplayListBuilder) -> Self {
+        Self {
+            current_space_and_clip: wr::SpaceAndClipInfo::root_scroll(wr.pipeline_id),
+            nearest_reference_frame: wr::SpatialId::root_reference_frame(wr.pipeline_id),
+            wr,
+        }
+    }
+
+    fn clipping_and_scrolling_scope<R>(&mut self, f: impl FnOnce(&mut Self) -> R) -> R {
+        let previous_space_and_clip = self.current_space_and_clip;
+        let previous_nearest_reference_frame = self.nearest_reference_frame;
+
+        let result = f(self);
+
+        self.current_space_and_clip = previous_space_and_clip;
+        self.nearest_reference_frame = previous_nearest_reference_frame;
+
+        result
+    }
+}
+
 #[derive(Clone, Copy, Eq, Ord, PartialEq, PartialOrd)]
 pub(crate) enum StackingContextSection {
     BackgroundsAndBorders,
@@ -228,28 +316,52 @@ impl<'a> StackingContext<'a> {
     }
 }
 
+#[derive(PartialEq)]
+pub(crate) enum StackingContextBuildMode {
+    IncludeHoisted,
+    SkipHoisted,
+}
+
 impl Fragment {
     pub(crate) fn build_stacking_context_tree<'a>(
         &'a self,
-        builder: &mut DisplayListBuilder,
-        containing_block: &PhysicalRect<Length>,
+        builder: &mut StackingContextBuilder,
+        containing_block_info: &ContainingBlockInfo<'a>,
         stacking_context: &mut StackingContext<'a>,
+        mode: StackingContextBuildMode,
     ) {
+        if mode == StackingContextBuildMode::SkipHoisted && self.is_hoisted() {
+            return;
+        }
+
         match self {
-            Fragment::Box(fragment) => fragment.build_stacking_context_tree(
-                self,
-                builder,
-                containing_block,
-                stacking_context,
-            ),
+            Fragment::Box(fragment) => {
+                fragment.build_stacking_context_tree(
+                    self,
+                    builder,
+                    containing_block_info,
+                    stacking_context,
+                );
+            },
+            Fragment::AbsoluteOrFixedPositioned(fragment) => {
+                fragment.build_stacking_context_tree(
+                    builder,
+                    containing_block_info,
+                    stacking_context,
+                );
+            },
             Fragment::Anonymous(fragment) => {
-                fragment.build_stacking_context_tree(builder, containing_block, stacking_context)
+                fragment.build_stacking_context_tree(
+                    builder,
+                    containing_block_info,
+                    stacking_context,
+                );
             },
             Fragment::Text(_) | Fragment::Image(_) => {
                 stacking_context.fragments.push(StackingContextFragment {
                     section: StackingContextSection::Content,
                     space_and_clip: builder.current_space_and_clip,
-                    containing_block: *containing_block,
+                    containing_block: containing_block_info.rect,
                     fragment: self,
                 });
             },
@@ -291,11 +403,35 @@ impl BoxFragment {
         StackingContextSection::BlockBackgroundsAndBorders
     }
 
+    fn build_containing_block<'a>(
+        &'a self,
+        builder: &mut StackingContextBuilder,
+        padding_rect: &PhysicalRect<Length>,
+        containing_block_info: &mut ContainingBlockInfo<'a>,
+    ) {
+        if !self.style.establishes_containing_block() {
+            return;
+        }
+
+        let new_containing_block =
+            ContainingBlock::new(padding_rect, builder.current_space_and_clip, &self.children);
+
+        if self
+            .style
+            .establishes_containing_block_for_all_descendants()
+        {
+            containing_block_info.nearest_containing_block = None;
+            containing_block_info.containing_block_for_all_descendants = new_containing_block;
+        } else {
+            containing_block_info.nearest_containing_block = Some(new_containing_block);
+        }
+    }
+
     fn build_stacking_context_tree<'a>(
         &'a self,
         fragment: &'a Fragment,
-        builder: &mut DisplayListBuilder,
-        containing_block: &PhysicalRect<Length>,
+        builder: &mut StackingContextBuilder,
+        containing_block_info: &ContainingBlockInfo<'a>,
         stacking_context: &mut StackingContext<'a>,
     ) {
         builder.clipping_and_scrolling_scope(|builder| {
@@ -307,7 +443,7 @@ impl BoxFragment {
                     self.build_stacking_context_tree_for_children(
                         fragment,
                         builder,
-                        *containing_block,
+                        containing_block_info,
                         stacking_context,
                     );
                     return;
@@ -318,7 +454,7 @@ impl BoxFragment {
             self.build_stacking_context_tree_for_children(
                 fragment,
                 builder,
-                *containing_block,
+                containing_block_info,
                 &mut child_stacking_context,
             );
 
@@ -343,46 +479,65 @@ impl BoxFragment {
     fn build_stacking_context_tree_for_children<'a>(
         &'a self,
         fragment: &'a Fragment,
-        builder: &mut DisplayListBuilder,
-        mut containing_block: PhysicalRect<Length>,
+        builder: &mut StackingContextBuilder,
+        containing_block_info: &ContainingBlockInfo<'a>,
         stacking_context: &mut StackingContext<'a>,
     ) {
         let relative_border_rect = self
             .border_rect()
-            .to_physical(self.style.writing_mode, &containing_block);
-        let border_rect = relative_border_rect.translate(containing_block.origin.to_vector());
+            .to_physical(self.style.writing_mode, &containing_block_info.rect);
+        let border_rect =
+            relative_border_rect.translate(containing_block_info.rect.origin.to_vector());
         let established_reference_frame =
             self.build_reference_frame_if_necessary(builder, &border_rect);
 
+        let mut new_containing_block_info = containing_block_info.clone();
+
         // WebRender reference frames establish a new coordinate system at their origin
         // (the border box of the fragment). We need to ensure that any coordinates we
         // give to WebRender in this reference frame are relative to the fragment border
         // box. We do this by adjusting the containing block origin.
         if established_reference_frame {
-            containing_block.origin = (-relative_border_rect.origin.to_vector()).to_point();
+            new_containing_block_info.rect.origin =
+                (-relative_border_rect.origin.to_vector()).to_point();
         }
 
         stacking_context.fragments.push(StackingContextFragment {
             space_and_clip: builder.current_space_and_clip,
             section: self.get_stacking_context_section(),
-            containing_block: containing_block,
+            containing_block: new_containing_block_info.rect,
             fragment,
         });
 
         // We want to build the scroll frame after the background and border, because
         // they shouldn't scroll with the rest of the box content.
-        self.build_scroll_frame_if_necessary(builder, &containing_block);
+        self.build_scroll_frame_if_necessary(builder, &new_containing_block_info);
 
-        let new_containing_block = self
+        let padding_rect = self
+            .padding_rect()
+            .to_physical(self.style.writing_mode, &new_containing_block_info.rect)
+            .translate(new_containing_block_info.rect.origin.to_vector());
+        new_containing_block_info.rect = self
             .content_rect
-            .to_physical(self.style.writing_mode, &containing_block)
-            .translate(containing_block.origin.to_vector());
+            .to_physical(self.style.writing_mode, &new_containing_block_info.rect)
+            .translate(new_containing_block_info.rect.origin.to_vector());
+
+        // If we establish a containing block we use the padding rect as the offset. This is
+        // because for all but the initial containing block, the padding rect determines
+        // the size and position of the containing block.
+        self.build_containing_block(builder, &padding_rect, &mut new_containing_block_info);
+
         for child in &self.children {
-            child.build_stacking_context_tree(builder, &new_containing_block, stacking_context);
+            child.build_stacking_context_tree(
+                builder,
+                &new_containing_block_info,
+                stacking_context,
+                StackingContextBuildMode::SkipHoisted,
+            );
         }
     }
 
-    fn adjust_spatial_id_for_positioning(&self, builder: &mut DisplayListBuilder) {
+    fn adjust_spatial_id_for_positioning(&self, builder: &mut StackingContextBuilder) {
         if self.style.get_box().position != ComputedPosition::Fixed {
             return;
         }
@@ -393,10 +548,10 @@ impl BoxFragment {
         builder.current_space_and_clip.spatial_id = builder.nearest_reference_frame;
     }
 
-    fn build_scroll_frame_if_necessary(
+    fn build_scroll_frame_if_necessary<'a>(
         &self,
-        builder: &mut DisplayListBuilder,
-        containing_block: &PhysicalRect<Length>,
+        builder: &mut StackingContextBuilder,
+        containing_block_info: &ContainingBlockInfo<'a>,
     ) {
         let overflow_x = self.style.get_box().overflow_x;
         let overflow_y = self.style.get_box().overflow_y;
@@ -419,8 +574,8 @@ impl BoxFragment {
 
             let padding_rect = self
                 .padding_rect()
-                .to_physical(self.style.writing_mode, containing_block)
-                .translate(containing_block.origin.to_vector())
+                .to_physical(self.style.writing_mode, &containing_block_info.rect)
+                .translate(containing_block_info.rect.origin.to_vector())
                 .to_webrender();
             builder.current_space_and_clip = builder.wr.define_scroll_frame(
                 &original_scroll_and_clip_info,
@@ -439,7 +594,7 @@ impl BoxFragment {
     /// a reference was built and `false` otherwise.
     fn build_reference_frame_if_necessary(
         &self,
-        builder: &mut DisplayListBuilder,
+        builder: &mut StackingContextBuilder,
         border_rect: &PhysicalRect<Length>,
     ) -> bool {
         if !self.style.has_transform_or_perspective() {
@@ -562,16 +717,63 @@ impl BoxFragment {
 impl AnonymousFragment {
     fn build_stacking_context_tree<'a>(
         &'a self,
-        builder: &mut DisplayListBuilder,
-        containing_block: &PhysicalRect<Length>,
+        builder: &mut StackingContextBuilder,
+        containing_block_info: &ContainingBlockInfo<'a>,
         stacking_context: &mut StackingContext<'a>,
     ) {
-        let new_containing_block = self
+        let mut new_containing_block_info = containing_block_info.clone();
+        new_containing_block_info.rect = self
             .rect
-            .to_physical(self.mode, containing_block)
-            .translate(containing_block.origin.to_vector());
+            .to_physical(self.mode, &containing_block_info.rect)
+            .translate(containing_block_info.rect.origin.to_vector());
         for child in &self.children {
-            child.build_stacking_context_tree(builder, &new_containing_block, stacking_context);
+            child.build_stacking_context_tree(
+                builder,
+                &new_containing_block_info,
+                stacking_context,
+                StackingContextBuildMode::SkipHoisted,
+            );
+        }
+    }
+}
+
+impl AbsoluteOrFixedPositionedFragment {
+    fn build_stacking_context_tree<'a>(
+        &'a self,
+        builder: &mut StackingContextBuilder,
+        containing_block_info: &ContainingBlockInfo<'a>,
+        stacking_context: &mut StackingContext<'a>,
+    ) {
+        let mut build_for_containing_block = |containing_block: &ContainingBlock<'a>| {
+            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.build_stacking_context_tree(
+                    builder,
+                    &new_containing_block_info,
+                    stacking_context,
+                    StackingContextBuildMode::IncludeHoisted,
+                );
+            });
+
+            return true;
+        };
+
+        if let Some(containing_block) = containing_block_info.nearest_containing_block.as_ref() {
+            if build_for_containing_block(containing_block) {
+                return;
+            }
+        }
+
+        if !build_for_containing_block(&containing_block_info.containing_block_for_all_descendants)
+        {
+            warn!("Could not find containing block of hoisted positioned child!");
         }
     }
 }
diff --git a/components/layout_2020/flow/inline.rs b/components/layout_2020/flow/inline.rs
index a33e5d8932a..bd8f5bc784f 100644
--- a/components/layout_2020/flow/inline.rs
+++ b/components/layout_2020/flow/inline.rs
@@ -6,8 +6,10 @@ use crate::context::LayoutContext;
 use crate::flow::float::FloatBox;
 use crate::flow::FlowLayout;
 use crate::formatting_contexts::IndependentFormattingContext;
-use crate::fragments::CollapsedBlockMargins;
-use crate::fragments::{AnonymousFragment, BoxFragment, DebugId, Fragment, TextFragment};
+use crate::fragments::{
+    AbsoluteOrFixedPositionedFragment, AnonymousFragment, BoxFragment, CollapsedBlockMargins,
+    DebugId, Fragment, TextFragment,
+};
 use crate::geom::flow_relative::{Rect, Sides, Vec2};
 use crate::positioned::{relative_adjustement, AbsolutelyPositionedBox, PositioningContext};
 use crate::sizing::ContentSizes;
@@ -254,8 +256,14 @@ impl InlineFormattingContext {
                                     panic!("display:none does not generate an abspos box")
                                 },
                             };
-                        ifc.positioning_context
-                            .push(box_.to_hoisted(initial_start_corner, tree_rank));
+                        let hoisted_fragment = box_.to_hoisted(initial_start_corner, tree_rank);
+                        let hoisted_fragment_id = hoisted_fragment.fragment_id;
+                        ifc.positioning_context.push(hoisted_fragment);
+                        ifc.lines
+                            .fragments
+                            .push(Fragment::AbsoluteOrFixedPositioned(
+                                AbsoluteOrFixedPositionedFragment(hoisted_fragment_id),
+                            ));
                     },
                     InlineLevelBox::OutOfFlowFloatBox(_box_) => {
                         // TODO
@@ -333,7 +341,7 @@ impl Lines {
         };
         if move_by > Length::zero() {
             for fragment in &mut line_contents {
-                fragment.position_mut().inline += move_by;
+                fragment.offset_inline(&move_by);
             }
         }
         let start_corner = Vec2 {
@@ -426,6 +434,7 @@ 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 {
@@ -488,6 +497,7 @@ fn layout_atomic<'box_tree>(
                 border,
                 margin,
                 CollapsedBlockMargins::zero(),
+                None, // hoisted_fragment_id
             )
         },
         Err(non_replaced) => {
@@ -563,6 +573,7 @@ fn layout_atomic<'box_tree>(
                 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 bc50177fe1e..e15947f52b0 100644
--- a/components/layout_2020/flow/mod.rs
+++ b/components/layout_2020/flow/mod.rs
@@ -8,7 +8,7 @@ use crate::context::LayoutContext;
 use crate::flow::float::{FloatBox, FloatContext};
 use crate::flow::inline::InlineFormattingContext;
 use crate::formatting_contexts::{IndependentFormattingContext, IndependentLayout, NonReplacedIFC};
-use crate::fragments::{AnonymousFragment, BoxFragment};
+use crate::fragments::{AbsoluteOrFixedPositionedFragment, AnonymousFragment, BoxFragment};
 use crate::fragments::{CollapsedBlockMargins, CollapsedMargin, Fragment};
 use crate::geom::flow_relative::{Rect, Sides, Vec2};
 use crate::positioned::{AbsolutelyPositionedBox, PositioningContext};
@@ -176,14 +176,7 @@ fn layout_block_level_children<'a>(
                     placement_state.current_margin.solve() + fragment_block_size;
                 placement_state.current_margin = fragment_block_margins.end;
             },
-            Fragment::Anonymous(fragment) => {
-                // FIXME(nox): Margin collapsing for hypothetical boxes of
-                // abspos elements is probably wrong.
-                assert!(fragment.children.is_empty());
-                assert_eq!(fragment.rect.size.block, Length::zero());
-                fragment.rect.start_corner.block +=
-                    placement_state.current_block_direction_position;
-            },
+            Fragment::Anonymous(_) | Fragment::AbsoluteOrFixedPositioned(_) => {},
             _ => unreachable!(),
         }
     }
@@ -321,9 +314,11 @@ impl BlockLevelBox {
                 ))
             },
             BlockLevelBox::OutOfFlowAbsolutelyPositionedBox(box_) => {
-                positioning_context.push(box_.to_hoisted(Vec2::zero(), tree_rank));
-                Fragment::Anonymous(AnonymousFragment::no_op(
-                    containing_block.style.writing_mode,
+                let hoisted_fragment = box_.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,
                 ))
             },
             BlockLevelBox::OutOfFlowFloatBox(_box_) => {
@@ -505,6 +500,7 @@ fn layout_in_flow_non_replaced_block_level<'a>(
         border,
         margin,
         block_margins_collapsed_with_children,
+        None, // hoisted_fragment_id
     )
 }
 
@@ -556,6 +552,7 @@ 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 6932e66acf1..0b93701b01b 100644
--- a/components/layout_2020/flow/root.rs
+++ b/components/layout_2020/flow/root.rs
@@ -3,7 +3,10 @@
  * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
 
 use crate::context::LayoutContext;
-use crate::display_list::stacking_context::StackingContext;
+use crate::display_list::stacking_context::{
+    ContainingBlock, ContainingBlockInfo, StackingContext, StackingContextBuildMode,
+    StackingContextBuilder,
+};
 use crate::dom_traversal::{Contents, NodeExt};
 use crate::flow::construct::ContainsFloats;
 use crate::flow::float::FloatBox;
@@ -186,12 +189,26 @@ impl BoxTreeRoot {
 impl FragmentTreeRoot {
     pub fn build_display_list(&self, builder: &mut crate::display_list::DisplayListBuilder) {
         let mut stacking_context = StackingContext::create_root();
-        for fragment in &self.children {
-            fragment.build_stacking_context_tree(
-                builder,
-                &self.initial_containing_block,
-                &mut stacking_context,
-            );
+        {
+            let mut stacking_context_builder = StackingContextBuilder::new(&mut builder.wr);
+            let containing_block_info = ContainingBlockInfo {
+                rect: self.initial_containing_block,
+                nearest_containing_block: None,
+                containing_block_for_all_descendants: ContainingBlock::new(
+                    &self.initial_containing_block,
+                    stacking_context_builder.current_space_and_clip,
+                    &self.children,
+                ),
+            };
+
+            for fragment in &self.children {
+                fragment.build_stacking_context_tree(
+                    &mut stacking_context_builder,
+                    &containing_block_info,
+                    &mut stacking_context,
+                    StackingContextBuildMode::SkipHoisted,
+                );
+            }
         }
 
         stacking_context.sort();
@@ -268,6 +285,7 @@ impl FragmentTreeRoot {
                 Fragment::Box(fragment) if fragment.tag == requested_node => fragment
                     .border_rect()
                     .to_physical(fragment.style.writing_mode, &containing_block),
+                Fragment::AbsoluteOrFixedPositioned(_) => PhysicalRect::zero(),
                 Fragment::Text(fragment) if fragment.tag == requested_node => fragment
                     .rect
                     .to_physical(fragment.parent_style.writing_mode, &containing_block),
@@ -301,6 +319,7 @@ impl FragmentTreeRoot {
                 Fragment::Box(fragment) if fragment.tag == requested_node => {
                     (&fragment.style, fragment.padding_rect())
                 },
+                Fragment::AbsoluteOrFixedPositioned(_) |
                 Fragment::Box(_) |
                 Fragment::Text(_) |
                 Fragment::Image(_) |
diff --git a/components/layout_2020/fragments.rs b/components/layout_2020/fragments.rs
index fcf0bf21d84..70c65dd470d 100644
--- a/components/layout_2020/fragments.rs
+++ b/components/layout_2020/fragments.rs
@@ -2,10 +2,11 @@
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
 
-use crate::geom::flow_relative::{Rect, Sides, Vec2};
+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::text::glyph::GlyphStore;
 use gfx_traits::print_tree::PrintTree;
 #[cfg(not(debug_assertions))]
@@ -24,11 +25,15 @@ use webrender_api::{FontInstanceKey, ImageKey};
 pub(crate) enum Fragment {
     Box(BoxFragment),
     Anonymous(AnonymousFragment),
+    AbsoluteOrFixedPositioned(AbsoluteOrFixedPositionedFragment),
     Text(TextFragment),
     Image(ImageFragment),
 }
 
 #[derive(Serialize)]
+pub(crate) struct AbsoluteOrFixedPositionedFragment(pub HoistedFragmentId);
+
+#[derive(Serialize)]
 pub(crate) struct BoxFragment {
     pub tag: OpaqueNode,
     pub debug_id: DebugId,
@@ -49,6 +54,9 @@ pub(crate) struct BoxFragment {
 
     /// The scrollable overflow of this box fragment.
     pub scrollable_overflow_from_children: PhysicalRect<Length>,
+
+    /// XXX Add thsi
+    pub hoisted_fragment_id: Option<HoistedFragmentId>,
 }
 
 #[derive(Serialize)]
@@ -100,18 +108,22 @@ pub(crate) struct ImageFragment {
 }
 
 impl Fragment {
-    pub fn position_mut(&mut self) -> &mut Vec2<Length> {
-        match self {
+    pub fn offset_inline(&mut self, offset: &Length) {
+        let position = match self {
             Fragment::Box(f) => &mut f.content_rect.start_corner,
+            Fragment::AbsoluteOrFixedPositioned(_) => return,
             Fragment::Anonymous(f) => &mut f.rect.start_corner,
             Fragment::Text(f) => &mut f.rect.start_corner,
             Fragment::Image(f) => &mut f.rect.start_corner,
-        }
+        };
+
+        position.inline += *offset;
     }
 
     pub fn print(&self, tree: &mut PrintTree) {
         match self {
             Fragment::Box(fragment) => fragment.print(tree),
+            Fragment::AbsoluteOrFixedPositioned(fragment) => fragment.print(tree),
             Fragment::Anonymous(fragment) => fragment.print(tree),
             Fragment::Text(fragment) => fragment.print(tree),
             Fragment::Image(fragment) => fragment.print(tree),
@@ -124,6 +136,7 @@ impl Fragment {
         let containing_block = PhysicalRect::zero();
         match self {
             Fragment::Box(fragment) => fragment.scrollable_overflow_for_parent(&containing_block),
+            Fragment::AbsoluteOrFixedPositioned(_) => PhysicalRect::zero(),
             Fragment::Anonymous(fragment) => fragment.scrollable_overflow.clone(),
             Fragment::Text(fragment) => fragment
                 .rect
@@ -133,6 +146,26 @@ impl Fragment {
                 .to_physical(fragment.style.writing_mode, &containing_block),
         }
     }
+
+    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,
+        }
+    }
+}
+
+impl AbsoluteOrFixedPositionedFragment {
+    pub fn print(&self, tree: &mut PrintTree) {
+        tree.add_item(format!("AbsoluteOrFixedPositionedFragment({:?})", self.0));
+    }
 }
 
 impl AnonymousFragment {
@@ -189,6 +222,7 @@ impl BoxFragment {
         border: Sides<Length>,
         margin: Sides<Length>,
         block_margins_collapsed_with_children: CollapsedBlockMargins,
+        hoisted_fragment_id: Option<HoistedFragmentId>,
     ) -> BoxFragment {
         let scrollable_overflow_from_children =
             children.iter().fold(PhysicalRect::zero(), |acc, child| {
@@ -205,6 +239,7 @@ impl BoxFragment {
             margin,
             block_margins_collapsed_with_children,
             scrollable_overflow_from_children,
+            hoisted_fragment_id,
         }
     }
 
@@ -242,7 +277,8 @@ impl BoxFragment {
                 \nborder rect={:?}\
                 \nscrollable_overflow={:?}\
                 \noverflow={:?} / {:?}\
-                \nstyle={:p}",
+                \nstyle={:p}\
+                \nhoisted_id={:?}",
             self.content_rect,
             self.padding_rect(),
             self.border_rect(),
@@ -250,6 +286,7 @@ 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/lib.rs b/components/layout_2020/lib.rs
index 62e1f1b9470..610c5306f53 100644
--- a/components/layout_2020/lib.rs
+++ b/components/layout_2020/lib.rs
@@ -6,6 +6,8 @@
 #![feature(exact_size_is_empty)]
 
 #[macro_use]
+extern crate log;
+#[macro_use]
 extern crate serde;
 
 pub mod context;
diff --git a/components/layout_2020/positioned.rs b/components/layout_2020/positioned.rs
index a0f0aac1c94..b40a3b8b1ab 100644
--- a/components/layout_2020/positioned.rs
+++ b/components/layout_2020/positioned.rs
@@ -5,7 +5,7 @@
 use crate::context::LayoutContext;
 use crate::dom_traversal::{Contents, NodeExt};
 use crate::formatting_contexts::IndependentFormattingContext;
-use crate::fragments::{AnonymousFragment, BoxFragment, CollapsedBlockMargins, Fragment};
+use crate::fragments::{BoxFragment, CollapsedBlockMargins, Fragment};
 use crate::geom::flow_relative::{Rect, Sides, Vec2};
 use crate::sizing::ContentSizesRequest;
 use crate::style_ext::{ComputedValuesExt, DisplayInside};
@@ -13,11 +13,24 @@ 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::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,
@@ -43,6 +56,11 @@ pub(crate) struct HoistedAbsolutelyPositionedBox<'box_tree> {
     pub(crate) tree_rank: usize,
 
     box_offsets: Vec2<AbsoluteBoxOffsets>,
+
+    /// The id which is shared between this HoistedAbsolutelyPositionedBox and its
+    /// placeholder AbsoluteOrFixedPositionedFragment in its original tree position.
+    /// This will be used later in order to paint this hoisted box in tree order.
+    pub fragment_id: HoistedFragmentId,
 }
 
 #[derive(Clone, Debug)]
@@ -127,6 +145,7 @@ impl AbsolutelyPositionedBox {
                     box_offsets.block_end.clone(),
                 ),
             },
+            fragment_id: HoistedFragmentId::new(),
         }
     }
 }
@@ -273,14 +292,7 @@ impl<'box_tree> PositioningContext<'box_tree> {
             )
         }
 
-        new_fragment
-            .children
-            .push(Fragment::Anonymous(AnonymousFragment::new(
-                padding_rect,
-                new_child_fragments,
-                new_fragment.style.writing_mode,
-            )));
-
+        new_fragment.children.extend(new_child_fragments);
         new_fragment
     }
 
@@ -395,13 +407,7 @@ impl<'box_tree> PositioningContext<'box_tree> {
                 &mut self.for_nearest_containing_block_for_all_descendants,
                 &containing_block,
             );
-            positioned_box_fragment
-                .children
-                .push(Fragment::Anonymous(AnonymousFragment::new(
-                    padding_rect,
-                    children,
-                    positioned_box_fragment.style.writing_mode,
-                )))
+            positioned_box_fragment.children.extend(children);
         }
     }
 }
@@ -599,6 +605,7 @@ impl<'box_tree> HoistedAbsolutelyPositionedBox<'box_tree> {
                     border,
                     margin,
                     CollapsedBlockMargins::zero(),
+                    Some(self.fragment_id),
                 )
             },
         )
@@ -715,14 +722,16 @@ fn adjust_static_positions(
     tree_rank_in_parent: usize,
 ) {
     for abspos_fragment in absolutely_positioned_fragments {
-        let child_fragment_rect = match &child_fragments[abspos_fragment.tree_rank] {
+        let original_tree_rank = abspos_fragment.tree_rank;
+        abspos_fragment.tree_rank = tree_rank_in_parent;
+
+        let child_fragment_rect = match &child_fragments[original_tree_rank] {
             Fragment::Box(b) => &b.content_rect,
+            Fragment::AbsoluteOrFixedPositioned(_) => continue,
             Fragment::Anonymous(a) => &a.rect,
             _ => unreachable!(),
         };
 
-        abspos_fragment.tree_rank = tree_rank_in_parent;
-
         if let AbsoluteBoxOffsets::StaticStart { start } = &mut abspos_fragment.box_offsets.inline {
             *start += child_fragment_rect.start_corner.inline;
         }
diff --git a/components/layout_2020/style_ext.rs b/components/layout_2020/style_ext.rs
index 44245e2c89d..7ed41d1cd91 100644
--- a/components/layout_2020/style_ext.rs
+++ b/components/layout_2020/style_ext.rs
@@ -56,6 +56,7 @@ pub(crate) trait ComputedValuesExt {
     fn has_transform_or_perspective(&self) -> bool;
     fn effective_z_index(&self) -> i32;
     fn establishes_stacking_context(&self) -> bool;
+    fn establishes_containing_block(&self) -> bool;
     fn establishes_containing_block_for_all_descendants(&self) -> bool;
 }
 
@@ -233,6 +234,14 @@ impl ComputedValuesExt for ComputedValues {
         !self.get_position().z_index.is_auto()
     }
 
+    fn establishes_containing_block(&self) -> bool {
+        if self.establishes_containing_block_for_all_descendants() {
+            return true;
+        }
+
+        self.clone_position() != ComputedPosition::Static
+    }
+
     /// Returns true if this style establishes a containing block for all descendants
     /// including fixed and absolutely positioned ones.
     fn establishes_containing_block_for_all_descendants(&self) -> bool {