[CSSGridLayout] Pass the valid tracks for |tracksForGrowAboveMaxBreadth|

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<size_t> growAboveMaxBreadthTrackIndexes;
 };
 
 RenderGrid::RenderGrid(Element* element)
     : RenderBlock(element)
     , m_gridIsDirty(true)
     , m_orderIterator(this)
 {
     ASSERT(!childrenInline());
 }
 
@@ skipping 497 matching lines @@
         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::hasMinOrMaxContentMinTrackBreadth, &RenderGrid::minContentForChild, &GridTrack::usedBreadth, &GridTrack::growUsedBreadth, &GridTrackSize::hasMinContentMinTrackBreadthAndMinOrMaxContentMaxTrackBreadth);
+            resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, *gridItem, &GridTrackSize::hasMaxContentMinTrackBreadth, &RenderGrid::maxContentForChild, &GridTrack::usedBreadth, &GridTrack::growUsedBreadth, &GridTrackSize::hasMaxContentMinTrackBreadthAndMaxContentMaxTrackBreadth);
             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, RenderBox& gridItem, FilterFunction filterFunction, SizingFunction sizingFunction, AccumulatorGetter trackGetter, AccumulatorGrowFunction trackGrowthFunction, FilterFunction growAboveMaxBreadthFilterFunction)
 {
     const GridCoordinate coordinate = cachedGridCoordinate(gridItem);
     const GridResolvedPosition initialTrackPosition = (direction == ForColumns) ? coordinate.columns.resolvedInitialPosition : coordinate.rows.resolvedInitialPosition;
     const GridResolvedPosition finalTrackPosition = (direction == ForColumns) ? coordinate.columns.resolvedFinalPosition : coordinate.rows.resolvedFinalPosition;
 
+    sizingData.growAboveMaxBreadthTrackIndexes.shrink(0);
     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 (growAboveMaxBreadthFilterFunction && (trackSize.*growAboveMaxBreadthFilterFunction)())
+            sizingData.growAboveMaxBreadthTrackIndexes.append(sizingData.filteredTracks.size() - 1);

[Julien - ping for review, 2014/09/30 17:36:57]

This line seems really weird: we are checking the track at |trackPosition| but
are inserting a different index. Why don't we just insert trackPosition.toInt()
? Also why is this logic operating on size_t and not GridTrack& ?

[svillar, 2014/10/01 07:48:56]

The reason is because this function and distributeSpaceToTracks operate on a
different set of tracks. This function filters the tracks between initial and
final position. But distributeSpaceToTracks will use only the set of filtered
tracks. And then we have to select from that set of filtered tracks just the
ones subject to grow beyond growth limits. That's why we collect the indexes of
the tracks inside sizingData.filteredTracks.

[Julien - ping for review, 2014/10/21 16:58:08]

Now I understand the rationale for the logic but storing the indexes into
another vector is super dangerous. Ideally we should push the GridTrack
directly. As the code stands, it won't work as we would need to get this index
back but if we were to introduce some wrappers around GridTrack to hold the
temporary growing information, we could make it work. It's a good follow-up
change.

[svillar, 2014/10/22 07:16:17]

Exactly that's the reason why I used the indexes, but I agree that we might
switch to some wrapper ala GridItemWithSpan in a follow-up change.

     }
 
     if (sizingData.filteredTracks.isEmpty())
         return;
 
     LayoutUnit additionalBreadthSpace = (this->*sizingFunction)(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)
-        distributeSpaceToTracks(sizingData.filteredTracks, &sizingData.filteredTracks, trackGetter, trackGrowthFunction, sizingData, additionalBreadthSpace);
+        distributeSpaceToTracks(sizingData.filteredTracks, &sizingData.growAboveMaxBreadthTrackIndexes, trackGetter, trackGrowthFunction, sizingData, additionalBreadthSpace);
 }
 
 static bool sortByGridTrackGrowthPotential(const GridTrack* track1, const GridTrack* track2)
 {
     // This check ensures that we respect the irreflexivity property of the strict weak ordering required by std::sort
     // (forall x: NOT x < x).
     if (track1->m_maxBreadth == infinity && track2->m_maxBreadth == infinity)
         return false;
 
     if (track1->m_maxBreadth == infinity || track2->m_maxBreadth == infinity)
         return track2->m_maxBreadth == infinity;
 
     return (track1->m_maxBreadth - track1->m_usedBreadth) < (track2->m_maxBreadth - track2->m_usedBreadth);
 }
 
