source: trunk/third/libxslt/libxslt/keys.c @ 19102

/*
 * keys.c: Implemetation of the keys support
 *
 * Reference:
 *   http://www.w3.org/TR/1999/REC-xslt-19991116
 *
 * See Copyright for the status of this software.
 *
 * daniel@veillard.com
 */

#define IN_LIBXSLT
#include "libxslt.h"

#include <string.h>

#include <libxml/xmlmemory.h>
#include <libxml/tree.h>
#include <libxml/valid.h>
#include <libxml/hash.h>
#include <libxml/xmlerror.h>
#include <libxml/parserInternals.h>
#include <libxml/xpathInternals.h>
#include "xslt.h"
#include "xsltInternals.h"
#include "xsltutils.h"
#include "imports.h"
#include "templates.h"
#include "keys.h"

#ifdef WITH_XSLT_DEBUG
#define WITH_XSLT_DEBUG_KEYS
#endif

typedef struct _xsltKeyDef xsltKeyDef;
typedef xsltKeyDef *xsltKeyDefPtr;
struct _xsltKeyDef {
    struct _xsltKeyDef *next;
    xmlNodePtr inst;
    xmlChar *name;
    xmlChar *nameURI;
    xmlChar *match;
    xmlChar *use;
    xmlXPathCompExprPtr comp;
    xmlXPathCompExprPtr usecomp;
};

typedef struct _xsltKeyTable xsltKeyTable;
typedef xsltKeyTable *xsltKeyTablePtr;
struct _xsltKeyTable {
    struct _xsltKeyTable *next;
    xmlChar *name;
    xmlChar *nameURI;
    xmlHashTablePtr keys;
};


/************************************************************************
 *                                                                      *
 *                      Type functions                                  *
 *                                                                      *
 ************************************************************************/

/**
 * xsltNewKeyDef:
 * @name:  the key name or NULL
 * @nameURI:  the name URI or NULL
 *
 * Create a new XSLT KeyDef
 *
 * Returns the newly allocated xsltKeyDefPtr or NULL in case of error
 */
static xsltKeyDefPtr
xsltNewKeyDef(const xmlChar *name, const xmlChar *nameURI) {
    xsltKeyDefPtr cur;

    cur = (xsltKeyDefPtr) xmlMalloc(sizeof(xsltKeyDef));
    if (cur == NULL) {
        xsltTransformError(NULL, NULL, NULL,
                "xsltNewKeyDef : malloc failed\n");
        return(NULL);
    }
    memset(cur, 0, sizeof(xsltKeyDef));
    if (name != NULL)
        cur->name = xmlStrdup(name);
    if (nameURI != NULL)
        cur->nameURI = xmlStrdup(nameURI);
    return(cur);
}

/**
 * xsltFreeKeyDef:
 * @keyd:  an XSLT key definition
 *
 * Free up the memory allocated by @keyd
 */
static void
xsltFreeKeyDef(xsltKeyDefPtr keyd) {
    if (keyd == NULL)
        return;
    if (keyd->comp != NULL)
        xmlXPathFreeCompExpr(keyd->comp);
    if (keyd->usecomp != NULL)
        xmlXPathFreeCompExpr(keyd->usecomp);
    if (keyd->name != NULL)
        xmlFree(keyd->name);
    if (keyd->nameURI != NULL)
        xmlFree(keyd->nameURI);
    if (keyd->match != NULL)
        xmlFree(keyd->match);
    if (keyd->use != NULL)
        xmlFree(keyd->use);
    memset(keyd, -1, sizeof(xsltKeyDef));
    xmlFree(keyd);
}

/**
 * xsltFreeKeyDefList:
 * @keyd:  an XSLT key definition list
 *
 * Free up the memory allocated by all the elements of @keyd
 */
static void
xsltFreeKeyDefList(xsltKeyDefPtr keyd) {
    xsltKeyDefPtr cur;

    while (keyd != NULL) {
        cur = keyd;
        keyd = keyd->next;
        xsltFreeKeyDef(cur);
    }
}

