xpath.c

Go to the documentation of this file.

/*
 * xpath.c: XML Path Language implementation
 *          XPath is a language for addressing parts of an XML document,
 *          designed to be used by both XSLT and XPointer
 *
 * Reference: W3C Recommendation 16 November 1999
 *     http://www.w3.org/TR/1999/REC-xpath-19991116
 * Public reference:
 *     http://www.w3.org/TR/xpath
 *
 * See Copyright for the status of this software
 *
 * Author: daniel@veillard.com
 *
 */

/* To avoid EBCDIC trouble when parsing on zOS */
#if defined(__MVS__)
#pragma convert("ISO8859-1")
#endif

#define IN_LIBXML
#include "libxml.h"

#include <limits.h>
#include <string.h>
#include <stddef.h>

#ifdef HAVE_SYS_TYPES_H
#include <sys/types.h>
#endif
#ifdef HAVE_MATH_H
#include <math.h>
#endif
#ifdef HAVE_FLOAT_H
#include <float.h>
#endif
#ifdef HAVE_CTYPE_H
#include <ctype.h>
#endif
#ifdef HAVE_SIGNAL_H
#include <signal.h>
#endif

#include <libxml/xmlmemory.h>
#include <libxml/tree.h>
#include <libxml/valid.h>
#include <libxml/xpath.h>
#include <libxml/xpathInternals.h>
#include <libxml/parserInternals.h>
#include <libxml/hash.h>
#ifdef LIBXML_XPTR_ENABLED
#include <libxml/xpointer.h>
#endif
#ifdef LIBXML_DEBUG_ENABLED
#include <libxml/debugXML.h>
#endif
#include <libxml/xmlerror.h>
#include <libxml/threads.h>
#include <libxml/globals.h>
#ifdef LIBXML_PATTERN_ENABLED
#include <libxml/pattern.h>
#endif

#include "buf.h"

#ifdef LIBXML_PATTERN_ENABLED
#define XPATH_STREAMING
#endif

#define TODO                                \
    xmlGenericError(xmlGenericErrorContext,             \
        "Unimplemented block at %s:%d\n",               \
            __FILE__, __LINE__);

#define WITH_TIM_SORT

/*
* XP_OPTIMIZED_NON_ELEM_COMPARISON:
* If defined, this will use xmlXPathCmpNodesExt() instead of
* xmlXPathCmpNodes(). The new function is optimized comparison of
* non-element nodes; actually it will speed up comparison only if
* xmlXPathOrderDocElems() was called in order to index the elements of
* a tree in document order; Libxslt does such an indexing, thus it will
* benefit from this optimization.
*/
#define XP_OPTIMIZED_NON_ELEM_COMPARISON

/*
* XP_OPTIMIZED_FILTER_FIRST:
* If defined, this will optimize expressions like "key('foo', 'val')[b][1]"
* in a way, that it stop evaluation at the first node.
*/
#define XP_OPTIMIZED_FILTER_FIRST

/*
* XP_DEBUG_OBJ_USAGE:
* Internal flag to enable tracking of how much XPath objects have been
* created.
*/
/* #define XP_DEBUG_OBJ_USAGE */

/*
 * XPATH_MAX_STEPS:
 * when compiling an XPath expression we arbitrary limit the maximum
 * number of step operation in the compiled expression. 1000000 is
 * an insanely large value which should never be reached under normal
 * circumstances
 */
#define XPATH_MAX_STEPS 1000000

/*
 * XPATH_MAX_STACK_DEPTH:
 * when evaluating an XPath expression we arbitrary limit the maximum
 * number of object allowed to be pushed on the stack. 1000000 is
 * an insanely large value which should never be reached under normal
 * circumstances
 */
#define XPATH_MAX_STACK_DEPTH 1000000

/*
 * XPATH_MAX_NODESET_LENGTH:
 * when evaluating an XPath expression nodesets are created and we
 * arbitrary limit the maximum length of those node set. 10000000 is
 * an insanely large value which should never be reached under normal
 * circumstances, one would first need to construct an in memory tree
 * with more than 10 millions nodes.
 */
#define XPATH_MAX_NODESET_LENGTH 10000000

/*
 * XPATH_MAX_RECRUSION_DEPTH:
 * Maximum amount of nested functions calls when parsing or evaluating
 * expressions
 */
#ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION
#define XPATH_MAX_RECURSION_DEPTH 500
#else
#define XPATH_MAX_RECURSION_DEPTH 5000
#endif

/*
 * TODO:
 * There are a few spots where some tests are done which depend upon ascii
 * data.  These should be enhanced for full UTF8 support (see particularly
 * any use of the macros IS_ASCII_CHARACTER and IS_ASCII_DIGIT)
 */

#ifdef XP_OPTIMIZED_NON_ELEM_COMPARISON

static int
xmlXPathCmpNodesExt(xmlNodePtr node1, xmlNodePtr node2) {
    int depth1, depth2;
    int misc = 0, precedence1 = 0, precedence2 = 0;
    xmlNodePtr miscNode1 = NULL, miscNode2 = NULL;
    xmlNodePtr cur, root;
    ptrdiff_t l1, l2;

    if ((node1 == NULL) || (node2 == NULL))
    return(-2);

    if (node1 == node2)
    return(0);

    /*
     * a couple of optimizations which will avoid computations in most cases
     */
    switch (node1->type) {
    case XML_ELEMENT_NODE:
        if (node2->type == XML_ELEMENT_NODE) {
        if ((0 > (ptrdiff_t) node1->content) &&
            (0 > (ptrdiff_t) node2->content) &&
            (node1->doc == node2->doc))
        {
            l1 = -((ptrdiff_t) node1->content);
            l2 = -((ptrdiff_t) node2->content);
            if (l1 < l2)
            return(1);
            if (l1 > l2)
            return(-1);
        } else
            goto turtle_comparison;
        }
        break;
    case XML_ATTRIBUTE_NODE:
        precedence1 = 1; /* element is owner */
        miscNode1 = node1;
        node1 = node1->parent;
        misc = 1;
        break;
    case XML_TEXT_NODE:
    case XML_CDATA_SECTION_NODE:
    case XML_COMMENT_NODE:
    case XML_PI_NODE: {
        miscNode1 = node1;
        /*
        * Find nearest element node.
        */
        if (node1->prev != NULL) {
        do {
            node1 = node1->prev;
            if (node1->type == XML_ELEMENT_NODE) {
            precedence1 = 3; /* element in prev-sibl axis */
            break;
            }
            if (node1->prev == NULL) {
            precedence1 = 2; /* element is parent */
            /*
            * URGENT TODO: Are there any cases, where the
            * parent of such a node is not an element node?
            */
            node1 = node1->parent;
            break;
            }
        } while (1);
        } else {
        precedence1 = 2; /* element is parent */
        node1 = node1->parent;
        }
        if ((node1 == NULL) || (node1->type != XML_ELEMENT_NODE) ||
        (0 <= (ptrdiff_t) node1->content)) {
        /*
        * Fallback for whatever case.
        */
        node1 = miscNode1;
        precedence1 = 0;
        } else
        misc = 1;
    }
        break;
    case XML_NAMESPACE_DECL:
        /*
        * TODO: why do we return 1 for namespace nodes?
        */
        return(1);
    default:
        break;
    }
    switch (node2->type) {
    case XML_ELEMENT_NODE:
        break;
    case XML_ATTRIBUTE_NODE:
        precedence2 = 1; /* element is owner */
        miscNode2 = node2;
        node2 = node2->parent;
        misc = 1;
        break;
    case XML_TEXT_NODE:
    case XML_CDATA_SECTION_NODE:
    case XML_COMMENT_NODE:
    case XML_PI_NODE: {
        miscNode2 = node2;
        if (node2->prev != NULL) {
        do {
            node2 = node2->prev;
            if (node2->type == XML_ELEMENT_NODE) {
            precedence2 = 3; /* element in prev-sibl axis */
            break;
            }
            if (node2->prev == NULL) {
            precedence2 = 2; /* element is parent */
            node2 = node2->parent;
            break;
            }
        } while (1);
        } else {
        precedence2 = 2; /* element is parent */
        node2 = node2->parent;
        }
        if ((node2 == NULL) || (node2->type != XML_ELEMENT_NODE) ||
        (0 <= (ptrdiff_t) node2->content))
        {
        node2 = miscNode2;
        precedence2 = 0;
        } else
        misc = 1;
    }
        break;
    case XML_NAMESPACE_DECL:
        return(1);
    default:
        break;
    }
    if (misc) {
    if (node1 == node2) {
        if (precedence1 == precedence2) {
        /*
        * The ugly case; but normally there aren't many
        * adjacent non-element nodes around.
        */
        cur = miscNode2->prev;
        while (cur != NULL) {
            if (cur == miscNode1)
            return(1);
            if (cur->type == XML_ELEMENT_NODE)
            return(-1);
            cur = cur->prev;
        }
        return (-1);
        } else {
        /*
        * Evaluate based on higher precedence wrt to the element.
        * TODO: This assumes attributes are sorted before content.
        *   Is this 100% correct?
        */
        if (precedence1 < precedence2)
            return(1);
        else
            return(-1);
        }
    }
    /*
    * Special case: One of the helper-elements is contained by the other.
    * <foo>
    *   <node2>
    *     <node1>Text-1(precedence1 == 2)</node1>
    *   </node2>
    *   Text-6(precedence2 == 3)
    * </foo>
    */
    if ((precedence2 == 3) && (precedence1 > 1)) {
        cur = node1->parent;
        while (cur) {
        if (cur == node2)
            return(1);
        cur = cur->parent;
        }
    }
    if ((precedence1 == 3) && (precedence2 > 1)) {
        cur = node2->parent;
        while (cur) {
        if (cur == node1)
            return(-1);
        cur = cur->parent;
        }
    }
    }

    /*
     * Speedup using document order if available.
     */
    if ((node1->type == XML_ELEMENT_NODE) &&
    (node2->type == XML_ELEMENT_NODE) &&
    (0 > (ptrdiff_t) node1->content) &&
    (0 > (ptrdiff_t) node2->content) &&
    (node1->doc == node2->doc)) {

    l1 = -((ptrdiff_t) node1->content);
    l2 = -((ptrdiff_t) node2->content);
    if (l1 < l2)
        return(1);
    if (l1 > l2)
        return(-1);
    }

turtle_comparison:

    if (node1 == node2->prev)
    return(1);
    if (node1 == node2->next)
    return(-1);
    /*
     * compute depth to root
     */
    for (depth2 = 0, cur = node2; cur->parent != NULL; cur = cur->parent) {
    if (cur->parent == node1)
        return(1);
    depth2++;
    }
    root = cur;
    for (depth1 = 0, cur = node1; cur->parent != NULL; cur = cur->parent) {
    if (cur->parent == node2)
        return(-1);
    depth1++;
    }
    /*
     * Distinct document (or distinct entities :-( ) case.
     */
    if (root != cur) {
    return(-2);
    }
    /*
     * get the nearest common ancestor.
     */
    while (depth1 > depth2) {
    depth1--;
    node1 = node1->parent;
    }
    while (depth2 > depth1) {
    depth2--;
    node2 = node2->parent;
    }
    while (node1->parent != node2->parent) {
    node1 = node1->parent;
    node2 = node2->parent;
    /* should not happen but just in case ... */
    if ((node1 == NULL) || (node2 == NULL))
        return(-2);
    }
    /*
     * Find who's first.
     */
    if (node1 == node2->prev)
    return(1);
    if (node1 == node2->next)
    return(-1);
    /*
     * Speedup using document order if available.
     */
    if ((node1->type == XML_ELEMENT_NODE) &&
    (node2->type == XML_ELEMENT_NODE) &&
    (0 > (ptrdiff_t) node1->content) &&
    (0 > (ptrdiff_t) node2->content) &&
    (node1->doc == node2->doc)) {

    l1 = -((ptrdiff_t) node1->content);
    l2 = -((ptrdiff_t) node2->content);
    if (l1 < l2)
        return(1);
    if (l1 > l2)
        return(-1);
    }

    for (cur = node1->next;cur != NULL;cur = cur->next)
    if (cur == node2)
        return(1);
    return(-1); /* assume there is no sibling list corruption */
}
#endif /* XP_OPTIMIZED_NON_ELEM_COMPARISON */

/*
 * Wrapper for the Timsort algorithm from timsort.h
 */
#ifdef WITH_TIM_SORT
#define SORT_NAME libxml_domnode
#define SORT_TYPE xmlNodePtr

static
int wrap_cmp( xmlNodePtr x, xmlNodePtr y );
#ifdef XP_OPTIMIZED_NON_ELEM_COMPARISON
    static int wrap_cmp( xmlNodePtr x, xmlNodePtr y )
    {
        int res = xmlXPathCmpNodesExt(x, y);
        return res == -2 ? res : -res;
    }
#else
    static int wrap_cmp( xmlNodePtr x, xmlNodePtr y )
    {
        int res = xmlXPathCmpNodes(x, y);
        return res == -2 ? res : -res;
    }
#endif
#define SORT_CMP(x, y)  (wrap_cmp(x, y))
#include "timsort.h"
#endif /* WITH_TIM_SORT */

#if defined(LIBXML_XPATH_ENABLED) || defined(LIBXML_SCHEMAS_ENABLED)

/************************************************************************
 *                                  *
 *          Floating point stuff                *
 *                                  *
 ************************************************************************/

double xmlXPathNAN;
double xmlXPathPINF;
double xmlXPathNINF;

ATTRIBUTE_NO_SANITIZE("float-divide-by-zero")
void
xmlXPathInit(void) {
    /* MSVC doesn't allow division by zero in constant expressions. */
    double zero = 0.0;
    xmlXPathNAN = 0.0 / zero;
    xmlXPathPINF = 1.0 / zero;
    xmlXPathNINF = -xmlXPathPINF;
}

int
xmlXPathIsNaN(double val) {
#ifdef isnan
    return isnan(val);
#else
    return !(val == val);
#endif
}

int
xmlXPathIsInf(double val) {
#ifdef isinf
    return isinf(val) ? (val > 0 ? 1 : -1) : 0;
#else
    if (val >= xmlXPathPINF)
        return 1;
    if (val <= -xmlXPathPINF)
        return -1;
    return 0;
#endif
}

#endif /* SCHEMAS or XPATH */

#ifdef LIBXML_XPATH_ENABLED

/*
 * TODO: when compatibility allows remove all "fake node libxslt" strings
 *       the test should just be name[0] = ' '
 */
#ifdef DEBUG_XPATH_EXPRESSION
#define DEBUG_STEP
#define DEBUG_EXPR
#define DEBUG_EVAL_COUNTS
#endif

static xmlNs xmlXPathXMLNamespaceStruct = {
    NULL,
    XML_NAMESPACE_DECL,
    XML_XML_NAMESPACE,
    BAD_CAST "xml",
    NULL,
    NULL
};
static xmlNsPtr xmlXPathXMLNamespace = &xmlXPathXMLNamespaceStruct;
#ifndef LIBXML_THREAD_ENABLED
/*
 * Optimizer is disabled only when threaded apps are detected while
 * the library ain't compiled for thread safety.
 */
static int xmlXPathDisableOptimizer = 0;
#endif

/************************************************************************
 *                                  *
 *          Error handling routines             *
 *                                  *
 ************************************************************************/

#define XP_ERRORNULL(X)                         \
    { xmlXPathErr(ctxt, X); return(NULL); }

/*
 * The array xmlXPathErrorMessages corresponds to the enum xmlXPathError
 */
static const char *xmlXPathErrorMessages[] = {
    "Ok\n",
    "Number encoding\n",
    "Unfinished literal\n",
    "Start of literal\n",
    "Expected $ for variable reference\n",
    "Undefined variable\n",
    "Invalid predicate\n",
    "Invalid expression\n",
    "Missing closing curly brace\n",
    "Unregistered function\n",
    "Invalid operand\n",
    "Invalid type\n",
    "Invalid number of arguments\n",
    "Invalid context size\n",
    "Invalid context position\n",
    "Memory allocation error\n",
    "Syntax error\n",
    "Resource error\n",
    "Sub resource error\n",
    "Undefined namespace prefix\n",
    "Encoding error\n",
    "Char out of XML range\n",
    "Invalid or incomplete context\n",
    "Stack usage error\n",
    "Forbidden variable\n",
    "Operation limit exceeded\n",
    "Recursion limit exceeded\n",
    "?? Unknown error ??\n" /* Must be last in the list! */
};
#define MAXERRNO ((int)(sizeof(xmlXPathErrorMessages) / \
           sizeof(xmlXPathErrorMessages[0])) - 1)

static void
xmlXPathErrMemory(xmlXPathContextPtr ctxt, const char *extra)
{
    if (ctxt != NULL) {
        xmlResetError(&ctxt->lastError);
        if (extra) {
            xmlChar buf[200];

            xmlStrPrintf(buf, 200,
                         "Memory allocation failed : %s\n",
                         extra);
            ctxt->lastError.message = (char *) xmlStrdup(buf);
        } else {
            ctxt->lastError.message = (char *)
           xmlStrdup(BAD_CAST "Memory allocation failed\n");
        }
        ctxt->lastError.domain = XML_FROM_XPATH;
        ctxt->lastError.code = XML_ERR_NO_MEMORY;
    if (ctxt->error != NULL)
        ctxt->error(ctxt->userData, &ctxt->lastError);
    } else {
        if (extra)
            __xmlRaiseError(NULL, NULL, NULL,
                            NULL, NULL, XML_FROM_XPATH,
                            XML_ERR_NO_MEMORY, XML_ERR_FATAL, NULL, 0,
                            extra, NULL, NULL, 0, 0,
                            "Memory allocation failed : %s\n", extra);
        else
            __xmlRaiseError(NULL, NULL, NULL,
                            NULL, NULL, XML_FROM_XPATH,
                            XML_ERR_NO_MEMORY, XML_ERR_FATAL, NULL, 0,
                            NULL, NULL, NULL, 0, 0,
                            "Memory allocation failed\n");
    }
}

static void
xmlXPathPErrMemory(xmlXPathParserContextPtr ctxt, const char *extra)
{
    if (ctxt == NULL)
    xmlXPathErrMemory(NULL, extra);
    else {
    ctxt->error = XPATH_MEMORY_ERROR;
    xmlXPathErrMemory(ctxt->context, extra);
    }
}

void
xmlXPathErr(xmlXPathParserContextPtr ctxt, int error)
{
    if ((error < 0) || (error > MAXERRNO))
    error = MAXERRNO;
    if (ctxt == NULL) {
    __xmlRaiseError(NULL, NULL, NULL,
            NULL, NULL, XML_FROM_XPATH,
            error + XML_XPATH_EXPRESSION_OK - XPATH_EXPRESSION_OK,
            XML_ERR_ERROR, NULL, 0,
            NULL, NULL, NULL, 0, 0,
            "%s", xmlXPathErrorMessages[error]);
    return;
    }
    ctxt->error = error;
    if (ctxt->context == NULL) {
    __xmlRaiseError(NULL, NULL, NULL,
            NULL, NULL, XML_FROM_XPATH,
            error + XML_XPATH_EXPRESSION_OK - XPATH_EXPRESSION_OK,
            XML_ERR_ERROR, NULL, 0,
            (const char *) ctxt->base, NULL, NULL,
            ctxt->cur - ctxt->base, 0,
            "%s", xmlXPathErrorMessages[error]);
    return;
    }

    /* cleanup current last error */
    xmlResetError(&ctxt->context->lastError);

    ctxt->context->lastError.domain = XML_FROM_XPATH;
    ctxt->context->lastError.code = error + XML_XPATH_EXPRESSION_OK -
                           XPATH_EXPRESSION_OK;
    ctxt->context->lastError.level = XML_ERR_ERROR;
    ctxt->context->lastError.str1 = (char *) xmlStrdup(ctxt->base);
    ctxt->context->lastError.int1 = ctxt->cur - ctxt->base;
    ctxt->context->lastError.node = ctxt->context->debugNode;
    if (ctxt->context->error != NULL) {
    ctxt->context->error(ctxt->context->userData,
                         &ctxt->context->lastError);
    } else {
    __xmlRaiseError(NULL, NULL, NULL,
            NULL, ctxt->context->debugNode, XML_FROM_XPATH,
            error + XML_XPATH_EXPRESSION_OK - XPATH_EXPRESSION_OK,
            XML_ERR_ERROR, NULL, 0,
            (const char *) ctxt->base, NULL, NULL,
            ctxt->cur - ctxt->base, 0,
            "%s", xmlXPathErrorMessages[error]);
    }

}

void
xmlXPatherror(xmlXPathParserContextPtr ctxt, const char *file ATTRIBUTE_UNUSED,
              int line ATTRIBUTE_UNUSED, int no) {
    xmlXPathErr(ctxt, no);
}

static int
xmlXPathCheckOpLimit(xmlXPathParserContextPtr ctxt, unsigned long opCount) {
    xmlXPathContextPtr xpctxt = ctxt->context;

    if ((opCount > xpctxt->opLimit) ||
        (xpctxt->opCount > xpctxt->opLimit - opCount)) {
        xpctxt->opCount = xpctxt->opLimit;
        xmlXPathErr(ctxt, XPATH_OP_LIMIT_EXCEEDED);
        return(-1);
    }

    xpctxt->opCount += opCount;
    return(0);
}

#define OP_LIMIT_EXCEEDED(ctxt, n) \
    ((ctxt->context->opLimit != 0) && (xmlXPathCheckOpLimit(ctxt, n) < 0))

/************************************************************************
 *                                  *
 *          Utilities                   *
 *                                  *
 ************************************************************************/

