1 /* 2 * Copyright (C) 1999 Lars Knoll (knoll (at) kde.org) 3 * (C) 2004-2005 Allan Sandfeld Jensen (kde (at) carewolf.com) 4 * Copyright (C) 2006, 2007 Nicholas Shanks (webkit (at) nickshanks.com) 5 * Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011 Apple Inc. All rights reserved. 6 * Copyright (C) 2007 Alexey Proskuryakov <ap (at) webkit.org> 7 * Copyright (C) 2007, 2008 Eric Seidel <eric (at) 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 } 184
