| OLD | NEW |
| 1 /* | 1 /* |
| 2 * Copyright 2005 Frerich Raabe <raabe@kde.org> | 2 * Copyright 2005 Frerich Raabe <raabe@kde.org> |
| 3 * Copyright (C) 2006 Apple Computer, Inc. | 3 * Copyright (C) 2006 Apple Computer, Inc. |
| 4 * Copyright (C) 2007 Alexey Proskuryakov <ap@webkit.org> | 4 * Copyright (C) 2007 Alexey Proskuryakov <ap@webkit.org> |
| 5 * | 5 * |
| 6 * Redistribution and use in source and binary forms, with or without | 6 * Redistribution and use in source and binary forms, with or without |
| 7 * modification, are permitted provided that the following conditions | 7 * modification, are permitted provided that the following conditions |
| 8 * are met: | 8 * are met: |
| 9 * | 9 * |
| 10 * 1. Redistributions of source code must retain the above copyright | 10 * 1. Redistributions of source code must retain the above copyright |
| (...skipping 10 matching lines...) Expand all Loading... |
| 21 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | 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 | 22 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| 23 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | 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 | 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. | 25 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| 26 */ | 26 */ |
| 27 | 27 |
| 28 #include "config.h" | 28 #include "config.h" |
| 29 #include "core/xml/XPathPredicate.h" | 29 #include "core/xml/XPathPredicate.h" |
| 30 | 30 |
| 31 #include <math.h> | |
| 32 #include "core/xml/XPathFunctions.h" | 31 #include "core/xml/XPathFunctions.h" |
| 33 #include "core/xml/XPathUtil.h" | 32 #include "core/xml/XPathUtil.h" |
| 34 #include "wtf/MathExtras.h" | 33 #include "wtf/MathExtras.h" |
| 34 #include <math.h> |
| 35 | 35 |
| 36 namespace WebCore { | 36 namespace WebCore { |
| 37 |
| 37 namespace XPath { | 38 namespace XPath { |
| 38 | 39 |
| 39 Number::Number(double value) | 40 Number::Number(double value) |
| 40 : m_value(value) | 41 : m_value(value) |
| 41 { | 42 { |
| 42 } | 43 } |
| 43 | 44 |
| 44 void Number::trace(Visitor* visitor) | 45 void Number::trace(Visitor* visitor) |
| 45 { | 46 { |
| 46 visitor->trace(m_value); | 47 visitor->trace(m_value); |
| (...skipping 36 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 83 | 84 |
| 84 Value NumericOp::evaluate() const | 85 Value NumericOp::evaluate() const |
| 85 { | 86 { |
| 86 Value lhs(subExpr(0)->evaluate()); | 87 Value lhs(subExpr(0)->evaluate()); |
| 87 Value rhs(subExpr(1)->evaluate()); | 88 Value rhs(subExpr(1)->evaluate()); |
| 88 | 89 |
| 89 double leftVal = lhs.toNumber(); | 90 double leftVal = lhs.toNumber(); |
| 90 double rightVal = rhs.toNumber(); | 91 double rightVal = rhs.toNumber(); |
| 91 | 92 |
| 92 switch (m_opcode) { | 93 switch (m_opcode) { |
| 93 case OP_Add: | 94 case OP_Add: |
| 94 return leftVal + rightVal; | 95 return leftVal + rightVal; |
| 95 case OP_Sub: | 96 case OP_Sub: |
| 96 return leftVal - rightVal; | 97 return leftVal - rightVal; |
| 97 case OP_Mul: | 98 case OP_Mul: |
| 98 return leftVal * rightVal; | 99 return leftVal * rightVal; |
| 99 case OP_Div: | 100 case OP_Div: |
| 100 return leftVal / rightVal; | 101 return leftVal / rightVal; |
| 101 case OP_Mod: | 102 case OP_Mod: |
| 102 return fmod(leftVal, rightVal); | 103 return fmod(leftVal, rightVal); |
| 103 } | 104 } |
| 104 ASSERT_NOT_REACHED(); | 105 ASSERT_NOT_REACHED(); |
| 105 return 0.0; | 106 return 0.0; |
| 106 } | 107 } |
| 107 | 108 |
| 108 EqTestOp::EqTestOp(Opcode opcode, PassOwnPtrWillBeRawPtr<Expression> lhs, PassOw
nPtrWillBeRawPtr<Expression> rhs) | 109 EqTestOp::EqTestOp(Opcode opcode, PassOwnPtrWillBeRawPtr<Expression> lhs, PassOw
nPtrWillBeRawPtr<Expression> rhs) |
| 109 : m_opcode(opcode) | 110 : m_opcode(opcode) |
| 110 { | 111 { |
| 111 addSubExpression(lhs); | 112 addSubExpression(lhs); |
| 112 addSubExpression(rhs); | 113 addSubExpression(rhs); |
| 113 } | 114 } |
| 114 | 115 |
| 115 bool EqTestOp::compare(const Value& lhs, const Value& rhs) const | 116 bool EqTestOp::compare(const Value& lhs, const Value& rhs) const |
| 116 { | 117 { |
| 117 if (lhs.isNodeSet()) { | 118 if (lhs.isNodeSet()) { |
| 118 const NodeSet& lhsSet = lhs.toNodeSet(); | 119 const NodeSet& lhsSet = lhs.toNodeSet(); |
| 119 if (rhs.isNodeSet()) { | 120 if (rhs.isNodeSet()) { |
| 120 // If both objects to be compared are node-sets, then the comparison
will be true if and only if | 121 // If both objects to be compared are node-sets, then the comparison |
| 121 // there is a node in the first node-set and a node in the second no
de-set such that the result of | 122 // will be true if and only if there is a node in the first node-set |
| 122 // performing the comparison on the string-values of the two nodes i
s true. | 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. |
| 123 const NodeSet& rhsSet = rhs.toNodeSet(); | 126 const NodeSet& rhsSet = rhs.toNodeSet(); |
| 124 for (unsigned lindex = 0; lindex < lhsSet.size(); ++lindex) | 127 for (unsigned lindex = 0; lindex < lhsSet.size(); ++lindex) { |
| 125 for (unsigned rindex = 0; rindex < rhsSet.size(); ++rindex) | 128 for (unsigned rindex = 0; rindex < rhsSet.size(); ++rindex) { |
| 126 if (compare(stringValue(lhsSet[lindex]), stringValue(rhsSet[
rindex]))) | 129 if (compare(stringValue(lhsSet[lindex]), stringValue(rhsSet[
rindex]))) |
| 127 return true; | 130 return true; |
| 131 } |
| 132 } |
| 128 return false; | 133 return false; |
| 129 } | 134 } |
| 130 if (rhs.isNumber()) { | 135 if (rhs.isNumber()) { |
| 131 // If one object to be compared is a node-set and the other is a num
ber, then the comparison will be true | 136 // If one object to be compared is a node-set and the other is a |
| 132 // if and only if there is a node in the node-set such that the resu
lt of performing the comparison on the number | 137 // number, then the comparison will be true if and only if there is |
| 133 // to be compared and on the result of converting the string-value o
f that node to a number using the number function is true. | 138 // a node in the node-set such that the result of performing the |
| 134 for (unsigned lindex = 0; lindex < lhsSet.size(); ++lindex) | 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) { |
| 135 if (compare(Value(stringValue(lhsSet[lindex])).toNumber(), rhs)) | 143 if (compare(Value(stringValue(lhsSet[lindex])).toNumber(), rhs)) |
| 136 return true; | 144 return true; |
| 145 } |
| 137 return false; | 146 return false; |
| 138 } | 147 } |
| 139 if (rhs.isString()) { | 148 if (rhs.isString()) { |
| 140 // If one object to be compared is a node-set and the other is a str
ing, then the comparison will be true | 149 // If one object to be compared is a node-set and the other is a |
| 141 // if and only if there is a node in the node-set such that the resu
lt of performing the comparison on | 150 // string, then the comparison will be true if and only if there is |
| 142 // the string-value of the node and the other string is true. | 151 // a node in the node-set such that the result of performing the |
| 143 for (unsigned lindex = 0; lindex < lhsSet.size(); ++lindex) | 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) { |
| 144 if (compare(stringValue(lhsSet[lindex]), rhs)) | 155 if (compare(stringValue(lhsSet[lindex]), rhs)) |
| 145 return true; | 156 return true; |
| 157 } |
| 146 return false; | 158 return false; |
| 147 } | 159 } |
| 148 if (rhs.isBoolean()) { | 160 if (rhs.isBoolean()) { |
| 149 // If one object to be compared is a node-set and the other is a boo
lean, then the comparison will be true | 161 // If one object to be compared is a node-set and the other is a |
| 150 // if and only if the result of performing the comparison on the boo
lean and on the result of converting | 162 // boolean, then the comparison will be true if and only if the |
| 151 // the node-set to a boolean using the boolean function is true. | 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. |
| 152 return compare(lhs.toBoolean(), rhs); | 166 return compare(lhs.toBoolean(), rhs); |
| 153 } | 167 } |
| 154 ASSERT(0); | 168 ASSERT(0); |
| 155 } | 169 } |
| 156 if (rhs.isNodeSet()) { | 170 if (rhs.isNodeSet()) { |
| 157 const NodeSet& rhsSet = rhs.toNodeSet(); | 171 const NodeSet& rhsSet = rhs.toNodeSet(); |
| 158 if (lhs.isNumber()) { | 172 if (lhs.isNumber()) { |
| 159 for (unsigned rindex = 0; rindex < rhsSet.size(); ++rindex) | 173 for (unsigned rindex = 0; rindex < rhsSet.size(); ++rindex) { |
| 160 if (compare(lhs, Value(stringValue(rhsSet[rindex])).toNumber())) | 174 if (compare(lhs, Value(stringValue(rhsSet[rindex])).toNumber())) |
| 161 return true; | 175 return true; |
| 176 } |
| 162 return false; | 177 return false; |
| 163 } | 178 } |
| 164 if (lhs.isString()) { | 179 if (lhs.isString()) { |
| 165 for (unsigned rindex = 0; rindex < rhsSet.size(); ++rindex) | 180 for (unsigned rindex = 0; rindex < rhsSet.size(); ++rindex) { |
| 166 if (compare(lhs, stringValue(rhsSet[rindex]))) | 181 if (compare(lhs, stringValue(rhsSet[rindex]))) |
| 167 return true; | 182 return true; |
| 183 } |
| 168 return false; | 184 return false; |
| 169 } | 185 } |
| 170 if (lhs.isBoolean()) | 186 if (lhs.isBoolean()) |
| 171 return compare(lhs, rhs.toBoolean()); | 187 return compare(lhs, rhs.toBoolean()); |
| 172 ASSERT(0); | 188 ASSERT(0); |
| 173 } | 189 } |
| 174 | 190 |
| 175 // Neither side is a NodeSet. | 191 // Neither side is a NodeSet. |
| 176 switch (m_opcode) { | 192 switch (m_opcode) { |
| 177 case OP_EQ: | 193 case OpcodeEqual: |
| 178 case OP_NE: | 194 case OpcodeNotEqual: |
| 179 bool equal; | 195 bool equal; |
| 180 if (lhs.isBoolean() || rhs.isBoolean()) | 196 if (lhs.isBoolean() || rhs.isBoolean()) |
| 181 equal = lhs.toBoolean() == rhs.toBoolean(); | 197 equal = lhs.toBoolean() == rhs.toBoolean(); |
| 182 else if (lhs.isNumber() || rhs.isNumber()) | 198 else if (lhs.isNumber() || rhs.isNumber()) |
| 183 equal = lhs.toNumber() == rhs.toNumber(); | 199 equal = lhs.toNumber() == rhs.toNumber(); |
| 184 else | 200 else |
| 185 equal = lhs.toString() == rhs.toString(); | 201 equal = lhs.toString() == rhs.toString(); |
| 186 | 202 |
| 187 if (m_opcode == OP_EQ) | 203 if (m_opcode == OpcodeEqual) |
| 188 return equal; | 204 return equal; |
| 189 return !equal; | 205 return !equal; |
| 190 case OP_GT: | 206 case OpcodeGreaterThan: |
| 191 return lhs.toNumber() > rhs.toNumber(); | 207 return lhs.toNumber() > rhs.toNumber(); |
| 192 case OP_GE: | 208 case OpcodeGreaterOrEqual: |
| 193 return lhs.toNumber() >= rhs.toNumber(); | 209 return lhs.toNumber() >= rhs.toNumber(); |
| 194 case OP_LT: | 210 case OpcodeLessThan: |
| 195 return lhs.toNumber() < rhs.toNumber(); | 211 return lhs.toNumber() < rhs.toNumber(); |
| 196 case OP_LE: | 212 case OpcodeLessOrEqual: |
| 197 return lhs.toNumber() <= rhs.toNumber(); | 213 return lhs.toNumber() <= rhs.toNumber(); |
| 198 } | 214 } |
| 199 ASSERT(0); | 215 ASSERT(0); |
| 200 return false; | 216 return false; |
| 201 } | 217 } |
| 202 | 218 |
| 203 Value EqTestOp::evaluate() const | 219 Value EqTestOp::evaluate() const |
| 204 { | 220 { |
| 205 Value lhs(subExpr(0)->evaluate()); | 221 Value lhs(subExpr(0)->evaluate()); |
| 206 Value rhs(subExpr(1)->evaluate()); | 222 Value rhs(subExpr(1)->evaluate()); |
| 207 | 223 |
| 208 return compare(lhs, rhs); | 224 return compare(lhs, rhs); |
| 209 } | 225 } |
| 210 | 226 |
| 211 LogicalOp::LogicalOp(Opcode opcode, PassOwnPtrWillBeRawPtr<Expression> lhs, Pass
OwnPtrWillBeRawPtr<Expression> rhs) | 227 LogicalOp::LogicalOp(Opcode opcode, PassOwnPtrWillBeRawPtr<Expression> lhs, Pass
OwnPtrWillBeRawPtr<Expression> rhs) |
| 212 : m_opcode(opcode) | 228 : m_opcode(opcode) |
| 213 { | 229 { |
| 214 addSubExpression(lhs); | 230 addSubExpression(lhs); |
| 215 addSubExpression(rhs); | 231 addSubExpression(rhs); |
| 216 } | 232 } |
| 217 | 233 |
| 218 bool LogicalOp::shortCircuitOn() const | 234 bool LogicalOp::shortCircuitOn() const |
| 219 { | 235 { |
| 220 if (m_opcode == OP_And) | 236 return m_opcode != OP_And; |
| 221 return false; //false and foo | |
| 222 | |
| 223 return true; //true or bar | |
| 224 } | 237 } |
| 225 | 238 |
| 226 Value LogicalOp::evaluate() const | 239 Value LogicalOp::evaluate() const |
| 227 { | 240 { |
| 228 Value lhs(subExpr(0)->evaluate()); | 241 Value lhs(subExpr(0)->evaluate()); |
| 229 | 242 |
| 230 // This is not only an optimization, http://www.w3.org/TR/xpath | 243 // This is not only an optimization, http://www.w3.org/TR/xpath |
| 231 // dictates that we must do short-circuit evaluation | 244 // dictates that we must do short-circuit evaluation |
| 232 bool lhsBool = lhs.toBoolean(); | 245 bool lhsBool = lhs.toBoolean(); |
| 233 if (lhsBool == shortCircuitOn()) | 246 if (lhsBool == shortCircuitOn()) |
| (...skipping 13 matching lines...) Expand all Loading... |
| 247 HashSet<Node*> nodes; | 260 HashSet<Node*> nodes; |
| 248 for (size_t i = 0; i < resultSet.size(); ++i) | 261 for (size_t i = 0; i < resultSet.size(); ++i) |
| 249 nodes.add(resultSet[i]); | 262 nodes.add(resultSet[i]); |
| 250 | 263 |
| 251 for (size_t i = 0; i < rhsNodes.size(); ++i) { | 264 for (size_t i = 0; i < rhsNodes.size(); ++i) { |
| 252 Node* node = rhsNodes[i]; | 265 Node* node = rhsNodes[i]; |
| 253 if (nodes.add(node).isNewEntry) | 266 if (nodes.add(node).isNewEntry) |
| 254 resultSet.append(node); | 267 resultSet.append(node); |
| 255 } | 268 } |
| 256 | 269 |
| 257 // It is also possible to use merge sort to avoid making the result unsorted
; | 270 // It is also possible to use merge sort to avoid making the result |
| 258 // but this would waste the time in cases when order is not important. | 271 // unsorted; but this would waste the time in cases when order is not |
| 272 // important. |
| 259 resultSet.markSorted(false); | 273 resultSet.markSorted(false); |
| 260 return lhsResult; | 274 return lhsResult; |
| 261 } | 275 } |
| 262 | 276 |
| 263 Predicate::Predicate(PassOwnPtrWillBeRawPtr<Expression> expr) | 277 Predicate::Predicate(PassOwnPtrWillBeRawPtr<Expression> expr) |
| 264 : m_expr(expr) | 278 : m_expr(expr) |
| 265 { | 279 { |
| 266 } | 280 } |
| 267 | 281 |
| 268 DEFINE_EMPTY_DESTRUCTOR_WILL_BE_REMOVED(Predicate); | 282 DEFINE_EMPTY_DESTRUCTOR_WILL_BE_REMOVED(Predicate); |
| 269 | 283 |
| 270 void Predicate::trace(Visitor* visitor) | 284 void Predicate::trace(Visitor* visitor) |
| 271 { | 285 { |
| 272 visitor->trace(m_expr); | 286 visitor->trace(m_expr); |
| 273 } | 287 } |
| 274 | 288 |
| 275 bool Predicate::evaluate() const | 289 bool Predicate::evaluate() const |
| 276 { | 290 { |
| 277 ASSERT(m_expr); | 291 ASSERT(m_expr); |
| 278 | 292 |
| 279 Value result(m_expr->evaluate()); | 293 Value result(m_expr->evaluate()); |
| 280 | 294 |
| 281 // foo[3] means foo[position()=3] | 295 // foo[3] means foo[position()=3] |
| 282 if (result.isNumber()) | 296 if (result.isNumber()) |
| 283 return EqTestOp(EqTestOp::OP_EQ, adoptPtrWillBeNoop(createFunction("posi
tion")), adoptPtrWillBeNoop(new Number(result.toNumber()))).evaluate().toBoolean
(); | 297 return EqTestOp(EqTestOp::OpcodeEqual, adoptPtrWillBeNoop(createFunction
("position")), adoptPtrWillBeNoop(new Number(result.toNumber()))).evaluate().toB
oolean(); |
| 284 | 298 |
| 285 return result.toBoolean(); | 299 return result.toBoolean(); |
| 286 } | 300 } |
| 287 | 301 |
| 288 } | 302 } |
| 289 } | 303 } |
| OLD | NEW |