pattern.c

Go to the documentation of this file.

/*
 * pattern.c: Implementation of selectors for nodes
 *
 * Reference:
 *   http://www.w3.org/TR/2001/REC-xmlschema-1-20010502/
 *   to some extent
 *   http://www.w3.org/TR/1999/REC-xml-19991116
 *
 * See Copyright for the status of this software.
 *
 * daniel@veillard.com
 */
 
/*
 * TODO:
 * - compilation flags to check for specific syntaxes
 *   using flags of xmlPatterncompile()
 * - making clear how pattern starting with / or . need to be handled,
 *   currently push(NULL, NULL) means a reset of the streaming context
 *   and indicating we are on / (the document node), probably need
 *   something similar for .
 * - get rid of the "compile" starting with lowercase
 * - DONE (2006-05-16): get rid of the Strdup/Strndup in case of dictionary
 */
 
#define IN_LIBXML
#include "libxml.h"
 
#include <string.h>
#include <libxml/xmlmemory.h>
#include <libxml/tree.h>
#include <libxml/hash.h>
#include <libxml/dict.h>
#include <libxml/xmlerror.h>
#include <libxml/parserInternals.h>
#include <libxml/pattern.h>
 
#ifdef LIBXML_PATTERN_ENABLED
 
/* #define DEBUG_STREAMING */
 
#ifdef ERROR
#undef ERROR
#endif
#define ERROR(a, b, c, d)
#define ERROR5(a, b, c, d, e)
 
#define XML_STREAM_STEP_DESC    1
#define XML_STREAM_STEP_FINAL   2
#define XML_STREAM_STEP_ROOT    4
#define XML_STREAM_STEP_ATTR    8
#define XML_STREAM_STEP_NODE    16
#define XML_STREAM_STEP_IN_SET  32
 
/*
* NOTE: Those private flags (XML_STREAM_xxx) are used
*   in _xmlStreamCtxt->flag. They extend the public
*   xmlPatternFlags, so be careful not to interfere with the
*   reserved values for xmlPatternFlags.
*/
#define XML_STREAM_FINAL_IS_ANY_NODE 1<<14
#define XML_STREAM_FROM_ROOT 1<<15
#define XML_STREAM_DESC 1<<16
 
/*
* XML_STREAM_ANY_NODE is used for comparison against
* xmlElementType enums, to indicate a node of any type.
*/
#define XML_STREAM_ANY_NODE 100
 
#define XML_PATTERN_NOTPATTERN  (XML_PATTERN_XPATH | \
                 XML_PATTERN_XSSEL | \
                 XML_PATTERN_XSFIELD)
 
#define XML_STREAM_XS_IDC(c) ((c)->flags & \
    (XML_PATTERN_XSSEL | XML_PATTERN_XSFIELD))
 
#define XML_STREAM_XS_IDC_SEL(c) ((c)->flags & XML_PATTERN_XSSEL)
 
#define XML_STREAM_XS_IDC_FIELD(c) ((c)->flags & XML_PATTERN_XSFIELD)
 
#define XML_PAT_COPY_NSNAME(c, r, nsname) \
    if ((c)->comp->dict) \
    r = (xmlChar *) xmlDictLookup((c)->comp->dict, BAD_CAST nsname, -1); \
    else r = xmlStrdup(BAD_CAST nsname);
 
#define XML_PAT_FREE_STRING(c, r) if ((c)->comp->dict == NULL) xmlFree(r);
 
typedef struct _xmlStreamStep xmlStreamStep;
typedef xmlStreamStep *xmlStreamStepPtr;
struct _xmlStreamStep {
    int flags;          /* properties of that step */
    const xmlChar *name;    /* first string value if NULL accept all */
    const xmlChar *ns;      /* second string value */
    int nodeType;       /* type of node */
};
 
typedef struct _xmlStreamComp xmlStreamComp;
typedef xmlStreamComp *xmlStreamCompPtr;
struct _xmlStreamComp {
    xmlDict *dict;      /* the dictionary if any */
    int nbStep;         /* number of steps in the automata */
    int maxStep;        /* allocated number of steps */
    xmlStreamStepPtr steps; /* the array of steps */
    int flags;
};
 
struct _xmlStreamCtxt {
    struct _xmlStreamCtxt *next;/* link to next sub pattern if | */
    xmlStreamCompPtr comp;  /* the compiled stream */
    int nbState;        /* number of states in the automata */
    int maxState;       /* allocated number of states */
    int level;          /* how deep are we ? */
    int *states;        /* the array of step indexes */
    int flags;          /* validation options */
    int blockLevel;
};
 
static void xmlFreeStreamComp(xmlStreamCompPtr comp);
 
/*
 * Types are private:
 */
 
typedef enum {
    XML_OP_END=0,
    XML_OP_ROOT,
    XML_OP_ELEM,
    XML_OP_CHILD,
    XML_OP_ATTR,
    XML_OP_PARENT,
    XML_OP_ANCESTOR,
    XML_OP_NS,
    XML_OP_ALL
} xmlPatOp;
 
 
typedef struct _xmlStepState xmlStepState;
typedef xmlStepState *xmlStepStatePtr;
struct _xmlStepState {
    int step;
    xmlNodePtr node;
};
 
typedef struct _xmlStepStates xmlStepStates;
typedef xmlStepStates *xmlStepStatesPtr;
struct _xmlStepStates {
    int nbstates;
    int maxstates;
    xmlStepStatePtr states;
};
 
typedef struct _xmlStepOp xmlStepOp;
typedef xmlStepOp *xmlStepOpPtr;
struct _xmlStepOp {
    xmlPatOp op;
    const xmlChar *value;
    const xmlChar *value2; /* The namespace name */
};
 
#define PAT_FROM_ROOT   (1<<8)
#define PAT_FROM_CUR    (1<<9)
 
struct _xmlPattern {
    void *data;     /* the associated template */
    xmlDictPtr dict;        /* the optional dictionary */
    struct _xmlPattern *next;   /* next pattern if | is used */
    const xmlChar *pattern; /* the pattern */
    int flags;          /* flags */
    int nbStep;
    int maxStep;
    xmlStepOpPtr steps;        /* ops for computation */
    xmlStreamCompPtr stream;    /* the streaming data if any */
};
 
typedef struct _xmlPatParserContext xmlPatParserContext;
typedef xmlPatParserContext *xmlPatParserContextPtr;
struct _xmlPatParserContext {
    const xmlChar *cur;         /* the current char being parsed */
    const xmlChar *base;        /* the full expression */
    int            error;       /* error code */
    xmlDictPtr     dict;        /* the dictionary if any */
    xmlPatternPtr  comp;        /* the result */
    xmlNodePtr     elem;        /* the current node if any */
    const xmlChar **namespaces;     /* the namespaces definitions */
    int   nb_namespaces;        /* the number of namespaces */
};
 
/************************************************************************
 *                                  *
 *          Type functions                  *
 *                                  *
 ************************************************************************/
 
static xmlPatternPtr
xmlNewPattern(void) {
    xmlPatternPtr cur;
 
    cur = (xmlPatternPtr) xmlMalloc(sizeof(xmlPattern));
    if (cur == NULL) {
    ERROR(NULL, NULL, NULL,
        "xmlNewPattern : malloc failed\n");
    return(NULL);
    }
    memset(cur, 0, sizeof(xmlPattern));
    cur->maxStep = 10;
    cur->steps = (xmlStepOpPtr) xmlMalloc(cur->maxStep * sizeof(xmlStepOp));
    if (cur->steps == NULL) {
        xmlFree(cur);
    ERROR(NULL, NULL, NULL,
        "xmlNewPattern : malloc failed\n");
    return(NULL);
    }
    return(cur);
}
 
void
xmlFreePattern(xmlPatternPtr comp) {
    xmlFreePatternList(comp);
}
 
static void
xmlFreePatternInternal(xmlPatternPtr comp) {
    xmlStepOpPtr op;
    int i;
 
    if (comp == NULL)
    return;
    if (comp->stream != NULL)
        xmlFreeStreamComp(comp->stream);
    if (comp->pattern != NULL)
    xmlFree((xmlChar *)comp->pattern);
    if (comp->steps != NULL) {
        if (comp->dict == NULL) {
        for (i = 0;i < comp->nbStep;i++) {
        op = &comp->steps[i];
        if (op->value != NULL)
            xmlFree((xmlChar *) op->value);
        if (op->value2 != NULL)
            xmlFree((xmlChar *) op->value2);
        }
    }
    xmlFree(comp->steps);
    }
    if (comp->dict != NULL)
        xmlDictFree(comp->dict);
 
    memset(comp, -1, sizeof(xmlPattern));
    xmlFree(comp);
}
 
