• 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 ((CUR == '/') && (NXT(1) == '/')) {
1791 		PUSH(XSLT_OP_ANCESTOR, NULL, NULL, novar);
1792 		NEXT;
1793 		NEXT;
1794 		SKIP_BLANKS;
1795 		xsltCompileRelativePathPattern(ctxt, NULL, novar);
1796 	    } else if (CUR == '/') {
1797 		PUSH(XSLT_OP_PARENT, NULL, NULL, novar);
1798 		NEXT;
1799 		SKIP_BLANKS;
1800 		xsltCompileRelativePathPattern(ctxt, NULL, novar);
1801 	    }
1802 	    return;
1803 	}
1804 	xsltCompileRelativePathPattern(ctxt, name, novar);
1805     }
1806 error:
1807     return;
1808 }
1809 
1810 /**
1811  * xsltCompilePatternInternal:
1812  * @pattern: an XSLT pattern
1813  * @doc:  the containing document
1814  * @node:  the containing element
1815  * @style:  the stylesheet
1816  * @runtime:  the transformation context, if done at run-time
1817  * @novar:  flag to prohibit xslt variables
1818  *
1819  * Compile the XSLT pattern and generates a list of precompiled form suitable
1820  * for fast matching.
1821  *
1822  * [1] Pattern ::= LocationPathPattern | Pattern '|' LocationPathPattern
1823  *
1824  * Returns the generated pattern list or NULL in case of failure
1825  */
1826 
1827 static xsltCompMatchPtr
xsltCompilePatternInternal(const xmlChar * pattern,xmlDocPtr doc,xmlNodePtr node,xsltStylesheetPtr style,xsltTransformContextPtr runtime,int novar)1828 xsltCompilePatternInternal(const xmlChar *pattern, xmlDocPtr doc,
1829 	           xmlNodePtr node, xsltStylesheetPtr style,
1830 		   xsltTransformContextPtr runtime, int novar) {
1831     xsltParserContextPtr ctxt = NULL;
1832     xsltCompMatchPtr element, first = NULL, previous = NULL;
1833     int current, start, end, level, j;
1834 
1835     if (pattern == NULL) {
1836 	xsltTransformError(NULL, NULL, node,
1837 			 "xsltCompilePattern : NULL pattern\n");
1838 	return(NULL);
1839     }
1840 
1841     ctxt = xsltNewParserContext(style, runtime);
1842     if (ctxt == NULL)
1843 	return(NULL);
1844     ctxt->doc = doc;
1845     ctxt->elem = node;
1846     current = end = 0;
1847     while (pattern[current] != 0) {
1848 	start = current;
1849 	while (IS_BLANK_CH(pattern[current]))
1850 	    current++;
1851 	end = current;
1852 	level = 0;
1853 	while ((pattern[end] != 0) && ((pattern[end] != '|') || (level != 0))) {
1854 	    if (pattern[end] == '[')
1855 		level++;
1856 	    else if (pattern[end] == ']')
1857 		level--;
1858 	    else if (pattern[end] == '\'') {
1859 		end++;
1860 		while ((pattern[end] != 0) && (pattern[end] != '\''))
1861 		    end++;
1862 	    } else if (pattern[end] == '"') {
1863 		end++;
1864 		while ((pattern[end] != 0) && (pattern[end] != '"'))
1865 		    end++;
1866 	    }
1867 	    end++;
1868 	}
1869 	if (current == end) {
1870 	    xsltTransformError(NULL, NULL, node,
1871 			     "xsltCompilePattern : NULL pattern\n");
1872 	    goto error;
1873 	}
1874 	element = xsltNewCompMatch();
1875 	if (element == NULL) {
1876 	    goto error;
1877 	}
1878 	if (first == NULL)
1879 	    first = element;
1880 	else if (previous != NULL)
1881 	    previous->next = element;
1882 	previous = element;
1883 
1884 	ctxt->comp = element;
1885 	ctxt->base = xmlStrndup(&pattern[start], end - start);
1886 	if (ctxt->base == NULL)
1887 	    goto error;
1888 	ctxt->cur = &(ctxt->base)[current - start];
1889 	element->pattern = ctxt->base;
1890 	element->nsList = xmlGetNsList(doc, node);
1891 	j = 0;
1892 	if (element->nsList != NULL) {
1893 	    while (element->nsList[j] != NULL)
1894 		j++;
1895 	}
1896 	element->nsNr = j;
1897 
1898 
1899 #ifdef WITH_XSLT_DEBUG_PATTERN
1900 	xsltGenericDebug(xsltGenericDebugContext,
1901 			 "xsltCompilePattern : parsing '%s'\n",
1902 			 element->pattern);
1903 #endif
1904 	/*
1905 	 Preset default priority to be zero.
1906 	 This may be changed by xsltCompileLocationPathPattern.
1907 	 */
1908 	element->priority = 0;
1909 	xsltCompileLocationPathPattern(ctxt, novar);
1910 	if (ctxt->error) {
1911 	    xsltTransformError(NULL, style, node,
1912 			     "xsltCompilePattern : failed to compile '%s'\n",
1913 			     element->pattern);
1914 	    if (style != NULL) style->errors++;
1915 	    goto error;
1916 	}
1917 
1918 	/*
1919 	 * Reverse for faster interpretation.
1920 	 */
1921 	xsltReverseCompMatch(ctxt, element);
1922 
1923 	/*
1924 	 * Set-up the priority
1925 	 */
1926 	if (element->priority == 0) {	/* if not yet determined */
1927 	    if (((element->steps[0].op == XSLT_OP_ELEM) ||
1928 		 (element->steps[0].op == XSLT_OP_ATTR) ||
1929 		 (element->steps[0].op == XSLT_OP_PI)) &&
1930 		(element->steps[0].value != NULL) &&
1931 		(element->steps[1].op == XSLT_OP_END)) {
1932 		;	/* previously preset */
1933 	    } else if ((element->steps[0].op == XSLT_OP_ATTR) &&
1934 		       (element->steps[0].value2 != NULL) &&
1935 		       (element->steps[1].op == XSLT_OP_END)) {
1936 			element->priority = -0.25;
1937 	    } else if ((element->steps[0].op == XSLT_OP_NS) &&
1938 		       (element->steps[0].value != NULL) &&
1939 		       (element->steps[1].op == XSLT_OP_END)) {
1940 			element->priority = -0.25;
1941 	    } else if ((element->steps[0].op == XSLT_OP_ATTR) &&
1942 		       (element->steps[0].value == NULL) &&
1943 		       (element->steps[0].value2 == NULL) &&
1944 		       (element->steps[1].op == XSLT_OP_END)) {
1945 			element->priority = -0.5;
1946 	    } else if (((element->steps[0].op == XSLT_OP_PI) ||
1947 		       (element->steps[0].op == XSLT_OP_TEXT) ||
1948 		       (element->steps[0].op == XSLT_OP_ALL) ||
1949 		       (element->steps[0].op == XSLT_OP_NODE) ||
1950 		       (element->steps[0].op == XSLT_OP_COMMENT)) &&
1951 		       (element->steps[1].op == XSLT_OP_END)) {
1952 			element->priority = -0.5;
1953 	    } else {
1954 		element->priority = 0.5;
1955 	    }
1956 	}
1957 #ifdef WITH_XSLT_DEBUG_PATTERN
1958 	xsltGenericDebug(xsltGenericDebugContext,
1959 		     "xsltCompilePattern : parsed %s, default priority %f\n",
1960 			 element->pattern, element->priority);
1961 #endif
1962 	if (pattern[end] == '|')
1963 	    end++;
1964 	current = end;
1965     }
1966     if (end == 0) {
1967 	xsltTransformError(NULL, style, node,
1968 			 "xsltCompilePattern : NULL pattern\n");
1969 	if (style != NULL) style->errors++;
1970 	goto error;
1971     }
1972 
1973     xsltFreeParserContext(ctxt);
1974     return(first);
1975 
1976 error:
1977     if (ctxt != NULL)
1978 	xsltFreeParserContext(ctxt);
1979     if (first != NULL)
1980 	xsltFreeCompMatchList(first);
1981     return(NULL);
1982 }
1983 
1984 /**
1985  * xsltCompilePattern:
1986  * @pattern: an XSLT pattern
1987  * @doc:  the containing document
1988  * @node:  the containing element
1989  * @style:  the stylesheet
1990  * @runtime:  the transformation context, if done at run-time
1991  *
1992  * Compile the XSLT pattern and generates a list of precompiled form suitable
1993  * for fast matching.
1994  *
1995  * [1] Pattern ::= LocationPathPattern | Pattern '|' LocationPathPattern
1996  *
1997  * Returns the generated pattern list or NULL in case of failure
1998  */
1999 
2000 xsltCompMatchPtr
xsltCompilePattern(const xmlChar * pattern,xmlDocPtr doc,xmlNodePtr node,xsltStylesheetPtr style,xsltTransformContextPtr runtime)2001 xsltCompilePattern(const xmlChar *pattern, xmlDocPtr doc,
2002 	           xmlNodePtr node, xsltStylesheetPtr style,
2003 		   xsltTransformContextPtr runtime) {
2004     return (xsltCompilePatternInternal(pattern, doc, node, style, runtime, 0));
2005 }
2006 
2007 /************************************************************************
2008  *									*
2009  *			Module interfaces				*
2010  *									*
2011  ************************************************************************/
2012 
2013 /**
2014  * xsltAddTemplate:
2015  * @style: an XSLT stylesheet
2016  * @cur: an XSLT template
2017  * @mode:  the mode name or NULL
2018  * @modeURI:  the mode URI or NULL
2019  *
2020  * Register the XSLT pattern associated to @cur
2021  *
2022  * Returns -1 in case of error, 0 otherwise
2023  */
2024 int
xsltAddTemplate(xsltStylesheetPtr style,xsltTemplatePtr cur,const xmlChar * mode,const xmlChar * modeURI)2025 xsltAddTemplate(xsltStylesheetPtr style, xsltTemplatePtr cur,
2026 	        const xmlChar *mode, const xmlChar *modeURI) {
2027     xsltCompMatchPtr pat, list, next;
2028     /*
2029      * 'top' will point to style->xxxMatch ptr - declaring as 'void'
2030      *  avoids gcc 'type-punned pointer' warning.
2031      */
2032     void **top = NULL;
2033     const xmlChar *name = NULL;
2034     float priority;              /* the priority */
2035 
2036     if ((style == NULL) || (cur == NULL) || (cur->match == NULL))
2037 	return(-1);
2038 
2039     priority = cur->priority;
2040     pat = xsltCompilePatternInternal(cur->match, style->doc, cur->elem,
2041 		    style, NULL, 1);
2042     if (pat == NULL)
2043     	return(-1);
2044     while (pat) {
2045 	next = pat->next;
2046 	pat->next = NULL;
2047 	name = NULL;
2048 
2049 	pat->template = cur;
2050 	if (mode != NULL)
2051 	    pat->mode = xmlDictLookup(style->dict, mode, -1);
2052 	if (modeURI != NULL)
2053 	    pat->modeURI = xmlDictLookup(style->dict, modeURI, -1);
2054 	if (priority != XSLT_PAT_NO_PRIORITY)
2055 	    pat->priority = priority;
2056 
2057 	/*
2058 	 * insert it in the hash table list corresponding to its lookup name
2059 	 */
2060 	switch (pat->steps[0].op) {
2061         case XSLT_OP_ATTR:
2062 	    if (pat->steps[0].value != NULL)
2063 		name = pat->steps[0].value;
2064 	    else
2065 		top = &(style->attrMatch);
2066 	    break;
2067         case XSLT_OP_PARENT:
2068         case XSLT_OP_ANCESTOR:
2069 	    top = &(style->elemMatch);
2070 	    break;
2071         case XSLT_OP_ROOT:
2072 	    top = &(style->rootMatch);
2073 	    break;
2074         case XSLT_OP_KEY:
2075 	    top = &(style->keyMatch);
2076 	    break;
2077         case XSLT_OP_ID:
2078 	    /* TODO optimize ID !!! */
2079         case XSLT_OP_NS:
2080         case XSLT_OP_ALL:
2081 	    top = &(style->elemMatch);
2082 	    break;
2083         case XSLT_OP_END:
2084 	case XSLT_OP_PREDICATE:
2085 	    xsltTransformError(NULL, style, NULL,
2086 			     "xsltAddTemplate: invalid compiled pattern\n");
2087 	    xsltFreeCompMatch(pat);
2088 	    return(-1);
2089 	    /*
2090 	     * TODO: some flags at the top level about type based patterns
2091 	     *       would be faster than inclusion in the hash table.
2092 	     */
2093 	case XSLT_OP_PI:
2094 	    if (pat->steps[0].value != NULL)
2095 		name = pat->steps[0].value;
2096 	    else
2097 		top = &(style->piMatch);
2098 	    break;
2099 	case XSLT_OP_COMMENT:
2100 	    top = &(style->commentMatch);
2101 	    break;
2102 	case XSLT_OP_TEXT:
2103 	    top = &(style->textMatch);
2104 	    break;
2105         case XSLT_OP_ELEM:
2106 	case XSLT_OP_NODE:
2107 	    if (pat->steps[0].value != NULL)
2108 		name = pat->steps[0].value;
2109 	    else
2110 		top = &(style->elemMatch);
2111 	    break;
2112 	}
2113 	if (name != NULL) {
2114 	    if (style->templatesHash == NULL) {
2115 		style->templatesHash = xmlHashCreate(1024);
2116 		if (style->templatesHash == NULL) {
2117 		    xsltFreeCompMatch(pat);
2118 		    return(-1);
2119 		}
2120 		xmlHashAddEntry3(style->templatesHash, name, mode, modeURI, pat);
2121 	    } else {
2122 		list = (xsltCompMatchPtr) xmlHashLookup3(style->templatesHash,
2123 							 name, mode, modeURI);
2124 		if (list == NULL) {
2125 		    xmlHashAddEntry3(style->templatesHash, name,
2126 				     mode, modeURI, pat);
2127 		} else {
2128 		    /*
2129 		     * Note '<=' since one must choose among the matching
2130 		     * template rules that are left, the one that occurs
2131 		     * last in the stylesheet
2132 		     */
2133 		    if (list->priority <= pat->priority) {
2134 			pat->next = list;
2135 			xmlHashUpdateEntry3(style->templatesHash, name,
2136 					    mode, modeURI, pat, NULL);
2137 		    } else {
2138 			while (list->next != NULL) {
2139 			    if (list->next->priority <= pat->priority)
2140 				break;
2141 			    list = list->next;
2142 			}
2143 			pat->next = list->next;
2144 			list->next = pat;
2145 		    }
2146 		}
2147 	    }
2148 	} else if (top != NULL) {
2149 	    list = *top;
2150 	    if (list == NULL) {
2151 		*top = pat;
2152 		pat->next = NULL;
2153 	    } else if (list->priority <= pat->priority) {
2154 		pat->next = list;
2155 		*top = pat;
2156 	    } else {
2157 		while (list->next != NULL) {
2158 		    if (list->next->priority <= pat->priority)
2159 			break;
2160 		    list = list->next;
2161 		}
2162 		pat->next = list->next;
2163 		list->next = pat;
2164 	    }
2165 	} else {
2166 	    xsltTransformError(NULL, style, NULL,
2167 			     "xsltAddTemplate: invalid compiled pattern\n");
2168 	    xsltFreeCompMatch(pat);
2169 	    return(-1);
2170 	}
2171 #ifdef WITH_XSLT_DEBUG_PATTERN
2172 	if (mode)
2173 	    xsltGenericDebug(xsltGenericDebugContext,
2174 			 "added pattern : '%s' mode '%s' priority %f\n",
2175 			     pat->pattern, pat->mode, pat->priority);
2176 	else
2177 	    xsltGenericDebug(xsltGenericDebugContext,
2178 			 "added pattern : '%s' priority %f\n",
2179 			     pat->pattern, pat->priority);
2180 #endif
2181 
2182 	pat = next;
2183     }
2184     return(0);
2185 }
2186 
2187 static int
xsltComputeAllKeys(xsltTransformContextPtr ctxt,xmlNodePtr contextNode)2188 xsltComputeAllKeys(xsltTransformContextPtr ctxt, xmlNodePtr contextNode)
2189 {
2190     if ((ctxt == NULL) || (contextNode == NULL)) {
2191 	xsltTransformError(ctxt, NULL, ctxt->inst,
2192 	    "Internal error in xsltComputeAllKeys(): "
2193 	    "Bad arguments.\n");
2194 	return(-1);
2195     }
2196 
2197     if (ctxt->document == NULL) {
2198 	/*
2199 	* The document info will only be NULL if we have a RTF.
2200 	*/
2201 	if (contextNode->doc->_private != NULL)
2202 	    goto doc_info_mismatch;
2203 	/*
2204 	* On-demand creation of the document info (needed for keys).
2205 	*/
2206 	ctxt->document = xsltNewDocument(ctxt, contextNode->doc);
2207 	if (ctxt->document == NULL)
2208 	    return(-1);
2209     }
2210     return xsltInitAllDocKeys(ctxt);
2211 
2212 doc_info_mismatch:
2213     xsltTransformError(ctxt, NULL, ctxt->inst,
2214 	"Internal error in xsltComputeAllKeys(): "
2215 	"The context's document info doesn't match the "
2216 	"document info of the current result tree.\n");
2217     ctxt->state = XSLT_STATE_STOPPED;
2218     return(-1);
2219 }
2220 
2221 /**
2222  * xsltGetTemplate:
2223  * @ctxt:  a XSLT process context
2224  * @node:  the node being processed
2225  * @style:  the current style
2226  *
2227  * Finds the template applying to this node, if @style is non-NULL
2228  * it means one needs to look for the next imported template in scope.
2229  *
2230  * Returns the xsltTemplatePtr or NULL if not found
2231  */
2232 xsltTemplatePtr
xsltGetTemplate(xsltTransformContextPtr ctxt,xmlNodePtr node,xsltStylesheetPtr style)2233 xsltGetTemplate(xsltTransformContextPtr ctxt, xmlNodePtr node,
2234 	        xsltStylesheetPtr style)
2235 {
2236     xsltStylesheetPtr curstyle;
2237     xsltTemplatePtr ret = NULL;
2238     const xmlChar *name = NULL;
2239     xsltCompMatchPtr list = NULL;
2240     float priority;
2241     int keyed = 0;
2242 
2243     if ((ctxt == NULL) || (node == NULL))
2244 	return(NULL);
2245 
2246     if (style == NULL) {
2247 	curstyle = ctxt->style;
2248     } else {
2249 	curstyle = xsltNextImport(style);
2250     }
2251 
2252     while ((curstyle != NULL) && (curstyle != style)) {
2253 	priority = XSLT_PAT_NO_PRIORITY;
2254 	/* TODO : handle IDs/keys here ! */
2255 	if (curstyle->templatesHash != NULL) {
2256 	    /*
2257 	     * Use the top name as selector
2258 	     */
2259 	    switch (node->type) {
2260 		case XML_ELEMENT_NODE:
2261 		    if (node->name[0] == ' ')
2262 			break;
2263 		case XML_ATTRIBUTE_NODE:
2264 		case XML_PI_NODE:
2265 		    name = node->name;
2266 		    break;
2267 		case XML_DOCUMENT_NODE:
2268 		case XML_HTML_DOCUMENT_NODE:
2269 		case XML_TEXT_NODE:
2270 		case XML_CDATA_SECTION_NODE:
2271 		case XML_COMMENT_NODE:
2272 		case XML_ENTITY_REF_NODE:
2273 		case XML_ENTITY_NODE:
2274 		case XML_DOCUMENT_TYPE_NODE:
2275 		case XML_DOCUMENT_FRAG_NODE:
2276 		case XML_NOTATION_NODE:
2277 		case XML_DTD_NODE:
2278 		case XML_ELEMENT_DECL:
2279 		case XML_ATTRIBUTE_DECL:
2280 		case XML_ENTITY_DECL:
2281 		case XML_NAMESPACE_DECL:
2282 		case XML_XINCLUDE_START:
2283 		case XML_XINCLUDE_END:
2284 		    break;
2285 		default:
2286 		    return(NULL);
2287 
2288 	    }
2289 	}
2290 	if (name != NULL) {
2291 	    /*
2292 	     * find the list of applicable expressions based on the name
2293 	     */
2294 	    list = (xsltCompMatchPtr) xmlHashLookup3(curstyle->templatesHash,
2295 					     name, ctxt->mode, ctxt->modeURI);
2296 	} else
2297 	    list = NULL;
2298 	while (list != NULL) {
2299 	    if (xsltTestCompMatch(ctxt, list, node,
2300 			          ctxt->mode, ctxt->modeURI)) {
2301 		ret = list->template;
2302 		priority = list->priority;
2303 		break;
2304 	    }
2305 	    list = list->next;
2306 	}
2307 	list = NULL;
2308 
2309 	/*
2310 	 * find alternate generic matches
2311 	 */
2312 	switch (node->type) {
2313 	    case XML_ELEMENT_NODE:
2314 		if (node->name[0] == ' ')
2315 		    list = curstyle->rootMatch;
2316 		else
2317 		    list = curstyle->elemMatch;
2318 		if (node->psvi != NULL) keyed = 1;
2319 		break;
2320 	    case XML_ATTRIBUTE_NODE: {
2321 	        xmlAttrPtr attr;
2322 
2323 		list = curstyle->attrMatch;
2324 		attr = (xmlAttrPtr) node;
2325 		if (attr->psvi != NULL) keyed = 1;
2326 		break;
2327 	    }
2328 	    case XML_PI_NODE:
2329 		list = curstyle->piMatch;
2330 		if (node->psvi != NULL) keyed = 1;
2331 		break;
2332 	    case XML_DOCUMENT_NODE:
2333 	    case XML_HTML_DOCUMENT_NODE: {
2334 	        xmlDocPtr doc;
2335 
2336 		list = curstyle->rootMatch;
2337 		doc = (xmlDocPtr) node;
2338 		if (doc->psvi != NULL) keyed = 1;
2339 		break;
2340 	    }
2341 	    case XML_TEXT_NODE:
2342 	    case XML_CDATA_SECTION_NODE:
2343 		list = curstyle->textMatch;
2344 		if (node->psvi != NULL) keyed = 1;
2345 		break;
2346 	    case XML_COMMENT_NODE:
2347 		list = curstyle->commentMatch;
2348 		if (node->psvi != NULL) keyed = 1;
2349 		break;
2350 	    case XML_ENTITY_REF_NODE:
2351 	    case XML_ENTITY_NODE:
2352 	    case XML_DOCUMENT_TYPE_NODE:
2353 	    case XML_DOCUMENT_FRAG_NODE:
2354 	    case XML_NOTATION_NODE:
2355 	    case XML_DTD_NODE:
2356 	    case XML_ELEMENT_DECL:
2357 	    case XML_ATTRIBUTE_DECL:
2358 	    case XML_ENTITY_DECL:
2359 	    case XML_NAMESPACE_DECL:
2360 	    case XML_XINCLUDE_START:
2361 	    case XML_XINCLUDE_END:
2362 		break;
2363 	    default:
2364 		break;
2365 	}
2366 	while ((list != NULL) &&
2367 	       ((ret == NULL)  || (list->priority > priority))) {
2368 	    if (xsltTestCompMatch(ctxt, list, node,
2369 			          ctxt->mode, ctxt->modeURI)) {
2370 		ret = list->template;
2371 		priority = list->priority;
2372 		break;
2373 	    }
2374 	    list = list->next;
2375 	}
2376 	/*
2377 	 * Some of the tests for elements can also apply to documents
2378 	 */
2379 	if ((node->type == XML_DOCUMENT_NODE) ||
2380 	    (node->type == XML_HTML_DOCUMENT_NODE) ||
2381 	    (node->type == XML_TEXT_NODE)) {
2382 	    list = curstyle->elemMatch;
2383 	    while ((list != NULL) &&
2384 		   ((ret == NULL)  || (list->priority > priority))) {
2385 		if (xsltTestCompMatch(ctxt, list, node,
2386 				      ctxt->mode, ctxt->modeURI)) {
2387 		    ret = list->template;
2388 		    priority = list->priority;
2389 		    break;
2390 		}
2391 		list = list->next;
2392 	    }
2393 	} else if ((node->type == XML_PI_NODE) ||
2394 		   (node->type == XML_COMMENT_NODE)) {
2395 	    list = curstyle->elemMatch;
2396 	    while ((list != NULL) &&
2397 		   ((ret == NULL)  || (list->priority > priority))) {
2398 		if (xsltTestCompMatch(ctxt, list, node,
2399 				      ctxt->mode, ctxt->modeURI)) {
2400 		    ret = list->template;
2401 		    priority = list->priority;
2402 		    break;
2403 		}
2404 		list = list->next;
2405 	    }
2406 	}
2407 
2408 keyed_match:
2409 	if (keyed) {
2410 	    list = curstyle->keyMatch;
2411 	    while ((list != NULL) &&
2412 		   ((ret == NULL)  || (list->priority > priority))) {
2413 		if (xsltTestCompMatch(ctxt, list, node,
2414 				      ctxt->mode, ctxt->modeURI)) {
2415 		    ret = list->template;
2416 		    priority = list->priority;
2417 		    break;
2418 		}
2419 		list = list->next;
2420 	    }
2421 	}
2422 	else if (ctxt->hasTemplKeyPatterns &&
2423 	    ((ctxt->document == NULL) ||
2424 	     (ctxt->document->nbKeysComputed < ctxt->nbKeys)))
2425 	{
2426 	    /*
2427 	    * Compute all remaining keys for this document.
2428 	    *
2429 	    * REVISIT TODO: I think this could be further optimized.
2430 	    */
2431 	    if (xsltComputeAllKeys(ctxt, node) == -1)
2432 		goto error;
2433 
2434 	    switch (node->type) {
2435 		case XML_ELEMENT_NODE:
2436 		    if (node->psvi != NULL) keyed = 1;
2437 		    break;
2438 		case XML_ATTRIBUTE_NODE:
2439 		    if (((xmlAttrPtr) node)->psvi != NULL) keyed = 1;
2440 		    break;
2441 		case XML_TEXT_NODE:
2442 		case XML_CDATA_SECTION_NODE:
2443 		case XML_COMMENT_NODE:
2444 		case XML_PI_NODE:
2445 		    if (node->psvi != NULL) keyed = 1;
2446 		    break;
2447 		case XML_DOCUMENT_NODE:
2448 		case XML_HTML_DOCUMENT_NODE:
2449 		    if (((xmlDocPtr) node)->psvi != NULL) keyed = 1;
2450 		    break;
2451 		default:
2452 		    break;
2453 	    }
2454 	    if (keyed)
2455 		goto keyed_match;
2456 	}
2457 	if (ret != NULL)
2458 	    return(ret);
2459 
2460 	/*
2461 	 * Cycle on next curstylesheet import.
2462 	 */
2463 	curstyle = xsltNextImport(curstyle);
2464     }
2465 
2466 error:
2467     return(NULL);
2468 }
2469 
2470 /**
2471  * xsltCleanupTemplates:
2472  * @style: an XSLT stylesheet
2473  *
2474  * Cleanup the state of the templates used by the stylesheet and
2475  * the ones it imports.
2476  */
2477 void
xsltCleanupTemplates(xsltStylesheetPtr style ATTRIBUTE_UNUSED)2478 xsltCleanupTemplates(xsltStylesheetPtr style ATTRIBUTE_UNUSED) {
2479 }
2480 
2481 /**
2482  * xsltFreeTemplateHashes:
2483  * @style: an XSLT stylesheet
2484  *
2485  * Free up the memory used by xsltAddTemplate/xsltGetTemplate mechanism
2486  */
2487 void
xsltFreeTemplateHashes(xsltStylesheetPtr style)2488 xsltFreeTemplateHashes(xsltStylesheetPtr style) {
2489     if (style->templatesHash != NULL)
2490 	xmlHashFree((xmlHashTablePtr) style->templatesHash,
2491 		    (xmlHashDeallocator) xsltFreeCompMatchList);
2492     if (style->rootMatch != NULL)
2493         xsltFreeCompMatchList(style->rootMatch);
2494     if (style->keyMatch != NULL)
2495         xsltFreeCompMatchList(style->keyMatch);
2496     if (style->elemMatch != NULL)
2497         xsltFreeCompMatchList(style->elemMatch);
2498     if (style->attrMatch != NULL)
2499         xsltFreeCompMatchList(style->attrMatch);
2500     if (style->parentMatch != NULL)
2501         xsltFreeCompMatchList(style->parentMatch);
2502     if (style->textMatch != NULL)
2503         xsltFreeCompMatchList(style->textMatch);
2504     if (style->piMatch != NULL)
2505         xsltFreeCompMatchList(style->piMatch);
2506     if (style->commentMatch != NULL)
2507         xsltFreeCompMatchList(style->commentMatch);
2508 }
2509 
2510