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