Optimize matching of descendant selectors
authorantti@apple.com <antti@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 5 Feb 2011 11:23:43 +0000 (11:23 +0000)
committerantti@apple.com <antti@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 5 Feb 2011 11:23:43 +0000 (11:23 +0000)
https://bugs.webkit.org/show_bug.cgi?id=49876
<rdar://problem/8772822>

Reviewed by Dave Hyatt.

During style recalculation, maintain a filter of tags, ids and classes seen in ancestor elements.
Use the filter to quickly reject descendant and child selectors when doing style matching.

This speeds up style recalculations 3-6x on many major web sites.

* css/CSSStyleSelector.cpp:
(WebCore::RuleData::RuleData):
(WebCore::RuleData::descendantSelectorIdentifierHashes):
(WebCore::collectElementIdentifiers):
(WebCore::CSSStyleSelector::pushParent):
(WebCore::CSSStyleSelector::popParent):
(WebCore::CSSStyleSelector::fastRejectSelector):
(WebCore::CSSStyleSelector::matchRulesForList):
(WebCore::RuleData::collectDescendantSelectorIdentifierHashes):
* css/CSSStyleSelector.h:
(WebCore::CSSStyleSelector::ParentStackFrame::ParentStackFrame):
* dom/Element.cpp:
(WebCore::StyleSelectorParentPusher::StyleSelectorParentPusher):
(WebCore::StyleSelectorParentPusher::push):
(WebCore::StyleSelectorParentPusher::~StyleSelectorParentPusher):
(WebCore::Element::attach):
(WebCore::Element::recalcStyle):

git-svn-id: http://svn.webkit.org/repository/webkit/trunk@77740 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/WebCore/ChangeLog
Source/WebCore/css/CSSStyleSelector.cpp
Source/WebCore/css/CSSStyleSelector.h
Source/WebCore/dom/Element.cpp

index 6c2397e1ca08aab00aafe019d2126f08160bcfe1..aa552452e9c25af0b6d1030b0391e16bf6ffb046 100644 (file)
@@ -1,3 +1,34 @@
+2011-02-05  Antti Koivisto  <antti@apple.com>
+
+        Reviewed by Dave Hyatt.
+
+        Optimize matching of descendant selectors
+        https://bugs.webkit.org/show_bug.cgi?id=49876
+        <rdar://problem/8772822>
+        
+        During style recalculation, maintain a filter of tags, ids and classes seen in ancestor elements.
+        Use the filter to quickly reject descendant and child selectors when doing style matching.
+
+        This speeds up style recalculations 3-6x on many major web sites.
+
+        * css/CSSStyleSelector.cpp:
+        (WebCore::RuleData::RuleData):
+        (WebCore::RuleData::descendantSelectorIdentifierHashes):
+        (WebCore::collectElementIdentifiers):
+        (WebCore::CSSStyleSelector::pushParent):
+        (WebCore::CSSStyleSelector::popParent):
+        (WebCore::CSSStyleSelector::fastRejectSelector):
+        (WebCore::CSSStyleSelector::matchRulesForList):
+        (WebCore::RuleData::collectDescendantSelectorIdentifierHashes):
+        * css/CSSStyleSelector.h:
+        (WebCore::CSSStyleSelector::ParentStackFrame::ParentStackFrame):
+        * dom/Element.cpp:
+        (WebCore::StyleSelectorParentPusher::StyleSelectorParentPusher):
+        (WebCore::StyleSelectorParentPusher::push):
+        (WebCore::StyleSelectorParentPusher::~StyleSelectorParentPusher):
+        (WebCore::Element::attach):
+        (WebCore::Element::recalcStyle):
+
 2011-02-05  Nate Chapin  <japhet@chromium.org>
 
         Reviewed by Adam Barth.
index 7d8174a3d6147330aa9a69f745f9d1f20fd8b29c..c8cd991803432f13abb3b40b92bf0a2239b371db 100644 (file)
@@ -359,15 +359,23 @@ public:
         , m_selector(selector)
         , m_position(position)
     {
+        collectDescendantSelectorIdentifierHashes();
     }
+    void collectDescendantSelectorIdentifierHashes();
     unsigned position() const { return m_position; }
     CSSStyleRule* rule() const { return m_rule; }
     CSSSelector* selector() const { return m_selector; }
+    
+    // Try to balance between memory usage (there can be lots of RuleData objects) and good filtering performance.
+    static const unsigned maximumIdentifierCount = 4;
+    const unsigned* descendantSelectorIdentifierHashes() const { return m_descendantSelectorIdentifierHashes; }
 
 private:
     CSSStyleRule* m_rule;
     CSSSelector* m_selector;
     unsigned m_position;
+    // Use plain array instead of a Vector to minimize memory overhead.
+    unsigned m_descendantSelectorIdentifierHashes[maximumIdentifierCount];
 };
 
 class RuleSet {
@@ -642,6 +650,56 @@ static void loadViewSourceStyle()
     defaultViewSourceStyle = new RuleSet;
     defaultViewSourceStyle->addRulesFromSheet(parseUASheet(sourceUserAgentStyleSheet, sizeof(sourceUserAgentStyleSheet)), screenEval());
 }
+    
+static inline void collectElementIdentifierHashes(Element* element, Vector<unsigned, 4>& identifierHashes)
+{
+    identifierHashes.append(element->localName().impl()->existingHash());
+    if (element->hasID())
+        identifierHashes.append(element->idForStyleResolution().impl()->existingHash());
+    StyledElement* styledElement = element->isStyledElement() ? static_cast<StyledElement*>(element) : 0;
+    if (styledElement && styledElement->hasClass()) {
+        const SpaceSplitString& classNames = static_cast<StyledElement*>(element)->classNames();
+        size_t count = classNames.size();
+        for (size_t i = 0; i < count; ++i)
+            identifierHashes.append(classNames[i].impl()->existingHash());
+    }
+}
+    
+void CSSStyleSelector::pushParent(Element* parent)
+{
+    // If we are not invoked consistently for each parent, just pause maintaining the stack.
+    // There are all kinds of wacky special cases where the style recalc may temporarily branch to some random elements.
+    // FIXME: Perhaps we should fix up the stack instead? There is some danger of getting into O(n^2) situations doing that.
+    if (m_parentStack.isEmpty()) {
+        ASSERT(m_ancestorIdentifierFilter.isEmpty());
+        // We must start from the root.
+        if (parent->parentElement())
+            return;
+    } else if (m_parentStack.last().element != parent->parentElement())
+        return;
+
+    m_parentStack.append(ParentStackFrame(parent));
+    ParentStackFrame& parentFrame = m_parentStack.last();
+    // Mix tags, class names and ids into some sort of weird bouillabaisse.
+    // The filter is used for fast rejection of child and descendant selectors.
+    collectElementIdentifierHashes(parent, parentFrame.identifierHashes);
+    size_t count = parentFrame.identifierHashes.size();
+    for (size_t i = 0; i < count; ++i)
+        m_ancestorIdentifierFilter.add(parentFrame.identifierHashes[i]);
+}
+
+void CSSStyleSelector::popParent(Element* parent)
+{
+    if (m_parentStack.isEmpty() || m_parentStack.last().element != parent)
+        return;
+
+    const ParentStackFrame& parentFrame = m_parentStack.last();
+    size_t count = parentFrame.identifierHashes.size();
+    for (size_t i = 0; i < count; ++i)
+        m_ancestorIdentifierFilter.remove(parentFrame.identifierHashes[i]);
+    m_parentStack.removeLast();
+    ASSERT(!m_parentStack.isEmpty() || m_ancestorIdentifierFilter.isEmpty());
+}
 
 void CSSStyleSelector::addMatchedDeclaration(CSSMutableStyleDeclaration* decl)
 {
@@ -693,22 +751,37 @@ void CSSStyleSelector::matchRules(RuleSet* rules, int& firstRuleIndex, int& last
     }
 }
 
+inline bool CSSStyleSelector::fastRejectSelector(const RuleData& ruleData) const
+{
+    const unsigned* descendantSelectorIdentifierHashes = ruleData.descendantSelectorIdentifierHashes();
+    for (unsigned n = 0; n < RuleData::maximumIdentifierCount && descendantSelectorIdentifierHashes[n]; ++n) {
+        if (!m_ancestorIdentifierFilter.contains(descendantSelectorIdentifierHashes[n]))
+            return true;
+    }
+    return false;
+}
+
 void CSSStyleSelector::matchRulesForList(const Vector<RuleData>* rules, int& firstRuleIndex, int& lastRuleIndex, bool includeEmptyRules)
 {
     if (!rules)
         return;
+    // In some cases we may end up looking up style for random elements in the middle of a recursive tree resolve.
+    // Ancestor identifier filter won't be up-to-date in that case and we can't use the fast path.
+    bool canUseFastReject = !m_parentStack.isEmpty() && m_parentStack.last().element == m_parentNode;
+
     unsigned size = rules->size();
     for (unsigned i = 0; i < size; ++i) {
         const RuleData& ruleData = rules->at(i);
         CSSStyleRule* rule = ruleData.rule();
-        if (m_checker.m_sameOriginOnly && !m_checker.m_document->securityOrigin()->canRequest(rule->baseURL()))
-            continue; 
+        if (canUseFastReject && fastRejectSelector(ruleData))
+            continue;
         if (checkSelector(ruleData.selector())) {
             // If the rule has no properties to apply, then ignore it in the non-debug mode.
             CSSMutableStyleDeclaration* decl = rule->declaration();
             if (!decl || (!decl->length() && !includeEmptyRules))
                 continue;
-            
+            if (m_checker.m_sameOriginOnly && !m_checker.m_document->securityOrigin()->canRequest(rule->baseURL()))
+                continue; 
             // If we're matching normal rules, set a pseudo bit if 
             // we really just matched a pseudo-element.
             if (m_dynamicPseudo != NOPSEUDO && m_checker.m_pseudoStyle == NOPSEUDO) {
@@ -2851,6 +2924,36 @@ bool CSSStyleSelector::SelectorChecker::checkScrollbarPseudoClass(CSSSelector* s
 
 // -----------------------------------------------------------------
 
+inline void RuleData::collectDescendantSelectorIdentifierHashes()
+{
+    unsigned identifierCount = 0;
+    CSSSelector::Relation relation = m_selector->relation();
+    CSSSelector* selector = m_selector->tagHistory();
+    // Skip the topmost selector. It is handled quickly by the rule hashes.
+    for (; selector; selector = selector->tagHistory()) {
+        if (relation != CSSSelector::SubSelector)
+            break;
+        relation = selector->relation();
+    }
+    for (; selector; selector = selector->tagHistory()) {
+        // Only collect identifiers that match direct ancestors.
+        // FIXME: Intead of just stopping, this should skip over sibling selectors.
+        if (relation != CSSSelector::Descendant && relation != CSSSelector::Child && relation != CSSSelector::SubSelector)
+            break;
+        if ((selector->m_match == CSSSelector::Id || selector->m_match == CSSSelector::Class) && !selector->value().isEmpty())
+            m_descendantSelectorIdentifierHashes[identifierCount++] = selector->value().impl()->existingHash();
+        if (identifierCount == maximumIdentifierCount)
+            return;
+        const AtomicString& localName = selector->tag().localName();
+        if (localName != starAtom)
+            m_descendantSelectorIdentifierHashes[identifierCount++] = localName.impl()->existingHash();
+        if (identifierCount == maximumIdentifierCount)
+            return;
+        relation = selector->relation();
+    }
+    m_descendantSelectorIdentifierHashes[identifierCount] = 0;
+}
+
 RuleSet::RuleSet()
     : m_ruleCount(0)
     , m_autoShrinkToFitEnabled(true)
index cfde5d0e9d8c183e1c8a74d42df4995a4329a3cc..18606234c79b80a23dd2c03a6a2a4df51b6a5735 100644 (file)
@@ -27,6 +27,7 @@
 #include "LinkHash.h"
 #include "MediaQueryExp.h"
 #include "RenderStyle.h"
+#include <wtf/HashCountedSet.h>
 #include <wtf/HashMap.h>
 #include <wtf/HashSet.h>
 #include <wtf/RefPtr.h>
@@ -89,6 +90,10 @@ public:
                          CSSStyleSheet* pageUserSheet, const Vector<RefPtr<CSSStyleSheet> >* pageGroupUserSheets,
                          bool strictParsing, bool matchAuthorAndUserStyles);
         ~CSSStyleSelector();
+        
+        // Using these during tree walk will allow style selector to optimize child and descendant selector lookups.
+        void pushParent(Element* parent);
+        void popParent(Element* parent);
 
         PassRefPtr<RenderStyle> styleForElement(Element* e, RenderStyle* parentStyle = 0, bool allowSharing = true, bool resolveForRootDefault = false, bool matchVisitedPseudoClass = false);
         
@@ -186,6 +191,7 @@ public:
 
         void matchRules(RuleSet*, int& firstRuleIndex, int& lastRuleIndex, bool includeEmptyRules);
         void matchRulesForList(const Vector<RuleData>*, int& firstRuleIndex, int& lastRuleIndex, bool includeEmptyRules);
+        bool fastRejectSelector(const RuleData&) const;
         void sortMatchedRules(unsigned start, unsigned end);
 
         template <bool firstPass>
@@ -203,6 +209,15 @@ public:
         
         OwnPtr<RuleSet> m_siblingRules;
         HashSet<AtomicStringImpl*> m_idsInRules;
+        
+        struct ParentStackFrame {
+            ParentStackFrame(Element* element) : element(element) {}
+            Element* element;
+            Vector<unsigned, 4> identifierHashes;
+        };
+        Vector<ParentStackFrame> m_parentStack;
+        // FIXME: Replace this with a bloom filter.
+        HashCountedSet<unsigned, AlreadyHashed> m_ancestorIdentifierFilter;
 
         bool m_hasUAAppearance;
         BorderData m_borderData;
index c62ae49bf268df64331b9acd0b25091a51b7b988..4da79eb8f1f520b21aa1e251df8caa71bb7537f1 100644 (file)
@@ -68,6 +68,33 @@ namespace WebCore {
 using namespace HTMLNames;
 using namespace XMLNames;
     
+class StyleSelectorParentPusher {
+public:
+    StyleSelectorParentPusher(CSSStyleSelector* styleSelector, Element* parent)
+        : m_styleSelector(styleSelector)
+        , m_parent(parent)
+        , m_didPush(false) 
+    {
+    }
+    void push()
+    {
+        if (m_didPush)
+            return;
+        m_styleSelector->pushParent(m_parent);
+        m_didPush = true;
+    }
+    ~StyleSelectorParentPusher() 
+    {
+        if (m_didPush)
+            m_styleSelector->popParent(m_parent); 
+    }
+
+private:
+    CSSStyleSelector* m_styleSelector;
+    Element* m_parent;
+    bool m_didPush;
+};
+    
 PassRefPtr<Element> Element::create(const QualifiedName& tagName, Document* document)
 {
     return adoptRef(new Element(tagName, document, CreateElement));
@@ -917,9 +944,15 @@ void Element::attach()
     RenderWidget::suspendWidgetHierarchyUpdates();
 
     createRendererIfNeeded();
+    
+    StyleSelectorParentPusher parentPusher(document()->styleSelector(), this);
+    if (firstChild())
+        parentPusher.push();
     ContainerNode::attach();
-    if (Node* shadow = shadowRoot())
+    if (Node* shadow = shadowRoot()) {
+        parentPusher.push();
         shadow->attach();
+    }
     if (hasRareData()) {   
         ElementRareData* data = rareData();
         if (data->needsFocusAppearanceUpdateSoonAfterAttach()) {
@@ -1059,7 +1092,7 @@ void Element::recalcStyle(StyleChange change)
                 change = ch;
         }
     }
-
+    StyleSelectorParentPusher parentPusher(document()->styleSelector(), this);
     // FIXME: This check is good enough for :hover + foo, but it is not good enough for :hover + foo + bar.
     // For now we will just worry about the common case, since it's a lot trickier to get the second case right
     // without doing way too much re-resolution.
@@ -1068,15 +1101,19 @@ void Element::recalcStyle(StyleChange change)
         bool childRulesChanged = n->needsStyleRecalc() && n->styleChangeType() == FullStyleChange;
         if (forceCheckOfNextElementSibling && n->isElementNode())
             n->setNeedsStyleRecalc();
-        if (change >= Inherit || n->isTextNode() || n->childNeedsStyleRecalc() || n->needsStyleRecalc())
+        if (change >= Inherit || n->isTextNode() || n->childNeedsStyleRecalc() || n->needsStyleRecalc()) {
+            parentPusher.push();
             n->recalcStyle(change);
+        }
         if (n->isElementNode())
             forceCheckOfNextElementSibling = childRulesChanged && hasDirectAdjacentRules;
     }
     // FIXME: This does not care about sibling combinators. Will be necessary in XBL2 world.
     if (Node* shadow = shadowRoot()) {
-        if (change >= Inherit || shadow->isTextNode() || shadow->childNeedsStyleRecalc() || shadow->needsStyleRecalc())
+        if (change >= Inherit || shadow->isTextNode() || shadow->childNeedsStyleRecalc() || shadow->needsStyleRecalc()) {
+            parentPusher.push();
             shadow->recalcStyle(change);
+        }
     }
 
     clearNeedsStyleRecalc();