Changeset 227787 in webkit


Ignore:
Timestamp:
Jan 30, 2018 8:13:15 AM (6 years ago)
Author:
Antti Koivisto
Message:

Avoid traversing too much when doing class change invalidation
​https://bugs.webkit.org/show_bug.cgi?id=181604

Reviewed by Zalan Bujtas.

We are now collecting information about which part of the tree a change in class can potentially affect.
Use the information to traverse only the required elements in Style::Invalidator.

The same mechanism can be later used for attribute and id change invalidation.

  • css/DocumentRuleSets.cpp:

(WebCore::DocumentRuleSets::collectFeatures const):
(WebCore::DocumentRuleSets::classInvalidationRuleSets const):
(WebCore::DocumentRuleSets::subjectClassRules const): Deleted.
(WebCore::DocumentRuleSets::ancestorClassRules const): Deleted.

Remove separate subject and ancestor invalidation RuleSets. Instead collect all invalidation rulesets
to a vector along with their MatchElements.

  • css/DocumentRuleSets.h:
  • css/RuleFeature.cpp:

(WebCore::RuleFeatureSet::computeNextMatchElement):
(WebCore::RuleFeatureSet::computeSubSelectorMatchElement):
(WebCore::RuleFeatureSet::collectFeatures):

Similarly collect all class invalidation RuleFeatures to a general HashMap along with the MatchElement.

(WebCore::RuleFeatureSet::add):
(WebCore::RuleFeatureSet::clear):
(WebCore::RuleFeatureSet::shrinkToFit):

  • css/RuleFeature.h:

(WebCore::RuleFeature::RuleFeature):

  • style/ClassChangeInvalidation.cpp:

(WebCore::Style::ClassChangeInvalidation::computeInvalidation):

Find out InvalidationRuleSets to use.

(WebCore::Style::ClassChangeInvalidation::invalidateStyleWithRuleSets):

Pass them to Style::Invalidator.

  • style/ClassChangeInvalidation.h:
  • style/StyleInvalidator.cpp:

(WebCore::Style::Invalidator::invalidateStyleForTree):
(WebCore::Style::Invalidator::invalidateStyleForDescendants):
(WebCore::Style::Invalidator::invalidateStyleWithMatchElement):

Traverse only the part of the tree needed by the given MatchElement.

  • style/StyleInvalidator.h:
  • style/StyleSharingResolver.cpp:

(WebCore::Style::SharingResolver::classNamesAffectedByRules const):