void
xmlFreePatternList(xmlPatternPtr comp) {
    xmlPatternPtr cur;
 
    while (comp != NULL) {
    cur = comp;
    comp = comp->next;
    cur->next = NULL;
    xmlFreePatternInternal(cur);
    }
}
 
static xmlPatParserContextPtr
xmlNewPatParserContext(const xmlChar *pattern, xmlDictPtr dict,
                       const xmlChar **namespaces) {
    xmlPatParserContextPtr cur;
 
    if (pattern == NULL)
        return(NULL);
 
    cur = (xmlPatParserContextPtr) xmlMalloc(sizeof(xmlPatParserContext));
    if (cur == NULL) {
    ERROR(NULL, NULL, NULL,
        "xmlNewPatParserContext : malloc failed\n");
    return(NULL);
    }
    memset(cur, 0, sizeof(xmlPatParserContext));
    cur->dict = dict;
    cur->cur = pattern;
    cur->base = pattern;
    if (namespaces != NULL) {
        int i;
        for (i = 0;namespaces[2 * i] != NULL;i++)
            ;
        cur->nb_namespaces = i;
    } else {
        cur->nb_namespaces = 0;
    }
    cur->namespaces = namespaces;
    return(cur);
}
 
static void
xmlFreePatParserContext(xmlPatParserContextPtr ctxt) {
    if (ctxt == NULL)
    return;
    memset(ctxt, -1, sizeof(xmlPatParserContext));
    xmlFree(ctxt);
}
 
static int
xmlPatternAdd(xmlPatParserContextPtr ctxt ATTRIBUTE_UNUSED,
                xmlPatternPtr comp,
                xmlPatOp op, xmlChar * value, xmlChar * value2)
{
    if (comp->nbStep >= comp->maxStep) {
        xmlStepOpPtr temp;
    temp = (xmlStepOpPtr) xmlRealloc(comp->steps, comp->maxStep * 2 *
                                     sizeof(xmlStepOp));
        if (temp == NULL) {
        ERROR(ctxt, NULL, NULL,
                 "xmlPatternAdd: realloc failed\n");
        return (-1);
    }
    comp->steps = temp;
    comp->maxStep *= 2;
    }
    comp->steps[comp->nbStep].op = op;
    comp->steps[comp->nbStep].value = value;
    comp->steps[comp->nbStep].value2 = value2;
    comp->nbStep++;
    return (0);
}
 
#if 0
static void
xsltSwapTopPattern(xmlPatternPtr comp) {
    int i;
    int j = comp->nbStep - 1;
 
    if (j > 0) {
    register const xmlChar *tmp;
    register xmlPatOp op;
    i = j - 1;
    tmp = comp->steps[i].value;
    comp->steps[i].value = comp->steps[j].value;
    comp->steps[j].value = tmp;
    tmp = comp->steps[i].value2;
    comp->steps[i].value2 = comp->steps[j].value2;
    comp->steps[j].value2 = tmp;
    op = comp->steps[i].op;
    comp->steps[i].op = comp->steps[j].op;
    comp->steps[j].op = op;
    }
}
#endif
 
static int
xmlReversePattern(xmlPatternPtr comp) {
    int i, j;
 
    /*
     * remove the leading // for //a or .//a
     */
    if ((comp->nbStep > 0) && (comp->steps[0].op == XML_OP_ANCESTOR)) {
        for (i = 0, j = 1;j < comp->nbStep;i++,j++) {
        comp->steps[i].value = comp->steps[j].value;
        comp->steps[i].value2 = comp->steps[j].value2;
        comp->steps[i].op = comp->steps[j].op;
    }
    comp->nbStep--;
    }
    if (comp->nbStep >= comp->maxStep) {
        xmlStepOpPtr temp;
    temp = (xmlStepOpPtr) xmlRealloc(comp->steps, comp->maxStep * 2 *
                                     sizeof(xmlStepOp));
        if (temp == NULL) {
        ERROR(ctxt, NULL, NULL,
                 "xmlReversePattern: realloc failed\n");
        return (-1);
    }
    comp->steps = temp;
    comp->maxStep *= 2;
    }
    i = 0;
    j = comp->nbStep - 1;
    while (j > i) {
    register const xmlChar *tmp;
    register xmlPatOp op;
    tmp = comp->steps[i].value;
    comp->steps[i].value = comp->steps[j].value;
    comp->steps[j].value = tmp;
    tmp = comp->steps[i].value2;
    comp->steps[i].value2 = comp->steps[j].value2;
    comp->steps[j].value2 = tmp;
    op = comp->steps[i].op;
    comp->steps[i].op = comp->steps[j].op;
    comp->steps[j].op = op;
    j--;
    i++;
    }
    comp->steps[comp->nbStep].value = NULL;
    comp->steps[comp->nbStep].value2 = NULL;
    comp->steps[comp->nbStep++].op = XML_OP_END;
    return(0);
}
 
/************************************************************************
 *                                  *
 *      The interpreter for the precompiled patterns        *
 *                                  *
 ************************************************************************/
 
static int
xmlPatPushState(xmlStepStates *states, int step, xmlNodePtr node) {
    if ((states->states == NULL) || (states->maxstates <= 0)) {
        states->maxstates = 4;
    states->nbstates = 0;
    states->states = xmlMalloc(4 * sizeof(xmlStepState));
    }
    else if (states->maxstates <= states->nbstates) {
        xmlStepState *tmp;
 
    tmp = (xmlStepStatePtr) xmlRealloc(states->states,
                   2 * states->maxstates * sizeof(xmlStepState));
    if (tmp == NULL)
        return(-1);
    states->states = tmp;
    states->maxstates *= 2;
    }
    states->states[states->nbstates].step = step;
    states->states[states->nbstates++].node = node;
#if 0
    fprintf(stderr, "Push: %d, %s\n", step, node->name);
#endif
    return(0);
}
 
