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