Sibling invalidation sets

Source/core/css/invalidation/StyleInvalidator.cpp

Index: Source/core/css/invalidation/StyleInvalidator.cpp
diff --git a/Source/core/css/invalidation/StyleInvalidator.cpp b/Source/core/css/invalidation/StyleInvalidator.cpp
index ddc28c70b6e8607355a4e9245bac2d1f5bca3d2d..17eb3b364593c945267e7176e877ba5c7aa0ab04 100644
--- a/Source/core/css/invalidation/StyleInvalidator.cpp
+++ b/Source/core/css/invalidation/StyleInvalidator.cpp
@@ -7,7 +7,7 @@
 
 #include "core/css/invalidation/StyleInvalidator.h"
 
-#include "core/css/invalidation/DescendantInvalidationSet.h"
+#include "core/css/invalidation/InvalidationSet.h"
 #include "core/dom/Document.h"
 #include "core/dom/Element.h"
 #include "core/dom/ElementTraversal.h"
@@ -23,7 +23,7 @@ namespace blink {
 // invalidate methods.
 // To minimize performance impact, we wrap trace events with a lookup of
 // cached flag. The cached flag is made "static const" and is not shared
-// with DescendantInvalidationSet to avoid additional GOT lookup cost.
+// with InvalidationSet to avoid additional GOT lookup cost.
 static const unsigned char* s_tracingEnabled = nullptr;
 
 #define TRACE_STYLE_INVALIDATOR_INVALIDATION_IF_ENABLED(element, reason) \
@@ -33,39 +33,52 @@ static const unsigned char* s_tracingEnabled = nullptr;
 void StyleInvalidator::invalidate(Document& document)
 {
     RecursionData recursionData;
+    SiblingData siblingData;
     if (Element* documentElement = document.documentElement())
-        invalidate(*documentElement, recursionData);
+        invalidate(*documentElement, recursionData, siblingData);
     document.clearChildNeedsStyleInvalidation();
     document.clearNeedsStyleInvalidation();
     clearPendingInvalidations();
 }
 
-void StyleInvalidator::scheduleInvalidation(PassRefPtrWillBeRawPtr<DescendantInvalidationSet> invalidationSet, Element& element)
+void StyleInvalidator::scheduleInvalidationSetsForElement(const InvalidationSetVector& descendant, const InvalidationSetVector& sibling, Element& element)
 {
     ASSERT(element.inActiveDocument());
-    if (element.styleChangeType() >= SubtreeStyleChange)
-        return;
-    if (invalidationSet->wholeSubtreeInvalid()) {
-        element.setNeedsStyleRecalc(SubtreeStyleChange, StyleChangeReasonForTracing::create(StyleChangeReason::StyleInvalidator));
-        clearInvalidation(element);
-        return;
+
+    bool requiresDescendantInvalidation = false;
+    if (element.styleChangeType() < SubtreeStyleChange) {
+        for (auto& invalidationSet : descendant) {
+            if (invalidationSet->wholeSubtreeInvalid()) {
+                element.setNeedsStyleRecalc(SubtreeStyleChange, StyleChangeReasonForTracing::create(StyleChangeReason::StyleInvalidator));
+                requiresDescendantInvalidation = false;
+                break;

[Timothy Loh, 2015/09/10 06:09:40]

this could possibly still be an early return, as well as the >= Subtree check
above

[Eric Willigers, 2015/09/14 07:20:24]

Done.

+            }
+
+            ASSERT(invalidationSet->appliesDirectly() || !invalidationSet->isEmpty());
+            if (invalidationSet->appliesDirectly())
+                element.setNeedsStyleRecalc(LocalStyleChange, StyleChangeReasonForTracing::create(StyleChangeReason::StyleInvalidator));
+            if (!invalidationSet->isEmpty())
+                requiresDescendantInvalidation = true;
+        }
     }
-    if (invalidationSet->isEmpty()) {
-        element.setNeedsStyleRecalc(LocalStyleChange, StyleChangeReasonForTracing::create(StyleChangeReason::StyleInvalidator));
+
+    if (sibling.isEmpty() && !requiresDescendantInvalidation)
         return;
-    }
 
-    InvalidationList& list = ensurePendingInvalidationList(element);
-    list.append(invalidationSet);
     element.setNeedsStyleInvalidation();
-}
+    InvalidationListData& listData = ensurePendingInvalidationListData(element);
 
-StyleInvalidator::InvalidationList& StyleInvalidator::ensurePendingInvalidationList(Element& element)
-{
-    PendingInvalidationMap::AddResult addResult = m_pendingInvalidationMap.add(&element, nullptr);
-    if (addResult.isNewEntry)
-        addResult.storedValue->value = adoptPtrWillBeNoop(new InvalidationList);
-    return *addResult.storedValue->value;
+    for (auto& invalidationSet : sibling)
+        listData.siblings().append(invalidationSet);
+
+    if (!requiresDescendantInvalidation)
+        return;
+
+    for (auto& invalidationSet : descendant) {
+        ASSERT(!invalidationSet->wholeSubtreeInvalid());
+        if (!invalidationSet->isEmpty())
+            listData.descendants().append(invalidationSet);
+    }
 }
 
 void StyleInvalidator::clearInvalidation(Element& element)
@@ -76,6 +89,14 @@ void StyleInvalidator::clearInvalidation(Element& element)
     element.clearNeedsStyleInvalidation();
 }
 
+InvalidationListData& StyleInvalidator::ensurePendingInvalidationListData(Element& element)
+{
+    PendingInvalidationMap::AddResult addResult = m_pendingInvalidationMap.add(&element, nullptr);
+    if (addResult.isNewEntry)
+        addResult.storedValue->value = InvalidationListData::create();
+    return *addResult.storedValue->value;
+}
+
 void StyleInvalidator::clearPendingInvalidations()
 {
     m_pendingInvalidationMap.clear();
@@ -84,14 +105,14 @@ void StyleInvalidator::clearPendingInvalidations()
 StyleInvalidator::StyleInvalidator()
 {
     s_tracingEnabled = TRACE_EVENT_API_GET_CATEGORY_ENABLED(TRACE_DISABLED_BY_DEFAULT("devtools.timeline.invalidationTracking"));
-    DescendantInvalidationSet::cacheTracingFlag();
+    InvalidationSet::cacheTracingFlag();
 }
 
 StyleInvalidator::~StyleInvalidator()
 {
 }
 
-void StyleInvalidator::RecursionData::pushInvalidationSet(const DescendantInvalidationSet& invalidationSet)
+void StyleInvalidator::RecursionData::pushInvalidationSet(const InvalidationSet& invalidationSet)
 {
     ASSERT(!m_wholeSubtreeInvalid);
     ASSERT(!invalidationSet.wholeSubtreeInvalid());
@@ -104,7 +125,7 @@ void StyleInvalidator::RecursionData::pushInvalidationSet(const DescendantInvali
     m_invalidateCustomPseudo = invalidationSet.customPseudoInvalid();
 }
 
-ALWAYS_INLINE bool StyleInvalidator::RecursionData::matchesCurrentInvalidationSets(Element& element)
+ALWAYS_INLINE bool StyleInvalidator::RecursionData::matchesCurrentInvalidationSets(Element& element) const
 {
     if (m_invalidateCustomPseudo && element.shadowPseudoId() != nullAtom) {
         TRACE_STYLE_INVALIDATOR_INVALIDATION_IF_ENABLED(element, InvalidateCustomPseudo);
@@ -122,54 +143,115 @@ ALWAYS_INLINE bool StyleInvalidator::RecursionData::matchesCurrentInvalidationSe
     return false;
 }
 
-ALWAYS_INLINE bool StyleInvalidator::checkInvalidationSetsAgainstElement(Element& element, StyleInvalidator::RecursionData& recursionData)
+void StyleInvalidator::SiblingData::pushInvalidationSet(const InvalidationSet& invalidationSet)
+{
+    unsigned invalidationLimit;
+    if (invalidationSet.maxDirectAdjacentSelectors() == std::numeric_limits<unsigned>::max())
+        invalidationLimit = std::numeric_limits<unsigned>::max();
+    else
+        invalidationLimit = m_elementIndex + invalidationSet.maxDirectAdjacentSelectors();
+    m_invalidationEntries.append(Entry { &invalidationSet, invalidationLimit });

[Timothy Loh, 2015/09/10 06:09:40]

this is banned https://chromium-cpp.appspot.com/ :-(

[Eric Willigers, 2015/09/14 07:20:24]

Fixed.

+}
+
+ALWAYS_INLINE bool StyleInvalidator::SiblingData::matchCurrentInvalidationSets(Element& element, RecursionData& recursionData)
+{
+    bool thisElementNeedsStyleRecalc = false;
+    ASSERT(!recursionData.wholeSubtreeInvalid());
+
+    unsigned index = 0;
+    while (index < m_invalidationEntries.size()) {
+        if (m_elementIndex > m_invalidationEntries[index].invalidationLimit) {
+            m_invalidationEntries[index] = m_invalidationEntries[m_invalidationEntries.size() - 1];

[Timothy Loh, 2015/09/10 06:09:40]

.last() I think?

[Eric Willigers, 2015/09/14 07:20:24]

Done.

+            m_invalidationEntries.removeLast();
+            continue;
+        }
+
+        const InvalidationSet* invalidationSet = m_invalidationEntries[index].invalidationSet.get();
+
+        if (invalidationSet->invalidatesElement(element)) {
+            ASSERT(invalidationSet->appliesDirectly() || invalidationSet->descendants());
+            if (invalidationSet->appliesDirectly())
+                thisElementNeedsStyleRecalc = true;
+            if (const InvalidationSet* descendants = invalidationSet->descendants()) {
+                if (descendants->wholeSubtreeInvalid()) {
+                    // Avoid directly setting SubtreeStyleChange on element, or ContainerNode::checkForChildrenAdjacentRuleChanges()
+                    // may propagate the SubtreeStyleChange to our own siblings' subtrees.
+
+                    for (Element* child = ElementTraversal::firstChild(element); child; child = ElementTraversal::nextSibling(*child)) {
+                        child->setNeedsStyleRecalc(SubtreeStyleChange, StyleChangeReasonForTracing::create(StyleChangeReason::SiblingSelector));
+                    }
+                    return true;
+                }
+
+                recursionData.pushInvalidationSet(*descendants);
+            }
+        }
+
+        ++index;
+    }
+    return thisElementNeedsStyleRecalc;
+}
+
+ALWAYS_INLINE bool StyleInvalidator::checkInvalidationSetsAgainstElement(Element& element, RecursionData& recursionData, SiblingData& siblingData)
 {
     if (element.styleChangeType() >= SubtreeStyleChange || recursionData.wholeSubtreeInvalid()) {
         recursionData.setWholeSubtreeInvalid();
         return false;
     }
-    if (element.needsStyleInvalidation()) {
-        if (InvalidationList* invalidationList = m_pendingInvalidationMap.get(&element)) {
-            for (const auto& invalidationSet : *invalidationList)
+
+    bool thisElementNeedsStyleRecalc = recursionData.matchesCurrentInvalidationSets(element);
+    thisElementNeedsStyleRecalc |= siblingData.matchCurrentInvalidationSets(element, recursionData);
+
+    if (UNLIKELY(element.needsStyleInvalidation())) {
+        InvalidationListData* listData = m_pendingInvalidationMap.get(&element);
+        ASSERT(listData);
+
+        if (!listData->descendants().isEmpty()) {
+            for (const auto& invalidationSet : listData->descendants())
                 recursionData.pushInvalidationSet(*invalidationSet);
             if (UNLIKELY(*s_tracingEnabled)) {
                 TRACE_EVENT_INSTANT1(TRACE_DISABLED_BY_DEFAULT("devtools.timeline.invalidationTracking"),
                     "StyleInvalidatorInvalidationTracking",
                     TRACE_EVENT_SCOPE_THREAD,
-                    "data", InspectorStyleInvalidatorInvalidateEvent::invalidationList(element, *invalidationList));
+                    "data", InspectorStyleInvalidatorInvalidateEvent::invalidationList(element, listData->descendants()));
             }
-            return true;
         }
+
+        for (const auto& invalidationSet : listData->siblings())
+            siblingData.pushInvalidationSet(*invalidationSet);
     }
 
-    return recursionData.matchesCurrentInvalidationSets(element);
+    return thisElementNeedsStyleRecalc;
 }
 
-bool StyleInvalidator::invalidateChildren(Element& element, StyleInvalidator::RecursionData& recursionData)
+bool StyleInvalidator::invalidateChildren(Element& element, RecursionData& recursionData)
 {
+    SiblingData siblingData;
+
     bool someChildrenNeedStyleRecalc = false;
     for (ShadowRoot* root = element.youngestShadowRoot(); root; root = root->olderShadowRoot()) {
         if (!recursionData.treeBoundaryCrossing() && !root->childNeedsStyleInvalidation() && !root->needsStyleInvalidation())
             continue;
         for (Element* child = ElementTraversal::firstChild(*root); child; child = ElementTraversal::nextSibling(*child)) {
-            bool childRecalced = invalidate(*child, recursionData);
+            bool childRecalced = invalidate(*child, recursionData, siblingData);
             someChildrenNeedStyleRecalc = someChildrenNeedStyleRecalc || childRecalced;
         }
         root->clearChildNeedsStyleInvalidation();
         root->clearNeedsStyleInvalidation();
     }
     for (Element* child = ElementTraversal::firstChild(element); child; child = ElementTraversal::nextSibling(*child)) {
-        bool childRecalced = invalidate(*child, recursionData);
+        bool childRecalced = invalidate(*child, recursionData, siblingData);
         someChildrenNeedStyleRecalc = someChildrenNeedStyleRecalc || childRecalced;
     }
     return someChildrenNeedStyleRecalc;
 }
 
-bool StyleInvalidator::invalidate(Element& element, StyleInvalidator::RecursionData& recursionData)
+bool StyleInvalidator::invalidate(Element& element, RecursionData& recursionData, SiblingData& siblingData)
 {
     RecursionCheckpoint checkpoint(&recursionData);
+    siblingData.advance();
 
-    bool thisElementNeedsStyleRecalc = checkInvalidationSetsAgainstElement(element, recursionData);
+    bool thisElementNeedsStyleRecalc = checkInvalidationSetsAgainstElement(element, recursionData, siblingData);
 
     bool someChildrenNeedStyleRecalc = false;
     if (recursionData.hasInvalidationSets() || element.childNeedsStyleInvalidation())