static int
xmlPatMatch(xmlPatternPtr comp, xmlNodePtr node) {
    int i;
    xmlStepOpPtr step;
    xmlStepStates states = {0, 0, NULL}; /* // may require backtrack */
 
    if ((comp == NULL) || (node == NULL)) return(-1);
    i = 0;
restart:
    for (;i < comp->nbStep;i++) {
    step = &comp->steps[i];
    switch (step->op) {
            case XML_OP_END:
        goto found;
            case XML_OP_ROOT:
        if (node->type == XML_NAMESPACE_DECL)
            goto rollback;
        node = node->parent;
        if ((node->type == XML_DOCUMENT_NODE) ||
            (node->type == XML_HTML_DOCUMENT_NODE))
            continue;
        goto rollback;
            case XML_OP_ELEM:
        if (node->type != XML_ELEMENT_NODE)
            goto rollback;
        if (step->value == NULL)
            continue;
        if (step->value[0] != node->name[0])
            goto rollback;
        if (!xmlStrEqual(step->value, node->name))
            goto rollback;
 
        /* Namespace test */
        if (node->ns == NULL) {
            if (step->value2 != NULL)
            goto rollback;
        } else if (node->ns->href != NULL) {
            if (step->value2 == NULL)
            goto rollback;
            if (!xmlStrEqual(step->value2, node->ns->href))
            goto rollback;
        }
        continue;
            case XML_OP_CHILD: {
        xmlNodePtr lst;
 
        if ((node->type != XML_ELEMENT_NODE) &&
            (node->type != XML_DOCUMENT_NODE) &&
            (node->type != XML_HTML_DOCUMENT_NODE))
            goto rollback;
 
        lst = node->children;
 
        if (step->value != NULL) {
            while (lst != NULL) {
            if ((lst->type == XML_ELEMENT_NODE) &&
                (step->value[0] == lst->name[0]) &&
                (xmlStrEqual(step->value, lst->name)))
                break;
            lst = lst->next;
            }
            if (lst != NULL)
            continue;
        }
        goto rollback;
        }
            case XML_OP_ATTR:
        if (node->type != XML_ATTRIBUTE_NODE)
            goto rollback;
        if (step->value != NULL) {
            if (step->value[0] != node->name[0])
            goto rollback;
            if (!xmlStrEqual(step->value, node->name))
            goto rollback;
        }
        /* Namespace test */
        if (node->ns == NULL) {
            if (step->value2 != NULL)
            goto rollback;
        } else if (step->value2 != NULL) {
            if (!xmlStrEqual(step->value2, node->ns->href))
            goto rollback;
        }
        continue;
            case XML_OP_PARENT:
        if ((node->type == XML_DOCUMENT_NODE) ||
            (node->type == XML_HTML_DOCUMENT_NODE) ||
            (node->type == XML_NAMESPACE_DECL))
            goto rollback;
        node = node->parent;
        if (node == NULL)
            goto rollback;
        if (step->value == NULL)
            continue;
        if (step->value[0] != node->name[0])
            goto rollback;
        if (!xmlStrEqual(step->value, node->name))
            goto rollback;
        /* Namespace test */
        if (node->ns == NULL) {
            if (step->value2 != NULL)
            goto rollback;
        } else if (node->ns->href != NULL) {
            if (step->value2 == NULL)
            goto rollback;
            if (!xmlStrEqual(step->value2, node->ns->href))
            goto rollback;
        }
        continue;
            case XML_OP_ANCESTOR:
        /* TODO: implement coalescing of ANCESTOR/NODE ops */
        if (step->value == NULL) {
            i++;
            step = &comp->steps[i];
            if (step->op == XML_OP_ROOT)
            goto found;
            if (step->op != XML_OP_ELEM)
            goto rollback;
            if (step->value == NULL)
            return(-1);
        }
        if (node == NULL)
            goto rollback;
        if ((node->type == XML_DOCUMENT_NODE) ||
            (node->type == XML_HTML_DOCUMENT_NODE) ||
            (node->type == XML_NAMESPACE_DECL))
            goto rollback;
        node = node->parent;
        while (node != NULL) {
            if ((node->type == XML_ELEMENT_NODE) &&
            (step->value[0] == node->name[0]) &&
            (xmlStrEqual(step->value, node->name))) {
            /* Namespace test */
            if (node->ns == NULL) {
                if (step->value2 == NULL)
                break;
            } else if (node->ns->href != NULL) {
                if ((step->value2 != NULL) &&
                    (xmlStrEqual(step->value2, node->ns->href)))
                break;
            }
            }
            node = node->parent;
        }
        if (node == NULL)
            goto rollback;
        /*
         * prepare a potential rollback from here
         * for ancestors of that node.
         */
        if (step->op == XML_OP_ANCESTOR)
            xmlPatPushState(&states, i, node);
        else
            xmlPatPushState(&states, i - 1, node);
        continue;
            case XML_OP_NS:
        if (node->type != XML_ELEMENT_NODE)
            goto rollback;
        if (node->ns == NULL) {
            if (step->value != NULL)
            goto rollback;
        } else if (node->ns->href != NULL) {
            if (step->value == NULL)
            goto rollback;
            if (!xmlStrEqual(step->value, node->ns->href))
            goto rollback;
        }
        break;
            case XML_OP_ALL:
        if (node->type != XML_ELEMENT_NODE)
            goto rollback;
        break;
    }
    }
found:
    if (states.states != NULL) {
        /* Free the rollback states */
    xmlFree(states.states);
    }
    return(1);
rollback:
    /* got an error try to rollback */
    if (states.states == NULL)
    return(0);
    if (states.nbstates <= 0) {
    xmlFree(states.states);
    return(0);
    }
    states.nbstates--;
    i = states.states[states.nbstates].step;
    node = states.states[states.nbstates].node;
#if 0
    fprintf(stderr, "Pop: %d, %s\n", i, node->name);
#endif
    goto restart;
}
 
/************************************************************************
 *                                  *
 *          Dedicated parser for templates          *
 *                                  *
 ************************************************************************/
 
#define TODO                                \
    xmlGenericError(xmlGenericErrorContext,             \
        "Unimplemented block at %s:%d\n",               \
            __FILE__, __LINE__);
#define CUR (*ctxt->cur)
#define SKIP(val) ctxt->cur += (val)
#define NXT(val) ctxt->cur[(val)]
#define PEEKPREV(val) ctxt->cur[-(val)]
#define CUR_PTR ctxt->cur
 
#define SKIP_BLANKS                         \
    while (IS_BLANK_CH(CUR)) NEXT
 
#define CURRENT (*ctxt->cur)
#define NEXT ((*ctxt->cur) ?  ctxt->cur++: ctxt->cur)
 
 
#define PUSH(op, val, val2)                     \
    if (xmlPatternAdd(ctxt, ctxt->comp, (op), (val), (val2))) goto error;
 
#define XSLT_ERROR(X)                           \
    { xsltError(ctxt, __FILE__, __LINE__, X);               \
      ctxt->error = (X); return; }
 
#define XSLT_ERROR0(X)                          \
    { xsltError(ctxt, __FILE__, __LINE__, X);               \
      ctxt->error = (X); return(0); }
 
#if 0
static xmlChar *
xmlPatScanLiteral(xmlPatParserContextPtr ctxt) {
    const xmlChar *q, *cur;
    xmlChar *ret = NULL;
    int val, len;
 
    SKIP_BLANKS;
    if (CUR == '"') {
        NEXT;
    cur = q = CUR_PTR;
    val = xmlStringCurrentChar(NULL, cur, &len);
    while ((IS_CHAR(val)) && (val != '"')) {
        cur += len;
        val = xmlStringCurrentChar(NULL, cur, &len);
    }
    if (!IS_CHAR(val)) {
        ctxt->error = 1;
        return(NULL);
    } else {
        if (ctxt->dict)
        ret = (xmlChar *) xmlDictLookup(ctxt->dict, q, cur - q);
        else
        ret = xmlStrndup(q, cur - q);
        }
    cur += len;
    CUR_PTR = cur;
    } else if (CUR == '\'') {
        NEXT;
    cur = q = CUR_PTR;
    val = xmlStringCurrentChar(NULL, cur, &len);
    while ((IS_CHAR(val)) && (val != '\'')) {
        cur += len;
        val = xmlStringCurrentChar(NULL, cur, &len);
    }
    if (!IS_CHAR(val)) {
        ctxt->error = 1;
        return(NULL);
    } else {
        if (ctxt->dict)
        ret = (xmlChar *) xmlDictLookup(ctxt->dict, q, cur - q);
        else
        ret = xmlStrndup(q, cur - q);
        }
    cur += len;
    CUR_PTR = cur;
    } else {
    /* XP_ERROR(XPATH_START_LITERAL_ERROR); */
    ctxt->error = 1;
    return(NULL);
    }
    return(ret);
}
#endif
 
static xmlChar *
xmlPatScanName(xmlPatParserContextPtr ctxt) {
    const xmlChar *q, *cur;
    xmlChar *ret = NULL;
    int val, len;
 
    SKIP_BLANKS;
 
    cur = q = CUR_PTR;
    val = xmlStringCurrentChar(NULL, cur, &len);
    if (!IS_LETTER(val) && (val != '_') && (val != ':'))
    return(NULL);
 
    while ((IS_LETTER(val)) || (IS_DIGIT(val)) ||
           (val == '.') || (val == '-') ||
       (val == '_') ||
       (IS_COMBINING(val)) ||
       (IS_EXTENDER(val))) {
    cur += len;
    val = xmlStringCurrentChar(NULL, cur, &len);
    }
    if (ctxt->dict)
    ret = (xmlChar *) xmlDictLookup(ctxt->dict, q, cur - q);
    else
    ret = xmlStrndup(q, cur - q);
    CUR_PTR = cur;
    return(ret);
}
 
static xmlChar *
xmlPatScanNCName(xmlPatParserContextPtr ctxt) {
    const xmlChar *q, *cur;
    xmlChar *ret = NULL;
    int val, len;
 
    SKIP_BLANKS;
 
    cur = q = CUR_PTR;
    val = xmlStringCurrentChar(NULL, cur, &len);
    if (!IS_LETTER(val) && (val != '_'))
    return(NULL);
 
    while ((IS_LETTER(val)) || (IS_DIGIT(val)) ||
           (val == '.') || (val == '-') ||
       (val == '_') ||
       (IS_COMBINING(val)) ||
       (IS_EXTENDER(val))) {
    cur += len;
    val = xmlStringCurrentChar(NULL, cur, &len);
    }
    if (ctxt->dict)
    ret = (xmlChar *) xmlDictLookup(ctxt->dict, q, cur - q);
    else
    ret = xmlStrndup(q, cur - q);
    CUR_PTR = cur;
    return(ret);
}
 
#if 0
static xmlChar *
xmlPatScanQName(xmlPatParserContextPtr ctxt, xmlChar **prefix) {
    xmlChar *ret = NULL;
 
    *prefix = NULL;
    ret = xmlPatScanNCName(ctxt);
    if (CUR == ':') {
        *prefix = ret;
    NEXT;
    ret = xmlPatScanNCName(ctxt);
    }
    return(ret);
}
#endif
 
