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(WTF::move(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(WTF::move(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(WTF::move(lhs));
73    addSubexpression(WTF::move(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(WTF::move(lhs));
102    addSubexpression(WTF::move(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 (unsigned lindex = 0; lindex < lhsSet.size(); ++lindex)
115                for (unsigned rindex = 0; rindex < rhsSet.size(); ++rindex)
116                    if (compare(stringValue(lhsSet[lindex]), stringValue(rhsSet[rindex])))
117                        return true;
118            return false;
119        }
120        if (rhs.isNumber()) {
121            // If one object to be compared is a node-set and the other is a number, then the comparison will be true
122            // if and only if there is a node in the node-set such that the result of performing the comparison on the number
123            // to be compared and on the result of converting the string-value of that node to a number using the number function is true.
124            for (unsigned lindex = 0; lindex < lhsSet.size(); ++lindex)
125                if (compare(Value(stringValue(lhsSet[lindex])).toNumber(), rhs))
126                    return true;
127            return false;
128        }
129        if (rhs.isString()) {
130            // If one object to be compared is a node-set and the other is a string, then the comparison will be true
131            // if and only if there is a node in the node-set such that the result of performing the comparison on
132            // the string-value of the node and the other string is true.
133            for (unsigned lindex = 0; lindex < lhsSet.size(); ++lindex)
134                if (compare(stringValue(lhsSet[lindex]), rhs))
135                    return true;
136            return false;
137        }
138        if (rhs.isBoolean()) {
139            // If one object to be compared is a node-set and the other is a boolean, then the comparison will be true
140            // if and only if the result of performing the comparison on the boolean and on the result of converting
141            // the node-set to a boolean using the boolean function is true.
142            return compare(lhs.toBoolean(), rhs);
143        }
144        ASSERT_NOT_REACHED();
145    }
146    if (rhs.isNodeSet()) {
147        const NodeSet& rhsSet = rhs.toNodeSet();
148        if (lhs.isNumber()) {
149            for (unsigned rindex = 0; rindex < rhsSet.size(); ++rindex)
150                if (compare(lhs, Value(stringValue(rhsSet[rindex])).toNumber()))
151                    return true;
152            return false;
153        }
154        if (lhs.isString()) {
155            for (unsigned rindex = 0; rindex < rhsSet.size(); ++rindex)
156                if (compare(lhs, stringValue(rhsSet[rindex])))
157                    return true;
158            return false;
159        }
160        if (lhs.isBoolean())
161            return compare(lhs, rhs.toBoolean());
162        ASSERT_NOT_REACHED();
163    }
164
165    // Neither side is a NodeSet.
166    switch (m_opcode) {
167        case OP_EQ:
168        case OP_NE:
169            bool equal;
170            if (lhs.isBoolean() || rhs.isBoolean())
171                equal = lhs.toBoolean() == rhs.toBoolean();
172            else if (lhs.isNumber() || rhs.isNumber())
173                equal = lhs.toNumber() == rhs.toNumber();
174            else
175                equal = lhs.toString() == rhs.toString();
176
177            if (m_opcode == OP_EQ)
178                return equal;
179            return !equal;
180        case OP_GT:
181            return lhs.toNumber() > rhs.toNumber();
182        case OP_GE:
183            return lhs.toNumber() >= rhs.toNumber();
184        case OP_LT:
185            return lhs.toNumber() < rhs.toNumber();
186        case OP_LE:
187            return lhs.toNumber() <= rhs.toNumber();
188    }
189
190    ASSERT_NOT_REACHED();
191    return false;
192}
193
194Value EqTestOp::evaluate() const
195{
196    Value lhs(subexpression(0).evaluate());
197    Value rhs(subexpression(1).evaluate());
198    return compare(lhs, rhs);
199}
200
201LogicalOp::LogicalOp(Opcode opcode, std::unique_ptr<Expression> lhs, std::unique_ptr<Expression> rhs)
202    : m_opcode(opcode)
203{
204    addSubexpression(WTF::move(lhs));
205    addSubexpression(WTF::move(rhs));
206}
207
208inline bool LogicalOp::shortCircuitOn() const
209{
210    return m_opcode != OP_And;
211}
212
213Value LogicalOp::evaluate() const
214{
215    // This is not only an optimization, http://www.w3.org/TR/xpath
216    // dictates that we must do short-circuit evaluation
217    bool lhsBool = subexpression(0).evaluate().toBoolean();
218    if (lhsBool == shortCircuitOn())
219        return lhsBool;
220
221    return subexpression(1).evaluate().toBoolean();
222}
223
224Union::Union(std::unique_ptr<Expression> lhs, std::unique_ptr<Expression> rhs)
225{
226    addSubexpression(WTF::move(lhs));
227    addSubexpression(WTF::move(rhs));
228}
229
230Value Union::evaluate() const
231{
232    Value lhsResult = subexpression(0).evaluate();
233    Value rhs = subexpression(1).evaluate();
234
235    NodeSet& resultSet = lhsResult.modifiableNodeSet();
236    const NodeSet& rhsNodes = rhs.toNodeSet();
237
238    HashSet<Node*> nodes;
239    for (size_t i = 0; i < resultSet.size(); ++i)
240        nodes.add(resultSet[i]);
241
242    for (size_t i = 0; i < rhsNodes.size(); ++i) {
243        Node* node = rhsNodes[i];
244        if (nodes.add(node).isNewEntry)
245            resultSet.append(node);
246    }
247
248    // It would also be possible to perform a merge sort here to avoid making an unsorted result,
249    // but that would waste the time in cases when order is not important.
250    resultSet.markSorted(false);
251
252    return lhsResult;
253}
254
255bool evaluatePredicate(const Expression& expression)
256{
257    Value result(expression.evaluate());
258
259    // foo[3] means foo[position()=3]
260    if (result.isNumber())
261        return EqTestOp(EqTestOp::OP_EQ, Function::create(ASCIILiteral("position")), std::make_unique<Number>(result.toNumber())).evaluate().toBoolean();
262
263    return result.toBoolean();
264}
265
266bool predicateIsContextPositionSensitive(const Expression& expression)
267{
268    return expression.isContextPositionSensitive() || expression.resultType() == Value::NumberValue;
269}
270
271}
272}
273