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