Refactored invalidation set extraction.

third_party/WebKit/Source/core/css/RuleFeature.cpp

 /*
  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
  *           (C) 2004-2005 Allan Sandfeld Jensen (kde@carewolf.com)
  * Copyright (C) 2006, 2007 Nicholas Shanks (webkit@nickshanks.com)
  * Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012 Apple Inc. All rights reserved.
  * Copyright (C) 2007 Alexey Proskuryakov <ap@webkit.org>
  * Copyright (C) 2007, 2008 Eric Seidel <eric@webkit.org>
  * Copyright (C) 2008, 2009 Torch Mobile Inc. All rights reserved. (http://www.torchmobile.com/)
  * Copyright (c) 2011, Code Aurora Forum. All rights reserved.
  * Copyright (C) Research In Motion Limited 2011. All rights reserved.
@@ skipping 29 matching lines @@
 #include "core/css/invalidation/InvalidationSet.h"
 #include "core/dom/Element.h"
 #include "core/dom/Node.h"
 #include "core/inspector/InspectorTraceEvents.h"
 #include "wtf/BitVector.h"
 
 namespace blink {
 
 namespace {
 
-#if ENABLE(ASSERT)
-
 bool supportsInvalidation(CSSSelector::MatchType match)
 {
     switch (match) {
     case CSSSelector::Tag:
     case CSSSelector::Id:
     case CSSSelector::Class:
     case CSSSelector::AttributeExact:
     case CSSSelector::AttributeSet:
     case CSSSelector::AttributeHyphen:
     case CSSSelector::AttributeList:
     case CSSSelector::AttributeContain:
     case CSSSelector::AttributeBegin:
     case CSSSelector::AttributeEnd:
         return true;
     case CSSSelector::Unknown:
     case CSSSelector::PagePseudoClass:
         // These should not appear in StyleRule selectors.
-        ASSERT_NOT_REACHED();
+        NOTREACHED();
         return false;
     default:
         // New match type added. Figure out if it needs a subtree invalidation or not.
-        ASSERT_NOT_REACHED();
+        NOTREACHED();
         return false;
     }
 }
 
 bool supportsInvalidation(CSSSelector::PseudoType type)
 {
     switch (type) {
     case CSSSelector::PseudoEmpty:
     case CSSSelector::PseudoFirstChild:
     case CSSSelector::PseudoFirstOfType:
@@ skipping 71 matching lines @@
     case CSSSelector::PseudoSpatialNavigationFocus:
     case CSSSelector::PseudoListBox:
     case CSSSelector::PseudoHostHasAppearance:
     case CSSSelector::PseudoSlotted:
         return true;
     case CSSSelector::PseudoUnknown:
     case CSSSelector::PseudoLeftPage:
     case CSSSelector::PseudoRightPage:
     case CSSSelector::PseudoFirstPage:
         // These should not appear in StyleRule selectors.
-        ASSERT_NOT_REACHED();
+        NOTREACHED();
         return false;
     default:
         // New pseudo type added. Figure out if it needs a subtree invalidation or not.
-        ASSERT_NOT_REACHED();
+        NOTREACHED();
         return false;
     }
 }
 
 bool supportsInvalidationWithSelectorList(CSSSelector::PseudoType pseudo)
 {
     return pseudo == CSSSelector::PseudoAny
         || pseudo == CSSSelector::PseudoCue
         || pseudo == CSSSelector::PseudoHost
         || pseudo == CSSSelector::PseudoHostContext
         || pseudo == CSSSelector::PseudoNot
         || pseudo == CSSSelector::PseudoSlotted;
 }
 
-#endif // ENABLE(ASSERT)
-
 bool requiresSubtreeInvalidation(const CSSSelector& selector)
 {
     if (selector.match() != CSSSelector::PseudoElement && selector.match() != CSSSelector::PseudoClass) {
-        ASSERT(supportsInvalidation(selector.match()));
+        DCHECK(supportsInvalidation(selector.match()));
         return false;
     }
 
     switch (selector.getPseudoType()) {
     case CSSSelector::PseudoFirstLine:
     case CSSSelector::PseudoFirstLetter:
         // FIXME: Most pseudo classes/elements above can be supported and moved
         // to assertSupportedPseudo(). Move on a case-by-case basis. If they
         // require subtree invalidation, document why.
     case CSSSelector::PseudoHostContext:
         // :host-context matches a shadow host, yet the simple selectors inside
         // :host-context matches an ancestor of the shadow host.
         return true;
     default:
-        ASSERT(supportsInvalidation(selector.getPseudoType()));
+        DCHECK(supportsInvalidation(selector.getPseudoType()));
         return false;
     }
 }
 
 template<class Map>
 InvalidationSet& ensureInvalidationSet(Map& map, const typename Map::KeyType& key, InvalidationType type)
 {
     typename Map::AddResult addResult = map.add(key, nullptr);
     if (addResult.isNewEntry) {
         if (type == InvalidateDescendants)
@@ skipping 72 matching lines @@
 ALWAYS_INLINE InvalidationSet& RuleFeatureSet::ensureIdInvalidationSet(const AtomicString& id, InvalidationType type)
 {
     return ensureInvalidationSet(m_idInvalidationSets, id, type);
 }
 
 ALWAYS_INLINE InvalidationSet& RuleFeatureSet::ensurePseudoInvalidationSet(CSSSelector::PseudoType pseudoType, InvalidationType type)
 {
     return ensureInvalidationSet(m_pseudoInvalidationSets, pseudoType, type);
 }
 
-bool RuleFeatureSet::extractInvalidationSetFeature(const CSSSelector& selector, InvalidationSetFeatures& features)
+void RuleFeatureSet::updateFeaturesFromCombinator(
+    const CSSSelector& lastInCompound,
+    const CSSSelector* lastCompoundInAdjacentChain,
+    InvalidationSetFeatures& lastCompoundInAdjacentChainFeatures,
+    InvalidationSetFeatures*& siblingFeatures,
+    InvalidationSetFeatures& descendantFeatures)
+{
+    if (lastInCompound.isAdjacentSelector()) {
+        if (!siblingFeatures) {
+            siblingFeatures = &lastCompoundInAdjacentChainFeatures;
+            if (lastCompoundInAdjacentChain) {
+                extractInvalidationSetFeaturesFromCompound(*lastCompoundInAdjacentChain, lastCompoundInAdjacentChainFeatures, Ancestor);
+                if (!lastCompoundInAdjacentChainFeatures.hasFeatures())
+                    lastCompoundInAdjacentChainFeatures.forceSubtree = true;
+            }
+        }
+        if (siblingFeatures->maxDirectAdjacentSelectors == UINT_MAX)
+            return;
+        if (lastInCompound.relation() == CSSSelector::DirectAdjacent)
+            ++siblingFeatures->maxDirectAdjacentSelectors;
+        else
+            siblingFeatures->maxDirectAdjacentSelectors = UINT_MAX;
+        return;
+    }
+
+    if (siblingFeatures && lastCompoundInAdjacentChainFeatures.maxDirectAdjacentSelectors)
+        lastCompoundInAdjacentChainFeatures = InvalidationSetFeatures();
+
+    siblingFeatures = nullptr;
+
+    if (lastInCompound.isShadowSelector())
+        descendantFeatures.treeBoundaryCrossing = true;
+    if (lastInCompound.relation() == CSSSelector::ShadowSlot || lastInCompound.relationIsAffectedByPseudoContent())
+        descendantFeatures.insertionPointCrossing = true;
+    if (lastInCompound.relationIsAffectedByPseudoContent())
+        descendantFeatures.contentPseudoCrossing = true;
+}
+
+void RuleFeatureSet::extractInvalidationSetFeaturesFromSimpleSelector(const CSSSelector& selector, InvalidationSetFeatures& features)
 {
     if (selector.match() == CSSSelector::Tag && selector.tagQName().localName() != starAtom) {
         features.tagNames.append(selector.tagQName().localName());
-        return true;
+        return;
     }
     if (selector.match() == CSSSelector::Id) {
         features.ids.append(selector.value());
-        return true;
+        return;
     }
     if (selector.match() == CSSSelector::Class) {
         features.classes.append(selector.value());
-        return true;
+        return;
     }
     if (selector.isAttributeSelector()) {
         features.attributes.append(selector.attribute().localName());
-        return true;
+        return;
     }
-    if (selector.getPseudoType() == CSSSelector::PseudoWebKitCustomElement || selector.getPseudoType() == CSSSelector::PseudoBlinkInternalElement) {
+    switch (selector.getPseudoType()) {
+    case CSSSelector::PseudoWebKitCustomElement:
+    case CSSSelector::PseudoBlinkInternalElement:
         features.customPseudoElement = true;
-        return true;
+        return;
+    case CSSSelector::PseudoBefore:
+    case CSSSelector::PseudoAfter:
+        features.hasBeforeOrAfter = true;
+        return;
+    case CSSSelector::PseudoSlotted:
+        features.invalidatesSlotted = true;
+        return;
+    default:
+        return;
     }
-    // Returning false for ::before and ::after as they are not used as
-    // invalidation set features, only used later to generate invalidation sets
-    // for attributes present in "content: attr(...)" declarations.
-    if (selector.getPseudoType() == CSSSelector::PseudoBefore || selector.getPseudoType() == CSSSelector::PseudoAfter)
-        features.hasBeforeOrAfter = true;
-    return false;
 }
 
-InvalidationSet* RuleFeatureSet::invalidationSetForSelector(const CSSSelector& selector, InvalidationType type)
+InvalidationSet* RuleFeatureSet::invalidationSetForSimpleSelector(const CSSSelector& selector, InvalidationType type)
 {
     if (selector.match() == CSSSelector::Class)
         return &ensureClassInvalidationSet(selector.value(), type);
     if (selector.isAttributeSelector())
         return &ensureAttributeInvalidationSet(selector.attribute().localName(), type);
     if (selector.match() == CSSSelector::Id)
         return &ensureIdInvalidationSet(selector.value(), type);
     if (selector.match() == CSSSelector::PseudoClass) {
         switch (selector.getPseudoType()) {
         case CSSSelector::PseudoEmpty:
@@ skipping 37 matching lines @@
         case CSSSelector::PseudoNthLastChild:
         case CSSSelector::PseudoNthLastOfType:
             return &ensureNthInvalidationSet();
         default:
             break;
         }
     }
     return nullptr;
 }
 
-// Given a rule, update the descendant invalidation sets for the features found
-// in its selector. The first step is to extract the features from the rightmost
-// compound selector (extractInvalidationSetFeatures). Secondly, add those features
-// to the invalidation sets for the features found in the other compound selectors
-// (addFeaturesToInvalidationSets). If we find a feature in the right-most compound
-// selector that requires a subtree recalc, we addFeaturesToInvalidationSets for the
-// rightmost compound selector as well.
-
 void RuleFeatureSet::updateInvalidationSets(const RuleData& ruleData)
 {
+    // Given a rule, update the descendant invalidation sets for the features
+    // found in its selector. The first step is to extract the features from the
+    // rightmost compound selector (extractInvalidationSetFeatures). Secondly,

[Eric Willigers, 2016/09/03 02:57:57]

extractInvalidationSetFeatures becomes
extractInvalidationSetFeaturesFromCompound

[rune, 2016/09/05 08:16:20]

Done.

+    // add those features to the invalidation sets for the features found in the
+    // other compound selectors (addFeaturesToInvalidationSets). If we find a
+    // feature in the right-most compound selector that requires a subtree
+    // recalc, nextCompound will be the rightmost compound and we will
+    // addFeaturesToInvalidationSets for that one as well.
+
     InvalidationSetFeatures features;
-    auto result = extractInvalidationSetFeatures(ruleData.selector(), features, Subject);
+    const CSSSelector* nextCompound = extractInvalidationSetFeaturesFromCompound(ruleData.selector(), features, Subject);
 
-    features.forceSubtree = result.second == ForceSubtree;
-    if (result.first) {
-        addFeaturesToInvalidationSets(result.first, features.adjacent ? &features : nullptr, features);
-    } else if (features.hasNthPseudo) {
-        DCHECK(m_nthInvalidationSet);
-        addFeaturesToInvalidationSet(*m_nthInvalidationSet, features);
-    }
+    if (!features.hasFeatures())
+        features.forceSubtree = true;
 
-    // If any ::before and ::after rules specify 'content: attr(...)', we
-    // need to create invalidation sets for those attributes.
+    if (nextCompound)
+        addFeaturesToInvalidationSets(*nextCompound, features);
+    else if (features.hasNthPseudo)
+        addFeaturesToInvalidationSet(ensureNthInvalidationSet(), features);
+
     if (features.hasBeforeOrAfter)
         updateInvalidationSetsForContentAttribute(ruleData);
 }
 
 void RuleFeatureSet::updateInvalidationSetsForContentAttribute(const RuleData& ruleData)
 {
+    // If any ::before and ::after rules specify 'content: attr(...)', we
+    // need to create invalidation sets for those attributes to have content
+    // changes applied through style recalc.
+
     const StylePropertySet& propertySet = ruleData.rule()->properties();
 
     int propertyIndex = propertySet.findPropertyIndex(CSSPropertyContent);
 
     if (propertyIndex == -1)
         return;
 
     StylePropertySet::PropertyReference contentProperty = propertySet.propertyAt(propertyIndex);
     const CSSValue& contentValue = contentProperty.value();
 
     if (!contentValue.isValueList())
         return;
 
     for (auto& item : toCSSValueList(contentValue)) {
         if (!item->isFunctionValue())
             continue;
         const CSSFunctionValue* functionValue = toCSSFunctionValue(item.get());
         if (functionValue->functionType() != CSSValueAttr)
             continue;
         ensureAttributeInvalidationSet(AtomicString(toCSSCustomIdentValue(functionValue->item(0)).value()), InvalidateDescendants).setInvalidatesSelf();
     }
 }
 
-std::pair<const CSSSelector*, RuleFeatureSet::UseFeaturesType>
-RuleFeatureSet::extractInvalidationSetFeatures(const CSSSelector& selector, InvalidationSetFeatures& features, PositionType position, CSSSelector::PseudoType pseudo)
+const CSSSelector*
+RuleFeatureSet::extractInvalidationSetFeaturesFromSelectorList(const CSSSelector& simpleSelector, InvalidationSetFeatures& features, PositionType position)
 {
-    bool foundFeatures = false;
-    for (const CSSSelector* current = &selector; current; current = current->tagHistory()) {
-        if (pseudo != CSSSelector::PseudoNot)
-            foundFeatures |= extractInvalidationSetFeature(*current, features);
-        // Initialize the entry in the invalidation set map, if supported.
-        if (InvalidationSet* invalidationSet = invalidationSetForSelector(*current, InvalidateDescendants)) {
-            if (position == Subject) {
-                if (invalidationSet == m_nthInvalidationSet)
-                    features.hasNthPseudo = true;
-                else
-                    invalidationSet->setInvalidatesSelf();
-            }
-        } else {
-            if (requiresSubtreeInvalidation(*current)) {
-                // Fall back to use subtree invalidations, even for features in the
-                // rightmost compound selector. Returning the start &selector here
-                // will make addFeaturesToInvalidationSets start marking invalidation
-                // sets for subtree recalc for features in the rightmost compound
-                // selector.
-                return std::make_pair(&selector, ForceSubtree);
-            }
-            if (const CSSSelectorList* selectorList = current->selectorList()) {
-                if (current->getPseudoType() == CSSSelector::PseudoSlotted) {
-                    ASSERT(position == Subject);
-                    features.invalidatesSlotted = true;
-                }
-                ASSERT(supportsInvalidationWithSelectorList(current->getPseudoType()));
-                const CSSSelector* subSelector = selectorList->first();
-                bool allSubSelectorsHaveFeatures = !!subSelector;
-                for (; subSelector; subSelector = CSSSelectorList::next(*subSelector)) {
-                    auto result = extractInvalidationSetFeatures(*subSelector, features, position, current->getPseudoType());
-                    if (result.first) {
-                        // A non-null selector return means the sub-selector contained a
-                        // selector which requiresSubtreeInvalidation(). Return the rightmost
-                        // selector to mark for subtree recalcs like above.
-                        return std::make_pair(&selector, ForceSubtree);
-                    }
-                    allSubSelectorsHaveFeatures &= result.second == UseFeatures;
-                }
-                foundFeatures |= allSubSelectorsHaveFeatures;
-            }
+    const CSSSelectorList* selectorList = simpleSelector.selectorList();
+    if (!selectorList)
+        return nullptr;
+
+    DCHECK(supportsInvalidationWithSelectorList(simpleSelector.getPseudoType()));
+
+    const CSSSelector* subSelector = selectorList->first();
+
+    bool allSubSelectorsHaveFeatures = true;
+    InvalidationSetFeatures anyFeatures;
+
+    for (; subSelector; subSelector = CSSSelectorList::next(*subSelector)) {
+        InvalidationSetFeatures compoundFeatures;
+        if (extractInvalidationSetFeaturesFromCompound(*subSelector, compoundFeatures, position, simpleSelector.getPseudoType())) {
+            // A non-null selector return means the sub-selector contained a
+            // selector which requiresSubtreeInvalidation().
+            DCHECK(compoundFeatures.forceSubtree);
+            features.forceSubtree = true;
+            return &simpleSelector;
+        }
+        if (allSubSelectorsHaveFeatures && !compoundFeatures.hasFeatures())
+            allSubSelectorsHaveFeatures = false;
+        else
+            anyFeatures.add(compoundFeatures);
+        if (compoundFeatures.hasNthPseudo)
+            features.hasNthPseudo = true;
+    }
+    // Don't add any features if one of the sub-selectors of does not contain
+    // any invalidation set features. E.g. :-webkit-any(*, span).
+    if (allSubSelectorsHaveFeatures)
+        features.add(anyFeatures);
+    return nullptr;
+}
+
+const CSSSelector*
+RuleFeatureSet::extractInvalidationSetFeaturesFromCompound(const CSSSelector& compound, InvalidationSetFeatures& features, PositionType position, CSSSelector::PseudoType pseudo)
+{
+    const CSSSelector* simpleSelector = &compound;
+    for (; simpleSelector; simpleSelector = simpleSelector->tagHistory()) {
+
+        // Fall back to use subtree invalidations, even for features in the
+        // rightmost compound selector. Returning the start &selector here
+        // will make addFeaturesToInvalidationSets start marking invalidation
+        // sets for subtree recalc for features in the rightmost compound
+        // selector.
+        if (requiresSubtreeInvalidation(*simpleSelector)) {
+            features.forceSubtree = true;
+            return &compound;
         }
 
-        if (current->relation() == CSSSelector::SubSelector)
+        // When inside a :not(), we should not use the found features for
+        // invalidation because we should invalidate elements _without_ that
+        // feature. On the other hand, we should still have invalidation sets
+        // for the features since we are able to detect when they change.
+        // That is, ".a" should not have ".b" in its invalidation set for
+        // ".a :not(.b)", but there should be an invalidation set for ".a" in
+        // ":not(.a) .b".
+        if (pseudo != CSSSelector::PseudoNot)
+            extractInvalidationSetFeaturesFromSimpleSelector(*simpleSelector, features);
+
+        // Initialize the entry in the invalidation set map for self-
+        // invalidation, if supported.
+        if (InvalidationSet* invalidationSet = invalidationSetForSimpleSelector(*simpleSelector, InvalidateDescendants)) {
+            if (invalidationSet == m_nthInvalidationSet)
+                features.hasNthPseudo = true;
+            else if (position == Subject)
+                invalidationSet->setInvalidatesSelf();
+        }
+
+        if (extractInvalidationSetFeaturesFromSelectorList(*simpleSelector, features, position)) {
+            DCHECK(features.forceSubtree);
+            return &compound;
+        }
+
+        if (simpleSelector->relation() == CSSSelector::SubSelector)
             continue;
 
-        if (features.hasNthPseudo && position == Subject) {
-            DCHECK(m_nthInvalidationSet);
-            if (foundFeatures)
-                addFeaturesToInvalidationSet(*m_nthInvalidationSet, features);
-            else
-                m_nthInvalidationSet->setWholeSubtreeInvalid();
+        if (position == Subject) {
+            if (features.hasNthPseudo) {
+                DCHECK(m_nthInvalidationSet);
+                if (features.hasFeatures())
+                    addFeaturesToInvalidationSet(*m_nthInvalidationSet, features);
+                else
+                    m_nthInvalidationSet->setWholeSubtreeInvalid();
+            }
+            InvalidationSetFeatures* siblingFeatures = nullptr;
+            updateFeaturesFromCombinator(*simpleSelector, nullptr, features, siblingFeatures, features);
         }
+        return simpleSelector->tagHistory();
+    }
 
-        features.treeBoundaryCrossing = current->isShadowSelector();
-        if (current->relationIsAffectedByPseudoContent()) {
-            features.contentPseudoCrossing = true;
-            features.insertionPointCrossing = true;
-        }
-        features.adjacent = current->isAdjacentSelector();
-        if (current->relation() == CSSSelector::DirectAdjacent)
-            features.maxDirectAdjacentSelectors = 1;
-        return std::make_pair(current->tagHistory(), foundFeatures ? UseFeatures : ForceSubtree);
-    }
-    return std::make_pair(nullptr, foundFeatures ? UseFeatures : ForceSubtree);
+    return nullptr;
 }
 
 // Add features extracted from the rightmost compound selector to descendant invalidation
 // sets for features found in other compound selectors.
 //
 // We use descendant invalidation for descendants, sibling invalidation for siblings and their subtrees.
 //
 // As we encounter a descendant type of combinator, the features only need to be checked
 // against descendants in the same subtree only. features.adjacent is set to false, and
 // we start adding features to the descendant invalidation set.
@@ skipping 16 matching lines @@
     for (const auto& tagName : features.tagNames)
         invalidationSet.addTagName(tagName);
     for (const auto& className : features.classes)
         invalidationSet.addClass(className);
     for (const auto& attribute : features.attributes)
         invalidationSet.addAttribute(attribute);
     if (features.customPseudoElement)
         invalidationSet.setCustomPseudoInvalid();
 }
 
-// selector is the selector immediately to the left of the rightmost combinator.
-// siblingFeatures is null if selector is not immediately to the left of a sibling combinator.
-// descendantFeatures has the features of the rightmost compound selector.
-void RuleFeatureSet::addFeaturesToInvalidationSets(const CSSSelector* selector, InvalidationSetFeatures* siblingFeatures, InvalidationSetFeatures& descendantFeatures)
+
+void RuleFeatureSet::addFeaturesToInvalidationSetsForSelectorList(const CSSSelector& simpleSelector, InvalidationSetFeatures* siblingFeatures, InvalidationSetFeatures& descendantFeatures)
 {
-    const CSSSelector* lastCompoundSelectorInAdjacentChain = selector;
+    if (!simpleSelector.selectorList())
+        return;
 
-    // We set siblingFeatures to &localFeatures if we find a rightmost sibling combinator.
-    InvalidationSetFeatures localFeatures;
+    DCHECK(supportsInvalidationWithSelectorList(simpleSelector.getPseudoType()));
 
-    bool universalCompound = true;
+    for (const CSSSelector* subSelector = simpleSelector.selectorList()->first(); subSelector; subSelector = CSSSelectorList::next(*subSelector))
+        addFeaturesToInvalidationSetsForCompoundSelector(*subSelector, siblingFeatures, descendantFeatures);
+}
 
-    for (const CSSSelector* current = selector; current; current = current->tagHistory()) {
-        InvalidationType type = siblingFeatures ? InvalidateSiblings : InvalidateDescendants;
-        if (InvalidationSet* invalidationSet = invalidationSetForSelector(*current, type)) {
-            if (current->match() != CSSSelector::PseudoClass)
-                universalCompound = false;
-            if (siblingFeatures && invalidationSet != m_nthInvalidationSet) {
-                SiblingInvalidationSet* siblingInvalidationSet = toSiblingInvalidationSet(invalidationSet);
-                siblingInvalidationSet->updateMaxDirectAdjacentSelectors(siblingFeatures->maxDirectAdjacentSelectors);
-
-                addFeaturesToInvalidationSet(*invalidationSet, *siblingFeatures);
-                if (siblingFeatures == &descendantFeatures)
-                    siblingInvalidationSet->setInvalidatesSelf();
-                else
-                    addFeaturesToInvalidationSet(siblingInvalidationSet->ensureSiblingDescendants(), descendantFeatures);
-            } else {
-                addFeaturesToInvalidationSet(*invalidationSet, descendantFeatures);
-            }
-        } else {
-            if (current->isHostPseudoClass())
-                descendantFeatures.treeBoundaryCrossing = true;
-            if (current->isInsertionPointCrossing())
-                descendantFeatures.insertionPointCrossing = true;
-            if (const CSSSelectorList* selectorList = current->selectorList()) {
-                ASSERT(supportsInvalidationWithSelectorList(current->getPseudoType()));
-                for (const CSSSelector* subSelector = selectorList->first(); subSelector; subSelector = CSSSelectorList::next(*subSelector))
-                    addFeaturesToInvalidationSets(subSelector, siblingFeatures, descendantFeatures);
-            }
+void RuleFeatureSet::addFeaturesToInvalidationSetsForSimpleSelector(const CSSSelector& simpleSelector, InvalidationSetFeatures* siblingFeatures, InvalidationSetFeatures& descendantFeatures)
+{
+    if (InvalidationSet* invalidationSet = invalidationSetForSimpleSelector(simpleSelector, siblingFeatures ? InvalidateSiblings : InvalidateDescendants)) {
+        if (!siblingFeatures || invalidationSet == m_nthInvalidationSet) {
+            addFeaturesToInvalidationSet(*invalidationSet, descendantFeatures);
+            return;
         }
 
-        if (current->relation() == CSSSelector::SubSelector)
-            continue;
-
-        if (universalCompound && siblingFeatures)
-            addFeaturesToUniversalSiblingInvalidationSet(*siblingFeatures, descendantFeatures);
-        universalCompound = true;
-
-        if (current->relationIsAffectedByPseudoContent() || current->relation() == CSSSelector::ShadowSlot) {
-            descendantFeatures.insertionPointCrossing = true;
-            descendantFeatures.contentPseudoCrossing = true;
-        }
-        if (current->isShadowSelector())
-            descendantFeatures.treeBoundaryCrossing = true;
-        if (!current->isAdjacentSelector()) {
-            lastCompoundSelectorInAdjacentChain = current->tagHistory();
-            siblingFeatures = nullptr;
-            continue;
-        }
-
-        if (siblingFeatures) {
-            if (siblingFeatures->maxDirectAdjacentSelectors == UINT_MAX)
-                continue;
-
-            if (current->relation() == CSSSelector::DirectAdjacent)
-                siblingFeatures->maxDirectAdjacentSelectors++;
-            else
-                siblingFeatures->maxDirectAdjacentSelectors = UINT_MAX;
-            continue;
-        }
-
-        localFeatures = InvalidationSetFeatures();
-        auto result = extractInvalidationSetFeatures(*lastCompoundSelectorInAdjacentChain, localFeatures, Ancestor);
-        ASSERT(result.first);
-        localFeatures.forceSubtree = result.second == ForceSubtree;
-        siblingFeatures = &localFeatures;
+        SiblingInvalidationSet* siblingInvalidationSet = toSiblingInvalidationSet(invalidationSet);
+        siblingInvalidationSet->updateMaxDirectAdjacentSelectors(siblingFeatures->maxDirectAdjacentSelectors);
+        addFeaturesToInvalidationSet(*invalidationSet, *siblingFeatures);
+        if (siblingFeatures == &descendantFeatures)
+            siblingInvalidationSet->setInvalidatesSelf();
+        else
+            addFeaturesToInvalidationSet(siblingInvalidationSet->ensureSiblingDescendants(), descendantFeatures);
+        return;
     }
 
-    if (universalCompound && siblingFeatures)
+    if (simpleSelector.isHostPseudoClass())
+        descendantFeatures.treeBoundaryCrossing = true;
+    if (simpleSelector.isInsertionPointCrossing())
+        descendantFeatures.insertionPointCrossing = true;
+
+    addFeaturesToInvalidationSetsForSelectorList(simpleSelector, siblingFeatures, descendantFeatures);
+}
+
+const CSSSelector* RuleFeatureSet::addFeaturesToInvalidationSetsForCompoundSelector(const CSSSelector& compound, InvalidationSetFeatures* siblingFeatures, InvalidationSetFeatures& descendantFeatures)
+{
+    bool compoundHasTagIdClassOrAttribute = false;
+    const CSSSelector* simpleSelector = &compound;
+    for (; simpleSelector; simpleSelector = simpleSelector->tagHistory()) {
+        addFeaturesToInvalidationSetsForSimpleSelector(*simpleSelector, siblingFeatures, descendantFeatures);
+        if (siblingFeatures)
+            compoundHasTagIdClassOrAttribute |= simpleSelector->isIdClassOrAttributeSelector();

[Eric Willigers, 2016/09/03 02:57:57]

tag? Should the CSSSelector method also consider tag?

[rune, 2016/09/05 08:16:20]

Then we would need to have invalidation sets for tags. We haven't had that since
an element cannot change tag name, but it would make sense for invalidations for
sibling mutations. This CL shouldn't cover that, though.

+        if (simpleSelector->relation() != CSSSelector::SubSelector)
+            break;
+        if (!simpleSelector->tagHistory())
+            break;
+    }
+
+    if (siblingFeatures && !compoundHasTagIdClassOrAttribute)
         addFeaturesToUniversalSiblingInvalidationSet(*siblingFeatures, descendantFeatures);
+
+    return simpleSelector;
+}
+
+void RuleFeatureSet::addFeaturesToInvalidationSets(const CSSSelector& selector, InvalidationSetFeatures& descendantFeatures)
+{
+    // selector is the selector immediately to the left of the rightmost combinator.
+    // descendantFeatures has the features of the rightmost compound selector.
+
+    InvalidationSetFeatures lastCompoundInSiblingChainFeatures;
+    InvalidationSetFeatures* siblingFeatures = descendantFeatures.maxDirectAdjacentSelectors ? &descendantFeatures : nullptr;
+
+    const CSSSelector* compound = &selector;
+    while (compound) {
+        const CSSSelector* lastInCompound = addFeaturesToInvalidationSetsForCompoundSelector(*compound, siblingFeatures, descendantFeatures);
+        DCHECK(lastInCompound);
+        updateFeaturesFromCombinator(*lastInCompound, compound, lastCompoundInSiblingChainFeatures, siblingFeatures, descendantFeatures);
+        compound = lastInCompound->tagHistory();
+    }
 }
 
 RuleFeatureSet::SelectorPreMatch RuleFeatureSet::collectFeaturesFromRuleData(const RuleData& ruleData)
 {
     RELEASE_ASSERT(m_isAlive);
     FeatureMetadata metadata;
     if (collectFeaturesFromSelector(ruleData.selector(), metadata) == SelectorNeverMatches)
         return SelectorNeverMatches;
 
     m_metadata.add(metadata);
@@ skipping 68 matching lines @@
             && ((relation != CSSSelector::SubSelector) || current->isLastInTagHistory())) {
             if (maxDirectAdjacentSelectors > metadata.maxDirectAdjacentSelectors)
                 metadata.maxDirectAdjacentSelectors = maxDirectAdjacentSelectors;
             maxDirectAdjacentSelectors = 0;
         }
 
         if (!metadata.foundInsertionPointCrossing && current->isAdjacentSelector())
             metadata.foundSiblingSelector = true;
     }
 
-    ASSERT(!maxDirectAdjacentSelectors);
+    DCHECK(!maxDirectAdjacentSelectors);
     return SelectorMayMatch;
 }
 
 void RuleFeatureSet::FeatureMetadata::add(const FeatureMetadata& other)
 {
     usesFirstLineRules = usesFirstLineRules || other.usesFirstLineRules;
     usesWindowInactiveSelector = usesWindowInactiveSelector || other.usesWindowInactiveSelector;
     maxDirectAdjacentSelectors = std::max(maxDirectAdjacentSelectors, other.maxDirectAdjacentSelectors);
 }
 
@@ skipping 218 matching lines @@
     else
         addFeaturesToInvalidationSet(universalSet.ensureSiblingDescendants(), descendantFeatures);
 }
 
 DEFINE_TRACE(RuleFeatureSet)
 {
     visitor->trace(siblingRules);
     visitor->trace(uncommonAttributeRules);
 }
 
+void RuleFeatureSet::InvalidationSetFeatures::add(const InvalidationSetFeatures& other)
+{
+    classes.appendVector(other.classes);
+    attributes.appendVector(other.attributes);
+    ids.appendVector(other.ids);
+    tagNames.appendVector(other.tagNames);
+    maxDirectAdjacentSelectors = std::max(maxDirectAdjacentSelectors, other.maxDirectAdjacentSelectors);
+    customPseudoElement |= other.customPseudoElement;
+    hasBeforeOrAfter |= other.hasBeforeOrAfter;
+    treeBoundaryCrossing |= other.treeBoundaryCrossing;
+    insertionPointCrossing |= other.insertionPointCrossing;
+    forceSubtree |= other.forceSubtree;
+    contentPseudoCrossing |= other.contentPseudoCrossing;
+    invalidatesSlotted |= other.invalidatesSlotted;
+    hasNthPseudo |= other.hasNthPseudo;
+}
+
+bool RuleFeatureSet::InvalidationSetFeatures::hasFeatures() const
+{
+    return !classes.isEmpty()
+        || !attributes.isEmpty()
+        || !ids.isEmpty()
+        || !tagNames.isEmpty()
+        || customPseudoElement;
+}
+
 } // namespace blink