[CSS Grid Layout] Size tracks using a list of all items sorted by span

[CSS Grid Layout] Size tracks using a list of all items sorted by span

RenderGrid::resolveContentBasedTrackSizingFunctions() was not spec
compliant because it used to compute content-based track sizes going
track-by-track. The specs clearly specify that instead, we should collect
all items spanning content-sized tracks and process them one by one after
sorting them by ascending span.

The obvious issue in the old implementation is that a grid item spanning the
first track was always processed before a non spanning item in the second
track. That leads to weird track size computations.

Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=183657

[svillar, 2014-09-22 15:42:11]

svillar@igalia.com changed reviewers:
+ cbiesinger@chromium.org, esprehn@chromium.org, jchaffraix@chromium.org

[svillar, 2014-09-22 15:42:50]

Sending for review

[Julien - ping for review, 2014-09-23 23:17:31]

https://codereview.chromium.org/592803003/diff/1/LayoutTests/fast/css-grid-la...
File LayoutTests/fast/css-grid-layout/grid-content-sized-columns-resolution.html
(right):

https://codereview.chromium.org/592803003/diff/1/LayoutTests/fast/css-grid-la...
LayoutTests/fast/css-grid-layout/grid-content-sized-columns-resolution.html:101:
<!-- Check that items are processed by ascending span instead of going track by
track forbidding extra space distribution. -->
forbidding? for adding or for bidding (like an auction)?

https://codereview.chromium.org/592803003/diff/1/Source/core/rendering/Render...
File Source/core/rendering/RenderGrid.cpp (right):

