libxslt/pattern.c

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