2a6482fe98f879087415bd6703988972c7d3a6a7
[WebKit-https.git] / Source / WebCore / xml / XPathPredicate.cpp
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
41 namespace WebCore {
42 namespace XPath {
43         
44 Number::Number(double value)
45     : m_value(value)
46 {
47 }
48
49 Value Number::evaluate() const
50 {
51     return m_value;
52 }
53
54 StringExpression::StringExpression(const String& value)
55     : m_value(value)
56 {
57 }
58
59 Value StringExpression::evaluate() const
60 {
61     return m_value;
62 }
63
64 Value Negative::evaluate() const
65 {
66     Value p(subExpr(0)->evaluate());
67     return -p.toNumber();
68 }
69
70 NumericOp::NumericOp(Opcode opcode, Expression* lhs, Expression* rhs)
71     : m_opcode(opcode)
72 {
73     addSubExpression(lhs);
74     addSubExpression(rhs);
75 }
76
77 Value 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
101 EqTestOp::EqTestOp(Opcode opcode, Expression* lhs, Expression* rhs)
102     : m_opcode(opcode)
103 {
104     addSubExpression(lhs);
105     addSubExpression(rhs);
106 }
107
108 bool 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
196 Value EqTestOp::evaluate() const
197 {
198     Value lhs(subExpr(0)->evaluate());
199     Value rhs(subExpr(1)->evaluate());
200
201     return compare(lhs, rhs);
202 }
203
204 LogicalOp::LogicalOp(Opcode opcode, Expression* lhs, Expression* rhs)
205     : m_opcode(opcode)
206 {
207     addSubExpression(lhs);
208     addSubExpression(rhs);
209 }
210
211 bool 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
219 Value 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
232 Value 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
256 Predicate::Predicate(Expression* expr)
257     : m_expr(expr)
258 {
259 }
260
261 Predicate::~Predicate()
262 {
263     delete m_expr;
264 }
265
266 bool 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)