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