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 "xslt.h"
  22 #include "xsltInternals.h"
  23
  24 #define DEBUG_PARSING
  25
  26 /*
  27  * To cleanup
  28  */
  29 xmlChar *xmlSplitQName2(const xmlChar *name, xmlChar **prefix);
  30
  31 /*
  32  * There is no XSLT specific error reporting module yet
  33  */
  34 #define xsltGenericError xmlGenericError
  35 #define xsltGenericErrorContext xmlGenericErrorContext
  36
  37 /*
  38  * Types are private:
  39  */
  40
  41 typedef enum {
  42     XSLT_OP_END=0,
  43     XSLT_OP_ROOT,
  44     XSLT_OP_ELEM,
  45     XSLT_OP_CHILD,
  46     XSLT_OP_ATTR,
  47     XSLT_OP_PARENT,
  48     XSLT_OP_ANCESTOR,
  49     XSLT_OP_ID,
  50     XSLT_OP_KEY,
  51     XSLT_OP_NS,
  52     XSLT_OP_ALL,
  53     XSLT_OP_PREDICATE
  54 } xsltOp;
  55
  56 typedef union _xsltStepOp xsltStepOp;
  57 typedef xsltStepOp *xsltStepOpPtr;
  58 union _xsltStepOp {
  59     xsltOp op;
  60     xmlChar *value;
  61 };
  62
  63 typedef struct _xsltCompMatch xsltCompMatch;
  64 typedef xsltCompMatch *xsltCompMatchPtr;
  65 struct _xsltCompMatch {
  66     struct _xsltCompMatch *next; /* siblings in the name hash */
  67     int priority;                /* the priority */
  68
  69     /* TODO fix the statically allocated size */
  70     int nbStep;
  71     int maxStep;
  72     xsltStepOp steps[20];        /* ops for computation */
  73 };
  74
  75
  76 /************************************************************************
  77  *                                                                      *
  78  *                      Type functions                                  *
  79  *                                                                      *
  80  ************************************************************************/
  81
  82 /**
  83  * xsltNewCompMatch:
  84  *
  85  * Create a new XSLT CompMatch
  86  *
  87  * Returns the newly allocated xsltCompMatchPtr or NULL in case of error
  88  */
  89 xsltCompMatchPtr
  90 xsltNewCompMatch(void) {
  91     xsltCompMatchPtr cur;
  92
  93     cur = (xsltCompMatchPtr) xmlMalloc(sizeof(xsltCompMatch));
  94     if (cur == NULL) {
  95         xsltGenericError(xsltGenericErrorContext,
  96                 "xsltNewCompMatch : malloc failed\n");
  97         return(NULL);
  98     }
  99     memset(cur, 0, sizeof(xsltCompMatch));
 100     cur->maxStep = 20;
 101     return(cur);
 102 }
 103
 104 /**
 105  * xsltFreeCompMatch:
 106  * @comp:  an XSLT comp
 107  *
 108  * Free up the memory allocated by @comp
 109  */
 110 void
 111 xsltFreeCompMatch(xsltCompMatchPtr comp) {
 112     if (comp == NULL)
 113         return;
 114     memset(comp, -1, sizeof(xsltCompMatch));
 115     xmlFree(comp);
 116 }
 117
 118 /**
 119  * xsltFreeCompMatchList:
 120  * @comp:  an XSLT comp list
 121  *
 122  * Free up the memory allocated by all the elements of @comp
 123  */
 124 void
 125 xsltFreeCompMatchList(xsltCompMatchPtr comp) {
 126     xsltCompMatchPtr cur;
 127
 128     while (comp != NULL) {
 129         cur = comp;
 130         comp = comp->next;
 131         xsltFreeCompMatch(cur);
 132     }
 133 }
 134
 135 /**
 136  * xsltCompMatchAddOp:
 137  * @comp:  the compiled match expression
 138  * @op:  an op
 139  *
 140  * Add an step to an XSLT Compiled Match
 141  *
 142  * Returns -1 in case of failure, 0 otherwise.
 143  */
 144 int
 145 xsltCompMatchAddOp(xsltCompMatchPtr comp, xsltOp op) {
 146     if (comp->nbStep >= 20) {
 147         xsltGenericError(xsltGenericErrorContext,
 148                 "xsltCompMatchAddOp: overflow\n");
 149         return(-1);
 150     }
 151     comp->steps[comp->nbStep++].op = op;
 152     return(0);
 153 }
 154
 155 /**
 156  * xsltCompMatchAddValue:
 157  * @comp:  the compiled match expression
 158  * @val:  a name
 159  *
 160  * Add an step to an XSLT Compiled Match
 161  *
 162  * Returns -1 in case of failure, 0 otherwise.
 163  */
 164 int
 165 xsltCompMatchAddValue(xsltCompMatchPtr comp, xmlChar *val) {
 166     if (comp->nbStep >= 20) {
 167         xsltGenericError(xsltGenericErrorContext,
 168                 "xsltCompMatchAddOp: overflow\n");
 169         return(-1);
 170     }
 171     comp->steps[comp->nbStep++].value = val;
 172     return(0);
 173 }
 174
 175 /**
 176  * xsltReverseCompMatch:
 177  * @comp:  the compiled match expression
 178  *
 179  * reverse all the stack of expressions
 180  */
 181 void
 182 xsltReverseCompMatch(xsltCompMatchPtr comp) {
 183     int i = 0;
 184     int j = comp->nbStep - 1;
 185
 186     while (j > i) {
 187         register xmlChar *tmp;
 188         tmp = comp->steps[i].value;
 189         comp->steps[i].value = comp->steps[j].value;
 190         comp->steps[j].value = tmp;
 191         j--;
 192         i++;
 193     }
 194     comp->steps[comp->nbStep].op = XSLT_OP_END;
 195 }
 196
 197 /************************************************************************
 198  *                                                                      *
 199  *                      Dedicated parser for templates                  *
 200  *                                                                      *
 201  ************************************************************************/
 202
 203 #define IS_BLANK(c) (((c) == 0x20) || ((c) == 0x09) || ((c) == 0xA) ||  \
 204                      ((c) == 0x0D))
 205
 206 #define SKIP_BLANKS while (IS_BLANK(*cur)) cur++;
 207
 208 #define CUR (*(cur))
 209 #define NXT (*(cur + 1))
 210 #define NEXT cur++
 211
 212 #define PUSH(comp, step)                                                \
 213     if (xsltCompMatchAddOp((comp), (xsltOp) step)) goto error;
 214
 215 #define PUSHSTR(comp, step)                                             \
 216     if (xsltCompMatchAddValue((comp), (xmlChar *) step)) goto error;
 217
 218 /*
 219  * Compile the XSLT LocationPathPattern
 220  * [2] LocationPathPattern ::= '/' RelativePathPattern?
 221  *                           | IdKeyPattern (('/' | '//') RelativePathPattern)?
 222  *                           | '//'? RelativePathPattern
 223  * [3] IdKeyPattern ::= 'id' '(' Literal ')'
 224  *                    | 'key' '(' Literal ',' Literal ')'
 225  * [4] RelativePathPattern ::= StepPattern
 226  *                           | RelativePathPattern '/' StepPattern
 227  *                           | RelativePathPattern '//' StepPattern
 228  * [5] StepPattern ::= ChildOrAttributeAxisSpecifier NodeTest Predicate*
 229  * [6] ChildOrAttributeAxisSpecifier ::= AbbreviatedAxisSpecifier
 230  *                                     | ('child' | 'attribute') '::'
 231  */
 232
 233 /**
 234  * xsltCompilePattern:
 235  * @pattern an XSLT pattern
 236  *
 237  * Compile the XSLT pattern and generates a precompiled form suitable
 238  * for fast matching.
 239  *
 240  * [1] Pattern ::= LocationPathPattern | Pattern '|' LocationPathPattern
 241  * Returns the generated xsltCompMatchPtr or NULL in case of failure
 242  */
 243
 244 xsltCompMatchPtr
 245 xsltCompilePattern(const xmlChar *pattern) {
 246     xsltCompMatchPtr ret;
 247     const xmlChar *cur;
 248
 249     if (pattern == NULL) {
 250         xsltGenericError(xsltGenericErrorContext,
 251                 "xsltCompilePattern : NULL pattern\n");
 252         return(NULL);
 253     }
 254
 255 #ifdef DEBUG_PARSING
 256     xsltGenericError(xsltGenericErrorContext,
 257             "xsltCompilePattern : parsing '%s'\n", pattern);
 258 #endif
 259
 260     cur = pattern;
 261     SKIP_BLANKS;
 262     if (*cur == 0) {
 263         xsltGenericError(xsltGenericErrorContext,
 264                 "xsltCompilePattern : NULL pattern\n");
 265         return(NULL);
 266     }
 267     ret = xsltNewCompMatch();
 268     if (ret == NULL)
 269         return(NULL);
 270
 271     if ((CUR == '/') && (NXT == '/')) {
 272     } else if (CUR == '/') {
 273         PUSH(ret, XSLT_OP_ROOT);
 274     }
 275
 276     /*
 277      * Reverse for faster interpretation.
 278      */
 279     xsltReverseCompMatch(ret);
 280
 281     return(ret);
 282
 283 error:
 284     xsltFreeCompMatch(ret);
 285     return(NULL);
 286
 287 }
 288
 289
 290 /************************************************************************
 291  *                                                                      *
 292  *                      Module interfaces                               *
 293  *                                                                      *
 294  ************************************************************************/
 295
 296 /**
 297  * xsltAddTemplate:
 298  * @style: an XSLT stylesheet
 299  * @cur: an XSLT template
 300  *
 301  * Register the XSLT pattern associated to @cur
 302  *
 303  * Returns -1 in case of error, 0 otherwise
 304  */
 305 int
 306 xsltAddTemplate(xsltStylesheetPtr style, xsltTemplatePtr cur) {
 307     xsltCompMatchPtr pat, list;
 308     const xmlChar *name;
 309
 310     /*
 311      * get a compiled form of the pattern
 312      */
 313     /* TODO : handle | in patterns as multple pat !!! */
 314     pat = xsltCompilePattern(cur->match);
 315     if (pat == NULL)
 316         return(-1);
 317     if (cur->priority != XSLT_PAT_NO_PRIORITY)
 318         pat->priority = cur->priority;
 319
 320     /*
 321      * insert it in the hash table list corresponding to its lookup name
 322      */
 323     switch (pat->steps[0].op) {
 324         case XSLT_OP_ELEM:
 325         case XSLT_OP_CHILD:
 326         case XSLT_OP_ATTR:
 327         case XSLT_OP_PARENT:
 328         case XSLT_OP_ANCESTOR:
 329         case XSLT_OP_ID:
 330         case XSLT_OP_KEY:
 331         case XSLT_OP_NS:
 332              name = pat->steps[1].value;
 333              break;
 334         case XSLT_OP_ROOT:
 335              name = (const xmlChar *) "/";
 336              break;
 337         case XSLT_OP_ALL:
 338              name = (const xmlChar *) "*";
 339              break;
 340         case XSLT_OP_END:
 341         case XSLT_OP_PREDICATE:
 342             xsltGenericError(xsltGenericErrorContext,
 343                     "xsltAddTemplate: invalid compiled pattern\n");
 344             xsltFreeCompMatch(pat);
 345             return(-1);
 346     }
 347     if (style->templatesHash == NULL) {
 348         style->templatesHash = xmlHashCreate(0);
 349         if (style->templatesHash == NULL) {
 350             xsltFreeCompMatch(pat);
 351             return(-1);
 352         }
 353 #ifdef DEBUG_PARSING
 354         xsltGenericError(xsltGenericErrorContext,
 355                 "xsltAddTemplate: created template hash\n");
 356 #endif
 357         xmlHashAddEntry(style->templatesHash, name, pat);
 358 #ifdef DEBUG_PARSING
 359         xsltGenericError(xsltGenericErrorContext,
 360                 "xsltAddTemplate: added new hash %s\n", name);
 361 #endif
 362     } else {
 363         list = (xsltCompMatchPtr) xmlHashLookup(style->templatesHash, name);
 364         if (list == NULL) {
 365             xmlHashAddEntry(style->templatesHash, name, pat);
 366 #ifdef DEBUG_PARSING
 367             xsltGenericError(xsltGenericErrorContext,
 368                     "xsltAddTemplate: added new hash %s\n", name);
 369 #endif
 370         } else {
 371             /*
 372              * Note '<=' since one must choose among the matching template
 373              * rules that are left, the one that occurs last in the stylesheet
 374              */
 375             if (list->priority <= pat->priority) {
 376                 pat->next = list;
 377                 xmlHashAddEntry(style->templatesHash, name, pat);
 378 #ifdef DEBUG_PARSING
 379                 xsltGenericError(xsltGenericErrorContext,
 380                         "xsltAddTemplate: added head hash for %s\n", name);
 381 #endif
 382             } else {
 383                 while (list->next != NULL) {
 384                     if (list->next->priority < pat->priority)
 385                         break;
 386                 }
 387                 pat->next = list->next;
 388                 list->next = pat;
 389             }
 390         }
 391     }
 392     return(0);
 393 }
 394
 395 /**
 396  * xsltAddTemplate:
 397  * @style: an XSLT stylesheet
 398  * @node: an XML Node
 399  *
 400  * Finds the template applying to this node
 401  *
 402  * Returns the xsltTemplatePtr or NULL if not found
 403  */
 404 xsltTemplatePtr
 405 xsltGetTemplate(xsltStylesheetPtr style, xmlNodePtr node) {
 406     return(NULL);
 407 }
 408