Use invalidation sets for nth invalidations.

Use invalidation sets for nth invalidations.

Invalidate siblings of inserted/removed elements for :nth type changes
by scheduling a descendant invalidation set on the parent node of the
inserted element.

There is currently one such set for all structural pseudo classes with
the exception of :first-child, :last-child, and :only-child, which have
their own sets and may have so since they can't affect arbitrary
siblings.

The descendant set never has invalidatesSelf since it's scheduled on
the parent node of where the actual change happens.

Structural pseudo classes in the righmost compound adds rightmost
compound features to the descendant set:

  .a:nth-child(3n) {} => adds ".a" to the descendant set.

Righmost compound structural pseudo classes where there are no other
features makes the descendant set have wholeSubtreeInvalid since all
siblings where the mutation happens have to be invalidated:

  :nth-child(3n) {} => setWholeSubtreeInvalid()

Sibling selectors turns into descendant features:

  :nth-child(3n) + .a {} => adds ".a" to the descendant set.

Descendant selectors causes features to be added as normal:

  :nth-child(3n) .a {} => adds ".a" to the descendant set.

This approach isn't super optimal since having a rightmost structural
pseudo without other features in the compound will cause nth-
invalidations to still be full subtree invalidations, but it should be
a good first iteration.

What we could do is something along the lines of what sibling
invalidations do where they have a maximum number of siblings a set
applies to. The nth-invalidation where the pseudo is in the rightmost
compound really needs to invalidation all siblings and not their
descendants. We could have some notion of removing descendant sets
which should no longer apply walking down the tree.

Traversing siblings scheduling invalidation sets on them was not chosen
for the same reason we schedule siblings invalidations as descendant
invalidations on the parent node for sibling mutations already.

R=esprehn@chromium.org,ericwilligers@chromium.org
BUG=624277
Committed: https://crrev.com/1ba555726fbc99f2eb999a97a69c728b31ca1cc5
Cr-Commit-Position: refs/heads/master@{#411647}

[rune, 2016-08-10 12:48:38]

Description was changed from

==========
Use invalidation sets for nth invalidations.

Invalidate siblings of inserted/removed elements for :nth type changes
by scheduling a descendant invalidation set on the parent node of the
inserted element.

There is currently one such set for all structural pseudo classes with
the exception of :first-child, :last-child, and :only-child, which have
their own sets and may have so since they can't affect arbitrary
siblings.

The descendant set never has invalidatesSelf since it's scheduled on
the parent node of where the actual change happens.

Structural pseudo classes in the righmost compound adds rightmost
compound features to the descendant set:

  .a:nth-child(3n) {} => adds ".a" to the descendant set.

Righmost compound structural pseudo classes where there are no other
features makes the descendant set have wholeSubtreeInvalid since all
siblings where the mutation happens have to be invalidated:

  :nth-child(3n) {} => setWholeSubtreeInvalid()

Sibling selectors turns into descendant features:

  :nth-child(3n) + .a {} => adds ".a" to the descendant set.

Descendant selectors causes features to be added as normal:

  :nth-child(3d) .a {} => adds ".a" to the descendant set.

This approach isn't super optimal since having a rightmost structural
pseudo without other features in the compound will cause nth-
invalidations to still be full subtree invalidations, but it should be
a good first iteration.

What we could do is something along the lines of what sibling
invalidations do where they have a maximum number of siblings a set
applies to. The nth-invalidation where the pseudo is in the rightmost
compound really needs to invalidation all siblings and not their
descendants. We could have some notion of removing descendant sets
which should no longer apply walking down the tree.

Traversing siblings scheduling invalidation sets on them was not chosen
for the same reason we schedule siblings invalidations as descendant
invalidations on the parent node for sibling mutations already.

R=esprehn@chromium.org,ericwilligers@chromium.org
BUG=624277
==========

to

==========
Use invalidation sets for nth invalidations.

Invalidate siblings of inserted/removed elements for :nth type changes
by scheduling a descendant invalidation set on the parent node of the
inserted element.

There is currently one such set for all structural pseudo classes with
the exception of :first-child, :last-child, and :only-child, which have
their own sets and may have so since they can't affect arbitrary
siblings.

The descendant set never has invalidatesSelf since it's scheduled on
the parent node of where the actual change happens.

Structural pseudo classes in the righmost compound adds rightmost
compound features to the descendant set:

  .a:nth-child(3n) {} => adds ".a" to the descendant set.

Righmost compound structural pseudo classes where there are no other
features makes the descendant set have wholeSubtreeInvalid since all
siblings where the mutation happens have to be invalidated:

  :nth-child(3n) {} => setWholeSubtreeInvalid()

Sibling selectors turns into descendant features:

  :nth-child(3n) + .a {} => adds ".a" to the descendant set.

Descendant selectors causes features to be added as normal:

  :nth-child(3n) .a {} => adds ".a" to the descendant set.

This approach isn't super optimal since having a rightmost structural
pseudo without other features in the compound will cause nth-
invalidations to still be full subtree invalidations, but it should be
a good first iteration.

What we could do is something along the lines of what sibling
invalidations do where they have a maximum number of siblings a set
applies to. The nth-invalidation where the pseudo is in the rightmost
compound really needs to invalidation all siblings and not their
descendants. We could have some notion of removing descendant sets
which should no longer apply walking down the tree.

Traversing siblings scheduling invalidation sets on them was not chosen
for the same reason we schedule siblings invalidations as descendant
invalidations on the parent node for sibling mutations already.

R=esprehn@chromium.org,ericwilligers@chromium.org
BUG=624277
==========

[rune, 2016-08-10 12:48:54]

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

[commit-bot: I haz the power, 2016-08-10 12:49:12]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-08-10 15:00:45]

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

