LibWeb: Introduce structure that maintains collapsible margins in BFC

Previously y position of boxes in block formatting context
was calculated by looking at y position of previous in-flow
sibling and adding collapsed margin of "collapse through"
boxes lying between box currently being laid out and it's
previous in-flow sibling.

Here introduced BlockMarginState structure that maintains
array of currently collapsible margins hence we no longer
need to look at previous sibling to calculate y position
of a box.

5 files changed, 93 insertions, 89 deletions

diff --git a/Userland/Libraries/LibWeb/Layout/BlockFormattingContext.cpp b/Userland/Libraries/LibWeb/Layout/BlockFormattingContext.cpp
index 2ed71c4687..5b51cd3574 100644
--- a/Userland/Libraries/LibWeb/Layout/BlockFormattingContext.cpp
+++ b/Userland/Libraries/LibWeb/Layout/BlockFormattingContext.cpp
@@ -214,6 +214,8 @@ void BlockFormattingContext::compute_width(Box const& box, AvailableSpace const&
 
     box_state.margin_left = margin_left.to_px(box);
     box_state.margin_right = margin_right.to_px(box);
+
+    resolve_vertical_box_model_metrics(box, m_state);
 }
 
 void BlockFormattingContext::compute_width_for_floating_box(Box const& box, AvailableSpace const& available_space)
@@ -291,6 +293,8 @@ void BlockFormattingContext::compute_width_for_floating_box(Box const& box, Avai
     box_state.border_right = computed_values.border_right().width;
     box_state.padding_left = padding_left.to_px(box);
     box_state.padding_right = padding_right.to_px(box);
+
+    resolve_vertical_box_model_metrics(box, m_state);
 }
 
 void BlockFormattingContext::compute_width_for_block_level_replaced_element_in_normal_flow(ReplacedBox const& box, AvailableSpace const& available_space)
