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