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