Schedule sibling invalidation sets for sibling insert/remove.

Schedule sibling invalidation sets for sibling insert/remove.

Invalidation sets have been used only for changes which do not alter the
tree structure, like changing id, class names, other attributes, and
pseudo states. For dom tree changes, style invalidation relies on attach
and detach of the layout tree for the inserted/removed element. For
subsequent siblings of inserted/removed elements, we have been marking
siblings for subtree recalc (when we know we have tried to match
adjacent combinators on one of the siblings before) based on the maximum
number of consecutive direct adjacent combinators or all subsequent
siblings for indirect adjacent combinators.

This CL starts using sibling invalidation sets on siblings instead of
doing subtree recalcs.

The following properties of invalidation sets affected how this first
implementation was done:

* Even though we invalidate descendants/siblings based on tag names, we
  don't have invalidation sets for tag names as elements do not change
  tag names dynamically. For inserted/removed elements, we could have
  used invalidation sets for tag names. Take the selector "div + span".
  If we remove a div we could have scheduled an invalidation set for div
  which invalidates a span sibling.

* Invalidation sets for simple selectors and their negated versions, for
  instance ".a" and ":not(.a)", share invalidation sets and they may do
  so because invalidation sets have been applied when they change. That
  is, "a" is either part of old or the new class attribute when the
  invalidation set needs to be scheduled. When removing/inserting
  elements, a selector like ":not(.a) + .b" will need to schedule a
  sibling for ".a" for all elements not having the class "a".

* Consider the selector "* + .a". We have to schedule a sibling
  invalidation for any inserted/removed element to invalidate a sibling
  with class "a". However, invalidation set construction has only
  created an invalidation set for ".a" with the invalidateSelf flag set.

For this CL, we create a single universal sibling invalidation set to
handle the cases above. In fact this CL only do sibling invalidations on
element insert/remove for id, class, and attribute in addition to
scheduling the universal sibling invalidation set. Also, we skip
selector lists (that is, :not() and :-webkit-any() as :host()
:host-context() and :slotted() never match when followed by an adjacent
combinator).

For the following set of selectors:

  :not(.a) + .b + .c
  #x:not(.a) + .d
  div + span
  :-webkit-any(.x) + .f .g

We end up with the following universal sibling invalidation set with the
descendant invalidation set, containing ".g", to the right.

  { .c, span, .f, invalidatesSelf } => { .g }

Note that if a compound contains both :not() and for instance an id
selector, we will not add it to the universal sibling invalidation set
as we can properly invalidate ".d" siblings above using the invalidation
set for "#x".


== Scheduling sibling invalidations

For changes not modifying the tree, we schedule sibling invalidation
sets on the changed element and invalidate the siblings with descendant
sets during the invalidation process. When removing an element, however,
the element is not left in the tree, so we need to associate the
invalidation set with another element.

Given these siblings and the rules ".b + .c" and ".a + .b":

  div.a div.b div.c

When we remove .b, we can schedule the invalidation set for .b on .a
instead as that will invalidate .c as expected. However, if we remove .a,
there is no preceding element to associate the invalidation set with.
Instead we can schedule the invalidation set on .c, but also at the same
time do the invalidation step for .c as the StyleInvalidator will start
invalidating for sibling sets on subsequent siblings of the scheduling
element.

Additionaly, we need to reschedule already scheduled sibling invalidation
sets for elements which are removed in order to not lose already
scheduled invalidation set which have not been through the invalidator.

== The effect on amazon.com

This CL gets rid of all post-page-load full recalcs before you start
interacting with the page. The full recalcs after you start interacting
needs to be investigated further.

BUG=542082

[rune, 2016-06-14 14:55:37]

The CQ bit was checked by rune@opera.com to run a CQ dry run

[commit-bot: I haz the power, 2016-06-14 14:55:54]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/2059163002/60001

[commit-bot: I haz the power, 2016-06-14 19:10:35]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-06-14 19:10:37]

Dry run: This issue passed the CQ dry run.

[esprehn, 2016-06-14 23:09:33]