static void
xmlCompileAttributeTest(xmlPatParserContextPtr ctxt) {
    xmlChar *token = NULL;
    xmlChar *name = NULL;
    xmlChar *URL = NULL;
 
    SKIP_BLANKS;
    name = xmlPatScanNCName(ctxt);
    if (name == NULL) {
    if (CUR == '*') {
        PUSH(XML_OP_ATTR, NULL, NULL);
        NEXT;
    } else {
        ERROR(NULL, NULL, NULL,
        "xmlCompileAttributeTest : Name expected\n");
        ctxt->error = 1;
    }
    return;
    }
    if (CUR == ':') {
    int i;
    xmlChar *prefix = name;
 
    NEXT;
 
    if (IS_BLANK_CH(CUR)) {
        ERROR5(NULL, NULL, NULL, "Invalid QName.\n", NULL);
        XML_PAT_FREE_STRING(ctxt, prefix);
        ctxt->error = 1;
        goto error;
    }
    /*
    * This is a namespace match
    */
    token = xmlPatScanName(ctxt);
    if ((prefix[0] == 'x') &&
        (prefix[1] == 'm') &&
        (prefix[2] == 'l') &&
        (prefix[3] == 0))
    {
        XML_PAT_COPY_NSNAME(ctxt, URL, XML_XML_NAMESPACE);
    } else {
        for (i = 0;i < ctxt->nb_namespaces;i++) {
        if (xmlStrEqual(ctxt->namespaces[2 * i + 1], prefix)) {
            XML_PAT_COPY_NSNAME(ctxt, URL, ctxt->namespaces[2 * i])
            break;
        }
        }
        if (i >= ctxt->nb_namespaces) {
        ERROR5(NULL, NULL, NULL,
            "xmlCompileAttributeTest : no namespace bound to prefix %s\n",
            prefix);
            XML_PAT_FREE_STRING(ctxt, prefix);
        ctxt->error = 1;
        goto error;
        }
    }
    XML_PAT_FREE_STRING(ctxt, prefix);
    if (token == NULL) {
        if (CUR == '*') {
        NEXT;
        PUSH(XML_OP_ATTR, NULL, URL);
        } else {
        ERROR(NULL, NULL, NULL,
            "xmlCompileAttributeTest : Name expected\n");
        ctxt->error = 1;
        goto error;
        }
    } else {
        PUSH(XML_OP_ATTR, token, URL);
    }
    } else {
    PUSH(XML_OP_ATTR, name, NULL);
    }
    return;
error:
    if (URL != NULL)
    XML_PAT_FREE_STRING(ctxt, URL)
    if (token != NULL)
    XML_PAT_FREE_STRING(ctxt, token);
}
 
static void
xmlCompileStepPattern(xmlPatParserContextPtr ctxt) {
    xmlChar *token = NULL;
    xmlChar *name = NULL;
    xmlChar *URL = NULL;
    int hasBlanks = 0;
 
    SKIP_BLANKS;
    if (CUR == '.') {
    /*
    * Context node.
    */
    NEXT;
    PUSH(XML_OP_ELEM, NULL, NULL);
    return;
    }
    if (CUR == '@') {
    /*
    * Attribute test.
    */
    if (XML_STREAM_XS_IDC_SEL(ctxt->comp)) {
        ERROR5(NULL, NULL, NULL,
        "Unexpected attribute axis in '%s'.\n", ctxt->base);
        ctxt->error = 1;
        return;
    }
    NEXT;
    xmlCompileAttributeTest(ctxt);
    if (ctxt->error != 0)
        goto error;
    return;
    }
    name = xmlPatScanNCName(ctxt);
    if (name == NULL) {
    if (CUR == '*') {
        NEXT;
        PUSH(XML_OP_ALL, NULL, NULL);
        return;
    } else {
        ERROR(NULL, NULL, NULL,
            "xmlCompileStepPattern : Name expected\n");
        ctxt->error = 1;
        return;
    }
    }
    if (IS_BLANK_CH(CUR)) {
    hasBlanks = 1;
    SKIP_BLANKS;
    }
    if (CUR == ':') {
    NEXT;
    if (CUR != ':') {
        xmlChar *prefix = name;
        int i;
 
        if (hasBlanks || IS_BLANK_CH(CUR)) {
        ERROR5(NULL, NULL, NULL, "Invalid QName.\n", NULL);
        ctxt->error = 1;
        goto error;
        }
        /*
         * This is a namespace match
         */
        token = xmlPatScanName(ctxt);
        if ((prefix[0] == 'x') &&
        (prefix[1] == 'm') &&
        (prefix[2] == 'l') &&
        (prefix[3] == 0))
        {
        XML_PAT_COPY_NSNAME(ctxt, URL, XML_XML_NAMESPACE)
        } else {
        for (i = 0;i < ctxt->nb_namespaces;i++) {
            if (xmlStrEqual(ctxt->namespaces[2 * i + 1], prefix)) {
            XML_PAT_COPY_NSNAME(ctxt, URL, ctxt->namespaces[2 * i])
            break;
            }
        }
        if (i >= ctxt->nb_namespaces) {
            ERROR5(NULL, NULL, NULL,
            "xmlCompileStepPattern : no namespace bound to prefix %s\n",
            prefix);
            ctxt->error = 1;
            goto error;
        }
        }
        XML_PAT_FREE_STRING(ctxt, prefix);
        name = NULL;
        if (token == NULL) {
        if (CUR == '*') {
            NEXT;
            PUSH(XML_OP_NS, URL, NULL);
        } else {
            ERROR(NULL, NULL, NULL,
                "xmlCompileStepPattern : Name expected\n");
            ctxt->error = 1;
            goto error;
        }
        } else {
        PUSH(XML_OP_ELEM, token, URL);
        }
    } else {
        NEXT;
        if (xmlStrEqual(name, (const xmlChar *) "child")) {
        XML_PAT_FREE_STRING(ctxt, name);
        name = xmlPatScanName(ctxt);
        if (name == NULL) {
            if (CUR == '*') {
            NEXT;
            PUSH(XML_OP_ALL, NULL, NULL);
            return;
            } else {
            ERROR(NULL, NULL, NULL,
                "xmlCompileStepPattern : QName expected\n");
            ctxt->error = 1;
            goto error;
            }
        }
        if (CUR == ':') {
            xmlChar *prefix = name;
            int i;
 
            NEXT;
            if (IS_BLANK_CH(CUR)) {
            ERROR5(NULL, NULL, NULL, "Invalid QName.\n", NULL);
            ctxt->error = 1;
            goto error;
            }
            /*
            * This is a namespace match
            */
            token = xmlPatScanName(ctxt);
            if ((prefix[0] == 'x') &&
            (prefix[1] == 'm') &&
            (prefix[2] == 'l') &&
            (prefix[3] == 0))
            {
            XML_PAT_COPY_NSNAME(ctxt, URL, XML_XML_NAMESPACE)
            } else {
            for (i = 0;i < ctxt->nb_namespaces;i++) {
                if (xmlStrEqual(ctxt->namespaces[2 * i + 1], prefix)) {
                XML_PAT_COPY_NSNAME(ctxt, URL, ctxt->namespaces[2 * i])
                break;
                }
            }
            if (i >= ctxt->nb_namespaces) {
                ERROR5(NULL, NULL, NULL,
                "xmlCompileStepPattern : no namespace bound "
                "to prefix %s\n", prefix);
                ctxt->error = 1;
                goto error;
            }
            }
            XML_PAT_FREE_STRING(ctxt, prefix);
            name = NULL;
            if (token == NULL) {
            if (CUR == '*') {
                NEXT;
                PUSH(XML_OP_NS, URL, NULL);
            } else {
                ERROR(NULL, NULL, NULL,
                "xmlCompileStepPattern : Name expected\n");
                ctxt->error = 1;
                goto error;
            }
            } else {
            PUSH(XML_OP_CHILD, token, URL);
            }
        } else
            PUSH(XML_OP_CHILD, name, NULL);
        return;
        } else if (xmlStrEqual(name, (const xmlChar *) "attribute")) {
        XML_PAT_FREE_STRING(ctxt, name)
        name = NULL;
        if (XML_STREAM_XS_IDC_SEL(ctxt->comp)) {
            ERROR5(NULL, NULL, NULL,
            "Unexpected attribute axis in '%s'.\n", ctxt->base);
            ctxt->error = 1;
            goto error;
        }
        xmlCompileAttributeTest(ctxt);
        if (ctxt->error != 0)
            goto error;
        return;
        } else {
        ERROR5(NULL, NULL, NULL,
            "The 'element' or 'attribute' axis is expected.\n", NULL);
        ctxt->error = 1;
        goto error;
        }
    }
    } else if (CUR == '*') {
        if (name != NULL) {
        ctxt->error = 1;
        goto error;
    }
    NEXT;
    PUSH(XML_OP_ALL, token, NULL);
    } else {
    PUSH(XML_OP_ELEM, name, NULL);
    }
    return;
error:
    if (URL != NULL)
    XML_PAT_FREE_STRING(ctxt, URL)
    if (token != NULL)
    XML_PAT_FREE_STRING(ctxt, token)
    if (name != NULL)
    XML_PAT_FREE_STRING(ctxt, name)
}
 
