Schedule sibling invalidation sets for sibling insert/remove.

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 488 matching lines @@
 // selector is the selector immediately to the left of the rightmost combinator.
 // siblingFeatures is null if selector is not immediately to the left of a sibling combinator.
 // descendantFeatures has the features of the rightmost compound selector.
 void RuleFeatureSet::addFeaturesToInvalidationSets(const CSSSelector* selector, InvalidationSetFeatures* siblingFeatures, InvalidationSetFeatures& descendantFeatures)
 {
     const CSSSelector* lastCompoundSelectorInAdjacentChain = selector;
 
     // 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) {
                 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);
             }
         } else {
             if (current->isHostPseudoClass())
                 descendantFeatures.treeBoundaryCrossing = true;
             if (current->isInsertionPointCrossing())
                 descendantFeatures.insertionPointCrossing = true;
             if (const CSSSelectorList* selectorList = current->selectorList()) {
                 ASSERT(supportsInvalidationWithSelectorList(current->getPseudoType()));
                 for (const CSSSelector* subSelector = selectorList->first(); subSelector; subSelector = CSSSelectorList::next(*subSelector))
                     addFeaturesToInvalidationSets(subSelector, siblingFeatures, descendantFeatures);
             }
         }
 
         if (current->relation() == CSSSelector::SubSelector)
             continue;
 
+        if (universalCompound && siblingFeatures)
+            addFeaturesToUniversalSiblingInvalidationSet(*siblingFeatures, descendantFeatures);
+        universalCompound = true;
+
         if (current->relationIsAffectedByPseudoContent() || current->relation() == CSSSelector::ShadowSlot) {
             descendantFeatures.insertionPointCrossing = true;
             descendantFeatures.contentPseudoCrossing = true;
         }
         if (current->isShadowSelector())
             descendantFeatures.treeBoundaryCrossing = true;
         if (!current->isAdjacentSelector()) {
             lastCompoundSelectorInAdjacentChain = current->tagHistory();
             siblingFeatures = nullptr;
             continue;
         }
 
         if (siblingFeatures) {
             if (siblingFeatures->maxDirectAdjacentSelectors == UINT_MAX)
                 continue;
 
             if (current->relation() == CSSSelector::DirectAdjacent)
                 siblingFeatures->maxDirectAdjacentSelectors++;
             else
                 siblingFeatures->maxDirectAdjacentSelectors = UINT_MAX;
             continue;
         }
 
         localFeatures = InvalidationSetFeatures();
         auto result = extractInvalidationSetFeatures(*lastCompoundSelectorInAdjacentChain, localFeatures, Ancestor);
         ASSERT(result.first);
         localFeatures.forceSubtree = result.second == ForceSubtree;
         siblingFeatures = &localFeatures;
     }
+
+    if (universalCompound && siblingFeatures)
+        addFeaturesToUniversalSiblingInvalidationSet(*siblingFeatures, descendantFeatures);
 }
 
 RuleFeatureSet::SelectorPreMatch RuleFeatureSet::collectFeaturesFromRuleData(const RuleData& ruleData)
 {
     FeatureMetadata metadata;
     if (collectFeaturesFromSelector(ruleData.selector(), metadata) == SelectorNeverMatches)
         return SelectorNeverMatches;
 
     m_metadata.add(metadata);
 
@@ skipping 97 matching lines @@
 void RuleFeatureSet::add(const RuleFeatureSet& other)
 {
     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);
 
     m_metadata.add(other.m_metadata);
 
     siblingRules.appendVector(other.siblingRules);
     uncommonAttributeRules.appendVector(other.uncommonAttributeRules);
 }
 
 void RuleFeatureSet::clear()
 {
     siblingRules.clear();
@@ skipping 19 matching lines @@
         TRACE_SCHEDULE_STYLE_INVALIDATION(element, *descendants, classChange, className);
         invalidationLists.descendants.append(descendants);
     }
 
     if (siblings) {
         TRACE_SCHEDULE_STYLE_INVALIDATION(element, *siblings, classChange, className);
         invalidationLists.siblings.append(siblings);
     }
 }
 
+void RuleFeatureSet::collectSiblingInvalidationSetForClass(InvalidationLists& invalidationLists, Element& element, const AtomicString& className, unsigned minDirectAdjacent) const
+{
+    InvalidationSetMap::const_iterator it = m_classInvalidationSets.find(className);
+    if (it == m_classInvalidationSets.end())
+        return;
+
+    InvalidationSet* invalidationSet = it->value.get();
+    if (invalidationSet->type() == InvalidateDescendants)
+        return;
+
+    SiblingInvalidationSet* siblingSet = toSiblingInvalidationSet(invalidationSet);
+    if (siblingSet->maxDirectAdjacentSelectors() < minDirectAdjacent)
+        return;
+
+    TRACE_SCHEDULE_STYLE_INVALIDATION(element, *siblingSet, classChange, className);
+    invalidationLists.siblings.append(siblingSet);
+}
+
 void RuleFeatureSet::collectInvalidationSetsForId(InvalidationLists& invalidationLists, Element& element, const AtomicString& id) const
 {
     InvalidationSetMap::const_iterator it = m_idInvalidationSets.find(id);
     if (it == m_idInvalidationSets.end())
         return;
 
     DescendantInvalidationSet* descendants;
     SiblingInvalidationSet* siblings;
     extractInvalidationSets(it->value.get(), descendants, siblings);
 
     if (descendants) {
         TRACE_SCHEDULE_STYLE_INVALIDATION(element, *descendants, idChange, id);
         invalidationLists.descendants.append(descendants);
     }
 
     if (siblings) {
         TRACE_SCHEDULE_STYLE_INVALIDATION(element, *siblings, idChange, id);
         invalidationLists.siblings.append(siblings);
     }
 }
 
