Update styleRecalc so that it traverses shadow insertion points in 2 pass algorithms

According to the new distribution algorithms, a child node of a shadow insertion point can be a descendant of (a parent of) a content insertion point in the render tree. Therefore, when recalculating style, we must traverse shadow trees in the following order:

1. Traverse shadow trees from the youngest to the oldest as usual, but we must skip a shadow insertion point in each shadow tree.

2. After that, traverse each subtree rooted by a shadow insertion point in each shadow tree, from the oldest to the youngest.

This order guarantees that a child node of shadow insertion point in the younger shadow root is visited after a content insertion point in the older shadow root.
(*1) http://w3c.github.io/webcomponents/spec/shadow/#distribution-algorithms


BUG=317895

[hayato, 2013-11-20 08:36:08]

PTAL.

[esprehn, 2013-11-20 09:21:09]

This doesn't appear correct, if you don't set that then if I change the parent
style of the insertion point what will make sure the distributed nodes go
through a recalc?

ex.

<div>
  <content></content>
</div>

and then later

div.style.color = 'red';

That has to work in all cases. We might need to rethink this algorithm if it
violates the fundamental structure of recalcStyle where an older shadow root can
require an earlier shadowRoot to have gone through a recalc. Note that this
creates a cycle, the older shadow root needs the newer one to have been through
a recalc for it to attach properly, but the old one needs to have been through a
recalc so the new one's <shadow> element knows if the children need to go
through a recalc.

All of style recalc would need to be over the composed tree for this to work,
but that's likely a huge perf regression.

[esprehn, 2013-11-20 09:22:23]

https://codereview.chromium.org/77863002/diff/1/LayoutTests/fast/dom/shadow/s...
File LayoutTests/fast/dom/shadow/shadow-element-add-child-dynamically.html
(right):

https://codereview.chromium.org/77863002/diff/1/LayoutTests/fast/dom/shadow/s...
LayoutTests/fast/dom/shadow/shadow-element-add-child-dynamically.html:25:
setTimeout(addChild, 0);
Why setTimeout? Are you assuming that a recalcStyle happened between? There's no
guarantee that will happen and this test will be flakily testing the thing you
want it to test. You should touch offsetTop of something or use getComputedStyle
to trigger a recalc and not make this an async test.

[hayato, 2013-11-20 11:09:42]

On 2013/11/20 09:21:09, esprehn wrote:
> This doesn't appear correct, if you don't set that then if I change the parent
> style of the insertion point what will make sure the distributed nodes go
> through a recalc?
> 
> ex.
> 
> <div>
>   <content></content>
> </div>
> 
> and then later
> 
> div.style.color = 'red';
> 
> That has to work in all cases. We might need to rethink this algorithm if it
> violates the fundamental structure of recalcStyle where an older shadow root
can
> require an earlier shadowRoot to have gone through a recalc. Note that this
> creates a cycle, the older shadow root needs the newer one to have been
through
> a recalc for it to attach properly, but the old one needs to have been through
a
> recalc so the new one's <shadow> element knows if the children need to go
> through a recalc.
> 
> All of style recalc would need to be over the composed tree for this to work,
> but that's likely a huge perf regression.

A very good point. Now I am sure this is a serious issue for us.

I am feeling that we should use 2-pass algorithms also in recalcStyle. i. e.
From the youngest to the oldest, then from the oldest to youngest, as I did in
calculating distribution results. Let me try that tomorrow.

[hayato, 2013-11-25 04:47:18]

Let me tackle this issue in the next week (Dec 1 - ).

[hayato, 2013-12-10 06:54:06]

I've updated styleRecalc so that it traverses shadow trees in 2 pass algorithm.

Could you review this?

[esprehn, 2013-12-11 09:53:27]

This doesn't handle ::attach properly, you need the same two pass stuff there
too. :(

I sent an email to parkour@ about this also btw.

https://codereview.chromium.org/77863002/diff/100001/Source/core/dom/Element.cpp
File Source/core/dom/Element.cpp (right):

https://codereview.chromium.org/77863002/diff/100001/Source/core/dom/Element....
Source/core/dom/Element.cpp:1617: if ((change >= Inherit && change < Reattach)
|| insertionPoint->childNeedsStyleRecalc())
if (shouldRecalcStyle(change, insertionPoint))

We cannot even get in here with a Reattach change, see the check in
Element::recalcStyle.

https://codereview.chromium.org/77863002/diff/100001/Source/core/dom/Element....
Source/core/dom/Element.cpp:1618: insertionPoint->recalcChildStyle(change, 0);
This doesn't work, the bloom filter is wrong at this point so some selectors
will not match. The only way to make this work is to do
markAncestorsWithChildNeedsStyleRecalc() on the insertionPoint and then call
recalcStyle() on the ShadowRoot again.

https://codereview.chromium.org/77863002/diff/100001/Source/core/dom/Element....
Source/core/dom/Element.cpp:1619: insertionPoint->clearChildNeedsStyleRecalc();
If you make the above change this goes away.

https://codereview.chromium.org/77863002/diff/100001/Source/core/dom/Element.h
File Source/core/dom/Element.h (right):

https://codereview.chromium.org/77863002/diff/100001/Source/core/dom/Element....
Source/core/dom/Element.h:579: void recalcChildStyle(StyleRecalcChange,
InsertionPoint* shadowInsertionPoint);
= 0, so you don't need to pass it below.

[hayato, 2013-12-11 11:16:10]

On 2013/12/11 09:53:27, esprehn wrote:
> This doesn't handle ::attach properly, you need the same two pass stuff there
> too. :(
> 
> I sent an email to parkour@ about this also btw.

Ops. I didn't notice the email. Let me re-think again tomorrow.