1 /*
2 * Copyright (C) 2005 Frerich Raabe <raabe@kde.org>
3 * Copyright (C) 2006, 2009 Apple Inc. All rights reserved.
4 * Copyright (C) 2007 Alexey Proskuryakov <ap@webkit.org>
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
17 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
18 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
19 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
20 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
21 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
25 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 */
27
28 #include "config.h"
29 #include "core/xml/XPathStep.h"
30
31 #include "core/XMLNSNames.h"
32 #include "core/dom/Attr.h"
33 #include "core/dom/Document.h"
34 #include "core/dom/Element.h"
35 #include "core/dom/NodeTraversal.h"
36 #include "core/xml/XPathParser.h"
37 #include "core/xml/XPathUtil.h"
38
39 namespace blink {
40 namespace XPath {
41
Step(Axis axis,const NodeTest & nodeTest)42 Step::Step(Axis axis, const NodeTest& nodeTest)
43 : m_axis(axis)
44 , m_nodeTest(adoptPtrWillBeNoop(new NodeTest(nodeTest)))
45 {
46 }
47
Step(Axis axis,const NodeTest & nodeTest,WillBeHeapVector<OwnPtrWillBeMember<Predicate>> & predicates)48 Step::Step(Axis axis, const NodeTest& nodeTest, WillBeHeapVector<OwnPtrWillBeMember<Predicate> >& predicates)
49 : m_axis(axis)
50 , m_nodeTest(adoptPtrWillBeNoop(new NodeTest(nodeTest)))
51 {
52 m_predicates.swap(predicates);
53 }
54
~Step()55 Step::~Step()
56 {
57 }
58
trace(Visitor * visitor)59 void Step::trace(Visitor* visitor)
60 {
61 visitor->trace(m_nodeTest);
62 visitor->trace(m_predicates);
63 ParseNode::trace(visitor);
64 }
65
optimize()66 void Step::optimize()
67 {
68 // Evaluate predicates as part of node test if possible to avoid building
69 // unnecessary NodeSets.
70 // E.g., there is no need to build a set of all "foo" nodes to evaluate
71 // "foo[@bar]", we can check the predicate while enumerating.
72 // This optimization can be applied to predicates that are not context node
73 // list sensitive, or to first predicate that is only context position
74 // sensitive, e.g. foo[position() mod 2 = 0].
75 WillBeHeapVector<OwnPtrWillBeMember<Predicate> > remainingPredicates;
76 for (size_t i = 0; i < m_predicates.size(); ++i) {
77 OwnPtrWillBeRawPtr<Predicate> predicate(m_predicates[i].release());
78 if ((!predicate->isContextPositionSensitive() || nodeTest().mergedPredicates().isEmpty()) && !predicate->isContextSizeSensitive() && remainingPredicates.isEmpty()) {
79 nodeTest().mergedPredicates().append(predicate.release());
80 } else {
81 remainingPredicates.append(predicate.release());
82 }
83 }
84 swap(remainingPredicates, m_predicates);
85 }
86
optimizeStepPair(Step * first,Step * second,bool & dropSecondStep)87 void optimizeStepPair(Step* first, Step* second, bool& dropSecondStep)
88 {
89 dropSecondStep = false;
90
91 if (first->m_axis == Step::DescendantOrSelfAxis
92 && first->nodeTest().kind() == Step::NodeTest::AnyNodeTest
93 && !first->m_predicates.size()
94 && !first->nodeTest().mergedPredicates().size()) {
95
96 ASSERT(first->nodeTest().data().isEmpty());
97 ASSERT(first->nodeTest().namespaceURI().isEmpty());
98
99 // Optimize the common case of "//" AKA
100 // /descendant-or-self::node()/child::NodeTest to /descendant::NodeTest.
101 if (second->m_axis == Step::ChildAxis && second->predicatesAreContextListInsensitive()) {
102 first->m_axis = Step::DescendantAxis;
103 first->nodeTest() = Step::NodeTest(second->nodeTest().kind(), second->nodeTest().data(), second->nodeTest().namespaceURI());
104 swap(second->nodeTest().mergedPredicates(), first->nodeTest().mergedPredicates());
105 swap(second->m_predicates, first->m_predicates);
106 first->optimize();
107 dropSecondStep = true;
108 }
109 }
110 }
111
predicatesAreContextListInsensitive() const112 bool Step::predicatesAreContextListInsensitive() const
113 {
114 for (size_t i = 0; i < m_predicates.size(); ++i) {
115 Predicate* predicate = m_predicates[i].get();
116 if (predicate->isContextPositionSensitive() || predicate->isContextSizeSensitive())
117 return false;
118 }
119
120 for (size_t i = 0; i < nodeTest().mergedPredicates().size(); ++i) {
121 Predicate* predicate = nodeTest().mergedPredicates()[i].get();
122 if (predicate->isContextPositionSensitive() || predicate->isContextSizeSensitive())
123 return false;
124 }
125
126 return true;
127 }
128
evaluate(EvaluationContext & evaluationContext,Node * context,NodeSet & nodes) const129 void Step::evaluate(EvaluationContext& evaluationContext, Node* context, NodeSet& nodes) const
130 {
131 evaluationContext.position = 0;
132
133 nodesInAxis(evaluationContext, context, nodes);
134
135 // Check predicates that couldn't be merged into node test.
136 for (unsigned i = 0; i < m_predicates.size(); i++) {
137 Predicate* predicate = m_predicates[i].get();
138
139 OwnPtrWillBeRawPtr<NodeSet> newNodes(NodeSet::create());
140 if (!nodes.isSorted())
141 newNodes->markSorted(false);
142
143 for (unsigned j = 0; j < nodes.size(); j++) {
144 Node* node = nodes[j];
145
146 evaluationContext.node = node;
147 evaluationContext.size = nodes.size();
148 evaluationContext.position = j + 1;
149 if (predicate->evaluate(evaluationContext))
150 newNodes->append(node);
151 }
152
153 nodes.swap(*newNodes);
154 }
155 }
156
157 #if ENABLE(ASSERT)
primaryNodeType(Step::Axis axis)158 static inline Node::NodeType primaryNodeType(Step::Axis axis)
159 {
160 switch (axis) {
161 case Step::AttributeAxis:
162 return Node::ATTRIBUTE_NODE;
163 default:
164 return Node::ELEMENT_NODE;
165 }
166 }
167 #endif
168
169 // Evaluate NodeTest without considering merged predicates.
nodeMatchesBasicTest(Node * node,Step::Axis axis,const Step::NodeTest & nodeTest)170 static inline bool nodeMatchesBasicTest(Node* node, Step::Axis axis, const Step::NodeTest& nodeTest)
171 {
172 switch (nodeTest.kind()) {
173 case Step::NodeTest::TextNodeTest: {
174 Node::NodeType type = node->nodeType();
175 return type == Node::TEXT_NODE || type == Node::CDATA_SECTION_NODE;
176 }
177 case Step::NodeTest::CommentNodeTest:
178 return node->nodeType() == Node::COMMENT_NODE;
179 case Step::NodeTest::ProcessingInstructionNodeTest: {
180 const AtomicString& name = nodeTest.data();
181 return node->nodeType() == Node::PROCESSING_INSTRUCTION_NODE && (name.isEmpty() || node->nodeName() == name);
182 }
183 case Step::NodeTest::AnyNodeTest:
184 return true;
185 case Step::NodeTest::NameTest: {
186 const AtomicString& name = nodeTest.data();
187 const AtomicString& namespaceURI = nodeTest.namespaceURI();
188
189 if (axis == Step::AttributeAxis) {
190 ASSERT(node->isAttributeNode());
191
192 // In XPath land, namespace nodes are not accessible on the
193 // attribute axis.
194 if (node->namespaceURI() == XMLNSNames::xmlnsNamespaceURI)
195 return false;
196
197 if (name == starAtom)
198 return namespaceURI.isEmpty() || node->namespaceURI() == namespaceURI;
199
200 return node->localName() == name && node->namespaceURI() == namespaceURI;
201 }
202
203 // Node test on the namespace axis is not implemented yet, the caller
204 // has a check for it.
205 ASSERT(axis != Step::NamespaceAxis);
206
207 // For other axes, the principal node type is element.
208 ASSERT(primaryNodeType(axis) == Node::ELEMENT_NODE);
209 if (!node->isElementNode())
210 return false;
211 Element& element = toElement(*node);
212
213 if (name == starAtom)
214 return namespaceURI.isEmpty() || namespaceURI == element.namespaceURI();
215
216 if (element.document().isHTMLDocument()) {
217 if (element.isHTMLElement()) {
218 // Paths without namespaces should match HTML elements in HTML
219 // documents despite those having an XHTML namespace. Names are
220 // compared case-insensitively.
221 return equalIgnoringCase(element.localName(), name) && (namespaceURI.isNull() || namespaceURI == element.namespaceURI());
222 }
223 // An expression without any prefix shouldn't match no-namespace
224 // nodes (because HTML5 says so).
225 return element.hasLocalName(name) && namespaceURI == element.namespaceURI() && !namespaceURI.isNull();
226 }
227 return element.hasLocalName(name) && namespaceURI == element.namespaceURI();
228 }
229 }
230 ASSERT_NOT_REACHED();
231 return false;
232 }
233
nodeMatches(EvaluationContext & evaluationContext,Node * node,Step::Axis axis,const Step::NodeTest & nodeTest)234 static inline bool nodeMatches(EvaluationContext& evaluationContext, Node* node, Step::Axis axis, const Step::NodeTest& nodeTest)
235 {
236 if (!nodeMatchesBasicTest(node, axis, nodeTest))
237 return false;
238
239 // Only the first merged predicate may depend on position.
240 ++evaluationContext.position;
241
242 const WillBeHeapVector<OwnPtrWillBeMember<Predicate> >& mergedPredicates = nodeTest.mergedPredicates();
243 for (unsigned i = 0; i < mergedPredicates.size(); i++) {
244 Predicate* predicate = mergedPredicates[i].get();
245
246 evaluationContext.node = node;
247 // No need to set context size - we only get here when evaluating
248 // predicates that do not depend on it.
249 if (!predicate->evaluate(evaluationContext))
250 return false;
251 }
252
253 return true;
254 }
255
256 // Result nodes are ordered in axis order. Node test (including merged
257 // predicates) is applied.
nodesInAxis(EvaluationContext & evaluationContext,Node * context,NodeSet & nodes) const258 void Step::nodesInAxis(EvaluationContext& evaluationContext, Node* context, NodeSet& nodes) const
259 {
260 ASSERT(nodes.isEmpty());
261 switch (m_axis) {
262 case ChildAxis:
263 // In XPath model, attribute nodes do not have children.
264 if (context->isAttributeNode())
265 return;
266
267 for (Node* n = context->firstChild(); n; n = n->nextSibling()) {
268 if (nodeMatches(evaluationContext, n, ChildAxis, nodeTest()))
269 nodes.append(n);
270 }
271 return;
272
273 case DescendantAxis:
274 // In XPath model, attribute nodes do not have children.
275 if (context->isAttributeNode())
276 return;
277
278 for (Node* n = context->firstChild(); n; n = NodeTraversal::next(*n, context)) {
279 if (nodeMatches(evaluationContext, n, DescendantAxis, nodeTest()))
280 nodes.append(n);
281 }
282 return;
283
284 case ParentAxis:
285 if (context->isAttributeNode()) {
286 Element* n = toAttr(context)->ownerElement();
287 if (nodeMatches(evaluationContext, n, ParentAxis, nodeTest()))
288 nodes.append(n);
289 } else {
290 ContainerNode* n = context->parentNode();
291 if (n && nodeMatches(evaluationContext, n, ParentAxis, nodeTest()))
292 nodes.append(n);
293 }
294 return;
295
296 case AncestorAxis: {
297 Node* n = context;
298 if (context->isAttributeNode()) {
299 n = toAttr(context)->ownerElement();
300 if (nodeMatches(evaluationContext, n, AncestorAxis, nodeTest()))
301 nodes.append(n);
302 }
303 for (n = n->parentNode(); n; n = n->parentNode()) {
304 if (nodeMatches(evaluationContext, n, AncestorAxis, nodeTest()))
305 nodes.append(n);
306 }
307 nodes.markSorted(false);
308 return;
309 }
310
311 case FollowingSiblingAxis:
312 if (context->nodeType() == Node::ATTRIBUTE_NODE)
313 return;
314
315 for (Node* n = context->nextSibling(); n; n = n->nextSibling()) {
316 if (nodeMatches(evaluationContext, n, FollowingSiblingAxis, nodeTest()))
317 nodes.append(n);
318 }
319 return;
320
321 case PrecedingSiblingAxis:
322 if (context->nodeType() == Node::ATTRIBUTE_NODE)
323 return;
324
325 for (Node* n = context->previousSibling(); n; n = n->previousSibling()) {
326 if (nodeMatches(evaluationContext, n, PrecedingSiblingAxis, nodeTest()))
327 nodes.append(n);
328 }
329 nodes.markSorted(false);
330 return;
331
332 case FollowingAxis:
333 if (context->isAttributeNode()) {
334 for (Node* p = NodeTraversal::next(*toAttr(context)->ownerElement()); p; p = NodeTraversal::next(*p)) {
335 if (nodeMatches(evaluationContext, p, FollowingAxis, nodeTest()))
336 nodes.append(p);
337 }
338 } else {
339 for (Node* p = context; !isRootDomNode(p); p = p->parentNode()) {
340 for (Node* n = p->nextSibling(); n; n = n->nextSibling()) {
341 if (nodeMatches(evaluationContext, n, FollowingAxis, nodeTest()))
342 nodes.append(n);
343 for (Node* c = n->firstChild(); c; c = NodeTraversal::next(*c, n)) {
344 if (nodeMatches(evaluationContext, c, FollowingAxis, nodeTest()))
345 nodes.append(c);
346 }
347 }
348 }
349 }
350 return;
351
352 case PrecedingAxis: {
353 if (context->isAttributeNode())
354 context = toAttr(context)->ownerElement();
355
356 Node* n = context;
357 while (ContainerNode* parent = n->parentNode()) {
358 for (n = NodeTraversal::previous(*n); n != parent; n = NodeTraversal::previous(*n)) {
359 if (nodeMatches(evaluationContext, n, PrecedingAxis, nodeTest()))
360 nodes.append(n);
361 }
362 n = parent;
363 }
364 nodes.markSorted(false);
365 return;
366 }
367
368 case AttributeAxis: {
369 if (!context->isElementNode())
370 return;
371
372 Element* contextElement = toElement(context);
373 // Avoid lazily creating attribute nodes for attributes that we do not
374 // need anyway.
375 if (nodeTest().kind() == NodeTest::NameTest && nodeTest().data() != starAtom) {
376 RefPtrWillBeRawPtr<Node> n = contextElement->getAttributeNodeNS(nodeTest().namespaceURI(), nodeTest().data());
377 // In XPath land, namespace nodes are not accessible on the attribute axis.
378 if (n && n->namespaceURI() != XMLNSNames::xmlnsNamespaceURI) {
379 // Still need to check merged predicates.
380 if (nodeMatches(evaluationContext, n.get(), AttributeAxis, nodeTest()))
381 nodes.append(n.release());
382 }
383 return;
384 }
385
386 AttributeCollection attributes = contextElement->attributes();
387 AttributeCollection::iterator end = attributes.end();
388 for (AttributeCollection::iterator it = attributes.begin(); it != end; ++it) {
389 RefPtrWillBeRawPtr<Attr> attr = contextElement->ensureAttr(it->name());
390 if (nodeMatches(evaluationContext, attr.get(), AttributeAxis, nodeTest()))
391 nodes.append(attr.release());
392 }
393 return;
394 }
395
396 case NamespaceAxis:
397 // XPath namespace nodes are not implemented.
398 return;
399
400 case SelfAxis:
401 if (nodeMatches(evaluationContext, context, SelfAxis, nodeTest()))
402 nodes.append(context);
403 return;
404
405 case DescendantOrSelfAxis:
406 if (nodeMatches(evaluationContext, context, DescendantOrSelfAxis, nodeTest()))
407 nodes.append(context);
408 // In XPath model, attribute nodes do not have children.
409 if (context->isAttributeNode())
410 return;
411
412 for (Node* n = context->firstChild(); n; n = NodeTraversal::next(*n, context)) {
413 if (nodeMatches(evaluationContext, n, DescendantOrSelfAxis, nodeTest()))
414 nodes.append(n);
415 }
416 return;
417
418 case AncestorOrSelfAxis: {
419 if (nodeMatches(evaluationContext, context, AncestorOrSelfAxis, nodeTest()))
420 nodes.append(context);
421 Node* n = context;
422 if (context->isAttributeNode()) {
423 n = toAttr(context)->ownerElement();
424 if (nodeMatches(evaluationContext, n, AncestorOrSelfAxis, nodeTest()))
425 nodes.append(n);
426 }
427 for (n = n->parentNode(); n; n = n->parentNode()) {
428 if (nodeMatches(evaluationContext, n, AncestorOrSelfAxis, nodeTest()))
429 nodes.append(n);
430 }
431 nodes.markSorted(false);
432 return;
433 }
434 }
435 ASSERT_NOT_REACHED();
436 }
437
438 }
439
440 }
441