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