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             *cur++ = CUR;
1011         } else if (CUR == '(') {
1012             level++;
1013             *cur++ = CUR;
1014         } else if (CUR == '^') {
1015             NEXT;
1016             if ((CUR == ')') || (CUR == '(') || (CUR == '^')) {
1017                 *cur++ = CUR;
1018             } else {
1019                 *cur++ = '^';
1020                 *cur++ = CUR;
1021             }
1022         } else {
1023             *cur++ = CUR;
1024         }
1025         NEXT;
1026     }
1027     *cur = 0;
1028
1029     if ((level != 0) && (CUR == 0)) {
1030         xmlFree(buffer);
1031         XP_ERROR(XPTR_SYNTAX_ERROR);
1032     }
1033
1034     if (xmlStrEqual(name, (xmlChar *) "xpointer")) {
1035         const xmlChar *left = CUR_PTR;
1036
1037         CUR_PTR = buffer;
1038         /*
1039          * To evaluate an xpointer scheme element (4.3) we need:
1040          *   context initialized to the root
1041          *   context position initalized to 1
1042          *   context size initialized to 1
1043          */
1044         ctxt->context->node = (xmlNodePtr)ctxt->context->doc;
1045         ctxt->context->proximityPosition = 1;
1046         ctxt->context->contextSize = 1;
1047         xmlXPathEvalExpr(ctxt);
1048         CUR_PTR=left;
1049     } else if (xmlStrEqual(name, (xmlChar *) "element")) {
1050         const xmlChar *left = CUR_PTR;
1051         xmlChar *name2;
1052
1053         CUR_PTR = buffer;
1054         if (buffer[0] == '/') {
1055             xmlXPathRoot(ctxt);
1056             xmlXPtrEvalChildSeq(ctxt, NULL);
1057         } else {
1058             name2 = xmlXPathParseName(ctxt);
1059             if (name2 == NULL) {
1060                 CUR_PTR = left;
1061                 xmlFree(buffer);
1062                 XP_ERROR(XPATH_EXPR_ERROR);
1063             }
1064             xmlXPtrEvalChildSeq(ctxt, name2);
1065         }
1066         CUR_PTR = left;
1067 #ifdef XPTR_XMLNS_SCHEME
1068     } else if (xmlStrEqual(name, (xmlChar *) "xmlns")) {
1069         const xmlChar *left = CUR_PTR;
1070         xmlChar *prefix;
1071         xmlChar *URI;
1072         xmlURIPtr value;
1073
1074         CUR_PTR = buffer;
1075         prefix = xmlXPathParseNCName(ctxt);
1076         if (prefix == NULL) {
1077             xmlFree(buffer);
1078             xmlFree(name);
1079             XP_ERROR(XPTR_SYNTAX_ERROR);
1080         }
1081         SKIP_BLANKS;
1082         if (CUR != '=') {
1083             xmlFree(prefix);
1084             xmlFree(buffer);
1085             xmlFree(name);
1086             XP_ERROR(XPTR_SYNTAX_ERROR);
1087         }
1088         NEXT;
1089         SKIP_BLANKS;
1090         /* @@ check escaping in the XPointer WD */
1091
1092         value = xmlParseURI((const char *)ctxt->cur);
1093         if (value == NULL) {
1094             xmlFree(prefix);
1095             xmlFree(buffer);
1096             xmlFree(name);
1097             XP_ERROR(XPTR_SYNTAX_ERROR);
1098         }
1099         URI = xmlSaveUri(value);
1100         xmlFreeURI(value);
1101         if (URI == NULL) {
1102             xmlFree(prefix);
1103             xmlFree(buffer);
1104             xmlFree(name);
1105             XP_ERROR(XPATH_MEMORY_ERROR);
1106         }
1107
1108         xmlXPathRegisterNs(ctxt->context, prefix, URI);
1109         CUR_PTR = left;
1110         xmlFree(URI);
1111         xmlFree(prefix);
1112 #endif /* XPTR_XMLNS_SCHEME */
1113     } else {
1114         xmlXPtrErr(ctxt, XML_XPTR_UNKNOWN_SCHEME,
1115                    "unsupported scheme '%s'\n", name);
1116     }
1117     xmlFree(buffer);
1118     xmlFree(name);
1119 }
1120
1121 /**
1122  * xmlXPtrEvalFullXPtr:
1123  * @ctxt:  the XPointer Parser context
1124  * @name:  the preparsed Scheme for the first XPtrPart
1125  *
1126  * FullXPtr ::= XPtrPart (S? XPtrPart)*
1127  *
1128  * As the specs says:
1129  * -----------
1130  * When multiple XPtrParts are provided, they must be evaluated in
1131  * left-to-right order. If evaluation of one part fails, the nexti
1132  * is evaluated. The following conditions cause XPointer part failure:
1133  *
1134  * - An unknown scheme
1135  * - A scheme that does not locate any sub-resource present in the resource
1136  * - A scheme that is not applicable to the media type of the resource
1137  *
1138  * The XPointer application must consume a failed XPointer part and
1139  * attempt to evaluate the next one, if any. The result of the first
1140  * XPointer part whose evaluation succeeds is taken to be the fragment
1141  * located by the XPointer as a whole. If all the parts fail, the result
1142  * for the XPointer as a whole is a sub-resource error.
1143  * -----------
1144  *
1145  * Parse and evaluate a Full XPtr i.e. possibly a cascade of XPath based
1146  * expressions or other schemes.
1147  */
1148 static void
1149 xmlXPtrEvalFullXPtr(xmlXPathParserContextPtr ctxt, xmlChar *name) {
1150     if (name == NULL)
1151     name = xmlXPathParseName(ctxt);
1152     if (name == NULL)
1153         XP_ERROR(XPATH_EXPR_ERROR);
1154     while (name != NULL) {
1155         ctxt->error = XPATH_EXPRESSION_OK;
1156         xmlXPtrEvalXPtrPart(ctxt, name);
1157
1158         /* in case of syntax error, break here */
1159         if ((ctxt->error != XPATH_EXPRESSION_OK) &&
1160             (ctxt->error != XML_XPTR_UNKNOWN_SCHEME))
1161             return;
1162
1163         /*
1164          * If the returned value is a non-empty nodeset
1165          * or location set, return here.
1166          */
1167         if (ctxt->value != NULL) {
1168             xmlXPathObjectPtr obj = ctxt->value;
1169
1170             switch (obj->type) {
1171                 case XPATH_LOCATIONSET: {
1172                     xmlLocationSetPtr loc = ctxt->value->user;
1173                     if ((loc != NULL) && (loc->locNr > 0))
1174                         return;
1175                     break;
1176                 }
1177                 case XPATH_NODESET: {
1178                     xmlNodeSetPtr loc = ctxt->value->nodesetval;
1179                     if ((loc != NULL) && (loc->nodeNr > 0))
1180                         return;
1181                     break;
1182                 }
1183                 default:
1184                     break;
1185             }
1186
1187             /*
1188              * Evaluating to improper values is equivalent to
1189              * a sub-resource error, clean-up the stack
1190              */
1191             do {
1192                 obj = valuePop(ctxt);
1193                 if (obj != NULL) {
1194                     xmlXPathFreeObject(obj);
1195                 }
1196             } while (obj != NULL);
1197         }
1198
1199         /*
1200          * Is there another XPointer part.
1201          */
1202         SKIP_BLANKS;
1203         name = xmlXPathParseName(ctxt);
1204     }
1205 }
1206
1207 /**
1208  * xmlXPtrEvalChildSeq:
1209  * @ctxt:  the XPointer Parser context
1210  * @name:  a possible ID name of the child sequence
1211  *
1212  *  ChildSeq ::= '/1' ('/' [0-9]*)*
1213  *             | Name ('/' [0-9]*)+
1214  *
1215  * Parse and evaluate a Child Sequence. This routine also handle the
1216  * case of a Bare Name used to get a document ID.
1217  */
1218 static void
1219 xmlXPtrEvalChildSeq(xmlXPathParserContextPtr ctxt, xmlChar *name) {
1220     /*
1221      * XPointer don't allow by syntax to address in mutirooted trees
1222      * this might prove useful in some cases, warn about it.
1223      */
1224     if ((name == NULL) && (CUR == '/') && (NXT(1) != '1')) {
1225         xmlXPtrErr(ctxt, XML_XPTR_CHILDSEQ_START,
1226                    "warning: ChildSeq not starting by /1\n", NULL);
1227     }
1228
1229     if (name != NULL) {
1230         valuePush(ctxt, xmlXPathNewString(name));
1231         xmlFree(name);
1232         xmlXPathIdFunction(ctxt, 1);
1233         CHECK_ERROR;
1234     }
1235
1236     while (CUR == '/') {
1237         int child = 0;
1238         NEXT;
1239
1240         while ((CUR >= '0') && (CUR <= '9')) {
1241             child = child * 10 + (CUR - '0');
1242             NEXT;
1243         }
1244         xmlXPtrGetChildNo(ctxt, child);
1245     }
1246 }
1247
1248
1249 /**
1250  * xmlXPtrEvalXPointer:
1251  * @ctxt:  the XPointer Parser context
1252  *
1253  *  XPointer ::= Name
1254  *             | ChildSeq
1255  *             | FullXPtr
1256  *
1257  * Parse and evaluate an XPointer
1258  */
1259 static void
1260 xmlXPtrEvalXPointer(xmlXPathParserContextPtr ctxt) {
1261     if (ctxt->valueTab == NULL) {
1262         /* Allocate the value stack */
1263         ctxt->valueTab = (xmlXPathObjectPtr *)
1264                          xmlMalloc(10 * sizeof(xmlXPathObjectPtr));
1265         if (ctxt->valueTab == NULL) {
1266             xmlXPtrErrMemory("allocating evaluation context");
1267             return;
1268         }
1269         ctxt->valueNr = 0;
1270         ctxt->valueMax = 10;
1271         ctxt->value = NULL;
1272     }
1273     SKIP_BLANKS;
1274     if (CUR == '/') {
1275         xmlXPathRoot(ctxt);
1276         xmlXPtrEvalChildSeq(ctxt, NULL);
1277     } else {
1278         xmlChar *name;
1279
1280         name = xmlXPathParseName(ctxt);
1281         if (name == NULL)
1282             XP_ERROR(XPATH_EXPR_ERROR);
1283         if (CUR == '(') {
1284             xmlXPtrEvalFullXPtr(ctxt, name);
1285             /* Short evaluation */
1286             return;
1287         } else {
1288             /* this handle both Bare Names and Child Sequences */
1289             xmlXPtrEvalChildSeq(ctxt, name);
1290         }
1291     }
1292     SKIP_BLANKS;
1293     if (CUR != 0)
1294         XP_ERROR(XPATH_EXPR_ERROR);
1295 }
1296
1297
1298 /************************************************************************
1299  *                                                                      *
1300  *                      General routines                                *
1301  *                                                                      *
1302  ************************************************************************/
1303
1304 static
1305 void xmlXPtrStringRangeFunction(xmlXPathParserContextPtr ctxt, int nargs);
1306 static
1307 void xmlXPtrStartPointFunction(xmlXPathParserContextPtr ctxt, int nargs);
1308 static
1309 void xmlXPtrEndPointFunction(xmlXPathParserContextPtr ctxt, int nargs);
1310 static
1311 void xmlXPtrHereFunction(xmlXPathParserContextPtr ctxt, int nargs);
1312 static
1313 void xmlXPtrOriginFunction(xmlXPathParserContextPtr ctxt, int nargs);
1314 static
1315 void xmlXPtrRangeInsideFunction(xmlXPathParserContextPtr ctxt, int nargs);
1316 static
1317 void xmlXPtrRangeFunction(xmlXPathParserContextPtr ctxt, int nargs);
1318
1319 /**
1320  * xmlXPtrNewContext:
1321  * @doc:  the XML document
1322  * @here:  the node that directly contains the XPointer being evaluated or NULL
1323  * @origin:  the element from which a user or program initiated traversal of
1324  *           the link, or NULL.
1325  *
1326  * Create a new XPointer context
1327  *
1328  * Returns the xmlXPathContext just allocated.
1329  */
1330 xmlXPathContextPtr
1331 xmlXPtrNewContext(xmlDocPtr doc, xmlNodePtr here, xmlNodePtr origin) {
1332     xmlXPathContextPtr ret;
1333
1334     ret = xmlXPathNewContext(doc);
1335     if (ret == NULL)
1336         return(ret);
1337     ret->xptr = 1;
1338     ret->here = here;
1339     ret->origin = origin;
1340
1341     xmlXPathRegisterFunc(ret, (xmlChar *)"range-to",
1342                          xmlXPtrRangeToFunction);
1343     xmlXPathRegisterFunc(ret, (xmlChar *)"range",
1344                          xmlXPtrRangeFunction);
1345     xmlXPathRegisterFunc(ret, (xmlChar *)"range-inside",
1346                          xmlXPtrRangeInsideFunction);
1347     xmlXPathRegisterFunc(ret, (xmlChar *)"string-range",
1348                          xmlXPtrStringRangeFunction);
1349     xmlXPathRegisterFunc(ret, (xmlChar *)"start-point",
1350                          xmlXPtrStartPointFunction);
1351     xmlXPathRegisterFunc(ret, (xmlChar *)"end-point",
1352                          xmlXPtrEndPointFunction);
1353     xmlXPathRegisterFunc(ret, (xmlChar *)"here",
1354                          xmlXPtrHereFunction);
1355     xmlXPathRegisterFunc(ret, (xmlChar *)" origin",
1356                          xmlXPtrOriginFunction);
1357
1358     return(ret);
1359 }
1360
1361 /**
1362  * xmlXPtrEval:
1363  * @str:  the XPointer expression
1364  * @ctx:  the XPointer context
1365  *
1366  * Evaluate the XPath Location Path in the given context.
1367  *
1368  * Returns the xmlXPathObjectPtr resulting from the evaluation or NULL.
1369  *         the caller has to free the object.
1370  */
1371 xmlXPathObjectPtr
1372 xmlXPtrEval(const xmlChar *str, xmlXPathContextPtr ctx) {
1373     xmlXPathParserContextPtr ctxt;
1374     xmlXPathObjectPtr res = NULL, tmp;
1375     xmlXPathObjectPtr init = NULL;
1376     int stack = 0;
1377
1378     xmlXPathInit();
1379
1380     if ((ctx == NULL) || (str == NULL))
1381         return(NULL);
1382
1383     ctxt = xmlXPathNewParserContext(str, ctx);
1384     ctxt->xptr = 1;
1385     xmlXPtrEvalXPointer(ctxt);
1386
1387     if ((ctxt->value != NULL) &&
1388         (ctxt->value->type != XPATH_NODESET) &&
1389         (ctxt->value->type != XPATH_LOCATIONSET)) {
1390         xmlXPtrErr(ctxt, XML_XPTR_EVAL_FAILED,
1391                 "xmlXPtrEval: evaluation failed to return a node set\n",
1392                    NULL);
1393     } else {
1394         res = valuePop(ctxt);
1395     }
1396
1397     do {
1398         tmp = valuePop(ctxt);
1399         if (tmp != NULL) {
1400             if (tmp != init) {
1401                 if (tmp->type == XPATH_NODESET) {
1402                     /*
1403                      * Evaluation may push a root nodeset which is unused
1404                      */
1405                     xmlNodeSetPtr set;
1406                     set = tmp->nodesetval;
1407                     if ((set->nodeNr != 1) ||
1408                         (set->nodeTab[0] != (xmlNodePtr) ctx->doc))
1409                         stack++;
1410                 } else
1411                     stack++;
1412             }
1413             xmlXPathFreeObject(tmp);
1414         }
1415     } while (tmp != NULL);
1416     if (stack != 0) {
1417         xmlXPtrErr(ctxt, XML_XPTR_EXTRA_OBJECTS,
1418                    "xmlXPtrEval: object(s) left on the eval stack\n",
1419                    NULL);
1420     }
1421     if (ctxt->error != XPATH_EXPRESSION_OK) {
1422         xmlXPathFreeObject(res);
1423         res = NULL;
1424     }
1425
1426     xmlXPathFreeParserContext(ctxt);
1427     return(res);
1428 }
1429
1430 /**
1431  * xmlXPtrBuildRangeNodeList:
1432  * @range:  a range object
1433  *
1434  * Build a node list tree copy of the range
1435  *
1436  * Returns an xmlNodePtr list or NULL.
1437  *         the caller has to free the node tree.
1438  */
1439 static xmlNodePtr
1440 xmlXPtrBuildRangeNodeList(xmlXPathObjectPtr range) {
1441     /* pointers to generated nodes */
1442     xmlNodePtr list = NULL, last = NULL, parent = NULL, tmp;
1443     /* pointers to traversal nodes */
1444     xmlNodePtr start, cur, end;
1445     int index1, index2;
1446
1447     if (range == NULL)
1448         return(NULL);
1449     if (range->type != XPATH_RANGE)
1450         return(NULL);
1451     start = (xmlNodePtr) range->user;
1452
1453     if (start == NULL)
1454         return(NULL);
1455     end = range->user2;
1456     if (end == NULL)
1457         return(xmlCopyNode(start, 1));
1458
1459     cur = start;
1460     index1 = range->index;
1461     index2 = range->index2;
1462     while (cur != NULL) {
1463         if (cur == end) {
1464             if (cur->type == XML_TEXT_NODE) {
1465                 const xmlChar *content = cur->content;
1466                 int len;
1467
1468                 if (content == NULL) {
1469                     tmp = xmlNewTextLen(NULL, 0);
1470                 } else {
1471                     len = index2;
1472                     if ((cur == start) && (index1 > 1)) {
1473                         content += (index1 - 1);
1474                         len -= (index1 - 1);
1475                         index1 = 0;
1476                     } else {
1477                         len = index2;
1478                     }
1479                     tmp = xmlNewTextLen(content, len);
1480                 }
1481                 /* single sub text node selection */
1482                 if (list == NULL)
1483                     return(tmp);
1484                 /* prune and return full set */
1485                 if (last != NULL)
1486                     xmlAddNextSibling(last, tmp);
1487                 else
1488                     xmlAddChild(parent, tmp);
1489                 return(list);
1490             } else {
1491                 tmp = xmlCopyNode(cur, 0);
1492                 if (list == NULL)
1493                     list = tmp;
1494                 else {
1495                     if (last != NULL)
1496                         xmlAddNextSibling(last, tmp);
1497                     else
1498                         xmlAddChild(parent, tmp);
1499                 }
1500                 last = NULL;
1501                 parent = tmp;
1502
1503                 if (index2 > 1) {
1504                     end = xmlXPtrGetNthChild(cur, index2 - 1);
1505                     index2 = 0;
1506                 }
1507                 if ((cur == start) && (index1 > 1)) {
1508                     cur = xmlXPtrGetNthChild(cur, index1 - 1);
1509                     index1 = 0;
1510                 } else {
1511                     cur = cur->children;
1512                 }
1513                 /*
1514                  * Now gather the remaining nodes from cur to end
1515                  */
1516                 continue; /* while */
1517             }
1518         } else if ((cur == start) &&
1519                    (list == NULL) /* looks superfluous but ... */ ) {
1520             if ((cur->type == XML_TEXT_NODE) ||
1521                 (cur->type == XML_CDATA_SECTION_NODE)) {
1522                 const xmlChar *content = cur->content;
1523
1524                 if (content == NULL) {
1525                     tmp = xmlNewTextLen(NULL, 0);
1526                 } else {
1527                     if (index1 > 1) {
1528                         content += (index1 - 1);
1529                     }
1530                     tmp = xmlNewText(content);
1531                 }
1532                 last = list = tmp;
1533             } else {
1534                 if ((cur == start) && (index1 > 1)) {
1535                     tmp = xmlCopyNode(cur, 0);
1536                     list = tmp;
1537                     parent = tmp;
1538                     last = NULL;
1539                     cur = xmlXPtrGetNthChild(cur, index1 - 1);
1540                     index1 = 0;
1541                     /*
1542                      * Now gather the remaining nodes from cur to end
1543                      */
1544                     continue; /* while */
1545                 }
1546                 tmp = xmlCopyNode(cur, 1);
1547                 list = tmp;
1548                 parent = NULL;
1549                 last = tmp;
1550             }
1551         } else {
1552             tmp = NULL;
1553             switch (cur->type) {
1554                 case XML_DTD_NODE:
1555                 case XML_ELEMENT_DECL:
1556                 case XML_ATTRIBUTE_DECL:
1557                 case XML_ENTITY_NODE:
1558                     /* Do not copy DTD informations */
1559                     break;
1560                 case XML_ENTITY_DECL:
1561                     TODO /* handle crossing entities -> stack needed */
1562                     break;
1563                 case XML_XINCLUDE_START:
1564                 case XML_XINCLUDE_END:
1565                     /* don't consider it part of the tree content */
1566                     break;
1567                 case XML_ATTRIBUTE_NODE:
1568                     /* Humm, should not happen ! */
1569                     STRANGE
1570                     break;
1571                 default:
1572                     tmp = xmlCopyNode(cur, 1);
1573                     break;
1574             }
1575             if (tmp != NULL) {
1576                 if ((list == NULL) || ((last == NULL) && (parent == NULL)))  {
1577                     STRANGE
1578                     return(NULL);
1579                 }
1580                 if (last != NULL)
1581                     xmlAddNextSibling(last, tmp);
1582                 else {
1583                     xmlAddChild(parent, tmp);
1584                     last = tmp;
1585                 }
1586             }
1587         }
1588         /*
1589          * Skip to next node in document order
1590          */
1591         if ((list == NULL) || ((last == NULL) && (parent == NULL)))  {
1592             STRANGE
1593             return(NULL);
1594         }
1595         cur = xmlXPtrAdvanceNode(cur, NULL);
1596     }
1597     return(list);
1598 }
1599
1600 /**
1601  * xmlXPtrBuildNodeList:
1602  * @obj:  the XPointer result from the evaluation.
1603  *
1604  * Build a node list tree copy of the XPointer result.
1605  * This will drop Attributes and Namespace declarations.
1606  *
1607  * Returns an xmlNodePtr list or NULL.
1608  *         the caller has to free the node tree.
1609  */
1610 xmlNodePtr
1611 xmlXPtrBuildNodeList(xmlXPathObjectPtr obj) {
1612     xmlNodePtr list = NULL, last = NULL;
1613     int i;
1614
1615     if (obj == NULL)
1616         return(NULL);
1617     switch (obj->type) {
1618         case XPATH_NODESET: {
1619             xmlNodeSetPtr set = obj->nodesetval;
1620             if (set == NULL)
1621                 return(NULL);
1622             for (i = 0;i < set->nodeNr;i++) {
1623                 if (set->nodeTab[i] == NULL)
1624                     continue;
1625                 switch (set->nodeTab[i]->type) {
1626                     case XML_TEXT_NODE:
1627                     case XML_CDATA_SECTION_NODE:
1628                     case XML_ELEMENT_NODE:
1629                     case XML_ENTITY_REF_NODE:
1630                     case XML_ENTITY_NODE:
1631                     case XML_PI_NODE:
1632                     case XML_COMMENT_NODE:
1633                     case XML_DOCUMENT_NODE:
1634                     case XML_HTML_DOCUMENT_NODE:
1635 #ifdef LIBXML_DOCB_ENABLED
1636                     case XML_DOCB_DOCUMENT_NODE:
1637 #endif
1638                     case XML_XINCLUDE_START:
1639                     case XML_XINCLUDE_END:
1640                         break;
1641                     case XML_ATTRIBUTE_NODE:
1642                     case XML_NAMESPACE_DECL:
1643                     case XML_DOCUMENT_TYPE_NODE:
1644                     case XML_DOCUMENT_FRAG_NODE:
1645                     case XML_NOTATION_NODE:
1646                     case XML_DTD_NODE:
1647                     case XML_ELEMENT_DECL:
1648                     case XML_ATTRIBUTE_DECL:
1649                     case XML_ENTITY_DECL:
1650                         continue; /* for */
1651                 }
1652                 if (last == NULL)
1653                     list = last = xmlCopyNode(set->nodeTab[i], 1);
1654                 else {
1655                     xmlAddNextSibling(last, xmlCopyNode(set->nodeTab[i], 1));
1656                     if (last->next != NULL)
1657                         last = last->next;
1658                 }
1659             }
1660             break;
1661         }
1662         case XPATH_LOCATIONSET: {
1663             xmlLocationSetPtr set = (xmlLocationSetPtr) obj->user;
1664             if (set == NULL)
1665                 return(NULL);
1666             for (i = 0;i < set->locNr;i++) {
1667                 if (last == NULL)
1668                     list = last = xmlXPtrBuildNodeList(set->locTab[i]);
1669                 else
1670                     xmlAddNextSibling(last,
1671                             xmlXPtrBuildNodeList(set->locTab[i]));
1672                 if (last != NULL) {
1673                     while (last->next != NULL)
1674                         last = last->next;
1675                 }
1676             }
1677             break;
1678         }
1679         case XPATH_RANGE:
1680             return(xmlXPtrBuildRangeNodeList(obj));
1681         case XPATH_POINT:
1682             return(xmlCopyNode(obj->user, 0));
1683         default:
1684             break;
1685     }
1686     return(list);
1687 }
1688
1689 /************************************************************************
1690  *                                                                      *
1691  *                      XPointer functions                              *
1692  *                                                                      *
1693  ************************************************************************/
1694
1695 /**
1696  * xmlXPtrNbLocChildren:
1697  * @node:  an xmlNodePtr
1698  *
1699  * Count the number of location children of @node or the length of the
1700  * string value in case of text/PI/Comments nodes
1701  *
1702  * Returns the number of location children
1703  */
1704 static int
1705 xmlXPtrNbLocChildren(xmlNodePtr node) {
1706     int ret = 0;
1707     if (node == NULL)
1708         return(-1);
1709     switch (node->type) {
1710         case XML_HTML_DOCUMENT_NODE:
1711         case XML_DOCUMENT_NODE:
1712         case XML_ELEMENT_NODE:
1713             node = node->children;
1714             while (node != NULL) {
1715                 if (node->type == XML_ELEMENT_NODE)
1716                     ret++;
1717                 node = node->next;
1718             }
1719             break;
1720         case XML_ATTRIBUTE_NODE:
1721             return(-1);
1722
1723         case XML_PI_NODE:
1724         case XML_COMMENT_NODE:
1725         case XML_TEXT_NODE:
1726         case XML_CDATA_SECTION_NODE:
1727         case XML_ENTITY_REF_NODE:
1728             ret = xmlStrlen(node->content);
1729             break;
1730         default:
1731             return(-1);
1732     }
1733     return(ret);
1734 }
1735
1736 /**
1737  * xmlXPtrHereFunction:
1738  * @ctxt:  the XPointer Parser context
1739  * @nargs:  the number of args
1740  *
1741  * Function implementing here() operation
1742  * as described in 5.4.3
1743  */
1744 static void
1745 xmlXPtrHereFunction(xmlXPathParserContextPtr ctxt, int nargs) {
1746     CHECK_ARITY(0);
1747
1748     if (ctxt->context->here == NULL)
1749         XP_ERROR(XPTR_SYNTAX_ERROR);
1750
1751     valuePush(ctxt, xmlXPtrNewLocationSetNodes(ctxt->context->here, NULL));
1752 }
1753
1754 /**
1755  * xmlXPtrOriginFunction:
1756  * @ctxt:  the XPointer Parser context
1757  * @nargs:  the number of args
1758  *
1759  * Function implementing origin() operation
1760  * as described in 5.4.3
1761  */
1762 static void
1763 xmlXPtrOriginFunction(xmlXPathParserContextPtr ctxt, int nargs) {
1764     CHECK_ARITY(0);
1765
1766     if (ctxt->context->origin == NULL)
1767         XP_ERROR(XPTR_SYNTAX_ERROR);
1768
1769     valuePush(ctxt, xmlXPtrNewLocationSetNodes(ctxt->context->origin, NULL));
1770 }
1771
1772 /**
1773  * xmlXPtrStartPointFunction:
1774  * @ctxt:  the XPointer Parser context
1775  * @nargs:  the number of args
1776  *
1777  * Function implementing start-point() operation
1778  * as described in 5.4.3
1779  * ----------------
1780  * location-set start-point(location-set)
1781  *
1782  * For each location x in the argument location-set, start-point adds a
1783  * location of type point to the result location-set. That point represents
1784  * the start point of location x and is determined by the following rules:
1785  *
1786  * - If x is of type point, the start point is x.
1787  * - If x is of type range, the start point is the start point of x.
1788  * - If x is of type root, element, text, comment, or processing instruction,
1789  * - the container node of the start point is x and the index is 0.
1790  * - If x is of type attribute or namespace, the function must signal a
1791  *   syntax error.
1792  * ----------------
1793  *
1794  */
1795 static void
1796 xmlXPtrStartPointFunction(xmlXPathParserContextPtr ctxt, int nargs) {
1797     xmlXPathObjectPtr tmp, obj, point;
1798     xmlLocationSetPtr newset = NULL;
1799     xmlLocationSetPtr oldset = NULL;
1800
1801     CHECK_ARITY(1);
1802     if ((ctxt->value == NULL) ||
1803         ((ctxt->value->type != XPATH_LOCATIONSET) &&
1804          (ctxt->value->type != XPATH_NODESET)))
1805         XP_ERROR(XPATH_INVALID_TYPE)
1806
1807     obj = valuePop(ctxt);
1808     if (obj->type == XPATH_NODESET) {
1809         /*
1810          * First convert to a location set
1811          */
1812         tmp = xmlXPtrNewLocationSetNodeSet(obj->nodesetval);
1813         xmlXPathFreeObject(obj);
1814         obj = tmp;
1815     }
1816
1817     newset = xmlXPtrLocationSetCreate(NULL);
1818     if (newset == NULL) {
1819         xmlXPathFreeObject(obj);
1820         XP_ERROR(XPATH_MEMORY_ERROR);
1821     }
1822     oldset = (xmlLocationSetPtr) obj->user;
1823     if (oldset != NULL) {
1824         int i;
1825
1826         for (i = 0; i < oldset->locNr; i++) {
1827             tmp = oldset->locTab[i];
1828             if (tmp == NULL)
1829                 continue;
1830             point = NULL;
1831             switch (tmp->type) {
1832                 case XPATH_POINT:
1833                     point = xmlXPtrNewPoint(tmp->user, tmp->index);
1834                     break;
1835                 case XPATH_RANGE: {
1836                     xmlNodePtr node = tmp->user;
1837                     if (node != NULL) {
1838                         if (node->type == XML_ATTRIBUTE_NODE) {
1839                             /* TODO: Namespace Nodes ??? */
1840                             xmlXPathFreeObject(obj);
1841                             xmlXPtrFreeLocationSet(newset);
1842                             XP_ERROR(XPTR_SYNTAX_ERROR);
1843                         }
1844                         point = xmlXPtrNewPoint(node, tmp->index);
1845                     }
1846                     break;
1847                 }
1848                 default:
1849                     /*** Should we raise an error ?
1850                     xmlXPathFreeObject(obj);
1851                     xmlXPathFreeObject(newset);
1852                     XP_ERROR(XPATH_INVALID_TYPE)
1853                     ***/
1854                     break;
1855             }
1856             if (point != NULL)
1857                 xmlXPtrLocationSetAdd(newset, point);
1858         }
1859     }
1860     xmlXPathFreeObject(obj);
1861     valuePush(ctxt, xmlXPtrWrapLocationSet(newset));
1862 }
1863
1864 /**
1865  * xmlXPtrEndPointFunction:
1866  * @ctxt:  the XPointer Parser context
1867  * @nargs:  the number of args
1868  *
1869  * Function implementing end-point() operation
1870  * as described in 5.4.3
1871  * ----------------------------
1872  * location-set end-point(location-set)
1873  *
1874  * For each location x in the argument location-set, end-point adds a
1875  * location of type point to the result location-set. That point represents
1876  * the end point of location x and is determined by the following rules:
1877  *
1878  * - If x is of type point, the resulting point is x.
1879  * - If x is of type range, the resulting point is the end point of x.
1880  * - If x is of type root or element, the container node of the resulting
1881  *   point is x and the index is the number of location children of x.
1882  * - If x is of type text, comment, or processing instruction, the container
1883  *   node of the resulting point is x and the index is the length of the
1884  *   string-value of x.
1885  * - If x is of type attribute or namespace, the function must signal a
1886  *   syntax error.
1887  * ----------------------------
1888  */
1889 static void
1890 xmlXPtrEndPointFunction(xmlXPathParserContextPtr ctxt, int nargs) {
1891     xmlXPathObjectPtr tmp, obj, point;
1892     xmlLocationSetPtr newset = NULL;
1893     xmlLocationSetPtr oldset = NULL;
1894
1895     CHECK_ARITY(1);
1896     if ((ctxt->value == NULL) ||
1897         ((ctxt->value->type != XPATH_LOCATIONSET) &&
1898          (ctxt->value->type != XPATH_NODESET)))
1899         XP_ERROR(XPATH_INVALID_TYPE)
1900
1901     obj = valuePop(ctxt);
1902     if (obj->type == XPATH_NODESET) {
1903         /*
1904          * First convert to a location set
1905          */
1906         tmp = xmlXPtrNewLocationSetNodeSet(obj->nodesetval);
1907         xmlXPathFreeObject(obj);
1908         obj = tmp;
1909     }
1910
1911     newset = xmlXPtrLocationSetCreate(NULL);
1912     oldset = (xmlLocationSetPtr) obj->user;
1913     if (oldset != NULL) {
1914         int i;
1915
1916         for (i = 0; i < oldset->locNr; i++) {
1917             tmp = oldset->locTab[i];
1918             if (tmp == NULL)
1919                 continue;
1920             point = NULL;
1921             switch (tmp->type) {
1922                 case XPATH_POINT:
1923                     point = xmlXPtrNewPoint(tmp->user, tmp->index);
1924                     break;
1925                 case XPATH_RANGE: {
1926                     xmlNodePtr node = tmp->user2;
1927                     if (node != NULL) {
1928                         if (node->type == XML_ATTRIBUTE_NODE) {
1929                             /* TODO: Namespace Nodes ??? */
1930                             xmlXPathFreeObject(obj);
1931                             xmlXPtrFreeLocationSet(newset);
1932                             XP_ERROR(XPTR_SYNTAX_ERROR);
1933                         }
1934                         point = xmlXPtrNewPoint(node, tmp->index2);
1935                     } else if (tmp->user == NULL) {
1936                         point = xmlXPtrNewPoint(node,
1937                                        xmlXPtrNbLocChildren(node));
1938                     }
1939                     break;
1940                 }
1941                 default:
1942                     /*** Should we raise an error ?
1943                     xmlXPathFreeObject(obj);
1944                     xmlXPathFreeObject(newset);
1945                     XP_ERROR(XPATH_INVALID_TYPE)
1946                     ***/
1947                     break;
1948             }
1949             if (point != NULL)
1950                 xmlXPtrLocationSetAdd(newset, point);
1951         }
1952     }
1953     xmlXPathFreeObject(obj);
1954     valuePush(ctxt, xmlXPtrWrapLocationSet(newset));
1955 }
1956
1957
1958 /**
1959  * xmlXPtrCoveringRange:
1960  * @ctxt:  the XPointer Parser context
1961  * @loc:  the location for which the covering range must be computed
1962  *
1963  * A covering range is a range that wholly encompasses a location
1964  * Section 5.3.3. Covering Ranges for All Location Types
1965  *        http://www.w3.org/TR/xptr#N2267
1966  *
1967  * Returns a new location or NULL in case of error
1968  */
1969 static xmlXPathObjectPtr
1970 xmlXPtrCoveringRange(xmlXPathParserContextPtr ctxt, xmlXPathObjectPtr loc) {
1971     if (loc == NULL)
1972         return(NULL);
1973     if ((ctxt == NULL) || (ctxt->context == NULL) ||
1974         (ctxt->context->doc == NULL))
1975         return(NULL);
1976     switch (loc->type) {
1977         case XPATH_POINT:
1978             return(xmlXPtrNewRange(loc->user, loc->index,
1979                                    loc->user, loc->index));
1980         case XPATH_RANGE:
1981             if (loc->user2 != NULL) {
1982                 return(xmlXPtrNewRange(loc->user, loc->index,
1983                                       loc->user2, loc->index2));
1984             } else {
1985                 xmlNodePtr node = (xmlNodePtr) loc->user;
1986                 if (node == (xmlNodePtr) ctxt->context->doc) {
1987                     return(xmlXPtrNewRange(node, 0, node,
1988                                            xmlXPtrGetArity(node)));
1989                 } else {
1990                     switch (node->type) {
1991                         case XML_ATTRIBUTE_NODE:
1992                         /* !!! our model is slightly different than XPath */
1993                             return(xmlXPtrNewRange(node, 0, node,
1994                                                    xmlXPtrGetArity(node)));
1995                         case XML_ELEMENT_NODE:
1996                         case XML_TEXT_NODE:
1997                         case XML_CDATA_SECTION_NODE:
1998                         case XML_ENTITY_REF_NODE:
1999                         case XML_PI_NODE:
2000                         case XML_COMMENT_NODE:
2001                         case XML_DOCUMENT_NODE:
2002                         case XML_NOTATION_NODE:
2003                         case XML_HTML_DOCUMENT_NODE: {
2004                             int indx = xmlXPtrGetIndex(node);
2005
2006                             node = node->parent;
2007                             return(xmlXPtrNewRange(node, indx - 1,
2008                                                    node, indx + 1));
2009                         }
2010                         default:
2011                             return(NULL);
2012                     }
2013                 }
2014             }
2015         default:
2016             TODO /* missed one case ??? */
2017     }
2018     return(NULL);
2019 }
2020
2021 /**
2022  * xmlXPtrRangeFunction:
2023  * @ctxt:  the XPointer Parser context
2024  * @nargs:  the number of args
2025  *
2026  * Function implementing the range() function 5.4.3
2027  *  location-set range(location-set )
2028  *
2029  *  The range function returns ranges covering the locations in
2030  *  the argument location-set. For each location x in the argument
2031  *  location-set, a range location representing the covering range of
2032  *  x is added to the result location-set.
2033  */
2034 static void
2035 xmlXPtrRangeFunction(xmlXPathParserContextPtr ctxt, int nargs) {
2036     int i;
2037     xmlXPathObjectPtr set;
2038     xmlLocationSetPtr oldset;
2039     xmlLocationSetPtr newset;
2040
2041     CHECK_ARITY(1);
2042     if ((ctxt->value == NULL) ||
2043         ((ctxt->value->type != XPATH_LOCATIONSET) &&
2044          (ctxt->value->type != XPATH_NODESET)))
2045         XP_ERROR(XPATH_INVALID_TYPE)
2046
2047     set = valuePop(ctxt);
2048     if (set->type == XPATH_NODESET) {
2049         xmlXPathObjectPtr tmp;
2050
2051         /*
2052          * First convert to a location set
2053          */
2054         tmp = xmlXPtrNewLocationSetNodeSet(set->nodesetval);
2055         xmlXPathFreeObject(set);
2056         set = tmp;
2057     }
2058     oldset = (xmlLocationSetPtr) set->user;
2059
2060     /*
2061      * The loop is to compute the covering range for each item and add it
2062      */
2063     newset = xmlXPtrLocationSetCreate(NULL);
2064     for (i = 0;i < oldset->locNr;i++) {
2065         xmlXPtrLocationSetAdd(newset,
2066                 xmlXPtrCoveringRange(ctxt, oldset->locTab[i]));
2067     }
2068
2069     /*
2070      * Save the new value and cleanup
2071      */
2072     valuePush(ctxt, xmlXPtrWrapLocationSet(newset));
2073     xmlXPathFreeObject(set);
2074 }
2075
2076 /**
2077  * xmlXPtrInsideRange:
2078  * @ctxt:  the XPointer Parser context
2079  * @loc:  the location for which the inside range must be computed
2080  *
2081  * A inside range is a range described in the range-inside() description
2082  *
2083  * Returns a new location or NULL in case of error
2084  */
2085 static xmlXPathObjectPtr
2086 xmlXPtrInsideRange(xmlXPathParserContextPtr ctxt, xmlXPathObjectPtr loc) {
2087     if (loc == NULL)
2088         return(NULL);
2089     if ((ctxt == NULL) || (ctxt->context == NULL) ||
2090         (ctxt->context->doc == NULL))
2091         return(NULL);
2092     switch (loc->type) {
2093         case XPATH_POINT: {
2094             xmlNodePtr node = (xmlNodePtr) loc->user;
2095             switch (node->type) {
2096                 case XML_PI_NODE:
2097                 case XML_COMMENT_NODE:
2098                 case XML_TEXT_NODE:
2099                 case XML_CDATA_SECTION_NODE: {
2100                     if (node->content == NULL) {
2101                         return(xmlXPtrNewRange(node, 0, node, 0));
2102                     } else {
2103                         return(xmlXPtrNewRange(node, 0, node,
2104                                                xmlStrlen(node->content)));
2105                     }
2106                 }
2107                 case XML_ATTRIBUTE_NODE:
2108                 case XML_ELEMENT_NODE:
2109                 case XML_ENTITY_REF_NODE:
2110                 case XML_DOCUMENT_NODE:
2111                 case XML_NOTATION_NODE:
2112                 case XML_HTML_DOCUMENT_NODE: {
2113                     return(xmlXPtrNewRange(node, 0, node,
2114                                            xmlXPtrGetArity(node)));
2115                 }
2116                 default:
2117                     break;
2118             }
2119             return(NULL);
2120         }
2121         case XPATH_RANGE: {
2122             xmlNodePtr node = (xmlNodePtr) loc->user;
2123             if (loc->user2 != NULL) {
2124                 return(xmlXPtrNewRange(node, loc->index,
2125                                        loc->user2, loc->index2));
2126             } else {
2127                 switch (node->type) {
2128                     case XML_PI_NODE:
2129                     case XML_COMMENT_NODE:
2130                     case XML_TEXT_NODE:
2131                     case XML_CDATA_SECTION_NODE: {
2132                         if (node->content == NULL) {
2133                             return(xmlXPtrNewRange(node, 0, node, 0));
2134                         } else {
2135                             return(xmlXPtrNewRange(node, 0, node,
2136                                                    xmlStrlen(node->content)));
2137                         }
2138                     }
2139                     case XML_ATTRIBUTE_NODE:
2140                     case XML_ELEMENT_NODE:
2141                     case XML_ENTITY_REF_NODE:
2142                     case XML_DOCUMENT_NODE:
2143                     case XML_NOTATION_NODE:
2144                     case XML_HTML_DOCUMENT_NODE: {
2145                         return(xmlXPtrNewRange(node, 0, node,
2146                                                xmlXPtrGetArity(node)));
2147                     }
2148                     default:
2149                         break;
2150                 }
2151                 return(NULL);
2152             }
2153         }
2154         default:
2155             TODO /* missed one case ??? */
2156     }
2157     return(NULL);
2158 }
2159
2160 /**
2161  * xmlXPtrRangeInsideFunction:
2162  * @ctxt:  the XPointer Parser context
2163  * @nargs:  the number of args
2164  *
2165  * Function implementing the range-inside() function 5.4.3
2166  *  location-set range-inside(location-set )
2167  *
2168  *  The range-inside function returns ranges covering the contents of
2169  *  the locations in the argument location-set. For each location x in
2170  *  the argument location-set, a range location is added to the result
2171  *  location-set. If x is a range location, then x is added to the
2172  *  result location-set. If x is not a range location, then x is used
2173  *  as the container location of the start and end points of the range
2174  *  location to be added; the index of the start point of the range is
2175  *  zero; if the end point is a character point then its index is the
2176  *  length of the string-value of x, and otherwise is the number of
2177  *  location children of x.
2178  *
2179  */
2180 static void
2181 xmlXPtrRangeInsideFunction(xmlXPathParserContextPtr ctxt, int nargs) {
2182     int i;
2183     xmlXPathObjectPtr set;
2184     xmlLocationSetPtr oldset;
2185     xmlLocationSetPtr newset;
2186
2187     CHECK_ARITY(1);
2188     if ((ctxt->value == NULL) ||
2189         ((ctxt->value->type != XPATH_LOCATIONSET) &&
2190          (ctxt->value->type != XPATH_NODESET)))
2191         XP_ERROR(XPATH_INVALID_TYPE)
2192
2193     set = valuePop(ctxt);
2194     if (set->type == XPATH_NODESET) {
2195         xmlXPathObjectPtr tmp;
2196
2197         /*
2198          * First convert to a location set
2199          */
2200         tmp = xmlXPtrNewLocationSetNodeSet(set->nodesetval);
2201         xmlXPathFreeObject(set);
2202         set = tmp;
2203     }
2204     oldset = (xmlLocationSetPtr) set->user;
2205
2206     /*
2207      * The loop is to compute the covering range for each item and add it
2208      */
2209     newset = xmlXPtrLocationSetCreate(NULL);
2210     for (i = 0;i < oldset->locNr;i++) {
2211         xmlXPtrLocationSetAdd(newset,
2212                 xmlXPtrInsideRange(ctxt, oldset->locTab[i]));
2213     }
2214
2215     /*
2216      * Save the new value and cleanup
2217      */
2218     valuePush(ctxt, xmlXPtrWrapLocationSet(newset));
2219     xmlXPathFreeObject(set);
2220 }
2221
2222 /**
2223  * xmlXPtrRangeToFunction:
2224  * @ctxt:  the XPointer Parser context
2225  * @nargs:  the number of args
2226  *
2227  * Implement the range-to() XPointer function
2228  */
2229 void
2230 xmlXPtrRangeToFunction(xmlXPathParserContextPtr ctxt, int nargs) {
2231     xmlXPathObjectPtr range;
2232     const xmlChar *cur;
2233     xmlXPathObjectPtr res, obj;
2234     xmlXPathObjectPtr tmp;
2235     xmlLocationSetPtr newset = NULL;
2236     xmlNodeSetPtr oldset;
2237     int i;
2238
2239     if (ctxt == NULL) return;
2240     CHECK_ARITY(1);
2241     /*
2242      * Save the expression pointer since we will have to evaluate
2243      * it multiple times. Initialize the new set.
2244      */
2245     CHECK_TYPE(XPATH_NODESET);
2246     obj = valuePop(ctxt);
2247     oldset = obj->nodesetval;
2248     ctxt->context->node = NULL;
2249
2250     cur = ctxt->cur;
2251     newset = xmlXPtrLocationSetCreate(NULL);
2252
2253     for (i = 0; i < oldset->nodeNr; i++) {
2254         ctxt->cur = cur;
2255
2256         /*
2257          * Run the evaluation with a node list made of a single item
2258          * in the nodeset.
2259          */
2260         ctxt->context->node = oldset->nodeTab[i];
2261         tmp = xmlXPathNewNodeSet(ctxt->context->node);
2262         valuePush(ctxt, tmp);
2263
2264         xmlXPathEvalExpr(ctxt);
2265         CHECK_ERROR;
2266
2267         /*
2268          * The result of the evaluation need to be tested to
2269          * decided whether the filter succeeded or not
2270          */
2271         res = valuePop(ctxt);
2272         range = xmlXPtrNewRangeNodeObject(oldset->nodeTab[i], res);
2273         if (range != NULL) {
2274             xmlXPtrLocationSetAdd(newset, range);
2275         }
2276
2277         /*
2278          * Cleanup
2279          */
2280         if (res != NULL)
2281             xmlXPathFreeObject(res);
2282         if (ctxt->value == tmp) {
2283             res = valuePop(ctxt);
2284             xmlXPathFreeObject(res);
2285         }
2286
2287         ctxt->context->node = NULL;
2288     }
2289
2290     /*
2291      * The result is used as the new evaluation set.
2292      */
2293     xmlXPathFreeObject(obj);
2294     ctxt->context->node = NULL;
2295     ctxt->context->contextSize = -1;
2296     ctxt->context->proximityPosition = -1;
2297     valuePush(ctxt, xmlXPtrWrapLocationSet(newset));
2298 }
2299
2300 /**
2301  * xmlXPtrAdvanceNode:
2302  * @cur:  the node
2303  * @level: incremented/decremented to show level in tree
2304  *
2305  * Advance to the next element or text node in document order
2306  * TODO: add a stack for entering/exiting entities
2307  *
2308  * Returns -1 in case of failure, 0 otherwise
2309  */
2310 xmlNodePtr
2311 xmlXPtrAdvanceNode(xmlNodePtr cur, int *level) {
2312 next:
2313     if (cur == NULL)
2314         return(NULL);
2315     if (cur->children != NULL) {
2316         cur = cur->children ;
2317         if (level != NULL)
2318             (*level)++;
2319         goto found;
2320     }
2321 skip:           /* This label should only be needed if something is wrong! */
2322     if (cur->next != NULL) {
2323         cur = cur->next;
2324         goto found;
2325     }
2326     do {
2327         cur = cur->parent;
2328         if (level != NULL)
2329             (*level)--;
2330         if (cur == NULL) return(NULL);
2331         if (cur->next != NULL) {
2332             cur = cur->next;
2333             goto found;
2334         }
2335     } while (cur != NULL);
2336
2337 found:
2338     if ((cur->type != XML_ELEMENT_NODE) &&
2339         (cur->type != XML_TEXT_NODE) &&
2340         (cur->type != XML_DOCUMENT_NODE) &&
2341         (cur->type != XML_HTML_DOCUMENT_NODE) &&
2342         (cur->type != XML_CDATA_SECTION_NODE)) {
2343             if (cur->type == XML_ENTITY_REF_NODE) {     /* Shouldn't happen */
2344                 TODO
2345                 goto skip;
2346             }
2347             goto next;
2348         }
2349     return(cur);
2350 }
2351
2352 /**
2353  * xmlXPtrAdvanceChar:
2354  * @node:  the node
2355  * @indx:  the indx
2356  * @bytes:  the number of bytes
2357  *
2358  * Advance a point of the associated number of bytes (not UTF8 chars)
2359  *
2360  * Returns -1 in case of failure, 0 otherwise
2361  */
2362 static int
2363 xmlXPtrAdvanceChar(xmlNodePtr *node, int *indx, int bytes) {
2364     xmlNodePtr cur;
2365     int pos;
2366     int len;
2367
2368     if ((node == NULL) || (indx == NULL))
2369         return(-1);
2370     cur = *node;
2371     if (cur == NULL)
2372         return(-1);
2373     pos = *indx;
2374
2375     while (bytes >= 0) {
2376         /*
2377          * First position to the beginning of the first text node
2378          * corresponding to this point
2379          */
2380         while ((cur != NULL) &&
2381                ((cur->type == XML_ELEMENT_NODE) ||
2382                 (cur->type == XML_DOCUMENT_NODE) ||
2383                 (cur->type == XML_HTML_DOCUMENT_NODE))) {
2384             if (pos > 0) {
2385                 cur = xmlXPtrGetNthChild(cur, pos);
2386                 pos = 0;
2387             } else {
2388                 cur = xmlXPtrAdvanceNode(cur, NULL);
2389                 pos = 0;
2390             }
2391         }
2392
2393         if (cur == NULL) {
2394             *node = NULL;
2395             *indx = 0;
2396             return(-1);
2397         }
2398
2399         /*
2400          * if there is no move needed return the current value.
2401          */
2402         if (pos == 0) pos = 1;
2403         if (bytes == 0) {
2404             *node = cur;
2405             *indx = pos;
2406             return(0);
2407         }
2408         /*
2409          * We should have a text (or cdata) node ...
2410          */
2411         len = 0;
2412         if ((cur->type != XML_ELEMENT_NODE) &&
2413             (cur->content != NULL)) {
2414             len = xmlStrlen(cur->content);
2415         }
2416         if (pos > len) {
2417             /* Strange, the indx in the text node is greater than it's len */
2418             STRANGE
2419             pos = len;
2420         }
2421         if (pos + bytes >= len) {
2422             bytes -= (len - pos);
2423             cur = xmlXPtrAdvanceNode(cur, NULL);
2424             pos = 0;
2425         } else if (pos + bytes < len) {
2426             pos += bytes;
2427             *node = cur;
2428             *indx = pos;
2429             return(0);
2430         }
2431     }
2432     return(-1);
2433 }
2434
2435 /**
2436  * xmlXPtrMatchString:
2437  * @string:  the string to search
2438  * @start:  the start textnode
2439  * @startindex:  the start index
2440  * @end:  the end textnode IN/OUT
2441  * @endindex:  the end index IN/OUT
2442  *
2443  * Check whether the document contains @string at the position
2444  * (@start, @startindex) and limited by the (@end, @endindex) point
2445  *
2446  * Returns -1 in case of failure, 0 if not found, 1 if found in which case
2447  *            (@start, @startindex) will indicate the position of the beginning
2448  *            of the range and (@end, @endindex) will indicate the end
2449  *            of the range
2450  */
2451 static int
2452 xmlXPtrMatchString(const xmlChar *string, xmlNodePtr start, int startindex,
2453                     xmlNodePtr *end, int *endindex) {
2454     xmlNodePtr cur;
2455     int pos; /* 0 based */
2456     int len; /* in bytes */
2457     int stringlen; /* in bytes */
2458     int match;
2459
2460     if (string == NULL)
2461         return(-1);
2462     if (start == NULL)
2463         return(-1);
2464     if ((end == NULL) || (endindex == NULL))
2465         return(-1);
2466     cur = start;
2467     if (cur == NULL)
2468         return(-1);
2469     pos = startindex - 1;
2470     stringlen = xmlStrlen(string);
2471
2472     while (stringlen > 0) {
2473         if ((cur == *end) && (pos + stringlen > *endindex))
2474             return(0);
2475
2476         if ((cur->type != XML_ELEMENT_NODE) && (cur->content != NULL)) {
2477             len = xmlStrlen(cur->content);
2478             if (len >= pos + stringlen) {
2479                 match = (!xmlStrncmp(&cur->content[pos], string, stringlen));
2480                 if (match) {
2481 #ifdef DEBUG_RANGES
2482                     xmlGenericError(xmlGenericErrorContext,
2483                             "found range %d bytes at index %d of ->",
2484                             stringlen, pos + 1);
2485                     xmlDebugDumpString(stdout, cur->content);
2486                     xmlGenericError(xmlGenericErrorContext, "\n");
2487 #endif
2488                     *end = cur;
2489                     *endindex = pos + stringlen;
2490                     return(1);
2491                 } else {
2492                     return(0);
2493                 }
2494             } else {
2495                 int sub = len - pos;
2496                 match = (!xmlStrncmp(&cur->content[pos], string, sub));
2497                 if (match) {
2498 #ifdef DEBUG_RANGES
2499                     xmlGenericError(xmlGenericErrorContext,
2500                             "found subrange %d bytes at index %d of ->",
2501                             sub, pos + 1);
2502                     xmlDebugDumpString(stdout, cur->content);
2503                     xmlGenericError(xmlGenericErrorContext, "\n");
2504 #endif
2505                     string = &string[sub];
2506                     stringlen -= sub;
2507                 } else {
2508                     return(0);
2509                 }
2510             }
2511         }
2512         cur = xmlXPtrAdvanceNode(cur, NULL);
2513         if (cur == NULL)
2514             return(0);
2515         pos = 0;
2516     }
2517     return(1);
2518 }
2519
2520 /**
2521  * xmlXPtrSearchString:
2522  * @string:  the string to search
2523  * @start:  the start textnode IN/OUT
2524  * @startindex:  the start index IN/OUT
2525  * @end:  the end textnode
2526  * @endindex:  the end index
2527  *
2528  * Search the next occurrence of @string within the document content
2529  * until the (@end, @endindex) point is reached
2530  *
2531  * Returns -1 in case of failure, 0 if not found, 1 if found in which case
2532  *            (@start, @startindex) will indicate the position of the beginning
2533  *            of the range and (@end, @endindex) will indicate the end
2534  *            of the range
2535  */
2536 static int
2537 xmlXPtrSearchString(const xmlChar *string, xmlNodePtr *start, int *startindex,
2538                     xmlNodePtr *end, int *endindex) {
2539     xmlNodePtr cur;
2540     const xmlChar *str;
2541     int pos; /* 0 based */
2542     int len; /* in bytes */
2543     xmlChar first;
2544
2545     if (string == NULL)
2546         return(-1);
2547     if ((start == NULL) || (startindex == NULL))
2548         return(-1);
2549     if ((end == NULL) || (endindex == NULL))
2550         return(-1);
2551     cur = *start;
2552     if (cur == NULL)
2553         return(-1);
2554     pos = *startindex - 1;
2555     first = string[0];
2556
2557     while (cur != NULL) {
2558         if ((cur->type != XML_ELEMENT_NODE) && (cur->content != NULL)) {
2559             len = xmlStrlen(cur->content);
2560             while (pos <= len) {
2561                 if (first != 0) {
2562                     str = xmlStrchr(&cur->content[pos], first);
2563                     if (str != NULL) {
2564                         pos = (str - (xmlChar *)(cur->content));
2565 #ifdef DEBUG_RANGES
2566                         xmlGenericError(xmlGenericErrorContext,
2567                                 "found '%c' at index %d of ->",
2568                                 first, pos + 1);
2569                         xmlDebugDumpString(stdout, cur->content);
2570                         xmlGenericError(xmlGenericErrorContext, "\n");
2571 #endif
2572                         if (xmlXPtrMatchString(string, cur, pos + 1,
2573                                                end, endindex)) {
2574                             *start = cur;
2575                             *startindex = pos + 1;
2576                             return(1);
2577                         }
2578                         pos++;
2579                     } else {
2580                         pos = len + 1;
2581                     }
2582                 } else {
2583                     /*
2584                      * An empty string is considered to match before each
2585                      * character of the string-value and after the final
2586                      * character.
2587                      */
2588 #ifdef DEBUG_RANGES
2589                     xmlGenericError(xmlGenericErrorContext,
2590                             "found '' at index %d of ->",
2591                             pos + 1);
2592                     xmlDebugDumpString(stdout, cur->content);
2593                     xmlGenericError(xmlGenericErrorContext, "\n");
2594 #endif
2595                     *start = cur;
2596                     *startindex = pos + 1;
2597                     *end = cur;
2598                     *endindex = pos + 1;
2599                     return(1);
2600                 }
2601             }
2602         }
2603         if ((cur == *end) && (pos >= *endindex))
2604             return(0);
2605         cur = xmlXPtrAdvanceNode(cur, NULL);
2606         if (cur == NULL)
2607             return(0);
2608         pos = 1;
2609     }
2610     return(0);
2611 }
2612
2613 /**
2614  * xmlXPtrGetLastChar:
2615  * @node:  the node
2616  * @index:  the index
2617  *
2618  * Computes the point coordinates of the last char of this point
2619  *
2620  * Returns -1 in case of failure, 0 otherwise
2621  */
2622 static int
2623 xmlXPtrGetLastChar(xmlNodePtr *node, int *indx) {
2624     xmlNodePtr cur;
2625     int pos, len = 0;
2626
2627     if ((node == NULL) || (indx == NULL))
2628         return(-1);
2629     cur = *node;
2630     pos = *indx;
2631
2632     if (cur == NULL)
2633         return(-1);
2634
2635     if ((cur->type == XML_ELEMENT_NODE) ||
2636         (cur->type == XML_DOCUMENT_NODE) ||
2637         (cur->type == XML_HTML_DOCUMENT_NODE)) {
2638         if (pos > 0) {
2639             cur = xmlXPtrGetNthChild(cur, pos);
2640         }
2641     }
2642     while (cur != NULL) {
2643         if (cur->last != NULL)
2644             cur = cur->last;
2645         else if ((cur->type != XML_ELEMENT_NODE) &&
2646                  (cur->content != NULL)) {
2647             len = xmlStrlen(cur->content);
2648             break;
2649         } else {
2650             return(-1);
2651         }
2652     }
2653     if (cur == NULL)
2654         return(-1);
2655     *node = cur;
2656     *indx = len;
2657     return(0);
2658 }
2659
2660 /**
2661  * xmlXPtrGetStartPoint:
2662  * @obj:  an range
2663  * @node:  the resulting node
2664  * @indx:  the resulting index
2665  *
2666  * read the object and return the start point coordinates.
2667  *
2668  * Returns -1 in case of failure, 0 otherwise
2669  */
2670 static int
2671 xmlXPtrGetStartPoint(xmlXPathObjectPtr obj, xmlNodePtr *node, int *indx) {
2672     if ((obj == NULL) || (node == NULL) || (indx == NULL))
2673         return(-1);
2674
2675     switch (obj->type) {
2676         case XPATH_POINT:
2677             *node = obj->user;
2678             if (obj->index <= 0)
2679                 *indx = 0;
2680             else
2681                 *indx = obj->index;
2682             return(0);
2683         case XPATH_RANGE:
2684             *node = obj->user;
2685             if (obj->index <= 0)
2686                 *indx = 0;
2687             else
2688                 *indx = obj->index;
2689             return(0);
2690         default:
2691             break;
2692     }
2693     return(-1);
2694 }
2695
2696 /**
2697  * xmlXPtrGetEndPoint:
2698  * @obj:  an range
2699  * @node:  the resulting node
2700  * @indx:  the resulting indx
2701  *
2702  * read the object and return the end point coordinates.
2703  *
2704  * Returns -1 in case of failure, 0 otherwise
2705  */
2706 static int
2707 xmlXPtrGetEndPoint(xmlXPathObjectPtr obj, xmlNodePtr *node, int *indx) {
2708     if ((obj == NULL) || (node == NULL) || (indx == NULL))
2709         return(-1);
2710
2711     switch (obj->type) {
2712         case XPATH_POINT:
2713             *node = obj->user;
2714             if (obj->index <= 0)
2715                 *indx = 0;
2716             else
2717                 *indx = obj->index;
2718             return(0);
2719         case XPATH_RANGE:
2720             *node = obj->user;
2721             if (obj->index <= 0)
2722                 *indx = 0;
2723             else
2724                 *indx = obj->index;
2725             return(0);
2726         default:
2727             break;
2728     }
2729     return(-1);
2730 }
2731
2732 /**
2733  * xmlXPtrStringRangeFunction:
2734  * @ctxt:  the XPointer Parser context
2735  * @nargs:  the number of args
2736  *
2737  * Function implementing the string-range() function
2738  * range as described in 5.4.2
2739  *
2740  * ------------------------------
2741  * [Definition: For each location in the location-set argument,
2742  * string-range returns a set of string ranges, a set of substrings in a
2743  * string. Specifically, the string-value of the location is searched for
2744  * substrings that match the string argument, and the resulting location-set
2745  * will contain a range location for each non-overlapping match.]
2746  * An empty string is considered to match before each character of the
2747  * string-value and after the final character. Whitespace in a string
2748  * is matched literally, with no normalization except that provided by
2749  * XML for line ends. The third argument gives the position of the first
2750  * character to be in the resulting range, relative to the start of the
2751  * match. The default value is 1, which makes the range start immediately
2752  * before the first character of the matched string. The fourth argument
2753  * gives the number of characters in the range; the default is that the
2754  * range extends to the end of the matched string.
2755  *
2756  * Element boundaries, as well as entire embedded nodes such as processing
2757  * instructions and comments, are ignored as defined in [XPath].
2758  *
2759  * If the string in the second argument is not found in the string-value
2760  * of the location, or if a value in the third or fourth argument indicates
2761  * a string that is beyond the beginning or end of the document, the
2762  * expression fails.
2763  *
2764  * The points of the range-locations in the returned location-set will
2765  * all be character points.
2766  * ------------------------------
2767  */
2768 static void
2769 xmlXPtrStringRangeFunction(xmlXPathParserContextPtr ctxt, int nargs) {
2770     int i, startindex, endindex = 0, fendindex;
2771     xmlNodePtr start, end = 0, fend;
2772     xmlXPathObjectPtr set;
2773     xmlLocationSetPtr oldset;
2774     xmlLocationSetPtr newset;
2775     xmlXPathObjectPtr string;
2776     xmlXPathObjectPtr position = NULL;
2777     xmlXPathObjectPtr number = NULL;
2778     int found, pos = 0, num = 0;
2779
2780     /*
2781      * Grab the arguments
2782      */
2783     if ((nargs < 2) || (nargs > 4))
2784         XP_ERROR(XPATH_INVALID_ARITY);
2785
2786     if (nargs >= 4) {
2787         CHECK_TYPE(XPATH_NUMBER);
2788         number = valuePop(ctxt);
2789         if (number != NULL)
2790             num = (int) number->floatval;
2791     }
2792     if (nargs >= 3) {
2793         CHECK_TYPE(XPATH_NUMBER);
2794         position = valuePop(ctxt);
2795         if (position != NULL)
2796             pos = (int) position->floatval;
2797     }
2798     CHECK_TYPE(XPATH_STRING);
2799     string = valuePop(ctxt);
2800     if ((ctxt->value == NULL) ||
2801         ((ctxt->value->type != XPATH_LOCATIONSET) &&
2802          (ctxt->value->type != XPATH_NODESET)))
2803         XP_ERROR(XPATH_INVALID_TYPE)
2804
2805     set = valuePop(ctxt);
2806     newset = xmlXPtrLocationSetCreate(NULL);
2807     if (set->nodesetval == NULL) {
2808         goto error;
2809     }
2810     if (set->type == XPATH_NODESET) {
2811         xmlXPathObjectPtr tmp;
2812
2813         /*
2814          * First convert to a location set
2815          */
2816         tmp = xmlXPtrNewLocationSetNodeSet(set->nodesetval);
2817         xmlXPathFreeObject(set);
2818         set = tmp;
2819     }
2820     oldset = (xmlLocationSetPtr) set->user;
2821
2822     /*
2823      * The loop is to search for each element in the location set
2824      * the list of location set corresponding to that search
2825      */
2826     for (i = 0;i < oldset->locNr;i++) {
2827 #ifdef DEBUG_RANGES
2828         xmlXPathDebugDumpObject(stdout, oldset->locTab[i], 0);
2829 #endif
2830
2831         xmlXPtrGetStartPoint(oldset->locTab[i], &start, &startindex);
2832         xmlXPtrGetEndPoint(oldset->locTab[i], &end, &endindex);
2833         xmlXPtrAdvanceChar(&start, &startindex, 0);
2834         xmlXPtrGetLastChar(&end, &endindex);
2835
2836 #ifdef DEBUG_RANGES
2837         xmlGenericError(xmlGenericErrorContext,
2838                 "from index %d of ->", startindex);
2839         xmlDebugDumpString(stdout, start->content);
2840         xmlGenericError(xmlGenericErrorContext, "\n");
2841         xmlGenericError(xmlGenericErrorContext,
2842                 "to index %d of ->", endindex);
2843         xmlDebugDumpString(stdout, end->content);
2844         xmlGenericError(xmlGenericErrorContext, "\n");
2845 #endif
2846         do {
2847             fend = end;
2848             fendindex = endindex;
2849             found = xmlXPtrSearchString(string->stringval, &start, &startindex,
2850                                         &fend, &fendindex);
2851             if (found == 1) {
2852                 if (position == NULL) {
2853                     xmlXPtrLocationSetAdd(newset,
2854                          xmlXPtrNewRange(start, startindex, fend, fendindex));
2855                 } else if (xmlXPtrAdvanceChar(&start, &startindex,
2856                                               pos - 1) == 0) {
2857                     if ((number != NULL) && (num > 0)) {
2858                         int rindx;
2859                         xmlNodePtr rend;
2860                         rend = start;
2861                         rindx = startindex - 1;
2862                         if (xmlXPtrAdvanceChar(&rend, &rindx,
2863                                                num) == 0) {
2864                             xmlXPtrLocationSetAdd(newset,
2865                                         xmlXPtrNewRange(start, startindex,
2866                                                         rend, rindx));
2867                         }
2868                     } else if ((number != NULL) && (num <= 0)) {
2869                         xmlXPtrLocationSetAdd(newset,
2870                                     xmlXPtrNewRange(start, startindex,
2871                                                     start, startindex));
2872                     } else {
2873                         xmlXPtrLocationSetAdd(newset,
2874                                     xmlXPtrNewRange(start, startindex,
2875                                                     fend, fendindex));
2876                     }
2877                 }
2878                 start = fend;
2879                 startindex = fendindex;
2880                 if (string->stringval[0] == 0)
2881                     startindex++;
2882             }
2883         } while (found == 1);
2884     }
2885
2886     /*
2887      * Save the new value and cleanup
2888      */
2889 error:
2890     valuePush(ctxt, xmlXPtrWrapLocationSet(newset));
2891     xmlXPathFreeObject(set);
2892     xmlXPathFreeObject(string);
2893     if (position) xmlXPathFreeObject(position);
2894     if (number) xmlXPathFreeObject(number);
2895 }
2896
2897 /**
2898  * xmlXPtrEvalRangePredicate:
2899  * @ctxt:  the XPointer Parser context
2900  *
2901  *  [8]   Predicate ::=   '[' PredicateExpr ']'
2902  *  [9]   PredicateExpr ::=   Expr
2903  *
2904  * Evaluate a predicate as in xmlXPathEvalPredicate() but for
2905  * a Location Set instead of a node set
2906  */
2907 void
2908 xmlXPtrEvalRangePredicate(xmlXPathParserContextPtr ctxt) {
2909     const xmlChar *cur;
2910     xmlXPathObjectPtr res;
2911     xmlXPathObjectPtr obj, tmp;
2912     xmlLocationSetPtr newset = NULL;
2913     xmlLocationSetPtr oldset;
2914     int i;
2915
2916     if (ctxt == NULL) return;
2917
2918     SKIP_BLANKS;
2919     if (CUR != '[') {
2920         XP_ERROR(XPATH_INVALID_PREDICATE_ERROR);
2921     }
2922     NEXT;
2923     SKIP_BLANKS;
2924
2925     /*
2926      * Extract the old set, and then evaluate the result of the
2927      * expression for all the element in the set. use it to grow
2928      * up a new set.
2929      */
2930     CHECK_TYPE(XPATH_LOCATIONSET);
2931     obj = valuePop(ctxt);
2932     oldset = obj->user;
2933     ctxt->context->node = NULL;
2934
2935     if ((oldset == NULL) || (oldset->locNr == 0)) {
2936         ctxt->context->contextSize = 0;
2937         ctxt->context->proximityPosition = 0;
2938         xmlXPathEvalExpr(ctxt);
2939         res = valuePop(ctxt);
2940         if (res != NULL)
2941             xmlXPathFreeObject(res);
2942         valuePush(ctxt, obj);
2943         CHECK_ERROR;
2944     } else {
2945         /*
2946          * Save the expression pointer since we will have to evaluate
2947          * it multiple times. Initialize the new set.
2948          */
2949         cur = ctxt->cur;
2950         newset = xmlXPtrLocationSetCreate(NULL);
2951
2952         for (i = 0; i < oldset->locNr; i++) {
2953             ctxt->cur = cur;
2954
2955             /*
2956              * Run the evaluation with a node list made of a single item
2957              * in the nodeset.
2958              */
2959             ctxt->context->node = oldset->locTab[i]->user;
2960             tmp = xmlXPathNewNodeSet(ctxt->context->node);
2961             valuePush(ctxt, tmp);
2962             ctxt->context->contextSize = oldset->locNr;
2963             ctxt->context->proximityPosition = i + 1;
2964
2965             xmlXPathEvalExpr(ctxt);
2966             CHECK_ERROR;
2967
2968             /*
2969              * The result of the evaluation need to be tested to
2970              * decided whether the filter succeeded or not
2971              */
2972             res = valuePop(ctxt);
2973             if (xmlXPathEvaluatePredicateResult(ctxt, res)) {
2974                 xmlXPtrLocationSetAdd(newset,
2975                         xmlXPathObjectCopy(oldset->locTab[i]));
2976             }
2977
2978             /*
2979              * Cleanup
2980              */
2981             if (res != NULL)
2982                 xmlXPathFreeObject(res);
2983             if (ctxt->value == tmp) {
2984                 res = valuePop(ctxt);
2985                 xmlXPathFreeObject(res);
2986             }
2987
2988             ctxt->context->node = NULL;
2989         }
2990
2991         /*
2992          * The result is used as the new evaluation set.
2993          */
2994         xmlXPathFreeObject(obj);
2995         ctxt->context->node = NULL;
2996         ctxt->context->contextSize = -1;
2997         ctxt->context->proximityPosition = -1;
2998         valuePush(ctxt, xmlXPtrWrapLocationSet(newset));
2999     }
3000     if (CUR != ']') {
3001         XP_ERROR(XPATH_INVALID_PREDICATE_ERROR);
3002     }
3003
3004     NEXT;
3005     SKIP_BLANKS;
3006 }
3007
3008 #define bottom_xpointer
3009 #include "elfgcchack.h"
3010 #endif
3011