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 f89de00af3ef780abe8d90b3ac724873fc0d88cc..4c1c8a349329bc5ba631db14a827c88506d85623 100644
--- a/Source/core/css/RuleFeature.cpp
+++ b/Source/core/css/RuleFeature.cpp
@@ -238,14 +238,14 @@ RuleFeatureSet::~RuleFeatureSet()
 {
 }
 
-InvalidationSet* RuleFeatureSet::invalidationSetForSelector(const CSSSelector& selector)
+InvalidationSet* RuleFeatureSet::invalidationSetForSelector(const CSSSelector& selector, InvalidationType 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:
@@ -266,7 +266,7 @@ InvalidationSet* RuleFeatureSet::invalidationSetForSelector(const CSSSelector& s
         case CSSSelector::PseudoInvalid:
         case CSSSelector::PseudoIndeterminate:
         case CSSSelector::PseudoTarget:
-            return &ensurePseudoInvalidationSet(selector.pseudoType());
+            return &ensurePseudoInvalidationSet(selector.pseudoType(), type);
         default:
             break;
         }
@@ -286,9 +286,10 @@ 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);
+        addFeaturesToInvalidationSets(result.first, features.adjacent ? &features : nullptr, features);
     }
 
     // If any ::before and ::after rules specify 'content: attr(...)', we
@@ -318,7 +319,7 @@ void RuleFeatureSet::updateInvalidationSetsForContentAttribute(const RuleData& r
         CSSFunctionValue* functionValue = toCSSFunctionValue(item.get());
         if (functionValue->functionType() != CSSValueAttr)
             continue;
-        ensureAttributeInvalidationSet(AtomicString(toCSSPrimitiveValue(functionValue->item(0))->getStringValue())).setInvalidatesSelf();
+        ensureAttributeInvalidationSet(AtomicString(toCSSPrimitiveValue(functionValue->item(0))->getStringValue()), InvalidateDescendants).setInvalidatesSelf();
     }
 }
 