typedef struct _xmlPointerList xmlPointerList;
typedef xmlPointerList *xmlPointerListPtr;
struct _xmlPointerList {
    void **items;
    int number;
    int size;
};
/*
* TODO: Since such a list-handling is used in xmlschemas.c and libxslt
* and here, we should make the functions public.
*/
static int
xmlPointerListAddSize(xmlPointerListPtr list,
               void *item,
               int initialSize)
{
    if (list->items == NULL) {
    if (initialSize <= 0)
        initialSize = 1;
    list->items = (void **) xmlMalloc(initialSize * sizeof(void *));
    if (list->items == NULL) {
        xmlXPathErrMemory(NULL,
        "xmlPointerListCreate: allocating item\n");
        return(-1);
    }
    list->number = 0;
    list->size = initialSize;
    } else if (list->size <= list->number) {
        if (list->size > 50000000) {
        xmlXPathErrMemory(NULL,
        "xmlPointerListAddSize: re-allocating item\n");
            return(-1);
        }
    list->size *= 2;
    list->items = (void **) xmlRealloc(list->items,
        list->size * sizeof(void *));
    if (list->items == NULL) {
        xmlXPathErrMemory(NULL,
        "xmlPointerListAddSize: re-allocating item\n");
        list->size = 0;
        return(-1);
    }
    }
    list->items[list->number++] = item;
    return(0);
}

static xmlPointerListPtr
xmlPointerListCreate(int initialSize)
{
    xmlPointerListPtr ret;

    ret = xmlMalloc(sizeof(xmlPointerList));
    if (ret == NULL) {
    xmlXPathErrMemory(NULL,
        "xmlPointerListCreate: allocating item\n");
    return (NULL);
    }
    memset(ret, 0, sizeof(xmlPointerList));
    if (initialSize > 0) {
    xmlPointerListAddSize(ret, NULL, initialSize);
    ret->number = 0;
    }
    return (ret);
}

static void
xmlPointerListFree(xmlPointerListPtr list)
{
    if (list == NULL)
    return;
    if (list->items != NULL)
    xmlFree(list->items);
    xmlFree(list);
}

/************************************************************************
 *                                  *
 *          Parser Types                    *
 *                                  *
 ************************************************************************/

/*
 * Types are private:
 */

typedef enum {
    XPATH_OP_END=0,
    XPATH_OP_AND,
    XPATH_OP_OR,
    XPATH_OP_EQUAL,
    XPATH_OP_CMP,
    XPATH_OP_PLUS,
    XPATH_OP_MULT,
    XPATH_OP_UNION,
    XPATH_OP_ROOT,
    XPATH_OP_NODE,
    XPATH_OP_COLLECT,
    XPATH_OP_VALUE, /* 11 */
    XPATH_OP_VARIABLE,
    XPATH_OP_FUNCTION,
    XPATH_OP_ARG,
    XPATH_OP_PREDICATE,
    XPATH_OP_FILTER, /* 16 */
    XPATH_OP_SORT /* 17 */
#ifdef LIBXML_XPTR_ENABLED
    ,XPATH_OP_RANGETO
#endif
} xmlXPathOp;

typedef enum {
    AXIS_ANCESTOR = 1,
    AXIS_ANCESTOR_OR_SELF,
    AXIS_ATTRIBUTE,
    AXIS_CHILD,
    AXIS_DESCENDANT,
    AXIS_DESCENDANT_OR_SELF,
    AXIS_FOLLOWING,
    AXIS_FOLLOWING_SIBLING,
    AXIS_NAMESPACE,
    AXIS_PARENT,
    AXIS_PRECEDING,
    AXIS_PRECEDING_SIBLING,
    AXIS_SELF
} xmlXPathAxisVal;

typedef enum {
    NODE_TEST_NONE = 0,
    NODE_TEST_TYPE = 1,
    NODE_TEST_PI = 2,
    NODE_TEST_ALL = 3,
    NODE_TEST_NS = 4,
    NODE_TEST_NAME = 5
} xmlXPathTestVal;

typedef enum {
    NODE_TYPE_NODE = 0,
    NODE_TYPE_COMMENT = XML_COMMENT_NODE,
    NODE_TYPE_TEXT = XML_TEXT_NODE,
    NODE_TYPE_PI = XML_PI_NODE
} xmlXPathTypeVal;

typedef struct _xmlXPathStepOp xmlXPathStepOp;
typedef xmlXPathStepOp *xmlXPathStepOpPtr;
struct _xmlXPathStepOp {
    xmlXPathOp op;      /* The identifier of the operation */
    int ch1;            /* First child */
    int ch2;            /* Second child */
    int value;
    int value2;
    int value3;
    void *value4;
    void *value5;
    xmlXPathFunction cache;
    void *cacheURI;
};

struct _xmlXPathCompExpr {
    int nbStep;         /* Number of steps in this expression */
    int maxStep;        /* Maximum number of steps allocated */
    xmlXPathStepOp *steps;  /* ops for computation of this expression */
    int last;           /* index of last step in expression */
    xmlChar *expr;      /* the expression being computed */
    xmlDictPtr dict;        /* the dictionary to use if any */
#ifdef DEBUG_EVAL_COUNTS
    int nb;
    xmlChar *string;
#endif
#ifdef XPATH_STREAMING
    xmlPatternPtr stream;
#endif
};

/************************************************************************
 *                                  *
 *          Forward declarations                *
 *                                  *
 ************************************************************************/
static void
xmlXPathFreeValueTree(xmlNodeSetPtr obj);
static void
xmlXPathReleaseObject(xmlXPathContextPtr ctxt, xmlXPathObjectPtr obj);
static int
xmlXPathCompOpEvalFirst(xmlXPathParserContextPtr ctxt,
                        xmlXPathStepOpPtr op, xmlNodePtr *first);
static int
xmlXPathCompOpEvalToBoolean(xmlXPathParserContextPtr ctxt,
                xmlXPathStepOpPtr op,
                int isPredicate);
static void
xmlXPathFreeObjectEntry(void *obj, const xmlChar *name);

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

static xmlXPathCompExprPtr
xmlXPathNewCompExpr(void) {
    xmlXPathCompExprPtr cur;

    cur = (xmlXPathCompExprPtr) xmlMalloc(sizeof(xmlXPathCompExpr));
    if (cur == NULL) {
        xmlXPathErrMemory(NULL, "allocating component\n");
    return(NULL);
    }
    memset(cur, 0, sizeof(xmlXPathCompExpr));
    cur->maxStep = 10;
    cur->nbStep = 0;
    cur->steps = (xmlXPathStepOp *) xmlMalloc(cur->maxStep *
                                       sizeof(xmlXPathStepOp));
    if (cur->steps == NULL) {
        xmlXPathErrMemory(NULL, "allocating steps\n");
    xmlFree(cur);
    return(NULL);
    }
    memset(cur->steps, 0, cur->maxStep * sizeof(xmlXPathStepOp));
    cur->last = -1;
#ifdef DEBUG_EVAL_COUNTS
    cur->nb = 0;
#endif
    return(cur);
}

void
xmlXPathFreeCompExpr(xmlXPathCompExprPtr comp)
{
    xmlXPathStepOpPtr op;
    int i;

    if (comp == NULL)
        return;
    if (comp->dict == NULL) {
    for (i = 0; i < comp->nbStep; i++) {
        op = &comp->steps[i];
        if (op->value4 != NULL) {
        if (op->op == XPATH_OP_VALUE)
            xmlXPathFreeObject(op->value4);
        else
            xmlFree(op->value4);
        }
        if (op->value5 != NULL)
        xmlFree(op->value5);
    }
    } else {
    for (i = 0; i < comp->nbStep; i++) {
        op = &comp->steps[i];
        if (op->value4 != NULL) {
        if (op->op == XPATH_OP_VALUE)
            xmlXPathFreeObject(op->value4);
        }
    }
        xmlDictFree(comp->dict);
    }
    if (comp->steps != NULL) {
        xmlFree(comp->steps);
    }
#ifdef DEBUG_EVAL_COUNTS
    if (comp->string != NULL) {
        xmlFree(comp->string);
    }
#endif
#ifdef XPATH_STREAMING
    if (comp->stream != NULL) {
        xmlFreePatternList(comp->stream);
    }
#endif
    if (comp->expr != NULL) {
        xmlFree(comp->expr);
    }

    xmlFree(comp);
}

static int
xmlXPathCompExprAdd(xmlXPathParserContextPtr ctxt, int ch1, int ch2,
   xmlXPathOp op, int value,
   int value2, int value3, void *value4, void *value5) {
    xmlXPathCompExprPtr comp = ctxt->comp;
    if (comp->nbStep >= comp->maxStep) {
    xmlXPathStepOp *real;

        if (comp->maxStep >= XPATH_MAX_STEPS) {
        xmlXPathPErrMemory(ctxt, "adding step\n");
        return(-1);
        }
    comp->maxStep *= 2;
    real = (xmlXPathStepOp *) xmlRealloc(comp->steps,
                              comp->maxStep * sizeof(xmlXPathStepOp));
    if (real == NULL) {
        comp->maxStep /= 2;
        xmlXPathPErrMemory(ctxt, "adding step\n");
        return(-1);
    }
    comp->steps = real;
    }
    comp->last = comp->nbStep;
    comp->steps[comp->nbStep].ch1 = ch1;
    comp->steps[comp->nbStep].ch2 = ch2;
    comp->steps[comp->nbStep].op = op;
    comp->steps[comp->nbStep].value = value;
    comp->steps[comp->nbStep].value2 = value2;
    comp->steps[comp->nbStep].value3 = value3;
    if ((comp->dict != NULL) &&
        ((op == XPATH_OP_FUNCTION) || (op == XPATH_OP_VARIABLE) ||
     (op == XPATH_OP_COLLECT))) {
        if (value4 != NULL) {
        comp->steps[comp->nbStep].value4 = (xmlChar *)
            (void *)xmlDictLookup(comp->dict, value4, -1);
        xmlFree(value4);
    } else
        comp->steps[comp->nbStep].value4 = NULL;
        if (value5 != NULL) {
        comp->steps[comp->nbStep].value5 = (xmlChar *)
            (void *)xmlDictLookup(comp->dict, value5, -1);
        xmlFree(value5);
    } else
        comp->steps[comp->nbStep].value5 = NULL;
    } else {
    comp->steps[comp->nbStep].value4 = value4;
    comp->steps[comp->nbStep].value5 = value5;
    }
    comp->steps[comp->nbStep].cache = NULL;
    return(comp->nbStep++);
}

static void
xmlXPathCompSwap(xmlXPathStepOpPtr op) {
    int tmp;

#ifndef LIBXML_THREAD_ENABLED
    /*
     * Since this manipulates possibly shared variables, this is
     * disabled if one detects that the library is used in a multithreaded
     * application
     */
    if (xmlXPathDisableOptimizer)
    return;
#endif

    tmp = op->ch1;
    op->ch1 = op->ch2;
    op->ch2 = tmp;
}

#define PUSH_FULL_EXPR(op, op1, op2, val, val2, val3, val4, val5)   \
    xmlXPathCompExprAdd(ctxt, (op1), (op2),         \
                    (op), (val), (val2), (val3), (val4), (val5))
#define PUSH_LONG_EXPR(op, val, val2, val3, val4, val5)         \
    xmlXPathCompExprAdd(ctxt, ctxt->comp->last, -1,     \
                    (op), (val), (val2), (val3), (val4), (val5))

#define PUSH_LEAVE_EXPR(op, val, val2)                  \
xmlXPathCompExprAdd(ctxt, -1, -1, (op), (val), (val2), 0 ,NULL ,NULL)

#define PUSH_UNARY_EXPR(op, ch, val, val2)              \
xmlXPathCompExprAdd(ctxt, (ch), -1, (op), (val), (val2), 0 ,NULL ,NULL)

#define PUSH_BINARY_EXPR(op, ch1, ch2, val, val2)           \
xmlXPathCompExprAdd(ctxt, (ch1), (ch2), (op),           \
            (val), (val2), 0 ,NULL ,NULL)

/************************************************************************
 *                                  *
 *      XPath object cache structures               *
 *                                  *
 ************************************************************************/

/* #define XP_DEFAULT_CACHE_ON */

#define XP_HAS_CACHE(c) ((c != NULL) && ((c)->cache != NULL))

typedef struct _xmlXPathContextCache xmlXPathContextCache;
typedef xmlXPathContextCache *xmlXPathContextCachePtr;
struct _xmlXPathContextCache {
    xmlPointerListPtr nodesetObjs;  /* contains xmlXPathObjectPtr */
    xmlPointerListPtr stringObjs;   /* contains xmlXPathObjectPtr */
    xmlPointerListPtr booleanObjs;  /* contains xmlXPathObjectPtr */
    xmlPointerListPtr numberObjs;   /* contains xmlXPathObjectPtr */
    xmlPointerListPtr miscObjs;     /* contains xmlXPathObjectPtr */
    int maxNodeset;
    int maxString;
    int maxBoolean;
    int maxNumber;
    int maxMisc;
#ifdef XP_DEBUG_OBJ_USAGE
    int dbgCachedAll;
    int dbgCachedNodeset;
    int dbgCachedString;
    int dbgCachedBool;
    int dbgCachedNumber;
    int dbgCachedPoint;
    int dbgCachedRange;
    int dbgCachedLocset;
    int dbgCachedUsers;
    int dbgCachedXSLTTree;
    int dbgCachedUndefined;


    int dbgReusedAll;
    int dbgReusedNodeset;
    int dbgReusedString;
    int dbgReusedBool;
    int dbgReusedNumber;
    int dbgReusedPoint;
    int dbgReusedRange;
    int dbgReusedLocset;
    int dbgReusedUsers;
    int dbgReusedXSLTTree;
    int dbgReusedUndefined;

#endif
};

/************************************************************************
 *                                  *
 *      Debugging related functions             *
 *                                  *
 ************************************************************************/

#define STRANGE                         \
    xmlGenericError(xmlGenericErrorContext,             \
        "Internal error at %s:%d\n",                \
            __FILE__, __LINE__);

#ifdef LIBXML_DEBUG_ENABLED
static void
xmlXPathDebugDumpNode(FILE *output, xmlNodePtr cur, int depth) {
    int i;
    char shift[100];

    for (i = 0;((i < depth) && (i < 25));i++)
        shift[2 * i] = shift[2 * i + 1] = ' ';
    shift[2 * i] = shift[2 * i + 1] = 0;
    if (cur == NULL) {
    fprintf(output, "%s", shift);
    fprintf(output, "Node is NULL !\n");
    return;

    }

    if ((cur->type == XML_DOCUMENT_NODE) ||
         (cur->type == XML_HTML_DOCUMENT_NODE)) {
    fprintf(output, "%s", shift);
    fprintf(output, " /\n");
    } else if (cur->type == XML_ATTRIBUTE_NODE)
    xmlDebugDumpAttr(output, (xmlAttrPtr)cur, depth);
    else
    xmlDebugDumpOneNode(output, cur, depth);
}
static void
xmlXPathDebugDumpNodeList(FILE *output, xmlNodePtr cur, int depth) {
    xmlNodePtr tmp;
    int i;
    char shift[100];

    for (i = 0;((i < depth) && (i < 25));i++)
        shift[2 * i] = shift[2 * i + 1] = ' ';
    shift[2 * i] = shift[2 * i + 1] = 0;
    if (cur == NULL) {
    fprintf(output, "%s", shift);
    fprintf(output, "Node is NULL !\n");
    return;

    }

    while (cur != NULL) {
    tmp = cur;
    cur = cur->next;
    xmlDebugDumpOneNode(output, tmp, depth);
    }
}

static void
xmlXPathDebugDumpNodeSet(FILE *output, xmlNodeSetPtr cur, int depth) {
    int i;
    char shift[100];

    for (i = 0;((i < depth) && (i < 25));i++)
        shift[2 * i] = shift[2 * i + 1] = ' ';
    shift[2 * i] = shift[2 * i + 1] = 0;

    if (cur == NULL) {
    fprintf(output, "%s", shift);
    fprintf(output, "NodeSet is NULL !\n");
    return;

    }

    if (cur != NULL) {
    fprintf(output, "Set contains %d nodes:\n", cur->nodeNr);
    for (i = 0;i < cur->nodeNr;i++) {
        fprintf(output, "%s", shift);
        fprintf(output, "%d", i + 1);
        xmlXPathDebugDumpNode(output, cur->nodeTab[i], depth + 1);
    }
    }
}

static void
xmlXPathDebugDumpValueTree(FILE *output, xmlNodeSetPtr cur, int depth) {
    int i;
    char shift[100];

    for (i = 0;((i < depth) && (i < 25));i++)
        shift[2 * i] = shift[2 * i + 1] = ' ';
    shift[2 * i] = shift[2 * i + 1] = 0;

    if ((cur == NULL) || (cur->nodeNr == 0) || (cur->nodeTab[0] == NULL)) {
    fprintf(output, "%s", shift);
    fprintf(output, "Value Tree is NULL !\n");
    return;

    }

    fprintf(output, "%s", shift);
    fprintf(output, "%d", i + 1);
    xmlXPathDebugDumpNodeList(output, cur->nodeTab[0]->children, depth + 1);
}
#if defined(LIBXML_XPTR_ENABLED)
static void
xmlXPathDebugDumpLocationSet(FILE *output, xmlLocationSetPtr cur, int depth) {
    int i;
    char shift[100];

    for (i = 0;((i < depth) && (i < 25));i++)
        shift[2 * i] = shift[2 * i + 1] = ' ';
    shift[2 * i] = shift[2 * i + 1] = 0;

    if (cur == NULL) {
    fprintf(output, "%s", shift);
    fprintf(output, "LocationSet is NULL !\n");
    return;

    }

    for (i = 0;i < cur->locNr;i++) {
    fprintf(output, "%s", shift);
        fprintf(output, "%d : ", i + 1);
    xmlXPathDebugDumpObject(output, cur->locTab[i], depth + 1);
    }
}
#endif /* LIBXML_XPTR_ENABLED */

void
xmlXPathDebugDumpObject(FILE *output, xmlXPathObjectPtr cur, int depth) {
    int i;
    char shift[100];

    if (output == NULL) return;

    for (i = 0;((i < depth) && (i < 25));i++)
        shift[2 * i] = shift[2 * i + 1] = ' ';
    shift[2 * i] = shift[2 * i + 1] = 0;


    fprintf(output, "%s", shift);

    if (cur == NULL) {
        fprintf(output, "Object is empty (NULL)\n");
    return;
    }
    switch(cur->type) {
        case XPATH_UNDEFINED:
        fprintf(output, "Object is uninitialized\n");
        break;
        case XPATH_NODESET:
        fprintf(output, "Object is a Node Set :\n");
        xmlXPathDebugDumpNodeSet(output, cur->nodesetval, depth);
        break;
    case XPATH_XSLT_TREE:
        fprintf(output, "Object is an XSLT value tree :\n");
        xmlXPathDebugDumpValueTree(output, cur->nodesetval, depth);
        break;
        case XPATH_BOOLEAN:
        fprintf(output, "Object is a Boolean : ");
        if (cur->boolval) fprintf(output, "true\n");
        else fprintf(output, "false\n");
        break;
        case XPATH_NUMBER:
        switch (xmlXPathIsInf(cur->floatval)) {
        case 1:
        fprintf(output, "Object is a number : Infinity\n");
        break;
        case -1:
        fprintf(output, "Object is a number : -Infinity\n");
        break;
        default:
        if (xmlXPathIsNaN(cur->floatval)) {
            fprintf(output, "Object is a number : NaN\n");
        } else if (cur->floatval == 0) {
                    /* Omit sign for negative zero. */
            fprintf(output, "Object is a number : 0\n");
        } else {
            fprintf(output, "Object is a number : %0g\n", cur->floatval);
        }
        }
        break;
        case XPATH_STRING:
        fprintf(output, "Object is a string : ");
        xmlDebugDumpString(output, cur->stringval);
        fprintf(output, "\n");
        break;
    case XPATH_POINT:
        fprintf(output, "Object is a point : index %d in node", cur->index);
        xmlXPathDebugDumpNode(output, (xmlNodePtr) cur->user, depth + 1);
        fprintf(output, "\n");
        break;
    case XPATH_RANGE:
        if ((cur->user2 == NULL) ||
        ((cur->user2 == cur->user) && (cur->index == cur->index2))) {
        fprintf(output, "Object is a collapsed range :\n");
        fprintf(output, "%s", shift);
        if (cur->index >= 0)
            fprintf(output, "index %d in ", cur->index);
        fprintf(output, "node\n");
        xmlXPathDebugDumpNode(output, (xmlNodePtr) cur->user,
                          depth + 1);
        } else  {
        fprintf(output, "Object is a range :\n");
        fprintf(output, "%s", shift);
        fprintf(output, "From ");
        if (cur->index >= 0)
            fprintf(output, "index %d in ", cur->index);
        fprintf(output, "node\n");
        xmlXPathDebugDumpNode(output, (xmlNodePtr) cur->user,
                          depth + 1);
        fprintf(output, "%s", shift);
        fprintf(output, "To ");
        if (cur->index2 >= 0)
            fprintf(output, "index %d in ", cur->index2);
        fprintf(output, "node\n");
        xmlXPathDebugDumpNode(output, (xmlNodePtr) cur->user2,
                          depth + 1);
        fprintf(output, "\n");
        }
        break;
    case XPATH_LOCATIONSET:
#if defined(LIBXML_XPTR_ENABLED)
        fprintf(output, "Object is a Location Set:\n");
        xmlXPathDebugDumpLocationSet(output,
            (xmlLocationSetPtr) cur->user, depth);
#endif
        break;
    case XPATH_USERS:
        fprintf(output, "Object is user defined\n");
        break;
    }
}

