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

Source/core/layout/LayoutGrid.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 124 matching lines @@
         , distributionOffset(distribution)
     {
     }
 
     bool isValid() { return positionOffset >= 0 && distributionOffset >= 0; }
 
     LayoutUnit positionOffset = -1;
     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,
 };
 
 class LayoutGrid::GridIterator {
     WTF_MAKE_NONCOPYABLE(GridIterator);
 public:
     // |direction| is the direction that is fixed to |fixedTrackIndex| so e.g
     // GridIterator(m_grid, ForColumns, 1) will walk over the rows of the 2nd column.
@@ skipping 212 matching lines @@
     LayoutUnit scrollbarWidth = intrinsicScrollbarLogicalWidth();
     minLogicalWidth += scrollbarWidth;
     maxLogicalWidth += scrollbarWidth;
 }
 
 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;
     Vector<GridTrack>& tracks = (direction == ForColumns) ? sizingData.columnTracks : sizingData.rowTracks;
     Vector<size_t> flexibleSizedTracksIndex;
     sizingData.contentSizedTracksIndex.shrink(0);
 
     // 1. Initialize per Grid track variables.
     for (size_t i = 0; i < tracks.size(); ++i) {
         GridTrack& track = tracks[i];
@@ skipping 40 matching lines @@
             track->setBaseSize(track->plannedSize());
     } 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;
+    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]);
             while (LayoutBox* gridItem = iterator.nextGridItem()) {
                 const GridCoordinate coordinate = cachedGridCoordinate(*gridItem);
                 const GridSpan span = (direction == ForColumns) ? coordinate.columns : coordinate.rows;
 
                 // Do not include already processed items.
                 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);
             }
         }
     }
 
     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;
     }
 
     // FIXME: Should ASSERT flexible tracks exhaust the freeSpace ? (see issue 739613002).
 }
 
 LayoutUnit LayoutGrid::computeUsedBreadthOfMinLength(GridTrackSizingDirection direction, const GridLength& gridLength) const
 {
     if (gridLength.isFlex())
@@ skipping 23 matching lines @@
     return infinity;
 }
 
 LayoutUnit LayoutGrid::computeUsedBreadthOfSpecifiedLength(GridTrackSizingDirection direction, const Length& trackLength) const
 {
     ASSERT(trackLength.isSpecified());
     // FIXME: The -1 here should be replaced by whatever the intrinsic height of the grid is.
     return valueForLength(trackLength, direction == ForColumns ? contentLogicalWidth() : std::max(LayoutUnit(), computeContentLogicalHeight(MainOrPreferredSize, style()->logicalHeight(), -1)));
 }
 
-static bool sortByGridNormalizedFlexValue(const GridTrackForNormalization& track1, const GridTrackForNormalization& track2)
+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

 {
-    return track1.m_normalizedFlexValue < track2.m_normalizedFlexValue;
+    // 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. 

+
+    // 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;
+        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.

 }
 
-double LayoutGrid::computeNormalizedFractionBreadth(Vector<GridTrack>& tracks, const GridSpan& tracksSpan, GridTrackSizingDirection direction, LayoutUnit spaceToFill) const
+double LayoutGrid::findFlexFactorUnitSize(const Vector<GridTrack>& tracks, const GridSpan& tracksSpan, GridTrackSizingDirection direction, LayoutUnit spaceToFill) const
 {
-    LayoutUnit allocatedSpace;
-    Vector<GridTrackForNormalization> tracksForNormalization;
+    if (spaceToFill <= 0)
+        return 0;
+
+    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) {
-        GridTrack& track = tracks[resolvedPosition.toInt()];
-        allocatedSpace += track.baseSize();
-
-        GridTrackSize trackSize = gridTrackSize(direction, resolvedPosition.toInt());
-        if (!trackSize.maxTrackBreadth().isFlex())
-            continue;
-
-        tracksForNormalization.append(GridTrackForNormalization(track, trackSize.maxTrackBreadth().flex()));
+        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;
+        }
     }
 
     // The function is not called if we don't have <flex> grid tracks
-    ASSERT(!tracksForNormalization.isEmpty());
+    ASSERT(!flexibleTracks.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;
-
-            fractionValueBasedOnGridItemsRatio = track.m_normalizedFlexValue;
-        }
-
-        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;
-
-    return availableLogicalSpaceIgnoringFractionTracks / accumulatedFractions;
+    return computeFlexFactorUnitSize(tracks, direction, flexFactorSum, leftOverSpace, flexibleTracks);
 }
 
 bool LayoutGrid::hasDefiniteLogicalSize(GridTrackSizingDirection direction) const
 {
     return (direction == ForRows) ? hasDefiniteLogicalHeight() : hasDefiniteLogicalWidth();
 }
 
 GridTrackSize LayoutGrid::gridTrackSize(GridTrackSizingDirection direction, size_t i) const
 {
     bool isForColumns = direction == ForColumns;
@@ skipping 1332 matching lines @@
 
     return LayoutPoint(rowAxisOffset, columnAxisOffsetForChild(child));
 }
 
 void LayoutGrid::paintChildren(const PaintInfo& paintInfo, const LayoutPoint& paintOffset)
 {
     GridPainter(*this).paintChildren(paintInfo, paintOffset);
 }
 
 } // namespace blink