layout.rs

/* 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::ops::Range;

use app_units::{Au, MAX_AU};
use log::warn;
use servo_arc::Arc;
use style::computed_values::border_collapse::T as BorderCollapse;
use style::logical_geometry::WritingMode;
use style::properties::ComputedValues;
use style::values::computed::{
    CSSPixelLength, Length, LengthPercentage as ComputedLengthPercentage, Percentage,
};
use style::values::generics::box_::{GenericVerticalAlign as VerticalAlign, VerticalAlignKeyword};
use style::values::generics::length::GenericLengthPercentageOrAuto::{Auto, LengthPercentage};
use style::Zero;

use super::{Table, TableSlot, TableSlotCell, TableTrackGroup};
use crate::context::LayoutContext;
use crate::formatting_contexts::{Baselines, IndependentLayout};
use crate::fragment_tree::{
    BoxFragment, CollapsedBlockMargins, ExtraBackground, Fragment, PositioningFragment,
};
use crate::geom::{AuOrAuto, LengthPercentageOrAuto, LogicalRect, LogicalSides, LogicalVec2};
use crate::positioned::{PositioningContext, PositioningContextLength};
use crate::sizing::ContentSizes;
use crate::style_ext::{Clamp, ComputedValuesExt, PaddingBorderMargin};
use crate::table::TableSlotCoordinates;
use crate::ContainingBlock;

/// A result of a final or speculative layout of a single cell in
/// the table. Note that this is only done for slots that are not
/// covered by spans or empty.
struct CellLayout {
    layout: IndependentLayout,
    padding: LogicalSides<Length>,
    border: LogicalSides<Length>,
    positioning_context: PositioningContext,
}

impl CellLayout {
    fn ascent(&self) -> Au {
        self.layout
            .baselines
            .first
            .unwrap_or(self.layout.content_block_size)
    }

    /// The block size of this laid out cell including its border and padding.
    fn outer_block_size(&self) -> Au {
        self.layout.content_block_size + (self.border.block_sum() + self.padding.block_sum()).into()
    }
}

/// Information stored during the layout of rows.
#[derive(Clone, Debug, Default)]
struct RowLayout {
    constrained: bool,
    has_cell_with_span_greater_than_one: bool,
    percent: Percentage,
}

/// Information stored during the layout of columns.
#[derive(Clone, Debug, Default)]
struct ColumnLayout {
    constrained: bool,
    has_originating_cells: bool,
}

/// A helper struct that performs the layout of the box tree version
/// of a table into the fragment tree version. This implements
/// <https://drafts.csswg.org/css-tables/#table-layout-algorithm>
struct TableLayout<'a> {
    table: &'a Table,
    pbm: PaddingBorderMargin,
    rows: Vec<RowLayout>,
    columns: Vec<ColumnLayout>,
    cell_measures: Vec<Vec<LogicalVec2<CellOrTrackMeasure>>>,
    assignable_width: Au,
    final_table_height: Au,
    column_measures: Vec<CellOrTrackMeasure>,
    distributed_column_widths: Vec<Au>,
    row_sizes: Vec<Au>,
    row_baselines: Vec<Au>,
    cells_laid_out: Vec<Vec<Option<CellLayout>>>,
    basis_for_cell_padding_percentage: Au,
}

#[derive(Clone, Debug)]
struct CellOrTrackMeasure {
    content_sizes: ContentSizes,
    percentage: Percentage,
}

impl Zero for CellOrTrackMeasure {
    fn zero() -> Self {
        Self {
            content_sizes: ContentSizes::zero(),
            percentage: Percentage(0.),
        }
    }

    fn is_zero(&self) -> bool {
        self.content_sizes.is_zero() && self.percentage.is_zero()
    }
}

impl<'a> TableLayout<'a> {
    fn new(table: &'a Table) -> TableLayout {
        Self {
            table,
            pbm: PaddingBorderMargin::zero(),
            rows: Vec::new(),
            columns: Vec::new(),
            cell_measures: Vec::new(),
            assignable_width: Au::zero(),
            final_table_height: Au::zero(),
            column_measures: Vec::new(),
            distributed_column_widths: Vec::new(),
            row_sizes: Vec::new(),
            row_baselines: Vec::new(),
            cells_laid_out: Vec::new(),
            basis_for_cell_padding_percentage: Au::zero(),
        }
    }

    /// This is an implementation of *Computing Cell Measures* from
    /// <https://drafts.csswg.org/css-tables/#computing-cell-measures>.
    pub(crate) fn compute_cell_measures(
        &mut self,
        layout_context: &LayoutContext,
        writing_mode: WritingMode,
    ) {
        let row_measures = vec![LogicalVec2::zero(); self.table.size.width];
        self.cell_measures = vec![row_measures; self.table.size.height];

        for row_index in 0..self.table.size.height {
            for column_index in 0..self.table.size.width {
                let cell = match self.table.slots[row_index][column_index] {
                    TableSlot::Cell(ref cell) => cell,
                    _ => continue,
                };

                let (size, min_size, max_size) = get_sizes_from_style(&cell.style, writing_mode);
                let inline_content_sizes = cell
                    .contents
                    .contents
                    .inline_content_sizes(layout_context, writing_mode);
                let percentage_contribution =
                    get_size_percentage_contribution_from_style(&cell.style, writing_mode);

                // > The outer min-content width of a table-cell is max(min-width, min-content width)
                // > adjusted by the cell intrinsic offsets.
                let mut outer_min_content_width =
                    inline_content_sizes.min_content.max(min_size.inline);
                let mut outer_max_content_width = if !self.columns[column_index].constrained {
                    // > The outer max-content width of a table-cell in a non-constrained column is
                    // > max(min-width, width, min-content width, min(max-width, max-content width))
                    // > adjusted by the cell intrinsic offsets.
                    min_size
                        .inline
                        .max(size.inline)
                        .max(inline_content_sizes.min_content)
                        .max(max_size.inline.min(inline_content_sizes.max_content))
                } else {
                    // > The outer max-content width of a table-cell in a constrained column is
                    // > max(min-width, width, min-content width, min(max-width, width)) adjusted by the
                    // > cell intrinsic offsets.
                    min_size
                        .inline
                        .max(size.inline)
                        .max(inline_content_sizes.min_content)
                        .max(max_size.inline.min(size.inline))
                };

                let padding = cell
                    .style
                    .padding(writing_mode)
                    .percentages_relative_to(Length::zero());
                let border = cell.style.border_width(writing_mode);

                let inline_padding_border_sum =
                    Au::from(padding.inline_sum() + border.inline_sum());
                outer_min_content_width += inline_padding_border_sum;
                outer_max_content_width += inline_padding_border_sum;

                let inline_measure = CellOrTrackMeasure {
                    content_sizes: ContentSizes {
                        min_content: outer_min_content_width,
                        max_content: outer_max_content_width,
                    },
                    percentage: percentage_contribution.inline,
                };

                // These calculations do not take into account the `min-content` and `max-content`
                // sizes. These sizes are incorporated after the first row layout pass, when the
                // block size of the layout is known.
                //
                // TODO: Is it correct to use the block size as the minimum of the `outer min
                // content height` here? The specification doesn't mention this, but it does cause
                // a test to pass.
                let mut outer_min_content_height = min_size.block.max(size.block);
                let mut outer_max_content_height = if !self.rows[row_index].constrained {
                    min_size.block.max(size.block)
                } else {
                    min_size
                        .block
                        .max(size.block)
                        .max(max_size.block.min(size.block))
                };

                let block_padding_border_sum = Au::from(padding.block_sum() + border.block_sum());
                outer_min_content_height += block_padding_border_sum;
                outer_max_content_height += block_padding_border_sum;

                let block_measure = CellOrTrackMeasure {
                    content_sizes: ContentSizes {
                        min_content: outer_min_content_height,
                        max_content: outer_max_content_height,
                    },
                    percentage: percentage_contribution.block,
                };

                self.cell_measures[row_index][column_index] = LogicalVec2 {
                    inline: inline_measure,
                    block: block_measure,
                };
            }
        }
    }

    /// Compute the constrainedness of every column in the table.
    ///
    /// > A column is constrained if its corresponding table-column-group (if any), its
    /// > corresponding table-column (if any), or any of the cells spanning only that
    /// > column has a computed width that is not "auto", and is not a percentage.
    fn compute_track_constrainedness_and_has_originating_cells(
        &mut self,
        writing_mode: WritingMode,
    ) {
        self.rows = vec![RowLayout::default(); self.table.size.height];
        self.columns = vec![ColumnLayout::default(); self.table.size.width];

        for column_index in 0..self.table.size.width {
            if let Some(column) = self.table.columns.get(column_index) {
                if !column.style.box_size(writing_mode).inline.is_auto() {
                    self.columns[column_index].constrained = true;
                    continue;
                }
                if let Some(column_group_index) = column.group_index {
                    let column_group = &self.table.column_groups[column_group_index];
                    if !column_group.style.box_size(writing_mode).inline.is_auto() {
                        self.columns[column_index].constrained = true;
                        continue;
                    }
                }
                self.columns[column_index].constrained = false;
            }
        }

        for row_index in 0..self.table.size.height {
            if let Some(row) = self.table.rows.get(row_index) {
                if !row.style.box_size(writing_mode).block.is_auto() {
                    self.rows[row_index].constrained = true;
                    continue;
                }
                if let Some(row_group_index) = row.group_index {
                    let row_group = &self.table.row_groups[row_group_index];
                    if !row_group.style.box_size(writing_mode).block.is_auto() {
                        self.rows[row_index].constrained = true;
                        continue;
                    }
                }
            }
            self.rows[row_index].constrained = false;
        }

        for column_index in 0..self.table.size.width {
            for row_index in 0..self.table.size.height {
                let coords = TableSlotCoordinates::new(column_index, row_index);
                let cell_constrained = match self.table.resolve_first_cell(coords) {
                    Some(cell) if cell.colspan == 1 => cell
                        .style
                        .box_size(writing_mode)
                        .inline
                        .non_auto()
                        .map(|length_percentage| length_percentage.to_length().is_some())
                        .unwrap_or(false),
                    _ => false,
                };

                let rowspan_greater_than_1 = match self.table.slots[row_index][column_index] {
                    TableSlot::Cell(ref cell) => cell.rowspan > 1,
                    _ => false,
                };

                self.rows[row_index].has_cell_with_span_greater_than_one |= rowspan_greater_than_1;
                self.rows[row_index].constrained |= cell_constrained;

                let has_originating_cell =
                    matches!(self.table.get_slot(coords), Some(TableSlot::Cell(_)));
                self.columns[column_index].has_originating_cells |= has_originating_cell;
                self.columns[column_index].constrained |= cell_constrained;
            }
        }
    }

    /// This is an implementation of *Computing Column Measures* from
    /// <https://drafts.csswg.org/css-tables/#computing-column-measures>.
    fn compute_column_measures(&mut self, writing_mode: WritingMode) {
        let mut column_measures = Vec::new();

        // Compute the column measures only taking into account cells with colspan == 1.
        // This is the base case that will be used to iteratively account for cells with
        // larger colspans afterward.
        //
        // > min-content width of a column based on cells of span up to 1
        // >     The largest of:
        // >         - the width specified for the column:
        // >               - the outer min-content width of its corresponding table-column,
        // >                 if any (and not auto)
        // >               - the outer min-content width of its corresponding table-column-group, if any
        // >               - or 0, if there is none
        // >         - the outer min-content width of each cell that spans the column whose colSpan
        // >           is 1 (or just the one in the first row in fixed mode) or 0 if there is none
        // >
        // > max-content width of a column based on cells of span up to 1
        // >     The largest of:
        // >         - the outer max-content width of its corresponding
        // >           table-column-group, if any
        // >         - the outer max-content width of its corresponding table-column, if any
        // >         - the outer max-content width of each cell that spans the column
        // >           whose colSpan is 1 (or just the one in the first row if in fixed mode) or 0
        // >           if there is no such cell
        // >
        // > intrinsic percentage width of a column based on cells of span up to 1
        // >     The largest of the percentage contributions of each cell that spans the column whose colSpan is
        // >     1, of its corresponding table-column (if any), and of its corresponding table-column-group (if
        // >     any)
        //
        // TODO: Take into account `table-column` and `table-column-group` lengths.
        // TODO: Take into account changes to this computation for fixed table layout.
        let mut next_span_n = usize::MAX;
        for column_index in 0..self.table.size.width {
            let mut column_measure = self
                .table
                .get_column_measure_for_column_at_index(writing_mode, column_index);

            for row_index in 0..self.table.size.height {
                let coords = TableSlotCoordinates::new(column_index, row_index);
                match self.table.resolve_first_cell(coords) {
                    Some(cell) if cell.colspan == 1 => cell,
                    Some(cell) => {
                        next_span_n = next_span_n.min(cell.colspan);
                        continue;
                    },
                    _ => continue,
                };

                // This takes the max of `min_content`, `max_content`, and
                // intrinsic percentage width as described above.
                let cell_measure = &self.cell_measures[row_index][column_index].inline;
                column_measure
                    .content_sizes
                    .max_assign(cell_measure.content_sizes);
                column_measure.percentage =
                    Percentage(column_measure.percentage.0.max(cell_measure.percentage.0));
            }

            column_measures.push(column_measure);
        }

        // Now we have the base computation complete, so iteratively take into account cells
        // with higher colspan. Using `next_span_n` we can skip over span counts that don't
        // correspond to any cells.
        while next_span_n < usize::MAX {
            (next_span_n, column_measures) = self
                .compute_content_sizes_for_columns_with_span_up_to_n(next_span_n, &column_measures);
        }

        // > intrinsic percentage width of a column:
        // > the smaller of:
        // >   * the intrinsic percentage width of the column based on cells of span up to N,
        // >     where N is the number of columns in the table
        // >   * 100% minus the sum of the intrinsic percentage width of all prior columns in
        // >     the table (further left when direction is "ltr" (right for "rtl"))
        let mut total_intrinsic_percentage_width = 0.;
        for column_index in 0..self.table.size.width {
            let column_measure = &mut column_measures[column_index];
            let final_intrinsic_percentage_width = column_measure
                .percentage
                .0
                .min(1. - total_intrinsic_percentage_width);
            total_intrinsic_percentage_width += final_intrinsic_percentage_width;
            column_measure.percentage = Percentage(final_intrinsic_percentage_width);
        }

        self.column_measures = column_measures;
    }

    fn compute_content_sizes_for_columns_with_span_up_to_n(
        &self,
        n: usize,
        old_column_measures: &[CellOrTrackMeasure],
    ) -> (usize, Vec<CellOrTrackMeasure>) {
        let mut next_span_n = usize::MAX;
        let mut new_content_sizes_for_columns = Vec::new();
        let border_spacing = self.table.border_spacing();

        for column_index in 0..self.table.size.width {
            let old_column_measure = &old_column_measures[column_index];
            let mut new_column_content_sizes = ContentSizes::zero();
            let mut new_column_intrinsic_percentage_width = Percentage(0.);

            for row_index in 0..self.table.size.height {
                let coords = TableSlotCoordinates::new(column_index, row_index);
                let resolved_coords = match self.table.resolve_first_cell_coords(coords) {
                    Some(resolved_coords) => resolved_coords,
                    None => continue,
                };

                let cell = match self.table.resolve_first_cell(resolved_coords) {
                    Some(cell) if cell.colspan <= n => cell,
                    Some(cell) => {
                        next_span_n = next_span_n.min(cell.colspan);
                        continue;
                    },
                    _ => continue,
                };

                let cell_measures =
                    &self.cell_measures[resolved_coords.y][resolved_coords.x].inline;
                let cell_inline_content_sizes = cell_measures.content_sizes;

                let columns_spanned = resolved_coords.x..resolved_coords.x + cell.colspan;
                let baseline_content_sizes: ContentSizes = columns_spanned.clone().fold(
                    ContentSizes::zero(),
                    |total: ContentSizes, spanned_column_index| {
                        total + old_column_measures[spanned_column_index].content_sizes
                    },
                );

                let old_column_content_size = old_column_measure.content_sizes;

                // > **min-content width of a column based on cells of span up to N (N > 1)**
                // >
                // > the largest of the min-content width of the column based on cells of span up to
                // > N-1 and the contributions of the cells in the column whose colSpan is N, where
                // > the contribution of a cell is the result of taking the following steps:
                // >
                // >     1. Define the baseline min-content width as the sum of the max-content
                // >        widths based on cells of span up to N-1 of all columns that the cell spans.
                //
                // Note: This definition is likely a typo, so we use the sum of the min-content
                // widths here instead.
                let baseline_min_content_width = baseline_content_sizes.min_content;
                let baseline_max_content_width = baseline_content_sizes.max_content;

                // >     2. Define the baseline border spacing as the sum of the horizontal
                // >        border-spacing for any columns spanned by the cell, other than the one in
                // >        which the cell originates.
                let baseline_border_spacing = border_spacing.inline * (n as i32 - 1);

                // >     3. The contribution of the cell is the sum of:
                // >         a. the min-content width of the column based on cells of span up to N-1
                let a = old_column_content_size.min_content;

                // >         b. the product of:
                // >             - the ratio of:
                // >                 - the max-content width of the column based on cells of span up
                // >                   to N-1 of the column minus the min-content width of the
                // >                   column based on cells of span up to N-1 of the column, to
                // >                 - the baseline max-content width minus the baseline min-content
                // >                   width
                // >               or zero if this ratio is undefined, and
                // >             - the outer min-content width of the cell minus the baseline
                // >               min-content width and the baseline border spacing, clamped to be
                // >               at least 0 and at most the difference between the baseline
                // >               max-content width and the baseline min-content width
                let old_content_size_difference =
                    old_column_content_size.max_content - old_column_content_size.min_content;
                let baseline_difference = baseline_min_content_width - baseline_max_content_width;

                let mut b =
                    old_content_size_difference.to_f32_px() / baseline_difference.to_f32_px();
                if !b.is_finite() {
                    b = 0.0;
                }
                let b = (cell_inline_content_sizes.min_content -
                    baseline_content_sizes.min_content -
                    baseline_border_spacing)
                    .clamp_between_extremums(Au::zero(), Some(baseline_difference))
                    .scale_by(b);

                // >         c. the product of:
                // >             - the ratio of the max-content width based on cells of span up to
                // >               N-1 of the column to the baseline max-content width
                // >             - the outer min-content width of the cell minus the baseline
                // >               max-content width and baseline border spacing, or 0 if this is
                // >               negative
                let c = (cell_inline_content_sizes.min_content -
                    baseline_content_sizes.max_content -
                    baseline_border_spacing)
                    .min(Au::zero())
                    .scale_by(
                        old_column_content_size.max_content.to_f32_px() /
                            baseline_content_sizes.max_content.to_f32_px(),
                    );

                let new_column_min_content_width = a + b + c;

                // > **max-content width of a column based on cells of span up to N (N > 1)**
                // >
                // > The largest of the max-content width based on cells of span up to N-1 and the
                // > contributions of the cells in the column whose colSpan is N, where the
                // > contribution of a cell is the result of taking the following steps:

                // >     1. Define the baseline max-content width as the sum of the max-content
                // >        widths based on cells of span up to N-1 of all columns that the cell spans.
                //
                // This is calculated above for the min-content width.

                // >     2. Define the baseline border spacing as the sum of the horizontal
                // >        border-spacing for any columns spanned by the cell, other than the one in
                // >        which the cell originates.
                //
                // This is calculated above for min-content width.

                // >     3. The contribution of the cell is the sum of:
                // >          a. the max-content width of the column based on cells of span up to N-1
                let a = old_column_content_size.max_content;

                // >          b. the product of:
                // >              1. the ratio of the max-content width based on cells of span up to
                // >                 N-1 of the column to the baseline max-content width
                let b_1 = old_column_content_size.max_content.to_f32_px() /
                    baseline_content_sizes.max_content.to_f32_px();

                // >              2. the outer max-content width of the cell minus the baseline
                // >                 max-content width and the baseline border spacing, or 0 if this
                // >                 is negative
                let b_2 = (cell_inline_content_sizes.max_content -
                    baseline_content_sizes.max_content -
                    baseline_border_spacing)
                    .min(Au::zero());
                let b = b_2.scale_by(b_1);
                let new_column_max_content_width = a + b + c;

                // The computed values for the column are always the largest of any processed cell
                // in that column.
                new_column_content_sizes.max_assign(ContentSizes {
                    min_content: new_column_min_content_width,
                    max_content: new_column_max_content_width,
                });

                // > If the intrinsic percentage width of a column based on cells of span up to N-1 is
                // > greater than 0%, then the intrinsic percentage width of the column based on cells
                // > of span up to N is the same as the intrinsic percentage width of the column based
                // > on cells of span up to N-1.
                // > Otherwise, it is the largest of the contributions of the cells in the column
                // > whose colSpan is N, where the contribution of a cell is the result of taking
                // > the following steps:
                if old_column_measure.percentage.0 <= 0. && cell_measures.percentage.0 != 0. {
                    // > 1. Start with the percentage contribution of the cell.
                    // > 2. Subtract the intrinsic percentage width of the column based on cells
                    // >    of span up to N-1 of all columns that the cell spans. If this gives a
                    // >    negative result, change it to 0%.
                    let mut spanned_columns_with_zero = 0;
                    let other_column_percentages_sum =
                        (columns_spanned).fold(0., |sum, spanned_column_index| {
                            let spanned_column_percentage =
                                old_column_measures[spanned_column_index].percentage;
                            if spanned_column_percentage.0 == 0. {
                                spanned_columns_with_zero += 1;
                            }
                            sum + spanned_column_percentage.0
                        });
                    let step_2 = (cell_measures.percentage -
                        Percentage(other_column_percentages_sum))
                    .clamp_to_non_negative();

                    // > Multiply by the ratio of:
                    // >  1. the column’s non-spanning max-content width to
                    // >  2. the sum of the non-spanning max-content widths of all columns
                    // >      spanned by the cell that have an intrinsic percentage width of the column
                    // >      based on cells of span up to N-1 equal to 0%.
                    // > However, if this ratio is undefined because the denominator is zero,
                    // > instead use the 1 divided by the number of columns spanned by the cell
                    // > that have an intrinsic percentage width of the column based on cells of
                    // > span up to N-1 equal to zero.
                    let step_3 = step_2.0 * (1.0 / spanned_columns_with_zero as f32);

                    new_column_intrinsic_percentage_width =
                        Percentage(new_column_intrinsic_percentage_width.0.max(step_3));
                }
            }
            new_content_sizes_for_columns.push(CellOrTrackMeasure {
                content_sizes: new_column_content_sizes,
                percentage: new_column_intrinsic_percentage_width,
            });
        }
        (next_span_n, new_content_sizes_for_columns)
    }

    /// Compute the GRIDMIN and GRIDMAX.
    fn compute_grid_min_max(
        &mut self,
        layout_context: &LayoutContext,
        writing_mode: WritingMode,
    ) -> ContentSizes {
        self.compute_track_constrainedness_and_has_originating_cells(writing_mode);
        self.compute_cell_measures(layout_context, writing_mode);
        self.compute_column_measures(writing_mode);

        // https://drafts.csswg.org/css-tables/#gridmin:
        // > 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.
        // https://drafts.csswg.org/css-tables/#gridmax:
        // > 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.
        let mut grid_min_max = self
            .column_measures
            .iter()
            .fold(ContentSizes::zero(), |result, measure| {
                result + measure.content_sizes
            });

        // TODO: GRIDMAX should never be smaller than GRIDMIN!
        grid_min_max.max_content = grid_min_max.max_content.max(grid_min_max.min_content);

        let inline_border_spacing = self.table.total_border_spacing().inline;
        grid_min_max.min_content += inline_border_spacing;
        grid_min_max.max_content += inline_border_spacing;
        grid_min_max
    }

    fn compute_table_width(
        &mut self,
        containing_block_for_children: &ContainingBlock,
        containing_block_for_table: &ContainingBlock,
        grid_min_max: ContentSizes,
    ) {
        let style = &self.table.style;
        self.pbm = style.padding_border_margin(containing_block_for_table);

        // https://drafts.csswg.org/css-tables/#resolved-table-width
        // * If inline-size computes to 'auto', this is the stretch-fit size
        //   (https://drafts.csswg.org/css-sizing-3/#stretch-fit-size).
        // * Otherwise, it's the resulting length (with percentages resolved).
        // In both cases, it's clamped between min-inline-size and max-inline-size.
        // This diverges a little from the specification.
        let resolved_table_width = containing_block_for_children.inline_size;

        // https://drafts.csswg.org/css-tables/#used-width-of-table
        // * If table-root has a computed value for inline-size different than auto:
        //   use the maximum of the resolved table width and GRIDMIN.
        // * If auto: use the resolved_table_width, clamped between GRIDMIN and GRIDMAX,
        //   but at least as big as min-inline-size.
        // This diverges a little from the specification, but should be equivalent
        // (other than using the stretch-fit size instead of the containing block width).
        let used_width_of_table = match style
            .content_box_size(containing_block_for_table, &self.pbm)
            .inline
        {
            LengthPercentage(_) => resolved_table_width.max(grid_min_max.min_content),
            Auto => {
                let min_width: Au = style
                    .content_min_box_size(containing_block_for_table, &self.pbm)
                    .inline
                    .auto_is(Length::zero)
                    .into();
                resolved_table_width
                    .clamp(grid_min_max.min_content, grid_min_max.max_content)
                    .max(min_width)
            },
        };

        // > The assignable table width is the used width of the table minus the total horizontal
        // > border spacing (if any). This is the width that we will be able to allocate to the
        // > columns.
        self.assignable_width = used_width_of_table - self.table.total_border_spacing().inline;

        // This is the amount that we will use to resolve percentages in the padding of cells.
        // It matches what Gecko and Blink do, though they disagree when there is a big caption.
        self.basis_for_cell_padding_percentage =
            used_width_of_table - self.table.border_spacing().inline * 2;
    }

    /// Distribute width to columns, performing step 2.4 of table layout from
    /// <https://drafts.csswg.org/css-tables/#table-layout-algorithm>.
    fn distribute_width_to_columns(&self) -> Vec<Au> {
        if self.table.slots.is_empty() {
            return Vec::new();
        }

        // > First, each column of the table is assigned a sizing type:
        // >  * percent-column: a column whose any constraint is defined to use a percentage only
        // >                    (with a value different from 0%)
        // >  * pixel-column: column whose any constraint is defined to use a defined length only
        // >                  (and is not a percent-column)
        // >  * auto-column: any other column
        // >
        // > Then, valid sizing methods are to be assigned to the columns by sizing type, yielding
        // > the following sizing-guesses:
        // >
        // > * The min-content sizing-guess is the set of column width assignments where
        // >   each column is assigned its min-content width.
        // > * The min-content-percentage sizing-guess is the set of column width assignments where:
        // >       * each percent-column is assigned the larger of:
        // >           * its intrinsic percentage width times the assignable width and
        // >           * its min-content width.
        // >       * all other columns are assigned their min-content width.
        // > * The min-content-specified sizing-guess is the set of column width assignments where:
        // >       * each percent-column is assigned the larger of:
        // >           * its intrinsic percentage width times the assignable width and
        // >           * its min-content width
        // >       * any other column that is constrained is assigned its max-content width
        // >       * all other columns are assigned their min-content width.
        // > * The max-content sizing-guess is the set of column width assignments where:
        // >       * each percent-column is assigned the larger of:
        // >           * its intrinsic percentage width times the assignable width and
        // >           * its min-content width
        // >       * all other columns are assigned their max-content width.
        let mut min_content_sizing_guesses = Vec::new();
        let mut min_content_percentage_sizing_guesses = Vec::new();
        let mut min_content_specified_sizing_guesses = Vec::new();
        let mut max_content_sizing_guesses = Vec::new();

        for column_idx in 0..self.table.size.width {
            let column_measure = &self.column_measures[column_idx];
            let min_content_width = column_measure.content_sizes.min_content;
            let max_content_width = column_measure.content_sizes.max_content;
            let constrained = self.columns[column_idx].constrained;

            let (
                min_content_percentage_sizing_guess,
                min_content_specified_sizing_guess,
                max_content_sizing_guess,
            ) = if !column_measure.percentage.is_zero() {
                let resolved = self.assignable_width.scale_by(column_measure.percentage.0);
                let percent_guess = min_content_width.max(resolved);
                (percent_guess, percent_guess, percent_guess)
            } else if constrained {
                (min_content_width, max_content_width, max_content_width)
            } else {
                (min_content_width, min_content_width, max_content_width)
            };

            min_content_sizing_guesses.push(min_content_width);
            min_content_percentage_sizing_guesses.push(min_content_percentage_sizing_guess);
            min_content_specified_sizing_guesses.push(min_content_specified_sizing_guess);
            max_content_sizing_guesses.push(max_content_sizing_guess);
        }

        // > If the assignable table width is less than or equal to the max-content sizing-guess, the
        // > used widths of the columns must be the linear combination (with weights adding to 1) of
        // > the two consecutive sizing-guesses whose width sums bound the available width.
        //
        // > Otherwise, the used widths of the columns are the result of starting from the max-content
        // > sizing-guess and distributing the excess width to the columns of the table according to
        // > the rules for distributing excess width to columns (for used width).
        fn sum(guesses: &[Au]) -> Au {
            guesses.iter().fold(Au::zero(), |sum, guess| sum + *guess)
        }

        let max_content_sizing_sum = sum(&max_content_sizing_guesses);
        if self.assignable_width >= max_content_sizing_sum {
            self.distribute_extra_width_to_columns(
                &mut max_content_sizing_guesses,
                max_content_sizing_sum,
            );
            return max_content_sizing_guesses;
        }
        let min_content_specified_sizing_sum = sum(&min_content_specified_sizing_guesses);
        if self.assignable_width == min_content_specified_sizing_sum {
            return min_content_specified_sizing_guesses;
        }
        let min_content_percentage_sizing_sum = sum(&min_content_percentage_sizing_guesses);
        if self.assignable_width == min_content_percentage_sizing_sum {
            return min_content_percentage_sizing_guesses;
        }
        let min_content_sizes_sum = sum(&min_content_sizing_guesses);
        if self.assignable_width <= min_content_sizes_sum {
            return min_content_sizing_guesses;
        }

        let bounds = |sum_a, sum_b| self.assignable_width > sum_a && self.assignable_width < sum_b;
        let blend = |a: &[Au], sum_a: Au, b: &[Au], sum_b: Au| {
            // First convert the Au units to f32 in order to do floating point division.
            let weight_a =
                (self.assignable_width - sum_b).to_f32_px() / (sum_a - sum_b).to_f32_px();
            let weight_b = 1.0 - weight_a;
            a.iter()
                .zip(b.iter())
                .map(|(guess_a, guess_b)| {
                    (guess_a.scale_by(weight_a)) + (guess_b.scale_by(weight_b))
                })
                .collect()
        };

        if bounds(min_content_sizes_sum, min_content_percentage_sizing_sum) {
            return blend(
                &min_content_sizing_guesses,
                min_content_sizes_sum,
                &min_content_percentage_sizing_guesses,
                min_content_percentage_sizing_sum,
            );
        }

        if bounds(
            min_content_percentage_sizing_sum,
            min_content_specified_sizing_sum,
        ) {
            return blend(
                &min_content_percentage_sizing_guesses,
                min_content_percentage_sizing_sum,
                &min_content_specified_sizing_guesses,
                min_content_specified_sizing_sum,
            );
        }

        assert!(bounds(
            min_content_specified_sizing_sum,
            max_content_sizing_sum
        ));
        blend(
            &min_content_specified_sizing_guesses,
            min_content_specified_sizing_sum,
            &max_content_sizing_guesses,
            max_content_sizing_sum,
        )
    }

    /// This is an implementation of *Distributing excess width to columns* from
    /// <https://drafts.csswg.org/css-tables/#distributing-width-to-columns>.
    fn distribute_extra_width_to_columns(&self, column_sizes: &mut Vec<Au>, column_sizes_sum: Au) {
        let all_columns = 0..self.table.size.width;
        let extra_inline_size = self.assignable_width - column_sizes_sum;

        let has_originating_cells =
            |column_index: &usize| self.columns[*column_index].has_originating_cells;
        let is_constrained = |column_index: &usize| self.columns[*column_index].constrained;
        let is_unconstrained = |column_index: &usize| !is_constrained(column_index);
        let has_percent_greater_than_zero =
            |column_index: &usize| self.column_measures[*column_index].percentage.0 > 0.;
        let has_percent_zero = |column_index: &usize| !has_percent_greater_than_zero(column_index);
        let has_max_content = |column_index: &usize| {
            self.column_measures[*column_index]
                .content_sizes
                .max_content !=
                Au(0)
        };

        let max_content_sum =
            |column_index: usize| self.column_measures[column_index].content_sizes.max_content;

        // > If there are non-constrained columns that have originating cells with intrinsic
        // > percentage width of 0% and with nonzero max-content width (aka the columns allowed to
        // > grow by this rule), the distributed widths of the columns allowed to grow by this rule
        // > are increased in proportion to max-content width so the total increase adds to the
        // > excess width.
        let unconstrained_max_content_columns = all_columns
            .clone()
            .filter(is_unconstrained)
            .filter(has_originating_cells)
            .filter(has_percent_zero)
            .filter(has_max_content);
        let total_max_content_width = unconstrained_max_content_columns
            .clone()
            .map(max_content_sum)
            .fold(Au::zero(), |a, b| a + b);
        if total_max_content_width != Au::zero() {
            for column_index in unconstrained_max_content_columns {
                column_sizes[column_index] += extra_inline_size.scale_by(
                    self.column_measures[column_index]
                        .content_sizes
                        .max_content
                        .to_f32_px() /
                        total_max_content_width.to_f32_px(),
                );
            }
            return;
        }

        // > Otherwise, if there are non-constrained columns that have originating cells with intrinsic
        // > percentage width of 0% (aka the columns allowed to grow by this rule, which thanks to the
        // > previous rule must have zero max-content width), the distributed widths of the columns
        // > allowed to grow by this rule are increased by equal amounts so the total increase adds to
        // > the excess width.V
        let unconstrained_no_percent_columns = all_columns
            .clone()
            .filter(is_unconstrained)
            .filter(has_originating_cells)
            .filter(has_percent_zero);
        let total_unconstrained_no_percent = unconstrained_no_percent_columns.clone().count();
        if total_unconstrained_no_percent > 0 {
            let extra_space_per_column =
                extra_inline_size.scale_by(1.0 / total_unconstrained_no_percent as f32);
            for column_index in unconstrained_no_percent_columns {
                column_sizes[column_index] += extra_space_per_column;
            }
            return;
        }

        // > Otherwise, if there are constrained columns with intrinsic percentage width of 0% and
        // > with nonzero max-content width (aka the columns allowed to grow by this rule, which, due
        // > to other rules, must have originating cells), the distributed widths of the columns
        // > allowed to grow by this rule are increased in proportion to max-content width so the
        // > total increase adds to the excess width.
        let constrained_max_content_columns = all_columns
            .clone()
            .filter(is_constrained)
            .filter(has_originating_cells)
            .filter(has_percent_zero)
            .filter(has_max_content);
        let total_max_content_width = constrained_max_content_columns
            .clone()
            .map(max_content_sum)
            .fold(Au::zero(), |a, b| a + b);
        if total_max_content_width != Au::zero() {
            for column_index in constrained_max_content_columns {
                column_sizes[column_index] += extra_inline_size.scale_by(
                    self.column_measures[column_index]
                        .content_sizes
                        .max_content
                        .to_f32_px() /
                        total_max_content_width.to_f32_px(),
                );
            }
            return;
        }

        // > Otherwise, if there are columns with intrinsic percentage width greater than 0% (aka the
        // > columns allowed to grow by this rule, which, due to other rules, must have originating
        // > cells), the distributed widths of the columns allowed to grow by this rule are increased
        // > in proportion to intrinsic percentage width so the total increase adds to the excess
        // > width.
        let columns_with_percentage = all_columns.clone().filter(has_percent_greater_than_zero);
        let total_percent = columns_with_percentage
            .clone()
            .map(|column_index| self.column_measures[column_index].percentage.0)
            .sum::<f32>();
        if total_percent > 0. {
            for column_index in columns_with_percentage {
                column_sizes[column_index] += extra_inline_size
                    .scale_by(self.column_measures[column_index].percentage.0 / total_percent);
            }
            return;
        }

        // > Otherwise, if there is any such column, the distributed widths of all columns that have
        // > originating cells are increased by equal amounts so the total increase adds to the excess
        // > width.
        let has_originating_cells_columns = all_columns.clone().filter(has_originating_cells);
        let total_has_originating_cells = has_originating_cells_columns.clone().count();
        if total_has_originating_cells > 0 {
            let extra_space_per_column =
                extra_inline_size.scale_by(1.0 / total_has_originating_cells as f32);
            for column_index in has_originating_cells_columns {
                column_sizes[column_index] += extra_space_per_column;
            }
            return;
        }

        // > Otherwise, the distributed widths of all columns are increased by equal amounts so the
        // total increase adds to the excess width.
        let extra_space_for_all_columns =
            extra_inline_size.scale_by(1.0 / self.table.size.width as f32);
        for guess in column_sizes.iter_mut() {
            *guess += extra_space_for_all_columns;
        }
    }

    /// This is an implementation of *Row layout (first pass)* from
    /// <https://drafts.csswg.org/css-tables/#row-layout>.
    fn layout_cells_in_row(
        &mut self,
        layout_context: &LayoutContext,
        containing_block_for_table: &ContainingBlock,
        parent_positioning_context: &mut PositioningContext,
    ) {
        for row_index in 0..self.table.slots.len() {
            let row = &self.table.slots[row_index];
            let mut cells_laid_out_row = Vec::new();
            for column_index in 0..row.len() {
                let cell = match &row[column_index] {
                    TableSlot::Cell(cell) => cell,
                    _ => {
                        cells_laid_out_row.push(None);
                        continue;
                    },
                };

                let mut total_width = Au::zero();
                for width_index in column_index..column_index + cell.colspan {
                    total_width += self.distributed_column_widths[width_index];
                }

                let border = cell
                    .style
                    .border_width(containing_block_for_table.style.writing_mode);
                let padding = cell
                    .style
                    .padding(containing_block_for_table.style.writing_mode)
                    .percentages_relative_to(self.basis_for_cell_padding_percentage.into());
                let inline_border_padding_sum = border.inline_sum() + padding.inline_sum();
                let mut total_width: CSSPixelLength =
                    Length::from(total_width) - inline_border_padding_sum;
                total_width = total_width.max(Length::zero());

                let containing_block_for_children = ContainingBlock {
                    inline_size: total_width.into(),
                    block_size: AuOrAuto::Auto,
                    style: &cell.style,
                };
                let collect_for_nearest_positioned_ancestor =
                    parent_positioning_context.collects_for_nearest_positioned_ancestor();
                let mut positioning_context =
                    PositioningContext::new_for_subtree(collect_for_nearest_positioned_ancestor);

                let layout = cell.contents.layout(
                    layout_context,
                    &mut positioning_context,
                    &containing_block_for_children,
                );

                let content_size_from_layout = ContentSizes {
                    min_content: layout.content_block_size,
                    max_content: layout.content_block_size,
                };
                self.cell_measures[row_index][column_index]
                    .block
                    .content_sizes
                    .max_assign(content_size_from_layout);

                cells_laid_out_row.push(Some(CellLayout {
                    layout,
                    padding,
                    border,
                    positioning_context,
                }));
            }
            self.cells_laid_out.push(cells_laid_out_row);
        }
    }

    /// Do the first layout of a table row, after laying out the cells themselves. This is
    /// more or less and implementation of <https://drafts.csswg.org/css-tables/#row-layout>.
    fn do_first_row_layout(&mut self, writing_mode: WritingMode) -> Vec<Au> {
        let mut row_sizes = (0..self.table.size.height)
            .map(|row_index| {
                let (mut max_ascent, mut max_descent, mut max_row_height) =
                    (Au::zero(), Au::zero(), Au::zero());

                for column_index in 0..self.table.size.width {
                    let cell = match self.table.slots[row_index][column_index] {
                        TableSlot::Cell(ref cell) => cell,
                        _ => continue,
                    };

                    let layout = match self.cells_laid_out[row_index][column_index] {
                        Some(ref layout) => layout,
                        None => {
                            warn!(
                                "Did not find a layout at a slot index with an originating cell."
                            );
                            continue;
                        },
                    };

                    let outer_block_size = layout.outer_block_size();
                    if cell.rowspan == 1 {
                        max_row_height = max_row_height.max(outer_block_size);
                    }

                    if cell.effective_vertical_align() == VerticalAlignKeyword::Baseline {
                        let ascent = layout.ascent();
                        let border_padding_start =
                            layout.border.block_start + layout.padding.block_start;
                        let border_padding_end = layout.border.block_end + layout.padding.block_end;
                        max_ascent = max_ascent.max(ascent + border_padding_start.into());

                        // Only take into account the descent of this cell if doesn't span
                        // rows. The descent portion of the cell in cells that do span rows
                        // may extend into other rows.
                        if cell.rowspan == 1 {
                            max_descent = max_descent.max(
                                layout.layout.content_block_size - ascent +
                                    border_padding_end.into(),
                            );
                        }
                    }
                }
                self.row_baselines.push(max_ascent);
                max_row_height.max(max_ascent + max_descent)
            })
            .collect();
        self.calculate_row_sizes_after_first_layout(&mut row_sizes, writing_mode);
        row_sizes
    }

    /// After doing layout of table rows, calculate final row size and distribute space across
    /// rowspanned cells. This follows the implementation of LayoutNG and the priority
    /// agorithm described at <https://github.com/w3c/csswg-drafts/issues/4418>.
    fn calculate_row_sizes_after_first_layout(
        &mut self,
        row_sizes: &mut Vec<Au>,
        writing_mode: WritingMode,
    ) {
        let mut cells_to_distribute = Vec::new();
        let mut total_percentage = 0.;
        for row_index in 0..self.table.size.height {
            let row_measure = self
                .table
                .get_row_measure_for_row_at_index(writing_mode, row_index);
            row_sizes[row_index] = row_sizes[row_index].max(row_measure.content_sizes.min_content);

            let mut percentage = match self.table.rows.get(row_index) {
                Some(row) => {
                    get_size_percentage_contribution_from_style(&row.style, writing_mode)
                        .block
                        .0
                },
                None => 0.,
            };
            for column_index in 0..self.table.size.width {
                let cell_percentage = self.cell_measures[row_index][column_index]
                    .block
                    .percentage
                    .0;
                percentage = percentage.max(cell_percentage);

                let cell_measure = &self.cell_measures[row_index][column_index].block;
                let cell = match self.table.slots[row_index][column_index] {
                    TableSlot::Cell(ref cell) if cell.rowspan > 1 => cell,
                    TableSlot::Cell(_) => {
                        // If this is an originating cell, that isn't spanning, then we make sure the row is
                        // at least big enough to hold the cell.
                        row_sizes[row_index] =
                            row_sizes[row_index].max(cell_measure.content_sizes.max_content);
                        continue;
                    },
                    _ => continue,
                };

                cells_to_distribute.push(RowspanToDistribute {
                    coordinates: TableSlotCoordinates::new(column_index, row_index),
                    cell,
                    measure: cell_measure,
                });
            }

            self.rows[row_index].percent = Percentage(percentage.min(1. - total_percentage));
            total_percentage += self.rows[row_index].percent.0;
        }

        cells_to_distribute.sort_by(|a, b| {
            if a.range() == b.range() {
                return a
                    .measure
                    .content_sizes
                    .min_content
                    .cmp(&b.measure.content_sizes.min_content);
            }
            if a.fully_encloses(b) {
                return std::cmp::Ordering::Greater;
            }
            if b.fully_encloses(a) {
                return std::cmp::Ordering::Less;
            }
            a.coordinates.y.cmp(&b.coordinates.y)
        });

        for rowspan_to_distribute in cells_to_distribute {
            let rows_spanned = rowspan_to_distribute.range();
            let current_rows_size: Au = rows_spanned.clone().map(|index| row_sizes[index]).sum();
            let border_spacing_spanned =
                self.table.border_spacing().block * (rows_spanned.len() - 1) as i32;
            let excess_size = (rowspan_to_distribute.measure.content_sizes.min_content -
                current_rows_size -
                border_spacing_spanned)
                .max(Au::zero());

            self.distribute_extra_size_to_rows(
                excess_size,
                rows_spanned,
                row_sizes,
                None,
                true, /* rowspan_distribution */
            );
        }
    }

    /// An implementation of the same extra block size distribution algorithm used in
    /// LayoutNG and described at <https://github.com/w3c/csswg-drafts/issues/4418>.
    fn distribute_extra_size_to_rows(
        &self,
        mut excess_size: Au,
        track_range: Range<usize>,
        track_sizes: &mut Vec<Au>,
        percentage_resolution_size: Option<Au>,
        rowspan_distribution: bool,
    ) {
        if excess_size.is_zero() {
            return;
        }

        let is_constrained = |track_index: &usize| self.rows[*track_index].constrained;
        let is_unconstrained = |track_index: &usize| !is_constrained(track_index);
        let is_empty: Vec<bool> = track_sizes.iter().map(|size| size.is_zero()).collect();
        let is_not_empty = |track_index: &usize| !is_empty[*track_index];
        let other_row_that_starts_a_rowspan = |track_index: &usize| {
            *track_index != track_range.start &&
                self.rows[*track_index].has_cell_with_span_greater_than_one
        };

        // If we have a table height (not during rowspan distribution), first distribute to rows
        // that have percentage sizes proportionally to the size missing to reach the percentage
        // of table height required.
        if let Some(percentage_resolution_size) = percentage_resolution_size {
            let get_percent_block_size_deficit = |row_index: usize, track_size: Au| {
                let size_needed_for_percent =
                    percentage_resolution_size.scale_by(self.rows[row_index].percent.0);
                (size_needed_for_percent - track_size).max(Au::zero())
            };
            let percent_block_size_deficit: Au = track_range
                .clone()
                .map(|index| get_percent_block_size_deficit(index, track_sizes[index]))
                .sum();
            let percent_distributable_block_size = percent_block_size_deficit.min(excess_size);
            if percent_distributable_block_size > Au::zero() {
                for track_index in track_range.clone() {
                    let row_deficit =
                        get_percent_block_size_deficit(track_index, track_sizes[track_index]);
                    if row_deficit > Au::zero() {
                        let ratio =
                            row_deficit.to_f32_px() / percent_block_size_deficit.to_f32_px();
                        let size = percent_distributable_block_size.scale_by(ratio);
                        track_sizes[track_index] += size;
                        excess_size -= size;
                    }
                }
            }
        }

        // If this is rowspan distribution and there are rows other than the first row that have a
        // cell with rowspan > 1, distribute the extra space equally to those rows.
        if rowspan_distribution {
            let rows_that_start_rowspan: Vec<usize> = track_range
                .clone()
                .filter(other_row_that_starts_a_rowspan)
                .collect();
            if !rows_that_start_rowspan.is_empty() {
                let scale = 1.0 / rows_that_start_rowspan.len() as f32;
                for track_index in rows_that_start_rowspan.iter() {
                    track_sizes[*track_index] += excess_size.scale_by(scale);
                }
                return;
            }
        }

        // If there are unconstrained non-empty rows, grow them all proportionally to their current size.
        let unconstrained_non_empty_rows: Vec<usize> = track_range
            .clone()
            .filter(is_unconstrained)
            .filter(is_not_empty)
            .collect();
        if !unconstrained_non_empty_rows.is_empty() {
            let total_size: Au = unconstrained_non_empty_rows
                .iter()
                .map(|index| track_sizes[*index])
                .sum();
            for track_index in unconstrained_non_empty_rows.iter() {
                let scale = track_sizes[*track_index].to_f32_px() / total_size.to_f32_px();
                track_sizes[*track_index] += excess_size.scale_by(scale);
            }
            return;
        }

        let (non_empty_rows, empty_rows): (Vec<usize>, Vec<usize>) =
            track_range.clone().partition(is_not_empty);
        let only_have_empty_rows = empty_rows.len() == track_range.len();
        if !empty_rows.is_empty() {
            // If this is rowspan distribution and there are only empty rows, just grow the
            // last one.
            if rowspan_distribution && only_have_empty_rows {
                track_sizes[*empty_rows.last().unwrap()] += excess_size;
                return;
            }

            // Otherwise, if we only have empty rows or if all the non-empty rows are constrained,
            // then grow the empty rows.
            let non_empty_rows_all_constrained = !non_empty_rows.iter().any(is_unconstrained);
            if only_have_empty_rows || non_empty_rows_all_constrained {
                // If there are both unconstrained and constrained empty rows, only increase the
                // size of the unconstrained ones, otherwise increase the size of all empty rows.
                let mut rows_to_grow = &empty_rows;
                let unconstrained_empty_rows: Vec<usize> = rows_to_grow
                    .iter()
                    .copied()
                    .filter(is_unconstrained)
                    .collect();
                if !unconstrained_empty_rows.is_empty() {
                    rows_to_grow = &unconstrained_empty_rows;
                }

                // All empty rows that will grow equally.
                let scale = 1.0 / rows_to_grow.len() as f32;
                for track_index in rows_to_grow.iter() {
                    track_sizes[*track_index] += excess_size.scale_by(scale);
                }
                return;
            }
        }

        // If there are non-empty rows, they all grow in proportion to their current size,
        // whether or not they are constrained.
        if !non_empty_rows.is_empty() {
            let total_size: Au = non_empty_rows.iter().map(|index| track_sizes[*index]).sum();
            for track_index in non_empty_rows.iter() {
                let scale = track_sizes[*track_index].to_f32_px() / total_size.to_f32_px();
                track_sizes[*track_index] += excess_size.scale_by(scale);
            }
        }
    }

    /// Given computed row sizes, compute the final block size of the table and distribute extra
    /// block size to table rows.
    fn compute_table_height_and_final_row_heights(
        &mut self,
        mut row_sizes: Vec<Au>,
        containing_block_for_children: &ContainingBlock,
        containing_block_for_table: &ContainingBlock,
    ) {
        // The table content height is the maximum of the computed table height from style and the
        // sum of computed row heights from row layout plus size from borders and spacing.
        // When block-size doesn't compute to auto, `containing_block_for children` will have
        // the resulting length, properly clamped between min-block-size and max-block-size.
        let style = &self.table.style;
        let table_height_from_style = match style
            .content_box_size(containing_block_for_table, &self.pbm)
            .block
        {
            LengthPercentage(_) => containing_block_for_children.block_size,
            Auto => style
                .content_min_box_size(containing_block_for_table, &self.pbm)
                .block
                .map(Au::from),
        }
        .auto_is(Au::zero);

        let block_border_spacing = self.table.total_border_spacing().block;
        let table_height_from_rows = row_sizes.iter().sum::<Au>() + block_border_spacing;
        self.final_table_height = table_height_from_rows.max(table_height_from_style);

        // If the table height is defined by the rows sizes, there is no extra space to distribute
        // to rows.
        if self.final_table_height == table_height_from_rows {
            self.row_sizes = row_sizes;
            return;
        }

        // There was extra block size added to the table from the table style, so distribute this
        // extra space to rows using the same distribution algorithm used for distributing rowspan
        // space.
        // TODO: This should first distribute space to row groups and then to rows.
        self.distribute_extra_size_to_rows(
            self.final_table_height - table_height_from_rows,
            0..self.table.size.height,
            &mut row_sizes,
            Some(self.final_table_height),
            false, /* rowspan_distribution */
        );
        self.row_sizes = row_sizes;
    }

    /// Lay out the table of this [`TableLayout`] into fragments. This should only be be called
    /// after calling [`TableLayout.compute_measures`].
    fn layout(
        mut self,
        layout_context: &LayoutContext,
        positioning_context: &mut PositioningContext,
        containing_block_for_children: &ContainingBlock,
        containing_block_for_table: &ContainingBlock,
    ) -> IndependentLayout {
        let writing_mode = containing_block_for_children.style.writing_mode;
        let grid_min_max = self.compute_grid_min_max(layout_context, writing_mode);
        self.compute_table_width(
            containing_block_for_children,
            containing_block_for_table,
            grid_min_max,
        );
        self.distributed_column_widths = self.distribute_width_to_columns();

        self.layout_cells_in_row(
            layout_context,
            containing_block_for_children,
            positioning_context,
        );
        let first_layout_row_heights = self.do_first_row_layout(writing_mode);
        self.compute_table_height_and_final_row_heights(
            first_layout_row_heights,
            containing_block_for_children,
            containing_block_for_table,
        );

        assert_eq!(self.table.size.height, self.row_sizes.len());
        assert_eq!(self.table.size.width, self.distributed_column_widths.len());

        let mut baselines = Baselines::default();
        let mut fragments = Vec::new();

        if self.table.size.width == 0 || self.table.size.height == 0 {
            return IndependentLayout {
                fragments,
                content_block_size: self.final_table_height,
                content_inline_size_for_table: Some(self.assignable_width),
                baselines,
            };
        }

        let dimensions = TableAndTrackDimensions::new(&self);
        self.make_fragments_for_columns_rows_and_groups(&dimensions, &mut fragments);

        for row_index in 0..self.table.size.height {
            // From <https://drafts.csswg.org/css-align-3/#baseline-export>
            // > If any cells in the row participate in first baseline/last baseline alignment along
            // > the inline axis, the first/last baseline set of the row is generated from their
            // > shared alignment baseline and the row’s first available font, after alignment has
            // > been performed. Otherwise, the first/last baseline set of the row is synthesized from
            // > the lowest and highest content edges of the cells in the row. [CSS2]
            //
            // If any cell below has baseline alignment, these values will be overwritten,
            // but they are initialized to the content edge of the first row.
            if row_index == 0 {
                let row_end = dimensions.get_row_rect(0).max_block_position();
                baselines.first = Some(row_end);
                baselines.last = Some(row_end);
            }

            for column_index in 0..self.table.size.width {
                let layout = match self.cells_laid_out[row_index][column_index].take() {
                    Some(layout) => layout,
                    None => {
                        continue;
                    },
                };

                let cell = match self.table.slots[row_index][column_index] {
                    TableSlot::Cell(ref cell) => cell,
                    _ => {
                        warn!("Did not find a non-spanned cell at index with layout.");
                        continue;
                    },
                };

                let cell_rect = dimensions.get_cell_rect(
                    TableSlotCoordinates::new(column_index, row_index),
                    cell.rowspan,
                    cell.colspan,
                );

                // If this cell has baseline alignment, it can adjust the table's overall baseline.
                let row_baseline = self.row_baselines[row_index];
                if cell.effective_vertical_align() == VerticalAlignKeyword::Baseline {
                    let baseline = cell_rect.start_corner.block + row_baseline;
                    if row_index == 0 {
                        baselines.first = Some(baseline);
                    }
                    baselines.last = Some(baseline);
                }

                let mut fragment =
                    cell.create_fragment(layout, cell_rect, row_baseline, positioning_context);

                let column = self.table.columns.get(column_index);
                let column_group = column
                    .and_then(|column| column.group_index)
                    .and_then(|index| self.table.column_groups.get(index));
                if let Some(column_group) = column_group {
                    fragment.add_extra_background(ExtraBackground {
                        style: column_group.style.clone(),
                        rect: dimensions.get_column_group_rect(column_group),
                    })
                }

                if let Some(column) = column {
                    if !column.is_anonymous {
                        fragment.add_extra_background(ExtraBackground {
                            style: column.style.clone(),
                            rect: dimensions.get_column_rect(column_index),
                        })
                    }
                }

                let row = self.table.rows.get(row_index);
                let row_group = row
                    .and_then(|row| row.group_index)
                    .and_then(|index| self.table.row_groups.get(index));
                if let Some(row_group) = row_group {
                    fragment.add_extra_background(ExtraBackground {
                        style: row_group.style.clone(),
                        rect: dimensions.get_row_group_rect(row_group),
                    })
                }

                if let Some(row) = row {
                    fragment.add_extra_background(ExtraBackground {
                        style: row.style.clone(),
                        rect: dimensions.get_row_rect(row_index),
                    })
                }

                fragments.push(Fragment::Box(fragment));
            }
        }

        if self.table.anonymous {
            baselines.first = None;
            baselines.last = None;
        }

        IndependentLayout {
            fragments,
            content_block_size: dimensions.table_rect.max_block_position(),
            content_inline_size_for_table: Some(dimensions.table_rect.max_inline_position()),
            baselines,
        }
    }

    fn make_fragments_for_columns_rows_and_groups(
        &mut self,
        dimensions: &TableAndTrackDimensions,
        fragments: &mut Vec<Fragment>,
    ) {
        for column_group in self.table.column_groups.iter() {
            if !column_group.is_empty() {
                fragments.push(Fragment::Positioning(PositioningFragment::new_empty(
                    column_group.base_fragment_info,
                    dimensions.get_column_group_rect(column_group).into(),
                    column_group.style.clone(),
                )));
            }
        }

        for (column_index, column) in self.table.columns.iter().enumerate() {
            fragments.push(Fragment::Positioning(PositioningFragment::new_empty(
                column.base_fragment_info,
                dimensions.get_column_rect(column_index).into(),
                column.style.clone(),
            )));
        }

        for row_group in self.table.row_groups.iter() {
            if !row_group.is_empty() {
                fragments.push(Fragment::Positioning(PositioningFragment::new_empty(
                    row_group.base_fragment_info,
                    dimensions.get_row_group_rect(row_group).into(),
                    row_group.style.clone(),
                )));
            }
        }

        for (row_index, row) in self.table.rows.iter().enumerate() {
            fragments.push(Fragment::Positioning(PositioningFragment::new_empty(
                row.base_fragment_info,
                dimensions.get_row_rect(row_index).into(),
                row.style.clone(),
            )));
        }
    }
}

