Sibling 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 220 matching lines @@
 }
 
 RuleFeatureSet::RuleFeatureSet()
 {
 }
 
 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:
         case CSSSelector::PseudoLink:
         case CSSSelector::PseudoVisited:
         case CSSSelector::PseudoAnyLink:
         case CSSSelector::PseudoAutofill:
         case CSSSelector::PseudoHover:
         case CSSSelector::PseudoFocus:
         case CSSSelector::PseudoActive:
         case CSSSelector::PseudoChecked:
         case CSSSelector::PseudoEnabled:
         case CSSSelector::PseudoDisabled:
         case CSSSelector::PseudoOptional:
         case CSSSelector::PseudoPlaceholderShown:
         case CSSSelector::PseudoRequired:
         case CSSSelector::PseudoValid:
         case CSSSelector::PseudoInvalid:
         case CSSSelector::PseudoIndeterminate:
         case CSSSelector::PseudoTarget:
-            return &ensurePseudoInvalidationSet(selector.pseudoType());
+            return &ensurePseudoInvalidationSet(selector.pseudoType(), type);
         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, 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
     // need to create invalidation sets for those attributes.
     if (features.hasBeforeOrAfter)
         updateInvalidationSetsForContentAttribute(ruleData);
 }
 
 void RuleFeatureSet::updateInvalidationSetsForContentAttribute(const RuleData& ruleData)
 {
     const StylePropertySet& propertySet = ruleData.rule()->properties();
 
     int propertyIndex = propertySet.findPropertyIndex(CSSPropertyContent);
 
     if (propertyIndex == -1)
         return;
 
     StylePropertySet::PropertyReference contentProperty = propertySet.propertyAt(propertyIndex);
     CSSValue* contentValue = contentProperty.value();
 
     if (!contentValue->isValueList())
         return;
 
     for (auto& item : toCSSValueList(*contentValue)) {
         if (!item->isFunctionValue())
             continue;
         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();
     }
 }
 
 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)
             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)) {
                 // 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);
             }
@@ skipping 13 matching lines @@
                 }
                 foundFeatures |= allSubSelectorsHaveFeatures;
             }
         }
 
         if (current->relation() == CSSSelector::SubSelector)
             continue;
 
         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);
 }
 
 // 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;
     }
     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)
         invalidationSet.addAttribute(attribute);
     if (features.customPseudoElement)
         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);
             }
         }
 
         if (current->relation() == CSSSelector::SubSelector)
             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;
+        }
     }
 }
 
 void RuleFeatureSet::collectFeaturesFromRuleData(const RuleData& ruleData)
 {
     updateInvalidationSets(ruleData);
 
     FeatureMetadata metadata;
     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()));
 }
 
-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;
 
     for (const CSSSelector* current = &selector; current; current = current->tagHistory()) {
         if (current->pseudoType() == CSSSelector::PseudoFirstLine)
             metadata.usesFirstLineRules = true;
         if (current->pseudoType() == CSSSelector::PseudoWindowInactive)
             metadata.usesWindowInactiveSelector = true;
         if (current->relation() == CSSSelector::DirectAdjacent) {
@@ skipping 28 matching lines @@
 void RuleFeatureSet::FeatureMetadata::clear()
 {
     usesFirstLineRules = false;
     usesWindowInactiveSelector = false;
     foundSiblingSelector = false;
     maxDirectAdjacentSelectors = 0;
 }
 
 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);
 
     siblingRules.appendVector(other.siblingRules);
     uncommonAttributeRules.appendVector(other.uncommonAttributeRules);
 }
 
 void RuleFeatureSet::clear()
 {
     siblingRules.clear();
     uncommonAttributeRules.clear();
     m_metadata.clear();
     m_classInvalidationSets.clear();
     m_attributeInvalidationSets.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());
+        }
     }
 }
 
 DEFINE_TRACE(RuleFeatureSet)
 {
 #if ENABLE(OILPAN)
     visitor->trace(siblingRules);
     visitor->trace(uncommonAttributeRules);
     visitor->trace(m_classInvalidationSets);
     visitor->trace(m_attributeInvalidationSets);
     visitor->trace(m_idInvalidationSets);
     visitor->trace(m_pseudoInvalidationSets);
 #endif
 }
 
 } // namespace blink