pattern.c

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

		xmlCompileAttributeTest(ctxt);
		if (ctxt->error != 0)
		    goto error;
		return;
	    } else {
		ERROR(NULL, NULL, NULL,
		    "xmlCompileStepPattern : 'child' or 'attribute' expected\n");
		ctxt->error = 1;
		goto error;
	    }
	    /* NOT REACHED xmlFree(name); */
	}
    } else if (CUR == '*') {
        if (name != NULL) {
	    ctxt->error = 1;
	    goto error;
	}
	NEXT;
	PUSH(XML_OP_ALL, token, NULL);
    } else {
	if (name == NULL) {
	    ctxt->error = 1;
	    goto error;
	}
	PUSH(XML_OP_ELEM, name, NULL);
    }
    return;
error:
    if (URL != NULL)
	xmlFree(URL);
    if (token != NULL)
	xmlFree(token);
    if (name != NULL)
	xmlFree(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;
    }
    if (CUR == '@') {
	NEXT;
	xmlCompileAttributeTest(ctxt);
	SKIP_BLANKS;
	if (CUR != 0) {
	    xmlCompileStepPattern(ctxt);
	}
    } else {
        if (CUR == '/') {
	    PUSH(XML_OP_ROOT, NULL, NULL);
	    NEXT;
	}
	xmlCompileStepPattern(ctxt);
	SKIP_BLANKS;
	while (CUR == '/') {
	    if (NXT(1) == '/') {
	        PUSH(XML_OP_ANCESTOR, NULL, NULL);
		NEXT;
		NEXT;
		SKIP_BLANKS;
		xmlCompileStepPattern(ctxt);
	    } else {
	        PUSH(XML_OP_PARENT, NULL, NULL);
		NEXT;
		SKIP_BLANKS;
		if (CUR != 0) {
		    xmlCompileStepPattern(ctxt);
		}
	    }
	}
    }
    if (CUR != 0) {
	ERROR5(NULL, NULL, NULL,
	       "Failed to compile pattern %s\n", ctxt->base);
	ctxt->error = 1;
    }
error:
    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 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;
    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;

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

    /*
     * Skip leading ./ on relative paths
     */
    i = 0;
    while ((comp->flags & PAT_FROM_CUR) && (comp->nbStep > i + 2) &&
        (comp->steps[i].op == XML_OP_ELEM) &&
	(comp->steps[i].value == NULL) &&
	(comp->steps[i].value2 == NULL) &&
	(comp->steps[i + 1].op == XML_OP_PARENT)) {
	i += 2;
    }
    for (;i < comp->nbStep;i++) {
        switch (comp->steps[i].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,
		    comp->steps[i].value, flags);
		flags = 0;
		if (s < 0)
		    goto error;
		break;	    
	    case XML_OP_ATTR:
		flags |= XML_STREAM_STEP_ATTR;
		s = xmlStreamCompAddStep(stream, comp->steps[i].value,
		    comp->steps[i].value2, flags);
		flags = 0;
		if (s < 0)
		    goto error;
		break;
	    case XML_OP_ELEM:
	        if ((comp->steps[i].value == NULL) &&
		    (comp->steps[i].value2 == NULL) &&
		    (comp->nbStep > i + 2) &&
		    (comp->steps[i + 1].op == XML_OP_PARENT)) {
		    i++;
		    continue;
		 }
	    case XML_OP_CHILD:
	        s = xmlStreamCompAddStep(stream, comp->steps[i].value,
		                         comp->steps[i].value2, flags);
		flags = 0;
		if (s < 0)
		    goto error;
		break;	    
	    case XML_OP_ALL:
	        s = xmlStreamCompAddStep(stream, NULL, NULL, flags);
		flags = 0;
		if (s < 0)
		    goto error;
		break;
	    case XML_OP_PARENT:
	        if ((comp->nbStep > i + 1) &&
		    (comp->steps[i + 1].op == XML_OP_ELEM) &&
		    (comp->steps[i + 1].value == NULL) &&
		    (comp->steps[i + 1].value2 == NULL)) {
		    i++;
		    continue;
		 }
	        break;
	    case XML_OP_ANCESTOR:
	        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;	    
	}
    }
    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,
		      xmlElementType nodeType) {
    int ret = 0, err = 0, final = 0, tmp, i, m, match, step, desc;
    xmlStreamCompPtr comp;
#ifdef DEBUG_STREAMING
    xmlStreamCtxtPtr orig = stream;
#endif

    if ((stream == NULL) || (stream->nbState < 0))
        return(-1);

    while (stream != NULL) {
	comp = stream->comp;
	if ((name == NULL) && (ns == NULL)) {
	    stream->nbState = 0;
	    stream->level = 0;
	    stream->blockLevel = -1;
	    if (comp->steps[0].flags & XML_STREAM_STEP_ROOT) {
		tmp = xmlStreamCtxtAddState(stream, 0, 0);
		if (tmp < 0)
		    err++;
		if (comp->nbStep == 0)
		    ret = 1;
	    }
	    stream = stream->next;
	    continue; /* while */
	}

	/*
	* Fast check for ".".
	*/
	if (comp->nbStep == 0) {
	    /*
	    * 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_ELEMENT_NODE) &&
		(((stream->flags & XML_PATTERN_NOTPATTERN) == 0) ||
		(stream->level == 0))) {
		    ret = 1;		
	    }
	    stream->level++;
	    goto stream_next;
	}