[CSS Grid Layout] Tracks growing beyond limits when they should not

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 25 matching lines @@
 
 namespace blink {
 
 static const int infinity = -1;
 
 class GridTrack {
 public:
     GridTrack()
         : m_baseSize(0)
         , m_growthLimit(0)
+        , m_plannedIncrease(0)

[Julien - ping for review, 2015/01/19 16:36:24]

TBH this field doesn't seem to belong here. It's used only in a single place in
the algorithm ("distribute extra space") soit could be kept outside of
GridTrack.

We used to have |distributeTrackVector| to store the planned increase outside
GridTrack and it's unclear that this approach was completely wrong, just that
our implementation was not totally right.

[svillar, 2015/01/20 08:23:24]

It isn't because the previous approach was wrong, just that this solution seemed
convenient as it allows us not to care about sorts in the Vector of tracks. 

Also that would simplify the fix for another bug I found, which is that we
should not update the sizes of tracks after processing each item, but after
processing all the items with the same span value.

Anyway I'll try some other thing.

[Julien - ping for review, 2015/01/20 13:47:14]

We discussed this part of the change over IRC and Sergio gave some good
arguments towards keeping that.

We currently keep the planned increase independently but that conflicts with the
different sorting that are done during the algorithm. We could wrap GridTrack
into a class with the planned increase but there would be little benefit to do
so (we don't store GridTrack outside layout so the memory footprint argument is
moot) and that would yield to more complexity.

All in all, we are better off with the field inside GridTrack.

     {
     }
 
     const LayoutUnit& baseSize() const
     {
         ASSERT(isGrowthLimitBiggerThanBaseSize());
         return m_baseSize;
     }
 
     const LayoutUnit& growthLimit() const
@@ skipping 36 matching lines @@
     {
         return m_growthLimit == infinity;
     }
 
     const LayoutUnit& growthLimitIfNotInfinite() const
     {
         ASSERT(isGrowthLimitBiggerThanBaseSize());
         return (m_growthLimit == infinity) ? m_baseSize : m_growthLimit;
     }
 
+    const LayoutUnit& plannedIncrease() const { return m_plannedIncrease; }
+    void setPlannedIncrease(const LayoutUnit& plannedIncrease)
+    {
+        ASSERT(plannedIncrease >= 0);
+        m_plannedIncrease = plannedIncrease;
+    }
+
+    void growPlannedIncrease(const LayoutUnit& plannedIncrease)
+    {
+        ASSERT(plannedIncrease >= 0);
+        m_plannedIncrease += plannedIncrease;

[Julien - ping for review, 2015/01/19 16:36:24]

This concerns me because we don't enforce that we don't forget to commit this
planned increase.

+    }
+
 private:
     bool isGrowthLimitBiggerThanBaseSize() const { return growthLimitIsInfinite() || m_growthLimit >= m_baseSize; }
 
     void ensureGrowthLimitIsBiggerThanBaseSize()
     {
         if (m_growthLimit != infinity && m_growthLimit < m_baseSize)
             m_growthLimit = m_baseSize;
     }
 
     LayoutUnit m_baseSize;
     LayoutUnit m_growthLimit;
+    LayoutUnit m_plannedIncrease;
 };
 
 struct GridTrackForNormalization {
     GridTrackForNormalization(const GridTrack& track, double flex)
         : m_track(&track)
         , m_flex(flex)
         , m_normalizedFlexValue(track.baseSize() / flex)
     {
     }
 
@@ skipping 98 matching lines @@
         : columnTracks(gridColumnCount)
         , rowTracks(gridRowCount)
     {
     }
 
     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;
     WillBeHeapVector<GridItemWithSpan> itemsSortedByIncreasingSpan;
-    Vector<size_t> growAboveMaxBreadthTrackIndexes;
+    Vector<GridTrack*> growBeyondGrowthLimitsTracks;
 };
 
 RenderGrid::RenderGrid(Element* element)
     : RenderBlock(element)
     , m_gridIsDirty(true)
     , m_orderIterator(this)
 {
     ASSERT(!childrenInline());
 }
 
@@ skipping 186 matching lines @@
         return;
 
     // 3. Grow all Grid tracks in GridTracks from their UsedBreadth up to their MaxBreadth value until
     // availableLogicalSpace (RemainingSpace in the specs) is exhausted.
     const size_t tracksSize = tracks.size();
     if (!hasUndefinedRemainingSpace) {
         Vector<GridTrack*> tracksForDistribution(tracksSize);
         for (size_t i = 0; i < tracksSize; ++i)
             tracksForDistribution[i] = tracks.data() + i;
 
-        distributeSpaceToTracks(tracksForDistribution, 0, &GridTrack::baseSize, &GridTrack::growBaseSize, sizingData, availableLogicalSpace);
+        distributeSpaceToTracks(tracksForDistribution, nullptr, &GridTrack::baseSize, &GridTrack::growBaseSize, sizingData, availableLogicalSpace);
     } else {
         for (auto& track : tracks)
             track.setBaseSize(track.growthLimit());
     }
 
     if (flexibleSizedTracksIndex.isEmpty())
         return;
 
     // 4. Grow all Grid tracks having a fraction as the MaxTrackSizingFunction.
     double normalizedFractionBreadth = 0;
@@ skipping 294 matching lines @@
         track.setGrowthLimit(std::max(track.growthLimit(), maxContentForChild(gridItem, direction, columnTracks)));
 }
 
 void RenderGrid::resolveContentBasedTrackSizingFunctionsForItems(GridTrackSizingDirection direction, GridSizingData& sizingData, GridItemWithSpan& gridItemWithSpan, FilterFunction filterFunction, SizingFunction sizingFunction, AccumulatorGetter trackGetter, AccumulatorGrowFunction trackGrowthFunction, FilterFunction growAboveMaxBreadthFilterFunction)
 {
     ASSERT(gridItemWithSpan.span() > 1);
     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.growAboveMaxBreadthTrackIndexes.shrink(0);
+    sizingData.growBeyondGrowthLimitsTracks.shrink(0);
     sizingData.filteredTracks.shrink(0);
     for (GridResolvedPosition trackPosition = initialTrackPosition; trackPosition <= finalTrackPosition; ++trackPosition) {
         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);
+        if (!growAboveMaxBreadthFilterFunction || (trackSize.*growAboveMaxBreadthFilterFunction)())
+            sizingData.growBeyondGrowthLimitsTracks.append(&track);
     }
 
     if (sizingData.filteredTracks.isEmpty())
         return;
 
