1623225 - Store FlexItems and FlexLines in nsTArrays instead of linked lists

Status: RESOLVED FIXED

(Core :: Layout: Flexbox, task)

Description

[Ting-Yu Lin [:TYLin] (PST, UTC-8)]

In this bug, I'd like to revert the decision made in bug 983434, and to store FlexItems and FlexLines in nsTArrays instead of linked lists. Also since inserting elements at the start of an array is inefficient, I'll also request eAllowBottomToTopChildOrdering to stop FlexItem and FlexLines from being stored in the reverse order. I'll use the example in bug 983427 to explain why storing the line and items in reversed order might not be needed to implement flex item fragmentation.

Before performing the final reflow of all the flex items a single-line column container, we've already determined each flex item's position and size as if they are not in a pagination environment. Hence each flex item will be reflow at its designated position across in the page/column. So, even if the flex item ABCD is reflow first, its available block-size is from its block-axis position to the flex container's content block-end.

 +-----+
 |+---+|
 ||E F||
 ||G H||
 |+---+|
 |+---+|
 ||A B||
 ||C D||
 |+---+|
 +-----+

  PAGE1       PAGE2
 +-----+     |     |
 |+---+|     ||C D||
 ||E F||     |+---+|
 ||G H||     +-----+
 |+---+|
 |+---+| <-- item ABCD's available block-size starts here
 ||A B||

If in the end, it is necessary to reflow the child from top to bottom, we can always traverse the FlexLines and FlexItems backward.

Comment 1

[Ting-Yu Lin [:TYLin] (PST, UTC-8)]

Attachment: Bug 1623225 Part 1 - Use nsFlexLine::NumItems() to replace all the read-only direct usages of mNumItems.

In the next part, we are going to change nsFlexLine::mItems to store in
nsTArray and remove mNumItems.

Comment 2

[Ting-Yu Lin [:TYLin] (PST, UTC-8)]

Attachment: Bug 1623225 Part 2 - Convert AxisTrackerFlags to an enum class.

When eAllowBottomToTopChildOrdering flag is not requested, we reverse
axes internally when the flex items are positioned from bottom to top.
This makes FlexLines or FlexItems to be inserted at the front of their
data structures when they are generated.

In the next parts, we will store FlexLines and FlexItems in nsTArray
instead of LinkedList, and it makes inserting elements at front very
expensive. Since we haven't implemented flex item fragmentation yet, and
eAllowBottomToTopChildOrdering might not needed, we can use the
eAllowBottomToTopChildOrdering to avoid the expensive path on
non-fragmenting flex layout for now.

If eAllowBottomToTopChildOrdering turns out to be needed in fragmenting
the flex items, we can either traverse FlexLines and FlexItems
backwards, or drop eAllowBottomToTopChildOrdering flag and fix the
performance impact by reversing the order of FlexLines and FlexItems
after they are fully constructed.

Depends on D67262

Comment 3

[Ting-Yu Lin [:TYLin] (PST, UTC-8)]

Attachment: Bug 1623225 Part 3 - Store FlexItems in nsTArrays instead of LinkedLists.

Notable changes in this part.

• GetFirstItem() and GetLastItem() now returns a reference to the
  FlexItem (if such an item exists). The caller is required to test the
  FlexLine's emptiness before calling the two methods.

• Deploy range-based for-loop to iterate all FlexItem in a FlexLine via
  a new Items() method.

• The bookkeeping mNumItems is no longer needed as nsTArray::Length() is
  sufficient.

• Use "." instead "->" because we now store FlexItem in an nsTArray.

Depends on D67263

Comment 4

[Ting-Yu Lin [:TYLin] (PST, UTC-8)]

Attachment: Bug 1623225 Part 4 - Store FlexLines in nsTArrays instead of LinkedLists.

Depends on D67264

Comment 5

[Ting-Yu Lin [:TYLin] (PST, UTC-8)]

Attachment: Bug 1623225 Part 6 - Construct FlexItem directly at the end of FlexLine::Items().

Depends on D67265

Comment 6

[Ting-Yu Lin [:TYLin] (PST, UTC-8)]

Attachment: Bug 1623225 Part 5 - Reverse FlexLines and FlexItems if the axes are reversed internally.

Rather than inserting FlexLines and FlexItems at the front of the array,
which is inefficient, we reverse them after they are fully constructed.

nsTArray::Reverse() (or std::reverse()) is implemented by std::swap. To
make FlexItem swappable, i.e. FlexItem needs to be move-constructible
and move-assignable), we can simply drop all the const qualifiers for
all the member variables to have compiler generates move-constructor and
move-assignment operator.

Depends on D67265

Comment 7

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/8c7625b9f662
Part 1 - Use nsFlexLine::NumItems() to replace all the read-only direct usages of mNumItems. r=dholbert
https://hg.mozilla.org/integration/autoland/rev/c4a6b45ed12c
Part 2 - Convert AxisTrackerFlags to an enum class. r=dholbert
https://hg.mozilla.org/integration/autoland/rev/b2365cff1862
Part 3 - Store FlexItems in nsTArrays instead of LinkedLists. r=dholbert
https://hg.mozilla.org/integration/autoland/rev/3b2a048639c3
Part 4 - Store FlexLines in nsTArrays instead of LinkedLists. r=dholbert
https://hg.mozilla.org/integration/autoland/rev/3928834326a7
Part 5 - Reverse FlexLines and FlexItems if the axes are reversed internally. r=dholbert
https://hg.mozilla.org/integration/autoland/rev/96ae6f058d3c
Part 6 - Construct FlexItem directly at the end of FlexLine::Items(). r=dholbert

Comment 8

[Stefan Hindli [:stefan_hindli]]

https://hg.mozilla.org/mozilla-central/rev/8c7625b9f662
https://hg.mozilla.org/mozilla-central/rev/c4a6b45ed12c
https://hg.mozilla.org/mozilla-central/rev/b2365cff1862
https://hg.mozilla.org/mozilla-central/rev/3b2a048639c3
https://hg.mozilla.org/mozilla-central/rev/3928834326a7
https://hg.mozilla.org/mozilla-central/rev/96ae6f058d3c

Comment 9

[Jens Hausdorf :jens1o [ni? me]]

Is this connected to performance or memory-usage improvements?

Comment 10

[Ting-Yu Lin [:TYLin] (PST, UTC-8)]

(In reply to Jens Hausdorf :jens1o [ni? me] from comment #9)

Is this connected to performance or memory-usage improvements?

This bug is not fixed with performance or memory-usage in mind, although in general accessing elements in an nsTArray could be a bit faster than in a linked-list. FlexItem and FlexLine were originally stored in the arrays, and changed to store in linked-list in bug 983434. This reverts the design.