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                 } else if ((select != NULL) && (select->op == XSLT_OP_ALL)) {
 516                     xmlNodePtr siblings = node->parent->children;
 517
 518                     while (siblings != NULL) {
 519                         if (siblings->type == XML_ELEMENT_NODE) {
 520                             len++;
 521                             if (siblings == node) {
 522                                 pos = len;
 523                             }
 524                         }
 525                         siblings = siblings->next;
 526                     }
 527                     if (pos != 0) {
 528                         ctxt->xpathCtxt->contextSize = len;
 529                         ctxt->xpathCtxt->proximityPosition = pos;
 530                     }
 531                 }
 532                 oldNode = ctxt->node;
 533                 ctxt->node = node;
 534
 535                 if ((step->value == NULL) ||
 536                     (!xsltEvalXPathPredicate(ctxt, step->value))) {
 537                     if (pos != 0) {
 538                         ctxt->xpathCtxt->contextSize = oldCS;
 539                         ctxt->xpathCtxt->proximityPosition = oldCP;
 540                     }
 541                     ctxt->node = oldNode;
 542                     return(0);
 543                 }
 544                 if (pos != 0) {
 545                     ctxt->xpathCtxt->contextSize = oldCS;
 546                     ctxt->xpathCtxt->proximityPosition = oldCP;
 547                 }
 548                 ctxt->node = oldNode;
 549                 break;
 550             }
 551             case XSLT_OP_PI:
 552                 if (node->type != XML_PI_NODE)
 553                     return(0);
 554                 if (step->value != NULL) {
 555                     if (!xmlStrEqual(step->value, node->name))
 556                         return(0);
 557                 }
 558                 break;
 559             case XSLT_OP_COMMENT:
 560                 if (node->type != XML_COMMENT_NODE)
 561                     return(0);
 562                 break;
 563             case XSLT_OP_TEXT:
 564                 if ((node->type != XML_TEXT_NODE) &&
 565                     (node->type != XML_CDATA_SECTION_NODE))
 566                     return(0);
 567                 break;
 568             case XSLT_OP_NODE:
 569                 switch (node->type) {
 570                     case XML_DOCUMENT_NODE:
 571                     case XML_HTML_DOCUMENT_NODE:
 572                     case XML_ELEMENT_NODE:
 573                     case XML_CDATA_SECTION_NODE:
 574                     case XML_PI_NODE:
 575                     case XML_COMMENT_NODE:
 576                     case XML_TEXT_NODE:
 577                     case XML_ATTRIBUTE_NODE:
 578                         break;
 579                     default:
 580                         return(0);
 581                 }
 582                 break;
 583         }
 584     }
 585     return(1);
 586 }
 587
 588 /**
 589  * xsltTestCompMatchList:
 590  * @ctxt:  a XSLT process context
 591  * @node: a node
 592  * @comp: the precompiled pattern list
 593  *
 594  * Test wether the node matches one of the patterns in the list
 595  *
 596  * Returns 1 if it matches, 0 if it doesn't and -1 in case of failure
 597  */
 598 int
 599 xsltTestCompMatchList(xsltTransformContextPtr ctxt, xmlNodePtr node,
 600                       xsltCompMatchPtr comp) {
 601     int ret;
 602
 603     if ((ctxt == NULL) || (node == NULL))
 604         return(-1);
 605     while (comp != NULL) {
 606         ret = xsltTestCompMatch(ctxt, comp, node, NULL, NULL);
 607         if (ret == 1)
 608             return(1);
 609         comp = comp->next;
 610     }
 611     return(0);
 612 }
 613
 614 /************************************************************************
 615  *                                                                      *
 616  *                      Dedicated parser for templates                  *
 617  *                                                                      *
 618  ************************************************************************/
 619
 620 #define CUR (*ctxt->cur)
 621 #define SKIP(val) ctxt->cur += (val)
 622 #define NXT(val) ctxt->cur[(val)]
 623 #define CUR_PTR ctxt->cur
 624
 625 #define SKIP_BLANKS                                                     \
 626     while (IS_BLANK(CUR)) NEXT
 627
 628 #define CURRENT (*ctxt->cur)
 629 #define NEXT ((*ctxt->cur) ?  ctxt->cur++: ctxt->cur)
 630
 631
 632 #define PUSH(op, val, val2)                                             \
 633     if (xsltCompMatchAdd(ctxt->comp, (op), (val), (val2))) goto error;
 634
 635 #define SWAP()                                          \
 636     xsltSwapTopCompMatch(ctxt->comp);
 637
 638 #define XSLT_ERROR(X)                                                   \
 639     { xsltError(ctxt, __FILE__, __LINE__, X);                   \
 640       ctxt->error = (X); return; }
 641
 642 #define XSLT_ERROR0(X)                                                  \
 643     { xsltError(ctxt, __FILE__, __LINE__, X);                   \
 644       ctxt->error = (X); return(0); }
 645
 646 /**
 647  * xsltScanLiteral:
 648  * @ctxt:  the XPath Parser context
 649  *
 650  * Parse an XPath Litteral:
 651  *
 652  * [29] Literal ::= '"' [^"]* '"'
 653  *                | "'" [^']* "'"
 654  *
 655  * Returns the Literal parsed or NULL
 656  */
 657
 658 xmlChar *
 659 xsltScanLiteral(xsltParserContextPtr ctxt) {
 660     const xmlChar *q;
 661     xmlChar *ret = NULL;
 662
 663     SKIP_BLANKS;
 664     if (CUR == '"') {
 665         NEXT;
 666         q = CUR_PTR;
 667         while ((IS_CHAR(CUR)) && (CUR != '"'))
 668             NEXT;
 669         if (!IS_CHAR(CUR)) {
 670             /* XP_ERROR(XPATH_UNFINISHED_LITERAL_ERROR); */
 671             ctxt->error = 1;
 672             return(NULL);
 673         } else {
 674             ret = xmlStrndup(q, CUR_PTR - q);
 675             NEXT;
 676         }
 677     } else if (CUR == '\'') {
 678         NEXT;
 679         q = CUR_PTR;
 680         while ((IS_CHAR(CUR)) && (CUR != '\''))
 681             NEXT;
 682         if (!IS_CHAR(CUR)) {
 683             /* XP_ERROR(XPATH_UNFINISHED_LITERAL_ERROR); */
 684             ctxt->error = 1;
 685             return(NULL);
 686         } else {
 687             ret = xmlStrndup(q, CUR_PTR - q);
 688             NEXT;
 689         }
 690     } else {
 691         /* XP_ERROR(XPATH_START_LITERAL_ERROR); */
 692         ctxt->error = 1;
 693         return(NULL);
 694     }
 695     return(ret);
 696 }
 697
 698 /**
 699  * xsltScanName:
 700  * @ctxt:  the XPath Parser context
 701  *
 702  * Trickery: parse an XML name but without consuming the input flow
 703  * Needed to avoid insanity in the parser state.
 704  *
 705  * [4] NameChar ::= Letter | Digit | '.' | '-' | '_' | ':' |
 706  *                  CombiningChar | Extender
 707  *
 708  * [5] Name ::= (Letter | '_' | ':') (NameChar)*
 709  *
 710  * [6] Names ::= Name (S Name)*
 711  *
 712  * Returns the Name parsed or NULL
 713  */
 714
 715 xmlChar *
 716 xsltScanName(xsltParserContextPtr ctxt) {
 717     xmlChar buf[XML_MAX_NAMELEN];
 718     int len = 0;
 719
 720     SKIP_BLANKS;
 721     if (!IS_LETTER(CUR) && (CUR != '_') &&
 722         (CUR != ':')) {
 723         return(NULL);
 724     }
 725
 726     while ((IS_LETTER(NXT(len))) || (IS_DIGIT(NXT(len))) ||
 727            (NXT(len) == '.') || (NXT(len) == '-') ||
 728            (NXT(len) == '_') || (NXT(len) == ':') ||
 729            (IS_COMBINING(NXT(len))) ||
 730            (IS_EXTENDER(NXT(len)))) {
 731         buf[len] = NXT(len);
 732         len++;
 733         if (len >= XML_MAX_NAMELEN) {
 734             xmlGenericError(xmlGenericErrorContext,
 735                "xmlScanName: reached XML_MAX_NAMELEN limit\n");
 736             while ((IS_LETTER(NXT(len))) || (IS_DIGIT(NXT(len))) ||
 737                    (NXT(len) == '.') || (NXT(len) == '-') ||
 738                    (NXT(len) == '_') || (NXT(len) == ':') ||
 739                    (IS_COMBINING(NXT(len))) ||
 740                    (IS_EXTENDER(NXT(len))))
 741                  len++;
 742             break;
 743         }
 744     }
 745     SKIP(len);
 746     return(xmlStrndup(buf, len));
 747 }
 748 /*
 749  * xsltCompileIdKeyPattern:
 750  * @comp:  the compilation context
 751  * @name:  a preparsed name
 752  * @aid:  whether id/key are allowed there
 753  *
 754  * Compile the XSLT LocationIdKeyPattern
 755  * [3] IdKeyPattern ::= 'id' '(' Literal ')'
 756  *                    | 'key' '(' Literal ',' Literal ')'
 757  *
 758  * also handle NodeType and PI from:
 759  *
 760  * [7]  NodeTest ::= NameTest
 761  *                 | NodeType '(' ')'
 762  *                 | 'processing-instruction' '(' Literal ')'
 763  */
 764 void
 765 xsltCompileIdKeyPattern(xsltParserContextPtr ctxt, xmlChar *name, int aid) {
 766     xmlChar *lit = NULL;
 767     xmlChar *lit2 = NULL;
 768
 769     if (CUR != '(') {
 770         xsltGenericError(xsltGenericErrorContext,
 771                 "xsltCompileIdKeyPattern : ( expected\n");
 772         ctxt->error = 1;
 773         return;
 774     }
 775     if ((aid) && (xmlStrEqual(name, (const xmlChar *)"id"))) {
 776         NEXT;
 777         SKIP_BLANKS;
 778         lit = xsltScanLiteral(ctxt);
 779         if (ctxt->error)
 780             return;
 781         SKIP_BLANKS;
 782         if (CUR != ')') {
 783             xsltGenericError(xsltGenericErrorContext,
 784                     "xsltCompileIdKeyPattern : ) expected\n");
 785             ctxt->error = 1;
 786             return;
 787         }
 788         NEXT;
 789         PUSH(XSLT_OP_ID, lit, NULL);
 790     } else if ((aid) && (xmlStrEqual(name, (const xmlChar *)"key"))) {
 791         NEXT;
 792         SKIP_BLANKS;
 793         lit = xsltScanLiteral(ctxt);
 794         if (ctxt->error)
 795             return;
 796         SKIP_BLANKS;
 797         if (CUR != ',') {
 798             xsltGenericError(xsltGenericErrorContext,
 799                     "xsltCompileIdKeyPattern : , expected\n");
 800             ctxt->error = 1;
 801             return;
 802         }
 803         NEXT;
 804         SKIP_BLANKS;
 805         lit2 = xsltScanLiteral(ctxt);
 806         if (ctxt->error)
 807             return;
 808         SKIP_BLANKS;
 809         if (CUR != ')') {
 810             xsltGenericError(xsltGenericErrorContext,
 811                     "xsltCompileIdKeyPattern : ) expected\n");
 812             ctxt->error = 1;
 813             return;
 814         }
 815         NEXT;
 816         /* TODO: support namespace in keys */
 817         PUSH(XSLT_OP_KEY, lit, lit2);
 818     } else if (xmlStrEqual(name, (const xmlChar *)"processing-instruction")) {
 819         NEXT;
 820         SKIP_BLANKS;
 821         if (CUR != ')') {
 822             lit = xsltScanLiteral(ctxt);
 823             if (ctxt->error)
 824                 return;
 825             SKIP_BLANKS;
 826             if (CUR != ')') {
 827                 xsltGenericError(xsltGenericErrorContext,
 828                         "xsltCompileIdKeyPattern : ) expected\n");
 829                 ctxt->error = 1;
 830                 return;
 831             }
 832         }
 833         NEXT;
 834         PUSH(XSLT_OP_PI, lit, NULL);
 835     } else if (xmlStrEqual(name, (const xmlChar *)"text")) {
 836         NEXT;
 837         SKIP_BLANKS;
 838         if (CUR != ')') {
 839             xsltGenericError(xsltGenericErrorContext,
 840                     "xsltCompileIdKeyPattern : ) expected\n");
 841             ctxt->error = 1;
 842             return;
 843         }
 844         NEXT;
 845         PUSH(XSLT_OP_TEXT, NULL, NULL);
 846     } else if (xmlStrEqual(name, (const xmlChar *)"comment")) {
 847         NEXT;
 848         SKIP_BLANKS;
 849         if (CUR != ')') {
 850             xsltGenericError(xsltGenericErrorContext,
 851                     "xsltCompileIdKeyPattern : ) expected\n");
 852             ctxt->error = 1;
 853             return;
 854         }
 855         NEXT;
 856         PUSH(XSLT_OP_COMMENT, NULL, NULL);
 857     } else if (xmlStrEqual(name, (const xmlChar *)"node")) {
 858         NEXT;
 859         SKIP_BLANKS;
 860         if (CUR != ')') {
 861             xsltGenericError(xsltGenericErrorContext,
 862                     "xsltCompileIdKeyPattern : ) expected\n");
 863             ctxt->error = 1;
 864             return;
 865         }
 866         NEXT;
 867         PUSH(XSLT_OP_NODE, NULL, NULL);
 868     } else if (aid) {
 869         xsltGenericError(xsltGenericErrorContext,
 870             "xsltCompileIdKeyPattern : expecting 'key' or 'id' or node type\n");
 871         ctxt->error = 1;
 872         return;
 873     } else {
 874         xsltGenericError(xsltGenericErrorContext,
 875             "xsltCompileIdKeyPattern : node type\n");
 876         ctxt->error = 1;
 877         return;
 878     }
 879 error:
 880     if (name != NULL)
 881         xmlFree(name);
 882 }
 883
 884 /**
 885  * xsltCompileStepPattern:
 886  * @comp:  the compilation context
 887  * @token:  a posible precompiled name
 888  *
 889  * Compile the XSLT StepPattern and generates a precompiled
 890  * form suitable for fast matching.
 891  *
 892  * [5] StepPattern ::= ChildOrAttributeAxisSpecifier NodeTest Predicate*
 893  * [6] ChildOrAttributeAxisSpecifier ::= AbbreviatedAxisSpecifier
 894  *                                     | ('child' | 'attribute') '::'
 895  * from XPath
 896  * [7]  NodeTest ::= NameTest
 897  *                 | NodeType '(' ')'
 898  *                 | 'processing-instruction' '(' Literal ')'
 899  * [8] Predicate ::= '[' PredicateExpr ']'
 900  * [9] PredicateExpr ::= Expr
 901  * [13] AbbreviatedAxisSpecifier ::= '@'?
 902  * [37] NameTest ::= '*' | NCName ':' '*' | QName
 903  */
 904
 905 void
 906 xsltCompileStepPattern(xsltParserContextPtr ctxt, xmlChar *token) {
 907     xmlChar *name = NULL;
 908
 909     SKIP_BLANKS;
 910     if ((token == NULL) && (CUR == '@')) {
 911         NEXT;
 912         if (CUR == '*') {
 913             NEXT;
 914             PUSH(XSLT_OP_ATTR, NULL, NULL);
 915             return;
 916         }
 917         token = xsltScanName(ctxt);
 918         if (token == NULL) {
 919             xsltGenericError(xsltGenericErrorContext,
 920                     "xsltCompileStepPattern : Name expected\n");
 921             ctxt->error = 1;
 922             goto error;
 923         }
 924         PUSH(XSLT_OP_ATTR, token, NULL);
 925         return;
 926     }
 927     if (token == NULL)
 928         token = xsltScanName(ctxt);
 929     if (token == NULL) {
 930         if (CUR == '*') {
 931             NEXT;
 932             PUSH(XSLT_OP_ALL, token, NULL);
 933             goto parse_predicate;
 934         } else {
 935             xsltGenericError(xsltGenericErrorContext,
 936                     "xsltCompileStepPattern : Name expected\n");
 937             ctxt->error = 1;
 938             goto error;
 939         }
 940     }
 941     SKIP_BLANKS;
 942     if (CUR == '(') {
 943         xsltCompileIdKeyPattern(ctxt, token, 0);
 944         if (ctxt->error)
 945             goto error;
 946     } else if (CUR == ':') {
 947         NEXT;
 948         if (NXT(1) != ':') {
 949             xsltGenericError(xsltGenericErrorContext,
 950                     "xsltCompileStepPattern : sequence '::' expected\n");
 951             ctxt->error = 1;
 952             goto error;
 953         }
 954         NEXT;
 955         if (xmlStrEqual(token, (const xmlChar *) "child")) {
 956             /* TODO: handle namespace */
 957             name = xsltScanName(ctxt);
 958             if (name == NULL) {
 959                 xsltGenericError(xsltGenericErrorContext,
 960                         "xsltCompileStepPattern : QName expected\n");
 961                 ctxt->error = 1;
 962                 goto error;
 963             }
 964             PUSH(XSLT_OP_CHILD, name, NULL);
 965         } else if (xmlStrEqual(token, (const xmlChar *) "attribute")) {
 966             /* TODO: handle namespace */
 967             name = xsltScanName(ctxt);
 968             if (name == NULL) {
 969                 xsltGenericError(xsltGenericErrorContext,
 970                         "xsltCompileStepPattern : QName expected\n");
 971                 ctxt->error = 1;
 972                 goto error;
 973             }
 974             PUSH(XSLT_OP_ATTR, name, NULL);
 975         } else {
 976             xsltGenericError(xsltGenericErrorContext,
 977                 "xsltCompileStepPattern : 'child' or 'attribute' expected\n");
 978             ctxt->error = 1;
 979             goto error;
 980         }
 981         xmlFree(token);
 982     } else if (CUR == '*') {
 983         NEXT;
 984         PUSH(XSLT_OP_ALL, token, NULL);
 985     } else {
 986         /* TODO: handle namespace */
 987         PUSH(XSLT_OP_ELEM, token, NULL);
 988     }
 989 parse_predicate:
 990     SKIP_BLANKS;
 991     while (CUR == '[') {
 992         const xmlChar *q;
 993         xmlChar *ret = NULL;
 994
 995         NEXT;
 996         q = CUR_PTR;
 997         /* TODO: avoid breaking in strings ... */
 998         while ((IS_CHAR(CUR)) && (CUR != ']'))
 999             NEXT;
1000         if (!IS_CHAR(CUR)) {
1001             xsltGenericError(xsltGenericErrorContext,
1002                     "xsltCompileStepPattern : ']' expected\n");
1003             ctxt->error = 1;
1004             goto error;
1005         }
1006         ret = xmlStrndup(q, CUR_PTR - q);
1007         PUSH(XSLT_OP_PREDICATE, ret, NULL);
1008         /* push the predicate lower than local test */
1009         SWAP();
1010         NEXT;
1011     }
1012     return;
1013 error:
1014     if (token != NULL)
1015         xmlFree(token);
1016     if (name != NULL)
1017         xmlFree(name);
1018 }
1019
1020 /**
1021  * xsltCompileRelativePathPattern:
1022  * @comp:  the compilation context
1023  * @token:  a posible precompiled name
1024  *
1025  * Compile the XSLT RelativePathPattern and generates a precompiled
1026  * form suitable for fast matching.
1027  *
1028  * [4] RelativePathPattern ::= StepPattern
1029  *                           | RelativePathPattern '/' StepPattern
1030  *                           | RelativePathPattern '//' StepPattern
1031  */
1032 void
1033 xsltCompileRelativePathPattern(xsltParserContextPtr ctxt, xmlChar *token) {
1034     xsltCompileStepPattern(ctxt, token);
1035     if (ctxt->error)
1036         goto error;
1037     SKIP_BLANKS;
1038     while ((CUR != 0) && (CUR != '|')) {
1039         if ((CUR == '/') && (NXT(1) == '/')) {
1040             PUSH(XSLT_OP_ANCESTOR, NULL, NULL);
1041             NEXT;
1042             NEXT;
1043             SKIP_BLANKS;
1044             xsltCompileStepPattern(ctxt, NULL);
1045         } else if (CUR == '/') {
1046             PUSH(XSLT_OP_PARENT, NULL, NULL);
1047             NEXT;
1048             SKIP_BLANKS;
1049             if ((CUR != 0) || (CUR == '|')) {
1050                 xsltCompileRelativePathPattern(ctxt, NULL);
1051             }
1052         } else {
1053             ctxt->error = 1;
1054         }
1055         if (ctxt->error)
1056             goto error;
1057         SKIP_BLANKS;
1058     }
1059 error:
1060     return;
1061 }
1062
1063 /**
1064  * xsltCompileLocationPathPattern:
1065  * @comp:  the compilation context
1066  *
1067  * Compile the XSLT LocationPathPattern and generates a precompiled
1068  * form suitable for fast matching.
1069  *
1070  * [2] LocationPathPattern ::= '/' RelativePathPattern?
1071  *                           | IdKeyPattern (('/' | '//') RelativePathPattern)?
1072  *                           | '//'? RelativePathPattern
1073  */
1074 void
1075 xsltCompileLocationPathPattern(xsltParserContextPtr ctxt) {
1076     SKIP_BLANKS;
1077     if ((CUR == '/') && (NXT(1) == '/')) {
1078         /*
1079          * since we reverse the query
1080          * a leading // can be safely ignored
1081          */
1082         NEXT;
1083         NEXT;
1084         xsltCompileRelativePathPattern(ctxt, NULL);
1085     } else if (CUR == '/') {
1086         /*
1087          * We need to find root as the parent
1088          */
1089         NEXT;
1090         SKIP_BLANKS;
1091         PUSH(XSLT_OP_ROOT, NULL, NULL);
1092         if ((CUR != 0) || (CUR == '|')) {
1093             PUSH(XSLT_OP_PARENT, NULL, NULL);
1094             xsltCompileRelativePathPattern(ctxt, NULL);
1095         }
1096     } else if (CUR == '*') {
1097         xsltCompileRelativePathPattern(ctxt, NULL);
1098     } else if (CUR == '@') {
1099         xsltCompileRelativePathPattern(ctxt, NULL);
1100     } else {
1101         xmlChar *name;
1102         name = xsltScanName(ctxt);
1103         if (name == NULL) {
1104             xsltGenericError(xsltGenericErrorContext,
1105                     "xsltCompileLocationPathPattern : Name expected\n");
1106             ctxt->error = 1;
1107             return;
1108         }
1109         SKIP_BLANKS;
1110         if (CUR == '(') {
1111             xsltCompileIdKeyPattern(ctxt, name, 1);
1112             if ((CUR == '/') && (NXT(1) == '/')) {
1113                 PUSH(XSLT_OP_ANCESTOR, NULL, NULL);
1114                 NEXT;
1115                 NEXT;
1116                 SKIP_BLANKS;
1117                 xsltCompileRelativePathPattern(ctxt, NULL);
1118             } else if (CUR == '/') {
1119                 PUSH(XSLT_OP_PARENT, NULL, NULL);
1120                 NEXT;
1121                 SKIP_BLANKS;
1122                 xsltCompileRelativePathPattern(ctxt, NULL);
1123             }
1124             return;
1125         }
1126         xsltCompileRelativePathPattern(ctxt, name);
1127     }
1128 error:
1129     return;
1130 }
1131
1132 /**
1133  * xsltCompilePattern:
1134  * @pattern an XSLT pattern
1135  *
1136  * Compile the XSLT pattern and generates a list of precompiled form suitable
1137  * for fast matching.
1138  *
1139  * [1] Pattern ::= LocationPathPattern | Pattern '|' LocationPathPattern
1140  *
1141  * Returns the generated pattern list or NULL in case of failure
1142  */
1143
1144 xsltCompMatchPtr
1145 xsltCompilePattern(const xmlChar *pattern) {
1146     xsltParserContextPtr ctxt = NULL;
1147     xsltCompMatchPtr element, first = NULL, previous = NULL;
1148     int current, start, end;
1149
1150     if (pattern == NULL) {
1151         xsltGenericError(xsltGenericErrorContext,
1152                          "xsltCompilePattern : NULL pattern\n");
1153         return(NULL);
1154     }
1155
1156 #ifdef DEBUG_PARSING
1157     xsltGenericDebug(xsltGenericDebugContext,
1158                      "xsltCompilePattern : parsing '%s'\n", pattern);
1159 #endif
1160
1161     ctxt = xsltNewParserContext();
1162     if (ctxt == NULL)
1163         return(NULL);
1164     current = end = 0;
1165     while (pattern[current] != 0) {
1166         start = current;
1167         while (IS_BLANK(pattern[current]))
1168             current++;
1169         end = current;
1170         while ((pattern[end] != 0) && (pattern[end] != '|'))
1171             end++;
1172         if (current == end) {
1173             xsltGenericError(xsltGenericErrorContext,
1174                              "xsltCompilePattern : NULL pattern\n");
1175             goto error;
1176         }
1177         element = xsltNewCompMatch();
1178         if (element == NULL) {
1179             goto error;
1180         }
1181         if (first == NULL)
1182             first = element;
1183         else if (previous != NULL)
1184             previous->next = element;
1185         previous = element;
1186
1187         ctxt->comp = element;
1188         ctxt->base = xmlStrndup(&pattern[start], end - start);
1189         ctxt->cur = &(ctxt->base)[current - start];
1190         xsltCompileLocationPathPattern(ctxt);
1191         if (ctxt->base)
1192             xmlFree((xmlChar *)ctxt->base);
1193         if (ctxt->error)
1194             goto error;
1195
1196         /*
1197          * Reverse for faster interpretation.
1198          */
1199         xsltReverseCompMatch(element);
1200
1201         /*
1202          * Set-up the priority
1203          */
1204         if (((element->steps[0].op == XSLT_OP_ELEM) ||
1205              (element->steps[0].op == XSLT_OP_ATTR)) &&
1206             (element->steps[0].value != NULL) &&
1207             (element->steps[1].op == XSLT_OP_END)) {
1208             element->priority = 0;
1209         } else if ((element->steps[0].op == XSLT_OP_PI) &&
1210                    (element->steps[0].value != NULL) &&
1211                    (element->steps[1].op == XSLT_OP_END)) {
1212             element->priority = 0;
1213         } else if ((element->steps[0].op == XSLT_OP_NS) &&
1214                    (element->steps[0].value != NULL) &&
1215                    (element->steps[1].op == XSLT_OP_END)) {
1216             element->priority = -0.25;
1217         } else if (((element->steps[0].op == XSLT_OP_PI) ||
1218                     (element->steps[0].op == XSLT_OP_TEXT) ||
1219                     (element->steps[0].op == XSLT_OP_ALL) ||
1220                     (element->steps[0].op == XSLT_OP_NODE) ||
1221                     (element->steps[0].op == XSLT_OP_COMMENT)) &&
1222                    (element->steps[1].op == XSLT_OP_END)) {
1223             element->priority = -0.5;
1224         } else {
1225             element->priority = 0.5;
1226         }
1227         if (pattern[end] == '|')
1228             end++;
1229         current = end;
1230     }
1231     if (end == 0) {
1232         xsltGenericError(xsltGenericErrorContext,
1233                          "xsltCompilePattern : NULL pattern\n");
1234         goto error;
1235     }
1236
1237     xsltFreeParserContext(ctxt);
1238     return(first);
1239
1240 error:
1241     if (ctxt != NULL)
1242         xsltFreeParserContext(ctxt);
1243     if (first != NULL)
1244         xsltFreeCompMatchList(first);
1245     return(NULL);
1246 }
1247
1248 /************************************************************************
1249  *                                                                      *
1250  *                      Module interfaces                               *
1251  *                                                                      *
1252  ************************************************************************/
1253
1254 /**
1255  * xsltAddTemplate:
1256  * @style: an XSLT stylesheet
1257  * @cur: an XSLT template
1258  * @mode:  the mode name or NULL
1259  * @modeURI:  the mode URI or NULL
1260  *
1261  * Register the XSLT pattern associated to @cur
1262  *
1263  * Returns -1 in case of error, 0 otherwise
1264  */
1265 int
1266 xsltAddTemplate(xsltStylesheetPtr style, xsltTemplatePtr cur,
1267                 const xmlChar *mode, const xmlChar *modeURI) {
1268     xsltCompMatchPtr pat, list, *top = NULL, next;
1269     const xmlChar *name = NULL;
1270
1271     if ((style == NULL) || (cur == NULL) || (cur->match == NULL))
1272         return(-1);
1273
1274     pat = xsltCompilePattern(cur->match);
1275     while (pat) {
1276         next = pat->next;
1277         pat->next = NULL;
1278
1279         pat->template = cur;
1280         if (mode != NULL)
1281             pat->mode = xmlStrdup(mode);
1282         if (modeURI != NULL)
1283             pat->modeURI = xmlStrdup(modeURI);
1284         if (pat->priority != XSLT_PAT_NO_PRIORITY)
1285             cur->priority = pat->priority;
1286         else
1287             pat->priority = cur->priority;
1288
1289         /*
1290          * insert it in the hash table list corresponding to its lookup name
1291          */
1292         switch (pat->steps[0].op) {
1293         case XSLT_OP_ATTR:
1294             if (pat->steps[0].value != NULL)
1295                 name = pat->steps[0].value;
1296             else
1297                 top = (xsltCompMatchPtr *) &(style->attrMatch);
1298             break;
1299         case XSLT_OP_ELEM:
1300         case XSLT_OP_CHILD:
1301         case XSLT_OP_PARENT:
1302         case XSLT_OP_ANCESTOR:
1303         case XSLT_OP_NS:
1304             name = pat->steps[0].value;
1305             break;
1306         case XSLT_OP_ROOT:
1307             top = (xsltCompMatchPtr *) &(style->rootMatch);
1308             break;
1309         case XSLT_OP_KEY:
1310             top = (xsltCompMatchPtr *) &(style->keyMatch);
1311             break;
1312         case XSLT_OP_ID:
1313             /* TODO optimize ID !!! */
1314         case XSLT_OP_ALL:
1315             top = (xsltCompMatchPtr *) &(style->elemMatch);
1316             break;
1317         case XSLT_OP_END:
1318         case XSLT_OP_PREDICATE:
1319             xsltGenericError(xsltGenericErrorContext,
1320                              "xsltAddTemplate: invalid compiled pattern\n");
1321             xsltFreeCompMatch(pat);
1322             return(-1);
1323             /*
1324              * TODO: some flags at the top level about type based patterns
1325              *       would be faster than inclusion in the hash table.
1326              */
1327         case XSLT_OP_PI:
1328             if (pat->steps[0].value != NULL)
1329                 name = pat->steps[0].value;
1330             else
1331                 top = (xsltCompMatchPtr *) &(style->piMatch);
1332             break;
1333         case XSLT_OP_COMMENT:
1334             top = (xsltCompMatchPtr *) &(style->commentMatch);
1335             break;
1336         case XSLT_OP_TEXT:
1337             top = (xsltCompMatchPtr *) &(style->textMatch);
1338             break;
1339         case XSLT_OP_NODE:
1340             if (pat->steps[0].value != NULL)
1341                 name = pat->steps[0].value;
1342             else
1343                 top = (xsltCompMatchPtr *) &(style->elemMatch);
1344
1345             break;
1346         }
1347         if (name != NULL) {
1348             if (style->templatesHash == NULL) {
1349                 style->templatesHash = xmlHashCreate(1024);
1350                 if (style->templatesHash == NULL) {
1351                     xsltFreeCompMatch(pat);
1352                     return(-1);
1353                 }
1354 #ifdef DEBUG_PARSING
1355                 xsltGenericDebug(xsltGenericDebugContext,
1356                                  "xsltAddTemplate: created template hash\n");
1357 #endif
1358                 xmlHashAddEntry3(style->templatesHash, name, mode, modeURI, pat);
1359 #ifdef DEBUG_PARSING
1360                 xsltGenericDebug(xsltGenericDebugContext,
1361                                  "xsltAddTemplate: added new hash %s\n", name);
1362 #endif
1363             } else {
1364                 list = (xsltCompMatchPtr) xmlHashLookup3(style->templatesHash,
1365                                                          name, mode, modeURI);
1366                 if (list == NULL) {
1367                     xmlHashAddEntry3(style->templatesHash, name,
1368                                      mode, modeURI, pat);
1369 #ifdef DEBUG_PARSING
1370                     xsltGenericDebug(xsltGenericDebugContext,
1371                                      "xsltAddTemplate: added new hash %s\n", name);
1372 #endif
1373                 } else {
1374                     /*
1375                      * Note '<=' since one must choose among the matching
1376                      * template rules that are left, the one that occurs
1377                      * last in the stylesheet
1378                      */
1379                     if (list->priority <= pat->priority) {
1380                         pat->next = list;
1381                         xmlHashUpdateEntry3(style->templatesHash, name,
1382                                             mode, modeURI, pat, NULL);
1383 #ifdef DEBUG_PARSING
1384                         xsltGenericDebug(xsltGenericDebugContext,
1385                                          "xsltAddTemplate: added head hash for %s\n", name);
1386 #endif
1387                     } else {
1388                         while (list->next != NULL) {
1389                             if (list->next->priority <= pat->priority)
1390                                 break;
1391                             list = list->next;
1392                         }
1393                         pat->next = list->next;
1394                         list->next = pat;
1395                     }
1396                 }
1397             }
1398         } else if (top != NULL) {
1399             list = *top;
1400             if (list == NULL) {
1401                 *top = pat;
1402                 pat->next = NULL;
1403             } else if (list->priority <= pat->priority) {
1404                 pat->next = list;
1405                 *top = pat;
1406             } else {
1407                 while (list->next != NULL) {
1408                     if (list->next->priority <= pat->priority)
1409                         break;
1410                     list = list->next;
1411                 }
1412                 pat->next = list->next;
1413                 list->next = pat;
1414             }
1415         } else {
1416             xsltGenericError(xsltGenericErrorContext,
1417                              "xsltAddTemplate: invalid compiled pattern\n");
1418             xsltFreeCompMatch(pat);
1419             return(-1);
1420         }
1421         pat = next;
1422     }
1423     return(0);
1424 }
1425
1426 /**
1427  * xsltGetTemplate:
1428  * @ctxt:  a XSLT process context
1429  * @mode:  the mode
1430  * @style:  the current style
1431  *
1432  * Finds the template applying to this node, if @style is non-NULL
1433  * it means one need to look for the next imported template in scope.
1434  *
1435  * Returns the xsltTemplatePtr or NULL if not found
1436  */
1437 xsltTemplatePtr
1438 xsltGetTemplate(xsltTransformContextPtr ctxt, xmlNodePtr node,
1439                 xsltStylesheetPtr style) {
1440     xsltStylesheetPtr curstyle;
1441     xsltTemplatePtr ret = NULL;
1442     const xmlChar *name = NULL;
1443     xsltCompMatchPtr list = NULL;
1444
1445     if ((ctxt == NULL) || (node == NULL))
1446         return(NULL);
1447
1448     if (style == NULL) {
1449         curstyle = ctxt->style;
1450     } else {
1451         curstyle = xsltNextImport(style);
1452     }
1453
1454     while ((curstyle != NULL) && (curstyle != style)) {
1455         /* TODO : handle IDs/keys here ! */
1456         if (curstyle->templatesHash != NULL) {
1457             /*
1458              * Use the top name as selector
1459              */
1460             switch (node->type) {
1461                 case XML_ELEMENT_NODE:
1462                 case XML_ATTRIBUTE_NODE:
1463                 case XML_PI_NODE:
1464                     name = node->name;
1465                     break;
1466                 case XML_DOCUMENT_NODE:
1467                 case XML_HTML_DOCUMENT_NODE:
1468                 case XML_TEXT_NODE:
1469                 case XML_CDATA_SECTION_NODE:
1470                 case XML_COMMENT_NODE:
1471                 case XML_ENTITY_REF_NODE:
1472                 case XML_ENTITY_NODE:
1473                 case XML_DOCUMENT_TYPE_NODE:
1474                 case XML_DOCUMENT_FRAG_NODE:
1475                 case XML_NOTATION_NODE:
1476                 case XML_DTD_NODE:
1477                 case XML_ELEMENT_DECL:
1478                 case XML_ATTRIBUTE_DECL:
1479                 case XML_ENTITY_DECL:
1480                 case XML_NAMESPACE_DECL:
1481                 case XML_XINCLUDE_START:
1482                 case XML_XINCLUDE_END:
1483                     break;
1484                 default:
1485                     return(NULL);
1486
1487             }
1488         }
1489         if (name != NULL) {
1490             /*
1491              * find the list of appliable expressions based on the name
1492              */
1493             list = (xsltCompMatchPtr) xmlHashLookup3(curstyle->templatesHash,
1494                                              name, ctxt->mode, ctxt->modeURI);
1495         }
1496         while (list != NULL) {
1497             if (xsltTestCompMatch(ctxt, list, node,
1498                                   ctxt->mode, ctxt->modeURI)) {
1499                 ret = list->template;
1500                 break;
1501             }
1502             list = list->next;
1503         }
1504         list = NULL;
1505
1506         /*
1507          * find alternate generic matches
1508          */
1509         switch (node->type) {
1510             case XML_ELEMENT_NODE:
1511                 list = curstyle->elemMatch;
1512                 break;
1513             case XML_ATTRIBUTE_NODE:
1514                 list = curstyle->attrMatch;
1515                 break;
1516             case XML_PI_NODE:
1517                 list = curstyle->piMatch;
1518                 break;
1519             case XML_DOCUMENT_NODE:
1520             case XML_HTML_DOCUMENT_NODE:
1521                 list = curstyle->rootMatch;
1522                 break;
1523             case XML_TEXT_NODE:
1524             case XML_CDATA_SECTION_NODE:
1525                 list = curstyle->textMatch;
1526                 break;
1527             case XML_COMMENT_NODE:
1528                 list = curstyle->commentMatch;
1529                 break;
1530             case XML_ENTITY_REF_NODE:
1531             case XML_ENTITY_NODE:
1532             case XML_DOCUMENT_TYPE_NODE:
1533             case XML_DOCUMENT_FRAG_NODE:
1534             case XML_NOTATION_NODE:
1535             case XML_DTD_NODE:
1536             case XML_ELEMENT_DECL:
1537             case XML_ATTRIBUTE_DECL:
1538             case XML_ENTITY_DECL:
1539             case XML_NAMESPACE_DECL:
1540             case XML_XINCLUDE_START:
1541             case XML_XINCLUDE_END:
1542                 break;
1543             default:
1544                 break;
1545
1546         }
1547         while ((list != NULL) &&
1548                ((ret == NULL)  || (list->priority > ret->priority))) {
1549             if (xsltTestCompMatch(ctxt, list, node,
1550                                   ctxt->mode, ctxt->modeURI)) {
1551                 ret = list->template;
1552                 break;
1553             }
1554             list = list->next;
1555         }
1556         if (node->_private != NULL) {
1557             list = curstyle->keyMatch;
1558             while ((list != NULL) &&
1559                    ((ret == NULL)  || (list->priority > ret->priority))) {
1560                 if (xsltTestCompMatch(ctxt, list, node,
1561                                       ctxt->mode, ctxt->modeURI)) {
1562                     ret = list->template;
1563                     break;
1564                 }
1565                 list = list->next;
1566             }
1567         }
1568
1569         if (ret != NULL)
1570             return(ret);
1571
1572         /*
1573          * Cycle on next curstylesheet import.
1574          */
1575         curstyle = xsltNextImport(curstyle);
1576     }
1577     return(NULL);
1578 }
1579
1580
1581 /**
1582  * xsltFreeTemplateHashes:
1583  * @style: an XSLT stylesheet
1584  *
1585  * Free up the memory used by xsltAddTemplate/xsltGetTemplate mechanism
1586  */
1587 void
1588 xsltFreeTemplateHashes(xsltStylesheetPtr style) {
1589     if (style->templatesHash != NULL)
1590         xmlHashFree((xmlHashTablePtr) style->templatesHash,
1591                     (xmlHashDeallocator) xsltFreeCompMatchList);
1592     if (style->rootMatch != NULL)
1593         xsltFreeCompMatchList(style->rootMatch);
1594     if (style->keyMatch != NULL)
1595         xsltFreeCompMatchList(style->keyMatch);
1596     if (style->elemMatch != NULL)
1597         xsltFreeCompMatchList(style->elemMatch);
1598     if (style->attrMatch != NULL)
1599         xsltFreeCompMatchList(style->attrMatch);
1600     if (style->parentMatch != NULL)
1601         xsltFreeCompMatchList(style->parentMatch);
1602     if (style->textMatch != NULL)
1603         xsltFreeCompMatchList(style->textMatch);
1604     if (style->piMatch != NULL)
1605         xsltFreeCompMatchList(style->piMatch);
1606     if (style->commentMatch != NULL)
1607         xsltFreeCompMatchList(style->commentMatch);
1608 }
1609
1610 /**
1611  * xsltMatchPattern
1612  * @node: a node in the source tree
1613  * @pattern: an XSLT pattern
1614  *
1615  * Determine if a node matches a pattern.
1616  */
1617 int
1618 xsltMatchPattern(xsltTransformContextPtr context,
1619                  xmlNodePtr node,
1620                  const xmlChar *pattern)
1621 {
1622     int match = 0;
1623     xsltCompMatchPtr first, comp;
1624
1625     if ((context != NULL) && (pattern != NULL)) {
1626         first = xsltCompilePattern(pattern);
1627         for (comp = first; comp != NULL; comp = comp->next) {
1628             match = xsltTestCompMatch(context, comp, node, NULL, NULL);
1629             if (match)
1630                 break; /* for */
1631         }
1632         if (first)
1633             xsltFreeCompMatchList(first);
1634     }
1635     return match;
1636 }
1637