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, 2012, 2013 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) 2013 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/SelectorCheckerFastPath.h"
31
32 #include "HTMLNames.h"
33 #include "core/dom/Element.h"
34 #include "core/html/HTMLDocument.h"
35
36 namespace WebCore {
37
38 using namespace HTMLNames;
39
40 namespace {
41
42 template <bool checkValue(const Element&, const CSSSelector*)>
fastCheckSingleSelector(const CSSSelector * & selector,const Element * & element,const CSSSelector * & topChildOrSubselector,const Element * & topChildOrSubselectorMatchElement)43 inline bool fastCheckSingleSelector(const CSSSelector*& selector, const Element*& element, const CSSSelector*& topChildOrSubselector, const Element*& topChildOrSubselectorMatchElement)
44 {
45 for (; element; element = element->parentElement()) {
46 if (checkValue(*element, selector)) {
47 if (selector->relation() == CSSSelector::Descendant)
48 topChildOrSubselector = 0;
49 else if (!topChildOrSubselector) {
50 ASSERT(selector->relation() == CSSSelector::Child || selector->relation() == CSSSelector::SubSelector);
51 topChildOrSubselector = selector;
52 topChildOrSubselectorMatchElement = element;
53 }
54 if (selector->relation() != CSSSelector::SubSelector)
55 element = element->parentElement();
56 selector = selector->tagHistory();
57 return true;
58 }
59 if (topChildOrSubselector) {
60 // Child or subselector check failed.
61 // If the match element is null, topChildOrSubselector was also the very topmost selector and had to match
62 // the original element we were checking.
63 if (!topChildOrSubselectorMatchElement)
64 return false;
65 // There may be other matches down the ancestor chain.
66 // Rewind to the topmost child or subselector and the element it matched, continue checking ancestors.
67 selector = topChildOrSubselector;
68 element = topChildOrSubselectorMatchElement->parentElement();
69 topChildOrSubselector = 0;
70 return true;
71 }
72 }
73 return false;
74 }
75
checkClassValue(const Element & element,const CSSSelector * selector)76 inline bool checkClassValue(const Element& element, const CSSSelector* selector)
77 {
78 return element.hasClass() && element.classNames().contains(selector->value());
79 }
80
checkIDValue(const Element & element,const CSSSelector * selector)81 inline bool checkIDValue(const Element& element, const CSSSelector* selector)
82 {
83 return element.hasID() && element.idForStyleResolution() == selector->value();
84 }
85
checkExactAttributeValue(const Element & element,const CSSSelector * selector)86 inline bool checkExactAttributeValue(const Element& element, const CSSSelector* selector)
87 {
88 return SelectorChecker::checkExactAttribute(element, selector->attribute(), selector->value().impl());
89 }
90
checkTagValue(const Element & element,const CSSSelector * selector)91 inline bool checkTagValue(const Element& element, const CSSSelector* selector)
92 {
93 return SelectorChecker::tagMatches(element, selector->tagQName());
94 }
95
96 }
97
SelectorCheckerFastPath(const CSSSelector * selector,const Element & element)98 SelectorCheckerFastPath::SelectorCheckerFastPath(const CSSSelector* selector, const Element& element)
99 : m_selector(selector)
100 , m_element(element)
101 {
102 }
103
matchesRightmostSelector(SelectorChecker::VisitedMatchType visitedMatchType) const104 bool SelectorCheckerFastPath::matchesRightmostSelector(SelectorChecker::VisitedMatchType visitedMatchType) const
105 {
106 ASSERT(SelectorCheckerFastPath::canUse(m_selector));
107
108 switch (m_selector->m_match) {
109 case CSSSelector::Tag:
110 return checkTagValue(m_element, m_selector);
111 case CSSSelector::Class:
112 return checkClassValue(m_element, m_selector);
113 case CSSSelector::Id:
114 return checkIDValue(m_element, m_selector);
115 case CSSSelector::Exact:
116 case CSSSelector::Set:
117 return checkExactAttributeValue(m_element, m_selector);
118 case CSSSelector::PseudoClass:
119 return commonPseudoClassSelectorMatches(visitedMatchType);
120 default:
121 ASSERT_NOT_REACHED();
122 }
123 return false;
124 }
125
matches() const126 bool SelectorCheckerFastPath::matches() const
127 {
128 ASSERT(matchesRightmostSelector(SelectorChecker::VisitedMatchEnabled));
129 const CSSSelector* selector = m_selector;
130 const Element* element = &m_element;
131
132 const CSSSelector* topChildOrSubselector = 0;
133 const Element* topChildOrSubselectorMatchElement = 0;
134 if (selector->relation() == CSSSelector::Child || selector->relation() == CSSSelector::SubSelector)
135 topChildOrSubselector = selector;
136
137 if (selector->relation() != CSSSelector::SubSelector)
138 element = element->parentElement();
139
140 selector = selector->tagHistory();
141
142 // We know this compound selector has descendant, child and subselector combinators only and all components are simple.
143 while (selector) {
144 switch (selector->m_match) {
145 case CSSSelector::Class:
146 if (!fastCheckSingleSelector<checkClassValue>(selector, element, topChildOrSubselector, topChildOrSubselectorMatchElement))
147 return false;
148 break;
149 case CSSSelector::Id:
150 if (!fastCheckSingleSelector<checkIDValue>(selector, element, topChildOrSubselector, topChildOrSubselectorMatchElement))
151 return false;
152 break;
153 case CSSSelector::Tag:
154 if (!fastCheckSingleSelector<checkTagValue>(selector, element, topChildOrSubselector, topChildOrSubselectorMatchElement))
155 return false;
156 break;
157 case CSSSelector::Set:
158 case CSSSelector::Exact:
159 if (!fastCheckSingleSelector<checkExactAttributeValue>(selector, element, topChildOrSubselector, topChildOrSubselectorMatchElement))
160 return false;
161 break;
162 default:
163 ASSERT_NOT_REACHED();
164 }
165 }
166 return true;
167 }
168
isFastCheckableRelation(CSSSelector::Relation relation)169 static inline bool isFastCheckableRelation(CSSSelector::Relation relation)
170 {
171 return relation == CSSSelector::Descendant || relation == CSSSelector::Child || relation == CSSSelector::SubSelector;
172 }
173
isFastCheckableMatch(const CSSSelector * selector)174 static inline bool isFastCheckableMatch(const CSSSelector* selector)
175 {
176 if (selector->m_match == CSSSelector::Set) {
177 // Style attribute is generated lazily but the fast path doesn't trigger it.
178 // Disallow them here rather than making the fast path more branchy.
179 return selector->attribute() != styleAttr;
180 }
181 if (selector->m_match == CSSSelector::Exact)
182 return selector->attribute() != styleAttr && HTMLDocument::isCaseSensitiveAttribute(selector->attribute());
183 return selector->m_match == CSSSelector::Tag || selector->m_match == CSSSelector::Id || selector->m_match == CSSSelector::Class;
184 }
185
isFastCheckableRightmostSelector(const CSSSelector * selector)186 static inline bool isFastCheckableRightmostSelector(const CSSSelector* selector)
187 {
188 if (!isFastCheckableRelation(selector->relation()))
189 return false;
190 return isFastCheckableMatch(selector) || SelectorChecker::isCommonPseudoClassSelector(selector);
191 }
192
canUse(const CSSSelector * selector)193 bool SelectorCheckerFastPath::canUse(const CSSSelector* selector)
194 {
195 if (!isFastCheckableRightmostSelector(selector))
196 return false;
197 for (selector = selector->tagHistory(); selector; selector = selector->tagHistory()) {
198 if (!isFastCheckableRelation(selector->relation()))
199 return false;
200 if (!isFastCheckableMatch(selector))
201 return false;
202 }
203 return true;
204 }
205
commonPseudoClassSelectorMatches(SelectorChecker::VisitedMatchType visitedMatchType) const206 bool SelectorCheckerFastPath::commonPseudoClassSelectorMatches(SelectorChecker::VisitedMatchType visitedMatchType) const
207 {
208 ASSERT(SelectorChecker::isCommonPseudoClassSelector(m_selector));
209 switch (m_selector->pseudoType()) {
210 case CSSSelector::PseudoLink:
211 case CSSSelector::PseudoAnyLink:
212 return m_element.isLink();
213 case CSSSelector::PseudoVisited:
214 return m_element.isLink() && visitedMatchType == SelectorChecker::VisitedMatchEnabled;
215 case CSSSelector::PseudoFocus:
216 return SelectorChecker::matchesFocusPseudoClass(m_element);
217 default:
218 ASSERT_NOT_REACHED();
219 }
220 return true;
221 }
222
223
224 }
225