Implemented RuleSet diff for active stylesheets.

Implemented RuleSet diff for active stylesheets.

This is an implementation of the diffing of active stylesheets outlined
in [1] to replace the current compareStyleSheets method in
TreeScopeStyleSheetCollection which currently cause a "Reconstruct" if
you both have insertions and removals. With async stylesheet update we
will more likely end up in those situations as changes to the list can
happen in a batches.

An important new aspect here is that together with each stylesheet keep
a traced pointer to the RuleSet it had reference last time the active
stylesheet list was updated. That way we can figure out what changed on
media query and CSSOM changes.

The comparison algorithm works like this:

INPUTS: The new and old active stylesheet vectors
OUTPUTS: A vector of added and removed RuleSets.
         Also a return value saying if we only appended stylesheets at
         the end. Given that sheets were only appended we can do certain
         optimizations updating rule data.

* First linearly walk the old and new active list as long as the
  stylesheet pointers are the same. If the ruleset changed for the
  given sheet, add the old and new rulesets to the list of changed
  rulesets.

* If we are finished walking any of the active lists, we have either
  appended a set of sheets to the end, or we have removed a set from
  the tail. Add the added/removed rulesets to the changed list and we
  are finished.

* If we have remaining sheets in both the old and new active list,
  merge the remaining items from both lists and sort the merged vector
  on stylesheet pointers. For stylesheet pointers occuring in pairs, if
  the rulesets are different for the two entries, the ruleset changed
  so we add them to the changed list. For stylesheets which do not occur
  in pairs, they are either added or removed and we add the ruleset to
  the changed list.

The time complexity for the algorithm is O(k) for the common prefix
and the complexity for std::sort for the m + n remaining sheets in the
new and old active lists. Note that each scope has its active list, so
the larger n's will be for the document scope as shadow trees most
often have a single stylesheet (I measured a max of three running some
Polymer apps).

An assumption here is that we will do ensureRuleSet() including media
query evaluation for the media attribute as we collect active
stylesheets. Currently, the analysis of which elements needs a style
recalc happens synchronously while updating the active sheets while the
rulesets are (re-)created asynchronously/on-demand via
lazyAppendAuthorStyleSheets in StyleResolver. The idea is that since
the active stylesheet update will be async, we can drop the lazyAppend
things from StyleResolver and add the stylesheets directly to the
ScopedStyleResolvers during the active stylesheet update.

Creating the RuleSets as we collect active stylesheets means we have
invalidation sets readily available to use style invalidation to
trigger style recalcs only on elements affected by the added/removed
stylesheets.

[1] http://bit.ly/25uxtnU

