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