libxslt/pattern.c

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