Sibling 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 3a23c477d158dd555659d59e1a6e9566d449ee4f..0893074ae23d6d9a7146fea4702b88ffdb6a7679 100644
--- a/Source/core/css/RuleFeature.cpp
+++ b/Source/core/css/RuleFeature.cpp
@@ -236,14 +236,14 @@ RuleFeatureSet::~RuleFeatureSet()
 {
 }
 
-DescendantInvalidationSet* RuleFeatureSet::invalidationSetForSelector(const CSSSelector& selector)
+DescendantInvalidationSet* RuleFeatureSet::invalidationSetForSelector(const CSSSelector& selector, InvalidateType type)
 {
     if (selector.match() == CSSSelector::Class)
-        return &ensureClassInvalidationSet(selector.value());
+        return &ensureClassInvalidationSet(selector.value(), type);
     if (selector.isAttributeSelector())
-        return &ensureAttributeInvalidationSet(selector.attribute().localName());
+        return &ensureAttributeInvalidationSet(selector.attribute().localName(), type);
     if (selector.match() == CSSSelector::Id)
-        return &ensureIdInvalidationSet(selector.value());
+        return &ensureIdInvalidationSet(selector.value(), type);
     if (selector.match() == CSSSelector::PseudoClass) {
         switch (selector.pseudoType()) {
         case CSSSelector::PseudoEmpty:
@@ -263,7 +263,7 @@ DescendantInvalidationSet* RuleFeatureSet::invalidationSetForSelector(const CSSS
         case CSSSelector::PseudoInvalid:
         case CSSSelector::PseudoIndeterminate:
         case CSSSelector::PseudoTarget:
-            return &ensurePseudoInvalidationSet(selector.pseudoType());
+            return &ensurePseudoInvalidationSet(selector.pseudoType(), type);
         default:
             break;
         }
@@ -273,25 +273,27 @@ DescendantInvalidationSet* RuleFeatureSet::invalidationSetForSelector(const CSSS
 
 // 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.
+// compound selector (extractInvalidationSetFeatures).
+// 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.
+// Finally, add those features to the invalidation sets for the features found
+// in the other compound selectors (addFeaturesToInvalidationSets).
 
 void RuleFeatureSet::updateInvalidationSets(const RuleData& ruleData)
 {
     InvalidationSetFeatures features;
     auto result = extractInvalidationSetFeatures(ruleData.selector(), features, false);
-    if (result.first) {
-        features.forceSubtree = result.second == ForceSubtree;
-        addFeaturesToInvalidationSets(*result.first, features);
-    }
 
     // If any ::before and ::after rules specify 'content: attr(...)', we
     // need to create invalidation sets for those attributes.
     if (features.hasBeforeOrAfter)
         updateInvalidationSetsForContentAttribute(ruleData);
+
+    if (result.first) {
+        features.forceSubtree = result.second == ForceSubtree;
+        addFeaturesToInvalidationSets(result.first, features.adjacent ? &features : nullptr, features);
+    }
 }
 
 void RuleFeatureSet::updateInvalidationSetsForContentAttribute(const RuleData& ruleData)
@@ -315,7 +317,7 @@ void RuleFeatureSet::updateInvalidationSetsForContentAttribute(const RuleData& r
         CSSPrimitiveValue* primitiveItem = toCSSPrimitiveValue(item.get());
         if (!primitiveItem->isAttr())
             continue;
-        ensureAttributeInvalidationSet(AtomicString(primitiveItem->getStringValue()));
+        ensureAttributeInvalidationSet(AtomicString(primitiveItem->getStringValue()), InvalidateDescendants);
     }
 }
 
@@ -327,7 +329,7 @@ RuleFeatureSet::extractInvalidationSetFeatures(const CSSSelector& selector, Inva
         if (!negated)
             foundFeatures |= extractInvalidationSetFeature(*current, features);
         // Initialize the entry in the invalidation set map, if supported.
-        if (!invalidationSetForSelector(*current)) {
+        if (!invalidationSetForSelector(*current, InvalidateDescendants)) {
             if (requiresSubtreeInvalidation(*current)) {
                 // Fall back to use subtree invalidations, even for features in the
                 // rightmost compound selector. Returning the start &selector here
@@ -359,6 +361,8 @@ RuleFeatureSet::extractInvalidationSetFeatures(const CSSSelector& selector, Inva
 
         features.treeBoundaryCrossing = current->isShadowSelector();
         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);
@@ -378,11 +382,13 @@ RuleFeatureSet::extractInvalidationSetFeatures(const CSSSelector& selector, Inva
 
 void RuleFeatureSet::addFeaturesToInvalidationSet(DescendantInvalidationSet& invalidationSet, const InvalidationSetFeatures& features)
 {
+    invalidationSet.setMaxDirectAdjacentSelectors(features.maxDirectAdjacentSelectors);
+
     if (features.treeBoundaryCrossing)
         invalidationSet.setTreeBoundaryCrossing();
     if (features.insertionPointCrossing)
         invalidationSet.setInsertionPointCrossing();
-    if (features.useSubtreeInvalidation()) {
+    if (features.forceSubtree) {
         invalidationSet.setWholeSubtreeInvalid();
         return;
     }
@@ -398,20 +404,36 @@ void RuleFeatureSet::addFeaturesToInvalidationSet(DescendantInvalidationSet& inv
         invalidationSet.setCustomPseudoInvalid();
 }
 
-void RuleFeatureSet::addFeaturesToInvalidationSets(const CSSSelector& selector, InvalidationSetFeatures& features)
+// selector is the selector immediately to the left of the rightmost selector.
+// siblingFeatures is null if selector is not immediately to the left of a sibling combinator.
+// descendantFeatures has the features of the rightmost selector.
+void RuleFeatureSet::addFeaturesToInvalidationSets(const CSSSelector* selector, InvalidationSetFeatures* siblingFeatures, InvalidationSetFeatures& descendantFeatures)
 {
-    for (const CSSSelector* current = &selector; current; current = current->tagHistory()) {
-        if (DescendantInvalidationSet* invalidationSet = invalidationSetForSelector(*current)) {
-            addFeaturesToInvalidationSet(*invalidationSet, features);
+    // We set siblingFeatures to &localFeatures if we find a rightmost sibling combinator.
+    InvalidationSetFeatures localFeatures;
+
+    for (const CSSSelector* current = selector; current; current = current->tagHistory()) {
+        InvalidateType type = siblingFeatures ? InvalidateSiblings : InvalidateDescendants;
+        if (DescendantInvalidationSet* invalidationSet = invalidationSetForSelector(*current, type)) {
+            addFeaturesToInvalidationSet(*invalidationSet, siblingFeatures ? *siblingFeatures : descendantFeatures);
+
+            if (siblingFeatures && !invalidationSet->wholeSubtreeInvalid()) {
+                if (siblingFeatures == &descendantFeatures)
+                    invalidationSet->setSiblingInvalid();
+                else if (descendantFeatures.forceSubtree)
+                    invalidationSet->setWholeSubtreeInvalid();
+                else
+                    addFeaturesToInvalidationSet(invalidationSet->ensureDescendantInvalidationSet(), descendantFeatures);
+            }
         } else {
             if (current->isTreeBoundaryCrossing())
-                features.treeBoundaryCrossing = true;
+                descendantFeatures.treeBoundaryCrossing = true;
             if (current->isInsertionPointCrossing())
-                features.insertionPointCrossing = true;
+                descendantFeatures.insertionPointCrossing = true;
             if (const CSSSelectorList* selectorList = current->selectorList()) {
                 ASSERT(supportsInvalidationWithSelectorList(current->pseudoType()));
-                for (const CSSSelector* selector = selectorList->first(); selector; selector = CSSSelectorList::next(*selector))
-                    addFeaturesToInvalidationSets(*selector, features);
+                for (const CSSSelector* subSelector = selectorList->first(); subSelector; subSelector = CSSSelectorList::next(*subSelector))
+                    addFeaturesToInvalidationSets(subSelector, siblingFeatures, descendantFeatures);
             }
         }
 
@@ -419,9 +441,29 @@ void RuleFeatureSet::addFeaturesToInvalidationSets(const CSSSelector& selector,
             continue;
 
         if (current->isShadowSelector())
-            features.treeBoundaryCrossing = true;
+            descendantFeatures.treeBoundaryCrossing = true;
 
-        features.adjacent = current->isAdjacentSelector();
+        if (!current->isAdjacentSelector()) {
+            selector = current->tagHistory();
+            siblingFeatures = nullptr;
+            continue;
+        }
+
+        if (siblingFeatures) {
+            if (siblingFeatures->maxDirectAdjacentSelectors != std::numeric_limits<unsigned>::max()) {
+                if (current->relation() == CSSSelector::DirectAdjacent)
+                    siblingFeatures->maxDirectAdjacentSelectors++;
+                else
+                    siblingFeatures->maxDirectAdjacentSelectors = std::numeric_limits<unsigned>::max();
+            }
+        } else {
+            localFeatures = InvalidationSetFeatures();
+            auto result = extractInvalidationSetFeatures(*selector, localFeatures, false);
+            if (result.first)
+                localFeatures.forceSubtree = result.second == ForceSubtree;
+
+            siblingFeatures = &localFeatures;
+        }
     }
 }
 
@@ -439,38 +481,6 @@ void RuleFeatureSet::collectFeaturesFromRuleData(const RuleData& ruleData)
         uncommonAttributeRules.append(RuleFeature(ruleData.rule(), ruleData.selectorIndex(), ruleData.hasDocumentSecurityOrigin()));
 }
 
-DescendantInvalidationSet& RuleFeatureSet::ensureClassInvalidationSet(const AtomicString& className)
-{
-    InvalidationSetMap::AddResult addResult = m_classInvalidationSets.add(className, nullptr);
-    if (addResult.isNewEntry)
-        addResult.storedValue->value = DescendantInvalidationSet::create();
-    return *addResult.storedValue->value;
-}
-
-DescendantInvalidationSet& RuleFeatureSet::ensureAttributeInvalidationSet(const AtomicString& attributeName)
-{
-    InvalidationSetMap::AddResult addResult = m_attributeInvalidationSets.add(attributeName, nullptr);
-    if (addResult.isNewEntry)
-        addResult.storedValue->value = DescendantInvalidationSet::create();
-    return *addResult.storedValue->value;
-}
-
-DescendantInvalidationSet& RuleFeatureSet::ensureIdInvalidationSet(const AtomicString& id)
-{
-    InvalidationSetMap::AddResult addResult = m_idInvalidationSets.add(id, nullptr);
-    if (addResult.isNewEntry)
-        addResult.storedValue->value = DescendantInvalidationSet::create();
-    return *addResult.storedValue->value;
-}
-
-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)
 {
     unsigned maxDirectAdjacentSelectors = 0;
@@ -519,14 +529,14 @@ void RuleFeatureSet::FeatureMetadata::clear()
 
 void RuleFeatureSet::add(const RuleFeatureSet& other)
 {
-    for (const auto& invalidationSet : other.m_classInvalidationSets)
-        ensureClassInvalidationSet(invalidationSet.key).combine(*invalidationSet.value);
-    for (const auto& invalidationSet : other.m_attributeInvalidationSets)
-        ensureAttributeInvalidationSet(invalidationSet.key).combine(*invalidationSet.value);
-    for (const auto& invalidationSet : other.m_idInvalidationSets)
-        ensureIdInvalidationSet(invalidationSet.key).combine(*invalidationSet.value);
-    for (const auto& invalidationSet : other.m_pseudoInvalidationSets)
-        ensurePseudoInvalidationSet(static_cast<CSSSelector::PseudoType>(invalidationSet.key)).combine(*invalidationSet.value);
+    for (const auto& entry : other.m_classInvalidationSets)
+        ensureClassInvalidationData(entry.key).combine(*entry.value);
+    for (const auto& entry : other.m_attributeInvalidationSets)
+        ensureAttributeInvalidationData(entry.key).combine(*entry.value);
+    for (const auto& entry : other.m_idInvalidationSets)
+        ensureIdInvalidationData(entry.key).combine(*entry.value);
+    for (const auto& entry : other.m_pseudoInvalidationSets)
+        ensurePseudoInvalidationData(static_cast<CSSSelector::PseudoType>(entry.key)).combine(*entry.value);
 
     m_metadata.add(other.m_metadata);
 
@@ -544,35 +554,63 @@ void RuleFeatureSet::clear()
     m_idInvalidationSets.clear();
 }
 
-void RuleFeatureSet::collectInvalidationSetsForClass(InvalidationSetVector& invalidationSets, Element& element, const AtomicString& className) const
+void RuleFeatureSet::collectInvalidationSetsForClass(InvalidationSetVector& descendant, InvalidationSetVector& sibling, Element& element, const AtomicString& className) const
 {
-    if (RefPtrWillBeRawPtr<DescendantInvalidationSet> invalidationSet = m_classInvalidationSets.get(className)) {
-        TRACE_SCHEDULE_STYLE_INVALIDATION(element, *invalidationSet, classChange, className);
-        invalidationSets.append(invalidationSet);
+    if (RefPtrWillBeRawPtr<InvalidationData> invalidationData = m_classInvalidationSets.get(className)) {
+        if (invalidationData->descendants()) {
+            TRACE_SCHEDULE_STYLE_INVALIDATION(element, *invalidationData->descendants(), classChange, className);
+            descendant.append(invalidationData->descendants());
+        }
+        if (invalidationData->siblings()) {
+            if (element.parentElement())
+                TRACE_SCHEDULE_STYLE_INVALIDATION(*element.parentElement(), *invalidationData->siblings(), classChange, className);
+            sibling.append(invalidationData->siblings());
+        }
     }
 }
 
-void RuleFeatureSet::collectInvalidationSetsForId(InvalidationSetVector& invalidationSets, Element& element, const AtomicString& id) const
+void RuleFeatureSet::collectInvalidationSetsForId(InvalidationSetVector& descendant, InvalidationSetVector& sibling, Element& element, const AtomicString& id) const
 {
-    if (RefPtrWillBeRawPtr<DescendantInvalidationSet> invalidationSet = m_idInvalidationSets.get(id)) {
-        TRACE_SCHEDULE_STYLE_INVALIDATION(element, *invalidationSet, idChange, id);
-        invalidationSets.append(invalidationSet);
+    if (RefPtrWillBeRawPtr<InvalidationData> invalidationData = m_idInvalidationSets.get(id)) {
+        if (invalidationData->descendants()) {
+            TRACE_SCHEDULE_STYLE_INVALIDATION(element, *invalidationData->descendants(), idChange, id);
+            descendant.append(invalidationData->descendants());
+        }
+        if (invalidationData->siblings()) {
+            if (element.parentElement())
+                TRACE_SCHEDULE_STYLE_INVALIDATION(*element.parentElement(), *invalidationData->siblings(), idChange, id);
+            sibling.append(invalidationData->siblings());
+        }
     }
 }
 
-void RuleFeatureSet::collectInvalidationSetsForAttribute(InvalidationSetVector& invalidationSets, Element& element, const QualifiedName& attributeName) const
+void RuleFeatureSet::collectInvalidationSetsForAttribute(InvalidationSetVector& descendant, InvalidationSetVector& sibling, Element& element, const QualifiedName& attributeName) const
 {
-    if (RefPtrWillBeRawPtr<DescendantInvalidationSet> invalidationSet = m_attributeInvalidationSets.get(attributeName.localName())) {
-        TRACE_SCHEDULE_STYLE_INVALIDATION(element, *invalidationSet, attributeChange, attributeName);
-        invalidationSets.append(invalidationSet);
+    if (RefPtrWillBeRawPtr<InvalidationData> invalidationData = m_attributeInvalidationSets.get(attributeName.localName())) {
+        if (invalidationData->descendants()) {
+            TRACE_SCHEDULE_STYLE_INVALIDATION(element, *invalidationData->descendants(), attributeChange, attributeName);
+            descendant.append(invalidationData->descendants());
+        }
+        if (invalidationData->siblings()) {
+            if (element.parentElement())
+                TRACE_SCHEDULE_STYLE_INVALIDATION(*element.parentElement(), *invalidationData->siblings(), attributeChange, attributeName);
+            sibling.append(invalidationData->siblings());
+        }
     }
 }
 
-void RuleFeatureSet::collectInvalidationSetsForPseudoClass(InvalidationSetVector& invalidationSets, Element& element, CSSSelector::PseudoType pseudo) const
+void RuleFeatureSet::collectInvalidationSetsForPseudoClass(InvalidationSetVector& descendant, InvalidationSetVector& sibling, Element& element, CSSSelector::PseudoType pseudo) const
 {
-    if (RefPtrWillBeRawPtr<DescendantInvalidationSet> invalidationSet = m_pseudoInvalidationSets.get(pseudo)) {
-        TRACE_SCHEDULE_STYLE_INVALIDATION(element, *invalidationSet, pseudoChange, pseudo);
-        invalidationSets.append(invalidationSet);
+    if (RefPtrWillBeRawPtr<InvalidationData> invalidationData = m_pseudoInvalidationSets.get(pseudo)) {
+        if (invalidationData->descendants()) {
+            TRACE_SCHEDULE_STYLE_INVALIDATION(element, *invalidationData->descendants(), pseudoChange, pseudo);
+            descendant.append(invalidationData->descendants());
+        }
+        if (invalidationData->siblings()) {
+            if (element.parentElement())
+                TRACE_SCHEDULE_STYLE_INVALIDATION(*element.parentElement(), *invalidationData->siblings(), pseudoChange, pseudo);
+            sibling.append(invalidationData->siblings());
+        }
     }
 }