/* * 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 */#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 xmlPatternPtrxmlNewPattern(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 */voidxmlFreePattern(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 */voidxmlFreePatternList(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 xmlPatParserContextPtrxmlNewPatParserContext(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 voidxmlFreePatParserContext(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 intxmlPatternAdd(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 voidxsltSwapTopPattern(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 intxmlReversePattern(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 intxmlPatPushState(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 intxmlPatMatch(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;