layout: Add support for table rows, columns, rowgroups and colgroups (#31341)

This adds support for table rows, columns, rowgroups and colgroups.
There are few additions here:

1. The createion of fragments, which allows script queries and hit
   testing to work properly. These fragments are empty as all cells are
   still direct descendants of the table fragment.
2. Properly handling size information from tracks and track groups as
   well as frustrating rules about reordering rowgroups.
3. Painting a background seemlessly across track groups and groups. This
   is a thing that isn't done in legacy layout (nor WebKit)!

Co-authored-by: Oriol Brufau <obrufau@igalia.com>

1 files changed, 341 insertions, 21 deletions

diff --git a/components/layout_2020/table/construct.rs b/components/layout_2020/table/construct.rs
index 708113fd21d..5bde80ee67e 100644
--- a/components/layout_2020/table/construct.rs
+++ b/components/layout_2020/table/construct.rs
@@ -4,6 +4,7 @@
 
 use std::borrow::Cow;
 use std::convert::{TryFrom, TryInto};
+use std::iter::repeat;
 
 use log::warn;
 use script_layout_interface::wrapper_traits::ThreadSafeLayoutNode;
@@ -13,7 +14,10 @@ use style::selector_parser::PseudoElement;
 use style::str::char_is_whitespace;
 use style::values::specified::TextDecorationLine;
 
-use super::{Table, TableSlot, TableSlotCell, TableSlotCoordinates, TableSlotOffset};
+use super::{
+    Table, TableSlot, TableSlotCell, TableSlotCoordinates, TableSlotOffset, TableTrack,
+    TableTrackGroup, TableTrackGroupType,
+};
 use crate::context::LayoutContext;
 use crate::dom::{BoxSlot, NodeExt};
 use crate::dom_traversal::{Contents, NodeAndStyleInfo, NonReplacedContents, TraversalHandler};
@@ -224,30 +228,216 @@ impl TableBuilder {
         Self::new(ComputedValues::initial_values().to_arc())
     }
 
+    pub fn last_row_index_in_row_group_at_row_n(&self, n: usize) -> usize {
+        // TODO: This is just a linear search, because the idea is that there are
+        // generally less than or equal to three row groups, but if we notice a lot
+        // of web content with more, we can consider a binary search here.
+        for row_group in self.table.row_groups.iter() {
+            if row_group.track_range.start > n {
+                return row_group.track_range.start - 1;
+            }
+        }
+        self.table.size.height - 1
+    }
+
     pub fn finish(mut self) -> Table {
-        // Make sure that every row has the same number of cells.
+        self.do_missing_cells_fixup();
+        self.remove_extra_columns_and_column_groups();
+        self.reorder_first_thead_and_tfoot();
+        self.do_final_rowspan_calculation();
+        self.table
+    }
+
+    /// Do <https://drafts.csswg.org/css-tables/#missing-cells-fixup> which ensures
+    /// that every row has the same number of cells.
+    fn do_missing_cells_fixup(&mut self) {
         for row in self.table.slots.iter_mut() {
             row.resize_with(self.table.size.width, || TableSlot::Empty);
         }
+    }
+
+    /// It's possible to define more table columns via `<colgroup>` and `<col>` elements
+    /// than actually exist in the table. In that case, remove these bogus columns
+    /// to prevent using them later in layout.
+    fn remove_extra_columns_and_column_groups(&mut self) {
+        let number_of_actual_table_columns = self.table.size.width;
+        self.table.columns.truncate(number_of_actual_table_columns);
+
+        let mut remove_from = None;
+        for (group_index, column_group) in self.table.column_groups.iter_mut().enumerate() {
+            if column_group.track_range.start >= number_of_actual_table_columns {
+                remove_from = Some(group_index);
+                break;
+            }
+            column_group.track_range.end = column_group
+                .track_range
+                .end
+                .min(number_of_actual_table_columns);
+        }
+
+        if let Some(remove_from) = remove_from {
+            self.table.column_groups.truncate(remove_from);
+        }
+    }
+
+    /// Reorder the first `<thead>` and `<tbody>` to be the first and last row groups respectively.
+    /// This requires fixing up all row group indices.
+    /// See <https://drafts.csswg.org/css-tables/#table-header-group> and
+    /// <https://drafts.csswg.org/css-tables/#table-footer-group>.
+    fn reorder_first_thead_and_tfoot(&mut self) {
+        let mut thead_index = None;
+        let mut tfoot_index = None;
+        for (row_group_index, row_group) in self.table.row_groups.iter().enumerate() {
+            if thead_index.is_none() && row_group.group_type == TableTrackGroupType::HeaderGroup {
+                thead_index = Some(row_group_index);
+            }
+            if tfoot_index.is_none() && row_group.group_type == TableTrackGroupType::FooterGroup {
+                tfoot_index = Some(row_group_index);
+            }
+            if thead_index.is_some() && tfoot_index.is_some() {
+                break;
+            }
+        }
+
+        if let Some(thead_index) = thead_index {
+            self.move_row_group_to_front(thead_index)
+        }
+
+        if let Some(mut tfoot_index) = tfoot_index {
+            // We may have moved a `<thead>` which means the original index we
+            // we found for this this <tfoot>` also needs to be updated!
+            if thead_index.unwrap_or(0) > tfoot_index {
+                tfoot_index += 1;
+            }
+            self.move_row_group_to_end(tfoot_index)
+        }
+    }
+
+    fn regenerate_track_ranges(&mut self) {
+        // Now update all track group ranges.
+        let mut current_row_group_index = None;
+        for (row_index, row) in self.table.rows.iter().enumerate() {
+            if current_row_group_index == row.group_index {
+                continue;
+            }
+
+            // Finish any row group that is currently being processed.
+            if let Some(current_group_index) = current_row_group_index {
+                self.table.row_groups[current_group_index].track_range.end = row_index;
+            }
+
+            // Start processing this new row group and update its starting index.
+            current_row_group_index = row.group_index;
+            if let Some(current_group_index) = current_row_group_index {
+                self.table.row_groups[current_group_index].track_range.start = row_index;
+            }
+        }
+
+        // Finish the last row group.
+        if let Some(current_group_index) = current_row_group_index {
+            self.table.row_groups[current_group_index].track_range.end = self.table.rows.len();
+        }
+    }
+
+    fn move_row_group_to_front(&mut self, index_to_move: usize) {
+        if index_to_move == 0 {
+            return;
+        }
+
+        // Move the slots associated with this group.
+        let row_range = self.table.row_groups[index_to_move].track_range.clone();
+        let removed_slots: Vec<Vec<TableSlot>> = self
+            .table
+            .slots
+            .splice(row_range.clone(), std::iter::empty())
+            .collect();
+        self.table.slots.splice(0..0, removed_slots);
+
+        // Move the rows associated with this group.
+        let removed_rows: Vec<TableTrack> = self
+            .table
+            .rows
+            .splice(row_range, std::iter::empty())
+            .collect();
+        self.table.rows.splice(0..0, removed_rows);
+
+        // Move the group itself.
+        let removed_row_group = self.table.row_groups.remove(index_to_move);
+        self.table.row_groups.insert(0, removed_row_group);
+
+        for row in self.table.rows.iter_mut() {
+            match row.group_index.as_mut() {
+                Some(group_index) if *group_index < index_to_move => *group_index += 1,
+                Some(group_index) if *group_index == index_to_move => *group_index = 0,
+                _ => {},
+            }
+        }
+
+        // Do this now, rather than after possibly moving a `<tfoot>` row group to the end,
+        // because moving row groups depends on an accurate `track_range` in every group.
+        self.regenerate_track_ranges();
+    }
+
+    fn move_row_group_to_end(&mut self, index_to_move: usize) {
+        let last_row_group_index = self.table.row_groups.len() - 1;
+        if index_to_move == last_row_group_index {
+            return;
+        }
+
+        // Move the slots associated with this group.
+        let row_range = self.table.row_groups[index_to_move].track_range.clone();
+        let removed_slots: Vec<Vec<TableSlot>> = self
+            .table
+            .slots
+            .splice(row_range.clone(), std::iter::empty())
+            .collect();
+        self.table.slots.extend(removed_slots);
+
+        // Move the rows associated with this group.
+        let removed_rows: Vec<TableTrack> = self
+            .table
+            .rows
+            .splice(row_range, std::iter::empty())
+            .collect();
+        self.table.rows.extend(removed_rows);
+
+        // Move the group itself.
+        let removed_row_group = self.table.row_groups.remove(index_to_move);
+        self.table.row_groups.push(removed_row_group);
+
+        for row in self.table.rows.iter_mut() {
+            match row.group_index.as_mut() {
+                Some(group_index) if *group_index > index_to_move => *group_index -= 1,
+                Some(group_index) if *group_index == index_to_move => {
+                    *group_index = last_row_group_index
+                },
+                _ => {},
+            }
+        }
 
-        // Turn all rowspan=0 rows into the real value to avoid having to
-        // make the calculation continually during layout. In addition, make
-        // sure that there are no rowspans that extend past the end of the
-        // table.
+        self.regenerate_track_ranges();
+    }
+
+    /// Turn all rowspan=0 rows into the real value to avoid having to make the calculation
+    /// continually during layout. In addition, make sure that there are no rowspans that extend
+    /// past the end of their row group.
+    fn do_final_rowspan_calculation(&mut self) {
         for row_index in 0..self.table.size.height {
+            let last_row_index_in_group = self.last_row_index_in_row_group_at_row_n(row_index);
             for cell in self.table.slots[row_index].iter_mut() {
                 if let TableSlot::Cell(ref mut cell) = cell {
-                    let rowspan_to_end_of_table = self.table.size.height - row_index;
+                    if cell.rowspan == 1 {
+                        continue;
+                    }
+                    let rowspan_to_end_of_group = last_row_index_in_group - row_index + 1;
                     if cell.rowspan == 0 {
-                        cell.rowspan = rowspan_to_end_of_table;
+                        cell.rowspan = rowspan_to_end_of_group;
                     } else {
-                        cell.rowspan = cell.rowspan.min(rowspan_to_end_of_table);
+                        cell.rowspan = cell.rowspan.min(rowspan_to_end_of_group);
                     }
                 }
             }
         }
-
-        self.table
     }
 
     fn current_y(&self) -> usize {
@@ -408,6 +598,9 @@ pub(crate) struct TableBuilderTraversal<'style, 'dom, Node> {
     builder: TableBuilder,
 
     current_anonymous_row_content: Vec<AnonymousTableContent<'dom, Node>>,
+
+    /// The index of the current row group, if there is one.
+    current_row_group_index: Option<usize>,
 }
 
 impl<'style, 'dom, Node> TableBuilderTraversal<'style, 'dom, Node>
@@ -425,6 +618,7 @@ where
             propagated_text_decoration_line,
             builder: TableBuilder::new(info.style.clone()),
             current_anonymous_row_content: Vec::new(),
+            current_row_group_index: None,
         }
     }
 
