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@imag.fr
  10  */
  11
  12 #include "xsltconfig.h"
  13
  14 #include <string.h>
  15
  16 #include <libxml/xmlmemory.h>
  17 #include <libxml/tree.h>
  18 #include <libxml/valid.h>
  19 #include <libxml/hash.h>
  20 #include <libxml/xmlerror.h>
  21 #include <libxml/parserInternals.h>
  22 #include "xslt.h"
  23 #include "xsltInternals.h"
  24 #include "xsltutils.h"
  25 #include "imports.h"
  26 #include "templates.h"
  27 #include "pattern.h"
  28
  29 /* #define DEBUG_PARSING */
  30
  31 /*
  32  * Types are private:
  33  */
  34
  35 typedef enum {
  36     XSLT_OP_END=0,
  37     XSLT_OP_ROOT,
  38     XSLT_OP_ELEM,
  39     XSLT_OP_CHILD,
  40     XSLT_OP_ATTR,
  41     XSLT_OP_PARENT,
  42     XSLT_OP_ANCESTOR,
  43     XSLT_OP_ID,
  44     XSLT_OP_KEY,
  45     XSLT_OP_NS,
  46     XSLT_OP_ALL,
  47     XSLT_OP_PI,
  48     XSLT_OP_COMMENT,
  49     XSLT_OP_TEXT,
  50     XSLT_OP_NODE,
  51     XSLT_OP_PREDICATE
  52 } xsltOp;
  53
  54
  55 typedef struct _xsltStepOp xsltStepOp;
  56 typedef xsltStepOp *xsltStepOpPtr;
  57 struct _xsltStepOp {
  58     xsltOp op;
  59     xmlChar *value;
  60     xmlChar *value2;
  61 };
  62
  63 typedef struct _xsltCompMatch xsltCompMatch;
  64 typedef xsltCompMatch *xsltCompMatchPtr;
  65 struct _xsltCompMatch {
  66     struct _xsltCompMatch *next; /* siblings in the name hash */
  67     float priority;              /* the priority */
  68     const xmlChar *mode;         /* the mode */
  69     const xmlChar *modeURI;      /* the mode URI */
  70     xsltTemplatePtr template;    /* the associated template */
  71
  72     /* TODO fix the statically allocated size steps[] */
  73     int nbStep;
  74     int maxStep;
  75     xsltStepOp steps[20];        /* ops for computation */
  76 };
  77
  78 typedef struct _xsltParserContext xsltParserContext;
  79 typedef xsltParserContext *xsltParserContextPtr;
  80 struct _xsltParserContext {
  81     const xmlChar *cur;                 /* the current char being parsed */
  82     const xmlChar *base;                /* the full expression */
  83     int error;                          /* error code */
  84     xsltCompMatchPtr comp;              /* the result */
  85 };
  86
  87 /************************************************************************
  88  *                                                                      *
  89  *                      Type functions                                  *
  90  *                                                                      *
  91  ************************************************************************/
  92
  93 /**
  94  * xsltNewCompMatch:
  95  * @mode:  the mode name or NULL
  96  * @modeURI:  the mode URI or NULL
  97  *
  98  * Create a new XSLT CompMatch
  99  *
 100  * Returns the newly allocated xsltCompMatchPtr or NULL in case of error
 101  */
 102 xsltCompMatchPtr
 103 xsltNewCompMatch(const xmlChar *mode, const xmlChar *modeURI) {
 104     xsltCompMatchPtr cur;
 105
 106     cur = (xsltCompMatchPtr) xmlMalloc(sizeof(xsltCompMatch));
 107     if (cur == NULL) {
 108         xsltGenericError(xsltGenericErrorContext,
 109                 "xsltNewCompMatch : malloc failed\n");
 110         return(NULL);
 111     }
 112     memset(cur, 0, sizeof(xsltCompMatch));
 113     cur->maxStep = 20;
 114     cur->mode = xmlStrdup(mode);
 115     cur->modeURI = xmlStrdup(modeURI);
 116     return(cur);
 117 }
 118
 119 /**
 120  * xsltFreeCompMatch:
 121  * @comp:  an XSLT comp
 122  *
 123  * Free up the memory allocated by @comp
 124  */
 125 void
 126 xsltFreeCompMatch(xsltCompMatchPtr comp) {
 127     xsltStepOpPtr op;
 128     int i;
 129
 130     if (comp == NULL)
 131         return;
 132     if (comp->mode != NULL)
 133         xmlFree((xmlChar *)comp->mode);
 134     if (comp->modeURI != NULL)
 135         xmlFree((xmlChar *)comp->modeURI);
 136     for (i = 0;i < comp->nbStep;i++) {
 137         op = &comp->steps[i];
 138         if (op->value != NULL)
 139             xmlFree(op->value);
 140         if (op->value2 != NULL)
 141             xmlFree(op->value2);
 142     }
 143     memset(comp, -1, sizeof(xsltCompMatch));
 144     xmlFree(comp);
 145 }
 146
 147 /**
 148  * xsltFreeCompMatchList:
 149  * @comp:  an XSLT comp list
 150  *
 151  * Free up the memory allocated by all the elements of @comp
 152  */
 153 void
 154 xsltFreeCompMatchList(xsltCompMatchPtr comp) {
 155     xsltCompMatchPtr cur;
 156
 157     while (comp != NULL) {
 158         cur = comp;
 159         comp = comp->next;
 160         xsltFreeCompMatch(cur);
 161     }
 162 }
 163
 164 /**
 165  * xsltNewParserContext:
 166  *
 167  * Create a new XSLT ParserContext
 168  *
 169  * Returns the newly allocated xsltParserContextPtr or NULL in case of error
 170  */
 171 xsltParserContextPtr
 172 xsltNewParserContext(void) {
 173     xsltParserContextPtr cur;
 174
 175     cur = (xsltParserContextPtr) xmlMalloc(sizeof(xsltParserContext));
 176     if (cur == NULL) {
 177         xsltGenericError(xsltGenericErrorContext,
 178                 "xsltNewParserContext : malloc failed\n");
 179         return(NULL);
 180     }
 181     memset(cur, 0, sizeof(xsltParserContext));
 182     return(cur);
 183 }
 184
 185 /**
 186  * xsltFreeParserContext:
 187  * @ctxt:  an XSLT parser context
 188  *
 189  * Free up the memory allocated by @ctxt
 190  */
 191 void
 192 xsltFreeParserContext(xsltParserContextPtr ctxt) {
 193     if (ctxt == NULL)
 194         return;
 195     memset(ctxt, -1, sizeof(xsltParserContext));
 196     xmlFree(ctxt);
 197 }
 198
 199 /**
 200  * xsltCompMatchAdd:
 201  * @comp:  the compiled match expression
 202  * @op:  an op
 203  * @value:  the first value
 204  * @value2:  the second value
 205  *
 206  * Add an step to an XSLT Compiled Match
 207  *
 208  * Returns -1 in case of failure, 0 otherwise.
 209  */
 210 int
 211 xsltCompMatchAdd(xsltCompMatchPtr comp, xsltOp op, xmlChar *value,
 212                    xmlChar *value2) {
 213     if (comp->nbStep >= 20) {
 214         xsltGenericError(xsltGenericErrorContext,
 215                 "xsltCompMatchAddOp: overflow\n");
 216         return(-1);
 217     }
 218     comp->steps[comp->nbStep].op = op;
 219     comp->steps[comp->nbStep].value = value;
 220     comp->steps[comp->nbStep].value2 = value2;
 221     comp->nbStep++;
 222     return(0);
 223 }
 224
 225 /**
 226  * xsltSwapTopCompMatch:
 227  * @comp:  the compiled match expression
 228  *
 229  * reverse the two top steps.
 230  */
 231 void
 232 xsltSwapTopCompMatch(xsltCompMatchPtr comp) {
 233     int i;
 234     int j = comp->nbStep - 1;
 235
 236     if (j > 0) {
 237         register xmlChar *tmp;
 238         register xsltOp op;
 239         i = j - 1;
 240         tmp = comp->steps[i].value;
 241         comp->steps[i].value = comp->steps[j].value;
 242         comp->steps[j].value = tmp;
 243         tmp = comp->steps[i].value2;
 244         comp->steps[i].value2 = comp->steps[j].value2;
 245         comp->steps[j].value2 = tmp;
 246         op = comp->steps[i].op;
 247         comp->steps[i].op = comp->steps[j].op;
 248         comp->steps[j].op = op;
 249     }
 250 }
 251
 252 /**
 253  * xsltReverseCompMatch:
 254  * @comp:  the compiled match expression
 255  *
 256  * reverse all the stack of expressions
 257  */
 258 void
 259 xsltReverseCompMatch(xsltCompMatchPtr comp) {
 260     int i = 0;
 261     int j = comp->nbStep - 1;
 262
 263     while (j > i) {
 264         register xmlChar *tmp;
 265         register xsltOp op;
 266         tmp = comp->steps[i].value;
 267         comp->steps[i].value = comp->steps[j].value;
 268         comp->steps[j].value = tmp;
 269         tmp = comp->steps[i].value2;
 270         comp->steps[i].value2 = comp->steps[j].value2;
 271         comp->steps[j].value2 = tmp;
 272         op = comp->steps[i].op;
 273         comp->steps[i].op = comp->steps[j].op;
 274         comp->steps[j].op = op;
 275         j--;
 276         i++;
 277     }
 278     comp->steps[comp->nbStep++].op = XSLT_OP_END;
 279 }
 280
 281 /************************************************************************
 282  *                                                                      *
 283  *              The interpreter for the precompiled patterns            *
 284  *                                                                      *
 285  ************************************************************************/
 286
 287 /**
 288  * xsltTestCompMatch:
 289  * @ctxt:  a XSLT process context
 290  * @comp: the precompiled pattern
 291  * @node: a node
 292  * @mode:  the mode name or NULL
 293  * @modeURI:  the mode URI or NULL
 294  *
 295  * Test wether the node matches the pattern
 296  *
 297  * Returns 1 if it matches, 0 if it doesn't and -1 in case of failure
 298  */
 299 int
 300 xsltTestCompMatch(xsltTransformContextPtr ctxt, xsltCompMatchPtr comp,
 301                   xmlNodePtr node, const xmlChar *mode,
 302                   const xmlChar *modeURI) {
 303     int i;
 304     xsltStepOpPtr step, select = NULL;
 305
 306     if ((comp == NULL) || (node == NULL) || (ctxt == NULL)) {
 307         xsltGenericError(xsltGenericErrorContext,
 308                 "xsltTestCompMatch: null arg\n");
 309         return(-1);
 310     }
 311     if (mode != NULL) {
 312         if (comp->mode == NULL)
 313             return(0);
 314         if ((comp->mode != mode) && (!xmlStrEqual(comp->mode, mode)))
 315             return(0);
 316     } else {
 317         if (comp->mode != NULL)
 318             return(0);
 319     }
 320     if (modeURI != NULL) {
 321         if (comp->modeURI == NULL)
 322             return(0);
 323         if ((comp->modeURI != modeURI) &&
 324             (!xmlStrEqual(comp->modeURI, modeURI)))
 325             return(0);
 326     } else {
 327         if (comp->modeURI != NULL)
 328             return(0);
 329     }
 330     for (i = 0;i < comp->nbStep;i++) {
 331         step = &comp->steps[i];
 332         if (step->op != XSLT_OP_PREDICATE)
 333             select = step;
 334         switch (step->op) {
 335             case XSLT_OP_END:
 336                 return(1);
 337             case XSLT_OP_ROOT:
 338                 if ((node->type != XML_DOCUMENT_NODE) &&
 339                     (node->type != XML_HTML_DOCUMENT_NODE))
 340                     return(0);
 341                 continue;
 342             case XSLT_OP_ELEM:
 343                 if (node->type != XML_ELEMENT_NODE)
 344                     return(0);
 345                 if (step->value == NULL)
 346                     continue;
 347                 if (!xmlStrEqual(step->value, node->name))
 348                     return(0);
 349
 350                 /* Namespace test */
 351                 if (node->ns == NULL) {
 352                     if (step->value2 != NULL)
 353                         return(0);
 354                 } else if (node->ns->href != NULL) {
 355                     if (step->value2 == NULL)
 356                         return(0);
 357                     if (!xmlStrEqual(step->value2, node->ns->href))
 358                         return(0);
 359                 }
 360                 continue;
 361             case XSLT_OP_CHILD:
 362                 TODO /* Handle OP_CHILD */
 363                 return(0);
 364             case XSLT_OP_ATTR:
 365                 if (node->type != XML_ATTRIBUTE_NODE)
 366                     return(0);
 367                 if (step->value == NULL)
 368                     continue;
 369                 if (!xmlStrEqual(step->value, node->name))
 370                     return(0);
 371
 372                 /* Namespace test */
 373                 if (node->ns == NULL) {
 374                     if (step->value2 != NULL)
 375                         return(0);
 376                 } else if (node->ns->href != NULL) {
 377                     if (step->value2 == NULL)
 378                         return(0);
 379                     if (!xmlStrEqual(step->value2, node->ns->href))
 380                         return(0);
 381                 }
 382                 continue;
 383             case XSLT_OP_PARENT:
 384                 node = node->parent;
 385                 if (node == NULL)
 386                     return(0);
 387                 if (step->value == NULL)
 388                     continue;
 389                 if (!xmlStrEqual(step->value, node->name))
 390                     return(0);
 391                 /* Namespace test */
 392                 if (node->ns == NULL) {
 393                     if (step->value2 != NULL)
 394                         return(0);
 395                 } else if (node->ns->href != NULL) {
 396                     if (step->value2 == NULL)
 397                         return(0);
 398                     if (!xmlStrEqual(step->value2, node->ns->href))
 399                         return(0);
 400                 }
 401                 continue;
 402             case XSLT_OP_ANCESTOR:
 403                 /* TODO: implement coalescing of ANCESTOR/NODE ops */
 404                 if (step->value == NULL) {
 405                     i++;
 406                     step = &comp->steps[i];
 407                     if (step->op == XSLT_OP_ROOT)
 408                         return(1);
 409                     if (step->op != XSLT_OP_ELEM)
 410                         return(0);
 411                     if (step->value == NULL)
 412                         return(-1);
 413                 }
 414                 if (node == NULL)
 415                     return(0);
 416                 node = node->parent;
 417                 while (node != NULL) {
 418                     if (node == NULL)
 419                         return(0);
 420                     if (xmlStrEqual(step->value, node->name)) {
 421                         /* Namespace test */
 422                         if (node->ns == NULL) {
 423                             if (step->value2 == NULL)
 424                                 break;
 425                         } else if (node->ns->href != NULL) {
 426                             if ((step->value2 != NULL) &&
 427                                 (xmlStrEqual(step->value2, node->ns->href)))
 428                                 break;
 429                         }
 430                     }
 431                     node = node->parent;
 432                 }
 433                 if (node == NULL)
 434                     return(0);
 435                 continue;
 436             case XSLT_OP_ID: {
 437                 /* TODO Handle IDs decently, must be done differently */
 438                 xmlAttrPtr id;
 439
 440                 id = xmlGetID(node->doc, step->value);
 441                 if ((id == NULL) || (id->parent != node))
 442                     return(0);
 443                 break;
 444             }
 445             case XSLT_OP_KEY:
 446                 TODO /* Handle Keys, might be done differently */
 447                 break;
 448             case XSLT_OP_NS:
 449                 /* Namespace test */
 450                 if (node->ns == NULL) {
 451                     if (step->value != NULL)
 452                         return(0);
 453                 } else if (node->ns->href != NULL) {
 454                     if (step->value == NULL)
 455                         return(0);
 456                     if (!xmlStrEqual(step->value, node->ns->href))
 457                         return(0);
 458                 }
 459                 break;
 460             case XSLT_OP_ALL:
 461                 switch (node->type) {
 462                     case XML_DOCUMENT_NODE:
 463                     case XML_HTML_DOCUMENT_NODE:
 464                     case XML_ELEMENT_NODE:
 465                         break;
 466                     default:
 467                         return(0);
 468                 }
 469                 break;
 470             case XSLT_OP_PREDICATE: {
 471                 xmlNodePtr oldNode;
 472                 int oldCS, oldCP;
 473                 int pos = 0, len = 0;
 474                 /*
 475                  * Depending on the last selection, one may need to
 476                  * recompute contextSize and proximityPosition.
 477                  */
 478                 oldCS = ctxt->xpathCtxt->contextSize;
 479                 oldCP = ctxt->xpathCtxt->proximityPosition;
 480                 if ((select != NULL) &&
 481                     (select->op == XSLT_OP_ELEM) &&
 482                     (select->value != NULL) &&
 483                     (node->type == XML_ELEMENT_NODE) &&
 484                     (node->parent != NULL)) {
 485
 486                     /* TODO: cache those informations ?!? */
 487                     xmlNodePtr siblings = node->parent->children;
 488
 489                     while (siblings != NULL) {
 490                         if (siblings->type == XML_ELEMENT_NODE) {
 491                             if (siblings == node) {
 492                                 len++;
 493                                 pos = len;
 494                             } else if (xmlStrEqual(node->name,
 495                                        siblings->name)) {
 496                                 len++;
 497                             }
 498                         }
 499                         siblings = siblings->next;
 500                     }
 501                     if (pos != 0) {
 502                         ctxt->xpathCtxt->contextSize = len;
 503                         ctxt->xpathCtxt->proximityPosition = pos;
 504                     }
 505                 }
 506                 oldNode = ctxt->node;
 507                 ctxt->node = node;
 508
 509                 if ((step->value == NULL) ||
 510                     (!xsltEvalXPathPredicate(ctxt, step->value))) {
 511                     if (pos != 0) {
 512                         ctxt->xpathCtxt->contextSize = oldCS;
 513                         ctxt->xpathCtxt->proximityPosition = oldCP;
 514                     }
 515                     ctxt->node = oldNode;
 516                     return(0);
 517                 }
 518                 if (pos != 0) {
 519                     ctxt->xpathCtxt->contextSize = oldCS;
 520                     ctxt->xpathCtxt->proximityPosition = oldCP;
 521                 }
 522                 ctxt->node = oldNode;
 523                 break;
 524             }
 525             case XSLT_OP_PI:
 526                 if (node->type != XML_PI_NODE)
 527                     return(0);
 528                 if (step->value != NULL) {
 529                     if (!xmlStrEqual(step->value, node->name))
 530                         return(0);
 531                 }
 532                 break;
 533             case XSLT_OP_COMMENT:
 534                 if (node->type != XML_COMMENT_NODE)
 535                     return(0);
 536                 break;
 537             case XSLT_OP_TEXT:
 538                 if ((node->type != XML_TEXT_NODE) &&
 539                     (node->type != XML_CDATA_SECTION_NODE))
 540                     return(0);
 541                 break;
 542             case XSLT_OP_NODE:
 543                 switch (node->type) {
 544                     case XML_DOCUMENT_NODE:
 545                     case XML_HTML_DOCUMENT_NODE:
 546                     case XML_ELEMENT_NODE:
 547                     case XML_CDATA_SECTION_NODE:
 548                     case XML_PI_NODE:
 549                     case XML_COMMENT_NODE:
 550                     case XML_TEXT_NODE:
 551                     case XML_ATTRIBUTE_NODE:
 552                         break;
 553                     default:
 554                         return(0);
 555                 }
 556                 break;
 557         }
 558     }
 559     return(1);
 560 }
 561
 562 /************************************************************************
 563  *                                                                      *
 564  *                      Dedicated parser for templates                  *
 565  *                                                                      *
 566  ************************************************************************/
 567
 568 #define CUR (*ctxt->cur)
 569 #define SKIP(val) ctxt->cur += (val)
 570 #define NXT(val) ctxt->cur[(val)]
 571 #define CUR_PTR ctxt->cur
 572
 573 #define SKIP_BLANKS                                                     \
 574     while (IS_BLANK(CUR)) NEXT
 575
 576 #define CURRENT (*ctxt->cur)
 577 #define NEXT ((*ctxt->cur) ?  ctxt->cur++: ctxt->cur)
 578
 579
 580 #define PUSH(op, val, val2)                                             \
 581     if (xsltCompMatchAdd(ctxt->comp, (op), (val), (val2))) goto error;
 582
 583 #define SWAP()                                          \
 584     xsltSwapTopCompMatch(ctxt->comp);
 585
 586 #define XSLT_ERROR(X)                                                   \
 587     { xsltError(ctxt, __FILE__, __LINE__, X);                   \
 588       ctxt->error = (X); return; }
 589
 590 #define XSLT_ERROR0(X)                                                  \
 591     { xsltError(ctxt, __FILE__, __LINE__, X);                   \
 592       ctxt->error = (X); return(0); }
 593
 594 /**
 595  * xsltScanLiteral:
 596  * @ctxt:  the XPath Parser context
 597  *
 598  * Parse an XPath Litteral:
 599  *
 600  * [29] Literal ::= '"' [^"]* '"'
 601  *                | "'" [^']* "'"
 602  *
 603  * Returns the Literal parsed or NULL
 604  */
 605
 606 xmlChar *
 607 xsltScanLiteral(xsltParserContextPtr ctxt) {
 608     const xmlChar *q;
 609     xmlChar *ret = NULL;
 610
 611     SKIP_BLANKS;
 612     if (CUR == '"') {
 613         NEXT;
 614         q = CUR_PTR;
 615         while ((IS_CHAR(CUR)) && (CUR != '"'))
 616             NEXT;
 617         if (!IS_CHAR(CUR)) {
 618             /* XP_ERROR(XPATH_UNFINISHED_LITERAL_ERROR); */
 619             ctxt->error = 1;
 620             return(NULL);
 621         } else {
 622             ret = xmlStrndup(q, CUR_PTR - q);
 623             NEXT;
 624         }
 625     } else if (CUR == '\'') {
 626         NEXT;
 627         q = CUR_PTR;
 628         while ((IS_CHAR(CUR)) && (CUR != '\''))
 629             NEXT;
 630         if (!IS_CHAR(CUR)) {
 631             /* XP_ERROR(XPATH_UNFINISHED_LITERAL_ERROR); */
 632             ctxt->error = 1;
 633             return(NULL);
 634         } else {
 635             ret = xmlStrndup(q, CUR_PTR - q);
 636             NEXT;
 637         }
 638     } else {
 639         /* XP_ERROR(XPATH_START_LITERAL_ERROR); */
 640         ctxt->error = 1;
 641         return(NULL);
 642     }
 643     return(ret);
 644 }
 645
 646 /**
 647  * xsltScanName:
 648  * @ctxt:  the XPath Parser context
 649  *
 650  * Trickery: parse an XML name but without consuming the input flow
 651  * Needed to avoid insanity in the parser state.
 652  *
 653  * [4] NameChar ::= Letter | Digit | '.' | '-' | '_' | ':' |
 654  *                  CombiningChar | Extender
 655  *
 656  * [5] Name ::= (Letter | '_' | ':') (NameChar)*
 657  *
 658  * [6] Names ::= Name (S Name)*
 659  *
 660  * Returns the Name parsed or NULL
 661  */
 662
 663 xmlChar *
 664 xsltScanName(xsltParserContextPtr ctxt) {
 665     xmlChar buf[XML_MAX_NAMELEN];
 666     int len = 0;
 667
 668     SKIP_BLANKS;
 669     if (!IS_LETTER(CUR) && (CUR != '_') &&
 670         (CUR != ':')) {
 671         return(NULL);
 672     }
 673
 674     while ((IS_LETTER(NXT(len))) || (IS_DIGIT(NXT(len))) ||
 675            (NXT(len) == '.') || (NXT(len) == '-') ||
 676            (NXT(len) == '_') || (NXT(len) == ':') ||
 677            (IS_COMBINING(NXT(len))) ||
 678            (IS_EXTENDER(NXT(len)))) {
 679         buf[len] = NXT(len);
 680         len++;
 681         if (len >= XML_MAX_NAMELEN) {
 682             xmlGenericError(xmlGenericErrorContext,
 683                "xmlScanName: reached XML_MAX_NAMELEN limit\n");
 684             while ((IS_LETTER(NXT(len))) || (IS_DIGIT(NXT(len))) ||
 685                    (NXT(len) == '.') || (NXT(len) == '-') ||
 686                    (NXT(len) == '_') || (NXT(len) == ':') ||
 687                    (IS_COMBINING(NXT(len))) ||
 688                    (IS_EXTENDER(NXT(len))))
 689                  len++;
 690             break;
 691         }
 692     }
 693     SKIP(len);
 694     return(xmlStrndup(buf, len));
 695 }
 696 /*
 697  * xsltCompileIdKeyPattern:
 698  * @comp:  the compilation context
 699  * @name:  a preparsed name
 700  * @aid:  whether id/key are allowed there
 701  *
 702  * Compile the XSLT LocationIdKeyPattern
 703  * [3] IdKeyPattern ::= 'id' '(' Literal ')'
 704  *                    | 'key' '(' Literal ',' Literal ')'
 705  *
 706  * also handle NodeType and PI from:
 707  *
 708  * [7]  NodeTest ::= NameTest
 709  *                 | NodeType '(' ')'
 710  *                 | 'processing-instruction' '(' Literal ')'
 711  */
 712 void
 713 xsltCompileIdKeyPattern(xsltParserContextPtr ctxt, xmlChar *name, int aid) {
 714     xmlChar *lit = NULL;
 715     xmlChar *lit2 = NULL;
 716
 717     if (CUR != '(') {
 718         xsltGenericError(xsltGenericErrorContext,
 719                 "xsltCompileIdKeyPattern : ( expected\n");
 720         ctxt->error = 1;
 721         return;
 722     }
 723     if ((aid) && (xmlStrEqual(name, (const xmlChar *)"id"))) {
 724         NEXT;
 725         SKIP_BLANKS;
 726         lit = xsltScanLiteral(ctxt);
 727         if (ctxt->error)
 728             return;
 729         SKIP_BLANKS;
 730         if (CUR != ')') {
 731             xsltGenericError(xsltGenericErrorContext,
 732                     "xsltCompileIdKeyPattern : ) expected\n");
 733             ctxt->error = 1;
 734             return;
 735         }
 736         NEXT;
 737         PUSH(XSLT_OP_ID, lit, NULL);
 738     } else if ((aid) && (xmlStrEqual(name, (const xmlChar *)"key"))) {
 739         NEXT;
 740         SKIP_BLANKS;
 741         lit = xsltScanLiteral(ctxt);
 742         if (ctxt->error)
 743             return;
 744         SKIP_BLANKS;
 745         if (CUR != ',') {
 746             xsltGenericError(xsltGenericErrorContext,
 747                     "xsltCompileIdKeyPattern : , expected\n");
 748             ctxt->error = 1;
 749             return;
 750         }
 751         NEXT;
 752         SKIP_BLANKS;
 753         lit2 = xsltScanLiteral(ctxt);
 754         if (ctxt->error)
 755             return;
 756         SKIP_BLANKS;
 757         if (CUR != ')') {
 758             xsltGenericError(xsltGenericErrorContext,
 759                     "xsltCompileIdKeyPattern : ) expected\n");
 760             ctxt->error = 1;
 761             return;
 762         }
 763         NEXT;
 764         PUSH(XSLT_OP_KEY, lit, lit2);
 765     } else if (xmlStrEqual(name, (const xmlChar *)"processing-instruction")) {
 766         NEXT;
 767         SKIP_BLANKS;
 768         if (CUR != ')') {
 769             lit = xsltScanLiteral(ctxt);
 770             if (ctxt->error)
 771                 return;
 772             SKIP_BLANKS;
 773             if (CUR != ')') {
 774                 xsltGenericError(xsltGenericErrorContext,
 775                         "xsltCompileIdKeyPattern : ) expected\n");
 776                 ctxt->error = 1;
 777                 return;
 778             }
 779         }
 780         NEXT;
 781         PUSH(XSLT_OP_PI, lit, NULL);
 782     } else if (xmlStrEqual(name, (const xmlChar *)"text")) {
 783         NEXT;
 784         SKIP_BLANKS;
 785         if (CUR != ')') {
 786             xsltGenericError(xsltGenericErrorContext,
 787                     "xsltCompileIdKeyPattern : ) expected\n");
 788             ctxt->error = 1;
 789             return;
 790         }
 791         NEXT;
 792         PUSH(XSLT_OP_TEXT, NULL, NULL);
 793     } else if (xmlStrEqual(name, (const xmlChar *)"comment")) {
 794         NEXT;
 795         SKIP_BLANKS;
 796         if (CUR != ')') {
 797             xsltGenericError(xsltGenericErrorContext,
 798                     "xsltCompileIdKeyPattern : ) expected\n");
 799             ctxt->error = 1;
 800             return;
 801         }
 802         NEXT;
 803         PUSH(XSLT_OP_COMMENT, NULL, NULL);
 804     } else if (xmlStrEqual(name, (const xmlChar *)"node")) {
 805         NEXT;
 806         SKIP_BLANKS;
 807         if (CUR != ')') {
 808             xsltGenericError(xsltGenericErrorContext,
 809                     "xsltCompileIdKeyPattern : ) expected\n");
 810             ctxt->error = 1;
 811             return;
 812         }
 813         NEXT;
 814         PUSH(XSLT_OP_NODE, NULL, NULL);
 815     } else if (aid) {
 816         xsltGenericError(xsltGenericErrorContext,
 817             "xsltCompileIdKeyPattern : expecting 'key' or 'id' or node type\n");
 818         ctxt->error = 1;
 819         return;
 820     } else {
 821         xsltGenericError(xsltGenericErrorContext,
 822             "xsltCompileIdKeyPattern : node type\n");
 823         ctxt->error = 1;
 824         return;
 825     }
 826 error:
 827     if (name != NULL)
 828         xmlFree(name);
 829 }
 830
 831 /**
 832  * xsltCompileStepPattern:
 833  * @comp:  the compilation context
 834  * @token:  a posible precompiled name
 835  *
 836  * Compile the XSLT StepPattern and generates a precompiled
 837  * form suitable for fast matching.
 838  *
 839  * [5] StepPattern ::= ChildOrAttributeAxisSpecifier NodeTest Predicate*
 840  * [6] ChildOrAttributeAxisSpecifier ::= AbbreviatedAxisSpecifier
 841  *                                     | ('child' | 'attribute') '::'
 842  * from XPath
 843  * [7]  NodeTest ::= NameTest
 844  *                 | NodeType '(' ')'
 845  *                 | 'processing-instruction' '(' Literal ')'
 846  * [8] Predicate ::= '[' PredicateExpr ']'
 847  * [9] PredicateExpr ::= Expr
 848  * [13] AbbreviatedAxisSpecifier ::= '@'?
 849  * [37] NameTest ::= '*' | NCName ':' '*' | QName
 850  */
 851
 852 void
 853 xsltCompileStepPattern(xsltParserContextPtr ctxt, xmlChar *token) {
 854     xmlChar *name = NULL;
 855
 856     SKIP_BLANKS;
 857     if ((token == NULL) && (CUR == '@')) {
 858         NEXT;
 859         if (CUR == '*') {
 860             NEXT;
 861             PUSH(XSLT_OP_ATTR, NULL, NULL);
 862             return;
 863         }
 864         token = xsltScanName(ctxt);
 865         if (token == NULL) {
 866             xsltGenericError(xsltGenericErrorContext,
 867                     "xsltCompileStepPattern : Name expected\n");
 868             ctxt->error = 1;
 869             goto error;
 870         }
 871         PUSH(XSLT_OP_ATTR, token, NULL);
 872         return;
 873     }
 874     if (token == NULL)
 875         token = xsltScanName(ctxt);
 876     if (token == NULL) {
 877         if (CUR == '*') {
 878             NEXT;
 879             PUSH(XSLT_OP_ALL, token, NULL);
 880             goto parse_predicate;
 881         } else {
 882             xsltGenericError(xsltGenericErrorContext,
 883                     "xsltCompileStepPattern : Name expected\n");
 884             ctxt->error = 1;
 885             goto error;
 886         }
 887     }
 888     SKIP_BLANKS;
 889     if (CUR == '(') {
 890         xsltCompileIdKeyPattern(ctxt, token, 0);
 891         if (ctxt->error)
 892             goto error;
 893     } else if (CUR == ':') {
 894         NEXT;
 895         if (NXT(1) != ':') {
 896             xsltGenericError(xsltGenericErrorContext,
 897                     "xsltCompileStepPattern : sequence '::' expected\n");
 898             ctxt->error = 1;
 899             goto error;
 900         }
 901         NEXT;
 902         if (xmlStrEqual(token, (const xmlChar *) "child")) {
 903             /* TODO: handle namespace */
 904             name = xsltScanName(ctxt);
 905             if (name == NULL) {
 906                 xsltGenericError(xsltGenericErrorContext,
 907                         "xsltCompileStepPattern : QName expected\n");
 908                 ctxt->error = 1;
 909                 goto error;
 910             }
 911             PUSH(XSLT_OP_CHILD, name, NULL);
 912         } else if (xmlStrEqual(token, (const xmlChar *) "attribute")) {
 913             /* TODO: handle namespace */
 914             name = xsltScanName(ctxt);
 915             if (name == NULL) {
 916                 xsltGenericError(xsltGenericErrorContext,
 917                         "xsltCompileStepPattern : QName expected\n");
 918                 ctxt->error = 1;
 919                 goto error;
 920             }
 921             PUSH(XSLT_OP_ATTR, name, NULL);
 922         } else {
 923             xsltGenericError(xsltGenericErrorContext,
 924                 "xsltCompileStepPattern : 'child' or 'attribute' expected\n");
 925             ctxt->error = 1;
 926             goto error;
 927         }
 928         xmlFree(token);
 929     } else if (CUR == '*') {
 930         NEXT;
 931         PUSH(XSLT_OP_ALL, token, NULL);
 932     } else {
 933         /* TODO: handle namespace */
 934         PUSH(XSLT_OP_ELEM, token, NULL);
 935     }
 936 parse_predicate:
 937     SKIP_BLANKS;
 938     while (CUR == '[') {
 939         const xmlChar *q;
 940         xmlChar *ret = NULL;
 941
 942         NEXT;
 943         q = CUR_PTR;
 944         /* TODO: avoid breaking in strings ... */
 945         while ((IS_CHAR(CUR)) && (CUR != ']'))
 946             NEXT;
 947         if (!IS_CHAR(CUR)) {
 948             xsltGenericError(xsltGenericErrorContext,
 949                     "xsltCompileStepPattern : ']' expected\n");
 950             ctxt->error = 1;
 951             goto error;
 952         }
 953         ret = xmlStrndup(q, CUR_PTR - q);
 954         PUSH(XSLT_OP_PREDICATE, ret, NULL);
 955         /* push the predicate lower than local test */
 956         SWAP();
 957         NEXT;
 958     }
 959     return;
 960 error:
 961     if (token != NULL)
 962         xmlFree(token);
 963     if (name != NULL)
 964         xmlFree(name);
 965 }
 966
 967 /**
 968  * xsltCompileRelativePathPattern:
 969  * @comp:  the compilation context
 970  * @token:  a posible precompiled name
 971  *
 972  * Compile the XSLT RelativePathPattern and generates a precompiled
 973  * form suitable for fast matching.
 974  *
 975  * [4] RelativePathPattern ::= StepPattern
 976  *                           | RelativePathPattern '/' StepPattern
 977  *                           | RelativePathPattern '//' StepPattern
 978  */
 979 void
 980 xsltCompileRelativePathPattern(xsltParserContextPtr ctxt, xmlChar *token) {
 981     xsltCompileStepPattern(ctxt, token);
 982     if (ctxt->error)
 983         goto error;
 984     SKIP_BLANKS;
 985     while ((CUR != 0) && (CUR != '|')) {
 986         if ((CUR == '/') && (NXT(1) == '/')) {
 987             PUSH(XSLT_OP_ANCESTOR, NULL, NULL);
 988             NEXT;
 989             NEXT;
 990             SKIP_BLANKS;
 991             xsltCompileStepPattern(ctxt, NULL);
 992         } else if (CUR == '/') {
 993             PUSH(XSLT_OP_PARENT, NULL, NULL);
 994             NEXT;
 995             SKIP_BLANKS;
 996             if ((CUR != 0) || (CUR == '|')) {
 997                 xsltCompileRelativePathPattern(ctxt, NULL);
 998             }
 999         } else {
1000             ctxt->error = 1;
1001         }
1002         if (ctxt->error)
1003             goto error;
1004         SKIP_BLANKS;
1005     }
1006 error:
1007     return;
1008 }
1009
1010 /**
1011  * xsltCompileLocationPathPattern:
1012  * @comp:  the compilation context
1013  *
1014  * Compile the XSLT LocationPathPattern and generates a precompiled
1015  * form suitable for fast matching.
1016  *
1017  * [2] LocationPathPattern ::= '/' RelativePathPattern?
1018  *                           | IdKeyPattern (('/' | '//') RelativePathPattern)?
1019  *                           | '//'? RelativePathPattern
1020  */
1021 void
1022 xsltCompileLocationPathPattern(xsltParserContextPtr ctxt) {
1023     SKIP_BLANKS;
1024     if ((CUR == '/') && (NXT(1) == '/')) {
1025         /*
1026          * since we reverse the query
1027          * a leading // can be safely ignored
1028          */
1029         NEXT;
1030         NEXT;
1031         xsltCompileRelativePathPattern(ctxt, NULL);
1032     } else if (CUR == '/') {
1033         /*
1034          * We need to find root as the parent
1035          */
1036         NEXT;
1037         SKIP_BLANKS;
1038         PUSH(XSLT_OP_ROOT, NULL, NULL);
1039         if ((CUR != 0) || (CUR == '|')) {
1040             PUSH(XSLT_OP_PARENT, NULL, NULL);
1041             xsltCompileRelativePathPattern(ctxt, NULL);
1042         }
1043     } else if (CUR == '*') {
1044         xsltCompileRelativePathPattern(ctxt, NULL);
1045     } else if (CUR == '@') {
1046         xsltCompileRelativePathPattern(ctxt, NULL);
1047     } else {
1048         xmlChar *name;
1049         name = xsltScanName(ctxt);
1050         if (name == NULL) {
1051             xsltGenericError(xsltGenericErrorContext,
1052                     "xsltCompileLocationPathPattern : Name expected\n");
1053             ctxt->error = 1;
1054             return;
1055         }
1056         SKIP_BLANKS;
1057         if (CUR == '(') {
1058             xsltCompileIdKeyPattern(ctxt, name, 1);
1059             if ((CUR == '/') && (NXT(1) == '/')) {
1060                 PUSH(XSLT_OP_ANCESTOR, NULL, NULL);
1061                 NEXT;
1062                 NEXT;
1063                 SKIP_BLANKS;
1064                 xsltCompileRelativePathPattern(ctxt, NULL);
1065             } else if (CUR == '/') {
1066                 PUSH(XSLT_OP_PARENT, NULL, NULL);
1067                 NEXT;
1068                 SKIP_BLANKS;
1069                 xsltCompileRelativePathPattern(ctxt, NULL);
1070             }
1071             return;
1072         }
1073         xsltCompileRelativePathPattern(ctxt, name);
1074     }
1075 error:
1076     return;
1077 }
1078
1079 /**
1080  * xsltCompilePattern:
1081  * @pattern an XSLT pattern
1082  * @mode:  the mode name or NULL
1083  * @modeURI:  the mode URI or NULL
1084  *
1085  * Compile the XSLT pattern and generates a precompiled form suitable
1086  * for fast matching.
1087  * Note that the splitting as union of patterns is expected to be handled
1088  * by the caller
1089  *
1090  * [1] Pattern ::= LocationPathPattern | Pattern '|' LocationPathPattern
1091  *
1092  * Returns the generated xsltCompMatchPtr or NULL in case of failure
1093  */
1094
1095 xsltCompMatchPtr
1096 xsltCompilePattern(const xmlChar *pattern, const xmlChar *mode,
1097                    const xmlChar *modeURI) {
1098     xsltParserContextPtr ctxt;
1099     xsltCompMatchPtr ret;
1100     const xmlChar *cur;
1101
1102     if (pattern == NULL) {
1103         xsltGenericError(xsltGenericErrorContext,
1104                 "xsltCompilePattern : NULL pattern\n");
1105         return(NULL);
1106     }
1107
1108 #ifdef DEBUG_PARSING
1109     xsltGenericDebug(xsltGenericDebugContext,
1110             "xsltCompilePattern : parsing '%s'\n", pattern);
1111 #endif
1112
1113     cur = pattern;
1114     while (IS_BLANK(*cur)) cur++;
1115     if (*cur == 0) {
1116         xsltGenericError(xsltGenericErrorContext,
1117                 "xsltCompilePattern : NULL pattern\n");
1118         return(NULL);
1119     }
1120     ctxt = xsltNewParserContext();
1121     if (ctxt == NULL)
1122         return(NULL);
1123     ret = xsltNewCompMatch(mode, modeURI);
1124     if (ret == NULL) {
1125         xsltFreeParserContext(ctxt);
1126         return(NULL);
1127     }
1128
1129     ctxt->comp = ret;
1130     ctxt->base = pattern;
1131     ctxt->cur = cur;
1132     xsltCompileLocationPathPattern(ctxt);
1133     if (ctxt->error)
1134         goto error;
1135
1136     /*
1137      * Reverse for faster interpretation.
1138      */
1139     xsltReverseCompMatch(ret);
1140
1141     /*
1142      * Set-up the priority
1143      */
1144     if (((ret->steps[0].op == XSLT_OP_ELEM) ||
1145          (ret->steps[0].op == XSLT_OP_ATTR)) &&
1146         (ret->steps[0].value != NULL) &&
1147         (ret->steps[1].op == XSLT_OP_END)) {
1148         ret->priority = 0;
1149     } else if ((ret->steps[0].op == XSLT_OP_PI) &&
1150                (ret->steps[0].value != NULL) &&
1151                (ret->steps[1].op == XSLT_OP_END)) {
1152         ret->priority = 0;
1153     } else if ((ret->steps[0].op == XSLT_OP_NS) &&
1154                (ret->steps[0].value != NULL) &&
1155                (ret->steps[1].op == XSLT_OP_END)) {
1156         ret->priority = -0.25;
1157     } else if (((ret->steps[0].op == XSLT_OP_PI) ||
1158                 (ret->steps[0].op == XSLT_OP_TEXT) ||
1159                 (ret->steps[0].op == XSLT_OP_NODE) ||
1160                 (ret->steps[0].op == XSLT_OP_COMMENT)) &&
1161                (ret->steps[1].op == XSLT_OP_END)) {
1162         ret->priority = -0.5;
1163     } else {
1164         ret->priority = 0.5;
1165     }
1166
1167     xsltFreeParserContext(ctxt);
1168     return(ret);
1169
1170 error:
1171     xsltFreeParserContext(ctxt);
1172     xsltFreeCompMatch(ret);
1173     return(NULL);
1174
1175 }
1176
1177
1178 /************************************************************************
1179  *                                                                      *
1180  *                      Module interfaces                               *
1181  *                                                                      *
1182  ************************************************************************/
1183
1184 /**
1185  * xsltAddTemplate:
1186  * @style: an XSLT stylesheet
1187  * @cur: an XSLT template
1188  * @mode:  the mode name or NULL
1189  * @modeURI:  the mode URI or NULL
1190  *
1191  * Register the XSLT pattern associated to @cur
1192  *
1193  * Returns -1 in case of error, 0 otherwise
1194  */
1195 int
1196 xsltAddTemplate(xsltStylesheetPtr style, xsltTemplatePtr cur,
1197                 const xmlChar *mode, const xmlChar *modeURI) {
1198     xsltCompMatchPtr pat, list, *top = NULL;
1199     const xmlChar *name = NULL;
1200     xmlChar *p, *pattern, tmp;
1201
1202     if ((style == NULL) || (cur == NULL))
1203         return(-1);
1204
1205     p = cur->match;
1206     if (p == NULL)
1207         return(-1);
1208
1209 next_pattern:
1210     if (*p == 0)
1211         return(0);
1212     /*
1213      * get a compiled form of the pattern
1214      */
1215     pattern = p;
1216     while ((*p != 0) && (*p != '|')) {
1217         /* TODO: handle string escaping "a | b" in patterns ... */
1218         p++;
1219     }
1220
1221     tmp = *p;
1222     *p = 0;
1223     pat = xsltCompilePattern(pattern, mode, modeURI);
1224     *p = tmp;
1225     if (tmp != 0)
1226         p++;
1227     if (pat == NULL)
1228         return(-1);
1229     pat->template = cur;
1230     if (cur->priority != XSLT_PAT_NO_PRIORITY)
1231         pat->priority = cur->priority;
1232
1233     /*
1234      * insert it in the hash table list corresponding to its lookup name
1235      */
1236     switch (pat->steps[0].op) {
1237         case XSLT_OP_ATTR:
1238             if (pat->steps[0].value != NULL)
1239                 name = pat->steps[0].value;
1240             else
1241                 top = (xsltCompMatchPtr *) &(style->attrMatch);
1242             break;
1243         case XSLT_OP_ELEM:
1244         case XSLT_OP_CHILD:
1245         case XSLT_OP_PARENT:
1246         case XSLT_OP_ANCESTOR:
1247         case XSLT_OP_NS:
1248              name = pat->steps[0].value;
1249              break;
1250         case XSLT_OP_ROOT:
1251              top = (xsltCompMatchPtr *) &(style->rootMatch);
1252              break;
1253         case XSLT_OP_ID:
1254         case XSLT_OP_KEY:
1255              /* TODO optimize ID/KEY !!! */
1256         case XSLT_OP_ALL:
1257              top = (xsltCompMatchPtr *) &(style->elemMatch);
1258              break;
1259         case XSLT_OP_END:
1260         case XSLT_OP_PREDICATE:
1261             xsltGenericError(xsltGenericErrorContext,
1262                     "xsltAddTemplate: invalid compiled pattern\n");
1263             xsltFreeCompMatch(pat);
1264             return(-1);
1265         /*
1266          * TODO: some flags at the top level about type based patterns
1267          *       would be faster than inclusion in the hash table.
1268          */
1269         case XSLT_OP_PI:
1270             if (pat->steps[0].value != NULL)
1271                 name = pat->steps[0].value;
1272             else
1273                 top = (xsltCompMatchPtr *) &(style->piMatch);
1274             break;
1275         case XSLT_OP_COMMENT:
1276             top = (xsltCompMatchPtr *) &(style->commentMatch);
1277             break;
1278         case XSLT_OP_TEXT:
1279             top = (xsltCompMatchPtr *) &(style->textMatch);
1280             break;
1281         case XSLT_OP_NODE:
1282             if (pat->steps[0].value != NULL)
1283                 name = pat->steps[0].value;
1284             else
1285                 top = (xsltCompMatchPtr *) &(style->elemMatch);
1286
1287             break;
1288     }
1289     if (name != NULL) {
1290         if (style->templatesHash == NULL) {
1291             style->templatesHash = xmlHashCreate(1024);
1292             if (style->templatesHash == NULL) {
1293                 xsltFreeCompMatch(pat);
1294                 return(-1);
1295             }
1296 #ifdef DEBUG_PARSING
1297             xsltGenericDebug(xsltGenericDebugContext,
1298                     "xsltAddTemplate: created template hash\n");
1299 #endif
1300             xmlHashAddEntry3(style->templatesHash, name, mode, modeURI, pat);
1301 #ifdef DEBUG_PARSING
1302             xsltGenericDebug(xsltGenericDebugContext,
1303                     "xsltAddTemplate: added new hash %s\n", name);
1304 #endif
1305         } else {
1306             list = (xsltCompMatchPtr) xmlHashLookup3(style->templatesHash,
1307                                       name, mode, modeURI);
1308             if (list == NULL) {
1309                 xmlHashAddEntry3(style->templatesHash, name,
1310                                  mode, modeURI, pat);
1311 #ifdef DEBUG_PARSING
1312                 xsltGenericDebug(xsltGenericDebugContext,
1313                         "xsltAddTemplate: added new hash %s\n", name);
1314 #endif
1315             } else {
1316                 /*
1317                  * Note '<=' since one must choose among the matching
1318                  * template rules that are left, the one that occurs
1319                  * last in the stylesheet
1320                  */
1321                 if (list->priority <= pat->priority) {
1322                     pat->next = list;
1323                     xmlHashUpdateEntry3(style->templatesHash, name,
1324                                         mode, modeURI, pat, NULL);
1325 #ifdef DEBUG_PARSING
1326                     xsltGenericDebug(xsltGenericDebugContext,
1327                             "xsltAddTemplate: added head hash for %s\n", name);
1328 #endif
1329                 } else {
1330                     while (list->next != NULL) {
1331                         if (list->next->priority <= pat->priority)
1332                             break;
1333                         list = list->next;
1334                     }
1335                     pat->next = list->next;
1336                     list->next = pat;
1337                 }
1338             }
1339         }
1340     } else if (top != NULL) {
1341         list = *top;
1342         if (list == NULL) {
1343             *top = pat;
1344             pat->next = NULL;
1345         } else if (list->priority <= pat->priority) {
1346             pat->next = list;
1347             *top = pat;
1348         } else {
1349             while (list->next != NULL) {
1350                 if (list->next->priority <= pat->priority)
1351                     break;
1352                 list = list->next;
1353             }
1354             pat->next = list->next;
1355             list->next = pat;
1356         }
1357     } else {
1358         xsltGenericError(xsltGenericErrorContext,
1359                 "xsltAddTemplate: invalid compiled pattern\n");
1360         xsltFreeCompMatch(pat);
1361         return(-1);
1362     }
1363     if (*p != 0)
1364         goto next_pattern;
1365     return(0);
1366 }
1367
1368 /**
1369  * xsltGetTemplate:
1370  * @ctxt:  a XSLT process context
1371  * @mode:  the mode name or NULL
1372  *
1373  * Finds the template applying to this node
1374  *
1375  * Returns the xsltTemplatePtr or NULL if not found
1376  */
1377 xsltTemplatePtr
1378 xsltGetTemplate(xsltTransformContextPtr ctxt, xmlNodePtr node) {
1379     xsltStylesheetPtr style;
1380     xsltTemplatePtr ret = NULL;
1381     const xmlChar *name = NULL;
1382     xsltCompMatchPtr list = NULL;
1383
1384     if ((ctxt == NULL) || (node == NULL))
1385         return(NULL);
1386
1387     style = ctxt->style;
1388     while (style != NULL) {
1389         /* TODO : handle IDs/keys here ! */
1390         if (style->templatesHash != NULL) {
1391             /*
1392              * Use the top name as selector
1393              */
1394             switch (node->type) {
1395                 case XML_ELEMENT_NODE:
1396                 case XML_ATTRIBUTE_NODE:
1397                 case XML_PI_NODE:
1398                     name = node->name;
1399                     break;
1400                 case XML_DOCUMENT_NODE:
1401                 case XML_HTML_DOCUMENT_NODE:
1402                 case XML_TEXT_NODE:
1403                 case XML_CDATA_SECTION_NODE:
1404                 case XML_COMMENT_NODE:
1405                 case XML_ENTITY_REF_NODE:
1406                 case XML_ENTITY_NODE:
1407                 case XML_DOCUMENT_TYPE_NODE:
1408                 case XML_DOCUMENT_FRAG_NODE:
1409                 case XML_NOTATION_NODE:
1410                 case XML_DTD_NODE:
1411                 case XML_ELEMENT_DECL:
1412                 case XML_ATTRIBUTE_DECL:
1413                 case XML_ENTITY_DECL:
1414                 case XML_NAMESPACE_DECL:
1415                 case XML_XINCLUDE_START:
1416                 case XML_XINCLUDE_END:
1417                     break;
1418                 default:
1419                     return(NULL);
1420
1421             }
1422         }
1423         if (name != NULL) {
1424             /*
1425              * find the list of appliable expressions based on the name
1426              */
1427             list = (xsltCompMatchPtr) xmlHashLookup3(style->templatesHash,
1428                                              name, ctxt->mode, ctxt->modeURI);
1429         }
1430         while (list != NULL) {
1431             if (xsltTestCompMatch(ctxt, list, node,
1432                                   ctxt->mode, ctxt->modeURI)) {
1433                 ret = list->template;
1434                 break;
1435             }
1436             list = list->next;
1437         }
1438         list = NULL;
1439
1440         /*
1441          * find alternate generic matches
1442          */
1443         switch (node->type) {
1444             case XML_ELEMENT_NODE:
1445                 list = style->elemMatch;
1446                 break;
1447             case XML_ATTRIBUTE_NODE:
1448                 list = style->attrMatch;
1449                 break;
1450             case XML_PI_NODE:
1451                 list = style->piMatch;
1452                 break;
1453             case XML_DOCUMENT_NODE:
1454             case XML_HTML_DOCUMENT_NODE:
1455                 list = style->rootMatch;
1456                 break;
1457             case XML_TEXT_NODE:
1458             case XML_CDATA_SECTION_NODE:
1459                 list = style->textMatch;
1460                 break;
1461             case XML_COMMENT_NODE:
1462                 list = style->commentMatch;
1463                 break;
1464             case XML_ENTITY_REF_NODE:
1465             case XML_ENTITY_NODE:
1466             case XML_DOCUMENT_TYPE_NODE:
1467             case XML_DOCUMENT_FRAG_NODE:
1468             case XML_NOTATION_NODE:
1469             case XML_DTD_NODE:
1470             case XML_ELEMENT_DECL:
1471             case XML_ATTRIBUTE_DECL:
1472             case XML_ENTITY_DECL:
1473             case XML_NAMESPACE_DECL:
1474             case XML_XINCLUDE_START:
1475             case XML_XINCLUDE_END:
1476                 break;
1477             default:
1478                 break;
1479
1480         }
1481         while ((list != NULL) &&
1482                ((ret == NULL)  || (list->priority > ret->priority))) {
1483             if (xsltTestCompMatch(ctxt, list, node,
1484                                   ctxt->mode, ctxt->modeURI)) {
1485                 ret = list->template;
1486                 break;
1487             }
1488             list = list->next;
1489         }
1490         if (ret != NULL)
1491             return(ret);
1492
1493         /*
1494          * Cycle on next stylesheet import.
1495          */
1496         style = xsltNextImport(style);
1497     }
1498     return(NULL);
1499 }
1500
1501
1502 /**
1503  * xsltFreeTemplateHashes:
1504  * @style: an XSLT stylesheet
1505  *
1506  * Free up the memory used by xsltAddTemplate/xsltGetTemplate mechanism
1507  */
1508 void
1509 xsltFreeTemplateHashes(xsltStylesheetPtr style) {
1510     if (style->templatesHash != NULL)
1511         xmlHashFree((xmlHashTablePtr) style->templatesHash,
1512                     (xmlHashDeallocator) xsltFreeCompMatchList);
1513     if (style->rootMatch != NULL)
1514         xsltFreeCompMatchList(style->rootMatch);
1515     if (style->elemMatch != NULL)
1516         xsltFreeCompMatchList(style->elemMatch);
1517     if (style->attrMatch != NULL)
1518         xsltFreeCompMatchList(style->attrMatch);
1519     if (style->parentMatch != NULL)
1520         xsltFreeCompMatchList(style->parentMatch);
1521     if (style->textMatch != NULL)
1522         xsltFreeCompMatchList(style->textMatch);
1523     if (style->piMatch != NULL)
1524         xsltFreeCompMatchList(style->piMatch);
1525     if (style->commentMatch != NULL)
1526         xsltFreeCompMatchList(style->commentMatch);
1527 }
1528