Changeset 286598 in webkit

Timestamp:

Dec 7, 2021, 9:49:42 AM (5 years ago)

Author:

Antti Koivisto

Message:

Use more specific keys for pseudo-class invalidation
​https://bugs.webkit.org/show_bug.cgi?id=233883

Reviewed by Simon Fraser.

Currently pseudo-class invalidation is keyed with pseudo-class type only. If we have rule like

.foo:hover { ... }

we end up considering this rule for every element whenever :hover state changes, whether the element has class 'foo' or not.

We can improve this by keying pseudo-class invalidation more narrowly with type/class, type/id or type/tag pairs.

• css/CSSSelector.cpp:

(WebCore::CSSSelector::CSSSelector):
(WebCore::CSSSelector::firstInCompound const):

Add a function to find the start of a compound selector.

• css/CSSSelector.h:

(WebCore::CSSSelector::tagHistory const):
(WebCore::CSSSelector::isFirstInTagHistory const):
(WebCore::CSSSelector::setNotFirstInTagHistory):

Add isFirstInTagHistory bit, similar to the isLastInTagHistory bit, to enable firstInCompound.

(WebCore::CSSSelector::CSSSelector):

• css/CSSSelectorList.cpp:

(WebCore::CSSSelectorList::CSSSelectorList):

Set the bit.

• style/PseudoClassChangeInvalidation.cpp:

(WebCore::Style::makePseudoClassInvalidationKeys):

Collect the id, tag and classes from the element and make keys out of them.

(WebCore::Style::PseudoClassChangeInvalidation::computeInvalidation):
(WebCore::Style::PseudoClassChangeInvalidation::collectRuleSets):

Use the keys to look up for matching invalidation rulesets.

• style/PseudoClassChangeInvalidation.h:
• style/RuleFeature.cpp:

(WebCore::Style::RuleFeatureSet::recursivelyCollectFeaturesFromSelector):
(WebCore::Style::makePseudoClassInvalidationKey):

Make a key out of a selector.
Search the compound for id, classes or tag.

(WebCore::Style::RuleFeatureSet::collectFeatures):
(WebCore::Style::RuleFeatureSet::add):
(WebCore::Style::RuleFeatureSet::clear):

• style/RuleFeature.h:
• style/StyleScopeRuleSets.cpp:

(WebCore::Style::ScopeRuleSets::pseudoClassInvalidationRuleSets const):

• style/StyleScopeRuleSets.h:

Location:

trunk/Source/WebCore

Files:

• ChangeLog (modified) (1 diff)
• css/CSSSelector.cpp (modified) (2 diffs)
• css/CSSSelector.h (modified) (6 diffs)
• css/CSSSelectorList.cpp (modified) (2 diffs)
• css/parser/CSSSelectorParser.cpp (modified) (1 diff)
• style/PseudoClassChangeInvalidation.cpp (modified) (3 diffs)
• style/PseudoClassChangeInvalidation.h (modified) (1 diff)
• style/RuleFeature.cpp (modified) (5 diffs)
• style/RuleFeature.h (modified) (4 diffs)
• style/StyleScopeRuleSets.cpp (modified) (1 diff)
• style/StyleScopeRuleSets.h (modified) (2 diffs)

trunk/Source/WebCore/ChangeLog

