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
  25 /* #define DEBUG_PARSING */
  26
  27 #define TODO                                                            \
  28     xsltGenericError(xsltGenericErrorContext,                           \
  29             "Unimplemented block at %s:%d\n",                           \
  30             __FILE__, __LINE__);
  31
  32 /*
  33  * To cleanup
  34  */
  35 xmlChar *xmlSplitQName2(const xmlChar *name, xmlChar **prefix);
  36
  37 /*
  38  * There is no XSLT specific error reporting module yet
  39  */
  40 #define xsltGenericError xmlGenericError
  41 #define xsltGenericErrorContext xmlGenericErrorContext
  42
  43 /*
  44  * Types are private:
  45  */
  46
  47 typedef enum {
  48     XSLT_OP_END=0,
  49     XSLT_OP_ROOT,
  50     XSLT_OP_ELEM,
  51     XSLT_OP_CHILD,
  52     XSLT_OP_ATTR,
  53     XSLT_OP_PARENT,
  54     XSLT_OP_ANCESTOR,
  55     XSLT_OP_ID,
  56     XSLT_OP_KEY,
  57     XSLT_OP_NS,
  58     XSLT_OP_ALL,
  59     XSLT_OP_PREDICATE
  60 } xsltOp;
  61
  62
  63 typedef struct _xsltStepOp xsltStepOp;
  64 typedef xsltStepOp *xsltStepOpPtr;
  65 struct _xsltStepOp {
  66     xsltOp op;
  67     xmlChar *value;
  68     xmlChar *value2;
  69 };
  70
  71 typedef struct _xsltCompMatch xsltCompMatch;
  72 typedef xsltCompMatch *xsltCompMatchPtr;
  73 struct _xsltCompMatch {
  74     struct _xsltCompMatch *next; /* siblings in the name hash */
  75     int priority;                /* the priority */
  76     xsltTemplatePtr template;    /* the associated template */
  77
  78     /* TODO fix the statically allocated size */
  79     int nbStep;
  80     int maxStep;
  81     xsltStepOp steps[20];        /* ops for computation */
  82 };
  83
  84 typedef struct _xsltParserContext xsltParserContext;
  85 typedef xsltParserContext *xsltParserContextPtr;
  86 struct _xsltParserContext {
  87     const xmlChar *cur;                 /* the current char being parsed */
  88     const xmlChar *base;                /* the full expression */
  89     int error;                          /* error code */
  90     xsltCompMatchPtr comp;              /* the result */
  91 };
  92
  93 /************************************************************************
  94  *                                                                      *
  95  *                      Type functions                                  *
  96  *                                                                      *
  97  ************************************************************************/
  98
  99 /**
 100  * xsltNewCompMatch:
 101  *
 102  * Create a new XSLT CompMatch
 103  *
 104  * Returns the newly allocated xsltCompMatchPtr or NULL in case of error
 105  */
 106 xsltCompMatchPtr
 107 xsltNewCompMatch(void) {
 108     xsltCompMatchPtr cur;
 109
 110     cur = (xsltCompMatchPtr) xmlMalloc(sizeof(xsltCompMatch));
 111     if (cur == NULL) {
 112         xsltGenericError(xsltGenericErrorContext,
 113                 "xsltNewCompMatch : malloc failed\n");
 114         return(NULL);
 115     }
 116     memset(cur, 0, sizeof(xsltCompMatch));
 117     cur->maxStep = 20;
 118     return(cur);
 119 }
 120
 121 /**
 122  * xsltFreeCompMatch:
 123  * @comp:  an XSLT comp
 124  *
 125  * Free up the memory allocated by @comp
 126  */
 127 void
 128 xsltFreeCompMatch(xsltCompMatchPtr comp) {
 129     xsltStepOpPtr op;
 130     int i;
 131
 132     if (comp == NULL)
 133         return;
 134     for (i = 0;i < comp->nbStep;i++) {
 135         op = &comp->steps[i];
 136         if (op->value != NULL)
 137             xmlFree(op->value);
 138         if (op->value2 != NULL)
 139             xmlFree(op->value2);
 140     }
 141     memset(comp, -1, sizeof(xsltCompMatch));
 142     xmlFree(comp);
 143 }
 144
 145 /**
 146  * xsltFreeCompMatchList:
 147  * @comp:  an XSLT comp list
 148  *
 149  * Free up the memory allocated by all the elements of @comp
 150  */
 151 void
 152 xsltFreeCompMatchList(xsltCompMatchPtr comp) {
 153     xsltCompMatchPtr cur;
 154
 155     while (comp != NULL) {
 156         cur = comp;
 157         comp = comp->next;
 158         xsltFreeCompMatch(cur);
 159     }
 160 }
 161
 162 /**
 163  * xsltNewParserContext:
 164  *
 165  * Create a new XSLT ParserContext
 166  *
 167  * Returns the newly allocated xsltParserContextPtr or NULL in case of error
 168  */
 169 xsltParserContextPtr
 170 xsltNewParserContext(void) {
 171     xsltParserContextPtr cur;
 172
 173     cur = (xsltParserContextPtr) xmlMalloc(sizeof(xsltParserContext));
 174     if (cur == NULL) {
 175         xsltGenericError(xsltGenericErrorContext,
 176                 "xsltNewParserContext : malloc failed\n");
 177         return(NULL);
 178     }
 179     memset(cur, 0, sizeof(xsltParserContext));
 180     return(cur);
 181 }
 182
 183 /**
 184  * xsltFreeParserContext:
 185  * @ctxt:  an XSLT parser context
 186  *
 187  * Free up the memory allocated by @ctxt
 188  */
 189 void
 190 xsltFreeParserContext(xsltParserContextPtr ctxt) {
 191     if (ctxt == NULL)
 192         return;
 193     memset(ctxt, -1, sizeof(xsltParserContext));
 194     xmlFree(ctxt);
 195 }
 196
 197 /**
 198  * xsltCompMatchAdd:
 199  * @comp:  the compiled match expression
 200  * @op:  an op
 201  * @value:  the first value
 202  * @value2:  the second value
 203  *
 204  * Add an step to an XSLT Compiled Match
 205  *
 206  * Returns -1 in case of failure, 0 otherwise.
 207  */
 208 int
 209 xsltCompMatchAdd(xsltCompMatchPtr comp, xsltOp op, xmlChar *value,
 210                    xmlChar *value2) {
 211     if (comp->nbStep >= 20) {
 212         xsltGenericError(xsltGenericErrorContext,
 213                 "xsltCompMatchAddOp: overflow\n");
 214         return(-1);
 215     }
 216     comp->steps[comp->nbStep].op = op;
 217     comp->steps[comp->nbStep].value = value;
 218     comp->steps[comp->nbStep].value2 = value2;
 219     comp->nbStep++;
 220     return(0);
 221 }
 222
 223 /**
 224  * xsltReverseCompMatch:
 225  * @comp:  the compiled match expression
 226  *
 227  * reverse all the stack of expressions
 228  */
 229 void
 230 xsltReverseCompMatch(xsltCompMatchPtr comp) {
 231     int i = 0;
 232     int j = comp->nbStep - 1;
 233
 234     while (j > i) {
 235         register xmlChar *tmp;
 236         register xsltOp op;
 237         tmp = comp->steps[i].value;
 238         comp->steps[i].value = comp->steps[j].value;
 239         comp->steps[j].value = tmp;
 240         tmp = comp->steps[i].value2;
 241         comp->steps[i].value2 = comp->steps[j].value2;
 242         comp->steps[j].value2 = tmp;
 243         op = comp->steps[i].op;
 244         comp->steps[i].op = comp->steps[j].op;
 245         comp->steps[j].op = op;
 246         j--;
 247         i++;
 248     }
 249     comp->steps[comp->nbStep++].op = XSLT_OP_END;
 250 }
 251
 252 /************************************************************************
 253  *                                                                      *
 254  *              The interpreter for the precompiled patterns            *
 255  *                                                                      *
 256  ************************************************************************/
 257
 258 /**
 259  * xsltTestCompMatch:
 260  * @comp: the precompiled pattern
 261  * @node: a node
 262  *
 263  * Test wether the node matches the pattern
 264  *
 265  * Returns 1 if it matches, 0 if it doesn't and -1 in case of failure
 266  */
 267 int
 268 xsltTestCompMatch(xsltCompMatchPtr comp, xmlNodePtr node) {
 269     int i;
 270     xsltStepOpPtr step;
 271
 272     if ((comp == NULL) || (node == NULL)) {
 273         xsltGenericError(xsltGenericErrorContext,
 274                 "xsltTestCompMatch: null arg\n");
 275         return(-1);
 276     }
 277     for (i = 0;i < comp->nbStep;i++) {
 278         step = &comp->steps[i];
 279         switch (step->op) {
 280             case XSLT_OP_END:
 281                 return(1);
 282             case XSLT_OP_ROOT:
 283                 if ((node->type != XML_DOCUMENT_NODE) &&
 284                     (node->type != XML_HTML_DOCUMENT_NODE))
 285                     return(0);
 286                 continue;
 287             case XSLT_OP_ELEM:
 288                 if (node->type != XML_ELEMENT_NODE)
 289                     return(0);
 290                 if (step->value == NULL)
 291                     continue;
 292                 if (!xmlStrEqual(step->value, node->name))
 293                     return(0);
 294                 /* TODO: Handle namespace ... */
 295                 continue;
 296             case XSLT_OP_CHILD:
 297                 TODO /* Hummm !!! */
 298                 return(0);
 299             case XSLT_OP_ATTR:
 300                 if (node->type != XML_ATTRIBUTE_NODE)
 301                     return(0);
 302                 if (step->value == NULL)
 303                     continue;
 304                 if (!xmlStrEqual(step->value, node->name))
 305                     return(0);
 306                 /* TODO: Handle namespace ... */
 307                 continue;
 308             case XSLT_OP_PARENT:
 309                 node = node->parent;
 310                 if (node == NULL)
 311                     return(0);
 312                 if (step->value == NULL)
 313                     continue;
 314                 if (!xmlStrEqual(step->value, node->name))
 315                     return(0);
 316                 /* TODO: Handle namespace ... */
 317                 continue;
 318             case XSLT_OP_ANCESTOR:
 319                 /* TODO: implement coalescing of ANCESTOR/NODE ops */
 320                 if (step->value == NULL) {
 321                     i++;
 322                     step = &comp->steps[i];
 323                     if (step->op == XSLT_OP_ROOT)
 324                         return(1);
 325                     if (step->op != XSLT_OP_ELEM)
 326                         return(0);
 327                     if (step->value == NULL)
 328                         return(-1);
 329                 }
 330                 if (node == NULL)
 331                     return(0);
 332                 node = node->parent;
 333                 while (node != NULL) {
 334                     if (node == NULL)
 335                         return(0);
 336                     if (xmlStrEqual(step->value, node->name)) {
 337                         /* TODO: Handle namespace ... */
 338                         break;
 339                     }
 340                 }
 341                 if (node == NULL)
 342                     return(0);
 343                 continue;
 344             case XSLT_OP_ID:
 345                 TODO /* Handle IDs, might be done differently */
 346                 break;
 347             case XSLT_OP_KEY:
 348                 TODO /* Handle Keys, might be done differently */
 349                 break;
 350             case XSLT_OP_NS:
 351                 TODO /* Handle Namespace */
 352                 break;
 353             case XSLT_OP_ALL:
 354                 TODO /* Handle Namespace */
 355                 break;
 356             case XSLT_OP_PREDICATE:
 357                 TODO /* Handle Namespace */
 358                 break;
 359         }
 360     }
 361     return(1);
 362 }
 363
 364 /************************************************************************
 365  *                                                                      *
 366  *                      Dedicated parser for templates                  *
 367  *                                                                      *
 368  ************************************************************************/
 369
 370 #define CUR (*ctxt->cur)
 371 #define SKIP(val) ctxt->cur += (val)
 372 #define NXT(val) ctxt->cur[(val)]
 373 #define CUR_PTR ctxt->cur
 374
 375 #define SKIP_BLANKS                                                     \
 376     while (IS_BLANK(CUR)) NEXT
 377
 378 #define CURRENT (*ctxt->cur)
 379 #define NEXT ((*ctxt->cur) ?  ctxt->cur++: ctxt->cur)
 380
 381
 382 #define PUSH(op, val, val2)                                             \
 383     if (xsltCompMatchAdd(ctxt->comp, (op), (val), (val2))) goto error;
 384
 385 /**
 386  * xsltScanName:
 387  * @ctxt:  the XPath Parser context
 388  *
 389  * Trickery: parse an XML name but without consuming the input flow
 390  * Needed to avoid insanity in the parser state.
 391  *
 392  * [4] NameChar ::= Letter | Digit | '.' | '-' | '_' | ':' |
 393  *                  CombiningChar | Extender
 394  *
 395  * [5] Name ::= (Letter | '_' | ':') (NameChar)*
 396  *
 397  * [6] Names ::= Name (S Name)*
 398  *
 399  * Returns the Name parsed or NULL
 400  */
 401
 402 xmlChar *
 403 xsltScanName(xsltParserContextPtr ctxt) {
 404     xmlChar buf[XML_MAX_NAMELEN];
 405     int len = 0;
 406
 407     SKIP_BLANKS;
 408     if (!IS_LETTER(CUR) && (CUR != '_') &&
 409         (CUR != ':')) {
 410         return(NULL);
 411     }
 412
 413     while ((IS_LETTER(NXT(len))) || (IS_DIGIT(NXT(len))) ||
 414            (NXT(len) == '.') || (NXT(len) == '-') ||
 415            (NXT(len) == '_') || (NXT(len) == ':') ||
 416            (IS_COMBINING(NXT(len))) ||
 417            (IS_EXTENDER(NXT(len)))) {
 418         buf[len] = NXT(len);
 419         len++;
 420         if (len >= XML_MAX_NAMELEN) {
 421             xmlGenericError(xmlGenericErrorContext,
 422                "xmlScanName: reached XML_MAX_NAMELEN limit\n");
 423             while ((IS_LETTER(NXT(len))) || (IS_DIGIT(NXT(len))) ||
 424                    (NXT(len) == '.') || (NXT(len) == '-') ||
 425                    (NXT(len) == '_') || (NXT(len) == ':') ||
 426                    (IS_COMBINING(NXT(len))) ||
 427                    (IS_EXTENDER(NXT(len))))
 428                  len++;
 429             break;
 430         }
 431     }
 432     SKIP(len);
 433     return(xmlStrndup(buf, len));
 434 }
 435 /*
 436  * Compile the XSLT LocationPathPattern
 437  * [3] IdKeyPattern ::= 'id' '(' Literal ')'
 438  *                    | 'key' '(' Literal ',' Literal ')'
 439  */
 440
 441 /**
 442  * xsltCompileStepPattern:
 443  * @comp:  the compilation context
 444  * @token:  a posible precompiled name
 445  *
 446  * Compile the XSLT StepPattern and generates a precompiled
 447  * form suitable for fast matching.
 448  *
 449  * [5] StepPattern ::= ChildOrAttributeAxisSpecifier NodeTest Predicate*
 450  * [6] ChildOrAttributeAxisSpecifier ::= AbbreviatedAxisSpecifier
 451  *                                     | ('child' | 'attribute') '::'
 452  * from XPath
 453  * [7]  NodeTest ::= NameTest
 454  *                 | NodeType '(' ')'
 455  *                 | 'processing-instruction' '(' Literal ')'
 456  * [8] Predicate ::= '[' PredicateExpr ']'
 457  * [9] PredicateExpr ::= Expr
 458  * [13] AbbreviatedAxisSpecifier ::= '@'?
 459  * [37] NameTest ::= '*' | NCName ':' '*' | QName
 460  */
 461
 462 void
 463 xsltCompileStepPattern(xsltParserContextPtr ctxt, xmlChar *token) {
 464     SKIP_BLANKS;
 465     if ((token == NULL) && (CUR == '@')) {
 466         token = xsltScanName(ctxt);
 467         if (token == NULL) {
 468             xsltGenericError(xsltGenericErrorContext,
 469                     "xsltCompilePattern : Name expected\n");
 470             ctxt->error = 1;
 471             return;
 472         }
 473     }
 474     if (token == NULL)
 475         token = xsltScanName(ctxt);
 476     if (token == NULL) {
 477         xsltGenericError(xsltGenericErrorContext,
 478                 "xsltCompilePattern : Name expected\n");
 479         ctxt->error = 1;
 480         return;
 481     }
 482     SKIP_BLANKS;
 483     if (CUR == '(') {
 484         TODO;
 485         /* if (xmlStrEqual(token, "processing-instruction")) */
 486     } else if (CUR == ':') {
 487         TODO;
 488     } else if (CUR == '*') {
 489         TODO;
 490     } else {
 491         PUSH(XSLT_OP_ELEM, token, NULL);
 492     }
 493     SKIP_BLANKS;
 494     while (CUR == '[') {
 495         TODO;
 496     }
 497     return;
 498 error:
 499     ctxt->error = 1;
 500 }
 501
 502 /**
 503  * xsltCompileRelativePathPattern:
 504  * @comp:  the compilation context
 505  * @token:  a posible precompiled name
 506  *
 507  * Compile the XSLT RelativePathPattern and generates a precompiled
 508  * form suitable for fast matching.
 509  *
 510  * [4] RelativePathPattern ::= StepPattern
 511  *                           | RelativePathPattern '/' StepPattern
 512  *                           | RelativePathPattern '//' StepPattern
 513  */
 514 void
 515 xsltCompileRelativePathPattern(xsltParserContextPtr ctxt, xmlChar *token) {
 516     xsltCompileStepPattern(ctxt, token);
 517     if (ctxt->error)
 518         goto error;
 519     SKIP_BLANKS;
 520     while ((CUR != 0) && (CUR != '|')) {
 521         if ((CUR == '/') && (NXT(1) == '/')) {
 522             PUSH(XSLT_OP_ANCESTOR, NULL, NULL);
 523             NEXT;
 524             NEXT;
 525             SKIP_BLANKS;
 526             xsltCompileStepPattern(ctxt, NULL);
 527         } else if (CUR == '/') {
 528             PUSH(XSLT_OP_PARENT, NULL, NULL);
 529             NEXT;
 530             SKIP_BLANKS;
 531             if ((CUR != 0) || (CUR == '|')) {
 532                 xsltCompileRelativePathPattern(ctxt, NULL);
 533             }
 534         } else {
 535             ctxt->error = 1;
 536         }
 537         if (ctxt->error)
 538             goto error;
 539         SKIP_BLANKS;
 540     }
 541 error:
 542     return;
 543 }
 544
 545 /**
 546  * xsltCompileLocationPathPattern:
 547  * @comp:  the compilation context
 548  *
 549  * Compile the XSLT LocationPathPattern and generates a precompiled
 550  * form suitable for fast matching.
 551  *
 552  * [2] LocationPathPattern ::= '/' RelativePathPattern?
 553  *                           | IdKeyPattern (('/' | '//') RelativePathPattern)?
 554  *                           | '//'? RelativePathPattern
 555  */
 556 void
 557 xsltCompileLocationPathPattern(xsltParserContextPtr ctxt) {
 558     SKIP_BLANKS;
 559     if ((CUR == '/') && (NXT(1) == '/')) {
 560         /*
 561          * since we reverse the query
 562          * a leading // can be safely ignored
 563          */
 564         NEXT;
 565         NEXT;
 566         xsltCompileRelativePathPattern(ctxt, NULL);
 567     } else if (CUR == '/') {
 568         /*
 569          * We need to find root as the parent
 570          */
 571         NEXT;
 572         SKIP_BLANKS;
 573         PUSH(XSLT_OP_ROOT, NULL, NULL);
 574         PUSH(XSLT_OP_PARENT, NULL, NULL);
 575         if ((CUR != 0) || (CUR == '|')) {
 576             xsltCompileRelativePathPattern(ctxt, NULL);
 577         }
 578     } else {
 579         xmlChar *name;
 580         name = xsltScanName(ctxt);
 581         if (name == NULL) {
 582             xsltGenericError(xsltGenericErrorContext,
 583                     "xsltCompilePattern : Name expected\n");
 584             ctxt->error = 1;
 585             return;
 586         }
 587         SKIP_BLANKS;
 588         if (CUR == '(') {
 589             TODO
 590         }
 591         xsltCompileRelativePathPattern(ctxt, name);
 592     }
 593 error:
 594     return;
 595 }
 596
 597 /**
 598  * xsltCompilePattern:
 599  * @pattern an XSLT pattern
 600  *
 601  * Compile the XSLT pattern and generates a precompiled form suitable
 602  * for fast matching.
 603  * Note that the splitting as union of patterns is expected to be handled
 604  * by the caller
 605  *
 606  * [1] Pattern ::= LocationPathPattern | Pattern '|' LocationPathPattern
 607  *
 608  * Returns the generated xsltCompMatchPtr or NULL in case of failure
 609  */
 610
 611 xsltCompMatchPtr
 612 xsltCompilePattern(const xmlChar *pattern) {
 613     xsltParserContextPtr ctxt;
 614     xsltCompMatchPtr ret;
 615     const xmlChar *cur;
 616
 617     if (pattern == NULL) {
 618         xsltGenericError(xsltGenericErrorContext,
 619                 "xsltCompilePattern : NULL pattern\n");
 620         return(NULL);
 621     }
 622
 623 #ifdef DEBUG_PARSING
 624     xsltGenericError(xsltGenericErrorContext,
 625             "xsltCompilePattern : parsing '%s'\n", pattern);
 626 #endif
 627
 628     cur = pattern;
 629     while (IS_BLANK(*cur)) cur++;
 630     if (*cur == 0) {
 631         xsltGenericError(xsltGenericErrorContext,
 632                 "xsltCompilePattern : NULL pattern\n");
 633         return(NULL);
 634     }
 635     ctxt = xsltNewParserContext();
 636     if (ctxt == NULL)
 637         return(NULL);
 638     ret = xsltNewCompMatch();
 639     if (ret == NULL) {
 640         xsltFreeParserContext(ctxt);
 641         return(NULL);
 642     }
 643
 644     ctxt->comp = ret;
 645     ctxt->base = pattern;
 646     ctxt->cur = cur;
 647     xsltCompileLocationPathPattern(ctxt);
 648     if (ctxt->error)
 649         goto error;
 650
 651     /*
 652      * Reverse for faster interpretation.
 653      */
 654     xsltReverseCompMatch(ret);
 655
 656     xsltFreeParserContext(ctxt);
 657     return(ret);
 658
 659 error:
 660     xsltFreeParserContext(ctxt);
 661     xsltFreeCompMatch(ret);
 662     return(NULL);
 663
 664 }
 665
 666
 667 /************************************************************************
 668  *                                                                      *
 669  *                      Module interfaces                               *
 670  *                                                                      *
 671  ************************************************************************/
 672
 673 /**
 674  * xsltAddTemplate:
 675  * @style: an XSLT stylesheet
 676  * @cur: an XSLT template
 677  *
 678  * Register the XSLT pattern associated to @cur
 679  *
 680  * Returns -1 in case of error, 0 otherwise
 681  */
 682 int
 683 xsltAddTemplate(xsltStylesheetPtr style, xsltTemplatePtr cur) {
 684     xsltCompMatchPtr pat, list;
 685     const xmlChar *name;
 686
 687     /*
 688      * get a compiled form of the pattern
 689      */
 690     /* TODO : handle | in patterns as multple pat !!! */
 691     pat = xsltCompilePattern(cur->match);
 692     if (pat == NULL)
 693         return(-1);
 694     pat->template = cur;
 695     if (cur->priority != XSLT_PAT_NO_PRIORITY)
 696         pat->priority = cur->priority;
 697
 698     /*
 699      * insert it in the hash table list corresponding to its lookup name
 700      */
 701     switch (pat->steps[0].op) {
 702         case XSLT_OP_ELEM:
 703         case XSLT_OP_CHILD:
 704         case XSLT_OP_ATTR:
 705         case XSLT_OP_PARENT:
 706         case XSLT_OP_ANCESTOR:
 707         case XSLT_OP_ID:
 708         case XSLT_OP_KEY:
 709         case XSLT_OP_NS:
 710              name = pat->steps[0].value;
 711              break;
 712         case XSLT_OP_ROOT:
 713              name = (const xmlChar *) "/";
 714              break;
 715         case XSLT_OP_ALL:
 716              name = (const xmlChar *) "*";
 717              break;
 718         case XSLT_OP_END:
 719         case XSLT_OP_PREDICATE:
 720             xsltGenericError(xsltGenericErrorContext,
 721                     "xsltAddTemplate: invalid compiled pattern\n");
 722             xsltFreeCompMatch(pat);
 723             return(-1);
 724     }
 725     if (name == NULL) {
 726         xsltGenericError(xsltGenericErrorContext,
 727                 "xsltAddTemplate: invalid compiled pattern\n");
 728         xsltFreeCompMatch(pat);
 729         return(-1);
 730     }
 731     if (style->templatesHash == NULL) {
 732         style->templatesHash = xmlHashCreate(0);
 733         if (style->templatesHash == NULL) {
 734             xsltFreeCompMatch(pat);
 735             return(-1);
 736         }
 737 #ifdef DEBUG_PARSING
 738         xsltGenericError(xsltGenericErrorContext,
 739                 "xsltAddTemplate: created template hash\n");
 740 #endif
 741         xmlHashAddEntry(style->templatesHash, name, pat);
 742 #ifdef DEBUG_PARSING
 743         xsltGenericError(xsltGenericErrorContext,
 744                 "xsltAddTemplate: added new hash %s\n", name);
 745 #endif
 746     } else {
 747         list = (xsltCompMatchPtr) xmlHashLookup(style->templatesHash, name);
 748         if (list == NULL) {
 749             xmlHashAddEntry(style->templatesHash, name, pat);
 750 #ifdef DEBUG_PARSING
 751             xsltGenericError(xsltGenericErrorContext,
 752                     "xsltAddTemplate: added new hash %s\n", name);
 753 #endif
 754         } else {
 755             /*
 756              * Note '<=' since one must choose among the matching template
 757              * rules that are left, the one that occurs last in the stylesheet
 758              */
 759             if (list->priority <= pat->priority) {
 760                 pat->next = list;
 761                 xmlHashUpdateEntry(style->templatesHash, name, pat, NULL);
 762 #ifdef DEBUG_PARSING
 763                 xsltGenericError(xsltGenericErrorContext,
 764                         "xsltAddTemplate: added head hash for %s\n", name);
 765 #endif
 766             } else {
 767                 while (list->next != NULL) {
 768                     if (list->next->priority <= pat->priority)
 769                         break;
 770                 }
 771                 pat->next = list->next;
 772                 list->next = pat;
 773             }
 774         }
 775     }
 776     return(0);
 777 }
 778
 779 /**
 780  * xsltGetTemplate:
 781  * @style: an XSLT stylesheet
 782  * @node: an XML Node
 783  *
 784  * Finds the template applying to this node
 785  *
 786  * Returns the xsltTemplatePtr or NULL if not found
 787  */
 788 xsltTemplatePtr
 789 xsltGetTemplate(xsltStylesheetPtr style, xmlNodePtr node) {
 790     const xmlChar *name;
 791     xsltCompMatchPtr list;
 792
 793     if ((style == NULL) || (node == NULL))
 794         return(NULL);
 795
 796     /* TODO : handle IDs/keys here ! */
 797     if (style->templatesHash == NULL)
 798         return(NULL);
 799
 800     /*
 801      * Use a name as selector
 802      */
 803     switch (node->type) {
 804         case XML_ELEMENT_NODE:
 805         case XML_ATTRIBUTE_NODE:
 806         case XML_PI_NODE:
 807             name = node->name;
 808             break;
 809         case XML_DOCUMENT_NODE:
 810         case XML_HTML_DOCUMENT_NODE:
 811             name = (const xmlChar *)"/";
 812             break;
 813         case XML_TEXT_NODE:
 814         case XML_CDATA_SECTION_NODE:
 815         case XML_ENTITY_REF_NODE:
 816         case XML_ENTITY_NODE:
 817         case XML_COMMENT_NODE:
 818         case XML_DOCUMENT_TYPE_NODE:
 819         case XML_DOCUMENT_FRAG_NODE:
 820         case XML_NOTATION_NODE:
 821         case XML_DTD_NODE:
 822         case XML_ELEMENT_DECL:
 823         case XML_ATTRIBUTE_DECL:
 824         case XML_ENTITY_DECL:
 825         case XML_NAMESPACE_DECL:
 826         case XML_XINCLUDE_START:
 827         case XML_XINCLUDE_END:
 828             return(NULL);
 829         default:
 830             return(NULL);
 831
 832     }
 833     if (name == NULL)
 834         return(NULL);
 835
 836     /*
 837      * find the list of appliable expressions based on the name
 838      */
 839     list = (xsltCompMatchPtr) xmlHashLookup(style->templatesHash, name);
 840     if (list == NULL) {
 841 #ifdef DEBUG_MATCHING
 842         xsltGenericError(xsltGenericErrorContext,
 843                 "xsltGetTemplate: empty set for %s\n", name);
 844 #endif
 845         return(NULL);
 846     }
 847     while (list != NULL) {
 848         if (xsltTestCompMatch(list, node))
 849             return(list->template);
 850         list = list->next;
 851     }
 852
 853     return(NULL);
 854 }
 855
 856
 857 /**
 858  * xsltFreeTemplateHashes:
 859  * @style: an XSLT stylesheet
 860  *
 861  * Free up the memory used by xsltAddTemplate/xsltGetTemplate mechanism
 862  */
 863 void
 864 xsltFreeTemplateHashes(xsltStylesheetPtr style) {
 865     if (style->templatesHash != NULL)
 866         xmlHashFree((xmlHashTablePtr) style->templatesHash,
 867                     (xmlHashDeallocator) xsltFreeCompMatchList);
 868 }
 869