1107786 - [css-grid] implement "order-modified document order" for grid item placement ('order' property)

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)]

I see two ways to implement this:
1. as done in flexbox: modify the child frame list so that it's sorted
2. write an iterator that gives you the child frames in sorted order
   (without actually re-ordering the frame list) and reflow/paint child
   frames using this iterator

I think both would be simple and roughly equal to implement.  1. has
the slight disadvantage that the child frames are in an unnatural order
which may confuse other code like the frame constructor.  1. also makes
kbd tabbing respect the 'order' property which it probably shouldn't
per the HTML spec (although CSS specs may override that? bug 812687).
Grid can also make items unordered visually anyway, either explicitly
using definite placement or implicitly with 'dense' auto-placement.

I don't think 1. or 2. matters for Find or Selection much, which are
going to be confusing for users anyway unless we do something special
for Grid (i.e. making them operate in actual visual order).

Fragmentation for Grid occurs between rows so pushing may push arbitrary
child frames from the child list, so there's no particular advantage for
either 1. or 2. as I see it.

Thoughts?

Comment 2

[Mats Palmgren (inactive)]

Attachment: part 1, [css-grid] Implement layout and painting per the CSS 'order' property for normal flow grid items.

I went with alternative 2. b/c it seems less complicated.

Comment 3

[Mats Palmgren (inactive)]

Attachment: part 2, [css-grid] Implement a DisplayList sorting function that sorts by CSS 'order'.

Comment 4

[Mats Palmgren (inactive)]

Attachment: part 3, [css-grid] Implement layout and painting per the CSS 'order' property for absolute positioned grid items.

Comment 5

[Mats Palmgren (inactive)]

Attachment: part 4, [css-grid] Reftests for the CSS 'order' property on grid items.

Comment 6

[Daniel Holbert [:dholbert]]

(In reply to Mats Palmgren (:mats) from comment #2)
> I went with alternative 2. b/c it seems less complicated.

Yeah, there probably will be fewer special cases that way.

It's a bit slower to have to potentially repeat the same sort over and over, but on the positive side, it's handy to be able to depend on things always being in document order.  So, seems fine to me! Maybe we'll want to switch flexbox to match this eventually, to for consistency & to make bug 812687 unnecessary to fix.

Comment 7

[Mats Palmgren (inactive)]

We can probably optimize this by keeping data around between reflows.
I think I'll do that for some of the other data anyway at some point.

Regarding tabbing, I think raw DOM order / CSS 'order' are both
undesirable for tabbing through a grid.  I think "'order'-modified
grid order"(*) would be better.
(*) http://dev.w3.org/csswg/css-grid/#order_modified-grid-order
TL;DR traverse cells in minor/major order

Comment 8

[Daniel Holbert [:dholbert]]

Comment on attachment 8582447 [details] [diff] [review]
part 1, [css-grid] Implement layout and painting per the CSS 'order' property for normal flow grid items.

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

r- for now, due to the nsTArray::Sort issue mentioned below; otherwise, comments are mostly nits.

::: layout/generic/nsGridContainerFrame.cpp
@@ +26,5 @@
>  using namespace mozilla;
>  typedef nsGridContainerFrame::TrackSize TrackSize;
>  
> +class nsGridContainerFrame::GridItemDocOrderIterator
> +{

I'm confused by "DocOrder" in the name of this class. It sounds like that means it iterates across them in document order (but it does not, necessarily; it iterates in 'order' order.)

Consider renaming and/or adding a brief comment above the class to clarify the behavior, to avoid giving the wrong impression about document-order iteration.

@@ +55,5 @@
> +        maxOrder = order;
> +      }
> +      if (count <= 1) {
> +        isOrdered = true;
> +      }

Is this count<=1 case necessary? It seems like we'll already get isOrdered = true for free. (isOrdered will be initialized to true, and the "for" loop above won't have reason to change it.)

@@ +65,5 @@
> +      mArray = new nsTArray<nsIFrame*>(count);
> +      for (nsFrameList::Enumerator e(mChildren); !e.AtEnd(); e.Next()) {
> +        mArray->AppendElement(e.get());
> +      }
> +      mArray->Sort(OrderComparator());

Unfortunately, nsTArray::Sort uses quicksort, which is not a stable sort. So I think this gives the wrong behavior -- it will potentially shuffle elements that share the same "order" to no longer be in document-order. (If you have e.g. a single element reordered with "order", then all the other elements may end up being jumbled.)

(I'm not sure how best to address this, in this iterator strategy. You'd have to make OrderComparator smarter, I suppose, with something like IsOrderLEQWithDOMFallback from nsFlexContainerFrame.)

