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