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 = (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 = 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 = containing_block_for_children.size.block.definite_or_min();
1476
1477        let block_border_spacing = self.table.total_border_spacing().block;
1478        let table_height_from_rows = row_sizes.iter().sum::<Au>() + block_border_spacing;
1479        self.final_table_height = table_height_from_rows.max(table_height_from_style);
1480
1481        // If the table height is defined by the rows sizes, there is no extra space to distribute
1482        // to rows.
1483        if self.final_table_height == table_height_from_rows {
1484            self.row_sizes = row_sizes;
1485            return;
1486        }
1487
1488        // There was extra block size added to the table from the table style, so distribute this
1489        // extra space to rows using the same distribution algorithm used for distributing rowspan
1490        // space.
1491        // TODO: This should first distribute space to row groups and then to rows.
1492        self.distribute_extra_size_to_rows(
1493            self.final_table_height - table_height_from_rows,
1494            0..self.table.size.height,
1495            &mut row_sizes,
1496            Some(self.final_table_height),
1497            false, /* rowspan_distribution */
1498        );
1499        self.row_sizes = row_sizes;
1500    }
1501
1502    fn layout_caption(
1503        &self,
1504        caption: &TableCaption,
1505        layout_context: &LayoutContext,
1506        parent_positioning_context: &mut PositioningContext,
1507    ) -> BoxFragment {
1508        let containing_block = &ContainingBlock {
1509            size: ContainingBlockSize {
1510                inline: self.table_width + self.pbm.padding_border_sums.inline,
1511                block: SizeConstraint::default(),
1512            },
1513            style: &self.table.style,
1514        };
1515
1516        // The parent of a caption is the table wrapper, which establishes an independent
1517        // formatting context. Therefore, we don't ignore block margins when resolving a
1518        // stretch block size. https://drafts.csswg.org/css-sizing-4/#stretch-fit-sizing
1519        let ignore_block_margins_for_stretch = LogicalSides1D::new(false, false);
1520
1521        let mut positioning_context =
1522            PositioningContext::new_for_layout_box_base(&caption.context.base);
1523        let mut box_fragment = caption.context.layout_in_flow_block_level(
1524            layout_context,
1525            positioning_context
1526                .as_mut()
1527                .unwrap_or(parent_positioning_context),
1528            containing_block,
1529            None, /* sequential_layout_state */
1530            ignore_block_margins_for_stretch,
1531        );
1532
1533        if let Some(mut positioning_context) = positioning_context.take() {
1534            positioning_context.layout_collected_children(layout_context, &mut box_fragment);
1535            parent_positioning_context.append(positioning_context);
1536        }
1537
1538        box_fragment
1539    }
1540
1541    /// Lay out the table (grid and captions) of this [`TableLayout`] into fragments. This should
1542    /// only be be called after calling [`TableLayout.compute_measures`].
1543    #[servo_tracing::instrument(name = "Table::layout", skip_all)]
1544    fn layout(
1545        mut self,
1546        layout_context: &LayoutContext,
1547        positioning_context: &mut PositioningContext,
1548        containing_block_for_children: &ContainingBlock,
1549        containing_block_for_table: &ContainingBlock,
1550    ) -> CacheableLayoutResult {
1551        let table_writing_mode = containing_block_for_children.style.writing_mode;
1552        self.compute_border_collapse(table_writing_mode);
1553        let layout_style = self.table.layout_style(Some(&self));
1554
1555        self.pbm = layout_style
1556            .padding_border_margin_with_writing_mode_and_containing_block_inline_size(
1557                table_writing_mode,
1558                containing_block_for_table.size.inline,
1559            );
1560        self.compute_measures(layout_context, table_writing_mode);
1561        self.compute_table_width(containing_block_for_children);
1562
1563        // The table wrapper is the one that has the CSS properties for the grid's border and padding. This
1564        // weirdness is difficult to express in Servo's layout system. We have the wrapper size itself as if
1565        // those properties applied to it and then just account for the discrepency in sizing here. In reality,
1566        // the wrapper does not draw borders / backgrounds and all of its content (grid and captions) are
1567        // placed with a negative offset in the table wrapper's content box so that they overlap the undrawn
1568        // border / padding area.
1569        //
1570        // TODO: This is a pretty large hack. It would be nicer to actually have the grid sized properly,
1571        // but it works for now.
1572        //
1573        // Get the padding, border, and margin of the table using the inline size of the table's containing
1574        // block but in the writing of the table itself.
1575        // TODO: This is broken for orthoganol flows, because the inline size of the parent isn't necessarily
1576        // the inline size of the table.
1577        let containing_block_for_logical_conversion = ContainingBlock {
1578            size: ContainingBlockSize {
1579                inline: self.table_width,
1580                block: containing_block_for_table.size.block,
1581            },
1582            style: containing_block_for_children.style,
1583        };
1584        let offset_from_wrapper = -self.pbm.padding - self.pbm.border;
1585        let mut current_block_offset = offset_from_wrapper.block_start;
1586
1587        let mut table_layout = CacheableLayoutResult {
1588            fragments: Vec::new(),
1589            content_block_size: Zero::zero(),
1590            content_inline_size_for_table: None,
1591            baselines: Baselines::default(),
1592            depends_on_block_constraints: true,
1593            specific_layout_info: Some(SpecificLayoutInfo::TableWrapper),
1594            collapsible_margins_in_children: CollapsedBlockMargins::zero(),
1595        };
1596
1597        #[derive(EnumIter, PartialEq)]
1598        enum TableWrapperSection {
1599            TopCaptions,
1600            Grid,
1601            BottomCaptions,
1602        }
1603        impl TableWrapperSection {
1604            fn accepts_caption(&self, caption: &TableCaption) -> bool {
1605                match caption.context.style().clone_caption_side() {
1606                    CaptionSide::Top => *self == TableWrapperSection::TopCaptions,
1607                    CaptionSide::Bottom => *self == TableWrapperSection::BottomCaptions,
1608                }
1609            }
1610        }
1611
1612        for section in TableWrapperSection::iter() {
1613            if section == TableWrapperSection::Grid {
1614                let original_positioning_context_length = positioning_context.len();
1615                let mut grid_fragment = self.layout_grid(
1616                    layout_context,
1617                    positioning_context,
1618                    &containing_block_for_logical_conversion,
1619                    containing_block_for_children,
1620                );
1621
1622                // Take the baseline of the grid fragment, after adjusting it to be in the coordinate system
1623                // of the table wrapper.
1624                let logical_grid_content_rect = grid_fragment
1625                    .content_rect
1626                    .to_logical(&containing_block_for_logical_conversion);
1627                let grid_pbm = grid_fragment
1628                    .padding_border_margin()
1629                    .to_logical(table_writing_mode);
1630                table_layout.baselines = grid_fragment.baselines(table_writing_mode).offset(
1631                    current_block_offset +
1632                        logical_grid_content_rect.start_corner.block +
1633                        grid_pbm.block_start,
1634                );
1635
1636                grid_fragment.content_rect = LogicalRect {
1637                    start_corner: LogicalVec2 {
1638                        inline: offset_from_wrapper.inline_start + grid_pbm.inline_start,
1639                        block: current_block_offset + grid_pbm.block_start,
1640                    },
1641                    size: grid_fragment
1642                        .content_rect
1643                        .size
1644                        .to_logical(table_writing_mode),
1645                }
1646                .as_physical(Some(&containing_block_for_logical_conversion));
1647
1648                current_block_offset += grid_fragment
1649                    .border_rect()
1650                    .size
1651                    .to_logical(table_writing_mode)
1652                    .block;
1653                if logical_grid_content_rect.size.inline < self.table_width {
1654                    // This can happen when collapsing columns
1655                    table_layout.content_inline_size_for_table =
1656                        Some(logical_grid_content_rect.size.inline);
1657                }
1658
1659                let grid_fragment = Fragment::Box(ArcRefCell::new(grid_fragment));
1660                positioning_context.adjust_static_position_of_hoisted_fragments(
1661                    &grid_fragment,
1662                    original_positioning_context_length,
1663                );
1664                table_layout.fragments.push(grid_fragment);
1665            } else {
1666                let caption_fragments = self.table.captions.iter().filter_map(|caption| {
1667                    let caption = caption.borrow();
1668                    if !section.accepts_caption(&caption) {
1669                        return None;
1670                    }
1671
1672                    let original_positioning_context_length = positioning_context.len();
1673                    let mut caption_fragment =
1674                        self.layout_caption(&caption, layout_context, positioning_context);
1675
1676                    // The caption is not placed yet. Construct a rectangle for it in the adjusted containing block
1677                    // for the table children and only then convert the result to physical geometry.
1678                    let caption_pbm = caption_fragment
1679                        .padding_border_margin()
1680                        .to_logical(table_writing_mode);
1681
1682                    let caption_relative_offset = match caption_fragment.style.clone_position() {
1683                        Position::Relative => relative_adjustement(
1684                            &caption_fragment.style,
1685                            containing_block_for_children,
1686                        ),
1687                        _ => LogicalVec2::zero(),
1688                    };
1689
1690                    caption_fragment.content_rect = LogicalRect {
1691                        start_corner: LogicalVec2 {
1692                            inline: offset_from_wrapper.inline_start + caption_pbm.inline_start,
1693                            block: current_block_offset + caption_pbm.block_start,
1694                        } + caption_relative_offset,
1695                        size: caption_fragment
1696                            .content_rect
1697                            .size
1698                            .to_logical(table_writing_mode),
1699                    }
1700                    .as_physical(Some(&containing_block_for_logical_conversion));
1701
1702                    current_block_offset += caption_fragment
1703                        .margin_rect()
1704                        .size
1705                        .to_logical(table_writing_mode)
1706                        .block;
1707
1708                    let caption_fragment = Fragment::Box(ArcRefCell::new(caption_fragment));
1709                    positioning_context.adjust_static_position_of_hoisted_fragments(
1710                        &caption_fragment,
1711                        original_positioning_context_length,
1712                    );
1713
1714                    caption.context.base.set_fragment(caption_fragment.clone());
1715                    Some(caption_fragment)
1716                });
1717                table_layout.fragments.extend(caption_fragments);
1718            }
1719        }
1720
1721        table_layout.content_block_size = current_block_offset + offset_from_wrapper.block_end;
1722        table_layout
1723    }
1724
1725    /// Lay out the grid portion of this [`TableLayout`] into fragments. This should only be be
1726    /// called after calling [`TableLayout.compute_measures`].
1727    fn layout_grid(
1728        &mut self,
1729        layout_context: &LayoutContext,
1730        positioning_context: &mut PositioningContext,
1731        containing_block_for_logical_conversion: &ContainingBlock,
1732        containing_block_for_children: &ContainingBlock,
1733    ) -> BoxFragment {
1734        self.distributed_column_widths =
1735            Self::distribute_width_to_columns(self.assignable_width, &self.columns);
1736        self.layout_cells_in_row(layout_context, containing_block_for_children);
1737        let table_writing_mode = containing_block_for_children.style.writing_mode;
1738        let first_layout_row_heights = self.do_first_row_layout(table_writing_mode);
1739        self.compute_table_height_and_final_row_heights(
1740            first_layout_row_heights,
1741            containing_block_for_children,
1742        );
1743
1744        assert_eq!(self.table.size.height, self.row_sizes.len());
1745        assert_eq!(self.table.size.width, self.distributed_column_widths.len());
1746
1747        if self.table.size.width == 0 && self.table.size.height == 0 {
1748            let content_rect = LogicalRect {
1749                start_corner: LogicalVec2::zero(),
1750                size: LogicalVec2 {
1751                    inline: self.table_width,
1752                    block: self.final_table_height,
1753                },
1754            }
1755            .as_physical(Some(containing_block_for_logical_conversion));
1756            return BoxFragment::new(
1757                self.table.grid_base_fragment_info,
1758                self.table.grid_style.clone(),
1759                Vec::new(),
1760                content_rect,
1761                self.pbm.padding.to_physical(table_writing_mode),
1762                self.pbm.border.to_physical(table_writing_mode),
1763                PhysicalSides::zero(),
1764                self.specific_layout_info_for_grid(),
1765            );
1766        }
1767
1768        let mut table_fragments = Vec::new();
1769        let table_and_track_dimensions = TableAndTrackDimensions::new(self);
1770        self.make_fragments_for_columns_and_column_groups(
1771            &table_and_track_dimensions,
1772            &mut table_fragments,
1773        );
1774
1775        let mut baselines = Baselines::default();
1776        let mut row_group_fragment_layout = None;
1777        for row_index in 0..self.table.size.height {
1778            // From <https://drafts.csswg.org/css-align-3/#baseline-export>
1779            // > If any cells in the row participate in first baseline/last baseline alignment along
1780            // > the inline axis, the first/last baseline set of the row is generated from their
1781            // > shared alignment baseline and the row’s first available font, after alignment has
1782            // > been performed. Otherwise, the first/last baseline set of the row is synthesized from
1783            // > the lowest and highest content edges of the cells in the row. [CSS2]
1784            //
1785            // If any cell below has baseline alignment, these values will be overwritten,
1786            // but they are initialized to the content edge of the first row.
1787            if row_index == 0 {
1788                let row_end = table_and_track_dimensions
1789                    .get_row_rect(0)
1790                    .max_block_position();
1791                baselines.first = Some(row_end);
1792                baselines.last = Some(row_end);
1793            }
1794
1795            let row_is_collapsed = self.is_row_collapsed(row_index);
1796            let table_row = self.table.rows[row_index].borrow();
1797            let mut row_fragment_layout = RowFragmentLayout::new(
1798                &table_row,
1799                row_index,
1800                &table_and_track_dimensions,
1801                &self.table.style,
1802            );
1803
1804            let old_row_group_index = row_group_fragment_layout
1805                .as_ref()
1806                .map(|layout: &RowGroupFragmentLayout| layout.index);
1807            if table_row.group_index != old_row_group_index {
1808                // First create the Fragment for any existing RowGroupFragmentLayout.
1809                if let Some(old_row_group_layout) = row_group_fragment_layout.take() {
1810                    table_fragments.push(old_row_group_layout.finish(
1811                        layout_context,
1812                        positioning_context,
1813                        containing_block_for_logical_conversion,
1814                        containing_block_for_children,
1815                    ));
1816                }
1817
1818                // Then, create a new RowGroupFragmentLayout for the current and potentially subsequent rows.
1819                if let Some(new_group_index) = table_row.group_index {
1820                    row_group_fragment_layout = Some(RowGroupFragmentLayout::new(
1821                        self.table.row_groups[new_group_index].clone(),
1822                        new_group_index,
1823                        &table_and_track_dimensions,
1824                    ));
1825                }
1826            }
1827
1828            let column_indices = 0..self.table.size.width;
1829            row_fragment_layout.fragments.reserve(self.table.size.width);
1830            for column_index in column_indices {
1831                self.do_final_cell_layout(
1832                    row_index,
1833                    column_index,
1834                    &table_and_track_dimensions,
1835                    &mut baselines,
1836                    &mut row_fragment_layout,
1837                    row_group_fragment_layout.as_mut(),
1838                    positioning_context,
1839                    self.is_column_collapsed(column_index) || row_is_collapsed,
1840                );
1841            }
1842
1843            let row_fragment = row_fragment_layout.finish(
1844                layout_context,
1845                positioning_context,
1846                containing_block_for_logical_conversion,
1847                containing_block_for_children,
1848                &mut row_group_fragment_layout,
1849            );
1850
1851            match row_group_fragment_layout.as_mut() {
1852                Some(layout) => layout.fragments.push(row_fragment),
1853                None => table_fragments.push(row_fragment),
1854            }
1855        }
1856
1857        if let Some(row_group_layout) = row_group_fragment_layout.take() {
1858            table_fragments.push(row_group_layout.finish(
1859                layout_context,
1860                positioning_context,
1861                containing_block_for_logical_conversion,
1862                containing_block_for_children,
1863            ));
1864        }
1865
1866        let content_rect = LogicalRect {
1867            start_corner: LogicalVec2::zero(),
1868            size: LogicalVec2 {
1869                inline: table_and_track_dimensions.table_rect.max_inline_position(),
1870                block: table_and_track_dimensions.table_rect.max_block_position(),
1871            },
1872        }
1873        .as_physical(Some(containing_block_for_logical_conversion));
1874        BoxFragment::new(
1875            self.table.grid_base_fragment_info,
1876            self.table.grid_style.clone(),
1877            table_fragments,
1878            content_rect,
1879            self.pbm.padding.to_physical(table_writing_mode),
1880            self.pbm.border.to_physical(table_writing_mode),
1881            PhysicalSides::zero(),
1882            self.specific_layout_info_for_grid(),
1883        )
1884        .with_baselines(baselines)
1885    }
1886
1887    fn specific_layout_info_for_grid(&mut self) -> Option<SpecificLayoutInfo> {
1888        mem::take(&mut self.collapsed_borders).map(|mut collapsed_borders| {
1889            // TODO: It would probably be better to use `TableAndTrackDimensions`, since that
1890            // has already taken care of collapsed tracks and knows the final track positions.
1891            let mut track_sizes = LogicalVec2 {
1892                inline: mem::take(&mut self.distributed_column_widths),
1893                block: mem::take(&mut self.row_sizes),
1894            };
1895            for (column_index, column_size) in track_sizes.inline.iter_mut().enumerate() {
1896                if self.is_column_collapsed(column_index) {
1897                    mem::take(column_size);
1898                }
1899            }
1900            for (row_index, row_size) in track_sizes.block.iter_mut().enumerate() {
1901                if self.is_row_collapsed(row_index) {
1902                    mem::take(row_size);
1903                }
1904            }
1905            let writing_mode = self.table.style.writing_mode;
1906            if !writing_mode.is_bidi_ltr() {
1907                track_sizes.inline.reverse();
1908                collapsed_borders.inline.reverse();
1909                for border_line in &mut collapsed_borders.block {
1910                    border_line.reverse();
1911                }
1912            }
1913            SpecificLayoutInfo::TableGridWithCollapsedBorders(Box::new(SpecificTableGridInfo {
1914                collapsed_borders: if writing_mode.is_horizontal() {
1915                    PhysicalVec::new(collapsed_borders.inline, collapsed_borders.block)
1916                } else {
1917                    PhysicalVec::new(collapsed_borders.block, collapsed_borders.inline)
1918                },
1919                track_sizes: if writing_mode.is_horizontal() {
1920                    PhysicalVec::new(track_sizes.inline, track_sizes.block)
1921                } else {
1922                    PhysicalVec::new(track_sizes.block, track_sizes.inline)
1923                },
1924            }))
1925        })
1926    }
1927
1928    fn is_row_collapsed(&self, row_index: usize) -> bool {
1929        let Some(row) = &self.table.rows.get(row_index) else {
1930            return false;
1931        };
1932
1933        let row = row.borrow();
1934        if row.base.style.get_inherited_box().visibility == Visibility::Collapse {
1935            return true;
1936        }
1937        let row_group = match row.group_index {
1938            Some(group_index) => self.table.row_groups[group_index].borrow(),
1939            None => return false,
1940        };
1941        row_group.base.style.get_inherited_box().visibility == Visibility::Collapse
1942    }
1943
1944    fn is_column_collapsed(&self, column_index: usize) -> bool {
1945        let Some(column) = &self.table.columns.get(column_index) else {
1946            return false;
1947        };
1948        let column = column.borrow();
1949        if column.base.style.get_inherited_box().visibility == Visibility::Collapse {
1950            return true;
1951        }
1952        let col_group = match column.group_index {
1953            Some(group_index) => self.table.column_groups[group_index].borrow(),
1954            None => return false,
1955        };
1956        col_group.base.style.get_inherited_box().visibility == Visibility::Collapse
1957    }
1958
1959    #[allow(clippy::too_many_arguments)]
1960    fn do_final_cell_layout(
1961        &mut self,
1962        row_index: usize,
1963        column_index: usize,
1964        dimensions: &TableAndTrackDimensions,
1965        baselines: &mut Baselines,
1966        row_fragment_layout: &mut RowFragmentLayout,
1967        row_group_fragment_layout: Option<&mut RowGroupFragmentLayout>,
1968        positioning_context_for_table: &mut PositioningContext,
1969        is_collapsed: bool,
1970    ) {
1971        // The PositioningContext for cells is, in order or preference, the PositioningContext of the row,
1972        // the PositioningContext of the row group, or the PositioningContext of the table.
1973        let row_group_positioning_context =
1974            row_group_fragment_layout.and_then(|layout| layout.positioning_context.as_mut());
1975        let positioning_context = row_fragment_layout
1976            .positioning_context
1977            .as_mut()
1978            .or(row_group_positioning_context)
1979            .unwrap_or(positioning_context_for_table);
1980
1981        let layout = match self.cells_laid_out[row_index][column_index].take() {
1982            Some(layout) => layout,
1983            None => {
1984                return;
1985            },
1986        };
1987        let cell = match self.table.slots[row_index][column_index] {
1988            TableSlot::Cell(ref cell) => cell,
1989            _ => {
1990                warn!("Did not find a non-spanned cell at index with layout.");
1991                return;
1992            },
1993        }
1994        .borrow();
1995
1996        // If this cell has baseline alignment, it can adjust the table's overall baseline.
1997        let row_block_offset = row_fragment_layout.rect.start_corner.block;
1998        let row_baseline = self.row_baselines[row_index];
1999        if cell.effective_vertical_align() == VerticalAlignKeyword::Baseline && !layout.is_empty() {
2000            let baseline = row_block_offset + row_baseline;
2001            if row_index == 0 {
2002                baselines.first = Some(baseline);
2003            }
2004            baselines.last = Some(baseline);
2005        }
2006        let mut row_relative_cell_rect = dimensions.get_cell_rect(
2007            TableSlotCoordinates::new(column_index, row_index),
2008            cell.rowspan,
2009            cell.colspan,
2010        );
2011        row_relative_cell_rect.start_corner -= row_fragment_layout.rect.start_corner;
2012        let mut fragment = cell.create_fragment(
2013            layout,
2014            row_relative_cell_rect,
2015            row_baseline,
2016            positioning_context,
2017            &self.table.style,
2018            &row_fragment_layout.containing_block,
2019            is_collapsed,
2020        );
2021
2022        // Make a table part rectangle relative to the row fragment for the purposes of
2023        // drawing extra backgrounds.
2024        //
2025        // This rectangle is an offset between the row fragment and the other table
2026        // part rectangle (row group, column, column group). Everything between them
2027        // is laid out in a left-to-right fashion, but respecting the verticality of
2028        // the writing mode. This is why below, only the axes are flipped, but the
2029        // rectangle is not flipped for RTL.
2030        let make_relative_to_row_start = |mut rect: LogicalRect<Au>| {
2031            rect.start_corner -= row_fragment_layout.rect.start_corner;
2032            let writing_mode = self.table.style.writing_mode;
2033            PhysicalRect::new(
2034                if writing_mode.is_horizontal() {
2035                    PhysicalPoint::new(rect.start_corner.inline, rect.start_corner.block)
2036                } else {
2037                    PhysicalPoint::new(rect.start_corner.block, rect.start_corner.inline)
2038                },
2039                rect.size.to_physical_size(writing_mode),
2040            )
2041        };
2042
2043        let column = self.table.columns.get(column_index);
2044        let column_group = column
2045            .and_then(|column| column.borrow().group_index)
2046            .and_then(|index| self.table.column_groups.get(index));
2047        if let Some(column_group) = column_group {
2048            let column_group = column_group.borrow();
2049            let rect = make_relative_to_row_start(dimensions.get_column_group_rect(&column_group));
2050            fragment.add_extra_background(ExtraBackground {
2051                style: column_group.shared_background_style.clone(),
2052                rect,
2053            })
2054        }
2055        if let Some(column) = column {
2056            let column = column.borrow();
2057            if !column.is_anonymous {
2058                let rect = make_relative_to_row_start(dimensions.get_column_rect(column_index));
2059                fragment.add_extra_background(ExtraBackground {
2060                    style: column.shared_background_style.clone(),
2061                    rect,
2062                })
2063            }
2064        }
2065        let row = self.table.rows.get(row_index);
2066        let row_group = row
2067            .and_then(|row| row.borrow().group_index)
2068            .and_then(|index| self.table.row_groups.get(index));
2069        if let Some(row_group) = row_group {
2070            let rect =
2071                make_relative_to_row_start(dimensions.get_row_group_rect(&row_group.borrow()));
2072            fragment.add_extra_background(ExtraBackground {
2073                style: row_group.borrow().shared_background_style.clone(),
2074                rect,
2075            })
2076        }
2077        if let Some(row) = row {
2078            let row = row.borrow();
2079            let rect = make_relative_to_row_start(row_fragment_layout.rect);
2080            fragment.add_extra_background(ExtraBackground {
2081                style: row.shared_background_style.clone(),
2082                rect,
2083            })
2084        }
2085
2086        let fragment = Fragment::Box(ArcRefCell::new(fragment));
2087        cell.base.set_fragment(fragment.clone());
2088        row_fragment_layout.fragments.push(fragment);
2089    }
2090
2091    fn make_fragments_for_columns_and_column_groups(
2092        &self,
2093        dimensions: &TableAndTrackDimensions,
2094        fragments: &mut Vec<Fragment>,
2095    ) {
2096        for column_group in self.table.column_groups.iter() {
2097            let column_group = column_group.borrow();
2098            if !column_group.is_empty() {
2099                let fragment = Fragment::Positioning(PositioningFragment::new_empty(
2100                    column_group.base.base_fragment_info,
2101                    dimensions
2102                        .get_column_group_rect(&column_group)
2103                        .as_physical(None),
2104                    column_group.base.style.clone(),
2105                ));
2106                column_group.base.set_fragment(fragment.clone());
2107                fragments.push(fragment);
2108            }
2109        }
2110
2111        for (column_index, column) in self.table.columns.iter().enumerate() {
2112            let column = column.borrow();
2113            let fragment = Fragment::Positioning(PositioningFragment::new_empty(
2114                column.base.base_fragment_info,
2115                dimensions.get_column_rect(column_index).as_physical(None),
2116                column.base.style.clone(),
2117            ));
2118            column.base.set_fragment(fragment.clone());
2119            fragments.push(fragment);
2120        }
2121    }
2122
2123    fn compute_border_collapse(&mut self, writing_mode: WritingMode) {
2124        if self.table.style.get_inherited_table().border_collapse != BorderCollapse::Collapse {
2125            self.collapsed_borders = None;
2126            return;
2127        }
2128
2129        let mut collapsed_borders = LogicalVec2 {
2130            block: vec![
2131                vec![Default::default(); self.table.size.width];
2132                self.table.size.height + 1
2133            ],
2134            inline: vec![
2135                vec![Default::default(); self.table.size.height];
2136                self.table.size.width + 1
2137            ],
2138        };
2139
2140        let apply_border = |collapsed_borders: &mut CollapsedBorders,
2141                            layout_style: &LayoutStyle,
2142                            block: &Range<usize>,
2143                            inline: &Range<usize>| {
2144            let border = CollapsedBorder::from_layout_style(layout_style, writing_mode);
2145            border
2146                .block_start
2147                .max_assign_to_slice(&mut collapsed_borders.block[block.start][inline.clone()]);
2148            border
2149                .block_end
2150                .max_assign_to_slice(&mut collapsed_borders.block[block.end][inline.clone()]);
2151            border
2152                .inline_start
2153                .max_assign_to_slice(&mut collapsed_borders.inline[inline.start][block.clone()]);
2154            border
2155                .inline_end
2156                .max_assign_to_slice(&mut collapsed_borders.inline[inline.end][block.clone()]);
2157        };
2158        let hide_inner_borders = |collapsed_borders: &mut CollapsedBorders,
2159                                  block: &Range<usize>,
2160                                  inline: &Range<usize>| {
2161            for x in inline.clone() {
2162                for y in block.clone() {
2163                    if x != inline.start {
2164                        collapsed_borders.inline[x][y].hide();
2165                    }
2166                    if y != block.start {
2167                        collapsed_borders.block[y][x].hide();
2168                    }
2169                }
2170            }
2171        };
2172        let all_rows = 0..self.table.size.height;
2173        let all_columns = 0..self.table.size.width;
2174        for row_index in all_rows.clone() {
2175            for column_index in all_columns.clone() {
2176                let cell = match self.table.slots[row_index][column_index] {
2177                    TableSlot::Cell(ref cell) => cell,
2178                    _ => continue,
2179                }
2180                .borrow();
2181                let block_range = row_index..row_index + cell.rowspan;
2182                let inline_range = column_index..column_index + cell.colspan;
2183                hide_inner_borders(&mut collapsed_borders, &block_range, &inline_range);
2184                apply_border(
2185                    &mut collapsed_borders,
2186                    &cell.layout_style(),
2187                    &block_range,
2188                    &inline_range,
2189                );
2190            }
2191        }
2192        for (row_index, row) in self.table.rows.iter().enumerate() {
2193            let row = row.borrow();
2194            apply_border(
2195                &mut collapsed_borders,
2196                &row.layout_style(),
2197                &(row_index..row_index + 1),
2198                &all_columns,
2199            );
2200        }
2201        for row_group in &self.table.row_groups {
2202            let row_group = row_group.borrow();
2203            apply_border(
2204                &mut collapsed_borders,
2205                &row_group.layout_style(),
2206                &row_group.track_range,
2207                &all_columns,
2208            );
2209        }
2210        for (column_index, column) in self.table.columns.iter().enumerate() {
2211            let column = column.borrow();
2212            apply_border(
2213                &mut collapsed_borders,
2214                &column.layout_style(),
2215                &all_rows,
2216                &(column_index..column_index + 1),
2217            );
2218        }
2219        for column_group in &self.table.column_groups {
2220            let column_group = column_group.borrow();
2221            apply_border(
2222                &mut collapsed_borders,
2223                &column_group.layout_style(),
2224                &all_rows,
2225                &column_group.track_range,
2226            );
2227        }
2228        apply_border(
2229            &mut collapsed_borders,
2230            &self.table.layout_style_for_grid(),
2231            &all_rows,
2232            &all_columns,
2233        );
2234
2235        self.collapsed_borders = Some(collapsed_borders);
2236    }
2237
2238    fn get_collapsed_border_widths_for_area(
2239        &self,
2240        area: LogicalSides<usize>,
2241    ) -> Option<LogicalSides<Au>> {
2242        let collapsed_borders = self.collapsed_borders.as_ref()?;
2243        let columns = || area.inline_start..area.inline_end;
2244        let rows = || area.block_start..area.block_end;
2245        let max_width = |slice: &[CollapsedBorder]| {
2246            let slice_widths = slice.iter().map(|collapsed_border| collapsed_border.width);
2247            slice_widths.max().unwrap_or_default()
2248        };
2249        Some(area.map_inline_and_block_axes(
2250            |column| max_width(&collapsed_borders.inline[*column][rows()]) / 2,
2251            |row| max_width(&collapsed_borders.block[*row][columns()]) / 2,
2252        ))
2253    }
2254}
2255
2256struct RowFragmentLayout<'a> {
2257    row: &'a TableTrack,
2258    rect: LogicalRect<Au>,
2259    containing_block: ContainingBlock<'a>,
2260    positioning_context: Option<PositioningContext>,
2261    fragments: Vec<Fragment>,
2262}
2263
2264impl<'a> RowFragmentLayout<'a> {
2265    fn new(
2266        table_row: &'a TableTrack,
2267        index: usize,
2268        dimensions: &TableAndTrackDimensions,
2269        table_style: &'a ComputedValues,
2270    ) -> Self {
2271        let rect = dimensions.get_row_rect(index);
2272        let containing_block = ContainingBlock {
2273            size: ContainingBlockSize {
2274                inline: rect.size.inline,
2275                block: SizeConstraint::Definite(rect.size.block),
2276            },
2277            style: table_style,
2278        };
2279        Self {
2280            row: table_row,
2281            rect,
2282            positioning_context: PositioningContext::new_for_layout_box_base(&table_row.base),
2283            containing_block,
2284            fragments: Vec::new(),
2285        }
2286    }
2287    fn finish(
2288        mut self,
2289        layout_context: &LayoutContext,
2290        table_positioning_context: &mut PositioningContext,
2291        containing_block_for_logical_conversion: &ContainingBlock,
2292        containing_block_for_children: &ContainingBlock,
2293        row_group_fragment_layout: &mut Option<RowGroupFragmentLayout>,
2294    ) -> Fragment {
2295        if self.positioning_context.is_some() {
2296            self.rect.start_corner +=
2297                relative_adjustement(&self.row.base.style, containing_block_for_children);
2298        }
2299
2300        let (inline_size, block_size) = if let Some(row_group_layout) = row_group_fragment_layout {
2301            self.rect.start_corner -= row_group_layout.rect.start_corner;
2302            (
2303                row_group_layout.rect.size.inline,
2304                SizeConstraint::Definite(row_group_layout.rect.size.block),
2305            )
2306        } else {
2307            (
2308                containing_block_for_logical_conversion.size.inline,
2309                containing_block_for_logical_conversion.size.block,
2310            )
2311        };
2312
2313        let row_group_containing_block = ContainingBlock {
2314            size: ContainingBlockSize {
2315                inline: inline_size,
2316                block: block_size,
2317            },
2318            style: containing_block_for_logical_conversion.style,
2319        };
2320
2321        let mut row_fragment = BoxFragment::new(
2322            self.row.base.base_fragment_info,
2323            self.row.base.style.clone(),
2324            self.fragments,
2325            self.rect.as_physical(Some(&row_group_containing_block)),
2326            PhysicalSides::zero(), /* padding */
2327            PhysicalSides::zero(), /* border */
2328            PhysicalSides::zero(), /* margin */
2329            None,                  /* specific_layout_info */
2330        );
2331        row_fragment.set_does_not_paint_background();
2332
2333        if let Some(mut row_positioning_context) = self.positioning_context.take() {
2334            row_positioning_context.layout_collected_children(layout_context, &mut row_fragment);
2335
2336            let parent_positioning_context = row_group_fragment_layout
2337                .as_mut()
2338                .and_then(|layout| layout.positioning_context.as_mut())
2339                .unwrap_or(table_positioning_context);
2340            parent_positioning_context.append(row_positioning_context);
2341        }
2342
2343        let fragment = Fragment::Box(ArcRefCell::new(row_fragment));
2344        self.row.base.set_fragment(fragment.clone());
2345        fragment
2346    }
2347}
2348
2349struct RowGroupFragmentLayout {
2350    row_group: ArcRefCell<TableTrackGroup>,
2351    rect: LogicalRect<Au>,
2352    positioning_context: Option<PositioningContext>,
2353    index: usize,
2354    fragments: Vec<Fragment>,
2355}
2356
2357impl RowGroupFragmentLayout {
2358    fn new(
2359        row_group: ArcRefCell<TableTrackGroup>,
2360        index: usize,
2361        dimensions: &TableAndTrackDimensions,
2362    ) -> Self {
2363        let (rect, positioning_context) = {
2364            let row_group = row_group.borrow();
2365            (
2366                dimensions.get_row_group_rect(&row_group),
2367                PositioningContext::new_for_layout_box_base(&row_group.base),
2368            )
2369        };
2370        Self {
2371            row_group,
2372            rect,
2373            positioning_context,
2374            index,
2375            fragments: Vec::new(),
2376        }
2377    }
2378
2379    fn finish(
2380        mut self,
2381        layout_context: &LayoutContext,
2382        table_positioning_context: &mut PositioningContext,
2383        containing_block_for_logical_conversion: &ContainingBlock,
2384        containing_block_for_children: &ContainingBlock,
2385    ) -> Fragment {
2386        let row_group = self.row_group.borrow();
2387        if self.positioning_context.is_some() {
2388            self.rect.start_corner +=
2389                relative_adjustement(&row_group.base.style, containing_block_for_children);
2390        }
2391
2392        let mut row_group_fragment = BoxFragment::new(
2393            row_group.base.base_fragment_info,
2394            row_group.base.style.clone(),
2395            self.fragments,
2396            self.rect
2397                .as_physical(Some(containing_block_for_logical_conversion)),
2398            PhysicalSides::zero(), /* padding */
2399            PhysicalSides::zero(), /* border */
2400            PhysicalSides::zero(), /* margin */
2401            None,                  /* specific_layout_info */
2402        );
2403        row_group_fragment.set_does_not_paint_background();
2404
2405        if let Some(mut row_positioning_context) = self.positioning_context.take() {
2406            row_positioning_context
2407                .layout_collected_children(layout_context, &mut row_group_fragment);
2408            table_positioning_context.append(row_positioning_context);
2409        }
2410
2411        let fragment = Fragment::Box(ArcRefCell::new(row_group_fragment));
2412        row_group.base.set_fragment(fragment.clone());
2413        fragment
2414    }
2415}
2416
2417struct TableAndTrackDimensions {
2418    /// The rect of the full table, not counting for borders, padding, and margin.
2419    table_rect: LogicalRect<Au>,
2420    /// The rect of the full table, not counting for borders, padding, and margin
2421    /// and offset by any border spacing and caption.
2422    table_cells_rect: LogicalRect<Au>,
2423    /// The min and max block offsets of each table row.
2424    row_dimensions: Vec<(Au, Au)>,
2425    /// The min and max inline offsets of each table column
2426    column_dimensions: Vec<(Au, Au)>,
2427}
2428
2429impl TableAndTrackDimensions {
2430    fn new(table_layout: &TableLayout) -> Self {
2431        let border_spacing = table_layout.table.border_spacing();
2432
2433        // The sizes used for a dimension when that dimension has no table tracks.
2434        let fallback_inline_size = table_layout.assignable_width;
2435        let fallback_block_size = table_layout.final_table_height;
2436
2437        let mut column_dimensions = Vec::new();
2438        let mut column_offset = Au::zero();
2439        for column_index in 0..table_layout.table.size.width {
2440            if table_layout.is_column_collapsed(column_index) {
2441                column_dimensions.push((column_offset, column_offset));
2442                continue;
2443            }
2444            let start_offset = column_offset + border_spacing.inline;
2445            let end_offset = start_offset + table_layout.distributed_column_widths[column_index];
2446            column_dimensions.push((start_offset, end_offset));
2447            column_offset = end_offset;
2448        }
2449        column_offset += if table_layout.table.size.width == 0 {
2450            fallback_inline_size
2451        } else {
2452            border_spacing.inline
2453        };
2454
2455        let mut row_dimensions = Vec::new();
2456        let mut row_offset = Au::zero();
2457        for row_index in 0..table_layout.table.size.height {
2458            if table_layout.is_row_collapsed(row_index) {
2459                row_dimensions.push((row_offset, row_offset));
2460                continue;
2461            }
2462            let start_offset = row_offset + border_spacing.block;
2463            let end_offset = start_offset + table_layout.row_sizes[row_index];
2464            row_dimensions.push((start_offset, end_offset));
2465            row_offset = end_offset;
2466        }
2467        row_offset += if table_layout.table.size.height == 0 {
2468            fallback_block_size
2469        } else {
2470            border_spacing.block
2471        };
2472
2473        let table_start_corner = LogicalVec2 {
2474            inline: column_dimensions.first().map_or_else(Au::zero, |v| v.0),
2475            block: row_dimensions.first().map_or_else(Au::zero, |v| v.0),
2476        };
2477        let table_size = LogicalVec2 {
2478            inline: column_dimensions
2479                .last()
2480                .map_or(fallback_inline_size, |v| v.1),
2481            block: row_dimensions.last().map_or(fallback_block_size, |v| v.1),
2482        } - table_start_corner;
2483        let table_cells_rect = LogicalRect {
2484            start_corner: table_start_corner,
2485            size: table_size,
2486        };
2487
2488        let table_rect = LogicalRect {
2489            start_corner: LogicalVec2::zero(),
2490            size: LogicalVec2 {
2491                inline: column_offset,
2492                block: row_offset,
2493            },
2494        };
2495
2496        Self {
2497            table_rect,
2498            table_cells_rect,
2499            row_dimensions,
2500            column_dimensions,
2501        }
2502    }
2503
2504    fn get_row_rect(&self, row_index: usize) -> LogicalRect<Au> {
2505        let mut row_rect = self.table_cells_rect;
2506        let row_dimensions = self.row_dimensions[row_index];
2507        row_rect.start_corner.block = row_dimensions.0;
2508        row_rect.size.block = row_dimensions.1 - row_dimensions.0;
2509        row_rect
2510    }
2511
2512    fn get_column_rect(&self, column_index: usize) -> LogicalRect<Au> {
2513        let mut row_rect = self.table_cells_rect;
2514        let column_dimensions = self.column_dimensions[column_index];
2515        row_rect.start_corner.inline = column_dimensions.0;
2516        row_rect.size.inline = column_dimensions.1 - column_dimensions.0;
2517        row_rect
2518    }
2519
2520    fn get_row_group_rect(&self, row_group: &TableTrackGroup) -> LogicalRect<Au> {
2521        if row_group.is_empty() {
2522            return LogicalRect::zero();
2523        }
2524
2525        let mut row_group_rect = self.table_cells_rect;
2526        let block_start = self.row_dimensions[row_group.track_range.start].0;
2527        let block_end = self.row_dimensions[row_group.track_range.end - 1].1;
2528        row_group_rect.start_corner.block = block_start;
2529        row_group_rect.size.block = block_end - block_start;
2530        row_group_rect
2531    }
2532
2533    fn get_column_group_rect(&self, column_group: &TableTrackGroup) -> LogicalRect<Au> {
2534        if column_group.is_empty() {
2535            return LogicalRect::zero();
2536        }
2537
2538        let mut column_group_rect = self.table_cells_rect;
2539        let inline_start = self.column_dimensions[column_group.track_range.start].0;
2540        let inline_end = self.column_dimensions[column_group.track_range.end - 1].1;
2541        column_group_rect.start_corner.inline = inline_start;
2542        column_group_rect.size.inline = inline_end - inline_start;
2543        column_group_rect
2544    }
2545
2546    fn get_cell_rect(
2547        &self,
2548        coordinates: TableSlotCoordinates,
2549        rowspan: usize,
2550        colspan: usize,
2551    ) -> LogicalRect<Au> {
2552        let start_corner = LogicalVec2 {
2553            inline: self.column_dimensions[coordinates.x].0,
2554            block: self.row_dimensions[coordinates.y].0,
2555        };
2556        let size = LogicalVec2 {
2557            inline: self.column_dimensions[coordinates.x + colspan - 1].1,
2558            block: self.row_dimensions[coordinates.y + rowspan - 1].1,
2559        } - start_corner;
2560        LogicalRect { start_corner, size }
2561    }
2562}
2563
2564impl Table {
2565    fn border_spacing(&self) -> LogicalVec2<Au> {
2566        if self.style.clone_border_collapse() == BorderCollapse::Collapse {
2567            LogicalVec2::zero()
2568        } else {
2569            let border_spacing = self.style.clone_border_spacing();
2570            LogicalVec2 {
2571                inline: border_spacing.horizontal(),
2572                block: border_spacing.vertical(),
2573            }
2574        }
2575    }
2576
2577    fn total_border_spacing(&self) -> LogicalVec2<Au> {
2578        let border_spacing = self.border_spacing();
2579        LogicalVec2 {
2580            inline: if self.size.width > 0 {
2581                border_spacing.inline * (self.size.width as i32 + 1)
2582            } else {
2583                Au::zero()
2584            },
2585            block: if self.size.height > 0 {
2586                border_spacing.block * (self.size.height as i32 + 1)
2587            } else {
2588                Au::zero()
2589            },
2590        }
2591    }
2592
2593    fn get_column_measure_for_column_at_index(
2594        &self,
2595        writing_mode: WritingMode,
2596        column_index: usize,
2597        is_in_fixed_mode: bool,
2598    ) -> CellOrTrackMeasure {
2599        let column = match self.columns.get(column_index) {
2600            Some(column) => column,
2601            None => return CellOrTrackMeasure::zero(),
2602        }
2603        .borrow();
2604
2605        let CellOrColumnOuterSizes {
2606            preferred: preferred_size,
2607            min: min_size,
2608            max: max_size,
2609            percentage: percentage_size,
2610        } = CellOrColumnOuterSizes::new(
2611            &column.base.style,
2612            writing_mode,
2613            &Default::default(),
2614            is_in_fixed_mode,
2615        );
2616
2617        CellOrTrackMeasure {
2618            content_sizes: ContentSizes {
2619                // > The outer min-content width of a table-column or table-column-group is
2620                // > max(min-width, width).
2621                // But that's clearly wrong, since it would be equal to or greater than
2622                // the outer max-content width. So we match other browsers instead.
2623                min_content: min_size.inline,
2624                // > The outer max-content width of a table-column or table-column-group is
2625                // > max(min-width, min(max-width, width)).
2626                // This matches Gecko, but Blink and WebKit ignore max_size.
2627                max_content: preferred_size
2628                    .inline
2629                    .clamp_between_extremums(min_size.inline, max_size.inline),
2630            },
2631            percentage: percentage_size.inline,
2632        }
2633    }
2634
2635    fn get_row_measure_for_row_at_index(
2636        &self,
2637        writing_mode: WritingMode,
2638        row_index: usize,
2639    ) -> CellOrTrackMeasure {
2640        let row = match self.rows.get(row_index) {
2641            Some(row) => row,
2642            None => return CellOrTrackMeasure::zero(),
2643        };
2644
2645        // In the block axis, the min-content and max-content sizes are the same
2646        // (except for new layout boxes like grid and flex containers). Note that
2647        // other browsers don't seem to use the min and max sizing properties here.
2648        let row = row.borrow();
2649        let size = row.base.style.box_size(writing_mode);
2650        let max_size = row.base.style.max_box_size(writing_mode);
2651        let percentage_contribution = get_size_percentage_contribution(&size, &max_size);
2652
2653        CellOrTrackMeasure {
2654            content_sizes: size
2655                .block
2656                .to_numeric()
2657                .and_then(|size| size.to_length())
2658                .map_or_else(Au::zero, Au::from)
2659                .into(),
2660            percentage: percentage_contribution.block,
2661        }
2662    }
2663
2664    pub(crate) fn layout(
2665        &self,
2666        layout_context: &LayoutContext,
2667        positioning_context: &mut PositioningContext,
2668        containing_block_for_children: &ContainingBlock,
2669        containing_block_for_table: &ContainingBlock,
2670    ) -> CacheableLayoutResult {
2671        TableLayout::new(self).layout(
2672            layout_context,
2673            positioning_context,
2674            containing_block_for_children,
2675            containing_block_for_table,
2676        )
2677    }
2678}
2679
2680impl ComputeInlineContentSizes for Table {
2681    #[servo_tracing::instrument(name = "Table::compute_inline_content_sizes", skip_all)]
2682    fn compute_inline_content_sizes(
2683        &self,
2684        layout_context: &LayoutContext,
2685        constraint_space: &ConstraintSpace,
2686    ) -> InlineContentSizesResult {
2687        let writing_mode = constraint_space.style.writing_mode;
2688        let mut layout = TableLayout::new(self);
2689        layout.compute_border_collapse(writing_mode);
2690        layout.pbm = self
2691            .layout_style(Some(&layout))
2692            .padding_border_margin_with_writing_mode_and_containing_block_inline_size(
2693                writing_mode,
2694                Au::zero(),
2695            );
2696        layout.compute_measures(layout_context, writing_mode);
2697
2698        let grid_content_sizes = layout.compute_grid_min_max();
2699
2700        // Padding and border should apply to the table grid, but they will be taken into
2701        // account when computing the inline content sizes of the table wrapper (our parent), so
2702        // this code removes their contribution from the inline content size of the caption.
2703        let caption_content_sizes = ContentSizes::from(
2704            layout.compute_caption_minimum_inline_size(layout_context) -
2705                layout.pbm.padding_border_sums.inline,
2706        );
2707
2708        InlineContentSizesResult {
2709            sizes: grid_content_sizes.max(caption_content_sizes),
2710            depends_on_block_constraints: false,
2711        }
2712    }
2713}
2714
2715impl Table {
2716    #[inline]
2717    pub(crate) fn layout_style<'a>(
2718        &'a self,
2719        layout: Option<&'a TableLayout<'a>>,
2720    ) -> LayoutStyle<'a> {
2721        LayoutStyle::Table(TableLayoutStyle {
2722            table: self,
2723            layout,
2724        })
2725    }
2726
2727    #[inline]
2728    pub(crate) fn layout_style_for_grid(&self) -> LayoutStyle<'_> {
2729        LayoutStyle::Default(&self.grid_style)
2730    }
2731}
2732
2733impl TableTrack {
2734    #[inline]
2735    pub(crate) fn layout_style(&self) -> LayoutStyle<'_> {
2736        LayoutStyle::Default(&self.base.style)
2737    }
2738}
2739
2740impl TableTrackGroup {
2741    #[inline]
2742    pub(crate) fn layout_style(&self) -> LayoutStyle<'_> {
2743        LayoutStyle::Default(&self.base.style)
2744    }
2745}
2746
2747impl TableLayoutStyle<'_> {
2748    #[inline]
2749    pub(crate) fn style(&self) -> &ComputedValues {
2750        &self.table.style
2751    }
2752
2753    #[inline]
2754    pub(crate) fn collapses_borders(&self) -> bool {
2755        self.style().get_inherited_table().border_collapse == BorderCollapse::Collapse
2756    }
2757
2758    pub(crate) fn halved_collapsed_border_widths(&self) -> LogicalSides<Au> {
2759        debug_assert!(self.collapses_borders());
2760        let area = LogicalSides {
2761            inline_start: 0,
2762            inline_end: self.table.size.width,
2763            block_start: 0,
2764            block_end: self.table.size.height,
2765        };
2766        if let Some(layout) = self.layout {
2767            layout.get_collapsed_border_widths_for_area(area)
2768        } else {
2769            // TODO: this should be cached.
2770            let mut layout = TableLayout::new(self.table);
2771            layout.compute_border_collapse(self.style().writing_mode);
2772            layout.get_collapsed_border_widths_for_area(area)
2773        }
2774        .expect("Collapsed borders should be computed")
2775    }
2776}
2777
2778impl TableSlotCell {
2779    #[inline]
2780    fn layout_style(&self) -> LayoutStyle<'_> {
2781        self.contents.layout_style(&self.base)
2782    }
2783
2784    fn effective_vertical_align(&self) -> VerticalAlignKeyword {
2785        match self.base.style.clone_vertical_align() {
2786            VerticalAlign::Keyword(VerticalAlignKeyword::Top) => VerticalAlignKeyword::Top,
2787            VerticalAlign::Keyword(VerticalAlignKeyword::Bottom) => VerticalAlignKeyword::Bottom,
2788            VerticalAlign::Keyword(VerticalAlignKeyword::Middle) => VerticalAlignKeyword::Middle,
2789            _ => VerticalAlignKeyword::Baseline,
2790        }
2791    }
2792
2793    fn inline_content_sizes(&self, layout_context: &LayoutContext) -> ContentSizes {
2794        let constraint_space = ConstraintSpace::new_for_style_and_ratio(
2795            &self.base.style,
2796            None, /* TODO: support preferred aspect ratios on non-replaced boxes */
2797        );
2798        self.base
2799            .inline_content_sizes(layout_context, &constraint_space, &self.contents.contents)
2800            .sizes
2801    }
2802
2803    #[allow(clippy::too_many_arguments)]
2804    fn create_fragment(
2805        &self,
2806        mut layout: CellLayout,
2807        cell_rect: LogicalRect<Au>,
2808        cell_baseline: Au,
2809        positioning_context: &mut PositioningContext,
2810        table_style: &ComputedValues,
2811        containing_block: &ContainingBlock,
2812        is_collapsed: bool,
2813    ) -> BoxFragment {
2814        // This must be scoped to this function because it conflicts with euclid's Zero.
2815        use style::Zero as StyleZero;
2816
2817        let cell_content_rect = cell_rect.deflate(&(layout.padding + layout.border));
2818        let content_block_size = layout.layout.content_block_size;
2819        let free_space = || Au::zero().max(cell_content_rect.size.block - content_block_size);
2820        let vertical_align_offset = match self.effective_vertical_align() {
2821            VerticalAlignKeyword::Top => Au::zero(),
2822            VerticalAlignKeyword::Bottom => free_space(),
2823            VerticalAlignKeyword::Middle => free_space().scale_by(0.5),
2824            _ => {
2825                cell_baseline -
2826                    (layout.padding.block_start + layout.border.block_start) -
2827                    layout.ascent()
2828            },
2829        };
2830
2831        let mut base_fragment_info = self.base.base_fragment_info;
2832        if self.base.style.get_inherited_table().empty_cells == EmptyCells::Hide &&
2833            table_style.get_inherited_table().border_collapse != BorderCollapse::Collapse &&
2834            layout.is_empty_for_empty_cells()
2835        {
2836            base_fragment_info.flags.insert(FragmentFlags::DO_NOT_PAINT);
2837        }
2838
2839        if is_collapsed {
2840            base_fragment_info.flags.insert(FragmentFlags::IS_COLLAPSED);
2841        }
2842
2843        // Create an `AnonymousFragment` to move the cell contents to the cell baseline.
2844        let mut vertical_align_fragment_rect = cell_content_rect;
2845        vertical_align_fragment_rect.start_corner = LogicalVec2 {
2846            inline: Au::zero(),
2847            block: vertical_align_offset,
2848        };
2849        let vertical_align_fragment = PositioningFragment::new_anonymous(
2850            self.base.style.clone(),
2851            vertical_align_fragment_rect.as_physical(None),
2852            layout.layout.fragments,
2853        );
2854
2855        // Adjust the static position of all absolute children based on the
2856        // final content rect of this fragment. Note that we are not shifting by the position of the
2857        // Anonymous fragment we use to shift content to the baseline.
2858        //
2859        // TODO(mrobinson): This is correct for absolutes that are direct children of the table
2860        // cell, but wrong for absolute fragments that are more deeply nested in the hierarchy of
2861        // fragments.
2862        let physical_cell_rect = cell_content_rect.as_physical(Some(containing_block));
2863        layout
2864            .positioning_context
2865            .adjust_static_position_of_hoisted_fragments_with_offset(
2866                &physical_cell_rect.origin.to_vector(),
2867                PositioningContextLength::zero(),
2868            );
2869        positioning_context.append(layout.positioning_context);
2870
2871        let specific_layout_info = (table_style.get_inherited_table().border_collapse ==
2872            BorderCollapse::Collapse)
2873            .then_some(SpecificLayoutInfo::TableCellWithCollapsedBorders);
2874
2875        BoxFragment::new(
2876            base_fragment_info,
2877            self.base.style.clone(),
2878            vec![Fragment::Positioning(vertical_align_fragment)],
2879            physical_cell_rect,
2880            layout.padding.to_physical(table_style.writing_mode),
2881            layout.border.to_physical(table_style.writing_mode),
2882            PhysicalSides::zero(), /* margin */
2883            specific_layout_info,
2884        )
2885        .with_baselines(layout.layout.baselines)
2886    }
2887}
2888
2889fn get_size_percentage_contribution(
2890    size: &LogicalVec2<Size<ComputedLengthPercentage>>,
2891    max_size: &LogicalVec2<Size<ComputedLengthPercentage>>,
2892) -> LogicalVec2<Option<Percentage>> {
2893    // From <https://drafts.csswg.org/css-tables/#percentage-contribution>
2894    // > The percentage contribution of a table cell, column, or column group is defined
2895    // > in terms of the computed values of width and max-width that have computed values
2896    // > that are percentages:
2897    // >    min(percentage width, percentage max-width).
2898    // > If the computed values are not percentages, then 0% is used for width, and an
2899    // > infinite percentage is used for max-width.
2900    LogicalVec2 {
2901        inline: max_two_optional_percentages(
2902            size.inline.to_percentage(),
2903            max_size.inline.to_percentage(),
2904        ),
2905        block: max_two_optional_percentages(
2906            size.block.to_percentage(),
2907            max_size.block.to_percentage(),
2908        ),
2909    }
2910}
2911
2912struct CellOrColumnOuterSizes {
2913    min: LogicalVec2<Au>,
2914    preferred: LogicalVec2<Au>,
2915    max: LogicalVec2<Option<Au>>,
2916    percentage: LogicalVec2<Option<Percentage>>,
2917}
2918
2919impl CellOrColumnOuterSizes {
2920    fn new(
2921        style: &Arc<ComputedValues>,
2922        writing_mode: WritingMode,
2923        padding_border_sums: &LogicalVec2<Au>,
2924        is_in_fixed_mode: bool,
2925    ) -> Self {
2926        let box_sizing = style.get_position().box_sizing;
2927        let outer_size = |size: LogicalVec2<Au>| match box_sizing {
2928            BoxSizing::ContentBox => size + *padding_border_sums,
2929            BoxSizing::BorderBox => LogicalVec2 {
2930                inline: size.inline.max(padding_border_sums.inline),
2931                block: size.block.max(padding_border_sums.block),
2932            },
2933        };
2934
2935        let outer_option_size = |size: LogicalVec2<Option<Au>>| match box_sizing {
2936            BoxSizing::ContentBox => size.map_inline_and_block_axes(
2937                |inline| inline.map(|inline| inline + padding_border_sums.inline),
2938                |block| block.map(|block| block + padding_border_sums.block),
2939            ),
2940            BoxSizing::BorderBox => size.map_inline_and_block_axes(
2941                |inline| inline.map(|inline| inline.max(padding_border_sums.inline)),
2942                |block| block.map(|block| block.max(padding_border_sums.block)),
2943            ),
2944        };
2945
2946        let get_size_for_axis = |size: &Size<ComputedLengthPercentage>| {
2947            // Note that measures treat all size values other than <length>
2948            // as the initial value of the property.
2949            size.to_numeric()
2950                .and_then(|length_percentage| length_percentage.to_length())
2951                .map(Au::from)
2952        };
2953
2954        let size = style.box_size(writing_mode);
2955        if is_in_fixed_mode {
2956            return Self {
2957                percentage: size.map(|v| v.to_percentage()),
2958                preferred: outer_option_size(size.map(get_size_for_axis))
2959                    .map(|v| v.unwrap_or_default()),
2960                min: LogicalVec2::default(),
2961                max: LogicalVec2::default(),
2962            };
2963        }
2964
2965        let min_size = style.min_box_size(writing_mode);
2966        let max_size = style.max_box_size(writing_mode);
2967
2968        Self {
2969            min: outer_size(min_size.map(|v| get_size_for_axis(v).unwrap_or_default())),
2970            preferred: outer_size(size.map(|v| get_size_for_axis(v).unwrap_or_default())),
2971            max: outer_option_size(max_size.map(get_size_for_axis)),
2972            percentage: get_size_percentage_contribution(&size, &max_size),
2973        }
2974    }
2975}
2976
2977struct RowspanToDistribute<'a> {
2978    coordinates: TableSlotCoordinates,
2979    cell: AtomicRef<'a, TableSlotCell>,
2980    measure: &'a CellOrTrackMeasure,
2981}
2982
2983impl RowspanToDistribute<'_> {
2984    fn range(&self) -> Range<usize> {
2985        self.coordinates.y..self.coordinates.y + self.cell.rowspan
2986    }
2987
2988    fn fully_encloses(&self, other: &RowspanToDistribute) -> bool {
2989        other.coordinates.y > self.coordinates.y && other.range().end < self.range().end
2990    }
2991}
2992
2993/// The inline size constraints provided by a cell that span multiple columns (`colspan` > 1).
2994/// These constraints are distributed to the individual columns that make up this cell's span.
2995#[derive(Debug)]
2996struct ColspanToDistribute {
2997    starting_column: usize,
2998    span: usize,
2999    content_sizes: ContentSizes,
3000    percentage: Option<Percentage>,
3001}
3002
3003impl ColspanToDistribute {
3004    /// A comparison function to sort the colspan cell constraints primarily by their span
3005    /// width and secondarily by their starting column. This is not an implementation of
3006    /// `PartialOrd` because we want to return [`Ordering::Equal`] even if `self != other`.
3007    fn comparison_for_sort(a: &Self, b: &Self) -> Ordering {
3008        a.span
3009            .cmp(&b.span)
3010            .then_with(|| a.starting_column.cmp(&b.starting_column))
3011    }
3012
3013    fn range(&self) -> Range<usize> {
3014        self.starting_column..self.starting_column + self.span
3015    }
3016}
3017
3018#[cfg(test)]
3019mod test {
3020    use app_units::MIN_AU;
3021
3022    use super::*;
3023    use crate::sizing::ContentSizes;
3024
3025    #[test]
3026    fn test_colspan_to_distribute_first_sort_by_span() {
3027        let a = ColspanToDistribute {
3028            starting_column: 0,
3029            span: 0,
3030            content_sizes: ContentSizes {
3031                min_content: MIN_AU,
3032                max_content: MIN_AU,
3033            },
3034            percentage: None,
3035        };
3036
3037        let b = ColspanToDistribute {
3038            starting_column: 0,
3039            span: 1,
3040            content_sizes: ContentSizes {
3041                min_content: MIN_AU,
3042                max_content: MIN_AU,
3043            },
3044            percentage: None,
3045        };
3046
3047        let ordering = ColspanToDistribute::comparison_for_sort(&a, &b);
3048        assert_eq!(ordering, Ordering::Less);
3049    }
3050
3051    #[test]
3052    fn test_colspan_to_distribute_if_spans_are_equal_sort_by_starting_column() {
3053        let a = ColspanToDistribute {
3054            starting_column: 0,
3055            span: 0,
3056            content_sizes: ContentSizes {
3057                min_content: MIN_AU,
3058                max_content: MIN_AU,
3059            },
3060            percentage: None,
3061        };
3062
3063        let b = ColspanToDistribute {
3064            starting_column: 1,
3065            span: 0,
3066            content_sizes: ContentSizes {
3067                min_content: MIN_AU,
3068                max_content: MIN_AU,
3069            },
3070            percentage: None,
3071        };
3072
3073        let ordering = ColspanToDistribute::comparison_for_sort(&a, &b);
3074        assert_eq!(ordering, Ordering::Less);
3075    }
3076}