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