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