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