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 ATTRIBUTE_UNUSED) {
 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 = xsltXPathCompile(ctxt->style, 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, sel = 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             sel = 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 ix, j;
 622                     int nocache = 0;
 623
 624                     prevdoc = (xmlDocPtr)
 625                         XSLT_RUNTIME_EXTRA(ctxt, sel->previousExtra);
 626                     ix = (int)
 627                         XSLT_RUNTIME_EXTRA(ctxt, sel->indexExtra);
 628                     list = (xmlXPathObjectPtr)
 629                         XSLT_RUNTIME_EXTRA_LST(ctxt, sel->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                         ix = 0;
 660
 661                         if ((parent == NULL) || (node->doc == NULL))
 662                             nocache = 1;
 663                         else {
 664                             if ((doc->name != NULL) &&
 665                                 (doc->name[0] == ' ') &&
 666                                 (xmlStrEqual(BAD_CAST doc->name,
 667                                              BAD_CAST " fake node libxslt")))
 668                                 nocache = 1;
 669                         }
 670
 671                         if (nocache == 0) {
 672                             if (list != NULL)
 673                                 xmlXPathFreeObject(list);
 674                             list = newlist;
 675
 676                             XSLT_RUNTIME_EXTRA_LST(ctxt, sel->lenExtra) =
 677                                 (void *) list;
 678                             XSLT_RUNTIME_EXTRA(ctxt, sel->previousExtra) =
 679                                 (void *) doc;
 680                             XSLT_RUNTIME_EXTRA(ctxt, sel->indexExtra) =
 681                                 0;
 682                             XSLT_RUNTIME_EXTRA_FREE(ctxt, sel->lenExtra) =
 683                                 (xmlFreeFunc) xmlXPathFreeObject;
 684                         } else
 685                             list = newlist;
 686                     }
 687                     if ((list->nodesetval == NULL) ||
 688                         (list->nodesetval->nodeNr <= 0)) {
 689                         if (nocache == 1)
 690                             xmlXPathFreeObject(list);
 691                         return(0);
 692                     }
 693                     /* TODO: store the index and use it for the scan */
 694                     if (ix == 0) {
 695                         for (j = 0;j < list->nodesetval->nodeNr;j++) {
 696                             if (list->nodesetval->nodeTab[j] == node) {
 697                                 if (nocache == 1)
 698                                     xmlXPathFreeObject(list);
 699                                 return(1);
 700                             }
 701                         }
 702                     } else {
 703                     }
 704                     if (nocache == 1)
 705                         xmlXPathFreeObject(list);
 706                     return(0);
 707                 }
 708                 /*
 709                  * Depending on the last selection, one may need to
 710                  * recompute contextSize and proximityPosition.
 711                  *
 712                  * TODO: make this thread safe !
 713                  */
 714                 oldCS = ctxt->xpathCtxt->contextSize;
 715                 oldCP = ctxt->xpathCtxt->proximityPosition;
 716                 if ((sel != NULL) &&
 717                     (sel->op == XSLT_OP_ELEM) &&
 718                     (sel->value != NULL) &&
 719                     (node->type == XML_ELEMENT_NODE) &&
 720                     (node->parent != NULL)) {
 721                     xmlNodePtr previous;
 722                     int ix, nocache = 0;
 723
 724                     previous = (xmlNodePtr)
 725                         XSLT_RUNTIME_EXTRA(ctxt, sel->previousExtra);
 726                     ix = (int)
 727                         XSLT_RUNTIME_EXTRA(ctxt, sel->indexExtra);
 728                     if ((previous != NULL) &&
 729                         (previous->parent == node->parent)) {
 730                         /*
 731                          * just walk back to adjust the index
 732                          */
 733                         int indx = 0;
 734                         xmlNodePtr sibling = node;
 735
 736                         while (sibling != NULL) {
 737                             if (sibling == previous)
 738                                 break;
 739                             if ((previous->type == XML_ELEMENT_NODE) &&
 740                                 (previous->name != NULL) &&
 741                                 (sibling->name != NULL) &&
 742                                 (previous->name[0] == sibling->name[0]) &&
 743                                 (xmlStrEqual(previous->name, sibling->name))) {
 744                                 if ((sel->value2 == NULL) ||
 745                                     ((sibling->ns != NULL) &&
 746                                      (xmlStrEqual(sel->value2,
 747                                                   sibling->ns->href))))
 748                                     indx++;
 749                             }
 750                             sibling = sibling->prev;
 751                         }
 752                         if (sibling == NULL) {
 753                             /* hum going backward in document order ... */
 754                             indx = 0;
 755                             sibling = node;
 756                             while (sibling != NULL) {
 757                                 if (sibling == previous)
 758                                     break;
 759                                 if ((sel->value2 == NULL) ||
 760                                     ((sibling->ns != NULL) &&
 761                                      (xmlStrEqual(sel->value2,
 762                                                   sibling->ns->href))))
 763                                     indx--;
 764                                 sibling = sibling->next;
 765                             }
 766                         }
 767                         if (sibling != NULL) {
 768                             pos = ix + indx;
 769                             /*
 770                              * If the node is in a Value Tree we need to
 771                              * save len, but cannot cache the node!
 772                              * (bugs 153137 and 158840)
 773                              */
 774                             if (node->doc != NULL) {
 775                                 len = (int)
 776                                     XSLT_RUNTIME_EXTRA(ctxt, sel->lenExtra);
 777                                 if ((node->doc->name != NULL) &&
 778                                     (node->doc->name[0] != ' ')) {
 779                                     XSLT_RUNTIME_EXTRA(ctxt,
 780                                         sel->previousExtra) = node;
 781                                     XSLT_RUNTIME_EXTRA(ctxt, sel->indexExtra) =
 782                                         (void *) pos;
 783                                 }
 784                             }
 785                             ix = pos;
 786                         } else
 787                             pos = 0;
 788                     } else {
 789                         /*
 790                          * recompute the index
 791                          */
 792                         xmlNodePtr siblings = node->parent->children;
 793                         xmlNodePtr parent = node->parent;
 794
 795                         while (siblings != NULL) {
 796                             if (siblings->type == XML_ELEMENT_NODE) {
 797                                 if (siblings == node) {
 798                                     len++;
 799                                     pos = len;
 800                                 } else if ((node->name != NULL) &&
 801                                            (siblings->name != NULL) &&
 802                                     (node->name[0] == siblings->name[0]) &&
 803                                     (xmlStrEqual(node->name, siblings->name))) {
 804                                     if ((sel->value2 == NULL) ||
 805                                         ((siblings->ns != NULL) &&
 806                                          (xmlStrEqual(sel->value2,
 807                                                       siblings->ns->href))))
 808                                         len++;
 809                                 }
 810                             }
 811                             siblings = siblings->next;
 812                         }
 813                         if ((parent == NULL) || (node->doc == NULL))
 814                             nocache = 1;
 815                         else {
 816                             while (parent->parent != NULL)
 817                                 parent = parent->parent;
 818                             if (((parent->type != XML_DOCUMENT_NODE) &&
 819                                  (parent->type != XML_HTML_DOCUMENT_NODE)) ||
 820                                  (parent != (xmlNodePtr) node->doc))
 821                                 nocache = 1;
 822                         }
 823                     }
 824                     if (pos != 0) {
 825                         ctxt->xpathCtxt->contextSize = len;
 826                         ctxt->xpathCtxt->proximityPosition = pos;
 827                         /*
 828                          * If the node is in a Value Tree we cannot
 829                          * cache it !
 830                          */
 831                         if ((node->doc != NULL) && (nocache == 0)) {
 832                             XSLT_RUNTIME_EXTRA(ctxt, sel->previousExtra) =
 833                                 node;
 834                             XSLT_RUNTIME_EXTRA(ctxt, sel->indexExtra) =
 835                                 (void *) pos;
 836                             XSLT_RUNTIME_EXTRA(ctxt, sel->lenExtra) =
 837                                 (void *) len;
 838                         }
 839                     }
 840                 } else if ((sel != NULL) && (sel->op == XSLT_OP_ALL) &&
 841                            (node->type == XML_ELEMENT_NODE)) {
 842                     xmlNodePtr previous;
 843                     int ix, nocache = 0;
 844
 845                     previous = (xmlNodePtr)
 846                         XSLT_RUNTIME_EXTRA(ctxt, sel->previousExtra);
 847                     ix = (int)
 848                         XSLT_RUNTIME_EXTRA(ctxt, sel->indexExtra);
 849                     if ((previous != NULL) &&
 850                         (previous->parent == node->parent)) {
 851                         /*
 852                          * just walk back to adjust the index
 853                          */
 854                         int indx = 0;
 855                         xmlNodePtr sibling = node;
 856
 857                         while (sibling != NULL) {
 858                             if (sibling == previous)
 859                                 break;
 860                             if (sibling->type == XML_ELEMENT_NODE)
 861                                 indx++;
 862                             sibling = sibling->prev;
 863                         }
 864                         if (sibling == NULL) {
 865                             /* hum going backward in document order ... */
 866                             indx = 0;
 867                             sibling = node;
 868                             while (sibling != NULL) {
 869                                 if (sibling == previous)
 870                                     break;
 871                                 if (sibling->type == XML_ELEMENT_NODE)
 872                                     indx--;
 873                                 sibling = sibling->next;
 874                             }
 875                         }
 876                         if (sibling != NULL) {
 877                             pos = ix + indx;
 878                             /*
 879                              * If the node is in a Value Tree we cannot
 880                              * cache it !
 881                              */
 882                             if ((node->doc != NULL) &&
 883                                 (node->doc->name != NULL) &&
 884                                 (node->doc->name[0] != ' ')) {
 885                                 len = (int)
 886                                     XSLT_RUNTIME_EXTRA(ctxt, sel->lenExtra);
 887                                 XSLT_RUNTIME_EXTRA(ctxt,
 888                                         sel->previousExtra) = node;
 889                                 XSLT_RUNTIME_EXTRA(ctxt, sel->indexExtra) =
 890                                     (void *) pos;
 891                             }
 892                         } else
 893                             pos = 0;
 894                     } else {
 895                         /*
 896                          * recompute the index
 897                          */
 898                         xmlNodePtr siblings = node->parent->children;
 899                         xmlNodePtr parent = node->parent;
 900
 901                         while (siblings != NULL) {
 902                             if (siblings->type == XML_ELEMENT_NODE) {
 903                                 len++;
 904                                 if (siblings == node) {
 905                                     pos = len;
 906                                 }
 907                             }
 908                             siblings = siblings->next;
 909                         }
 910                         if ((parent == NULL) || (node->doc == NULL))
 911                             nocache = 1;
 912                         else {
 913                             while (parent->parent != NULL)
 914                                 parent = parent->parent;
 915                             if (((parent->type != XML_DOCUMENT_NODE) &&
 916                                  (parent->type != XML_HTML_DOCUMENT_NODE)) ||
 917                                  (parent != (xmlNodePtr) node->doc))
 918                                 nocache = 1;
 919                         }
 920                     }
 921                     if (pos != 0) {
 922                         ctxt->xpathCtxt->contextSize = len;
 923                         ctxt->xpathCtxt->proximityPosition = pos;
 924                         /*
 925                          * If the node is in a Value Tree we cannot
 926                          * cache it !
 927                          */
 928                         if ((node->doc != NULL) && (nocache == 0)) {
 929                             XSLT_RUNTIME_EXTRA(ctxt, sel->previousExtra) =
 930                                 node;
 931                             XSLT_RUNTIME_EXTRA(ctxt, sel->indexExtra) =
 932                                 (void *) pos;
 933                             XSLT_RUNTIME_EXTRA(ctxt, sel->lenExtra) =
 934                                 (void *) len;
 935                         }
 936                     }
 937                 }
 938                 oldNode = ctxt->node;
 939                 ctxt->node = node;
 940
 941                 if (step->value == NULL)
 942                     goto wrong_index;
 943                 if (step->comp == NULL)
 944                     goto wrong_index;
 945
 946                 if (!xsltEvalXPathPredicate(ctxt, step->comp, comp->nsList,
 947                                             comp->nsNr))
 948                     goto wrong_index;
 949
 950                 if (pos != 0) {
 951                     ctxt->xpathCtxt->contextSize = oldCS;
 952                     ctxt->xpathCtxt->proximityPosition = oldCP;
 953                 }
 954                 ctxt->node = oldNode;
 955                 break;
 956 wrong_index:
 957                 if (pos != 0) {
 958                     ctxt->xpathCtxt->contextSize = oldCS;
 959                     ctxt->xpathCtxt->proximityPosition = oldCP;
 960                 }
 961                 ctxt->node = oldNode;
 962                 return(0);
 963             }
 964             case XSLT_OP_PI:
 965                 if (node->type != XML_PI_NODE)
 966                     return(0);
 967                 if (step->value != NULL) {
 968                     if (!xmlStrEqual(step->value, node->name))
 969                         return(0);
 970                 }
 971                 break;
 972             case XSLT_OP_COMMENT:
 973                 if (node->type != XML_COMMENT_NODE)
 974                     return(0);
 975                 break;
 976             case XSLT_OP_TEXT:
 977                 if ((node->type != XML_TEXT_NODE) &&
 978                     (node->type != XML_CDATA_SECTION_NODE))
 979                     return(0);
 980                 break;
 981             case XSLT_OP_NODE:
 982                 switch (node->type) {
 983                     case XML_ELEMENT_NODE:
 984                     case XML_CDATA_SECTION_NODE:
 985                     case XML_PI_NODE:
 986                     case XML_COMMENT_NODE:
 987                     case XML_TEXT_NODE:
 988                         break;
 989                     default:
 990                         return(0);
 991                 }
 992                 break;
 993         }
 994     }
 995     return(1);
 996 }
 997
 998 /**
 999  * xsltTestCompMatchList:
1000  * @ctxt:  a XSLT process context
1001  * @node: a node
1002  * @comp: the precompiled pattern list
1003  *
1004  * Test wether the node matches one of the patterns in the list
1005  *
1006  * Returns 1 if it matches, 0 if it doesn't and -1 in case of failure
1007  */
1008 int
1009 xsltTestCompMatchList(xsltTransformContextPtr ctxt, xmlNodePtr node,
1010                       xsltCompMatchPtr comp) {
1011     int ret;
1012
1013     if ((ctxt == NULL) || (node == NULL))
1014         return(-1);
1015     while (comp != NULL) {
1016         ret = xsltTestCompMatch(ctxt, comp, node, NULL, NULL);
1017         if (ret == 1)
1018             return(1);
1019         comp = comp->next;
1020     }
1021     return(0);
1022 }
1023
1024 /************************************************************************
1025  *                                                                      *
1026  *                      Dedicated parser for templates                  *
1027  *                                                                      *
1028  ************************************************************************/
1029
1030 #define CUR (*ctxt->cur)
1031 #define SKIP(val) ctxt->cur += (val)
1032 #define NXT(val) ctxt->cur[(val)]
1033 #define CUR_PTR ctxt->cur
1034
1035 #define SKIP_BLANKS                                                     \
1036     while (IS_BLANK_CH(CUR)) NEXT
1037
1038 #define CURRENT (*ctxt->cur)
1039 #define NEXT ((*ctxt->cur) ?  ctxt->cur++: ctxt->cur)
1040
1041
1042 #define PUSH(op, val, val2)                                             \
1043     if (xsltCompMatchAdd(ctxt, ctxt->comp, (op), (val), (val2))) goto error;
1044
1045 #define SWAP()                                          \
1046     xsltSwapTopCompMatch(ctxt->comp);
1047
1048 #define XSLT_ERROR(X)                                                   \
1049     { xsltError(ctxt, __FILE__, __LINE__, X);                   \
1050       ctxt->error = (X); return; }
1051
1052 #define XSLT_ERROR0(X)                                                  \
1053     { xsltError(ctxt, __FILE__, __LINE__, X);                   \
1054       ctxt->error = (X); return(0); }
1055
1056 /**
1057  * xsltScanLiteral:
1058  * @ctxt:  the XPath Parser context
1059  *
1060  * Parse an XPath Litteral:
1061  *
1062  * [29] Literal ::= '"' [^"]* '"'
1063  *                | "'" [^']* "'"
1064  *
1065  * Returns the Literal parsed or NULL
1066  */
1067
1068 static xmlChar *
1069 xsltScanLiteral(xsltParserContextPtr ctxt) {
1070     const xmlChar *q, *cur;
1071     xmlChar *ret = NULL;
1072     int val, len;
1073
1074     SKIP_BLANKS;
1075     if (CUR == '"') {
1076         NEXT;
1077         cur = q = CUR_PTR;
1078         val = xmlStringCurrentChar(NULL, cur, &len);
1079         while ((IS_CHAR(val)) && (val != '"')) {
1080             cur += len;
1081             val = xmlStringCurrentChar(NULL, cur, &len);
1082         }
1083         if (!IS_CHAR(val)) {
1084             ctxt->error = 1;
1085             return(NULL);
1086         } else {
1087             ret = xmlStrndup(q, cur - q);
1088         }
1089         cur += len;
1090         CUR_PTR = cur;
1091     } else if (CUR == '\'') {
1092         NEXT;
1093         cur = q = CUR_PTR;
1094         val = xmlStringCurrentChar(NULL, cur, &len);
1095         while ((IS_CHAR(val)) && (val != '\'')) {
1096             cur += len;
1097             val = xmlStringCurrentChar(NULL, cur, &len);
1098         }
1099         if (!IS_CHAR(val)) {
1100             ctxt->error = 1;
1101             return(NULL);
1102         } else {
1103             ret = xmlStrndup(q, cur - q);
1104         }
1105         cur += len;
1106         CUR_PTR = cur;
1107     } else {
1108         /* XP_ERROR(XPATH_START_LITERAL_ERROR); */
1109         ctxt->error = 1;
1110         return(NULL);
1111     }
1112     return(ret);
1113 }
1114
1115 /**
1116  * xsltScanName:
1117  * @ctxt:  the XPath Parser context
1118  *
1119  * [4] NameChar ::= Letter | Digit | '.' | '-' | '_' |
1120  *                  CombiningChar | Extender
1121  *
1122  * [5] Name ::= (Letter | '_' | ':') (NameChar)*
1123  *
1124  * [6] Names ::= Name (S Name)*
1125  *
1126  * Returns the Name parsed or NULL
1127  */
1128
1129 static xmlChar *
1130 xsltScanName(xsltParserContextPtr ctxt) {
1131     const xmlChar *q, *cur;
1132     xmlChar *ret = NULL;
1133     int val, len;
1134
1135     SKIP_BLANKS;
1136
1137     cur = q = CUR_PTR;
1138     val = xmlStringCurrentChar(NULL, cur, &len);
1139     if (!IS_LETTER(val) && (val != '_') && (val != ':'))
1140         return(NULL);
1141
1142     while ((IS_LETTER(val)) || (IS_DIGIT(val)) ||
1143            (val == '.') || (val == '-') ||
1144            (val == '_') ||
1145            (IS_COMBINING(val)) ||
1146            (IS_EXTENDER(val))) {
1147         cur += len;
1148         val = xmlStringCurrentChar(NULL, cur, &len);
1149     }
1150     ret = xmlStrndup(q, cur - q);
1151     CUR_PTR = cur;
1152     return(ret);
1153 }
1154
1155 /**
1156  * xsltScanNCName:
1157  * @ctxt:  the XPath Parser context
1158  *
1159  * Parses a non qualified name
1160  *
1161  * Returns the Name parsed or NULL
1162  */
1163
1164 static xmlChar *
1165 xsltScanNCName(xsltParserContextPtr ctxt) {
1166     const xmlChar *q, *cur;
1167     xmlChar *ret = NULL;
1168     int val, len;
1169
1170     SKIP_BLANKS;
1171
1172     cur = q = CUR_PTR;
1173     val = xmlStringCurrentChar(NULL, cur, &len);
1174     if (!IS_LETTER(val) && (val != '_'))
1175         return(NULL);
1176
1177     while ((IS_LETTER(val)) || (IS_DIGIT(val)) ||
1178            (val == '.') || (val == '-') ||
1179            (val == '_') ||
1180            (IS_COMBINING(val)) ||
1181            (IS_EXTENDER(val))) {
1182         cur += len;
1183         val = xmlStringCurrentChar(NULL, cur, &len);
1184     }
1185     ret = xmlStrndup(q, cur - q);
1186     CUR_PTR = cur;
1187     return(ret);
1188 }
1189
1190 /**
1191  * xsltScanQName:
1192  * @ctxt:  the XPath Parser context
1193  * @prefix:  the place to store the prefix
1194  *
1195  * Parse a qualified name
1196  *
1197  * Returns the Name parsed or NULL
1198  */
1199
1200 static xmlChar *
1201 xsltScanQName(xsltParserContextPtr ctxt, xmlChar **prefix) {
1202     xmlChar *ret = NULL;
1203
1204     *prefix = NULL;
1205     ret = xsltScanNCName(ctxt);
1206     if (CUR == ':') {
1207         *prefix = ret;
1208         NEXT;
1209         ret = xsltScanNCName(ctxt);
1210     }
1211     return(ret);
1212 }
1213
1214 /*
1215  * xsltCompileIdKeyPattern:
1216  * @ctxt:  the compilation context
1217  * @name:  a preparsed name
1218  * @aid:  whether id/key are allowed there
1219  *
1220  * Compile the XSLT LocationIdKeyPattern
1221  * [3] IdKeyPattern ::= 'id' '(' Literal ')'
1222  *                    | 'key' '(' Literal ',' Literal ')'
1223  *
1224  * also handle NodeType and PI from:
1225  *
1226  * [7]  NodeTest ::= NameTest
1227  *                 | NodeType '(' ')'
1228  *                 | 'processing-instruction' '(' Literal ')'
1229  */
1230 static void
1231 xsltCompileIdKeyPattern(xsltParserContextPtr ctxt, xmlChar *name, int aid) {
1232     xmlChar *lit = NULL;
1233     xmlChar *lit2 = NULL;
1234
1235     if (CUR != '(') {
1236         xsltTransformError(NULL, NULL, NULL,
1237                 "xsltCompileIdKeyPattern : ( expected\n");
1238         ctxt->error = 1;
1239         return;
1240     }
1241     if ((aid) && (xmlStrEqual(name, (const xmlChar *)"id"))) {
1242         NEXT;
1243         SKIP_BLANKS;
1244         lit = xsltScanLiteral(ctxt);
1245         if (ctxt->error)
1246             return;
1247         SKIP_BLANKS;
1248         if (CUR != ')') {
1249             xsltTransformError(NULL, NULL, NULL,
1250                     "xsltCompileIdKeyPattern : ) expected\n");
1251             ctxt->error = 1;
1252             return;
1253         }
1254         NEXT;
1255         PUSH(XSLT_OP_ID, lit, NULL);
1256     } else if ((aid) && (xmlStrEqual(name, (const xmlChar *)"key"))) {
1257         NEXT;
1258         SKIP_BLANKS;
1259         lit = xsltScanLiteral(ctxt);
1260         if (ctxt->error)
1261             return;
1262         SKIP_BLANKS;
1263         if (CUR != ',') {
1264             xsltTransformError(NULL, NULL, NULL,
1265                     "xsltCompileIdKeyPattern : , expected\n");
1266             ctxt->error = 1;
1267             return;
1268         }
1269         NEXT;
1270         SKIP_BLANKS;
1271         lit2 = xsltScanLiteral(ctxt);
1272         if (ctxt->error)
1273             return;
1274         SKIP_BLANKS;
1275         if (CUR != ')') {
1276             xsltTransformError(NULL, NULL, NULL,
1277                     "xsltCompileIdKeyPattern : ) expected\n");
1278             ctxt->error = 1;
1279             return;
1280         }
1281         NEXT;
1282         /* TODO: support namespace in keys */
1283         PUSH(XSLT_OP_KEY, lit, lit2);
1284     } else if (xmlStrEqual(name, (const xmlChar *)"processing-instruction")) {
1285         NEXT;
1286         SKIP_BLANKS;
1287         if (CUR != ')') {
1288             lit = xsltScanLiteral(ctxt);
1289             if (ctxt->error)
1290                 return;
1291             SKIP_BLANKS;
1292             if (CUR != ')') {
1293                 xsltTransformError(NULL, NULL, NULL,
1294                         "xsltCompileIdKeyPattern : ) expected\n");
1295                 ctxt->error = 1;
1296                 return;
1297             }
1298         }
1299         NEXT;
1300         PUSH(XSLT_OP_PI, lit, NULL);
1301     } else if (xmlStrEqual(name, (const xmlChar *)"text")) {
1302         NEXT;
1303         SKIP_BLANKS;
1304         if (CUR != ')') {
1305             xsltTransformError(NULL, NULL, NULL,
1306                     "xsltCompileIdKeyPattern : ) expected\n");
1307             ctxt->error = 1;
1308             return;
1309         }
1310         NEXT;
1311         PUSH(XSLT_OP_TEXT, NULL, NULL);
1312     } else if (xmlStrEqual(name, (const xmlChar *)"comment")) {
1313         NEXT;
1314         SKIP_BLANKS;
1315         if (CUR != ')') {
1316             xsltTransformError(NULL, NULL, NULL,
1317                     "xsltCompileIdKeyPattern : ) expected\n");
1318             ctxt->error = 1;
1319             return;
1320         }
1321         NEXT;
1322         PUSH(XSLT_OP_COMMENT, NULL, NULL);
1323     } else if (xmlStrEqual(name, (const xmlChar *)"node")) {
1324         NEXT;
1325         SKIP_BLANKS;
1326         if (CUR != ')') {
1327             xsltTransformError(NULL, NULL, NULL,
1328                     "xsltCompileIdKeyPattern : ) expected\n");
1329             ctxt->error = 1;
1330             return;
1331         }
1332         NEXT;
1333         PUSH(XSLT_OP_NODE, NULL, NULL);
1334     } else if (aid) {
1335         xsltTransformError(NULL, NULL, NULL,
1336             "xsltCompileIdKeyPattern : expecting 'key' or 'id' or node type\n");
1337         ctxt->error = 1;
1338         return;
1339     } else {
1340         xsltTransformError(NULL, NULL, NULL,
1341             "xsltCompileIdKeyPattern : node type\n");
1342         ctxt->error = 1;
1343         return;
1344     }
1345 error:
1346     if (name != NULL)
1347         xmlFree(name);
1348 }
1349
1350 /**
1351  * xsltCompileStepPattern:
1352  * @ctxt:  the compilation context
1353  * @token:  a posible precompiled name
1354  *
1355  * Compile the XSLT StepPattern and generates a precompiled
1356  * form suitable for fast matching.
1357  *
1358  * [5] StepPattern ::= ChildOrAttributeAxisSpecifier NodeTest Predicate*
1359  * [6] ChildOrAttributeAxisSpecifier ::= AbbreviatedAxisSpecifier
1360  *                                     | ('child' | 'attribute') '::'
1361  * from XPath
1362  * [7]  NodeTest ::= NameTest
1363  *                 | NodeType '(' ')'
1364  *                 | 'processing-instruction' '(' Literal ')'
1365  * [8] Predicate ::= '[' PredicateExpr ']'
1366  * [9] PredicateExpr ::= Expr
1367  * [13] AbbreviatedAxisSpecifier ::= '@'?
1368  * [37] NameTest ::= '*' | NCName ':' '*' | QName
1369  */
1370
1371 static void
1372 xsltCompileStepPattern(xsltParserContextPtr ctxt, xmlChar *token) {
1373     xmlChar *name = NULL;
1374     const xmlChar *URI = NULL;
1375     xmlChar *URL = NULL;
1376     int level;
1377
1378     SKIP_BLANKS;
1379     if ((token == NULL) && (CUR == '@')) {
1380         xmlChar *prefix = NULL;
1381
1382         NEXT;
1383         if (CUR == '*') {
1384             NEXT;
1385             PUSH(XSLT_OP_ATTR, NULL, NULL);
1386             goto parse_predicate;
1387         }
1388         token = xsltScanQName(ctxt, &prefix);
1389         if (prefix != NULL) {
1390             xmlNsPtr ns;
1391
1392             ns = xmlSearchNs(ctxt->doc, ctxt->elem, prefix);
1393             if (ns == NULL) {
1394                 xsltTransformError(NULL, NULL, NULL,
1395                 "xsltCompileStepPattern : no namespace bound to prefix %s\n",
1396                                  prefix);
1397             } else {
1398                 URL = xmlStrdup(ns->href);
1399             }
1400             xmlFree(prefix);
1401         }
1402         if (token == NULL) {
1403             if (CUR == '*') {
1404                 NEXT;
1405                 PUSH(XSLT_OP_ATTR, NULL, URL);
1406                 return;
1407             }
1408             xsltTransformError(NULL, NULL, NULL,
1409                     "xsltCompileStepPattern : Name expected\n");
1410             ctxt->error = 1;
1411             goto error;
1412         }
1413         PUSH(XSLT_OP_ATTR, token, URL);
1414         goto parse_predicate;
1415     }
1416     if (token == NULL)
1417         token = xsltScanName(ctxt);
1418     if (token == NULL) {
1419         if (CUR == '*') {
1420             NEXT;
1421             PUSH(XSLT_OP_ALL, token, NULL);
1422             goto parse_predicate;
1423         } else {
1424             xsltTransformError(NULL, NULL, NULL,
1425                     "xsltCompileStepPattern : Name expected\n");
1426             ctxt->error = 1;
1427             goto error;
1428         }
1429     }
1430
1431
1432     SKIP_BLANKS;
1433     if (CUR == '(') {
1434         xsltCompileIdKeyPattern(ctxt, token, 0);
1435         if (ctxt->error)
1436             goto error;
1437     } else if (CUR == ':') {
1438         NEXT;
1439         if (CUR != ':') {
1440             xmlChar *prefix = token;
1441             xmlNsPtr ns;
1442
1443             /*
1444              * This is a namespace match
1445              */
1446             token = xsltScanName(ctxt);
1447             ns = xmlSearchNs(ctxt->doc, ctxt->elem, prefix);
1448             if (ns == NULL) {
1449                 xsltTransformError(NULL, NULL, NULL,
1450             "xsltCompileStepPattern : no namespace bound to prefix %s\n",
1451                                  prefix);
1452                 ctxt->error = 1;
1453                 goto error;
1454             } else {
1455                 URL = xmlStrdup(ns->href);
1456             }
1457             xmlFree(prefix);
1458             if (token == NULL) {
1459                 if (CUR == '*') {
1460                     NEXT;
1461                     PUSH(XSLT_OP_NS, URL, NULL);
1462                 } else {
1463                     xsltTransformError(NULL, NULL, NULL,
1464                             "xsltCompileStepPattern : Name expected\n");
1465                     ctxt->error = 1;
1466                     goto error;
1467                 }
1468             } else {
1469                 PUSH(XSLT_OP_ELEM, token, URL);
1470             }
1471         } else {
1472             NEXT;
1473             if (xmlStrEqual(token, (const xmlChar *) "child")) {
1474                 xmlFree(token);
1475                 token = xsltScanName(ctxt);
1476                 if (token == NULL) {
1477                     if (CUR == '*') {
1478                         NEXT;
1479                         PUSH(XSLT_OP_ALL, token, NULL);
1480                         goto parse_predicate;
1481                     } else {
1482                         xsltTransformError(NULL, NULL, NULL,
1483                             "xsltCompileStepPattern : QName expected\n");
1484                         ctxt->error = 1;
1485                         goto error;
1486                     }
1487                 }
1488                 URI = xsltGetQNameURI(ctxt->elem, &token);
1489                 if (token == NULL) {
1490                     ctxt->error = 1;
1491                     goto error;
1492                 } else {
1493                     name = xmlStrdup(token);
1494                     if (URI != NULL)
1495                         URL = xmlStrdup(URI);
1496                 }
1497                 PUSH(XSLT_OP_CHILD, name, URL);
1498             } else if (xmlStrEqual(token, (const xmlChar *) "attribute")) {
1499                 xmlFree(token);
1500                 token = xsltScanName(ctxt);
1501                 if (token == NULL) {
1502                     xsltTransformError(NULL, NULL, NULL,
1503                             "xsltCompileStepPattern : QName expected\n");
1504                     ctxt->error = 1;
1505                     goto error;
1506                 }
1507                 URI = xsltGetQNameURI(ctxt->elem, &token);
1508                 if (token == NULL) {
1509                     ctxt->error = 1;
1510                     goto error;
1511                 } else {
1512                     name = xmlStrdup(token);
1513                     if (URI != NULL)
1514                         URL = xmlStrdup(URI);
1515                 }
1516                 PUSH(XSLT_OP_ATTR, name, URL);
1517             } else {
1518                 xsltTransformError(NULL, NULL, NULL,
1519                     "xsltCompileStepPattern : 'child' or 'attribute' expected\n");
1520                 ctxt->error = 1;
1521                 goto error;
1522             }
1523             xmlFree(token);
1524         }
1525     } else if (CUR == '*') {
1526         NEXT;
1527         PUSH(XSLT_OP_ALL, token, NULL);
1528     } else {
1529         URI = xsltGetQNameURI(ctxt->elem, &token);
1530         if (token == NULL) {
1531             ctxt->error = 1;
1532             goto error;
1533         }
1534         if (URI != NULL)
1535             URL = xmlStrdup(URI);
1536         PUSH(XSLT_OP_ELEM, token, URL);
1537     }
1538 parse_predicate:
1539     SKIP_BLANKS;
1540     level = 0;
1541     while (CUR == '[') {
1542         const xmlChar *q;
1543         xmlChar *ret = NULL;
1544
1545         level++;
1546         NEXT;
1547         q = CUR_PTR;
1548         while (CUR != 0) {
1549             /* Skip over nested predicates */
1550             if (CUR == '[')
1551                 level++;
1552             else if (CUR == ']') {
1553                 level--;
1554                 if (level == 0)
1555                     break;
1556             } else if (CUR == '"') {
1557                 NEXT;
1558                 while ((CUR != 0) && (CUR != '"'))
1559                     NEXT;
1560             } else if (CUR == '\'') {
1561                 NEXT;
1562                 while ((CUR != 0) && (CUR != '\''))
1563                     NEXT;
1564             }
1565             NEXT;
1566         }
1567         if (CUR == 0) {
1568             xsltTransformError(NULL, NULL, NULL,
1569                     "xsltCompileStepPattern : ']' expected\n");
1570             ctxt->error = 1;
1571             return;
1572         }
1573         ret = xmlStrndup(q, CUR_PTR - q);
1574         PUSH(XSLT_OP_PREDICATE, ret, NULL);
1575         /* push the predicate lower than local test */
1576         SWAP();
1577         NEXT;
1578         SKIP_BLANKS;
1579     }
1580     return;
1581 error:
1582     if (token != NULL)
1583         xmlFree(token);
1584     if (name != NULL)
1585         xmlFree(name);
1586 }
1587
1588 /**
1589  * xsltCompileRelativePathPattern:
1590  * @comp:  the compilation context
1591  * @token:  a posible precompiled name
1592  *
1593  * Compile the XSLT RelativePathPattern and generates a precompiled
1594  * form suitable for fast matching.
1595  *
1596  * [4] RelativePathPattern ::= StepPattern
1597  *                           | RelativePathPattern '/' StepPattern
1598  *                           | RelativePathPattern '//' StepPattern
1599  */
1600 static void
1601 xsltCompileRelativePathPattern(xsltParserContextPtr ctxt, xmlChar *token) {
1602     xsltCompileStepPattern(ctxt, token);
1603     if (ctxt->error)
1604         goto error;
1605     SKIP_BLANKS;
1606     while ((CUR != 0) && (CUR != '|')) {
1607         if ((CUR == '/') && (NXT(1) == '/')) {
1608             PUSH(XSLT_OP_ANCESTOR, NULL, NULL);
1609             NEXT;
1610             NEXT;
1611             SKIP_BLANKS;
1612             xsltCompileStepPattern(ctxt, NULL);
1613         } else if (CUR == '/') {
1614             PUSH(XSLT_OP_PARENT, NULL, NULL);
1615             NEXT;
1616             SKIP_BLANKS;
1617             if ((CUR != 0) || (CUR == '|')) {
1618                 xsltCompileRelativePathPattern(ctxt, NULL);
1619             }
1620         } else {
1621             ctxt->error = 1;
1622         }
1623         if (ctxt->error)
1624             goto error;
1625         SKIP_BLANKS;
1626     }
1627 error:
1628     return;
1629 }
1630
1631 /**
1632  * xsltCompileLocationPathPattern:
1633  * @ctxt:  the compilation context
1634  *
1635  * Compile the XSLT LocationPathPattern and generates a precompiled
1636  * form suitable for fast matching.
1637  *
1638  * [2] LocationPathPattern ::= '/' RelativePathPattern?
1639  *                           | IdKeyPattern (('/' | '//') RelativePathPattern)?
1640  *                           | '//'? RelativePathPattern
1641  */
1642 static void
1643 xsltCompileLocationPathPattern(xsltParserContextPtr ctxt) {
1644     SKIP_BLANKS;
1645     if ((CUR == '/') && (NXT(1) == '/')) {
1646         /*
1647          * since we reverse the query
1648          * a leading // can be safely ignored
1649          */
1650         NEXT;
1651         NEXT;
1652         ctxt->comp->priority = 0.5;     /* '//' means not 0 priority */
1653         xsltCompileRelativePathPattern(ctxt, NULL);
1654     } else if (CUR == '/') {
1655         /*
1656          * We need to find root as the parent
1657          */
1658         NEXT;
1659         SKIP_BLANKS;
1660         PUSH(XSLT_OP_ROOT, NULL, NULL);
1661         if ((CUR != 0) || (CUR == '|')) {
1662             PUSH(XSLT_OP_PARENT, NULL, NULL);
1663             xsltCompileRelativePathPattern(ctxt, NULL);
1664         }
1665     } else if (CUR == '*') {
1666         xsltCompileRelativePathPattern(ctxt, NULL);
1667     } else if (CUR == '@') {
1668         xsltCompileRelativePathPattern(ctxt, NULL);
1669     } else {
1670         xmlChar *name;
1671         name = xsltScanName(ctxt);
1672         if (name == NULL) {
1673             xsltTransformError(NULL, NULL, NULL,
1674                     "xsltCompileLocationPathPattern : Name expected\n");
1675             ctxt->error = 1;
1676             return;
1677         }
1678         SKIP_BLANKS;
1679         if ((CUR == '(') && !xmlXPathIsNodeType(name)) {
1680             xsltCompileIdKeyPattern(ctxt, name, 1);
1681             if ((CUR == '/') && (NXT(1) == '/')) {
1682                 PUSH(XSLT_OP_ANCESTOR, NULL, NULL);
1683                 NEXT;
1684                 NEXT;
1685                 SKIP_BLANKS;
1686                 xsltCompileRelativePathPattern(ctxt, NULL);
1687             } else if (CUR == '/') {
1688                 PUSH(XSLT_OP_PARENT, NULL, NULL);
1689                 NEXT;
1690                 SKIP_BLANKS;
1691                 xsltCompileRelativePathPattern(ctxt, NULL);
1692             }
1693             return;
1694         }
1695         xsltCompileRelativePathPattern(ctxt, name);
1696     }
1697 error:
1698     return;
1699 }
1700
1701 /**
1702  * xsltCompilePattern:
1703  * @pattern: an XSLT pattern
1704  * @doc:  the containing document
1705  * @node:  the containing element
1706  * @style:  the stylesheet
1707  * @runtime:  the transformation context, if done at run-time
1708  *
1709  * Compile the XSLT pattern and generates a list of precompiled form suitable
1710  * for fast matching.
1711  *
1712  * [1] Pattern ::= LocationPathPattern | Pattern '|' LocationPathPattern
1713  *
1714  * Returns the generated pattern list or NULL in case of failure
1715  */
1716
1717 xsltCompMatchPtr
1718 xsltCompilePattern(const xmlChar *pattern, xmlDocPtr doc,
1719                    xmlNodePtr node, xsltStylesheetPtr style,
1720                    xsltTransformContextPtr runtime) {
1721     xsltParserContextPtr ctxt = NULL;
1722     xsltCompMatchPtr element, first = NULL, previous = NULL;
1723     int current, start, end, level, j;
1724
1725     if (pattern == NULL) {
1726         xsltTransformError(NULL, NULL, node,
1727                          "xsltCompilePattern : NULL pattern\n");
1728         return(NULL);
1729     }
1730
1731     ctxt = xsltNewParserContext(style, runtime);
1732     if (ctxt == NULL)
1733         return(NULL);
1734     ctxt->doc = doc;
1735     ctxt->elem = node;
1736     current = end = 0;
1737     while (pattern[current] != 0) {
1738         start = current;
1739         while (IS_BLANK_CH(pattern[current]))
1740             current++;
1741         end = current;
1742         level = 0;
1743         while ((pattern[end] != 0) && ((pattern[end] != '|') || (level != 0))) {
1744             if (pattern[end] == '[')
1745                 level++;
1746             else if (pattern[end] == ']')
1747                 level--;
1748             else if (pattern[end] == '\'') {
1749                 end++;
1750                 while ((pattern[end] != 0) && (pattern[end] != '\''))
1751                     end++;
1752             } else if (pattern[end] == '"') {
1753                 end++;
1754                 while ((pattern[end] != 0) && (pattern[end] != '"'))
1755                     end++;
1756             }
1757             end++;
1758         }
1759         if (current == end) {
1760             xsltTransformError(NULL, NULL, node,
1761                              "xsltCompilePattern : NULL pattern\n");
1762             goto error;
1763         }
1764         element = xsltNewCompMatch();
1765         if (element == NULL) {
1766             goto error;
1767         }
1768         if (first == NULL)
1769             first = element;
1770         else if (previous != NULL)
1771             previous->next = element;
1772         previous = element;
1773
1774         ctxt->comp = element;
1775         ctxt->base = xmlStrndup(&pattern[start], end - start);
1776         if (ctxt->base == NULL)
1777             goto error;
1778         ctxt->cur = &(ctxt->base)[current - start];
1779         element->pattern = ctxt->base;
1780         element->nsList = xmlGetNsList(doc, node);
1781         j = 0;
1782         if (element->nsList != NULL) {
1783             while (element->nsList[j] != NULL)
1784                 j++;
1785         }
1786         element->nsNr = j;
1787
1788
1789 #ifdef WITH_XSLT_DEBUG_PATTERN
1790         xsltGenericDebug(xsltGenericDebugContext,
1791                          "xsltCompilePattern : parsing '%s'\n",
1792                          element->pattern);
1793 #endif
1794         /*
1795          Preset default priority to be zero.
1796          This may be changed by xsltCompileLocationPathPattern.
1797          */
1798         element->priority = 0;
1799         xsltCompileLocationPathPattern(ctxt);
1800         if (ctxt->error) {
1801             xsltTransformError(NULL, style, node,
1802                              "xsltCompilePattern : failed to compile '%s'\n",
1803                              element->pattern);
1804             if (style != NULL) style->errors++;
1805             goto error;
1806         }
1807
1808         /*
1809          * Reverse for faster interpretation.
1810          */
1811         xsltReverseCompMatch(element);
1812
1813         /*
1814          * Set-up the priority
1815          */
1816         if (element->priority == 0) {   /* if not yet determined */
1817             if (((element->steps[0].op == XSLT_OP_ELEM) ||
1818                  (element->steps[0].op == XSLT_OP_ATTR) ||
1819                  (element->steps[0].op == XSLT_OP_PI)) &&
1820                 (element->steps[0].value != NULL) &&
1821                 (element->steps[1].op == XSLT_OP_END)) {
1822                 ;       /* previously preset */
1823             } else if ((element->steps[0].op == XSLT_OP_ATTR) &&
1824                        (element->steps[0].value2 != NULL) &&
1825                        (element->steps[1].op == XSLT_OP_END)) {
1826                         element->priority = -0.25;
1827             } else if ((element->steps[0].op == XSLT_OP_NS) &&
1828                        (element->steps[0].value != NULL) &&
1829                        (element->steps[1].op == XSLT_OP_END)) {
1830                         element->priority = -0.25;
1831             } else if ((element->steps[0].op == XSLT_OP_ATTR) &&
1832                        (element->steps[0].value == NULL) &&
1833                        (element->steps[0].value2 == NULL) &&
1834                        (element->steps[1].op == XSLT_OP_END)) {
1835                         element->priority = -0.5;
1836             } else if (((element->steps[0].op == XSLT_OP_PI) ||
1837                        (element->steps[0].op == XSLT_OP_TEXT) ||
1838                        (element->steps[0].op == XSLT_OP_ALL) ||
1839                        (element->steps[0].op == XSLT_OP_NODE) ||
1840                        (element->steps[0].op == XSLT_OP_COMMENT)) &&
1841                        (element->steps[1].op == XSLT_OP_END)) {
1842                         element->priority = -0.5;
1843             } else {
1844                 element->priority = 0.5;
1845             }
1846         }
1847 #ifdef WITH_XSLT_DEBUG_PATTERN
1848         xsltGenericDebug(xsltGenericDebugContext,
1849                      "xsltCompilePattern : parsed %s, default priority %f\n",
1850                          element->pattern, element->priority);
1851 #endif
1852         if (pattern[end] == '|')
1853             end++;
1854         current = end;
1855     }
1856     if (end == 0) {
1857         xsltTransformError(NULL, style, node,
1858                          "xsltCompilePattern : NULL pattern\n");
1859         if (style != NULL) style->errors++;
1860         goto error;
1861     }
1862
1863     xsltFreeParserContext(ctxt);
1864     return(first);
1865
1866 error:
1867     if (ctxt != NULL)
1868         xsltFreeParserContext(ctxt);
1869     if (first != NULL)
1870         xsltFreeCompMatchList(first);
1871     return(NULL);
1872 }
1873
1874 /************************************************************************
1875  *                                                                      *
1876  *                      Module interfaces                               *
1877  *                                                                      *
1878  ************************************************************************/
1879
1880 /**
1881  * xsltAddTemplate:
1882  * @style: an XSLT stylesheet
1883  * @cur: an XSLT template
1884  * @mode:  the mode name or NULL
1885  * @modeURI:  the mode URI or NULL
1886  *
1887  * Register the XSLT pattern associated to @cur
1888  *
1889  * Returns -1 in case of error, 0 otherwise
1890  */
1891 int
1892 xsltAddTemplate(xsltStylesheetPtr style, xsltTemplatePtr cur,
1893                 const xmlChar *mode, const xmlChar *modeURI) {
1894     xsltCompMatchPtr pat, list, *top = NULL, next;
1895     const xmlChar *name = NULL;
1896     float priority;              /* the priority */
1897
1898     if ((style == NULL) || (cur == NULL) || (cur->match == NULL))
1899         return(-1);
1900
1901     priority = cur->priority;
1902     pat = xsltCompilePattern(cur->match, style->doc, cur->elem, style, NULL);
1903     while (pat) {
1904         next = pat->next;
1905         pat->next = NULL;
1906         name = NULL;
1907
1908         pat->template = cur;
1909         if (mode != NULL)
1910             pat->mode = xmlStrdup(mode);
1911         if (modeURI != NULL)
1912             pat->modeURI = xmlStrdup(modeURI);
1913         if (priority != XSLT_PAT_NO_PRIORITY)
1914             pat->priority = priority;
1915
1916         /*
1917          * insert it in the hash table list corresponding to its lookup name
1918          */
1919         switch (pat->steps[0].op) {
1920         case XSLT_OP_ATTR:
1921             if (pat->steps[0].value != NULL)
1922                 name = pat->steps[0].value;
1923             else
1924                 top = (xsltCompMatchPtr *) &(style->attrMatch);
1925             break;
1926         case XSLT_OP_CHILD:
1927         case XSLT_OP_PARENT:
1928         case XSLT_OP_ANCESTOR:
1929             top = (xsltCompMatchPtr *) &(style->elemMatch);
1930             break;
1931         case XSLT_OP_ROOT:
1932             top = (xsltCompMatchPtr *) &(style->rootMatch);
1933             break;
1934         case XSLT_OP_KEY:
1935             top = (xsltCompMatchPtr *) &(style->keyMatch);
1936             break;
1937         case XSLT_OP_ID:
1938             /* TODO optimize ID !!! */
1939         case XSLT_OP_NS:
1940         case XSLT_OP_ALL:
1941             top = (xsltCompMatchPtr *) &(style->elemMatch);
1942             break;
1943         case XSLT_OP_END:
1944         case XSLT_OP_PREDICATE:
1945             xsltTransformError(NULL, style, NULL,
1946                              "xsltAddTemplate: invalid compiled pattern\n");
1947             xsltFreeCompMatch(pat);
1948             return(-1);
1949             /*
1950              * TODO: some flags at the top level about type based patterns
1951              *       would be faster than inclusion in the hash table.
1952              */
1953         case XSLT_OP_PI:
1954             if (pat->steps[0].value != NULL)
1955                 name = pat->steps[0].value;
1956             else
1957                 top = (xsltCompMatchPtr *) &(style->piMatch);
1958             break;
1959         case XSLT_OP_COMMENT:
1960             top = (xsltCompMatchPtr *) &(style->commentMatch);
1961             break;
1962         case XSLT_OP_TEXT:
1963             top = (xsltCompMatchPtr *) &(style->textMatch);
1964             break;
1965         case XSLT_OP_ELEM:
1966         case XSLT_OP_NODE:
1967             if (pat->steps[0].value != NULL)
1968                 name = pat->steps[0].value;
1969             else
1970                 top = (xsltCompMatchPtr *) &(style->elemMatch);
1971             break;
1972         }
1973         if (name != NULL) {
1974             if (style->templatesHash == NULL) {
1975                 style->templatesHash = xmlHashCreate(1024);
1976                 if (style->templatesHash == NULL) {
1977                     xsltFreeCompMatch(pat);
1978                     return(-1);
1979                 }
1980                 xmlHashAddEntry3(style->templatesHash, name, mode, modeURI, pat);
1981             } else {
1982                 list = (xsltCompMatchPtr) xmlHashLookup3(style->templatesHash,
1983                                                          name, mode, modeURI);
1984                 if (list == NULL) {
1985                     xmlHashAddEntry3(style->templatesHash, name,
1986                                      mode, modeURI, pat);
1987                 } else {
1988                     /*
1989                      * Note '<=' since one must choose among the matching
1990                      * template rules that are left, the one that occurs
1991                      * last in the stylesheet
1992                      */
1993                     if (list->priority <= pat->priority) {
1994                         pat->next = list;
1995                         xmlHashUpdateEntry3(style->templatesHash, name,
1996                                             mode, modeURI, pat, NULL);
1997                     } else {
1998                         while (list->next != NULL) {
1999                             if (list->next->priority <= pat->priority)
2000                                 break;
2001                             list = list->next;
2002                         }
2003                         pat->next = list->next;
2004                         list->next = pat;
2005                     }
2006                 }
2007             }
2008         } else if (top != NULL) {
2009             list = *top;
2010             if (list == NULL) {
2011                 *top = pat;
2012                 pat->next = NULL;
2013             } else if (list->priority <= pat->priority) {
2014                 pat->next = list;
2015                 *top = pat;
2016             } else {
2017                 while (list->next != NULL) {
2018                     if (list->next->priority <= pat->priority)
2019                         break;
2020                     list = list->next;
2021                 }
2022                 pat->next = list->next;
2023                 list->next = pat;
2024             }
2025         } else {
2026             xsltTransformError(NULL, style, NULL,
2027                              "xsltAddTemplate: invalid compiled pattern\n");
2028             xsltFreeCompMatch(pat);
2029             return(-1);
2030         }
2031 #ifdef WITH_XSLT_DEBUG_PATTERN
2032         if (mode)
2033             xsltGenericDebug(xsltGenericDebugContext,
2034                          "added pattern : '%s' mode '%s' priority %f\n",
2035                              pat->pattern, pat->mode, pat->priority);
2036         else
2037             xsltGenericDebug(xsltGenericDebugContext,
2038                          "added pattern : '%s' priority %f\n",
2039                              pat->pattern, pat->priority);
2040 #endif
2041
2042         pat = next;
2043     }
2044     return(0);
2045 }
2046
2047 /**
2048  * xsltGetTemplate:
2049  * @ctxt:  a XSLT process context
2050  * @node:  the node being processed
2051  * @style:  the current style
2052  *
2053  * Finds the template applying to this node, if @style is non-NULL
2054  * it means one needs to look for the next imported template in scope.
2055  *
2056  * Returns the xsltTemplatePtr or NULL if not found
2057  */
2058 xsltTemplatePtr
2059 xsltGetTemplate(xsltTransformContextPtr ctxt, xmlNodePtr node,
2060                 xsltStylesheetPtr style) {
2061     xsltStylesheetPtr curstyle;
2062     xsltTemplatePtr ret = NULL;
2063     const xmlChar *name = NULL;
2064     xsltCompMatchPtr list = NULL;
2065     float priority;
2066     int keyed = 0;
2067
2068     if ((ctxt == NULL) || (node == NULL))
2069         return(NULL);
2070
2071     if (style == NULL) {
2072         curstyle = ctxt->style;
2073     } else {
2074         curstyle = xsltNextImport(style);
2075     }
2076
2077     while ((curstyle != NULL) && (curstyle != style)) {
2078         priority = XSLT_PAT_NO_PRIORITY;
2079         /* TODO : handle IDs/keys here ! */
2080         if (curstyle->templatesHash != NULL) {
2081             /*
2082              * Use the top name as selector
2083              */
2084             switch (node->type) {
2085                 case XML_ELEMENT_NODE:
2086                     if (node->name[0] == ' ')
2087                         break;
2088                 case XML_ATTRIBUTE_NODE:
2089                 case XML_PI_NODE:
2090                     name = node->name;
2091                     break;
2092                 case XML_DOCUMENT_NODE:
2093                 case XML_HTML_DOCUMENT_NODE:
2094                 case XML_TEXT_NODE:
2095                 case XML_CDATA_SECTION_NODE:
2096                 case XML_COMMENT_NODE:
2097                 case XML_ENTITY_REF_NODE:
2098                 case XML_ENTITY_NODE:
2099                 case XML_DOCUMENT_TYPE_NODE:
2100                 case XML_DOCUMENT_FRAG_NODE:
2101                 case XML_NOTATION_NODE:
2102                 case XML_DTD_NODE:
2103                 case XML_ELEMENT_DECL:
2104                 case XML_ATTRIBUTE_DECL:
2105                 case XML_ENTITY_DECL:
2106                 case XML_NAMESPACE_DECL:
2107                 case XML_XINCLUDE_START:
2108                 case XML_XINCLUDE_END:
2109                     break;
2110                 default:
2111                     return(NULL);
2112
2113             }
2114         }
2115         if (name != NULL) {
2116             /*
2117              * find the list of appliable expressions based on the name
2118              */
2119             list = (xsltCompMatchPtr) xmlHashLookup3(curstyle->templatesHash,
2120                                              name, ctxt->mode, ctxt->modeURI);
2121         } else
2122             list = NULL;
2123         while (list != NULL) {
2124             if (xsltTestCompMatch(ctxt, list, node,
2125                                   ctxt->mode, ctxt->modeURI)) {
2126                 ret = list->template;
2127                 priority = list->priority;
2128                 break;
2129             }
2130             list = list->next;
2131         }
2132         list = NULL;
2133
2134         /*
2135          * find alternate generic matches
2136          */
2137         switch (node->type) {
2138             case XML_ELEMENT_NODE:
2139                 if (node->name[0] == ' ')
2140                     list = curstyle->rootMatch;
2141                 else
2142                     list = curstyle->elemMatch;
2143                 if (node->psvi != NULL) keyed = 1;
2144                 break;
2145             case XML_ATTRIBUTE_NODE: {
2146                 xmlAttrPtr attr;
2147
2148                 list = curstyle->attrMatch;
2149                 attr = (xmlAttrPtr) node;
2150                 if (attr->psvi != NULL) keyed = 1;
2151                 break;
2152             }
2153             case XML_PI_NODE:
2154                 list = curstyle->piMatch;
2155                 if (node->psvi != NULL) keyed = 1;
2156                 break;
2157             case XML_DOCUMENT_NODE:
2158             case XML_HTML_DOCUMENT_NODE: {
2159                 xmlDocPtr doc;
2160
2161                 list = curstyle->rootMatch;
2162                 doc = (xmlDocPtr) node;
2163                 if (doc->psvi != NULL) keyed = 1;
2164                 break;
2165             }
2166             case XML_TEXT_NODE:
2167             case XML_CDATA_SECTION_NODE:
2168                 list = curstyle->textMatch;
2169                 if (node->psvi != NULL) keyed = 1;
2170                 break;
2171             case XML_COMMENT_NODE:
2172                 list = curstyle->commentMatch;
2173                 if (node->psvi != NULL) keyed = 1;
2174                 break;
2175             case XML_ENTITY_REF_NODE:
2176             case XML_ENTITY_NODE:
2177             case XML_DOCUMENT_TYPE_NODE:
2178             case XML_DOCUMENT_FRAG_NODE:
2179             case XML_NOTATION_NODE:
2180             case XML_DTD_NODE:
2181             case XML_ELEMENT_DECL:
2182             case XML_ATTRIBUTE_DECL:
2183             case XML_ENTITY_DECL:
2184             case XML_NAMESPACE_DECL:
2185             case XML_XINCLUDE_START:
2186             case XML_XINCLUDE_END:
2187                 break;
2188             default:
2189                 break;
2190         }
2191         while ((list != NULL) &&
2192                ((ret == NULL)  || (list->priority > priority))) {
2193             if (xsltTestCompMatch(ctxt, list, node,
2194                                   ctxt->mode, ctxt->modeURI)) {
2195                 ret = list->template;
2196                 priority = list->priority;
2197                 break;
2198             }
2199             list = list->next;
2200         }
2201         /*
2202          * Some of the tests for elements can also apply to documents
2203          */
2204         if ((node->type == XML_DOCUMENT_NODE) ||
2205             (node->type == XML_HTML_DOCUMENT_NODE) ||
2206             (node->type == XML_TEXT_NODE)) {
2207             list = curstyle->elemMatch;
2208             while ((list != NULL) &&
2209                    ((ret == NULL)  || (list->priority > priority))) {
2210                 if (xsltTestCompMatch(ctxt, list, node,
2211                                       ctxt->mode, ctxt->modeURI)) {
2212                     ret = list->template;
2213                     priority = list->priority;
2214                     break;
2215                 }
2216                 list = list->next;
2217             }
2218         } else if ((node->type == XML_PI_NODE) ||
2219                    (node->type == XML_COMMENT_NODE)) {
2220             list = curstyle->elemMatch;
2221             while ((list != NULL) &&
2222                    ((ret == NULL)  || (list->priority > priority))) {
2223                 if (xsltTestCompMatch(ctxt, list, node,
2224                                       ctxt->mode, ctxt->modeURI)) {
2225                     ret = list->template;
2226                     priority = list->priority;
2227                     break;
2228                 }
2229                 list = list->next;
2230             }
2231         }
2232
2233         if (keyed) {
2234             list = curstyle->keyMatch;
2235             while ((list != NULL) &&
2236                    ((ret == NULL)  || (list->priority > priority))) {
2237                 if (xsltTestCompMatch(ctxt, list, node,
2238                                       ctxt->mode, ctxt->modeURI)) {
2239                     ret = list->template;
2240                     priority = list->priority;
2241                     break;
2242                 }
2243                 list = list->next;
2244             }
2245         }
2246         if (ret != NULL)
2247             return(ret);
2248
2249         /*
2250          * Cycle on next curstylesheet import.
2251          */
2252         curstyle = xsltNextImport(curstyle);
2253     }
2254     return(NULL);
2255 }
2256
2257 /**
2258  * xsltCleanupTemplates:
2259  * @style: an XSLT stylesheet
2260  *
2261  * Cleanup the state of the templates used by the stylesheet and
2262  * the ones it imports.
2263  */
2264 void
2265 xsltCleanupTemplates(xsltStylesheetPtr style ATTRIBUTE_UNUSED) {
2266 }
2267
2268 /**
2269  * xsltFreeTemplateHashes:
2270  * @style: an XSLT stylesheet
2271  *
2272  * Free up the memory used by xsltAddTemplate/xsltGetTemplate mechanism
2273  */
2274 void
2275 xsltFreeTemplateHashes(xsltStylesheetPtr style) {
2276     if (style->templatesHash != NULL)
2277         xmlHashFree((xmlHashTablePtr) style->templatesHash,
2278                     (xmlHashDeallocator) xsltFreeCompMatchList);
2279     if (style->rootMatch != NULL)
2280         xsltFreeCompMatchList(style->rootMatch);
2281     if (style->keyMatch != NULL)
2282         xsltFreeCompMatchList(style->keyMatch);
2283     if (style->elemMatch != NULL)
2284         xsltFreeCompMatchList(style->elemMatch);
2285     if (style->attrMatch != NULL)
2286         xsltFreeCompMatchList(style->attrMatch);
2287     if (style->parentMatch != NULL)
2288         xsltFreeCompMatchList(style->parentMatch);
2289     if (style->textMatch != NULL)
2290         xsltFreeCompMatchList(style->textMatch);
2291     if (style->piMatch != NULL)
2292         xsltFreeCompMatchList(style->piMatch);
2293     if (style->commentMatch != NULL)
2294         xsltFreeCompMatchList(style->commentMatch);
2295 }
2296