Bug 119061 – Setting up OrderIterator shouldn't require an extra Vector

• Status: RESOLVED
• Resolution: FIXED
• Component: Layout and Rendering

[Ryosuke Niwa]

Consider merging https://chromium.googlesource.com/chromium/blink/+/55ebfdcea9f07cba9887ffd1494c2968def48a97
or come up with a better fix.

This change reuses the OrderIterator's Vector for fun and profit.
The idea is to have an helper class OrderIteratorPopulator, used for
manipulating the Vector directly.

The helper class has the nice upside of consolidating the code into a
single implementation across flexbox and grid.

Also tweaked the Vector to have an inline capacity for a single entry
that will cover the common case.

[Ryosuke Niwa]

Also see https://chromium.googlesource.com/chromium/blink/+/bff4f889e1e3f97952fca3a9464212e887ccb0db

[Ryosuke Niwa]

Also https://src.chromium.org/viewvc/blink?revision=154445&view=revision
and
https://chromium.googlesource.com/chromium/blink/+/336cf4c90ae5dd5759f5c1aea09b568461bcb856

[Manuel Rego Casasnovas]

Created attachment 228336 [details]
Patch

This is a patch merging https://src.chromium.org/viewvc/blink?revision=153971&view=revision and https://src.chromium.org/viewvc/blink?revision=158388&view=revision from Blink. As the other changes were finally reverted there.

[Manuel Rego Casasnovas]

Created attachment 228537 [details]
Patch

I've realized that std::set is not used in WebKit, so I think it's better to go step by step and this first patch will only port https://src.chromium.org/viewvc/blink?revision=153971&view=revision from Blink. Further improvements could be done in later patches.

[Manuel Rego Casasnovas]

Created attachment 228585 [details]
Patch

This is a different approach partially based on Blink r153971.\n\nThe idea is to avoid the extra loops in OrderIterator for each different order value. It has some minor performance impact in the grid tests, however it drastically improves the performance if you use different order values.\nOn top of that, OrderIterator code is simplified.

[Manuel Rego Casasnovas]

Created attachment 230107 [details]
Patch

Remove unneeded initialization of OrderIterator using default constructor.

[Darin Adler]

Comment on attachment 230107 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=230107&action=review

Looks good. review- because of the use of an iterator rather than an index for m_childrenIterator.

> Source/WebCore/rendering/OrderIterator.cpp:59
> +static bool sortByOrderValueAndIndex(ChildIndex childIndex1, const ChildIndex childIndex2)

The const here is neither needed nor helpful.

I don’t think the name “sort” is good for a less-than function. Maybe “compareBy” or “isLessThanBy”?

> Source/WebCore/rendering/OrderIterator.cpp:74
> +    m_iterator.m_children.append(std::make_pair(&child, m_childIndex++));

No need for make_pair any more, can just use braces in C++11:

    m_iterator.m_children.append({ &child, m_childIndex++ });

> Source/WebCore/rendering/OrderIterator.h:42
> +typedef std::pair<RenderBox*, int> ChildIndex;

Seems a little overkill to typedef this. Also the name is too broad. ChildIndex doesn’t give a rendering context, or even an OrderIterator context.

> Source/WebCore/rendering/OrderIterator.h:44
>  class OrderIterator {

This name also seems to broad. I think OrderedRendererChildIterator would be better, or some other name like this.

> Source/WebCore/rendering/OrderIterator.h:55
> +    typedef Vector<ChildIndex> ChildrenVector;

No need for a typedef here.

> Source/WebCore/rendering/OrderIterator.h:57
> +    ChildrenVector::const_iterator m_childrenIterator;

Should use an index, not an iterator, to track a position within a vector. It’s especially dangerous to have this if there’s any chance m_children might be modified while the iterator is around, since the vector memory can be reallocated.

[Manuel Rego Casasnovas]

(In reply to comment #7)
> (From update of attachment 230107 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=230107&action=review
> 
> Looks good. review- because of the use of an iterator rather than an index for m_childrenIterator.

Thanks for the review. I'm uploading a new patch following your suggestions.

> > Source/WebCore/rendering/OrderIterator.h:44
> >  class OrderIterator {
> 
> This name also seems to broad. I think OrderedRendererChildIterator would be better, or some other name like this.

I think we can leave this change for a later patch to avoid mixing the rename with this change.

[Manuel Rego Casasnovas]

Created attachment 230172 [details]
Patch

[WebKit Commit Bot]

Comment on attachment 230172 [details]
Patch

Clearing flags on attachment: 230172

Committed r167879: <http://trac.webkit.org/changeset/167879>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.

[Manuel Rego Casasnovas]

This patch introduces a regression in RenderFlexibleBox that is being managed at bug #132337 (with patch included).

[WebKit Commit Bot]

Re-opened since this is blocked by bug 132408

[Manuel Rego Casasnovas]

I forgot to note down the bug that leads me to rollout this change. It was bug #132400 which I didn't manage to reproduce in GTK+ port yet, but I'll keep taking a look.

[Manuel Rego Casasnovas]

(In reply to comment #14)
> I forgot to note down the bug that leads me to rollout this change. It was bug #132400 which I didn't manage to reproduce in GTK+ port yet, but I'll keep taking a look.

Maybe the problem is that we're not adding/removing new children from OrderIterator.
In addition, knowing that we're using a Vector of pairs it won't be easy/cheap to keep it updated.

So I think that as initial step we could only port the Blink change that will allow us to share code between grids and flexboxes:
https://src.chromium.org/viewvc/blink?revision=153971&view=revision

[Manuel Rego Casasnovas]

Created attachment 232071 [details]
Patch

New patch sharing code between RenderFlexibleBox and RenderGrid.

[Darin Adler]

Comment on attachment 232071 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=232071&action=review

> Source/WebCore/rendering/OrderIterator.cpp:94
> +    OrderIterator::OrderValues& orderValues = m_iterator.m_orderValues;

I suggest auto& here.

> Source/WebCore/rendering/OrderIterator.h:46
> +    OrderIterator(RenderBox&);

Should mark this explicit.

> Source/WebCore/rendering/OrderIterator.h:58
> +    typedef Vector<int, 1> OrderValues;

I don’t think we need a typedef for this. The only places that would use this type should just use auto instead.

> Source/WebCore/rendering/OrderIterator.h:73
> +    OrderIteratorPopulator(OrderIterator& iterator)
> +        : m_iterator(iterator)
> +    {
> +        // Note that we don't release the memory here, we only invalidate the size
> +        // This avoids unneeded reallocation if the size ends up not changing.
> +        m_iterator.m_orderValues.shrink(0);
> +    }
> +
> +    ~OrderIteratorPopulator();

I’m not sure I understand why the constructor is inlined and included here in the header but none of the other functions are. It would be nice to be consistent. Maybe no inlining is the right way to start.

> Source/WebCore/rendering/OrderIterator.h:78
> +

Please omit this blank line.

[Manuel Rego Casasnovas]

Created attachment 232094 [details]
Patch for landing.

[WebKit Commit Bot]

Comment on attachment 232094 [details]
Patch for landing.

Clearing flags on attachment: 232094

Committed r169372: <http://trac.webkit.org/changeset/169372>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.