1/*
2 * Copyright 2005 Frerich Raabe <raabe@kde.org>
3 * Copyright (C) 2006, 2013 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 "XPathPredicate.h"
30
31#include "XPathFunctions.h"
32#include "XPathUtil.h"
33#include <math.h>
34#include <wtf/MathExtras.h>
35
36namespace WebCore {
37namespace XPath {
38
39Number::Number(double value)
40 : m_value(value)
41{
42}
43
44Value Number::evaluate() const
45{
46 return m_value;
47}
48
49StringExpression::StringExpression(String&& value)
50 : m_value(WTFMove(value))
51{
52}
53
54Value StringExpression::evaluate() const
55{
56 return m_value;
57}
58
59Negative::Negative(std::unique_ptr<Expression> expression)
60{
61 addSubexpression(WTFMove(expression));
62}
63
64Value Negative::evaluate() const
65{
66 return -subexpression(0).evaluate().toNumber();
67}
68
69NumericOp::NumericOp(Opcode opcode, std::unique_ptr<Expression> lhs, std::unique_ptr<Expression> rhs)
70 : m_opcode(opcode)
71{
72 addSubexpression(WTFMove(lhs));
73 addSubexpression(WTFMove(rhs));
74}
75
76Value NumericOp::evaluate() const
77{
78 double leftVal = subexpression(0).evaluate().toNumber();
79 double rightVal = subexpression(1).evaluate().toNumber();
80
81 switch (m_opcode) {
82 case OP_Add:
83 return leftVal + rightVal;
84 case OP_Sub:
85 return leftVal - rightVal;
86 case OP_Mul:
87 return leftVal * rightVal;
88 case OP_Div:
89 return leftVal / rightVal;
90 case OP_Mod:
91 return fmod(leftVal, rightVal);
92 }
93
94 ASSERT_NOT_REACHED();
95 return 0.0;
96}
97
98EqTestOp::EqTestOp(Opcode opcode, std::unique_ptr<Expression> lhs, std::unique_ptr<Expression> rhs)
99 : m_opcode(opcode)
100{
101 addSubexpression(WTFMove(lhs));
102 addSubexpression(WTFMove(rhs));
103}
104
105bool EqTestOp::compare(const Value& lhs, const Value& rhs) const
106{
107 if (lhs.isNodeSet()) {
108 const NodeSet& lhsSet = lhs.toNodeSet();
109 if (rhs.isNodeSet()) {
110 // If both objects to be compared are node-sets, then the comparison will be true if and only if
111 // there is a node in the first node-set and a node in the second node-set such that the result of
112 // performing the comparison on the string-values of the two nodes is true.
113 const NodeSet& rhsSet = rhs.toNodeSet();
114 for (auto& lhs : lhsSet) {
115 for (auto& rhs : rhsSet) {
116 if (compare(stringValue(lhs.get()), stringValue(rhs.get())))
117 return true;
118 }
119 }
120 return false;
121 }
122 if (rhs.isNumber()) {
123 // If one object to be compared is a node-set and the other is a number, then the comparison will be true
124 // if and only if there is a node in the node-set such that the result of performing the comparison on the number
125 // to be compared and on the result of converting the string-value of that node to a number using the number function is true.
126 for (auto& lhs : lhsSet) {
127 if (compare(Value(stringValue(lhs.get())).toNumber(), rhs))
128 return true;
129 }
130 return false;
131 }
132 if (rhs.isString()) {
133 // If one object to be compared is a node-set and the other is a string, then the comparison will be true
134 // if and only if there is a node in the node-set such that the result of performing the comparison on
135 // the string-value of the node and the other string is true.
136 for (auto& lhs : lhsSet) {
137 if (compare(stringValue(lhs.get()), rhs))
138 return true;
139 }
140 return false;
141 }
142 if (rhs.isBoolean()) {
143 // If one object to be compared is a node-set and the other is a boolean, then the comparison will be true
144 // if and only if the result of performing the comparison on the boolean and on the result of converting
145 // the node-set to a boolean using the boolean function is true.
146 return compare(lhs.toBoolean(), rhs);
147 }
148 ASSERT_NOT_REACHED();
149 }
150 if (rhs.isNodeSet()) {
151 const NodeSet& rhsSet = rhs.toNodeSet();
152 if (lhs.isNumber()) {
153 for (auto& rhs : rhsSet) {
154 if (compare(lhs, Value(stringValue(rhs.get())).toNumber()))
155 return true;
156 }
157 return false;
158 }
159 if (lhs.isString()) {
160 for (auto& rhs : rhsSet) {
161 if (compare(lhs, stringValue(rhs.get())))
162 return true;
163 }
164 return false;
165 }
166 if (lhs.isBoolean())
167 return compare(lhs, rhs.toBoolean());
168 ASSERT_NOT_REACHED();
169 }
170
171 // Neither side is a NodeSet.
172 switch (m_opcode) {
173 case OP_EQ:
174 case OP_NE:
175 bool equal;
176 if (lhs.isBoolean() || rhs.isBoolean())
177 equal = lhs.toBoolean() == rhs.toBoolean();
178 else if (lhs.isNumber() || rhs.isNumber())
179 equal = lhs.toNumber() == rhs.toNumber();
180 else
181 equal = lhs.toString() == rhs.toString();
182
183 if (m_opcode == OP_EQ)
184 return equal;
185 return !equal;
186 case OP_GT:
187 return lhs.toNumber() > rhs.toNumber();
188 case OP_GE:
189 return lhs.toNumber() >= rhs.toNumber();
190 case OP_LT:
191 return lhs.toNumber() < rhs.toNumber();
192 case OP_LE:
193 return lhs.toNumber() <= rhs.toNumber();
194 }
195
196 ASSERT_NOT_REACHED();
197 return false;
198}
199
200Value EqTestOp::evaluate() const
201{
202 Value lhs(subexpression(0).evaluate());
203 Value rhs(subexpression(1).evaluate());
204 return compare(lhs, rhs);
205}
206
207LogicalOp::LogicalOp(Opcode opcode, std::unique_ptr<Expression> lhs, std::unique_ptr<Expression> rhs)
208 : m_opcode(opcode)
209{
210 addSubexpression(WTFMove(lhs));
211 addSubexpression(WTFMove(rhs));
212}
213
214inline bool LogicalOp::shortCircuitOn() const
215{
216 return m_opcode != OP_And;
217}
218
219Value LogicalOp::evaluate() const
220{
221 // This is not only an optimization, http://www.w3.org/TR/xpath
222 // dictates that we must do short-circuit evaluation
223 bool lhsBool = subexpression(0).evaluate().toBoolean();
224 if (lhsBool == shortCircuitOn())
225 return lhsBool;
226
227 return subexpression(1).evaluate().toBoolean();
228}
229
230Union::Union(std::unique_ptr<Expression> lhs, std::unique_ptr<Expression> rhs)
231{
232 addSubexpression(WTFMove(lhs));
233 addSubexpression(WTFMove(rhs));
234}
235
236Value Union::evaluate() const
237{
238 Value lhsResult = subexpression(0).evaluate();
239 Value rhs = subexpression(1).evaluate();
240
241 NodeSet& resultSet = lhsResult.modifiableNodeSet();
242 const NodeSet& rhsNodes = rhs.toNodeSet();
243
244 HashSet<Node*> nodes;
245 for (auto& result : resultSet)
246 nodes.add(result.get());
247
248 for (auto& node : rhsNodes) {
249 if (nodes.add(node.get()).isNewEntry)
250 resultSet.append(node.get());
251 }
252
253 // It would also be possible to perform a merge sort here to avoid making an unsorted result,
254 // but that would waste the time in cases when order is not important.
255 resultSet.markSorted(false);
256
257 return lhsResult;
258}
259
260bool evaluatePredicate(const Expression& expression)
261{
262 Value result(expression.evaluate());
263
264 // foo[3] means foo[position()=3]
265 if (result.isNumber())
266 return EqTestOp(EqTestOp::OP_EQ, Function::create("position"_s), std::make_unique<Number>(result.toNumber())).evaluate().toBoolean();
267
268 return result.toBoolean();
269}
270
271bool predicateIsContextPositionSensitive(const Expression& expression)
272{
273 return expression.isContextPositionSensitive() || expression.resultType() == Value::NumberValue;
274}
275
276}
277}
278