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