struct TableAndTrackDimensions {
    /// The rect of the full table, not counting for borders, padding, and margin.
    table_rect: LogicalRect<Au>,
    /// The rect of the full table, not counting for borders, padding, and margin
    /// and offset by any border spacing and caption.
    table_cells_rect: LogicalRect<Au>,
    /// The min and max block offsets of each table row.
    row_dimensions: Vec<(Au, Au)>,
    /// The min and max inline offsets of each table column
    column_dimensions: Vec<(Au, Au)>,
}

impl TableAndTrackDimensions {
    fn new(table_layout: &TableLayout) -> Self {
        let border_spacing = table_layout.table.border_spacing();

        let mut column_dimensions = Vec::new();
        let mut column_offset = border_spacing.inline;
        for column_index in 0..table_layout.table.size.width {
            let column_size = table_layout.distributed_column_widths[column_index];
            column_dimensions.push((column_offset, column_offset + column_size));
            column_offset += column_size + border_spacing.inline;
        }

        let mut row_dimensions = Vec::new();
        let mut row_offset = border_spacing.block;
        for row_index in 0..table_layout.table.size.height {
            let row_size = table_layout.row_sizes[row_index];
            row_dimensions.push((row_offset, row_offset + row_size));
            row_offset += row_size + border_spacing.block;
        }

        let table_start_corner = LogicalVec2 {
            inline: column_dimensions[0].0,
            block: row_dimensions[0].0,
        };
        let table_size = &LogicalVec2 {
            inline: column_dimensions[column_dimensions.len() - 1].1,
            block: row_dimensions[row_dimensions.len() - 1].1,
        } - &table_start_corner;
        let table_cells_rect = LogicalRect {
            start_corner: table_start_corner,
            size: table_size,
        };

        let table_rect = LogicalRect {
            start_corner: LogicalVec2::zero(),
            size: LogicalVec2 {
                inline: column_offset,
                block: row_offset,
            },
        };

        Self {
            table_rect,
            table_cells_rect,
            row_dimensions,
            column_dimensions,
        }
    }

