983434 - Store FlexItems and FlexLines in linked lists instead of nsTArray<>s

Status: RESOLVED FIXED

(Core :: Layout, defect)

Description

[Daniel Holbert [:dholbert]]

Right now, nsFlexContainerFrame::Reflow generates an array of lines, each of which contains an array of items.

In order to efficiently, process our children in reverse (for bug 983427), it would help if instead they were stored in a linked list.

This lets us do a forward pass over our child frames, converting them into a reverse-order collection of items/lines, in O(N) time.

(If instead we continued to use arrays, then for each new child we insert at the head of a FlexItem array, we have to shift the rest of the array over to make room. So that would end up being O(N^2) performance).

It will also be nice to have linked lists if we want to pass already-generated FlexLines between continuations of a flex container (much like we do with lines in block frames).

--> Filing this bug to store FlexItems and FlexLines in linked lists.

Comment 1

[Daniel Holbert [:dholbert]]

(BACKGROUND MOTIVATIONAL NOTE: So, I initially was planning on implementing a naive approach to bug 983427 -- the idea was, I was going to reverse the flex container's child-frame list, and then walk over that list the same way we currently do to generate FlexLines of FlexItems.

However, this approach has a problem in multi-line flex containers that have extra space on their last line. For example, if we have a "row wrap-reverse" flex container with three children "A,B,C", and only two items fit on a single line, then we *should* render that as two lines, with C on the top line and A & B on bottom. But my naive solution would end up giving us B & C on top and A on bottom.

For this to *actually* work (such that we fill the bottom flex line first in this example), we *really* need to leave our child-frame list untouched, so that we can do a correctly-ordered walk over it and fill flex lines in the correct order. Then, if our lines & items are stored in a linked list, we can create that list & just link the flex lines (and their items) together in reverse order. (which lets us ensure that those structures at least are approximately top-to-bottom, for bug 983427.))

Comment 2

[Daniel Holbert [:dholbert]]

Attachment: part 1: rename a few variables, promote a function to a private method

This first patch has a few minor changes that I spun off of the main patch here, to allow the main patch to be more targeted.

