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

Changeset 287772 in webkit


Ignore:
Timestamp:
Jan 7, 2022, 11:38:44 AM (5 years ago)
Author:
Antti Koivisto
Message:

Make separate invalidation rulesets for negated selectors (inside :not())
​https://bugs.webkit.org/show_bug.cgi?id=234959

Reviewed by Darin Adler.

Use this information to reduce traversal on class changes. Other mutations will follow.

  • style/ClassChangeInvalidation.cpp:

(WebCore::Style::collectClasses):
(WebCore::Style::computeClassChanges):
(WebCore::Style::ClassChangeInvalidation::computeInvalidation):

Adding a class can only make a regular selector (not inside :not()) start matching.
Adding a class can only make a negated selector (inside :not()) stop matching.
We only need to invalidate for the first case after the mutation has happened and for the second
case before it happens.

These are reversed when removing a class.

(WebCore::Style::ClassChangeInvalidation::invalidateBeforeChange):
(WebCore::Style::ClassChangeInvalidation::invalidateAfterChange):
(WebCore::Style::computeClassChange): Deleted.
(WebCore::Style::ClassChangeInvalidation::invalidateStyleWithRuleSets): Deleted.

  • style/ClassChangeInvalidation.h:

(WebCore::Style::ClassChangeInvalidation::ClassChangeInvalidation):
(WebCore::Style::ClassChangeInvalidation::~ClassChangeInvalidation):

  • style/RuleFeature.cpp:

(WebCore::Style::RuleFeature::RuleFeature):
(WebCore::Style::RuleFeatureWithInvalidationSelector::RuleFeatureWithInvalidationSelector):
(WebCore::Style::RuleFeatureSet::recursivelyCollectFeaturesFromSelector):

Compute the negation state. :not(foo) is negated, :not(:not(foo)) isn't.

(WebCore::Style::RuleFeatureSet::collectFeatures):

  • style/RuleFeature.h:

(WebCore::Style::RuleFeatureWithInvalidationSelector::RuleFeatureWithInvalidationSelector): Deleted.

  • style/StyleScopeRuleSets.cpp:

(WebCore::Style::ensureInvalidationRuleSets):

Make separate ruleset.

  • style/StyleScopeRuleSets.h:
