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 

    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((unsigned long)(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, (unsigned long)(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 (unsigned long)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 (unsigned long)lhsBool;

   228 

   229     return (unsigned long)(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)