Ensure that positioned objects' list is always in parent first order

Ensure that positioned objects' list is always in parent first order

When a container's position attribute is changed 
(fixed->absolute or relative->absolute), the container's position 
in the list of positioned objects may appear after the position 
of its child, if this container also has a positioned child.
RenderBlock::layoutPositionedObjects()'s logic relies on "parent first" 
positioned object ordering. Wrong ordering could end up having
dirty children, after finishing layouting positioned objects.

Fix it by inserting the parent before the child,
instead of appending it to the end of the list.

Test debug build with some real content:
http://binged.it/K9uLcw
http://www.bing.com/maps/
http://www.nytimes.com (scroll down)
http://www.awwwards.com/22-experimental-webgl-demo-examples.html (scroll down)

Patch was developed by Zalan Bujtas  <zbujtas@gmail.com>;
see original bug https://bugs.webkit.org/show_bug.cgi?id=93891

BUG=407356, 416210, 351709, 144608

[alexanderk, 2015-01-27 08:47:56]

alexanderk@opera.com changed reviewers:
+ jchaffraix@chromium.org, zbujtas@gmail.com

[Krzysztof Olczyk, 2015-01-27 09:45:06]

kolczyk@opera.com changed reviewers:
+ chrishtr@chromium.org, fs@opera.com, jochen@chromium.org, kolczyk@opera.com,
mortens@opera.com, vollick@chromium.org

[Krzysztof Olczyk, 2015-01-27 09:45:06]

Hi jchaffraix, vollick, chrishtr,

could you please take a look at this patch which seems to fix the assert firing
in Blink for many live pages?

[fs, 2015-01-27 10:11:36]

fs@opera.com changed reviewers:
+ mstensho@opera.com
- mortens@opera.com

[fs, 2015-01-27 10:11:37]

s/mortens/mstensho/

[Julien - ping for review, 2015-01-27 14:47:45]

jchaffraix@chromium.org changed reviewers:
+ inferno@chromium.org, leviw@chromium.org
- chrishtr@chromium.org, jochen@chromium.org, vollick@chromium.org

[Julien - ping for review, 2015-01-27 14:47:46]

Removing some folks that are not working in rendering + adding folks who did the
original code review.

https://codereview.chromium.org/875563003/diff/1/Source/core/rendering/Render...
File Source/core/rendering/RenderBlock.cpp (right):