static void
xmlXPathDebugDumpStepOp(FILE *output, xmlXPathCompExprPtr comp,
                         xmlXPathStepOpPtr op, int depth) {
    int i;
    char shift[100];

    for (i = 0;((i < depth) && (i < 25));i++)
        shift[2 * i] = shift[2 * i + 1] = ' ';
    shift[2 * i] = shift[2 * i + 1] = 0;

    fprintf(output, "%s", shift);
    if (op == NULL) {
    fprintf(output, "Step is NULL\n");
    return;
    }
    switch (op->op) {
        case XPATH_OP_END:
        fprintf(output, "END"); break;
        case XPATH_OP_AND:
        fprintf(output, "AND"); break;
        case XPATH_OP_OR:
        fprintf(output, "OR"); break;
        case XPATH_OP_EQUAL:
         if (op->value)
         fprintf(output, "EQUAL =");
         else
         fprintf(output, "EQUAL !=");
         break;
        case XPATH_OP_CMP:
         if (op->value)
         fprintf(output, "CMP <");
         else
         fprintf(output, "CMP >");
         if (!op->value2)
         fprintf(output, "=");
         break;
        case XPATH_OP_PLUS:
         if (op->value == 0)
         fprintf(output, "PLUS -");
         else if (op->value == 1)
         fprintf(output, "PLUS +");
         else if (op->value == 2)
         fprintf(output, "PLUS unary -");
         else if (op->value == 3)
         fprintf(output, "PLUS unary - -");
         break;
        case XPATH_OP_MULT:
         if (op->value == 0)
         fprintf(output, "MULT *");
         else if (op->value == 1)
         fprintf(output, "MULT div");
         else
         fprintf(output, "MULT mod");
         break;
        case XPATH_OP_UNION:
         fprintf(output, "UNION"); break;
        case XPATH_OP_ROOT:
         fprintf(output, "ROOT"); break;
        case XPATH_OP_NODE:
         fprintf(output, "NODE"); break;
        case XPATH_OP_SORT:
         fprintf(output, "SORT"); break;
        case XPATH_OP_COLLECT: {
        xmlXPathAxisVal axis = (xmlXPathAxisVal)op->value;
        xmlXPathTestVal test = (xmlXPathTestVal)op->value2;
        xmlXPathTypeVal type = (xmlXPathTypeVal)op->value3;
        const xmlChar *prefix = op->value4;
        const xmlChar *name = op->value5;

        fprintf(output, "COLLECT ");
        switch (axis) {
        case AXIS_ANCESTOR:
            fprintf(output, " 'ancestors' "); break;
        case AXIS_ANCESTOR_OR_SELF:
            fprintf(output, " 'ancestors-or-self' "); break;
        case AXIS_ATTRIBUTE:
            fprintf(output, " 'attributes' "); break;
        case AXIS_CHILD:
            fprintf(output, " 'child' "); break;
        case AXIS_DESCENDANT:
            fprintf(output, " 'descendant' "); break;
        case AXIS_DESCENDANT_OR_SELF:
            fprintf(output, " 'descendant-or-self' "); break;
        case AXIS_FOLLOWING:
            fprintf(output, " 'following' "); break;
        case AXIS_FOLLOWING_SIBLING:
            fprintf(output, " 'following-siblings' "); break;
        case AXIS_NAMESPACE:
            fprintf(output, " 'namespace' "); break;
        case AXIS_PARENT:
            fprintf(output, " 'parent' "); break;
        case AXIS_PRECEDING:
            fprintf(output, " 'preceding' "); break;
        case AXIS_PRECEDING_SIBLING:
            fprintf(output, " 'preceding-sibling' "); break;
        case AXIS_SELF:
            fprintf(output, " 'self' "); break;
        }
        switch (test) {
                case NODE_TEST_NONE:
            fprintf(output, "'none' "); break;
                case NODE_TEST_TYPE:
            fprintf(output, "'type' "); break;
                case NODE_TEST_PI:
            fprintf(output, "'PI' "); break;
                case NODE_TEST_ALL:
            fprintf(output, "'all' "); break;
                case NODE_TEST_NS:
            fprintf(output, "'namespace' "); break;
                case NODE_TEST_NAME:
            fprintf(output, "'name' "); break;
        }
        switch (type) {
                case NODE_TYPE_NODE:
            fprintf(output, "'node' "); break;
                case NODE_TYPE_COMMENT:
            fprintf(output, "'comment' "); break;
                case NODE_TYPE_TEXT:
            fprintf(output, "'text' "); break;
                case NODE_TYPE_PI:
            fprintf(output, "'PI' "); break;
        }
        if (prefix != NULL)
        fprintf(output, "%s:", prefix);
        if (name != NULL)
        fprintf(output, "%s", (const char *) name);
        break;

        }
    case XPATH_OP_VALUE: {
        xmlXPathObjectPtr object = (xmlXPathObjectPtr) op->value4;

        fprintf(output, "ELEM ");
        xmlXPathDebugDumpObject(output, object, 0);
        goto finish;
    }
    case XPATH_OP_VARIABLE: {
        const xmlChar *prefix = op->value5;
        const xmlChar *name = op->value4;

        if (prefix != NULL)
        fprintf(output, "VARIABLE %s:%s", prefix, name);
        else
        fprintf(output, "VARIABLE %s", name);
        break;
    }
    case XPATH_OP_FUNCTION: {
        int nbargs = op->value;
        const xmlChar *prefix = op->value5;
        const xmlChar *name = op->value4;

        if (prefix != NULL)
        fprintf(output, "FUNCTION %s:%s(%d args)",
            prefix, name, nbargs);
        else
        fprintf(output, "FUNCTION %s(%d args)", name, nbargs);
        break;
    }
        case XPATH_OP_ARG: fprintf(output, "ARG"); break;
        case XPATH_OP_PREDICATE: fprintf(output, "PREDICATE"); break;
        case XPATH_OP_FILTER: fprintf(output, "FILTER"); break;
#ifdef LIBXML_XPTR_ENABLED
        case XPATH_OP_RANGETO: fprintf(output, "RANGETO"); break;
#endif
    default:
        fprintf(output, "UNKNOWN %d\n", op->op); return;
    }
    fprintf(output, "\n");
finish:
    if (op->ch1 >= 0)
    xmlXPathDebugDumpStepOp(output, comp, &comp->steps[op->ch1], depth + 1);
    if (op->ch2 >= 0)
    xmlXPathDebugDumpStepOp(output, comp, &comp->steps[op->ch2], depth + 1);
}

void
xmlXPathDebugDumpCompExpr(FILE *output, xmlXPathCompExprPtr comp,
                      int depth) {
    int i;
    char shift[100];

    if ((output == NULL) || (comp == NULL)) return;

    for (i = 0;((i < depth) && (i < 25));i++)
        shift[2 * i] = shift[2 * i + 1] = ' ';
    shift[2 * i] = shift[2 * i + 1] = 0;

    fprintf(output, "%s", shift);

#ifdef XPATH_STREAMING
    if (comp->stream) {
        fprintf(output, "Streaming Expression\n");
    } else
#endif
    {
        fprintf(output, "Compiled Expression : %d elements\n",
                comp->nbStep);
        i = comp->last;
        xmlXPathDebugDumpStepOp(output, comp, &comp->steps[i], depth + 1);
    }
}

#ifdef XP_DEBUG_OBJ_USAGE

/*
* XPath object usage related debugging variables.
*/
static int xmlXPathDebugObjCounterUndefined = 0;
static int xmlXPathDebugObjCounterNodeset = 0;
static int xmlXPathDebugObjCounterBool = 0;
static int xmlXPathDebugObjCounterNumber = 0;
static int xmlXPathDebugObjCounterString = 0;
static int xmlXPathDebugObjCounterPoint = 0;
static int xmlXPathDebugObjCounterRange = 0;
static int xmlXPathDebugObjCounterLocset = 0;
static int xmlXPathDebugObjCounterUsers = 0;
static int xmlXPathDebugObjCounterXSLTTree = 0;
static int xmlXPathDebugObjCounterAll = 0;

static int xmlXPathDebugObjTotalUndefined = 0;
static int xmlXPathDebugObjTotalNodeset = 0;
static int xmlXPathDebugObjTotalBool = 0;
static int xmlXPathDebugObjTotalNumber = 0;
static int xmlXPathDebugObjTotalString = 0;
static int xmlXPathDebugObjTotalPoint = 0;
static int xmlXPathDebugObjTotalRange = 0;
static int xmlXPathDebugObjTotalLocset = 0;
static int xmlXPathDebugObjTotalUsers = 0;
static int xmlXPathDebugObjTotalXSLTTree = 0;
static int xmlXPathDebugObjTotalAll = 0;

static int xmlXPathDebugObjMaxUndefined = 0;
static int xmlXPathDebugObjMaxNodeset = 0;
static int xmlXPathDebugObjMaxBool = 0;
static int xmlXPathDebugObjMaxNumber = 0;
static int xmlXPathDebugObjMaxString = 0;
static int xmlXPathDebugObjMaxPoint = 0;
static int xmlXPathDebugObjMaxRange = 0;
static int xmlXPathDebugObjMaxLocset = 0;
static int xmlXPathDebugObjMaxUsers = 0;
static int xmlXPathDebugObjMaxXSLTTree = 0;
static int xmlXPathDebugObjMaxAll = 0;

static void
xmlXPathDebugObjUsageReset(xmlXPathContextPtr ctxt)
{
    if (ctxt != NULL) {
    if (ctxt->cache != NULL) {
        xmlXPathContextCachePtr cache =
        (xmlXPathContextCachePtr) ctxt->cache;

        cache->dbgCachedAll = 0;
        cache->dbgCachedNodeset = 0;
        cache->dbgCachedString = 0;
        cache->dbgCachedBool = 0;
        cache->dbgCachedNumber = 0;
        cache->dbgCachedPoint = 0;
        cache->dbgCachedRange = 0;
        cache->dbgCachedLocset = 0;
        cache->dbgCachedUsers = 0;
        cache->dbgCachedXSLTTree = 0;
        cache->dbgCachedUndefined = 0;

        cache->dbgReusedAll = 0;
        cache->dbgReusedNodeset = 0;
        cache->dbgReusedString = 0;
        cache->dbgReusedBool = 0;
        cache->dbgReusedNumber = 0;
        cache->dbgReusedPoint = 0;
        cache->dbgReusedRange = 0;
        cache->dbgReusedLocset = 0;
        cache->dbgReusedUsers = 0;
        cache->dbgReusedXSLTTree = 0;
        cache->dbgReusedUndefined = 0;
    }
    }

    xmlXPathDebugObjCounterUndefined = 0;
    xmlXPathDebugObjCounterNodeset = 0;
    xmlXPathDebugObjCounterBool = 0;
    xmlXPathDebugObjCounterNumber = 0;
    xmlXPathDebugObjCounterString = 0;
    xmlXPathDebugObjCounterPoint = 0;
    xmlXPathDebugObjCounterRange = 0;
    xmlXPathDebugObjCounterLocset = 0;
    xmlXPathDebugObjCounterUsers = 0;
    xmlXPathDebugObjCounterXSLTTree = 0;
    xmlXPathDebugObjCounterAll = 0;

    xmlXPathDebugObjTotalUndefined = 0;
    xmlXPathDebugObjTotalNodeset = 0;
    xmlXPathDebugObjTotalBool = 0;
    xmlXPathDebugObjTotalNumber = 0;
    xmlXPathDebugObjTotalString = 0;
    xmlXPathDebugObjTotalPoint = 0;
    xmlXPathDebugObjTotalRange = 0;
    xmlXPathDebugObjTotalLocset = 0;
    xmlXPathDebugObjTotalUsers = 0;
    xmlXPathDebugObjTotalXSLTTree = 0;
    xmlXPathDebugObjTotalAll = 0;

    xmlXPathDebugObjMaxUndefined = 0;
    xmlXPathDebugObjMaxNodeset = 0;
    xmlXPathDebugObjMaxBool = 0;
    xmlXPathDebugObjMaxNumber = 0;
    xmlXPathDebugObjMaxString = 0;
    xmlXPathDebugObjMaxPoint = 0;
    xmlXPathDebugObjMaxRange = 0;
    xmlXPathDebugObjMaxLocset = 0;
    xmlXPathDebugObjMaxUsers = 0;
    xmlXPathDebugObjMaxXSLTTree = 0;
    xmlXPathDebugObjMaxAll = 0;

}

static void
xmlXPathDebugObjUsageRequested(xmlXPathContextPtr ctxt,
                  xmlXPathObjectType objType)
{
    int isCached = 0;

    if (ctxt != NULL) {
    if (ctxt->cache != NULL) {
        xmlXPathContextCachePtr cache =
        (xmlXPathContextCachePtr) ctxt->cache;

        isCached = 1;

        cache->dbgReusedAll++;
        switch (objType) {
        case XPATH_UNDEFINED:
            cache->dbgReusedUndefined++;
            break;
        case XPATH_NODESET:
            cache->dbgReusedNodeset++;
            break;
        case XPATH_BOOLEAN:
            cache->dbgReusedBool++;
            break;
        case XPATH_NUMBER:
            cache->dbgReusedNumber++;
            break;
        case XPATH_STRING:
            cache->dbgReusedString++;
            break;
        case XPATH_POINT:
            cache->dbgReusedPoint++;
            break;
        case XPATH_RANGE:
            cache->dbgReusedRange++;
            break;
        case XPATH_LOCATIONSET:
            cache->dbgReusedLocset++;
            break;
        case XPATH_USERS:
            cache->dbgReusedUsers++;
            break;
        case XPATH_XSLT_TREE:
            cache->dbgReusedXSLTTree++;
            break;
        default:
            break;
        }
    }
    }

    switch (objType) {
    case XPATH_UNDEFINED:
        if (! isCached)
        xmlXPathDebugObjTotalUndefined++;
        xmlXPathDebugObjCounterUndefined++;
        if (xmlXPathDebugObjCounterUndefined >
        xmlXPathDebugObjMaxUndefined)
        xmlXPathDebugObjMaxUndefined =
            xmlXPathDebugObjCounterUndefined;
        break;
    case XPATH_NODESET:
        if (! isCached)
        xmlXPathDebugObjTotalNodeset++;
        xmlXPathDebugObjCounterNodeset++;
        if (xmlXPathDebugObjCounterNodeset >
        xmlXPathDebugObjMaxNodeset)
        xmlXPathDebugObjMaxNodeset =
            xmlXPathDebugObjCounterNodeset;
        break;
    case XPATH_BOOLEAN:
        if (! isCached)
        xmlXPathDebugObjTotalBool++;
        xmlXPathDebugObjCounterBool++;
        if (xmlXPathDebugObjCounterBool >
        xmlXPathDebugObjMaxBool)
        xmlXPathDebugObjMaxBool =
            xmlXPathDebugObjCounterBool;
        break;
    case XPATH_NUMBER:
        if (! isCached)
        xmlXPathDebugObjTotalNumber++;
        xmlXPathDebugObjCounterNumber++;
        if (xmlXPathDebugObjCounterNumber >
        xmlXPathDebugObjMaxNumber)
        xmlXPathDebugObjMaxNumber =
            xmlXPathDebugObjCounterNumber;
        break;
    case XPATH_STRING:
        if (! isCached)
        xmlXPathDebugObjTotalString++;
        xmlXPathDebugObjCounterString++;
        if (xmlXPathDebugObjCounterString >
        xmlXPathDebugObjMaxString)
        xmlXPathDebugObjMaxString =
            xmlXPathDebugObjCounterString;
        break;
    case XPATH_POINT:
        if (! isCached)
        xmlXPathDebugObjTotalPoint++;
        xmlXPathDebugObjCounterPoint++;
        if (xmlXPathDebugObjCounterPoint >
        xmlXPathDebugObjMaxPoint)
        xmlXPathDebugObjMaxPoint =
            xmlXPathDebugObjCounterPoint;
        break;
    case XPATH_RANGE:
        if (! isCached)
        xmlXPathDebugObjTotalRange++;
        xmlXPathDebugObjCounterRange++;
        if (xmlXPathDebugObjCounterRange >
        xmlXPathDebugObjMaxRange)
        xmlXPathDebugObjMaxRange =
            xmlXPathDebugObjCounterRange;
        break;
    case XPATH_LOCATIONSET:
        if (! isCached)
        xmlXPathDebugObjTotalLocset++;
        xmlXPathDebugObjCounterLocset++;
        if (xmlXPathDebugObjCounterLocset >
        xmlXPathDebugObjMaxLocset)
        xmlXPathDebugObjMaxLocset =
            xmlXPathDebugObjCounterLocset;
        break;
    case XPATH_USERS:
        if (! isCached)
        xmlXPathDebugObjTotalUsers++;
        xmlXPathDebugObjCounterUsers++;
        if (xmlXPathDebugObjCounterUsers >
        xmlXPathDebugObjMaxUsers)
        xmlXPathDebugObjMaxUsers =
            xmlXPathDebugObjCounterUsers;
        break;
    case XPATH_XSLT_TREE:
        if (! isCached)
        xmlXPathDebugObjTotalXSLTTree++;
        xmlXPathDebugObjCounterXSLTTree++;
        if (xmlXPathDebugObjCounterXSLTTree >
        xmlXPathDebugObjMaxXSLTTree)
        xmlXPathDebugObjMaxXSLTTree =
            xmlXPathDebugObjCounterXSLTTree;
        break;
    default:
        break;
    }
    if (! isCached)
    xmlXPathDebugObjTotalAll++;
    xmlXPathDebugObjCounterAll++;
    if (xmlXPathDebugObjCounterAll >
    xmlXPathDebugObjMaxAll)
    xmlXPathDebugObjMaxAll =
        xmlXPathDebugObjCounterAll;
}

static void
xmlXPathDebugObjUsageReleased(xmlXPathContextPtr ctxt,
                  xmlXPathObjectType objType)
{
    int isCached = 0;

    if (ctxt != NULL) {
    if (ctxt->cache != NULL) {
        xmlXPathContextCachePtr cache =
        (xmlXPathContextCachePtr) ctxt->cache;

        isCached = 1;

        cache->dbgCachedAll++;
        switch (objType) {
        case XPATH_UNDEFINED:
            cache->dbgCachedUndefined++;
            break;
        case XPATH_NODESET:
            cache->dbgCachedNodeset++;
            break;
        case XPATH_BOOLEAN:
            cache->dbgCachedBool++;
            break;
        case XPATH_NUMBER:
            cache->dbgCachedNumber++;
            break;
        case XPATH_STRING:
            cache->dbgCachedString++;
            break;
        case XPATH_POINT:
            cache->dbgCachedPoint++;
            break;
        case XPATH_RANGE:
            cache->dbgCachedRange++;
            break;
        case XPATH_LOCATIONSET:
            cache->dbgCachedLocset++;
            break;
        case XPATH_USERS:
            cache->dbgCachedUsers++;
            break;
        case XPATH_XSLT_TREE:
            cache->dbgCachedXSLTTree++;
            break;
        default:
            break;
        }

    }
    }
    switch (objType) {
    case XPATH_UNDEFINED:
        xmlXPathDebugObjCounterUndefined--;
        break;
    case XPATH_NODESET:
        xmlXPathDebugObjCounterNodeset--;
        break;
    case XPATH_BOOLEAN:
        xmlXPathDebugObjCounterBool--;
        break;
    case XPATH_NUMBER:
        xmlXPathDebugObjCounterNumber--;
        break;
    case XPATH_STRING:
        xmlXPathDebugObjCounterString--;
        break;
    case XPATH_POINT:
        xmlXPathDebugObjCounterPoint--;
        break;
    case XPATH_RANGE:
        xmlXPathDebugObjCounterRange--;
        break;
    case XPATH_LOCATIONSET:
        xmlXPathDebugObjCounterLocset--;
        break;
    case XPATH_USERS:
        xmlXPathDebugObjCounterUsers--;
        break;
    case XPATH_XSLT_TREE:
        xmlXPathDebugObjCounterXSLTTree--;
        break;
    default:
        break;
    }
    xmlXPathDebugObjCounterAll--;
}

