Add initial support for table box tree construction (#30799)

This is the first part of constructing the box tree for table layout. No
layout is actually done and the construction of tables is now hidden
behind a flag (in order to not regress WPT).  Notably, this does not
handle anonymous table part construction, when the DOM does not reflect
a fully-formed table. That's part two.

Progress toward #27459.

Co-authored-by: Oriol Brufau <obrufau@igalia.com>
Co-authored-by: Manish Goregaokar <manishsmail@gmail.com>

10 files changed, 915 insertions, 18 deletions

diff --git a/components/layout_2020/flexbox/construct.rs b/components/layout_2020/flexbox/construct.rs
index cc2abc6630c..04f8f0746b4 100644
--- a/components/layout_2020/flexbox/construct.rs
+++ b/components/layout_2020/flexbox/construct.rs
@@ -165,6 +165,7 @@ where
                 } => {
                     let display_inside = match display {
                         DisplayGeneratingBox::OutsideInside { inside, .. } => inside,
+                        DisplayGeneratingBox::LayoutInternal(_) => display.display_inside(),
                     };
                     let box_ = if info.style.get_box().position.is_absolutely_positioned() {
                         // https://drafts.csswg.org/css-flexbox/#abspos-items
diff --git a/components/layout_2020/flow/construct.rs b/components/layout_2020/flow/construct.rs
index e2ef5c2aa52..9fb5cb2509b 100644
--- a/components/layout_2020/flow/construct.rs
+++ b/components/layout_2020/flow/construct.rs
@@ -273,6 +273,9 @@ where
                     }
                 },
             },
+            DisplayGeneratingBox::LayoutInternal(_) => {
+                unreachable!("The result of blockification should never be layout-internal value.");
+            },
         }
     }
 
diff --git a/components/layout_2020/flow/inline.rs b/components/layout_2020/flow/inline.rs
index 83856afa7c7..e247c1d37ee 100644
--- a/components/layout_2020/flow/inline.rs
+++ b/components/layout_2020/flow/inline.rs
@@ -2248,6 +2248,11 @@ impl AbsolutelyPositionedLineItem {
                     block: Length::zero(),
                 }
             },
+            Display::GeneratingBox(DisplayGeneratingBox::LayoutInternal(_)) => {
+                unreachable!(
+                    "The result of blockification should never be a layout-internal value."
+                );
+            },
             Display::Contents => {
                 panic!("display:contents does not generate an abspos box")
             },
diff --git a/components/layout_2020/flow/root.rs b/components/layout_2020/flow/root.rs
index 8cd0225ee15..6423aebc096 100644
--- a/components/layout_2020/flow/root.rs
+++ b/components/layout_2020/flow/root.rs
@@ -225,7 +225,7 @@ fn construct_for_root_element<'dom>(
             unreachable!()
         },
         // The root element is blockified, ignore DisplayOutside
-        Display::GeneratingBox(DisplayGeneratingBox::OutsideInside { inside, .. }) => inside,
+        Display::GeneratingBox(display_generating_box) => display_generating_box.display_inside(),
     };
 
     let contents =
diff --git a/components/layout_2020/formatting_contexts.rs b/components/layout_2020/formatting_contexts.rs
index d13ea240251..94ab0e089d1 100644
--- a/components/layout_2020/formatting_contexts.rs
+++ b/components/layout_2020/formatting_contexts.rs
@@ -21,6 +21,7 @@ use crate::positioned::PositioningContext;
 use crate::replaced::ReplacedContent;
 use crate::sizing::{self, ContentSizes};
 use crate::style_ext::DisplayInside;
+use crate::table::Table;
 use crate::ContainingBlock;
 
 /// https://drafts.csswg.org/css-display/#independent-formatting-context
