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