[CSS Grid Layout] Support span in auto-placement algorithm

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 717 matching lines @@
 void RenderGrid::insertItemIntoGrid(RenderBox* child, const GridCoordinate& coordinate)
 {
     for (GridResolvedPosition row = coordinate.rows.resolvedInitialPosition; row <= coordinate.rows.resolvedFinalPosition; ++row) {
         for (GridResolvedPosition column = coordinate.columns.resolvedInitialPosition; column <= coordinate.columns.resolvedFinalPosition; ++column)
             m_grid[row.toInt()][column.toInt()].append(child);
     }
 
     m_gridItemCoordinate.set(child, coordinate);
 }
 
-void RenderGrid::insertItemIntoGrid(RenderBox* child, const GridResolvedPosition& rowTrack, const GridResolvedPosition& columnTrack)
-{
-    const GridSpan& rowSpan = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(*child, ForRows, rowTrack);
-    const GridSpan& columnSpan = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(*child, ForColumns, columnTrack);
-    insertItemIntoGrid(child, GridCoordinate(rowSpan, columnSpan));
-}
-
 void RenderGrid::placeItemsOnGrid()
 {
     if (!gridIsDirty())
         return;
 
     ASSERT(m_gridItemCoordinate.isEmpty());
 
     populateExplicitGridAndOrderIterator();
 
     // We clear the dirty bit here as the grid sizes have been updated, this means
@@ skipping 42 matching lines @@
     size_t maximumRowIndex = std::max<size_t>(1, GridResolvedPosition::explicitGridRowCount(*style()));
     size_t maximumColumnIndex = std::max<size_t>(1, GridResolvedPosition::explicitGridColumnCount(*style()));
 
     for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
         populator.collectChild(child);
 
         // This function bypasses the cache (cachedGridCoordinate()) as it is used to build it.
         OwnPtr<GridSpan> rowPositions = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *child, ForRows);
         OwnPtr<GridSpan> columnPositions = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *child, ForColumns);
 
-        // |positions| is 0 if we need to run the auto-placement algorithm. Our estimation ignores
-        // this case as the auto-placement algorithm will grow the grid as needed.
-        if (rowPositions)
-            maximumRowIndex = std::max<size_t>(maximumRowIndex, rowPositions->resolvedFinalPosition.toInt() + 1);
-        if (columnPositions)
-            maximumColumnIndex = std::max<size_t>(maximumColumnIndex, columnPositions->resolvedFinalPosition.toInt() + 1);
+        // |positions| is 0 if we need to run the auto-placement algorithm.
+        if (rowPositions) {
+            maximumRowIndex = std::max(maximumRowIndex, rowPositions->resolvedFinalPosition.toInt() + 1);
+        } else if (autoPlacementMinorAxisDirection() == ForRows) {

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

It seems to me that we need to make the initial grid as tall as the tallest
known span, regardless of the auto-placement direction.

We don't strictly have to do this resizing and could totally resize the grid as
needed, which I think would simplify the code as we *have* to handle growing the
grid several rows / columns anyway.

+            // Grow the grid for items with a definite row span, getting the largest such span.
+            OwnPtr<GridSpan> positions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(*style(), *child, ForRows, GridResolvedPosition(0));
+            maximumRowIndex = std::max(maximumRowIndex, positions->resolvedFinalPosition.toInt() + 1);
+        }
+
+        if (columnPositions) {
+            maximumColumnIndex = std::max(maximumColumnIndex, columnPositions->resolvedFinalPosition.toInt() + 1);
+        } else if (autoPlacementMinorAxisDirection() == ForColumns) {
+            // Grow the grid for items with a definite column span, getting the largest such span.
+            OwnPtr<GridSpan> positions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(*style(), *child, ForColumns, GridResolvedPosition(0));
+            maximumColumnIndex = std::max(maximumColumnIndex, positions->resolvedFinalPosition.toInt() + 1);
+        }
     }
 
     m_grid.grow(maximumRowIndex);
     for (size_t i = 0; i < m_grid.size(); ++i)
         m_grid[i].grow(maximumColumnIndex);
 }
 
