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.com
  10  */
  11
  12 /*
  13  * TODO: handle pathological cases like *[*[@a="b"]]
  14  * TODO: detect [number] at compilation, optimize accordingly
  15  */
  16
  17 #define IN_LIBXSLT
  18 #include "libxslt.h"
  19
  20 #include <string.h>
  21
  22 #include <libxml/xmlmemory.h>
  23 #include <libxml/tree.h>
  24 #include <libxml/valid.h>
  25 #include <libxml/hash.h>
  26 #include <libxml/xmlerror.h>
  27 #include <libxml/parserInternals.h>
  28 #include "xslt.h"
  29 #include "xsltInternals.h"
  30 #include "xsltutils.h"
  31 #include "imports.h"
  32 #include "templates.h"
  33 #include "keys.h"
  34 #include "pattern.h"
  35
  36 #ifdef WITH_XSLT_DEBUG
  37 #define WITH_XSLT_DEBUG_PATTERN
  38 #endif
  39
  40 /*
  41  * Types are private:
  42  */
  43
  44 typedef enum {
  45     XSLT_OP_END=0,
  46     XSLT_OP_ROOT,
  47     XSLT_OP_ELEM,
  48     XSLT_OP_CHILD,
  49     XSLT_OP_ATTR,
  50     XSLT_OP_PARENT,
  51     XSLT_OP_ANCESTOR,
  52     XSLT_OP_ID,
  53     XSLT_OP_KEY,
  54     XSLT_OP_NS,
  55     XSLT_OP_ALL,
  56     XSLT_OP_PI,
  57     XSLT_OP_COMMENT,
  58     XSLT_OP_TEXT,
  59     XSLT_OP_NODE,
  60     XSLT_OP_PREDICATE
  61 } xsltOp;
  62
  63 typedef struct _xsltStepState xsltStepState;
  64 typedef xsltStepState *xsltStepStatePtr;
  65 struct _xsltStepState {
  66     int step;
  67     xmlNodePtr node;
  68 };
  69
  70 typedef struct _xsltStepStates xsltStepStates;
  71 typedef xsltStepStates *xsltStepStatesPtr;
  72 struct _xsltStepStates {
  73     int nbstates;
  74     int maxstates;
  75     xsltStepStatePtr states;
  76 };
  77
  78 typedef struct _xsltStepOp xsltStepOp;
  79 typedef xsltStepOp *xsltStepOpPtr;
  80 struct _xsltStepOp {
  81     xsltOp op;
  82     xmlChar *value;
  83     xmlChar *value2;
  84     xmlChar *value3;
  85     xmlXPathCompExprPtr comp;
  86     /*
  87      * Optimisations for count
  88      */
  89     int        previousExtra;
  90     int        indexExtra;
  91     int        lenExtra;
  92 };
  93
  94 struct _xsltCompMatch {
  95     struct _xsltCompMatch *next; /* siblings in the name hash */
  96     float priority;              /* the priority */
  97     const xmlChar *pattern;       /* the pattern */
  98     const xmlChar *mode;         /* the mode */
  99     const xmlChar *modeURI;      /* the mode URI */
 100     xsltTemplatePtr template;    /* the associated template */
 101
 102     /* TODO fix the statically allocated size steps[] */
 103     int nbStep;
 104     int maxStep;
 105     xmlNsPtr *nsList;           /* the namespaces in scope */
 106     int nsNr;                   /* the number of namespaces in scope */
 107     xsltStepOp steps[40];        /* ops for computation */
 108 };
 109
 110 typedef struct _xsltParserContext xsltParserContext;
 111 typedef xsltParserContext *xsltParserContextPtr;
 112 struct _xsltParserContext {
 113     xsltStylesheetPtr style;            /* the stylesheet */
 114     xsltTransformContextPtr ctxt;       /* the transformation or NULL */
 115     const xmlChar *cur;                 /* the current char being parsed */
 116     const xmlChar *base;                /* the full expression */
 117     xmlDocPtr      doc;                 /* the source document */
 118     xmlNodePtr    elem;                 /* the source element */
 119     int error;                          /* error code */
 120     xsltCompMatchPtr comp;              /* the result */
 121 };
 122
 123 /************************************************************************
 124  *                                                                      *
 125  *                      Type functions                                  *
 126  *                                                                      *
 127  ************************************************************************/
 128
 129 /**
 130  * xsltNewCompMatch:
 131  *
 132  * Create a new XSLT CompMatch
 133  *
 134  * Returns the newly allocated xsltCompMatchPtr or NULL in case of error
 135  */
 136 static xsltCompMatchPtr
 137 xsltNewCompMatch(void) {
 138     xsltCompMatchPtr cur;
 139
 140     cur = (xsltCompMatchPtr) xmlMalloc(sizeof(xsltCompMatch));
 141     if (cur == NULL) {
 142         xsltTransformError(NULL, NULL, NULL,
 143                 "xsltNewCompMatch : malloc failed\n");
 144         return(NULL);
 145     }
 146     memset(cur, 0, sizeof(xsltCompMatch));
 147     cur->maxStep = 40;
 148     cur->nsNr = 0;
 149     cur->nsList = NULL;
 150     return(cur);
 151 }
 152
 153 /**
 154  * xsltFreeCompMatch:
 155  * @comp:  an XSLT comp
 156  *
 157  * Free up the memory allocated by @comp
 158  */
 159 static void
 160 xsltFreeCompMatch(xsltCompMatchPtr comp) {
 161     xsltStepOpPtr op;
 162     int i;
 163
 164     if (comp == NULL)
 165         return;
 166     if (comp->pattern != NULL)
 167         xmlFree((xmlChar *)comp->pattern);
 168     if (comp->nsList != NULL)
 169         xmlFree(comp->nsList);
 170     for (i = 0;i < comp->nbStep;i++) {
 171         op = &comp->steps[i];
 172         if (op->value != NULL)
 173             xmlFree(op->value);
 174         if (op->value2 != NULL)
 175             xmlFree(op->value2);
 176         if (op->value3 != NULL)
 177             xmlFree(op->value3);
 178         if (op->comp != NULL)
 179             xmlXPathFreeCompExpr(op->comp);
 180     }
 181     memset(comp, -1, sizeof(xsltCompMatch));
 182     xmlFree(comp);
 183 }
 184
 185 /**
 186  * xsltFreeCompMatchList:
 187  * @comp:  an XSLT comp list
 188  *
 189  * Free up the memory allocated by all the elements of @comp
 190  */
 191 void
 192 xsltFreeCompMatchList(xsltCompMatchPtr comp) {
 193     xsltCompMatchPtr cur;
 194
 195     while (comp != NULL) {
 196         cur = comp;
 197         comp = comp->next;
 198         xsltFreeCompMatch(cur);
 199     }
 200 }
 201
 202 /**
 203  * xsltNormalizeCompSteps:
 204  * @payload: pointer to template hash table entry
 205  * @data: pointer to the stylesheet
 206  * @name: template match name
 207  *
 208  * This is a hashtable scanner function to normalize the compiled
 209  * steps of an imported stylesheet.
 210  */
 211 void xsltNormalizeCompSteps(void *payload,
 212         void *data, const xmlChar *name ATTRIBUTE_UNUSED) {
 213     xsltCompMatchPtr comp = payload;
 214     xsltStylesheetPtr style = data;
 215     int ix;
 216
 217     for (ix = 0; ix < comp->nbStep; ix++) {
 218         comp->steps[ix].previousExtra += style->extrasNr;
 219         comp->steps[ix].indexExtra += style->extrasNr;
 220         comp->steps[ix].lenExtra += style->extrasNr;
 221     }
 222 }
 223
 224 /**
 225  * xsltNewParserContext:
 226  * @style:  the stylesheet
 227  * @ctxt:  the transformation context, if done at run-time
 228  *
 229  * Create a new XSLT ParserContext
 230  *
 231  * Returns the newly allocated xsltParserContextPtr or NULL in case of error
 232  */
 233 static xsltParserContextPtr
 234 xsltNewParserContext(xsltStylesheetPtr style, xsltTransformContextPtr ctxt) {
 235     xsltParserContextPtr cur;
 236
 237     cur = (xsltParserContextPtr) xmlMalloc(sizeof(xsltParserContext));
 238     if (cur == NULL) {
 239         xsltTransformError(NULL, NULL, NULL,
 240                 "xsltNewParserContext : malloc failed\n");
 241         return(NULL);
 242     }
 243     memset(cur, 0, sizeof(xsltParserContext));
 244     cur->style = style;
 245     cur->ctxt = ctxt;
 246     return(cur);
 247 }
 248
 249 /**
 250  * xsltFreeParserContext:
 251  * @ctxt:  an XSLT parser context
 252  *
 253  * Free up the memory allocated by @ctxt
 254  */
 255 static void
 256 xsltFreeParserContext(xsltParserContextPtr ctxt) {
 257     if (ctxt == NULL)
 258         return;
 259     memset(ctxt, -1, sizeof(xsltParserContext));
 260     xmlFree(ctxt);
 261 }
 262
 263 /**
 264  * xsltCompMatchAdd:
 265  * @comp:  the compiled match expression
 266  * @op:  an op
 267  * @value:  the first value
 268  * @value2:  the second value
 269  *
 270  * Add an step to an XSLT Compiled Match
 271  *
 272  * Returns -1 in case of failure, 0 otherwise.
 273  */
 274 static int
 275 xsltCompMatchAdd(xsltParserContextPtr ctxt, xsltCompMatchPtr comp,
 276                  xsltOp op, xmlChar * value, xmlChar * value2)
 277 {
 278     if (comp->nbStep >= 40) {
 279         xsltTransformError(NULL, NULL, NULL,
 280                          "xsltCompMatchAdd: overflow\n");
 281         return (-1);
 282     }
 283     comp->steps[comp->nbStep].op = op;
 284     comp->steps[comp->nbStep].value = value;
 285     comp->steps[comp->nbStep].value2 = value2;
 286     if (ctxt->ctxt != NULL) {
 287         comp->steps[comp->nbStep].previousExtra =
 288             xsltAllocateExtraCtxt(ctxt->ctxt);
 289         comp->steps[comp->nbStep].indexExtra =
 290             xsltAllocateExtraCtxt(ctxt->ctxt);
 291         comp->steps[comp->nbStep].lenExtra =
 292             xsltAllocateExtraCtxt(ctxt->ctxt);
 293     } else {
 294         comp->steps[comp->nbStep].previousExtra =
 295             xsltAllocateExtra(ctxt->style);
 296         comp->steps[comp->nbStep].indexExtra =
 297             xsltAllocateExtra(ctxt->style);
 298         comp->steps[comp->nbStep].lenExtra =
 299             xsltAllocateExtra(ctxt->style);
 300     }
 301     if (op == XSLT_OP_PREDICATE) {
 302         comp->steps[comp->nbStep].comp = xsltXPathCompile(ctxt->style, value);
 303     }
 304     comp->nbStep++;
 305     return (0);
 306 }
 307
 308 /**
 309  * xsltSwapTopCompMatch:
 310  * @comp:  the compiled match expression
 311  *
 312  * reverse the two top steps.
 313  */
 314 static void
 315 xsltSwapTopCompMatch(xsltCompMatchPtr comp) {
 316     int i;
 317     int j = comp->nbStep - 1;
 318
 319     if (j > 0) {
 320         register xmlChar *tmp;
 321         register xsltOp op;
 322         register xmlXPathCompExprPtr expr;
 323         i = j - 1;
 324         tmp = comp->steps[i].value;
 325         comp->steps[i].value = comp->steps[j].value;
 326         comp->steps[j].value = tmp;
 327         tmp = comp->steps[i].value2;
 328         comp->steps[i].value2 = comp->steps[j].value2;
 329         comp->steps[j].value2 = tmp;
 330         op = comp->steps[i].op;
 331         comp->steps[i].op = comp->steps[j].op;
 332         comp->steps[j].op = op;
 333         expr = comp->steps[i].comp;
 334         comp->steps[i].comp = comp->steps[j].comp;
 335         comp->steps[j].comp = expr;
 336     }
 337 }
 338
 339 /**
 340  * xsltReverseCompMatch:
 341  * @comp:  the compiled match expression
 342  *
 343  * reverse all the stack of expressions
 344  */
 345 static void
 346 xsltReverseCompMatch(xsltCompMatchPtr comp) {
 347     int i = 0;
 348     int j = comp->nbStep - 1;
 349
 350     while (j > i) {
 351         register xmlChar *tmp;
 352         register xsltOp op;
 353         register xmlXPathCompExprPtr expr;
 354         tmp = comp->steps[i].value;
 355         comp->steps[i].value = comp->steps[j].value;
 356         comp->steps[j].value = tmp;
 357         tmp = comp->steps[i].value2;
 358         comp->steps[i].value2 = comp->steps[j].value2;
 359         comp->steps[j].value2 = tmp;
 360         op = comp->steps[i].op;
 361         comp->steps[i].op = comp->steps[j].op;
 362         comp->steps[j].op = op;
 363         expr = comp->steps[i].comp;
 364         comp->steps[i].comp = comp->steps[j].comp;
 365         comp->steps[j].comp = expr;
 366         j--;
 367         i++;
 368     }
 369     comp->steps[comp->nbStep++].op = XSLT_OP_END;
 370 }
 371
 372 /************************************************************************
 373  *                                                                      *
 374  *              The interpreter for the precompiled patterns            *
 375  *                                                                      *
 376  ************************************************************************/
 377
 378 static int
 379 xsltPatPushState(xsltStepStates *states, int step, xmlNodePtr node) {
 380     if ((states->states == NULL) || (states->maxstates <= 0)) {
 381         states->maxstates = 4;
 382         states->nbstates = 0;
 383         states->states = xmlMalloc(4 * sizeof(xsltStepState));
 384     }
 385     else if (states->maxstates <= states->nbstates) {
 386         xsltStepState *tmp;
 387
 388         tmp = (xsltStepStatePtr) xmlRealloc(states->states,
 389                                2 * states->maxstates * sizeof(xsltStepState));
 390         if (tmp == NULL)
 391             return(-1);
 392         states->states = tmp;
 393         states->maxstates *= 2;
 394     }
 395     states->states[states->nbstates].step = step;
 396     states->states[states->nbstates++].node = node;
 397 #if 0
 398     fprintf(stderr, "Push: %d, %s\n", step, node->name);
 399 #endif
 400     return(0);
 401 }
 402
 403 /**
 404  * xsltTestCompMatch:
 405  * @ctxt:  a XSLT process context
 406  * @comp: the precompiled pattern
 407  * @node: a node
 408  * @mode:  the mode name or NULL
 409  * @modeURI:  the mode URI or NULL
 410  *
 411  * Test whether the node matches the pattern
 412  *
 413  * Returns 1 if it matches, 0 if it doesn't and -1 in case of failure
 414  */
 415 static int
 416 xsltTestCompMatch(xsltTransformContextPtr ctxt, xsltCompMatchPtr comp,
 417                   xmlNodePtr node, const xmlChar *mode,
 418                   const xmlChar *modeURI) {
 419     int i;
 420     xsltStepOpPtr step, sel = NULL;
 421     xsltStepStates states = {0, 0, NULL}; /* // may require backtrack */
 422
 423     if ((comp == NULL) || (node == NULL) || (ctxt == NULL)) {
 424         xsltTransformError(ctxt, NULL, node,
 425                 "xsltTestCompMatch: null arg\n");
 426         return(-1);
 427     }
 428     if (mode != NULL) {
 429         if (comp->mode == NULL)
 430             return(0);
 431         /*
 432          * both mode strings must be interned on the stylesheet dictionary
 433          */
 434         if (comp->mode != mode)
 435             return(0);
 436     } else {
 437         if (comp->mode != NULL)
 438             return(0);
 439     }
 440     if (modeURI != NULL) {
 441         if (comp->modeURI == NULL)
 442             return(0);
 443         /*
 444          * both modeURI strings must be interned on the stylesheet dictionary
 445          */
 446         if (comp->modeURI != modeURI)
 447             return(0);
 448     } else {
 449         if (comp->modeURI != NULL)
 450             return(0);
 451     }
 452     i = 0;
 453 restart:
 454     for (;i < comp->nbStep;i++) {
 455         step = &comp->steps[i];
 456         if (step->op != XSLT_OP_PREDICATE)
 457             sel = step;
 458         switch (step->op) {
 459             case XSLT_OP_END:
 460                 goto found;
 461             case XSLT_OP_ROOT:
 462                 if ((node->type == XML_DOCUMENT_NODE) ||
 463 #ifdef LIBXML_DOCB_ENABLED
 464                     (node->type == XML_DOCB_DOCUMENT_NODE) ||
 465 #endif
 466                     (node->type == XML_HTML_DOCUMENT_NODE))
 467                     continue;
 468                 if ((node->type == XML_ELEMENT_NODE) && (node->name[0] == ' '))
 469                     continue;
 470                 goto rollback;
 471             case XSLT_OP_ELEM:
 472                 if (node->type != XML_ELEMENT_NODE)
 473                     goto rollback;
 474                 if (step->value == NULL)
 475                     continue;
 476                 if (step->value[0] != node->name[0])
 477                     goto rollback;
 478                 if (!xmlStrEqual(step->value, node->name))
 479                     goto rollback;
 480
 481                 /* Namespace test */
 482                 if (node->ns == NULL) {
 483                     if (step->value2 != NULL)
 484                         goto rollback;
 485                 } else if (node->ns->href != NULL) {
 486                     if (step->value2 == NULL)
 487                         goto rollback;
 488                     if (!xmlStrEqual(step->value2, node->ns->href))
 489                         goto rollback;
 490                 }
 491                 continue;
 492             case XSLT_OP_CHILD: {
 493                 xmlNodePtr lst;
 494
 495                 if ((node->type != XML_ELEMENT_NODE) &&
 496                     (node->type != XML_DOCUMENT_NODE) &&
 497 #ifdef LIBXML_DOCB_ENABLED
 498                     (node->type != XML_DOCB_DOCUMENT_NODE) &&
 499 #endif
 500                     (node->type != XML_HTML_DOCUMENT_NODE))
 501                     goto rollback;
 502
 503                 lst = node->children;
 504
 505                 if (step->value != NULL) {
 506                     while (lst != NULL) {
 507                         if ((lst->type == XML_ELEMENT_NODE) &&
 508                             (step->value[0] == lst->name[0]) &&
 509                             (xmlStrEqual(step->value, lst->name)))
 510                             break;
 511                         lst = lst->next;
 512                     }
 513                     if (lst != NULL)
 514                         continue;
 515                 }
 516                 goto rollback;
 517             }
 518             case XSLT_OP_ATTR:
 519                 if (node->type != XML_ATTRIBUTE_NODE)
 520                     goto rollback;
 521                 if (step->value != NULL) {
 522                     if (step->value[0] != node->name[0])
 523                         goto rollback;
 524                     if (!xmlStrEqual(step->value, node->name))
 525                         goto rollback;
 526                 }
 527                 /* Namespace test */
 528                 if (node->ns == NULL) {
 529                     if (step->value2 != NULL)
 530                         goto rollback;
 531                 } else if (step->value2 != NULL) {
 532                     if (!xmlStrEqual(step->value2, node->ns->href))
 533                         goto rollback;
 534                 }
 535                 continue;
 536             case XSLT_OP_PARENT:
 537                 if ((node->type == XML_DOCUMENT_NODE) ||
 538                     (node->type == XML_HTML_DOCUMENT_NODE) ||
 539 #ifdef LIBXML_DOCB_ENABLED
 540                     (node->type == XML_DOCB_DOCUMENT_NODE) ||
 541 #endif
 542                     (node->type == XML_NAMESPACE_DECL))
 543                     goto rollback;
 544                 node = node->parent;
 545                 if (node == NULL)
 546                     goto rollback;
 547                 if (step->value == NULL)
 548                     continue;
 549                 if (step->value[0] != node->name[0])
 550                     goto rollback;
 551                 if (!xmlStrEqual(step->value, node->name))
 552                     goto rollback;
 553                 /* Namespace test */
 554                 if (node->ns == NULL) {
 555                     if (step->value2 != NULL)
 556                         goto rollback;
 557                 } else if (node->ns->href != NULL) {
 558                     if (step->value2 == NULL)
 559                         goto rollback;
 560                     if (!xmlStrEqual(step->value2, node->ns->href))
 561                         goto rollback;
 562                 }
 563                 continue;
 564             case XSLT_OP_ANCESTOR:
 565                 /* TODO: implement coalescing of ANCESTOR/NODE ops */
 566                 if (step->value == NULL) {
 567                     step = &comp->steps[i+1];
 568                     if (step->op == XSLT_OP_ROOT)
 569                         goto found;
 570                     /* added NS, ID and KEY as a result of bug 168208 */
 571                     if ((step->op != XSLT_OP_ELEM) &&
 572                         (step->op != XSLT_OP_ALL) &&
 573                         (step->op != XSLT_OP_NS) &&
 574                         (step->op != XSLT_OP_ID) &&
 575                         (step->op != XSLT_OP_KEY))
 576                         goto rollback;
 577                 }
 578                 if (node == NULL)
 579                     goto rollback;
 580                 if ((node->type == XML_DOCUMENT_NODE) ||
 581                     (node->type == XML_HTML_DOCUMENT_NODE) ||
 582 #ifdef LIBXML_DOCB_ENABLED
 583                     (node->type == XML_DOCB_DOCUMENT_NODE) ||
 584 #endif
 585                     (node->type == XML_NAMESPACE_DECL))
 586                     goto rollback;
 587                 node = node->parent;
 588                 if ((step->op != XSLT_OP_ELEM) && step->op != XSLT_OP_ALL) {
 589                     xsltPatPushState(&states, i, node);
 590                     continue;
 591                 }
 592                 i++;
 593                 if (step->value == NULL) {
 594                     xsltPatPushState(&states, i - 1, node);
 595                     continue;
 596                 }
 597                 while (node != NULL) {
 598                     if (node == NULL)
 599                         goto rollback;
 600                     if ((node->type == XML_ELEMENT_NODE) &&
 601                         (step->value[0] == node->name[0]) &&
 602                         (xmlStrEqual(step->value, node->name))) {
 603                         /* Namespace test */
 604                         if (node->ns == NULL) {
 605                             if (step->value2 == NULL)
 606                                 break;
 607                         } else if (node->ns->href != NULL) {
 608                             if ((step->value2 != NULL) &&
 609                                 (xmlStrEqual(step->value2, node->ns->href)))
 610                                 break;
 611                         }
 612                     }
 613                     node = node->parent;
 614                 }
 615                 if (node == NULL)
 616                     goto rollback;
 617                 xsltPatPushState(&states, i - 1, node);
 618                 continue;
 619             case XSLT_OP_ID: {
 620                 /* TODO Handle IDs decently, must be done differently */
 621                 xmlAttrPtr id;
 622
 623                 if (node->type != XML_ELEMENT_NODE)
 624                     goto rollback;
 625
 626                 id = xmlGetID(node->doc, step->value);
 627                 if ((id == NULL) || (id->parent != node))
 628                     goto rollback;
 629                 break;
 630             }
 631             case XSLT_OP_KEY: {
 632                 xmlNodeSetPtr list;
 633                 int indx;
 634
 635                 list = xsltGetKey(ctxt, step->value,
 636                                   step->value3, step->value2);
 637                 if (list == NULL)
 638                     goto rollback;
 639                 for (indx = 0;indx < list->nodeNr;indx++)
 640                     if (list->nodeTab[indx] == node)
 641                         break;
 642                 if (indx >= list->nodeNr)
 643                     goto rollback;
 644                 break;
 645             }
 646             case XSLT_OP_NS:
 647                 if (node->type != XML_ELEMENT_NODE)
 648                     goto rollback;
 649                 if (node->ns == NULL) {
 650                     if (step->value != NULL)
 651                         goto rollback;
 652                 } else if (node->ns->href != NULL) {
 653                     if (step->value == NULL)
 654                         goto rollback;
 655                     if (!xmlStrEqual(step->value, node->ns->href))
 656                         goto rollback;
 657                 }
 658                 break;
 659             case XSLT_OP_ALL:
 660                 if (node->type != XML_ELEMENT_NODE)
 661                     goto rollback;
 662                 break;
 663             case XSLT_OP_PREDICATE: {
 664                 xmlNodePtr oldNode;
 665                 xmlDocPtr doc;
 666                 int oldCS, oldCP;
 667                 int pos = 0, len = 0;
 668                 int isRVT;
 669
 670                 doc = node->doc;
 671                 if ((doc != NULL) &&
 672                     (doc->name != NULL) &&
 673                     (doc->name[0] == ' ') &&
 674                     (xmlStrEqual(BAD_CAST doc->name,
 675                                  BAD_CAST " fake node libxslt")))
 676                     isRVT = 1;
 677                 else
 678                     isRVT = 0;
 679                 /*
 680                  * The simple existing predicate code cannot handle
 681                  * properly cascaded predicates. If in this situation
 682                  * compute directly the full node list once and check
 683                  * if the node is in the result list.
 684                  */
 685                 if (comp->steps[i + 1].op == XSLT_OP_PREDICATE) {
 686                     xmlDocPtr prevdoc;
 687                     xmlXPathObjectPtr list;
 688                     int ix, j;
 689                     int nocache = 0;
 690
 691                     prevdoc = (xmlDocPtr)
 692                         XSLT_RUNTIME_EXTRA(ctxt, sel->previousExtra, ptr);
 693                     ix = XSLT_RUNTIME_EXTRA(ctxt, sel->indexExtra, ival);
 694                     list = (xmlXPathObjectPtr)
 695                         XSLT_RUNTIME_EXTRA_LST(ctxt, sel->lenExtra);
 696
 697                     if ((list == NULL) || (prevdoc != doc)) {
 698                         xmlChar *query;
 699                         xmlXPathObjectPtr newlist;
 700                         xmlNodePtr parent = node->parent;
 701                         xmlDocPtr olddoc;
 702                         xmlNodePtr oldnode;
 703
 704                         if (comp->pattern[0] == '/')
 705                             query = xmlStrdup(comp->pattern);
 706                         else {
 707                             query = xmlStrdup((const xmlChar *)"//");
 708                             query = xmlStrcat(query, comp->pattern);
 709                         }
 710                         oldnode = ctxt->xpathCtxt->node;
 711                         olddoc = ctxt->xpathCtxt->doc;
 712                         ctxt->xpathCtxt->node = node;
 713                         ctxt->xpathCtxt->doc = doc;
 714                         newlist = xmlXPathEval(query, ctxt->xpathCtxt);
 715                         ctxt->xpathCtxt->node = oldnode;
 716                         ctxt->xpathCtxt->doc = olddoc;
 717                         xmlFree(query);
 718                         if (newlist == NULL)
 719                             return(-1);
 720                         if (newlist->type != XPATH_NODESET) {
 721                             xmlXPathFreeObject(newlist);
 722                             return(-1);
 723                         }
 724                         ix = 0;
 725
 726                         if ((parent == NULL) || (node->doc == NULL) || isRVT)
 727                             nocache = 1;
 728
 729                         if (nocache == 0) {
 730                             if (list != NULL)
 731                                 xmlXPathFreeObject(list);
 732                             list = newlist;
 733
 734                             XSLT_RUNTIME_EXTRA_LST(ctxt, sel->lenExtra) =
 735                                 (void *) list;
 736                             XSLT_RUNTIME_EXTRA(ctxt, sel->previousExtra, ptr) =
 737                                 (void *) doc;
 738                             XSLT_RUNTIME_EXTRA(ctxt, sel->indexExtra, ival) =
 739                                 0;
 740                             XSLT_RUNTIME_EXTRA_FREE(ctxt, sel->lenExtra) =
 741                                 (xmlFreeFunc) xmlXPathFreeObject;
 742                         } else
 743                             list = newlist;
 744                     }
 745                     if ((list->nodesetval == NULL) ||
 746                         (list->nodesetval->nodeNr <= 0)) {
 747                         if (nocache == 1)
 748                             xmlXPathFreeObject(list);
 749                         goto rollback;
 750                     }
 751                     /* TODO: store the index and use it for the scan */
 752                     if (ix == 0) {
 753                         for (j = 0;j < list->nodesetval->nodeNr;j++) {
 754                             if (list->nodesetval->nodeTab[j] == node) {
 755                                 if (nocache == 1)
 756                                     xmlXPathFreeObject(list);
 757                                 goto found;
 758                             }
 759                         }
 760                     } else {
 761                     }
 762                     if (nocache == 1)
 763                         xmlXPathFreeObject(list);
 764                     goto rollback;
 765                 }
 766                 /*
 767                  * Depending on the last selection, one may need to
 768                  * recompute contextSize and proximityPosition.
 769                  *
 770                  * TODO: make this thread safe !
 771                  */
 772                 oldCS = ctxt->xpathCtxt->contextSize;
 773                 oldCP = ctxt->xpathCtxt->proximityPosition;
 774                 if ((sel != NULL) &&
 775                     (sel->op == XSLT_OP_ELEM) &&
 776                     (sel->value != NULL) &&
 777                     (node->type == XML_ELEMENT_NODE) &&
 778                     (node->parent != NULL)) {
 779                     xmlNodePtr previous;
 780                     int ix, nocache = 0;
 781
 782                     previous = (xmlNodePtr)
 783                         XSLT_RUNTIME_EXTRA(ctxt, sel->previousExtra, ptr);
 784                     ix = XSLT_RUNTIME_EXTRA(ctxt, sel->indexExtra, ival);
 785                     if ((previous != NULL) &&
 786                         (previous->parent == node->parent)) {
 787                         /*
 788                          * just walk back to adjust the index
 789                          */
 790                         int indx = 0;
 791                         xmlNodePtr sibling = node;
 792
 793                         while (sibling != NULL) {
 794                             if (sibling == previous)
 795                                 break;
 796                             if ((previous->type == XML_ELEMENT_NODE) &&
 797                                 (previous->name != NULL) &&
 798                                 (sibling->name != NULL) &&
 799                                 (previous->name[0] == sibling->name[0]) &&
 800                                 (xmlStrEqual(previous->name, sibling->name))) {
 801                                 if ((sel->value2 == NULL) ||
 802                                     ((sibling->ns != NULL) &&
 803                                      (xmlStrEqual(sel->value2,
 804                                                   sibling->ns->href))))
 805                                     indx++;
 806                             }
 807                             sibling = sibling->prev;
 808                         }
 809                         if (sibling == NULL) {
 810                             /* hum going backward in document order ... */
 811                             indx = 0;
 812                             sibling = node;
 813                             while (sibling != NULL) {
 814                                 if (sibling == previous)
 815                                     break;
 816                                 if ((sel->value2 == NULL) ||
 817                                     ((sibling->ns != NULL) &&
 818                                      (xmlStrEqual(sel->value2,
 819                                                   sibling->ns->href))))
 820                                     indx--;
 821                                 sibling = sibling->next;
 822                             }
 823                         }
 824                         if (sibling != NULL) {
 825                             pos = ix + indx;
 826                             /*
 827                              * If the node is in a Value Tree we need to
 828                              * save len, but cannot cache the node!
 829                              * (bugs 153137 and 158840)
 830                              */
 831                             if (node->doc != NULL) {
 832                                 len = XSLT_RUNTIME_EXTRA(ctxt,
 833                                         sel->lenExtra, ival);
 834                                 if (!isRVT) {
 835                                     XSLT_RUNTIME_EXTRA(ctxt,
 836                                         sel->previousExtra, ptr) = node;
 837                                     XSLT_RUNTIME_EXTRA(ctxt,
 838                                         sel->indexExtra, ival) = pos;
 839                                 }
 840                             }
 841                             ix = pos;
 842                         } else
 843                             pos = 0;
 844                     } else {
 845                         /*
 846                          * recompute the index
 847                          */
 848                         xmlNodePtr siblings = node->parent->children;
 849                         xmlNodePtr parent = node->parent;
 850
 851                         while (siblings != NULL) {
 852                             if (siblings->type == XML_ELEMENT_NODE) {
 853                                 if (siblings == node) {
 854                                     len++;
 855                                     pos = len;
 856                                 } else if ((node->name != NULL) &&
 857                                            (siblings->name != NULL) &&
 858                                     (node->name[0] == siblings->name[0]) &&
 859                                     (xmlStrEqual(node->name, siblings->name))) {
 860                                     if ((sel->value2 == NULL) ||
 861                                         ((siblings->ns != NULL) &&
 862                                          (xmlStrEqual(sel->value2,
 863                                                       siblings->ns->href))))
 864                                         len++;
 865                                 }
 866                             }
 867                             siblings = siblings->next;
 868                         }
 869                         if ((parent == NULL) || (node->doc == NULL))
 870                             nocache = 1;
 871                         else {
 872                             while (parent->parent != NULL)
 873                                 parent = parent->parent;
 874                             if (((parent->type != XML_DOCUMENT_NODE) &&
 875                                  (parent->type != XML_HTML_DOCUMENT_NODE)) ||
 876                                  (parent != (xmlNodePtr) node->doc))
 877                                 nocache = 1;
 878                         }
 879                     }
 880                     if (pos != 0) {
 881                         ctxt->xpathCtxt->contextSize = len;
 882                         ctxt->xpathCtxt->proximityPosition = pos;
 883                         /*
 884                          * If the node is in a Value Tree we cannot
 885                          * cache it !
 886                          */
 887                         if ((!isRVT) && (node->doc != NULL) &&
 888                             (nocache == 0)) {
 889                             XSLT_RUNTIME_EXTRA(ctxt, sel->previousExtra, ptr) =
 890                                 node;
 891                             XSLT_RUNTIME_EXTRA(ctxt, sel->indexExtra, ival) =
 892                                 pos;
 893                             XSLT_RUNTIME_EXTRA(ctxt, sel->lenExtra, ival) =
 894                                 len;
 895                         }
 896                     }
 897                 } else if ((sel != NULL) && (sel->op == XSLT_OP_ALL) &&
 898                            (node->type == XML_ELEMENT_NODE)) {
 899                     xmlNodePtr previous;
 900                     int ix, nocache = 0;
 901
 902                     previous = (xmlNodePtr)
 903                         XSLT_RUNTIME_EXTRA(ctxt, sel->previousExtra, ptr);
 904                     ix = XSLT_RUNTIME_EXTRA(ctxt, sel->indexExtra, ival);
 905                     if ((previous != NULL) &&
 906                         (previous->parent == node->parent)) {
 907                         /*
 908                          * just walk back to adjust the index
 909                          */
 910                         int indx = 0;
 911                         xmlNodePtr sibling = node;
 912
 913                         while (sibling != NULL) {
 914                             if (sibling == previous)
 915                                 break;
 916                             if (sibling->type == XML_ELEMENT_NODE)
 917                                 indx++;
 918                             sibling = sibling->prev;
 919                         }
 920                         if (sibling == NULL) {
 921                             /* hum going backward in document order ... */
 922                             indx = 0;
 923                             sibling = node;
 924                             while (sibling != NULL) {
 925                                 if (sibling == previous)
 926                                     break;
 927                                 if (sibling->type == XML_ELEMENT_NODE)
 928                                     indx--;
 929                                 sibling = sibling->next;
 930                             }
 931                         }
 932                         if (sibling != NULL) {
 933                             pos = ix + indx;
 934                             /*
 935                              * If the node is in a Value Tree we cannot
 936                              * cache it !
 937                              */
 938                             if ((node->doc != NULL) && !isRVT) {
 939                                 len = XSLT_RUNTIME_EXTRA(ctxt,
 940                                         sel->lenExtra, ival);
 941                                 XSLT_RUNTIME_EXTRA(ctxt,
 942                                         sel->previousExtra, ptr) = node;
 943                                 XSLT_RUNTIME_EXTRA(ctxt,
 944                                         sel->indexExtra, ival) = pos;
 945                             }
 946                         } else
 947                             pos = 0;
 948                     } else {
 949                         /*
 950                          * recompute the index
 951                          */
 952                         xmlNodePtr siblings = node->parent->children;
 953                         xmlNodePtr parent = node->parent;
 954
 955                         while (siblings != NULL) {
 956                             if (siblings->type == XML_ELEMENT_NODE) {
 957                                 len++;
 958                                 if (siblings == node) {
 959                                     pos = len;
 960                                 }
 961                             }
 962                             siblings = siblings->next;
 963                         }
 964                         if ((parent == NULL) || (node->doc == NULL))
 965                             nocache = 1;
 966                         else {
 967                             while (parent->parent != NULL)
 968                                 parent = parent->parent;
 969                             if (((parent->type != XML_DOCUMENT_NODE) &&
 970                                  (parent->type != XML_HTML_DOCUMENT_NODE)) ||
 971                                  (parent != (xmlNodePtr) node->doc))
 972                                 nocache = 1;
 973                         }
 974                     }
 975                     if (pos != 0) {
 976                         ctxt->xpathCtxt->contextSize = len;
 977                         ctxt->xpathCtxt->proximityPosition = pos;
 978                         /*
 979                          * If the node is in a Value Tree we cannot
 980                          * cache it !
 981                          */
 982                         if ((node->doc != NULL) && (nocache == 0) && !isRVT) {
 983                             XSLT_RUNTIME_EXTRA(ctxt, sel->previousExtra, ptr) =
 984                                 node;
 985                             XSLT_RUNTIME_EXTRA(ctxt, sel->indexExtra, ival) =
 986                                 pos;
 987                             XSLT_RUNTIME_EXTRA(ctxt, sel->lenExtra, ival) =
 988                                 len;
 989                         }
 990                     }
 991                 }
 992                 oldNode = ctxt->node;
 993                 ctxt->node = node;
 994
 995                 if (step->value == NULL)
 996                     goto wrong_index;
 997                 if (step->comp == NULL)
 998                     goto wrong_index;
 999
1000                 if (!xsltEvalXPathPredicate(ctxt, step->comp, comp->nsList,
1001                                             comp->nsNr))
1002                     goto wrong_index;
1003
1004                 if (pos != 0) {
1005                     ctxt->xpathCtxt->contextSize = oldCS;
1006                     ctxt->xpathCtxt->proximityPosition = oldCP;
1007                 }
1008                 ctxt->node = oldNode;
1009                 break;
1010 wrong_index:
1011                 if (pos != 0) {
1012                     ctxt->xpathCtxt->contextSize = oldCS;
1013                     ctxt->xpathCtxt->proximityPosition = oldCP;
1014                 }
1015                 ctxt->node = oldNode;
1016                 goto rollback;
1017             }
1018             case XSLT_OP_PI:
1019                 if (node->type != XML_PI_NODE)
1020                     goto rollback;
1021                 if (step->value != NULL) {
1022                     if (!xmlStrEqual(step->value, node->name))
1023                         goto rollback;
1024                 }
1025                 break;
1026             case XSLT_OP_COMMENT:
1027                 if (node->type != XML_COMMENT_NODE)
1028                     goto rollback;
1029                 break;
1030             case XSLT_OP_TEXT:
1031                 if ((node->type != XML_TEXT_NODE) &&
1032                     (node->type != XML_CDATA_SECTION_NODE))
1033                     goto rollback;
1034                 break;
1035             case XSLT_OP_NODE:
1036                 switch (node->type) {
1037                     case XML_ELEMENT_NODE:
1038                     case XML_CDATA_SECTION_NODE:
1039                     case XML_PI_NODE:
1040                     case XML_COMMENT_NODE:
1041                     case XML_TEXT_NODE:
1042                         break;
1043                     default:
1044                         goto rollback;
1045                 }
1046                 break;
1047         }
1048     }
1049 found:
1050     if (states.states != NULL) {
1051         /* Free the rollback states */
1052         xmlFree(states.states);
1053     }
1054     return(1);
1055 rollback:
1056     /* got an error try to rollback */
1057     if (states.states == NULL)
1058         return(0);
1059     if (states.nbstates <= 0) {
1060         xmlFree(states.states);
1061         return(0);
1062     }
1063     states.nbstates--;
1064     i = states.states[states.nbstates].step;
1065     node = states.states[states.nbstates].node;
1066 #if 0
1067     fprintf(stderr, "Pop: %d, %s\n", i, node->name);
1068 #endif
1069     goto restart;
1070 }
1071
1072 /**
1073  * xsltTestCompMatchList:
1074  * @ctxt:  a XSLT process context
1075  * @node: a node
1076  * @comp: the precompiled pattern list
1077  *
1078  * Test whether the node matches one of the patterns in the list
1079  *
1080  * Returns 1 if it matches, 0 if it doesn't and -1 in case of failure
1081  */
1082 int
1083 xsltTestCompMatchList(xsltTransformContextPtr ctxt, xmlNodePtr node,
1084                       xsltCompMatchPtr comp) {
1085     int ret;
1086
1087     if ((ctxt == NULL) || (node == NULL))
1088         return(-1);
1089     while (comp != NULL) {
1090         ret = xsltTestCompMatch(ctxt, comp, node, NULL, NULL);
1091         if (ret == 1)
1092             return(1);
1093         comp = comp->next;
1094     }
1095     return(0);
1096 }
1097
1098 /************************************************************************
1099  *                                                                      *
1100  *                      Dedicated parser for templates                  *
1101  *                                                                      *
1102  ************************************************************************/
1103
1104 #define CUR (*ctxt->cur)
1105 #define SKIP(val) ctxt->cur += (val)
1106 #define NXT(val) ctxt->cur[(val)]
1107 #define CUR_PTR ctxt->cur
1108
1109 #define SKIP_BLANKS                                                     \
1110     while (IS_BLANK_CH(CUR)) NEXT
1111
1112 #define CURRENT (*ctxt->cur)
1113 #define NEXT ((*ctxt->cur) ?  ctxt->cur++: ctxt->cur)
1114
1115
1116 #define PUSH(op, val, val2)                                             \
1117     if (xsltCompMatchAdd(ctxt, ctxt->comp, (op), (val), (val2))) goto error;
1118
1119 #define SWAP()                                          \
1120     xsltSwapTopCompMatch(ctxt->comp);
1121
1122 #define XSLT_ERROR(X)                                                   \
1123     { xsltError(ctxt, __FILE__, __LINE__, X);                   \
1124       ctxt->error = (X); return; }
1125
1126 #define XSLT_ERROR0(X)                                                  \
1127     { xsltError(ctxt, __FILE__, __LINE__, X);                   \
1128       ctxt->error = (X); return(0); }
1129
1130 /**
1131  * xsltScanLiteral:
1132  * @ctxt:  the XPath Parser context
1133  *
1134  * Parse an XPath Litteral:
1135  *
1136  * [29] Literal ::= '"' [^"]* '"'
1137  *                | "'" [^']* "'"
1138  *
1139  * Returns the Literal parsed or NULL
1140  */
1141
1142 static xmlChar *
1143 xsltScanLiteral(xsltParserContextPtr ctxt) {
1144     const xmlChar *q, *cur;
1145     xmlChar *ret = NULL;
1146     int val, len;
1147
1148     SKIP_BLANKS;
1149     if (CUR == '"') {
1150         NEXT;
1151         cur = q = CUR_PTR;
1152         val = xmlStringCurrentChar(NULL, cur, &len);
1153         while ((IS_CHAR(val)) && (val != '"')) {
1154             cur += len;
1155             val = xmlStringCurrentChar(NULL, cur, &len);
1156         }
1157         if (!IS_CHAR(val)) {
1158             ctxt->error = 1;
1159             return(NULL);
1160         } else {
1161             ret = xmlStrndup(q, cur - q);
1162         }
1163         cur += len;
1164         CUR_PTR = cur;
1165     } else if (CUR == '\'') {
1166         NEXT;
1167         cur = q = CUR_PTR;
1168         val = xmlStringCurrentChar(NULL, cur, &len);
1169         while ((IS_CHAR(val)) && (val != '\'')) {
1170             cur += len;
1171             val = xmlStringCurrentChar(NULL, cur, &len);
1172         }
1173         if (!IS_CHAR(val)) {
1174             ctxt->error = 1;
1175             return(NULL);
1176         } else {
1177             ret = xmlStrndup(q, cur - q);
1178         }
1179         cur += len;
1180         CUR_PTR = cur;
1181     } else {
1182         /* XP_ERROR(XPATH_START_LITERAL_ERROR); */
1183         ctxt->error = 1;
1184         return(NULL);
1185     }
1186     return(ret);
1187 }
1188
1189 /**
1190  * xsltScanName:
1191  * @ctxt:  the XPath Parser context
1192  *
1193  * [4] NameChar ::= Letter | Digit | '.' | '-' | '_' |
1194  *                  CombiningChar | Extender
1195  *
1196  * [5] Name ::= (Letter | '_' | ':') (NameChar)*
1197  *
1198  * [6] Names ::= Name (S Name)*
1199  *
1200  * Returns the Name parsed or NULL
1201  */
1202
1203 static xmlChar *
1204 xsltScanName(xsltParserContextPtr ctxt) {
1205     const xmlChar *q, *cur;
1206     xmlChar *ret = NULL;
1207     int val, len;
1208
1209     SKIP_BLANKS;
1210
1211     cur = q = CUR_PTR;
1212     val = xmlStringCurrentChar(NULL, cur, &len);
1213     if (!IS_LETTER(val) && (val != '_') && (val != ':'))
1214         return(NULL);
1215
1216     while ((IS_LETTER(val)) || (IS_DIGIT(val)) ||
1217            (val == '.') || (val == '-') ||
1218            (val == '_') ||
1219            (IS_COMBINING(val)) ||
1220            (IS_EXTENDER(val))) {
1221         cur += len;
1222         val = xmlStringCurrentChar(NULL, cur, &len);
1223     }
1224     ret = xmlStrndup(q, cur - q);
1225     CUR_PTR = cur;
1226     return(ret);
1227 }
1228
1229 /**
1230  * xsltScanNCName:
1231  * @ctxt:  the XPath Parser context
1232  *
1233  * Parses a non qualified name
1234  *
1235  * Returns the Name parsed or NULL
1236  */
1237
1238 static xmlChar *
1239 xsltScanNCName(xsltParserContextPtr ctxt) {
1240     const xmlChar *q, *cur;
1241     xmlChar *ret = NULL;
1242     int val, len;
1243
1244     SKIP_BLANKS;
1245
1246     cur = q = CUR_PTR;
1247     val = xmlStringCurrentChar(NULL, cur, &len);
1248     if (!IS_LETTER(val) && (val != '_'))
1249         return(NULL);
1250
1251     while ((IS_LETTER(val)) || (IS_DIGIT(val)) ||
1252            (val == '.') || (val == '-') ||
1253            (val == '_') ||
1254            (IS_COMBINING(val)) ||
1255            (IS_EXTENDER(val))) {
1256         cur += len;
1257         val = xmlStringCurrentChar(NULL, cur, &len);
1258     }
1259     ret = xmlStrndup(q, cur - q);
1260     CUR_PTR = cur;
1261     return(ret);
1262 }
1263
1264 /**
1265  * xsltScanQName:
1266  * @ctxt:  the XPath Parser context
1267  * @prefix:  the place to store the prefix
1268  *
1269  * Parse a qualified name
1270  *
1271  * Returns the Name parsed or NULL
1272  */
1273
1274 static xmlChar *
1275 xsltScanQName(xsltParserContextPtr ctxt, xmlChar **prefix) {
1276     xmlChar *ret = NULL;
1277
1278     *prefix = NULL;
1279     ret = xsltScanNCName(ctxt);
1280     if (CUR == ':') {
1281         *prefix = ret;
1282         NEXT;
1283         ret = xsltScanNCName(ctxt);
1284     }
1285     return(ret);
1286 }
1287
1288 /*
1289  * xsltCompileIdKeyPattern:
1290  * @ctxt:  the compilation context
1291  * @name:  a preparsed name
1292  * @aid:  whether id/key are allowed there
1293  *
1294  * Compile the XSLT LocationIdKeyPattern
1295  * [3] IdKeyPattern ::= 'id' '(' Literal ')'
1296  *                    | 'key' '(' Literal ',' Literal ')'
1297  *
1298  * also handle NodeType and PI from:
1299  *
1300  * [7]  NodeTest ::= NameTest
1301  *                 | NodeType '(' ')'
1302  *                 | 'processing-instruction' '(' Literal ')'
1303  */
1304 static void
1305 xsltCompileIdKeyPattern(xsltParserContextPtr ctxt, xmlChar *name, int aid) {
1306     xmlChar *lit = NULL;
1307     xmlChar *lit2 = NULL;
1308
1309     if (CUR != '(') {
1310         xsltTransformError(NULL, NULL, NULL,
1311                 "xsltCompileIdKeyPattern : ( expected\n");
1312         ctxt->error = 1;
1313         return;
1314     }
1315     if ((aid) && (xmlStrEqual(name, (const xmlChar *)"id"))) {
1316         NEXT;
1317         SKIP_BLANKS;
1318         lit = xsltScanLiteral(ctxt);
1319         if (ctxt->error)
1320             return;
1321         SKIP_BLANKS;
1322         if (CUR != ')') {
1323             xsltTransformError(NULL, NULL, NULL,
1324                     "xsltCompileIdKeyPattern : ) expected\n");
1325             ctxt->error = 1;
1326             return;
1327         }
1328         NEXT;
1329         PUSH(XSLT_OP_ID, lit, NULL);
1330     } else if ((aid) && (xmlStrEqual(name, (const xmlChar *)"key"))) {
1331         NEXT;
1332         SKIP_BLANKS;
1333         lit = xsltScanLiteral(ctxt);
1334         if (ctxt->error)
1335             return;
1336         SKIP_BLANKS;
1337         if (CUR != ',') {
1338             xsltTransformError(NULL, NULL, NULL,
1339                     "xsltCompileIdKeyPattern : , expected\n");
1340             ctxt->error = 1;
1341             return;
1342         }
1343         NEXT;
1344         SKIP_BLANKS;
1345         lit2 = xsltScanLiteral(ctxt);
1346         if (ctxt->error)
1347             return;
1348         SKIP_BLANKS;
1349         if (CUR != ')') {
1350             xsltTransformError(NULL, NULL, NULL,
1351                     "xsltCompileIdKeyPattern : ) expected\n");
1352             ctxt->error = 1;
1353             return;
1354         }
1355         NEXT;
1356         /* TODO: support namespace in keys */
1357         PUSH(XSLT_OP_KEY, lit, lit2);
1358     } else if (xmlStrEqual(name, (const xmlChar *)"processing-instruction")) {
1359         NEXT;
1360         SKIP_BLANKS;
1361         if (CUR != ')') {
1362             lit = xsltScanLiteral(ctxt);
1363             if (ctxt->error)
1364                 return;
1365             SKIP_BLANKS;
1366             if (CUR != ')') {
1367                 xsltTransformError(NULL, NULL, NULL,
1368                         "xsltCompileIdKeyPattern : ) expected\n");
1369                 ctxt->error = 1;
1370                 return;
1371             }
1372         }
1373         NEXT;
1374         PUSH(XSLT_OP_PI, lit, NULL);
1375     } else if (xmlStrEqual(name, (const xmlChar *)"text")) {
1376         NEXT;
1377         SKIP_BLANKS;
1378         if (CUR != ')') {
1379             xsltTransformError(NULL, NULL, NULL,
1380                     "xsltCompileIdKeyPattern : ) expected\n");
1381             ctxt->error = 1;
1382             return;
1383         }
1384         NEXT;
1385         PUSH(XSLT_OP_TEXT, NULL, NULL);
1386     } else if (xmlStrEqual(name, (const xmlChar *)"comment")) {
1387         NEXT;
1388         SKIP_BLANKS;
1389         if (CUR != ')') {
1390             xsltTransformError(NULL, NULL, NULL,
1391                     "xsltCompileIdKeyPattern : ) expected\n");
1392             ctxt->error = 1;
1393             return;
1394         }
1395         NEXT;
1396         PUSH(XSLT_OP_COMMENT, NULL, NULL);
1397     } else if (xmlStrEqual(name, (const xmlChar *)"node")) {
1398         NEXT;
1399         SKIP_BLANKS;
1400         if (CUR != ')') {
1401             xsltTransformError(NULL, NULL, NULL,
1402                     "xsltCompileIdKeyPattern : ) expected\n");
1403             ctxt->error = 1;
1404             return;
1405         }
1406         NEXT;
1407         PUSH(XSLT_OP_NODE, NULL, NULL);
1408     } else if (aid) {
1409         xsltTransformError(NULL, NULL, NULL,
1410             "xsltCompileIdKeyPattern : expecting 'key' or 'id' or node type\n");
1411         ctxt->error = 1;
1412         return;
1413     } else {
1414         xsltTransformError(NULL, NULL, NULL,
1415             "xsltCompileIdKeyPattern : node type\n");
1416         ctxt->error = 1;
1417         return;
1418     }
1419 error:
1420     if (name != NULL)
1421         xmlFree(name);
1422 }
1423
1424 /**
1425  * xsltCompileStepPattern:
1426  * @ctxt:  the compilation context
1427  * @token:  a posible precompiled name
1428  *
1429  * Compile the XSLT StepPattern and generates a precompiled
1430  * form suitable for fast matching.
1431  *
1432  * [5] StepPattern ::= ChildOrAttributeAxisSpecifier NodeTest Predicate*
1433  * [6] ChildOrAttributeAxisSpecifier ::= AbbreviatedAxisSpecifier
1434  *                                     | ('child' | 'attribute') '::'
1435  * from XPath
1436  * [7]  NodeTest ::= NameTest
1437  *                 | NodeType '(' ')'
1438  *                 | 'processing-instruction' '(' Literal ')'
1439  * [8] Predicate ::= '[' PredicateExpr ']'
1440  * [9] PredicateExpr ::= Expr
1441  * [13] AbbreviatedAxisSpecifier ::= '@'?
1442  * [37] NameTest ::= '*' | NCName ':' '*' | QName
1443  */
1444
1445 static void
1446 xsltCompileStepPattern(xsltParserContextPtr ctxt, xmlChar *token) {
1447     xmlChar *name = NULL;
1448     const xmlChar *URI = NULL;
1449     xmlChar *URL = NULL;
1450     int level;
1451
1452     SKIP_BLANKS;
1453     if ((token == NULL) && (CUR == '@')) {
1454         xmlChar *prefix = NULL;
1455
1456         NEXT;
1457         if (CUR == '*') {
1458             NEXT;
1459             PUSH(XSLT_OP_ATTR, NULL, NULL);
1460             goto parse_predicate;
1461         }
1462         token = xsltScanQName(ctxt, &prefix);
1463         if (prefix != NULL) {
1464             xmlNsPtr ns;
1465
1466             ns = xmlSearchNs(ctxt->doc, ctxt->elem, prefix);
1467             if (ns == NULL) {
1468                 xsltTransformError(NULL, NULL, NULL,
1469                 "xsltCompileStepPattern : no namespace bound to prefix %s\n",
1470                                  prefix);
1471             } else {
1472                 URL = xmlStrdup(ns->href);
1473             }
1474             xmlFree(prefix);
1475         }
1476         if (token == NULL) {
1477             if (CUR == '*') {
1478                 NEXT;
1479                 PUSH(XSLT_OP_ATTR, NULL, URL);
1480                 return;
1481             }
1482             xsltTransformError(NULL, NULL, NULL,
1483                     "xsltCompileStepPattern : Name expected\n");
1484             ctxt->error = 1;
1485             goto error;
1486         }
1487         PUSH(XSLT_OP_ATTR, token, URL);
1488         goto parse_predicate;
1489     }
1490     if (token == NULL)
1491         token = xsltScanName(ctxt);
1492     if (token == NULL) {
1493         if (CUR == '*') {
1494             NEXT;
1495             PUSH(XSLT_OP_ALL, token, NULL);
1496             goto parse_predicate;
1497         } else {
1498             xsltTransformError(NULL, NULL, NULL,
1499                     "xsltCompileStepPattern : Name expected\n");
1500             ctxt->error = 1;
1501             goto error;
1502         }
1503     }
1504
1505
1506     SKIP_BLANKS;
1507     if (CUR == '(') {
1508         xsltCompileIdKeyPattern(ctxt, token, 0);
1509         if (ctxt->error)
1510             goto error;
1511     } else if (CUR == ':') {
1512         NEXT;
1513         if (CUR != ':') {
1514             xmlChar *prefix = token;
1515             xmlNsPtr ns;
1516
1517             /*
1518              * This is a namespace match
1519              */
1520             token = xsltScanName(ctxt);
1521             ns = xmlSearchNs(ctxt->doc, ctxt->elem, prefix);
1522             if (ns == NULL) {
1523                 xsltTransformError(NULL, NULL, NULL,
1524             "xsltCompileStepPattern : no namespace bound to prefix %s\n",
1525                                  prefix);
1526                 ctxt->error = 1;
1527                 goto error;
1528             } else {
1529                 URL = xmlStrdup(ns->href);
1530             }
1531             xmlFree(prefix);
1532             if (token == NULL) {
1533                 if (CUR == '*') {
1534                     NEXT;
1535                     PUSH(XSLT_OP_NS, URL, NULL);
1536                 } else {
1537                     xsltTransformError(NULL, NULL, NULL,
1538                             "xsltCompileStepPattern : Name expected\n");
1539                     ctxt->error = 1;
1540                     goto error;
1541                 }
1542             } else {
1543                 PUSH(XSLT_OP_ELEM, token, URL);
1544             }
1545         } else {
1546             NEXT;
1547             if (xmlStrEqual(token, (const xmlChar *) "child")) {
1548                 xmlFree(token);
1549                 token = xsltScanName(ctxt);
1550                 if (token == NULL) {
1551                     if (CUR == '*') {
1552                         NEXT;
1553                         PUSH(XSLT_OP_ALL, token, NULL);
1554                         goto parse_predicate;
1555                     } else {
1556                         xsltTransformError(NULL, NULL, NULL,
1557                             "xsltCompileStepPattern : QName expected\n");
1558                         ctxt->error = 1;
1559                         goto error;
1560                     }
1561                 }
1562                 URI = xsltGetQNameURI(ctxt->elem, &token);
1563                 if (token == NULL) {
1564                     ctxt->error = 1;
1565                     goto error;
1566                 } else {
1567                     name = xmlStrdup(token);
1568                     if (URI != NULL)
1569                         URL = xmlStrdup(URI);
1570                 }
1571                 PUSH(XSLT_OP_CHILD, name, URL);
1572             } else if (xmlStrEqual(token, (const xmlChar *) "attribute")) {
1573                 xmlFree(token);
1574                 token = xsltScanName(ctxt);
1575                 if (token == NULL) {
1576                     xsltTransformError(NULL, NULL, NULL,
1577                             "xsltCompileStepPattern : QName expected\n");
1578                     ctxt->error = 1;
1579                     goto error;
1580                 }
1581                 URI = xsltGetQNameURI(ctxt->elem, &token);
1582                 if (token == NULL) {
1583                     ctxt->error = 1;
1584                     goto error;
1585                 } else {
1586                     name = xmlStrdup(token);
1587                     if (URI != NULL)
1588                         URL = xmlStrdup(URI);
1589                 }
1590                 PUSH(XSLT_OP_ATTR, name, URL);
1591             } else {
1592                 xsltTransformError(NULL, NULL, NULL,
1593                     "xsltCompileStepPattern : 'child' or 'attribute' expected\n");
1594                 ctxt->error = 1;
1595                 goto error;
1596             }
1597             xmlFree(token);
1598         }
1599     } else if (CUR == '*') {
1600         NEXT;
1601         PUSH(XSLT_OP_ALL, token, NULL);
1602     } else {
1603         URI = xsltGetQNameURI(ctxt->elem, &token);
1604         if (token == NULL) {
1605             ctxt->error = 1;
1606             goto error;
1607         }
1608         if (URI != NULL)
1609             URL = xmlStrdup(URI);
1610         PUSH(XSLT_OP_ELEM, token, URL);
1611     }
1612 parse_predicate:
1613     SKIP_BLANKS;
1614     level = 0;
1615     while (CUR == '[') {
1616         const xmlChar *q;
1617         xmlChar *ret = NULL;
1618
1619         level++;
1620         NEXT;
1621         q = CUR_PTR;
1622         while (CUR != 0) {
1623             /* Skip over nested predicates */
1624             if (CUR == '[')
1625                 level++;
1626             else if (CUR == ']') {
1627                 level--;
1628                 if (level == 0)
1629                     break;
1630             } else if (CUR == '"') {
1631                 NEXT;
1632                 while ((CUR != 0) && (CUR != '"'))
1633                     NEXT;
1634             } else if (CUR == '\'') {
1635                 NEXT;
1636                 while ((CUR != 0) && (CUR != '\''))
1637                     NEXT;
1638             }
1639             NEXT;
1640         }
1641         if (CUR == 0) {
1642             xsltTransformError(NULL, NULL, NULL,
1643                     "xsltCompileStepPattern : ']' expected\n");
1644             ctxt->error = 1;
1645             return;
1646         }
1647         ret = xmlStrndup(q, CUR_PTR - q);
1648         PUSH(XSLT_OP_PREDICATE, ret, NULL);
1649         /* push the predicate lower than local test */
1650         SWAP();
1651         NEXT;
1652         SKIP_BLANKS;
1653     }
1654     return;
1655 error:
1656     if (token != NULL)
1657         xmlFree(token);
1658     if (name != NULL)
1659         xmlFree(name);
1660 }
1661
1662 /**
1663  * xsltCompileRelativePathPattern:
1664  * @comp:  the compilation context
1665  * @token:  a posible precompiled name
1666  *
1667  * Compile the XSLT RelativePathPattern and generates a precompiled
1668  * form suitable for fast matching.
1669  *
1670  * [4] RelativePathPattern ::= StepPattern
1671  *                           | RelativePathPattern '/' StepPattern
1672  *                           | RelativePathPattern '//' StepPattern
1673  */
1674 static void
1675 xsltCompileRelativePathPattern(xsltParserContextPtr ctxt, xmlChar *token) {
1676     xsltCompileStepPattern(ctxt, token);
1677     if (ctxt->error)
1678         goto error;
1679     SKIP_BLANKS;
1680     while ((CUR != 0) && (CUR != '|')) {
1681         if ((CUR == '/') && (NXT(1) == '/')) {
1682             PUSH(XSLT_OP_ANCESTOR, NULL, NULL);
1683             NEXT;
1684             NEXT;
1685             SKIP_BLANKS;
1686             xsltCompileStepPattern(ctxt, NULL);
1687         } else if (CUR == '/') {
1688             PUSH(XSLT_OP_PARENT, NULL, NULL);
1689             NEXT;
1690             SKIP_BLANKS;
1691             if ((CUR != 0) && (CUR != '|')) {
1692                 xsltCompileRelativePathPattern(ctxt, NULL);
1693             }
1694         } else {
1695             ctxt->error = 1;
1696         }
1697         if (ctxt->error)
1698             goto error;
1699         SKIP_BLANKS;
1700     }
1701 error:
1702     return;
1703 }
1704
1705 /**
1706  * xsltCompileLocationPathPattern:
1707  * @ctxt:  the compilation context
1708  *
1709  * Compile the XSLT LocationPathPattern and generates a precompiled
1710  * form suitable for fast matching.
1711  *
1712  * [2] LocationPathPattern ::= '/' RelativePathPattern?
1713  *                           | IdKeyPattern (('/' | '//') RelativePathPattern)?
1714  *                           | '//'? RelativePathPattern
1715  */
1716 static void
1717 xsltCompileLocationPathPattern(xsltParserContextPtr ctxt) {
1718     SKIP_BLANKS;
1719     if ((CUR == '/') && (NXT(1) == '/')) {
1720         /*
1721          * since we reverse the query
1722          * a leading // can be safely ignored
1723          */
1724         NEXT;
1725         NEXT;
1726         ctxt->comp->priority = 0.5;     /* '//' means not 0 priority */
1727         xsltCompileRelativePathPattern(ctxt, NULL);
1728     } else if (CUR == '/') {
1729         /*
1730          * We need to find root as the parent
1731          */
1732         NEXT;
1733         SKIP_BLANKS;
1734         PUSH(XSLT_OP_ROOT, NULL, NULL);
1735         if ((CUR != 0) && (CUR != '|')) {
1736             PUSH(XSLT_OP_PARENT, NULL, NULL);
1737             xsltCompileRelativePathPattern(ctxt, NULL);
1738         }
1739     } else if (CUR == '*') {
1740         xsltCompileRelativePathPattern(ctxt, NULL);
1741     } else if (CUR == '@') {
1742         xsltCompileRelativePathPattern(ctxt, NULL);
1743     } else {
1744         xmlChar *name;
1745         name = xsltScanName(ctxt);
1746         if (name == NULL) {
1747             xsltTransformError(NULL, NULL, NULL,
1748                     "xsltCompileLocationPathPattern : Name expected\n");
1749             ctxt->error = 1;
1750             return;
1751         }
1752         SKIP_BLANKS;
1753         if ((CUR == '(') && !xmlXPathIsNodeType(name)) {
1754             xsltCompileIdKeyPattern(ctxt, name, 1);
1755             if ((CUR == '/') && (NXT(1) == '/')) {
1756                 PUSH(XSLT_OP_ANCESTOR, NULL, NULL);
1757                 NEXT;
1758                 NEXT;
1759                 SKIP_BLANKS;
1760                 xsltCompileRelativePathPattern(ctxt, NULL);
1761             } else if (CUR == '/') {
1762                 PUSH(XSLT_OP_PARENT, NULL, NULL);
1763                 NEXT;
1764                 SKIP_BLANKS;
1765                 xsltCompileRelativePathPattern(ctxt, NULL);
1766             }
1767             return;
1768         }
1769         xsltCompileRelativePathPattern(ctxt, name);
1770     }
1771 error:
1772     return;
1773 }
1774
1775 /**
1776  * xsltCompilePattern:
1777  * @pattern: an XSLT pattern
1778  * @doc:  the containing document
1779  * @node:  the containing element
1780  * @style:  the stylesheet
1781  * @runtime:  the transformation context, if done at run-time
1782  *
1783  * Compile the XSLT pattern and generates a list of precompiled form suitable
1784  * for fast matching.
1785  *
1786  * [1] Pattern ::= LocationPathPattern | Pattern '|' LocationPathPattern
1787  *
1788  * Returns the generated pattern list or NULL in case of failure
1789  */
1790
1791 xsltCompMatchPtr
1792 xsltCompilePattern(const xmlChar *pattern, xmlDocPtr doc,
1793                    xmlNodePtr node, xsltStylesheetPtr style,
1794                    xsltTransformContextPtr runtime) {
1795     xsltParserContextPtr ctxt = NULL;
1796     xsltCompMatchPtr element, first = NULL, previous = NULL;
1797     int current, start, end, level, j;
1798
1799     if (pattern == NULL) {
1800         xsltTransformError(NULL, NULL, node,
1801                          "xsltCompilePattern : NULL pattern\n");
1802         return(NULL);
1803     }
1804
1805     ctxt = xsltNewParserContext(style, runtime);
1806     if (ctxt == NULL)
1807         return(NULL);
1808     ctxt->doc = doc;
1809     ctxt->elem = node;
1810     current = end = 0;
1811     while (pattern[current] != 0) {
1812         start = current;
1813         while (IS_BLANK_CH(pattern[current]))
1814             current++;
1815         end = current;
1816         level = 0;
1817         while ((pattern[end] != 0) && ((pattern[end] != '|') || (level != 0))) {
1818             if (pattern[end] == '[')
1819                 level++;
1820             else if (pattern[end] == ']')
1821                 level--;
1822             else if (pattern[end] == '\'') {
1823                 end++;
1824                 while ((pattern[end] != 0) && (pattern[end] != '\''))
1825                     end++;
1826             } else if (pattern[end] == '"') {
1827                 end++;
1828                 while ((pattern[end] != 0) && (pattern[end] != '"'))
1829                     end++;
1830             }
1831             end++;
1832         }
1833         if (current == end) {
1834             xsltTransformError(NULL, NULL, node,
1835                              "xsltCompilePattern : NULL pattern\n");
1836             goto error;
1837         }
1838         element = xsltNewCompMatch();
1839         if (element == NULL) {
1840             goto error;
1841         }
1842         if (first == NULL)
1843             first = element;
1844         else if (previous != NULL)
1845             previous->next = element;
1846         previous = element;
1847
1848         ctxt->comp = element;
1849         ctxt->base = xmlStrndup(&pattern[start], end - start);
1850         if (ctxt->base == NULL)
1851             goto error;
1852         ctxt->cur = &(ctxt->base)[current - start];
1853         element->pattern = ctxt->base;
1854         element->nsList = xmlGetNsList(doc, node);
1855         j = 0;
1856         if (element->nsList != NULL) {
1857             while (element->nsList[j] != NULL)
1858                 j++;
1859         }
1860         element->nsNr = j;
1861
1862
1863 #ifdef WITH_XSLT_DEBUG_PATTERN
1864         xsltGenericDebug(xsltGenericDebugContext,
1865                          "xsltCompilePattern : parsing '%s'\n",
1866                          element->pattern);
1867 #endif
1868         /*
1869          Preset default priority to be zero.
1870          This may be changed by xsltCompileLocationPathPattern.
1871          */
1872         element->priority = 0;
1873         xsltCompileLocationPathPattern(ctxt);
1874         if (ctxt->error) {
1875             xsltTransformError(NULL, style, node,
1876                              "xsltCompilePattern : failed to compile '%s'\n",
1877                              element->pattern);
1878             if (style != NULL) style->errors++;
1879             goto error;
1880         }
1881
1882         /*
1883          * Reverse for faster interpretation.
1884          */
1885         xsltReverseCompMatch(element);
1886
1887         /*
1888          * Set-up the priority
1889          */
1890         if (element->priority == 0) {   /* if not yet determined */
1891             if (((element->steps[0].op == XSLT_OP_ELEM) ||
1892                  (element->steps[0].op == XSLT_OP_ATTR) ||
1893                  (element->steps[0].op == XSLT_OP_PI)) &&
1894                 (element->steps[0].value != NULL) &&
1895                 (element->steps[1].op == XSLT_OP_END)) {
1896                 ;       /* previously preset */
1897             } else if ((element->steps[0].op == XSLT_OP_ATTR) &&
1898                        (element->steps[0].value2 != NULL) &&
1899                        (element->steps[1].op == XSLT_OP_END)) {
1900                         element->priority = -0.25;
1901             } else if ((element->steps[0].op == XSLT_OP_NS) &&
1902                        (element->steps[0].value != NULL) &&
1903                        (element->steps[1].op == XSLT_OP_END)) {
1904                         element->priority = -0.25;
1905             } else if ((element->steps[0].op == XSLT_OP_ATTR) &&
1906                        (element->steps[0].value == NULL) &&
1907                        (element->steps[0].value2 == NULL) &&
1908                        (element->steps[1].op == XSLT_OP_END)) {
1909                         element->priority = -0.5;
1910             } else if (((element->steps[0].op == XSLT_OP_PI) ||
1911                        (element->steps[0].op == XSLT_OP_TEXT) ||
1912                        (element->steps[0].op == XSLT_OP_ALL) ||
1913                        (element->steps[0].op == XSLT_OP_NODE) ||
1914                        (element->steps[0].op == XSLT_OP_COMMENT)) &&
1915                        (element->steps[1].op == XSLT_OP_END)) {
1916                         element->priority = -0.5;
1917             } else {
1918                 element->priority = 0.5;
1919             }
1920         }
1921 #ifdef WITH_XSLT_DEBUG_PATTERN
1922         xsltGenericDebug(xsltGenericDebugContext,
1923                      "xsltCompilePattern : parsed %s, default priority %f\n",
1924                          element->pattern, element->priority);
1925 #endif
1926         if (pattern[end] == '|')
1927             end++;
1928         current = end;
1929     }
1930     if (end == 0) {
1931         xsltTransformError(NULL, style, node,
1932                          "xsltCompilePattern : NULL pattern\n");
1933         if (style != NULL) style->errors++;
1934         goto error;
1935     }
1936
1937     xsltFreeParserContext(ctxt);
1938     return(first);
1939
1940 error:
1941     if (ctxt != NULL)
1942         xsltFreeParserContext(ctxt);
1943     if (first != NULL)
1944         xsltFreeCompMatchList(first);
1945     return(NULL);
1946 }
1947
1948 /************************************************************************
1949  *                                                                      *
1950  *                      Module interfaces                               *
1951  *                                                                      *
1952  ************************************************************************/
1953
1954 /**
1955  * xsltAddTemplate:
1956  * @style: an XSLT stylesheet
1957  * @cur: an XSLT template
1958  * @mode:  the mode name or NULL
1959  * @modeURI:  the mode URI or NULL
1960  *
1961  * Register the XSLT pattern associated to @cur
1962  *
1963  * Returns -1 in case of error, 0 otherwise
1964  */
1965 int
1966 xsltAddTemplate(xsltStylesheetPtr style, xsltTemplatePtr cur,
1967                 const xmlChar *mode, const xmlChar *modeURI) {
1968     xsltCompMatchPtr pat, list, *top = NULL, next;
1969     const xmlChar *name = NULL;
1970     float priority;              /* the priority */
1971
1972     if ((style == NULL) || (cur == NULL) || (cur->match == NULL))
1973         return(-1);
1974
1975     priority = cur->priority;
1976     pat = xsltCompilePattern(cur->match, style->doc, cur->elem, style, NULL);
1977     while (pat) {
1978         next = pat->next;
1979         pat->next = NULL;
1980         name = NULL;
1981
1982         pat->template = cur;
1983         if (mode != NULL)
1984             pat->mode = xmlDictLookup(style->dict, mode, -1);
1985         if (modeURI != NULL)
1986             pat->modeURI = xmlDictLookup(style->dict, modeURI, -1);
1987         if (priority != XSLT_PAT_NO_PRIORITY)
1988             pat->priority = priority;
1989
1990         /*
1991          * insert it in the hash table list corresponding to its lookup name
1992          */
1993         switch (pat->steps[0].op) {
1994         case XSLT_OP_ATTR:
1995             if (pat->steps[0].value != NULL)
1996                 name = pat->steps[0].value;
1997             else
1998                 top = (xsltCompMatchPtr *) &(style->attrMatch);
1999             break;
2000         case XSLT_OP_CHILD:
2001         case XSLT_OP_PARENT:
2002         case XSLT_OP_ANCESTOR:
2003             top = (xsltCompMatchPtr *) &(style->elemMatch);
2004             break;
2005         case XSLT_OP_ROOT:
2006             top = (xsltCompMatchPtr *) &(style->rootMatch);
2007             break;
2008         case XSLT_OP_KEY:
2009             top = (xsltCompMatchPtr *) &(style->keyMatch);
2010             break;
2011         case XSLT_OP_ID:
2012             /* TODO optimize ID !!! */
2013         case XSLT_OP_NS:
2014         case XSLT_OP_ALL:
2015             top = (xsltCompMatchPtr *) &(style->elemMatch);
2016             break;
2017         case XSLT_OP_END:
2018         case XSLT_OP_PREDICATE:
2019             xsltTransformError(NULL, style, NULL,
2020                              "xsltAddTemplate: invalid compiled pattern\n");
2021             xsltFreeCompMatch(pat);
2022             return(-1);
2023             /*
2024              * TODO: some flags at the top level about type based patterns
2025              *       would be faster than inclusion in the hash table.
2026              */
2027         case XSLT_OP_PI:
2028             if (pat->steps[0].value != NULL)
2029                 name = pat->steps[0].value;
2030             else
2031                 top = (xsltCompMatchPtr *) &(style->piMatch);
2032             break;
2033         case XSLT_OP_COMMENT:
2034             top = (xsltCompMatchPtr *) &(style->commentMatch);
2035             break;
2036         case XSLT_OP_TEXT:
2037             top = (xsltCompMatchPtr *) &(style->textMatch);
2038             break;
2039         case XSLT_OP_ELEM:
2040         case XSLT_OP_NODE:
2041             if (pat->steps[0].value != NULL)
2042                 name = pat->steps[0].value;
2043             else
2044                 top = (xsltCompMatchPtr *) &(style->elemMatch);
2045             break;
2046         }
2047         if (name != NULL) {
2048             if (style->templatesHash == NULL) {
2049                 style->templatesHash = xmlHashCreate(1024);
2050                 if (style->templatesHash == NULL) {
2051                     xsltFreeCompMatch(pat);
2052                     return(-1);
2053                 }
2054                 xmlHashAddEntry3(style->templatesHash, name, mode, modeURI, pat);
2055             } else {
2056                 list = (xsltCompMatchPtr) xmlHashLookup3(style->templatesHash,
2057                                                          name, mode, modeURI);
2058                 if (list == NULL) {
2059                     xmlHashAddEntry3(style->templatesHash, name,
2060                                      mode, modeURI, pat);
2061                 } else {
2062                     /*
2063                      * Note '<=' since one must choose among the matching
2064                      * template rules that are left, the one that occurs
2065                      * last in the stylesheet
2066                      */
2067                     if (list->priority <= pat->priority) {
2068                         pat->next = list;
2069                         xmlHashUpdateEntry3(style->templatesHash, name,
2070                                             mode, modeURI, pat, NULL);
2071                     } else {
2072                         while (list->next != NULL) {
2073                             if (list->next->priority <= pat->priority)
2074                                 break;
2075                             list = list->next;
2076                         }
2077                         pat->next = list->next;
2078                         list->next = pat;
2079                     }
2080                 }
2081             }
2082         } else if (top != NULL) {
2083             list = *top;
2084             if (list == NULL) {
2085                 *top = pat;
2086                 pat->next = NULL;
2087             } else if (list->priority <= pat->priority) {
2088                 pat->next = list;
2089                 *top = pat;
2090             } else {
2091                 while (list->next != NULL) {
2092                     if (list->next->priority <= pat->priority)
2093                         break;
2094                     list = list->next;
2095                 }
2096                 pat->next = list->next;
2097                 list->next = pat;
2098             }
2099         } else {
2100             xsltTransformError(NULL, style, NULL,
2101                              "xsltAddTemplate: invalid compiled pattern\n");
2102             xsltFreeCompMatch(pat);
2103             return(-1);
2104         }
2105 #ifdef WITH_XSLT_DEBUG_PATTERN
2106         if (mode)
2107             xsltGenericDebug(xsltGenericDebugContext,
2108                          "added pattern : '%s' mode '%s' priority %f\n",
2109                              pat->pattern, pat->mode, pat->priority);
2110         else
2111             xsltGenericDebug(xsltGenericDebugContext,
2112                          "added pattern : '%s' priority %f\n",
2113                              pat->pattern, pat->priority);
2114 #endif
2115
2116         pat = next;
2117     }
2118     return(0);
2119 }
2120
2121 /**
2122  * xsltGetTemplate:
2123  * @ctxt:  a XSLT process context
2124  * @node:  the node being processed
2125  * @style:  the current style
2126  *
2127  * Finds the template applying to this node, if @style is non-NULL
2128  * it means one needs to look for the next imported template in scope.
2129  *
2130  * Returns the xsltTemplatePtr or NULL if not found
2131  */
2132 xsltTemplatePtr
2133 xsltGetTemplate(xsltTransformContextPtr ctxt, xmlNodePtr node,
2134                 xsltStylesheetPtr style) {
2135     xsltStylesheetPtr curstyle;
2136     xsltTemplatePtr ret = NULL;
2137     const xmlChar *name = NULL;
2138     xsltCompMatchPtr list = NULL;
2139     float priority;
2140     int keyed = 0;
2141
2142     if ((ctxt == NULL) || (node == NULL))
2143         return(NULL);
2144
2145     if (style == NULL) {
2146         curstyle = ctxt->style;
2147     } else {
2148         curstyle = xsltNextImport(style);
2149     }
2150
2151     while ((curstyle != NULL) && (curstyle != style)) {
2152         priority = XSLT_PAT_NO_PRIORITY;
2153         /* TODO : handle IDs/keys here ! */
2154         if (curstyle->templatesHash != NULL) {
2155             /*
2156              * Use the top name as selector
2157              */
2158             switch (node->type) {
2159                 case XML_ELEMENT_NODE:
2160                     if (node->name[0] == ' ')
2161                         break;
2162                 case XML_ATTRIBUTE_NODE:
2163                 case XML_PI_NODE:
2164                     name = node->name;
2165                     break;
2166                 case XML_DOCUMENT_NODE:
2167                 case XML_HTML_DOCUMENT_NODE:
2168                 case XML_TEXT_NODE:
2169                 case XML_CDATA_SECTION_NODE:
2170                 case XML_COMMENT_NODE:
2171                 case XML_ENTITY_REF_NODE:
2172                 case XML_ENTITY_NODE:
2173                 case XML_DOCUMENT_TYPE_NODE:
2174                 case XML_DOCUMENT_FRAG_NODE:
2175                 case XML_NOTATION_NODE:
2176                 case XML_DTD_NODE:
2177                 case XML_ELEMENT_DECL:
2178                 case XML_ATTRIBUTE_DECL:
2179                 case XML_ENTITY_DECL:
2180                 case XML_NAMESPACE_DECL:
2181                 case XML_XINCLUDE_START:
2182                 case XML_XINCLUDE_END:
2183                     break;
2184                 default:
2185                     return(NULL);
2186
2187             }
2188         }
2189         if (name != NULL) {
2190             /*
2191              * find the list of applicable expressions based on the name
2192              */
2193             list = (xsltCompMatchPtr) xmlHashLookup3(curstyle->templatesHash,
2194                                              name, ctxt->mode, ctxt->modeURI);
2195         } else
2196             list = NULL;
2197         while (list != NULL) {
2198             if (xsltTestCompMatch(ctxt, list, node,
2199                                   ctxt->mode, ctxt->modeURI)) {
2200                 ret = list->template;
2201                 priority = list->priority;
2202                 break;
2203             }
2204             list = list->next;
2205         }
2206         list = NULL;
2207
2208         /*
2209          * find alternate generic matches
2210          */
2211         switch (node->type) {
2212             case XML_ELEMENT_NODE:
2213                 if (node->name[0] == ' ')
2214                     list = curstyle->rootMatch;
2215                 else
2216                     list = curstyle->elemMatch;
2217                 if (node->psvi != NULL) keyed = 1;
2218                 break;
2219             case XML_ATTRIBUTE_NODE: {
2220                 xmlAttrPtr attr;
2221
2222                 list = curstyle->attrMatch;
2223                 attr = (xmlAttrPtr) node;
2224                 if (attr->psvi != NULL) keyed = 1;
2225                 break;
2226             }
2227             case XML_PI_NODE:
2228                 list = curstyle->piMatch;
2229                 if (node->psvi != NULL) keyed = 1;
2230                 break;
2231             case XML_DOCUMENT_NODE:
2232             case XML_HTML_DOCUMENT_NODE: {
2233                 xmlDocPtr doc;
2234
2235                 list = curstyle->rootMatch;
2236                 doc = (xmlDocPtr) node;
2237                 if (doc->psvi != NULL) keyed = 1;
2238                 break;
2239             }
2240             case XML_TEXT_NODE:
2241             case XML_CDATA_SECTION_NODE:
2242                 list = curstyle->textMatch;
2243                 if (node->psvi != NULL) keyed = 1;
2244                 break;
2245             case XML_COMMENT_NODE:
2246                 list = curstyle->commentMatch;
2247                 if (node->psvi != NULL) keyed = 1;
2248                 break;
2249             case XML_ENTITY_REF_NODE:
2250             case XML_ENTITY_NODE:
2251             case XML_DOCUMENT_TYPE_NODE:
2252             case XML_DOCUMENT_FRAG_NODE:
2253             case XML_NOTATION_NODE:
2254             case XML_DTD_NODE:
2255             case XML_ELEMENT_DECL:
2256             case XML_ATTRIBUTE_DECL:
2257             case XML_ENTITY_DECL:
2258             case XML_NAMESPACE_DECL:
2259             case XML_XINCLUDE_START:
2260             case XML_XINCLUDE_END:
2261                 break;
2262             default:
2263                 break;
2264         }
2265         while ((list != NULL) &&
2266                ((ret == NULL)  || (list->priority > priority))) {
2267             if (xsltTestCompMatch(ctxt, list, node,
2268                                   ctxt->mode, ctxt->modeURI)) {
2269                 ret = list->template;
2270                 priority = list->priority;
2271                 break;
2272             }
2273             list = list->next;
2274         }
2275         /*
2276          * Some of the tests for elements can also apply to documents
2277          */
2278         if ((node->type == XML_DOCUMENT_NODE) ||
2279             (node->type == XML_HTML_DOCUMENT_NODE) ||
2280             (node->type == XML_TEXT_NODE)) {
2281             list = curstyle->elemMatch;
2282             while ((list != NULL) &&
2283                    ((ret == NULL)  || (list->priority > priority))) {
2284                 if (xsltTestCompMatch(ctxt, list, node,
2285                                       ctxt->mode, ctxt->modeURI)) {
2286                     ret = list->template;
2287                     priority = list->priority;
2288                     break;
2289                 }
2290                 list = list->next;
2291             }
2292         } else if ((node->type == XML_PI_NODE) ||
2293                    (node->type == XML_COMMENT_NODE)) {
2294             list = curstyle->elemMatch;
2295             while ((list != NULL) &&
2296                    ((ret == NULL)  || (list->priority > priority))) {
2297                 if (xsltTestCompMatch(ctxt, list, node,
2298                                       ctxt->mode, ctxt->modeURI)) {
2299                     ret = list->template;
2300                     priority = list->priority;
2301                     break;
2302                 }
2303                 list = list->next;
2304             }
2305         }
2306
2307         if (keyed) {
2308             list = curstyle->keyMatch;
2309             while ((list != NULL) &&
2310                    ((ret == NULL)  || (list->priority > priority))) {
2311                 if (xsltTestCompMatch(ctxt, list, node,
2312                                       ctxt->mode, ctxt->modeURI)) {
2313                     ret = list->template;
2314                     priority = list->priority;
2315                     break;
2316                 }
2317                 list = list->next;
2318             }
2319         }
2320         if (ret != NULL)
2321             return(ret);
2322
2323         /*
2324          * Cycle on next curstylesheet import.
2325          */
2326         curstyle = xsltNextImport(curstyle);
2327     }
2328     return(NULL);
2329 }
2330
2331 /**
2332  * xsltCleanupTemplates:
2333  * @style: an XSLT stylesheet
2334  *
2335  * Cleanup the state of the templates used by the stylesheet and
2336  * the ones it imports.
2337  */
2338 void
2339 xsltCleanupTemplates(xsltStylesheetPtr style ATTRIBUTE_UNUSED) {
2340 }
2341
2342 /**
2343  * xsltFreeTemplateHashes:
2344  * @style: an XSLT stylesheet
2345  *
2346  * Free up the memory used by xsltAddTemplate/xsltGetTemplate mechanism
2347  */
2348 void
2349 xsltFreeTemplateHashes(xsltStylesheetPtr style) {
2350     if (style->templatesHash != NULL)
2351         xmlHashFree((xmlHashTablePtr) style->templatesHash,
2352                     (xmlHashDeallocator) xsltFreeCompMatchList);
2353     if (style->rootMatch != NULL)
2354         xsltFreeCompMatchList(style->rootMatch);
2355     if (style->keyMatch != NULL)
2356         xsltFreeCompMatchList(style->keyMatch);
2357     if (style->elemMatch != NULL)
2358         xsltFreeCompMatchList(style->elemMatch);
2359     if (style->attrMatch != NULL)
2360         xsltFreeCompMatchList(style->attrMatch);
2361     if (style->parentMatch != NULL)
2362         xsltFreeCompMatchList(style->parentMatch);
2363     if (style->textMatch != NULL)
2364         xsltFreeCompMatchList(style->textMatch);
2365     if (style->piMatch != NULL)
2366         xsltFreeCompMatchList(style->piMatch);
2367     if (style->commentMatch != NULL)
2368         xsltFreeCompMatchList(style->commentMatch);
2369 }
2370