libxslt/pattern.c

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