@@ -54,6 +55,7 @@ pub(crate) struct ReplacedFormattingContext {
 pub(crate) enum NonReplacedFormattingContextContents {
     Flow(BlockFormattingContext),
     Flex(FlexContainer),
+    Table(Table),
     // Other layout modes go here
 }
 
@@ -73,7 +75,7 @@ impl IndependentFormattingContext {
         propagated_text_decoration_line: TextDecorationLine,
     ) -> Self {
         match contents.try_into() {
-            Ok(non_replaced) => {
+            Ok(non_replaced_contents) => {
                 let contents = match display_inside {
                     DisplayInside::Flow { is_list_item } |
                     DisplayInside::FlowRoot { is_list_item } => {
@@ -81,7 +83,7 @@ impl IndependentFormattingContext {
                             BlockFormattingContext::construct(
                                 context,
                                 node_and_style_info,
-                                non_replaced,
+                                non_replaced_contents,
                                 propagated_text_decoration_line,
                                 is_list_item,
                             ),
@@ -91,7 +93,15 @@ impl IndependentFormattingContext {
                         NonReplacedFormattingContextContents::Flex(FlexContainer::construct(
                             context,
                             node_and_style_info,
-                            non_replaced,
+                            non_replaced_contents,
+                            propagated_text_decoration_line,
+                        ))
+                    },
+                    DisplayInside::Table => {
+                        NonReplacedFormattingContextContents::Table(Table::construct(
+                            context,
+                            node_and_style_info,
+                            non_replaced_contents,
                             propagated_text_decoration_line,
                         ))
                     },
@@ -190,6 +200,9 @@ impl NonReplacedFormattingContext {
             NonReplacedFormattingContextContents::Flex(fc) => {
                 fc.layout(layout_context, positioning_context, containing_block)
             },
+            NonReplacedFormattingContextContents::Table(table) => {
+                table.layout(layout_context, positioning_context, containing_block)
+            },
         }
     }
 
@@ -213,6 +226,7 @@ impl NonReplacedFormattingContextContents {
                 .contents
                 .inline_content_sizes(layout_context, writing_mode),
             Self::Flex(inner) => inner.inline_content_sizes(),
+            Self::Table(table) => table.inline_content_sizes(),
         }
     }
 }
diff --git a/components/layout_2020/lib.rs b/components/layout_2020/lib.rs
index 50294c3ad1c..6d2fdcb0375 100644
--- a/components/layout_2020/lib.rs
+++ b/components/layout_2020/lib.rs
@@ -23,6 +23,7 @@ pub mod query;
 mod replaced;
 mod sizing;
 mod style_ext;
+pub mod table;
 pub mod traversal;
 
 pub use flow::BoxTree;
diff --git a/components/layout_2020/style_ext.rs b/components/layout_2020/style_ext.rs
index 0f8d4d245ad..f615ec13ac9 100644
--- a/components/layout_2020/style_ext.rs
+++ b/components/layout_2020/style_ext.rs
@@ -2,6 +2,7 @@
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
 
+use servo_config::pref;
 use style::computed_values::mix_blend_mode::T as ComputedMixBlendMode;
 use style::computed_values::position::T as ComputedPosition;
 use style::computed_values::transform_style::T as ComputedTransformStyle;
@@ -36,8 +37,19 @@ pub(crate) enum DisplayGeneratingBox {
         outside: DisplayOutside,
         inside: DisplayInside,
     },
-    // Layout-internal display types go here:
     // https://drafts.csswg.org/css-display-3/#layout-specific-display
+    LayoutInternal(DisplayLayoutInternal),
+}
+
+impl DisplayGeneratingBox {
+    pub(crate) fn display_inside(&self) -> DisplayInside {
+        match *self {
+            DisplayGeneratingBox::OutsideInside { inside, .. } => inside,
+            DisplayGeneratingBox::LayoutInternal(layout_internal) => {
+                layout_internal.display_inside()
+            },
+        }
+    }
 }
 
 #[derive(Clone, Copy, Eq, PartialEq)]
@@ -53,6 +65,32 @@ pub(crate) enum DisplayInside {
     Flow { is_list_item: bool },
     FlowRoot { is_list_item: bool },
     Flex,
+    Table,
+}
+
+#[derive(Clone, Copy, Debug, Eq, PartialEq)]
+/// https://drafts.csswg.org/css-display-3/#layout-specific-display
+pub(crate) enum DisplayLayoutInternal {
+    TableCaption,
+    TableCell,
+    TableColumn,
+    TableColumnGroup,
+    TableFooterGroup,
+    TableHeaderGroup,
+    TableRow,
+    TableRowGroup,
+}
+
+impl DisplayLayoutInternal {
+    /// https://drafts.csswg.org/css-display-3/#layout-specific-displa
+    pub(crate) fn display_inside(&self) -> DisplayInside {
+        // When we add ruby, the display_inside of ruby must be Flow.
+        // TODO: this should be unreachable for everything but
+        // table cell and caption, once we have box tree fixups.
+        DisplayInside::FlowRoot {
+            is_list_item: false,
+        }
+    }
 }
 
 /// Percentages resolved but not `auto` margins
@@ -492,6 +530,46 @@ impl ComputedValuesExt for ComputedValues {
 
 impl From<stylo::Display> for Display {
     fn from(packed: stylo::Display) -> Self {
+        let outside = packed.outside();
+        let inside = packed.inside();
+
+        let outside = match outside {
+            stylo::DisplayOutside::Block => DisplayOutside::Block,
+            stylo::DisplayOutside::Inline => DisplayOutside::Inline,
+            stylo::DisplayOutside::TableCaption if pref!(layout.tables.enabled) => {
+                return Display::GeneratingBox(DisplayGeneratingBox::LayoutInternal(
+                    DisplayLayoutInternal::TableCaption,
+                ));
+            },
+            stylo::DisplayOutside::TableCaption => DisplayOutside::Block,
+            stylo::DisplayOutside::InternalTable if pref!(layout.tables.enabled) => {
+                let internal = match inside {
+                    stylo::DisplayInside::TableRowGroup => DisplayLayoutInternal::TableRowGroup,
+                    stylo::DisplayInside::TableColumn => DisplayLayoutInternal::TableColumn,
+                    stylo::DisplayInside::TableColumnGroup => {
+                        DisplayLayoutInternal::TableColumnGroup
+                    },
+                    stylo::DisplayInside::TableHeaderGroup => {
+                        DisplayLayoutInternal::TableHeaderGroup
+                    },
+                    stylo::DisplayInside::TableFooterGroup => {
+                        DisplayLayoutInternal::TableFooterGroup
+                    },
+                    stylo::DisplayInside::TableRow => DisplayLayoutInternal::TableRow,
+                    stylo::DisplayInside::TableCell => DisplayLayoutInternal::TableCell,
+                    _ => unreachable!("Non-internal DisplayInside found"),
+                };
+                return Display::GeneratingBox(DisplayGeneratingBox::LayoutInternal(internal));
+            },
+            stylo::DisplayOutside::InternalTable => DisplayOutside::Block,
+            // This should not be a value of DisplayInside, but oh well
+            // special-case display: contents because we still want it to work despite the early return
+            stylo::DisplayOutside::None if inside == stylo::DisplayInside::Contents => {
+                return Display::Contents
+            },
+            stylo::DisplayOutside::None => return Display::None,
+        };
+
         let inside = match packed.inside() {
             stylo::DisplayInside::Flow => DisplayInside::Flow {
                 is_list_item: packed.is_list_item(),
@@ -505,7 +583,7 @@ impl From<stylo::Display> for Display {
             stylo::DisplayInside::None => return Display::None,
             stylo::DisplayInside::Contents => return Display::Contents,
 
-            // TODO: Implement support for tables.
+            stylo::DisplayInside::Table if pref!(layout.tables.enabled) => DisplayInside::Table,
             stylo::DisplayInside::Table |
             stylo::DisplayInside::TableRowGroup |
             stylo::DisplayInside::TableColumn |
@@ -517,18 +595,6 @@ impl From<stylo::Display> for Display {
                 is_list_item: packed.is_list_item(),
             },
         };
-        let outside = match packed.outside() {
-            stylo::DisplayOutside::Block => DisplayOutside::Block,
-            stylo::DisplayOutside::Inline => DisplayOutside::Inline,
-
-            // This should not be a value of DisplayInside, but oh well
-            stylo::DisplayOutside::None => return Display::None,
-
-            // TODO: Implement support for tables.
-            stylo::DisplayOutside::TableCaption | stylo::DisplayOutside::InternalTable => {
-                DisplayOutside::Block
-            },
-        };
         Display::GeneratingBox(DisplayGeneratingBox::OutsideInside { outside, inside })
     }
 }
diff --git a/components/layout_2020/table/construct.rs b/components/layout_2020/table/construct.rs
new file mode 100644
index 00000000000..40bec8188de
--- /dev/null
+++ b/components/layout_2020/table/construct.rs
@@ -0,0 +1,439 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
+
+use std::borrow::Cow;
+use std::convert::{TryFrom, TryInto};
+
+use log::warn;
+use script_layout_interface::wrapper_traits::ThreadSafeLayoutNode;
+use style::values::specified::TextDecorationLine;
+
+use super::{Table, TableSlot, TableSlotCell, TableSlotCoordinates, TableSlotOffset};
+use crate::context::LayoutContext;
+use crate::dom::{BoxSlot, NodeExt};
+use crate::dom_traversal::{Contents, NodeAndStyleInfo, NonReplacedContents, TraversalHandler};
+use crate::flow::BlockFormattingContext;
+use crate::style_ext::{DisplayGeneratingBox, DisplayLayoutInternal};
+
+/// A reference to a slot and its coordinates in the table
+#[derive(Clone, Copy, Debug)]
+struct ResolvedSlotAndLocation<'a> {
+    cell: &'a TableSlotCell,
+    coords: TableSlotCoordinates,
+}
+
+impl<'a> ResolvedSlotAndLocation<'a> {
+    fn covers_cell_at(&self, coords: TableSlotCoordinates) -> bool {
+        let covered_in_x =
+            coords.x >= self.coords.x && coords.x < self.coords.x + self.cell.colspan;
+        let covered_in_y = coords.y >= self.coords.y &&
+            (self.cell.rowspan == 0 || coords.y < self.coords.y + self.cell.rowspan);
+        covered_in_x && covered_in_y
+    }
+}
+
+impl Table {
+    pub(crate) fn construct<'dom>(
+        context: &LayoutContext,
+        info: &NodeAndStyleInfo<impl NodeExt<'dom>>,
+        contents: NonReplacedContents,
+        propagated_text_decoration_line: TextDecorationLine,
+    ) -> Self {
+        let mut traversal = TableBuilderTraversal {
+            context,
+            _info: info,
+            propagated_text_decoration_line,
+            builder: Default::default(),
+        };
+        contents.traverse(context, info, &mut traversal);
+        traversal.builder.finish()
+    }
+
+    /// Push a new slot into the last row of this table.
+    fn push_new_slot_to_last_row(&mut self, slot: TableSlot) {
+        self.slots.last_mut().expect("Should have rows").push(slot)
+    }
+
+    /// Convenience method for get() that returns a SlotAndLocation
+    fn get_slot<'a>(&'a self, coords: TableSlotCoordinates) -> Option<&'a TableSlot> {
+        self.slots.get(coords.y)?.get(coords.x)
+    }
+
+    /// Find [`ResolvedSlotAndLocation`] of all the slots that cover the slot at the given
+    /// coordinates. This recursively resolves all of the [`TableSlotCell`]s that cover
+    /// the target and returns a [`ResolvedSlotAndLocation`] for each of them. If there is
+    /// no slot at the given coordinates or that slot is an empty space, an empty vector
+    /// is returned.
+    fn resolve_slot_at<'a>(
+        &'a self,
+        coords: TableSlotCoordinates,
+    ) -> Vec<ResolvedSlotAndLocation<'a>> {
+        let slot = self.get_slot(coords);
+        match slot {
+            Some(TableSlot::Cell(cell)) => vec![ResolvedSlotAndLocation {
+                cell: &cell,
+                coords,
+            }],
+            Some(TableSlot::Spanned(ref offsets)) => offsets
+                .iter()
+                .map(|offset| self.resolve_slot_at(coords - *offset))
+                .flatten()
+                .collect(),
+            Some(TableSlot::Empty) | None => {
+                warn!("Tried to resolve an empty or nonexistant slot!");
+                vec![]
+            },
+        }
+    }
+
+    /// Create a [`TableSlot::Spanned`] for the target cell at the given coordinates. If
+    /// no slots cover the target, then this returns [`None`]. Note: This does not handle
+    /// slots that cover the target using `colspan`, but instead only considers slots that
+    /// cover this slot via `rowspan`. `colspan` should be handled by appending to the
+    /// return value of this function.
+    fn create_spanned_slot_based_on_cell_above(
+        &self,
+        target_coords: TableSlotCoordinates,
+    ) -> Option<TableSlot> {
+        let coords_for_slot_above =
+            TableSlotCoordinates::new(target_coords.x, self.slots.len() - 2);
+        let slots_covering_slot_above = self.resolve_slot_at(coords_for_slot_above);
+
+        let coords_of_slots_that_cover_target: Vec<_> = slots_covering_slot_above
+            .into_iter()
+            .filter(|ref slot| slot.covers_cell_at(target_coords))
+            .map(|slot| target_coords - slot.coords)
+            .collect();
+
+        if coords_of_slots_that_cover_target.is_empty() {
+            return None;
+        } else {
+            Some(TableSlot::Spanned(coords_of_slots_that_cover_target))
+        }
+    }
+}
+
+impl TableSlot {
+    /// Merge a TableSlot::Spanned(x, y) with this (only for model errors)
+    pub fn push_spanned(&mut self, new_offset: TableSlotOffset) {
+        match *self {
+            TableSlot::Cell { .. } => {
+                panic!("Should never have a table model error with an originating cell slot overlapping a spanned slot")
+            },
+            TableSlot::Spanned(ref mut vec) => vec.insert(0, new_offset),
+            TableSlot::Empty => {
+                panic!("Should never have a table model error with an empty slot");
+            },
+        }
+    }
+}
+
+#[derive(Default)]
+pub struct TableBuilder {
+    /// The table that we are building.
+    table: Table,
+
+    /// An incoming rowspan is a value indicating that a cell in a row above the current row,
+    /// had a rowspan value other than 1. The values in this array indicate how many more
+    /// rows the cell should span. For example, a value of 0 at an index before `current_x()`
+    /// indicates that the cell on that column will not span into the next row, and at an index
+    /// after `current_x()` it indicates that the cell will not span into the current row.
+    /// A negative value means that the cell will span all remaining rows in the row group.
+    ///
+    /// As each column in a row is processed, the values in this vector are updated for the
+    /// next row.
+    pub incoming_rowspans: Vec<isize>,
+}
+
+impl TableBuilder {
+    pub fn finish(self) -> Table {
+        self.table
+    }
+
+    fn current_y(&self) -> usize {
+        self.table.slots.len() - 1
+    }
+
+    fn current_x(&self) -> usize {
+        self.table.slots[self.current_y()].len()
+    }
+
+    fn current_coords(&self) -> TableSlotCoordinates {
+        TableSlotCoordinates::new(self.current_x(), self.current_y())
+    }
+
+    pub fn start_row<'builder>(&'builder mut self) {
+        self.table.slots.push(Vec::new());
+        self.create_slots_for_cells_above_with_rowspan(true);
+    }
+
+    pub fn end_row(&mut self) {
+        // TODO: We need to insert a cell for any leftover non-table-like
+        // content in the TableRowBuilder.
+
+        // Truncate entries that are zero at the end of [`Self::incoming_rowspans`]. This
+        // prevents padding the table with empty cells when it isn't necessary.
+        let current_x = self.current_x();
+        for i in (current_x..self.incoming_rowspans.len()).rev() {
+            if self.incoming_rowspans[i] == 0 {
+                self.incoming_rowspans.pop();
+            } else {
+                break;
+            }
+        }
+
+        self.create_slots_for_cells_above_with_rowspan(false);
+    }
+
+    /// When not in the process of filling a cell, make sure any incoming rowspans are
+    /// filled so that the next specified cell comes after them. Should have been called before
+    /// [`Self::handle_cell`].
+    ///
+    /// if `stop_at_cell_opportunity` is set, this will stop at the first slot with
+    /// `incoming_rowspans` equal to zero. If not, it will insert [`TableSlot::Empty`] and
+    /// continue to look for more incoming rowspans (which should only be done once we're
+    /// finished processing the cells in a row, and after calling truncating cells with
+    /// remaining rowspan from the end of `incoming_rowspans`.
+    fn create_slots_for_cells_above_with_rowspan(&mut self, stop_at_cell_opportunity: bool) {
+        let mut current_x = self.current_x();
+        while let Some(span) = self.incoming_rowspans.get_mut(current_x) {
+            // This column has no incoming rowspanned cells and `stop_at_zero` is true, so
+            // we should stop to process new cells defined in the current row.
+            if *span == 0 && stop_at_cell_opportunity {
+                break;
+            }
+
+            let new_cell = if *span != 0 {
+                *span -= 1;
+                self.table
+                    .create_spanned_slot_based_on_cell_above(self.current_coords())
+                    .expect(
+                        "Nonzero incoming rowspan cannot occur without a cell spanning this slot",
+                    )
+            } else {
+                TableSlot::Empty
+            };
+
+            self.table.push_new_slot_to_last_row(new_cell);
+            current_x = self.current_x();
+        }
+    }
+
+    /// https://html.spec.whatwg.org/multipage/#algorithm-for-processing-rows
+    /// Push a single cell onto the slot map, handling any colspans it may have, and
+    /// setting up the outgoing rowspans.
+    pub fn add_cell(&mut self, cell: TableSlotCell) {
+        // Make sure the incoming_rowspans table is large enough
+        // because we will be writing to it.
+        let current_x = self.current_x();
+        let colspan = cell.colspan;
+        let rowspan = cell.rowspan;
+
+        if self.incoming_rowspans.len() < current_x + colspan {
+            self.incoming_rowspans.resize(current_x + colspan, 0isize);
+        }
+
+        debug_assert_eq!(
+            self.incoming_rowspans[current_x], 0,
+            "Added a cell in a position that also had an incoming rowspan!"
+        );
+
+        // If `rowspan` is zero, this is automatically negative and will stay negative.
+        let outgoing_rowspan = rowspan as isize - 1;
+        self.table.push_new_slot_to_last_row(TableSlot::Cell(cell));
+        self.incoming_rowspans[current_x] = outgoing_rowspan;
+
+        // Draw colspanned cells
+        for colspan_offset in 1..colspan {
+            let current_x_plus_colspan_offset = current_x + colspan_offset;
+            let new_offset = TableSlotOffset::new(colspan_offset, 0);
+            let incoming_rowspan = &mut self.incoming_rowspans[current_x_plus_colspan_offset];
+            let new_slot = if *incoming_rowspan == 0 {
+                *incoming_rowspan = outgoing_rowspan;
+                TableSlot::new_spanned(new_offset)
+            } else {
+                // This means we have a table model error.
+
+                // if `incoming_rowspan` is greater than zero, a cell from above is spanning
+                // into our row, colliding with the cells we are creating via colspan. In
+                // that case, set the incoming rowspan to the highest of two possible
+                // outgoing rowspan values (the incoming rowspan minus one, OR this cell's
+                // outgoing rowspan).  `spanned_slot()`` will handle filtering out
+                // inapplicable spans when it needs to.
+                //
+                // If the `incoming_rowspan` is negative we are in `rowspan=0` mode, (i.e.
+                // rowspan=infinity), so we don't have to worry about the current cell
+                // making it larger. In that case, don't change the rowspan.
+                if *incoming_rowspan > 0 {
+                    *incoming_rowspan = std::cmp::max(*incoming_rowspan - 1, outgoing_rowspan);
+                }
+
+                // This code creates a new slot in the case that there is a table model error.
+                let coords_of_spanned_cell =
+                    TableSlotCoordinates::new(current_x_plus_colspan_offset, self.current_y());
+                match self
+                    .table
+                    .create_spanned_slot_based_on_cell_above(coords_of_spanned_cell)
+                {
+                    Some(mut incoming_slot) => {
+                        incoming_slot.push_spanned(new_offset);
+                        incoming_slot
+                    },
+                    None => TableSlot::new_spanned(new_offset),
+                }
+            };
+            self.table.push_new_slot_to_last_row(new_slot);
+        }
+
+        debug_assert_eq!(
+            current_x + colspan,
+            self.current_x(),
+            "Must have produced `colspan` slot entries!"
+        );
+        self.create_slots_for_cells_above_with_rowspan(true);
+    }
+}
+
+struct TableBuilderTraversal<'a, Node> {
+    context: &'a LayoutContext<'a>,
+    _info: &'a NodeAndStyleInfo<Node>,
+
+    /// Propagated value for text-decoration-line, used to construct the block
+    /// contents of table cells.
+    propagated_text_decoration_line: TextDecorationLine,
+
+    /// The [`TableBuilder`] for this [`TableBuilderTraversal`]. This is separated
+    /// into another struct so that we can write unit tests against the builder.
+    builder: TableBuilder,
+}
+
+impl<'a, 'dom, Node: 'dom> TraversalHandler<'dom, Node> for TableBuilderTraversal<'a, Node>
+where
+    Node: NodeExt<'dom>,
+{
+    fn handle_text(&mut self, _info: &NodeAndStyleInfo<Node>, _text: Cow<'dom, str>) {
+        // TODO: We should collect these contents into a new table cell.
+    }
+
+    /// https://html.spec.whatwg.org/multipage/#forming-a-table
+    fn handle_element(
+        &mut self,
+        info: &NodeAndStyleInfo<Node>,
+        display: DisplayGeneratingBox,
+        contents: Contents,
+        box_slot: BoxSlot<'dom>,
+    ) {
+        match display {
+            DisplayGeneratingBox::LayoutInternal(internal) => match internal {
+                DisplayLayoutInternal::TableRowGroup => {
+                    // TODO: Should we fixup `rowspan=0` to the actual resolved value and
+                    // any other rowspans that have been cut short?
+                    self.builder.incoming_rowspans.clear();
+                    NonReplacedContents::try_from(contents).unwrap().traverse(
+                        self.context,
+                        info,
+                        self,
+                    );
+
+                    // TODO: Handle style for row groups here.
+                },
+                DisplayLayoutInternal::TableRow => {
+                    self.builder.start_row();
+                    NonReplacedContents::try_from(contents).unwrap().traverse(
+                        self.context,
+                        info,
+                        &mut TableRowBuilder::new(self),
+                    );
+                    self.builder.end_row();
+                },
+                _ => {
+                    // TODO: Handle other types of unparented table content, colgroups, and captions.
+                },
+            },
+            _ => {
+                // TODO: Create an anonymous row and cell for other unwrapped content.
+            },
+        }
+
+        // We are doing this until we have actually set a Box for this `BoxSlot`.
+        ::std::mem::forget(box_slot)
+    }
+}
+
+struct TableRowBuilder<'a, 'builder, Node> {
+    table_traversal: &'builder mut TableBuilderTraversal<'a, Node>,
+}
+
+impl<'a, 'builder, Node> TableRowBuilder<'a, 'builder, Node> {
+    fn new(table_traversal: &'builder mut TableBuilderTraversal<'a, Node>) -> Self {
+        TableRowBuilder { table_traversal }
+    }
+}
+
+impl<'a, 'builder, 'dom, Node: 'dom> TraversalHandler<'dom, Node>
+    for TableRowBuilder<'a, 'builder, Node>
+where
+    Node: NodeExt<'dom>,
+{
+    fn handle_text(&mut self, _info: &NodeAndStyleInfo<Node>, _text: Cow<'dom, str>) {
+        // TODO: We should collect these contents into a new table cell.
+    }
+
+    /// https://html.spec.whatwg.org/multipage/#algorithm-for-processing-rows
+    fn handle_element(
+        &mut self,
+        info: &NodeAndStyleInfo<Node>,
+        display: DisplayGeneratingBox,
+        contents: Contents,
+        box_slot: BoxSlot<'dom>,
+    ) {
+        match display {
+            DisplayGeneratingBox::LayoutInternal(internal) => match internal {
+                DisplayLayoutInternal::TableCell => {
+                    // This value will already have filtered out rowspan=0
+                    // in quirks mode, so we don't have to worry about that.
+                    //
+                    // The HTML specification limits the parsed value of `rowspan` to
+                    // 65534 and `colspan` to 1000, so we also enforce the same limits
+                    // when dealing with arbitrary DOM elements (perhaps created via
+                    // script).
+                    let node = info.node.to_threadsafe();
+                    let rowspan = std::cmp::min(node.get_rowspan() as usize, 65534);
+                    let colspan = std::cmp::min(node.get_colspan() as usize, 1000);
+
+                    let contents = match contents.try_into() {
+                        Ok(non_replaced_contents) => {
+                            BlockFormattingContext::construct(
+                                self.table_traversal.context,
+                                info,
+                                non_replaced_contents,
+                                self.table_traversal.propagated_text_decoration_line,
+                                false, /* is_list_item */
+                            )
+                        },
+                        Err(_replaced) => {
+                            panic!("We don't handle this yet.");
+                        },
+                    };
+
+                    self.table_traversal.builder.add_cell(TableSlotCell {
+                        contents,
+                        colspan,
+                        rowspan,
+                        id: 0, // This is just an id used for testing purposes.
+                    });
+                },
+                _ => {
+                    // TODO: Properly handle other table-like elements in the middle of a row.
+                },
+            },
+            _ => {
+                // TODO: We should collect these contents into a new table cell.
+            },
+        }
+
+        // We are doing this until we have actually set a Box for this `BoxSlot`.
+        ::std::mem::forget(box_slot)
+    }
+}
diff --git a/components/layout_2020/table/mod.rs b/components/layout_2020/table/mod.rs
new file mode 100644
index 00000000000..a228ccc6907
--- /dev/null
+++ b/components/layout_2020/table/mod.rs
@@ -0,0 +1,117 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
+
+//! Table layout.
+//! See https://html.spec.whatwg.org/multipage/table-processing-model.
+
+mod construct;
+
+pub use construct::TableBuilder;
+use euclid::{Point2D, UnknownUnit, Vector2D};
+use serde::Serialize;
+use style::values::computed::Length;
+
+use super::flow::BlockFormattingContext;
+use crate::context::LayoutContext;
+use crate::flow::BlockContainer;
+use crate::formatting_contexts::IndependentLayout;
+use crate::positioned::PositioningContext;
+use crate::sizing::ContentSizes;
+use crate::ContainingBlock;
+
+#[derive(Debug, Default, Serialize)]
+pub struct Table {
+    pub slots: Vec<Vec<TableSlot>>,
+}
+
+impl Table {
+    pub(crate) fn inline_content_sizes(&self) -> ContentSizes {
+        ContentSizes::zero()
+    }
+
+    pub(crate) fn layout(
+        &self,
+        _layout_context: &LayoutContext,
+        _positioning_context: &mut PositioningContext,
+        _containing_block: &ContainingBlock,
+    ) -> IndependentLayout {
+        IndependentLayout {
+            fragments: Vec::new(),
+            content_block_size: Length::new(0.),
+        }
+    }
+}
+
+type TableSlotCoordinates = Point2D<usize, UnknownUnit>;
+pub type TableSlotOffset = Vector2D<usize, UnknownUnit>;
+
+#[derive(Debug, Serialize)]
+pub struct TableSlotCell {
+    /// The contents of this cell, with its own layout.
+    contents: BlockFormattingContext,
+
+    /// Number of columns that the cell is to span. Must be greater than zero.
+    colspan: usize,
+
+    /// Number of rows that the cell is to span. Zero means that the cell is to span all
+    /// the remaining rows in the row group.
+    rowspan: usize,
+
+    // An id used for testing purposes.
+    pub id: u8,
+}
+
+impl TableSlotCell {
+    pub fn mock_for_testing(id: u8, colspan: usize, rowspan: usize) -> Self {
+        Self {
+            contents: BlockFormattingContext {
+                contents: BlockContainer::BlockLevelBoxes(Vec::new()),
+                contains_floats: false,
+            },
+            colspan,
+            rowspan,
+            id,
+        }
+    }
+}
+
+#[derive(Serialize)]
+/// A single table slot. It may be an actual cell, or a reference
+/// to a previous cell that is spanned here
+///
+/// In case of table model errors, it may be multiple references
+pub enum TableSlot {
+    /// A table cell, with a colspan and a rowspan.
+    Cell(TableSlotCell),
+
+    /// This slot is spanned by one or more multiple cells earlier in the table, which are
+    /// found at the given negative coordinate offsets. The vector is in the order of most
+    /// recent to earliest cell.
+    ///
+    /// If there is more than one cell that spans a slot, this is a table model error, but
+    /// we still keep track of it. See
+    /// https://html.spec.whatwg.org/multipage/#table-model-error
+    Spanned(Vec<TableSlotOffset>),
+
+    /// An empty spot in the table. This can happen when there is a gap in columns between
+    /// cells that are defined and one which should exist because of cell with a rowspan
+    /// from a previous row.
+    Empty,
+}
+
+impl std::fmt::Debug for TableSlot {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        match self {
+            Self::Cell(_) => f.debug_tuple("Cell").finish(),
+            Self::Spanned(spanned) => f.debug_tuple("Spanned").field(spanned).finish(),
+            Self::Empty => write!(f, "Empty"),
+        }
+    }
+}
+
+impl TableSlot {
+    fn new_spanned(offset: TableSlotOffset) -> Self {
+        Self::Spanned(vec![offset])
+    }
+}
diff --git a/components/layout_2020/tests/tables.rs b/components/layout_2020/tests/tables.rs
new file mode 100644
index 00000000000..66976a3ef62
--- /dev/null
+++ b/components/layout_2020/tests/tables.rs
@@ -0,0 +1,251 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
+
+//! Tests for proper table box tree construction.
+
+mod tables {
+    use euclid::Vector2D;
+    use layout_2020::table::{Table, TableBuilder, TableSlot, TableSlotCell, TableSlotOffset};
+
+    fn row_lengths(table: &Table) -> Vec<usize> {
+        table.slots.iter().map(|row| row.len()).collect()
+    }
+
+    fn slot_is_cell_with_id(slot: &TableSlot, id: u8) -> bool {
+        match slot {
+            TableSlot::Cell(TableSlotCell { id: cell_id, .. }) if id == *cell_id => true,
+            _ => false,
+        }
+    }
+
+    fn slot_is_empty(slot: &TableSlot) -> bool {
+        match slot {
+            TableSlot::Empty => true,
+            _ => false,
+        }
+    }
+
+    fn slot_is_spanned_with_offsets(slot: &TableSlot, offsets: Vec<(usize, usize)>) -> bool {
+        match slot {
+            TableSlot::Spanned(slot_offsets) => {
+                let offsets: Vec<TableSlotOffset> = offsets
+                    .iter()
+                    .map(|offset| Vector2D::new(offset.0, offset.1))
+                    .collect();
+                offsets == *slot_offsets
+            },
+            _ => false,
+        }
+    }
+
+    #[test]
+    fn test_empty_table() {
+        let table_builder = TableBuilder::default();
+        let table = table_builder.finish();
+        assert!(table.slots.is_empty())
+    }
+
+    #[test]
+    fn test_simple_table() {
+        let mut table_builder = TableBuilder::default();
+
+        table_builder.start_row();
+        table_builder.add_cell(TableSlotCell::mock_for_testing(1, 1, 1));
+        table_builder.add_cell(TableSlotCell::mock_for_testing(2, 1, 1));
+        table_builder.end_row();
+
+        table_builder.start_row();
+        table_builder.add_cell(TableSlotCell::mock_for_testing(3, 1, 1));
+        table_builder.add_cell(TableSlotCell::mock_for_testing(4, 1, 1));
+        table_builder.end_row();
+
+        let table = table_builder.finish();
+        assert_eq!(row_lengths(&table), vec![2, 2]);
+
+        assert!(slot_is_cell_with_id(&table.slots[0][0], 1));
+        assert!(slot_is_cell_with_id(&table.slots[0][1], 2));
+        assert!(slot_is_cell_with_id(&table.slots[1][0], 3));
+        assert!(slot_is_cell_with_id(&table.slots[1][1], 4));
+    }
+
+    #[test]
+    fn test_simple_rowspan() {
+        let mut table_builder = TableBuilder::default();
+
+        table_builder.start_row();
+        table_builder.add_cell(TableSlotCell::mock_for_testing(1, 1, 1));
+        table_builder.add_cell(TableSlotCell::mock_for_testing(2, 1, 1));
+        table_builder.add_cell(TableSlotCell::mock_for_testing(3, 1, 2));
+        table_builder.end_row();
+
+        table_builder.start_row();
+        table_builder.add_cell(TableSlotCell::mock_for_testing(4, 1, 1));
+        table_builder.end_row();
+
+        let table = table_builder.finish();
+        assert_eq!(row_lengths(&table), vec![3, 3]);
+
+        assert!(slot_is_cell_with_id(&table.slots[0][0], 1));
+        assert!(slot_is_cell_with_id(&table.slots[0][1], 2));
+        assert!(slot_is_cell_with_id(&table.slots[0][2], 3));
+
+        assert!(slot_is_cell_with_id(&table.slots[1][0], 4));
+        assert!(slot_is_empty(&table.slots[1][1]));
+        assert!(slot_is_spanned_with_offsets(
+            &table.slots[1][2],
+            vec![(0, 1)]
+        ));
+    }
+
+    #[test]
+    fn test_simple_colspan() {
+        let mut table_builder = TableBuilder::default();
+
+        table_builder.start_row();
+        table_builder.add_cell(TableSlotCell::mock_for_testing(1, 3, 1));
+        table_builder.add_cell(TableSlotCell::mock_for_testing(2, 1, 1));
+        table_builder.add_cell(TableSlotCell::mock_for_testing(3, 1, 1));
+        table_builder.end_row();
+
+        table_builder.start_row();
+        table_builder.add_cell(TableSlotCell::mock_for_testing(4, 1, 1));
+        table_builder.add_cell(TableSlotCell::mock_for_testing(5, 3, 1));
+        table_builder.add_cell(TableSlotCell::mock_for_testing(6, 1, 1));
+        table_builder.end_row();
+
+        table_builder.start_row();
+        table_builder.add_cell(TableSlotCell::mock_for_testing(7, 1, 1));
+        table_builder.add_cell(TableSlotCell::mock_for_testing(8, 1, 1));
+        table_builder.add_cell(TableSlotCell::mock_for_testing(9, 3, 1));
+        table_builder.end_row();
+
+        let table = table_builder.finish();
+        assert_eq!(row_lengths(&table), vec![5, 5, 5]);
+
+        assert!(slot_is_cell_with_id(&table.slots[0][0], 1));
+        assert!(slot_is_spanned_with_offsets(
+            &table.slots[0][1],
+            vec![(1, 0)]
+        ));
+        assert!(slot_is_spanned_with_offsets(
+            &table.slots[0][2],
+            vec![(2, 0)]
+        ));
+        assert!(slot_is_cell_with_id(&table.slots[0][3], 2));
+        assert!(slot_is_cell_with_id(&table.slots[0][4], 3));
+
+        assert!(slot_is_cell_with_id(&table.slots[1][0], 4));
+        assert!(slot_is_cell_with_id(&table.slots[1][1], 5));
+        assert!(slot_is_spanned_with_offsets(
+            &table.slots[1][2],
+            vec![(1, 0)]
+        ));
+        assert!(slot_is_spanned_with_offsets(
+            &table.slots[1][3],
+            vec![(2, 0)]
+        ));
+        assert!(slot_is_cell_with_id(&table.slots[1][4], 6));
+
+        assert!(slot_is_cell_with_id(&table.slots[2][0], 7));
+        assert!(slot_is_cell_with_id(&table.slots[2][1], 8));
+        assert!(slot_is_cell_with_id(&table.slots[2][2], 9));
+        assert!(slot_is_spanned_with_offsets(
+            &table.slots[2][3],
+            vec![(1, 0)]
+        ));
+        assert!(slot_is_spanned_with_offsets(
+            &table.slots[2][4],
+            vec![(2, 0)]
+        ));
+    }
+
+    #[test]
+    fn test_simple_table_model_error() {
+        let mut table_builder = TableBuilder::default();
+
+        table_builder.start_row();
+        table_builder.add_cell(TableSlotCell::mock_for_testing(1, 1, 1));
+        table_builder.add_cell(TableSlotCell::mock_for_testing(2, 1, 1));
+        table_builder.add_cell(TableSlotCell::mock_for_testing(3, 1, 2));
+        table_builder.end_row();
+
+        table_builder.start_row();
+        table_builder.add_cell(TableSlotCell::mock_for_testing(4, 3, 1));
+        table_builder.end_row();
+
+        let table = table_builder.finish();
+        assert_eq!(row_lengths(&table), vec![3, 3]);
+
+        assert!(slot_is_cell_with_id(&table.slots[0][0], 1));
+        assert!(slot_is_cell_with_id(&table.slots[0][1], 2));
+        assert!(slot_is_cell_with_id(&table.slots[0][2], 3));
+
+        assert!(slot_is_cell_with_id(&table.slots[1][0], 4));
+        assert!(slot_is_spanned_with_offsets(
+            &table.slots[1][1],
+            vec![(1, 0)]
+        ));
+        assert!(slot_is_spanned_with_offsets(
+            &table.slots[1][2],
+            vec![(2, 0), (0, 1)]
+        ));
+    }
+
+    #[test]
+    fn test_simple_rowspan_0() {
+        let mut table_builder = TableBuilder::default();
+
+        table_builder.start_row();
+        table_builder.add_cell(TableSlotCell::mock_for_testing(1, 1, 1));
+        table_builder.add_cell(TableSlotCell::mock_for_testing(2, 1, 1));
+        table_builder.add_cell(TableSlotCell::mock_for_testing(3, 1, 0));
+        table_builder.end_row();
+
+        table_builder.start_row();
+        table_builder.end_row();
+
+        table_builder.start_row();
+        table_builder.end_row();
+
+        table_builder.start_row();
+        table_builder.end_row();
+
+        let table = table_builder.finish();
+        assert_eq!(row_lengths(&table), vec![3, 3, 3, 3]);
+
+        assert!(slot_is_empty(&table.slots[1][0]));
+        assert!(slot_is_empty(&table.slots[1][1]));
+        assert!(slot_is_spanned_with_offsets(
+            &table.slots[1][2],
+            vec![(0, 1)]
+        ));
+        assert!(slot_is_spanned_with_offsets(
+            &table.slots[2][2],
+            vec![(0, 2)]
+        ));
+        assert!(slot_is_spanned_with_offsets(
+            &table.slots[3][2],
+            vec![(0, 3)]
+        ));
+    }
+
+    #[test]
+    fn test_incoming_rowspans() {
+        let mut table_builder = TableBuilder::default();
+
+        table_builder.start_row();
+        table_builder.add_cell(TableSlotCell::mock_for_testing(1, 1, 1));
+        table_builder.add_cell(TableSlotCell::mock_for_testing(2, 1, 30));
+        table_builder.end_row();
+
+        table_builder.start_row();
+        table_builder.add_cell(TableSlotCell::mock_for_testing(3, 2, 1));
+        table_builder.end_row();
+
+        assert_eq!(table_builder.incoming_rowspans, vec![0, 28]);
+
+        let table = table_builder.finish();
+        assert_eq!(row_lengths(&table), vec![2, 2]);
+    }
+}