Prefer ids and classes over tag names in 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, 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::pushParentStackFrame(Element* parent)
67 {
68     ASSERT(m_parentStack.isEmpty() || m_parentStack.last().element == parent->parentElement());
69     ASSERT(!m_parentStack.isEmpty() || !parent->parentElement());
70     m_parentStack.append(ParentStackFrame(parent));
71     ParentStackFrame& parentFrame = m_parentStack.last();
72     // Mix tags, class names and ids into some sort of weird bouillabaisse.
73     // The filter is used for fast rejection of child and descendant selectors.
74     collectElementIdentifierHashes(parent, parentFrame.identifierHashes);
75     size_t count = parentFrame.identifierHashes.size();
76     for (size_t i = 0; i < count; ++i)
77         m_ancestorIdentifierFilter.add(parentFrame.identifierHashes[i]);
78 }
79
80 void SelectorFilter::popParentStackFrame()
81 {
82     ASSERT(!m_parentStack.isEmpty());
83     const ParentStackFrame& parentFrame = m_parentStack.last();
84     size_t count = parentFrame.identifierHashes.size();
85     for (size_t i = 0; i < count; ++i)
86         m_ancestorIdentifierFilter.remove(parentFrame.identifierHashes[i]);
87     m_parentStack.removeLast();
88     if (m_parentStack.isEmpty()) {
89         ASSERT(m_ancestorIdentifierFilter.likelyEmpty());
90         m_ancestorIdentifierFilter.clear();
91     }
92 }
93
94 void SelectorFilter::pushParent(Element* parent)
95 {
96     pushParentStackFrame(parent);
97 }
98
99 struct CollectedSelectorHashes {
100     using HashVector = Vector<unsigned, 8>;
101     HashVector ids;
102     HashVector classes;
103     HashVector tags;
104 };
105
106 static inline void collectSimpleSelectorHash(CollectedSelectorHashes& collectedHashes, const CSSSelector& selector)
107 {
108     switch (selector.match()) {
109     case CSSSelector::Id:
110         if (!selector.value().isEmpty())
111             collectedHashes.ids.append(selector.value().impl()->existingHash() * IdAttributeSalt);
112         break;
113     case CSSSelector::Class:
114         if (!selector.value().isEmpty())
115             collectedHashes.classes.append(selector.value().impl()->existingHash() * ClassAttributeSalt);
116         break;
117     case CSSSelector::Tag: {
118         auto& tagLowercaseLocalName = selector.tagLowercaseLocalName();
119         if (tagLowercaseLocalName != starAtom())
120             collectedHashes.tags.append(tagLowercaseLocalName.impl()->existingHash() * TagNameSalt);
121         break;
122     }
123     default:
124         break;
125     }
126 }
127
128 static CollectedSelectorHashes collectSelectorHashes(const CSSSelector& rightmostSelector)
129 {
130     CollectedSelectorHashes collectedHashes;
131
132     auto* selector = &rightmostSelector;
133     auto relation = selector->relation();
134
135     // Skip the topmost selector. It is handled quickly by the rule hashes.
136     bool skipOverSubselectors = true;
137     for (selector = selector->tagHistory(); selector; selector = selector->tagHistory()) {
138         // Only collect identifiers that match ancestors.
139         switch (relation) {
140         case CSSSelector::Subselector:
141             if (!skipOverSubselectors)
142                 collectSimpleSelectorHash(collectedHashes, *selector);
143             break;
144         case CSSSelector::DirectAdjacent:
145         case CSSSelector::IndirectAdjacent:
146         case CSSSelector::ShadowDescendant:
147             skipOverSubselectors = true;
148             break;
149         case CSSSelector::DescendantSpace:
150         case CSSSelector::Child:
151             skipOverSubselectors = false;
152             collectSimpleSelectorHash(collectedHashes, *selector);
153             break;
154         }
155         relation = selector->relation();
156     }
157     return collectedHashes;
158 }
159
160 static SelectorFilter::Hashes chooseSelectorHashesForFilter(const CollectedSelectorHashes& collectedSelectorHashes)
161 {
162     SelectorFilter::Hashes resultHashes;
163     unsigned index = 0;
164
165     auto addIfNew = [&] (unsigned hash) {
166         for (unsigned i = 0; i < index; ++i) {
167             if (resultHashes[i] == hash)
168                 return;
169         }
170         resultHashes[index++] = hash;
171     };
172
173     auto copyHashes = [&] (auto& hashes) {
174         for (auto& hash : hashes) {
175             addIfNew(hash);
176             if (index == resultHashes.size())
177                 return true;
178         }
179         return false;
180     };
181
182     // There is a limited number of slots. Prefer more specific selector types.
183     if (copyHashes(collectedSelectorHashes.ids))
184         return resultHashes;
185     if (copyHashes(collectedSelectorHashes.classes))
186         return resultHashes;
187     if (copyHashes(collectedSelectorHashes.tags))
188         return resultHashes;
189
190     // Null-terminate if not full.
191     resultHashes[index] = 0;
192     return resultHashes;
193 }
194
195 SelectorFilter::Hashes SelectorFilter::collectHashes(const CSSSelector& selector)
196 {
197     auto hashes = collectSelectorHashes(selector);
198     return chooseSelectorHashesForFilter(hashes);
199 }
200
201 }
202