    fn get_row_rect(&self, row_index: usize) -> LogicalRect<Au> {
        let mut row_rect = self.table_cells_rect.clone();
        let row_dimensions = self.row_dimensions[row_index];
        row_rect.start_corner.block = row_dimensions.0;
        row_rect.size.block = row_dimensions.1 - row_dimensions.0;
        row_rect
    }

    fn get_column_rect(&self, column_index: usize) -> LogicalRect<Au> {
        let mut row_rect = self.table_cells_rect.clone();
        let column_dimensions = self.column_dimensions[column_index];
        row_rect.start_corner.inline = column_dimensions.0;
        row_rect.size.inline = column_dimensions.1 - column_dimensions.0;
        row_rect
    }

    fn get_row_group_rect(&self, row_group: &TableTrackGroup) -> LogicalRect<Au> {
        if row_group.is_empty() {
            return LogicalRect::zero();
        }

        let mut row_group_rect = self.table_cells_rect.clone();
        let block_start = self.row_dimensions[row_group.track_range.start].0;
        let block_end = self.row_dimensions[row_group.track_range.end - 1].1;
        row_group_rect.start_corner.block = block_start;
        row_group_rect.size.block = block_end - block_start;
        row_group_rect
    }

    fn get_column_group_rect(&self, column_group: &TableTrackGroup) -> LogicalRect<Au> {
        if column_group.is_empty() {
            return LogicalRect::zero();
        }

        let mut column_group_rect = self.table_cells_rect.clone();
        let inline_start = self.column_dimensions[column_group.track_range.start].0;
        let inline_end = self.column_dimensions[column_group.track_range.end - 1].1;
        column_group_rect.start_corner.inline = inline_start;
        column_group_rect.size.inline = inline_end - inline_start;
        column_group_rect
    }

