Auto merge of #25273 - servo:fixedpos, r=nox

 Layout `position: fixed` in the initial containing block

1 files changed, 326 insertions, 122 deletions

diff --git a/components/layout_2020/positioned.rs b/components/layout_2020/positioned.rs
index b9c64ea54d3..cfe615ae27d 100644
--- a/components/layout_2020/positioned.rs
+++ b/components/layout_2020/positioned.rs
@@ -10,8 +10,10 @@ use crate::geom::flow_relative::{Rect, Sides, Vec2};
 use crate::sizing::ContentSizesRequest;
 use crate::style_ext::{ComputedValuesExt, DisplayInside};
 use crate::{ContainingBlock, DefiniteContainingBlock};
-use rayon::iter::{IntoParallelRefIterator, ParallelIterator};
+use rayon::iter::{IntoParallelRefIterator, ParallelExtend};
+use rayon_croissant::ParallelIteratorExt;
 use servo_arc::Arc;
+use style::computed_values::position::T as Position;
 use style::properties::ComputedValues;
 use style::values::computed::{Length, LengthOrAuto, LengthPercentage, LengthPercentageOrAuto};
 use style::Zero;
@@ -21,9 +23,14 @@ pub(crate) struct AbsolutelyPositionedBox {
     pub contents: IndependentFormattingContext,
 }
 
+pub(crate) struct PositioningContext<'box_tree> {
+    for_nearest_positioned_ancestor: Option<Vec<HoistedAbsolutelyPositionedBox<'box_tree>>>,
+    for_initial_containing_block: Vec<HoistedAbsolutelyPositionedBox<'box_tree>>,
+}
+
 #[derive(Debug)]
-pub(crate) struct AbsolutelyPositionedFragment<'box_> {
-    absolutely_positioned_box: &'box_ AbsolutelyPositionedBox,
+pub(crate) struct HoistedAbsolutelyPositionedBox<'box_tree> {
+    absolutely_positioned_box: &'box_tree AbsolutelyPositionedBox,
 
     /// The rank of the child from which this absolutely positioned fragment
     /// came from, when doing the layout of a block container. Used to compute
@@ -77,11 +84,11 @@ impl AbsolutelyPositionedBox {
         }
     }
 
