I had a bit of a read of the code surrounding this, since it was interesting and I really don't know it well enough.
The frame tree structure for a table looks like this:
```
Table
RowGroup1
Row1
Cell1
Cell2
Row2
Cell3
RowGroup2
Row3
Cell4
ColGroupList<
ColGroup1
Column1
Column2
ColGroup2
Column3
>
```
Tracing through the display list building code for this gives us this iteration order:
```
Table BuildDisplayList/DisplayGenericTablePart
For-each ColGroup, call BuildDisplayList/DisplayGenericTablePart
Build a vector of Column indices in the ColGroup
For-each RowGroup in the table, call PaintRowGroupBackgroundByColIdx with the Column indices
For-each Row in the RowGroup
For-each Cell in the Row
Add col-group background for the cell if cell is in one of the columns
For-each Column, call BuildDisplayList/DisplayGenericTablePart
For-each RowGroup in the table, call PaintRowGroupBackgroundByColIdx with the the current Column index
For-each Row in the RowGroup
For-each Cell in the Row
Add column background for the cell if cell is in the current columns
For-each RowGroup (principal child list) BuildDisplayList/DisplayGenericTablePart
Call PaintRowGroupBackground
For-each Row, call PaintRowBackground
For-each Cell in the Row
Add the row-group background for the cell
For-each Row in the group call BuildDisplayList/DisplayGenericTablePart (uses DisplayRows, maybe using a cursor to optimise iteration)
Call PaintRowBackground
For-each Cell in the Row
Add the row background for the cell
For-each Cell in the Row, call BuildDisplayList/DisplayGenericTablePart
Add display items for cell, and recurse into descendants.
```
(Which is the same as bz said at [1], just worded slightly differently)
I think we could solve all of this by doing a single iteration of the table (just descending through principal children lists), collecting the different types of items separately, and then collating them in the right order at the end.
We can create a temporary nsDisplayListSet to collect all the 'normal' items (items for the cells themselves, and their descendants), and pass this through BuildDisplayList. We can then also create 4 (col-group, col, row-group, row) extra nsDisplayLists (stored centrally somewhere, similar to nsDisplayListBuilder::GetCurrentTableItem), and each cell can also add background items to those lists.
Once we've finished building all the items for the table, we can sort the special lists so that they have the same order as the current iterations, and append all their items to the BorderBackground() list of the outer nsDisplayListSet. Then we append all the items/lists from the temp nsDisplayListSet to the outer, guaranteeing that these items end up after all table-specific backgrounds.
For sorting the special lists, both row-group and row backgrounds should already be in the right order. Column backgrounds need to be sorted by column, but we can look this up easily using nsTableCellFrame::GetColIndex (or cache it when we stored the item to avoid another dereference).
The col-group lists needs to be sorted by col-group, which we don't have an easy way to do (afaict). I believe col-groups are relatively rare, so we can probably not worry about this too much. Maybe build a hashmap of column index -> col-group index?
Doing that would give us a single pass over all the cells, and should make things significantly faster, especially when retaining isn't effective.
[1] https://bugzilla.mozilla.org/show_bug.cgi?id=1409047#c9
Bug 1409114 Comment 8 Edit History
Note: The actual edited comment in the bug view page will always show the original commenter’s name and original timestamp.
I had a bit of a read of the code surrounding this, since it was interesting and I really don't know it well enough.
The frame tree structure for a table looks like this:
```
Table
RowGroup1
Row1
Cell1
Cell2
Row2
Cell3
RowGroup2
Row3
Cell4
ColGroupList<
ColGroup1
Column1
Column2
ColGroup2
Column3
>
```
Tracing through the display list building code for this gives us this iteration order:
```
Table BuildDisplayList/DisplayGenericTablePart
For-each ColGroup, call BuildDisplayList/DisplayGenericTablePart
Build a vector of Column indices in the ColGroup
For-each RowGroup in the table, call PaintRowGroupBackgroundByColIdx with the Column indices
For-each Row in the RowGroup
For-each Cell in the Row
Add col-group background for the cell if cell is in one of the columns
For-each Column, call BuildDisplayList/DisplayGenericTablePart
For-each RowGroup in the table, call PaintRowGroupBackgroundByColIdx with the the current Column index
For-each Row in the RowGroup
For-each Cell in the Row
Add column background for the cell if cell is in the current columns
For-each RowGroup (principal child list) BuildDisplayList/DisplayGenericTablePart
Call PaintRowGroupBackground
For-each Row, call PaintRowBackground
For-each Cell in the Row
Add the row-group background for the cell
For-each Row in the group call BuildDisplayList/DisplayGenericTablePart (uses DisplayRows, maybe using a cursor to optimise iteration)
Call PaintRowBackground
For-each Cell in the Row
Add the row background for the cell
For-each Cell in the Row, call BuildDisplayList/DisplayGenericTablePart
Add display items for cell, and recurse into descendants.
```
(Which is the same as bz said at [1], just worded slightly differently)
I think we could solve all of this by doing a single iteration of the table (just descending through principal children lists), collecting the different types of items separately, and then collating them in the right order at the end.
We can create a temporary nsDisplayListSet to collect all the 'normal' items (items for the cells themselves, and their descendants), and pass this through BuildDisplayList. We can then also create 4 (col-group, col, row-group, row) extra nsDisplayLists (stored centrally somewhere, similar to nsDisplayListBuilder::GetCurrentTableItem), and each cell can also add background items to those lists.
Once we've finished building all the items for the table, we can sort the special lists so that they have the same order as the current iterations, and append all their items to the BorderBackground() list of the outer nsDisplayListSet. Then we append all the items/lists from the temp nsDisplayListSet to the outer, guaranteeing that these items end up after all table-specific backgrounds.
For sorting the special lists, both row-group and row backgrounds should already be in the right order. Column backgrounds need to be sorted by column, but we can look this up easily using nsTableCellFrame::GetColIndex (or cache it when we stored the item to avoid another dereference).
The col-group lists needs to be sorted by col-group, which we don't have an easy way to do (afaict). I believe col-groups are relatively rare, so we can probably not worry about this too much. Maybe build a hashmap of column index -> col-group index?
Doing that would give us a single pass over all the cells, and should make things significantly faster, especially when retaining isn't effective.
[1] https://bugzilla.mozilla.org/show_bug.cgi?id=1409047#c9
I had a bit of a read of the code surrounding this, since it was interesting and I really don't know it well enough.
The frame tree structure for a table looks like this:
```
Table
RowGroup1
Row1
Cell1
Cell2
Row2
Cell3
RowGroup2
Row3
Cell4
ColGroupList<
ColGroup1
Column1
Column2
ColGroup2
Column3
>
```
Tracing through the display list building code for this gives us this iteration order:
```
Table BuildDisplayList/DisplayGenericTablePart
Table box shadow outer
Table background
Table box shadow inner
Table outline
For-each ColGroup, call BuildDisplayList/DisplayGenericTablePart
ColGroup box shadow outer, inner and outline.
Build a vector of Column indices in the ColGroup
For-each RowGroup in the table, call PaintRowGroupBackgroundByColIdx with the Column indices
For-each Row in the RowGroup
For-each Cell in the Row
Add col-group background for the cell if cell is in one of the columns
For-each Column, call BuildDisplayList/DisplayGenericTablePart
Column box shadow outer, inner and outline.
For-each RowGroup in the table, call PaintRowGroupBackgroundByColIdx with the the current Column index
For-each Row in the RowGroup
For-each Cell in the Row
Add column background for the cell if cell is in the current columns
Column border.
ColGroup border.
For-each RowGroup (principal child list) BuildDisplayList/DisplayGenericTablePart
RowGroup box shadow outer, inner and outline.
Call PaintRowGroupBackground
For-each Row, call PaintRowBackground
For-each Cell in the Row
Add the row-group background for the cell
For-each Row in the group call BuildDisplayList/DisplayGenericTablePart (uses DisplayRows, maybe using a cursor to optimise iteration)
Row box shadow outer, inner and outline.
Call PaintRowBackground
For-each Cell in the Row
Add the row background for the cell
For-each Cell in the Row, call BuildDisplayList/DisplayGenericTablePart
Add display items for cell, and recurse into descendants.
Row border.
RowGroup border.
Table border.
```
(Which is the same as bz said at [1], just worded slightly differently)
I think we could solve all of this by doing a single iteration of the table (just descending through principal children lists), collecting the different types of items separately, and then collating them in the right order at the end.
We can create a temporary nsDisplayListSet to collect all the 'normal' items (items for the cells themselves, and their descendants), and pass this through BuildDisplayList. We can then also create 4 (col-group, col, row-group, row) extra nsDisplayLists (stored centrally somewhere, similar to nsDisplayListBuilder::GetCurrentTableItem), and each cell can also add background items to those lists.
Once we've finished building all the items for the table, we can sort the special lists so that they have the same order as the current iterations, and append all their items to the BorderBackground() list of the outer nsDisplayListSet. Then we append all the items/lists from the temp nsDisplayListSet to the outer, guaranteeing that these items end up after all table-specific backgrounds.
For sorting the special lists, both row-group and row backgrounds should already be in the right order. Column backgrounds need to be sorted by column, but we can look this up easily using nsTableCellFrame::GetColIndex (or cache it when we stored the item to avoid another dereference).
The col-group lists needs to be sorted by col-group, which we don't have an easy way to do (afaict). I believe col-groups are relatively rare, so we can probably not worry about this too much. Maybe build a hashmap of column index -> col-group index?
Doing that would give us a single pass over all the cells, and should make things significantly faster, especially when retaining isn't effective.
[1] https://bugzilla.mozilla.org/show_bug.cgi?id=1409047#c9
I had a bit of a read of the code surrounding this, since it was interesting and I really don't know it well enough.
The frame tree structure for a table looks like this:
```
Table
RowGroup1
Row1
Cell1
Cell2
Row2
Cell3
RowGroup2
Row3
Cell4
ColGroupList<
ColGroup1
Column1
Column2
ColGroup2
Column3
>
```
Tracing through the display list building code for this gives us this iteration order:
```
Table BuildDisplayList/DisplayGenericTablePart
Table box shadow outer
Table background
Table box shadow inner
Table outline
For-each ColGroup, call BuildDisplayList/DisplayGenericTablePart
ColGroup box shadow outer
Build a vector of Column indices in the ColGroup
For-each RowGroup in the table, call PaintRowGroupBackgroundByColIdx with the Column indices
For-each Row in the RowGroup
For-each Cell in the Row
Add col-group background for the cell if cell is in one of the columns
For-each Column, call BuildDisplayList/DisplayGenericTablePart
Column box shadow outer.
For-each RowGroup in the table, call PaintRowGroupBackgroundByColIdx with the the current Column index
For-each Row in the RowGroup
For-each Cell in the Row
Add column background for the cell if cell is in the current columns
Column box shadow inner and outline.
ColGroup box shadow inner and outline.
For-each RowGroup (principal child list) BuildDisplayList/DisplayGenericTablePart
RowGroup box shadow outer.
Call PaintRowGroupBackground
For-each Row, call PaintRowBackground
For-each Cell in the Row
Add the row-group background for the cell
For-each Row in the group call BuildDisplayList/DisplayGenericTablePart (uses DisplayRows, maybe using a cursor to optimise iteration)
Row box shadow outer.
Call PaintRowBackground
For-each Cell in the Row
Add the row background for the cell
For-each Cell in the Row, call BuildDisplayList/DisplayGenericTablePart
Add display items for cell (border, background, shadows, outline etc), and recurse into descendants.
Row box shadow inner and outline.
RowGroup box shadow inner and outline.
Table border, or border-collapse borders for the whole table.
```
(Which is the same as bz said at [1], just worded slightly differently)
I think we could solve all of this by doing a single iteration of the table (just descending through principal children lists), collecting the different types of items separately, and then collating them in the right order at the end.
We can create a temporary nsDisplayListSet to collect all the 'normal' items (items for the cells themselves, and their descendants), and pass this through BuildDisplayList. We can then also create 4 (col-group, col, row-group, row) extra nsDisplayLists (stored centrally somewhere, similar to nsDisplayListBuilder::GetCurrentTableItem), and each cell can also add background items to those lists.
Once we've finished building all the items for the table, we can sort the special lists so that they have the same order as the current iterations, and append all their items to the BorderBackground() list of the outer nsDisplayListSet. Then we append all the items/lists from the temp nsDisplayListSet to the outer, guaranteeing that these items end up after all table-specific backgrounds.
For sorting the special lists, both row-group and row backgrounds should already be in the right order. Column backgrounds need to be sorted by column, but we can look this up easily using nsTableCellFrame::GetColIndex (or cache it when we stored the item to avoid another dereference).
The col-group lists needs to be sorted by col-group, which we don't have an easy way to do (afaict). I believe col-groups are relatively rare, so we can probably not worry about this too much. Maybe build a hashmap of column index -> col-group index?
Doing that would give us a single pass over all the cells, and should make things significantly faster, especially when retaining isn't effective.
[1] https://bugzilla.mozilla.org/show_bug.cgi?id=1409047#c9
I had a bit of a read of the code surrounding this, since it was interesting and I really don't know it well enough.
The frame tree structure for a table looks like this:
```
Table
RowGroup1
Row1
Cell1
Cell2
Row2
Cell3
RowGroup2
Row3
Cell4
ColGroupList<
ColGroup1
Column1
Column2
ColGroup2
Column3
>
```
Tracing through the display list building code for this gives us this iteration order:
```
Table BuildDisplayList/DisplayGenericTablePart
Table box shadow outer
Table background
Table box shadow inner
Table outline
For-each ColGroup, call BuildDisplayList/DisplayGenericTablePart
ColGroup box shadow outer
Build a vector of Column indices in the ColGroup
For-each RowGroup in the table, call PaintRowGroupBackgroundByColIdx with the Column indices
For-each Row in the RowGroup
For-each Cell in the Row
Add col-group background for the cell if cell is in one of the columns
For-each Column, call BuildDisplayList/DisplayGenericTablePart
Column box shadow outer.
For-each RowGroup in the table, call PaintRowGroupBackgroundByColIdx with the the current Column index
For-each Row in the RowGroup
For-each Cell in the Row
Add column background for the cell if cell is in the current columns
Column box shadow inner and outline.
ColGroup box shadow inner and outline.
For-each RowGroup (principal child list) BuildDisplayList/DisplayGenericTablePart
RowGroup box shadow outer.
Call PaintRowGroupBackground
For-each Row, call PaintRowBackground
For-each Cell in the Row
Add the row-group background for the cell
RowGroup box shadow inner and outline.
For-each Row in the group call BuildDisplayList/DisplayGenericTablePart (uses DisplayRows, maybe using a cursor to optimise iteration)
Row box shadow outer.
Call PaintRowBackground
For-each Cell in the Row
Add the row background for the cell
Row box shadow inner and outline.
For-each Cell in the Row, call BuildDisplayList/DisplayGenericTablePart
Add display items for cell (border, background, shadows, outline etc), and recurse into descendants.
Table border, or border-collapse borders for the whole table.
```
(Which is the same as bz said at [1], just worded slightly differently)
I think we could solve all of this by doing a single iteration of the table (just descending through principal children lists), collecting the different types of items separately, and then collating them in the right order at the end.
We can create a temporary nsDisplayListSet to collect all the 'normal' items (items for the cells themselves, and their descendants), and pass this through BuildDisplayList. We can then also create 4 (col-group, col, row-group, row) extra nsDisplayLists (stored centrally somewhere, similar to nsDisplayListBuilder::GetCurrentTableItem), and each cell can also add background items to those lists.
Once we've finished building all the items for the table, we can sort the special lists so that they have the same order as the current iterations, and append all their items to the BorderBackground() list of the outer nsDisplayListSet. Then we append all the items/lists from the temp nsDisplayListSet to the outer, guaranteeing that these items end up after all table-specific backgrounds.
For sorting the special lists, both row-group and row backgrounds should already be in the right order. Column backgrounds need to be sorted by column, but we can look this up easily using nsTableCellFrame::GetColIndex (or cache it when we stored the item to avoid another dereference).
The col-group lists needs to be sorted by col-group, which we don't have an easy way to do (afaict). I believe col-groups are relatively rare, so we can probably not worry about this too much. Maybe build a hashmap of column index -> col-group index?
Doing that would give us a single pass over all the cells, and should make things significantly faster, especially when retaining isn't effective.
[1] https://bugzilla.mozilla.org/show_bug.cgi?id=1409047#c9