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