Revert "Replace style sharing cousin list search with LRU"

Source/core/css/resolver/SharedStyleFinder.cpp

 /*
  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
  *           (C) 2004-2005 Allan Sandfeld Jensen (kde@carewolf.com)
  * Copyright (C) 2006, 2007 Nicholas Shanks (webkit@nickshanks.com)
  * Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013 Apple Inc. All rights reserved.
  * Copyright (C) 2007 Alexey Proskuryakov <ap@webkit.org>
  * Copyright (C) 2007, 2008 Eric Seidel <eric@webkit.org>
  * Copyright (C) 2008, 2009 Torch Mobile Inc. All rights reserved. (http://www.torchmobile.com/)
  * Copyright (c) 2011, Code Aurora Forum. All rights reserved.
  * Copyright (C) Research In Motion Limited 2011. All rights reserved.
@@ skipping 38 matching lines @@
 #include "core/html/track/WebVTTElement.h"
 #include "core/rendering/style/RenderStyle.h"
 #include "core/svg/SVGElement.h"
 #include "wtf/HashSet.h"
 #include "wtf/text/AtomicString.h"
 
 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))
         return false;
 
     HTMLInputElement* thisInputElement = toHTMLInputElement(element);
     HTMLInputElement* otherInputElement = toHTMLInputElement(context.element());
     if (thisInputElement->elementData() != otherInputElement->elementData()) {
         if (thisInputElement->fastGetAttribute(typeAttr) != otherInputElement->fastGetAttribute(typeAttr))
             return false;
@@ skipping 80 matching lines @@
     if (context.element()->hasTagName(progressTag)) {
         if (context.element()->shouldAppearIndeterminate() != sharingCandidate->shouldAppearIndeterminate())
             return false;
     }
 
     return true;
 }
 
 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())
         return false;
     if (element->tagQName() != context.element()->tagQName())
         return false;
     if (element->inlineStyle())
         return false;
     if (element->needsStyleRecalc())
         return false;
@@ skipping 59 matching lines @@
         return false;
 
     if (element->isWebVTTElement() && context.element()->isWebVTTElement() && toWebVTTElement(element)->isPastNode() != toWebVTTElement(context.element())->isPastNode())
         return false;
 
     if (FullscreenElementStack* fullscreen = FullscreenElementStack::fromIfExists(context.document())) {
         if (element == fullscreen->webkitCurrentFullScreenElement() || context.element() == fullscreen->webkitCurrentFullScreenElement())
             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
 {
     for (Element* element = context.element()->document()->documentElement(); element; element = ElementTraversal::next(element)) {
         if (canShareStyleWithElement(context, element))
             return element;
     }
     return 0;
 }
 #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.
     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;
@@ skipping 23 matching lines @@
         return 0;
     if (isShadowHost(context.element()) && context.element()->shadow()->containsActiveStyles())
         return 0;
 
     STYLE_STATS_ADD_ELEMENT_ELIGIBLE_FOR_SHARING();
 
     // Cache whether context.element() is affected by any known class selectors.
     // 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
     // rules prevent these nodes from actually sharing
     if (shareElement) {
         STYLE_STATS_ADD_SEARCH_FOUND_SIBLING_FOR_SHARING();
     } else {
         shareElement = searchDocumentForSharedStyle(context);
         if (shareElement)
             STYLE_STATS_ADD_SEARCH_MISSED_SHARING();
@@ skipping 12 matching lines @@
     if (m_styleResolver->styleSharingCandidateMatchesRuleSet(context, newStyle, m_uncommonAttributeRuleSet))
         return 0;
     // Tracking child index requires unique style for each node. This may get set by the sibling rule match above.
     if (parentElementPreventsSharing(context.element()->parentElement()))
         return 0;
     STYLE_STATS_ADD_STYLE_SHARED();
     return shareElement->renderStyle();
 }
 
 }