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