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