static void
xmlCompilePathPattern(xmlPatParserContextPtr ctxt) {
    SKIP_BLANKS;
    if (CUR == '/') {
        ctxt->comp->flags |= PAT_FROM_ROOT;
    } else if ((CUR == '.') || (ctxt->comp->flags & XML_PATTERN_NOTPATTERN)) {
        ctxt->comp->flags |= PAT_FROM_CUR;
    }
 
    if ((CUR == '/') && (NXT(1) == '/')) {
    PUSH(XML_OP_ANCESTOR, NULL, NULL);
    NEXT;
    NEXT;
    } else if ((CUR == '.') && (NXT(1) == '/') && (NXT(2) == '/')) {
    PUSH(XML_OP_ANCESTOR, NULL, NULL);
    NEXT;
    NEXT;
    NEXT;
    /* Check for incompleteness. */
    SKIP_BLANKS;
    if (CUR == 0) {
        ERROR5(NULL, NULL, NULL,
           "Incomplete expression '%s'.\n", ctxt->base);
        ctxt->error = 1;
        goto error;
    }
    }
    if (CUR == '@') {
    NEXT;
    xmlCompileAttributeTest(ctxt);
    SKIP_BLANKS;
    /* TODO: check for incompleteness */
    if (CUR != 0) {
        xmlCompileStepPattern(ctxt);
        if (ctxt->error != 0)
        goto error;
    }
    } else {
        if (CUR == '/') {
        PUSH(XML_OP_ROOT, NULL, NULL);
        NEXT;
        /* Check for incompleteness. */
        SKIP_BLANKS;
        if (CUR == 0) {
        ERROR5(NULL, NULL, NULL,
            "Incomplete expression '%s'.\n", ctxt->base);
        ctxt->error = 1;
        goto error;
        }
    }
    xmlCompileStepPattern(ctxt);
    if (ctxt->error != 0)
        goto error;
    SKIP_BLANKS;
    while (CUR == '/') {
        if (NXT(1) == '/') {
            PUSH(XML_OP_ANCESTOR, NULL, NULL);
        NEXT;
        NEXT;
        SKIP_BLANKS;
        xmlCompileStepPattern(ctxt);
        if (ctxt->error != 0)
            goto error;
        } else {
            PUSH(XML_OP_PARENT, NULL, NULL);
        NEXT;
        SKIP_BLANKS;
        if (CUR == 0) {
            ERROR5(NULL, NULL, NULL,
            "Incomplete expression '%s'.\n", ctxt->base);
            ctxt->error = 1;
            goto error;
        }
        xmlCompileStepPattern(ctxt);
        if (ctxt->error != 0)
            goto error;
        }
    }
    }
    if (CUR != 0) {
    ERROR5(NULL, NULL, NULL,
           "Failed to compile pattern %s\n", ctxt->base);
    ctxt->error = 1;
    }
error:
    return;
}
 
static void
xmlCompileIDCXPathPath(xmlPatParserContextPtr ctxt) {
    SKIP_BLANKS;
    if (CUR == '/') {
    ERROR5(NULL, NULL, NULL,
        "Unexpected selection of the document root in '%s'.\n",
        ctxt->base);
    goto error;
    }
    ctxt->comp->flags |= PAT_FROM_CUR;
 
    if (CUR == '.') {
    /* "." - "self::node()" */
    NEXT;
    SKIP_BLANKS;
    if (CUR == 0) {
        /*
        * Selection of the context node.
        */
        PUSH(XML_OP_ELEM, NULL, NULL);
        return;
    }
    if (CUR != '/') {
        /* TODO: A more meaningful error message. */
        ERROR5(NULL, NULL, NULL,
        "Unexpected token after '.' in '%s'.\n", ctxt->base);
        goto error;
    }
    /* "./" - "self::node()/" */
    NEXT;
    SKIP_BLANKS;
    if (CUR == '/') {
        if (IS_BLANK_CH(PEEKPREV(1))) {
        /*
        * Disallow "./ /"
        */
        ERROR5(NULL, NULL, NULL,
            "Unexpected '/' token in '%s'.\n", ctxt->base);
        goto error;
        }
        /* ".//" - "self:node()/descendant-or-self::node()/" */
        PUSH(XML_OP_ANCESTOR, NULL, NULL);
        NEXT;
        SKIP_BLANKS;
    }
    if (CUR == 0)
        goto error_unfinished;
    }
    /*
    * Process steps.
    */
    do {
    xmlCompileStepPattern(ctxt);
    if (ctxt->error != 0)
        goto error;
    SKIP_BLANKS;
    if (CUR != '/')
        break;
    PUSH(XML_OP_PARENT, NULL, NULL);
    NEXT;
    SKIP_BLANKS;
    if (CUR == '/') {
        /*
        * Disallow subsequent '//'.
        */
        ERROR5(NULL, NULL, NULL,
        "Unexpected subsequent '//' in '%s'.\n",
        ctxt->base);
        goto error;
    }
    if (CUR == 0)
        goto error_unfinished;
 
    } while (CUR != 0);
 
    if (CUR != 0) {
    ERROR5(NULL, NULL, NULL,
        "Failed to compile expression '%s'.\n", ctxt->base);
    ctxt->error = 1;
    }
    return;
error:
    ctxt->error = 1;
    return;
 
error_unfinished:
    ctxt->error = 1;
    ERROR5(NULL, NULL, NULL,
    "Unfinished expression '%s'.\n", ctxt->base);
    return;
}
 
/************************************************************************
 *                                  *
 *          The streaming code              *
 *                                  *
 ************************************************************************/
 
#ifdef DEBUG_STREAMING
static void
xmlDebugStreamComp(xmlStreamCompPtr stream) {
    int i;
 
    if (stream == NULL) {
        printf("Stream: NULL\n");
    return;
    }
    printf("Stream: %d steps\n", stream->nbStep);
    for (i = 0;i < stream->nbStep;i++) {
    if (stream->steps[i].ns != NULL) {
        printf("{%s}", stream->steps[i].ns);
    }
        if (stream->steps[i].name == NULL) {
        printf("* ");
    } else {
        printf("%s ", stream->steps[i].name);
    }
    if (stream->steps[i].flags & XML_STREAM_STEP_ROOT)
        printf("root ");
    if (stream->steps[i].flags & XML_STREAM_STEP_DESC)
        printf("// ");
    if (stream->steps[i].flags & XML_STREAM_STEP_FINAL)
        printf("final ");
    printf("\n");
    }
}
static void
xmlDebugStreamCtxt(xmlStreamCtxtPtr ctxt, int match) {
    int i;
 
    if (ctxt == NULL) {
        printf("Stream: NULL\n");
    return;
    }
    printf("Stream: level %d, %d states: ", ctxt->level, ctxt->nbState);
    if (match)
        printf("matches\n");
    else
        printf("\n");
    for (i = 0;i < ctxt->nbState;i++) {
        if (ctxt->states[2 * i] < 0)
        printf(" %d: free\n", i);
    else {
        printf(" %d: step %d, level %d", i, ctxt->states[2 * i],
               ctxt->states[(2 * i) + 1]);
            if (ctxt->comp->steps[ctxt->states[2 * i]].flags &
            XML_STREAM_STEP_DESC)
            printf(" //\n");
        else
            printf("\n");
    }
    }
}
#endif
static xmlStreamCompPtr
xmlNewStreamComp(int size) {
    xmlStreamCompPtr cur;
 
    if (size < 4)
        size  = 4;
 
    cur = (xmlStreamCompPtr) xmlMalloc(sizeof(xmlStreamComp));
    if (cur == NULL) {
    ERROR(NULL, NULL, NULL,
        "xmlNewStreamComp: malloc failed\n");
    return(NULL);
    }
    memset(cur, 0, sizeof(xmlStreamComp));
    cur->steps = (xmlStreamStepPtr) xmlMalloc(size * sizeof(xmlStreamStep));
    if (cur->steps == NULL) {
    xmlFree(cur);
    ERROR(NULL, NULL, NULL,
          "xmlNewStreamComp: malloc failed\n");
    return(NULL);
    }
    cur->nbStep = 0;
    cur->maxStep = size;
    return(cur);
}
 
static void
xmlFreeStreamComp(xmlStreamCompPtr comp) {
    if (comp != NULL) {
        if (comp->steps != NULL)
        xmlFree(comp->steps);
    if (comp->dict != NULL)
        xmlDictFree(comp->dict);
        xmlFree(comp);
    }
}
 
