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@imag.fr
  10  */
  11
  12 #include "xsltconfig.h"
  13
  14 #include <string.h>
  15
  16 #include <libxml/xmlmemory.h>
  17 #include <libxml/tree.h>
  18 #include <libxml/valid.h>
  19 #include <libxml/hash.h>
  20 #include <libxml/xmlerror.h>
  21 #include <libxml/parserInternals.h>
  22 #include "xslt.h"
  23 #include "xsltInternals.h"
  24 #include "xsltutils.h"
  25 #include "imports.h"
  26 #include "templates.h"
  27 #include "keys.h"
  28 #include "pattern.h"
  29
  30 /* #define DEBUG_PARSING */
  31
  32 /*
  33  * Types are private:
  34  */
  35
  36 typedef enum {
  37     XSLT_OP_END=0,
  38     XSLT_OP_ROOT,
  39     XSLT_OP_ELEM,
  40     XSLT_OP_CHILD,
  41     XSLT_OP_ATTR,
  42     XSLT_OP_PARENT,
  43     XSLT_OP_ANCESTOR,
  44     XSLT_OP_ID,
  45     XSLT_OP_KEY,
  46     XSLT_OP_NS,
  47     XSLT_OP_ALL,
  48     XSLT_OP_PI,
  49     XSLT_OP_COMMENT,
  50     XSLT_OP_TEXT,
  51     XSLT_OP_NODE,
  52     XSLT_OP_PREDICATE
  53 } xsltOp;
  54
  55
  56 typedef struct _xsltStepOp xsltStepOp;
  57 typedef xsltStepOp *xsltStepOpPtr;
  58 struct _xsltStepOp {
  59     xsltOp op;
  60     xmlChar *value;
  61     xmlChar *value2;
  62     xmlChar *value3;
  63 };
  64
  65 struct _xsltCompMatch {
  66     struct _xsltCompMatch *next; /* siblings in the name hash */
  67     float priority;              /* the priority */
  68     const xmlChar *mode;         /* the mode */
  69     const xmlChar *modeURI;      /* the mode URI */
  70     xsltTemplatePtr template;    /* the associated template */
  71
  72     /* TODO fix the statically allocated size steps[] */
  73     int nbStep;
  74     int maxStep;
  75     xsltStepOp steps[20];        /* ops for computation */
  76 };
  77
  78 typedef struct _xsltParserContext xsltParserContext;
  79 typedef xsltParserContext *xsltParserContextPtr;
  80 struct _xsltParserContext {
  81     const xmlChar *cur;                 /* the current char being parsed */
  82     const xmlChar *base;                /* the full expression */
  83     int error;                          /* error code */
  84     xsltCompMatchPtr comp;              /* the result */
  85 };
  86
  87 /************************************************************************
  88  *                                                                      *
  89  *                      Type functions                                  *
  90  *                                                                      *
  91  ************************************************************************/
  92
  93 /**
  94  * xsltNewCompMatch:
  95  *
  96  * Create a new XSLT CompMatch
  97  *
  98  * Returns the newly allocated xsltCompMatchPtr or NULL in case of error
  99  */
 100 xsltCompMatchPtr
 101 xsltNewCompMatch(void) {
 102     xsltCompMatchPtr cur;
 103
 104     cur = (xsltCompMatchPtr) xmlMalloc(sizeof(xsltCompMatch));
 105     if (cur == NULL) {
 106         xsltGenericError(xsltGenericErrorContext,
 107                 "xsltNewCompMatch : malloc failed\n");
 108         return(NULL);
 109     }
 110     memset(cur, 0, sizeof(xsltCompMatch));
 111     cur->maxStep = 20;
 112     return(cur);
 113 }
 114
 115 /**
 116  * xsltFreeCompMatch:
 117  * @comp:  an XSLT comp
 118  *
 119  * Free up the memory allocated by @comp
 120  */
 121 void
 122 xsltFreeCompMatch(xsltCompMatchPtr comp) {
 123     xsltStepOpPtr op;
 124     int i;
 125
 126     if (comp == NULL)
 127         return;
 128     if (comp->mode != NULL)
 129         xmlFree((xmlChar *)comp->mode);
 130     if (comp->modeURI != NULL)
 131         xmlFree((xmlChar *)comp->modeURI);
 132     for (i = 0;i < comp->nbStep;i++) {
 133         op = &comp->steps[i];
 134         if (op->value != NULL)
 135             xmlFree(op->value);
 136         if (op->value2 != NULL)
 137             xmlFree(op->value2);
 138         if (op->value3 != NULL)
 139             xmlFree(op->value3);
 140     }
 141     memset(comp, -1, sizeof(xsltCompMatch));
 142     xmlFree(comp);
 143 }
 144
 145 /**
 146  * xsltFreeCompMatchList:
 147  * @comp:  an XSLT comp list
 148  *
 149  * Free up the memory allocated by all the elements of @comp
 150  */
 151 void
 152 xsltFreeCompMatchList(xsltCompMatchPtr comp) {
 153     xsltCompMatchPtr cur;
 154
 155     while (comp != NULL) {
 156         cur = comp;
 157         comp = comp->next;
 158         xsltFreeCompMatch(cur);
 159     }
 160 }
 161
 162 /**
 163  * xsltNewParserContext:
 164  *
 165  * Create a new XSLT ParserContext
 166  *
 167  * Returns the newly allocated xsltParserContextPtr or NULL in case of error
 168  */
 169 xsltParserContextPtr
 170 xsltNewParserContext(void) {
 171     xsltParserContextPtr cur;
 172
 173     cur = (xsltParserContextPtr) xmlMalloc(sizeof(xsltParserContext));
 174     if (cur == NULL) {
 175         xsltGenericError(xsltGenericErrorContext,
 176                 "xsltNewParserContext : malloc failed\n");
 177         return(NULL);
 178     }
 179     memset(cur, 0, sizeof(xsltParserContext));
 180     return(cur);
 181 }
 182
 183 /**
 184  * xsltFreeParserContext:
 185  * @ctxt:  an XSLT parser context
 186  *
 187  * Free up the memory allocated by @ctxt
 188  */
 189 void
 190 xsltFreeParserContext(xsltParserContextPtr ctxt) {
 191     if (ctxt == NULL)
 192         return;
 193     memset(ctxt, -1, sizeof(xsltParserContext));
 194     xmlFree(ctxt);
 195 }
 196
 197 /**
 198  * xsltCompMatchAdd:
 199  * @comp:  the compiled match expression
 200  * @op:  an op
 201  * @value:  the first value
 202  * @value2:  the second value
 203  *
 204  * Add an step to an XSLT Compiled Match
 205  *
 206  * Returns -1 in case of failure, 0 otherwise.
 207  */
 208 int
 209 xsltCompMatchAdd(xsltCompMatchPtr comp, xsltOp op, xmlChar *value,
 210                    xmlChar *value2) {
 211     if (comp->nbStep >= 20) {
 212         xsltGenericError(xsltGenericErrorContext,
 213                 "xsltCompMatchAddOp: overflow\n");
 214         return(-1);
 215     }
 216     comp->steps[comp->nbStep].op = op;
 217     comp->steps[comp->nbStep].value = value;
 218     comp->steps[comp->nbStep].value2 = value2;
 219     comp->nbStep++;
 220     return(0);
 221 }
 222
 223 /**
 224  * xsltSwapTopCompMatch:
 225  * @comp:  the compiled match expression
 226  *
 227  * reverse the two top steps.
 228  */
 229 void
 230 xsltSwapTopCompMatch(xsltCompMatchPtr comp) {
 231     int i;
 232     int j = comp->nbStep - 1;
 233
 234     if (j > 0) {
 235         register xmlChar *tmp;
 236         register xsltOp op;
 237         i = j - 1;
 238         tmp = comp->steps[i].value;
 239         comp->steps[i].value = comp->steps[j].value;
 240         comp->steps[j].value = tmp;
 241         tmp = comp->steps[i].value2;
 242         comp->steps[i].value2 = comp->steps[j].value2;
 243         comp->steps[j].value2 = tmp;
 244         op = comp->steps[i].op;
 245         comp->steps[i].op = comp->steps[j].op;
 246         comp->steps[j].op = op;
 247     }
 248 }
 249
 250 /**
 251  * xsltReverseCompMatch:
 252  * @comp:  the compiled match expression
 253  *
 254  * reverse all the stack of expressions
 255  */
 256 void
 257 xsltReverseCompMatch(xsltCompMatchPtr comp) {
 258     int i = 0;
 259     int j = comp->nbStep - 1;
 260
 261     while (j > i) {
 262         register xmlChar *tmp;
 263         register xsltOp op;
 264         tmp = comp->steps[i].value;
 265         comp->steps[i].value = comp->steps[j].value;
 266         comp->steps[j].value = tmp;
 267         tmp = comp->steps[i].value2;
 268         comp->steps[i].value2 = comp->steps[j].value2;
 269         comp->steps[j].value2 = tmp;
 270         op = comp->steps[i].op;
 271         comp->steps[i].op = comp->steps[j].op;
 272         comp->steps[j].op = op;
 273         j--;
 274         i++;
 275     }
 276     comp->steps[comp->nbStep++].op = XSLT_OP_END;
 277 }
 278
 279 /************************************************************************
 280  *                                                                      *
 281  *              The interpreter for the precompiled patterns            *
 282  *                                                                      *
 283  ************************************************************************/
 284
 285 /**
 286  * xsltTestCompMatch:
 287  * @ctxt:  a XSLT process context
 288  * @comp: the precompiled pattern
 289  * @node: a node
 290  * @mode:  the mode name or NULL
 291  * @modeURI:  the mode URI or NULL
 292  *
 293  * Test wether the node matches the pattern
 294  *
 295  * Returns 1 if it matches, 0 if it doesn't and -1 in case of failure
 296  */
 297 int
 298 xsltTestCompMatch(xsltTransformContextPtr ctxt, xsltCompMatchPtr comp,
 299                   xmlNodePtr node, const xmlChar *mode,
 300                   const xmlChar *modeURI) {
 301     int i;
 302     xsltStepOpPtr step, select = NULL;
 303
 304     if ((comp == NULL) || (node == NULL) || (ctxt == NULL)) {
 305         xsltGenericError(xsltGenericErrorContext,
 306                 "xsltTestCompMatch: null arg\n");
 307         return(-1);
 308     }
 309     if (mode != NULL) {
 310         if (comp->mode == NULL)
 311             return(0);
 312         if ((comp->mode != mode) && (!xmlStrEqual(comp->mode, mode)))
 313             return(0);
 314     } else {
 315         if (comp->mode != NULL)
 316             return(0);
 317     }
 318     if (modeURI != NULL) {
 319         if (comp->modeURI == NULL)
 320             return(0);
 321         if ((comp->modeURI != modeURI) &&
 322             (!xmlStrEqual(comp->modeURI, modeURI)))
 323             return(0);
 324     } else {
 325         if (comp->modeURI != NULL)
 326             return(0);
 327     }
 328     for (i = 0;i < comp->nbStep;i++) {
 329         step = &comp->steps[i];
 330         if (step->op != XSLT_OP_PREDICATE)
 331             select = step;
 332         switch (step->op) {
 333             case XSLT_OP_END:
 334                 return(1);
 335             case XSLT_OP_ROOT:
 336                 if ((node->type != XML_DOCUMENT_NODE) &&
 337                     (node->type != XML_HTML_DOCUMENT_NODE))
 338                     return(0);
 339                 continue;
 340             case XSLT_OP_ELEM:
 341                 if (node->type != XML_ELEMENT_NODE)
 342                     return(0);
 343                 if (step->value == NULL)
 344                     continue;
 345                 if (!xmlStrEqual(step->value, node->name))
 346                     return(0);
 347
 348                 /* Namespace test */
 349                 if (node->ns == NULL) {
 350                     if (step->value2 != NULL)
 351                         return(0);
 352                 } else if (node->ns->href != NULL) {
 353                     if (step->value2 == NULL)
 354                         return(0);
 355                     if (!xmlStrEqual(step->value2, node->ns->href))
 356                         return(0);
 357                 }
 358                 continue;
 359             case XSLT_OP_CHILD:
 360                 TODO /* Handle OP_CHILD */
 361                 return(0);
 362             case XSLT_OP_ATTR:
 363                 if (node->type != XML_ATTRIBUTE_NODE)
 364                     return(0);
 365                 if (step->value == NULL)
 366                     continue;
 367                 if (!xmlStrEqual(step->value, node->name))
 368                     return(0);
 369
 370                 /* Namespace test */
 371                 if (node->ns == NULL) {
 372                     if (step->value2 != NULL)
 373                         return(0);
 374                 } else if (node->ns->href != NULL) {
 375                     if (step->value2 == NULL)
 376                         return(0);
 377                     if (!xmlStrEqual(step->value2, node->ns->href))
 378                         return(0);
 379                 }
 380                 continue;
 381             case XSLT_OP_PARENT:
 382                 node = node->parent;
 383                 if (node == NULL)
 384                     return(0);
 385                 if (step->value == NULL)
 386                     continue;
 387                 if (!xmlStrEqual(step->value, node->name))
 388                     return(0);
 389                 /* Namespace test */
 390                 if (node->ns == NULL) {
 391                     if (step->value2 != NULL)
 392                         return(0);
 393                 } else if (node->ns->href != NULL) {
 394                     if (step->value2 == NULL)
 395                         return(0);
 396                     if (!xmlStrEqual(step->value2, node->ns->href))
 397                         return(0);
 398                 }
 399                 continue;
 400             case XSLT_OP_ANCESTOR:
 401                 /* TODO: implement coalescing of ANCESTOR/NODE ops */
 402                 if (step->value == NULL) {
 403                     i++;
 404                     step = &comp->steps[i];
 405                     if (step->op == XSLT_OP_ROOT)
 406                         return(1);
 407                     if (step->op != XSLT_OP_ELEM)
 408                         return(0);
 409                     if (step->value == NULL)
 410                         return(-1);
 411                 }
 412                 if (node == NULL)
 413                     return(0);
 414                 node = node->parent;
 415                 while (node != NULL) {
 416                     if (node == NULL)
 417                         return(0);
 418                     if (xmlStrEqual(step->value, node->name)) {
 419                         /* Namespace test */
 420                         if (node->ns == NULL) {
 421                             if (step->value2 == NULL)
 422                                 break;
 423                         } else if (node->ns->href != NULL) {
 424                             if ((step->value2 != NULL) &&
 425                                 (xmlStrEqual(step->value2, node->ns->href)))
 426                                 break;
 427                         }
 428                     }
 429                     node = node->parent;
 430                 }
 431                 if (node == NULL)
 432                     return(0);
 433                 continue;
 434             case XSLT_OP_ID: {
 435                 /* TODO Handle IDs decently, must be done differently */
 436                 xmlAttrPtr id;
 437
 438                 id = xmlGetID(node->doc, step->value);
 439                 if ((id == NULL) || (id->parent != node))
 440                     return(0);
 441                 break;
 442             }
 443             case XSLT_OP_KEY: {
 444                 xmlNodeSetPtr list;
 445                 int i;
 446
 447                 list = xsltGetKey(ctxt, step->value,
 448                                   step->value3, step->value2);
 449                 if (list == NULL)
 450                     return(0);
 451                 for (i = 0;i < list->nodeNr;i++)
 452                     if (list->nodeTab[i] == node)
 453                         break;
 454                 if (i >= list->nodeNr)
 455                     return(0);
 456                 break;
 457             }
 458             case XSLT_OP_NS:
 459                 /* Namespace test */
 460                 if (node->ns == NULL) {
 461                     if (step->value != NULL)
 462                         return(0);
 463                 } else if (node->ns->href != NULL) {
 464                     if (step->value == NULL)
 465                         return(0);
 466                     if (!xmlStrEqual(step->value, node->ns->href))
 467                         return(0);
 468                 }
 469                 break;
 470             case XSLT_OP_ALL:
 471                 switch (node->type) {
 472                     case XML_DOCUMENT_NODE:
 473                     case XML_HTML_DOCUMENT_NODE:
 474                     case XML_ELEMENT_NODE:
 475                         break;
 476                     default:
 477                         return(0);
 478                 }
 479                 break;
 480             case XSLT_OP_PREDICATE: {
 481                 xmlNodePtr oldNode;
 482                 int oldCS, oldCP;
 483                 int pos = 0, len = 0;
 484                 /*
 485                  * Depending on the last selection, one may need to
 486                  * recompute contextSize and proximityPosition.
 487                  */
 488                 oldCS = ctxt->xpathCtxt->contextSize;
 489                 oldCP = ctxt->xpathCtxt->proximityPosition;
 490                 if ((select != NULL) &&
 491                     (select->op == XSLT_OP_ELEM) &&
 492                     (select->value != NULL) &&
 493                     (node->type == XML_ELEMENT_NODE) &&
 494                     (node->parent != NULL)) {
 495
 496                     /* TODO: cache those informations ?!? */
 497                     xmlNodePtr siblings = node->parent->children;
 498
 499                     while (siblings != NULL) {
 500                         if (siblings->type == XML_ELEMENT_NODE) {
 501                             if (siblings == node) {
 502                                 len++;
 503                                 pos = len;
 504                             } else if (xmlStrEqual(node->name,
 505                                        siblings->name)) {
 506                                 len++;
 507                             }
 508                         }
 509                         siblings = siblings->next;
 510                     }
 511                     if (pos != 0) {
 512                         ctxt->xpathCtxt->contextSize = len;
 513                         ctxt->xpathCtxt->proximityPosition = pos;
 514                     }
 515                 }
 516                 oldNode = ctxt->node;
 517                 ctxt->node = node;
 518
 519                 if ((step->value == NULL) ||
 520                     (!xsltEvalXPathPredicate(ctxt, step->value))) {
 521                     if (pos != 0) {
 522                         ctxt->xpathCtxt->contextSize = oldCS;
 523                         ctxt->xpathCtxt->proximityPosition = oldCP;
 524                     }
 525                     ctxt->node = oldNode;
 526                     return(0);
 527                 }
 528                 if (pos != 0) {
 529                     ctxt->xpathCtxt->contextSize = oldCS;
 530                     ctxt->xpathCtxt->proximityPosition = oldCP;
 531                 }
 532                 ctxt->node = oldNode;
 533                 break;
 534             }
 535             case XSLT_OP_PI:
 536                 if (node->type != XML_PI_NODE)
 537                     return(0);
 538                 if (step->value != NULL) {
 539                     if (!xmlStrEqual(step->value, node->name))
 540                         return(0);
 541                 }
 542                 break;
 543             case XSLT_OP_COMMENT:
 544                 if (node->type != XML_COMMENT_NODE)
 545                     return(0);
 546                 break;
 547             case XSLT_OP_TEXT:
 548                 if ((node->type != XML_TEXT_NODE) &&
 549                     (node->type != XML_CDATA_SECTION_NODE))
 550                     return(0);
 551                 break;
 552             case XSLT_OP_NODE:
 553                 switch (node->type) {
 554                     case XML_DOCUMENT_NODE:
 555                     case XML_HTML_DOCUMENT_NODE:
 556                     case XML_ELEMENT_NODE:
 557                     case XML_CDATA_SECTION_NODE:
 558                     case XML_PI_NODE:
 559                     case XML_COMMENT_NODE:
 560                     case XML_TEXT_NODE:
 561                     case XML_ATTRIBUTE_NODE:
 562                         break;
 563                     default:
 564                         return(0);
 565                 }
 566                 break;
 567         }
 568     }
 569     return(1);
 570 }
 571
 572 /**
 573  * xsltTestCompMatchList:
 574  * @ctxt:  a XSLT process context
 575  * @node: a node
 576  * @comp: the precompiled pattern list
 577  *
 578  * Test wether the node matches one of the patterns in the list
 579  *
 580  * Returns 1 if it matches, 0 if it doesn't and -1 in case of failure
 581  */
 582 int
 583 xsltTestCompMatchList(xsltTransformContextPtr ctxt, xmlNodePtr node,
 584                       xsltCompMatchPtr comp) {
 585     int ret;
 586
 587     if ((ctxt == NULL) || (node == NULL))
 588         return(-1);
 589     while (comp != NULL) {
 590         ret = xsltTestCompMatch(ctxt, comp, node, NULL, NULL);
 591         if (ret == 1)
 592             return(1);
 593         comp = comp->next;
 594     }
 595     return(0);
 596 }
 597
 598 /************************************************************************
 599  *                                                                      *
 600  *                      Dedicated parser for templates                  *
 601  *                                                                      *
 602  ************************************************************************/
 603
 604 #define CUR (*ctxt->cur)
 605 #define SKIP(val) ctxt->cur += (val)
 606 #define NXT(val) ctxt->cur[(val)]
 607 #define CUR_PTR ctxt->cur
 608
 609 #define SKIP_BLANKS                                                     \
 610     while (IS_BLANK(CUR)) NEXT
 611
 612 #define CURRENT (*ctxt->cur)
 613 #define NEXT ((*ctxt->cur) ?  ctxt->cur++: ctxt->cur)
 614
 615
 616 #define PUSH(op, val, val2)                                             \
 617     if (xsltCompMatchAdd(ctxt->comp, (op), (val), (val2))) goto error;
 618
 619 #define SWAP()                                          \
 620     xsltSwapTopCompMatch(ctxt->comp);
 621
 622 #define XSLT_ERROR(X)                                                   \
 623     { xsltError(ctxt, __FILE__, __LINE__, X);                   \
 624       ctxt->error = (X); return; }
 625
 626 #define XSLT_ERROR0(X)                                                  \
 627     { xsltError(ctxt, __FILE__, __LINE__, X);                   \
 628       ctxt->error = (X); return(0); }
 629
 630 /**
 631  * xsltScanLiteral:
 632  * @ctxt:  the XPath Parser context
 633  *
 634  * Parse an XPath Litteral:
 635  *
 636  * [29] Literal ::= '"' [^"]* '"'
 637  *                | "'" [^']* "'"
 638  *
 639  * Returns the Literal parsed or NULL
 640  */
 641
 642 xmlChar *
 643 xsltScanLiteral(xsltParserContextPtr ctxt) {
 644     const xmlChar *q;
 645     xmlChar *ret = NULL;
 646
 647     SKIP_BLANKS;
 648     if (CUR == '"') {
 649         NEXT;
 650         q = CUR_PTR;
 651         while ((IS_CHAR(CUR)) && (CUR != '"'))
 652             NEXT;
 653         if (!IS_CHAR(CUR)) {
 654             /* XP_ERROR(XPATH_UNFINISHED_LITERAL_ERROR); */
 655             ctxt->error = 1;
 656             return(NULL);
 657         } else {
 658             ret = xmlStrndup(q, CUR_PTR - q);
 659             NEXT;
 660         }
 661     } else if (CUR == '\'') {
 662         NEXT;
 663         q = CUR_PTR;
 664         while ((IS_CHAR(CUR)) && (CUR != '\''))
 665             NEXT;
 666         if (!IS_CHAR(CUR)) {
 667             /* XP_ERROR(XPATH_UNFINISHED_LITERAL_ERROR); */
 668             ctxt->error = 1;
 669             return(NULL);
 670         } else {
 671             ret = xmlStrndup(q, CUR_PTR - q);
 672             NEXT;
 673         }
 674     } else {
 675         /* XP_ERROR(XPATH_START_LITERAL_ERROR); */
 676         ctxt->error = 1;
 677         return(NULL);
 678     }
 679     return(ret);
 680 }
 681
 682 /**
 683  * xsltScanName:
 684  * @ctxt:  the XPath Parser context
 685  *
 686  * Trickery: parse an XML name but without consuming the input flow
 687  * Needed to avoid insanity in the parser state.
 688  *
 689  * [4] NameChar ::= Letter | Digit | '.' | '-' | '_' | ':' |
 690  *                  CombiningChar | Extender
 691  *
 692  * [5] Name ::= (Letter | '_' | ':') (NameChar)*
 693  *
 694  * [6] Names ::= Name (S Name)*
 695  *
 696  * Returns the Name parsed or NULL
 697  */
 698
 699 xmlChar *
 700 xsltScanName(xsltParserContextPtr ctxt) {
 701     xmlChar buf[XML_MAX_NAMELEN];
 702     int len = 0;
 703
 704     SKIP_BLANKS;
 705     if (!IS_LETTER(CUR) && (CUR != '_') &&
 706         (CUR != ':')) {
 707         return(NULL);
 708     }
 709
 710     while ((IS_LETTER(NXT(len))) || (IS_DIGIT(NXT(len))) ||
 711            (NXT(len) == '.') || (NXT(len) == '-') ||
 712            (NXT(len) == '_') || (NXT(len) == ':') ||
 713            (IS_COMBINING(NXT(len))) ||
 714            (IS_EXTENDER(NXT(len)))) {
 715         buf[len] = NXT(len);
 716         len++;
 717         if (len >= XML_MAX_NAMELEN) {
 718             xmlGenericError(xmlGenericErrorContext,
 719                "xmlScanName: reached XML_MAX_NAMELEN limit\n");
 720             while ((IS_LETTER(NXT(len))) || (IS_DIGIT(NXT(len))) ||
 721                    (NXT(len) == '.') || (NXT(len) == '-') ||
 722                    (NXT(len) == '_') || (NXT(len) == ':') ||
 723                    (IS_COMBINING(NXT(len))) ||
 724                    (IS_EXTENDER(NXT(len))))
 725                  len++;
 726             break;
 727         }
 728     }
 729     SKIP(len);
 730     return(xmlStrndup(buf, len));
 731 }
 732 /*
 733  * xsltCompileIdKeyPattern:
 734  * @comp:  the compilation context
 735  * @name:  a preparsed name
 736  * @aid:  whether id/key are allowed there
 737  *
 738  * Compile the XSLT LocationIdKeyPattern
 739  * [3] IdKeyPattern ::= 'id' '(' Literal ')'
 740  *                    | 'key' '(' Literal ',' Literal ')'
 741  *
 742  * also handle NodeType and PI from:
 743  *
 744  * [7]  NodeTest ::= NameTest
 745  *                 | NodeType '(' ')'
 746  *                 | 'processing-instruction' '(' Literal ')'
 747  */
 748 void
 749 xsltCompileIdKeyPattern(xsltParserContextPtr ctxt, xmlChar *name, int aid) {
 750     xmlChar *lit = NULL;
 751     xmlChar *lit2 = NULL;
 752
 753     if (CUR != '(') {
 754         xsltGenericError(xsltGenericErrorContext,
 755                 "xsltCompileIdKeyPattern : ( expected\n");
 756         ctxt->error = 1;
 757         return;
 758     }
 759     if ((aid) && (xmlStrEqual(name, (const xmlChar *)"id"))) {
 760         NEXT;
 761         SKIP_BLANKS;
 762         lit = xsltScanLiteral(ctxt);
 763         if (ctxt->error)
 764             return;
 765         SKIP_BLANKS;
 766         if (CUR != ')') {
 767             xsltGenericError(xsltGenericErrorContext,
 768                     "xsltCompileIdKeyPattern : ) expected\n");
 769             ctxt->error = 1;
 770             return;
 771         }
 772         NEXT;
 773         PUSH(XSLT_OP_ID, lit, NULL);
 774     } else if ((aid) && (xmlStrEqual(name, (const xmlChar *)"key"))) {
 775         NEXT;
 776         SKIP_BLANKS;
 777         lit = xsltScanLiteral(ctxt);
 778         if (ctxt->error)
 779             return;
 780         SKIP_BLANKS;
 781         if (CUR != ',') {
 782             xsltGenericError(xsltGenericErrorContext,
 783                     "xsltCompileIdKeyPattern : , expected\n");
 784             ctxt->error = 1;
 785             return;
 786         }
 787         NEXT;
 788         SKIP_BLANKS;
 789         lit2 = xsltScanLiteral(ctxt);
 790         if (ctxt->error)
 791             return;
 792         SKIP_BLANKS;
 793         if (CUR != ')') {
 794             xsltGenericError(xsltGenericErrorContext,
 795                     "xsltCompileIdKeyPattern : ) expected\n");
 796             ctxt->error = 1;
 797             return;
 798         }
 799         NEXT;
 800         /* TODO: support namespace in keys */
 801         PUSH(XSLT_OP_KEY, lit, lit2);
 802     } else if (xmlStrEqual(name, (const xmlChar *)"processing-instruction")) {
 803         NEXT;
 804         SKIP_BLANKS;
 805         if (CUR != ')') {
 806             lit = xsltScanLiteral(ctxt);
 807             if (ctxt->error)
 808                 return;
 809             SKIP_BLANKS;
 810             if (CUR != ')') {
 811                 xsltGenericError(xsltGenericErrorContext,
 812                         "xsltCompileIdKeyPattern : ) expected\n");
 813                 ctxt->error = 1;
 814                 return;
 815             }
 816         }
 817         NEXT;
 818         PUSH(XSLT_OP_PI, lit, NULL);
 819     } else if (xmlStrEqual(name, (const xmlChar *)"text")) {
 820         NEXT;
 821         SKIP_BLANKS;
 822         if (CUR != ')') {
 823             xsltGenericError(xsltGenericErrorContext,
 824                     "xsltCompileIdKeyPattern : ) expected\n");
 825             ctxt->error = 1;
 826             return;
 827         }
 828         NEXT;
 829         PUSH(XSLT_OP_TEXT, NULL, NULL);
 830     } else if (xmlStrEqual(name, (const xmlChar *)"comment")) {
 831         NEXT;
 832         SKIP_BLANKS;
 833         if (CUR != ')') {
 834             xsltGenericError(xsltGenericErrorContext,
 835                     "xsltCompileIdKeyPattern : ) expected\n");
 836             ctxt->error = 1;
 837             return;
 838         }
 839         NEXT;
 840         PUSH(XSLT_OP_COMMENT, NULL, NULL);
 841     } else if (xmlStrEqual(name, (const xmlChar *)"node")) {
 842         NEXT;
 843         SKIP_BLANKS;
 844         if (CUR != ')') {
 845             xsltGenericError(xsltGenericErrorContext,
 846                     "xsltCompileIdKeyPattern : ) expected\n");
 847             ctxt->error = 1;
 848             return;
 849         }
 850         NEXT;
 851         PUSH(XSLT_OP_NODE, NULL, NULL);
 852     } else if (aid) {
 853         xsltGenericError(xsltGenericErrorContext,
 854             "xsltCompileIdKeyPattern : expecting 'key' or 'id' or node type\n");
 855         ctxt->error = 1;
 856         return;
 857     } else {
 858         xsltGenericError(xsltGenericErrorContext,
 859             "xsltCompileIdKeyPattern : node type\n");
 860         ctxt->error = 1;
 861         return;
 862     }
 863 error:
 864     if (name != NULL)
 865         xmlFree(name);
 866 }
 867
 868 /**
 869  * xsltCompileStepPattern:
 870  * @comp:  the compilation context
 871  * @token:  a posible precompiled name
 872  *
 873  * Compile the XSLT StepPattern and generates a precompiled
 874  * form suitable for fast matching.
 875  *
 876  * [5] StepPattern ::= ChildOrAttributeAxisSpecifier NodeTest Predicate*
 877  * [6] ChildOrAttributeAxisSpecifier ::= AbbreviatedAxisSpecifier
 878  *                                     | ('child' | 'attribute') '::'
 879  * from XPath
 880  * [7]  NodeTest ::= NameTest
 881  *                 | NodeType '(' ')'
 882  *                 | 'processing-instruction' '(' Literal ')'
 883  * [8] Predicate ::= '[' PredicateExpr ']'
 884  * [9] PredicateExpr ::= Expr
 885  * [13] AbbreviatedAxisSpecifier ::= '@'?
 886  * [37] NameTest ::= '*' | NCName ':' '*' | QName
 887  */
 888
 889 void
 890 xsltCompileStepPattern(xsltParserContextPtr ctxt, xmlChar *token) {
 891     xmlChar *name = NULL;
 892
 893     SKIP_BLANKS;
 894     if ((token == NULL) && (CUR == '@')) {
 895         NEXT;
 896         if (CUR == '*') {
 897             NEXT;
 898             PUSH(XSLT_OP_ATTR, NULL, NULL);
 899             return;
 900         }
 901         token = xsltScanName(ctxt);
 902         if (token == NULL) {
 903             xsltGenericError(xsltGenericErrorContext,
 904                     "xsltCompileStepPattern : Name expected\n");
 905             ctxt->error = 1;
 906             goto error;
 907         }
 908         PUSH(XSLT_OP_ATTR, token, NULL);
 909         return;
 910     }
 911     if (token == NULL)
 912         token = xsltScanName(ctxt);
 913     if (token == NULL) {
 914         if (CUR == '*') {
 915             NEXT;
 916             PUSH(XSLT_OP_ALL, token, NULL);
 917             goto parse_predicate;
 918         } else {
 919             xsltGenericError(xsltGenericErrorContext,
 920                     "xsltCompileStepPattern : Name expected\n");
 921             ctxt->error = 1;
 922             goto error;
 923         }
 924     }
 925     SKIP_BLANKS;
 926     if (CUR == '(') {
 927         xsltCompileIdKeyPattern(ctxt, token, 0);
 928         if (ctxt->error)
 929             goto error;
 930     } else if (CUR == ':') {
 931         NEXT;
 932         if (NXT(1) != ':') {
 933             xsltGenericError(xsltGenericErrorContext,
 934                     "xsltCompileStepPattern : sequence '::' expected\n");
 935             ctxt->error = 1;
 936             goto error;
 937         }
 938         NEXT;
 939         if (xmlStrEqual(token, (const xmlChar *) "child")) {
 940             /* TODO: handle namespace */
 941             name = xsltScanName(ctxt);
 942             if (name == NULL) {
 943                 xsltGenericError(xsltGenericErrorContext,
 944                         "xsltCompileStepPattern : QName expected\n");
 945                 ctxt->error = 1;
 946                 goto error;
 947             }
 948             PUSH(XSLT_OP_CHILD, name, NULL);
 949         } else if (xmlStrEqual(token, (const xmlChar *) "attribute")) {
 950             /* TODO: handle namespace */
 951             name = xsltScanName(ctxt);
 952             if (name == NULL) {
 953                 xsltGenericError(xsltGenericErrorContext,
 954                         "xsltCompileStepPattern : QName expected\n");
 955                 ctxt->error = 1;
 956                 goto error;
 957             }
 958             PUSH(XSLT_OP_ATTR, name, NULL);
 959         } else {
 960             xsltGenericError(xsltGenericErrorContext,
 961                 "xsltCompileStepPattern : 'child' or 'attribute' expected\n");
 962             ctxt->error = 1;
 963             goto error;
 964         }
 965         xmlFree(token);
 966     } else if (CUR == '*') {
 967         NEXT;
 968         PUSH(XSLT_OP_ALL, token, NULL);
 969     } else {
 970         /* TODO: handle namespace */
 971         PUSH(XSLT_OP_ELEM, token, NULL);
 972     }
 973 parse_predicate:
 974     SKIP_BLANKS;
 975     while (CUR == '[') {
 976         const xmlChar *q;
 977         xmlChar *ret = NULL;
 978
 979         NEXT;
 980         q = CUR_PTR;
 981         /* TODO: avoid breaking in strings ... */
 982         while ((IS_CHAR(CUR)) && (CUR != ']'))
 983             NEXT;
 984         if (!IS_CHAR(CUR)) {
 985             xsltGenericError(xsltGenericErrorContext,
 986                     "xsltCompileStepPattern : ']' expected\n");
 987             ctxt->error = 1;
 988             goto error;
 989         }
 990         ret = xmlStrndup(q, CUR_PTR - q);
 991         PUSH(XSLT_OP_PREDICATE, ret, NULL);
 992         /* push the predicate lower than local test */
 993         SWAP();
 994         NEXT;
 995     }
 996     return;
 997 error:
 998     if (token != NULL)
 999         xmlFree(token);
1000     if (name != NULL)
1001         xmlFree(name);
1002 }
1003
1004 /**
1005  * xsltCompileRelativePathPattern:
1006  * @comp:  the compilation context
1007  * @token:  a posible precompiled name
1008  *
1009  * Compile the XSLT RelativePathPattern and generates a precompiled
1010  * form suitable for fast matching.
1011  *
1012  * [4] RelativePathPattern ::= StepPattern
1013  *                           | RelativePathPattern '/' StepPattern
1014  *                           | RelativePathPattern '//' StepPattern
1015  */
1016 void
1017 xsltCompileRelativePathPattern(xsltParserContextPtr ctxt, xmlChar *token) {
1018     xsltCompileStepPattern(ctxt, token);
1019     if (ctxt->error)
1020         goto error;
1021     SKIP_BLANKS;
1022     while ((CUR != 0) && (CUR != '|')) {
1023         if ((CUR == '/') && (NXT(1) == '/')) {
1024             PUSH(XSLT_OP_ANCESTOR, NULL, NULL);
1025             NEXT;
1026             NEXT;
1027             SKIP_BLANKS;
1028             xsltCompileStepPattern(ctxt, NULL);
1029         } else if (CUR == '/') {
1030             PUSH(XSLT_OP_PARENT, NULL, NULL);
1031             NEXT;
1032             SKIP_BLANKS;
1033             if ((CUR != 0) || (CUR == '|')) {
1034                 xsltCompileRelativePathPattern(ctxt, NULL);
1035             }
1036         } else {
1037             ctxt->error = 1;
1038         }
1039         if (ctxt->error)
1040             goto error;
1041         SKIP_BLANKS;
1042     }
1043 error:
1044     return;
1045 }
1046
1047 /**
1048  * xsltCompileLocationPathPattern:
1049  * @comp:  the compilation context
1050  *
1051  * Compile the XSLT LocationPathPattern and generates a precompiled
1052  * form suitable for fast matching.
1053  *
1054  * [2] LocationPathPattern ::= '/' RelativePathPattern?
1055  *                           | IdKeyPattern (('/' | '//') RelativePathPattern)?
1056  *                           | '//'? RelativePathPattern
1057  */
1058 void
1059 xsltCompileLocationPathPattern(xsltParserContextPtr ctxt) {
1060     SKIP_BLANKS;
1061     if ((CUR == '/') && (NXT(1) == '/')) {
1062         /*
1063          * since we reverse the query
1064          * a leading // can be safely ignored
1065          */
1066         NEXT;
1067         NEXT;
1068         xsltCompileRelativePathPattern(ctxt, NULL);
1069     } else if (CUR == '/') {
1070         /*
1071          * We need to find root as the parent
1072          */
1073         NEXT;
1074         SKIP_BLANKS;
1075         PUSH(XSLT_OP_ROOT, NULL, NULL);
1076         if ((CUR != 0) || (CUR == '|')) {
1077             PUSH(XSLT_OP_PARENT, NULL, NULL);
1078             xsltCompileRelativePathPattern(ctxt, NULL);
1079         }
1080     } else if (CUR == '*') {
1081         xsltCompileRelativePathPattern(ctxt, NULL);
1082     } else if (CUR == '@') {
1083         xsltCompileRelativePathPattern(ctxt, NULL);
1084     } else {
1085         xmlChar *name;
1086         name = xsltScanName(ctxt);
1087         if (name == NULL) {
1088             xsltGenericError(xsltGenericErrorContext,
1089                     "xsltCompileLocationPathPattern : Name expected\n");
1090             ctxt->error = 1;
1091             return;
1092         }
1093         SKIP_BLANKS;
1094         if (CUR == '(') {
1095             xsltCompileIdKeyPattern(ctxt, name, 1);
1096             if ((CUR == '/') && (NXT(1) == '/')) {
1097                 PUSH(XSLT_OP_ANCESTOR, NULL, NULL);
1098                 NEXT;
1099                 NEXT;
1100                 SKIP_BLANKS;
1101                 xsltCompileRelativePathPattern(ctxt, NULL);
1102             } else if (CUR == '/') {
1103                 PUSH(XSLT_OP_PARENT, NULL, NULL);
1104                 NEXT;
1105                 SKIP_BLANKS;
1106                 xsltCompileRelativePathPattern(ctxt, NULL);
1107             }
1108             return;
1109         }
1110         xsltCompileRelativePathPattern(ctxt, name);
1111     }
1112 error:
1113     return;
1114 }
1115
1116 /**
1117  * xsltCompilePattern:
1118  * @pattern an XSLT pattern
1119  *
1120  * Compile the XSLT pattern and generates a list of precompiled form suitable
1121  * for fast matching.
1122  *
1123  * [1] Pattern ::= LocationPathPattern | Pattern '|' LocationPathPattern
1124  *
1125  * Returns the generated pattern list or NULL in case of failure
1126  */
1127
1128 xsltCompMatchPtr
1129 xsltCompilePattern(const xmlChar *pattern) {
1130     xsltParserContextPtr ctxt = NULL;
1131     xsltCompMatchPtr element, first = NULL, previous = NULL;
1132     int current, start, end;
1133
1134     if (pattern == NULL) {
1135         xsltGenericError(xsltGenericErrorContext,
1136                          "xsltCompilePattern : NULL pattern\n");
1137         return(NULL);
1138     }
1139
1140 #ifdef DEBUG_PARSING
1141     xsltGenericDebug(xsltGenericDebugContext,
1142                      "xsltCompilePattern : parsing '%s'\n", pattern);
1143 #endif
1144
1145     ctxt = xsltNewParserContext();
1146     if (ctxt == NULL)
1147         return(NULL);
1148     current = end = 0;
1149     while (pattern[current] != 0) {
1150         start = current;
1151         while (IS_BLANK(pattern[current]))
1152             current++;
1153         end = current;
1154         while ((pattern[end] != 0) && (pattern[end] != '|'))
1155             end++;
1156         if (current == end) {
1157             xsltGenericError(xsltGenericErrorContext,
1158                              "xsltCompilePattern : NULL pattern\n");
1159             goto error;
1160         }
1161         element = xsltNewCompMatch();
1162         if (element == NULL) {
1163             goto error;
1164         }
1165         if (first == NULL)
1166             first = element;
1167         else if (previous != NULL)
1168             previous->next = element;
1169         previous = element;
1170
1171         ctxt->comp = element;
1172         ctxt->base = xmlStrndup(&pattern[start], end - start);
1173         ctxt->cur = &(ctxt->base)[current - start];
1174         xsltCompileLocationPathPattern(ctxt);
1175         if (ctxt->base)
1176             xmlFree((xmlChar *)ctxt->base);
1177         if (ctxt->error)
1178             goto error;
1179
1180         /*
1181          * Reverse for faster interpretation.
1182          */
1183         xsltReverseCompMatch(element);
1184
1185         /*
1186          * Set-up the priority
1187          */
1188         if (((element->steps[0].op == XSLT_OP_ELEM) ||
1189              (element->steps[0].op == XSLT_OP_ATTR)) &&
1190             (element->steps[0].value != NULL) &&
1191             (element->steps[1].op == XSLT_OP_END)) {
1192             element->priority = 0;
1193         } else if ((element->steps[0].op == XSLT_OP_PI) &&
1194                    (element->steps[0].value != NULL) &&
1195                    (element->steps[1].op == XSLT_OP_END)) {
1196             element->priority = 0;
1197         } else if ((element->steps[0].op == XSLT_OP_NS) &&
1198                    (element->steps[0].value != NULL) &&
1199                    (element->steps[1].op == XSLT_OP_END)) {
1200             element->priority = -0.25;
1201         } else if (((element->steps[0].op == XSLT_OP_PI) ||
1202                     (element->steps[0].op == XSLT_OP_TEXT) ||
1203                     (element->steps[0].op == XSLT_OP_ALL) ||
1204                     (element->steps[0].op == XSLT_OP_NODE) ||
1205                     (element->steps[0].op == XSLT_OP_COMMENT)) &&
1206                    (element->steps[1].op == XSLT_OP_END)) {
1207             element->priority = -0.5;
1208         } else {
1209             element->priority = 0.5;
1210         }
1211         if (pattern[end] == '|')
1212             end++;
1213         current = end;
1214     }
1215     if (end == 0) {
1216         xsltGenericError(xsltGenericErrorContext,
1217                          "xsltCompilePattern : NULL pattern\n");
1218         goto error;
1219     }
1220
1221     xsltFreeParserContext(ctxt);
1222     return(first);
1223
1224 error:
1225     if (ctxt != NULL)
1226         xsltFreeParserContext(ctxt);
1227     if (first != NULL)
1228         xsltFreeCompMatchList(first);
1229     return(NULL);
1230 }
1231
1232 /************************************************************************
1233  *                                                                      *
1234  *                      Module interfaces                               *
1235  *                                                                      *
1236  ************************************************************************/
1237
1238 /**
1239  * xsltAddTemplate:
1240  * @style: an XSLT stylesheet
1241  * @cur: an XSLT template
1242  * @mode:  the mode name or NULL
1243  * @modeURI:  the mode URI or NULL
1244  *
1245  * Register the XSLT pattern associated to @cur
1246  *
1247  * Returns -1 in case of error, 0 otherwise
1248  */
1249 int
1250 xsltAddTemplate(xsltStylesheetPtr style, xsltTemplatePtr cur,
1251                 const xmlChar *mode, const xmlChar *modeURI) {
1252     xsltCompMatchPtr pat, list, *top = NULL, next;
1253     const xmlChar *name = NULL;
1254
1255     if ((style == NULL) || (cur == NULL) || (cur->match == NULL))
1256         return(-1);
1257
1258     pat = xsltCompilePattern(cur->match);
1259     while (pat) {
1260         next = pat->next;
1261         pat->next = NULL;
1262
1263         pat->template = cur;
1264         if (mode != NULL)
1265             pat->mode = xmlStrdup(mode);
1266         if (modeURI != NULL)
1267             pat->modeURI = xmlStrdup(modeURI);
1268         if (pat->priority != XSLT_PAT_NO_PRIORITY)
1269             cur->priority = pat->priority;
1270         else
1271             pat->priority = cur->priority;
1272
1273         /*
1274          * insert it in the hash table list corresponding to its lookup name
1275          */
1276         switch (pat->steps[0].op) {
1277         case XSLT_OP_ATTR:
1278             if (pat->steps[0].value != NULL)
1279                 name = pat->steps[0].value;
1280             else
1281                 top = (xsltCompMatchPtr *) &(style->attrMatch);
1282             break;
1283         case XSLT_OP_ELEM:
1284         case XSLT_OP_CHILD:
1285         case XSLT_OP_PARENT:
1286         case XSLT_OP_ANCESTOR:
1287         case XSLT_OP_NS:
1288             name = pat->steps[0].value;
1289             break;
1290         case XSLT_OP_ROOT:
1291             top = (xsltCompMatchPtr *) &(style->rootMatch);
1292             break;
1293         case XSLT_OP_KEY:
1294             top = (xsltCompMatchPtr *) &(style->keyMatch);
1295             break;
1296         case XSLT_OP_ID:
1297             /* TODO optimize ID !!! */
1298         case XSLT_OP_ALL:
1299             top = (xsltCompMatchPtr *) &(style->elemMatch);
1300             break;
1301         case XSLT_OP_END:
1302         case XSLT_OP_PREDICATE:
1303             xsltGenericError(xsltGenericErrorContext,
1304                              "xsltAddTemplate: invalid compiled pattern\n");
1305             xsltFreeCompMatch(pat);
1306             return(-1);
1307             /*
1308              * TODO: some flags at the top level about type based patterns
1309              *       would be faster than inclusion in the hash table.
1310              */
1311         case XSLT_OP_PI:
1312             if (pat->steps[0].value != NULL)
1313                 name = pat->steps[0].value;
1314             else
1315                 top = (xsltCompMatchPtr *) &(style->piMatch);
1316             break;
1317         case XSLT_OP_COMMENT:
1318             top = (xsltCompMatchPtr *) &(style->commentMatch);
1319             break;
1320         case XSLT_OP_TEXT:
1321             top = (xsltCompMatchPtr *) &(style->textMatch);
1322             break;
1323         case XSLT_OP_NODE:
1324             if (pat->steps[0].value != NULL)
1325                 name = pat->steps[0].value;
1326             else
1327                 top = (xsltCompMatchPtr *) &(style->elemMatch);
1328
1329             break;
1330         }
1331         if (name != NULL) {
1332             if (style->templatesHash == NULL) {
1333                 style->templatesHash = xmlHashCreate(1024);
1334                 if (style->templatesHash == NULL) {
1335                     xsltFreeCompMatch(pat);
1336                     return(-1);
1337                 }
1338 #ifdef DEBUG_PARSING
1339                 xsltGenericDebug(xsltGenericDebugContext,
1340                                  "xsltAddTemplate: created template hash\n");
1341 #endif
1342                 xmlHashAddEntry3(style->templatesHash, name, mode, modeURI, pat);
1343 #ifdef DEBUG_PARSING
1344                 xsltGenericDebug(xsltGenericDebugContext,
1345                                  "xsltAddTemplate: added new hash %s\n", name);
1346 #endif
1347             } else {
1348                 list = (xsltCompMatchPtr) xmlHashLookup3(style->templatesHash,
1349                                                          name, mode, modeURI);
1350                 if (list == NULL) {
1351                     xmlHashAddEntry3(style->templatesHash, name,
1352                                      mode, modeURI, pat);
1353 #ifdef DEBUG_PARSING
1354                     xsltGenericDebug(xsltGenericDebugContext,
1355                                      "xsltAddTemplate: added new hash %s\n", name);
1356 #endif
1357                 } else {
1358                     /*
1359                      * Note '<=' since one must choose among the matching
1360                      * template rules that are left, the one that occurs
1361                      * last in the stylesheet
1362                      */
1363                     if (list->priority <= pat->priority) {
1364                         pat->next = list;
1365                         xmlHashUpdateEntry3(style->templatesHash, name,
1366                                             mode, modeURI, pat, NULL);
1367 #ifdef DEBUG_PARSING
1368                         xsltGenericDebug(xsltGenericDebugContext,
1369                                          "xsltAddTemplate: added head hash for %s\n", name);
1370 #endif
1371                     } else {
1372                         while (list->next != NULL) {
1373                             if (list->next->priority <= pat->priority)
1374                                 break;
1375                             list = list->next;
1376                         }
1377                         pat->next = list->next;
1378                         list->next = pat;
1379                     }
1380                 }
1381             }
1382         } else if (top != NULL) {
1383             list = *top;
1384             if (list == NULL) {
1385                 *top = pat;
1386                 pat->next = NULL;
1387             } else if (list->priority <= pat->priority) {
1388                 pat->next = list;
1389                 *top = pat;
1390             } else {
1391                 while (list->next != NULL) {
1392                     if (list->next->priority <= pat->priority)
1393                         break;
1394                     list = list->next;
1395                 }
1396                 pat->next = list->next;
1397                 list->next = pat;
1398             }
1399         } else {
1400             xsltGenericError(xsltGenericErrorContext,
1401                              "xsltAddTemplate: invalid compiled pattern\n");
1402             xsltFreeCompMatch(pat);
1403             return(-1);
1404         }
1405         pat = next;
1406     }
1407     return(0);
1408 }
1409
1410 /**
1411  * xsltGetTemplate:
1412  * @ctxt:  a XSLT process context
1413  * @mode:  the mode
1414  * @style:  the current style
1415  *
1416  * Finds the template applying to this node, if @style is non-NULL
1417  * it means one need to look for the next imported template in scope.
1418  *
1419  * Returns the xsltTemplatePtr or NULL if not found
1420  */
1421 xsltTemplatePtr
1422 xsltGetTemplate(xsltTransformContextPtr ctxt, xmlNodePtr node,
1423                 xsltStylesheetPtr style) {
1424     xsltStylesheetPtr curstyle;
1425     xsltTemplatePtr ret = NULL;
1426     const xmlChar *name = NULL;
1427     xsltCompMatchPtr list = NULL;
1428
1429     if ((ctxt == NULL) || (node == NULL))
1430         return(NULL);
1431
1432     if (style == NULL) {
1433         curstyle = ctxt->style;
1434     } else {
1435         curstyle = xsltNextImport(style);
1436     }
1437
1438     while ((curstyle != NULL) && (curstyle != style)) {
1439         /* TODO : handle IDs/keys here ! */
1440         if (curstyle->templatesHash != NULL) {
1441             /*
1442              * Use the top name as selector
1443              */
1444             switch (node->type) {
1445                 case XML_ELEMENT_NODE:
1446                 case XML_ATTRIBUTE_NODE:
1447                 case XML_PI_NODE:
1448                     name = node->name;
1449                     break;
1450                 case XML_DOCUMENT_NODE:
1451                 case XML_HTML_DOCUMENT_NODE:
1452                 case XML_TEXT_NODE:
1453                 case XML_CDATA_SECTION_NODE:
1454                 case XML_COMMENT_NODE:
1455                 case XML_ENTITY_REF_NODE:
1456                 case XML_ENTITY_NODE:
1457                 case XML_DOCUMENT_TYPE_NODE:
1458                 case XML_DOCUMENT_FRAG_NODE:
1459                 case XML_NOTATION_NODE:
1460                 case XML_DTD_NODE:
1461                 case XML_ELEMENT_DECL:
1462                 case XML_ATTRIBUTE_DECL:
1463                 case XML_ENTITY_DECL:
1464                 case XML_NAMESPACE_DECL:
1465                 case XML_XINCLUDE_START:
1466                 case XML_XINCLUDE_END:
1467                     break;
1468                 default:
1469                     return(NULL);
1470
1471             }
1472         }
1473         if (name != NULL) {
1474             /*
1475              * find the list of appliable expressions based on the name
1476              */
1477             list = (xsltCompMatchPtr) xmlHashLookup3(curstyle->templatesHash,
1478                                              name, ctxt->mode, ctxt->modeURI);
1479         }
1480         while (list != NULL) {
1481             if (xsltTestCompMatch(ctxt, list, node,
1482                                   ctxt->mode, ctxt->modeURI)) {
1483                 ret = list->template;
1484                 break;
1485             }
1486             list = list->next;
1487         }
1488         list = NULL;
1489
1490         /*
1491          * find alternate generic matches
1492          */
1493         switch (node->type) {
1494             case XML_ELEMENT_NODE:
1495                 list = curstyle->elemMatch;
1496                 break;
1497             case XML_ATTRIBUTE_NODE:
1498                 list = curstyle->attrMatch;
1499                 break;
1500             case XML_PI_NODE:
1501                 list = curstyle->piMatch;
1502                 break;
1503             case XML_DOCUMENT_NODE:
1504             case XML_HTML_DOCUMENT_NODE:
1505                 list = curstyle->rootMatch;
1506                 break;
1507             case XML_TEXT_NODE:
1508             case XML_CDATA_SECTION_NODE:
1509                 list = curstyle->textMatch;
1510                 break;
1511             case XML_COMMENT_NODE:
1512                 list = curstyle->commentMatch;
1513                 break;
1514             case XML_ENTITY_REF_NODE:
1515             case XML_ENTITY_NODE:
1516             case XML_DOCUMENT_TYPE_NODE:
1517             case XML_DOCUMENT_FRAG_NODE:
1518             case XML_NOTATION_NODE:
1519             case XML_DTD_NODE:
1520             case XML_ELEMENT_DECL:
1521             case XML_ATTRIBUTE_DECL:
1522             case XML_ENTITY_DECL:
1523             case XML_NAMESPACE_DECL:
1524             case XML_XINCLUDE_START:
1525             case XML_XINCLUDE_END:
1526                 break;
1527             default:
1528                 break;
1529
1530         }
1531         while ((list != NULL) &&
1532                ((ret == NULL)  || (list->priority > ret->priority))) {
1533             if (xsltTestCompMatch(ctxt, list, node,
1534                                   ctxt->mode, ctxt->modeURI)) {
1535                 ret = list->template;
1536                 break;
1537             }
1538             list = list->next;
1539         }
1540         if (node->_private != NULL) {
1541             list = curstyle->keyMatch;
1542             while ((list != NULL) &&
1543                    ((ret == NULL)  || (list->priority > ret->priority))) {
1544                 if (xsltTestCompMatch(ctxt, list, node,
1545                                       ctxt->mode, ctxt->modeURI)) {
1546                     ret = list->template;
1547                     break;
1548                 }
1549                 list = list->next;
1550             }
1551         }
1552
1553         if (ret != NULL)
1554             return(ret);
1555
1556         /*
1557          * Cycle on next curstylesheet import.
1558          */
1559         curstyle = xsltNextImport(curstyle);
1560     }
1561     return(NULL);
1562 }
1563
1564
1565 /**
1566  * xsltFreeTemplateHashes:
1567  * @style: an XSLT stylesheet
1568  *
1569  * Free up the memory used by xsltAddTemplate/xsltGetTemplate mechanism
1570  */
1571 void
1572 xsltFreeTemplateHashes(xsltStylesheetPtr style) {
1573     if (style->templatesHash != NULL)
1574         xmlHashFree((xmlHashTablePtr) style->templatesHash,
1575                     (xmlHashDeallocator) xsltFreeCompMatchList);
1576     if (style->rootMatch != NULL)
1577         xsltFreeCompMatchList(style->rootMatch);
1578     if (style->keyMatch != NULL)
1579         xsltFreeCompMatchList(style->keyMatch);
1580     if (style->elemMatch != NULL)
1581         xsltFreeCompMatchList(style->elemMatch);
1582     if (style->attrMatch != NULL)
1583         xsltFreeCompMatchList(style->attrMatch);
1584     if (style->parentMatch != NULL)
1585         xsltFreeCompMatchList(style->parentMatch);
1586     if (style->textMatch != NULL)
1587         xsltFreeCompMatchList(style->textMatch);
1588     if (style->piMatch != NULL)
1589         xsltFreeCompMatchList(style->piMatch);
1590     if (style->commentMatch != NULL)
1591         xsltFreeCompMatchList(style->commentMatch);
1592 }
1593
1594 /**
1595  * xsltMatchPattern
1596  * @node: a node in the source tree
1597  * @pattern: an XSLT pattern
1598  *
1599  * Determine if a node matches a pattern.
1600  */
1601 int
1602 xsltMatchPattern(xsltTransformContextPtr context,
1603                  xmlNodePtr node,
1604                  const xmlChar *pattern)
1605 {
1606     int match = 0;
1607     xsltCompMatchPtr first, comp;
1608
1609     if ((context != NULL) && (pattern != NULL)) {
1610         first = xsltCompilePattern(pattern);
1611         for (comp = first; comp != NULL; comp = comp->next) {
1612             match = xsltTestCompMatch(context, comp, node, NULL, NULL);
1613             if (match)
1614                 break; /* for */
1615         }
1616         if (first)
1617             xsltFreeCompMatchList(first);
1618     }
1619     return match;
1620 }
1621