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>
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
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.
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.
29 #include "core/xml/XPathStep.h"
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"
42 Step::Step(Axis axis, const NodeTest& nodeTest)
44 , m_nodeTest(adoptPtrWillBeNoop(new NodeTest(nodeTest)))
48 Step::Step(Axis axis, const NodeTest& nodeTest, WillBeHeapVector<OwnPtrWillBeMember<Predicate> >& predicates)
50 , m_nodeTest(adoptPtrWillBeNoop(new NodeTest(nodeTest)))
52 m_predicates.swap(predicates);
59 void Step::trace(Visitor* visitor)
61 visitor->trace(m_nodeTest);
62 visitor->trace(m_predicates);
63 ParseNode::trace(visitor);
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());
81 remainingPredicates.append(predicate.release());
84 swap(remainingPredicates, m_predicates);
87 void optimizeStepPair(Step* first, Step* second, bool& dropSecondStep)
89 dropSecondStep = false;
91 if (first->m_axis == Step::DescendantOrSelfAxis
92 && first->nodeTest().kind() == Step::NodeTest::AnyNodeTest
93 && !first->m_predicates.size()
94 && !first->nodeTest().mergedPredicates().size()) {
96 ASSERT(first->nodeTest().data().isEmpty());
97 ASSERT(first->nodeTest().namespaceURI().isEmpty());
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);
107 dropSecondStep = true;
112 bool Step::predicatesAreContextListInsensitive() const
114 for (size_t i = 0; i < m_predicates.size(); ++i) {
115 Predicate* predicate = m_predicates[i].get();
116 if (predicate->isContextPositionSensitive() || predicate->isContextSizeSensitive())
120 for (size_t i = 0; i < nodeTest().mergedPredicates().size(); ++i) {
121 Predicate* predicate = nodeTest().mergedPredicates()[i].get();
122 if (predicate->isContextPositionSensitive() || predicate->isContextSizeSensitive())
129 void Step::evaluate(EvaluationContext& evaluationContext, Node* context, NodeSet& nodes) const
131 evaluationContext.position = 0;
133 nodesInAxis(evaluationContext, context, nodes);
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();
139 OwnPtrWillBeRawPtr<NodeSet> newNodes(NodeSet::create());
140 if (!nodes.isSorted())
141 newNodes->markSorted(false);
143 for (unsigned j = 0; j < nodes.size(); j++) {
144 Node* node = nodes[j];
146 evaluationContext.node = node;
147 evaluationContext.size = nodes.size();
148 evaluationContext.position = j + 1;
149 if (predicate->evaluate(evaluationContext))
150 newNodes->append(node);
153 nodes.swap(*newNodes);
158 static inline Node::NodeType primaryNodeType(Step::Axis axis)
161 case Step::AttributeAxis:
162 return Node::ATTRIBUTE_NODE;
164 return Node::ELEMENT_NODE;
169 // Evaluate NodeTest without considering merged predicates.
170 static inline bool nodeMatchesBasicTest(Node* node, Step::Axis axis, const Step::NodeTest& nodeTest)
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;
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);
183 case Step::NodeTest::AnyNodeTest:
185 case Step::NodeTest::NameTest: {
186 const AtomicString& name = nodeTest.data();
187 const AtomicString& namespaceURI = nodeTest.namespaceURI();
189 if (axis == Step::AttributeAxis) {
190 ASSERT(node->isAttributeNode());
192 // In XPath land, namespace nodes are not accessible on the
194 if (node->namespaceURI() == XMLNSNames::xmlnsNamespaceURI)
197 if (name == starAtom)
198 return namespaceURI.isEmpty() || node->namespaceURI() == namespaceURI;
200 return node->localName() == name && node->namespaceURI() == namespaceURI;
203 // Node test on the namespace axis is not implemented yet, the caller
204 // has a check for it.
205 ASSERT(axis != Step::NamespaceAxis);
207 // For other axes, the principal node type is element.
208 ASSERT(primaryNodeType(axis) == Node::ELEMENT_NODE);
209 if (!node->isElementNode())
211 Element& element = toElement(*node);
213 if (name == starAtom)
214 return namespaceURI.isEmpty() || namespaceURI == element.namespaceURI();
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());
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();
227 return element.hasLocalName(name) && namespaceURI == element.namespaceURI();
230 ASSERT_NOT_REACHED();
234 static inline bool nodeMatches(EvaluationContext& evaluationContext, Node* node, Step::Axis axis, const Step::NodeTest& nodeTest)
236 if (!nodeMatchesBasicTest(node, axis, nodeTest))
239 // Only the first merged predicate may depend on position.
240 ++evaluationContext.position;
242 const WillBeHeapVector<OwnPtrWillBeMember<Predicate> >& mergedPredicates = nodeTest.mergedPredicates();
243 for (unsigned i = 0; i < mergedPredicates.size(); i++) {
244 Predicate* predicate = mergedPredicates[i].get();
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))
256 // Result nodes are ordered in axis order. Node test (including merged
257 // predicates) is applied.
258 void Step::nodesInAxis(EvaluationContext& evaluationContext, Node* context, NodeSet& nodes) const
260 ASSERT(nodes.isEmpty());
263 // In XPath model, attribute nodes do not have children.
264 if (context->isAttributeNode())
267 for (Node* n = context->firstChild(); n; n = n->nextSibling()) {
268 if (nodeMatches(evaluationContext, n, ChildAxis, nodeTest()))
274 // In XPath model, attribute nodes do not have children.
275 if (context->isAttributeNode())
278 for (Node& n : NodeTraversal::descendantsOf(*context)) {
279 if (nodeMatches(evaluationContext, &n, DescendantAxis, nodeTest()))
285 if (context->isAttributeNode()) {
286 Element* n = toAttr(context)->ownerElement();
287 if (nodeMatches(evaluationContext, n, ParentAxis, nodeTest()))
290 ContainerNode* n = context->parentNode();
291 if (n && nodeMatches(evaluationContext, n, ParentAxis, nodeTest()))
298 if (context->isAttributeNode()) {
299 n = toAttr(context)->ownerElement();
300 if (nodeMatches(evaluationContext, n, AncestorAxis, nodeTest()))
303 for (n = n->parentNode(); n; n = n->parentNode()) {
304 if (nodeMatches(evaluationContext, n, AncestorAxis, nodeTest()))
307 nodes.markSorted(false);
311 case FollowingSiblingAxis:
312 if (context->nodeType() == Node::ATTRIBUTE_NODE)
315 for (Node* n = context->nextSibling(); n; n = n->nextSibling()) {
316 if (nodeMatches(evaluationContext, n, FollowingSiblingAxis, nodeTest()))
321 case PrecedingSiblingAxis:
322 if (context->nodeType() == Node::ATTRIBUTE_NODE)
325 for (Node* n = context->previousSibling(); n; n = n->previousSibling()) {
326 if (nodeMatches(evaluationContext, n, PrecedingSiblingAxis, nodeTest()))
329 nodes.markSorted(false);
333 if (context->isAttributeNode()) {
334 for (Node& p : NodeTraversal::startsAfter(*toAttr(context)->ownerElement())) {
335 if (nodeMatches(evaluationContext, &p, FollowingAxis, nodeTest()))
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()))
343 for (Node& c : NodeTraversal::descendantsOf(*n)) {
344 if (nodeMatches(evaluationContext, &c, FollowingAxis, nodeTest()))
352 case PrecedingAxis: {
353 if (context->isAttributeNode())
354 context = toAttr(context)->ownerElement();
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()))
364 nodes.markSorted(false);
368 case AttributeAxis: {
369 if (!context->isElementNode())
372 Element* contextElement = toElement(context);
373 // Avoid lazily creating attribute nodes for attributes that we do not
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());
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());
397 // XPath namespace nodes are not implemented.
401 if (nodeMatches(evaluationContext, context, SelfAxis, nodeTest()))
402 nodes.append(context);
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())
412 for (Node& n : NodeTraversal::descendantsOf(*context)) {
413 if (nodeMatches(evaluationContext, &n, DescendantOrSelfAxis, nodeTest()))
418 case AncestorOrSelfAxis: {
419 if (nodeMatches(evaluationContext, context, AncestorOrSelfAxis, nodeTest()))
420 nodes.append(context);
422 if (context->isAttributeNode()) {
423 n = toAttr(context)->ownerElement();
424 if (nodeMatches(evaluationContext, n, AncestorOrSelfAxis, nodeTest()))
427 for (n = n->parentNode(); n; n = n->parentNode()) {
428 if (nodeMatches(evaluationContext, n, AncestorOrSelfAxis, nodeTest()))
431 nodes.markSorted(false);
435 ASSERT_NOT_REACHED();