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