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