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 <math.h> 32 #include "core/xml/XPathFunctions.h" 33 #include "core/xml/XPathUtil.h" 34 #include "core/xml/XPathValue.h" 35 #include <wtf/MathExtras.h> 36 37 namespace WebCore { 38 namespace XPath { 39 40 Number::Number(double value) 41 : m_value(value) 42 { 43 } 44 45 Value Number::evaluate() const 46 { 47 return m_value; 48 } 49 50 StringExpression::StringExpression(const String& value) 51 : m_value(value) 52 { 53 } 54 55 Value StringExpression::evaluate() const 56 { 57 return m_value; 58 } 59 60 Value Negative::evaluate() const 61 { 62 Value p(subExpr(0)->evaluate()); 63 return -p.toNumber(); 64 } 65 66 NumericOp::NumericOp(Opcode opcode, Expression* lhs, Expression* rhs) 67 : m_opcode(opcode) 68 { 69 addSubExpression(lhs); 70 addSubExpression(rhs); 71 } 72 73 Value NumericOp::evaluate() const 74 { 75 Value lhs(subExpr(0)->evaluate()); 76 Value rhs(subExpr(1)->evaluate()); 77 78 double leftVal = lhs.toNumber(); 79 double rightVal = rhs.toNumber(); 80 81 switch (m_opcode) { 82 case OP_Add: 83 return leftVal + rightVal; 84 case OP_Sub: 85 return leftVal - rightVal; 86 case OP_Mul: 87 return leftVal * rightVal; 88 case OP_Div: 89 return leftVal / rightVal; 90 case OP_Mod: 91 return fmod(leftVal, rightVal); 92 } 93 ASSERT_NOT_REACHED(); 94 return 0.0; 95 } 96 97 EqTestOp::EqTestOp(Opcode opcode, Expression* lhs, Expression* rhs) 98 : m_opcode(opcode) 99 { 100 addSubExpression(lhs); 101 addSubExpression(rhs); 102 } 103 104 bool EqTestOp::compare(const Value& lhs, const Value& rhs) const 105 { 106 if (lhs.isNodeSet()) { 107 const NodeSet& lhsSet = lhs.toNodeSet(); 108 if (rhs.isNodeSet()) { 109 // If both objects to be compared are node-sets, then the comparison will be true if and only if 110 // there is a node in the first node-set and a node in the second node-set such that the result of 111 // performing the comparison on the string-values of the two nodes is true. 112 const NodeSet& rhsSet = rhs.toNodeSet(); 113 for (unsigned lindex = 0; lindex < lhsSet.size(); ++lindex) 114 for (unsigned rindex = 0; rindex < rhsSet.size(); ++rindex) 115 if (compare(stringValue(lhsSet[lindex]), stringValue(rhsSet[rindex]))) 116 return true; 117 return false; 118 } 119 if (rhs.isNumber()) { 120 // If one object to be compared is a node-set and the other is a number, then the comparison will be true 121 // if and only if there is a node in the node-set such that the result of performing the comparison on the number 122 // to be compared and on the result of converting the string-value of that node to a number using the number function is true. 123 for (unsigned lindex = 0; lindex < lhsSet.size(); ++lindex) 124 if (compare(Value(stringValue(lhsSet[lindex])).toNumber(), rhs)) 125 return true; 126 return false; 127 } 128 if (rhs.isString()) { 129 // If one object to be compared is a node-set and the other is a string, then the comparison will be true 130 // if and only if there is a node in the node-set such that the result of performing the comparison on 131 // the string-value of the node and the other string is true. 132 for (unsigned lindex = 0; lindex < lhsSet.size(); ++lindex) 133 if (compare(stringValue(lhsSet[lindex]), rhs)) 134 return true; 135 return false; 136 } 137 if (rhs.isBoolean()) { 138 // If one object to be compared is a node-set and the other is a boolean, then the comparison will be true 139 // if and only if the result of performing the comparison on the boolean and on the result of converting 140 // the node-set to a boolean using the boolean function is true. 141 return compare(lhs.toBoolean(), rhs); 142 } 143 ASSERT(0); 144 } 145 if (rhs.isNodeSet()) { 146 const NodeSet& rhsSet = rhs.toNodeSet(); 147 if (lhs.isNumber()) { 148 for (unsigned rindex = 0; rindex < rhsSet.size(); ++rindex) 149 if (compare(lhs, Value(stringValue(rhsSet[rindex])).toNumber())) 150 return true; 151 return false; 152 } 153 if (lhs.isString()) { 154 for (unsigned rindex = 0; rindex < rhsSet.size(); ++rindex) 155 if (compare(lhs, stringValue(rhsSet[rindex]))) 156 return true; 157 return false; 158 } 159 if (lhs.isBoolean()) 160 return compare(lhs, rhs.toBoolean()); 161 ASSERT(0); 162 } 163 164 // Neither side is a NodeSet. 165 switch (m_opcode) { 166 case OP_EQ: 167 case OP_NE: 168 bool equal; 169 if (lhs.isBoolean() || rhs.isBoolean()) 170 equal = lhs.toBoolean() == rhs.toBoolean(); 171 else if (lhs.isNumber() || rhs.isNumber()) 172 equal = lhs.toNumber() == rhs.toNumber(); 173 else 174 equal = lhs.toString() == rhs.toString(); 175 176 if (m_opcode == OP_EQ) 177 return equal; 178 return !equal; 179 case OP_GT: 180 return lhs.toNumber() > rhs.toNumber(); 181 case OP_GE: 182 return lhs.toNumber() >= rhs.toNumber(); 183 case OP_LT: 184 return lhs.toNumber() < rhs.toNumber(); 185 case OP_LE: 186 return lhs.toNumber() <= rhs.toNumber(); 187 } 188 ASSERT(0); 189 return false; 190 } 191 192 Value EqTestOp::evaluate() const 193 { 194 Value lhs(subExpr(0)->evaluate()); 195 Value rhs(subExpr(1)->evaluate()); 196 197 return compare(lhs, rhs); 198 } 199 200 LogicalOp::LogicalOp(Opcode opcode, Expression* lhs, Expression* rhs) 201 : m_opcode(opcode) 202 { 203 addSubExpression(lhs); 204 addSubExpression(rhs); 205 } 206 207 bool LogicalOp::shortCircuitOn() const 208 { 209 if (m_opcode == OP_And) 210 return false; //false and foo 211 212 return true; //true or bar 213 } 214 215 Value LogicalOp::evaluate() const 216 { 217 Value lhs(subExpr(0)->evaluate()); 218 219 // This is not only an optimization, http://www.w3.org/TR/xpath 220 // dictates that we must do short-circuit evaluation 221 bool lhsBool = lhs.toBoolean(); 222 if (lhsBool == shortCircuitOn()) 223 return lhsBool; 224 225 return subExpr(1)->evaluate().toBoolean(); 226 } 227 228 Value Union::evaluate() const 229 { 230 Value lhsResult = subExpr(0)->evaluate(); 231 Value rhs = subExpr(1)->evaluate(); 232 233 NodeSet& resultSet = lhsResult.modifiableNodeSet(); 234 const NodeSet& rhsNodes = rhs.toNodeSet(); 235 236 HashSet<Node*> nodes; 237 for (size_t i = 0; i < resultSet.size(); ++i) 238 nodes.add(resultSet[i]); 239 240 for (size_t i = 0; i < rhsNodes.size(); ++i) { 241 Node* node = rhsNodes[i]; 242 if (nodes.add(node).isNewEntry) 243 resultSet.append(node); 244 } 245 246 // It is also possible to use merge sort to avoid making the result unsorted; 247 // but this would waste the time in cases when order is not important. 248 resultSet.markSorted(false); 249 return lhsResult; 250 } 251 252 Predicate::Predicate(Expression* expr) 253 : m_expr(expr) 254 { 255 } 256 257 Predicate::~Predicate() 258 { 259 delete m_expr; 260 } 261 262 bool Predicate::evaluate() const 263 { 264 ASSERT(m_expr != 0); 265 266 Value result(m_expr->evaluate()); 267 268 // foo[3] means foo[position()=3] 269 if (result.isNumber()) 270 return EqTestOp(EqTestOp::OP_EQ, createFunction("position"), new Number(result.toNumber())).evaluate().toBoolean(); 271 272 return result.toBoolean(); 273 } 274 275 } 276 } 277