src/third_party/WebKit/Source/core/css/RuleFeature.cpp

   1 /*
   2  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
   3  *           (C) 2004-2005 Allan Sandfeld Jensen (kde@carewolf.com)
   4  * Copyright (C) 2006, 2007 Nicholas Shanks (webkit@nickshanks.com)
   5  * Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012 Apple Inc. All rights reserved.
   6  * Copyright (C) 2007 Alexey Proskuryakov <ap@webkit.org>
   7  * Copyright (C) 2007, 2008 Eric Seidel <eric@webkit.org>
   8  * Copyright (C) 2008, 2009 Torch Mobile Inc. All rights reserved. (http://www.torchmobile.com/)
   9  * Copyright (c) 2011, Code Aurora Forum. All rights reserved.
  10  * Copyright (C) Research In Motion Limited 2011. All rights reserved.
  11  * Copyright (C) 2012 Google Inc. All rights reserved.
  12  *
  13  * This library is free software; you can redistribute it and/or
  14  * modify it under the terms of the GNU Library General Public
  15  * License as published by the Free Software Foundation; either
  16  * version 2 of the License, or (at your option) any later version.
  17  *
  18  * This library is distributed in the hope that it will be useful,
  19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  21  * Library General Public License for more details.
  22  *
  23  * You should have received a copy of the GNU Library General Public License
  24  * along with this library; see the file COPYING.LIB.  If not, write to
  25  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  26  * Boston, MA 02110-1301, USA.
  27  */
  28
  29 #include "config.h"
  30 #include "core/css/RuleFeature.h"
  31
  32 #include "core/HTMLNames.h"
  33 #include "core/css/CSSSelector.h"
  34 #include "core/css/CSSSelectorList.h"
  35 #include "core/css/RuleSet.h"
  36 #include "core/css/StyleRule.h"
  37 #include "core/css/invalidation/DescendantInvalidationSet.h"
  38 #include "core/dom/Element.h"
  39 #include "core/dom/Node.h"
  40 #include "platform/RuntimeEnabledFeatures.h"
  41 #include "wtf/BitVector.h"
  42
  43 namespace blink {
  44
  45 static bool isSkippableComponentForInvalidation(const CSSSelector& selector)
  46 {
  47     if (selector.match() == CSSSelector::Tag) {
  48         ASSERT(selector.tagQName().localName() == starAtom);
  49         return true;
  50     }
  51     if (selector.match() == CSSSelector::PseudoElement) {
  52         switch (selector.pseudoType()) {
  53         case CSSSelector::PseudoBefore:
  54         case CSSSelector::PseudoAfter:
  55         case CSSSelector::PseudoBackdrop:
  56         case CSSSelector::PseudoShadow:
  57             return true;
  58         default:
  59             ASSERT(!selector.isCustomPseudoElement());
  60             return false;
  61         }
  62     }
  63     if (selector.match() != CSSSelector::PseudoClass)
  64         return false;
  65     switch (selector.pseudoType()) {
  66     case CSSSelector::PseudoEmpty:
  67     case CSSSelector::PseudoFirstChild:
  68     case CSSSelector::PseudoFirstOfType:
  69     case CSSSelector::PseudoLastChild:
  70     case CSSSelector::PseudoLastOfType:
  71     case CSSSelector::PseudoOnlyChild:
  72     case CSSSelector::PseudoOnlyOfType:
  73     case CSSSelector::PseudoNthChild:
  74     case CSSSelector::PseudoNthOfType:
  75     case CSSSelector::PseudoNthLastChild:
  76     case CSSSelector::PseudoNthLastOfType:
  77     case CSSSelector::PseudoLink:
  78     case CSSSelector::PseudoVisited:
  79     case CSSSelector::PseudoAnyLink:
  80     case CSSSelector::PseudoHover:
  81     case CSSSelector::PseudoDrag:
  82     case CSSSelector::PseudoFocus:
  83     case CSSSelector::PseudoActive:
  84     case CSSSelector::PseudoChecked:
  85     case CSSSelector::PseudoEnabled:
  86     case CSSSelector::PseudoDefault:
  87     case CSSSelector::PseudoDisabled:
  88     case CSSSelector::PseudoOptional:
  89     case CSSSelector::PseudoRequired:
  90     case CSSSelector::PseudoReadOnly:
  91     case CSSSelector::PseudoReadWrite:
  92     case CSSSelector::PseudoValid:
  93     case CSSSelector::PseudoInvalid:
  94     case CSSSelector::PseudoIndeterminate:
  95     case CSSSelector::PseudoTarget:
  96     case CSSSelector::PseudoLang:
  97     case CSSSelector::PseudoRoot:
  98     case CSSSelector::PseudoScope:
  99     case CSSSelector::PseudoInRange:
 100     case CSSSelector::PseudoOutOfRange:
 101     case CSSSelector::PseudoUnresolved:
 102     case CSSSelector::PseudoListBox:
 103         return true;
 104     default:
 105         return false;
 106     }
 107 }
 108
 109 RuleFeature::RuleFeature(StyleRule* rule, unsigned selectorIndex, bool hasDocumentSecurityOrigin)
 110     : rule(rule)
 111     , selectorIndex(selectorIndex)
 112     , hasDocumentSecurityOrigin(hasDocumentSecurityOrigin)
 113 {
 114 }
 115
 116 void RuleFeature::trace(Visitor* visitor)
 117 {
 118     visitor->trace(rule);
 119 }
 120
 121 // This method is somewhat conservative in what it accepts.
 122 RuleFeatureSet::InvalidationSetMode RuleFeatureSet::invalidationSetModeForSelector(const CSSSelector& selector)
 123 {
 124     bool foundCombinator = false;
 125     bool foundIdent = false;
 126     for (const CSSSelector* component = &selector; component; component = component->tagHistory()) {
 127
 128         if (component->match() == CSSSelector::Class || component->match() == CSSSelector::Id
 129             || (component->match() == CSSSelector::Tag && component->tagQName().localName() != starAtom)
 130             || component->isAttributeSelector() || component->isCustomPseudoElement()) {
 131             if (!foundCombinator) {
 132                 // We have found an invalidation set feature in the rightmost compound selector.
 133                 foundIdent = true;
 134             }
 135         } else if (component->pseudoType() == CSSSelector::PseudoNot
 136             || component->pseudoType() == CSSSelector::PseudoHost
 137             || component->pseudoType() == CSSSelector::PseudoAny) {
 138             if (const CSSSelectorList* selectorList = component->selectorList()) {
 139                 // Features inside :not() are not added to the feature set, so consider it a universal selector.
 140                 bool foundUniversal = component->pseudoType() == CSSSelector::PseudoNot;
 141                 for (const CSSSelector* selector = selectorList->first(); selector; selector = CSSSelectorList::next(*selector)) {
 142                     // Find the invalidation set mode for each of the selectors in the selector list
 143                     // of a :not(), :host(), etc. For instance, ".x :-webkit-any(.a, .b)" yields an
 144                     // AddFeatures mode for both ".a" and ".b". ":-webkit-any(.a, *)" yields AddFeatures
 145                     // for ".a", but UseSubtreeStyleChange for "*". One sub-selector without invalidation
 146                     // set features is sufficient to cause the selector to be a universal selector as far
 147                     // the invalidation set is concerned.
 148                     InvalidationSetMode subSelectorMode = invalidationSetModeForSelector(*selector);
 149
 150                     // The sub-selector contained something unskippable, fall back to whole subtree
 151                     // recalcs in collectFeaturesFromSelector. subSelectorMode will return
 152                     // UseSubtreeStyleChange since there are no combinators inside the selector list,
 153                     // so translate it to UseLocalStyleChange if a combinator has been seen in the
 154                     // outer context.
 155                     //
 156                     // FIXME: Is UseSubtreeStyleChange ever needed as input to collectFeaturesFromSelector?
 157                     // That is, are there any selectors for which we need to use SubtreeStyleChange for
 158                     // changing features when present in the rightmost compound selector?
 159                     if (subSelectorMode == UseSubtreeStyleChange)
 160                         return foundCombinator ? UseLocalStyleChange : UseSubtreeStyleChange;
 161
 162                     // We found no features in the sub-selector, only skippable ones (foundIdent was
 163                     // false at the end of this method). That is a universal selector as far as the
 164                     // invalidation set is concerned.
 165                     if (subSelectorMode == UseLocalStyleChange)
 166                         foundUniversal = true;
 167                 }
 168                 if (!foundUniversal && !foundCombinator) {
 169                     // All sub-selectors contained invalidation set features and
 170                     // we are in the rightmost compound selector.
 171                     foundIdent = true;
 172                 }
 173             }
 174         } else if (!isSkippableComponentForInvalidation(*component)) {
 175             return foundCombinator ? UseLocalStyleChange : UseSubtreeStyleChange;
 176         }
 177         if (component->relation() != CSSSelector::SubSelector)
 178             foundCombinator = true;
 179     }
 180     return foundIdent ? AddFeatures : UseLocalStyleChange;
 181 }
 182
 183 void RuleFeatureSet::extractInvalidationSetFeature(const CSSSelector& selector, InvalidationSetFeatures& features)
 184 {
 185     if (selector.match() == CSSSelector::Tag)
 186         features.tagName = selector.tagQName().localName();
 187     else if (selector.match() == CSSSelector::Id)
 188         features.id = selector.value();
 189     else if (selector.match() == CSSSelector::Class)
 190         features.classes.append(selector.value());
 191     else if (selector.isAttributeSelector())
 192         features.attributes.append(selector.attribute().localName());
 193     else if (selector.isCustomPseudoElement())
 194         features.customPseudoElement = true;
 195 }
 196
 197 RuleFeatureSet::RuleFeatureSet()
 198 {
 199 }
 200
 201 RuleFeatureSet::~RuleFeatureSet()
 202 {
 203 }
 204
 205 DescendantInvalidationSet* RuleFeatureSet::invalidationSetForSelector(const CSSSelector& selector)
 206 {
 207     if (selector.match() == CSSSelector::Class)
 208         return &ensureClassInvalidationSet(selector.value());
 209     if (selector.isAttributeSelector())
 210         return &ensureAttributeInvalidationSet(selector.attribute().localName());
 211     if (selector.match() == CSSSelector::Id)
 212         return &ensureIdInvalidationSet(selector.value());
 213     if (selector.match() == CSSSelector::PseudoClass) {
 214         switch (selector.pseudoType()) {
 215         case CSSSelector::PseudoEmpty:
 216         case CSSSelector::PseudoHover:
 217         case CSSSelector::PseudoActive:
 218         case CSSSelector::PseudoFocus:
 219         case CSSSelector::PseudoChecked:
 220         case CSSSelector::PseudoEnabled:
 221         case CSSSelector::PseudoDisabled:
 222         case CSSSelector::PseudoIndeterminate:
 223         case CSSSelector::PseudoLink:
 224         case CSSSelector::PseudoTarget:
 225         case CSSSelector::PseudoVisited:
 226             return &ensurePseudoInvalidationSet(selector.pseudoType());
 227         default:
 228             break;
 229         }
 230     }
 231     return 0;
 232 }
 233
 234 // Given a selector, update the descendant invalidation sets for the features found
 235 // in the selector. The first step is to extract the features from the rightmost
 236 // compound selector (extractInvalidationSetFeatures). Secondly, those features will be
 237 // added to the invalidation sets for the features found in the other compound selectors
 238 // (addFeaturesToInvalidationSets).
 239
 240 RuleFeatureSet::InvalidationSetMode RuleFeatureSet::updateInvalidationSets(const CSSSelector& selector)
 241 {
 242     InvalidationSetMode mode = invalidationSetModeForSelector(selector);
 243     if (mode != AddFeatures)
 244         return mode;
 245
 246     InvalidationSetFeatures features;
 247     if (const CSSSelector* current = extractInvalidationSetFeatures(selector, features, false))
 248         addFeaturesToInvalidationSets(*current, features);
 249     return AddFeatures;
 250 }
 251
 252 const CSSSelector* RuleFeatureSet::extractInvalidationSetFeatures(const CSSSelector& selector, InvalidationSetFeatures& features, bool negated)
 253 {
 254     for (const CSSSelector* current = &selector; current; current = current->tagHistory()) {
 255         if (!negated)
 256             extractInvalidationSetFeature(*current, features);
 257         // Initialize the entry in the invalidation set map, if supported.
 258         invalidationSetForSelector(*current);
 259         if (current->pseudoType() == CSSSelector::PseudoHost || current->pseudoType() == CSSSelector::PseudoAny || current->pseudoType() == CSSSelector::PseudoNot) {
 260             if (const CSSSelectorList* selectorList = current->selectorList()) {
 261                 for (const CSSSelector* selector = selectorList->first(); selector; selector = CSSSelectorList::next(*selector))
 262                     extractInvalidationSetFeatures(*selector, features, current->pseudoType() == CSSSelector::PseudoNot);
 263             }
 264         }
 265
 266         switch (current->relation()) {
 267         case CSSSelector::SubSelector:
 268             break;
 269         case CSSSelector::ShadowPseudo:
 270         case CSSSelector::ShadowDeep:
 271             features.treeBoundaryCrossing = true;
 272             return current->tagHistory();
 273         case CSSSelector::DirectAdjacent:
 274         case CSSSelector::IndirectAdjacent:
 275             features.wholeSubtree = true;
 276             return current->tagHistory();
 277         case CSSSelector::Descendant:
 278         case CSSSelector::Child:
 279             return current->tagHistory();
 280         }
 281     }
 282     return 0;
 283 }
 284
 285 // Add features extracted from the rightmost compound selector to descendant invalidation
 286 // sets for features found in other compound selectors.
 287 //
 288 // Style invalidation is currently supported for descendants only, not for sibling subtrees.
 289 // We use wholeSubtree invalidation for features found left of adjacent combinators as
 290 // SubtreeStyleChange will force sibling subtree recalc in
 291 // ContainerNode::checkForChildrenAdjacentRuleChanges.
 292 //
 293 // As we encounter a descendant type of combinator, the features only need to be checked
 294 // against descendants in the same subtree only. Hence wholeSubtree is reset to false.
 295
 296 void RuleFeatureSet::addFeaturesToInvalidationSets(const CSSSelector& selector, InvalidationSetFeatures& features)
 297 {
 298     for (const CSSSelector* current = &selector; current; current = current->tagHistory()) {
 299         if (DescendantInvalidationSet* invalidationSet = invalidationSetForSelector(*current)) {
 300             if (features.treeBoundaryCrossing)
 301                 invalidationSet->setTreeBoundaryCrossing();
 302             if (features.wholeSubtree) {
 303                 invalidationSet->setWholeSubtreeInvalid();
 304             } else {
 305                 if (!features.id.isEmpty())
 306                     invalidationSet->addId(features.id);
 307                 if (!features.tagName.isEmpty())
 308                     invalidationSet->addTagName(features.tagName);
 309                 for (Vector<AtomicString>::const_iterator it = features.classes.begin(); it != features.classes.end(); ++it)
 310                     invalidationSet->addClass(*it);
 311                 for (Vector<AtomicString>::const_iterator it = features.attributes.begin(); it != features.attributes.end(); ++it)
 312                     invalidationSet->addAttribute(*it);
 313                 if (features.customPseudoElement)
 314                     invalidationSet->setCustomPseudoInvalid();
 315             }
 316         } else {
 317             if (current->pseudoType() == CSSSelector::PseudoHost)
 318                 features.treeBoundaryCrossing = true;
 319             if (const CSSSelectorList* selectorList = current->selectorList()) {
 320                 ASSERT(current->pseudoType() == CSSSelector::PseudoHost || current->pseudoType() == CSSSelector::PseudoAny || current->pseudoType() == CSSSelector::PseudoNot);
 321                 for (const CSSSelector* selector = selectorList->first(); selector; selector = CSSSelectorList::next(*selector))
 322                     addFeaturesToInvalidationSets(*selector, features);
 323             }
 324         }
 325         switch (current->relation()) {
 326         case CSSSelector::SubSelector:
 327             break;
 328         case CSSSelector::ShadowPseudo:
 329         case CSSSelector::ShadowDeep:
 330             features.treeBoundaryCrossing = true;
 331             features.wholeSubtree = false;
 332             break;
 333         case CSSSelector::Descendant:
 334         case CSSSelector::Child:
 335             features.wholeSubtree = false;
 336             break;
 337         case CSSSelector::DirectAdjacent:
 338         case CSSSelector::IndirectAdjacent:
 339             features.wholeSubtree = true;
 340             break;
 341         }
 342     }
 343 }
 344
 345 void RuleFeatureSet::addContentAttr(const AtomicString& attributeName)
 346 {
 347     DescendantInvalidationSet& invalidationSet = ensureAttributeInvalidationSet(attributeName);
 348     invalidationSet.setWholeSubtreeInvalid();
 349 }
 350
 351 void RuleFeatureSet::collectFeaturesFromRuleData(const RuleData& ruleData)
 352 {
 353     FeatureMetadata metadata;
 354     InvalidationSetMode mode = updateInvalidationSets(ruleData.selector());
 355
 356     collectFeaturesFromSelector(ruleData.selector(), metadata, mode);
 357     m_metadata.add(metadata);
 358
 359     if (metadata.foundSiblingSelector)
 360         siblingRules.append(RuleFeature(ruleData.rule(), ruleData.selectorIndex(), ruleData.hasDocumentSecurityOrigin()));
 361     if (ruleData.containsUncommonAttributeSelector())
 362         uncommonAttributeRules.append(RuleFeature(ruleData.rule(), ruleData.selectorIndex(), ruleData.hasDocumentSecurityOrigin()));
 363 }
 364
 365 DescendantInvalidationSet& RuleFeatureSet::ensureClassInvalidationSet(const AtomicString& className)
 366 {
 367     InvalidationSetMap::AddResult addResult = m_classInvalidationSets.add(className, nullptr);
 368     if (addResult.isNewEntry)
 369         addResult.storedValue->value = DescendantInvalidationSet::create();
 370     return *addResult.storedValue->value;
 371 }
 372
 373 DescendantInvalidationSet& RuleFeatureSet::ensureAttributeInvalidationSet(const AtomicString& attributeName)
 374 {
 375     InvalidationSetMap::AddResult addResult = m_attributeInvalidationSets.add(attributeName, nullptr);
 376     if (addResult.isNewEntry)
 377         addResult.storedValue->value = DescendantInvalidationSet::create();
 378     return *addResult.storedValue->value;
 379 }
 380
 381 DescendantInvalidationSet& RuleFeatureSet::ensureIdInvalidationSet(const AtomicString& id)
 382 {
 383     InvalidationSetMap::AddResult addResult = m_idInvalidationSets.add(id, nullptr);
 384     if (addResult.isNewEntry)
 385         addResult.storedValue->value = DescendantInvalidationSet::create();
 386     return *addResult.storedValue->value;
 387 }
 388
 389 DescendantInvalidationSet& RuleFeatureSet::ensurePseudoInvalidationSet(CSSSelector::PseudoType pseudoType)
 390 {
 391     PseudoTypeInvalidationSetMap::AddResult addResult = m_pseudoInvalidationSets.add(pseudoType, nullptr);
 392     if (addResult.isNewEntry)
 393         addResult.storedValue->value = DescendantInvalidationSet::create();
 394     return *addResult.storedValue->value;
 395 }
 396
 397 void RuleFeatureSet::collectFeaturesFromSelector(const CSSSelector& selector, RuleFeatureSet::FeatureMetadata& metadata, InvalidationSetMode mode)
 398 {
 399     unsigned maxDirectAdjacentSelectors = 0;
 400
 401     for (const CSSSelector* current = &selector; current; current = current->tagHistory()) {
 402         if (mode != AddFeatures) {
 403             if (DescendantInvalidationSet* invalidationSet = invalidationSetForSelector(*current)) {
 404                 if (mode == UseSubtreeStyleChange)
 405                     invalidationSet->setWholeSubtreeInvalid();
 406             }
 407         }
 408         if (current->pseudoType() == CSSSelector::PseudoFirstLine)
 409             metadata.usesFirstLineRules = true;
 410         if (current->isDirectAdjacentSelector()) {
 411             maxDirectAdjacentSelectors++;
 412         } else if (maxDirectAdjacentSelectors) {
 413             if (maxDirectAdjacentSelectors > metadata.maxDirectAdjacentSelectors)
 414                 metadata.maxDirectAdjacentSelectors = maxDirectAdjacentSelectors;
 415             maxDirectAdjacentSelectors = 0;
 416         }
 417         if (current->isSiblingSelector())
 418             metadata.foundSiblingSelector = true;
 419
 420         collectFeaturesFromSelectorList(current->selectorList(), metadata, mode);
 421
 422         if (mode == UseLocalStyleChange && current->relation() != CSSSelector::SubSelector)
 423             mode = UseSubtreeStyleChange;
 424     }
 425
 426     ASSERT(!maxDirectAdjacentSelectors);
 427 }
 428
 429 void RuleFeatureSet::collectFeaturesFromSelectorList(const CSSSelectorList* selectorList, RuleFeatureSet::FeatureMetadata& metadata, InvalidationSetMode mode)
 430 {
 431     if (!selectorList)
 432         return;
 433
 434     for (const CSSSelector* selector = selectorList->first(); selector; selector = CSSSelectorList::next(*selector))
 435         collectFeaturesFromSelector(*selector, metadata, mode);
 436 }
 437
 438 void RuleFeatureSet::FeatureMetadata::add(const FeatureMetadata& other)
 439 {
 440     usesFirstLineRules = usesFirstLineRules || other.usesFirstLineRules;
 441     maxDirectAdjacentSelectors = std::max(maxDirectAdjacentSelectors, other.maxDirectAdjacentSelectors);
 442 }
 443
 444 void RuleFeatureSet::FeatureMetadata::clear()
 445 {
 446     usesFirstLineRules = false;
 447     foundSiblingSelector = false;
 448     maxDirectAdjacentSelectors = 0;
 449 }
 450
 451 void RuleFeatureSet::add(const RuleFeatureSet& other)
 452 {
 453     for (InvalidationSetMap::const_iterator it = other.m_classInvalidationSets.begin(); it != other.m_classInvalidationSets.end(); ++it)
 454         ensureClassInvalidationSet(it->key).combine(*it->value);
 455     for (InvalidationSetMap::const_iterator it = other.m_attributeInvalidationSets.begin(); it != other.m_attributeInvalidationSets.end(); ++it)
 456         ensureAttributeInvalidationSet(it->key).combine(*it->value);
 457     for (InvalidationSetMap::const_iterator it = other.m_idInvalidationSets.begin(); it != other.m_idInvalidationSets.end(); ++it)
 458         ensureIdInvalidationSet(it->key).combine(*it->value);
 459     for (PseudoTypeInvalidationSetMap::const_iterator it = other.m_pseudoInvalidationSets.begin(); it != other.m_pseudoInvalidationSets.end(); ++it)
 460         ensurePseudoInvalidationSet(static_cast<CSSSelector::PseudoType>(it->key)).combine(*it->value);
 461
 462     m_metadata.add(other.m_metadata);
 463
 464     siblingRules.appendVector(other.siblingRules);
 465     uncommonAttributeRules.appendVector(other.uncommonAttributeRules);
 466 }
 467
 468 void RuleFeatureSet::clear()
 469 {
 470     siblingRules.clear();
 471     uncommonAttributeRules.clear();
 472     m_metadata.clear();
 473     m_classInvalidationSets.clear();
 474     m_attributeInvalidationSets.clear();
 475     m_idInvalidationSets.clear();
 476     // We cannot clear m_styleInvalidator here, because the style invalidator might not
 477     // have been evaluated yet. If not yet, in StyleInvalidator, there exists some element
 478     // who has needsStyleInvlidation but does not have any invalidation list.
 479     // This makes Blink not to recalc style correctly. crbug.com/344729.
 480 }
 481
 482 void RuleFeatureSet::scheduleStyleInvalidationForClassChange(const SpaceSplitString& changedClasses, Element& element)
 483 {
 484     unsigned changedSize = changedClasses.size();
 485     for (unsigned i = 0; i < changedSize; ++i) {
 486         addClassToInvalidationSet(changedClasses[i], element);
 487     }
 488 }
 489
 490 void RuleFeatureSet::scheduleStyleInvalidationForClassChange(const SpaceSplitString& oldClasses, const SpaceSplitString& newClasses, Element& element)
 491 {
 492     if (!oldClasses.size()) {
 493         scheduleStyleInvalidationForClassChange(newClasses, element);
 494         return;
 495     }
 496
 497     // Class vectors tend to be very short. This is faster than using a hash table.
 498     BitVector remainingClassBits;
 499     remainingClassBits.ensureSize(oldClasses.size());
 500
 501     for (unsigned i = 0; i < newClasses.size(); ++i) {
 502         bool found = false;
 503         for (unsigned j = 0; j < oldClasses.size(); ++j) {
 504             if (newClasses[i] == oldClasses[j]) {
 505                 // Mark each class that is still in the newClasses so we can skip doing
 506                 // an n^2 search below when looking for removals. We can't break from
 507                 // this loop early since a class can appear more than once.
 508                 remainingClassBits.quickSet(j);
 509                 found = true;
 510             }
 511         }
 512         // Class was added.
 513         if (!found)
 514             addClassToInvalidationSet(newClasses[i], element);
 515     }
 516
 517     for (unsigned i = 0; i < oldClasses.size(); ++i) {
 518         if (remainingClassBits.quickGet(i))
 519             continue;
 520         // Class was removed.
 521         addClassToInvalidationSet(oldClasses[i], element);
 522     }
 523 }
 524
 525 void RuleFeatureSet::scheduleStyleInvalidationForAttributeChange(const QualifiedName& attributeName, Element& element)
 526 {
 527
 528     if (RefPtrWillBeRawPtr<DescendantInvalidationSet> invalidationSet = m_attributeInvalidationSets.get(attributeName.localName()))
 529         m_styleInvalidator.scheduleInvalidation(invalidationSet, element);
 530 }
 531
 532 void RuleFeatureSet::scheduleStyleInvalidationForIdChange(const AtomicString& oldId, const AtomicString& newId, Element& element)
 533 {
 534     if (!oldId.isEmpty()) {
 535         if (RefPtrWillBeRawPtr<DescendantInvalidationSet> invalidationSet = m_idInvalidationSets.get(oldId))
 536             m_styleInvalidator.scheduleInvalidation(invalidationSet, element);
 537     }
 538     if (!newId.isEmpty()) {
 539         if (RefPtrWillBeRawPtr<DescendantInvalidationSet> invalidationSet = m_idInvalidationSets.get(newId))
 540             m_styleInvalidator.scheduleInvalidation(invalidationSet, element);
 541     }
 542 }
 543
 544 void RuleFeatureSet::scheduleStyleInvalidationForPseudoChange(CSSSelector::PseudoType pseudo, Element& element)
 545 {
 546     if (RefPtrWillBeRawPtr<DescendantInvalidationSet> invalidationSet = m_pseudoInvalidationSets.get(pseudo))
 547         m_styleInvalidator.scheduleInvalidation(invalidationSet, element);
 548 }
 549
 550 void RuleFeatureSet::addClassToInvalidationSet(const AtomicString& className, Element& element)
 551 {
 552     if (RefPtrWillBeRawPtr<DescendantInvalidationSet> invalidationSet = m_classInvalidationSets.get(className))
 553         m_styleInvalidator.scheduleInvalidation(invalidationSet, element);
 554 }
 555
 556 StyleInvalidator& RuleFeatureSet::styleInvalidator()
 557 {
 558     return m_styleInvalidator;
 559 }
 560
 561 void RuleFeatureSet::trace(Visitor* visitor)
 562 {
 563 #if ENABLE(OILPAN)
 564     visitor->trace(siblingRules);
 565     visitor->trace(uncommonAttributeRules);
 566     visitor->trace(m_classInvalidationSets);
 567     visitor->trace(m_attributeInvalidationSets);
 568     visitor->trace(m_idInvalidationSets);
 569     visitor->trace(m_pseudoInvalidationSets);
 570     visitor->trace(m_styleInvalidator);
 571 #endif
 572 }
 573
 574 } // namespace blink