1/* 2 * Copyright 2005 Frerich Raabe <raabe@kde.org> 3 * Copyright (C) 2006, 2013 Apple Inc. All rights reserved. 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 "XPathFunctions.h" 32#include "XPathUtil.h" 33#include <math.h> 34#include <wtf/MathExtras.h> 35 36namespace WebCore { 37namespace XPath { 38 39Number::Number(double value) 40 : m_value(value) 41{ 42} 43 44Value Number::evaluate() const 45{ 46 return m_value; 47} 48 49StringExpression::StringExpression(String&& value) 50 : m_value(WTF::move(value)) 51{ 52} 53 54Value StringExpression::evaluate() const 55{ 56 return m_value; 57} 58 59Negative::Negative(std::unique_ptr<Expression> expression) 60{ 61 addSubexpression(WTF::move(expression)); 62} 63 64Value Negative::evaluate() const 65{ 66 return -subexpression(0).evaluate().toNumber(); 67} 68 69NumericOp::NumericOp(Opcode opcode, std::unique_ptr<Expression> lhs, std::unique_ptr<Expression> rhs) 70 : m_opcode(opcode) 71{ 72 addSubexpression(WTF::move(lhs)); 73 addSubexpression(WTF::move(rhs)); 74} 75 76Value NumericOp::evaluate() const 77{ 78 double leftVal = subexpression(0).evaluate().toNumber(); 79 double rightVal = subexpression(1).evaluate().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 94 ASSERT_NOT_REACHED(); 95 return 0.0; 96} 97 98EqTestOp::EqTestOp(Opcode opcode, std::unique_ptr<Expression> lhs, std::unique_ptr<Expression> rhs) 99 : m_opcode(opcode) 100{ 101 addSubexpression(WTF::move(lhs)); 102 addSubexpression(WTF::move(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_NOT_REACHED(); 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_NOT_REACHED(); 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 190 ASSERT_NOT_REACHED(); 191 return false; 192} 193 194Value EqTestOp::evaluate() const 195{ 196 Value lhs(subexpression(0).evaluate()); 197 Value rhs(subexpression(1).evaluate()); 198 return compare(lhs, rhs); 199} 200 201LogicalOp::LogicalOp(Opcode opcode, std::unique_ptr<Expression> lhs, std::unique_ptr<Expression> rhs) 202 : m_opcode(opcode) 203{ 204 addSubexpression(WTF::move(lhs)); 205 addSubexpression(WTF::move(rhs)); 206} 207 208inline bool LogicalOp::shortCircuitOn() const 209{ 210 return m_opcode != OP_And; 211} 212 213Value LogicalOp::evaluate() const 214{ 215 // This is not only an optimization, http://www.w3.org/TR/xpath 216 // dictates that we must do short-circuit evaluation 217 bool lhsBool = subexpression(0).evaluate().toBoolean(); 218 if (lhsBool == shortCircuitOn()) 219 return lhsBool; 220 221 return subexpression(1).evaluate().toBoolean(); 222} 223 224Union::Union(std::unique_ptr<Expression> lhs, std::unique_ptr<Expression> rhs) 225{ 226 addSubexpression(WTF::move(lhs)); 227 addSubexpression(WTF::move(rhs)); 228} 229 230Value Union::evaluate() const 231{ 232 Value lhsResult = subexpression(0).evaluate(); 233 Value rhs = subexpression(1).evaluate(); 234 235 NodeSet& resultSet = lhsResult.modifiableNodeSet(); 236 const NodeSet& rhsNodes = rhs.toNodeSet(); 237 238 HashSet<Node*> nodes; 239 for (size_t i = 0; i < resultSet.size(); ++i) 240 nodes.add(resultSet[i]); 241 242 for (size_t i = 0; i < rhsNodes.size(); ++i) { 243 Node* node = rhsNodes[i]; 244 if (nodes.add(node).isNewEntry) 245 resultSet.append(node); 246 } 247 248 // It would also be possible to perform a merge sort here to avoid making an unsorted result, 249 // but that would waste the time in cases when order is not important. 250 resultSet.markSorted(false); 251 252 return lhsResult; 253} 254 255bool evaluatePredicate(const Expression& expression) 256{ 257 Value result(expression.evaluate()); 258 259 // foo[3] means foo[position()=3] 260 if (result.isNumber()) 261 return EqTestOp(EqTestOp::OP_EQ, Function::create(ASCIILiteral("position")), std::make_unique<Number>(result.toNumber())).evaluate().toBoolean(); 262 263 return result.toBoolean(); 264} 265 266bool predicateIsContextPositionSensitive(const Expression& expression) 267{ 268 return expression.isContextPositionSensitive() || expression.resultType() == Value::NumberValue; 269} 270 271} 272} 273