pattern.c

ReactOS是一些高手根据Windows XP的内核编写出的类XP。内核实现机理和API函数调用几乎相同。甚至可以兼容XP的程序。喜欢研究系统内核的人可以看一看。

/*
 * 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.
 *
 * [e-mail]
 */

/*
 * 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
 * - 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

/*
* TODO: This is used on _xmlStreamCtxt, so don't use any values
* from xmlPatternFlags.
*/
#define XML_STREAM_DESC 1<<16

#define XML_PATTERN_NOTPATTERN  (XML_PATTERN_XPATH | \
				 XML_PATTERN_XSSEL | \
				 XML_PATTERN_XSFIELD)

#define XML_STREAM_XS_IDC(item) (item->flags & \
    (XML_PATTERN_XSSEL | XML_PATTERN_XSFIELD))

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 */
};

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;
};

#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 */
    xmlPatternFlags 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;