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