OLD | NEW |
1 /* | 1 /* |
2 * Copyright (C) 2011 Apple Inc. All rights reserved. | 2 * Copyright (C) 2011, 2013 Apple Inc. All rights reserved. |
| 3 * Copyright (C) 2014 Samsung Electronics. All rights reserved. |
3 * | 4 * |
4 * Redistribution and use in source and binary forms, with or without | 5 * Redistribution and use in source and binary forms, with or without |
5 * modification, are permitted provided that the following conditions | 6 * modification, are permitted provided that the following conditions |
6 * are met: | 7 * are met: |
7 * | 8 * |
8 * 1. Redistributions of source code must retain the above copyright | 9 * 1. Redistributions of source code must retain the above copyright |
9 * notice, this list of conditions and the following disclaimer. | 10 * notice, this list of conditions and the following disclaimer. |
10 * 2. Redistributions in binary form must reproduce the above copyright | 11 * 2. Redistributions in binary form must reproduce the above copyright |
11 * notice, this list of conditions and the following disclaimer in the | 12 * notice, this list of conditions and the following disclaimer in the |
12 * documentation and/or other materials provided with the distribution. | 13 * documentation and/or other materials provided with the distribution. |
(...skipping 18 matching lines...) Expand all Loading... |
31 #include "core/css/SelectorChecker.h" | 32 #include "core/css/SelectorChecker.h" |
32 #include "core/css/SelectorCheckerFastPath.h" | 33 #include "core/css/SelectorCheckerFastPath.h" |
33 #include "core/css/SiblingTraversalStrategies.h" | 34 #include "core/css/SiblingTraversalStrategies.h" |
34 #include "core/dom/Document.h" | 35 #include "core/dom/Document.h" |
35 #include "core/dom/ElementTraversal.h" | 36 #include "core/dom/ElementTraversal.h" |
36 #include "core/dom/Node.h" | 37 #include "core/dom/Node.h" |
37 #include "core/dom/StaticNodeList.h" | 38 #include "core/dom/StaticNodeList.h" |
38 | 39 |
39 namespace WebCore { | 40 namespace WebCore { |
40 | 41 |
41 class SimpleNodeList { | 42 struct SingleElementSelectorQueryTrait { |
42 public: | 43 typedef Element* OutputType; |
43 virtual ~SimpleNodeList() { } | 44 static const bool shouldOnlyMatchFirstElement = true; |
44 virtual bool isEmpty() const = 0; | 45 ALWAYS_INLINE static void appendElement(OutputType& output, Element& element
) |
45 virtual Node* next() = 0; | 46 { |
| 47 ASSERT(!output); |
| 48 output = &element; |
| 49 } |
46 }; | 50 }; |
47 | 51 |
48 class SingleNodeList FINAL : public SimpleNodeList { | 52 struct AllElementsSelectorQueryTrait { |
49 public: | 53 typedef Vector<RefPtr<Node> > OutputType; |
50 explicit SingleNodeList(Node* rootNode) : m_currentNode(rootNode) { } | 54 static const bool shouldOnlyMatchFirstElement = false; |
51 | 55 ALWAYS_INLINE static void appendElement(OutputType& output, Node& element) |
52 virtual bool isEmpty() const OVERRIDE { return !m_currentNode; } | |
53 | |
54 virtual Node* next() OVERRIDE | |
55 { | 56 { |
56 Node* current = m_currentNode; | 57 output.append(RefPtr<Node>(element)); |
57 m_currentNode = 0; | |
58 return current; | |
59 } | 58 } |
60 | |
61 private: | |
62 Node* m_currentNode; | |
63 }; | 59 }; |
64 | 60 |
65 class ClassRootNodeList FINAL : public SimpleNodeList { | 61 enum ClassElementListBehavior { AllElements, OnlyRoots }; |
66 public: | |
67 ClassRootNodeList(Node& rootNode, const AtomicString& className) | |
68 : m_className(className) | |
69 , m_rootNode(rootNode) | |
70 , m_currentElement(nextInternal(ElementTraversal::firstWithin(m_rootNode
))) { } | |
71 | 62 |
72 virtual bool isEmpty() const OVERRIDE { return !m_currentElement; } | 63 template <ClassElementListBehavior onlyRoots> |
73 | 64 class ClassElementList { |
74 virtual Node* next() OVERRIDE | |
75 { | |
76 Node* current = m_currentElement; | |
77 ASSERT(current); | |
78 m_currentElement = nextInternal(ElementTraversal::nextSkippingChildren(*
m_currentElement, &m_rootNode)); | |
79 return current; | |
80 } | |
81 | |
82 private: | |
83 Element* nextInternal(Element* element) | |
84 { | |
85 for (; element; element = ElementTraversal::next(*element, &m_rootNode))
{ | |
86 if (element->hasClass() && element->classNames().contains(m_classNam
e)) | |
87 return element; | |
88 } | |
89 return 0; | |
90 } | |
91 | |
92 const AtomicString& m_className; | |
93 Node& m_rootNode; | |
94 Element* m_currentElement; | |
95 }; | |
96 | |
97 class ClassElementList FINAL : public SimpleNodeList { | |
98 public: | 65 public: |
99 ClassElementList(Node& rootNode, const AtomicString& className) | 66 ClassElementList(Node& rootNode, const AtomicString& className) |
100 : m_className(className) | 67 : m_className(className) |
101 , m_rootNode(rootNode) | 68 , m_rootNode(rootNode) |
102 , m_currentElement(nextInternal(ElementTraversal::firstWithin(rootNode))
) { } | 69 , m_currentElement(nextInternal(ElementTraversal::firstWithin(rootNode))
) { } |
103 | 70 |
104 virtual bool isEmpty() const OVERRIDE { return !m_currentElement; } | 71 bool isEmpty() const { return !m_currentElement; } |
105 | 72 |
106 virtual Node* next() OVERRIDE | 73 Node* next() |
107 { | 74 { |
108 Node* current = m_currentElement; | 75 Node* current = m_currentElement; |
109 ASSERT(current); | 76 ASSERT(current); |
110 m_currentElement = nextInternal(ElementTraversal::next(*m_currentElement
, &m_rootNode)); | 77 if (onlyRoots) |
| 78 m_currentElement = nextInternal(ElementTraversal::nextSkippingChildr
en(*m_currentElement, &m_rootNode)); |
| 79 else |
| 80 m_currentElement = nextInternal(ElementTraversal::next(*m_currentEle
ment, &m_rootNode)); |
111 return current; | 81 return current; |
112 } | 82 } |
113 | 83 |
114 private: | 84 private: |
115 Element* nextInternal(Element* element) | 85 Element* nextInternal(Element* element) |
116 { | 86 { |
117 for (; element; element = ElementTraversal::next(*element, &m_rootNode))
{ | 87 for (; element; element = ElementTraversal::next(*element, &m_rootNode))
{ |
118 if (element->hasClass() && element->classNames().contains(m_classNam
e)) | 88 if (element->hasClass() && element->classNames().contains(m_classNam
e)) |
119 return element; | 89 return element; |
120 } | 90 } |
(...skipping 41 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
162 if (selectorMatches(m_selectors[i], targetElement, targetElement)) | 132 if (selectorMatches(m_selectors[i], targetElement, targetElement)) |
163 return true; | 133 return true; |
164 } | 134 } |
165 | 135 |
166 return false; | 136 return false; |
167 } | 137 } |
168 | 138 |
169 PassRefPtr<NodeList> SelectorDataList::queryAll(Node& rootNode) const | 139 PassRefPtr<NodeList> SelectorDataList::queryAll(Node& rootNode) const |
170 { | 140 { |
171 Vector<RefPtr<Node> > result; | 141 Vector<RefPtr<Node> > result; |
172 executeQueryAll(rootNode, result); | 142 execute<AllElementsSelectorQueryTrait>(rootNode, result); |
173 return StaticNodeList::adopt(result); | 143 return StaticNodeList::adopt(result); |
174 } | 144 } |
175 | 145 |
176 PassRefPtr<Element> SelectorDataList::queryFirst(Node& rootNode) const | 146 PassRefPtr<Element> SelectorDataList::queryFirst(Node& rootNode) const |
177 { | 147 { |
178 return executeQueryFirst(rootNode); | 148 Element* matchedElement = 0; |
| 149 execute<SingleElementSelectorQueryTrait>(rootNode, matchedElement); |
| 150 return matchedElement; |
179 } | 151 } |
180 | 152 |
181 void SelectorDataList::collectElementsByClassName(Node& rootNode, const AtomicSt
ring& className, Vector<RefPtr<Node> >& traversalRoots) const | 153 template <typename SelectorQueryTrait> |
| 154 void SelectorDataList::collectElementsByClassName(Node& rootNode, const AtomicSt
ring& className, typename SelectorQueryTrait::OutputType& output) const |
182 { | 155 { |
183 for (Element* element = ElementTraversal::firstWithin(rootNode); element; el
ement = ElementTraversal::next(*element, &rootNode)) { | 156 for (Element* element = ElementTraversal::firstWithin(rootNode); element; el
ement = ElementTraversal::next(*element, &rootNode)) { |
184 if (element->hasClass() && element->classNames().contains(className)) | 157 if (element->hasClass() && element->classNames().contains(className)) { |
185 traversalRoots.append(element); | 158 SelectorQueryTrait::appendElement(output, *element); |
| 159 if (SelectorQueryTrait::shouldOnlyMatchFirstElement) |
| 160 return; |
| 161 } |
186 } | 162 } |
187 } | 163 } |
188 | 164 |
189 void SelectorDataList::collectElementsByTagName(Node& rootNode, const QualifiedN
ame& tagName, Vector<RefPtr<Node> >& traversalRoots) const | 165 template <typename SelectorQueryTrait> |
| 166 void SelectorDataList::collectElementsByTagName(Node& rootNode, const QualifiedN
ame& tagName, typename SelectorQueryTrait::OutputType& output) const |
190 { | 167 { |
191 for (Element* element = ElementTraversal::firstWithin(rootNode); element; el
ement = ElementTraversal::next(*element, &rootNode)) { | 168 for (Element* element = ElementTraversal::firstWithin(rootNode); element; el
ement = ElementTraversal::next(*element, &rootNode)) { |
192 if (SelectorChecker::tagMatches(*element, tagName)) | 169 if (SelectorChecker::tagMatches(*element, tagName)) { |
193 traversalRoots.append(element); | 170 SelectorQueryTrait::appendElement(output, *element); |
| 171 if (SelectorQueryTrait::shouldOnlyMatchFirstElement) |
| 172 return; |
| 173 } |
194 } | 174 } |
195 } | 175 } |
196 | 176 |
197 Element* SelectorDataList::findElementByClassName(Node& rootNode, const AtomicSt
ring& className) const | |
198 { | |
199 for (Element* element = ElementTraversal::firstWithin(rootNode); element; el
ement = ElementTraversal::next(*element, &rootNode)) { | |
200 if (element->hasClass() && element->classNames().contains(className)) | |
201 return element; | |
202 } | |
203 return 0; | |
204 } | |
205 | |
206 Element* SelectorDataList::findElementByTagName(Node& rootNode, const QualifiedN
ame& tagName) const | |
207 { | |
208 for (Element* element = ElementTraversal::firstWithin(rootNode); element; el
ement = ElementTraversal::next(*element, &rootNode)) { | |
209 if (SelectorChecker::tagMatches(*element, tagName)) | |
210 return element; | |
211 } | |
212 return 0; | |
213 } | |
214 | |
215 inline bool SelectorDataList::canUseFastQuery(const Node& rootNode) const | 177 inline bool SelectorDataList::canUseFastQuery(const Node& rootNode) const |
216 { | 178 { |
217 return m_selectors.size() == 1 && rootNode.inDocument() && !rootNode.documen
t().inQuirksMode(); | 179 return m_selectors.size() == 1 && rootNode.inDocument() && !rootNode.documen
t().inQuirksMode(); |
218 } | 180 } |
219 | 181 |
220 inline bool ancestorHasClassName(Node& rootNode, const AtomicString& className) | 182 inline bool ancestorHasClassName(Node& rootNode, const AtomicString& className) |
221 { | 183 { |
222 if (!rootNode.isElementNode()) | 184 if (!rootNode.isElementNode()) |
223 return false; | 185 return false; |
224 | 186 |
225 for (Element* element = &toElement(rootNode); element; element = element->pa
rentElement()) { | 187 for (Element* element = &toElement(rootNode); element; element = element->pa
rentElement()) { |
226 if (element->hasClass() && element->classNames().contains(className)) | 188 if (element->hasClass() && element->classNames().contains(className)) |
227 return true; | 189 return true; |
228 } | 190 } |
229 return false; | 191 return false; |
230 } | 192 } |
231 | 193 |
232 | 194 |
233 // If returns true, traversalRoots has the elements that may match the selector
query. | 195 // If returns true, traversalRoots has the elements that may match the selector
query. |
234 // | 196 // |
235 // If returns false, traversalRoots has the rootNode parameter or descendants of
rootNode representing | 197 // If returns false, traversalRoots has the rootNode parameter or descendants of
rootNode representing |
236 // the subtree for which we can limit the querySelector traversal. | 198 // the subtree for which we can limit the querySelector traversal. |
237 // | 199 // |
238 // The travseralRoots may be empty, regardless of the returned bool value, if th
is method finds that the selectors won't | 200 // The travseralRoots may be empty, regardless of the returned bool value, if th
is method finds that the selectors won't |
239 // match any element. | 201 // match any element. |
240 PassOwnPtr<SimpleNodeList> SelectorDataList::findTraverseRoots(Node& rootNode, b
ool& matchTraverseRoots) const | 202 template <typename SelectorQueryTrait> |
| 203 void SelectorDataList::findTraverseRootsAndExecute(Node& rootNode, typename Sele
ctorQueryTrait::OutputType& output) const |
241 { | 204 { |
242 // We need to return the matches in document order. To use id lookup while t
here is possiblity of multiple matches | 205 // We need to return the matches in document order. To use id lookup while t
here is possiblity of multiple matches |
243 // we would need to sort the results. For now, just traverse the document in
that case. | 206 // we would need to sort the results. For now, just traverse the document in
that case. |
244 ASSERT(m_selectors.size() == 1); | 207 ASSERT(m_selectors.size() == 1); |
245 ASSERT(m_selectors[0].selector); | 208 ASSERT(m_selectors[0].selector); |
246 | 209 |
247 bool isRightmostSelector = true; | 210 bool isRightmostSelector = true; |
248 bool startFromParent = false; | 211 bool startFromParent = false; |
249 | 212 |
250 for (const CSSSelector* selector = m_selectors[0].selector; selector; select
or = selector->tagHistory()) { | 213 for (const CSSSelector* selector = m_selectors[0].selector; selector; select
or = selector->tagHistory()) { |
251 if (selector->m_match == CSSSelector::Id && !rootNode.document().contain
sMultipleElementsWithId(selector->value())) { | 214 if (selector->m_match == CSSSelector::Id && !rootNode.document().contain
sMultipleElementsWithId(selector->value())) { |
252 Element* element = rootNode.treeScope().getElementById(selector->val
ue()); | 215 Element* element = rootNode.treeScope().getElementById(selector->val
ue()); |
253 Node* adjustedNode = &rootNode; | 216 Node* adjustedNode = &rootNode; |
254 if (element && (isTreeScopeRoot(rootNode) || element->isDescendantOf
(&rootNode))) | 217 if (element && (isTreeScopeRoot(rootNode) || element->isDescendantOf
(&rootNode))) |
255 adjustedNode = element; | 218 adjustedNode = element; |
256 else if (!element || isRightmostSelector) | 219 else if (!element || isRightmostSelector) |
257 adjustedNode = 0; | 220 adjustedNode = 0; |
258 if (isRightmostSelector) { | 221 if (isRightmostSelector) { |
259 matchTraverseRoots = true; | 222 executeForTraverseRoot<SelectorQueryTrait>(m_selectors[0], adjus
tedNode, MatchesTraverseRoots, rootNode, output); |
260 return adoptPtr(new SingleNodeList(adjustedNode)); | 223 return; |
261 } | 224 } |
| 225 |
262 if (startFromParent && adjustedNode) | 226 if (startFromParent && adjustedNode) |
263 adjustedNode = adjustedNode->parentNode(); | 227 adjustedNode = adjustedNode->parentNode(); |
264 | 228 |
265 matchTraverseRoots = false; | 229 executeForTraverseRoot<SelectorQueryTrait>(m_selectors[0], adjustedN
ode, DoesNotMatchTraverseRoots, rootNode, output); |
266 return adoptPtr(new SingleNodeList(adjustedNode)); | 230 return; |
267 } | 231 } |
268 | 232 |
269 // If we have both CSSSelector::Id and CSSSelector::Class at the same ti
me, we should use Id | 233 // If we have both CSSSelector::Id and CSSSelector::Class at the same ti
me, we should use Id |
270 // to find traverse root. | 234 // to find traverse root. |
271 if (!startFromParent && selector->m_match == CSSSelector::Class) { | 235 if (!SelectorQueryTrait::shouldOnlyMatchFirstElement && !startFromParent
&& selector->m_match == CSSSelector::Class) { |
272 if (isRightmostSelector) { | 236 if (isRightmostSelector) { |
273 matchTraverseRoots = true; | 237 ClassElementList<AllElements> traverseRoots(rootNode, selector->
value()); |
274 return adoptPtr(new ClassElementList(rootNode, selector->value()
)); | 238 executeForTraverseRoots<SelectorQueryTrait>(m_selectors[0], trav
erseRoots, MatchesTraverseRoots, rootNode, output); |
| 239 return; |
275 } | 240 } |
276 matchTraverseRoots = false; | |
277 // Since there exists some ancestor element which has the class name
, we need to see all children of rootNode. | 241 // Since there exists some ancestor element which has the class name
, we need to see all children of rootNode. |
278 if (ancestorHasClassName(rootNode, selector->value())) | 242 if (ancestorHasClassName(rootNode, selector->value())) { |
279 return adoptPtr(new SingleNodeList(&rootNode)); | 243 executeForTraverseRoot<SelectorQueryTrait>(m_selectors[0], &root
Node, DoesNotMatchTraverseRoots, rootNode, output); |
| 244 return; |
| 245 } |
280 | 246 |
281 return adoptPtr(new ClassRootNodeList(rootNode, selector->value())); | 247 ClassElementList<OnlyRoots> traverseRoots(rootNode, selector->value(
)); |
| 248 executeForTraverseRoots<SelectorQueryTrait>(m_selectors[0], traverse
Roots, DoesNotMatchTraverseRoots, rootNode, output); |
| 249 return; |
282 } | 250 } |
283 | 251 |
284 if (selector->relation() == CSSSelector::SubSelector) | 252 if (selector->relation() == CSSSelector::SubSelector) |
285 continue; | 253 continue; |
286 isRightmostSelector = false; | 254 isRightmostSelector = false; |
287 if (selector->relation() == CSSSelector::DirectAdjacent || selector->rel
ation() == CSSSelector::IndirectAdjacent) | 255 if (selector->relation() == CSSSelector::DirectAdjacent || selector->rel
ation() == CSSSelector::IndirectAdjacent) |
288 startFromParent = true; | 256 startFromParent = true; |
289 else | 257 else |
290 startFromParent = false; | 258 startFromParent = false; |
291 } | 259 } |
292 | 260 |
293 matchTraverseRoots = false; | 261 executeForTraverseRoot<SelectorQueryTrait>(m_selectors[0], &rootNode, DoesNo
tMatchTraverseRoots, rootNode, output); |
294 return adoptPtr(new SingleNodeList(&rootNode)); | |
295 } | 262 } |
296 | 263 |
297 void SelectorDataList::executeSlowQueryAll(Node& rootNode, Vector<RefPtr<Node> >
& matchedElements) const | 264 template <typename SelectorQueryTrait> |
| 265 void SelectorDataList::executeForTraverseRoot(const SelectorData& selector, Node
* traverseRoot, MatchTraverseRootState matchTraverseRoot, Node& rootNode, typena
me SelectorQueryTrait::OutputType& output) const |
| 266 { |
| 267 if (!traverseRoot) |
| 268 return; |
| 269 |
| 270 if (matchTraverseRoot) { |
| 271 if (selectorMatches(selector, toElement(*traverseRoot), rootNode)) |
| 272 SelectorQueryTrait::appendElement(output, toElement(*traverseRoot)); |
| 273 return; |
| 274 } |
| 275 |
| 276 for (Element* element = ElementTraversal::firstWithin(*traverseRoot); elemen
t; element = ElementTraversal::next(*element, traverseRoot)) { |
| 277 if (selectorMatches(selector, *element, rootNode)) { |
| 278 SelectorQueryTrait::appendElement(output, *element); |
| 279 if (SelectorQueryTrait::shouldOnlyMatchFirstElement) |
| 280 return; |
| 281 } |
| 282 } |
| 283 } |
| 284 |
| 285 template <typename SelectorQueryTrait, typename SimpleNodeListType> |
| 286 void SelectorDataList::executeForTraverseRoots(const SelectorData& selector, Sim
pleNodeListType& traverseRoots, MatchTraverseRootState matchTraverseRoots, Node&
rootNode, typename SelectorQueryTrait::OutputType& output) const |
| 287 { |
| 288 if (traverseRoots.isEmpty()) |
| 289 return; |
| 290 |
| 291 if (matchTraverseRoots) { |
| 292 while (!traverseRoots.isEmpty()) { |
| 293 Node& node = *traverseRoots.next(); |
| 294 Element& element = toElement(node); |
| 295 if (selectorMatches(selector, element, rootNode)) { |
| 296 SelectorQueryTrait::appendElement(output, element); |
| 297 if (SelectorQueryTrait::shouldOnlyMatchFirstElement) |
| 298 return; |
| 299 } |
| 300 } |
| 301 return; |
| 302 } |
| 303 |
| 304 while (!traverseRoots.isEmpty()) { |
| 305 Node* traverseRoot = traverseRoots.next(); |
| 306 ASSERT(traverseRoot); |
| 307 for (Element* element = ElementTraversal::firstWithin(*traverseRoot); el
ement; element = ElementTraversal::next(*element, traverseRoot)) { |
| 308 if (selectorMatches(selector, *element, rootNode)) { |
| 309 SelectorQueryTrait::appendElement(output, *element); |
| 310 if (SelectorQueryTrait::shouldOnlyMatchFirstElement) |
| 311 return; |
| 312 } |
| 313 } |
| 314 } |
| 315 } |
| 316 |
| 317 template <typename SelectorQueryTrait> |
| 318 void SelectorDataList::executeSlow(Node& rootNode, typename SelectorQueryTrait::
OutputType& output) const |
298 { | 319 { |
299 for (Element* element = ElementTraversal::firstWithin(rootNode); element; el
ement = ElementTraversal::next(*element, &rootNode)) { | 320 for (Element* element = ElementTraversal::firstWithin(rootNode); element; el
ement = ElementTraversal::next(*element, &rootNode)) { |
300 for (unsigned i = 0; i < m_selectors.size(); ++i) { | 321 for (unsigned i = 0; i < m_selectors.size(); ++i) { |
301 if (selectorMatches(m_selectors[i], *element, rootNode)) { | 322 if (selectorMatches(m_selectors[i], *element, rootNode)) { |
302 matchedElements.append(element); | 323 SelectorQueryTrait::appendElement(output, *element); |
| 324 if (SelectorQueryTrait::shouldOnlyMatchFirstElement) |
| 325 return; |
303 break; | 326 break; |
304 } | 327 } |
305 } | 328 } |
306 } | 329 } |
307 } | 330 } |
308 | 331 |
309 const CSSSelector* SelectorDataList::selectorForIdLookup(const CSSSelector* firs
tSelector) const | 332 const CSSSelector* SelectorDataList::selectorForIdLookup(const CSSSelector* firs
tSelector) const |
310 { | 333 { |
311 for (const CSSSelector* selector = firstSelector; selector; selector = selec
tor->tagHistory()) { | 334 for (const CSSSelector* selector = firstSelector; selector; selector = selec
tor->tagHistory()) { |
312 if (selector->m_match == CSSSelector::Id) | 335 if (selector->m_match == CSSSelector::Id) |
313 return selector; | 336 return selector; |
314 if (selector->relation() != CSSSelector::SubSelector) | 337 if (selector->relation() != CSSSelector::SubSelector) |
315 break; | 338 break; |
316 } | 339 } |
317 return 0; | 340 return 0; |
318 } | 341 } |
319 | 342 |
320 void SelectorDataList::executeQueryAll(Node& rootNode, Vector<RefPtr<Node> >& ma
tchedElements) const | 343 template <typename SelectorQueryTrait> |
| 344 void SelectorDataList::execute(Node& rootNode, typename SelectorQueryTrait::Outp
utType& output) const |
321 { | 345 { |
322 if (!canUseFastQuery(rootNode)) | 346 if (!canUseFastQuery(rootNode)) { |
323 return executeSlowQueryAll(rootNode, matchedElements); | 347 executeSlow<SelectorQueryTrait>(rootNode, output); |
| 348 return; |
| 349 } |
324 | 350 |
325 ASSERT(m_selectors.size() == 1); | 351 ASSERT(m_selectors.size() == 1); |
326 ASSERT(m_selectors[0].selector); | 352 ASSERT(m_selectors[0].selector); |
327 | |
328 const SelectorData& selector = m_selectors[0]; | |
329 const CSSSelector* firstSelector = selector.selector; | |
330 | |
331 // Fast path for querySelectorAll('#id'), querySelectorAll('tag#id'). | |
332 if (const CSSSelector* idSelector = selectorForIdLookup(firstSelector)) { | |
333 const AtomicString& idToMatch = idSelector->value(); | |
334 if (rootNode.treeScope().containsMultipleElementsWithId(idToMatch)) { | |
335 const Vector<Element*>& elements = rootNode.treeScope().getAllElemen
tsById(idToMatch); | |
336 size_t count = elements.size(); | |
337 for (size_t i = 0; i < count; ++i) { | |
338 Element* element = elements[i]; | |
339 ASSERT(element); | |
340 if (!(isTreeScopeRoot(rootNode) || element->isDescendantOf(&root
Node))) | |
341 continue; | |
342 if (selectorMatches(selector, *element, rootNode)) | |
343 matchedElements.append(element); | |
344 } | |
345 return; | |
346 } | |
347 Element* element = rootNode.treeScope().getElementById(idToMatch); | |
348 if (!element || !(isTreeScopeRoot(rootNode) || element->isDescendantOf(&
rootNode))) | |
349 return; | |
350 if (selectorMatches(selector, *element, rootNode)) | |
351 matchedElements.append(element); | |
352 return; | |
353 } | |
354 | |
355 if (!firstSelector->tagHistory()) { | |
356 // Fast path for querySelectorAl('.foo'), and querySelectorAll('div'). | |
357 switch (firstSelector->m_match) { | |
358 case CSSSelector::Class: | |
359 return collectElementsByClassName(rootNode, firstSelector->value(),
matchedElements); | |
360 case CSSSelector::Tag: | |
361 return collectElementsByTagName(rootNode, firstSelector->tagQName(),
matchedElements); | |
362 default: | |
363 break; // If we need another fast path, add here. | |
364 } | |
365 } | |
366 | |
367 bool matchTraverseRoots; | |
368 OwnPtr<SimpleNodeList> traverseRoots = findTraverseRoots(rootNode, matchTrav
erseRoots); | |
369 if (traverseRoots->isEmpty()) | |
370 return; | |
371 | |
372 if (matchTraverseRoots) { | |
373 while (!traverseRoots->isEmpty()) { | |
374 Node& node = *traverseRoots->next(); | |
375 Element& element = toElement(node); | |
376 if (selectorMatches(selector, element, rootNode)) | |
377 matchedElements.append(&element); | |
378 } | |
379 return; | |
380 } | |
381 | |
382 while (!traverseRoots->isEmpty()) { | |
383 Node* traverseRoot = traverseRoots->next(); | |
384 ASSERT(traverseRoot); | |
385 for (Element* element = ElementTraversal::firstWithin(*traverseRoot); el
ement; element = ElementTraversal::next(*element, traverseRoot)) { | |
386 if (selectorMatches(selector, *element, rootNode)) | |
387 matchedElements.append(element); | |
388 } | |
389 } | |
390 } | |
391 | |
392 // If matchTraverseRoot is true, the returned Node is the single Element that ma
y match the selector query. | |
393 // | |
394 // If matchTraverseRoot is false, the returned Node is the rootNode parameter or
a descendant of rootNode representing | |
395 // the subtree for which we can limit the querySelector traversal. | |
396 // | |
397 // The returned Node may be 0, regardless of matchTraverseRoot, if this method f
inds that the selectors won't | |
398 // match any element. | |
399 Node* SelectorDataList::findTraverseRoot(Node& rootNode, bool& matchTraverseRoot
) const | |
400 { | |
401 // We need to return the matches in document order. To use id lookup while t
here is possiblity of multiple matches | |
402 // we would need to sort the results. For now, just traverse the document in
that case. | |
403 ASSERT(m_selectors.size() == 1); | |
404 ASSERT(m_selectors[0].selector); | |
405 | |
406 bool matchSingleNode = true; | |
407 bool startFromParent = false; | |
408 for (const CSSSelector* selector = m_selectors[0].selector; selector; select
or = selector->tagHistory()) { | |
409 if (selector->m_match == CSSSelector::Id && !rootNode.document().contain
sMultipleElementsWithId(selector->value())) { | |
410 Element* element = rootNode.treeScope().getElementById(selector->val
ue()); | |
411 Node* adjustedRootNode = &rootNode; | |
412 if (element && (isTreeScopeRoot(rootNode) || element->isDescendantOf
(&rootNode))) | |
413 adjustedRootNode = element; | |
414 else if (!element || matchSingleNode) | |
415 adjustedRootNode = 0; | |
416 if (matchSingleNode) { | |
417 matchTraverseRoot = true; | |
418 return adjustedRootNode; | |
419 } | |
420 if (startFromParent && adjustedRootNode) | |
421 adjustedRootNode = adjustedRootNode->parentNode(); | |
422 matchTraverseRoot = false; | |
423 return adjustedRootNode; | |
424 } | |
425 if (selector->relation() == CSSSelector::SubSelector) | |
426 continue; | |
427 matchSingleNode = false; | |
428 if (selector->relation() == CSSSelector::DirectAdjacent || selector->rel
ation() == CSSSelector::IndirectAdjacent) | |
429 startFromParent = true; | |
430 else | |
431 startFromParent = false; | |
432 } | |
433 matchTraverseRoot = false; | |
434 return &rootNode; | |
435 } | |
436 | |
437 Element* SelectorDataList::executeSlowQueryFirst(Node& rootNode) const | |
438 { | |
439 for (Element* element = ElementTraversal::firstWithin(rootNode); element; el
ement = ElementTraversal::next(*element, &rootNode)) { | |
440 for (unsigned i = 0; i < m_selectors.size(); ++i) { | |
441 if (selectorMatches(m_selectors[i], *element, rootNode)) | |
442 return element; | |
443 } | |
444 } | |
445 return 0; | |
446 } | |
447 | |
448 Element* SelectorDataList::executeQueryFirst(Node& rootNode) const | |
449 { | |
450 if (!canUseFastQuery(rootNode)) | |
451 return executeSlowQueryFirst(rootNode); | |
452 | |
453 ASSERT(m_selectors.size() == 1); | |
454 ASSERT(m_selectors[0].selector); | |
455 | 353 |
456 const SelectorData& selector = m_selectors[0]; | 354 const SelectorData& selector = m_selectors[0]; |
457 const CSSSelector* firstSelector = selector.selector; | 355 const CSSSelector* firstSelector = selector.selector; |
458 | 356 |
459 // Fast path for querySelectorAll('#id'), querySelectorAll('tag#id'). | 357 // Fast path for querySelector*('#id'), querySelector*('tag#id'). |
460 if (const CSSSelector* idSelector = selectorForIdLookup(firstSelector)) { | 358 if (const CSSSelector* idSelector = selectorForIdLookup(firstSelector)) { |
461 const AtomicString& idToMatch = idSelector->value(); | 359 const AtomicString& idToMatch = idSelector->value(); |
462 if (rootNode.treeScope().containsMultipleElementsWithId(idToMatch)) { | 360 if (rootNode.treeScope().containsMultipleElementsWithId(idToMatch)) { |
463 const Vector<Element*>& elements = rootNode.treeScope().getAllElemen
tsById(idToMatch); | 361 const Vector<Element*>& elements = rootNode.treeScope().getAllElemen
tsById(idToMatch); |
464 size_t count = elements.size(); | 362 size_t count = elements.size(); |
465 for (size_t i = 0; i < count; ++i) { | 363 for (size_t i = 0; i < count; ++i) { |
466 Element* element = elements[i]; | 364 Element& element = *elements[i]; |
467 ASSERT(element); | 365 if (!(isTreeScopeRoot(rootNode) || element.isDescendantOf(&rootN
ode))) |
468 if (!(isTreeScopeRoot(rootNode) || element->isDescendantOf(&root
Node))) | |
469 continue; | 366 continue; |
470 if (selectorMatches(selector, *element, rootNode)) | 367 if (selectorMatches(selector, element, rootNode)) { |
471 return element; | 368 SelectorQueryTrait::appendElement(output, element); |
| 369 if (SelectorQueryTrait::shouldOnlyMatchFirstElement) |
| 370 return; |
| 371 } |
472 } | 372 } |
473 return 0; | 373 return; |
474 } | 374 } |
475 Element* element = rootNode.treeScope().getElementById(idToMatch); | 375 Element* element = rootNode.treeScope().getElementById(idToMatch); |
476 if (!element || !(isTreeScopeRoot(rootNode) || element->isDescendantOf(&
rootNode))) | 376 if (!element || !(isTreeScopeRoot(rootNode) || element->isDescendantOf(&
rootNode))) |
477 return 0; | 377 return; |
478 return selectorMatches(selector, *element, rootNode) ? element : 0; | 378 if (selectorMatches(selector, *element, rootNode)) |
| 379 SelectorQueryTrait::appendElement(output, *element); |
| 380 return; |
479 } | 381 } |
480 | 382 |
481 if (!firstSelector->tagHistory()) { | 383 if (!firstSelector->tagHistory()) { |
482 // Fast path for querySelector('.foo'), and querySelector('div'). | 384 // Fast path for querySelector*('.foo'), and querySelector*('div'). |
483 // Many web developers uses querySelector with these simple selectors. | |
484 switch (firstSelector->m_match) { | 385 switch (firstSelector->m_match) { |
485 case CSSSelector::Class: | 386 case CSSSelector::Class: |
486 return findElementByClassName(rootNode, firstSelector->value()); | 387 collectElementsByClassName<SelectorQueryTrait>(rootNode, firstSelect
or->value(), output); |
| 388 return; |
487 case CSSSelector::Tag: | 389 case CSSSelector::Tag: |
488 return findElementByTagName(rootNode, firstSelector->tagQName()); | 390 collectElementsByTagName<SelectorQueryTrait>(rootNode, firstSelector
->tagQName(), output); |
| 391 return; |
489 default: | 392 default: |
490 break; // If we need another fast path, add here. | 393 break; // If we need another fast path, add here. |
491 } | 394 } |
492 } | 395 } |
493 | 396 |
494 bool matchTraverseRoot; | 397 findTraverseRootsAndExecute<SelectorQueryTrait>(rootNode, output); |
495 Node* traverseRootNode = findTraverseRoot(rootNode, matchTraverseRoot); | |
496 if (!traverseRootNode) | |
497 return 0; | |
498 if (matchTraverseRoot) { | |
499 ASSERT(traverseRootNode->isElementNode()); | |
500 Element& element = toElement(*traverseRootNode); | |
501 return selectorMatches(selector, element, rootNode) ? &element : 0; | |
502 } | |
503 | |
504 for (Element* element = ElementTraversal::firstWithin(*traverseRootNode); el
ement; element = ElementTraversal::next(*element, traverseRootNode)) { | |
505 if (selectorMatches(selector, *element, rootNode)) | |
506 return element; | |
507 } | |
508 return 0; | |
509 } | 398 } |
510 | 399 |
511 SelectorQuery::SelectorQuery(const CSSSelectorList& selectorList) | 400 SelectorQuery::SelectorQuery(const CSSSelectorList& selectorList) |
512 : m_selectorList(selectorList) | 401 : m_selectorList(selectorList) |
513 { | 402 { |
514 m_selectors.initialize(m_selectorList); | 403 m_selectors.initialize(m_selectorList); |
515 } | 404 } |
516 | 405 |
517 bool SelectorQuery::matches(Element& element) const | 406 bool SelectorQuery::matches(Element& element) const |
518 { | 407 { |
(...skipping 40 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
559 m_entries.add(selectors, selectorQuery.release()); | 448 m_entries.add(selectors, selectorQuery.release()); |
560 return rawSelectorQuery; | 449 return rawSelectorQuery; |
561 } | 450 } |
562 | 451 |
563 void SelectorQueryCache::invalidate() | 452 void SelectorQueryCache::invalidate() |
564 { | 453 { |
565 m_entries.clear(); | 454 m_entries.clear(); |
566 } | 455 } |
567 | 456 |
568 } | 457 } |
OLD | NEW |