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 38namespace WebCore { 39namespace XPath { 40 41Number::Number(double value) 42 : m_value(value) 43{ 44} 45 46Value Number::evaluate() const 47{ 48 return m_value; 49} 50 51StringExpression::StringExpression(const String& value) 52 : m_value(value) 53{ 54} 55 56Value StringExpression::evaluate() const 57{ 58 return m_value; 59} 60 61Value Negative::evaluate() const 62{ 63 Value p(subExpr(0)->evaluate()); 64 return -p.toNumber(); 65} 66 67NumericOp::NumericOp(Opcode opcode, Expression* lhs, Expression* rhs) 68 : m_opcode(opcode) 69{ 70 addSubExpression(lhs); 71 addSubExpression(rhs); 72} 73 74Value 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 98EqTestOp::EqTestOp(Opcode opcode, Expression* lhs, Expression* rhs) 99 : m_opcode(opcode) 100{ 101 addSubExpression(lhs); 102 addSubExpression(rhs); 103} 104 105bool 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 193Value EqTestOp::evaluate() const 194{ 195 Value lhs(subExpr(0)->evaluate()); 196 Value rhs(subExpr(1)->evaluate()); 197 198 return compare(lhs, rhs); 199} 200 201LogicalOp::LogicalOp(Opcode opcode, Expression* lhs, Expression* rhs) 202 : m_opcode(opcode) 203{ 204 addSubExpression(lhs); 205 addSubExpression(rhs); 206} 207 208bool 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 216Value 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 229Value 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).isNewEntry) 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 253Predicate::Predicate(Expression* expr) 254 : m_expr(expr) 255{ 256} 257 258Predicate::~Predicate() 259{ 260 delete m_expr; 261} 262 263bool 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} 278