Use invalidation sets for nth invalidations.

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 333 matching lines @@
         case CSSSelector::PseudoIndeterminate:
         case CSSSelector::PseudoTarget:
         case CSSSelector::PseudoLang:
         case CSSSelector::PseudoFullScreen:
         case CSSSelector::PseudoFullScreenAncestor:
         case CSSSelector::PseudoInRange:
         case CSSSelector::PseudoOutOfRange:
         case CSSSelector::PseudoUnresolved:
         case CSSSelector::PseudoDefined:
             return &ensurePseudoInvalidationSet(selector.getPseudoType(), type);
+        case CSSSelector::PseudoFirstOfType:
+        case CSSSelector::PseudoLastOfType:
+        case CSSSelector::PseudoOnlyOfType:
+        case CSSSelector::PseudoNthChild:
+        case CSSSelector::PseudoNthOfType:
+        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)
 {
     InvalidationSetFeatures features;
     auto result = extractInvalidationSetFeatures(ruleData.selector(), features, Subject);
 
+    features.forceSubtree = result.second == ForceSubtree;
     if (result.first) {
-        features.forceSubtree = result.second == ForceSubtree;
         addFeaturesToInvalidationSets(result.first, features.adjacent ? &features : nullptr, features);
+    } else if (features.hasNthPseudo) {
+        DCHECK(m_nthInvalidationSet);
+        addFeaturesToInvalidationSet(*m_nthInvalidationSet, features);
     }
 
     // If any ::before and ::after rules specify 'content: attr(...)', we
     // need to create invalidation sets for those attributes.
     if (features.hasBeforeOrAfter)
         updateInvalidationSetsForContentAttribute(ruleData);
 }
 
 void RuleFeatureSet::updateInvalidationSetsForContentAttribute(const RuleData& ruleData)
 {
@@ skipping 22 matching lines @@
 
 std::pair<const CSSSelector*, RuleFeatureSet::UseFeaturesType>
 RuleFeatureSet::extractInvalidationSetFeatures(const CSSSelector& selector, InvalidationSetFeatures& features, PositionType position, CSSSelector::PseudoType pseudo)
 {
     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)
-                invalidationSet->setInvalidatesSelf();
+            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()) {
@@ skipping 14 matching lines @@
                     }
                     allSubSelectorsHaveFeatures &= result.second == UseFeatures;
                 }
                 foundFeatures |= allSubSelectorsHaveFeatures;
             }
         }
 
         if (current->relation() == CSSSelector::SubSelector)
             continue;
 
