Replace style sharing cousin list search with LRU

Replace style sharing cousin list search with LRU

The current implementation of style sharing uses a very confusing set of methods to
search a node's cousins in an attempt to find other nodes to share style with. This
patch replaces this confusing method with a simple LRU that allows us to find
nodes to share with even if they're not our cousins.

Re-worked to be simpler in the lazy-attach world (thanks esprehn & ojan!).

Previous commits of this change had perf regressions, the last of which should be
handled by only adding elements to the style sharing LRU during recalcStyle if sharing
is indeed possible for the element. Without this, in the degenerate case where there's
a large document and no elements can share style (like the fixed-grid-lots-of-data
performance test) we'd end up doing more work.

Because this change introduces RefPtrs that can hold onto nodes while the style
resolver is active, Internal gc functions are updated to clear the style sharing list.

Previous codereviews https://codereview.chromium.org/23075004/ and
https://chromiumcodereview.appspot.com/23049008

BUG=272363, 286376
Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=157646

[esprehn, 2013-09-11 21:53:01]

LGTM, two comments, I think you want to check elementCanShareStyle() at the top
of find*() otherwise you'll add things that can't share at all to the LRU?

https://codereview.chromium.org/24106007/diff/1/Source/core/css/resolver/Shar...
File Source/core/css/resolver/SharedStyleFinder.cpp (right):

https://codereview.chromium.org/24106007/diff/1/Source/core/css/resolver/Shar...
Source/core/css/resolver/SharedStyleFinder.cpp:296:
m_styleResolver->addToStyleSharingList(context.element());
If the context.element() returns false for elementCanShareStyle() we should
probably return at the top of this function, right now you'll look at all the
things in the LRU and then end up here and add it to the list, while in
::recalcStyle you guard against that and only add ones that return true.

https://codereview.chromium.org/24106007/diff/1/Source/core/css/resolver/Styl...
File Source/core/css/resolver/StyleResolver.cpp (right):

https://codereview.chromium.org/24106007/diff/1/Source/core/css/resolver/Styl...
Source/core/css/resolver/StyleResolver.cpp:244: bool
StyleResolver::elementCanShareStyle(Element* element)
supportsStyleSharing?

https://codereview.chromium.org/24106007/diff/1/Source/core/html/parser/HTMLC...
File Source/core/html/parser/HTMLConstructionSite.cpp (right):

https://codereview.chromium.org/24106007/diff/1/Source/core/html/parser/HTMLC...
Source/core/html/parser/HTMLConstructionSite.cpp:32: #include
"core/css/resolver/StyleResolver.h"
Doesn't look needed.

[leviw_travelin_and_unemployed, 2013-09-11 21:58:15]

https://codereview.chromium.org/24106007/diff/1/Source/core/css/resolver/Shar...
File Source/core/css/resolver/SharedStyleFinder.cpp (right):

https://codereview.chromium.org/24106007/diff/1/Source/core/css/resolver/Shar...
Source/core/css/resolver/SharedStyleFinder.cpp:296:
m_styleResolver->addToStyleSharingList(context.element());
On 2013/09/11 21:53:01, esprehn wrote:
> If the context.element() returns false for elementCanShareStyle() we should
> probably return at the top of this function, right now you'll look at all the
> things in the LRU and then end up here and add it to the list, while in
> ::recalcStyle you guard against that and only add ones that return true.

We guard against it by calling elementCanShareStyle() in locateSharedStyle,
which calls findElementForStyleSharing

https://codereview.chromium.org/24106007/diff/1/Source/core/css/resolver/Styl...
File Source/core/css/resolver/StyleResolver.cpp (right):

https://codereview.chromium.org/24106007/diff/1/Source/core/css/resolver/Styl...
Source/core/css/resolver/StyleResolver.cpp:244: bool
StyleResolver::elementCanShareStyle(Element* element)
On 2013/09/11 21:53:01, esprehn wrote:
> supportsStyleSharing?

Will do :)

https://codereview.chromium.org/24106007/diff/1/Source/core/dom/ContainerNode...
File Source/core/dom/ContainerNode.cpp (right):

https://codereview.chromium.org/24106007/diff/1/Source/core/dom/ContainerNode...
Source/core/dom/ContainerNode.cpp:28: #include
"core/css/resolver/StyleResolver.h"
Whoops, this can go away now :)

https://codereview.chromium.org/24106007/diff/1/Source/core/html/parser/HTMLC...
File Source/core/html/parser/HTMLConstructionSite.cpp (right):

https://codereview.chromium.org/24106007/diff/1/Source/core/html/parser/HTMLC...
Source/core/html/parser/HTMLConstructionSite.cpp:32: #include
"core/css/resolver/StyleResolver.h"
On 2013/09/11 21:53:01, esprehn wrote:
> Doesn't look needed.

Nope!

[commit-bot: I haz the power, 2013-09-11 22:07:06]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/leviw@chromium.org/24106007/9001

[commit-bot: I haz the power, 2013-09-12 00:44:14]

Change committed as 157646