Last Comment Bug 811521 - Keep flex container's child-frame list sorted by "order" property
: Keep flex container's child-frame list sorted by "order" property
Status: RESOLVED FIXED
:
Product: Core
Classification: Components
Component: Layout (show other bugs)
: Trunk
: x86_64 Linux
: -- normal with 1 vote (vote)
: mozilla20
Assigned To: Daniel Holbert [:dholbert]
:
: Jet Villegas (:jet)
Mentors:
: 783474 (view as bug list)
Depends on: 812687 1048113 813358 825810 826483 873172 876074
Blocks: 783474 981116
  Show dependency treegraph
 
Reported: 2012-11-13 15:36 PST by Daniel Holbert [:dholbert]
Modified: 2015-03-24 09:28 PDT (History)
1 user (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
fix (21.74 KB, patch)
2012-11-27 16:24 PST, Daniel Holbert [:dholbert]
no flags Details | Diff | Splinter Review
fix w/ reftest, v2 (26.49 KB, patch)
2012-11-28 17:48 PST, Daniel Holbert [:dholbert]
no flags Details | Diff | Splinter Review
fix w/ reftest, v2a (26.35 KB, patch)
2012-11-30 16:26 PST, Daniel Holbert [:dholbert]
dbaron: review+
Details | Diff | Splinter Review

Description Daniel Holbert [:dholbert] 2012-11-13 15:36:07 PST
The "order" property is supposed to behave as if it reorders the actual frame tree, as far as layout and painting are concerned, but *not* as far as tab-index is concerned.

Right now, we don't *actually* reorder the frame tree, so that we can keep tab-index working correctly. (because that relies on the frame tree)  However, now that we're going to be paginating flex containers (and shifting kids back and forth between continuation frames), we really need the children to be in the correct sorted order, and we can add a hack of some sort to keep tab-index working.

THEREFORE: filing this bug on keeping a flex container's actual child list in sorted order.
Comment 1 Daniel Holbert [:dholbert] 2012-11-27 16:24:30 PST
Created attachment 685881 [details] [diff] [review]
fix

This calls into bug 813358's templated SortFrameList() / IsFrameListSorted() helper-functions to sort our child list.
Comment 2 Daniel Holbert [:dholbert] 2012-11-27 16:43:35 PST
Comment on attachment 685881 [details] [diff] [review]
fix

Canceling review while I add an optimization to make the checks here less costly when our children never need to be sorted. (the usual case)
Comment 3 Daniel Holbert [:dholbert] 2012-11-28 17:48:02 PST
Created attachment 686363 [details] [diff] [review]
fix w/ reftest, v2

OK -- now this will set a flag the first time we actually have to sort our children.

When the flag is false, we can be a bit faster about checking our children for sorted-ness -- we already know they're in DOM-order, so we don't need to consider DOM position when checking for sorted-ness.

But once the flag has been set (after we've messed with our child order at least once), we'll be a little more comprehensive in our comparisons -- specifically, when two children have the same "order" value, we'll check the DOM tree to figure out which should go first.

(Motivation for using this flag: the usual case will be that "order" won't be explicitly set.  It'd be nice if our "already-sorted?" check were as fast as possible for that usual-case, and especially nice if it didn't have to walk the DOM tree.  This achieves that.)
Comment 4 Daniel Holbert [:dholbert] 2012-11-30 16:26:34 PST
Created attachment 687323 [details] [diff] [review]
fix w/ reftest, v2a

(bug 815671 modified some of the code that this patch removes. Updating patch to fix bitrot.)
Comment 5 David Baron :dbaron: ⌚️UTC-10 (vacation, returning December 19) 2012-12-26 10:32:15 PST
Comment on attachment 687323 [details] [diff] [review]
fix w/ reftest, v2a

>+/**
>+ * Helper-function to find the nsIContent* that we should use for comparing the
>+ * DOM tree position of the given flex-item frame.
>+ *
>+ * In most cases, this will be aFrame->GetContent(), but if aFrame is an
>+ * anonymous container, then its GetContent() won't be what we want. In such
>+ * cases, we need to find aFrame's first non-anonymous-container descendant.
>+ */
>+static nsIContent*
>+GetContentForComparison(const nsIFrame* aFrame)

What sort of anonymous box has the wrong content?  I'd have hoped
that the anonymous boxes to wrap a non-flexbox in a flexbox would
have the right content.


In IsOrderLEQWithDOMFallback, it might be good to use <= rather
than < (even though the difference isn't relevant) just because
you're implementing a <= operator.


This is going to get a good bit more complicated wonce you start paginating, but r=dbaron on this.

(Once you start paginating, it's not clear to me whether it will be easier to do the sorting during reflow or frame construction.)
Comment 6 Daniel Holbert [:dholbert] 2012-12-26 10:43:59 PST
(In reply to David Baron [:dbaron] from comment #5)
> Comment on attachment 687323 [details] [diff] [review]
> fix w/ reftest, v2a
> 
> >+/**
> >+ * Helper-function to find the nsIContent* that we should use for comparing the
> >+ * DOM tree position of the given flex-item frame.
> >+ *
> >+ * In most cases, this will be aFrame->GetContent(), but if aFrame is an
> >+ * anonymous container, then its GetContent() won't be what we want. In such
> >+ * cases, we need to find aFrame's first non-anonymous-container descendant.
> 
> What sort of anonymous box has the wrong content?  I'd have hoped
> that the anonymous boxes to wrap a non-flexbox in a flexbox would
> have the right content.

In particular, an anonymous flex item's block-frame will have the "wrong" content (for sorting purposes).  E.g. consider the block that we generate to wrap "DEF" here:

 <div style="display: flex" id="flexContainer">
   <div>abc</div>
   DEF
   <div>ghi</div>
 </div>

We'll generate an anonymous flex item (a nsBlockFrame) around "DEF", and that block's mContent pointer will point to the flex container.  When we sort the children (e.g. after setting and then un-setting "order" on one of the children), we want to be ordering "DEF" based on the *text node's* DOM position, not on the flex container's DOM position.  So we have to descend *into* the anonymous flex item (ignoring its mContent pointer) and get its child's content pointer.

I seem to recall that table-fixup-generated table wrappers (around e.g. a raw "<td>" element) hit the same problem & require the same hackaround, too -- that's why this is a loop where we sometimes need to descend multiple levels.
Comment 7 Daniel Holbert [:dholbert] 2012-12-26 11:10:32 PST
(In reply to David Baron [:dbaron] from comment #5)
> This is going to get a good bit more complicated wonce you start paginating,
> but r=dbaron on this.

Yup -- my plan is to do a recursive check along the lines of
 Am I sorted?
 Is my last child <= my next continuation's first child?
 [recursive call on my next continuation]
...and if that finds out we're not sorted, then we'll blow away our continuations and rebuild them.

> (Once you start paginating, it's not clear to me whether it will be easier
> to do the sorting during reflow or frame construction.)

We'll need to at least do some of it during reflow, for cases of e.g. dynamic changes to "order" in a flex container that happens to be nested inside of a multicol element.
Comment 8 Daniel Holbert [:dholbert] 2012-12-26 11:35:10 PST
(In reply to David Baron [:dbaron] from comment #5)
> In IsOrderLEQWithDOMFallback, it might be good to use <= rather
> than < (even though the difference isn't relevant) just because
> you're implementing a <= operator.

(sorry for skipping this chunk when responding to the rest of the comment)

If it's OK with you, I think I'd like to kee this as-is (with "<") -- at least for me, that makes the code a little harder to read/grok, since
 (a) we already know they're not equal when we hit that clause
     (as you said, the difference isn't relevant -- but making it <= would imply that it
     might be possible that they're equal)

 (b) If by some miracle (or future-refactoring) the values _were_ equal, then a simple <= comparison wouldn't be sufficient -- we'd need to explicitly compare DOM positions. (as we do after that clause)

Actually... on reflection, IsOrderLEQWithDOMFallback is really a strict "less-than" rather than LEQ, except for the case where you're comparing the same frame... and actually we do the wrong thing in that case right now -- I should probably add a case for where GetContentForComparison() returns the same thing for both frames, and call that "equal" (but probably assert, because we're not expecting that to happen, unless aFrame1 == aFrame2)
Comment 9 Daniel Holbert [:dholbert] 2012-12-26 11:36:08 PST
(In reply to Daniel Holbert [:dholbert] from comment #8)
> If it's OK with you, I think I'd like to kee this as-is (with "<") -- at
> least for me, that makes the code a little harder to read/grok, since

(er s/that makes/that change would make/)
Comment 10 David Baron :dbaron: ⌚️UTC-10 (vacation, returning December 19) 2012-12-26 11:41:20 PST
sounds fine
Comment 11 Daniel Holbert [:dholbert] 2012-12-26 12:27:36 PST
Cool -- I added a "aFrame1 == aFrame2" early-return (as "equal"), with a NS_ERROR because we're not expecting that to happen (but it's feasible that an odd sort algorithm might compare things against themselves, so it's a case that our LEQ function should handle).

I also added a check to be sure we're not getting the same nsIContent* pointer from two different flex items. If that were something we were expecting, then we'd need to return "true" since those items would be equal. This would result in those flex items being sorted in an arbitrary order, which would be bad.  Luckily, it shouldn't happen (I don't know of any way to get 2 flex items from one DOM node), so I just added a MOZ_ASSERT to make that explicit.

https://hg.mozilla.org/integration/mozilla-inbound/rev/c0adf89b103b
Comment 12 Daniel Holbert [:dholbert] 2012-12-27 14:03:14 PST
https://hg.mozilla.org/mozilla-central/rev/c0adf89b103b
Comment 13 Daniel Holbert [:dholbert] 2013-02-15 13:21:31 PST
*** Bug 783474 has been marked as a duplicate of this bug. ***

Note You need to log in before you can comment on or make changes to this bug.