static int
xmlStreamCompAddStep(xmlStreamCompPtr comp, const xmlChar *name,
                     const xmlChar *ns, int nodeType, int flags) {
    xmlStreamStepPtr cur;
 
    if (comp->nbStep >= comp->maxStep) {
    cur = (xmlStreamStepPtr) xmlRealloc(comp->steps,
                 comp->maxStep * 2 * sizeof(xmlStreamStep));
    if (cur == NULL) {
        ERROR(NULL, NULL, NULL,
          "xmlNewStreamComp: malloc failed\n");
        return(-1);
    }
    comp->steps = cur;
        comp->maxStep *= 2;
    }
    cur = &comp->steps[comp->nbStep++];
    cur->flags = flags;
    cur->name = name;
    cur->ns = ns;
    cur->nodeType = nodeType;
    return(comp->nbStep - 1);
}
 
static int
xmlStreamCompile(xmlPatternPtr comp) {
    xmlStreamCompPtr stream;
    int i, s = 0, root = 0, flags = 0, prevs = -1;
    xmlStepOp step;
 
    if ((comp == NULL) || (comp->steps == NULL))
        return(-1);
    /*
     * special case for .
     */
    if ((comp->nbStep == 1) &&
        (comp->steps[0].op == XML_OP_ELEM) &&
    (comp->steps[0].value == NULL) &&
    (comp->steps[0].value2 == NULL)) {
    stream = xmlNewStreamComp(0);
    if (stream == NULL)
        return(-1);
    /* Note that the stream will have no steps in this case. */
    stream->flags |= XML_STREAM_FINAL_IS_ANY_NODE;
    comp->stream = stream;
    return(0);
    }
 
    stream = xmlNewStreamComp((comp->nbStep / 2) + 1);
    if (stream == NULL)
        return(-1);
    if (comp->dict != NULL) {
        stream->dict = comp->dict;
    xmlDictReference(stream->dict);
    }
 
    i = 0;
    if (comp->flags & PAT_FROM_ROOT)
    stream->flags |= XML_STREAM_FROM_ROOT;
 
    for (;i < comp->nbStep;i++) {
    step = comp->steps[i];
        switch (step.op) {
        case XML_OP_END:
            break;
        case XML_OP_ROOT:
            if (i != 0)
            goto error;
        root = 1;
        break;
        case XML_OP_NS:
        s = xmlStreamCompAddStep(stream, NULL, step.value,
            XML_ELEMENT_NODE, flags);
        if (s < 0)
            goto error;
        prevs = s;
        flags = 0;
        break;
        case XML_OP_ATTR:
        flags |= XML_STREAM_STEP_ATTR;
        prevs = -1;
        s = xmlStreamCompAddStep(stream,
            step.value, step.value2, XML_ATTRIBUTE_NODE, flags);
        flags = 0;
        if (s < 0)
            goto error;
        break;
        case XML_OP_ELEM:
            if ((step.value == NULL) && (step.value2 == NULL)) {
            /*
            * We have a "." or "self::node()" here.
            * Eliminate redundant self::node() tests like in "/./."
            * or "//./"
            * The only case we won't eliminate is "//.", i.e. if
            * self::node() is the last node test and we had
            * continuation somewhere beforehand.
            */
            if ((comp->nbStep == i + 1) &&
            (flags & XML_STREAM_STEP_DESC)) {
            /*
            * Mark the special case where the expression resolves
            * to any type of node.
            */
            if (comp->nbStep == i + 1) {
                stream->flags |= XML_STREAM_FINAL_IS_ANY_NODE;
            }
            flags |= XML_STREAM_STEP_NODE;
            s = xmlStreamCompAddStep(stream, NULL, NULL,
                XML_STREAM_ANY_NODE, flags);
            if (s < 0)
                goto error;
            flags = 0;
            /*
            * If there was a previous step, mark it to be added to
            * the result node-set; this is needed since only
            * the last step will be marked as "final" and only
            * "final" nodes are added to the resulting set.
            */
            if (prevs != -1) {
                stream->steps[prevs].flags |= XML_STREAM_STEP_IN_SET;
                prevs = -1;
            }
            break;
 
            } else {
            /* Just skip this one. */
            continue;
            }
        }
        /* An element node. */
            s = xmlStreamCompAddStep(stream, step.value, step.value2,
            XML_ELEMENT_NODE, flags);
        if (s < 0)
            goto error;
        prevs = s;
        flags = 0;
        break;
        case XML_OP_CHILD:
        /* An element node child. */
            s = xmlStreamCompAddStep(stream, step.value, step.value2,
            XML_ELEMENT_NODE, flags);
        if (s < 0)
            goto error;
        prevs = s;
        flags = 0;
        break;
        case XML_OP_ALL:
            s = xmlStreamCompAddStep(stream, NULL, NULL,
            XML_ELEMENT_NODE, flags);
        if (s < 0)
            goto error;
        prevs = s;
        flags = 0;
        break;
        case XML_OP_PARENT:
            break;
        case XML_OP_ANCESTOR:
        /* Skip redundant continuations. */
        if (flags & XML_STREAM_STEP_DESC)
            break;
            flags |= XML_STREAM_STEP_DESC;
        /*
        * Mark the expression as having "//".
        */
        if ((stream->flags & XML_STREAM_DESC) == 0)
            stream->flags |= XML_STREAM_DESC;
        break;
    }
    }
    if ((! root) && (comp->flags & XML_PATTERN_NOTPATTERN) == 0) {
    /*
    * If this should behave like a real pattern, we will mark
    * the first step as having "//", to be reentrant on every
    * tree level.
    */
    if ((stream->flags & XML_STREAM_DESC) == 0)
        stream->flags |= XML_STREAM_DESC;
 
    if (stream->nbStep > 0) {
        if ((stream->steps[0].flags & XML_STREAM_STEP_DESC) == 0)
        stream->steps[0].flags |= XML_STREAM_STEP_DESC;
    }
    }
    if (stream->nbStep <= s)
    goto error;
    stream->steps[s].flags |= XML_STREAM_STEP_FINAL;
    if (root)
    stream->steps[0].flags |= XML_STREAM_STEP_ROOT;
#ifdef DEBUG_STREAMING
    xmlDebugStreamComp(stream);
#endif
    comp->stream = stream;
    return(0);
error:
    xmlFreeStreamComp(stream);
    return(0);
}
 
static xmlStreamCtxtPtr
xmlNewStreamCtxt(xmlStreamCompPtr stream) {
    xmlStreamCtxtPtr cur;
 
    cur = (xmlStreamCtxtPtr) xmlMalloc(sizeof(xmlStreamCtxt));
    if (cur == NULL) {
    ERROR(NULL, NULL, NULL,
        "xmlNewStreamCtxt: malloc failed\n");
    return(NULL);
    }
    memset(cur, 0, sizeof(xmlStreamCtxt));
    cur->states = (int *) xmlMalloc(4 * 2 * sizeof(int));
    if (cur->states == NULL) {
    xmlFree(cur);
    ERROR(NULL, NULL, NULL,
          "xmlNewStreamCtxt: malloc failed\n");
    return(NULL);
    }
    cur->nbState = 0;
    cur->maxState = 4;
    cur->level = 0;
    cur->comp = stream;
    cur->blockLevel = -1;
    return(cur);
}
 
void
xmlFreeStreamCtxt(xmlStreamCtxtPtr stream) {
    xmlStreamCtxtPtr next;
 
    while (stream != NULL) {
        next = stream->next;
        if (stream->states != NULL)
        xmlFree(stream->states);
        xmlFree(stream);
    stream = next;
    }
}
 
static int
xmlStreamCtxtAddState(xmlStreamCtxtPtr comp, int idx, int level) {
    int i;
    for (i = 0;i < comp->nbState;i++) {
        if (comp->states[2 * i] < 0) {
        comp->states[2 * i] = idx;
        comp->states[2 * i + 1] = level;
        return(i);
    }
    }
    if (comp->nbState >= comp->maxState) {
        int *cur;
 
    cur = (int *) xmlRealloc(comp->states,
                 comp->maxState * 4 * sizeof(int));
    if (cur == NULL) {
        ERROR(NULL, NULL, NULL,
          "xmlNewStreamCtxt: malloc failed\n");
        return(-1);
    }
    comp->states = cur;
        comp->maxState *= 2;
    }
    comp->states[2 * comp->nbState] = idx;
    comp->states[2 * comp->nbState++ + 1] = level;
    return(comp->nbState - 1);
}
 
