Skip to main content

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