R=esprehn@chromium.org,timloh@chromium.org
BUG=567021
Committed: https://crrev.com/f9d162281661e2fb8805814513a549683775d56b
Cr-Commit-Position: refs/heads/master@{#416520}

[rune, 2016-04-14 21:17:39]

I have implemented active stylesheet comparison as outlined in the design
document I sent to style-dev@chromium.org. I did this in a  file/method
disconnected from the rest of the code for now. I don't know if it should be an
ActiveStyleSheets class instead or simply replace the vector type in
StyleSheetCollection directly with the new one.

[rune, 2016-04-18 21:10:04]

Description was changed from

==========
Implemented RuleSet diff for active stylesheets.

*** NOT FOR LANDING ***

This is an implementation of the diffing of active stylesheets outlined
in [1] to replace the current compareStyleSheets method in
TreeScopeStyleSheetCollection which currently cause a "Reconstruct" if
you both have insertions and removals. With async stylesheet update we
will more likely end up in those situations as changes to the list can
happen in a batches.

An important new aspect here is that together with each stylesheet keep
a traced pointer to the RuleSet it had reference last time the active
stylesheet list was updated. That way we can figure out what changed on
media query and CSSOM changes.

The comparison algorithm works like this:

INPUTS: The new and old active stylesheet vectors
OUTPUTS: Two vectors of RuleSets, one for the added ones, and one for
         the removed ones.
         Also a return value saying if we only appended stylesheets at
         the end. Given that sheets were only appended we can do certain
         optimizations updating rule data.

* First linearly walk the old and new active list as long as the
  stylesheet pointers are the same. If the ruleset changed for the
  given sheet, add the old ruleset to the removed list and the new
  ruleset to the added list.

* If we are finished walking any of the active lists, we have either
  appended a set of sheets to the end, or we have removed a set from
  the tail. Add the added/removed rulesets to the corresponding output
  lists and we are finished.

* If we have remaining sheets in both the old and new active list,
  merge the remaining items from both lists and sort the merged vector
  on stylesheet pointers. For stylesheet pointers occuring in pairs, if
  the rulesets are different for the two entries are different, the
  ruleset changed so we add them to the added/removed lists. For
  stylesheets which do not occur in pairs, they are either added or
  removed and we add the ruleset to the corresponding list.

The time complexity for the algorithm is O(k) for the common prefix
and the complexity for std::sort for the m + n remaining sheets in the
new and old active lists. Note that each scope has its active list, so
the larger n's will be for the document scope as shadow trees most
often have a single stylesheet (I measured a max of three running some
Polymer apps).

An assumption here is that we will do ensureRuleSet() including media
query evaluation for the media attribute as we collect active
stylesheets. Currently, the analysis of which elements needs a style
recalc happens synchronously while updating the active sheets while the
rulesets are (re-)created asynchronously/on-demand via
lazyAppendAuthorStyleSheets in StyleResolver. The idea is that since
the active stylesheet update will be async, we can drop the lazyAppend
things from StyleResolver and add the stylesheets directly to the
ScopedStyleResolvers during the active stylesheet update.

Creating the RuleSets as we collect active stylesheets means we have
invalidation sets readily available to use style invalidation to
trigger style recalcs only on elements affected by the added/removed
stylesheets.

[1] http://bit.ly/25uxtnU

R=esprehn@chromium.org,timloh@chromium.org
BUG=567021
==========

to

==========
Implemented RuleSet diff for active stylesheets.

This is an implementation of the diffing of active stylesheets outlined
in [1] to replace the current compareStyleSheets method in
TreeScopeStyleSheetCollection which currently cause a "Reconstruct" if
you both have insertions and removals. With async stylesheet update we
will more likely end up in those situations as changes to the list can
happen in a batches.

An important new aspect here is that together with each stylesheet keep
a traced pointer to the RuleSet it had reference last time the active
stylesheet list was updated. That way we can figure out what changed on
media query and CSSOM changes.

The comparison algorithm works like this:

INPUTS: The new and old active stylesheet vectors
OUTPUTS: Two vectors of RuleSets, one for the added ones, and one for
         the removed ones.
         Also a return value saying if we only appended stylesheets at
         the end. Given that sheets were only appended we can do certain
         optimizations updating rule data.

* First linearly walk the old and new active list as long as the
  stylesheet pointers are the same. If the ruleset changed for the
  given sheet, add the old ruleset to the removed list and the new
  ruleset to the added list.

* If we are finished walking any of the active lists, we have either
  appended a set of sheets to the end, or we have removed a set from
  the tail. Add the added/removed rulesets to the corresponding output
  lists and we are finished.

* If we have remaining sheets in both the old and new active list,
  merge the remaining items from both lists and sort the merged vector
  on stylesheet pointers. For stylesheet pointers occuring in pairs, if
  the rulesets are different for the two entries are different, the
  ruleset changed so we add them to the added/removed lists. For
  stylesheets which do not occur in pairs, they are either added or
  removed and we add the ruleset to the corresponding list.

The time complexity for the algorithm is O(k) for the common prefix
and the complexity for std::sort for the m + n remaining sheets in the
new and old active lists. Note that each scope has its active list, so
the larger n's will be for the document scope as shadow trees most
often have a single stylesheet (I measured a max of three running some
Polymer apps).

An assumption here is that we will do ensureRuleSet() including media
query evaluation for the media attribute as we collect active
stylesheets. Currently, the analysis of which elements needs a style
recalc happens synchronously while updating the active sheets while the
rulesets are (re-)created asynchronously/on-demand via
lazyAppendAuthorStyleSheets in StyleResolver. The idea is that since
the active stylesheet update will be async, we can drop the lazyAppend
things from StyleResolver and add the stylesheets directly to the
ScopedStyleResolvers during the active stylesheet update.

Creating the RuleSets as we collect active stylesheets means we have
invalidation sets readily available to use style invalidation to
trigger style recalcs only on elements affected by the added/removed
stylesheets.

[1] http://bit.ly/25uxtnU

R=esprehn@chromium.org,timloh@chromium.org
BUG=567021
==========

[rune, 2016-04-20 20:57:13]

@timloh, @esprehn: could you take a look at this, please?

[rune, 2016-04-25 13:32:58]

ping

[esprehn, 2016-04-28 02:49:14]

This seems fine, but I'm not sure why we need to know if sheets changed or were
added. Any time a sheet changes, for any reason, we should just schedule
invalidation sets for all the rules in that sheet. So for example if you remove
a sheet, we schedule invalidation sets for all the removed rules, if you add a
sheet, we schedule invalidation sets for all the new rules. There's no reason to
care about where the sheet was inserted or removed from. Is there a reason we
can't just do that?

[rune, 2016-04-28 07:32:13]

On 2016/04/28 02:49:14, esprehn wrote:
> This seems fine, but I'm not sure why we need to know if sheets changed or
were
> added. Any time a sheet changes, for any reason, we should just schedule
> invalidation sets for all the rules in that sheet. So for example if you
remove
> a sheet, we schedule invalidation sets for all the removed rules, if you add a
> sheet, we schedule invalidation sets for all the new rules. There's no reason
to
> care about where the sheet was inserted or removed from. Is there a reason we
> can't just do that?

For style rules that is true. This is only for @font-face rules atm. We
currently clear the font cache when adding @font-face rules (because they need
to be re-added in the correct order), but only remove the removed @font-face
rules otherwise. I don't think there are other rules which can benefit from this
distinction atm. Keyframe rules replaces rules with the same name in a hashmap,
so they currently need to be re-collected unless stylesheets are purely appended
to the existing ones.

[esprehn, 2016-05-17 22:28:46]

On 2016/04/28 at 07:32:13, rune wrote:
> On 2016/04/28 02:49:14, esprehn wrote:
> > This seems fine, but I'm not sure why we need to know if sheets changed or
were
> > added. Any time a sheet changes, for any reason, we should just schedule
> > invalidation sets for all the rules in that sheet. So for example if you
remove
> > a sheet, we schedule invalidation sets for all the removed rules, if you add
a
> > sheet, we schedule invalidation sets for all the new rules. There's no
reason to
> > care about where the sheet was inserted or removed from. Is there a reason
we
> > can't just do that?
> 
> For style rules that is true. This is only for @font-face rules atm. We
currently clear the font cache when adding @font-face rules (because they need
to be re-added in the correct order), but only remove the removed @font-face
rules otherwise. I don't think there are other rules which can benefit from this
distinction atm. Keyframe rules replaces rules with the same name in a hashmap,
so they currently need to be re-collected unless stylesheets are purely appended
to the existing ones.

Can we just add a pass over the sheets that rebuilds just font lists and
keyframes? I worry this system is very complex when the common case is just to
schedule invalidation sets for all rules in the added or removed sheet.

[rune, 2016-05-18 09:03:17]

On 2016/05/17 22:28:46, esprehn wrote:
> On 2016/04/28 at 07:32:13, rune wrote:
> > On 2016/04/28 02:49:14, esprehn wrote:
> > > This seems fine, but I'm not sure why we need to know if sheets changed or
> were
> > > added. Any time a sheet changes, for any reason, we should just schedule
> > > invalidation sets for all the rules in that sheet. So for example if you
> remove
> > > a sheet, we schedule invalidation sets for all the removed rules, if you
add
> a
> > > sheet, we schedule invalidation sets for all the new rules. There's no
> reason to
> > > care about where the sheet was inserted or removed from. Is there a reason
> we
> > > can't just do that?
> > 
> > For style rules that is true. This is only for @font-face rules atm. We
> currently clear the font cache when adding @font-face rules (because they need
> to be re-added in the correct order), but only remove the removed @font-face
> rules otherwise. I don't think there are other rules which can benefit from
this
> distinction atm. Keyframe rules replaces rules with the same name in a
hashmap,
> so they currently need to be re-collected unless stylesheets are purely
appended
> to the existing ones.
> 
> Can we just add a pass over the sheets that rebuilds just font lists and
> keyframes? I worry this system is very complex when the common case is just to
> schedule invalidation sets for all rules in the added or removed sheet.

Removing sheets with @font-face is probably not that common, so I guess that's
ok.

[rune, 2016-05-18 13:14:14]

Description was changed from

==========
Implemented RuleSet diff for active stylesheets.

This is an implementation of the diffing of active stylesheets outlined
in [1] to replace the current compareStyleSheets method in
TreeScopeStyleSheetCollection which currently cause a "Reconstruct" if
you both have insertions and removals. With async stylesheet update we
will more likely end up in those situations as changes to the list can
happen in a batches.

An important new aspect here is that together with each stylesheet keep
a traced pointer to the RuleSet it had reference last time the active
stylesheet list was updated. That way we can figure out what changed on
media query and CSSOM changes.

The comparison algorithm works like this:

INPUTS: The new and old active stylesheet vectors
OUTPUTS: Two vectors of RuleSets, one for the added ones, and one for
         the removed ones.
         Also a return value saying if we only appended stylesheets at
         the end. Given that sheets were only appended we can do certain
         optimizations updating rule data.

* First linearly walk the old and new active list as long as the
  stylesheet pointers are the same. If the ruleset changed for the
  given sheet, add the old ruleset to the removed list and the new
  ruleset to the added list.

* If we are finished walking any of the active lists, we have either
  appended a set of sheets to the end, or we have removed a set from
  the tail. Add the added/removed rulesets to the corresponding output
  lists and we are finished.

* If we have remaining sheets in both the old and new active list,
  merge the remaining items from both lists and sort the merged vector
  on stylesheet pointers. For stylesheet pointers occuring in pairs, if
  the rulesets are different for the two entries are different, the
  ruleset changed so we add them to the added/removed lists. For
  stylesheets which do not occur in pairs, they are either added or
  removed and we add the ruleset to the corresponding list.

The time complexity for the algorithm is O(k) for the common prefix
and the complexity for std::sort for the m + n remaining sheets in the
new and old active lists. Note that each scope has its active list, so
the larger n's will be for the document scope as shadow trees most
often have a single stylesheet (I measured a max of three running some
Polymer apps).

An assumption here is that we will do ensureRuleSet() including media
query evaluation for the media attribute as we collect active
stylesheets. Currently, the analysis of which elements needs a style
recalc happens synchronously while updating the active sheets while the
rulesets are (re-)created asynchronously/on-demand via
lazyAppendAuthorStyleSheets in StyleResolver. The idea is that since
the active stylesheet update will be async, we can drop the lazyAppend
things from StyleResolver and add the stylesheets directly to the
ScopedStyleResolvers during the active stylesheet update.

Creating the RuleSets as we collect active stylesheets means we have
invalidation sets readily available to use style invalidation to
trigger style recalcs only on elements affected by the added/removed
stylesheets.

[1] http://bit.ly/25uxtnU

R=esprehn@chromium.org,timloh@chromium.org
BUG=567021
==========

to

==========
Implemented RuleSet diff for active stylesheets.

This is an implementation of the diffing of active stylesheets outlined
in [1] to replace the current compareStyleSheets method in
TreeScopeStyleSheetCollection which currently cause a "Reconstruct" if
you both have insertions and removals. With async stylesheet update we
will more likely end up in those situations as changes to the list can
happen in a batches.

An important new aspect here is that together with each stylesheet keep
a traced pointer to the RuleSet it had reference last time the active
stylesheet list was updated. That way we can figure out what changed on
media query and CSSOM changes.

The comparison algorithm works like this:

INPUTS: The new and old active stylesheet vectors
OUTPUTS: A vector of added and removed RuleSets.
         Also a return value saying if we only appended stylesheets at
         the end. Given that sheets were only appended we can do certain
         optimizations updating rule data.

* First linearly walk the old and new active list as long as the
  stylesheet pointers are the same. If the ruleset changed for the
  given sheet, add the old and new rulesets to the list of changed
  rulesets.

* If we are finished walking any of the active lists, we have either
  appended a set of sheets to the end, or we have removed a set from
  the tail. Add the added/removed rulesets to the changed list and we
  are finished.

* If we have remaining sheets in both the old and new active list,
  merge the remaining items from both lists and sort the merged vector
  on stylesheet pointers. For stylesheet pointers occuring in pairs, if
  the rulesets are different for the two entries, the ruleset changed
  so we add them to the changed list. For stylesheets which do not occur
  in pairs, they are either added or removed and we add the ruleset to
  the changed list.

The time complexity for the algorithm is O(k) for the common prefix
and the complexity for std::sort for the m + n remaining sheets in the
new and old active lists. Note that each scope has its active list, so
the larger n's will be for the document scope as shadow trees most
often have a single stylesheet (I measured a max of three running some
Polymer apps).

An assumption here is that we will do ensureRuleSet() including media
query evaluation for the media attribute as we collect active
stylesheets. Currently, the analysis of which elements needs a style
recalc happens synchronously while updating the active sheets while the
rulesets are (re-)created asynchronously/on-demand via
lazyAppendAuthorStyleSheets in StyleResolver. The idea is that since
the active stylesheet update will be async, we can drop the lazyAppend
things from StyleResolver and add the stylesheets directly to the
ScopedStyleResolvers during the active stylesheet update.

Creating the RuleSets as we collect active stylesheets means we have
invalidation sets readily available to use style invalidation to
trigger style recalcs only on elements affected by the added/removed
stylesheets.

[1] http://bit.ly/25uxtnU

R=esprehn@chromium.org,timloh@chromium.org
BUG=567021
==========

[rune, 2016-05-18 13:15:27]

On 2016/05/18 09:03:17, rune wrote:
> On 2016/05/17 22:28:46, esprehn wrote:

> > Can we just add a pass over the sheets that rebuilds just font lists and
> > keyframes? I worry this system is very complex when the common case is just
to
> > schedule invalidation sets for all rules in the added or removed sheet.
> 
> Removing sheets with @font-face is probably not that common, so I guess that's
> ok.

Done in PS4.

[esprehn, 2016-06-01 05:16:10]

Hmm, I must be confused, I'm still not sure why we need this prefix matching and
sorting system. I had imagined something like:

void didRemoveSheet(sheet)
void didAddSheet(sheet)

where calling either one marks that sheet as dirty and schedules every
invalidation set for that sheet. Why do we ever end up with an "old list" and
"new list" and need to compare them? I feel like we should be able to
synchronously know what sheets are being added and removed, mark them dirty, and
schedule the future work to do. This patch seems to be working backwards from
not knowing what changed.

[rune, 2016-06-01 07:59:29]

On 2016/06/01 05:16:10, esprehn wrote:
> Hmm, I must be confused, I'm still not sure why we need this prefix matching
and
> sorting system. I had imagined something like:
> 
> void didRemoveSheet(sheet)
> void didAddSheet(sheet)
> 
> where calling either one marks that sheet as dirty and schedules every
> invalidation set for that sheet. Why do we ever end up with an "old list" and
> "new list" and need to compare them? I feel like we should be able to
> synchronously know what sheets are being added and removed, mark them dirty,
and
> schedule the future work to do. This patch seems to be working backwards from
> not knowing what changed.

The invalidation sets for a given RuleSet depends on media queries. Ensuring
that RuleSet is up-to-date is already async as part of the lazyAppend... in
StyleResolver. I fear updating the different RuleSets synchronously based on the
current media features is going to be error prone and cause unnecessary extra
work. At a minimum, we need to compare active stylesheets to figure out if we
are just appending new sheets. If we are appending, we can just append new
font-face rules and keyframes without clearing the scoped resolver and the font
cache for such rules.

Did you mean that we should have a dirty flag i CSSStyleSheet but do the RuleSet
invalidation set scheduling asynchronously? I think that would require us to
schedule invalidations for the existing ruleset synchronously, or delay clearing
the ruleset for the StyleSheetContents based on dirty CSSStyleSheet. Not quite
sure how that would work. In particular, StyleSheetContents, hence rulesets, may
be shared between CSSStyleSheets, even with media queries if they are <style>
elements.


I'm not sure you've seen it, but I have WIP in [1] for the whole thing. In [2]
you can see that I've added an updateActiveStyle() step in the
updateStyleAndLayoutTree() which will collect the active stylesheets, ensure
their RuleSets based on the current media query evaluation, and schedule
invalidations for the changed RuleSets. What's currently failing are inspector
tests where the inspector code depends on synchronous update of active
stylesheets, and -webkit-image-set style resources not responding to dpi
changes.

This change is quite fundamental, so I'd expect more issues to pop up. Ideally,
I should have a design for this first, but I've had to learn through coding to
figure out how things work. I should be able to have enough information now to
do a write-up now and we can discuss it from there. There is one thing I've had
to fix (for now in a hacky way) in [1] related to this CL. Stylesheets in HTML
Imports are kept alive together with the import document itself when you remove
the import link element from the main document and re-insert the link somewhere
else. The diff in this CL assumes CSSStyleSheet is recreated when moved relative
to other stylesheets in the document structure.

Will you be at BlinkOn in Munich, btw?

[1] https://codereview.chromium.org/1913833002/
[2] https://codereview.chromium.org/1913833002/patch/120001/130035

[esprehn, 2016-06-11 11:56:48]

On 2016/06/01 at 07:59:29, rune wrote:
> ... 
> Will you be at BlinkOn in Munich, btw?
> 

Yup, I'll see you there! :)

[esprehn, 2016-06-29 04:45:36]

So what's the status here? Should I review this?

[rune, 2016-06-29 08:04:53]

On 2016/06/29 04:45:36, esprehn wrote:
> So what's the status here? Should I review this?

We discussed the need to the sort/comparison of RuleSets. Did you read #msg12 ?

[rune, 2016-08-08 09:40:09]

ping, see comment #12.

[esprehn, 2016-09-01 23:15:45]

lgtm

[rune, 2016-09-02 14:09:37]

The CQ bit was checked by rune@opera.com

[rune, 2016-09-02 14:09:38]

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/1889993002/#ps80001
(title: "Rebased.")

[commit-bot: I haz the power, 2016-09-02 14:09:53]

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-09-02 14:38:55]

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

