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
collectElementIdentifierHashes(const Element & element,Vector<unsigned,4> & identifierHashes)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
pushParentStackFrame(Element & parent)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
popParentStackFrame()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
setupParentStack(Element & parent)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
pushParent(Element & parent)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
collectDescendantSelectorIdentifierHashes(const CSSSelector & selector,unsigned * & hash)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
collectIdentifierHashes(const CSSSelector & selector,unsigned * identifierHashes,unsigned maximumIdentifierCount)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
trace(Visitor * visitor)173 void SelectorFilter::ParentStackFrame::trace(Visitor* visitor)
174 {
175 visitor->trace(element);
176 }
177
trace(Visitor * visitor)178 void SelectorFilter::trace(Visitor* visitor)
179 {
180 visitor->trace(m_parentStack);
181 }
182
183 }
184