[CSS Grid Layout] Support "sparse" in auto-placed items locked to a row/column

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 960 matching lines @@
 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();
     GridSpan crossDirectionPositions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(*style(), gridItem, crossDirection, GridResolvedPosition(endOfCrossDirection));
     return adoptPtr(new GridCoordinate(specifiedDirection == ForColumns ? crossDirectionPositions : specifiedPositions, specifiedDirection == ForColumns ? specifiedPositions : crossDirectionPositions));
 }
 
 void RenderGrid::placeSpecifiedMajorAxisItemsOnGrid(const Vector<RenderBox*>& autoGridItems)
 {
+    GridTrackSizingDirection direction = autoPlacementMajorAxisDirection();
+    bool isGridAutoFlowDense = style()->isGridAutoFlowAlgorithmDense();
+
+    Vector<size_t> minorAxisCursors;

[Julien - ping for review, 2015/02/23 16:15:16]

I would love a comment about this vector to explain what it's doing.

[Manuel Rego, 2015/02/23 22:22:00]

I agree. But finally I'm changing the Vector for a HashMap as
suggested by @svillar. Of course, adding a comment to explain the map. :-)

Using the HashMap has some small benefits:
* The code is clearer (as you don't need to initialize the values).
* You won't need to reserve memory for all the tracks if you just have a few
  items with this auto-placement.
* Testing it in a 200x200 grid, it's slightly faster than the Vector.

+    if (!isGridAutoFlowDense)
+        minorAxisCursors.grow(direction == ForColumns ? gridColumnCount() : gridRowCount());
+
     for (const auto& autoGridItem : autoGridItems) {
         OwnPtr<GridSpan> majorAxisPositions = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *autoGridItem, autoPlacementMajorAxisDirection());
         GridSpan minorAxisPositions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(*style(), *autoGridItem, autoPlacementMinorAxisDirection(), GridResolvedPosition(0));
 
-        GridIterator iterator(m_grid, autoPlacementMajorAxisDirection(), majorAxisPositions->resolvedInitialPosition.toInt());
+        GridIterator iterator(m_grid, autoPlacementMajorAxisDirection(), majorAxisPositions->resolvedInitialPosition.toInt(), isGridAutoFlowDense ? 0 : minorAxisCursors[majorAxisPositions->resolvedInitialPosition.toInt()]);

[Julien - ping for review, 2015/02/18 21:08:40]

That's relying on the default value in minorAxisCursor (we set it below), which
is weird and unintuitive.

I would have assumed that we would just reuse the position from the previous run
and get the algorithm straight. Why do we need all this complexity?

[Manuel Rego, 2015/02/18 21:23:10]

We can use minorAxisCursors.fill(0) before to make it clear that it's 
the initial value.
We cannot do that, as it's not guaranteed the order of the elements.

For example:
  <div style="grid-row: 1;">item 1</div>
  <div style="grid-row: 2;">item 2</div>
  <div style="grid-row: 1;">item 3</div>

Imagine that "item 1" is placed in the 4th column (due to other fixed 
elements before) and "item 2" in the 2nd column.
Then, if for "item 3" we use the value from the previous run, we'll be 
trying to place it in 3rd column first, which is wrong as we should be
starting in 5th column.

We could sort the elements by row, and process them per row, but then 
we'll be breaking the order-modified document order.

[Julien - ping for review, 2015/02/23 16:15:16]

minorAxisCursors.fill(0) makes the code more clear and more readable but it's
some extra unneeded work. I don't have an opinion on whether we should do it or
just put a comment.
I see the issue and that we're processing step 1. of the auto placement
algorithm, not the general case.

+
         OwnPtr<GridCoordinate> emptyGridArea = iterator.nextEmptyGridArea(majorAxisPositions->integerSpan(), minorAxisPositions.integerSpan());
         if (!emptyGridArea)
             emptyGridArea = createEmptyGridAreaAtSpecifiedPositionsOutsideGrid(*autoGridItem, autoPlacementMajorAxisDirection(), *majorAxisPositions);
         insertItemIntoGrid(*autoGridItem, *emptyGridArea);
+
+        if (!isGridAutoFlowDense)
+            minorAxisCursors[majorAxisPositions->resolvedInitialPosition.toInt()] = (direction == ForColumns) ? emptyGridArea->rows.resolvedInitialPosition.toInt() : emptyGridArea->columns.resolvedInitialPosition.toInt();
     }
 }
 
 void RenderGrid::placeAutoMajorAxisItemsOnGrid(const Vector<RenderBox*>& autoGridItems)
 {
     std::pair<size_t, size_t> autoPlacementCursor = std::make_pair(0, 0);
     bool isGridAutoFlowDense = style()->isGridAutoFlowAlgorithmDense();
 
     for (const auto& autoGridItem : autoGridItems) {
         placeAutoMajorAxisItemOnGrid(*autoGridItem, autoPlacementCursor);
@@ skipping 735 matching lines @@
     if (isOutOfFlowPositioned())
         return "RenderGrid (positioned)";
     if (isAnonymous())
         return "RenderGrid (generated)";
     if (isRelPositioned())
         return "RenderGrid (relative positioned)";
     return "RenderGrid";
 }
 
 } // namespace blink