@@ -499,17 +693,26 @@ where
                 DisplayLayoutInternal::TableFooterGroup |
                 DisplayLayoutInternal::TableHeaderGroup => {
                     self.finish_anonymous_row_if_needed();
-
-                    // 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();
+
+                    let next_row_index = self.builder.table.rows.len();
+                    self.builder.table.row_groups.push(TableTrackGroup {
+                        base_fragment_info: info.into(),
+                        style: info.style.clone(),
+                        group_type: internal.into(),
+                        track_range: next_row_index..next_row_index,
+                    });
+
+                    let new_row_group_index = self.builder.table.row_groups.len() - 1;
+                    self.current_row_group_index = Some(new_row_group_index);
                     NonReplacedContents::try_from(contents).unwrap().traverse(
                         self.context,
                         info,
                         self,
                     );
 
-                    // TODO: Handle style for row groups here.
+                    self.current_row_group_index = None;
+                    self.builder.incoming_rowspans.clear();
 
                     // We are doing this until we have actually set a Box for this `BoxSlot`.
                     ::std::mem::forget(box_slot)
@@ -527,17 +730,87 @@ where
                     );
                     row_builder.finish();
 
+                    self.builder.table.rows.push(TableTrack {
+                        base_fragment_info: info.into(),
+                        style: info.style.clone(),
+                        group_index: self.current_row_group_index,
+                        is_anonymous: false,
+                    });
+
+                    let last_row = self.builder.table.rows.len();
+                    let row_group = self
+                        .current_row_group_index
+                        .map(|index| &mut self.builder.table.row_groups[index]);
+                    if let Some(row_group) = row_group {
+                        row_group.track_range.end = last_row;
+                    }
+
                     // We are doing this until we have actually set a Box for this `BoxSlot`.
                     ::std::mem::forget(box_slot)
                 },
