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 162 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)
+        && !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