libxslt/pattern.c

   1 /*
   2  * pattern.c: Implemetation of the template match compilation and lookup
   3  *
   4  * Reference:
   5  *   http://www.w3.org/TR/1999/REC-xslt-19991116
   6  *
   7  * See Copyright for the status of this software.
   8  *
   9  * Daniel.Veillard@imag.fr
  10  */
  11
  12 #include "xsltconfig.h"
  13
  14 #include <string.h>
  15
  16 #include <libxml/xmlmemory.h>
  17 #include <libxml/tree.h>
  18 #include <libxml/valid.h>
  19 #include <libxml/hash.h>
  20 #include <libxml/xmlerror.h>
  21 #include <libxml/parserInternals.h>
  22 #include "xslt.h"
  23 #include "xsltInternals.h"
  24
  25 #define DEBUG_PARSING
  26
  27 #define TODO                                                            \
  28     xsltGenericError(xsltGenericErrorContext,                           \
  29             "Unimplemented block at %s:%d\n",                           \
  30             __FILE__, __LINE__);
  31
  32 /*
  33  * To cleanup
  34  */
  35 xmlChar *xmlSplitQName2(const xmlChar *name, xmlChar **prefix);
  36
  37 /*
  38  * There is no XSLT specific error reporting module yet
  39  */
  40 #define xsltGenericError xmlGenericError
  41 #define xsltGenericErrorContext xmlGenericErrorContext
  42
  43 /*
  44  * Types are private:
  45  */
  46
  47 typedef enum {
  48     XSLT_OP_END=0,
  49     XSLT_OP_ROOT,
  50     XSLT_OP_ELEM,
  51     XSLT_OP_CHILD,
  52     XSLT_OP_ATTR,
  53     XSLT_OP_PARENT,
  54     XSLT_OP_ANCESTOR,
  55     XSLT_OP_ID,
  56     XSLT_OP_KEY,
  57     XSLT_OP_NS,
  58     XSLT_OP_ALL,
  59     XSLT_OP_PREDICATE
  60 } xsltOp;
  61
  62 typedef union _xsltStepOp xsltStepOp;
  63 typedef xsltStepOp *xsltStepOpPtr;
  64 union _xsltStepOp {
  65     xsltOp op;
  66     xmlChar *value;
  67 };
  68
  69 typedef struct _xsltCompMatch xsltCompMatch;
  70 typedef xsltCompMatch *xsltCompMatchPtr;
  71 struct _xsltCompMatch {
  72     struct _xsltCompMatch *next; /* siblings in the name hash */
  73     int priority;                /* the priority */
  74
  75     /* TODO fix the statically allocated size */
  76     int nbStep;
  77     int maxStep;
  78     xsltStepOp steps[20];        /* ops for computation */
  79 };
  80
  81 typedef struct _xsltParserContext xsltParserContext;
  82 typedef xsltParserContext *xsltParserContextPtr;
  83 struct _xsltParserContext {
  84     const xmlChar *cur;                 /* the current char being parsed */
  85     const xmlChar *base;                /* the full expression */
  86     int error;                          /* error code */
  87     xsltCompMatchPtr comp;              /* the result */
  88 };
  89
  90 /************************************************************************
  91  *                                                                      *
  92  *                      Type functions                                  *
  93  *                                                                      *
  94  ************************************************************************/
  95
  96 /**
  97  * xsltNewCompMatch:
  98  *
  99  * Create a new XSLT CompMatch
 100  *
 101  * Returns the newly allocated xsltCompMatchPtr or NULL in case of error
 102  */
 103 xsltCompMatchPtr
 104 xsltNewCompMatch(void) {
 105     xsltCompMatchPtr cur;
 106
 107     cur = (xsltCompMatchPtr) xmlMalloc(sizeof(xsltCompMatch));
 108     if (cur == NULL) {
 109         xsltGenericError(xsltGenericErrorContext,
 110                 "xsltNewCompMatch : malloc failed\n");
 111         return(NULL);
 112     }
 113     memset(cur, 0, sizeof(xsltCompMatch));
 114     cur->maxStep = 20;
 115     return(cur);
 116 }
 117
 118 /**
 119  * xsltFreeCompMatch:
 120  * @comp:  an XSLT comp
 121  *
 122  * Free up the memory allocated by @comp
 123  */
 124 void
 125 xsltFreeCompMatch(xsltCompMatchPtr comp) {
 126     if (comp == NULL)
 127         return;
 128     memset(comp, -1, sizeof(xsltCompMatch));
 129     xmlFree(comp);
 130 }
 131
 132 /**
 133  * xsltFreeCompMatchList:
 134  * @comp:  an XSLT comp list
 135  *
 136  * Free up the memory allocated by all the elements of @comp
 137  */
 138 void
 139 xsltFreeCompMatchList(xsltCompMatchPtr comp) {
 140     xsltCompMatchPtr cur;
 141
 142     while (comp != NULL) {
 143         cur = comp;
 144         comp = comp->next;
 145         xsltFreeCompMatch(cur);
 146     }
 147 }
 148
 149 /**
 150  * xsltNewParserContext:
 151  *
 152  * Create a new XSLT ParserContext
 153  *
 154  * Returns the newly allocated xsltParserContextPtr or NULL in case of error
 155  */
 156 xsltParserContextPtr
 157 xsltNewParserContext(void) {
 158     xsltParserContextPtr cur;
 159
 160     cur = (xsltParserContextPtr) xmlMalloc(sizeof(xsltParserContext));
 161     if (cur == NULL) {
 162         xsltGenericError(xsltGenericErrorContext,
 163                 "xsltNewParserContext : malloc failed\n");
 164         return(NULL);
 165     }
 166     memset(cur, 0, sizeof(xsltParserContext));
 167     return(cur);
 168 }
 169
 170 /**
 171  * xsltFreeParserContext:
 172  * @comp:  an XSLT comp
 173  *
 174  * Free up the memory allocated by @comp
 175  */
 176 void
 177 xsltFreeParserContext(xsltParserContextPtr comp) {
 178     if (comp == NULL)
 179         return;
 180     memset(comp, -1, sizeof(xsltParserContext));
 181     xmlFree(comp);
 182 }
 183
 184 /**
 185  * xsltCompMatchAddOp:
 186  * @comp:  the compiled match expression
 187  * @op:  an op
 188  *
 189  * Add an step to an XSLT Compiled Match
 190  *
 191  * Returns -1 in case of failure, 0 otherwise.
 192  */
 193 int
 194 xsltCompMatchAddOp(xsltCompMatchPtr comp, xsltOp op) {
 195     if (comp->nbStep >= 20) {
 196         xsltGenericError(xsltGenericErrorContext,
 197                 "xsltCompMatchAddOp: overflow\n");
 198         return(-1);
 199     }
 200     comp->steps[comp->nbStep++].op = op;
 201     return(0);
 202 }
 203
 204 /**
 205  * xsltCompMatchAddValue:
 206  * @comp:  the compiled match expression
 207  * @val:  a name
 208  *
 209  * Add an step to an XSLT Compiled Match
 210  *
 211  * Returns -1 in case of failure, 0 otherwise.
 212  */
 213 int
 214 xsltCompMatchAddValue(xsltCompMatchPtr comp, xmlChar *val) {
 215     if (comp->nbStep >= 20) {
 216         xsltGenericError(xsltGenericErrorContext,
 217                 "xsltCompMatchAddOp: overflow\n");
 218         return(-1);
 219     }
 220     comp->steps[comp->nbStep++].value = val;
 221     return(0);
 222 }
 223
 224 /**
 225  * xsltReverseCompMatch:
 226  * @comp:  the compiled match expression
 227  *
 228  * reverse all the stack of expressions
 229  */
 230 void
 231 xsltReverseCompMatch(xsltCompMatchPtr comp) {
 232     int i = 0;
 233     int j = comp->nbStep - 1;
 234
 235     while (j > i) {
 236         register xmlChar *tmp;
 237         tmp = comp->steps[i].value;
 238         comp->steps[i].value = comp->steps[j].value;
 239         comp->steps[j].value = tmp;
 240         j--;
 241         i++;
 242     }
 243     comp->steps[comp->nbStep].op = XSLT_OP_END;
 244 }
 245
 246 /************************************************************************
 247  *                                                                      *
 248  *                      Dedicated parser for templates                  *
 249  *                                                                      *
 250  ************************************************************************/
 251
 252 #define CUR (*ctxt->cur)
 253 #define SKIP(val) ctxt->cur += (val)
 254 #define NXT(val) ctxt->cur[(val)]
 255 #define CUR_PTR ctxt->cur
 256
 257 #define SKIP_BLANKS                                                     \
 258     while (IS_BLANK(CUR)) NEXT
 259
 260 #define CURRENT (*ctxt->cur)
 261 #define NEXT ((*ctxt->cur) ?  ctxt->cur++: ctxt->cur)
 262
 263
 264 #define PUSH(step)                                              \
 265     if (xsltCompMatchAddOp(ctxt->comp, (xsltOp) step)) goto error;
 266
 267 #define PUSHSTR(step)                                           \
 268     if (xsltCompMatchAddValue(ctxt->comp, (xmlChar *) step)) goto error;
 269
 270 /**
 271  * xsltScanName:
 272  * @ctxt:  the XPath Parser context
 273  *
 274  * Trickery: parse an XML name but without consuming the input flow
 275  * Needed to avoid insanity in the parser state.
 276  *
 277  * [4] NameChar ::= Letter | Digit | '.' | '-' | '_' | ':' |
 278  *                  CombiningChar | Extender
 279  *
 280  * [5] Name ::= (Letter | '_' | ':') (NameChar)*
 281  *
 282  * [6] Names ::= Name (S Name)*
 283  *
 284  * Returns the Name parsed or NULL
 285  */
 286
 287 xmlChar *
 288 xsltScanName(xsltParserContextPtr ctxt) {
 289     xmlChar buf[XML_MAX_NAMELEN];
 290     int len = 0;
 291
 292     SKIP_BLANKS;
 293     if (!IS_LETTER(CUR) && (CUR != '_') &&
 294         (CUR != ':')) {
 295         return(NULL);
 296     }
 297
 298     while ((IS_LETTER(NXT(len))) || (IS_DIGIT(NXT(len))) ||
 299            (NXT(len) == '.') || (NXT(len) == '-') ||
 300            (NXT(len) == '_') || (NXT(len) == ':') ||
 301            (IS_COMBINING(NXT(len))) ||
 302            (IS_EXTENDER(NXT(len)))) {
 303         buf[len] = NXT(len);
 304         len++;
 305         if (len >= XML_MAX_NAMELEN) {
 306             xmlGenericError(xmlGenericErrorContext,
 307                "xmlScanName: reached XML_MAX_NAMELEN limit\n");
 308             while ((IS_LETTER(NXT(len))) || (IS_DIGIT(NXT(len))) ||
 309                    (NXT(len) == '.') || (NXT(len) == '-') ||
 310                    (NXT(len) == '_') || (NXT(len) == ':') ||
 311                    (IS_COMBINING(NXT(len))) ||
 312                    (IS_EXTENDER(NXT(len))))
 313                  len++;
 314             break;
 315         }
 316     }
 317     SKIP(len);
 318     return(xmlStrndup(buf, len));
 319 }
 320 /*
 321  * Compile the XSLT LocationPathPattern
 322  * [3] IdKeyPattern ::= 'id' '(' Literal ')'
 323  *                    | 'key' '(' Literal ',' Literal ')'
 324  */
 325
 326 /**
 327  * xsltCompileStepPattern:
 328  * @comp:  the compilation context
 329  * @token:  a posible precompiled name
 330  *
 331  * Compile the XSLT StepPattern and generates a precompiled
 332  * form suitable for fast matching.
 333  *
 334  * [5] StepPattern ::= ChildOrAttributeAxisSpecifier NodeTest Predicate*
 335  * [6] ChildOrAttributeAxisSpecifier ::= AbbreviatedAxisSpecifier
 336  *                                     | ('child' | 'attribute') '::'
 337  * from XPath
 338  * [7]  NodeTest ::= NameTest
 339  *                 | NodeType '(' ')'
 340  *                 | 'processing-instruction' '(' Literal ')'
 341  * [8] Predicate ::= '[' PredicateExpr ']'
 342  * [9] PredicateExpr ::= Expr
 343  * [13] AbbreviatedAxisSpecifier ::= '@'?
 344  * [37] NameTest ::= '*' | NCName ':' '*' | QName
 345  */
 346
 347 void
 348 xsltCompileStepPattern(xsltParserContextPtr ctxt, xmlChar *token) {
 349     SKIP_BLANKS;
 350     if ((token == NULL) && (CUR == '@')) {
 351         token = xsltScanName(ctxt);
 352         if (token == NULL) {
 353             xsltGenericError(xsltGenericErrorContext,
 354                     "xsltCompilePattern : Name expected\n");
 355             ctxt->error = 1;
 356             return;
 357         }
 358     }
 359     if (token == NULL)
 360         token = xsltScanName(ctxt);
 361     if (token == NULL) {
 362         xsltGenericError(xsltGenericErrorContext,
 363                 "xsltCompilePattern : Name expected\n");
 364         ctxt->error = 1;
 365         return;
 366     }
 367     SKIP_BLANKS;
 368     if (CUR == '(') {
 369         TODO;
 370         /* if (xmlStrEqual(token, "processing-instruction")) */
 371     } else if (CUR == ':') {
 372         TODO;
 373     } else if (CUR == '*') {
 374         TODO;
 375     } else {
 376         PUSH(XSLT_OP_ELEM);
 377         PUSHSTR(token);
 378     }
 379     SKIP_BLANKS;
 380     while (CUR == '[') {
 381         TODO;
 382     }
 383     return;
 384 error:
 385     ctxt->error = 1;
 386 }
 387
 388 /**
 389  * xsltCompileRelativePathPattern:
 390  * @comp:  the compilation context
 391  * @token:  a posible precompiled name
 392  *
 393  * Compile the XSLT RelativePathPattern and generates a precompiled
 394  * form suitable for fast matching.
 395  *
 396  * [4] RelativePathPattern ::= StepPattern
 397  *                           | RelativePathPattern '/' StepPattern
 398  *                           | RelativePathPattern '//' StepPattern
 399  */
 400 void
 401 xsltCompileRelativePathPattern(xsltParserContextPtr ctxt, xmlChar *token) {
 402     xsltCompileStepPattern(ctxt, token);
 403     if (ctxt->error)
 404         goto error;
 405     SKIP_BLANKS;
 406     while ((CUR != 0) && (CUR != '|')) {
 407         if ((CUR == '/') && (NXT(1) == '/')) {
 408             PUSH(XSLT_OP_ANCESTOR);
 409             NEXT;
 410             NEXT;
 411             SKIP_BLANKS;
 412             xsltCompileStepPattern(ctxt, NULL);
 413         } else if (CUR == '/') {
 414             PUSH(XSLT_OP_PARENT);
 415             NEXT;
 416             SKIP_BLANKS;
 417             if ((CUR != 0) || (CUR == '|')) {
 418                 xsltCompileRelativePathPattern(ctxt, NULL);
 419             }
 420         } else {
 421             ctxt->error = 1;
 422         }
 423         if (ctxt->error)
 424             goto error;
 425         SKIP_BLANKS;
 426     }
 427 error:
 428     return;
 429 }
 430
 431 /**
 432  * xsltCompileLocationPathPattern:
 433  * @comp:  the compilation context
 434  *
 435  * Compile the XSLT LocationPathPattern and generates a precompiled
 436  * form suitable for fast matching.
 437  *
 438  * [2] LocationPathPattern ::= '/' RelativePathPattern?
 439  *                           | IdKeyPattern (('/' | '//') RelativePathPattern)?
 440  *                           | '//'? RelativePathPattern
 441  */
 442 void
 443 xsltCompileLocationPathPattern(xsltParserContextPtr ctxt) {
 444     SKIP_BLANKS;
 445     if ((CUR == '/') && (NXT(1) == '/')) {
 446         /*
 447          * since we reverse the query
 448          * a leading // can be safely ignored
 449          */
 450         NEXT;
 451         NEXT;
 452         xsltCompileRelativePathPattern(ctxt, NULL);
 453     } else if (CUR == '/') {
 454         /*
 455          * We need to find root as the parent
 456          */
 457         NEXT;
 458         SKIP_BLANKS;
 459         PUSH(XSLT_OP_ROOT);
 460         PUSH(XSLT_OP_PARENT);
 461         if ((CUR != 0) || (CUR == '|')) {
 462             xsltCompileRelativePathPattern(ctxt, NULL);
 463         }
 464     } else {
 465         xmlChar *name;
 466         name = xsltScanName(ctxt);
 467         if (name == NULL) {
 468             xsltGenericError(xsltGenericErrorContext,
 469                     "xsltCompilePattern : Name expected\n");
 470             ctxt->error = 1;
 471             return;
 472         }
 473         SKIP_BLANKS;
 474         if (CUR == '(') {
 475             TODO
 476         }
 477         xsltCompileRelativePathPattern(ctxt, name);
 478     }
 479 error:
 480     return;
 481 }
 482
 483 /**
 484  * xsltCompilePattern:
 485  * @pattern an XSLT pattern
 486  *
 487  * Compile the XSLT pattern and generates a precompiled form suitable
 488  * for fast matching.
 489  * Note that the splitting as union of patterns is expected to be handled
 490  * by the caller
 491  *
 492  * [1] Pattern ::= LocationPathPattern | Pattern '|' LocationPathPattern
 493  *
 494  * Returns the generated xsltCompMatchPtr or NULL in case of failure
 495  */
 496
 497 xsltCompMatchPtr
 498 xsltCompilePattern(const xmlChar *pattern) {
 499     xsltParserContextPtr ctxt;
 500     xsltCompMatchPtr ret;
 501     const xmlChar *cur;
 502
 503     if (pattern == NULL) {
 504         xsltGenericError(xsltGenericErrorContext,
 505                 "xsltCompilePattern : NULL pattern\n");
 506         return(NULL);
 507     }
 508
 509 #ifdef DEBUG_PARSING
 510     xsltGenericError(xsltGenericErrorContext,
 511             "xsltCompilePattern : parsing '%s'\n", pattern);
 512 #endif
 513
 514     cur = pattern;
 515     while (IS_BLANK(*cur)) cur++;
 516     if (*cur == 0) {
 517         xsltGenericError(xsltGenericErrorContext,
 518                 "xsltCompilePattern : NULL pattern\n");
 519         return(NULL);
 520     }
 521     ctxt = xsltNewParserContext();
 522     if (ctxt == NULL)
 523         return(NULL);
 524     ret = xsltNewCompMatch();
 525     if (ret == NULL) {
 526         xsltFreeParserContext(ctxt);
 527         return(NULL);
 528     }
 529
 530     ctxt->comp = ret;
 531     ctxt->base = pattern;
 532     ctxt->cur = cur;
 533     xsltCompileLocationPathPattern(ctxt);
 534     if (ctxt->error)
 535         goto error;
 536
 537     /*
 538      * Reverse for faster interpretation.
 539      */
 540     xsltReverseCompMatch(ret);
 541
 542     xsltFreeParserContext(ctxt);
 543     return(ret);
 544
 545 error:
 546     xsltFreeParserContext(ctxt);
 547     xsltFreeCompMatch(ret);
 548     return(NULL);
 549
 550 }
 551
 552
 553 /************************************************************************
 554  *                                                                      *
 555  *                      Module interfaces                               *
 556  *                                                                      *
 557  ************************************************************************/
 558
 559 /**
 560  * xsltAddTemplate:
 561  * @style: an XSLT stylesheet
 562  * @cur: an XSLT template
 563  *
 564  * Register the XSLT pattern associated to @cur
 565  *
 566  * Returns -1 in case of error, 0 otherwise
 567  */
 568 int
 569 xsltAddTemplate(xsltStylesheetPtr style, xsltTemplatePtr cur) {
 570     xsltCompMatchPtr pat, list;
 571     const xmlChar *name;
 572
 573     /*
 574      * get a compiled form of the pattern
 575      */
 576     /* TODO : handle | in patterns as multple pat !!! */
 577     pat = xsltCompilePattern(cur->match);
 578     if (pat == NULL)
 579         return(-1);
 580     if (cur->priority != XSLT_PAT_NO_PRIORITY)
 581         pat->priority = cur->priority;
 582
 583     /*
 584      * insert it in the hash table list corresponding to its lookup name
 585      */
 586     switch (pat->steps[0].op) {
 587         case XSLT_OP_ELEM:
 588         case XSLT_OP_CHILD:
 589         case XSLT_OP_ATTR:
 590         case XSLT_OP_PARENT:
 591         case XSLT_OP_ANCESTOR:
 592         case XSLT_OP_ID:
 593         case XSLT_OP_KEY:
 594         case XSLT_OP_NS:
 595              name = pat->steps[1].value;
 596              break;
 597         case XSLT_OP_ROOT:
 598              name = (const xmlChar *) "/";
 599              break;
 600         case XSLT_OP_ALL:
 601              name = (const xmlChar *) "*";
 602              break;
 603         case XSLT_OP_END:
 604         case XSLT_OP_PREDICATE:
 605             xsltGenericError(xsltGenericErrorContext,
 606                     "xsltAddTemplate: invalid compiled pattern\n");
 607             xsltFreeCompMatch(pat);
 608             return(-1);
 609     }
 610     if (style->templatesHash == NULL) {
 611         style->templatesHash = xmlHashCreate(0);
 612         if (style->templatesHash == NULL) {
 613             xsltFreeCompMatch(pat);
 614             return(-1);
 615         }
 616 #ifdef DEBUG_PARSING
 617         xsltGenericError(xsltGenericErrorContext,
 618                 "xsltAddTemplate: created template hash\n");
 619 #endif
 620         xmlHashAddEntry(style->templatesHash, name, pat);
 621 #ifdef DEBUG_PARSING
 622         xsltGenericError(xsltGenericErrorContext,
 623                 "xsltAddTemplate: added new hash %s\n", name);
 624 #endif
 625     } else {
 626         list = (xsltCompMatchPtr) xmlHashLookup(style->templatesHash, name);
 627         if (list == NULL) {
 628             xmlHashAddEntry(style->templatesHash, name, pat);
 629 #ifdef DEBUG_PARSING
 630             xsltGenericError(xsltGenericErrorContext,
 631                     "xsltAddTemplate: added new hash %s\n", name);
 632 #endif
 633         } else {
 634             /*
 635              * Note '<=' since one must choose among the matching template
 636              * rules that are left, the one that occurs last in the stylesheet
 637              */
 638             if (list->priority <= pat->priority) {
 639                 pat->next = list;
 640                 xmlHashAddEntry(style->templatesHash, name, pat);
 641 #ifdef DEBUG_PARSING
 642                 xsltGenericError(xsltGenericErrorContext,
 643                         "xsltAddTemplate: added head hash for %s\n", name);
 644 #endif
 645             } else {
 646                 while (list->next != NULL) {
 647                     if (list->next->priority < pat->priority)
 648                         break;
 649                 }
 650                 pat->next = list->next;
 651                 list->next = pat;
 652             }
 653         }
 654     }
 655     return(0);
 656 }
 657
 658 /**
 659  * xsltAddTemplate:
 660  * @style: an XSLT stylesheet
 661  * @node: an XML Node
 662  *
 663  * Finds the template applying to this node
 664  *
 665  * Returns the xsltTemplatePtr or NULL if not found
 666  */
 667 xsltTemplatePtr
 668 xsltGetTemplate(xsltStylesheetPtr style, xmlNodePtr node) {
 669     return(NULL);
 670 }
 671