Title: [286494] trunk/Source/WebCore
- Revision
- 286494
- Author
- an...@apple.com
- Date
- 2021-12-03 09:10:13 -0800 (Fri, 03 Dec 2021)
Log Message
[:has() pseudo-class] Improve result caching
https://bugs.webkit.org/show_bug.cgi?id=233806
Reviewed by Simon Fraser.
Improve caching to to avoid O(n^2) cases during invalidation and style resolution.
* css/SelectorChecker.cpp:
(WebCore::SelectorChecker::matchHasPseudoClass const):
Cache matches as well as failures.
Cache failures that don't apply to subtrees.
Check cached matches and failures for all :has() match element types.
* style/SelectorMatchingState.h:
Modified Paths
Diff
Modified: trunk/Source/WebCore/ChangeLog (286493 => 286494)
--- trunk/Source/WebCore/ChangeLog 2021-12-03 17:08:36 UTC (rev 286493)
+++ trunk/Source/WebCore/ChangeLog 2021-12-03 17:10:13 UTC (rev 286494)
@@ -1,3 +1,21 @@
+2021-12-03 Antti Koivisto <an...@apple.com>
+
+ [:has() pseudo-class] Improve result caching
+ https://bugs.webkit.org/show_bug.cgi?id=233806
+
+ Reviewed by Simon Fraser.
+
+ Improve caching to to avoid O(n^2) cases during invalidation and style resolution.
+
+ * css/SelectorChecker.cpp:
+ (WebCore::SelectorChecker::matchHasPseudoClass const):
+
+ Cache matches as well as failures.
+ Cache failures that don't apply to subtrees.
+ Check cached matches and failures for all :has() match element types.
+
+ * style/SelectorMatchingState.h:
+
2021-12-03 Alex Christensen <achristen...@webkit.org>
Add room for more bytecode in WKContentRuleList file format
Modified: trunk/Source/WebCore/css/SelectorChecker.cpp (286493 => 286494)
--- trunk/Source/WebCore/css/SelectorChecker.cpp 2021-12-03 17:08:36 UTC (rev 286493)
+++ trunk/Source/WebCore/css/SelectorChecker.cpp 2021-12-03 17:10:13 UTC (rev 286494)
@@ -1249,8 +1249,22 @@
bool SelectorChecker::matchHasPseudoClass(CheckingContext& checkingContext, const Element& element, const CSSSelector& hasSelector) const
{
- // FIXME: This could be better in terms of performance.
+ 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) {
+ case Style::HasPseudoClassMatch::Matches:
+ return true;
+ case Style::HasPseudoClassMatch::Fails:
+ case Style::HasPseudoClassMatch::FailsSubtree:
+ return false;
+ case Style::HasPseudoClassMatch::None:
+ break;
+ }
+ }
+
SelectorChecker hasChecker(element.document());
bool matchedInsideScope = false;
@@ -1267,69 +1281,90 @@
};
auto checkDescendants = [&](const Element& descendantRoot) {
- auto descendants = descendantsOfType<Element>(descendantRoot);
- if (!descendants.first())
- return false;
-
- if (checkingContext.selectorMatchingState) {
- // See if we already know this :has() selector doesn't match in this subtree.
- auto& failureCache = checkingContext.selectorMatchingState->hasPseudoClassDescendantFailureCache;
- if (!failureCache.isEmpty()) {
- for (auto* ancestor = descendantRoot.parentElement(); ancestor; ancestor = ancestor->parentElement()) {
- if (failureCache.contains(Style::makeHasPseudoClassCacheKey(hasSelector, *ancestor)))
- return false;
+ for (auto it = descendantsOfType<Element>(descendantRoot).begin(); it;) {
+ auto& descendant = *it;
+ if (cache) {
+ auto key = Style::makeHasPseudoClassCacheKey(hasSelector, descendant);
+ if (cache->get(key) == Style::HasPseudoClassMatch::FailsSubtree) {
+ it.traverseNextSkippingChildren();
+ continue;
}
}
- }
-
- matchedInsideScope = false;
-
- for (auto& descendant : descendants) {
if (checkRelative(descendant))
return true;
- }
- if (checkingContext.selectorMatchingState && !matchedInsideScope) {
- auto& failureCache = checkingContext.selectorMatchingState->hasPseudoClassDescendantFailureCache;
- failureCache.add(Style::makeHasPseudoClassCacheKey(hasSelector, descendantRoot));
+ it.traverseNext();
}
return false;
};
- auto matchElement = Style::computeHasPseudoClassMatchElement(hasSelector);
+ auto match = [&] {
+ auto matchElement = Style::computeHasPseudoClassMatchElement(hasSelector);
- switch (matchElement) {
- case Style::MatchElement::HasChild:
- for (auto& child : childrenOfType<Element>(element)) {
- if (checkRelative(child))
+ switch (matchElement) {
+ // :has(> .child)
+ case Style::MatchElement::HasChild:
+ for (auto& child : childrenOfType<Element>(element)) {
+ if (checkRelative(child))
+ return true;
+ }
+ 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);
+ if (cache->get(key) == Style::HasPseudoClassMatch::FailsSubtree)
+ return false;
+ }
+ }
+ if (checkDescendants(element))
return true;
+ break;
}
- break;
- case Style::MatchElement::HasDescendant: {
- if (checkDescendants(element))
- return true;
- break;
- }
- case Style::MatchElement::HasSibling:
- for (auto* sibling = element.nextElementSibling(); sibling; sibling = sibling->nextElementSibling()) {
- if (checkRelative(*sibling))
- return true;
+ // FIXME: Add a separate case for adjacent combinator.
+ // :has(+ .sibling)
+ // :has(~ .sibling)
+ case Style::MatchElement::HasSibling:
+ for (auto* sibling = element.nextElementSibling(); sibling; sibling = sibling->nextElementSibling()) {
+ if (checkRelative(*sibling))
+ return true;
+ }
+ break;
+ // FIXME: Add a separate case for adjacent combinator.
+ // :has(+ .sibling .descendant)
+ // :has(~ .sibling .descendant)
+ case Style::MatchElement::HasSiblingDescendant:
+ for (auto* sibling = element.nextElementSibling(); sibling; sibling = sibling->nextElementSibling()) {
+ if (checkDescendants(*sibling))
+ return true;
+ }
+ break;
+
+ default:
+ ASSERT_NOT_REACHED();
+ break;
}
- break;
- case Style::MatchElement::HasSiblingDescendant:
- for (auto* sibling = element.nextElementSibling(); sibling; sibling = sibling->nextElementSibling()) {
- if (checkDescendants(*sibling))
- return true;
- }
- break;
+ return false;
+ };
- default:
- ASSERT_NOT_REACHED();
- break;
+ auto result = match();
+
+ if (cachedMatch) {
+ *cachedMatch = [&] {
+ if (result)
+ return Style::HasPseudoClassMatch::Matches;
+ if (matchedInsideScope)
+ return Style::HasPseudoClassMatch::Fails;
+ return Style::HasPseudoClassMatch::FailsSubtree;
+ }();
}
- return false;
+ return result;
}
bool SelectorChecker::checkScrollbarPseudoClass(const CheckingContext& checkingContext, const Element& element, const CSSSelector& selector) const
Modified: trunk/Source/WebCore/style/SelectorMatchingState.h (286493 => 286494)
--- trunk/Source/WebCore/style/SelectorMatchingState.h 2021-12-03 17:08:36 UTC (rev 286493)
+++ trunk/Source/WebCore/style/SelectorMatchingState.h 2021-12-03 17:10:13 UTC (rev 286494)
@@ -25,15 +25,17 @@
#pragma once
#include "SelectorFilter.h"
-#include <wtf/HashSet.h>
+#include <wtf/HashMap.h>
namespace WebCore::Style {
using HasPseudoClassCacheKey = std::pair<const CSSSelector*, const Element*>;
+enum class HasPseudoClassMatch : uint8_t { None, Matches, Fails, FailsSubtree };
+
struct SelectorMatchingState {
SelectorFilter selectorFilter;
- HashSet<HasPseudoClassCacheKey> hasPseudoClassDescendantFailureCache;
+ HashMap<HasPseudoClassCacheKey, HasPseudoClassMatch> hasPseudoClassMatchCache;
};
inline HasPseudoClassCacheKey makeHasPseudoClassCacheKey(const CSSSelector& selector, const Element& element)
_______________________________________________
webkit-changes mailing list
webkit-changes@lists.webkit.org
https://lists.webkit.org/mailman/listinfo/webkit-changes
