libxml2/xpointer.c

   1 /*
   2  * xpointer.c : Code to handle XML Pointer
   3  *
   4  * Base implementation was made accordingly to
   5  * W3C Candidate Recommendation 7 June 2000
   6  * http://www.w3.org/TR/2000/CR-xptr-20000607
   7  *
   8  * Added support for the element() scheme described in:
   9  * W3C Proposed Recommendation 13 November 2002
  10  * http://www.w3.org/TR/2002/PR-xptr-element-20021113/
  11  *
  12  * See Copyright for the status of this software.
  13  *
  14  * daniel@veillard.com
  15  */
  16
  17 #define IN_LIBXML
  18 #include "libxml.h"
  19
  20 /*
  21  * TODO: better handling of error cases, the full expression should
  22  *       be parsed beforehand instead of a progressive evaluation
  23  * TODO: Access into entities references are not supported now ...
  24  *       need a start to be able to pop out of entities refs since
  25  *       parent is the endity declaration, not the ref.
  26  */
  27
  28 #include <string.h>
  29 #include <libxml/xpointer.h>
  30 #include <libxml/xmlmemory.h>
  31 #include <libxml/parserInternals.h>
  32 #include <libxml/uri.h>
  33 #include <libxml/xpath.h>
  34 #include <libxml/xpathInternals.h>
  35 #include <libxml/xmlerror.h>
  36 #include <libxml/globals.h>
  37
  38 #ifdef LIBXML_XPTR_ENABLED
  39
  40 /* Add support of the xmlns() xpointer scheme to initialize the namespaces */
  41 #define XPTR_XMLNS_SCHEME
  42
  43 /* #define DEBUG_RANGES */
  44 #ifdef DEBUG_RANGES
  45 #ifdef LIBXML_DEBUG_ENABLED
  46 #include <libxml/debugXML.h>
  47 #endif
  48 #endif
  49
  50 #define TODO                                                            \
  51     xmlGenericError(xmlGenericErrorContext,                             \
  52             "Unimplemented block at %s:%d\n",                           \
  53             __FILE__, __LINE__);
  54
  55 #define STRANGE                                                         \
  56     xmlGenericError(xmlGenericErrorContext,                             \
  57             "Internal error at %s:%d\n",                                \
  58             __FILE__, __LINE__);
  59
  60 /************************************************************************
  61  *                                                                      *
  62  *              A few helper functions for child sequences              *
  63  *                                                                      *
  64  ************************************************************************/
  65
  66 xmlNodePtr xmlXPtrAdvanceNode(xmlNodePtr cur);
  67 /**
  68  * xmlXPtrGetArity:
  69  * @cur:  the node
  70  *
  71  * Returns the number of child for an element, -1 in case of error
  72  */
  73 static int
  74 xmlXPtrGetArity(xmlNodePtr cur) {
  75     int i;
  76     if (cur == NULL)
  77         return(-1);
  78     cur = cur->children;
  79     for (i = 0;cur != NULL;cur = cur->next) {
  80         if ((cur->type == XML_ELEMENT_NODE) ||
  81             (cur->type == XML_DOCUMENT_NODE) ||
  82             (cur->type == XML_HTML_DOCUMENT_NODE)) {
  83             i++;
  84         }
  85     }
  86     return(i);
  87 }
  88
  89 /**
  90  * xmlXPtrGetIndex:
  91  * @cur:  the node
  92  *
  93  * Returns the index of the node in its parent children list, -1
  94  *         in case of error
  95  */
  96 static int
  97 xmlXPtrGetIndex(xmlNodePtr cur) {
  98     int i;
  99     if (cur == NULL)
 100         return(-1);
 101     for (i = 1;cur != NULL;cur = cur->prev) {
 102         if ((cur->type == XML_ELEMENT_NODE) ||
 103             (cur->type == XML_DOCUMENT_NODE) ||
 104             (cur->type == XML_HTML_DOCUMENT_NODE)) {
 105             i++;
 106         }
 107     }
 108     return(i);
 109 }
 110
 111 /**
 112  * xmlXPtrGetNthChild:
 113  * @cur:  the node
 114  * @no:  the child number
 115  *
 116  * Returns the @no'th element child of @cur or NULL
 117  */
 118 static xmlNodePtr
 119 xmlXPtrGetNthChild(xmlNodePtr cur, int no) {
 120     int i;
 121     if (cur == NULL)
 122         return(cur);
 123     cur = cur->children;
 124     for (i = 0;i <= no;cur = cur->next) {
 125         if (cur == NULL)
 126             return(cur);
 127         if ((cur->type == XML_ELEMENT_NODE) ||
 128             (cur->type == XML_DOCUMENT_NODE) ||
 129             (cur->type == XML_HTML_DOCUMENT_NODE)) {
 130             i++;
 131             if (i == no)
 132                 break;
 133         }
 134     }
 135     return(cur);
 136 }
 137
 138 /************************************************************************
 139  *                                                                      *
 140  *              Handling of XPointer specific types                     *
 141  *                                                                      *
 142  ************************************************************************/
 143
 144 /**
 145  * xmlXPtrCmpPoints:
 146  * @node1:  the first node
 147  * @index1:  the first index
 148  * @node2:  the second node
 149  * @index2:  the second index
 150  *
 151  * Compare two points w.r.t document order
 152  *
 153  * Returns -2 in case of error 1 if first point < second point, 0 if
 154  *         that's the same point, -1 otherwise
 155  */
 156 static int
 157 xmlXPtrCmpPoints(xmlNodePtr node1, int index1, xmlNodePtr node2, int index2) {
 158     if ((node1 == NULL) || (node2 == NULL))
 159         return(-2);
 160     /*
 161      * a couple of optimizations which will avoid computations in most cases
 162      */
 163     if (node1 == node2) {
 164         if (index1 < index2)
 165             return(1);
 166         if (index1 > index2)
 167             return(-1);
 168         return(0);
 169     }
 170     return(xmlXPathCmpNodes(node1, node2));
 171 }
 172
 173 /**
 174  * xmlXPtrNewPoint:
 175  * @node:  the xmlNodePtr
 176  * @indx:  the indx within the node
 177  *
 178  * Create a new xmlXPathObjectPtr of type point
 179  *
 180  * Returns the newly created object.
 181  */
 182 static xmlXPathObjectPtr
 183 xmlXPtrNewPoint(xmlNodePtr node, int indx) {
 184     xmlXPathObjectPtr ret;
 185
 186     if (node == NULL)
 187         return(NULL);
 188     if (indx < 0)
 189         return(NULL);
 190
 191     ret = (xmlXPathObjectPtr) xmlMalloc(sizeof(xmlXPathObject));
 192     if (ret == NULL) {
 193         xmlGenericError(xmlGenericErrorContext,
 194                 "xmlXPtrNewPoint: out of memory\n");
 195         return(NULL);
 196     }
 197     memset(ret, 0 , (size_t) sizeof(xmlXPathObject));
 198     ret->type = XPATH_POINT;
 199     ret->user = (void *) node;
 200     ret->index = indx;
 201     return(ret);
 202 }
 203
 204 /**
 205  * xmlXPtrRangeCheckOrder:
 206  * @range:  an object range
 207  *
 208  * Make sure the points in the range are in the right order
 209  */
 210 static void
 211 xmlXPtrRangeCheckOrder(xmlXPathObjectPtr range) {
 212     int tmp;
 213     xmlNodePtr tmp2;
 214     if (range == NULL)
 215         return;
 216     if (range->type != XPATH_RANGE)
 217         return;
 218     if (range->user2 == NULL)
 219         return;
 220     tmp = xmlXPtrCmpPoints(range->user, range->index,
 221                              range->user2, range->index2);
 222     if (tmp == -1) {
 223         tmp2 = range->user;
 224         range->user = range->user2;
 225         range->user2 = tmp2;
 226         tmp = range->index;
 227         range->index = range->index2;
 228         range->index2 = tmp;
 229     }
 230 }
 231
 232 /**
 233  * xmlXPtrRangesEqual:
 234  * @range1:  the first range
 235  * @range2:  the second range
 236  *
 237  * Compare two ranges
 238  *
 239  * Returns 1 if equal, 0 otherwise
 240  */
 241 static int
 242 xmlXPtrRangesEqual(xmlXPathObjectPtr range1, xmlXPathObjectPtr range2) {
 243     if (range1 == range2)
 244         return(1);
 245     if ((range1 == NULL) || (range2 == NULL))
 246         return(0);
 247     if (range1->type != range2->type)
 248         return(0);
 249     if (range1->type != XPATH_RANGE)
 250         return(0);
 251     if (range1->user != range2->user)
 252         return(0);
 253     if (range1->index != range2->index)
 254         return(0);
 255     if (range1->user2 != range2->user2)
 256         return(0);
 257     if (range1->index2 != range2->index2)
 258         return(0);
 259     return(1);
 260 }
 261
 262 /**
 263  * xmlXPtrNewRange:
 264  * @start:  the starting node
 265  * @startindex:  the start index
 266  * @end:  the ending point
 267  * @endindex:  the ending index
 268  *
 269  * Create a new xmlXPathObjectPtr of type range
 270  *
 271  * Returns the newly created object.
 272  */
 273 xmlXPathObjectPtr
 274 xmlXPtrNewRange(xmlNodePtr start, int startindex,
 275                 xmlNodePtr end, int endindex) {
 276     xmlXPathObjectPtr ret;
 277
 278     if (start == NULL)
 279         return(NULL);
 280     if (end == NULL)
 281         return(NULL);
 282     if (startindex < 0)
 283         return(NULL);
 284     if (endindex < 0)
 285         return(NULL);
 286
 287     ret = (xmlXPathObjectPtr) xmlMalloc(sizeof(xmlXPathObject));
 288     if (ret == NULL) {
 289         xmlGenericError(xmlGenericErrorContext,
 290                 "xmlXPtrNewRange: out of memory\n");
 291         return(NULL);
 292     }
 293     memset(ret, 0 , (size_t) sizeof(xmlXPathObject));
 294     ret->type = XPATH_RANGE;
 295     ret->user = start;
 296     ret->index = startindex;
 297     ret->user2 = end;
 298     ret->index2 = endindex;
 299     xmlXPtrRangeCheckOrder(ret);
 300     return(ret);
 301 }
 302
 303 /**
 304  * xmlXPtrNewRangePoints:
 305  * @start:  the starting point
 306  * @end:  the ending point
 307  *
 308  * Create a new xmlXPathObjectPtr of type range using 2 Points
 309  *
 310  * Returns the newly created object.
 311  */
 312 xmlXPathObjectPtr
 313 xmlXPtrNewRangePoints(xmlXPathObjectPtr start, xmlXPathObjectPtr end) {
 314     xmlXPathObjectPtr ret;
 315
 316     if (start == NULL)
 317         return(NULL);
 318     if (end == NULL)
 319         return(NULL);
 320     if (start->type != XPATH_POINT)
 321         return(NULL);
 322     if (end->type != XPATH_POINT)
 323         return(NULL);
 324
 325     ret = (xmlXPathObjectPtr) xmlMalloc(sizeof(xmlXPathObject));
 326     if (ret == NULL) {
 327         xmlGenericError(xmlGenericErrorContext,
 328                 "xmlXPtrNewRangePoints: out of memory\n");
 329         return(NULL);
 330     }
 331     memset(ret, 0 , (size_t) sizeof(xmlXPathObject));
 332     ret->type = XPATH_RANGE;
 333     ret->user = start->user;
 334     ret->index = start->index;
 335     ret->user2 = end->user;
 336     ret->index2 = end->index;
 337     xmlXPtrRangeCheckOrder(ret);
 338     return(ret);
 339 }
 340
 341 /**
 342  * xmlXPtrNewRangePointNode:
 343  * @start:  the starting point
 344  * @end:  the ending node
 345  *
 346  * Create a new xmlXPathObjectPtr of type range from a point to a node
 347  *
 348  * Returns the newly created object.
 349  */
 350 xmlXPathObjectPtr
 351 xmlXPtrNewRangePointNode(xmlXPathObjectPtr start, xmlNodePtr end) {
 352     xmlXPathObjectPtr ret;
 353
 354     if (start == NULL)
 355         return(NULL);
 356     if (end == NULL)
 357         return(NULL);
 358     if (start->type != XPATH_POINT)
 359         return(NULL);
 360
 361     ret = (xmlXPathObjectPtr) xmlMalloc(sizeof(xmlXPathObject));
 362     if (ret == NULL) {
 363         xmlGenericError(xmlGenericErrorContext,
 364                 "xmlXPtrNewRangePointNode: out of memory\n");
 365         return(NULL);
 366     }
 367     memset(ret, 0 , (size_t) sizeof(xmlXPathObject));
 368     ret->type = XPATH_RANGE;
 369     ret->user = start->user;
 370     ret->index = start->index;
 371     ret->user2 = end;
 372     ret->index2 = -1;
 373     xmlXPtrRangeCheckOrder(ret);
 374     return(ret);
 375 }
 376
 377 /**
 378  * xmlXPtrNewRangeNodePoint:
 379  * @start:  the starting node
 380  * @end:  the ending point
 381  *
 382  * Create a new xmlXPathObjectPtr of type range from a node to a point
 383  *
 384  * Returns the newly created object.
 385  */
 386 xmlXPathObjectPtr
 387 xmlXPtrNewRangeNodePoint(xmlNodePtr start, xmlXPathObjectPtr end) {
 388     xmlXPathObjectPtr ret;
 389
 390     if (start == NULL)
 391         return(NULL);
 392     if (end == NULL)
 393         return(NULL);
 394     if (start->type != XPATH_POINT)
 395         return(NULL);
 396     if (end->type != XPATH_POINT)
 397         return(NULL);
 398
 399     ret = (xmlXPathObjectPtr) xmlMalloc(sizeof(xmlXPathObject));
 400     if (ret == NULL) {
 401         xmlGenericError(xmlGenericErrorContext,
 402                 "xmlXPtrNewRangeNodePoint: out of memory\n");
 403         return(NULL);
 404     }
 405     memset(ret, 0 , (size_t) sizeof(xmlXPathObject));
 406     ret->type = XPATH_RANGE;
 407     ret->user = start;
 408     ret->index = -1;
 409     ret->user2 = end->user;
 410     ret->index2 = end->index;
 411     xmlXPtrRangeCheckOrder(ret);
 412     return(ret);
 413 }
 414
 415 /**
 416  * xmlXPtrNewRangeNodes:
 417  * @start:  the starting node
 418  * @end:  the ending node
 419  *
 420  * Create a new xmlXPathObjectPtr of type range using 2 nodes
 421  *
 422  * Returns the newly created object.
 423  */
 424 xmlXPathObjectPtr
 425 xmlXPtrNewRangeNodes(xmlNodePtr start, xmlNodePtr end) {
 426     xmlXPathObjectPtr ret;
 427
 428     if (start == NULL)
 429         return(NULL);
 430     if (end == NULL)
 431         return(NULL);
 432
 433     ret = (xmlXPathObjectPtr) xmlMalloc(sizeof(xmlXPathObject));
 434     if (ret == NULL) {
 435         xmlGenericError(xmlGenericErrorContext,
 436                 "xmlXPtrNewRangeNodes: out of memory\n");
 437         return(NULL);
 438     }
 439     memset(ret, 0 , (size_t) sizeof(xmlXPathObject));
 440     ret->type = XPATH_RANGE;
 441     ret->user = start;
 442     ret->index = -1;
 443     ret->user2 = end;
 444     ret->index2 = -1;
 445     xmlXPtrRangeCheckOrder(ret);
 446     return(ret);
 447 }
 448
 449 /**
 450  * xmlXPtrNewCollapsedRange:
 451  * @start:  the starting and ending node
 452  *
 453  * Create a new xmlXPathObjectPtr of type range using a single nodes
 454  *
 455  * Returns the newly created object.
 456  */
 457 xmlXPathObjectPtr
 458 xmlXPtrNewCollapsedRange(xmlNodePtr start) {
 459     xmlXPathObjectPtr ret;
 460
 461     if (start == NULL)
 462         return(NULL);
 463
 464     ret = (xmlXPathObjectPtr) xmlMalloc(sizeof(xmlXPathObject));
 465     if (ret == NULL) {
 466         xmlGenericError(xmlGenericErrorContext,
 467                 "xmlXPtrNewCollapsedRange: out of memory\n");
 468         return(NULL);
 469     }
 470     memset(ret, 0 , (size_t) sizeof(xmlXPathObject));
 471     ret->type = XPATH_RANGE;
 472     ret->user = start;
 473     ret->index = -1;
 474     ret->user2 = NULL;
 475     ret->index2 = -1;
 476     return(ret);
 477 }
 478
 479 /**
 480  * xmlXPtrNewRangeNodeObject:
 481  * @start:  the starting node
 482  * @end:  the ending object
 483  *
 484  * Create a new xmlXPathObjectPtr of type range from a not to an object
 485  *
 486  * Returns the newly created object.
 487  */
 488 xmlXPathObjectPtr
 489 xmlXPtrNewRangeNodeObject(xmlNodePtr start, xmlXPathObjectPtr end) {
 490     xmlXPathObjectPtr ret;
 491
 492     if (start == NULL)
 493         return(NULL);
 494     if (end == NULL)
 495         return(NULL);
 496     switch (end->type) {
 497         case XPATH_POINT:
 498             break;
 499         case XPATH_NODESET:
 500             /*
 501              * Empty set ...
 502              */
 503             if (end->nodesetval->nodeNr <= 0)
 504                 return(NULL);
 505             break;
 506         default:
 507             TODO
 508             return(NULL);
 509     }
 510
 511     ret = (xmlXPathObjectPtr) xmlMalloc(sizeof(xmlXPathObject));
 512     if (ret == NULL) {
 513         xmlGenericError(xmlGenericErrorContext,
 514                 "xmlXPtrNewRangeNodeObject: out of memory\n");
 515         return(NULL);
 516     }
 517     memset(ret, 0 , (size_t) sizeof(xmlXPathObject));
 518     ret->type = XPATH_RANGE;
 519     ret->user = start;
 520     ret->index = -1;
 521     switch (end->type) {
 522         case XPATH_POINT:
 523             ret->user2 = end->user;
 524             ret->index2 = end->index;
 525         case XPATH_NODESET: {
 526             ret->user2 = end->nodesetval->nodeTab[end->nodesetval->nodeNr - 1];
 527             ret->index2 = -1;
 528             break;
 529         }
 530         default:
 531             STRANGE
 532             return(NULL);
 533     }
 534     xmlXPtrRangeCheckOrder(ret);
 535     return(ret);
 536 }
 537
 538 #define XML_RANGESET_DEFAULT    10
 539
 540 /**
 541  * xmlXPtrLocationSetCreate:
 542  * @val:  an initial xmlXPathObjectPtr, or NULL
 543  *
 544  * Create a new xmlLocationSetPtr of type double and of value @val
 545  *
 546  * Returns the newly created object.
 547  */
 548 xmlLocationSetPtr
 549 xmlXPtrLocationSetCreate(xmlXPathObjectPtr val) {
 550     xmlLocationSetPtr ret;
 551
 552     ret = (xmlLocationSetPtr) xmlMalloc(sizeof(xmlLocationSet));
 553     if (ret == NULL) {
 554         xmlGenericError(xmlGenericErrorContext,
 555                 "xmlXPtrLocationSetCreate: out of memory\n");
 556         return(NULL);
 557     }
 558     memset(ret, 0 , (size_t) sizeof(xmlLocationSet));
 559     if (val != NULL) {
 560         ret->locTab = (xmlXPathObjectPtr *) xmlMalloc(XML_RANGESET_DEFAULT *
 561                                              sizeof(xmlXPathObjectPtr));
 562         if (ret->locTab == NULL) {
 563             xmlGenericError(xmlGenericErrorContext,
 564                     "xmlXPtrLocationSetCreate: out of memory\n");
 565             return(NULL);
 566         }
 567         memset(ret->locTab, 0 ,
 568                XML_RANGESET_DEFAULT * (size_t) sizeof(xmlXPathObjectPtr));
 569         ret->locMax = XML_RANGESET_DEFAULT;
 570         ret->locTab[ret->locNr++] = val;
 571     }
 572     return(ret);
 573 }
 574
 575 /**
 576  * xmlXPtrLocationSetAdd:
 577  * @cur:  the initial range set
 578  * @val:  a new xmlXPathObjectPtr
 579  *
 580  * add a new xmlXPathObjectPtr to an existing LocationSet
 581  * If the location already exist in the set @val is freed.
 582  */
 583 void
 584 xmlXPtrLocationSetAdd(xmlLocationSetPtr cur, xmlXPathObjectPtr val) {
 585     int i;
 586
 587     if (val == NULL) return;
 588
 589     /*
 590      * check against doublons
 591      */
 592     for (i = 0;i < cur->locNr;i++) {
 593         if (xmlXPtrRangesEqual(cur->locTab[i], val)) {
 594             xmlXPathFreeObject(val);
 595             return;
 596         }
 597     }
 598
 599     /*
 600      * grow the locTab if needed
 601      */
 602     if (cur->locMax == 0) {
 603         cur->locTab = (xmlXPathObjectPtr *) xmlMalloc(XML_RANGESET_DEFAULT *
 604                                              sizeof(xmlXPathObjectPtr));
 605         if (cur->locTab == NULL) {
 606             xmlGenericError(xmlGenericErrorContext,
 607                     "xmlXPtrLocationSetAdd: out of memory\n");
 608             return;
 609         }
 610         memset(cur->locTab, 0 ,
 611                XML_RANGESET_DEFAULT * (size_t) sizeof(xmlXPathObjectPtr));
 612         cur->locMax = XML_RANGESET_DEFAULT;
 613     } else if (cur->locNr == cur->locMax) {
 614         xmlXPathObjectPtr *temp;
 615
 616         cur->locMax *= 2;
 617         temp = (xmlXPathObjectPtr *) xmlRealloc(cur->locTab, cur->locMax *
 618                                       sizeof(xmlXPathObjectPtr));
 619         if (temp == NULL) {
 620             xmlGenericError(xmlGenericErrorContext,
 621                     "xmlXPtrLocationSetAdd: out of memory\n");
 622             return;
 623         }
 624         cur->locTab = temp;
 625     }
 626     cur->locTab[cur->locNr++] = val;
 627 }
 628
 629 /**
 630  * xmlXPtrLocationSetMerge:
 631  * @val1:  the first LocationSet
 632  * @val2:  the second LocationSet
 633  *
 634  * Merges two rangesets, all ranges from @val2 are added to @val1
 635  *
 636  * Returns val1 once extended or NULL in case of error.
 637  */
 638 xmlLocationSetPtr
 639 xmlXPtrLocationSetMerge(xmlLocationSetPtr val1, xmlLocationSetPtr val2) {
 640     int i;
 641
 642     if (val1 == NULL) return(NULL);
 643     if (val2 == NULL) return(val1);
 644
 645     /*
 646      * !!!!! this can be optimized a lot, knowing that both
 647      *       val1 and val2 already have unicity of their values.
 648      */
 649
 650     for (i = 0;i < val2->locNr;i++)
 651         xmlXPtrLocationSetAdd(val1, val2->locTab[i]);
 652
 653     return(val1);
 654 }
 655
 656 /**
 657  * xmlXPtrLocationSetDel:
 658  * @cur:  the initial range set
 659  * @val:  an xmlXPathObjectPtr
 660  *
 661  * Removes an xmlXPathObjectPtr from an existing LocationSet
 662  */
 663 void
 664 xmlXPtrLocationSetDel(xmlLocationSetPtr cur, xmlXPathObjectPtr val) {
 665     int i;
 666
 667     if (cur == NULL) return;
 668     if (val == NULL) return;
 669
 670     /*
 671      * check against doublons
 672      */
 673     for (i = 0;i < cur->locNr;i++)
 674         if (cur->locTab[i] == val) break;
 675
 676     if (i >= cur->locNr) {
 677 #ifdef DEBUG
 678         xmlGenericError(xmlGenericErrorContext,
 679                 "xmlXPtrLocationSetDel: Range wasn't found in RangeList\n");
 680 #endif
 681         return;
 682     }
 683     cur->locNr--;
 684     for (;i < cur->locNr;i++)
 685         cur->locTab[i] = cur->locTab[i + 1];
 686     cur->locTab[cur->locNr] = NULL;
 687 }
 688
 689 /**
 690  * xmlXPtrLocationSetRemove:
 691  * @cur:  the initial range set
 692  * @val:  the index to remove
 693  *
 694  * Removes an entry from an existing LocationSet list.
 695  */
 696 void
 697 xmlXPtrLocationSetRemove(xmlLocationSetPtr cur, int val) {
 698     if (cur == NULL) return;
 699     if (val >= cur->locNr) return;
 700     cur->locNr--;
 701     for (;val < cur->locNr;val++)
 702         cur->locTab[val] = cur->locTab[val + 1];
 703     cur->locTab[cur->locNr] = NULL;
 704 }
 705
 706 /**
 707  * xmlXPtrFreeLocationSet:
 708  * @obj:  the xmlLocationSetPtr to free
 709  *
 710  * Free the LocationSet compound (not the actual ranges !).
 711  */
 712 void
 713 xmlXPtrFreeLocationSet(xmlLocationSetPtr obj) {
 714     int i;
 715
 716     if (obj == NULL) return;
 717     if (obj->locTab != NULL) {
 718         for (i = 0;i < obj->locNr; i++) {
 719             xmlXPathFreeObject(obj->locTab[i]);
 720         }
 721         xmlFree(obj->locTab);
 722     }
 723     xmlFree(obj);
 724 }
 725
 726 /**
 727  * xmlXPtrNewLocationSetNodes:
 728  * @start:  the start NodePtr value
 729  * @end:  the end NodePtr value or NULL
 730  *
 731  * Create a new xmlXPathObjectPtr of type LocationSet and initialize
 732  * it with the single range made of the two nodes @start and @end
 733  *
 734  * Returns the newly created object.
 735  */
 736 xmlXPathObjectPtr
 737 xmlXPtrNewLocationSetNodes(xmlNodePtr start, xmlNodePtr end) {
 738     xmlXPathObjectPtr ret;
 739
 740     ret = (xmlXPathObjectPtr) xmlMalloc(sizeof(xmlXPathObject));
 741     if (ret == NULL) {
 742         xmlGenericError(xmlGenericErrorContext,
 743                 "xmlXPtrNewLocationSetNodes: out of memory\n");
 744         return(NULL);
 745     }
 746     memset(ret, 0 , (size_t) sizeof(xmlXPathObject));
 747     ret->type = XPATH_LOCATIONSET;
 748     if (end == NULL)
 749         ret->user = xmlXPtrLocationSetCreate(xmlXPtrNewCollapsedRange(start));
 750     else
 751         ret->user = xmlXPtrLocationSetCreate(xmlXPtrNewRangeNodes(start,end));
 752     return(ret);
 753 }
 754
 755 /**
 756  * xmlXPtrNewLocationSetNodeSet:
 757  * @set:  a node set
 758  *
 759  * Create a new xmlXPathObjectPtr of type LocationSet and initialize
 760  * it with all the nodes from @set
 761  *
 762  * Returns the newly created object.
 763  */
 764 xmlXPathObjectPtr
 765 xmlXPtrNewLocationSetNodeSet(xmlNodeSetPtr set) {
 766     xmlXPathObjectPtr ret;
 767
 768     ret = (xmlXPathObjectPtr) xmlMalloc(sizeof(xmlXPathObject));
 769     if (ret == NULL) {
 770         xmlGenericError(xmlGenericErrorContext,
 771                 "xmlXPtrNewLocationSetNodeSet: out of memory\n");
 772         return(NULL);
 773     }
 774     memset(ret, 0 , (size_t) sizeof(xmlXPathObject));
 775     ret->type = XPATH_LOCATIONSET;
 776     if (set != NULL) {
 777         int i;
 778         xmlLocationSetPtr newset;
 779
 780         newset = xmlXPtrLocationSetCreate(NULL);
 781         if (newset == NULL)
 782             return(ret);
 783
 784         for (i = 0;i < set->nodeNr;i++)
 785             xmlXPtrLocationSetAdd(newset,
 786                         xmlXPtrNewCollapsedRange(set->nodeTab[i]));
 787
 788         ret->user = (void *) newset;
 789     }
 790     return(ret);
 791 }
 792
 793 /**
 794  * xmlXPtrWrapLocationSet:
 795  * @val:  the LocationSet value
 796  *
 797  * Wrap the LocationSet @val in a new xmlXPathObjectPtr
 798  *
 799  * Returns the newly created object.
 800  */
 801 xmlXPathObjectPtr
 802 xmlXPtrWrapLocationSet(xmlLocationSetPtr val) {
 803     xmlXPathObjectPtr ret;
 804
 805     ret = (xmlXPathObjectPtr) xmlMalloc(sizeof(xmlXPathObject));
 806     if (ret == NULL) {
 807         xmlGenericError(xmlGenericErrorContext,
 808                 "xmlXPtrWrapLocationSet: out of memory\n");
 809         return(NULL);
 810     }
 811     memset(ret, 0 , (size_t) sizeof(xmlXPathObject));
 812     ret->type = XPATH_LOCATIONSET;
 813     ret->user = (void *) val;
 814     return(ret);
 815 }
 816
 817 /************************************************************************
 818  *                                                                      *
 819  *                      The parser                                      *
 820  *                                                                      *
 821  ************************************************************************/
 822
 823 static void xmlXPtrEvalChildSeq(xmlXPathParserContextPtr ctxt, xmlChar *name);
 824
 825 /*
 826  * Macros for accessing the content. Those should be used only by the parser,
 827  * and not exported.
 828  *
 829  * Dirty macros, i.e. one need to make assumption on the context to use them
 830  *
 831  *   CUR_PTR return the current pointer to the xmlChar to be parsed.
 832  *   CUR     returns the current xmlChar value, i.e. a 8 bit value
 833  *           in ISO-Latin or UTF-8.
 834  *           This should be used internally by the parser
 835  *           only to compare to ASCII values otherwise it would break when
 836  *           running with UTF-8 encoding.
 837  *   NXT(n)  returns the n'th next xmlChar. Same as CUR is should be used only
 838  *           to compare on ASCII based substring.
 839  *   SKIP(n) Skip n xmlChar, and must also be used only to skip ASCII defined
 840  *           strings within the parser.
 841  *   CURRENT Returns the current char value, with the full decoding of
 842  *           UTF-8 if we are using this mode. It returns an int.
 843  *   NEXT    Skip to the next character, this does the proper decoding
 844  *           in UTF-8 mode. It also pop-up unfinished entities on the fly.
 845  *           It returns the pointer to the current xmlChar.
 846  */
 847
 848 #define CUR (*ctxt->cur)
 849 #define SKIP(val) ctxt->cur += (val)
 850 #define NXT(val) ctxt->cur[(val)]
 851 #define CUR_PTR ctxt->cur
 852
 853 #define SKIP_BLANKS                                                     \
 854     while (IS_BLANK(*(ctxt->cur))) NEXT
 855
 856 #define CURRENT (*ctxt->cur)
 857 #define NEXT ((*ctxt->cur) ?  ctxt->cur++: ctxt->cur)
 858
 859 /*
 860  * xmlXPtrGetChildNo:
 861  * @ctxt:  the XPointer Parser context
 862  * @index:  the child number
 863  *
 864  * Move the current node of the nodeset on the stack to the
 865  * given child if found
 866  */
 867 static void
 868 xmlXPtrGetChildNo(xmlXPathParserContextPtr ctxt, int indx) {
 869     xmlNodePtr cur = NULL;
 870     xmlXPathObjectPtr obj;
 871     xmlNodeSetPtr oldset;
 872
 873     CHECK_TYPE(XPATH_NODESET);
 874     obj = valuePop(ctxt);
 875     oldset = obj->nodesetval;
 876     if ((indx <= 0) || (oldset == NULL) || (oldset->nodeNr != 1)) {
 877         xmlXPathFreeObject(obj);
 878         valuePush(ctxt, xmlXPathNewNodeSet(NULL));
 879         return;
 880     }
 881     cur = xmlXPtrGetNthChild(oldset->nodeTab[0], indx);
 882     if (cur == NULL) {
 883         xmlXPathFreeObject(obj);
 884         valuePush(ctxt, xmlXPathNewNodeSet(NULL));
 885         return;
 886     }
 887     oldset->nodeTab[0] = cur;
 888     valuePush(ctxt, obj);
 889 }
 890
 891 /**
 892  * xmlXPtrEvalXPtrPart:
 893  * @ctxt:  the XPointer Parser context
 894  * @name:  the preparsed Scheme for the XPtrPart
 895  *
 896  * XPtrPart ::= 'xpointer' '(' XPtrExpr ')'
 897  *            | Scheme '(' SchemeSpecificExpr ')'
 898  *
 899  * Scheme   ::=  NCName - 'xpointer' [VC: Non-XPointer schemes]
 900  *
 901  * SchemeSpecificExpr ::= StringWithBalancedParens
 902  *
 903  * StringWithBalancedParens ::=
 904  *              [^()]* ('(' StringWithBalancedParens ')' [^()]*)*
 905  *              [VC: Parenthesis escaping]
 906  *
 907  * XPtrExpr ::= Expr [VC: Parenthesis escaping]
 908  *
 909  * VC: Parenthesis escaping:
 910  *   The end of an XPointer part is signaled by the right parenthesis ")"
 911  *   character that is balanced with the left parenthesis "(" character
 912  *   that began the part. Any unbalanced parenthesis character inside the
 913  *   expression, even within literals, must be escaped with a circumflex (^)
 914  *   character preceding it. If the expression contains any literal
 915  *   occurrences of the circumflex, each must be escaped with an additional
 916  *   circumflex (that is, ^^). If the unescaped parentheses in the expression
 917  *   are not balanced, a syntax error results.
 918  *
 919  * Parse and evaluate an XPtrPart. Basically it generates the unescaped
 920  * string and if the scheme is 'xpointer' it will call the XPath interpreter.
 921  *
 922  * TODO: there is no new scheme registration mechanism
 923  */
 924
 925 static void
 926 xmlXPtrEvalXPtrPart(xmlXPathParserContextPtr ctxt, xmlChar *name) {
 927     xmlChar *buffer, *cur;
 928     int len;
 929     int level;
 930
 931     if (name == NULL)
 932     name = xmlXPathParseName(ctxt);
 933     if (name == NULL)
 934         XP_ERROR(XPATH_EXPR_ERROR);
 935
 936     if (CUR != '(')
 937         XP_ERROR(XPATH_EXPR_ERROR);
 938     NEXT;
 939     level = 1;
 940
 941     len = xmlStrlen(ctxt->cur);
 942     len++;
 943     buffer = (xmlChar *) xmlMallocAtomic(len * sizeof (xmlChar));
 944     if (buffer == NULL) {
 945         xmlGenericError(xmlGenericErrorContext,
 946                 "xmlXPtrEvalXPtrPart: out of memory\n");
 947         return;
 948     }
 949
 950     cur = buffer;
 951     while (CUR != 0) {
 952         if (CUR == ')') {
 953             level--;
 954             if (level == 0) {
 955                 NEXT;
 956                 break;
 957             }
 958             *cur++ = CUR;
 959         } else if (CUR == '(') {
 960             level++;
 961             *cur++ = CUR;
 962         } else if (CUR == '^') {
 963             NEXT;
 964             if ((CUR == ')') || (CUR == '(') || (CUR == '^')) {
 965                 *cur++ = CUR;
 966             } else {
 967                 *cur++ = '^';
 968                 *cur++ = CUR;
 969             }
 970         } else {
 971             *cur++ = CUR;
 972         }
 973         NEXT;
 974     }
 975     *cur = 0;
 976
 977     if ((level != 0) && (CUR == 0)) {
 978         xmlFree(buffer);
 979         XP_ERROR(XPTR_SYNTAX_ERROR);
 980     }
 981
 982     if (xmlStrEqual(name, (xmlChar *) "xpointer")) {
 983         const xmlChar *left = CUR_PTR;
 984
 985         CUR_PTR = buffer;
 986         xmlXPathEvalExpr(ctxt);
 987         CUR_PTR=left;
 988     } else if (xmlStrEqual(name, (xmlChar *) "element")) {
 989         const xmlChar *left = CUR_PTR;
 990         xmlChar *name2;
 991
 992         CUR_PTR = buffer;
 993         if (buffer[0] == '/') {
 994             xmlXPathRoot(ctxt);
 995             xmlXPtrEvalChildSeq(ctxt, NULL);
 996         } else {
 997             name2 = xmlXPathParseName(ctxt);
 998             if (name2 == NULL) {
 999                 CUR_PTR = left;
1000                 xmlFree(buffer);
1001                 XP_ERROR(XPATH_EXPR_ERROR);
1002             }
1003             xmlXPtrEvalChildSeq(ctxt, name2);
1004         }
1005         CUR_PTR = left;
1006 #ifdef XPTR_XMLNS_SCHEME
1007     } else if (xmlStrEqual(name, (xmlChar *) "xmlns")) {
1008         const xmlChar *left = CUR_PTR;
1009         xmlChar *prefix;
1010         xmlChar *URI;
1011         xmlURIPtr value;
1012
1013         CUR_PTR = buffer;
1014         prefix = xmlXPathParseNCName(ctxt);
1015         if (prefix == NULL) {
1016             xmlFree(buffer);
1017             xmlFree(name);
1018             XP_ERROR(XPTR_SYNTAX_ERROR);
1019         }
1020         SKIP_BLANKS;
1021         if (CUR != '=') {
1022             xmlFree(prefix);
1023             xmlFree(buffer);
1024             xmlFree(name);
1025             XP_ERROR(XPTR_SYNTAX_ERROR);
1026         }
1027         NEXT;
1028         SKIP_BLANKS;
1029         /* @@ check escaping in the XPointer WD */
1030
1031         value = xmlParseURI((const char *)ctxt->cur);
1032         if (value == NULL) {
1033             xmlFree(prefix);
1034             xmlFree(buffer);
1035             xmlFree(name);
1036             XP_ERROR(XPTR_SYNTAX_ERROR);
1037         }
1038         URI = xmlSaveUri(value);
1039         xmlFreeURI(value);
1040         if (URI == NULL) {
1041             xmlFree(prefix);
1042             xmlFree(buffer);
1043             xmlFree(name);
1044             XP_ERROR(XPATH_MEMORY_ERROR);
1045         }
1046
1047         xmlXPathRegisterNs(ctxt->context, prefix, URI);
1048         CUR_PTR = left;
1049         xmlFree(URI);
1050         xmlFree(prefix);
1051 #endif /* XPTR_XMLNS_SCHEME */
1052     } else {
1053         xmlGenericError(xmlGenericErrorContext,
1054                 "unsupported scheme '%s'\n", name);
1055     }
1056     xmlFree(buffer);
1057     xmlFree(name);
1058 }
1059
1060 /**
1061  * xmlXPtrEvalFullXPtr:
1062  * @ctxt:  the XPointer Parser context
1063  * @name:  the preparsed Scheme for the first XPtrPart
1064  *
1065  * FullXPtr ::= XPtrPart (S? XPtrPart)*
1066  *
1067  * As the specs says:
1068  * -----------
1069  * When multiple XPtrParts are provided, they must be evaluated in
1070  * left-to-right order. If evaluation of one part fails, the nexti
1071  * is evaluated. The following conditions cause XPointer part failure:
1072  *
1073  * - An unknown scheme
1074  * - A scheme that does not locate any sub-resource present in the resource
1075  * - A scheme that is not applicable to the media type of the resource
1076  *
1077  * The XPointer application must consume a failed XPointer part and
1078  * attempt to evaluate the next one, if any. The result of the first
1079  * XPointer part whose evaluation succeeds is taken to be the fragment
1080  * located by the XPointer as a whole. If all the parts fail, the result
1081  * for the XPointer as a whole is a sub-resource error.
1082  * -----------
1083  *
1084  * Parse and evaluate a Full XPtr i.e. possibly a cascade of XPath based
1085  * expressions or other schemes.
1086  */
1087 static void
1088 xmlXPtrEvalFullXPtr(xmlXPathParserContextPtr ctxt, xmlChar *name) {
1089     if (name == NULL)
1090     name = xmlXPathParseName(ctxt);
1091     if (name == NULL)
1092         XP_ERROR(XPATH_EXPR_ERROR);
1093     while (name != NULL) {
1094         xmlXPtrEvalXPtrPart(ctxt, name);
1095
1096         /* in case of syntax error, break here */
1097         if (ctxt->error != XPATH_EXPRESSION_OK)
1098             return;
1099
1100         /*
1101          * If the returned value is a non-empty nodeset
1102          * or location set, return here.
1103          */
1104         if (ctxt->value != NULL) {
1105             xmlXPathObjectPtr obj = ctxt->value;
1106
1107             switch (obj->type) {
1108                 case XPATH_LOCATIONSET: {
1109                     xmlLocationSetPtr loc = ctxt->value->user;
1110                     if ((loc != NULL) && (loc->locNr > 0))
1111                         return;
1112                     break;
1113                 }
1114                 case XPATH_NODESET: {
1115                     xmlNodeSetPtr loc = ctxt->value->nodesetval;
1116                     if ((loc != NULL) && (loc->nodeNr > 0))
1117                         return;
1118                     break;
1119                 }
1120                 default:
1121                     break;
1122             }
1123
1124             /*
1125              * Evaluating to improper values is equivalent to
1126              * a sub-resource error, clean-up the stack
1127              */
1128             do {
1129                 obj = valuePop(ctxt);
1130                 if (obj != NULL) {
1131                     xmlXPathFreeObject(obj);
1132                 }
1133             } while (obj != NULL);
1134         }
1135
1136         /*
1137          * Is there another XPointer part.
1138          */
1139         SKIP_BLANKS;
1140         name = xmlXPathParseName(ctxt);
1141     }
1142 }
1143
1144 /**
1145  * xmlXPtrEvalChildSeq:
1146  * @ctxt:  the XPointer Parser context
1147  * @name:  a possible ID name of the child sequence
1148  *
1149  *  ChildSeq ::= '/1' ('/' [0-9]*)*
1150  *             | Name ('/' [0-9]*)+
1151  *
1152  * Parse and evaluate a Child Sequence. This routine also handle the
1153  * case of a Bare Name used to get a document ID.
1154  */
1155 static void
1156 xmlXPtrEvalChildSeq(xmlXPathParserContextPtr ctxt, xmlChar *name) {
1157     /*
1158      * XPointer don't allow by syntax to address in mutirooted trees
1159      * this might prove useful in some cases, warn about it.
1160      */
1161     if ((name == NULL) && (CUR == '/') && (NXT(1) != '1')) {
1162         xmlGenericError(xmlGenericErrorContext,
1163                 "warning: ChildSeq not starting by /1\n");
1164     }
1165
1166     if (name != NULL) {
1167         valuePush(ctxt, xmlXPathNewString(name));
1168         xmlFree(name);
1169         xmlXPathIdFunction(ctxt, 1);
1170         CHECK_ERROR;
1171     }
1172
1173     while (CUR == '/') {
1174         int child = 0;
1175         NEXT;
1176
1177         while ((CUR >= '0') && (CUR <= '9')) {
1178             child = child * 10 + (CUR - '0');
1179             NEXT;
1180         }
1181         xmlXPtrGetChildNo(ctxt, child);
1182     }
1183 }
1184
1185
1186 /**
1187  * xmlXPtrEvalXPointer:
1188  * @ctxt:  the XPointer Parser context
1189  *
1190  *  XPointer ::= Name
1191  *             | ChildSeq
1192  *             | FullXPtr
1193  *
1194  * Parse and evaluate an XPointer
1195  */
1196 static void
1197 xmlXPtrEvalXPointer(xmlXPathParserContextPtr ctxt) {
1198     if (ctxt->valueTab == NULL) {
1199         /* Allocate the value stack */
1200         ctxt->valueTab = (xmlXPathObjectPtr *)
1201                          xmlMalloc(10 * sizeof(xmlXPathObjectPtr));
1202         if (ctxt->valueTab == NULL) {
1203             xmlFree(ctxt);
1204             xmlGenericError(xmlGenericErrorContext,
1205                     "xmlXPathEvalXPointer: out of memory\n");
1206             return;
1207         }
1208         ctxt->valueNr = 0;
1209         ctxt->valueMax = 10;
1210         ctxt->value = NULL;
1211     }
1212     SKIP_BLANKS;
1213     if (CUR == '/') {
1214         xmlXPathRoot(ctxt);
1215         xmlXPtrEvalChildSeq(ctxt, NULL);
1216     } else {
1217         xmlChar *name;
1218
1219         name = xmlXPathParseName(ctxt);
1220         if (name == NULL)
1221             XP_ERROR(XPATH_EXPR_ERROR);
1222         if (CUR == '(') {
1223             xmlXPtrEvalFullXPtr(ctxt, name);
1224             /* Short evaluation */
1225             return;
1226         } else {
1227             /* this handle both Bare Names and Child Sequences */
1228             xmlXPtrEvalChildSeq(ctxt, name);
1229         }
1230     }
1231     SKIP_BLANKS;
1232     if (CUR != 0)
1233         XP_ERROR(XPATH_EXPR_ERROR);
1234 }
1235
1236
1237 /************************************************************************
1238  *                                                                      *
1239  *                      General routines                                *
1240  *                                                                      *
1241  ************************************************************************/
1242
1243 void xmlXPtrStringRangeFunction(xmlXPathParserContextPtr ctxt, int nargs);
1244 void xmlXPtrStartPointFunction(xmlXPathParserContextPtr ctxt, int nargs);
1245 void xmlXPtrEndPointFunction(xmlXPathParserContextPtr ctxt, int nargs);
1246 void xmlXPtrHereFunction(xmlXPathParserContextPtr ctxt, int nargs);
1247 void xmlXPtrOriginFunction(xmlXPathParserContextPtr ctxt, int nargs);
1248 void xmlXPtrRangeInsideFunction(xmlXPathParserContextPtr ctxt, int nargs);
1249 void xmlXPtrRangeFunction(xmlXPathParserContextPtr ctxt, int nargs);
1250
1251 /**
1252  * xmlXPtrNewContext:
1253  * @doc:  the XML document
1254  * @here:  the node that directly contains the XPointer being evaluated or NULL
1255  * @origin:  the element from which a user or program initiated traversal of
1256  *           the link, or NULL.
1257  *
1258  * Create a new XPointer context
1259  *
1260  * Returns the xmlXPathContext just allocated.
1261  */
1262 xmlXPathContextPtr
1263 xmlXPtrNewContext(xmlDocPtr doc, xmlNodePtr here, xmlNodePtr origin) {
1264     xmlXPathContextPtr ret;
1265
1266     ret = xmlXPathNewContext(doc);
1267     if (ret == NULL)
1268         return(ret);
1269     ret->xptr = 1;
1270     ret->here = here;
1271     ret->origin = origin;
1272
1273     xmlXPathRegisterFunc(ret, (xmlChar *)"range-to",
1274                          xmlXPtrRangeToFunction);
1275     xmlXPathRegisterFunc(ret, (xmlChar *)"range",
1276                          xmlXPtrRangeFunction);
1277     xmlXPathRegisterFunc(ret, (xmlChar *)"range-inside",
1278                          xmlXPtrRangeInsideFunction);
1279     xmlXPathRegisterFunc(ret, (xmlChar *)"string-range",
1280                          xmlXPtrStringRangeFunction);
1281     xmlXPathRegisterFunc(ret, (xmlChar *)"start-point",
1282                          xmlXPtrStartPointFunction);
1283     xmlXPathRegisterFunc(ret, (xmlChar *)"end-point",
1284                          xmlXPtrEndPointFunction);
1285     xmlXPathRegisterFunc(ret, (xmlChar *)"here",
1286                          xmlXPtrHereFunction);
1287     xmlXPathRegisterFunc(ret, (xmlChar *)" origin",
1288                          xmlXPtrOriginFunction);
1289
1290     return(ret);
1291 }
1292
1293 /**
1294  * xmlXPtrEval:
1295  * @str:  the XPointer expression
1296  * @ctx:  the XPointer context
1297  *
1298  * Evaluate the XPath Location Path in the given context.
1299  *
1300  * Returns the xmlXPathObjectPtr resulting from the evaluation or NULL.
1301  *         the caller has to free the object.
1302  */
1303 xmlXPathObjectPtr
1304 xmlXPtrEval(const xmlChar *str, xmlXPathContextPtr ctx) {
1305     xmlXPathParserContextPtr ctxt;
1306     xmlXPathObjectPtr res = NULL, tmp;
1307     xmlXPathObjectPtr init = NULL;
1308     int stack = 0;
1309
1310     xmlXPathInit();
1311
1312     if ((ctx == NULL) || (str == NULL))
1313         return(NULL);
1314
1315     ctxt = xmlXPathNewParserContext(str, ctx);
1316     ctxt->xptr = 1;
1317     xmlXPtrEvalXPointer(ctxt);
1318
1319     if ((ctxt->value != NULL) &&
1320         (ctxt->value->type != XPATH_NODESET) &&
1321         (ctxt->value->type != XPATH_LOCATIONSET)) {
1322         xmlGenericError(xmlGenericErrorContext,
1323                 "xmlXPtrEval: evaluation failed to return a node set\n");
1324     } else {
1325         res = valuePop(ctxt);
1326     }
1327
1328     do {
1329         tmp = valuePop(ctxt);
1330         if (tmp != NULL) {
1331             if (tmp != init) {
1332                 if (tmp->type == XPATH_NODESET) {
1333                     /*
1334                      * Evaluation may push a root nodeset which is unused
1335                      */
1336                     xmlNodeSetPtr set;
1337                     set = tmp->nodesetval;
1338                     if ((set->nodeNr != 1) ||
1339                         (set->nodeTab[0] != (xmlNodePtr) ctx->doc))
1340                         stack++;
1341                 } else
1342                     stack++;
1343             }
1344             xmlXPathFreeObject(tmp);
1345         }
1346     } while (tmp != NULL);
1347     if (stack != 0) {
1348         xmlGenericError(xmlGenericErrorContext,
1349                 "xmlXPtrEval: %d object left on the stack\n",
1350                 stack);
1351     }
1352     if (ctxt->error != XPATH_EXPRESSION_OK) {
1353         xmlXPathFreeObject(res);
1354         res = NULL;
1355     }
1356
1357     xmlXPathFreeParserContext(ctxt);
1358     return(res);
1359 }
1360
1361 /**
1362  * xmlXPtrBuildRangeNodeList:
1363  * @range:  a range object
1364  *
1365  * Build a node list tree copy of the range
1366  *
1367  * Returns an xmlNodePtr list or NULL.
1368  *         the caller has to free the node tree.
1369  */
1370 static xmlNodePtr
1371 xmlXPtrBuildRangeNodeList(xmlXPathObjectPtr range) {
1372     /* pointers to generated nodes */
1373     xmlNodePtr list = NULL, last = NULL, parent = NULL, tmp;
1374     /* pointers to traversal nodes */
1375     xmlNodePtr start, cur, end;
1376     int index1, index2;
1377
1378     if (range == NULL)
1379         return(NULL);
1380     if (range->type != XPATH_RANGE)
1381         return(NULL);
1382     start = (xmlNodePtr) range->user;
1383
1384     if (start == NULL)
1385         return(NULL);
1386     end = range->user2;
1387     if (end == NULL)
1388         return(xmlCopyNode(start, 1));
1389
1390     cur = start;
1391     index1 = range->index;
1392     index2 = range->index2;
1393     while (cur != NULL) {
1394         if (cur == end) {
1395             if (cur->type == XML_TEXT_NODE) {
1396                 const xmlChar *content = cur->content;
1397                 int len;
1398
1399                 if (content == NULL) {
1400                     tmp = xmlNewTextLen(NULL, 0);
1401                 } else {
1402                     len = index2;
1403                     if ((cur == start) && (index1 > 1)) {
1404                         content += (index1 - 1);
1405                         len -= (index1 - 1);
1406                         index1 = 0;
1407                     } else {
1408                         len = index2;
1409                     }
1410                     tmp = xmlNewTextLen(content, len);
1411                 }
1412                 /* single sub text node selection */
1413                 if (list == NULL)
1414                     return(tmp);
1415                 /* prune and return full set */
1416                 if (last != NULL)
1417                     xmlAddNextSibling(last, tmp);
1418                 else
1419                     xmlAddChild(parent, tmp);
1420                 return(list);
1421             } else {
1422                 tmp = xmlCopyNode(cur, 0);
1423                 if (list == NULL)
1424                     list = tmp;
1425                 else {
1426                     if (last != NULL)
1427                         xmlAddNextSibling(last, tmp);
1428                     else
1429                         xmlAddChild(parent, tmp);
1430                 }
1431                 last = NULL;
1432                 parent = tmp;
1433
1434                 if (index2 > 1) {
1435                     end = xmlXPtrGetNthChild(cur, index2 - 1);
1436                     index2 = 0;
1437                 }
1438                 if ((cur == start) && (index1 > 1)) {
1439                     cur = xmlXPtrGetNthChild(cur, index1 - 1);
1440                     index1 = 0;
1441                 } else {
1442                     cur = cur->children;
1443                 }
1444                 /*
1445                  * Now gather the remaining nodes from cur to end
1446                  */
1447                 continue; /* while */
1448             }
1449         } else if ((cur == start) &&
1450                    (list == NULL) /* looks superfluous but ... */ ) {
1451             if ((cur->type == XML_TEXT_NODE) ||
1452                 (cur->type == XML_CDATA_SECTION_NODE)) {
1453                 const xmlChar *content = cur->content;
1454
1455                 if (content == NULL) {
1456                     tmp = xmlNewTextLen(NULL, 0);
1457                 } else {
1458                     if (index1 > 1) {
1459                         content += (index1 - 1);
1460                     }
1461                     tmp = xmlNewText(content);
1462                 }
1463                 last = list = tmp;
1464             } else {
1465                 if ((cur == start) && (index1 > 1)) {
1466                     tmp = xmlCopyNode(cur, 0);
1467                     list = tmp;
1468                     parent = tmp;
1469                     last = NULL;
1470                     cur = xmlXPtrGetNthChild(cur, index1 - 1);
1471                     index1 = 0;
1472                     /*
1473                      * Now gather the remaining nodes from cur to end
1474                      */
1475                     continue; /* while */
1476                 }
1477                 tmp = xmlCopyNode(cur, 1);
1478                 list = tmp;
1479                 parent = NULL;
1480                 last = tmp;
1481             }
1482         } else {
1483             tmp = NULL;
1484             switch (cur->type) {
1485                 case XML_DTD_NODE:
1486                 case XML_ELEMENT_DECL:
1487                 case XML_ATTRIBUTE_DECL:
1488                 case XML_ENTITY_NODE:
1489                     /* Do not copy DTD informations */
1490                     break;
1491                 case XML_ENTITY_DECL:
1492                     TODO /* handle crossing entities -> stack needed */
1493                     break;
1494                 case XML_XINCLUDE_START:
1495                 case XML_XINCLUDE_END:
1496                     /* don't consider it part of the tree content */
1497                     break;
1498                 case XML_ATTRIBUTE_NODE:
1499                     /* Humm, should not happen ! */
1500                     STRANGE
1501                     break;
1502                 default:
1503                     tmp = xmlCopyNode(cur, 1);
1504                     break;
1505             }
1506             if (tmp != NULL) {
1507                 if ((list == NULL) || ((last == NULL) && (parent == NULL)))  {
1508                     STRANGE
1509                     return(NULL);
1510                 }
1511                 if (last != NULL)
1512                     xmlAddNextSibling(last, tmp);
1513                 else {
1514                     xmlAddChild(parent, tmp);
1515                     last = tmp;
1516                 }
1517             }
1518         }
1519         /*
1520          * Skip to next node in document order
1521          */
1522         if ((list == NULL) || ((last == NULL) && (parent == NULL)))  {
1523             STRANGE
1524             return(NULL);
1525         }
1526         cur = xmlXPtrAdvanceNode(cur);
1527     }
1528     return(list);
1529 }
1530
1531 /**
1532  * xmlXPtrBuildNodeList:
1533  * @obj:  the XPointer result from the evaluation.
1534  *
1535  * Build a node list tree copy of the XPointer result.
1536  * This will drop Attributes and Namespace declarations.
1537  *
1538  * Returns an xmlNodePtr list or NULL.
1539  *         the caller has to free the node tree.
1540  */
1541 xmlNodePtr
1542 xmlXPtrBuildNodeList(xmlXPathObjectPtr obj) {
1543     xmlNodePtr list = NULL, last = NULL;
1544     int i;
1545
1546     if (obj == NULL)
1547         return(NULL);
1548     switch (obj->type) {
1549         case XPATH_NODESET: {
1550             xmlNodeSetPtr set = obj->nodesetval;
1551             if (set == NULL)
1552                 return(NULL);
1553             for (i = 0;i < set->nodeNr;i++) {
1554                 if (set->nodeTab[i] == NULL)
1555                     continue;
1556                 switch (set->nodeTab[i]->type) {
1557                     case XML_TEXT_NODE:
1558                     case XML_CDATA_SECTION_NODE:
1559                     case XML_ELEMENT_NODE:
1560                     case XML_ENTITY_REF_NODE:
1561                     case XML_ENTITY_NODE:
1562                     case XML_PI_NODE:
1563                     case XML_COMMENT_NODE:
1564                     case XML_DOCUMENT_NODE:
1565                     case XML_HTML_DOCUMENT_NODE:
1566 #ifdef LIBXML_DOCB_ENABLED
1567                     case XML_DOCB_DOCUMENT_NODE:
1568 #endif
1569                     case XML_XINCLUDE_START:
1570                     case XML_XINCLUDE_END:
1571                         break;
1572                     case XML_ATTRIBUTE_NODE:
1573                     case XML_NAMESPACE_DECL:
1574                     case XML_DOCUMENT_TYPE_NODE:
1575                     case XML_DOCUMENT_FRAG_NODE:
1576                     case XML_NOTATION_NODE:
1577                     case XML_DTD_NODE:
1578                     case XML_ELEMENT_DECL:
1579                     case XML_ATTRIBUTE_DECL:
1580                     case XML_ENTITY_DECL:
1581                         continue; /* for */
1582                 }
1583                 if (last == NULL)
1584                     list = last = xmlCopyNode(set->nodeTab[i], 1);
1585                 else {
1586                     xmlAddNextSibling(last, xmlCopyNode(set->nodeTab[i], 1));
1587                     if (last->next != NULL)
1588                         last = last->next;
1589                 }
1590             }
1591             break;
1592         }
1593         case XPATH_LOCATIONSET: {
1594             xmlLocationSetPtr set = (xmlLocationSetPtr) obj->user;
1595             if (set == NULL)
1596                 return(NULL);
1597             for (i = 0;i < set->locNr;i++) {
1598                 if (last == NULL)
1599                     list = last = xmlXPtrBuildNodeList(set->locTab[i]);
1600                 else
1601                     xmlAddNextSibling(last,
1602                             xmlXPtrBuildNodeList(set->locTab[i]));
1603                 if (last != NULL) {
1604                     while (last->next != NULL)
1605                         last = last->next;
1606                 }
1607             }
1608             break;
1609         }
1610         case XPATH_RANGE:
1611             return(xmlXPtrBuildRangeNodeList(obj));
1612         case XPATH_POINT:
1613             return(xmlCopyNode(obj->user, 0));
1614         default:
1615             break;
1616     }
1617     return(list);
1618 }
1619
1620 /************************************************************************
1621  *                                                                      *
1622  *                      XPointer functions                              *
1623  *                                                                      *
1624  ************************************************************************/
1625
1626 /**
1627  * xmlXPtrNbLocChildren:
1628  * @node:  an xmlNodePtr
1629  *
1630  * Count the number of location children of @node or the length of the
1631  * string value in case of text/PI/Comments nodes
1632  *
1633  * Returns the number of location children
1634  */
1635 static int
1636 xmlXPtrNbLocChildren(xmlNodePtr node) {
1637     int ret = 0;
1638     if (node == NULL)
1639         return(-1);
1640     switch (node->type) {
1641         case XML_HTML_DOCUMENT_NODE:
1642         case XML_DOCUMENT_NODE:
1643         case XML_ELEMENT_NODE:
1644             node = node->children;
1645             while (node != NULL) {
1646                 if (node->type == XML_ELEMENT_NODE)
1647                     ret++;
1648                 node = node->next;
1649             }
1650             break;
1651         case XML_ATTRIBUTE_NODE:
1652             return(-1);
1653
1654         case XML_PI_NODE:
1655         case XML_COMMENT_NODE:
1656         case XML_TEXT_NODE:
1657         case XML_CDATA_SECTION_NODE:
1658         case XML_ENTITY_REF_NODE:
1659             ret = xmlStrlen(node->content);
1660             break;
1661         default:
1662             return(-1);
1663     }
1664     return(ret);
1665 }
1666
1667 /**
1668  * xmlXPtrHereFunction:
1669  * @ctxt:  the XPointer Parser context
1670  * @nargs:  the number of args
1671  *
1672  * Function implementing here() operation
1673  * as described in 5.4.3
1674  */
1675 void
1676 xmlXPtrHereFunction(xmlXPathParserContextPtr ctxt, int nargs) {
1677     CHECK_ARITY(0);
1678
1679     if (ctxt->context->here == NULL)
1680         XP_ERROR(XPTR_SYNTAX_ERROR);
1681
1682     valuePush(ctxt, xmlXPtrNewLocationSetNodes(ctxt->context->here, NULL));
1683 }
1684
1685 /**
1686  * xmlXPtrOriginFunction:
1687  * @ctxt:  the XPointer Parser context
1688  * @nargs:  the number of args
1689  *
1690  * Function implementing origin() operation
1691  * as described in 5.4.3
1692  */
1693 void
1694 xmlXPtrOriginFunction(xmlXPathParserContextPtr ctxt, int nargs) {
1695     CHECK_ARITY(0);
1696
1697     if (ctxt->context->origin == NULL)
1698         XP_ERROR(XPTR_SYNTAX_ERROR);
1699
1700     valuePush(ctxt, xmlXPtrNewLocationSetNodes(ctxt->context->origin, NULL));
1701 }
1702
1703 /**
1704  * xmlXPtrStartPointFunction:
1705  * @ctxt:  the XPointer Parser context
1706  * @nargs:  the number of args
1707  *
1708  * Function implementing start-point() operation
1709  * as described in 5.4.3
1710  * ----------------
1711  * location-set start-point(location-set)
1712  *
1713  * For each location x in the argument location-set, start-point adds a
1714  * location of type point to the result location-set. That point represents
1715  * the start point of location x and is determined by the following rules:
1716  *
1717  * - If x is of type point, the start point is x.
1718  * - If x is of type range, the start point is the start point of x.
1719  * - If x is of type root, element, text, comment, or processing instruction,
1720  * - the container node of the start point is x and the index is 0.
1721  * - If x is of type attribute or namespace, the function must signal a
1722  *   syntax error.
1723  * ----------------
1724  *
1725  */
1726 void
1727 xmlXPtrStartPointFunction(xmlXPathParserContextPtr ctxt, int nargs) {
1728     xmlXPathObjectPtr tmp, obj, point;
1729     xmlLocationSetPtr newset = NULL;
1730     xmlLocationSetPtr oldset = NULL;
1731
1732     CHECK_ARITY(1);
1733     if ((ctxt->value == NULL) ||
1734         ((ctxt->value->type != XPATH_LOCATIONSET) &&
1735          (ctxt->value->type != XPATH_NODESET)))
1736         XP_ERROR(XPATH_INVALID_TYPE)
1737
1738     obj = valuePop(ctxt);
1739     if (obj->type == XPATH_NODESET) {
1740         /*
1741          * First convert to a location set
1742          */
1743         tmp = xmlXPtrNewLocationSetNodeSet(obj->nodesetval);
1744         xmlXPathFreeObject(obj);
1745         obj = tmp;
1746     }
1747
1748     newset = xmlXPtrLocationSetCreate(NULL);
1749     if (newset == NULL) {
1750         xmlXPathFreeObject(obj);
1751         XP_ERROR(XPATH_MEMORY_ERROR);
1752     }
1753     oldset = (xmlLocationSetPtr) obj->user;
1754     if (oldset != NULL) {
1755         int i;
1756
1757         for (i = 0; i < oldset->locNr; i++) {
1758             tmp = oldset->locTab[i];
1759             if (tmp == NULL)
1760                 continue;
1761             point = NULL;
1762             switch (tmp->type) {
1763                 case XPATH_POINT:
1764                     point = xmlXPtrNewPoint(tmp->user, tmp->index);
1765                     break;
1766                 case XPATH_RANGE: {
1767                     xmlNodePtr node = tmp->user;
1768                     if (node != NULL) {
1769                         if (node->type == XML_ATTRIBUTE_NODE) {
1770                             /* TODO: Namespace Nodes ??? */
1771                             xmlXPathFreeObject(obj);
1772                             xmlXPtrFreeLocationSet(newset);
1773                             XP_ERROR(XPTR_SYNTAX_ERROR);
1774                         }
1775                         point = xmlXPtrNewPoint(node, tmp->index);
1776                     }
1777                     break;
1778                 }
1779                 default:
1780                     /*** Should we raise an error ?
1781                     xmlXPathFreeObject(obj);
1782                     xmlXPathFreeObject(newset);
1783                     XP_ERROR(XPATH_INVALID_TYPE)
1784                     ***/
1785                     break;
1786             }
1787             if (point != NULL)
1788                 xmlXPtrLocationSetAdd(newset, point);
1789         }
1790     }
1791     xmlXPathFreeObject(obj);
1792     valuePush(ctxt, xmlXPtrWrapLocationSet(newset));
1793 }
1794
1795 /**
1796  * xmlXPtrEndPointFunction:
1797  * @ctxt:  the XPointer Parser context
1798  * @nargs:  the number of args
1799  *
1800  * Function implementing end-point() operation
1801  * as described in 5.4.3
1802  * ----------------------------
1803  * location-set end-point(location-set)
1804  *
1805  * For each location x in the argument location-set, end-point adds a
1806  * location of type point to the result location-set. That point represents
1807  * the end point of location x and is determined by the following rules:
1808  *
1809  * - If x is of type point, the resulting point is x.
1810  * - If x is of type range, the resulting point is the end point of x.
1811  * - If x is of type root or element, the container node of the resulting
1812  *   point is x and the index is the number of location children of x.
1813  * - If x is of type text, comment, or processing instruction, the container
1814  *   node of the resulting point is x and the index is the length of the
1815  *   string-value of x.
1816  * - If x is of type attribute or namespace, the function must signal a
1817  *   syntax error.
1818  * ----------------------------
1819  */
1820 void
1821 xmlXPtrEndPointFunction(xmlXPathParserContextPtr ctxt, int nargs) {
1822     xmlXPathObjectPtr tmp, obj, point;
1823     xmlLocationSetPtr newset = NULL;
1824     xmlLocationSetPtr oldset = NULL;
1825
1826     CHECK_ARITY(1);
1827     if ((ctxt->value == NULL) ||
1828         ((ctxt->value->type != XPATH_LOCATIONSET) &&
1829          (ctxt->value->type != XPATH_NODESET)))
1830         XP_ERROR(XPATH_INVALID_TYPE)
1831
1832     obj = valuePop(ctxt);
1833     if (obj->type == XPATH_NODESET) {
1834         /*
1835          * First convert to a location set
1836          */
1837         tmp = xmlXPtrNewLocationSetNodeSet(obj->nodesetval);
1838         xmlXPathFreeObject(obj);
1839         obj = tmp;
1840     }
1841
1842     newset = xmlXPtrLocationSetCreate(NULL);
1843     oldset = (xmlLocationSetPtr) obj->user;
1844     if (oldset != NULL) {
1845         int i;
1846
1847         for (i = 0; i < oldset->locNr; i++) {
1848             tmp = oldset->locTab[i];
1849             if (tmp == NULL)
1850                 continue;
1851             point = NULL;
1852             switch (tmp->type) {
1853                 case XPATH_POINT:
1854                     point = xmlXPtrNewPoint(tmp->user, tmp->index);
1855                     break;
1856                 case XPATH_RANGE: {
1857                     xmlNodePtr node = tmp->user2;
1858                     if (node != NULL) {
1859                         if (node->type == XML_ATTRIBUTE_NODE) {
1860                             /* TODO: Namespace Nodes ??? */
1861                             xmlXPathFreeObject(obj);
1862                             xmlXPtrFreeLocationSet(newset);
1863                             XP_ERROR(XPTR_SYNTAX_ERROR);
1864                         }
1865                         point = xmlXPtrNewPoint(node, tmp->index2);
1866                     } else if (tmp->user == NULL) {
1867                         point = xmlXPtrNewPoint(node,
1868                                        xmlXPtrNbLocChildren(node));
1869                     }
1870                     break;
1871                 }
1872                 default:
1873                     /*** Should we raise an error ?
1874                     xmlXPathFreeObject(obj);
1875                     xmlXPathFreeObject(newset);
1876                     XP_ERROR(XPATH_INVALID_TYPE)
1877                     ***/
1878                     break;
1879             }
1880             if (point != NULL)
1881                 xmlXPtrLocationSetAdd(newset, point);
1882         }
1883     }
1884     xmlXPathFreeObject(obj);
1885     valuePush(ctxt, xmlXPtrWrapLocationSet(newset));
1886 }
1887
1888
1889 /**
1890  * xmlXPtrCoveringRange:
1891  * @ctxt:  the XPointer Parser context
1892  * @loc:  the location for which the covering range must be computed
1893  *
1894  * A covering range is a range that wholly encompasses a location
1895  * Section 5.3.3. Covering Ranges for All Location Types
1896  *        http://www.w3.org/TR/xptr#N2267
1897  *
1898  * Returns a new location or NULL in case of error
1899  */
1900 static xmlXPathObjectPtr
1901 xmlXPtrCoveringRange(xmlXPathParserContextPtr ctxt, xmlXPathObjectPtr loc) {
1902     if (loc == NULL)
1903         return(NULL);
1904     if ((ctxt == NULL) || (ctxt->context == NULL) ||
1905         (ctxt->context->doc == NULL))
1906         return(NULL);
1907     switch (loc->type) {
1908         case XPATH_POINT:
1909             return(xmlXPtrNewRange(loc->user, loc->index,
1910                                    loc->user, loc->index));
1911         case XPATH_RANGE:
1912             if (loc->user2 != NULL) {
1913                 return(xmlXPtrNewRange(loc->user, loc->index,
1914                                       loc->user2, loc->index2));
1915             } else {
1916                 xmlNodePtr node = (xmlNodePtr) loc->user;
1917                 if (node == (xmlNodePtr) ctxt->context->doc) {
1918                     return(xmlXPtrNewRange(node, 0, node,
1919                                            xmlXPtrGetArity(node)));
1920                 } else {
1921                     switch (node->type) {
1922                         case XML_ATTRIBUTE_NODE:
1923                         /* !!! our model is slightly different than XPath */
1924                             return(xmlXPtrNewRange(node, 0, node,
1925                                                    xmlXPtrGetArity(node)));
1926                         case XML_ELEMENT_NODE:
1927                         case XML_TEXT_NODE:
1928                         case XML_CDATA_SECTION_NODE:
1929                         case XML_ENTITY_REF_NODE:
1930                         case XML_PI_NODE:
1931                         case XML_COMMENT_NODE:
1932                         case XML_DOCUMENT_NODE:
1933                         case XML_NOTATION_NODE:
1934                         case XML_HTML_DOCUMENT_NODE: {
1935                             int indx = xmlXPtrGetIndex(node);
1936
1937                             node = node->parent;
1938                             return(xmlXPtrNewRange(node, indx - 1,
1939                                                    node, indx + 1));
1940                         }
1941                         default:
1942                             return(NULL);
1943                     }
1944                 }
1945             }
1946         default:
1947             TODO /* missed one case ??? */
1948     }
1949     return(NULL);
1950 }
1951
1952 /**
1953  * xmlXPtrRangeFunction:
1954  * @ctxt:  the XPointer Parser context
1955  * @nargs:  the number of args
1956  *
1957  * Function implementing the range() function 5.4.3
1958  *  location-set range(location-set )
1959  *
1960  *  The range function returns ranges covering the locations in
1961  *  the argument location-set. For each location x in the argument
1962  *  location-set, a range location representing the covering range of
1963  *  x is added to the result location-set.
1964  */
1965 void
1966 xmlXPtrRangeFunction(xmlXPathParserContextPtr ctxt, int nargs) {
1967     int i;
1968     xmlXPathObjectPtr set;
1969     xmlLocationSetPtr oldset;
1970     xmlLocationSetPtr newset;
1971
1972     CHECK_ARITY(1);
1973     if ((ctxt->value == NULL) ||
1974         ((ctxt->value->type != XPATH_LOCATIONSET) &&
1975          (ctxt->value->type != XPATH_NODESET)))
1976         XP_ERROR(XPATH_INVALID_TYPE)
1977
1978     set = valuePop(ctxt);
1979     if (set->type == XPATH_NODESET) {
1980         xmlXPathObjectPtr tmp;
1981
1982         /*
1983          * First convert to a location set
1984          */
1985         tmp = xmlXPtrNewLocationSetNodeSet(set->nodesetval);
1986         xmlXPathFreeObject(set);
1987         set = tmp;
1988     }
1989     oldset = (xmlLocationSetPtr) set->user;
1990
1991     /*
1992      * The loop is to compute the covering range for each item and add it
1993      */
1994     newset = xmlXPtrLocationSetCreate(NULL);
1995     for (i = 0;i < oldset->locNr;i++) {
1996         xmlXPtrLocationSetAdd(newset,
1997                 xmlXPtrCoveringRange(ctxt, oldset->locTab[i]));
1998     }
1999
2000     /*
2001      * Save the new value and cleanup
2002      */
2003     valuePush(ctxt, xmlXPtrWrapLocationSet(newset));
2004     xmlXPathFreeObject(set);
2005 }
2006
2007 /**
2008  * xmlXPtrInsideRange:
2009  * @ctxt:  the XPointer Parser context
2010  * @loc:  the location for which the inside range must be computed
2011  *
2012  * A inside range is a range described in the range-inside() description
2013  *
2014  * Returns a new location or NULL in case of error
2015  */
2016 static xmlXPathObjectPtr
2017 xmlXPtrInsideRange(xmlXPathParserContextPtr ctxt, xmlXPathObjectPtr loc) {
2018     if (loc == NULL)
2019         return(NULL);
2020     if ((ctxt == NULL) || (ctxt->context == NULL) ||
2021         (ctxt->context->doc == NULL))
2022         return(NULL);
2023     switch (loc->type) {
2024         case XPATH_POINT: {
2025             xmlNodePtr node = (xmlNodePtr) loc->user;
2026             switch (node->type) {
2027                 case XML_PI_NODE:
2028                 case XML_COMMENT_NODE:
2029                 case XML_TEXT_NODE:
2030                 case XML_CDATA_SECTION_NODE: {
2031                     if (node->content == NULL) {
2032                         return(xmlXPtrNewRange(node, 0, node, 0));
2033                     } else {
2034                         return(xmlXPtrNewRange(node, 0, node,
2035                                                xmlStrlen(node->content)));
2036                     }
2037                 }
2038                 case XML_ATTRIBUTE_NODE:
2039                 case XML_ELEMENT_NODE:
2040                 case XML_ENTITY_REF_NODE:
2041                 case XML_DOCUMENT_NODE:
2042                 case XML_NOTATION_NODE:
2043                 case XML_HTML_DOCUMENT_NODE: {
2044                     return(xmlXPtrNewRange(node, 0, node,
2045                                            xmlXPtrGetArity(node)));
2046                 }
2047                 default:
2048                     break;
2049             }
2050             return(NULL);
2051         }
2052         case XPATH_RANGE: {
2053             xmlNodePtr node = (xmlNodePtr) loc->user;
2054             if (loc->user2 != NULL) {
2055                 return(xmlXPtrNewRange(node, loc->index,
2056                                        loc->user2, loc->index2));
2057             } else {
2058                 switch (node->type) {
2059                     case XML_PI_NODE:
2060                     case XML_COMMENT_NODE:
2061                     case XML_TEXT_NODE:
2062                     case XML_CDATA_SECTION_NODE: {
2063                         if (node->content == NULL) {
2064                             return(xmlXPtrNewRange(node, 0, node, 0));
2065                         } else {
2066                             return(xmlXPtrNewRange(node, 0, node,
2067                                                    xmlStrlen(node->content)));
2068                         }
2069                     }
2070                     case XML_ATTRIBUTE_NODE:
2071                     case XML_ELEMENT_NODE:
2072                     case XML_ENTITY_REF_NODE:
2073                     case XML_DOCUMENT_NODE:
2074                     case XML_NOTATION_NODE:
2075                     case XML_HTML_DOCUMENT_NODE: {
2076                         return(xmlXPtrNewRange(node, 0, node,
2077                                                xmlXPtrGetArity(node)));
2078                     }
2079                     default:
2080                         break;
2081                 }
2082                 return(NULL);
2083             }
2084         }
2085         default:
2086             TODO /* missed one case ??? */
2087     }
2088     return(NULL);
2089 }
2090
2091 /**
2092  * xmlXPtrRangeInsideFunction:
2093  * @ctxt:  the XPointer Parser context
2094  * @nargs:  the number of args
2095  *
2096  * Function implementing the range-inside() function 5.4.3
2097  *  location-set range-inside(location-set )
2098  *
2099  *  The range-inside function returns ranges covering the contents of
2100  *  the locations in the argument location-set. For each location x in
2101  *  the argument location-set, a range location is added to the result
2102  *  location-set. If x is a range location, then x is added to the
2103  *  result location-set. If x is not a range location, then x is used
2104  *  as the container location of the start and end points of the range
2105  *  location to be added; the index of the start point of the range is
2106  *  zero; if the end point is a character point then its index is the
2107  *  length of the string-value of x, and otherwise is the number of
2108  *  location children of x.
2109  *
2110  */
2111 void
2112 xmlXPtrRangeInsideFunction(xmlXPathParserContextPtr ctxt, int nargs) {
2113     int i;
2114     xmlXPathObjectPtr set;
2115     xmlLocationSetPtr oldset;
2116     xmlLocationSetPtr newset;
2117
2118     CHECK_ARITY(1);
2119     if ((ctxt->value == NULL) ||
2120         ((ctxt->value->type != XPATH_LOCATIONSET) &&
2121          (ctxt->value->type != XPATH_NODESET)))
2122         XP_ERROR(XPATH_INVALID_TYPE)
2123
2124     set = valuePop(ctxt);
2125     if (set->type == XPATH_NODESET) {
2126         xmlXPathObjectPtr tmp;
2127
2128         /*
2129          * First convert to a location set
2130          */
2131         tmp = xmlXPtrNewLocationSetNodeSet(set->nodesetval);
2132         xmlXPathFreeObject(set);
2133         set = tmp;
2134     }
2135     oldset = (xmlLocationSetPtr) set->user;
2136
2137     /*
2138      * The loop is to compute the covering range for each item and add it
2139      */
2140     newset = xmlXPtrLocationSetCreate(NULL);
2141     for (i = 0;i < oldset->locNr;i++) {
2142         xmlXPtrLocationSetAdd(newset,
2143                 xmlXPtrInsideRange(ctxt, oldset->locTab[i]));
2144     }
2145
2146     /*
2147      * Save the new value and cleanup
2148      */
2149     valuePush(ctxt, xmlXPtrWrapLocationSet(newset));
2150     xmlXPathFreeObject(set);
2151 }
2152
2153 /**
2154  * xmlXPtrRangeToFunction:
2155  * @ctxt:  the XPointer Parser context
2156  * @nargs:  the number of args
2157  *
2158  * Implement the range-to() XPointer function
2159  */
2160 void
2161 xmlXPtrRangeToFunction(xmlXPathParserContextPtr ctxt, int nargs) {
2162     xmlXPathObjectPtr range;
2163     const xmlChar *cur;
2164     xmlXPathObjectPtr res, obj;
2165     xmlXPathObjectPtr tmp;
2166     xmlLocationSetPtr newset = NULL;
2167     xmlNodeSetPtr oldset;
2168     int i;
2169
2170     CHECK_ARITY(1);
2171     /*
2172      * Save the expression pointer since we will have to evaluate
2173      * it multiple times. Initialize the new set.
2174      */
2175     CHECK_TYPE(XPATH_NODESET);
2176     obj = valuePop(ctxt);
2177     oldset = obj->nodesetval;
2178     ctxt->context->node = NULL;
2179
2180     cur = ctxt->cur;
2181     newset = xmlXPtrLocationSetCreate(NULL);
2182
2183     for (i = 0; i < oldset->nodeNr; i++) {
2184         ctxt->cur = cur;
2185
2186         /*
2187          * Run the evaluation with a node list made of a single item
2188          * in the nodeset.
2189          */
2190         ctxt->context->node = oldset->nodeTab[i];
2191         tmp = xmlXPathNewNodeSet(ctxt->context->node);
2192         valuePush(ctxt, tmp);
2193
2194         xmlXPathEvalExpr(ctxt);
2195         CHECK_ERROR;
2196
2197         /*
2198          * The result of the evaluation need to be tested to
2199          * decided whether the filter succeeded or not
2200          */
2201         res = valuePop(ctxt);
2202         range = xmlXPtrNewRangeNodeObject(oldset->nodeTab[i], res);
2203         if (range != NULL) {
2204             xmlXPtrLocationSetAdd(newset, range);
2205         }
2206
2207         /*
2208          * Cleanup
2209          */
2210         if (res != NULL)
2211             xmlXPathFreeObject(res);
2212         if (ctxt->value == tmp) {
2213             res = valuePop(ctxt);
2214             xmlXPathFreeObject(res);
2215         }
2216
2217         ctxt->context->node = NULL;
2218     }
2219
2220     /*
2221      * The result is used as the new evaluation set.
2222      */
2223     xmlXPathFreeObject(obj);
2224     ctxt->context->node = NULL;
2225     ctxt->context->contextSize = -1;
2226     ctxt->context->proximityPosition = -1;
2227     valuePush(ctxt, xmlXPtrWrapLocationSet(newset));
2228 }
2229
2230 /**
2231  * xmlXPtrAdvanceNode:
2232  * @cur:  the node
2233  *
2234  * Advance to the next element or text node in document order
2235  * TODO: add a stack for entering/exiting entities
2236  *
2237  * Returns -1 in case of failure, 0 otherwise
2238  */
2239 xmlNodePtr
2240 xmlXPtrAdvanceNode(xmlNodePtr cur) {
2241 next:
2242     if (cur == NULL)
2243         return(NULL);
2244     if (cur->children != NULL) {
2245         cur = cur->children ;
2246         goto found;
2247     }
2248     if (cur->next != NULL) {
2249         cur = cur->next;
2250         goto found;
2251     }
2252     do {
2253         cur = cur->parent;
2254         if (cur == NULL) return(NULL);
2255         if (cur->next != NULL) {
2256             cur = cur->next;
2257             goto found;
2258         }
2259     } while (cur != NULL);
2260
2261 found:
2262     if ((cur->type != XML_ELEMENT_NODE) &&
2263         (cur->type != XML_TEXT_NODE) &&
2264         (cur->type != XML_DOCUMENT_NODE) &&
2265         (cur->type != XML_HTML_DOCUMENT_NODE) &&
2266         (cur->type != XML_CDATA_SECTION_NODE))
2267         goto next;
2268     if (cur->type == XML_ENTITY_REF_NODE) {
2269         TODO
2270     }
2271     return(cur);
2272 }
2273
2274 /**
2275  * xmlXPtrAdvanceChar:
2276  * @node:  the node
2277  * @indx:  the indx
2278  * @bytes:  the number of bytes
2279  *
2280  * Advance a point of the associated number of bytes (not UTF8 chars)
2281  *
2282  * Returns -1 in case of failure, 0 otherwise
2283  */
2284 static int
2285 xmlXPtrAdvanceChar(xmlNodePtr *node, int *indx, int bytes) {
2286     xmlNodePtr cur;
2287     int pos;
2288     int len;
2289
2290     if ((node == NULL) || (indx == NULL))
2291         return(-1);
2292     cur = *node;
2293     if (cur == NULL)
2294         return(-1);
2295     pos = *indx;
2296
2297     while (bytes >= 0) {
2298         /*
2299          * First position to the beginning of the first text node
2300          * corresponding to this point
2301          */
2302         while ((cur != NULL) &&
2303                ((cur->type == XML_ELEMENT_NODE) ||
2304                 (cur->type == XML_DOCUMENT_NODE) ||
2305                 (cur->type == XML_HTML_DOCUMENT_NODE))) {
2306             if (pos > 0) {
2307                 cur = xmlXPtrGetNthChild(cur, pos);
2308                 pos = 0;
2309             } else {
2310                 cur = xmlXPtrAdvanceNode(cur);
2311                 pos = 0;
2312             }
2313         }
2314
2315         if (cur == NULL) {
2316             *node = NULL;
2317             *indx = 0;
2318             return(-1);
2319         }
2320
2321         /*
2322          * if there is no move needed return the current value.
2323          */
2324         if (pos == 0) pos = 1;
2325         if (bytes == 0) {
2326             *node = cur;
2327             *indx = pos;
2328             return(0);
2329         }
2330         /*
2331          * We should have a text (or cdata) node ...
2332          */
2333         len = 0;
2334         if ((cur->type != XML_ELEMENT_NODE) &&
2335             (cur->content != NULL)) {
2336             len = xmlStrlen(cur->content);
2337         }
2338         if (pos > len) {
2339             /* Strange, the indx in the text node is greater than it's len */
2340             STRANGE
2341             pos = len;
2342         }
2343         if (pos + bytes >= len) {
2344             bytes -= (len - pos);
2345             cur = xmlXPtrAdvanceNode(cur);
2346             cur = 0;
2347         } else if (pos + bytes < len) {
2348             pos += bytes;
2349             *node = cur;
2350             *indx = pos;
2351             return(0);
2352         }
2353     }
2354     return(-1);
2355 }
2356
2357 /**
2358  * xmlXPtrMatchString:
2359  * @string:  the string to search
2360  * @start:  the start textnode
2361  * @startindex:  the start index
2362  * @end:  the end textnode IN/OUT
2363  * @endindex:  the end index IN/OUT
2364  *
2365  * Check whether the document contains @string at the position
2366  * (@start, @startindex) and limited by the (@end, @endindex) point
2367  *
2368  * Returns -1 in case of failure, 0 if not found, 1 if found in which case
2369  *            (@start, @startindex) will indicate the position of the beginning
2370  *            of the range and (@end, @endindex) will indicate the end
2371  *            of the range
2372  */
2373 static int
2374 xmlXPtrMatchString(const xmlChar *string, xmlNodePtr start, int startindex,
2375                     xmlNodePtr *end, int *endindex) {
2376     xmlNodePtr cur;
2377     int pos; /* 0 based */
2378     int len; /* in bytes */
2379     int stringlen; /* in bytes */
2380     int match;
2381
2382     if (string == NULL)
2383         return(-1);
2384     if (start == NULL)
2385         return(-1);
2386     if ((end == NULL) || (endindex == NULL))
2387         return(-1);
2388     cur = start;
2389     if (cur == NULL)
2390         return(-1);
2391     pos = startindex - 1;
2392     stringlen = xmlStrlen(string);
2393
2394     while (stringlen > 0) {
2395         if ((cur == *end) && (pos + stringlen > *endindex))
2396             return(0);
2397
2398         if ((cur->type != XML_ELEMENT_NODE) && (cur->content != NULL)) {
2399             len = xmlStrlen(cur->content);
2400             if (len >= pos + stringlen) {
2401                 match = (!xmlStrncmp(&cur->content[pos], string, stringlen));
2402                 if (match) {
2403 #ifdef DEBUG_RANGES
2404                     xmlGenericError(xmlGenericErrorContext,
2405                             "found range %d bytes at index %d of ->",
2406                             stringlen, pos + 1);
2407                     xmlDebugDumpString(stdout, cur->content);
2408                     xmlGenericError(xmlGenericErrorContext, "\n");
2409 #endif
2410                     *end = cur;
2411                     *endindex = pos + stringlen;
2412                     return(1);
2413                 } else {
2414                     return(0);
2415                 }
2416             } else {
2417                 int sub = len - pos;
2418                 match = (!xmlStrncmp(&cur->content[pos], string, sub));
2419                 if (match) {
2420 #ifdef DEBUG_RANGES
2421                     xmlGenericError(xmlGenericErrorContext,
2422                             "found subrange %d bytes at index %d of ->",
2423                             sub, pos + 1);
2424                     xmlDebugDumpString(stdout, cur->content);
2425                     xmlGenericError(xmlGenericErrorContext, "\n");
2426 #endif
2427                     string = &string[sub];
2428                     stringlen -= sub;
2429                 } else {
2430                     return(0);
2431                 }
2432             }
2433         }
2434         cur = xmlXPtrAdvanceNode(cur);
2435         if (cur == NULL)
2436             return(0);
2437         pos = 0;
2438     }
2439     return(1);
2440 }
2441
2442 /**
2443  * xmlXPtrSearchString:
2444  * @string:  the string to search
2445  * @start:  the start textnode IN/OUT
2446  * @startindex:  the start index IN/OUT
2447  * @end:  the end textnode
2448  * @endindex:  the end index
2449  *
2450  * Search the next occurrence of @string within the document content
2451  * until the (@end, @endindex) point is reached
2452  *
2453  * Returns -1 in case of failure, 0 if not found, 1 if found in which case
2454  *            (@start, @startindex) will indicate the position of the beginning
2455  *            of the range and (@end, @endindex) will indicate the end
2456  *            of the range
2457  */
2458 static int
2459 xmlXPtrSearchString(const xmlChar *string, xmlNodePtr *start, int *startindex,
2460                     xmlNodePtr *end, int *endindex) {
2461     xmlNodePtr cur;
2462     const xmlChar *str;
2463     int pos; /* 0 based */
2464     int len; /* in bytes */
2465     xmlChar first;
2466
2467     if (string == NULL)
2468         return(-1);
2469     if ((start == NULL) || (startindex == NULL))
2470         return(-1);
2471     if ((end == NULL) || (endindex == NULL))
2472         return(-1);
2473     cur = *start;
2474     if (cur == NULL)
2475         return(-1);
2476     pos = *startindex - 1;
2477     first = string[0];
2478
2479     while (cur != NULL) {
2480         if ((cur->type != XML_ELEMENT_NODE) && (cur->content != NULL)) {
2481             len = xmlStrlen(cur->content);
2482             while (pos <= len) {
2483                 if (first != 0) {
2484                     str = xmlStrchr(&cur->content[pos], first);
2485                     if (str != NULL) {
2486                         pos = (str - (xmlChar *)(cur->content));
2487 #ifdef DEBUG_RANGES
2488                         xmlGenericError(xmlGenericErrorContext,
2489                                 "found '%c' at index %d of ->",
2490                                 first, pos + 1);
2491                         xmlDebugDumpString(stdout, cur->content);
2492                         xmlGenericError(xmlGenericErrorContext, "\n");
2493 #endif
2494                         if (xmlXPtrMatchString(string, cur, pos + 1,
2495                                                end, endindex)) {
2496                             *start = cur;
2497                             *startindex = pos + 1;
2498                             return(1);
2499                         }
2500                         pos++;
2501                     } else {
2502                         pos = len + 1;
2503                     }
2504                 } else {
2505                     /*
2506                      * An empty string is considered to match before each
2507                      * character of the string-value and after the final
2508                      * character.
2509                      */
2510 #ifdef DEBUG_RANGES
2511                     xmlGenericError(xmlGenericErrorContext,
2512                             "found '' at index %d of ->",
2513                             pos + 1);
2514                     xmlDebugDumpString(stdout, cur->content);
2515                     xmlGenericError(xmlGenericErrorContext, "\n");
2516 #endif
2517                     *start = cur;
2518                     *startindex = pos + 1;
2519                     *end = cur;
2520                     *endindex = pos + 1;
2521                     return(1);
2522                 }
2523             }
2524         }
2525         if ((cur == *end) && (pos >= *endindex))
2526             return(0);
2527         cur = xmlXPtrAdvanceNode(cur);
2528         if (cur == NULL)
2529             return(0);
2530         pos = 1;
2531     }
2532     return(0);
2533 }
2534
2535 /**
2536  * xmlXPtrGetLastChar:
2537  * @node:  the node
2538  * @index:  the index
2539  *
2540  * Computes the point coordinates of the last char of this point
2541  *
2542  * Returns -1 in case of failure, 0 otherwise
2543  */
2544 static int
2545 xmlXPtrGetLastChar(xmlNodePtr *node, int *indx) {
2546     xmlNodePtr cur;
2547     int pos, len = 0;
2548
2549     if ((node == NULL) || (indx == NULL))
2550         return(-1);
2551     cur = *node;
2552     pos = *indx;
2553
2554     if (cur == NULL)
2555         return(-1);
2556
2557     if ((cur->type == XML_ELEMENT_NODE) ||
2558         (cur->type == XML_DOCUMENT_NODE) ||
2559         (cur->type == XML_HTML_DOCUMENT_NODE)) {
2560         if (pos > 0) {
2561             cur = xmlXPtrGetNthChild(cur, pos);
2562             pos = 0;
2563         }
2564     }
2565     while (cur != NULL) {
2566         if (cur->last != NULL)
2567             cur = cur->last;
2568         else if ((cur->type != XML_ELEMENT_NODE) &&
2569                  (cur->content != NULL)) {
2570             len = xmlStrlen(cur->content);
2571             break;
2572         } else {
2573             return(-1);
2574         }
2575     }
2576     if (cur == NULL)
2577         return(-1);
2578     *node = cur;
2579     *indx = len;
2580     return(0);
2581 }
2582
2583 /**
2584  * xmlXPtrGetStartPoint:
2585  * @obj:  an range
2586  * @node:  the resulting node
2587  * @indx:  the resulting index
2588  *
2589  * read the object and return the start point coordinates.
2590  *
2591  * Returns -1 in case of failure, 0 otherwise
2592  */
2593 static int
2594 xmlXPtrGetStartPoint(xmlXPathObjectPtr obj, xmlNodePtr *node, int *indx) {
2595     if ((obj == NULL) || (node == NULL) || (indx == NULL))
2596         return(-1);
2597
2598     switch (obj->type) {
2599         case XPATH_POINT:
2600             *node = obj->user;
2601             if (obj->index <= 0)
2602                 *indx = 0;
2603             else
2604                 *indx = obj->index;
2605             return(0);
2606         case XPATH_RANGE:
2607             *node = obj->user;
2608             if (obj->index <= 0)
2609                 *indx = 0;
2610             else
2611                 *indx = obj->index;
2612             return(0);
2613         default:
2614             break;
2615     }
2616     return(-1);
2617 }
2618
2619 /**
2620  * xmlXPtrGetEndPoint:
2621  * @obj:  an range
2622  * @node:  the resulting node
2623  * @indx:  the resulting indx
2624  *
2625  * read the object and return the end point coordinates.
2626  *
2627  * Returns -1 in case of failure, 0 otherwise
2628  */
2629 static int
2630 xmlXPtrGetEndPoint(xmlXPathObjectPtr obj, xmlNodePtr *node, int *indx) {
2631     if ((obj == NULL) || (node == NULL) || (indx == NULL))
2632         return(-1);
2633
2634     switch (obj->type) {
2635         case XPATH_POINT:
2636             *node = obj->user;
2637             if (obj->index <= 0)
2638                 *indx = 0;
2639             else
2640                 *indx = obj->index;
2641             return(0);
2642         case XPATH_RANGE:
2643             *node = obj->user;
2644             if (obj->index <= 0)
2645                 *indx = 0;
2646             else
2647                 *indx = obj->index;
2648             return(0);
2649         default:
2650             break;
2651     }
2652     return(-1);
2653 }
2654
2655 /**
2656  * xmlXPtrStringRangeFunction:
2657  * @ctxt:  the XPointer Parser context
2658  * @nargs:  the number of args
2659  *
2660  * Function implementing the string-range() function
2661  * range as described in 5.4.2
2662  *
2663  * ------------------------------
2664  * [Definition: For each location in the location-set argument,
2665  * string-range returns a set of string ranges, a set of substrings in a
2666  * string. Specifically, the string-value of the location is searched for
2667  * substrings that match the string argument, and the resulting location-set
2668  * will contain a range location for each non-overlapping match.]
2669  * An empty string is considered to match before each character of the
2670  * string-value and after the final character. Whitespace in a string
2671  * is matched literally, with no normalization except that provided by
2672  * XML for line ends. The third argument gives the position of the first
2673  * character to be in the resulting range, relative to the start of the
2674  * match. The default value is 1, which makes the range start immediately
2675  * before the first character of the matched string. The fourth argument
2676  * gives the number of characters in the range; the default is that the
2677  * range extends to the end of the matched string.
2678  *
2679  * Element boundaries, as well as entire embedded nodes such as processing
2680  * instructions and comments, are ignored as defined in [XPath].
2681  *
2682  * If the string in the second argument is not found in the string-value
2683  * of the location, or if a value in the third or fourth argument indicates
2684  * a string that is beyond the beginning or end of the document, the
2685  * expression fails.
2686  *
2687  * The points of the range-locations in the returned location-set will
2688  * all be character points.
2689  * ------------------------------
2690  */
2691 void
2692 xmlXPtrStringRangeFunction(xmlXPathParserContextPtr ctxt, int nargs) {
2693     int i, startindex, endindex, fendindex;
2694     xmlNodePtr start, end, fend;
2695     xmlXPathObjectPtr set;
2696     xmlLocationSetPtr oldset;
2697     xmlLocationSetPtr newset;
2698     xmlXPathObjectPtr string;
2699     xmlXPathObjectPtr position = NULL;
2700     xmlXPathObjectPtr number = NULL;
2701     int found, pos = 0, num = 0;
2702
2703     /*
2704      * Grab the arguments
2705      */
2706     if ((nargs < 2) || (nargs > 4))
2707         XP_ERROR(XPATH_INVALID_ARITY);
2708
2709     if (nargs >= 4) {
2710         CHECK_TYPE(XPATH_NUMBER);
2711         number = valuePop(ctxt);
2712         if (number != NULL)
2713             num = (int) number->floatval;
2714     }
2715     if (nargs >= 3) {
2716         CHECK_TYPE(XPATH_NUMBER);
2717         position = valuePop(ctxt);
2718         if (position != NULL)
2719             pos = (int) position->floatval;
2720     }
2721     CHECK_TYPE(XPATH_STRING);
2722     string = valuePop(ctxt);
2723     if ((ctxt->value == NULL) ||
2724         ((ctxt->value->type != XPATH_LOCATIONSET) &&
2725          (ctxt->value->type != XPATH_NODESET)))
2726         XP_ERROR(XPATH_INVALID_TYPE)
2727
2728     set = valuePop(ctxt);
2729     if (set->type == XPATH_NODESET) {
2730         xmlXPathObjectPtr tmp;
2731
2732         /*
2733          * First convert to a location set
2734          */
2735         tmp = xmlXPtrNewLocationSetNodeSet(set->nodesetval);
2736         xmlXPathFreeObject(set);
2737         set = tmp;
2738     }
2739     oldset = (xmlLocationSetPtr) set->user;
2740
2741     /*
2742      * The loop is to search for each element in the location set
2743      * the list of location set corresponding to that search
2744      */
2745     newset = xmlXPtrLocationSetCreate(NULL);
2746     for (i = 0;i < oldset->locNr;i++) {
2747 #ifdef DEBUG_RANGES
2748         xmlXPathDebugDumpObject(stdout, oldset->locTab[i], 0);
2749 #endif
2750
2751         xmlXPtrGetStartPoint(oldset->locTab[i], &start, &startindex);
2752         xmlXPtrGetEndPoint(oldset->locTab[i], &end, &endindex);
2753         xmlXPtrAdvanceChar(&start, &startindex, 0);
2754         xmlXPtrGetLastChar(&end, &endindex);
2755
2756 #ifdef DEBUG_RANGES
2757         xmlGenericError(xmlGenericErrorContext,
2758                 "from index %d of ->", startindex);
2759         xmlDebugDumpString(stdout, start->content);
2760         xmlGenericError(xmlGenericErrorContext, "\n");
2761         xmlGenericError(xmlGenericErrorContext,
2762                 "to index %d of ->", endindex);
2763         xmlDebugDumpString(stdout, end->content);
2764         xmlGenericError(xmlGenericErrorContext, "\n");
2765 #endif
2766         do {
2767             fend = end;
2768             fendindex = endindex;
2769             found = xmlXPtrSearchString(string->stringval, &start, &startindex,
2770                                         &fend, &fendindex);
2771             if (found == 1) {
2772                 if (position == NULL) {
2773                     xmlXPtrLocationSetAdd(newset,
2774                          xmlXPtrNewRange(start, startindex, fend, fendindex));
2775                 } else if (xmlXPtrAdvanceChar(&start, &startindex,
2776                                               pos - 1) == 0) {
2777                     if ((number != NULL) && (num > 0)) {
2778                         int rindx;
2779                         xmlNodePtr rend;
2780                         rend = start;
2781                         rindx = startindex - 1;
2782                         if (xmlXPtrAdvanceChar(&rend, &rindx,
2783                                                num) == 0) {
2784                             xmlXPtrLocationSetAdd(newset,
2785                                         xmlXPtrNewRange(start, startindex,
2786                                                         rend, rindx));
2787                         }
2788                     } else if ((number != NULL) && (num <= 0)) {
2789                         xmlXPtrLocationSetAdd(newset,
2790                                     xmlXPtrNewRange(start, startindex,
2791                                                     start, startindex));
2792                     } else {
2793                         xmlXPtrLocationSetAdd(newset,
2794                                     xmlXPtrNewRange(start, startindex,
2795                                                     fend, fendindex));
2796                     }
2797                 }
2798                 start = fend;
2799                 startindex = fendindex;
2800                 if (string->stringval[0] == 0)
2801                     startindex++;
2802             }
2803         } while (found == 1);
2804     }
2805
2806     /*
2807      * Save the new value and cleanup
2808      */
2809     valuePush(ctxt, xmlXPtrWrapLocationSet(newset));
2810     xmlXPathFreeObject(set);
2811     xmlXPathFreeObject(string);
2812     if (position) xmlXPathFreeObject(position);
2813     if (number) xmlXPathFreeObject(number);
2814 }
2815
2816 /**
2817  * xmlXPtrEvalRangePredicate:
2818  * @ctxt:  the XPointer Parser context
2819  *
2820  *  [8]   Predicate ::=   '[' PredicateExpr ']'
2821  *  [9]   PredicateExpr ::=   Expr
2822  *
2823  * Evaluate a predicate as in xmlXPathEvalPredicate() but for
2824  * a Location Set instead of a node set
2825  */
2826 void
2827 xmlXPtrEvalRangePredicate(xmlXPathParserContextPtr ctxt) {
2828     const xmlChar *cur;
2829     xmlXPathObjectPtr res;
2830     xmlXPathObjectPtr obj, tmp;
2831     xmlLocationSetPtr newset = NULL;
2832     xmlLocationSetPtr oldset;
2833     int i;
2834
2835     SKIP_BLANKS;
2836     if (CUR != '[') {
2837         XP_ERROR(XPATH_INVALID_PREDICATE_ERROR);
2838     }
2839     NEXT;
2840     SKIP_BLANKS;
2841
2842     /*
2843      * Extract the old set, and then evaluate the result of the
2844      * expression for all the element in the set. use it to grow
2845      * up a new set.
2846      */
2847     CHECK_TYPE(XPATH_LOCATIONSET);
2848     obj = valuePop(ctxt);
2849     oldset = obj->user;
2850     ctxt->context->node = NULL;
2851
2852     if ((oldset == NULL) || (oldset->locNr == 0)) {
2853         ctxt->context->contextSize = 0;
2854         ctxt->context->proximityPosition = 0;
2855         xmlXPathEvalExpr(ctxt);
2856         res = valuePop(ctxt);
2857         if (res != NULL)
2858             xmlXPathFreeObject(res);
2859         valuePush(ctxt, obj);
2860         CHECK_ERROR;
2861     } else {
2862         /*
2863          * Save the expression pointer since we will have to evaluate
2864          * it multiple times. Initialize the new set.
2865          */
2866         cur = ctxt->cur;
2867         newset = xmlXPtrLocationSetCreate(NULL);
2868
2869         for (i = 0; i < oldset->locNr; i++) {
2870             ctxt->cur = cur;
2871
2872             /*
2873              * Run the evaluation with a node list made of a single item
2874              * in the nodeset.
2875              */
2876             ctxt->context->node = oldset->locTab[i]->user;
2877             tmp = xmlXPathNewNodeSet(ctxt->context->node);
2878             valuePush(ctxt, tmp);
2879             ctxt->context->contextSize = oldset->locNr;
2880             ctxt->context->proximityPosition = i + 1;
2881
2882             xmlXPathEvalExpr(ctxt);
2883             CHECK_ERROR;
2884
2885             /*
2886              * The result of the evaluation need to be tested to
2887              * decided whether the filter succeeded or not
2888              */
2889             res = valuePop(ctxt);
2890             if (xmlXPathEvaluatePredicateResult(ctxt, res)) {
2891                 xmlXPtrLocationSetAdd(newset,
2892                         xmlXPathObjectCopy(oldset->locTab[i]));
2893             }
2894
2895             /*
2896              * Cleanup
2897              */
2898             if (res != NULL)
2899                 xmlXPathFreeObject(res);
2900             if (ctxt->value == tmp) {
2901                 res = valuePop(ctxt);
2902                 xmlXPathFreeObject(res);
2903             }
2904
2905             ctxt->context->node = NULL;
2906         }
2907
2908         /*
2909          * The result is used as the new evaluation set.
2910          */
2911         xmlXPathFreeObject(obj);
2912         ctxt->context->node = NULL;
2913         ctxt->context->contextSize = -1;
2914         ctxt->context->proximityPosition = -1;
2915         valuePush(ctxt, xmlXPtrWrapLocationSet(newset));
2916     }
2917     if (CUR != ']') {
2918         XP_ERROR(XPATH_INVALID_PREDICATE_ERROR);
2919     }
2920
2921     NEXT;
2922     SKIP_BLANKS;
2923 }
2924
2925 #else
2926 #endif
2927