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