Title: [286302] trunk/Source/WebCore
- Revision
- 286302
- Author
- [email protected]
- Date
- 2021-11-30 10:03:28 -0800 (Tue, 30 Nov 2021)
Log Message
[:has() pseudo-class] Cache :has() failures for subtrees
https://bugs.webkit.org/show_bug.cgi?id=233631
Reviewed by Simon Fraser.
Add a temporary (single style resolution/invalidation scoped) cache that remembers whether
a given :has() argument has any matches in a subtree. This avoids repeated tree walks in
presence of very generic descendant matching :has() selectors.
* css/SelectorChecker.cpp:
(WebCore::SelectorChecker::checkOne const):
This optimization can be used if the :has() not matching wasn't about the scope.
(WebCore::SelectorChecker::matchHasPseudoClass const):
When we traverse a subtree and find no matches for a has selector add a cache entry saying so.
Before traversing test if any of the ancestors elements already have a cache entry saying there
are no matches in this subtree for this selector.
* css/SelectorChecker.h:
* style/ElementRuleCollector.cpp:
(WebCore::Style::ElementRuleCollector::ruleMatches):
* style/SelectorMatchingState.h:
(WebCore::Style::makeHasPseudoClassCacheKey):
Add the cache to SelectorMatchingState. It is available when selector filter is.
Modified Paths
Diff
Modified: trunk/Source/WebCore/ChangeLog (286301 => 286302)
--- trunk/Source/WebCore/ChangeLog 2021-11-30 16:44:18 UTC (rev 286301)
+++ trunk/Source/WebCore/ChangeLog 2021-11-30 18:03:28 UTC (rev 286302)
@@ -1,3 +1,33 @@
+2021-11-30 Antti Koivisto <[email protected]>
+
+ [:has() pseudo-class] Cache :has() failures for subtrees
+ https://bugs.webkit.org/show_bug.cgi?id=233631
+
+ Reviewed by Simon Fraser.
+
+ Add a temporary (single style resolution/invalidation scoped) cache that remembers whether
+ a given :has() argument has any matches in a subtree. This avoids repeated tree walks in
+ presence of very generic descendant matching :has() selectors.
+
+ * css/SelectorChecker.cpp:
+ (WebCore::SelectorChecker::checkOne const):
+
+ This optimization can be used if the :has() not matching wasn't about the scope.
+
+ (WebCore::SelectorChecker::matchHasPseudoClass const):
+
+ When we traverse a subtree and find no matches for a has selector add a cache entry saying so.
+ Before traversing test if any of the ancestors elements already have a cache entry saying there
+ are no matches in this subtree for this selector.
+
+ * css/SelectorChecker.h:
+ * style/ElementRuleCollector.cpp:
+ (WebCore::Style::ElementRuleCollector::ruleMatches):
+ * style/SelectorMatchingState.h:
+ (WebCore::Style::makeHasPseudoClassCacheKey):
+
+ Add the cache to SelectorMatchingState. It is available when selector filter is.
+
2021-11-30 Youenn Fablet <[email protected]>
Migrate some WebSWClientConnection messages to async replies
Modified: trunk/Source/WebCore/css/SelectorChecker.cpp (286301 => 286302)
--- trunk/Source/WebCore/css/SelectorChecker.cpp 2021-11-30 16:44:18 UTC (rev 286301)
+++ trunk/Source/WebCore/css/SelectorChecker.cpp 2021-11-30 18:03:28 UTC (rev 286302)
@@ -1085,9 +1085,15 @@
case CSSSelector::PseudoClassScope:
case CSSSelector::PseudoClassRelativeScope: {
const Node* contextualReferenceNode = !checkingContext.scope ? element.document().documentElement() : checkingContext.scope;
- if (&element == contextualReferenceNode)
- return true;
- break;
+
+ bool matches = &element == contextualReferenceNode;
+
+ if (!matches && checkingContext.scope) {
+ if (element.isDescendantOf(*checkingContext.scope))
+ checkingContext.matchedInsideScope = true;
+ }
+
+ return matches;
}
case CSSSelector::PseudoClassHost: {
if (!context.mustMatchHostPseudoClass)
@@ -1241,18 +1247,56 @@
return hasMatchedAnything;
}
-bool SelectorChecker::matchHasPseudoClass(CheckingContext&, const Element& element, const CSSSelector& hasSelector) const
+bool SelectorChecker::matchHasPseudoClass(CheckingContext& checkingContext, const Element& element, const CSSSelector& hasSelector) const
{
- // FIXME: This is almost the worst possible implementation in terms of performance.
+ // FIXME: This could be better in terms of performance.
SelectorChecker hasChecker(element.document());
+ bool matchedInsideScope = false;
auto checkRelative = [&](auto& elementToCheck) {
CheckingContext hasCheckingContext(SelectorChecker::Mode::ResolvingStyle);
hasCheckingContext.scope = &element;
- return hasChecker.match(hasSelector, elementToCheck, hasCheckingContext);
+
+ auto result = hasChecker.match(hasSelector, elementToCheck, hasCheckingContext);
+
+ if (hasCheckingContext.matchedInsideScope)
+ matchedInsideScope = true;
+
+ return result;
};
+ 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;
+ }
+ }
+ }
+
+ 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));
+ }
+
+ return false;
+ };
+
auto matchElement = Style::computeHasPseudoClassMatchElement(hasSelector);
switch (matchElement) {
@@ -1262,20 +1306,17 @@
return true;
}
break;
- case Style::MatchElement::HasDescendant:
- for (auto& descendant : descendantsOfType<Element>(element)) {
- if (checkRelative(descendant))
- return true;
- }
+ 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;
- for (auto& descendant : descendantsOfType<Element>(*sibling)) {
- if (checkRelative(descendant))
- return true;
- }
+ if (checkDescendants(*sibling))
+ return true;
}
break;
default:
Modified: trunk/Source/WebCore/css/SelectorChecker.h (286301 => 286302)
--- trunk/Source/WebCore/css/SelectorChecker.h 2021-11-30 16:44:18 UTC (rev 286301)
+++ trunk/Source/WebCore/css/SelectorChecker.h 2021-11-30 18:03:28 UTC (rev 286302)
@@ -29,6 +29,7 @@
#include "CSSSelector.h"
#include "Element.h"
+#include "SelectorMatchingState.h"
#include "StyleRelations.h"
#include "StyleScopeOrdinal.h"
@@ -95,10 +96,12 @@
AtomString nameForHightlightPseudoElement;
const ContainerNode* scope { nullptr };
Style::ScopeOrdinal styleScopeOrdinal { Style::ScopeOrdinal::Element };
+ Style::SelectorMatchingState* selectorMatchingState { nullptr };
// FIXME: It would be nicer to have a separate object for return values. This requires some more work in the selector compiler.
Style::Relations styleRelations;
PseudoIdSet pseudoIDSet;
+ bool matchedInsideScope { false };
};
bool match(const CSSSelector&, const Element&, CheckingContext&) const;
Modified: trunk/Source/WebCore/style/ElementRuleCollector.cpp (286301 => 286302)
--- trunk/Source/WebCore/style/ElementRuleCollector.cpp 2021-11-30 16:44:18 UTC (rev 286301)
+++ trunk/Source/WebCore/style/ElementRuleCollector.cpp 2021-11-30 18:03:28 UTC (rev 286302)
@@ -441,7 +441,8 @@
context.scrollbarState = m_pseudoElementRequest.scrollbarState;
context.nameForHightlightPseudoElement = m_pseudoElementRequest.highlightName;
context.styleScopeOrdinal = styleScopeOrdinal;
-
+ context.selectorMatchingState = m_selectorMatchingState;
+
bool selectorMatches;
#if ENABLE(CSS_SELECTOR_JIT)
if (compiledSelector.status == SelectorCompilationStatus::SelectorCheckerWithCheckingContext) {
Modified: trunk/Source/WebCore/style/SelectorMatchingState.h (286301 => 286302)
--- trunk/Source/WebCore/style/SelectorMatchingState.h 2021-11-30 16:44:18 UTC (rev 286301)
+++ trunk/Source/WebCore/style/SelectorMatchingState.h 2021-11-30 18:03:28 UTC (rev 286302)
@@ -25,11 +25,20 @@
#pragma once
#include "SelectorFilter.h"
+#include <wtf/HashSet.h>
namespace WebCore::Style {
+using HasPseudoClassCacheKey = std::pair<const CSSSelector*, const Element*>;
+
struct SelectorMatchingState {
SelectorFilter selectorFilter;
+ HashSet<HasPseudoClassCacheKey> hasPseudoClassDescendantFailureCache;
};
+inline HasPseudoClassCacheKey makeHasPseudoClassCacheKey(const CSSSelector& selector, const Element& element)
+{
+ return { &selector, &element };
}
+
+}
_______________________________________________
webkit-changes mailing list
[email protected]
https://lists.webkit.org/mailman/listinfo/webkit-changes
