Revert "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 d3899ad104264c3fedf910cce73c48442e7ecf42..ee83ce26fadc855efcfe5b60788b01e685bf38d4 100644
--- a/Source/core/css/resolver/SharedStyleFinder.cpp
+++ b/Source/core/css/resolver/SharedStyleFinder.cpp
@@ -56,11 +56,64 @@ 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))
@@ -161,16 +214,9 @@ 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())
@@ -250,24 +296,22 @@ bool SharedStyleFinder::canShareStyleWithElement(const ElementResolveContext& co
             return false;
     }
 
-    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 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;
+    }
+    return toElement(node);
+}
+
 #ifdef STYLE_STATS
 Element* SharedStyleFinder::searchDocumentForSharedStyle(const ElementResolveContext& context) const
 {
@@ -279,28 +323,10 @@ 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) {
-        if (canShareStyleWithElement(context, *iter)) {
-            Element* element = *iter;
-            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() || !context.element()->parentElement())
+    if (!context.element() || !context.element()->isStyledElement())
         return 0;
 
     // If the element has inline style it is probably unique.
@@ -344,7 +370,17 @@ 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());
 
-    Element* shareElement = findElementForStyleSharing(context);
+    // 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);
+    }
 
 #ifdef STYLE_STATS
     // FIXME: these stats don't to into account whether or not sibling/attribute