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