xpointer.c

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