Changeset 288012 in webkit


Ignore:
Timestamp:
Jan 14, 2022 3:56:51 AM (6 months ago)
Author:
Antti Koivisto
Message:

[:has() pseudo-class] Avoid O(n2) 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:

Location:
trunk
Files:
2 added
8 edited

Legend:

Unmodified
Added
Removed

  • trunk/LayoutTests/ChangeLog

    r288009 r288012  
     12022-01-14  Antti Koivisto  <antti@apple.com>
     2
     3        [:has() pseudo-class] Avoid O(n^2) in style invalidation with repeated DOM mutations
     4        https://bugs.webkit.org/show_bug.cgi?id=234842
     5        <rdar://problem/87397176>
     6
     7        Reviewed by Dean Jackson.
     8
     9        * TestExpectations:
     10
    1112022-01-13  Antoine Quint  <graouts@webkit.org>
    212

  • trunk/LayoutTests/TestExpectations

    r288009 r288012  
    14891489webkit.org/b/223497 imported/w3c/web-platform-tests/css/selectors/nesting.html [ ImageOnlyFailure ]
    14901490imported/w3c/web-platform-tests/css/selectors/xml-class-selector.xml [ ImageOnlyFailure ]
     1491
     1492# This test is bit heavy for debug
     1493[ Debug ] imported/w3c/web-platform-tests/css/selectors/invalidation/has-complexity.html [ Skip ]
    14911494
    14921495# ref for this is under a directory that is not yet imported

  • trunk/LayoutTests/imported/w3c/ChangeLog

    r288009 r288012  
     12022-01-14  Antti Koivisto  <antti@apple.com>
     2
     3        [:has() pseudo-class] Avoid O(n^2) in style invalidation with repeated DOM mutations
     4        https://bugs.webkit.org/show_bug.cgi?id=234842
     5        <rdar://problem/87397176>
     6
     7        Reviewed by Dean Jackson.
     8
     9        * web-platform-tests/css/selectors/invalidation/has-complexity-expected.txt: Added.
     10        * web-platform-tests/css/selectors/invalidation/has-complexity.html: Added.
     11
    1122022-01-13  Antoine Quint  <graouts@webkit.org>
    213

  • trunk/Source/WebCore/ChangeLog

    r288011 r288012  
     12022-01-14  Antti Koivisto  <antti@apple.com>
     2
     3        [:has() pseudo-class] Avoid O(n^2) in style invalidation with repeated DOM mutations
     4        https://bugs.webkit.org/show_bug.cgi?id=234842
     5        <rdar://problem/87397176>
     6
     7        Reviewed by Dean Jackson.
     8
     9        Use invalidation selectors to check if a given mutation needs :has() invalidation.
     10
     11        Test: imported/w3c/web-platform-tests/css/selectors/invalidation/has-complexity.html
     12
     13        * css/SelectorChecker.cpp:
     14        (WebCore::SelectorChecker::checkOne const):
     15        * css/SelectorChecker.h:
     16        * style/ChildChangeInvalidation.cpp:
     17        (WebCore::Style::ChildChangeInvalidation::invalidateForChangedElement):
     18
     19        Invalidate only if the invalidation ruleset has an invalidation selector that matches
     20        the added/removed element. Even in that case we only need to invalidate if that selector
     21        has not already matched within this parent.
     22
     23        As we don't have persistent state that would remember what already matched accross multiple
     24        mutations, approximate this by checking if the closest sibling matched.
     25
     26        (WebCore::Style::ChildChangeInvalidation::invalidateForHasBeforeMutation):
     27        (WebCore::Style::ChildChangeInvalidation::invalidateForHasAfterMutation):
     28        * style/ChildChangeInvalidation.h:
     29
    1302022-01-14  Nikolas Zimmermann  <nzimmermann@igalia.com>
    231

  • trunk/Source/WebCore/css/SelectorChecker.cpp

    r287222 r288012  
    10851085            const Node* contextualReferenceNode = !checkingContext.scope ? element.document().documentElement() : checkingContext.scope;
    10861086
    1087             bool matches = &element == contextualReferenceNode;
     1087            bool matches = &element == contextualReferenceNode || checkingContext.matchesAllScopes;
    10881088
    10891089            if (!matches && checkingContext.scope) {

  • trunk/Source/WebCore/css/SelectorChecker.h

    r286302 r288012  
    9696        AtomString nameForHightlightPseudoElement;
    9797        const ContainerNode* scope { nullptr };
     98        bool matchesAllScopes { false };
    9899        Style::ScopeOrdinal styleScopeOrdinal { Style::ScopeOrdinal::Element };
    99100        Style::SelectorMatchingState* selectorMatchingState { nullptr };

  • trunk/Source/WebCore/style/ChildChangeInvalidation.cpp

    r287973 r288012  
    3838namespace WebCore::Style {
    3939
    40 void ChildChangeInvalidation::invalidateForChangedElement(Element& changedElement)
     40void ChildChangeInvalidation::invalidateForChangedElement(Element& changedElement, MatchingHasSelectors& matchingHasSelectors)
    4141{
    4242    auto& ruleSets = parentElement().styleResolver().ruleSets();
    … …  
    4444    Invalidator::MatchElementRuleSets matchElementRuleSets;
    4545
    46     bool isDescendant = changedElement.parentElement() != &parentElement();
    47 
    48     auto canAffectAncestors = [&](MatchElement matchElement) {
    49         if (!isDescendant)
     46    bool isChild = changedElement.parentElement() == &parentElement();
     47
     48    auto canAffectElementsWithStyle = [&](MatchElement matchElement) {
     49        switch (matchElement) {
     50        case MatchElement::HasSibling:
     51        case MatchElement::HasChild:
     52            return isChild;
     53        case MatchElement::HasDescendant:
     54        case MatchElement::HasSiblingDescendant:
     55        case MatchElement::HasNonSubject:
    5056            return true;
    51         return matchElement == MatchElement::HasDescendant
    52             || matchElement == MatchElement::HasSiblingDescendant
    53             || matchElement == MatchElement::HasNonSubject;
     57        default:
     58            ASSERT_NOT_REACHED();
     59            return false;
     60        }
     61    };
     62
     63    bool isFirst = isChild && m_childChange.previousSiblingElement == changedElement.previousElementSibling();
     64
     65    auto hasMatchingInvalidationSelector = [&](auto& invalidationRuleSet) {
     66        SelectorChecker selectorChecker(changedElement.document());
     67        SelectorChecker::CheckingContext checkingContext(SelectorChecker::Mode::CollectingRulesIgnoringVirtualPseudoElements);
     68        checkingContext.matchesAllScopes = true;
     69
     70        for (auto* selector : invalidationRuleSet.invalidationSelectors) {
     71            if (isFirst) {
     72                // If this :has() matches ignoring this mutation, nothing actually changes and we don't need to invalidate.
     73                // FIXME: We could cache this state across invalidations instead of just testing a single sibling.
     74                auto* sibling = m_childChange.previousSiblingElement ? m_childChange.previousSiblingElement : m_childChange.nextSiblingElement;
     75                if (sibling && selectorChecker.match(*selector, *sibling, checkingContext)) {
     76                    matchingHasSelectors.add(selector);
     77                    continue;
     78                }
     79            }
     80
     81            if (matchingHasSelectors.contains(selector))
     82                continue;
     83
     84            if (selectorChecker.match(*selector, changedElement, checkingContext)) {
     85                matchingHasSelectors.add(selector);
     86                return true;
     87            }
     88        }
     89        return false;
    5490    };
    5591
    … …  
    5894            return;
    5995        for (auto& invalidationRuleSet : *invalidationRuleSets) {
    60             if (!canAffectAncestors(invalidationRuleSet.matchElement))
     96            if (!canAffectElementsWithStyle(invalidationRuleSet.matchElement))
     97                continue;
     98            if (!hasMatchingInvalidationSelector(invalidationRuleSet))
    6199                continue;
    62100            Invalidator::addToMatchElementRuleSets(matchElementRuleSets, invalidationRuleSet);
    … …  
    77115        return;
    78116
     117    MatchingHasSelectors matchingHasSelectors;
     118
    79119    traverseRemovedElements([&](auto& changedElement) {
    80         invalidateForChangedElement(changedElement);
     120        invalidateForChangedElement(changedElement, matchingHasSelectors);
    81121    });
    82122}
    … …  
    89129        return;
    90130
     131    MatchingHasSelectors matchingHasSelectors;
     132
    91133    traverseAddedElements([&](auto& changedElement) {
    92         invalidateForChangedElement(changedElement);
     134        invalidateForChangedElement(changedElement, matchingHasSelectors);
    93135    });
    94136}
    … …  
    107149    bool needsDescendantTraversal = Style::needsDescendantTraversal(features);
    108150
    109     auto* toRemove = m_childChange.previousSiblingElement ? m_childChange.previousSiblingElement->nextElementSibling() : parentElement().firstElementChild();
    110     for (; toRemove != m_childChange.nextSiblingElement; toRemove = toRemove->nextElementSibling()) {
     151    auto* firstToRemove = m_childChange.previousSiblingElement ? m_childChange.previousSiblingElement->nextElementSibling() : parentElement().firstElementChild();
     152
     153    for (auto* toRemove = firstToRemove; toRemove != m_childChange.nextSiblingElement; toRemove = toRemove->nextElementSibling()) {
    111154        function(*toRemove);
    112155

  • trunk/Source/WebCore/style/ChildChangeInvalidation.h

    r287325 r288012  
    2929#include "StyleInvalidator.h"
    3030#include "StyleScope.h"
     31#include <wtf/HashSet.h>
    3132
    3233namespace WebCore {
    … …  
    4546    void invalidateAfterChange();
    4647    void checkForSiblingStyleChanges();
    47     void invalidateForChangedElement(Element&);
     48    using MatchingHasSelectors = HashSet<const CSSSelector*>;
     49    void invalidateForChangedElement(Element&, MatchingHasSelectors&);
    4850
    4951    template<typename Function> void traverseRemovedElements(Function&&);
Note: See TracChangeset for help on using the changeset viewer.