@@ +1 @@
+2021-12-07  Antti Koivisto  <antti@apple.com>
+
+        Use more specific keys for pseudo-class invalidation
+        https://bugs.webkit.org/show_bug.cgi?id=233883
+
+        Reviewed by Simon Fraser.
+
+        Currently pseudo-class invalidation is keyed with pseudo-class type only. If we have rule like
+
+        .foo:hover { ... }
+
+        we end up considering this rule for every element whenever :hover state changes, whether the element has class 'foo' or not.
+
+        We can improve this by keying pseudo-class invalidation more narrowly with type/class, type/id or type/tag pairs.
+
+        * css/CSSSelector.cpp:
+        (WebCore::CSSSelector::CSSSelector):
+        (WebCore::CSSSelector::firstInCompound const):
+
+        Add a function to find the start of a compound selector.
+
+        * css/CSSSelector.h:
+        (WebCore::CSSSelector::tagHistory const):
+        (WebCore::CSSSelector::isFirstInTagHistory const):
+        (WebCore::CSSSelector::setNotFirstInTagHistory):
+
+        Add isFirstInTagHistory bit, similar to the isLastInTagHistory bit, to enable firstInCompound.
+
+        (WebCore::CSSSelector::CSSSelector):
+        * css/CSSSelectorList.cpp:
+        (WebCore::CSSSelectorList::CSSSelectorList):
+
+        Set the bit.
+
+        * style/PseudoClassChangeInvalidation.cpp:
+        (WebCore::Style::makePseudoClassInvalidationKeys):
+
+        Collect the id, tag and classes from the element and make keys out of them.
+
+        (WebCore::Style::PseudoClassChangeInvalidation::computeInvalidation):
+        (WebCore::Style::PseudoClassChangeInvalidation::collectRuleSets):
+
+        Use the keys to look up for matching invalidation rulesets.
+
+        * style/PseudoClassChangeInvalidation.h:
+        * style/RuleFeature.cpp:
+        (WebCore::Style::RuleFeatureSet::recursivelyCollectFeaturesFromSelector):
+        (WebCore::Style::makePseudoClassInvalidationKey):
+
+        Make a key out of a selector.
+        Search the compound for id, classes or tag.
+
+        (WebCore::Style::RuleFeatureSet::collectFeatures):
+        (WebCore::Style::RuleFeatureSet::add):
+        (WebCore::Style::RuleFeatureSet::clear):
+        * style/RuleFeature.h:
+        * style/StyleScopeRuleSets.cpp:
+        (WebCore::Style::ScopeRuleSets::pseudoClassInvalidationRuleSets const):
+        * style/StyleScopeRuleSets.h:
+
 2021-12-07  Kimmo Kinnunen  <kkinnunen@apple.com>
 

trunk/Source/WebCore/css/CSSSelector.cpp

@@ -57 +57 @@
     , m_pseudoType(0)
     , m_isLastInSelectorList(false)
+    , m_isFirstInTagHistory(true)
     , m_isLastInTagHistory(true)
     , m_hasRareData(false)
@@ -289 +290 @@
 }
 
+const CSSSelector* CSSSelector::firstInCompound() const
+{
+    auto* selector = this;
+    while (!selector->isFirstInTagHistory()) {
+        auto* previousSelector = selector - 1;
+        if (previousSelector->relation() != Subselector)
+            break;
+        selector = previousSelector;
+    }
+    return selector;
+}
+
 bool CSSSelector::operator==(const CSSSelector& other) const
 {

trunk/Source/WebCore/css/CSSSelector.h

@@ -254 +254 @@
         // Selectors are kept in an array by CSSSelectorList. The next component of the selector is
         // the next item in the array.
-        const CSSSelector* tagHistory() const { return m_isLastInTagHistory ? 0 : const_cast<CSSSelector*>(this + 1); }
+        const CSSSelector* tagHistory() const { return m_isLastInTagHistory ? nullptr : this + 1; }
+        const CSSSelector* firstInCompound() const;
 
         const QualifiedName& tagQName() const;
@@ -340 +341 @@
         bool isLastInSelectorList() const { return m_isLastInSelectorList; }
         void setLastInSelectorList() { m_isLastInSelectorList = true; }
+        bool isFirstInTagHistory() const { return m_isFirstInTagHistory; }
         bool isLastInTagHistory() const { return m_isLastInTagHistory; }
+        void setNotFirstInTagHistory() { m_isFirstInTagHistory = false; }
         void setNotLastInTagHistory() { m_isLastInTagHistory = false; }
 
@@ -351 +354 @@
         mutable unsigned m_pseudoType    : 8; // PseudoType.
         unsigned m_isLastInSelectorList  : 1;
+        unsigned m_isFirstInTagHistory   : 1;
         unsigned m_isLastInTagHistory    : 1;
         unsigned m_hasRareData           : 1;
@@ -469 +473 @@
 }
 
