Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(458)

Side by Side Diff: Source/core/dom/SelectorQuery.cpp

Issue 142513003: Use Traits in SelectorQuery to avoid a lot of code duplication (Closed) Base URL: svn://svn.chromium.org/blink/trunk
Patch Set: Rename methods Created 6 years, 11 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
« no previous file with comments | « Source/core/dom/SelectorQuery.h ('k') | no next file » | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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
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
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
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 }
OLDNEW
« no previous file with comments | « Source/core/dom/SelectorQuery.h ('k') | no next file » | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698