-    LayoutUnit additionalBreadthSpace = (this->*sizingFunction)(gridItemWithSpan.gridItem(), direction, sizingData.columnTracks);
+    LayoutUnit extraSpace = (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)();
+        extraSpace -= (track.*trackGetter)();
     }
 
-    // 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.growAboveMaxBreadthTrackIndexes, trackGetter, trackGrowthFunction, sizingData, additionalBreadthSpace);
+    extraSpace = std::max<LayoutUnit>(0, extraSpace);
+    Vector<GridTrack*>* tracksToGrowBeyondGrowthLimits = sizingData.growBeyondGrowthLimitsTracks.isEmpty() ? &sizingData.filteredTracks : &sizingData.growBeyondGrowthLimitsTracks;
+    distributeSpaceToTracks(sizingData.filteredTracks, tracksToGrowBeyondGrowthLimits, trackGetter, trackGrowthFunction, sizingData, extraSpace);
 }
 
 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->growthLimitIsInfinite() && track2->growthLimitIsInfinite())
         return false;
 
     if (track1->growthLimitIsInfinite() || track2->growthLimitIsInfinite())
         return track2->growthLimitIsInfinite();
 
     return (track1->growthLimit() - track1->baseSize()) < (track2->growthLimit() - track2->baseSize());
 }
 
