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