LibWeb: Add inline-level iterator that enumerates items for line layout

This patch adds a new mechanism that allows InlineFormattingContext to
build line boxes incrementally instead of all-in-one go.

Incremental build will eventually allow much better support for CSS
floating objects.

6 files changed, 248 insertions, 13 deletions

diff --git a/Userland/Libraries/LibWeb/CMakeLists.txt b/Userland/Libraries/LibWeb/CMakeLists.txt
index f13b78c5ed..f5aff4bdd2 100644
--- a/Userland/Libraries/LibWeb/CMakeLists.txt
+++ b/Userland/Libraries/LibWeb/CMakeLists.txt
@@ -215,6 +215,7 @@ set(SOURCES
     Layout/ImageBox.cpp
     Layout/InitialContainingBlock.cpp
     Layout/InlineFormattingContext.cpp
+    Layout/InlineLevelIterator.cpp
     Layout/InlineNode.cpp
     Layout/Label.cpp
     Layout/LayoutPosition.cpp
diff --git a/Userland/Libraries/LibWeb/Layout/InlineFormattingContext.cpp b/Userland/Libraries/LibWeb/Layout/InlineFormattingContext.cpp
index a8d0eb9d83..a1cf598434 100644
--- a/Userland/Libraries/LibWeb/Layout/InlineFormattingContext.cpp
+++ b/Userland/Libraries/LibWeb/Layout/InlineFormattingContext.cpp
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2020, Andreas Kling <kling@serenityos.org>
+ * Copyright (c) 2020-2022, Andreas Kling <kling@serenityos.org>
  *
  * SPDX-License-Identifier: BSD-2-Clause
  */
@@ -11,6 +11,7 @@
 #include <LibWeb/Layout/BlockFormattingContext.h>
 #include <LibWeb/Layout/Box.h>
 #include <LibWeb/Layout/InlineFormattingContext.h>
+#include <LibWeb/Layout/InlineLevelIterator.h>
 #include <LibWeb/Layout/ReplacedBox.h>
 
 namespace Web::Layout {
@@ -74,25 +75,17 @@ float InlineFormattingContext::available_width_at_line(size_t line_index) const
 void InlineFormattingContext::run(Box&, LayoutMode layout_mode)
 {
     VERIFY(containing_block().children_are_inline());
-    containing_block().line_boxes().clear();
+
+    generate_line_boxes(layout_mode);
+
     containing_block().for_each_child([&](auto& child) {
         VERIFY(child.is_inline());
         if (is<Box>(child) && child.is_absolutely_positioned()) {
             layout_absolutely_positioned_element(verify_cast<Box>(child));
             return;
         }
-
-        child.split_into_lines(*this, layout_mode);
     });
 
-    for (auto& line_box : containing_block().line_boxes()) {
-        line_box.trim_trailing_whitespace();
-    }
-
-    // If there's an empty line box at the bottom, just remove it instead of giving it height.
-    if (!containing_block().line_boxes().is_empty() && containing_block().line_boxes().last().fragments().is_empty())
-        containing_block().line_boxes().take_last();
-
     auto text_align = containing_block().computed_values().text_align();
     float min_line_height = containing_block().line_height();
     float content_height = 0;
@@ -234,4 +227,60 @@ void InlineFormattingContext::dimension_box_on_line(Box& box, LayoutMode layout_
     dump_tree(box);
 }
 
+void InlineFormattingContext::generate_line_boxes(LayoutMode layout_mode)
+{
+    auto& line_boxes = containing_block().line_boxes();
+    line_boxes.clear();
+    containing_block().ensure_last_line_box();
+
+    InlineLevelIterator iterator(containing_block(), layout_mode);
+
+    float available_width = containing_block().width();
+
+    for (;;) {
+        auto item_opt = iterator.next(available_width);
+        if (!item_opt.has_value())
+            break;
+        auto& item = item_opt.value();
+
+        float current_line_width = line_boxes.last().width();
+
+        bool should_break_here = layout_mode == LayoutMode::AllPossibleLineBreaks || (current_line_width + item.width) > available_width;
+
+        if (should_break_here)
+            line_boxes.append(LineBox());
+
+        if (item.type == InlineLevelIterator::Item::Type::ForcedBreak) {
+            line_boxes.append(LineBox());
+            continue;
+        }
+
+        if (item.type == InlineLevelIterator::Item::Type::Element) {
+            auto& box = verify_cast<Layout::Box>(*item.node);
+            dimension_box_on_line(box, LayoutMode::Default);
+            line_boxes.last().add_fragment(box, 0, 0, box.width(), box.height());
+            continue;
+        }
+
+        if (item.type == InlineLevelIterator::Item::Type::Text) {
+            auto& text_node = verify_cast<Layout::TextNode>(*item.node);
+            line_boxes.last().add_fragment(
+                text_node,
+                item.offset_in_node,
+                item.length_in_node,
+                item.width,
+                text_node.font().glyph_height());
+            continue;
+        }
+    }
+
+    for (auto& line_box : containing_block().line_boxes()) {
+        line_box.trim_trailing_whitespace();
+    }
+
+    // If there's an empty line box at the bottom, just remove it instead of giving it height.
+    if (!containing_block().line_boxes().is_empty() && containing_block().line_boxes().last().fragments().is_empty())
+        containing_block().line_boxes().take_last();
+}
+
 }
diff --git a/Userland/Libraries/LibWeb/Layout/InlineFormattingContext.h b/Userland/Libraries/LibWeb/Layout/InlineFormattingContext.h
index fbf75b1684..43fdef047b 100644
--- a/Userland/Libraries/LibWeb/Layout/InlineFormattingContext.h
+++ b/Userland/Libraries/LibWeb/Layout/InlineFormattingContext.h
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2020, Andreas Kling <kling@serenityos.org>
+ * Copyright (c) 2020-2022, Andreas Kling <kling@serenityos.org>
  *
  * SPDX-License-Identifier: BSD-2-Clause
  */
@@ -26,6 +26,9 @@ public:
     float available_width_at_line(size_t line_index) const;
 
     void dimension_box_on_line(Box&, LayoutMode);
+
+private:
+    void generate_line_boxes(LayoutMode);
 };
 
 }
