Single code path for updating invalidation sets.

Source/core/css/RuleFeature.cpp

Index: Source/core/css/RuleFeature.cpp
diff --git a/Source/core/css/RuleFeature.cpp b/Source/core/css/RuleFeature.cpp
index 2cbc51daa1f5af4a96b621de7c3ad3ea29c15af4..b792d56488a15a256a4f6b189f50e2b20f4268ea 100644
--- a/Source/core/css/RuleFeature.cpp
+++ b/Source/core/css/RuleFeature.cpp
@@ -163,6 +163,15 @@ static bool supportsInvalidation(CSSSelector::PseudoType type)
     }
 }
 
+static bool supportsInvalidationWithSelectorList(CSSSelector::PseudoType pseudo)
+{
+    return pseudo == CSSSelector::PseudoAny
+        || pseudo == CSSSelector::PseudoCue
+        || pseudo == CSSSelector::PseudoHost
+        || pseudo == CSSSelector::PseudoHostContext

[chrishtr, 2014/11/13 23:01:11]

This one is sort of unrelated to the main thrust of this CL, right?

[rune, 2014/11/14 00:04:53]

This is what's described in the last section of the CL description about not
requiring subtree invalidation for :host-context presence in other compound
selectors than the rightmost one. Introducing a single pass through the
selector, which is the main thing with this CL, makes it hard if there are
selectors in the non-rightmost-compound that can trigger subtree recalcs because
we then would've already started to add features to invalidation sets before
discovering that we should've set wholeSubtree instead. It's possible to do the
allow :host-context part first. That would mean modifying the
InvalidationSetMode code to do so before introducing this CL which will just
nuke that again.

+        || pseudo == CSSSelector::PseudoNot;
+}
+
 #endif // ENABLE(ASSERT)
 
 static bool requiresSubtreeInvalidation(const CSSSelector& selector)
@@ -200,77 +209,9 @@ void RuleFeature::trace(Visitor* visitor)
     visitor->trace(rule);
 }
 
-static bool supportsInvalidationWithSelectorList(CSSSelector::PseudoType pseudo)
-{
-    return pseudo == CSSSelector::PseudoAny
-        || pseudo == CSSSelector::PseudoCue
-        || pseudo == CSSSelector::PseudoHost
-        || pseudo == CSSSelector::PseudoNot;
-}
-
-// This method is somewhat conservative in what it accepts.
-RuleFeatureSet::InvalidationSetMode RuleFeatureSet::invalidationSetModeForSelector(const CSSSelector& selector)
+bool RuleFeatureSet::extractInvalidationSetFeature(const CSSSelector& selector, InvalidationSetFeatures& features)
 {
-    bool foundCombinator = false;
-    bool foundIdent = false;
-    for (const CSSSelector* component = &selector; component; component = component->tagHistory()) {
-
-        if (component->match() == CSSSelector::Class || component->match() == CSSSelector::Id
-            || (component->match() == CSSSelector::Tag && component->tagQName().localName() != starAtom)
-            || component->isAttributeSelector() || component->isCustomPseudoElement()) {
-            if (!foundCombinator) {
-                // We have found an invalidation set feature in the rightmost compound selector.
-                foundIdent = true;
-            }
-        } else if (supportsInvalidationWithSelectorList(component->pseudoType())) {
-            if (const CSSSelectorList* selectorList = component->selectorList()) {
-                // Features inside :not() are not added to the feature set, so consider it a universal selector.
-                bool foundUniversal = component->pseudoType() == CSSSelector::PseudoNot;
-                for (const CSSSelector* selector = selectorList->first(); selector; selector = CSSSelectorList::next(*selector)) {
-                    // Find the invalidation set mode for each of the selectors in the selector list
-                    // of a :not(), :host(), etc. For instance, ".x :-webkit-any(.a, .b)" yields an
-                    // AddFeatures mode for both ".a" and ".b". ":-webkit-any(.a, *)" yields AddFeatures
-                    // for ".a", but UseSubtreeStyleChange for "*". One sub-selector without invalidation
-                    // set features is sufficient to cause the selector to be a universal selector as far
-                    // the invalidation set is concerned.
-                    InvalidationSetMode subSelectorMode = invalidationSetModeForSelector(*selector);
-
-                    // The sub-selector contained something unskippable, fall back to whole subtree
-                    // recalcs in collectFeaturesFromSelector. subSelectorMode will return
-                    // UseSubtreeStyleChange since there are no combinators inside the selector list,
-                    // so translate it to UseLocalStyleChange if a combinator has been seen in the
-                    // outer context.
-                    //
-                    // FIXME: Is UseSubtreeStyleChange ever needed as input to collectFeaturesFromSelector?
-                    // That is, are there any selectors for which we need to use SubtreeStyleChange for
-                    // changing features when present in the rightmost compound selector?
-                    if (subSelectorMode == UseSubtreeStyleChange)
-                        return foundCombinator ? UseLocalStyleChange : UseSubtreeStyleChange;
-
-                    // We found no features in the sub-selector, only skippable ones (foundIdent was
-                    // false at the end of this method). That is a universal selector as far as the
-                    // invalidation set is concerned.
-                    if (subSelectorMode == UseLocalStyleChange)
-                        foundUniversal = true;
-                }
-                if (!foundUniversal && !foundCombinator) {
-                    // All sub-selectors contained invalidation set features and
-                    // we are in the rightmost compound selector.
-                    foundIdent = true;
-                }
-            }
-        } else if (requiresSubtreeInvalidation(*component)) {
-            return foundCombinator ? UseLocalStyleChange : UseSubtreeStyleChange;
-        }
-        if (component->relation() != CSSSelector::SubSelector)
-            foundCombinator = true;
-    }
-    return foundIdent ? AddFeatures : UseLocalStyleChange;
-}
-
-void RuleFeatureSet::extractInvalidationSetFeature(const CSSSelector& selector, InvalidationSetFeatures& features)
-{
-    if (selector.match() == CSSSelector::Tag)
+    if (selector.match() == CSSSelector::Tag && selector.tagQName().localName() != starAtom)

[chrishtr, 2014/11/13 23:01:11]

Why this change?

[rune, 2014/11/14 00:04:53]

It's to get the return value correct, and avoid using "*" as a tag name.

The universal selector is not a feature like a tag name is. Alternatively, I
could've done:

if (selector.match() == CSSSelector::Tag) {
    features.tagName = selector.tagQName().localName();
    return features.tagName != starAtom;
}

to not change the behavior, but before this change, and with the alternative
above, we would unnecessarily add "*" as a tag name to the invalidation set hash
map for tag names. This should be an improvement.

         features.tagName = selector.tagQName().localName();
     else if (selector.match() == CSSSelector::Id)
         features.id = selector.value();
@@ -280,6 +221,9 @@ void RuleFeatureSet::extractInvalidationSetFeature(const CSSSelector& selector,
         features.attributes.append(selector.attribute().localName());
     else if (selector.isCustomPseudoElement())
         features.customPseudoElement = true;
+    else
+        return false;
+    return true;

[chrishtr, 2014/11/13 23:01:11]

Is this code reachable?

[rune, 2014/11/14 00:04:53]

Yes, it's the return value for all but the last else.

 }
 
 RuleFeatureSet::RuleFeatureSet()
@@ -321,38 +265,59 @@ DescendantInvalidationSet* RuleFeatureSet::invalidationSetForSelector(const CSSS
             break;
         }
     }