/**
 * xsltNewKeyTable:
 * @name:  the key name or NULL
 * @nameURI:  the name URI or NULL
 *
 * Create a new XSLT KeyTable
 *
 * Returns the newly allocated xsltKeyTablePtr or NULL in case of error
 */
static xsltKeyTablePtr
xsltNewKeyTable(const xmlChar *name, const xmlChar *nameURI) {
    xsltKeyTablePtr cur;

    cur = (xsltKeyTablePtr) xmlMalloc(sizeof(xsltKeyTable));
    if (cur == NULL) {
        xsltTransformError(NULL, NULL, NULL,
                "xsltNewKeyTable : malloc failed\n");
        return(NULL);
    }
    memset(cur, 0, sizeof(xsltKeyTable));
    if (name != NULL)
        cur->name = xmlStrdup(name);
    if (nameURI != NULL)
        cur->nameURI = xmlStrdup(nameURI);
    cur->keys = xmlHashCreate(0);
    return(cur);
}

/**
 * xsltFreeKeyTable:
 * @keyt:  an XSLT key table
 *
 * Free up the memory allocated by @keyt
 */
static void
xsltFreeKeyTable(xsltKeyTablePtr keyt) {
    if (keyt == NULL)
        return;
    if (keyt->name != NULL)
        xmlFree(keyt->name);
    if (keyt->nameURI != NULL)
        xmlFree(keyt->nameURI);
    if (keyt->keys != NULL)
        xmlHashFree(keyt->keys, 
                    (xmlHashDeallocator) xmlXPathFreeNodeSet);
    memset(keyt, -1, sizeof(xsltKeyTable));
    xmlFree(keyt);
}

/**
 * xsltFreeKeyTableList:
 * @keyt:  an XSLT key table list
 *
 * Free up the memory allocated by all the elements of @keyt
 */
static void
xsltFreeKeyTableList(xsltKeyTablePtr keyt) {
    xsltKeyTablePtr cur;

    while (keyt != NULL) {
        cur = keyt;
        keyt = keyt->next;
        xsltFreeKeyTable(cur);
    }
}

/************************************************************************
 *                                                                      *
 *              The interpreter for the precompiled patterns            *
 *                                                                      *
 ************************************************************************/


/**
 * xsltFreeKeys:
 * @style: an XSLT stylesheet
 *
 * Free up the memory used by XSLT keys in a stylesheet
 */
void
xsltFreeKeys(xsltStylesheetPtr style) {
    if (style->keys)
        xsltFreeKeyDefList((xsltKeyDefPtr) style->keys);
}

/**
 * xsltAddKey:
 * @style: an XSLT stylesheet
 * @name:  the key name or NULL
 * @nameURI:  the name URI or NULL
 * @match:  the match value
 * @use:  the use value
 * @inst: the key instruction
 *
 * add a key definition to a stylesheet
 *
 * Returns 0 in case of success, and -1 in case of failure.
 */