+inline bool isLogicalCombinationPseudoClass(CSSSelector::PseudoClassType pseudoClassType)
+{
+    switch (pseudoClassType) {
+    case CSSSelector::PseudoClassIs:
+    case CSSSelector::PseudoClassWhere:
+    case CSSSelector::PseudoClassNot:
+    case CSSSelector::PseudoClassAny:
+    case CSSSelector::PseudoClassMatches:
+    case CSSSelector::PseudoClassHas:
+        return true;
+    default:
+        return false;
+    }
+}
+
 inline bool CSSSelector::isSiblingSelector() const
 {
@@ -512 +531 @@
     , m_pseudoType(0)
     , m_isLastInSelectorList(false)
+    , m_isFirstInTagHistory(true)
     , m_isLastInTagHistory(true)
     , m_hasRareData(false)
@@ -529 +549 @@
     , m_pseudoType(o.m_pseudoType)
     , m_isLastInSelectorList(o.m_isLastInSelectorList)
+    , m_isFirstInTagHistory(o.m_isFirstInTagHistory)
     , m_isLastInTagHistory(o.m_isLastInTagHistory)
     , m_hasRareData(o.m_hasRareData)

trunk/Source/WebCore/css/CSSSelectorList.cpp

@@ -56 +56 @@
     size_t arrayIndex = 0;
     for (size_t i = 0; i < selectorVector.size(); ++i) {
-        CSSParserSelector* current = selectorVector[i].get();
+        CSSParserSelector* first = selectorVector[i].get();
+        CSSParserSelector* current = first;
         while (current) {
             {
@@ -66 +67 @@
                 operator delete (currentSelector);
             }
+            if (current != first)
+                m_selectorArray[arrayIndex].setNotFirstInTagHistory();
             current = current->tagHistory();
             ASSERT(!m_selectorArray[arrayIndex].isLastInSelectorList());

trunk/Source/WebCore/css/parser/CSSSelectorParser.cpp

@@ -321 +321 @@
 }
 
-static bool isLogicalCombinationPseudoClass(CSSSelector::PseudoClassType pseudo)
-{
-    switch (pseudo) {
-    case CSSSelector::PseudoClassIs:
-    case CSSSelector::PseudoClassWhere:
-    case CSSSelector::PseudoClassNot:
-    case CSSSelector::PseudoClassAny:
-    case CSSSelector::PseudoClassMatches:
-    case CSSSelector::PseudoClassHas:
-        return true;
-    default:
-        return false;
-    }
-}
-
 static bool isPseudoClassValidAfterPseudoElement(CSSSelector::PseudoClassType pseudoClass, CSSSelector::PseudoElementType compoundPseudoElement)
 {

trunk/Source/WebCore/style/PseudoClassChangeInvalidation.cpp

@@ -33 +33 @@
 namespace Style {
 
+static Vector<PseudoClassInvalidationKey, 4> makePseudoClassInvalidationKeys(CSSSelector::PseudoClassType pseudoClass, const Element& element)
+{
+    Vector<PseudoClassInvalidationKey, 4> keys;
+
+    if (!element.idForStyleResolution().isEmpty())
+        keys.append(makePseudoClassInvalidationKey(pseudoClass, InvalidationKeyType::Id, element.idForStyleResolution()));
+
+    if (element.hasClass()) {
+        auto classCount = element.classNames().size();
+        for (size_t i = 0; i < classCount; ++i)
+            keys.append(makePseudoClassInvalidationKey(pseudoClass, InvalidationKeyType::Class, element.classNames()[i]));
+    }
+
+    keys.append(makePseudoClassInvalidationKey(pseudoClass, InvalidationKeyType::Tag, element.localName().convertToASCIILowercase()));
+    keys.append(makePseudoClassInvalidationKey(pseudoClass, InvalidationKeyType::Universal));
+
+    return keys;
+};
+
 void PseudoClassChangeInvalidation::computeInvalidation(CSSSelector::PseudoClassType pseudoClass, InvalidationScope invalidationScope)
 {
@@ -39 +58 @@
 
     traverseRuleFeatures(m_element, [&] (const RuleFeatureSet& features, bool mayAffectShadowTree) {
-        if (mayAffectShadowTree && features.pseudoClassRules.contains(pseudoClass))
+        if (mayAffectShadowTree && features.pseudoClassTypes.contains(pseudoClass))
             mayAffectStyleInShadowTree = true;
         if (m_element.shadowRoot() && features.pseudoClassesAffectingHost.contains(pseudoClass))
@@ -53 +72 @@
         m_element.invalidateStyle();
 
+    for (auto& key : makePseudoClassInvalidationKeys(pseudoClass, m_element))
+        collectRuleSets(key, invalidationScope);
+}
+
+void PseudoClassChangeInvalidation::collectRuleSets(const PseudoClassInvalidationKey& key, InvalidationScope invalidationScope)
+{
     auto& ruleSets = m_element.styleResolver().ruleSets();
-    if (auto* invalidationRuleSets = ruleSets.pseudoClassInvalidationRuleSets(pseudoClass)) {
-        for (auto& invalidationRuleSet : *invalidationRuleSets) {
-            // For focus/hover we flip the whole ancestor chain. We only need to do deep invalidation traversal in the change root.
-            auto shouldInvalidate = [&] {
-                switch (invalidationScope) {
-                case InvalidationScope::All:
-                    return true;
-                case InvalidationScope::SelfChildrenAndSiblings:
-                    return invalidationRuleSet.matchElement != MatchElement::Ancestor;
-                case InvalidationScope::Descendants:
-                    return invalidationRuleSet.matchElement == MatchElement::Ancestor;
-                }
-                ASSERT_NOT_REACHED();
+    auto* invalidationRuleSets = ruleSets.pseudoClassInvalidationRuleSets(key);
+    if (!invalidationRuleSets)
+        return;
+
+    for (auto& invalidationRuleSet : *invalidationRuleSets) {
+        // For focus/hover we flip the whole ancestor chain. We only need to do deep invalidation traversal in the change root.
+        auto shouldInvalidate = [&] {
+            bool invalidatesAllDescendants = invalidationRuleSet.matchElement == MatchElement::Ancestor && isUniversalInvalidation(key);
+            switch (invalidationScope) {
+            case InvalidationScope::All:
                 return true;
-            }();
-            if (!shouldInvalidate)
-                continue;
-            Invalidator::addToMatchElementRuleSets(m_matchElementRuleSets, invalidationRuleSet);
-        }
+            case InvalidationScope::SelfChildrenAndSiblings:
+                return !invalidatesAllDescendants;
+            case InvalidationScope::Descendants:
+                return invalidatesAllDescendants;
+            }
+            ASSERT_NOT_REACHED();
+            return true;
+        }();
+        if (!shouldInvalidate)
+            continue;
+
+        Invalidator::addToMatchElementRuleSets(m_matchElementRuleSets, invalidationRuleSet);
     }
 }

trunk/Source/WebCore/style/PseudoClassChangeInvalidation.h

@@ -41 +41 @@
 private:
     void computeInvalidation(CSSSelector::PseudoClassType, Style::InvalidationScope);
+    void collectRuleSets(const PseudoClassInvalidationKey&, InvalidationScope);
     void invalidateStyleWithRuleSets();
 

trunk/Source/WebCore/style/RuleFeature.cpp

@@ -227 +227 @@
                 break;
             }
-        } else if (selector->match() == CSSSelector::PseudoClass)
-            selectorFeatures.pseudoClasses.append(std::make_pair(selector->pseudoClassType(), matchElement));
+        } else if (selector->match() == CSSSelector::PseudoClass) {
+            if (!isLogicalCombinationPseudoClass(selector->pseudoClassType()))
+                selectorFeatures.pseudoClasses.append(std::make_pair(selector, matchElement));
+        }
 
         if (!selectorFeatures.hasSiblingSelector && selector->isSiblingSelector())
@@ -247 +249 @@
     } while (selector);
 }
+
+PseudoClassInvalidationKey makePseudoClassInvalidationKey(CSSSelector::PseudoClassType pseudoClass, InvalidationKeyType keyType, const AtomString& keyString)
+{
+    ASSERT(keyType != InvalidationKeyType::Universal || keyString == starAtom());
+    return {
+        pseudoClass,
+        static_cast<uint8_t>(keyType),
+        keyString
+    };
+};
+
+static PseudoClassInvalidationKey makePseudoClassInvalidationKey(const CSSSelector& selector)
+{
+    ASSERT(selector.match() == CSSSelector::PseudoClass);
+
+    auto pseudoClassType = selector.pseudoClassType();
+
+    AtomString className;
+    AtomString tagName;
+    for (auto* simpleSelector = selector.firstInCompound(); simpleSelector; simpleSelector = simpleSelector->tagHistory()) {
+        if (simpleSelector->match() == CSSSelector::Id)
+            return makePseudoClassInvalidationKey(pseudoClassType, InvalidationKeyType::Id, simpleSelector->value());
+
+        if (simpleSelector->match() == CSSSelector::Class && className.isNull())
+            className = simpleSelector->value();
+
+        if (simpleSelector->match() == CSSSelector::Tag)
+            tagName = simpleSelector->tagLowercaseLocalName();
+
+        if (simpleSelector->relation() != CSSSelector::Subselector)
+            break;
+    }
+    if (!className.isEmpty())
+        return makePseudoClassInvalidationKey(pseudoClassType, InvalidationKeyType::Class, className);
+
+    if (!tagName.isEmpty() && tagName != starAtom())
+        return makePseudoClassInvalidationKey(pseudoClassType, InvalidationKeyType::Tag, tagName);
+
+    return makePseudoClassInvalidationKey(selector.pseudoClassType(), InvalidationKeyType::Universal);
+};
 
 void RuleFeatureSet::collectFeatures(const RuleData& ruleData)
@@ -288 +330 @@
     }
 
-    addToMap(pseudoClassRules, selectorFeatures.pseudoClasses, &pseudoClassesAffectingHost);
+    for (auto& selectorAndMatch : selectorFeatures.pseudoClasses) {
+        auto* selector = selectorAndMatch.first;
+        auto matchElement = selectorAndMatch.second;
+        pseudoClassRules.ensure(makePseudoClassInvalidationKey(*selector), [] {
+            return makeUnique<Vector<RuleFeature>>();
+        }).iterator->value->append({ ruleData, matchElement });
+
+        if (matchElement == MatchElement::Host)
+            pseudoClassesAffectingHost.add(selector->pseudoClassType());
+        pseudoClassTypes.add(selector->pseudoClassType());
+
+        setUsesMatchElement(matchElement);
+    }
 }
 