-                DisplayLayoutInternal::TableCaption |
-                DisplayLayoutInternal::TableColumn |
-                DisplayLayoutInternal::TableColumnGroup => {
-                    // TODO: Handle these other types of table elements.
+                DisplayLayoutInternal::TableColumn => {
+                    let node = info.node.to_threadsafe();
+                    let span = (node.get_span().unwrap_or(1) as usize).min(1000);
+                    for _ in 0..span + 1 {
+                        self.builder.table.columns.push(TableTrack {
+                            base_fragment_info: info.into(),
+                            style: info.style.clone(),
+                            group_index: None,
+                            is_anonymous: false,
+                        })
+                    }
 
                     // We are doing this until we have actually set a Box for this `BoxSlot`.
                     ::std::mem::forget(box_slot)
                 },
+                DisplayLayoutInternal::TableColumnGroup => {
+                    let column_group_index = self.builder.table.column_groups.len();
+                    let mut column_group_builder = TableColumnGroupBuilder {
+                        column_group_index,
+                        columns: Vec::new(),
+                    };
+
+                    NonReplacedContents::try_from(contents).unwrap().traverse(
+                        self.context,
+                        info,
+                        &mut column_group_builder,
+                    );
+
+                    let first_column = self.builder.table.columns.len();
+                    if column_group_builder.columns.is_empty() {
+                        let node = info.node.to_threadsafe();
+                        let span = (node.get_span().unwrap_or(1) as usize).min(1000);
+
+                        self.builder.table.columns.extend(
+                            repeat(TableTrack {
+                                base_fragment_info: info.into(),
+                                style: info.style.clone(),
+                                group_index: Some(column_group_index),
+                                is_anonymous: true,
+                            })
+                            .take(span),
+                        );
+                    } else {
+                        self.builder
+                            .table
+                            .columns
+                            .extend(column_group_builder.columns);
+                    }
+
+                    self.builder.table.column_groups.push(TableTrackGroup {
+                        base_fragment_info: info.into(),
+                        style: info.style.clone(),
+                        group_type: internal.into(),
+                        track_range: first_column..self.builder.table.columns.len(),
+                    });
+
+                    ::std::mem::forget(box_slot);
+                },
+                DisplayLayoutInternal::TableCaption => {
+                    // TODO: Handle table captions.
+                    // We are doing this until we have actually set a Box for this `BoxSlot`.
+                    ::std::mem::forget(box_slot);
+                },
                 DisplayLayoutInternal::TableCell => {
                     self.current_anonymous_row_content
                         .push(AnonymousTableContent::Element {
@@ -682,8 +955,8 @@ where
                     // 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 rowspan = (node.get_rowspan().unwrap_or(1) as usize).min(65534);
+                    let colspan = (node.get_colspan().unwrap_or(1) as usize).min(1000);
 
                     let contents = match contents.try_into() {
                         Ok(non_replaced_contents) => {
@@ -735,3 +1008,50 @@ where
         }
     }
 }
+
+struct TableColumnGroupBuilder {
+    column_group_index: usize,
+    columns: Vec<TableTrack>,
+}
+
+impl<'dom, Node: 'dom> TraversalHandler<'dom, Node> for TableColumnGroupBuilder
+where
+    Node: NodeExt<'dom>,
+{
+    fn handle_text(&mut self, _info: &NodeAndStyleInfo<Node>, _text: Cow<'dom, str>) {}
+    fn handle_element(
+        &mut self,
+        info: &NodeAndStyleInfo<Node>,
+        display: DisplayGeneratingBox,
+        _contents: Contents,
+        box_slot: BoxSlot<'dom>,
+    ) {
+        // We are doing this until we have actually set a Box for this `BoxSlot`.
+        ::std::mem::forget(box_slot);
+
+        if !matches!(
+            display,
+            DisplayGeneratingBox::LayoutInternal(DisplayLayoutInternal::TableColumn)
+        ) {
+            return;
+        }
+        self.columns.push(TableTrack {
+            base_fragment_info: info.into(),
+            style: info.style.clone(),
+            group_index: Some(self.column_group_index),
+            is_anonymous: false,
+        });
+    }
+}
+
+impl From<DisplayLayoutInternal> for TableTrackGroupType {
+    fn from(value: DisplayLayoutInternal) -> Self {
+        match value {
+            DisplayLayoutInternal::TableColumnGroup => TableTrackGroupType::ColumnGroup,
+            DisplayLayoutInternal::TableFooterGroup => TableTrackGroupType::FooterGroup,
+            DisplayLayoutInternal::TableHeaderGroup => TableTrackGroupType::HeaderGroup,
+            DisplayLayoutInternal::TableRowGroup => TableTrackGroupType::RowGroup,
+            _ => unreachable!(),
+        }
+    }
+}