[commit-bot: I haz the power, 2016-09-02 14:38:56]

Try jobs failed on following builders:
  linux_chromium_compile_dbg_ng on master.tryserver.chromium.linux (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...)

[rune, 2016-09-02 16:19:17]

The CQ bit was checked by rune@opera.com

[rune, 2016-09-02 16:19:17]

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/1889993002/#ps100001
(title: "Missing CORE_EXPORT.")

[commit-bot: I haz the power, 2016-09-02 16:19:37]

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-09-02 18:24:19]

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

[commit-bot: I haz the power, 2016-09-02 18:24:20]

Exceeded global retry quota

[rune, 2016-09-05 08:18:31]

The CQ bit was checked by rune@opera.com

[commit-bot: I haz the power, 2016-09-05 08:18:44]

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-09-05 08:21:00]

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

[commit-bot: I haz the power, 2016-09-05 08:21:01]

Try jobs failed on following builders:
  cast_shell_linux on master.tryserver.chromium.linux (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/cast_shell_linu...)
  mac_chromium_compile_dbg_ng on master.tryserver.chromium.mac (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.mac/builders/mac_chromium_comp...)
  mac_chromium_rel_ng on master.tryserver.chromium.mac (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.mac/builders/mac_chromium_rel_...)

[rune, 2016-09-05 08:29:16]

