Home | History | Annotate | Download | only in css 
      1 /*
      2  * Copyright (C) 1999 Lars Knoll (knoll (at) kde.org)
      3  *           (C) 2004-2005 Allan Sandfeld Jensen (kde (at) carewolf.com)
      4  * Copyright (C) 2006, 2007 Nicholas Shanks (webkit (at) 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 (at) webkit.org>
      7  * Copyright (C) 2007, 2008 Eric Seidel <eric (at) 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
    575