1 /* 2 * Copyright 2005 Frerich Raabe <raabe (at) kde.org> 3 * Copyright (C) 2006 Apple Computer, Inc. 4 * Copyright (C) 2007 Alexey Proskuryakov <ap (at) 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 36 namespace blink { 37 38 namespace XPath { 39 40 Number::Number(double value) 41 : m_value(value) 42 { 43 } 44 45 void Number::trace(Visitor* visitor) 46 { 47 visitor->trace(m_value); 48 Expression::trace(visitor); 49 } 50 51 Value Number::evaluate(EvaluationContext&) const 52 { 53 return m_value; 54 } 55 56 StringExpression::StringExpression(const String& value) 57 : m_value(value) 58 { 59 } 60 61 void StringExpression::trace(Visitor* visitor) 62 { 63 visitor->trace(m_value); 64 Expression::trace(visitor); 65 } 66 67 Value StringExpression::evaluate(EvaluationContext&) const 68 { 69 return m_value; 70 } 71 72 Value Negative::evaluate(EvaluationContext& context) const 73 { 74 Value p(subExpr(0)->evaluate(context)); 75 return -p.toNumber(); 76 } 77 78 NumericOp::NumericOp(Opcode opcode, PassOwnPtrWillBeRawPtr<Expression> lhs, PassOwnPtrWillBeRawPtr<Expression> rhs) 79 : m_opcode(opcode) 80 { 81 addSubExpression(lhs); 82 addSubExpression(rhs); 83 } 84 85 Value 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 109 EqTestOp::EqTestOp(Opcode opcode, PassOwnPtrWillBeRawPtr<Expression> lhs, PassOwnPtrWillBeRawPtr<Expression> rhs) 110 : m_opcode(opcode) 111 { 112 addSubExpression(lhs); 113 addSubExpression(rhs); 114 } 115 116 bool 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 219 Value 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 227 LogicalOp::LogicalOp(Opcode opcode, PassOwnPtrWillBeRawPtr<Expression> lhs, PassOwnPtrWillBeRawPtr<Expression> rhs) 228 : m_opcode(opcode) 229 { 230 addSubExpression(lhs); 231 addSubExpression(rhs); 232 } 233 234 bool LogicalOp::shortCircuitOn() const 235 { 236 return m_opcode != OP_And; 237 } 238 239 Value 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 252 Value 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 277 Predicate::Predicate(PassOwnPtrWillBeRawPtr<Expression> expr) 278 : m_expr(expr) 279 { 280 } 281 282 DEFINE_EMPTY_DESTRUCTOR_WILL_BE_REMOVED(Predicate); 283 284 void Predicate::trace(Visitor* visitor) 285 { 286 visitor->trace(m_expr); 287 } 288 289 bool 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