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