libxslt/pattern.c

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