Implement style invalidation tree walk for targeted style recalc upon class change.

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 8dfb8cdac6adf67b7ea6c45c4c51d41b4e9311b2..c1a6a5e2d508aae660d88a09760ea5c02650bec4 100644
--- a/Source/core/css/RuleFeature.cpp
+++ b/Source/core/css/RuleFeature.cpp
@@ -34,6 +34,12 @@
 #include "core/css/CSSSelector.h"
 #include "core/css/CSSSelectorList.h"
 #include "core/css/RuleSet.h"
+#include "core/dom/Document.h"
+#include "core/dom/Element.h"
+#include "core/dom/Node.h"
+#include "core/dom/shadow/ElementShadow.h"
+#include "core/dom/shadow/ShadowRoot.h"
+#include "wtf/BitVector.h"
 
 namespace WebCore {
 
@@ -55,9 +61,8 @@ static bool supportsClassDescendantInvalidation(const CSSSelector* selector)
         // FIXME: We should allow pseudo elements, but we need to change how they hook
         // into recalcStyle by moving them to recalcOwnStyle instead of recalcChildStyle.
 
-        if (component->m_match == CSSSelector::Tag
-            || component->m_match == CSSSelector::Id
-            || component->m_match == CSSSelector::Class) {
+        // FIXME: next up: Tag and Id.
+        if (component->m_match == CSSSelector::Class) {
             if (!foundDescendantRelation)
                 foundIdent = true;
             else
@@ -240,4 +245,172 @@ void RuleFeatureSet::clear()
     uncommonAttributeRules.clear();
 }
 
+void RuleFeatureSet::scheduleStyleInvalidationForClassChange(const SpaceSplitString& changedClasses, Element* element)
+{
+    if (scheduleStyleInvalidationForClassChangeInternal(changedClasses, element)
+        && !RuntimeEnabledFeatures::targetedStyleRecalcEnabled())

[esprehn, 2014/01/28 00:11:34]

Your flag checks need to always be first, otherwise we run code even with the
flag disabled. We usually keep it separate too.

if (!RuntimeEnabledFeatures::targetedStyleRecalcEnabled())
  return;

if (scheduleStyleInvalidationForClassChangeInternal(changedClasses, element))
  element->setNeedsStyleRecalc();

[chrishtr, 2014/01/28 01:11:55]

The situation here is a little subtle. The code in
scheduleStyleInvalidationForClassChangeInternal is the same as what used to be
in checkSelectorForClassName in Element.cpp, except taht it has a
RuntimeEnabledFeatures::targetedStyleRecalcEnabled() check at each of the points
when the logic differs from with the flag off. Further, the return value of
scheduleStyleInvalidationForClassChangeInternal is ignored when the flag is on
but not when it is off, hence the code here.

On 2014/01/28 00:11:34, esprehn wrote:

+        element->setNeedsStyleRecalc();
+}
+
+void RuleFeatureSet::scheduleStyleInvalidationForClassChange(const SpaceSplitString& oldClasses, const SpaceSplitString& newClasses, Element* element)
+{
+    if (scheduleStyleInvalidationForClassChangeInternal(oldClasses, newClasses, element)
+        && !RuntimeEnabledFeatures::targetedStyleRecalcEnabled())
+        element->setNeedsStyleRecalc();

[esprehn, 2014/01/28 00:11:34]

Ditto.

[chrishtr, 2014/01/28 01:11:55]

Same.

+}
+
+bool RuleFeatureSet::scheduleStyleInvalidationForClassChangeInternal(const SpaceSplitString& changedClasses, Element* element)
+{
+    unsigned changedSize = changedClasses.size();
+    for (unsigned i = 0; i < changedSize; ++i) {
+        if (RuntimeEnabledFeatures::targetedStyleRecalcEnabled())
+            scheduleStyleInvalidationForOneClass(changedClasses[i], element);
+        else if (m_metadata.classesInRules.contains(changedClasses[i]))
+            return true;
+    }
+    return false;
+}
+
+bool RuleFeatureSet::scheduleStyleInvalidationForClassChangeInternal(const SpaceSplitString& oldClasses, const SpaceSplitString& newClasses, Element* element)
+{
+    if (!oldClasses.size())
+        return scheduleStyleInvalidationForClassChangeInternal(newClasses, element);
+
+    // Class vectors tend to be very short. This is faster than using a hash table.
+    BitVector remainingClassBits;
+    remainingClassBits.ensureSize(oldClasses.size());
+
+    for (unsigned i = 0; i < newClasses.size(); ++i) {
+        bool found = false;
+        for (unsigned j = 0; j < oldClasses.size(); ++j) {
+            if (newClasses[i] == oldClasses[j]) {
+                // Mark each class that is still in the newClasses so we can skip doing
+                // an n^2 search below when looking for removals. We can't break from
+                // this loop early since a class can appear more than once.
+                remainingClassBits.quickSet(j);
+                found = true;
+            }
+        }
+        // Class was added.
+        if (!found) {
+            if (RuntimeEnabledFeatures::targetedStyleRecalcEnabled())
+                scheduleStyleInvalidationForOneClass(newClasses[i], element);
+            else if (m_metadata.classesInRules.contains(newClasses[i]))
+                return true;
+        }
+    }
+
+    for (unsigned i = 0; i < oldClasses.size(); ++i) {
+        if (remainingClassBits.quickGet(i))
+            continue;
+
+        // Class was removed.
+        if (RuntimeEnabledFeatures::targetedStyleRecalcEnabled())
+            scheduleStyleInvalidationForOneClass(oldClasses[i], element);
+        else if (m_metadata.classesInRules.contains(oldClasses[i]))
+            return true;
+    }
+    return false;
+}
+
+void RuleFeatureSet::scheduleStyleInvalidationForOneClass(const AtomicString& className, Element* element)

[esprehn, 2014/01/28 00:11:34]

ForClass(), no need for the "OneClass". Multiple classes are SpaceSplitStrings.

[chrishtr, 2014/01/28 01:11:55]

Made name more clear, it's really about adding a descendant invalidation set.

+{
+    if (DescendantInvalidationSet* invalidationSet = m_classInvalidationSets.get(className)) {
+        ensurePendingInvalidationVector(element)->append(invalidationSet);
+        element->markAncestorsWithChildNeedsStyleInvalidation();
+    }
+}
+
+RuleFeatureSet::InvalidationVec* RuleFeatureSet::ensurePendingInvalidationVector(Element* element)

[esprehn, 2014/01/28 00:11:34]

Returns a ref.

[chrishtr, 2014/01/28 01:11:55]

Done.

+{
+    PendingInvalidationMap::AddResult addResult = m_pendingInvalidationMap.add(element, 0);
+    if (addResult.isNewEntry)
+        addResult.iterator->value = new InvalidationVec;
+    return addResult.iterator->value;

[esprehn, 2014/01/28 00:11:34]

*addResult->value

[chrishtr, 2014/01/28 01:11:55]

Done.

+}
+
+void RuleFeatureSet::computeStyleInvalidation(Document* document)
+{
+    Vector<AtomicString> invalidationClasses;
+    for (Node* child = document->firstChild(); child; child = child->nextSibling()) {
+        if (child->isElementNode() && child->childNeedsStyleInvalidation()) {
+            Element* childElement = toElement(child);
+            computeStyleInvalidationInternal(childElement, invalidationClasses, false);
+        }
+    }
+    document->clearChildNeedsStyleInvalidation();
+    m_pendingInvalidationMap.clear();
+}
+
+bool RuleFeatureSet::computeStyleInvalidationForChildren(Element* element, Vector<AtomicString>& invalidationClasses, bool foundInvalidationSet)
+{
+    bool someChildrenNeedStyleRecalc = false;
+    for (Node* child = element->firstChild(); child; child = child->nextSibling()) {
+        if (child->isElementNode()) {
+            Element* childElement = toElement(child);
+            bool childRecalced = computeStyleInvalidationInternal(childElement, invalidationClasses, foundInvalidationSet);
+            someChildrenNeedStyleRecalc = someChildrenNeedStyleRecalc || childRecalced;
+        }
+    }
+    for (ShadowRoot* root = element->youngestShadowRoot(); root; root = root->olderShadowRoot()) {
+        for (Node* child = root->firstChild(); child; child = child->nextSibling()) {
+            if (child->isElementNode()) {
+                Element* childElement = toElement(child);
+                bool childRecalced = computeStyleInvalidationInternal(childElement, invalidationClasses, foundInvalidationSet);
+                someChildrenNeedStyleRecalc = someChildrenNeedStyleRecalc || childRecalced;

[esprehn, 2014/01/28 00:11:34]

Remove this boolean stuff.

[chrishtr, 2014/01/28 01:11:55]

See below.

+            }
+        }
+    }
+    return someChildrenNeedStyleRecalc;
+}
+
+bool RuleFeatureSet::computeStyleInvalidationInternal(Element* element, Vector<AtomicString>& invalidationClasses, bool foundInvalidationSet)
+{
+    int oldSize = invalidationClasses.size();
+    if (InvalidationVec* invalidationVec = m_pendingInvalidationMap.get(element)) {

[esprehn, 2014/01/28 00:11:34]

You want two bits, you're doing tons of hash map lookups when they're not
needed.  One bit for self and one for child.

[chrishtr, 2014/01/28 01:11:55]

Done.

+        foundInvalidationSet = true;
+        bool recalcWholeSubtree = false;
+        for (InvalidationVec::const_iterator it = invalidationVec->begin(); it != invalidationVec->end(); ++it) {
+            if ((*it)->wholeSubtreeInvalid()) {
+                recalcWholeSubtree = true;
+                break;
+            }
+            (*it)->getClasses(invalidationClasses);
+        }
+        if (recalcWholeSubtree) {
+            element->setNeedsStyleRecalc(SubtreeStyleChange);
+            invalidationClasses.remove(oldSize, invalidationClasses.size() - oldSize);
+            element->clearChildNeedsStyleInvalidation();
+            return true;
+        }
+    }
+    bool thisElementNeedsStyleRecalc = false;
+
+    if (element->hasClass()) {
+        const SpaceSplitString& classNames = element->classNames();
+        for (Vector<AtomicString>::const_iterator it = invalidationClasses.begin(); it != invalidationClasses.end(); ++it) {
+            if (classNames.contains(*it)) {
+                thisElementNeedsStyleRecalc = true;
+                break;
+            }
+        }
+    }
+
+    // foundInvalidationSet will be true if we are in a subtree of a node with a DescendantInvalidationSet on it.
+    // We need to check all nodes in the subtree of such a node.
+    if (foundInvalidationSet || element->childNeedsStyleInvalidation()) {
+        bool someChildrenNeedStyleRecalc = computeStyleInvalidationForChildren(element, invalidationClasses, foundInvalidationSet);
+        // We only need to possibly recalc style if this node is in the subtree of a node with a DescendantInvalidationSet on it.
+        if (foundInvalidationSet)
+            thisElementNeedsStyleRecalc = thisElementNeedsStyleRecalc || someChildrenNeedStyleRecalc;

[esprehn, 2014/01/28 00:11:34]

Instead of returning this bool, just walk the ancestors below.

[chrishtr, 2014/01/28 01:11:55]

See below.

+    }
+
+    if (thisElementNeedsStyleRecalc)
+        element->setNeedsStyleRecalc(LocalStyleChange);

[esprehn, 2014/01/28 00:11:34]

This should just walk ancestors:

for (Element* ancestor = element; element; element =
element->parentOrShadowHostNode()) {
  if (!element->needsStyleRecalc())
     element->setNeedsStyleRecalc(LocalStyleChange);
}

[chrishtr, 2014/01/28 01:11:55]

That'll do a bunch of of extra tree walking. Inefficient?

On 2014/01/28 00:11:34, esprehn wrote:

+
+    invalidationClasses.remove(oldSize, invalidationClasses.size() - oldSize);
+    element->clearChildNeedsStyleInvalidation();
+    return thisElementNeedsStyleRecalc;
+}
+
 } // namespace WebCore