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 "HTMLNames.h"
  33 #include "RuntimeEnabledFeatures.h"
  34 #include "core/css/CSSSelector.h"
  35 #include "core/css/CSSSelectorList.h"
  36 #include "core/css/RuleSet.h"
  37 #include "core/dom/Element.h"
  38 #include "core/dom/Node.h"
  39 #include "wtf/BitVector.h"
  40
  41 namespace WebCore {
  42
  43 static bool isSkippableComponentForInvalidation(const CSSSelector& selector)
  44 {
  45     if (selector.m_match == CSSSelector::Tag
  46         || selector.m_match == CSSSelector::Id
  47         || selector.isAttributeSelector())
  48         return true;
  49     if (selector.m_match == CSSSelector::PseudoElement) {
  50         switch (selector.pseudoType()) {
  51         case CSSSelector::PseudoBefore:
  52         case CSSSelector::PseudoAfter:
  53         case CSSSelector::PseudoBackdrop:
  54         case CSSSelector::PseudoShadow:
  55             return true;
  56         default:
  57             return false;
  58         }
  59     }
  60     if (selector.m_match != CSSSelector::PseudoClass)
  61         return false;
  62     switch (selector.pseudoType()) {
  63     case CSSSelector::PseudoEmpty:
  64     case CSSSelector::PseudoFirstChild:
  65     case CSSSelector::PseudoFirstOfType:
  66     case CSSSelector::PseudoLastChild:
  67     case CSSSelector::PseudoLastOfType:
  68     case CSSSelector::PseudoOnlyChild:
  69     case CSSSelector::PseudoOnlyOfType:
  70     case CSSSelector::PseudoNthChild:
  71     case CSSSelector::PseudoNthOfType:
  72     case CSSSelector::PseudoNthLastChild:
  73     case CSSSelector::PseudoNthLastOfType:
  74     case CSSSelector::PseudoLink:
  75     case CSSSelector::PseudoVisited:
  76     case CSSSelector::PseudoAnyLink:
  77     case CSSSelector::PseudoHover:
  78     case CSSSelector::PseudoDrag:
  79     case CSSSelector::PseudoFocus:
  80     case CSSSelector::PseudoActive:
  81     case CSSSelector::PseudoChecked:
  82     case CSSSelector::PseudoEnabled:
  83     case CSSSelector::PseudoDefault:
  84     case CSSSelector::PseudoDisabled:
  85     case CSSSelector::PseudoOptional:
  86     case CSSSelector::PseudoRequired:
  87     case CSSSelector::PseudoReadOnly:
  88     case CSSSelector::PseudoReadWrite:
  89     case CSSSelector::PseudoValid:
  90     case CSSSelector::PseudoInvalid:
  91     case CSSSelector::PseudoIndeterminate:
  92     case CSSSelector::PseudoTarget:
  93     case CSSSelector::PseudoLang:
  94     case CSSSelector::PseudoRoot:
  95     case CSSSelector::PseudoScope:
  96     case CSSSelector::PseudoInRange:
  97     case CSSSelector::PseudoOutOfRange:
  98     case CSSSelector::PseudoUnresolved:
  99         return true;
 100     default:
 101         return false;
 102     }
 103 }
 104
 105 // This method is somewhat conservative in what it accepts.
 106 RuleFeatureSet::InvalidationSetMode RuleFeatureSet::invalidationSetModeForSelector(const CSSSelector& selector)
 107 {
 108     bool foundDescendantRelation = false;
 109     bool foundIdent = false;
 110     for (const CSSSelector* component = &selector; component; component = component->tagHistory()) {
 111
 112         // FIXME: next up: Tag and Id.
 113         if (component->m_match == CSSSelector::Class || component->isAttributeSelector()) {
 114             if (!foundDescendantRelation)
 115                 foundIdent = true;
 116         } else if (component->pseudoType() == CSSSelector::PseudoHost || component->pseudoType() == CSSSelector::PseudoAny) {
 117             if (const CSSSelectorList* selectorList = component->selectorList()) {
 118                 for (const CSSSelector* selector = selectorList->first(); selector; selector = CSSSelectorList::next(*selector)) {
 119                     InvalidationSetMode hostMode = invalidationSetModeForSelector(*selector);
 120                     if (hostMode == UseSubtreeStyleChange)
 121                         return foundDescendantRelation ? UseLocalStyleChange : UseSubtreeStyleChange;
 122                     if (!foundDescendantRelation && hostMode == AddFeatures)
 123                         foundIdent = true;
 124                 }
 125             }
 126         } else if (!isSkippableComponentForInvalidation(*component)) {
 127             return foundDescendantRelation ? UseLocalStyleChange : UseSubtreeStyleChange;
 128         }
 129         switch (component->relation()) {
 130         case CSSSelector::Descendant:
 131         case CSSSelector::Child:
 132         case CSSSelector::ShadowPseudo:
 133         case CSSSelector::ShadowDeep:
 134             foundDescendantRelation = true;
 135             // Fall through!
 136         case CSSSelector::SubSelector:
 137             continue;
 138         default:
 139             return UseLocalStyleChange;
 140         }
 141     }
 142     return foundIdent ? AddFeatures : UseLocalStyleChange;
 143 }
 144
 145 void RuleFeatureSet::extractInvalidationSetFeature(const CSSSelector& selector, InvalidationSetFeatures& features)
 146 {
 147     if (selector.m_match == CSSSelector::Tag)
 148         features.tagName = selector.tagQName().localName();
 149     else if (selector.m_match == CSSSelector::Id)
 150         features.id = selector.value();
 151     else if (selector.m_match == CSSSelector::Class)
 152         features.classes.append(selector.value());
 153     else if (selector.isAttributeSelector())
 154         features.attributes.append(selector.attribute().localName());
 155 }
 156
 157 RuleFeatureSet::RuleFeatureSet()
 158     : m_targetedStyleRecalcEnabled(RuntimeEnabledFeatures::targetedStyleRecalcEnabled())
 159 {
 160 }
 161
 162 DescendantInvalidationSet* RuleFeatureSet::invalidationSetForSelector(const CSSSelector& selector)
 163 {
 164     if (selector.m_match == CSSSelector::Class)
 165         return &ensureClassInvalidationSet(selector.value());
 166     if (selector.isAttributeSelector())
 167         return &ensureAttributeInvalidationSet(selector.attribute().localName());
 168     return 0;
 169 }
 170
 171 RuleFeatureSet::InvalidationSetMode RuleFeatureSet::updateInvalidationSets(const CSSSelector& selector)
 172 {
 173     InvalidationSetMode mode = invalidationSetModeForSelector(selector);
 174     if (mode != AddFeatures)
 175         return mode;
 176
 177     InvalidationSetFeatures features;
 178     const CSSSelector* current = extractInvalidationSetFeatures(selector, features);
 179     if (current)
 180         current = current->tagHistory();
 181
 182     if (current)
 183         addFeaturesToInvalidationSets(*current, features);
 184     return AddFeatures;
 185 }
 186
 187 const CSSSelector* RuleFeatureSet::extractInvalidationSetFeatures(const CSSSelector& selector, InvalidationSetFeatures& features)
 188 {
 189     const CSSSelector* lastSelector = &selector;
 190     for (; lastSelector; lastSelector = lastSelector->tagHistory()) {
 191         extractInvalidationSetFeature(*lastSelector, features);
 192         // Initialize the entry in the invalidation set map, if supported.
 193         invalidationSetForSelector(*lastSelector);
 194         if (lastSelector->pseudoType() == CSSSelector::PseudoHost || lastSelector->pseudoType() == CSSSelector::PseudoAny) {
 195             if (const CSSSelectorList* selectorList = lastSelector->selectorList()) {
 196                 for (const CSSSelector* selector = selectorList->first(); selector; selector = CSSSelectorList::next(*selector))
 197                     extractInvalidationSetFeatures(*selector, features);
 198             }
 199         }
 200
 201         if (lastSelector->relation() != CSSSelector::SubSelector)
 202             break;
 203     }
 204     return lastSelector;
 205 }
 206
 207 void RuleFeatureSet::addFeaturesToInvalidationSets(const CSSSelector& selector, const InvalidationSetFeatures& features)
 208 {
 209     for (const CSSSelector* current = &selector; current; current = current->tagHistory()) {
 210         if (DescendantInvalidationSet* invalidationSet = invalidationSetForSelector(*current)) {
 211             if (!features.id.isEmpty())
 212                 invalidationSet->addId(features.id);
 213             if (!features.tagName.isEmpty())
 214                 invalidationSet->addTagName(features.tagName);
 215             for (Vector<AtomicString>::const_iterator it = features.classes.begin(); it != features.classes.end(); ++it)
 216                 invalidationSet->addClass(*it);
 217             for (Vector<AtomicString>::const_iterator it = features.attributes.begin(); it != features.attributes.end(); ++it)
 218                 invalidationSet->addAttribute(*it);
 219         } else if (current->pseudoType() == CSSSelector::PseudoHost || current->pseudoType() == CSSSelector::PseudoAny) {
 220             if (const CSSSelectorList* selectorList = current->selectorList()) {
 221                 for (const CSSSelector* selector = selectorList->first(); selector; selector = CSSSelectorList::next(*selector))
 222                     addFeaturesToInvalidationSets(*selector, features);
 223             }
 224         }
 225     }
 226 }
 227
 228 void RuleFeatureSet::addContentAttr(const AtomicString& attributeName)
 229 {
 230     DescendantInvalidationSet& invalidationSet = ensureAttributeInvalidationSet(attributeName);
 231     invalidationSet.setWholeSubtreeInvalid();
 232 }
 233
 234 void RuleFeatureSet::collectFeaturesFromRuleData(const RuleData& ruleData)
 235 {
 236     FeatureMetadata metadata;
 237     InvalidationSetMode mode = UseSubtreeStyleChange;
 238     if (m_targetedStyleRecalcEnabled)
 239         mode = updateInvalidationSets(ruleData.selector());
 240
 241     collectFeaturesFromSelector(ruleData.selector(), metadata, mode);
 242     m_metadata.add(metadata);
 243
 244     if (metadata.foundSiblingSelector)
 245         siblingRules.append(RuleFeature(ruleData.rule(), ruleData.selectorIndex(), ruleData.hasDocumentSecurityOrigin()));
 246     if (ruleData.containsUncommonAttributeSelector())
 247         uncommonAttributeRules.append(RuleFeature(ruleData.rule(), ruleData.selectorIndex(), ruleData.hasDocumentSecurityOrigin()));
 248 }
 249
 250 DescendantInvalidationSet& RuleFeatureSet::ensureClassInvalidationSet(const AtomicString& className)
 251 {
 252     InvalidationSetMap::AddResult addResult = m_classInvalidationSets.add(className, nullptr);
 253     if (addResult.isNewEntry)
 254         addResult.storedValue->value = DescendantInvalidationSet::create();
 255     return *addResult.storedValue->value;
 256 }
 257
 258 DescendantInvalidationSet& RuleFeatureSet::ensureAttributeInvalidationSet(const AtomicString& attributeName)
 259 {
 260     InvalidationSetMap::AddResult addResult = m_attributeInvalidationSets.add(attributeName, nullptr);
 261     if (addResult.isNewEntry)
 262         addResult.storedValue->value = DescendantInvalidationSet::create();
 263     return *addResult.storedValue->value;
 264 }
 265 void RuleFeatureSet::collectFeaturesFromSelector(const CSSSelector& selector)
 266 {
 267     collectFeaturesFromSelector(selector, m_metadata, UseSubtreeStyleChange);
 268 }
 269
 270 void RuleFeatureSet::collectFeaturesFromSelector(const CSSSelector& selector, RuleFeatureSet::FeatureMetadata& metadata, InvalidationSetMode mode)
 271 {
 272     unsigned maxDirectAdjacentSelectors = 0;
 273
 274     for (const CSSSelector* current = &selector; current; current = current->tagHistory()) {
 275         if (current->m_match == CSSSelector::Id) {
 276             metadata.idsInRules.add(current->value());
 277         } else if (mode != AddFeatures && (current->m_match == CSSSelector::Class || current->isAttributeSelector())) {
 278             DescendantInvalidationSet* invalidationSet = invalidationSetForSelector(*current);
 279             ASSERT(invalidationSet);
 280             if (mode == UseSubtreeStyleChange)
 281                 invalidationSet->setWholeSubtreeInvalid();
 282         }
 283         if (current->pseudoType() == CSSSelector::PseudoFirstLine)
 284             metadata.usesFirstLineRules = true;
 285         if (current->isDirectAdjacentSelector()) {
 286             maxDirectAdjacentSelectors++;
 287         } else if (maxDirectAdjacentSelectors) {
 288             if (maxDirectAdjacentSelectors > metadata.maxDirectAdjacentSelectors)
 289                 metadata.maxDirectAdjacentSelectors = maxDirectAdjacentSelectors;
 290             maxDirectAdjacentSelectors = 0;
 291         }
 292         if (current->isSiblingSelector())
 293             metadata.foundSiblingSelector = true;
 294
 295         collectFeaturesFromSelectorList(current->selectorList(), metadata, mode);
 296
 297         if (mode == UseLocalStyleChange && current->relation() != CSSSelector::SubSelector)
 298             mode = UseSubtreeStyleChange;
 299     }
 300
 301     ASSERT(!maxDirectAdjacentSelectors);
 302 }
 303
 304 void RuleFeatureSet::collectFeaturesFromSelectorList(const CSSSelectorList* selectorList, RuleFeatureSet::FeatureMetadata& metadata, InvalidationSetMode mode)
 305 {
 306     if (!selectorList)
 307         return;
 308
 309     for (const CSSSelector* selector = selectorList->first(); selector; selector = CSSSelectorList::next(*selector))
 310         collectFeaturesFromSelector(*selector, metadata, mode);
 311 }
 312
 313 void RuleFeatureSet::FeatureMetadata::add(const FeatureMetadata& other)
 314 {
 315     usesFirstLineRules = usesFirstLineRules || other.usesFirstLineRules;
 316     maxDirectAdjacentSelectors = std::max(maxDirectAdjacentSelectors, other.maxDirectAdjacentSelectors);
 317
 318     HashSet<AtomicString>::const_iterator end = other.idsInRules.end();
 319     for (HashSet<AtomicString>::const_iterator it = other.idsInRules.begin(); it != end; ++it)
 320         idsInRules.add(*it);
 321 }
 322
 323 void RuleFeatureSet::FeatureMetadata::clear()
 324 {
 325     idsInRules.clear();
 326     usesFirstLineRules = false;
 327     foundSiblingSelector = false;
 328     maxDirectAdjacentSelectors = 0;
 329 }
 330
 331 void RuleFeatureSet::add(const RuleFeatureSet& other)
 332 {
 333     for (InvalidationSetMap::const_iterator it = other.m_classInvalidationSets.begin(); it != other.m_classInvalidationSets.end(); ++it)
 334         ensureClassInvalidationSet(it->key).combine(*it->value);
 335     for (InvalidationSetMap::const_iterator it = other.m_attributeInvalidationSets.begin(); it != other.m_attributeInvalidationSets.end(); ++it)
 336         ensureAttributeInvalidationSet(it->key).combine(*it->value);
 337
 338     m_metadata.add(other.m_metadata);
 339
 340     siblingRules.appendVector(other.siblingRules);
 341     uncommonAttributeRules.appendVector(other.uncommonAttributeRules);
 342 }
 343
 344 void RuleFeatureSet::clear()
 345 {
 346     siblingRules.clear();
 347     uncommonAttributeRules.clear();
 348     m_metadata.clear();
 349     m_classInvalidationSets.clear();
 350     m_attributeInvalidationSets.clear();
 351     // We cannot clear m_styleInvalidator here, because the style invalidator might not
 352     // have been evaluated yet. If not yet, in StyleInvalidator, there exists some element
 353     // who has needsStyleInvlidation but does not have any invalidation list.
 354     // This makes Blink not to recalc style correctly. crbug.com/344729.
 355 }
 356
 357 void RuleFeatureSet::scheduleStyleInvalidationForClassChange(const SpaceSplitString& changedClasses, Element* element)
 358 {
 359     unsigned changedSize = changedClasses.size();
 360     for (unsigned i = 0; i < changedSize; ++i) {
 361         addClassToInvalidationSet(changedClasses[i], element);
 362     }
 363 }
 364
 365 void RuleFeatureSet::scheduleStyleInvalidationForClassChange(const SpaceSplitString& oldClasses, const SpaceSplitString& newClasses, Element* element)
 366 {
 367     if (!oldClasses.size())
 368         scheduleStyleInvalidationForClassChange(newClasses, element);
 369
 370     // Class vectors tend to be very short. This is faster than using a hash table.
 371     BitVector remainingClassBits;
 372     remainingClassBits.ensureSize(oldClasses.size());
 373
 374     for (unsigned i = 0; i < newClasses.size(); ++i) {
 375         bool found = false;
 376         for (unsigned j = 0; j < oldClasses.size(); ++j) {
 377             if (newClasses[i] == oldClasses[j]) {
 378                 // Mark each class that is still in the newClasses so we can skip doing
 379                 // an n^2 search below when looking for removals. We can't break from
 380                 // this loop early since a class can appear more than once.
 381                 remainingClassBits.quickSet(j);
 382                 found = true;
 383             }
 384         }
 385         // Class was added.
 386         if (!found)
 387             addClassToInvalidationSet(newClasses[i], element);
 388     }
 389
 390     for (unsigned i = 0; i < oldClasses.size(); ++i) {
 391         if (remainingClassBits.quickGet(i))
 392             continue;
 393         // Class was removed.
 394         addClassToInvalidationSet(oldClasses[i], element);
 395     }
 396 }
 397
 398 void RuleFeatureSet::scheduleStyleInvalidationForAttributeChange(const QualifiedName& attributeName, Element* element)
 399 {
 400     if (RefPtr<DescendantInvalidationSet> invalidationSet = m_attributeInvalidationSets.get(attributeName.localName())) {
 401         ensurePendingInvalidationList(element).append(invalidationSet);
 402         element->setNeedsStyleInvalidation();
 403     }
 404 }
 405
 406 void RuleFeatureSet::addClassToInvalidationSet(const AtomicString& className, Element* element)
 407 {
 408     if (RefPtr<DescendantInvalidationSet> invalidationSet = m_classInvalidationSets.get(className)) {
 409         ensurePendingInvalidationList(element).append(invalidationSet);
 410         element->setNeedsStyleInvalidation();
 411     }
 412 }
 413
 414 RuleFeatureSet::InvalidationList& RuleFeatureSet::ensurePendingInvalidationList(Element* element)
 415 {
 416     PendingInvalidationMap::AddResult addResult = m_pendingInvalidationMap.add(element, nullptr);
 417     if (addResult.isNewEntry)
 418         addResult.storedValue->value = adoptPtr(new InvalidationList);
 419     return *addResult.storedValue->value;
 420 }
 421
 422 void RuleFeatureSet::clearStyleInvalidation(Node* node)
 423 {
 424     node->clearChildNeedsStyleInvalidation();
 425     node->clearNeedsStyleInvalidation();
 426     if (node->isElementNode())
 427         m_pendingInvalidationMap.remove(toElement(node));
 428 }
 429
 430 RuleFeatureSet::PendingInvalidationMap& RuleFeatureSet::pendingInvalidationMap()
 431 {
 432     return m_pendingInvalidationMap;
 433 }
 434
 435 } // namespace WebCore