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