Very cool patch, can you expand the change description to explain what this does
and the change it has on Amazon?

[rune, 2016-06-16 08:16:05]

Description was changed from

==========
Schedule sibling invalidation sets for sibling insert/remove.

BUG=542082
==========

to

==========
Schedule sibling invalidation sets for sibling insert/remove.

Invalidation sets have been used only for changes which do not alter the
tree structure, like changing id, class names, other attributes, and
pseudo states. For dom tree changes, style invalidation relies on attach
and detach of the layout tree for the inserted/removed element. For
subsequent siblings of inserted/removed elements, we have been marking
siblings for subtree recalc (when we know we have tried to match
adjacent combinators on one of the siblings before) based on the maximum
number of consecutive direct adjacent combinators or all subsequent
siblings for indirect adjacent combinators.

This CL starts using sibling invalidation sets on siblings instead of
doing subtree recalcs.

The following properties of invalidation sets affected how this first
implementation was done:

* Even though we invalidate descendants/siblings based on tag names, we
  don't have invalidation sets for tag names as elements do not change
  tag names dynamically. For inserted/removed elements, we could have
  used invalidation sets for tag names. Take the selector "div + span".
  If we remove a div we could have scheduled an invalidation set for div
  which invalidates a span sibling.

* Invalidation sets for simple selectors and their negated versions, for
  instance ".a" and ":not(.a)", share invalidation sets and they may do
  so because invalidation sets have been applied when they change. That
  is, "a" is either part of old or the new class attribute when the
  invalidation set needs to be scheduled. When removing/inserting
  elements, a selector like ":not(.a) + .b" will need to schedule a
  sibling for ".a" for all elements not having the class "a".

* Consider the selector "* + .a". We have to schedule a sibling
  invalidation for any inserted/removed element to invalidate a sibling
  with class "a". However, invalidation set construction has only
  created an invalidation set for ".a" with the invalidateSelf flag set.

For this CL, we create a single universal sibling invalidation set to
handle the cases above. In fact this CL only do sibling invalidations on
element insert/remove for id, class, and attribute in addition to
scheduling the universal sibling invalidation set. Also, we skip
selector lists (that is, :not() and :-webkit-any() as :host()
:host-context() and :slotted() never match when followed by an adjacent
combinator).

For the following set of selectors:

  :not(.a) + .b + .c
  #x:not(.a) + .d
  div + span
  :-webkit-any(.x) + .f .g

We end up with the following universal sibling invalidation set with the
descendant invalidation set, containing ".g", to the right.

  { .c, span, .f, invalidatesSelf } => { .g }

Note that if a compound contains both :not() and for instance an id
selector, we will not add it to the universal sibling invalidation set
as we can properly invalidate ".d" siblings above using the invalidation
set for "#x".


== Scheduling sibling invalidations

For changes not modifying the tree, we schedule sibling invalidation
sets on the changed element and invalidate the siblings with descendant
sets during the invalidation process. When removing an element, however,
the element is not left in the tree, so we need to associate the
invalidation set with another element.

Given these siblings and the rules ".b + .c" and ".a + .b":

  div.a div.b div.c

When we remove .b, we can schedule the invalidation set for .b on .a
instead as that will invalidate .c as expected. However, if we remove .a,
there is no preceding element to associate the invalidation set with.
Instead we can schedule the invalidation set on .c, but also at the same
time do the invalidation step for .c as the StyleInvalidator will start
invalidating for sibling sets on subsequent siblings of the scheduling
element.

Additionaly, we need to reschedule already scheduled sibling invalidation
sets for elements which are removed in order to not lose already
scheduled invalidation set which have not been through the invalidator.

== The effect on amazon.com

This CL gets rid of all post-page-load full recalcs before you start
interacting with the page. The full recalcs after you start interacting
needs to be investigated further.

BUG=542082
==========

[rune, 2016-06-16 08:16:34]

On 2016/06/14 23:09:33, esprehn wrote:
> Very cool patch, can you expand the change description to explain what this
does
> and the change it has on Amazon?