@@ +69,5 @@
> +      mArray->Sort(OrderComparator());
> +    }
> +  }
> +  nsIFrame* operator*() const
> +  {

Nit: IMO this would be more readable with a blank line in between adjacent methods here. (Otherwise the code kinda all runs together and looks like one giant function.)

@@ +117,5 @@
> +  };
> +
> +  nsFrameList mChildren;
> +  Maybe<nsFrameList::Enumerator> mEnumerator;
> +  nsAutoPtr<nsTArray<nsIFrame*>> mArray;  

nit: end-of-line whitespace here.

Also, seems like mArray would be better off as a Maybe<nsTArray...>. Right now, it needs 2 heap allocations -- for the nsTArray object itself, and for its actual underlying array. We can eliminate the first allocation (& use stack memory instead for the nsTArray object itself) if we used Maybe<>.

(I think most of the mArray usages can stay as they are, since Maybe<> behaves like a pointer w.r.t. operator* and ->.)

Also: maybe add comments next to mEnumerator & mArray, saying e.g.:
  // Used if child list is already in ascending 'order'.
  // Used if child list is *not* in ascending 'order'.

@@ +1119,5 @@
>    const LogicalPoint gridOrigin(aContentArea.Origin(wm));
>    const nscoord gridWidth = aContentArea.Width(wm);
>    nsPresContext* pc = PresContext();
> +  aIter.Reset();
> +  for (; !aIter.AtEnd(); aIter.Next()) {

Right now, we're a bit inconsistent on assumptions about a passed-in iterator:
 * PlaceGridItems() just directly uses the passed-in iterator, without bothering to reset it.
 * ReflowChildren() resets it before first use.

We should probably make their expectations consistent.

It seems reasonable to require that a caller must pass in a *useful* iterator (one that's already pointed at the start), so I'd probably lean towards dropping the Reset() call in ReflowChildren (and moving it out to the caller).  But I'm happy going the other direction, too, if you prefer. (not trusting the caller, and always doing a sanity-check "Reset()" call before using a passed-in iterator.)

(It might even be worth adding an "AssertAtStart()" method to the iterator (with an #ifdef DEBUG impl, since it probably uses some debug-only information), which we could call as a precondition, to be sure the caller is matching our expectations.)

Comment 9

[Daniel Holbert [:dholbert]]

Comment on attachment 8582451 [details] [diff] [review]
part 3, [css-grid] Implement layout and painting per the CSS 'order' property for absolute positioned grid items.

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

::: layout/generic/nsGridContainerFrame.cpp
@@ +1259,5 @@
>    // inline-blocks in painting, so their borders/backgrounds all go on
>    // the BlockBorderBackgrounds list.
> +  nsDisplayList positionedDescendants;
> +  nsDisplayListSet childLists(aLists.BlockBorderBackgrounds(),
> +                              aLists.BlockBorderBackgrounds(),

Extend the existing comment to say something like,
  "Also, we capture positioned descendants so we can sort them by 'order'."

(Maybe seems self-explanatory, but it makes it clearer that the rest of this long childLists(...) constructor is un-interesting and just copying through stuff from aLists.)

Comment 10

[Mats Palmgren (inactive)]

> Unfortunately, nsTArray::Sort uses quicksort, which is not a stable sort.

Oh man, what a bummer!  Why on earth is it using quicksort?

Comment 11

[Mats Palmgren (inactive)]

(I filed bug 1147091 on getting a nsTArray::MergeSort method, fwiw)

Comment 12

[Mats Palmgren (inactive)]

Attachment: part 1, [css-grid] Implement layout and painting per the CSS 'order' property for normal flow grid items.

I'm addressing the nits here and spawning off the r- issue into
a separate patch for easier reviewing.

(In reply to Daniel Holbert [:dholbert] from comment #8)
> I'm confused by "DocOrder" in the name of this class.

I renamed it GridItemCSSOrderIterator.

> > +      if (count <= 1) {
> > +        isOrdered = true;
> > +      }
> 
> Is this count<=1 case necessary?

Good catch.  This was a remnant from an earlier version
of the patch that I forgot to remove.

> > +      mArray->Sort(OrderComparator());
> 
> Unfortunately, nsTArray::Sort uses quicksort
> (I'm not sure how best to address this, in this iterator strategy. You'd
> have to make OrderComparator smarter, I suppose, with something like
> IsOrderLEQWithDOMFallback from nsFlexContainerFrame.)

Ideally, some kind soul would implement nsTArray::MergeSort (bug 1147091).
I'm not holding my breath though... :-)

> Also, seems like mArray would be better off as a Maybe<nsTArray...>. Right
> now, it needs 2 heap allocations

Yep, good point.

> It seems reasonable to require that a caller must pass in a *useful*
> iterator (one that's already pointed at the start), so I'd probably lean
> towards dropping the Reset() call in ReflowChildren (and moving it out to
> the caller).

I made it so.

Comment 13

[Mats Palmgren (inactive)]

Attachment: part 1, addendum - use std::stable_sort

Just for review - I'll fold this into part 1 before landing.

(I still need to add a test that would have failed with QuickSort.)

Comment 14

[Mats Palmgren (inactive)]

BTW, the "mArray->Length() > 1" is because I read somewhere that stable_sort()
doesn't work for empty arrays, so I figured I might as well check for "> 1"
but now that I think about it - it would already be sorted in that case,
so this test isn't needed!  It's a bit subtle though, so I'll remove the
test and add a fatal assertion instead...

Comment 15

[Mats Palmgren (inactive)]

Attachment: part 1, addendum - use std::stable_sort

Comment 16

[Mats Palmgren (inactive)]

Comment on attachment 8582777 [details] [diff] [review]
part 1, addendum - use std::stable_sort

Actually, this is safer, just in case we're DIRTY and our child list
was changed after Reflow but before BuildDisplayList.  We could get
here with 'eKnownUnordered' passed in.

Comment 17

[Daniel Holbert [:dholbert]]

Comment on attachment 8582777 [details] [diff] [review]
part 1, addendum - use std::stable_sort

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

::: layout/generic/nsGridContainerFrame.cpp
@@ +63,5 @@
>        for (nsFrameList::Enumerator e(mChildren); !e.AtEnd(); e.Next()) {
>          mArray->AppendElement(e.get());
>        }
> +      if (mArray->Length() > 1) {
> +        std::stable_sort(mArray->begin(), mArray->end(), OrderComparator);

Two nits:

(1) Add a XXX comment here, mentioning bug 1147091, so that we have a better shot at remembering to migrate to the nsTArray version if & when it arrives.

(2) So, is the "Length() > 1" check here to avoid some pathological behavior (per comment 14)? It surprises me a bit that this is needed -- I'd assume that stable_sort() can sanely handle 0-length and 1-length cases. (Maybe even with an immediate early-return). Do you have a link / reference on the issues here?  If so, maybe mention it (or hint at it) in a comment -- otherwise, this check looks like something that might just get cleaned up as unnecessary, at some point in the future (perhaps naively, if we really need the check).

Anyway -- according to http://en.cppreference.com/w/cpp/algorithm/stable_sort, it seems like stable_sort should be fine here, generally -- it allocates a buffer using std::get_temporary_buffer, which promises not to throw exceptions. So I think this is OK.

@@ +117,1 @@
>      { return a->StylePosition()->mOrder < b->StylePosition()->mOrder; }

Nit: maybe just call this "IsOrderLessThan" or something like that, to make its behavior more obvious.

The current name, "OrderComparator" is a bit abstract.  (sounds like it could be a struct, like it was before, or a smart comparison function with -1/0/+1 return values.)  Something "LessThan"-flavored seems more specific & appropriate.

Comment 18

[Daniel Holbert [:dholbert]]

Gah, sorry -- that last nit was on the "OrderComparator" function-name. I have no idea why splinter decided to only show 1 line of context instead of 2 or more.

Comment 19

[Mats Palmgren (inactive)]

>  (2) So, is the "Length() > 1" check here to avoid some pathological behavior

Yeah, I saw a comment from someone on StackOverflow that it was undefined for
empty arrays, which surprised me a bit as well, but in retrospect I think the
guy was probably just confused.  I removed the "> 1" check after confirming
nothing bad happened in a small test program compiled with ASAN checks.

Comment 20

[Mats Palmgren (inactive)]

Attachment: part 1, [css-grid] Implement layout and painting per the CSS 'order' property for normal flow grid items.

(Merged in the r+ addendum patch with nits fixed.)

Comment 21

[Mats Palmgren (inactive)]

https://hg.mozilla.org/integration/mozilla-inbound/rev/b41915b3c38b
https://hg.mozilla.org/integration/mozilla-inbound/rev/33d6a3e888a8
https://hg.mozilla.org/integration/mozilla-inbound/rev/c2c20dfa58f6
https://hg.mozilla.org/integration/mozilla-inbound/rev/fbbe7bf43929

Comment 22

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/b41915b3c38b
https://hg.mozilla.org/mozilla-central/rev/33d6a3e888a8
https://hg.mozilla.org/mozilla-central/rev/c2c20dfa58f6
https://hg.mozilla.org/mozilla-central/rev/fbbe7bf43929