OLD | NEW |
---|---|
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 Loading... | |
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()); | |
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; | |
haraken
2013/07/08 06:13:16
This change looks correct, but we might want to ha
| |
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 Loading... | |
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 } |
OLD | NEW |