Closed Bug 1107786 Opened 10 years ago Closed 10 years ago

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

Categories

(Core :: Layout, enhancement)

enhancement
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla39
Tracking Status
firefox39 --- fixed

People

(Reporter: MatsPalmgren_bugz, Assigned: MatsPalmgren_bugz)

References

(Blocks 1 open bug)

Details

Attachments

(5 files, 3 obsolete files)

Depends on: 1145968
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?
I went with alternative 2. b/c it seems less complicated.
Attachment #8582447 - Flags: review?(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.
See Also: → 811521
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 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.)
Attachment #8582447 - Flags: review?(dholbert) → review-
Attachment #8582448 - Flags: review?(dholbert) → review+
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.)
Attachment #8582451 - Flags: review?(dholbert) → review+
> Unfortunately, nsTArray::Sort uses quicksort, which is not a stable sort. Oh man, what a bummer! Why on earth is it using quicksort?
(I filed bug 1147091 on getting a nsTArray::MergeSort method, fwiw)
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.
Attachment #8582447 - Attachment is obsolete: true
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.)
Attachment #8582777 - Flags: review?(dholbert)
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...
Attachment #8582777 - Attachment is obsolete: true
Attachment #8582777 - Flags: review?(dholbert)
Attachment #8582780 - Flags: review?(dholbert)
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.
Attachment #8582777 - Attachment is obsolete: false
Attachment #8582777 - Flags: review?(dholbert)
Attachment #8582780 - Attachment is obsolete: true
Attachment #8582780 - Flags: review?(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.
Attachment #8582777 - Flags: review?(dholbert) → review+
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.
> (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.
(Merged in the r+ addendum patch with nits fixed.)
Attachment #8582777 - Attachment is obsolete: true
Attachment #8583929 - Flags: review+
Flags: in-testsuite+
Depends on: 1266131
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Created:
Updated:
Size: