Use bloom filter for descendant selector filtering
[WebKit.git] / Source / WebCore / css / CSSStyleSelector.h
index e035af2778e5d628f41e3c3496d45a8166ae4d13..a89c080bf733c311093736b66da3a5d7492ccb9e 100644 (file)
@@ -27,6 +27,7 @@
 #include "LinkHash.h"
 #include "MediaQueryExp.h"
 #include "RenderStyle.h"
+#include <wtf/BloomFilter.h>
 #include <wtf/HashMap.h>
 #include <wtf/HashSet.h>
 #include <wtf/RefPtr.h>
@@ -42,10 +43,7 @@ class CSSProperty;
 class CSSFontFace;
 class CSSFontFaceRule;
 class CSSImageValue;
-class CSSRuleData;
-class CSSRuleDataList;
 class CSSRuleList;
-class CSSRuleSet;
 class CSSSelector;
 class CSSStyleRule;
 class CSSStyleSheet;
@@ -61,6 +59,8 @@ class KeyframeList;
 class KeyframeValue;
 class MediaQueryEvaluator;
 class Node;
+class RuleData;
+class RuleSet;
 class Settings;
 class StyleImage;
 class StyleSheet;
@@ -90,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);
         
@@ -182,28 +186,40 @@ public:
 
         void adjustRenderStyle(RenderStyle* styleToAdjust, RenderStyle* parentStyle, Element*);
 
-        void addMatchedRule(CSSRuleData* rule) { m_matchedRules.append(rule); }
+        void addMatchedRule(const RuleData* rule) { m_matchedRules.append(rule); }
         void addMatchedDeclaration(CSSMutableStyleDeclaration* decl);
 
-        void matchRules(CSSRuleSet*, int& firstRuleIndex, int& lastRuleIndex, bool includeEmptyRules);
-        void matchRulesForList(CSSRuleDataList*, int& firstRuleIndex, int& lastRuleIndex, bool includeEmptyRules);
+        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>
         void applyDeclarations(bool important, int startIndex, int endIndex);
 
-        void matchPageRules(CSSRuleSet*, bool isLeftPage, bool isFirstPage, const String& pageName);
-        void matchPageRulesForList(CSSRuleDataList*, bool isLeftPage, bool isFirstPage, const String& pageName);
+        void matchPageRules(RuleSet*, bool isLeftPage, bool isFirstPage, const String& pageName);
+        void matchPageRulesForList(const Vector<RuleData>*, bool isLeftPage, bool isFirstPage, const String& pageName);
         bool isLeftPage(int pageIndex) const;
         bool isRightPage(int pageIndex) const { return !isLeftPage(pageIndex); }
         bool isFirstPage(int pageIndex) const;
         String pageName(int pageIndex) const;
         
-        OwnPtr<CSSRuleSet> m_authorStyle;
-        OwnPtr<CSSRuleSet> m_userStyle;
+        OwnPtr<RuleSet> m_authorStyle;
+        OwnPtr<RuleSet> m_userStyle;
         
-        OwnPtr<CSSRuleSet> m_siblingRules;
+        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;
+        
+        // With 100 unique strings in the filter, 2^12 slot table has false positive rate of ~0.2%.
+        static const unsigned bloomFilterKeyBits = 12;
+        OwnPtr<BloomFilter<bloomFilterKeyBits> > m_ancestorIdentifierFilter;
 
         bool m_hasUAAppearance;
         BorderData m_borderData;
@@ -293,7 +309,7 @@ public:
 
         // A buffer used to hold the set of matched rules for an element, and a temporary buffer used for
         // merge sorting.
-        Vector<CSSRuleData*, 32> m_matchedRules;
+        Vector<const RuleData*, 32> m_matchedRules;
 
         RefPtr<CSSRuleList> m_ruleList;