[commit-bot: I haz the power, 2016-08-10 15:00:46]

Dry run: This issue passed the CQ dry run.

[rune, 2016-08-10 16:06:21]

ptal

[esprehn, 2016-08-11 09:44:25]

Hmm, I wonder if we should just add another bit that means "just children"
instead of "whole subtree" since we only need to go one level down?

[rune, 2016-08-11 10:13:36]

On 2016/08/11 09:44:25, esprehn wrote:
> Hmm, I wonder if we should just add another bit that means "just children"
> instead of "whole subtree" since we only need to go one level down?

Yes, that sounds like a plan. Do you want me to do that as part of this CL?

[esprehn, 2016-08-11 10:32:55]

I'll admit the extractInvalidationSetFeatures code is making less and less sense
to me, I think we probably want to try refactoring this into smaller functions
and writing a bunch of comments or something. :/

lgtm since this seems strictly better than the SubtreeStyleChange we used to do.

https://codereview.chromium.org/2235723002/diff/1/third_party/WebKit/Source/c...
File third_party/WebKit/Source/core/css/RuleFeature.cpp (right):

https://codereview.chromium.org/2235723002/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/css/RuleFeature.cpp:474:
m_nthInvalidationSet->setWholeSubtreeInvalid();
If we're going to mark it for the whole subtree why bother doing
addFeaturesToInvalidationSet?

I have to admit this foundFeatures flag is very confusing since the function
returns false in some cases that seem like they found features:
https://cs.chromium.org/chromium/src/third_party/WebKit/Source/core/css/RuleF...

why do all the other cases return true but ::before/::after return false? I
maybe that needs a comment?

I also wonder if foundFeatures should be a computed getter on the features
object instead that's like

bool hasFoo() const {
  return !m_foo.isEmpty() || !m_bar.isEmpty() || ...;
}

and then add a comment about it instead of this |= dance.

[esprehn, 2016-08-11 10:33:07]

On 2016/08/11 at 10:13:36, rune wrote:
> On 2016/08/11 09:44:25, esprehn wrote:
> > Hmm, I wonder if we should just add another bit that means "just children"
> > instead of "whole subtree" since we only need to go one level down?
> 
> Yes, that sounds like a plan. Do you want me to do that as part of this CL?

Nah, lets do that next.

[rune, 2016-08-12 11:03:14]

https://codereview.chromium.org/2235723002/diff/1/third_party/WebKit/Source/c...
File third_party/WebKit/Source/core/css/RuleFeature.cpp (right):