-void RenderGrid::distributeSpaceToTracks(Vector<GridTrack*>& tracks, Vector<size_t>* growAboveMaxBreadthTrackIndexes, AccumulatorGetter trackGetter, AccumulatorGrowFunction trackGrowthFunction, GridSizingData& sizingData, LayoutUnit& availableLogicalSpace)
+void RenderGrid::distributeSpaceToTracks(Vector<GridTrack*>& tracks, const Vector<GridTrack*>* growBeyondGrowthLimitsTracks, AccumulatorGetter trackGetter, AccumulatorGrowFunction trackGrowthFunction, GridSizingData& sizingData, LayoutUnit& availableLogicalSpace)
 {
-    ASSERT(availableLogicalSpace > 0);

[Julien - ping for review, 2015/01/19 16:36:24]

If you don't have any |availableLogicalSpace|, it seems wasteful to try to
distribute it below.

[svillar, 2015/01/20 08:23:24]

Correct, I removed it by accident, it was part of a previous downstream instance
of the patch. I'll bring it back.

     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);
-        const LayoutUnit& trackBreadth = (tracks[i]->*trackGetter)();
-        LayoutUnit growthShare = track.growthLimitIsInfinite() ? availableLogicalSpaceShare : std::min(availableLogicalSpaceShare, track.growthLimit() - trackBreadth);
-        sizingData.distributeTrackVector[i] = trackBreadth;
+    size_t i = 0;
+    for (auto* track : tracks) {
+        LayoutUnit availableLogicalSpaceShare = availableLogicalSpace / (tracksSize - i++);
+        const LayoutUnit& trackBreadth = (track->*trackGetter)();
+        LayoutUnit growthShare = track->growthLimitIsInfinite() ? availableLogicalSpaceShare : std::min(availableLogicalSpaceShare, track->growthLimit() - trackBreadth);
+        track->setPlannedIncrease(0);
         // 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;
+            track->growPlannedIncrease(growthShare);
             availableLogicalSpace -= 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.
-        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;
+    if (availableLogicalSpace > 0 && growBeyondGrowthLimitsTracks) {
+        size_t tracksGrowingAboveMaxBreadthSize = growBeyondGrowthLimitsTracks->size();
+        size_t i = 0;
+        for (auto* track : *growBeyondGrowthLimitsTracks) {
+            LayoutUnit growthShare = availableLogicalSpace / (tracksGrowingAboveMaxBreadthSize - i++);

[Julien - ping for review, 2015/01/19 16:36:24]

The pattern with the auto-for loop + manual iterator doesn't seem like an
improvement over the old code that was explicit.

[svillar, 2015/01/20 08:23:24]

Yeah, I don't have a strong opinion here, I can rollback this change.

+            track->growPlannedIncrease(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);
+    for (auto* track: tracks) {
+        if (auto plannedIncrease = track->plannedIncrease())
+            (track->*trackGrowthFunction)(plannedIncrease);
     }
 }
 
 #if ENABLE(ASSERT)
 bool RenderGrid::tracksAreWiderThanMinTrackBreadth(GridTrackSizingDirection direction, const Vector<GridTrack>& tracks)
 {
     for (size_t i = 0; i < tracks.size(); ++i) {
         GridTrackSize trackSize = gridTrackSize(direction, i);
         const GridLength& minTrackBreadth = trackSize.minTrackBreadth();
         if (computeUsedBreadthOfMinLength(direction, minTrackBreadth) > tracks[i].baseSize())
@@ skipping 813 matching lines @@
     if (isOutOfFlowPositioned())
         return "RenderGrid (positioned)";
     if (isAnonymous())
         return "RenderGrid (generated)";
     if (isRelPositioned())
         return "RenderGrid (relative positioned)";
     return "RenderGrid";
 }
 
 } // namespace blink