static int
xmlStreamPushInternal(xmlStreamCtxtPtr stream,
              const xmlChar *name, const xmlChar *ns,
              int nodeType) {
    int ret = 0, err = 0, final = 0, tmp, i, m, match, stepNr, desc;
    xmlStreamCompPtr comp;
    xmlStreamStep step;
#ifdef DEBUG_STREAMING
    xmlStreamCtxtPtr orig = stream;
#endif
 
    if ((stream == NULL) || (stream->nbState < 0))
        return(-1);
 
    while (stream != NULL) {
    comp = stream->comp;
 
    if ((nodeType == XML_ELEMENT_NODE) &&
        (name == NULL) && (ns == NULL)) {
        /* We have a document node here (or a reset). */
        stream->nbState = 0;
        stream->level = 0;
        stream->blockLevel = -1;
        if (comp->flags & XML_STREAM_FROM_ROOT) {
        if (comp->nbStep == 0) {
            /* TODO: We have a "/." here? */
            ret = 1;
        } else {
            if ((comp->nbStep == 1) &&
            (comp->steps[0].nodeType == XML_STREAM_ANY_NODE) &&
            (comp->steps[0].flags & XML_STREAM_STEP_DESC))
            {
            /*
            * In the case of "//." the document node will match
            * as well.
            */
            ret = 1;
            } else if (comp->steps[0].flags & XML_STREAM_STEP_ROOT) {
            /* TODO: Do we need this ? */
            tmp = xmlStreamCtxtAddState(stream, 0, 0);
            if (tmp < 0)
                err++;
            }
        }
        }
        stream = stream->next;
        continue; /* while */
    }
 
    /*
    * Fast check for ".".
    */
    if (comp->nbStep == 0) {
        /*
         * / and . are handled at the XPath node set creation
         * level by checking min depth
         */
        if (stream->flags & XML_PATTERN_XPATH) {
        stream = stream->next;
        continue; /* while */
        }
        /*
        * For non-pattern like evaluation like XML Schema IDCs
        * or traditional XPath expressions, this will match if
        * we are at the first level only, otherwise on every level.
        */
        if ((nodeType != XML_ATTRIBUTE_NODE) &&
        (((stream->flags & XML_PATTERN_NOTPATTERN) == 0) ||
        (stream->level == 0))) {
            ret = 1;
        }
        stream->level++;
        goto stream_next;
    }
    if (stream->blockLevel != -1) {
        /*
        * Skip blocked expressions.
        */
        stream->level++;
        goto stream_next;
    }
 
    if ((nodeType != XML_ELEMENT_NODE) &&
        (nodeType != XML_ATTRIBUTE_NODE) &&
        ((comp->flags & XML_STREAM_FINAL_IS_ANY_NODE) == 0)) {
        /*
        * No need to process nodes of other types if we don't
        * resolve to those types.
        * TODO: Do we need to block the context here?
        */
        stream->level++;
        goto stream_next;
    }
 
    /*
     * Check evolution of existing states
     */
    i = 0;
    m = stream->nbState;
    while (i < m) {
        if ((comp->flags & XML_STREAM_DESC) == 0) {
        /*
        * If there is no "//", then only the last
        * added state is of interest.
        */
        stepNr = stream->states[2 * (stream->nbState -1)];
        /*
        * TODO: Security check, should not happen, remove it.
        */
        if (stream->states[(2 * (stream->nbState -1)) + 1] <
            stream->level) {
            return (-1);
        }
        desc = 0;
        /* loop-stopper */
        i = m;
        } else {
        /*
        * If there are "//", then we need to process every "//"
        * occurring in the states, plus any other state for this
        * level.
        */
        stepNr = stream->states[2 * i];
 
        /* TODO: should not happen anymore: dead states */
        if (stepNr < 0)
            goto next_state;
 
        tmp = stream->states[(2 * i) + 1];
 
        /* skip new states just added */
        if (tmp > stream->level)
            goto next_state;
 
        /* skip states at ancestor levels, except if "//" */
        desc = comp->steps[stepNr].flags & XML_STREAM_STEP_DESC;
        if ((tmp < stream->level) && (!desc))
            goto next_state;
        }
        /*
        * Check for correct node-type.
        */
        step = comp->steps[stepNr];
        if (step.nodeType != nodeType) {
        if (step.nodeType == XML_ATTRIBUTE_NODE) {
            /*
            * Block this expression for deeper evaluation.
            */
            if ((comp->flags & XML_STREAM_DESC) == 0)
            stream->blockLevel = stream->level +1;
            goto next_state;
        } else if (step.nodeType != XML_STREAM_ANY_NODE)
            goto next_state;
        }
        /*
        * Compare local/namespace-name.
        */
        match = 0;
        if (step.nodeType == XML_STREAM_ANY_NODE) {
        match = 1;
        } else if (step.name == NULL) {
        if (step.ns == NULL) {
            /*
            * This lets through all elements/attributes.
            */
            match = 1;
        } else if (ns != NULL)
            match = xmlStrEqual(step.ns, ns);
        } else if (((step.ns != NULL) == (ns != NULL)) &&
        (name != NULL) &&
        (step.name[0] == name[0]) &&
        xmlStrEqual(step.name, name) &&
        ((step.ns == ns) || xmlStrEqual(step.ns, ns)))
        {
        match = 1;
        }
#if 0
/*
* TODO: Pointer comparison won't work, since not guaranteed that the given
*  values are in the same dict; especially if it's the namespace name,
*  normally coming from ns->href. We need a namespace dict mechanism !
*/
        } else if (comp->dict) {
        if (step.name == NULL) {
            if (step.ns == NULL)
            match = 1;
            else
            match = (step.ns == ns);
        } else {
            match = ((step.name == name) && (step.ns == ns));
        }
#endif /* if 0 ------------------------------------------------------- */
        if (match) {
        final = step.flags & XML_STREAM_STEP_FINAL;
        if (desc) {
            if (final) {
            ret = 1;
            } else {
            /* descending match create a new state */
            xmlStreamCtxtAddState(stream, stepNr + 1,
                                  stream->level + 1);
            }
        } else {
            if (final) {
            ret = 1;
            } else {
            xmlStreamCtxtAddState(stream, stepNr + 1,
                                  stream->level + 1);
            }
        }
        if ((ret != 1) && (step.flags & XML_STREAM_STEP_IN_SET)) {
            /*
            * Check if we have a special case like "foo/bar//.", where
            * "foo" is selected as well.
            */
            ret = 1;
        }
        }
        if (((comp->flags & XML_STREAM_DESC) == 0) &&
        ((! match) || final))  {
        /*
        * Mark this expression as blocked for any evaluation at
        * deeper levels. Note that this includes "/foo"
        * expressions if the *pattern* behaviour is used.
        */
        stream->blockLevel = stream->level +1;
        }
next_state:
        i++;
    }
 
    stream->level++;
 
    /*
    * Re/enter the expression.
    * Don't reenter if it's an absolute expression like "/foo",
    *   except "//foo".
    */
    step = comp->steps[0];
    if (step.flags & XML_STREAM_STEP_ROOT)
        goto stream_next;
 
    desc = step.flags & XML_STREAM_STEP_DESC;
    if (stream->flags & XML_PATTERN_NOTPATTERN) {
        /*
        * Re/enter the expression if it is a "descendant" one,
        * or if we are at the 1st level of evaluation.
        */
 
        if (stream->level == 1) {
        if (XML_STREAM_XS_IDC(stream)) {
            /*
            * XS-IDC: The missing "self::node()" will always
            * match the first given node.
            */
            goto stream_next;
        } else
            goto compare;
        }
        /*
        * A "//" is always reentrant.
        */
        if (desc)
        goto compare;
 
        /*
        * XS-IDC: Process the 2nd level, since the missing
        * "self::node()" is responsible for the 2nd level being
        * the real start level.
        */
        if ((stream->level == 2) && XML_STREAM_XS_IDC(stream))
        goto compare;
 
        goto stream_next;
    }
 
compare:
    /*
    * Check expected node-type.
    */
    if (step.nodeType != nodeType) {
        if (nodeType == XML_ATTRIBUTE_NODE)
        goto stream_next;
        else if (step.nodeType != XML_STREAM_ANY_NODE)
        goto stream_next;
    }
    /*
    * Compare local/namespace-name.
    */
    match = 0;
    if (step.nodeType == XML_STREAM_ANY_NODE) {
        match = 1;
    } else if (step.name == NULL) {
        if (step.ns == NULL) {
        /*
        * This lets through all elements/attributes.
        */
        match = 1;
        } else if (ns != NULL)
        match = xmlStrEqual(step.ns, ns);
    } else if (((step.ns != NULL) == (ns != NULL)) &&
        (name != NULL) &&
        (step.name[0] == name[0]) &&
        xmlStrEqual(step.name, name) &&
        ((step.ns == ns) || xmlStrEqual(step.ns, ns)))
    {
        match = 1;
    }
    final = step.flags & XML_STREAM_STEP_FINAL;
    if (match) {
        if (final)
        ret = 1;
        else
        xmlStreamCtxtAddState(stream, 1, stream->level);
        if ((ret != 1) && (step.flags & XML_STREAM_STEP_IN_SET)) {
        /*
        * Check if we have a special case like "foo//.", where
        * "foo" is selected as well.
        */
        ret = 1;
        }
    }
    if (((comp->flags & XML_STREAM_DESC) == 0) &&
        ((! match) || final))  {
        /*
        * Mark this expression as blocked for any evaluation at
        * deeper levels.
        */
        stream->blockLevel = stream->level;
    }
 
stream_next:
        stream = stream->next;
    } /* while stream != NULL */
 
    if (err > 0)
        ret = -1;
#ifdef DEBUG_STREAMING
    xmlDebugStreamCtxt(orig, ret);
#endif
    return(ret);
}
 