https://codereview.chromium.org/2235723002/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/css/RuleFeature.cpp:474:
m_nthInvalidationSet->setWholeSubtreeInvalid();
On 2016/08/11 10:32:55, esprehn wrote:
> If we're going to mark it for the whole subtree why bother doing
> addFeaturesToInvalidationSet?

Will fix.

> I have to admit this foundFeatures flag is very confusing since the function
> returns false in some cases that seem like they found features:
>
https://cs.chromium.org/chromium/src/third_party/WebKit/Source/core/css/RuleF...
> 
> why do all the other cases return true but ::before/::after return false? I
> maybe that needs a comment?

I'll comment. It's because ::before/::after are not invalidation set features,
but flags used to later create invalidation sets for attributes in content
properties: "content: attr(x)".

It would be less confusing is that was part of collectFeaturesFromSelector(),
yet that method is confusing in itself. We have two passes over the selectors.
One for invalidation sets and one for a few other flags. I've thought about
making it a single pass, but then it would be even more code into the extract..
and addFeaturesTo... methods.

> I also wonder if foundFeatures should be a computed getter on the features
> object instead that's like
> 
> bool hasFoo() const {
>   return !m_foo.isEmpty() || !m_bar.isEmpty() || ...;
> }
> 
> and then add a comment about it instead of this |= dance.

It's done like that because of the recursiveness for :-webkit-any. We pass the
same InvalidationSetFeatures to all sub-selectors and aggregate the features,
but we need to know if any of the sub-selectors were universal in the sense that
they didn't have any features. E.g.:

  #x  :-webkit-any(.a, *) {}

Extracting features from the first sub-selector adds ".a", but since we didn't
find any features in "*", we need to do a subtree recalc for #x changes.

The alternative is to use a separate InvalidationSetFeatures object for each
sub-selectors and aggregate them after we've set the wholeSubtreeInvalid flag
for the sub-selector.

[rune, 2016-08-12 11:03:46]

On 2016/08/11 10:32:55, esprehn wrote:
> I'll admit the extractInvalidationSetFeatures code is making less and less
sense
> to me, I think we probably want to try refactoring this into smaller functions
> and writing a bunch of comments or something. :/

Agree.

[rune, 2016-08-12 11:46:13]

The CQ bit was checked by rune@opera.com

[rune, 2016-08-12 11:46:13]

The patchset sent to the CQ was uploaded after l-g-t-m from esprehn@chromium.org
Link to the patchset: https://codereview.chromium.org/2235723002/#ps60001
(title: "Comment ::before/::after")

[commit-bot: I haz the power, 2016-08-12 11:46:29]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-08-12 13:07:58]

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

[commit-bot: I haz the power, 2016-08-12 13:07:59]

Try jobs failed on following builders:
  linux_android_rel_ng on master.tryserver.chromium.android (JOB_FAILED,
https://build.chromium.org/p/tryserver.chromium.android/builders/linux_androi...)

[rune, 2016-08-12 13:55:14]

The CQ bit was checked by rune@opera.com

[commit-bot: I haz the power, 2016-08-12 13:55:24]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-08-12 14:36:39]

Description was changed from

==========
Use invalidation sets for nth invalidations.

Invalidate siblings of inserted/removed elements for :nth type changes
by scheduling a descendant invalidation set on the parent node of the
inserted element.

There is currently one such set for all structural pseudo classes with
the exception of :first-child, :last-child, and :only-child, which have
their own sets and may have so since they can't affect arbitrary
siblings.

The descendant set never has invalidatesSelf since it's scheduled on
the parent node of where the actual change happens.

Structural pseudo classes in the righmost compound adds rightmost
compound features to the descendant set:

  .a:nth-child(3n) {} => adds ".a" to the descendant set.

Righmost compound structural pseudo classes where there are no other
features makes the descendant set have wholeSubtreeInvalid since all
siblings where the mutation happens have to be invalidated:

  :nth-child(3n) {} => setWholeSubtreeInvalid()

