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 ) |
esprehn
2014/01/23 18:26:34
reference.
Inactive
2014/01/23 21:07:52
Ok, I will update and reupload.
| |
45 virtual Node* next() = 0; | 46 { |
47 ASSERT(element); | |
48 ASSERT(!output); | |
49 output = element; | |
50 } | |
46 }; | 51 }; |
47 | 52 |
48 class SingleNodeList FINAL : public SimpleNodeList { | 53 struct AllElementsSelectorQueryTrait { |
49 public: | 54 typedef Vector<RefPtr<Node> > OutputType; |
50 explicit SingleNodeList(Node* rootNode) : m_currentNode(rootNode) { } | 55 static const bool shouldOnlyMatchFirstElement = false; |
51 | 56 ALWAYS_INLINE static void appendElement(OutputType& output, Node* element) |
esprehn
2014/01/23 18:26:34
Same
| |
52 virtual bool isEmpty() const OVERRIDE { return !m_currentNode; } | |
53 | |
54 virtual Node* next() OVERRIDE | |
55 { | 57 { |
56 Node* current = m_currentNode; | 58 ASSERT(element); |
57 m_currentNode = 0; | 59 output.append(element); |
58 return current; | |
59 } | 60 } |
60 | |
61 private: | |
62 Node* m_currentNode; | |
63 }; | 61 }; |
64 | 62 |
65 class ClassRootNodeList FINAL : public SimpleNodeList { | 63 class ClassRootNodeList { |
66 public: | 64 public: |
67 ClassRootNodeList(Node& rootNode, const AtomicString& className) | 65 ClassRootNodeList(Node& rootNode, const AtomicString& className) |
68 : m_className(className) | 66 : m_className(className) |
69 , m_rootNode(rootNode) | 67 , m_rootNode(rootNode) |
70 , m_currentElement(nextInternal(ElementTraversal::firstWithin(m_rootNode ))) { } | 68 , m_currentElement(nextInternal(ElementTraversal::firstWithin(m_rootNode ))) { } |
71 | 69 |
72 virtual bool isEmpty() const OVERRIDE { return !m_currentElement; } | 70 bool isEmpty() const { return !m_currentElement; } |
73 | 71 |
74 virtual Node* next() OVERRIDE | 72 Node* next() |
75 { | 73 { |
76 Node* current = m_currentElement; | 74 Node* current = m_currentElement; |
77 ASSERT(current); | 75 ASSERT(current); |
78 m_currentElement = nextInternal(ElementTraversal::nextSkippingChildren(* m_currentElement, &m_rootNode)); | 76 m_currentElement = nextInternal(ElementTraversal::nextSkippingChildren(* m_currentElement, &m_rootNode)); |
79 return current; | 77 return current; |
80 } | 78 } |
81 | 79 |
82 private: | 80 private: |
83 Element* nextInternal(Element* element) | 81 Element* nextInternal(Element* element) |
84 { | 82 { |
85 for (; element; element = ElementTraversal::next(*element, &m_rootNode)) { | 83 for (; element; element = ElementTraversal::next(*element, &m_rootNode)) { |
86 if (element->hasClass() && element->classNames().contains(m_classNam e)) | 84 if (element->hasClass() && element->classNames().contains(m_classNam e)) |
87 return element; | 85 return element; |
88 } | 86 } |
89 return 0; | 87 return 0; |
90 } | 88 } |
91 | 89 |
92 const AtomicString& m_className; | 90 const AtomicString& m_className; |
93 Node& m_rootNode; | 91 Node& m_rootNode; |
94 Element* m_currentElement; | 92 Element* m_currentElement; |
95 }; | 93 }; |
96 | 94 |
97 class ClassElementList FINAL : public SimpleNodeList { | 95 class ClassElementList { |
adamk
2014/01/23 21:16:13
This and the above are nearly the same, so I'm tem
Inactive
2014/01/23 21:22:10
I had the same thinking but was planning to do thi
| |
98 public: | 96 public: |
99 ClassElementList(Node& rootNode, const AtomicString& className) | 97 ClassElementList(Node& rootNode, const AtomicString& className) |
100 : m_className(className) | 98 : m_className(className) |
101 , m_rootNode(rootNode) | 99 , m_rootNode(rootNode) |
102 , m_currentElement(nextInternal(ElementTraversal::firstWithin(rootNode)) ) { } | 100 , m_currentElement(nextInternal(ElementTraversal::firstWithin(rootNode)) ) { } |
103 | 101 |
104 virtual bool isEmpty() const OVERRIDE { return !m_currentElement; } | 102 bool isEmpty() const { return !m_currentElement; } |
105 | 103 |
106 virtual Node* next() OVERRIDE | 104 Node* next() |
107 { | 105 { |
108 Node* current = m_currentElement; | 106 Node* current = m_currentElement; |
109 ASSERT(current); | 107 ASSERT(current); |
110 m_currentElement = nextInternal(ElementTraversal::next(*m_currentElement , &m_rootNode)); | 108 m_currentElement = nextInternal(ElementTraversal::next(*m_currentElement , &m_rootNode)); |
111 return current; | 109 return current; |
112 } | 110 } |
113 | 111 |
114 private: | 112 private: |
115 Element* nextInternal(Element* element) | 113 Element* nextInternal(Element* element) |
116 { | 114 { |
(...skipping 45 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
162 if (selectorMatches(m_selectors[i], targetElement, targetElement)) | 160 if (selectorMatches(m_selectors[i], targetElement, targetElement)) |
163 return true; | 161 return true; |
164 } | 162 } |
165 | 163 |
166 return false; | 164 return false; |
167 } | 165 } |
168 | 166 |
169 PassRefPtr<NodeList> SelectorDataList::queryAll(Node& rootNode) const | 167 PassRefPtr<NodeList> SelectorDataList::queryAll(Node& rootNode) const |
170 { | 168 { |
171 Vector<RefPtr<Node> > result; | 169 Vector<RefPtr<Node> > result; |
172 executeQueryAll(rootNode, result); | 170 execute<AllElementsSelectorQueryTrait>(rootNode, result); |
173 return StaticNodeList::adopt(result); | 171 return StaticNodeList::adopt(result); |
174 } | 172 } |
175 | 173 |
176 PassRefPtr<Element> SelectorDataList::queryFirst(Node& rootNode) const | 174 PassRefPtr<Element> SelectorDataList::queryFirst(Node& rootNode) const |
177 { | 175 { |
178 return executeQueryFirst(rootNode); | 176 Element* matchedElement = 0; |
177 execute<SingleElementSelectorQueryTrait>(rootNode, matchedElement); | |
178 return matchedElement; | |
179 } | 179 } |
180 | 180 |
181 void SelectorDataList::collectElementsByClassName(Node& rootNode, const AtomicSt ring& className, Vector<RefPtr<Node> >& traversalRoots) const | 181 template <typename SelectorQueryTrait> |
182 void SelectorDataList::collectElementsByClassName(Node& rootNode, const AtomicSt ring& className, typename SelectorQueryTrait::OutputType& output) const | |
182 { | 183 { |
183 for (Element* element = ElementTraversal::firstWithin(rootNode); element; el ement = ElementTraversal::next(*element, &rootNode)) { | 184 for (Element* element = ElementTraversal::firstWithin(rootNode); element; el ement = ElementTraversal::next(*element, &rootNode)) { |
184 if (element->hasClass() && element->classNames().contains(className)) | 185 if (element->hasClass() && element->classNames().contains(className)) { |
185 traversalRoots.append(element); | 186 SelectorQueryTrait::appendElement(output, element); |
187 if (SelectorQueryTrait::shouldOnlyMatchFirstElement) | |
188 return; | |
189 } | |
186 } | 190 } |
187 } | 191 } |
188 | 192 |
189 void SelectorDataList::collectElementsByTagName(Node& rootNode, const QualifiedN ame& tagName, Vector<RefPtr<Node> >& traversalRoots) const | 193 template <typename SelectorQueryTrait> |
194 void SelectorDataList::collectElementsByTagName(Node& rootNode, const QualifiedN ame& tagName, typename SelectorQueryTrait::OutputType& output) const | |
190 { | 195 { |
191 for (Element* element = ElementTraversal::firstWithin(rootNode); element; el ement = ElementTraversal::next(*element, &rootNode)) { | 196 for (Element* element = ElementTraversal::firstWithin(rootNode); element; el ement = ElementTraversal::next(*element, &rootNode)) { |
192 if (SelectorChecker::tagMatches(*element, tagName)) | 197 if (SelectorChecker::tagMatches(*element, tagName)) { |
193 traversalRoots.append(element); | 198 SelectorQueryTrait::appendElement(output, element); |
199 if (SelectorQueryTrait::shouldOnlyMatchFirstElement) | |
200 return; | |
201 } | |
194 } | 202 } |
195 } | 203 } |
196 | 204 |
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 | 205 inline bool SelectorDataList::canUseFastQuery(const Node& rootNode) const |
216 { | 206 { |
217 return m_selectors.size() == 1 && rootNode.inDocument() && !rootNode.documen t().inQuirksMode(); | 207 return m_selectors.size() == 1 && rootNode.inDocument() && !rootNode.documen t().inQuirksMode(); |
218 } | 208 } |
219 | 209 |
220 inline bool ancestorHasClassName(Node& rootNode, const AtomicString& className) | 210 inline bool ancestorHasClassName(Node& rootNode, const AtomicString& className) |
221 { | 211 { |
222 if (!rootNode.isElementNode()) | 212 if (!rootNode.isElementNode()) |
223 return false; | 213 return false; |
224 | 214 |
225 for (Element* element = &toElement(rootNode); element; element = element->pa rentElement()) { | 215 for (Element* element = &toElement(rootNode); element; element = element->pa rentElement()) { |
226 if (element->hasClass() && element->classNames().contains(className)) | 216 if (element->hasClass() && element->classNames().contains(className)) |
227 return true; | 217 return true; |
228 } | 218 } |
229 return false; | 219 return false; |
230 } | 220 } |
231 | 221 |
232 | 222 |
233 // If returns true, traversalRoots has the elements that may match the selector query. | 223 // If returns true, traversalRoots has the elements that may match the selector query. |
234 // | 224 // |
235 // If returns false, traversalRoots has the rootNode parameter or descendants of rootNode representing | 225 // If returns false, traversalRoots has the rootNode parameter or descendants of rootNode representing |
236 // the subtree for which we can limit the querySelector traversal. | 226 // the subtree for which we can limit the querySelector traversal. |
237 // | 227 // |
238 // The travseralRoots may be empty, regardless of the returned bool value, if th is method finds that the selectors won't | 228 // 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. | 229 // match any element. |
240 PassOwnPtr<SimpleNodeList> SelectorDataList::findTraverseRoots(Node& rootNode, b ool& matchTraverseRoots) const | 230 template <typename SelectorQueryTrait> |
231 void SelectorDataList::findTraverseRootsAndExecute(Node& rootNode, typename Sele ctorQueryTrait::OutputType& output) const | |
241 { | 232 { |
242 // We need to return the matches in document order. To use id lookup while t here is possiblity of multiple matches | 233 // 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. | 234 // we would need to sort the results. For now, just traverse the document in that case. |
244 ASSERT(m_selectors.size() == 1); | 235 ASSERT(m_selectors.size() == 1); |
245 ASSERT(m_selectors[0].selector); | 236 ASSERT(m_selectors[0].selector); |
246 | 237 |
247 bool isRightmostSelector = true; | 238 bool isRightmostSelector = true; |
248 bool startFromParent = false; | 239 bool startFromParent = false; |
249 | 240 |
250 for (const CSSSelector* selector = m_selectors[0].selector; selector; select or = selector->tagHistory()) { | 241 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())) { | 242 if (selector->m_match == CSSSelector::Id && !rootNode.document().contain sMultipleElementsWithId(selector->value())) { |
252 Element* element = rootNode.treeScope().getElementById(selector->val ue()); | 243 Element* element = rootNode.treeScope().getElementById(selector->val ue()); |
253 Node* adjustedNode = &rootNode; | 244 Node* adjustedNode = &rootNode; |
254 if (element && (isTreeScopeRoot(rootNode) || element->isDescendantOf (&rootNode))) | 245 if (element && (isTreeScopeRoot(rootNode) || element->isDescendantOf (&rootNode))) |
255 adjustedNode = element; | 246 adjustedNode = element; |
256 else if (!element || isRightmostSelector) | 247 else if (!element || isRightmostSelector) |
257 adjustedNode = 0; | 248 adjustedNode = 0; |
258 if (isRightmostSelector) { | 249 if (isRightmostSelector) |
259 matchTraverseRoots = true; | 250 return executeForTraverseRoot<SelectorQueryTrait>(m_selectors[0] , adjustedNode, MatchesTraverseRoots, rootNode, output); |
adamk
2014/01/23 21:16:13
returning a void function is a bit odd looking to
Inactive
2014/01/23 21:22:10
I tend to agree. The pattern was already used in t
| |
260 return adoptPtr(new SingleNodeList(adjustedNode)); | 251 |
261 } | |
262 if (startFromParent && adjustedNode) | 252 if (startFromParent && adjustedNode) |
263 adjustedNode = adjustedNode->parentNode(); | 253 adjustedNode = adjustedNode->parentNode(); |
264 | 254 |
265 matchTraverseRoots = false; | 255 return executeForTraverseRoot<SelectorQueryTrait>(m_selectors[0], ad justedNode, DoesNotMatchTraverseRoots, rootNode, output); |
266 return adoptPtr(new SingleNodeList(adjustedNode)); | |
267 } | 256 } |
268 | 257 |
269 // If we have both CSSSelector::Id and CSSSelector::Class at the same ti me, we should use Id | 258 // If we have both CSSSelector::Id and CSSSelector::Class at the same ti me, we should use Id |
270 // to find traverse root. | 259 // to find traverse root. |
271 if (!startFromParent && selector->m_match == CSSSelector::Class) { | 260 if (!SelectorQueryTrait::shouldOnlyMatchFirstElement && !startFromParent && selector->m_match == CSSSelector::Class) { |
272 if (isRightmostSelector) { | 261 if (isRightmostSelector) { |
273 matchTraverseRoots = true; | 262 OwnPtr<ClassElementList> traverseRoots = adoptPtr(new ClassEleme ntList(rootNode, selector->value())); |
adamk
2014/01/23 21:16:13
Why is this and the ClassRootNodeList heap-allocat
Inactive
2014/01/23 21:22:10
Historical reasons. This is a good point, I will c
| |
274 return adoptPtr(new ClassElementList(rootNode, selector->value() )); | 263 return executeForTraverseRoots<SelectorQueryTrait>(m_selectors[0 ], traverseRoots.get(), MatchesTraverseRoots, rootNode, output); |
275 } | 264 } |
276 matchTraverseRoots = false; | |
277 // Since there exists some ancestor element which has the class name , we need to see all children of rootNode. | 265 // 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())) | 266 if (ancestorHasClassName(rootNode, selector->value())) |
279 return adoptPtr(new SingleNodeList(&rootNode)); | 267 return executeForTraverseRoot<SelectorQueryTrait>(m_selectors[0] , &rootNode, DoesNotMatchTraverseRoots, rootNode, output); |
280 | 268 |
281 return adoptPtr(new ClassRootNodeList(rootNode, selector->value())); | 269 OwnPtr<ClassRootNodeList> traverseRoots = adoptPtr(new ClassRootNode List(rootNode, selector->value())); |
270 return executeForTraverseRoots<SelectorQueryTrait>(m_selectors[0], t raverseRoots.get(), DoesNotMatchTraverseRoots, rootNode, output); | |
282 } | 271 } |
283 | 272 |
284 if (selector->relation() == CSSSelector::SubSelector) | 273 if (selector->relation() == CSSSelector::SubSelector) |
285 continue; | 274 continue; |
286 isRightmostSelector = false; | 275 isRightmostSelector = false; |
287 if (selector->relation() == CSSSelector::DirectAdjacent || selector->rel ation() == CSSSelector::IndirectAdjacent) | 276 if (selector->relation() == CSSSelector::DirectAdjacent || selector->rel ation() == CSSSelector::IndirectAdjacent) |
288 startFromParent = true; | 277 startFromParent = true; |
289 else | 278 else |
290 startFromParent = false; | 279 startFromParent = false; |
291 } | 280 } |
292 | 281 |
293 matchTraverseRoots = false; | 282 executeForTraverseRoot<SelectorQueryTrait>(m_selectors[0], &rootNode, DoesNo tMatchTraverseRoots, rootNode, output); |
294 return adoptPtr(new SingleNodeList(&rootNode)); | |
295 } | 283 } |
296 | 284 |
297 void SelectorDataList::executeSlowQueryAll(Node& rootNode, Vector<RefPtr<Node> > & matchedElements) const | 285 template <typename SelectorQueryTrait> |
286 void SelectorDataList::executeForTraverseRoot(const SelectorData& selector, Node * traverseRoot, MatchTraverseRootState matchTraverseRoot, Node& rootNode, typena me SelectorQueryTrait::OutputType& output) const | |
298 { | 287 { |
299 for (Element* element = ElementTraversal::firstWithin(rootNode); element; el ement = ElementTraversal::next(*element, &rootNode)) { | 288 if (!traverseRoot) |
300 for (unsigned i = 0; i < m_selectors.size(); ++i) { | 289 return; |
301 if (selectorMatches(m_selectors[i], *element, rootNode)) { | 290 |
302 matchedElements.append(element); | 291 if (matchTraverseRoot) { |
303 break; | 292 if (selectorMatches(selector, toElement(*traverseRoot), rootNode)) |
304 } | 293 SelectorQueryTrait::appendElement(output, toElement(traverseRoot)); |
294 return; | |
295 } | |
296 | |
297 for (Element* element = ElementTraversal::firstWithin(*traverseRoot); elemen t; element = ElementTraversal::next(*element, traverseRoot)) { | |
298 if (selectorMatches(selector, *element, rootNode)) { | |
299 SelectorQueryTrait::appendElement(output, element); | |
300 if (SelectorQueryTrait::shouldOnlyMatchFirstElement) | |
301 return; | |
305 } | 302 } |
306 } | 303 } |
307 } | 304 } |
308 | 305 |
309 const CSSSelector* SelectorDataList::selectorForIdLookup(const CSSSelector* firs tSelector) const | 306 template <typename SelectorQueryTrait, typename SimpleNodeListType> |
307 void SelectorDataList::executeForTraverseRoots(const SelectorData& selector, Sim pleNodeListType* traverseRoots, MatchTraverseRootState matchTraverseRoots, Node& rootNode, typename SelectorQueryTrait::OutputType& output) const | |
adamk
2014/01/23 21:16:13
...and make the |traverseRoots| argument a SimpleN
Inactive
2014/01/23 21:22:10
ok
| |
310 { | 308 { |
311 for (const CSSSelector* selector = firstSelector; selector; selector = selec tor->tagHistory()) { | |
312 if (selector->m_match == CSSSelector::Id) | |
313 return selector; | |
314 if (selector->relation() != CSSSelector::SubSelector) | |
315 break; | |
316 } | |
317 return 0; | |
318 } | |
319 | |
320 void SelectorDataList::executeQueryAll(Node& rootNode, Vector<RefPtr<Node> >& ma tchedElements) const | |
321 { | |
322 if (!canUseFastQuery(rootNode)) | |
323 return executeSlowQueryAll(rootNode, matchedElements); | |
324 | |
325 ASSERT(m_selectors.size() == 1); | |
326 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()) | 309 if (traverseRoots->isEmpty()) |
370 return; | 310 return; |
371 | 311 |
372 if (matchTraverseRoots) { | 312 if (matchTraverseRoots) { |
373 while (!traverseRoots->isEmpty()) { | 313 while (!traverseRoots->isEmpty()) { |
374 Node& node = *traverseRoots->next(); | 314 Node& node = *traverseRoots->next(); |
375 Element& element = toElement(node); | 315 Element& element = toElement(node); |
376 if (selectorMatches(selector, element, rootNode)) | 316 if (selectorMatches(selector, element, rootNode)) { |
377 matchedElements.append(&element); | 317 SelectorQueryTrait::appendElement(output, &element); |
318 if (SelectorQueryTrait::shouldOnlyMatchFirstElement) | |
319 return; | |
320 } | |
378 } | 321 } |
379 return; | 322 return; |
380 } | 323 } |
381 | 324 |
382 while (!traverseRoots->isEmpty()) { | 325 while (!traverseRoots->isEmpty()) { |
383 Node* traverseRoot = traverseRoots->next(); | 326 Node* traverseRoot = traverseRoots->next(); |
384 ASSERT(traverseRoot); | 327 ASSERT(traverseRoot); |
385 for (Element* element = ElementTraversal::firstWithin(*traverseRoot); el ement; element = ElementTraversal::next(*element, traverseRoot)) { | 328 for (Element* element = ElementTraversal::firstWithin(*traverseRoot); el ement; element = ElementTraversal::next(*element, traverseRoot)) { |
386 if (selectorMatches(selector, *element, rootNode)) | 329 if (selectorMatches(selector, *element, rootNode)) { |
387 matchedElements.append(element); | 330 SelectorQueryTrait::appendElement(output, element); |
331 if (SelectorQueryTrait::shouldOnlyMatchFirstElement) | |
332 return; | |
333 } | |
388 } | 334 } |
389 } | 335 } |
390 } | 336 } |
391 | 337 |
392 // If matchTraverseRoot is true, the returned Node is the single Element that ma y match the selector query. | 338 template <typename SelectorQueryTrait> |
393 // | 339 void SelectorDataList::executeSlow(Node& rootNode, typename SelectorQueryTrait:: OutputType& output) const |
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 { | 340 { |
439 for (Element* element = ElementTraversal::firstWithin(rootNode); element; el ement = ElementTraversal::next(*element, &rootNode)) { | 341 for (Element* element = ElementTraversal::firstWithin(rootNode); element; el ement = ElementTraversal::next(*element, &rootNode)) { |
440 for (unsigned i = 0; i < m_selectors.size(); ++i) { | 342 for (unsigned i = 0; i < m_selectors.size(); ++i) { |
441 if (selectorMatches(m_selectors[i], *element, rootNode)) | 343 if (selectorMatches(m_selectors[i], *element, rootNode)) { |
442 return element; | 344 SelectorQueryTrait::appendElement(output, element); |
345 if (SelectorQueryTrait::shouldOnlyMatchFirstElement) | |
346 return; | |
347 break; | |
348 } | |
443 } | 349 } |
444 } | 350 } |
351 } | |
352 | |
353 const CSSSelector* SelectorDataList::selectorForIdLookup(const CSSSelector* firs tSelector) const | |
354 { | |
355 for (const CSSSelector* selector = firstSelector; selector; selector = selec tor->tagHistory()) { | |
356 if (selector->m_match == CSSSelector::Id) | |
357 return selector; | |
358 if (selector->relation() != CSSSelector::SubSelector) | |
359 break; | |
360 } | |
445 return 0; | 361 return 0; |
446 } | 362 } |
447 | 363 |
448 Element* SelectorDataList::executeQueryFirst(Node& rootNode) const | 364 template <typename SelectorQueryTrait> |
365 void SelectorDataList::execute(Node& rootNode, typename SelectorQueryTrait::Outp utType& output) const | |
449 { | 366 { |
450 if (!canUseFastQuery(rootNode)) | 367 if (!canUseFastQuery(rootNode)) |
451 return executeSlowQueryFirst(rootNode); | 368 return executeSlow<SelectorQueryTrait>(rootNode, output); |
452 | 369 |
453 ASSERT(m_selectors.size() == 1); | 370 ASSERT(m_selectors.size() == 1); |
454 ASSERT(m_selectors[0].selector); | 371 ASSERT(m_selectors[0].selector); |
455 | 372 |
456 const SelectorData& selector = m_selectors[0]; | 373 const SelectorData& selector = m_selectors[0]; |
457 const CSSSelector* firstSelector = selector.selector; | 374 const CSSSelector* firstSelector = selector.selector; |
458 | 375 |
459 // Fast path for querySelectorAll('#id'), querySelectorAll('tag#id'). | 376 // Fast path for querySelector*('#id'), querySelector*('tag#id'). |
460 if (const CSSSelector* idSelector = selectorForIdLookup(firstSelector)) { | 377 if (const CSSSelector* idSelector = selectorForIdLookup(firstSelector)) { |
461 const AtomicString& idToMatch = idSelector->value(); | 378 const AtomicString& idToMatch = idSelector->value(); |
462 if (rootNode.treeScope().containsMultipleElementsWithId(idToMatch)) { | 379 if (rootNode.treeScope().containsMultipleElementsWithId(idToMatch)) { |
463 const Vector<Element*>& elements = rootNode.treeScope().getAllElemen tsById(idToMatch); | 380 const Vector<Element*>& elements = rootNode.treeScope().getAllElemen tsById(idToMatch); |
464 size_t count = elements.size(); | 381 size_t count = elements.size(); |
465 for (size_t i = 0; i < count; ++i) { | 382 for (size_t i = 0; i < count; ++i) { |
466 Element* element = elements[i]; | 383 Element* element = elements[i]; |
467 ASSERT(element); | 384 ASSERT(element); |
468 if (!(isTreeScopeRoot(rootNode) || element->isDescendantOf(&root Node))) | 385 if (!(isTreeScopeRoot(rootNode) || element->isDescendantOf(&root Node))) |
469 continue; | 386 continue; |
470 if (selectorMatches(selector, *element, rootNode)) | 387 if (selectorMatches(selector, *element, rootNode)) { |
471 return element; | 388 SelectorQueryTrait::appendElement(output, element); |
389 if (SelectorQueryTrait::shouldOnlyMatchFirstElement) | |
390 return; | |
391 } | |
472 } | 392 } |
473 return 0; | 393 return; |
474 } | 394 } |
475 Element* element = rootNode.treeScope().getElementById(idToMatch); | 395 Element* element = rootNode.treeScope().getElementById(idToMatch); |
476 if (!element || !(isTreeScopeRoot(rootNode) || element->isDescendantOf(& rootNode))) | 396 if (!element || !(isTreeScopeRoot(rootNode) || element->isDescendantOf(& rootNode))) |
477 return 0; | 397 return; |
478 return selectorMatches(selector, *element, rootNode) ? element : 0; | 398 if (selectorMatches(selector, *element, rootNode)) |
399 SelectorQueryTrait::appendElement(output, element); | |
400 return; | |
479 } | 401 } |
480 | 402 |
481 if (!firstSelector->tagHistory()) { | 403 if (!firstSelector->tagHistory()) { |
482 // Fast path for querySelector('.foo'), and querySelector('div'). | 404 // Fast path for querySelector*('.foo'), and querySelector*('div'). |
483 // Many web developers uses querySelector with these simple selectors. | |
484 switch (firstSelector->m_match) { | 405 switch (firstSelector->m_match) { |
485 case CSSSelector::Class: | 406 case CSSSelector::Class: |
486 return findElementByClassName(rootNode, firstSelector->value()); | 407 return collectElementsByClassName<SelectorQueryTrait>(rootNode, firs tSelector->value(), output); |
487 case CSSSelector::Tag: | 408 case CSSSelector::Tag: |
488 return findElementByTagName(rootNode, firstSelector->tagQName()); | 409 return collectElementsByTagName<SelectorQueryTrait>(rootNode, firstS elector->tagQName(), output); |
489 default: | 410 default: |
490 break; // If we need another fast path, add here. | 411 break; // If we need another fast path, add here. |
491 } | 412 } |
492 } | 413 } |
493 | 414 |
494 bool matchTraverseRoot; | 415 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 } | 416 } |
510 | 417 |
511 SelectorQuery::SelectorQuery(const CSSSelectorList& selectorList) | 418 SelectorQuery::SelectorQuery(const CSSSelectorList& selectorList) |
512 : m_selectorList(selectorList) | 419 : m_selectorList(selectorList) |
513 { | 420 { |
514 m_selectors.initialize(m_selectorList); | 421 m_selectors.initialize(m_selectorList); |
515 } | 422 } |
516 | 423 |
517 bool SelectorQuery::matches(Element& element) const | 424 bool SelectorQuery::matches(Element& element) const |
518 { | 425 { |
(...skipping 40 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
559 m_entries.add(selectors, selectorQuery.release()); | 466 m_entries.add(selectors, selectorQuery.release()); |
560 return rawSelectorQuery; | 467 return rawSelectorQuery; |
561 } | 468 } |
562 | 469 |
563 void SelectorQueryCache::invalidate() | 470 void SelectorQueryCache::invalidate() |
564 { | 471 { |
565 m_entries.clear(); | 472 m_entries.clear(); |
566 } | 473 } |
567 | 474 |
568 } | 475 } |
OLD | NEW |