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

Source/core/dom/shadow/SelectRuleFeatureSet.cpp

 /*
  * Copyright (C) 2012 Google Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions are
  * met:
  *
  *     * Redistributions of source code must retain the above copyright
  * notice, this list of conditions and the following disclaimer.
  *     * Redistributions in binary form must reproduce the above
@@ skipping 15 matching lines @@
  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */
 
 #include "config.h"
 #include "core/dom/shadow/SelectRuleFeatureSet.h"
 
 #include "core/css/CSSSelector.h"
 
+#include "wtf/BitVector.h"
+
 namespace WebCore {
 
 SelectRuleFeatureSet::SelectRuleFeatureSet()
     : m_featureFlags(0)
 {
 }
 
 void SelectRuleFeatureSet::add(const SelectRuleFeatureSet& featureSet)
 {
     m_cssRuleFeatureSet.add(featureSet.m_cssRuleFeatureSet);
@@ skipping 30 matching lines @@
         setSelectRuleFeature(AffectedSelectorTarget);
         break;
     case CSSSelector::PseudoVisited:
         setSelectRuleFeature(AffectedSelectorVisited);
         break;
     default:
         break;
     }
 }
 
+bool SelectRuleFeatureSet::checkSelectorsForClassChange(const SpaceSplitString& changedClasses) const
+{
+    unsigned changedSize = changedClasses.size();
+    for (unsigned i = 0; i < changedSize; ++i) {
+        if (hasSelectorForClass(changedClasses[i]))
+            return true;
+    }
+    return false;
+}
+
+bool SelectRuleFeatureSet::checkSelectorsForClassChange(const SpaceSplitString& oldClasses, const SpaceSplitString& newClasses) const
+{
+    if (!oldClasses.size())
+        return checkSelectorsForClassChange(newClasses);
+
+    // 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 (hasSelectorForClass(newClasses[i]))
+                return true;
+        }
+    }
+
+    for (unsigned i = 0; i < oldClasses.size(); ++i) {
+        if (remainingClassBits.quickGet(i))
+            continue;
+
+        // Class was removed.
+        if (hasSelectorForClass(oldClasses[i]))
+            return true;
+    }
+    return false;
+}
+
 }