Always enable ENABLE(XPATH)
[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 #include "XPathPredicate.h"
30
31 #include "Node.h"
32 #include "XPathFunctions.h"
33 #include "XPathUtil.h"
34 #include "XPathValue.h"
35 #include <math.h>
36 #include <wtf/MathExtras.h>
37
38 namespace WebCore {
39 namespace XPath {
40         
41 Number::Number(double value)
42     : m_value(value)
43 {
44 }
45
46 Value Number::evaluate() const
47 {
48     return m_value;
49 }
50
51 StringExpression::StringExpression(const String& value)
52     : m_value(value)
53 {
54 }
55
56 Value StringExpression::evaluate() const
57 {
58     return m_value;
59 }
60
61 Value Negative::evaluate() const
62 {
63     Value p(subExpr(0)->evaluate());
64     return -p.toNumber();
65 }
66
67 NumericOp::NumericOp(Opcode opcode, Expression* lhs, Expression* rhs)
68     : m_opcode(opcode)
69 {
70     addSubExpression(lhs);
71     addSubExpression(rhs);
72 }
73
74 Value NumericOp::evaluate() const
75 {
76     Value lhs(subExpr(0)->evaluate());
77     Value rhs(subExpr(1)->evaluate());
78     
79     double leftVal = lhs.toNumber();
80     double rightVal = rhs.toNumber();
81
82     switch (m_opcode) {
83         case OP_Add:
84             return leftVal + rightVal;
85         case OP_Sub:
86             return leftVal - rightVal;
87         case OP_Mul:
88             return leftVal * rightVal;
89         case OP_Div:
90             return leftVal / rightVal;
91         case OP_Mod:
92             return fmod(leftVal, rightVal);
93     }
94     ASSERT_NOT_REACHED();
95     return 0.0;
96 }
97
98 EqTestOp::EqTestOp(Opcode opcode, Expression* lhs, Expression* rhs)
99     : m_opcode(opcode)
100 {
101     addSubExpression(lhs);
102     addSubExpression(rhs);
103 }
104
105 bool 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(0);
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(0);
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     ASSERT(0);
190     return false;
191 }
192
193 Value EqTestOp::evaluate() const
194 {
195     Value lhs(subExpr(0)->evaluate());
196     Value rhs(subExpr(1)->evaluate());
197
198     return compare(lhs, rhs);
199 }
200
201 LogicalOp::LogicalOp(Opcode opcode, Expression* lhs, Expression* rhs)
202     : m_opcode(opcode)
203 {
204     addSubExpression(lhs);
205     addSubExpression(rhs);
206 }
207
208 bool LogicalOp::shortCircuitOn() const
209 {
210     if (m_opcode == OP_And)
211         return false; //false and foo
212
213     return true;  //true or bar
214 }
215
216 Value LogicalOp::evaluate() const
217 {
218     Value lhs(subExpr(0)->evaluate());
219
220     // This is not only an optimization, http://www.w3.org/TR/xpath
221     // dictates that we must do short-circuit evaluation
222     bool lhsBool = lhs.toBoolean();
223     if (lhsBool == shortCircuitOn())
224         return lhsBool;
225
226     return subExpr(1)->evaluate().toBoolean();
227 }
228
229 Value Union::evaluate() const
230 {
231     Value lhsResult = subExpr(0)->evaluate();
232     Value rhs = subExpr(1)->evaluate();
233     
234     NodeSet& resultSet = lhsResult.modifiableNodeSet();
235     const NodeSet& rhsNodes = rhs.toNodeSet();
236     
237     HashSet<Node*> nodes;
238     for (size_t i = 0; i < resultSet.size(); ++i)
239         nodes.add(resultSet[i]);
240     
241     for (size_t i = 0; i < rhsNodes.size(); ++i) {
242         Node* node = rhsNodes[i];
243         if (nodes.add(node).second)
244             resultSet.append(node);
245     }
246
247     // It is also possible to use merge sort to avoid making the result unsorted;
248     // but this would waste the time in cases when order is not important.
249     resultSet.markSorted(false);
250     return lhsResult;
251 }
252
253 Predicate::Predicate(Expression* expr)
254     : m_expr(expr)
255 {
256 }
257
258 Predicate::~Predicate()
259 {
260     delete m_expr;
261 }
262
263 bool Predicate::evaluate() const
264 {
265     ASSERT(m_expr != 0);
266
267     Value result(m_expr->evaluate());
268
269     // foo[3] means foo[position()=3]
270     if (result.isNumber())
271         return EqTestOp(EqTestOp::OP_EQ, createFunction("position"), new Number(result.toNumber())).evaluate().toBoolean();
272
273     return result.toBoolean();
274 }
275
276 }
277 }