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

Source/core/rendering/RenderGrid.cpp

Index: Source/core/rendering/RenderGrid.cpp
diff --git a/Source/core/rendering/RenderGrid.cpp b/Source/core/rendering/RenderGrid.cpp
index 508b5fe0f880dec58c923b9335334aa292519cde..304dc6712bc589a6495e0472abbe7b0ecdfa14c9 100644
--- a/Source/core/rendering/RenderGrid.cpp
+++ b/Source/core/rendering/RenderGrid.cpp
@@ -184,6 +184,7 @@ public:
     // Performance optimization: hold onto these Vectors until the end of Layout to avoid repeated malloc / free.
     Vector<LayoutUnit> distributeTrackVector;
     Vector<GridTrack*> filteredTracks;
+    Vector<GridItemWithSpan> itemsSortedByIncreasingSpan;
 };
 
 RenderGrid::RenderGrid(Element* element)
@@ -660,62 +661,67 @@ LayoutUnit RenderGrid::maxContentForChild(RenderBox& child, GridTrackSizingDirec
     return logicalHeightForChild(child, columnTracks);
 }
 
-size_t RenderGrid::gridItemSpan(const RenderBox& child, GridTrackSizingDirection direction)
-{
-    GridCoordinate childCoordinate = cachedGridCoordinate(child);
-    GridSpan childSpan = (direction == ForRows) ? childCoordinate.rows : childCoordinate.columns;
-
-    return childSpan.resolvedFinalPosition.toInt() - childSpan.resolvedInitialPosition.toInt() + 1;
-}
-
-typedef std::pair<RenderBox*, size_t> GridItemWithSpan;
+class GridItemWithSpan {

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

Can't we just reuse GridCoordinate or GridSpan by using a comparator function or
class in std::sort?

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

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.

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

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.

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

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.

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

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

+public:
+    GridItemWithSpan(RenderBox& gridItem, GridCoordinate coordinate, GridTrackSizingDirection direction)

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

Nit: const GridCoordinate&

+        : m_gridItem(gridItem)
+        , m_coordinate(coordinate)
+    {
+        const GridSpan& span = (direction == ForRows) ? coordinate.rows : coordinate.columns;
+        m_span = span.resolvedFinalPosition.toInt() - span.resolvedInitialPosition.toInt() + 1;
+    }
 
-// This function sorts by span (.second in the pair) but also places pointers (.first in the pair) to the same object in
-// consecutive positions so duplicates could be easily removed with std::unique() for example.
-static bool gridItemWithSpanSorter(const GridItemWithSpan& item1, const GridItemWithSpan& item2)
-{
-    if (item1.second != item2.second)
-        return item1.second < item2.second;
+    RenderBox& gridItem() const { return m_gridItem; }
+    GridCoordinate coordinate() const { return m_coordinate; }
 
-    return item1.first < item2.first;
-}
+    bool operator<(const GridItemWithSpan other) const
+    {
+        return m_span < other.m_span;
+    }
 
-static bool uniquePointerInPair(const GridItemWithSpan& item1, const GridItemWithSpan& item2)
-{
-    return item1.first == item2.first;
-}
+private:
+    std::reference_wrapper<RenderBox> m_gridItem;

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

This is unused in blink. Why can't we just use a reference directly?

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

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

+    GridCoordinate m_coordinate;
+    size_t m_span;
+};
 
 void RenderGrid::resolveContentBasedTrackSizingFunctions(GridTrackSizingDirection direction, GridSizingData& sizingData, LayoutUnit& availableLogicalSpace)
 {
     // FIXME: Split the grid tracks into groups that doesn't overlap a <flex> grid track (crbug.com/235258).

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

We should move this comment below and update it as it doesn't completely match
the latest specification.

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

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

 
-    for (size_t i = 0; i < sizingData.contentSizedTracksIndex.size(); ++i) {
-        size_t trackIndex = sizingData.contentSizedTracksIndex[i];
-        GridIterator iterator(m_grid, direction, trackIndex);
-        Vector<GridItemWithSpan> itemsSortedByIncreasingSpan;
-
-        while (RenderBox* gridItem = iterator.nextGridItem())
-            itemsSortedByIncreasingSpan.append(std::make_pair(gridItem, gridItemSpan(*gridItem, direction)));
-        std::stable_sort(itemsSortedByIncreasingSpan.begin(), itemsSortedByIncreasingSpan.end(), gridItemWithSpanSorter);
-        Vector<GridItemWithSpan>::iterator end = std::unique(itemsSortedByIncreasingSpan.begin(), itemsSortedByIncreasingSpan.end(), uniquePointerInPair);
-
-        for (Vector<GridItemWithSpan>::iterator it = itemsSortedByIncreasingSpan.begin(); it != end; ++it) {
-            RenderBox* gridItem = it->first;
-            resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, *gridItem, &GridTrackSize::hasMinOrMaxContentMinTrackBreadth, &RenderGrid::minContentForChild, &GridTrack::usedBreadth, &GridTrack::growUsedBreadth);
-            resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, *gridItem, &GridTrackSize::hasMaxContentMinTrackBreadth, &RenderGrid::maxContentForChild, &GridTrack::usedBreadth, &GridTrack::growUsedBreadth);
-            resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, *gridItem, &GridTrackSize::hasMinOrMaxContentMaxTrackBreadth, &RenderGrid::minContentForChild, &GridTrack::maxBreadthIfNotInfinite, &GridTrack::growMaxBreadth);
-            resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, *gridItem, &GridTrackSize::hasMaxContentMaxTrackBreadth, &RenderGrid::maxContentForChild, &GridTrack::maxBreadthIfNotInfinite, &GridTrack::growMaxBreadth);
+    sizingData.itemsSortedByIncreasingSpan.shrink(0);
+    size_t contentSizedTracksCount = sizingData.contentSizedTracksIndex.size();
+    for (size_t i = 0; i < contentSizedTracksCount; ++i) {
+        GridIterator iterator(m_grid, direction, sizingData.contentSizedTracksIndex[i]);

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

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.

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

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.
 
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.
 

+        HashSet<RenderBox*> itemsSet;
+
+        while (RenderBox* gridItem = iterator.nextGridItem()) {
+            if (itemsSet.add(gridItem).isNewEntry)
+                sizingData.itemsSortedByIncreasingSpan.append(GridItemWithSpan(*gridItem, cachedGridCoordinate(*gridItem), direction));
         }
+    }
+    std::sort(sizingData.itemsSortedByIncreasingSpan.begin(), sizingData.itemsSortedByIncreasingSpan.end());

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

