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