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

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

The first step of grid item placement algorithm has been updated in
order to support both "sparse" and "dense" modes. Current code is always
doing a "dense" packing in this case.

Modified RenderGrid::placeSpecifiedMajorAxisItemsOnGrid() in order to
add a cursor for each row/column and use it to place items in the right
position.

See: http://dev.w3.org/csswg/css-grid/#auto-placement-algo

BUG=384099
TEST=fast/css-grid-layout/grid-item-auto-placement-fixed-row-column.html

Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=190759

[Manuel Rego, 2015-02-13 13:02:52]

rego@igalia.com changed reviewers:
+ eae@chromium.org, jchaffraix@chromium.org, leviw@chromium.org

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

https://codereview.chromium.org/920413002/diff/1/Source/core/rendering/Render...
File Source/core/rendering/RenderGrid.cpp (right):

https://codereview.chromium.org/920413002/diff/1/Source/core/rendering/Render...
Source/core/rendering/RenderGrid.cpp:992: GridIterator iterator(m_grid,
autoPlacementMajorAxisDirection(),
majorAxisPositions->resolvedInitialPosition.toInt(), isGridAutoFlowDense ? 0 :
minorAxisCursors[majorAxisPositions->resolvedInitialPosition.toInt()]);
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]

Thanks for the review, see the comments inline.

https://codereview.chromium.org/920413002/diff/1/Source/core/rendering/Render...
File Source/core/rendering/RenderGrid.cpp (right):

https://codereview.chromium.org/920413002/diff/1/Source/core/rendering/Render...
Source/core/rendering/RenderGrid.cpp:992: GridIterator iterator(m_grid,
autoPlacementMajorAxisDirection(),
majorAxisPositions->resolvedInitialPosition.toInt(), isGridAutoFlowDense ? 0 :
minorAxisCursors[majorAxisPositions->resolvedInitialPosition.toInt()]);
On 2015/02/18 21:08:40, Julien Chaffraix - PST wrote:
> That's relying on the default value in minorAxisCursor (we set it below),
which
> is weird and unintuitive.

We can use minorAxisCursors.fill(0) before to make it clear that it's 
the initial value.

> 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?

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]

lgtm

https://codereview.chromium.org/920413002/diff/1/Source/core/rendering/Render...
File Source/core/rendering/RenderGrid.cpp (right):

https://codereview.chromium.org/920413002/diff/1/Source/core/rendering/Render...
Source/core/rendering/RenderGrid.cpp:984: Vector<size_t> minorAxisCursors;
I would love a comment about this vector to explain what it's doing.

https://codereview.chromium.org/920413002/diff/1/Source/core/rendering/Render...
Source/core/rendering/RenderGrid.cpp:992: GridIterator iterator(m_grid,
autoPlacementMajorAxisDirection(),
majorAxisPositions->resolvedInitialPosition.toInt(), isGridAutoFlowDense ? 0 :
minorAxisCursors[majorAxisPositions->resolvedInitialPosition.toInt()]);
On 2015/02/18 at 21:23:10, Manuel Rego wrote:
> On 2015/02/18 21:08:40, Julien Chaffraix - PST wrote:
> > That's relying on the default value in minorAxisCursor (we set it below),
which
> > is weird and unintuitive.
> 
> We can use minorAxisCursors.fill(0) before to make it clear that it's 
> the initial value.

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 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?
> 
> 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.

I see the issue and that we're processing step 1. of the auto placement
algorithm, not the general case.

[Manuel Rego, 2015-02-23 22:22:01]

Thank for the review.

https://codereview.chromium.org/920413002/diff/1/Source/core/rendering/Render...
File Source/core/rendering/RenderGrid.cpp (right):

https://codereview.chromium.org/920413002/diff/1/Source/core/rendering/Render...
Source/core/rendering/RenderGrid.cpp:984: Vector<size_t> minorAxisCursors;
On 2015/02/23 16:15:16, Julien Chaffraix - PST wrote:
> I would love a comment about this vector to explain what it's doing.

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.

[Manuel Rego, 2015-02-23 22:22:14]

The CQ bit was checked by rego@igalia.com

[Manuel Rego, 2015-02-23 22:22:14]

The patchset sent to the CQ was uploaded after l-g-t-m from
jchaffraix@chromium.org
Link to the patchset: https://codereview.chromium.org/920413002/#ps20001 (title:
"Patch for landing using a map instead of a vector")

[commit-bot: I haz the power, 2015-02-23 22:22:54]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/920413002/20001

[commit-bot: I haz the power, 2015-02-24 04:43:19]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2015-02-24 04:43:21]

Try jobs failed on following builders:
  linux_blink_rel on tryserver.blink (JOB_FAILED,
http://build.chromium.org/p/tryserver.blink/builders/linux_blink_rel/builds/4...)

[Manuel Rego, 2015-02-24 16:49:11]

The CQ bit was checked by rego@igalia.com

[Manuel Rego, 2015-02-24 16:49:11]

The patchset sent to the CQ was uploaded after l-g-t-m from
jchaffraix@chromium.org
Link to the patchset: https://codereview.chromium.org/920413002/#ps40001 (title:
"Fixing issues in the bots due to 0 key (using
WTF::UnsignedWithZeroKeyHashTraits)")

[commit-bot: I haz the power, 2015-02-24 16:50:26]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/920413002/40001

[commit-bot: I haz the power, 2015-02-24 17:02:13]

Committed patchset #3 (id:40001) as
https://src.chromium.org/viewvc/blink?view=rev&revision=190759