LibWeb: Start implementation of CSS Table 3 spec

Here I try to address bug where content of table overflows
it's width (hacker news is an example of such site) by
reimplementing some parts of table formatting context.

Now TFC implements first steps of:
https://www.w3.org/TR/css-tables-3/#table-layout-algorithm
but column width and row height distribution steps are
still very incomplete.

4 files changed, 242 insertions, 172 deletions

diff --git a/Userland/Libraries/LibWeb/Layout/TableFormattingContext.cpp b/Userland/Libraries/LibWeb/Layout/TableFormattingContext.cpp
index 5e2a95dd1b..c9e5917ea8 100644
--- a/Userland/Libraries/LibWeb/Layout/TableFormattingContext.cpp
+++ b/Userland/Libraries/LibWeb/Layout/TableFormattingContext.cpp
@@ -14,6 +14,26 @@
 #include <LibWeb/Layout/TableRowBox.h>
 #include <LibWeb/Layout/TableRowGroupBox.h>
 
+struct GridPosition {
+    size_t x;
+    size_t y;
+};
+
+inline bool operator==(GridPosition const& a, GridPosition const& b)
+{
+    return a.x == b.x && a.y == b.y;
+}
+
+namespace AK {
+template<>
+struct Traits<GridPosition> : public GenericTraits<GridPosition> {
+    static unsigned hash(GridPosition const& key)
+    {
+        return pair_int_hash(key.x, key.y);
+    }
+};
+}
+
 namespace Web::Layout {
 
 TableFormattingContext::TableFormattingContext(LayoutState& state, BlockContainer const& block_container, FormattingContext* parent)
@@ -23,192 +43,237 @@ TableFormattingContext::TableFormattingContext(LayoutState& state, BlockContaine
 
 TableFormattingContext::~TableFormattingContext() = default;
 
-void TableFormattingContext::run(Box const& box, LayoutMode, AvailableSpace const& available_space)
+void TableFormattingContext::calculate_row_column_grid(Box const& box)
 {
-    auto& box_state = m_state.get_mutable(box);
+    // Implements https://html.spec.whatwg.org/multipage/tables.html#forming-a-table
+    HashMap<GridPosition, bool> grid;
 
-    compute_width(box, available_space);
-    auto table_width = CSS::Length::make_px(box_state.content_width());
-    auto table_width_is_auto = box.computed_values().width().is_auto();
+    size_t x_width = 0, y_height = 0;
+    size_t x_current = 0, y_current = 0;
 
-    float total_content_width = 0;
-    float total_content_height = 0;
+    auto process_row = [&](auto& row) {
+        if (y_height == y_current)
+            y_height++;
 
-    Vector<ColumnWidth> column_widths;
-    box.for_each_child_of_type<TableRowGroupBox>([&](auto& row_group_box) {
-        compute_width(row_group_box, available_space);
-        auto column_count = row_group_box.column_count();
-        column_widths.resize(max(column_count, column_widths.size()));
+        x_current = 0;
+        while (x_current < x_width && grid.contains(GridPosition { x_current, y_current }))
+            x_current++;
 
-        row_group_box.template for_each_child_of_type<TableRowBox>([&](auto& row) {
-            calculate_column_widths(row, table_width, column_widths, available_space);
-        });
-    });
-    box.for_each_child_of_type<TableRowGroupBox>([&](auto& row_group_box) {
-        auto& row_group_box_state = m_state.get_mutable(row_group_box);
+        for (auto* child = row.first_child(); child; child = child->next_sibling()) {
+            if (is<TableCellBox>(*child)) {
+                Box* box = static_cast<Box*>(child);
+                if (x_current == x_width)
+                    x_width++;
 
-        float remaining_for_max = box_state.content_width();
-        float remaining_for_min = box_state.content_width();
-        for (auto& column_width : column_widths) {
-            remaining_for_max -= column_width.max;
-            remaining_for_min -= column_width.min;
-        }
+                const size_t colspan = static_cast<TableCellBox*>(child)->colspan();
+                const size_t rowspan = 1;
 
-        bool max_fits = remaining_for_max >= 0;
-        bool min_fits = remaining_for_min >= 0;
+                if (x_width < x_current + colspan)
+                    x_width = x_current + colspan;
+                if (y_height < y_current + rowspan)
+                    y_height = y_current + rowspan;
 
-        if (max_fits) {
-            for (auto& column_width : column_widths)
-                column_width.used = column_width.max;
-        } else {
-            for (auto& column_width : column_widths)
-                column_width.used = column_width.min;
-        }
+                for (size_t y = y_current; y < y_current + rowspan; y++)
+                    for (size_t x = x_current; x < x_current + colspan; x++)
+                        grid.set(GridPosition { x, y }, true);
+                m_cells.append(Cell { *box, x_current, y_current, colspan, rowspan });
 
-        if (!table_width_is_auto || (min_fits && !max_fits)) {
-            float missing_width = max_fits ? remaining_for_max : remaining_for_min;
-            if (missing_width > 0) {
-                size_t num_auto_columns = 0;
-                for (auto& column_width : column_widths) {
-                    if (column_width.is_auto)
-                        num_auto_columns++;
-                }
-                if (num_auto_columns) {
-                    float extra = missing_width / (float)num_auto_columns;
-                    for (auto& column_width : column_widths) {
-                        if (column_width.is_auto)
-                            column_width.used += extra;
-                    }
-                }
+                x_current += colspan;
             }
         }
 
-        float content_width = 0;
-        float content_height = 0;
+        m_rows.append(Row { row });
+        y_current++;
+    };
 
+    box.template for_each_child_of_type<TableRowGroupBox>([&](auto& row_group_box) {
         row_group_box.template for_each_child_of_type<TableRowBox>([&](auto& row) {
-            auto& row_state = m_state.get_mutable(row);
-            row_state.offset = { 0, content_height };
-            layout_row(row, column_widths, available_space);
-            content_width = max(content_width, row_state.content_width());
-            content_height += row_state.content_height();
+            process_row(row);
+            return IterationDecision::Continue;
         });
-
-        if (row_group_box.computed_values().width().is_auto())
-            row_group_box_state.set_content_width(content_width);
-        row_group_box_state.set_content_height(content_height);
-
-        row_group_box_state.offset = { 0, total_content_height };
-        total_content_height += content_height;
-        total_content_width = max(total_content_width, row_group_box_state.content_width());
     });
 
-    if (table_width_is_auto)
-        box_state.set_content_width(total_content_width);
+    m_columns.resize(x_width);
+}
 
-    // FIXME: This is a total hack, we should respect the 'height' property.
-    m_automatic_content_height = total_content_height;
+void TableFormattingContext::compute_table_measures()
+{
+    for (auto& cell : m_cells) {
+        auto width_of_containing_block = m_state.get(*cell.box.containing_block()).content_width();
+        auto width_of_containing_block_as_length = CSS::Length::make_px(width_of_containing_block);
+        float padding_left = cell.box.computed_values().padding().left().resolved(cell.box, width_of_containing_block_as_length).to_px(cell.box);
+        float padding_right = cell.box.computed_values().padding().right().resolved(cell.box, width_of_containing_block_as_length).to_px(cell.box);
+        float border_left = cell.box.computed_values().border_left().width;
+        float border_right = cell.box.computed_values().border_right().width;
+
+        auto min_width = calculate_min_content_width(cell.box) + padding_left + padding_right + border_left + border_right;
+        auto max_width = calculate_max_content_width(cell.box) + padding_left + padding_right + border_left + border_right;
+        m_columns[cell.column_index].min_width = max(m_columns[cell.column_index].min_width, min_width);
+        m_columns[cell.column_index].max_width = max(m_columns[cell.column_index].max_width, max_width);
+    }
+
+    for (auto& column : m_columns) {
+        column.used_width = column.min_width;
+    }
 }
 
-void TableFormattingContext::calculate_column_widths(Box const& row, CSS::Length const& table_width, Vector<ColumnWidth>& column_widths, AvailableSpace const& available_space)
+void TableFormattingContext::compute_table_width(float& extra_width)
 {
-    m_state.get_mutable(row);
-    size_t column_index = 0;
-    row.for_each_child_of_type<TableCellBox>([&](auto& cell) {
-        auto& cell_state = m_state.get_mutable(cell);
-        auto const& computed_values = cell.computed_values();
-        auto specified_width = computed_values.width().resolved(cell, table_width).resolved(cell);
-
-        if (specified_width.is_auto()) {
-            auto width = calculate_max_content_width(cell);
-            cell_state.set_content_width(width);
-        } else {
-            compute_width(cell, AvailableSpace(AvailableSize::make_indefinite(), AvailableSize::make_indefinite()), LayoutMode::Normal);
-        }
+    auto const& table_box = context_box();
+    auto& table_box_state = m_state.get_mutable(table_box);
 
-        if (auto independent_formatting_context = layout_inside(cell, LayoutMode::Normal, cell_state.available_inner_space_or_constraints_from(available_space)))
-            independent_formatting_context->parent_context_did_dimension_child_root_box();
+    auto& computed_values = table_box.computed_values();
 
-        if (cell.colspan() == 1) {
-            auto min_width = calculate_min_content_width(cell);
-            auto max_width = calculate_max_content_width(cell);
-            min_width = max(min_width, cell_state.border_box_width());
-            max_width = max(max_width, cell_state.border_box_width());
-            column_widths[column_index].min = max(column_widths[column_index].min, min_width);
-            column_widths[column_index].max = max(column_widths[column_index].max, max_width);
-            column_widths[column_index].is_auto &= specified_width.is_auto();
-        }
-        column_index += cell.colspan();
-    });
-    column_index = 0;
-    row.for_each_child_of_type<TableCellBox>([&](auto& cell) {
-        size_t colspan = cell.colspan();
-        if (colspan > 1) {
-            auto& cell_state = m_state.get_mutable(cell);
-            auto min_width = calculate_min_content_width(cell);
-            auto max_width = calculate_max_content_width(cell);
-            float missing_min = max(min_width, cell_state.border_box_width());
-            float missing_max = max(max_width, cell_state.border_box_width());
-            for (size_t i = 0; i < colspan; ++i) {
-                missing_min -= column_widths[column_index + i].min;
-                missing_max -= column_widths[column_index + i].max;
-            }
-            if (missing_min > 0) {
-                float extra = missing_min / (float)colspan;
-                for (size_t i = 0; i < colspan; ++i)
-                    column_widths[column_index + i].min += extra;
-            }
-            if (missing_max > 0) {
-                float extra = missing_max / (float)colspan;
-                for (size_t i = 0; i < colspan; ++i)
-                    column_widths[column_index + i].max += extra;
-            }
-        }
-        column_index += colspan;
-    });
+    float width_of_table_containing_block = m_state.get(*table_box.containing_block()).content_width();
+
+    // The row/column-grid width minimum (GRIDMIN) width is the sum of the min-content width
+    // of all the columns plus cell spacing or borders.
+    float grid_min = 0.0f;
+    for (auto& column : m_columns) {
+        grid_min += column.min_width;
+    }
+
+    // The row/column-grid width maximum (GRIDMAX) width is the sum of the max-content width
+    // of all the columns plus cell spacing or borders.
+    float grid_max = 0.0f;
+    for (auto& column : m_columns) {
+        grid_max += column.max_width;
+    }
+
+    // The used min-width of a table is the greater of the resolved min-width, CAPMIN, and GRIDMIN.
+    float used_min_width = grid_min;
+    if (!computed_values.min_width().is_auto()) {
+        used_min_width = max(used_min_width, computed_values.min_width().resolved(table_box, CSS::Length::make_px(width_of_table_containing_block)).to_px(table_box));
+    }
+
+    float used_width;
+    if (computed_values.width().is_auto()) {
+        // If the table-root has 'width: auto', the used width is the greater of
+        // min(GRIDMAX, the table’s containing block width), the used min-width of the table.
+        used_width = max(min(grid_max, width_of_table_containing_block), used_min_width);
+        table_box_state.set_content_width(used_width);
+    } else {
+        // If the table-root’s width property has a computed value (resolving to
+        // resolved-table-width) other than auto, the used width is the greater
+        // of resolved-table-width, and the used min-width of the table.
+        float resolved_table_width = computed_values.width().resolved(table_box, CSS::Length::make_px(width_of_table_containing_block)).to_px(table_box);
+        used_width = max(resolved_table_width, used_min_width);
+        table_box_state.set_content_width(used_width);
+    }
+
+    if (used_width > grid_min) {
+        extra_width = used_width - grid_min;
+    }
 }
 
-void TableFormattingContext::layout_row(Box const& row, Vector<ColumnWidth>& column_widths, AvailableSpace const& available_space)
+void TableFormattingContext::distribute_width_to_columns(float extra_width)
 {
-    auto& row_state = m_state.get_mutable(row);
-    size_t column_index = 0;
-    float tallest_cell_height = 0;
-    float content_width = 0;
-    auto* table = row.first_ancestor_of_type<TableBox>();
-    bool use_auto_layout = !table || table->computed_values().width().is_auto();
+    float grid_max = 0.0f;
+    for (auto& column : m_columns)
+        grid_max += column.max_width - column.min_width;
 
-    row.for_each_child_of_type<TableCellBox>([&](auto& cell) {
-        auto& cell_state = m_state.get_mutable(cell);
+    for (auto& column : m_columns)
+        column.used_width += ((column.max_width - column.min_width) / grid_max) * extra_width;
+}
+
+void TableFormattingContext::run(Box const& box, LayoutMode, AvailableSpace const& available_space)
+{
+    float total_content_height = 0;
+
+    // Determine the number of rows/columns the table requires.
+    calculate_row_column_grid(box);
+
+    // Compute the minimum width of each column.
+    compute_table_measures();
+
+    // Compute the width of the table.
+    float extra_width = 0;
+    compute_table_width(extra_width);
+
+    // Distribute the width of the table among columns.
+    distribute_width_to_columns(extra_width);
+
+    float left_column_offset = 0;
+    for (auto& column : m_columns) {
+        column.left_offset = left_column_offset;
+        left_column_offset += column.used_width;
+    }
+
+    for (auto& cell : m_cells) {
+        auto& cell_state = m_state.get_mutable(cell.box);
 
         float span_width = 0;
-        for (size_t i = 0; i < cell.colspan(); ++i)
-            span_width += column_widths[column_index++].used;
-        cell_state.set_content_width(span_width - cell_state.border_box_left() - cell_state.border_box_right());
+        for (size_t i = 0; i < cell.column_span; ++i)
+            span_width += m_columns[cell.column_index + i].used_width;
 
-        BlockFormattingContext::compute_height(cell, AvailableSpace(AvailableSize::make_indefinite(), AvailableSize::make_indefinite()));
-        cell_state.offset = row_state.offset.translated(cell_state.border_box_left() + content_width, cell_state.border_box_top());
+        auto width_of_containing_block = m_state.get(*cell.box.containing_block()).content_width();
+        auto width_of_containing_block_as_length = CSS::Length::make_px(width_of_containing_block);
 
-        // Layout the cell contents a second time, now that we know its final width.
-        if (auto independent_formatting_context = layout_inside(cell, LayoutMode::Normal, cell_state.available_inner_space_or_constraints_from(available_space)))
+        cell_state.padding_top = cell.box.computed_values().padding().top().resolved(cell.box, width_of_containing_block_as_length).to_px(cell.box);
+        cell_state.padding_bottom = cell.box.computed_values().padding().bottom().resolved(cell.box, width_of_containing_block_as_length).to_px(cell.box);
+        cell_state.padding_left = cell.box.computed_values().padding().left().resolved(cell.box, width_of_containing_block_as_length).to_px(cell.box);
+        cell_state.padding_right = cell.box.computed_values().padding().right().resolved(cell.box, width_of_containing_block_as_length).to_px(cell.box);
+        cell_state.border_top = cell.box.computed_values().border_top().width;
+        cell_state.border_bottom = cell.box.computed_values().border_bottom().width;
+        cell_state.border_left = cell.box.computed_values().border_left().width;
+        cell_state.border_right = cell.box.computed_values().border_right().width;
+
+        cell_state.set_content_width(span_width - cell_state.border_box_left() - cell_state.border_box_right());
+        if (auto independent_formatting_context = layout_inside(cell.box, LayoutMode::Normal, cell_state.available_inner_space_or_constraints_from(available_space)))
             independent_formatting_context->parent_context_did_dimension_child_root_box();
 
-        content_width += span_width;
-        tallest_cell_height = max(tallest_cell_height, cell_state.border_box_height());
-    });
+        BlockFormattingContext::compute_height(cell.box, AvailableSpace(AvailableSize::make_indefinite(), AvailableSize::make_indefinite()));
+
+        Row& row = m_rows[cell.row_index];
+        row.used_width = max(row.used_width, cell_state.border_box_height());
+    }
+
+    for (size_t y = 0; y < m_rows.size(); y++) {
+        auto& row = m_rows[y];
+        auto& row_state = m_state.get_mutable(row.box);
+        float row_width = 0.0f;
+        for (auto& column : m_columns) {
+            row_width += column.used_width;
+        }
+
+        row_state.set_content_height(row.used_width);
+        row_state.set_content_width(row_width);
+    }
+
+    float row_group_top_offset = 0.0f;
+    box.for_each_child_of_type<TableRowGroupBox>([&](auto& row_group_box) {
+        float row_group_height = 0.0f;
+        float row_group_width = 0.0f;
+
+        auto& row_group_box_state = m_state.get_mutable(row_group_box);
+        row_group_box_state.set_content_y(row_group_top_offset);
+
+        float row_top_offset = 0.0f;
+        row_group_box.template for_each_child_of_type<TableRowBox>([&](auto& row) {
+            auto& row_state = m_state.get_mutable(row);
+            row_state.set_content_y(row_top_offset);
+            row_group_height += row_state.border_box_height();
+            row_group_width = max(row_group_width, row_state.border_box_width());
+            row_top_offset += row_state.border_box_height();
+        });
 
-    row_state.set_content_height(tallest_cell_height);
+        row_group_top_offset += row_top_offset;
 
-    row.for_each_child_of_type<TableCellBox>([&](auto& cell) {
-        auto& cell_state = m_state.get_mutable(cell);
-        cell_state.set_content_height(tallest_cell_height - cell_state.border_box_top() - cell_state.border_box_bottom());
+        row_group_box_state.set_content_height(row_group_height);
+        row_group_box_state.set_content_width(row_group_width);
     });
 
-    if (use_auto_layout) {
-        row_state.set_content_width(content_width);
-    } else {
-        auto& table_state = m_state.get_mutable(*table);
-        row_state.set_content_width(table_state.content_width());
+    for (auto& cell : m_cells) {
+        auto& cell_state = m_state.get_mutable(cell.box);
+        auto& row_state = m_state.get(m_rows[cell.row_index].box);
+        cell_state.set_content_height(row_state.content_height() - cell_state.border_box_top() - cell_state.border_box_bottom());
+        cell_state.offset = row_state.offset.translated(cell_state.border_box_left() + m_columns[cell.column_index].left_offset, cell_state.border_box_top());
     }
+
+    m_state.get_mutable(context_box()).set_content_height(total_content_height);
+
+    // FIXME: This is a total hack, we should respect the 'height' property.
+    m_automatic_content_height = total_content_height;
 }
 
 float TableFormattingContext::automatic_content_height() const
diff --git a/Userland/Libraries/LibWeb/Layout/TableFormattingContext.h b/Userland/Libraries/LibWeb/Layout/TableFormattingContext.h
index 9f4d56d5ba..4df2ac97ad 100644
--- a/Userland/Libraries/LibWeb/Layout/TableFormattingContext.h
+++ b/Userland/Libraries/LibWeb/Layout/TableFormattingContext.h
@@ -11,13 +11,6 @@
 
 namespace Web::Layout {
 
-struct ColumnWidth {
-    float min { 0 };
-    float max { 0 };
-    float used { 0 };
-    bool is_auto { true };
-};
-
 class TableFormattingContext final : public BlockFormattingContext {
 public:
     explicit TableFormattingContext(LayoutState&, BlockContainer const&, FormattingContext* parent);
@@ -27,10 +20,37 @@ public:
     virtual float automatic_content_height() const override;
 
 private:
-    void calculate_column_widths(Box const& row, CSS::Length const& table_width, Vector<ColumnWidth>& column_widths, AvailableSpace const&);
-    void layout_row(Box const& row, Vector<ColumnWidth>& column_widths, AvailableSpace const&);
+    void calculate_row_column_grid(Box const&);
+    void compute_table_measures();
+    void compute_table_width(float&);
+    void distribute_width_to_columns(float extra_width);
+    void determine_intrisic_size_of_table_container(AvailableSpace const& available_space);
 
     float m_automatic_content_height { 0 };
+
+    struct Column {
+        float left_offset { 0 };
+        float min_width { 0 };
+        float max_width { 0 };
+        float used_width { 0 };
+    };
+
+    struct Row {
+        Box& box;
+        float used_width { 0 };
+    };
+
+    struct Cell {
+        Box& box;
+        size_t column_index;
+        size_t row_index;
+        size_t column_span;
+        size_t raw_span;
+    };
+
+    Vector<Cell> m_cells;
+    Vector<Column> m_columns;
+    Vector<Row> m_rows;
 };
 
 }
diff --git a/Userland/Libraries/LibWeb/Layout/TableRowGroupBox.cpp b/Userland/Libraries/LibWeb/Layout/TableRowGroupBox.cpp
index 2a5c45d036..8f1d2018c3 100644
--- a/Userland/Libraries/LibWeb/Layout/TableRowGroupBox.cpp
+++ b/Userland/Libraries/LibWeb/Layout/TableRowGroupBox.cpp
@@ -18,17 +18,4 @@ TableRowGroupBox::TableRowGroupBox(DOM::Document& document, DOM::Element* elemen
 
 TableRowGroupBox::~TableRowGroupBox() = default;
 
-size_t TableRowGroupBox::column_count() const
-{
-    size_t table_column_count = 0;
-    for_each_child_of_type<TableRowBox>([&](auto& row) {
-        size_t row_column_count = 0;
-        row.template for_each_child_of_type<TableCellBox>([&](auto& cell) {
-            row_column_count += cell.colspan();
-        });
-        table_column_count = max(table_column_count, row_column_count);
-    });
-    return table_column_count;
-}
-
 }
diff --git a/Userland/Libraries/LibWeb/Layout/TableRowGroupBox.h b/Userland/Libraries/LibWeb/Layout/TableRowGroupBox.h
index 923c662f47..46442606da 100644
--- a/Userland/Libraries/LibWeb/Layout/TableRowGroupBox.h
+++ b/Userland/Libraries/LibWeb/Layout/TableRowGroupBox.h
@@ -16,8 +16,6 @@ class TableRowGroupBox final : public BlockContainer {
 public:
     TableRowGroupBox(DOM::Document&, DOM::Element*, NonnullRefPtr<CSS::StyleProperties>);
     virtual ~TableRowGroupBox() override;
-
-    size_t column_count() const;
 };
 
 }