Cascade declared property values instead of applying values on top of each other

Cascade declared property values instead of applying values on top of each other

Currently, the StyleResolver builds the style for an element by calling
StyleBuilder::applyProperty in the appropriate order for all the matched
property declarations. This is inefficient in that for elements with
complex styling, many of these declarations will be overridden by other
declarations, so we will end up doing many unneeded conversions of
CSSValues. This patch makes us cascade declared property values before
applying, so that we generally only end up applying each property at
most once (-webkit-appearance and animations break this rule).

The existence of vendor-prefixed properties complicate this change
somewhat. It's generally accepted that specifying a property and a
vendor-prefixed variant will have the latter one take effect. Thus we
map these to the same property, so they can properly cascade, and
disallow calling into the StyleBuilder with these aliased properties.
To handle this for the various non-standard direction aware properties,
we resolve the values of direction and writing-mode (now super-high
priority) before cascading.

Note that -webkit-perspective allows more values that perspective (in
particular, numbers are allowed), although they now use the same handler.
The test transforms/perspective-parsing.html ensures that perspective
considers values that are allowed for -webkit-perspective as invalid.

This patch is similar in nature to similar work done in WebKit by akling,
https://bugs.webkit.org/show_bug.cgi?id=125213. The implementation is
different here in lots of little ways, although I've copied the function
elementTypeHasAppearanceFromUAStyle to avoid doing work to support
-webkit-appearance in the common case.

BUG=399497

[Timothy Loh, 2014-06-26 02:01:51]

Hey guys,

This change isn't quite done yet but I'd like to get some quick
high-level feedback to make sure I'm doing something useful here before
finishing it up and splitting it up into smaller patches. Does this seem
like a worthwhile change to you guys? The current apply-all-the-things
applyMatchedProperties has always seemed bizarre to me, and this may
also be a useful step towards ojan's RenderStyle data packing ideas or
other optimisations around here.

[esprehn, 2014-06-26 02:09:08]

On 2014/06/26 at 02:01:51, timloh wrote:
> Hey guys,
> 
> This change isn't quite done yet but I'd like to get some quick
> high-level feedback to make sure I'm doing something useful here before
> finishing it up and splitting it up into smaller patches. Does this seem
> like a worthwhile change to you guys? The current apply-all-the-things
> applyMatchedProperties has always seemed bizarre to me, and this may
> also be a useful step towards ojan's RenderStyle data packing ideas or
> other optimisations around here.

I definitely support doing this. They did it in webkit too, there's a class
called StyleResolver::CascadedProperties:
https://trac.webkit.org/browser/trunk/Source/WebCore/css/StyleResolver.cpp#L3696