    fn get_cell_rect(
        &self,
        coordinates: TableSlotCoordinates,
        rowspan: usize,
        colspan: usize,
    ) -> LogicalRect<Au> {
        let start_corner = LogicalVec2 {
            inline: self.column_dimensions[coordinates.x].0,
            block: self.row_dimensions[coordinates.y].0,
        };
        let size = &LogicalVec2 {
            inline: self.column_dimensions[coordinates.x + colspan - 1].1,
            block: self.row_dimensions[coordinates.y + rowspan - 1].1,
        } - &start_corner;
        LogicalRect { start_corner, size }
    }
}

impl Table {
    fn border_spacing(&self) -> LogicalVec2<Au> {
        if self.style.clone_border_collapse() == BorderCollapse::Collapse {
            LogicalVec2::zero()
        } else {
            let border_spacing = self.style.clone_border_spacing();
            LogicalVec2 {
                inline: border_spacing.horizontal(),
                block: border_spacing.vertical(),
            }
        }
    }

    fn total_border_spacing(&self) -> LogicalVec2<Au> {
        let border_spacing = self.border_spacing();
        LogicalVec2 {
            inline: if self.size.width > 0 {
                border_spacing.inline * (self.size.width as i32 + 1)
            } else {
                Au::zero()
            },
            block: if self.size.height > 0 {
                border_spacing.block * (self.size.height as i32 + 1)
            } else {
                Au::zero()
            },
        }
    }