Done.

[rune, 2016-06-16 08:18:13]

rune@opera.com changed reviewers:
+ ericwilligers@chromium.org, esprehn@chromium.org

[Eric Willigers, 2016-06-21 10:17:12]

lgtm

https://codereview.chromium.org/2059163002/diff/60001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/css/RuleFeature.cpp (right):

https://codereview.chromium.org/2059163002/diff/60001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/css/RuleFeature.cpp:874:
universalSet.setInvalidatesSelf();
If this call is replaced with an empty statement (;), or the whole if statement
is replaced with an unconditional addFeaturesToInvalidationSet call, the style
invalidation layout tests still pass.

This suggests we might have a missing layout test.

[rune, 2016-06-22 09:00:19]

esprehn@: We discussed the potential n² problem for inserting n children with
the presence of indirect adjacent. That would not be a problem for appending n
children, but if they are all inserted at position 0, it would.

You mentioned scheduling descendant invalidation sets on the parent instead.
That wouldn't work out of the box if you don't have descendants after the
adjacent combinators. E.g.:

(1) .a ~ .b .c
(2) .a ~ .d

For (1) we could schedule the descendant invalidation set for the sibling
invalidation set on the parent and ".c" would be appropriately invalidated. For
(2) we have no descendant invalidation set containing ".d". So for the
invalidate self case we'd need to do some trickery.

esprehn@: do you think this issue is blocking this CL from landing?

https://codereview.chromium.org/2059163002/diff/60001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/css/RuleFeature.cpp (right):

https://codereview.chromium.org/2059163002/diff/60001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/css/RuleFeature.cpp:874:
universalSet.setInvalidatesSelf();
On 2016/06/21 10:17:12, Eric Willigers wrote:
> If this call is replaced with an empty statement (;), or the whole if
statement
> is replaced with an unconditional addFeaturesToInvalidationSet call, the style
> invalidation layout tests still pass.
> 
> This suggests we might have a missing layout test.

It's covered by the new unit tests. 4 failing tests with the mentioned change.

[esprehn, 2016-06-22 09:56:21]

I'll read through this tomorrow and see, I'm worried about the complexity and
the possible n^2. Can you explain why you don't have an invalidation set to
schedule? Any time you have one to schedule on a sibling you could have
scheduled one on the parent. What's the DOM look like in your example, what are
the rules, and what are the mutations you're doing? :)

[rune, 2016-06-22 10:50:12]

On 2016/06/22 09:56:21, esprehn wrote:
> I'll read through this tomorrow and see, I'm worried about the complexity and
> the possible n^2. Can you explain why you don't have an invalidation set to
> schedule? Any time you have one to schedule on a sibling you could have
> scheduled one on the parent. What's the DOM look like in your example, what
are
> the rules, and what are the mutations you're doing? :)

<!DOCTYPE html>
<style>
  .a ~ .b { color: green }
</style>
<div id="p">
  <div></div>
  <div></div>
  <div></div>
  <div class="b"></div>
</div>
<script>
  document.body.offsetTop;
  var newElm = document.createElement("div");
  newElm.setAttribute("class", "a");
  p.insertBefore(newElm, p.firstChild);
</script>

I have a sibling invalidation set for ".a" which has ".b" among its features
with an invalidatesSelf(). No descendant invalidation set. In order to
invalidate scheduling something on the parent, I need to turn the sibling
invalidation set into a descendant invalidation set somehow. If I have ".a ~ .b
.c", the sibling invalidation set for ".a" has a descendant invalidation set
containing ".c" which I can schedule on #p.

[rune, 2016-06-22 11:20:41]