The CQ bit was checked by rune@opera.com

[rune, 2016-09-05 08:29:17]

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/1889993002/#ps120001
(title: "Rebased.")

[commit-bot: I haz the power, 2016-09-05 08:29:26]

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-09-05 10:18:25]

Description was changed from

==========
Implemented RuleSet diff for active stylesheets.

This is an implementation of the diffing of active stylesheets outlined
in [1] to replace the current compareStyleSheets method in
TreeScopeStyleSheetCollection which currently cause a "Reconstruct" if
you both have insertions and removals. With async stylesheet update we
will more likely end up in those situations as changes to the list can
happen in a batches.

An important new aspect here is that together with each stylesheet keep
a traced pointer to the RuleSet it had reference last time the active
stylesheet list was updated. That way we can figure out what changed on
media query and CSSOM changes.

The comparison algorithm works like this:

INPUTS: The new and old active stylesheet vectors
OUTPUTS: A vector of added and removed RuleSets.
         Also a return value saying if we only appended stylesheets at
         the end. Given that sheets were only appended we can do certain
         optimizations updating rule data.

* First linearly walk the old and new active list as long as the
  stylesheet pointers are the same. If the ruleset changed for the
  given sheet, add the old and new rulesets to the list of changed
  rulesets.

* If we are finished walking any of the active lists, we have either
  appended a set of sheets to the end, or we have removed a set from
  the tail. Add the added/removed rulesets to the changed list and we
  are finished.

