Handle BFC roots with auto width next to floats (#30057)

Co-authored-by: Martin Robinson <mrobinson@igalia.com>

13 files changed, 179 insertions, 36 deletions

diff --git a/components/layout_2020/flow/float.rs b/components/layout_2020/flow/float.rs
index 382477860d9..45493ebd8f4 100644
--- a/components/layout_2020/flow/float.rs
+++ b/components/layout_2020/flow/float.rs
@@ -160,6 +160,12 @@ impl<'a> PlacementAmongFloats<'a> {
         return (max_inline_start, min_inline_end);
     }
 
+    /// Find the total inline size provided by the current set of bands under consideration.
+    fn calculate_viable_inline_size(&self) -> Length {
+        let (inline_start, inline_end) = self.calculate_inline_start_and_end();
+        inline_end - inline_start
+    }
+
     fn try_place_once(&mut self) -> Option<Rect<Length>> {
         assert!(!self.current_bands.is_empty());
         self.accumulate_enough_bands_for_block_size();
@@ -207,6 +213,56 @@ impl<'a> PlacementAmongFloats<'a> {
             },
         }
     }
+
+    /// After placing an object with `height: auto` (and using the minimum inline and
+    /// block size as the object size) and then laying it out, try to fit the object into
+    /// the current set of bands, given block size after layout and the available inline
+    /// space from the original placement. This will return true if the object fits at the
+    /// original placement location or false if the placement and layout must be run again
+    /// (with this [PlacementAmongFloats]).
+    pub(crate) fn try_to_expand_for_auto_block_size(
+        &mut self,
+        block_size_after_layout: Length,
+        size_from_placement: &Vec2<Length>,
+    ) -> bool {
+        debug_assert_eq!(size_from_placement.block, self.current_bands_height());
+        debug_assert_eq!(
+            size_from_placement.inline,
+            self.calculate_viable_inline_size()
+        );
+
+        // If the object after layout fits into the originally calculated placement, then
+        // it fits without any more work.
+        if block_size_after_layout <= size_from_placement.block {
+            return true;
+        }
+
+        // Keep searching until we have found an area with enough height
+        // to contain the block after layout.
+        let old_num_bands = self.current_bands.len();
+        assert!(old_num_bands > 0);
+        while self.current_bands_height() < block_size_after_layout {
+            self.add_one_band();
+
+            // If the new inline size is narrower, we must stop and run layout again.
+            // Normally, a narrower block size means a bigger height, but in some
+            // circumstances, such as when aspect ratio is used a narrower inline size
+            // can counter-interuitively lead to a smaller block size after layout!
+            let available_inline_size = self.calculate_viable_inline_size();
+            if available_inline_size < size_from_placement.inline {
+                // If the inline size becomes smaller than the minimum inline size, then
+                // the current set of bands will never work and we must try removing the
+                // first and searching starting from the second.
+                if available_inline_size < self.object_size.inline {
+                    self.next_band = self.current_bands[old_num_bands];
+                    self.current_bands.truncate(old_num_bands);
+                    self.current_bands.pop_front();
+                }
+                return false;
+            }
+        }
+        true
+    }
 }
 
 /// Data kept during layout about the floats in a given block formatting context.
