Bug 135701 - [CSS Grid Layout] Sort items by span when resolving content-based track sizing functions
Summary: [CSS Grid Layout] Sort items by span when resolving content-based track sizin...
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: New Bugs (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Sergio Villar Senin
URL:
Keywords:
Depends on:
Blocks: 60731
  Show dependency treegraph
 
Reported: 2014-08-07 07:45 PDT by Sergio Villar Senin
Modified: 2014-10-15 04:44 PDT (History)
9 users (show)

See Also:


Attachments
Patch (12.09 KB, patch)
2014-08-07 09:13 PDT, Sergio Villar Senin
no flags Details | Formatted Diff | Diff
Patch (15.90 KB, patch)
2014-09-12 08:02 PDT, Sergio Villar Senin
darin: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Sergio Villar Senin 2014-08-07 07:45:31 PDT
[CSS Grid Layout] Sort items by span when resolving content-based track sizing functions
Comment 1 Sergio Villar Senin 2014-08-07 09:13:33 PDT
Created attachment 236190 [details]
Patch
Comment 2 Darin Adler 2014-08-18 09:24:15 PDT
Comment on attachment 236190 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=236190&action=review

Looks fine.

Test coverage doesn’t seem to be sufficient; it missed the fact that the sort is not stable, and instead incorrectly is dependent on the pointer values of the grid item renderers. That tells me that we did not check the stability constraint for complex enough grids.

> Source/WebCore/rendering/RenderGrid.cpp:534
> +size_t RenderGrid::gridItemSpan(const RenderBox* child, GridTrackSizingDirection direction)

This should take a RenderBox& rather than a RenderBox* since it takes an argument that can’t be null.

> Source/WebCore/rendering/RenderGrid.cpp:536
> +    GridCoordinate childCoordinate = cachedGridCoordinate(child);

Seems this could just be called coordinate, since this is a local variable and the child context is clear.

> Source/WebCore/rendering/RenderGrid.cpp:537
> +    GridSpan childSpan = (direction == ForRows) ? childCoordinate.rows : childCoordinate.columns;

I suggest using the type GridSpan& or auto& for this instead of making a copy. And also call it just span instead of childSpan.

> Source/WebCore/rendering/RenderGrid.cpp:539
> +    return childSpan.resolvedFinalPosition.toInt() - childSpan.resolvedInitialPosition.toInt() + 1;

Do we have a guarantee this will not be negative?

> Source/WebCore/rendering/RenderGrid.cpp:542
> +typedef std::pair<RenderBox*, size_t> GridItemWithSpan;

Might be easier to read the code if this was a class or struct instead of a pair. It’s not at all clear that “first” is the grid item and “second” is the span.

It doesn’t make sense to use size_t for a span, since a span is not a memory-object-size concept. I’m not sure why the existing code does this; it should not. The type should be unsigned unless there is some reason it needs to be 64-bit. I think that generally this file is overusing the size_t type a lot. But especially for the span value, since we are using toInt to compute the values here, this is an unwanted mix of types, since int is 32-bit and size_t is often 64-bit.

> Source/WebCore/rendering/RenderGrid.cpp:546
> +static bool gridItemWithSpanSorter(const GridItemWithSpan& item1, const GridItemWithSpan& item2)

This function should only compare the span values. It should not compare the RenderBox pointers. It should be named isSpanLessThan, not “grid item with span sorter”, because this comparison function is neither something that returns a “grid item” nor a “sorter”; the current item makes it sound like it returns a “grid item” that has a “span sorter”. Or we could use the naming scheme we use elsewhere with stable_sort and call this compareSpans; not great but better than this name.

> Source/WebCore/rendering/RenderGrid.cpp:551
> +    return item1.first < item2.first;

It is incorrect to sort by comparing pointers. In fact, it can even be a security problem to sort things by pointer value.

> Source/WebCore/rendering/RenderGrid.cpp:554
> +static bool uniquePointerInPair(const GridItemWithSpan& item1, const GridItemWithSpan& item2)

A function named “unique pointer in pair” should return a “unique pointer”. Since it’s a predicate it should have a different name, an adjective phrase instead of noun phrase. Maybe arePointersEqual.

> Source/WebCore/rendering/RenderGrid.cpp:563
>      for (size_t i = 0; i < sizingData.contentSizedTracksIndex.size(); ++i) {

Should change this to a modern for loop.

> Source/WebCore/rendering/RenderGrid.cpp:569
> +        std::stable_sort(itemsSortedByIncreasingSpan.begin(), itemsSortedByIncreasingSpan.end(), gridItemWithSpanSorter);

With the comparison function in this patch, stable_sort is not needed because the comparison function fully orders the values. So if that function was correct, I’d say we should switch to std::sort, since it can be more efficient and we gain nothing from the more complex stable sort.

However, I think the intent here may in fact be to sort in a stable fashion. We want to preserve the ordering of the grid items from the iterator when the spans are equal, so I suppose it’s OK to use stable_sort and fix the comparison function as described above.

> Source/WebCore/rendering/RenderGrid.cpp:570
> +        Vector<GridItemWithSpan>::iterator end = std::unique(itemsSortedByIncreasingSpan.begin(), itemsSortedByIncreasingSpan.end(), uniquePointerInPair);

The type here should be auto as with the iterator in the loop below.

> Source/WebCore/rendering/RenderGrid.cpp:572
> +        for (auto it = itemsSortedByIncreasingSpan.begin(); it != end; ++it) {

If I was writing this I would probably use a shrink call and then a modern for loop instead, but this way is also OK.

> Source/WebCore/rendering/RenderGrid.cpp:573
> +            RenderBox* gridItem = it->first;

Since this can never be null, I suggest we make it a RenderBox& instead.

> LayoutTests/fast/css-grid-layout/grid-item-order-in-content-sized-columns-resolution-expected.txt:8
> +PASS grid-template-columns are identical after grid row swap.
> +PASS grid-template-columns are identical after grid row swap.
> +PASS grid-template-columns are identical after grid row swap.
> +PASS grid-template-columns are identical after grid row swap.
> +PASS grid-template-columns are identical after grid row swap.
> +PASS grid-template-columns are identical after grid row swap.
> +PASS grid-template-columns are identical after grid row swap.
> +PASS grid-template-columns are identical after grid row swap.

It’s better to write tests so they make clear in the output what is being tested. It’s not so good to just right out “success” over and over again. Easier to see what’s failing. That’s why the standard functions write out what is being tested as well as the test results.
Comment 3 Sergio Villar Senin 2014-08-18 09:40:14 PDT
Comment on attachment 236190 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=236190&action=review

Thanks for the detailed review

>> Source/WebCore/rendering/RenderGrid.cpp:546
>> +static bool gridItemWithSpanSorter(const GridItemWithSpan& item1, const GridItemWithSpan& item2)
> 
> This function should only compare the span values. It should not compare the RenderBox pointers. It should be named isSpanLessThan, not “grid item with span sorter”, because this comparison function is neither something that returns a “grid item” nor a “sorter”; the current item makes it sound like it returns a “grid item” that has a “span sorter”. Or we could use the naming scheme we use elsewhere with stable_sort and call this compareSpans; not great but better than this name.

See bellow...

>> Source/WebCore/rendering/RenderGrid.cpp:551
>> +    return item1.first < item2.first;
> 
> It is incorrect to sort by comparing pointers. In fact, it can even be a security problem to sort things by pointer value.

Note that the only reason to have that comparison is to place duplicated pointers together so that std::unique() could remove them later. Maybe I should use a different approach then...
Comment 4 Sergio Villar Senin 2014-08-19 02:19:00 PDT
Comment on attachment 236190 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=236190&action=review

>> Source/WebCore/rendering/RenderGrid.cpp:542
>> +typedef std::pair<RenderBox*, size_t> GridItemWithSpan;
> 
> Might be easier to read the code if this was a class or struct instead of a pair. It’s not at all clear that “first” is the grid item and “second” is the span.
> 
> It doesn’t make sense to use size_t for a span, since a span is not a memory-object-size concept. I’m not sure why the existing code does this; it should not. The type should be unsigned unless there is some reason it needs to be 64-bit. I think that generally this file is overusing the size_t type a lot. But especially for the span value, since we are using toInt to compute the values here, this is an unwanted mix of types, since int is 32-bit and size_t is often 64-bit.

I think the reason why size_t was initially used is because we deal with Vectors and indexes into Vectors. Those indexes are size_t (the same as vector sizes) so even if we use unsigned we'll have to deal with those mix of types.
Comment 5 Darin Adler 2014-08-19 14:01:42 PDT
(In reply to comment #4)
> I think the reason why size_t was initially used is because we deal with Vectors and indexes into Vectors. Those indexes are size_t (the same as vector sizes) so even if we use unsigned we'll have to deal with those mix of types.

Is a span integer used as an index into a Vector?
Comment 6 Sergio Villar Senin 2014-08-20 03:51:56 PDT
(In reply to comment #5)
> (In reply to comment #4)
> > I think the reason why size_t was initially used is because we deal with Vectors and indexes into Vectors. Those indexes are size_t (the same as vector sizes) so even if we use unsigned we'll have to deal with those mix of types.
> 
> Is a span integer used as an index into a Vector?

The span integer can be arbitrary large, as long as the number of columns/rows in the grid. Since we use vectors internally to represent the grid it can be indeed understood as a difference between indexes in a vector.

Apart from that there are many other places using size_t due to the fact that we use vectors, for example the number of columns/rows is computed as vector.size() which is a size_t as well.

The spec does not define any limit to the number of tracks (columns/rows) in a grid. What we could do is to suggest the grid editors to allow implementors to set a cap. That is already allowed for the repeat() function so it seems sensible to me to extend it to grid track definitions that do not use repeat(). For example in the case of repeat() we have 10000 as a limit. Knowing that we have some kind of limit will allow us to safely use unsigned types keeping the internal representation using in Vectors. What do you think?

In any case, can we move this discussion to a different bug? Seems like the size_t vs unsigned issue is orthogonal to the problem this bug is trying to fix.
Comment 7 Darin Adler 2014-08-20 09:00:21 PDT
(In reply to comment #6)
> In any case, can we move this discussion to a different bug?

Sure thing, you can move it wherever you like.

It’s a bad pattern to use data types that are based on the memory model of the computer in a way that produces observable web-page-visible differences.
Comment 8 Sergio Villar Senin 2014-08-20 09:46:39 PDT
(In reply to comment #7)
> (In reply to comment #6)
> > In any case, can we move this discussion to a different bug?
> 
> Sure thing, you can move it wherever you like.

Cool, I think it'd be nice to have a different bug to replace the usage of size_t by unsigned.
 
> It’s a bad pattern to use data types that are based on the memory model of the computer in a way that produces observable web-page-visible differences.

Sure thing. I mean, although I'm maintaining that code right now, the fact is that I was not the original implementor so I was just guessing, not sure about the exact reasons.
Comment 9 Sergio Villar Senin 2014-09-12 08:02:17 PDT
Created attachment 238028 [details]
Patch
Comment 10 Darin Adler 2014-09-12 18:01:16 PDT
Comment on attachment 238028 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=238028&action=review

> Source/WebCore/rendering/RenderGrid.cpp:544
> +    RenderBox* gridItem() const { return m_gridItem; }

This should return RenderBox&.

> Source/WebCore/rendering/RenderGrid.cpp:553
> +    RenderBox* m_gridItem;

This could also be std::reference_wrapper<RenderBox>.

> Source/WebCore/rendering/RenderGrid.cpp:563
>      for (size_t i = 0; i < sizingData.contentSizedTracksIndex.size(); ++i) {
>          GridIterator iterator(m_grid, direction, sizingData.contentSizedTracksIndex[i]);

This loop should be a modern for loop.
Comment 11 Sergio Villar Senin 2014-09-15 07:05:28 PDT
Comment on attachment 238028 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=238028&action=review

>> Source/WebCore/rendering/RenderGrid.cpp:553
>> +    RenderBox* m_gridItem;
> 
> This could also be std::reference_wrapper<RenderBox>.

Oh didn't know about it. Thanks for pointing out.

>> Source/WebCore/rendering/RenderGrid.cpp:563
>>          GridIterator iterator(m_grid, direction, sizingData.contentSizedTracksIndex[i]);
> 
> This loop should be a modern for loop.

The thing is that we use i to access another vectors at the end of the for loop.
Comment 12 Sergio Villar Senin 2014-09-15 07:21:03 PDT
Committed r173620: <http://trac.webkit.org/changeset/173620>