@@ -320 +374 @@
     addMap(pseudoClassRules, other.pseudoClassRules);
     pseudoClassesAffectingHost.add(other.pseudoClassesAffectingHost.begin(), other.pseudoClassesAffectingHost.end());
+    pseudoClassTypes.add(other.pseudoClassTypes.begin(), other.pseudoClassTypes.end());
 
     for (size_t i = 0; i < usedMatchElements.size(); ++i)
@@ -352 +407 @@
     pseudoClassRules.clear();
     pseudoClassesAffectingHost.clear();
+    pseudoClassTypes.clear();
     usesFirstLineRules = false;
     usesFirstLetterRules = false;

trunk/Source/WebCore/style/RuleFeature.h

@@ -75 +75 @@
 };
 
+using PseudoClassInvalidationKey = std::tuple<unsigned, uint8_t, AtomString>;
+
 using RuleFeatureVector = Vector<RuleFeature>;
 
@@ -99 +101 @@
     HashMap<AtomString, std::unique_ptr<RuleFeatureVector>> classRules;
     HashMap<AtomString, std::unique_ptr<Vector<RuleFeatureWithInvalidationSelector>>> attributeRules;
-    HashMap<CSSSelector::PseudoClassType, std::unique_ptr<RuleFeatureVector>, IntHash<CSSSelector::PseudoClassType>, WTF::StrongEnumHashTraits<CSSSelector::PseudoClassType>> pseudoClassRules;
+    HashMap<PseudoClassInvalidationKey, std::unique_ptr<RuleFeatureVector>> pseudoClassRules;
     HashSet<AtomString> classesAffectingHost;
     HashSet<AtomString> attributesAffectingHost;
     HashSet<CSSSelector::PseudoClassType, IntHash<CSSSelector::PseudoClassType>, WTF::StrongEnumHashTraits<CSSSelector::PseudoClassType>> pseudoClassesAffectingHost;