+bool RenderGrid::checkEmptyCells(const GridCoordinate& coordinate) const
+{
+    // Ignore cells outside current grid as we will grow it later if needed.
+    size_t maxRows = std::min(coordinate.rows.resolvedFinalPosition.toInt() + 1, gridRowCount());
+    size_t maxColumns = std::min(coordinate.columns.resolvedFinalPosition.toInt() + 1, gridColumnCount());
+
+    // This adds a O(N^2) behavior that shouldn't be a big deal as we expect spanning areas to be small.
+    for (size_t row = coordinate.rows.resolvedInitialPosition.toInt(); row < maxRows; ++row) {
+        for (size_t column = coordinate.columns.resolvedInitialPosition.toInt(); column < maxColumns; ++column) {
+            const GridCell& children = m_grid[row][column];
+            if (!children.isEmpty())
+                return false;
+        }
+    }
+
+    return true;
+}
+
+PassOwnPtr<GridCoordinate> RenderGrid::implicitEmptyGridAreaSpecifiedPositions(const RenderBox* gridItem, GridTrackSizingDirection specifiedDirection, const GridSpan& specifiedPositions) const

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

What is an implicit empty grid area?

There are 2 patterns when trying to find an empty grid area:
- either we have a fixed axis, in which case we must find a position, if needed
past the end of the grid.
- try placing the grid item, in which case we just return NULL (no position) at
the end.