* If we have remaining sheets in both the old and new active list,
  merge the remaining items from both lists and sort the merged vector
  on stylesheet pointers. For stylesheet pointers occuring in pairs, if
  the rulesets are different for the two entries, the ruleset changed
  so we add them to the changed list. For stylesheets which do not occur
  in pairs, they are either added or removed and we add the ruleset to
  the changed list.

The time complexity for the algorithm is O(k) for the common prefix
and the complexity for std::sort for the m + n remaining sheets in the
new and old active lists. Note that each scope has its active list, so
the larger n's will be for the document scope as shadow trees most
often have a single stylesheet (I measured a max of three running some
Polymer apps).

An assumption here is that we will do ensureRuleSet() including media
query evaluation for the media attribute as we collect active
stylesheets. Currently, the analysis of which elements needs a style
recalc happens synchronously while updating the active sheets while the
rulesets are (re-)created asynchronously/on-demand via
lazyAppendAuthorStyleSheets in StyleResolver. The idea is that since
the active stylesheet update will be async, we can drop the lazyAppend
things from StyleResolver and add the stylesheets directly to the
ScopedStyleResolvers during the active stylesheet update.

Creating the RuleSets as we collect active stylesheets means we have
invalidation sets readily available to use style invalidation to
trigger style recalcs only on elements affected by the added/removed
stylesheets.