Location:
trunk/Source/WebCore
Files:
10 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/WebCore/ChangeLog

    r227786 r227787  
     12018-01-30  Antti Koivisto  <antti@apple.com>
     2
     3        Avoid traversing too much when doing class change invalidation
     4        https://bugs.webkit.org/show_bug.cgi?id=181604
     5
     6        Reviewed by Zalan Bujtas.
     7
     8        We are now collecting information about which part of the tree a change in class can potentially affect.
     9        Use the information to traverse only the required elements in Style::Invalidator.
     10
     11        The same mechanism can be later used for attribute and id change invalidation.
     12
     13        * css/DocumentRuleSets.cpp:
     14        (WebCore::DocumentRuleSets::collectFeatures const):
     15        (WebCore::DocumentRuleSets::classInvalidationRuleSets const):
     16        (WebCore::DocumentRuleSets::subjectClassRules const): Deleted.
     17        (WebCore::DocumentRuleSets::ancestorClassRules const): Deleted.
     18
     19            Remove separate subject and ancestor invalidation RuleSets. Instead collect all invalidation rulesets
     20            to a vector along with their MatchElements.
     21
     22        * css/DocumentRuleSets.h:
     23        * css/RuleFeature.cpp:
     24        (WebCore::RuleFeatureSet::computeNextMatchElement):
     25        (WebCore::RuleFeatureSet::computeSubSelectorMatchElement):
     26        (WebCore::RuleFeatureSet::collectFeatures):
     27
     28            Similarly collect all class invalidation RuleFeatures to a general HashMap along with the MatchElement.
     29
     30        (WebCore::RuleFeatureSet::add):
     31        (WebCore::RuleFeatureSet::clear):
     32        (WebCore::RuleFeatureSet::shrinkToFit):
     33        * css/RuleFeature.h:
     34        (WebCore::RuleFeature::RuleFeature):
     35        * style/ClassChangeInvalidation.cpp:
     36        (WebCore::Style::ClassChangeInvalidation::computeInvalidation):
     37
     38            Find out InvalidationRuleSets to use.
     39
     40        (WebCore::Style::ClassChangeInvalidation::invalidateStyleWithRuleSets):
     41
     42            Pass them to Style::Invalidator.
     43
     44        * style/ClassChangeInvalidation.h:
     45        * style/StyleInvalidator.cpp:
     46        (WebCore::Style::Invalidator::invalidateStyleForTree):
     47        (WebCore::Style::Invalidator::invalidateStyleForDescendants):
     48        (WebCore::Style::Invalidator::invalidateStyleWithMatchElement):
     49
     50            Traverse only the part of the tree needed by the given MatchElement.
     51
     52        * style/StyleInvalidator.h:
     53        * style/StyleSharingResolver.cpp:
     54        (WebCore::Style::SharingResolver::classNamesAffectedByRules const):
     55
    1562018-01-30  Javier Fernandez  <jfernandez@igalia.com>
    257

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

    r226703 r227787  
    168168    m_uncommonAttributeRuleSet = makeRuleSet(m_features.uncommonAttributeRules);
    169169
    170     m_subjectClassRuleSets.clear();
    171     m_ancestorClassRuleSets.clear();
     170    m_classInvalidationRuleSets.clear();
    172171    m_ancestorAttributeRuleSetsForHTML.clear();
    173172
    … …  
    175174}
    176175
    177 RuleSet* DocumentRuleSets::subjectClassRules(const AtomicString& className) const
    178 {
    179     return m_subjectClassRuleSets.ensure(className, [&] {
    180         auto* rules = m_features.subjectClassRules.get(className);
    181         return rules ? makeRuleSet(*rules) : nullptr;
    182     }).iterator->value.get();
    183 }
    184 
    185 RuleSet* DocumentRuleSets::ancestorClassRules(const AtomicString& className) const
    186 {
    187     return m_ancestorClassRuleSets.ensure(className, [&] {
    188         auto* rules = m_features.ancestorClassRules.get(className);
    189         return rules ? makeRuleSet(*rules) : nullptr;
     176const Vector<InvalidationRuleSet>* DocumentRuleSets::classInvalidationRuleSets(const AtomicString& className) const
     177{
     178    return m_classInvalidationRuleSets.ensure(className, [&] () -> std::unique_ptr<Vector<InvalidationRuleSet>> {
     179        auto* features = m_features.classRules.get(className);
     180        if (!features)
     181            return nullptr;
     182        std::array<std::unique_ptr<RuleSet>, matchElementCount> matchElementArray;
     183        for (auto& feature : *features) {
     184            auto& ruleSet = matchElementArray[static_cast<unsigned>(*feature.matchElement)];
     185            if (!ruleSet)
     186                ruleSet = std::make_unique<RuleSet>();
     187            ruleSet->addRule(feature.rule, feature.selectorIndex);
     188        }
     189        auto invalidationRuleSets = std::make_unique<Vector<InvalidationRuleSet>>();
     190        for (unsigned i = 0; i < matchElementArray.size(); ++i) {
     191            if (matchElementArray[i])
     192                invalidationRuleSets->append({ static_cast<MatchElement>(i), WTFMove(matchElementArray[i]) });
     193        }
     194        return invalidationRuleSets;
    190195    }).iterator->value.get();
    191196}

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

    r226703 r227787  
    3939class MediaQueryEvaluator;
    4040
     41struct InvalidationRuleSet {
     42    MatchElement matchElement;
     43    std::unique_ptr<RuleSet> ruleSet;
     44
     45    WTF_MAKE_FAST_ALLOCATED;
     46};
     47
    4148class DocumentRuleSets {
    4249public:
    … …  
    5158    RuleSet* sibling() const { return m_siblingRuleSet.get(); }
    5259    RuleSet* uncommonAttribute() const { return m_uncommonAttributeRuleSet.get(); }
    53     RuleSet* subjectClassRules(const AtomicString& className) const;
    54     RuleSet* ancestorClassRules(const AtomicString& className) const;
     60
     61    const Vector<InvalidationRuleSet>* classInvalidationRuleSets(const AtomicString& className) const;
    5562
    5663    struct AttributeRules {
    … …  
    9299    mutable std::unique_ptr<RuleSet> m_siblingRuleSet;
    93100    mutable std::unique_ptr<RuleSet> m_uncommonAttributeRuleSet;
    94     mutable HashMap<AtomicString, std::unique_ptr<RuleSet>> m_subjectClassRuleSets;
    95     mutable HashMap<AtomicString, std::unique_ptr<RuleSet>> m_ancestorClassRuleSets;
     101    mutable HashMap<AtomicString, std::unique_ptr<Vector<InvalidationRuleSet>>> m_classInvalidationRuleSets;
    96102    mutable HashMap<AtomicString, std::unique_ptr<AttributeRules>> m_ancestorAttributeRuleSetsForHTML;
    97103};

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

    r226718 r227787  
    3636namespace WebCore {
    3737
    38 RuleFeatureSet::MatchElement RuleFeatureSet::computeNextMatchElement(MatchElement matchElement, CSSSelector::RelationType relation)
     38MatchElement RuleFeatureSet::computeNextMatchElement(MatchElement matchElement, CSSSelector::RelationType relation)
    3939{
    4040    if (matchElement == MatchElement::Subject || matchElement == MatchElement::IndirectSibling || matchElement == MatchElement::DirectSibling) {
    … …  
    7070};
    7171
    72 RuleFeatureSet::MatchElement RuleFeatureSet::computeSubSelectorMatchElement(MatchElement matchElement, const CSSSelector& selector)
     72MatchElement RuleFeatureSet::computeSubSelectorMatchElement(MatchElement matchElement, const CSSSelector& selector)
    7373{
    7474    ASSERT(selector.selectorList());
    … …  
    158158    if (ruleData.containsUncommonAttributeSelector())
    159159        uncommonAttributeRules.append(RuleFeature(ruleData.rule(), ruleData.selectorIndex()));
    160     for (auto& classNameAndMatchElement : selectorFeatures.classes) {
    161         auto& className = classNameAndMatchElement.first;
    162         switch (classNameAndMatchElement.second) {
    163         case MatchElement::Subject:
    164             subjectClassRules.ensure(className, [] {
    165                 return std::make_unique<Vector<RuleFeature>>();
    166             }).iterator->value->append(RuleFeature(ruleData.rule(), ruleData.selectorIndex()));
    167             break;
    168         case MatchElement::Parent:
    169         case MatchElement::Ancestor:
    170             ancestorClassRules.ensure(className, [] {
    171                 return std::make_unique<Vector<RuleFeature>>();
    172             }).iterator->value->append(RuleFeature(ruleData.rule(), ruleData.selectorIndex()));
    173             break;
    174         case MatchElement::DirectSibling:
    175         case MatchElement::IndirectSibling:
    176         case MatchElement::ParentSibling:
    177         case MatchElement::AncestorSibling:
    178         case MatchElement::Host:
    179             otherClassesInRules.add(className);
    180             break;
    181         };
     160    for (auto& nameAndMatch : selectorFeatures.classes) {
     161        classRules.ensure(nameAndMatch.first, [] {
     162            return std::make_unique<Vector<RuleFeature>>();
     163        }).iterator->value->append(RuleFeature(ruleData.rule(), ruleData.selectorIndex(), nameAndMatch.second));
     164        if (nameAndMatch.second == MatchElement::Host)
     165            classesAffectingHost.add(nameAndMatch.first);
    182166    }
    183167    for (auto* selector : selectorFeatures.attributeSelectorsMatchingAncestors) {
    … …  
    197181    idsInRules.add(other.idsInRules.begin(), other.idsInRules.end());
    198182    idsMatchingAncestorsInRules.add(other.idsMatchingAncestorsInRules.begin(), other.idsMatchingAncestorsInRules.end());
    199     otherClassesInRules.add(other.otherClassesInRules.begin(), other.otherClassesInRules.end());
    200183    attributeCanonicalLocalNamesInRules.add(other.attributeCanonicalLocalNamesInRules.begin(), other.attributeCanonicalLocalNamesInRules.end());
    201184    attributeLocalNamesInRules.add(other.attributeLocalNamesInRules.begin(), other.attributeLocalNamesInRules.end());
    202185    siblingRules.appendVector(other.siblingRules);
    203186    uncommonAttributeRules.appendVector(other.uncommonAttributeRules);
    204     for (auto& keyValuePair : other.ancestorClassRules) {
    205         ancestorClassRules.ensure(keyValuePair.key, [] {
     187    for (auto& keyValuePair : other.classRules) {
     188        classRules.ensure(keyValuePair.key, [] {
    206189            return std::make_unique<Vector<RuleFeature>>();
    207190        }).iterator->value->appendVector(*keyValuePair.value);
    208191    }
    209     for (auto& keyValuePair : other.subjectClassRules) {
    210         subjectClassRules.ensure(keyValuePair.key, [] {
    211             return std::make_unique<Vector<RuleFeature>>();
    212         }).iterator->value->appendVector(*keyValuePair.value);
    213     }
     192    classesAffectingHost.add(other.classesAffectingHost.begin(), other.classesAffectingHost.end());
    214193
    215194    for (auto& keyValuePair : other.ancestorAttributeRulesForHTML) {
    … …  
    230209    idsInRules.clear();
    231210    idsMatchingAncestorsInRules.clear();
    232     otherClassesInRules.clear();
    233211    attributeCanonicalLocalNamesInRules.clear();
    234212    attributeLocalNamesInRules.clear();
    235213    siblingRules.clear();
    236214    uncommonAttributeRules.clear();
    237     ancestorClassRules.clear();
    238     subjectClassRules.clear();
     215    classRules.clear();
     216    classesAffectingHost.clear();
    239217    ancestorAttributeRulesForHTML.clear();
    240218    usesFirstLineRules = false;
    … …  
    246224    siblingRules.shrinkToFit();
    247225    uncommonAttributeRules.shrinkToFit();
    248     for (auto& rules : ancestorClassRules.values())
    249         rules->shrinkToFit();
    250     for (auto& rules : subjectClassRules.values())
     226    for (auto& rules : classRules.values())
    251227        rules->shrinkToFit();
    252228    for (auto& rules : ancestorAttributeRulesForHTML.values())

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

    r226703 r227787  
    3434class StyleRule;
    3535
     36enum class MatchElement { Subject, Parent, Ancestor, DirectSibling, IndirectSibling, ParentSibling, AncestorSibling, Host };
     37constexpr unsigned matchElementCount = static_cast<unsigned>(MatchElement::Host) + 1;
     38
    3639struct RuleFeature {
    37     RuleFeature(StyleRule* rule, unsigned selectorIndex)
     40    RuleFeature(StyleRule* rule, unsigned selectorIndex, std::optional<MatchElement> matchElement = std::nullopt)
    3841        : rule(rule)
    3942        , selectorIndex(selectorIndex)
     43        , matchElement(matchElement)
    4044    {
    4145    }
    4246    StyleRule* rule;
    4347    unsigned selectorIndex;
     48    std::optional<MatchElement> matchElement;
    4449};
    4550
    … …  
    5661    Vector<RuleFeature> siblingRules;
    5762    Vector<RuleFeature> uncommonAttributeRules;
    58     HashMap<AtomicString, std::unique_ptr<Vector<RuleFeature>>> ancestorClassRules;
    59     HashMap<AtomicString, std::unique_ptr<Vector<RuleFeature>>> subjectClassRules;
    60     HashSet<AtomicString> otherClassesInRules;
     63   
     64    HashMap<AtomicString, std::unique_ptr<Vector<RuleFeature>>> classRules;
     65    HashSet<AtomicString> classesAffectingHost;
    6166
    6267    struct AttributeRules {
    … …  
    7277
    7378private:
    74     enum class MatchElement { Subject, Parent, Ancestor, DirectSibling, IndirectSibling, ParentSibling, AncestorSibling, Host };
    75 
    7679    static MatchElement computeNextMatchElement(MatchElement, CSSSelector::RelationType);
    7780    static MatchElement computeSubSelectorMatchElement(MatchElement, const CSSSelector&);

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

    r226703 r227787  
    9090    bool shouldInvalidateCurrent = false;
    9191    bool mayAffectStyleInShadowTree = false;
    92     ClassChangeVector classesAffectingDescendant;
    93     ClassChangeVector classesAffectingCurrent;
    9492
    9593    traverseRuleFeatures(m_element, [&] (const RuleFeatureSet& features, bool mayAffectShadowTree) {
    9694        for (auto* changedClass : changedClasses) {
    97             bool mayAffectStyle = false;
    98             if (features.otherClassesInRules.contains(changedClass)) {
     95            if (mayAffectShadowTree && features.classRules.contains(changedClass))
     96                mayAffectStyleInShadowTree = true;
     97            if (features.classesAffectingHost.contains(changedClass))
    9998                shouldInvalidateCurrent = true;
    100                 mayAffectStyle = true;
    101             }
    102             if (features.ancestorClassRules.contains(changedClass)) {
    103                 classesAffectingDescendant.append(changedClass);
    104                 mayAffectStyle = true;
    105             }
    106             if (features.subjectClassRules.contains(changedClass)) {
    107                 classesAffectingCurrent.append(changedClass);
    108                 mayAffectStyle = true;
    109             }
    110             if (mayAffectStyle && mayAffectShadowTree)
    111                 mayAffectStyleInShadowTree = true;
    11299        }
    113100    });
    … …  
    119106    }
    120107
     108    if (shouldInvalidateCurrent)
     109        m_element.invalidateStyle();
     110
    121111    auto& ruleSets = m_element.styleResolver().ruleSets();
    122112
    123     if (childrenOfType<Element>(m_element).first()) {
    124         for (auto* changedClass : classesAffectingDescendant) {
    125             if (auto* rules = ruleSets.ancestorClassRules(changedClass))
    126                 m_invalidationRuleSets.append(rules);
     113    for (auto* changedClass : changedClasses) {
     114        if (auto* invalidationRuleSets = ruleSets.classInvalidationRuleSets(changedClass)) {
     115            for (auto& invalidationRuleSet : *invalidationRuleSets)
     116                m_invalidationRuleSets.append(&invalidationRuleSet);
    127117        }
    128     }
    129 
    130     if (shouldInvalidateCurrent) {
    131         m_element.invalidateStyle();
    132         return;
    133     }
    134 
    135     for (auto* changedClass : classesAffectingCurrent) {
    136         if (auto* rules = ruleSets.subjectClassRules(changedClass))
    137             m_invalidationRuleSets.append(rules);
    138118    }
    139119}
    … …  
    141121void ClassChangeInvalidation::invalidateStyleWithRuleSets()
    142122{
    143     for (auto* rules : m_invalidationRuleSets) {
    144         Invalidator invalidator(*rules);
    145         invalidator.invalidateStyle(m_element);
     123    for (auto* invalidationRuleSet : m_invalidationRuleSets) {
     124        Invalidator invalidator(*invalidationRuleSet->ruleSet);
     125        invalidator.invalidateStyleWithMatchElement(m_element, invalidationRuleSet->matchElement);
    146126    }
    147127}

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

    r226703 r227787  
    3434class RuleSet;
    3535class SpaceSplitString;
     36struct InvalidationRuleSet;
    3637
    3738namespace Style {
    … …  
    4950    Element& m_element;
    5051
    51     Vector<const RuleSet*, 4> m_invalidationRuleSets;
     52    Vector<const InvalidationRuleSet*, 4> m_invalidationRuleSets;
    5253};
    5354

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

    r216117 r227787  
    144144    if (invalidateIfNeeded(root, filter) == CheckDescendants::No)
    145145        return;
    146 
     146    invalidateStyleForDescendants(root, filter);
     147}
     148
     149void Invalidator::invalidateStyleForDescendants(Element& root, SelectorFilter* filter)
     150{
    147151    Vector<Element*, 20> parentStack;
    148152    Element* previousElement = &root;
    … …  
    206210}
    207211
    208 }
    209 }
     212void Invalidator::invalidateStyleWithMatchElement(Element& element, MatchElement matchElement)
     213{
     214    switch (matchElement) {
     215    case MatchElement::Subject: {
     216        invalidateIfNeeded(element, nullptr);
     217        break;
     218    }
     219    case MatchElement::Parent: {
     220        auto children = childrenOfType<Element>(element);
     221        for (auto& child : children)
     222            invalidateIfNeeded(child, nullptr);
     223        break;
     224    }
     225    case MatchElement::Ancestor: {
     226        invalidateStyleForDescendants(element, nullptr);
     227        break;
     228    }
     229    case MatchElement::DirectSibling:
     230    case MatchElement::IndirectSibling:
     231    case MatchElement::ParentSibling:
     232    case MatchElement::AncestorSibling:
     233        // FIXME: Currently sibling invalidation happens during style resolution tree walk. It should be done here too.
     234        element.invalidateStyle();
     235        break;
     236    case MatchElement::Host:
     237        // FIXME: Handle this here as well.
     238        break;
     239    }
     240}
     241
     242}
     243}

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

    r222113 r227787  
    2626#pragma once
    2727
     28#include "RuleFeature.h"
    2829#include <wtf/Forward.h>
    2930
    … …  
    5051    void invalidateStyle(ShadowRoot&);
    5152    void invalidateStyle(Element&);
     53    void invalidateStyleWithMatchElement(Element&, MatchElement);
    5254
    5355private:
    … …  
    5557    CheckDescendants invalidateIfNeeded(Element&, const SelectorFilter*);
    5658    void invalidateStyleForTree(Element&, SelectorFilter*);
     59    void invalidateStyleForDescendants(Element&, SelectorFilter*);
    5760
    5861    std::unique_ptr<RuleSet> m_ownedRuleSet;

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

    r226703 r227787  
    341341{
    342342    for (unsigned i = 0; i < classNames.size(); ++i) {
    343         if (m_ruleSets.features().otherClassesInRules.contains(classNames[i]))
     343        if (m_ruleSets.features().classRules.contains(classNames[i]))
    344344            return true;
    345         if (m_ruleSets.features().ancestorClassRules.contains(classNames[i]))
    346             return true;
    347         if (m_ruleSets.features().subjectClassRules.contains(classNames[i]))
    348             return true;
    349 
    350345    }
    351346    return false;
Note: See TracChangeset for help on using the changeset viewer.