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
Review-Url: https://codereview.chromium.org/1889993002
Cr-Commit-Position: refs/heads/master@{#416520}
5 files changed