[1] http://bit.ly/25uxtnU

R=esprehn@chromium.org,timloh@chromium.org
BUG=567021
==========

to

==========
Implemented RuleSet diff for active stylesheets.

This is an implementation of the diffing of active stylesheets outlined
in [1] to replace the current compareStyleSheets method in
TreeScopeStyleSheetCollection which currently cause a "Reconstruct" if
you both have insertions and removals. With async stylesheet update we
will more likely end up in those situations as changes to the list can
happen in a batches.

An important new aspect here is that together with each stylesheet keep
a traced pointer to the RuleSet it had reference last time the active
stylesheet list was updated. That way we can figure out what changed on
media query and CSSOM changes.

The comparison algorithm works like this:

INPUTS: The new and old active stylesheet vectors
OUTPUTS: A vector of added and removed RuleSets.
         Also a return value saying if we only appended stylesheets at
         the end. Given that sheets were only appended we can do certain
         optimizations updating rule data.

* First linearly walk the old and new active list as long as the
  stylesheet pointers are the same. If the ruleset changed for the
  given sheet, add the old and new rulesets to the list of changed
  rulesets.

* If we are finished walking any of the active lists, we have either
  appended a set of sheets to the end, or we have removed a set from
  the tail. Add the added/removed rulesets to the changed list and we
  are finished.

