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