    pub(crate) fn inline_content_sizes(
        &mut self,
        layout_context: &LayoutContext,
        writing_mode: WritingMode,
    ) -> ContentSizes {
        TableLayout::new(self).compute_grid_min_max(layout_context, writing_mode)
    }

    fn get_column_measure_for_column_at_index(
        &self,
        writing_mode: WritingMode,
        column_index: usize,
    ) -> CellOrTrackMeasure {
        let column = match self.columns.get(column_index) {
            Some(column) => column,
            None => return CellOrTrackMeasure::zero(),
        };

        let (size, min_size, max_size) = get_sizes_from_style(&column.style, writing_mode);
        let percentage_contribution =
            get_size_percentage_contribution_from_style(&column.style, writing_mode);

        CellOrTrackMeasure {
            content_sizes: ContentSizes {
                // > The outer min-content width of a table-column or table-column-group is
                // > max(min-width, width).
                // But that's clearly wrong, since it would be equal to or greater than
                // the outer max-content width. So we match other browsers instead.
                min_content: min_size.inline,
                // > The outer max-content width of a table-column or table-column-group is
                // > max(min-width, min(max-width, width)).
                // This matches Gecko, but Blink and WebKit ignore max_size.
                max_content: min_size.inline.max(max_size.inline.min(size.inline)),
            },
            percentage: percentage_contribution.inline,
        }
    }