Sibling selectors turns into descendant features:

  :nth-child(3n) + .a {} => adds ".a" to the descendant set.

Descendant selectors causes features to be added as normal:

  :nth-child(3n) .a {} => adds ".a" to the descendant set.

This approach isn't super optimal since having a rightmost structural
pseudo without other features in the compound will cause nth-
invalidations to still be full subtree invalidations, but it should be
a good first iteration.

What we could do is something along the lines of what sibling
invalidations do where they have a maximum number of siblings a set
applies to. The nth-invalidation where the pseudo is in the rightmost
compound really needs to invalidation all siblings and not their
descendants. We could have some notion of removing descendant sets
which should no longer apply walking down the tree.

Traversing siblings scheduling invalidation sets on them was not chosen
for the same reason we schedule siblings invalidations as descendant
invalidations on the parent node for sibling mutations already.

R=esprehn@chromium.org,ericwilligers@chromium.org
BUG=624277
==========

to

==========
Use invalidation sets for nth invalidations.

Invalidate siblings of inserted/removed elements for :nth type changes
by scheduling a descendant invalidation set on the parent node of the
inserted element.

There is currently one such set for all structural pseudo classes with
the exception of :first-child, :last-child, and :only-child, which have
their own sets and may have so since they can't affect arbitrary
siblings.

The descendant set never has invalidatesSelf since it's scheduled on
the parent node of where the actual change happens.

Structural pseudo classes in the righmost compound adds rightmost
compound features to the descendant set:

  .a:nth-child(3n) {} => adds ".a" to the descendant set.

Righmost compound structural pseudo classes where there are no other
features makes the descendant set have wholeSubtreeInvalid since all
siblings where the mutation happens have to be invalidated:

  :nth-child(3n) {} => setWholeSubtreeInvalid()

Sibling selectors turns into descendant features:

  :nth-child(3n) + .a {} => adds ".a" to the descendant set.

Descendant selectors causes features to be added as normal:

  :nth-child(3n) .a {} => adds ".a" to the descendant set.

This approach isn't super optimal since having a rightmost structural
pseudo without other features in the compound will cause nth-
invalidations to still be full subtree invalidations, but it should be
a good first iteration.

What we could do is something along the lines of what sibling
invalidations do where they have a maximum number of siblings a set
applies to. The nth-invalidation where the pseudo is in the rightmost
compound really needs to invalidation all siblings and not their
descendants. We could have some notion of removing descendant sets
which should no longer apply walking down the tree.

Traversing siblings scheduling invalidation sets on them was not chosen
for the same reason we schedule siblings invalidations as descendant
invalidations on the parent node for sibling mutations already.

R=esprehn@chromium.org,ericwilligers@chromium.org
BUG=624277
==========

[commit-bot: I haz the power, 2016-08-12 14:36:40]

Committed patchset #4 (id:60001)

[commit-bot: I haz the power, 2016-08-12 14:39:04]

Description was changed from

==========
Use invalidation sets for nth invalidations.

Invalidate siblings of inserted/removed elements for :nth type changes
by scheduling a descendant invalidation set on the parent node of the
inserted element.

There is currently one such set for all structural pseudo classes with
the exception of :first-child, :last-child, and :only-child, which have
their own sets and may have so since they can't affect arbitrary
siblings.

The descendant set never has invalidatesSelf since it's scheduled on
the parent node of where the actual change happens.

Structural pseudo classes in the righmost compound adds rightmost
compound features to the descendant set:

  .a:nth-child(3n) {} => adds ".a" to the descendant set.

Righmost compound structural pseudo classes where there are no other
features makes the descendant set have wholeSubtreeInvalid since all
siblings where the mutation happens have to be invalidated:

  :nth-child(3n) {} => setWholeSubtreeInvalid()

Sibling selectors turns into descendant features:

  :nth-child(3n) + .a {} => adds ".a" to the descendant set.

Descendant selectors causes features to be added as normal:

  :nth-child(3n) .a {} => adds ".a" to the descendant set.

This approach isn't super optimal since having a rightmost structural
pseudo without other features in the compound will cause nth-
invalidations to still be full subtree invalidations, but it should be
a good first iteration.