static void
xmlXPathDebugObjUsageDisplay(xmlXPathContextPtr ctxt)
{
    int reqAll, reqNodeset, reqString, reqBool, reqNumber,
    reqXSLTTree, reqUndefined;
    int caAll = 0, caNodeset = 0, caString = 0, caBool = 0,
    caNumber = 0, caXSLTTree = 0, caUndefined = 0;
    int reAll = 0, reNodeset = 0, reString = 0, reBool = 0,
    reNumber = 0, reXSLTTree = 0, reUndefined = 0;
    int leftObjs = xmlXPathDebugObjCounterAll;

    reqAll = xmlXPathDebugObjTotalAll;
    reqNodeset = xmlXPathDebugObjTotalNodeset;
    reqString = xmlXPathDebugObjTotalString;
    reqBool = xmlXPathDebugObjTotalBool;
    reqNumber = xmlXPathDebugObjTotalNumber;
    reqXSLTTree = xmlXPathDebugObjTotalXSLTTree;
    reqUndefined = xmlXPathDebugObjTotalUndefined;

    printf("# XPath object usage:\n");

    if (ctxt != NULL) {
    if (ctxt->cache != NULL) {
        xmlXPathContextCachePtr cache =
        (xmlXPathContextCachePtr) ctxt->cache;

        reAll = cache->dbgReusedAll;
        reqAll += reAll;
        reNodeset = cache->dbgReusedNodeset;
        reqNodeset += reNodeset;
        reString = cache->dbgReusedString;
        reqString += reString;
        reBool = cache->dbgReusedBool;
        reqBool += reBool;
        reNumber = cache->dbgReusedNumber;
        reqNumber += reNumber;
        reXSLTTree = cache->dbgReusedXSLTTree;
        reqXSLTTree += reXSLTTree;
        reUndefined = cache->dbgReusedUndefined;
        reqUndefined += reUndefined;

        caAll = cache->dbgCachedAll;
        caBool = cache->dbgCachedBool;
        caNodeset = cache->dbgCachedNodeset;
        caString = cache->dbgCachedString;
        caNumber = cache->dbgCachedNumber;
        caXSLTTree = cache->dbgCachedXSLTTree;
        caUndefined = cache->dbgCachedUndefined;

        if (cache->nodesetObjs)
        leftObjs -= cache->nodesetObjs->number;
        if (cache->stringObjs)
        leftObjs -= cache->stringObjs->number;
        if (cache->booleanObjs)
        leftObjs -= cache->booleanObjs->number;
        if (cache->numberObjs)
        leftObjs -= cache->numberObjs->number;
        if (cache->miscObjs)
        leftObjs -= cache->miscObjs->number;
    }
    }

    printf("# all\n");
    printf("#   total  : %d\n", reqAll);
    printf("#   left  : %d\n", leftObjs);
    printf("#   created: %d\n", xmlXPathDebugObjTotalAll);
    printf("#   reused : %d\n", reAll);
    printf("#   max    : %d\n", xmlXPathDebugObjMaxAll);

    printf("# node-sets\n");
    printf("#   total  : %d\n", reqNodeset);
    printf("#   created: %d\n", xmlXPathDebugObjTotalNodeset);
    printf("#   reused : %d\n", reNodeset);
    printf("#   max    : %d\n", xmlXPathDebugObjMaxNodeset);

    printf("# strings\n");
    printf("#   total  : %d\n", reqString);
    printf("#   created: %d\n", xmlXPathDebugObjTotalString);
    printf("#   reused : %d\n", reString);
    printf("#   max    : %d\n", xmlXPathDebugObjMaxString);

    printf("# booleans\n");
    printf("#   total  : %d\n", reqBool);
    printf("#   created: %d\n", xmlXPathDebugObjTotalBool);
    printf("#   reused : %d\n", reBool);
    printf("#   max    : %d\n", xmlXPathDebugObjMaxBool);

    printf("# numbers\n");
    printf("#   total  : %d\n", reqNumber);
    printf("#   created: %d\n", xmlXPathDebugObjTotalNumber);
    printf("#   reused : %d\n", reNumber);
    printf("#   max    : %d\n", xmlXPathDebugObjMaxNumber);

    printf("# XSLT result tree fragments\n");
    printf("#   total  : %d\n", reqXSLTTree);
    printf("#   created: %d\n", xmlXPathDebugObjTotalXSLTTree);
    printf("#   reused : %d\n", reXSLTTree);
    printf("#   max    : %d\n", xmlXPathDebugObjMaxXSLTTree);

    printf("# undefined\n");
    printf("#   total  : %d\n", reqUndefined);
    printf("#   created: %d\n", xmlXPathDebugObjTotalUndefined);
    printf("#   reused : %d\n", reUndefined);
    printf("#   max    : %d\n", xmlXPathDebugObjMaxUndefined);

}

#endif /* XP_DEBUG_OBJ_USAGE */

#endif /* LIBXML_DEBUG_ENABLED */

/************************************************************************
 *                                  *
 *          XPath object caching                *
 *                                  *
 ************************************************************************/

static xmlXPathContextCachePtr
xmlXPathNewCache(void)
{
    xmlXPathContextCachePtr ret;

    ret = (xmlXPathContextCachePtr) xmlMalloc(sizeof(xmlXPathContextCache));
    if (ret == NULL) {
        xmlXPathErrMemory(NULL, "creating object cache\n");
    return(NULL);
    }
    memset(ret, 0 , (size_t) sizeof(xmlXPathContextCache));
    ret->maxNodeset = 100;
    ret->maxString = 100;
    ret->maxBoolean = 100;
    ret->maxNumber = 100;
    ret->maxMisc = 100;
    return(ret);
}

static void
xmlXPathCacheFreeObjectList(xmlPointerListPtr list)
{
    int i;
    xmlXPathObjectPtr obj;

    if (list == NULL)
    return;

    for (i = 0; i < list->number; i++) {
    obj = list->items[i];
    /*
    * Note that it is already assured that we don't need to
    * look out for namespace nodes in the node-set.
    */
    if (obj->nodesetval != NULL) {
        if (obj->nodesetval->nodeTab != NULL)
        xmlFree(obj->nodesetval->nodeTab);
        xmlFree(obj->nodesetval);
    }
    xmlFree(obj);
#ifdef XP_DEBUG_OBJ_USAGE
    xmlXPathDebugObjCounterAll--;
#endif
    }
    xmlPointerListFree(list);
}

static void
xmlXPathFreeCache(xmlXPathContextCachePtr cache)
{
    if (cache == NULL)
    return;
    if (cache->nodesetObjs)
    xmlXPathCacheFreeObjectList(cache->nodesetObjs);
    if (cache->stringObjs)
    xmlXPathCacheFreeObjectList(cache->stringObjs);
    if (cache->booleanObjs)
    xmlXPathCacheFreeObjectList(cache->booleanObjs);
    if (cache->numberObjs)
    xmlXPathCacheFreeObjectList(cache->numberObjs);
    if (cache->miscObjs)
    xmlXPathCacheFreeObjectList(cache->miscObjs);
    xmlFree(cache);
}

int
xmlXPathContextSetCache(xmlXPathContextPtr ctxt,
            int active,
            int value,
            int options)
{
    if (ctxt == NULL)
    return(-1);
    if (active) {
    xmlXPathContextCachePtr cache;

    if (ctxt->cache == NULL) {
        ctxt->cache = xmlXPathNewCache();
        if (ctxt->cache == NULL)
        return(-1);
    }
    cache = (xmlXPathContextCachePtr) ctxt->cache;
    if (options == 0) {
        if (value < 0)
        value = 100;
        cache->maxNodeset = value;
        cache->maxString = value;
        cache->maxNumber = value;
        cache->maxBoolean = value;
        cache->maxMisc = value;
    }
    } else if (ctxt->cache != NULL) {
    xmlXPathFreeCache((xmlXPathContextCachePtr) ctxt->cache);
    ctxt->cache = NULL;
    }
    return(0);
}

static xmlXPathObjectPtr
xmlXPathCacheWrapNodeSet(xmlXPathContextPtr ctxt, xmlNodeSetPtr val)
{
    if ((ctxt != NULL) && (ctxt->cache != NULL)) {
    xmlXPathContextCachePtr cache =
        (xmlXPathContextCachePtr) ctxt->cache;

    if ((cache->miscObjs != NULL) &&
        (cache->miscObjs->number != 0))
    {
        xmlXPathObjectPtr ret;

        ret = (xmlXPathObjectPtr)
        cache->miscObjs->items[--cache->miscObjs->number];
        ret->type = XPATH_NODESET;
        ret->nodesetval = val;
#ifdef XP_DEBUG_OBJ_USAGE
        xmlXPathDebugObjUsageRequested(ctxt, XPATH_NODESET);
#endif
        return(ret);
    }
    }

    return(xmlXPathWrapNodeSet(val));

}

static xmlXPathObjectPtr
xmlXPathCacheWrapString(xmlXPathContextPtr ctxt, xmlChar *val)
{
    if ((ctxt != NULL) && (ctxt->cache != NULL)) {
    xmlXPathContextCachePtr cache = (xmlXPathContextCachePtr) ctxt->cache;

    if ((cache->stringObjs != NULL) &&
        (cache->stringObjs->number != 0))
    {

        xmlXPathObjectPtr ret;

        ret = (xmlXPathObjectPtr)
        cache->stringObjs->items[--cache->stringObjs->number];
        ret->type = XPATH_STRING;
        ret->stringval = val;
#ifdef XP_DEBUG_OBJ_USAGE
        xmlXPathDebugObjUsageRequested(ctxt, XPATH_STRING);
#endif
        return(ret);
    } else if ((cache->miscObjs != NULL) &&
        (cache->miscObjs->number != 0))
    {
        xmlXPathObjectPtr ret;
        /*
        * Fallback to misc-cache.
        */
        ret = (xmlXPathObjectPtr)
        cache->miscObjs->items[--cache->miscObjs->number];

        ret->type = XPATH_STRING;
        ret->stringval = val;
#ifdef XP_DEBUG_OBJ_USAGE
        xmlXPathDebugObjUsageRequested(ctxt, XPATH_STRING);
#endif
        return(ret);
    }
    }
    return(xmlXPathWrapString(val));
}

static xmlXPathObjectPtr
xmlXPathCacheNewNodeSet(xmlXPathContextPtr ctxt, xmlNodePtr val)
{
    if ((ctxt != NULL) && (ctxt->cache)) {
    xmlXPathContextCachePtr cache = (xmlXPathContextCachePtr) ctxt->cache;

    if ((cache->nodesetObjs != NULL) &&
        (cache->nodesetObjs->number != 0))
    {
        xmlXPathObjectPtr ret;
        /*
        * Use the nodeset-cache.
        */
        ret = (xmlXPathObjectPtr)
        cache->nodesetObjs->items[--cache->nodesetObjs->number];
        ret->type = XPATH_NODESET;
        ret->boolval = 0;
        if (val) {
        if ((ret->nodesetval->nodeMax == 0) ||
            (val->type == XML_NAMESPACE_DECL))
        {
                    /* TODO: Check memory error. */
            xmlXPathNodeSetAddUnique(ret->nodesetval, val);
        } else {
            ret->nodesetval->nodeTab[0] = val;
            ret->nodesetval->nodeNr = 1;
        }
        }
#ifdef XP_DEBUG_OBJ_USAGE
        xmlXPathDebugObjUsageRequested(ctxt, XPATH_NODESET);
#endif
        return(ret);
    } else if ((cache->miscObjs != NULL) &&
        (cache->miscObjs->number != 0))
    {
        xmlXPathObjectPtr ret;
        /*
        * Fallback to misc-cache.
        */

        ret = (xmlXPathObjectPtr)
        cache->miscObjs->items[--cache->miscObjs->number];

        ret->type = XPATH_NODESET;
        ret->boolval = 0;
        ret->nodesetval = xmlXPathNodeSetCreate(val);
        if (ret->nodesetval == NULL) {
        ctxt->lastError.domain = XML_FROM_XPATH;
        ctxt->lastError.code = XML_ERR_NO_MEMORY;
        return(NULL);
        }
#ifdef XP_DEBUG_OBJ_USAGE
        xmlXPathDebugObjUsageRequested(ctxt, XPATH_NODESET);
#endif
        return(ret);
    }
    }
    return(xmlXPathNewNodeSet(val));
}

static xmlXPathObjectPtr
xmlXPathCacheNewCString(xmlXPathContextPtr ctxt, const char *val)
{
    if ((ctxt != NULL) && (ctxt->cache)) {
    xmlXPathContextCachePtr cache = (xmlXPathContextCachePtr) ctxt->cache;

    if ((cache->stringObjs != NULL) &&
        (cache->stringObjs->number != 0))
    {
        xmlXPathObjectPtr ret;

        ret = (xmlXPathObjectPtr)
        cache->stringObjs->items[--cache->stringObjs->number];

        ret->type = XPATH_STRING;
        ret->stringval = xmlStrdup(BAD_CAST val);
#ifdef XP_DEBUG_OBJ_USAGE
        xmlXPathDebugObjUsageRequested(ctxt, XPATH_STRING);
#endif
        return(ret);
    } else if ((cache->miscObjs != NULL) &&
        (cache->miscObjs->number != 0))
    {
        xmlXPathObjectPtr ret;

        ret = (xmlXPathObjectPtr)
        cache->miscObjs->items[--cache->miscObjs->number];

        ret->type = XPATH_STRING;
        ret->stringval = xmlStrdup(BAD_CAST val);
#ifdef XP_DEBUG_OBJ_USAGE
        xmlXPathDebugObjUsageRequested(ctxt, XPATH_STRING);
#endif
        return(ret);
    }
    }
    return(xmlXPathNewCString(val));
}

static xmlXPathObjectPtr
xmlXPathCacheNewString(xmlXPathContextPtr ctxt, const xmlChar *val)
{
    if ((ctxt != NULL) && (ctxt->cache)) {
    xmlXPathContextCachePtr cache = (xmlXPathContextCachePtr) ctxt->cache;

    if ((cache->stringObjs != NULL) &&
        (cache->stringObjs->number != 0))
    {
        xmlXPathObjectPtr ret;

        ret = (xmlXPathObjectPtr)
        cache->stringObjs->items[--cache->stringObjs->number];
        ret->type = XPATH_STRING;
        if (val != NULL)
        ret->stringval = xmlStrdup(val);
        else
        ret->stringval = xmlStrdup((const xmlChar *)"");
#ifdef XP_DEBUG_OBJ_USAGE
        xmlXPathDebugObjUsageRequested(ctxt, XPATH_STRING);
#endif
        return(ret);
    } else if ((cache->miscObjs != NULL) &&
        (cache->miscObjs->number != 0))
    {
        xmlXPathObjectPtr ret;

        ret = (xmlXPathObjectPtr)
        cache->miscObjs->items[--cache->miscObjs->number];

        ret->type = XPATH_STRING;
        if (val != NULL)
        ret->stringval = xmlStrdup(val);
        else
        ret->stringval = xmlStrdup((const xmlChar *)"");
#ifdef XP_DEBUG_OBJ_USAGE
        xmlXPathDebugObjUsageRequested(ctxt, XPATH_STRING);
#endif
        return(ret);
    }
    }
    return(xmlXPathNewString(val));
}

static xmlXPathObjectPtr
xmlXPathCacheNewBoolean(xmlXPathContextPtr ctxt, int val)
{
    if ((ctxt != NULL) && (ctxt->cache)) {
    xmlXPathContextCachePtr cache = (xmlXPathContextCachePtr) ctxt->cache;

    if ((cache->booleanObjs != NULL) &&
        (cache->booleanObjs->number != 0))
    {
        xmlXPathObjectPtr ret;

        ret = (xmlXPathObjectPtr)
        cache->booleanObjs->items[--cache->booleanObjs->number];
        ret->type = XPATH_BOOLEAN;
        ret->boolval = (val != 0);
#ifdef XP_DEBUG_OBJ_USAGE
        xmlXPathDebugObjUsageRequested(ctxt, XPATH_BOOLEAN);
#endif
        return(ret);
    } else if ((cache->miscObjs != NULL) &&
        (cache->miscObjs->number != 0))
    {
        xmlXPathObjectPtr ret;

        ret = (xmlXPathObjectPtr)
        cache->miscObjs->items[--cache->miscObjs->number];

        ret->type = XPATH_BOOLEAN;
        ret->boolval = (val != 0);
#ifdef XP_DEBUG_OBJ_USAGE
        xmlXPathDebugObjUsageRequested(ctxt, XPATH_BOOLEAN);
#endif
        return(ret);
    }
    }
    return(xmlXPathNewBoolean(val));
}

static xmlXPathObjectPtr
xmlXPathCacheNewFloat(xmlXPathContextPtr ctxt, double val)
{
     if ((ctxt != NULL) && (ctxt->cache)) {
    xmlXPathContextCachePtr cache = (xmlXPathContextCachePtr) ctxt->cache;

    if ((cache->numberObjs != NULL) &&
        (cache->numberObjs->number != 0))
    {
        xmlXPathObjectPtr ret;

        ret = (xmlXPathObjectPtr)
        cache->numberObjs->items[--cache->numberObjs->number];
        ret->type = XPATH_NUMBER;
        ret->floatval = val;
#ifdef XP_DEBUG_OBJ_USAGE
        xmlXPathDebugObjUsageRequested(ctxt, XPATH_NUMBER);
#endif
        return(ret);
    } else if ((cache->miscObjs != NULL) &&
        (cache->miscObjs->number != 0))
    {
        xmlXPathObjectPtr ret;

        ret = (xmlXPathObjectPtr)
        cache->miscObjs->items[--cache->miscObjs->number];

        ret->type = XPATH_NUMBER;
        ret->floatval = val;
#ifdef XP_DEBUG_OBJ_USAGE
        xmlXPathDebugObjUsageRequested(ctxt, XPATH_NUMBER);
#endif
        return(ret);
    }
    }
    return(xmlXPathNewFloat(val));
}

static xmlXPathObjectPtr
xmlXPathCacheConvertString(xmlXPathContextPtr ctxt, xmlXPathObjectPtr val) {
    xmlChar *res = NULL;

    if (val == NULL)
    return(xmlXPathCacheNewCString(ctxt, ""));

    switch (val->type) {
    case XPATH_UNDEFINED:
#ifdef DEBUG_EXPR
    xmlGenericError(xmlGenericErrorContext, "STRING: undefined\n");
#endif
    break;
    case XPATH_NODESET:
    case XPATH_XSLT_TREE:
    res = xmlXPathCastNodeSetToString(val->nodesetval);
    break;
    case XPATH_STRING:
    return(val);
    case XPATH_BOOLEAN:
    res = xmlXPathCastBooleanToString(val->boolval);
    break;
    case XPATH_NUMBER:
    res = xmlXPathCastNumberToString(val->floatval);
    break;
    case XPATH_USERS:
    case XPATH_POINT:
    case XPATH_RANGE:
    case XPATH_LOCATIONSET:
    TODO;
    break;
    }
    xmlXPathReleaseObject(ctxt, val);
    if (res == NULL)
    return(xmlXPathCacheNewCString(ctxt, ""));
    return(xmlXPathCacheWrapString(ctxt, res));
}

static xmlXPathObjectPtr
xmlXPathCacheObjectCopy(xmlXPathContextPtr ctxt, xmlXPathObjectPtr val)
{
    if (val == NULL)
    return(NULL);

    if (XP_HAS_CACHE(ctxt)) {
    switch (val->type) {
        case XPATH_NODESET:
        return(xmlXPathCacheWrapNodeSet(ctxt,
            xmlXPathNodeSetMerge(NULL, val->nodesetval)));
        case XPATH_STRING:
        return(xmlXPathCacheNewString(ctxt, val->stringval));
        case XPATH_BOOLEAN:
        return(xmlXPathCacheNewBoolean(ctxt, val->boolval));
        case XPATH_NUMBER:
        return(xmlXPathCacheNewFloat(ctxt, val->floatval));
        default:
        break;
    }
    }
    return(xmlXPathObjectCopy(val));
}

static xmlXPathObjectPtr
xmlXPathCacheConvertBoolean(xmlXPathContextPtr ctxt, xmlXPathObjectPtr val) {
    xmlXPathObjectPtr ret;

    if (val == NULL)
    return(xmlXPathCacheNewBoolean(ctxt, 0));
    if (val->type == XPATH_BOOLEAN)
    return(val);
    ret = xmlXPathCacheNewBoolean(ctxt, xmlXPathCastToBoolean(val));
    xmlXPathReleaseObject(ctxt, val);
    return(ret);
}

static xmlXPathObjectPtr
xmlXPathCacheConvertNumber(xmlXPathContextPtr ctxt, xmlXPathObjectPtr val) {
    xmlXPathObjectPtr ret;

    if (val == NULL)
    return(xmlXPathCacheNewFloat(ctxt, 0.0));
    if (val->type == XPATH_NUMBER)
    return(val);
    ret = xmlXPathCacheNewFloat(ctxt, xmlXPathCastToNumber(val));
    xmlXPathReleaseObject(ctxt, val);
    return(ret);
}

/************************************************************************
 *                                  *
 *      Parser stacks related functions and macros      *
 *                                  *
 ************************************************************************/

static int
xmlXPathSetFrame(xmlXPathParserContextPtr ctxt) {
    int ret;

    if (ctxt == NULL)
        return(0);
    ret = ctxt->valueFrame;
    ctxt->valueFrame = ctxt->valueNr;
    return(ret);
}

static void
xmlXPathPopFrame(xmlXPathParserContextPtr ctxt, int frame) {
    if (ctxt == NULL)
        return;
    if (ctxt->valueNr < ctxt->valueFrame) {
        xmlXPatherror(ctxt, __FILE__, __LINE__, XPATH_STACK_ERROR);
    }
    ctxt->valueFrame = frame;
}

xmlXPathObjectPtr
valuePop(xmlXPathParserContextPtr ctxt)
{
    xmlXPathObjectPtr ret;

    if ((ctxt == NULL) || (ctxt->valueNr <= 0))
        return (NULL);

    if (ctxt->valueNr <= ctxt->valueFrame) {
        xmlXPatherror(ctxt, __FILE__, __LINE__, XPATH_STACK_ERROR);
        return (NULL);
    }

    ctxt->valueNr--;
    if (ctxt->valueNr > 0)
        ctxt->value = ctxt->valueTab[ctxt->valueNr - 1];
    else
        ctxt->value = NULL;
    ret = ctxt->valueTab[ctxt->valueNr];
    ctxt->valueTab[ctxt->valueNr] = NULL;
    return (ret);
}
int
valuePush(xmlXPathParserContextPtr ctxt, xmlXPathObjectPtr value)
{
    if (ctxt == NULL) return(-1);
    if (value == NULL) {
        /*
         * A NULL value typically indicates that a memory allocation failed,
         * so we set ctxt->error here to propagate the error.
         */
    ctxt->error = XPATH_MEMORY_ERROR;
        return(-1);
    }
    if (ctxt->valueNr >= ctxt->valueMax) {
        xmlXPathObjectPtr *tmp;

        if (ctxt->valueMax >= XPATH_MAX_STACK_DEPTH) {
            xmlXPathPErrMemory(ctxt, "XPath stack depth limit reached\n");
            return (-1);
        }
        tmp = (xmlXPathObjectPtr *) xmlRealloc(ctxt->valueTab,
                                             2 * ctxt->valueMax *
                                             sizeof(ctxt->valueTab[0]));
        if (tmp == NULL) {
            xmlXPathPErrMemory(ctxt, "pushing value\n");
            return (-1);
        }
        ctxt->valueMax *= 2;
    ctxt->valueTab = tmp;
    }
    ctxt->valueTab[ctxt->valueNr] = value;
    ctxt->value = value;
    return (ctxt->valueNr++);
}

