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 "core/inspector/InspectorTraceEvents.h"
  41 #include "wtf/BitVector.h"
  42
  43 namespace blink {
  44
  45 #if ENABLE(ASSERT)
  46
  47 static bool supportsInvalidation(CSSSelector::Match match)
  48 {
  49     switch (match) {
  50     case CSSSelector::Tag:
  51     case CSSSelector::Id:
  52     case CSSSelector::Class:
  53     case CSSSelector::AttributeExact:
  54     case CSSSelector::AttributeSet:
  55     case CSSSelector::AttributeHyphen:
  56     case CSSSelector::AttributeList:
  57     case CSSSelector::AttributeContain:
  58     case CSSSelector::AttributeBegin:
  59     case CSSSelector::AttributeEnd:
  60         return true;
  61     case CSSSelector::Unknown:
  62     case CSSSelector::PagePseudoClass:
  63         // These should not appear in StyleRule selectors.
  64         ASSERT_NOT_REACHED();
  65         return false;
  66     default:
  67         // New match type added. Figure out if it needs a subtree invalidation or not.
  68         ASSERT_NOT_REACHED();
  69         return false;
  70     }
  71 }
  72
  73 static bool supportsInvalidation(CSSSelector::PseudoType type)
  74 {
  75     switch (type) {
  76     case CSSSelector::PseudoEmpty:
  77     case CSSSelector::PseudoFirstChild:
  78     case CSSSelector::PseudoFirstOfType:
  79     case CSSSelector::PseudoLastChild:
  80     case CSSSelector::PseudoLastOfType:
  81     case CSSSelector::PseudoOnlyChild:
  82     case CSSSelector::PseudoOnlyOfType:
  83     case CSSSelector::PseudoNthChild:
  84     case CSSSelector::PseudoNthOfType:
  85     case CSSSelector::PseudoNthLastChild:
  86     case CSSSelector::PseudoNthLastOfType:
  87     case CSSSelector::PseudoLink:
  88     case CSSSelector::PseudoVisited:
  89     case CSSSelector::PseudoAny:
  90     case CSSSelector::PseudoAnyLink:
  91     case CSSSelector::PseudoAutofill:
  92     case CSSSelector::PseudoHover:
  93     case CSSSelector::PseudoDrag:
  94     case CSSSelector::PseudoFocus:
  95     case CSSSelector::PseudoActive:
  96     case CSSSelector::PseudoChecked:
  97     case CSSSelector::PseudoEnabled:
  98     case CSSSelector::PseudoFullPageMedia:
  99     case CSSSelector::PseudoDefault:
 100     case CSSSelector::PseudoDisabled:
 101     case CSSSelector::PseudoOptional:
 102     case CSSSelector::PseudoRequired:
 103     case CSSSelector::PseudoReadOnly:
 104     case CSSSelector::PseudoReadWrite:
 105     case CSSSelector::PseudoValid:
 106     case CSSSelector::PseudoInvalid:
 107     case CSSSelector::PseudoIndeterminate:
 108     case CSSSelector::PseudoTarget:
 109     case CSSSelector::PseudoBefore:
 110     case CSSSelector::PseudoAfter:
 111     case CSSSelector::PseudoBackdrop:
 112     case CSSSelector::PseudoLang:
 113     case CSSSelector::PseudoNot:
 114     case CSSSelector::PseudoResizer:
 115     case CSSSelector::PseudoRoot:
 116     case CSSSelector::PseudoScope:
 117     case CSSSelector::PseudoScrollbar:
 118     case CSSSelector::PseudoScrollbarButton:
 119     case CSSSelector::PseudoScrollbarCorner:
 120     case CSSSelector::PseudoScrollbarThumb:
 121     case CSSSelector::PseudoScrollbarTrack:
 122     case CSSSelector::PseudoScrollbarTrackPiece:
 123     case CSSSelector::PseudoWindowInactive:
 124     case CSSSelector::PseudoSelection:
 125     case CSSSelector::PseudoCornerPresent:
 126     case CSSSelector::PseudoDecrement:
 127     case CSSSelector::PseudoIncrement:
 128     case CSSSelector::PseudoHorizontal:
 129     case CSSSelector::PseudoVertical:
 130     case CSSSelector::PseudoStart:
 131     case CSSSelector::PseudoEnd:
 132     case CSSSelector::PseudoDoubleButton:
 133     case CSSSelector::PseudoSingleButton:
 134     case CSSSelector::PseudoNoButton:
 135     case CSSSelector::PseudoFullScreen:
 136     case CSSSelector::PseudoFullScreenDocument:
 137     case CSSSelector::PseudoFullScreenAncestor:
 138     case CSSSelector::PseudoInRange:
 139     case CSSSelector::PseudoOutOfRange:
 140     case CSSSelector::PseudoWebKitCustomElement:
 141     case CSSSelector::PseudoUnresolved:
 142     case CSSSelector::PseudoContent:
 143     case CSSSelector::PseudoHost:
 144     case CSSSelector::PseudoShadow:
 145     case CSSSelector::PseudoListBox:
 146         return true;
 147     case CSSSelector::PseudoNotParsed:
 148     case CSSSelector::PseudoUnknown:
 149     case CSSSelector::PseudoLeftPage:
 150     case CSSSelector::PseudoRightPage:
 151     case CSSSelector::PseudoFirstPage:
 152         // These should not appear in StyleRule selectors.
 153         ASSERT_NOT_REACHED();
 154         return false;
 155     default:
 156         // New pseudo type added. Figure out if it needs a subtree invalidation or not.
 157         ASSERT_NOT_REACHED();
 158         return false;
 159     }
 160 }
 161
 162 #endif // ENABLE(ASSERT)
 163
 164 static bool requiresSubtreeInvalidation(const CSSSelector& selector)
 165 {
 166     if (!selector.matchesPseudoElement() && selector.match() != CSSSelector::PseudoClass) {
 167         ASSERT(supportsInvalidation(selector.match()));
 168         return false;
 169     }
 170
 171     switch (selector.pseudoType()) {
 172     case CSSSelector::PseudoFirstLine:
 173     case CSSSelector::PseudoFirstLetter:
 174     case CSSSelector::PseudoCue:
 175     case CSSSelector::PseudoFutureCue:
 176     case CSSSelector::PseudoPastCue:
 177     case CSSSelector::PseudoSpatialNavigationFocus:
 178         // FIXME: Most pseudo classes/elements above can be supported and moved
 179         // to assertSupportedPseudo(). Move on a case-by-case basis. If they
 180         // require subtree invalidation, document why.
 181     case CSSSelector::PseudoHostContext:
 182         // :host-context matches a shadow host, yet the simple selectors inside
 183         // :host-context matches an ancestor of the shadow host.
 184         return true;
 185     default:
 186         ASSERT(supportsInvalidation(selector.pseudoType()));
 187         return false;
 188     }
 189 }
 190
 191 RuleFeature::RuleFeature(StyleRule* rule, unsigned selectorIndex, bool hasDocumentSecurityOrigin)
 192     : rule(rule)
 193     , selectorIndex(selectorIndex)
 194     , hasDocumentSecurityOrigin(hasDocumentSecurityOrigin)
 195 {
 196 }
 197
 198 void RuleFeature::trace(Visitor* visitor)
 199 {
 200     visitor->trace(rule);
 201 }
 202
 203 // This method is somewhat conservative in what it accepts.
 204 RuleFeatureSet::InvalidationSetMode RuleFeatureSet::invalidationSetModeForSelector(const CSSSelector& selector)
 205 {
 206     bool foundCombinator = false;
 207     bool foundIdent = false;
 208     for (const CSSSelector* component = &selector; component; component = component->tagHistory()) {
 209
 210         if (component->match() == CSSSelector::Class || component->match() == CSSSelector::Id
 211             || (component->match() == CSSSelector::Tag && component->tagQName().localName() != starAtom)
 212             || component->isAttributeSelector() || component->isCustomPseudoElement()) {
 213             if (!foundCombinator) {
 214                 // We have found an invalidation set feature in the rightmost compound selector.
 215                 foundIdent = true;
 216             }
 217         } else if (component->pseudoType() == CSSSelector::PseudoNot
 218             || component->pseudoType() == CSSSelector::PseudoHost
 219             || component->pseudoType() == CSSSelector::PseudoAny) {
 220             if (const CSSSelectorList* selectorList = component->selectorList()) {
 221                 // Features inside :not() are not added to the feature set, so consider it a universal selector.
 222                 bool foundUniversal = component->pseudoType() == CSSSelector::PseudoNot;
 223                 for (const CSSSelector* selector = selectorList->first(); selector; selector = CSSSelectorList::next(*selector)) {
 224                     // Find the invalidation set mode for each of the selectors in the selector list
 225                     // of a :not(), :host(), etc. For instance, ".x :-webkit-any(.a, .b)" yields an
 226                     // AddFeatures mode for both ".a" and ".b". ":-webkit-any(.a, *)" yields AddFeatures
 227                     // for ".a", but UseSubtreeStyleChange for "*". One sub-selector without invalidation
 228                     // set features is sufficient to cause the selector to be a universal selector as far
 229                     // the invalidation set is concerned.
 230                     InvalidationSetMode subSelectorMode = invalidationSetModeForSelector(*selector);
 231
 232                     // The sub-selector contained something unskippable, fall back to whole subtree
 233                     // recalcs in collectFeaturesFromSelector. subSelectorMode will return
 234                     // UseSubtreeStyleChange since there are no combinators inside the selector list,
 235                     // so translate it to UseLocalStyleChange if a combinator has been seen in the
 236                     // outer context.
 237                     //
 238                     // FIXME: Is UseSubtreeStyleChange ever needed as input to collectFeaturesFromSelector?
 239                     // That is, are there any selectors for which we need to use SubtreeStyleChange for
 240                     // changing features when present in the rightmost compound selector?
 241                     if (subSelectorMode == UseSubtreeStyleChange)
 242                         return foundCombinator ? UseLocalStyleChange : UseSubtreeStyleChange;
 243
 244                     // We found no features in the sub-selector, only skippable ones (foundIdent was
 245                     // false at the end of this method). That is a universal selector as far as the
 246                     // invalidation set is concerned.
 247                     if (subSelectorMode == UseLocalStyleChange)
 248                         foundUniversal = true;
 249                 }
 250                 if (!foundUniversal && !foundCombinator) {
 251                     // All sub-selectors contained invalidation set features and
 252                     // we are in the rightmost compound selector.
 253                     foundIdent = true;
 254                 }
 255             }
 256         } else if (requiresSubtreeInvalidation(*component)) {
 257             return foundCombinator ? UseLocalStyleChange : UseSubtreeStyleChange;
 258         }
 259         if (component->relation() != CSSSelector::SubSelector)
 260             foundCombinator = true;
 261     }
 262     return foundIdent ? AddFeatures : UseLocalStyleChange;
 263 }
 264
 265 void RuleFeatureSet::extractInvalidationSetFeature(const CSSSelector& selector, InvalidationSetFeatures& features)
 266 {
 267     if (selector.match() == CSSSelector::Tag)
 268         features.tagName = selector.tagQName().localName();
 269     else if (selector.match() == CSSSelector::Id)
 270         features.id = selector.value();
 271     else if (selector.match() == CSSSelector::Class)
 272         features.classes.append(selector.value());
 273     else if (selector.isAttributeSelector())
 274         features.attributes.append(selector.attribute().localName());
 275     else if (selector.isCustomPseudoElement())
 276         features.customPseudoElement = true;
 277 }
 278
 279 RuleFeatureSet::RuleFeatureSet()
 280 {
 281 }
 282
 283 RuleFeatureSet::~RuleFeatureSet()
 284 {
 285 }
 286
 287 DescendantInvalidationSet* RuleFeatureSet::invalidationSetForSelector(const CSSSelector& selector)
 288 {
 289     if (selector.match() == CSSSelector::Class)
 290         return &ensureClassInvalidationSet(selector.value());
 291     if (selector.isAttributeSelector())
 292         return &ensureAttributeInvalidationSet(selector.attribute().localName());
 293     if (selector.match() == CSSSelector::Id)
 294         return &ensureIdInvalidationSet(selector.value());
 295     if (selector.match() == CSSSelector::PseudoClass) {
 296         switch (selector.pseudoType()) {
 297         case CSSSelector::PseudoEmpty:
 298         case CSSSelector::PseudoLink:
 299         case CSSSelector::PseudoVisited:
 300         case CSSSelector::PseudoAutofill:
 301         case CSSSelector::PseudoHover:
 302         case CSSSelector::PseudoFocus:
 303         case CSSSelector::PseudoActive:
 304         case CSSSelector::PseudoChecked:
 305         case CSSSelector::PseudoEnabled:
 306         case CSSSelector::PseudoDisabled:
 307         case CSSSelector::PseudoOptional:
 308         case CSSSelector::PseudoRequired:
 309         case CSSSelector::PseudoValid:
 310         case CSSSelector::PseudoInvalid:
 311         case CSSSelector::PseudoIndeterminate:
 312         case CSSSelector::PseudoTarget:
 313             return &ensurePseudoInvalidationSet(selector.pseudoType());
 314         default:
 315             break;
 316         }
 317     }
 318     return 0;
 319 }
 320
 321 // Given a selector, update the descendant invalidation sets for the features found
 322 // in the selector. The first step is to extract the features from the rightmost
 323 // compound selector (extractInvalidationSetFeatures). Secondly, those features will be
 324 // added to the invalidation sets for the features found in the other compound selectors
 325 // (addFeaturesToInvalidationSets).
 326
 327 RuleFeatureSet::InvalidationSetMode RuleFeatureSet::updateInvalidationSets(const CSSSelector& selector)
 328 {
 329     InvalidationSetMode mode = invalidationSetModeForSelector(selector);
 330     if (mode != AddFeatures)
 331         return mode;
 332
 333     InvalidationSetFeatures features;
 334     if (const CSSSelector* current = extractInvalidationSetFeatures(selector, features, false))
 335         addFeaturesToInvalidationSets(*current, features);
 336     return AddFeatures;
 337 }
 338
 339 const CSSSelector* RuleFeatureSet::extractInvalidationSetFeatures(const CSSSelector& selector, InvalidationSetFeatures& features, bool negated)
 340 {
 341     for (const CSSSelector* current = &selector; current; current = current->tagHistory()) {
 342         if (!negated)
 343             extractInvalidationSetFeature(*current, features);
 344         // Initialize the entry in the invalidation set map, if supported.
 345         invalidationSetForSelector(*current);
 346         if (current->pseudoType() == CSSSelector::PseudoHost || current->pseudoType() == CSSSelector::PseudoAny || current->pseudoType() == CSSSelector::PseudoNot) {
 347             if (const CSSSelectorList* selectorList = current->selectorList()) {
 348                 for (const CSSSelector* selector = selectorList->first(); selector; selector = CSSSelectorList::next(*selector))
 349                     extractInvalidationSetFeatures(*selector, features, current->pseudoType() == CSSSelector::PseudoNot);
 350             }
 351         }
 352
 353         if (current->relation() == CSSSelector::SubSelector)
 354             continue;
 355
 356         features.treeBoundaryCrossing = current->isShadowSelector();
 357         features.adjacent = current->isAdjacentSelector();
 358         return current->tagHistory();
 359     }
 360     return 0;
 361 }
 362
 363 // Add features extracted from the rightmost compound selector to descendant invalidation
 364 // sets for features found in other compound selectors.
 365 //
 366 // Style invalidation is currently supported for descendants only, not for sibling subtrees.
 367 // We use wholeSubtree invalidation for features found left of adjacent combinators as
 368 // SubtreeStyleChange will force sibling subtree recalc in
 369 // ContainerNode::checkForChildrenAdjacentRuleChanges.
 370 //
 371 // As we encounter a descendant type of combinator, the features only need to be checked
 372 // against descendants in the same subtree only. features.adjacent is set to false, and
 373 // we start adding features instead of calling setWholeSubtreeInvalid.
 374
 375 void RuleFeatureSet::addFeaturesToInvalidationSet(DescendantInvalidationSet& invalidationSet, const InvalidationSetFeatures& features)
 376 {
 377     if (features.treeBoundaryCrossing)
 378         invalidationSet.setTreeBoundaryCrossing();
 379     if (features.insertionPointCrossing)
 380         invalidationSet.setInsertionPointCrossing();
 381     if (features.adjacent) {
 382         invalidationSet.setWholeSubtreeInvalid();
 383         return;
 384     }
 385     if (!features.id.isEmpty())
 386         invalidationSet.addId(features.id);
 387     if (!features.tagName.isEmpty())
 388         invalidationSet.addTagName(features.tagName);
 389     for (const auto& className : features.classes)
 390         invalidationSet.addClass(className);
 391     for (const auto& attribute : features.attributes)
 392         invalidationSet.addAttribute(attribute);
 393     if (features.customPseudoElement)
 394         invalidationSet.setCustomPseudoInvalid();
 395 }
 396
 397 void RuleFeatureSet::addFeaturesToInvalidationSets(const CSSSelector& selector, InvalidationSetFeatures& features)
 398 {
 399     for (const CSSSelector* current = &selector; current; current = current->tagHistory()) {
 400         if (DescendantInvalidationSet* invalidationSet = invalidationSetForSelector(*current)) {
 401             addFeaturesToInvalidationSet(*invalidationSet, features);
 402         } else {
 403             if (current->isTreeBoundaryCrossing())
 404                 features.treeBoundaryCrossing = true;
 405             if (current->isInsertionPointCrossing())
 406                 features.insertionPointCrossing = true;
 407             if (const CSSSelectorList* selectorList = current->selectorList()) {
 408                 ASSERT(current->pseudoType() == CSSSelector::PseudoHost || current->pseudoType() == CSSSelector::PseudoAny || current->pseudoType() == CSSSelector::PseudoNot);
 409                 for (const CSSSelector* selector = selectorList->first(); selector; selector = CSSSelectorList::next(*selector))
 410                     addFeaturesToInvalidationSets(*selector, features);
 411             }
 412         }
 413
 414         if (current->relation() == CSSSelector::SubSelector)
 415             continue;
 416
 417         if (current->isShadowSelector())
 418             features.treeBoundaryCrossing = true;
 419
 420         features.adjacent = current->isAdjacentSelector();
 421     }
 422 }
 423
 424 void RuleFeatureSet::addContentAttr(const AtomicString& attributeName)
 425 {
 426     ensureAttributeInvalidationSet(attributeName);
 427 }
 428
 429 void RuleFeatureSet::collectFeaturesFromRuleData(const RuleData& ruleData)
 430 {
 431     FeatureMetadata metadata;
 432     InvalidationSetMode mode = updateInvalidationSets(ruleData.selector());
 433
 434     collectFeaturesFromSelector(ruleData.selector(), metadata, mode);
 435     m_metadata.add(metadata);
 436
 437     if (metadata.foundSiblingSelector)
 438         siblingRules.append(RuleFeature(ruleData.rule(), ruleData.selectorIndex(), ruleData.hasDocumentSecurityOrigin()));
 439     if (ruleData.containsUncommonAttributeSelector())
 440         uncommonAttributeRules.append(RuleFeature(ruleData.rule(), ruleData.selectorIndex(), ruleData.hasDocumentSecurityOrigin()));
 441 }
 442
 443 DescendantInvalidationSet& RuleFeatureSet::ensureClassInvalidationSet(const AtomicString& className)
 444 {
 445     InvalidationSetMap::AddResult addResult = m_classInvalidationSets.add(className, nullptr);
 446     if (addResult.isNewEntry)
 447         addResult.storedValue->value = DescendantInvalidationSet::create();
 448     return *addResult.storedValue->value;
 449 }
 450
 451 DescendantInvalidationSet& RuleFeatureSet::ensureAttributeInvalidationSet(const AtomicString& attributeName)
 452 {
 453     InvalidationSetMap::AddResult addResult = m_attributeInvalidationSets.add(attributeName, nullptr);
 454     if (addResult.isNewEntry)
 455         addResult.storedValue->value = DescendantInvalidationSet::create();
 456     return *addResult.storedValue->value;
 457 }
 458
 459 DescendantInvalidationSet& RuleFeatureSet::ensureIdInvalidationSet(const AtomicString& id)
 460 {
 461     InvalidationSetMap::AddResult addResult = m_idInvalidationSets.add(id, nullptr);
 462     if (addResult.isNewEntry)
 463         addResult.storedValue->value = DescendantInvalidationSet::create();
 464     return *addResult.storedValue->value;
 465 }
 466
 467 DescendantInvalidationSet& RuleFeatureSet::ensurePseudoInvalidationSet(CSSSelector::PseudoType pseudoType)
 468 {
 469     PseudoTypeInvalidationSetMap::AddResult addResult = m_pseudoInvalidationSets.add(pseudoType, nullptr);
 470     if (addResult.isNewEntry)
 471         addResult.storedValue->value = DescendantInvalidationSet::create();
 472     return *addResult.storedValue->value;
 473 }
 474
 475 void RuleFeatureSet::collectFeaturesFromSelector(const CSSSelector& selector, RuleFeatureSet::FeatureMetadata& metadata, InvalidationSetMode mode)
 476 {
 477     unsigned maxDirectAdjacentSelectors = 0;
 478
 479     for (const CSSSelector* current = &selector; current; current = current->tagHistory()) {
 480         if (mode != AddFeatures) {
 481             if (DescendantInvalidationSet* invalidationSet = invalidationSetForSelector(*current)) {
 482                 if (mode == UseSubtreeStyleChange)
 483                     invalidationSet->setWholeSubtreeInvalid();
 484             }
 485         }
 486         if (current->pseudoType() == CSSSelector::PseudoFirstLine)
 487             metadata.usesFirstLineRules = true;
 488         if (current->isDirectAdjacentSelector()) {
 489             maxDirectAdjacentSelectors++;
 490         } else if (maxDirectAdjacentSelectors) {
 491             if (maxDirectAdjacentSelectors > metadata.maxDirectAdjacentSelectors)
 492                 metadata.maxDirectAdjacentSelectors = maxDirectAdjacentSelectors;
 493             maxDirectAdjacentSelectors = 0;
 494         }
 495         if (current->isSiblingSelector())
 496             metadata.foundSiblingSelector = true;
 497
 498         collectFeaturesFromSelectorList(current->selectorList(), metadata, mode);
 499
 500         if (mode == UseLocalStyleChange && current->relation() != CSSSelector::SubSelector)
 501             mode = UseSubtreeStyleChange;
 502     }
 503
 504     ASSERT(!maxDirectAdjacentSelectors);
 505 }
 506
 507 void RuleFeatureSet::collectFeaturesFromSelectorList(const CSSSelectorList* selectorList, RuleFeatureSet::FeatureMetadata& metadata, InvalidationSetMode mode)
 508 {
 509     if (!selectorList)
 510         return;
 511
 512     for (const CSSSelector* selector = selectorList->first(); selector; selector = CSSSelectorList::next(*selector))
 513         collectFeaturesFromSelector(*selector, metadata, mode);
 514 }
 515
 516 void RuleFeatureSet::FeatureMetadata::add(const FeatureMetadata& other)
 517 {
 518     usesFirstLineRules = usesFirstLineRules || other.usesFirstLineRules;
 519     maxDirectAdjacentSelectors = std::max(maxDirectAdjacentSelectors, other.maxDirectAdjacentSelectors);
 520 }
 521
 522 void RuleFeatureSet::FeatureMetadata::clear()
 523 {
 524     usesFirstLineRules = false;
 525     foundSiblingSelector = false;
 526     maxDirectAdjacentSelectors = 0;
 527 }
 528
 529 void RuleFeatureSet::add(const RuleFeatureSet& other)
 530 {
 531     for (const auto& invalidationSet : other.m_classInvalidationSets)
 532         ensureClassInvalidationSet(invalidationSet.key).combine(*invalidationSet.value);
 533     for (const auto& invalidationSet : other.m_attributeInvalidationSets)
 534         ensureAttributeInvalidationSet(invalidationSet.key).combine(*invalidationSet.value);
 535     for (const auto& invalidationSet : other.m_idInvalidationSets)
 536         ensureIdInvalidationSet(invalidationSet.key).combine(*invalidationSet.value);
 537     for (const auto& invalidationSet : other.m_pseudoInvalidationSets)
 538         ensurePseudoInvalidationSet(static_cast<CSSSelector::PseudoType>(invalidationSet.key)).combine(*invalidationSet.value);
 539
 540     m_metadata.add(other.m_metadata);
 541
 542     siblingRules.appendVector(other.siblingRules);
 543     uncommonAttributeRules.appendVector(other.uncommonAttributeRules);
 544 }
 545
 546 void RuleFeatureSet::clear()
 547 {
 548     siblingRules.clear();
 549     uncommonAttributeRules.clear();
 550     m_metadata.clear();
 551     m_classInvalidationSets.clear();
 552     m_attributeInvalidationSets.clear();
 553     m_idInvalidationSets.clear();
 554     // We cannot clear m_styleInvalidator here, because the style invalidator might not
 555     // have been evaluated yet. If not yet, in StyleInvalidator, there exists some element
 556     // who has needsStyleInvlidation but does not have any invalidation list.
 557     // This makes Blink not to recalc style correctly. crbug.com/344729.
 558 }
 559
 560 void RuleFeatureSet::scheduleStyleInvalidationForClassChange(const SpaceSplitString& changedClasses, Element& element)
 561 {
 562     unsigned changedSize = changedClasses.size();
 563     for (unsigned i = 0; i < changedSize; ++i) {
 564         addClassToInvalidationSet(changedClasses[i], element);
 565     }
 566 }
 567
 568 void RuleFeatureSet::scheduleStyleInvalidationForClassChange(const SpaceSplitString& oldClasses, const SpaceSplitString& newClasses, Element& element)
 569 {
 570     if (!oldClasses.size()) {
 571         scheduleStyleInvalidationForClassChange(newClasses, element);
 572         return;
 573     }
 574
 575     // Class vectors tend to be very short. This is faster than using a hash table.
 576     BitVector remainingClassBits;
 577     remainingClassBits.ensureSize(oldClasses.size());
 578
 579     for (unsigned i = 0; i < newClasses.size(); ++i) {
 580         bool found = false;
 581         for (unsigned j = 0; j < oldClasses.size(); ++j) {
 582             if (newClasses[i] == oldClasses[j]) {
 583                 // Mark each class that is still in the newClasses so we can skip doing
 584                 // an n^2 search below when looking for removals. We can't break from
 585                 // this loop early since a class can appear more than once.
 586                 remainingClassBits.quickSet(j);
 587                 found = true;
 588             }
 589         }
 590         // Class was added.
 591         if (!found)
 592             addClassToInvalidationSet(newClasses[i], element);
 593     }
 594
 595     for (unsigned i = 0; i < oldClasses.size(); ++i) {
 596         if (remainingClassBits.quickGet(i))
 597             continue;
 598         // Class was removed.
 599         addClassToInvalidationSet(oldClasses[i], element);
 600     }
 601 }
 602
 603 void RuleFeatureSet::scheduleStyleInvalidationForAttributeChange(const QualifiedName& attributeName, Element& element)
 604 {
 605     if (RefPtrWillBeRawPtr<DescendantInvalidationSet> invalidationSet = m_attributeInvalidationSets.get(attributeName.localName())) {
 606         TRACE_SCHEDULE_STYLE_INVALIDATION(element, *invalidationSet, attributeChange, attributeName);
 607         m_styleInvalidator.scheduleInvalidation(invalidationSet, element);
 608     }
 609 }
 610
 611 void RuleFeatureSet::scheduleStyleInvalidationForIdChange(const AtomicString& oldId, const AtomicString& newId, Element& element)
 612 {
 613     if (!oldId.isEmpty()) {
 614         if (RefPtrWillBeRawPtr<DescendantInvalidationSet> invalidationSet = m_idInvalidationSets.get(oldId)) {
 615             TRACE_SCHEDULE_STYLE_INVALIDATION(element, *invalidationSet, idChange, oldId);
 616             m_styleInvalidator.scheduleInvalidation(invalidationSet, element);
 617         }
 618     }
 619     if (!newId.isEmpty()) {
 620         if (RefPtrWillBeRawPtr<DescendantInvalidationSet> invalidationSet = m_idInvalidationSets.get(newId)) {
 621             TRACE_SCHEDULE_STYLE_INVALIDATION(element, *invalidationSet, idChange, newId);
 622             m_styleInvalidator.scheduleInvalidation(invalidationSet, element);
 623         }
 624     }
 625 }
 626
 627 void RuleFeatureSet::scheduleStyleInvalidationForPseudoChange(CSSSelector::PseudoType pseudo, Element& element)
 628 {
 629     if (RefPtrWillBeRawPtr<DescendantInvalidationSet> invalidationSet = m_pseudoInvalidationSets.get(pseudo)) {
 630         TRACE_SCHEDULE_STYLE_INVALIDATION(element, *invalidationSet, pseudoChange, pseudo);
 631         m_styleInvalidator.scheduleInvalidation(invalidationSet, element);
 632     }
 633 }
 634
 635 inline void RuleFeatureSet::addClassToInvalidationSet(const AtomicString& className, Element& element)
 636 {
 637     if (RefPtrWillBeRawPtr<DescendantInvalidationSet> invalidationSet = m_classInvalidationSets.get(className)) {
 638         TRACE_SCHEDULE_STYLE_INVALIDATION(element, *invalidationSet, classChange, className);
 639         m_styleInvalidator.scheduleInvalidation(invalidationSet, element);
 640     }
 641 }
 642
 643 StyleInvalidator& RuleFeatureSet::styleInvalidator()
 644 {
 645     return m_styleInvalidator;
 646 }
 647
 648 void RuleFeatureSet::trace(Visitor* visitor)
 649 {
 650 #if ENABLE(OILPAN)
 651     visitor->trace(siblingRules);
 652     visitor->trace(uncommonAttributeRules);
 653     visitor->trace(m_classInvalidationSets);
 654     visitor->trace(m_attributeInvalidationSets);
 655     visitor->trace(m_idInvalidationSets);
 656     visitor->trace(m_pseudoInvalidationSets);
 657     visitor->trace(m_styleInvalidator);
 658 #endif
 659 }
 660
 661 } // namespace blink