1107778 - [css-grid] implement automatic grid item placement

Status: RESOLVED FIXED

(Core :: Layout, enhancement)

Description

[Mats Palmgren (inactive)]

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

Comment 1

[Mats Palmgren (inactive)]

Attachment: [css-grid] implement automatic grid item placement.

(applies on top of patches in bug 1009776)

Comment 2

[Mats Palmgren (inactive)]

BTW, I have ~2000 lines of reftests for grid areas (this bug and bug 1009776).
We need bug 1139539 first though.  (I compared the layout with Chrome Canary and it
appeared to match, fwiw.)

Comment 3

[Mats Palmgren (inactive)]

Full disclosure: it didn't match at first because I implemented slightly more
advanced cursors for Step 1 than specced.  I thought it was a bug in Chrome at
first so I contacted Rego (who implemented this in Chrome) and he pointed me
to this thread:
https://lists.w3.org/Archives/Public/www-style/2015Feb/0320.html
where Tab says a grid item only moves the cursors on its *first* row.

(My gut feeling is still that a grid item should move the cursor on all the rows
it occupies, but I'm still chewing on this...)

Anyway, just so you know for the review on that bit...

Comment 4

[Daniel Holbert [:dholbert]]

Comment on attachment 8572726 [details] [diff] [review]
[css-grid] implement automatic grid item placement.

Review of attachment 8572726 [details] [diff] [review]:
-----------------------------------------------------------------

Haven't looked in detail yet, but here's what I've got so far:

::: layout/generic/nsGridContainerFrame.cpp
@@ +590,5 @@
>      }
>    }
> +
> +  // http://dev.w3.org/csswg/css-grid/#auto-placement-algo
> +  // Step 1, place 'auto' items that has one definite position -

nit, "items that has" -- s/has/have/, I think?

@@ +593,5 @@
> +  // http://dev.w3.org/csswg/css-grid/#auto-placement-algo
> +  // Step 1, place 'auto' items that has one definite position -
> +  // definite row (column) for grid-auto-flow:row (column).
> +  const bool isRowOrder = (aStyle->mGridAutoFlow & NS_STYLE_GRID_AUTO_FLOW_ROW);
> +  const bool isSparse = !(aStyle->mGridAutoFlow & NS_STYLE_GRID_AUTO_FLOW_DENSE);

nit: this line is just 82 chars.