https://codereview.chromium.org/875563003/diff/1/Source/core/rendering/Render...
Source/core/rendering/RenderBlock.cpp:1955: if (box->isDescendantOf(descendant))
{
This check is expensive as it involves walking the tree up repeatedly (due to
the for loop).

This will be run for *every* layout, which is a show-stopper for me. Your
description mentions a precise situation(s) in which we could have this problem.
It seems to me that we should narrow this code for this case(s).

https://codereview.chromium.org/875563003/diff/1/Source/core/rendering/Render...
Source/core/rendering/RenderBlock.cpp:1962: descendantSet->add(descendant);
I think descendantSet->insertBefore() should be able to handle already added
nodes.

Thus we could write:

// Insert the descendant.
bool added = descendantSet->add(descendant).isNewEntry;

if (added) {
   ...
}

// We may need to change the order, e.g. if a containing block changed position.
// Try to find the right position for this case.
if (descendant->isRenderBlock()) {
    TrackedRendererListHashSet::iterator end = descendantSet->end();
    for (TrackedRendererListHashSet::iterator it = descendantSet->begin(); it !=
end; ++it) {
        RenderBox* box = *it;
        if (box->isDescendantOf(descendant)) {
            descendantSet->insertBefore(box, descendant);
            break;
        }
    }
}

Which seems more readable to me.

[leviw_travelin_and_unemployed, 2015-01-27 16:39:57]

On 2015/01/27 at 14:47:46, jchaffraix wrote:
> Removing some folks that are not working in rendering + adding folks who did
the original code review.
> 
>
https://codereview.chromium.org/875563003/diff/1/Source/core/rendering/Render...
> File Source/core/rendering/RenderBlock.cpp (right):
> 
>
https://codereview.chromium.org/875563003/diff/1/Source/core/rendering/Render...
> Source/core/rendering/RenderBlock.cpp:1955: if
(box->isDescendantOf(descendant)) {
> This check is expensive as it involves walking the tree up repeatedly (due to
the for loop).
> 
> This will be run for *every* layout, which is a show-stopper for me. Your
description mentions a precise situation(s) in which we could have this problem.
It seems to me that we should narrow this code for this case(s).
> 
>
https://codereview.chromium.org/875563003/diff/1/Source/core/rendering/Render...
> Source/core/rendering/RenderBlock.cpp:1962: descendantSet->add(descendant);
> I think descendantSet->insertBefore() should be able to handle already added
nodes.
> 
> Thus we could write:
> 
> // Insert the descendant.
> bool added = descendantSet->add(descendant).isNewEntry;
> 
> if (added) {
>    ...
> }
> 
> // We may need to change the order, e.g. if a containing block changed
position.
> // Try to find the right position for this case.
> if (descendant->isRenderBlock()) {
>     TrackedRendererListHashSet::iterator end = descendantSet->end();
>     for (TrackedRendererListHashSet::iterator it = descendantSet->begin(); it
!= end; ++it) {
>         RenderBox* box = *it;
>         if (box->isDescendantOf(descendant)) {
>             descendantSet->insertBefore(box, descendant);
>             break;
>         }
>     }
> }

^^^ CodeReview level: expert

> Which seems more readable to me.

[alexanderk, 2015-01-28 14:15:27]

https://chromiumcodereview.appspot.com/875563003/diff/1/Source/core/rendering...
File Source/core/rendering/RenderBlock.cpp (right):

https://chromiumcodereview.appspot.com/875563003/diff/1/Source/core/rendering...
Source/core/rendering/RenderBlock.cpp:1955: if (box->isDescendantOf(descendant))
{
On 2015/01/27 14:47:46, Julien Chaffraix - CET wrote:
> This check is expensive as it involves walking the tree up repeatedly (due to
> the for loop).
> 
> This will be run for *every* layout, which is a show-stopper for me. Your
> description mentions a precise situation(s) in which we could have this
problem.
> It seems to me that we should narrow this code for this case(s).

Right, isDescendantOf() is expensive.
And optimization is possible for this particular "remove and then append back"
case, but, as it turned out, we have some other cases when "parent first" order
is broken.
I will try to analyse these cases to minimize isDescendantOf() calls.

https://chromiumcodereview.appspot.com/875563003/diff/1/Source/core/rendering...
Source/core/rendering/RenderBlock.cpp:1962: descendantSet->add(descendant);
On 2015/01/27 14:47:46, Julien Chaffraix - CET wrote:
> I think descendantSet->insertBefore() should be able to handle already added
> nodes.
> 
> Thus we could write:
> 
> // Insert the descendant.
> bool added = descendantSet->add(descendant).isNewEntry;
> 
> if (added) {
>    ...
> }
> 
> // We may need to change the order, e.g. if a containing block changed
position.
> // Try to find the right position for this case.
> if (descendant->isRenderBlock()) {
>     TrackedRendererListHashSet::iterator end = descendantSet->end();
>     for (TrackedRendererListHashSet::iterator it = descendantSet->begin(); it
!=
> end; ++it) {
>         RenderBox* box = *it;
>         if (box->isDescendantOf(descendant)) {
>             descendantSet->insertBefore(box, descendant);
>             break;
>         }
>     }
> }
> 
> Which seems more readable to me.

Unfortunately insertBefore() does not move already added nodes.

[alexanderk, 2015-01-30 11:21:43]

Some notes regarding isDescendantOf expensiveness:

isDescendantOf is very simple and its time complexity is just the depth of
Render Tree 
which in turn is not big: cannot imagine it more than 100, in practice it is
usually less than 10.

bool RenderObject::isDescendantOf(const RenderObject* obj) const
{
    for (const RenderObject* r = this; r; r = r->m_parent) {
        if (r == obj)
            return true;
    }
    return false;
}

Time complexity added by isDescendantOf call is O(C * N * D) where
C - number of insertIntoTrackedRendererMaps effective calls
N - number of nodes in descendantSet (before "break")
D - already mentioned the depth of Render Tree

Usually the number of insertIntoTrackedRendererMaps effective is less than 1000,

but for some specific content it may be over 1000 while loading.
We have not so many "isOutOfFlowPositioned" objects in descendantSet,
usually less than 10, less than 100 is the worst case.
Thus the expected complexity should not be bigger than 100 000.
The worst case ~10 000 000 means 1s for 10 MOPS.

Some real data:

site			insertIntoTrackedRendererMaps effective calls
					isDescendantOf calls	
							isDescendantOf loops

nyt.com			998		1852		10402
myspace.com		728		291		2521
ebay.com		1036		497		6762
maps.google.com		243		473		5940
youtube.com		249		75		2116
sina.com.cn		556		172		1487
yahoo.com		121		61		992
cnn.com			241		62		600
en.wikipedia.org	30		67		357
amazon.com		203		30		350
taobao.com		65		22		312
bbc.com			82		13		123
qq.com			37		17		102
facebook.com		8		1		15

[alexanderk, 2015-01-30 13:27:55]

jchaffraix, I have considered your suggestions, but unfortunately they are not
applicable:

1) The idea to narrow down the code for this particular case resulted with wider
case: descendant may have children (in the list) and can be added first time, it
may not necessarily removed from the list previously, e.g. changing position
from "relative" to "absolute" (I will update TC). Thus to keep "parent first"
condition we always have to check hierarchy when inserting descendant.

2) As to readability improvement: we cannot add descendant first then move it in
the list, insertBefore() does not do that.

I have been trying to find some ways to avoid or minimize isDescendantOf calls
but could not come up with any better approach yet. So your advice for further
development is highly appreciated. Please also reconsider isDescendantOf taking
into account its real expensiveness (#10).

[alexanderk, 2015-02-05 12:36:39]

Hi jchaffraix, guys,

Could you please take a look at updated patch?
Now performance should be OK.

Thanks in advance

[mstensho (USE GERRIT), 2015-02-09 17:58:59]

We should be able to come up with a less intrusive fix (one that isn't in
generic code for tracked renderer maps, and also one that's executed only when
'position' changes).

I suspect that it's the code in RenderBlock::styleWillChange() that should be
changed. Maybe we could change it so that we call removePositionedObjects()
somehow, to get rid of everything under the renderer that gets its 'position'
changed. The current static vs. non-static checks there won't really do.

Also, what takes place at the end of
removeFloatingOrPositionedChildFromBlockLists() looks scary, when you keep in
mind that what you remove there may get re-inserted later (at the wrong place).

[mstensho (USE GERRIT), 2015-03-26 13:28:34]

Ping. Are you still interested in working on this or should the CL be closed?

[alexanderk, 2015-03-26 13:41:36]

On 2015/03/26 13:28:34, mstensho wrote:
> Ping. Are you still interested in working on this or should the CL be closed?

I have tried your idea about redesigning this positioned objects handling
(removePositionedObjects in RenderBlock::styleWillChange etc),
and it worked!, but had many side-effects.
Unfortunately I have no enough time to work on this now... maybe later.

[Julien - ping for review, 2015-03-26 15:46:07]

On 2015/03/26 at 13:41:36, alexanderk wrote:
> On 2015/03/26 13:28:34, mstensho wrote:
> > Ping. Are you still interested in working on this or should the CL be
closed?
> 
> I have tried your idea about redesigning this positioned objects handling
> (removePositionedObjects in RenderBlock::styleWillChange etc),
> and it worked!, but had many side-effects.
> Unfortunately I have no enough time to work on this now... maybe later.

Would you be willing to publish the WIP patch? I have been pointing people at
this CL as this is a pretty big cause of ASSERTs triggering so someone may jump
in to carry the torch forward.

[alexanderk, 2015-03-26 16:41:53]

On 2015/03/26 15:46:07, Julien Chaffraix - PST wrote:
> On 2015/03/26 at 13:41:36, alexanderk wrote:
> > On 2015/03/26 13:28:34, mstensho wrote:
> > > Ping. Are you still interested in working on this or should the CL be
> closed?
> > 
> > I have tried your idea about redesigning this positioned objects handling
> > (removePositionedObjects in RenderBlock::styleWillChange etc),
> > and it worked!, but had many side-effects.
> > Unfortunately I have no enough time to work on this now... maybe later.
> 
> Would you be willing to publish the WIP patch? I have been pointing people at
> this CL as this is a pretty big cause of ASSERTs triggering so someone may
jump
> in to carry the torch forward.

Sure, please see Patch Set 4

[eae, 2015-06-03 22:03:11]

Is anyone willing to take this and try to get it into a state where we could
land it?

[mstensho (USE GERRIT), 2015-06-04 06:12:22]

Sounds like something robhogan might enjoy. :)

[chrishtr, 2015-06-11 19:04:46]

On 2015/06/04 at 06:12:22, mstensho wrote:
> Sounds like something robhogan might enjoy. :)

I just hit this too.

[kojii, 2015-06-12 05:04:12]

Rebased to ToT at https://codereview.chromium.org/1181983002/, and I'll look
into further.