    fn get_row_measure_for_row_at_index(
        &self,
        writing_mode: WritingMode,
        row_index: usize,
    ) -> CellOrTrackMeasure {
        let row = match self.rows.get(row_index) {
            Some(row) => row,
            None => return CellOrTrackMeasure::zero(),
        };

        // In the block axis, the min-content and max-content sizes are the same
        // (except for new layout boxes like grid and flex containers). Note that
        // other browsers don't seem to use the min and max sizing properties here.
        let size = row
            .style
            .box_size(writing_mode)
            .block
            .non_auto()
            .and_then(|size| size.to_length())
            .map_or_else(Au::zero, Au::from);
        let percentage_contribution =
            get_size_percentage_contribution_from_style(&row.style, writing_mode);

        CellOrTrackMeasure {
            content_sizes: ContentSizes {
                min_content: size,
                max_content: size,
            },
            percentage: percentage_contribution.block,
        }
    }

    pub(crate) fn layout(
        &self,
        layout_context: &LayoutContext,
        positioning_context: &mut PositioningContext,
        containing_block_for_children: &ContainingBlock,
        containing_block_for_table: &ContainingBlock,
    ) -> IndependentLayout {
        TableLayout::new(self).layout(
            layout_context,
            positioning_context,
            containing_block_for_children,
            containing_block_for_table,
        )
    }
}

