src/third_party/libxslt/libxslt/pattern.c

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