[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 104 matching lines @@
         for (; varyingTrackIndex < endOfVaryingTrackIndex; ++varyingTrackIndex) {
             const GridCell& children = m_grid[m_rowIndex][m_columnIndex];
             if (m_childIndex < children.size())
                 return children[m_childIndex++];
 
             m_childIndex = 0;
         }
         return 0;
     }
 
-    PassOwnPtr<GridCoordinate> nextEmptyGridArea()
+    bool areCellsEmpty(size_t spanningPositions)
+    {
+        // 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;
+            }
+        }
+
+        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);
 
-        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();
+        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;
     }
 
 private:
     const GridRepresentation& m_grid;
     GridTrackSizingDirection m_direction;
     size_t m_rowIndex;
     size_t m_columnIndex;
     size_t m_childIndex;
 };
@@ skipping 662 matching lines @@
     m_grid.grow(maximumRowIndex);
     for (size_t i = 0; i < m_grid.size(); ++i)
         m_grid[i].grow(maximumColumnIndex);
 }
 
 void RenderGrid::placeSpecifiedMajorAxisItemsOnGrid(const Vector<RenderBox*>& autoGridItems)
 {
     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);
     }
 }
 
 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 = 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;
             }
         }
     }
 
     // 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
 {
     GridAutoFlow flow = style()->gridAutoFlow();
     ASSERT(flow != AutoFlowNone);
     return (flow == AutoFlowColumn) ? ForColumns : ForRows;
 }
 
 GridTrackSizingDirection RenderGrid::autoPlacementMinorAxisDirection() const
@@ skipping 504 matching lines @@
     if (isOutOfFlowPositioned())
         return "RenderGrid (positioned)";
     if (isAnonymous())
         return "RenderGrid (generated)";
     if (isRelPositioned())
         return "RenderGrid (relative positioned)";
     return "RenderGrid";
 }
 
 } // namespace WebCore