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