@@ -330,7 +331,7 @@ RuleFeatureSet::extractInvalidationSetFeatures(const CSSSelector& selector, Inva
         if (!negated)
             foundFeatures |= extractInvalidationSetFeature(*current, features);
         // Initialize the entry in the invalidation set map, if supported.
-        if (InvalidationSet* invalidationSet = invalidationSetForSelector(*current)) {
+        if (InvalidationSet* invalidationSet = invalidationSetForSelector(*current, InvalidateDescendants)) {
             invalidationSet->setInvalidatesSelf();
         } else {
             if (requiresSubtreeInvalidation(*current)) {
@@ -364,6 +365,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);
@@ -372,22 +375,21 @@ RuleFeatureSet::extractInvalidationSetFeatures(const CSSSelector& selector, Inva
 // 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.
+// 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 instead of calling setWholeSubtreeInvalid.
+// we start adding features to the descendant invalidation set.
 
 void RuleFeatureSet::addFeaturesToInvalidationSet(InvalidationSet& invalidationSet, const InvalidationSetFeatures& features)
 {
+    invalidationSet.updateMaxDirectAdjacentSelectors(features.maxDirectAdjacentSelectors);
+
     if (features.treeBoundaryCrossing)
         invalidationSet.setTreeBoundaryCrossing();
     if (features.insertionPointCrossing)
         invalidationSet.setInsertionPointCrossing();
-    if (features.useSubtreeInvalidation()) {
+    if (features.forceSubtree) {
         invalidationSet.setWholeSubtreeInvalid();
         return;
     }
@@ -403,20 +405,35 @@ void RuleFeatureSet::addFeaturesToInvalidationSet(InvalidationSet& invalidationS
         invalidationSet.setCustomPseudoInvalid();
 }
 
-void RuleFeatureSet::addFeaturesToInvalidationSets(const CSSSelector& selector, InvalidationSetFeatures& features)
+// selector is the selector immediately to the left of the rightmost selector.

[rune, 2015/10/02 13:17:58]

Immediately to the left of the rightmost _combinator_?

[Eric Willigers, 2015/10/14 00:25:40]

Done.

+// siblingFeatures is null if selector is not immediately to the left of a sibling combinator.
+// descendantFeatures has the features of the rightmost selector.

[rune, 2015/10/02 13:17:58]

"rightmost compound selector"

[Eric Willigers, 2015/10/14 00:25:40]

Done.

+void RuleFeatureSet::addFeaturesToInvalidationSets(const CSSSelector* selector, InvalidationSetFeatures* siblingFeatures, InvalidationSetFeatures& descendantFeatures)
 {
-    for (const CSSSelector* current = &selector; current; current = current->tagHistory()) {
-        if (InvalidationSet* 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()) {
+        InvalidationType type = siblingFeatures ? InvalidateSiblings : InvalidateDescendants;
+        if (InvalidationSet* invalidationSet = invalidationSetForSelector(*current, type)) {
+            if (siblingFeatures) {
+                addFeaturesToInvalidationSet(*invalidationSet, *siblingFeatures);
+                if (siblingFeatures == &descendantFeatures)
+                    invalidationSet->ensureDescendantInvalidationSet().setInvalidatesSelf();
+                else
+                    addFeaturesToInvalidationSet(invalidationSet->ensureDescendantInvalidationSet(), descendantFeatures);
+            } else {
+                addFeaturesToInvalidationSet(*invalidationSet, 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* subSelector = selectorList->first(); subSelector; subSelector = CSSSelectorList::next(*subSelector))
-                    addFeaturesToInvalidationSets(*subSelector, features);
+                    addFeaturesToInvalidationSets(subSelector, siblingFeatures, descendantFeatures);
             }
         }
 
@@ -424,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();

[rune, 2015/10/02 13:17:58]

This took a while for me to understand. It's used to record the start of the
previous compound selector, right? Instead of re-using the in-parameter, could
you make it a local variable naming it previousCompoundSelector,
lastCompoundSelectorInAdjacentChain, or something similar?

[Eric Willigers, 2015/10/14 00:25:40]

Done.

[Eric Willigers, 2015/10/14 00:25:40]

Yes, for example when processing ".p.q + .r.s + .t.v > .w.x + .y.z"
from right to left, we need to remember .v so that when we reach ".s +" we know
the compound selector to the right is ".t.v".

Renamed to lastCompoundSelectorInAdjacentChain.

+            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 {

[rune, 2015/10/02 13:17:58]

Could you try to get rid of some if-ery nesting here? You could use continue as
you did for the block above.

[Eric Willigers, 2015/10/14 00:25:40]

Done.

+            localFeatures = InvalidationSetFeatures();
+            auto result = extractInvalidationSetFeatures(*selector, localFeatures, false);

[rune, 2015/10/02 13:57:56]

Note: extractInvalidationSetFeatures with requiresSubtreeInvalidation were
implemented under the assumption that it was done on the rightmost compound, and
this breaks that assumption. I don't think it currently matters for all
practical purposes, but it's something to be aware of.

Currently, it matters for ::first-line, ::first-letter, and :host-context. The
two former can only appear in the rightmost compound anyway, and the latter will
never match anything if preceeded by an adjacent combinator.

[Eric Willigers, 2015/10/14 00:25:40]

Acknowledged.

+            ASSERT(result.first);
+            localFeatures.forceSubtree = result.second == ForceSubtree;
+
+            siblingFeatures = &localFeatures;
+        }
     }
 }
 
@@ -444,38 +481,6 @@ void RuleFeatureSet::collectFeaturesFromRuleData(const RuleData& ruleData)
         uncommonAttributeRules.append(RuleFeature(ruleData.rule(), ruleData.selectorIndex(), ruleData.hasDocumentSecurityOrigin()));
 }
 
-InvalidationSet& RuleFeatureSet::ensureClassInvalidationSet(const AtomicString& className)
-{
-    InvalidationSetMap::AddResult addResult = m_classInvalidationSets.add(className, nullptr);
-    if (addResult.isNewEntry)
-        addResult.storedValue->value = InvalidationSet::create();
-    return *addResult.storedValue->value;
-}
-
-InvalidationSet& RuleFeatureSet::ensureAttributeInvalidationSet(const AtomicString& attributeName)
-{
-    InvalidationSetMap::AddResult addResult = m_attributeInvalidationSets.add(attributeName, nullptr);
-    if (addResult.isNewEntry)
-        addResult.storedValue->value = InvalidationSet::create();
-    return *addResult.storedValue->value;
-}
-
-InvalidationSet& RuleFeatureSet::ensureIdInvalidationSet(const AtomicString& id)
-{
-    InvalidationSetMap::AddResult addResult = m_idInvalidationSets.add(id, nullptr);
-    if (addResult.isNewEntry)
-        addResult.storedValue->value = InvalidationSet::create();
-    return *addResult.storedValue->value;
-}
-
-InvalidationSet& RuleFeatureSet::ensurePseudoInvalidationSet(CSSSelector::PseudoType pseudoType)
-{
-    PseudoTypeInvalidationSetMap::AddResult addResult = m_pseudoInvalidationSets.add(pseudoType, nullptr);
-    if (addResult.isNewEntry)
-        addResult.storedValue->value = InvalidationSet::create();
-    return *addResult.storedValue->value;
-}
-
 void RuleFeatureSet::collectFeaturesFromSelector(const CSSSelector& selector, RuleFeatureSet::FeatureMetadata& metadata)
 {
     unsigned maxDirectAdjacentSelectors = 0;
@@ -524,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);
 
@@ -549,35 +554,63 @@ void RuleFeatureSet::clear()
     m_idInvalidationSets.clear();
 }
 
-void RuleFeatureSet::collectInvalidationSetsForClass(InvalidationSetVector& invalidationSets, Element& element, const AtomicString& className) const
+void RuleFeatureSet::collectInvalidationSetsForClass(InvalidationLists& invalidationLists, Element& element, const AtomicString& className) const
 {
-    if (RefPtrWillBeRawPtr<InvalidationSet> 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);
+            invalidationLists.descendants.append(invalidationData->descendants());
+        }
+        if (invalidationData->siblings()) {
+            if (element.parentElement())
+                TRACE_SCHEDULE_STYLE_INVALIDATION(*element.parentElement(), *invalidationData->siblings(), classChange, className);
+            invalidationLists.siblings.append(invalidationData->siblings());
+        }
     }
 }
 
-void RuleFeatureSet::collectInvalidationSetsForId(InvalidationSetVector& invalidationSets, Element& element, const AtomicString& id) const
+void RuleFeatureSet::collectInvalidationSetsForId(InvalidationLists& invalidationLists, Element& element, const AtomicString& id) const
 {
-    if (RefPtrWillBeRawPtr<InvalidationSet> 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);
+            invalidationLists.descendants.append(invalidationData->descendants());
+        }
+        if (invalidationData->siblings()) {
+            if (element.parentElement())
+                TRACE_SCHEDULE_STYLE_INVALIDATION(*element.parentElement(), *invalidationData->siblings(), idChange, id);
+            invalidationLists.siblings.append(invalidationData->siblings());
+        }
     }
 }
 
-void RuleFeatureSet::collectInvalidationSetsForAttribute(InvalidationSetVector& invalidationSets, Element& element, const QualifiedName& attributeName) const
+void RuleFeatureSet::collectInvalidationSetsForAttribute(InvalidationLists& invalidationLists, Element& element, const QualifiedName& attributeName) const
 {
-    if (RefPtrWillBeRawPtr<InvalidationSet> 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);
+            invalidationLists.descendants.append(invalidationData->descendants());
+        }
+        if (invalidationData->siblings()) {
+            if (element.parentElement())
+                TRACE_SCHEDULE_STYLE_INVALIDATION(*element.parentElement(), *invalidationData->siblings(), attributeChange, attributeName);
+            invalidationLists.siblings.append(invalidationData->siblings());
+        }
     }
 }
 
-void RuleFeatureSet::collectInvalidationSetsForPseudoClass(InvalidationSetVector& invalidationSets, Element& element, CSSSelector::PseudoType pseudo) const
+void RuleFeatureSet::collectInvalidationSetsForPseudoClass(InvalidationLists& invalidationLists, Element& element, CSSSelector::PseudoType pseudo) const
 {
-    if (RefPtrWillBeRawPtr<InvalidationSet> 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);
+            invalidationLists.descendants.append(invalidationData->descendants());
+        }
+        if (invalidationData->siblings()) {
+            if (element.parentElement())
+                TRACE_SCHEDULE_STYLE_INVALIDATION(*element.parentElement(), *invalidationData->siblings(), pseudoChange, pseudo);
+            invalidationLists.siblings.append(invalidationData->siblings());
+        }
     }
 }