layout/table/
layout.rs

1/* This Source Code Form is subject to the terms of the Mozilla Public
2 * License, v. 2.0. If a copy of the MPL was not distributed with this
3 * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
4
5use core::cmp::Ordering;
6use std::mem;
7use std::ops::Range;
8
9use app_units::Au;
10use atomic_refcell::AtomicRef;
11use log::warn;
12use rayon::iter::{IndexedParallelIterator, IntoParallelRefIterator, ParallelIterator};
13use servo_arc::Arc;
14use strum::{EnumIter, IntoEnumIterator};
15use style::Zero;
16use style::computed_values::border_collapse::T as BorderCollapse;
17use style::computed_values::box_sizing::T as BoxSizing;
18use style::computed_values::caption_side::T as CaptionSide;
19use style::computed_values::empty_cells::T as EmptyCells;
20use style::computed_values::position::T as Position;
21use style::computed_values::table_layout::T as TableLayoutMode;
22use style::computed_values::visibility::T as Visibility;
23use style::properties::ComputedValues;
24use style::values::computed::{
25    BorderStyle, LengthPercentage as ComputedLengthPercentage, Percentage,
26};
27use style::values::generics::box_::{GenericVerticalAlign as VerticalAlign, VerticalAlignKeyword};
28
29use super::{
30    ArcRefCell, CollapsedBorder, CollapsedBorderLine, SpecificTableGridInfo, Table, TableCaption,
31    TableLayoutStyle, TableSlot, TableSlotCell, TableSlotCoordinates, TableTrack, TableTrackGroup,
32};
33use crate::context::LayoutContext;
34use crate::formatting_contexts::Baselines;
35use crate::fragment_tree::{
36    BoxFragment, CollapsedBlockMargins, ExtraBackground, Fragment, FragmentFlags,
37    PositioningFragment, SpecificLayoutInfo,
38};
39use crate::geom::{
40    LogicalRect, LogicalSides, LogicalSides1D, LogicalVec2, PhysicalPoint, PhysicalRect,
41    PhysicalSides, PhysicalVec, ToLogical, ToLogicalWithContainingBlock,
42};
43use crate::layout_box_base::CacheableLayoutResult;
44use crate::positioned::{PositioningContext, PositioningContextLength, relative_adjustement};
45use crate::sizing::{
46    ComputeInlineContentSizes, ContentSizes, InlineContentSizesResult, Size, SizeConstraint,
47};
48use crate::style_ext::{
49    BorderStyleColor, Clamp, ComputedValuesExt, LayoutStyle, PaddingBorderMargin,
50};
51use crate::{
52    ConstraintSpace, ContainingBlock, ContainingBlockSize, IndefiniteContainingBlock, WritingMode,
53};
54
55/// A result of a final or speculative layout of a single cell in
56/// the table. Note that this is only done for slots that are not
57/// covered by spans or empty.
58struct CellLayout {
59    layout: CacheableLayoutResult,
60    padding: LogicalSides<Au>,
61    border: LogicalSides<Au>,
62    positioning_context: PositioningContext,
63}
64
65impl CellLayout {
66    fn ascent(&self) -> Au {
67        self.layout
68            .baselines
69            .first
70            .unwrap_or(self.layout.content_block_size)
71    }
72
73    /// The block size of this laid out cell including its border and padding.
74    fn outer_block_size(&self) -> Au {
75        self.layout.content_block_size + self.border.block_sum() + self.padding.block_sum()
76    }
77
78    /// Whether the cell has no in-flow or out-of-flow contents, other than collapsed whitespace.
79    /// Note this logic differs from 'empty-cells', which counts abspos contents as empty.
80    fn is_empty(&self) -> bool {
81        self.layout.fragments.is_empty()
82    }
83
84    /// Whether the cell is considered empty for the purpose of the 'empty-cells' property.
85    fn is_empty_for_empty_cells(&self) -> bool {
86        self.layout
87            .fragments
88            .iter()
89            .all(|fragment| matches!(fragment, Fragment::AbsoluteOrFixedPositioned(_)))
90    }
91}
92
93/// Information stored during the layout of rows.
94#[derive(Clone, Debug, Default)]
95struct RowLayout {
96    constrained: bool,
97    has_cell_with_span_greater_than_one: bool,
98    percent: Percentage,
99}
100
101/// Information stored during the layout of columns.
102#[derive(Clone, Debug, Default)]
103struct ColumnLayout {
104    constrained: bool,
105    has_originating_cells: bool,
106    content_sizes: ContentSizes,
107    percentage: Option<Percentage>,
108}
109
110fn max_two_optional_percentages(
111    a: Option<Percentage>,
112    b: Option<Percentage>,
113) -> Option<Percentage> {
114    match (a, b) {
115        (Some(a), Some(b)) => Some(Percentage(a.0.max(b.0))),
116        _ => a.or(b),
117    }
118}
119
120impl ColumnLayout {
121    fn incorporate_cell_measure(&mut self, cell_measure: &CellOrTrackMeasure) {
122        self.content_sizes.max_assign(cell_measure.content_sizes);
123        self.percentage = max_two_optional_percentages(self.percentage, cell_measure.percentage);
124    }
125}
126
127impl CollapsedBorder {
128    fn new(style_color: BorderStyleColor, width: Au) -> Self {
129        Self { style_color, width }
130    }
131
132    fn from_layout_style(
133        layout_style: &LayoutStyle,
134        writing_mode: WritingMode,
135    ) -> LogicalSides<Self> {
136        let border_style_color = layout_style.style().border_style_color(writing_mode);
137        let border_width = layout_style.border_width(writing_mode);
138        LogicalSides {
139            inline_start: Self::new(border_style_color.inline_start, border_width.inline_start),
140            inline_end: Self::new(border_style_color.inline_end, border_width.inline_end),
141            block_start: Self::new(border_style_color.block_start, border_width.block_start),
142            block_end: Self::new(border_style_color.block_end, border_width.block_end),
143        }
144    }
145
146    fn max_assign(&mut self, other: &Self) {
147        if *self < *other {
148            *self = other.clone();
149        }
150    }
151
152    fn max_assign_to_slice(&self, slice: &mut [CollapsedBorder]) {
153        for collapsed_border in slice {
154            collapsed_border.max_assign(self)
155        }
156    }
157
158    fn hide(&mut self) {
159        self.style_color = BorderStyleColor::hidden();
160        self.width = Au::zero();
161    }
162}
163
164/// <https://drafts.csswg.org/css-tables/#border-specificity>
165/// > Given two borders styles, the border style having the most specificity is the border style which…
166/// > 1. … has the value "hidden" as border-style, if only one does
167/// > 2. … has the biggest border-width, once converted into css pixels
168/// > 3. … has the border-style which comes first in the following list:
169/// >    double, solid, dashed, dotted, ridge, outset, groove, inset, none
170impl PartialOrd for CollapsedBorder {
171    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
172        let is_hidden = |border: &Self| border.style_color.style == BorderStyle::Hidden;
173        let style_specificity = |border: &Self| match border.style_color.style {
174            BorderStyle::None => 0,
175            BorderStyle::Inset => 1,
176            BorderStyle::Groove => 2,
177            BorderStyle::Outset => 3,
178            BorderStyle::Ridge => 4,
179            BorderStyle::Dotted => 5,
180            BorderStyle::Dashed => 6,
181            BorderStyle::Solid => 7,
182            BorderStyle::Double => 8,
183            BorderStyle::Hidden => 9,
184        };
185        let candidate = (is_hidden(self).cmp(&is_hidden(other)))
186            .then_with(|| self.width.cmp(&other.width))
187            .then_with(|| style_specificity(self).cmp(&style_specificity(other)));
188        if !candidate.is_eq() || self.style_color.color == other.style_color.color {
189            Some(candidate)
190        } else {
191            None
192        }
193    }
194}
195
196impl Eq for CollapsedBorder {}
197
198type CollapsedBorders = LogicalVec2<Vec<CollapsedBorderLine>>;
199
200/// A helper struct that performs the layout of the box tree version
201/// of a table into the fragment tree version. This implements
202/// <https://drafts.csswg.org/css-tables/#table-layout-algorithm>
203pub(crate) struct TableLayout<'a> {
204    table: &'a Table,
205    pbm: PaddingBorderMargin,
206    rows: Vec<RowLayout>,
207    columns: Vec<ColumnLayout>,
208    cell_measures: Vec<Vec<LogicalVec2<CellOrTrackMeasure>>>,
209    /// The calculated width of the table, including space for the grid and also for any
210    /// captions.
211    table_width: Au,
212    /// The table width minus the total horizontal border spacing (if any). This is the
213    /// width that we will be able to allocate to the columns.
214    assignable_width: Au,
215    final_table_height: Au,
216    distributed_column_widths: Vec<Au>,
217    row_sizes: Vec<Au>,
218    /// The accumulated baseline of each row, relative to the top of the row.
219    row_baselines: Vec<Au>,
220    cells_laid_out: Vec<Vec<Option<CellLayout>>>,
221    basis_for_cell_padding_percentage: Au,
222    /// Information about collapsed borders.
223    collapsed_borders: Option<CollapsedBorders>,
224    is_in_fixed_mode: bool,
225}
226
227#[derive(Clone, Debug)]
228struct CellOrTrackMeasure {
229    content_sizes: ContentSizes,
230    percentage: Option<Percentage>,
231}
232
233impl Zero for CellOrTrackMeasure {
234    fn zero() -> Self {
235        Self {
236            content_sizes: ContentSizes::zero(),
237            percentage: None,
238        }
239    }
240
241    fn is_zero(&self) -> bool {
242        self.content_sizes.is_zero() && self.percentage.is_none()
243    }
244}
245
246impl<'a> TableLayout<'a> {
247    fn new(table: &'a Table) -> TableLayout<'a> {
248        // The CSSWG resolved that `auto` and `max-content` inline sizes prevent fixed table mode.
249        // <https://github.com/w3c/csswg-drafts/issues/10937>
250        let style = &table.style;
251        let is_in_fixed_mode = style.get_table().table_layout == TableLayoutMode::Fixed &&
252            !matches!(
253                style.box_size(style.writing_mode).inline,
254                Size::Initial | Size::MaxContent
255            );
256        Self {
257            table,
258            pbm: PaddingBorderMargin::zero(),
259            rows: Vec::new(),
260            columns: Vec::new(),
261            cell_measures: Vec::new(),
262            table_width: Au::zero(),
263            assignable_width: Au::zero(),
264            final_table_height: Au::zero(),
265            distributed_column_widths: Vec::new(),
266            row_sizes: Vec::new(),
267            row_baselines: Vec::new(),
268            cells_laid_out: Vec::new(),
269            basis_for_cell_padding_percentage: Au::zero(),
270            collapsed_borders: None,
271            is_in_fixed_mode,
272        }
273    }
274
275    /// This is an implementation of *Computing Cell Measures* from
276    /// <https://drafts.csswg.org/css-tables/#computing-cell-measures>.
277    pub(crate) fn compute_cell_measures(
278        &mut self,
279        layout_context: &LayoutContext,
280        writing_mode: WritingMode,
281    ) {
282        let row_measures = vec![LogicalVec2::zero(); self.table.size.width];
283        self.cell_measures = vec![row_measures; self.table.size.height];
284
285        for row_index in 0..self.table.size.height {
286            for column_index in 0..self.table.size.width {
287                let cell = match self.table.slots[row_index][column_index] {
288                    TableSlot::Cell(ref cell) => cell,
289                    _ => continue,
290                }
291                .borrow();
292
293                let layout_style = cell.layout_style();
294                let padding = layout_style
295                    .padding(writing_mode)
296                    .percentages_relative_to(Au::zero());
297                let border = self
298                    .get_collapsed_border_widths_for_area(LogicalSides {
299                        inline_start: column_index,
300                        inline_end: column_index + cell.colspan,
301                        block_start: row_index,
302                        block_end: row_index + cell.rowspan,
303                    })
304                    .unwrap_or_else(|| layout_style.border_width(writing_mode));
305
306                let padding_border_sums = LogicalVec2 {
307                    inline: padding.inline_sum() + border.inline_sum(),
308                    block: padding.block_sum() + border.block_sum(),
309                };
310
311                let CellOrColumnOuterSizes {
312                    preferred: preferred_size,
313                    min: min_size,
314                    max: max_size,
315                    percentage: percentage_size,
316                } = CellOrColumnOuterSizes::new(
317                    &cell.base.style,
318                    writing_mode,
319                    &padding_border_sums,
320                    self.is_in_fixed_mode,
321                );
322
323                // <https://drafts.csswg.org/css-tables/#in-fixed-mode>
324                // > When a table-root is laid out in fixed mode, the content of its table-cells is ignored
325                // > for the purpose of width computation, the aggregation algorithm for column sizing considers
326                // > only table-cells belonging to the first row track
327                let inline_measure = if self.is_in_fixed_mode {
328                    if row_index > 0 {
329                        CellOrTrackMeasure::zero()
330                    } else {
331                        CellOrTrackMeasure {
332                            content_sizes: preferred_size.inline.into(),
333                            percentage: percentage_size.inline,
334                        }
335                    }
336                } else {
337                    let inline_content_sizes = cell.inline_content_sizes(layout_context) +
338                        padding_border_sums.inline.into();
339                    assert!(
340                        inline_content_sizes.max_content >= inline_content_sizes.min_content,
341                        "the max-content size should never be smaller than the min-content size"
342                    );
343
344                    // These formulas differ from the spec, but seem to match Gecko and Blink.
345                    let outer_min_content_width = inline_content_sizes
346                        .min_content
347                        .clamp_between_extremums(min_size.inline, max_size.inline);
348                    let outer_max_content_width = if self.columns[column_index].constrained {
349                        inline_content_sizes
350                            .min_content
351                            .max(preferred_size.inline)
352                            .clamp_between_extremums(min_size.inline, max_size.inline)
353                    } else {
354                        inline_content_sizes
355                            .max_content
356                            .max(preferred_size.inline)
357                            .clamp_between_extremums(min_size.inline, max_size.inline)
358                    };
359                    assert!(outer_min_content_width <= outer_max_content_width);
360
361                    CellOrTrackMeasure {
362                        content_sizes: ContentSizes {
363                            min_content: outer_min_content_width,
364                            max_content: outer_max_content_width,
365                        },
366                        percentage: percentage_size.inline,
367                    }
368                };
369
370                // This measure doesn't take into account the `min-content` and `max-content` sizes.
371                // These sizes are incorporated after the first row layout pass, when the block size
372                // of the layout is known.
373                let block_measure = CellOrTrackMeasure {
374                    content_sizes: preferred_size.block.into(),
375                    percentage: percentage_size.block,
376                };
377
378                self.cell_measures[row_index][column_index] = LogicalVec2 {
379                    inline: inline_measure,
380                    block: block_measure,
381                };
382            }
383        }
384    }
385
386    /// Compute the constrainedness of every column in the table.
387    ///
388    /// > A column is constrained if its corresponding table-column-group (if any), its
389    /// > corresponding table-column (if any), or any of the cells spanning only that
390    /// > column has a computed width that is not "auto", and is not a percentage.
391    fn compute_track_constrainedness_and_has_originating_cells(
392        &mut self,
393        writing_mode: WritingMode,
394    ) {
395        self.rows = vec![RowLayout::default(); self.table.size.height];
396        self.columns = vec![ColumnLayout::default(); self.table.size.width];
397
398        let is_length = |size: &Size<ComputedLengthPercentage>| {
399            size.to_numeric().is_some_and(|size| !size.has_percentage())
400        };
401
402        for column_index in 0..self.table.size.width {
403            if let Some(column) = self.table.columns.get(column_index) {
404                let column = column.borrow();
405                if is_length(&column.base.style.box_size(writing_mode).inline) {
406                    self.columns[column_index].constrained = true;
407                    continue;
408                }
409                if let Some(column_group_index) = column.group_index {
410                    let column_group = self.table.column_groups[column_group_index].borrow();
411                    if is_length(&column_group.base.style.box_size(writing_mode).inline) {
412                        self.columns[column_index].constrained = true;
413                        continue;
414                    }
415                }
416            }
417        }
418
419        for row_index in 0..self.table.size.height {
420            if let Some(row) = self.table.rows.get(row_index) {
421                let row = row.borrow();
422                if is_length(&row.base.style.box_size(writing_mode).block) {
423                    self.rows[row_index].constrained = true;
424                    continue;
425                }
426                if let Some(row_group_index) = row.group_index {
427                    let row_group = self.table.row_groups[row_group_index].borrow();
428                    if is_length(&row_group.base.style.box_size(writing_mode).block) {
429                        self.rows[row_index].constrained = true;
430                        continue;
431                    }
432                }
433            }
434        }
435
436        for column_index in 0..self.table.size.width {
437            for row_index in 0..self.table.size.height {
438                let coords = TableSlotCoordinates::new(column_index, row_index);
439                let cell_constrained = match self.table.resolve_first_cell(coords) {
440                    Some(cell) if cell.colspan == 1 => {
441                        cell.base.style.box_size(writing_mode).map(is_length)
442                    },
443                    _ => LogicalVec2::default(),
444                };
445
446                let rowspan_greater_than_1 = match self.table.slots[row_index][column_index] {
447                    TableSlot::Cell(ref cell) => cell.borrow().rowspan > 1,
448                    _ => false,
449                };
450
451                self.rows[row_index].has_cell_with_span_greater_than_one |= rowspan_greater_than_1;
452                self.rows[row_index].constrained |= cell_constrained.block;
453
454                let has_originating_cell =
455                    matches!(self.table.get_slot(coords), Some(TableSlot::Cell(_)));
456                self.columns[column_index].has_originating_cells |= has_originating_cell;
457                self.columns[column_index].constrained |= cell_constrained.inline;
458            }
459        }
460    }
461
462    /// This is an implementation of *Computing Column Measures* from
463    /// <https://drafts.csswg.org/css-tables/#computing-column-measures>.
464    fn compute_column_measures(&mut self, writing_mode: WritingMode) {
465        // Compute the column measures only taking into account cells with colspan == 1.
466        // This is the base case that will be used to iteratively account for cells with
467        // larger colspans afterward.
468        //
469        // > min-content width of a column based on cells of span up to 1
470        // >     The largest of:
471        // >         - the width specified for the column:
472        // >               - the outer min-content width of its corresponding table-column,
473        // >                 if any (and not auto)
474        // >               - the outer min-content width of its corresponding table-column-group, if any
475        // >               - or 0, if there is none
476        // >         - the outer min-content width of each cell that spans the column whose colSpan
477        // >           is 1 (or just the one in the first row in fixed mode) or 0 if there is none
478        // >
479        // > max-content width of a column based on cells of span up to 1
480        // >     The largest of:
481        // >         - the outer max-content width of its corresponding
482        // >           table-column-group, if any
483        // >         - the outer max-content width of its corresponding table-column, if any
484        // >         - the outer max-content width of each cell that spans the column
485        // >           whose colSpan is 1 (or just the one in the first row if in fixed mode) or 0
486        // >           if there is no such cell
487        // >
488        // > intrinsic percentage width of a column based on cells of span up to 1
489        // >     The largest of the percentage contributions of each cell that spans the column whose colSpan is
490        // >     1, of its corresponding table-column (if any), and of its corresponding table-column-group (if
491        // >     any)
492        //
493        // TODO: Take into account `table-column` and `table-column-group` lengths.
494        // TODO: Take into account changes to this computation for fixed table layout.
495        let mut colspan_cell_constraints = Vec::new();
496        for column_index in 0..self.table.size.width {
497            let column = &mut self.columns[column_index];
498
499            let column_measure = self.table.get_column_measure_for_column_at_index(
500                writing_mode,
501                column_index,
502                self.is_in_fixed_mode,
503            );
504            column.content_sizes = column_measure.content_sizes;
505            column.percentage = column_measure.percentage;
506
507            for row_index in 0..self.table.size.height {
508                let coords = TableSlotCoordinates::new(column_index, row_index);
509                let cell_measure = &self.cell_measures[row_index][column_index].inline;
510
511                let cell = match self.table.get_slot(coords) {
512                    Some(TableSlot::Cell(cell)) => cell,
513                    _ => continue,
514                }
515                .borrow();
516
517                if cell.colspan != 1 {
518                    colspan_cell_constraints.push(ColspanToDistribute {
519                        starting_column: column_index,
520                        span: cell.colspan,
521                        content_sizes: cell_measure.content_sizes,
522                        percentage: cell_measure.percentage,
523                    });
524                    continue;
525                }
526
527                // This takes the max of `min_content`, `max_content`, and
528                // intrinsic percentage width as described above.
529                column.incorporate_cell_measure(cell_measure);
530            }
531        }
532
533        // Sort the colspanned cell constraints by their span and starting column.
534        colspan_cell_constraints.sort_by(ColspanToDistribute::comparison_for_sort);
535
536        // Distribute constraints from cells with colspan != 1 to their component columns.
537        self.distribute_colspanned_cells_to_columns(colspan_cell_constraints);
538
539        // > intrinsic percentage width of a column:
540        // > the smaller of:
541        // >   * the intrinsic percentage width of the column based on cells of span up to N,
542        // >     where N is the number of columns in the table
543        // >   * 100% minus the sum of the intrinsic percentage width of all prior columns in
544        // >     the table (further left when direction is "ltr" (right for "rtl"))
545        let mut total_intrinsic_percentage_width = 0.;
546        for column in self.columns.iter_mut() {
547            if let Some(ref mut percentage) = column.percentage {
548                let final_intrinsic_percentage_width =
549                    percentage.0.min(1. - total_intrinsic_percentage_width);
550                total_intrinsic_percentage_width += final_intrinsic_percentage_width;
551                *percentage = Percentage(final_intrinsic_percentage_width);
552            }
553        }
554    }
555
556    fn distribute_colspanned_cells_to_columns(
557        &mut self,
558        colspan_cell_constraints: Vec<ColspanToDistribute>,
559    ) {
560        for colspan_cell_constraints in colspan_cell_constraints {
561            self.distribute_colspanned_cell_to_columns(colspan_cell_constraints);
562        }
563    }
564
565    /// Distribute the inline size from a cell with colspan != 1 to the columns that it spans.
566    /// This is heavily inspired by the approach that Chromium takes in redistributing colspan
567    /// cells' inline size to columns (`DistributeColspanCellToColumnsAuto` in
568    /// `blink/renderer/core/layout/table/table_layout_utils.cc`).
569    fn distribute_colspanned_cell_to_columns(
570        &mut self,
571        colspan_cell_constraints: ColspanToDistribute,
572    ) {
573        let border_spacing = self.table.border_spacing().inline;
574        let column_range = colspan_cell_constraints.range();
575        let column_count = column_range.len();
576        let total_border_spacing =
577            border_spacing.scale_by((colspan_cell_constraints.span - 1) as f32);
578
579        let mut percent_columns_count = 0;
580        let mut columns_percent_sum = 0.;
581        let mut columns_non_percent_max_inline_size_sum = Au::zero();
582        for column in self.columns[column_range.clone()].iter() {
583            if let Some(percentage) = column.percentage {
584                percent_columns_count += 1;
585                columns_percent_sum += percentage.0;
586            } else {
587                columns_non_percent_max_inline_size_sum += column.content_sizes.max_content;
588            }
589        }
590
591        let colspan_percentage = colspan_cell_constraints.percentage.unwrap_or_default();
592        let surplus_percent = colspan_percentage.0 - columns_percent_sum;
593        if surplus_percent > 0. && column_count > percent_columns_count {
594            for column in self.columns[column_range.clone()].iter_mut() {
595                if column.percentage.is_some() {
596                    continue;
597                }
598
599                let ratio = if columns_non_percent_max_inline_size_sum.is_zero() {
600                    1. / ((column_count - percent_columns_count) as f32)
601                } else {
602                    column.content_sizes.max_content.to_f32_px() /
603                        columns_non_percent_max_inline_size_sum.to_f32_px()
604                };
605                column.percentage = Some(Percentage(surplus_percent * ratio));
606            }
607        }
608
609        let colspan_cell_min_size = (colspan_cell_constraints.content_sizes.min_content -
610            total_border_spacing)
611            .max(Au::zero());
612        let distributed_minimum = Self::distribute_width_to_columns(
613            colspan_cell_min_size,
614            &self.columns[column_range.clone()],
615        );
616        {
617            let column_span = &mut self.columns[colspan_cell_constraints.range()];
618            for (column, minimum_size) in column_span.iter_mut().zip(distributed_minimum) {
619                column.content_sizes.min_content.max_assign(minimum_size);
620            }
621        }
622
623        let colspan_cell_max_size = (colspan_cell_constraints.content_sizes.max_content -
624            total_border_spacing)
625            .max(Au::zero());
626        let distributed_maximum = Self::distribute_width_to_columns(
627            colspan_cell_max_size,
628            &self.columns[colspan_cell_constraints.range()],
629        );
630        {
631            let column_span = &mut self.columns[colspan_cell_constraints.range()];
632            for (column, maximum_size) in column_span.iter_mut().zip(distributed_maximum) {
633                column
634                    .content_sizes
635                    .max_content
636                    .max_assign(maximum_size.max(column.content_sizes.min_content));
637            }
638        }
639    }
640
641    fn compute_measures(&mut self, layout_context: &LayoutContext, writing_mode: WritingMode) {
642        self.compute_track_constrainedness_and_has_originating_cells(writing_mode);
643        self.compute_cell_measures(layout_context, writing_mode);
644        self.compute_column_measures(writing_mode);
645    }
646
647    /// Compute the GRIDMIN and GRIDMAX.
648    fn compute_grid_min_max(&self) -> ContentSizes {
649        // https://drafts.csswg.org/css-tables/#gridmin:
650        // > The row/column-grid width minimum (GRIDMIN) width is the sum of the min-content width of
651        // > all the columns plus cell spacing or borders.
652        // https://drafts.csswg.org/css-tables/#gridmax:
653        // > The row/column-grid width maximum (GRIDMAX) width is the sum of the max-content width of
654        // > all the columns plus cell spacing or borders.
655        //
656        // The specification doesn't say what to do with columns with percentages, so we follow the
657        // approach that LayoutNG takes here. We try to figure out the size contribution
658        // of the percentage columns, by working backward to find the calculated
659        // percentage of non-percent columns and using that to calculate the size of the
660        // percent columns.
661        let mut largest_percentage_column_max_size = Au::zero();
662        let mut percent_sum = 0.;
663        let mut non_percent_columns_max_sum = Au::zero();
664        let mut grid_min_max = ContentSizes::zero();
665        for column in self.columns.iter() {
666            match column.percentage {
667                Some(percentage) if !percentage.is_zero() => {
668                    largest_percentage_column_max_size.max_assign(
669                        column
670                            .content_sizes
671                            .max_content
672                            .scale_by(1.0 / percentage.0),
673                    );
674                    percent_sum += percentage.0;
675                },
676                _ => {
677                    non_percent_columns_max_sum += column.content_sizes.max_content;
678                },
679            }
680
681            grid_min_max += column.content_sizes;
682        }
683
684        grid_min_max
685            .max_content
686            .max_assign(largest_percentage_column_max_size);
687
688        // Do not take into account percentage of columns when this table is a descendant
689        // of a flex, grid, or table container. These modes with percentage columns can
690        // cause inline width to become infinitely wide.
691        if !percent_sum.is_zero() &&
692            self.table
693                .percentage_columns_allowed_for_inline_content_sizes
694        {
695            let total_inline_size =
696                non_percent_columns_max_sum.scale_by(1.0 / (1.0 - percent_sum.min(1.0)));
697            grid_min_max.max_content.max_assign(total_inline_size);
698        }
699
700        assert!(
701            grid_min_max.min_content <= grid_min_max.max_content,
702            "GRIDMAX should never be smaller than GRIDMIN {:?}",
703            grid_min_max
704        );
705
706        let inline_border_spacing = self.table.total_border_spacing().inline;
707        grid_min_max.min_content += inline_border_spacing;
708        grid_min_max.max_content += inline_border_spacing;
709        grid_min_max
710    }
711
712    /// Compute CAPMIN: <https://drafts.csswg.org/css-tables/#capmin>
713    fn compute_caption_minimum_inline_size(&self, layout_context: &LayoutContext) -> Au {
714        let containing_block = IndefiniteContainingBlock {
715            size: LogicalVec2::default(),
716            style: &self.table.style,
717        };
718        self.table
719            .captions
720            .iter()
721            .map(|caption| {
722                caption
723                    .borrow()
724                    .context
725                    .outer_inline_content_sizes(
726                        layout_context,
727                        &containing_block,
728                        &LogicalVec2::zero(),
729                        false, /* auto_block_size_stretches_to_containing_block */
730                    )
731                    .sizes
732                    .min_content
733            })
734            .max()
735            .unwrap_or_default()
736    }
737
738    fn compute_table_width(&mut self, containing_block_for_children: &ContainingBlock) {
739        // This assumes that the parent formatting context computed the correct inline size
740        // of the table, by enforcing its min-content size as a minimum.
741        // This should be roughly equivalent to what the spec calls "used width of a table".
742        // https://drafts.csswg.org/css-tables/#used-width-of-table
743        self.table_width = containing_block_for_children.size.inline;
744
745        // > The assignable table width is the used width of the table minus the total horizontal
746        // > border spacing (if any). This is the width that we will be able to allocate to the
747        // > columns.
748        self.assignable_width = self.table_width - self.table.total_border_spacing().inline;
749
750        // This is the amount that we will use to resolve percentages in the padding of cells.
751        // It matches what Gecko and Blink do, though they disagree when there is a big caption.
752        self.basis_for_cell_padding_percentage =
753            self.table_width - self.table.border_spacing().inline * 2;
754    }
755
756    /// Distribute width to columns, performing step 2.4 of table layout from
757    /// <https://drafts.csswg.org/css-tables/#table-layout-algorithm>.
758    fn distribute_width_to_columns(target_inline_size: Au, columns: &[ColumnLayout]) -> Vec<Au> {
759        // No need to do anything if there is no column.
760        // Note that tables without rows may still have columns.
761        if columns.is_empty() {
762            return Vec::new();
763        }
764
765        // > First, each column of the table is assigned a sizing type:
766        // >  * percent-column: a column whose any constraint is defined to use a percentage only
767        // >                    (with a value different from 0%)
768        // >  * pixel-column: column whose any constraint is defined to use a defined length only
769        // >                  (and is not a percent-column)
770        // >  * auto-column: any other column
771        // >
772        // > Then, valid sizing methods are to be assigned to the columns by sizing type, yielding
773        // > the following sizing-guesses:
774        // >
775        // > * The min-content sizing-guess is the set of column width assignments where
776        // >   each column is assigned its min-content width.
777        // > * The min-content-percentage sizing-guess is the set of column width assignments where:
778        // >       * each percent-column is assigned the larger of:
779        // >           * its intrinsic percentage width times the assignable width and
780        // >           * its min-content width.
781        // >       * all other columns are assigned their min-content width.
782        // > * The min-content-specified sizing-guess is the set of column width assignments where:
783        // >       * each percent-column is assigned the larger of:
784        // >           * its intrinsic percentage width times the assignable width and
785        // >           * its min-content width
786        // >       * any other column that is constrained is assigned its max-content width
787        // >       * all other columns are assigned their min-content width.
788        // > * The max-content sizing-guess is the set of column width assignments where:
789        // >       * each percent-column is assigned the larger of:
790        // >           * its intrinsic percentage width times the assignable width and
791        // >           * its min-content width
792        // >       * all other columns are assigned their max-content width.
793        let mut min_content_sizing_guesses = Vec::new();
794        let mut min_content_percentage_sizing_guesses = Vec::new();
795        let mut min_content_specified_sizing_guesses = Vec::new();
796        let mut max_content_sizing_guesses = Vec::new();
797
798        for column in columns {
799            let min_content_width = column.content_sizes.min_content;
800            let max_content_width = column.content_sizes.max_content;
801            let constrained = column.constrained;
802
803            let (
804                min_content_percentage_sizing_guess,
805                min_content_specified_sizing_guess,
806                max_content_sizing_guess,
807            ) = if let Some(percentage) = column.percentage {
808                let resolved = target_inline_size.scale_by(percentage.0);
809                let percent_guess = min_content_width.max(resolved);
810                (percent_guess, percent_guess, percent_guess)
811            } else if constrained {
812                (min_content_width, max_content_width, max_content_width)
813            } else {
814                (min_content_width, min_content_width, max_content_width)
815            };
816
817            min_content_sizing_guesses.push(min_content_width);
818            min_content_percentage_sizing_guesses.push(min_content_percentage_sizing_guess);
819            min_content_specified_sizing_guesses.push(min_content_specified_sizing_guess);
820            max_content_sizing_guesses.push(max_content_sizing_guess);
821        }
822
823        // > If the assignable table width is less than or equal to the max-content sizing-guess, the
824        // > used widths of the columns must be the linear combination (with weights adding to 1) of
825        // > the two consecutive sizing-guesses whose width sums bound the available width.
826        //
827        // > Otherwise, the used widths of the columns are the result of starting from the max-content
828        // > sizing-guess and distributing the excess width to the columns of the table according to
829        // > the rules for distributing excess width to columns (for used width).
830        fn sum(guesses: &[Au]) -> Au {
831            guesses.iter().fold(Au::zero(), |sum, guess| sum + *guess)
832        }
833
834        let max_content_sizing_sum = sum(&max_content_sizing_guesses);
835        if target_inline_size >= max_content_sizing_sum {
836            Self::distribute_extra_width_to_columns(
837                columns,
838                &mut max_content_sizing_guesses,
839                max_content_sizing_sum,
840                target_inline_size,
841            );
842            return max_content_sizing_guesses;
843        }
844        let min_content_specified_sizing_sum = sum(&min_content_specified_sizing_guesses);
845        if target_inline_size == min_content_specified_sizing_sum {
846            return min_content_specified_sizing_guesses;
847        }
848        let min_content_percentage_sizing_sum = sum(&min_content_percentage_sizing_guesses);
849        if target_inline_size == min_content_percentage_sizing_sum {
850            return min_content_percentage_sizing_guesses;
851        }
852        let min_content_sizes_sum = sum(&min_content_sizing_guesses);
853        if target_inline_size <= min_content_sizes_sum {
854            return min_content_sizing_guesses;
855        }
856
857        let bounds = |sum_a, sum_b| target_inline_size > sum_a && target_inline_size < sum_b;
858
859        let blend = |a: &[Au], sum_a: Au, b: &[Au], sum_b: Au| {
860            // First convert the Au units to f32 in order to do floating point division.
861            let weight_a = (target_inline_size - sum_b).to_f32_px() / (sum_a - sum_b).to_f32_px();
862            let weight_b = 1.0 - weight_a;
863
864            let mut remaining_assignable_width = target_inline_size;
865            let mut widths: Vec<Au> = a
866                .iter()
867                .zip(b.iter())
868                .map(|(guess_a, guess_b)| {
869                    let column_width = guess_a.scale_by(weight_a) + guess_b.scale_by(weight_b);
870                    // Clamp to avoid exceeding the assignable width. This could otherwise
871                    // happen when dealing with huge values whose sum is clamped to MAX_AU.
872                    let column_width = column_width.min(remaining_assignable_width);
873                    remaining_assignable_width -= column_width;
874                    column_width
875                })
876                .collect();
877
878            if !remaining_assignable_width.is_zero() {
879                // The computations above can introduce floating-point imprecisions.
880                // Since these errors are very small (1Au), it's fine to simply adjust
881                // the first column such that the total width matches the assignable width
882                debug_assert!(
883                    remaining_assignable_width >= Au::zero(),
884                    "Sum of columns shouldn't exceed the assignable table width"
885                );
886                debug_assert!(
887                    remaining_assignable_width <= Au::new(widths.len() as i32),
888                    "A deviation of more than one Au per column is unlikely to be caused by float imprecision"
889                );
890
891                // We checked if the table had columns at the top of the function, so there
892                // always is a first column
893                widths[0] += remaining_assignable_width;
894            }
895
896            debug_assert!(widths.iter().sum::<Au>() == target_inline_size);
897
898            widths
899        };
900
901        if bounds(min_content_sizes_sum, min_content_percentage_sizing_sum) {
902            return blend(
903                &min_content_sizing_guesses,
904                min_content_sizes_sum,
905                &min_content_percentage_sizing_guesses,
906                min_content_percentage_sizing_sum,
907            );
908        }
909
910        if bounds(
911            min_content_percentage_sizing_sum,
912            min_content_specified_sizing_sum,
913        ) {
914            return blend(
915                &min_content_percentage_sizing_guesses,
916                min_content_percentage_sizing_sum,
917                &min_content_specified_sizing_guesses,
918                min_content_specified_sizing_sum,
919            );
920        }
921
922        assert!(bounds(
923            min_content_specified_sizing_sum,
924            max_content_sizing_sum
925        ));
926        blend(
927            &min_content_specified_sizing_guesses,
928            min_content_specified_sizing_sum,
929            &max_content_sizing_guesses,
930            max_content_sizing_sum,
931        )
932    }
933
934    /// This is an implementation of *Distributing excess width to columns* from
935    /// <https://drafts.csswg.org/css-tables/#distributing-width-to-columns>.
936    fn distribute_extra_width_to_columns(
937        columns: &[ColumnLayout],
938        column_sizes: &mut [Au],
939        column_sizes_sum: Au,
940        assignable_width: Au,
941    ) {
942        let all_columns = 0..columns.len();
943        let extra_inline_size = assignable_width - column_sizes_sum;
944
945        let has_originating_cells =
946            |column_index: &usize| columns[*column_index].has_originating_cells;
947        let is_constrained = |column_index: &usize| columns[*column_index].constrained;
948        let is_unconstrained = |column_index: &usize| !is_constrained(column_index);
949        let has_percent_greater_than_zero = |column_index: &usize| {
950            columns[*column_index]
951                .percentage
952                .is_some_and(|percentage| percentage.0 > 0.)
953        };
954        let has_percent_zero = |column_index: &usize| !has_percent_greater_than_zero(column_index);
955        let has_max_content =
956            |column_index: &usize| !columns[*column_index].content_sizes.max_content.is_zero();
957
958        let max_content_sum = |column_index: usize| columns[column_index].content_sizes.max_content;
959
960        // > If there are non-constrained columns that have originating cells with intrinsic
961        // > percentage width of 0% and with nonzero max-content width (aka the columns allowed to
962        // > grow by this rule), the distributed widths of the columns allowed to grow by this rule
963        // > are increased in proportion to max-content width so the total increase adds to the
964        // > excess width.
965        let unconstrained_max_content_columns = all_columns
966            .clone()
967            .filter(is_unconstrained)
968            .filter(has_originating_cells)
969            .filter(has_percent_zero)
970            .filter(has_max_content);
971        let total_max_content_width = unconstrained_max_content_columns
972            .clone()
973            .map(max_content_sum)
974            .fold(Au::zero(), |a, b| a + b);
975        if !total_max_content_width.is_zero() {
976            for column_index in unconstrained_max_content_columns {
977                column_sizes[column_index] += extra_inline_size.scale_by(
978                    columns[column_index].content_sizes.max_content.to_f32_px() /
979                        total_max_content_width.to_f32_px(),
980                );
981            }
982            return;
983        }
984
985        // > Otherwise, if there are non-constrained columns that have originating cells with intrinsic
986        // > percentage width of 0% (aka the columns allowed to grow by this rule, which thanks to the
987        // > previous rule must have zero max-content width), the distributed widths of the columns
988        // > allowed to grow by this rule are increased by equal amounts so the total increase adds to
989        // > the excess width.V
990        let unconstrained_no_percent_columns = all_columns
991            .clone()
992            .filter(is_unconstrained)
993            .filter(has_originating_cells)
994            .filter(has_percent_zero);
995        let total_unconstrained_no_percent = unconstrained_no_percent_columns.clone().count();
996        if total_unconstrained_no_percent > 0 {
997            let extra_space_per_column =
998                extra_inline_size.scale_by(1.0 / total_unconstrained_no_percent as f32);
999            for column_index in unconstrained_no_percent_columns {
1000                column_sizes[column_index] += extra_space_per_column;
1001            }
1002            return;
1003        }
1004
1005        // > Otherwise, if there are constrained columns with intrinsic percentage width of 0% and
1006        // > with nonzero max-content width (aka the columns allowed to grow by this rule, which, due
1007        // > to other rules, must have originating cells), the distributed widths of the columns
1008        // > allowed to grow by this rule are increased in proportion to max-content width so the
1009        // > total increase adds to the excess width.
1010        let constrained_max_content_columns = all_columns
1011            .clone()
1012            .filter(is_constrained)
1013            .filter(has_originating_cells)
1014            .filter(has_percent_zero)
1015            .filter(has_max_content);
1016        let total_max_content_width = constrained_max_content_columns
1017            .clone()
1018            .map(max_content_sum)
1019            .fold(Au::zero(), |a, b| a + b);
1020        if !total_max_content_width.is_zero() {
1021            for column_index in constrained_max_content_columns {
1022                column_sizes[column_index] += extra_inline_size.scale_by(
1023                    columns[column_index].content_sizes.max_content.to_f32_px() /
1024                        total_max_content_width.to_f32_px(),
1025                );
1026            }
1027            return;
1028        }
1029
1030        // > Otherwise, if there are columns with intrinsic percentage width greater than 0% (aka the
1031        // > columns allowed to grow by this rule, which, due to other rules, must have originating
1032        // > cells), the distributed widths of the columns allowed to grow by this rule are increased
1033        // > in proportion to intrinsic percentage width so the total increase adds to the excess
1034        // > width.
1035        let columns_with_percentage = all_columns.clone().filter(has_percent_greater_than_zero);
1036        let total_percent = columns_with_percentage
1037            .clone()
1038            .map(|column_index| columns[column_index].percentage.unwrap_or_default().0)
1039            .sum::<f32>();
1040        if total_percent > 0. {
1041            for column_index in columns_with_percentage {
1042                let column_percentage = columns[column_index].percentage.unwrap_or_default();
1043                column_sizes[column_index] +=
1044                    extra_inline_size.scale_by(column_percentage.0 / total_percent);
1045            }
1046            return;
1047        }
1048
1049        // > Otherwise, if there is any such column, the distributed widths of all columns that have
1050        // > originating cells are increased by equal amounts so the total increase adds to the excess
1051        // > width.
1052        let has_originating_cells_columns = all_columns.clone().filter(has_originating_cells);
1053        let total_has_originating_cells = has_originating_cells_columns.clone().count();
1054        if total_has_originating_cells > 0 {
1055            let extra_space_per_column =
1056                extra_inline_size.scale_by(1.0 / total_has_originating_cells as f32);
1057            for column_index in has_originating_cells_columns {
1058                column_sizes[column_index] += extra_space_per_column;
1059            }
1060            return;
1061        }
1062
1063        // > Otherwise, the distributed widths of all columns are increased by equal amounts so the
1064        // total increase adds to the excess width.
1065        let extra_space_for_all_columns = extra_inline_size.scale_by(1.0 / columns.len() as f32);
1066        for guess in column_sizes.iter_mut() {
1067            *guess += extra_space_for_all_columns;
1068        }
1069    }
1070
1071    /// This is an implementation of *Row layout (first pass)* from
1072    /// <https://drafts.csswg.org/css-tables/#row-layout>.
1073    fn layout_cells_in_row(
1074        &mut self,
1075        layout_context: &LayoutContext,
1076        containing_block_for_table: &ContainingBlock,
1077    ) {
1078        let layout_table_slot = |coordinate: TableSlotCoordinates, slot: &TableSlot| {
1079            let TableSlot::Cell(cell) = slot else {
1080                return None;
1081            };
1082
1083            let cell = cell.borrow();
1084            let area = LogicalSides {
1085                inline_start: coordinate.x,
1086                inline_end: coordinate.x + cell.colspan,
1087                block_start: coordinate.y,
1088                block_end: coordinate.y + cell.rowspan,
1089            };
1090            let layout_style = cell.layout_style();
1091            let border = self
1092                .get_collapsed_border_widths_for_area(area)
1093                .unwrap_or_else(|| {
1094                    layout_style.border_width(containing_block_for_table.style.writing_mode)
1095                });
1096            let padding: LogicalSides<Au> = layout_style
1097                .padding(containing_block_for_table.style.writing_mode)
1098                .percentages_relative_to(self.basis_for_cell_padding_percentage);
1099            let inline_border_padding_sum = border.inline_sum() + padding.inline_sum();
1100            let border_spacing_spanned =
1101                self.table.border_spacing().inline * (cell.colspan - 1) as i32;
1102
1103            let mut total_cell_width: Au = (coordinate.x..coordinate.x + cell.colspan)
1104                .map(|column_index| self.distributed_column_widths[column_index])
1105                .sum::<Au>() -
1106                inline_border_padding_sum +
1107                border_spacing_spanned;
1108            total_cell_width = total_cell_width.max(Au::zero());
1109
1110            let containing_block_for_children = ContainingBlock {
1111                size: ContainingBlockSize {
1112                    inline: total_cell_width,
1113                    block: SizeConstraint::default(),
1114                },
1115                style: &cell.base.style,
1116            };
1117
1118            let mut positioning_context = PositioningContext::default();
1119            let layout = cell.contents.layout(
1120                layout_context,
1121                &mut positioning_context,
1122                &containing_block_for_children,
1123            );
1124
1125            Some(CellLayout {
1126                layout,
1127                padding,
1128                border,
1129                positioning_context,
1130            })
1131        };
1132
1133        self.cells_laid_out = if layout_context.use_rayon {
1134            self.table
1135                .slots
1136                .par_iter()
1137                .enumerate()
1138                .map(|(row_index, row_slots)| {
1139                    row_slots
1140                        .par_iter()
1141                        .enumerate()
1142                        .map(|(column_index, slot)| {
1143                            layout_table_slot(
1144                                TableSlotCoordinates::new(column_index, row_index),
1145                                slot,
1146                            )
1147                        })
1148                        .collect()
1149                })
1150                .collect()
1151        } else {
1152            self.table
1153                .slots
1154                .iter()
1155                .enumerate()
1156                .map(|(row_index, row_slots)| {
1157                    row_slots
1158                        .iter()
1159                        .enumerate()
1160                        .map(|(column_index, slot)| {
1161                            layout_table_slot(
1162                                TableSlotCoordinates::new(column_index, row_index),
1163                                slot,
1164                            )
1165                        })
1166                        .collect()
1167                })
1168                .collect()
1169        };
1170
1171        // Now go through all cells laid out and update the cell measure based on the size
1172        // determined during layout.
1173        for row_index in 0..self.table.size.height {
1174            for column_index in 0..self.table.size.width {
1175                let Some(layout) = &self.cells_laid_out[row_index][column_index] else {
1176                    continue;
1177                };
1178
1179                self.cell_measures[row_index][column_index]
1180                    .block
1181                    .content_sizes
1182                    .max_assign(layout.outer_block_size().into());
1183            }
1184        }
1185    }
1186
1187    /// Do the first layout of a table row, after laying out the cells themselves. This is
1188    /// more or less and implementation of <https://drafts.csswg.org/css-tables/#row-layout>.
1189    fn do_first_row_layout(&mut self, writing_mode: WritingMode) -> Vec<Au> {
1190        let mut row_sizes = (0..self.table.size.height)
1191            .map(|row_index| {
1192                let (mut max_ascent, mut max_descent, mut max_row_height) =
1193                    (Au::zero(), Au::zero(), Au::zero());
1194
1195                for column_index in 0..self.table.size.width {
1196                    let cell = match self.table.slots[row_index][column_index] {
1197                        TableSlot::Cell(ref cell) => cell,
1198                        _ => continue,
1199                    };
1200
1201                    let layout = match self.cells_laid_out[row_index][column_index] {
1202                        Some(ref layout) => layout,
1203                        None => {
1204                            warn!(
1205                                "Did not find a layout at a slot index with an originating cell."
1206                            );
1207                            continue;
1208                        },
1209                    };
1210
1211                    let cell = cell.borrow();
1212                    let outer_block_size = layout.outer_block_size();
1213                    if cell.rowspan == 1 {
1214                        max_row_height.max_assign(outer_block_size);
1215                    }
1216
1217                    if cell.effective_vertical_align() == VerticalAlignKeyword::Baseline {
1218                        let ascent = layout.ascent();
1219                        let border_padding_start =
1220                            layout.border.block_start + layout.padding.block_start;
1221                        let border_padding_end = layout.border.block_end + layout.padding.block_end;
1222                        max_ascent.max_assign(ascent + border_padding_start);
1223
1224                        // Only take into account the descent of this cell if doesn't span
1225                        // rows. The descent portion of the cell in cells that do span rows
1226                        // may extend into other rows.
1227                        if cell.rowspan == 1 {
1228                            max_descent.max_assign(
1229                                layout.layout.content_block_size - ascent + border_padding_end,
1230                            );
1231                        }
1232                    }
1233                }
1234                self.row_baselines.push(max_ascent);
1235                max_row_height.max(max_ascent + max_descent)
1236            })
1237            .collect();
1238        self.calculate_row_sizes_after_first_layout(&mut row_sizes, writing_mode);
1239        row_sizes
1240    }
1241
1242    #[allow(clippy::ptr_arg)] // Needs to be a vec because of the function above
1243    /// After doing layout of table rows, calculate final row size and distribute space across
1244    /// rowspanned cells. This follows the implementation of LayoutNG and the priority
1245    /// agorithm described at <https://github.com/w3c/csswg-drafts/issues/4418>.
1246    fn calculate_row_sizes_after_first_layout(
1247        &mut self,
1248        row_sizes: &mut Vec<Au>,
1249        writing_mode: WritingMode,
1250    ) {
1251        let mut cells_to_distribute = Vec::new();
1252        let mut total_percentage = 0.;
1253        #[allow(clippy::needless_range_loop)] // It makes sense to use it here
1254        for row_index in 0..self.table.size.height {
1255            let row_measure = self
1256                .table
1257                .get_row_measure_for_row_at_index(writing_mode, row_index);
1258            row_sizes[row_index].max_assign(row_measure.content_sizes.min_content);
1259
1260            let mut percentage = row_measure.percentage.unwrap_or_default().0;
1261            for column_index in 0..self.table.size.width {
1262                let cell_percentage = self.cell_measures[row_index][column_index]
1263                    .block
1264                    .percentage
1265                    .unwrap_or_default()
1266                    .0;
1267                percentage = percentage.max(cell_percentage);
1268
1269                let cell_measure = &self.cell_measures[row_index][column_index].block;
1270                let cell = match self.table.slots[row_index][column_index] {
1271                    TableSlot::Cell(ref cell) if cell.borrow().rowspan > 1 => cell,
1272                    TableSlot::Cell(_) => {
1273                        // If this is an originating cell, that isn't spanning, then we make sure the row is
1274                        // at least big enough to hold the cell.
1275                        row_sizes[row_index].max_assign(cell_measure.content_sizes.max_content);
1276                        continue;
1277                    },
1278                    _ => continue,
1279                };
1280
1281                cells_to_distribute.push(RowspanToDistribute {
1282                    coordinates: TableSlotCoordinates::new(column_index, row_index),
1283                    cell: cell.borrow(),
1284                    measure: cell_measure,
1285                });
1286            }
1287
1288            self.rows[row_index].percent = Percentage(percentage.min(1. - total_percentage));
1289            total_percentage += self.rows[row_index].percent.0;
1290        }
1291
1292        cells_to_distribute.sort_by(|a, b| {
1293            if a.range() == b.range() {
1294                return a
1295                    .measure
1296                    .content_sizes
1297                    .min_content
1298                    .cmp(&b.measure.content_sizes.min_content);
1299            }
1300            if a.fully_encloses(b) {
1301                return std::cmp::Ordering::Greater;
1302            }
1303            if b.fully_encloses(a) {
1304                return std::cmp::Ordering::Less;
1305            }
1306            a.coordinates.y.cmp(&b.coordinates.y)
1307        });
1308
1309        for rowspan_to_distribute in cells_to_distribute {
1310            let rows_spanned = rowspan_to_distribute.range();
1311            let current_rows_size: Au = rows_spanned.clone().map(|index| row_sizes[index]).sum();
1312            let border_spacing_spanned =
1313                self.table.border_spacing().block * (rows_spanned.len() - 1) as i32;
1314            let excess_size = (rowspan_to_distribute.measure.content_sizes.min_content -
1315                current_rows_size -
1316                border_spacing_spanned)
1317                .max(Au::zero());
1318
1319            self.distribute_extra_size_to_rows(
1320                excess_size,
1321                rows_spanned,
1322                row_sizes,
1323                None,
1324                true, /* rowspan_distribution */
1325            );
1326        }
1327    }
1328
1329    /// An implementation of the same extra block size distribution algorithm used in
1330    /// LayoutNG and described at <https://github.com/w3c/csswg-drafts/issues/4418>.
1331    fn distribute_extra_size_to_rows(
1332        &self,
1333        mut excess_size: Au,
1334        track_range: Range<usize>,
1335        track_sizes: &mut [Au],
1336        percentage_resolution_size: Option<Au>,
1337        rowspan_distribution: bool,
1338    ) {
1339        if excess_size.is_zero() {
1340            return;
1341        }
1342
1343        let is_constrained = |track_index: &usize| self.rows[*track_index].constrained;
1344        let is_unconstrained = |track_index: &usize| !is_constrained(track_index);
1345        let is_empty: Vec<bool> = track_sizes.iter().map(|size| size.is_zero()).collect();
1346        let is_not_empty = |track_index: &usize| !is_empty[*track_index];
1347        let other_row_that_starts_a_rowspan = |track_index: &usize| {
1348            *track_index != track_range.start &&
1349                self.rows[*track_index].has_cell_with_span_greater_than_one
1350        };
1351
1352        // If we have a table height (not during rowspan distribution), first distribute to rows
1353        // that have percentage sizes proportionally to the size missing to reach the percentage
1354        // of table height required.
1355        if let Some(percentage_resolution_size) = percentage_resolution_size {
1356            let get_percent_block_size_deficit = |row_index: usize, track_size: Au| {
1357                let size_needed_for_percent =
1358                    percentage_resolution_size.scale_by(self.rows[row_index].percent.0);
1359                (size_needed_for_percent - track_size).max(Au::zero())
1360            };
1361            let percent_block_size_deficit: Au = track_range
1362                .clone()
1363                .map(|index| get_percent_block_size_deficit(index, track_sizes[index]))
1364                .sum();
1365            let percent_distributable_block_size = percent_block_size_deficit.min(excess_size);
1366            if percent_distributable_block_size > Au::zero() {
1367                for track_index in track_range.clone() {
1368                    let row_deficit =
1369                        get_percent_block_size_deficit(track_index, track_sizes[track_index]);
1370                    if row_deficit > Au::zero() {
1371                        let ratio =
1372                            row_deficit.to_f32_px() / percent_block_size_deficit.to_f32_px();
1373                        let size = percent_distributable_block_size.scale_by(ratio);
1374                        track_sizes[track_index] += size;
1375                        excess_size -= size;
1376                    }
1377                }
1378            }
1379        }
1380
1381        // If this is rowspan distribution and there are rows other than the first row that have a
1382        // cell with rowspan > 1, distribute the extra space equally to those rows.
1383        if rowspan_distribution {
1384            let rows_that_start_rowspan: Vec<usize> = track_range
1385                .clone()
1386                .filter(other_row_that_starts_a_rowspan)
1387                .collect();
1388            if !rows_that_start_rowspan.is_empty() {
1389                let scale = 1.0 / rows_that_start_rowspan.len() as f32;
1390                for track_index in rows_that_start_rowspan.iter() {
1391                    track_sizes[*track_index] += excess_size.scale_by(scale);
1392                }
1393                return;
1394            }
1395        }
1396
1397        // If there are unconstrained non-empty rows, grow them all proportionally to their current size.
1398        let unconstrained_non_empty_rows: Vec<usize> = track_range
1399            .clone()
1400            .filter(is_unconstrained)
1401            .filter(is_not_empty)
1402            .collect();
1403        if !unconstrained_non_empty_rows.is_empty() {
1404            let total_size: Au = unconstrained_non_empty_rows
1405                .iter()
1406                .map(|index| track_sizes[*index])
1407                .sum();
1408            for track_index in unconstrained_non_empty_rows.iter() {
1409                let scale = track_sizes[*track_index].to_f32_px() / total_size.to_f32_px();
1410                track_sizes[*track_index] += excess_size.scale_by(scale);
1411            }
1412            return;
1413        }
1414
1415        let (non_empty_rows, empty_rows): (Vec<usize>, Vec<usize>) =
1416            track_range.clone().partition(is_not_empty);
1417        let only_have_empty_rows = empty_rows.len() == track_range.len();
1418        if !empty_rows.is_empty() {
1419            // If this is rowspan distribution and there are only empty rows, just grow the
1420            // last one.
1421            if rowspan_distribution && only_have_empty_rows {
1422                track_sizes[*empty_rows.last().unwrap()] += excess_size;
1423                return;
1424            }
1425
1426            // Otherwise, if we only have empty rows or if all the non-empty rows are constrained,
1427            // then grow the empty rows.
1428            let non_empty_rows_all_constrained = !non_empty_rows.iter().any(is_unconstrained);
1429            if only_have_empty_rows || non_empty_rows_all_constrained {
1430                // If there are both unconstrained and constrained empty rows, only increase the
1431                // size of the unconstrained ones, otherwise increase the size of all empty rows.
1432                let mut rows_to_grow = &empty_rows;
1433                let unconstrained_empty_rows: Vec<usize> = rows_to_grow
1434                    .iter()
1435                    .copied()
1436                    .filter(is_unconstrained)
1437                    .collect();
1438                if !unconstrained_empty_rows.is_empty() {
1439                    rows_to_grow = &unconstrained_empty_rows;
1440                }
1441
1442                // All empty rows that will grow equally.
1443                let scale = 1.0 / rows_to_grow.len() as f32;
1444                for track_index in rows_to_grow.iter() {
1445                    track_sizes[*track_index] += excess_size.scale_by(scale);
1446                }
1447                return;
1448            }
1449        }
1450
1451        // If there are non-empty rows, they all grow in proportion to their current size,
1452        // whether or not they are constrained.
1453        if !non_empty_rows.is_empty() {
1454            let total_size: Au = non_empty_rows.iter().map(|index| track_sizes[*index]).sum();
1455            for track_index in non_empty_rows.iter() {
1456                let scale = track_sizes[*track_index].to_f32_px() / total_size.to_f32_px();
1457                track_sizes[*track_index] += excess_size.scale_by(scale);
1458            }
1459        }
1460    }
1461
1462    /// Given computed row sizes, compute the final block size of the table and distribute extra
1463    /// block size to table rows.
1464    fn compute_table_height_and_final_row_heights(
1465        &mut self,
1466        mut row_sizes: Vec<Au>,
1467        containing_block_for_children: &ContainingBlock,
1468    ) {
1469        // The table content height is the maximum of the computed table height from style and the
1470        // sum of computed row heights from row layout plus size from borders and spacing.
1471        // TODO: for `height: stretch`, the block size of the containing block is the available
1472        // space for the entire table wrapper, but here we are using that amount for the table grid.
1473        // Therefore, if there is a caption, this will cause overflow. Gecko and WebKit have the
1474        // same problem, but not Blink.
1475        let table_height_from_style = match containing_block_for_children.size.block {
1476            SizeConstraint::Definite(size) => size,
1477            SizeConstraint::MinMax(min, _) => min,
1478        };
1479
1480        let block_border_spacing = self.table.total_border_spacing().block;
1481        let table_height_from_rows = row_sizes.iter().sum::<Au>() + block_border_spacing;
1482        self.final_table_height = table_height_from_rows.max(table_height_from_style);
1483
1484        // If the table height is defined by the rows sizes, there is no extra space to distribute
1485        // to rows.
1486        if self.final_table_height == table_height_from_rows {
1487            self.row_sizes = row_sizes;
1488            return;
1489        }
1490
1491        // There was extra block size added to the table from the table style, so distribute this
1492        // extra space to rows using the same distribution algorithm used for distributing rowspan
1493        // space.
1494        // TODO: This should first distribute space to row groups and then to rows.
1495        self.distribute_extra_size_to_rows(
1496            self.final_table_height - table_height_from_rows,
1497            0..self.table.size.height,
1498            &mut row_sizes,
1499            Some(self.final_table_height),
1500            false, /* rowspan_distribution */
1501        );
1502        self.row_sizes = row_sizes;
1503    }
1504
1505    fn layout_caption(
1506        &self,
1507        caption: &TableCaption,
1508        layout_context: &LayoutContext,
1509        parent_positioning_context: &mut PositioningContext,
1510    ) -> BoxFragment {
1511        let containing_block = &ContainingBlock {
1512            size: ContainingBlockSize {
1513                inline: self.table_width + self.pbm.padding_border_sums.inline,
1514                block: SizeConstraint::default(),
1515            },
1516            style: &self.table.style,
1517        };
1518
1519        // The parent of a caption is the table wrapper, which establishes an independent
1520        // formatting context. Therefore, we don't ignore block margins when resolving a
1521        // stretch block size. https://drafts.csswg.org/css-sizing-4/#stretch-fit-sizing
1522        let ignore_block_margins_for_stretch = LogicalSides1D::new(false, false);
1523
1524        let mut positioning_context =
1525            PositioningContext::new_for_layout_box_base(&caption.context.base);
1526        let mut box_fragment = caption.context.layout_in_flow_block_level(
1527            layout_context,
1528            positioning_context
1529                .as_mut()
1530                .unwrap_or(parent_positioning_context),
1531            containing_block,
1532            None, /* sequential_layout_state */
1533            ignore_block_margins_for_stretch,
1534        );
1535
1536        if let Some(mut positioning_context) = positioning_context.take() {
1537            positioning_context.layout_collected_children(layout_context, &mut box_fragment);
1538            parent_positioning_context.append(positioning_context);
1539        }
1540
1541        box_fragment
1542    }
1543
1544    /// Lay out the table (grid and captions) of this [`TableLayout`] into fragments. This should
1545    /// only be be called after calling [`TableLayout.compute_measures`].
1546    #[servo_tracing::instrument(name = "Table::layout", skip_all)]
1547    fn layout(
1548        mut self,
1549        layout_context: &LayoutContext,
1550        positioning_context: &mut PositioningContext,
1551        containing_block_for_children: &ContainingBlock,
1552        containing_block_for_table: &ContainingBlock,
1553    ) -> CacheableLayoutResult {
1554        let table_writing_mode = containing_block_for_children.style.writing_mode;
1555        self.compute_border_collapse(table_writing_mode);
1556        let layout_style = self.table.layout_style(Some(&self));
1557
1558        self.pbm = layout_style
1559            .padding_border_margin_with_writing_mode_and_containing_block_inline_size(
1560                table_writing_mode,
1561                containing_block_for_table.size.inline,
1562            );
1563        self.compute_measures(layout_context, table_writing_mode);
1564        self.compute_table_width(containing_block_for_children);
1565
1566        // The table wrapper is the one that has the CSS properties for the grid's border and padding. This
1567        // weirdness is difficult to express in Servo's layout system. We have the wrapper size itself as if
1568        // those properties applied to it and then just account for the discrepency in sizing here. In reality,
1569        // the wrapper does not draw borders / backgrounds and all of its content (grid and captions) are
1570        // placed with a negative offset in the table wrapper's content box so that they overlap the undrawn
1571        // border / padding area.
1572        //
1573        // TODO: This is a pretty large hack. It would be nicer to actually have the grid sized properly,
1574        // but it works for now.
1575        //
1576        // Get the padding, border, and margin of the table using the inline size of the table's containing
1577        // block but in the writing of the table itself.
1578        // TODO: This is broken for orthoganol flows, because the inline size of the parent isn't necessarily
1579        // the inline size of the table.
1580        let containing_block_for_logical_conversion = ContainingBlock {
1581            size: ContainingBlockSize {
1582                inline: self.table_width,
1583                block: containing_block_for_table.size.block,
1584            },
1585            style: containing_block_for_children.style,
1586        };
1587        let offset_from_wrapper = -self.pbm.padding - self.pbm.border;
1588        let mut current_block_offset = offset_from_wrapper.block_start;
1589
1590        let mut table_layout = CacheableLayoutResult {
1591            fragments: Vec::new(),
1592            content_block_size: Zero::zero(),
1593            content_inline_size_for_table: None,
1594            baselines: Baselines::default(),
1595            depends_on_block_constraints: true,
1596            specific_layout_info: Some(SpecificLayoutInfo::TableWrapper),
1597            collapsible_margins_in_children: CollapsedBlockMargins::zero(),
1598        };
1599
1600        #[derive(EnumIter, PartialEq)]
1601        enum TableWrapperSection {
1602            TopCaptions,
1603            Grid,
1604            BottomCaptions,
1605        }
1606        impl TableWrapperSection {
1607            fn accepts_caption(&self, caption: &TableCaption) -> bool {
1608                match caption.context.style().clone_caption_side() {
1609                    CaptionSide::Top => *self == TableWrapperSection::TopCaptions,
1610                    CaptionSide::Bottom => *self == TableWrapperSection::BottomCaptions,
1611                }
1612            }
1613        }
1614
1615        for section in TableWrapperSection::iter() {
1616            if section == TableWrapperSection::Grid {
1617                let original_positioning_context_length = positioning_context.len();
1618                let mut grid_fragment = self.layout_grid(
1619                    layout_context,
1620                    positioning_context,
1621                    &containing_block_for_logical_conversion,
1622                    containing_block_for_children,
1623                );
1624
1625                // Take the baseline of the grid fragment, after adjusting it to be in the coordinate system
1626                // of the table wrapper.
1627                let logical_grid_content_rect = grid_fragment
1628                    .content_rect
1629                    .to_logical(&containing_block_for_logical_conversion);
1630                let grid_pbm = grid_fragment
1631                    .padding_border_margin()
1632                    .to_logical(table_writing_mode);
1633                table_layout.baselines = grid_fragment.baselines(table_writing_mode).offset(
1634                    current_block_offset +
1635                        logical_grid_content_rect.start_corner.block +
1636                        grid_pbm.block_start,
1637                );
1638
1639                grid_fragment.content_rect = LogicalRect {
1640                    start_corner: LogicalVec2 {
1641                        inline: offset_from_wrapper.inline_start + grid_pbm.inline_start,
1642                        block: current_block_offset + grid_pbm.block_start,
1643                    },
1644                    size: grid_fragment
1645                        .content_rect
1646                        .size
1647                        .to_logical(table_writing_mode),
1648                }
1649                .as_physical(Some(&containing_block_for_logical_conversion));
1650
1651                current_block_offset += grid_fragment
1652                    .border_rect()
1653                    .size
1654                    .to_logical(table_writing_mode)
1655                    .block;
1656                if logical_grid_content_rect.size.inline < self.table_width {
1657                    // This can happen when collapsing columns
1658                    table_layout.content_inline_size_for_table =
1659                        Some(logical_grid_content_rect.size.inline);
1660                }
1661
1662                let grid_fragment = Fragment::Box(ArcRefCell::new(grid_fragment));
1663                positioning_context.adjust_static_position_of_hoisted_fragments(
1664                    &grid_fragment,
1665                    original_positioning_context_length,
1666                );
1667                table_layout.fragments.push(grid_fragment);
1668            } else {
1669                let caption_fragments = self.table.captions.iter().filter_map(|caption| {
1670                    let caption = caption.borrow();
1671                    if !section.accepts_caption(&caption) {
1672                        return None;
1673                    }
1674
1675                    let original_positioning_context_length = positioning_context.len();
1676                    let mut caption_fragment =
1677                        self.layout_caption(&caption, layout_context, positioning_context);
1678
1679                    // The caption is not placed yet. Construct a rectangle for it in the adjusted containing block
1680                    // for the table children and only then convert the result to physical geometry.
1681                    let caption_pbm = caption_fragment
1682                        .padding_border_margin()
1683                        .to_logical(table_writing_mode);
1684
1685                    let caption_relative_offset = match caption_fragment.style.clone_position() {
1686                        Position::Relative => relative_adjustement(
1687                            &caption_fragment.style,
1688                            containing_block_for_children,
1689                        ),
1690                        _ => LogicalVec2::zero(),
1691                    };
1692
1693                    caption_fragment.content_rect = LogicalRect {
1694                        start_corner: LogicalVec2 {
1695                            inline: offset_from_wrapper.inline_start + caption_pbm.inline_start,
1696                            block: current_block_offset + caption_pbm.block_start,
1697                        } + caption_relative_offset,
1698                        size: caption_fragment
1699                            .content_rect
1700                            .size
1701                            .to_logical(table_writing_mode),
1702                    }
1703                    .as_physical(Some(&containing_block_for_logical_conversion));
1704
1705                    current_block_offset += caption_fragment
1706                        .margin_rect()
1707                        .size
1708                        .to_logical(table_writing_mode)
1709                        .block;
1710
1711                    let caption_fragment = Fragment::Box(ArcRefCell::new(caption_fragment));
1712                    positioning_context.adjust_static_position_of_hoisted_fragments(
1713                        &caption_fragment,
1714                        original_positioning_context_length,
1715                    );
1716
1717                    caption.context.base.set_fragment(caption_fragment.clone());
1718                    Some(caption_fragment)
1719                });
1720                table_layout.fragments.extend(caption_fragments);
1721            }
1722        }
1723
1724        table_layout.content_block_size = current_block_offset + offset_from_wrapper.block_end;
1725        table_layout
1726    }
1727
1728    /// Lay out the grid portion of this [`TableLayout`] into fragments. This should only be be
1729    /// called after calling [`TableLayout.compute_measures`].
1730    fn layout_grid(
1731        &mut self,
1732        layout_context: &LayoutContext,
1733        positioning_context: &mut PositioningContext,
1734        containing_block_for_logical_conversion: &ContainingBlock,
1735        containing_block_for_children: &ContainingBlock,
1736    ) -> BoxFragment {
1737        self.distributed_column_widths =
1738            Self::distribute_width_to_columns(self.assignable_width, &self.columns);
1739        self.layout_cells_in_row(layout_context, containing_block_for_children);
1740        let table_writing_mode = containing_block_for_children.style.writing_mode;
1741        let first_layout_row_heights = self.do_first_row_layout(table_writing_mode);
1742        self.compute_table_height_and_final_row_heights(
1743            first_layout_row_heights,
1744            containing_block_for_children,
1745        );
1746
1747        assert_eq!(self.table.size.height, self.row_sizes.len());
1748        assert_eq!(self.table.size.width, self.distributed_column_widths.len());
1749
1750        if self.table.size.width == 0 && self.table.size.height == 0 {
1751            let content_rect = LogicalRect {
1752                start_corner: LogicalVec2::zero(),
1753                size: LogicalVec2 {
1754                    inline: self.table_width,
1755                    block: self.final_table_height,
1756                },
1757            }
1758            .as_physical(Some(containing_block_for_logical_conversion));
1759            return BoxFragment::new(
1760                self.table.grid_base_fragment_info,
1761                self.table.grid_style.clone(),
1762                Vec::new(),
1763                content_rect,
1764                self.pbm.padding.to_physical(table_writing_mode),
1765                self.pbm.border.to_physical(table_writing_mode),
1766                PhysicalSides::zero(),
1767                self.specific_layout_info_for_grid(),
1768            );
1769        }
1770
1771        let mut table_fragments = Vec::new();
1772        let table_and_track_dimensions = TableAndTrackDimensions::new(self);
1773        self.make_fragments_for_columns_and_column_groups(
1774            &table_and_track_dimensions,
1775            &mut table_fragments,
1776        );
1777
1778        let mut baselines = Baselines::default();
1779        let mut row_group_fragment_layout = None;
1780        for row_index in 0..self.table.size.height {
1781            // From <https://drafts.csswg.org/css-align-3/#baseline-export>
1782            // > If any cells in the row participate in first baseline/last baseline alignment along
1783            // > the inline axis, the first/last baseline set of the row is generated from their
1784            // > shared alignment baseline and the row’s first available font, after alignment has
1785            // > been performed. Otherwise, the first/last baseline set of the row is synthesized from
1786            // > the lowest and highest content edges of the cells in the row. [CSS2]
1787            //
1788            // If any cell below has baseline alignment, these values will be overwritten,
1789            // but they are initialized to the content edge of the first row.
1790            if row_index == 0 {
1791                let row_end = table_and_track_dimensions
1792                    .get_row_rect(0)
1793                    .max_block_position();
1794                baselines.first = Some(row_end);
1795                baselines.last = Some(row_end);
1796            }
1797
1798            let row_is_collapsed = self.is_row_collapsed(row_index);
1799            let table_row = self.table.rows[row_index].borrow();
1800            let mut row_fragment_layout = RowFragmentLayout::new(
1801                &table_row,
1802                row_index,
1803                &table_and_track_dimensions,
1804                &self.table.style,
1805            );
1806
1807            let old_row_group_index = row_group_fragment_layout
1808                .as_ref()
1809                .map(|layout: &RowGroupFragmentLayout| layout.index);
1810            if table_row.group_index != old_row_group_index {
1811                // First create the Fragment for any existing RowGroupFragmentLayout.
1812                if let Some(old_row_group_layout) = row_group_fragment_layout.take() {
1813                    table_fragments.push(old_row_group_layout.finish(
1814                        layout_context,
1815                        positioning_context,
1816                        containing_block_for_logical_conversion,
1817                        containing_block_for_children,
1818                    ));
1819                }
1820
1821                // Then, create a new RowGroupFragmentLayout for the current and potentially subsequent rows.
1822                if let Some(new_group_index) = table_row.group_index {
1823                    row_group_fragment_layout = Some(RowGroupFragmentLayout::new(
1824                        self.table.row_groups[new_group_index].clone(),
1825                        new_group_index,
1826                        &table_and_track_dimensions,
1827                    ));
1828                }
1829            }
1830
1831            let column_indices = 0..self.table.size.width;
1832            row_fragment_layout.fragments.reserve(self.table.size.width);
1833            for column_index in column_indices {
1834                self.do_final_cell_layout(
1835                    row_index,
1836                    column_index,
1837                    &table_and_track_dimensions,
1838                    &mut baselines,
1839                    &mut row_fragment_layout,
1840                    row_group_fragment_layout.as_mut(),
1841                    positioning_context,
1842                    self.is_column_collapsed(column_index) || row_is_collapsed,
1843                );
1844            }
1845
1846            let row_fragment = row_fragment_layout.finish(
1847                layout_context,
1848                positioning_context,
1849                containing_block_for_logical_conversion,
1850                containing_block_for_children,
1851                &mut row_group_fragment_layout,
1852            );
1853
1854            match row_group_fragment_layout.as_mut() {
1855                Some(layout) => layout.fragments.push(row_fragment),
1856                None => table_fragments.push(row_fragment),
1857            }
1858        }
1859
1860        if let Some(row_group_layout) = row_group_fragment_layout.take() {
1861            table_fragments.push(row_group_layout.finish(
1862                layout_context,
1863                positioning_context,
1864                containing_block_for_logical_conversion,
1865                containing_block_for_children,
1866            ));
1867        }
1868
1869        let content_rect = LogicalRect {
1870            start_corner: LogicalVec2::zero(),
1871            size: LogicalVec2 {
1872                inline: table_and_track_dimensions.table_rect.max_inline_position(),
1873                block: table_and_track_dimensions.table_rect.max_block_position(),
1874            },
1875        }
1876        .as_physical(Some(containing_block_for_logical_conversion));
1877        BoxFragment::new(
1878            self.table.grid_base_fragment_info,
1879            self.table.grid_style.clone(),
1880            table_fragments,
1881            content_rect,
1882            self.pbm.padding.to_physical(table_writing_mode),
1883            self.pbm.border.to_physical(table_writing_mode),
1884            PhysicalSides::zero(),
1885            self.specific_layout_info_for_grid(),
1886        )
1887        .with_baselines(baselines)
1888    }
1889
1890    fn specific_layout_info_for_grid(&mut self) -> Option<SpecificLayoutInfo> {
1891        mem::take(&mut self.collapsed_borders).map(|mut collapsed_borders| {
1892            // TODO: It would probably be better to use `TableAndTrackDimensions`, since that
1893            // has already taken care of collapsed tracks and knows the final track positions.
1894            let mut track_sizes = LogicalVec2 {
1895                inline: mem::take(&mut self.distributed_column_widths),
1896                block: mem::take(&mut self.row_sizes),
1897            };
1898            for (column_index, column_size) in track_sizes.inline.iter_mut().enumerate() {
1899                if self.is_column_collapsed(column_index) {
1900                    mem::take(column_size);
1901                }
1902            }
1903            for (row_index, row_size) in track_sizes.block.iter_mut().enumerate() {
1904                if self.is_row_collapsed(row_index) {
1905                    mem::take(row_size);
1906                }
1907            }
1908            let writing_mode = self.table.style.writing_mode;
1909            if !writing_mode.is_bidi_ltr() {
1910                track_sizes.inline.reverse();
1911                collapsed_borders.inline.reverse();
1912                for border_line in &mut collapsed_borders.block {
1913                    border_line.reverse();
1914                }
1915            }
1916            SpecificLayoutInfo::TableGridWithCollapsedBorders(Box::new(SpecificTableGridInfo {
1917                collapsed_borders: if writing_mode.is_horizontal() {
1918                    PhysicalVec::new(collapsed_borders.inline, collapsed_borders.block)
1919                } else {
1920                    PhysicalVec::new(collapsed_borders.block, collapsed_borders.inline)
1921                },
1922                track_sizes: if writing_mode.is_horizontal() {
1923                    PhysicalVec::new(track_sizes.inline, track_sizes.block)
1924                } else {
1925                    PhysicalVec::new(track_sizes.block, track_sizes.inline)
1926                },
1927            }))
1928        })
1929    }
1930
1931    fn is_row_collapsed(&self, row_index: usize) -> bool {
1932        let Some(row) = &self.table.rows.get(row_index) else {
1933            return false;
1934        };
1935
1936        let row = row.borrow();
1937        if row.base.style.get_inherited_box().visibility == Visibility::Collapse {
1938            return true;
1939        }
1940        let row_group = match row.group_index {
1941            Some(group_index) => self.table.row_groups[group_index].borrow(),
1942            None => return false,
1943        };
1944        row_group.base.style.get_inherited_box().visibility == Visibility::Collapse
1945    }
1946
1947    fn is_column_collapsed(&self, column_index: usize) -> bool {
1948        let Some(column) = &self.table.columns.get(column_index) else {
1949            return false;
1950        };
1951        let column = column.borrow();
1952        if column.base.style.get_inherited_box().visibility == Visibility::Collapse {
1953            return true;
1954        }
1955        let col_group = match column.group_index {
1956            Some(group_index) => self.table.column_groups[group_index].borrow(),
1957            None => return false,
1958        };
1959        col_group.base.style.get_inherited_box().visibility == Visibility::Collapse
1960    }
1961
1962    #[allow(clippy::too_many_arguments)]
1963    fn do_final_cell_layout(
1964        &mut self,
1965        row_index: usize,
1966        column_index: usize,
1967        dimensions: &TableAndTrackDimensions,
1968        baselines: &mut Baselines,
1969        row_fragment_layout: &mut RowFragmentLayout,
1970        row_group_fragment_layout: Option<&mut RowGroupFragmentLayout>,
1971        positioning_context_for_table: &mut PositioningContext,
1972        is_collapsed: bool,
1973    ) {
1974        // The PositioningContext for cells is, in order or preference, the PositioningContext of the row,
1975        // the PositioningContext of the row group, or the PositioningContext of the table.
1976        let row_group_positioning_context =
1977            row_group_fragment_layout.and_then(|layout| layout.positioning_context.as_mut());
1978        let positioning_context = row_fragment_layout
1979            .positioning_context
1980            .as_mut()
1981            .or(row_group_positioning_context)
1982            .unwrap_or(positioning_context_for_table);
1983
1984        let layout = match self.cells_laid_out[row_index][column_index].take() {
1985            Some(layout) => layout,
1986            None => {
1987                return;
1988            },
1989        };
1990        let cell = match self.table.slots[row_index][column_index] {
1991            TableSlot::Cell(ref cell) => cell,
1992            _ => {
1993                warn!("Did not find a non-spanned cell at index with layout.");
1994                return;
1995            },
1996        }
1997        .borrow();
1998
1999        // If this cell has baseline alignment, it can adjust the table's overall baseline.
2000        let row_block_offset = row_fragment_layout.rect.start_corner.block;
2001        let row_baseline = self.row_baselines[row_index];
2002        if cell.effective_vertical_align() == VerticalAlignKeyword::Baseline && !layout.is_empty() {
2003            let baseline = row_block_offset + row_baseline;
2004            if row_index == 0 {
2005                baselines.first = Some(baseline);
2006            }
2007            baselines.last = Some(baseline);
2008        }
2009        let mut row_relative_cell_rect = dimensions.get_cell_rect(
2010            TableSlotCoordinates::new(column_index, row_index),
2011            cell.rowspan,
2012            cell.colspan,
2013        );
2014        row_relative_cell_rect.start_corner -= row_fragment_layout.rect.start_corner;
2015        let mut fragment = cell.create_fragment(
2016            layout,
2017            row_relative_cell_rect,
2018            row_baseline,
2019            positioning_context,
2020            &self.table.style,
2021            &row_fragment_layout.containing_block,
2022            is_collapsed,
2023        );
2024
2025        // Make a table part rectangle relative to the row fragment for the purposes of
2026        // drawing extra backgrounds.
2027        //
2028        // This rectangle is an offset between the row fragment and the other table
2029        // part rectangle (row group, column, column group). Everything between them
2030        // is laid out in a left-to-right fashion, but respecting the verticality of
2031        // the writing mode. This is why below, only the axes are flipped, but the
2032        // rectangle is not flipped for RTL.
2033        let make_relative_to_row_start = |mut rect: LogicalRect<Au>| {
2034            rect.start_corner -= row_fragment_layout.rect.start_corner;
2035            let writing_mode = self.table.style.writing_mode;
2036            PhysicalRect::new(
2037                if writing_mode.is_horizontal() {
2038                    PhysicalPoint::new(rect.start_corner.inline, rect.start_corner.block)
2039                } else {
2040                    PhysicalPoint::new(rect.start_corner.block, rect.start_corner.inline)
2041                },
2042                rect.size.to_physical_size(writing_mode),
2043            )
2044        };
2045
2046        let column = self.table.columns.get(column_index);
2047        let column_group = column
2048            .and_then(|column| column.borrow().group_index)
2049            .and_then(|index| self.table.column_groups.get(index));
2050        if let Some(column_group) = column_group {
2051            let column_group = column_group.borrow();
2052            let rect = make_relative_to_row_start(dimensions.get_column_group_rect(&column_group));
2053            fragment.add_extra_background(ExtraBackground {
2054                style: column_group.shared_background_style.clone(),
2055                rect,
2056            })
2057        }
2058        if let Some(column) = column {
2059            let column = column.borrow();
2060            if !column.is_anonymous {
2061                let rect = make_relative_to_row_start(dimensions.get_column_rect(column_index));
2062                fragment.add_extra_background(ExtraBackground {
2063                    style: column.shared_background_style.clone(),
2064                    rect,
2065                })
2066            }
2067        }
2068        let row = self.table.rows.get(row_index);
2069        let row_group = row
2070            .and_then(|row| row.borrow().group_index)
2071            .and_then(|index| self.table.row_groups.get(index));
2072        if let Some(row_group) = row_group {
2073            let rect =
2074                make_relative_to_row_start(dimensions.get_row_group_rect(&row_group.borrow()));
2075            fragment.add_extra_background(ExtraBackground {
2076                style: row_group.borrow().shared_background_style.clone(),
2077                rect,
2078            })
2079        }
2080        if let Some(row) = row {
2081            let row = row.borrow();
2082            let rect = make_relative_to_row_start(row_fragment_layout.rect);
2083            fragment.add_extra_background(ExtraBackground {
2084                style: row.shared_background_style.clone(),
2085                rect,
2086            })
2087        }
2088
2089        let fragment = Fragment::Box(ArcRefCell::new(fragment));
2090        cell.base.set_fragment(fragment.clone());
2091        row_fragment_layout.fragments.push(fragment);
2092    }
2093
2094    fn make_fragments_for_columns_and_column_groups(
2095        &self,
2096        dimensions: &TableAndTrackDimensions,
2097        fragments: &mut Vec<Fragment>,
2098    ) {
2099        for column_group in self.table.column_groups.iter() {
2100            let column_group = column_group.borrow();
2101            if !column_group.is_empty() {
2102                let fragment = Fragment::Positioning(PositioningFragment::new_empty(
2103                    column_group.base.base_fragment_info,
2104                    dimensions
2105                        .get_column_group_rect(&column_group)
2106                        .as_physical(None),
2107                    column_group.base.style.clone(),
2108                ));
2109                column_group.base.set_fragment(fragment.clone());
2110                fragments.push(fragment);
2111            }
2112        }
2113
2114        for (column_index, column) in self.table.columns.iter().enumerate() {
2115            let column = column.borrow();
2116            let fragment = Fragment::Positioning(PositioningFragment::new_empty(
2117                column.base.base_fragment_info,
2118                dimensions.get_column_rect(column_index).as_physical(None),
2119                column.base.style.clone(),
2120            ));
2121            column.base.set_fragment(fragment.clone());
2122            fragments.push(fragment);
2123        }
2124    }
2125
2126    fn compute_border_collapse(&mut self, writing_mode: WritingMode) {
2127        if self.table.style.get_inherited_table().border_collapse != BorderCollapse::Collapse {
2128            self.collapsed_borders = None;
2129            return;
2130        }
2131
2132        let mut collapsed_borders = LogicalVec2 {
2133            block: vec![
2134                vec![Default::default(); self.table.size.width];
2135                self.table.size.height + 1
2136            ],
2137            inline: vec![
2138                vec![Default::default(); self.table.size.height];
2139                self.table.size.width + 1
2140            ],
2141        };
2142
2143        let apply_border = |collapsed_borders: &mut CollapsedBorders,
2144                            layout_style: &LayoutStyle,
2145                            block: &Range<usize>,
2146                            inline: &Range<usize>| {
2147            let border = CollapsedBorder::from_layout_style(layout_style, writing_mode);
2148            border
2149                .block_start
2150                .max_assign_to_slice(&mut collapsed_borders.block[block.start][inline.clone()]);
2151            border
2152                .block_end
2153                .max_assign_to_slice(&mut collapsed_borders.block[block.end][inline.clone()]);
2154            border
2155                .inline_start
2156                .max_assign_to_slice(&mut collapsed_borders.inline[inline.start][block.clone()]);
2157            border
2158                .inline_end
2159                .max_assign_to_slice(&mut collapsed_borders.inline[inline.end][block.clone()]);
2160        };
2161        let hide_inner_borders = |collapsed_borders: &mut CollapsedBorders,
2162                                  block: &Range<usize>,
2163                                  inline: &Range<usize>| {
2164            for x in inline.clone() {
2165                for y in block.clone() {
2166                    if x != inline.start {
2167                        collapsed_borders.inline[x][y].hide();
2168                    }
2169                    if y != block.start {
2170                        collapsed_borders.block[y][x].hide();
2171                    }
2172                }
2173            }
2174        };
2175        let all_rows = 0..self.table.size.height;
2176        let all_columns = 0..self.table.size.width;
2177        for row_index in all_rows.clone() {
2178            for column_index in all_columns.clone() {
2179                let cell = match self.table.slots[row_index][column_index] {
2180                    TableSlot::Cell(ref cell) => cell,
2181                    _ => continue,
2182                }
2183                .borrow();
2184                let block_range = row_index..row_index + cell.rowspan;
2185                let inline_range = column_index..column_index + cell.colspan;
2186                hide_inner_borders(&mut collapsed_borders, &block_range, &inline_range);
2187                apply_border(
2188                    &mut collapsed_borders,
2189                    &cell.layout_style(),
2190                    &block_range,
2191                    &inline_range,
2192                );
2193            }
2194        }
2195        for (row_index, row) in self.table.rows.iter().enumerate() {
2196            let row = row.borrow();
2197            apply_border(
2198                &mut collapsed_borders,
2199                &row.layout_style(),
2200                &(row_index..row_index + 1),
2201                &all_columns,
2202            );
2203        }
2204        for row_group in &self.table.row_groups {
2205            let row_group = row_group.borrow();
2206            apply_border(
2207                &mut collapsed_borders,
2208                &row_group.layout_style(),
2209                &row_group.track_range,
2210                &all_columns,
2211            );
2212        }
2213        for (column_index, column) in self.table.columns.iter().enumerate() {
2214            let column = column.borrow();
2215            apply_border(
2216                &mut collapsed_borders,
2217                &column.layout_style(),
2218                &all_rows,
2219                &(column_index..column_index + 1),
2220            );
2221        }
2222        for column_group in &self.table.column_groups {
2223            let column_group = column_group.borrow();
2224            apply_border(
2225                &mut collapsed_borders,
2226                &column_group.layout_style(),
2227                &all_rows,
2228                &column_group.track_range,
2229            );
2230        }
2231        apply_border(
2232            &mut collapsed_borders,
2233            &self.table.layout_style_for_grid(),
2234            &all_rows,
2235            &all_columns,
2236        );
2237
2238        self.collapsed_borders = Some(collapsed_borders);
2239    }
2240
2241    fn get_collapsed_border_widths_for_area(
2242        &self,
2243        area: LogicalSides<usize>,
2244    ) -> Option<LogicalSides<Au>> {
2245        let collapsed_borders = self.collapsed_borders.as_ref()?;
2246        let columns = || area.inline_start..area.inline_end;
2247        let rows = || area.block_start..area.block_end;
2248        let max_width = |slice: &[CollapsedBorder]| {
2249            let slice_widths = slice.iter().map(|collapsed_border| collapsed_border.width);
2250            slice_widths.max().unwrap_or_default()
2251        };
2252        Some(area.map_inline_and_block_axes(
2253            |column| max_width(&collapsed_borders.inline[*column][rows()]) / 2,
2254            |row| max_width(&collapsed_borders.block[*row][columns()]) / 2,
2255        ))
2256    }
2257}
2258
2259struct RowFragmentLayout<'a> {
2260    row: &'a TableTrack,
2261    rect: LogicalRect<Au>,
2262    containing_block: ContainingBlock<'a>,
2263    positioning_context: Option<PositioningContext>,
2264    fragments: Vec<Fragment>,
2265}
2266
2267impl<'a> RowFragmentLayout<'a> {
2268    fn new(
2269        table_row: &'a TableTrack,
2270        index: usize,
2271        dimensions: &TableAndTrackDimensions,
2272        table_style: &'a ComputedValues,
2273    ) -> Self {
2274        let rect = dimensions.get_row_rect(index);
2275        let containing_block = ContainingBlock {
2276            size: ContainingBlockSize {
2277                inline: rect.size.inline,
2278                block: SizeConstraint::Definite(rect.size.block),
2279            },
2280            style: table_style,
2281        };
2282        Self {
2283            row: table_row,
2284            rect,
2285            positioning_context: PositioningContext::new_for_layout_box_base(&table_row.base),
2286            containing_block,
2287            fragments: Vec::new(),
2288        }
2289    }
2290    fn finish(
2291        mut self,
2292        layout_context: &LayoutContext,
2293        table_positioning_context: &mut PositioningContext,
2294        containing_block_for_logical_conversion: &ContainingBlock,
2295        containing_block_for_children: &ContainingBlock,
2296        row_group_fragment_layout: &mut Option<RowGroupFragmentLayout>,
2297    ) -> Fragment {
2298        if self.positioning_context.is_some() {
2299            self.rect.start_corner +=
2300                relative_adjustement(&self.row.base.style, containing_block_for_children);
2301        }
2302
2303        let (inline_size, block_size) = if let Some(row_group_layout) = row_group_fragment_layout {
2304            self.rect.start_corner -= row_group_layout.rect.start_corner;
2305            (
2306                row_group_layout.rect.size.inline,
2307                SizeConstraint::Definite(row_group_layout.rect.size.block),
2308            )
2309        } else {
2310            (
2311                containing_block_for_logical_conversion.size.inline,
2312                containing_block_for_logical_conversion.size.block,
2313            )
2314        };
2315
2316        let row_group_containing_block = ContainingBlock {
2317            size: ContainingBlockSize {
2318                inline: inline_size,
2319                block: block_size,
2320            },
2321            style: containing_block_for_logical_conversion.style,
2322        };
2323
2324        let mut row_fragment = BoxFragment::new(
2325            self.row.base.base_fragment_info,
2326            self.row.base.style.clone(),
2327            self.fragments,
2328            self.rect.as_physical(Some(&row_group_containing_block)),
2329            PhysicalSides::zero(), /* padding */
2330            PhysicalSides::zero(), /* border */
2331            PhysicalSides::zero(), /* margin */
2332            None,                  /* specific_layout_info */
2333        );
2334        row_fragment.set_does_not_paint_background();
2335
2336        if let Some(mut row_positioning_context) = self.positioning_context.take() {
2337            row_positioning_context.layout_collected_children(layout_context, &mut row_fragment);
2338
2339            let parent_positioning_context = row_group_fragment_layout
2340                .as_mut()
2341                .and_then(|layout| layout.positioning_context.as_mut())
2342                .unwrap_or(table_positioning_context);
2343            parent_positioning_context.append(row_positioning_context);
2344        }
2345
2346        let fragment = Fragment::Box(ArcRefCell::new(row_fragment));
2347        self.row.base.set_fragment(fragment.clone());
2348        fragment
2349    }
2350}
2351
2352struct RowGroupFragmentLayout {
2353    row_group: ArcRefCell<TableTrackGroup>,
2354    rect: LogicalRect<Au>,
2355    positioning_context: Option<PositioningContext>,
2356    index: usize,
2357    fragments: Vec<Fragment>,
2358}
2359
2360impl RowGroupFragmentLayout {
2361    fn new(
2362        row_group: ArcRefCell<TableTrackGroup>,
2363        index: usize,
2364        dimensions: &TableAndTrackDimensions,
2365    ) -> Self {
2366        let (rect, positioning_context) = {
2367            let row_group = row_group.borrow();
2368            (
2369                dimensions.get_row_group_rect(&row_group),
2370                PositioningContext::new_for_layout_box_base(&row_group.base),
2371            )
2372        };
2373        Self {
2374            row_group,
2375            rect,
2376            positioning_context,
2377            index,
2378            fragments: Vec::new(),
2379        }
2380    }
2381
2382    fn finish(
2383        mut self,
2384        layout_context: &LayoutContext,
2385        table_positioning_context: &mut PositioningContext,
2386        containing_block_for_logical_conversion: &ContainingBlock,
2387        containing_block_for_children: &ContainingBlock,
2388    ) -> Fragment {
2389        let row_group = self.row_group.borrow();
2390        if self.positioning_context.is_some() {
2391            self.rect.start_corner +=
2392                relative_adjustement(&row_group.base.style, containing_block_for_children);
2393        }
2394
2395        let mut row_group_fragment = BoxFragment::new(
2396            row_group.base.base_fragment_info,
2397            row_group.base.style.clone(),
2398            self.fragments,
2399            self.rect
2400                .as_physical(Some(containing_block_for_logical_conversion)),
2401            PhysicalSides::zero(), /* padding */
2402            PhysicalSides::zero(), /* border */
2403            PhysicalSides::zero(), /* margin */
2404            None,                  /* specific_layout_info */
2405        );
2406        row_group_fragment.set_does_not_paint_background();
2407
2408        if let Some(mut row_positioning_context) = self.positioning_context.take() {
2409            row_positioning_context
2410                .layout_collected_children(layout_context, &mut row_group_fragment);
2411            table_positioning_context.append(row_positioning_context);
2412        }
2413
2414        let fragment = Fragment::Box(ArcRefCell::new(row_group_fragment));
2415        row_group.base.set_fragment(fragment.clone());
2416        fragment
2417    }
2418}
2419
2420struct TableAndTrackDimensions {
2421    /// The rect of the full table, not counting for borders, padding, and margin.
2422    table_rect: LogicalRect<Au>,
2423    /// The rect of the full table, not counting for borders, padding, and margin
2424    /// and offset by any border spacing and caption.
2425    table_cells_rect: LogicalRect<Au>,
2426    /// The min and max block offsets of each table row.
2427    row_dimensions: Vec<(Au, Au)>,
2428    /// The min and max inline offsets of each table column
2429    column_dimensions: Vec<(Au, Au)>,
2430}
2431
2432impl TableAndTrackDimensions {
2433    fn new(table_layout: &TableLayout) -> Self {
2434        let border_spacing = table_layout.table.border_spacing();
2435
2436        // The sizes used for a dimension when that dimension has no table tracks.
2437        let fallback_inline_size = table_layout.assignable_width;
2438        let fallback_block_size = table_layout.final_table_height;
2439
2440        let mut column_dimensions = Vec::new();
2441        let mut column_offset = Au::zero();
2442        for column_index in 0..table_layout.table.size.width {
2443            if table_layout.is_column_collapsed(column_index) {
2444                column_dimensions.push((column_offset, column_offset));
2445                continue;
2446            }
2447            let start_offset = column_offset + border_spacing.inline;
2448            let end_offset = start_offset + table_layout.distributed_column_widths[column_index];
2449            column_dimensions.push((start_offset, end_offset));
2450            column_offset = end_offset;
2451        }
2452        column_offset += if table_layout.table.size.width == 0 {
2453            fallback_inline_size
2454        } else {
2455            border_spacing.inline
2456        };
2457
2458        let mut row_dimensions = Vec::new();
2459        let mut row_offset = Au::zero();
2460        for row_index in 0..table_layout.table.size.height {
2461            if table_layout.is_row_collapsed(row_index) {
2462                row_dimensions.push((row_offset, row_offset));
2463                continue;
2464            }
2465            let start_offset = row_offset + border_spacing.block;
2466            let end_offset = start_offset + table_layout.row_sizes[row_index];
2467            row_dimensions.push((start_offset, end_offset));
2468            row_offset = end_offset;
2469        }
2470        row_offset += if table_layout.table.size.height == 0 {
2471            fallback_block_size
2472        } else {
2473            border_spacing.block
2474        };
2475
2476        let table_start_corner = LogicalVec2 {
2477            inline: column_dimensions.first().map_or_else(Au::zero, |v| v.0),
2478            block: row_dimensions.first().map_or_else(Au::zero, |v| v.0),
2479        };
2480        let table_size = LogicalVec2 {
2481            inline: column_dimensions
2482                .last()
2483                .map_or(fallback_inline_size, |v| v.1),
2484            block: row_dimensions.last().map_or(fallback_block_size, |v| v.1),
2485        } - table_start_corner;
2486        let table_cells_rect = LogicalRect {
2487            start_corner: table_start_corner,
2488            size: table_size,
2489        };
2490
2491        let table_rect = LogicalRect {
2492            start_corner: LogicalVec2::zero(),
2493            size: LogicalVec2 {
2494                inline: column_offset,
2495                block: row_offset,
2496            },
2497        };
2498
2499        Self {
2500            table_rect,
2501            table_cells_rect,
2502            row_dimensions,
2503            column_dimensions,
2504        }
2505    }
2506
2507    fn get_row_rect(&self, row_index: usize) -> LogicalRect<Au> {
2508        let mut row_rect = self.table_cells_rect;
2509        let row_dimensions = self.row_dimensions[row_index];
2510        row_rect.start_corner.block = row_dimensions.0;
2511        row_rect.size.block = row_dimensions.1 - row_dimensions.0;
2512        row_rect
2513    }
2514
2515    fn get_column_rect(&self, column_index: usize) -> LogicalRect<Au> {
2516        let mut row_rect = self.table_cells_rect;
2517        let column_dimensions = self.column_dimensions[column_index];
2518        row_rect.start_corner.inline = column_dimensions.0;
2519        row_rect.size.inline = column_dimensions.1 - column_dimensions.0;
2520        row_rect
2521    }
2522
2523    fn get_row_group_rect(&self, row_group: &TableTrackGroup) -> LogicalRect<Au> {
2524        if row_group.is_empty() {
2525            return LogicalRect::zero();
2526        }
2527
2528        let mut row_group_rect = self.table_cells_rect;
2529        let block_start = self.row_dimensions[row_group.track_range.start].0;
2530        let block_end = self.row_dimensions[row_group.track_range.end - 1].1;
2531        row_group_rect.start_corner.block = block_start;
2532        row_group_rect.size.block = block_end - block_start;
2533        row_group_rect
2534    }
2535
2536    fn get_column_group_rect(&self, column_group: &TableTrackGroup) -> LogicalRect<Au> {
2537        if column_group.is_empty() {
2538            return LogicalRect::zero();
2539        }
2540
2541        let mut column_group_rect = self.table_cells_rect;
2542        let inline_start = self.column_dimensions[column_group.track_range.start].0;
2543        let inline_end = self.column_dimensions[column_group.track_range.end - 1].1;
2544        column_group_rect.start_corner.inline = inline_start;
2545        column_group_rect.size.inline = inline_end - inline_start;
2546        column_group_rect
2547    }
2548
2549    fn get_cell_rect(
2550        &self,
2551        coordinates: TableSlotCoordinates,
2552        rowspan: usize,
2553        colspan: usize,
2554    ) -> LogicalRect<Au> {
2555        let start_corner = LogicalVec2 {
2556            inline: self.column_dimensions[coordinates.x].0,
2557            block: self.row_dimensions[coordinates.y].0,
2558        };
2559        let size = LogicalVec2 {
2560            inline: self.column_dimensions[coordinates.x + colspan - 1].1,
2561            block: self.row_dimensions[coordinates.y + rowspan - 1].1,
2562        } - start_corner;
2563        LogicalRect { start_corner, size }
2564    }
2565}
2566
2567impl Table {
2568    fn border_spacing(&self) -> LogicalVec2<Au> {
2569        if self.style.clone_border_collapse() == BorderCollapse::Collapse {
2570            LogicalVec2::zero()
2571        } else {
2572            let border_spacing = self.style.clone_border_spacing();
2573            LogicalVec2 {
2574                inline: border_spacing.horizontal(),
2575                block: border_spacing.vertical(),
2576            }
2577        }
2578    }
2579
2580    fn total_border_spacing(&self) -> LogicalVec2<Au> {
2581        let border_spacing = self.border_spacing();
2582        LogicalVec2 {
2583            inline: if self.size.width > 0 {
2584                border_spacing.inline * (self.size.width as i32 + 1)
2585            } else {
2586                Au::zero()
2587            },
2588            block: if self.size.height > 0 {
2589                border_spacing.block * (self.size.height as i32 + 1)
2590            } else {
2591                Au::zero()
2592            },
2593        }
2594    }
2595
2596    fn get_column_measure_for_column_at_index(
2597        &self,
2598        writing_mode: WritingMode,
2599        column_index: usize,
2600        is_in_fixed_mode: bool,
2601    ) -> CellOrTrackMeasure {
2602        let column = match self.columns.get(column_index) {
2603            Some(column) => column,
2604            None => return CellOrTrackMeasure::zero(),
2605        }
2606        .borrow();
2607
2608        let CellOrColumnOuterSizes {
2609            preferred: preferred_size,
2610            min: min_size,
2611            max: max_size,
2612            percentage: percentage_size,
2613        } = CellOrColumnOuterSizes::new(
2614            &column.base.style,
2615            writing_mode,
2616            &Default::default(),
2617            is_in_fixed_mode,
2618        );
2619
2620        CellOrTrackMeasure {
2621            content_sizes: ContentSizes {
2622                // > The outer min-content width of a table-column or table-column-group is
2623                // > max(min-width, width).
2624                // But that's clearly wrong, since it would be equal to or greater than
2625                // the outer max-content width. So we match other browsers instead.
2626                min_content: min_size.inline,
2627                // > The outer max-content width of a table-column or table-column-group is
2628                // > max(min-width, min(max-width, width)).
2629                // This matches Gecko, but Blink and WebKit ignore max_size.
2630                max_content: preferred_size
2631                    .inline
2632                    .clamp_between_extremums(min_size.inline, max_size.inline),
2633            },
2634            percentage: percentage_size.inline,
2635        }
2636    }
2637
2638    fn get_row_measure_for_row_at_index(
2639        &self,
2640        writing_mode: WritingMode,
2641        row_index: usize,
2642    ) -> CellOrTrackMeasure {
2643        let row = match self.rows.get(row_index) {
2644            Some(row) => row,
2645            None => return CellOrTrackMeasure::zero(),
2646        };
2647
2648        // In the block axis, the min-content and max-content sizes are the same
2649        // (except for new layout boxes like grid and flex containers). Note that
2650        // other browsers don't seem to use the min and max sizing properties here.
2651        let row = row.borrow();
2652        let size = row.base.style.box_size(writing_mode);
2653        let max_size = row.base.style.max_box_size(writing_mode);
2654        let percentage_contribution = get_size_percentage_contribution(&size, &max_size);
2655
2656        CellOrTrackMeasure {
2657            content_sizes: size
2658                .block
2659                .to_numeric()
2660                .and_then(|size| size.to_length())
2661                .map_or_else(Au::zero, Au::from)
2662                .into(),
2663            percentage: percentage_contribution.block,
2664        }
2665    }
2666
2667    pub(crate) fn layout(
2668        &self,
2669        layout_context: &LayoutContext,
2670        positioning_context: &mut PositioningContext,
2671        containing_block_for_children: &ContainingBlock,
2672        containing_block_for_table: &ContainingBlock,
2673    ) -> CacheableLayoutResult {
2674        TableLayout::new(self).layout(
2675            layout_context,
2676            positioning_context,
2677            containing_block_for_children,
2678            containing_block_for_table,
2679        )
2680    }
2681}
2682
2683impl ComputeInlineContentSizes for Table {
2684    #[servo_tracing::instrument(name = "Table::compute_inline_content_sizes", skip_all)]
2685    fn compute_inline_content_sizes(
2686        &self,
2687        layout_context: &LayoutContext,
2688        constraint_space: &ConstraintSpace,
2689    ) -> InlineContentSizesResult {
2690        let writing_mode = constraint_space.style.writing_mode;
2691        let mut layout = TableLayout::new(self);
2692        layout.compute_border_collapse(writing_mode);
2693        layout.pbm = self
2694            .layout_style(Some(&layout))
2695            .padding_border_margin_with_writing_mode_and_containing_block_inline_size(
2696                writing_mode,
2697                Au::zero(),
2698            );
2699        layout.compute_measures(layout_context, writing_mode);
2700
2701        let grid_content_sizes = layout.compute_grid_min_max();
2702
2703        // Padding and border should apply to the table grid, but they will be taken into
2704        // account when computing the inline content sizes of the table wrapper (our parent), so
2705        // this code removes their contribution from the inline content size of the caption.
2706        let caption_content_sizes = ContentSizes::from(
2707            layout.compute_caption_minimum_inline_size(layout_context) -
2708                layout.pbm.padding_border_sums.inline,
2709        );
2710
2711        InlineContentSizesResult {
2712            sizes: grid_content_sizes.max(caption_content_sizes),
2713            depends_on_block_constraints: false,
2714        }
2715    }
2716}
2717
2718impl Table {
2719    #[inline]
2720    pub(crate) fn layout_style<'a>(
2721        &'a self,
2722        layout: Option<&'a TableLayout<'a>>,
2723    ) -> LayoutStyle<'a> {
2724        LayoutStyle::Table(TableLayoutStyle {
2725            table: self,
2726            layout,
2727        })
2728    }
2729
2730    #[inline]
2731    pub(crate) fn layout_style_for_grid(&self) -> LayoutStyle<'_> {
2732        LayoutStyle::Default(&self.grid_style)
2733    }
2734}
2735
2736impl TableTrack {
2737    #[inline]
2738    pub(crate) fn layout_style(&self) -> LayoutStyle<'_> {
2739        LayoutStyle::Default(&self.base.style)
2740    }
2741}
2742
2743impl TableTrackGroup {
2744    #[inline]
2745    pub(crate) fn layout_style(&self) -> LayoutStyle<'_> {
2746        LayoutStyle::Default(&self.base.style)
2747    }
2748}
2749
2750impl TableLayoutStyle<'_> {
2751    #[inline]
2752    pub(crate) fn style(&self) -> &ComputedValues {
2753        &self.table.style
2754    }
2755
2756    #[inline]
2757    pub(crate) fn collapses_borders(&self) -> bool {
2758        self.style().get_inherited_table().border_collapse == BorderCollapse::Collapse
2759    }
2760
2761    pub(crate) fn halved_collapsed_border_widths(&self) -> LogicalSides<Au> {
2762        debug_assert!(self.collapses_borders());
2763        let area = LogicalSides {
2764            inline_start: 0,
2765            inline_end: self.table.size.width,
2766            block_start: 0,
2767            block_end: self.table.size.height,
2768        };
2769        if let Some(layout) = self.layout {
2770            layout.get_collapsed_border_widths_for_area(area)
2771        } else {
2772            // TODO: this should be cached.
2773            let mut layout = TableLayout::new(self.table);
2774            layout.compute_border_collapse(self.style().writing_mode);
2775            layout.get_collapsed_border_widths_for_area(area)
2776        }
2777        .expect("Collapsed borders should be computed")
2778    }
2779}
2780
2781impl TableSlotCell {
2782    #[inline]
2783    fn layout_style(&self) -> LayoutStyle<'_> {
2784        self.contents.layout_style(&self.base)
2785    }
2786
2787    fn effective_vertical_align(&self) -> VerticalAlignKeyword {
2788        match self.base.style.clone_vertical_align() {
2789            VerticalAlign::Keyword(VerticalAlignKeyword::Top) => VerticalAlignKeyword::Top,
2790            VerticalAlign::Keyword(VerticalAlignKeyword::Bottom) => VerticalAlignKeyword::Bottom,
2791            VerticalAlign::Keyword(VerticalAlignKeyword::Middle) => VerticalAlignKeyword::Middle,
2792            _ => VerticalAlignKeyword::Baseline,
2793        }
2794    }
2795
2796    fn inline_content_sizes(&self, layout_context: &LayoutContext) -> ContentSizes {
2797        let constraint_space = ConstraintSpace::new_for_style_and_ratio(
2798            &self.base.style,
2799            None, /* TODO: support preferred aspect ratios on non-replaced boxes */
2800        );
2801        self.base
2802            .inline_content_sizes(layout_context, &constraint_space, &self.contents.contents)
2803            .sizes
2804    }
2805
2806    #[allow(clippy::too_many_arguments)]
2807    fn create_fragment(
2808        &self,
2809        mut layout: CellLayout,
2810        cell_rect: LogicalRect<Au>,
2811        cell_baseline: Au,
2812        positioning_context: &mut PositioningContext,
2813        table_style: &ComputedValues,
2814        containing_block: &ContainingBlock,
2815        is_collapsed: bool,
2816    ) -> BoxFragment {
2817        // This must be scoped to this function because it conflicts with euclid's Zero.
2818        use style::Zero as StyleZero;
2819
2820        let cell_content_rect = cell_rect.deflate(&(layout.padding + layout.border));
2821        let content_block_size = layout.layout.content_block_size;
2822        let free_space = || Au::zero().max(cell_content_rect.size.block - content_block_size);
2823        let vertical_align_offset = match self.effective_vertical_align() {
2824            VerticalAlignKeyword::Top => Au::zero(),
2825            VerticalAlignKeyword::Bottom => free_space(),
2826            VerticalAlignKeyword::Middle => free_space().scale_by(0.5),
2827            _ => {
2828                cell_baseline -
2829                    (layout.padding.block_start + layout.border.block_start) -
2830                    layout.ascent()
2831            },
2832        };
2833
2834        let mut base_fragment_info = self.base.base_fragment_info;
2835        if self.base.style.get_inherited_table().empty_cells == EmptyCells::Hide &&
2836            table_style.get_inherited_table().border_collapse != BorderCollapse::Collapse &&
2837            layout.is_empty_for_empty_cells()
2838        {
2839            base_fragment_info.flags.insert(FragmentFlags::DO_NOT_PAINT);
2840        }
2841
2842        if is_collapsed {
2843            base_fragment_info.flags.insert(FragmentFlags::IS_COLLAPSED);
2844        }
2845
2846        // Create an `AnonymousFragment` to move the cell contents to the cell baseline.
2847        let mut vertical_align_fragment_rect = cell_content_rect;
2848        vertical_align_fragment_rect.start_corner = LogicalVec2 {
2849            inline: Au::zero(),
2850            block: vertical_align_offset,
2851        };
2852        let vertical_align_fragment = PositioningFragment::new_anonymous(
2853            self.base.style.clone(),
2854            vertical_align_fragment_rect.as_physical(None),
2855            layout.layout.fragments,
2856        );
2857
2858        // Adjust the static position of all absolute children based on the
2859        // final content rect of this fragment. Note that we are not shifting by the position of the
2860        // Anonymous fragment we use to shift content to the baseline.
2861        //
2862        // TODO(mrobinson): This is correct for absolutes that are direct children of the table
2863        // cell, but wrong for absolute fragments that are more deeply nested in the hierarchy of
2864        // fragments.
2865        let physical_cell_rect = cell_content_rect.as_physical(Some(containing_block));
2866        layout
2867            .positioning_context
2868            .adjust_static_position_of_hoisted_fragments_with_offset(
2869                &physical_cell_rect.origin.to_vector(),
2870                PositioningContextLength::zero(),
2871            );
2872        positioning_context.append(layout.positioning_context);
2873
2874        let specific_layout_info = (table_style.get_inherited_table().border_collapse ==
2875            BorderCollapse::Collapse)
2876            .then_some(SpecificLayoutInfo::TableCellWithCollapsedBorders);
2877
2878        BoxFragment::new(
2879            base_fragment_info,
2880            self.base.style.clone(),
2881            vec![Fragment::Positioning(vertical_align_fragment)],
2882            physical_cell_rect,
2883            layout.padding.to_physical(table_style.writing_mode),
2884            layout.border.to_physical(table_style.writing_mode),
2885            PhysicalSides::zero(), /* margin */
2886            specific_layout_info,
2887        )
2888        .with_baselines(layout.layout.baselines)
2889    }
2890}
2891
2892fn get_size_percentage_contribution(
2893    size: &LogicalVec2<Size<ComputedLengthPercentage>>,
2894    max_size: &LogicalVec2<Size<ComputedLengthPercentage>>,
2895) -> LogicalVec2<Option<Percentage>> {
2896    // From <https://drafts.csswg.org/css-tables/#percentage-contribution>
2897    // > The percentage contribution of a table cell, column, or column group is defined
2898    // > in terms of the computed values of width and max-width that have computed values
2899    // > that are percentages:
2900    // >    min(percentage width, percentage max-width).
2901    // > If the computed values are not percentages, then 0% is used for width, and an
2902    // > infinite percentage is used for max-width.
2903    LogicalVec2 {
2904        inline: max_two_optional_percentages(
2905            size.inline.to_percentage(),
2906            max_size.inline.to_percentage(),
2907        ),
2908        block: max_two_optional_percentages(
2909            size.block.to_percentage(),
2910            max_size.block.to_percentage(),
2911        ),
2912    }
2913}
2914
2915struct CellOrColumnOuterSizes {
2916    min: LogicalVec2<Au>,
2917    preferred: LogicalVec2<Au>,
2918    max: LogicalVec2<Option<Au>>,
2919    percentage: LogicalVec2<Option<Percentage>>,
2920}
2921
2922impl CellOrColumnOuterSizes {
2923    fn new(
2924        style: &Arc<ComputedValues>,
2925        writing_mode: WritingMode,
2926        padding_border_sums: &LogicalVec2<Au>,
2927        is_in_fixed_mode: bool,
2928    ) -> Self {
2929        let box_sizing = style.get_position().box_sizing;
2930        let outer_size = |size: LogicalVec2<Au>| match box_sizing {
2931            BoxSizing::ContentBox => size + *padding_border_sums,
2932            BoxSizing::BorderBox => LogicalVec2 {
2933                inline: size.inline.max(padding_border_sums.inline),
2934                block: size.block.max(padding_border_sums.block),
2935            },
2936        };
2937
2938        let outer_option_size = |size: LogicalVec2<Option<Au>>| match box_sizing {
2939            BoxSizing::ContentBox => size.map_inline_and_block_axes(
2940                |inline| inline.map(|inline| inline + padding_border_sums.inline),
2941                |block| block.map(|block| block + padding_border_sums.block),
2942            ),
2943            BoxSizing::BorderBox => size.map_inline_and_block_axes(
2944                |inline| inline.map(|inline| inline.max(padding_border_sums.inline)),
2945                |block| block.map(|block| block.max(padding_border_sums.block)),
2946            ),
2947        };
2948
2949        let get_size_for_axis = |size: &Size<ComputedLengthPercentage>| {
2950            // Note that measures treat all size values other than <length>
2951            // as the initial value of the property.
2952            size.to_numeric()
2953                .and_then(|length_percentage| length_percentage.to_length())
2954                .map(Au::from)
2955        };
2956
2957        let size = style.box_size(writing_mode);
2958        if is_in_fixed_mode {
2959            return Self {
2960                percentage: size.map(|v| v.to_percentage()),
2961                preferred: outer_option_size(size.map(get_size_for_axis))
2962                    .map(|v| v.unwrap_or_default()),
2963                min: LogicalVec2::default(),
2964                max: LogicalVec2::default(),
2965            };
2966        }
2967
2968        let min_size = style.min_box_size(writing_mode);
2969        let max_size = style.max_box_size(writing_mode);
2970
2971        Self {
2972            min: outer_size(min_size.map(|v| get_size_for_axis(v).unwrap_or_default())),
2973            preferred: outer_size(size.map(|v| get_size_for_axis(v).unwrap_or_default())),
2974            max: outer_option_size(max_size.map(get_size_for_axis)),
2975            percentage: get_size_percentage_contribution(&size, &max_size),
2976        }
2977    }
2978}
2979
2980struct RowspanToDistribute<'a> {
2981    coordinates: TableSlotCoordinates,
2982    cell: AtomicRef<'a, TableSlotCell>,
2983    measure: &'a CellOrTrackMeasure,
2984}
2985
2986impl RowspanToDistribute<'_> {
2987    fn range(&self) -> Range<usize> {
2988        self.coordinates.y..self.coordinates.y + self.cell.rowspan
2989    }
2990
2991    fn fully_encloses(&self, other: &RowspanToDistribute) -> bool {
2992        other.coordinates.y > self.coordinates.y && other.range().end < self.range().end
2993    }
2994}
2995
2996/// The inline size constraints provided by a cell that span multiple columns (`colspan` > 1).
2997/// These constraints are distributed to the individual columns that make up this cell's span.
2998#[derive(Debug)]
2999struct ColspanToDistribute {
3000    starting_column: usize,
3001    span: usize,
3002    content_sizes: ContentSizes,
3003    percentage: Option<Percentage>,
3004}
3005
3006impl ColspanToDistribute {
3007    /// A comparison function to sort the colspan cell constraints primarily by their span
3008    /// width and secondarily by their starting column. This is not an implementation of
3009    /// `PartialOrd` because we want to return [`Ordering::Equal`] even if `self != other`.
3010    fn comparison_for_sort(a: &Self, b: &Self) -> Ordering {
3011        a.span
3012            .cmp(&b.span)
3013            .then_with(|| b.starting_column.cmp(&b.starting_column))
3014    }
3015
3016    fn range(&self) -> Range<usize> {
3017        self.starting_column..self.starting_column + self.span
3018    }
3019}