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