[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..843772c1107c821fc1396dbabe9d1a92f3b8b5b0 100644
--- a/Source/core/rendering/RenderGrid.cpp
+++ b/Source/core/rendering/RenderGrid.cpp
@@ -122,16 +122,37 @@ public:
         return 0;
     }
 
-    PassOwnPtr<GridCoordinate> nextEmptyGridArea()
+    bool areCellsEmpty(size_t spanningAreas)

[Julien - ping for review, 2014/03/21 18:18:02]

Note that this introduces some O(N^2) behavior. It's not a big deal as we expect
spanning areas to be small but it may be worth a comment if we find this to be
an issue (there are definitely better data structure that could alleviate this).

Also would this work with spanning items as we don't insert them repeatedly into
m_grid? (what I mean is that grid-row: 1 / span 2; grid-column: 1; will be
inserted into m_grid[0][0] but not m_grid[1][0])

+    {
+        if (m_direction == ForColumns) {
+            for (size_t i = m_columnIndex; i < m_columnIndex + spanningAreas; ++i) {
+                const GridCell& children = m_grid[m_rowIndex][i];
+                if (!children.isEmpty())
+                    return false;
+            }
+        } else {
+            for (size_t i = m_rowIndex; i < m_rowIndex + spanningAreas; ++i) {
+                const GridCell& children = m_grid[i][m_columnIndex];
+                if (!children.isEmpty())
+                    return false;
+            }
+        }
+
+        return true;
+    }
+
+    PassOwnPtr<GridCoordinate> nextEmptyGridArea(size_t spanningAreas)

[Julien - ping for review, 2014/03/21 18:18:02]

It is weird to have the *same* |spanningAreas| for both directions when we know
they can be different. I would be way more comfortable with passing both even if
you only use one for now.

     {
         ASSERT(!m_grid.isEmpty());
+        ASSERT(spanningAreas >= 1);
 
         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)));
+            if (areCellsEmpty(spanningAreas)) {
+                GridSpan rowSpan = GridSpan(m_rowIndex, (m_direction == ForColumns) ? m_rowIndex : m_rowIndex + spanningAreas - 1);
+                GridSpan columnSpan = GridSpan(m_columnIndex, (m_direction == ForColumns) ? m_columnIndex + spanningAreas - 1 : m_columnIndex);
+                OwnPtr<GridCoordinate> result = adoptPtr(new GridCoordinate(rowSpan, columnSpan));

[Julien - ping for review, 2014/03/21 18:18:02]

I wonder if just having a single m_direction == ForColumns check would simplify
this code (it's a nit though).

                 // Advance the iterator to avoid an infinite loop where we would return the same grid area over and over.
                 ++varyingTrackIndex;
                 return result.release();
@@ -819,15 +840,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->finalPositionIndex - majorAxisPositions->initialPositionIndex + 1)) {

[Julien - ping for review, 2014/03/21 18:18:02]

How about adding a helper function to return the span from a GridSpan?

+            insertItemIntoGrid(autoGridItems[i], *emptyGridArea);
             continue;
         }
 
         growGrid(autoPlacementMinorAxisDirection());
-        OwnPtr<GridCoordinate> emptyGridArea = iterator.nextEmptyGridArea();
+        OwnPtr<GridCoordinate> emptyGridArea = iterator.nextEmptyGridArea(majorAxisPositions->finalPositionIndex - majorAxisPositions->initialPositionIndex + 1);
         ASSERT(emptyGridArea);
-        insertItemIntoGrid(autoGridItems[i], emptyGridArea->rows.initialPositionIndex, emptyGridArea->columns.initialPositionIndex);
+        insertItemIntoGrid(autoGridItems[i], *emptyGridArea);
     }
 }
 
@@ -841,19 +862,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->finalPositionIndex - minorAxisPositions->initialPositionIndex + 1)) {
+            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 +881,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