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