Move MediaQueryMatcher, SelectorFilter to std::unique_ptr
[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 "StyledElement.h"
34
35 namespace WebCore {
36
37 // Salt to separate otherwise identical string hashes so a class-selector like .article won't match <article> elements.
38 enum { TagNameSalt = 13, IdAttributeSalt = 17, ClassAttributeSalt = 19 };
39
40 static inline void collectElementIdentifierHashes(const Element* element, Vector<unsigned, 4>& identifierHashes)
41 {
42     identifierHashes.append(element->localName().impl()->existingHash() * TagNameSalt);
43     if (element->hasID())
44         identifierHashes.append(element->idForStyleResolution().impl()->existingHash() * IdAttributeSalt);
45     const StyledElement* styledElement = element->isStyledElement() ? static_cast<const StyledElement*>(element) : 0;
46     if (styledElement && styledElement->hasClass()) {
47         const SpaceSplitString& classNames = styledElement->classNames();
48         size_t count = classNames.size();
49         for (size_t i = 0; i < count; ++i)
50             identifierHashes.append(classNames[i].impl()->existingHash() * ClassAttributeSalt);
51     }
52 }
53
54 void SelectorFilter::pushParentStackFrame(Element* parent)
55 {
56     ASSERT(m_ancestorIdentifierFilter);
57     ASSERT(m_parentStack.isEmpty() || m_parentStack.last().element == parent->parentOrShadowHostElement());
58     ASSERT(!m_parentStack.isEmpty() || !parent->parentOrShadowHostElement());
59     m_parentStack.append(ParentStackFrame(parent));
60     ParentStackFrame& parentFrame = m_parentStack.last();
61     // Mix tags, class names and ids into some sort of weird bouillabaisse.
62     // The filter is used for fast rejection of child and descendant selectors.
63     collectElementIdentifierHashes(parent, parentFrame.identifierHashes);
64     size_t count = parentFrame.identifierHashes.size();
65     for (size_t i = 0; i < count; ++i)
66         m_ancestorIdentifierFilter->add(parentFrame.identifierHashes[i]);
67 }
68
69 void SelectorFilter::popParentStackFrame()
70 {
71     ASSERT(!m_parentStack.isEmpty());
72     ASSERT(m_ancestorIdentifierFilter);
73     const ParentStackFrame& parentFrame = m_parentStack.last();
74     size_t count = parentFrame.identifierHashes.size();
75     for (size_t i = 0; i < count; ++i)
76         m_ancestorIdentifierFilter->remove(parentFrame.identifierHashes[i]);
77     m_parentStack.removeLast();
78     if (m_parentStack.isEmpty()) {
79         ASSERT(m_ancestorIdentifierFilter->likelyEmpty());
80         m_ancestorIdentifierFilter = nullptr;
81     }
82 }
83
84 void SelectorFilter::setupParentStack(Element* parent)
85 {
86     ASSERT(m_parentStack.isEmpty() == !m_ancestorIdentifierFilter);
87     // Kill whatever we stored before.
88     m_parentStack.shrink(0);
89     m_ancestorIdentifierFilter = std::make_unique<BloomFilter<bloomFilterKeyBits>>();
90     // Fast version if parent is a root element:
91     if (!parent->parentNode() && !parent->isShadowRoot()) {
92         pushParentStackFrame(parent);
93         return;
94     }
95     // Otherwise climb up the tree.
96     Vector<Element*, 30> ancestors;
97     for (Element* ancestor = parent; ancestor; ancestor = ancestor->parentOrShadowHostElement())
98         ancestors.append(ancestor);
99     for (size_t n = ancestors.size(); n; --n)
100         pushParentStackFrame(ancestors[n - 1]);
101 }
102
103 void SelectorFilter::pushParent(Element* parent)
104 {
105     ASSERT(m_ancestorIdentifierFilter);
106     // We may get invoked for some random elements in some wacky cases during style resolve.
107     // Pause maintaining the stack in this case.
108     if (m_parentStack.last().element != parent->parentOrShadowHostElement())
109         return;
110     pushParentStackFrame(parent);
111 }
112
113 static inline void collectDescendantSelectorIdentifierHashes(const CSSSelector* selector, unsigned*& hash)
114 {
115     switch (selector->m_match) {
116     case CSSSelector::Id:
117         if (!selector->value().isEmpty())
118             (*hash++) = selector->value().impl()->existingHash() * IdAttributeSalt;
119         break;
120     case CSSSelector::Class:
121         if (!selector->value().isEmpty())
122             (*hash++) = selector->value().impl()->existingHash() * ClassAttributeSalt;
123         break;
124     case CSSSelector::Tag:
125         if (selector->tagQName().localName() != starAtom)
126             (*hash++) = selector->tagQName().localName().impl()->existingHash() * TagNameSalt;
127         break;
128     default:
129         break;
130     }
131 }
132
133 void SelectorFilter::collectIdentifierHashes(const CSSSelector* selector, unsigned* identifierHashes, unsigned maximumIdentifierCount)
134 {
135     unsigned* hash = identifierHashes;
136     unsigned* end = identifierHashes + maximumIdentifierCount;
137     CSSSelector::Relation relation = selector->relation();
138
139     // Skip the topmost selector. It is handled quickly by the rule hashes.
140     bool skipOverSubselectors = true;
141     for (selector = selector->tagHistory(); selector; selector = selector->tagHistory()) {
142         // Only collect identifiers that match ancestors.
143         switch (relation) {
144         case CSSSelector::SubSelector:
145             if (!skipOverSubselectors)
146                 collectDescendantSelectorIdentifierHashes(selector, hash);
147             break;
148         case CSSSelector::DirectAdjacent:
149         case CSSSelector::IndirectAdjacent:
150         case CSSSelector::ShadowDescendant:
151             skipOverSubselectors = true;
152             break;
153         case CSSSelector::Descendant:
154         case CSSSelector::Child:
155             skipOverSubselectors = false;
156             collectDescendantSelectorIdentifierHashes(selector, hash);
157             break;
158         }
159         if (hash == end)
160             return;
161         relation = selector->relation();
162     }
163     *hash = 0;
164 }
165
166 }
167