1 /*
   2  * keys.c: Implemetation of the keys support
   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 #define IN_LIBXSLT
  13 #include "libxslt.h"
  14 
  15 #include <string.h>
  16 
  17 #include <libxml/xmlmemory.h>
  18 #include <libxml/tree.h>
  19 #include <libxml/valid.h>
  20 #include <libxml/hash.h>
  21 #include <libxml/xmlerror.h>
  22 #include <libxml/parserInternals.h>
  23 #include <libxml/xpathInternals.h>
  24 #include <libxml/xpath.h>
  25 #include "xslt.h"
  26 #include "xsltInternals.h"
  27 #include "xsltutils.h"
  28 #include "imports.h"
  29 #include "templates.h"
  30 #include "keys.h"
  31 
  32 #ifdef WITH_XSLT_DEBUG
  33 #define WITH_XSLT_DEBUG_KEYS
  34 #endif
  35 
  36 static int
  37 xsltInitDocKeyTable(xsltTransformContextPtr ctxt, const xmlChar *name,
  38                     const xmlChar *nameURI);
  39 
  40 /************************************************************************
  41  *                                  *
  42  *          Type functions                  *
  43  *                                  *
  44  ************************************************************************/
  45 
  46 /**
  47  * xsltNewKeyDef:
  48  * @name:  the key name or NULL
  49  * @nameURI:  the name URI or NULL
  50  *
  51  * Create a new XSLT KeyDef
  52  *
  53  * Returns the newly allocated xsltKeyDefPtr or NULL in case of error
  54  */
  55 static xsltKeyDefPtr
  56 xsltNewKeyDef(const xmlChar *name, const xmlChar *nameURI) {
  57     xsltKeyDefPtr cur;
  58 
  59     cur = (xsltKeyDefPtr) xmlMalloc(sizeof(xsltKeyDef));
  60     if (cur == NULL) {
  61     xsltTransformError(NULL, NULL, NULL,
  62         "xsltNewKeyDef : malloc failed\n");
  63     return(NULL);
  64     }
  65     memset(cur, 0, sizeof(xsltKeyDef));
  66     if (name != NULL)
  67     cur->name = xmlStrdup(name);
  68     if (nameURI != NULL)
  69     cur->nameURI = xmlStrdup(nameURI);
  70     cur->nsList = NULL;
  71     return(cur);
  72 }
  73 
  74 /**
  75  * xsltFreeKeyDef:
  76  * @keyd:  an XSLT key definition
  77  *
  78  * Free up the memory allocated by @keyd
  79  */
  80 static void
  81 xsltFreeKeyDef(xsltKeyDefPtr keyd) {
  82     if (keyd == NULL)
  83     return;
  84     if (keyd->comp != NULL)
  85     xmlXPathFreeCompExpr(keyd->comp);
  86     if (keyd->usecomp != NULL)
  87     xmlXPathFreeCompExpr(keyd->usecomp);
  88     if (keyd->name != NULL)
  89     xmlFree(keyd->name);
  90     if (keyd->nameURI != NULL)
  91     xmlFree(keyd->nameURI);
  92     if (keyd->match != NULL)
  93     xmlFree(keyd->match);
  94     if (keyd->use != NULL)
  95     xmlFree(keyd->use);
  96     if (keyd->nsList != NULL)
  97         xmlFree(keyd->nsList);
  98     memset(keyd, -1, sizeof(xsltKeyDef));
  99     xmlFree(keyd);
 100 }
 101 
 102 /**
 103  * xsltFreeKeyDefList:
 104  * @keyd:  an XSLT key definition list
 105  *
 106  * Free up the memory allocated by all the elements of @keyd
 107  */
 108 static void
 109 xsltFreeKeyDefList(xsltKeyDefPtr keyd) {
 110     xsltKeyDefPtr cur;
 111 
 112     while (keyd != NULL) {
 113     cur = keyd;
 114     keyd = keyd->next;
 115     xsltFreeKeyDef(cur);
 116     }
 117 }
 118 
 119 /**
 120  * xsltNewKeyTable:
 121  * @name:  the key name or NULL
 122  * @nameURI:  the name URI or NULL
 123  *
 124  * Create a new XSLT KeyTable
 125  *
 126  * Returns the newly allocated xsltKeyTablePtr or NULL in case of error
 127  */
 128 static xsltKeyTablePtr
 129 xsltNewKeyTable(const xmlChar *name, const xmlChar *nameURI) {
 130     xsltKeyTablePtr cur;
 131 
 132     cur = (xsltKeyTablePtr) xmlMalloc(sizeof(xsltKeyTable));
 133     if (cur == NULL) {
 134     xsltTransformError(NULL, NULL, NULL,
 135         "xsltNewKeyTable : malloc failed\n");
 136     return(NULL);
 137     }
 138     memset(cur, 0, sizeof(xsltKeyTable));
 139     if (name != NULL)
 140     cur->name = xmlStrdup(name);
 141     if (nameURI != NULL)
 142     cur->nameURI = xmlStrdup(nameURI);
 143     cur->keys = xmlHashCreate(0);
 144     return(cur);
 145 }
 146 
 147 /**
 148  * xsltFreeKeyTable:
 149  * @keyt:  an XSLT key table
 150  *
 151  * Free up the memory allocated by @keyt
 152  */
 153 static void
 154 xsltFreeKeyTable(xsltKeyTablePtr keyt) {
 155     if (keyt == NULL)
 156     return;
 157     if (keyt->name != NULL)
 158     xmlFree(keyt->name);
 159     if (keyt->nameURI != NULL)
 160     xmlFree(keyt->nameURI);
 161     if (keyt->keys != NULL)
 162     xmlHashFree(keyt->keys,
 163             (xmlHashDeallocator) xmlXPathFreeNodeSet);
 164     memset(keyt, -1, sizeof(xsltKeyTable));
 165     xmlFree(keyt);
 166 }
 167 
 168 /**
 169  * xsltFreeKeyTableList:
 170  * @keyt:  an XSLT key table list
 171  *
 172  * Free up the memory allocated by all the elements of @keyt
 173  */
 174 static void
 175 xsltFreeKeyTableList(xsltKeyTablePtr keyt) {
 176     xsltKeyTablePtr cur;
 177 
 178     while (keyt != NULL) {
 179     cur = keyt;
 180     keyt = keyt->next;
 181     xsltFreeKeyTable(cur);
 182     }
 183 }
 184 
 185 /************************************************************************
 186  *                                  *
 187  *      The interpreter for the precompiled patterns        *
 188  *                                  *
 189  ************************************************************************/
 190 
 191 
 192 /**
 193  * xsltFreeKeys:
 194  * @style: an XSLT stylesheet
 195  *
 196  * Free up the memory used by XSLT keys in a stylesheet
 197  */
 198 void
 199 xsltFreeKeys(xsltStylesheetPtr style) {
 200     if (style->keys)
 201     xsltFreeKeyDefList((xsltKeyDefPtr) style->keys);
 202 }
 203 
 204 /**
 205  * skipString:
 206  * @cur: the current pointer
 207  * @end: the current offset
 208  *
 209  * skip a string delimited by " or '
 210  *
 211  * Returns the byte after the string or -1 in case of error
 212  */
 213 static int
 214 skipString(const xmlChar *cur, int end) {
 215     xmlChar limit;
 216 
 217     if ((cur == NULL) || (end < 0)) return(-1);
 218     if ((cur[end] == '\'') || (cur[end] == '"')) limit = cur[end];
 219     else return(end);
 220     end++;
 221     while (cur[end] != 0) {
 222         if (cur[end] == limit)
 223         return(end + 1);
 224     end++;
 225     }
 226     return(-1);
 227 }
 228 
 229 /**
 230  * skipPredicate:
 231  * @cur: the current pointer
 232  * @end: the current offset
 233  *
 234  * skip a predicate
 235  *
 236  * Returns the byte after the predicate or -1 in case of error
 237  */
 238 static int
 239 skipPredicate(const xmlChar *cur, int end) {
 240     if ((cur == NULL) || (end < 0)) return(-1);
 241     if (cur[end] != '[') return(end);
 242     end++;
 243     while (cur[end] != 0) {
 244         if ((cur[end] == '\'') || (cur[end] == '"')) {
 245         end = skipString(cur, end);
 246         if (end <= 0)
 247             return(-1);
 248         continue;
 249     } else if (cur[end] == '[') {
 250         end = skipPredicate(cur, end);
 251         if (end <= 0)
 252             return(-1);
 253         continue;
 254     } else if (cur[end] == ']')
 255         return(end + 1);
 256     end++;
 257     }
 258     return(-1);
 259 }
 260 
 261 /**
 262  * xsltAddKey:
 263  * @style: an XSLT stylesheet
 264  * @name:  the key name or NULL
 265  * @nameURI:  the name URI or NULL
 266  * @match:  the match value
 267  * @use:  the use value
 268  * @inst: the key instruction
 269  *
 270  * add a key definition to a stylesheet
 271  *
 272  * Returns 0 in case of success, and -1 in case of failure.
 273  */
 274 int
 275 xsltAddKey(xsltStylesheetPtr style, const xmlChar *name,
 276        const xmlChar *nameURI, const xmlChar *match,
 277        const xmlChar *use, xmlNodePtr inst) {
 278     xsltKeyDefPtr key;
 279     xmlChar *pattern = NULL;
 280     int current, end, start, i = 0;
 281 
 282     if ((style == NULL) || (name == NULL) || (match == NULL) || (use == NULL))
 283     return(-1);
 284 
 285 #ifdef WITH_XSLT_DEBUG_KEYS
 286     xsltGenericDebug(xsltGenericDebugContext,
 287     "Add key %s, match %s, use %s\n", name, match, use);
 288 #endif
 289 
 290     key = xsltNewKeyDef(name, nameURI);
 291     key->match = xmlStrdup(match);
 292     key->use = xmlStrdup(use);
 293     key->inst = inst;
 294     key->nsList = xmlGetNsList(inst->doc, inst);
 295     if (key->nsList != NULL) {
 296         while (key->nsList[i] != NULL)
 297         i++;
 298     }
 299     key->nsNr = i;
 300 
 301     /*
 302      * Split the | and register it as as many keys
 303      */
 304     current = end = 0;
 305     while (match[current] != 0) {
 306     start = current;
 307     while (IS_BLANK_CH(match[current]))
 308         current++;
 309     end = current;
 310     while ((match[end] != 0) && (match[end] != '|')) {
 311         if (match[end] == '[') {
 312             end = skipPredicate(match, end);
 313         if (end <= 0) {
 314             xsltTransformError(NULL, style, inst,
 315                 "xsl:key : 'match' pattern is malformed: %s",
 316                 key->match);
 317             if (style != NULL) style->errors++;
 318             goto error;
 319         }
 320         } else
 321         end++;
 322     }
 323     if (current == end) {
 324         xsltTransformError(NULL, style, inst,
 325                    "xsl:key : 'match' pattern is empty\n");
 326         if (style != NULL) style->errors++;
 327         goto error;
 328     }
 329     if (match[start] != '/') {
 330         pattern = xmlStrcat(pattern, (xmlChar *)"//");
 331         if (pattern == NULL) {
 332         if (style != NULL) style->errors++;
 333         goto error;
 334         }
 335     }
 336     pattern = xmlStrncat(pattern, &match[start], end - start);
 337     if (pattern == NULL) {
 338         if (style != NULL) style->errors++;
 339         goto error;
 340     }
 341 
 342     if (match[end] == '|') {
 343         pattern = xmlStrcat(pattern, (xmlChar *)"|");
 344         end++;
 345     }
 346     current = end;
 347     }
 348     if (pattern == NULL) {
 349         xsltTransformError(NULL, style, inst,
 350                            "xsl:key : 'match' pattern is empty\n");
 351         if (style != NULL) style->errors++;
 352         goto error;
 353     }
 354 #ifdef WITH_XSLT_DEBUG_KEYS
 355     xsltGenericDebug(xsltGenericDebugContext,
 356     "   resulting pattern %s\n", pattern);
 357 #endif
 358     /*
 359     * XSLT-1: "It is an error for the value of either the use
 360     *  attribute or the match attribute to contain a
 361     *  VariableReference."
 362     * TODO: We should report a variable-reference at compile-time.
 363     *   Maybe a search for "$", if it occurs outside of quotation
 364     *   marks, could be sufficient.
 365     */
 366 #ifdef XML_XPATH_NOVAR
 367     key->comp = xsltXPathCompileFlags(style, pattern, XML_XPATH_NOVAR);
 368 #else
 369     key->comp = xsltXPathCompile(style, pattern);
 370 #endif
 371     if (key->comp == NULL) {
 372     xsltTransformError(NULL, style, inst,
 373         "xsl:key : 'match' pattern compilation failed '%s'\n",
 374                  pattern);
 375     if (style != NULL) style->errors++;
 376     }
 377 #ifdef XML_XPATH_NOVAR
 378     key->usecomp = xsltXPathCompileFlags(style, use, XML_XPATH_NOVAR);
 379 #else
 380     key->usecomp = xsltXPathCompile(style, use);
 381 #endif
 382     if (key->usecomp == NULL) {
 383     xsltTransformError(NULL, style, inst,
 384         "xsl:key : 'use' expression compilation failed '%s'\n",
 385                  use);
 386     if (style != NULL) style->errors++;
 387     }
 388 
 389     /*
 390      * Sometimes the stylesheet writer use the order to ease the
 391      * resolution of keys when they are dependant, keep the provided
 392      * order so add the new one at the end.
 393      */
 394     if (style->keys == NULL) {
 395     style->keys = key;
 396     } else {
 397         xsltKeyDefPtr prev = style->keys;
 398 
 399     while (prev->next != NULL)
 400         prev = prev->next;
 401 
 402     prev->next = key;
 403     }
 404     key->next = NULL;
 405 
 406 error:
 407     if (pattern != NULL)
 408     xmlFree(pattern);
 409     return(0);
 410 }
 411 
 412 /**
 413  * xsltGetKey:
 414  * @ctxt: an XSLT transformation context
 415  * @name:  the key name or NULL
 416  * @nameURI:  the name URI or NULL
 417  * @value:  the key value to look for
 418  *
 419  * Looks up a key of the in current source doc (the document info
 420  * on @ctxt->document). Computes the key if not already done
 421  * for the current source doc.
 422  *
 423  * Returns the nodeset resulting from the query or NULL
 424  */
 425 xmlNodeSetPtr
 426 xsltGetKey(xsltTransformContextPtr ctxt, const xmlChar *name,
 427        const xmlChar *nameURI, const xmlChar *value) {
 428     xmlNodeSetPtr ret;
 429     xsltKeyTablePtr table;
 430     int init_table = 0;
 431 
 432     if ((ctxt == NULL) || (name == NULL) || (value == NULL) ||
 433     (ctxt->document == NULL))
 434     return(NULL);
 435 
 436 #ifdef WITH_XSLT_DEBUG_KEYS
 437     xsltGenericDebug(xsltGenericDebugContext,
 438     "Get key %s, value %s\n", name, value);
 439 #endif
 440 
 441     /*
 442      * keys are computed only on-demand on first key access for a document
 443      */
 444     if ((ctxt->document->nbKeysComputed < ctxt->nbKeys) &&
 445         (ctxt->keyInitLevel == 0)) {
 446         /*
 447      * If non-recursive behaviour, just try to initialize all keys
 448      */
 449     if (xsltInitAllDocKeys(ctxt))
 450         return(NULL);
 451     }
 452 
 453 retry:
 454     table = (xsltKeyTablePtr) ctxt->document->keys;
 455     while (table != NULL) {
 456     if (((nameURI != NULL) == (table->nameURI != NULL)) &&
 457         xmlStrEqual(table->name, name) &&
 458         xmlStrEqual(table->nameURI, nameURI))
 459     {
 460         ret = (xmlNodeSetPtr)xmlHashLookup(table->keys, value);
 461         return(ret);
 462     }
 463     table = table->next;
 464     }
 465 
 466     if ((ctxt->keyInitLevel != 0) && (init_table == 0)) {
 467         /*
 468      * Apparently one key is recursive and this one is needed,
 469      * initialize just it, that time and retry
 470      */
 471         xsltInitDocKeyTable(ctxt, name, nameURI);
 472     init_table = 1;
 473     goto retry;
 474     }
 475 
 476     return(NULL);
 477 }
 478 
 479 
 480 /**
 481  * xsltInitDocKeyTable:
 482  *
 483  * INTERNAL ROUTINE ONLY
 484  *
 485  * Check if any keys on the current document need to be computed
 486  */
 487 static int
 488 xsltInitDocKeyTable(xsltTransformContextPtr ctxt, const xmlChar *name,
 489                     const xmlChar *nameURI)
 490 {
 491     xsltStylesheetPtr style;
 492     xsltKeyDefPtr keyd = NULL;
 493     int found = 0;
 494 
 495 #ifdef KEY_INIT_DEBUG
 496 fprintf(stderr, "xsltInitDocKeyTable %s\n", name);
 497 #endif
 498 
 499     style = ctxt->style;
 500     while (style != NULL) {
 501     keyd = (xsltKeyDefPtr) style->keys;
 502     while (keyd != NULL) {
 503         if (((keyd->nameURI != NULL) ==
 504          (nameURI != NULL)) &&
 505         xmlStrEqual(keyd->name, name) &&
 506         xmlStrEqual(keyd->nameURI, nameURI))
 507         {
 508         xsltInitCtxtKey(ctxt, ctxt->document, keyd);
 509         if (ctxt->document->nbKeysComputed == ctxt->nbKeys)
 510             return(0);
 511         found = 1;
 512         }
 513         keyd = keyd->next;
 514     }
 515     style = xsltNextImport(style);
 516     }
 517     if (found == 0) {
 518 #ifdef WITH_XSLT_DEBUG_KEYS
 519     XSLT_TRACE(ctxt,XSLT_TRACE_KEYS,xsltGenericDebug(xsltGenericDebugContext,
 520          "xsltInitDocKeyTable: did not found %s\n", name));
 521 #endif
 522     xsltTransformError(ctxt, NULL, keyd? keyd->inst : NULL,
 523         "Failed to find key definition for %s\n", name);
 524     ctxt->state = XSLT_STATE_STOPPED;
 525         return(-1);
 526     }
 527 #ifdef KEY_INIT_DEBUG
 528 fprintf(stderr, "xsltInitDocKeyTable %s done\n", name);
 529 #endif
 530     return(0);
 531 }
 532 
 533 /**
 534  * xsltInitAllDocKeys:
 535  * @ctxt: transformation context
 536  *
 537  * INTERNAL ROUTINE ONLY
 538  *
 539  * Check if any keys on the current document need to be computed
 540  *
 541  * Returns 0 in case of success, -1 in case of failure
 542  */
 543 int
 544 xsltInitAllDocKeys(xsltTransformContextPtr ctxt)
 545 {
 546     xsltStylesheetPtr style;
 547     xsltKeyDefPtr keyd;
 548     xsltKeyTablePtr table;
 549 
 550     if (ctxt == NULL)
 551     return(-1);
 552 
 553 #ifdef KEY_INIT_DEBUG
 554 fprintf(stderr, "xsltInitAllDocKeys %d %d\n",
 555         ctxt->document->nbKeysComputed, ctxt->nbKeys);
 556 #endif
 557 
 558     if (ctxt->document->nbKeysComputed == ctxt->nbKeys)
 559     return(0);
 560 
 561 
 562     /*
 563     * TODO: This could be further optimized
 564     */
 565     style = ctxt->style;
 566     while (style) {
 567     keyd = (xsltKeyDefPtr) style->keys;
 568     while (keyd != NULL) {
 569 #ifdef KEY_INIT_DEBUG
 570 fprintf(stderr, "Init key %s\n", keyd->name);
 571 #endif
 572         /*
 573         * Check if keys with this QName have been already
 574         * computed.
 575         */
 576         table = (xsltKeyTablePtr) ctxt->document->keys;
 577         while (table) {
 578         if (((keyd->nameURI != NULL) == (table->nameURI != NULL)) &&
 579             xmlStrEqual(keyd->name, table->name) &&
 580             xmlStrEqual(keyd->nameURI, table->nameURI))
 581         {
 582             break;
 583         }
 584         table = table->next;
 585         }
 586         if (table == NULL) {
 587         /*
 588         * Keys with this QName have not been yet computed.
 589         */
 590         xsltInitDocKeyTable(ctxt, keyd->name, keyd->nameURI);
 591         }
 592         keyd = keyd->next;
 593     }
 594     style = xsltNextImport(style);
 595     }
 596 #ifdef KEY_INIT_DEBUG
 597 fprintf(stderr, "xsltInitAllDocKeys: done\n");
 598 #endif
 599     return(0);
 600 }
 601 
 602 /**
 603  * xsltInitCtxtKey:
 604  * @ctxt: an XSLT transformation context
 605  * @idoc:  the document information (holds key values)
 606  * @keyDef: the key definition
 607  *
 608  * Computes the key tables this key and for the current input document.
 609  *
 610  * Returns: 0 on success, -1 on error
 611  */
 612 int
 613 xsltInitCtxtKey(xsltTransformContextPtr ctxt, xsltDocumentPtr idoc,
 614             xsltKeyDefPtr keyDef)
 615 {
 616     int i, len, k;
 617     xmlNodeSetPtr matchList = NULL, keylist;
 618     xmlXPathObjectPtr matchRes = NULL, useRes = NULL;
 619     xmlChar *str = NULL;
 620     xsltKeyTablePtr table;
 621     xmlNodePtr oldInst, cur;
 622     xmlNodePtr oldContextNode;
 623     xsltDocumentPtr oldDocInfo;
 624     int oldXPPos, oldXPSize;
 625     xmlDocPtr oldXPDoc;
 626     int oldXPNsNr;
 627     xmlNsPtr *oldXPNamespaces;
 628     xmlXPathContextPtr xpctxt;
 629 
 630 #ifdef KEY_INIT_DEBUG
 631 fprintf(stderr, "xsltInitCtxtKey %s : %d\n", keyDef->name, ctxt->keyInitLevel);
 632 #endif
 633 
 634     if ((keyDef->comp == NULL) || (keyDef->usecomp == NULL))
 635     return(-1);
 636 
 637     /*
 638      * Detect recursive keys
 639      */
 640     if (ctxt->keyInitLevel > ctxt->nbKeys) {
 641 #ifdef WITH_XSLT_DEBUG_KEYS
 642     XSLT_TRACE(ctxt,XSLT_TRACE_KEYS,
 643                xsltGenericDebug(xsltGenericDebugContext,
 644                "xsltInitCtxtKey: key definition of %s is recursive\n",
 645                keyDef->name));
 646 #endif
 647     xsltTransformError(ctxt, NULL, keyDef->inst,
 648         "Key definition for %s is recursive\n", keyDef->name);
 649     ctxt->state = XSLT_STATE_STOPPED;
 650         return(-1);
 651     }
 652     ctxt->keyInitLevel++;
 653 
 654     xpctxt = ctxt->xpathCtxt;
 655     idoc->nbKeysComputed++;
 656     /*
 657     * Save context state.
 658     */
 659     oldInst = ctxt->inst;
 660     oldDocInfo = ctxt->document;
 661     oldContextNode = ctxt->node;
 662 
 663     oldXPDoc = xpctxt->doc;
 664     oldXPPos = xpctxt->proximityPosition;
 665     oldXPSize = xpctxt->contextSize;
 666     oldXPNsNr = xpctxt->nsNr;
 667     oldXPNamespaces = xpctxt->namespaces;
 668 
 669     /*
 670     * Set up contexts.
 671     */
 672     ctxt->document = idoc;
 673     ctxt->node = (xmlNodePtr) idoc->doc;
 674     ctxt->inst = keyDef->inst;
 675 
 676     xpctxt->doc = idoc->doc;
 677     xpctxt->node = (xmlNodePtr) idoc->doc;
 678     /* TODO : clarify the use of namespaces in keys evaluation */
 679     xpctxt->namespaces = keyDef->nsList;
 680     xpctxt->nsNr = keyDef->nsNr;
 681 
 682     /*
 683     * Evaluate the 'match' expression of the xsl:key.
 684     * TODO: The 'match' is a *pattern*.
 685     */
 686     matchRes = xmlXPathCompiledEval(keyDef->comp, xpctxt);
 687     if (matchRes == NULL) {
 688 
 689 #ifdef WITH_XSLT_DEBUG_KEYS
 690     XSLT_TRACE(ctxt,XSLT_TRACE_KEYS,xsltGenericDebug(xsltGenericDebugContext,
 691          "xsltInitCtxtKey: %s evaluation failed\n", keyDef->match));
 692 #endif
 693     xsltTransformError(ctxt, NULL, keyDef->inst,
 694         "Failed to evaluate the 'match' expression.\n");
 695     ctxt->state = XSLT_STATE_STOPPED;
 696     goto error;
 697     } else {
 698     if (matchRes->type == XPATH_NODESET) {
 699         matchList = matchRes->nodesetval;
 700 
 701 #ifdef WITH_XSLT_DEBUG_KEYS
 702         if (matchList != NULL)
 703         XSLT_TRACE(ctxt,XSLT_TRACE_KEYS,xsltGenericDebug(xsltGenericDebugContext,
 704              "xsltInitCtxtKey: %s evaluates to %d nodes\n",
 705                  keyDef->match, matchList->nodeNr));
 706 #endif
 707     } else {
 708         /*
 709         * Is not a node set, but must be.
 710         */
 711 #ifdef WITH_XSLT_DEBUG_KEYS
 712         XSLT_TRACE(ctxt,XSLT_TRACE_KEYS,xsltGenericDebug(xsltGenericDebugContext,
 713          "xsltInitCtxtKey: %s is not a node set\n", keyDef->match));
 714 #endif
 715         xsltTransformError(ctxt, NULL, keyDef->inst,
 716         "The 'match' expression did not evaluate to a node set.\n");
 717         ctxt->state = XSLT_STATE_STOPPED;
 718         goto error;
 719     }
 720     }
 721     if ((matchList == NULL) || (matchList->nodeNr <= 0))
 722     goto exit;
 723 
 724     /**
 725      * Multiple key definitions for the same name are allowed, so
 726      * we must check if the key is already present for this doc
 727      */
 728     table = (xsltKeyTablePtr) idoc->keys;
 729     while (table != NULL) {
 730         if (xmlStrEqual(table->name, keyDef->name) &&
 731         (((keyDef->nameURI == NULL) && (table->nameURI == NULL)) ||
 732          ((keyDef->nameURI != NULL) && (table->nameURI != NULL) &&
 733           (xmlStrEqual(table->nameURI, keyDef->nameURI)))))
 734         break;
 735     table = table->next;
 736     }
 737     /**
 738      * If the key was not previously defined, create it now and
 739      * chain it to the list of keys for the doc
 740      */
 741     if (table == NULL) {
 742         table = xsltNewKeyTable(keyDef->name, keyDef->nameURI);
 743         if (table == NULL)
 744         goto error;
 745         table->next = idoc->keys;
 746         idoc->keys = table;
 747     }
 748 
 749     /*
 750     * SPEC XSLT 1.0 (XSLT 2.0 does not clarify the context size!)
 751     * "...the use attribute of the xsl:key element is evaluated with x as
 752     "  the current node and with a node list containing just x as the
 753     *  current node list"
 754     */
 755     xpctxt->contextSize = 1;
 756     xpctxt->proximityPosition = 1;
 757 
 758     for (i = 0; i < matchList->nodeNr; i++) {
 759     cur = matchList->nodeTab[i];
 760     if (! IS_XSLT_REAL_NODE(cur))
 761         continue;
 762     xpctxt->node = cur;
 763     /*
 764     * Process the 'use' of the xsl:key.
 765     * SPEC XSLT 1.0:
 766     * "The use attribute is an expression specifying the values of
 767     *  the key; the expression is evaluated once for each node that
 768     *  matches the pattern."
 769     */
 770     if (useRes != NULL)
 771         xmlXPathFreeObject(useRes);
 772     useRes = xmlXPathCompiledEval(keyDef->usecomp, xpctxt);
 773     if (useRes == NULL) {
 774         xsltTransformError(ctxt, NULL, keyDef->inst,
 775         "Failed to evaluate the 'use' expression.\n");
 776         ctxt->state = XSLT_STATE_STOPPED;
 777         break;
 778     }
 779     if (useRes->type == XPATH_NODESET) {
 780         if ((useRes->nodesetval != NULL) &&
 781         (useRes->nodesetval->nodeNr != 0))
 782         {
 783         len = useRes->nodesetval->nodeNr;
 784         str = xmlXPathCastNodeToString(useRes->nodesetval->nodeTab[0]);
 785         } else {
 786         continue;
 787         }
 788     } else {
 789         len = 1;
 790         if (useRes->type == XPATH_STRING) {
 791         /*
 792         * Consume the string value.
 793         */
 794         str = useRes->stringval;
 795         useRes->stringval = NULL;
 796         } else {
 797         str = xmlXPathCastToString(useRes);
 798         }
 799     }
 800     /*
 801     * Process all strings.
 802     */
 803     k = 0;
 804     while (1) {
 805         if (str == NULL)
 806         goto next_string;
 807 
 808 #ifdef WITH_XSLT_DEBUG_KEYS
 809         XSLT_TRACE(ctxt,XSLT_TRACE_KEYS,xsltGenericDebug(xsltGenericDebugContext,
 810         "xsl:key : node associated to ('%s', '%s')\n", keyDef->name, str));
 811 #endif
 812 
 813         keylist = xmlHashLookup(table->keys, str);
 814         if (keylist == NULL) {
 815         keylist = xmlXPathNodeSetCreate(cur);
 816         if (keylist == NULL)
 817             goto error;
 818         xmlHashAddEntry(table->keys, str, keylist);
 819         } else {
 820         /*
 821         * TODO: How do we know if this function failed?
 822         */
 823         xmlXPathNodeSetAdd(keylist, cur);
 824         }
 825         switch (cur->type) {
 826         case XML_ELEMENT_NODE:
 827         case XML_TEXT_NODE:
 828         case XML_CDATA_SECTION_NODE:
 829         case XML_PI_NODE:
 830         case XML_COMMENT_NODE:
 831             cur->psvi = keyDef;
 832             break;
 833         case XML_ATTRIBUTE_NODE:
 834             ((xmlAttrPtr) cur)->psvi = keyDef;
 835             break;
 836         case XML_DOCUMENT_NODE:
 837         case XML_HTML_DOCUMENT_NODE:
 838             ((xmlDocPtr) cur)->psvi = keyDef;
 839             break;
 840         default:
 841             break;
 842         }
 843         xmlFree(str);
 844         str = NULL;
 845 
 846 next_string:
 847         k++;
 848         if (k >= len)
 849         break;
 850         str = xmlXPathCastNodeToString(useRes->nodesetval->nodeTab[k]);
 851     }
 852     }
 853 
 854 exit:
 855 error:
 856     ctxt->keyInitLevel--;
 857     /*
 858     * Restore context state.
 859     */
 860     xpctxt->doc = oldXPDoc;
 861     xpctxt->nsNr = oldXPNsNr;
 862     xpctxt->namespaces = oldXPNamespaces;
 863     xpctxt->proximityPosition = oldXPPos;
 864     xpctxt->contextSize = oldXPSize;
 865 
 866     ctxt->node = oldContextNode;
 867     ctxt->document = oldDocInfo;
 868     ctxt->inst = oldInst;
 869 
 870     if (str)
 871     xmlFree(str);
 872     if (useRes != NULL)
 873     xmlXPathFreeObject(useRes);
 874     if (matchRes != NULL)
 875     xmlXPathFreeObject(matchRes);
 876     return(0);
 877 }
 878 
 879 /**
 880  * xsltInitCtxtKeys:
 881  * @ctxt:  an XSLT transformation context
 882  * @idoc:  a document info
 883  *
 884  * Computes all the keys tables for the current input document.
 885  * Should be done before global varibales are initialized.
 886  * NOTE: Not used anymore in the refactored code.
 887  */
 888 void
 889 xsltInitCtxtKeys(xsltTransformContextPtr ctxt, xsltDocumentPtr idoc) {
 890     xsltStylesheetPtr style;
 891     xsltKeyDefPtr keyDef;
 892 
 893     if ((ctxt == NULL) || (idoc == NULL))
 894     return;
 895 
 896 #ifdef KEY_INIT_DEBUG
 897 fprintf(stderr, "xsltInitCtxtKeys on document\n");
 898 #endif
 899 
 900 #ifdef WITH_XSLT_DEBUG_KEYS
 901     if ((idoc->doc != NULL) && (idoc->doc->URL != NULL))
 902     XSLT_TRACE(ctxt,XSLT_TRACE_KEYS,xsltGenericDebug(xsltGenericDebugContext, "Initializing keys on %s\n",
 903              idoc->doc->URL));
 904 #endif
 905     style = ctxt->style;
 906     while (style != NULL) {
 907     keyDef = (xsltKeyDefPtr) style->keys;
 908     while (keyDef != NULL) {
 909         xsltInitCtxtKey(ctxt, idoc, keyDef);
 910 
 911         keyDef = keyDef->next;
 912     }
 913 
 914     style = xsltNextImport(style);
 915     }
 916 
 917 #ifdef KEY_INIT_DEBUG
 918 fprintf(stderr, "xsltInitCtxtKeys on document: done\n");
 919 #endif
 920 
 921 }
 922 
 923 /**
 924  * xsltFreeDocumentKeys:
 925  * @idoc: a XSLT document
 926  *
 927  * Free the keys associated to a document
 928  */
 929 void
 930 xsltFreeDocumentKeys(xsltDocumentPtr idoc) {
 931     if (idoc != NULL)
 932         xsltFreeKeyTableList(idoc->keys);
 933 }
 934