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