+        if (features.hasNthPseudo && position == Subject) {
+            DCHECK(m_nthInvalidationSet);
+            addFeaturesToInvalidationSet(*m_nthInvalidationSet, features);
+            if (!foundFeatures)
+                m_nthInvalidationSet->setWholeSubtreeInvalid();

[esprehn, 2016/08/11 10:32:55]

If we're going to mark it for the whole subtree why bother doing
addFeaturesToInvalidationSet?

I have to admit this foundFeatures flag is very confusing since the function
returns false in some cases that seem like they found features:
https://cs.chromium.org/chromium/src/third_party/WebKit/Source/core/css/RuleF...

why do all the other cases return true but ::before/::after return false? I
maybe that needs a comment?

I also wonder if foundFeatures should be a computed getter on the features
object instead that's like

bool hasFoo() const {
  return !m_foo.isEmpty() || !m_bar.isEmpty() || ...;
}

and then add a comment about it instead of this |= dance.

[rune, 2016/08/12 11:03:14]

Will fix.
I'll comment. It's because ::before/::after are not invalidation set features,
but flags used to later create invalidation sets for attributes in content
properties: "content: attr(x)".

It would be less confusing is that was part of collectFeaturesFromSelector(),
yet that method is confusing in itself. We have two passes over the selectors.
One for invalidation sets and one for a few other flags. I've thought about
making it a single pass, but then it would be even more code into the extract..
and addFeaturesTo... methods.
It's done like that because of the recursiveness for :-webkit-any. We pass the
same InvalidationSetFeatures to all sub-selectors and aggregate the features,
but we need to know if any of the sub-selectors were universal in the sense that
they didn't have any features. E.g.:

  #x  :-webkit-any(.a, *) {}

Extracting features from the first sub-selector adds ".a", but since we didn't
find any features in "*", we need to do a subtree recalc for #x changes.

The alternative is to use a separate InvalidationSetFeatures object for each
sub-selectors and aggregate them after we've set the wholeSubtreeInvalid flag
for the sub-selector.

+        }
+
         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 std::make_pair(nullptr, foundFeatures ? UseFeatures : ForceSubtree);
 }
 
 // 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 33 matching lines @@
     // We set siblingFeatures to &localFeatures if we find a rightmost sibling combinator.
     InvalidationSetFeatures localFeatures;
 
     bool universalCompound = true;
 
     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) {
+            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);
@@ skipping 161 matching lines @@
     for (const auto& entry : other.m_classInvalidationSets)
         ensureInvalidationSet(m_classInvalidationSets, entry.key, entry.value->type()).combine(*entry.value);
     for (const auto& entry : other.m_attributeInvalidationSets)
         ensureInvalidationSet(m_attributeInvalidationSets, entry.key, entry.value->type()).combine(*entry.value);
     for (const auto& entry : other.m_idInvalidationSets)
         ensureInvalidationSet(m_idInvalidationSets, entry.key, entry.value->type()).combine(*entry.value);
     for (const auto& entry : other.m_pseudoInvalidationSets)
         ensureInvalidationSet(m_pseudoInvalidationSets, static_cast<CSSSelector::PseudoType>(entry.key), entry.value->type()).combine(*entry.value);
     if (other.m_universalSiblingInvalidationSet)
         ensureUniversalSiblingInvalidationSet().combine(*other.m_universalSiblingInvalidationSet);
+    if (other.m_nthInvalidationSet)
+        ensureNthInvalidationSet().combine(*other.m_nthInvalidationSet);
 
     m_metadata.add(other.m_metadata);
 
     siblingRules.appendVector(other.siblingRules);
     uncommonAttributeRules.appendVector(other.uncommonAttributeRules);
 }
 
 void RuleFeatureSet::clear()
 {
     siblingRules.clear();
@@ skipping 149 matching lines @@
         invalidationLists.siblings.append(m_universalSiblingInvalidationSet);
 }
 
 SiblingInvalidationSet& RuleFeatureSet::ensureUniversalSiblingInvalidationSet()
 {
     if (!m_universalSiblingInvalidationSet)
         m_universalSiblingInvalidationSet = SiblingInvalidationSet::create(nullptr);
     return *m_universalSiblingInvalidationSet;
 }
 
+void RuleFeatureSet::collectNthInvalidationSet(InvalidationLists& invalidationLists) const
+{
+    if (m_nthInvalidationSet)
+        invalidationLists.descendants.append(m_nthInvalidationSet);
+}
+
+DescendantInvalidationSet& RuleFeatureSet::ensureNthInvalidationSet()
+{
+    if (!m_nthInvalidationSet)
+        m_nthInvalidationSet = DescendantInvalidationSet::create();
+    return *m_nthInvalidationSet;
+}
+
 void RuleFeatureSet::addFeaturesToUniversalSiblingInvalidationSet(const InvalidationSetFeatures& siblingFeatures, const InvalidationSetFeatures& descendantFeatures)
 {
     SiblingInvalidationSet& universalSet = ensureUniversalSiblingInvalidationSet();
     addFeaturesToInvalidationSet(universalSet, siblingFeatures);
     universalSet.updateMaxDirectAdjacentSelectors(siblingFeatures.maxDirectAdjacentSelectors);
 
     if (&siblingFeatures == &descendantFeatures)
         universalSet.setInvalidatesSelf();
     else
         addFeaturesToInvalidationSet(universalSet.ensureSiblingDescendants(), descendantFeatures);
 }
 
 DEFINE_TRACE(RuleFeatureSet)
 {
     visitor->trace(siblingRules);
     visitor->trace(uncommonAttributeRules);
 }
 
 } // namespace blink