int
xmlXPathPopBoolean (xmlXPathParserContextPtr ctxt) {
    xmlXPathObjectPtr obj;
    int ret;

    obj = valuePop(ctxt);
    if (obj == NULL) {
    xmlXPathSetError(ctxt, XPATH_INVALID_OPERAND);
    return(0);
    }
    if (obj->type != XPATH_BOOLEAN)
    ret = xmlXPathCastToBoolean(obj);
    else
        ret = obj->boolval;
    xmlXPathReleaseObject(ctxt->context, obj);
    return(ret);
}

double
xmlXPathPopNumber (xmlXPathParserContextPtr ctxt) {
    xmlXPathObjectPtr obj;
    double ret;

    obj = valuePop(ctxt);
    if (obj == NULL) {
    xmlXPathSetError(ctxt, XPATH_INVALID_OPERAND);
    return(0);
    }
    if (obj->type != XPATH_NUMBER)
    ret = xmlXPathCastToNumber(obj);
    else
        ret = obj->floatval;
    xmlXPathReleaseObject(ctxt->context, obj);
    return(ret);
}

xmlChar *
xmlXPathPopString (xmlXPathParserContextPtr ctxt) {
    xmlXPathObjectPtr obj;
    xmlChar * ret;

    obj = valuePop(ctxt);
    if (obj == NULL) {
    xmlXPathSetError(ctxt, XPATH_INVALID_OPERAND);
    return(NULL);
    }
    ret = xmlXPathCastToString(obj);    /* this does required strdup */
    /* TODO: needs refactoring somewhere else */
    if (obj->stringval == ret)
    obj->stringval = NULL;
    xmlXPathReleaseObject(ctxt->context, obj);
    return(ret);
}

xmlNodeSetPtr
xmlXPathPopNodeSet (xmlXPathParserContextPtr ctxt) {
    xmlXPathObjectPtr obj;
    xmlNodeSetPtr ret;

    if (ctxt == NULL) return(NULL);
    if (ctxt->value == NULL) {
    xmlXPathSetError(ctxt, XPATH_INVALID_OPERAND);
    return(NULL);
    }
    if (!xmlXPathStackIsNodeSet(ctxt)) {
    xmlXPathSetTypeError(ctxt);
    return(NULL);
    }
    obj = valuePop(ctxt);
    ret = obj->nodesetval;
#if 0
    /* to fix memory leak of not clearing obj->user */
    if (obj->boolval && obj->user != NULL)
        xmlFreeNodeList((xmlNodePtr) obj->user);
#endif
    obj->nodesetval = NULL;
    xmlXPathReleaseObject(ctxt->context, obj);
    return(ret);
}

void *
xmlXPathPopExternal (xmlXPathParserContextPtr ctxt) {
    xmlXPathObjectPtr obj;
    void * ret;

    if ((ctxt == NULL) || (ctxt->value == NULL)) {
    xmlXPathSetError(ctxt, XPATH_INVALID_OPERAND);
    return(NULL);
    }
    if (ctxt->value->type != XPATH_USERS) {
    xmlXPathSetTypeError(ctxt);
    return(NULL);
    }
    obj = valuePop(ctxt);
    ret = obj->user;
    obj->user = NULL;
    xmlXPathReleaseObject(ctxt->context, obj);
    return(ret);
}

/*
 * Macros for accessing the content. Those should be used only by the parser,
 * and not exported.
 *
 * Dirty macros, i.e. one need to make assumption on the context to use them
 *
 *   CUR_PTR return the current pointer to the xmlChar to be parsed.
 *   CUR     returns the current xmlChar value, i.e. a 8 bit value
 *           in ISO-Latin or UTF-8.
 *           This should be used internally by the parser
 *           only to compare to ASCII values otherwise it would break when
 *           running with UTF-8 encoding.
 *   NXT(n)  returns the n'th next xmlChar. Same as CUR is should be used only
 *           to compare on ASCII based substring.
 *   SKIP(n) Skip n xmlChar, and must also be used only to skip ASCII defined
 *           strings within the parser.
 *   CURRENT Returns the current char value, with the full decoding of
 *           UTF-8 if we are using this mode. It returns an int.
 *   NEXT    Skip to the next character, this does the proper decoding
 *           in UTF-8 mode. It also pop-up unfinished entities on the fly.
 *           It returns the pointer to the current xmlChar.
 */

#define CUR (*ctxt->cur)
#define SKIP(val) ctxt->cur += (val)
#define NXT(val) ctxt->cur[(val)]
#define CUR_PTR ctxt->cur
#define CUR_CHAR(l) xmlXPathCurrentChar(ctxt, &l)

#define COPY_BUF(l,b,i,v)                                              \
    if (l == 1) b[i++] = (xmlChar) v;                                  \
    else i += xmlCopyChar(l,&b[i],v)

#define NEXTL(l)  ctxt->cur += l

#define SKIP_BLANKS                         \
    while (IS_BLANK_CH(*(ctxt->cur))) NEXT

#define CURRENT (*ctxt->cur)
#define NEXT ((*ctxt->cur) ?  ctxt->cur++: ctxt->cur)


#ifndef DBL_DIG
#define DBL_DIG 16
#endif
#ifndef DBL_EPSILON
#define DBL_EPSILON 1E-9
#endif

#define UPPER_DOUBLE 1E9
#define LOWER_DOUBLE 1E-5
#define LOWER_DOUBLE_EXP 5

#define INTEGER_DIGITS DBL_DIG
#define FRACTION_DIGITS (DBL_DIG + 1 + (LOWER_DOUBLE_EXP))
#define EXPONENT_DIGITS (3 + 2)

static void
xmlXPathFormatNumber(double number, char buffer[], int buffersize)
{
    switch (xmlXPathIsInf(number)) {
    case 1:
    if (buffersize > (int)sizeof("Infinity"))
        snprintf(buffer, buffersize, "Infinity");
    break;
    case -1:
    if (buffersize > (int)sizeof("-Infinity"))
        snprintf(buffer, buffersize, "-Infinity");
    break;
    default:
    if (xmlXPathIsNaN(number)) {
        if (buffersize > (int)sizeof("NaN"))
        snprintf(buffer, buffersize, "NaN");
    } else if (number == 0) {
            /* Omit sign for negative zero. */
        snprintf(buffer, buffersize, "0");
    } else if ((number > INT_MIN) && (number < INT_MAX) &&
                   (number == (int) number)) {
        char work[30];
        char *ptr, *cur;
        int value = (int) number;

            ptr = &buffer[0];
        if (value == 0) {
        *ptr++ = '0';
        } else {
        snprintf(work, 29, "%d", value);
        cur = &work[0];
        while ((*cur) && (ptr - buffer < buffersize)) {
            *ptr++ = *cur++;
        }
        }
        if (ptr - buffer < buffersize) {
        *ptr = 0;
        } else if (buffersize > 0) {
        ptr--;
        *ptr = 0;
        }
    } else {
        /*
          For the dimension of work,
              DBL_DIG is number of significant digits
          EXPONENT is only needed for "scientific notation"
              3 is sign, decimal point, and terminating zero
          LOWER_DOUBLE_EXP is max number of leading zeroes in fraction
          Note that this dimension is slightly (a few characters)
          larger than actually necessary.
        */
        char work[DBL_DIG + EXPONENT_DIGITS + 3 + LOWER_DOUBLE_EXP];
        int integer_place, fraction_place;
        char *ptr;
        char *after_fraction;
        double absolute_value;
        int size;

        absolute_value = fabs(number);

        /*
         * First choose format - scientific or regular floating point.
         * In either case, result is in work, and after_fraction points
         * just past the fractional part.
        */
        if ( ((absolute_value > UPPER_DOUBLE) ||
          (absolute_value < LOWER_DOUBLE)) &&
         (absolute_value != 0.0) ) {
        /* Use scientific notation */
        integer_place = DBL_DIG + EXPONENT_DIGITS + 1;
        fraction_place = DBL_DIG - 1;
        size = snprintf(work, sizeof(work),"%*.*e",
             integer_place, fraction_place, number);
        while ((size > 0) && (work[size] != 'e')) size--;

        }
        else {
        /* Use regular notation */
        if (absolute_value > 0.0) {
            integer_place = (int)log10(absolute_value);
            if (integer_place > 0)
                fraction_place = DBL_DIG - integer_place - 1;
            else
                fraction_place = DBL_DIG - integer_place;
        } else {
            fraction_place = 1;
        }
        size = snprintf(work, sizeof(work), "%0.*f",
                fraction_place, number);
        }

        /* Remove leading spaces sometimes inserted by snprintf */
        while (work[0] == ' ') {
            for (ptr = &work[0];(ptr[0] = ptr[1]);ptr++);
        size--;
        }

        /* Remove fractional trailing zeroes */
        after_fraction = work + size;
        ptr = after_fraction;
        while (*(--ptr) == '0')
        ;
        if (*ptr != '.')
            ptr++;
        while ((*ptr++ = *after_fraction++) != 0);

        /* Finally copy result back to caller */
        size = strlen(work) + 1;
        if (size > buffersize) {
        work[buffersize - 1] = 0;
        size = buffersize;
        }
        memmove(buffer, work, size);
    }
    break;
    }
}


/************************************************************************
 *                                  *
 *          Routines to handle NodeSets         *
 *                                  *
 ************************************************************************/

long
xmlXPathOrderDocElems(xmlDocPtr doc) {
    ptrdiff_t count = 0;
    xmlNodePtr cur;

    if (doc == NULL)
    return(-1);
    cur = doc->children;
    while (cur != NULL) {
    if (cur->type == XML_ELEMENT_NODE) {
        cur->content = (void *) (-(++count));
        if (cur->children != NULL) {
        cur = cur->children;
        continue;
        }
    }
    if (cur->next != NULL) {
        cur = cur->next;
        continue;
    }
    do {
        cur = cur->parent;
        if (cur == NULL)
        break;
        if (cur == (xmlNodePtr) doc) {
        cur = NULL;
        break;
        }
        if (cur->next != NULL) {
        cur = cur->next;
        break;
        }
    } while (cur != NULL);
    }
    return((long) count);
}

int
xmlXPathCmpNodes(xmlNodePtr node1, xmlNodePtr node2) {
    int depth1, depth2;
    int attr1 = 0, attr2 = 0;
    xmlNodePtr attrNode1 = NULL, attrNode2 = NULL;
    xmlNodePtr cur, root;

    if ((node1 == NULL) || (node2 == NULL))
    return(-2);
    /*
     * a couple of optimizations which will avoid computations in most cases
     */
    if (node1 == node2)     /* trivial case */
    return(0);
    if (node1->type == XML_ATTRIBUTE_NODE) {
    attr1 = 1;
    attrNode1 = node1;
    node1 = node1->parent;
    }
    if (node2->type == XML_ATTRIBUTE_NODE) {
    attr2 = 1;
    attrNode2 = node2;
    node2 = node2->parent;
    }
    if (node1 == node2) {
    if (attr1 == attr2) {
        /* not required, but we keep attributes in order */
        if (attr1 != 0) {
            cur = attrNode2->prev;
        while (cur != NULL) {
            if (cur == attrNode1)
                return (1);
            cur = cur->prev;
        }
        return (-1);
        }
        return(0);
    }
    if (attr2 == 1)
        return(1);
    return(-1);
    }
    if ((node1->type == XML_NAMESPACE_DECL) ||
        (node2->type == XML_NAMESPACE_DECL))
    return(1);
    if (node1 == node2->prev)
    return(1);
    if (node1 == node2->next)
    return(-1);

    /*
     * Speedup using document order if available.
     */
    if ((node1->type == XML_ELEMENT_NODE) &&
    (node2->type == XML_ELEMENT_NODE) &&
    (0 > (ptrdiff_t) node1->content) &&
    (0 > (ptrdiff_t) node2->content) &&
    (node1->doc == node2->doc)) {
    ptrdiff_t l1, l2;

    l1 = -((ptrdiff_t) node1->content);
    l2 = -((ptrdiff_t) node2->content);
    if (l1 < l2)
        return(1);
    if (l1 > l2)
        return(-1);
    }

    /*
     * compute depth to root
     */
    for (depth2 = 0, cur = node2;cur->parent != NULL;cur = cur->parent) {
    if (cur->parent == node1)
        return(1);
    depth2++;
    }
    root = cur;
    for (depth1 = 0, cur = node1;cur->parent != NULL;cur = cur->parent) {
    if (cur->parent == node2)
        return(-1);
    depth1++;
    }
    /*
     * Distinct document (or distinct entities :-( ) case.
     */
    if (root != cur) {
    return(-2);
    }
    /*
     * get the nearest common ancestor.
     */
    while (depth1 > depth2) {
    depth1--;
    node1 = node1->parent;
    }
    while (depth2 > depth1) {
    depth2--;
    node2 = node2->parent;
    }
    while (node1->parent != node2->parent) {
    node1 = node1->parent;
    node2 = node2->parent;
    /* should not happen but just in case ... */
    if ((node1 == NULL) || (node2 == NULL))
        return(-2);
    }
    /*
     * Find who's first.
     */
    if (node1 == node2->prev)
    return(1);
    if (node1 == node2->next)
    return(-1);
    /*
     * Speedup using document order if available.
     */
    if ((node1->type == XML_ELEMENT_NODE) &&
    (node2->type == XML_ELEMENT_NODE) &&
    (0 > (ptrdiff_t) node1->content) &&
    (0 > (ptrdiff_t) node2->content) &&
    (node1->doc == node2->doc)) {
    ptrdiff_t l1, l2;

    l1 = -((ptrdiff_t) node1->content);
    l2 = -((ptrdiff_t) node2->content);
    if (l1 < l2)
        return(1);
    if (l1 > l2)
        return(-1);
    }

    for (cur = node1->next;cur != NULL;cur = cur->next)
    if (cur == node2)
        return(1);
    return(-1); /* assume there is no sibling list corruption */
}

void
xmlXPathNodeSetSort(xmlNodeSetPtr set) {
#ifndef WITH_TIM_SORT
    int i, j, incr, len;
    xmlNodePtr tmp;
#endif

    if (set == NULL)
    return;

#ifndef WITH_TIM_SORT
    /*
     * Use the old Shell's sort implementation to sort the node-set
     * Timsort ought to be quite faster
     */
    len = set->nodeNr;
    for (incr = len / 2; incr > 0; incr /= 2) {
    for (i = incr; i < len; i++) {
        j = i - incr;
        while (j >= 0) {
#ifdef XP_OPTIMIZED_NON_ELEM_COMPARISON
        if (xmlXPathCmpNodesExt(set->nodeTab[j],
            set->nodeTab[j + incr]) == -1)
#else
        if (xmlXPathCmpNodes(set->nodeTab[j],
            set->nodeTab[j + incr]) == -1)
#endif
        {
            tmp = set->nodeTab[j];
            set->nodeTab[j] = set->nodeTab[j + incr];
            set->nodeTab[j + incr] = tmp;
            j -= incr;
        } else
            break;
        }
    }
    }
#else /* WITH_TIM_SORT */
    libxml_domnode_tim_sort(set->nodeTab, set->nodeNr);
#endif /* WITH_TIM_SORT */
}

#define XML_NODESET_DEFAULT 10

static xmlNodePtr
xmlXPathNodeSetDupNs(xmlNodePtr node, xmlNsPtr ns) {
    xmlNsPtr cur;

    if ((ns == NULL) || (ns->type != XML_NAMESPACE_DECL))
    return(NULL);
    if ((node == NULL) || (node->type == XML_NAMESPACE_DECL))
    return((xmlNodePtr) ns);

    /*
     * Allocate a new Namespace and fill the fields.
     */
    cur = (xmlNsPtr) xmlMalloc(sizeof(xmlNs));
    if (cur == NULL) {
        xmlXPathErrMemory(NULL, "duplicating namespace\n");
    return(NULL);
    }
    memset(cur, 0, sizeof(xmlNs));
    cur->type = XML_NAMESPACE_DECL;
    if (ns->href != NULL)
    cur->href = xmlStrdup(ns->href);
    if (ns->prefix != NULL)
    cur->prefix = xmlStrdup(ns->prefix);
    cur->next = (xmlNsPtr) node;
    return((xmlNodePtr) cur);
}

void
xmlXPathNodeSetFreeNs(xmlNsPtr ns) {
    if ((ns == NULL) || (ns->type != XML_NAMESPACE_DECL))
    return;

    if ((ns->next != NULL) && (ns->next->type != XML_NAMESPACE_DECL)) {
    if (ns->href != NULL)
        xmlFree((xmlChar *)ns->href);
    if (ns->prefix != NULL)
        xmlFree((xmlChar *)ns->prefix);
    xmlFree(ns);
    }
}

xmlNodeSetPtr
xmlXPathNodeSetCreate(xmlNodePtr val) {
    xmlNodeSetPtr ret;

    ret = (xmlNodeSetPtr) xmlMalloc(sizeof(xmlNodeSet));
    if (ret == NULL) {
        xmlXPathErrMemory(NULL, "creating nodeset\n");
    return(NULL);
    }
    memset(ret, 0 , (size_t) sizeof(xmlNodeSet));
    if (val != NULL) {
        ret->nodeTab = (xmlNodePtr *) xmlMalloc(XML_NODESET_DEFAULT *
                         sizeof(xmlNodePtr));
    if (ret->nodeTab == NULL) {
        xmlXPathErrMemory(NULL, "creating nodeset\n");
        xmlFree(ret);
        return(NULL);
    }
    memset(ret->nodeTab, 0 ,
           XML_NODESET_DEFAULT * (size_t) sizeof(xmlNodePtr));
        ret->nodeMax = XML_NODESET_DEFAULT;
    if (val->type == XML_NAMESPACE_DECL) {
        xmlNsPtr ns = (xmlNsPtr) val;

            /* TODO: Check memory error. */
        ret->nodeTab[ret->nodeNr++] =
        xmlXPathNodeSetDupNs((xmlNodePtr) ns->next, ns);
    } else
        ret->nodeTab[ret->nodeNr++] = val;
    }
    return(ret);
}

int
xmlXPathNodeSetContains (xmlNodeSetPtr cur, xmlNodePtr val) {
    int i;

    if ((cur == NULL) || (val == NULL)) return(0);
    if (val->type == XML_NAMESPACE_DECL) {
    for (i = 0; i < cur->nodeNr; i++) {
        if (cur->nodeTab[i]->type == XML_NAMESPACE_DECL) {
        xmlNsPtr ns1, ns2;

        ns1 = (xmlNsPtr) val;
        ns2 = (xmlNsPtr) cur->nodeTab[i];
        if (ns1 == ns2)
            return(1);
        if ((ns1->next != NULL) && (ns2->next == ns1->next) &&
                (xmlStrEqual(ns1->prefix, ns2->prefix)))
            return(1);
        }
    }
    } else {
    for (i = 0; i < cur->nodeNr; i++) {
        if (cur->nodeTab[i] == val)
        return(1);
    }
    }
    return(0);
}

int
xmlXPathNodeSetAddNs(xmlNodeSetPtr cur, xmlNodePtr node, xmlNsPtr ns) {
    int i;


    if ((cur == NULL) || (ns == NULL) || (node == NULL) ||
        (ns->type != XML_NAMESPACE_DECL) ||
    (node->type != XML_ELEMENT_NODE))
    return(-1);

    /* @@ with_ns to check whether namespace nodes should be looked at @@ */
    /*
     * prevent duplicates
     */
    for (i = 0;i < cur->nodeNr;i++) {
        if ((cur->nodeTab[i] != NULL) &&
        (cur->nodeTab[i]->type == XML_NAMESPACE_DECL) &&
        (((xmlNsPtr)cur->nodeTab[i])->next == (xmlNsPtr) node) &&
        (xmlStrEqual(ns->prefix, ((xmlNsPtr)cur->nodeTab[i])->prefix)))
        return(0);
    }

    /*
     * grow the nodeTab if needed
     */
    if (cur->nodeMax == 0) {
        cur->nodeTab = (xmlNodePtr *) xmlMalloc(XML_NODESET_DEFAULT *
                         sizeof(xmlNodePtr));
    if (cur->nodeTab == NULL) {
        xmlXPathErrMemory(NULL, "growing nodeset\n");
        return(-1);
    }
    memset(cur->nodeTab, 0 ,
           XML_NODESET_DEFAULT * (size_t) sizeof(xmlNodePtr));
        cur->nodeMax = XML_NODESET_DEFAULT;
    } else if (cur->nodeNr == cur->nodeMax) {
        xmlNodePtr *temp;

        if (cur->nodeMax >= XPATH_MAX_NODESET_LENGTH) {
            xmlXPathErrMemory(NULL, "growing nodeset hit limit\n");
            return(-1);
        }
    temp = (xmlNodePtr *) xmlRealloc(cur->nodeTab, cur->nodeMax * 2 *
                      sizeof(xmlNodePtr));
    if (temp == NULL) {
        xmlXPathErrMemory(NULL, "growing nodeset\n");
        return(-1);
    }
        cur->nodeMax *= 2;
    cur->nodeTab = temp;
    }
    /* TODO: Check memory error. */
    cur->nodeTab[cur->nodeNr++] = xmlXPathNodeSetDupNs(node, ns);
    return(0);
}