We should use stable_sort whenever we sort, else we can't guarantee the
ordering.

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

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.

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

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

+
+    Vector<GridItemWithSpan>::iterator end = sizingData.itemsSortedByIncreasingSpan.end();
+    for (Vector<GridItemWithSpan>::iterator it = sizingData.itemsSortedByIncreasingSpan.begin(); it != end; ++it) {
+        GridItemWithSpan itemWithSpan = *it;
+        resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, itemWithSpan, &GridTrackSize::hasMinOrMaxContentMinTrackBreadth, &RenderGrid::minContentForChild, &GridTrack::usedBreadth, &GridTrack::growUsedBreadth);
+        resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, itemWithSpan, &GridTrackSize::hasMaxContentMinTrackBreadth, &RenderGrid::maxContentForChild, &GridTrack::usedBreadth, &GridTrack::growUsedBreadth);
+        resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, itemWithSpan, &GridTrackSize::hasMinOrMaxContentMaxTrackBreadth, &RenderGrid::minContentForChild, &GridTrack::maxBreadthIfNotInfinite, &GridTrack::growMaxBreadth);
+        resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, itemWithSpan, &GridTrackSize::hasMaxContentMaxTrackBreadth, &RenderGrid::maxContentForChild, &GridTrack::maxBreadthIfNotInfinite, &GridTrack::growMaxBreadth);
+    }
 
+    for (size_t i = 0; i < contentSizedTracksCount; ++i) {
+        size_t trackIndex = sizingData.contentSizedTracksIndex[i];
         GridTrack& track = (direction == ForColumns) ? sizingData.columnTracks[trackIndex] : sizingData.rowTracks[trackIndex];
         if (track.m_maxBreadth == infinity)
             track.m_maxBreadth = track.m_usedBreadth;
     }
 }
 
-void RenderGrid::resolveContentBasedTrackSizingFunctionsForItems(GridTrackSizingDirection direction, GridSizingData& sizingData, RenderBox& gridItem, FilterFunction filterFunction, SizingFunction sizingFunction, AccumulatorGetter trackGetter, AccumulatorGrowFunction trackGrowthFunction)
+void RenderGrid::resolveContentBasedTrackSizingFunctionsForItems(GridTrackSizingDirection direction, GridSizingData& sizingData, GridItemWithSpan& gridItemWithSpan, FilterFunction filterFunction, SizingFunction sizingFunction, AccumulatorGetter trackGetter, AccumulatorGrowFunction trackGrowthFunction)
 {
-    const GridCoordinate coordinate = cachedGridCoordinate(gridItem);
+    const GridCoordinate coordinate = gridItemWithSpan.coordinate();
     const GridResolvedPosition initialTrackPosition = (direction == ForColumns) ? coordinate.columns.resolvedInitialPosition : coordinate.rows.resolvedInitialPosition;
     const GridResolvedPosition finalTrackPosition = (direction == ForColumns) ? coordinate.columns.resolvedFinalPosition : coordinate.rows.resolvedFinalPosition;
 
@@ -732,7 +738,7 @@ void RenderGrid::resolveContentBasedTrackSizingFunctionsForItems(GridTrackSizing
     if (sizingData.filteredTracks.isEmpty())
         return;
 
-    LayoutUnit additionalBreadthSpace = (this->*sizingFunction)(gridItem, direction, sizingData.columnTracks);
+    LayoutUnit additionalBreadthSpace = (this->*sizingFunction)(gridItemWithSpan.gridItem(), direction, sizingData.columnTracks);
     for (GridResolvedPosition trackIndexForSpace = initialTrackPosition; trackIndexForSpace <= finalTrackPosition; ++trackIndexForSpace) {
         GridTrack& track = (direction == ForColumns) ? sizingData.columnTracks[trackIndexForSpace.toInt()] : sizingData.rowTracks[trackIndexForSpace.toInt()];
         additionalBreadthSpace -= (track.*trackGetter)();