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