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