LibWeb: Improve inline flow around floating boxes

This patch combines a number of techniques to make inline content flow more correctly around floats: - During inline layout, BFC now lets LineBuilder decide the Y coordinate when inserting a new float. LineBuilder has more information about the currently accumulated line, and can make better breaking decisions. - When inserting a float on one side, and the top of the newly inserted float is below the bottommost float on the opposite side, we now reset the opposite side back to the start of that edge. This improves breaking behavior between opposite-side floats. - After inserting a float during inline layout, we now recalculate the available space on the line, but don't adjust X offsets of already existing fragments. This is handled by update_last_line() anyway, so it was pointless busywork. - When measuring whether a line can fit at a given Y coordinate, we now consider both the top and bottom Y values of the line. This fixes an issue where the bottom part of a line would bleed over other content (since we had only checked that the top Y coordinate of that line would fit.) There are some pretty brain-dead algorithms in here that we need to make smarter, but I didn't want to complicate this any further so I've left FIXMEs about them instead.
author: Andreas Kling <kling@serenityos.org> 2022-09-16 14:21:52 +0200
committer: Andreas Kling <kling@serenityos.org> 2022-09-16 15:15:50 +0200
commit: 412b2313f33f5efe7f672fed7c26c8fa0187c188 (patch)
tree: 4dbbe7a51d94e0ac545283ea3ab6375be1a8d682
parent: 54e735924301fd96d54b64c8aa769b813891b1f9 (diff)
download: serenity-412b2313f33f5efe7f672fed7c26c8fa0187c188.zip
6 files changed, 185 insertions, 32 deletions
diff --git a/Base/res/html/misc/float-stress-1.html b/Base/res/html/misc/float-stress-1.html
new file mode 100644
index 0000000000..37e03a0ea6
--- /dev/null
+++ b/Base/res/html/misc/float-stress-1.html
@@ -0,0 +1,67 @@
+<!DOCTYPE html>
+<html>
+  <head>
+    <title>float horror show</title>
+    <style type="text/css">
+html {
+    font: 16px/1 Arial;
+}
+      .outer {
+        border: 1px solid black;
+        width: 300px;
+        height: 250px;
+      }
+
+      .one {
+        float: left;
+        height: 50px;
+        width: 200px;
+        margin: 0;
+        border: 1px solid black;
+        background-color: #fc0;
+      }
+      .two {
+        float: right;
+        height: 50px;
+        width: 200px;
+        margin: 0;
+        border: 1px solid black;
+        background-color: pink;
+      }
+      .lefty {
+        float: left;
+        height: 50px;
+        width: 50px;
+        margin: 0;
+        border: 1px solid black;
+        background-color: lime;
+      }
+      .righty {
+        float: right;
+        height: 30px;
+        width: 30px;
+        margin: 0;
+        border: 1px solid black;
+        background-color: magenta;
+      }
+</style></head><body>
+    <div class=outer>
+        foo bar baz foo bar baz
+        <div class=lefty></div>
+        <div class=one></div>
+        <div class=two></div>
+        foo bar baz foo bar baz
+        foo bar baz foo bar baz
+        <div class=righty></div>
+        foo bar baz foo bar baz
+        foo bar baz foo bar baz
+        foo bar baz foo bar baz
+        <div class="lefty shwifty"></div>
+        foo bar baz foo bar baz
+        <div class=righty></div>
+        foo bar baz foo bar baz
+        foo bar baz foo bar baz
+        foo bar baz foo bar baz
+        foo bar baz foo bar baz
+        foo bar baz foo bar baz
+        foo bar baz foo bar baz
diff --git a/Userland/Libraries/LibWeb/Layout/BlockFormattingContext.cpp b/Userland/Libraries/LibWeb/Layout/BlockFormattingContext.cpp
index 7efea3e353..31b83db127 100644
--- a/Userland/Libraries/LibWeb/Layout/BlockFormattingContext.cpp
+++ b/Userland/Libraries/LibWeb/Layout/BlockFormattingContext.cpp
@@ -616,17 +616,15 @@ void BlockFormattingContext::layout_floating_box(Box const& box, BlockContainer
     // First we place the box normally (to get the right y coordinate.)
     // If we have a LineBuilder, we're in the middle of inline layout, otherwise this is block layout.
     if (line_builder) {
-        float y_offset = box_state.margin_box_top();
-        line_builder->break_if_needed(box_state.margin_box_width());
-        box_state.offset.set_y(line_builder->current_y() + y_offset);
-        line_builder->adjust_last_line_after_inserting_floating_box({}, box.computed_values().float_(), box_state.margin_box_width());
+        auto y = line_builder->y_for_float_to_be_inserted_here(box);
+        box_state.offset.set_y(y + box_state.margin_box_top());
     } else {
         place_block_level_element_in_normal_flow_vertically(box, containing_block);
         place_block_level_element_in_normal_flow_horizontally(box, containing_block);
     }
 
     // Then we float it to the left or right.
-    auto float_box = [&](FloatSide side, FloatSideData& side_data) {
+    auto float_box = [&](FloatSide side, FloatSideData& side_data, FloatSideData& other_side_data) {
         float offset_from_edge = 0;
         auto float_to_edge = [&] {
             if (side == FloatSide::Left)
@@ -684,7 +682,15 @@ void BlockFormattingContext::layout_floating_box(Box const& box, BlockContainer
                 side_data.clear();
             }
         }
-        y += side_data.y_offset;
+
+        // NOTE: If we're in inline layout, the LineBuilder has already provided the right Y offset.
+        //       In block layout, we adjust by the side's current Y offset here.
+        // FIXME: It's annoying that we have different behavior for inline vs block here.
+        //        Find a way to unify the behavior so we don't need to branch here.
+
+        if (!line_builder)
+            y += side_data.y_offset;
+
         side_data.all_boxes.append(adopt_own(*new FloatingBox {
             .box = box,
             .offset_from_edge = offset_from_edge,
@@ -703,16 +709,24 @@ void BlockFormattingContext::layout_floating_box(Box const& box, BlockContainer
         // NOTE: We don't set the X position here, that happens later, once we know the root block width.
         //       See parent_context_did_dimension_child_root_box() for that logic.
         box_state.offset.set_y(y);
+
+        // If the new box was inserted below the bottom of the opposite side,
+        // we reset the other side back to its edge.
+        if (y > other_side_data.y_offset)
+            other_side_data.clear();
     };
 
     // Next, float to the left and/or right
     if (box.computed_values().float_() == CSS::Float::Left) {
-        float_box(FloatSide::Left, m_left_floats);
+        float_box(FloatSide::Left, m_left_floats, m_right_floats);
     } else if (box.computed_values().float_() == CSS::Float::Right) {
-        float_box(FloatSide::Right, m_right_floats);
+        float_box(FloatSide::Right, m_right_floats, m_left_floats);
     }
 
     m_state.get_mutable(root()).add_floating_descendant(box);
+
+    if (line_builder)
+        line_builder->recalculate_available_space();
 }
 
 void BlockFormattingContext::layout_list_item_marker(ListItemBox const& list_item_box)
@@ -755,7 +769,8 @@ BlockFormattingContext::SpaceUsedByFloats BlockFormattingContext::space_used_by_
 {
     SpaceUsedByFloats space_used_by_floats;
 
-    for (auto const& floating_box : m_left_floats.current_boxes.in_reverse()) {
+    for (auto const& floating_box_ptr : m_left_floats.all_boxes.in_reverse()) {
+        auto const& floating_box = *floating_box_ptr;
         auto const& floating_box_state = m_state.get(floating_box.box);
         // NOTE: The floating box is *not* in the final horizontal position yet, but the size and vertical position is valid.
         auto rect = border_box_rect_in_ancestor_coordinate_space(floating_box.box, root(), m_state);
@@ -767,7 +782,8 @@ BlockFormattingContext::SpaceUsedByFloats BlockFormattingContext::space_used_by_
         }
     }
 
-    for (auto const& floating_box : m_right_floats.current_boxes.in_reverse()) {
+    for (auto const& floating_box_ptr : m_right_floats.all_boxes.in_reverse()) {
+        auto const& floating_box = *floating_box_ptr;
         auto const& floating_box_state = m_state.get(floating_box.box);
         // NOTE: The floating box is *not* in the final horizontal position yet, but the size and vertical position is valid.
         auto rect = border_box_rect_in_ancestor_coordinate_space(floating_box.box, root(), m_state);
diff --git a/Userland/Libraries/LibWeb/Layout/InlineFormattingContext.cpp b/Userland/Libraries/LibWeb/Layout/InlineFormattingContext.cpp
index 0ab47b3cba..6640229e4d 100644
--- a/Userland/Libraries/LibWeb/Layout/InlineFormattingContext.cpp
+++ b/Userland/Libraries/LibWeb/Layout/InlineFormattingContext.cpp
@@ -305,4 +305,23 @@ bool InlineFormattingContext::any_floats_intrude_at_y(float y) const
     return space.left > 0 || space.right > 0;
 }
 
+bool InlineFormattingContext::can_fit_new_line_at_y(float y) const
+{
+    auto box_in_root_rect = content_box_rect_in_ancestor_coordinate_space(containing_block(), parent().root(), m_state);
+    float y_in_root = box_in_root_rect.y() + y;
+    auto space_top = parent().space_used_by_floats(y_in_root);
+    auto space_bottom = parent().space_used_by_floats(y_in_root + containing_block().line_height() - 1);
+
+    [[maybe_unused]] auto top_left_edge = space_top.left;
+    [[maybe_unused]] auto top_right_edge = m_effective_containing_block_width - space_top.right;
+    [[maybe_unused]] auto bottom_left_edge = space_bottom.left;
+    [[maybe_unused]] auto bottom_right_edge = m_effective_containing_block_width - space_bottom.right;
+
+    if (top_left_edge > bottom_right_edge)
+        return false;
+    if (bottom_left_edge > top_right_edge)
+        return false;
+    return true;
+}
+
 }
diff --git a/Userland/Libraries/LibWeb/Layout/InlineFormattingContext.h b/Userland/Libraries/LibWeb/Layout/InlineFormattingContext.h
index 525f968144..0eeb452aa7 100644
--- a/Userland/Libraries/LibWeb/Layout/InlineFormattingContext.h
+++ b/Userland/Libraries/LibWeb/Layout/InlineFormattingContext.h
@@ -30,6 +30,7 @@ public:
     float leftmost_x_offset_at(float y) const;
     float available_space_for_line(float y) const;
     bool any_floats_intrude_at_y(float y) const;
+    bool can_fit_new_line_at_y(float y) const;
 
     float effective_containing_block_width() const { return m_effective_containing_block_width; }
 
diff --git a/Userland/Libraries/LibWeb/Layout/LineBuilder.cpp b/Userland/Libraries/LibWeb/Layout/LineBuilder.cpp
index e1176ecc99..9f11e914df 100644
--- a/Userland/Libraries/LibWeb/Layout/LineBuilder.cpp
+++ b/Userland/Libraries/LibWeb/Layout/LineBuilder.cpp
@@ -27,19 +27,40 @@ LineBuilder::~LineBuilder()
 void LineBuilder::break_line(Optional<float> next_item_width)
 {
     update_last_line();
+    size_t break_count = 0;
+    bool floats_intrude_at_current_y = false;
     do {
         m_containing_block_state.line_boxes.append(LineBox());
-        begin_new_line(true);
-    } while (next_item_width.has_value()
-        && next_item_width.value() > m_available_width_for_current_line
-        && m_context.any_floats_intrude_at_y(m_current_y));
+        begin_new_line(true, break_count == 0);
+        break_count++;
+        floats_intrude_at_current_y = m_context.any_floats_intrude_at_y(m_current_y);
+    } while ((floats_intrude_at_current_y && !m_context.can_fit_new_line_at_y(m_current_y))
+        || (next_item_width.has_value()
+            && next_item_width.value() > m_available_width_for_current_line
+            && floats_intrude_at_current_y));
 }
 
-void LineBuilder::begin_new_line(bool increment_y)
+void LineBuilder::begin_new_line(bool increment_y, bool is_first_break_in_sequence)
 {
-    if (increment_y)
-        m_current_y += max(m_max_height_on_current_line, m_context.containing_block().line_height());
-    m_available_width_for_current_line = m_context.available_space_for_line(m_current_y);
+    if (increment_y) {
+        if (is_first_break_in_sequence) {
+            // First break is simple, just go to the start of the next line.
+            m_current_y += max(m_max_height_on_current_line, m_context.containing_block().line_height());
+        } else {
+            // We're doing more than one break in a row.
+            // This means we're trying to squeeze past intruding floats.
+            // Scan 1px at a time until we find a Y value where a new line can fit.
+            // FIXME: This is super dumb and inefficient.
+            float candidate_y = m_current_y + 1;
+            while (true) {
+                if (m_context.can_fit_new_line_at_y(candidate_y))
+                    break;
+                ++candidate_y;
+            }
+            m_current_y = candidate_y;
+        }
+    }
+    recalculate_available_space();
     m_max_height_on_current_line = 0;
     m_last_line_needs_update = true;
 }
@@ -71,6 +92,32 @@ void LineBuilder::append_text_chunk(TextNode const& text_node, size_t offset_in_
     m_max_height_on_current_line = max(m_max_height_on_current_line, content_height);
 }
 
+float LineBuilder::y_for_float_to_be_inserted_here(Box const& box)
+{
+    auto const& box_state = m_layout_state.get(box);
+    auto width = box_state.margin_box_width();
+
+    auto current_line_width = ensure_last_line_box().width();
+    if (roundf(current_line_width + width) > m_available_width_for_current_line) {
+        float candidate_y = m_current_y + m_context.containing_block().line_height();
+        // FIXME: This is super dumb, we move 1px downwards per iteration and stop
+        //        when we find an Y value where we don't collide with other floats.
+        while (true) {
+            if (width > m_context.available_space_for_line(candidate_y)) {
+                if (!m_context.any_floats_intrude_at_y(candidate_y)) {
+                    return candidate_y;
+                }
+            } else {
+                return candidate_y;
+            }
+            candidate_y += 1;
+        }
+
+        return m_current_y + m_context.containing_block().line_height();
+    }
+    return m_current_y;
+}
+
 bool LineBuilder::should_break(float next_item_width)
 {
     if (!isfinite(m_available_width_for_current_line))
@@ -82,6 +129,8 @@ bool LineBuilder::should_break(float next_item_width)
         // at this Y coordinate, we don't need to break before inserting anything.
         if (!m_context.any_floats_intrude_at_y(m_current_y))
             return false;
+        if (!m_context.any_floats_intrude_at_y(m_current_y + m_context.containing_block().line_height()))
+            return false;
     }
     auto current_line_width = ensure_last_line_box().width();
     return roundf(current_line_width + next_item_width) > m_available_width_for_current_line;
@@ -124,7 +173,12 @@ void LineBuilder::update_last_line()
     auto& line_box = line_boxes.last();
 
     auto text_align = m_context.containing_block().computed_values().text_align();
-    float x_offset = m_context.leftmost_x_offset_at(m_current_y);
+
+    auto current_line_height = max(m_max_height_on_current_line, m_context.containing_block().line_height());
+    float x_offset_top = m_context.leftmost_x_offset_at(m_current_y);
+    float x_offset_bottom = m_context.leftmost_x_offset_at(m_current_y + current_line_height - 1);
+    float x_offset = max(x_offset_top, x_offset_bottom);
+
     float excess_horizontal_space = m_context.effective_containing_block_width() - line_box.width();
 
     switch (text_align) {
@@ -260,18 +314,12 @@ void LineBuilder::remove_last_line_if_empty()
     }
 }
 
-void LineBuilder::adjust_last_line_after_inserting_floating_box(Badge<BlockFormattingContext>, CSS::Float float_, float space_used_by_float)
+void LineBuilder::recalculate_available_space()
 {
-    // NOTE: LineBuilder generates lines from left-to-right, so if we've just added a left-side float,
-    //       that means every fragment already on this line has to move towards the right.
-    if (float_ == CSS::Float::Left && !m_containing_block_state.line_boxes.is_empty()) {
-        for (auto& fragment : m_containing_block_state.line_boxes.last().fragments())
-            fragment.set_offset(fragment.offset().translated(space_used_by_float, 0));
-    }
-
-    m_available_width_for_current_line -= space_used_by_float;
-    if (m_available_width_for_current_line < 0)
-        m_available_width_for_current_line = 0;
+    auto current_line_height = max(m_max_height_on_current_line, m_context.containing_block().line_height());
+    auto available_at_top_of_line_box = m_context.available_space_for_line(m_current_y);
+    auto available_at_bottom_of_line_box = m_context.available_space_for_line(m_current_y + current_line_height - 1);
+    m_available_width_for_current_line = min(available_at_bottom_of_line_box, available_at_top_of_line_box);
 }
 
 }
diff --git a/Userland/Libraries/LibWeb/Layout/LineBuilder.h b/Userland/Libraries/LibWeb/Layout/LineBuilder.h
index b240612d64..42fa6f65df 100644
--- a/Userland/Libraries/LibWeb/Layout/LineBuilder.h
+++ b/Userland/Libraries/LibWeb/Layout/LineBuilder.h
@@ -39,11 +39,13 @@ public:
     void remove_last_line_if_empty();
 
     float current_y() const { return m_current_y; }
+    void set_current_y(float y) { m_current_y = y; }
 
-    void adjust_last_line_after_inserting_floating_box(Badge<BlockFormattingContext>, CSS::Float, float space_used_by_float);
+    void recalculate_available_space();
+    float y_for_float_to_be_inserted_here(Box const&);
 
 private:
-    void begin_new_line(bool increment_y);
+    void begin_new_line(bool increment_y, bool is_first_break_in_sequence = true);
 
     bool should_break(float next_item_width);
author	Andreas Kling <kling@serenityos.org>	2022-09-16 14:21:52 +0200
committer	Andreas Kling <kling@serenityos.org>	2022-09-16 15:15:50 +0200
commit	412b2313f33f5efe7f672fed7c26c8fa0187c188 (patch)
tree	4dbbe7a51d94e0ac545283ea3ab6375be1a8d682
parent	54e735924301fd96d54b64c8aa769b813891b1f9 (diff)
download	serenity-412b2313f33f5efe7f672fed7c26c8fa0187c188.zip