int
xmlStreamPush(xmlStreamCtxtPtr stream,
              const xmlChar *name, const xmlChar *ns) {
    return (xmlStreamPushInternal(stream, name, ns, (int) XML_ELEMENT_NODE));
}
 
int
xmlStreamPushNode(xmlStreamCtxtPtr stream,
          const xmlChar *name, const xmlChar *ns,
          int nodeType)
{
    return (xmlStreamPushInternal(stream, name, ns,
    nodeType));
}
 
int
xmlStreamPushAttr(xmlStreamCtxtPtr stream,
          const xmlChar *name, const xmlChar *ns) {
    return (xmlStreamPushInternal(stream, name, ns, (int) XML_ATTRIBUTE_NODE));
}
 
int
xmlStreamPop(xmlStreamCtxtPtr stream) {
    int i, lev;
 
    if (stream == NULL)
        return(-1);
    while (stream != NULL) {
    /*
    * Reset block-level.
    */
    if (stream->blockLevel == stream->level)
        stream->blockLevel = -1;
 
    /*
     *  stream->level can be zero when XML_FINAL_IS_ANY_NODE is set
     *  (see the thread at
     *  http://mail.gnome.org/archives/xslt/2008-July/msg00027.html)
     */
    if (stream->level)
        stream->level--;
    /*
     * Check evolution of existing states
     */
    for (i = stream->nbState -1; i >= 0; i--) {
        /* discard obsoleted states */
        lev = stream->states[(2 * i) + 1];
        if (lev > stream->level)
        stream->nbState--;
        if (lev <= stream->level)
        break;
    }
    stream = stream->next;
    }
    return(0);
}
 
int
xmlStreamWantsAnyNode(xmlStreamCtxtPtr streamCtxt)
{
    if (streamCtxt == NULL)
    return(-1);
    while (streamCtxt != NULL) {
    if (streamCtxt->comp->flags & XML_STREAM_FINAL_IS_ANY_NODE)
        return(1);
    streamCtxt = streamCtxt->next;
    }
    return(0);
}
 
/************************************************************************
 *                                  *
 *          The public interfaces               *
 *                                  *
 ************************************************************************/
 
xmlPatternPtr
xmlPatterncompile(const xmlChar *pattern, xmlDict *dict, int flags,
                  const xmlChar **namespaces) {
    xmlPatternPtr ret = NULL, cur;
    xmlPatParserContextPtr ctxt = NULL;
    const xmlChar *or, *start;
    xmlChar *tmp = NULL;
    int type = 0;
    int streamable = 1;
 
    if (pattern == NULL)
        return(NULL);
 
    start = pattern;
    or = start;
    while (*or != 0) {
    tmp = NULL;
    while ((*or != 0) && (*or != '|')) or++;
        if (*or == 0)
        ctxt = xmlNewPatParserContext(start, dict, namespaces);
    else {
        tmp = xmlStrndup(start, or - start);
        if (tmp != NULL) {
        ctxt = xmlNewPatParserContext(tmp, dict, namespaces);
        }
        or++;
    }
    if (ctxt == NULL) goto error;
    cur = xmlNewPattern();
    if (cur == NULL) goto error;
    /*
    * Assign string dict.
    */
    if (dict) {
        cur->dict = dict;
        xmlDictReference(dict);
    }
    if (ret == NULL)
        ret = cur;
    else {
        cur->next = ret->next;
        ret->next = cur;
    }
    cur->flags = flags;
    ctxt->comp = cur;
 
    if (XML_STREAM_XS_IDC(cur))
        xmlCompileIDCXPathPath(ctxt);
    else
        xmlCompilePathPattern(ctxt);
    if (ctxt->error != 0)
        goto error;
    xmlFreePatParserContext(ctxt);
    ctxt = NULL;
 
 
        if (streamable) {
        if (type == 0) {
            type = cur->flags & (PAT_FROM_ROOT | PAT_FROM_CUR);
        } else if (type == PAT_FROM_ROOT) {
            if (cur->flags & PAT_FROM_CUR)
            streamable = 0;
        } else if (type == PAT_FROM_CUR) {
            if (cur->flags & PAT_FROM_ROOT)
            streamable = 0;
        }
    }
    if (streamable)
        xmlStreamCompile(cur);
    if (xmlReversePattern(cur) < 0)
        goto error;
    if (tmp != NULL) {
        xmlFree(tmp);
        tmp = NULL;
    }
    start = or;
    }
    if (streamable == 0) {
        cur = ret;
    while (cur != NULL) {
        if (cur->stream != NULL) {
        xmlFreeStreamComp(cur->stream);
        cur->stream = NULL;
        }
        cur = cur->next;
    }
    }
 
    return(ret);
error:
    if (ctxt != NULL) xmlFreePatParserContext(ctxt);
    if (ret != NULL) xmlFreePattern(ret);
    if (tmp != NULL) xmlFree(tmp);
    return(NULL);
}
 
int
xmlPatternMatch(xmlPatternPtr comp, xmlNodePtr node)
{
    int ret = 0;
 
    if ((comp == NULL) || (node == NULL))
        return(-1);
 
    while (comp != NULL) {
        ret = xmlPatMatch(comp, node);
    if (ret != 0)
        return(ret);
    comp = comp->next;
    }
    return(ret);
}
 
xmlStreamCtxtPtr
xmlPatternGetStreamCtxt(xmlPatternPtr comp)
{
    xmlStreamCtxtPtr ret = NULL, cur;
 
    if ((comp == NULL) || (comp->stream == NULL))
        return(NULL);
 
    while (comp != NULL) {
        if (comp->stream == NULL)
        goto failed;
    cur = xmlNewStreamCtxt(comp->stream);
    if (cur == NULL)
        goto failed;
    if (ret == NULL)
        ret = cur;
    else {
        cur->next = ret->next;
        ret->next = cur;
    }
    cur->flags = comp->flags;
    comp = comp->next;
    }
    return(ret);
failed:
    xmlFreeStreamCtxt(ret);
    return(NULL);
}
 
int
xmlPatternStreamable(xmlPatternPtr comp) {
    if (comp == NULL)
        return(-1);
    while (comp != NULL) {
        if (comp->stream == NULL)
        return(0);
    comp = comp->next;
    }
    return(1);
}
 
int
xmlPatternMaxDepth(xmlPatternPtr comp) {
    int ret = 0, i;
    if (comp == NULL)
        return(-1);
    while (comp != NULL) {
        if (comp->stream == NULL)
        return(-1);
    for (i = 0;i < comp->stream->nbStep;i++)
        if (comp->stream->steps[i].flags & XML_STREAM_STEP_DESC)
            return(-2);
    if (comp->stream->nbStep > ret)
        ret = comp->stream->nbStep;
    comp = comp->next;
    }
    return(ret);
}
 
int
xmlPatternMinDepth(xmlPatternPtr comp) {
    int ret = 12345678;
    if (comp == NULL)
        return(-1);
    while (comp != NULL) {
        if (comp->stream == NULL)
        return(-1);
    if (comp->stream->nbStep < ret)
        ret = comp->stream->nbStep;
    if (ret == 0)
        return(0);
    comp = comp->next;
    }
    return(ret);
}
 
int
xmlPatternFromRoot(xmlPatternPtr comp) {
    if (comp == NULL)
        return(-1);
    while (comp != NULL) {
        if (comp->stream == NULL)
        return(-1);
    if (comp->flags & PAT_FROM_ROOT)
        return(1);
    comp = comp->next;
    }
    return(0);
 
}
 
#endif /* LIBXML_PATTERN_ENABLED */