Location:
trunk/Source/WebCore
Files:
7 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/WebCore/ChangeLog

    r287771 r287772  
     12022-01-07  Antti Koivisto  <antti@apple.com>
     2
     3        Make separate invalidation rulesets for negated selectors (inside :not())
     4        https://bugs.webkit.org/show_bug.cgi?id=234959
     5
     6        Reviewed by Darin Adler.
     7
     8        Use this information to reduce traversal on class changes. Other mutations will follow.
     9
     10        * style/ClassChangeInvalidation.cpp:
     11        (WebCore::Style::collectClasses):
     12        (WebCore::Style::computeClassChanges):
     13        (WebCore::Style::ClassChangeInvalidation::computeInvalidation):
     14
     15        Adding a class can only make a regular selector (not inside :not()) start matching.
     16        Adding a class can only make a negated selector (inside :not()) stop matching.
     17        We only need to invalidate for the first case after the mutation has happened and for the second
     18        case before it happens.
     19
     20        These are reversed when removing a class.
     21
     22        (WebCore::Style::ClassChangeInvalidation::invalidateBeforeChange):
     23        (WebCore::Style::ClassChangeInvalidation::invalidateAfterChange):
     24        (WebCore::Style::computeClassChange): Deleted.
     25        (WebCore::Style::ClassChangeInvalidation::invalidateStyleWithRuleSets): Deleted.
     26        * style/ClassChangeInvalidation.h:
     27        (WebCore::Style::ClassChangeInvalidation::ClassChangeInvalidation):
     28        (WebCore::Style::ClassChangeInvalidation::~ClassChangeInvalidation):
     29        * style/RuleFeature.cpp:
     30        (WebCore::Style::RuleFeature::RuleFeature):
     31        (WebCore::Style::RuleFeatureWithInvalidationSelector::RuleFeatureWithInvalidationSelector):
     32        (WebCore::Style::RuleFeatureSet::recursivelyCollectFeaturesFromSelector):
     33
     34        Compute the negation state. :not(foo) is negated, :not(:not(foo)) isn't.
     35
     36        (WebCore::Style::RuleFeatureSet::collectFeatures):
     37        * style/RuleFeature.h:
     38        (WebCore::Style::RuleFeatureWithInvalidationSelector::RuleFeatureWithInvalidationSelector): Deleted.
     39        * style/StyleScopeRuleSets.cpp:
     40        (WebCore::Style::ensureInvalidationRuleSets):
     41
     42        Make separate ruleset.
     43
     44        * style/StyleScopeRuleSets.h:
     45
    1462022-01-07  Gabriel Nava Marino  <gnavamarino@apple.com>
    247

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

    r253690 r287772  
    3535namespace Style {
    3636
    37 using ClassChangeVector = Vector<AtomStringImpl*, 4>;
     37enum class ClassChangeType : bool { Add, Remove };
    3838
    39 static ClassChangeVector collectClasses(const SpaceSplitString& classes)
     39struct ClassChange {
     40    AtomStringImpl* className { };
     41    ClassChangeType type;
     42};
     43
     44using ClassChangeVector = Vector<ClassChange, 4>;
     45
     46static ClassChangeVector collectClasses(const SpaceSplitString& classes, ClassChangeType changeType)
    4047{
    4148    ClassChangeVector result;
    4249    result.reserveCapacity(classes.size());
    4350    for (unsigned i = 0; i < classes.size(); ++i)
    44         result.uncheckedAppend(classes[i].impl());
     51        result.uncheckedAppend({ classes[i].impl(), changeType });
    4552    return result;
    4653}
    4754
    48 static ClassChangeVector computeClassChange(const SpaceSplitString& oldClasses, const SpaceSplitString& newClasses)
     55static ClassChangeVector computeClassChanges(const SpaceSplitString& oldClasses, const SpaceSplitString& newClasses)
    4956{
    5057    unsigned oldSize = oldClasses.size();
    … …  
    5259
    5360    if (!oldSize)
    54         return collectClasses(newClasses);
     61        return collectClasses(newClasses, ClassChangeType::Add);
    5562    if (!newSize)
    56         return collectClasses(oldClasses);
     63        return collectClasses(oldClasses, ClassChangeType::Remove);
    5764
    5865    ClassChangeVector changedClasses;
    … …  
    7178        if (foundFromBoth)
    7279            continue;
    73         changedClasses.append(newClasses[i].impl());
     80        changedClasses.append({ newClasses[i].impl(), ClassChangeType::Add });
    7481    }
    7582    for (unsigned i = 0; i < oldSize; ++i) {
    … …  
    7784        if (remainingClassBits.quickGet(i))
    7885            continue;
    79         changedClasses.append(oldClasses[i].impl());
     86        changedClasses.append({ oldClasses[i].impl(), ClassChangeType::Remove });
    8087    }
    8188
    … …  
    8592void ClassChangeInvalidation::computeInvalidation(const SpaceSplitString& oldClasses, const SpaceSplitString& newClasses)
    8693{
    87     auto changedClasses = computeClassChange(oldClasses, newClasses);
     94    auto classChanges = computeClassChanges(oldClasses, newClasses);
    8895
    8996    bool shouldInvalidateCurrent = false;
    … …  
    9198
    9299    traverseRuleFeatures(m_element, [&] (const RuleFeatureSet& features, bool mayAffectShadowTree) {
    93         for (auto* changedClass : changedClasses) {
    94             if (mayAffectShadowTree && features.classRules.contains(changedClass))
     100        for (auto& classChange : classChanges) {
     101            if (mayAffectShadowTree && features.classRules.contains(classChange.className))
    95102                mayAffectStyleInShadowTree = true;
    96             if (features.classesAffectingHost.contains(changedClass))
     103            if (features.classesAffectingHost.contains(classChange.className))
    97104                shouldInvalidateCurrent = true;
    98105        }
    … …  
    109116    auto& ruleSets = m_element.styleResolver().ruleSets();
    110117
    111     for (auto* changedClass : changedClasses) {
    112         if (auto* invalidationRuleSets = ruleSets.classInvalidationRuleSets(changedClass)) {
    113             for (auto& invalidationRuleSet : *invalidationRuleSets)
    114                 Invalidator::addToMatchElementRuleSets(m_matchElementRuleSets, invalidationRuleSet);
     118    auto invalidateBeforeChange = [](ClassChangeType type, IsNegation isNegation) {
     119        if (type == ClassChangeType::Remove)
     120            return isNegation == IsNegation::No;
     121        return isNegation == IsNegation::Yes;
     122    };
     123
     124    for (auto& classChange : classChanges) {
     125        if (auto* invalidationRuleSets = ruleSets.classInvalidationRuleSets(classChange.className)) {
     126            for (auto& invalidationRuleSet : *invalidationRuleSets) {
     127                if (invalidateBeforeChange(classChange.type, invalidationRuleSet.isNegation))
     128                    Invalidator::addToMatchElementRuleSets(m_beforeChangeRuleSets, invalidationRuleSet);
     129                else
     130                    Invalidator::addToMatchElementRuleSets(m_afterChangeRuleSets, invalidationRuleSet);
     131            }
    115132        }
    116133    }
    117134}
    118135
    119 void ClassChangeInvalidation::invalidateStyleWithRuleSets()
     136void ClassChangeInvalidation::invalidateBeforeChange()
    120137{
    121     Invalidator::invalidateWithMatchElementRuleSets(m_element, m_matchElementRuleSets);
     138    Invalidator::invalidateWithMatchElementRuleSets(m_element, m_beforeChangeRuleSets);
     139}
     140
     141void ClassChangeInvalidation::invalidateAfterChange()
     142{
     143    Invalidator::invalidateWithMatchElementRuleSets(m_element, m_afterChangeRuleSets);
    122144}
    123145

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

    r253690 r287772  
    4343private:
    4444    void computeInvalidation(const SpaceSplitString& oldClasses, const SpaceSplitString& newClasses);
    45     void invalidateStyleWithRuleSets();
     45    void invalidateBeforeChange();
     46    void invalidateAfterChange();
    4647
    4748    const bool m_isEnabled;
    4849    Element& m_element;
    4950
    50     Invalidator::MatchElementRuleSets m_matchElementRuleSets;
     51    Invalidator::MatchElementRuleSets m_beforeChangeRuleSets;
     52    Invalidator::MatchElementRuleSets m_afterChangeRuleSets;
    5153};
    5254
    … …  
    5961        return;
    6062    computeInvalidation(oldClasses, newClasses);
    61     invalidateStyleWithRuleSets();
     63    invalidateBeforeChange();
    6264}
    6365
    … …  
    6668    if (!m_isEnabled)
    6769        return;
    68     invalidateStyleWithRuleSets();
     70    invalidateAfterChange();
    6971}
    7072

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

    r287479 r287772  
    8585
    8686
    87 RuleFeature::RuleFeature(const RuleData& ruleData, MatchElement matchElement)
     87RuleFeature::RuleFeature(const RuleData& ruleData, MatchElement matchElement, IsNegation isNegation)
    8888    : RuleAndSelector(ruleData)
    8989    , matchElement(matchElement)
     90    , isNegation(isNegation)
     91{
     92}
     93
     94RuleFeatureWithInvalidationSelector::RuleFeatureWithInvalidationSelector(const RuleData& data, MatchElement matchElement, IsNegation isNegation, const CSSSelector* invalidationSelector)
     95    : RuleFeature(data, matchElement, isNegation)
     96    , invalidationSelector(invalidationSelector)
    9097{
    9198}
    … …  
    201208};
    202209
    203 void RuleFeatureSet::recursivelyCollectFeaturesFromSelector(SelectorFeatures& selectorFeatures, const CSSSelector& firstSelector, MatchElement matchElement)
     210void RuleFeatureSet::recursivelyCollectFeaturesFromSelector(SelectorFeatures& selectorFeatures, const CSSSelector& firstSelector, MatchElement matchElement, IsNegation isNegation)
    204211{
    205212    const CSSSelector* selector = &firstSelector;
    … …  
    210217                idsMatchingAncestorsInRules.add(selector->value());
    211218            else if (isHasPseudoClassMatchElement(matchElement))
    212                 selectorFeatures.ids.append(std::make_pair(selector->value(), matchElement));
     219                selectorFeatures.ids.append({ selector->value(), matchElement, isNegation });
    213220        } else if (selector->match() == CSSSelector::Class)
    214             selectorFeatures.classes.append(std::make_pair(selector->value(), matchElement));
     221            selectorFeatures.classes.append({ selector->value(), matchElement, isNegation });
    215222        else if (selector->match() == CSSSelector::Tag) {
    216223            if (isHasPseudoClassMatchElement(matchElement))
    217                 selectorFeatures.tags.append(std::make_pair(selector->tagLowercaseLocalName(), matchElement));
     224                selectorFeatures.tags.append({ selector->tagLowercaseLocalName(), matchElement, isNegation });
    218225        } else if (selector->isAttributeSelector()) {
    219226            auto& canonicalLocalName = selector->attributeCanonicalLocalName();
    … …  
    221228            attributeCanonicalLocalNamesInRules.add(canonicalLocalName);
    222229            attributeLocalNamesInRules.add(localName);
    223             selectorFeatures.attributes.append(std::make_pair(selector, matchElement));
     230            selectorFeatures.attributes.append({ selector, matchElement, isNegation });
    224231        } else if (selector->match() == CSSSelector::PseudoElement) {
    225232            switch (selector->pseudoElementType()) {
    … …  
    235242        } else if (selector->match() == CSSSelector::PseudoClass) {
    236243            if (!isLogicalCombinationPseudoClass(selector->pseudoClassType()))
    237                 selectorFeatures.pseudoClasses.append(std::make_pair(selector, matchElement));
     244                selectorFeatures.pseudoClasses.append({ selector, matchElement, isNegation });
    238245        }
    239246
    … …  
    242249
    243250        if (const CSSSelectorList* selectorList = selector->selectorList()) {
     251            auto subSelectorIsNegation = isNegation;
     252            if (selector->match() == CSSSelector::PseudoClass && selector->pseudoClassType() == CSSSelector::PseudoClassNot)
     253                subSelectorIsNegation = isNegation == IsNegation::No ? IsNegation::Yes : IsNegation::No;
     254
    244255            for (const CSSSelector* subSelector = selectorList->first(); subSelector; subSelector = CSSSelectorList::next(subSelector)) {
    245256                auto subSelectorMatchElement = computeSubSelectorMatchElement(matchElement, *selector, *subSelector);
    246257                if (!selectorFeatures.hasSiblingSelector && selector->isSiblingSelector())
    247258                    selectorFeatures.hasSiblingSelector = true;
    248                 recursivelyCollectFeaturesFromSelector(selectorFeatures, *subSelector, subSelectorMatchElement);
     259                recursivelyCollectFeaturesFromSelector(selectorFeatures, *subSelector, subSelectorMatchElement, subSelectorIsNegation);
    249260            }
    250261        }
    … …  
    307318    auto addToMap = [&](auto& map, auto& entries, auto hostAffectingNames) {
    308319        for (auto& entry : entries) {
    309             auto& [name, matchElement] = entry;
     320            auto& [name, matchElement, isNegation] = entry;
    310321            map.ensure(name, [] {
    311322                return makeUnique<RuleFeatureVector>();
    312             }).iterator->value->append({ ruleData, matchElement });
     323            }).iterator->value->append({ ruleData, matchElement, isNegation });
    313324
    314325            setUsesMatchElement(matchElement);
    … …  
    325336    addToMap(classRules, selectorFeatures.classes, &classesAffectingHost);
    326337
    327     for (auto& selectorAndMatch : selectorFeatures.attributes) {
    328         auto* selector = selectorAndMatch.first;
    329         auto matchElement = selectorAndMatch.second;
     338    for (auto& entry : selectorFeatures.attributes) {
     339        auto [selector, matchElement, isNegation] = entry;
    330340        attributeRules.ensure(selector->attribute().localName().convertToASCIILowercase(), [] {
    331341            return makeUnique<Vector<RuleFeatureWithInvalidationSelector>>();
    332         }).iterator->value->append({ ruleData, matchElement, selector });
     342        }).iterator->value->append({ ruleData, matchElement, isNegation, selector });
    333343        if (matchElement == MatchElement::Host)
    334344            attributesAffectingHost.add(selector->attribute().localName().convertToASCIILowercase());
    … …  
    336346    }
    337347
    338     for (auto& selectorAndMatch : selectorFeatures.pseudoClasses) {
    339         auto* selector = selectorAndMatch.first;
    340         auto matchElement = selectorAndMatch.second;
     348    for (auto& entry : selectorFeatures.pseudoClasses) {
     349        auto [selector, matchElement, isNegation] = entry;
    341350        pseudoClassRules.ensure(makePseudoClassInvalidationKey(*selector), [] {
    342351            return makeUnique<Vector<RuleFeature>>();
    343         }).iterator->value->append({ ruleData, matchElement });
     352        }).iterator->value->append({ ruleData, matchElement, isNegation });
    344353
    345354        if (matchElement == MatchElement::Host)

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

    r287479 r287772  
    5656constexpr unsigned matchElementCount = static_cast<unsigned>(MatchElement::Host) + 1;
    5757
     58enum class IsNegation : bool { No, Yes };
     59
    5860// For MSVC.
    5961#pragma pack(push, 4)
    … …  
    6769
    6870struct RuleFeature : public RuleAndSelector {
    69     RuleFeature(const RuleData&, MatchElement);
     71    RuleFeature(const RuleData&, MatchElement, IsNegation);
    7072
    7173    MatchElement matchElement;
     74    IsNegation isNegation; // Whether the selector is in a (non-paired) :not() context.
    7275};
    7376static_assert(sizeof(RuleFeature) <= 16, "RuleFeature is a frquently alocated object. Keep it small.");
    7477
    7578struct RuleFeatureWithInvalidationSelector : public RuleFeature {
    76     RuleFeatureWithInvalidationSelector(const RuleData& data, MatchElement matchElement, const CSSSelector* invalidationSelector = nullptr)
    77         : RuleFeature(data, matchElement)
    78         , invalidationSelector(invalidationSelector)
    79     { }
     79    RuleFeatureWithInvalidationSelector(const RuleData&, MatchElement, IsNegation, const CSSSelector* invalidationSelector);
    8080
    8181    const CSSSelector* invalidationSelector { nullptr };
    … …  
    125125        bool hasSiblingSelector { false };
    126126
    127         Vector<std::pair<AtomString, MatchElement>, 32> tags;
    128         Vector<std::pair<AtomString, MatchElement>, 32> ids;
    129         Vector<std::pair<AtomString, MatchElement>, 32> classes;
    130         Vector<std::pair<const CSSSelector*, MatchElement>, 32> attributes;
    131         Vector<std::pair<const CSSSelector*, MatchElement>, 32> pseudoClasses;
     127        Vector<std::tuple<AtomString, MatchElement, IsNegation>, 32> tags;
     128        Vector<std::tuple<AtomString, MatchElement, IsNegation>, 32> ids;
     129        Vector<std::tuple<AtomString, MatchElement, IsNegation>, 32> classes;
     130        Vector<std::tuple<const CSSSelector*, MatchElement, IsNegation>, 32> attributes;
     131        Vector<std::tuple<const CSSSelector*, MatchElement, IsNegation>, 32> pseudoClasses;
    132132    };
    133     void recursivelyCollectFeaturesFromSelector(SelectorFeatures&, const CSSSelector&, MatchElement = MatchElement::Subject);
     133    void recursivelyCollectFeaturesFromSelector(SelectorFeatures&, const CSSSelector&, MatchElement = MatchElement::Subject, IsNegation =  IsNegation::No);
    134134};
    135135

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

    r287479 r287772  
    241241            return nullptr;
    242242
    243         std::array<RefPtr<RuleSet>, matchElementCount> matchElementArray;
    244         std::array<Vector<const CSSSelector*>, matchElementCount> invalidationSelectorArray;
     243        HashMap<std::tuple<uint8_t, bool, bool>, InvalidationRuleSet> invalidationRuleSetMap;
     244
    245245        for (auto& feature : *features) {
    246             auto arrayIndex = static_cast<unsigned>(feature.matchElement);
    247             RELEASE_ASSERT(arrayIndex < matchElementArray.size());
    248 
    249             auto& ruleSet = matchElementArray[arrayIndex];
    250             if (!ruleSet)
    251                 ruleSet = RuleSet::create();
    252             ruleSet->addRule(*feature.styleRule, feature.selectorIndex, feature.selectorListIndex);
     246            auto key = std::tuple { static_cast<uint8_t>(feature.matchElement), static_cast<bool>(feature.isNegation), true };
     247
     248            auto& invalidationRuleSet = invalidationRuleSetMap.ensure(key, [&] {
     249                return InvalidationRuleSet {
     250                    RuleSet::create(),
     251                    { },
     252                    feature.matchElement,
     253                    feature.isNegation,
     254                };
     255            }).iterator->value;
     256
     257            invalidationRuleSet.ruleSet->addRule(*feature.styleRule, feature.selectorIndex, feature.selectorListIndex);
     258
    253259            if constexpr (std::is_same<typename RuleFeatureVectorType::ValueType, RuleFeatureWithInvalidationSelector>::value) {
    254260                if (feature.invalidationSelector)
    255                     invalidationSelectorArray[arrayIndex].append(feature.invalidationSelector);
     261                    invalidationRuleSet.invalidationSelectors.append(feature.invalidationSelector);
    256262            }
    257263        }
    258264
    259         unsigned ruleSetCount = 0;
    260         for (const auto& item : matchElementArray) {
    261             if (item)
    262                 ++ruleSetCount;
    263         }
    264 
    265265        auto invalidationRuleSets = makeUnique<Vector<InvalidationRuleSet>>();
    266         invalidationRuleSets->reserveInitialCapacity(ruleSetCount);
    267 
    268         for (unsigned i = 0; i < matchElementArray.size(); ++i) {
    269             if (matchElementArray[i]) {
    270                 matchElementArray[i]->shrinkToFit();
    271                 invalidationRuleSets->uncheckedAppend({ static_cast<MatchElement>(i), matchElementArray[i].releaseNonNull(), WTFMove(invalidationSelectorArray[i]) });
    272             }
    273         }
     266        invalidationRuleSets->reserveInitialCapacity(invalidationRuleSetMap.size());
     267
     268        for (auto& invalidationRuleSet : invalidationRuleSetMap.values())
     269            invalidationRuleSets->uncheckedAppend(WTFMove(invalidationRuleSet));
     270
    274271        return invalidationRuleSets;
    275272    }).iterator->value.get();

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

    r286598 r287772  
    4444
    4545struct InvalidationRuleSet {
     46    RefPtr<RuleSet> ruleSet;
     47    Vector<const CSSSelector*> invalidationSelectors;
    4648    MatchElement matchElement;
    47     Ref<RuleSet> ruleSet;
    48     Vector<const CSSSelector*> invalidationSelectors;
    49 
    50     WTF_MAKE_FAST_ALLOCATED;
     49    IsNegation isNegation;
    5150};
    5251
Note: See TracChangeset for help on using the changeset viewer.