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