diff options
Diffstat (limited to 'libxml2/pattern.c')
| -rw-r--r-- | libxml2/pattern.c | 2617 |
1 files changed, 2617 insertions, 0 deletions
diff --git a/libxml2/pattern.c b/libxml2/pattern.c new file mode 100644 index 0000000..33dee3a --- /dev/null +++ b/libxml2/pattern.c @@ -0,0 +1,2617 @@ +/* + * pattern.c: Implemetation 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 carefull 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 * + * * + ************************************************************************/ + +/** + * xmlNewPattern: + * + * Create a new XSLT Pattern + * + * Returns the newly allocated xmlPatternPtr or NULL in case of error + */ +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); +} + +/** + * xmlFreePattern: + * @comp: an XSLT comp + * + * Free up the memory allocated by @comp + */ +void +xmlFreePattern(xmlPatternPtr comp) { + xmlStepOpPtr op; + int i; + + if (comp == NULL) + return; + if (comp->next != NULL) + xmlFreePattern(comp->next); + 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); +} + +/** + * xmlFreePatternList: + * @comp: an XSLT comp list + * + * Free up the memory allocated by all the elements of @comp + */ +void +xmlFreePatternList(xmlPatternPtr comp) { + xmlPatternPtr cur; + + while (comp != NULL) { + cur = comp; + comp = comp->next; + cur->next = NULL; + xmlFreePattern(cur); + } +} + +/** + * xmlNewPatParserContext: + * @pattern: the pattern context + * @dict: the inherited dictionary or NULL + * @namespaces: the prefix definitions, array of [URI, prefix] terminated + * with [NULL, NULL] or NULL if no namespace is used + * + * Create a new XML pattern parser context + * + * Returns the newly allocated xmlPatParserContextPtr or NULL in case of error + */ +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); +} + +/** + * xmlFreePatParserContext: + * @ctxt: an XSLT parser context + * + * Free up the memory allocated by @ctxt + */ +static void +xmlFreePatParserContext(xmlPatParserContextPtr ctxt) { + if (ctxt == NULL) + return; + memset(ctxt, -1, sizeof(xmlPatParserContext)); + xmlFree(ctxt); +} + +/** + * xmlPatternAdd: + * @comp: the compiled match expression + * @op: an op + * @value: the first value + * @value2: the second value + * + * Add a step to an XSLT Compiled Match + * + * Returns -1 in case of failure, 0 otherwise. + */ +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 +/** + * xsltSwapTopPattern: + * @comp: the compiled match expression + * + * reverse the two top steps. + */ +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 + +/** + * xmlReversePattern: + * @comp: the compiled match expression + * + * reverse all the stack of expressions + * + * returns 0 in case of success and -1 in case of error. + */ +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); +} + +/** + * xmlPatMatch: + * @comp: the precompiled pattern + * @node: a node + * + * Test whether the node matches the pattern + * + * Returns 1 if it matches, 0 if it doesn't and -1 in case of failure + */ +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) || +#ifdef LIBXML_DOCB_ENABLED + (node->type == XML_DOCB_DOCUMENT_NODE) || +#endif + (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) && +#ifdef LIBXML_DOCB_ENABLED + (node->type != XML_DOCB_DOCUMENT_NODE) && +#endif + (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) || +#ifdef LIBXML_DOCB_ENABLED + (node->type == XML_DOCB_DOCUMENT_NODE) || +#endif + (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) || +#ifdef LIBXML_DOCB_ENABLED + (node->type == XML_DOCB_DOCUMENT_NODE) || +#endif + (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 +/** + * xmlPatScanLiteral: + * @ctxt: the XPath Parser context + * + * Parse an XPath Litteral: + * + * [29] Literal ::= '"' [^"]* '"' + * | "'" [^']* "'" + * + * Returns the Literal parsed or NULL + */ + +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 + +/** + * xmlPatScanName: + * @ctxt: the XPath Parser context + * + * [4] NameChar ::= Letter | Digit | '.' | '-' | '_' | + * CombiningChar | Extender + * + * [5] Name ::= (Letter | '_' | ':') (NameChar)* + * + * [6] Names ::= Name (S Name)* + * + * Returns the Name parsed or NULL + */ + +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); +} + +/** + * xmlPatScanNCName: + * @ctxt: the XPath Parser context + * + * Parses a non qualified name + * + * Returns the Name parsed or NULL + */ + +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 +/** + * xmlPatScanQName: + * @ctxt: the XPath Parser context + * @prefix: the place to store the prefix + * + * Parse a qualified name + * + * Returns the Name parsed or NULL + */ + +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 + +/** + * xmlCompileAttributeTest: + * @ctxt: the compilation context + * + * Compile an attribute test. + */ +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); + 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); +} + +/** + * xmlCompileStepPattern: + * @ctxt: the compilation context + * + * Compile the Step Pattern and generates a precompiled + * form suitable for fast matching. + * + * [3] Step ::= '.' | NameTest + * [4] NameTest ::= QName | '*' | NCName ':' '*' + */ + +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) +} + +/** + * xmlCompilePathPattern: + * @ctxt: the compilation context + * + * Compile the Path Pattern and generates a precompiled + * form suitable for fast matching. + * + * [5] Path ::= ('.//')? ( Step '/' )* ( Step | '@' NameTest ) + */ +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; +} + +/** + * xmlCompileIDCXPathPath: + * @ctxt: the compilation context + * + * Compile the Path Pattern and generates a precompiled + * form suitable for fast matching. + * + * [5] Path ::= ('.//')? ( Step '/' )* ( Step | '@' NameTest ) + */ +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 +/** + * xmlNewStreamComp: + * @size: the number of expected steps + * + * build a new compiled pattern for streaming + * + * Returns the new structure or NULL in case of error. + */ +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); +} + +/** + * xmlFreeStreamComp: + * @comp: the compiled pattern for streaming + * + * Free the compiled pattern for streaming + */ +static void +xmlFreeStreamComp(xmlStreamCompPtr comp) { + if (comp != NULL) { + if (comp->steps != NULL) + xmlFree(comp->steps); + if (comp->dict != NULL) + xmlDictFree(comp->dict); + xmlFree(comp); + } +} + +/** + * xmlStreamCompAddStep: + * @comp: the compiled pattern for streaming + * @name: the first string, the name, or NULL for * + * @ns: the second step, the namespace name + * @flags: the flags for that step + * + * Add a new step to the compiled pattern + * + * Returns -1 in case of error or the step index if successful + */ +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); +} + +/** + * xmlStreamCompile: + * @comp: the precompiled pattern + * + * Tries to stream compile a pattern + * + * Returns -1 in case of failure and 0 in case of success. + */ +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); +} + +/** + * xmlNewStreamCtxt: + * @size: the number of expected states + * + * build a new stream context + * + * Returns the new structure or NULL in case of error. + */ +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); +} + +/** + * xmlFreeStreamCtxt: + * @stream: the stream context + * + * Free the stream context + */ +void +xmlFreeStreamCtxt(xmlStreamCtxtPtr stream) { + xmlStreamCtxtPtr next; + + while (stream != NULL) { + next = stream->next; + if (stream->states != NULL) + xmlFree(stream->states); + xmlFree(stream); + stream = next; + } +} + +/** + * xmlStreamCtxtAddState: + * @comp: the stream context + * @idx: the step index for that streaming state + * + * Add a new state to the stream context + * + * Returns -1 in case of error or the state index if successful + */ +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); +} + +/** + * xmlStreamPushInternal: + * @stream: the stream context + * @name: the current name + * @ns: the namespace name + * @nodeType: the type of the node + * + * Push new data onto the stream. NOTE: if the call xmlPatterncompile() + * indicated a dictionary, then strings for name and ns will be expected + * to come from the dictionary. + * Both @name and @ns being NULL means the / i.e. the root of the document. + * This can also act as a reset. + * + * Returns: -1 in case of error, 1 if the current state in the stream is a + * match and 0 otherwise. + */ +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 "//" + * occuring 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); +} + +/** + * xmlStreamPush: + * @stream: the stream context + * @name: the current name + * @ns: the namespace name + * + * Push new data onto the stream. NOTE: if the call xmlPatterncompile() + * indicated a dictionary, then strings for name and ns will be expected + * to come from the dictionary. + * Both @name and @ns being NULL means the / i.e. the root of the document. + * This can also act as a reset. + * Otherwise the function will act as if it has been given an element-node. + * + * Returns: -1 in case of error, 1 if the current state in the stream is a + * match and 0 otherwise. + */ +int +xmlStreamPush(xmlStreamCtxtPtr stream, + const xmlChar *name, const xmlChar *ns) { + return (xmlStreamPushInternal(stream, name, ns, (int) XML_ELEMENT_NODE)); +} + +/** + * xmlStreamPushNode: + * @stream: the stream context + * @name: the current name + * @ns: the namespace name + * @nodeType: the type of the node being pushed + * + * Push new data onto the stream. NOTE: if the call xmlPatterncompile() + * indicated a dictionary, then strings for name and ns will be expected + * to come from the dictionary. + * Both @name and @ns being NULL means the / i.e. the root of the document. + * This can also act as a reset. + * Different from xmlStreamPush() this function can be fed with nodes of type: + * element-, attribute-, text-, cdata-section-, comment- and + * processing-instruction-node. + * + * Returns: -1 in case of error, 1 if the current state in the stream is a + * match and 0 otherwise. + */ +int +xmlStreamPushNode(xmlStreamCtxtPtr stream, + const xmlChar *name, const xmlChar *ns, + int nodeType) +{ + return (xmlStreamPushInternal(stream, name, ns, + nodeType)); +} + +/** +* xmlStreamPushAttr: +* @stream: the stream context +* @name: the current name +* @ns: the namespace name +* +* Push new attribute data onto the stream. NOTE: if the call xmlPatterncompile() +* indicated a dictionary, then strings for name and ns will be expected +* to come from the dictionary. +* Both @name and @ns being NULL means the / i.e. the root of the document. +* This can also act as a reset. +* Otherwise the function will act as if it has been given an attribute-node. +* +* Returns: -1 in case of error, 1 if the current state in the stream is a +* match and 0 otherwise. +*/ +int +xmlStreamPushAttr(xmlStreamCtxtPtr stream, + const xmlChar *name, const xmlChar *ns) { + return (xmlStreamPushInternal(stream, name, ns, (int) XML_ATTRIBUTE_NODE)); +} + +/** + * xmlStreamPop: + * @stream: the stream context + * + * push one level from the stream. + * + * Returns: -1 in case of error, 0 otherwise. + */ +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); +} + +/** + * xmlStreamWantsAnyNode: + * @streamCtxt: the stream context + * + * Query if the streaming pattern additionally needs to be fed with + * text-, cdata-section-, comment- and processing-instruction-nodes. + * If the result is 0 then only element-nodes and attribute-nodes + * need to be pushed. + * + * Returns: 1 in case of need of nodes of the above described types, + * 0 otherwise. -1 on API errors. + */ +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 * + * * + ************************************************************************/ + +/** + * xmlPatterncompile: + * @pattern: the pattern to compile + * @dict: an optional dictionary for interned strings + * @flags: compilation flags, see xmlPatternFlags + * @namespaces: the prefix definitions, array of [URI, prefix] or NULL + * + * Compile a pattern. + * + * Returns the compiled form of the pattern or NULL in case of error + */ +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); +} + +/** + * xmlPatternMatch: + * @comp: the precompiled pattern + * @node: a node + * + * Test whether the node matches the pattern + * + * Returns 1 if it matches, 0 if it doesn't and -1 in case of failure + */ +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); +} + +/** + * xmlPatternGetStreamCtxt: + * @comp: the precompiled pattern + * + * Get a streaming context for that pattern + * Use xmlFreeStreamCtxt to free the context. + * + * Returns a pointer to the context or NULL in case of failure + */ +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); +} + +/** + * xmlPatternStreamable: + * @comp: the precompiled pattern + * + * Check if the pattern is streamable i.e. xmlPatternGetStreamCtxt() + * should work. + * + * Returns 1 if streamable, 0 if not and -1 in case of error. + */ +int +xmlPatternStreamable(xmlPatternPtr comp) { + if (comp == NULL) + return(-1); + while (comp != NULL) { + if (comp->stream == NULL) + return(0); + comp = comp->next; + } + return(1); +} + +/** + * xmlPatternMaxDepth: + * @comp: the precompiled pattern + * + * Check the maximum depth reachable by a pattern + * + * Returns -2 if no limit (using //), otherwise the depth, + * and -1 in case of error + */ +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); +} + +/** + * xmlPatternMinDepth: + * @comp: the precompiled pattern + * + * Check the minimum depth reachable by a pattern, 0 mean the / or . are + * part of the set. + * + * Returns -1 in case of error otherwise the depth, + * + */ +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); +} + +/** + * xmlPatternFromRoot: + * @comp: the precompiled pattern + * + * Check if the pattern must be looked at from the root. + * + * Returns 1 if true, 0 if false and -1 in case of error + */ +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); + +} + +#define bottom_pattern +#include "elfgcchack.h" +#endif /* LIBXML_PATTERN_ENABLED */ |