+    HashSet<CSSSelector::PseudoClassType, IntHash<CSSSelector::PseudoClassType>, WTF::StrongEnumHashTraits<CSSSelector::PseudoClassType>> pseudoClassTypes;
 
     std::array<bool, matchElementCount> usedMatchElements { };
@@ -117 +120 @@
         Vector<std::pair<AtomString, MatchElement>, 32> classes;
         Vector<std::pair<const CSSSelector*, MatchElement>, 32> attributes;
-        Vector<std::pair<CSSSelector::PseudoClassType, MatchElement>, 32> pseudoClasses;
+        Vector<std::pair<const CSSSelector*, MatchElement>, 32> pseudoClasses;
     };
     void recursivelyCollectFeaturesFromSelector(SelectorFeatures&, const CSSSelector&, MatchElement = MatchElement::Subject);
@@ -125 +128 @@
 MatchElement computeHasPseudoClassMatchElement(const CSSSelector&);
 
+enum class InvalidationKeyType : uint8_t { Universal = 1, Class, Id, Tag };
+PseudoClassInvalidationKey makePseudoClassInvalidationKey(CSSSelector::PseudoClassType, InvalidationKeyType, const AtomString& = starAtom());
+
+inline bool isUniversalInvalidation(const PseudoClassInvalidationKey& key)
+{
+    return static_cast<InvalidationKeyType>(std::get<1>(key)) == InvalidationKeyType::Universal;
+}
+
 } // namespace Style
 } // namespace WebCore