diff --git a/Userland/Libraries/LibWeb/Layout/InlineLevelIterator.cpp b/Userland/Libraries/LibWeb/Layout/InlineLevelIterator.cpp
new file mode 100644
index 0000000000..ef894e4d6d
--- /dev/null
+++ b/Userland/Libraries/LibWeb/Layout/InlineLevelIterator.cpp
@@ -0,0 +1,117 @@
+/*
+ * Copyright (c) 2022, Andreas Kling <kling@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibWeb/Layout/BreakNode.h>
+#include <LibWeb/Layout/InlineLevelIterator.h>
+#include <LibWeb/Layout/InlineNode.h>
+#include <LibWeb/Layout/ReplacedBox.h>
+
+namespace Web::Layout {
+
+void InlineLevelIterator::skip_to_next()
+{
+    VERIFY(m_current_node);
+    do {
+        m_current_node = m_current_node->next_in_pre_order(&m_container);
+    } while (m_current_node && !m_current_node->is_inline());
+}
+
+Optional<InlineLevelIterator::Item> InlineLevelIterator::next(float available_width)
+{
+    if (!m_current_node)
+        return {};
+
+    if (is<Layout::TextNode>(*m_current_node)) {
+        auto& text_node = static_cast<Layout::TextNode&>(*m_current_node);
+
+        if (!m_text_node_context.has_value())
+            enter_text_node(text_node);
+
+        auto chunk_opt = m_text_node_context->chunk_iterator.next();
+        if (!chunk_opt.has_value()) {
+            m_text_node_context = {};
+            skip_to_next();
+            return next(available_width);
+        }
+
+        auto& chunk = chunk_opt.value();
+        float chunk_width = text_node.font().width(chunk.view) + text_node.font().glyph_spacing();
+        Item item {
+            .type = Item::Type::Text,
+            .node = &text_node,
+            .offset_in_node = chunk.start,
+            .length_in_node = chunk.length,
+            .width = chunk_width,
+        };
+
+        return item;
+    }
+
+    if (is<Layout::BreakNode>(*m_current_node)) {
+        skip_to_next();
+        return Item {
+            .type = Item::Type::ForcedBreak,
+        };
+    }
+
+    if (!is<Layout::Box>(*m_current_node)) {
+        skip_to_next();
+        return next(available_width);
+    }
+
+    if (is<Layout::ReplacedBox>(*m_current_node)) {
+        auto& replaced_box = static_cast<Layout::ReplacedBox&>(*m_current_node);
+        replaced_box.prepare_for_replaced_layout();
+    }
+
+    auto& box = verify_cast<Layout::Box>(*m_current_node);
+
+    skip_to_next();
+    return Item {
+        .type = Item::Type::Element,
+        .node = &box,
+        .offset_in_node = 0,
+        .length_in_node = 0,
+        .width = box.width(),
+    };
+}
+
+void InlineLevelIterator::enter_text_node(Layout::TextNode& text_node)
+{
+    bool do_collapse = true;
+    bool do_wrap_lines = true;
+    bool do_respect_linebreaks = false;
+
+    if (text_node.computed_values().white_space() == CSS::WhiteSpace::Nowrap) {
+        do_collapse = true;
+        do_wrap_lines = false;
+        do_respect_linebreaks = false;
+    } else if (text_node.computed_values().white_space() == CSS::WhiteSpace::Pre) {
+        do_collapse = false;
+        do_wrap_lines = false;
+        do_respect_linebreaks = true;
+    } else if (text_node.computed_values().white_space() == CSS::WhiteSpace::PreLine) {
+        do_collapse = true;
+        do_wrap_lines = true;
+        do_respect_linebreaks = true;
+    } else if (text_node.computed_values().white_space() == CSS::WhiteSpace::PreWrap) {
+        do_collapse = false;
+        do_wrap_lines = true;
+        do_respect_linebreaks = true;
+    }
+
+    // FIXME: Pass the correct value for the last boolean!
+    text_node.compute_text_for_rendering(do_collapse, true);
+
+    m_text_node_context = TextNodeContext {
+        .do_collapse = do_collapse,
+        .do_wrap_lines = do_wrap_lines,
+        .do_respect_linebreaks = do_respect_linebreaks,
+        .chunk_iterator = TextNode::ChunkIterator { text_node.text_for_rendering(), m_layout_mode, do_wrap_lines, do_respect_linebreaks },
+    };
+}
+
+}
diff --git a/Userland/Libraries/LibWeb/Layout/InlineLevelIterator.h b/Userland/Libraries/LibWeb/Layout/InlineLevelIterator.h
new file mode 100644
index 0000000000..174e3385bc
--- /dev/null
+++ b/Userland/Libraries/LibWeb/Layout/InlineLevelIterator.h
@@ -0,0 +1,64 @@
+/*
+ * Copyright (c) 2022, Andreas Kling <kling@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#pragma once
+
+#include <AK/Noncopyable.h>
+#include <LibWeb/Layout/Box.h>
+#include <LibWeb/Layout/TextNode.h>
+
+namespace Web::Layout {
+
+// This class iterates over all the inline-level objects within an inline formatting context.
+// By repeatedly calling next() with the remaining available width on the current line,
+// it returns an "Item" representing the next piece of inline-level content to be placed on the line.
+class InlineLevelIterator {
+    AK_MAKE_NONCOPYABLE(InlineLevelIterator);
+    AK_MAKE_NONMOVABLE(InlineLevelIterator);
+
+public:
+    struct Item {
+        enum class Type {
+            Text,
+            Element,
+            ForcedBreak,
+        };
+        Type type {};
+        Layout::Node* node { nullptr };
+        size_t offset_in_node { 0 };
+        size_t length_in_node { 0 };
+        float width { 0.0f };
+    };
+
+    explicit InlineLevelIterator(Layout::Box& container, LayoutMode layout_mode)
+        : m_container(container)
+        , m_current_node(container.first_child())
+        , m_layout_mode(layout_mode)
+    {
+    }
+
+    Optional<Item> next(float available_width);
+
+private:
+    void skip_to_next();
+
+    void enter_text_node(Layout::TextNode&);
+
+    Layout::Box& m_container;
+    Layout::Node* m_current_node { nullptr };
+    LayoutMode const m_layout_mode;
+
+    struct TextNodeContext {
+        bool do_collapse {};
+        bool do_wrap_lines {};
+        bool do_respect_linebreaks {};
+        TextNode::ChunkIterator chunk_iterator;
+    };
+
+    Optional<TextNodeContext> m_text_node_context;
+};
+
+}
diff --git a/Userland/Libraries/LibWeb/Layout/LineBox.h b/Userland/Libraries/LibWeb/Layout/LineBox.h
index 6e6a3b3cd9..d28f2181a5 100644
--- a/Userland/Libraries/LibWeb/Layout/LineBox.h
+++ b/Userland/Libraries/LibWeb/Layout/LineBox.h
@@ -26,6 +26,7 @@ public:
     void trim_trailing_whitespace();
 
     bool is_empty_or_ends_in_whitespace() const;
+    bool is_empty() { return m_fragments.is_empty(); }
     bool ends_with_forced_line_break() const;
 
 private: