WebCore/xml/XPathFunctions.cpp

   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 "XPathFunctions.h"
  30
  31 #if ENABLE(XPATH)
  32
  33 #include "Document.h"
  34 #include "Element.h"
  35 #include "NamedAttrMap.h"
  36 #include "XMLNames.h"
  37 #include "XPathUtil.h"
  38 #include "XPathValue.h"
  39 #include <wtf/MathExtras.h>
  40
  41 namespace WebCore {
  42 namespace XPath {
  43
  44 static inline bool isWhitespace(UChar c)
  45 {
  46     return c == ' ' || c == '\n' || c == '\r' || c == '\t';
  47 }
  48
  49
  50 #define DEFINE_FUNCTION_CREATOR(Class) static Function* create##Class() { return new Class; }
  51
  52 class Interval {
  53 public:
  54     static const int Inf = -1;
  55
  56     Interval();
  57     Interval(int value);
  58     Interval(int min, int max);
  59
  60     bool contains(int value) const;
  61
  62 private:
  63     int m_min;
  64     int m_max;
  65 };
  66
  67 struct FunctionRec {
  68     typedef Function *(*FactoryFn)();
  69     FactoryFn factoryFn;
  70     Interval args;
  71 };
  72
  73 static HashMap<String, FunctionRec>* functionMap;
  74
  75 class FunLast : public Function {
  76     virtual Value evaluate() const;
  77 };
  78
  79 class FunPosition : public Function {
  80     virtual Value evaluate() const;
  81 };
  82
  83 class FunCount : public Function {
  84     virtual Value evaluate() const;
  85 };
  86
  87 class FunId : public Function {
  88     virtual Value evaluate() const;
  89 };
  90
  91 class FunLocalName : public Function {
  92     virtual Value evaluate() const;
  93 };
  94
  95 class FunNamespaceURI : public Function {
  96     virtual Value evaluate() const;
  97 };
  98
  99 class FunName : public Function {
 100     virtual Value evaluate() const;
 101 };
 102
 103 class FunString : public Function {
 104     virtual Value evaluate() const;
 105 };
 106
 107 class FunConcat : public Function {
 108     virtual Value evaluate() const;
 109 };
 110
 111 class FunStartsWith : public Function {
 112     virtual Value evaluate() const;
 113 };
 114
 115 class FunContains : public Function {
 116     virtual Value evaluate() const;
 117 };
 118
 119 class FunSubstringBefore : public Function {
 120     virtual Value evaluate() const;
 121 };
 122
 123 class FunSubstringAfter : public Function {
 124     virtual Value evaluate() const;
 125 };
 126
 127 class FunSubstring : public Function {
 128     virtual Value evaluate() const;
 129 };
 130
 131 class FunStringLength : public Function {
 132     virtual Value evaluate() const;
 133 };
 134
 135 class FunNormalizeSpace : public Function {
 136     virtual Value evaluate() const;
 137 };
 138
 139 class FunTranslate : public Function {
 140     virtual Value evaluate() const;
 141 };
 142
 143 class FunBoolean : public Function {
 144     virtual Value evaluate() const;
 145 };
 146
 147 class FunNot : public Function {
 148     virtual Value evaluate() const;
 149 };
 150
 151 class FunTrue : public Function {
 152     virtual Value evaluate() const;
 153 };
 154
 155 class FunFalse : public Function {
 156     virtual Value evaluate() const;
 157 };
 158
 159 class FunLang : public Function {
 160     virtual Value evaluate() const;
 161 };
 162
 163 class FunNumber : public Function {
 164     virtual Value evaluate() const;
 165 };
 166
 167 class FunSum : public Function {
 168     virtual Value evaluate() const;
 169 };
 170
 171 class FunFloor : public Function {
 172     virtual Value evaluate() const;
 173 };
 174
 175 class FunCeiling : public Function {
 176     virtual Value evaluate() const;
 177 };
 178
 179 class FunRound : public Function {
 180     virtual Value evaluate() const;
 181 public:
 182     static double round(double);
 183 };
 184
 185 DEFINE_FUNCTION_CREATOR(FunLast)
 186 DEFINE_FUNCTION_CREATOR(FunPosition)
 187 DEFINE_FUNCTION_CREATOR(FunCount)
 188 DEFINE_FUNCTION_CREATOR(FunId)
 189 DEFINE_FUNCTION_CREATOR(FunLocalName)
 190 DEFINE_FUNCTION_CREATOR(FunNamespaceURI)
 191 DEFINE_FUNCTION_CREATOR(FunName)
 192
 193 DEFINE_FUNCTION_CREATOR(FunString)
 194 DEFINE_FUNCTION_CREATOR(FunConcat)
 195 DEFINE_FUNCTION_CREATOR(FunStartsWith)
 196 DEFINE_FUNCTION_CREATOR(FunContains)
 197 DEFINE_FUNCTION_CREATOR(FunSubstringBefore)
 198 DEFINE_FUNCTION_CREATOR(FunSubstringAfter)
 199 DEFINE_FUNCTION_CREATOR(FunSubstring)
 200 DEFINE_FUNCTION_CREATOR(FunStringLength)
 201 DEFINE_FUNCTION_CREATOR(FunNormalizeSpace)
 202 DEFINE_FUNCTION_CREATOR(FunTranslate)
 203
 204 DEFINE_FUNCTION_CREATOR(FunBoolean)
 205 DEFINE_FUNCTION_CREATOR(FunNot)
 206 DEFINE_FUNCTION_CREATOR(FunTrue)
 207 DEFINE_FUNCTION_CREATOR(FunFalse)
 208 DEFINE_FUNCTION_CREATOR(FunLang)
 209
 210 DEFINE_FUNCTION_CREATOR(FunNumber)
 211 DEFINE_FUNCTION_CREATOR(FunSum)
 212 DEFINE_FUNCTION_CREATOR(FunFloor)
 213 DEFINE_FUNCTION_CREATOR(FunCeiling)
 214 DEFINE_FUNCTION_CREATOR(FunRound)
 215
 216 #undef DEFINE_FUNCTION_CREATOR
 217
 218 inline Interval::Interval()
 219     : m_min(Inf), m_max(Inf)
 220 {
 221 }
 222
 223 inline Interval::Interval(int value)
 224     : m_min(value), m_max(value)
 225 {
 226 }
 227
 228 inline Interval::Interval(int min, int max)
 229     : m_min(min), m_max(max)
 230 {
 231 }
 232
 233 inline bool Interval::contains(int value) const
 234 {
 235     if (m_min == Inf && m_max == Inf)
 236         return true;
 237
 238     if (m_min == Inf)
 239         return value <= m_max;
 240
 241     if (m_max == Inf)
 242         return value >= m_min;
 243
 244     return value >= m_min && value <= m_max;
 245 }
 246
 247 void Function::setArguments(const Vector<Expression*>& args)
 248 {
 249     Vector<Expression*>::const_iterator end = args.end();
 250
 251     for (Vector<Expression*>::const_iterator it = args.begin(); it != end; it++)
 252         addSubExpression(*it);
 253 }
 254
 255 Value FunLast::evaluate() const
 256 {
 257     return Expression::evaluationContext().size;
 258 }
 259
 260 Value FunPosition::evaluate() const
 261 {
 262     return Expression::evaluationContext().position;
 263 }
 264
 265 Value FunId::evaluate() const
 266 {
 267     Value a = arg(0)->evaluate();
 268     Vector<UChar> idList; // A whitespace-separated list of IDs
 269
 270     if (a.isNodeSet()) {
 271         const NodeSet& nodes = a.toNodeSet();
 272         for (size_t i = 0; i < nodes.size(); ++i) {
 273             String str = stringValue(nodes[i]);
 274             idList.append(str.characters(), str.length());
 275             idList.append(' ');
 276         }
 277     } else {
 278         String str = a.toString();
 279         idList.append(str.characters(), str.length());
 280     }
 281
 282     Document* contextDocument = evaluationContext().node->document();
 283     NodeSet result;
 284     HashSet<Node*> resultSet;
 285
 286     size_t startPos = 0;
 287     size_t length = idList.size();
 288     while (true) {
 289         while (startPos < length && isWhitespace(idList[startPos]))
 290             ++startPos;
 291
 292         if (startPos == length)
 293             break;
 294
 295         size_t endPos = startPos;
 296         while (endPos < length && !isWhitespace(idList[endPos]))
 297             ++endPos;
 298
 299         // If there are several nodes with the same id, id() should return the first one.
 300         // In WebKit, getElementById behaves so, too, although its behavior in this case is formally undefined.
 301         Node* node = contextDocument->getElementById(String(&idList[startPos], endPos - startPos));
 302         if (node && resultSet.add(node).second)
 303             result.append(node);
 304
 305         startPos = endPos;
 306     }
 307
 308     result.markSorted(false);
 309
 310     return Value(result, Value::adopt);
 311 }
 312
 313 Value FunLocalName::evaluate() const
 314 {
 315     Node* node = 0;
 316     if (argCount() > 0) {
 317         Value a = arg(0)->evaluate();
 318         if (!a.isNodeSet())
 319             return "";
 320
 321         node = a.toNodeSet().firstNode();
 322         if (!node)
 323             return "";
 324     }
 325
 326     if (!node)
 327         node = evaluationContext().node.get();
 328
 329     return node->localName().domString();
 330 }
 331
 332 Value FunNamespaceURI::evaluate() const
 333 {
 334     Node* node = 0;
 335     if (argCount() > 0) {
 336         Value a = arg(0)->evaluate();
 337         if (!a.isNodeSet())
 338             return "";
 339
 340         node = a.toNodeSet().firstNode();
 341         if (!node)
 342             return "";
 343     }
 344
 345     if (!node)
 346         node = evaluationContext().node.get();
 347
 348     return node->namespaceURI().domString();
 349 }
 350
 351 Value FunName::evaluate() const
 352 {
 353     Node* node = 0;
 354     if (argCount() > 0) {
 355         Value a = arg(0)->evaluate();
 356         if (!a.isNodeSet())
 357             return "";
 358
 359         node = a.toNodeSet().firstNode();
 360         if (!node)
 361             return "";
 362     }
 363
 364     if (!node)
 365         node = evaluationContext().node.get();
 366
 367     const AtomicString& prefix = node->prefix();
 368     return prefix.isEmpty() ? node->localName().domString() : prefix + ":" + node->localName();
 369 }
 370
 371 Value FunCount::evaluate() const
 372 {
 373     Value a = arg(0)->evaluate();
 374
 375     if (!a.isNodeSet())
 376         return 0.0;
 377
 378     return a.toNodeSet().size();
 379 }
 380
 381 Value FunString::evaluate() const
 382 {
 383     if (!argCount())
 384         return Value(Expression::evaluationContext().node.get()).toString();
 385     return arg(0)->evaluate().toString();
 386 }
 387
 388 Value FunConcat::evaluate() const
 389 {
 390     Vector<UChar, 1024> result;
 391
 392     unsigned count = argCount();
 393     for (unsigned i = 0; i < count; ++i) {
 394         String str(arg(i)->evaluate().toString());
 395         result.append(str.characters(), str.length());
 396     }
 397
 398     return String(result.data(), result.size());
 399 }
 400
 401 Value FunStartsWith::evaluate() const
 402 {
 403     String s1 = arg(0)->evaluate().toString();
 404     String s2 = arg(1)->evaluate().toString();
 405
 406     if (s2.isEmpty())
 407         return true;
 408
 409     return s1.startsWith(s2);
 410 }
 411
 412 Value FunContains::evaluate() const
 413 {
 414     String s1 = arg(0)->evaluate().toString();
 415     String s2 = arg(1)->evaluate().toString();
 416
 417     if (s2.isEmpty())
 418         return true;
 419
 420     return s1.contains(s2) != 0;
 421 }
 422
 423 Value FunSubstringBefore::evaluate() const
 424 {
 425     String s1 = arg(0)->evaluate().toString();
 426     String s2 = arg(1)->evaluate().toString();
 427
 428     if (s2.isEmpty())
 429         return "";
 430
 431     int i = s1.find(s2);
 432
 433     if (i == -1)
 434         return "";
 435
 436     return s1.left(i);
 437 }
 438
 439 Value FunSubstringAfter::evaluate() const
 440 {
 441     String s1 = arg(0)->evaluate().toString();
 442     String s2 = arg(1)->evaluate().toString();
 443
 444     int i = s1.find(s2);
 445     if (i == -1)
 446         return "";
 447
 448     return s1.substring(i + s2.length());
 449 }
 450
 451 Value FunSubstring::evaluate() const
 452 {
 453     String s = arg(0)->evaluate().toString();
 454     long pos = static_cast<long>(FunRound::round(arg(1)->evaluate().toNumber()));
 455     bool haveLength = argCount() == 3;
 456     long len = -1;
 457     if (haveLength) {
 458         double doubleLen = arg(2)->evaluate().toNumber();
 459         if (isnan(doubleLen))
 460             return "";
 461         len = static_cast<long>(FunRound::round(doubleLen));
 462     }
 463
 464     if (pos > long(s.length()))
 465         return "";
 466
 467     if (haveLength && pos < 1) {
 468         len -= 1 - pos;
 469         pos = 1;
 470         if (len < 1)
 471             return "";
 472     }
 473
 474     return s.substring(pos - 1, len);
 475 }
 476
 477 Value FunStringLength::evaluate() const
 478 {
 479     if (!argCount())
 480         return Value(Expression::evaluationContext().node.get()).toString().length();
 481     return arg(0)->evaluate().toString().length();
 482 }
 483
 484 Value FunNormalizeSpace::evaluate() const
 485 {
 486     if (!argCount()) {
 487         String s = Value(Expression::evaluationContext().node.get()).toString();
 488         return s.simplifyWhiteSpace();
 489     }
 490
 491     String s = arg(0)->evaluate().toString();
 492     return s.simplifyWhiteSpace();
 493 }
 494
 495 Value FunTranslate::evaluate() const
 496 {
 497     String s1 = arg(0)->evaluate().toString();
 498     String s2 = arg(1)->evaluate().toString();
 499     String s3 = arg(2)->evaluate().toString();
 500     String newString;
 501
 502     // FIXME: Building a String a character at a time is quite slow.
 503     for (unsigned i1 = 0; i1 < s1.length(); ++i1) {
 504         UChar ch = s1[i1];
 505         int i2 = s2.find(ch);
 506
 507         if (i2 == -1)
 508             newString += String(&ch, 1);
 509         else if ((unsigned)i2 < s3.length()) {
 510             UChar c2 = s3[i2];
 511             newString += String(&c2, 1);
 512         }
 513     }
 514
 515     return newString;
 516 }
 517
 518 Value FunBoolean::evaluate() const
 519 {
 520     return arg(0)->evaluate().toBoolean();
 521 }
 522
 523 Value FunNot::evaluate() const
 524 {
 525     return !arg(0)->evaluate().toBoolean();
 526 }
 527
 528 Value FunTrue::evaluate() const
 529 {
 530     return true;
 531 }
 532
 533 Value FunLang::evaluate() const
 534 {
 535     String lang = arg(0)->evaluate().toString();
 536
 537     RefPtr<Node> langNode = 0;
 538     Node* node = evaluationContext().node.get();
 539     while (node) {
 540         NamedAttrMap* attrs = node->attributes();
 541         if (attrs)
 542             langNode = attrs->getNamedItemNS(XMLNames::xmlNamespaceURI, "lang");
 543         if (langNode)
 544             break;
 545         node = node->parentNode();
 546     }
 547
 548     if (!langNode)
 549         return false;
 550
 551     String langNodeValue = langNode->nodeValue();
 552     while (true) {
 553         if (equalIgnoringCase(langNodeValue, lang))
 554             return true;
 555
 556         // Remove suffixes one by one.
 557         int index = langNodeValue.reverseFind('-');
 558         if (index == -1)
 559             break;
 560         langNodeValue = langNodeValue.left(index);
 561     }
 562
 563     return false;
 564 }
 565
 566 Value FunFalse::evaluate() const
 567 {
 568     return false;
 569 }
 570
 571 Value FunNumber::evaluate() const
 572 {
 573     if (!argCount())
 574         return Value(Expression::evaluationContext().node.get()).toNumber();
 575     return arg(0)->evaluate().toNumber();
 576 }
 577
 578 Value FunSum::evaluate() const
 579 {
 580     Value a = arg(0)->evaluate();
 581     if (!a.isNodeSet())
 582         return 0.0;
 583
 584     double sum = 0.0;
 585     const NodeSet& nodes = a.toNodeSet();
 586     // To be really compliant, we should sort the node-set, as floating point addition is not associative.
 587     // However, this is unlikely to ever become a practical issue, and sorting is slow.
 588
 589     for (unsigned i = 0; i < nodes.size(); i++)
 590         sum += Value(stringValue(nodes[i])).toNumber();
 591
 592     return sum;
 593 }
 594
 595 Value FunFloor::evaluate() const
 596 {
 597     return floor(arg(0)->evaluate().toNumber());
 598 }
 599
 600 Value FunCeiling::evaluate() const
 601 {
 602     return ceil(arg(0)->evaluate().toNumber());
 603 }
 604
 605 double FunRound::round(double val)
 606 {
 607     if (!isnan(val) && !isinf(val)) {
 608         if (signbit(val) && val >= -0.5)
 609             val *= 0; // negative zero
 610         else
 611             val = floor(val + 0.5);
 612     }
 613     return val;
 614 }
 615
 616 Value FunRound::evaluate() const
 617 {
 618     return round(arg(0)->evaluate().toNumber());
 619 }
 620
 621 static void createFunctionMap()
 622 {
 623     struct FunctionMapping {
 624         const char *name;
 625         FunctionRec function;
 626     };
 627     static const FunctionMapping functions[] = {
 628         { "boolean", { &createFunBoolean, 1 } },
 629         { "ceiling", { &createFunCeiling, 1 } },
 630         { "concat", { &createFunConcat, Interval(2, Interval::Inf) } },
 631         { "contains", { &createFunContains, 2 } },
 632         { "count", { &createFunCount, 1 } },
 633         { "false", { &createFunFalse, 0 } },
 634         { "floor", { &createFunFloor, 1 } },
 635         { "id", { &createFunId, 1 } },
 636         { "lang", { &createFunLang, 1 } },
 637         { "last", { &createFunLast, 0 } },
 638         { "local-name", { &createFunLocalName, Interval(0, 1) } },
 639         { "name", { &createFunName, Interval(0, 1) } },
 640         { "namespace-uri", { &createFunNamespaceURI, Interval(0, 1) } },
 641         { "normalize-space", { &createFunNormalizeSpace, Interval(0, 1) } },
 642         { "not", { &createFunNot, 1 } },
 643         { "number", { &createFunNumber, Interval(0, 1) } },
 644         { "position", { &createFunPosition, 0 } },
 645         { "round", { &createFunRound, 1 } },
 646         { "starts-with", { &createFunStartsWith, 2 } },
 647         { "string", { &createFunString, Interval(0, 1) } },
 648         { "string-length", { &createFunStringLength, Interval(0, 1) } },
 649         { "substring", { &createFunSubstring, Interval(2, 3) } },
 650         { "substring-after", { &createFunSubstringAfter, 2 } },
 651         { "substring-before", { &createFunSubstringBefore, 2 } },
 652         { "sum", { &createFunSum, 1 } },
 653         { "translate", { &createFunTranslate, 3 } },
 654         { "true", { &createFunTrue, 0 } },
 655     };
 656     const unsigned int numFunctions = sizeof(functions) / sizeof(functions[0]);
 657
 658     functionMap = new HashMap<String, FunctionRec>;
 659     for (unsigned i = 0; i < numFunctions; ++i)
 660         functionMap->set(functions[i].name, functions[i].function);
 661 }
 662
 663 Function* createFunction(const String& name, const Vector<Expression*>& args)
 664 {
 665     if (!functionMap)
 666         createFunctionMap();
 667
 668     HashMap<String, FunctionRec>::iterator functionMapIter = functionMap->find(name);
 669     FunctionRec* functionRec = 0;
 670
 671     if (functionMapIter == functionMap->end() || !(functionRec = &functionMapIter->second)->args.contains(args.size()))
 672         return 0;
 673
 674     Function* function = functionRec->factoryFn();
 675     function->setArguments(args);
 676     function->setName(name);
 677     return function;
 678 }
 679
 680 }
 681 }
 682
 683 #endif // ENABLE(XPATH)