trunk/Source/WebCore/style/StyleScopeRuleSets.cpp

@@ -296 +296 @@
 }
 
-const Vector<InvalidationRuleSet>* ScopeRuleSets::pseudoClassInvalidationRuleSets(CSSSelector::PseudoClassType pseudoClass) const
-{
-    return ensureInvalidationRuleSets(pseudoClass, m_pseudoClassInvalidationRuleSets, m_features.pseudoClassRules);
+const Vector<InvalidationRuleSet>* ScopeRuleSets::pseudoClassInvalidationRuleSets(const PseudoClassInvalidationKey& pseudoClassKey) const
+{
+    return ensureInvalidationRuleSets(pseudoClassKey, m_pseudoClassInvalidationRuleSets, m_features.pseudoClassRules);
 }
 

trunk/Source/WebCore/style/StyleScopeRuleSets.h

@@ -68 +68 @@
     const Vector<InvalidationRuleSet>* classInvalidationRuleSets(const AtomString&) const;
     const Vector<InvalidationRuleSet>* attributeInvalidationRuleSets(const AtomString&) const;
-    const Vector<InvalidationRuleSet>* pseudoClassInvalidationRuleSets(CSSSelector::PseudoClassType) const;
+    const Vector<InvalidationRuleSet>* pseudoClassInvalidationRuleSets(const PseudoClassInvalidationKey&) const;
 
     const Vector<InvalidationRuleSet>* invalidationRuleSetsForChildChange(const Element&);
@@ -107 +107 @@
     mutable HashMap<AtomString, std::unique_ptr<Vector<InvalidationRuleSet>>> m_classInvalidationRuleSets;
     mutable HashMap<AtomString, std::unique_ptr<Vector<InvalidationRuleSet>>> m_attributeInvalidationRuleSets;
-    mutable HashMap<CSSSelector::PseudoClassType, std::unique_ptr<Vector<InvalidationRuleSet>>, IntHash<CSSSelector::PseudoClassType>, WTF::StrongEnumHashTraits<CSSSelector::PseudoClassType>> m_pseudoClassInvalidationRuleSets;
+    mutable HashMap<PseudoClassInvalidationKey, std::unique_ptr<Vector<InvalidationRuleSet>>> m_pseudoClassInvalidationRuleSets;
 
     mutable std::optional<bool> m_cachedHasComplexSelectorsForStyleAttribute;