Single code path for updating invalidation sets.

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 145 matching lines @@
         // These should not appear in StyleRule selectors.
         ASSERT_NOT_REACHED();
         return false;
     default:
         // New pseudo type added. Figure out if it needs a subtree invalidation or not.
         ASSERT_NOT_REACHED();
         return false;
     }
 }
 
+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)
 {
     if (!selector.matchesPseudoElement() && selector.match() != CSSSelector::PseudoClass) {
         ASSERT(supportsInvalidation(selector.match()));
         return false;
     }
 
     switch (selector.pseudoType()) {
@@ skipping 17 matching lines @@
     , selectorIndex(selectorIndex)
     , hasDocumentSecurityOrigin(hasDocumentSecurityOrigin)
 {
 }
 
 void RuleFeature::trace(Visitor* visitor)
 {
     visitor->trace(rule);
 }
 
-static bool supportsInvalidationWithSelectorList(CSSSelector::PseudoType pseudo)
+bool RuleFeatureSet::extractInvalidationSetFeature(const CSSSelector& selector, InvalidationSetFeatures& features)
 {
-    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 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();
     else if (selector.match() == CSSSelector::Class)
         features.classes.append(selector.value());
     else if (selector.isAttributeSelector())
         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()
 {
 }
 
 RuleFeatureSet::~RuleFeatureSet()
 {
 }
 
@@ skipping 21 matching lines @@
         case CSSSelector::PseudoRequired:
         case CSSSelector::PseudoValid:
         case CSSSelector::PseudoInvalid:
         case CSSSelector::PseudoIndeterminate:
         case CSSSelector::PseudoTarget:
             return &ensurePseudoInvalidationSet(selector.pseudoType());
         default:
             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;
             }
         }
 
         if (current->relation() == CSSSelector::SubSelector)
             continue;
 
         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
 // sets for features found in other compound selectors.
 //
 // Style invalidation is currently supported for descendants only, not for sibling subtrees.
 // We use wholeSubtree invalidation for features found left of adjacent combinators as
 // SubtreeStyleChange will force sibling subtree recalc in
 // ContainerNode::checkForChildrenAdjacentRuleChanges.
 //
 // 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 instead of calling setWholeSubtreeInvalid.
 
 void RuleFeatureSet::addFeaturesToInvalidationSet(DescendantInvalidationSet& invalidationSet, const InvalidationSetFeatures& features)
 {
     if (features.treeBoundaryCrossing)
         invalidationSet.setTreeBoundaryCrossing();
     if (features.insertionPointCrossing)
         invalidationSet.setInsertionPointCrossing();
-    if (features.adjacent) {
+    if (features.useSubtreeInvalidation()) {
         invalidationSet.setWholeSubtreeInvalid();
         return;
     }
     if (!features.id.isEmpty())
         invalidationSet.addId(features.id);
     if (!features.tagName.isEmpty())
         invalidationSet.addTagName(features.tagName);
     for (const auto& className : features.classes)
         invalidationSet.addClass(className);
     for (const auto& attribute : features.attributes)
@@ skipping 29 matching lines @@
     }
 }
 
 void RuleFeatureSet::addContentAttr(const AtomicString& attributeName)
 {
     ensureAttributeInvalidationSet(attributeName);
 }
 
 void RuleFeatureSet::collectFeaturesFromRuleData(const RuleData& ruleData)
 {
+    updateInvalidationSets(ruleData.selector());
+
     FeatureMetadata metadata;
-    InvalidationSetMode mode = updateInvalidationSets(ruleData.selector());
-
-    collectFeaturesFromSelector(ruleData.selector(), metadata, mode);
+    collectFeaturesFromSelector(ruleData.selector(), metadata);
     m_metadata.add(metadata);
 
     if (metadata.foundSiblingSelector)
         siblingRules.append(RuleFeature(ruleData.rule(), ruleData.selectorIndex(), ruleData.hasDocumentSecurityOrigin()));
     if (ruleData.containsUncommonAttributeSelector())
         uncommonAttributeRules.append(RuleFeature(ruleData.rule(), ruleData.selectorIndex(), ruleData.hasDocumentSecurityOrigin()));
 }
 
 DescendantInvalidationSet& RuleFeatureSet::ensureClassInvalidationSet(const AtomicString& className)
 {
@@ skipping 20 matching lines @@
 }
 
 DescendantInvalidationSet& RuleFeatureSet::ensurePseudoInvalidationSet(CSSSelector::PseudoType pseudoType)
 {
     PseudoTypeInvalidationSetMap::AddResult addResult = m_pseudoInvalidationSets.add(pseudoType, nullptr);
     if (addResult.isNewEntry)
         addResult.storedValue->value = DescendantInvalidationSet::create();
     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()) {
             maxDirectAdjacentSelectors++;
         } else if (maxDirectAdjacentSelectors) {
             if (maxDirectAdjacentSelectors > metadata.maxDirectAdjacentSelectors)
                 metadata.maxDirectAdjacentSelectors = maxDirectAdjacentSelectors;
             maxDirectAdjacentSelectors = 0;
         }
         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;
     maxDirectAdjacentSelectors = std::max(maxDirectAdjacentSelectors, other.maxDirectAdjacentSelectors);
 }
 
 void RuleFeatureSet::FeatureMetadata::clear()
 {
     usesFirstLineRules = false;
     foundSiblingSelector = false;
@@ skipping 126 matching lines @@
     visitor->trace(uncommonAttributeRules);
     visitor->trace(m_classInvalidationSets);
     visitor->trace(m_attributeInvalidationSets);
     visitor->trace(m_idInvalidationSets);
     visitor->trace(m_pseudoInvalidationSets);
     visitor->trace(m_styleInvalidator);
 #endif
 }
 
 } // namespace blink