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