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