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

Source/core/rendering/RenderGrid.cpp

 /*
  * Copyright (C) 2011 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
@@ skipping 166 matching lines @@
     {
     }
 
     Vector<GridTrack> columnTracks;
     Vector<GridTrack> rowTracks;
     Vector<size_t> contentSizedTracksIndex;
 
     // 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)
     : RenderBlock(element)
     , m_gridIsDirty(true)
     , m_orderIterator(this)
 {
     ASSERT(!childrenInline());
 }
 
@@ skipping 456 matching lines @@
 
     if (direction == ForColumns) {
         // FIXME: It's unclear if we should return the intrinsic width or the preferred width.
         // See http://lists.w3.org/Archives/Public/www-style/2013Jan/0245.html
         return child.maxPreferredLogicalWidth() + marginIntrinsicLogicalWidthForChild(&child);
     }
 
     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;
+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;
+    }
 
-    return childSpan.resolvedFinalPosition.toInt() - childSpan.resolvedInitialPosition.toInt() + 1;
-}
+    RenderBox& gridItem() const { return m_gridItem; }
+    GridCoordinate coordinate() const { return m_coordinate; }
 
-typedef std::pair<RenderBox*, size_t> GridItemWithSpan;
+    bool operator<(const GridItemWithSpan other) const
+    {
+        return m_span < other.m_span;
+    }
 
-// 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;
-
-    return item1.first < item2.first;
-}
-
-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) {
+    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];
-        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);
-        }
-
         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;
 
     sizingData.filteredTracks.shrink(0);
     for (GridResolvedPosition trackPosition = initialTrackPosition; trackPosition <= finalTrackPosition; ++trackPosition) {
         const GridTrackSize& trackSize = gridTrackSize(direction, trackPosition.toInt());
         if (!(trackSize.*filterFunction)())
             continue;
 
         GridTrack& track = (direction == ForColumns) ? sizingData.columnTracks[trackPosition.toInt()] : sizingData.rowTracks[trackPosition.toInt()];
         sizingData.filteredTracks.append(&track);
     }
 
     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)();
     }
 
     // FIXME: We should pass different values for |tracksForGrowthAboveMaxBreadth|.
 
     // Specs mandate to floor additionalBreadthSpace (extra-space in specs) to 0. Instead we directly avoid the function
     // call in those cases as it will be a noop in terms of track sizing.
     if (additionalBreadthSpace > 0)
@@ skipping 708 matching lines @@
     if (isOutOfFlowPositioned())
         return "RenderGrid (positioned)";
     if (isAnonymous())
         return "RenderGrid (generated)";
     if (isRelPositioned())
         return "RenderGrid (relative positioned)";
     return "RenderGrid";
 }
 
 } // namespace blink