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