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         while (CUR != 0) {
1446             /* Skip over nested predicates */
1447             if (CUR == '[')
1448                 level++;
1449             else if (CUR == ']') {
1450                 level--;
1451                 if (level == 0)
1452                     break;
1453             } else if (CUR == '"') {
1454                 NEXT;
1455                 while ((CUR != 0) && (CUR != '"'))
1456                     NEXT;
1457             } else if (CUR == '\'') {
1458                 NEXT;
1459                 while ((CUR != 0) && (CUR != '\''))
1460                     NEXT;
1461             }
1462             NEXT;
1463         }
1464         if (CUR == 0) {
1465             xsltPrintErrorContext(NULL, NULL, NULL); /* TODO */
1466             xsltGenericError(xsltGenericErrorContext,
1467                     "xsltCompileStepPattern : ']' expected\n");
1468             ctxt->error = 1;
1469             goto error;
1470         }
1471         ret = xmlStrndup(q, CUR_PTR - q);
1472         PUSH(XSLT_OP_PREDICATE, ret, NULL);
1473         /* push the predicate lower than local test */
1474         SWAP();
1475         NEXT;
1476         SKIP_BLANKS;
1477     }
1478     return;
1479 error:
1480     if (token != NULL)
1481         xmlFree(token);
1482     if (name != NULL)
1483         xmlFree(name);
1484 }
1485
1486 /**
1487  * xsltCompileRelativePathPattern:
1488  * @comp:  the compilation context
1489  * @token:  a posible precompiled name
1490  *
1491  * Compile the XSLT RelativePathPattern and generates a precompiled
1492  * form suitable for fast matching.
1493  *
1494  * [4] RelativePathPattern ::= StepPattern
1495  *                           | RelativePathPattern '/' StepPattern
1496  *                           | RelativePathPattern '//' StepPattern
1497  */
1498 static void
1499 xsltCompileRelativePathPattern(xsltParserContextPtr ctxt, xmlChar *token) {
1500     xsltCompileStepPattern(ctxt, token);
1501     if (ctxt->error)
1502         goto error;
1503     SKIP_BLANKS;
1504     while ((CUR != 0) && (CUR != '|')) {
1505         if ((CUR == '/') && (NXT(1) == '/')) {
1506             PUSH(XSLT_OP_ANCESTOR, NULL, NULL);
1507             NEXT;
1508             NEXT;
1509             SKIP_BLANKS;
1510             xsltCompileStepPattern(ctxt, NULL);
1511         } else if (CUR == '/') {
1512             PUSH(XSLT_OP_PARENT, NULL, NULL);
1513             NEXT;
1514             SKIP_BLANKS;
1515             if ((CUR != 0) || (CUR == '|')) {
1516                 xsltCompileRelativePathPattern(ctxt, NULL);
1517             }
1518         } else {
1519             ctxt->error = 1;
1520         }
1521         if (ctxt->error)
1522             goto error;
1523         SKIP_BLANKS;
1524     }
1525 error:
1526     return;
1527 }
1528
1529 /**
1530  * xsltCompileLocationPathPattern:
1531  * @ctxt:  the compilation context
1532  *
1533  * Compile the XSLT LocationPathPattern and generates a precompiled
1534  * form suitable for fast matching.
1535  *
1536  * [2] LocationPathPattern ::= '/' RelativePathPattern?
1537  *                           | IdKeyPattern (('/' | '//') RelativePathPattern)?
1538  *                           | '//'? RelativePathPattern
1539  */
1540 static void
1541 xsltCompileLocationPathPattern(xsltParserContextPtr ctxt) {
1542     SKIP_BLANKS;
1543     if ((CUR == '/') && (NXT(1) == '/')) {
1544         /*
1545          * since we reverse the query
1546          * a leading // can be safely ignored
1547          */
1548         NEXT;
1549         NEXT;
1550         xsltCompileRelativePathPattern(ctxt, NULL);
1551     } else if (CUR == '/') {
1552         /*
1553          * We need to find root as the parent
1554          */
1555         NEXT;
1556         SKIP_BLANKS;
1557         PUSH(XSLT_OP_ROOT, NULL, NULL);
1558         if ((CUR != 0) || (CUR == '|')) {
1559             PUSH(XSLT_OP_PARENT, NULL, NULL);
1560             xsltCompileRelativePathPattern(ctxt, NULL);
1561         }
1562     } else if (CUR == '*') {
1563         xsltCompileRelativePathPattern(ctxt, NULL);
1564     } else if (CUR == '@') {
1565         xsltCompileRelativePathPattern(ctxt, NULL);
1566     } else {
1567         xmlChar *name;
1568         name = xsltScanName(ctxt);
1569         if (name == NULL) {
1570             xsltPrintErrorContext(NULL, NULL, NULL); /* TODO */
1571             xsltGenericError(xsltGenericErrorContext,
1572                     "xsltCompileLocationPathPattern : Name expected\n");
1573             ctxt->error = 1;
1574             return;
1575         }
1576         SKIP_BLANKS;
1577         if ((CUR == '(') && !xmlXPathIsNodeType(name)) {
1578             xsltCompileIdKeyPattern(ctxt, name, 1);
1579             if ((CUR == '/') && (NXT(1) == '/')) {
1580                 PUSH(XSLT_OP_ANCESTOR, NULL, NULL);
1581                 NEXT;
1582                 NEXT;
1583                 SKIP_BLANKS;
1584                 xsltCompileRelativePathPattern(ctxt, NULL);
1585             } else if (CUR == '/') {
1586                 PUSH(XSLT_OP_PARENT, NULL, NULL);
1587                 NEXT;
1588                 SKIP_BLANKS;
1589                 xsltCompileRelativePathPattern(ctxt, NULL);
1590             }
1591             return;
1592         }
1593         xsltCompileRelativePathPattern(ctxt, name);
1594     }
1595 error:
1596     return;
1597 }
1598
1599 /**
1600  * xsltCompilePattern:
1601  * @pattern: an XSLT pattern
1602  * @doc:  the containing document
1603  * @node:  the containing element
1604  * @style:  the stylesheet
1605  * @runtime:  the transformation context, if done at run-time
1606  *
1607  * Compile the XSLT pattern and generates a list of precompiled form suitable
1608  * for fast matching.
1609  *
1610  * [1] Pattern ::= LocationPathPattern | Pattern '|' LocationPathPattern
1611  *
1612  * Returns the generated pattern list or NULL in case of failure
1613  */
1614
1615 xsltCompMatchPtr
1616 xsltCompilePattern(const xmlChar *pattern, xmlDocPtr doc,
1617                    xmlNodePtr node, xsltStylesheetPtr style,
1618                    xsltTransformContextPtr runtime) {
1619     xsltParserContextPtr ctxt = NULL;
1620     xsltCompMatchPtr element, first = NULL, previous = NULL;
1621     int current, start, end, level;
1622
1623     if (pattern == NULL) {
1624         xsltPrintErrorContext(NULL, NULL, node); /* TODO */
1625         xsltGenericError(xsltGenericErrorContext,
1626                          "xsltCompilePattern : NULL pattern\n");
1627         return(NULL);
1628     }
1629
1630     ctxt = xsltNewParserContext(style, runtime);
1631     if (ctxt == NULL)
1632         return(NULL);
1633     ctxt->doc = doc;
1634     ctxt->elem = node;
1635     current = end = 0;
1636     while (pattern[current] != 0) {
1637         start = current;
1638         while (IS_BLANK(pattern[current]))
1639             current++;
1640         end = current;
1641         level = 0;
1642         while ((pattern[end] != 0) && ((pattern[end] != '|') || (level != 0))) {
1643             if (pattern[end] == '[')
1644                 level++;
1645             else if (pattern[end] == ']')
1646                 level--;
1647             else if (pattern[end] == '\'') {
1648                 end++;
1649                 while ((pattern[end] != 0) && (pattern[end] != '\''))
1650                     end++;
1651             } else if (pattern[end] == '"') {
1652                 end++;
1653                 while ((pattern[end] != 0) && (pattern[end] != '"'))
1654                     end++;
1655             }
1656             end++;
1657         }
1658         if (current == end) {
1659             xsltPrintErrorContext(NULL, NULL, node); /* TODO */
1660             xsltGenericError(xsltGenericErrorContext,
1661                              "xsltCompilePattern : NULL pattern\n");
1662             goto error;
1663         }
1664         element = xsltNewCompMatch();
1665         if (element == NULL) {
1666             goto error;
1667         }
1668         if (first == NULL)
1669             first = element;
1670         else if (previous != NULL)
1671             previous->next = element;
1672         previous = element;
1673
1674         ctxt->comp = element;
1675         ctxt->base = xmlStrndup(&pattern[start], end - start);
1676         if (ctxt->base == NULL)
1677             goto error;
1678         ctxt->cur = &(ctxt->base)[current - start];
1679         element->pattern = ctxt->base;
1680
1681 #ifdef WITH_XSLT_DEBUG_PATTERN
1682         xsltGenericDebug(xsltGenericDebugContext,
1683                          "xsltCompilePattern : parsing '%s'\n",
1684                          element->pattern);
1685 #endif
1686         xsltCompileLocationPathPattern(ctxt);
1687         if (ctxt->error)
1688             goto error;
1689
1690         /*
1691          * Reverse for faster interpretation.
1692          */
1693         xsltReverseCompMatch(element);
1694
1695         /*
1696          * Set-up the priority
1697          */
1698         if (((element->steps[0].op == XSLT_OP_ELEM) ||
1699              (element->steps[0].op == XSLT_OP_ATTR)) &&
1700             (element->steps[0].value != NULL) &&
1701             (element->steps[1].op == XSLT_OP_END)) {
1702             element->priority = 0;
1703 #if 0
1704         } else if ((element->steps[0].op == XSLT_OP_ROOT) &&
1705                    (element->steps[1].op == XSLT_OP_END)) {
1706             element->priority = 0;
1707 #endif
1708         } else if ((element->steps[0].op == XSLT_OP_PI) &&
1709                    (element->steps[0].value != NULL) &&
1710                    (element->steps[1].op == XSLT_OP_END)) {
1711             element->priority = 0;
1712         } else if ((element->steps[0].op == XSLT_OP_ATTR) &&
1713                    (element->steps[0].value2 != NULL) &&
1714                    (element->steps[1].op == XSLT_OP_END)) {
1715             element->priority = -0.25;
1716         } else if ((element->steps[0].op == XSLT_OP_NS) &&
1717                    (element->steps[0].value != NULL) &&
1718                    (element->steps[1].op == XSLT_OP_END)) {
1719             element->priority = -0.25;
1720         } else if ((element->steps[0].op == XSLT_OP_ATTR) &&
1721                    (element->steps[0].value == NULL) &&
1722                    (element->steps[0].value2 == NULL) &&
1723                    (element->steps[1].op == XSLT_OP_END)) {
1724             element->priority = -0.5;
1725         } else if (((element->steps[0].op == XSLT_OP_PI) ||
1726                     (element->steps[0].op == XSLT_OP_TEXT) ||
1727                     (element->steps[0].op == XSLT_OP_ALL) ||
1728                     (element->steps[0].op == XSLT_OP_NODE) ||
1729                     (element->steps[0].op == XSLT_OP_COMMENT)) &&
1730                    (element->steps[1].op == XSLT_OP_END)) {
1731             element->priority = -0.5;
1732         } else {
1733             element->priority = 0.5;
1734         }
1735 #ifdef WITH_XSLT_DEBUG_PATTERN
1736         xsltGenericDebug(xsltGenericDebugContext,
1737                      "xsltCompilePattern : parsed %s, default priority %f\n",
1738                          element->pattern, element->priority);
1739 #endif
1740         if (pattern[end] == '|')
1741             end++;
1742         current = end;
1743     }
1744     if (end == 0) {
1745         xsltPrintErrorContext(NULL, NULL, node); /* TODO */
1746         xsltGenericError(xsltGenericErrorContext,
1747                          "xsltCompilePattern : NULL pattern\n");
1748         goto error;
1749     }
1750
1751     xsltFreeParserContext(ctxt);
1752     return(first);
1753
1754 error:
1755     if (ctxt != NULL)
1756         xsltFreeParserContext(ctxt);
1757     if (first != NULL)
1758         xsltFreeCompMatchList(first);
1759     return(NULL);
1760 }
1761
1762 /************************************************************************
1763  *                                                                      *
1764  *                      Module interfaces                               *
1765  *                                                                      *
1766  ************************************************************************/
1767
1768 /**
1769  * xsltAddTemplate:
1770  * @style: an XSLT stylesheet
1771  * @cur: an XSLT template
1772  * @mode:  the mode name or NULL
1773  * @modeURI:  the mode URI or NULL
1774  *
1775  * Register the XSLT pattern associated to @cur
1776  *
1777  * Returns -1 in case of error, 0 otherwise
1778  */
1779 int
1780 xsltAddTemplate(xsltStylesheetPtr style, xsltTemplatePtr cur,
1781                 const xmlChar *mode, const xmlChar *modeURI) {
1782     xsltCompMatchPtr pat, list, *top = NULL, next;
1783     const xmlChar *name = NULL;
1784     float priority;              /* the priority */
1785
1786     if ((style == NULL) || (cur == NULL) || (cur->match == NULL))
1787         return(-1);
1788
1789     priority = cur->priority;
1790     pat = xsltCompilePattern(cur->match, style->doc, cur->elem, style, NULL);
1791     while (pat) {
1792         next = pat->next;
1793         pat->next = NULL;
1794         name = NULL;
1795
1796         pat->template = cur;
1797         if (mode != NULL)
1798             pat->mode = xmlStrdup(mode);
1799         if (modeURI != NULL)
1800             pat->modeURI = xmlStrdup(modeURI);
1801         if (priority != XSLT_PAT_NO_PRIORITY)
1802             pat->priority = priority;
1803
1804         /*
1805          * insert it in the hash table list corresponding to its lookup name
1806          */
1807         switch (pat->steps[0].op) {
1808         case XSLT_OP_ATTR:
1809             if (pat->steps[0].value != NULL)
1810                 name = pat->steps[0].value;
1811             else
1812                 top = (xsltCompMatchPtr *) &(style->attrMatch);
1813             break;
1814         case XSLT_OP_ELEM:
1815         case XSLT_OP_CHILD:
1816         case XSLT_OP_PARENT:
1817         case XSLT_OP_ANCESTOR:
1818             top = (xsltCompMatchPtr *) &(style->elemMatch);
1819             break;
1820         case XSLT_OP_ROOT:
1821             top = (xsltCompMatchPtr *) &(style->rootMatch);
1822             break;
1823         case XSLT_OP_KEY:
1824             top = (xsltCompMatchPtr *) &(style->keyMatch);
1825             break;
1826         case XSLT_OP_ID:
1827             /* TODO optimize ID !!! */
1828         case XSLT_OP_NS:
1829         case XSLT_OP_ALL:
1830             top = (xsltCompMatchPtr *) &(style->elemMatch);
1831             break;
1832         case XSLT_OP_END:
1833         case XSLT_OP_PREDICATE:
1834             xsltPrintErrorContext(NULL, style, NULL);
1835             xsltGenericError(xsltGenericErrorContext,
1836                              "xsltAddTemplate: invalid compiled pattern\n");
1837             xsltFreeCompMatch(pat);
1838             return(-1);
1839             /*
1840              * TODO: some flags at the top level about type based patterns
1841              *       would be faster than inclusion in the hash table.
1842              */
1843         case XSLT_OP_PI:
1844             if (pat->steps[0].value != NULL)
1845                 name = pat->steps[0].value;
1846             else
1847                 top = (xsltCompMatchPtr *) &(style->piMatch);
1848             break;
1849         case XSLT_OP_COMMENT:
1850             top = (xsltCompMatchPtr *) &(style->commentMatch);
1851             break;
1852         case XSLT_OP_TEXT:
1853             top = (xsltCompMatchPtr *) &(style->textMatch);
1854             break;
1855         case XSLT_OP_NODE:
1856             if (pat->steps[0].value != NULL)
1857                 name = pat->steps[0].value;
1858             else
1859                 top = (xsltCompMatchPtr *) &(style->elemMatch);
1860
1861             break;
1862         }
1863         if (name != NULL) {
1864             if (style->templatesHash == NULL) {
1865                 style->templatesHash = xmlHashCreate(1024);
1866                 if (style->templatesHash == NULL) {
1867                     xsltFreeCompMatch(pat);
1868                     return(-1);
1869                 }
1870                 xmlHashAddEntry3(style->templatesHash, name, mode, modeURI, pat);
1871             } else {
1872                 list = (xsltCompMatchPtr) xmlHashLookup3(style->templatesHash,
1873                                                          name, mode, modeURI);
1874                 if (list == NULL) {
1875                     xmlHashAddEntry3(style->templatesHash, name,
1876                                      mode, modeURI, pat);
1877                 } else {
1878                     /*
1879                      * Note '<=' since one must choose among the matching
1880                      * template rules that are left, the one that occurs
1881                      * last in the stylesheet
1882                      */
1883                     if (list->priority <= pat->priority) {
1884                         pat->next = list;
1885                         xmlHashUpdateEntry3(style->templatesHash, name,
1886                                             mode, modeURI, pat, NULL);
1887                     } else {
1888                         while (list->next != NULL) {
1889                             if (list->next->priority <= pat->priority)
1890                                 break;
1891                             list = list->next;
1892                         }
1893                         pat->next = list->next;
1894                         list->next = pat;
1895                     }
1896                 }
1897             }
1898         } else if (top != NULL) {
1899             list = *top;
1900             if (list == NULL) {
1901                 *top = pat;
1902                 pat->next = NULL;
1903             } else if (list->priority <= pat->priority) {
1904                 pat->next = list;
1905                 *top = pat;
1906             } else {
1907                 while (list->next != NULL) {
1908                     if (list->next->priority <= pat->priority)
1909                         break;
1910                     list = list->next;
1911                 }
1912                 pat->next = list->next;
1913                 list->next = pat;
1914             }
1915         } else {
1916             xsltPrintErrorContext(NULL, style, NULL);
1917             xsltGenericError(xsltGenericErrorContext,
1918                              "xsltAddTemplate: invalid compiled pattern\n");
1919             xsltFreeCompMatch(pat);
1920             return(-1);
1921         }
1922 #ifdef WITH_XSLT_DEBUG_PATTERN
1923         if (mode)
1924             xsltGenericDebug(xsltGenericDebugContext,
1925                          "added pattern : '%s' mode '%s' priority %f\n",
1926                              pat->pattern, pat->mode, pat->priority);
1927         else
1928             xsltGenericDebug(xsltGenericDebugContext,
1929                          "added pattern : '%s' priority %f\n",
1930                              pat->pattern, pat->priority);
1931 #endif
1932
1933         pat = next;
1934     }
1935     return(0);
1936 }
1937
1938 /**
1939  * xsltGetTemplate:
1940  * @ctxt:  a XSLT process context
1941  * @node:  the node being processed
1942  * @style:  the current style
1943  *
1944  * Finds the template applying to this node, if @style is non-NULL
1945  * it means one needs to look for the next imported template in scope.
1946  *
1947  * Returns the xsltTemplatePtr or NULL if not found
1948  */
1949 xsltTemplatePtr
1950 xsltGetTemplate(xsltTransformContextPtr ctxt, xmlNodePtr node,
1951                 xsltStylesheetPtr style) {
1952     xsltStylesheetPtr curstyle;
1953     xsltTemplatePtr ret = NULL;
1954     const xmlChar *name = NULL;
1955     xsltCompMatchPtr list = NULL;
1956     float priority;
1957
1958     if ((ctxt == NULL) || (node == NULL))
1959         return(NULL);
1960
1961     if (style == NULL) {
1962         curstyle = ctxt->style;
1963     } else {
1964         curstyle = xsltNextImport(style);
1965     }
1966
1967     while ((curstyle != NULL) && (curstyle != style)) {
1968         priority = XSLT_PAT_NO_PRIORITY;
1969         /* TODO : handle IDs/keys here ! */
1970         if (curstyle->templatesHash != NULL) {
1971             /*
1972              * Use the top name as selector
1973              */
1974             switch (node->type) {
1975                 case XML_ELEMENT_NODE:
1976                 case XML_ATTRIBUTE_NODE:
1977                 case XML_PI_NODE:
1978                     name = node->name;
1979                     break;
1980                 case XML_DOCUMENT_NODE:
1981                 case XML_HTML_DOCUMENT_NODE:
1982                 case XML_TEXT_NODE:
1983                 case XML_CDATA_SECTION_NODE:
1984                 case XML_COMMENT_NODE:
1985                 case XML_ENTITY_REF_NODE:
1986                 case XML_ENTITY_NODE:
1987                 case XML_DOCUMENT_TYPE_NODE:
1988                 case XML_DOCUMENT_FRAG_NODE:
1989                 case XML_NOTATION_NODE:
1990                 case XML_DTD_NODE:
1991                 case XML_ELEMENT_DECL:
1992                 case XML_ATTRIBUTE_DECL:
1993                 case XML_ENTITY_DECL:
1994                 case XML_NAMESPACE_DECL:
1995                 case XML_XINCLUDE_START:
1996                 case XML_XINCLUDE_END:
1997                     break;
1998                 default:
1999                     return(NULL);
2000
2001             }
2002         }
2003         if (name != NULL) {
2004             /*
2005              * find the list of appliable expressions based on the name
2006              */
2007             list = (xsltCompMatchPtr) xmlHashLookup3(curstyle->templatesHash,
2008                                              name, ctxt->mode, ctxt->modeURI);
2009         } else
2010             list = NULL;
2011         while (list != NULL) {
2012             if (xsltTestCompMatch(ctxt, list, node,
2013                                   ctxt->mode, ctxt->modeURI)) {
2014                 ret = list->template;
2015                 priority = list->priority;
2016                 break;
2017             }
2018             list = list->next;
2019         }
2020         list = NULL;
2021
2022         /*
2023          * find alternate generic matches
2024          */
2025         switch (node->type) {
2026             case XML_ELEMENT_NODE:
2027                 list = curstyle->elemMatch;
2028                 break;
2029             case XML_ATTRIBUTE_NODE:
2030                 list = curstyle->attrMatch;
2031                 break;
2032             case XML_PI_NODE:
2033                 list = curstyle->piMatch;
2034                 break;
2035             case XML_DOCUMENT_NODE:
2036             case XML_HTML_DOCUMENT_NODE:
2037                 list = curstyle->rootMatch;
2038                 break;
2039             case XML_TEXT_NODE:
2040             case XML_CDATA_SECTION_NODE:
2041                 list = curstyle->textMatch;
2042                 break;
2043             case XML_COMMENT_NODE:
2044                 list = curstyle->commentMatch;
2045                 break;
2046             case XML_ENTITY_REF_NODE:
2047             case XML_ENTITY_NODE:
2048             case XML_DOCUMENT_TYPE_NODE:
2049             case XML_DOCUMENT_FRAG_NODE:
2050             case XML_NOTATION_NODE:
2051             case XML_DTD_NODE:
2052             case XML_ELEMENT_DECL:
2053             case XML_ATTRIBUTE_DECL:
2054             case XML_ENTITY_DECL:
2055             case XML_NAMESPACE_DECL:
2056             case XML_XINCLUDE_START:
2057             case XML_XINCLUDE_END:
2058                 break;
2059             default:
2060                 break;
2061
2062         }
2063         while ((list != NULL) &&
2064                ((ret == NULL)  || (list->priority > priority))) {
2065             if (xsltTestCompMatch(ctxt, list, node,
2066                                   ctxt->mode, ctxt->modeURI)) {
2067                 ret = list->template;
2068                 priority = list->priority;
2069                 break;
2070             }
2071             list = list->next;
2072         }
2073         /*
2074          * Some of the tests for elements can also apply to documents
2075          */
2076         if ((node->type == XML_DOCUMENT_NODE) ||
2077             (node->type == XML_HTML_DOCUMENT_NODE)) {
2078             list = curstyle->elemMatch;
2079             while ((list != NULL) &&
2080                    ((ret == NULL)  || (list->priority > priority))) {
2081                 if (xsltTestCompMatch(ctxt, list, node,
2082                                       ctxt->mode, ctxt->modeURI)) {
2083                     ret = list->template;
2084                     priority = list->priority;
2085                     break;
2086                 }
2087                 list = list->next;
2088             }
2089         }
2090
2091         if (node->_private != NULL) {
2092             list = curstyle->keyMatch;
2093             while ((list != NULL) &&
2094                    ((ret == NULL)  || (list->priority > priority))) {
2095                 if (xsltTestCompMatch(ctxt, list, node,
2096                                       ctxt->mode, ctxt->modeURI)) {
2097                     ret = list->template;
2098                     priority = list->priority;
2099                     break;
2100                 }
2101                 list = list->next;
2102             }
2103         }
2104         if (ret != NULL)
2105             return(ret);
2106
2107         /*
2108          * Cycle on next curstylesheet import.
2109          */
2110         curstyle = xsltNextImport(curstyle);
2111     }
2112     return(NULL);
2113 }
2114
2115 /**
2116  * xsltCleanupTemplates:
2117  * @style: an XSLT stylesheet
2118  *
2119  * Cleanup the state of the templates used by the stylesheet and
2120  * the ones it imports.
2121  */
2122 void
2123 xsltCleanupTemplates(xsltStylesheetPtr style ATTRIBUTE_UNUSED) {
2124 }
2125
2126 /**
2127  * xsltFreeTemplateHashes:
2128  * @style: an XSLT stylesheet
2129  *
2130  * Free up the memory used by xsltAddTemplate/xsltGetTemplate mechanism
2131  */
2132 void
2133 xsltFreeTemplateHashes(xsltStylesheetPtr style) {
2134     if (style->templatesHash != NULL)
2135         xmlHashFree((xmlHashTablePtr) style->templatesHash,
2136                     (xmlHashDeallocator) xsltFreeCompMatchList);
2137     if (style->rootMatch != NULL)
2138         xsltFreeCompMatchList(style->rootMatch);
2139     if (style->keyMatch != NULL)
2140         xsltFreeCompMatchList(style->keyMatch);
2141     if (style->elemMatch != NULL)
2142         xsltFreeCompMatchList(style->elemMatch);
2143     if (style->attrMatch != NULL)
2144         xsltFreeCompMatchList(style->attrMatch);
2145     if (style->parentMatch != NULL)
2146         xsltFreeCompMatchList(style->parentMatch);
2147     if (style->textMatch != NULL)
2148         xsltFreeCompMatchList(style->textMatch);
2149     if (style->piMatch != NULL)
2150         xsltFreeCompMatchList(style->piMatch);
2151     if (style->commentMatch != NULL)
2152         xsltFreeCompMatchList(style->commentMatch);
2153 }
2154
2155 #if 0
2156 /**
2157  * xsltMatchPattern
2158  * @node: a node in the source tree
2159  * @pattern: an XSLT pattern
2160  * @ctxtdoc:  context document (for namespaces)
2161  * @ctxtnode:  context node (for namespaces)
2162  *
2163  * Determine if a node matches a pattern.
2164  */
2165 int
2166 xsltMatchPattern(xsltTransformContextPtr context,
2167                  xmlNodePtr node,
2168                  const xmlChar *pattern,
2169                  xmlDocPtr ctxtdoc,
2170                  xmlNodePtr ctxtnode)
2171 {
2172     int match = 0;
2173     xsltCompMatchPtr first, comp;
2174
2175     if ((context != NULL) && (pattern != NULL)) {
2176         first = xsltCompilePattern(pattern, ctxtdoc, ctxtnode);
2177         for (comp = first; comp != NULL; comp = comp->next) {
2178             match = xsltTestCompMatch(context, comp, node, NULL, NULL);
2179             if (match)
2180                 break; /* for */
2181         }
2182         if (first)
2183             xsltFreeCompMatchList(first);
2184     }
2185     return match;
2186 }
2187 #endif