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