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