1/*
2 * Copyright (C) 2005 Frerich Raabe <raabe@kde.org>
3 * Copyright (C) 2006, 2009 Apple 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 "core/xml/XPathPath.h"
30
31#include "core/dom/Document.h"
32#include "core/dom/NodeTraversal.h"
33#include "core/xml/XPathPredicate.h"
34#include "core/xml/XPathStep.h"
35#include "core/xml/XPathValue.h"
36
37namespace blink {
38namespace XPath {
39
40Filter::Filter(PassOwnPtrWillBeRawPtr<Expression> expr, WillBeHeapVector<OwnPtrWillBeMember<Predicate> >& predicates)
41    : m_expr(expr)
42{
43    m_predicates.swap(predicates);
44    setIsContextNodeSensitive(m_expr->isContextNodeSensitive());
45    setIsContextPositionSensitive(m_expr->isContextPositionSensitive());
46    setIsContextSizeSensitive(m_expr->isContextSizeSensitive());
47}
48
49Filter::~Filter()
50{
51}
52
53void Filter::trace(Visitor* visitor)
54{
55    visitor->trace(m_expr);
56    visitor->trace(m_predicates);
57    Expression::trace(visitor);
58}
59
60Value Filter::evaluate(EvaluationContext& evaluationContext) const
61{
62    Value v = m_expr->evaluate(evaluationContext);
63
64    NodeSet& nodes = v.modifiableNodeSet(evaluationContext);
65    nodes.sort();
66
67    for (unsigned i = 0; i < m_predicates.size(); i++) {
68        OwnPtrWillBeRawPtr<NodeSet> newNodes(NodeSet::create());
69        evaluationContext.size = nodes.size();
70        evaluationContext.position = 0;
71
72        for (unsigned j = 0; j < nodes.size(); j++) {
73            Node* node = nodes[j];
74
75            evaluationContext.node = node;
76            ++evaluationContext.position;
77
78            if (m_predicates[i]->evaluate(evaluationContext))
79                newNodes->append(node);
80        }
81        nodes.swap(*newNodes);
82    }
83
84    return v;
85}
86
87LocationPath::LocationPath()
88    : m_absolute(false)
89{
90    setIsContextNodeSensitive(true);
91}
92
93LocationPath::~LocationPath()
94{
95#if !ENABLE(OILPAN)
96    deleteAllValues(m_steps);
97#endif
98}
99
100void LocationPath::trace(Visitor* visitor)
101{
102#if ENABLE(OILPAN)
103    visitor->trace(m_steps);
104#endif
105    Expression::trace(visitor);
106}
107
108Value LocationPath::evaluate(EvaluationContext& evaluationContext) const
109{
110    EvaluationContext clonedContext = evaluationContext;
111    // http://www.w3.org/TR/xpath/
112    // Section 2, Location Paths:
113    // "/ selects the document root (which is always the parent of the document element)"
114    // "A / by itself selects the root node of the document containing the context node."
115    // In the case of a tree that is detached from the document, we violate
116    // the spec and treat / as the root node of the detached tree.
117    // This is for compatibility with Firefox, and also seems like a more
118    // logical treatment of where you would expect the "root" to be.
119    Node* context = evaluationContext.node.get();
120    if (m_absolute && context->nodeType() != Node::DOCUMENT_NODE)  {
121        if (context->inDocument())
122            context = context->ownerDocument();
123        else
124            context = &NodeTraversal::highestAncestorOrSelf(*context);
125    }
126
127    OwnPtrWillBeRawPtr<NodeSet> nodes(NodeSet::create());
128    nodes->append(context);
129    evaluate(clonedContext, *nodes);
130
131    return Value(nodes.release(), Value::adopt);
132}
133
134void LocationPath::evaluate(EvaluationContext& context, NodeSet& nodes) const
135{
136    bool resultIsSorted = nodes.isSorted();
137
138    for (unsigned i = 0; i < m_steps.size(); i++) {
139        Step* step = m_steps[i];
140        OwnPtrWillBeRawPtr<NodeSet> newNodes(NodeSet::create());
141        WillBeHeapHashSet<RawPtrWillBeMember<Node> > newNodesSet;
142
143        bool needToCheckForDuplicateNodes = !nodes.subtreesAreDisjoint() || (step->axis() != Step::ChildAxis && step->axis() != Step::SelfAxis
144            && step->axis() != Step::DescendantAxis && step->axis() != Step::DescendantOrSelfAxis && step->axis() != Step::AttributeAxis);
145
146        if (needToCheckForDuplicateNodes)
147            resultIsSorted = false;
148
149        // This is a simplified check that can be improved to handle more cases.
150        if (nodes.subtreesAreDisjoint() && (step->axis() == Step::ChildAxis || step->axis() == Step::SelfAxis))
151            newNodes->markSubtreesDisjoint(true);
152
153        for (unsigned j = 0; j < nodes.size(); j++) {
154            OwnPtrWillBeRawPtr<NodeSet> matches(NodeSet::create());
155            step->evaluate(context, nodes[j], *matches);
156
157            if (!matches->isSorted())
158                resultIsSorted = false;
159
160            for (size_t nodeIndex = 0; nodeIndex < matches->size(); ++nodeIndex) {
161                Node* node = (*matches)[nodeIndex];
162                if (!needToCheckForDuplicateNodes || newNodesSet.add(node).isNewEntry)
163                    newNodes->append(node);
164            }
165        }
166
167        nodes.swap(*newNodes);
168    }
169
170    nodes.markSorted(resultIsSorted);
171}
172
173void LocationPath::appendStep(Step* step)
174{
175    unsigned stepCount = m_steps.size();
176    if (stepCount) {
177        bool dropSecondStep;
178        optimizeStepPair(m_steps[stepCount - 1], step, dropSecondStep);
179        if (dropSecondStep) {
180#if !ENABLE(OILPAN)
181            delete step;
182#endif
183            return;
184        }
185    }
186    step->optimize();
187    m_steps.append(step);
188}
189
190void LocationPath::insertFirstStep(Step* step)
191{
192    if (m_steps.size()) {
193        bool dropSecondStep;
194        optimizeStepPair(step, m_steps[0], dropSecondStep);
195        if (dropSecondStep) {
196#if !ENABLE(OILPAN)
197            delete m_steps[0];
198#endif
199            m_steps[0] = step;
200            return;
201        }
202    }
203    step->optimize();
204    m_steps.insert(0, step);
205}
206
207Path::Path(Expression* filter, LocationPath* path)
208    : m_filter(adoptPtrWillBeNoop(filter))
209    , m_path(adoptPtrWillBeNoop(path))
210{
211    setIsContextNodeSensitive(filter->isContextNodeSensitive());
212    setIsContextPositionSensitive(filter->isContextPositionSensitive());
213    setIsContextSizeSensitive(filter->isContextSizeSensitive());
214}
215
216Path::~Path()
217{
218}
219
220void Path::trace(Visitor* visitor)
221{
222    visitor->trace(m_filter);
223    visitor->trace(m_path);
224    Expression::trace(visitor);
225}
226
227Value Path::evaluate(EvaluationContext& context) const
228{
229    Value v = m_filter->evaluate(context);
230
231    NodeSet& nodes = v.modifiableNodeSet(context);
232    m_path->evaluate(context, nodes);
233
234    return v;
235}
236
237}
238}
239