+void RuleFeatureSet::collectSiblingInvalidationSetForId(InvalidationLists& invalidationLists, Element& element, const AtomicString& id, unsigned minDirectAdjacent) const
+{
+    InvalidationSetMap::const_iterator it = m_idInvalidationSets.find(id);
+    if (it == m_idInvalidationSets.end())
+        return;
+
+    InvalidationSet* invalidationSet = it->value.get();
+    if (invalidationSet->type() == InvalidateDescendants)
+        return;
+
+    SiblingInvalidationSet* siblingSet = toSiblingInvalidationSet(invalidationSet);
+    if (siblingSet->maxDirectAdjacentSelectors() < minDirectAdjacent)
+        return;
+
+    TRACE_SCHEDULE_STYLE_INVALIDATION(element, *siblingSet, idChange, id);
+    invalidationLists.siblings.append(siblingSet);
+}
+
 void RuleFeatureSet::collectInvalidationSetsForAttribute(InvalidationLists& invalidationLists, Element& element, const QualifiedName& attributeName) const
 {
     InvalidationSetMap::const_iterator it = m_attributeInvalidationSets.find(attributeName.localName());
     if (it == m_attributeInvalidationSets.end())
         return;
 
     DescendantInvalidationSet* descendants;
     SiblingInvalidationSet* siblings;
     extractInvalidationSets(it->value.get(), descendants, siblings);
 
     if (descendants) {
         TRACE_SCHEDULE_STYLE_INVALIDATION(element, *descendants, attributeChange, attributeName);
         invalidationLists.descendants.append(descendants);
     }
 
     if (siblings) {
         TRACE_SCHEDULE_STYLE_INVALIDATION(element, *siblings, attributeChange, attributeName);
         invalidationLists.siblings.append(siblings);
     }
 }
 
+void RuleFeatureSet::collectSiblingInvalidationSetForAttribute(InvalidationLists& invalidationLists, Element& element, const QualifiedName& attributeName, unsigned minDirectAdjacent) const
+{
+    InvalidationSetMap::const_iterator it = m_attributeInvalidationSets.find(attributeName.localName());
+    if (it == m_attributeInvalidationSets.end())
+        return;
+
+    InvalidationSet* invalidationSet = it->value.get();
+    if (invalidationSet->type() == InvalidateDescendants)
+        return;
+
+    SiblingInvalidationSet* siblingSet = toSiblingInvalidationSet(invalidationSet);
+    if (siblingSet->maxDirectAdjacentSelectors() < minDirectAdjacent)

[esprehn, 2016/06/25 01:54:07]

Can you explain why we can skip collecting the set if it's
maxDirectAdjacentSelectors value is less than the min you passed in?

[rune, 2016/06/25 11:06:34]

The min that is passed in is the distance from the element we are collecting
sibling invalidation sets for to the first element that may need invalidation.
If the max number of combinators for the invalidation set is less than this
distance, it will never reach the elements which may need invalidation.

Ex:

Selectors:

  .x ~ .b {}
  .a + .b { color: green }

Siblings:

A.a X.x Y B.b

Now, if we remove the Y element, we walk all previous siblings due to the first
(indirect adjacent) selector affecting one of the siblings. When we reach A, we
try to collect the sibling invalidation set for ".a", but that set has a max
direct adjacent count of 1. Since the min distance is > 1 in order to reach B,
we don't have to schedule the set for ".a".

[esprehn, 2016/06/29 04:52:08]

Interesting, I wonder if we should do that in a separate patch as an
optimization.

[rune, 2016/06/29 07:44:21]

Yeah. I didn't add any tests for that either, so I'll split it out as a separate
CL.

[rune, 2016/06/29 08:26:06]

Done.

+        return;
+
+    TRACE_SCHEDULE_STYLE_INVALIDATION(element, *siblingSet, attributeChange, attributeName);
+    invalidationLists.siblings.append(siblingSet);
+}
+
 void RuleFeatureSet::collectInvalidationSetsForPseudoClass(InvalidationLists& invalidationLists, Element& element, CSSSelector::PseudoType pseudo) const
 {
     PseudoTypeInvalidationSetMap::const_iterator it = m_pseudoInvalidationSets.find(pseudo);
     if (it == m_pseudoInvalidationSets.end())
         return;
 
     DescendantInvalidationSet* descendants;
     SiblingInvalidationSet* siblings;
     extractInvalidationSets(it->value.get(), descendants, siblings);
 
     if (descendants) {
         TRACE_SCHEDULE_STYLE_INVALIDATION(element, *descendants, pseudoChange, pseudo);
         invalidationLists.descendants.append(descendants);
     }
 
     if (siblings) {
         TRACE_SCHEDULE_STYLE_INVALIDATION(element, *siblings, pseudoChange, pseudo);
         invalidationLists.siblings.append(siblings);
     }
 }
 
+void RuleFeatureSet::collectUniversalSiblingInvalidationSet(InvalidationLists& invalidationLists, unsigned minDirectAdjacent) const
+{
+    if (m_universalSiblingInvalidationSet && m_universalSiblingInvalidationSet->maxDirectAdjacentSelectors() >= minDirectAdjacent)
+        invalidationLists.siblings.append(m_universalSiblingInvalidationSet);
+}
+
+SiblingInvalidationSet& RuleFeatureSet::ensureUniversalSiblingInvalidationSet()
+{
+    if (!m_universalSiblingInvalidationSet)
+        m_universalSiblingInvalidationSet = SiblingInvalidationSet::create(nullptr);
+    return *m_universalSiblingInvalidationSet;
+}
+
+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