1 /* 2 * xpath.c: XML Path Language implementation 3 * XPath is a language for addressing parts of an XML document, 4 * designed to be used by both XSLT and XPointer 5 *f 6 * Reference: W3C Recommendation 16 November 1999 7 * http://www.w3.org/TR/1999/REC-xpath-19991116 8 * Public reference: 9 * http://www.w3.org/TR/xpath 10 * 11 * See Copyright for the status of this software 12 * 13 * Author: daniel (at) veillard.com 14 * 15 */ 16 17 #define IN_LIBXML 18 #include "libxml.h" 19 20 #include <string.h> 21 22 #ifdef HAVE_SYS_TYPES_H 23 #include <sys/types.h> 24 #endif 25 #ifdef HAVE_MATH_H 26 #include <math.h> 27 #endif 28 #ifdef HAVE_FLOAT_H 29 #include <float.h> 30 #endif 31 #ifdef HAVE_CTYPE_H 32 #include <ctype.h> 33 #endif 34 #ifdef HAVE_SIGNAL_H 35 #include <signal.h> 36 #endif 37 38 #include <libxml/xmlmemory.h> 39 #include <libxml/tree.h> 40 #include <libxml/valid.h> 41 #include <libxml/xpath.h> 42 #include <libxml/xpathInternals.h> 43 #include <libxml/parserInternals.h> 44 #include <libxml/hash.h> 45 #ifdef LIBXML_XPTR_ENABLED 46 #include <libxml/xpointer.h> 47 #endif 48 #ifdef LIBXML_DEBUG_ENABLED 49 #include <libxml/debugXML.h> 50 #endif 51 #include <libxml/xmlerror.h> 52 #include <libxml/threads.h> 53 #include <libxml/globals.h> 54 #ifdef LIBXML_PATTERN_ENABLED 55 #include <libxml/pattern.h> 56 #endif 57 58 #include "buf.h" 59 60 #ifdef LIBXML_PATTERN_ENABLED 61 #define XPATH_STREAMING 62 #endif 63 64 #define TODO \ 65 xmlGenericError(xmlGenericErrorContext, \ 66 "Unimplemented block at %s:%d\n", \ 67 __FILE__, __LINE__); 68 69 /** 70 * WITH_TIM_SORT: 71 * 72 * Use the Timsort algorithm provided in timsort.h to sort 73 * nodeset as this is a great improvement over the old Shell sort 74 * used in xmlXPathNodeSetSort() 75 */ 76 #define WITH_TIM_SORT 77 78 /* 79 * XP_OPTIMIZED_NON_ELEM_COMPARISON: 80 * If defined, this will use xmlXPathCmpNodesExt() instead of 81 * xmlXPathCmpNodes(). The new function is optimized comparison of 82 * non-element nodes; actually it will speed up comparison only if 83 * xmlXPathOrderDocElems() was called in order to index the elements of 84 * a tree in document order; Libxslt does such an indexing, thus it will 85 * benefit from this optimization. 86 */ 87 #define XP_OPTIMIZED_NON_ELEM_COMPARISON 88 89 /* 90 * XP_OPTIMIZED_FILTER_FIRST: 91 * If defined, this will optimize expressions like "key('foo', 'val')[b][1]" 92 * in a way, that it stop evaluation at the first node. 93 */ 94 #define XP_OPTIMIZED_FILTER_FIRST 95 96 /* 97 * XP_DEBUG_OBJ_USAGE: 98 * Internal flag to enable tracking of how much XPath objects have been 99 * created. 100 */ 101 /* #define XP_DEBUG_OBJ_USAGE */ 102 103 /* 104 * XPATH_MAX_STEPS: 105 * when compiling an XPath expression we arbitrary limit the maximum 106 * number of step operation in the compiled expression. 1000000 is 107 * an insanely large value which should never be reached under normal 108 * circumstances 109 */ 110 #define XPATH_MAX_STEPS 1000000 111 112 /* 113 * XPATH_MAX_STACK_DEPTH: 114 * when evaluating an XPath expression we arbitrary limit the maximum 115 * number of object allowed to be pushed on the stack. 1000000 is 116 * an insanely large value which should never be reached under normal 117 * circumstances 118 */ 119 #define XPATH_MAX_STACK_DEPTH 1000000 120 121 /* 122 * XPATH_MAX_NODESET_LENGTH: 123 * when evaluating an XPath expression nodesets are created and we 124 * arbitrary limit the maximum length of those node set. 10000000 is 125 * an insanely large value which should never be reached under normal 126 * circumstances, one would first need to construct an in memory tree 127 * with more than 10 millions nodes. 128 */ 129 #define XPATH_MAX_NODESET_LENGTH 10000000 130 131 /* 132 * TODO: 133 * There are a few spots where some tests are done which depend upon ascii 134 * data. These should be enhanced for full UTF8 support (see particularly 135 * any use of the macros IS_ASCII_CHARACTER and IS_ASCII_DIGIT) 136 */ 137 138 #ifdef XP_OPTIMIZED_NON_ELEM_COMPARISON 139 /** 140 * xmlXPathCmpNodesExt: 141 * @node1: the first node 142 * @node2: the second node 143 * 144 * Compare two nodes w.r.t document order. 145 * This one is optimized for handling of non-element nodes. 146 * 147 * Returns -2 in case of error 1 if first point < second point, 0 if 148 * it's the same node, -1 otherwise 149 */ 150 static int 151 xmlXPathCmpNodesExt(xmlNodePtr node1, xmlNodePtr node2) { 152 int depth1, depth2; 153 int misc = 0, precedence1 = 0, precedence2 = 0; 154 xmlNodePtr miscNode1 = NULL, miscNode2 = NULL; 155 xmlNodePtr cur, root; 156 long l1, l2; 157 158 if ((node1 == NULL) || (node2 == NULL)) 159 return(-2); 160 161 if (node1 == node2) 162 return(0); 163 164 /* 165 * a couple of optimizations which will avoid computations in most cases 166 */ 167 switch (node1->type) { 168 case XML_ELEMENT_NODE: 169 if (node2->type == XML_ELEMENT_NODE) { 170 if ((0 > (long) node1->content) && /* TODO: Would a != 0 suffice here? */ 171 (0 > (long) node2->content) && 172 (node1->doc == node2->doc)) 173 { 174 l1 = -((long) node1->content); 175 l2 = -((long) node2->content); 176 if (l1 < l2) 177 return(1); 178 if (l1 > l2) 179 return(-1); 180 } else 181 goto turtle_comparison; 182 } 183 break; 184 case XML_ATTRIBUTE_NODE: 185 precedence1 = 1; /* element is owner */ 186 miscNode1 = node1; 187 node1 = node1->parent; 188 misc = 1; 189 break; 190 case XML_TEXT_NODE: 191 case XML_CDATA_SECTION_NODE: 192 case XML_COMMENT_NODE: 193 case XML_PI_NODE: { 194 miscNode1 = node1; 195 /* 196 * Find nearest element node. 197 */ 198 if (node1->prev != NULL) { 199 do { 200 node1 = node1->prev; 201 if (node1->type == XML_ELEMENT_NODE) { 202 precedence1 = 3; /* element in prev-sibl axis */ 203 break; 204 } 205 if (node1->prev == NULL) { 206 precedence1 = 2; /* element is parent */ 207 /* 208 * URGENT TODO: Are there any cases, where the 209 * parent of such a node is not an element node? 210 */ 211 node1 = node1->parent; 212 break; 213 } 214 } while (1); 215 } else { 216 precedence1 = 2; /* element is parent */ 217 node1 = node1->parent; 218 } 219 if ((node1 == NULL) || (node1->type != XML_ELEMENT_NODE) || 220 (0 <= (long) node1->content)) { 221 /* 222 * Fallback for whatever case. 223 */ 224 node1 = miscNode1; 225 precedence1 = 0; 226 } else 227 misc = 1; 228 } 229 break; 230 case XML_NAMESPACE_DECL: 231 /* 232 * TODO: why do we return 1 for namespace nodes? 233 */ 234 return(1); 235 default: 236 break; 237 } 238 switch (node2->type) { 239 case XML_ELEMENT_NODE: 240 break; 241 case XML_ATTRIBUTE_NODE: 242 precedence2 = 1; /* element is owner */ 243 miscNode2 = node2; 244 node2 = node2->parent; 245 misc = 1; 246 break; 247 case XML_TEXT_NODE: 248 case XML_CDATA_SECTION_NODE: 249 case XML_COMMENT_NODE: 250 case XML_PI_NODE: { 251 miscNode2 = node2; 252 if (node2->prev != NULL) { 253 do { 254 node2 = node2->prev; 255 if (node2->type == XML_ELEMENT_NODE) { 256 precedence2 = 3; /* element in prev-sibl axis */ 257 break; 258 } 259 if (node2->prev == NULL) { 260 precedence2 = 2; /* element is parent */ 261 node2 = node2->parent; 262 break; 263 } 264 } while (1); 265 } else { 266 precedence2 = 2; /* element is parent */ 267 node2 = node2->parent; 268 } 269 if ((node2 == NULL) || (node2->type != XML_ELEMENT_NODE) || 270 (0 <= (long) node2->content)) 271 { 272 node2 = miscNode2; 273 precedence2 = 0; 274 } else 275 misc = 1; 276 } 277 break; 278 case XML_NAMESPACE_DECL: 279 return(1); 280 default: 281 break; 282 } 283 if (misc) { 284 if (node1 == node2) { 285 if (precedence1 == precedence2) { 286 /* 287 * The ugly case; but normally there aren't many 288 * adjacent non-element nodes around. 289 */ 290 cur = miscNode2->prev; 291 while (cur != NULL) { 292 if (cur == miscNode1) 293 return(1); 294 if (cur->type == XML_ELEMENT_NODE) 295 return(-1); 296 cur = cur->prev; 297 } 298 return (-1); 299 } else { 300 /* 301 * Evaluate based on higher precedence wrt to the element. 302 * TODO: This assumes attributes are sorted before content. 303 * Is this 100% correct? 304 */ 305 if (precedence1 < precedence2) 306 return(1); 307 else 308 return(-1); 309 } 310 } 311 /* 312 * Special case: One of the helper-elements is contained by the other. 313 * <foo> 314 * <node2> 315 * <node1>Text-1(precedence1 == 2)</node1> 316 * </node2> 317 * Text-6(precedence2 == 3) 318 * </foo> 319 */ 320 if ((precedence2 == 3) && (precedence1 > 1)) { 321 cur = node1->parent; 322 while (cur) { 323 if (cur == node2) 324 return(1); 325 cur = cur->parent; 326 } 327 } 328 if ((precedence1 == 3) && (precedence2 > 1)) { 329 cur = node2->parent; 330 while (cur) { 331 if (cur == node1) 332 return(-1); 333 cur = cur->parent; 334 } 335 } 336 } 337 338 /* 339 * Speedup using document order if availble. 340 */ 341 if ((node1->type == XML_ELEMENT_NODE) && 342 (node2->type == XML_ELEMENT_NODE) && 343 (0 > (long) node1->content) && 344 (0 > (long) node2->content) && 345 (node1->doc == node2->doc)) { 346 347 l1 = -((long) node1->content); 348 l2 = -((long) node2->content); 349 if (l1 < l2) 350 return(1); 351 if (l1 > l2) 352 return(-1); 353 } 354 355 turtle_comparison: 356 357 if (node1 == node2->prev) 358 return(1); 359 if (node1 == node2->next) 360 return(-1); 361 /* 362 * compute depth to root 363 */ 364 for (depth2 = 0, cur = node2; cur->parent != NULL; cur = cur->parent) { 365 if (cur->parent == node1) 366 return(1); 367 depth2++; 368 } 369 root = cur; 370 for (depth1 = 0, cur = node1; cur->parent != NULL; cur = cur->parent) { 371 if (cur->parent == node2) 372 return(-1); 373 depth1++; 374 } 375 /* 376 * Distinct document (or distinct entities :-( ) case. 377 */ 378 if (root != cur) { 379 return(-2); 380 } 381 /* 382 * get the nearest common ancestor. 383 */ 384 while (depth1 > depth2) { 385 depth1--; 386 node1 = node1->parent; 387 } 388 while (depth2 > depth1) { 389 depth2--; 390 node2 = node2->parent; 391 } 392 while (node1->parent != node2->parent) { 393 node1 = node1->parent; 394 node2 = node2->parent; 395 /* should not happen but just in case ... */ 396 if ((node1 == NULL) || (node2 == NULL)) 397 return(-2); 398 } 399 /* 400 * Find who's first. 401 */ 402 if (node1 == node2->prev) 403 return(1); 404 if (node1 == node2->next) 405 return(-1); 406 /* 407 * Speedup using document order if availble. 408 */ 409 if ((node1->type == XML_ELEMENT_NODE) && 410 (node2->type == XML_ELEMENT_NODE) && 411 (0 > (long) node1->content) && 412 (0 > (long) node2->content) && 413 (node1->doc == node2->doc)) { 414 415 l1 = -((long) node1->content); 416 l2 = -((long) node2->content); 417 if (l1 < l2) 418 return(1); 419 if (l1 > l2) 420 return(-1); 421 } 422 423 for (cur = node1->next;cur != NULL;cur = cur->next) 424 if (cur == node2) 425 return(1); 426 return(-1); /* assume there is no sibling list corruption */ 427 } 428 #endif /* XP_OPTIMIZED_NON_ELEM_COMPARISON */ 429 430 /* 431 * Wrapper for the Timsort argorithm from timsort.h 432 */ 433 #ifdef WITH_TIM_SORT 434 #define SORT_NAME libxml_domnode 435 #define SORT_TYPE xmlNodePtr 436 /** 437 * wrap_cmp: 438 * @x: a node 439 * @y: another node 440 * 441 * Comparison function for the Timsort implementation 442 * 443 * Returns -2 in case of error -1 if first point < second point, 0 if 444 * it's the same node, +1 otherwise 445 */ 446 static 447 int wrap_cmp( xmlNodePtr x, xmlNodePtr y ); 448 #ifdef XP_OPTIMIZED_NON_ELEM_COMPARISON 449 static int wrap_cmp( xmlNodePtr x, xmlNodePtr y ) 450 { 451 int res = xmlXPathCmpNodesExt(x, y); 452 return res == -2 ? res : -res; 453 } 454 #else 455 static int wrap_cmp( xmlNodePtr x, xmlNodePtr y ) 456 { 457 int res = xmlXPathCmpNodes(x, y); 458 return res == -2 ? res : -res; 459 } 460 #endif 461 #define SORT_CMP(x, y) (wrap_cmp(x, y)) 462 #include "timsort.h" 463 #endif /* WITH_TIM_SORT */ 464 465 #if defined(LIBXML_XPATH_ENABLED) || defined(LIBXML_SCHEMAS_ENABLED) 466 467 /************************************************************************ 468 * * 469 * Floating point stuff * 470 * * 471 ************************************************************************/ 472 473 #ifndef TRIO_REPLACE_STDIO 474 #define TRIO_PUBLIC static 475 #endif 476 #include "trionan.c" 477 478 /* 479 * The lack of portability of this section of the libc is annoying ! 480 */ 481 double xmlXPathNAN = 0; 482 double xmlXPathPINF = 1; 483 double xmlXPathNINF = -1; 484 static double xmlXPathNZERO = 0; /* not exported from headers */ 485 static int xmlXPathInitialized = 0; 486 487 /** 488 * xmlXPathInit: 489 * 490 * Initialize the XPath environment 491 */ 492 void 493 xmlXPathInit(void) { 494 if (xmlXPathInitialized) return; 495 496 xmlXPathPINF = trio_pinf(); 497 xmlXPathNINF = trio_ninf(); 498 xmlXPathNAN = trio_nan(); 499 xmlXPathNZERO = trio_nzero(); 500 501 xmlXPathInitialized = 1; 502 } 503 504 /** 505 * xmlXPathIsNaN: 506 * @val: a double value 507 * 508 * Provides a portable isnan() function to detect whether a double 509 * is a NotaNumber. Based on trio code 510 * http://sourceforge.net/projects/ctrio/ 511 * 512 * Returns 1 if the value is a NaN, 0 otherwise 513 */ 514 int 515 xmlXPathIsNaN(double val) { 516 return(trio_isnan(val)); 517 } 518 519 /** 520 * xmlXPathIsInf: 521 * @val: a double value 522 * 523 * Provides a portable isinf() function to detect whether a double 524 * is a +Infinite or -Infinite. Based on trio code 525 * http://sourceforge.net/projects/ctrio/ 526 * 527 * Returns 1 vi the value is +Infinite, -1 if -Infinite, 0 otherwise 528 */ 529 int 530 xmlXPathIsInf(double val) { 531 return(trio_isinf(val)); 532 } 533 534 #endif /* SCHEMAS or XPATH */ 535 #ifdef LIBXML_XPATH_ENABLED 536 /** 537 * xmlXPathGetSign: 538 * @val: a double value 539 * 540 * Provides a portable function to detect the sign of a double 541 * Modified from trio code 542 * http://sourceforge.net/projects/ctrio/ 543 * 544 * Returns 1 if the value is Negative, 0 if positive 545 */ 546 static int 547 xmlXPathGetSign(double val) { 548 return(trio_signbit(val)); 549 } 550 551 552 /* 553 * TODO: when compatibility allows remove all "fake node libxslt" strings 554 * the test should just be name[0] = ' ' 555 */ 556 #ifdef DEBUG_XPATH_EXPRESSION 557 #define DEBUG_STEP 558 #define DEBUG_EXPR 559 #define DEBUG_EVAL_COUNTS 560 #endif 561 562 static xmlNs xmlXPathXMLNamespaceStruct = { 563 NULL, 564 XML_NAMESPACE_DECL, 565 XML_XML_NAMESPACE, 566 BAD_CAST "xml", 567 NULL, 568 NULL 569 }; 570 static xmlNsPtr xmlXPathXMLNamespace = &xmlXPathXMLNamespaceStruct; 571 #ifndef LIBXML_THREAD_ENABLED 572 /* 573 * Optimizer is disabled only when threaded apps are detected while 574 * the library ain't compiled for thread safety. 575 */ 576 static int xmlXPathDisableOptimizer = 0; 577 #endif 578 579 /************************************************************************ 580 * * 581 * Error handling routines * 582 * * 583 ************************************************************************/ 584 585 /** 586 * XP_ERRORNULL: 587 * @X: the error code 588 * 589 * Macro to raise an XPath error and return NULL. 590 */ 591 #define XP_ERRORNULL(X) \ 592 { xmlXPathErr(ctxt, X); return(NULL); } 593 594 /* 595 * The array xmlXPathErrorMessages corresponds to the enum xmlXPathError 596 */ 597 static const char *xmlXPathErrorMessages[] = { 598 "Ok\n", 599 "Number encoding\n", 600 "Unfinished literal\n", 601 "Start of literal\n", 602 "Expected $ for variable reference\n", 603 "Undefined variable\n", 604 "Invalid predicate\n", 605 "Invalid expression\n", 606 "Missing closing curly brace\n", 607 "Unregistered function\n", 608 "Invalid operand\n", 609 "Invalid type\n", 610 "Invalid number of arguments\n", 611 "Invalid context size\n", 612 "Invalid context position\n", 613 "Memory allocation error\n", 614 "Syntax error\n", 615 "Resource error\n", 616 "Sub resource error\n", 617 "Undefined namespace prefix\n", 618 "Encoding error\n", 619 "Char out of XML range\n", 620 "Invalid or incomplete context\n", 621 "Stack usage error\n", 622 "Forbidden variable\n", 623 "?? Unknown error ??\n" /* Must be last in the list! */ 624 }; 625 #define MAXERRNO ((int)(sizeof(xmlXPathErrorMessages) / \ 626 sizeof(xmlXPathErrorMessages[0])) - 1) 627 /** 628 * xmlXPathErrMemory: 629 * @ctxt: an XPath context 630 * @extra: extra informations 631 * 632 * Handle a redefinition of attribute error 633 */ 634 static void 635 xmlXPathErrMemory(xmlXPathContextPtr ctxt, const char *extra) 636 { 637 if (ctxt != NULL) { 638 if (extra) { 639 xmlChar buf[200]; 640 641 xmlStrPrintf(buf, 200, 642 BAD_CAST "Memory allocation failed : %s\n", 643 extra); 644 ctxt->lastError.message = (char *) xmlStrdup(buf); 645 } else { 646 ctxt->lastError.message = (char *) 647 xmlStrdup(BAD_CAST "Memory allocation failed\n"); 648 } 649 ctxt->lastError.domain = XML_FROM_XPATH; 650 ctxt->lastError.code = XML_ERR_NO_MEMORY; 651 if (ctxt->error != NULL) 652 ctxt->error(ctxt->userData, &ctxt->lastError); 653 } else { 654 if (extra) 655 __xmlRaiseError(NULL, NULL, NULL, 656 NULL, NULL, XML_FROM_XPATH, 657 XML_ERR_NO_MEMORY, XML_ERR_FATAL, NULL, 0, 658 extra, NULL, NULL, 0, 0, 659 "Memory allocation failed : %s\n", extra); 660 else 661 __xmlRaiseError(NULL, NULL, NULL, 662 NULL, NULL, XML_FROM_XPATH, 663 XML_ERR_NO_MEMORY, XML_ERR_FATAL, NULL, 0, 664 NULL, NULL, NULL, 0, 0, 665 "Memory allocation failed\n"); 666 } 667 } 668 669 /** 670 * xmlXPathPErrMemory: 671 * @ctxt: an XPath parser context 672 * @extra: extra informations 673 * 674 * Handle a redefinition of attribute error 675 */ 676 static void 677 xmlXPathPErrMemory(xmlXPathParserContextPtr ctxt, const char *extra) 678 { 679 if (ctxt == NULL) 680 xmlXPathErrMemory(NULL, extra); 681 else { 682 ctxt->error = XPATH_MEMORY_ERROR; 683 xmlXPathErrMemory(ctxt->context, extra); 684 } 685 } 686 687 /** 688 * xmlXPathErr: 689 * @ctxt: a XPath parser context 690 * @error: the error code 691 * 692 * Handle an XPath error 693 */ 694 void 695 xmlXPathErr(xmlXPathParserContextPtr ctxt, int error) 696 { 697 if ((error < 0) || (error > MAXERRNO)) 698 error = MAXERRNO; 699 if (ctxt == NULL) { 700 __xmlRaiseError(NULL, NULL, NULL, 701 NULL, NULL, XML_FROM_XPATH, 702 error + XML_XPATH_EXPRESSION_OK - XPATH_EXPRESSION_OK, 703 XML_ERR_ERROR, NULL, 0, 704 NULL, NULL, NULL, 0, 0, 705 "%s", xmlXPathErrorMessages[error]); 706 return; 707 } 708 ctxt->error = error; 709 if (ctxt->context == NULL) { 710 __xmlRaiseError(NULL, NULL, NULL, 711 NULL, NULL, XML_FROM_XPATH, 712 error + XML_XPATH_EXPRESSION_OK - XPATH_EXPRESSION_OK, 713 XML_ERR_ERROR, NULL, 0, 714 (const char *) ctxt->base, NULL, NULL, 715 ctxt->cur - ctxt->base, 0, 716 "%s", xmlXPathErrorMessages[error]); 717 return; 718 } 719 720 /* cleanup current last error */ 721 xmlResetError(&ctxt->context->lastError); 722 723 ctxt->context->lastError.domain = XML_FROM_XPATH; 724 ctxt->context->lastError.code = error + XML_XPATH_EXPRESSION_OK - 725 XPATH_EXPRESSION_OK; 726 ctxt->context->lastError.level = XML_ERR_ERROR; 727 ctxt->context->lastError.str1 = (char *) xmlStrdup(ctxt->base); 728 ctxt->context->lastError.int1 = ctxt->cur - ctxt->base; 729 ctxt->context->lastError.node = ctxt->context->debugNode; 730 if (ctxt->context->error != NULL) { 731 ctxt->context->error(ctxt->context->userData, 732 &ctxt->context->lastError); 733 } else { 734 __xmlRaiseError(NULL, NULL, NULL, 735 NULL, ctxt->context->debugNode, XML_FROM_XPATH, 736 error + XML_XPATH_EXPRESSION_OK - XPATH_EXPRESSION_OK, 737 XML_ERR_ERROR, NULL, 0, 738 (const char *) ctxt->base, NULL, NULL, 739 ctxt->cur - ctxt->base, 0, 740 "%s", xmlXPathErrorMessages[error]); 741 } 742 743 } 744 745 /** 746 * xmlXPatherror: 747 * @ctxt: the XPath Parser context 748 * @file: the file name 749 * @line: the line number 750 * @no: the error number 751 * 752 * Formats an error message. 753 */ 754 void 755 xmlXPatherror(xmlXPathParserContextPtr ctxt, const char *file ATTRIBUTE_UNUSED, 756 int line ATTRIBUTE_UNUSED, int no) { 757 xmlXPathErr(ctxt, no); 758 } 759 760 /************************************************************************ 761 * * 762 * Utilities * 763 * * 764 ************************************************************************/ 765 766 /** 767 * xsltPointerList: 768 * 769 * Pointer-list for various purposes. 770 */ 771 typedef struct _xmlPointerList xmlPointerList; 772 typedef xmlPointerList *xmlPointerListPtr; 773 struct _xmlPointerList { 774 void **items; 775 int number; 776 int size; 777 }; 778 /* 779 * TODO: Since such a list-handling is used in xmlschemas.c and libxslt 780 * and here, we should make the functions public. 781 */ 782 static int 783 xmlPointerListAddSize(xmlPointerListPtr list, 784 void *item, 785 int initialSize) 786 { 787 if (list->items == NULL) { 788 if (initialSize <= 0) 789 initialSize = 1; 790 list->items = (void **) xmlMalloc(initialSize * sizeof(void *)); 791 if (list->items == NULL) { 792 xmlXPathErrMemory(NULL, 793 "xmlPointerListCreate: allocating item\n"); 794 return(-1); 795 } 796 list->number = 0; 797 list->size = initialSize; 798 } else if (list->size <= list->number) { 799 if (list->size > 50000000) { 800 xmlXPathErrMemory(NULL, 801 "xmlPointerListAddSize: re-allocating item\n"); 802 return(-1); 803 } 804 list->size *= 2; 805 list->items = (void **) xmlRealloc(list->items, 806 list->size * sizeof(void *)); 807 if (list->items == NULL) { 808 xmlXPathErrMemory(NULL, 809 "xmlPointerListAddSize: re-allocating item\n"); 810 list->size = 0; 811 return(-1); 812 } 813 } 814 list->items[list->number++] = item; 815 return(0); 816 } 817 818 /** 819 * xsltPointerListCreate: 820 * 821 * Creates an xsltPointerList structure. 822 * 823 * Returns a xsltPointerList structure or NULL in case of an error. 824 */ 825 static xmlPointerListPtr 826 xmlPointerListCreate(int initialSize) 827 { 828 xmlPointerListPtr ret; 829 830 ret = xmlMalloc(sizeof(xmlPointerList)); 831 if (ret == NULL) { 832 xmlXPathErrMemory(NULL, 833 "xmlPointerListCreate: allocating item\n"); 834 return (NULL); 835 } 836 memset(ret, 0, sizeof(xmlPointerList)); 837 if (initialSize > 0) { 838 xmlPointerListAddSize(ret, NULL, initialSize); 839 ret->number = 0; 840 } 841 return (ret); 842 } 843 844 /** 845 * xsltPointerListFree: 846 * 847 * Frees the xsltPointerList structure. This does not free 848 * the content of the list. 849 */ 850 static void 851 xmlPointerListFree(xmlPointerListPtr list) 852 { 853 if (list == NULL) 854 return; 855 if (list->items != NULL) 856 xmlFree(list->items); 857 xmlFree(list); 858 } 859 860 /************************************************************************ 861 * * 862 * Parser Types * 863 * * 864 ************************************************************************/ 865 866 /* 867 * Types are private: 868 */ 869 870 typedef enum { 871 XPATH_OP_END=0, 872 XPATH_OP_AND, 873 XPATH_OP_OR, 874 XPATH_OP_EQUAL, 875 XPATH_OP_CMP, 876 XPATH_OP_PLUS, 877 XPATH_OP_MULT, 878 XPATH_OP_UNION, 879 XPATH_OP_ROOT, 880 XPATH_OP_NODE, 881 XPATH_OP_RESET, /* 10 */ 882 XPATH_OP_COLLECT, 883 XPATH_OP_VALUE, /* 12 */ 884 XPATH_OP_VARIABLE, 885 XPATH_OP_FUNCTION, 886 XPATH_OP_ARG, 887 XPATH_OP_PREDICATE, 888 XPATH_OP_FILTER, /* 17 */ 889 XPATH_OP_SORT /* 18 */ 890 #ifdef LIBXML_XPTR_ENABLED 891 ,XPATH_OP_RANGETO 892 #endif 893 } xmlXPathOp; 894 895 typedef enum { 896 AXIS_ANCESTOR = 1, 897 AXIS_ANCESTOR_OR_SELF, 898 AXIS_ATTRIBUTE, 899 AXIS_CHILD, 900 AXIS_DESCENDANT, 901 AXIS_DESCENDANT_OR_SELF, 902 AXIS_FOLLOWING, 903 AXIS_FOLLOWING_SIBLING, 904 AXIS_NAMESPACE, 905 AXIS_PARENT, 906 AXIS_PRECEDING, 907 AXIS_PRECEDING_SIBLING, 908 AXIS_SELF 909 } xmlXPathAxisVal; 910 911 typedef enum { 912 NODE_TEST_NONE = 0, 913 NODE_TEST_TYPE = 1, 914 NODE_TEST_PI = 2, 915 NODE_TEST_ALL = 3, 916 NODE_TEST_NS = 4, 917 NODE_TEST_NAME = 5 918 } xmlXPathTestVal; 919 920 typedef enum { 921 NODE_TYPE_NODE = 0, 922 NODE_TYPE_COMMENT = XML_COMMENT_NODE, 923 NODE_TYPE_TEXT = XML_TEXT_NODE, 924 NODE_TYPE_PI = XML_PI_NODE 925 } xmlXPathTypeVal; 926 927 typedef struct _xmlXPathStepOp xmlXPathStepOp; 928 typedef xmlXPathStepOp *xmlXPathStepOpPtr; 929 struct _xmlXPathStepOp { 930 xmlXPathOp op; /* The identifier of the operation */ 931 int ch1; /* First child */ 932 int ch2; /* Second child */ 933 int value; 934 int value2; 935 int value3; 936 void *value4; 937 void *value5; 938 void *cache; 939 void *cacheURI; 940 }; 941 942 struct _xmlXPathCompExpr { 943 int nbStep; /* Number of steps in this expression */ 944 int maxStep; /* Maximum number of steps allocated */ 945 xmlXPathStepOp *steps; /* ops for computation of this expression */ 946 int last; /* index of last step in expression */ 947 xmlChar *expr; /* the expression being computed */ 948 xmlDictPtr dict; /* the dictionnary to use if any */ 949 #ifdef DEBUG_EVAL_COUNTS 950 int nb; 951 xmlChar *string; 952 #endif 953 #ifdef XPATH_STREAMING 954 xmlPatternPtr stream; 955 #endif 956 }; 957 958 /************************************************************************ 959 * * 960 * Forward declarations * 961 * * 962 ************************************************************************/ 963 static void 964 xmlXPathFreeValueTree(xmlNodeSetPtr obj); 965 static void 966 xmlXPathReleaseObject(xmlXPathContextPtr ctxt, xmlXPathObjectPtr obj); 967 static int 968 xmlXPathCompOpEvalFirst(xmlXPathParserContextPtr ctxt, 969 xmlXPathStepOpPtr op, xmlNodePtr *first); 970 static int 971 xmlXPathCompOpEvalToBoolean(xmlXPathParserContextPtr ctxt, 972 xmlXPathStepOpPtr op, 973 int isPredicate); 974 975 /************************************************************************ 976 * * 977 * Parser Type functions * 978 * * 979 ************************************************************************/ 980 981 /** 982 * xmlXPathNewCompExpr: 983 * 984 * Create a new Xpath component 985 * 986 * Returns the newly allocated xmlXPathCompExprPtr or NULL in case of error 987 */ 988 static xmlXPathCompExprPtr 989 xmlXPathNewCompExpr(void) { 990 xmlXPathCompExprPtr cur; 991 992 cur = (xmlXPathCompExprPtr) xmlMalloc(sizeof(xmlXPathCompExpr)); 993 if (cur == NULL) { 994 xmlXPathErrMemory(NULL, "allocating component\n"); 995 return(NULL); 996 } 997 memset(cur, 0, sizeof(xmlXPathCompExpr)); 998 cur->maxStep = 10; 999 cur->nbStep = 0; 1000 cur->steps = (xmlXPathStepOp *) xmlMalloc(cur->maxStep * 1001 sizeof(xmlXPathStepOp)); 1002 if (cur->steps == NULL) { 1003 xmlXPathErrMemory(NULL, "allocating steps\n"); 1004 xmlFree(cur); 1005 return(NULL); 1006 } 1007 memset(cur->steps, 0, cur->maxStep * sizeof(xmlXPathStepOp)); 1008 cur->last = -1; 1009 #ifdef DEBUG_EVAL_COUNTS 1010 cur->nb = 0; 1011 #endif 1012 return(cur); 1013 } 1014 1015 /** 1016 * xmlXPathFreeCompExpr: 1017 * @comp: an XPATH comp 1018 * 1019 * Free up the memory allocated by @comp 1020 */ 1021 void 1022 xmlXPathFreeCompExpr(xmlXPathCompExprPtr comp) 1023 { 1024 xmlXPathStepOpPtr op; 1025 int i; 1026 1027 if (comp == NULL) 1028 return; 1029 if (comp->dict == NULL) { 1030 for (i = 0; i < comp->nbStep; i++) { 1031 op = &comp->steps[i]; 1032 if (op->value4 != NULL) { 1033 if (op->op == XPATH_OP_VALUE) 1034 xmlXPathFreeObject(op->value4); 1035 else 1036 xmlFree(op->value4); 1037 } 1038 if (op->value5 != NULL) 1039 xmlFree(op->value5); 1040 } 1041 } else { 1042 for (i = 0; i < comp->nbStep; i++) { 1043 op = &comp->steps[i]; 1044 if (op->value4 != NULL) { 1045 if (op->op == XPATH_OP_VALUE) 1046 xmlXPathFreeObject(op->value4); 1047 } 1048 } 1049 xmlDictFree(comp->dict); 1050 } 1051 if (comp->steps != NULL) { 1052 xmlFree(comp->steps); 1053 } 1054 #ifdef DEBUG_EVAL_COUNTS 1055 if (comp->string != NULL) { 1056 xmlFree(comp->string); 1057 } 1058 #endif 1059 #ifdef XPATH_STREAMING 1060 if (comp->stream != NULL) { 1061 xmlFreePatternList(comp->stream); 1062 } 1063 #endif 1064 if (comp->expr != NULL) { 1065 xmlFree(comp->expr); 1066 } 1067 1068 xmlFree(comp); 1069 } 1070 1071 /** 1072 * xmlXPathCompExprAdd: 1073 * @comp: the compiled expression 1074 * @ch1: first child index 1075 * @ch2: second child index 1076 * @op: an op 1077 * @value: the first int value 1078 * @value2: the second int value 1079 * @value3: the third int value 1080 * @value4: the first string value 1081 * @value5: the second string value 1082 * 1083 * Add a step to an XPath Compiled Expression 1084 * 1085 * Returns -1 in case of failure, the index otherwise 1086 */ 1087 static int 1088 xmlXPathCompExprAdd(xmlXPathCompExprPtr comp, int ch1, int ch2, 1089 xmlXPathOp op, int value, 1090 int value2, int value3, void *value4, void *value5) { 1091 if (comp->nbStep >= comp->maxStep) { 1092 xmlXPathStepOp *real; 1093 1094 if (comp->maxStep >= XPATH_MAX_STEPS) { 1095 xmlXPathErrMemory(NULL, "adding step\n"); 1096 return(-1); 1097 } 1098 comp->maxStep *= 2; 1099 real = (xmlXPathStepOp *) xmlRealloc(comp->steps, 1100 comp->maxStep * sizeof(xmlXPathStepOp)); 1101 if (real == NULL) { 1102 comp->maxStep /= 2; 1103 xmlXPathErrMemory(NULL, "adding step\n"); 1104 return(-1); 1105 } 1106 comp->steps = real; 1107 } 1108 comp->last = comp->nbStep; 1109 comp->steps[comp->nbStep].ch1 = ch1; 1110 comp->steps[comp->nbStep].ch2 = ch2; 1111 comp->steps[comp->nbStep].op = op; 1112 comp->steps[comp->nbStep].value = value; 1113 comp->steps[comp->nbStep].value2 = value2; 1114 comp->steps[comp->nbStep].value3 = value3; 1115 if ((comp->dict != NULL) && 1116 ((op == XPATH_OP_FUNCTION) || (op == XPATH_OP_VARIABLE) || 1117 (op == XPATH_OP_COLLECT))) { 1118 if (value4 != NULL) { 1119 comp->steps[comp->nbStep].value4 = (xmlChar *) 1120 (void *)xmlDictLookup(comp->dict, value4, -1); 1121 xmlFree(value4); 1122 } else 1123 comp->steps[comp->nbStep].value4 = NULL; 1124 if (value5 != NULL) { 1125 comp->steps[comp->nbStep].value5 = (xmlChar *) 1126 (void *)xmlDictLookup(comp->dict, value5, -1); 1127 xmlFree(value5); 1128 } else 1129 comp->steps[comp->nbStep].value5 = NULL; 1130 } else { 1131 comp->steps[comp->nbStep].value4 = value4; 1132 comp->steps[comp->nbStep].value5 = value5; 1133 } 1134 comp->steps[comp->nbStep].cache = NULL; 1135 return(comp->nbStep++); 1136 } 1137 1138 /** 1139 * xmlXPathCompSwap: 1140 * @comp: the compiled expression 1141 * @op: operation index 1142 * 1143 * Swaps 2 operations in the compiled expression 1144 */ 1145 static void 1146 xmlXPathCompSwap(xmlXPathStepOpPtr op) { 1147 int tmp; 1148 1149 #ifndef LIBXML_THREAD_ENABLED 1150 /* 1151 * Since this manipulates possibly shared variables, this is 1152 * disabled if one detects that the library is used in a multithreaded 1153 * application 1154 */ 1155 if (xmlXPathDisableOptimizer) 1156 return; 1157 #endif 1158 1159 tmp = op->ch1; 1160 op->ch1 = op->ch2; 1161 op->ch2 = tmp; 1162 } 1163 1164 #define PUSH_FULL_EXPR(op, op1, op2, val, val2, val3, val4, val5) \ 1165 xmlXPathCompExprAdd(ctxt->comp, (op1), (op2), \ 1166 (op), (val), (val2), (val3), (val4), (val5)) 1167 #define PUSH_LONG_EXPR(op, val, val2, val3, val4, val5) \ 1168 xmlXPathCompExprAdd(ctxt->comp, ctxt->comp->last, -1, \ 1169 (op), (val), (val2), (val3), (val4), (val5)) 1170 1171 #define PUSH_LEAVE_EXPR(op, val, val2) \ 1172 xmlXPathCompExprAdd(ctxt->comp, -1, -1, (op), (val), (val2), 0 ,NULL ,NULL) 1173 1174 #define PUSH_UNARY_EXPR(op, ch, val, val2) \ 1175 xmlXPathCompExprAdd(ctxt->comp, (ch), -1, (op), (val), (val2), 0 ,NULL ,NULL) 1176 1177 #define PUSH_BINARY_EXPR(op, ch1, ch2, val, val2) \ 1178 xmlXPathCompExprAdd(ctxt->comp, (ch1), (ch2), (op), \ 1179 (val), (val2), 0 ,NULL ,NULL) 1180 1181 /************************************************************************ 1182 * * 1183 * XPath object cache structures * 1184 * * 1185 ************************************************************************/ 1186 1187 /* #define XP_DEFAULT_CACHE_ON */ 1188 1189 #define XP_HAS_CACHE(c) ((c != NULL) && ((c)->cache != NULL)) 1190 1191 typedef struct _xmlXPathContextCache xmlXPathContextCache; 1192 typedef xmlXPathContextCache *xmlXPathContextCachePtr; 1193 struct _xmlXPathContextCache { 1194 xmlPointerListPtr nodesetObjs; /* contains xmlXPathObjectPtr */ 1195 xmlPointerListPtr stringObjs; /* contains xmlXPathObjectPtr */ 1196 xmlPointerListPtr booleanObjs; /* contains xmlXPathObjectPtr */ 1197 xmlPointerListPtr numberObjs; /* contains xmlXPathObjectPtr */ 1198 xmlPointerListPtr miscObjs; /* contains xmlXPathObjectPtr */ 1199 int maxNodeset; 1200 int maxString; 1201 int maxBoolean; 1202 int maxNumber; 1203 int maxMisc; 1204 #ifdef XP_DEBUG_OBJ_USAGE 1205 int dbgCachedAll; 1206 int dbgCachedNodeset; 1207 int dbgCachedString; 1208 int dbgCachedBool; 1209 int dbgCachedNumber; 1210 int dbgCachedPoint; 1211 int dbgCachedRange; 1212 int dbgCachedLocset; 1213 int dbgCachedUsers; 1214 int dbgCachedXSLTTree; 1215 int dbgCachedUndefined; 1216 1217 1218 int dbgReusedAll; 1219 int dbgReusedNodeset; 1220 int dbgReusedString; 1221 int dbgReusedBool; 1222 int dbgReusedNumber; 1223 int dbgReusedPoint; 1224 int dbgReusedRange; 1225 int dbgReusedLocset; 1226 int dbgReusedUsers; 1227 int dbgReusedXSLTTree; 1228 int dbgReusedUndefined; 1229 1230 #endif 1231 }; 1232 1233 /************************************************************************ 1234 * * 1235 * Debugging related functions * 1236 * * 1237 ************************************************************************/ 1238 1239 #define STRANGE \ 1240 xmlGenericError(xmlGenericErrorContext, \ 1241 "Internal error at %s:%d\n", \ 1242 __FILE__, __LINE__); 1243 1244 #ifdef LIBXML_DEBUG_ENABLED 1245 static void 1246 xmlXPathDebugDumpNode(FILE *output, xmlNodePtr cur, int depth) { 1247 int i; 1248 char shift[100]; 1249 1250 for (i = 0;((i < depth) && (i < 25));i++) 1251 shift[2 * i] = shift[2 * i + 1] = ' '; 1252 shift[2 * i] = shift[2 * i + 1] = 0; 1253 if (cur == NULL) { 1254 fprintf(output, "%s", shift); 1255 fprintf(output, "Node is NULL !\n"); 1256 return; 1257 1258 } 1259 1260 if ((cur->type == XML_DOCUMENT_NODE) || 1261 (cur->type == XML_HTML_DOCUMENT_NODE)) { 1262 fprintf(output, "%s", shift); 1263 fprintf(output, " /\n"); 1264 } else if (cur->type == XML_ATTRIBUTE_NODE) 1265 xmlDebugDumpAttr(output, (xmlAttrPtr)cur, depth); 1266 else 1267 xmlDebugDumpOneNode(output, cur, depth); 1268 } 1269 static void 1270 xmlXPathDebugDumpNodeList(FILE *output, xmlNodePtr cur, int depth) { 1271 xmlNodePtr tmp; 1272 int i; 1273 char shift[100]; 1274 1275 for (i = 0;((i < depth) && (i < 25));i++) 1276 shift[2 * i] = shift[2 * i + 1] = ' '; 1277 shift[2 * i] = shift[2 * i + 1] = 0; 1278 if (cur == NULL) { 1279 fprintf(output, "%s", shift); 1280 fprintf(output, "Node is NULL !\n"); 1281 return; 1282 1283 } 1284 1285 while (cur != NULL) { 1286 tmp = cur; 1287 cur = cur->next; 1288 xmlDebugDumpOneNode(output, tmp, depth); 1289 } 1290 } 1291 1292 static void 1293 xmlXPathDebugDumpNodeSet(FILE *output, xmlNodeSetPtr cur, int depth) { 1294 int i; 1295 char shift[100]; 1296 1297 for (i = 0;((i < depth) && (i < 25));i++) 1298 shift[2 * i] = shift[2 * i + 1] = ' '; 1299 shift[2 * i] = shift[2 * i + 1] = 0; 1300 1301 if (cur == NULL) { 1302 fprintf(output, "%s", shift); 1303 fprintf(output, "NodeSet is NULL !\n"); 1304 return; 1305 1306 } 1307 1308 if (cur != NULL) { 1309 fprintf(output, "Set contains %d nodes:\n", cur->nodeNr); 1310 for (i = 0;i < cur->nodeNr;i++) { 1311 fprintf(output, "%s", shift); 1312 fprintf(output, "%d", i + 1); 1313 xmlXPathDebugDumpNode(output, cur->nodeTab[i], depth + 1); 1314 } 1315 } 1316 } 1317 1318 static void 1319 xmlXPathDebugDumpValueTree(FILE *output, xmlNodeSetPtr cur, int depth) { 1320 int i; 1321 char shift[100]; 1322 1323 for (i = 0;((i < depth) && (i < 25));i++) 1324 shift[2 * i] = shift[2 * i + 1] = ' '; 1325 shift[2 * i] = shift[2 * i + 1] = 0; 1326 1327 if ((cur == NULL) || (cur->nodeNr == 0) || (cur->nodeTab[0] == NULL)) { 1328 fprintf(output, "%s", shift); 1329 fprintf(output, "Value Tree is NULL !\n"); 1330 return; 1331 1332 } 1333 1334 fprintf(output, "%s", shift); 1335 fprintf(output, "%d", i + 1); 1336 xmlXPathDebugDumpNodeList(output, cur->nodeTab[0]->children, depth + 1); 1337 } 1338 #if defined(LIBXML_XPTR_ENABLED) 1339 static void 1340 xmlXPathDebugDumpLocationSet(FILE *output, xmlLocationSetPtr cur, int depth) { 1341 int i; 1342 char shift[100]; 1343 1344 for (i = 0;((i < depth) && (i < 25));i++) 1345 shift[2 * i] = shift[2 * i + 1] = ' '; 1346 shift[2 * i] = shift[2 * i + 1] = 0; 1347 1348 if (cur == NULL) { 1349 fprintf(output, "%s", shift); 1350 fprintf(output, "LocationSet is NULL !\n"); 1351 return; 1352 1353 } 1354 1355 for (i = 0;i < cur->locNr;i++) { 1356 fprintf(output, "%s", shift); 1357 fprintf(output, "%d : ", i + 1); 1358 xmlXPathDebugDumpObject(output, cur->locTab[i], depth + 1); 1359 } 1360 } 1361 #endif /* LIBXML_XPTR_ENABLED */ 1362 1363 /** 1364 * xmlXPathDebugDumpObject: 1365 * @output: the FILE * to dump the output 1366 * @cur: the object to inspect 1367 * @depth: indentation level 1368 * 1369 * Dump the content of the object for debugging purposes 1370 */ 1371 void 1372 xmlXPathDebugDumpObject(FILE *output, xmlXPathObjectPtr cur, int depth) { 1373 int i; 1374 char shift[100]; 1375 1376 if (output == NULL) return; 1377 1378 for (i = 0;((i < depth) && (i < 25));i++) 1379 shift[2 * i] = shift[2 * i + 1] = ' '; 1380 shift[2 * i] = shift[2 * i + 1] = 0; 1381 1382 1383 fprintf(output, "%s", shift); 1384 1385 if (cur == NULL) { 1386 fprintf(output, "Object is empty (NULL)\n"); 1387 return; 1388 } 1389 switch(cur->type) { 1390 case XPATH_UNDEFINED: 1391 fprintf(output, "Object is uninitialized\n"); 1392 break; 1393 case XPATH_NODESET: 1394 fprintf(output, "Object is a Node Set :\n"); 1395 xmlXPathDebugDumpNodeSet(output, cur->nodesetval, depth); 1396 break; 1397 case XPATH_XSLT_TREE: 1398 fprintf(output, "Object is an XSLT value tree :\n"); 1399 xmlXPathDebugDumpValueTree(output, cur->nodesetval, depth); 1400 break; 1401 case XPATH_BOOLEAN: 1402 fprintf(output, "Object is a Boolean : "); 1403 if (cur->boolval) fprintf(output, "true\n"); 1404 else fprintf(output, "false\n"); 1405 break; 1406 case XPATH_NUMBER: 1407 switch (xmlXPathIsInf(cur->floatval)) { 1408 case 1: 1409 fprintf(output, "Object is a number : Infinity\n"); 1410 break; 1411 case -1: 1412 fprintf(output, "Object is a number : -Infinity\n"); 1413 break; 1414 default: 1415 if (xmlXPathIsNaN(cur->floatval)) { 1416 fprintf(output, "Object is a number : NaN\n"); 1417 } else if (cur->floatval == 0 && xmlXPathGetSign(cur->floatval) != 0) { 1418 fprintf(output, "Object is a number : 0\n"); 1419 } else { 1420 fprintf(output, "Object is a number : %0g\n", cur->floatval); 1421 } 1422 } 1423 break; 1424 case XPATH_STRING: 1425 fprintf(output, "Object is a string : "); 1426 xmlDebugDumpString(output, cur->stringval); 1427 fprintf(output, "\n"); 1428 break; 1429 case XPATH_POINT: 1430 fprintf(output, "Object is a point : index %d in node", cur->index); 1431 xmlXPathDebugDumpNode(output, (xmlNodePtr) cur->user, depth + 1); 1432 fprintf(output, "\n"); 1433 break; 1434 case XPATH_RANGE: 1435 if ((cur->user2 == NULL) || 1436 ((cur->user2 == cur->user) && (cur->index == cur->index2))) { 1437 fprintf(output, "Object is a collapsed range :\n"); 1438 fprintf(output, "%s", shift); 1439 if (cur->index >= 0) 1440 fprintf(output, "index %d in ", cur->index); 1441 fprintf(output, "node\n"); 1442 xmlXPathDebugDumpNode(output, (xmlNodePtr) cur->user, 1443 depth + 1); 1444 } else { 1445 fprintf(output, "Object is a range :\n"); 1446 fprintf(output, "%s", shift); 1447 fprintf(output, "From "); 1448 if (cur->index >= 0) 1449 fprintf(output, "index %d in ", cur->index); 1450 fprintf(output, "node\n"); 1451 xmlXPathDebugDumpNode(output, (xmlNodePtr) cur->user, 1452 depth + 1); 1453 fprintf(output, "%s", shift); 1454 fprintf(output, "To "); 1455 if (cur->index2 >= 0) 1456 fprintf(output, "index %d in ", cur->index2); 1457 fprintf(output, "node\n"); 1458 xmlXPathDebugDumpNode(output, (xmlNodePtr) cur->user2, 1459 depth + 1); 1460 fprintf(output, "\n"); 1461 } 1462 break; 1463 case XPATH_LOCATIONSET: 1464 #if defined(LIBXML_XPTR_ENABLED) 1465 fprintf(output, "Object is a Location Set:\n"); 1466 xmlXPathDebugDumpLocationSet(output, 1467 (xmlLocationSetPtr) cur->user, depth); 1468 #endif 1469 break; 1470 case XPATH_USERS: 1471 fprintf(output, "Object is user defined\n"); 1472 break; 1473 } 1474 } 1475 1476 static void 1477 xmlXPathDebugDumpStepOp(FILE *output, xmlXPathCompExprPtr comp, 1478 xmlXPathStepOpPtr op, int depth) { 1479 int i; 1480 char shift[100]; 1481 1482 for (i = 0;((i < depth) && (i < 25));i++) 1483 shift[2 * i] = shift[2 * i + 1] = ' '; 1484 shift[2 * i] = shift[2 * i + 1] = 0; 1485 1486 fprintf(output, "%s", shift); 1487 if (op == NULL) { 1488 fprintf(output, "Step is NULL\n"); 1489 return; 1490 } 1491 switch (op->op) { 1492 case XPATH_OP_END: 1493 fprintf(output, "END"); break; 1494 case XPATH_OP_AND: 1495 fprintf(output, "AND"); break; 1496 case XPATH_OP_OR: 1497 fprintf(output, "OR"); break; 1498 case XPATH_OP_EQUAL: 1499 if (op->value) 1500 fprintf(output, "EQUAL ="); 1501 else 1502 fprintf(output, "EQUAL !="); 1503 break; 1504 case XPATH_OP_CMP: 1505 if (op->value) 1506 fprintf(output, "CMP <"); 1507 else 1508 fprintf(output, "CMP >"); 1509 if (!op->value2) 1510 fprintf(output, "="); 1511 break; 1512 case XPATH_OP_PLUS: 1513 if (op->value == 0) 1514 fprintf(output, "PLUS -"); 1515 else if (op->value == 1) 1516 fprintf(output, "PLUS +"); 1517 else if (op->value == 2) 1518 fprintf(output, "PLUS unary -"); 1519 else if (op->value == 3) 1520 fprintf(output, "PLUS unary - -"); 1521 break; 1522 case XPATH_OP_MULT: 1523 if (op->value == 0) 1524 fprintf(output, "MULT *"); 1525 else if (op->value == 1) 1526 fprintf(output, "MULT div"); 1527 else 1528 fprintf(output, "MULT mod"); 1529 break; 1530 case XPATH_OP_UNION: 1531 fprintf(output, "UNION"); break; 1532 case XPATH_OP_ROOT: 1533 fprintf(output, "ROOT"); break; 1534 case XPATH_OP_NODE: 1535 fprintf(output, "NODE"); break; 1536 case XPATH_OP_RESET: 1537 fprintf(output, "RESET"); break; 1538 case XPATH_OP_SORT: 1539 fprintf(output, "SORT"); break; 1540 case XPATH_OP_COLLECT: { 1541 xmlXPathAxisVal axis = (xmlXPathAxisVal)op->value; 1542 xmlXPathTestVal test = (xmlXPathTestVal)op->value2; 1543 xmlXPathTypeVal type = (xmlXPathTypeVal)op->value3; 1544 const xmlChar *prefix = op->value4; 1545 const xmlChar *name = op->value5; 1546 1547 fprintf(output, "COLLECT "); 1548 switch (axis) { 1549 case AXIS_ANCESTOR: 1550 fprintf(output, " 'ancestors' "); break; 1551 case AXIS_ANCESTOR_OR_SELF: 1552 fprintf(output, " 'ancestors-or-self' "); break; 1553 case AXIS_ATTRIBUTE: 1554 fprintf(output, " 'attributes' "); break; 1555 case AXIS_CHILD: 1556 fprintf(output, " 'child' "); break; 1557 case AXIS_DESCENDANT: 1558 fprintf(output, " 'descendant' "); break; 1559 case AXIS_DESCENDANT_OR_SELF: 1560 fprintf(output, " 'descendant-or-self' "); break; 1561 case AXIS_FOLLOWING: 1562 fprintf(output, " 'following' "); break; 1563 case AXIS_FOLLOWING_SIBLING: 1564 fprintf(output, " 'following-siblings' "); break; 1565 case AXIS_NAMESPACE: 1566 fprintf(output, " 'namespace' "); break; 1567 case AXIS_PARENT: 1568 fprintf(output, " 'parent' "); break; 1569 case AXIS_PRECEDING: 1570 fprintf(output, " 'preceding' "); break; 1571 case AXIS_PRECEDING_SIBLING: 1572 fprintf(output, " 'preceding-sibling' "); break; 1573 case AXIS_SELF: 1574 fprintf(output, " 'self' "); break; 1575 } 1576 switch (test) { 1577 case NODE_TEST_NONE: 1578 fprintf(output, "'none' "); break; 1579 case NODE_TEST_TYPE: 1580 fprintf(output, "'type' "); break; 1581 case NODE_TEST_PI: 1582 fprintf(output, "'PI' "); break; 1583 case NODE_TEST_ALL: 1584 fprintf(output, "'all' "); break; 1585 case NODE_TEST_NS: 1586 fprintf(output, "'namespace' "); break; 1587 case NODE_TEST_NAME: 1588 fprintf(output, "'name' "); break; 1589 } 1590 switch (type) { 1591 case NODE_TYPE_NODE: 1592 fprintf(output, "'node' "); break; 1593 case NODE_TYPE_COMMENT: 1594 fprintf(output, "'comment' "); break; 1595 case NODE_TYPE_TEXT: 1596 fprintf(output, "'text' "); break; 1597 case NODE_TYPE_PI: 1598 fprintf(output, "'PI' "); break; 1599 } 1600 if (prefix != NULL) 1601 fprintf(output, "%s:", prefix); 1602 if (name != NULL) 1603 fprintf(output, "%s", (const char *) name); 1604 break; 1605 1606 } 1607 case XPATH_OP_VALUE: { 1608 xmlXPathObjectPtr object = (xmlXPathObjectPtr) op->value4; 1609 1610 fprintf(output, "ELEM "); 1611 xmlXPathDebugDumpObject(output, object, 0); 1612 goto finish; 1613 } 1614 case XPATH_OP_VARIABLE: { 1615 const xmlChar *prefix = op->value5; 1616 const xmlChar *name = op->value4; 1617 1618 if (prefix != NULL) 1619 fprintf(output, "VARIABLE %s:%s", prefix, name); 1620 else 1621 fprintf(output, "VARIABLE %s", name); 1622 break; 1623 } 1624 case XPATH_OP_FUNCTION: { 1625 int nbargs = op->value; 1626 const xmlChar *prefix = op->value5; 1627 const xmlChar *name = op->value4; 1628 1629 if (prefix != NULL) 1630 fprintf(output, "FUNCTION %s:%s(%d args)", 1631 prefix, name, nbargs); 1632 else 1633 fprintf(output, "FUNCTION %s(%d args)", name, nbargs); 1634 break; 1635 } 1636 case XPATH_OP_ARG: fprintf(output, "ARG"); break; 1637 case XPATH_OP_PREDICATE: fprintf(output, "PREDICATE"); break; 1638 case XPATH_OP_FILTER: fprintf(output, "FILTER"); break; 1639 #ifdef LIBXML_XPTR_ENABLED 1640 case XPATH_OP_RANGETO: fprintf(output, "RANGETO"); break; 1641 #endif 1642 default: 1643 fprintf(output, "UNKNOWN %d\n", op->op); return; 1644 } 1645 fprintf(output, "\n"); 1646 finish: 1647 if (op->ch1 >= 0) 1648 xmlXPathDebugDumpStepOp(output, comp, &comp->steps[op->ch1], depth + 1); 1649 if (op->ch2 >= 0) 1650 xmlXPathDebugDumpStepOp(output, comp, &comp->steps[op->ch2], depth + 1); 1651 } 1652 1653 /** 1654 * xmlXPathDebugDumpCompExpr: 1655 * @output: the FILE * for the output 1656 * @comp: the precompiled XPath expression 1657 * @depth: the indentation level. 1658 * 1659 * Dumps the tree of the compiled XPath expression. 1660 */ 1661 void 1662 xmlXPathDebugDumpCompExpr(FILE *output, xmlXPathCompExprPtr comp, 1663 int depth) { 1664 int i; 1665 char shift[100]; 1666 1667 if ((output == NULL) || (comp == NULL)) return; 1668 1669 for (i = 0;((i < depth) && (i < 25));i++) 1670 shift[2 * i] = shift[2 * i + 1] = ' '; 1671 shift[2 * i] = shift[2 * i + 1] = 0; 1672 1673 fprintf(output, "%s", shift); 1674 1675 fprintf(output, "Compiled Expression : %d elements\n", 1676 comp->nbStep); 1677 i = comp->last; 1678 xmlXPathDebugDumpStepOp(output, comp, &comp->steps[i], depth + 1); 1679 } 1680 1681 #ifdef XP_DEBUG_OBJ_USAGE 1682 1683 /* 1684 * XPath object usage related debugging variables. 1685 */ 1686 static int xmlXPathDebugObjCounterUndefined = 0; 1687 static int xmlXPathDebugObjCounterNodeset = 0; 1688 static int xmlXPathDebugObjCounterBool = 0; 1689 static int xmlXPathDebugObjCounterNumber = 0; 1690 static int xmlXPathDebugObjCounterString = 0; 1691 static int xmlXPathDebugObjCounterPoint = 0; 1692 static int xmlXPathDebugObjCounterRange = 0; 1693 static int xmlXPathDebugObjCounterLocset = 0; 1694 static int xmlXPathDebugObjCounterUsers = 0; 1695 static int xmlXPathDebugObjCounterXSLTTree = 0; 1696 static int xmlXPathDebugObjCounterAll = 0; 1697 1698 static int xmlXPathDebugObjTotalUndefined = 0; 1699 static int xmlXPathDebugObjTotalNodeset = 0; 1700 static int xmlXPathDebugObjTotalBool = 0; 1701 static int xmlXPathDebugObjTotalNumber = 0; 1702 static int xmlXPathDebugObjTotalString = 0; 1703 static int xmlXPathDebugObjTotalPoint = 0; 1704 static int xmlXPathDebugObjTotalRange = 0; 1705 static int xmlXPathDebugObjTotalLocset = 0; 1706 static int xmlXPathDebugObjTotalUsers = 0; 1707 static int xmlXPathDebugObjTotalXSLTTree = 0; 1708 static int xmlXPathDebugObjTotalAll = 0; 1709 1710 static int xmlXPathDebugObjMaxUndefined = 0; 1711 static int xmlXPathDebugObjMaxNodeset = 0; 1712 static int xmlXPathDebugObjMaxBool = 0; 1713 static int xmlXPathDebugObjMaxNumber = 0; 1714 static int xmlXPathDebugObjMaxString = 0; 1715 static int xmlXPathDebugObjMaxPoint = 0; 1716 static int xmlXPathDebugObjMaxRange = 0; 1717 static int xmlXPathDebugObjMaxLocset = 0; 1718 static int xmlXPathDebugObjMaxUsers = 0; 1719 static int xmlXPathDebugObjMaxXSLTTree = 0; 1720 static int xmlXPathDebugObjMaxAll = 0; 1721 1722 /* REVISIT TODO: Make this static when committing */ 1723 static void 1724 xmlXPathDebugObjUsageReset(xmlXPathContextPtr ctxt) 1725 { 1726 if (ctxt != NULL) { 1727 if (ctxt->cache != NULL) { 1728 xmlXPathContextCachePtr cache = 1729 (xmlXPathContextCachePtr) ctxt->cache; 1730 1731 cache->dbgCachedAll = 0; 1732 cache->dbgCachedNodeset = 0; 1733 cache->dbgCachedString = 0; 1734 cache->dbgCachedBool = 0; 1735 cache->dbgCachedNumber = 0; 1736 cache->dbgCachedPoint = 0; 1737 cache->dbgCachedRange = 0; 1738 cache->dbgCachedLocset = 0; 1739 cache->dbgCachedUsers = 0; 1740 cache->dbgCachedXSLTTree = 0; 1741 cache->dbgCachedUndefined = 0; 1742 1743 cache->dbgReusedAll = 0; 1744 cache->dbgReusedNodeset = 0; 1745 cache->dbgReusedString = 0; 1746 cache->dbgReusedBool = 0; 1747 cache->dbgReusedNumber = 0; 1748 cache->dbgReusedPoint = 0; 1749 cache->dbgReusedRange = 0; 1750 cache->dbgReusedLocset = 0; 1751 cache->dbgReusedUsers = 0; 1752 cache->dbgReusedXSLTTree = 0; 1753 cache->dbgReusedUndefined = 0; 1754 } 1755 } 1756 1757 xmlXPathDebugObjCounterUndefined = 0; 1758 xmlXPathDebugObjCounterNodeset = 0; 1759 xmlXPathDebugObjCounterBool = 0; 1760 xmlXPathDebugObjCounterNumber = 0; 1761 xmlXPathDebugObjCounterString = 0; 1762 xmlXPathDebugObjCounterPoint = 0; 1763 xmlXPathDebugObjCounterRange = 0; 1764 xmlXPathDebugObjCounterLocset = 0; 1765 xmlXPathDebugObjCounterUsers = 0; 1766 xmlXPathDebugObjCounterXSLTTree = 0; 1767 xmlXPathDebugObjCounterAll = 0; 1768 1769 xmlXPathDebugObjTotalUndefined = 0; 1770 xmlXPathDebugObjTotalNodeset = 0; 1771 xmlXPathDebugObjTotalBool = 0; 1772 xmlXPathDebugObjTotalNumber = 0; 1773 xmlXPathDebugObjTotalString = 0; 1774 xmlXPathDebugObjTotalPoint = 0; 1775 xmlXPathDebugObjTotalRange = 0; 1776 xmlXPathDebugObjTotalLocset = 0; 1777 xmlXPathDebugObjTotalUsers = 0; 1778 xmlXPathDebugObjTotalXSLTTree = 0; 1779 xmlXPathDebugObjTotalAll = 0; 1780 1781 xmlXPathDebugObjMaxUndefined = 0; 1782 xmlXPathDebugObjMaxNodeset = 0; 1783 xmlXPathDebugObjMaxBool = 0; 1784 xmlXPathDebugObjMaxNumber = 0; 1785 xmlXPathDebugObjMaxString = 0; 1786 xmlXPathDebugObjMaxPoint = 0; 1787 xmlXPathDebugObjMaxRange = 0; 1788 xmlXPathDebugObjMaxLocset = 0; 1789 xmlXPathDebugObjMaxUsers = 0; 1790 xmlXPathDebugObjMaxXSLTTree = 0; 1791 xmlXPathDebugObjMaxAll = 0; 1792 1793 } 1794 1795 static void 1796 xmlXPathDebugObjUsageRequested(xmlXPathContextPtr ctxt, 1797 xmlXPathObjectType objType) 1798 { 1799 int isCached = 0; 1800 1801 if (ctxt != NULL) { 1802 if (ctxt->cache != NULL) { 1803 xmlXPathContextCachePtr cache = 1804 (xmlXPathContextCachePtr) ctxt->cache; 1805 1806 isCached = 1; 1807 1808 cache->dbgReusedAll++; 1809 switch (objType) { 1810 case XPATH_UNDEFINED: 1811 cache->dbgReusedUndefined++; 1812 break; 1813 case XPATH_NODESET: 1814 cache->dbgReusedNodeset++; 1815 break; 1816 case XPATH_BOOLEAN: 1817 cache->dbgReusedBool++; 1818 break; 1819 case XPATH_NUMBER: 1820 cache->dbgReusedNumber++; 1821 break; 1822 case XPATH_STRING: 1823 cache->dbgReusedString++; 1824 break; 1825 case XPATH_POINT: 1826 cache->dbgReusedPoint++; 1827 break; 1828 case XPATH_RANGE: 1829 cache->dbgReusedRange++; 1830 break; 1831 case XPATH_LOCATIONSET: 1832 cache->dbgReusedLocset++; 1833 break; 1834 case XPATH_USERS: 1835 cache->dbgReusedUsers++; 1836 break; 1837 case XPATH_XSLT_TREE: 1838 cache->dbgReusedXSLTTree++; 1839 break; 1840 default: 1841 break; 1842 } 1843 } 1844 } 1845 1846 switch (objType) { 1847 case XPATH_UNDEFINED: 1848 if (! isCached) 1849 xmlXPathDebugObjTotalUndefined++; 1850 xmlXPathDebugObjCounterUndefined++; 1851 if (xmlXPathDebugObjCounterUndefined > 1852 xmlXPathDebugObjMaxUndefined) 1853 xmlXPathDebugObjMaxUndefined = 1854 xmlXPathDebugObjCounterUndefined; 1855 break; 1856 case XPATH_NODESET: 1857 if (! isCached) 1858 xmlXPathDebugObjTotalNodeset++; 1859 xmlXPathDebugObjCounterNodeset++; 1860 if (xmlXPathDebugObjCounterNodeset > 1861 xmlXPathDebugObjMaxNodeset) 1862 xmlXPathDebugObjMaxNodeset = 1863 xmlXPathDebugObjCounterNodeset; 1864 break; 1865 case XPATH_BOOLEAN: 1866 if (! isCached) 1867 xmlXPathDebugObjTotalBool++; 1868 xmlXPathDebugObjCounterBool++; 1869 if (xmlXPathDebugObjCounterBool > 1870 xmlXPathDebugObjMaxBool) 1871 xmlXPathDebugObjMaxBool = 1872 xmlXPathDebugObjCounterBool; 1873 break; 1874 case XPATH_NUMBER: 1875 if (! isCached) 1876 xmlXPathDebugObjTotalNumber++; 1877 xmlXPathDebugObjCounterNumber++; 1878 if (xmlXPathDebugObjCounterNumber > 1879 xmlXPathDebugObjMaxNumber) 1880 xmlXPathDebugObjMaxNumber = 1881 xmlXPathDebugObjCounterNumber; 1882 break; 1883 case XPATH_STRING: 1884 if (! isCached) 1885 xmlXPathDebugObjTotalString++; 1886 xmlXPathDebugObjCounterString++; 1887 if (xmlXPathDebugObjCounterString > 1888 xmlXPathDebugObjMaxString) 1889 xmlXPathDebugObjMaxString = 1890 xmlXPathDebugObjCounterString; 1891 break; 1892 case XPATH_POINT: 1893 if (! isCached) 1894 xmlXPathDebugObjTotalPoint++; 1895 xmlXPathDebugObjCounterPoint++; 1896 if (xmlXPathDebugObjCounterPoint > 1897 xmlXPathDebugObjMaxPoint) 1898 xmlXPathDebugObjMaxPoint = 1899 xmlXPathDebugObjCounterPoint; 1900 break; 1901 case XPATH_RANGE: 1902 if (! isCached) 1903 xmlXPathDebugObjTotalRange++; 1904 xmlXPathDebugObjCounterRange++; 1905 if (xmlXPathDebugObjCounterRange > 1906 xmlXPathDebugObjMaxRange) 1907 xmlXPathDebugObjMaxRange = 1908 xmlXPathDebugObjCounterRange; 1909 break; 1910 case XPATH_LOCATIONSET: 1911 if (! isCached) 1912 xmlXPathDebugObjTotalLocset++; 1913 xmlXPathDebugObjCounterLocset++; 1914 if (xmlXPathDebugObjCounterLocset > 1915 xmlXPathDebugObjMaxLocset) 1916 xmlXPathDebugObjMaxLocset = 1917 xmlXPathDebugObjCounterLocset; 1918 break; 1919 case XPATH_USERS: 1920 if (! isCached) 1921 xmlXPathDebugObjTotalUsers++; 1922 xmlXPathDebugObjCounterUsers++; 1923 if (xmlXPathDebugObjCounterUsers > 1924 xmlXPathDebugObjMaxUsers) 1925 xmlXPathDebugObjMaxUsers = 1926 xmlXPathDebugObjCounterUsers; 1927 break; 1928 case XPATH_XSLT_TREE: 1929 if (! isCached) 1930 xmlXPathDebugObjTotalXSLTTree++; 1931 xmlXPathDebugObjCounterXSLTTree++; 1932 if (xmlXPathDebugObjCounterXSLTTree > 1933 xmlXPathDebugObjMaxXSLTTree) 1934 xmlXPathDebugObjMaxXSLTTree = 1935 xmlXPathDebugObjCounterXSLTTree; 1936 break; 1937 default: 1938 break; 1939 } 1940 if (! isCached) 1941 xmlXPathDebugObjTotalAll++; 1942 xmlXPathDebugObjCounterAll++; 1943 if (xmlXPathDebugObjCounterAll > 1944 xmlXPathDebugObjMaxAll) 1945 xmlXPathDebugObjMaxAll = 1946 xmlXPathDebugObjCounterAll; 1947 } 1948 1949 static void 1950 xmlXPathDebugObjUsageReleased(xmlXPathContextPtr ctxt, 1951 xmlXPathObjectType objType) 1952 { 1953 int isCached = 0; 1954 1955 if (ctxt != NULL) { 1956 if (ctxt->cache != NULL) { 1957 xmlXPathContextCachePtr cache = 1958 (xmlXPathContextCachePtr) ctxt->cache; 1959 1960 isCached = 1; 1961 1962 cache->dbgCachedAll++; 1963 switch (objType) { 1964 case XPATH_UNDEFINED: 1965 cache->dbgCachedUndefined++; 1966 break; 1967 case XPATH_NODESET: 1968 cache->dbgCachedNodeset++; 1969 break; 1970 case XPATH_BOOLEAN: 1971 cache->dbgCachedBool++; 1972 break; 1973 case XPATH_NUMBER: 1974 cache->dbgCachedNumber++; 1975 break; 1976 case XPATH_STRING: 1977 cache->dbgCachedString++; 1978 break; 1979 case XPATH_POINT: 1980 cache->dbgCachedPoint++; 1981 break; 1982 case XPATH_RANGE: 1983 cache->dbgCachedRange++; 1984 break; 1985 case XPATH_LOCATIONSET: 1986 cache->dbgCachedLocset++; 1987 break; 1988 case XPATH_USERS: 1989 cache->dbgCachedUsers++; 1990 break; 1991 case XPATH_XSLT_TREE: 1992 cache->dbgCachedXSLTTree++; 1993 break; 1994 default: 1995 break; 1996 } 1997 1998 } 1999 } 2000 switch (objType) { 2001 case XPATH_UNDEFINED: 2002 xmlXPathDebugObjCounterUndefined--; 2003 break; 2004 case XPATH_NODESET: 2005 xmlXPathDebugObjCounterNodeset--; 2006 break; 2007 case XPATH_BOOLEAN: 2008 xmlXPathDebugObjCounterBool--; 2009 break; 2010 case XPATH_NUMBER: 2011 xmlXPathDebugObjCounterNumber--; 2012 break; 2013 case XPATH_STRING: 2014 xmlXPathDebugObjCounterString--; 2015 break; 2016 case XPATH_POINT: 2017 xmlXPathDebugObjCounterPoint--; 2018 break; 2019 case XPATH_RANGE: 2020 xmlXPathDebugObjCounterRange--; 2021 break; 2022 case XPATH_LOCATIONSET: 2023 xmlXPathDebugObjCounterLocset--; 2024 break; 2025 case XPATH_USERS: 2026 xmlXPathDebugObjCounterUsers--; 2027 break; 2028 case XPATH_XSLT_TREE: 2029 xmlXPathDebugObjCounterXSLTTree--; 2030 break; 2031 default: 2032 break; 2033 } 2034 xmlXPathDebugObjCounterAll--; 2035 } 2036 2037 /* REVISIT TODO: Make this static when committing */ 2038 static void 2039 xmlXPathDebugObjUsageDisplay(xmlXPathContextPtr ctxt) 2040 { 2041 int reqAll, reqNodeset, reqString, reqBool, reqNumber, 2042 reqXSLTTree, reqUndefined; 2043 int caAll = 0, caNodeset = 0, caString = 0, caBool = 0, 2044 caNumber = 0, caXSLTTree = 0, caUndefined = 0; 2045 int reAll = 0, reNodeset = 0, reString = 0, reBool = 0, 2046 reNumber = 0, reXSLTTree = 0, reUndefined = 0; 2047 int leftObjs = xmlXPathDebugObjCounterAll; 2048 2049 reqAll = xmlXPathDebugObjTotalAll; 2050 reqNodeset = xmlXPathDebugObjTotalNodeset; 2051 reqString = xmlXPathDebugObjTotalString; 2052 reqBool = xmlXPathDebugObjTotalBool; 2053 reqNumber = xmlXPathDebugObjTotalNumber; 2054 reqXSLTTree = xmlXPathDebugObjTotalXSLTTree; 2055 reqUndefined = xmlXPathDebugObjTotalUndefined; 2056 2057 printf("# XPath object usage:\n"); 2058 2059 if (ctxt != NULL) { 2060 if (ctxt->cache != NULL) { 2061 xmlXPathContextCachePtr cache = 2062 (xmlXPathContextCachePtr) ctxt->cache; 2063 2064 reAll = cache->dbgReusedAll; 2065 reqAll += reAll; 2066 reNodeset = cache->dbgReusedNodeset; 2067 reqNodeset += reNodeset; 2068 reString = cache->dbgReusedString; 2069 reqString += reString; 2070 reBool = cache->dbgReusedBool; 2071 reqBool += reBool; 2072 reNumber = cache->dbgReusedNumber; 2073 reqNumber += reNumber; 2074 reXSLTTree = cache->dbgReusedXSLTTree; 2075 reqXSLTTree += reXSLTTree; 2076 reUndefined = cache->dbgReusedUndefined; 2077 reqUndefined += reUndefined; 2078 2079 caAll = cache->dbgCachedAll; 2080 caBool = cache->dbgCachedBool; 2081 caNodeset = cache->dbgCachedNodeset; 2082 caString = cache->dbgCachedString; 2083 caNumber = cache->dbgCachedNumber; 2084 caXSLTTree = cache->dbgCachedXSLTTree; 2085 caUndefined = cache->dbgCachedUndefined; 2086 2087 if (cache->nodesetObjs) 2088 leftObjs -= cache->nodesetObjs->number; 2089 if (cache->stringObjs) 2090 leftObjs -= cache->stringObjs->number; 2091 if (cache->booleanObjs) 2092 leftObjs -= cache->booleanObjs->number; 2093 if (cache->numberObjs) 2094 leftObjs -= cache->numberObjs->number; 2095 if (cache->miscObjs) 2096 leftObjs -= cache->miscObjs->number; 2097 } 2098 } 2099 2100 printf("# all\n"); 2101 printf("# total : %d\n", reqAll); 2102 printf("# left : %d\n", leftObjs); 2103 printf("# created: %d\n", xmlXPathDebugObjTotalAll); 2104 printf("# reused : %d\n", reAll); 2105 printf("# max : %d\n", xmlXPathDebugObjMaxAll); 2106 2107 printf("# node-sets\n"); 2108 printf("# total : %d\n", reqNodeset); 2109 printf("# created: %d\n", xmlXPathDebugObjTotalNodeset); 2110 printf("# reused : %d\n", reNodeset); 2111 printf("# max : %d\n", xmlXPathDebugObjMaxNodeset); 2112 2113 printf("# strings\n"); 2114 printf("# total : %d\n", reqString); 2115 printf("# created: %d\n", xmlXPathDebugObjTotalString); 2116 printf("# reused : %d\n", reString); 2117 printf("# max : %d\n", xmlXPathDebugObjMaxString); 2118 2119 printf("# booleans\n"); 2120 printf("# total : %d\n", reqBool); 2121 printf("# created: %d\n", xmlXPathDebugObjTotalBool); 2122 printf("# reused : %d\n", reBool); 2123 printf("# max : %d\n", xmlXPathDebugObjMaxBool); 2124 2125 printf("# numbers\n"); 2126 printf("# total : %d\n", reqNumber); 2127 printf("# created: %d\n", xmlXPathDebugObjTotalNumber); 2128 printf("# reused : %d\n", reNumber); 2129 printf("# max : %d\n", xmlXPathDebugObjMaxNumber); 2130 2131 printf("# XSLT result tree fragments\n"); 2132 printf("# total : %d\n", reqXSLTTree); 2133 printf("# created: %d\n", xmlXPathDebugObjTotalXSLTTree); 2134 printf("# reused : %d\n", reXSLTTree); 2135 printf("# max : %d\n", xmlXPathDebugObjMaxXSLTTree); 2136 2137 printf("# undefined\n"); 2138 printf("# total : %d\n", reqUndefined); 2139 printf("# created: %d\n", xmlXPathDebugObjTotalUndefined); 2140 printf("# reused : %d\n", reUndefined); 2141 printf("# max : %d\n", xmlXPathDebugObjMaxUndefined); 2142 2143 } 2144 2145 #endif /* XP_DEBUG_OBJ_USAGE */ 2146 2147 #endif /* LIBXML_DEBUG_ENABLED */ 2148 2149 /************************************************************************ 2150 * * 2151 * XPath object caching * 2152 * * 2153 ************************************************************************/ 2154 2155 /** 2156 * xmlXPathNewCache: 2157 * 2158 * Create a new object cache 2159 * 2160 * Returns the xmlXPathCache just allocated. 2161 */ 2162 static xmlXPathContextCachePtr 2163 xmlXPathNewCache(void) 2164 { 2165 xmlXPathContextCachePtr ret; 2166 2167 ret = (xmlXPathContextCachePtr) xmlMalloc(sizeof(xmlXPathContextCache)); 2168 if (ret == NULL) { 2169 xmlXPathErrMemory(NULL, "creating object cache\n"); 2170 return(NULL); 2171 } 2172 memset(ret, 0 , (size_t) sizeof(xmlXPathContextCache)); 2173 ret->maxNodeset = 100; 2174 ret->maxString = 100; 2175 ret->maxBoolean = 100; 2176 ret->maxNumber = 100; 2177 ret->maxMisc = 100; 2178 return(ret); 2179 } 2180 2181 static void 2182 xmlXPathCacheFreeObjectList(xmlPointerListPtr list) 2183 { 2184 int i; 2185 xmlXPathObjectPtr obj; 2186 2187 if (list == NULL) 2188 return; 2189 2190 for (i = 0; i < list->number; i++) { 2191 obj = list->items[i]; 2192 /* 2193 * Note that it is already assured that we don't need to 2194 * look out for namespace nodes in the node-set. 2195 */ 2196 if (obj->nodesetval != NULL) { 2197 if (obj->nodesetval->nodeTab != NULL) 2198 xmlFree(obj->nodesetval->nodeTab); 2199 xmlFree(obj->nodesetval); 2200 } 2201 xmlFree(obj); 2202 #ifdef XP_DEBUG_OBJ_USAGE 2203 xmlXPathDebugObjCounterAll--; 2204 #endif 2205 } 2206 xmlPointerListFree(list); 2207 } 2208 2209 static void 2210 xmlXPathFreeCache(xmlXPathContextCachePtr cache) 2211 { 2212 if (cache == NULL) 2213 return; 2214 if (cache->nodesetObjs) 2215 xmlXPathCacheFreeObjectList(cache->nodesetObjs); 2216 if (cache->stringObjs) 2217 xmlXPathCacheFreeObjectList(cache->stringObjs); 2218 if (cache->booleanObjs) 2219 xmlXPathCacheFreeObjectList(cache->booleanObjs); 2220 if (cache->numberObjs) 2221 xmlXPathCacheFreeObjectList(cache->numberObjs); 2222 if (cache->miscObjs) 2223 xmlXPathCacheFreeObjectList(cache->miscObjs); 2224 xmlFree(cache); 2225 } 2226 2227 /** 2228 * xmlXPathContextSetCache: 2229 * 2230 * @ctxt: the XPath context 2231 * @active: enables/disables (creates/frees) the cache 2232 * @value: a value with semantics dependant on @options 2233 * @options: options (currently only the value 0 is used) 2234 * 2235 * Creates/frees an object cache on the XPath context. 2236 * If activates XPath objects (xmlXPathObject) will be cached internally 2237 * to be reused. 2238 * @options: 2239 * 0: This will set the XPath object caching: 2240 * @value: 2241 * This will set the maximum number of XPath objects 2242 * to be cached per slot 2243 * There are 5 slots for: node-set, string, number, boolean, and 2244 * misc objects. Use <0 for the default number (100). 2245 * Other values for @options have currently no effect. 2246 * 2247 * Returns 0 if the setting succeeded, and -1 on API or internal errors. 2248 */ 2249 int 2250 xmlXPathContextSetCache(xmlXPathContextPtr ctxt, 2251 int active, 2252 int value, 2253 int options) 2254 { 2255 if (ctxt == NULL) 2256 return(-1); 2257 if (active) { 2258 xmlXPathContextCachePtr cache; 2259 2260 if (ctxt->cache == NULL) { 2261 ctxt->cache = xmlXPathNewCache(); 2262 if (ctxt->cache == NULL) 2263 return(-1); 2264 } 2265 cache = (xmlXPathContextCachePtr) ctxt->cache; 2266 if (options == 0) { 2267 if (value < 0) 2268 value = 100; 2269 cache->maxNodeset = value; 2270 cache->maxString = value; 2271 cache->maxNumber = value; 2272 cache->maxBoolean = value; 2273 cache->maxMisc = value; 2274 } 2275 } else if (ctxt->cache != NULL) { 2276 xmlXPathFreeCache((xmlXPathContextCachePtr) ctxt->cache); 2277 ctxt->cache = NULL; 2278 } 2279 return(0); 2280 } 2281 2282 /** 2283 * xmlXPathCacheWrapNodeSet: 2284 * @ctxt: the XPath context 2285 * @val: the NodePtr value 2286 * 2287 * This is the cached version of xmlXPathWrapNodeSet(). 2288 * Wrap the Nodeset @val in a new xmlXPathObjectPtr 2289 * 2290 * Returns the created or reused object. 2291 */ 2292 static xmlXPathObjectPtr 2293 xmlXPathCacheWrapNodeSet(xmlXPathContextPtr ctxt, xmlNodeSetPtr val) 2294 { 2295 if ((ctxt != NULL) && (ctxt->cache != NULL)) { 2296 xmlXPathContextCachePtr cache = 2297 (xmlXPathContextCachePtr) ctxt->cache; 2298 2299 if ((cache->miscObjs != NULL) && 2300 (cache->miscObjs->number != 0)) 2301 { 2302 xmlXPathObjectPtr ret; 2303 2304 ret = (xmlXPathObjectPtr) 2305 cache->miscObjs->items[--cache->miscObjs->number]; 2306 ret->type = XPATH_NODESET; 2307 ret->nodesetval = val; 2308 #ifdef XP_DEBUG_OBJ_USAGE 2309 xmlXPathDebugObjUsageRequested(ctxt, XPATH_NODESET); 2310 #endif 2311 return(ret); 2312 } 2313 } 2314 2315 return(xmlXPathWrapNodeSet(val)); 2316 2317 } 2318 2319 /** 2320 * xmlXPathCacheWrapString: 2321 * @ctxt: the XPath context 2322 * @val: the xmlChar * value 2323 * 2324 * This is the cached version of xmlXPathWrapString(). 2325 * Wraps the @val string into an XPath object. 2326 * 2327 * Returns the created or reused object. 2328 */ 2329 static xmlXPathObjectPtr 2330 xmlXPathCacheWrapString(xmlXPathContextPtr ctxt, xmlChar *val) 2331 { 2332 if ((ctxt != NULL) && (ctxt->cache != NULL)) { 2333 xmlXPathContextCachePtr cache = (xmlXPathContextCachePtr) ctxt->cache; 2334 2335 if ((cache->stringObjs != NULL) && 2336 (cache->stringObjs->number != 0)) 2337 { 2338 2339 xmlXPathObjectPtr ret; 2340 2341 ret = (xmlXPathObjectPtr) 2342 cache->stringObjs->items[--cache->stringObjs->number]; 2343 ret->type = XPATH_STRING; 2344 ret->stringval = val; 2345 #ifdef XP_DEBUG_OBJ_USAGE 2346 xmlXPathDebugObjUsageRequested(ctxt, XPATH_STRING); 2347 #endif 2348 return(ret); 2349 } else if ((cache->miscObjs != NULL) && 2350 (cache->miscObjs->number != 0)) 2351 { 2352 xmlXPathObjectPtr ret; 2353 /* 2354 * Fallback to misc-cache. 2355 */ 2356 ret = (xmlXPathObjectPtr) 2357 cache->miscObjs->items[--cache->miscObjs->number]; 2358 2359 ret->type = XPATH_STRING; 2360 ret->stringval = val; 2361 #ifdef XP_DEBUG_OBJ_USAGE 2362 xmlXPathDebugObjUsageRequested(ctxt, XPATH_STRING); 2363 #endif 2364 return(ret); 2365 } 2366 } 2367 return(xmlXPathWrapString(val)); 2368 } 2369 2370 /** 2371 * xmlXPathCacheNewNodeSet: 2372 * @ctxt: the XPath context 2373 * @val: the NodePtr value 2374 * 2375 * This is the cached version of xmlXPathNewNodeSet(). 2376 * Acquire an xmlXPathObjectPtr of type NodeSet and initialize 2377 * it with the single Node @val 2378 * 2379 * Returns the created or reused object. 2380 */ 2381 static xmlXPathObjectPtr 2382 xmlXPathCacheNewNodeSet(xmlXPathContextPtr ctxt, xmlNodePtr val) 2383 { 2384 if ((ctxt != NULL) && (ctxt->cache)) { 2385 xmlXPathContextCachePtr cache = (xmlXPathContextCachePtr) ctxt->cache; 2386 2387 if ((cache->nodesetObjs != NULL) && 2388 (cache->nodesetObjs->number != 0)) 2389 { 2390 xmlXPathObjectPtr ret; 2391 /* 2392 * Use the nodset-cache. 2393 */ 2394 ret = (xmlXPathObjectPtr) 2395 cache->nodesetObjs->items[--cache->nodesetObjs->number]; 2396 ret->type = XPATH_NODESET; 2397 ret->boolval = 0; 2398 if (val) { 2399 if ((ret->nodesetval->nodeMax == 0) || 2400 (val->type == XML_NAMESPACE_DECL)) 2401 { 2402 xmlXPathNodeSetAddUnique(ret->nodesetval, val); 2403 } else { 2404 ret->nodesetval->nodeTab[0] = val; 2405 ret->nodesetval->nodeNr = 1; 2406 } 2407 } 2408 #ifdef XP_DEBUG_OBJ_USAGE 2409 xmlXPathDebugObjUsageRequested(ctxt, XPATH_NODESET); 2410 #endif 2411 return(ret); 2412 } else if ((cache->miscObjs != NULL) && 2413 (cache->miscObjs->number != 0)) 2414 { 2415 xmlXPathObjectPtr ret; 2416 /* 2417 * Fallback to misc-cache. 2418 */ 2419 2420 ret = (xmlXPathObjectPtr) 2421 cache->miscObjs->items[--cache->miscObjs->number]; 2422 2423 ret->type = XPATH_NODESET; 2424 ret->boolval = 0; 2425 ret->nodesetval = xmlXPathNodeSetCreate(val); 2426 if (ret->nodesetval == NULL) { 2427 ctxt->lastError.domain = XML_FROM_XPATH; 2428 ctxt->lastError.code = XML_ERR_NO_MEMORY; 2429 return(NULL); 2430 } 2431 #ifdef XP_DEBUG_OBJ_USAGE 2432 xmlXPathDebugObjUsageRequested(ctxt, XPATH_NODESET); 2433 #endif 2434 return(ret); 2435 } 2436 } 2437 return(xmlXPathNewNodeSet(val)); 2438 } 2439 2440 /** 2441 * xmlXPathCacheNewCString: 2442 * @ctxt: the XPath context 2443 * @val: the char * value 2444 * 2445 * This is the cached version of xmlXPathNewCString(). 2446 * Acquire an xmlXPathObjectPtr of type string and of value @val 2447 * 2448 * Returns the created or reused object. 2449 */ 2450 static xmlXPathObjectPtr 2451 xmlXPathCacheNewCString(xmlXPathContextPtr ctxt, const char *val) 2452 { 2453 if ((ctxt != NULL) && (ctxt->cache)) { 2454 xmlXPathContextCachePtr cache = (xmlXPathContextCachePtr) ctxt->cache; 2455 2456 if ((cache->stringObjs != NULL) && 2457 (cache->stringObjs->number != 0)) 2458 { 2459 xmlXPathObjectPtr ret; 2460 2461 ret = (xmlXPathObjectPtr) 2462 cache->stringObjs->items[--cache->stringObjs->number]; 2463 2464 ret->type = XPATH_STRING; 2465 ret->stringval = xmlStrdup(BAD_CAST val); 2466 #ifdef XP_DEBUG_OBJ_USAGE 2467 xmlXPathDebugObjUsageRequested(ctxt, XPATH_STRING); 2468 #endif 2469 return(ret); 2470 } else if ((cache->miscObjs != NULL) && 2471 (cache->miscObjs->number != 0)) 2472 { 2473 xmlXPathObjectPtr ret; 2474 2475 ret = (xmlXPathObjectPtr) 2476 cache->miscObjs->items[--cache->miscObjs->number]; 2477 2478 ret->type = XPATH_STRING; 2479 ret->stringval = xmlStrdup(BAD_CAST val); 2480 #ifdef XP_DEBUG_OBJ_USAGE 2481 xmlXPathDebugObjUsageRequested(ctxt, XPATH_STRING); 2482 #endif 2483 return(ret); 2484 } 2485 } 2486 return(xmlXPathNewCString(val)); 2487 } 2488 2489 /** 2490 * xmlXPathCacheNewString: 2491 * @ctxt: the XPath context 2492 * @val: the xmlChar * value 2493 * 2494 * This is the cached version of xmlXPathNewString(). 2495 * Acquire an xmlXPathObjectPtr of type string and of value @val 2496 * 2497 * Returns the created or reused object. 2498 */ 2499 static xmlXPathObjectPtr 2500 xmlXPathCacheNewString(xmlXPathContextPtr ctxt, const xmlChar *val) 2501 { 2502 if ((ctxt != NULL) && (ctxt->cache)) { 2503 xmlXPathContextCachePtr cache = (xmlXPathContextCachePtr) ctxt->cache; 2504 2505 if ((cache->stringObjs != NULL) && 2506 (cache->stringObjs->number != 0)) 2507 { 2508 xmlXPathObjectPtr ret; 2509 2510 ret = (xmlXPathObjectPtr) 2511 cache->stringObjs->items[--cache->stringObjs->number]; 2512 ret->type = XPATH_STRING; 2513 if (val != NULL) 2514 ret->stringval = xmlStrdup(val); 2515 else 2516 ret->stringval = xmlStrdup((const xmlChar *)""); 2517 #ifdef XP_DEBUG_OBJ_USAGE 2518 xmlXPathDebugObjUsageRequested(ctxt, XPATH_STRING); 2519 #endif 2520 return(ret); 2521 } else if ((cache->miscObjs != NULL) && 2522 (cache->miscObjs->number != 0)) 2523 { 2524 xmlXPathObjectPtr ret; 2525 2526 ret = (xmlXPathObjectPtr) 2527 cache->miscObjs->items[--cache->miscObjs->number]; 2528 2529 ret->type = XPATH_STRING; 2530 if (val != NULL) 2531 ret->stringval = xmlStrdup(val); 2532 else 2533 ret->stringval = xmlStrdup((const xmlChar *)""); 2534 #ifdef XP_DEBUG_OBJ_USAGE 2535 xmlXPathDebugObjUsageRequested(ctxt, XPATH_STRING); 2536 #endif 2537 return(ret); 2538 } 2539 } 2540 return(xmlXPathNewString(val)); 2541 } 2542 2543 /** 2544 * xmlXPathCacheNewBoolean: 2545 * @ctxt: the XPath context 2546 * @val: the boolean value 2547 * 2548 * This is the cached version of xmlXPathNewBoolean(). 2549 * Acquires an xmlXPathObjectPtr of type boolean and of value @val 2550 * 2551 * Returns the created or reused object. 2552 */ 2553 static xmlXPathObjectPtr 2554 xmlXPathCacheNewBoolean(xmlXPathContextPtr ctxt, int val) 2555 { 2556 if ((ctxt != NULL) && (ctxt->cache)) { 2557 xmlXPathContextCachePtr cache = (xmlXPathContextCachePtr) ctxt->cache; 2558 2559 if ((cache->booleanObjs != NULL) && 2560 (cache->booleanObjs->number != 0)) 2561 { 2562 xmlXPathObjectPtr ret; 2563 2564 ret = (xmlXPathObjectPtr) 2565 cache->booleanObjs->items[--cache->booleanObjs->number]; 2566 ret->type = XPATH_BOOLEAN; 2567 ret->boolval = (val != 0); 2568 #ifdef XP_DEBUG_OBJ_USAGE 2569 xmlXPathDebugObjUsageRequested(ctxt, XPATH_BOOLEAN); 2570 #endif 2571 return(ret); 2572 } else if ((cache->miscObjs != NULL) && 2573 (cache->miscObjs->number != 0)) 2574 { 2575 xmlXPathObjectPtr ret; 2576 2577 ret = (xmlXPathObjectPtr) 2578 cache->miscObjs->items[--cache->miscObjs->number]; 2579 2580 ret->type = XPATH_BOOLEAN; 2581 ret->boolval = (val != 0); 2582 #ifdef XP_DEBUG_OBJ_USAGE 2583 xmlXPathDebugObjUsageRequested(ctxt, XPATH_BOOLEAN); 2584 #endif 2585 return(ret); 2586 } 2587 } 2588 return(xmlXPathNewBoolean(val)); 2589 } 2590 2591 /** 2592 * xmlXPathCacheNewFloat: 2593 * @ctxt: the XPath context 2594 * @val: the double value 2595 * 2596 * This is the cached version of xmlXPathNewFloat(). 2597 * Acquires an xmlXPathObjectPtr of type double and of value @val 2598 * 2599 * Returns the created or reused object. 2600 */ 2601 static xmlXPathObjectPtr 2602 xmlXPathCacheNewFloat(xmlXPathContextPtr ctxt, double val) 2603 { 2604 if ((ctxt != NULL) && (ctxt->cache)) { 2605 xmlXPathContextCachePtr cache = (xmlXPathContextCachePtr) ctxt->cache; 2606 2607 if ((cache->numberObjs != NULL) && 2608 (cache->numberObjs->number != 0)) 2609 { 2610 xmlXPathObjectPtr ret; 2611 2612 ret = (xmlXPathObjectPtr) 2613 cache->numberObjs->items[--cache->numberObjs->number]; 2614 ret->type = XPATH_NUMBER; 2615 ret->floatval = val; 2616 #ifdef XP_DEBUG_OBJ_USAGE 2617 xmlXPathDebugObjUsageRequested(ctxt, XPATH_NUMBER); 2618 #endif 2619 return(ret); 2620 } else if ((cache->miscObjs != NULL) && 2621 (cache->miscObjs->number != 0)) 2622 { 2623 xmlXPathObjectPtr ret; 2624 2625 ret = (xmlXPathObjectPtr) 2626 cache->miscObjs->items[--cache->miscObjs->number]; 2627 2628 ret->type = XPATH_NUMBER; 2629 ret->floatval = val; 2630 #ifdef XP_DEBUG_OBJ_USAGE 2631 xmlXPathDebugObjUsageRequested(ctxt, XPATH_NUMBER); 2632 #endif 2633 return(ret); 2634 } 2635 } 2636 return(xmlXPathNewFloat(val)); 2637 } 2638 2639 /** 2640 * xmlXPathCacheConvertString: 2641 * @ctxt: the XPath context 2642 * @val: an XPath object 2643 * 2644 * This is the cached version of xmlXPathConvertString(). 2645 * Converts an existing object to its string() equivalent 2646 * 2647 * Returns a created or reused object, the old one is freed (cached) 2648 * (or the operation is done directly on @val) 2649 */ 2650 2651 static xmlXPathObjectPtr 2652 xmlXPathCacheConvertString(xmlXPathContextPtr ctxt, xmlXPathObjectPtr val) { 2653 xmlChar *res = NULL; 2654 2655 if (val == NULL) 2656 return(xmlXPathCacheNewCString(ctxt, "")); 2657 2658 switch (val->type) { 2659 case XPATH_UNDEFINED: 2660 #ifdef DEBUG_EXPR 2661 xmlGenericError(xmlGenericErrorContext, "STRING: undefined\n"); 2662 #endif 2663 break; 2664 case XPATH_NODESET: 2665 case XPATH_XSLT_TREE: 2666 res = xmlXPathCastNodeSetToString(val->nodesetval); 2667 break; 2668 case XPATH_STRING: 2669 return(val); 2670 case XPATH_BOOLEAN: 2671 res = xmlXPathCastBooleanToString(val->boolval); 2672 break; 2673 case XPATH_NUMBER: 2674 res = xmlXPathCastNumberToString(val->floatval); 2675 break; 2676 case XPATH_USERS: 2677 case XPATH_POINT: 2678 case XPATH_RANGE: 2679 case XPATH_LOCATIONSET: 2680 TODO; 2681 break; 2682 } 2683 xmlXPathReleaseObject(ctxt, val); 2684 if (res == NULL) 2685 return(xmlXPathCacheNewCString(ctxt, "")); 2686 return(xmlXPathCacheWrapString(ctxt, res)); 2687 } 2688 2689 /** 2690 * xmlXPathCacheObjectCopy: 2691 * @ctxt: the XPath context 2692 * @val: the original object 2693 * 2694 * This is the cached version of xmlXPathObjectCopy(). 2695 * Acquire a copy of a given object 2696 * 2697 * Returns a created or reused created object. 2698 */ 2699 static xmlXPathObjectPtr 2700 xmlXPathCacheObjectCopy(xmlXPathContextPtr ctxt, xmlXPathObjectPtr val) 2701 { 2702 if (val == NULL) 2703 return(NULL); 2704 2705 if (XP_HAS_CACHE(ctxt)) { 2706 switch (val->type) { 2707 case XPATH_NODESET: 2708 return(xmlXPathCacheWrapNodeSet(ctxt, 2709 xmlXPathNodeSetMerge(NULL, val->nodesetval))); 2710 case XPATH_STRING: 2711 return(xmlXPathCacheNewString(ctxt, val->stringval)); 2712 case XPATH_BOOLEAN: 2713 return(xmlXPathCacheNewBoolean(ctxt, val->boolval)); 2714 case XPATH_NUMBER: 2715 return(xmlXPathCacheNewFloat(ctxt, val->floatval)); 2716 default: 2717 break; 2718 } 2719 } 2720 return(xmlXPathObjectCopy(val)); 2721 } 2722 2723 /** 2724 * xmlXPathCacheConvertBoolean: 2725 * @ctxt: the XPath context 2726 * @val: an XPath object 2727 * 2728 * This is the cached version of xmlXPathConvertBoolean(). 2729 * Converts an existing object to its boolean() equivalent 2730 * 2731 * Returns a created or reused object, the old one is freed (or the operation 2732 * is done directly on @val) 2733 */ 2734 static xmlXPathObjectPtr 2735 xmlXPathCacheConvertBoolean(xmlXPathContextPtr ctxt, xmlXPathObjectPtr val) { 2736 xmlXPathObjectPtr ret; 2737 2738 if (val == NULL) 2739 return(xmlXPathCacheNewBoolean(ctxt, 0)); 2740 if (val->type == XPATH_BOOLEAN) 2741 return(val); 2742 ret = xmlXPathCacheNewBoolean(ctxt, xmlXPathCastToBoolean(val)); 2743 xmlXPathReleaseObject(ctxt, val); 2744 return(ret); 2745 } 2746 2747 /** 2748 * xmlXPathCacheConvertNumber: 2749 * @ctxt: the XPath context 2750 * @val: an XPath object 2751 * 2752 * This is the cached version of xmlXPathConvertNumber(). 2753 * Converts an existing object to its number() equivalent 2754 * 2755 * Returns a created or reused object, the old one is freed (or the operation 2756 * is done directly on @val) 2757 */ 2758 static xmlXPathObjectPtr 2759 xmlXPathCacheConvertNumber(xmlXPathContextPtr ctxt, xmlXPathObjectPtr val) { 2760 xmlXPathObjectPtr ret; 2761 2762 if (val == NULL) 2763 return(xmlXPathCacheNewFloat(ctxt, 0.0)); 2764 if (val->type == XPATH_NUMBER) 2765 return(val); 2766 ret = xmlXPathCacheNewFloat(ctxt, xmlXPathCastToNumber(val)); 2767 xmlXPathReleaseObject(ctxt, val); 2768 return(ret); 2769 } 2770 2771 /************************************************************************ 2772 * * 2773 * Parser stacks related functions and macros * 2774 * * 2775 ************************************************************************/ 2776 2777 /** 2778 * xmlXPathSetFrame: 2779 * @ctxt: an XPath parser context 2780 * 2781 * Set the callee evaluation frame 2782 * 2783 * Returns the previous frame value to be restored once done 2784 */ 2785 static int 2786 xmlXPathSetFrame(xmlXPathParserContextPtr ctxt) { 2787 int ret; 2788 2789 if (ctxt == NULL) 2790 return(0); 2791 ret = ctxt->valueFrame; 2792 ctxt->valueFrame = ctxt->valueNr; 2793 return(ret); 2794 } 2795 2796 /** 2797 * xmlXPathPopFrame: 2798 * @ctxt: an XPath parser context 2799 * @frame: the previous frame value 2800 * 2801 * Remove the callee evaluation frame 2802 */ 2803 static void 2804 xmlXPathPopFrame(xmlXPathParserContextPtr ctxt, int frame) { 2805 if (ctxt == NULL) 2806 return; 2807 if (ctxt->valueNr < ctxt->valueFrame) { 2808 xmlXPatherror(ctxt, __FILE__, __LINE__, XPATH_STACK_ERROR); 2809 } 2810 ctxt->valueFrame = frame; 2811 } 2812 2813 /** 2814 * valuePop: 2815 * @ctxt: an XPath evaluation context 2816 * 2817 * Pops the top XPath object from the value stack 2818 * 2819 * Returns the XPath object just removed 2820 */ 2821 xmlXPathObjectPtr 2822 valuePop(xmlXPathParserContextPtr ctxt) 2823 { 2824 xmlXPathObjectPtr ret; 2825 2826 if ((ctxt == NULL) || (ctxt->valueNr <= 0)) 2827 return (NULL); 2828 2829 if (ctxt->valueNr <= ctxt->valueFrame) { 2830 xmlXPatherror(ctxt, __FILE__, __LINE__, XPATH_STACK_ERROR); 2831 return (NULL); 2832 } 2833 2834 ctxt->valueNr--; 2835 if (ctxt->valueNr > 0) 2836 ctxt->value = ctxt->valueTab[ctxt->valueNr - 1]; 2837 else 2838 ctxt->value = NULL; 2839 ret = ctxt->valueTab[ctxt->valueNr]; 2840 ctxt->valueTab[ctxt->valueNr] = NULL; 2841 return (ret); 2842 } 2843 /** 2844 * valuePush: 2845 * @ctxt: an XPath evaluation context 2846 * @value: the XPath object 2847 * 2848 * Pushes a new XPath object on top of the value stack 2849 * 2850 * returns the number of items on the value stack 2851 */ 2852 int 2853 valuePush(xmlXPathParserContextPtr ctxt, xmlXPathObjectPtr value) 2854 { 2855 if ((ctxt == NULL) || (value == NULL)) return(-1); 2856 if (ctxt->valueNr >= ctxt->valueMax) { 2857 xmlXPathObjectPtr *tmp; 2858 2859 if (ctxt->valueMax >= XPATH_MAX_STACK_DEPTH) { 2860 xmlXPathErrMemory(NULL, "XPath stack depth limit reached\n"); 2861 ctxt->error = XPATH_MEMORY_ERROR; 2862 return (0); 2863 } 2864 tmp = (xmlXPathObjectPtr *) xmlRealloc(ctxt->valueTab, 2865 2 * ctxt->valueMax * 2866 sizeof(ctxt->valueTab[0])); 2867 if (tmp == NULL) { 2868 xmlXPathErrMemory(NULL, "pushing value\n"); 2869 ctxt->error = XPATH_MEMORY_ERROR; 2870 return (0); 2871 } 2872 ctxt->valueMax *= 2; 2873 ctxt->valueTab = tmp; 2874 } 2875 ctxt->valueTab[ctxt->valueNr] = value; 2876 ctxt->value = value; 2877 return (ctxt->valueNr++); 2878 } 2879 2880 /** 2881 * xmlXPathPopBoolean: 2882 * @ctxt: an XPath parser context 2883 * 2884 * Pops a boolean from the stack, handling conversion if needed. 2885 * Check error with #xmlXPathCheckError. 2886 * 2887 * Returns the boolean 2888 */ 2889 int 2890 xmlXPathPopBoolean (xmlXPathParserContextPtr ctxt) { 2891 xmlXPathObjectPtr obj; 2892 int ret; 2893 2894 obj = valuePop(ctxt); 2895 if (obj == NULL) { 2896 xmlXPathSetError(ctxt, XPATH_INVALID_OPERAND); 2897 return(0); 2898 } 2899 if (obj->type != XPATH_BOOLEAN) 2900 ret = xmlXPathCastToBoolean(obj); 2901 else 2902 ret = obj->boolval; 2903 xmlXPathReleaseObject(ctxt->context, obj); 2904 return(ret); 2905 } 2906 2907 /** 2908 * xmlXPathPopNumber: 2909 * @ctxt: an XPath parser context 2910 * 2911 * Pops a number from the stack, handling conversion if needed. 2912 * Check error with #xmlXPathCheckError. 2913 * 2914 * Returns the number 2915 */ 2916 double 2917 xmlXPathPopNumber (xmlXPathParserContextPtr ctxt) { 2918 xmlXPathObjectPtr obj; 2919 double ret; 2920 2921 obj = valuePop(ctxt); 2922 if (obj == NULL) { 2923 xmlXPathSetError(ctxt, XPATH_INVALID_OPERAND); 2924 return(0); 2925 } 2926 if (obj->type != XPATH_NUMBER) 2927 ret = xmlXPathCastToNumber(obj); 2928 else 2929 ret = obj->floatval; 2930 xmlXPathReleaseObject(ctxt->context, obj); 2931 return(ret); 2932 } 2933 2934 /** 2935 * xmlXPathPopString: 2936 * @ctxt: an XPath parser context 2937 * 2938 * Pops a string from the stack, handling conversion if needed. 2939 * Check error with #xmlXPathCheckError. 2940 * 2941 * Returns the string 2942 */ 2943 xmlChar * 2944 xmlXPathPopString (xmlXPathParserContextPtr ctxt) { 2945 xmlXPathObjectPtr obj; 2946 xmlChar * ret; 2947 2948 obj = valuePop(ctxt); 2949 if (obj == NULL) { 2950 xmlXPathSetError(ctxt, XPATH_INVALID_OPERAND); 2951 return(NULL); 2952 } 2953 ret = xmlXPathCastToString(obj); /* this does required strdup */ 2954 /* TODO: needs refactoring somewhere else */ 2955 if (obj->stringval == ret) 2956 obj->stringval = NULL; 2957 xmlXPathReleaseObject(ctxt->context, obj); 2958 return(ret); 2959 } 2960 2961 /** 2962 * xmlXPathPopNodeSet: 2963 * @ctxt: an XPath parser context 2964 * 2965 * Pops a node-set from the stack, handling conversion if needed. 2966 * Check error with #xmlXPathCheckError. 2967 * 2968 * Returns the node-set 2969 */ 2970 xmlNodeSetPtr 2971 xmlXPathPopNodeSet (xmlXPathParserContextPtr ctxt) { 2972 xmlXPathObjectPtr obj; 2973 xmlNodeSetPtr ret; 2974 2975 if (ctxt == NULL) return(NULL); 2976 if (ctxt->value == NULL) { 2977 xmlXPathSetError(ctxt, XPATH_INVALID_OPERAND); 2978 return(NULL); 2979 } 2980 if (!xmlXPathStackIsNodeSet(ctxt)) { 2981 xmlXPathSetTypeError(ctxt); 2982 return(NULL); 2983 } 2984 obj = valuePop(ctxt); 2985 ret = obj->nodesetval; 2986 #if 0 2987 /* to fix memory leak of not clearing obj->user */ 2988 if (obj->boolval && obj->user != NULL) 2989 xmlFreeNodeList((xmlNodePtr) obj->user); 2990 #endif 2991 obj->nodesetval = NULL; 2992 xmlXPathReleaseObject(ctxt->context, obj); 2993 return(ret); 2994 } 2995 2996 /** 2997 * xmlXPathPopExternal: 2998 * @ctxt: an XPath parser context 2999 * 3000 * Pops an external object from the stack, handling conversion if needed. 3001 * Check error with #xmlXPathCheckError. 3002 * 3003 * Returns the object 3004 */ 3005 void * 3006 xmlXPathPopExternal (xmlXPathParserContextPtr ctxt) { 3007 xmlXPathObjectPtr obj; 3008 void * ret; 3009 3010 if ((ctxt == NULL) || (ctxt->value == NULL)) { 3011 xmlXPathSetError(ctxt, XPATH_INVALID_OPERAND); 3012 return(NULL); 3013 } 3014 if (ctxt->value->type != XPATH_USERS) { 3015 xmlXPathSetTypeError(ctxt); 3016 return(NULL); 3017 } 3018 obj = valuePop(ctxt); 3019 ret = obj->user; 3020 obj->user = NULL; 3021 xmlXPathReleaseObject(ctxt->context, obj); 3022 return(ret); 3023 } 3024 3025 /* 3026 * Macros for accessing the content. Those should be used only by the parser, 3027 * and not exported. 3028 * 3029 * Dirty macros, i.e. one need to make assumption on the context to use them 3030 * 3031 * CUR_PTR return the current pointer to the xmlChar to be parsed. 3032 * CUR returns the current xmlChar value, i.e. a 8 bit value 3033 * in ISO-Latin or UTF-8. 3034 * This should be used internally by the parser 3035 * only to compare to ASCII values otherwise it would break when 3036 * running with UTF-8 encoding. 3037 * NXT(n) returns the n'th next xmlChar. Same as CUR is should be used only 3038 * to compare on ASCII based substring. 3039 * SKIP(n) Skip n xmlChar, and must also be used only to skip ASCII defined 3040 * strings within the parser. 3041 * CURRENT Returns the current char value, with the full decoding of 3042 * UTF-8 if we are using this mode. It returns an int. 3043 * NEXT Skip to the next character, this does the proper decoding 3044 * in UTF-8 mode. It also pop-up unfinished entities on the fly. 3045 * It returns the pointer to the current xmlChar. 3046 */ 3047 3048 #define CUR (*ctxt->cur) 3049 #define SKIP(val) ctxt->cur += (val) 3050 #define NXT(val) ctxt->cur[(val)] 3051 #define CUR_PTR ctxt->cur 3052 #define CUR_CHAR(l) xmlXPathCurrentChar(ctxt, &l) 3053 3054 #define COPY_BUF(l,b,i,v) \ 3055 if (l == 1) b[i++] = (xmlChar) v; \ 3056 else i += xmlCopyChar(l,&b[i],v) 3057 3058 #define NEXTL(l) ctxt->cur += l 3059 3060 #define SKIP_BLANKS \ 3061 while (IS_BLANK_CH(*(ctxt->cur))) NEXT 3062 3063 #define CURRENT (*ctxt->cur) 3064 #define NEXT ((*ctxt->cur) ? ctxt->cur++: ctxt->cur) 3065 3066 3067 #ifndef DBL_DIG 3068 #define DBL_DIG 16 3069 #endif 3070 #ifndef DBL_EPSILON 3071 #define DBL_EPSILON 1E-9 3072 #endif 3073 3074 #define UPPER_DOUBLE 1E9 3075 #define LOWER_DOUBLE 1E-5 3076 #define LOWER_DOUBLE_EXP 5 3077 3078 #define INTEGER_DIGITS DBL_DIG 3079 #define FRACTION_DIGITS (DBL_DIG + 1 + (LOWER_DOUBLE_EXP)) 3080 #define EXPONENT_DIGITS (3 + 2) 3081 3082 /** 3083 * xmlXPathFormatNumber: 3084 * @number: number to format 3085 * @buffer: output buffer 3086 * @buffersize: size of output buffer 3087 * 3088 * Convert the number into a string representation. 3089 */ 3090 static void 3091 xmlXPathFormatNumber(double number, char buffer[], int buffersize) 3092 { 3093 switch (xmlXPathIsInf(number)) { 3094 case 1: 3095 if (buffersize > (int)sizeof("Infinity")) 3096 snprintf(buffer, buffersize, "Infinity"); 3097 break; 3098 case -1: 3099 if (buffersize > (int)sizeof("-Infinity")) 3100 snprintf(buffer, buffersize, "-Infinity"); 3101 break; 3102 default: 3103 if (xmlXPathIsNaN(number)) { 3104 if (buffersize > (int)sizeof("NaN")) 3105 snprintf(buffer, buffersize, "NaN"); 3106 } else if (number == 0 && xmlXPathGetSign(number) != 0) { 3107 snprintf(buffer, buffersize, "0"); 3108 } else if (number == ((int) number)) { 3109 char work[30]; 3110 char *ptr, *cur; 3111 int value = (int) number; 3112 3113 ptr = &buffer[0]; 3114 if (value == 0) { 3115 *ptr++ = '0'; 3116 } else { 3117 snprintf(work, 29, "%d", value); 3118 cur = &work[0]; 3119 while ((*cur) && (ptr - buffer < buffersize)) { 3120 *ptr++ = *cur++; 3121 } 3122 } 3123 if (ptr - buffer < buffersize) { 3124 *ptr = 0; 3125 } else if (buffersize > 0) { 3126 ptr--; 3127 *ptr = 0; 3128 } 3129 } else { 3130 /* 3131 For the dimension of work, 3132 DBL_DIG is number of significant digits 3133 EXPONENT is only needed for "scientific notation" 3134 3 is sign, decimal point, and terminating zero 3135 LOWER_DOUBLE_EXP is max number of leading zeroes in fraction 3136 Note that this dimension is slightly (a few characters) 3137 larger than actually necessary. 3138 */ 3139 char work[DBL_DIG + EXPONENT_DIGITS + 3 + LOWER_DOUBLE_EXP]; 3140 int integer_place, fraction_place; 3141 char *ptr; 3142 char *after_fraction; 3143 double absolute_value; 3144 int size; 3145 3146 absolute_value = fabs(number); 3147 3148 /* 3149 * First choose format - scientific or regular floating point. 3150 * In either case, result is in work, and after_fraction points 3151 * just past the fractional part. 3152 */ 3153 if ( ((absolute_value > UPPER_DOUBLE) || 3154 (absolute_value < LOWER_DOUBLE)) && 3155 (absolute_value != 0.0) ) { 3156 /* Use scientific notation */ 3157 integer_place = DBL_DIG + EXPONENT_DIGITS + 1; 3158 fraction_place = DBL_DIG - 1; 3159 size = snprintf(work, sizeof(work),"%*.*e", 3160 integer_place, fraction_place, number); 3161 while ((size > 0) && (work[size] != 'e')) size--; 3162 3163 } 3164 else { 3165 /* Use regular notation */ 3166 if (absolute_value > 0.0) { 3167 integer_place = (int)log10(absolute_value); 3168 if (integer_place > 0) 3169 fraction_place = DBL_DIG - integer_place - 1; 3170 else 3171 fraction_place = DBL_DIG - integer_place; 3172 } else { 3173 fraction_place = 1; 3174 } 3175 size = snprintf(work, sizeof(work), "%0.*f", 3176 fraction_place, number); 3177 } 3178 3179 /* Remove leading spaces sometimes inserted by snprintf */ 3180 while (work[0] == ' ') { 3181 for (ptr = &work[0];(ptr[0] = ptr[1]);ptr++); 3182 size--; 3183 } 3184 3185 /* Remove fractional trailing zeroes */ 3186 after_fraction = work + size; 3187 ptr = after_fraction; 3188 while (*(--ptr) == '0') 3189 ; 3190 if (*ptr != '.') 3191 ptr++; 3192 while ((*ptr++ = *after_fraction++) != 0); 3193 3194 /* Finally copy result back to caller */ 3195 size = strlen(work) + 1; 3196 if (size > buffersize) { 3197 work[buffersize - 1] = 0; 3198 size = buffersize; 3199 } 3200 memmove(buffer, work, size); 3201 } 3202 break; 3203 } 3204 } 3205 3206 3207 /************************************************************************ 3208 * * 3209 * Routines to handle NodeSets * 3210 * * 3211 ************************************************************************/ 3212 3213 /** 3214 * xmlXPathOrderDocElems: 3215 * @doc: an input document 3216 * 3217 * Call this routine to speed up XPath computation on static documents. 3218 * This stamps all the element nodes with the document order 3219 * Like for line information, the order is kept in the element->content 3220 * field, the value stored is actually - the node number (starting at -1) 3221 * to be able to differentiate from line numbers. 3222 * 3223 * Returns the number of elements found in the document or -1 in case 3224 * of error. 3225 */ 3226 long 3227 xmlXPathOrderDocElems(xmlDocPtr doc) { 3228 long count = 0; 3229 xmlNodePtr cur; 3230 3231 if (doc == NULL) 3232 return(-1); 3233 cur = doc->children; 3234 while (cur != NULL) { 3235 if (cur->type == XML_ELEMENT_NODE) { 3236 cur->content = (void *) (-(++count)); 3237 if (cur->children != NULL) { 3238 cur = cur->children; 3239 continue; 3240 } 3241 } 3242 if (cur->next != NULL) { 3243 cur = cur->next; 3244 continue; 3245 } 3246 do { 3247 cur = cur->parent; 3248 if (cur == NULL) 3249 break; 3250 if (cur == (xmlNodePtr) doc) { 3251 cur = NULL; 3252 break; 3253 } 3254 if (cur->next != NULL) { 3255 cur = cur->next; 3256 break; 3257 } 3258 } while (cur != NULL); 3259 } 3260 return(count); 3261 } 3262 3263 /** 3264 * xmlXPathCmpNodes: 3265 * @node1: the first node 3266 * @node2: the second node 3267 * 3268 * Compare two nodes w.r.t document order 3269 * 3270 * Returns -2 in case of error 1 if first point < second point, 0 if 3271 * it's the same node, -1 otherwise 3272 */ 3273 int 3274 xmlXPathCmpNodes(xmlNodePtr node1, xmlNodePtr node2) { 3275 int depth1, depth2; 3276 int attr1 = 0, attr2 = 0; 3277 xmlNodePtr attrNode1 = NULL, attrNode2 = NULL; 3278 xmlNodePtr cur, root; 3279 3280 if ((node1 == NULL) || (node2 == NULL)) 3281 return(-2); 3282 /* 3283 * a couple of optimizations which will avoid computations in most cases 3284 */ 3285 if (node1 == node2) /* trivial case */ 3286 return(0); 3287 if (node1->type == XML_ATTRIBUTE_NODE) { 3288 attr1 = 1; 3289 attrNode1 = node1; 3290 node1 = node1->parent; 3291 } 3292 if (node2->type == XML_ATTRIBUTE_NODE) { 3293 attr2 = 1; 3294 attrNode2 = node2; 3295 node2 = node2->parent; 3296 } 3297 if (node1 == node2) { 3298 if (attr1 == attr2) { 3299 /* not required, but we keep attributes in order */ 3300 if (attr1 != 0) { 3301 cur = attrNode2->prev; 3302 while (cur != NULL) { 3303 if (cur == attrNode1) 3304 return (1); 3305 cur = cur->prev; 3306 } 3307 return (-1); 3308 } 3309 return(0); 3310 } 3311 if (attr2 == 1) 3312 return(1); 3313 return(-1); 3314 } 3315 if ((node1->type == XML_NAMESPACE_DECL) || 3316 (node2->type == XML_NAMESPACE_DECL)) 3317 return(1); 3318 if (node1 == node2->prev) 3319 return(1); 3320 if (node1 == node2->next) 3321 return(-1); 3322 3323 /* 3324 * Speedup using document order if availble. 3325 */ 3326 if ((node1->type == XML_ELEMENT_NODE) && 3327 (node2->type == XML_ELEMENT_NODE) && 3328 (0 > (long) node1->content) && 3329 (0 > (long) node2->content) && 3330 (node1->doc == node2->doc)) { 3331 long l1, l2; 3332 3333 l1 = -((long) node1->content); 3334 l2 = -((long) node2->content); 3335 if (l1 < l2) 3336 return(1); 3337 if (l1 > l2) 3338 return(-1); 3339 } 3340 3341 /* 3342 * compute depth to root 3343 */ 3344 for (depth2 = 0, cur = node2;cur->parent != NULL;cur = cur->parent) { 3345 if (cur == node1) 3346 return(1); 3347 depth2++; 3348 } 3349 root = cur; 3350 for (depth1 = 0, cur = node1;cur->parent != NULL;cur = cur->parent) { 3351 if (cur == node2) 3352 return(-1); 3353 depth1++; 3354 } 3355 /* 3356 * Distinct document (or distinct entities :-( ) case. 3357 */ 3358 if (root != cur) { 3359 return(-2); 3360 } 3361 /* 3362 * get the nearest common ancestor. 3363 */ 3364 while (depth1 > depth2) { 3365 depth1--; 3366 node1 = node1->parent; 3367 } 3368 while (depth2 > depth1) { 3369 depth2--; 3370 node2 = node2->parent; 3371 } 3372 while (node1->parent != node2->parent) { 3373 node1 = node1->parent; 3374 node2 = node2->parent; 3375 /* should not happen but just in case ... */ 3376 if ((node1 == NULL) || (node2 == NULL)) 3377 return(-2); 3378 } 3379 /* 3380 * Find who's first. 3381 */ 3382 if (node1 == node2->prev) 3383 return(1); 3384 if (node1 == node2->next) 3385 return(-1); 3386 /* 3387 * Speedup using document order if availble. 3388 */ 3389 if ((node1->type == XML_ELEMENT_NODE) && 3390 (node2->type == XML_ELEMENT_NODE) && 3391 (0 > (long) node1->content) && 3392 (0 > (long) node2->content) && 3393 (node1->doc == node2->doc)) { 3394 long l1, l2; 3395 3396 l1 = -((long) node1->content); 3397 l2 = -((long) node2->content); 3398 if (l1 < l2) 3399 return(1); 3400 if (l1 > l2) 3401 return(-1); 3402 } 3403 3404 for (cur = node1->next;cur != NULL;cur = cur->next) 3405 if (cur == node2) 3406 return(1); 3407 return(-1); /* assume there is no sibling list corruption */ 3408 } 3409 3410 /** 3411 * xmlXPathNodeSetSort: 3412 * @set: the node set 3413 * 3414 * Sort the node set in document order 3415 */ 3416 void 3417 xmlXPathNodeSetSort(xmlNodeSetPtr set) { 3418 #ifndef WITH_TIM_SORT 3419 int i, j, incr, len; 3420 xmlNodePtr tmp; 3421 #endif 3422 3423 if (set == NULL) 3424 return; 3425 3426 #ifndef WITH_TIM_SORT 3427 /* 3428 * Use the old Shell's sort implementation to sort the node-set 3429 * Timsort ought to be quite faster 3430 */ 3431 len = set->nodeNr; 3432 for (incr = len / 2; incr > 0; incr /= 2) { 3433 for (i = incr; i < len; i++) { 3434 j = i - incr; 3435 while (j >= 0) { 3436 #ifdef XP_OPTIMIZED_NON_ELEM_COMPARISON 3437 if (xmlXPathCmpNodesExt(set->nodeTab[j], 3438 set->nodeTab[j + incr]) == -1) 3439 #else 3440 if (xmlXPathCmpNodes(set->nodeTab[j], 3441 set->nodeTab[j + incr]) == -1) 3442 #endif 3443 { 3444 tmp = set->nodeTab[j]; 3445 set->nodeTab[j] = set->nodeTab[j + incr]; 3446 set->nodeTab[j + incr] = tmp; 3447 j -= incr; 3448 } else 3449 break; 3450 } 3451 } 3452 } 3453 #else /* WITH_TIM_SORT */ 3454 libxml_domnode_tim_sort(set->nodeTab, set->nodeNr); 3455 #endif /* WITH_TIM_SORT */ 3456 } 3457 3458 #define XML_NODESET_DEFAULT 10 3459 /** 3460 * xmlXPathNodeSetDupNs: 3461 * @node: the parent node of the namespace XPath node 3462 * @ns: the libxml namespace declaration node. 3463 * 3464 * Namespace node in libxml don't match the XPath semantic. In a node set 3465 * the namespace nodes are duplicated and the next pointer is set to the 3466 * parent node in the XPath semantic. 3467 * 3468 * Returns the newly created object. 3469 */ 3470 static xmlNodePtr 3471 xmlXPathNodeSetDupNs(xmlNodePtr node, xmlNsPtr ns) { 3472 xmlNsPtr cur; 3473 3474 if ((ns == NULL) || (ns->type != XML_NAMESPACE_DECL)) 3475 return(NULL); 3476 if ((node == NULL) || (node->type == XML_NAMESPACE_DECL)) 3477 return((xmlNodePtr) ns); 3478 3479 /* 3480 * Allocate a new Namespace and fill the fields. 3481 */ 3482 cur = (xmlNsPtr) xmlMalloc(sizeof(xmlNs)); 3483 if (cur == NULL) { 3484 xmlXPathErrMemory(NULL, "duplicating namespace\n"); 3485 return(NULL); 3486 } 3487 memset(cur, 0, sizeof(xmlNs)); 3488 cur->type = XML_NAMESPACE_DECL; 3489 if (ns->href != NULL) 3490 cur->href = xmlStrdup(ns->href); 3491 if (ns->prefix != NULL) 3492 cur->prefix = xmlStrdup(ns->prefix); 3493 cur->next = (xmlNsPtr) node; 3494 return((xmlNodePtr) cur); 3495 } 3496 3497 /** 3498 * xmlXPathNodeSetFreeNs: 3499 * @ns: the XPath namespace node found in a nodeset. 3500 * 3501 * Namespace nodes in libxml don't match the XPath semantic. In a node set 3502 * the namespace nodes are duplicated and the next pointer is set to the 3503 * parent node in the XPath semantic. Check if such a node needs to be freed 3504 */ 3505 void 3506 xmlXPathNodeSetFreeNs(xmlNsPtr ns) { 3507 if ((ns == NULL) || (ns->type != XML_NAMESPACE_DECL)) 3508 return; 3509 3510 if ((ns->next != NULL) && (ns->next->type != XML_NAMESPACE_DECL)) { 3511 if (ns->href != NULL) 3512 xmlFree((xmlChar *)ns->href); 3513 if (ns->prefix != NULL) 3514 xmlFree((xmlChar *)ns->prefix); 3515 xmlFree(ns); 3516 } 3517 } 3518 3519 /** 3520 * xmlXPathNodeSetCreate: 3521 * @val: an initial xmlNodePtr, or NULL 3522 * 3523 * Create a new xmlNodeSetPtr of type double and of value @val 3524 * 3525 * Returns the newly created object. 3526 */ 3527 xmlNodeSetPtr 3528 xmlXPathNodeSetCreate(xmlNodePtr val) { 3529 xmlNodeSetPtr ret; 3530 3531 ret = (xmlNodeSetPtr) xmlMalloc(sizeof(xmlNodeSet)); 3532 if (ret == NULL) { 3533 xmlXPathErrMemory(NULL, "creating nodeset\n"); 3534 return(NULL); 3535 } 3536 memset(ret, 0 , (size_t) sizeof(xmlNodeSet)); 3537 if (val != NULL) { 3538 ret->nodeTab = (xmlNodePtr *) xmlMalloc(XML_NODESET_DEFAULT * 3539 sizeof(xmlNodePtr)); 3540 if (ret->nodeTab == NULL) { 3541 xmlXPathErrMemory(NULL, "creating nodeset\n"); 3542 xmlFree(ret); 3543 return(NULL); 3544 } 3545 memset(ret->nodeTab, 0 , 3546 XML_NODESET_DEFAULT * (size_t) sizeof(xmlNodePtr)); 3547 ret->nodeMax = XML_NODESET_DEFAULT; 3548 if (val->type == XML_NAMESPACE_DECL) { 3549 xmlNsPtr ns = (xmlNsPtr) val; 3550 3551 ret->nodeTab[ret->nodeNr++] = 3552 xmlXPathNodeSetDupNs((xmlNodePtr) ns->next, ns); 3553 } else 3554 ret->nodeTab[ret->nodeNr++] = val; 3555 } 3556 return(ret); 3557 } 3558 3559 /** 3560 * xmlXPathNodeSetCreateSize: 3561 * @size: the initial size of the set 3562 * 3563 * Create a new xmlNodeSetPtr of type double and of value @val 3564 * 3565 * Returns the newly created object. 3566 */ 3567 static xmlNodeSetPtr 3568 xmlXPathNodeSetCreateSize(int size) { 3569 xmlNodeSetPtr ret; 3570 3571 ret = (xmlNodeSetPtr) xmlMalloc(sizeof(xmlNodeSet)); 3572 if (ret == NULL) { 3573 xmlXPathErrMemory(NULL, "creating nodeset\n"); 3574 return(NULL); 3575 } 3576 memset(ret, 0 , (size_t) sizeof(xmlNodeSet)); 3577 if (size < XML_NODESET_DEFAULT) 3578 size = XML_NODESET_DEFAULT; 3579 ret->nodeTab = (xmlNodePtr *) xmlMalloc(size * sizeof(xmlNodePtr)); 3580 if (ret->nodeTab == NULL) { 3581 xmlXPathErrMemory(NULL, "creating nodeset\n"); 3582 xmlFree(ret); 3583 return(NULL); 3584 } 3585 memset(ret->nodeTab, 0 , size * (size_t) sizeof(xmlNodePtr)); 3586 ret->nodeMax = size; 3587 return(ret); 3588 } 3589 3590 /** 3591 * xmlXPathNodeSetContains: 3592 * @cur: the node-set 3593 * @val: the node 3594 * 3595 * checks whether @cur contains @val 3596 * 3597 * Returns true (1) if @cur contains @val, false (0) otherwise 3598 */ 3599 int 3600 xmlXPathNodeSetContains (xmlNodeSetPtr cur, xmlNodePtr val) { 3601 int i; 3602 3603 if ((cur == NULL) || (val == NULL)) return(0); 3604 if (val->type == XML_NAMESPACE_DECL) { 3605 for (i = 0; i < cur->nodeNr; i++) { 3606 if (cur->nodeTab[i]->type == XML_NAMESPACE_DECL) { 3607 xmlNsPtr ns1, ns2; 3608 3609 ns1 = (xmlNsPtr) val; 3610 ns2 = (xmlNsPtr) cur->nodeTab[i]; 3611 if (ns1 == ns2) 3612 return(1); 3613 if ((ns1->next != NULL) && (ns2->next == ns1->next) && 3614 (xmlStrEqual(ns1->prefix, ns2->prefix))) 3615 return(1); 3616 } 3617 } 3618 } else { 3619 for (i = 0; i < cur->nodeNr; i++) { 3620 if (cur->nodeTab[i] == val) 3621 return(1); 3622 } 3623 } 3624 return(0); 3625 } 3626 3627 /** 3628 * xmlXPathNodeSetAddNs: 3629 * @cur: the initial node set 3630 * @node: the hosting node 3631 * @ns: a the namespace node 3632 * 3633 * add a new namespace node to an existing NodeSet 3634 * 3635 * Returns 0 in case of success and -1 in case of error 3636 */ 3637 int 3638 xmlXPathNodeSetAddNs(xmlNodeSetPtr cur, xmlNodePtr node, xmlNsPtr ns) { 3639 int i; 3640 3641 3642 if ((cur == NULL) || (ns == NULL) || (node == NULL) || 3643 (ns->type != XML_NAMESPACE_DECL) || 3644 (node->type != XML_ELEMENT_NODE)) 3645 return(-1); 3646 3647 /* @@ with_ns to check whether namespace nodes should be looked at @@ */ 3648 /* 3649 * prevent duplicates 3650 */ 3651 for (i = 0;i < cur->nodeNr;i++) { 3652 if ((cur->nodeTab[i] != NULL) && 3653 (cur->nodeTab[i]->type == XML_NAMESPACE_DECL) && 3654 (((xmlNsPtr)cur->nodeTab[i])->next == (xmlNsPtr) node) && 3655 (xmlStrEqual(ns->prefix, ((xmlNsPtr)cur->nodeTab[i])->prefix))) 3656 return(0); 3657 } 3658 3659 /* 3660 * grow the nodeTab if needed 3661 */ 3662 if (cur->nodeMax == 0) { 3663 cur->nodeTab = (xmlNodePtr *) xmlMalloc(XML_NODESET_DEFAULT * 3664 sizeof(xmlNodePtr)); 3665 if (cur->nodeTab == NULL) { 3666 xmlXPathErrMemory(NULL, "growing nodeset\n"); 3667 return(-1); 3668 } 3669 memset(cur->nodeTab, 0 , 3670 XML_NODESET_DEFAULT * (size_t) sizeof(xmlNodePtr)); 3671 cur->nodeMax = XML_NODESET_DEFAULT; 3672 } else if (cur->nodeNr == cur->nodeMax) { 3673 xmlNodePtr *temp; 3674 3675 if (cur->nodeMax >= XPATH_MAX_NODESET_LENGTH) { 3676 xmlXPathErrMemory(NULL, "growing nodeset hit limit\n"); 3677 return(-1); 3678 } 3679 temp = (xmlNodePtr *) xmlRealloc(cur->nodeTab, cur->nodeMax * 2 * 3680 sizeof(xmlNodePtr)); 3681 if (temp == NULL) { 3682 xmlXPathErrMemory(NULL, "growing nodeset\n"); 3683 return(-1); 3684 } 3685 cur->nodeMax *= 2; 3686 cur->nodeTab = temp; 3687 } 3688 cur->nodeTab[cur->nodeNr++] = xmlXPathNodeSetDupNs(node, ns); 3689 return(0); 3690 } 3691 3692 /** 3693 * xmlXPathNodeSetAdd: 3694 * @cur: the initial node set 3695 * @val: a new xmlNodePtr 3696 * 3697 * add a new xmlNodePtr to an existing NodeSet 3698 * 3699 * Returns 0 in case of success, and -1 in case of error 3700 */ 3701 int 3702 xmlXPathNodeSetAdd(xmlNodeSetPtr cur, xmlNodePtr val) { 3703 int i; 3704 3705 if ((cur == NULL) || (val == NULL)) return(-1); 3706 3707 /* @@ with_ns to check whether namespace nodes should be looked at @@ */ 3708 /* 3709 * prevent duplcates 3710 */ 3711 for (i = 0;i < cur->nodeNr;i++) 3712 if (cur->nodeTab[i] == val) return(0); 3713 3714 /* 3715 * grow the nodeTab if needed 3716 */ 3717 if (cur->nodeMax == 0) { 3718 cur->nodeTab = (xmlNodePtr *) xmlMalloc(XML_NODESET_DEFAULT * 3719 sizeof(xmlNodePtr)); 3720 if (cur->nodeTab == NULL) { 3721 xmlXPathErrMemory(NULL, "growing nodeset\n"); 3722 return(-1); 3723 } 3724 memset(cur->nodeTab, 0 , 3725 XML_NODESET_DEFAULT * (size_t) sizeof(xmlNodePtr)); 3726 cur->nodeMax = XML_NODESET_DEFAULT; 3727 } else if (cur->nodeNr == cur->nodeMax) { 3728 xmlNodePtr *temp; 3729 3730 if (cur->nodeMax >= XPATH_MAX_NODESET_LENGTH) { 3731 xmlXPathErrMemory(NULL, "growing nodeset hit limit\n"); 3732 return(-1); 3733 } 3734 temp = (xmlNodePtr *) xmlRealloc(cur->nodeTab, cur->nodeMax * 2 * 3735 sizeof(xmlNodePtr)); 3736 if (temp == NULL) { 3737 xmlXPathErrMemory(NULL, "growing nodeset\n"); 3738 return(-1); 3739 } 3740 cur->nodeMax *= 2; 3741 cur->nodeTab = temp; 3742 } 3743 if (val->type == XML_NAMESPACE_DECL) { 3744 xmlNsPtr ns = (xmlNsPtr) val; 3745 3746 cur->nodeTab[cur->nodeNr++] = 3747 xmlXPathNodeSetDupNs((xmlNodePtr) ns->next, ns); 3748 } else 3749 cur->nodeTab[cur->nodeNr++] = val; 3750 return(0); 3751 } 3752 3753 /** 3754 * xmlXPathNodeSetAddUnique: 3755 * @cur: the initial node set 3756 * @val: a new xmlNodePtr 3757 * 3758 * add a new xmlNodePtr to an existing NodeSet, optimized version 3759 * when we are sure the node is not already in the set. 3760 * 3761 * Returns 0 in case of success and -1 in case of failure 3762 */ 3763 int 3764 xmlXPathNodeSetAddUnique(xmlNodeSetPtr cur, xmlNodePtr val) { 3765 if ((cur == NULL) || (val == NULL)) return(-1); 3766 3767 /* @@ with_ns to check whether namespace nodes should be looked at @@ */ 3768 /* 3769 * grow the nodeTab if needed 3770 */ 3771 if (cur->nodeMax == 0) { 3772 cur->nodeTab = (xmlNodePtr *) xmlMalloc(XML_NODESET_DEFAULT * 3773 sizeof(xmlNodePtr)); 3774 if (cur->nodeTab == NULL) { 3775 xmlXPathErrMemory(NULL, "growing nodeset\n"); 3776 return(-1); 3777 } 3778 memset(cur->nodeTab, 0 , 3779 XML_NODESET_DEFAULT * (size_t) sizeof(xmlNodePtr)); 3780 cur->nodeMax = XML_NODESET_DEFAULT; 3781 } else if (cur->nodeNr == cur->nodeMax) { 3782 xmlNodePtr *temp; 3783 3784 if (cur->nodeMax >= XPATH_MAX_NODESET_LENGTH) { 3785 xmlXPathErrMemory(NULL, "growing nodeset hit limit\n"); 3786 return(-1); 3787 } 3788 temp = (xmlNodePtr *) xmlRealloc(cur->nodeTab, cur->nodeMax * 2 * 3789 sizeof(xmlNodePtr)); 3790 if (temp == NULL) { 3791 xmlXPathErrMemory(NULL, "growing nodeset\n"); 3792 return(-1); 3793 } 3794 cur->nodeTab = temp; 3795 cur->nodeMax *= 2; 3796 } 3797 if (val->type == XML_NAMESPACE_DECL) { 3798 xmlNsPtr ns = (xmlNsPtr) val; 3799 3800 cur->nodeTab[cur->nodeNr++] = 3801 xmlXPathNodeSetDupNs((xmlNodePtr) ns->next, ns); 3802 } else 3803 cur->nodeTab[cur->nodeNr++] = val; 3804 return(0); 3805 } 3806 3807 /** 3808 * xmlXPathNodeSetMerge: 3809 * @val1: the first NodeSet or NULL 3810 * @val2: the second NodeSet 3811 * 3812 * Merges two nodesets, all nodes from @val2 are added to @val1 3813 * if @val1 is NULL, a new set is created and copied from @val2 3814 * 3815 * Returns @val1 once extended or NULL in case of error. 3816 */ 3817 xmlNodeSetPtr 3818 xmlXPathNodeSetMerge(xmlNodeSetPtr val1, xmlNodeSetPtr val2) { 3819 int i, j, initNr, skip; 3820 xmlNodePtr n1, n2; 3821 3822 if (val2 == NULL) return(val1); 3823 if (val1 == NULL) { 3824 val1 = xmlXPathNodeSetCreate(NULL); 3825 if (val1 == NULL) 3826 return (NULL); 3827 #if 0 3828 /* 3829 * TODO: The optimization won't work in every case, since 3830 * those nasty namespace nodes need to be added with 3831 * xmlXPathNodeSetDupNs() to the set; thus a pure 3832 * memcpy is not possible. 3833 * If there was a flag on the nodesetval, indicating that 3834 * some temporary nodes are in, that would be helpfull. 3835 */ 3836 /* 3837 * Optimization: Create an equally sized node-set 3838 * and memcpy the content. 3839 */ 3840 val1 = xmlXPathNodeSetCreateSize(val2->nodeNr); 3841 if (val1 == NULL) 3842 return(NULL); 3843 if (val2->nodeNr != 0) { 3844 if (val2->nodeNr == 1) 3845 *(val1->nodeTab) = *(val2->nodeTab); 3846 else { 3847 memcpy(val1->nodeTab, val2->nodeTab, 3848 val2->nodeNr * sizeof(xmlNodePtr)); 3849 } 3850 val1->nodeNr = val2->nodeNr; 3851 } 3852 return(val1); 3853 #endif 3854 } 3855 3856 /* @@ with_ns to check whether namespace nodes should be looked at @@ */ 3857 initNr = val1->nodeNr; 3858 3859 for (i = 0;i < val2->nodeNr;i++) { 3860 n2 = val2->nodeTab[i]; 3861 /* 3862 * check against duplicates 3863 */ 3864 skip = 0; 3865 for (j = 0; j < initNr; j++) { 3866 n1 = val1->nodeTab[j]; 3867 if (n1 == n2) { 3868 skip = 1; 3869 break; 3870 } else if ((n1->type == XML_NAMESPACE_DECL) && 3871 (n2->type == XML_NAMESPACE_DECL)) { 3872 if ((((xmlNsPtr) n1)->next == ((xmlNsPtr) n2)->next) && 3873 (xmlStrEqual(((xmlNsPtr) n1)->prefix, 3874 ((xmlNsPtr) n2)->prefix))) 3875 { 3876 skip = 1; 3877 break; 3878 } 3879 } 3880 } 3881 if (skip) 3882 continue; 3883 3884 /* 3885 * grow the nodeTab if needed 3886 */ 3887 if (val1->nodeMax == 0) { 3888 val1->nodeTab = (xmlNodePtr *) xmlMalloc(XML_NODESET_DEFAULT * 3889 sizeof(xmlNodePtr)); 3890 if (val1->nodeTab == NULL) {