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  * Trickery: parse an XML name but without consuming the input flow
 857  * Needed to avoid insanity in the parser state.
 858  *
 859  * [4] NameChar ::= Letter | Digit | '.' | '-' | '_' | ':' |
 860  *                  CombiningChar | Extender
 861  *
 862  * [5] Name ::= (Letter | '_' | ':') (NameChar)*
 863  *
 864  * [6] Names ::= Name (S Name)*
 865  *
 866  * Returns the Name parsed or NULL
 867  */
 868
 869 static xmlChar *
 870 xsltScanName(xsltParserContextPtr ctxt) {
 871     xmlChar buf[XML_MAX_NAMELEN];
 872     int len = 0;
 873
 874     SKIP_BLANKS;
 875     if (!IS_LETTER(CUR) && (CUR != '_') &&
 876         (CUR != ':')) {
 877         return(NULL);
 878     }
 879
 880     while ((IS_LETTER(NXT(len))) || (IS_DIGIT(NXT(len))) ||
 881            (NXT(len) == '.') || (NXT(len) == '-') ||
 882            (NXT(len) == '_') || (NXT(len) == ':') ||
 883            (IS_COMBINING(NXT(len))) ||
 884            (IS_EXTENDER(NXT(len)))) {
 885         buf[len] = NXT(len);
 886         len++;
 887         if (len >= XML_MAX_NAMELEN) {
 888             xmlGenericError(xmlGenericErrorContext,
 889                "xmlScanName: reached XML_MAX_NAMELEN limit\n");
 890             while ((IS_LETTER(NXT(len))) || (IS_DIGIT(NXT(len))) ||
 891                    (NXT(len) == '.') || (NXT(len) == '-') ||
 892                    (NXT(len) == '_') || (NXT(len) == ':') ||
 893                    (IS_COMBINING(NXT(len))) ||
 894                    (IS_EXTENDER(NXT(len))))
 895                  len++;
 896             break;
 897         }
 898     }
 899     SKIP(len);
 900     return(xmlStrndup(buf, len));
 901 }
 902 /*
 903  * xsltCompileIdKeyPattern:
 904  * @comp:  the compilation context
 905  * @name:  a preparsed name
 906  * @aid:  whether id/key are allowed there
 907  *
 908  * Compile the XSLT LocationIdKeyPattern
 909  * [3] IdKeyPattern ::= 'id' '(' Literal ')'
 910  *                    | 'key' '(' Literal ',' Literal ')'
 911  *
 912  * also handle NodeType and PI from:
 913  *
 914  * [7]  NodeTest ::= NameTest
 915  *                 | NodeType '(' ')'
 916  *                 | 'processing-instruction' '(' Literal ')'
 917  */
 918 static void
 919 xsltCompileIdKeyPattern(xsltParserContextPtr ctxt, xmlChar *name, int aid) {
 920     xmlChar *lit = NULL;
 921     xmlChar *lit2 = NULL;
 922
 923     if (CUR != '(') {
 924         xsltGenericError(xsltGenericErrorContext,
 925                 "xsltCompileIdKeyPattern : ( expected\n");
 926         ctxt->error = 1;
 927         return;
 928     }
 929     if ((aid) && (xmlStrEqual(name, (const xmlChar *)"id"))) {
 930         NEXT;
 931         SKIP_BLANKS;
 932         lit = xsltScanLiteral(ctxt);
 933         if (ctxt->error)
 934             return;
 935         SKIP_BLANKS;
 936         if (CUR != ')') {
 937             xsltGenericError(xsltGenericErrorContext,
 938                     "xsltCompileIdKeyPattern : ) expected\n");
 939             ctxt->error = 1;
 940             return;
 941         }
 942         NEXT;
 943         PUSH(XSLT_OP_ID, lit, NULL);
 944     } else if ((aid) && (xmlStrEqual(name, (const xmlChar *)"key"))) {
 945         NEXT;
 946         SKIP_BLANKS;
 947         lit = xsltScanLiteral(ctxt);
 948         if (ctxt->error)
 949             return;
 950         SKIP_BLANKS;
 951         if (CUR != ',') {
 952             xsltGenericError(xsltGenericErrorContext,
 953                     "xsltCompileIdKeyPattern : , expected\n");
 954             ctxt->error = 1;
 955             return;
 956         }
 957         NEXT;
 958         SKIP_BLANKS;
 959         lit2 = xsltScanLiteral(ctxt);
 960         if (ctxt->error)
 961             return;
 962         SKIP_BLANKS;
 963         if (CUR != ')') {
 964             xsltGenericError(xsltGenericErrorContext,
 965                     "xsltCompileIdKeyPattern : ) expected\n");
 966             ctxt->error = 1;
 967             return;
 968         }
 969         NEXT;
 970         /* TODO: support namespace in keys */
 971         PUSH(XSLT_OP_KEY, lit, lit2);
 972     } else if (xmlStrEqual(name, (const xmlChar *)"processing-instruction")) {
 973         NEXT;
 974         SKIP_BLANKS;
 975         if (CUR != ')') {
 976             lit = xsltScanLiteral(ctxt);
 977             if (ctxt->error)
 978                 return;
 979             SKIP_BLANKS;
 980             if (CUR != ')') {
 981                 xsltGenericError(xsltGenericErrorContext,
 982                         "xsltCompileIdKeyPattern : ) expected\n");
 983                 ctxt->error = 1;
 984                 return;
 985             }
 986         }
 987         NEXT;
 988         PUSH(XSLT_OP_PI, lit, NULL);
 989     } else if (xmlStrEqual(name, (const xmlChar *)"text")) {
 990         NEXT;
 991         SKIP_BLANKS;
 992         if (CUR != ')') {
 993             xsltGenericError(xsltGenericErrorContext,
 994                     "xsltCompileIdKeyPattern : ) expected\n");
 995             ctxt->error = 1;
 996             return;
 997         }
 998         NEXT;
 999         PUSH(XSLT_OP_TEXT, NULL, NULL);
1000     } else if (xmlStrEqual(name, (const xmlChar *)"comment")) {
1001         NEXT;
1002         SKIP_BLANKS;
1003         if (CUR != ')') {
1004             xsltGenericError(xsltGenericErrorContext,
1005                     "xsltCompileIdKeyPattern : ) expected\n");
1006             ctxt->error = 1;
1007             return;
1008         }
1009         NEXT;
1010         PUSH(XSLT_OP_COMMENT, NULL, NULL);
1011     } else if (xmlStrEqual(name, (const xmlChar *)"node")) {
1012         NEXT;
1013         SKIP_BLANKS;
1014         if (CUR != ')') {
1015             xsltGenericError(xsltGenericErrorContext,
1016                     "xsltCompileIdKeyPattern : ) expected\n");
1017             ctxt->error = 1;
1018             return;
1019         }
1020         NEXT;
1021         PUSH(XSLT_OP_NODE, NULL, NULL);
1022     } else if (aid) {
1023         xsltGenericError(xsltGenericErrorContext,
1024             "xsltCompileIdKeyPattern : expecting 'key' or 'id' or node type\n");
1025         ctxt->error = 1;
1026         return;
1027     } else {
1028         xsltGenericError(xsltGenericErrorContext,
1029             "xsltCompileIdKeyPattern : node type\n");
1030         ctxt->error = 1;
1031         return;
1032     }
1033 error:
1034     if (name != NULL)
1035         xmlFree(name);
1036 }
1037
1038 /**
1039  * xsltCompileStepPattern:
1040  * @comp:  the compilation context
1041  * @token:  a posible precompiled name
1042  *
1043  * Compile the XSLT StepPattern and generates a precompiled
1044  * form suitable for fast matching.
1045  *
1046  * [5] StepPattern ::= ChildOrAttributeAxisSpecifier NodeTest Predicate*
1047  * [6] ChildOrAttributeAxisSpecifier ::= AbbreviatedAxisSpecifier
1048  *                                     | ('child' | 'attribute') '::'
1049  * from XPath
1050  * [7]  NodeTest ::= NameTest
1051  *                 | NodeType '(' ')'
1052  *                 | 'processing-instruction' '(' Literal ')'
1053  * [8] Predicate ::= '[' PredicateExpr ']'
1054  * [9] PredicateExpr ::= Expr
1055  * [13] AbbreviatedAxisSpecifier ::= '@'?
1056  * [37] NameTest ::= '*' | NCName ':' '*' | QName
1057  */
1058
1059 static void
1060 xsltCompileStepPattern(xsltParserContextPtr ctxt, xmlChar *token) {
1061     xmlChar *name = NULL;
1062     xmlChar *prefix = NULL;
1063     xmlChar *ncname = NULL;
1064     xmlChar *URL = NULL;
1065     int level;
1066
1067     SKIP_BLANKS;
1068     if ((token == NULL) && (CUR == '@')) {
1069         NEXT;
1070         if (CUR == '*') {
1071             NEXT;
1072             PUSH(XSLT_OP_ATTR, NULL, NULL);
1073             return;
1074         }
1075         token = xsltScanName(ctxt);
1076         if (token == NULL) {
1077             xsltGenericError(xsltGenericErrorContext,
1078                     "xsltCompileStepPattern : Name expected\n");
1079             ctxt->error = 1;
1080             goto error;
1081         }
1082         PUSH(XSLT_OP_ATTR, token, NULL);
1083         return;
1084     }
1085     if (token == NULL)
1086         token = xsltScanName(ctxt);
1087     if (token == NULL) {
1088         if (CUR == '*') {
1089             NEXT;
1090             PUSH(XSLT_OP_ALL, token, NULL);
1091             goto parse_predicate;
1092         } else {
1093             xsltGenericError(xsltGenericErrorContext,
1094                     "xsltCompileStepPattern : Name expected\n");
1095             ctxt->error = 1;
1096             goto error;
1097         }
1098     }
1099
1100
1101     SKIP_BLANKS;
1102     if (CUR == '(') {
1103         xsltCompileIdKeyPattern(ctxt, token, 0);
1104         if (ctxt->error)
1105             goto error;
1106     } else if (CUR == ':') {
1107         NEXT;
1108         if (NXT(1) != ':') {
1109             xsltGenericError(xsltGenericErrorContext,
1110                     "xsltCompileStepPattern : sequence '::' expected\n");
1111             ctxt->error = 1;
1112             goto error;
1113         }
1114         NEXT;
1115         if (xmlStrEqual(token, (const xmlChar *) "child")) {
1116             name = xsltScanName(ctxt);
1117             if (name == NULL) {
1118                 xsltGenericError(xsltGenericErrorContext,
1119                         "xsltCompileStepPattern : QName expected\n");
1120                 ctxt->error = 1;
1121                 goto error;
1122             }
1123             ncname = xmlSplitQName2(name, &prefix);
1124             if (ncname != NULL) {
1125                 if (prefix != NULL) {
1126                     xmlNsPtr ns;
1127
1128                     ns = xmlSearchNs(ctxt->doc, ctxt->elem, prefix);
1129                     if (ns == NULL) {
1130                         xsltGenericError(xsltGenericErrorContext,
1131                             "xsl: pattern, no namespace bound to prefix %s\n",
1132                                          prefix);
1133                     } else {
1134                         URL = xmlStrdup(ns->href);
1135                     }
1136                     xmlFree(prefix);
1137                 }
1138                 xmlFree(name);
1139                 name = ncname;
1140             }
1141             PUSH(XSLT_OP_CHILD, name, URL);
1142         } else if (xmlStrEqual(token, (const xmlChar *) "attribute")) {
1143             name = xsltScanName(ctxt);
1144             if (name == NULL) {
1145                 xsltGenericError(xsltGenericErrorContext,
1146                         "xsltCompileStepPattern : QName expected\n");
1147                 ctxt->error = 1;
1148                 goto error;
1149             }
1150             ncname = xmlSplitQName2(name, &prefix);
1151             if (ncname != NULL) {
1152                 if (prefix != NULL) {
1153                     xmlNsPtr ns;
1154
1155                     ns = xmlSearchNs(ctxt->doc, ctxt->elem, prefix);
1156                     if (ns == NULL) {
1157                         xsltGenericError(xsltGenericErrorContext,
1158                             "xsl: pattern, no namespace bound to prefix %s\n",
1159                                          prefix);
1160                     } else {
1161                         URL = xmlStrdup(ns->href);
1162                     }
1163                     xmlFree(prefix);
1164                 }
1165                 xmlFree(name);
1166                 name = ncname;
1167             }
1168             PUSH(XSLT_OP_ATTR, name, URL);
1169         } else {
1170             xsltGenericError(xsltGenericErrorContext,
1171                 "xsltCompileStepPattern : 'child' or 'attribute' expected\n");
1172             ctxt->error = 1;
1173             goto error;
1174         }
1175         xmlFree(token);
1176     } else if (CUR == '*') {
1177         NEXT;
1178         PUSH(XSLT_OP_ALL, token, NULL);
1179     } else {
1180         ncname = xmlSplitQName2(token, &prefix);
1181         if (ncname != NULL) {
1182             if (prefix != NULL) {
1183                 xmlNsPtr ns;
1184
1185                 ns = xmlSearchNs(ctxt->doc, ctxt->elem, prefix);
1186                 if (ns == NULL) {
1187                     xsltGenericError(xsltGenericErrorContext,
1188                         "xsl: pattern, no namespace bound to prefix %s\n",
1189                                      prefix);
1190                 } else {
1191                     URL = xmlStrdup(ns->href);
1192                 }
1193                 xmlFree(prefix);
1194             }
1195             xmlFree(token);
1196             token = ncname;
1197         }
1198         PUSH(XSLT_OP_ELEM, token, URL);
1199     }
1200 parse_predicate:
1201     SKIP_BLANKS;
1202     level = 0;
1203     while (CUR == '[') {
1204         const xmlChar *q;
1205         xmlChar *ret = NULL;
1206
1207         level++;
1208         NEXT;
1209         q = CUR_PTR;
1210         /* TODO: avoid breaking in strings ... */
1211         while (IS_CHAR(CUR)) {
1212             /* Skip over nested predicates */
1213             if (CUR == '[')
1214                 level++;
1215             if (CUR == ']') {
1216                 level--;
1217                 if (level == 0)
1218                     break;
1219             }
1220             NEXT;
1221         }
1222         if (!IS_CHAR(CUR)) {
1223             xsltGenericError(xsltGenericErrorContext,
1224                     "xsltCompileStepPattern : ']' expected\n");
1225             ctxt->error = 1;
1226             goto error;
1227         }
1228         ret = xmlStrndup(q, CUR_PTR - q);
1229         PUSH(XSLT_OP_PREDICATE, ret, NULL);
1230         /* push the predicate lower than local test */
1231         SWAP();
1232         NEXT;
1233     }
1234     return;
1235 error:
1236     if (token != NULL)
1237         xmlFree(token);
1238     if (name != NULL)
1239         xmlFree(name);
1240 }
1241
1242 /**
1243  * xsltCompileRelativePathPattern:
1244  * @comp:  the compilation context
1245  * @token:  a posible precompiled name
1246  *
1247  * Compile the XSLT RelativePathPattern and generates a precompiled
1248  * form suitable for fast matching.
1249  *
1250  * [4] RelativePathPattern ::= StepPattern
1251  *                           | RelativePathPattern '/' StepPattern
1252  *                           | RelativePathPattern '//' StepPattern
1253  */
1254 static void
1255 xsltCompileRelativePathPattern(xsltParserContextPtr ctxt, xmlChar *token) {
1256     xsltCompileStepPattern(ctxt, token);
1257     if (ctxt->error)
1258         goto error;
1259     SKIP_BLANKS;
1260     while ((CUR != 0) && (CUR != '|')) {
1261         if ((CUR == '/') && (NXT(1) == '/')) {
1262             PUSH(XSLT_OP_ANCESTOR, NULL, NULL);
1263             NEXT;
1264             NEXT;
1265             SKIP_BLANKS;
1266             xsltCompileStepPattern(ctxt, NULL);
1267         } else if (CUR == '/') {
1268             PUSH(XSLT_OP_PARENT, NULL, NULL);
1269             NEXT;
1270             SKIP_BLANKS;
1271             if ((CUR != 0) || (CUR == '|')) {
1272                 xsltCompileRelativePathPattern(ctxt, NULL);
1273             }
1274         } else {
1275             ctxt->error = 1;
1276         }
1277         if (ctxt->error)
1278             goto error;
1279         SKIP_BLANKS;
1280     }
1281 error:
1282     return;
1283 }
1284
1285 /**
1286  * xsltCompileLocationPathPattern:
1287  * @comp:  the compilation context
1288  *
1289  * Compile the XSLT LocationPathPattern and generates a precompiled
1290  * form suitable for fast matching.
1291  *
1292  * [2] LocationPathPattern ::= '/' RelativePathPattern?
1293  *                           | IdKeyPattern (('/' | '//') RelativePathPattern)?
1294  *                           | '//'? RelativePathPattern
1295  */
1296 static void
1297 xsltCompileLocationPathPattern(xsltParserContextPtr ctxt) {
1298     SKIP_BLANKS;
1299     if ((CUR == '/') && (NXT(1) == '/')) {
1300         /*
1301          * since we reverse the query
1302          * a leading // can be safely ignored
1303          */
1304         NEXT;
1305         NEXT;
1306         xsltCompileRelativePathPattern(ctxt, NULL);
1307     } else if (CUR == '/') {
1308         /*
1309          * We need to find root as the parent
1310          */
1311         NEXT;
1312         SKIP_BLANKS;
1313         PUSH(XSLT_OP_ROOT, NULL, NULL);
1314         if ((CUR != 0) || (CUR == '|')) {
1315             PUSH(XSLT_OP_PARENT, NULL, NULL);
1316             xsltCompileRelativePathPattern(ctxt, NULL);
1317         }
1318     } else if (CUR == '*') {
1319         xsltCompileRelativePathPattern(ctxt, NULL);
1320     } else if (CUR == '@') {
1321         xsltCompileRelativePathPattern(ctxt, NULL);
1322     } else {
1323         xmlChar *name;
1324         name = xsltScanName(ctxt);
1325         if (name == NULL) {
1326             xsltGenericError(xsltGenericErrorContext,
1327                     "xsltCompileLocationPathPattern : Name expected\n");
1328             ctxt->error = 1;
1329             return;
1330         }
1331         SKIP_BLANKS;
1332         if ((CUR == '(') && !xmlXPathIsNodeType(name)) {
1333             xsltCompileIdKeyPattern(ctxt, name, 1);
1334             if ((CUR == '/') && (NXT(1) == '/')) {
1335                 PUSH(XSLT_OP_ANCESTOR, NULL, NULL);
1336                 NEXT;
1337                 NEXT;
1338                 SKIP_BLANKS;
1339                 xsltCompileRelativePathPattern(ctxt, NULL);
1340             } else if (CUR == '/') {
1341                 PUSH(XSLT_OP_PARENT, NULL, NULL);
1342                 NEXT;
1343                 SKIP_BLANKS;
1344                 xsltCompileRelativePathPattern(ctxt, NULL);
1345             }
1346             return;
1347         }
1348         xsltCompileRelativePathPattern(ctxt, name);
1349     }
1350 error:
1351     return;
1352 }
1353
1354 /**
1355  * xsltCompilePattern:
1356  * @pattern an XSLT pattern
1357  * @doc:  the containing document
1358  * @node:  the containing element
1359  *
1360  * Compile the XSLT pattern and generates a list of precompiled form suitable
1361  * for fast matching.
1362  *
1363  * [1] Pattern ::= LocationPathPattern | Pattern '|' LocationPathPattern
1364  *
1365  * Returns the generated pattern list or NULL in case of failure
1366  */
1367
1368 xsltCompMatchPtr
1369 xsltCompilePattern(const xmlChar *pattern, xmlDocPtr doc, xmlNodePtr node) {
1370     xsltParserContextPtr ctxt = NULL;
1371     xsltCompMatchPtr element, first = NULL, previous = NULL;
1372     int current, start, end;
1373
1374     if (pattern == NULL) {
1375         xsltGenericError(xsltGenericErrorContext,
1376                          "xsltCompilePattern : NULL pattern\n");
1377         return(NULL);
1378     }
1379
1380 #ifdef WITH_XSLT_DEBUG_PATTERN
1381     xsltGenericDebug(xsltGenericDebugContext,
1382                      "xsltCompilePattern : parsing '%s'\n", pattern);
1383 #endif
1384
1385     ctxt = xsltNewParserContext();
1386     if (ctxt == NULL)
1387         return(NULL);
1388     ctxt->doc = doc;
1389     ctxt->elem = node;
1390     current = end = 0;
1391     while (pattern[current] != 0) {
1392         start = current;
1393         while (IS_BLANK(pattern[current]))
1394             current++;
1395         end = current;
1396         while ((pattern[end] != 0) && (pattern[end] != '|'))
1397             end++;
1398         if (current == end) {
1399             xsltGenericError(xsltGenericErrorContext,
1400                              "xsltCompilePattern : NULL pattern\n");
1401             goto error;
1402         }
1403         element = xsltNewCompMatch();
1404         if (element == NULL) {
1405             goto error;
1406         }
1407         if (first == NULL)
1408             first = element;
1409         else if (previous != NULL)
1410             previous->next = element;
1411         previous = element;
1412
1413         ctxt->comp = element;
1414         ctxt->base = xmlStrndup(&pattern[start], end - start);
1415         ctxt->cur = &(ctxt->base)[current - start];
1416         xsltCompileLocationPathPattern(ctxt);
1417         if (ctxt->base)
1418             xmlFree((xmlChar *)ctxt->base);
1419         if (ctxt->error)
1420             goto error;
1421
1422         /*
1423          * Reverse for faster interpretation.
1424          */
1425         xsltReverseCompMatch(element);
1426
1427         /*
1428          * Set-up the priority
1429          */
1430         if (((element->steps[0].op == XSLT_OP_ELEM) ||
1431              (element->steps[0].op == XSLT_OP_ATTR)) &&
1432             (element->steps[0].value != NULL) &&
1433             (element->steps[1].op == XSLT_OP_END)) {
1434             element->priority = 0;
1435         } else if ((element->steps[0].op == XSLT_OP_ROOT) &&
1436                    (element->steps[1].op == XSLT_OP_END)) {
1437             element->priority = 0;
1438         } else if ((element->steps[0].op == XSLT_OP_PI) &&
1439                    (element->steps[0].value != NULL) &&
1440                    (element->steps[1].op == XSLT_OP_END)) {
1441             element->priority = 0;
1442         } else if ((element->steps[0].op == XSLT_OP_NS) &&
1443                    (element->steps[0].value != NULL) &&
1444                    (element->steps[1].op == XSLT_OP_END)) {
1445             element->priority = -0.25;
1446         } else if (((element->steps[0].op == XSLT_OP_PI) ||
1447                     (element->steps[0].op == XSLT_OP_TEXT) ||
1448                     (element->steps[0].op == XSLT_OP_ALL) ||
1449                     (element->steps[0].op == XSLT_OP_NODE) ||
1450                     (element->steps[0].op == XSLT_OP_COMMENT)) &&
1451                    (element->steps[1].op == XSLT_OP_END)) {
1452             element->priority = -0.5;
1453         } else {
1454             element->priority = 0.5;
1455         }
1456         if (pattern[end] == '|')
1457             end++;
1458         current = end;
1459     }
1460     if (end == 0) {
1461         xsltGenericError(xsltGenericErrorContext,
1462                          "xsltCompilePattern : NULL pattern\n");
1463         goto error;
1464     }
1465
1466     xsltFreeParserContext(ctxt);
1467     return(first);
1468
1469 error:
1470     if (ctxt != NULL)
1471         xsltFreeParserContext(ctxt);
1472     if (first != NULL)
1473         xsltFreeCompMatchList(first);
1474     return(NULL);
1475 }
1476
1477 /************************************************************************
1478  *                                                                      *
1479  *                      Module interfaces                               *
1480  *                                                                      *
1481  ************************************************************************/
1482
1483 /**
1484  * xsltAddTemplate:
1485  * @style: an XSLT stylesheet
1486  * @cur: an XSLT template
1487  * @mode:  the mode name or NULL
1488  * @modeURI:  the mode URI or NULL
1489  *
1490  * Register the XSLT pattern associated to @cur
1491  *
1492  * Returns -1 in case of error, 0 otherwise
1493  */
1494 int
1495 xsltAddTemplate(xsltStylesheetPtr style, xsltTemplatePtr cur,
1496                 const xmlChar *mode, const xmlChar *modeURI) {
1497     xsltCompMatchPtr pat, list, *top = NULL, next;
1498     const xmlChar *name = NULL;
1499
1500     if ((style == NULL) || (cur == NULL) || (cur->match == NULL))
1501         return(-1);
1502
1503     pat = xsltCompilePattern(cur->match, style->doc, cur->elem);
1504     while (pat) {
1505         next = pat->next;
1506         pat->next = NULL;
1507
1508         pat->template = cur;
1509         if (mode != NULL)
1510             pat->mode = xmlStrdup(mode);
1511         if (modeURI != NULL)
1512             pat->modeURI = xmlStrdup(modeURI);
1513         if (cur->priority == XSLT_PAT_NO_PRIORITY)
1514             cur->priority = pat->priority;
1515         else
1516             pat->priority = cur->priority;
1517
1518         /*
1519          * insert it in the hash table list corresponding to its lookup name
1520          */
1521         switch (pat->steps[0].op) {
1522         case XSLT_OP_ATTR:
1523             if (pat->steps[0].value != NULL)
1524                 name = pat->steps[0].value;
1525             else
1526                 top = (xsltCompMatchPtr *) &(style->attrMatch);
1527             break;
1528         case XSLT_OP_ELEM:
1529         case XSLT_OP_CHILD:
1530         case XSLT_OP_PARENT:
1531         case XSLT_OP_ANCESTOR:
1532         case XSLT_OP_NS:
1533             name = pat->steps[0].value;
1534             break;
1535         case XSLT_OP_ROOT:
1536             top = (xsltCompMatchPtr *) &(style->rootMatch);
1537             break;
1538         case XSLT_OP_KEY:
1539             top = (xsltCompMatchPtr *) &(style->keyMatch);
1540             break;
1541         case XSLT_OP_ID:
1542             /* TODO optimize ID !!! */
1543         case XSLT_OP_ALL:
1544             top = (xsltCompMatchPtr *) &(style->elemMatch);
1545             break;
1546         case XSLT_OP_END:
1547         case XSLT_OP_PREDICATE:
1548             xsltGenericError(xsltGenericErrorContext,
1549                              "xsltAddTemplate: invalid compiled pattern\n");
1550             xsltFreeCompMatch(pat);
1551             return(-1);
1552             /*
1553              * TODO: some flags at the top level about type based patterns
1554              *       would be faster than inclusion in the hash table.
1555              */
1556         case XSLT_OP_PI:
1557             if (pat->steps[0].value != NULL)
1558                 name = pat->steps[0].value;
1559             else
1560                 top = (xsltCompMatchPtr *) &(style->piMatch);
1561             break;
1562         case XSLT_OP_COMMENT:
1563             top = (xsltCompMatchPtr *) &(style->commentMatch);
1564             break;
1565         case XSLT_OP_TEXT:
1566             top = (xsltCompMatchPtr *) &(style->textMatch);
1567             break;
1568         case XSLT_OP_NODE:
1569             if (pat->steps[0].value != NULL)
1570                 name = pat->steps[0].value;
1571             else
1572                 top = (xsltCompMatchPtr *) &(style->elemMatch);
1573
1574             break;
1575         }
1576         if (name != NULL) {
1577             if (style->templatesHash == NULL) {
1578                 style->templatesHash = xmlHashCreate(1024);
1579                 if (style->templatesHash == NULL) {
1580                     xsltFreeCompMatch(pat);
1581                     return(-1);
1582                 }
1583                 xmlHashAddEntry3(style->templatesHash, name, mode, modeURI, pat);
1584             } else {
1585                 list = (xsltCompMatchPtr) xmlHashLookup3(style->templatesHash,
1586                                                          name, mode, modeURI);
1587                 if (list == NULL) {
1588                     xmlHashAddEntry3(style->templatesHash, name,
1589                                      mode, modeURI, pat);
1590                 } else {
1591                     /*
1592                      * Note '<=' since one must choose among the matching
1593                      * template rules that are left, the one that occurs
1594                      * last in the stylesheet
1595                      */
1596                     if (list->priority <= pat->priority) {
1597                         pat->next = list;
1598                         xmlHashUpdateEntry3(style->templatesHash, name,
1599                                             mode, modeURI, pat, NULL);
1600                     } else {
1601                         while (list->next != NULL) {
1602                             if (list->next->priority <= pat->priority)
1603                                 break;
1604                             list = list->next;
1605                         }
1606                         pat->next = list->next;
1607                         list->next = pat;
1608                     }
1609                 }
1610             }
1611         } else if (top != NULL) {
1612             list = *top;
1613             if (list == NULL) {
1614                 *top = pat;
1615                 pat->next = NULL;
1616             } else if (list->priority <= pat->priority) {
1617                 pat->next = list;
1618                 *top = pat;
1619             } else {
1620                 while (list->next != NULL) {
1621                     if (list->next->priority <= pat->priority)
1622                         break;
1623                     list = list->next;
1624                 }
1625                 pat->next = list->next;
1626                 list->next = pat;
1627             }
1628         } else {
1629             xsltGenericError(xsltGenericErrorContext,
1630                              "xsltAddTemplate: invalid compiled pattern\n");
1631             xsltFreeCompMatch(pat);
1632             return(-1);
1633         }
1634 #ifdef WITH_XSLT_DEBUG_PATTERN
1635         if (mode)
1636             xsltGenericDebug(xsltGenericDebugContext,
1637                          "added pattern : '%s' mode '%s' priority %f\n",
1638                              pat->template->match, pat->mode, pat->priority);
1639         else
1640             xsltGenericDebug(xsltGenericDebugContext,
1641                          "added pattern : '%s' priority %f\n",
1642                              pat->template->match, pat->priority);
1643 #endif
1644
1645         pat = next;
1646     }
1647     return(0);
1648 }
1649
1650 /**
1651  * xsltGetTemplate:
1652  * @ctxt:  a XSLT process context
1653  * @mode:  the mode
1654  * @style:  the current style
1655  *
1656  * Finds the template applying to this node, if @style is non-NULL
1657  * it means one need to look for the next imported template in scope.
1658  *
1659  * Returns the xsltTemplatePtr or NULL if not found
1660  */
1661 xsltTemplatePtr
1662 xsltGetTemplate(xsltTransformContextPtr ctxt, xmlNodePtr node,
1663                 xsltStylesheetPtr style) {
1664     xsltStylesheetPtr curstyle;
1665     xsltTemplatePtr ret = NULL;
1666     const xmlChar *name = NULL;
1667     xsltCompMatchPtr list = NULL;
1668
1669     if ((ctxt == NULL) || (node == NULL))
1670         return(NULL);
1671
1672     if (style == NULL) {
1673         curstyle = ctxt->style;
1674     } else {
1675         curstyle = xsltNextImport(style);
1676     }
1677
1678     while ((curstyle != NULL) && (curstyle != style)) {
1679         /* TODO : handle IDs/keys here ! */
1680         if (curstyle->templatesHash != NULL) {
1681             /*
1682              * Use the top name as selector
1683              */
1684             switch (node->type) {
1685                 case XML_ELEMENT_NODE:
1686                 case XML_ATTRIBUTE_NODE:
1687                 case XML_PI_NODE:
1688                     name = node->name;
1689                     break;
1690                 case XML_DOCUMENT_NODE:
1691                 case XML_HTML_DOCUMENT_NODE:
1692                 case XML_TEXT_NODE:
1693                 case XML_CDATA_SECTION_NODE:
1694                 case XML_COMMENT_NODE:
1695                 case XML_ENTITY_REF_NODE:
1696                 case XML_ENTITY_NODE:
1697                 case XML_DOCUMENT_TYPE_NODE:
1698                 case XML_DOCUMENT_FRAG_NODE:
1699                 case XML_NOTATION_NODE:
1700                 case XML_DTD_NODE:
1701                 case XML_ELEMENT_DECL:
1702                 case XML_ATTRIBUTE_DECL:
1703                 case XML_ENTITY_DECL:
1704                 case XML_NAMESPACE_DECL:
1705                 case XML_XINCLUDE_START:
1706                 case XML_XINCLUDE_END:
1707                     break;
1708                 default:
1709                     return(NULL);
1710
1711             }
1712         }
1713         if (name != NULL) {
1714             /*
1715              * find the list of appliable expressions based on the name
1716              */
1717             list = (xsltCompMatchPtr) xmlHashLookup3(curstyle->templatesHash,
1718                                              name, ctxt->mode, ctxt->modeURI);
1719         } else
1720             list = NULL;
1721         while (list != NULL) {
1722             if (xsltTestCompMatch(ctxt, list, node,
1723                                   ctxt->mode, ctxt->modeURI)) {
1724                 ret = list->template;
1725                 break;
1726             }
1727             list = list->next;
1728         }
1729         list = NULL;
1730
1731         /*
1732          * find alternate generic matches
1733          */
1734         switch (node->type) {
1735             case XML_ELEMENT_NODE:
1736                 list = curstyle->elemMatch;
1737                 break;
1738             case XML_ATTRIBUTE_NODE:
1739                 list = curstyle->attrMatch;
1740                 break;
1741             case XML_PI_NODE:
1742                 list = curstyle->piMatch;
1743                 break;
1744             case XML_DOCUMENT_NODE:
1745             case XML_HTML_DOCUMENT_NODE:
1746                 list = curstyle->rootMatch;
1747                 break;
1748             case XML_TEXT_NODE:
1749             case XML_CDATA_SECTION_NODE:
1750                 list = curstyle->textMatch;
1751                 break;
1752             case XML_COMMENT_NODE:
1753                 list = curstyle->commentMatch;
1754                 break;
1755             case XML_ENTITY_REF_NODE:
1756             case XML_ENTITY_NODE:
1757             case XML_DOCUMENT_TYPE_NODE:
1758             case XML_DOCUMENT_FRAG_NODE:
1759             case XML_NOTATION_NODE:
1760             case XML_DTD_NODE:
1761             case XML_ELEMENT_DECL:
1762             case XML_ATTRIBUTE_DECL:
1763             case XML_ENTITY_DECL:
1764             case XML_NAMESPACE_DECL:
1765             case XML_XINCLUDE_START:
1766             case XML_XINCLUDE_END:
1767                 break;
1768             default:
1769                 break;
1770
1771         }
1772         while ((list != NULL) &&
1773                ((ret == NULL)  || (list->priority > ret->priority))) {
1774             if (xsltTestCompMatch(ctxt, list, node,
1775                                   ctxt->mode, ctxt->modeURI)) {
1776                 ret = list->template;
1777                 break;
1778             }
1779             list = list->next;
1780         }
1781         if (node->_private != NULL) {
1782             list = curstyle->keyMatch;
1783             while ((list != NULL) &&
1784                    ((ret == NULL)  || (list->priority > ret->priority))) {
1785                 if (xsltTestCompMatch(ctxt, list, node,
1786                                       ctxt->mode, ctxt->modeURI)) {
1787                     ret = list->template;
1788                     break;
1789                 }
1790                 list = list->next;
1791             }
1792         }
1793         if (ret != NULL)
1794             return(ret);
1795
1796         /*
1797          * Cycle on next curstylesheet import.
1798          */
1799         curstyle = xsltNextImport(curstyle);
1800     }
1801     return(NULL);
1802 }
1803
1804 /**
1805  * xsltCleanupTemplates:
1806  * @style: an XSLT stylesheet
1807  *
1808  * Cleanup the state of the templates used by the stylesheet and
1809  * the ones it imports.
1810  */
1811 void
1812 xsltCleanupTemplates(xsltStylesheetPtr style) {
1813     while (style != NULL) {
1814         xmlHashScan((xmlHashTablePtr) style->templatesHash,
1815                     (xmlHashScanner) xsltCleanupCompMatch, NULL);
1816
1817         style = xsltNextImport(style);
1818     }
1819 }
1820
1821 /**
1822  * xsltFreeTemplateHashes:
1823  * @style: an XSLT stylesheet
1824  *
1825  * Free up the memory used by xsltAddTemplate/xsltGetTemplate mechanism
1826  */
1827 void
1828 xsltFreeTemplateHashes(xsltStylesheetPtr style) {
1829     if (style->templatesHash != NULL)
1830         xmlHashFree((xmlHashTablePtr) style->templatesHash,
1831                     (xmlHashDeallocator) xsltFreeCompMatchList);
1832     if (style->rootMatch != NULL)
1833         xsltFreeCompMatchList(style->rootMatch);
1834     if (style->keyMatch != NULL)
1835         xsltFreeCompMatchList(style->keyMatch);
1836     if (style->elemMatch != NULL)
1837         xsltFreeCompMatchList(style->elemMatch);
1838     if (style->attrMatch != NULL)
1839         xsltFreeCompMatchList(style->attrMatch);
1840     if (style->parentMatch != NULL)
1841         xsltFreeCompMatchList(style->parentMatch);
1842     if (style->textMatch != NULL)
1843         xsltFreeCompMatchList(style->textMatch);
1844     if (style->piMatch != NULL)
1845         xsltFreeCompMatchList(style->piMatch);
1846     if (style->commentMatch != NULL)
1847         xsltFreeCompMatchList(style->commentMatch);
1848 }
1849
1850 #if 0
1851 /**
1852  * xsltMatchPattern
1853  * @node: a node in the source tree
1854  * @pattern: an XSLT pattern
1855  *
1856  * Determine if a node matches a pattern.
1857  */
1858 int
1859 xsltMatchPattern(xsltTransformContextPtr context,
1860                  xmlNodePtr node,
1861                  const xmlChar *pattern)
1862 {
1863     int match = 0;
1864     xsltCompMatchPtr first, comp;
1865
1866     if ((context != NULL) && (pattern != NULL)) {
1867         first = xsltCompilePattern(pattern);
1868         for (comp = first; comp != NULL; comp = comp->next) {
1869             match = xsltTestCompMatch(context, comp, node, NULL, NULL);
1870             if (match)
1871                 break; /* for */
1872         }
1873         if (first)
1874             xsltFreeCompMatchList(first);
1875     }
1876     return match;
1877 }
1878 #endif