Diff
Modified: trunk/Source/WebCore/ChangeLog (95051 => 95052)
--- trunk/Source/WebCore/ChangeLog 2011-09-13 22:33:30 UTC (rev 95051)
+++ trunk/Source/WebCore/ChangeLog 2011-09-13 22:38:42 UTC (rev 95052)
@@ -1,3 +1,33 @@
+2011-09-13 Antti Koivisto <an...@apple.com>
+
+ Move identifier filter from CSSStyleSelector to SelectorChecker
+ https://bugs.webkit.org/show_bug.cgi?id=68025
+
+ Reviewed by Sam Weinig.
+
+ This is a more logical place for this code. It also makes CSSStyleSelector slightly less bloated.
+ It will make it possible to use fastRejectSelector for querySelectorAll in the future.
+
+ * css/CSSStyleSelector.cpp:
+ (WebCore::loadViewSourceStyle):
+ (WebCore::CSSStyleSelector::matchRulesForList):
+ (WebCore::RuleData::RuleData):
+ * css/CSSStyleSelector.h:
+ (WebCore::CSSStyleSelector::pushParent):
+ (WebCore::CSSStyleSelector::popParent):
+ * css/SelectorChecker.cpp:
+ (WebCore::collectElementIdentifierHashes):
+ (WebCore::SelectorChecker::pushParentStackFrame):
+ (WebCore::SelectorChecker::popParentStackFrame):
+ (WebCore::SelectorChecker::pushParent):
+ (WebCore::SelectorChecker::popParent):
+ (WebCore::collectDescendantSelectorIdentifierHashes):
+ (WebCore::SelectorChecker::collectIdentifierHashes):
+ * css/SelectorChecker.h:
+ (WebCore::SelectorChecker::parentStackIsConsistent):
+ (WebCore::SelectorChecker::ParentStackFrame::ParentStackFrame):
+ (WebCore::SelectorChecker::fastRejectSelector):
+
2011-09-13 Kiyoto Tamura <owenes...@gmail.com>
For compatibility, execCommand should support deprecated 'useCSS' alias for 'styleWithCSS'
Modified: trunk/Source/WebCore/css/CSSStyleSelector.cpp (95051 => 95052)
--- trunk/Source/WebCore/css/CSSStyleSelector.cpp 2011-09-13 22:33:30 UTC (rev 95051)
+++ trunk/Source/WebCore/css/CSSStyleSelector.cpp 2011-09-13 22:38:42 UTC (rev 95052)
@@ -195,10 +195,7 @@
static const unsigned maximumIdentifierCount = 4;
const unsigned* descendantSelectorIdentifierHashes() const { return m_descendantSelectorIdentifierHashes; }
-private:
- void collectDescendantSelectorIdentifierHashes();
- void collectIdentifierHashes(const CSSSelector*, unsigned& identifierCount);
-
+private:
CSSStyleRule* m_rule;
CSSSelector* m_selector;
unsigned m_specificity;
@@ -507,89 +504,7 @@
defaultViewSourceStyle = new RuleSet;
defaultViewSourceStyle->addRulesFromSheet(parseUASheet(sourceUserAgentStyleSheet, sizeof(sourceUserAgentStyleSheet)), screenEval());
}
-
-static inline void collectElementIdentifierHashes(const Element* element, Vector<unsigned, 4>& identifierHashes)
-{
- identifierHashes.append(element->localName().impl()->existingHash());
- if (element->hasID())
- identifierHashes.append(element->idForStyleResolution().impl()->existingHash());
- 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());
- }
-}
-void CSSStyleSelector::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 CSSStyleSelector::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 CSSStyleSelector::pushParent(Element* parent)
-{
- if (m_parentStack.isEmpty()) {
- ASSERT(!m_ancestorIdentifierFilter);
- m_ancestorIdentifierFilter = adoptPtr(new BloomFilter<bloomFilterKeyBits>);
- // If the element is not the root itself, build the stack starting from the root.
- if (parent->parentOrHostNode()) {
- Vector<Element*, 30> ancestors;
- for (Element* ancestor = parent; ancestor; ancestor = ancestor->parentOrHostElement())
- ancestors.append(ancestor);
- int count = ancestors.size();
- for (int n = count - 1; n >= 0; --n)
- pushParentStackFrame(ancestors[n]);
- return;
- }
- } else if (!parent->parentOrHostElement()) {
- // We are not always invoked consistently. For example, script execution can cause us to enter
- // style recalc in the middle of tree building. Reset the stack if we see a new root element.
- ASSERT(m_ancestorIdentifierFilter);
- m_ancestorIdentifierFilter->clear();
- m_parentStack.resize(0);
- } else {
- 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);
-}
-
-void CSSStyleSelector::popParent(Element* parent)
-{
- if (m_parentStack.isEmpty() || m_parentStack.last().element != parent)
- return;
- popParentStackFrame();
-}
-
void CSSStyleSelector::addMatchedDeclaration(CSSMutableStyleDeclaration* decl)
{
m_matchedDecls.append(decl);
@@ -641,17 +556,6 @@
}
}
-inline bool CSSStyleSelector::fastRejectSelector(const RuleData& ruleData) const
-{
- ASSERT(m_ancestorIdentifierFilter);
- const unsigned* descendantSelectorIdentifierHashes = ruleData.descendantSelectorIdentifierHashes();
- for (unsigned n = 0; n < RuleData::maximumIdentifierCount && descendantSelectorIdentifierHashes[n]; ++n) {
- if (!m_ancestorIdentifierFilter->mayContain(descendantSelectorIdentifierHashes[n]))
- return true;
- }
- return false;
-}
-
class MatchingUARulesScope {
public:
MatchingUARulesScope();
@@ -692,12 +596,12 @@
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;
+ bool canUseFastReject = m_checker.parentStackIsConsistent(m_parentNode);
unsigned size = rules->size();
for (unsigned i = 0; i < size; ++i) {
const RuleData& ruleData = rules->at(i);
- if (canUseFastReject && fastRejectSelector(ruleData))
+ if (canUseFastReject && m_checker.fastRejectSelector<RuleData::maximumIdentifierCount>(ruleData.descendantSelectorIdentifierHashes()))
continue;
if (checkSelector(ruleData)) {
if (!matchesInTreeScope(m_element->treeScope(), m_checker.hasUnknownPseudoElements()))
@@ -1924,52 +1828,9 @@
, m_hasMultipartSelector(selector->tagHistory())
, m_hasTopSelectorMatchingHTMLBasedOnRuleHash(isSelectorMatchingHTMLBasedOnRuleHash(selector))
{
- collectDescendantSelectorIdentifierHashes();
+ SelectorChecker::collectIdentifierHashes(m_selector, m_descendantSelectorIdentifierHashes, maximumIdentifierCount);
}
-inline void RuleData::collectIdentifierHashes(const CSSSelector* selector, unsigned& identifierCount)
-{
- 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();
-}
-
-inline void RuleData::collectDescendantSelectorIdentifierHashes()
-{
- unsigned identifierCount = 0;
- CSSSelector::Relation relation = m_selector->relation();
-
- // Skip the topmost selector. It is handled quickly by the rule hashes.
- bool skipOverSubselectors = true;
- for (const CSSSelector* selector = m_selector->tagHistory(); selector; selector = selector->tagHistory()) {
- // Only collect identifiers that match ancestors.
- switch (relation) {
- case CSSSelector::SubSelector:
- if (!skipOverSubselectors)
- collectIdentifierHashes(selector, identifierCount);
- break;
- case CSSSelector::DirectAdjacent:
- case CSSSelector::IndirectAdjacent:
- case CSSSelector::ShadowDescendant:
- skipOverSubselectors = true;
- break;
- case CSSSelector::Descendant:
- case CSSSelector::Child:
- skipOverSubselectors = false;
- collectIdentifierHashes(selector, identifierCount);
- break;
- }
- if (identifierCount == maximumIdentifierCount)
- return;
- relation = selector->relation();
- }
- m_descendantSelectorIdentifierHashes[identifierCount] = 0;
-}
-
RuleSet::RuleSet()
: m_ruleCount(0)
, m_autoShrinkToFitEnabled(true)
Modified: trunk/Source/WebCore/css/CSSStyleSelector.h (95051 => 95052)
--- trunk/Source/WebCore/css/CSSStyleSelector.h 2011-09-13 22:33:30 UTC (rev 95051)
+++ trunk/Source/WebCore/css/CSSStyleSelector.h 2011-09-13 22:38:42 UTC (rev 95052)
@@ -27,7 +27,6 @@
#include "MediaQueryExp.h"
#include "RenderStyle.h"
#include "SelectorChecker.h"
-#include <wtf/BloomFilter.h>
#include <wtf/HashMap.h>
#include <wtf/HashSet.h>
#include <wtf/RefPtr.h>
@@ -95,10 +94,9 @@
~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);
+ void pushParent(Element* parent) { m_checker.pushParent(parent); }
+ void popParent(Element* parent) { m_checker.popParent(parent); }
-
PassRefPtr<RenderStyle> styleForElement(Element*, RenderStyle* parentStyle = 0, bool allowSharing = true, bool resolveForRootDefault = false, bool matchVisitedPseudoClass = false);
void keyframeStylesForAnimation(Element*, const RenderStyle*, KeyframeList&);
@@ -128,9 +126,6 @@
Node* locateCousinList(Element* parent, unsigned& visitedNodeCount) const;
Node* findSiblingForStyleSharing(Node*, unsigned& count) const;
bool canShareStyleWithElement(Node*) const;
-
- void pushParentStackFrame(Element* parent);
- void popParentStackFrame();
PassRefPtr<RenderStyle> styleForKeyframe(const RenderStyle*, const WebKitCSSKeyframeRule*, KeyframeValue&);
@@ -245,18 +240,6 @@
Features m_features;
- struct ParentStackFrame {
- 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;
FillLayer m_backgroundData;
Modified: trunk/Source/WebCore/css/SelectorChecker.cpp (95051 => 95052)
--- trunk/Source/WebCore/css/SelectorChecker.cpp 2011-09-13 22:33:30 UTC (rev 95051)
+++ trunk/Source/WebCore/css/SelectorChecker.cpp 2011-09-13 22:38:42 UTC (rev 95052)
@@ -79,6 +79,132 @@
{
}
+static inline void collectElementIdentifierHashes(const Element* element, Vector<unsigned, 4>& identifierHashes)
+{
+ identifierHashes.append(element->localName().impl()->existingHash());
+ if (element->hasID())
+ identifierHashes.append(element->idForStyleResolution().impl()->existingHash());
+ 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());
+ }
+}
+
+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::pushParent(Element* parent)
+{
+ if (m_parentStack.isEmpty()) {
+ ASSERT(!m_ancestorIdentifierFilter);
+ m_ancestorIdentifierFilter = adoptPtr(new BloomFilter<bloomFilterKeyBits>);
+ // If the element is not the root itself, build the stack starting from the root.
+ if (parent->parentOrHostNode()) {
+ Vector<Element*, 30> ancestors;
+ for (Element* ancestor = parent; ancestor; ancestor = ancestor->parentOrHostElement())
+ ancestors.append(ancestor);
+ int count = ancestors.size();
+ for (int n = count - 1; n >= 0; --n)
+ pushParentStackFrame(ancestors[n]);
+ return;
+ }
+ } else if (!parent->parentOrHostElement()) {
+ // We are not always invoked consistently. For example, script execution can cause us to enter
+ // style recalc in the middle of tree building. Reset the stack if we see a new root element.
+ ASSERT(m_ancestorIdentifierFilter);
+ m_ancestorIdentifierFilter->clear();
+ m_parentStack.resize(0);
+ } else {
+ 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);
+}
+
+void SelectorChecker::popParent(Element* parent)
+{
+ if (m_parentStack.isEmpty() || m_parentStack.last().element != parent)
+ return;
+ popParentStackFrame();
+}
+
+static inline void collectDescendantSelectorIdentifierHashes(const CSSSelector* selector, unsigned* hash, const unsigned* end)
+{
+ if ((selector->m_match == CSSSelector::Id || selector->m_match == CSSSelector::Class) && !selector->value().isEmpty())
+ (*hash++) = selector->value().impl()->existingHash();
+ if (hash == end)
+ return;
+ const AtomicString& localName = selector->tag().localName();
+ if (localName != starAtom)
+ (*hash++) = localName.impl()->existingHash();
+}
+
+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(Node* node)
{
if (!node->isLink())
Modified: trunk/Source/WebCore/css/SelectorChecker.h (95051 => 95052)
--- trunk/Source/WebCore/css/SelectorChecker.h 2011-09-13 22:33:30 UTC (rev 95051)
+++ trunk/Source/WebCore/css/SelectorChecker.h 2011-09-13 22:38:42 UTC (rev 95052)
@@ -31,6 +31,7 @@
#include "Element.h"
#include "LinkHash.h"
#include "RenderStyleConstants.h"
+#include <wtf/BloomFilter.h>
#include <wtf/HashSet.h>
#include <wtf/Vector.h>
@@ -52,6 +53,14 @@
static bool isFastCheckableSelector(const CSSSelector*);
static bool fastCheckSelector(const CSSSelector*, const Element*);
+ template <unsigned maximumIdentifierCount>
+ inline bool fastRejectSelector(const unsigned* identifierHashes) const;
+ static void collectIdentifierHashes(const CSSSelector*, unsigned* identifierHashes, unsigned maximumIdentifierCount);
+
+ void pushParent(Element* parent);
+ void popParent(Element* parent);
+ bool parentStackIsConsistent(ContainerNode* parentNode) const { return !m_parentStack.isEmpty() && m_parentStack.last().element == parentNode; }
+
EInsideLink determineLinkState(Element*) const;
void allVisitedStateChanged();
void visitedStateChanged(LinkHash visitedHash);
@@ -77,6 +86,9 @@
EInsideLink determineLinkStateSlowCase(Element*) const;
+ void pushParentStackFrame(Element* parent);
+ void popParentStackFrame();
+
Document* m_document;
bool m_strictParsing;
bool m_documentIsHTML;
@@ -85,6 +97,18 @@
mutable bool m_hasUnknownPseudoElements;
mutable bool m_isMatchingVisitedPseudoClass;
mutable HashSet<LinkHash, LinkHashHash> m_linksCheckedForVisitedState;
+
+ struct ParentStackFrame {
+ 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;
};
inline EInsideLink SelectorChecker::determineLinkState(Element* element) const
@@ -93,6 +117,17 @@
return NotInsideLink;
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;
+}
}