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