@@ -939,14 +995,20 @@ impl SequentialLayoutState {
 
     /// Computes the position of the block-start border edge of an element
     /// with the provided `block_start_margin`, assuming no clearance.
-    fn position_without_clearance(&self, block_start_margin: &CollapsedMargin) -> Length {
+    pub(crate) fn position_without_clearance(
+        &self,
+        block_start_margin: &CollapsedMargin,
+    ) -> Length {
         // Adjoin `current_margin` and `block_start_margin` since there is no clearance.
         self.bfc_relative_block_position + self.current_margin.adjoin(&block_start_margin).solve()
     }
 
     /// Computes the position of the block-start border edge of an element
     /// with the provided `block_start_margin`, assuming a clearance of 0px.
-    fn position_with_zero_clearance(&self, block_start_margin: &CollapsedMargin) -> Length {
+    pub(crate) fn position_with_zero_clearance(
+        &self,
+        block_start_margin: &CollapsedMargin,
+    ) -> Length {
         // Clearance prevents `current_margin` and `block_start_margin` from being
         // adjoining, so we need to solve them separately and then sum.
         self.bfc_relative_block_position + self.current_margin.solve() + block_start_margin.solve()
@@ -954,7 +1016,7 @@ impl SequentialLayoutState {
 
     /// Returns the block-end outer edge of the lowest float that is to be cleared (if any)
     /// by an element with the provided `clear` and `block_start_margin`.
-    fn calculate_clear_position(
+    pub(crate) fn calculate_clear_position(
         &self,
         clear: Clear,
         block_start_margin: &CollapsedMargin,
diff --git a/components/layout_2020/flow/mod.rs b/components/layout_2020/flow/mod.rs
index 7082f48f346..331b13cd345 100644
--- a/components/layout_2020/flow/mod.rs
+++ b/components/layout_2020/flow/mod.rs
@@ -6,7 +6,9 @@
 
 use crate::cell::ArcRefCell;
 use crate::context::LayoutContext;
-use crate::flow::float::{ContainingBlockPositionInfo, FloatBox, SequentialLayoutState};
+use crate::flow::float::{
+    ContainingBlockPositionInfo, FloatBox, PlacementAmongFloats, SequentialLayoutState,
+};
 use crate::flow::inline::InlineFormattingContext;
 use crate::formatting_contexts::{
     IndependentFormattingContext, IndependentLayout, NonReplacedFormattingContext,
@@ -899,8 +901,8 @@ impl NonReplacedFormattingContext {
         //  element next to the float or by how much said element may become narrower."
         let clearance;
         let inline_adjustment_from_floats;
-        let content_size;
-        let layout;
+        let mut content_size;
+        let mut layout;
         if let LengthOrAuto::LengthPercentage(ref inline_size) = box_size.inline {
             let inline_size =
                 inline_size.clamp_between_extremums(min_box_size.inline, max_box_size.inline);
@@ -929,33 +931,93 @@ impl NonReplacedFormattingContext {
                     &content_size + &pbm.padding_border_sums,
                 );
         } else {
-            // TODO: Use PlacementAmongFloats to avoid overlapping floats.
-            let inline_size = (containing_block.inline_size -
-                pbm.padding_border_sums.inline -
-                pbm.margin.inline_start.auto_is(Length::zero) -
-                pbm.margin.inline_end.auto_is(Length::zero))
-            .clamp_between_extremums(min_box_size.inline, max_box_size.inline);
-            layout = self.layout(
-                layout_context,
-                positioning_context,
-                &ContainingBlock {
-                    inline_size,
-                    block_size,
-                    style: &self.style,
-                },
+            // First compute the clear position required by the 'clear' property.
+            // The code below may then add extra clearance when the element can't fit
+            // next to floats not covered by 'clear'.
+            let clear_position = sequential_layout_state.calculate_clear_position(
+                self.style.get_box().clear,
+                &collapsed_margin_block_start,
             );
-            content_size = Vec2 {
-                inline: inline_size,
-                block: block_size.auto_is(|| {
-                    layout
-                        .content_block_size
-                        .clamp_between_extremums(min_box_size.block, max_box_size.block)
-                }),
+            let ceiling = clear_position.unwrap_or_else(|| {
+                sequential_layout_state.position_without_clearance(&collapsed_margin_block_start)
+            });
+
+            // Create a PlacementAmongFloats using the minimum size in all dimensions as the object size.
+            let minimum_size_of_block = &Vec2 {
+                inline: min_box_size.inline,
+                block: block_size.auto_is(|| min_box_size.block),
+            } + &pbm.padding_border_sums;
+            let mut placement = PlacementAmongFloats::new(
+                &sequential_layout_state.floats,
+                ceiling,
+                minimum_size_of_block,
+            );
+            let mut placement_rect;
+
+            loop {
+                // First try to place the block using the minimum size as the object size.
+                placement_rect = placement.place();
+                let proposed_inline_size = (placement_rect.size.inline -
+                    pbm.padding_border_sums.inline)
+                    .clamp_between_extremums(min_box_size.inline, max_box_size.inline);
+
+                // Now lay out the block using the inline size we calculated from the placement.
+                // Later we'll check to see if the resulting block size is compatible with the
+                // placement.
+                let positioning_context_length = positioning_context.len();
+                layout = self.layout(
+                    layout_context,
+                    positioning_context,
+                    &ContainingBlock {
+                        inline_size: proposed_inline_size,
+                        block_size,
+                        style: &self.style,
+                    },
+                );
+
+                content_size = Vec2 {
+                    inline: proposed_inline_size,
+                    block: block_size.auto_is(|| {
+                        layout
+                            .content_block_size
+                            .clamp_between_extremums(min_box_size.block, max_box_size.block)
+                    }),
+                };
+
+                // Now we know the block size of this attempted layout of a box with block
+                // size of auto. Try to fit it into our precalculated placement among the
+                // floats. If it fits, then we can stop trying layout candidates.
+                if placement.try_to_expand_for_auto_block_size(
+                    content_size.block + pbm.padding_border_sums.block,
+                    &placement_rect.size,
+                ) {
+                    break;
+                }
+
+                // The previous attempt to lay out this independent formatting context
+                // among the floats did not work, so we must unhoist any boxes from that
+                // attempt.
+                positioning_context.truncate(&positioning_context_length);
+            }
+
+            // Only set clearance if we would have cleared or the placement among floats moves
+            // the block further in the block direction. These two situations are the ones that
+            // prevent margin collapse.
+            clearance = if clear_position.is_some() || placement_rect.start_corner.block > ceiling {
+                Some(
+                    placement_rect.start_corner.block -
+                        sequential_layout_state
+                            .position_with_zero_clearance(&collapsed_margin_block_start),
+                )
+            } else {
+                None
             };
 
-            clearance = sequential_layout_state
-                .calculate_clearance(self.style.get_box().clear, &collapsed_margin_block_start);
-            inline_adjustment_from_floats = Length::zero();
+            inline_adjustment_from_floats = placement_rect.start_corner.inline -
+                sequential_layout_state
+                    .floats
+                    .containing_block_info
+                    .inline_start;
         }
 
         // TODO: solve_inline_margins_for_in_flow_block_level() doesn't take floats into account.
diff --git a/components/layout_2020/positioned.rs b/components/layout_2020/positioned.rs
index 85c4731686d..d6be2298356 100644
--- a/components/layout_2020/positioned.rs
+++ b/components/layout_2020/positioned.rs
@@ -364,6 +364,17 @@ impl PositioningContext {
                 .len(),
         }
     }
+
+    /// Truncate this [PositioningContext] to the given [PositioningContextLength].  This
+    /// is useful for "unhoisting" boxes in this context and returning it to the state at
+    /// the time that [`len()`] was called.
+    pub(crate) fn truncate(&mut self, length: &PositioningContextLength) {
+        if let Some(vec) = self.for_nearest_positioned_ancestor.as_mut() {
+            vec.truncate(length.for_nearest_positioned_ancestor);
+        }
+        self.for_nearest_containing_block_for_all_descendants
+            .truncate(length.for_nearest_containing_block_for_all_descendants);
+    }
 }
 
 /// A data structure which stores the size of a positioning context.
diff --git a/tests/wpt/meta/css/CSS2/floats/floats-wrap-bfc-002-left-overflow.xht.ini b/tests/wpt/meta/css/CSS2/floats/floats-wrap-bfc-002-left-overflow.xht.ini
deleted file mode 100644
index 3d2a6534df8..00000000000
--- a/tests/wpt/meta/css/CSS2/floats/floats-wrap-bfc-002-left-overflow.xht.ini
+++ /dev/null
@@ -1,2 +0,0 @@
-[floats-wrap-bfc-002-left-overflow.xht]
-  expected: FAIL
diff --git a/tests/wpt/meta/css/CSS2/floats/new-fc-relayout.html.ini b/tests/wpt/meta/css/CSS2/floats/new-fc-relayout.html.ini
deleted file mode 100644
index 52f35974f9e..00000000000
--- a/tests/wpt/meta/css/CSS2/floats/new-fc-relayout.html.ini
+++ /dev/null
@@ -1,2 +0,0 @@
-[new-fc-relayout.html]
-  expected: FAIL
diff --git a/tests/wpt/meta/css/CSS2/floats/zero-width-floats.html.ini b/tests/wpt/meta/css/CSS2/floats/zero-width-floats.html.ini
new file mode 100644
index 00000000000..e20b1a193ff
--- /dev/null
+++ b/tests/wpt/meta/css/CSS2/floats/zero-width-floats.html.ini
@@ -0,0 +1,2 @@
+[zero-width-floats.html]
+  expected: FAIL
diff --git a/tests/wpt/meta/css/css-flexbox/flex-aspect-ratio-img-row-004.html.ini b/tests/wpt/meta/css/css-flexbox/flex-aspect-ratio-img-row-004.html.ini
deleted file mode 100644
index cc57c8329ea..00000000000
--- a/tests/wpt/meta/css/css-flexbox/flex-aspect-ratio-img-row-004.html.ini
+++ /dev/null
@@ -1,2 +0,0 @@
-[flex-aspect-ratio-img-row-004.html]
-  expected: FAIL
diff --git a/tests/wpt/meta/css/css-flexbox/flex-direction-modify.html.ini b/tests/wpt/meta/css/css-flexbox/flex-direction-modify.html.ini
new file mode 100644
index 00000000000..4628cda4267
--- /dev/null
+++ b/tests/wpt/meta/css/css-flexbox/flex-direction-modify.html.ini
@@ -0,0 +1,2 @@
+[flex-direction-modify.html]
+  expected: FAIL
diff --git a/tests/wpt/mozilla/meta/css/block_formatting_context_a.html.ini b/tests/wpt/mozilla/meta/css/block_formatting_context_a.html.ini
new file mode 100644
index 00000000000..766e4b3cd9d
--- /dev/null
+++ b/tests/wpt/mozilla/meta/css/block_formatting_context_a.html.ini
@@ -0,0 +1,2 @@
+[block_formatting_context_a.html]
+  expected: FAIL
diff --git a/tests/wpt/mozilla/meta/css/block_formatting_context_complex_a.html.ini b/tests/wpt/mozilla/meta/css/block_formatting_context_complex_a.html.ini
new file mode 100644
index 00000000000..5498e467c6e
--- /dev/null
+++ b/tests/wpt/mozilla/meta/css/block_formatting_context_complex_a.html.ini
@@ -0,0 +1,2 @@
+[block_formatting_context_complex_a.html]
+  expected: FAIL
diff --git a/tests/wpt/mozilla/meta/css/block_formatting_context_margin_inout_a.html.ini b/tests/wpt/mozilla/meta/css/block_formatting_context_margin_inout_a.html.ini
new file mode 100644
index 00000000000..7bb6c05416f
--- /dev/null
+++ b/tests/wpt/mozilla/meta/css/block_formatting_context_margin_inout_a.html.ini
@@ -0,0 +1,2 @@
+[block_formatting_context_margin_inout_a.html]
+  expected: FAIL
diff --git a/tests/wpt/mozilla/meta/css/block_formatting_context_negative_margins_a.html.ini b/tests/wpt/mozilla/meta/css/block_formatting_context_negative_margins_a.html.ini
new file mode 100644
index 00000000000..c5dc44da406
--- /dev/null
+++ b/tests/wpt/mozilla/meta/css/block_formatting_context_negative_margins_a.html.ini
@@ -0,0 +1,2 @@
+[block_formatting_context_negative_margins_a.html]
+  expected: FAIL
diff --git a/tests/wpt/mozilla/meta/css/block_formatting_context_relative_a.html.ini b/tests/wpt/mozilla/meta/css/block_formatting_context_relative_a.html.ini
new file mode 100644
index 00000000000..27d6a36d72e
--- /dev/null
+++ b/tests/wpt/mozilla/meta/css/block_formatting_context_relative_a.html.ini
@@ -0,0 +1,2 @@
+[block_formatting_context_relative_a.html]
+  expected: FAIL