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
 284                 /* Namespace test */
 285                 if (node->ns == NULL) {
 286                     if (step->value2 != NULL)
 287                         return(0);
 288                 } else if (node->ns->href != NULL) {
 289                     if (step->value2 == NULL)
 290                         return(0);
 291                     if (!xmlStrEqual(step->value2, node->ns->href))
 292                         return(0);
 293                 }
 294                 continue;
 295             case XSLT_OP_CHILD:
 296                 TODO /* Handle OP_CHILD */
 297                 return(0);
 298             case XSLT_OP_ATTR:
 299                 if (node->type != XML_ATTRIBUTE_NODE)
 300                     return(0);
 301                 if (step->value == NULL)
 302                     continue;
 303                 if (!xmlStrEqual(step->value, node->name))
 304                     return(0);
 305
 306                 /* Namespace test */
 307                 if (node->ns == NULL) {
 308                     if (step->value2 != NULL)
 309                         return(0);
 310                 } else if (node->ns->href != NULL) {
 311                     if (step->value2 == NULL)
 312                         return(0);
 313                     if (!xmlStrEqual(step->value2, node->ns->href))
 314                         return(0);
 315                 }
 316                 continue;
 317             case XSLT_OP_PARENT:
 318                 node = node->parent;
 319                 if (node == NULL)
 320                     return(0);
 321                 if (step->value == NULL)
 322                     continue;
 323                 if (!xmlStrEqual(step->value, node->name))
 324                     return(0);
 325                 /* Namespace test */
 326                 if (node->ns == NULL) {
 327                     if (step->value2 != NULL)
 328                         return(0);
 329                 } else if (node->ns->href != NULL) {
 330                     if (step->value2 == NULL)
 331                         return(0);
 332                     if (!xmlStrEqual(step->value2, node->ns->href))
 333                         return(0);
 334                 }
 335                 continue;
 336             case XSLT_OP_ANCESTOR:
 337                 /* TODO: implement coalescing of ANCESTOR/NODE ops */
 338                 if (step->value == NULL) {
 339                     i++;
 340                     step = &comp->steps[i];
 341                     if (step->op == XSLT_OP_ROOT)
 342                         return(1);
 343                     if (step->op != XSLT_OP_ELEM)
 344                         return(0);
 345                     if (step->value == NULL)
 346                         return(-1);
 347                 }
 348                 if (node == NULL)
 349                     return(0);
 350                 node = node->parent;
 351                 while (node != NULL) {
 352                     if (node == NULL)
 353                         return(0);
 354                     if (xmlStrEqual(step->value, node->name)) {
 355                         /* Namespace test */
 356                         if (node->ns == NULL) {
 357                             if (step->value2 == NULL)
 358                                 break;
 359                         } else if (node->ns->href != NULL) {
 360                             if ((step->value2 != NULL) &&
 361                                 (xmlStrEqual(step->value2, node->ns->href)))
 362                                 break;
 363                         }
 364                     }
 365                 }
 366                 if (node == NULL)
 367                     return(0);
 368                 continue;
 369             case XSLT_OP_ID:
 370                 TODO /* Handle IDs, might be done differently */
 371                 break;
 372             case XSLT_OP_KEY:
 373                 TODO /* Handle Keys, might be done differently */
 374                 break;
 375             case XSLT_OP_NS:
 376                 /* Namespace test */
 377                 if (node->ns == NULL) {
 378                     if (step->value != NULL)
 379                         return(0);
 380                 } else if (node->ns->href != NULL) {
 381                     if (step->value == NULL)
 382                         return(0);
 383                     if (!xmlStrEqual(step->value, node->ns->href))
 384                         return(0);
 385                 }
 386                 break;
 387             case XSLT_OP_ALL:
 388                 switch (node->type) {
 389                     case XML_DOCUMENT_NODE:
 390                     case XML_HTML_DOCUMENT_NODE:
 391                     case XML_ELEMENT_NODE:
 392                         break;
 393                     default:
 394                         return(0);
 395                 }
 396                 break;
 397             case XSLT_OP_PREDICATE:
 398                 TODO /* Handle Predicate */
 399                 break;
 400             case XSLT_OP_PI:
 401                 if (node->type != XML_PI_NODE)
 402                     return(0);
 403                 if (step->value == NULL) {
 404                     if (!xmlStrEqual(step->value, node->name))
 405                         return(0);
 406                 }
 407                 break;
 408             case XSLT_OP_COMMENT:
 409                 if (node->type != XML_COMMENT_NODE)
 410                     return(0);
 411                 break;
 412             case XSLT_OP_TEXT:
 413                 if ((node->type != XML_TEXT_NODE) &&
 414                     (node->type != XML_CDATA_SECTION_NODE))
 415                     return(0);
 416                 break;
 417             case XSLT_OP_NODE:
 418                 switch (node->type) {
 419                     case XML_DOCUMENT_NODE:
 420                     case XML_HTML_DOCUMENT_NODE:
 421                     case XML_ELEMENT_NODE:
 422                     case XML_CDATA_SECTION_NODE:
 423                     case XML_PI_NODE:
 424                     case XML_COMMENT_NODE:
 425                     case XML_TEXT_NODE:
 426                     case XML_ATTRIBUTE_NODE:
 427                         break;
 428                     default:
 429                         return(0);
 430                 }
 431                 break;
 432         }
 433     }
 434     return(1);
 435 }
 436
 437 /************************************************************************
 438  *                                                                      *
 439  *                      Dedicated parser for templates                  *
 440  *                                                                      *
 441  ************************************************************************/
 442
 443 #define CUR (*ctxt->cur)
 444 #define SKIP(val) ctxt->cur += (val)
 445 #define NXT(val) ctxt->cur[(val)]
 446 #define CUR_PTR ctxt->cur
 447
 448 #define SKIP_BLANKS                                                     \
 449     while (IS_BLANK(CUR)) NEXT
 450
 451 #define CURRENT (*ctxt->cur)
 452 #define NEXT ((*ctxt->cur) ?  ctxt->cur++: ctxt->cur)
 453
 454
 455 #define PUSH(op, val, val2)                                             \
 456     if (xsltCompMatchAdd(ctxt->comp, (op), (val), (val2))) goto error;
 457
 458 #define XSLT_ERROR(X)                                                   \
 459     { xsltError(ctxt, __FILE__, __LINE__, X);                   \
 460       ctxt->error = (X); return; }
 461
 462 #define XSLT_ERROR0(X)                                                  \
 463     { xsltError(ctxt, __FILE__, __LINE__, X);                   \
 464       ctxt->error = (X); return(0); }
 465
 466 /**
 467  * xsltScanLiteral:
 468  * @ctxt:  the XPath Parser context
 469  *
 470  * Parse an XPath Litteral:
 471  *
 472  * [29] Literal ::= '"' [^"]* '"'
 473  *                | "'" [^']* "'"
 474  *
 475  * Returns the Literal parsed or NULL
 476  */
 477
 478 xmlChar *
 479 xsltScanLiteral(xsltParserContextPtr ctxt) {
 480     const xmlChar *q;
 481     xmlChar *ret = NULL;
 482
 483     SKIP_BLANKS;
 484     if (CUR == '"') {
 485         NEXT;
 486         q = CUR_PTR;
 487         while ((IS_CHAR(CUR)) && (CUR != '"'))
 488             NEXT;
 489         if (!IS_CHAR(CUR)) {
 490             /* XP_ERROR(XPATH_UNFINISHED_LITERAL_ERROR); */
 491             ctxt->error = 1;
 492             return(NULL);
 493         } else {
 494             ret = xmlStrndup(q, CUR_PTR - q);
 495             NEXT;
 496         }
 497     } else if (CUR == '\'') {
 498         NEXT;
 499         q = CUR_PTR;
 500         while ((IS_CHAR(CUR)) && (CUR != '\''))
 501             NEXT;
 502         if (!IS_CHAR(CUR)) {
 503             /* XP_ERROR(XPATH_UNFINISHED_LITERAL_ERROR); */
 504             ctxt->error = 1;
 505             return(NULL);
 506         } else {
 507             ret = xmlStrndup(q, CUR_PTR - q);
 508             NEXT;
 509         }
 510     } else {
 511         /* XP_ERROR(XPATH_START_LITERAL_ERROR); */
 512         ctxt->error = 1;
 513         return(NULL);
 514     }
 515     return(ret);
 516 }
 517
 518 /**
 519  * xsltScanName:
 520  * @ctxt:  the XPath Parser context
 521  *
 522  * Trickery: parse an XML name but without consuming the input flow
 523  * Needed to avoid insanity in the parser state.
 524  *
 525  * [4] NameChar ::= Letter | Digit | '.' | '-' | '_' | ':' |
 526  *                  CombiningChar | Extender
 527  *
 528  * [5] Name ::= (Letter | '_' | ':') (NameChar)*
 529  *
 530  * [6] Names ::= Name (S Name)*
 531  *
 532  * Returns the Name parsed or NULL
 533  */
 534
 535 xmlChar *
 536 xsltScanName(xsltParserContextPtr ctxt) {
 537     xmlChar buf[XML_MAX_NAMELEN];
 538     int len = 0;
 539
 540     SKIP_BLANKS;
 541     if (!IS_LETTER(CUR) && (CUR != '_') &&
 542         (CUR != ':')) {
 543         return(NULL);
 544     }
 545
 546     while ((IS_LETTER(NXT(len))) || (IS_DIGIT(NXT(len))) ||
 547            (NXT(len) == '.') || (NXT(len) == '-') ||
 548            (NXT(len) == '_') || (NXT(len) == ':') ||
 549            (IS_COMBINING(NXT(len))) ||
 550            (IS_EXTENDER(NXT(len)))) {
 551         buf[len] = NXT(len);
 552         len++;
 553         if (len >= XML_MAX_NAMELEN) {
 554             xmlGenericError(xmlGenericErrorContext,
 555                "xmlScanName: reached XML_MAX_NAMELEN limit\n");
 556             while ((IS_LETTER(NXT(len))) || (IS_DIGIT(NXT(len))) ||
 557                    (NXT(len) == '.') || (NXT(len) == '-') ||
 558                    (NXT(len) == '_') || (NXT(len) == ':') ||
 559                    (IS_COMBINING(NXT(len))) ||
 560                    (IS_EXTENDER(NXT(len))))
 561                  len++;
 562             break;
 563         }
 564     }
 565     SKIP(len);
 566     return(xmlStrndup(buf, len));
 567 }
 568 /*
 569  * xsltCompileIdKeyPattern:
 570  * @comp:  the compilation context
 571  * @name:  a preparsed name
 572  * @aid:  whether id/key are allowed there
 573  *
 574  * Compile the XSLT LocationIdKeyPattern
 575  * [3] IdKeyPattern ::= 'id' '(' Literal ')'
 576  *                    | 'key' '(' Literal ',' Literal ')'
 577  *
 578  * also handle NodeType and PI from:
 579  *
 580  * [7]  NodeTest ::= NameTest
 581  *                 | NodeType '(' ')'
 582  *                 | 'processing-instruction' '(' Literal ')'
 583  */
 584 void
 585 xsltCompileIdKeyPattern(xsltParserContextPtr ctxt, xmlChar *name, int aid) {
 586     xmlChar *lit = NULL;
 587     xmlChar *lit2 = NULL;
 588
 589     if (CUR != '(') {
 590         xsltGenericError(xsltGenericErrorContext,
 591                 "xsltCompileIdKeyPattern : ( expected\n");
 592         ctxt->error = 1;
 593         return;
 594     }
 595     if ((aid) && (xmlStrEqual(name, (const xmlChar *)"id"))) {
 596         NEXT;
 597         SKIP_BLANKS;
 598         lit = xsltScanLiteral(ctxt);
 599         if (ctxt->error)
 600             return;
 601         SKIP_BLANKS;
 602         if (CUR != ')') {
 603             xsltGenericError(xsltGenericErrorContext,
 604                     "xsltCompileIdKeyPattern : ) expected\n");
 605             ctxt->error = 1;
 606             return;
 607         }
 608         NEXT;
 609         PUSH(XSLT_OP_ID, lit, NULL);
 610     } else if ((aid) && (xmlStrEqual(name, (const xmlChar *)"key"))) {
 611         NEXT;
 612         SKIP_BLANKS;
 613         lit = xsltScanLiteral(ctxt);
 614         if (ctxt->error)
 615             return;
 616         SKIP_BLANKS;
 617         if (CUR != ',') {
 618             xsltGenericError(xsltGenericErrorContext,
 619                     "xsltCompileIdKeyPattern : , expected\n");
 620             ctxt->error = 1;
 621             return;
 622         }
 623         NEXT;
 624         SKIP_BLANKS;
 625         lit2 = xsltScanLiteral(ctxt);
 626         if (ctxt->error)
 627             return;
 628         SKIP_BLANKS;
 629         if (CUR != ')') {
 630             xsltGenericError(xsltGenericErrorContext,
 631                     "xsltCompileIdKeyPattern : ) expected\n");
 632             ctxt->error = 1;
 633             return;
 634         }
 635         NEXT;
 636         PUSH(XSLT_OP_KEY, lit, NULL);
 637     } else if (xmlStrEqual(name, (const xmlChar *)"processing-instruction")) {
 638         NEXT;
 639         SKIP_BLANKS;
 640         if (CUR != ')') {
 641             lit = xsltScanLiteral(ctxt);
 642             if (ctxt->error)
 643                 return;
 644             SKIP_BLANKS;
 645             if (CUR != ')') {
 646                 xsltGenericError(xsltGenericErrorContext,
 647                         "xsltCompileIdKeyPattern : ) expected\n");
 648                 ctxt->error = 1;
 649                 return;
 650             }
 651         }
 652         NEXT;
 653         PUSH(XSLT_OP_PI, lit, NULL);
 654     } else if (xmlStrEqual(name, (const xmlChar *)"text")) {
 655         NEXT;
 656         SKIP_BLANKS;
 657         if (CUR != ')') {
 658             xsltGenericError(xsltGenericErrorContext,
 659                     "xsltCompileIdKeyPattern : ) expected\n");
 660             ctxt->error = 1;
 661             return;
 662         }
 663         NEXT;
 664         PUSH(XSLT_OP_TEXT, NULL, NULL);
 665     } else if (xmlStrEqual(name, (const xmlChar *)"comment")) {
 666         NEXT;
 667         SKIP_BLANKS;
 668         if (CUR != ')') {
 669             xsltGenericError(xsltGenericErrorContext,
 670                     "xsltCompileIdKeyPattern : ) expected\n");
 671             ctxt->error = 1;
 672             return;
 673         }
 674         NEXT;
 675         PUSH(XSLT_OP_COMMENT, NULL, NULL);
 676     } else if (xmlStrEqual(name, (const xmlChar *)"node")) {
 677         NEXT;
 678         SKIP_BLANKS;
 679         if (CUR != ')') {
 680             xsltGenericError(xsltGenericErrorContext,
 681                     "xsltCompileIdKeyPattern : ) expected\n");
 682             ctxt->error = 1;
 683             return;
 684         }
 685         NEXT;
 686         PUSH(XSLT_OP_NODE, NULL, NULL);
 687     } else if (aid) {
 688         xsltGenericError(xsltGenericErrorContext,
 689             "xsltCompileIdKeyPattern : expecting 'key' or 'id' or node type\n");
 690         ctxt->error = 1;
 691         return;
 692     } else {
 693         xsltGenericError(xsltGenericErrorContext,
 694             "xsltCompileIdKeyPattern : node type\n");
 695         ctxt->error = 1;
 696         return;
 697     }
 698 error:
 699     if (lit != NULL)
 700         xmlFree(lit);
 701     if (lit2 != NULL)
 702         xmlFree(lit2);
 703 }
 704
 705 /**
 706  * xsltCompileStepPattern:
 707  * @comp:  the compilation context
 708  * @token:  a posible precompiled name
 709  *
 710  * Compile the XSLT StepPattern and generates a precompiled
 711  * form suitable for fast matching.
 712  *
 713  * [5] StepPattern ::= ChildOrAttributeAxisSpecifier NodeTest Predicate*
 714  * [6] ChildOrAttributeAxisSpecifier ::= AbbreviatedAxisSpecifier
 715  *                                     | ('child' | 'attribute') '::'
 716  * from XPath
 717  * [7]  NodeTest ::= NameTest
 718  *                 | NodeType '(' ')'
 719  *                 | 'processing-instruction' '(' Literal ')'
 720  * [8] Predicate ::= '[' PredicateExpr ']'
 721  * [9] PredicateExpr ::= Expr
 722  * [13] AbbreviatedAxisSpecifier ::= '@'?
 723  * [37] NameTest ::= '*' | NCName ':' '*' | QName
 724  */
 725
 726 void
 727 xsltCompileStepPattern(xsltParserContextPtr ctxt, xmlChar *token) {
 728     xmlChar *name = NULL;
 729
 730     SKIP_BLANKS;
 731     if ((token == NULL) && (CUR == '@')) {
 732         token = xsltScanName(ctxt);
 733         if (token == NULL) {
 734             xsltGenericError(xsltGenericErrorContext,
 735                     "xsltCompilePattern : Name expected\n");
 736             ctxt->error = 1;
 737             goto error;
 738         }
 739         PUSH(XSLT_OP_ATTR, token, NULL);
 740         return;
 741     }
 742     if (token == NULL)
 743         token = xsltScanName(ctxt);
 744     if (token == NULL) {
 745         xsltGenericError(xsltGenericErrorContext,
 746                 "xsltCompilePattern : Name expected\n");
 747         ctxt->error = 1;
 748         goto error;
 749     }
 750     SKIP_BLANKS;
 751     if (CUR == '(') {
 752         xsltCompileIdKeyPattern(ctxt, token, 0);
 753         if (ctxt->error)
 754             goto error;
 755     } else if (CUR == ':') {
 756         NEXT;
 757         if (NXT(1) != ':') {
 758             xsltGenericError(xsltGenericErrorContext,
 759                     "xsltCompilePattern : sequence '::' expected\n");
 760             ctxt->error = 1;
 761             goto error;
 762         }
 763         NEXT;
 764         if (xmlStrEqual(token, (const xmlChar *) "child")) {
 765             /* TODO: handle namespace */
 766             name = xsltScanName(ctxt);
 767             if (name == NULL) {
 768                 xsltGenericError(xsltGenericErrorContext,
 769                         "xsltCompilePattern : QName expected\n");
 770                 ctxt->error = 1;
 771                 goto error;
 772             }
 773             PUSH(XSLT_OP_CHILD, name, NULL);
 774         } else if (xmlStrEqual(token, (const xmlChar *) "attribute")) {
 775             /* TODO: handle namespace */
 776             name = xsltScanName(ctxt);
 777             if (name == NULL) {
 778                 xsltGenericError(xsltGenericErrorContext,
 779                         "xsltCompilePattern : QName expected\n");
 780                 ctxt->error = 1;
 781                 goto error;
 782             }
 783             PUSH(XSLT_OP_ATTR, name, NULL);
 784         } else {
 785             xsltGenericError(xsltGenericErrorContext,
 786                     "xsltCompilePattern : 'child' or 'attribute' expected\n");
 787             ctxt->error = 1;
 788             goto error;
 789         }
 790         xmlFree(token);
 791     } else if (CUR == '*') {
 792         NEXT;
 793         PUSH(XSLT_OP_ALL, token, NULL);
 794     } else {
 795         /* TODO: handle namespace */
 796         PUSH(XSLT_OP_ELEM, token, NULL);
 797     }
 798     SKIP_BLANKS;
 799     while (CUR == '[') {
 800         const xmlChar *q;
 801         xmlChar *ret = NULL;
 802
 803         NEXT;
 804         q = CUR_PTR;
 805         /* TODO: avoid breaking in strings ... */
 806         while ((IS_CHAR(CUR)) && (CUR != ']'))
 807             NEXT;
 808         if (!IS_CHAR(CUR)) {
 809             xsltGenericError(xsltGenericErrorContext,
 810                     "xsltCompilePattern : ']' expected\n");
 811             ctxt->error = 1;
 812             goto error;
 813         }
 814         NEXT;
 815         ret = xmlStrndup(q, CUR_PTR - q);
 816         PUSH(XSLT_OP_PREDICATE, ret, NULL);
 817     }
 818     return;
 819 error:
 820     if (token != NULL)
 821         xmlFree(token);
 822     if (name != NULL)
 823         xmlFree(name);
 824 }
 825
 826 /**
 827  * xsltCompileRelativePathPattern:
 828  * @comp:  the compilation context
 829  * @token:  a posible precompiled name
 830  *
 831  * Compile the XSLT RelativePathPattern and generates a precompiled
 832  * form suitable for fast matching.
 833  *
 834  * [4] RelativePathPattern ::= StepPattern
 835  *                           | RelativePathPattern '/' StepPattern
 836  *                           | RelativePathPattern '//' StepPattern
 837  */
 838 void
 839 xsltCompileRelativePathPattern(xsltParserContextPtr ctxt, xmlChar *token) {
 840     xsltCompileStepPattern(ctxt, token);
 841     if (ctxt->error)
 842         goto error;
 843     SKIP_BLANKS;
 844     while ((CUR != 0) && (CUR != '|')) {
 845         if ((CUR == '/') && (NXT(1) == '/')) {
 846             PUSH(XSLT_OP_ANCESTOR, NULL, NULL);
 847             NEXT;
 848             NEXT;
 849             SKIP_BLANKS;
 850             xsltCompileStepPattern(ctxt, NULL);
 851         } else if (CUR == '/') {
 852             PUSH(XSLT_OP_PARENT, NULL, NULL);
 853             NEXT;
 854             SKIP_BLANKS;
 855             if ((CUR != 0) || (CUR == '|')) {
 856                 xsltCompileRelativePathPattern(ctxt, NULL);
 857             }
 858         } else {
 859             ctxt->error = 1;
 860         }
 861         if (ctxt->error)
 862             goto error;
 863         SKIP_BLANKS;
 864     }
 865 error:
 866     return;
 867 }
 868
 869 /**
 870  * xsltCompileLocationPathPattern:
 871  * @comp:  the compilation context
 872  *
 873  * Compile the XSLT LocationPathPattern and generates a precompiled
 874  * form suitable for fast matching.
 875  *
 876  * [2] LocationPathPattern ::= '/' RelativePathPattern?
 877  *                           | IdKeyPattern (('/' | '//') RelativePathPattern)?
 878  *                           | '//'? RelativePathPattern
 879  */
 880 void
 881 xsltCompileLocationPathPattern(xsltParserContextPtr ctxt) {
 882     SKIP_BLANKS;
 883     if ((CUR == '/') && (NXT(1) == '/')) {
 884         /*
 885          * since we reverse the query
 886          * a leading // can be safely ignored
 887          */
 888         NEXT;
 889         NEXT;
 890         xsltCompileRelativePathPattern(ctxt, NULL);
 891     } else if (CUR == '/') {
 892         /*
 893          * We need to find root as the parent
 894          */
 895         NEXT;
 896         SKIP_BLANKS;
 897         PUSH(XSLT_OP_ROOT, NULL, NULL);
 898         if ((CUR != 0) || (CUR == '|')) {
 899             PUSH(XSLT_OP_PARENT, NULL, NULL);
 900             xsltCompileRelativePathPattern(ctxt, NULL);
 901         }
 902     } else {
 903         xmlChar *name;
 904         name = xsltScanName(ctxt);
 905         if (name == NULL) {
 906             xsltGenericError(xsltGenericErrorContext,
 907                     "xsltCompilePattern : Name expected\n");
 908             ctxt->error = 1;
 909             return;
 910         }
 911         SKIP_BLANKS;
 912         if (CUR == '(') {
 913             xsltCompileIdKeyPattern(ctxt, name, 1);
 914             if ((CUR == '/') && (NXT(1) == '/')) {
 915                 PUSH(XSLT_OP_ANCESTOR, NULL, NULL);
 916                 NEXT;
 917                 NEXT;
 918                 SKIP_BLANKS;
 919                 xsltCompileRelativePathPattern(ctxt, NULL);
 920             } else if (CUR == '/') {
 921                 PUSH(XSLT_OP_PARENT, NULL, NULL);
 922                 NEXT;
 923                 SKIP_BLANKS;
 924                 xsltCompileRelativePathPattern(ctxt, NULL);
 925             }
 926             return;
 927         }
 928         xsltCompileRelativePathPattern(ctxt, name);
 929     }
 930 error:
 931     return;
 932 }
 933
 934 /**
 935  * xsltCompilePattern:
 936  * @pattern an XSLT pattern
 937  *
 938  * Compile the XSLT pattern and generates a precompiled form suitable
 939  * for fast matching.
 940  * Note that the splitting as union of patterns is expected to be handled
 941  * by the caller
 942  *
 943  * [1] Pattern ::= LocationPathPattern | Pattern '|' LocationPathPattern
 944  *
 945  * Returns the generated xsltCompMatchPtr or NULL in case of failure
 946  */
 947
 948 xsltCompMatchPtr
 949 xsltCompilePattern(const xmlChar *pattern) {
 950     xsltParserContextPtr ctxt;
 951     xsltCompMatchPtr ret;
 952     const xmlChar *cur;
 953
 954     if (pattern == NULL) {
 955         xsltGenericError(xsltGenericErrorContext,
 956                 "xsltCompilePattern : NULL pattern\n");
 957         return(NULL);
 958     }
 959
 960 #ifdef DEBUG_PARSING
 961     xsltGenericDebug(xsltGenericDebugContext,
 962             "xsltCompilePattern : parsing '%s'\n", pattern);
 963 #endif
 964
 965     cur = pattern;
 966     while (IS_BLANK(*cur)) cur++;
 967     if (*cur == 0) {
 968         xsltGenericError(xsltGenericErrorContext,
 969                 "xsltCompilePattern : NULL pattern\n");
 970         return(NULL);
 971     }
 972     ctxt = xsltNewParserContext();
 973     if (ctxt == NULL)
 974         return(NULL);
 975     ret = xsltNewCompMatch();
 976     if (ret == NULL) {
 977         xsltFreeParserContext(ctxt);
 978         return(NULL);
 979     }
 980
 981     ctxt->comp = ret;
 982     ctxt->base = pattern;
 983     ctxt->cur = cur;
 984     xsltCompileLocationPathPattern(ctxt);
 985     if (ctxt->error)
 986         goto error;
 987
 988     /*
 989      * Reverse for faster interpretation.
 990      */
 991     xsltReverseCompMatch(ret);
 992
 993     /*
 994      * Set-up the priority
 995      */
 996     if (((ret->steps[0].op == XSLT_OP_ELEM) ||
 997          (ret->steps[0].op == XSLT_OP_ATTR)) &&
 998         (ret->steps[0].value != NULL) &&
 999         (ret->steps[1].op == XSLT_OP_END)) {
1000         ret->priority = 0;
1001     } else if ((ret->steps[0].op == XSLT_OP_PI) &&
1002                (ret->steps[0].value != NULL) &&
1003                (ret->steps[1].op == XSLT_OP_END)) {
1004         ret->priority = 0;
1005     } else if ((ret->steps[0].op == XSLT_OP_NS) &&
1006                (ret->steps[0].value != NULL) &&
1007                (ret->steps[1].op == XSLT_OP_END)) {
1008         ret->priority = -0.25;
1009     } else if (((ret->steps[0].op == XSLT_OP_PI) ||
1010                 (ret->steps[0].op == XSLT_OP_TEXT) ||
1011                 (ret->steps[0].op == XSLT_OP_NODE) ||
1012                 (ret->steps[0].op == XSLT_OP_COMMENT)) &&
1013                (ret->steps[1].op == XSLT_OP_END)) {
1014         ret->priority = -0.5;
1015     } else {
1016         ret->priority = 0.5;
1017     }
1018
1019     xsltFreeParserContext(ctxt);
1020     return(ret);
1021
1022 error:
1023     xsltFreeParserContext(ctxt);
1024     xsltFreeCompMatch(ret);
1025     return(NULL);
1026
1027 }
1028
1029
1030 /************************************************************************
1031  *                                                                      *
1032  *                      Module interfaces                               *
1033  *                                                                      *
1034  ************************************************************************/
1035
1036 /**
1037  * xsltAddTemplate:
1038  * @style: an XSLT stylesheet
1039  * @cur: an XSLT template
1040  *
1041  * Register the XSLT pattern associated to @cur
1042  *
1043  * Returns -1 in case of error, 0 otherwise
1044  */
1045 int
1046 xsltAddTemplate(xsltStylesheetPtr style, xsltTemplatePtr cur) {
1047     xsltCompMatchPtr pat, list;
1048     const xmlChar *name = NULL;
1049     xmlChar *p, *pattern, tmp;
1050
1051     if ((style == NULL) || (cur == NULL))
1052         return(-1);
1053
1054     p = cur->match;
1055     if (p == NULL)
1056         return(-1);
1057
1058 next_pattern:
1059     if (*p == 0)
1060         return(0);
1061     /*
1062      * get a compiled form of the pattern
1063      */
1064     pattern = p;
1065     while ((*p != 0) && (*p != '|')) {
1066         /* TODO: handle string escaping "a | b" in patterns ... */
1067         p++;
1068     }
1069
1070     tmp = *p;
1071     *p = 0;
1072     pat = xsltCompilePattern(pattern);
1073     *p = tmp;
1074     if (tmp != 0)
1075         p++;
1076     if (pat == NULL)
1077         return(-1);
1078     pat->template = cur;
1079     if (cur->priority != XSLT_PAT_NO_PRIORITY)
1080         pat->priority = cur->priority;
1081
1082     /*
1083      * insert it in the hash table list corresponding to its lookup name
1084      */
1085     switch (pat->steps[0].op) {
1086         case XSLT_OP_ELEM:
1087         case XSLT_OP_CHILD:
1088         case XSLT_OP_ATTR:
1089         case XSLT_OP_PARENT:
1090         case XSLT_OP_ANCESTOR:
1091         case XSLT_OP_ID:
1092         case XSLT_OP_KEY:
1093         case XSLT_OP_NS:
1094              name = pat->steps[0].value;
1095              break;
1096         case XSLT_OP_ROOT:
1097              name = (const xmlChar *) "/";
1098              break;
1099         case XSLT_OP_ALL:
1100              name = (const xmlChar *) "*";
1101              break;
1102         case XSLT_OP_END:
1103         case XSLT_OP_PREDICATE:
1104             xsltGenericError(xsltGenericErrorContext,
1105                     "xsltAddTemplate: invalid compiled pattern\n");
1106             xsltFreeCompMatch(pat);
1107             return(-1);
1108         /*
1109          * TODO: some flags at the top level about type based patterns
1110          *       would be faster than inclusion in the hash table.
1111          */
1112         case XSLT_OP_PI:
1113             name = (const xmlChar *) "processing-instruction()";
1114             break;
1115         case XSLT_OP_COMMENT:
1116             name = (const xmlChar *) "comment()";
1117             break;
1118         case XSLT_OP_TEXT:
1119             name = (const xmlChar *) "text()";
1120             break;
1121         case XSLT_OP_NODE:
1122             name = (const xmlChar *) "node()";
1123             break;
1124     }
1125     if (name == NULL) {
1126         xsltGenericError(xsltGenericErrorContext,
1127                 "xsltAddTemplate: invalid compiled pattern\n");
1128         xsltFreeCompMatch(pat);
1129         return(-1);
1130     }
1131     if (style->templatesHash == NULL) {
1132         style->templatesHash = xmlHashCreate(0);
1133         if (style->templatesHash == NULL) {
1134             xsltFreeCompMatch(pat);
1135             return(-1);
1136         }
1137 #ifdef DEBUG_PARSING
1138         xsltGenericDebug(xsltGenericDebugContext,
1139                 "xsltAddTemplate: created template hash\n");
1140 #endif
1141         xmlHashAddEntry(style->templatesHash, name, pat);
1142 #ifdef DEBUG_PARSING
1143         xsltGenericDebug(xsltGenericDebugContext,
1144                 "xsltAddTemplate: added new hash %s\n", name);
1145 #endif
1146     } else {
1147         list = (xsltCompMatchPtr) xmlHashLookup(style->templatesHash, name);
1148         if (list == NULL) {
1149             xmlHashAddEntry(style->templatesHash, name, pat);
1150 #ifdef DEBUG_PARSING
1151             xsltGenericDebug(xsltGenericDebugContext,
1152                     "xsltAddTemplate: added new hash %s\n", name);
1153 #endif
1154         } else {
1155             /*
1156              * Note '<=' since one must choose among the matching template
1157              * rules that are left, the one that occurs last in the stylesheet
1158              */
1159             if (list->priority <= pat->priority) {
1160                 pat->next = list;
1161                 xmlHashUpdateEntry(style->templatesHash, name, pat, NULL);
1162 #ifdef DEBUG_PARSING
1163                 xsltGenericDebug(xsltGenericDebugContext,
1164                         "xsltAddTemplate: added head hash for %s\n", name);
1165 #endif
1166             } else {
1167                 while (list->next != NULL) {
1168                     if (list->next->priority <= pat->priority)
1169                         break;
1170                 }
1171                 pat->next = list->next;
1172                 list->next = pat;
1173             }
1174         }
1175     }
1176     if (*p != 0)
1177         goto next_pattern;
1178     return(0);
1179 }
1180
1181 /**
1182  * xsltGetTemplate:
1183  * @style: an XSLT stylesheet
1184  * @node: an XML Node
1185  *
1186  * Finds the template applying to this node
1187  *
1188  * Returns the xsltTemplatePtr or NULL if not found
1189  */
1190 xsltTemplatePtr
1191 xsltGetTemplate(xsltStylesheetPtr style, xmlNodePtr node) {
1192     const xmlChar *name;
1193     xsltCompMatchPtr list;
1194
1195     if ((style == NULL) || (node == NULL))
1196         return(NULL);
1197
1198     /* TODO : handle IDs/keys here ! */
1199     if (style->templatesHash == NULL)
1200         return(NULL);
1201
1202     /*
1203      * Use a name as selector
1204      */
1205     switch (node->type) {
1206         case XML_ELEMENT_NODE:
1207         case XML_ATTRIBUTE_NODE:
1208         case XML_PI_NODE:
1209             name = node->name;
1210             break;
1211         case XML_DOCUMENT_NODE:
1212         case XML_HTML_DOCUMENT_NODE:
1213             name = (const xmlChar *)"/";
1214             break;
1215         case XML_TEXT_NODE:
1216         case XML_CDATA_SECTION_NODE:
1217         case XML_ENTITY_REF_NODE:
1218         case XML_ENTITY_NODE:
1219         case XML_COMMENT_NODE:
1220         case XML_DOCUMENT_TYPE_NODE:
1221         case XML_DOCUMENT_FRAG_NODE:
1222         case XML_NOTATION_NODE:
1223         case XML_DTD_NODE:
1224         case XML_ELEMENT_DECL:
1225         case XML_ATTRIBUTE_DECL:
1226         case XML_ENTITY_DECL:
1227         case XML_NAMESPACE_DECL:
1228         case XML_XINCLUDE_START:
1229         case XML_XINCLUDE_END:
1230             return(NULL);
1231         default:
1232             return(NULL);
1233
1234     }
1235     if (name == NULL)
1236         return(NULL);
1237
1238     /*
1239      * find the list of appliable expressions based on the name
1240      */
1241     list = (xsltCompMatchPtr) xmlHashLookup(style->templatesHash, name);
1242     if (list == NULL) {
1243 #ifdef DEBUG_MATCHING
1244         xsltGenericDebug(xsltGenericDebugContext,
1245                 "xsltGetTemplate: empty set for %s\n", name);
1246 #endif
1247         return(NULL);
1248     }
1249     while (list != NULL) {
1250         if (xsltTestCompMatch(list, node))
1251             return(list->template);
1252         list = list->next;
1253     }
1254
1255     return(NULL);
1256 }
1257
1258
1259 /**
1260  * xsltFreeTemplateHashes:
1261  * @style: an XSLT stylesheet
1262  *
1263  * Free up the memory used by xsltAddTemplate/xsltGetTemplate mechanism
1264  */
1265 void
1266 xsltFreeTemplateHashes(xsltStylesheetPtr style) {
1267     if (style->templatesHash != NULL)
1268         xmlHashFree((xmlHashTablePtr) style->templatesHash,
1269                     (xmlHashDeallocator) xsltFreeCompMatchList);
1270 }
1271
1272 /**
1273  * xsltFindTemplate:
1274  * @style: an XSLT stylesheet
1275  * @name: the template name
1276  * @nameURI: the template name URI
1277  *
1278  * Finds the named template.
1279  *
1280  * Returns the xsltTemplatePtr or NULL if not found
1281  */
1282 xsltTemplatePtr
1283 xsltFindTemplate(xsltStylesheetPtr style, const xmlChar *name,
1284                 const xmlChar *nameURI) {
1285     xsltTemplatePtr cur;
1286
1287     if ((style == NULL) || (name == NULL))
1288         return(NULL);
1289
1290     /* TODO: apply stylesheet import order */
1291     cur = style->templates;
1292     while (cur != NULL) {
1293         if (xmlStrEqual(name, cur->name)) {
1294             if (((nameURI == NULL) && (cur->nameURI == NULL)) ||
1295                 ((nameURI != NULL) && (cur->nameURI != NULL) &&
1296                  (xmlStrEqual(nameURI, cur->nameURI)))) {
1297                 return(cur);
1298             }
1299         }
1300         cur = cur->next;
1301     }
1302     return(NULL);
1303 }
1304