I think we should try to make this code more readable by making the 2 patterns
more obvious. For example, you could have a emptyGridAreaAtSpecifiedPosition()
(that can't return NULL) vs tryFindingEmptyGridAreaAtSpecifiedPosition(). The
names can be improved.

+{
+    GridTrackSizingDirection crossDirection = specifiedDirection == ForColumns ? ForRows : ForColumns;
+    const size_t endOfCrossDirection = crossDirection == ForColumns ? gridColumnCount() : gridRowCount();
+    OwnPtr<GridSpan> crossDirectionPositions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(*style(), *gridItem, crossDirection, GridResolvedPosition(endOfCrossDirection));
+    return adoptPtr(new GridCoordinate(specifiedDirection == ForColumns ? *crossDirectionPositions : specifiedPositions, specifiedDirection == ForColumns ? specifiedPositions : *crossDirectionPositions));
+}
+
+PassOwnPtr<GridCoordinate> RenderGrid::emptyGridAreaSpecifiedPositions(const RenderBox* gridItem, GridTrackSizingDirection specifiedDirection, const GridSpan& specifiedPositions) const
+{
+    GridTrackSizingDirection crossDirection = specifiedDirection == ForColumns ? ForRows : ForColumns;
+
+    GridIterator iterator(m_grid, specifiedDirection, specifiedPositions.resolvedInitialPosition.toInt());
+    OwnPtr<GridCoordinate> emptyGridArea;
+    for (emptyGridArea = iterator.nextEmptyGridArea(); emptyGridArea; emptyGridArea = iterator.nextEmptyGridArea()) {
+        GridResolvedPosition crossDirectionInitialPositionIndex = crossDirection == ForColumns ? emptyGridArea->columns.resolvedInitialPosition : emptyGridArea->rows.resolvedInitialPosition;
+        OwnPtr<GridSpan> crossDirectionPositions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(*style(), *gridItem, crossDirection, crossDirectionInitialPositionIndex);

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

I think we should explain why we need to resolve the position over and over.
This is because span 2 'c' can have a different resolution based on your
position.

Also only some cases would have a varying span value (explicit grid line and
integer don't need that).

+
+        emptyGridArea->rows = specifiedDirection == ForColumns ? *crossDirectionPositions : specifiedPositions;
+        emptyGridArea->columns = specifiedDirection == ForColumns ? specifiedPositions : *crossDirectionPositions;
+        if (checkEmptyCells(*emptyGridArea))
+            break;
+    }
+
+    return emptyGridArea.release();
+}
+
+void RenderGrid::insertItemIntoGridGrowingIfNeeded(RenderBox* gridItem, const GridCoordinate& coordinate, GridTrackSizingDirection growingDirection)

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

I don't like this split for several reasons:
* insertItemIntoGrid() has only one caller - this function - which means that we
don't really need the difference.
* fundamentally, growing the grid is an implementation detail that shouldn't be
exposed to the caller (who shouldn't care really).
* Also we don't want to allow callers to call insertItemIntoGrid as you could
potentially write past outside the grid (using a defense-in-depth pattern is
great).

+{
+    GridResolvedPosition growingDirectionFinalPositionIndex = growingDirection == ForColumns ? coordinate.columns.resolvedFinalPosition : coordinate.rows.resolvedFinalPosition;
+    const size_t endOfGrowingDirection = growingDirection == ForColumns ? gridColumnCount() : gridRowCount();
+    if (growingDirectionFinalPositionIndex.toInt() >= endOfGrowingDirection)
+        growGrid(growingDirection, growingDirectionFinalPositionIndex.toInt());
+    insertItemIntoGrid(gridItem, coordinate);
+}
+
 void RenderGrid::placeSpecifiedMajorAxisItemsOnGrid(const Vector<RenderBox*>& autoGridItems)
 {
     for (size_t i = 0; i < autoGridItems.size(); ++i) {
         OwnPtr<GridSpan> majorAxisPositions = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *autoGridItems[i], autoPlacementMajorAxisDirection());
-        GridIterator iterator(m_grid, autoPlacementMajorAxisDirection(), majorAxisPositions->resolvedInitialPosition.toInt());
-        if (OwnPtr<GridCoordinate> emptyGridArea = iterator.nextEmptyGridArea()) {
-            insertItemIntoGrid(autoGridItems[i], emptyGridArea->rows.resolvedInitialPosition, emptyGridArea->columns.resolvedInitialPosition);
-            continue;
-        }
-
-        growGrid(autoPlacementMinorAxisDirection(), autoPlacementMinorAxisDirection() == ForColumns ? m_grid[0].size() : m_grid.size());
-        OwnPtr<GridCoordinate> emptyGridArea = iterator.nextEmptyGridArea();
-        ASSERT(emptyGridArea);
-        insertItemIntoGrid(autoGridItems[i], emptyGridArea->rows.resolvedInitialPosition, emptyGridArea->columns.resolvedInitialPosition);
+        OwnPtr<GridCoordinate> emptyGridArea = emptyGridAreaSpecifiedPositions(autoGridItems[i], autoPlacementMajorAxisDirection(), *majorAxisPositions);
+        if (!emptyGridArea)
+            emptyGridArea = implicitEmptyGridAreaSpecifiedPositions(autoGridItems[i], autoPlacementMajorAxisDirection(), *majorAxisPositions);
+        insertItemIntoGridGrowingIfNeeded(autoGridItems[i], *emptyGridArea, autoPlacementMinorAxisDirection());
     }
 }
 
 void RenderGrid::placeAutoMajorAxisItemsOnGrid(const Vector<RenderBox*>& autoGridItems)
 {
     for (size_t i = 0; i < autoGridItems.size(); ++i)
         placeAutoMajorAxisItemOnGrid(autoGridItems[i]);
 }
 
 void RenderGrid::placeAutoMajorAxisItemOnGrid(RenderBox* gridItem)
 {
     OwnPtr<GridSpan> minorAxisPositions = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *gridItem, autoPlacementMinorAxisDirection());
     ASSERT(!GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *gridItem, autoPlacementMajorAxisDirection()));
-    size_t minorAxisIndex = 0;
     if (minorAxisPositions) {
-        minorAxisIndex = minorAxisPositions->resolvedInitialPosition.toInt();
-        GridIterator iterator(m_grid, autoPlacementMinorAxisDirection(), minorAxisIndex);
-        if (OwnPtr<GridCoordinate> emptyGridArea = iterator.nextEmptyGridArea()) {
-            insertItemIntoGrid(gridItem, emptyGridArea->rows.resolvedInitialPosition, emptyGridArea->columns.resolvedInitialPosition);
-            return;
-        }
+        OwnPtr<GridCoordinate> emptyGridArea = emptyGridAreaSpecifiedPositions(gridItem, autoPlacementMinorAxisDirection(), *minorAxisPositions);
+        if (!emptyGridArea)
+            emptyGridArea = implicitEmptyGridAreaSpecifiedPositions(gridItem, autoPlacementMinorAxisDirection(), *minorAxisPositions);
+        insertItemIntoGridGrowingIfNeeded(gridItem, *emptyGridArea, autoPlacementMajorAxisDirection());
     } else {
+        OwnPtr<GridCoordinate> emptyGridArea;
+
         const size_t endOfMajorAxis = (autoPlacementMajorAxisDirection() == ForColumns) ? gridColumnCount() : gridRowCount();
         for (size_t majorAxisIndex = 0; majorAxisIndex < endOfMajorAxis; ++majorAxisIndex) {
-            GridIterator iterator(m_grid, autoPlacementMajorAxisDirection(), majorAxisIndex);
-            if (OwnPtr<GridCoordinate> emptyGridArea = iterator.nextEmptyGridArea()) {
-                insertItemIntoGrid(gridItem, emptyGridArea->rows.resolvedInitialPosition, emptyGridArea->columns.resolvedInitialPosition);
-                return;
+            OwnPtr<GridSpan> majorAxisPositions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(*style(), *gridItem, autoPlacementMajorAxisDirection(), majorAxisIndex);
+            emptyGridArea = emptyGridAreaSpecifiedPositions(gridItem, autoPlacementMajorAxisDirection(), *majorAxisPositions);
+
+            if (emptyGridArea) {
+                // Check that it fits in the minor axis direction, as we shouldn't grow in that direction here (it was already managed in populateExplicitGridAndOrderIterator()).
+                GridResolvedPosition minorAxisFinalPositionIndex = autoPlacementMinorAxisDirection() == ForColumns ? emptyGridArea->columns.resolvedFinalPosition : emptyGridArea->rows.resolvedFinalPosition;
+                const size_t endOfMinorAxis = autoPlacementMinorAxisDirection() == ForColumns ? gridColumnCount() : gridRowCount();
+                if (minorAxisFinalPositionIndex.toInt() < endOfMinorAxis)
+                    break;
             }
         }
+
+        if (!emptyGridArea) {
+            OwnPtr<GridSpan> majorAxisPositions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(*style(), *gridItem, autoPlacementMajorAxisDirection(), GridResolvedPosition(endOfMajorAxis));
+            OwnPtr<GridSpan> minorAxisPositions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(*style(), *gridItem, autoPlacementMinorAxisDirection(), GridResolvedPosition(0));
+            emptyGridArea = adoptPtr(new GridCoordinate(autoPlacementMajorAxisDirection() == ForColumns ? *minorAxisPositions : *majorAxisPositions, autoPlacementMajorAxisDirection() == ForColumns ? *majorAxisPositions : *minorAxisPositions));
+        }
+
+        insertItemIntoGridGrowingIfNeeded(gridItem, *emptyGridArea, autoPlacementMajorAxisDirection());
     }
-
-    // We didn't find an empty grid area so we need to create an extra major axis line and insert our gridItem in it.
-    const size_t columnIndex = (autoPlacementMajorAxisDirection() == ForColumns) ? m_grid[0].size() : minorAxisIndex;
-    const size_t rowIndex = (autoPlacementMajorAxisDirection() == ForColumns) ? minorAxisIndex : m_grid.size();
-    growGrid(autoPlacementMajorAxisDirection(), autoPlacementMajorAxisDirection() == ForColumns ? m_grid[0].size() : m_grid.size());
-    insertItemIntoGrid(gridItem, rowIndex, columnIndex);
 }
 
 GridTrackSizingDirection RenderGrid::autoPlacementMajorAxisDirection() const
 {
     GridAutoFlow flow = style()->gridAutoFlow();
     ASSERT(flow != AutoFlowNone);
     return (flow == AutoFlowColumn) ? ForColumns : ForRows;
 }
 
 GridTrackSizingDirection RenderGrid::autoPlacementMinorAxisDirection() const
@@ skipping 341 matching lines @@
     if (isOutOfFlowPositioned())
         return "RenderGrid (positioned)";
     if (isAnonymous())
         return "RenderGrid (generated)";
     if (isRelPositioned())
         return "RenderGrid (relative positioned)";
     return "RenderGrid";
 }
 
 } // namespace WebCore