[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 186 matching lines @@
     }
 
     RenderBox* newChildBox = toRenderBox(newChild);
     OwnPtr<GridSpan> rowPositions = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *newChildBox, ForRows);
     OwnPtr<GridSpan> columnPositions = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *newChildBox, ForColumns);
     if (!rowPositions || !columnPositions) {
         // The new child requires the auto-placement algorithm to run so we need to recompute the grid fully.
         dirtyGrid();
         return;
     } else {
-        // Ensure that the grid is big enough to contain new grid item.
-        if (gridRowCount() <= rowPositions->resolvedFinalPosition.toInt())
-            growGrid(ForRows, rowPositions->resolvedFinalPosition.toInt());
-        if (gridColumnCount() <= columnPositions->resolvedFinalPosition.toInt())
-            growGrid(ForColumns, columnPositions->resolvedFinalPosition.toInt());
-
         insertItemIntoGrid(newChildBox, GridCoordinate(*rowPositions, *columnPositions));
         addChildToIndexesMap(newChildBox);
     }
 }
 
 void RenderGrid::addChildToIndexesMap(RenderBox* child)
 {
     ASSERT(!m_gridItemsIndexesMap.contains(child));
     RenderBox* sibling = child->nextSiblingBox();
     bool lastSibling = !sibling;
@@ skipping 521 matching lines @@
         ASSERT(maximumPositionIndex >= gridRowCount());
         const size_t oldRowSize = gridRowCount();
         m_grid.grow(maximumPositionIndex + 1);
         for (size_t row = oldRowSize; row < gridRowCount(); ++row)
             m_grid[row].grow(gridColumnCount());
     }
 }
 
 void RenderGrid::insertItemIntoGrid(RenderBox* child, const GridCoordinate& coordinate)
 {
+    // Ensure that the grid is big enough to contain new grid item.
+    if (gridRowCount() <= coordinate.rows.resolvedFinalPosition.toInt())
+        growGrid(ForRows, coordinate.rows.resolvedFinalPosition.toInt());
+    if (gridColumnCount() <= coordinate.columns.resolvedFinalPosition.toInt())
+        growGrid(ForColumns, coordinate.columns.resolvedFinalPosition.toInt());

[Julien - ping for review, 2014/05/29 21:07:00]

I think we should just unconditionally ensure enough grid rows / columns and
have an API to grow both directions at once. That can be done in a follow-up
change.

+
     for (GridSpan::iterator row = coordinate.rows.begin(); row != coordinate.rows.end(); ++row) {
         for (GridSpan::iterator column = coordinate.columns.begin(); column != coordinate.columns.end(); ++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 45 matching lines @@
     ASSERT(m_gridItemsIndexesMap.isEmpty());
     size_t childIndex = 0;
     for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
         populator.collectChild(child);
         m_gridItemsIndexesMap.set(child, childIndex++);
 
         // 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)
+        // |positions| is 0 if we need to run the auto-placement algorithm.
+        if (rowPositions) {
             maximumRowIndex = std::max<size_t>(maximumRowIndex, rowPositions->resolvedFinalPosition.next().toInt());
-        if (columnPositions)
+        } else if (autoPlacementMinorAxisDirection() == ForRows) {
+            // 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<size_t>(maximumRowIndex, positions->resolvedFinalPosition.next().toInt());
+        }
+
+        if (columnPositions) {
             maximumColumnIndex = std::max<size_t>(maximumColumnIndex, columnPositions->resolvedFinalPosition.next().toInt());
+        } else if (autoPlacementMinorAxisDirection() == ForColumns) {

[Julien - ping for review, 2014/05/29 21:07:00]

I still don't agree with being conditional here.

If you have a 3x3 items, your grid should be *at least* 3x3 regardless of where
we place the item. Your example does show that it can be bigger, which is
perfectly fine. Checking for the auto-placement axis is artificial, shouldn't
change the final grid size and prevent us from pre-allocating the grid to a
minimum sensible size.

(btw, please comment using the UI instead of replying as it breaks rietveld so I
can't easily reply to your comments)

+            // 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<size_t>(maximumColumnIndex, positions->resolvedFinalPosition.next().toInt());
+        }
     }
 
     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.next().toInt(), gridRowCount());
+    size_t maxColumns = std::min(coordinate.columns.resolvedFinalPosition.next().toInt(), 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::createEmptyGridAreaAtSpecifiedPositionsOutsideGrid(const RenderBox* gridItem, GridTrackSizingDirection specifiedDirection, const GridSpan& specifiedPositions) const
+{
+    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::findEmptyGridAreaAtSpecifiedPositionsInsideGrid(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);
+
+        emptyGridArea->rows = specifiedDirection == ForColumns ? *crossDirectionPositions : specifiedPositions;
+        emptyGridArea->columns = specifiedDirection == ForColumns ? specifiedPositions : *crossDirectionPositions;
+        if (checkEmptyCells(*emptyGridArea))
+            break;
+    }
+
+    return emptyGridArea.release();
+}
+
 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 ? gridColumnCount() : gridRowCount());
-        OwnPtr<GridCoordinate> emptyGridArea = iterator.nextEmptyGridArea();
-        ASSERT(emptyGridArea);
-        insertItemIntoGrid(autoGridItems[i], emptyGridArea->rows.resolvedInitialPosition, emptyGridArea->columns.resolvedInitialPosition);
+        OwnPtr<GridCoordinate> emptyGridArea = findEmptyGridAreaAtSpecifiedPositionsInsideGrid(autoGridItems[i], autoPlacementMajorAxisDirection(), *majorAxisPositions);
+        if (!emptyGridArea)
+            emptyGridArea = createEmptyGridAreaAtSpecifiedPositionsOutsideGrid(autoGridItems[i], autoPlacementMajorAxisDirection(), *majorAxisPositions);
+        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 = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *gridItem, autoPlacementMinorAxisDirection());
     ASSERT(!GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *gridItem, autoPlacementMajorAxisDirection()));
