Source/WebCore/css/SelectorFilter.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 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 "SelectorFilter.h"
  31
  32 #include "CSSSelector.h"
  33 #include "ShadowRoot.h"
  34 #include "StyledElement.h"
  35
  36 namespace WebCore {
  37
  38 // Salt to separate otherwise identical string hashes so a class-selector like .article won't match <article> elements.
  39 enum { TagNameSalt = 13, IdSalt = 17, ClassSalt = 19, AttributeSalt = 23 };
  40
  41 static bool isExcludedAttribute(const AtomicString& name)
  42 {
  43     return name == HTMLNames::classAttr->localName() || name == HTMLNames::idAttr->localName() || name == HTMLNames::styleAttr->localName();
  44 }
  45
  46 static inline void collectElementIdentifierHashes(const Element& element, Vector<unsigned, 4>& identifierHashes)
  47 {
  48     AtomicString tagLowercaseLocalName = element.localName().convertToASCIILowercase();
  49     identifierHashes.append(tagLowercaseLocalName.impl()->existingHash() * TagNameSalt);
  50
  51     auto& id = element.idForStyleResolution();
  52     if (!id.isNull())
  53         identifierHashes.append(id.impl()->existingHash() * IdSalt);
  54
  55     if (element.hasClass()) {
  56         const SpaceSplitString& classNames = element.classNames();
  57         size_t count = classNames.size();
  58         for (size_t i = 0; i < count; ++i)
  59             identifierHashes.append(classNames[i].impl()->existingHash() * ClassSalt);
  60     }
  61
  62     if (element.hasAttributesWithoutUpdate()) {
  63         for (auto& attribute : element.attributesIterator()) {
  64             auto attributeName = element.isHTMLElement() ? attribute.localName() : attribute.localName().convertToASCIILowercase();
  65             if (isExcludedAttribute(attributeName))
  66                 continue;
  67             identifierHashes.append(attributeName.impl()->existingHash() * AttributeSalt);
  68         }
  69     }
  70 }
  71
  72 bool SelectorFilter::parentStackIsConsistent(const ContainerNode* parentNode) const
  73 {
  74     if (!parentNode || is<Document>(parentNode) || is<ShadowRoot>(parentNode))
  75         return m_parentStack.isEmpty();
  76
  77     return !m_parentStack.isEmpty() && m_parentStack.last().element == parentNode;
  78 }
  79
  80 void SelectorFilter::initializeParentStack(Element& parent)
  81 {
  82     Vector<Element*, 20> ancestors;
  83     for (auto* ancestor = &parent; ancestor; ancestor = ancestor->parentElement())
  84         ancestors.append(ancestor);
  85     for (unsigned i = ancestors.size(); i--;)
  86         pushParent(ancestors[i]);
  87 }
  88
  89 void SelectorFilter::pushParent(Element* parent)
  90 {
  91     ASSERT(m_parentStack.isEmpty() || m_parentStack.last().element == parent->parentElement());
  92     ASSERT(!m_parentStack.isEmpty() || !parent->parentElement());
  93     m_parentStack.append(ParentStackFrame(parent));
  94     ParentStackFrame& parentFrame = m_parentStack.last();
  95     // Mix tags, class names and ids into some sort of weird bouillabaisse.
  96     // The filter is used for fast rejection of child and descendant selectors.
  97     collectElementIdentifierHashes(*parent, parentFrame.identifierHashes);
  98     size_t count = parentFrame.identifierHashes.size();
  99     for (size_t i = 0; i < count; ++i)
 100         m_ancestorIdentifierFilter.add(parentFrame.identifierHashes[i]);
 101 }
 102
 103 void SelectorFilter::pushParentInitializingIfNeeded(Element& parent)
 104 {
 105     if (UNLIKELY(m_parentStack.isEmpty())) {
 106         initializeParentStack(parent);
 107         return;
 108     }
 109     pushParent(&parent);
 110 }
 111
 112 void SelectorFilter::popParent()
 113 {
 114     ASSERT(!m_parentStack.isEmpty());
 115     const ParentStackFrame& parentFrame = m_parentStack.last();
 116     size_t count = parentFrame.identifierHashes.size();
 117     for (size_t i = 0; i < count; ++i)
 118         m_ancestorIdentifierFilter.remove(parentFrame.identifierHashes[i]);
 119     m_parentStack.removeLast();
 120     if (m_parentStack.isEmpty()) {
 121         ASSERT(m_ancestorIdentifierFilter.likelyEmpty());
 122         m_ancestorIdentifierFilter.clear();
 123     }
 124 }
 125
 126 void SelectorFilter::popParentsUntil(Element* parent)
 127 {
 128     while (!m_parentStack.isEmpty()) {
 129         if (parent && m_parentStack.last().element == parent)
 130             return;
 131         popParent();
 132     }
 133 }
 134
 135 struct CollectedSelectorHashes {
 136     using HashVector = Vector<unsigned, 8>;
 137     HashVector ids;
 138     HashVector classes;
 139     HashVector tags;
 140     HashVector attributes;
 141 };
 142
 143 static inline void collectSimpleSelectorHash(CollectedSelectorHashes& collectedHashes, const CSSSelector& selector)
 144 {
 145     switch (selector.match()) {
 146     case CSSSelector::Id:
 147         if (!selector.value().isEmpty())
 148             collectedHashes.ids.append(selector.value().impl()->existingHash() * IdSalt);
 149         break;
 150     case CSSSelector::Class:
 151         if (!selector.value().isEmpty())
 152             collectedHashes.classes.append(selector.value().impl()->existingHash() * ClassSalt);
 153         break;
 154     case CSSSelector::Tag: {
 155         auto& tagLowercaseLocalName = selector.tagLowercaseLocalName();
 156         if (tagLowercaseLocalName != starAtom())
 157             collectedHashes.tags.append(tagLowercaseLocalName.impl()->existingHash() * TagNameSalt);
 158         break;
 159     }
 160     case CSSSelector::Exact:
 161     case CSSSelector::Set:
 162     case CSSSelector::List:
 163     case CSSSelector::Hyphen:
 164     case CSSSelector::Contain:
 165     case CSSSelector::Begin:
 166     case CSSSelector::End: {
 167         auto attributeName = selector.attributeCanonicalLocalName().convertToASCIILowercase();
 168         if (!isExcludedAttribute(attributeName))
 169             collectedHashes.attributes.append(attributeName.impl()->existingHash() * AttributeSalt);
 170         break;
 171     }
 172     default:
 173         break;
 174     }
 175 }
 176
 177 static CollectedSelectorHashes collectSelectorHashes(const CSSSelector& rightmostSelector)
 178 {
 179     CollectedSelectorHashes collectedHashes;
 180
 181     auto* selector = &rightmostSelector;
 182     auto relation = selector->relation();
 183
 184     // Skip the topmost selector. It is handled quickly by the rule hashes.
 185     bool skipOverSubselectors = true;
 186     for (selector = selector->tagHistory(); selector; selector = selector->tagHistory()) {
 187         // Only collect identifiers that match ancestors.
 188         switch (relation) {
 189         case CSSSelector::Subselector:
 190             if (!skipOverSubselectors)
 191                 collectSimpleSelectorHash(collectedHashes, *selector);
 192             break;
 193         case CSSSelector::DirectAdjacent:
 194         case CSSSelector::IndirectAdjacent:
 195         case CSSSelector::ShadowDescendant:
 196             skipOverSubselectors = true;
 197             break;
 198         case CSSSelector::DescendantSpace:
 199         case CSSSelector::Child:
 200             skipOverSubselectors = false;
 201             collectSimpleSelectorHash(collectedHashes, *selector);
 202             break;
 203         }
 204         relation = selector->relation();
 205     }
 206     return collectedHashes;
 207 }
 208
 209 static SelectorFilter::Hashes chooseSelectorHashesForFilter(const CollectedSelectorHashes& collectedSelectorHashes)
 210 {
 211     SelectorFilter::Hashes resultHashes;
 212     unsigned index = 0;
 213
 214     auto addIfNew = [&] (unsigned hash) {
 215         for (unsigned i = 0; i < index; ++i) {
 216             if (resultHashes[i] == hash)
 217                 return;
 218         }
 219         resultHashes[index++] = hash;
 220     };
 221
 222     auto copyHashes = [&] (auto& hashes) {
 223         for (auto& hash : hashes) {
 224             addIfNew(hash);
 225             if (index == resultHashes.size())
 226                 return true;
 227         }
 228         return false;
 229     };
 230
 231     // There is a limited number of slots. Prefer more specific selector types.
 232     if (copyHashes(collectedSelectorHashes.ids))
 233         return resultHashes;
 234     if (copyHashes(collectedSelectorHashes.attributes))
 235         return resultHashes;
 236     if (copyHashes(collectedSelectorHashes.classes))
 237         return resultHashes;
 238     if (copyHashes(collectedSelectorHashes.tags))
 239         return resultHashes;
 240
 241     // Null-terminate if not full.
 242     resultHashes[index] = 0;
 243     return resultHashes;
 244 }
 245
 246 SelectorFilter::Hashes SelectorFilter::collectHashes(const CSSSelector& selector)
 247 {
 248     auto hashes = collectSelectorHashes(selector);
 249     return chooseSelectorHashesForFilter(hashes);
 250 }
 251
 252 }
 253