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