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