-    pub(crate) fn layout<'a>(
-        &'a self,
+    pub(crate) fn layout(
+        &self,
         initial_start_corner: Vec2<Length>,
         tree_rank: usize,
-    ) -> AbsolutelyPositionedFragment {
+    ) -> HoistedAbsolutelyPositionedBox {
         fn absolute_box_offsets(
             initial_static_start: Length,
             start: LengthPercentageOrAuto,
@@ -98,7 +105,7 @@ impl AbsolutelyPositionedBox {
         }
 
         let box_offsets = self.contents.style.box_offsets();
-        AbsolutelyPositionedFragment {
+        HoistedAbsolutelyPositionedBox {
             absolutely_positioned_box: self,
             tree_rank,
             box_offsets: Vec2 {
@@ -117,46 +124,217 @@ impl AbsolutelyPositionedBox {
     }
 }
 
-impl<'a> AbsolutelyPositionedFragment<'a> {
-    pub(crate) fn in_positioned_containing_block(
+impl<'box_tree> PositioningContext<'box_tree> {
+    pub(crate) fn new_for_initial_containing_block() -> Self {
+        Self {
+            for_nearest_positioned_ancestor: None,
+            for_initial_containing_block: Vec::new(),
+        }
+    }
+
+    pub(crate) fn new_for_rayon(has_positioned_ancestor: bool) -> Self {
+        Self {
+            for_nearest_positioned_ancestor: if has_positioned_ancestor {
+                Some(Vec::new())
+            } else {
+                None
+            },
+            for_initial_containing_block: Vec::new(),
+        }
+    }
+
+    pub(crate) fn has_positioned_ancestor(&self) -> bool {
+        self.for_nearest_positioned_ancestor.is_some()
+    }
+
+    pub(crate) fn for_maybe_position_relative(
+        &mut self,
         layout_context: &LayoutContext,
-        absolute: &[Self],
-        fragments: &mut Vec<Fragment>,
-        content_rect_size: &Vec2<Length>,
-        padding: &Sides<Length>,
+        containing_block: &ContainingBlock,
         style: &ComputedValues,
+        f: impl FnOnce(&mut Self) -> BoxFragment,
+    ) -> BoxFragment {
+        if style.clone_position() == Position::Relative {
+            let mut fragment =
+                // Establing a containing block for absolutely positioned descendants
+                Self::for_positioned(layout_context, &mut self.for_initial_containing_block, f);
+
+            fragment.content_rect.start_corner += &relative_adjustement(style, containing_block);
+            fragment
+        } else {
+            f(self)
+        }
+    }
+
+    fn for_positioned(
+        layout_context: &LayoutContext,
+        for_initial_containing_block: &mut Vec<HoistedAbsolutelyPositionedBox<'box_tree>>,
+        f: impl FnOnce(&mut Self) -> BoxFragment,
+    ) -> BoxFragment {
+        let mut new = Self {
+            for_nearest_positioned_ancestor: Some(Vec::new()),
+            for_initial_containing_block: std::mem::take(for_initial_containing_block),
+        };
+        let mut positioned_box_fragment = f(&mut new);
+        new.layout_in_positioned_ancestor(layout_context, &mut positioned_box_fragment);
+        *for_initial_containing_block = new.for_initial_containing_block;
+        positioned_box_fragment
+    }
+
+    pub(crate) fn push(&mut self, box_: HoistedAbsolutelyPositionedBox<'box_tree>) {
+        if let Some(nearest) = &mut self.for_nearest_positioned_ancestor {
+            match box_
+                .absolutely_positioned_box
+                .contents
+                .style
+                .clone_position()
+            {
+                Position::Fixed => {}, // fall through
+                Position::Absolute => return nearest.push(box_),
+                Position::Static | Position::Relative => unreachable!(),
+            }
+        }
+        self.for_initial_containing_block.push(box_)
+    }
+
+    pub(crate) fn append(&mut self, other: Self) {
+        vec_append_owned(
+            &mut self.for_initial_containing_block,
+            other.for_initial_containing_block,
+        );
+        match (
+            self.for_nearest_positioned_ancestor.as_mut(),
+            other.for_nearest_positioned_ancestor,
+        ) {
+            (Some(a), Some(b)) => vec_append_owned(a, b),
+            (None, None) => {},
+            _ => unreachable!(),
+        }
+    }
+
+    pub(crate) fn adjust_static_positions(
+        &mut self,
+        tree_rank_in_parent: usize,
+        f: impl FnOnce(&mut Self) -> Vec<Fragment>,
+    ) -> Vec<Fragment> {
+        let for_icb_so_far = self.for_initial_containing_block.len();
+        let for_nearest_so_far = self
+            .for_nearest_positioned_ancestor
+            .as_ref()
+            .map(|v| v.len());
+
+        let fragments = f(self);
+
+        adjust_static_positions(
+            &mut self.for_initial_containing_block[for_icb_so_far..],
+            &fragments,
+            tree_rank_in_parent,
+        );
+        if let Some(nearest) = &mut self.for_nearest_positioned_ancestor {
+            adjust_static_positions(
+                &mut nearest[for_nearest_so_far.unwrap()..],
+                &fragments,
+                tree_rank_in_parent,
+            );
+        }
+        fragments
+    }
+
+    pub(crate) fn layout_in_initial_containing_block(
+        &mut self,
+        layout_context: &LayoutContext,
+        initial_containing_block: &DefiniteContainingBlock,
+        fragments: &mut Vec<Fragment>,
     ) {
-        if absolute.is_empty() {
-            return;
+        debug_assert!(self.for_nearest_positioned_ancestor.is_none());
+
+        // Loop because it’s possible that we discover (the static position of)
+        // more absolutely-positioned boxes while doing layout for others.
+        while !self.for_initial_containing_block.is_empty() {
+            HoistedAbsolutelyPositionedBox::layout_many(
+                layout_context,
+                &std::mem::take(&mut self.for_initial_containing_block),
+                fragments,
+                &mut self.for_initial_containing_block,
+                initial_containing_block,
+            )
         }
-        let padding_rect = Rect {
-            size: content_rect_size.clone(),
-            // Ignore the content rect’s position in its own containing block:
-            start_corner: Vec2::zero(),
+    }
+
+    fn layout_in_positioned_ancestor(
+        &mut self,
+        layout_context: &LayoutContext,
+        positioned_box_fragment: &mut BoxFragment,
+    ) {
+        let for_here = self.for_nearest_positioned_ancestor.take().unwrap();
+        if !for_here.is_empty() {
+            let padding_rect = Rect {
+                size: positioned_box_fragment.content_rect.size.clone(),
+                // Ignore the content rect’s position in its own containing block:
+                start_corner: Vec2::zero(),
+            }
+            .inflate(&positioned_box_fragment.padding);
+            let containing_block = DefiniteContainingBlock {
+                size: padding_rect.size.clone(),
+                style: &positioned_box_fragment.style,
+            };
+            let mut children = Vec::new();
+            HoistedAbsolutelyPositionedBox::layout_many(
+                layout_context,
+                &for_here,
+                &mut children,
+                &mut self.for_initial_containing_block,
+                &containing_block,
+            );
+            positioned_box_fragment
+                .children
+                .push(Fragment::Anonymous(AnonymousFragment {
+                    children,
+                    rect: padding_rect,
+                    mode: positioned_box_fragment.style.writing_mode,
+                }))
         }
-        .inflate(&padding);
-        let containing_block = DefiniteContainingBlock {
-            size: padding_rect.size.clone(),
-            style,
-        };
-        let map = |a: &AbsolutelyPositionedFragment| a.layout(layout_context, &containing_block);
-        let children = if layout_context.use_rayon {
-            absolute.par_iter().map(map).collect()
+    }
+}
+
+impl<'box_tree> HoistedAbsolutelyPositionedBox<'box_tree> {
+    pub(crate) fn layout_many(
+        layout_context: &LayoutContext,
+        boxes: &[Self],
+        fragments: &mut Vec<Fragment>,
+        for_initial_containing_block: &mut Vec<HoistedAbsolutelyPositionedBox<'box_tree>>,
+        containing_block: &DefiniteContainingBlock,
+    ) {
+        if layout_context.use_rayon {
+            fragments.par_extend(boxes.par_iter().mapfold_reduce_into(
+                for_initial_containing_block,
+                |for_initial_containing_block, box_| {
+                    Fragment::Box(box_.layout(
+                        layout_context,
+                        for_initial_containing_block,
+                        containing_block,
+                    ))
+                },
+                Vec::new,
+                vec_append_owned,
+            ))
         } else {
-            absolute.iter().map(map).collect()
-        };
-        fragments.push(Fragment::Anonymous(AnonymousFragment {
-            children,
-            rect: padding_rect,
-            mode: style.writing_mode,
-        }))
+            fragments.extend(boxes.iter().map(|box_| {
+                Fragment::Box(box_.layout(
+                    layout_context,
+                    for_initial_containing_block,
+                    containing_block,
+                ))
+            }))
+        }
     }
 
     pub(crate) fn layout(
         &self,
         layout_context: &LayoutContext,
+        for_initial_containing_block: &mut Vec<HoistedAbsolutelyPositionedBox<'box_tree>>,
         containing_block: &DefiniteContainingBlock,
-    ) -> Fragment {
+    ) -> BoxFragment {
         let style = &self.absolutely_positioned_box.contents.style;
         let cbis = containing_block.size.inline;
         let cbbs = containing_block.size.block;
@@ -216,95 +394,89 @@ impl<'a> AbsolutelyPositionedFragment<'a> {
             block_end: block_axis.margin_end,
         };
 
-        let mut absolutely_positioned_fragments = Vec::new();
-        let (size, mut fragments) = match self.absolutely_positioned_box.contents.as_replaced() {
-            Ok(replaced) => {
-                // https://drafts.csswg.org/css2/visudet.html#abs-replaced-width
-                // https://drafts.csswg.org/css2/visudet.html#abs-replaced-height
-                let style = &self.absolutely_positioned_box.contents.style;
-                let size = replaced_used_size.unwrap();
-                let fragments = replaced.make_fragments(style, size.clone());
-                (size, fragments)
-            },
-            Err(non_replaced) => {
-                // https://drafts.csswg.org/css2/visudet.html#abs-non-replaced-width
-                // https://drafts.csswg.org/css2/visudet.html#abs-non-replaced-height
-                let inline_size = inline_axis.size.auto_is(|| {
-                    let available_size = match inline_axis.anchor {
-                        Anchor::Start(start) => {
-                            cbis - start - pb.inline_sum() - margin.inline_sum()
-                        },
-                        Anchor::End(end) => cbis - end - pb.inline_sum() - margin.inline_sum(),
+        let for_icb = for_initial_containing_block;
+        PositioningContext::for_positioned(layout_context, for_icb, |positioning_context| {
+            let size;
+            let fragments;
+            match self.absolutely_positioned_box.contents.as_replaced() {
+                Ok(replaced) => {
+                    // https://drafts.csswg.org/css2/visudet.html#abs-replaced-width
+                    // https://drafts.csswg.org/css2/visudet.html#abs-replaced-height
+                    let style = &self.absolutely_positioned_box.contents.style;
+                    size = replaced_used_size.unwrap();
+                    fragments = replaced.make_fragments(style, size.clone());
+                },
+                Err(non_replaced) => {
+                    // https://drafts.csswg.org/css2/visudet.html#abs-non-replaced-width
+                    // https://drafts.csswg.org/css2/visudet.html#abs-non-replaced-height
+                    let inline_size = inline_axis.size.auto_is(|| {
+                        let available_size = match inline_axis.anchor {
+                            Anchor::Start(start) => {
+                                cbis - start - pb.inline_sum() - margin.inline_sum()
+                            },
+                            Anchor::End(end) => cbis - end - pb.inline_sum() - margin.inline_sum(),
+                        };
+                        self.absolutely_positioned_box
+                            .contents
+                            .content_sizes
+                            .shrink_to_fit(available_size)
+                    });
+
+                    let containing_block_for_children = ContainingBlock {
+                        inline_size,
+                        block_size: block_axis.size,
+                        style,
                     };
-                    self.absolutely_positioned_box
-                        .contents
-                        .content_sizes
-                        .shrink_to_fit(available_size)
-                });
-
-                let containing_block_for_children = ContainingBlock {
-                    inline_size,
-                    block_size: block_axis.size,
-                    style,
-                };
-                // https://drafts.csswg.org/css-writing-modes/#orthogonal-flows
-                assert_eq!(
-                    containing_block.style.writing_mode,
-                    containing_block_for_children.style.writing_mode,
-                    "Mixed writing modes are not supported yet"
-                );
-                let dummy_tree_rank = 0;
-                let independent_layout = non_replaced.layout(
-                    layout_context,
-                    &containing_block_for_children,
-                    dummy_tree_rank,
-                    &mut absolutely_positioned_fragments,
-                );
-
-                let size = Vec2 {
-                    inline: inline_size,
-                    block: block_axis
-                        .size
-                        .auto_is(|| independent_layout.content_block_size),
-                };
-                (size, independent_layout.fragments)
-            },
-        };
+                    // https://drafts.csswg.org/css-writing-modes/#orthogonal-flows
+                    assert_eq!(
+                        containing_block.style.writing_mode,
+                        containing_block_for_children.style.writing_mode,
+                        "Mixed writing modes are not supported yet"
+                    );
+                    let dummy_tree_rank = 0;
+                    let independent_layout = non_replaced.layout(
+                        layout_context,
+                        positioning_context,
+                        &containing_block_for_children,
+                        dummy_tree_rank,
+                    );
 
-        let inline_start = match inline_axis.anchor {
-            Anchor::Start(start) => start + pb.inline_start + margin.inline_start,
-            Anchor::End(end) => cbbs - end - pb.inline_end - margin.inline_end - size.inline,
-        };
-        let block_start = match block_axis.anchor {
-            Anchor::Start(start) => start + pb.block_start + margin.block_start,
-            Anchor::End(end) => cbbs - end - pb.block_end - margin.block_end - size.block,
-        };
+                    size = Vec2 {
+                        inline: inline_size,
+                        block: block_axis
+                            .size
+                            .auto_is(|| independent_layout.content_block_size),
+                    };
+                    fragments = independent_layout.fragments
+                },
+            };
 
-        let content_rect = Rect {
-            start_corner: Vec2 {
-                inline: inline_start,
-                block: block_start,
-            },
-            size,
-        };
+            let inline_start = match inline_axis.anchor {
+                Anchor::Start(start) => start + pb.inline_start + margin.inline_start,
+                Anchor::End(end) => cbis - end - pb.inline_end - margin.inline_end - size.inline,
+            };
+            let block_start = match block_axis.anchor {
+                Anchor::Start(start) => start + pb.block_start + margin.block_start,
+                Anchor::End(end) => cbbs - end - pb.block_end - margin.block_end - size.block,
+            };
 
-        AbsolutelyPositionedFragment::in_positioned_containing_block(
-            layout_context,
-            &absolutely_positioned_fragments,
-            &mut fragments,
-            &content_rect.size,
-            &padding,
-            style,
-        );
+            let content_rect = Rect {
+                start_corner: Vec2 {
+                    inline: inline_start,
+                    block: block_start,
+                },
+                size,
+            };
 
-        Fragment::Box(BoxFragment {
-            style: style.clone(),
-            children: fragments,
-            content_rect,
-            padding,
-            border,
-            margin,
-            block_margins_collapsed_with_children: CollapsedBlockMargins::zero(),
+            BoxFragment {
+                style: style.clone(),
+                children: fragments,
+                content_rect,
+                padding,
+                border,
+                margin,
+                block_margins_collapsed_with_children: CollapsedBlockMargins::zero(),
+            }
         })
     }
 }
@@ -413,9 +585,9 @@ fn solve_axis(
     }
 }
 
-pub(crate) fn adjust_static_positions(
-    absolutely_positioned_fragments: &mut [AbsolutelyPositionedFragment],
-    child_fragments: &mut [Fragment],
+fn adjust_static_positions(
+    absolutely_positioned_fragments: &mut [HoistedAbsolutelyPositionedBox],
+    child_fragments: &[Fragment],
     tree_rank_in_parent: usize,
 ) {
     for abspos_fragment in absolutely_positioned_fragments {
@@ -436,3 +608,35 @@ pub(crate) fn adjust_static_positions(
         }
     }
 }
+
+fn vec_append_owned<T>(a: &mut Vec<T>, mut b: Vec<T>) {
+    if a.is_empty() {
+        *a = b
+    } else {
+        a.append(&mut b)
+    }
+}
+
+/// https://drafts.csswg.org/css2/visuren.html#relative-positioning
+pub(crate) fn relative_adjustement(
+    style: &ComputedValues,
+    containing_block: &ContainingBlock,
+) -> Vec2<Length> {
+    let cbis = containing_block.inline_size;
+    let cbbs = containing_block.block_size.auto_is(Length::zero);
+    let box_offsets = style.box_offsets().map_inline_and_block_axes(
+        |v| v.percentage_relative_to(cbis),
+        |v| v.percentage_relative_to(cbbs),
+    );
+    fn adjust(start: LengthOrAuto, end: LengthOrAuto) -> Length {
+        match (start, end) {
+            (LengthOrAuto::Auto, LengthOrAuto::Auto) => Length::zero(),
+            (LengthOrAuto::Auto, LengthOrAuto::LengthPercentage(end)) => -end,
+            (LengthOrAuto::LengthPercentage(start), _) => start,
+        }
+    }
+    Vec2 {
+        inline: adjust(box_offsets.inline_start, box_offsets.inline_end),
+        block: adjust(box_offsets.block_start, box_offsets.block_end),
+    }
+}