-    size_t minorAxisIndex = 0;
+    OwnPtr<GridCoordinate> emptyGridArea;
     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;
-        }
+        emptyGridArea = findEmptyGridAreaAtSpecifiedPositionsInsideGrid(gridItem, autoPlacementMinorAxisDirection(), *minorAxisPositions);
+        if (!emptyGridArea)
+            emptyGridArea = createEmptyGridAreaAtSpecifiedPositionsOutsideGrid(gridItem, autoPlacementMinorAxisDirection(), *minorAxisPositions);
     } 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()) {
-                insertItemIntoGrid(gridItem, emptyGridArea->rows.resolvedInitialPosition, emptyGridArea->columns.resolvedInitialPosition);
-                return;
+            // We need to resolve the position for every different index as the number of cells might vary depending on it.
+            // This will happen when we have "span <custom-indent>", which has a different resolution based on the position.
+            OwnPtr<GridSpan> majorAxisPositions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(*style(), *gridItem, autoPlacementMajorAxisDirection(), majorAxisIndex);
+            emptyGridArea = findEmptyGridAreaAtSpecifiedPositionsInsideGrid(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> minorAxisPositions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(*style(), *gridItem, autoPlacementMinorAxisDirection(), GridResolvedPosition(0));
+            emptyGridArea = createEmptyGridAreaAtSpecifiedPositionsOutsideGrid(gridItem, autoPlacementMinorAxisDirection(), *minorAxisPositions);
+        }
     }
 
-    // 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) ? gridColumnCount() : minorAxisIndex;
-    const size_t rowIndex = (autoPlacementMajorAxisDirection() == ForColumns) ? minorAxisIndex : gridRowCount();
-    growGrid(autoPlacementMajorAxisDirection(), autoPlacementMajorAxisDirection() == ForColumns ? gridColumnCount() : gridRowCount());
-    insertItemIntoGrid(gridItem, rowIndex, columnIndex);
+    insertItemIntoGrid(gridItem, *emptyGridArea);
 }
 
 GridTrackSizingDirection RenderGrid::autoPlacementMajorAxisDirection() const
 {
     GridAutoFlow flow = style()->gridAutoFlow();
     ASSERT(flow != AutoFlowNone);
     return (flow == AutoFlowColumn) ? ForColumns : ForRows;
 }
 
 GridTrackSizingDirection RenderGrid::autoPlacementMinorAxisDirection() const
@@ skipping 304 matching lines @@
     if (isOutOfFlowPositioned())
         return "RenderGrid (positioned)";
     if (isAnonymous())
         return "RenderGrid (generated)";
     if (isRelPositioned())
         return "RenderGrid (relative positioned)";
     return "RenderGrid";
 }
 
 } // namespace WebCore