Replace style sharing cousin list search with LRU

Source/core/css/resolver/SharedStyleFinder.cpp

Index: Source/core/css/resolver/SharedStyleFinder.cpp
diff --git a/Source/core/css/resolver/SharedStyleFinder.cpp b/Source/core/css/resolver/SharedStyleFinder.cpp
index 2cbc11f8bec7a4a49438de5d3018d5c837d9ff2e..5f996330f14c62005dd500c849c77e69cd0b8b4f 100644
--- a/Source/core/css/resolver/SharedStyleFinder.cpp
+++ b/Source/core/css/resolver/SharedStyleFinder.cpp
@@ -36,6 +36,7 @@
 #include "core/dom/ContainerNode.h"
 #include "core/dom/Document.h"
 #include "core/dom/Element.h"
+#include "core/dom/ElementTraversal.h"
 #include "core/dom/FullscreenElementStack.h"
 #include "core/dom/Node.h"
 #include "core/dom/NodeRenderStyle.h"
@@ -55,64 +56,11 @@ namespace WebCore {
 
 using namespace HTMLNames;
 
-static const unsigned cStyleSearchThreshold = 10;
-static const unsigned cStyleSearchLevelThreshold = 10;
-
 static inline bool parentElementPreventsSharing(const Element* parentElement)
 {
-    if (!parentElement)
-        return false;
     return parentElement->hasFlagsSetDuringStylingOfChildren();
 }
 
-Node* SharedStyleFinder::locateCousinList(Element* parent, unsigned& visitedNodeCount) const
-{
-    if (visitedNodeCount >= cStyleSearchThreshold * cStyleSearchLevelThreshold)
-        return 0;
-    if (!parent || !parent->isStyledElement())
-        return 0;
-    if (parent->hasScopedHTMLStyleChild())
-        return 0;
-    if (parent->inlineStyle())
-        return 0;
-    if (parent->isSVGElement() && toSVGElement(parent)->animatedSMILStyleProperties())
-        return 0;
-    if (parent->hasID() && m_features.idsInRules.contains(parent->idForStyleResolution().impl()))
-        return 0;
-    if (isShadowHost(parent) && parent->shadow()->containsActiveStyles())
-        return 0;
-
-    RenderStyle* parentStyle = parent->renderStyle();
-    unsigned subcount = 0;
-    Node* thisCousin = parent;
-    Node* currentNode = parent->previousSibling();
-
-    // Reserve the tries for this level. This effectively makes sure that the algorithm
-    // will never go deeper than cStyleSearchLevelThreshold levels into recursion.
-    visitedNodeCount += cStyleSearchThreshold;
-    while (thisCousin) {
-        while (currentNode) {
-            ++subcount;
-            if (!currentNode->hasScopedHTMLStyleChild() && currentNode->renderStyle() == parentStyle && currentNode->lastChild()
-                && currentNode->isElementNode() && !parentElementPreventsSharing(toElement(currentNode))
-                && !toElement(currentNode)->shadow()
-                ) {
-                // Adjust for unused reserved tries.
-                visitedNodeCount -= cStyleSearchThreshold - subcount;
-                return currentNode->lastChild();
-            }
-            if (subcount >= cStyleSearchThreshold)
-                return 0;
-            currentNode = currentNode->previousSibling();
-        }
-        currentNode = locateCousinList(thisCousin->parentElement(), visitedNodeCount);
-        thisCousin = currentNode;
-    }
-
-    return 0;
-}
-
-
 bool SharedStyleFinder::canShareStyleWithControl(const ElementResolveContext& context, Element* element) const
 {
     if (!element->hasTagName(inputTag) || !context.element()->hasTagName(inputTag))
@@ -213,9 +161,16 @@ bool SharedStyleFinder::sharingCandidateHasIdenticalStyleAffectingAttributes(con
 
 bool SharedStyleFinder::canShareStyleWithElement(const ElementResolveContext& context, Element* element) const
 {
+    if (context.element() == element)
+        return false;
+    Element* parent = element->parentElement();
     RenderStyle* style = element->renderStyle();
     if (!style)
         return false;
+    if (!parent)
+        return false;
+    if (context.element()->parentElement()->renderStyle() != parent->renderStyle())
+        return false;
     if (style->unique())
         return false;
     if (style->hasUniquePseudoStyle())
@@ -295,20 +250,22 @@ bool SharedStyleFinder::canShareStyleWithElement(const ElementResolveContext& co
             return false;
     }
 
-    return true;
-}
-
-inline Element* SharedStyleFinder::findSiblingForStyleSharing(const ElementResolveContext& context, Node* node, unsigned& count) const
-{
-    for (; node; node = node->previousSibling()) {
-        if (!node->isStyledElement())
-            continue;
-        if (canShareStyleWithElement(context, toElement(node)))
-            break;
-        if (count++ == cStyleSearchThreshold)
-            return 0;
+    if (context.element()->parentElement() != parent) {
+        if (!parent->isStyledElement())
+            return false;
+        if (parent->hasScopedHTMLStyleChild())
+            return false;
+        if (parent->inlineStyle())
+            return false;
+        if (parent->isSVGElement() && toSVGElement(parent)->animatedSMILStyleProperties())
+            return false;
+        if (parent->hasID() && m_features.idsInRules.contains(parent->idForStyleResolution().impl()))
+            return false;
+        if (parentElementPreventsSharing(parent))
+            return false;
     }
-    return toElement(node);
+
+    return true;
 }
 
 #ifdef STYLE_STATS
@@ -322,45 +279,29 @@ Element* SharedStyleFinder::searchDocumentForSharedStyle(const ElementResolveCon
 }
 #endif
 
+inline Element* SharedStyleFinder::findElementForStyleSharing(const ElementResolveContext& context) const
+{
+    StyleSharingList& styleSharingList = m_styleResolver->styleSharingList();
+    for (StyleSharingList::iterator it = styleSharingList.begin(); it != styleSharingList.end(); ++it) {
+        if (!canShareStyleWithElement(context, it->get()))
+            continue;
+        Element* element = it->get();
+        if (it != styleSharingList.begin()) {
+            // Move the element to the front of the LRU
+            styleSharingList.remove(it);
+            styleSharingList.prepend(element);
+        }
+        return element;
+    }
+    m_styleResolver->addToStyleSharingList(context.element());

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

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.

[leviw_travelin_and_unemployed, 2013/09/11 21:58:16]

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

+    return 0;
+}
+
 RenderStyle* SharedStyleFinder::locateSharedStyle(const ElementResolveContext& context, RenderStyle* newStyle)
 {
     STYLE_STATS_ADD_SEARCH();
-    if (!context.element() || !context.element()->isStyledElement())
-        return 0;
 
-    // If the element has inline style it is probably unique.
-    if (context.element()->inlineStyle())
-        return 0;
-    if (context.element()->isSVGElement() && toSVGElement(context.element())->animatedSMILStyleProperties())
-        return 0;
-    // Ids stop style sharing if they show up in the stylesheets.
-    if (context.element()->hasID() && m_features.idsInRules.contains(context.element()->idForStyleResolution().impl()))
-        return 0;
-    // Active and hovered elements always make a chain towards the document node
-    // and no siblings or cousins will have the same state.
-    if (context.element()->hovered())
-        return 0;
-    if (context.element()->active())
-        return 0;
-    // There is always only one focused element.
-    if (context.element()->focused())
-        return 0;
-    if (parentElementPreventsSharing(context.element()->parentElement()))
-        return 0;
-    if (context.element()->hasScopedHTMLStyleChild())
-        return 0;
-    if (context.element() == context.document().cssTarget())
-        return 0;
-    if (elementHasDirectionAuto(context.element()))
-        return 0;
-    if (context.element()->hasActiveAnimations())
-        return 0;
-    // When a dialog is first shown, its style is mutated to center it in the
-    // viewport. So the styles can't be shared since the viewport position and
-    // size may be different each time a dialog is opened.
-    if (context.element()->hasTagName(dialogTag))
-        return 0;
-    if (isShadowHost(context.element()) && context.element()->shadow()->containsActiveStyles())
+    if (!m_styleResolver->elementCanShareStyle(context.element()))
         return 0;
 
     STYLE_STATS_ADD_ELEMENT_ELIGIBLE_FOR_SHARING();
@@ -369,17 +310,7 @@ RenderStyle* SharedStyleFinder::locateSharedStyle(const ElementResolveContext& c
     // FIXME: This should be an explicit out parameter, instead of a member variable.
     m_elementAffectedByClassRules = context.element() && context.element()->hasClass() && classNamesAffectedByRules(context.element()->classNames());
 
-    // Check previous siblings and their cousins.
-    unsigned count = 0;
-    unsigned visitedNodeCount = 0;
-    Element* shareElement = 0;
-    Node* cousinList = context.element()->previousSibling();
-    while (cousinList) {
-        shareElement = findSiblingForStyleSharing(context, cousinList, count);
-        if (shareElement)
-            break;
-        cousinList = locateCousinList(cousinList->parentElement(), visitedNodeCount);
-    }
+    Element* shareElement = findElementForStyleSharing(context);
 
 #ifdef STYLE_STATS
     // FIXME: these stats don't to into account whether or not sibling/attribute