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