Diff
Modified: trunk/Source/WebCore/ChangeLog (287090 => 287091)
--- trunk/Source/WebCore/ChangeLog 2021-12-15 19:42:28 UTC (rev 287090)
+++ trunk/Source/WebCore/ChangeLog 2021-12-15 19:45:12 UTC (rev 287091)
@@ -1,3 +1,56 @@
+2021-12-15 Antti Koivisto <an...@apple.com>
+
+ [:has() pseudo-class] Use Bloom filter to quickly reject :has() selectors
+ https://bugs.webkit.org/show_bug.cgi?id=234341
+
+ Reviewed by Dean Jackson.
+
+ We can dramatically speed up cases where there are many :has rules, most of which don't match their argument
+ by building a Bloom filter describing the features of the subtree.
+
+ * Sources.txt:
+ * WebCore.xcodeproj/project.pbxproj:
+ * css/SelectorChecker.cpp:
+ (WebCore::SelectorChecker::matchHasPseudoClass const):
+
+ Build and cache HasSelectorFilter per element/filter type. It will be constructed only if multiple :has()
+ selectors are tested for the same element (otherwise the regular match cache is more efficient).
+ Use it to quickly reject selectors.
+ Also add a basic inital optimization to bail out if there are no child/sibling elements that could match.
+
+ * css/SelectorFilter.cpp:
+ (WebCore::SelectorFilter::collectElementIdentifierHashes):
+ (WebCore::SelectorFilter::collectSimpleSelectorHash):
+ (WebCore::SelectorFilter::collectSelectorHashes):
+ (WebCore::SelectorFilter::chooseSelectorHashesForFilter):
+ (WebCore::collectElementIdentifierHashes): Deleted.
+ (WebCore::collectSimpleSelectorHash): Deleted.
+ (WebCore::collectSelectorHashes): Deleted.
+ (WebCore::chooseSelectorHashesForFilter): Deleted.
+ * css/SelectorFilter.h:
+ * style/HasSelectorFilter.cpp: Added.
+ (WebCore::Style::HasSelectorFilter::HasSelectorFilter):
+ (WebCore::Style::HasSelectorFilter::typeForMatchElement):
+ (WebCore::Style::HasSelectorFilter::makeKey):
+
+ The key consists of the most specific string in the rightmost compound of the selector along with
+ :hover pseudo class, if any.
+
+ (WebCore::Style::HasSelectorFilter::add):
+
+ Add an Element to the filter.
+ The features collected are the same as for the regular selector filter, plus permutations with
+ :hover pseudo-class if it would match.
+
+ * style/HasSelectorFilter.h: Copied from Source/WebCore/style/SelectorMatchingState.h.
+ (WebCore::Style::HasSelectorFilter::type const):
+ (WebCore::Style::HasSelectorFilter::reject const):
+
+ Add HasSelectorFilter which uses non-counting BloomFilter internally. The size of the filter is 512 bytes.
+
+ * style/SelectorMatchingState.h:
+ (WebCore::Style::makeHasPseudoClassSelectorFilterKey):
+
2021-12-15 Alexey Shvayka <ashva...@apple.com>
[WebIDL] onselectionchange IDL attribute should not Document-reflect event listeners
Modified: trunk/Source/WebCore/Sources.txt (287090 => 287091)
--- trunk/Source/WebCore/Sources.txt 2021-12-15 19:42:28 UTC (rev 287090)
+++ trunk/Source/WebCore/Sources.txt 2021-12-15 19:45:12 UTC (rev 287091)
@@ -2543,6 +2543,7 @@
style/ChildChangeInvalidation.cpp
style/ClassChangeInvalidation.cpp
style/ElementRuleCollector.cpp
+style/HasSelectorFilter.cpp
style/IdChangeInvalidation.cpp
style/InlineTextBoxStyle.cpp
style/InspectorCSSOMWrappers.cpp
Modified: trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj (287090 => 287091)
--- trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj 2021-12-15 19:42:28 UTC (rev 287090)
+++ trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj 2021-12-15 19:45:12 UTC (rev 287091)
@@ -5384,6 +5384,7 @@
E4E8B4EC216B79E500B8834D /* SystemFontDatabaseCoreText.h in Headers */ = {isa = PBXBuildFile; fileRef = E4E8B4EA216B79E500B8834D /* SystemFontDatabaseCoreText.h */; };
E4E8B4F5216B956500B8834D /* FontCascadeDescription.h in Headers */ = {isa = PBXBuildFile; fileRef = E4E8B4F2216B8B6000B8834D /* FontCascadeDescription.h */; settings = {ATTRIBUTES = (Private, ); }; };
E4E94D6122FF158A00DD191F /* LegacyLineLayout.h in Headers */ = {isa = PBXBuildFile; fileRef = E4A1AC7822FAFD500017B75B /* LegacyLineLayout.h */; settings = {ATTRIBUTES = (Private, ); }; };
+ E4ED3ECC2768A51D00F17AC8 /* HasSelectorFilter.h in Headers */ = {isa = PBXBuildFile; fileRef = E4ED3ECA2768A51C00F17AC8 /* HasSelectorFilter.h */; };
E4F0BE3125712F6E009E7431 /* CaretRectComputation.h in Headers */ = {isa = PBXBuildFile; fileRef = E4F0BE2E25710A75009E7431 /* CaretRectComputation.h */; };
E4F38D1B2626F13B007B1064 /* DefaultResourceLoadPriority.h in Headers */ = {isa = PBXBuildFile; fileRef = E4F38D192626F13B007B1064 /* DefaultResourceLoadPriority.h */; };
E4F819C626FB4EBF0094E162 /* InlineBoxPainter.h in Headers */ = {isa = PBXBuildFile; fileRef = E4F819C526FB4EBF0094E162 /* InlineBoxPainter.h */; };
@@ -17466,6 +17467,8 @@
E4E8B4ED216B79F400B8834D /* SystemFontDatabaseCoreText.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = SystemFontDatabaseCoreText.cpp; sourceTree = "<group>"; };
E4E8B4F0216B8B5F00B8834D /* FontCascadeDescription.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = FontCascadeDescription.cpp; sourceTree = "<group>"; };
E4E8B4F2216B8B6000B8834D /* FontCascadeDescription.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = FontCascadeDescription.h; sourceTree = "<group>"; };
+ E4ED3ECA2768A51C00F17AC8 /* HasSelectorFilter.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = HasSelectorFilter.h; sourceTree = "<group>"; };
+ E4ED3ECD2768A68800F17AC8 /* HasSelectorFilter.cpp */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.cpp; path = HasSelectorFilter.cpp; sourceTree = "<group>"; };
E4F0BE2E25710A75009E7431 /* CaretRectComputation.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CaretRectComputation.h; sourceTree = "<group>"; };
E4F0BE3025710A76009E7431 /* CaretRectComputation.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CaretRectComputation.cpp; sourceTree = "<group>"; };
E4F38D192626F13B007B1064 /* DefaultResourceLoadPriority.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = DefaultResourceLoadPriority.h; sourceTree = "<group>"; };
@@ -31080,6 +31083,8 @@
E4A814D31C6DEC4000BF85AC /* ClassChangeInvalidation.h */,
FBDB619A16D6032A00BB3394 /* ElementRuleCollector.cpp */,
FBDB619E16D6036500BB3394 /* ElementRuleCollector.h */,
+ E4ED3ECD2768A68800F17AC8 /* HasSelectorFilter.cpp */,
+ E4ED3ECA2768A51C00F17AC8 /* HasSelectorFilter.h */,
E4A814DD1C7338D100BF85AC /* IdChangeInvalidation.cpp */,
E4A814DF1C7338EB00BF85AC /* IdChangeInvalidation.h */,
1C0106FE192594DF008A4201 /* InlineTextBoxStyle.cpp */,
@@ -34473,6 +34478,7 @@
26EA89A71B4F2B75008C5FD2 /* HashableActionList.h in Headers */,
8482B7461198C35400BFB005 /* HashChangeEvent.h in Headers */,
A8748BE012CBF2DC001FBA41 /* HashTools.h in Headers */,
+ E4ED3ECC2768A51D00F17AC8 /* HasSelectorFilter.h in Headers */,
CD3EEF3D25799FB5006563BB /* HdrMetadataType.h in Headers */,
CDA595932146DEC300A84185 /* HEVCUtilities.h in Headers */,
CDA595982146DF7800A84185 /* HEVCUtilitiesCocoa.h in Headers */,
Modified: trunk/Source/WebCore/css/SelectorChecker.cpp (287090 => 287091)
--- trunk/Source/WebCore/css/SelectorChecker.cpp 2021-12-15 19:42:28 UTC (rev 287090)
+++ trunk/Source/WebCore/css/SelectorChecker.cpp 2021-12-15 19:45:12 UTC (rev 287091)
@@ -1249,12 +1249,31 @@
bool SelectorChecker::matchHasPseudoClass(CheckingContext& checkingContext, const Element& element, const CSSSelector& hasSelector) const
{
+ auto matchElement = Style::computeHasPseudoClassMatchElement(hasSelector);
+
+ auto canMatch = [&] {
+ switch (matchElement) {
+ case Style::MatchElement::HasChild:
+ case Style::MatchElement::HasDescendant:
+ return !!element.firstElementChild();
+ case Style::MatchElement::HasSibling:
+ case Style::MatchElement::HasSiblingDescendant:
+ return !!element.nextElementSibling();
+ default:
+ return true;
+ };
+ };
+
+ // See if there are any elements that this :has() selector could match.
+ if (!canMatch())
+ return false;
+
auto* cache = checkingContext.selectorMatchingState ? &checkingContext.selectorMatchingState->hasPseudoClassMatchCache : nullptr;
- Style::HasPseudoClassMatch* cachedMatch = nullptr;
- if (cache) {
- cachedMatch = &cache->add(Style::makeHasPseudoClassCacheKey(hasSelector, element), Style::HasPseudoClassMatch::None).iterator->value;
- switch (*cachedMatch) {
+ auto checkForCachedMatch = [&]() -> std::optional<bool> {
+ if (!cache)
+ return { };
+ switch (cache->get(Style::makeHasPseudoClassCacheKey(element, hasSelector))) {
case Style::HasPseudoClassMatch::Matches:
return true;
case Style::HasPseudoClassMatch::Fails:
@@ -1263,6 +1282,34 @@
case Style::HasPseudoClassMatch::None:
break;
}
+ return { };
+ };
+
+ // See if we know the result already.
+ if (auto match = checkForCachedMatch())
+ return *match;
+
+ auto filterForElement = [&]() -> Style::HasSelectorFilter* {
+ if (!checkingContext.selectorMatchingState)
+ return nullptr;
+ auto type = Style::HasSelectorFilter::typeForMatchElement(matchElement);
+ if (!type)
+ return nullptr;
+ auto& filtersMap = checkingContext.selectorMatchingState->hasPseudoClassSelectorFilters;
+ auto addResult = filtersMap.add(Style::makeHasPseudoClassFilterKey(element, *type), std::unique_ptr<Style::HasSelectorFilter>());
+ // Only build a filter if the same element gets checked second time with a different selector (misses the match cache).
+ if (addResult.isNewEntry)
+ return nullptr;
+
+ if (!addResult.iterator->value)
+ addResult.iterator->value = makeUnique<Style::HasSelectorFilter>(element, *type);
+ return addResult.iterator->value.get();
+ };
+
+ // Check if the bloom filter rejects this selector
+ if (auto* filter = filterForElement()) {
+ if (filter->reject(hasSelector))
+ return false;
}
SelectorChecker hasChecker(element.document());
@@ -1283,8 +1330,8 @@
auto checkDescendants = [&](const Element& descendantRoot) {
for (auto it = descendantsOfType<Element>(descendantRoot).begin(); it;) {
auto& descendant = *it;
- if (cache) {
- auto key = Style::makeHasPseudoClassCacheKey(hasSelector, descendant);
+ if (cache && descendant.firstElementChild()) {
+ auto key = Style::makeHasPseudoClassCacheKey(descendant, hasSelector);
if (cache->get(key) == Style::HasPseudoClassMatch::FailsSubtree) {
it.traverseNextSkippingChildren();
continue;
@@ -1300,8 +1347,6 @@
};
auto match = [&] {
- auto matchElement = Style::computeHasPseudoClassMatchElement(hasSelector);
-
switch (matchElement) {
// :has(> .child)
case Style::MatchElement::HasChild:
@@ -1312,12 +1357,10 @@
break;
// :has(.descendant)
case Style::MatchElement::HasDescendant: {
- if (!element.firstElementChild())
- return false;
if (cache) {
// See if we already know this descendant selector doesn't match in this subtree.
for (auto* ancestor = element.parentElement(); ancestor; ancestor = ancestor->parentElement()) {
- auto key = Style::makeHasPseudoClassCacheKey(hasSelector, *ancestor);
+ auto key = Style::makeHasPseudoClassCacheKey(*ancestor, hasSelector);
if (cache->get(key) == Style::HasPseudoClassMatch::FailsSubtree)
return false;
}
@@ -1324,6 +1367,7 @@
}
if (checkDescendants(element))
return true;
+
break;
}
// FIXME: Add a separate case for adjacent combinator.
@@ -1354,16 +1398,17 @@
auto result = match();
- if (cachedMatch) {
- *cachedMatch = [&] {
- if (result)
- return Style::HasPseudoClassMatch::Matches;
- if (matchedInsideScope)
- return Style::HasPseudoClassMatch::Fails;
- return Style::HasPseudoClassMatch::FailsSubtree;
- }();
- }
+ auto matchTypeForCache = [&] {
+ if (result)
+ return Style::HasPseudoClassMatch::Matches;
+ if (matchedInsideScope)
+ return Style::HasPseudoClassMatch::Fails;
+ return Style::HasPseudoClassMatch::FailsSubtree;
+ };
+ if (cache)
+ cache->add(Style::makeHasPseudoClassCacheKey(element, hasSelector), matchTypeForCache());
+
return result;
}
Modified: trunk/Source/WebCore/css/SelectorFilter.cpp (287090 => 287091)
--- trunk/Source/WebCore/css/SelectorFilter.cpp 2021-12-15 19:42:28 UTC (rev 287090)
+++ trunk/Source/WebCore/css/SelectorFilter.cpp 2021-12-15 19:45:12 UTC (rev 287091)
@@ -45,7 +45,7 @@
return name == HTMLNames::classAttr->localName() || name == HTMLNames::idAttr->localName() || name == HTMLNames::styleAttr->localName();
}
-static inline void collectElementIdentifierHashes(const Element& element, Vector<unsigned, 4>& identifierHashes)
+void SelectorFilter::collectElementIdentifierHashes(const Element& element, Vector<unsigned, 4>& identifierHashes)
{
AtomString tagLowercaseLocalName = element.localName().convertToASCIILowercase();
identifierHashes.append(tagLowercaseLocalName.impl()->existingHash() * TagNameSalt);
@@ -134,15 +134,7 @@
}
}
-struct CollectedSelectorHashes {
- using HashVector = Vector<unsigned, 8>;
- HashVector ids;
- HashVector classes;
- HashVector tags;
- HashVector attributes;
-};
-
-static inline void collectSimpleSelectorHash(CollectedSelectorHashes& collectedHashes, const CSSSelector& selector)
+void SelectorFilter::collectSimpleSelectorHash(CollectedSelectorHashes& collectedHashes, const CSSSelector& selector)
{
switch (selector.match()) {
case CSSSelector::Id:
@@ -176,7 +168,7 @@
}
}
-static CollectedSelectorHashes collectSelectorHashes(const CSSSelector& rightmostSelector)
+auto SelectorFilter::collectSelectorHashes(const CSSSelector& rightmostSelector) -> CollectedSelectorHashes
{
CollectedSelectorHashes collectedHashes;
@@ -210,9 +202,9 @@
return collectedHashes;
}
-static SelectorFilter::Hashes chooseSelectorHashesForFilter(const CollectedSelectorHashes& collectedSelectorHashes)
+auto SelectorFilter::chooseSelectorHashesForFilter(const CollectedSelectorHashes& collectedSelectorHashes) -> Hashes
{
- SelectorFilter::Hashes resultHashes;
+ Hashes resultHashes;
unsigned index = 0;
auto addIfNew = [&] (unsigned hash) {
Modified: trunk/Source/WebCore/css/SelectorFilter.h (287090 => 287091)
--- trunk/Source/WebCore/css/SelectorFilter.h 2021-12-15 19:42:28 UTC (rev 287090)
+++ trunk/Source/WebCore/css/SelectorFilter.h 2021-12-15 19:45:12 UTC (rev 287091)
@@ -50,8 +50,21 @@
bool fastRejectSelector(const Hashes&) const;
static Hashes collectHashes(const CSSSelector&);
+ static void collectElementIdentifierHashes(const Element&, Vector<unsigned, 4>&);
+
+ struct CollectedSelectorHashes {
+ using HashVector = Vector<unsigned, 8>;
+ HashVector ids;
+ HashVector classes;
+ HashVector tags;
+ HashVector attributes;
+ };
+ static void collectSimpleSelectorHash(CollectedSelectorHashes&, const CSSSelector&);
+
private:
void initializeParentStack(Element& parent);
+ static CollectedSelectorHashes collectSelectorHashes(const CSSSelector& rightmostSelector);
+ static Hashes chooseSelectorHashesForFilter(const CollectedSelectorHashes&);
struct ParentStackFrame {
ParentStackFrame() : element(0) { }
Added: trunk/Source/WebCore/style/HasSelectorFilter.cpp (0 => 287091)
--- trunk/Source/WebCore/style/HasSelectorFilter.cpp (rev 0)
+++ trunk/Source/WebCore/style/HasSelectorFilter.cpp 2021-12-15 19:45:12 UTC (rev 287091)
@@ -0,0 +1,109 @@
+/*
+ * Copyright (C) 2021 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS BE LIABLE FOR ANY
+ * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
+ * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "config.h"
+#include "HasSelectorFilter.h"
+
+#include "ElementIterator.h"
+#include "RuleFeature.h"
+#include "SelectorFilter.h"
+
+namespace WebCore::Style {
+
+// FIXME: Support additional pseudo-classes.
+static constexpr unsigned HoverSalt = 101;
+
+HasSelectorFilter::HasSelectorFilter(const Element& element, Type type)
+ : m_type(type)
+{
+ switch (type) {
+ case Type::Descendants:
+ for (auto& descendant : descendantsOfType<Element>(element))
+ add(descendant);
+ break;
+ case Type::Children:
+ for (auto& child : childrenOfType<Element>(element))
+ add(child);
+ break;
+ }
+}
+
+auto HasSelectorFilter::typeForMatchElement(MatchElement matchElement) -> std::optional<Type>
+{
+ switch (matchElement) {
+ case MatchElement::HasChild:
+ return Type::Children;
+ case MatchElement::HasDescendant:
+ return Type::Descendants;
+ default:
+ return { };
+ }
+}
+
+auto HasSelectorFilter::makeKey(const CSSSelector& hasSelector) -> Key
+{
+ SelectorFilter::CollectedSelectorHashes hashes;
+ bool hasHoverInCompound = false;
+ for (auto* simpleSelector = &hasSelector; simpleSelector; simpleSelector = simpleSelector->tagHistory()) {
+ if (simpleSelector->match() == CSSSelector::PseudoClass && simpleSelector->pseudoClassType() == CSSSelector::PseudoClassHover)
+ hasHoverInCompound = true;
+ SelectorFilter::collectSimpleSelectorHash(hashes, *simpleSelector);
+ if (!hashes.ids.isEmpty())
+ break;
+ if (simpleSelector->relation() != CSSSelector::Subselector)
+ break;
+ }
+
+ auto pickKey = [&](auto& hashVector) -> Key {
+ if (hashVector.isEmpty())
+ return 0;
+ if (hasHoverInCompound)
+ return hashVector[0] * HoverSalt;
+ return hashVector[0];
+ };
+
+ if (auto key = pickKey(hashes.ids))
+ return key;
+ if (auto key = pickKey(hashes.classes))
+ return key;
+ if (auto key = pickKey(hashes.attributes))
+ return key;
+ return pickKey(hashes.tags);
+}
+
+void HasSelectorFilter::add(const Element& element)
+{
+ Vector<unsigned, 4> elementHashes;
+ SelectorFilter::collectElementIdentifierHashes(element, elementHashes);
+
+ for (auto hash : elementHashes)
+ m_filter.add(hash);
+
+ if (element.hovered()) {
+ for (auto hash : elementHashes)
+ m_filter.add(hash * HoverSalt);
+ }
+}
+
+}
Copied: trunk/Source/WebCore/style/HasSelectorFilter.h (from rev 287090, trunk/Source/WebCore/style/SelectorMatchingState.h) (0 => 287091)
--- trunk/Source/WebCore/style/HasSelectorFilter.h (rev 0)
+++ trunk/Source/WebCore/style/HasSelectorFilter.h 2021-12-15 19:45:12 UTC (rev 287091)
@@ -0,0 +1,59 @@
+/*
+ * Copyright (C) 2021 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS BE LIABLE FOR ANY
+ * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
+ * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#pragma once
+
+#include "CSSSelector.h"
+#include <wtf/BloomFilter.h>
+
+namespace WebCore {
+namespace Style {
+
+enum class MatchElement : uint8_t;
+
+class HasSelectorFilter {
+ WTF_MAKE_FAST_ALLOCATED;
+public:
+ enum class Type : uint8_t { Children, Descendants };
+ HasSelectorFilter(const Element&, Type);
+
+ Type type() const { return m_type; }
+ static std::optional<Type> typeForMatchElement(MatchElement);
+
+ using Key = unsigned;
+ static Key makeKey(const CSSSelector& hasSelector);
+
+ bool reject(const CSSSelector& hasSelector) const { return reject(makeKey(hasSelector)); }
+ bool reject(Key key) const { return !m_filter.mayContain(key); }
+
+
+private:
+ void add(const Element&);
+
+ const Type m_type;
+ BloomFilter<12> m_filter;
+};
+
+}
+}
Modified: trunk/Source/WebCore/style/SelectorMatchingState.h (287090 => 287091)
--- trunk/Source/WebCore/style/SelectorMatchingState.h 2021-12-15 19:42:28 UTC (rev 287090)
+++ trunk/Source/WebCore/style/SelectorMatchingState.h 2021-12-15 19:45:12 UTC (rev 287091)
@@ -24,23 +24,32 @@
#pragma once
+#include "HasSelectorFilter.h"
#include "SelectorFilter.h"
#include <wtf/HashMap.h>
namespace WebCore::Style {
-using HasPseudoClassCacheKey = std::pair<const CSSSelector*, const Element*>;
+using HasPseudoClassCacheKey = std::pair<const Element*, const CSSSelector*>;
+using HasPseudoClassFilterKey = std::pair<const Element*, uint8_t>;
enum class HasPseudoClassMatch : uint8_t { None, Matches, Fails, FailsSubtree };
struct SelectorMatchingState {
SelectorFilter selectorFilter;
+
HashMap<HasPseudoClassCacheKey, HasPseudoClassMatch> hasPseudoClassMatchCache;
+ HashMap<HasPseudoClassFilterKey, std::unique_ptr<HasSelectorFilter>> hasPseudoClassSelectorFilters;
};
-inline HasPseudoClassCacheKey makeHasPseudoClassCacheKey(const CSSSelector& selector, const Element& element)
+inline HasPseudoClassCacheKey makeHasPseudoClassCacheKey(const Element& element, const CSSSelector& selector)
{
- return { &selector, &element };
+ return { &element, &selector };
}
+inline HasPseudoClassFilterKey makeHasPseudoClassFilterKey(const Element& element, HasSelectorFilter::Type type)
+{
+ return { &element, static_cast<uint8_t>(type) };
}
+
+}