What we could do is something along the lines of what sibling
invalidations do where they have a maximum number of siblings a set
applies to. The nth-invalidation where the pseudo is in the rightmost
compound really needs to invalidation all siblings and not their
descendants. We could have some notion of removing descendant sets
which should no longer apply walking down the tree.

Traversing siblings scheduling invalidation sets on them was not chosen
for the same reason we schedule siblings invalidations as descendant
invalidations on the parent node for sibling mutations already.

R=esprehn@chromium.org,ericwilligers@chromium.org
BUG=624277
==========

to

==========
Use invalidation sets for nth invalidations.

Invalidate siblings of inserted/removed elements for :nth type changes
by scheduling a descendant invalidation set on the parent node of the
inserted element.

There is currently one such set for all structural pseudo classes with
the exception of :first-child, :last-child, and :only-child, which have
their own sets and may have so since they can't affect arbitrary
siblings.

The descendant set never has invalidatesSelf since it's scheduled on
the parent node of where the actual change happens.

Structural pseudo classes in the righmost compound adds rightmost
compound features to the descendant set:

  .a:nth-child(3n) {} => adds ".a" to the descendant set.

Righmost compound structural pseudo classes where there are no other
features makes the descendant set have wholeSubtreeInvalid since all
siblings where the mutation happens have to be invalidated:

  :nth-child(3n) {} => setWholeSubtreeInvalid()

Sibling selectors turns into descendant features:

  :nth-child(3n) + .a {} => adds ".a" to the descendant set.

Descendant selectors causes features to be added as normal:

  :nth-child(3n) .a {} => adds ".a" to the descendant set.

This approach isn't super optimal since having a rightmost structural
pseudo without other features in the compound will cause nth-
invalidations to still be full subtree invalidations, but it should be
a good first iteration.

What we could do is something along the lines of what sibling
invalidations do where they have a maximum number of siblings a set
applies to. The nth-invalidation where the pseudo is in the rightmost
compound really needs to invalidation all siblings and not their
descendants. We could have some notion of removing descendant sets
which should no longer apply walking down the tree.

Traversing siblings scheduling invalidation sets on them was not chosen
for the same reason we schedule siblings invalidations as descendant
invalidations on the parent node for sibling mutations already.

R=esprehn@chromium.org,ericwilligers@chromium.org
BUG=624277

Committed: https://crrev.com/1ba555726fbc99f2eb999a97a69c728b31ca1cc5
Cr-Commit-Position: refs/heads/master@{#411647}
==========

[commit-bot: I haz the power, 2016-08-12 14:39:05]

Patchset 4 (id:??) landed as
https://crrev.com/1ba555726fbc99f2eb999a97a69c728b31ca1cc5
Cr-Commit-Position: refs/heads/master@{#411647}

[Eric Willigers, 2016-08-13 01:00:05]

https://codereview.chromium.org/2235723002/diff/1/third_party/WebKit/LayoutTe...
File third_party/WebKit/LayoutTests/fast/css/invalidation/nth-pseudo.html
(right):

https://codereview.chromium.org/2235723002/diff/1/third_party/WebKit/LayoutTe...
third_party/WebKit/LayoutTests/fast/css/invalidation/nth-pseudo.html:59: },
"Prepending an element sibling should not affect :nth-last-child of succeeding
siblings.");
This test is about nth-child.

[rune, 2016-08-15 07:38:06]

On 2016/08/13 01:00:05, Eric Willigers wrote:
>
https://codereview.chromium.org/2235723002/diff/1/third_party/WebKit/LayoutTe...
> File third_party/WebKit/LayoutTests/fast/css/invalidation/nth-pseudo.html
> (right):
> 
>
https://codereview.chromium.org/2235723002/diff/1/third_party/WebKit/LayoutTe...
> third_party/WebKit/LayoutTests/fast/css/invalidation/nth-pseudo.html:59: },
> "Prepending an element sibling should not affect :nth-last-child of succeeding
> siblings.");
> This test is about nth-child.

Thanks for spotting that. Uploaded https://codereview.chromium.org/2242113002/