Reviewed by Darin.
[WebKit-https.git] / WebCore / xml / XPathStep.cpp
1 /*
2  * Copyright 2005 Frerich Raabe <raabe@kde.org>
3  * Copyright (C) 2006 Apple Computer, Inc.
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 "Document.h"
34 #include "Element.h"
35 #include "NamedAttrMap.h"
36 #include "XPathNSResolver.h"
37 #include "XPathParser.h"
38 #include "XPathUtil.h"
39
40 namespace WebCore {
41 namespace XPath {
42
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
50 Step::~Step()
51 {
52     deleteAllValues(m_predicates);
53 }
54
55 void Step::evaluate(Node* context, NodeSet& nodes) const
56 {
57     nodesInAxis(context, nodes);
58     
59     EvaluationContext& evaluationContext = Expression::evaluationContext();
60     
61     for (unsigned i = 0; i < m_predicates.size(); i++) {
62         Predicate* predicate = m_predicates[i];
63
64         NodeSet newNodes;
65         if (!nodes.isSorted())
66             newNodes.markSorted(false);
67
68         for (unsigned j = 0; j < nodes.size(); j++) {
69             Node* node = nodes[j];
70
71             Expression::evaluationContext().node = node;
72             evaluationContext.size = nodes.size();
73             evaluationContext.position = j + 1;
74             if (predicate->evaluate())
75                 newNodes.append(node);
76         }
77
78         nodes.swap(newNodes);
79     }
80 }
81
82 void Step::nodesInAxis(Node* context, NodeSet& nodes) const
83 {
84     ASSERT(nodes.isEmpty());
85     switch (m_axis) {
86         case ChildAxis:
87             if (context->isAttributeNode()) // In XPath model, attribute nodes do not have children.
88                 return;
89
90             for (Node* n = context->firstChild(); n; n = n->nextSibling())
91                 if (nodeMatches(n))
92                     nodes.append(n);
93             return;
94         case DescendantAxis:
95             if (context->isAttributeNode()) // In XPath model, attribute nodes do not have children.
96                 return;
97
98             for (Node* n = context->firstChild(); n; n = n->traverseNextNode(context))
99                 if (nodeMatches(n))
100                     nodes.append(n);
101             return;
102         case ParentAxis:
103             if (context->isAttributeNode()) {
104                 Node* n = static_cast<Attr*>(context)->ownerElement();
105                 if (nodeMatches(n))
106                     nodes.append(n);
107             } else {
108                 Node* n = context->parentNode();
109                 if (n && nodeMatches(n))
110                     nodes.append(n);
111             }
112             return;
113         case AncestorAxis: {
114             Node* n = context;
115             if (context->isAttributeNode()) {
116                 n = static_cast<Attr*>(context)->ownerElement();
117                 if (nodeMatches(n))
118                     nodes.append(n);
119             }
120             for (n = n->parentNode(); n; n = n->parentNode())
121                 if (nodeMatches(n))
122                     nodes.append(n);
123             nodes.markSorted(false);
124             return;
125         }
126         case FollowingSiblingAxis:
127             if (context->nodeType() == Node::ATTRIBUTE_NODE ||
128                  context->nodeType() == Node::XPATH_NAMESPACE_NODE) 
129                 return;
130             
131             for (Node* n = context->nextSibling(); n; n = n->nextSibling())
132                 if (nodeMatches(n))
133                     nodes.append(n);
134             return;
135         case PrecedingSiblingAxis:
136             if (context->nodeType() == Node::ATTRIBUTE_NODE ||
137                  context->nodeType() == Node::XPATH_NAMESPACE_NODE)
138                 return;
139             
140             for (Node* n = context->previousSibling(); n; n = n->previousSibling())
141                 if (nodeMatches(n))
142                     nodes.append(n);
143
144             nodes.markSorted(false);
145             return;
146         case FollowingAxis:
147             if (context->isAttributeNode()) {
148                 Node* p = static_cast<Attr*>(context)->ownerElement();
149                 while ((p = p->traverseNextNode()))
150                     if (nodeMatches(p))
151                         nodes.append(p);
152             } else {
153                 for (Node* p = context; !isRootDomNode(p); p = p->parentNode()) {
154                     for (Node* n = p->nextSibling(); n; n = n->nextSibling()) {
155                         if (nodeMatches(n))
156                             nodes.append(n);
157                         for (Node* c = n->firstChild(); c; c = c->traverseNextNode(n))
158                             if (nodeMatches(c))
159                                 nodes.append(c);
160                     }
161                 }
162             }
163             return;
164         case PrecedingAxis:
165             if (context->isAttributeNode())
166                 context = static_cast<Attr*>(context)->ownerElement();
167
168             Node* n = context;
169             while (Node* parent = n->parent()) {
170                 for (n = n->traversePreviousNode(); n != parent; n = n->traversePreviousNode())
171                     if (nodeMatches(n))
172                         nodes.append(n);
173                 n = parent;
174             }
175             nodes.markSorted(false);
176             return;
177         case AttributeAxis: {
178             if (context->nodeType() != Node::ELEMENT_NODE)
179                 return;
180
181             // Avoid lazily creating attribute nodes for attributes that we do not need anyway.
182             if (m_nodeTest.kind() == NodeTest::NameTest && m_nodeTest.data() != "*") {
183                 RefPtr<Node> n = static_cast<Element*>(context)->getAttributeNodeNS(m_nodeTest.namespaceURI(), m_nodeTest.data());
184                 if (n && n->namespaceURI() != "http://www.w3.org/2000/xmlns/") // In XPath land, namespace nodes are not accessible on the attribute axis.
185                     nodes.append(n.release());
186                 return;
187             }
188             
189             NamedAttrMap* attrs = context->attributes();
190             if (!attrs)
191                 return;
192
193             for (unsigned long i = 0; i < attrs->length(); ++i) {
194                 RefPtr<Node> n = attrs->item(i);
195                 if (nodeMatches(n.get()))
196                     nodes.append(n.release());
197             }
198             return;
199         }
200         case NamespaceAxis:
201             // XPath namespace nodes are not implemented yet.
202             return;
203         case SelfAxis:
204             if (nodeMatches(context))
205                 nodes.append(context);
206             return;
207         case DescendantOrSelfAxis:
208             if (nodeMatches(context))
209                 nodes.append(context);
210             if (context->isAttributeNode()) // In XPath model, attribute nodes do not have children.
211                 return;
212
213             for (Node* n = context->firstChild(); n; n = n->traverseNextNode(context))
214             if (nodeMatches(n))
215                 nodes.append(n);
216             return;
217         case AncestorOrSelfAxis: {
218             if (nodeMatches(context))
219                 nodes.append(context);
220             Node* n = context;
221             if (context->isAttributeNode()) {
222                 n = static_cast<Attr*>(context)->ownerElement();
223                 if (nodeMatches(n))
224                     nodes.append(n);
225             }
226             for (n = n->parentNode(); n; n = n->parentNode())
227                 if (nodeMatches(n))
228                     nodes.append(n);
229
230             nodes.markSorted(false);
231             return;
232         }
233     }
234     ASSERT_NOT_REACHED();
235 }
236
237
238 bool Step::nodeMatches(Node* node) const
239 {
240     switch (m_nodeTest.kind()) {
241         case NodeTest::TextNodeTest:
242             return node->nodeType() == Node::TEXT_NODE || node->nodeType() == Node::CDATA_SECTION_NODE;
243         case NodeTest::CommentNodeTest:
244             return node->nodeType() == Node::COMMENT_NODE;
245         case NodeTest::ProcessingInstructionNodeTest: {
246             const String& name = m_nodeTest.data();
247             return node->nodeType() == Node::PROCESSING_INSTRUCTION_NODE && (name.isEmpty() || node->nodeName() == name);
248         }
249         case NodeTest::ElementNodeTest:
250             return node->isElementNode();
251         case NodeTest::AnyNodeTest:
252             return true;
253         case NodeTest::NameTest: {
254             const String& name = m_nodeTest.data();
255             const String& namespaceURI = m_nodeTest.namespaceURI();
256
257             if (m_axis == AttributeAxis) {
258                 ASSERT(node->isAttributeNode());
259
260                 // In XPath land, namespace nodes are not accessible on the attribute axis.
261                 if (node->namespaceURI() == "http://www.w3.org/2000/xmlns/")
262                     return false;
263
264                 if (name == "*")
265                     return namespaceURI.isEmpty() || node->namespaceURI() == namespaceURI;
266
267                 return node->localName() == name && node->namespaceURI() == namespaceURI;
268             }
269
270             if (m_axis == NamespaceAxis) {
271                 // Node test on the namespace axis is not implemented yet
272                 return false;
273             }
274             
275             if (name == "*")
276                 return node->nodeType() == primaryNodeType(m_axis) && (namespaceURI.isEmpty() || namespaceURI == node->namespaceURI());
277
278             // We use tagQName here because we don't want the element name in uppercase 
279             // like we get with HTML elements.
280             // Paths without namespaces should match HTML elements in HTML documents despite those having an XHTML namespace.
281             return node->nodeType() == Node::ELEMENT_NODE
282                     && static_cast<Element*>(node)->tagQName().localName() == name
283                     && ((node->isHTMLElement() && node->document()->isHTMLDocument() && namespaceURI.isNull()) || namespaceURI == node->namespaceURI());
284         }
285     }
286     ASSERT_NOT_REACHED();
287     return false;
288 }
289
290 Node::NodeType Step::primaryNodeType(Axis axis) const
291 {
292     switch (axis) {
293         case AttributeAxis:
294             return Node::ATTRIBUTE_NODE;
295         case NamespaceAxis:
296             return Node::XPATH_NAMESPACE_NODE;
297         default:
298             return Node::ELEMENT_NODE;
299     }
300 }
301
302 }
303 }
304
305 #endif // ENABLE(XPATH)