int     
xsltAddKey(xsltStylesheetPtr style, const xmlChar *name,
           const xmlChar *nameURI, const xmlChar *match,
           const xmlChar *use, xmlNodePtr inst) {
    xsltKeyDefPtr key;
    xmlChar *pattern = NULL;
    int current, end, start;

    if ((style == NULL) || (name == NULL) || (match == NULL) || (use == NULL))
        return(-1);

#ifdef WITH_XSLT_DEBUG_KEYS
    xsltGenericDebug(xsltGenericDebugContext,
        "Add key %s, match %s, use %s\n", name, match, use);
#endif

    key = xsltNewKeyDef(name, nameURI);
    key->match = xmlStrdup(match);
    key->use = xmlStrdup(use);
    key->inst = inst;

    /*
     * Split the | and register it as as many keys
     */
    current = end = 0;
    while (match[current] != 0) {
        start = current;
        while (IS_BLANK(match[current]))
            current++;
        end = current;
        while ((match[end] != 0) && (match[end] != '|')) {
            end++;
        }
        if (current == end) {
            xsltTransformError(NULL, style, inst,
                             "key pattern is empty\n");
            if (style != NULL) style->errors++;
            goto error;
        }
        if (match[start] != '/') {
            pattern = xmlStrcat(pattern, (xmlChar *)"//");
            if (pattern == NULL) {
                if (style != NULL) style->errors++;
                goto error;
            }
        }
        pattern = xmlStrncat(pattern, &match[start], end - start);
        if (pattern == NULL) {
            if (style != NULL) style->errors++;
            goto error;
        }

        if (match[end] == '|') {
            pattern = xmlStrcat(pattern, (xmlChar *)"|");
            end++;
        }
        current = end;
    }
#ifdef WITH_XSLT_DEBUG_KEYS
    xsltGenericDebug(xsltGenericDebugContext,
        "   resulting pattern %s\n", pattern);
#endif
    key->comp = xmlXPathCompile(pattern);
    if (key->comp == NULL) {
        xsltTransformError(NULL, style, inst,
                "xsl:key : XPath pattern compilation failed '%s'\n",
                         pattern);
        if (style != NULL) style->errors++;
    }
    key->usecomp = xmlXPathCompile(use);
    if (key->usecomp == NULL) {
        xsltTransformError(NULL, style, inst,
                "xsl:key : XPath pattern compilation failed '%s'\n",
                         use);
        if (style != NULL) style->errors++;
    }
    key->next = style->keys;
    style->keys = key;
error:
    if (pattern != NULL)
        xmlFree(pattern);
    return(0);
}

/**
 * xsltGetKey:
 * @ctxt: an XSLT transformation context
 * @name:  the key name or NULL
 * @nameURI:  the name URI or NULL
 * @value:  the key value to look for
 *
 * Lookup a key
 *
 * Returns the nodeset resulting from the query or NULL
 */
xmlNodeSetPtr
xsltGetKey(xsltTransformContextPtr ctxt, const xmlChar *name,
           const xmlChar *nameURI, const xmlChar *value) {
    xmlNodeSetPtr ret;
    xsltKeyTablePtr table;

    if ((ctxt == NULL) || (name == NULL) || (value == NULL))
        return(NULL);

#ifdef WITH_XSLT_DEBUG_KEYS
    xsltGenericDebug(xsltGenericDebugContext,
        "Get key %s, value %s\n", name, value);
#endif
    table = (xsltKeyTablePtr) ctxt->document->keys;
    while (table != NULL) {
        if (xmlStrEqual(table->name, name) &&
            (((nameURI == NULL) && (table->nameURI == NULL)) ||
             ((nameURI != NULL) && (table->nameURI != NULL) &&
              (xmlStrEqual(table->nameURI, nameURI))))) {
            ret = (xmlNodeSetPtr)xmlHashLookup(table->keys, value);
            return(ret);
        }
        table = table->next;
    }
    return(NULL);
}

/**
 * xsltEvalXPathKeys:
 * @ctxt:  the XSLT transformation context
 * @comp:  the compiled XPath expression
 *
 * Process the expression using XPath to get the list of keys
 *
 * Returns the array of computed string value or NULL, must be deallocated
 *         by the caller.
 */
