Reviewed by Darin.
[WebKit-https.git] / WebCore / xml / XPathPredicate.cpp
1 /*
2  * Copyright 2005 Frerich Raabe <raabe@kde.org>
3  * Copyright (C) 2006 Apple Computer, Inc.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 
9  * 1. Redistributions of source code must retain the above copyright
10  *    notice, this list of conditions and the following disclaimer.
11  * 2. Redistributions in binary form must reproduce the above copyright
12  *    notice, this list of conditions and the following disclaimer in the
13  *    documentation and/or other materials provided with the distribution.
14  * 
15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
16  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
17  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
18  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
19  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
20  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
24  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25  */
26
27 #include "config.h"
28
29 #if ENABLE(XPATH)
30
31 #include "XPathPredicate.h"
32
33 #include "Node.h"
34 #include "XPathFunctions.h"
35 #include "XPathValue.h"
36 #include <math.h>
37
38 #ifdef _MSC_VER // math functions missing from Microsoft Visual Studio standard C library
39 #define remainder(x, y) fmod((x), (y))
40 #endif
41
42 namespace WebCore {
43 namespace XPath {
44         
45 Number::Number(double value)
46     : m_value(value)
47 {
48 }
49
50 bool Number::isConstant() const
51 {
52     return true;
53 }
54
55 Value Number::doEvaluate() const
56 {
57     return m_value;
58 }
59
60 StringExpression::StringExpression(const String& value)
61     : m_value(value)
62 {
63 }
64
65 bool StringExpression::isConstant() const
66 {
67     return true;
68 }
69
70 Value StringExpression::doEvaluate() const
71 {
72     return m_value;
73 }
74
75 Value Negative::doEvaluate() const
76 {
77     Value p(subExpr(0)->evaluate());
78     if (!p.isNumber())
79         return Value();
80     return -p.toNumber();
81 }
82
83 NumericOp::NumericOp(Opcode opcode, Expression* lhs, Expression* rhs)
84     : m_opcode(opcode)
85 {
86     addSubExpression(lhs);
87     addSubExpression(rhs);
88 }
89
90 Value NumericOp::doEvaluate() const
91 {
92     Value lhs(subExpr(0)->evaluate());
93     Value rhs(subExpr(1)->evaluate());
94     
95     if (!lhs.isNumber() || !rhs.isNumber())
96         return Value();
97
98     double leftVal = lhs.toNumber(), rightVal = rhs.toNumber();
99
100     switch (m_opcode) {
101         case OP_Add:
102             return leftVal + rightVal;
103         case OP_Sub:
104             return leftVal - rightVal;
105         case OP_Mul:
106             return leftVal * rightVal;
107         case OP_Div:
108             return leftVal / rightVal;
109         case OP_Mod:
110             return remainder(leftVal, rightVal);
111     }
112     
113     return Value();
114 }
115
116 EqTestOp::EqTestOp(Opcode opcode, Expression* lhs, Expression* rhs)
117     : m_opcode(opcode)
118 {
119     addSubExpression(lhs);
120     addSubExpression(rhs);
121 }
122
123 bool EqTestOp::compare(const Value& lhs, const Value& rhs) const
124 {
125     if (lhs.isNodeVector()) {
126         const NodeVector& lhsVector = lhs.toNodeVector();
127         if (rhs.isNodeVector()) {
128             // If both objects to be compared are node-sets, then the comparison will be true if and only if
129             // there is a node in the first node-set and a node in the second node-set such that the result of
130             // performing the comparison on the string-values of the two nodes is true.
131             const NodeVector& rhsVector = rhs.toNodeVector();
132             for (unsigned lindex = 0; lindex < lhsVector.size(); ++lindex)
133                 for (unsigned rindex = 0; rindex < rhsVector.size(); ++rindex)
134                     if (compare(stringValue(lhsVector[lindex].get()), stringValue(rhsVector[rindex].get())))
135                         return true;
136             return false;
137         }
138         if (rhs.isNumber()) {
139             // If one object to be compared is a node-set and the other is a number, then the comparison will be true
140             // if and only if there is a node in the node-set such that the result of performing the comparison on the number
141             // to be compared and on the result of converting the string-value of that node to a number using the number function is true.
142             for (unsigned lindex = 0; lindex < lhsVector.size(); ++lindex)
143                 if (compare(Value(stringValue(lhsVector[lindex].get())).toNumber(), rhs))
144                     return true;
145             return false;
146         }
147         if (rhs.isString()) {
148             // If one object to be compared is a node-set and the other is a string, then the comparison will be true
149             // if and only if there is a node in the node-set such that the result of performing the comparison on
150             // the string-value of the node and the other string is true.
151             for (unsigned lindex = 0; lindex < lhsVector.size(); ++lindex)
152                 if (compare(stringValue(lhsVector[lindex].get()), rhs))
153                     return true;
154             return false;
155         }
156         if (rhs.isBoolean()) {
157             // If one object to be compared is a node-set and the other is a boolean, then the comparison will be true
158             // if and only if the result of performing the comparison on the boolean and on the result of converting
159             // the node-set to a boolean using the boolean function is true.
160             return compare(lhs.toBoolean(), rhs);
161         }
162         ASSERT(0);
163     }
164     if (rhs.isNodeVector()) {
165         const NodeVector& rhsVector = rhs.toNodeVector();
166         if (lhs.isNumber()) {
167             for (unsigned rindex = 0; rindex < rhsVector.size(); ++rindex)
168                 if (compare(lhs, Value(stringValue(rhsVector[rindex].get())).toNumber()))
169                     return true;
170             return false;
171         }
172         if (lhs.isString()) {
173             for (unsigned rindex = 0; rindex < rhsVector.size(); ++rindex)
174                 if (compare(lhs, stringValue(rhsVector[rindex].get())))
175                     return true;
176             return false;
177         }
178         if (lhs.isBoolean())
179             return compare(lhs, rhs.toBoolean());
180         ASSERT(0);
181     }
182     
183     // Neither side is a NodeVector.
184     switch (m_opcode) {
185         case OP_EQ:
186         case OP_NE:
187             bool equal;
188             if (lhs.isBoolean() || rhs.isBoolean())
189                 equal = lhs.toBoolean() == rhs.toBoolean();
190             else if (lhs.isNumber() || rhs.isNumber())
191                 equal = lhs.toNumber() == rhs.toNumber();
192             else
193                 equal = lhs.toString() == rhs.toString();
194
195             if (m_opcode == OP_EQ)
196                 return equal;
197             return !equal;
198         case OP_GT:
199             return lhs.toNumber() > rhs.toNumber();
200         case OP_GE:
201             return lhs.toNumber() >= rhs.toNumber();
202         case OP_LT:
203             return lhs.toNumber() < rhs.toNumber();
204         case OP_LE:
205             return lhs.toNumber() <= rhs.toNumber();
206     }
207     ASSERT(0);
208     return false;
209 }
210
211 Value EqTestOp::doEvaluate() const
212 {
213     Value lhs(subExpr(0)->evaluate());
214     Value rhs(subExpr(1)->evaluate());
215
216     return compare(lhs, rhs);
217 }
218
219 LogicalOp::LogicalOp(Opcode opcode, Expression* lhs, Expression* rhs)
220     : m_opcode(opcode)
221 {
222     addSubExpression(lhs);
223     addSubExpression(rhs);
224 }
225
226 bool LogicalOp::shortCircuitOn() const
227 {
228     if (m_opcode == OP_And)
229         return false; //false and foo
230
231     return true;  //true or bar
232 }
233
234 bool LogicalOp::isConstant() const
235 {
236     return subExpr(0)->isConstant() &&
237            subExpr(0)->evaluate().toBoolean() == shortCircuitOn();
238 }
239
240 Value LogicalOp::doEvaluate() const
241 {
242     Value lhs(subExpr(0)->evaluate());
243
244     // This is not only an optimization, http://www.w3.org/TR/xpath
245     // dictates that we must do short-circuit evaluation
246     bool lhsBool = lhs.toBoolean();
247     if (lhsBool == shortCircuitOn())
248         return lhsBool;
249
250     return subExpr(1)->evaluate().toBoolean();
251 }
252
253 Value Union::doEvaluate() const
254 {
255     // FIXME: This algorithm doesn't return nodes in document order, as it should.
256     Value lhs = subExpr(0)->evaluate();
257     Value rhs = subExpr(1)->evaluate();
258     if (!lhs.isNodeVector() || !rhs.isNodeVector())
259         return NodeVector();
260     
261     NodeVector lhsNodes = lhs.toNodeVector();
262     NodeVector rhsNodes = rhs.toNodeVector();
263     NodeVector result = lhsNodes;
264     
265     HashSet<Node*> nodes;
266     for (size_t i = 0; i < result.size(); ++i)
267         nodes.add(result[i].get());
268     
269     for (size_t i = 0; i < rhsNodes.size(); ++i) {
270         Node* node = rhsNodes[i].get();
271         if (nodes.add(node).second)
272             result.append(node);
273     }
274     
275     return result;
276 }
277
278 Predicate::Predicate(Expression* expr)
279     : m_expr(expr)
280 {
281 }
282
283 Predicate::~Predicate()
284 {
285     delete m_expr;
286 }
287
288 bool Predicate::evaluate() const
289 {
290     ASSERT(m_expr != 0);
291
292     Value result(m_expr->evaluate());
293
294     // foo[3] means foo[position()=3]
295     if (result.isNumber())
296         return EqTestOp(EqTestOp::OP_EQ, createFunction("position"), new Number(result.toNumber())).evaluate().toBoolean();
297
298     return result.toBoolean();
299 }
300
301 void Predicate::optimize()
302 {
303     m_expr->optimize();
304 }
305
306 }
307 }
308
309 #endif // ENABLE(XPATH)