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

Source/core/rendering/RenderGrid.cpp

Index: Source/core/rendering/RenderGrid.cpp
diff --git a/Source/core/rendering/RenderGrid.cpp b/Source/core/rendering/RenderGrid.cpp
index 351881084b582f24de06651ade28f7fd5595239d..eb005d41afd62284b8f3777a98a9b9a4c3b17b06 100644
--- a/Source/core/rendering/RenderGrid.cpp
+++ b/Source/core/rendering/RenderGrid.cpp
@@ -122,21 +122,55 @@ public:
         return 0;
     }
 
-    PassOwnPtr<GridCoordinate> nextEmptyGridArea()
+    bool areCellsEmpty(size_t spanningPositions)
     {
-        ASSERT(!m_grid.isEmpty());
+        // This adds a O(N^2) behavior that shouldn't be a big deal as we expect spanning areas to be small.
+        if (m_direction == ForColumns) {
+            for (size_t i = m_columnIndex; i < m_columnIndex + spanningPositions; ++i) {
+                const GridCell& children = m_grid[m_rowIndex][i];
+                if (!children.isEmpty())
+                    return false;
+            }
+        } else {
+            for (size_t i = m_rowIndex; i < m_rowIndex + spanningPositions; ++i) {
+                const GridCell& children = m_grid[i][m_columnIndex];
+                if (!children.isEmpty())
+                    return false;
+            }
+        }
 
-        size_t& varyingTrackIndex = (m_direction == ForColumns) ? m_rowIndex : m_columnIndex;
-        const size_t endOfVaryingTrackIndex = (m_direction == ForColumns) ? m_grid.size() : m_grid[0].size();
-        for (; varyingTrackIndex < endOfVaryingTrackIndex; ++varyingTrackIndex) {
-            const GridCell& children = m_grid[m_rowIndex][m_columnIndex];
-            if (children.isEmpty()) {
-                OwnPtr<GridCoordinate> result = adoptPtr(new GridCoordinate(GridSpan(m_rowIndex, m_rowIndex), GridSpan(m_columnIndex, m_columnIndex)));
-                // Advance the iterator to avoid an infinite loop where we would return the same grid area over and over.
-                ++varyingTrackIndex;
-                return result.release();
+        return true;
+    }
+
+    PassOwnPtr<GridCoordinate> nextEmptyGridArea(size_t spanningPositions)

[Julien - ping for review, 2014/04/04 00:10:16]

|spanningPositions| confuses me: that's because it's using a plural which I
thought meant that we handled 2 directions. How about renaming it to
positionSpanInDirectionOfIteration (or something equivalent but less verbose).

This previous confusion comes from the fact that to fully support the grid
specification we will need to account for the spans in *both* direction. That's
because you need to find a position that does not overlap any "occupied grid
cell".

I would be much more comfortable passing the 2 spans as part of this patch (to
iron out the API) even if you ignore about the one in the cross direction.

+    {
+        ASSERT(!m_grid.isEmpty());
+        ASSERT(spanningPositions >= 1);
+
+        if (m_direction == ForColumns) {
+            for (; m_rowIndex < m_grid.size(); ++m_rowIndex) {
+                if (areCellsEmpty(spanningPositions)) {
+                    GridSpan rowSpan = GridSpan(m_rowIndex, m_rowIndex);
+                    GridSpan columnSpan = GridSpan(m_columnIndex, m_columnIndex + spanningPositions - 1);
+                    OwnPtr<GridCoordinate> result = adoptPtr(new GridCoordinate(rowSpan, columnSpan));
+                    // Advance the iterator to avoid an infinite loop where we would return the same grid area over and over.
+                    ++m_rowIndex;
+                    return result.release();
+                }
+            }
+        } else {
+            for (; m_columnIndex < m_grid[0].size(); ++m_columnIndex) {
+                if (areCellsEmpty(spanningPositions)) {
+                    GridSpan rowSpan = GridSpan(m_rowIndex, m_rowIndex + spanningPositions - 1);
+                    GridSpan columnSpan = GridSpan(m_columnIndex, m_columnIndex);
+                    OwnPtr<GridCoordinate> result = adoptPtr(new GridCoordinate(rowSpan, columnSpan));
+                    // Advance the iterator to avoid an infinite loop where we would return the same grid area over and over.
+                    ++m_columnIndex;
+                    return result.release();
+                }
             }
         }
+
         return nullptr;
     }
 
@@ -819,15 +853,15 @@ void RenderGrid::placeSpecifiedMajorAxisItemsOnGrid(const Vector<RenderBox*>& au
     for (size_t i = 0; i < autoGridItems.size(); ++i) {
         OwnPtr<GridSpan> majorAxisPositions = resolveGridPositionsFromStyle(autoGridItems[i], autoPlacementMajorAxisDirection());
         GridIterator iterator(m_grid, autoPlacementMajorAxisDirection(), majorAxisPositions->initialPositionIndex);
-        if (OwnPtr<GridCoordinate> emptyGridArea = iterator.nextEmptyGridArea()) {
-            insertItemIntoGrid(autoGridItems[i], emptyGridArea->rows.initialPositionIndex, emptyGridArea->columns.initialPositionIndex);
+        if (OwnPtr<GridCoordinate> emptyGridArea = iterator.nextEmptyGridArea(majorAxisPositions->spanningPositions())) {
+            insertItemIntoGrid(autoGridItems[i], *emptyGridArea);
             continue;
         }
 
         growGrid(autoPlacementMinorAxisDirection());
-        OwnPtr<GridCoordinate> emptyGridArea = iterator.nextEmptyGridArea();
+        OwnPtr<GridCoordinate> emptyGridArea = iterator.nextEmptyGridArea(majorAxisPositions->spanningPositions());
         ASSERT(emptyGridArea);
-        insertItemIntoGrid(autoGridItems[i], emptyGridArea->rows.initialPositionIndex, emptyGridArea->columns.initialPositionIndex);
+        insertItemIntoGrid(autoGridItems[i], *emptyGridArea);
     }
 }
 
@@ -841,19 +875,18 @@ void RenderGrid::placeAutoMajorAxisItemOnGrid(RenderBox* gridItem)
 {
     OwnPtr<GridSpan> minorAxisPositions = resolveGridPositionsFromStyle(gridItem, autoPlacementMinorAxisDirection());
     ASSERT(!resolveGridPositionsFromStyle(gridItem, autoPlacementMajorAxisDirection()));
-    size_t minorAxisIndex = 0;
     if (minorAxisPositions) {
-        minorAxisIndex = minorAxisPositions->initialPositionIndex;
+        size_t minorAxisIndex = minorAxisPositions->initialPositionIndex;
         GridIterator iterator(m_grid, autoPlacementMinorAxisDirection(), minorAxisIndex);
-        if (OwnPtr<GridCoordinate> emptyGridArea = iterator.nextEmptyGridArea()) {
-            insertItemIntoGrid(gridItem, emptyGridArea->rows.initialPositionIndex, emptyGridArea->columns.initialPositionIndex);
+        if (OwnPtr<GridCoordinate> emptyGridArea = iterator.nextEmptyGridArea(minorAxisPositions->spanningPositions())) {
+            insertItemIntoGrid(gridItem, *emptyGridArea);
             return;
         }
     } else {
         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()) {
+            if (OwnPtr<GridCoordinate> emptyGridArea = iterator.nextEmptyGridArea(1)) {
                 insertItemIntoGrid(gridItem, emptyGridArea->rows.initialPositionIndex, emptyGridArea->columns.initialPositionIndex);
                 return;
             }
@@ -861,10 +894,11 @@ void RenderGrid::placeAutoMajorAxisItemOnGrid(RenderBox* gridItem)
     }
 
     // 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();
+    GridSpan minorAxisSpan = minorAxisPositions ? *minorAxisPositions : GridSpan(0, 0);
+    GridSpan columnSpan = (autoPlacementMajorAxisDirection() == ForColumns) ? GridSpan(m_grid[0].size(), m_grid[0].size()) : minorAxisSpan;
+    GridSpan rowSpan = (autoPlacementMajorAxisDirection() == ForColumns) ? minorAxisSpan : GridSpan(m_grid.size(), m_grid.size());
     growGrid(autoPlacementMajorAxisDirection());
-    insertItemIntoGrid(gridItem, rowIndex, columnIndex);
+    insertItemIntoGrid(gridItem, GridCoordinate(rowSpan, columnSpan));
 }
 
 GridTrackSizingDirection RenderGrid::autoPlacementMajorAxisDirection() const