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

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 16 matching lines @@
  */
 
 #include "config.h"
 #include "core/css/RuleFeature.h"
 
 #include "HTMLNames.h"
 #include "RuntimeEnabledFeatures.h"
 #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 {
 
 static bool isSkippableComponentForInvalidation(const CSSSelector* selector)
 {
     if (selector->matchesPseudoElement() || selector->pseudoType() == CSSSelector::PseudoHost)
         return false;
     return true;
 }
 
 // This method is somewhat conservative in what it acceptss.
 static bool supportsClassDescendantInvalidation(const CSSSelector* selector)
 {
     bool foundDescendantRelation = false;
     bool foundAncestorIdent = false;
     bool foundIdent = false;
     for (const CSSSelector* component = selector; component; component = component->tagHistory()) {
 
         // 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
                 foundAncestorIdent = true;
         } else if (!isSkippableComponentForInvalidation(component)) {
             return false;
         }
         // FIXME: We can probably support ChildTree and DescendantTree.
         switch (component->relation()) {
         case CSSSelector::Descendant:
@@ skipping 12 matching lines @@
 void extractClassIdOrTag(const CSSSelector& selector, HashSet<AtomicString>& classes, AtomicString& id, AtomicString& tagName)
 {
     if (selector.m_match == CSSSelector::Tag)
         tagName = selector.tagQName().localName();
     else if (selector.m_match == CSSSelector::Id)
         id = selector.value();
     else if (selector.m_match == CSSSelector::Class)
         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)
         return false;
     if (!supportsClassDescendantInvalidation(selector))
         return false;
 
     HashSet<AtomicString> classes;
     AtomicString id;
     AtomicString tagName;
@@ skipping 17 matching lines @@
         }
     }
     return true;
 }
 
 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) {
                 DescendantInvalidationSet& invalidationSet = ensureClassInvalidationSet(*it);
                 invalidationSet.setWholeSubtreeInvalid();
             }
         }
     }
+
     if (metadata.foundSiblingSelector)
         siblingRules.append(RuleFeature(ruleData.rule(), ruleData.selectorIndex(), ruleData.hasDocumentSecurityOrigin()));
     if (ruleData.containsUncommonAttributeSelector())
         uncommonAttributeRules.append(RuleFeature(ruleData.rule(), ruleData.selectorIndex(), ruleData.hasDocumentSecurityOrigin()));
 }
 
 DescendantInvalidationSet& RuleFeatureSet::ensureClassInvalidationSet(const AtomicString& className)
 {
     InvalidationSetMap::AddResult addResult = m_classInvalidationSets.add(className, 0);
     if (addResult.isNewEntry)
@@ skipping 77 matching lines @@
     uncommonAttributeRules.append(other.uncommonAttributeRules);
 }
 
 void RuleFeatureSet::clear()
 {
     m_metadata.clear();
     siblingRules.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