LibWeb: Support inline-level padding and border properly

Here's roughly how this works:

- InlineLevelIterator keeps a nesting stack of inline-level nodes with
  box model metrics.
- When entering a node with box model metrics, we add them to the
  current "leading metrics".
- When exiting a node with box model metrics, we add them to the
  current "trailing metrics".
- Pending leading metrics are consumed by the first fragment added
  to the line.
- Pending trailing metrics are consumed by the last fragment added
  to the line.

Like before, the position of a line box fragment is the top left of its
content box. However, fragments are placed horizontally along the line
with space inserted for padding and border.

InlineNode::paint() now expands the content rect as appropriate when
painting background and borders.

Note that margins and margin collapsing is not yet implemented.

This makes the eyes on ACID2 horizontally centered. :^)

8 files changed, 191 insertions, 36 deletions

diff --git a/Userland/Libraries/LibWeb/Layout/InlineFormattingContext.cpp b/Userland/Libraries/LibWeb/Layout/InlineFormattingContext.cpp
index f78559871b..1fec64cbf1 100644
--- a/Userland/Libraries/LibWeb/Layout/InlineFormattingContext.cpp
+++ b/Userland/Libraries/LibWeb/Layout/InlineFormattingContext.cpp
@@ -166,7 +166,7 @@ void InlineFormattingContext::generate_line_boxes(LayoutMode layout_mode)
 {
     containing_block().line_boxes().clear();
 
-    InlineLevelIterator iterator(containing_block(), layout_mode);
+    InlineLevelIterator iterator(*this, containing_block(), layout_mode);
     LineBuilder line_builder(*this);
 
     for (;;) {
@@ -185,18 +185,19 @@ void InlineFormattingContext::generate_line_boxes(LayoutMode layout_mode)
             break;
         case InlineLevelIterator::Item::Type::Element: {
             auto& box = verify_cast<Layout::Box>(*item.node);
-            dimension_box_on_line(box, layout_mode);
-            line_builder.break_if_needed(layout_mode, box.content_width(), item.should_force_break);
-            line_builder.append_box(box);
+            line_builder.break_if_needed(layout_mode, item.border_box_width(), item.should_force_break);
+            line_builder.append_box(box, item.border_start + item.padding_start, item.padding_end + item.border_end);
             break;
         }
         case InlineLevelIterator::Item::Type::Text: {
             auto& text_node = verify_cast<Layout::TextNode>(*item.node);
-            line_builder.break_if_needed(layout_mode, item.width, item.should_force_break);
+            line_builder.break_if_needed(layout_mode, item.border_box_width(), item.should_force_break);
             line_builder.append_text_chunk(
                 text_node,
                 item.offset_in_node,
                 item.length_in_node,
+                item.border_start + item.padding_start,
+                item.padding_end + item.border_end,
                 item.width,
                 text_node.font().glyph_height());
             break;
diff --git a/Userland/Libraries/LibWeb/Layout/InlineLevelIterator.cpp b/Userland/Libraries/LibWeb/Layout/InlineLevelIterator.cpp
index 6b801a1911..4d7fd10053 100644
--- a/Userland/Libraries/LibWeb/Layout/InlineLevelIterator.cpp
+++ b/Userland/Libraries/LibWeb/Layout/InlineLevelIterator.cpp
@@ -5,6 +5,7 @@
  */
 
 #include <LibWeb/Layout/BreakNode.h>
+#include <LibWeb/Layout/InlineFormattingContext.h>
 #include <LibWeb/Layout/InlineLevelIterator.h>
 #include <LibWeb/Layout/InlineNode.h>
 #include <LibWeb/Layout/ListItemMarkerBox.h>
@@ -12,8 +13,51 @@
 
 namespace Web::Layout {
 
+InlineLevelIterator::InlineLevelIterator(Layout::InlineFormattingContext& inline_formatting_context, Layout::BlockContainer& container, LayoutMode layout_mode)
+    : m_inline_formatting_context(inline_formatting_context)
+    , m_container(container)
+    , m_next_node(container.first_child())
+    , m_layout_mode(layout_mode)
+{
+    skip_to_next();
+}
+
+void InlineLevelIterator::enter_node_with_box_model_metrics(Layout::NodeWithStyleAndBoxModelMetrics& node)
+{
+    if (!m_extra_leading_metrics.has_value())
+        m_extra_leading_metrics = ExtraBoxMetrics {};
+
+    node.box_model().margin.left = node.computed_values().margin().left.resolved(node, CSS::Length::make_px(m_container.content_width())).to_px(node);
+    node.box_model().border.left = node.computed_values().border_left().width;
+    node.box_model().padding.left = node.computed_values().padding().left.resolved(node, CSS::Length::make_px(m_container.content_width())).to_px(node);
+
+    m_extra_leading_metrics->margin += node.box_model().margin.left;
+    m_extra_leading_metrics->border += node.box_model().border.left;
+    m_extra_leading_metrics->padding += node.box_model().padding.left;
+
+    m_box_model_node_stack.append(node);
+}
+
+void InlineLevelIterator::exit_node_with_box_model_metrics()
+{
+    if (!m_extra_trailing_metrics.has_value())
+        m_extra_trailing_metrics = ExtraBoxMetrics {};
+
+    auto& node = m_box_model_node_stack.last();
+
+    node.box_model().margin.right = node.computed_values().margin().right.resolved(node, CSS::Length::make_px(m_container.content_width())).to_px(node);
+    node.box_model().border.right = node.computed_values().border_right().width;
+    node.box_model().padding.right = node.computed_values().padding().right.resolved(node, CSS::Length::make_px(m_container.content_width())).to_px(node);
+
+    m_extra_trailing_metrics->margin += node.box_model().margin.right;
+    m_extra_trailing_metrics->border += node.box_model().border.right;
+    m_extra_trailing_metrics->padding += node.box_model().padding.right;
+
+    m_box_model_node_stack.take_last();
+}
+
 // This is similar to Layout::Node::next_in_pre_order() but will not descend into inline-block nodes.
-static Layout::Node* next_inline_node_in_pre_order(Layout::Node& current, Layout::Node const* stay_within)
+Layout::Node* InlineLevelIterator::next_inline_node_in_pre_order(Layout::Node& current, Layout::Node const* stay_within)
 {
     if (current.first_child() && current.first_child()->is_inline() && !current.is_inline_block())
         return current.first_child();
@@ -22,6 +66,12 @@ static Layout::Node* next_inline_node_in_pre_order(Layout::Node& current, Layout
     Layout::Node* next = nullptr;
     while (!(next = node->next_sibling())) {
         node = node->parent();
+
+        // If node is the last node on the "box model node stack", pop it off.
+        if (!m_box_model_node_stack.is_empty()
+            && &m_box_model_node_stack.last() == node) {
+            exit_node_with_box_model_metrics();
+        }
         if (!node || node == stay_within)
             return nullptr;
     }
@@ -29,12 +79,22 @@ static Layout::Node* next_inline_node_in_pre_order(Layout::Node& current, Layout
     return next;
 }
 
-void InlineLevelIterator::skip_to_next()
+void InlineLevelIterator::compute_next()
 {
-    VERIFY(m_current_node);
+    if (m_next_node == nullptr)
+        return;
     do {
-        m_current_node = next_inline_node_in_pre_order(*m_current_node, &m_container);
-    } while (m_current_node && !m_current_node->is_inline());
+        m_next_node = next_inline_node_in_pre_order(*m_next_node, &m_container);
+    } while (m_next_node && !m_next_node->is_inline());
+}
+
+void InlineLevelIterator::skip_to_next()
+{
+    if (m_next_node && is<Layout::NodeWithStyleAndBoxModelMetrics>(*m_next_node))
+        enter_node_with_box_model_metrics(static_cast<Layout::NodeWithStyleAndBoxModelMetrics&>(*m_next_node));
+
+    m_current_node = m_next_node;
+    compute_next();
 }
 
 Optional<InlineLevelIterator::Item> InlineLevelIterator::next(float available_width)
@@ -50,13 +110,17 @@ Optional<InlineLevelIterator::Item> InlineLevelIterator::next(float available_wi
             enter_text_node(text_node, previous_is_empty_or_ends_in_whitespace);
         }
 
-        auto chunk_opt = m_text_node_context->chunk_iterator.next();
+        auto chunk_opt = m_text_node_context->next_chunk;
         if (!chunk_opt.has_value()) {
             m_text_node_context = {};
             skip_to_next();
             return next(available_width);
         }
 
+        m_text_node_context->next_chunk = m_text_node_context->chunk_iterator.next();
+        if (!m_text_node_context->next_chunk.has_value())
+            m_text_node_context->is_last_chunk = true;
+
         auto& chunk = chunk_opt.value();
         float chunk_width = text_node.font().width(chunk.view) + text_node.font().glyph_spacing();
         Item item {
@@ -69,6 +133,7 @@ Optional<InlineLevelIterator::Item> InlineLevelIterator::next(float available_wi
             .is_collapsible_whitespace = m_text_node_context->do_collapse && chunk.is_all_whitespace,
         };
 
+        add_extra_box_model_metrics_to_item(item, m_text_node_context->is_first_chunk, m_text_node_context->is_last_chunk);
         return item;
     }
 
@@ -95,15 +160,24 @@ Optional<InlineLevelIterator::Item> InlineLevelIterator::next(float available_wi
     }
 
     auto& box = verify_cast<Layout::Box>(*m_current_node);
+    m_inline_formatting_context.dimension_box_on_line(box, m_layout_mode);
 
     skip_to_next();
-    return Item {
+    auto item = Item {
         .type = Item::Type::Element,
         .node = &box,
         .offset_in_node = 0,
         .length_in_node = 0,
         .width = box.content_width(),
+        .padding_start = box.box_model().padding.left,
+        .padding_end = box.box_model().padding.right,
+        .border_start = box.box_model().border.left,
+        .border_end = box.box_model().border.right,
+        .margin_start = box.box_model().margin.left,
+        .margin_end = box.box_model().margin.right,
     };
+    add_extra_box_model_metrics_to_item(item, true, true);
+    return item;
 }
 
 void InlineLevelIterator::enter_text_node(Layout::TextNode& text_node, bool previous_is_empty_or_ends_in_whitespace)
@@ -136,8 +210,28 @@ void InlineLevelIterator::enter_text_node(Layout::TextNode& text_node, bool prev
         .do_collapse = do_collapse,
         .do_wrap_lines = do_wrap_lines,
         .do_respect_linebreaks = do_respect_linebreaks,
+        .is_first_chunk = true,
+        .is_last_chunk = false,
         .chunk_iterator = TextNode::ChunkIterator { text_node.text_for_rendering(), m_layout_mode, do_wrap_lines, do_respect_linebreaks },
     };
+    m_text_node_context->next_chunk = m_text_node_context->chunk_iterator.next();
+}
+
+void InlineLevelIterator::add_extra_box_model_metrics_to_item(Item& item, bool add_leading_metrics, bool add_trailing_metrics)
+{
+    if (add_leading_metrics && m_extra_leading_metrics.has_value()) {
+        item.margin_start += m_extra_leading_metrics->margin;
+        item.border_start += m_extra_leading_metrics->border;
+        item.padding_start += m_extra_leading_metrics->padding;
+        m_extra_leading_metrics = {};
+    }
+
+    if (add_trailing_metrics && m_extra_trailing_metrics.has_value()) {
+        item.margin_end += m_extra_trailing_metrics->margin;
+        item.border_end += m_extra_trailing_metrics->border;
+        item.padding_end += m_extra_trailing_metrics->padding;
+        m_extra_trailing_metrics = {};
+    }
 }
 
 }
diff --git a/Userland/Libraries/LibWeb/Layout/InlineLevelIterator.h b/Userland/Libraries/LibWeb/Layout/InlineLevelIterator.h
index 9621d92570..b7039c7db5 100644
--- a/Userland/Libraries/LibWeb/Layout/InlineLevelIterator.h
+++ b/Userland/Libraries/LibWeb/Layout/InlineLevelIterator.h
@@ -8,6 +8,7 @@
 
 #include <AK/Noncopyable.h>
 #include <LibWeb/Layout/BlockContainer.h>
+#include <LibWeb/Layout/InlineNode.h>
 #include <LibWeb/Layout/TextNode.h>
 
 namespace Web::Layout {
@@ -31,36 +32,66 @@ public:
         size_t offset_in_node { 0 };
         size_t length_in_node { 0 };
         float width { 0.0f };
+        float padding_start { 0.0f };
+        float padding_end { 0.0f };
+        float border_start { 0.0f };
+        float border_end { 0.0f };
+        float margin_start { 0.0f };
+        float margin_end { 0.0f };
         bool should_force_break { false };
         bool is_collapsible_whitespace { false };
+
+        float border_box_width() const
+        {
+            return border_start + padding_start + width + padding_end + border_end;
+        }
     };
 
-    explicit InlineLevelIterator(Layout::BlockContainer& container, LayoutMode layout_mode)
-        : m_container(container)
-        , m_current_node(container.first_child())
-        , m_layout_mode(layout_mode)
-    {
-    }
+    InlineLevelIterator(Layout::InlineFormattingContext&, Layout::BlockContainer&, LayoutMode);
 
     Optional<Item> next(float available_width);
 
 private:
     void skip_to_next();
+    void compute_next();
 
     void enter_text_node(Layout::TextNode&, bool previous_is_empty_or_ends_in_whitespace);
 
+    void enter_node_with_box_model_metrics(Layout::NodeWithStyleAndBoxModelMetrics&);
+    void exit_node_with_box_model_metrics();
+
+    void add_extra_box_model_metrics_to_item(Item&, bool add_leading_metrics, bool add_trailing_metrics);
+
+    Layout::Node* next_inline_node_in_pre_order(Layout::Node& current, Layout::Node const* stay_within);
+
+    Layout::InlineFormattingContext& m_inline_formatting_context;
     Layout::BlockContainer& m_container;
     Layout::Node* m_current_node { nullptr };
+    Layout::Node* m_next_node { nullptr };
     LayoutMode const m_layout_mode;
 
     struct TextNodeContext {
         bool do_collapse {};
         bool do_wrap_lines {};
         bool do_respect_linebreaks {};
+        bool is_first_chunk {};
+        bool is_last_chunk {};
         TextNode::ChunkIterator chunk_iterator;
+        Optional<TextNode::Chunk> next_chunk {};
     };
 
     Optional<TextNodeContext> m_text_node_context;
+
+    struct ExtraBoxMetrics {
+        float margin { 0 };
+        float border { 0 };
+        float padding { 0 };
+    };
+
+    Optional<ExtraBoxMetrics> m_extra_leading_metrics;
+    Optional<ExtraBoxMetrics> m_extra_trailing_metrics;
+
+    Vector<NodeWithStyleAndBoxModelMetrics&> m_box_model_node_stack;
 };
 
 }
diff --git a/Userland/Libraries/LibWeb/Layout/InlineNode.cpp b/Userland/Libraries/LibWeb/Layout/InlineNode.cpp
index 1ac4fd6b98..3f4300f830 100644
--- a/Userland/Libraries/LibWeb/Layout/InlineNode.cpp
+++ b/Userland/Libraries/LibWeb/Layout/InlineNode.cpp
@@ -38,8 +38,20 @@ void InlineNode::paint(PaintContext& context, PaintPhase phase)
         auto bottom_left_border_radius = computed_values().border_bottom_left_radius();
         auto containing_block_position_in_absolute_coordinates = containing_block()->absolute_position();
 
-        for_each_fragment([&](auto const& fragment) {
+        for_each_fragment([&](auto const& fragment, bool is_first_fragment, bool is_last_fragment) {
             Gfx::FloatRect absolute_fragment_rect { containing_block_position_in_absolute_coordinates.translated(fragment.offset()), fragment.size() };
+
+            if (is_first_fragment) {
+                float extra_start_width = box_model().padding.left;
+                absolute_fragment_rect.translate_by(-extra_start_width, 0);
+                absolute_fragment_rect.set_width(absolute_fragment_rect.width() + extra_start_width);
+            }
+
+            if (is_last_fragment) {
+                float extra_end_width = box_model().padding.right;
+                absolute_fragment_rect.set_width(absolute_fragment_rect.width() + extra_end_width);
+            }
+
             auto border_radius_data = Painting::normalized_border_radius_data(*this, absolute_fragment_rect, top_left_border_radius, top_right_border_radius, bottom_right_border_radius, bottom_left_border_radius);
             Painting::paint_background(context, *this, enclosing_int_rect(absolute_fragment_rect), computed_values().background_color(), &computed_values().background_layers(), border_radius_data);
 
@@ -77,8 +89,20 @@ void InlineNode::paint(PaintContext& context, PaintPhase phase)
 
         auto containing_block_position_in_absolute_coordinates = containing_block()->absolute_position();
 
-        for_each_fragment([&](auto& fragment) {
+        for_each_fragment([&](auto const& fragment, bool is_first_fragment, bool is_last_fragment) {
             Gfx::FloatRect absolute_fragment_rect { containing_block_position_in_absolute_coordinates.translated(fragment.offset()), fragment.size() };
+
+            if (is_first_fragment) {
+                float extra_start_width = box_model().padding.left;
+                absolute_fragment_rect.translate_by(-extra_start_width, 0);
+                absolute_fragment_rect.set_width(absolute_fragment_rect.width() + extra_start_width);
+            }
+
+            if (is_last_fragment) {
+                float extra_end_width = box_model().padding.right;
+                absolute_fragment_rect.set_width(absolute_fragment_rect.width() + extra_end_width);
+            }
+
             auto bordered_rect = absolute_fragment_rect.inflated(borders_data.top.width, borders_data.right.width, borders_data.bottom.width, borders_data.left.width);
             auto border_radius_data = Painting::normalized_border_radius_data(*this, bordered_rect, top_left_border_radius, top_right_border_radius, bottom_right_border_radius, bottom_left_border_radius);
 
@@ -92,7 +116,7 @@ void InlineNode::paint(PaintContext& context, PaintPhase phase)
         // FIXME: This paints a double-thick border between adjacent fragments, where ideally there
         //        would be none. Once we implement non-rectangular outlines for the `outline` CSS
         //        property, we can use that here instead.
-        for_each_fragment([&](auto& fragment) {
+        for_each_fragment([&](auto& fragment, bool, bool) {
             painter.draw_rect(enclosing_int_rect(fragment.absolute_rect()), Color::Magenta);
             return IterationDecision::Continue;
         });
@@ -103,11 +127,16 @@ template<typename Callback>
 void InlineNode::for_each_fragment(Callback callback)
 {
     // FIXME: This will be slow if the containing block has a lot of fragments!
+    Vector<LineBoxFragment const&> fragments;
     containing_block()->for_each_fragment([&](auto& fragment) {
-        if (!is_inclusive_ancestor_of(fragment.layout_node()))
-            return IterationDecision::Continue;
-        return callback(fragment);
+        if (is_inclusive_ancestor_of(fragment.layout_node()))
+            fragments.append(fragment);
+        return IterationDecision::Continue;
     });
+    for (size_t i = 0; i < fragments.size(); ++i) {
+        auto const& fragment = fragments[i];
+        callback(fragment, i == 0, i == fragments.size() - 1);
+    }
 }
 
 }
diff --git a/Userland/Libraries/LibWeb/Layout/LineBox.cpp b/Userland/Libraries/LibWeb/Layout/LineBox.cpp
index 50a65af787..cbec544844 100644
--- a/Userland/Libraries/LibWeb/Layout/LineBox.cpp
+++ b/Userland/Libraries/LibWeb/Layout/LineBox.cpp
@@ -15,18 +15,18 @@
 
 namespace Web::Layout {
 
-void LineBox::add_fragment(Node& layout_node, int start, int length, float width, float height, LineBoxFragment::Type fragment_type)
+void LineBox::add_fragment(Node& layout_node, int start, int length, float leading_size, float trailing_size, float content_width, float content_height, LineBoxFragment::Type fragment_type)
 {
     bool text_align_is_justify = layout_node.computed_values().text_align() == CSS::TextAlign::Justify;
     if (!text_align_is_justify && !m_fragments.is_empty() && &m_fragments.last().layout_node() == &layout_node) {
         // The fragment we're adding is from the last Layout::Node on the line.
         // Expand the last fragment instead of adding a new one with the same Layout::Node.
         m_fragments.last().m_length = (start - m_fragments.last().m_start) + length;
-        m_fragments.last().set_width(m_fragments.last().width() + width);
+        m_fragments.last().set_width(m_fragments.last().width() + content_width);
     } else {
-        m_fragments.append(make<LineBoxFragment>(layout_node, start, length, Gfx::FloatPoint(m_width, 0.0f), Gfx::FloatSize(width, height), fragment_type));
+        m_fragments.append(make<LineBoxFragment>(layout_node, start, length, Gfx::FloatPoint(m_width + leading_size, 0.0f), Gfx::FloatSize(content_width, content_height), fragment_type));
     }
-    m_width += width;
+    m_width += content_width + leading_size + trailing_size;
 
     if (is<Box>(layout_node))
         verify_cast<Box>(layout_node).set_containing_line_box_fragment(m_fragments.last());
diff --git a/Userland/Libraries/LibWeb/Layout/LineBox.h b/Userland/Libraries/LibWeb/Layout/LineBox.h
index 5a02a4ea06..e0503aacf2 100644
--- a/Userland/Libraries/LibWeb/Layout/LineBox.h
+++ b/Userland/Libraries/LibWeb/Layout/LineBox.h
@@ -18,7 +18,7 @@ public:
 
     float width() const { return m_width; }
 
-    void add_fragment(Node& layout_node, int start, int length, float width, float height, LineBoxFragment::Type = LineBoxFragment::Type::Normal);
+    void add_fragment(Node& layout_node, int start, int length, float leading_size, float trailing_size, float content_width, float content_height, LineBoxFragment::Type = LineBoxFragment::Type::Normal);
 
     const NonnullOwnPtrVector<LineBoxFragment>& fragments() const { return m_fragments; }
     NonnullOwnPtrVector<LineBoxFragment>& fragments() { return m_fragments; }
diff --git a/Userland/Libraries/LibWeb/Layout/LineBuilder.cpp b/Userland/Libraries/LibWeb/Layout/LineBuilder.cpp
index 977e480b1d..73884f4e6e 100644
--- a/Userland/Libraries/LibWeb/Layout/LineBuilder.cpp
+++ b/Userland/Libraries/LibWeb/Layout/LineBuilder.cpp
@@ -39,16 +39,16 @@ void LineBuilder::begin_new_line(bool increment_y)
     m_last_line_needs_update = true;
 }
 
-void LineBuilder::append_box(Box& box)
+void LineBuilder::append_box(Box& box, float leading_size, float trailing_size)
 {
-    m_context.containing_block().ensure_last_line_box().add_fragment(box, 0, 0, box.content_width(), box.content_height());
+    m_context.containing_block().ensure_last_line_box().add_fragment(box, 0, 0, leading_size, trailing_size, box.content_width(), box.content_height());
     m_max_height_on_current_line = max(m_max_height_on_current_line, box.content_height());
 }
 
-void LineBuilder::append_text_chunk(TextNode& text_node, size_t offset_in_node, size_t length_in_node, float width, float height)
+void LineBuilder::append_text_chunk(TextNode& text_node, size_t offset_in_node, size_t length_in_node, float leading_size, float trailing_size, float content_width, float content_height)
 {
-    m_context.containing_block().ensure_last_line_box().add_fragment(text_node, offset_in_node, length_in_node, width, height);
-    m_max_height_on_current_line = max(m_max_height_on_current_line, height);
+    m_context.containing_block().ensure_last_line_box().add_fragment(text_node, offset_in_node, length_in_node, leading_size, trailing_size, content_width, content_height);
+    m_max_height_on_current_line = max(m_max_height_on_current_line, content_height);
 }
 
 bool LineBuilder::should_break(LayoutMode layout_mode, float next_item_width, bool should_force_break)
diff --git a/Userland/Libraries/LibWeb/Layout/LineBuilder.h b/Userland/Libraries/LibWeb/Layout/LineBuilder.h
index dea23ad737..9ccb0ed233 100644
--- a/Userland/Libraries/LibWeb/Layout/LineBuilder.h
+++ b/Userland/Libraries/LibWeb/Layout/LineBuilder.h
@@ -19,8 +19,8 @@ public:
     ~LineBuilder();
 
     void break_line();
-    void append_box(Box&);
-    void append_text_chunk(TextNode&, size_t offset_in_node, size_t length_in_node, float width, float height);
+    void append_box(Box&, float leading_size, float trailing_size);
+    void append_text_chunk(TextNode&, size_t offset_in_node, size_t length_in_node, float leading_size, float trailing_size, float content_width, float content_height);
 
     void break_if_needed(LayoutMode layout_mode, float next_item_width, bool should_force_break)
     {