* If we have remaining sheets in both the old and new active list,
  merge the remaining items from both lists and sort the merged vector
  on stylesheet pointers. For stylesheet pointers occuring in pairs, if
  the rulesets are different for the two entries, the ruleset changed
  so we add them to the changed list. For stylesheets which do not occur
  in pairs, they are either added or removed and we add the ruleset to
  the changed list.

The time complexity for the algorithm is O(k) for the common prefix
and the complexity for std::sort for the m + n remaining sheets in the
new and old active lists. Note that each scope has its active list, so
the larger n's will be for the document scope as shadow trees most
often have a single stylesheet (I measured a max of three running some
Polymer apps).

An assumption here is that we will do ensureRuleSet() including media
query evaluation for the media attribute as we collect active
stylesheets. Currently, the analysis of which elements needs a style
recalc happens synchronously while updating the active sheets while the
rulesets are (re-)created asynchronously/on-demand via
lazyAppendAuthorStyleSheets in StyleResolver. The idea is that since
the active stylesheet update will be async, we can drop the lazyAppend
things from StyleResolver and add the stylesheets directly to the
ScopedStyleResolvers during the active stylesheet update.

Creating the RuleSets as we collect active stylesheets means we have
invalidation sets readily available to use style invalidation to
trigger style recalcs only on elements affected by the added/removed
stylesheets.

[1] http://bit.ly/25uxtnU

R=esprehn@chromium.org,timloh@chromium.org
BUG=567021
==========

[commit-bot: I haz the power, 2016-09-05 10:18:26]

Committed patchset #7 (id:120001)

[commit-bot: I haz the power, 2016-09-05 10:20:38]

Description was changed from

==========
Implemented RuleSet diff for active stylesheets.

This is an implementation of the diffing of active stylesheets outlined
in [1] to replace the current compareStyleSheets method in
TreeScopeStyleSheetCollection which currently cause a "Reconstruct" if
you both have insertions and removals. With async stylesheet update we
will more likely end up in those situations as changes to the list can
happen in a batches.

An important new aspect here is that together with each stylesheet keep
a traced pointer to the RuleSet it had reference last time the active
stylesheet list was updated. That way we can figure out what changed on
media query and CSSOM changes.

The comparison algorithm works like this:

INPUTS: The new and old active stylesheet vectors
OUTPUTS: A vector of added and removed RuleSets.
         Also a return value saying if we only appended stylesheets at
         the end. Given that sheets were only appended we can do certain
         optimizations updating rule data.

* First linearly walk the old and new active list as long as the
  stylesheet pointers are the same. If the ruleset changed for the
  given sheet, add the old and new rulesets to the list of changed
  rulesets.

* If we are finished walking any of the active lists, we have either
  appended a set of sheets to the end, or we have removed a set from
  the tail. Add the added/removed rulesets to the changed list and we
  are finished.