impl TableSlotCell {
    fn effective_vertical_align(&self) -> VerticalAlignKeyword {
        match self.style.clone_vertical_align() {
            VerticalAlign::Keyword(VerticalAlignKeyword::Top) => VerticalAlignKeyword::Top,
            VerticalAlign::Keyword(VerticalAlignKeyword::Bottom) => VerticalAlignKeyword::Bottom,
            VerticalAlign::Keyword(VerticalAlignKeyword::Middle) => VerticalAlignKeyword::Middle,
            _ => VerticalAlignKeyword::Baseline,
        }
    }

    fn create_fragment(
        &self,
        mut layout: CellLayout,
        cell_rect: LogicalRect<Au>,
        cell_baseline: Au,
        positioning_context: &mut PositioningContext,
    ) -> BoxFragment {
        // This must be scoped to this function because it conflicts with euclid's Zero.
        use style::Zero as StyleZero;

        let cell_rect: LogicalRect<Length> = cell_rect.into();
        let cell_content_rect = cell_rect.deflate(&(&layout.padding + &layout.border));
        let content_block_size = layout.layout.content_block_size.into();
        let vertical_align_offset = match self.effective_vertical_align() {
            VerticalAlignKeyword::Top => Length::new(0.),
            VerticalAlignKeyword::Bottom => cell_content_rect.size.block - content_block_size,
            VerticalAlignKeyword::Middle => {
                (cell_content_rect.size.block - content_block_size).scale_by(0.5)
            },
            _ => {
                Length::from(cell_baseline) -
                    (layout.padding.block_start + layout.border.block_start) -
                    Length::from(layout.ascent())
            },
        };

        // Create an `AnonymousFragment` to move the cell contents to the cell baseline.
        let mut vertical_align_fragment_rect = cell_content_rect.clone();
        vertical_align_fragment_rect.start_corner = LogicalVec2 {
            inline: Length::new(0.),
            block: vertical_align_offset,
        };
        let vertical_align_fragment = PositioningFragment::new_anonymous(
            vertical_align_fragment_rect,
            layout.layout.fragments,
            self.style.writing_mode,
        );

        // Adjust the static position of all absolute children based on the
        // final content rect of this fragment. Note that we are not shifting by the position of the
        // Anonymous fragment we use to shift content to the baseline.
        //
        // TODO(mrobinson): This is correct for absolutes that are direct children of the table
        // cell, but wrong for absolute fragments that are more deeply nested in the hierarchy of
        // fragments.
        layout
            .positioning_context
            .adjust_static_position_of_hoisted_fragments_with_offset(
                &cell_content_rect.start_corner,
                PositioningContextLength::zero(),
            );
        positioning_context.append(layout.positioning_context);

        BoxFragment::new(
            self.base_fragment_info,
            self.style.clone(),
            vec![Fragment::Positioning(vertical_align_fragment)],
            cell_content_rect,
            layout.padding,
            layout.border,
            LogicalSides::zero(), /* margin */
            None,                 /* clearance */
            CollapsedBlockMargins::zero(),
        )
        .with_baselines(layout.layout.baselines)
    }
}

