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
39namespace blink {
40namespace XPath {
41
42Step::Step(Axis axis, const NodeTest& nodeTest)
43    : m_axis(axis)
44    , m_nodeTest(adoptPtrWillBeNoop(new NodeTest(nodeTest)))
45{
46}
47
48Step::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
55Step::~Step()
56{
57}
58
59void Step::trace(Visitor* visitor)
60{
61    visitor->trace(m_nodeTest);
62    visitor->trace(m_predicates);
63    ParseNode::trace(visitor);
64}
65
66void 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
87void 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
112bool 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
129void 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)
158static 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.
170static 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
234static 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.
258void 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