Diff
Modified: trunk/Source/WebCore/CMakeLists.txt (138431 => 138432)
--- trunk/Source/WebCore/CMakeLists.txt 2012-12-24 04:43:23 UTC (rev 138431)
+++ trunk/Source/WebCore/CMakeLists.txt 2012-12-24 05:05:13 UTC (rev 138432)
@@ -1078,6 +1078,7 @@
css/RuleSet.h
css/RuleSet.cpp
css/SelectorChecker.cpp
+ css/SelectorFilter.cpp
css/ShadowValue.cpp
css/StyleBuilder.cpp
css/StyleInvalidationAnalysis.cpp
Modified: trunk/Source/WebCore/ChangeLog (138431 => 138432)
--- trunk/Source/WebCore/ChangeLog 2012-12-24 04:43:23 UTC (rev 138431)
+++ trunk/Source/WebCore/ChangeLog 2012-12-24 05:05:13 UTC (rev 138432)
@@ -1,3 +1,34 @@
+2012-12-23 Dimitri Glazkov <dglaz...@chromium.org>
+
+ Split fast-rejection filter logic off SelectorChecker.
+ https://bugs.webkit.org/show_bug.cgi?id=105660
+
+ The awesome Bloom filter and parent stack logic don't need to be in SelectorChecker. They nicely factor out
+ into their own pretty thing, named thereby SelectorFilter.
+
+ Reviewed by Eric Seidel.
+
+ No change in functionality, covered by existing tests.
+
+ * CMakeLists.txt: Added SelectorFilter to build systems.
+ * GNUmakefile.list.am: Ditto.
+ * Target.pri: Ditto.
+ * WebCore.gypi: Ditto.
+ * WebCore.xcodeproj/project.pbxproj: Ditto.
+ * css/CSSAllInOne.cpp: Ditto.
+ * css/RuleSet.cpp: Changed to use SelectorFilter.
+ (WebCore::RuleData::RuleData): Ditto.
+ * css/SelectorChecker.cpp: Ditto.
+ * css/SelectorChecker.h: Ditto.
+ (SelectorChecker):
+ * css/StyleResolver.cpp: Ditto.
+ (WebCore):
+ (WebCore::StyleResolver::pushParentElement): Ditto.
+ (WebCore::StyleResolver::popParentElement): Ditto.
+ (WebCore::StyleResolver::collectMatchingRulesForList): Ditto.
+ * css/StyleResolver.h:
+ (StyleResolver): Ditto.
+
2012-12-23 Qiankun Miao <qiankun.m...@intel.com>
Remove unused reference to "class LayerChromium"
Modified: trunk/Source/WebCore/GNUmakefile.list.am (138431 => 138432)
--- trunk/Source/WebCore/GNUmakefile.list.am 2012-12-24 04:43:23 UTC (rev 138431)
+++ trunk/Source/WebCore/GNUmakefile.list.am 2012-12-24 05:05:13 UTC (rev 138432)
@@ -2631,6 +2631,8 @@
Source/WebCore/css/RuleSet.h \
Source/WebCore/css/SelectorChecker.cpp \
Source/WebCore/css/SelectorChecker.h \
+ Source/WebCore/css/SelectorFilter.cpp \
+ Source/WebCore/css/SelectorFilter.h \
Source/WebCore/css/ShadowValue.cpp \
Source/WebCore/css/ShadowValue.h \
Source/WebCore/css/SiblingTraversalStrategies.h \
Modified: trunk/Source/WebCore/Target.pri (138431 => 138432)
--- trunk/Source/WebCore/Target.pri 2012-12-24 04:43:23 UTC (rev 138431)
+++ trunk/Source/WebCore/Target.pri 2012-12-24 05:05:13 UTC (rev 138432)
@@ -306,6 +306,7 @@
css/RuleFeature.cpp \
css/RuleSet.cpp \
css/SelectorChecker.cpp \
+ css/SelectorFilter.cpp \
css/ShadowValue.cpp \
css/StyleBuilder.cpp \
css/StyleInvalidationAnalysis.cpp \
Modified: trunk/Source/WebCore/WebCore.gypi (138431 => 138432)
--- trunk/Source/WebCore/WebCore.gypi 2012-12-24 04:43:23 UTC (rev 138431)
+++ trunk/Source/WebCore/WebCore.gypi 2012-12-24 05:05:13 UTC (rev 138432)
@@ -1549,6 +1549,8 @@
'css/SVGCSSStyleSelector.cpp',
'css/SelectorChecker.cpp',
'css/SelectorChecker.h',
+ 'css/SelectorFilter.cpp',
+ 'css/SelectorFilter.h',
'css/ShadowValue.cpp',
'css/ShadowValue.h',
'css/SiblingTraversalStrategies.h',
Modified: trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj (138431 => 138432)
--- trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj 2012-12-24 04:43:23 UTC (rev 138431)
+++ trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj 2012-12-24 05:05:13 UTC (rev 138432)
@@ -1060,6 +1060,8 @@
4138D3361244054800323D33 /* EventContext.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 4138D3341244054800323D33 /* EventContext.cpp */; };
414B867313AD074E00B4B373 /* FileIconLoader.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 414B867113AD074E00B4B373 /* FileIconLoader.cpp */; };
414B867413AD074E00B4B373 /* FileIconLoader.h in Headers */ = {isa = PBXBuildFile; fileRef = 414B867213AD074E00B4B373 /* FileIconLoader.h */; settings = {ATTRIBUTES = (Private, ); }; };
+ 415071571685067300C3C7B3 /* SelectorFilter.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 415071551685067300C3C7B3 /* SelectorFilter.cpp */; };
+ 415071581685067300C3C7B3 /* SelectorFilter.h in Headers */ = {isa = PBXBuildFile; fileRef = 415071561685067300C3C7B3 /* SelectorFilter.h */; };
4150F9F112B6E0E70008C860 /* SliderThumbElement.h in Headers */ = {isa = PBXBuildFile; fileRef = 4150F9EF12B6E0E70008C860 /* SliderThumbElement.h */; };
4150F9F212B6E0E70008C860 /* SliderThumbElement.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 4150F9F012B6E0E70008C860 /* SliderThumbElement.cpp */; };
4157AF8012F1FB0400A8C6F5 /* MediaControlsApple.h in Headers */ = {isa = PBXBuildFile; fileRef = 4157AF7E12F1FB0400A8C6F5 /* MediaControlsApple.h */; };
@@ -8288,6 +8290,8 @@
4138D3341244054800323D33 /* EventContext.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = EventContext.cpp; sourceTree = "<group>"; };
414B867113AD074E00B4B373 /* FileIconLoader.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = FileIconLoader.cpp; sourceTree = "<group>"; };
414B867213AD074E00B4B373 /* FileIconLoader.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = FileIconLoader.h; sourceTree = "<group>"; };
+ 415071551685067300C3C7B3 /* SelectorFilter.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = SelectorFilter.cpp; sourceTree = "<group>"; };
+ 415071561685067300C3C7B3 /* SelectorFilter.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SelectorFilter.h; sourceTree = "<group>"; };
4150F9EF12B6E0E70008C860 /* SliderThumbElement.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SliderThumbElement.h; sourceTree = "<group>"; };
4150F9F012B6E0E70008C860 /* SliderThumbElement.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = SliderThumbElement.cpp; sourceTree = "<group>"; };
4157AF7E12F1FB0400A8C6F5 /* MediaControlsApple.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = MediaControlsApple.h; sourceTree = "<group>"; };
@@ -21580,6 +21584,8 @@
A79BADA0161E7F3F00C2E652 /* RuleSet.h */,
E44B4BB1141650D7002B1D8B /* SelectorChecker.cpp */,
E44B4BB2141650D7002B1D8B /* SelectorChecker.h */,
+ 415071551685067300C3C7B3 /* SelectorFilter.cpp */,
+ 415071561685067300C3C7B3 /* SelectorFilter.h */,
A80E6CCA0A1989CA007FB8C5 /* ShadowValue.cpp */,
A80E6CBE0A1989CA007FB8C5 /* ShadowValue.h */,
5728BD9D1625369600C40B56 /* SiblingTraversalStrategies.h */,
@@ -25985,6 +25991,7 @@
0FB8890A167D2FA10010CDA5 /* ScrollingTreeStickyNode.h in Headers */,
0FB8890F167D30160010CDA5 /* ScrollingStateStickyNode.h in Headers */,
E13EF3441684ECF40034C83F /* NetworkStorageSession.h in Headers */,
+ 415071581685067300C3C7B3 /* SelectorFilter.h in Headers */,
);
runOnlyForDeploymentPostprocessing = 0;
};
@@ -29104,6 +29111,7 @@
0FB8890E167D30160010CDA5 /* ScrollingStateStickyNode.cpp in Sources */,
209B456B16796A7E00E54E4E /* JSCryptoCustom.cpp in Sources */,
E13EF34916850C470034C83F /* NetworkStorageSessionCFNet.cpp in Sources */,
+ 415071571685067300C3C7B3 /* SelectorFilter.cpp in Sources */,
);
runOnlyForDeploymentPostprocessing = 0;
};
Modified: trunk/Source/WebCore/css/CSSAllInOne.cpp (138431 => 138432)
--- trunk/Source/WebCore/css/CSSAllInOne.cpp 2012-12-24 04:43:23 UTC (rev 138431)
+++ trunk/Source/WebCore/css/CSSAllInOne.cpp 2012-12-24 05:05:13 UTC (rev 138432)
@@ -68,6 +68,7 @@
#include "CSSValuePool.cpp"
#include "RuleFeature.cpp"
#include "RuleSet.cpp"
+#include "SelectorFilter.cpp"
#include "StyleBuilder.cpp"
#include "StylePropertySet.cpp"
#include "StylePropertyShorthand.cpp"
Modified: trunk/Source/WebCore/css/RuleSet.cpp (138431 => 138432)
--- trunk/Source/WebCore/css/RuleSet.cpp 2012-12-24 04:43:23 UTC (rev 138431)
+++ trunk/Source/WebCore/css/RuleSet.cpp 2012-12-24 05:05:13 UTC (rev 138432)
@@ -36,6 +36,7 @@
#include "MediaQueryEvaluator.h"
#include "SecurityOrigin.h"
#include "SelectorChecker.h"
+#include "SelectorFilter.h"
#include "StyleResolver.h"
#include "StyleRule.h"
#include "StyleRuleImport.h"
@@ -122,7 +123,7 @@
{
ASSERT(m_position == position);
ASSERT(m_selectorIndex == selectorIndex);
- SelectorChecker::collectIdentifierHashes(selector(), m_descendantSelectorIdentifierHashes, maximumIdentifierCount);
+ SelectorFilter::collectIdentifierHashes(selector(), m_descendantSelectorIdentifierHashes, maximumIdentifierCount);
}
void RuleData::reportMemoryUsage(MemoryObjectInfo* memoryObjectInfo) const
Modified: trunk/Source/WebCore/css/SelectorChecker.cpp (138431 => 138432)
--- trunk/Source/WebCore/css/SelectorChecker.cpp 2012-12-24 04:43:23 UTC (rev 138431)
+++ trunk/Source/WebCore/css/SelectorChecker.cpp 2012-12-24 05:05:13 UTC (rev 138432)
@@ -77,136 +77,6 @@
{
}
-// Salt to separate otherwise identical string hashes so a class-selector like .article won't match <article> elements.
-enum { TagNameSalt = 13, IdAttributeSalt = 17, ClassAttributeSalt = 19 };
-
-static inline void collectElementIdentifierHashes(const Element* element, Vector<unsigned, 4>& identifierHashes)
-{
- identifierHashes.append(element->localName().impl()->existingHash() * TagNameSalt);
- if (element->hasID())
- identifierHashes.append(element->idForStyleResolution().impl()->existingHash() * IdAttributeSalt);
- const StyledElement* styledElement = element->isStyledElement() ? static_cast<const StyledElement*>(element) : 0;
- if (styledElement && styledElement->hasClass()) {
- const SpaceSplitString& classNames = styledElement->classNames();
- size_t count = classNames.size();
- for (size_t i = 0; i < count; ++i)
- identifierHashes.append(classNames[i].impl()->existingHash() * ClassAttributeSalt);
- }
-}
-
-void SelectorChecker::pushParentStackFrame(Element* parent)
-{
- ASSERT(m_ancestorIdentifierFilter);
- ASSERT(m_parentStack.isEmpty() || m_parentStack.last().element == parent->parentOrHostElement());
- ASSERT(!m_parentStack.isEmpty() || !parent->parentOrHostElement());
- 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 SelectorChecker::popParentStackFrame()
-{
- ASSERT(!m_parentStack.isEmpty());
- ASSERT(m_ancestorIdentifierFilter);
- 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();
- if (m_parentStack.isEmpty()) {
- ASSERT(m_ancestorIdentifierFilter->likelyEmpty());
- m_ancestorIdentifierFilter.clear();
- }
-}
-
-void SelectorChecker::setupParentStack(Element* parent)
-{
- ASSERT(m_parentStack.isEmpty() == !m_ancestorIdentifierFilter);
- // Kill whatever we stored before.
- m_parentStack.shrink(0);
- m_ancestorIdentifierFilter = adoptPtr(new BloomFilter<bloomFilterKeyBits>);
- // Fast version if parent is a root element:
- if (!parent->parentOrHostNode()) {
- pushParentStackFrame(parent);
- return;
- }
- // Otherwise climb up the tree.
- Vector<Element*, 30> ancestors;
- for (Element* ancestor = parent; ancestor; ancestor = ancestor->parentOrHostElement())
- ancestors.append(ancestor);
- for (size_t n = ancestors.size(); n; --n)
- pushParentStackFrame(ancestors[n - 1]);
-}
-
-void SelectorChecker::pushParent(Element* parent)
-{
- ASSERT(m_ancestorIdentifierFilter);
- // We may get invoked for some random elements in some wacky cases during style resolve.
- // Pause maintaining the stack in this case.
- if (m_parentStack.last().element != parent->parentOrHostElement())
- return;
- pushParentStackFrame(parent);
-}
-
-static inline void collectDescendantSelectorIdentifierHashes(const CSSSelector* selector, unsigned*& hash, const unsigned* end)
-{
- switch (selector->m_match) {
- case CSSSelector::Id:
- if (!selector->value().isEmpty())
- (*hash++) = selector->value().impl()->existingHash() * IdAttributeSalt;
- break;
- case CSSSelector::Class:
- if (!selector->value().isEmpty())
- (*hash++) = selector->value().impl()->existingHash() * ClassAttributeSalt;
- break;
- default:
- break;
- }
- if (hash == end)
- return;
- const AtomicString& localName = selector->tag().localName();
- if (localName != starAtom)
- (*hash++) = localName.impl()->existingHash() * TagNameSalt;
-}
-
-void SelectorChecker::collectIdentifierHashes(const CSSSelector* selector, unsigned* identifierHashes, unsigned maximumIdentifierCount)
-{
- unsigned* hash = identifierHashes;
- unsigned* end = identifierHashes + maximumIdentifierCount;
- CSSSelector::Relation relation = selector->relation();
-
- // Skip the topmost selector. It is handled quickly by the rule hashes.
- bool skipOverSubselectors = true;
- for (selector = selector->tagHistory(); selector; selector = selector->tagHistory()) {
- // Only collect identifiers that match ancestors.
- switch (relation) {
- case CSSSelector::SubSelector:
- if (!skipOverSubselectors)
- collectDescendantSelectorIdentifierHashes(selector, hash, end);
- break;
- case CSSSelector::DirectAdjacent:
- case CSSSelector::IndirectAdjacent:
- case CSSSelector::ShadowDescendant:
- skipOverSubselectors = true;
- break;
- case CSSSelector::Descendant:
- case CSSSelector::Child:
- skipOverSubselectors = false;
- collectDescendantSelectorIdentifierHashes(selector, hash, end);
- break;
- }
- if (hash == end)
- return;
- relation = selector->relation();
- }
- *hash = 0;
-}
-
static inline const AtomicString* linkAttribute(Element* element)
{
if (!element->isLink())
Modified: trunk/Source/WebCore/css/SelectorChecker.h (138431 => 138432)
--- trunk/Source/WebCore/css/SelectorChecker.h 2012-12-24 04:43:23 UTC (rev 138431)
+++ trunk/Source/WebCore/css/SelectorChecker.h 2012-12-24 05:05:13 UTC (rev 138432)
@@ -35,7 +35,6 @@
#include "RenderStyleConstants.h"
#include "SpaceSplitString.h"
#include "StyledElement.h"
-#include <wtf/BloomFilter.h>
#include <wtf/HashSet.h>
#include <wtf/Vector.h>
@@ -89,16 +88,6 @@
static bool isFastCheckableSelector(const CSSSelector*);
bool fastCheckSelector(const CSSSelector*, const Element*) const;
- template <unsigned maximumIdentifierCount>
- inline bool fastRejectSelector(const unsigned* identifierHashes) const;
- static void collectIdentifierHashes(const CSSSelector*, unsigned* identifierHashes, unsigned maximumIdentifierCount);
-
- void setupParentStack(Element* parent);
- void pushParent(Element* parent);
- void popParent() { popParentStackFrame(); }
- bool parentStackIsEmpty() const { return m_parentStack.isEmpty(); }
- bool parentStackIsConsistent(const ContainerNode* parentNode) const { return !m_parentStack.isEmpty() && m_parentStack.last().element == parentNode; }
-
EInsideLink determineLinkState(Element*) const;
void allVisitedStateChanged();
void visitedStateChanged(LinkHash visitedHash);
@@ -128,26 +117,11 @@
EInsideLink determineLinkStateSlowCase(Element*) const;
- void pushParentStackFrame(Element* parent);
- void popParentStackFrame();
-
Document* m_document;
bool m_strictParsing;
bool m_documentIsHTML;
Mode m_mode;
mutable HashSet<LinkHash, LinkHashHash> m_linksCheckedForVisitedState;
-
- struct ParentStackFrame {
- ParentStackFrame() : element(0) { }
- 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;
};
inline EInsideLink SelectorChecker::determineLinkState(Element* element) const
@@ -157,17 +131,6 @@
return determineLinkStateSlowCase(element);
}
-template <unsigned maximumIdentifierCount>
-inline bool SelectorChecker::fastRejectSelector(const unsigned* identifierHashes) const
-{
- ASSERT(m_ancestorIdentifierFilter);
- for (unsigned n = 0; n < maximumIdentifierCount && identifierHashes[n]; ++n) {
- if (!m_ancestorIdentifierFilter->mayContain(identifierHashes[n]))
- return true;
- }
- return false;
-}
-
inline bool SelectorChecker::isCommonPseudoClassSelector(const CSSSelector* selector)
{
if (selector->m_match != CSSSelector::PseudoClass)
Added: trunk/Source/WebCore/css/SelectorFilter.cpp (0 => 138432)
--- trunk/Source/WebCore/css/SelectorFilter.cpp (rev 0)
+++ trunk/Source/WebCore/css/SelectorFilter.cpp 2012-12-24 05:05:13 UTC (rev 138432)
@@ -0,0 +1,167 @@
+/*
+ * Copyright (C) 1999 Lars Knoll (kn...@kde.org)
+ * (C) 2004-2005 Allan Sandfeld Jensen (k...@carewolf.com)
+ * Copyright (C) 2006, 2007 Nicholas Shanks (web...@nickshanks.com)
+ * Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011 Apple Inc. All rights reserved.
+ * Copyright (C) 2007 Alexey Proskuryakov <a...@webkit.org>
+ * Copyright (C) 2007, 2008 Eric Seidel <e...@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.
+ * Copyright (C) 2012 Google Inc. All rights reserved.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Library General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public License
+ * along with this library; see the file COPYING.LIB. If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
+ * Boston, MA 02110-1301, USA.
+ */
+
+#include "config.h"
+#include "SelectorFilter.h"
+
+#include "CSSSelector.h"
+
+namespace WebCore {
+
+// Salt to separate otherwise identical string hashes so a class-selector like .article won't match <article> elements.
+enum { TagNameSalt = 13, IdAttributeSalt = 17, ClassAttributeSalt = 19 };
+
+static inline void collectElementIdentifierHashes(const Element* element, Vector<unsigned, 4>& identifierHashes)
+{
+ identifierHashes.append(element->localName().impl()->existingHash() * TagNameSalt);
+ if (element->hasID())
+ identifierHashes.append(element->idForStyleResolution().impl()->existingHash() * IdAttributeSalt);
+ const StyledElement* styledElement = element->isStyledElement() ? static_cast<const StyledElement*>(element) : 0;
+ if (styledElement && styledElement->hasClass()) {
+ const SpaceSplitString& classNames = styledElement->classNames();
+ size_t count = classNames.size();
+ for (size_t i = 0; i < count; ++i)
+ identifierHashes.append(classNames[i].impl()->existingHash() * ClassAttributeSalt);
+ }
+}
+
+void SelectorFilter::pushParentStackFrame(Element* parent)
+{
+ ASSERT(m_ancestorIdentifierFilter);
+ ASSERT(m_parentStack.isEmpty() || m_parentStack.last().element == parent->parentOrHostElement());
+ ASSERT(!m_parentStack.isEmpty() || !parent->parentOrHostElement());
+ 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 SelectorFilter::popParentStackFrame()
+{
+ ASSERT(!m_parentStack.isEmpty());
+ ASSERT(m_ancestorIdentifierFilter);
+ 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();
+ if (m_parentStack.isEmpty()) {
+ ASSERT(m_ancestorIdentifierFilter->likelyEmpty());
+ m_ancestorIdentifierFilter.clear();
+ }
+}
+
+void SelectorFilter::setupParentStack(Element* parent)
+{
+ ASSERT(m_parentStack.isEmpty() == !m_ancestorIdentifierFilter);
+ // Kill whatever we stored before.
+ m_parentStack.shrink(0);
+ m_ancestorIdentifierFilter = adoptPtr(new BloomFilter<bloomFilterKeyBits>);
+ // Fast version if parent is a root element:
+ if (!parent->parentOrHostNode()) {
+ pushParentStackFrame(parent);
+ return;
+ }
+ // Otherwise climb up the tree.
+ Vector<Element*, 30> ancestors;
+ for (Element* ancestor = parent; ancestor; ancestor = ancestor->parentOrHostElement())
+ ancestors.append(ancestor);
+ for (size_t n = ancestors.size(); n; --n)
+ pushParentStackFrame(ancestors[n - 1]);
+}
+
+void SelectorFilter::pushParent(Element* parent)
+{
+ ASSERT(m_ancestorIdentifierFilter);
+ // We may get invoked for some random elements in some wacky cases during style resolve.
+ // Pause maintaining the stack in this case.
+ if (m_parentStack.last().element != parent->parentOrHostElement())
+ return;
+ pushParentStackFrame(parent);
+}
+
+static inline void collectDescendantSelectorIdentifierHashes(const CSSSelector* selector, unsigned*& hash, const unsigned* end)
+{
+ switch (selector->m_match) {
+ case CSSSelector::Id:
+ if (!selector->value().isEmpty())
+ (*hash++) = selector->value().impl()->existingHash() * IdAttributeSalt;
+ break;
+ case CSSSelector::Class:
+ if (!selector->value().isEmpty())
+ (*hash++) = selector->value().impl()->existingHash() * ClassAttributeSalt;
+ break;
+ default:
+ break;
+ }
+ if (hash == end)
+ return;
+ const AtomicString& localName = selector->tag().localName();
+ if (localName != starAtom)
+ (*hash++) = localName.impl()->existingHash() * TagNameSalt;
+}
+
+void SelectorFilter::collectIdentifierHashes(const CSSSelector* selector, unsigned* identifierHashes, unsigned maximumIdentifierCount)
+{
+ unsigned* hash = identifierHashes;
+ unsigned* end = identifierHashes + maximumIdentifierCount;
+ CSSSelector::Relation relation = selector->relation();
+
+ // Skip the topmost selector. It is handled quickly by the rule hashes.
+ bool skipOverSubselectors = true;
+ for (selector = selector->tagHistory(); selector; selector = selector->tagHistory()) {
+ // Only collect identifiers that match ancestors.
+ switch (relation) {
+ case CSSSelector::SubSelector:
+ if (!skipOverSubselectors)
+ collectDescendantSelectorIdentifierHashes(selector, hash, end);
+ break;
+ case CSSSelector::DirectAdjacent:
+ case CSSSelector::IndirectAdjacent:
+ case CSSSelector::ShadowDescendant:
+ skipOverSubselectors = true;
+ break;
+ case CSSSelector::Descendant:
+ case CSSSelector::Child:
+ skipOverSubselectors = false;
+ collectDescendantSelectorIdentifierHashes(selector, hash, end);
+ break;
+ }
+ if (hash == end)
+ return;
+ relation = selector->relation();
+ }
+ *hash = 0;
+}
+
+}
+
Added: trunk/Source/WebCore/css/SelectorFilter.h (0 => 138432)
--- trunk/Source/WebCore/css/SelectorFilter.h (rev 0)
+++ trunk/Source/WebCore/css/SelectorFilter.h 2012-12-24 05:05:13 UTC (rev 138432)
@@ -0,0 +1,82 @@
+/*
+ * Copyright (C) 1999 Lars Knoll (kn...@kde.org)
+ * (C) 2004-2005 Allan Sandfeld Jensen (k...@carewolf.com)
+ * Copyright (C) 2006, 2007 Nicholas Shanks (web...@nickshanks.com)
+ * Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011 Apple Inc. All rights reserved.
+ * Copyright (C) 2007 Alexey Proskuryakov <a...@webkit.org>
+ * Copyright (C) 2007, 2008 Eric Seidel <e...@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.
+ * Copyright (C) 2012 Google Inc. All rights reserved.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Library General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public License
+ * along with this library; see the file COPYING.LIB. If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
+ * Boston, MA 02110-1301, USA.
+ */
+
+#ifndef SelectorFilter_h
+#define SelectorFilter_h
+
+#include "StyledElement.h"
+#include <wtf/BloomFilter.h>
+#include <wtf/Vector.h>
+
+namespace WebCore {
+
+class CSSSelector;
+
+class SelectorFilter {
+public:
+ void pushParentStackFrame(Element* parent);
+ void popParentStackFrame();
+
+ void setupParentStack(Element* parent);
+ void pushParent(Element* parent);
+ void popParent() { popParentStackFrame(); }
+ bool parentStackIsEmpty() const { return m_parentStack.isEmpty(); }
+ bool parentStackIsConsistent(const ContainerNode* parentNode) const { return !m_parentStack.isEmpty() && m_parentStack.last().element == parentNode; }
+
+ template <unsigned maximumIdentifierCount>
+ inline bool fastRejectSelector(const unsigned* identifierHashes) const;
+ static void collectIdentifierHashes(const CSSSelector*, unsigned* identifierHashes, unsigned maximumIdentifierCount);
+
+private:
+ struct ParentStackFrame {
+ ParentStackFrame() : element(0) { }
+ 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;
+};
+
+template <unsigned maximumIdentifierCount>
+inline bool SelectorFilter::fastRejectSelector(const unsigned* identifierHashes) const
+{
+ ASSERT(m_ancestorIdentifierFilter);
+ for (unsigned n = 0; n < maximumIdentifierCount && identifierHashes[n]; ++n) {
+ if (!m_ancestorIdentifierFilter->mayContain(identifierHashes[n]))
+ return true;
+ }
+ return false;
+}
+
+}
+
+#endif
Modified: trunk/Source/WebCore/css/StyleResolver.cpp (138431 => 138432)
--- trunk/Source/WebCore/css/StyleResolver.cpp 2012-12-24 04:43:23 UTC (rev 138431)
+++ trunk/Source/WebCore/css/StyleResolver.cpp 2012-12-24 05:05:13 UTC (rev 138432)
@@ -258,6 +258,7 @@
return rightToLeftDecl.get();
}
+
StyleResolver::StyleResolver(Document* document, bool matchAuthorAndUserStyles)
: m_hasUAAppearance(false)
, m_backgroundData(BackgroundFillLayer)
@@ -405,10 +406,10 @@
// 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_checker.parentStackIsEmpty())
- m_checker.setupParentStack(parent);
+ if (!parentsParent || m_selectorFilter.parentStackIsEmpty())
+ m_selectorFilter.setupParentStack(parent);
else
- m_checker.pushParent(parent);
+ m_selectorFilter.pushParent(parent);
// Note: We mustn't skip ShadowRoot nodes for the scope stack.
if (m_scopeResolver)
@@ -419,8 +420,8 @@
{
// Note that we may get invoked for some random elements in some wacky cases during style resolve.
// Pause maintaining the stack in this case.
- if (m_checker.parentStackIsConsistent(parent))
- m_checker.popParent();
+ if (m_selectorFilter.parentStackIsConsistent(parent))
+ m_selectorFilter.popParent();
if (m_scopeResolver)
m_scopeResolver->pop(parent);
}
@@ -843,12 +844,12 @@
// 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_checker.parentStackIsConsistent(m_parentNode);
+ bool canUseFastReject = m_selectorFilter.parentStackIsConsistent(m_parentNode);
unsigned size = rules->size();
for (unsigned i = 0; i < size; ++i) {
const RuleData& ruleData = rules->at(i);
- if (canUseFastReject && m_checker.fastRejectSelector<RuleData::maximumIdentifierCount>(ruleData.descendantSelectorIdentifierHashes()))
+ if (canUseFastReject && m_selectorFilter.fastRejectSelector<RuleData::maximumIdentifierCount>(ruleData.descendantSelectorIdentifierHashes()))
continue;
StyleRule* rule = ruleData.rule();
Modified: trunk/Source/WebCore/css/StyleResolver.h (138431 => 138432)
--- trunk/Source/WebCore/css/StyleResolver.h 2012-12-24 04:43:23 UTC (rev 138431)
+++ trunk/Source/WebCore/css/StyleResolver.h 2012-12-24 05:05:13 UTC (rev 138432)
@@ -31,6 +31,7 @@
#include "RuleFeature.h"
#include "RuntimeEnabledFeatures.h"
#include "SelectorChecker.h"
+#include "SelectorFilter.h"
#include "StyleInheritedData.h"
#include "StyleScopeResolver.h"
#include "ViewportStyleResolver.h"
@@ -491,6 +492,7 @@
PseudoId m_pseudoStyle;
SelectorChecker m_checker;
+ SelectorFilter m_selectorFilter;
RefPtr<RenderStyle> m_style;
RenderStyle* m_parentStyle;
