Bug 112299 – [CSS Grid Layout] resolveContentBasedTrackSizingFunctions should iterate over the grid items not the grid tracks

• Status: RESOLVED
• Resolution: FIXED
• Component: Layout and Rendering

[Julien Chaffraix]

While implementing the first layout algorithm, we made the choice to do a grid tracks' iteration in resolveContentBasedTrackSizingFunctions, ignoring the fact that the specification does a grid items'.

Iterating over grid items is more efficient for sparse grids. However it requires an additional pass over the grid tracks as we don't know which ones have been touched during the loop so it's difficult to say in the general case.

However to properly implement grid spanning, we need to consider grid items and not grid tracks as a single grid item can now (differently) contribute to several grid tracks. This change will align our layout algorithm with the specification to make it easier to implement spanning.

[Julien Chaffraix]

Scratch my complexity analysis: it should be also better in the general case.

We currently always walk the full grid in each direction (which O(N*M) on a N * M grid), we also have to walk the grid items as we need to account for all of them during layout.

The algorithm in the specification keeps the mandatory grid items walking and add some extra grid track walking in the considered direction (O(N) or O(M)).

[Julien Chaffraix]

Created attachment 193028 [details]
Proposed change 1: Added a filtering logic (similar to the spec), simplified the availableLogicalSpace update logic.

[WebKit Review Bot]

Comment on attachment 193028 [details]
Proposed change 1: Added a filtering logic (similar to the spec), simplified the availableLogicalSpace update logic.

Clearing flags on attachment: 193028

Committed r145840: <http://trac.webkit.org/changeset/145840>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.