Replace style sharing cousin list search with LRU

Source/core/css/resolver/StyleResolver.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 223 matching lines @@
 void StyleResolver::collectFeatures()
 {
     m_features.clear();
     m_ruleSets.collectFeaturesTo(m_features, document().isViewSource());
     m_styleTree.collectFeaturesTo(m_features);
 
     m_siblingRuleSet = makeRuleSet(m_features.siblingRules);
     m_uncommonAttributeRuleSet = makeRuleSet(m_features.uncommonAttributeRules);
 }
 
+bool StyleResolver::supportsStyleSharing(Element* element)
+{
+    if (!element || !element->isStyledElement() || !element->parentElement())
+        return false;
+
+    // If the element has inline style it is probably unique.
+    if (element->inlineStyle())
+        return false;
+    if (element->isSVGElement() && toSVGElement(element)->animatedSMILStyleProperties())
+        return false;
+    // Ids stop style sharing if they show up in the stylesheets.
+    if (element->hasID() && m_features.idsInRules.contains(element->idForStyleResolution().impl()))
+        return false;
+    // Active and hovered elements always make a chain towards the document node
+    // and no siblings or cousins will have the same state.
+    if (element->hovered())
+        return false;
+    if (element->active())
+        return false;
+    // There is always only one focused element.
+    if (element->focused())
+        return false;
+    if (element->parentElement()->hasFlagsSetDuringStylingOfChildren())
+        return false;
+    if (element->hasScopedHTMLStyleChild())
+        return false;
+    if (element == m_document.cssTarget())
+        return false;
+    if (element->isHTMLElement() && toHTMLElement(element)->hasDirectionAuto())
+        return false;
+    if (element->hasActiveAnimations())
+        return false;
+    // 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 (element->hasTagName(dialogTag))
+        return false;
+    if (isShadowHost(element) && element->shadow()->containsActiveStyles())
+        return false;
+    return true;
+}
+
+void StyleResolver::addToStyleSharingList(Element* element)
+{
+    if (m_styleSharingList.size() >= styleSharingListSize)
+        m_styleSharingList.remove(--m_styleSharingList.end());
+    m_styleSharingList.prepend(element);
+}
+
+void StyleResolver::clearStyleSharingList()
+{
+    m_styleSharingList.clear();
+}
+
 void StyleResolver::pushParentElement(Element* parent)
 {
     ASSERT(parent);
     const ContainerNode* parentsParent = parent->parentOrShadowHostElement();
 
     // We are not always invoked consistently. For example, script execution can cause us to enter
     // style recalc in the middle of tree building. We may also be invoked from somewhere within the tree.
     // Reset the stack in this case, or if we see a new root element.
     // Otherwise just push the new parent.
     if (!parentsParent || m_selectorFilter.parentStackIsEmpty())
@@ skipping 1258 matching lines @@
         m_matchedPropertiesSearches, m_matchedPropertiesHit, m_matchedPropertiesSharedInheritedHit, m_matchedPropertiesToCache, m_matchedPropertiesEnteredIntoCache);
 
     fprintf(stderr, "Total:\n");
     printStyleStats(m_totalSearches, m_totalElementsEligibleForSharing, m_totalStylesShared, m_totalSearchFoundSiblingForSharing, m_totalSearchesMissedSharing,
         m_totalMatchedPropertiesSearches, m_totalMatchedPropertiesHit, m_totalMatchedPropertiesSharedInheritedHit, m_totalMatchedPropertiesToCache, m_totalMatchedPropertiesEnteredIntoCache);
     fprintf(stderr, "--------------------------------------------------------------------------------\n");
 }
 #endif
 
 } // namespace WebCore