static xmlChar **
xsltEvalXPathKeys(xsltTransformContextPtr ctxt, xmlXPathCompExprPtr comp) {
    xmlChar **ret = NULL;
    xmlXPathObjectPtr res;
    xmlNodePtr oldInst;
    xmlNodePtr oldNode;
    int oldPos, oldSize;
    int oldNsNr;
    xmlNsPtr *oldNamespaces;

    oldInst = ctxt->inst;
    oldNode = ctxt->node;
    oldPos = ctxt->xpathCtxt->proximityPosition;
    oldSize = ctxt->xpathCtxt->contextSize;
    oldNsNr = ctxt->xpathCtxt->nsNr;
    oldNamespaces = ctxt->xpathCtxt->namespaces;

    ctxt->xpathCtxt->node = ctxt->node;
    /* TODO: do we need to propagate the namespaces here ? */
    ctxt->xpathCtxt->namespaces = NULL;
    ctxt->xpathCtxt->nsNr = 0;
    res = xmlXPathCompiledEval(comp, ctxt->xpathCtxt);
    if (res != NULL) {
        if (res->type == XPATH_NODESET) {
            int len, i, j;

            if (res->nodesetval != NULL)
                len = res->nodesetval->nodeNr;
            else
                len = 0;
            if (len != 0) {
                ret = (xmlChar **) xmlMalloc((len + 1) * sizeof(xmlChar *));
                if (ret != NULL) {
                    for (i = 0,j = 0;i < len;i++) {
                        ret[j] = xmlXPathCastNodeToString(
                                res->nodesetval->nodeTab[i]);
                        if (ret[j] != NULL)
                            j++;
                    }
                    ret[j] = NULL;
                }
            }
        } else {
            if (res->type != XPATH_STRING)
                res = xmlXPathConvertString(res);
            if (res->type == XPATH_STRING) {
                ret = (xmlChar **) xmlMalloc(2 * sizeof(xmlChar *));
                if (ret != NULL) {
                    ret[0] = res->stringval;
                    ret[1] = NULL;
                    res->stringval = NULL;
                }
            } else {
                xsltTransformError(ctxt, NULL, NULL,
                     "xpath : string() function didn't return a String\n");
            }
        }
        xmlXPathFreeObject(res);
    } else {
        ctxt->state = XSLT_STATE_STOPPED;
    }
#ifdef WITH_XSLT_DEBUG_TEMPLATES
    xsltGenericDebug(xsltGenericDebugContext,
         "xsltEvalXPathString: returns %s\n", ret);
#endif
    ctxt->inst = oldInst;
    ctxt->node = oldNode;
    ctxt->xpathCtxt->contextSize = oldSize;
    ctxt->xpathCtxt->proximityPosition = oldPos;
    ctxt->xpathCtxt->nsNr = oldNsNr;
    ctxt->xpathCtxt->namespaces = oldNamespaces;
    return(ret);
}
/**
 * xsltInitCtxtKey:
 * @ctxt: an XSLT transformation context
 * @doc:  an XSLT document
 * @keyd: the key definition
 *
 * Computes the key tables this key and for the current input document.
 */
