[CSS Grid Layout] Flex tracks sizing alg must handle 0fr values

Source/core/layout/LayoutGrid.cpp

Index: Source/core/layout/LayoutGrid.cpp
diff --git a/Source/core/layout/LayoutGrid.cpp b/Source/core/layout/LayoutGrid.cpp
index fc5aa6d6f0a9b1923406f12b6936ff71a7b446b3..b0d3f12e06e1b4976c854bffa317ee028ea809bf 100644
--- a/Source/core/layout/LayoutGrid.cpp
+++ b/Source/core/layout/LayoutGrid.cpp
@@ -142,28 +142,6 @@ public:
     LayoutUnit distributionOffset = -1;
 };
 
-struct GridTrackForNormalization {
-    GridTrackForNormalization(const GridTrack& track, double flex)
-        : m_track(&track)
-        , m_flex(flex)
-        , m_normalizedFlexValue(track.baseSize() / flex)
-    {
-    }
-
-    // Required by std::sort.
-    GridTrackForNormalization& operator=(const GridTrackForNormalization& o)
-    {
-        m_track = o.m_track;
-        m_flex = o.m_flex;
-        m_normalizedFlexValue = o.m_normalizedFlexValue;
-        return *this;
-    }
-
-    const GridTrack* m_track;
-    double m_flex;
-    LayoutUnit m_normalizedFlexValue;
-};
-
 enum TrackSizeRestriction {
     AllowInfinity,
     ForbidInfinity,
@@ -396,6 +374,11 @@ bool LayoutGrid::gridElementIsShrinkToFit()
     return isFloatingOrOutOfFlowPositioned();
 }
 
