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 "XPathStep.h"
30
31 #if ENABLE(XPATH)
32
33 #include "Attr.h"
34 #include "Document.h"
35 #include "Element.h"
36 #include "NamedNodeMap.h"
37 #include "XPathParser.h"
38 #include "XPathUtil.h"
39
40 namespace WebCore {
41 namespace XPath {
42
Step(Axis axis,const NodeTest & nodeTest,const Vector<Predicate * > & predicates)43 Step::Step(Axis axis, const NodeTest& nodeTest, const Vector<Predicate*>& predicates)
44 : m_axis(axis)
45 , m_nodeTest(nodeTest)
46 , m_predicates(predicates)
47 {
48 }
49
~Step()50 Step::~Step()
51 {
52 deleteAllValues(m_predicates);
53 deleteAllValues(m_nodeTest.mergedPredicates());
54 }
55
optimize()56 void Step::optimize()
57 {
58 // Evaluate predicates as part of node test if possible to avoid building unnecessary NodeSets.
59 // E.g., there is no need to build a set of all "foo" nodes to evaluate "foo[@bar]", we can check the predicate while enumerating.
60 // This optimization can be applied to predicates that are not context node list sensitive, or to first predicate that is only context position sensitive, e.g. foo[position() mod 2 = 0].
61 Vector<Predicate*> remainingPredicates;
62 for (size_t i = 0; i < m_predicates.size(); ++i) {
63 Predicate* predicate = m_predicates[i];
64 if ((!predicate->isContextPositionSensitive() || m_nodeTest.mergedPredicates().isEmpty()) && !predicate->isContextSizeSensitive() && remainingPredicates.isEmpty()) {
65 m_nodeTest.mergedPredicates().append(predicate);
66 } else
67 remainingPredicates.append(predicate);
68 }
69 swap(remainingPredicates, m_predicates);
70 }
71
optimizeStepPair(Step * first,Step * second,bool & dropSecondStep)72 void optimizeStepPair(Step* first, Step* second, bool& dropSecondStep)
73 {
74 dropSecondStep = false;
75
76 if (first->m_axis == Step::DescendantOrSelfAxis
77 && first->m_nodeTest.kind() == Step::NodeTest::AnyNodeTest
78 && !first->m_predicates.size()
79 && !first->m_nodeTest.mergedPredicates().size()) {
80
81 ASSERT(first->m_nodeTest.data().isEmpty());
82 ASSERT(first->m_nodeTest.namespaceURI().isEmpty());
83
84 // Optimize the common case of "//" AKA /descendant-or-self::node()/child::NodeTest to /descendant::NodeTest.
85 if (second->m_axis == Step::ChildAxis && second->predicatesAreContextListInsensitive()) {
86 first->m_axis = Step::DescendantAxis;
87 first->m_nodeTest = Step::NodeTest(second->m_nodeTest.kind(), second->m_nodeTest.data(), second->m_nodeTest.namespaceURI());
88 swap(second->m_nodeTest.mergedPredicates(), first->m_nodeTest.mergedPredicates());
89 swap(second->m_predicates, first->m_predicates);
90 first->optimize();
91 dropSecondStep = true;
92 }
93 }
94 }
95
predicatesAreContextListInsensitive() const96 bool Step::predicatesAreContextListInsensitive() const
97 {
98 for (size_t i = 0; i < m_predicates.size(); ++i) {
99 Predicate* predicate = m_predicates[i];
100 if (predicate->isContextPositionSensitive() || predicate->isContextSizeSensitive())
101 return false;
102 }
103
104 for (size_t i = 0; i < m_nodeTest.mergedPredicates().size(); ++i) {
105 Predicate* predicate = m_nodeTest.mergedPredicates()[i];
106 if (predicate->isContextPositionSensitive() || predicate->isContextSizeSensitive())
107 return false;
108 }
109
110 return true;
111 }
112
evaluate(Node * context,NodeSet & nodes) const113 void Step::evaluate(Node* context, NodeSet& nodes) const
114 {
115 EvaluationContext& evaluationContext = Expression::evaluationContext();
116 evaluationContext.position = 0;
117
118 nodesInAxis(context, nodes);
119
120 // Check predicates that couldn't be merged into node test.
121 for (unsigned i = 0; i < m_predicates.size(); i++) {
122 Predicate* predicate = m_predicates[i];
123
124 NodeSet newNodes;
125 if (!nodes.isSorted())
126 newNodes.markSorted(false);
127
128 for (unsigned j = 0; j < nodes.size(); j++) {
129 Node* node = nodes[j];
130
131 evaluationContext.node = node;
132 evaluationContext.size = nodes.size();
133 evaluationContext.position = j + 1;
134 if (predicate->evaluate())
135 newNodes.append(node);
136 }
137
138 nodes.swap(newNodes);
139 }
140 }
141
primaryNodeType(Step::Axis axis)142 static inline Node::NodeType primaryNodeType(Step::Axis axis)
143 {
144 switch (axis) {
145 case Step::AttributeAxis:
146 return Node::ATTRIBUTE_NODE;
147 case Step::NamespaceAxis:
148 return Node::XPATH_NAMESPACE_NODE;
149 default:
150 return Node::ELEMENT_NODE;
151 }
152 }
153
154 // Evaluate NodeTest without considering merged predicates.
nodeMatchesBasicTest(Node * node,Step::Axis axis,const Step::NodeTest & nodeTest)155 static inline bool nodeMatchesBasicTest(Node* node, Step::Axis axis, const Step::NodeTest& nodeTest)
156 {
157 switch (nodeTest.kind()) {
158 case Step::NodeTest::TextNodeTest:
159 return node->nodeType() == Node::TEXT_NODE || node->nodeType() == Node::CDATA_SECTION_NODE;
160 case Step::NodeTest::CommentNodeTest:
161 return node->nodeType() == Node::COMMENT_NODE;
162 case Step::NodeTest::ProcessingInstructionNodeTest: {
163 const AtomicString& name = nodeTest.data();
164 return node->nodeType() == Node::PROCESSING_INSTRUCTION_NODE && (name.isEmpty() || node->nodeName() == name);
165 }
166 case Step::NodeTest::AnyNodeTest:
167 return true;
168 case Step::NodeTest::NameTest: {
169 const AtomicString& name = nodeTest.data();
170 const AtomicString& namespaceURI = nodeTest.namespaceURI();
171
172 if (axis == Step::AttributeAxis) {
173 ASSERT(node->isAttributeNode());
174
175 // In XPath land, namespace nodes are not accessible on the attribute axis.
176 if (node->namespaceURI() == "http://www.w3.org/2000/xmlns/")
177 return false;
178
179 if (name == starAtom)
180 return namespaceURI.isEmpty() || node->namespaceURI() == namespaceURI;
181
182 return node->localName() == name && node->namespaceURI() == namespaceURI;
183 }
184
185 // Node test on the namespace axis is not implemented yet, the caller has a check for it.
186 ASSERT(axis != Step::NamespaceAxis);
187
188 // For other axes, the principal node type is element.
189 ASSERT(primaryNodeType(axis) == Node::ELEMENT_NODE);
190 if (node->nodeType() != Node::ELEMENT_NODE)
191 return false;
192
193 if (name == starAtom)
194 return namespaceURI.isEmpty() || namespaceURI == node->namespaceURI();
195
196 if (node->isHTMLElement() && node->document()->isHTMLDocument()) {
197 // Paths without namespaces should match HTML elements in HTML documents despite those having an XHTML namespace. Names are compared case-insensitively.
198 return equalIgnoringCase(static_cast<Element*>(node)->localName(), name) && (namespaceURI.isNull() || namespaceURI == node->namespaceURI());
199 }
200 return static_cast<Element*>(node)->hasLocalName(name) && namespaceURI == node->namespaceURI();
201 }
202 }
203 ASSERT_NOT_REACHED();
204 return false;
205 }
206
nodeMatches(Node * node,Step::Axis axis,const Step::NodeTest & nodeTest)207 static inline bool nodeMatches(Node* node, Step::Axis axis, const Step::NodeTest& nodeTest)
208 {
209 if (!nodeMatchesBasicTest(node, axis, nodeTest))
210 return false;
211
212 EvaluationContext& evaluationContext = Expression::evaluationContext();
213
214 // Only the first merged predicate may depend on position.
215 ++evaluationContext.position;
216
217 const Vector<Predicate*>& mergedPredicates = nodeTest.mergedPredicates();
218 for (unsigned i = 0; i < mergedPredicates.size(); i++) {
219 Predicate* predicate = mergedPredicates[i];
220
221 evaluationContext.node = node;
222 // No need to set context size - we only get here when evaluating predicates that do not depend on it.
223 if (!predicate->evaluate())
224 return false;
225 }
226
227 return true;
228 }
229
230 // Result nodes are ordered in axis order. Node test (including merged predicates) is applied.
nodesInAxis(Node * context,NodeSet & nodes) const231 void Step::nodesInAxis(Node* context, NodeSet& nodes) const
232 {
233 ASSERT(nodes.isEmpty());
234 switch (m_axis) {
235 case ChildAxis:
236 if (context->isAttributeNode()) // In XPath model, attribute nodes do not have children.
237 return;
238
239 for (Node* n = context->firstChild(); n; n = n->nextSibling())
240 if (nodeMatches(n, ChildAxis, m_nodeTest))
241 nodes.append(n);
242 return;
243 case DescendantAxis:
244 if (context->isAttributeNode()) // In XPath model, attribute nodes do not have children.
245 return;
246
247 for (Node* n = context->firstChild(); n; n = n->traverseNextNode(context))
248 if (nodeMatches(n, DescendantAxis, m_nodeTest))
249 nodes.append(n);
250 return;
251 case ParentAxis:
252 if (context->isAttributeNode()) {
253 Node* n = static_cast<Attr*>(context)->ownerElement();
254 if (nodeMatches(n, ParentAxis, m_nodeTest))
255 nodes.append(n);
256 } else {
257 Node* n = context->parentNode();
258 if (n && nodeMatches(n, ParentAxis, m_nodeTest))
259 nodes.append(n);
260 }
261 return;
262 case AncestorAxis: {
263 Node* n = context;
264 if (context->isAttributeNode()) {
265 n = static_cast<Attr*>(context)->ownerElement();
266 if (nodeMatches(n, AncestorAxis, m_nodeTest))
267 nodes.append(n);
268 }
269 for (n = n->parentNode(); n; n = n->parentNode())
270 if (nodeMatches(n, AncestorAxis, m_nodeTest))
271 nodes.append(n);
272 nodes.markSorted(false);
273 return;
274 }
275 case FollowingSiblingAxis:
276 if (context->nodeType() == Node::ATTRIBUTE_NODE ||
277 context->nodeType() == Node::XPATH_NAMESPACE_NODE)
278 return;
279
280 for (Node* n = context->nextSibling(); n; n = n->nextSibling())
281 if (nodeMatches(n, FollowingSiblingAxis, m_nodeTest))
282 nodes.append(n);
283 return;
284 case PrecedingSiblingAxis:
285 if (context->nodeType() == Node::ATTRIBUTE_NODE ||
286 context->nodeType() == Node::XPATH_NAMESPACE_NODE)
287 return;
288
289 for (Node* n = context->previousSibling(); n; n = n->previousSibling())
290 if (nodeMatches(n, PrecedingSiblingAxis, m_nodeTest))
291 nodes.append(n);
292
293 nodes.markSorted(false);
294 return;
295 case FollowingAxis:
296 if (context->isAttributeNode()) {
297 Node* p = static_cast<Attr*>(context)->ownerElement();
298 while ((p = p->traverseNextNode()))
299 if (nodeMatches(p, FollowingAxis, m_nodeTest))
300 nodes.append(p);
301 } else {
302 for (Node* p = context; !isRootDomNode(p); p = p->parentNode()) {
303 for (Node* n = p->nextSibling(); n; n = n->nextSibling()) {
304 if (nodeMatches(n, FollowingAxis, m_nodeTest))
305 nodes.append(n);
306 for (Node* c = n->firstChild(); c; c = c->traverseNextNode(n))
307 if (nodeMatches(c, FollowingAxis, m_nodeTest))
308 nodes.append(c);
309 }
310 }
311 }
312 return;
313 case PrecedingAxis: {
314 if (context->isAttributeNode())
315 context = static_cast<Attr*>(context)->ownerElement();
316
317 Node* n = context;
318 while (Node* parent = n->parent()) {
319 for (n = n->traversePreviousNode(); n != parent; n = n->traversePreviousNode())
320 if (nodeMatches(n, PrecedingAxis, m_nodeTest))
321 nodes.append(n);
322 n = parent;
323 }
324 nodes.markSorted(false);
325 return;
326 }
327 case AttributeAxis: {
328 if (context->nodeType() != Node::ELEMENT_NODE)
329 return;
330
331 // Avoid lazily creating attribute nodes for attributes that we do not need anyway.
332 if (m_nodeTest.kind() == NodeTest::NameTest && m_nodeTest.data() != starAtom) {
333 RefPtr<Node> n = static_cast<Element*>(context)->getAttributeNodeNS(m_nodeTest.namespaceURI(), m_nodeTest.data());
334 if (n && n->namespaceURI() != "http://www.w3.org/2000/xmlns/") { // In XPath land, namespace nodes are not accessible on the attribute axis.
335 if (nodeMatches(n.get(), AttributeAxis, m_nodeTest)) // Still need to check merged predicates.
336 nodes.append(n.release());
337 }
338 return;
339 }
340
341 NamedNodeMap* attrs = context->attributes();
342 if (!attrs)
343 return;
344
345 for (unsigned i = 0; i < attrs->length(); ++i) {
346 RefPtr<Attr> attr = attrs->attributeItem(i)->createAttrIfNeeded(static_cast<Element*>(context));
347 if (nodeMatches(attr.get(), AttributeAxis, m_nodeTest))
348 nodes.append(attr.release());
349 }
350 return;
351 }
352 case NamespaceAxis:
353 // XPath namespace nodes are not implemented yet.
354 return;
355 case SelfAxis:
356 if (nodeMatches(context, SelfAxis, m_nodeTest))
357 nodes.append(context);
358 return;
359 case DescendantOrSelfAxis:
360 if (nodeMatches(context, DescendantOrSelfAxis, m_nodeTest))
361 nodes.append(context);
362 if (context->isAttributeNode()) // In XPath model, attribute nodes do not have children.
363 return;
364
365 for (Node* n = context->firstChild(); n; n = n->traverseNextNode(context))
366 if (nodeMatches(n, DescendantOrSelfAxis, m_nodeTest))
367 nodes.append(n);
368 return;
369 case AncestorOrSelfAxis: {
370 if (nodeMatches(context, AncestorOrSelfAxis, m_nodeTest))
371 nodes.append(context);
372 Node* n = context;
373 if (context->isAttributeNode()) {
374 n = static_cast<Attr*>(context)->ownerElement();
375 if (nodeMatches(n, AncestorOrSelfAxis, m_nodeTest))
376 nodes.append(n);
377 }
378 for (n = n->parentNode(); n; n = n->parentNode())
379 if (nodeMatches(n, AncestorOrSelfAxis, m_nodeTest))
380 nodes.append(n);
381
382 nodes.markSorted(false);
383 return;
384 }
385 }
386 ASSERT_NOT_REACHED();
387 }
388
389
390 }
391 }
392
393 #endif // ENABLE(XPATH)
394