@@ -300,8 +304,6 @@ void BlockFormattingContext::compute_width_for_block_level_replaced_element_in_n
 
 void BlockFormattingContext::compute_height(Box const& box, AvailableSpace const& available_space)
 {
-    resolve_vertical_box_model_metrics(box, m_state);
-
     auto const& computed_values = box.computed_values();
     auto containing_block_height = CSS::Length::make_px(available_space.height.to_px());
 
@@ -347,7 +349,16 @@ void BlockFormattingContext::layout_inline_children(BlockContainer const& block_
         block_container_state.set_content_height(context.automatic_content_height());
 }
 
-void BlockFormattingContext::layout_block_level_box(Box const& box, BlockContainer const& block_container, LayoutMode layout_mode, float& bottom_of_lowest_margin_box, AvailableSpace const& available_space)
+static bool margins_collapse_through(Box const& box, LayoutState& state)
+{
+    // FIXME: A box's own margins collapse if the 'min-height' property is zero, and it has neither top or bottom borders
+    // nor top or bottom padding, and it has a 'height' of either 0 or 'auto', and it does not contain a line box, and
+    // all of its in-flow children's margins (if any) collapse.
+    // https://www.w3.org/TR/CSS22/box.html#collapsing-margins
+    return state.get(box).border_box_height() == 0;
+}
+
+void BlockFormattingContext::layout_block_level_box(Box const& box, BlockContainer const& block_container, LayoutMode layout_mode, float& bottom_of_lowest_margin_box, AvailableSpace const& available_space, float& current_y)
 {
     auto& box_state = m_state.get_mutable(box);
 
@@ -361,35 +372,50 @@ void BlockFormattingContext::layout_block_level_box(Box const& box, BlockContain
         return;
 
     if (box.is_floating()) {
-        layout_floating_box(box, block_container, layout_mode, available_space);
+        layout_floating_box(box, block_container, layout_mode, available_space, m_margin_state.current_collapsed_margin() + current_y);
         bottom_of_lowest_margin_box = max(bottom_of_lowest_margin_box, box_state.offset.y() + box_state.content_height() + box_state.margin_box_bottom());
         return;
     }
 
     compute_width(box, available_space, layout_mode);
 
-    place_block_level_element_in_normal_flow_vertically(box);
-    place_block_level_element_in_normal_flow_horizontally(box, available_space);
-
     if (box_state.has_definite_height()) {
         compute_height(box, available_space);
     }
 
+    m_margin_state.add_margin(box_state.margin_top);
+    auto margin_top = m_margin_state.current_collapsed_margin();
+
+    place_block_level_element_in_normal_flow_vertically(box, current_y + box_state.border_box_top() + margin_top);
+    place_block_level_element_in_normal_flow_horizontally(box, available_space);
+
     OwnPtr<FormattingContext> independent_formatting_context;
     if (!box.is_replaced_box() && box.has_children()) {
         independent_formatting_context = create_independent_formatting_context_if_needed(m_state, box);
         if (independent_formatting_context) {
+            // Margins of elements that establish new formatting contexts do not collapse with their in-flow children
+            m_margin_state.reset();
+
             independent_formatting_context->run(box, layout_mode, box_state.available_inner_space_or_constraints_from(available_space));
         } else {
-            if (box.children_are_inline())
+            if (box.children_are_inline()) {
                 layout_inline_children(verify_cast<BlockContainer>(box), layout_mode, box_state.available_inner_space_or_constraints_from(available_space));
-            else
+            } else {
+                m_margin_state.reset();
                 layout_block_level_children(verify_cast<BlockContainer>(box), layout_mode, box_state.available_inner_space_or_constraints_from(available_space));
+            }
         }
     }
 
     compute_height(box, available_space);
 
+    if (!margins_collapse_through(box, m_state)) {
+        m_margin_state.reset();
+        current_y = box_state.offset.y() + box_state.content_height() + box_state.border_box_bottom();
+    }
+
+    m_margin_state.add_margin(box_state.margin_bottom);
+
     compute_inset(box);
 
     if (is<ListItemBox>(box)) {
@@ -407,12 +433,16 @@ void BlockFormattingContext::layout_block_level_children(BlockContainer const& b
     VERIFY(!block_container.children_are_inline());
 
     float bottom_of_lowest_margin_box = 0;
+    float current_y = 0;
 
     block_container.for_each_child_of_type<Box>([&](Box& box) {
-        layout_block_level_box(box, block_container, layout_mode, bottom_of_lowest_margin_box, available_space);
+        layout_block_level_box(box, block_container, layout_mode, bottom_of_lowest_margin_box, available_space, current_y);
         return IterationDecision::Continue;
     });
 
+    // FIXME: margin-bottom of last in-flow child can be collapsed with margin-bottom of parent
+    m_margin_state.reset();
+
     if (layout_mode == LayoutMode::IntrinsicSizing) {
         auto& block_container_state = m_state.get_mutable(block_container);
         if (!block_container_state.has_definite_width())
@@ -436,14 +466,37 @@ void BlockFormattingContext::resolve_vertical_box_model_metrics(Box const& box,
     box_state.padding_bottom = computed_values.padding().bottom().resolved(box, width_of_containing_block).to_px(box);
 }
 
-void BlockFormattingContext::place_block_level_element_in_normal_flow_vertically(Box const& child_box)
+float BlockFormattingContext::BlockMarginState::current_collapsed_margin() const
 {
-    auto& box_state = m_state.get_mutable(child_box);
-    auto const& computed_values = child_box.computed_values();
+    float smallest_margin = 0;
+    float largest_margin = 0;
+    size_t negative_margin_count = 0;
+    for (auto margin : current_collapsible_margins) {
+        if (margin < 0)
+            ++negative_margin_count;
+        largest_margin = max(largest_margin, margin);
+        smallest_margin = min(smallest_margin, margin);
+    }
+
+    float collapsed_margin = 0;
+    if (negative_margin_count == current_collapsible_margins.size()) {
+        // When all margins are negative, the size of the collapsed margin is the smallest (most negative) margin.
+        collapsed_margin = smallest_margin;
+    } else if (negative_margin_count > 0) {
+        // When negative margins are involved, the size of the collapsed margin is the sum of the largest positive margin and the smallest (most negative) negative margin.
+        collapsed_margin = largest_margin + smallest_margin;
+    } else {
+        // Otherwise, collapse all the adjacent margins by using only the largest one.
+        collapsed_margin = largest_margin;
+    }
 
-    resolve_vertical_box_model_metrics(child_box, m_state);
+    return collapsed_margin;
+}
 
-    auto y = FormattingContext::compute_box_y_position_with_respect_to_siblings(child_box);
+void BlockFormattingContext::place_block_level_element_in_normal_flow_vertically(Box const& child_box, float y)
+{
+    auto& box_state = m_state.get_mutable(child_box);
+    auto const& computed_values = child_box.computed_values();
 
     auto clear_floating_boxes = [&](FloatSideData& float_side) {
         if (!float_side.current_boxes.is_empty()) {
@@ -546,7 +599,7 @@ void BlockFormattingContext::layout_initial_containing_block(LayoutMode layout_m
     }
 }
 
-void BlockFormattingContext::layout_floating_box(Box const& box, BlockContainer const&, LayoutMode layout_mode, AvailableSpace const& available_space, LineBuilder* line_builder)
+void BlockFormattingContext::layout_floating_box(Box const& box, BlockContainer const&, LayoutMode layout_mode, AvailableSpace const& available_space, float y, LineBuilder* line_builder)
 {
     VERIFY(box.is_floating());
 
@@ -563,7 +616,7 @@ void BlockFormattingContext::layout_floating_box(Box const& box, BlockContainer
         auto y = line_builder->y_for_float_to_be_inserted_here(box);
         box_state.set_content_y(y + box_state.margin_box_top());
     } else {
-        place_block_level_element_in_normal_flow_vertically(box);
+        place_block_level_element_in_normal_flow_vertically(box, y + box_state.margin_box_top());
         place_block_level_element_in_normal_flow_horizontally(box, available_space);
     }
 
diff --git a/Userland/Libraries/LibWeb/Layout/BlockFormattingContext.h b/Userland/Libraries/LibWeb/Layout/BlockFormattingContext.h
index ae0bd84dd6..a896cb4966 100644
--- a/Userland/Libraries/LibWeb/Layout/BlockFormattingContext.h
+++ b/Userland/Libraries/LibWeb/Layout/BlockFormattingContext.h
@@ -44,9 +44,9 @@ public:
 
     virtual float greatest_child_width(Box const&) override;
 
-    void layout_floating_box(Box const& child, BlockContainer const& containing_block, LayoutMode, AvailableSpace const&, LineBuilder* = nullptr);
+    void layout_floating_box(Box const& child, BlockContainer const& containing_block, LayoutMode, AvailableSpace const&, float y, LineBuilder* = nullptr);
 
-    void layout_block_level_box(Box const&, BlockContainer const&, LayoutMode, float& bottom_of_lowest_margin_box, AvailableSpace const&);
+    void layout_block_level_box(Box const&, BlockContainer const&, LayoutMode, float& bottom_of_lowest_margin_box, AvailableSpace const&, float& current_y);
 
     virtual bool can_determine_size_of_child() const override { return true; }
     virtual void determine_width_of_child(Box const&, AvailableSpace const&) override;
@@ -66,7 +66,7 @@ private:
 
     static void resolve_vertical_box_model_metrics(Box const& box, LayoutState&);
     void place_block_level_element_in_normal_flow_horizontally(Box const& child_box, AvailableSpace const&);
-    void place_block_level_element_in_normal_flow_vertically(Box const&);
+    void place_block_level_element_in_normal_flow_vertically(Box const&, float y);
 
     void layout_list_item_marker(ListItemBox const&);
 
@@ -111,6 +111,24 @@ private:
         }
     };
 
+    struct BlockMarginState {
+        Vector<float> current_collapsible_margins;
+
+        void add_margin(float margin)
+        {
+            current_collapsible_margins.append(margin);
+        }
+
+        float current_collapsed_margin() const;
+
+        void reset()
+        {
+            current_collapsible_margins.clear();
+        }
+    };
+
+    BlockMarginState m_margin_state;
+
     FloatSideData m_left_floats;
     FloatSideData m_right_floats;
 
diff --git a/Userland/Libraries/LibWeb/Layout/FormattingContext.cpp b/Userland/Libraries/LibWeb/Layout/FormattingContext.cpp
index 55774d67a4..9d7d685aa4 100644
--- a/Userland/Libraries/LibWeb/Layout/FormattingContext.cpp
+++ b/Userland/Libraries/LibWeb/Layout/FormattingContext.cpp
@@ -927,7 +927,7 @@ Gfx::FloatPoint FormattingContext::calculate_static_position(Box const& box) con
     } else {
         x = m_state.get(box).margin_box_left();
         // We're among block siblings, Y can be calculated easily.
-        y = compute_box_y_position_with_respect_to_siblings(box);
+        y = m_state.get(box).margin_box_top();
     }
     auto offset_to_static_parent = content_box_rect_in_static_position_ancestor_coordinate_space(box, *box.containing_block(), m_state);
     return offset_to_static_parent.location().translated(x, y);
@@ -1364,71 +1364,6 @@ float FormattingContext::containing_block_height_for(Box const& box, LayoutState
     VERIFY_NOT_REACHED();
 }
 
-static Box const* previous_block_level_sibling(Box const& box)
-{
-    for (auto* sibling = box.previous_sibling_of_type<Box>(); sibling; sibling = sibling->previous_sibling_of_type<Box>()) {
-        if (sibling->display().is_block_outside())
-            return sibling;
-    }
-    return nullptr;
-}
-
-float FormattingContext::compute_box_y_position_with_respect_to_siblings(Box const& box) const
-{
-    auto const& box_state = m_state.get(box);
-    float y = box_state.border_box_top();
-
-    Vector<float> collapsible_margins;
-
-    auto* relevant_sibling = previous_block_level_sibling(box);
-    while (relevant_sibling != nullptr) {
-        if (!relevant_sibling->is_absolutely_positioned() && !relevant_sibling->is_floating()) {
-            auto const& relevant_sibling_state = m_state.get(*relevant_sibling);
-            collapsible_margins.append(relevant_sibling_state.margin_bottom);
-            // NOTE: Empty (0-height) preceding siblings have their margins collapsed with *their* preceding sibling, etc.
-            if (relevant_sibling_state.border_box_height() > 0)
-                break;
-            collapsible_margins.append(relevant_sibling_state.margin_top);
-        }
-        relevant_sibling = previous_block_level_sibling(*relevant_sibling);
-    }
-
-    if (relevant_sibling) {
-        // Collapse top margin with the collapsed margin(s) of preceding siblings.
-        collapsible_margins.append(box_state.margin_top);
-
-        float smallest_margin = 0;
-        float largest_margin = 0;
-        size_t negative_margin_count = 0;
-        for (auto margin : collapsible_margins) {
-            if (margin < 0)
-                ++negative_margin_count;
-            largest_margin = max(largest_margin, margin);
-            smallest_margin = min(smallest_margin, margin);
-        }
-
-        float collapsed_margin = 0;
-        if (negative_margin_count == collapsible_margins.size()) {
-            // When all margins are negative, the size of the collapsed margin is the smallest (most negative) margin.
-            collapsed_margin = smallest_margin;
-        } else if (negative_margin_count > 0) {
-            // When negative margins are involved, the size of the collapsed margin is the sum of the largest positive margin and the smallest (most negative) negative margin.
-            collapsed_margin = largest_margin + smallest_margin;
-        } else {
-            // Otherwise, collapse all the adjacent margins by using only the largest one.
-            collapsed_margin = largest_margin;
-        }
-
-        auto const& relevant_sibling_state = m_state.get(*relevant_sibling);
-        return y + relevant_sibling_state.offset.y()
-            + relevant_sibling_state.content_height()
-            + relevant_sibling_state.border_box_bottom()
-            + collapsed_margin;
-    } else {
-        return y + box_state.margin_top;
-    }
-}
-
 // https://drafts.csswg.org/css-sizing-3/#stretch-fit-size
 float FormattingContext::calculate_stretch_fit_width(Box const& box, AvailableSize const& available_width) const
 {
diff --git a/Userland/Libraries/LibWeb/Layout/FormattingContext.h b/Userland/Libraries/LibWeb/Layout/FormattingContext.h
index 7026021149..4b358d2908 100644
--- a/Userland/Libraries/LibWeb/Layout/FormattingContext.h
+++ b/Userland/Libraries/LibWeb/Layout/FormattingContext.h
@@ -71,8 +71,6 @@ public:
     static float containing_block_width_for(Box const&, LayoutState const&);
     static float containing_block_height_for(Box const&, LayoutState const&);
 
-    float compute_box_y_position_with_respect_to_siblings(Box const&) const;
-
     [[nodiscard]] float calculate_stretch_fit_width(Box const&, AvailableSize const&) const;
     [[nodiscard]] float calculate_stretch_fit_height(Box const&, AvailableSize const&) const;
 
diff --git a/Userland/Libraries/LibWeb/Layout/InlineFormattingContext.cpp b/Userland/Libraries/LibWeb/Layout/InlineFormattingContext.cpp
index 38a1d70a1b..ad78181d36 100644
--- a/Userland/Libraries/LibWeb/Layout/InlineFormattingContext.cpp
+++ b/Userland/Libraries/LibWeb/Layout/InlineFormattingContext.cpp
@@ -263,7 +263,7 @@ void InlineFormattingContext::generate_line_boxes(LayoutMode layout_mode)
 
         case InlineLevelIterator::Item::Type::FloatingElement:
             if (is<Box>(*item.node))
-                parent().layout_floating_box(static_cast<Layout::Box const&>(*item.node), containing_block(), layout_mode, *m_available_space, &line_builder);
+                parent().layout_floating_box(static_cast<Layout::Box const&>(*item.node), containing_block(), layout_mode, *m_available_space, 0, &line_builder);
             break;
 
         case InlineLevelIterator::Item::Type::Text: {