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 ee83ce26fadc855efcfe5b60788b01e685bf38d4..9382bcf1b190047d93d8ff7ef463ed42aad86330 100644
--- a/Source/core/css/resolver/SharedStyleFinder.cpp
+++ b/Source/core/css/resolver/SharedStyleFinder.cpp
@@ -56,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))
@@ -214,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())
@@ -296,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
@@ -323,10 +279,28 @@ Element* SharedStyleFinder::searchDocumentForSharedStyle(const ElementResolveCon
 }
 #endif
 
+inline Element* SharedStyleFinder::findElementForStyleSharing(const ElementResolveContext& context) const
+{
+    StyleSharingList& styleSharingList = m_styleResolver->styleSharingList();
+    for (StyleSharingList::iterator iter = styleSharingList.begin(); iter != styleSharingList.end(); ++iter) {

[esprehn, 2013/08/20 00:48:01]

I think we usually use "it" for iterators.

+        if (canShareStyleWithElement(context, iter->get())) {

[esprehn, 2013/08/20 00:48:01]

if (!...)
  continue;

would make this nicer since then the whole loop isn't indented.

[leviw_travelin_and_unemployed, 2013/08/20 00:54:09]

Sure.

+            Element* element = iter->get();
+            if (iter != styleSharingList.begin()) {
+                // Move the element to the front of the LRU
+                styleSharingList.remove(iter);
+                styleSharingList.prepend(element);
+            }
+            return element;
+        }
+    }
+    m_styleResolver->addToStyleSharingList(context.element());
+    return 0;
+}
+
 RenderStyle* SharedStyleFinder::locateSharedStyle(const ElementResolveContext& context, RenderStyle* newStyle)
 {
     STYLE_STATS_ADD_SEARCH();
-    if (!context.element() || !context.element()->isStyledElement())
+    if (!context.element() || !context.element()->isStyledElement() || !context.element()->parentElement())
         return 0;
 
     // If the element has inline style it is probably unique.
@@ -370,17 +344,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