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..28ed031bb92153816649c4a9680f90272e02eba9 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
@@ -90,6 +95,11 @@ void extractClassIdOrTag(const CSSSelector& selector, HashSet<AtomicString>& cla
         classes.add(selector.value());
 }
 
+RuleFeatureSet::RuleFeatureSet()
+{
+    m_targetedStyleRecalcEnabled = RuntimeEnabledFeatures::targetedStyleRecalcEnabled();

[esprehn, 2014/01/30 05:09:24]

This should be in the initializer list.

RuleFeatureSet::RuleFeatureSet()
  : m_targetedStyleRecalcEnabled(...)
{
}

[chrishtr, 2014/01/30 17:28:15]

Done.

+}
+
 bool RuleFeatureSet::updateClassInvalidationSets(const CSSSelector* selector)
 {
     if (!selector)
@@ -127,14 +137,12 @@ void RuleFeatureSet::addAttributeInASelector(const AtomicString& attributeName)
     m_metadata.attrsInRules.add(attributeName);
 }
 
-
 void RuleFeatureSet::collectFeaturesFromRuleData(const RuleData& ruleData)
 {
-
     FeatureMetadata metadata;
     collectFeaturesFromSelector(ruleData.selector(), metadata);
     m_metadata.add(metadata);
-    if (RuntimeEnabledFeatures::targetedStyleRecalcEnabled()) {
+    if (m_targetedStyleRecalcEnabled) {
         bool selectorUsesClassInvalidationSet = updateClassInvalidationSets(ruleData.selector());
         if (!selectorUsesClassInvalidationSet) {
             for (HashSet<AtomicString>::const_iterator it = metadata.classesInRules.begin(); it != metadata.classesInRules.end(); ++it) {
@@ -143,6 +151,7 @@ void RuleFeatureSet::collectFeaturesFromRuleData(const RuleData& ruleData)
             }
         }
     }
+
     if (metadata.foundSiblingSelector)
         siblingRules.append(RuleFeature(ruleData.rule(), ruleData.selectorIndex(), ruleData.hasDocumentSecurityOrigin()));
     if (ruleData.containsUncommonAttributeSelector())
@@ -240,4 +249,175 @@ void RuleFeatureSet::clear()
     uncommonAttributeRules.clear();
 }
 
+void RuleFeatureSet::scheduleStyleInvalidationForClassChange(const SpaceSplitString& changedClasses, Element* element)
+{
+    if (scheduleStyleInvalidationForClassChangeInternal(changedClasses, element)
+        && !m_targetedStyleRecalcEnabled)

[esprehn, 2014/01/30 05:09:24]

I wouldn't wrap these.

[chrishtr, 2014/01/30 17:28:15]

Done.

+        element->setNeedsStyleRecalc();
+}
+
+void RuleFeatureSet::scheduleStyleInvalidationForClassChange(const SpaceSplitString& oldClasses, const SpaceSplitString& newClasses, Element* element)
+{
+    if (scheduleStyleInvalidationForClassChangeInternal(oldClasses, newClasses, element)
+        && !m_targetedStyleRecalcEnabled)
+        element->setNeedsStyleRecalc();
+}
+
+bool RuleFeatureSet::scheduleStyleInvalidationForClassChangeInternal(const SpaceSplitString& changedClasses, Element* element)
+{
+    unsigned changedSize = changedClasses.size();
+    for (unsigned i = 0; i < changedSize; ++i) {
+        if (m_targetedStyleRecalcEnabled)
+            addClassToInvalidationSet(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)

[esprehn, 2014/01/30 05:09:24]

Having two methods with the same name like this is pretty confusing. I might
suggest not naming them ...Internal() and using a more specific name. Then the
above functions would be.

bool shouldRecalcStyle = invalidateSubtreeForClassChange(...);
if (shouldRecalcStyle)
  element->setNeedsStyleRecalc();

[chrishtr, 2014/01/30 17:28:15]

Done.

+{
+    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 (m_targetedStyleRecalcEnabled)
+                addClassToInvalidationSet(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 (m_targetedStyleRecalcEnabled)
+            addClassToInvalidationSet(oldClasses[i], element);
+        else if (m_metadata.classesInRules.contains(oldClasses[i]))
+            return true;
+    }
+    return false;
+}
+
+void RuleFeatureSet::addClassToInvalidationSet(const AtomicString& className, Element* element)
+{
+    if (DescendantInvalidationSet* invalidationSet = m_classInvalidationSets.get(className)) {
+        ensurePendingInvalidationList(element).append(invalidationSet);
+        element->setNeedsStyleInvalidation();
+    }
+}
+
+RuleFeatureSet::InvalidationList& RuleFeatureSet::ensurePendingInvalidationList(Element* element)
+{
+    PendingInvalidationMap::AddResult addResult = m_pendingInvalidationMap.add(element, 0);
+    if (addResult.isNewEntry)
+        addResult.iterator->value = new InvalidationList;
+    return *addResult.iterator->value;
+}
+
+void RuleFeatureSet::computeStyleInvalidation(Document& document)
+{
+    Vector<AtomicString> invalidationClasses;
+    for (Node* child = document.firstChild(); child; child = child->nextSibling()) {

[esprehn, 2014/01/30 05:09:24]

A document can only have one element child, you don't need this loop.

if (Element* documentElement = document.documentElement()) {
  if (documentElement->needs...())
    compute...(documentElement);
}

see for example Document::recalcStyle.

[chrishtr, 2014/01/30 17:28:15]

Done.

+        if (child->isElementNode() && child->childNeedsStyleInvalidation()) {
+            Element* childElement = toElement(child);
+            computeStyleInvalidationInternal(childElement, invalidationClasses, false);

[esprehn, 2014/01/30 05:09:24]

I would name these methods invalidateStyleForClassChange() or
invalidateSubtree() or something like that, Internal() doesn't really make it
clear what's going on. It's good to avoid all the Internal stuff too, since you
call it in several places.

[chrishtr, 2014/01/30 17:28:15]

Done.

+        }
+    }
+    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);

[esprehn, 2014/01/30 05:09:24]

invalidateSubtree(...)

[chrishtr, 2014/01/30 17:28:15]

Done.

[chrishtr, 2014/01/30 17:28:15]

Done.

+            someChildrenNeedStyleRecalc = someChildrenNeedStyleRecalc || childRecalced;
+        }
+    }
+    for (ShadowRoot* root = element->youngestShadowRoot(); root; root = root->olderShadowRoot()) {

[esprehn, 2014/01/30 05:09:24]

Usually we do ShadowRoots first, I'd swap these two sections. I suppose it
doesn't matter though.

[chrishtr, 2014/01/30 17:28:15]

Done.

+        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;
+            }
+        }
+    }
+    return someChildrenNeedStyleRecalc;
+}
+
+bool RuleFeatureSet::computeStyleInvalidationInternal(Element* element, Vector<AtomicString>& invalidationClasses, bool foundInvalidationSet)
+{
+    int oldSize = invalidationClasses.size();
+    if (element->needsStyleInvalidation()) {
+        if (InvalidationList* invalidationList = m_pendingInvalidationMap.get(element)) {
+            foundInvalidationSet = true;
+            bool recalcWholeSubtree = false;
+            for (InvalidationList::const_iterator it = invalidationList->begin(); it != invalidationList->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;

[esprehn, 2014/01/30 05:09:24]

element->setNeedsSylRecalc(LocalStyleChange);
and then mark all ancestors with LocalStyleChange too.

[chrishtr, 2014/01/30 17:28:15]

I don't like that, as it will cause a bunch of redundant tree walking in
situations when multiple descendants of an element need local recalc. The logic
to add these bools is not very hard to understand.

[ojan, 2014/01/30 19:08:39]

setNeedsStyleRecalc does the ancestor walk only once. If you call it on
something that already needs recalc, then it won't do the ancestor walk.

The extra bool here does help avoiding a bunch of extra branching in
setNeedsStyleRecalc itself, but I'm skeptical it matters.

Meh. I don't feel strongly either way.

[chrishtr, 2014/01/30 19:25:48]

It's not the ancestor child-needs-recalc bit setting that is the issue. It's
that we need to call setNeedsStyleRecalc(LocalStyleChange) on all ancestors of
this element, or else style sharing will break.
Elliott was suggesting an extra tree walk here. But that introduces redundant
tree walks in cases when many elements need descendant selector recalc.

[ojan, 2014/01/30 19:51:18]

There's something I'm missing. If you just replace the two places where you set
thisElementNeedsStyleRecalc to true with
element->setNeedsStyleRecalc(LocalStyleChange), isn't the code equivalent?

[chrishtr, 2014/01/30 21:39:44]

Yes. I can make that change if you want. The return-value boolean and
accompanying logic I don't want to remove though.

[ojan, 2014/01/30 22:15:55]

Ah. Didn't notice that we're returning this value.

[chrishtr, 2014/01/30 22:25:53]

Ack.

+                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/30 05:09:24]

Get rid of the bools, just call setNeedsStyleRecalc(LocalStyleChange) up the
tree.

[chrishtr, 2014/01/30 17:28:15]

See above.

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

[esprehn, 2014/01/30 05:09:24]

Remove this. If you just mark yourself above and then walk up the tree you get
the same behavior.

[chrishtr, 2014/01/30 17:28:15]

See above.

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