-    return 0;
+    return nullptr;
 }
 
 // Given a selector, update the descendant invalidation sets for the features found
 // in the selector. The first step is to extract the features from the rightmost
-// compound selector (extractInvalidationSetFeatures). Secondly, those features will be
-// added to the invalidation sets for the features found in the other compound selectors
-// (addFeaturesToInvalidationSets).
+// 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.
 
-RuleFeatureSet::InvalidationSetMode RuleFeatureSet::updateInvalidationSets(const CSSSelector& selector)
+void RuleFeatureSet::updateInvalidationSets(const CSSSelector& selector)
 {
-    InvalidationSetMode mode = invalidationSetModeForSelector(selector);
-    if (mode != AddFeatures)
-        return mode;
-
     InvalidationSetFeatures features;
-    if (const CSSSelector* current = extractInvalidationSetFeatures(selector, features, false))
-        addFeaturesToInvalidationSets(*current, features);
-    return AddFeatures;
+    auto result = extractInvalidationSetFeatures(selector, features, false);
+    if (result.first) {
+        features.forceSubtree = result.second == ForceSubtree;
+        addFeaturesToInvalidationSets(*result.first, features);
+    }
 }
 
-const CSSSelector* RuleFeatureSet::extractInvalidationSetFeatures(const CSSSelector& selector, InvalidationSetFeatures& features, bool negated)
+std::pair<const CSSSelector*, RuleFeatureSet::UseFeaturesType>
+RuleFeatureSet::extractInvalidationSetFeatures(const CSSSelector& selector, InvalidationSetFeatures& features, bool negated)
 {
+    bool foundFeatures = false;
     for (const CSSSelector* current = &selector; current; current = current->tagHistory()) {
         if (!negated)
-            extractInvalidationSetFeature(*current, features);
+            foundFeatures |= extractInvalidationSetFeature(*current, features);
         // Initialize the entry in the invalidation set map, if supported.
-        invalidationSetForSelector(*current);
-        if (supportsInvalidationWithSelectorList(current->pseudoType())) {
+        if (!invalidationSetForSelector(*current)) {
+            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()) {
-                for (const CSSSelector* selector = selectorList->first(); selector; selector = CSSSelectorList::next(*selector))
-                    extractInvalidationSetFeatures(*selector, features, current->pseudoType() == CSSSelector::PseudoNot);
+                ASSERT(supportsInvalidationWithSelectorList(current->pseudoType()));
+                const CSSSelector* subSelector = selectorList->first();
+                bool allSubSelectorsHaveFeatures = !!subSelector;
+                for (; subSelector; subSelector = CSSSelectorList::next(*subSelector)) {
+                    auto result = extractInvalidationSetFeatures(*subSelector, features, current->pseudoType() == CSSSelector::PseudoNot);
+                    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;
             }
         }
 
@@ -361,9 +326,9 @@ const CSSSelector* RuleFeatureSet::extractInvalidationSetFeatures(const CSSSelec
 
         features.treeBoundaryCrossing = current->isShadowSelector();
         features.adjacent = current->isAdjacentSelector();
-        return current->tagHistory();
+        return std::make_pair(current->tagHistory(), foundFeatures ? UseFeatures : ForceSubtree);
     }
-    return 0;
+    return std::make_pair(nullptr, ForceSubtree);
 }
 
 // Add features extracted from the rightmost compound selector to descendant invalidation
@@ -384,7 +349,7 @@ void RuleFeatureSet::addFeaturesToInvalidationSet(DescendantInvalidationSet& inv
         invalidationSet.setTreeBoundaryCrossing();
     if (features.insertionPointCrossing)
         invalidationSet.setInsertionPointCrossing();
-    if (features.adjacent) {
+    if (features.useSubtreeInvalidation()) {
         invalidationSet.setWholeSubtreeInvalid();
         return;
     }
@@ -434,10 +399,10 @@ void RuleFeatureSet::addContentAttr(const AtomicString& attributeName)
 
 void RuleFeatureSet::collectFeaturesFromRuleData(const RuleData& ruleData)
 {
-    FeatureMetadata metadata;
-    InvalidationSetMode mode = updateInvalidationSets(ruleData.selector());
+    updateInvalidationSets(ruleData.selector());
 
-    collectFeaturesFromSelector(ruleData.selector(), metadata, mode);
+    FeatureMetadata metadata;
+    collectFeaturesFromSelector(ruleData.selector(), metadata);
     m_metadata.add(metadata);
 
     if (metadata.foundSiblingSelector)
@@ -478,17 +443,11 @@ DescendantInvalidationSet& RuleFeatureSet::ensurePseudoInvalidationSet(CSSSelect
     return *addResult.storedValue->value;
 }
 
-void RuleFeatureSet::collectFeaturesFromSelector(const CSSSelector& selector, RuleFeatureSet::FeatureMetadata& metadata, InvalidationSetMode mode)
+void RuleFeatureSet::collectFeaturesFromSelector(const CSSSelector& selector, RuleFeatureSet::FeatureMetadata& metadata)
 {
     unsigned maxDirectAdjacentSelectors = 0;
 
     for (const CSSSelector* current = &selector; current; current = current->tagHistory()) {
-        if (mode != AddFeatures) {
-            if (DescendantInvalidationSet* invalidationSet = invalidationSetForSelector(*current)) {
-                if (mode == UseSubtreeStyleChange)
-                    invalidationSet->setWholeSubtreeInvalid();
-            }
-        }
         if (current->pseudoType() == CSSSelector::PseudoFirstLine)
             metadata.usesFirstLineRules = true;
         if (current->isDirectAdjacentSelector()) {
@@ -501,24 +460,17 @@ void RuleFeatureSet::collectFeaturesFromSelector(const CSSSelector& selector, Ru
         if (current->isSiblingSelector())
             metadata.foundSiblingSelector = true;
 
-        collectFeaturesFromSelectorList(current->selectorList(), metadata, mode);
+        const CSSSelectorList* selectorList = current->selectorList();
+        if (!selectorList)
+            continue;
 
-        if (mode == UseLocalStyleChange && current->relation() != CSSSelector::SubSelector)
-            mode = UseSubtreeStyleChange;
+        for (const CSSSelector* selector = selectorList->first(); selector; selector = CSSSelectorList::next(*selector))
+            collectFeaturesFromSelector(*selector, metadata);
     }
 
     ASSERT(!maxDirectAdjacentSelectors);
 }
 
-void RuleFeatureSet::collectFeaturesFromSelectorList(const CSSSelectorList* selectorList, RuleFeatureSet::FeatureMetadata& metadata, InvalidationSetMode mode)
-{
-    if (!selectorList)
-        return;
-
-    for (const CSSSelector* selector = selectorList->first(); selector; selector = CSSSelectorList::next(*selector))
-        collectFeaturesFromSelector(*selector, metadata, mode);
-}
-
 void RuleFeatureSet::FeatureMetadata::add(const FeatureMetadata& other)
 {
     usesFirstLineRules = usesFirstLineRules || other.usesFirstLineRules;