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