libxslt/xsltutils.c

   1 /*
   2  * xsltutils.c: Utilities for the XSL Transformation 1.0 engine
   3  *
   4  * Reference:
   5  *   http://www.w3.org/TR/1999/REC-xslt-19991116
   6  *
   7  * See Copyright for the status of this software.
   8  *
   9  * daniel@veillard.com
  10  */
  11
  12 #include "libxslt.h"
  13
  14 #include <stdio.h>
  15 #ifdef HAVE_SYS_TIME_H
  16 #include <sys/time.h>
  17 #endif
  18 #ifdef HAVE_UNISTD_H
  19 #include <unistd.h>
  20 #endif
  21 #ifdef HAVE_STDLIB_H
  22 #include <stdlib.h>
  23 #endif
  24 #include <stdarg.h>
  25
  26 #include <libxml/xmlmemory.h>
  27 #include <libxml/tree.h>
  28 #include <libxml/HTMLtree.h>
  29 #include <libxml/xmlerror.h>
  30 #include <libxml/xmlIO.h>
  31 #include "xsltutils.h"
  32 #include "templates.h"
  33 #include "xsltInternals.h"
  34 #include "imports.h"
  35 #include "transform.h"
  36
  37 /* gettimeofday on Windows ??? */
  38 #if defined(WIN32) && !defined(__CYGWIN__)
  39 #ifdef _MSC_VER
  40 #include <winsock2.h>
  41 #pragma comment(lib, "ws2_32.lib")
  42 #define gettimeofday(p1,p2)
  43 #define HAVE_GETTIMEOFDAY
  44 #define XSLT_WIN32_PERFORMANCE_COUNTER
  45 #endif /* _MS_VER */
  46 #endif /* WIN32 */
  47
  48 /************************************************************************
  49  *                                                                      *
  50  *                      Convenience function                            *
  51  *                                                                      *
  52  ************************************************************************/
  53
  54 /**
  55  * xsltGetNsProp:
  56  * @node:  the node
  57  * @name:  the attribute name
  58  * @nameSpace:  the URI of the namespace
  59  *
  60  * Similar to xmlGetNsProp() but with a slightly different semantic
  61  *
  62  * Search and get the value of an attribute associated to a node
  63  * This attribute has to be anchored in the namespace specified,
  64  * or has no namespace and the element is in that namespace.
  65  *
  66  * This does the entity substitution.
  67  * This function looks in DTD attribute declaration for #FIXED or
  68  * default declaration values unless DTD use has been turned off.
  69  *
  70  * Returns the attribute value or NULL if not found.
  71  *     It's up to the caller to free the memory.
  72  */
  73 xmlChar *
  74 xsltGetNsProp(xmlNodePtr node, const xmlChar *name, const xmlChar *nameSpace) {
  75     xmlAttrPtr prop;
  76     xmlDocPtr doc;
  77     xmlNsPtr ns;
  78
  79     if (node == NULL)
  80         return(NULL);
  81
  82     prop = node->properties;
  83     if (nameSpace == NULL)
  84         return(xmlGetProp(node, name));
  85     while (prop != NULL) {
  86         /*
  87          * One need to have
  88          *   - same attribute names
  89          *   - and the attribute carrying that namespace
  90          */
  91         if ((xmlStrEqual(prop->name, name)) &&
  92             (((prop->ns == NULL) && (node->ns != NULL) &&
  93               (xmlStrEqual(node->ns->href, nameSpace))) ||
  94              ((prop->ns != NULL) &&
  95               (xmlStrEqual(prop->ns->href, nameSpace))))) {
  96             xmlChar *ret;
  97
  98             ret = xmlNodeListGetString(node->doc, prop->children, 1);
  99             if (ret == NULL) return(xmlStrdup((xmlChar *)""));
 100             return(ret);
 101         }
 102         prop = prop->next;
 103     }
 104
 105     /*
 106      * Check if there is a default declaration in the internal
 107      * or external subsets
 108      */
 109     doc =  node->doc;
 110     if (doc != NULL) {
 111         if (doc->intSubset != NULL) {
 112             xmlAttributePtr attrDecl;
 113
 114             attrDecl = xmlGetDtdAttrDesc(doc->intSubset, node->name, name);
 115             if ((attrDecl == NULL) && (doc->extSubset != NULL))
 116                 attrDecl = xmlGetDtdAttrDesc(doc->extSubset, node->name, name);
 117
 118             if ((attrDecl != NULL) && (attrDecl->prefix != NULL)) {
 119                 /*
 120                  * The DTD declaration only allows a prefix search
 121                  */
 122                 ns = xmlSearchNs(doc, node, attrDecl->prefix);
 123                 if ((ns != NULL) && (xmlStrEqual(ns->href, nameSpace)))
 124                     return(xmlStrdup(attrDecl->defaultValue));
 125             }
 126         }
 127     }
 128     return(NULL);
 129 }
 130
 131
 132 /************************************************************************
 133  *                                                                      *
 134  *              Handling of XSLT stylesheets messages                   *
 135  *                                                                      *
 136  ************************************************************************/
 137
 138 /**
 139  * xsltMessage:
 140  * @ctxt:  an XSLT processing context
 141  * @node:  The current node
 142  * @inst:  The node containing the message instruction
 143  *
 144  * Process and xsl:message construct
 145  */
 146 void
 147 xsltMessage(xsltTransformContextPtr ctxt, xmlNodePtr node, xmlNodePtr inst) {
 148     xmlChar *prop, *message;
 149     int terminate = 0;
 150
 151     if ((ctxt == NULL) || (inst == NULL))
 152         return;
 153
 154     prop = xsltGetNsProp(inst, (const xmlChar *)"terminate", XSLT_NAMESPACE);
 155     if (prop != NULL) {
 156         if (xmlStrEqual(prop, (const xmlChar *)"yes")) {
 157             terminate = 1;
 158         } else if (xmlStrEqual(prop, (const xmlChar *)"no")) {
 159             terminate = 0;
 160         } else {
 161             xsltGenericError(xsltGenericErrorContext,
 162                 "xsl:message : terminate expecting 'yes' or 'no'\n");
 163         }
 164         xmlFree(prop);
 165     }
 166     message = xsltEvalTemplateString(ctxt, node, inst);
 167     if (message != NULL) {
 168         int len = xmlStrlen(message);
 169
 170         xsltGenericError(xsltGenericErrorContext, "%s",
 171                          (const char *)message);
 172         if ((len > 0) && (message[len - 1] != '\n'))
 173             xsltGenericError(xsltGenericErrorContext, "\n");
 174         xmlFree(message);
 175     }
 176     if (terminate)
 177         ctxt->state = XSLT_STATE_STOPPED;
 178 }
 179
 180 /************************************************************************
 181  *                                                                      *
 182  *              Handling of out of context errors                       *
 183  *                                                                      *
 184  ************************************************************************/
 185
 186 /**
 187  * xsltGenericErrorDefaultFunc:
 188  * @ctx:  an error context
 189  * @msg:  the message to display/transmit
 190  * @...:  extra parameters for the message display
 191  *
 192  * Default handler for out of context error messages.
 193  */
 194 static void
 195 xsltGenericErrorDefaultFunc(void *ctx ATTRIBUTE_UNUSED, const char *msg, ...) {
 196     va_list args;
 197
 198     if (xsltGenericErrorContext == NULL)
 199         xsltGenericErrorContext = (void *) stderr;
 200
 201     va_start(args, msg);
 202     vfprintf((FILE *)xsltGenericErrorContext, msg, args);
 203     va_end(args);
 204 }
 205
 206 xmlGenericErrorFunc xsltGenericError = xsltGenericErrorDefaultFunc;
 207 void *xsltGenericErrorContext = NULL;
 208
 209
 210 /**
 211  * xsltSetGenericErrorFunc:
 212  * @ctx:  the new error handling context
 213  * @handler:  the new handler function
 214  *
 215  * Function to reset the handler and the error context for out of
 216  * context error messages.
 217  * This simply means that @handler will be called for subsequent
 218  * error messages while not parsing nor validating. And @ctx will
 219  * be passed as first argument to @handler
 220  * One can simply force messages to be emitted to another FILE * than
 221  * stderr by setting @ctx to this file handle and @handler to NULL.
 222  */
 223 void
 224 xsltSetGenericErrorFunc(void *ctx, xmlGenericErrorFunc handler) {
 225     xsltGenericErrorContext = ctx;
 226     if (handler != NULL)
 227         xsltGenericError = handler;
 228     else
 229         xsltGenericError = xsltGenericErrorDefaultFunc;
 230 }
 231
 232 /**
 233  * xsltGenericDebugDefaultFunc:
 234  * @ctx:  an error context
 235  * @msg:  the message to display/transmit
 236  * @...:  extra parameters for the message display
 237  *
 238  * Default handler for out of context error messages.
 239  */
 240 static void
 241 xsltGenericDebugDefaultFunc(void *ctx ATTRIBUTE_UNUSED, const char *msg, ...) {
 242     va_list args;
 243
 244     if (xsltGenericDebugContext == NULL)
 245         return;
 246
 247     va_start(args, msg);
 248     vfprintf((FILE *)xsltGenericDebugContext, msg, args);
 249     va_end(args);
 250 }
 251
 252 xmlGenericErrorFunc xsltGenericDebug = xsltGenericDebugDefaultFunc;
 253 void *xsltGenericDebugContext = NULL;
 254
 255
 256 /**
 257  * xsltSetGenericDebugFunc:
 258  * @ctx:  the new error handling context
 259  * @handler:  the new handler function
 260  *
 261  * Function to reset the handler and the error context for out of
 262  * context error messages.
 263  * This simply means that @handler will be called for subsequent
 264  * error messages while not parsing or validating. And @ctx will
 265  * be passed as first argument to @handler
 266  * One can simply force messages to be emitted to another FILE * than
 267  * stderr by setting @ctx to this file handle and @handler to NULL.
 268  */
 269 void
 270 xsltSetGenericDebugFunc(void *ctx, xmlGenericErrorFunc handler) {
 271     xsltGenericDebugContext = ctx;
 272     if (handler != NULL)
 273         xsltGenericDebug = handler;
 274     else
 275         xsltGenericDebug = xsltGenericDebugDefaultFunc;
 276 }
 277
 278 /**
 279  * xsltPrintErrorContext:
 280  * @ctxt:  the transformation context
 281  * @style:  the stylesheet
 282  * @node:  the current node being processed
 283  *
 284  * Display the context of an error.
 285  */
 286 void
 287 xsltPrintErrorContext(xsltTransformContextPtr ctxt,
 288                       xsltStylesheetPtr style, xmlNodePtr node) {
 289     int line = 0;
 290     const xmlChar *file = NULL;
 291     const xmlChar *name = NULL;
 292     const char *type = "error";
 293
 294     if (ctxt != NULL)
 295         ctxt->state = XSLT_STATE_ERROR;
 296     if ((node == NULL) && (ctxt != NULL))
 297         node = ctxt->inst;
 298
 299     if (node != NULL)  {
 300         if ((node->type == XML_DOCUMENT_NODE) ||
 301             (node->type == XML_HTML_DOCUMENT_NODE)) {
 302             xmlDocPtr doc = (xmlDocPtr) node;
 303
 304             file = doc->URL;
 305         } else {
 306             /*
 307              * Try to find contextual informations to report
 308              */
 309             if (node->type == XML_ELEMENT_NODE) {
 310                 line = (int) node->content;
 311             } else if ((node->prev != NULL) &&
 312                        (node->prev->type == XML_ELEMENT_NODE)) {
 313                 line = (int) node->prev->content;
 314             } else if ((node->parent != NULL) &&
 315                        (node->parent->type == XML_ELEMENT_NODE)) {
 316                 line = (int) node->parent->content;
 317             }
 318             if ((node->doc != NULL) && (node->doc->URL != NULL))
 319                 file = node->doc->URL;
 320             if (node->name != NULL)
 321                 name = node->name;
 322         }
 323     }
 324
 325     if (ctxt != NULL)
 326         type = "runtime error";
 327     else if (style != NULL)
 328         type = "compilation error";
 329
 330     if ((file != NULL) && (line != 0) && (name != NULL))
 331         xsltGenericError(xsltGenericErrorContext,
 332                 "%s: file %s line %d element %s\n",
 333                 type, file, line, name);
 334     else if ((file != NULL) && (name != NULL))
 335         xsltGenericError(xsltGenericErrorContext,
 336                 "%s: file %s element %s\n",
 337                 type, file, name);
 338     else if ((file != NULL) && (line != 0))
 339         xsltGenericError(xsltGenericErrorContext,
 340                 "%s: file %s line %d\n",
 341                 type, file, line);
 342     else if (file != NULL)
 343         xsltGenericError(xsltGenericErrorContext,
 344                 "%s: file %s\n",
 345                 type, file);
 346     else if (name != NULL)
 347         xsltGenericError(xsltGenericErrorContext,
 348                 "%s: element %s\n",
 349                 type, name);
 350     else
 351         xsltGenericError(xsltGenericErrorContext,
 352                 "%s\n",
 353                 type);
 354 }
 355
 356 /************************************************************************
 357  *                                                                      *
 358  *                              QNames                                  *
 359  *                                                                      *
 360  ************************************************************************/
 361
 362 /**
 363  * xsltGetQNameURI:
 364  * @node:  the node holding the QName
 365  * @name:  pointer to the initial QName value
 366  *
 367  * This function analyzes @name, if the name contains a prefix,
 368  * the function seaches the associated namespace in scope for it.
 369  * It will also replace @name value with the NCName, the old value being
 370  * freed.
 371  * Errors in the prefix lookup are signalled by setting @name to NULL.
 372  *
 373  * NOTE: the namespace returned is a pointer to the place where it is
 374  *       defined and hence has the same lifespan as the document holding it.
 375  *
 376  * Returns the namespace URI if there is a prefix, or NULL if @name is
 377  *         not prefixed.
 378  */
 379 const xmlChar *
 380 xsltGetQNameURI(xmlNodePtr node, xmlChar ** name)
 381 {
 382     int len = 0;
 383     xmlChar *qname;
 384     xmlNsPtr ns;
 385
 386     if (name == NULL)
 387         return(NULL);
 388     qname = *name;
 389     if ((qname == NULL) || (*qname == 0))
 390         return(NULL);
 391     if (node == NULL) {
 392         xsltGenericError(xsltGenericErrorContext,
 393                          "QName: no element for namespace lookup %s\n",
 394                          qname);
 395         xmlFree(qname);
 396         *name = NULL;
 397         return(NULL);
 398     }
 399
 400     /* nasty but valid */
 401     if (qname[0] == ':')
 402         return(NULL);
 403
 404     /*
 405      * we are not trying to validate but just to cut, and yes it will
 406      * work even if this is a set of UTF-8 encoded chars
 407      */
 408     while ((qname[len] != 0) && (qname[len] != ':'))
 409         len++;
 410
 411     if (qname[len] == 0)
 412         return(NULL);
 413
 414     /*
 415      * handle xml: separately, this one is magical
 416      */
 417     if ((qname[0] == 'x') && (qname[1] == 'm') &&
 418         (qname[2] == 'l') && (qname[3] == ':')) {
 419         if (qname[4] == 0)
 420             return(NULL);
 421         *name = xmlStrdup(&qname[4]);
 422         xmlFree(qname);
 423         return(XML_XML_NAMESPACE);
 424     }
 425
 426     qname[len] = 0;
 427     ns = xmlSearchNs(node->doc, node, qname);
 428     if (ns == NULL) {
 429         xsltGenericError(xsltGenericErrorContext,
 430                 "%s:%s : no namespace bound to prefix %s\n",
 431                          qname, &qname[len + 1]);
 432         *name = NULL;
 433         xmlFree(qname);
 434         return(NULL);
 435     }
 436     *name = xmlStrdup(&qname[len + 1]);
 437     xmlFree(qname);
 438     return(ns->href);
 439 }
 440
 441 /************************************************************************
 442  *                                                                      *
 443  *                              Sorting                                 *
 444  *                                                                      *
 445  ************************************************************************/
 446
 447 /**
 448  * xsltDocumentSortFunction:
 449  * @list:  the node set
 450  *
 451  * reorder the current node list @list accordingly to the document order
 452  */
 453 void
 454 xsltDocumentSortFunction(xmlNodeSetPtr list) {
 455     int i, j;
 456     int len, tst;
 457     xmlNodePtr node;
 458
 459     if (list == NULL)
 460         return;
 461     len = list->nodeNr;
 462     if (len <= 1)
 463         return;
 464     /* TODO: sort is really not optimized, does it needs to ? */
 465     for (i = 0;i < len -1;i++) {
 466         for (j = i + 1; j < len; j++) {
 467             tst = xmlXPathCmpNodes(list->nodeTab[i], list->nodeTab[j]);
 468             if (tst == -1) {
 469                 node = list->nodeTab[i];
 470                 list->nodeTab[i] = list->nodeTab[j];
 471                 list->nodeTab[j] = node;
 472             }
 473         }
 474     }
 475 }
 476
 477 /**
 478  * xsltComputeSortResult:
 479  * @ctxt:  a XSLT process context
 480  * @sorts:  array of sort nodes
 481  *
 482  * reorder the current node list accordingly to the set of sorting
 483  * requirement provided by the array of nodes.
 484  */
 485 static xmlXPathObjectPtr *
 486 xsltComputeSortResult(xsltTransformContextPtr ctxt, xmlNodePtr sort) {
 487     xmlXPathObjectPtr *results = NULL;
 488     xmlNodeSetPtr list = NULL;
 489     xmlXPathObjectPtr res;
 490     int len = 0;
 491     int i;
 492     xsltStylePreCompPtr comp;
 493     xmlNodePtr oldNode;
 494     xmlNodePtr oldInst;
 495     int oldPos, oldSize ;
 496     int oldNsNr;
 497     xmlNsPtr *oldNamespaces;
 498
 499     comp = sort->_private;
 500     if (comp == NULL) {
 501         xsltGenericError(xsltGenericErrorContext,
 502              "xsl:sort : compilation failed\n");
 503         return(NULL);
 504     }
 505
 506     if ((comp->select == NULL) || (comp->comp == NULL))
 507         return(NULL);
 508
 509     list = ctxt->nodeList;
 510     if ((list == NULL) || (list->nodeNr <= 1))
 511         return(NULL);
 512
 513     len = list->nodeNr;
 514
 515     /* TODO: xsl:sort lang attribute */
 516     /* TODO: xsl:sort case-order attribute */
 517
 518
 519     results = xmlMalloc(len * sizeof(xmlXPathObjectPtr));
 520     if (results == NULL) {
 521         xsltGenericError(xsltGenericErrorContext,
 522              "xsltComputeSortResult: memory allocation failure\n");
 523         return(NULL);
 524     }
 525
 526     oldNode = ctxt->node;
 527     oldInst = ctxt->inst;
 528     oldPos = ctxt->xpathCtxt->proximityPosition;
 529     oldSize = ctxt->xpathCtxt->contextSize;
 530     oldNsNr = ctxt->xpathCtxt->nsNr;
 531     oldNamespaces = ctxt->xpathCtxt->namespaces;
 532     for (i = 0;i < len;i++) {
 533         ctxt->inst = sort;
 534         ctxt->xpathCtxt->contextSize = len;
 535         ctxt->xpathCtxt->proximityPosition = i + 1;
 536         ctxt->node = list->nodeTab[i];
 537         ctxt->xpathCtxt->node = ctxt->node;
 538         ctxt->xpathCtxt->namespaces = comp->nsList;
 539         ctxt->xpathCtxt->nsNr = comp->nsNr;
 540         res = xmlXPathCompiledEval(comp->comp, ctxt->xpathCtxt);
 541         if (res != NULL) {
 542             if (res->type != XPATH_STRING)
 543                 res = xmlXPathConvertString(res);
 544             if (comp->number)
 545                 res = xmlXPathConvertNumber(res);
 546             res->index = i;     /* Save original pos for dupl resolv */
 547             if (comp->number) {
 548                 if (res->type == XPATH_NUMBER) {
 549                     results[i] = res;
 550                 } else {
 551 #ifdef WITH_XSLT_DEBUG_PROCESS
 552                     xsltGenericDebug(xsltGenericDebugContext,
 553                         "xsltComputeSortResult: select didn't evaluate to a number\n");
 554 #endif
 555                     results[i] = NULL;
 556                 }
 557             } else {
 558                 if (res->type == XPATH_STRING) {
 559                     results[i] = res;
 560                 } else {
 561 #ifdef WITH_XSLT_DEBUG_PROCESS
 562                     xsltGenericDebug(xsltGenericDebugContext,
 563                         "xsltComputeSortResult: select didn't evaluate to a string\n");
 564 #endif
 565                     results[i] = NULL;
 566                 }
 567             }
 568         } else {
 569             ctxt->state = XSLT_STATE_STOPPED;
 570             results[i] = NULL;
 571         }
 572     }
 573     ctxt->node = oldNode;
 574     ctxt->inst = oldInst;
 575     ctxt->xpathCtxt->contextSize = oldSize;
 576     ctxt->xpathCtxt->proximityPosition = oldPos;
 577     ctxt->xpathCtxt->nsNr = oldNsNr;
 578     ctxt->xpathCtxt->namespaces = oldNamespaces;
 579
 580     return(results);
 581 }
 582
 583 /**
 584  * xsltDoSortFunction:
 585  * @ctxt:  a XSLT process context
 586  * @sorts:  array of sort nodes
 587  * @nbsorts:  the number of sorts in the array
 588  *
 589  * reorder the current node list accordingly to the set of sorting
 590  * requirement provided by the arry of nodes.
 591  */
 592 void
 593 xsltDoSortFunction(xsltTransformContextPtr ctxt, xmlNodePtr *sorts,
 594                    int nbsorts) {
 595     xmlXPathObjectPtr *resultsTab[XSLT_MAX_SORT];
 596     xmlXPathObjectPtr *results = NULL, *res;
 597     xmlNodeSetPtr list = NULL;
 598     int descending, number, desc, numb;
 599     int len = 0;
 600     int i, j, incr;
 601     int tst;
 602     int depth;
 603     xmlNodePtr node;
 604     xmlXPathObjectPtr tmp;
 605     xsltStylePreCompPtr comp;
 606
 607     if ((ctxt == NULL) || (sorts == NULL) || (nbsorts <= 0) ||
 608         (nbsorts >= XSLT_MAX_SORT))
 609         return;
 610     if (sorts[0] == NULL)
 611         return;
 612     comp = sorts[0]->_private;
 613     if (comp == NULL)
 614         return;
 615
 616     list = ctxt->nodeList;
 617     if ((list == NULL) || (list->nodeNr <= 1))
 618         return; /* nothing to do */
 619
 620     len = list->nodeNr;
 621
 622     resultsTab[0] = xsltComputeSortResult(ctxt, sorts[0]);
 623     for (i = 1;i < XSLT_MAX_SORT;i++)
 624         resultsTab[i] = NULL;
 625
 626     results = resultsTab[0];
 627
 628     descending = comp->descending;
 629     number = comp->number;
 630     if (results == NULL)
 631         return;
 632
 633     /* Shell's sort of node-set */
 634     for (incr = len / 2; incr > 0; incr /= 2) {
 635         for (i = incr; i < len; i++) {
 636             j = i - incr;
 637             if (results[i] == NULL)
 638                 continue;
 639
 640             while (j >= 0) {
 641                 if (results[j] == NULL)
 642                     tst = 1;
 643                 else {
 644                     if (number) {
 645                         if (results[j]->floatval == results[j + incr]->floatval)
 646                             tst = 0;
 647                         else if (results[j]->floatval >
 648                                 results[j + incr]->floatval)
 649                             tst = 1;
 650                         else tst = -1;
 651                     } else {
 652                         tst = xmlStrcmp(results[j]->stringval,
 653                                      results[j + incr]->stringval);
 654                     }
 655                     if (descending)
 656                         tst = -tst;
 657                 }
 658                 if (tst == 0) {
 659                     /*
 660                      * Okay we need to use multi level sorts
 661                      */
 662                     depth = 1;
 663                     while (depth < nbsorts) {
 664                         if (sorts[depth] == NULL)
 665                             break;
 666                         comp = sorts[depth]->_private;
 667                         if (comp == NULL)
 668                             break;
 669                         desc = comp->descending;
 670                         numb = comp->number;
 671
 672                         /*
 673                          * Compute the result of the next level for the
 674                          * full set, this might be optimized ... or not
 675                          */
 676                         if (resultsTab[depth] == NULL)
 677                             resultsTab[depth] = xsltComputeSortResult(ctxt,
 678                                                         sorts[depth]);
 679                         res = resultsTab[depth];
 680                         if (res == NULL)
 681                             break;
 682                         if (res[j] == NULL)
 683                             tst = 1;
 684                         else {
 685                             if (numb) {
 686                                 if (res[j]->floatval == res[j + incr]->floatval)
 687                                     tst = 0;
 688                                 else if (res[j]->floatval >
 689                                         res[j + incr]->floatval)
 690                                     tst = 1;
 691                                 else tst = -1;
 692                             } else {
 693                                 tst = xmlStrcmp(res[j]->stringval,
 694                                              res[j + incr]->stringval);
 695                             }
 696                             if (desc)
 697                                 tst = -tst;
 698                         }
 699
 700                         /*
 701                          * if we still can't differenciate at this level
 702                          * try one level deeper.
 703                          */
 704                         if (tst != 0)
 705                             break;
 706                         depth++;
 707                     }
 708                 }
 709                 if (tst == 0) {
 710                     tst = results[j]->index > results[j + incr]->index;
 711                 }
 712                 if (tst > 0) {
 713                     tmp = results[j];
 714                     results[j] = results[j + incr];
 715                     results[j + incr] = tmp;
 716                     node = list->nodeTab[j];
 717                     list->nodeTab[j] = list->nodeTab[j + incr];
 718                     list->nodeTab[j + incr] = node;
 719                     depth = 1;
 720                     while (depth < nbsorts) {
 721                         if (sorts[depth] == NULL)
 722                             break;
 723                         if (resultsTab[depth] == NULL)
 724                             break;
 725                         res = resultsTab[depth];
 726                         tmp = res[j];
 727                         res[j] = res[j + incr];
 728                         res[j + incr] = tmp;
 729                         depth++;
 730                     }
 731                     j -= incr;
 732                 } else
 733                     break;
 734             }
 735         }
 736     }
 737
 738     for (j = 0; j < nbsorts; j++) {
 739         if (resultsTab[j] != NULL) {
 740             for (i = 0;i < len;i++)
 741                 xmlXPathFreeObject(resultsTab[j][i]);
 742             xmlFree(resultsTab[j]);
 743         }
 744     }
 745 }
 746
 747 /************************************************************************
 748  *                                                                      *
 749  *                              Output                                  *
 750  *                                                                      *
 751  ************************************************************************/
 752
 753 /**
 754  * xsltSaveResultTo:
 755  * @buf:  an output buffer
 756  * @result:  the result xmlDocPtr
 757  * @style:  the stylesheet
 758  *
 759  * Save the result @result obtained by applying the @style stylesheet
 760  * to an I/O output channel @buf
 761  *
 762  * Returns the number of byte written or -1 in case of failure.
 763  */
 764 int
 765 xsltSaveResultTo(xmlOutputBufferPtr buf, xmlDocPtr result,
 766                xsltStylesheetPtr style) {
 767     const xmlChar *encoding;
 768     xmlNodePtr root;
 769     int base;
 770     const xmlChar *method;
 771     int indent;
 772
 773     if ((buf == NULL) || (result == NULL) || (style == NULL))
 774         return(-1);
 775     if ((result->children == NULL) ||
 776         ((result->children->type == XML_DTD_NODE) &&
 777          (result->children->next == NULL)))
 778         return(0);
 779
 780     if ((style->methodURI != NULL) &&
 781         ((style->method == NULL) ||
 782          (!xmlStrEqual(style->method, (const xmlChar *) "xhtml")))) {
 783         xsltGenericError(xsltGenericErrorContext,
 784                 "xsltSaveResultTo : unknown ouput method\n");
 785         return(-1);
 786     }
 787
 788     base = buf->written;
 789
 790     XSLT_GET_IMPORT_PTR(method, style, method)
 791     XSLT_GET_IMPORT_PTR(encoding, style, encoding)
 792     XSLT_GET_IMPORT_INT(indent, style, indent);
 793
 794     if ((method == NULL) && (result->type == XML_HTML_DOCUMENT_NODE))
 795         method = (const xmlChar *) "html";
 796
 797     if (method == NULL)
 798         root = xmlDocGetRootElement(result);
 799     else
 800         root = NULL;
 801
 802     if ((method != NULL) &&
 803         (xmlStrEqual(method, (const xmlChar *) "html"))) {
 804         if (encoding != NULL) {
 805             htmlSetMetaEncoding(result, (const xmlChar *) encoding);
 806         } else {
 807             htmlSetMetaEncoding(result, (const xmlChar *) "UTF-8");
 808         }
 809         if (indent != 0)
 810             indent = 1;
 811         htmlDocContentDumpFormatOutput(buf, result, (const char *) encoding,
 812                                        indent);
 813         xmlOutputBufferFlush(buf);
 814     } else if ((method != NULL) &&
 815         (xmlStrEqual(method, (const xmlChar *) "xhtml"))) {
 816         if (encoding != NULL) {
 817             htmlSetMetaEncoding(result, (const xmlChar *) encoding);
 818         } else {
 819             htmlSetMetaEncoding(result, (const xmlChar *) "UTF-8");
 820         }
 821         htmlDocContentDumpOutput(buf, result, (const char *) encoding);
 822         xmlOutputBufferFlush(buf);
 823     } else if ((method != NULL) &&
 824                (xmlStrEqual(method, (const xmlChar *) "text"))) {
 825         xmlNodePtr cur;
 826
 827         cur = result->children;
 828         while (cur != NULL) {
 829             if (cur->type == XML_TEXT_NODE)
 830                 xmlOutputBufferWriteString(buf, (const char *) cur->content);
 831
 832             /*
 833              * Skip to next node
 834              */
 835             if (cur->children != NULL) {
 836                 if ((cur->children->type != XML_ENTITY_DECL) &&
 837                     (cur->children->type != XML_ENTITY_REF_NODE) &&
 838                     (cur->children->type != XML_ENTITY_NODE)) {
 839                     cur = cur->children;
 840                     continue;
 841                 }
 842             }
 843             if (cur->next != NULL) {
 844                 cur = cur->next;
 845                 continue;
 846             }
 847
 848             do {
 849                 cur = cur->parent;
 850                 if (cur == NULL)
 851                     break;
 852                 if (cur == (xmlNodePtr) style->doc) {
 853                     cur = NULL;
 854                     break;
 855                 }
 856                 if (cur->next != NULL) {
 857                     cur = cur->next;
 858                     break;
 859                 }
 860             } while (cur != NULL);
 861         }
 862         xmlOutputBufferFlush(buf);
 863     } else {
 864         int omitXmlDecl;
 865         int standalone;
 866         const xmlChar *version;
 867
 868         XSLT_GET_IMPORT_INT(omitXmlDecl, style, omitXmlDeclaration);
 869         XSLT_GET_IMPORT_INT(standalone, style, standalone);
 870         XSLT_GET_IMPORT_PTR(version, style, version)
 871
 872         if (omitXmlDecl != 1) {
 873             xmlOutputBufferWriteString(buf, "<?xml version=");
 874             if (result->version != NULL)
 875                 xmlBufferWriteQuotedString(buf->buffer, result->version);
 876             else
 877                 xmlOutputBufferWriteString(buf, "\"1.0\"");
 878             if (encoding == NULL) {
 879                 if (result->encoding != NULL)
 880                     encoding = result->encoding;
 881                 else if (result->charset != XML_CHAR_ENCODING_UTF8)
 882                     encoding = (const xmlChar *)
 883                                xmlGetCharEncodingName((xmlCharEncoding)
 884                                                       result->charset);
 885             }
 886             if (encoding != NULL) {
 887                 xmlOutputBufferWriteString(buf, " encoding=");
 888                 xmlBufferWriteQuotedString(buf->buffer, (xmlChar *) encoding);
 889             }
 890             switch (standalone) {
 891                 case 0:
 892                     xmlOutputBufferWriteString(buf, " standalone=\"no\"");
 893                     break;
 894                 case 1:
 895                     xmlOutputBufferWriteString(buf, " standalone=\"yes\"");
 896                     break;
 897                 default:
 898                     break;
 899             }
 900             xmlOutputBufferWriteString(buf, "?>\n");
 901         }
 902         if (result->children != NULL) {
 903             xmlNodePtr child = result->children;
 904
 905             while (child != NULL) {
 906                 xmlNodeDumpOutput(buf, result, child, 0, (indent == 1),
 907                                   (const char *) encoding);
 908                 if (child->type == XML_DTD_NODE)
 909                     xmlOutputBufferWriteString(buf, "\n");
 910                 child = child->next;
 911             }
 912             xmlOutputBufferWriteString(buf, "\n");
 913         }
 914         xmlOutputBufferFlush(buf);
 915     }
 916     return(buf->written - base);
 917 }
 918
 919 /**
 920  * xsltSaveResultToFilename:
 921  * @URL:  a filename or URL
 922  * @result:  the result xmlDocPtr
 923  * @style:  the stylesheet
 924  * @compression:  the compression factor (0 - 9 included)
 925  *
 926  * Save the result @result obtained by applying the @style stylesheet
 927  * to a file or @URL
 928  *
 929  * Returns the number of byte written or -1 in case of failure.
 930  */
 931 int
 932 xsltSaveResultToFilename(const char *URL, xmlDocPtr result,
 933                          xsltStylesheetPtr style, int compression) {
 934     xmlOutputBufferPtr buf;
 935     const xmlChar *encoding;
 936     int ret;
 937
 938     if ((URL == NULL) || (result == NULL) || (style == NULL))
 939         return(-1);
 940     if (result->children == NULL)
 941         return(0);
 942
 943     XSLT_GET_IMPORT_PTR(encoding, style, encoding)
 944     if (encoding != NULL) {
 945         xmlCharEncodingHandlerPtr encoder;
 946
 947         encoder = xmlFindCharEncodingHandler((char *)encoding);
 948         if ((encoder != NULL) &&
 949             (xmlStrEqual((const xmlChar *)encoder->name,
 950                          (const xmlChar *) "UTF-8")))
 951             encoder = NULL;
 952         buf = xmlOutputBufferCreateFilename(URL, encoder, compression);
 953     } else {
 954         buf = xmlOutputBufferCreateFilename(URL, NULL, compression);
 955     }
 956     if (buf == NULL)
 957         return(-1);
 958     xsltSaveResultTo(buf, result, style);
 959     ret = xmlOutputBufferClose(buf);
 960     return(ret);
 961 }
 962
 963 /**
 964  * xsltSaveResultToFile:
 965  * @file:  a FILE * I/O
 966  * @result:  the result xmlDocPtr
 967  * @style:  the stylesheet
 968  *
 969  * Save the result @result obtained by applying the @style stylesheet
 970  * to an open FILE * I/O.
 971  * This does not close the FILE @file
 972  *
 973  * Returns the number of bytes written or -1 in case of failure.
 974  */
 975 int
 976 xsltSaveResultToFile(FILE *file, xmlDocPtr result, xsltStylesheetPtr style) {
 977     xmlOutputBufferPtr buf;
 978     const xmlChar *encoding;
 979     int ret;
 980
 981     if ((file == NULL) || (result == NULL) || (style == NULL))
 982         return(-1);
 983     if (result->children == NULL)
 984         return(0);
 985
 986     XSLT_GET_IMPORT_PTR(encoding, style, encoding)
 987     if (encoding != NULL) {
 988         xmlCharEncodingHandlerPtr encoder;
 989
 990         encoder = xmlFindCharEncodingHandler((char *)encoding);
 991         if ((encoder != NULL) &&
 992             (xmlStrEqual((const xmlChar *)encoder->name,
 993                          (const xmlChar *) "UTF-8")))
 994             encoder = NULL;
 995         buf = xmlOutputBufferCreateFile(file, encoder);
 996     } else {
 997         buf = xmlOutputBufferCreateFile(file, NULL);
 998     }
 999
1000     if (buf == NULL)
1001         return(-1);
1002     xsltSaveResultTo(buf, result, style);
1003     ret = xmlOutputBufferClose(buf);
1004     return(ret);
1005 }
1006
1007 /**
1008  * xsltSaveResultToFd:
1009  * @fd:  a file descriptor
1010  * @result:  the result xmlDocPtr
1011  * @style:  the stylesheet
1012  *
1013  * Save the result @result obtained by applying the @style stylesheet
1014  * to an open file descriptor
1015  * This does not close the descriptor.
1016  *
1017  * Returns the number of bytes written or -1 in case of failure.
1018  */
1019 int
1020 xsltSaveResultToFd(int fd, xmlDocPtr result, xsltStylesheetPtr style) {
1021     xmlOutputBufferPtr buf;
1022     const xmlChar *encoding;
1023     int ret;
1024
1025     if ((fd < 0) || (result == NULL) || (style == NULL))
1026         return(-1);
1027     if (result->children == NULL)
1028         return(0);
1029
1030     XSLT_GET_IMPORT_PTR(encoding, style, encoding)
1031     if (encoding != NULL) {
1032         xmlCharEncodingHandlerPtr encoder;
1033
1034         encoder = xmlFindCharEncodingHandler((char *)encoding);
1035         if ((encoder != NULL) &&
1036             (xmlStrEqual((const xmlChar *)encoder->name,
1037                          (const xmlChar *) "UTF-8")))
1038             encoder = NULL;
1039         buf = xmlOutputBufferCreateFd(fd, encoder);
1040     } else {
1041         buf = xmlOutputBufferCreateFd(fd, NULL);
1042     }
1043     if (buf == NULL)
1044         return(-1);
1045     xsltSaveResultTo(buf, result, style);
1046     ret = xmlOutputBufferClose(buf);
1047     return(ret);
1048 }
1049
1050 /************************************************************************
1051  *                                                                      *
1052  *              Generating profiling informations                       *
1053  *                                                                      *
1054  ************************************************************************/
1055
1056 static long calibration = -1;
1057
1058 /**
1059  * xsltCalibrateTimestamps:
1060  *
1061  * Used for to calibrate the xsltTimestamp() function
1062  * Should work if launched at startup and we don't loose our quantum :-)
1063  *
1064  * Returns the number of milliseconds used by xsltTimestamp()
1065  */
1066 static long
1067 xsltCalibrateTimestamps(void) {
1068     register int i;
1069
1070     for (i = 0;i < 999;i++)
1071         xsltTimestamp();
1072     return(xsltTimestamp() / 1000);
1073 }
1074
1075 /**
1076  * xsltCalibrateAdjust:
1077  * @delta:  a negative dealy value found
1078  *
1079  * Used for to correct the calibration for xsltTimestamp()
1080  */
1081 void
1082 xsltCalibrateAdjust(long delta) {
1083     calibration += delta;
1084 }
1085
1086 /**
1087  * xsltTimestamp:
1088  *
1089  * Used for gathering profiling data
1090  *
1091  * Returns the number of tenth of milliseconds since the beginning of the
1092  * profiling
1093  */
1094 long
1095 xsltTimestamp(void)
1096 {
1097 #ifdef XSLT_WIN32_PERFORMANCE_COUNTER
1098     BOOL ok;
1099     LARGE_INTEGER performanceCount;
1100     LARGE_INTEGER performanceFrequency;
1101     LONGLONG quadCount;
1102     double seconds;
1103     static LONGLONG startupQuadCount = 0;
1104     static LONGLONG startupQuadFreq = 0;
1105
1106     ok = QueryPerformanceCounter(&performanceCount);
1107     if (!ok)
1108         return 0;
1109     quadCount = performanceCount.QuadPart;
1110     if (calibration < 0) {
1111         calibration = 0;
1112         ok = QueryPerformanceFrequency(&performanceFrequency);
1113         if (!ok)
1114             return 0;
1115         startupQuadFreq = performanceFrequency.QuadPart;
1116         startupQuadCount = quadCount;
1117         return (0);
1118     }
1119     if (startupQuadFreq == 0)
1120         return 0;
1121     seconds = (quadCount - startupQuadCount) / (double) startupQuadFreq;
1122     return (long) (seconds * XSLT_TIMESTAMP_TICS_PER_SEC);
1123
1124 #else /* XSLT_WIN32_PERFORMANCE_COUNTER */
1125 #ifdef HAVE_GETTIMEOFDAY
1126     static struct timeval startup;
1127     struct timeval cur;
1128     long tics;
1129
1130     if (calibration < 0) {
1131         gettimeofday(&startup, NULL);
1132         calibration = 0;
1133         calibration = xsltCalibrateTimestamps();
1134         gettimeofday(&startup, NULL);
1135         return (0);
1136     }
1137
1138     gettimeofday(&cur, NULL);
1139     tics = (cur.tv_sec - startup.tv_sec) * XSLT_TIMESTAMP_TICS_PER_SEC;
1140     tics += (cur.tv_usec - startup.tv_usec) /
1141                           (1000000l / XSLT_TIMESTAMP_TICS_PER_SEC);
1142
1143     tics -= calibration;
1144     return(tics);
1145 #else
1146
1147     /* Neither gettimeofday() nor Win32 performance counter available */
1148
1149     return (0);
1150
1151 #endif /* HAVE_GETTIMEOFDAY */
1152 #endif /* XSLT_WIN32_PERFORMANCE_COUNTER */
1153 }
1154
1155 #define MAX_TEMPLATES 10000
1156
1157 /**
1158  * xsltSaveProfiling:
1159  * @ctxt:  an XSLT context
1160  * @output:  a FILE * for saving the informations
1161  *
1162  * Save the profiling informations on @output
1163  */
1164 void
1165 xsltSaveProfiling(xsltTransformContextPtr ctxt, FILE *output) {
1166     int nb, i,j;
1167     int max;
1168     int total;
1169     long totalt;
1170     xsltTemplatePtr *templates;
1171     xsltStylesheetPtr style;
1172     xsltTemplatePtr template;
1173
1174     if ((output == NULL) || (ctxt == NULL))
1175         return;
1176     if (ctxt->profile == 0)
1177         return;
1178
1179     nb = 0;
1180     max = MAX_TEMPLATES;
1181     templates = xmlMalloc(max * sizeof(xsltTemplatePtr));
1182     if (templates == NULL)
1183         return;
1184
1185     style = ctxt->style;
1186     while (style != NULL) {
1187         template = style->templates;
1188         while (template != NULL) {
1189             if (nb >= max)
1190                 break;
1191
1192             if (template->nbCalls > 0)
1193                 templates[nb++] = template;
1194             template = template->next;
1195         }
1196
1197         style = xsltNextImport(style);
1198     }
1199
1200     for (i = 0;i < nb -1;i++) {
1201         for (j = i + 1; j < nb; j++) {
1202             if ((templates[i]->time <= templates[j]->time) ||
1203                 ((templates[i]->time == templates[j]->time) &&
1204                  (templates[i]->nbCalls <= templates[j]->nbCalls))) {
1205                 template = templates[j];
1206                 templates[j] = templates[i];
1207                 templates[i] = template;
1208             }
1209         }
1210     }
1211
1212     fprintf(output, "%6s%20s%20s%10s  Calls Tot 100us Avg\n\n",
1213             "number", "match", "name", "mode");
1214     total = 0;
1215     totalt = 0;
1216     for (i = 0;i < nb;i++) {
1217         fprintf(output, "%5d ", i);
1218         if (templates[i]->match != NULL) {
1219             if (xmlStrlen(templates[i]->match) > 20)
1220                 fprintf(output, "%s\n%26s", templates[i]->match, "");
1221             else
1222                 fprintf(output, "%20s", templates[i]->match);
1223         } else {
1224             fprintf(output, "%20s", "");
1225         }
1226         if (templates[i]->name != NULL) {
1227             if (xmlStrlen(templates[i]->name) > 20)
1228                 fprintf(output, "%s\n%46s", templates[i]->name, "");
1229             else
1230                 fprintf(output, "%20s", templates[i]->name);
1231         } else {
1232             fprintf(output, "%20s", "");
1233         }
1234         if (templates[i]->mode != NULL) {
1235             if (xmlStrlen(templates[i]->mode) > 10)
1236                 fprintf(output, "%s\n%56s", templates[i]->mode, "");
1237             else
1238                 fprintf(output, "%10s", templates[i]->mode);
1239         } else {
1240             fprintf(output, "%10s", "");
1241         }
1242         fprintf(output, " %6d", templates[i]->nbCalls);
1243         fprintf(output, " %6ld %6ld\n", templates[i]->time,
1244                 templates[i]->time / templates[i]->nbCalls);
1245         total += templates[i]->nbCalls;
1246         totalt += templates[i]->time;
1247     }
1248     fprintf(output, "\n%30s%26s %6d %6ld\n", "Total", "", total, totalt);
1249
1250     xmlFree(templates);
1251 }
1252
1253 /************************************************************************
1254  *                                                                      *
1255  *              Hooks for the debugger                                  *
1256  *                                                                      *
1257  ************************************************************************/
1258
1259 /*
1260  * There is currently only 3 debugging callback defined
1261  * Debugger callbacks are disabled by default
1262  */
1263 #define XSLT_CALLBACK_NUMBER 3
1264
1265 typedef struct _xsltDebuggerCallbacks xsltDebuggerCallbacks;
1266 typedef xsltDebuggerCallbacks *xsltDebuggerCallbacksPtr;
1267 struct _xsltDebuggerCallbacks {
1268     xsltHandleDebuggerCallback handler;
1269     xsltAddCallCallback add;
1270     xsltDropCallCallback drop;
1271 };
1272
1273 static xsltDebuggerCallbacks xsltDebuggerCurrentCallbacks = {
1274     NULL, /* handler */
1275     NULL, /* add */
1276     NULL  /* drop */
1277 };
1278
1279 int xslDebugStatus;
1280
1281 /**
1282  * xslSetDebuggerCallbacks:
1283  * @no : number of callbacks
1284  * @block : the block of callbacks
1285  *
1286  * This function allow to plug a debugger into the XSLT library
1287  * @block points to a block of memory containing the address of @no
1288  * callback routines.
1289  *
1290  * Returns 0 in case of success and -1 in case of error
1291  */
1292 int
1293 xsltSetDebuggerCallbacks(int no, void *block)
1294 {
1295     xsltDebuggerCallbacksPtr callbacks;
1296
1297     if ((block == NULL) || (no != XSLT_CALLBACK_NUMBER))
1298         return(-1);
1299
1300     callbacks = (xsltDebuggerCallbacksPtr) block;
1301     xsltDebuggerCurrentCallbacks.handler = callbacks->handler;
1302     xsltDebuggerCurrentCallbacks.add  = callbacks->add;
1303     xsltDebuggerCurrentCallbacks.drop  = callbacks->drop;
1304     return(0);
1305 }
1306
1307 /**
1308  * xslHandleDebugger:
1309  * @cur : source node being executed
1310  * @node : data node being processed
1311  * @templ : temlate that applies to node
1312  * @ctxt : the xslt transform context
1313  *
1314  * If either cur or node are a breakpoint, or xslDebugStatus in state
1315  *   where debugging must occcur at this time then transfer control
1316  *   to the xslDebugBreak function
1317  */
1318 void
1319 xslHandleDebugger(xmlNodePtr cur, xmlNodePtr node, xsltTemplatePtr templ,
1320                   xsltTransformContextPtr ctxt)
1321 {
1322     if (xsltDebuggerCurrentCallbacks.handler != NULL)
1323         xsltDebuggerCurrentCallbacks.handler(cur, node, templ, ctxt);
1324 }
1325
1326 /**
1327  * xslAddCall:
1328  * @templ : current template being applied
1329  * @source : the source node being processed
1330  *
1331  * Add template "call" to call stack
1332  * Returns : 1 on sucess 0 otherwise an error may be printed if
1333  *            WITH_XSLT_DEBUG_BREAKPOINTS is defined
1334  */
1335 int
1336 xslAddCall(xsltTemplatePtr templ, xmlNodePtr source)
1337 {
1338     if (xsltDebuggerCurrentCallbacks.add != NULL)
1339         return(xsltDebuggerCurrentCallbacks.add(templ, source));
1340     return(0);
1341 }
1342
1343 /**
1344  * xslDropCall :
1345  *
1346  * Drop the topmost item off the call stack
1347  */
1348 void
1349 xslDropCall(void)
1350 {
1351     if (xsltDebuggerCurrentCallbacks.drop != NULL)
1352         xsltDebuggerCurrentCallbacks.drop();
1353 }
1354