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 (lit != NULL)
 700         xmlFree(lit);
 701     if (lit2 != NULL)
 702         xmlFree(lit2);
 703 }
 704
 705 /**
 706  * xsltCompileStepPattern:
 707  * @comp:  the compilation context
 708  * @token:  a posible precompiled name
 709  *
 710  * Compile the XSLT StepPattern and generates a precompiled
 711  * form suitable for fast matching.
 712  *
 713  * [5] StepPattern ::= ChildOrAttributeAxisSpecifier NodeTest Predicate*
 714  * [6] ChildOrAttributeAxisSpecifier ::= AbbreviatedAxisSpecifier
 715  *                                     | ('child' | 'attribute') '::'
 716  * from XPath
 717  * [7]  NodeTest ::= NameTest
 718  *                 | NodeType '(' ')'
 719  *                 | 'processing-instruction' '(' Literal ')'
 720  * [8] Predicate ::= '[' PredicateExpr ']'
 721  * [9] PredicateExpr ::= Expr
 722  * [13] AbbreviatedAxisSpecifier ::= '@'?
 723  * [37] NameTest ::= '*' | NCName ':' '*' | QName
 724  */
 725
 726 void
 727 xsltCompileStepPattern(xsltParserContextPtr ctxt, xmlChar *token) {
 728     xmlChar *name = NULL;
 729
 730     SKIP_BLANKS;
 731     if ((token == NULL) && (CUR == '@')) {
 732         token = xsltScanName(ctxt);
 733         if (token == NULL) {
 734             xsltGenericError(xsltGenericErrorContext,
 735                     "xsltCompileStepPattern : Name expected\n");
 736             ctxt->error = 1;
 737             goto error;
 738         }
 739         PUSH(XSLT_OP_ATTR, token, NULL);
 740         return;
 741     }
 742     if (token == NULL)
 743         token = xsltScanName(ctxt);
 744     if (token == NULL) {
 745         if (CUR == '*') {
 746             NEXT;
 747             PUSH(XSLT_OP_ALL, token, NULL);
 748             goto parse_predicate;
 749         } else {
 750             xsltGenericError(xsltGenericErrorContext,
 751                     "xsltCompileStepPattern : Name expected\n");
 752             ctxt->error = 1;
 753             goto error;
 754         }
 755     }
 756     SKIP_BLANKS;
 757     if (CUR == '(') {
 758         xsltCompileIdKeyPattern(ctxt, token, 0);
 759         if (ctxt->error)
 760             goto error;
 761     } else if (CUR == ':') {
 762         NEXT;
 763         if (NXT(1) != ':') {
 764             xsltGenericError(xsltGenericErrorContext,
 765                     "xsltCompileStepPattern : sequence '::' expected\n");
 766             ctxt->error = 1;
 767             goto error;
 768         }
 769         NEXT;
 770         if (xmlStrEqual(token, (const xmlChar *) "child")) {
 771             /* TODO: handle namespace */
 772             name = xsltScanName(ctxt);
 773             if (name == NULL) {
 774                 xsltGenericError(xsltGenericErrorContext,
 775                         "xsltCompileStepPattern : QName expected\n");
 776                 ctxt->error = 1;
 777                 goto error;
 778             }
 779             PUSH(XSLT_OP_CHILD, name, NULL);
 780         } else if (xmlStrEqual(token, (const xmlChar *) "attribute")) {
 781             /* TODO: handle namespace */
 782             name = xsltScanName(ctxt);
 783             if (name == NULL) {
 784                 xsltGenericError(xsltGenericErrorContext,
 785                         "xsltCompileStepPattern : QName expected\n");
 786                 ctxt->error = 1;
 787                 goto error;
 788             }
 789             PUSH(XSLT_OP_ATTR, name, NULL);
 790         } else {
 791             xsltGenericError(xsltGenericErrorContext,
 792                 "xsltCompileStepPattern : 'child' or 'attribute' expected\n");
 793             ctxt->error = 1;
 794             goto error;
 795         }
 796         xmlFree(token);
 797     } else if (CUR == '*') {
 798         NEXT;
 799         PUSH(XSLT_OP_ALL, token, NULL);
 800     } else {
 801         /* TODO: handle namespace */
 802         PUSH(XSLT_OP_ELEM, token, NULL);
 803     }
 804 parse_predicate:
 805     SKIP_BLANKS;
 806     while (CUR == '[') {
 807         const xmlChar *q;
 808         xmlChar *ret = NULL;
 809
 810         NEXT;
 811         q = CUR_PTR;
 812         /* TODO: avoid breaking in strings ... */
 813         while ((IS_CHAR(CUR)) && (CUR != ']'))
 814             NEXT;
 815         if (!IS_CHAR(CUR)) {
 816             xsltGenericError(xsltGenericErrorContext,
 817                     "xsltCompileStepPattern : ']' expected\n");
 818             ctxt->error = 1;
 819             goto error;
 820         }
 821         NEXT;
 822         ret = xmlStrndup(q, CUR_PTR - q);
 823         PUSH(XSLT_OP_PREDICATE, ret, NULL);
 824     }
 825     return;
 826 error:
 827     if (token != NULL)
 828         xmlFree(token);
 829     if (name != NULL)
 830         xmlFree(name);
 831 }
 832
 833 /**
 834  * xsltCompileRelativePathPattern:
 835  * @comp:  the compilation context
 836  * @token:  a posible precompiled name
 837  *
 838  * Compile the XSLT RelativePathPattern and generates a precompiled
 839  * form suitable for fast matching.
 840  *
 841  * [4] RelativePathPattern ::= StepPattern
 842  *                           | RelativePathPattern '/' StepPattern
 843  *                           | RelativePathPattern '//' StepPattern
 844  */
 845 void
 846 xsltCompileRelativePathPattern(xsltParserContextPtr ctxt, xmlChar *token) {
 847     xsltCompileStepPattern(ctxt, token);
 848     if (ctxt->error)
 849         goto error;
 850     SKIP_BLANKS;
 851     while ((CUR != 0) && (CUR != '|')) {
 852         if ((CUR == '/') && (NXT(1) == '/')) {
 853             PUSH(XSLT_OP_ANCESTOR, NULL, NULL);
 854             NEXT;
 855             NEXT;
 856             SKIP_BLANKS;
 857             xsltCompileStepPattern(ctxt, NULL);
 858         } else if (CUR == '/') {
 859             PUSH(XSLT_OP_PARENT, NULL, NULL);
 860             NEXT;
 861             SKIP_BLANKS;
 862             if ((CUR != 0) || (CUR == '|')) {
 863                 xsltCompileRelativePathPattern(ctxt, NULL);
 864             }
 865         } else {
 866             ctxt->error = 1;
 867         }
 868         if (ctxt->error)
 869             goto error;
 870         SKIP_BLANKS;
 871     }
 872 error:
 873     return;
 874 }
 875
 876 /**
 877  * xsltCompileLocationPathPattern:
 878  * @comp:  the compilation context
 879  *
 880  * Compile the XSLT LocationPathPattern and generates a precompiled
 881  * form suitable for fast matching.
 882  *
 883  * [2] LocationPathPattern ::= '/' RelativePathPattern?
 884  *                           | IdKeyPattern (('/' | '//') RelativePathPattern)?
 885  *                           | '//'? RelativePathPattern
 886  */
 887 void
 888 xsltCompileLocationPathPattern(xsltParserContextPtr ctxt) {
 889     SKIP_BLANKS;
 890     if ((CUR == '/') && (NXT(1) == '/')) {
 891         /*
 892          * since we reverse the query
 893          * a leading // can be safely ignored
 894          */
 895         NEXT;
 896         NEXT;
 897         xsltCompileRelativePathPattern(ctxt, NULL);
 898     } else if (CUR == '/') {
 899         /*
 900          * We need to find root as the parent
 901          */
 902         NEXT;
 903         SKIP_BLANKS;
 904         PUSH(XSLT_OP_ROOT, NULL, NULL);
 905         if ((CUR != 0) || (CUR == '|')) {
 906             PUSH(XSLT_OP_PARENT, NULL, NULL);
 907             xsltCompileRelativePathPattern(ctxt, NULL);
 908         }
 909     } else if (CUR == '*') {
 910         xsltCompileRelativePathPattern(ctxt, NULL);
 911     } else {
 912         xmlChar *name;
 913         name = xsltScanName(ctxt);
 914         if (name == NULL) {
 915             xsltGenericError(xsltGenericErrorContext,
 916                     "xsltCompilePattern : Name expected\n");
 917             ctxt->error = 1;
 918             return;
 919         }
 920         SKIP_BLANKS;
 921         if (CUR == '(') {
 922             xsltCompileIdKeyPattern(ctxt, name, 1);
 923             if ((CUR == '/') && (NXT(1) == '/')) {
 924                 PUSH(XSLT_OP_ANCESTOR, NULL, NULL);
 925                 NEXT;
 926                 NEXT;
 927                 SKIP_BLANKS;
 928                 xsltCompileRelativePathPattern(ctxt, NULL);
 929             } else if (CUR == '/') {
 930                 PUSH(XSLT_OP_PARENT, NULL, NULL);
 931                 NEXT;
 932                 SKIP_BLANKS;
 933                 xsltCompileRelativePathPattern(ctxt, NULL);
 934             }
 935             return;
 936         }
 937         xsltCompileRelativePathPattern(ctxt, name);
 938     }
 939 error:
 940     return;
 941 }
 942
 943 /**
 944  * xsltCompilePattern:
 945  * @pattern an XSLT pattern
 946  *
 947  * Compile the XSLT pattern and generates a precompiled form suitable
 948  * for fast matching.
 949  * Note that the splitting as union of patterns is expected to be handled
 950  * by the caller
 951  *
 952  * [1] Pattern ::= LocationPathPattern | Pattern '|' LocationPathPattern
 953  *
 954  * Returns the generated xsltCompMatchPtr or NULL in case of failure
 955  */
 956
 957 xsltCompMatchPtr
 958 xsltCompilePattern(const xmlChar *pattern) {
 959     xsltParserContextPtr ctxt;
 960     xsltCompMatchPtr ret;
 961     const xmlChar *cur;
 962
 963     if (pattern == NULL) {
 964         xsltGenericError(xsltGenericErrorContext,
 965                 "xsltCompilePattern : NULL pattern\n");
 966         return(NULL);
 967     }
 968
 969 #ifdef DEBUG_PARSING
 970     xsltGenericDebug(xsltGenericDebugContext,
 971             "xsltCompilePattern : parsing '%s'\n", pattern);
 972 #endif
 973
 974     cur = pattern;
 975     while (IS_BLANK(*cur)) cur++;
 976     if (*cur == 0) {
 977         xsltGenericError(xsltGenericErrorContext,
 978                 "xsltCompilePattern : NULL pattern\n");
 979         return(NULL);
 980     }
 981     ctxt = xsltNewParserContext();
 982     if (ctxt == NULL)
 983         return(NULL);
 984     ret = xsltNewCompMatch();
 985     if (ret == NULL) {
 986         xsltFreeParserContext(ctxt);
 987         return(NULL);
 988     }
 989
 990     ctxt->comp = ret;
 991     ctxt->base = pattern;
 992     ctxt->cur = cur;
 993     xsltCompileLocationPathPattern(ctxt);
 994     if (ctxt->error)
 995         goto error;
 996
 997     /*
 998      * Reverse for faster interpretation.
 999      */
1000     xsltReverseCompMatch(ret);
1001
1002     /*
1003      * Set-up the priority
1004      */
1005     if (((ret->steps[0].op == XSLT_OP_ELEM) ||
1006          (ret->steps[0].op == XSLT_OP_ATTR)) &&
1007         (ret->steps[0].value != NULL) &&
1008         (ret->steps[1].op == XSLT_OP_END)) {
1009         ret->priority = 0;
1010     } else if ((ret->steps[0].op == XSLT_OP_PI) &&
1011                (ret->steps[0].value != NULL) &&
1012                (ret->steps[1].op == XSLT_OP_END)) {
1013         ret->priority = 0;
1014     } else if ((ret->steps[0].op == XSLT_OP_NS) &&
1015                (ret->steps[0].value != NULL) &&
1016                (ret->steps[1].op == XSLT_OP_END)) {
1017         ret->priority = -0.25;
1018     } else if (((ret->steps[0].op == XSLT_OP_PI) ||
1019                 (ret->steps[0].op == XSLT_OP_TEXT) ||
1020                 (ret->steps[0].op == XSLT_OP_NODE) ||
1021                 (ret->steps[0].op == XSLT_OP_COMMENT)) &&
1022                (ret->steps[1].op == XSLT_OP_END)) {
1023         ret->priority = -0.5;
1024     } else {
1025         ret->priority = 0.5;
1026     }
1027
1028     xsltFreeParserContext(ctxt);
1029     return(ret);
1030
1031 error:
1032     xsltFreeParserContext(ctxt);
1033     xsltFreeCompMatch(ret);
1034     return(NULL);
1035
1036 }
1037
1038
1039 /************************************************************************
1040  *                                                                      *
1041  *                      Module interfaces                               *
1042  *                                                                      *
1043  ************************************************************************/
1044
1045 /**
1046  * xsltAddTemplate:
1047  * @style: an XSLT stylesheet
1048  * @cur: an XSLT template
1049  *
1050  * Register the XSLT pattern associated to @cur
1051  *
1052  * Returns -1 in case of error, 0 otherwise
1053  */
1054 int
1055 xsltAddTemplate(xsltStylesheetPtr style, xsltTemplatePtr cur) {
1056     xsltCompMatchPtr pat, list, *top;
1057     const xmlChar *name = NULL;
1058     xmlChar *p, *pattern, tmp;
1059
1060     if ((style == NULL) || (cur == NULL))
1061         return(-1);
1062
1063     p = cur->match;
1064     if (p == NULL)
1065         return(-1);
1066
1067 next_pattern:
1068     if (*p == 0)
1069         return(0);
1070     /*
1071      * get a compiled form of the pattern
1072      */
1073     pattern = p;
1074     while ((*p != 0) && (*p != '|')) {
1075         /* TODO: handle string escaping "a | b" in patterns ... */
1076         p++;
1077     }
1078
1079     tmp = *p;
1080     *p = 0;
1081     pat = xsltCompilePattern(pattern);
1082     *p = tmp;
1083     if (tmp != 0)
1084         p++;
1085     if (pat == NULL)
1086         return(-1);
1087     pat->template = cur;
1088     if (cur->priority != XSLT_PAT_NO_PRIORITY)
1089         pat->priority = cur->priority;
1090
1091     /*
1092      * insert it in the hash table list corresponding to its lookup name
1093      */
1094     switch (pat->steps[0].op) {
1095         case XSLT_OP_ATTR:
1096             if (pat->steps[0].value != NULL)
1097                 name = pat->steps[0].value;
1098             else
1099                 top = (xsltCompMatchPtr *) &(style->attrMatch);
1100             break;
1101         case XSLT_OP_ELEM:
1102         case XSLT_OP_CHILD:
1103         case XSLT_OP_PARENT:
1104         case XSLT_OP_ANCESTOR:
1105         case XSLT_OP_ID:
1106         case XSLT_OP_KEY:
1107         case XSLT_OP_NS:
1108              name = pat->steps[0].value;
1109              break;
1110         case XSLT_OP_ROOT:
1111              top = (xsltCompMatchPtr *) &(style->rootMatch);
1112              break;
1113         case XSLT_OP_ALL:
1114              top = (xsltCompMatchPtr *) &(style->elemMatch);
1115              break;
1116         case XSLT_OP_END:
1117         case XSLT_OP_PREDICATE:
1118             xsltGenericError(xsltGenericErrorContext,
1119                     "xsltAddTemplate: invalid compiled pattern\n");
1120             xsltFreeCompMatch(pat);
1121             return(-1);
1122         /*
1123          * TODO: some flags at the top level about type based patterns
1124          *       would be faster than inclusion in the hash table.
1125          */
1126         case XSLT_OP_PI:
1127             if (pat->steps[0].value != NULL)
1128                 name = pat->steps[0].value;
1129             else
1130                 top = (xsltCompMatchPtr *) &(style->piMatch);
1131             break;
1132         case XSLT_OP_COMMENT:
1133             top = (xsltCompMatchPtr *) &(style->commentMatch);
1134             break;
1135         case XSLT_OP_TEXT:
1136             top = (xsltCompMatchPtr *) &(style->textMatch);
1137             break;
1138         case XSLT_OP_NODE:
1139             if (pat->steps[0].value != NULL)
1140                 name = pat->steps[0].value;
1141             else
1142                 top = (xsltCompMatchPtr *) &(style->elemMatch);
1143
1144             break;
1145     }
1146     if (name != NULL) {
1147         if (style->templatesHash == NULL) {
1148             style->templatesHash = xmlHashCreate(0);
1149             if (style->templatesHash == NULL) {
1150                 xsltFreeCompMatch(pat);
1151                 return(-1);
1152             }
1153 #ifdef DEBUG_PARSING
1154             xsltGenericDebug(xsltGenericDebugContext,
1155                     "xsltAddTemplate: created template hash\n");
1156 #endif
1157             xmlHashAddEntry(style->templatesHash, name, pat);
1158 #ifdef DEBUG_PARSING
1159             xsltGenericDebug(xsltGenericDebugContext,
1160                     "xsltAddTemplate: added new hash %s\n", name);
1161 #endif
1162         } else {
1163             list = (xsltCompMatchPtr) xmlHashLookup(style->templatesHash, name);
1164             if (list == NULL) {
1165                 xmlHashAddEntry(style->templatesHash, name, pat);
1166 #ifdef DEBUG_PARSING
1167                 xsltGenericDebug(xsltGenericDebugContext,
1168                         "xsltAddTemplate: added new hash %s\n", name);
1169 #endif
1170             } else {
1171                 /*
1172                  * Note '<=' since one must choose among the matching
1173                  * template rules that are left, the one that occurs
1174                  * last in the stylesheet
1175                  */
1176                 if (list->priority <= pat->priority) {
1177                     pat->next = list;
1178                     xmlHashUpdateEntry(style->templatesHash, name, pat, NULL);
1179 #ifdef DEBUG_PARSING
1180                     xsltGenericDebug(xsltGenericDebugContext,
1181                             "xsltAddTemplate: added head hash for %s\n", name);
1182 #endif
1183                 } else {
1184                     while (list->next != NULL) {
1185                         if (list->next->priority <= pat->priority)
1186                             break;
1187                     }
1188                     pat->next = list->next;
1189                     list->next = pat;
1190                 }
1191             }
1192         }
1193     } else if (top != NULL) {
1194         list = *top;
1195         if (list == NULL) {
1196             *top = pat;
1197             pat->next = NULL;
1198         } else if (list->priority <= pat->priority) {
1199             pat->next = list;
1200             *top = pat;
1201         } else {
1202             while (list->next != NULL) {
1203                 if (list->next->priority <= pat->priority)
1204                     break;
1205             }
1206             pat->next = list->next;
1207             list->next = pat;
1208         }
1209     } else {
1210         xsltGenericError(xsltGenericErrorContext,
1211                 "xsltAddTemplate: invalid compiled pattern\n");
1212         xsltFreeCompMatch(pat);
1213         return(-1);
1214     }
1215     if (*p != 0)
1216         goto next_pattern;
1217     return(0);
1218 }
1219
1220 /**
1221  * xsltGetTemplate:
1222  * @style: an XSLT stylesheet
1223  * @node: an XML Node
1224  *
1225  * Finds the template applying to this node
1226  *
1227  * Returns the xsltTemplatePtr or NULL if not found
1228  */
1229 xsltTemplatePtr
1230 xsltGetTemplate(xsltStylesheetPtr style, xmlNodePtr node) {
1231     xsltTemplatePtr ret = NULL;
1232     const xmlChar *name = NULL;
1233     xsltCompMatchPtr list = NULL;
1234
1235     if ((style == NULL) || (node == NULL))
1236         return(NULL);
1237
1238     /* TODO : handle IDs/keys here ! */
1239     if (style->templatesHash != NULL) {
1240         /*
1241          * Use the top name as selector
1242          */
1243         switch (node->type) {
1244             case XML_ELEMENT_NODE:
1245             case XML_ATTRIBUTE_NODE:
1246             case XML_PI_NODE:
1247                 name = node->name;
1248                 break;
1249             case XML_DOCUMENT_NODE:
1250             case XML_HTML_DOCUMENT_NODE:
1251             case XML_TEXT_NODE:
1252             case XML_CDATA_SECTION_NODE:
1253             case XML_COMMENT_NODE:
1254             case XML_ENTITY_REF_NODE:
1255             case XML_ENTITY_NODE:
1256             case XML_DOCUMENT_TYPE_NODE:
1257             case XML_DOCUMENT_FRAG_NODE:
1258             case XML_NOTATION_NODE:
1259             case XML_DTD_NODE:
1260             case XML_ELEMENT_DECL:
1261             case XML_ATTRIBUTE_DECL:
1262             case XML_ENTITY_DECL:
1263             case XML_NAMESPACE_DECL:
1264             case XML_XINCLUDE_START:
1265             case XML_XINCLUDE_END:
1266                 break;
1267             default:
1268                 return(NULL);
1269
1270         }
1271     }
1272     if (name != NULL) {
1273         /*
1274          * find the list of appliable expressions based on the name
1275          */
1276         list = (xsltCompMatchPtr) xmlHashLookup(style->templatesHash, name);
1277     }
1278     while (list != NULL) {
1279         if (xsltTestCompMatch(list, node)) {
1280             ret = list->template;
1281             break;
1282         }
1283         list = list->next;
1284     }
1285     list = NULL;
1286
1287     /*
1288      * find alternate generic matches
1289      */
1290     switch (node->type) {
1291         case XML_ELEMENT_NODE:
1292             list = style->elemMatch;
1293             break;
1294         case XML_ATTRIBUTE_NODE:
1295             list = style->attrMatch;
1296             break;
1297         case XML_PI_NODE:
1298             list = style->piMatch;
1299             break;
1300         case XML_DOCUMENT_NODE:
1301         case XML_HTML_DOCUMENT_NODE:
1302             list = style->rootMatch;
1303             break;
1304         case XML_TEXT_NODE:
1305         case XML_CDATA_SECTION_NODE:
1306             list = style->textMatch;
1307             break;
1308         case XML_COMMENT_NODE:
1309             list = style->commentMatch;
1310             break;
1311         case XML_ENTITY_REF_NODE:
1312         case XML_ENTITY_NODE:
1313         case XML_DOCUMENT_TYPE_NODE:
1314         case XML_DOCUMENT_FRAG_NODE:
1315         case XML_NOTATION_NODE:
1316         case XML_DTD_NODE:
1317         case XML_ELEMENT_DECL:
1318         case XML_ATTRIBUTE_DECL:
1319         case XML_ENTITY_DECL:
1320         case XML_NAMESPACE_DECL:
1321         case XML_XINCLUDE_START:
1322         case XML_XINCLUDE_END:
1323             break;
1324         default:
1325             break;
1326
1327     }
1328     while ((list != NULL) &&
1329            ((ret == NULL)  || (list->priority > ret->priority))) {
1330         if (xsltTestCompMatch(list, node)) {
1331             ret = list->template;
1332             break;
1333         }
1334     }
1335     return(ret);
1336 }
1337
1338
1339 /**
1340  * xsltFreeTemplateHashes:
1341  * @style: an XSLT stylesheet
1342  *
1343  * Free up the memory used by xsltAddTemplate/xsltGetTemplate mechanism
1344  */
1345 void
1346 xsltFreeTemplateHashes(xsltStylesheetPtr style) {
1347     if (style->templatesHash != NULL)
1348         xmlHashFree((xmlHashTablePtr) style->templatesHash,
1349                     (xmlHashDeallocator) xsltFreeCompMatchList);
1350     if (style->rootMatch != NULL)
1351         xsltFreeCompMatchList(style->rootMatch);
1352     if (style->elemMatch != NULL)
1353         xsltFreeCompMatchList(style->elemMatch);
1354     if (style->attrMatch != NULL)
1355         xsltFreeCompMatchList(style->attrMatch);
1356     if (style->parentMatch != NULL)
1357         xsltFreeCompMatchList(style->parentMatch);
1358     if (style->textMatch != NULL)
1359         xsltFreeCompMatchList(style->textMatch);
1360     if (style->piMatch != NULL)
1361         xsltFreeCompMatchList(style->piMatch);
1362     if (style->commentMatch != NULL)
1363         xsltFreeCompMatchList(style->commentMatch);
1364 }
1365
1366 /**
1367  * xsltFindTemplate:
1368  * @style: an XSLT stylesheet
1369  * @name: the template name
1370  * @nameURI: the template name URI
1371  *
1372  * Finds the named template.
1373  *
1374  * Returns the xsltTemplatePtr or NULL if not found
1375  */
1376 xsltTemplatePtr
1377 xsltFindTemplate(xsltStylesheetPtr style, const xmlChar *name,
1378                 const xmlChar *nameURI) {
1379     xsltTemplatePtr cur;
1380
1381     if ((style == NULL) || (name == NULL))
1382         return(NULL);
1383
1384     /* TODO: apply stylesheet import order */
1385     cur = style->templates;
1386     while (cur != NULL) {
1387         if (xmlStrEqual(name, cur->name)) {
1388             if (((nameURI == NULL) && (cur->nameURI == NULL)) ||
1389                 ((nameURI != NULL) && (cur->nameURI != NULL) &&
1390                  (xmlStrEqual(nameURI, cur->nameURI)))) {
1391                 return(cur);
1392             }
1393         }
1394         cur = cur->next;
1395     }
1396     return(NULL);
1397 }
1398