https://codereview.chromium.org/592803003/diff/1/Source/core/rendering/Render...
Source/core/rendering/RenderGrid.cpp:664: class GridItemWithSpan {
Can't we just reuse GridCoordinate or GridSpan by using a comparator function or
class in std::sort?

https://codereview.chromium.org/592803003/diff/1/Source/core/rendering/Render...
Source/core/rendering/RenderGrid.cpp:690: // FIXME: Split the grid tracks into
groups that doesn't overlap a <flex> grid track (crbug.com/235258).
We should move this comment below and update it as it doesn't completely match
the latest specification.

https://codereview.chromium.org/592803003/diff/1/Source/core/rendering/Render...
Source/core/rendering/RenderGrid.cpp:695: GridIterator iterator(m_grid,
direction, sizingData.contentSizedTracksIndex[i]);
Is it really good to follow the grid cells' order and not the DOM order? Or even
the order-modified DOM order?

Also the logic prevents inserting the same items several times only in the
direction opposite to |direction|. If a grid item spans along |direction|, it
will be included several times in |sizingData.itemsSortedByIncreasingSpan|.

An idea for that is just to collect the direct children of the grid container,
that should naturally prevent duplicated entries.

https://codereview.chromium.org/592803003/diff/1/Source/core/rendering/Render...
Source/core/rendering/RenderGrid.cpp:703:
std::sort(sizingData.itemsSortedByIncreasingSpan.begin(),
sizingData.itemsSortedByIncreasingSpan.end());
We should use stable_sort whenever we sort, else we can't guarantee the
ordering.

[svillar, 2014-09-24 08:33:11]

Big thanks for reviewing!

https://codereview.chromium.org/592803003/diff/1/LayoutTests/fast/css-grid-la...
File LayoutTests/fast/css-grid-layout/grid-content-sized-columns-resolution.html
(right):

https://codereview.chromium.org/592803003/diff/1/LayoutTests/fast/css-grid-la...
LayoutTests/fast/css-grid-layout/grid-content-sized-columns-resolution.html:101:
<!-- Check that items are processed by ascending span instead of going track by
track forbidding extra space distribution. -->
On 2014/09/23 23:17:31, Julien Chaffraix - PST wrote:
> forbidding? for adding or for bidding (like an auction)?

forbidding in the sense of disallowing

https://codereview.chromium.org/592803003/diff/1/Source/core/rendering/Render...
File Source/core/rendering/RenderGrid.cpp (right):

https://codereview.chromium.org/592803003/diff/1/Source/core/rendering/Render...
Source/core/rendering/RenderGrid.cpp:664: class GridItemWithSpan {
On 2014/09/23 23:17:31, Julien Chaffraix - PST wrote:
> Can't we just reuse GridCoordinate or GridSpan by using a comparator function
or
> class in std::sort?

Thing is that we want to sort grid items but we need to use their grid spans so
I don't see how we can do it without something like this (we're using a
std::pair so this looks like a similar solution but more elegant and explicit).
Neither GridCoordinate nor GridSpan know anything about the renderers.

Apart from that having a class like this saves us a lot of hash lookups because
resolveContentBasedTrackSizingFunctionsForItems() does not need to call
cachedGridCoordinate() again.

https://codereview.chromium.org/592803003/diff/1/Source/core/rendering/Render...
Source/core/rendering/RenderGrid.cpp:690: // FIXME: Split the grid tracks into
groups that doesn't overlap a <flex> grid track (crbug.com/235258).
On 2014/09/23 23:17:31, Julien Chaffraix - PST wrote:
> We should move this comment below and update it as it doesn't completely match
> the latest specification.

OK will do. I've updated a CL for that issue long time ago BTW :). See
https://codereview.chromium.org/448993002/

https://codereview.chromium.org/592803003/diff/1/Source/core/rendering/Render...
Source/core/rendering/RenderGrid.cpp:695: GridIterator iterator(m_grid,
direction, sizingData.contentSizedTracksIndex[i]);
On 2014/09/23 23:17:31, Julien Chaffraix - PST wrote:
> Is it really good to follow the grid cells' order and not the DOM order? Or
even
> the order-modified DOM order?

Following (order modified) DOM order will force us to inspect every single item
in the grid, that would mean to lookup the grid coordinates for all of them. By
just inspecting the content-sized tracks we can save a lot of processing.
 
> Also the logic prevents inserting the same items several times only in the
> direction opposite to |direction|. If a grid item spans along |direction|, it
> will be included several times in |sizingData.itemsSortedByIncreasingSpan|.

Oh good catch, it's just that I placed itemsSet definition inside the loop. It's
meant to be declared outside the for loop. As we hash only by grid item that
will allow us to prevent duplicates no matter the direction they span.
 
> An idea for that is just to collect the direct children of the grid container,
> that should naturally prevent duplicated entries.

https://codereview.chromium.org/592803003/diff/1/Source/core/rendering/Render...
Source/core/rendering/RenderGrid.cpp:703:
std::sort(sizingData.itemsSortedByIncreasingSpan.begin(),
sizingData.itemsSortedByIncreasingSpan.end());
On 2014/09/23 23:17:31, Julien Chaffraix - PST wrote:
> We should use stable_sort whenever we sort, else we can't guarantee the
> ordering.

Well the specs don't really mention anything related to that IIRC. They just
talk about groupping the items based on their spans (they even say "For each
track with an intrinsic track sizing function"). I think that's intentional,
i.e., we don't want to depend on the order we process items to size the grid
tracks. Note that we have likely lost any trace of DOM order by going track by
track.

[svillar, 2014-10-08 13:55:46]

@jchaffraix I think I responded to your questions above. WDTY?

[Julien - ping for review, 2014-10-09 19:01:57]

https://codereview.chromium.org/592803003/diff/1/Source/core/rendering/Render...
File Source/core/rendering/RenderGrid.cpp (right):

https://codereview.chromium.org/592803003/diff/1/Source/core/rendering/Render...
Source/core/rendering/RenderGrid.cpp:664: class GridItemWithSpan {
On 2014/09/24 at 08:33:11, svillar wrote:
> On 2014/09/23 23:17:31, Julien Chaffraix - PST wrote:
> > Can't we just reuse GridCoordinate or GridSpan by using a comparator
function or
> > class in std::sort?
> 
> Thing is that we want to sort grid items but we need to use their grid spans
so I don't see how we can do it without something like this (we're using a
std::pair so this looks like a similar solution but more elegant and explicit).
Neither GridCoordinate nor GridSpan know anything about the renderers.
> 
> Apart from that having a class like this saves us a lot of hash lookups
because resolveContentBasedTrackSizingFunctionsForItems() does not need to call
cachedGridCoordinate() again.

We could get the same functionality with std::pair<RenderBox, GridCoordinate> if
you expose a span() function on GridCoordinate. I think this would be bit better
than a custom class (which adds a lot of extra code) but I could be convinced
otherwise. If you want the class, we should add a class comment along what you
just wrote.

https://codereview.chromium.org/592803003/diff/1/Source/core/rendering/Render...
Source/core/rendering/RenderGrid.cpp:666: GridItemWithSpan(RenderBox& gridItem,
GridCoordinate coordinate, GridTrackSizingDirection direction)
Nit: const GridCoordinate&

https://codereview.chromium.org/592803003/diff/1/Source/core/rendering/Render...
Source/core/rendering/RenderGrid.cpp:683: std::reference_wrapper<RenderBox>
m_gridItem;
This is unused in blink. Why can't we just use a reference directly?

https://codereview.chromium.org/592803003/diff/1/Source/core/rendering/Render...
Source/core/rendering/RenderGrid.cpp:703:
std::sort(sizingData.itemsSortedByIncreasingSpan.begin(),
sizingData.itemsSortedByIncreasingSpan.end());
On 2014/09/24 at 08:33:11, svillar wrote:
> On 2014/09/23 23:17:31, Julien Chaffraix - PST wrote:
> > We should use stable_sort whenever we sort, else we can't guarantee the
> > ordering.
> 
> Well the specs don't really mention anything related to that IIRC. They just
talk about groupping the items based on their spans (they even say "For each
track with an intrinsic track sizing function"). I think that's intentional,
i.e., we don't want to depend on the order we process items to size the grid
tracks. Note that we have likely lost any trace of DOM order by going track by
track.

I think you're right and that's due to step 1 of the "distribute extra space"
section.

[svillar, 2014-10-10 06:50:28]

Thanks for the review. Will upload a new patch soon.

https://codereview.chromium.org/592803003/diff/1/Source/core/rendering/Render...
File Source/core/rendering/RenderGrid.cpp (right):

https://codereview.chromium.org/592803003/diff/1/Source/core/rendering/Render...
Source/core/rendering/RenderGrid.cpp:664: class GridItemWithSpan {
On 2014/10/09 19:01:57, Julien Chaffraix - PST wrote:
> On 2014/09/24 at 08:33:11, svillar wrote:
> > On 2014/09/23 23:17:31, Julien Chaffraix - PST wrote:
> > > Can't we just reuse GridCoordinate or GridSpan by using a comparator
> function or
> > > class in std::sort?
> > 
> > Thing is that we want to sort grid items but we need to use their grid spans
> so I don't see how we can do it without something like this (we're using a
> std::pair so this looks like a similar solution but more elegant and
explicit).
> Neither GridCoordinate nor GridSpan know anything about the renderers.
> > 
> > Apart from that having a class like this saves us a lot of hash lookups
> because resolveContentBasedTrackSizingFunctionsForItems() does not need to
call
> cachedGridCoordinate() again.
> 
> We could get the same functionality with std::pair<RenderBox, GridCoordinate>
if
> you expose a span() function on GridCoordinate. I think this would be bit
better
> than a custom class (which adds a lot of extra code) but I could be convinced
> otherwise. If you want the class, we should add a class comment along what you
> just wrote.

Accessing the members of the class seems more explicit to me than .first/.second
but as it's a very temporal object I don't have a strong opinion here.

https://codereview.chromium.org/592803003/diff/1/Source/core/rendering/Render...
Source/core/rendering/RenderGrid.cpp:683: std::reference_wrapper<RenderBox>
m_gridItem;
On 2014/10/09 19:01:57, Julien Chaffraix - PST wrote:
> This is unused in blink. Why can't we just use a reference directly?

It was required by the std::sort() algorithm as the class needs to be copiable.

[svillar, 2014-10-10 07:58:31]

https://codereview.chromium.org/592803003/diff/1/Source/core/rendering/Render...
File Source/core/rendering/RenderGrid.cpp (right):

https://codereview.chromium.org/592803003/diff/1/Source/core/rendering/Render...
Source/core/rendering/RenderGrid.cpp:664: class GridItemWithSpan {
On 2014/10/10 06:50:28, svillar wrote:
> On 2014/10/09 19:01:57, Julien Chaffraix - PST wrote:
> > On 2014/09/24 at 08:33:11, svillar wrote:
> > > On 2014/09/23 23:17:31, Julien Chaffraix - PST wrote:
> > > > Can't we just reuse GridCoordinate or GridSpan by using a comparator
> > function or
> > > > class in std::sort?
> > > 
> > > Thing is that we want to sort grid items but we need to use their grid
spans
> > so I don't see how we can do it without something like this (we're using a
> > std::pair so this looks like a similar solution but more elegant and
> explicit).
> > Neither GridCoordinate nor GridSpan know anything about the renderers.
> > > 
> > > Apart from that having a class like this saves us a lot of hash lookups
> > because resolveContentBasedTrackSizingFunctionsForItems() does not need to
> call
> > cachedGridCoordinate() again.
> > 
> > We could get the same functionality with std::pair<RenderBox,
GridCoordinate>
> if
> > you expose a span() function on GridCoordinate. I think this would be bit
> better
> > than a custom class (which adds a lot of extra code) but I could be
convinced
> > otherwise. If you want the class, we should add a class comment along what
you
> > just wrote.
> 
> Accessing the members of the class seems more explicit to me than
.first/.second
> but as it's a very temporal object I don't have a strong opinion here.

Said that I think using a class is still better based on the fact that we can
precompute the span, which is quite convenient for the sorting algorithm

[svillar, 2014-10-13 14:44:54]

I guess all doubts should have been clarified after my replies. Do you have any
additional concern Julien? Do you want me to revisit anything in the patch?

[Julien - ping for review, 2014-10-13 19:38:18]

lgtm

https://codereview.chromium.org/592803003/diff/50001/LayoutTests/fast/css-gri...
File LayoutTests/fast/css-grid-layout/grid-content-sized-columns-resolution.html
(right):

https://codereview.chromium.org/592803003/diff/50001/LayoutTests/fast/css-gri...
LayoutTests/fast/css-grid-layout/grid-content-sized-columns-resolution.html:245:
</div>
All the tests are using the same items. It would be nice to have some difference
in them like 2 vs 3-spanning items or 3 spanning items with some growth.

https://codereview.chromium.org/592803003/diff/50001/Source/core/rendering/Re...
File Source/core/rendering/RenderGrid.cpp (right):

https://codereview.chromium.org/592803003/diff/50001/Source/core/rendering/Re...
Source/core/rendering/RenderGrid.cpp:686: std::reference_wrapper<RenderBox>
m_gridItem;
I would just use a pointer, which is unfortunate, but the reference_wrapper
seems artificial. Let's put a comment about why we need these contortions
though.

[svillar, 2014-10-14 06:32:01]

https://codereview.chromium.org/592803003/diff/50001/LayoutTests/fast/css-gri...
File LayoutTests/fast/css-grid-layout/grid-content-sized-columns-resolution.html
(right):

https://codereview.chromium.org/592803003/diff/50001/LayoutTests/fast/css-gri...
LayoutTests/fast/css-grid-layout/grid-content-sized-columns-resolution.html:245:
</div>
On 2014/10/13 19:38:18, Julien Chaffraix - PST wrote:
> All the tests are using the same items. It would be nice to have some
difference
> in them like 2 vs 3-spanning items or 3 spanning items with some growth.

Yeah, it was easier for me to compute the expected results but I'd try to get
some new results.

https://codereview.chromium.org/592803003/diff/50001/Source/core/rendering/Re...
File Source/core/rendering/RenderGrid.cpp (right):

https://codereview.chromium.org/592803003/diff/50001/Source/core/rendering/Re...
Source/core/rendering/RenderGrid.cpp:686: std::reference_wrapper<RenderBox>
m_gridItem;
On 2014/10/13 19:38:18, Julien Chaffraix - PST wrote:
> I would just use a pointer, which is unfortunate, but the reference_wrapper
> seems artificial. Let's put a comment about why we need these contortions
> though.

Acknowledged.

[svillar, 2014-10-14 07:58:32]

The CQ bit was checked by svillar@igalia.com

[commit-bot: I haz the power, 2014-10-14 07:59:06]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/592803003/140001

[commit-bot: I haz the power, 2014-10-14 08:09:21]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2014-10-14 08:09:23]

Try jobs failed on following builders:
  mac_blink_rel on tryserver.blink
(http://build.chromium.org/p/tryserver.blink/builders/mac_blink_rel/builds/26964)

[svillar, 2014-10-14 08:24:20]

Finally removed std::reference_wrapper. We're now using RawPtrWillBeMember<>
instead

[svillar, 2014-10-14 08:24:54]

The CQ bit was checked by svillar@igalia.com

[commit-bot: I haz the power, 2014-10-14 08:25:08]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/592803003/160001

[commit-bot: I haz the power, 2014-10-14 09:28:27]

Committed patchset #4 (id:160001) as 183657