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