-void RenderGrid::distributeSpaceToTracks(Vector<GridTrack*>& tracks, Vector<GridTrack*>* tracksForGrowthAboveMaxBreadth, AccumulatorGetter trackGetter, AccumulatorGrowFunction trackGrowthFunction, GridSizingData& sizingData, LayoutUnit& availableLogicalSpace)
+void RenderGrid::distributeSpaceToTracks(Vector<GridTrack*>& tracks, Vector<size_t>* growAboveMaxBreadthTrackIndexes, AccumulatorGetter trackGetter, AccumulatorGrowFunction trackGrowthFunction, GridSizingData& sizingData, LayoutUnit& availableLogicalSpace)
 {
     ASSERT(availableLogicalSpace > 0);
     std::sort(tracks.begin(), tracks.end(), sortByGridTrackGrowthPotential);
 
     size_t tracksSize = tracks.size();
     sizingData.distributeTrackVector.resize(tracksSize);
 
     for (size_t i = 0; i < tracksSize; ++i) {
         GridTrack& track = *tracks[i];
         LayoutUnit availableLogicalSpaceShare = availableLogicalSpace / (tracksSize - i);
         LayoutUnit trackBreadth = (tracks[i]->*trackGetter)();
         LayoutUnit growthShare = track.m_maxBreadth == infinity ? availableLogicalSpaceShare : std::min(availableLogicalSpaceShare, track.m_maxBreadth - trackBreadth);
         ASSERT(growthShare != infinity);
         sizingData.distributeTrackVector[i] = trackBreadth;
         // We should never shrink any grid track or else we can't guarantee we abide by our min-sizing function.
         if (growthShare > 0) {
             sizingData.distributeTrackVector[i] += growthShare;
             availableLogicalSpace -= growthShare;
         }
     }
 
-    if (availableLogicalSpace > 0 && tracksForGrowthAboveMaxBreadth) {
-        tracksSize = tracksForGrowthAboveMaxBreadth->size();
-        for (size_t i = 0; i < tracksSize; ++i) {
-            LayoutUnit growthShare = availableLogicalSpace / (tracksSize - i);
-            sizingData.distributeTrackVector[i] += growthShare;
+    if (availableLogicalSpace > 0 && growAboveMaxBreadthTrackIndexes) {
+        size_t indexesSize = growAboveMaxBreadthTrackIndexes->size();
+        size_t tracksGrowingAboveMaxBreadthSize = indexesSize ? indexesSize : tracksSize;
+        // If we have a non-null empty vector of track indexes to grow above max breadth means that we should grow all
+        // affected tracks.

[Julien - ping for review, 2014/09/30 17:36:57]

The specification uses 2 passes for growth. Is this implementation guaranteed to
perform like the specification?

[svillar, 2014/10/01 07:48:57]

Hmm I don't get this. Which 2 passes are you talking about?

I'm basing the implementation on the part that describes the distribution of
extra space http://dev.w3.org/csswg/css-grid/#distribute-extra-space when it
talks about "3. Distribute space beyond growth limits:"

The rest of the algorithm is already there if I am not wrong.

[Julien - ping for review, 2014/10/21 16:58:08]

I think I was referring to this text from step 2: "(and continuing to grow the
unfrozen tracks as needed)". I thought we would need some extra passes to do it
but on second thoughts we should be good as we order the tracks by grow
potential.
You're right, most of the algorithm is here.

[svillar, 2014/10/22 07:16:17]

Yeah it isn't obvious after a first read but the fact that the algorithm does
the sorting before growing the tracks guarantees that we equally grow all of
them while respecting the upper limits.

My opinion is that the MS algorithm was designed to be efficient and avoid as
many passes as possible. The counterpart is that the resulting code is far for
self-explanatory. Switching to the rewritten algo will improve the situation
although we should be very careful with the implementation.

+        for (size_t i = 0; i < tracksGrowingAboveMaxBreadthSize; ++i) {
+            LayoutUnit growthShare = availableLogicalSpace / (tracksGrowingAboveMaxBreadthSize - i);
+            size_t distributeTrackIndex = indexesSize ? growAboveMaxBreadthTrackIndexes->at(i) : i;
+            sizingData.distributeTrackVector[distributeTrackIndex] += growthShare;
             availableLogicalSpace -= growthShare;
         }
     }
 
     for (size_t i = 0; i < tracksSize; ++i) {
         LayoutUnit growth = sizingData.distributeTrackVector[i] - (tracks[i]->*trackGetter)();
         if (growth >= 0)
             (tracks[i]->*trackGrowthFunction)(growth);
     }
 }
@@ skipping 655 matching lines @@
     if (isOutOfFlowPositioned())
         return "RenderGrid (positioned)";
     if (isAnonymous())
         return "RenderGrid (generated)";
     if (isRelPositioned())
         return "RenderGrid (relative positioned)";
     return "RenderGrid";
 }
 
 } // namespace blink