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