You might want to look at how they did it, there's a lot of special cases they
accounted for. (You may already know all this, I haven't looked at your patch).

[Timothy Loh, 2014-07-02 07:50:47]

This is ready for review now. A subsequent (not yet ready) patch
(https://codereview.chromium.org/361173002/) will somewhat simplify handling for
-webkit-appearance following on from this change, and remove the step of
applying the UA stylesheet properties independently of the cascade.

On 2014/06/26 02:09:08, esprehn wrote:
> On 2014/06/26 at 02:01:51, timloh wrote:
> > Hey guys,
> > 
> > This change isn't quite done yet but I'd like to get some quick
> > high-level feedback to make sure I'm doing something useful here before
> > finishing it up and splitting it up into smaller patches. Does this seem
> > like a worthwhile change to you guys? The current apply-all-the-things
> > applyMatchedProperties has always seemed bizarre to me, and this may
> > also be a useful step towards ojan's RenderStyle data packing ideas or
> > other optimisations around here.
> 
> I definitely support doing this. They did it in webkit too, there's a class
> called StyleResolver::CascadedProperties:
>
https://trac.webkit.org/browser/trunk/Source/WebCore/css/StyleResolver.cpp#L3696
> 
> You might want to look at how they did it, there's a lot of special cases they
> accounted for. (You may already know all this, I haven't looked at your
patch).

I've had a look and we've ended up with lots of mostly small differences. The
main difference is that in webkit the approach for properties with prefixed and
non-prefixed versions is to simply push these into a list instead of cascading,
whereas my patch buckets these together.

[Timothy Loh, 2014-07-17 04:48:26]

PTAL

[andersr, 2014-07-17 12:15:38]

Nice. I wonder if we can be more clever with our style application as a result
of this, e.g. apply all background properties at the same time to avoid
after-the-fact adjustment.

https://codereview.chromium.org/350333003/diff/210001/Source/core/css/resolve...
File Source/core/css/resolver/CascadedValues.cpp (right):

https://codereview.chromium.org/350333003/diff/210001/Source/core/css/resolve...
Source/core/css/resolver/CascadedValues.cpp:259: for (size_t i = 0; i <
matchResult.matchedProperties.size(); ++i) {
This code *seems* annoyingly redundant, since it does approximately a subset of
what CascadedValues does as a whole.

Would it be possible to move '-webkit-writing-mode' next to 'direction' in
CSSPropertyNames.in (to create an ultra-high priority segment), then extend some
'addValues' method with a valid range of property names to add? Then you could
perhaps apply this more "normally", e.g.:

CascadedValues::CascadedValues(...) {
   // memset ...
   addValues(matchResult, ... , CSSPropertyDirection,
CSSPropertyWebkitWritingMode);
   applyValues(CSSPropertyDirection, CSSPropertyWebkitWritingMode, false);
   direction = ...;
   writingMode = ...;
}

Although the !important handling complicates things a bit here ...

https://codereview.chromium.org/350333003/diff/210001/Source/core/css/resolve...
Source/core/css/resolver/CascadedValues.cpp:376: void
CascadedValues::applyValues(CSSPropertyID start, CSSPropertyID end, bool
inheritedOnly)
Is first/last more appropriate than start/end?

   applyValues(CSSPropertyID first, CSSPropertyID last, bool inheritedOnly)

In STL (FWIW), and in wtf/Vector, 'end()' means past-the-last-element, whereas
here it means last-element.

[Timothy Loh, 2014-07-21 06:06:00]

https://codereview.chromium.org/350333003/diff/210001/Source/core/css/resolve...
File Source/core/css/resolver/CascadedValues.cpp (right):

https://codereview.chromium.org/350333003/diff/210001/Source/core/css/resolve...
Source/core/css/resolver/CascadedValues.cpp:259: for (size_t i = 0; i <
matchResult.matchedProperties.size(); ++i) {
On 2014/07/17 12:15:38, andersr wrote:
> This code *seems* annoyingly redundant, since it does approximately a subset
of
> what CascadedValues does as a whole.
> 
> Would it be possible to move '-webkit-writing-mode' next to 'direction' in
> CSSPropertyNames.in (to create an ultra-high priority segment), then extend
some
> 'addValues' method with a valid range of property names to add? Then you could
> perhaps apply this more "normally", e.g.:
> 
> CascadedValues::CascadedValues(...) {
>    // memset ...
>    addValues(matchResult, ... , CSSPropertyDirection,
> CSSPropertyWebkitWritingMode);
>    applyValues(CSSPropertyDirection, CSSPropertyWebkitWritingMode, false);
>    direction = ...;
>    writingMode = ...;
> }
> 
> Although the !important handling complicates things a bit here ...

Done.

https://codereview.chromium.org/350333003/diff/210001/Source/core/css/resolve...
Source/core/css/resolver/CascadedValues.cpp:376: void
CascadedValues::applyValues(CSSPropertyID start, CSSPropertyID end, bool
inheritedOnly)
On 2014/07/17 12:15:38, andersr wrote:
> Is first/last more appropriate than start/end?
> 
>    applyValues(CSSPropertyID first, CSSPropertyID last, bool inheritedOnly)
> 
> In STL (FWIW), and in wtf/Vector, 'end()' means past-the-last-element, whereas
> here it means last-element.

Good idea; changed to first/last.

[Timothy Loh, 2014-07-21 06:30:32]

On 2014/07/17 12:15:38, andersr wrote:
> Nice. I wonder if we can be more clever with our style application as a result
> of this, e.g. apply all background properties at the same time to avoid
> after-the-fact adjustment.

I suspect that there's some nice solution here to get rid of the current
background adjustment mess that involves having an FillLayer iterator which does
the necessary repeating instead of having it at style resolution time, although
it seems like a high-effort-low-reward refactor. On the other hand, I've made
note of a few smaller things that I can probably clean up after this is done :)

[esprehn, 2014-07-21 18:50:35]

This patch is pretty big, can we break it up?

https://codereview.chromium.org/350333003/diff/270001/Source/core/css/resolve...
File Source/core/css/resolver/CascadedValues.cpp (right):

https://codereview.chromium.org/350333003/diff/270001/Source/core/css/resolve...
Source/core/css/resolver/CascadedValues.cpp:18: bool
isValidCueStyleProperty(CSSPropertyID property)
static, get rid of the anonymous namespace.

https://codereview.chromium.org/350333003/diff/270001/Source/core/css/resolve...
Source/core/css/resolver/CascadedValues.cpp:66: bool
isValidFirstLetterStyleProperty(CSSPropertyID property)
static

https://codereview.chromium.org/350333003/diff/270001/Source/core/css/resolve...
Source/core/css/resolver/CascadedValues.cpp:189: CSSPropertyID
resolveProperty(CSSPropertyID property, TextDirection direction, WritingMode
writingMode)
static

https://codereview.chromium.org/350333003/diff/270001/Source/core/css/resolve...
Source/core/css/resolver/CascadedValues.cpp:257:
addMatchResultInternal(matchResult, false, 0,
matchResult.matchedProperties.size() - 1, CSSPropertyDirection,
CSSPropertyWebkitWritingMode);
Can we get rid of this boolean argument?

https://codereview.chromium.org/350333003/diff/270001/Source/core/css/resolve...
Source/core/css/resolver/CascadedValues.cpp:330: values[CSSPropertyLineHeight -
firstCSSProperty] = nullptr;
Why are you always subtracting backwards? I think you want to make this either a
macro or a function with a comment.

values[INDEX(CSSPropertyLineHeight)] = nullptr

https://codereview.chromium.org/350333003/diff/270001/Source/core/css/resolve...
File Source/core/css/resolver/CascadedValues.h (right):

https://codereview.chromium.org/350333003/diff/270001/Source/core/css/resolve...
Source/core/css/resolver/CascadedValues.h:41: WritingMode writingMode;
Missing m_ on all the members.

https://codereview.chromium.org/350333003/diff/270001/Source/core/css/resolve...
File Source/core/css/resolver/StyleResolver.cpp (right):

https://codereview.chromium.org/350333003/diff/270001/Source/core/css/resolve...
Source/core/css/resolver/StyleResolver.cpp:102: // These elements have
-webkit-appearance specified in html.css
What happens if someone uses webkit-appearance not in a UA style or this gets
out of sync?

https://codereview.chromium.org/350333003/diff/270001/Source/core/css/resolve...
Source/core/css/resolver/StyleResolver.cpp:1154:
cascadedValues.addMatchResult(matchResult, true, matchResult.ranges.firstUARule,
matchResult.ranges.lastUARule);
Can we get rid of this boolean?

[Timothy Loh, 2014-07-22 14:32:48]

I couldn't think of any reasonable way to break this up. The part of the change
which maps prefixed properties (previously use_handlers_for and direction_aware
in CSSProperties.in, now CascadedValues::resolveProperty) could maybe stand on
its own, although I think it works better as part of this patch :/

https://codereview.chromium.org/350333003/diff/270001/Source/core/css/resolve...
File Source/core/css/resolver/CascadedValues.cpp (right):

https://codereview.chromium.org/350333003/diff/270001/Source/core/css/resolve...
Source/core/css/resolver/CascadedValues.cpp:18: bool
isValidCueStyleProperty(CSSPropertyID property)
On 2014/07/21 18:50:34, esprehn wrote:
> static, get rid of the anonymous namespace.

Done.

https://codereview.chromium.org/350333003/diff/270001/Source/core/css/resolve...
Source/core/css/resolver/CascadedValues.cpp:66: bool
isValidFirstLetterStyleProperty(CSSPropertyID property)
On 2014/07/21 18:50:34, esprehn wrote:
> static

Done.

https://codereview.chromium.org/350333003/diff/270001/Source/core/css/resolve...
Source/core/css/resolver/CascadedValues.cpp:189: CSSPropertyID
resolveProperty(CSSPropertyID property, TextDirection direction, WritingMode
writingMode)
On 2014/07/21 18:50:34, esprehn wrote:
> static

Done.

https://codereview.chromium.org/350333003/diff/270001/Source/core/css/resolve...
Source/core/css/resolver/CascadedValues.cpp:257:
addMatchResultInternal(matchResult, false, 0,
matchResult.matchedProperties.size() - 1, CSSPropertyDirection,
CSSPropertyWebkitWritingMode);
On 2014/07/21 18:50:34, esprehn wrote:
> Can we get rid of this boolean argument?

The MatchResult stores declarations in the order (UA Rules -> Author rules), but
we want the order (UA not important -> author not important -> author important
-> UA important), so there's not really much we can do here. I've simplfiied the
interface a bit though, so now the ctor here will add the rest of the values in
the MatchResult.

https://codereview.chromium.org/350333003/diff/270001/Source/core/css/resolve...
Source/core/css/resolver/CascadedValues.cpp:330: values[CSSPropertyLineHeight -
firstCSSProperty] = nullptr;
On 2014/07/21 18:50:34, esprehn wrote:
> Why are you always subtracting backwards? I think you want to make this either
a
> macro or a function with a comment.
> 
> values[INDEX(CSSPropertyLineHeight)] = nullptr

Done.

https://codereview.chromium.org/350333003/diff/270001/Source/core/css/resolve...
File Source/core/css/resolver/CascadedValues.h (right):

https://codereview.chromium.org/350333003/diff/270001/Source/core/css/resolve...
Source/core/css/resolver/CascadedValues.h:41: WritingMode writingMode;
On 2014/07/21 18:50:34, esprehn wrote:
> Missing m_ on all the members.

Oops, fixed.

https://codereview.chromium.org/350333003/diff/270001/Source/core/css/resolve...
File Source/core/css/resolver/StyleResolver.cpp (right):

https://codereview.chromium.org/350333003/diff/270001/Source/core/css/resolve...
Source/core/css/resolver/StyleResolver.cpp:102: // These elements have
-webkit-appearance specified in html.css
On 2014/07/21 18:50:34, esprehn wrote:
> What happens if someone uses webkit-appearance not in a UA style or this gets
> out of sync?

It isn't of concern here whether -webkit-appearance is specified as an author
rule. cacheUserAgentBorderAndBackground currently only does anything if the UA
style has -webkit-appearance set (I'm just trying to match existing behaviour
right now). Note that a subsequent patch (wip at
https://codereview.chromium.org/361173002/) will make some clean-ups to handling
-webkit-appearance.

I couldn't find any nice points to add an assertion that this check matches
what's in the current UA stylesheet.

https://codereview.chromium.org/350333003/diff/270001/Source/core/css/resolve...
Source/core/css/resolver/StyleResolver.cpp:1154:
cascadedValues.addMatchResult(matchResult, true, matchResult.ranges.firstUARule,
matchResult.ranges.lastUARule);
On 2014/07/21 18:50:34, esprehn wrote:
> Can we get rid of this boolean?

See other comment

[Timothy Loh, 2014-07-28 15:08:23]

PTAL, thanks!

[esprehn, 2014-07-28 17:38:35]

Can we really not do the code moves in one patch, and the refactoring into
methods in another? You can add that new class and have it not really do
anything to start... it's super hard to tell what you changed and what was
already there...

Have you run html5-full-render? Does this make it faster? :)

https://codereview.chromium.org/350333003/diff/370001/Source/core/css/resolve...
File Source/core/css/resolver/CascadedValues.cpp (right):

https://codereview.chromium.org/350333003/diff/370001/Source/core/css/resolve...
Source/core/css/resolver/CascadedValues.cpp:303: // problems with e.g.
foo:first-letter { all: inherit; }
Is this a new FIXME?

https://codereview.chromium.org/350333003/diff/370001/Source/core/css/resolve...
File Source/core/css/resolver/CascadedValues.h (right):

https://codereview.chromium.org/350333003/diff/370001/Source/core/css/resolve...
Source/core/css/resolver/CascadedValues.h:35: CSSValue*&
cascadedValue(CSSPropertyID id)
Returning references to array values is pretty sketchy, why not have a getter
and a setter?

[Timothy Loh, 2014-07-29 08:32:15]

https://codereview.chromium.org/350333003/diff/370001/Source/core/css/resolve...
File Source/core/css/resolver/CascadedValues.cpp (right):

https://codereview.chromium.org/350333003/diff/370001/Source/core/css/resolve...
Source/core/css/resolver/CascadedValues.cpp:303: // problems with e.g.
foo:first-letter { all: inherit; }
On 2014/07/28 17:38:34, esprehn wrote:
> Is this a new FIXME?

The problem exists in the current code but it hadn't been noticed previously.

https://codereview.chromium.org/350333003/diff/370001/Source/core/css/resolve...
File Source/core/css/resolver/CascadedValues.h (right):

https://codereview.chromium.org/350333003/diff/370001/Source/core/css/resolve...
Source/core/css/resolver/CascadedValues.h:35: CSSValue*&
cascadedValue(CSSPropertyID id)
On 2014/07/28 17:38:35, esprehn wrote:
> Returning references to array values is pretty sketchy, why not have a getter
> and a setter?

Good idea, done.

[Timothy Loh, 2014-07-29 08:46:30]

On 2014/07/28 17:38:35, esprehn wrote:
> Can we really not do the code moves in one patch, and the refactoring into
> methods in another? You can add that new class and have it not really do
> anything to start... it's super hard to tell what you changed and what was
> already there...

Tweaked patch to leave the property whitelists in StyleResolver.cpp for now. The
only other code move now is first/lastCSSPropertyId, which are changed slightly
with new values due to new super-high-priority pass.

> Have you run html5-full-render? Does this make it faster? :)

I'm looking into how to make optimise this code now, I'll probably have to work
something out before we can land this. Currently we always iterate over the
400ish properties for both the regular and visited cases, regardless of how many
properties are set. So for elements with little styling, this will be more
expensive than what we currently have (html5-full-render appears 0.3% slower and
style recalc shouldn't even account for too much of the total time). I expect
we'll end up storing some sort of extra metadata about which properties have
been set that will be faster to check over than the current arrays; I'll test
out a few options to see what works well.

[Timothy Loh, 2014-07-30 10:35:08]

On 2014/07/29 08:46:30, Timothy Loh wrote:
> On 2014/07/28 17:38:35, esprehn wrote:
> > Can we really not do the code moves in one patch, and the refactoring into
> > methods in another? You can add that new class and have it not really do
> > anything to start... it's super hard to tell what you changed and what was
> > already there...
> 
> Tweaked patch to leave the property whitelists in StyleResolver.cpp for now.
The
> only other code move now is first/lastCSSPropertyId, which are changed
slightly
> with new values due to new super-high-priority pass.
> 
> > Have you run html5-full-render? Does this make it faster? :)
> 
> I'm looking into how to make optimise this code now, I'll probably have to
work
> something out before we can land this. Currently we always iterate over the
> 400ish properties for both the regular and visited cases, regardless of how
many
> properties are set. So for elements with little styling, this will be more
> expensive than what we currently have (html5-full-render appears 0.3% slower
and
> style recalc shouldn't even account for too much of the total time). I expect
> we'll end up storing some sort of extra metadata about which properties have
> been set that will be faster to check over than the current arrays; I'll test
> out a few options to see what works well.

I've tested a few options and the latest patch set shows what seemed to work
best. Performance in html5-full-render seemed unchanged (nexus7v2, up to random
fluctuations) with this patchset. Some tests are going to show lower
performance, where we have lots of style recalcs on elements with extremely
little styling (e.g. some transition tests). There'll be some more opportunities
to optimise this further later; e.g. having all the properties that we care
about (not aliases or longhands) in a contiguous range to reduce the storage
space for our arrays (i.e. the size of array we need to memset). There's
probably also room for handling visited properties a bit better. We may also be
able to apply all the properties in a single go instead of doing high priority
then low priority.

The other approaches I tried were
1) Lazily initialising the array of CSSValues and having a bit array to indicate
which properties have been set; this is what WebKit seems to currently do. This
change did not appear to improve performance.
2) Similar to (1), but with an array-backed tree data structure which lets us
iterate over the set properties in O(max(n, k log n)) when there are k set
properties. This appeared slightly worse than the vector approach in the latest
patch set and the code is somewhat more complex.

[Timothy Loh, 2014-08-05 02:19:39]

PTAL

One more optimisation I came up with here is that if we have a cascaded value of
inherit for an inherited property or initial for a non-inherited property then
we should be able to skip applying the property entirely. This should be fairly
common when specifying shorthands (e.g. "background: black" sets nine properties
to initial).

I can't do this yet due to the re-application for -webkit-appearance, although
it shouldn't be too much extra work to make this optimisation possible.

[Timothy Loh, 2014-08-26 00:58:27]

On 2014/08/05 02:19:39, Timothy Loh wrote:
> PTAL
> 
> One more optimisation I came up with here is that if we have a cascaded value
of
> inherit for an inherited property or initial for a non-inherited property then
> we should be able to skip applying the property entirely. This should be
fairly
> common when specifying shorthands (e.g. "background: black" sets nine
properties
> to initial).
> 
> I can't do this yet due to the re-application for -webkit-appearance, although
> it shouldn't be too much extra work to make this optimisation possible.

Going to close this for now; I've made a whole heap of changes which I need to
rebase over and there's a couple of changes I still want to do before revisiting
this.