src/third_party/WebKit/Source/core/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 "core/css/SelectorFilter.h"
  31
  32 #include "core/css/CSSSelector.h"
  33
  34 namespace blink {
  35
  36 // Salt to separate otherwise identical string hashes so a class-selector like .article won't match <article> elements.
  37 enum { TagNameSalt = 13, IdAttributeSalt = 17, ClassAttributeSalt = 19 };
  38
  39 static inline void collectElementIdentifierHashes(const Element& element, Vector<unsigned, 4>& identifierHashes)
  40 {
  41     identifierHashes.append(element.localName().impl()->existingHash() * TagNameSalt);
  42     if (element.hasID())
  43         identifierHashes.append(element.idForStyleResolution().impl()->existingHash() * IdAttributeSalt);
  44     if (element.isStyledElement() && element.hasClass()) {
  45         const SpaceSplitString& classNames = element.classNames();
  46         size_t count = classNames.size();
  47         for (size_t i = 0; i < count; ++i)
  48             identifierHashes.append(classNames[i].impl()->existingHash() * ClassAttributeSalt);
  49     }
  50 }
  51
  52 void SelectorFilter::pushParentStackFrame(Element& parent)
  53 {
  54     ASSERT(m_ancestorIdentifierFilter);
  55     ASSERT(m_parentStack.isEmpty() || m_parentStack.last().element == parent.parentOrShadowHostElement());
  56     ASSERT(!m_parentStack.isEmpty() || !parent.parentOrShadowHostElement());
  57     m_parentStack.append(ParentStackFrame(parent));
  58     ParentStackFrame& parentFrame = m_parentStack.last();
  59     // Mix tags, class names and ids into some sort of weird bouillabaisse.
  60     // The filter is used for fast rejection of child and descendant selectors.
  61     collectElementIdentifierHashes(parent, parentFrame.identifierHashes);
  62     size_t count = parentFrame.identifierHashes.size();
  63     for (size_t i = 0; i < count; ++i)
  64         m_ancestorIdentifierFilter->add(parentFrame.identifierHashes[i]);
  65 }
  66
  67 void SelectorFilter::popParentStackFrame()
  68 {
  69     ASSERT(!m_parentStack.isEmpty());
  70     ASSERT(m_ancestorIdentifierFilter);
  71     const ParentStackFrame& parentFrame = m_parentStack.last();
  72     size_t count = parentFrame.identifierHashes.size();
  73     for (size_t i = 0; i < count; ++i)
  74         m_ancestorIdentifierFilter->remove(parentFrame.identifierHashes[i]);
  75     m_parentStack.removeLast();
  76     if (m_parentStack.isEmpty()) {
  77         ASSERT(m_ancestorIdentifierFilter->likelyEmpty());
  78         m_ancestorIdentifierFilter.clear();
  79     }
  80 }
  81
  82 void SelectorFilter::setupParentStack(Element& parent)
  83 {
  84     ASSERT(m_parentStack.isEmpty() == !m_ancestorIdentifierFilter);
  85     // Kill whatever we stored before.
  86     m_parentStack.shrink(0);
  87     m_ancestorIdentifierFilter = adoptPtr(new BloomFilter<bloomFilterKeyBits>);
  88     // Fast version if parent is a root element:
  89     if (!parent.parentOrShadowHostNode()) {
  90         pushParentStackFrame(parent);
  91         return;
  92     }
  93     // Otherwise climb up the tree.
  94     WillBeHeapVector<RawPtrWillBeMember<Element>, 30> ancestors;
  95     for (Element* ancestor = &parent; ancestor; ancestor = ancestor->parentOrShadowHostElement())
  96         ancestors.append(ancestor);
  97     for (size_t n = ancestors.size(); n; --n)
  98         pushParentStackFrame(*ancestors[n - 1]);
  99 }
 100
 101 void SelectorFilter::pushParent(Element& parent)
 102 {
 103     ASSERT(m_ancestorIdentifierFilter);
 104     // We may get invoked for some random elements in some wacky cases during style resolve.
 105     // Pause maintaining the stack in this case.
 106     if (m_parentStack.last().element != parent.parentOrShadowHostElement())
 107         return;
 108     pushParentStackFrame(parent);
 109 }
 110
 111 static inline void collectDescendantSelectorIdentifierHashes(const CSSSelector& selector, unsigned*& hash)
 112 {
 113     switch (selector.match()) {
 114     case CSSSelector::Id:
 115         if (!selector.value().isEmpty())
 116             (*hash++) = selector.value().impl()->existingHash() * IdAttributeSalt;
 117         break;
 118     case CSSSelector::Class:
 119         if (!selector.value().isEmpty())
 120             (*hash++) = selector.value().impl()->existingHash() * ClassAttributeSalt;
 121         break;
 122     case CSSSelector::Tag:
 123         if (selector.tagQName().localName() != starAtom)
 124             (*hash++) = selector.tagQName().localName().impl()->existingHash() * TagNameSalt;
 125         break;
 126     default:
 127         break;
 128     }
 129 }
 130
 131 void SelectorFilter::collectIdentifierHashes(const CSSSelector& selector, unsigned* identifierHashes, unsigned maximumIdentifierCount)
 132 {
 133     unsigned* hash = identifierHashes;
 134     unsigned* end = identifierHashes + maximumIdentifierCount;
 135     CSSSelector::Relation relation = selector.relation();
 136     bool relationIsAffectedByPseudoContent = selector.relationIsAffectedByPseudoContent();
 137
 138     // Skip the topmost selector. It is handled quickly by the rule hashes.
 139     bool skipOverSubselectors = true;
 140     for (const CSSSelector* current = selector.tagHistory(); current; current = current->tagHistory()) {
 141         // Only collect identifiers that match ancestors.
 142         switch (relation) {
 143         case CSSSelector::SubSelector:
 144             if (!skipOverSubselectors)
 145                 collectDescendantSelectorIdentifierHashes(*current, hash);
 146             break;
 147         case CSSSelector::DirectAdjacent:
 148         case CSSSelector::IndirectAdjacent:
 149             skipOverSubselectors = true;
 150             break;
 151         case CSSSelector::Descendant:
 152         case CSSSelector::Child:
 153             if (relationIsAffectedByPseudoContent) {
 154                 // Disable fastRejectSelector.
 155                 *identifierHashes = 0;
 156                 return;
 157             }
 158             // Fall through.
 159         case CSSSelector::ShadowPseudo:
 160         case CSSSelector::ShadowDeep:
 161             skipOverSubselectors = false;
 162             collectDescendantSelectorIdentifierHashes(*current, hash);
 163             break;
 164         }
 165         if (hash == end)
 166             return;
 167         relation = current->relation();
 168         relationIsAffectedByPseudoContent = current->relationIsAffectedByPseudoContent();
 169     }
 170     *hash = 0;
 171 }
 172
 173 void SelectorFilter::ParentStackFrame::trace(Visitor* visitor)
 174 {
 175     visitor->trace(element);
 176 }
 177
 178 void SelectorFilter::trace(Visitor* visitor)
 179 {
 180     visitor->trace(m_parentStack);
 181 }
 182
 183 }