libxslt/pattern.c

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