static void
xsltInitCtxtKey(xsltTransformContextPtr ctxt, xsltDocumentPtr doc,
                xsltKeyDefPtr keyd) {
    int i;
    xmlNodeSetPtr nodelist = NULL, keylist;
    xmlXPathObjectPtr res = NULL;
    xmlChar *str, **list;
    xsltKeyTablePtr table;
    int oldPos, oldSize;
    xmlNodePtr oldInst;
    xsltDocumentPtr oldDoc;
    xmlDocPtr oldXDoc;
    int oldNsNr;
    xmlNsPtr *oldNamespaces;

    /*
     * Evaluate the nodelist
     */

    oldXDoc= ctxt->xpathCtxt->doc;
    oldPos = ctxt->xpathCtxt->proximityPosition;
    oldSize = ctxt->xpathCtxt->contextSize;
    oldInst = ctxt->inst;
    oldDoc = ctxt->document;
    oldNsNr = ctxt->xpathCtxt->nsNr;
    oldNamespaces = ctxt->xpathCtxt->namespaces;

    if (keyd->comp == NULL)
        goto error;
    if (keyd->usecomp == NULL)
        goto error;

    ctxt->document = doc;
    ctxt->xpathCtxt->doc = doc->doc;
    ctxt->xpathCtxt->node = (xmlNodePtr) doc->doc;
    ctxt->node = (xmlNodePtr) doc->doc;
    /* TODO : clarify the use of namespaces in keys evaluation */
    ctxt->xpathCtxt->namespaces = NULL;
    ctxt->xpathCtxt->nsNr = 0;
    ctxt->inst = keyd->inst;
    res = xmlXPathCompiledEval(keyd->comp, ctxt->xpathCtxt);
    ctxt->xpathCtxt->contextSize = oldSize;
    ctxt->xpathCtxt->proximityPosition = oldPos;
    ctxt->inst = oldInst;

    if (res != NULL) {
        if (res->type == XPATH_NODESET) {
            nodelist = res->nodesetval;
#ifdef WITH_XSLT_DEBUG_KEYS
            if (nodelist != NULL)
                xsltGenericDebug(xsltGenericDebugContext,
                     "xsltInitCtxtKey: %s evaluates to %d nodes\n",
                                 keyd->match, nodelist->nodeNr);
#endif
        } else {
#ifdef WITH_XSLT_DEBUG_KEYS
            xsltGenericDebug(xsltGenericDebugContext,
                 "xsltInitCtxtKey: %s is not a node set\n", keyd->match);
#endif
            goto error;
        }
    } else {
#ifdef WITH_XSLT_DEBUG_KEYS
        xsltGenericDebug(xsltGenericDebugContext,
             "xsltInitCtxtKey: %s evaluation failed\n", keyd->match);
#endif
        ctxt->state = XSLT_STATE_STOPPED;
        goto error;
    }

    /*
     * for each node in the list evaluate the key and insert the node
     */
    if ((nodelist == NULL) || (nodelist->nodeNr <= 0))
        goto error;

    table = xsltNewKeyTable(keyd->name, keyd->nameURI);
    if (table == NULL)
        goto error;

    for (i = 0;i < nodelist->nodeNr;i++) {
        if (IS_XSLT_REAL_NODE(nodelist->nodeTab[i])) {
            ctxt->node = nodelist->nodeTab[i];

            list = xsltEvalXPathKeys(ctxt, keyd->usecomp);
            if (list != NULL) {
                int index = 0;

                str = list[index++];
                while (str != NULL) {
#ifdef WITH_XSLT_DEBUG_KEYS
                    xsltGenericDebug(xsltGenericDebugContext,
                         "xsl:key : node associated to(%s,%s)\n",
                                     keyd->name, str);
#endif
                    keylist = xmlHashLookup(table->keys, str);
                    if (keylist == NULL) {
                        keylist = xmlXPathNodeSetCreate(nodelist->nodeTab[i]);
                        xmlHashAddEntry(table->keys, str, keylist);
                    } else {
                        xmlXPathNodeSetAdd(keylist, nodelist->nodeTab[i]);
                    }
                    nodelist->nodeTab[i]->_private = keyd;
                    xmlFree(str);
                    str = list[index++];
                }
                xmlFree(list);
#ifdef WITH_XSLT_DEBUG_KEYS
            } else {
                xsltGenericDebug(xsltGenericDebugContext,
                     "xsl:key : use %s failed to return strings\n",
                                 keyd->use);
#endif
            }
        }
    }

    table->next = doc->keys;
    doc->keys = table;

error:
    ctxt->document = oldDoc;
    ctxt->xpathCtxt->doc = oldXDoc;
    ctxt->xpathCtxt->nsNr = oldNsNr;
    ctxt->xpathCtxt->namespaces = oldNamespaces;
    if (res != NULL)
        xmlXPathFreeObject(res);
}

/**
 * xsltInitCtxtKeys:
 * @ctxt:  an XSLT transformation context
 * @doc:  an XSLT document
 *
 * Computes all the keys tables for the current input document.
 * Should be done before global varibales are initialized.
 */
void
xsltInitCtxtKeys(xsltTransformContextPtr ctxt, xsltDocumentPtr doc) {
    xsltStylesheetPtr style;
    xsltKeyDefPtr keyd;

    if ((ctxt == NULL) || (doc == NULL))
        return;
#ifdef WITH_XSLT_DEBUG_KEYS
    if ((doc->doc != NULL) && (doc->doc->URL != NULL))
        xsltGenericDebug(xsltGenericDebugContext, "Initializing keys on %s\n",
                     doc->doc->URL);
#endif
    style = ctxt->style;
    while (style != NULL) {
        keyd = (xsltKeyDefPtr) style->keys;
        while (keyd != NULL) {
            xsltInitCtxtKey(ctxt, doc, keyd);

            keyd = keyd->next;
        }

        style = xsltNextImport(style);
    }
}

/**
 * xsltFreeDocumentKeys:
 * @doc: a XSLT document
 *
 * Free the keys associated to a document
 */
void    
xsltFreeDocumentKeys(xsltDocumentPtr doc) {
    if (doc != NULL)
        xsltFreeKeyTableList(doc->keys);
}