⚠ Archived content — this site is no longer maintained.   Current WebKit documentation is at docs.webkit.org.

Changeset 288502 in webkit


Ignore:
Timestamp:
Jan 24, 2022, 5:55:06 PM (5 years ago)
Author:
Russell Epstein
Message:

Cherry-pick r288012. rdar://problem/87397176

[: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:

git-svn-id: ​https://svn.webkit.org/repository/webkit/trunk@288012 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Location:
branches/safari-613-branch
Files:
2 added
8 edited

Legend:

Unmodified
Added
Removed

  • branches/safari-613-branch/LayoutTests/ChangeLog

    r288498 r288502  
     12022-01-24  Alan Coon  <alancoon@apple.com>
     2
     3        Cherry-pick r288012. rdar://problem/87397176
     4
     5    [:has() pseudo-class] Avoid O(n^2) in style invalidation with repeated DOM mutations
     6    https://bugs.webkit.org/show_bug.cgi?id=234842
     7    <rdar://problem/87397176>
     8   
     9    Reviewed by Dean Jackson.
     10   
     11    LayoutTests/imported/w3c:
     12   
     13    * web-platform-tests/css/selectors/invalidation/has-complexity-expected.txt: Added.
     14    * web-platform-tests/css/selectors/invalidation/has-complexity.html: Added.
     15   
     16    Source/WebCore:
     17   
     18    Use invalidation selectors to check if a given mutation needs :has() invalidation.
     19   
     20    Test: imported/w3c/web-platform-tests/css/selectors/invalidation/has-complexity.html
     21   
     22    * css/SelectorChecker.cpp:
     23    (WebCore::SelectorChecker::checkOne const):
     24    * css/SelectorChecker.h:
     25    * style/ChildChangeInvalidation.cpp:
     26    (WebCore::Style::ChildChangeInvalidation::invalidateForChangedElement):
     27   
     28    Invalidate only if the invalidation ruleset has an invalidation selector that matches
     29    the added/removed element. Even in that case we only need to invalidate if that selector
     30    has not already matched within this parent.
     31   
     32    As we don't have persistent state that would remember what already matched accross multiple
     33    mutations, approximate this by checking if the closest sibling matched.
     34   
     35    (WebCore::Style::ChildChangeInvalidation::invalidateForHasBeforeMutation):
     36    (WebCore::Style::ChildChangeInvalidation::invalidateForHasAfterMutation):
     37    * style/ChildChangeInvalidation.h:
     38   
     39    LayoutTests:
     40   
     41    * TestExpectations:
     42   
     43   
     44    git-svn-id: https://svn.webkit.org/repository/webkit/trunk@288012 268f45cc-cd09-0410-ab3c-d52691b4dbfc
     45
     46    2022-01-14  Antti Koivisto  <antti@apple.com>
     47
     48            [:has() pseudo-class] Avoid O(n^2) in style invalidation with repeated DOM mutations
     49            https://bugs.webkit.org/show_bug.cgi?id=234842
     50            <rdar://problem/87397176>
     51
     52            Reviewed by Dean Jackson.
     53
     54            * TestExpectations:
     55
    1562022-01-24  Alan Coon  <alancoon@apple.com>
    257

  • branches/safari-613-branch/LayoutTests/TestExpectations

    r287823 r288502  
    14781478webkit.org/b/223497 imported/w3c/web-platform-tests/css/selectors/nesting.html [ ImageOnlyFailure ]
    14791479imported/w3c/web-platform-tests/css/selectors/xml-class-selector.xml [ ImageOnlyFailure ]
     1480
     1481# This test is bit heavy for debug
     1482[ Debug ] imported/w3c/web-platform-tests/css/selectors/invalidation/has-complexity.html [ Skip ]
    14801483
    14811484# ref for this is under a directory that is not yet imported

  • branches/safari-613-branch/LayoutTests/imported/w3c/ChangeLog

    r288496 r288502  
     12022-01-24  Alan Coon  <alancoon@apple.com>
     2
     3        Cherry-pick r288012. rdar://problem/87397176
     4
     5    [:has() pseudo-class] Avoid O(n^2) in style invalidation with repeated DOM mutations
     6    https://bugs.webkit.org/show_bug.cgi?id=234842
     7    <rdar://problem/87397176>
     8   
     9    Reviewed by Dean Jackson.
     10   
     11    LayoutTests/imported/w3c:
     12   
     13    * web-platform-tests/css/selectors/invalidation/has-complexity-expected.txt: Added.
     14    * web-platform-tests/css/selectors/invalidation/has-complexity.html: Added.
     15   
     16    Source/WebCore:
     17   
     18    Use invalidation selectors to check if a given mutation needs :has() invalidation.
     19   
     20    Test: imported/w3c/web-platform-tests/css/selectors/invalidation/has-complexity.html
     21   
     22    * css/SelectorChecker.cpp:
     23    (WebCore::SelectorChecker::checkOne const):
     24    * css/SelectorChecker.h:
     25    * style/ChildChangeInvalidation.cpp:
     26    (WebCore::Style::ChildChangeInvalidation::invalidateForChangedElement):
     27   
     28    Invalidate only if the invalidation ruleset has an invalidation selector that matches
     29    the added/removed element. Even in that case we only need to invalidate if that selector
     30    has not already matched within this parent.
     31   
     32    As we don't have persistent state that would remember what already matched accross multiple
     33    mutations, approximate this by checking if the closest sibling matched.
     34   
     35    (WebCore::Style::ChildChangeInvalidation::invalidateForHasBeforeMutation):
     36    (WebCore::Style::ChildChangeInvalidation::invalidateForHasAfterMutation):
     37    * style/ChildChangeInvalidation.h:
     38   
     39    LayoutTests:
     40   
     41    * TestExpectations:
     42   
     43   
     44    git-svn-id: https://svn.webkit.org/repository/webkit/trunk@288012 268f45cc-cd09-0410-ab3c-d52691b4dbfc
     45
     46    2022-01-14  Antti Koivisto  <antti@apple.com>
     47
     48            [:has() pseudo-class] Avoid O(n^2) in style invalidation with repeated DOM mutations
     49            https://bugs.webkit.org/show_bug.cgi?id=234842
     50            <rdar://problem/87397176>
     51
     52            Reviewed by Dean Jackson.
     53
     54            * web-platform-tests/css/selectors/invalidation/has-complexity-expected.txt: Added.
     55            * web-platform-tests/css/selectors/invalidation/has-complexity.html: Added.
     56
    1572022-01-24  Alan Coon  <alancoon@apple.com>
    258

  • branches/safari-613-branch/Source/WebCore/ChangeLog

    r288500 r288502  
     12022-01-24  Alan Coon  <alancoon@apple.com>
     2
     3        Cherry-pick r288012. rdar://problem/87397176
     4
     5    [:has() pseudo-class] Avoid O(n^2) in style invalidation with repeated DOM mutations
     6    https://bugs.webkit.org/show_bug.cgi?id=234842
     7    <rdar://problem/87397176>
     8   
     9    Reviewed by Dean Jackson.
     10   
     11    LayoutTests/imported/w3c:
     12   
     13    * web-platform-tests/css/selectors/invalidation/has-complexity-expected.txt: Added.
     14    * web-platform-tests/css/selectors/invalidation/has-complexity.html: Added.
     15   
     16    Source/WebCore:
     17   
     18    Use invalidation selectors to check if a given mutation needs :has() invalidation.
     19   
     20    Test: imported/w3c/web-platform-tests/css/selectors/invalidation/has-complexity.html
     21   
     22    * css/SelectorChecker.cpp:
     23    (WebCore::SelectorChecker::checkOne const):
     24    * css/SelectorChecker.h:
     25    * style/ChildChangeInvalidation.cpp:
     26    (WebCore::Style::ChildChangeInvalidation::invalidateForChangedElement):
     27   
     28    Invalidate only if the invalidation ruleset has an invalidation selector that matches
     29    the added/removed element. Even in that case we only need to invalidate if that selector
     30    has not already matched within this parent.
     31   
     32    As we don't have persistent state that would remember what already matched accross multiple
     33    mutations, approximate this by checking if the closest sibling matched.
     34   
     35    (WebCore::Style::ChildChangeInvalidation::invalidateForHasBeforeMutation):
     36    (WebCore::Style::ChildChangeInvalidation::invalidateForHasAfterMutation):
     37    * style/ChildChangeInvalidation.h:
     38   
     39    LayoutTests:
     40   
     41    * TestExpectations:
     42   
     43   
     44    git-svn-id: https://svn.webkit.org/repository/webkit/trunk@288012 268f45cc-cd09-0410-ab3c-d52691b4dbfc
     45
     46    2022-01-14  Antti Koivisto  <antti@apple.com>
     47
     48            [:has() pseudo-class] Avoid O(n^2) in style invalidation with repeated DOM mutations
     49            https://bugs.webkit.org/show_bug.cgi?id=234842
     50            <rdar://problem/87397176>
     51
     52            Reviewed by Dean Jackson.
     53
     54            Use invalidation selectors to check if a given mutation needs :has() invalidation.
     55
     56            Test: imported/w3c/web-platform-tests/css/selectors/invalidation/has-complexity.html
     57
     58            * css/SelectorChecker.cpp:
     59            (WebCore::SelectorChecker::checkOne const):
     60            * css/SelectorChecker.h:
     61            * style/ChildChangeInvalidation.cpp:
     62            (WebCore::Style::ChildChangeInvalidation::invalidateForChangedElement):
     63
     64            Invalidate only if the invalidation ruleset has an invalidation selector that matches
     65            the added/removed element. Even in that case we only need to invalidate if that selector
     66            has not already matched within this parent.
     67
     68            As we don't have persistent state that would remember what already matched accross multiple
     69            mutations, approximate this by checking if the closest sibling matched.
     70
     71            (WebCore::Style::ChildChangeInvalidation::invalidateForHasBeforeMutation):
     72            (WebCore::Style::ChildChangeInvalidation::invalidateForHasAfterMutation):
     73            * style/ChildChangeInvalidation.h:
     74
    1752022-01-24  Alan Coon  <alancoon@apple.com>
    276

  • branches/safari-613-branch/Source/WebCore/css/SelectorChecker.cpp

    r287222 r288502  
    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) {

  • branches/safari-613-branch/Source/WebCore/css/SelectorChecker.h

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

  • branches/safari-613-branch/Source/WebCore/style/ChildChangeInvalidation.cpp

    r288500 r288502  
    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

  • branches/safari-613-branch/Source/WebCore/style/ChildChangeInvalidation.h

    r287325 r288502  
    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.