Diff
Modified: branches/safari-613-branch/LayoutTests/ChangeLog (288501 => 288502)
--- branches/safari-613-branch/LayoutTests/ChangeLog 2022-01-25 01:55:01 UTC (rev 288501)
+++ branches/safari-613-branch/LayoutTests/ChangeLog 2022-01-25 01:55:06 UTC (rev 288502)
@@ -1,5 +1,60 @@
2022-01-24 Alan Coon <[email protected]>
+ Cherry-pick r288012. rdar://problem/87397176
+
+ [:has() pseudo-class] Avoid O(n^2) in style invalidation with repeated DOM mutations
+ https://bugs.webkit.org/show_bug.cgi?id=234842
+ <rdar://problem/87397176>
+
+ Reviewed by Dean Jackson.
+
+ LayoutTests/imported/w3c:
+
+ * web-platform-tests/css/selectors/invalidation/has-complexity-expected.txt: Added.
+ * web-platform-tests/css/selectors/invalidation/has-complexity.html: Added.
+
+ Source/WebCore:
+
+ Use invalidation selectors to check if a given mutation needs :has() invalidation.
+
+ Test: imported/w3c/web-platform-tests/css/selectors/invalidation/has-complexity.html
+
+ * css/SelectorChecker.cpp:
+ (WebCore::SelectorChecker::checkOne const):
+ * css/SelectorChecker.h:
+ * style/ChildChangeInvalidation.cpp:
+ (WebCore::Style::ChildChangeInvalidation::invalidateForChangedElement):
+
+ Invalidate only if the invalidation ruleset has an invalidation selector that matches
+ the added/removed element. Even in that case we only need to invalidate if that selector
+ has not already matched within this parent.
+
+ As we don't have persistent state that would remember what already matched accross multiple
+ mutations, approximate this by checking if the closest sibling matched.
+
+ (WebCore::Style::ChildChangeInvalidation::invalidateForHasBeforeMutation):
+ (WebCore::Style::ChildChangeInvalidation::invalidateForHasAfterMutation):
+ * style/ChildChangeInvalidation.h:
+
+ LayoutTests:
+
+ * TestExpectations:
+
+
+ git-svn-id: https://svn.webkit.org/repository/webkit/trunk@288012 268f45cc-cd09-0410-ab3c-d52691b4dbfc
+
+ 2022-01-14 Antti Koivisto <[email protected]>
+
+ [:has() pseudo-class] Avoid O(n^2) in style invalidation with repeated DOM mutations
+ https://bugs.webkit.org/show_bug.cgi?id=234842
+ <rdar://problem/87397176>
+
+ Reviewed by Dean Jackson.
+
+ * TestExpectations:
+
+2022-01-24 Alan Coon <[email protected]>
+
Cherry-pick r287934. rdar://problem/86578732
Web Inspector: Unhandled exception when moving cursor mid-token after receiving CSS property name completions
Modified: branches/safari-613-branch/LayoutTests/TestExpectations (288501 => 288502)
--- branches/safari-613-branch/LayoutTests/TestExpectations 2022-01-25 01:55:01 UTC (rev 288501)
+++ branches/safari-613-branch/LayoutTests/TestExpectations 2022-01-25 01:55:06 UTC (rev 288502)
@@ -1478,6 +1478,9 @@
webkit.org/b/223497 imported/w3c/web-platform-tests/css/selectors/nesting.html [ ImageOnlyFailure ]
imported/w3c/web-platform-tests/css/selectors/xml-class-selector.xml [ ImageOnlyFailure ]
+# This test is bit heavy for debug
+[ Debug ] imported/w3c/web-platform-tests/css/selectors/invalidation/has-complexity.html [ Skip ]
+
# ref for this is under a directory that is not yet imported
webkit.org/b/209735 imported/w3c/web-platform-tests/css/selectors/root-siblings.htm [ Skip ]
Modified: branches/safari-613-branch/LayoutTests/imported/w3c/ChangeLog (288501 => 288502)
--- branches/safari-613-branch/LayoutTests/imported/w3c/ChangeLog 2022-01-25 01:55:01 UTC (rev 288501)
+++ branches/safari-613-branch/LayoutTests/imported/w3c/ChangeLog 2022-01-25 01:55:06 UTC (rev 288502)
@@ -1,5 +1,61 @@
2022-01-24 Alan Coon <[email protected]>
+ Cherry-pick r288012. rdar://problem/87397176
+
+ [:has() pseudo-class] Avoid O(n^2) in style invalidation with repeated DOM mutations
+ https://bugs.webkit.org/show_bug.cgi?id=234842
+ <rdar://problem/87397176>
+
+ Reviewed by Dean Jackson.
+
+ LayoutTests/imported/w3c:
+
+ * web-platform-tests/css/selectors/invalidation/has-complexity-expected.txt: Added.
+ * web-platform-tests/css/selectors/invalidation/has-complexity.html: Added.
+
+ Source/WebCore:
+
+ Use invalidation selectors to check if a given mutation needs :has() invalidation.
+
+ Test: imported/w3c/web-platform-tests/css/selectors/invalidation/has-complexity.html
+
+ * css/SelectorChecker.cpp:
+ (WebCore::SelectorChecker::checkOne const):
+ * css/SelectorChecker.h:
+ * style/ChildChangeInvalidation.cpp:
+ (WebCore::Style::ChildChangeInvalidation::invalidateForChangedElement):
+
+ Invalidate only if the invalidation ruleset has an invalidation selector that matches
+ the added/removed element. Even in that case we only need to invalidate if that selector
+ has not already matched within this parent.
+
+ As we don't have persistent state that would remember what already matched accross multiple
+ mutations, approximate this by checking if the closest sibling matched.
+
+ (WebCore::Style::ChildChangeInvalidation::invalidateForHasBeforeMutation):
+ (WebCore::Style::ChildChangeInvalidation::invalidateForHasAfterMutation):
+ * style/ChildChangeInvalidation.h:
+
+ LayoutTests:
+
+ * TestExpectations:
+
+
+ git-svn-id: https://svn.webkit.org/repository/webkit/trunk@288012 268f45cc-cd09-0410-ab3c-d52691b4dbfc
+
+ 2022-01-14 Antti Koivisto <[email protected]>
+
+ [:has() pseudo-class] Avoid O(n^2) in style invalidation with repeated DOM mutations
+ https://bugs.webkit.org/show_bug.cgi?id=234842
+ <rdar://problem/87397176>
+
+ Reviewed by Dean Jackson.
+
+ * web-platform-tests/css/selectors/invalidation/has-complexity-expected.txt: Added.
+ * web-platform-tests/css/selectors/invalidation/has-complexity.html: Added.
+
+2022-01-24 Alan Coon <[email protected]>
+
Cherry-pick r287878. rdar://problem/85359803
::backdrop pseudo element should react to associated element event listeners
Added: branches/safari-613-branch/LayoutTests/imported/w3c/web-platform-tests/css/selectors/invalidation/has-complexity-expected.txt (0 => 288502)
--- branches/safari-613-branch/LayoutTests/imported/w3c/web-platform-tests/css/selectors/invalidation/has-complexity-expected.txt (rev 0)
+++ branches/safari-613-branch/LayoutTests/imported/w3c/web-platform-tests/css/selectors/invalidation/has-complexity-expected.txt 2022-01-25 01:55:06 UTC (rev 288502)
@@ -0,0 +1,9 @@
+
+PASS Before appending 25000 elements
+PASS After appending 25000 elements. This should not time out.
+PASS After appending another 25000 elements. This should not time out.
+PASS After appending div with 25000 elements. This should not time out.
+PASS After removing div with 25000 elements. This should not time out.
+PASS After removing 25000 elements one-by-one. This should not time out.
+PASS After removing the remaining elements. This should not time out.
+
Added: branches/safari-613-branch/LayoutTests/imported/w3c/web-platform-tests/css/selectors/invalidation/has-complexity.html (0 => 288502)
--- branches/safari-613-branch/LayoutTests/imported/w3c/web-platform-tests/css/selectors/invalidation/has-complexity.html (rev 0)
+++ branches/safari-613-branch/LayoutTests/imported/w3c/web-platform-tests/css/selectors/invalidation/has-complexity.html 2022-01-25 01:55:06 UTC (rev 288502)
@@ -0,0 +1,80 @@
+<!DOCTYPE html>
+<meta charset="utf-8">
+<title>CSS Selector Invalidation: :has() invalidation should not be O(n^2)</title>
+<link rel="author" title="Antti Koivisto" href=""
+<script src=""
+<script src=""
+<link rel="help" href=""
+<style>
+div, main { color: grey }
+main:has(span) .subject { color: red }
+main:has(span + span) .subject { color: green }
+main:has(final) .subject { color: blue }
+main:has(nonexistent + span) .subject { color: black }
+main:has(span) span { color: black }
+main:has(nonexistent) span { color: black }
+main:has(div div span) .subject { color: purple }
+</style>
+<main>
+ <div id=container>
+ <span></span>
+ </div>
+ <div id=subject class=subject></div>
+</main>
+<script>
+const grey = 'rgb(128, 128, 128)';
+const red = 'rgb(255, 0, 0)';
+const green = 'rgb(0, 128, 0)';
+const blue = 'rgb(0, 0, 255)';
+const purple = 'rgb(128, 0, 128)';
+
+function testColor(test_name, color) {
+ test(function() {
+ assert_equals(getComputedStyle(subject).color, color);
+ }, test_name);
+}
+
+const count = 25000;
+
+testColor(`Before appending ${count} elements`, red);
+
+for (let i = 0; i < count; ++i) {
+ const span = document.createElement("span");
+ container.appendChild(span);
+}
+
+testColor(`After appending ${count} elements. This should not time out.`, green);
+
+for (let i = 0; i < count - 1; ++i) {
+ const span = document.createElement("span");
+ container.appendChild(span);
+}
+
+const final = document.createElement("final");
+container.appendChild(final);
+
+testColor(`After appending another ${count} elements. This should not time out.`, blue);
+
+const div = document.createElement("div");
+for (let i = 0; i < count; ++i) {
+ const span = document.createElement("span");
+ div.appendChild(span);
+}
+container.appendChild(div);
+
+testColor(`After appending div with ${count} elements. This should not time out.`, purple);
+
+div.remove();
+
+testColor(`After removing div with ${count} elements. This should not time out.`, blue);
+
+for (let i = 0; i < count; ++i)
+ container.lastChild.remove();
+
+testColor(`After removing ${count} elements one-by-one. This should not time out.`, green);
+
+container.replaceChildren();
+
+testColor(`After removing the remaining elements. This should not time out.`, grey);
+
+</script>
Modified: branches/safari-613-branch/Source/WebCore/ChangeLog (288501 => 288502)
--- branches/safari-613-branch/Source/WebCore/ChangeLog 2022-01-25 01:55:01 UTC (rev 288501)
+++ branches/safari-613-branch/Source/WebCore/ChangeLog 2022-01-25 01:55:06 UTC (rev 288502)
@@ -1,5 +1,79 @@
2022-01-24 Alan Coon <[email protected]>
+ Cherry-pick r288012. rdar://problem/87397176
+
+ [:has() pseudo-class] Avoid O(n^2) in style invalidation with repeated DOM mutations
+ https://bugs.webkit.org/show_bug.cgi?id=234842
+ <rdar://problem/87397176>
+
+ Reviewed by Dean Jackson.
+
+ LayoutTests/imported/w3c:
+
+ * web-platform-tests/css/selectors/invalidation/has-complexity-expected.txt: Added.
+ * web-platform-tests/css/selectors/invalidation/has-complexity.html: Added.
+
+ Source/WebCore:
+
+ Use invalidation selectors to check if a given mutation needs :has() invalidation.
+
+ Test: imported/w3c/web-platform-tests/css/selectors/invalidation/has-complexity.html
+
+ * css/SelectorChecker.cpp:
+ (WebCore::SelectorChecker::checkOne const):
+ * css/SelectorChecker.h:
+ * style/ChildChangeInvalidation.cpp:
+ (WebCore::Style::ChildChangeInvalidation::invalidateForChangedElement):
+
+ Invalidate only if the invalidation ruleset has an invalidation selector that matches
+ the added/removed element. Even in that case we only need to invalidate if that selector
+ has not already matched within this parent.
+
+ As we don't have persistent state that would remember what already matched accross multiple
+ mutations, approximate this by checking if the closest sibling matched.
+
+ (WebCore::Style::ChildChangeInvalidation::invalidateForHasBeforeMutation):
+ (WebCore::Style::ChildChangeInvalidation::invalidateForHasAfterMutation):
+ * style/ChildChangeInvalidation.h:
+
+ LayoutTests:
+
+ * TestExpectations:
+
+
+ git-svn-id: https://svn.webkit.org/repository/webkit/trunk@288012 268f45cc-cd09-0410-ab3c-d52691b4dbfc
+
+ 2022-01-14 Antti Koivisto <[email protected]>
+
+ [:has() pseudo-class] Avoid O(n^2) in style invalidation with repeated DOM mutations
+ https://bugs.webkit.org/show_bug.cgi?id=234842
+ <rdar://problem/87397176>
+
+ Reviewed by Dean Jackson.
+
+ Use invalidation selectors to check if a given mutation needs :has() invalidation.
+
+ Test: imported/w3c/web-platform-tests/css/selectors/invalidation/has-complexity.html
+
+ * css/SelectorChecker.cpp:
+ (WebCore::SelectorChecker::checkOne const):
+ * css/SelectorChecker.h:
+ * style/ChildChangeInvalidation.cpp:
+ (WebCore::Style::ChildChangeInvalidation::invalidateForChangedElement):
+
+ Invalidate only if the invalidation ruleset has an invalidation selector that matches
+ the added/removed element. Even in that case we only need to invalidate if that selector
+ has not already matched within this parent.
+
+ As we don't have persistent state that would remember what already matched accross multiple
+ mutations, approximate this by checking if the closest sibling matched.
+
+ (WebCore::Style::ChildChangeInvalidation::invalidateForHasBeforeMutation):
+ (WebCore::Style::ChildChangeInvalidation::invalidateForHasAfterMutation):
+ * style/ChildChangeInvalidation.h:
+
+2022-01-24 Alan Coon <[email protected]>
+
Cherry-pick r287973. rdar://problem/87533906
[:has() pseudo-class] Collect invalidation selectors for child invalidation
Modified: branches/safari-613-branch/Source/WebCore/css/SelectorChecker.cpp (288501 => 288502)
--- branches/safari-613-branch/Source/WebCore/css/SelectorChecker.cpp 2022-01-25 01:55:01 UTC (rev 288501)
+++ branches/safari-613-branch/Source/WebCore/css/SelectorChecker.cpp 2022-01-25 01:55:06 UTC (rev 288502)
@@ -1084,7 +1084,7 @@
case CSSSelector::PseudoClassRelativeScope: {
const Node* contextualReferenceNode = !checkingContext.scope ? element.document().documentElement() : checkingContext.scope;
- bool matches = &element == contextualReferenceNode;
+ bool matches = &element == contextualReferenceNode || checkingContext.matchesAllScopes;
if (!matches && checkingContext.scope) {
if (element.isDescendantOf(*checkingContext.scope))
Modified: branches/safari-613-branch/Source/WebCore/css/SelectorChecker.h (288501 => 288502)
--- branches/safari-613-branch/Source/WebCore/css/SelectorChecker.h 2022-01-25 01:55:01 UTC (rev 288501)
+++ branches/safari-613-branch/Source/WebCore/css/SelectorChecker.h 2022-01-25 01:55:06 UTC (rev 288502)
@@ -95,6 +95,7 @@
std::optional<StyleScrollbarState> scrollbarState;
AtomString nameForHightlightPseudoElement;
const ContainerNode* scope { nullptr };
+ bool matchesAllScopes { false };
Style::ScopeOrdinal styleScopeOrdinal { Style::ScopeOrdinal::Element };
Style::SelectorMatchingState* selectorMatchingState { nullptr };
Modified: branches/safari-613-branch/Source/WebCore/style/ChildChangeInvalidation.cpp (288501 => 288502)
--- branches/safari-613-branch/Source/WebCore/style/ChildChangeInvalidation.cpp 2022-01-25 01:55:01 UTC (rev 288501)
+++ branches/safari-613-branch/Source/WebCore/style/ChildChangeInvalidation.cpp 2022-01-25 01:55:06 UTC (rev 288502)
@@ -37,28 +37,66 @@
namespace WebCore::Style {
-void ChildChangeInvalidation::invalidateForChangedElement(Element& changedElement)
+void ChildChangeInvalidation::invalidateForChangedElement(Element& changedElement, MatchingHasSelectors& matchingHasSelectors)
{
auto& ruleSets = parentElement().styleResolver().ruleSets();
Invalidator::MatchElementRuleSets matchElementRuleSets;
- bool isDescendant = changedElement.parentElement() != &parentElement();
+ bool isChild = changedElement.parentElement() == &parentElement();
- auto canAffectAncestors = [&](MatchElement matchElement) {
- if (!isDescendant)
+ auto canAffectElementsWithStyle = [&](MatchElement matchElement) {
+ switch (matchElement) {
+ case MatchElement::HasSibling:
+ case MatchElement::HasChild:
+ return isChild;
+ case MatchElement::HasDescendant:
+ case MatchElement::HasSiblingDescendant:
+ case MatchElement::HasNonSubject:
return true;
- return matchElement == MatchElement::HasDescendant
- || matchElement == MatchElement::HasSiblingDescendant
- || matchElement == MatchElement::HasNonSubject;
+ default:
+ ASSERT_NOT_REACHED();
+ return false;
+ }
};
+ bool isFirst = isChild && m_childChange.previousSiblingElement == changedElement.previousElementSibling();
+
+ auto hasMatchingInvalidationSelector = [&](auto& invalidationRuleSet) {
+ SelectorChecker selectorChecker(changedElement.document());
+ SelectorChecker::CheckingContext checkingContext(SelectorChecker::Mode::CollectingRulesIgnoringVirtualPseudoElements);
+ checkingContext.matchesAllScopes = true;
+
+ for (auto* selector : invalidationRuleSet.invalidationSelectors) {
+ if (isFirst) {
+ // If this :has() matches ignoring this mutation, nothing actually changes and we don't need to invalidate.
+ // FIXME: We could cache this state across invalidations instead of just testing a single sibling.
+ auto* sibling = m_childChange.previousSiblingElement ? m_childChange.previousSiblingElement : m_childChange.nextSiblingElement;
+ if (sibling && selectorChecker.match(*selector, *sibling, checkingContext)) {
+ matchingHasSelectors.add(selector);
+ continue;
+ }
+ }
+
+ if (matchingHasSelectors.contains(selector))
+ continue;
+
+ if (selectorChecker.match(*selector, changedElement, checkingContext)) {
+ matchingHasSelectors.add(selector);
+ return true;
+ }
+ }
+ return false;
+ };
+
auto addHasInvalidation = [&](const Vector<InvalidationRuleSet>* invalidationRuleSets) {
if (!invalidationRuleSets)
return;
for (auto& invalidationRuleSet : *invalidationRuleSets) {
- if (!canAffectAncestors(invalidationRuleSet.matchElement))
+ if (!canAffectElementsWithStyle(invalidationRuleSet.matchElement))
continue;
+ if (!hasMatchingInvalidationSelector(invalidationRuleSet))
+ continue;
Invalidator::addToMatchElementRuleSets(matchElementRuleSets, invalidationRuleSet);
}
};
@@ -76,8 +114,10 @@
if (m_childChange.isInsertion() && m_childChange.type != ContainerNode::ChildChange::Type::AllChildrenReplaced)
return;
+ MatchingHasSelectors matchingHasSelectors;
+
traverseRemovedElements([&](auto& changedElement) {
- invalidateForChangedElement(changedElement);
+ invalidateForChangedElement(changedElement, matchingHasSelectors);
});
}
@@ -88,8 +128,10 @@
if (!m_childChange.isInsertion())
return;
+ MatchingHasSelectors matchingHasSelectors;
+
traverseAddedElements([&](auto& changedElement) {
- invalidateForChangedElement(changedElement);
+ invalidateForChangedElement(changedElement, matchingHasSelectors);
});
}
@@ -106,8 +148,9 @@
auto& features = parentElement().styleResolver().ruleSets().features();
bool needsDescendantTraversal = Style::needsDescendantTraversal(features);
- auto* toRemove = m_childChange.previousSiblingElement ? m_childChange.previousSiblingElement->nextElementSibling() : parentElement().firstElementChild();
- for (; toRemove != m_childChange.nextSiblingElement; toRemove = toRemove->nextElementSibling()) {
+ auto* firstToRemove = m_childChange.previousSiblingElement ? m_childChange.previousSiblingElement->nextElementSibling() : parentElement().firstElementChild();
+
+ for (auto* toRemove = firstToRemove; toRemove != m_childChange.nextSiblingElement; toRemove = toRemove->nextElementSibling()) {
function(*toRemove);
if (!needsDescendantTraversal)
Modified: branches/safari-613-branch/Source/WebCore/style/ChildChangeInvalidation.h (288501 => 288502)
--- branches/safari-613-branch/Source/WebCore/style/ChildChangeInvalidation.h 2022-01-25 01:55:01 UTC (rev 288501)
+++ branches/safari-613-branch/Source/WebCore/style/ChildChangeInvalidation.h 2022-01-25 01:55:06 UTC (rev 288502)
@@ -28,6 +28,7 @@
#include "Element.h"
#include "StyleInvalidator.h"
#include "StyleScope.h"
+#include <wtf/HashSet.h>
namespace WebCore {
namespace Style {
@@ -44,7 +45,8 @@
void invalidateForHasAfterMutation();
void invalidateAfterChange();
void checkForSiblingStyleChanges();
- void invalidateForChangedElement(Element&);
+ using MatchingHasSelectors = HashSet<const CSSSelector*>;
+ void invalidateForChangedElement(Element&, MatchingHasSelectors&);
template<typename Function> void traverseRemovedElements(Function&&);
template<typename Function> void traverseAddedElements(Function&&);