* If we have remaining sheets in both the old and new active list,
  merge the remaining items from both lists and sort the merged vector
  on stylesheet pointers. For stylesheet pointers occuring in pairs, if
  the rulesets are different for the two entries, the ruleset changed
  so we add them to the changed list. For stylesheets which do not occur
  in pairs, they are either added or removed and we add the ruleset to
  the changed list.

The time complexity for the algorithm is O(k) for the common prefix
and the complexity for std::sort for the m + n remaining sheets in the
new and old active lists. Note that each scope has its active list, so
the larger n's will be for the document scope as shadow trees most
often have a single stylesheet (I measured a max of three running some
Polymer apps).

An assumption here is that we will do ensureRuleSet() including media
query evaluation for the media attribute as we collect active
stylesheets. Currently, the analysis of which elements needs a style
recalc happens synchronously while updating the active sheets while the
rulesets are (re-)created asynchronously/on-demand via
lazyAppendAuthorStyleSheets in StyleResolver. The idea is that since
the active stylesheet update will be async, we can drop the lazyAppend
things from StyleResolver and add the stylesheets directly to the
ScopedStyleResolvers during the active stylesheet update.

Creating the RuleSets as we collect active stylesheets means we have
invalidation sets readily available to use style invalidation to
trigger style recalcs only on elements affected by the added/removed
stylesheets.

[1] http://bit.ly/25uxtnU

R=esprehn@chromium.org,timloh@chromium.org
BUG=567021
==========

to

==========
Implemented RuleSet diff for active stylesheets.

This is an implementation of the diffing of active stylesheets outlined
in [1] to replace the current compareStyleSheets method in
TreeScopeStyleSheetCollection which currently cause a "Reconstruct" if
you both have insertions and removals. With async stylesheet update we
will more likely end up in those situations as changes to the list can
happen in a batches.

An important new aspect here is that together with each stylesheet keep
a traced pointer to the RuleSet it had reference last time the active
stylesheet list was updated. That way we can figure out what changed on
media query and CSSOM changes.

The comparison algorithm works like this:

INPUTS: The new and old active stylesheet vectors
OUTPUTS: A vector of added and removed RuleSets.
         Also a return value saying if we only appended stylesheets at
         the end. Given that sheets were only appended we can do certain
         optimizations updating rule data.

* First linearly walk the old and new active list as long as the
  stylesheet pointers are the same. If the ruleset changed for the
  given sheet, add the old and new rulesets to the list of changed
  rulesets.

* If we are finished walking any of the active lists, we have either
  appended a set of sheets to the end, or we have removed a set from
  the tail. Add the added/removed rulesets to the changed list and we
  are finished.

* If we have remaining sheets in both the old and new active list,
  merge the remaining items from both lists and sort the merged vector
  on stylesheet pointers. For stylesheet pointers occuring in pairs, if
  the rulesets are different for the two entries, the ruleset changed
  so we add them to the changed list. For stylesheets which do not occur
  in pairs, they are either added or removed and we add the ruleset to
  the changed list.

The time complexity for the algorithm is O(k) for the common prefix
and the complexity for std::sort for the m + n remaining sheets in the
new and old active lists. Note that each scope has its active list, so
the larger n's will be for the document scope as shadow trees most
often have a single stylesheet (I measured a max of three running some
Polymer apps).

An assumption here is that we will do ensureRuleSet() including media
query evaluation for the media attribute as we collect active
stylesheets. Currently, the analysis of which elements needs a style
recalc happens synchronously while updating the active sheets while the
rulesets are (re-)created asynchronously/on-demand via
lazyAppendAuthorStyleSheets in StyleResolver. The idea is that since
the active stylesheet update will be async, we can drop the lazyAppend
things from StyleResolver and add the stylesheets directly to the
ScopedStyleResolvers during the active stylesheet update.

Creating the RuleSets as we collect active stylesheets means we have
invalidation sets readily available to use style invalidation to
trigger style recalcs only on elements affected by the added/removed
stylesheets.

[1] http://bit.ly/25uxtnU

R=esprehn@chromium.org,timloh@chromium.org
BUG=567021

Committed: https://crrev.com/f9d162281661e2fb8805814513a549683775d56b
Cr-Commit-Position: refs/heads/master@{#416520}
==========

[commit-bot: I haz the power, 2016-09-05 10:20:39]

Patchset 7 (id:??) landed as
https://crrev.com/f9d162281661e2fb8805814513a549683775d56b
Cr-Commit-Position: refs/heads/master@{#416520}