int
xmlXPathNodeSetAdd(xmlNodeSetPtr cur, xmlNodePtr val) {
    int i;

    if ((cur == NULL) || (val == NULL)) return(-1);

    /* @@ with_ns to check whether namespace nodes should be looked at @@ */
    /*
     * prevent duplicates
     */
    for (i = 0;i < cur->nodeNr;i++)
        if (cur->nodeTab[i] == val) return(0);

    /*
     * grow the nodeTab if needed
     */
    if (cur->nodeMax == 0) {
        cur->nodeTab = (xmlNodePtr *) xmlMalloc(XML_NODESET_DEFAULT *
                         sizeof(xmlNodePtr));
    if (cur->nodeTab == NULL) {
        xmlXPathErrMemory(NULL, "growing nodeset\n");
        return(-1);
    }
    memset(cur->nodeTab, 0 ,
           XML_NODESET_DEFAULT * (size_t) sizeof(xmlNodePtr));
        cur->nodeMax = XML_NODESET_DEFAULT;
    } else if (cur->nodeNr == cur->nodeMax) {
        xmlNodePtr *temp;

        if (cur->nodeMax >= XPATH_MAX_NODESET_LENGTH) {
            xmlXPathErrMemory(NULL, "growing nodeset hit limit\n");
            return(-1);
        }
    temp = (xmlNodePtr *) xmlRealloc(cur->nodeTab, cur->nodeMax * 2 *
                      sizeof(xmlNodePtr));
    if (temp == NULL) {
        xmlXPathErrMemory(NULL, "growing nodeset\n");
        return(-1);
    }
        cur->nodeMax *= 2;
    cur->nodeTab = temp;
    }
    if (val->type == XML_NAMESPACE_DECL) {
    xmlNsPtr ns = (xmlNsPtr) val;

        /* TODO: Check memory error. */
    cur->nodeTab[cur->nodeNr++] =
        xmlXPathNodeSetDupNs((xmlNodePtr) ns->next, ns);
    } else
    cur->nodeTab[cur->nodeNr++] = val;
    return(0);
}

int
xmlXPathNodeSetAddUnique(xmlNodeSetPtr cur, xmlNodePtr val) {
    if ((cur == NULL) || (val == NULL)) return(-1);

    /* @@ with_ns to check whether namespace nodes should be looked at @@ */
    /*
     * grow the nodeTab if needed
     */
    if (cur->nodeMax == 0) {
        cur->nodeTab = (xmlNodePtr *) xmlMalloc(XML_NODESET_DEFAULT *
                         sizeof(xmlNodePtr));
    if (cur->nodeTab == NULL) {
        xmlXPathErrMemory(NULL, "growing nodeset\n");
        return(-1);
    }
    memset(cur->nodeTab, 0 ,
           XML_NODESET_DEFAULT * (size_t) sizeof(xmlNodePtr));
        cur->nodeMax = XML_NODESET_DEFAULT;
    } else if (cur->nodeNr == cur->nodeMax) {
        xmlNodePtr *temp;

        if (cur->nodeMax >= XPATH_MAX_NODESET_LENGTH) {
            xmlXPathErrMemory(NULL, "growing nodeset hit limit\n");
            return(-1);
        }
    temp = (xmlNodePtr *) xmlRealloc(cur->nodeTab, cur->nodeMax * 2 *
                      sizeof(xmlNodePtr));
    if (temp == NULL) {
        xmlXPathErrMemory(NULL, "growing nodeset\n");
        return(-1);
    }
    cur->nodeTab = temp;
        cur->nodeMax *= 2;
    }
    if (val->type == XML_NAMESPACE_DECL) {
    xmlNsPtr ns = (xmlNsPtr) val;

        /* TODO: Check memory error. */
    cur->nodeTab[cur->nodeNr++] =
        xmlXPathNodeSetDupNs((xmlNodePtr) ns->next, ns);
    } else
    cur->nodeTab[cur->nodeNr++] = val;
    return(0);
}

xmlNodeSetPtr
xmlXPathNodeSetMerge(xmlNodeSetPtr val1, xmlNodeSetPtr val2) {
    int i, j, initNr, skip;
    xmlNodePtr n1, n2;

    if (val2 == NULL) return(val1);
    if (val1 == NULL) {
    val1 = xmlXPathNodeSetCreate(NULL);
    if (val1 == NULL)
        return (NULL);
#if 0
    /*
    * TODO: The optimization won't work in every case, since
    *  those nasty namespace nodes need to be added with
    *  xmlXPathNodeSetDupNs() to the set; thus a pure
    *  memcpy is not possible.
    *  If there was a flag on the nodesetval, indicating that
    *  some temporary nodes are in, that would be helpful.
    */
    /*
    * Optimization: Create an equally sized node-set
    * and memcpy the content.
    */
    val1 = xmlXPathNodeSetCreateSize(val2->nodeNr);
    if (val1 == NULL)
        return(NULL);
    if (val2->nodeNr != 0) {
        if (val2->nodeNr == 1)
        *(val1->nodeTab) = *(val2->nodeTab);
        else {
        memcpy(val1->nodeTab, val2->nodeTab,
            val2->nodeNr * sizeof(xmlNodePtr));
        }
        val1->nodeNr = val2->nodeNr;
    }
    return(val1);
#endif
    }

    /* @@ with_ns to check whether namespace nodes should be looked at @@ */
    initNr = val1->nodeNr;

    for (i = 0;i < val2->nodeNr;i++) {
    n2 = val2->nodeTab[i];
    /*
     * check against duplicates
     */
    skip = 0;
    for (j = 0; j < initNr; j++) {
        n1 = val1->nodeTab[j];
        if (n1 == n2) {
        skip = 1;
        break;
        } else if ((n1->type == XML_NAMESPACE_DECL) &&
               (n2->type == XML_NAMESPACE_DECL)) {
        if ((((xmlNsPtr) n1)->next == ((xmlNsPtr) n2)->next) &&
            (xmlStrEqual(((xmlNsPtr) n1)->prefix,
            ((xmlNsPtr) n2)->prefix)))
        {
            skip = 1;
            break;
        }
        }
    }
    if (skip)
        continue;

    /*
     * grow the nodeTab if needed
     */
    if (val1->nodeMax == 0) {
        val1->nodeTab = (xmlNodePtr *) xmlMalloc(XML_NODESET_DEFAULT *
                            sizeof(xmlNodePtr));
        if (val1->nodeTab == NULL) {
            xmlXPathErrMemory(NULL, "merging nodeset\n");
        return(NULL);
        }
        memset(val1->nodeTab, 0 ,
           XML_NODESET_DEFAULT * (size_t) sizeof(xmlNodePtr));
        val1->nodeMax = XML_NODESET_DEFAULT;
    } else if (val1->nodeNr == val1->nodeMax) {
        xmlNodePtr *temp;

            if (val1->nodeMax >= XPATH_MAX_NODESET_LENGTH) {
                xmlXPathErrMemory(NULL, "merging nodeset hit limit\n");
                return(NULL);
            }
        temp = (xmlNodePtr *) xmlRealloc(val1->nodeTab, val1->nodeMax * 2 *
                         sizeof(xmlNodePtr));
        if (temp == NULL) {
            xmlXPathErrMemory(NULL, "merging nodeset\n");
        return(NULL);
        }
        val1->nodeTab = temp;
        val1->nodeMax *= 2;
    }
    if (n2->type == XML_NAMESPACE_DECL) {
        xmlNsPtr ns = (xmlNsPtr) n2;

            /* TODO: Check memory error. */
        val1->nodeTab[val1->nodeNr++] =
        xmlXPathNodeSetDupNs((xmlNodePtr) ns->next, ns);
    } else
        val1->nodeTab[val1->nodeNr++] = n2;
    }

    return(val1);
}


static xmlNodeSetPtr
xmlXPathNodeSetMergeAndClear(xmlNodeSetPtr set1, xmlNodeSetPtr set2)
{
    {
    int i, j, initNbSet1;
    xmlNodePtr n1, n2;

    initNbSet1 = set1->nodeNr;
    for (i = 0;i < set2->nodeNr;i++) {
        n2 = set2->nodeTab[i];
        /*
        * Skip duplicates.
        */
        for (j = 0; j < initNbSet1; j++) {
        n1 = set1->nodeTab[j];
        if (n1 == n2) {
            goto skip_node;
        } else if ((n1->type == XML_NAMESPACE_DECL) &&
            (n2->type == XML_NAMESPACE_DECL))
        {
            if ((((xmlNsPtr) n1)->next == ((xmlNsPtr) n2)->next) &&
            (xmlStrEqual(((xmlNsPtr) n1)->prefix,
            ((xmlNsPtr) n2)->prefix)))
            {
            /*
            * Free the namespace node.
            */
            set2->nodeTab[i] = NULL;
            xmlXPathNodeSetFreeNs((xmlNsPtr) n2);
            goto skip_node;
            }
        }
        }
        /*
        * grow the nodeTab if needed
        */
        if (set1->nodeMax == 0) {
        set1->nodeTab = (xmlNodePtr *) xmlMalloc(
            XML_NODESET_DEFAULT * sizeof(xmlNodePtr));
        if (set1->nodeTab == NULL) {
            xmlXPathErrMemory(NULL, "merging nodeset\n");
            return(NULL);
        }
        memset(set1->nodeTab, 0,
            XML_NODESET_DEFAULT * (size_t) sizeof(xmlNodePtr));
        set1->nodeMax = XML_NODESET_DEFAULT;
        } else if (set1->nodeNr >= set1->nodeMax) {
        xmlNodePtr *temp;

                if (set1->nodeMax >= XPATH_MAX_NODESET_LENGTH) {
                    xmlXPathErrMemory(NULL, "merging nodeset hit limit\n");
                    return(NULL);
                }
        temp = (xmlNodePtr *) xmlRealloc(
            set1->nodeTab, set1->nodeMax * 2 * sizeof(xmlNodePtr));
        if (temp == NULL) {
            xmlXPathErrMemory(NULL, "merging nodeset\n");
            return(NULL);
        }
        set1->nodeTab = temp;
        set1->nodeMax *= 2;
        }
        set1->nodeTab[set1->nodeNr++] = n2;
skip_node:
        {}
    }
    }
    set2->nodeNr = 0;
    return(set1);
}

static xmlNodeSetPtr
xmlXPathNodeSetMergeAndClearNoDupls(xmlNodeSetPtr set1, xmlNodeSetPtr set2)
{
    {
    int i;
    xmlNodePtr n2;

    for (i = 0;i < set2->nodeNr;i++) {
        n2 = set2->nodeTab[i];
        if (set1->nodeMax == 0) {
        set1->nodeTab = (xmlNodePtr *) xmlMalloc(
            XML_NODESET_DEFAULT * sizeof(xmlNodePtr));
        if (set1->nodeTab == NULL) {
            xmlXPathErrMemory(NULL, "merging nodeset\n");
            return(NULL);
        }
        memset(set1->nodeTab, 0,
            XML_NODESET_DEFAULT * (size_t) sizeof(xmlNodePtr));
        set1->nodeMax = XML_NODESET_DEFAULT;
        } else if (set1->nodeNr >= set1->nodeMax) {
        xmlNodePtr *temp;

                if (set1->nodeMax >= XPATH_MAX_NODESET_LENGTH) {
                    xmlXPathErrMemory(NULL, "merging nodeset hit limit\n");
                    return(NULL);
                }
        temp = (xmlNodePtr *) xmlRealloc(
            set1->nodeTab, set1->nodeMax * 2 * sizeof(xmlNodePtr));
        if (temp == NULL) {
            xmlXPathErrMemory(NULL, "merging nodeset\n");
            return(NULL);
        }
        set1->nodeTab = temp;
        set1->nodeMax *= 2;
        }
        set1->nodeTab[set1->nodeNr++] = n2;
    }
    }
    set2->nodeNr = 0;
    return(set1);
}

void
xmlXPathNodeSetDel(xmlNodeSetPtr cur, xmlNodePtr val) {
    int i;

    if (cur == NULL) return;
    if (val == NULL) return;

    /*
     * find node in nodeTab
     */
    for (i = 0;i < cur->nodeNr;i++)
        if (cur->nodeTab[i] == val) break;

    if (i >= cur->nodeNr) { /* not found */
#ifdef DEBUG
        xmlGenericError(xmlGenericErrorContext,
            "xmlXPathNodeSetDel: Node %s wasn't found in NodeList\n",
        val->name);
#endif
        return;
    }
    if ((cur->nodeTab[i] != NULL) &&
    (cur->nodeTab[i]->type == XML_NAMESPACE_DECL))
    xmlXPathNodeSetFreeNs((xmlNsPtr) cur->nodeTab[i]);
    cur->nodeNr--;
    for (;i < cur->nodeNr;i++)
        cur->nodeTab[i] = cur->nodeTab[i + 1];
    cur->nodeTab[cur->nodeNr] = NULL;
}

void
xmlXPathNodeSetRemove(xmlNodeSetPtr cur, int val) {
    if (cur == NULL) return;
    if (val >= cur->nodeNr) return;
    if ((cur->nodeTab[val] != NULL) &&
    (cur->nodeTab[val]->type == XML_NAMESPACE_DECL))
    xmlXPathNodeSetFreeNs((xmlNsPtr) cur->nodeTab[val]);
    cur->nodeNr--;
    for (;val < cur->nodeNr;val++)
        cur->nodeTab[val] = cur->nodeTab[val + 1];
    cur->nodeTab[cur->nodeNr] = NULL;
}

void
xmlXPathFreeNodeSet(xmlNodeSetPtr obj) {
    if (obj == NULL) return;
    if (obj->nodeTab != NULL) {
    int i;

    /* @@ with_ns to check whether namespace nodes should be looked at @@ */
    for (i = 0;i < obj->nodeNr;i++)
        if ((obj->nodeTab[i] != NULL) &&
        (obj->nodeTab[i]->type == XML_NAMESPACE_DECL))
        xmlXPathNodeSetFreeNs((xmlNsPtr) obj->nodeTab[i]);
    xmlFree(obj->nodeTab);
    }
    xmlFree(obj);
}

static void
xmlXPathNodeSetClearFromPos(xmlNodeSetPtr set, int pos, int hasNsNodes)
{
    if ((set == NULL) || (pos >= set->nodeNr))
    return;
    else if ((hasNsNodes)) {
    int i;
    xmlNodePtr node;

    for (i = pos; i < set->nodeNr; i++) {
        node = set->nodeTab[i];
        if ((node != NULL) &&
        (node->type == XML_NAMESPACE_DECL))
        xmlXPathNodeSetFreeNs((xmlNsPtr) node);
    }
    }
    set->nodeNr = pos;
}

static void
xmlXPathNodeSetClear(xmlNodeSetPtr set, int hasNsNodes)
{
    xmlXPathNodeSetClearFromPos(set, 0, hasNsNodes);
}

static void
xmlXPathNodeSetKeepLast(xmlNodeSetPtr set)
{
    int i;
    xmlNodePtr node;

    if ((set == NULL) || (set->nodeNr <= 1))
    return;
    for (i = 0; i < set->nodeNr - 1; i++) {
        node = set->nodeTab[i];
        if ((node != NULL) &&
            (node->type == XML_NAMESPACE_DECL))
            xmlXPathNodeSetFreeNs((xmlNsPtr) node);
    }
    set->nodeTab[0] = set->nodeTab[set->nodeNr-1];
    set->nodeNr = 1;
}

static void
xmlXPathFreeValueTree(xmlNodeSetPtr obj) {
    int i;

    if (obj == NULL) return;

    if (obj->nodeTab != NULL) {
    for (i = 0;i < obj->nodeNr;i++) {
        if (obj->nodeTab[i] != NULL) {
        if (obj->nodeTab[i]->type == XML_NAMESPACE_DECL) {
            xmlXPathNodeSetFreeNs((xmlNsPtr) obj->nodeTab[i]);
        } else {
            xmlFreeNodeList(obj->nodeTab[i]);
        }
        }
    }
    xmlFree(obj->nodeTab);
    }
    xmlFree(obj);
}

#if defined(DEBUG) || defined(DEBUG_STEP)

void
xmlGenericErrorContextNodeSet(FILE *output, xmlNodeSetPtr obj) {
    int i;

    if (output == NULL) output = xmlGenericErrorContext;
    if (obj == NULL)  {
        fprintf(output, "NodeSet == NULL !\n");
    return;
    }
    if (obj->nodeNr == 0) {
        fprintf(output, "NodeSet is empty\n");
    return;
    }
    if (obj->nodeTab == NULL) {
    fprintf(output, " nodeTab == NULL !\n");
    return;
    }
    for (i = 0; i < obj->nodeNr; i++) {
        if (obj->nodeTab[i] == NULL) {
        fprintf(output, " NULL !\n");
        return;
        }
    if ((obj->nodeTab[i]->type == XML_DOCUMENT_NODE) ||
        (obj->nodeTab[i]->type == XML_HTML_DOCUMENT_NODE))
        fprintf(output, " /");
    else if (obj->nodeTab[i]->name == NULL)
        fprintf(output, " noname!");
    else fprintf(output, " %s", obj->nodeTab[i]->name);
    }
    fprintf(output, "\n");
}
#endif

xmlXPathObjectPtr
xmlXPathNewNodeSet(xmlNodePtr val) {
    xmlXPathObjectPtr ret;

    ret = (xmlXPathObjectPtr) xmlMalloc(sizeof(xmlXPathObject));
    if (ret == NULL) {
        xmlXPathErrMemory(NULL, "creating nodeset\n");
    return(NULL);
    }
    memset(ret, 0 , (size_t) sizeof(xmlXPathObject));
    ret->type = XPATH_NODESET;
    ret->boolval = 0;
    /* TODO: Check memory error. */
    ret->nodesetval = xmlXPathNodeSetCreate(val);
    /* @@ with_ns to check whether namespace nodes should be looked at @@ */
#ifdef XP_DEBUG_OBJ_USAGE
    xmlXPathDebugObjUsageRequested(NULL, XPATH_NODESET);
#endif
    return(ret);
}

xmlXPathObjectPtr
xmlXPathNewValueTree(xmlNodePtr val) {
    xmlXPathObjectPtr ret;

    ret = (xmlXPathObjectPtr) xmlMalloc(sizeof(xmlXPathObject));
    if (ret == NULL) {
        xmlXPathErrMemory(NULL, "creating result value tree\n");
    return(NULL);
    }
    memset(ret, 0 , (size_t) sizeof(xmlXPathObject));
    ret->type = XPATH_XSLT_TREE;
    ret->boolval = 1;
    ret->user = (void *) val;
    ret->nodesetval = xmlXPathNodeSetCreate(val);
#ifdef XP_DEBUG_OBJ_USAGE
    xmlXPathDebugObjUsageRequested(NULL, XPATH_XSLT_TREE);
#endif
    return(ret);
}

xmlXPathObjectPtr
xmlXPathNewNodeSetList(xmlNodeSetPtr val)
{
    xmlXPathObjectPtr ret;
    int i;

    if (val == NULL)
        ret = NULL;
    else if (val->nodeTab == NULL)
        ret = xmlXPathNewNodeSet(NULL);
    else {
        ret = xmlXPathNewNodeSet(val->nodeTab[0]);
        if (ret) {
            for (i = 1; i < val->nodeNr; ++i) {
                /* TODO: Propagate memory error. */
                if (xmlXPathNodeSetAddUnique(ret->nodesetval, val->nodeTab[i])
            < 0) break;
        }
    }
    }

    return (ret);
}

xmlXPathObjectPtr
xmlXPathWrapNodeSet(xmlNodeSetPtr val) {
    xmlXPathObjectPtr ret;

    ret = (xmlXPathObjectPtr) xmlMalloc(sizeof(xmlXPathObject));
    if (ret == NULL) {
        xmlXPathErrMemory(NULL, "creating node set object\n");
    return(NULL);
    }
    memset(ret, 0 , (size_t) sizeof(xmlXPathObject));
    ret->type = XPATH_NODESET;
    ret->nodesetval = val;
#ifdef XP_DEBUG_OBJ_USAGE
    xmlXPathDebugObjUsageRequested(NULL, XPATH_NODESET);
#endif
    return(ret);
}

void
xmlXPathFreeNodeSetList(xmlXPathObjectPtr obj) {
    if (obj == NULL) return;
#ifdef XP_DEBUG_OBJ_USAGE
    xmlXPathDebugObjUsageReleased(NULL, obj->type);
#endif
    xmlFree(obj);
}

xmlNodeSetPtr
xmlXPathDifference (xmlNodeSetPtr nodes1, xmlNodeSetPtr nodes2) {
    xmlNodeSetPtr ret;
    int i, l1;
    xmlNodePtr cur;

    if (xmlXPathNodeSetIsEmpty(nodes2))
    return(nodes1);

    /* TODO: Check memory error. */
    ret = xmlXPathNodeSetCreate(NULL);
    if (xmlXPathNodeSetIsEmpty(nodes1))
    return(ret);

    l1 = xmlXPathNodeSetGetLength(nodes1);

    for (i = 0; i < l1; i++) {
    cur = xmlXPathNodeSetItem(nodes1, i);
    if (!xmlXPathNodeSetContains(nodes2, cur)) {
            /* TODO: Propagate memory error. */
        if (xmlXPathNodeSetAddUnique(ret, cur) < 0)
            break;
    }
    }
    return(ret);
}

xmlNodeSetPtr
xmlXPathIntersection (xmlNodeSetPtr nodes1, xmlNodeSetPtr nodes2) {
    xmlNodeSetPtr ret = xmlXPathNodeSetCreate(NULL);
    int i, l1;
    xmlNodePtr cur;

    if (ret == NULL)
        return(ret);
    if (xmlXPathNodeSetIsEmpty(nodes1))
    return(ret);
    if (xmlXPathNodeSetIsEmpty(nodes2))
    return(ret);

    l1 = xmlXPathNodeSetGetLength(nodes1);

    for (i = 0; i < l1; i++) {
    cur = xmlXPathNodeSetItem(nodes1, i);
    if (xmlXPathNodeSetContains(nodes2, cur)) {
            /* TODO: Propagate memory error. */
        if (xmlXPathNodeSetAddUnique(ret, cur) < 0)
            break;
    }
    }
    return(ret);
}

