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