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 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) 283