On 2016/06/22 10:50:12, rune wrote:
> On 2016/06/22 09:56:21, esprehn wrote:
> > I'll read through this tomorrow and see, I'm worried about the complexity
and
> > the possible n^2. Can you explain why you don't have an invalidation set to
> > schedule? Any time you have one to schedule on a sibling you could have
> > scheduled one on the parent. What's the DOM look like in your example, what
> are
> > the rules, and what are the mutations you're doing? :)
> 
> <!DOCTYPE html>
> <style>
>   .a ~ .b { color: green }
> </style>
> <div id="p">
>   <div></div>
>   <div></div>
>   <div></div>
>   <div class="b"></div>
> </div>
> <script>
>   document.body.offsetTop;
>   var newElm = document.createElement("div");
>   newElm.setAttribute("class", "a");
>   p.insertBefore(newElm, p.firstChild);
> </script>
> 
> I have a sibling invalidation set for ".a" which has ".b" among its features
> with an invalidatesSelf(). No descendant invalidation set. In order to
> invalidate scheduling something on the parent, I need to turn the sibling
> invalidation set into a descendant invalidation set somehow. If I have ".a ~
.b
> .c", the sibling invalidation set for ".a" has a descendant invalidation set
> containing ".c" which I can schedule on #p.

Technically, this looks possible, albeit ugly, if we cast the
SiblingInvalidationSet to a DescendantInvalidationSet as
DescendantInvalidationSet does not add additional data members to the
InvalidationSet base class. The only problem I've found is the checked type
conversion in StyleInvalidator::RecursionData::pushInvalidationSet(). But, I
don't think we need that conversion. We can just use the InvalidationSet type
for that vector. I'll try out an alternative CL where I always schedule
invalidation sets on the parent (even for direct siblings) and see where we get.

[rune, 2016-06-22 12:26:23]

On 2016/06/22 11:20:41, rune wrote:
> Technically, this looks possible, albeit ugly, if we cast the
> SiblingInvalidationSet to a DescendantInvalidationSet as
> DescendantInvalidationSet does not add additional data members to the
> InvalidationSet base class. The only problem I've found is the checked type
> conversion in StyleInvalidator::RecursionData::pushInvalidationSet(). But, I
> don't think we need that conversion. We can just use the InvalidationSet type
> for that vector. I'll try out an alternative CL where I always schedule
> invalidation sets on the parent (even for direct siblings) and see where we
get.

Need to be able to schedule invalidation sets on ShadowRoots as well, but that
should be doable ...

[rune, 2016-06-22 23:23:19]

On 2016/06/22 12:26:23, rune wrote:
> On 2016/06/22 11:20:41, rune wrote:
> > Technically, this looks possible, albeit ugly, if we cast the
> > SiblingInvalidationSet to a DescendantInvalidationSet as
> > DescendantInvalidationSet does not add additional data members to the
> > InvalidationSet base class. The only problem I've found is the checked type
> > conversion in StyleInvalidator::RecursionData::pushInvalidationSet(). But, I
> > don't think we need that conversion. We can just use the InvalidationSet
type
> > for that vector. I'll try out an alternative CL where I always schedule
> > invalidation sets on the parent (even for direct siblings) and see where we
> get.
> 
> Need to be able to schedule invalidation sets on ShadowRoots as well, but that
> should be doable ...

Scheduling on parent attempt here: https://codereview.chromium.org/2089063005

[rune, 2016-07-01 10:58:12]

On 2016/06/22 23:23:19, rune wrote:
> On 2016/06/22 12:26:23, rune wrote:
> > On 2016/06/22 11:20:41, rune wrote:
> > > Technically, this looks possible, albeit ugly, if we cast the
> > > SiblingInvalidationSet to a DescendantInvalidationSet as
> > > DescendantInvalidationSet does not add additional data members to the
> > > InvalidationSet base class. The only problem I've found is the checked
type
> > > conversion in StyleInvalidator::RecursionData::pushInvalidationSet(). But,
I
> > > don't think we need that conversion. We can just use the InvalidationSet
> type
> > > for that vector. I'll try out an alternative CL where I always schedule
> > > invalidation sets on the parent (even for direct siblings) and see where
we
> > get.
> > 
> > Need to be able to schedule invalidation sets on ShadowRoots as well, but
that
> > should be doable ...
> 
> Scheduling on parent attempt here: https://codereview.chromium.org/2089063005

Closing as the alternative approach landed.