fn get_size_percentage_contribution_from_style(
    style: &Arc<ComputedValues>,
    writing_mode: WritingMode,
) -> LogicalVec2<Percentage> {
    // From <https://drafts.csswg.org/css-tables/#percentage-contribution>
    // > The percentage contribution of a table cell, column, or column group is defined
    // > in terms of the computed values of width and max-width that have computed values
    // > that are percentages:
    // >    min(percentage width, percentage max-width).
    // > If the computed values are not percentages, then 0% is used for width, and an
    // > infinite percentage is used for max-width.
    let size = style.box_size(writing_mode);
    let max_size = style.max_box_size(writing_mode);

    let get_contribution_for_axis =
        |size: LengthPercentageOrAuto<'_>, max_size: Option<&ComputedLengthPercentage>| {
            let size_percentage = size
                .non_auto()
                .and_then(|length_percentage| length_percentage.to_percentage())
                .unwrap_or(Percentage(0.));
            let max_size_percentage = max_size
                .and_then(|length_percentage| length_percentage.to_percentage())
                .unwrap_or(Percentage(f32::INFINITY));
            Percentage(size_percentage.0.min(max_size_percentage.0))
        };

    LogicalVec2 {
        inline: get_contribution_for_axis(size.inline, max_size.inline),
        block: get_contribution_for_axis(size.block, max_size.block),
    }
}

fn get_sizes_from_style(
    style: &Arc<ComputedValues>,
    writing_mode: WritingMode,
) -> (LogicalVec2<Au>, LogicalVec2<Au>, LogicalVec2<Au>) {
    let get_max_size_for_axis = |size: Option<&ComputedLengthPercentage>| {
        size.and_then(|length_percentage| length_percentage.to_length())
            .map_or(MAX_AU, Au::from)
    };

    let max_size = style.max_box_size(writing_mode);
    let max_size = LogicalVec2 {
        inline: get_max_size_for_axis(max_size.inline),
        block: get_max_size_for_axis(max_size.block),
    };

    let get_size_for_axis = |size: LengthPercentageOrAuto<'_>| {
        size.non_auto()
            .and_then(|size| size.to_length())
            .map_or_else(Au::zero, Au::from)
    };

    let min_size = style.min_box_size(writing_mode);
    let min_size = LogicalVec2 {
        inline: get_size_for_axis(min_size.inline),
        block: get_size_for_axis(min_size.block),
    };

    let size = style.box_size(writing_mode);
    let size = LogicalVec2 {
        inline: get_size_for_axis(size.inline),
        block: get_size_for_axis(size.block),
    };

    (size, min_size, max_size)
}

struct RowspanToDistribute<'a> {
    coordinates: TableSlotCoordinates,
    cell: &'a TableSlotCell,
    measure: &'a CellOrTrackMeasure,
}

impl<'a> RowspanToDistribute<'a> {
    fn range(&self) -> Range<usize> {
        self.coordinates.y..self.coordinates.y + self.cell.rowspan
    }

    fn fully_encloses(&self, other: &RowspanToDistribute) -> bool {
        other.coordinates.y > self.coordinates.y && other.range().end < self.range().end
    }
}