+static inline double normalizedFlexFraction(const GridTrack& track, double flexFactor)
+{
+    return flexFactor > 1 ? track.baseSize() / flexFactor : track.baseSize().toDouble();
+}
+
 void LayoutGrid::computeUsedBreadthOfGridTracks(GridTrackSizingDirection direction, GridSizingData& sizingData, LayoutUnit& freeSpace)
 {
     const LayoutUnit initialFreeSpace = freeSpace;
@@ -456,14 +439,12 @@ void LayoutGrid::computeUsedBreadthOfGridTracks(GridTrackSizingDirection directi
         return;
 
     // 4. Grow all Grid tracks having a fraction as the MaxTrackSizingFunction.
-    double normalizedFractionBreadth = 0;
+    double flexFraction = 0;
     if (!hasUndefinedRemainingSpace) {
-        normalizedFractionBreadth = computeNormalizedFractionBreadth(tracks, GridSpan(0, tracks.size() - 1), direction, initialFreeSpace);
+        flexFraction = findFlexFactorUnitSize(tracks, GridSpan(0, tracks.size() - 1), direction, initialFreeSpace);
     } else {
-        for (const auto& trackIndex : flexibleSizedTracksIndex) {
-            GridTrackSize trackSize = gridTrackSize(direction, trackIndex);
-            normalizedFractionBreadth = std::max(normalizedFractionBreadth, tracks[trackIndex].baseSize() / trackSize.maxTrackBreadth().flex());
-        }
+        for (const auto& trackIndex : flexibleSizedTracksIndex)
+            flexFraction = std::max(flexFraction, normalizedFlexFraction(tracks[trackIndex], gridTrackSize(direction, trackIndex).maxTrackBreadth().flex()));
 
         for (size_t i = 0; i < flexibleSizedTracksIndex.size(); ++i) {
             GridIterator iterator(m_grid, direction, flexibleSizedTracksIndex[i]);
@@ -475,8 +456,8 @@ void LayoutGrid::computeUsedBreadthOfGridTracks(GridTrackSizingDirection directi
                 if (i > 0 && span.resolvedInitialPosition.toInt() <= flexibleSizedTracksIndex[i - 1])
                     continue;
 
-                double itemNormalizedFlexBreadth = computeNormalizedFractionBreadth(tracks, span, direction, maxContentForChild(*gridItem, direction, sizingData.columnTracks));
-                normalizedFractionBreadth = std::max(normalizedFractionBreadth, itemNormalizedFlexBreadth);
+                double itemFlexFraction = findFlexFactorUnitSize(tracks, span, direction, maxContentForChild(*gridItem, direction, sizingData.columnTracks));
+                flexFraction = std::max(flexFraction, itemFlexFraction);
             }
         }
     }
@@ -484,7 +465,7 @@ void LayoutGrid::computeUsedBreadthOfGridTracks(GridTrackSizingDirection directi
     for (const auto& trackIndex : flexibleSizedTracksIndex) {
         GridTrackSize trackSize = gridTrackSize(direction, trackIndex);
 
-        LayoutUnit baseSize = std::max<LayoutUnit>(tracks[trackIndex].baseSize(), normalizedFractionBreadth * trackSize.maxTrackBreadth().flex());
+        LayoutUnit baseSize = std::max<LayoutUnit>(tracks[trackIndex].baseSize(), flexFraction * trackSize.maxTrackBreadth().flex());
         tracks[trackIndex].setBaseSize(baseSize);
         freeSpace -= baseSize;
     }
@@ -528,59 +509,58 @@ LayoutUnit LayoutGrid::computeUsedBreadthOfSpecifiedLength(GridTrackSizingDirect
     return valueForLength(trackLength, direction == ForColumns ? contentLogicalWidth() : std::max(LayoutUnit(), computeContentLogicalHeight(MainOrPreferredSize, style()->logicalHeight(), -1)));
 }
 
-static bool sortByGridNormalizedFlexValue(const GridTrackForNormalization& track1, const GridTrackForNormalization& track2)
-{
-    return track1.m_normalizedFlexValue < track2.m_normalizedFlexValue;
-}
-
-double LayoutGrid::computeNormalizedFractionBreadth(Vector<GridTrack>& tracks, const GridSpan& tracksSpan, GridTrackSizingDirection direction, LayoutUnit spaceToFill) const
+double LayoutGrid::computeFlexFactorUnitSize(const Vector<GridTrack>& tracks, GridTrackSizingDirection direction, double flexFactorSum, double leftOverSpace, const Vector<size_t, 8>& flexibleTracks, PassOwnPtr<TrackIndexSet> tracksToTreatAsInflexible) const

[svillar, 2015/09/23 14:57:15]

I don't think you need to use specify the initial capacity for the vector here.

Also perhaps the name should be flexibleTracksIndexes

 {
-    LayoutUnit allocatedSpace;
-    Vector<GridTrackForNormalization> tracksForNormalization;
-    for (const auto& resolvedPosition : tracksSpan) {
-        GridTrack& track = tracks[resolvedPosition.toInt()];
-        allocatedSpace += track.baseSize();
+    // Let flex factor sum be the sum of the flex factors of the flexible tracks. If this value
+    // is less than 1, set it to 1 instead.
+    double hypotheticalFactorUnitSize = flexFactorSum > 1 ? leftOverSpace / flexFactorSum : leftOverSpace;

[svillar, 2015/09/23 14:57:15]

Although perhaps slightly less efficient, I think we can remove the comment and
instead write this as follows:

double hypotheticalFactorUnitSize = leftOverSpace / std::max(1, leftOverSpace);

[jfernandez, 2015/09/24 08:16:36]

I think I'll change the comment so it explains why we don't want flex factor sum
less than 1.
I'm not sure abut this. I don't think the code is clearer and we are not only
computing the max, we also do an useless division by 1 operation. 

 
-        GridTrackSize trackSize = gridTrackSize(direction, resolvedPosition.toInt());
-        if (!trackSize.maxTrackBreadth().isFlex())
+    // product of the hypothetical "flex factor unit" and any flexible track's "flex factor" must be grater than such track's "base size".
+    OwnPtr<TrackIndexSet> additionalTacksToTreatAsInflexible = tracksToTreatAsInflexible;

[svillar, 2015/09/23 14:57:15]

nit: additionalTracks

[jfernandez, 2015/09/24 08:16:36]

Done.

+    bool validFlexFactorUnit = true;
+    for (auto index : flexibleTracks) {
+        if (additionalTacksToTreatAsInflexible && additionalTacksToTreatAsInflexible->contains(index))
             continue;
-
-        tracksForNormalization.append(GridTrackForNormalization(track, trackSize.maxTrackBreadth().flex()));
+        double baseSize = tracks[index].baseSize();
+        double flexFactor = gridTrackSize(direction, index).maxTrackBreadth().flex();
+        // treating all such tracks as inflexible.
+        if (hypotheticalFactorUnitSize * flexFactor < baseSize) {
+            leftOverSpace -= baseSize;
+            flexFactorSum -= flexFactor;
+            if (!additionalTacksToTreatAsInflexible)
+                additionalTacksToTreatAsInflexible = adoptPtr(new TrackIndexSet());
+            additionalTacksToTreatAsInflexible->add(index);
+            validFlexFactorUnit = false;
+        }
     }
+    return validFlexFactorUnit ? hypotheticalFactorUnitSize : computeFlexFactorUnitSize(tracks, direction, flexFactorSum, leftOverSpace, flexibleTracks, additionalTacksToTreatAsInflexible.release());

[svillar, 2015/09/23 14:57:15]

I know this is nitpicking but I'd prefer this to be in different lines.
Something like

if (!valid)
    return computeFlexFactor();

return hypothetical;

[jfernandez, 2015/09/24 08:16:36]

Done.

+}
 
-    // The function is not called if we don't have <flex> grid tracks
-    ASSERT(!tracksForNormalization.isEmpty());
-
-    std::sort(tracksForNormalization.begin(), tracksForNormalization.end(), sortByGridNormalizedFlexValue);
-
-    // These values work together: as we walk over our grid tracks, we increase fractionValueBasedOnGridItemsRatio
-    // to match a grid track's usedBreadth to <flex> ratio until the total fractions sized grid tracks wouldn't
-    // fit into availableLogicalSpaceIgnoringFractionTracks.
-    double accumulatedFractions = 0;
-    LayoutUnit fractionValueBasedOnGridItemsRatio = 0;
-    LayoutUnit availableLogicalSpaceIgnoringFractionTracks = spaceToFill - allocatedSpace;
-
-    for (const auto& track : tracksForNormalization) {
-        if (track.m_normalizedFlexValue > fractionValueBasedOnGridItemsRatio) {
-            // If the normalized flex value (we ordered |tracksForNormalization| by increasing normalized flex value)
-            // will make us overflow our container, then stop. We have the previous step's ratio is the best fit.
-            if (track.m_normalizedFlexValue * accumulatedFractions > availableLogicalSpaceIgnoringFractionTracks)
-                break;
+double LayoutGrid::findFlexFactorUnitSize(const Vector<GridTrack>& tracks, const GridSpan& tracksSpan, GridTrackSizingDirection direction, LayoutUnit spaceToFill) const
+{
+    if (spaceToFill <= 0)
+        return 0;
 
-            fractionValueBasedOnGridItemsRatio = track.m_normalizedFlexValue;
+    double flexFactorSum = 0;
+    double leftOverSpace = spaceToFill;

[svillar, 2015/09/23 14:57:15]

Why are you using doubles here? Although the flex factor is a double I think we
should still use LayoutUnit for all this size computations.

[jfernandez, 2015/09/24 08:16:36]

Well, some operators doesn't allow to mix LayoutUnit and double, like "<", ">",
"-=" and "+="; we use those in the recursive function computeFlexFactorUnitSize.
 Also, the main operation to compute the flex factor unit size is "/", which
will result a double value, not to mention the returning type is double as well.


If there is no important reason to use use LayoutUnit in this computation I
think converting the 2 LayoutUnit values we have as input arguments,
'spaceToFill' and 'baseSize', just once is the best approach.

+    Vector<size_t, 8> flexibleTracks;
+    for (const auto& resolvedPosition : tracksSpan) {
+        size_t trackIndex = resolvedPosition.toInt();
+        GridTrackSize trackSize = gridTrackSize(direction, trackIndex);
+        double baseSize = tracks[trackIndex].baseSize();
+        if (!trackSize.maxTrackBreadth().isFlex()) {
+            leftOverSpace -= baseSize;
+        } else {
+            double flexFactor = trackSize.maxTrackBreadth().flex();
+            flexibleTracks.append(trackIndex);
+            flexFactorSum += flexFactor;
         }
-
-        accumulatedFractions += track.m_flex;
-        // This item was processed so we re-add its used breadth to the available space to accurately count the remaining space.
-        availableLogicalSpaceIgnoringFractionTracks += track.m_track->baseSize();
     }
 
-    // Let flex factor sum be the sum of the flex factors of the flexible tracks. If this value
-    // is less than 1, set it to 1 instead.
-    if (accumulatedFractions < 1)
-        return availableLogicalSpaceIgnoringFractionTracks;
+    // The function is not called if we don't have <flex> grid tracks
+    ASSERT(!flexibleTracks.isEmpty());
 
-    return availableLogicalSpaceIgnoringFractionTracks / accumulatedFractions;
+    return computeFlexFactorUnitSize(tracks, direction, flexFactorSum, leftOverSpace, flexibleTracks);
 }
 
 bool LayoutGrid::hasDefiniteLogicalSize(GridTrackSizingDirection direction) const