811521 - Keep flex container's child-frame list sorted by "order" property

Status: RESOLVED FIXED

(Core :: Layout, defect)

Description

[Daniel Holbert [:dholbert]]

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

Attachment: fix

This calls into bug 813358's templated SortFrameList() / IsFrameListSorted() helper-functions to sort our child list.

Comment 2

[Daniel Holbert [:dholbert]]

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

Attachment: 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]]

Attachment: 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-4, no longer working on Mozilla)]

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

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

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

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

(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-4, no longer working on Mozilla)]

sounds fine

Comment 11

[Daniel Holbert [:dholbert]]

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

https://hg.mozilla.org/mozilla-central/rev/c0adf89b103b