• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * pattern.c: Implemetation of the template match compilation and lookup
3  *
4  * Reference:
5  *   http://www.w3.org/TR/1999/REC-xslt-19991116
6  *
7  * See Copyright for the status of this software.
8  *
9  * daniel@veillard.com
10  */
11 
12 /*
13  * TODO: handle pathological cases like *[*[@a="b"]]
14  * TODO: detect [number] at compilation, optimize accordingly
15  */
16 
17 #define IN_LIBXSLT
18 #include "libxslt.h"
19 
20 #include <string.h>
21 
22 #include <libxml/xmlmemory.h>
23 #include <libxml/tree.h>
24 #include <libxml/valid.h>
25 #include <libxml/hash.h>
26 #include <libxml/xmlerror.h>
27 #include <libxml/parserInternals.h>
28 #include "xslt.h"
29 #include "xsltInternals.h"
30 #include "xsltutils.h"
31 #include "imports.h"
32 #include "templates.h"
33 #include "keys.h"
34 #include "pattern.h"
35 #include "documents.h"
36 
37 #ifdef WITH_XSLT_DEBUG
38 #define WITH_XSLT_DEBUG_PATTERN
39 #endif
40 
41 /*
42  * Types are private:
43  */
44 
45 typedef enum {
46     XSLT_OP_END=0,
47     XSLT_OP_ROOT,
48     XSLT_OP_ELEM,
49     XSLT_OP_ATTR,
50     XSLT_OP_PARENT,
51     XSLT_OP_ANCESTOR,
52     XSLT_OP_ID,
53     XSLT_OP_KEY,
54     XSLT_OP_NS,
55     XSLT_OP_ALL,
56     XSLT_OP_PI,
57     XSLT_OP_COMMENT,
58     XSLT_OP_TEXT,
59     XSLT_OP_NODE,
60     XSLT_OP_PREDICATE
61 } xsltOp;
62 
63 typedef enum {
64     AXIS_CHILD=1,
65     AXIS_ATTRIBUTE
66 } xsltAxis;
67 
68 typedef struct _xsltStepState xsltStepState;
69 typedef xsltStepState *xsltStepStatePtr;
70 struct _xsltStepState {
71     int step;
72     xmlNodePtr node;
73 };
74 
75 typedef struct _xsltStepStates xsltStepStates;
76 typedef xsltStepStates *xsltStepStatesPtr;
77 struct _xsltStepStates {
78     int nbstates;
79     int maxstates;
80     xsltStepStatePtr states;
81 };
82 
83 typedef struct _xsltStepOp xsltStepOp;
84 typedef xsltStepOp *xsltStepOpPtr;
85 struct _xsltStepOp {
86     xsltOp op;
87     xmlChar *value;
88     xmlChar *value2;
89     xmlChar *value3;
90     xmlXPathCompExprPtr comp;
91     /*
92      * Optimisations for count
93      */
94     int        previousExtra;
95     int        indexExtra;
96     int        lenExtra;
97 };
98 
99 struct _xsltCompMatch {
100     struct _xsltCompMatch *next; /* siblings in the name hash */
101     float priority;              /* the priority */
102     const xmlChar *pattern;       /* the pattern */
103     const xmlChar *mode;         /* the mode */
104     const xmlChar *modeURI;      /* the mode URI */
105     xsltTemplatePtr template;    /* the associated template */
106 
107     int direct;
108     /* TODO fix the statically allocated size steps[] */
109     int nbStep;
110     int maxStep;
111     xmlNsPtr *nsList;		/* the namespaces in scope */
112     int nsNr;			/* the number of namespaces in scope */
113     xsltStepOpPtr steps;        /* ops for computation */
114 };
115 
116 typedef struct _xsltParserContext xsltParserContext;
117 typedef xsltParserContext *xsltParserContextPtr;
118 struct _xsltParserContext {
119     xsltStylesheetPtr style;		/* the stylesheet */
120     xsltTransformContextPtr ctxt;	/* the transformation or NULL */
121     const xmlChar *cur;			/* the current char being parsed */
122     const xmlChar *base;		/* the full expression */
123     xmlDocPtr      doc;			/* the source document */
124     xmlNodePtr    elem;			/* the source element */
125     int error;				/* error code */
126     xsltCompMatchPtr comp;		/* the result */
127 };
128 
129 /************************************************************************
130  * 									*
131  * 			Type functions 					*
132  * 									*
133  ************************************************************************/
134 
135 /**
136  * xsltNewCompMatch:
137  *
138  * Create a new XSLT CompMatch
139  *
140  * Returns the newly allocated xsltCompMatchPtr or NULL in case of error
141  */
142 static xsltCompMatchPtr
xsltNewCompMatch(void)143 xsltNewCompMatch(void) {
144     xsltCompMatchPtr cur;
145 
146     cur = (xsltCompMatchPtr) xmlMalloc(sizeof(xsltCompMatch));
147     if (cur == NULL) {
148 	xsltTransformError(NULL, NULL, NULL,
149 		"xsltNewCompMatch : out of memory error\n");
150 	return(NULL);
151     }
152     memset(cur, 0, sizeof(xsltCompMatch));
153     cur->maxStep = 10;
154     cur->nbStep = 0;
155     cur-> steps = (xsltStepOpPtr) xmlMalloc(sizeof(xsltStepOp) *
156                                             cur->maxStep);
157     if (cur->steps == NULL) {
158 	xsltTransformError(NULL, NULL, NULL,
159 		"xsltNewCompMatch : out of memory error\n");
160 	xmlFree(cur);
161 	return(NULL);
162     }
163     cur->nsNr = 0;
164     cur->nsList = NULL;
165     cur->direct = 0;
166     return(cur);
167 }
168 
169 /**
170  * xsltFreeCompMatch:
171  * @comp:  an XSLT comp
172  *
173  * Free up the memory allocated by @comp
174  */
175 static void
xsltFreeCompMatch(xsltCompMatchPtr comp)176 xsltFreeCompMatch(xsltCompMatchPtr comp) {
177     xsltStepOpPtr op;
178     int i;
179 
180     if (comp == NULL)
181 	return;
182     if (comp->pattern != NULL)
183 	xmlFree((xmlChar *)comp->pattern);
184     if (comp->nsList != NULL)
185 	xmlFree(comp->nsList);
186     for (i = 0;i < comp->nbStep;i++) {
187 	op = &comp->steps[i];
188 	if (op->value != NULL)
189 	    xmlFree(op->value);
190 	if (op->value2 != NULL)
191 	    xmlFree(op->value2);
192 	if (op->value3 != NULL)
193 	    xmlFree(op->value3);
194 	if (op->comp != NULL)
195 	    xmlXPathFreeCompExpr(op->comp);
196     }
197     xmlFree(comp->steps);
198     memset(comp, -1, sizeof(xsltCompMatch));
199     xmlFree(comp);
200 }
201 
202 /**
203  * xsltFreeCompMatchList:
204  * @comp:  an XSLT comp list
205  *
206  * Free up the memory allocated by all the elements of @comp
207  */
208 void
xsltFreeCompMatchList(xsltCompMatchPtr comp)209 xsltFreeCompMatchList(xsltCompMatchPtr comp) {
210     xsltCompMatchPtr cur;
211 
212     while (comp != NULL) {
213 	cur = comp;
214 	comp = comp->next;
215 	xsltFreeCompMatch(cur);
216     }
217 }
218 
219 /**
220  * xsltNormalizeCompSteps:
221  * @payload: pointer to template hash table entry
222  * @data: pointer to the stylesheet
223  * @name: template match name
224  *
225  * This is a hashtable scanner function to normalize the compiled
226  * steps of an imported stylesheet.
227  */
xsltNormalizeCompSteps(void * payload,void * data,const xmlChar * name ATTRIBUTE_UNUSED)228 void xsltNormalizeCompSteps(void *payload,
229         void *data, const xmlChar *name ATTRIBUTE_UNUSED) {
230     xsltCompMatchPtr comp = payload;
231     xsltStylesheetPtr style = data;
232     int ix;
233 
234     for (ix = 0; ix < comp->nbStep; ix++) {
235         comp->steps[ix].previousExtra += style->extrasNr;
236         comp->steps[ix].indexExtra += style->extrasNr;
237         comp->steps[ix].lenExtra += style->extrasNr;
238     }
239 }
240 
241 /**
242  * xsltNewParserContext:
243  * @style:  the stylesheet
244  * @ctxt:  the transformation context, if done at run-time
245  *
246  * Create a new XSLT ParserContext
247  *
248  * Returns the newly allocated xsltParserContextPtr or NULL in case of error
249  */
250 static xsltParserContextPtr
xsltNewParserContext(xsltStylesheetPtr style,xsltTransformContextPtr ctxt)251 xsltNewParserContext(xsltStylesheetPtr style, xsltTransformContextPtr ctxt) {
252     xsltParserContextPtr cur;
253 
254     cur = (xsltParserContextPtr) xmlMalloc(sizeof(xsltParserContext));
255     if (cur == NULL) {
256 	xsltTransformError(NULL, NULL, NULL,
257 		"xsltNewParserContext : malloc failed\n");
258 	return(NULL);
259     }
260     memset(cur, 0, sizeof(xsltParserContext));
261     cur->style = style;
262     cur->ctxt = ctxt;
263     return(cur);
264 }
265 
266 /**
267  * xsltFreeParserContext:
268  * @ctxt:  an XSLT parser context
269  *
270  * Free up the memory allocated by @ctxt
271  */
272 static void
xsltFreeParserContext(xsltParserContextPtr ctxt)273 xsltFreeParserContext(xsltParserContextPtr ctxt) {
274     if (ctxt == NULL)
275 	return;
276     memset(ctxt, -1, sizeof(xsltParserContext));
277     xmlFree(ctxt);
278 }
279 
280 /**
281  * xsltCompMatchAdd:
282  * @comp:  the compiled match expression
283  * @op:  an op
284  * @value:  the first value
285  * @value2:  the second value
286  * @novar:  flag to set XML_XPATH_NOVAR
287  *
288  * Add an step to an XSLT Compiled Match
289  *
290  * Returns -1 in case of failure, 0 otherwise.
291  */
292 static int
xsltCompMatchAdd(xsltParserContextPtr ctxt,xsltCompMatchPtr comp,xsltOp op,xmlChar * value,xmlChar * value2,int novar)293 xsltCompMatchAdd(xsltParserContextPtr ctxt, xsltCompMatchPtr comp,
294                  xsltOp op, xmlChar * value, xmlChar * value2, int novar)
295 {
296     if (comp->nbStep >= comp->maxStep) {
297         xsltStepOpPtr tmp;
298 
299 	tmp = (xsltStepOpPtr) xmlRealloc(comp->steps, comp->maxStep * 2 *
300 	                                 sizeof(xsltStepOp));
301 	if (tmp == NULL) {
302 	    xsltGenericError(xsltGenericErrorContext,
303 	     "xsltCompMatchAdd: memory re-allocation failure.\n");
304 	    if (ctxt->style != NULL)
305 		ctxt->style->errors++;
306 	    return (-1);
307 	}
308         comp->maxStep *= 2;
309 	comp->steps = tmp;
310     }
311     comp->steps[comp->nbStep].op = op;
312     comp->steps[comp->nbStep].value = value;
313     comp->steps[comp->nbStep].value2 = value2;
314     comp->steps[comp->nbStep].value3 = NULL;
315     comp->steps[comp->nbStep].comp = NULL;
316     if (ctxt->ctxt != NULL) {
317 	comp->steps[comp->nbStep].previousExtra =
318 	    xsltAllocateExtraCtxt(ctxt->ctxt);
319 	comp->steps[comp->nbStep].indexExtra =
320 	    xsltAllocateExtraCtxt(ctxt->ctxt);
321 	comp->steps[comp->nbStep].lenExtra =
322 	    xsltAllocateExtraCtxt(ctxt->ctxt);
323     } else {
324 	comp->steps[comp->nbStep].previousExtra =
325 	    xsltAllocateExtra(ctxt->style);
326 	comp->steps[comp->nbStep].indexExtra =
327 	    xsltAllocateExtra(ctxt->style);
328 	comp->steps[comp->nbStep].lenExtra =
329 	    xsltAllocateExtra(ctxt->style);
330     }
331     if (op == XSLT_OP_PREDICATE) {
332 	xmlXPathContextPtr xctxt;
333 
334 	if (ctxt->style != NULL)
335 	    xctxt = xmlXPathNewContext(ctxt->style->doc);
336 	else
337 	    xctxt = xmlXPathNewContext(NULL);
338 #ifdef XML_XPATH_NOVAR
339 	if (novar != 0)
340 	    xctxt->flags = XML_XPATH_NOVAR;
341 #endif
342 	if (ctxt->style != NULL)
343 	    xctxt->dict = ctxt->style->dict;
344 	comp->steps[comp->nbStep].comp = xmlXPathCtxtCompile(xctxt, value);
345 	xmlXPathFreeContext(xctxt);
346 	if (comp->steps[comp->nbStep].comp == NULL) {
347 	    xsltTransformError(NULL, ctxt->style, ctxt->elem,
348 		    "Failed to compile predicate\n");
349 	    if (ctxt->style != NULL)
350 		ctxt->style->errors++;
351 	}
352     }
353     comp->nbStep++;
354     return (0);
355 }
356 
357 /**
358  * xsltSwapTopCompMatch:
359  * @comp:  the compiled match expression
360  *
361  * reverse the two top steps.
362  */
363 static void
xsltSwapTopCompMatch(xsltCompMatchPtr comp)364 xsltSwapTopCompMatch(xsltCompMatchPtr comp) {
365     int i;
366     int j = comp->nbStep - 1;
367 
368     if (j > 0) {
369 	register xmlChar *tmp;
370 	register xsltOp op;
371 	register xmlXPathCompExprPtr expr;
372 	register int t;
373 	i = j - 1;
374 	tmp = comp->steps[i].value;
375 	comp->steps[i].value = comp->steps[j].value;
376 	comp->steps[j].value = tmp;
377 	tmp = comp->steps[i].value2;
378 	comp->steps[i].value2 = comp->steps[j].value2;
379 	comp->steps[j].value2 = tmp;
380 	tmp = comp->steps[i].value3;
381 	comp->steps[i].value3 = comp->steps[j].value3;
382 	comp->steps[j].value3 = tmp;
383 	op = comp->steps[i].op;
384 	comp->steps[i].op = comp->steps[j].op;
385 	comp->steps[j].op = op;
386 	expr = comp->steps[i].comp;
387 	comp->steps[i].comp = comp->steps[j].comp;
388 	comp->steps[j].comp = expr;
389 	t = comp->steps[i].previousExtra;
390 	comp->steps[i].previousExtra = comp->steps[j].previousExtra;
391 	comp->steps[j].previousExtra = t;
392 	t = comp->steps[i].indexExtra;
393 	comp->steps[i].indexExtra = comp->steps[j].indexExtra;
394 	comp->steps[j].indexExtra = t;
395 	t = comp->steps[i].lenExtra;
396 	comp->steps[i].lenExtra = comp->steps[j].lenExtra;
397 	comp->steps[j].lenExtra = t;
398     }
399 }
400 
401 /**
402  * xsltReverseCompMatch:
403  * @ctxt: the parser context
404  * @comp:  the compiled match expression
405  *
406  * reverse all the stack of expressions
407  */
408 static void
xsltReverseCompMatch(xsltParserContextPtr ctxt,xsltCompMatchPtr comp)409 xsltReverseCompMatch(xsltParserContextPtr ctxt, xsltCompMatchPtr comp) {
410     int i = 0;
411     int j = comp->nbStep - 1;
412 
413     while (j > i) {
414 	register xmlChar *tmp;
415 	register xsltOp op;
416 	register xmlXPathCompExprPtr expr;
417 	register int t;
418 
419 	tmp = comp->steps[i].value;
420 	comp->steps[i].value = comp->steps[j].value;
421 	comp->steps[j].value = tmp;
422 	tmp = comp->steps[i].value2;
423 	comp->steps[i].value2 = comp->steps[j].value2;
424 	comp->steps[j].value2 = tmp;
425 	tmp = comp->steps[i].value3;
426 	comp->steps[i].value3 = comp->steps[j].value3;
427 	comp->steps[j].value3 = tmp;
428 	op = comp->steps[i].op;
429 	comp->steps[i].op = comp->steps[j].op;
430 	comp->steps[j].op = op;
431 	expr = comp->steps[i].comp;
432 	comp->steps[i].comp = comp->steps[j].comp;
433 	comp->steps[j].comp = expr;
434 	t = comp->steps[i].previousExtra;
435 	comp->steps[i].previousExtra = comp->steps[j].previousExtra;
436 	comp->steps[j].previousExtra = t;
437 	t = comp->steps[i].indexExtra;
438 	comp->steps[i].indexExtra = comp->steps[j].indexExtra;
439 	comp->steps[j].indexExtra = t;
440 	t = comp->steps[i].lenExtra;
441 	comp->steps[i].lenExtra = comp->steps[j].lenExtra;
442 	comp->steps[j].lenExtra = t;
443 	j--;
444 	i++;
445     }
446     xsltCompMatchAdd(ctxt, comp, XSLT_OP_END, NULL, NULL, 0);
447 
448     /*
449      * detect consecutive XSLT_OP_PREDICATE indicating a direct
450      * matching should be done.
451      */
452     for (i = 0;i < comp->nbStep - 1;i++) {
453         if ((comp->steps[i].op == XSLT_OP_PREDICATE) &&
454 	    (comp->steps[i + 1].op == XSLT_OP_PREDICATE)) {
455 
456 	    comp->direct = 1;
457 	    if (comp->pattern[0] != '/') {
458 		xmlChar *query;
459 
460 		query = xmlStrdup((const xmlChar *)"//");
461 		query = xmlStrcat(query, comp->pattern);
462 
463 		xmlFree((xmlChar *) comp->pattern);
464 		comp->pattern = query;
465 	    }
466 	    break;
467 	}
468     }
469 }
470 
471 /************************************************************************
472  * 									*
473  * 		The interpreter for the precompiled patterns		*
474  * 									*
475  ************************************************************************/
476 
477 static int
xsltPatPushState(xsltTransformContextPtr ctxt,xsltStepStates * states,int step,xmlNodePtr node)478 xsltPatPushState(xsltTransformContextPtr ctxt, xsltStepStates *states,
479                  int step, xmlNodePtr node) {
480     if ((states->states == NULL) || (states->maxstates <= 0)) {
481         states->maxstates = 4;
482 	states->nbstates = 0;
483 	states->states = xmlMalloc(4 * sizeof(xsltStepState));
484     }
485     else if (states->maxstates <= states->nbstates) {
486         xsltStepState *tmp;
487 
488 	tmp = (xsltStepStatePtr) xmlRealloc(states->states,
489 			       2 * states->maxstates * sizeof(xsltStepState));
490 	if (tmp == NULL) {
491 	    xsltGenericError(xsltGenericErrorContext,
492 	     "xsltPatPushState: memory re-allocation failure.\n");
493 	    ctxt->state = XSLT_STATE_STOPPED;
494 	    return(-1);
495 	}
496 	states->states = tmp;
497 	states->maxstates *= 2;
498     }
499     states->states[states->nbstates].step = step;
500     states->states[states->nbstates++].node = node;
501 #if 0
502     fprintf(stderr, "Push: %d, %s\n", step, node->name);
503 #endif
504     return(0);
505 }
506 
507 /**
508  * xsltTestCompMatchDirect:
509  * @ctxt:  a XSLT process context
510  * @comp: the precompiled pattern
511  * @node: a node
512  * @nsList: the namespaces in scope
513  * @nsNr: the number of namespaces in scope
514  *
515  * Test whether the node matches the pattern, do a direct evalutation
516  * and not a step by step evaluation.
517  *
518  * Returns 1 if it matches, 0 if it doesn't and -1 in case of failure
519  */
520 static int
xsltTestCompMatchDirect(xsltTransformContextPtr ctxt,xsltCompMatchPtr comp,xmlNodePtr node,xmlNsPtr * nsList,int nsNr)521 xsltTestCompMatchDirect(xsltTransformContextPtr ctxt, xsltCompMatchPtr comp,
522 	                xmlNodePtr node, xmlNsPtr *nsList, int nsNr) {
523     xsltStepOpPtr sel = NULL;
524     xmlDocPtr prevdoc;
525     xmlDocPtr doc;
526     xmlXPathObjectPtr list;
527     int ix, j;
528     int nocache = 0;
529     int isRVT;
530 
531     doc = node->doc;
532     if (XSLT_IS_RES_TREE_FRAG(doc))
533 	isRVT = 1;
534     else
535 	isRVT = 0;
536     sel = &comp->steps[0]; /* store extra in first step arbitrarily */
537 
538     prevdoc = (xmlDocPtr)
539 	XSLT_RUNTIME_EXTRA(ctxt, sel->previousExtra, ptr);
540     ix = XSLT_RUNTIME_EXTRA(ctxt, sel->indexExtra, ival);
541     list = (xmlXPathObjectPtr)
542 	XSLT_RUNTIME_EXTRA_LST(ctxt, sel->lenExtra);
543 
544     if ((list == NULL) || (prevdoc != doc)) {
545 	xmlXPathObjectPtr newlist;
546 	xmlNodePtr parent = node->parent;
547 	xmlDocPtr olddoc;
548 	xmlNodePtr oldnode;
549 	int oldNsNr;
550 	xmlNsPtr *oldNamespaces;
551 
552 	oldnode = ctxt->xpathCtxt->node;
553 	olddoc = ctxt->xpathCtxt->doc;
554 	oldNsNr = ctxt->xpathCtxt->nsNr;
555 	oldNamespaces = ctxt->xpathCtxt->namespaces;
556 	ctxt->xpathCtxt->node = node;
557 	ctxt->xpathCtxt->doc = doc;
558 	ctxt->xpathCtxt->namespaces = nsList;
559 	ctxt->xpathCtxt->nsNr = nsNr;
560 	newlist = xmlXPathEval(comp->pattern, ctxt->xpathCtxt);
561 	ctxt->xpathCtxt->node = oldnode;
562 	ctxt->xpathCtxt->doc = olddoc;
563 	ctxt->xpathCtxt->namespaces = oldNamespaces;
564 	ctxt->xpathCtxt->nsNr = oldNsNr;
565 	if (newlist == NULL)
566 	    return(-1);
567 	if (newlist->type != XPATH_NODESET) {
568 	    xmlXPathFreeObject(newlist);
569 	    return(-1);
570 	}
571 	ix = 0;
572 
573 	if ((parent == NULL) || (node->doc == NULL) || isRVT)
574 	    nocache = 1;
575 
576 	if (nocache == 0) {
577 	    if (list != NULL)
578 		xmlXPathFreeObject(list);
579 	    list = newlist;
580 
581 	    XSLT_RUNTIME_EXTRA_LST(ctxt, sel->lenExtra) =
582 		(void *) list;
583 	    XSLT_RUNTIME_EXTRA(ctxt, sel->previousExtra, ptr) =
584 		(void *) doc;
585 	    XSLT_RUNTIME_EXTRA(ctxt, sel->indexExtra, ival) =
586 		0;
587 	    XSLT_RUNTIME_EXTRA_FREE(ctxt, sel->lenExtra) =
588 		(xmlFreeFunc) xmlXPathFreeObject;
589 	} else
590 	    list = newlist;
591     }
592     if ((list->nodesetval == NULL) ||
593 	(list->nodesetval->nodeNr <= 0)) {
594 	if (nocache == 1)
595 	    xmlXPathFreeObject(list);
596 	return(0);
597     }
598     /* TODO: store the index and use it for the scan */
599     if (ix == 0) {
600 	for (j = 0;j < list->nodesetval->nodeNr;j++) {
601 	    if (list->nodesetval->nodeTab[j] == node) {
602 		if (nocache == 1)
603 		    xmlXPathFreeObject(list);
604 		return(1);
605 	    }
606 	}
607     } else {
608     }
609     if (nocache == 1)
610 	xmlXPathFreeObject(list);
611     return(0);
612 }
613 
614 /**
615  * xsltTestCompMatch:
616  * @ctxt:  a XSLT process context
617  * @comp: the precompiled pattern
618  * @node: a node
619  * @mode:  the mode name or NULL
620  * @modeURI:  the mode URI or NULL
621  *
622  * Test whether the node matches the pattern
623  *
624  * Returns 1 if it matches, 0 if it doesn't and -1 in case of failure
625  */
626 static int
xsltTestCompMatch(xsltTransformContextPtr ctxt,xsltCompMatchPtr comp,xmlNodePtr node,const xmlChar * mode,const xmlChar * modeURI)627 xsltTestCompMatch(xsltTransformContextPtr ctxt, xsltCompMatchPtr comp,
628 	          xmlNodePtr node, const xmlChar *mode,
629 		  const xmlChar *modeURI) {
630     int i;
631     xsltStepOpPtr step, sel = NULL;
632     xsltStepStates states = {0, 0, NULL}; /* // may require backtrack */
633 
634     if ((comp == NULL) || (node == NULL) || (ctxt == NULL)) {
635 	xsltTransformError(ctxt, NULL, node,
636 		"xsltTestCompMatch: null arg\n");
637         return(-1);
638     }
639     if (mode != NULL) {
640 	if (comp->mode == NULL)
641 	    return(0);
642 	/*
643 	 * both mode strings must be interned on the stylesheet dictionary
644 	 */
645 	if (comp->mode != mode)
646 	    return(0);
647     } else {
648 	if (comp->mode != NULL)
649 	    return(0);
650     }
651     if (modeURI != NULL) {
652 	if (comp->modeURI == NULL)
653 	    return(0);
654 	/*
655 	 * both modeURI strings must be interned on the stylesheet dictionary
656 	 */
657 	if (comp->modeURI != modeURI)
658 	    return(0);
659     } else {
660 	if (comp->modeURI != NULL)
661 	    return(0);
662     }
663 
664     i = 0;
665 restart:
666     for (;i < comp->nbStep;i++) {
667 	step = &comp->steps[i];
668 	if (step->op != XSLT_OP_PREDICATE)
669 	    sel = step;
670 	switch (step->op) {
671             case XSLT_OP_END:
672 		goto found;
673             case XSLT_OP_ROOT:
674 		if ((node->type == XML_DOCUMENT_NODE) ||
675 #ifdef LIBXML_DOCB_ENABLED
676 		    (node->type == XML_DOCB_DOCUMENT_NODE) ||
677 #endif
678 		    (node->type == XML_HTML_DOCUMENT_NODE))
679 		    continue;
680 		if ((node->type == XML_ELEMENT_NODE) && (node->name[0] == ' '))
681 		    continue;
682 		goto rollback;
683             case XSLT_OP_ELEM:
684 		if (node->type != XML_ELEMENT_NODE)
685 		    goto rollback;
686 		if (step->value == NULL)
687 		    continue;
688 		if (step->value[0] != node->name[0])
689 		    goto rollback;
690 		if (!xmlStrEqual(step->value, node->name))
691 		    goto rollback;
692 
693 		/* Namespace test */
694 		if (node->ns == NULL) {
695 		    if (step->value2 != NULL)
696 			goto rollback;
697 		} else if (node->ns->href != NULL) {
698 		    if (step->value2 == NULL)
699 			goto rollback;
700 		    if (!xmlStrEqual(step->value2, node->ns->href))
701 			goto rollback;
702 		}
703 		continue;
704             case XSLT_OP_ATTR:
705 		if (node->type != XML_ATTRIBUTE_NODE)
706 		    goto rollback;
707 		if (step->value != NULL) {
708 		    if (step->value[0] != node->name[0])
709 			goto rollback;
710 		    if (!xmlStrEqual(step->value, node->name))
711 			goto rollback;
712 		}
713 		/* Namespace test */
714 		if (node->ns == NULL) {
715 		    if (step->value2 != NULL)
716 			goto rollback;
717 		} else if (step->value2 != NULL) {
718 		    if (!xmlStrEqual(step->value2, node->ns->href))
719 			goto rollback;
720 		}
721 		continue;
722             case XSLT_OP_PARENT:
723 		if ((node->type == XML_DOCUMENT_NODE) ||
724 		    (node->type == XML_HTML_DOCUMENT_NODE) ||
725 #ifdef LIBXML_DOCB_ENABLED
726 		    (node->type == XML_DOCB_DOCUMENT_NODE) ||
727 #endif
728 		    (node->type == XML_NAMESPACE_DECL))
729 		    goto rollback;
730 		node = node->parent;
731 		if (node == NULL)
732 		    goto rollback;
733 		if (step->value == NULL)
734 		    continue;
735 		if (step->value[0] != node->name[0])
736 		    goto rollback;
737 		if (!xmlStrEqual(step->value, node->name))
738 		    goto rollback;
739 		/* Namespace test */
740 		if (node->ns == NULL) {
741 		    if (step->value2 != NULL)
742 			goto rollback;
743 		} else if (node->ns->href != NULL) {
744 		    if (step->value2 == NULL)
745 			goto rollback;
746 		    if (!xmlStrEqual(step->value2, node->ns->href))
747 			goto rollback;
748 		}
749 		continue;
750             case XSLT_OP_ANCESTOR:
751 		/* TODO: implement coalescing of ANCESTOR/NODE ops */
752 		if (step->value == NULL) {
753 		    step = &comp->steps[i+1];
754 		    if (step->op == XSLT_OP_ROOT)
755 			goto found;
756 		    /* added NS, ID and KEY as a result of bug 168208 */
757 		    if ((step->op != XSLT_OP_ELEM) &&
758 			(step->op != XSLT_OP_ALL) &&
759 			(step->op != XSLT_OP_NS) &&
760 			(step->op != XSLT_OP_ID) &&
761 			(step->op != XSLT_OP_KEY))
762 			goto rollback;
763 		}
764 		if (node == NULL)
765 		    goto rollback;
766 		if ((node->type == XML_DOCUMENT_NODE) ||
767 		    (node->type == XML_HTML_DOCUMENT_NODE) ||
768 #ifdef LIBXML_DOCB_ENABLED
769 		    (node->type == XML_DOCB_DOCUMENT_NODE) ||
770 #endif
771 		    (node->type == XML_NAMESPACE_DECL))
772 		    goto rollback;
773 		node = node->parent;
774 		if ((step->op != XSLT_OP_ELEM) && step->op != XSLT_OP_ALL) {
775 		    xsltPatPushState(ctxt, &states, i, node);
776 		    continue;
777 		}
778 		i++;
779 		if (step->value == NULL) {
780 		    xsltPatPushState(ctxt, &states, i - 1, node);
781 		    continue;
782 		}
783 		while (node != NULL) {
784 		    if ((node->type == XML_ELEMENT_NODE) &&
785 			(step->value[0] == node->name[0]) &&
786 			(xmlStrEqual(step->value, node->name))) {
787 			/* Namespace test */
788 			if (node->ns == NULL) {
789 			    if (step->value2 == NULL)
790 				break;
791 			} else if (node->ns->href != NULL) {
792 			    if ((step->value2 != NULL) &&
793 			        (xmlStrEqual(step->value2, node->ns->href)))
794 				break;
795 			}
796 		    }
797 		    node = node->parent;
798 		}
799 		if (node == NULL)
800 		    goto rollback;
801 		xsltPatPushState(ctxt, &states, i - 1, node);
802 		continue;
803             case XSLT_OP_ID: {
804 		/* TODO Handle IDs decently, must be done differently */
805 		xmlAttrPtr id;
806 
807 		if (node->type != XML_ELEMENT_NODE)
808 		    goto rollback;
809 
810 		id = xmlGetID(node->doc, step->value);
811 		if ((id == NULL) || (id->parent != node))
812 		    goto rollback;
813 		break;
814 	    }
815             case XSLT_OP_KEY: {
816 		xmlNodeSetPtr list;
817 		int indx;
818 
819 		list = xsltGetKey(ctxt, step->value,
820 			          step->value3, step->value2);
821 		if (list == NULL)
822 		    goto rollback;
823 		for (indx = 0;indx < list->nodeNr;indx++)
824 		    if (list->nodeTab[indx] == node)
825 			break;
826 		if (indx >= list->nodeNr)
827 		    goto rollback;
828 		break;
829 	    }
830             case XSLT_OP_NS:
831 		if (node->type != XML_ELEMENT_NODE)
832 		    goto rollback;
833 		if (node->ns == NULL) {
834 		    if (step->value != NULL)
835 			goto rollback;
836 		} else if (node->ns->href != NULL) {
837 		    if (step->value == NULL)
838 			goto rollback;
839 		    if (!xmlStrEqual(step->value, node->ns->href))
840 			goto rollback;
841 		}
842 		break;
843             case XSLT_OP_ALL:
844 		if (node->type != XML_ELEMENT_NODE)
845 		    goto rollback;
846 		break;
847 	    case XSLT_OP_PREDICATE: {
848 		xmlNodePtr oldNode;
849 		xmlDocPtr doc;
850 		int oldCS, oldCP;
851 		int pos = 0, len = 0;
852 		int isRVT;
853 
854 		/*
855 		 * when there is cascading XSLT_OP_PREDICATE, then use a
856 		 * direct computation approach. It's not done directly
857 		 * at the beginning of the routine to filter out as much
858 		 * as possible this costly computation.
859 		 */
860 		if (comp->direct) {
861 		    if (states.states != NULL) {
862 			/* Free the rollback states */
863 			xmlFree(states.states);
864 		    }
865 		    return(xsltTestCompMatchDirect(ctxt, comp, node,
866 		    				   comp->nsList, comp->nsNr));
867 		}
868 
869 		doc = node->doc;
870 		if (XSLT_IS_RES_TREE_FRAG(doc))
871 		    isRVT = 1;
872 		else
873 		    isRVT = 0;
874 
875 		/*
876 		 * Depending on the last selection, one may need to
877 		 * recompute contextSize and proximityPosition.
878 		 */
879 		oldCS = ctxt->xpathCtxt->contextSize;
880 		oldCP = ctxt->xpathCtxt->proximityPosition;
881 		if ((sel != NULL) &&
882 		    (sel->op == XSLT_OP_ELEM) &&
883 		    (sel->value != NULL) &&
884 		    (node->type == XML_ELEMENT_NODE) &&
885 		    (node->parent != NULL)) {
886 		    xmlNodePtr previous;
887 		    int ix, nocache = 0;
888 
889 		    previous = (xmlNodePtr)
890 			XSLT_RUNTIME_EXTRA(ctxt, sel->previousExtra, ptr);
891 		    ix = XSLT_RUNTIME_EXTRA(ctxt, sel->indexExtra, ival);
892 		    if ((previous != NULL) &&
893 			(previous->parent == node->parent)) {
894 			/*
895 			 * just walk back to adjust the index
896 			 */
897 			int indx = 0;
898 			xmlNodePtr sibling = node;
899 
900 			while (sibling != NULL) {
901 			    if (sibling == previous)
902 				break;
903 			    if ((previous->type == XML_ELEMENT_NODE) &&
904 				(previous->name != NULL) &&
905 				(sibling->name != NULL) &&
906 				(previous->name[0] == sibling->name[0]) &&
907 				(xmlStrEqual(previous->name, sibling->name)))
908 			    {
909 				if ((sel->value2 == NULL) ||
910 				    ((sibling->ns != NULL) &&
911 				     (xmlStrEqual(sel->value2,
912 						  sibling->ns->href))))
913 				    indx++;
914 			    }
915 			    sibling = sibling->prev;
916 			}
917 			if (sibling == NULL) {
918 			    /* hum going backward in document order ... */
919 			    indx = 0;
920 			    sibling = node;
921 			    while (sibling != NULL) {
922 				if (sibling == previous)
923 				    break;
924 				if ((previous->type == XML_ELEMENT_NODE) &&
925 				    (previous->name != NULL) &&
926 				    (sibling->name != NULL) &&
927 				    (previous->name[0] == sibling->name[0]) &&
928 				    (xmlStrEqual(previous->name, sibling->name)))
929 				{
930 				    if ((sel->value2 == NULL) ||
931 					((sibling->ns != NULL) &&
932 					(xmlStrEqual(sel->value2,
933 					sibling->ns->href))))
934 				    {
935 					indx--;
936 				    }
937 				}
938 				sibling = sibling->next;
939 			    }
940 			}
941 			if (sibling != NULL) {
942 			    pos = ix + indx;
943 			    /*
944 			     * If the node is in a Value Tree we need to
945 			     * save len, but cannot cache the node!
946 			     * (bugs 153137 and 158840)
947 			     */
948 			    if (node->doc != NULL) {
949 				len = XSLT_RUNTIME_EXTRA(ctxt,
950 				        sel->lenExtra, ival);
951 				if (!isRVT) {
952 				    XSLT_RUNTIME_EXTRA(ctxt,
953 					sel->previousExtra, ptr) = node;
954 				    XSLT_RUNTIME_EXTRA(ctxt,
955 				        sel->indexExtra, ival) = pos;
956 				}
957 			    }
958 			    ix = pos;
959 			} else
960 			    pos = 0;
961 		    } else {
962 			/*
963 			 * recompute the index
964 			 */
965 			xmlNodePtr parent = node->parent;
966 			xmlNodePtr siblings = NULL;
967 
968                         if (parent) siblings = parent->children;
969 
970 			while (siblings != NULL) {
971 			    if (siblings->type == XML_ELEMENT_NODE) {
972 				if (siblings == node) {
973 				    len++;
974 				    pos = len;
975 				} else if ((node->name != NULL) &&
976 					   (siblings->name != NULL) &&
977 				    (node->name[0] == siblings->name[0]) &&
978 				    (xmlStrEqual(node->name, siblings->name))) {
979 				    if ((sel->value2 == NULL) ||
980 					((siblings->ns != NULL) &&
981 					 (xmlStrEqual(sel->value2,
982 						      siblings->ns->href))))
983 					len++;
984 				}
985 			    }
986 			    siblings = siblings->next;
987 			}
988 			if ((parent == NULL) || (node->doc == NULL))
989 			    nocache = 1;
990 			else {
991 			    while (parent->parent != NULL)
992 				parent = parent->parent;
993 			    if (((parent->type != XML_DOCUMENT_NODE) &&
994 				 (parent->type != XML_HTML_DOCUMENT_NODE)) ||
995 				 (parent != (xmlNodePtr) node->doc))
996 				nocache = 1;
997 			}
998 		    }
999 		    if (pos != 0) {
1000 			ctxt->xpathCtxt->contextSize = len;
1001 			ctxt->xpathCtxt->proximityPosition = pos;
1002 			/*
1003 			 * If the node is in a Value Tree we cannot
1004 			 * cache it !
1005 			 */
1006 			if ((!isRVT) && (node->doc != NULL) &&
1007 			    (nocache == 0)) {
1008 			    XSLT_RUNTIME_EXTRA(ctxt, sel->previousExtra, ptr) =
1009 				node;
1010 			    XSLT_RUNTIME_EXTRA(ctxt, sel->indexExtra, ival) =
1011 				pos;
1012 			    XSLT_RUNTIME_EXTRA(ctxt, sel->lenExtra, ival) =
1013 				len;
1014 			}
1015 		    }
1016 		} else if ((sel != NULL) && (sel->op == XSLT_OP_ALL) &&
1017 			   (node->type == XML_ELEMENT_NODE)) {
1018 		    xmlNodePtr previous;
1019 		    int ix, nocache = 0;
1020 
1021 		    previous = (xmlNodePtr)
1022 			XSLT_RUNTIME_EXTRA(ctxt, sel->previousExtra, ptr);
1023 		    ix = XSLT_RUNTIME_EXTRA(ctxt, sel->indexExtra, ival);
1024 		    if ((previous != NULL) &&
1025 			(previous->parent == node->parent)) {
1026 			/*
1027 			 * just walk back to adjust the index
1028 			 */
1029 			int indx = 0;
1030 			xmlNodePtr sibling = node;
1031 
1032 			while (sibling != NULL) {
1033 			    if (sibling == previous)
1034 				break;
1035 			    if (sibling->type == XML_ELEMENT_NODE)
1036 				indx++;
1037 			    sibling = sibling->prev;
1038 			}
1039 			if (sibling == NULL) {
1040 			    /* hum going backward in document order ... */
1041 			    indx = 0;
1042 			    sibling = node;
1043 			    while (sibling != NULL) {
1044 				if (sibling == previous)
1045 				    break;
1046 				if (sibling->type == XML_ELEMENT_NODE)
1047 				    indx--;
1048 				sibling = sibling->next;
1049 			    }
1050 			}
1051 			if (sibling != NULL) {
1052 			    pos = ix + indx;
1053 			    /*
1054 			     * If the node is in a Value Tree we cannot
1055 			     * cache it !
1056 			     */
1057 			    if ((node->doc != NULL) && !isRVT) {
1058 				len = XSLT_RUNTIME_EXTRA(ctxt,
1059 				        sel->lenExtra, ival);
1060 				XSLT_RUNTIME_EXTRA(ctxt,
1061 					sel->previousExtra, ptr) = node;
1062 				XSLT_RUNTIME_EXTRA(ctxt,
1063 					sel->indexExtra, ival) = pos;
1064 			    }
1065 			} else
1066 			    pos = 0;
1067 		    } else {
1068 			/*
1069 			 * recompute the index
1070 			 */
1071 			xmlNodePtr parent = node->parent;
1072 			xmlNodePtr siblings = NULL;
1073 
1074                         if (parent) siblings = parent->children;
1075 
1076 			while (siblings != NULL) {
1077 			    if (siblings->type == XML_ELEMENT_NODE) {
1078 				len++;
1079 				if (siblings == node) {
1080 				    pos = len;
1081 				}
1082 			    }
1083 			    siblings = siblings->next;
1084 			}
1085 			if ((parent == NULL) || (node->doc == NULL))
1086 			    nocache = 1;
1087 			else {
1088 			    while (parent->parent != NULL)
1089 				parent = parent->parent;
1090 			    if (((parent->type != XML_DOCUMENT_NODE) &&
1091 				 (parent->type != XML_HTML_DOCUMENT_NODE)) ||
1092 				 (parent != (xmlNodePtr) node->doc))
1093 				nocache = 1;
1094 			}
1095 		    }
1096 		    if (pos != 0) {
1097 			ctxt->xpathCtxt->contextSize = len;
1098 			ctxt->xpathCtxt->proximityPosition = pos;
1099 			/*
1100 			 * If the node is in a Value Tree we cannot
1101 			 * cache it !
1102 			 */
1103 			if ((node->doc != NULL) && (nocache == 0) && !isRVT) {
1104 			    XSLT_RUNTIME_EXTRA(ctxt, sel->previousExtra, ptr) =
1105 				node;
1106 			    XSLT_RUNTIME_EXTRA(ctxt, sel->indexExtra, ival) =
1107 				pos;
1108 			    XSLT_RUNTIME_EXTRA(ctxt, sel->lenExtra, ival) =
1109 				len;
1110 			}
1111 		    }
1112 		}
1113 		oldNode = ctxt->node;
1114 		ctxt->node = node;
1115 
1116 		if (step->value == NULL)
1117 		    goto wrong_index;
1118 		if (step->comp == NULL)
1119 		    goto wrong_index;
1120 
1121 		if (!xsltEvalXPathPredicate(ctxt, step->comp, comp->nsList,
1122 			                    comp->nsNr))
1123 		    goto wrong_index;
1124 
1125 		if (pos != 0) {
1126 		    ctxt->xpathCtxt->contextSize = oldCS;
1127 		    ctxt->xpathCtxt->proximityPosition = oldCP;
1128 		}
1129 		ctxt->node = oldNode;
1130 		break;
1131 wrong_index:
1132 		if (pos != 0) {
1133 		    ctxt->xpathCtxt->contextSize = oldCS;
1134 		    ctxt->xpathCtxt->proximityPosition = oldCP;
1135 		}
1136 		ctxt->node = oldNode;
1137 		goto rollback;
1138 	    }
1139             case XSLT_OP_PI:
1140 		if (node->type != XML_PI_NODE)
1141 		    goto rollback;
1142 		if (step->value != NULL) {
1143 		    if (!xmlStrEqual(step->value, node->name))
1144 			goto rollback;
1145 		}
1146 		break;
1147             case XSLT_OP_COMMENT:
1148 		if (node->type != XML_COMMENT_NODE)
1149 		    goto rollback;
1150 		break;
1151             case XSLT_OP_TEXT:
1152 		if ((node->type != XML_TEXT_NODE) &&
1153 		    (node->type != XML_CDATA_SECTION_NODE))
1154 		    goto rollback;
1155 		break;
1156             case XSLT_OP_NODE:
1157 		switch (node->type) {
1158 		    case XML_ELEMENT_NODE:
1159 		    case XML_CDATA_SECTION_NODE:
1160 		    case XML_PI_NODE:
1161 		    case XML_COMMENT_NODE:
1162 		    case XML_TEXT_NODE:
1163 			break;
1164 		    default:
1165 			goto rollback;
1166 		}
1167 		break;
1168 	}
1169     }
1170 found:
1171     if (states.states != NULL) {
1172         /* Free the rollback states */
1173 	xmlFree(states.states);
1174     }
1175     return(1);
1176 rollback:
1177     /* got an error try to rollback */
1178     if (states.states == NULL)
1179 	return(0);
1180     if (states.nbstates <= 0) {
1181 	xmlFree(states.states);
1182 	return(0);
1183     }
1184     states.nbstates--;
1185     i = states.states[states.nbstates].step;
1186     node = states.states[states.nbstates].node;
1187 #if 0
1188     fprintf(stderr, "Pop: %d, %s\n", i, node->name);
1189 #endif
1190     goto restart;
1191 }
1192 
1193 /**
1194  * xsltTestCompMatchList:
1195  * @ctxt:  a XSLT process context
1196  * @node: a node
1197  * @comp: the precompiled pattern list
1198  *
1199  * Test whether the node matches one of the patterns in the list
1200  *
1201  * Returns 1 if it matches, 0 if it doesn't and -1 in case of failure
1202  */
1203 int
xsltTestCompMatchList(xsltTransformContextPtr ctxt,xmlNodePtr node,xsltCompMatchPtr comp)1204 xsltTestCompMatchList(xsltTransformContextPtr ctxt, xmlNodePtr node,
1205 	              xsltCompMatchPtr comp) {
1206     int ret;
1207 
1208     if ((ctxt == NULL) || (node == NULL))
1209 	return(-1);
1210     while (comp != NULL) {
1211 	ret = xsltTestCompMatch(ctxt, comp, node, NULL, NULL);
1212 	if (ret == 1)
1213 	    return(1);
1214 	comp = comp->next;
1215     }
1216     return(0);
1217 }
1218 
1219 /************************************************************************
1220  *									*
1221  *			Dedicated parser for templates			*
1222  *									*
1223  ************************************************************************/
1224 
1225 #define CUR (*ctxt->cur)
1226 #define SKIP(val) ctxt->cur += (val)
1227 #define NXT(val) ctxt->cur[(val)]
1228 #define CUR_PTR ctxt->cur
1229 
1230 #define SKIP_BLANKS 							\
1231     while (IS_BLANK_CH(CUR)) NEXT
1232 
1233 #define CURRENT (*ctxt->cur)
1234 #define NEXT ((*ctxt->cur) ?  ctxt->cur++: ctxt->cur)
1235 
1236 
1237 #define PUSH(op, val, val2, novar) 						\
1238     if (xsltCompMatchAdd(ctxt, ctxt->comp, (op), (val), (val2), (novar))) goto error;
1239 
1240 #define SWAP() 						\
1241     xsltSwapTopCompMatch(ctxt->comp);
1242 
1243 #define XSLT_ERROR(X)							\
1244     { xsltError(ctxt, __FILE__, __LINE__, X);			\
1245       ctxt->error = (X); return; }
1246 
1247 #define XSLT_ERROR0(X)							\
1248     { xsltError(ctxt, __FILE__, __LINE__, X);			\
1249       ctxt->error = (X); return(0); }
1250 
1251 /**
1252  * xsltScanLiteral:
1253  * @ctxt:  the XPath Parser context
1254  *
1255  * Parse an XPath Litteral:
1256  *
1257  * [29] Literal ::= '"' [^"]* '"'
1258  *                | "'" [^']* "'"
1259  *
1260  * Returns the Literal parsed or NULL
1261  */
1262 
1263 static xmlChar *
xsltScanLiteral(xsltParserContextPtr ctxt)1264 xsltScanLiteral(xsltParserContextPtr ctxt) {
1265     const xmlChar *q, *cur;
1266     xmlChar *ret = NULL;
1267     int val, len;
1268 
1269     SKIP_BLANKS;
1270     if (CUR == '"') {
1271         NEXT;
1272 	cur = q = CUR_PTR;
1273 	val = xmlStringCurrentChar(NULL, cur, &len);
1274 	while ((IS_CHAR(val)) && (val != '"')) {
1275 	    cur += len;
1276 	    val = xmlStringCurrentChar(NULL, cur, &len);
1277 	}
1278 	if (!IS_CHAR(val)) {
1279 	    ctxt->error = 1;
1280 	    return(NULL);
1281 	} else {
1282 	    ret = xmlStrndup(q, cur - q);
1283         }
1284 	cur += len;
1285 	CUR_PTR = cur;
1286     } else if (CUR == '\'') {
1287         NEXT;
1288 	cur = q = CUR_PTR;
1289 	val = xmlStringCurrentChar(NULL, cur, &len);
1290 	while ((IS_CHAR(val)) && (val != '\'')) {
1291 	    cur += len;
1292 	    val = xmlStringCurrentChar(NULL, cur, &len);
1293 	}
1294 	if (!IS_CHAR(val)) {
1295 	    ctxt->error = 1;
1296 	    return(NULL);
1297 	} else {
1298 	    ret = xmlStrndup(q, cur - q);
1299         }
1300 	cur += len;
1301 	CUR_PTR = cur;
1302     } else {
1303 	/* XP_ERROR(XPATH_START_LITERAL_ERROR); */
1304 	ctxt->error = 1;
1305 	return(NULL);
1306     }
1307     return(ret);
1308 }
1309 
1310 /**
1311  * xsltScanNCName:
1312  * @ctxt:  the XPath Parser context
1313  *
1314  * Parses a non qualified name
1315  *
1316  * Returns the Name parsed or NULL
1317  */
1318 
1319 static xmlChar *
xsltScanNCName(xsltParserContextPtr ctxt)1320 xsltScanNCName(xsltParserContextPtr ctxt) {
1321     const xmlChar *q, *cur;
1322     xmlChar *ret = NULL;
1323     int val, len;
1324 
1325     SKIP_BLANKS;
1326 
1327     cur = q = CUR_PTR;
1328     val = xmlStringCurrentChar(NULL, cur, &len);
1329     if (!IS_LETTER(val) && (val != '_'))
1330 	return(NULL);
1331 
1332     while ((IS_LETTER(val)) || (IS_DIGIT(val)) ||
1333            (val == '.') || (val == '-') ||
1334 	   (val == '_') ||
1335 	   (IS_COMBINING(val)) ||
1336 	   (IS_EXTENDER(val))) {
1337 	cur += len;
1338 	val = xmlStringCurrentChar(NULL, cur, &len);
1339     }
1340     ret = xmlStrndup(q, cur - q);
1341     CUR_PTR = cur;
1342     return(ret);
1343 }
1344 
1345 /*
1346  * xsltCompileIdKeyPattern:
1347  * @ctxt:  the compilation context
1348  * @name:  a preparsed name
1349  * @aid:  whether id/key are allowed there
1350  * @novar:  flag to prohibit xslt var
1351  *
1352  * Compile the XSLT LocationIdKeyPattern
1353  * [3] IdKeyPattern ::= 'id' '(' Literal ')'
1354  *                    | 'key' '(' Literal ',' Literal ')'
1355  *
1356  * also handle NodeType and PI from:
1357  *
1358  * [7]  NodeTest ::= NameTest
1359  *                 | NodeType '(' ')'
1360  *                 | 'processing-instruction' '(' Literal ')'
1361  */
1362 static void
xsltCompileIdKeyPattern(xsltParserContextPtr ctxt,xmlChar * name,int aid,int novar,xsltAxis axis)1363 xsltCompileIdKeyPattern(xsltParserContextPtr ctxt, xmlChar *name,
1364 		int aid, int novar, xsltAxis axis) {
1365     xmlChar *lit = NULL;
1366     xmlChar *lit2 = NULL;
1367 
1368     if (CUR != '(') {
1369 	xsltTransformError(NULL, NULL, NULL,
1370 		"xsltCompileIdKeyPattern : ( expected\n");
1371 	ctxt->error = 1;
1372 	return;
1373     }
1374     if ((aid) && (xmlStrEqual(name, (const xmlChar *)"id"))) {
1375 	if (axis != 0) {
1376 	    xsltTransformError(NULL, NULL, NULL,
1377 		    "xsltCompileIdKeyPattern : NodeTest expected\n");
1378 	    ctxt->error = 1;
1379 	    return;
1380 	}
1381 	NEXT;
1382 	SKIP_BLANKS;
1383         lit = xsltScanLiteral(ctxt);
1384 	if (ctxt->error)
1385 	    return;
1386 	SKIP_BLANKS;
1387 	if (CUR != ')') {
1388 	    xsltTransformError(NULL, NULL, NULL,
1389 		    "xsltCompileIdKeyPattern : ) expected\n");
1390 	    ctxt->error = 1;
1391 	    return;
1392 	}
1393 	NEXT;
1394 	PUSH(XSLT_OP_ID, lit, NULL, novar);
1395     } else if ((aid) && (xmlStrEqual(name, (const xmlChar *)"key"))) {
1396 	if (axis != 0) {
1397 	    xsltTransformError(NULL, NULL, NULL,
1398 		    "xsltCompileIdKeyPattern : NodeTest expected\n");
1399 	    ctxt->error = 1;
1400 	    return;
1401 	}
1402 	NEXT;
1403 	SKIP_BLANKS;
1404         lit = xsltScanLiteral(ctxt);
1405 	if (ctxt->error)
1406 	    return;
1407 	SKIP_BLANKS;
1408 	if (CUR != ',') {
1409 	    xsltTransformError(NULL, NULL, NULL,
1410 		    "xsltCompileIdKeyPattern : , expected\n");
1411 	    ctxt->error = 1;
1412 	    return;
1413 	}
1414 	NEXT;
1415 	SKIP_BLANKS;
1416         lit2 = xsltScanLiteral(ctxt);
1417 	if (ctxt->error)
1418 	    return;
1419 	SKIP_BLANKS;
1420 	if (CUR != ')') {
1421 	    xsltTransformError(NULL, NULL, NULL,
1422 		    "xsltCompileIdKeyPattern : ) expected\n");
1423 	    ctxt->error = 1;
1424 	    return;
1425 	}
1426 	NEXT;
1427 	/* URGENT TODO: support namespace in keys */
1428 	PUSH(XSLT_OP_KEY, lit, lit2, novar);
1429     } else if (xmlStrEqual(name, (const xmlChar *)"processing-instruction")) {
1430 	NEXT;
1431 	SKIP_BLANKS;
1432 	if (CUR != ')') {
1433 	    lit = xsltScanLiteral(ctxt);
1434 	    if (ctxt->error)
1435 		return;
1436 	    SKIP_BLANKS;
1437 	    if (CUR != ')') {
1438 		xsltTransformError(NULL, NULL, NULL,
1439 			"xsltCompileIdKeyPattern : ) expected\n");
1440 		ctxt->error = 1;
1441 		return;
1442 	    }
1443 	}
1444 	NEXT;
1445 	PUSH(XSLT_OP_PI, lit, NULL, novar);
1446     } else if (xmlStrEqual(name, (const xmlChar *)"text")) {
1447 	NEXT;
1448 	SKIP_BLANKS;
1449 	if (CUR != ')') {
1450 	    xsltTransformError(NULL, NULL, NULL,
1451 		    "xsltCompileIdKeyPattern : ) expected\n");
1452 	    ctxt->error = 1;
1453 	    return;
1454 	}
1455 	NEXT;
1456 	PUSH(XSLT_OP_TEXT, NULL, NULL, novar);
1457     } else if (xmlStrEqual(name, (const xmlChar *)"comment")) {
1458 	NEXT;
1459 	SKIP_BLANKS;
1460 	if (CUR != ')') {
1461 	    xsltTransformError(NULL, NULL, NULL,
1462 		    "xsltCompileIdKeyPattern : ) expected\n");
1463 	    ctxt->error = 1;
1464 	    return;
1465 	}
1466 	NEXT;
1467 	PUSH(XSLT_OP_COMMENT, NULL, NULL, novar);
1468     } else if (xmlStrEqual(name, (const xmlChar *)"node")) {
1469 	NEXT;
1470 	SKIP_BLANKS;
1471 	if (CUR != ')') {
1472 	    xsltTransformError(NULL, NULL, NULL,
1473 		    "xsltCompileIdKeyPattern : ) expected\n");
1474 	    ctxt->error = 1;
1475 	    return;
1476 	}
1477 	NEXT;
1478 	if (axis == AXIS_ATTRIBUTE) {
1479 	    PUSH(XSLT_OP_ATTR, NULL, NULL, novar);
1480 	}
1481 	else {
1482 	    PUSH(XSLT_OP_NODE, NULL, NULL, novar);
1483 	}
1484     } else if (aid) {
1485 	xsltTransformError(NULL, NULL, NULL,
1486 	    "xsltCompileIdKeyPattern : expecting 'key' or 'id' or node type\n");
1487 	ctxt->error = 1;
1488 	return;
1489     } else {
1490 	xsltTransformError(NULL, NULL, NULL,
1491 	    "xsltCompileIdKeyPattern : node type\n");
1492 	ctxt->error = 1;
1493 	return;
1494     }
1495 error:
1496     if (name != NULL)
1497 	xmlFree(name);
1498 }
1499 
1500 /**
1501  * xsltCompileStepPattern:
1502  * @ctxt:  the compilation context
1503  * @token:  a posible precompiled name
1504  * @novar: flag to prohibit xslt variables from pattern
1505  *
1506  * Compile the XSLT StepPattern and generates a precompiled
1507  * form suitable for fast matching.
1508  *
1509  * [5] StepPattern ::= ChildOrAttributeAxisSpecifier NodeTest Predicate*
1510  * [6] ChildOrAttributeAxisSpecifier ::= AbbreviatedAxisSpecifier
1511  *                                     | ('child' | 'attribute') '::'
1512  * from XPath
1513  * [7]  NodeTest ::= NameTest
1514  *                 | NodeType '(' ')'
1515  *                 | 'processing-instruction' '(' Literal ')'
1516  * [8] Predicate ::= '[' PredicateExpr ']'
1517  * [9] PredicateExpr ::= Expr
1518  * [13] AbbreviatedAxisSpecifier ::= '@'?
1519  * [37] NameTest ::= '*' | NCName ':' '*' | QName
1520  */
1521 
1522 static void
xsltCompileStepPattern(xsltParserContextPtr ctxt,xmlChar * token,int novar)1523 xsltCompileStepPattern(xsltParserContextPtr ctxt, xmlChar *token, int novar) {
1524     xmlChar *name = NULL;
1525     const xmlChar *URI = NULL;
1526     xmlChar *URL = NULL;
1527     int level;
1528     xsltAxis axis = 0;
1529 
1530     SKIP_BLANKS;
1531     if ((token == NULL) && (CUR == '@')) {
1532 	NEXT;
1533         axis = AXIS_ATTRIBUTE;
1534     }
1535 parse_node_test:
1536     if (token == NULL)
1537 	token = xsltScanNCName(ctxt);
1538     if (token == NULL) {
1539 	if (CUR == '*') {
1540 	    NEXT;
1541 	    if (axis == AXIS_ATTRIBUTE) {
1542                 PUSH(XSLT_OP_ATTR, NULL, NULL, novar);
1543             }
1544             else {
1545                 PUSH(XSLT_OP_ALL, NULL, NULL, novar);
1546             }
1547 	    goto parse_predicate;
1548 	} else {
1549 	    xsltTransformError(NULL, NULL, NULL,
1550 		    "xsltCompileStepPattern : Name expected\n");
1551 	    ctxt->error = 1;
1552 	    goto error;
1553 	}
1554     }
1555 
1556 
1557     SKIP_BLANKS;
1558     if (CUR == '(') {
1559 	xsltCompileIdKeyPattern(ctxt, token, 0, novar, axis);
1560 	if (ctxt->error)
1561 	    goto error;
1562     } else if (CUR == ':') {
1563 	NEXT;
1564 	if (CUR != ':') {
1565 	    xmlChar *prefix = token;
1566 	    xmlNsPtr ns;
1567 
1568 	    /*
1569 	     * This is a namespace match
1570 	     */
1571 	    token = xsltScanNCName(ctxt);
1572 	    ns = xmlSearchNs(ctxt->doc, ctxt->elem, prefix);
1573 	    if (ns == NULL) {
1574 		xsltTransformError(NULL, NULL, NULL,
1575 	    "xsltCompileStepPattern : no namespace bound to prefix %s\n",
1576 				 prefix);
1577 		xmlFree(prefix);
1578 		ctxt->error = 1;
1579 		goto error;
1580 	    } else {
1581 		URL = xmlStrdup(ns->href);
1582 	    }
1583 	    xmlFree(prefix);
1584 	    if (token == NULL) {
1585 		if (CUR == '*') {
1586 		    NEXT;
1587                     if (axis == AXIS_ATTRIBUTE) {
1588                         PUSH(XSLT_OP_ATTR, NULL, URL, novar);
1589                     }
1590                     else {
1591                         PUSH(XSLT_OP_NS, URL, NULL, novar);
1592                     }
1593 		} else {
1594 		    xsltTransformError(NULL, NULL, NULL,
1595 			    "xsltCompileStepPattern : Name expected\n");
1596 		    ctxt->error = 1;
1597 		    goto error;
1598 		}
1599 	    } else {
1600                 if (axis == AXIS_ATTRIBUTE) {
1601                     PUSH(XSLT_OP_ATTR, token, URL, novar);
1602                 }
1603                 else {
1604                     PUSH(XSLT_OP_ELEM, token, URL, novar);
1605                 }
1606 	    }
1607 	} else {
1608 	    if (axis != 0) {
1609 		xsltTransformError(NULL, NULL, NULL,
1610 		    "xsltCompileStepPattern : NodeTest expected\n");
1611 		ctxt->error = 1;
1612 		goto error;
1613 	    }
1614 	    NEXT;
1615 	    if (xmlStrEqual(token, (const xmlChar *) "child")) {
1616 	        axis = AXIS_CHILD;
1617 	    } else if (xmlStrEqual(token, (const xmlChar *) "attribute")) {
1618 	        axis = AXIS_ATTRIBUTE;
1619 	    } else {
1620 		xsltTransformError(NULL, NULL, NULL,
1621 		    "xsltCompileStepPattern : 'child' or 'attribute' expected\n");
1622 		ctxt->error = 1;
1623 		goto error;
1624 	    }
1625 	    xmlFree(token);
1626             SKIP_BLANKS;
1627             token = xsltScanNCName(ctxt);
1628 	    goto parse_node_test;
1629 	}
1630     } else {
1631 	URI = xsltGetQNameURI(ctxt->elem, &token);
1632 	if (token == NULL) {
1633 	    ctxt->error = 1;
1634 	    goto error;
1635 	}
1636 	if (URI != NULL)
1637 	    URL = xmlStrdup(URI);
1638         if (axis == AXIS_ATTRIBUTE) {
1639             PUSH(XSLT_OP_ATTR, token, URL, novar);
1640         }
1641         else {
1642             PUSH(XSLT_OP_ELEM, token, URL, novar);
1643         }
1644     }
1645 parse_predicate:
1646     SKIP_BLANKS;
1647     level = 0;
1648     while (CUR == '[') {
1649 	const xmlChar *q;
1650 	xmlChar *ret = NULL;
1651 
1652 	level++;
1653 	NEXT;
1654 	q = CUR_PTR;
1655 	while (CUR != 0) {
1656 	    /* Skip over nested predicates */
1657 	    if (CUR == '[')
1658 		level++;
1659 	    else if (CUR == ']') {
1660 		level--;
1661 		if (level == 0)
1662 		    break;
1663 	    } else if (CUR == '"') {
1664 		NEXT;
1665 		while ((CUR != 0) && (CUR != '"'))
1666 		    NEXT;
1667 	    } else if (CUR == '\'') {
1668 		NEXT;
1669 		while ((CUR != 0) && (CUR != '\''))
1670 		    NEXT;
1671 	    }
1672 	    NEXT;
1673 	}
1674 	if (CUR == 0) {
1675 	    xsltTransformError(NULL, NULL, NULL,
1676 		    "xsltCompileStepPattern : ']' expected\n");
1677 	    ctxt->error = 1;
1678 	    return;
1679         }
1680 	ret = xmlStrndup(q, CUR_PTR - q);
1681 	PUSH(XSLT_OP_PREDICATE, ret, NULL, novar);
1682 	/* push the predicate lower than local test */
1683 	SWAP();
1684 	NEXT;
1685 	SKIP_BLANKS;
1686     }
1687     return;
1688 error:
1689     if (token != NULL)
1690 	xmlFree(token);
1691     if (name != NULL)
1692 	xmlFree(name);
1693 }
1694 
1695 /**
1696  * xsltCompileRelativePathPattern:
1697  * @comp:  the compilation context
1698  * @token:  a posible precompiled name
1699  * @novar:  flag to prohibit xslt variables
1700  *
1701  * Compile the XSLT RelativePathPattern and generates a precompiled
1702  * form suitable for fast matching.
1703  *
1704  * [4] RelativePathPattern ::= StepPattern
1705  *                           | RelativePathPattern '/' StepPattern
1706  *                           | RelativePathPattern '//' StepPattern
1707  */
1708 static void
xsltCompileRelativePathPattern(xsltParserContextPtr ctxt,xmlChar * token,int novar)1709 xsltCompileRelativePathPattern(xsltParserContextPtr ctxt, xmlChar *token, int novar) {
1710     xsltCompileStepPattern(ctxt, token, novar);
1711     if (ctxt->error)
1712 	goto error;
1713     SKIP_BLANKS;
1714     while ((CUR != 0) && (CUR != '|')) {
1715 	if ((CUR == '/') && (NXT(1) == '/')) {
1716 	    PUSH(XSLT_OP_ANCESTOR, NULL, NULL, novar);
1717 	    NEXT;
1718 	    NEXT;
1719 	    SKIP_BLANKS;
1720 	    xsltCompileStepPattern(ctxt, NULL, novar);
1721 	} else if (CUR == '/') {
1722 	    PUSH(XSLT_OP_PARENT, NULL, NULL, novar);
1723 	    NEXT;
1724 	    SKIP_BLANKS;
1725 	    if ((CUR != 0) && (CUR != '|')) {
1726 		xsltCompileRelativePathPattern(ctxt, NULL, novar);
1727 	    }
1728 	} else {
1729 	    ctxt->error = 1;
1730 	}
1731 	if (ctxt->error)
1732 	    goto error;
1733 	SKIP_BLANKS;
1734     }
1735 error:
1736     return;
1737 }
1738 
1739 /**
1740  * xsltCompileLocationPathPattern:
1741  * @ctxt:  the compilation context
1742  * @novar:  flag to prohibit xslt variables
1743  *
1744  * Compile the XSLT LocationPathPattern and generates a precompiled
1745  * form suitable for fast matching.
1746  *
1747  * [2] LocationPathPattern ::= '/' RelativePathPattern?
1748  *                           | IdKeyPattern (('/' | '//') RelativePathPattern)?
1749  *                           | '//'? RelativePathPattern
1750  */
1751 static void
xsltCompileLocationPathPattern(xsltParserContextPtr ctxt,int novar)1752 xsltCompileLocationPathPattern(xsltParserContextPtr ctxt, int novar) {
1753     SKIP_BLANKS;
1754     if ((CUR == '/') && (NXT(1) == '/')) {
1755 	/*
1756 	 * since we reverse the query
1757 	 * a leading // can be safely ignored
1758 	 */
1759 	NEXT;
1760 	NEXT;
1761 	ctxt->comp->priority = 0.5;	/* '//' means not 0 priority */
1762 	xsltCompileRelativePathPattern(ctxt, NULL, novar);
1763     } else if (CUR == '/') {
1764 	/*
1765 	 * We need to find root as the parent
1766 	 */
1767 	NEXT;
1768 	SKIP_BLANKS;
1769 	PUSH(XSLT_OP_ROOT, NULL, NULL, novar);
1770 	if ((CUR != 0) && (CUR != '|')) {
1771 	    PUSH(XSLT_OP_PARENT, NULL, NULL, novar);
1772 	    xsltCompileRelativePathPattern(ctxt, NULL, novar);
1773 	}
1774     } else if (CUR == '*') {
1775 	xsltCompileRelativePathPattern(ctxt, NULL, novar);
1776     } else if (CUR == '@') {
1777 	xsltCompileRelativePathPattern(ctxt, NULL, novar);
1778     } else {
1779 	xmlChar *name;
1780 	name = xsltScanNCName(ctxt);
1781 	if (name == NULL) {
1782 	    xsltTransformError(NULL, NULL, NULL,
1783 		    "xsltCompileLocationPathPattern : Name expected\n");
1784 	    ctxt->error = 1;
1785 	    return;
1786 	}
1787 	SKIP_BLANKS;
1788 	if ((CUR == '(') && !xmlXPathIsNodeType(name)) {
1789 	    xsltCompileIdKeyPattern(ctxt, name, 1, novar, 0);
1790 	    if (ctxt->error)
1791 		return;
1792 	    if ((CUR == '/') && (NXT(1) == '/')) {
1793 		PUSH(XSLT_OP_ANCESTOR, NULL, NULL, novar);
1794 		NEXT;
1795 		NEXT;
1796 		SKIP_BLANKS;
1797 		xsltCompileRelativePathPattern(ctxt, NULL, novar);
1798 	    } else if (CUR == '/') {
1799 		PUSH(XSLT_OP_PARENT, NULL, NULL, novar);
1800 		NEXT;
1801 		SKIP_BLANKS;
1802 		xsltCompileRelativePathPattern(ctxt, NULL, novar);
1803 	    }
1804 	    return;
1805 	}
1806 	xsltCompileRelativePathPattern(ctxt, name, novar);
1807     }
1808 error:
1809     return;
1810 }
1811 
1812 /**
1813  * xsltCompilePatternInternal:
1814  * @pattern: an XSLT pattern
1815  * @doc:  the containing document
1816  * @node:  the containing element
1817  * @style:  the stylesheet
1818  * @runtime:  the transformation context, if done at run-time
1819  * @novar:  flag to prohibit xslt variables
1820  *
1821  * Compile the XSLT pattern and generates a list of precompiled form suitable
1822  * for fast matching.
1823  *
1824  * [1] Pattern ::= LocationPathPattern | Pattern '|' LocationPathPattern
1825  *
1826  * Returns the generated pattern list or NULL in case of failure
1827  */
1828 
1829 static xsltCompMatchPtr
xsltCompilePatternInternal(const xmlChar * pattern,xmlDocPtr doc,xmlNodePtr node,xsltStylesheetPtr style,xsltTransformContextPtr runtime,int novar)1830 xsltCompilePatternInternal(const xmlChar *pattern, xmlDocPtr doc,
1831 	           xmlNodePtr node, xsltStylesheetPtr style,
1832 		   xsltTransformContextPtr runtime, int novar) {
1833     xsltParserContextPtr ctxt = NULL;
1834     xsltCompMatchPtr element, first = NULL, previous = NULL;
1835     int current, start, end, level, j;
1836 
1837     if (pattern == NULL) {
1838 	xsltTransformError(NULL, NULL, node,
1839 			 "xsltCompilePattern : NULL pattern\n");
1840 	return(NULL);
1841     }
1842 
1843     ctxt = xsltNewParserContext(style, runtime);
1844     if (ctxt == NULL)
1845 	return(NULL);
1846     ctxt->doc = doc;
1847     ctxt->elem = node;
1848     current = end = 0;
1849     while (pattern[current] != 0) {
1850 	start = current;
1851 	while (IS_BLANK_CH(pattern[current]))
1852 	    current++;
1853 	end = current;
1854 	level = 0;
1855 	while ((pattern[end] != 0) && ((pattern[end] != '|') || (level != 0))) {
1856 	    if (pattern[end] == '[')
1857 		level++;
1858 	    else if (pattern[end] == ']')
1859 		level--;
1860 	    else if (pattern[end] == '\'') {
1861 		end++;
1862 		while ((pattern[end] != 0) && (pattern[end] != '\''))
1863 		    end++;
1864 	    } else if (pattern[end] == '"') {
1865 		end++;
1866 		while ((pattern[end] != 0) && (pattern[end] != '"'))
1867 		    end++;
1868 	    }
1869       if (pattern[end] == 0)
1870           break;
1871 	    end++;
1872 	}
1873 	if (current == end) {
1874 	    xsltTransformError(NULL, NULL, node,
1875 			     "xsltCompilePattern : NULL pattern\n");
1876 	    goto error;
1877 	}
1878 	element = xsltNewCompMatch();
1879 	if (element == NULL) {
1880 	    goto error;
1881 	}
1882 	if (first == NULL)
1883 	    first = element;
1884 	else if (previous != NULL)
1885 	    previous->next = element;
1886 	previous = element;
1887 
1888 	ctxt->comp = element;
1889 	ctxt->base = xmlStrndup(&pattern[start], end - start);
1890 	if (ctxt->base == NULL)
1891 	    goto error;
1892 	ctxt->cur = &(ctxt->base)[current - start];
1893 	element->pattern = ctxt->base;
1894 	element->nsList = xmlGetNsList(doc, node);
1895 	j = 0;
1896 	if (element->nsList != NULL) {
1897 	    while (element->nsList[j] != NULL)
1898 		j++;
1899 	}
1900 	element->nsNr = j;
1901 
1902 
1903 #ifdef WITH_XSLT_DEBUG_PATTERN
1904 	xsltGenericDebug(xsltGenericDebugContext,
1905 			 "xsltCompilePattern : parsing '%s'\n",
1906 			 element->pattern);
1907 #endif
1908 	/*
1909 	 Preset default priority to be zero.
1910 	 This may be changed by xsltCompileLocationPathPattern.
1911 	 */
1912 	element->priority = 0;
1913 	xsltCompileLocationPathPattern(ctxt, novar);
1914 	if (ctxt->error) {
1915 	    xsltTransformError(NULL, style, node,
1916 			     "xsltCompilePattern : failed to compile '%s'\n",
1917 			     element->pattern);
1918 	    if (style != NULL) style->errors++;
1919 	    goto error;
1920 	}
1921 
1922 	/*
1923 	 * Reverse for faster interpretation.
1924 	 */
1925 	xsltReverseCompMatch(ctxt, element);
1926 
1927 	/*
1928 	 * Set-up the priority
1929 	 */
1930 	if (element->priority == 0) {	/* if not yet determined */
1931 	    if (((element->steps[0].op == XSLT_OP_ELEM) ||
1932 		 (element->steps[0].op == XSLT_OP_ATTR) ||
1933 		 (element->steps[0].op == XSLT_OP_PI)) &&
1934 		(element->steps[0].value != NULL) &&
1935 		(element->steps[1].op == XSLT_OP_END)) {
1936 		;	/* previously preset */
1937 	    } else if ((element->steps[0].op == XSLT_OP_ATTR) &&
1938 		       (element->steps[0].value2 != NULL) &&
1939 		       (element->steps[1].op == XSLT_OP_END)) {
1940 			element->priority = -0.25;
1941 	    } else if ((element->steps[0].op == XSLT_OP_NS) &&
1942 		       (element->steps[0].value != NULL) &&
1943 		       (element->steps[1].op == XSLT_OP_END)) {
1944 			element->priority = -0.25;
1945 	    } else if ((element->steps[0].op == XSLT_OP_ATTR) &&
1946 		       (element->steps[0].value == NULL) &&
1947 		       (element->steps[0].value2 == NULL) &&
1948 		       (element->steps[1].op == XSLT_OP_END)) {
1949 			element->priority = -0.5;
1950 	    } else if (((element->steps[0].op == XSLT_OP_PI) ||
1951 		       (element->steps[0].op == XSLT_OP_TEXT) ||
1952 		       (element->steps[0].op == XSLT_OP_ALL) ||
1953 		       (element->steps[0].op == XSLT_OP_NODE) ||
1954 		       (element->steps[0].op == XSLT_OP_COMMENT)) &&
1955 		       (element->steps[1].op == XSLT_OP_END)) {
1956 			element->priority = -0.5;
1957 	    } else {
1958 		element->priority = 0.5;
1959 	    }
1960 	}
1961 #ifdef WITH_XSLT_DEBUG_PATTERN
1962 	xsltGenericDebug(xsltGenericDebugContext,
1963 		     "xsltCompilePattern : parsed %s, default priority %f\n",
1964 			 element->pattern, element->priority);
1965 #endif
1966 	if (pattern[end] == '|')
1967 	    end++;
1968 	current = end;
1969     }
1970     if (end == 0) {
1971 	xsltTransformError(NULL, style, node,
1972 			 "xsltCompilePattern : NULL pattern\n");
1973 	if (style != NULL) style->errors++;
1974 	goto error;
1975     }
1976 
1977     xsltFreeParserContext(ctxt);
1978     return(first);
1979 
1980 error:
1981     if (ctxt != NULL)
1982 	xsltFreeParserContext(ctxt);
1983     if (first != NULL)
1984 	xsltFreeCompMatchList(first);
1985     return(NULL);
1986 }
1987 
1988 /**
1989  * xsltCompilePattern:
1990  * @pattern: an XSLT pattern
1991  * @doc:  the containing document
1992  * @node:  the containing element
1993  * @style:  the stylesheet
1994  * @runtime:  the transformation context, if done at run-time
1995  *
1996  * Compile the XSLT pattern and generates a list of precompiled form suitable
1997  * for fast matching.
1998  *
1999  * [1] Pattern ::= LocationPathPattern | Pattern '|' LocationPathPattern
2000  *
2001  * Returns the generated pattern list or NULL in case of failure
2002  */
2003 
2004 xsltCompMatchPtr
xsltCompilePattern(const xmlChar * pattern,xmlDocPtr doc,xmlNodePtr node,xsltStylesheetPtr style,xsltTransformContextPtr runtime)2005 xsltCompilePattern(const xmlChar *pattern, xmlDocPtr doc,
2006 	           xmlNodePtr node, xsltStylesheetPtr style,
2007 		   xsltTransformContextPtr runtime) {
2008     return (xsltCompilePatternInternal(pattern, doc, node, style, runtime, 0));
2009 }
2010 
2011 /************************************************************************
2012  *									*
2013  *			Module interfaces				*
2014  *									*
2015  ************************************************************************/
2016 
2017 /**
2018  * xsltAddTemplate:
2019  * @style: an XSLT stylesheet
2020  * @cur: an XSLT template
2021  * @mode:  the mode name or NULL
2022  * @modeURI:  the mode URI or NULL
2023  *
2024  * Register the XSLT pattern associated to @cur
2025  *
2026  * Returns -1 in case of error, 0 otherwise
2027  */
2028 int
xsltAddTemplate(xsltStylesheetPtr style,xsltTemplatePtr cur,const xmlChar * mode,const xmlChar * modeURI)2029 xsltAddTemplate(xsltStylesheetPtr style, xsltTemplatePtr cur,
2030 	        const xmlChar *mode, const xmlChar *modeURI) {
2031     xsltCompMatchPtr pat, list, next;
2032     /*
2033      * 'top' will point to style->xxxMatch ptr - declaring as 'void'
2034      *  avoids gcc 'type-punned pointer' warning.
2035      */
2036     void **top = NULL;
2037     const xmlChar *name = NULL;
2038     float priority;              /* the priority */
2039 
2040     if ((style == NULL) || (cur == NULL) || (cur->match == NULL))
2041 	return(-1);
2042 
2043     priority = cur->priority;
2044     pat = xsltCompilePatternInternal(cur->match, style->doc, cur->elem,
2045 		    style, NULL, 1);
2046     if (pat == NULL)
2047     	return(-1);
2048     while (pat) {
2049 	next = pat->next;
2050 	pat->next = NULL;
2051 	name = NULL;
2052 
2053 	pat->template = cur;
2054 	if (mode != NULL)
2055 	    pat->mode = xmlDictLookup(style->dict, mode, -1);
2056 	if (modeURI != NULL)
2057 	    pat->modeURI = xmlDictLookup(style->dict, modeURI, -1);
2058 	if (priority != XSLT_PAT_NO_PRIORITY)
2059 	    pat->priority = priority;
2060 
2061 	/*
2062 	 * insert it in the hash table list corresponding to its lookup name
2063 	 */
2064 	switch (pat->steps[0].op) {
2065         case XSLT_OP_ATTR:
2066 	    if (pat->steps[0].value != NULL)
2067 		name = pat->steps[0].value;
2068 	    else
2069 		top = &(style->attrMatch);
2070 	    break;
2071         case XSLT_OP_PARENT:
2072         case XSLT_OP_ANCESTOR:
2073 	    top = &(style->elemMatch);
2074 	    break;
2075         case XSLT_OP_ROOT:
2076 	    top = &(style->rootMatch);
2077 	    break;
2078         case XSLT_OP_KEY:
2079 	    top = &(style->keyMatch);
2080 	    break;
2081         case XSLT_OP_ID:
2082 	    /* TODO optimize ID !!! */
2083         case XSLT_OP_NS:
2084         case XSLT_OP_ALL:
2085 	    top = &(style->elemMatch);
2086 	    break;
2087         case XSLT_OP_END:
2088 	case XSLT_OP_PREDICATE:
2089 	    xsltTransformError(NULL, style, NULL,
2090 			     "xsltAddTemplate: invalid compiled pattern\n");
2091 	    xsltFreeCompMatch(pat);
2092 	    return(-1);
2093 	    /*
2094 	     * TODO: some flags at the top level about type based patterns
2095 	     *       would be faster than inclusion in the hash table.
2096 	     */
2097 	case XSLT_OP_PI:
2098 	    if (pat->steps[0].value != NULL)
2099 		name = pat->steps[0].value;
2100 	    else
2101 		top = &(style->piMatch);
2102 	    break;
2103 	case XSLT_OP_COMMENT:
2104 	    top = &(style->commentMatch);
2105 	    break;
2106 	case XSLT_OP_TEXT:
2107 	    top = &(style->textMatch);
2108 	    break;
2109         case XSLT_OP_ELEM:
2110 	case XSLT_OP_NODE:
2111 	    if (pat->steps[0].value != NULL)
2112 		name = pat->steps[0].value;
2113 	    else
2114 		top = &(style->elemMatch);
2115 	    break;
2116 	}
2117 	if (name != NULL) {
2118 	    if (style->templatesHash == NULL) {
2119 		style->templatesHash = xmlHashCreate(1024);
2120 		if (style->templatesHash == NULL) {
2121 		    xsltFreeCompMatch(pat);
2122 		    return(-1);
2123 		}
2124 		xmlHashAddEntry3(style->templatesHash, name, mode, modeURI, pat);
2125 	    } else {
2126 		list = (xsltCompMatchPtr) xmlHashLookup3(style->templatesHash,
2127 							 name, mode, modeURI);
2128 		if (list == NULL) {
2129 		    xmlHashAddEntry3(style->templatesHash, name,
2130 				     mode, modeURI, pat);
2131 		} else {
2132 		    /*
2133 		     * Note '<=' since one must choose among the matching
2134 		     * template rules that are left, the one that occurs
2135 		     * last in the stylesheet
2136 		     */
2137 		    if (list->priority <= pat->priority) {
2138 			pat->next = list;
2139 			xmlHashUpdateEntry3(style->templatesHash, name,
2140 					    mode, modeURI, pat, NULL);
2141 		    } else {
2142 			while (list->next != NULL) {
2143 			    if (list->next->priority <= pat->priority)
2144 				break;
2145 			    list = list->next;
2146 			}
2147 			pat->next = list->next;
2148 			list->next = pat;
2149 		    }
2150 		}
2151 	    }
2152 	} else if (top != NULL) {
2153 	    list = *top;
2154 	    if (list == NULL) {
2155 		*top = pat;
2156 		pat->next = NULL;
2157 	    } else if (list->priority <= pat->priority) {
2158 		pat->next = list;
2159 		*top = pat;
2160 	    } else {
2161 		while (list->next != NULL) {
2162 		    if (list->next->priority <= pat->priority)
2163 			break;
2164 		    list = list->next;
2165 		}
2166 		pat->next = list->next;
2167 		list->next = pat;
2168 	    }
2169 	} else {
2170 	    xsltTransformError(NULL, style, NULL,
2171 			     "xsltAddTemplate: invalid compiled pattern\n");
2172 	    xsltFreeCompMatch(pat);
2173 	    return(-1);
2174 	}
2175 #ifdef WITH_XSLT_DEBUG_PATTERN
2176 	if (mode)
2177 	    xsltGenericDebug(xsltGenericDebugContext,
2178 			 "added pattern : '%s' mode '%s' priority %f\n",
2179 			     pat->pattern, pat->mode, pat->priority);
2180 	else
2181 	    xsltGenericDebug(xsltGenericDebugContext,
2182 			 "added pattern : '%s' priority %f\n",
2183 			     pat->pattern, pat->priority);
2184 #endif
2185 
2186 	pat = next;
2187     }
2188     return(0);
2189 }
2190 
2191 static int
xsltComputeAllKeys(xsltTransformContextPtr ctxt,xmlNodePtr contextNode)2192 xsltComputeAllKeys(xsltTransformContextPtr ctxt, xmlNodePtr contextNode)
2193 {
2194     if ((ctxt == NULL) || (contextNode == NULL)) {
2195 	xsltTransformError(ctxt, NULL, ctxt->inst,
2196 	    "Internal error in xsltComputeAllKeys(): "
2197 	    "Bad arguments.\n");
2198 	return(-1);
2199     }
2200 
2201     if (ctxt->document == NULL) {
2202 	/*
2203 	* The document info will only be NULL if we have a RTF.
2204 	*/
2205 	if (contextNode->doc->_private != NULL)
2206 	    goto doc_info_mismatch;
2207 	/*
2208 	* On-demand creation of the document info (needed for keys).
2209 	*/
2210 	ctxt->document = xsltNewDocument(ctxt, contextNode->doc);
2211 	if (ctxt->document == NULL)
2212 	    return(-1);
2213     }
2214     return xsltInitAllDocKeys(ctxt);
2215 
2216 doc_info_mismatch:
2217     xsltTransformError(ctxt, NULL, ctxt->inst,
2218 	"Internal error in xsltComputeAllKeys(): "
2219 	"The context's document info doesn't match the "
2220 	"document info of the current result tree.\n");
2221     ctxt->state = XSLT_STATE_STOPPED;
2222     return(-1);
2223 }
2224 
2225 /**
2226  * xsltGetTemplate:
2227  * @ctxt:  a XSLT process context
2228  * @node:  the node being processed
2229  * @style:  the current style
2230  *
2231  * Finds the template applying to this node, if @style is non-NULL
2232  * it means one needs to look for the next imported template in scope.
2233  *
2234  * Returns the xsltTemplatePtr or NULL if not found
2235  */
2236 xsltTemplatePtr
xsltGetTemplate(xsltTransformContextPtr ctxt,xmlNodePtr node,xsltStylesheetPtr style)2237 xsltGetTemplate(xsltTransformContextPtr ctxt, xmlNodePtr node,
2238 	        xsltStylesheetPtr style)
2239 {
2240     xsltStylesheetPtr curstyle;
2241     xsltTemplatePtr ret = NULL;
2242     const xmlChar *name = NULL;
2243     xsltCompMatchPtr list = NULL;
2244     float priority;
2245     int keyed = 0;
2246 
2247     if ((ctxt == NULL) || (node == NULL))
2248 	return(NULL);
2249 
2250     if (style == NULL) {
2251 	curstyle = ctxt->style;
2252     } else {
2253 	curstyle = xsltNextImport(style);
2254     }
2255 
2256     while ((curstyle != NULL) && (curstyle != style)) {
2257 	priority = XSLT_PAT_NO_PRIORITY;
2258 	/* TODO : handle IDs/keys here ! */
2259 	if (curstyle->templatesHash != NULL) {
2260 	    /*
2261 	     * Use the top name as selector
2262 	     */
2263 	    switch (node->type) {
2264 		case XML_ELEMENT_NODE:
2265 		    if (node->name[0] == ' ')
2266 			break;
2267 		case XML_ATTRIBUTE_NODE:
2268 		case XML_PI_NODE:
2269 		    name = node->name;
2270 		    break;
2271 		case XML_DOCUMENT_NODE:
2272 		case XML_HTML_DOCUMENT_NODE:
2273 		case XML_TEXT_NODE:
2274 		case XML_CDATA_SECTION_NODE:
2275 		case XML_COMMENT_NODE:
2276 		case XML_ENTITY_REF_NODE:
2277 		case XML_ENTITY_NODE:
2278 		case XML_DOCUMENT_TYPE_NODE:
2279 		case XML_DOCUMENT_FRAG_NODE:
2280 		case XML_NOTATION_NODE:
2281 		case XML_DTD_NODE:
2282 		case XML_ELEMENT_DECL:
2283 		case XML_ATTRIBUTE_DECL:
2284 		case XML_ENTITY_DECL:
2285 		case XML_NAMESPACE_DECL:
2286 		case XML_XINCLUDE_START:
2287 		case XML_XINCLUDE_END:
2288 		    break;
2289 		default:
2290 		    return(NULL);
2291 
2292 	    }
2293 	}
2294 	if (name != NULL) {
2295 	    /*
2296 	     * find the list of applicable expressions based on the name
2297 	     */
2298 	    list = (xsltCompMatchPtr) xmlHashLookup3(curstyle->templatesHash,
2299 					     name, ctxt->mode, ctxt->modeURI);
2300 	} else
2301 	    list = NULL;
2302 	while (list != NULL) {
2303 	    if (xsltTestCompMatch(ctxt, list, node,
2304 			          ctxt->mode, ctxt->modeURI)) {
2305 		ret = list->template;
2306 		priority = list->priority;
2307 		break;
2308 	    }
2309 	    list = list->next;
2310 	}
2311 	list = NULL;
2312 
2313 	/*
2314 	 * find alternate generic matches
2315 	 */
2316 	switch (node->type) {
2317 	    case XML_ELEMENT_NODE:
2318 		if (node->name[0] == ' ')
2319 		    list = curstyle->rootMatch;
2320 		else
2321 		    list = curstyle->elemMatch;
2322 		if (node->psvi != NULL) keyed = 1;
2323 		break;
2324 	    case XML_ATTRIBUTE_NODE: {
2325 	        xmlAttrPtr attr;
2326 
2327 		list = curstyle->attrMatch;
2328 		attr = (xmlAttrPtr) node;
2329 		if (attr->psvi != NULL) keyed = 1;
2330 		break;
2331 	    }
2332 	    case XML_PI_NODE:
2333 		list = curstyle->piMatch;
2334 		if (node->psvi != NULL) keyed = 1;
2335 		break;
2336 	    case XML_DOCUMENT_NODE:
2337 	    case XML_HTML_DOCUMENT_NODE: {
2338 	        xmlDocPtr doc;
2339 
2340 		list = curstyle->rootMatch;
2341 		doc = (xmlDocPtr) node;
2342 		if (doc->psvi != NULL) keyed = 1;
2343 		break;
2344 	    }
2345 	    case XML_TEXT_NODE:
2346 	    case XML_CDATA_SECTION_NODE:
2347 		list = curstyle->textMatch;
2348 		if (node->psvi != NULL) keyed = 1;
2349 		break;
2350 	    case XML_COMMENT_NODE:
2351 		list = curstyle->commentMatch;
2352 		if (node->psvi != NULL) keyed = 1;
2353 		break;
2354 	    case XML_ENTITY_REF_NODE:
2355 	    case XML_ENTITY_NODE:
2356 	    case XML_DOCUMENT_TYPE_NODE:
2357 	    case XML_DOCUMENT_FRAG_NODE:
2358 	    case XML_NOTATION_NODE:
2359 	    case XML_DTD_NODE:
2360 	    case XML_ELEMENT_DECL:
2361 	    case XML_ATTRIBUTE_DECL:
2362 	    case XML_ENTITY_DECL:
2363 	    case XML_NAMESPACE_DECL:
2364 	    case XML_XINCLUDE_START:
2365 	    case XML_XINCLUDE_END:
2366 		break;
2367 	    default:
2368 		break;
2369 	}
2370 	while ((list != NULL) &&
2371 	       ((ret == NULL)  || (list->priority > priority))) {
2372 	    if (xsltTestCompMatch(ctxt, list, node,
2373 			          ctxt->mode, ctxt->modeURI)) {
2374 		ret = list->template;
2375 		priority = list->priority;
2376 		break;
2377 	    }
2378 	    list = list->next;
2379 	}
2380 	/*
2381 	 * Some of the tests for elements can also apply to documents
2382 	 */
2383 	if ((node->type == XML_DOCUMENT_NODE) ||
2384 	    (node->type == XML_HTML_DOCUMENT_NODE) ||
2385 	    (node->type == XML_TEXT_NODE)) {
2386 	    list = curstyle->elemMatch;
2387 	    while ((list != NULL) &&
2388 		   ((ret == NULL)  || (list->priority > priority))) {
2389 		if (xsltTestCompMatch(ctxt, list, node,
2390 				      ctxt->mode, ctxt->modeURI)) {
2391 		    ret = list->template;
2392 		    priority = list->priority;
2393 		    break;
2394 		}
2395 		list = list->next;
2396 	    }
2397 	} else if ((node->type == XML_PI_NODE) ||
2398 		   (node->type == XML_COMMENT_NODE)) {
2399 	    list = curstyle->elemMatch;
2400 	    while ((list != NULL) &&
2401 		   ((ret == NULL)  || (list->priority > priority))) {
2402 		if (xsltTestCompMatch(ctxt, list, node,
2403 				      ctxt->mode, ctxt->modeURI)) {
2404 		    ret = list->template;
2405 		    priority = list->priority;
2406 		    break;
2407 		}
2408 		list = list->next;
2409 	    }
2410 	}
2411 
2412 keyed_match:
2413 	if (keyed) {
2414 	    list = curstyle->keyMatch;
2415 	    while ((list != NULL) &&
2416 		   ((ret == NULL)  || (list->priority > priority))) {
2417 		if (xsltTestCompMatch(ctxt, list, node,
2418 				      ctxt->mode, ctxt->modeURI)) {
2419 		    ret = list->template;
2420 		    priority = list->priority;
2421 		    break;
2422 		}
2423 		list = list->next;
2424 	    }
2425 	}
2426 	else if (ctxt->hasTemplKeyPatterns &&
2427 	    ((ctxt->document == NULL) ||
2428 	     (ctxt->document->nbKeysComputed < ctxt->nbKeys)))
2429 	{
2430 	    /*
2431 	    * Compute all remaining keys for this document.
2432 	    *
2433 	    * REVISIT TODO: I think this could be further optimized.
2434 	    */
2435 	    if (xsltComputeAllKeys(ctxt, node) == -1)
2436 		goto error;
2437 
2438 	    switch (node->type) {
2439 		case XML_ELEMENT_NODE:
2440 		    if (node->psvi != NULL) keyed = 1;
2441 		    break;
2442 		case XML_ATTRIBUTE_NODE:
2443 		    if (((xmlAttrPtr) node)->psvi != NULL) keyed = 1;
2444 		    break;
2445 		case XML_TEXT_NODE:
2446 		case XML_CDATA_SECTION_NODE:
2447 		case XML_COMMENT_NODE:
2448 		case XML_PI_NODE:
2449 		    if (node->psvi != NULL) keyed = 1;
2450 		    break;
2451 		case XML_DOCUMENT_NODE:
2452 		case XML_HTML_DOCUMENT_NODE:
2453 		    if (((xmlDocPtr) node)->psvi != NULL) keyed = 1;
2454 		    break;
2455 		default:
2456 		    break;
2457 	    }
2458 	    if (keyed)
2459 		goto keyed_match;
2460 	}
2461 	if (ret != NULL)
2462 	    return(ret);
2463 
2464 	/*
2465 	 * Cycle on next curstylesheet import.
2466 	 */
2467 	curstyle = xsltNextImport(curstyle);
2468     }
2469 
2470 error:
2471     return(NULL);
2472 }
2473 
2474 /**
2475  * xsltCleanupTemplates:
2476  * @style: an XSLT stylesheet
2477  *
2478  * Cleanup the state of the templates used by the stylesheet and
2479  * the ones it imports.
2480  */
2481 void
xsltCleanupTemplates(xsltStylesheetPtr style ATTRIBUTE_UNUSED)2482 xsltCleanupTemplates(xsltStylesheetPtr style ATTRIBUTE_UNUSED) {
2483 }
2484 
2485 /**
2486  * xsltFreeTemplateHashes:
2487  * @style: an XSLT stylesheet
2488  *
2489  * Free up the memory used by xsltAddTemplate/xsltGetTemplate mechanism
2490  */
2491 void
xsltFreeTemplateHashes(xsltStylesheetPtr style)2492 xsltFreeTemplateHashes(xsltStylesheetPtr style) {
2493     if (style->templatesHash != NULL)
2494 	xmlHashFree((xmlHashTablePtr) style->templatesHash,
2495 		    (xmlHashDeallocator) xsltFreeCompMatchList);
2496     if (style->rootMatch != NULL)
2497         xsltFreeCompMatchList(style->rootMatch);
2498     if (style->keyMatch != NULL)
2499         xsltFreeCompMatchList(style->keyMatch);
2500     if (style->elemMatch != NULL)
2501         xsltFreeCompMatchList(style->elemMatch);
2502     if (style->attrMatch != NULL)
2503         xsltFreeCompMatchList(style->attrMatch);
2504     if (style->parentMatch != NULL)
2505         xsltFreeCompMatchList(style->parentMatch);
2506     if (style->textMatch != NULL)
2507         xsltFreeCompMatchList(style->textMatch);
2508     if (style->piMatch != NULL)
2509         xsltFreeCompMatchList(style->piMatch);
2510     if (style->commentMatch != NULL)
2511         xsltFreeCompMatchList(style->commentMatch);
2512 }
2513 
2514