xmlNodeSetPtr
xmlXPathDistinctSorted (xmlNodeSetPtr nodes) {
    xmlNodeSetPtr ret;
    xmlHashTablePtr hash;
    int i, l;
    xmlChar * strval;
    xmlNodePtr cur;

    if (xmlXPathNodeSetIsEmpty(nodes))
    return(nodes);

    ret = xmlXPathNodeSetCreate(NULL);
    if (ret == NULL)
        return(ret);
    l = xmlXPathNodeSetGetLength(nodes);
    hash = xmlHashCreate (l);
    for (i = 0; i < l; i++) {
    cur = xmlXPathNodeSetItem(nodes, i);
    strval = xmlXPathCastNodeToString(cur);
    if (xmlHashLookup(hash, strval) == NULL) {
        xmlHashAddEntry(hash, strval, strval);
            /* TODO: Propagate memory error. */
        if (xmlXPathNodeSetAddUnique(ret, cur) < 0)
            break;
    } else {
        xmlFree(strval);
    }
    }
    xmlHashFree(hash, xmlHashDefaultDeallocator);
    return(ret);
}

xmlNodeSetPtr
xmlXPathDistinct (xmlNodeSetPtr nodes) {
    if (xmlXPathNodeSetIsEmpty(nodes))
    return(nodes);

    xmlXPathNodeSetSort(nodes);
    return(xmlXPathDistinctSorted(nodes));
}

int
xmlXPathHasSameNodes (xmlNodeSetPtr nodes1, xmlNodeSetPtr nodes2) {
    int i, l;
    xmlNodePtr cur;

    if (xmlXPathNodeSetIsEmpty(nodes1) ||
    xmlXPathNodeSetIsEmpty(nodes2))
    return(0);

    l = xmlXPathNodeSetGetLength(nodes1);
    for (i = 0; i < l; i++) {
    cur = xmlXPathNodeSetItem(nodes1, i);
    if (xmlXPathNodeSetContains(nodes2, cur))
        return(1);
    }
    return(0);
}

xmlNodeSetPtr
xmlXPathNodeLeadingSorted (xmlNodeSetPtr nodes, xmlNodePtr node) {
    int i, l;
    xmlNodePtr cur;
    xmlNodeSetPtr ret;

    if (node == NULL)
    return(nodes);

    ret = xmlXPathNodeSetCreate(NULL);
    if (ret == NULL)
        return(ret);
    if (xmlXPathNodeSetIsEmpty(nodes) ||
    (!xmlXPathNodeSetContains(nodes, node)))
    return(ret);

    l = xmlXPathNodeSetGetLength(nodes);
    for (i = 0; i < l; i++) {
    cur = xmlXPathNodeSetItem(nodes, i);
    if (cur == node)
        break;
        /* TODO: Propagate memory error. */
    if (xmlXPathNodeSetAddUnique(ret, cur) < 0)
        break;
    }
    return(ret);
}

xmlNodeSetPtr
xmlXPathNodeLeading (xmlNodeSetPtr nodes, xmlNodePtr node) {
    xmlXPathNodeSetSort(nodes);
    return(xmlXPathNodeLeadingSorted(nodes, node));
}

xmlNodeSetPtr
xmlXPathLeadingSorted (xmlNodeSetPtr nodes1, xmlNodeSetPtr nodes2) {
    if (xmlXPathNodeSetIsEmpty(nodes2))
    return(nodes1);
    return(xmlXPathNodeLeadingSorted(nodes1,
                     xmlXPathNodeSetItem(nodes2, 1)));
}

xmlNodeSetPtr
xmlXPathLeading (xmlNodeSetPtr nodes1, xmlNodeSetPtr nodes2) {
    if (xmlXPathNodeSetIsEmpty(nodes2))
    return(nodes1);
    if (xmlXPathNodeSetIsEmpty(nodes1))
    return(xmlXPathNodeSetCreate(NULL));
    xmlXPathNodeSetSort(nodes1);
    xmlXPathNodeSetSort(nodes2);
    return(xmlXPathNodeLeadingSorted(nodes1,
                     xmlXPathNodeSetItem(nodes2, 1)));
}

xmlNodeSetPtr
xmlXPathNodeTrailingSorted (xmlNodeSetPtr nodes, xmlNodePtr node) {
    int i, l;
    xmlNodePtr cur;
    xmlNodeSetPtr ret;

    if (node == NULL)
    return(nodes);

    ret = xmlXPathNodeSetCreate(NULL);
    if (ret == NULL)
        return(ret);
    if (xmlXPathNodeSetIsEmpty(nodes) ||
    (!xmlXPathNodeSetContains(nodes, node)))
    return(ret);

    l = xmlXPathNodeSetGetLength(nodes);
    for (i = l - 1; i >= 0; i--) {
    cur = xmlXPathNodeSetItem(nodes, i);
    if (cur == node)
        break;
        /* TODO: Propagate memory error. */
    if (xmlXPathNodeSetAddUnique(ret, cur) < 0)
        break;
    }
    xmlXPathNodeSetSort(ret);   /* bug 413451 */
    return(ret);
}

xmlNodeSetPtr
xmlXPathNodeTrailing (xmlNodeSetPtr nodes, xmlNodePtr node) {
    xmlXPathNodeSetSort(nodes);
    return(xmlXPathNodeTrailingSorted(nodes, node));
}

xmlNodeSetPtr
xmlXPathTrailingSorted (xmlNodeSetPtr nodes1, xmlNodeSetPtr nodes2) {
    if (xmlXPathNodeSetIsEmpty(nodes2))
    return(nodes1);
    return(xmlXPathNodeTrailingSorted(nodes1,
                      xmlXPathNodeSetItem(nodes2, 0)));
}

xmlNodeSetPtr
xmlXPathTrailing (xmlNodeSetPtr nodes1, xmlNodeSetPtr nodes2) {
    if (xmlXPathNodeSetIsEmpty(nodes2))
    return(nodes1);
    if (xmlXPathNodeSetIsEmpty(nodes1))
    return(xmlXPathNodeSetCreate(NULL));
    xmlXPathNodeSetSort(nodes1);
    xmlXPathNodeSetSort(nodes2);
    return(xmlXPathNodeTrailingSorted(nodes1,
                      xmlXPathNodeSetItem(nodes2, 0)));
}

/************************************************************************
 *                                  *
 *      Routines to handle extra functions          *
 *                                  *
 ************************************************************************/

int
xmlXPathRegisterFunc(xmlXPathContextPtr ctxt, const xmlChar *name,
             xmlXPathFunction f) {
    return(xmlXPathRegisterFuncNS(ctxt, name, NULL, f));
}

int
xmlXPathRegisterFuncNS(xmlXPathContextPtr ctxt, const xmlChar *name,
               const xmlChar *ns_uri, xmlXPathFunction f) {
    if (ctxt == NULL)
    return(-1);
    if (name == NULL)
    return(-1);

    if (ctxt->funcHash == NULL)
    ctxt->funcHash = xmlHashCreate(0);
    if (ctxt->funcHash == NULL)
    return(-1);
    if (f == NULL)
        return(xmlHashRemoveEntry2(ctxt->funcHash, name, ns_uri, NULL));
XML_IGNORE_PEDANTIC_WARNINGS
    return(xmlHashAddEntry2(ctxt->funcHash, name, ns_uri, (void *) f));
XML_POP_WARNINGS
}

void
xmlXPathRegisterFuncLookup (xmlXPathContextPtr ctxt,
                xmlXPathFuncLookupFunc f,
                void *funcCtxt) {
    if (ctxt == NULL)
    return;
    ctxt->funcLookupFunc = f;
    ctxt->funcLookupData = funcCtxt;
}

xmlXPathFunction
xmlXPathFunctionLookup(xmlXPathContextPtr ctxt, const xmlChar *name) {
    if (ctxt == NULL)
    return (NULL);

    if (ctxt->funcLookupFunc != NULL) {
    xmlXPathFunction ret;
    xmlXPathFuncLookupFunc f;

    f = ctxt->funcLookupFunc;
    ret = f(ctxt->funcLookupData, name, NULL);
    if (ret != NULL)
        return(ret);
    }
    return(xmlXPathFunctionLookupNS(ctxt, name, NULL));
}

xmlXPathFunction
xmlXPathFunctionLookupNS(xmlXPathContextPtr ctxt, const xmlChar *name,
             const xmlChar *ns_uri) {
    xmlXPathFunction ret;

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

    if (ctxt->funcLookupFunc != NULL) {
    xmlXPathFuncLookupFunc f;

    f = ctxt->funcLookupFunc;
    ret = f(ctxt->funcLookupData, name, ns_uri);
    if (ret != NULL)
        return(ret);
    }

    if (ctxt->funcHash == NULL)
    return(NULL);

XML_IGNORE_PEDANTIC_WARNINGS
    ret = (xmlXPathFunction) xmlHashLookup2(ctxt->funcHash, name, ns_uri);
XML_POP_WARNINGS
    return(ret);
}

void
xmlXPathRegisteredFuncsCleanup(xmlXPathContextPtr ctxt) {
    if (ctxt == NULL)
    return;

    xmlHashFree(ctxt->funcHash, NULL);
    ctxt->funcHash = NULL;
}

/************************************************************************
 *                                  *
 *          Routines to handle Variables            *
 *                                  *
 ************************************************************************/

int
xmlXPathRegisterVariable(xmlXPathContextPtr ctxt, const xmlChar *name,
             xmlXPathObjectPtr value) {
    return(xmlXPathRegisterVariableNS(ctxt, name, NULL, value));
}

int
xmlXPathRegisterVariableNS(xmlXPathContextPtr ctxt, const xmlChar *name,
               const xmlChar *ns_uri,
               xmlXPathObjectPtr value) {
    if (ctxt == NULL)
    return(-1);
    if (name == NULL)
    return(-1);

    if (ctxt->varHash == NULL)
    ctxt->varHash = xmlHashCreate(0);
    if (ctxt->varHash == NULL)
    return(-1);
    if (value == NULL)
        return(xmlHashRemoveEntry2(ctxt->varHash, name, ns_uri,
                               xmlXPathFreeObjectEntry));
    return(xmlHashUpdateEntry2(ctxt->varHash, name, ns_uri,
                   (void *) value, xmlXPathFreeObjectEntry));
}

void
xmlXPathRegisterVariableLookup(xmlXPathContextPtr ctxt,
     xmlXPathVariableLookupFunc f, void *data) {
    if (ctxt == NULL)
    return;
    ctxt->varLookupFunc = f;
    ctxt->varLookupData = data;
}

xmlXPathObjectPtr
xmlXPathVariableLookup(xmlXPathContextPtr ctxt, const xmlChar *name) {
    if (ctxt == NULL)
    return(NULL);

    if (ctxt->varLookupFunc != NULL) {
    xmlXPathObjectPtr ret;

    ret = ((xmlXPathVariableLookupFunc)ctxt->varLookupFunc)
            (ctxt->varLookupData, name, NULL);
    return(ret);
    }
    return(xmlXPathVariableLookupNS(ctxt, name, NULL));
}

xmlXPathObjectPtr
xmlXPathVariableLookupNS(xmlXPathContextPtr ctxt, const xmlChar *name,
             const xmlChar *ns_uri) {
    if (ctxt == NULL)
    return(NULL);

    if (ctxt->varLookupFunc != NULL) {
    xmlXPathObjectPtr ret;

    ret = ((xmlXPathVariableLookupFunc)ctxt->varLookupFunc)
            (ctxt->varLookupData, name, ns_uri);
    if (ret != NULL) return(ret);
    }

    if (ctxt->varHash == NULL)
    return(NULL);
    if (name == NULL)
    return(NULL);

    return(xmlXPathCacheObjectCopy(ctxt, (xmlXPathObjectPtr)
        xmlHashLookup2(ctxt->varHash, name, ns_uri)));
}

void
xmlXPathRegisteredVariablesCleanup(xmlXPathContextPtr ctxt) {
    if (ctxt == NULL)
    return;

    xmlHashFree(ctxt->varHash, xmlXPathFreeObjectEntry);
    ctxt->varHash = NULL;
}

int
xmlXPathRegisterNs(xmlXPathContextPtr ctxt, const xmlChar *prefix,
               const xmlChar *ns_uri) {
    if (ctxt == NULL)
    return(-1);
    if (prefix == NULL)
    return(-1);
    if (prefix[0] == 0)
    return(-1);

    if (ctxt->nsHash == NULL)
    ctxt->nsHash = xmlHashCreate(10);
    if (ctxt->nsHash == NULL)
    return(-1);
    if (ns_uri == NULL)
        return(xmlHashRemoveEntry(ctxt->nsHash, prefix,
                              xmlHashDefaultDeallocator));
    return(xmlHashUpdateEntry(ctxt->nsHash, prefix, (void *) xmlStrdup(ns_uri),
                  xmlHashDefaultDeallocator));
}

const xmlChar *
xmlXPathNsLookup(xmlXPathContextPtr ctxt, const xmlChar *prefix) {
    if (ctxt == NULL)
    return(NULL);
    if (prefix == NULL)
    return(NULL);

#ifdef XML_XML_NAMESPACE
    if (xmlStrEqual(prefix, (const xmlChar *) "xml"))
    return(XML_XML_NAMESPACE);
#endif

    if (ctxt->namespaces != NULL) {
    int i;

    for (i = 0;i < ctxt->nsNr;i++) {
        if ((ctxt->namespaces[i] != NULL) &&
        (xmlStrEqual(ctxt->namespaces[i]->prefix, prefix)))
        return(ctxt->namespaces[i]->href);
    }
    }

    return((const xmlChar *) xmlHashLookup(ctxt->nsHash, prefix));
}

void
xmlXPathRegisteredNsCleanup(xmlXPathContextPtr ctxt) {
    if (ctxt == NULL)
    return;

    xmlHashFree(ctxt->nsHash, xmlHashDefaultDeallocator);
    ctxt->nsHash = NULL;
}

/************************************************************************
 *                                  *
 *          Routines to handle Values           *
 *                                  *
 ************************************************************************/

/* Allocations are terrible, one needs to optimize all this !!! */

xmlXPathObjectPtr
xmlXPathNewFloat(double val) {
    xmlXPathObjectPtr ret;

    ret = (xmlXPathObjectPtr) xmlMalloc(sizeof(xmlXPathObject));
    if (ret == NULL) {
        xmlXPathErrMemory(NULL, "creating float object\n");
    return(NULL);
    }
    memset(ret, 0 , (size_t) sizeof(xmlXPathObject));
    ret->type = XPATH_NUMBER;
    ret->floatval = val;
#ifdef XP_DEBUG_OBJ_USAGE
    xmlXPathDebugObjUsageRequested(NULL, XPATH_NUMBER);
#endif
    return(ret);
}

xmlXPathObjectPtr
xmlXPathNewBoolean(int val) {
    xmlXPathObjectPtr ret;

    ret = (xmlXPathObjectPtr) xmlMalloc(sizeof(xmlXPathObject));
    if (ret == NULL) {
        xmlXPathErrMemory(NULL, "creating boolean object\n");
    return(NULL);
    }
    memset(ret, 0 , (size_t) sizeof(xmlXPathObject));
    ret->type = XPATH_BOOLEAN;
    ret->boolval = (val != 0);
#ifdef XP_DEBUG_OBJ_USAGE
    xmlXPathDebugObjUsageRequested(NULL, XPATH_BOOLEAN);
#endif
    return(ret);
}

xmlXPathObjectPtr
xmlXPathNewString(const xmlChar *val) {
    xmlXPathObjectPtr ret;

    ret = (xmlXPathObjectPtr) xmlMalloc(sizeof(xmlXPathObject));
    if (ret == NULL) {
        xmlXPathErrMemory(NULL, "creating string object\n");
    return(NULL);
    }
    memset(ret, 0 , (size_t) sizeof(xmlXPathObject));
    ret->type = XPATH_STRING;
    if (val != NULL)
    ret->stringval = xmlStrdup(val);
    else
    ret->stringval = xmlStrdup((const xmlChar *)"");
#ifdef XP_DEBUG_OBJ_USAGE
    xmlXPathDebugObjUsageRequested(NULL, XPATH_STRING);
#endif
    return(ret);
}

xmlXPathObjectPtr
xmlXPathWrapString (xmlChar *val) {
    xmlXPathObjectPtr ret;

    ret = (xmlXPathObjectPtr) xmlMalloc(sizeof(xmlXPathObject));
    if (ret == NULL) {
        xmlXPathErrMemory(NULL, "creating string object\n");
    return(NULL);
    }
    memset(ret, 0 , (size_t) sizeof(xmlXPathObject));
    ret->type = XPATH_STRING;
    ret->stringval = val;
#ifdef XP_DEBUG_OBJ_USAGE
    xmlXPathDebugObjUsageRequested(NULL, XPATH_STRING);
#endif
    return(ret);
}

xmlXPathObjectPtr
xmlXPathNewCString(const char *val) {
    xmlXPathObjectPtr ret;

    ret = (xmlXPathObjectPtr) xmlMalloc(sizeof(xmlXPathObject));
    if (ret == NULL) {
        xmlXPathErrMemory(NULL, "creating string object\n");
    return(NULL);
    }
    memset(ret, 0 , (size_t) sizeof(xmlXPathObject));
    ret->type = XPATH_STRING;
    ret->stringval = xmlStrdup(BAD_CAST val);
#ifdef XP_DEBUG_OBJ_USAGE
    xmlXPathDebugObjUsageRequested(NULL, XPATH_STRING);
#endif
    return(ret);
}

xmlXPathObjectPtr
xmlXPathWrapCString (char * val) {
    return(xmlXPathWrapString((xmlChar *)(val)));
}

xmlXPathObjectPtr
xmlXPathWrapExternal (void *val) {
    xmlXPathObjectPtr ret;

    ret = (xmlXPathObjectPtr) xmlMalloc(sizeof(xmlXPathObject));
    if (ret == NULL) {
        xmlXPathErrMemory(NULL, "creating user object\n");
    return(NULL);
    }
    memset(ret, 0 , (size_t) sizeof(xmlXPathObject));
    ret->type = XPATH_USERS;
    ret->user = val;
#ifdef XP_DEBUG_OBJ_USAGE
    xmlXPathDebugObjUsageRequested(NULL, XPATH_USERS);
#endif
    return(ret);
}

xmlXPathObjectPtr
xmlXPathObjectCopy(xmlXPathObjectPtr val) {
    xmlXPathObjectPtr ret;

    if (val == NULL)
    return(NULL);

    ret = (xmlXPathObjectPtr) xmlMalloc(sizeof(xmlXPathObject));
    if (ret == NULL) {
        xmlXPathErrMemory(NULL, "copying object\n");
    return(NULL);
    }
    memcpy(ret, val , (size_t) sizeof(xmlXPathObject));
#ifdef XP_DEBUG_OBJ_USAGE
    xmlXPathDebugObjUsageRequested(NULL, val->type);
#endif
    switch (val->type) {
    case XPATH_BOOLEAN:
    case XPATH_NUMBER:
    case XPATH_POINT:
    case XPATH_RANGE:
        break;
    case XPATH_STRING:
        ret->stringval = xmlStrdup(val->stringval);
        break;
    case XPATH_XSLT_TREE:
#if 0
/*
  Removed 11 July 2004 - the current handling of xslt tmpRVT nodes means that
  this previous handling is no longer correct, and can cause some serious
  problems (ref. bug 145547)
*/
        if ((val->nodesetval != NULL) &&
        (val->nodesetval->nodeTab != NULL)) {
        xmlNodePtr cur, tmp;
        xmlDocPtr top;

        ret->boolval = 1;
        top =  xmlNewDoc(NULL);
        top->name = (char *)
            xmlStrdup(val->nodesetval->nodeTab[0]->name);
        ret->user = top;
        if (top != NULL) {
            top->doc = top;
            cur = val->nodesetval->nodeTab[0]->children;
            while (cur != NULL) {
            tmp = xmlDocCopyNode(cur, top, 1);
            xmlAddChild((xmlNodePtr) top, tmp);
            cur = cur->next;
            }
        }

        ret->nodesetval = xmlXPathNodeSetCreate((xmlNodePtr) top);
        } else
        ret->nodesetval = xmlXPathNodeSetCreate(NULL);
        /* Deallocate the copied tree value */
        break;
#endif
    case XPATH_NODESET:
            /* TODO: Check memory error. */
        ret->nodesetval = xmlXPathNodeSetMerge(NULL, val->nodesetval);
        /* Do not deallocate the copied tree value */
        ret->boolval = 0;
        break;
    case XPATH_LOCATIONSET:
#ifdef LIBXML_XPTR_ENABLED
    {
        xmlLocationSetPtr loc = val->user;
        ret->user = (void *) xmlXPtrLocationSetMerge(NULL, loc);
        break;
    }
#endif
        case XPATH_USERS:
        ret->user = val->user;
        break;
        case XPATH_UNDEFINED:
        xmlGenericError(xmlGenericErrorContext,
            "xmlXPathObjectCopy: unsupported type %d\n",
            val->type);
        break;
    }
    return(ret);
}

void
xmlXPathFreeObject(xmlXPathObjectPtr obj) {
    if (obj == NULL) return;
    if ((obj->type == XPATH_NODESET) || (obj->type == XPATH_XSLT_TREE)) {
    if (obj->boolval) {
#if 0
        if (obj->user != NULL) {
                xmlXPathFreeNodeSet(obj->nodesetval);
        xmlFreeNodeList((xmlNodePtr) obj->user);
        } else
#endif
        obj->type = XPATH_XSLT_TREE; /* TODO: Just for debugging. */
        if (obj->nodesetval != NULL)
        xmlXPathFreeValueTree(obj->nodesetval);
    } else {
        if (obj->nodesetval != NULL)
        xmlXPathFreeNodeSet(obj->nodesetval);
    }
#ifdef LIBXML_XPTR_ENABLED
    } else if (obj->type == XPATH_LOCATIONSET) {
    if (obj->user != NULL)
        xmlXPtrFreeLocationSet(obj->user);
#endif
    } else if (obj->type == XPATH_STRING) {
    if (obj->stringval != NULL)
        xmlFree(obj->stringval);
    }
#ifdef XP_DEBUG_OBJ_USAGE
    xmlXPathDebugObjUsageReleased(NULL, obj->type);
#endif
    xmlFree(obj);
}

