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) || (cur->type == XML_NAMESPACE_DECL))
 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) || (cur->type == XML_NAMESPACE_DECL))
 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) || (cur->type == XML_NAMESPACE_DECL))
 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) || (start->type == XML_NAMESPACE_DECL))
1448         return(NULL);
1449     end = range->user2;
1450     if (end == NULL)
1451         return(xmlCopyNode(start, 1));
1452     if (end->type == XML_NAMESPACE_DECL)
1453         return(NULL);
1454
1455     cur = start;
1456     index1 = range->index;
1457     index2 = range->index2;
1458     while (cur != NULL) {
1459         if (cur == end) {
1460             if (cur->type == XML_TEXT_NODE) {
1461                 const xmlChar *content = cur->content;
1462                 int len;
1463
1464                 if (content == NULL) {
1465                     tmp = xmlNewTextLen(NULL, 0);
1466                 } else {
1467                     len = index2;
1468                     if ((cur == start) && (index1 > 1)) {
1469                         content += (index1 - 1);
1470                         len -= (index1 - 1);
1471                         index1 = 0;
1472                     } else {
1473                         len = index2;
1474                     }
1475                     tmp = xmlNewTextLen(content, len);
1476                 }
1477                 /* single sub text node selection */
1478                 if (list == NULL)
1479                     return(tmp);
1480                 /* prune and return full set */
1481                 if (last != NULL)
1482                     xmlAddNextSibling(last, tmp);
1483                 else
1484                     xmlAddChild(parent, tmp);
1485                 return(list);
1486             } else {
1487                 tmp = xmlCopyNode(cur, 0);
1488                 if (list == NULL)
1489                     list = tmp;
1490                 else {
1491                     if (last != NULL)
1492                         xmlAddNextSibling(last, tmp);
1493                     else
1494                         xmlAddChild(parent, tmp);
1495                 }
1496                 last = NULL;
1497                 parent = tmp;
1498
1499                 if (index2 > 1) {
1500                     end = xmlXPtrGetNthChild(cur, index2 - 1);
1501                     index2 = 0;
1502                 }
1503                 if ((cur == start) && (index1 > 1)) {
1504                     cur = xmlXPtrGetNthChild(cur, index1 - 1);
1505                     index1 = 0;
1506                 } else {
1507                     cur = cur->children;
1508                 }
1509                 /*
1510                  * Now gather the remaining nodes from cur to end
1511                  */
1512                 continue; /* while */
1513             }
1514         } else if ((cur == start) &&
1515                    (list == NULL) /* looks superfluous but ... */ ) {
1516             if ((cur->type == XML_TEXT_NODE) ||
1517                 (cur->type == XML_CDATA_SECTION_NODE)) {
1518                 const xmlChar *content = cur->content;
1519
1520                 if (content == NULL) {
1521                     tmp = xmlNewTextLen(NULL, 0);
1522                 } else {
1523                     if (index1 > 1) {
1524                         content += (index1 - 1);
1525                     }
1526                     tmp = xmlNewText(content);
1527                 }
1528                 last = list = tmp;
1529             } else {
1530                 if ((cur == start) && (index1 > 1)) {
1531                     tmp = xmlCopyNode(cur, 0);
1532                     list = tmp;
1533                     parent = tmp;
1534                     last = NULL;
1535                     cur = xmlXPtrGetNthChild(cur, index1 - 1);
1536                     index1 = 0;
1537                     /*
1538                      * Now gather the remaining nodes from cur to end
1539                      */
1540                     continue; /* while */
1541                 }
1542                 tmp = xmlCopyNode(cur, 1);
1543                 list = tmp;
1544                 parent = NULL;
1545                 last = tmp;
1546             }
1547         } else {
1548             tmp = NULL;
1549             switch (cur->type) {
1550                 case XML_DTD_NODE:
1551                 case XML_ELEMENT_DECL:
1552                 case XML_ATTRIBUTE_DECL:
1553                 case XML_ENTITY_NODE:
1554                     /* Do not copy DTD informations */
1555                     break;
1556                 case XML_ENTITY_DECL:
1557                     TODO /* handle crossing entities -> stack needed */
1558                     break;
1559                 case XML_XINCLUDE_START:
1560                 case XML_XINCLUDE_END:
1561                     /* don't consider it part of the tree content */
1562                     break;
1563                 case XML_ATTRIBUTE_NODE:
1564                     /* Humm, should not happen ! */
1565                     STRANGE
1566                     break;
1567                 default:
1568                     tmp = xmlCopyNode(cur, 1);
1569                     break;
1570             }
1571             if (tmp != NULL) {
1572                 if ((list == NULL) || ((last == NULL) && (parent == NULL)))  {
1573                     STRANGE
1574                     return(NULL);
1575                 }
1576                 if (last != NULL)
1577                     xmlAddNextSibling(last, tmp);
1578                 else {
1579                     xmlAddChild(parent, tmp);
1580                     last = tmp;
1581                 }
1582             }
1583         }
1584         /*
1585          * Skip to next node in document order
1586          */
1587         if ((list == NULL) || ((last == NULL) && (parent == NULL)))  {
1588             STRANGE
1589             return(NULL);
1590         }
1591         cur = xmlXPtrAdvanceNode(cur, NULL);
1592     }
1593     return(list);
1594 }
1595
1596 /**
1597  * xmlXPtrBuildNodeList:
1598  * @obj:  the XPointer result from the evaluation.
1599  *
1600  * Build a node list tree copy of the XPointer result.
1601  * This will drop Attributes and Namespace declarations.
1602  *
1603  * Returns an xmlNodePtr list or NULL.
1604  *         the caller has to free the node tree.
1605  */
1606 xmlNodePtr
1607 xmlXPtrBuildNodeList(xmlXPathObjectPtr obj) {
1608     xmlNodePtr list = NULL, last = NULL;
1609     int i;
1610
1611     if (obj == NULL)
1612         return(NULL);
1613     switch (obj->type) {
1614         case XPATH_NODESET: {
1615             xmlNodeSetPtr set = obj->nodesetval;
1616             if (set == NULL)
1617                 return(NULL);
1618             for (i = 0;i < set->nodeNr;i++) {
1619                 if (set->nodeTab[i] == NULL)
1620                     continue;
1621                 switch (set->nodeTab[i]->type) {
1622                     case XML_TEXT_NODE:
1623                     case XML_CDATA_SECTION_NODE:
1624                     case XML_ELEMENT_NODE:
1625                     case XML_ENTITY_REF_NODE:
1626                     case XML_ENTITY_NODE:
1627                     case XML_PI_NODE:
1628                     case XML_COMMENT_NODE:
1629                     case XML_DOCUMENT_NODE:
1630                     case XML_HTML_DOCUMENT_NODE:
1631 #ifdef LIBXML_DOCB_ENABLED
1632                     case XML_DOCB_DOCUMENT_NODE:
1633 #endif
1634                     case XML_XINCLUDE_START:
1635                     case XML_XINCLUDE_END:
1636                         break;
1637                     case XML_ATTRIBUTE_NODE:
1638                     case XML_NAMESPACE_DECL:
1639                     case XML_DOCUMENT_TYPE_NODE:
1640                     case XML_DOCUMENT_FRAG_NODE:
1641                     case XML_NOTATION_NODE:
1642                     case XML_DTD_NODE:
1643                     case XML_ELEMENT_DECL:
1644                     case XML_ATTRIBUTE_DECL:
1645                     case XML_ENTITY_DECL:
1646                         continue; /* for */
1647                 }
1648                 if (last == NULL)
1649                     list = last = xmlCopyNode(set->nodeTab[i], 1);
1650                 else {
1651                     xmlAddNextSibling(last, xmlCopyNode(set->nodeTab[i], 1));
1652                     if (last->next != NULL)
1653                         last = last->next;
1654                 }
1655             }
1656             break;
1657         }
1658         case XPATH_LOCATIONSET: {
1659             xmlLocationSetPtr set = (xmlLocationSetPtr) obj->user;
1660             if (set == NULL)
1661                 return(NULL);
1662             for (i = 0;i < set->locNr;i++) {
1663                 if (last == NULL)
1664                     list = last = xmlXPtrBuildNodeList(set->locTab[i]);
1665                 else
1666                     xmlAddNextSibling(last,
1667                             xmlXPtrBuildNodeList(set->locTab[i]));
1668                 if (last != NULL) {
1669                     while (last->next != NULL)
1670                         last = last->next;
1671                 }
1672             }
1673             break;
1674         }
1675         case XPATH_RANGE:
1676             return(xmlXPtrBuildRangeNodeList(obj));
1677         case XPATH_POINT:
1678             return(xmlCopyNode(obj->user, 0));
1679         default:
1680             break;
1681     }
1682     return(list);
1683 }
1684
1685 /************************************************************************
1686  *                                                                      *
1687  *                      XPointer functions                              *
1688  *                                                                      *
1689  ************************************************************************/
1690
1691 /**
1692  * xmlXPtrNbLocChildren:
1693  * @node:  an xmlNodePtr
1694  *
1695  * Count the number of location children of @node or the length of the
1696  * string value in case of text/PI/Comments nodes
1697  *
1698  * Returns the number of location children
1699  */
1700 static int
1701 xmlXPtrNbLocChildren(xmlNodePtr node) {
1702     int ret = 0;
1703     if (node == NULL)
1704         return(-1);
1705     switch (node->type) {
1706         case XML_HTML_DOCUMENT_NODE:
1707         case XML_DOCUMENT_NODE:
1708         case XML_ELEMENT_NODE:
1709             node = node->children;
1710             while (node != NULL) {
1711                 if (node->type == XML_ELEMENT_NODE)
1712                     ret++;
1713                 node = node->next;
1714             }
1715             break;
1716         case XML_ATTRIBUTE_NODE:
1717             return(-1);
1718
1719         case XML_PI_NODE:
1720         case XML_COMMENT_NODE:
1721         case XML_TEXT_NODE:
1722         case XML_CDATA_SECTION_NODE:
1723         case XML_ENTITY_REF_NODE:
1724             ret = xmlStrlen(node->content);
1725             break;
1726         default:
1727             return(-1);
1728     }
1729     return(ret);
1730 }
1731
1732 /**
1733  * xmlXPtrHereFunction:
1734  * @ctxt:  the XPointer Parser context
1735  * @nargs:  the number of args
1736  *
1737  * Function implementing here() operation
1738  * as described in 5.4.3
1739  */
1740 static void
1741 xmlXPtrHereFunction(xmlXPathParserContextPtr ctxt, int nargs) {
1742     CHECK_ARITY(0);
1743
1744     if (ctxt->context->here == NULL)
1745         XP_ERROR(XPTR_SYNTAX_ERROR);
1746
1747     valuePush(ctxt, xmlXPtrNewLocationSetNodes(ctxt->context->here, NULL));
1748 }
1749
1750 /**
1751  * xmlXPtrOriginFunction:
1752  * @ctxt:  the XPointer Parser context
1753  * @nargs:  the number of args
1754  *
1755  * Function implementing origin() operation
1756  * as described in 5.4.3
1757  */
1758 static void
1759 xmlXPtrOriginFunction(xmlXPathParserContextPtr ctxt, int nargs) {
1760     CHECK_ARITY(0);
1761
1762     if (ctxt->context->origin == NULL)
1763         XP_ERROR(XPTR_SYNTAX_ERROR);
1764
1765     valuePush(ctxt, xmlXPtrNewLocationSetNodes(ctxt->context->origin, NULL));
1766 }
1767
1768 /**
1769  * xmlXPtrStartPointFunction:
1770  * @ctxt:  the XPointer Parser context
1771  * @nargs:  the number of args
1772  *
1773  * Function implementing start-point() operation
1774  * as described in 5.4.3
1775  * ----------------
1776  * location-set start-point(location-set)
1777  *
1778  * For each location x in the argument location-set, start-point adds a
1779  * location of type point to the result location-set. That point represents
1780  * the start point of location x and is determined by the following rules:
1781  *
1782  * - If x is of type point, the start point is x.
1783  * - If x is of type range, the start point is the start point of x.
1784  * - If x is of type root, element, text, comment, or processing instruction,
1785  * - the container node of the start point is x and the index is 0.
1786  * - If x is of type attribute or namespace, the function must signal a
1787  *   syntax error.
1788  * ----------------
1789  *
1790  */
1791 static void
1792 xmlXPtrStartPointFunction(xmlXPathParserContextPtr ctxt, int nargs) {
1793     xmlXPathObjectPtr tmp, obj, point;
1794     xmlLocationSetPtr newset = NULL;
1795     xmlLocationSetPtr oldset = NULL;
1796
1797     CHECK_ARITY(1);
1798     if ((ctxt->value == NULL) ||
1799         ((ctxt->value->type != XPATH_LOCATIONSET) &&
1800          (ctxt->value->type != XPATH_NODESET)))
1801         XP_ERROR(XPATH_INVALID_TYPE)
1802
1803     obj = valuePop(ctxt);
1804     if (obj->type == XPATH_NODESET) {
1805         /*
1806          * First convert to a location set
1807          */
1808         tmp = xmlXPtrNewLocationSetNodeSet(obj->nodesetval);
1809         xmlXPathFreeObject(obj);
1810         obj = tmp;
1811     }
1812
1813     newset = xmlXPtrLocationSetCreate(NULL);
1814     if (newset == NULL) {
1815         xmlXPathFreeObject(obj);
1816         XP_ERROR(XPATH_MEMORY_ERROR);
1817     }
1818     oldset = (xmlLocationSetPtr) obj->user;
1819     if (oldset != NULL) {
1820         int i;
1821
1822         for (i = 0; i < oldset->locNr; i++) {
1823             tmp = oldset->locTab[i];
1824             if (tmp == NULL)
1825                 continue;
1826             point = NULL;
1827             switch (tmp->type) {
1828                 case XPATH_POINT:
1829                     point = xmlXPtrNewPoint(tmp->user, tmp->index);
1830                     break;
1831                 case XPATH_RANGE: {
1832                     xmlNodePtr node = tmp->user;
1833                     if (node != NULL) {
1834                         if (node->type == XML_ATTRIBUTE_NODE) {
1835                             /* TODO: Namespace Nodes ??? */
1836                             xmlXPathFreeObject(obj);
1837                             xmlXPtrFreeLocationSet(newset);
1838                             XP_ERROR(XPTR_SYNTAX_ERROR);
1839                         }
1840                         point = xmlXPtrNewPoint(node, tmp->index);
1841                     }
1842                     break;
1843                 }
1844                 default:
1845                     /*** Should we raise an error ?
1846                     xmlXPathFreeObject(obj);
1847                     xmlXPathFreeObject(newset);
1848                     XP_ERROR(XPATH_INVALID_TYPE)
1849                     ***/
1850                     break;
1851             }
1852             if (point != NULL)
1853                 xmlXPtrLocationSetAdd(newset, point);
1854         }
1855     }
1856     xmlXPathFreeObject(obj);
1857     valuePush(ctxt, xmlXPtrWrapLocationSet(newset));
1858 }
1859
1860 /**
1861  * xmlXPtrEndPointFunction:
1862  * @ctxt:  the XPointer Parser context
1863  * @nargs:  the number of args
1864  *
1865  * Function implementing end-point() operation
1866  * as described in 5.4.3
1867  * ----------------------------
1868  * location-set end-point(location-set)
1869  *
1870  * For each location x in the argument location-set, end-point adds a
1871  * location of type point to the result location-set. That point represents
1872  * the end point of location x and is determined by the following rules:
1873  *
1874  * - If x is of type point, the resulting point is x.
1875  * - If x is of type range, the resulting point is the end point of x.
1876  * - If x is of type root or element, the container node of the resulting
1877  *   point is x and the index is the number of location children of x.
1878  * - If x is of type text, comment, or processing instruction, the container
1879  *   node of the resulting point is x and the index is the length of the
1880  *   string-value of x.
1881  * - If x is of type attribute or namespace, the function must signal a
1882  *   syntax error.
1883  * ----------------------------
1884  */
1885 static void
1886 xmlXPtrEndPointFunction(xmlXPathParserContextPtr ctxt, int nargs) {
1887     xmlXPathObjectPtr tmp, obj, point;
1888     xmlLocationSetPtr newset = NULL;
1889     xmlLocationSetPtr oldset = NULL;
1890
1891     CHECK_ARITY(1);
1892     if ((ctxt->value == NULL) ||
1893         ((ctxt->value->type != XPATH_LOCATIONSET) &&
1894          (ctxt->value->type != XPATH_NODESET)))
1895         XP_ERROR(XPATH_INVALID_TYPE)
1896
1897     obj = valuePop(ctxt);
1898     if (obj->type == XPATH_NODESET) {
1899         /*
1900          * First convert to a location set
1901          */
1902         tmp = xmlXPtrNewLocationSetNodeSet(obj->nodesetval);
1903         xmlXPathFreeObject(obj);
1904         obj = tmp;
1905     }
1906
1907     newset = xmlXPtrLocationSetCreate(NULL);
1908     oldset = (xmlLocationSetPtr) obj->user;
1909     if (oldset != NULL) {
1910         int i;
1911
1912         for (i = 0; i < oldset->locNr; i++) {
1913             tmp = oldset->locTab[i];
1914             if (tmp == NULL)
1915                 continue;
1916             point = NULL;
1917             switch (tmp->type) {
1918                 case XPATH_POINT:
1919                     point = xmlXPtrNewPoint(tmp->user, tmp->index);
1920                     break;
1921                 case XPATH_RANGE: {
1922                     xmlNodePtr node = tmp->user2;
1923                     if (node != NULL) {
1924                         if (node->type == XML_ATTRIBUTE_NODE) {
1925                             /* TODO: Namespace Nodes ??? */
1926                             xmlXPathFreeObject(obj);
1927                             xmlXPtrFreeLocationSet(newset);
1928                             XP_ERROR(XPTR_SYNTAX_ERROR);
1929                         }
1930                         point = xmlXPtrNewPoint(node, tmp->index2);
1931                     } else if (tmp->user == NULL) {
1932                         point = xmlXPtrNewPoint(node,
1933                                        xmlXPtrNbLocChildren(node));
1934                     }
1935                     break;
1936                 }
1937                 default:
1938                     /*** Should we raise an error ?
1939                     xmlXPathFreeObject(obj);
1940                     xmlXPathFreeObject(newset);
1941                     XP_ERROR(XPATH_INVALID_TYPE)
1942                     ***/
1943                     break;
1944             }
1945             if (point != NULL)
1946                 xmlXPtrLocationSetAdd(newset, point);
1947         }
1948     }
1949     xmlXPathFreeObject(obj);
1950     valuePush(ctxt, xmlXPtrWrapLocationSet(newset));
1951 }
1952
1953
1954 /**
1955  * xmlXPtrCoveringRange:
1956  * @ctxt:  the XPointer Parser context
1957  * @loc:  the location for which the covering range must be computed
1958  *
1959  * A covering range is a range that wholly encompasses a location
1960  * Section 5.3.3. Covering Ranges for All Location Types
1961  *        http://www.w3.org/TR/xptr#N2267
1962  *
1963  * Returns a new location or NULL in case of error
1964  */
1965 static xmlXPathObjectPtr
1966 xmlXPtrCoveringRange(xmlXPathParserContextPtr ctxt, xmlXPathObjectPtr loc) {
1967     if (loc == NULL)
1968         return(NULL);
1969     if ((ctxt == NULL) || (ctxt->context == NULL) ||
1970         (ctxt->context->doc == NULL))
1971         return(NULL);
1972     switch (loc->type) {
1973         case XPATH_POINT:
1974             return(xmlXPtrNewRange(loc->user, loc->index,
1975                                    loc->user, loc->index));
1976         case XPATH_RANGE:
1977             if (loc->user2 != NULL) {
1978                 return(xmlXPtrNewRange(loc->user, loc->index,
1979                                       loc->user2, loc->index2));
1980             } else {
1981                 xmlNodePtr node = (xmlNodePtr) loc->user;
1982                 if (node == (xmlNodePtr) ctxt->context->doc) {
1983                     return(xmlXPtrNewRange(node, 0, node,
1984                                            xmlXPtrGetArity(node)));
1985                 } else {
1986                     switch (node->type) {
1987                         case XML_ATTRIBUTE_NODE:
1988                         /* !!! our model is slightly different than XPath */
1989                             return(xmlXPtrNewRange(node, 0, node,
1990                                                    xmlXPtrGetArity(node)));
1991                         case XML_ELEMENT_NODE:
1992                         case XML_TEXT_NODE:
1993                         case XML_CDATA_SECTION_NODE:
1994                         case XML_ENTITY_REF_NODE:
1995                         case XML_PI_NODE:
1996                         case XML_COMMENT_NODE:
1997                         case XML_DOCUMENT_NODE:
1998                         case XML_NOTATION_NODE:
1999                         case XML_HTML_DOCUMENT_NODE: {
2000                             int indx = xmlXPtrGetIndex(node);
2001
2002                             node = node->parent;
2003                             return(xmlXPtrNewRange(node, indx - 1,
2004                                                    node, indx + 1));
2005                         }
2006                         default:
2007                             return(NULL);
2008                     }
2009                 }
2010             }
2011         default:
2012             TODO /* missed one case ??? */
2013     }
2014     return(NULL);
2015 }
2016
2017 /**
2018  * xmlXPtrRangeFunction:
2019  * @ctxt:  the XPointer Parser context
2020  * @nargs:  the number of args
2021  *
2022  * Function implementing the range() function 5.4.3
2023  *  location-set range(location-set )
2024  *
2025  *  The range function returns ranges covering the locations in
2026  *  the argument location-set. For each location x in the argument
2027  *  location-set, a range location representing the covering range of
2028  *  x is added to the result location-set.
2029  */
2030 static void
2031 xmlXPtrRangeFunction(xmlXPathParserContextPtr ctxt, int nargs) {
2032     int i;
2033     xmlXPathObjectPtr set;
2034     xmlLocationSetPtr oldset;
2035     xmlLocationSetPtr newset;
2036
2037     CHECK_ARITY(1);
2038     if ((ctxt->value == NULL) ||
2039         ((ctxt->value->type != XPATH_LOCATIONSET) &&
2040          (ctxt->value->type != XPATH_NODESET)))
2041         XP_ERROR(XPATH_INVALID_TYPE)
2042
2043     set = valuePop(ctxt);
2044     if (set->type == XPATH_NODESET) {
2045         xmlXPathObjectPtr tmp;
2046
2047         /*
2048          * First convert to a location set
2049          */
2050         tmp = xmlXPtrNewLocationSetNodeSet(set->nodesetval);
2051         xmlXPathFreeObject(set);
2052         set = tmp;
2053     }
2054     oldset = (xmlLocationSetPtr) set->user;
2055
2056     /*
2057      * The loop is to compute the covering range for each item and add it
2058      */
2059     newset = xmlXPtrLocationSetCreate(NULL);
2060     for (i = 0;i < oldset->locNr;i++) {
2061         xmlXPtrLocationSetAdd(newset,
2062                 xmlXPtrCoveringRange(ctxt, oldset->locTab[i]));
2063     }
2064
2065     /*
2066      * Save the new value and cleanup
2067      */
2068     valuePush(ctxt, xmlXPtrWrapLocationSet(newset));
2069     xmlXPathFreeObject(set);
2070 }
2071
2072 /**
2073  * xmlXPtrInsideRange:
2074  * @ctxt:  the XPointer Parser context
2075  * @loc:  the location for which the inside range must be computed
2076  *
2077  * A inside range is a range described in the range-inside() description
2078  *
2079  * Returns a new location or NULL in case of error
2080  */
2081 static xmlXPathObjectPtr
2082 xmlXPtrInsideRange(xmlXPathParserContextPtr ctxt, xmlXPathObjectPtr loc) {
2083     if (loc == NULL)
2084         return(NULL);
2085     if ((ctxt == NULL) || (ctxt->context == NULL) ||
2086         (ctxt->context->doc == NULL))
2087         return(NULL);
2088     switch (loc->type) {
2089         case XPATH_POINT: {
2090             xmlNodePtr node = (xmlNodePtr) loc->user;
2091             switch (node->type) {
2092                 case XML_PI_NODE:
2093                 case XML_COMMENT_NODE:
2094                 case XML_TEXT_NODE:
2095                 case XML_CDATA_SECTION_NODE: {
2096                     if (node->content == NULL) {
2097                         return(xmlXPtrNewRange(node, 0, node, 0));
2098                     } else {
2099                         return(xmlXPtrNewRange(node, 0, node,
2100                                                xmlStrlen(node->content)));
2101                     }
2102                 }
2103                 case XML_ATTRIBUTE_NODE:
2104                 case XML_ELEMENT_NODE:
2105                 case XML_ENTITY_REF_NODE:
2106                 case XML_DOCUMENT_NODE:
2107                 case XML_NOTATION_NODE:
2108                 case XML_HTML_DOCUMENT_NODE: {
2109                     return(xmlXPtrNewRange(node, 0, node,
2110                                            xmlXPtrGetArity(node)));
2111                 }
2112                 default:
2113                     break;
2114             }
2115             return(NULL);
2116         }
2117         case XPATH_RANGE: {
2118             xmlNodePtr node = (xmlNodePtr) loc->user;
2119             if (loc->user2 != NULL) {
2120                 return(xmlXPtrNewRange(node, loc->index,
2121                                        loc->user2, loc->index2));
2122             } else {
2123                 switch (node->type) {
2124                     case XML_PI_NODE:
2125                     case XML_COMMENT_NODE:
2126                     case XML_TEXT_NODE:
2127                     case XML_CDATA_SECTION_NODE: {
2128                         if (node->content == NULL) {
2129                             return(xmlXPtrNewRange(node, 0, node, 0));
2130                         } else {
2131                             return(xmlXPtrNewRange(node, 0, node,
2132                                                    xmlStrlen(node->content)));
2133                         }
2134                     }
2135                     case XML_ATTRIBUTE_NODE:
2136                     case XML_ELEMENT_NODE:
2137                     case XML_ENTITY_REF_NODE:
2138                     case XML_DOCUMENT_NODE:
2139                     case XML_NOTATION_NODE:
2140                     case XML_HTML_DOCUMENT_NODE: {
2141                         return(xmlXPtrNewRange(node, 0, node,
2142                                                xmlXPtrGetArity(node)));
2143                     }
2144                     default:
2145                         break;
2146                 }
2147                 return(NULL);
2148             }
2149         }
2150         default:
2151             TODO /* missed one case ??? */
2152     }
2153     return(NULL);
2154 }
2155
2156 /**
2157  * xmlXPtrRangeInsideFunction:
2158  * @ctxt:  the XPointer Parser context
2159  * @nargs:  the number of args
2160  *
2161  * Function implementing the range-inside() function 5.4.3
2162  *  location-set range-inside(location-set )
2163  *
2164  *  The range-inside function returns ranges covering the contents of
2165  *  the locations in the argument location-set. For each location x in
2166  *  the argument location-set, a range location is added to the result
2167  *  location-set. If x is a range location, then x is added to the
2168  *  result location-set. If x is not a range location, then x is used
2169  *  as the container location of the start and end points of the range
2170  *  location to be added; the index of the start point of the range is
2171  *  zero; if the end point is a character point then its index is the
2172  *  length of the string-value of x, and otherwise is the number of
2173  *  location children of x.
2174  *
2175  */
2176 static void
2177 xmlXPtrRangeInsideFunction(xmlXPathParserContextPtr ctxt, int nargs) {
2178     int i;
2179     xmlXPathObjectPtr set;
2180     xmlLocationSetPtr oldset;
2181     xmlLocationSetPtr newset;
2182
2183     CHECK_ARITY(1);
2184     if ((ctxt->value == NULL) ||
2185         ((ctxt->value->type != XPATH_LOCATIONSET) &&
2186          (ctxt->value->type != XPATH_NODESET)))
2187         XP_ERROR(XPATH_INVALID_TYPE)
2188
2189     set = valuePop(ctxt);
2190     if (set->type == XPATH_NODESET) {
2191         xmlXPathObjectPtr tmp;
2192
2193         /*
2194          * First convert to a location set
2195          */
2196         tmp = xmlXPtrNewLocationSetNodeSet(set->nodesetval);
2197         xmlXPathFreeObject(set);
2198         set = tmp;
2199     }
2200     oldset = (xmlLocationSetPtr) set->user;
2201
2202     /*
2203      * The loop is to compute the covering range for each item and add it
2204      */
2205     newset = xmlXPtrLocationSetCreate(NULL);
2206     for (i = 0;i < oldset->locNr;i++) {
2207         xmlXPtrLocationSetAdd(newset,
2208                 xmlXPtrInsideRange(ctxt, oldset->locTab[i]));
2209     }
2210
2211     /*
2212      * Save the new value and cleanup
2213      */
2214     valuePush(ctxt, xmlXPtrWrapLocationSet(newset));
2215     xmlXPathFreeObject(set);
2216 }
2217
2218 /**
2219  * xmlXPtrRangeToFunction:
2220  * @ctxt:  the XPointer Parser context
2221  * @nargs:  the number of args
2222  *
2223  * Implement the range-to() XPointer function
2224  */
2225 void
2226 xmlXPtrRangeToFunction(xmlXPathParserContextPtr ctxt, int nargs) {
2227     xmlXPathObjectPtr range;
2228     const xmlChar *cur;
2229     xmlXPathObjectPtr res, obj;
2230     xmlXPathObjectPtr tmp;
2231     xmlLocationSetPtr newset = NULL;
2232     xmlNodeSetPtr oldset;
2233     int i;
2234
2235     if (ctxt == NULL) return;
2236     CHECK_ARITY(1);
2237     /*
2238      * Save the expression pointer since we will have to evaluate
2239      * it multiple times. Initialize the new set.
2240      */
2241     CHECK_TYPE(XPATH_NODESET);
2242     obj = valuePop(ctxt);
2243     oldset = obj->nodesetval;
2244     ctxt->context->node = NULL;
2245
2246     cur = ctxt->cur;
2247     newset = xmlXPtrLocationSetCreate(NULL);
2248
2249     for (i = 0; i < oldset->nodeNr; i++) {
2250         ctxt->cur = cur;
2251
2252         /*
2253          * Run the evaluation with a node list made of a single item
2254          * in the nodeset.
2255          */
2256         ctxt->context->node = oldset->nodeTab[i];
2257         tmp = xmlXPathNewNodeSet(ctxt->context->node);
2258         valuePush(ctxt, tmp);
2259
2260         xmlXPathEvalExpr(ctxt);
2261         CHECK_ERROR;
2262
2263         /*
2264          * The result of the evaluation need to be tested to
2265          * decided whether the filter succeeded or not
2266          */
2267         res = valuePop(ctxt);
2268         range = xmlXPtrNewRangeNodeObject(oldset->nodeTab[i], res);
2269         if (range != NULL) {
2270             xmlXPtrLocationSetAdd(newset, range);
2271         }
2272
2273         /*
2274          * Cleanup
2275          */
2276         if (res != NULL)
2277             xmlXPathFreeObject(res);
2278         if (ctxt->value == tmp) {
2279             res = valuePop(ctxt);
2280             xmlXPathFreeObject(res);
2281         }
2282
2283         ctxt->context->node = NULL;
2284     }
2285
2286     /*
2287      * The result is used as the new evaluation set.
2288      */
2289     xmlXPathFreeObject(obj);
2290     ctxt->context->node = NULL;
2291     ctxt->context->contextSize = -1;
2292     ctxt->context->proximityPosition = -1;
2293     valuePush(ctxt, xmlXPtrWrapLocationSet(newset));
2294 }
2295
2296 /**
2297  * xmlXPtrAdvanceNode:
2298  * @cur:  the node
2299  * @level: incremented/decremented to show level in tree
2300  *
2301  * Advance to the next element or text node in document order
2302  * TODO: add a stack for entering/exiting entities
2303  *
2304  * Returns -1 in case of failure, 0 otherwise
2305  */
2306 xmlNodePtr
2307 xmlXPtrAdvanceNode(xmlNodePtr cur, int *level) {
2308 next:
2309     if ((cur == NULL) || (cur->type == XML_NAMESPACE_DECL))
2310         return(NULL);
2311     if (cur->children != NULL) {
2312         cur = cur->children ;
2313         if (level != NULL)
2314             (*level)++;
2315         goto found;
2316     }
2317 skip:           /* This label should only be needed if something is wrong! */
2318     if (cur->next != NULL) {
2319         cur = cur->next;
2320         goto found;
2321     }
2322     do {
2323         cur = cur->parent;
2324         if (level != NULL)
2325             (*level)--;
2326         if (cur == NULL) return(NULL);
2327         if (cur->next != NULL) {
2328             cur = cur->next;
2329             goto found;
2330         }
2331     } while (cur != NULL);
2332
2333 found:
2334     if ((cur->type != XML_ELEMENT_NODE) &&
2335         (cur->type != XML_TEXT_NODE) &&
2336         (cur->type != XML_DOCUMENT_NODE) &&
2337         (cur->type != XML_HTML_DOCUMENT_NODE) &&
2338         (cur->type != XML_CDATA_SECTION_NODE)) {
2339             if (cur->type == XML_ENTITY_REF_NODE) {     /* Shouldn't happen */
2340                 TODO
2341                 goto skip;
2342             }
2343             goto next;
2344         }
2345     return(cur);
2346 }
2347
2348 /**
2349  * xmlXPtrAdvanceChar:
2350  * @node:  the node
2351  * @indx:  the indx
2352  * @bytes:  the number of bytes
2353  *
2354  * Advance a point of the associated number of bytes (not UTF8 chars)
2355  *
2356  * Returns -1 in case of failure, 0 otherwise
2357  */
2358 static int
2359 xmlXPtrAdvanceChar(xmlNodePtr *node, int *indx, int bytes) {
2360     xmlNodePtr cur;
2361     int pos;
2362     int len;
2363
2364     if ((node == NULL) || (indx == NULL))
2365         return(-1);
2366     cur = *node;
2367     if ((cur == NULL) || (cur->type == XML_NAMESPACE_DECL))
2368         return(-1);
2369     pos = *indx;
2370
2371     while (bytes >= 0) {
2372         /*
2373          * First position to the beginning of the first text node
2374          * corresponding to this point
2375          */
2376         while ((cur != NULL) &&
2377                ((cur->type == XML_ELEMENT_NODE) ||
2378                 (cur->type == XML_DOCUMENT_NODE) ||
2379                 (cur->type == XML_HTML_DOCUMENT_NODE))) {
2380             if (pos > 0) {
2381                 cur = xmlXPtrGetNthChild(cur, pos);
2382                 pos = 0;
2383             } else {
2384                 cur = xmlXPtrAdvanceNode(cur, NULL);
2385                 pos = 0;
2386             }
2387         }
2388
2389         if (cur == NULL) {
2390             *node = NULL;
2391             *indx = 0;
2392             return(-1);
2393         }
2394
2395         /*
2396          * if there is no move needed return the current value.
2397          */
2398         if (pos == 0) pos = 1;
2399         if (bytes == 0) {
2400             *node = cur;
2401             *indx = pos;
2402             return(0);
2403         }
2404         /*
2405          * We should have a text (or cdata) node ...
2406          */
2407         len = 0;
2408         if ((cur->type != XML_ELEMENT_NODE) &&
2409             (cur->content != NULL)) {
2410             len = xmlStrlen(cur->content);
2411         }
2412         if (pos > len) {
2413             /* Strange, the indx in the text node is greater than it's len */
2414             STRANGE
2415             pos = len;
2416         }
2417         if (pos + bytes >= len) {
2418             bytes -= (len - pos);
2419             cur = xmlXPtrAdvanceNode(cur, NULL);
2420             pos = 0;
2421         } else if (pos + bytes < len) {
2422             pos += bytes;
2423             *node = cur;
2424             *indx = pos;
2425             return(0);
2426         }
2427     }
2428     return(-1);
2429 }
2430
2431 /**
2432  * xmlXPtrMatchString:
2433  * @string:  the string to search
2434  * @start:  the start textnode
2435  * @startindex:  the start index
2436  * @end:  the end textnode IN/OUT
2437  * @endindex:  the end index IN/OUT
2438  *
2439  * Check whether the document contains @string at the position
2440  * (@start, @startindex) and limited by the (@end, @endindex) point
2441  *
2442  * Returns -1 in case of failure, 0 if not found, 1 if found in which case
2443  *            (@start, @startindex) will indicate the position of the beginning
2444  *            of the range and (@end, @endindex) will indicate the end
2445  *            of the range
2446  */
2447 static int
2448 xmlXPtrMatchString(const xmlChar *string, xmlNodePtr start, int startindex,
2449                     xmlNodePtr *end, int *endindex) {
2450     xmlNodePtr cur;
2451     int pos; /* 0 based */
2452     int len; /* in bytes */
2453     int stringlen; /* in bytes */
2454     int match;
2455
2456     if (string == NULL)
2457         return(-1);
2458     if ((start == NULL) || (start->type == XML_NAMESPACE_DECL))
2459         return(-1);
2460     if ((end == NULL) || (*end == NULL) ||
2461         ((*end)->type == XML_NAMESPACE_DECL) || (endindex == NULL))
2462         return(-1);
2463     cur = start;
2464     if (cur == NULL)
2465         return(-1);
2466     pos = startindex - 1;
2467     stringlen = xmlStrlen(string);
2468
2469     while (stringlen > 0) {
2470         if ((cur == *end) && (pos + stringlen > *endindex))
2471             return(0);
2472
2473         if ((cur->type != XML_ELEMENT_NODE) && (cur->content != NULL)) {
2474             len = xmlStrlen(cur->content);
2475             if (len >= pos + stringlen) {
2476                 match = (!xmlStrncmp(&cur->content[pos], string, stringlen));
2477                 if (match) {
2478 #ifdef DEBUG_RANGES
2479                     xmlGenericError(xmlGenericErrorContext,
2480                             "found range %d bytes at index %d of ->",
2481                             stringlen, pos + 1);
2482                     xmlDebugDumpString(stdout, cur->content);
2483                     xmlGenericError(xmlGenericErrorContext, "\n");
2484 #endif
2485                     *end = cur;
2486                     *endindex = pos + stringlen;
2487                     return(1);
2488                 } else {
2489                     return(0);
2490                 }
2491             } else {
2492                 int sub = len - pos;
2493                 match = (!xmlStrncmp(&cur->content[pos], string, sub));
2494                 if (match) {
2495 #ifdef DEBUG_RANGES
2496                     xmlGenericError(xmlGenericErrorContext,
2497                             "found subrange %d bytes at index %d of ->",
2498                             sub, pos + 1);
2499                     xmlDebugDumpString(stdout, cur->content);
2500                     xmlGenericError(xmlGenericErrorContext, "\n");
2501 #endif
2502                     string = &string[sub];
2503                     stringlen -= sub;
2504                 } else {
2505                     return(0);
2506                 }
2507             }
2508         }
2509         cur = xmlXPtrAdvanceNode(cur, NULL);
2510         if (cur == NULL)
2511             return(0);
2512         pos = 0;
2513     }
2514     return(1);
2515 }
2516
2517 /**
2518  * xmlXPtrSearchString:
2519  * @string:  the string to search
2520  * @start:  the start textnode IN/OUT
2521  * @startindex:  the start index IN/OUT
2522  * @end:  the end textnode
2523  * @endindex:  the end index
2524  *
2525  * Search the next occurrence of @string within the document content
2526  * until the (@end, @endindex) point is reached
2527  *
2528  * Returns -1 in case of failure, 0 if not found, 1 if found in which case
2529  *            (@start, @startindex) will indicate the position of the beginning
2530  *            of the range and (@end, @endindex) will indicate the end
2531  *            of the range
2532  */
2533 static int
2534 xmlXPtrSearchString(const xmlChar *string, xmlNodePtr *start, int *startindex,
2535                     xmlNodePtr *end, int *endindex) {
2536     xmlNodePtr cur;
2537     const xmlChar *str;
2538     int pos; /* 0 based */
2539     int len; /* in bytes */
2540     xmlChar first;
2541
2542     if (string == NULL)
2543         return(-1);
2544     if ((start == NULL) || (*start == NULL) ||
2545         ((*start)->type == XML_NAMESPACE_DECL) || (startindex == NULL))
2546         return(-1);
2547     if ((end == NULL) || (endindex == NULL))
2548         return(-1);
2549     cur = *start;
2550     pos = *startindex - 1;
2551     first = string[0];
2552
2553     while (cur != NULL) {
2554         if ((cur->type != XML_ELEMENT_NODE) && (cur->content != NULL)) {
2555             len = xmlStrlen(cur->content);
2556             while (pos <= len) {
2557                 if (first != 0) {
2558                     str = xmlStrchr(&cur->content[pos], first);
2559                     if (str != NULL) {
2560                         pos = (str - (xmlChar *)(cur->content));
2561 #ifdef DEBUG_RANGES
2562                         xmlGenericError(xmlGenericErrorContext,
2563                                 "found '%c' at index %d of ->",
2564                                 first, pos + 1);
2565                         xmlDebugDumpString(stdout, cur->content);
2566                         xmlGenericError(xmlGenericErrorContext, "\n");
2567 #endif
2568                         if (xmlXPtrMatchString(string, cur, pos + 1,
2569                                                end, endindex)) {
2570                             *start = cur;
2571                             *startindex = pos + 1;
2572                             return(1);
2573                         }
2574                         pos++;
2575                     } else {
2576                         pos = len + 1;
2577                     }
2578                 } else {
2579                     /*
2580                      * An empty string is considered to match before each
2581                      * character of the string-value and after the final
2582                      * character.
2583                      */
2584 #ifdef DEBUG_RANGES
2585                     xmlGenericError(xmlGenericErrorContext,
2586                             "found '' at index %d of ->",
2587                             pos + 1);
2588                     xmlDebugDumpString(stdout, cur->content);
2589                     xmlGenericError(xmlGenericErrorContext, "\n");
2590 #endif
2591                     *start = cur;
2592                     *startindex = pos + 1;
2593                     *end = cur;
2594                     *endindex = pos + 1;
2595                     return(1);
2596                 }
2597             }
2598         }
2599         if ((cur == *end) && (pos >= *endindex))
2600             return(0);
2601         cur = xmlXPtrAdvanceNode(cur, NULL);
2602         if (cur == NULL)
2603             return(0);
2604         pos = 1;
2605     }
2606     return(0);
2607 }
2608
2609 /**
2610  * xmlXPtrGetLastChar:
2611  * @node:  the node
2612  * @index:  the index
2613  *
2614  * Computes the point coordinates of the last char of this point
2615  *
2616  * Returns -1 in case of failure, 0 otherwise
2617  */
2618 static int
2619 xmlXPtrGetLastChar(xmlNodePtr *node, int *indx) {
2620     xmlNodePtr cur;
2621     int pos, len = 0;
2622
2623     if ((node == NULL) || (*node == NULL) ||
2624         ((*node)->type == XML_NAMESPACE_DECL) || (indx == NULL))
2625         return(-1);
2626     cur = *node;
2627     pos = *indx;
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