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

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

Issue 18732004: Add fast path for querySelector(All) (Closed) Base URL: svn://svn.chromium.org/blink/trunk
Patch Set: Created 7 years, 5 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 Apple Inc. All rights reserved.
3 * 3 *
4 * Redistribution and use in source and binary forms, with or without 4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions 5 * modification, are permitted provided that the following conditions
6 * are met: 6 * are met:
7 * 7 *
8 * 1. Redistributions of source code must retain the above copyright 8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer. 9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright 10 * 2. Redistributions in binary form must reproduce the above copyright
(...skipping 86 matching lines...) Expand 10 before | Expand all | Expand 10 after
97 ASSERT(result.first()->isElementNode()); 97 ASSERT(result.first()->isElementNode());
98 return toElement(result.first().get()); 98 return toElement(result.first().get());
99 } 99 }
100 100
101 static inline bool isTreeScopeRoot(Node* node) 101 static inline bool isTreeScopeRoot(Node* node)
102 { 102 {
103 ASSERT(node); 103 ASSERT(node);
104 return node->isDocumentNode() || node->isShadowRoot(); 104 return node->isDocumentNode() || node->isShadowRoot();
105 } 105 }
106 106
107 // If the first pair value is true, the returned Node is the single Element that may match the selector query. 107 static bool hasNodeContains(DocumentOrderedList& rootNodes, Node* node)
108 {
109 for (DocumentOrderedList::iterator it = rootNodes.begin(); it != rootNodes.e nd(); ++it) {
110 Node* rootNode = *it;
111 if (rootNode->contains(node))
112 return true;
113 }
114 return false;
115 }
116
117 static void addWithRemoveNodesContainedBy(DocumentOrderedList& rootNodes, Node* rootNode)
118 {
119 rootNodes.add(rootNode);
120
121 // Remove nodes contained by a given rootNode, because rootNode is not given in document order.
122 DocumentOrderedList::iterator it = rootNodes.end();
123 do {
124 --it;
125 if (rootNode == *it)
126 break;
127 if (rootNode->contains(*it))
128 rootNodes.remove(*it);
129 } while (it != rootNodes.begin());
130 }
131
132 // If returns true, traversalRoots has the elements that may match the selector query.
108 // 133 //
109 // If the first value is false, the returned Node is the rootNode parameter or a descendant of rootNode representing 134 // If returns false, traversalRoots has the rootNode parameter or descendants of rootNode representing
110 // the subtree for which we can limit the querySelector traversal. 135 // the subtree for which we can limit the querySelector traversal.
111 // 136 //
112 // The returned Node may be 0, regardless of the returned bool value, if this me thod finds that the selectors won't 137 // The travseralRoots may be empty, regardless of the returned bool value, if th is method finds that the selectors won't
113 // match any element. 138 // match any element.
114 std::pair<bool, Node*> SelectorDataList::findTraverseRoot(Node* rootNode) const 139 bool SelectorDataList::findTraverseRoot(Node* rootNode, DocumentOrderedList& tra versalRoots) const
115 { 140 {
116 // We need to return the matches in document order. To use id lookup while t here is possiblity of multiple matches 141 // We need to return the matches in document order. To use id lookup while t here is possiblity of multiple matches
117 // we would need to sort the results. For now, just traverse the document in that case. 142 // we would need to sort the results. For now, just traverse the document in that case.
118 if (m_selectors.size() != 1) 143 if (m_selectors.size() != 1 || !rootNode->inDocument() || rootNode->document ()->inQuirksMode()) {
119 return std::make_pair(false, rootNode); 144 traversalRoots.parserAdd(rootNode);
120 if (!rootNode->inDocument()) 145 return false;
121 return std::make_pair(false, rootNode); 146 }
122 if (rootNode->document()->inQuirksMode())
123 return std::make_pair(false, rootNode);
124 147
125 bool matchSingleNode = true; 148 bool matchTraverseRoots = true;
126 bool startFromParent = false; 149 bool startFromParent = false;
127 for (const CSSSelector* selector = m_selectors[0].selector; selector; select or = selector->tagHistory()) { 150 for (const CSSSelector* selector = m_selectors[0].selector; selector; select or = selector->tagHistory()) {
128 if (selector->m_match == CSSSelector::Id && !rootNode->document()->conta insMultipleElementsWithId(selector->value())) { 151 if (selector->m_match == CSSSelector::Id && !rootNode->document()->conta insMultipleElementsWithId(selector->value())) {
129 Element* element = rootNode->treeScope()->getElementById(selector->v alue()); 152 Element* element = rootNode->treeScope()->getElementById(selector->v alue());
130 if (element && (isTreeScopeRoot(rootNode) || element->isDescendantOf (rootNode))) 153 if (element && (isTreeScopeRoot(rootNode) || element->isDescendantOf (rootNode)))
131 rootNode = element; 154 rootNode = element;
132 else if (!element || matchSingleNode) 155 else if (!element || matchTraverseRoots)
133 rootNode = 0; 156 rootNode = 0;
134 if (matchSingleNode) 157 if (matchTraverseRoots) {
135 return std::make_pair(true, rootNode); 158 if (rootNode)
159 traversalRoots.parserAdd(rootNode);
160 return true;
161 }
136 if (startFromParent && rootNode) 162 if (startFromParent && rootNode)
137 rootNode = rootNode->parentNode(); 163 rootNode = rootNode->parentNode();
138 return std::make_pair(false, rootNode); 164 if (rootNode)
165 traversalRoots.parserAdd(rootNode);
166 return false;
139 } 167 }
168 if (selector->m_match == CSSSelector::Class) {
169 RefPtr<NodeList> nodeList = rootNode->getElementsByClassName(selecto r->value());
haraken 2013/07/08 11:33:47 oh, this will create unexpected NodeList cache in
170 if (startFromParent) {
171 // Looking at parent nodes, we need to sort in document order.
172 for (unsigned i = 0; i < nodeList->length(); ++i) {
173 Node* node = nodeList->item(i);
174 if (!node || (!isTreeScopeRoot(rootNode) && !node->isDescend antOf(rootNode)))
175 continue;
176 if (Node* parent = node->parentNode()) {
177 if (!hasNodeContains(traversalRoots, parent))
178 addWithRemoveNodesContainedBy(traversalRoots, parent );
179 }
180 }
181 } else if (matchTraverseRoots) {
182 for (unsigned i = 0; i < nodeList->length(); ++i) {
183 Node* node = nodeList->item(i);
184 if (node && (isTreeScopeRoot(rootNode) || node->isDescendant Of(rootNode)))
185 traversalRoots.parserAdd(node);
186 }
187 return true;
188 } else {
189 for (unsigned i = 0; i < nodeList->length(); ++i) {
190 Node* node = nodeList->item(i);
191 if (!node || (!isTreeScopeRoot(rootNode) && !node->isDescend antOf(rootNode)))
192 continue;
193 // Need to check whether the new node is contained by other nodes.
194 if (!hasNodeContains(traversalRoots, node))
195 traversalRoots.add(node);
196 }
197 }
198 return false;
199 }
200
140 if (selector->relation() == CSSSelector::SubSelector) 201 if (selector->relation() == CSSSelector::SubSelector)
141 continue; 202 continue;
142 matchSingleNode = false; 203 matchTraverseRoots = false;
143 if (selector->relation() == CSSSelector::DirectAdjacent || selector->rel ation() == CSSSelector::IndirectAdjacent) 204 if (selector->relation() == CSSSelector::DirectAdjacent || selector->rel ation() == CSSSelector::IndirectAdjacent)
144 startFromParent = true; 205 startFromParent = true;
145 else 206 else
146 startFromParent = false; 207 startFromParent = false;
147 } 208 }
148 return std::make_pair(false, rootNode); 209 if (rootNode)
210 traversalRoots.parserAdd(rootNode);
211 return false;
149 } 212 }
150 213
151 template <bool firstMatchOnly> 214 template <bool firstMatchOnly>
152 void SelectorDataList::execute(Node* rootNode, Vector<RefPtr<Node> >& matchedEle ments) const 215 void SelectorDataList::execute(Node* rootNode, Vector<RefPtr<Node> >& matchedEle ments) const
153 { 216 {
154 std::pair<bool, Node*> traverseRoot = findTraverseRoot(rootNode); 217 DocumentOrderedList traverseRoots;
155 if (!traverseRoot.second) 218 bool matchTraverseRoots = findTraverseRoot(rootNode, traverseRoots);
219
220 if (traverseRoots.isEmpty())
156 return; 221 return;
157 Node* traverseRootNode = traverseRoot.second; 222 if (matchTraverseRoots) {
158 if (traverseRoot.first) {
159 ASSERT(m_selectors.size() == 1); 223 ASSERT(m_selectors.size() == 1);
160 ASSERT(traverseRootNode->isElementNode()); 224 for (DocumentOrderedList::iterator it = traverseRoots.begin(); it != tra verseRoots.end(); ++it) {
161 Element* element = toElement(traverseRootNode); 225 Element* element = toElement(*it);
162 if (selectorMatches(m_selectors[0], element, rootNode)) 226 if (selectorMatches(m_selectors[0], element, rootNode))
163 matchedElements.append(element); 227 matchedElements.append(element);
228 }
164 return; 229 return;
165 } 230 }
166 231
167 unsigned selectorCount = m_selectors.size(); 232 unsigned selectorCount = m_selectors.size();
168 if (selectorCount == 1) { 233 if (selectorCount == 1) {
169 const SelectorData& selector = m_selectors[0]; 234 const SelectorData& selector = m_selectors[0];
170 for (Element* element = ElementTraversal::firstWithin(rootNode); element ; element = ElementTraversal::next(element, rootNode)) { 235 for (DocumentOrderedList::iterator it = traverseRoots.begin(); it != tra verseRoots.end(); ++it) {
171 if (selectorMatches(selector, element, rootNode)) { 236 Node* traverseRoot = *it;
172 matchedElements.append(element); 237 for (Element* element = ElementTraversal::firstWithin(traverseRoot); element; element = ElementTraversal::next(element, traverseRoot)) {
173 if (firstMatchOnly) 238 if (selectorMatches(selector, element, rootNode)) {
174 return; 239 matchedElements.append(element);
240 if (firstMatchOnly)
241 return;
242 }
175 } 243 }
176 } 244 }
177 return; 245 return;
178 } 246 }
179 for (Element* element = ElementTraversal::firstWithin(rootNode); element; el ement = ElementTraversal::next(element, rootNode)) { 247 for (Element* element = ElementTraversal::firstWithin(rootNode); element; el ement = ElementTraversal::next(element, rootNode)) {
180 for (unsigned i = 0; i < selectorCount; ++i) { 248 for (unsigned i = 0; i < selectorCount; ++i) {
181 if (selectorMatches(m_selectors[i], element, rootNode)) { 249 if (selectorMatches(m_selectors[i], element, rootNode)) {
182 matchedElements.append(element); 250 matchedElements.append(element);
183 if (firstMatchOnly) 251 if (firstMatchOnly)
184 return; 252 return;
(...skipping 54 matching lines...) Expand 10 before | Expand all | Expand 10 after
239 m_entries.add(selectors, selectorQuery.release()); 307 m_entries.add(selectors, selectorQuery.release());
240 return rawSelectorQuery; 308 return rawSelectorQuery;
241 } 309 }
242 310
243 void SelectorQueryCache::invalidate() 311 void SelectorQueryCache::invalidate()
244 { 312 {
245 m_entries.clear(); 313 m_entries.clear();
246 } 314 }
247 315
248 } 316 }
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