static void
xmlXPathFreeObjectEntry(void *obj, const xmlChar *name ATTRIBUTE_UNUSED) {
    xmlXPathFreeObject((xmlXPathObjectPtr) obj);
}

static void
xmlXPathReleaseObject(xmlXPathContextPtr ctxt, xmlXPathObjectPtr obj)
{
#define XP_CACHE_ADD(sl, o) if (sl == NULL) { \
    sl = xmlPointerListCreate(10); if (sl == NULL) goto free_obj; } \
    if (xmlPointerListAddSize(sl, obj, 0) == -1) goto free_obj;

#define XP_CACHE_WANTS(sl, n) ((sl == NULL) || ((sl)->number < n))

    if (obj == NULL)
    return;
    if ((ctxt == NULL) || (ctxt->cache == NULL)) {
     xmlXPathFreeObject(obj);
    } else {
    xmlXPathContextCachePtr cache =
        (xmlXPathContextCachePtr) ctxt->cache;

    switch (obj->type) {
        case XPATH_NODESET:
        case XPATH_XSLT_TREE:
        if (obj->nodesetval != NULL) {
            if (obj->boolval) {
            /*
            * It looks like the @boolval is used for
            * evaluation if this an XSLT Result Tree Fragment.
            * TODO: Check if this assumption is correct.
            */
            obj->type = XPATH_XSLT_TREE; /* just for debugging */
            xmlXPathFreeValueTree(obj->nodesetval);
            obj->nodesetval = NULL;
            } else if ((obj->nodesetval->nodeMax <= 40) &&
            (XP_CACHE_WANTS(cache->nodesetObjs,
                    cache->maxNodeset)))
            {
            XP_CACHE_ADD(cache->nodesetObjs, obj);
            goto obj_cached;
            } else {
            xmlXPathFreeNodeSet(obj->nodesetval);
            obj->nodesetval = NULL;
            }
        }
        break;
        case XPATH_STRING:
        if (obj->stringval != NULL)
            xmlFree(obj->stringval);

        if (XP_CACHE_WANTS(cache->stringObjs, cache->maxString)) {
            XP_CACHE_ADD(cache->stringObjs, obj);
            goto obj_cached;
        }
        break;
        case XPATH_BOOLEAN:
        if (XP_CACHE_WANTS(cache->booleanObjs, cache->maxBoolean)) {
            XP_CACHE_ADD(cache->booleanObjs, obj);
            goto obj_cached;
        }
        break;
        case XPATH_NUMBER:
        if (XP_CACHE_WANTS(cache->numberObjs, cache->maxNumber)) {
            XP_CACHE_ADD(cache->numberObjs, obj);
            goto obj_cached;
        }
        break;
#ifdef LIBXML_XPTR_ENABLED
        case XPATH_LOCATIONSET:
        if (obj->user != NULL) {
            xmlXPtrFreeLocationSet(obj->user);
        }
        goto free_obj;
#endif
        default:
        goto free_obj;
    }

    /*
    * Fallback to adding to the misc-objects slot.
    */
    if (XP_CACHE_WANTS(cache->miscObjs, cache->maxMisc)) {
        XP_CACHE_ADD(cache->miscObjs, obj);
    } else
        goto free_obj;

obj_cached:

#ifdef XP_DEBUG_OBJ_USAGE
    xmlXPathDebugObjUsageReleased(ctxt, obj->type);
#endif

    if (obj->nodesetval != NULL) {
        xmlNodeSetPtr tmpset = obj->nodesetval;

        /*
        * TODO: Due to those nasty ns-nodes, we need to traverse
        *  the list and free the ns-nodes.
        * URGENT TODO: Check if it's actually slowing things down.
        *  Maybe we shouldn't try to preserve the list.
        */
        if (tmpset->nodeNr > 1) {
        int i;
        xmlNodePtr node;

        for (i = 0; i < tmpset->nodeNr; i++) {
            node = tmpset->nodeTab[i];
            if ((node != NULL) &&
            (node->type == XML_NAMESPACE_DECL))
            {
            xmlXPathNodeSetFreeNs((xmlNsPtr) node);
            }
        }
        } else if (tmpset->nodeNr == 1) {
        if ((tmpset->nodeTab[0] != NULL) &&
            (tmpset->nodeTab[0]->type == XML_NAMESPACE_DECL))
            xmlXPathNodeSetFreeNs((xmlNsPtr) tmpset->nodeTab[0]);
        }
        tmpset->nodeNr = 0;
        memset(obj, 0, sizeof(xmlXPathObject));
        obj->nodesetval = tmpset;
    } else
        memset(obj, 0, sizeof(xmlXPathObject));

    return;

free_obj:
    /*
    * Cache is full; free the object.
    */
    if (obj->nodesetval != NULL)
        xmlXPathFreeNodeSet(obj->nodesetval);
#ifdef XP_DEBUG_OBJ_USAGE
    xmlXPathDebugObjUsageReleased(NULL, obj->type);
#endif
    xmlFree(obj);
    }
    return;
}


/************************************************************************
 *                                  *
 *          Type Casting Routines               *
 *                                  *
 ************************************************************************/

xmlChar *
xmlXPathCastBooleanToString (int val) {
    xmlChar *ret;
    if (val)
    ret = xmlStrdup((const xmlChar *) "true");
    else
    ret = xmlStrdup((const xmlChar *) "false");
    return(ret);
}

xmlChar *
xmlXPathCastNumberToString (double val) {
    xmlChar *ret;
    switch (xmlXPathIsInf(val)) {
    case 1:
    ret = xmlStrdup((const xmlChar *) "Infinity");
    break;
    case -1:
    ret = xmlStrdup((const xmlChar *) "-Infinity");
    break;
    default:
    if (xmlXPathIsNaN(val)) {
        ret = xmlStrdup((const xmlChar *) "NaN");
    } else if (val == 0) {
            /* Omit sign for negative zero. */
        ret = xmlStrdup((const xmlChar *) "0");
    } else {
        /* could be improved */
        char buf[100];
        xmlXPathFormatNumber(val, buf, 99);
        buf[99] = 0;
        ret = xmlStrdup((const xmlChar *) buf);
    }
    }
    return(ret);
}

xmlChar *
xmlXPathCastNodeToString (xmlNodePtr node) {
xmlChar *ret;
    if ((ret = xmlNodeGetContent(node)) == NULL)
    ret = xmlStrdup((const xmlChar *) "");
    return(ret);
}

xmlChar *
xmlXPathCastNodeSetToString (xmlNodeSetPtr ns) {
    if ((ns == NULL) || (ns->nodeNr == 0) || (ns->nodeTab == NULL))
    return(xmlStrdup((const xmlChar *) ""));

    if (ns->nodeNr > 1)
    xmlXPathNodeSetSort(ns);
    return(xmlXPathCastNodeToString(ns->nodeTab[0]));
}

xmlChar *
xmlXPathCastToString(xmlXPathObjectPtr val) {
    xmlChar *ret = NULL;

    if (val == NULL)
    return(xmlStrdup((const xmlChar *) ""));
    switch (val->type) {
    case XPATH_UNDEFINED:
#ifdef DEBUG_EXPR
        xmlGenericError(xmlGenericErrorContext, "String: undefined\n");
#endif
        ret = xmlStrdup((const xmlChar *) "");
        break;
        case XPATH_NODESET:
        case XPATH_XSLT_TREE:
        ret = xmlXPathCastNodeSetToString(val->nodesetval);
        break;
    case XPATH_STRING:
        return(xmlStrdup(val->stringval));
        case XPATH_BOOLEAN:
        ret = xmlXPathCastBooleanToString(val->boolval);
        break;
    case XPATH_NUMBER: {
        ret = xmlXPathCastNumberToString(val->floatval);
        break;
    }
    case XPATH_USERS:
    case XPATH_POINT:
    case XPATH_RANGE:
    case XPATH_LOCATIONSET:
        TODO
        ret = xmlStrdup((const xmlChar *) "");
        break;
    }
    return(ret);
}

xmlXPathObjectPtr
xmlXPathConvertString(xmlXPathObjectPtr val) {
    xmlChar *res = NULL;

    if (val == NULL)
    return(xmlXPathNewCString(""));

    switch (val->type) {
    case XPATH_UNDEFINED:
#ifdef DEBUG_EXPR
    xmlGenericError(xmlGenericErrorContext, "STRING: undefined\n");
#endif
    break;
    case XPATH_NODESET:
    case XPATH_XSLT_TREE:
    res = xmlXPathCastNodeSetToString(val->nodesetval);
    break;
    case XPATH_STRING:
    return(val);
    case XPATH_BOOLEAN:
    res = xmlXPathCastBooleanToString(val->boolval);
    break;
    case XPATH_NUMBER:
    res = xmlXPathCastNumberToString(val->floatval);
    break;
    case XPATH_USERS:
    case XPATH_POINT:
    case XPATH_RANGE:
    case XPATH_LOCATIONSET:
    TODO;
    break;
    }
    xmlXPathFreeObject(val);
    if (res == NULL)
    return(xmlXPathNewCString(""));
    return(xmlXPathWrapString(res));
}

double
xmlXPathCastBooleanToNumber(int val) {
    if (val)
    return(1.0);
    return(0.0);
}

double
xmlXPathCastStringToNumber(const xmlChar * val) {
    return(xmlXPathStringEvalNumber(val));
}

double
xmlXPathCastNodeToNumber (xmlNodePtr node) {
    xmlChar *strval;
    double ret;

    if (node == NULL)
    return(xmlXPathNAN);
    strval = xmlXPathCastNodeToString(node);
    if (strval == NULL)
    return(xmlXPathNAN);
    ret = xmlXPathCastStringToNumber(strval);
    xmlFree(strval);

    return(ret);
}

double
xmlXPathCastNodeSetToNumber (xmlNodeSetPtr ns) {
    xmlChar *str;
    double ret;

    if (ns == NULL)
    return(xmlXPathNAN);
    str = xmlXPathCastNodeSetToString(ns);
    ret = xmlXPathCastStringToNumber(str);
    xmlFree(str);
    return(ret);
}

double
xmlXPathCastToNumber(xmlXPathObjectPtr val) {
    double ret = 0.0;

    if (val == NULL)
    return(xmlXPathNAN);
    switch (val->type) {
    case XPATH_UNDEFINED:
#ifdef DEBUG_EXPR
    xmlGenericError(xmlGenericErrorContext, "NUMBER: undefined\n");
#endif
    ret = xmlXPathNAN;
    break;
    case XPATH_NODESET:
    case XPATH_XSLT_TREE:
    ret = xmlXPathCastNodeSetToNumber(val->nodesetval);
    break;
    case XPATH_STRING:
    ret = xmlXPathCastStringToNumber(val->stringval);
    break;
    case XPATH_NUMBER:
    ret = val->floatval;
    break;
    case XPATH_BOOLEAN:
    ret = xmlXPathCastBooleanToNumber(val->boolval);
    break;
    case XPATH_USERS:
    case XPATH_POINT:
    case XPATH_RANGE:
    case XPATH_LOCATIONSET:
    TODO;
    ret = xmlXPathNAN;
    break;
    }
    return(ret);
}

xmlXPathObjectPtr
xmlXPathConvertNumber(xmlXPathObjectPtr val) {
    xmlXPathObjectPtr ret;

    if (val == NULL)
    return(xmlXPathNewFloat(0.0));
    if (val->type == XPATH_NUMBER)
    return(val);
    ret = xmlXPathNewFloat(xmlXPathCastToNumber(val));
    xmlXPathFreeObject(val);
    return(ret);
}

int
xmlXPathCastNumberToBoolean (double val) {
     if (xmlXPathIsNaN(val) || (val == 0.0))
     return(0);
     return(1);
}

int
xmlXPathCastStringToBoolean (const xmlChar *val) {
    if ((val == NULL) || (xmlStrlen(val) == 0))
    return(0);
    return(1);
}

int
xmlXPathCastNodeSetToBoolean (xmlNodeSetPtr ns) {
    if ((ns == NULL) || (ns->nodeNr == 0))
    return(0);
    return(1);
}

int
xmlXPathCastToBoolean (xmlXPathObjectPtr val) {
    int ret = 0;

    if (val == NULL)
    return(0);
    switch (val->type) {
    case XPATH_UNDEFINED:
#ifdef DEBUG_EXPR
    xmlGenericError(xmlGenericErrorContext, "BOOLEAN: undefined\n");
#endif
    ret = 0;
    break;
    case XPATH_NODESET:
    case XPATH_XSLT_TREE:
    ret = xmlXPathCastNodeSetToBoolean(val->nodesetval);
    break;
    case XPATH_STRING:
    ret = xmlXPathCastStringToBoolean(val->stringval);
    break;
    case XPATH_NUMBER:
    ret = xmlXPathCastNumberToBoolean(val->floatval);
    break;
    case XPATH_BOOLEAN:
    ret = val->boolval;
    break;
    case XPATH_USERS:
    case XPATH_POINT:
    case XPATH_RANGE:
    case XPATH_LOCATIONSET:
    TODO;
    ret = 0;
    break;
    }
    return(ret);
}


xmlXPathObjectPtr
xmlXPathConvertBoolean(xmlXPathObjectPtr val) {
    xmlXPathObjectPtr ret;

    if (val == NULL)
    return(xmlXPathNewBoolean(0));
    if (val->type == XPATH_BOOLEAN)
    return(val);
    ret = xmlXPathNewBoolean(xmlXPathCastToBoolean(val));
    xmlXPathFreeObject(val);
    return(ret);
}

/************************************************************************
 *                                  *
 *      Routines to handle XPath contexts           *
 *                                  *
 ************************************************************************/

xmlXPathContextPtr
xmlXPathNewContext(xmlDocPtr doc) {
    xmlXPathContextPtr ret;

    ret = (xmlXPathContextPtr) xmlMalloc(sizeof(xmlXPathContext));
    if (ret == NULL) {
        xmlXPathErrMemory(NULL, "creating context\n");
    return(NULL);
    }
    memset(ret, 0 , (size_t) sizeof(xmlXPathContext));
    ret->doc = doc;
    ret->node = NULL;

    ret->varHash = NULL;

    ret->nb_types = 0;
    ret->max_types = 0;
    ret->types = NULL;

    ret->funcHash = xmlHashCreate(0);

    ret->nb_axis = 0;
    ret->max_axis = 0;
    ret->axis = NULL;

    ret->nsHash = NULL;
    ret->user = NULL;

    ret->contextSize = -1;
    ret->proximityPosition = -1;

#ifdef XP_DEFAULT_CACHE_ON
    if (xmlXPathContextSetCache(ret, 1, -1, 0) == -1) {
    xmlXPathFreeContext(ret);
    return(NULL);
    }
#endif

    xmlXPathRegisterAllFunctions(ret);

    return(ret);
}

void
xmlXPathFreeContext(xmlXPathContextPtr ctxt) {
    if (ctxt == NULL) return;

    if (ctxt->cache != NULL)
    xmlXPathFreeCache((xmlXPathContextCachePtr) ctxt->cache);
    xmlXPathRegisteredNsCleanup(ctxt);
    xmlXPathRegisteredFuncsCleanup(ctxt);
    xmlXPathRegisteredVariablesCleanup(ctxt);
    xmlResetError(&ctxt->lastError);
    xmlFree(ctxt);
}

/************************************************************************
 *                                  *
 *      Routines to handle XPath parser contexts        *
 *                                  *
 ************************************************************************/

#define CHECK_CTXT(ctxt)                        \
    if (ctxt == NULL) {                     \
    __xmlRaiseError(NULL, NULL, NULL,               \
        NULL, NULL, XML_FROM_XPATH,             \
        XML_ERR_INTERNAL_ERROR, XML_ERR_FATAL,          \
        __FILE__, __LINE__,                 \
        NULL, NULL, NULL, 0, 0,                 \
        "NULL context pointer\n");              \
    return(NULL);                           \
    }                                   \

#define CHECK_CTXT_NEG(ctxt)                        \
    if (ctxt == NULL) {                     \
    __xmlRaiseError(NULL, NULL, NULL,               \
        NULL, NULL, XML_FROM_XPATH,             \
        XML_ERR_INTERNAL_ERROR, XML_ERR_FATAL,          \
        __FILE__, __LINE__,                 \
        NULL, NULL, NULL, 0, 0,                 \
        "NULL context pointer\n");              \
    return(-1);                         \
    }                                   \


#define CHECK_CONTEXT(ctxt)                     \
    if ((ctxt == NULL) || (ctxt->doc == NULL) ||            \
        (ctxt->doc->children == NULL)) {                \
    xmlXPatherror(ctxt, __FILE__, __LINE__, XPATH_INVALID_CTXT);    \
    return(NULL);                           \
    }


xmlXPathParserContextPtr
xmlXPathNewParserContext(const xmlChar *str, xmlXPathContextPtr ctxt) {
    xmlXPathParserContextPtr ret;

    ret = (xmlXPathParserContextPtr) xmlMalloc(sizeof(xmlXPathParserContext));
    if (ret == NULL) {
        xmlXPathErrMemory(ctxt, "creating parser context\n");
    return(NULL);
    }
    memset(ret, 0 , (size_t) sizeof(xmlXPathParserContext));
    ret->cur = ret->base = str;
    ret->context = ctxt;

    ret->comp = xmlXPathNewCompExpr();
    if (ret->comp == NULL) {
    xmlFree(ret->valueTab);
    xmlFree(ret);
    return(NULL);
    }
    if ((ctxt != NULL) && (ctxt->dict != NULL)) {
        ret->comp->dict = ctxt->dict;
    xmlDictReference(ret->comp->dict);
    }

    return(ret);
}

static xmlXPathParserContextPtr
xmlXPathCompParserContext(xmlXPathCompExprPtr comp, xmlXPathContextPtr ctxt) {
    xmlXPathParserContextPtr ret;

    ret = (xmlXPathParserContextPtr) xmlMalloc(sizeof(xmlXPathParserContext));
    if (ret == NULL) {
        xmlXPathErrMemory(ctxt, "creating evaluation context\n");
    return(NULL);
    }
    memset(ret, 0 , (size_t) sizeof(xmlXPathParserContext));

    /* Allocate the value stack */
    ret->valueTab = (xmlXPathObjectPtr *)
                     xmlMalloc(10 * sizeof(xmlXPathObjectPtr));
    if (ret->valueTab == NULL) {
    xmlFree(ret);
    xmlXPathErrMemory(ctxt, "creating evaluation context\n");
    return(NULL);
    }
    ret->valueNr = 0;
    ret->valueMax = 10;
    ret->value = NULL;
    ret->valueFrame = 0;

    ret->context = ctxt;
    ret->comp = comp;

    return(ret);
}

void
xmlXPathFreeParserContext(xmlXPathParserContextPtr ctxt) {
    int i;

    if (ctxt->valueTab != NULL) {
        for (i = 0; i < ctxt->valueNr; i++) {
            if (ctxt->context)
                xmlXPathReleaseObject(ctxt->context, ctxt->valueTab[i]);
            else
                xmlXPathFreeObject(ctxt->valueTab[i]);
        }
        xmlFree(ctxt->valueTab);
    }
    if (ctxt->comp != NULL) {
#ifdef XPATH_STREAMING
    if (ctxt->comp->stream != NULL) {
        xmlFreePatternList(ctxt->comp->stream);
        ctxt->comp->stream = NULL;
    }
#endif
    xmlXPathFreeCompExpr(ctxt->comp);
    }
    xmlFree(ctxt);
}

/************************************************************************
 *                                  *
 *      The implicit core function library          *
 *                                  *
 ************************************************************************/

static unsigned int
xmlXPathNodeValHash(xmlNodePtr node) {
    int len = 2;
    const xmlChar * string = NULL;
    xmlNodePtr tmp = NULL;
    unsigned int ret = 0;

    if (node == NULL)
    return(0);

    if (node->type == XML_DOCUMENT_NODE) {
    tmp = xmlDocGetRootElement((xmlDocPtr) node);
    if (tmp == NULL)
        node = node->children;
    else
        node = tmp;

    if (node == NULL)
        return(0);
    }

    switch (node->type) {
    case XML_COMMENT_NODE:
    case XML_PI_NODE:
    case XML_CDATA_SECTION_NODE:
    case XML_TEXT_NODE:
        string = node->content;
        if (string == NULL)
        return(0);
        if (string[0] == 0)
        return(0);
        return(((unsigned int) string[0]) +
           (((unsigned int) string[1]) << 8));
    case XML_NAMESPACE_DECL:
        string = ((xmlNsPtr)node)->href;
        if (string == NULL)
        return(0);
        if (string[0] == 0)
        return(0);
        return(((unsigned int) string[0]) +
           (((unsigned int) string[1]) << 8));
    case XML_ATTRIBUTE_NODE:
        tmp = ((xmlAttrPtr) node)->children;
        break;
    case XML_ELEMENT_NODE:
        tmp = node->children;
        break;
    default:
        return(0);
    }
    while (tmp != NULL) {
    switch (tmp->type) {
        case XML_CDATA_SECTION_NODE:
        case XML_TEXT_NODE:
        string = tmp->content;
        break;
        default:
                string = NULL;
        break;
    }
    if ((string != NULL) && (string[0] != 0)) {
        if (len == 1) {
        return(ret + (((unsigned int) string[0]) << 8));
        }
        if (string[1] == 0) {
        len = 1;
        ret = (unsigned int) string[0];
        } else {
        return(((unsigned int) string[0]) +
               (((unsigned int)