::: layout/generic/nsGridContainerFrame.h
@@ +167,5 @@
>  
>    /**
> +   * Place aArea in the first column (in row aArea->mRows.mStart) starting at
> +   * aStartCol without overlapping other items.  The resulting aArea may
> +   * overflow the grid bounds.

There are (at least?) 2 types of "grid bounds" -- implicit & explicit. Please clarify this to indicate which bounds you're talking about. (I think "explicit"? Or maybe "current implicit" [w/ 'current' indicating that we expect the grid will ultimately grow, so that there won't be overflow)

(This applies to the documentation for PlaceAutoCol, FindAutoCol, PlaceAutoRow, FindAutoRow - each of them have something about "may...overflow the grid bounds")

@@ +211,5 @@
> +
> +  /**
> +   * Place aArea in the first row starting at aStartCol,aStartRow without
> +   * causing it to overlap other items or overflow mGridRowEnd.
> +   * If there's no such row in aStartCol, continue in position 1,aStartCol+1.

That should be "position aStartCol+1, 1." at the end there.

(Elsewhere, you list coordinates as "col, row"; best to stay consistent.) (This is in the PlaceAutoAutoInColOrder documentation, if it's not clear from splinter-context.)

Comment 5

[Mats Palmgren (inactive)]

Do you have any further comments on this patch?

Comment 6

[Mats Palmgren (inactive)]

Attachment: part 2, [css-grid] Some reftests for grid item placement with auto positions.

Tests for the code in this bug.  I'll land it together with bug 1139539
since it requires that code to pass.

Comment 7

[Daniel Holbert [:dholbert]]

(In reply to Mats Palmgren (:mats) from comment #5)
> Do you have any further comments on this patch?

(Sorry for the delay here -- I'm intending to finish this review today.)

Comment 8

[Daniel Holbert [:dholbert]]

Comment on attachment 8572726 [details] [diff] [review]
[css-grid] implement automatic grid item placement.

Review of attachment 8572726 [details] [diff] [review]:
-----------------------------------------------------------------

Not quite through this patch, but here's my second wave of feedback (the first wave being comment 4):

::: layout/generic/nsGridContainerFrame.cpp
@@ +422,5 @@
> +nsGridContainerFrame::FindAutoCol(uint32_t aStartCol, uint32_t aLockedRow,
> +                                  const GridArea* aArea) const
> +{
> +  MOZ_ASSERT(aStartCol > 0);
> +  MOZ_ASSERT(aLockedRow > 0);

Add a message to these assertions here, e.g. "expecting 1-based track numbers".

(Same goes for FindAutoRow)

@@ +432,5 @@
> +    if (i >= mCellMap.mCells.Length()) {
> +      break;
> +    }
> +    const nsTArray<CellMap::Cell>& cellsInRow = mCellMap.mCells[i];
> +    const uint32_t len = cellsInRow.Length();

(Maybe s/len/jEnd/, for consistency & symmetry with the similar code in "FindAutoRow"? Particularly given my comment on "clampedJEnd", which will do away with "len" over there.)

@@ +434,5 @@
> +    }
> +    const nsTArray<CellMap::Cell>& cellsInRow = mCellMap.mCells[i];
> +    const uint32_t len = cellsInRow.Length();
> +    const uint32_t lastCandidate = candidate;
> +    for (uint32_t j = candidate, gap = 0; j < len && gap < extent; ++j, ++gap) {

Document what this loop is trying to do. e.g.:
  // Find the first gap in current row that's at least |extent| wide.
  // (|gap| tracks how wide the current gap is.)

@@ +452,5 @@
> +    } else {
> +      ++i;
> +    }
> +  }
> +  return candidate + 1;

Add a comment explaining the magic "+ 1" here (we're converting from 0-based array-idx to a 1-based track-idx, I think?)

(This goes for both FindAutoCol & FindAutoCol)

@@ +458,5 @@
> +
> +void
> +nsGridContainerFrame::PlaceAutoCol(uint32_t aStartCol, GridArea* aArea) const
> +{
> +  MOZ_ASSERT(aArea->mRows.IsDefinite());

Maybe worth also adding "&& aArea->mCols.IsAuto()" to this assertion?

It looks like the caller ensures that this is true -- and from the function-name, it seems like something that's reasonable to assert.  And if we end up hitting this function with *definite* mCols, it seems like it'd be good to trip an assertion before we stomp on the preexisting mCols.mStart / mCols.End values.

(Same goes for PlaceAutoRow())

@@ +462,5 @@
> +  MOZ_ASSERT(aArea->mRows.IsDefinite());
> +  uint32_t col = FindAutoCol(aStartCol, aArea->mRows.mStart, aArea);
> +  uint32_t colExtent = aArea->mCols.Extent();
> +  aArea->mCols.mStart = col;
> +  aArea->mCols.mEnd = col + colExtent;

Optional: These last 3 lines seem like they should maybe be replaced with a 1-line call to a LineRange method, like:
  aArea->mCols.ResolveAutoPosition(col);

(mCols already knows its extent & can update mEnd on its own; it just needs the resolved start-idx. This new method could perhaps assert IsAuto() and that its arg is nonzero, as sanity-checks, too)

Same goes for the analogous 3 lines in PlaceAutoRow.

@@ +478,5 @@
> +  const uint32_t jEnd = jStart + aArea->mCols.Extent();
> +  const uint32_t iEnd = mCellMap.mCells.Length();
> +  uint32_t candidate = aStartRow - 1;
> +  for (uint32_t i = candidate, gap = 0; i < iEnd && gap < extent; ++i) {
> +    ++gap;

Can you move "++gap" up into the for-statement here?  That'd make this function (FindAutoRow) more analogous to your FindAutoCol() impl, which has ++gap in the for statement.

I don't think this change should affect behavior -- we don't actually read "gap" at all inside the loop-body -- just in the loop condition. (gap < extent)  So I think your currently-placed "++gap" (just after the loop begins) should be equivalent to having ++gap in the "for" statement (as the loop ends) -- in either case, it'll happens before we evaluate the loop condition. And it makes more sense to me, conceptually, to increment at the end, *after* we've established that we really can grow the gap.

@@ +481,5 @@
> +  for (uint32_t i = candidate, gap = 0; i < iEnd && gap < extent; ++i) {
> +    ++gap;
> +    const nsTArray<CellMap::Cell>& cellsInRow = mCellMap.mCells[i];
> +    const uint32_t len = cellsInRow.Length();
> +    for (uint32_t j = jStart; j < jEnd && j < len; ++j) {

Seems wasteful to compare "j" against 2 different upper-limits on each iteration here.  Let's just pick the smaller of jEnd and len -- something like:
  const uint32_t clampedJEnd = std::min(jEnd, cellsInRow.Length());
  for (uint32_t j = jStart; j < clampedJEnd; ++j) {

@@ +485,5 @@
> +    for (uint32_t j = jStart; j < jEnd && j < len; ++j) {
> +      if (cellsInRow[j].mIsOccupied) {
> +        gap = 0;
> +        candidate = i + 1;
> +        break;

Document the reason for the +1 here. (In particular, it's different from most of the other explicit "+1" / "-1" adjustments to 'candidate' in these functions, which are usually for 0-to-1 base conversions.)

e.g. something like this (similar to your comment in FindAutoCol):
    // Couldn't fit 'extent' rows at 'candidate' here; we hit something
    // at row 'i'.  So, try row after 'i' as our next candidate.

@@ +608,5 @@
> +      LineRange& minor = isRowOrder ? area->mCols : area->mRows;
> +      auto PlacementFunc = isRowOrder ? &nsGridContainerFrame::PlaceAutoCol
> +                                      : &nsGridContainerFrame::PlaceAutoRow;
> +      if (major.IsDefinite() && minor.IsAuto()) {
> +        // items with 'auto' in the minor dimension only.

I think PlacementFunc should be declared inside this "if" body, because
 (1) (code-wise) That's the only place it's used.
 (2) (conceptually) These functions only make sense as being our "placement function" if this "if" conditional is satisfied. 

(i.e. if we're row-order, then it only makes sense that we'd want PlaceAutoCol if our column-span is auto.)

Comment 9

[Daniel Holbert [:dholbert]]

Comment on attachment 8572726 [details] [diff] [review]
[css-grid] implement automatic grid item placement.

Review of attachment 8572726 [details] [diff] [review]:
-----------------------------------------------------------------

Third & final wave of feedback -- r=me with this & earlier waves of feedback addressed as you see fit.

::: layout/generic/nsGridContainerFrame.cpp
@@ +524,5 @@
> +  }
> +  MOZ_ASSERT(row < gridRowEnd || col == 1,
> +             "expected column 1 for placing in new line");
> +  aArea->mCols = LineRange(col, col + colExtent);
> +  aArea->mRows = LineRange(row, row + aArea->mRows.Extent());

These expressions should probably be consistent with how you tell mRows/mCols their resolved auto-start position in PlaceAutoCol() / PlaceAutoRow(), using something like my suggested "ResolveAutoPosition" (though you can probably come up with a better name).

In particular, mCols/mRows already *know* their extent, so it seems a bit silly that we have to look it up & do arithmetic just to effectively give it back the same extent it already had. We've got this arithmetic hardcoded in 6 different places, which makes it more likely that we could have or introduce a mistake in one of those places. Really, we just need to tell mCols/mRows their resolved start-line, and they can do arithmetic internally to update their end-line & preserve their extent.

(This applies both to PlaceAutoAutoInRowOrder and PlaceAutoAutoInColOrder)

@@ +648,5 @@
> +        if (isSparse) {
> +          if (minor.mStart < cursorMinor) {
> +            ++cursorMajor;
> +          }
> +          cursorMinor = minor.mStart;

So,  I was going to say: "In the non-sparse case here, I believe we're supposed to set cursorMajor to 1".  But then I realized that you have cursorMajor just *staying at 1* in the non-sparse case, which means we're OK after all. :)

That fact would be worth calling out in a comment -- something like
        if (isSparse) {
          [...]
        } // else, leave cursors pointing at (1,1)

Or alternately, you could document this up next to the cursorMajor/cursorMinor declarations.

@@ +663,5 @@
> +          PlaceAutoAutoInColOrder(cursorMajor, cursorMinor, area);
> +        }
> +        if (isSparse) {
> +          cursorMinor = minor.mEnd;
> +          cursorMajor = major.mStart;

Nit: consider swapping these last 2 lines (handle "cursorMajor" first).

Everywhere else where you've got 2 back-2-back lines where one deals with Major and the other deals with Minor, you handle Major first. (including the #if DEBUG section right after this)

@@ +664,5 @@
> +        }
> +        if (isSparse) {
> +          cursorMinor = minor.mEnd;
> +          cursorMajor = major.mStart;
> +#if DEBUG

We seem to prefer "#ifdef DEBUG", not "#if".

(In layout, there are only 3 instances of "#if DEBUG", vs. 1074 instances of "#ifdef DEBUG")

@@ +668,5 @@
> +#if DEBUG
> +          uint32_t gridMajorEnd = isRowOrder ? mGridRowEnd : mGridColEnd;
> +          uint32_t gridMinorEnd = isRowOrder ? mGridColEnd : mGridRowEnd;
> +          MOZ_ASSERT(cursorMajor == gridMajorEnd || cursorMinor <= gridMinorEnd,
> +                     "we shouldn't add implicit minor tracks for auto/auto");

Are the two conditions joined by "||" actually connected here? I don't see how they connect or how they map to the assertion-message.

I wonder if this should maybe really be:
 MOZ_ASSERT(cursorMajor <= gridMajorEnd,
            "we shouldn't need to place items further than 1 track "
            "past the current end of the grid, in major dimension");
 MOZ_ASSERT(cursorMinor <= gridMinorEnd,
            "we shouldn't add implicit minor tracks for auto/auto");

Comment 10

[Mats Palmgren (inactive)]

Attachment: part 1, [css-grid] implement automatic grid item placement.

Thanks for your comments; I've addressed most of them as you suggested
so I'll only make a few notes:

> > +  for (uint32_t i = candidate, gap = 0; i < iEnd && gap < extent; ++i) {
> > +    ++gap;
> 
> Can you move "++gap" up into the for-statement here?  That'd make this
> function (FindAutoRow) more analogous to your FindAutoCol() impl, which has
> ++gap in the for statement.
> 
> I don't think this change should affect behavior -- we don't actually read
> "gap" at all inside the loop-body -- just in the loop condition.

No, actually, it does affect the loop, because we do "gap = 0" if some
column is occupied and then continue the iteration, which would increment
'gap' *before* checking the condition, so we would have 'gap' == 1 and
thus exit the loop if 'extent' is 1.

I tested moving the "++gap" as you suggested and many tests failed with
that (extent == 1 is fairly common).

So why didn't the same thing fail in the earlier loop?  Well, that's
a bug actually, although due to the optimization there (skipping all
occupied columns) it actually works since that implicitly guarantees
a gap of 1 if there is one.

Anyway, the code shouldn't depend on that optimization of course, so
I moved the ++gap inside the loop there too.  (I verified that tests
fail with the old code w/o the optimization)


> I think PlacementFunc should be declared inside this "if" body, ...

I would do that except I realized that this calculation is a loop
invariant, so I moved it outside the loop instead to make that clear.


> > +  uint32_t gridMajorEnd = isRowOrder ? mGridRowEnd : mGridColEnd;
> > +  uint32_t gridMinorEnd = isRowOrder ? mGridColEnd : mGridRowEnd;
> > +  MOZ_ASSERT(cursorMajor == gridMajorEnd || cursorMinor <= gridMinorEnd,
> > +             "we shouldn't add implicit minor tracks for auto/auto");
> 
> Are the two conditions joined by "||" actually connected here? I don't see
> how they connect or how they map to the assertion-message.

I was going to say yes, b/c if the item we're auto-placing here is
wider then any row so far it will cause a new row *and* be wider than
all the other rows so it will also create new implicit columns.
But then I realized that we have already inflated both dimensions to
be at least as wide as the widest item in Step 2 of the algorithm,
so that can't occur and you're quite right that we can assert that
no minor tracks are ever created here.  Clever boy :-)

Comment 11

[Daniel Holbert [:dholbert]]

(In reply to Mats Palmgren (:mats) from comment #10)
> > I think PlacementFunc should be declared inside this "if" body, ...
> 
> I would do that except I realized that this calculation is a loop
> invariant, so I moved it outside the loop instead to make that clear.

Maybe rename it to "minorPlacementFunc", then? (For symmetry with "majorPlacementFunc", which you declare later)  (Or "minorAutoPlacementFunc" even, though maybe that's too long)

Part of my concern here was that, at the spot it's declared, it's unclear what it represents or why the resulting particular choice of "Placement Func" is appropriate.  (It's a bit more-unclear now that it's further from its actual usage, too.)

Anyway, not a huge deal, & could be tweaked in a followup as well.

Comment 12

[Mats Palmgren (inactive)]

https://hg.mozilla.org/integration/mozilla-inbound/rev/3c33e363db31

https://hg.mozilla.org/integration/mozilla-inbound/rev/d1917dcc93ce

Comment 13

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/3c33e363db31
https://hg.mozilla.org/mozilla-central/rev/d1917dcc93ce

Comment 14

[Jonathan Kew [:jfkthame]]

Comment on attachment 8575982 [details] [diff] [review]
part 2, [css-grid] Some reftests for grid item placement with auto positions.

Review of attachment 8575982 [details] [diff] [review]:
-----------------------------------------------------------------

::: layout/reftests/css-grid/reftest.list
@@ +9,5 @@
>  == grid-placement-definite-002.html grid-placement-definite-002-ref.html
> +== grid-placement-auto-row-sparse-001.html grid-placement-auto-row-sparse-001-ref.html
> +== grid-placement-auto-row-dense-001.html grid-placement-auto-row-dense-001-ref.html
> +== grid-placement-auto-col-sparse-001.html grid-placement-auto-col-sparse-001-ref.html
> +== grid-placement-auto-col-dense-001.html grid-placement-auto-col-dense-001-ref.html

The manifest here fails to mention the grid-placement-auto-001.html testcase and reference that were included in the patch. Is that an oversight?

Note that when I tried it manually, I saw a failure in the last row of grid-placement-auto-001.

Comment 15

[Mats Palmgren (inactive)]

(In reply to Jonathan Kew (:jfkthame) from comment #14)
> > +== grid-placement-auto-row-sparse-001.html grid-placement-auto-row-sparse-001-ref.html
> > +== grid-placement-auto-row-dense-001.html grid-placement-auto-row-dense-001-ref.html
> > +== grid-placement-auto-col-sparse-001.html grid-placement-auto-col-sparse-001-ref.html
> > +== grid-placement-auto-col-dense-001.html grid-placement-auto-col-dense-001-ref.html
> 
> The manifest here fails to mention the grid-placement-auto-001.html testcase
> and reference that were included in the patch. Is that an oversight?

I wrote grid-placement-auto-001.html first, then decided to split it up into the
four variations above, so it was included by mistake.

I'll "hg rm" those two files when I get the chance (unless someone beats me to it).

Comment 16

[Mats Palmgren (inactive)]

Removed the files that were accidentally landed:
layout/reftests/css-grid/grid-placement-auto-001-ref.html
layout/reftests/css-grid/grid-placement-auto-001.html

https://hg.mozilla.org/integration/mozilla-inbound/rev/2cb44074958a

Comment 17

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/2cb44074958a