This first patch does the following:
  - Renames |curItem| to |item| in a few loops, for consistency & brevity.
  - Promotes FreezeOrRestoreEachFlexibleSize() to a private method on FlexLine (since it's only called in one place, by a private FlexLine method).  (This lets it access |mItems| as a member-variable, instead of needing it to be passed in as an arg. This is useful because my next patch adds better encapsulation around mItems.)
  - Adds "Is" to the name of a that function's boolean arg (s/aFinalIteration/aIsFinalIteration/).

Comment 3

[Daniel Holbert [:dholbert]]

Attachment: part 2 v1: Convert nsTArrays to LinkedLists

This patch does the main thing this bug is trying to achieve, which is:
 - Instead of using a nsTArray of FlexLines (each of which has a nsTArray of FlexItems), we'll now use the MFBT LinkedList container.

In support of that, this patch also:
 - Makes FlexLine's item list private instead of public (with accessors), for better encapsulation.
 - Adds a count of the number of FlexItems ("mNumItems") to FlexLine. This is kept up-to-date by the function that we use to add new items. (The count is needed in several places. We could calculate it on-the-fly, but that'd take O(N) work each time, now that the items are stored in a linked-list.)
 - Makes us pass around a FlexLine* "first line" pointer instead of a nsTArray<FlexLine> in several places. (We can iterate across the line list, given a pointer to the first one.)
 - Also makes us pass around a FlexLine* instead of a nsTArray<FlexItems> in several places. (We can't just pass a FlexItem* "first item pointer", becuase some functions also need the item-count, and that's stored on the FlexLine now.)
 - s/./->/ all over the place, since we're dealing with pointers to list-items now.
 - Simplifies some logic in GenerateFlexLines() about moving a flex item from one array to another when it doesn't fit.  (We'll now wait to add the FlexItem to a line until we're sure which line it goes in.)
 - Adds a "AutoFlexLineListClearer" RAII class to automatically clean up our LinkedList of flex lines (and their items) when reflow completes. (This is necessary because the LinkedList destructor doesn't free anything, and it asserts that the list is empty.)
 - Adds more documentation in a few places that this patch is already touching.

Comment 4

[Daniel Holbert [:dholbert]]

Attachment: part 2, v1a: Convert nsTArrays to LinkedLists

(fixed a typo in a comment)

Comment 5

[Daniel Holbert [:dholbert]]

Attachment: part 2, v1b: Convert nsTArrays to LinkedLists

(sorry, one last tweak: fixed a mis-indented line)

Comment 6

[Daniel Holbert [:dholbert]]

Attachment: part 2, v1c: Convert nsTArrays to LinkedLists

(One more tweak: added MOZ_GUARD_OBJECT macros to the RAII "AutoFlexLineListClearer" class, and qref'ed w/ 8 lines of context for easier reviewing.)

Comment 7

[Mats Palmgren (inactive)]

Comment on attachment 8391988 [details] [diff] [review]
part 2, v1c: Convert nsTArrays to LinkedLists

>layout/generic/nsFlexContainerFrame.cpp
> // Represents a flex item.
> // Includes the various pieces of input that the Flexbox Layout Algorithm uses
> // to resolve a flexible width.
>-class nsFlexContainerFrame::FlexItem {
>+class nsFlexContainerFrame::FlexItem : public LinkedListElement<FlexItem> {
> [...]
> // Represents a single flex line in a flex container.
> // Manages an array of the FlexItems that are in the line.
>-class nsFlexContainerFrame::FlexLine {
>+class nsFlexContainerFrame::FlexLine : public LinkedListElement<FlexLine> {

s/an array/a linked list/

Also, while we're here, change // to /** style comments?
and { should go on a separate line.

>+  uint32_t GetNumItems() const

I think this should be named NumItems().
Also, I think all the new accessors could have this MOZ_ASSERT
to increase the chance of catching anything going bad.

>+  void AddItem(FlexItem* aItem,
> [...]
>+    mItems.insertBack(aItem);
>     mTotalInnerHypotheticalMainSize += aItemInnerHypotheticalMainSize;
>     mTotalOuterHypotheticalMainSize += aItemOuterHypotheticalMainSize;
>+    mNumItems++;

Minor nit: I'd prefer moving "mNumItems++" two lines up.

> FlexLine::ResolveFlexibleLengths(nscoord aFlexContainerMainSize)
> {
>   PR_LOG(GetFlexContainerLog(), PR_LOG_DEBUG, ("ResolveFlexibleLengths\n"));
>-  if (mItems.IsEmpty()) {
>+  if (mItems.isEmpty()) {

I would prefer IsEmpty() (the accessor you added)

>@@ -2326,75 +2379,63 @@ nsFlexContainerFrame::GenerateFlexLines(
>+        !curLine->IsEmpty() && // Don't wrap if it'll leave line empty

The comment seems slightly confusing now that we don't remove the item.
Perhaps "No need to wrap at the start of a line" is clearer?

>       // Need to wrap to a new line! Create a new line, create a copy of the
>       // newest FlexItem there, and clear that FlexItem out of the prev. line.

Remove the "create a copy..." part.  Actually, I think you can just remove
the whole comment.  The comment above the 'if' is clear enough what it does.

> // Returns the content-box main-size of our flex container, based on the
> // available height (if appropriate) and the main-sizes of the flex items.
> static nscoord
> ClampFlexContainerMainSize(const nsHTMLReflowState& aReflowState,
>                            const FlexboxAxisTracker& aAxisTracker,
>                            nscoord aUnclampedMainSize,
>                            nscoord aAvailableHeightForContent,
>-                           const nsTArray<FlexLine>& aLines,
>+                           FlexLine* aFirstLine,

Seems like it could take a 'const FlexLine*' ?

>layout/generic/nsFlexContainerFrame.h
>+  // Returns a new FlexItem for the given child frame, allocated on the heap.
>+  // Caller is responsible for managing that child's lifetime.
>+  FlexItem* GenerateFlexItemForChild(nsPresContext* aPresContext,

s/child/item/ ?

Comment 8

[Mats Palmgren (inactive)]

> s/child/item/ ?

I mean the "child" in "child's lifetime".

Comment 9

[Mats Palmgren (inactive)]

Also, now that FlexLine/FlexItem are individually heap-allocated, I think we should
consider using an arena to coalesce the individual new/delete.  With an arena we can
also skip the traversal at the end of the life time, assuming they stay POD.
File a separate bug about that?

Comment 10

[Daniel Holbert [:dholbert]]

Thanks for the review! (Good catch on the "create a copy" and "array" comments - I looked right past those. Definitely don't want to leave in stale documentation.)

Addressed all review comments, and filed bug 984613 for arena allocation, and landed:
https://hg.mozilla.org/integration/mozilla-inbound/rev/850dd9773e9d
https://hg.mozilla.org/integration/mozilla-inbound/rev/c5dc2de8d224

(Patches coming soon on bug 983427 to actually benefit from this work.)

Comment 11

[Daniel Holbert [:dholbert]]

Backed out part 2:
 https://hg.mozilla.org/integration/mozilla-inbound/rev/e158b7448622
for build bustage on Static Analysis and B2G Desktop Windows Opt builds:
 https://tbpl.mozilla.org/php/getParsedLog.php?id=36296119&tree=Mozilla-Inbound
 https://tbpl.mozilla.org/php/getParsedLog.php?id=36296251&tree=Mozilla-Inbound

Comment 12

[Daniel Holbert [:dholbert]]

And Linux Debug bustage, too:
 https://tbpl.mozilla.org/php/getParsedLog.php?id=36296529&tree=Mozilla-Inbound
(though successful builds on Mac. I probably had no problems locally because I'm using Clang instead of gcc [like our mac builders].)

Comment 13

[Daniel Holbert [:dholbert]]

(ah, looks like the build error only happens in non-unified builds, actually.)

Comment 14

[Mats Palmgren (inactive)]

The #include "mozilla/LinkedList.h" needs to be in the header?

Comment 15

[Daniel Holbert [:dholbert]]

Nope -- it looks like I just needed "using namespace mozilla;" (which unified builds were helpfully providing to me via some other .cpp file).

Will re-land with that fixed at some point after the tree reopens.

Comment 16

[Daniel Holbert [:dholbert]]

Re-landed:  https://hg.mozilla.org/integration/mozilla-inbound/rev/cd28787bf390

Comment 17

[Daniel Holbert [:dholbert]]

Pushed a bustage fix to address some static-analysis-only bustage, for MOZ_STACK_CLASS being in the wrong position:
 https://hg.mozilla.org/integration/mozilla-inbound/rev/ade1c02d9793

(I had MOZ_STACK_CLASS after the classname (which is where some other keywords like MOZ_FINAL belong), but it turns out MOZ_STACK_CLASS needs to go before the class name.  This only affects static-analysis builds, because those are the only builds where this macro evaluates to anything.)

Comment 18

[Phil Ringnalda (:philor)]

https://hg.mozilla.org/mozilla-central/rev/850dd9773e9d

Comment 19

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

https://hg.mozilla.org/mozilla-central/rev/cd28787bf390
https://hg.mozilla.org/mozilla-central/rev/ade1c02d9793