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