xmlregexp.c revision 38ae7e4efe803ea78b6499cd05a394db32623e41
/*
* regexp.c: generic and extensible Regular Expression engine
*
* Basically designed with the purpose of compiling regexps for
* the variety of validation/shemas mechanisms now available in
* XML related specifications these include:
* - XML-1.0 DTD validation
* - XML Schemas structure part 1
* - XML Schemas Datatypes part 2 especially Appendix F
*
* See Copyright for the status of this software.
*
* Daniel Veillard <veillard@redhat.com>
*/
#define IN_LIBXML
#include "libxml.h"
#ifdef LIBXML_REGEXP_ENABLED
/* #define DEBUG_ERR */
#include <stdio.h>
#include <string.h>
#ifdef HAVE_LIMITS_H
#include <limits.h>
#endif
#include <libxml/parserInternals.h>
#include <libxml/xmlregexp.h>
#include <libxml/xmlautomata.h>
#include <libxml/xmlunicode.h>
#ifndef INT_MAX
#endif
/* #define DEBUG_REGEXP_GRAPH */
/* #define DEBUG_REGEXP_EXEC */
/* #define DEBUG_PUSH */
/* #define DEBUG_COMPACTION */
#define MAX_PUSH 10000000
#define XML_REG_STRING_SEPARATOR '|'
/*
* Need PREV to check on a '-' within a Character Group. May only be used
* when it's guaranteed that cur is not at the beginning of ctxt->string!
*/
/**
* TODO:
*
* macro to flag unimplemented blocks
*/
#define TODO \
"Unimplemented block at %s:%d\n", \
/************************************************************************
* *
* Datatypes and structures *
* *
************************************************************************/
/*
* Note: the order of the enums below is significant, do not shuffle
*/
typedef enum {
XML_REGEXP_EPSILON = 1,
XML_REGEXP_SUBREG, /* used for () sub regexps */
XML_REGEXP_ANYCHAR, /* . */
XML_REGEXP_ANYSPACE, /* \s */
XML_REGEXP_NOTSPACE, /* \S */
XML_REGEXP_INITNAME, /* \l */
XML_REGEXP_NOTINITNAME, /* \L */
XML_REGEXP_NAMECHAR, /* \c */
XML_REGEXP_NOTNAMECHAR, /* \C */
XML_REGEXP_DECIMAL, /* \d */
XML_REGEXP_NOTDECIMAL, /* \D */
XML_REGEXP_REALCHAR, /* \w */
XML_REGEXP_NOTREALCHAR, /* \W */
XML_REGEXP_LETTER = 100,
typedef enum {
typedef enum {
typedef enum {
typedef struct _xmlRegRange xmlRegRange;
typedef xmlRegRange *xmlRegRangePtr;
struct _xmlRegRange {
int neg; /* 0 normal, 1 not, 2 exclude */
int start;
int end;
};
typedef struct _xmlRegAtom xmlRegAtom;
typedef xmlRegAtom *xmlRegAtomPtr;
typedef struct _xmlAutomataState xmlRegState;
typedef xmlRegState *xmlRegStatePtr;
struct _xmlRegAtom {
int no;
int min;
int max;
void *valuep;
void *valuep2;
int neg;
int codepoint;
int maxRanges;
int nbRanges;
void *data;
};
typedef struct _xmlRegCounter xmlRegCounter;
typedef xmlRegCounter *xmlRegCounterPtr;
struct _xmlRegCounter {
int min;
int max;
};
typedef struct _xmlRegTrans xmlRegTrans;
typedef xmlRegTrans *xmlRegTransPtr;
struct _xmlRegTrans {
int to;
int counter;
int count;
int nd;
};
struct _xmlAutomataState {
int no;
int maxTrans;
int nbTrans;
/* knowing states ponting to us can speed things up */
int maxTransTo;
int nbTransTo;
int *transTo;
};
typedef struct _xmlAutomata xmlRegParserCtxt;
typedef xmlRegParserCtxt *xmlRegParserCtxtPtr;
struct _xmlAutomata {
int error;
int neg;
int maxAtoms;
int nbAtoms;
int maxStates;
int nbStates;
int maxCounters;
int nbCounters;
int determinist;
int negs;
};
struct _xmlRegexp {
int nbStates;
int nbAtoms;
int nbCounters;
int determinist;
/*
* That's the compact form for determinists automatas
*/
int nbstates;
int *compact;
void **transdata;
int nbstrings;
};
typedef struct _xmlRegExecRollback xmlRegExecRollback;
typedef xmlRegExecRollback *xmlRegExecRollbackPtr;
struct _xmlRegExecRollback {
int index; /* the index in the input stack */
int nextbranch; /* the next transition to explore in that state */
int *counts; /* save the automata state if it has some */
};
typedef struct _xmlRegInputToken xmlRegInputToken;
typedef xmlRegInputToken *xmlRegInputTokenPtr;
struct _xmlRegInputToken {
void *data;
};
struct _xmlRegExecCtxt {
int status; /* execution status != 0 indicate an error */
int determinist; /* did we find an indeterministic behaviour */
void *data;
int transno; /* the current transition on that state */
int transcount; /* the number of chars in char counted transitions */
/*
* A stack of rollback states
*/
int maxRollbacks;
int nbRollbacks;
/*
* The state of the automata if any
*/
int *counts;
/*
* The input stack
*/
int inputStackMax;
int inputStackNr;
int index;
int *charStack;
/*
* error handling
*/
int errStateNo; /* the error state number */
int *errCounts; /* counters at the error state */
int nbPush;
};
#define REGEXP_ALL_COUNTER 0x123456
#define REGEXP_ALL_LAX_COUNTER 0x123457
/************************************************************************
* *
* Regexp memory error handler *
* *
************************************************************************/
/**
* xmlRegexpErrMemory:
* @extra: extra information
*
* Handle an out of memory condition
*/
static void
{
}
"Memory allocation failed : %s\n", extra);
}
/**
* xmlRegexpErrCompile:
* @extra: extra information
*
* Handle a compilation failure
*/
static void
{
int idx = 0;
}
"failed to compile: %s\n", extra);
}
/************************************************************************
* *
* *
************************************************************************/
/**
* xmlRegEpxFromParse:
* @ctxt: the parser context used to build it
*
* Allocate a new regexp and fill it with the result from the parser
*
* Returns the new regexp or NULL in case of error
*/
static xmlRegexpPtr
return(NULL);
}
}
if ((ret->determinist != 0) &&
(ret->nbCounters == 0) &&
int *stateRemap;
int *stringRemap;
int *transitions;
void **transdata;
/*
* Switch to a compact representation
* 1/ counting the effective number of states left
* 2/ counting the unique number of atoms, and check that
* they are all of the string type
* 3/ build a table state x atom for the transitions
*/
if (stateRemap == NULL) {
return(NULL);
}
stateRemap[i] = nbstates;
nbstates++;
} else {
stateRemap[i] = -1;
}
}
#ifdef DEBUG_COMPACTION
#endif
return(NULL);
}
if (stringRemap == NULL) {
return(NULL);
}
for (j = 0;j < nbatoms;j++) {
stringRemap[i] = j;
break;
}
}
if (j >= nbatoms) {
stringRemap[i] = nbatoms;
for (i = 0;i < nbatoms;i++)
return(NULL);
}
nbatoms++;
}
} else {
for (i = 0;i < nbatoms;i++)
return(NULL);
}
}
#ifdef DEBUG_COMPACTION
#endif
(nbatoms + 1) * sizeof(int));
if (transitions == NULL) {
return(NULL);
}
/*
* Allocate the transition table. The first entry for each
* state corresponds to the state type.
*/
stateno = stateRemap[i];
if (stateno == -1)
continue;
continue;
sizeof(void *));
else {
break;
}
}
/*
* if the same atom can generate transitions to 2 different
* states then it means the automata is not determinist and
* the compact form can't be used !
*/
if (prev != 0) {
ret->determinist = 0;
#ifdef DEBUG_COMPACTION
printf("Indet: state %d trans %d, atom %d to %d : %d to %d\n",
#endif
for (i = 0;i < nbatoms;i++)
goto not_determ;
}
} else {
#if 0
printf("State %d trans %d: atom %d to %d : %d to %d\n",
#endif
}
}
}
#ifdef DEBUG_COMPACTION
/*
* Debug
*/
for (i = 0;i < nbstates;i++) {
for (j = 0;j < nbatoms + 1;j++) {
}
printf("\n");
}
printf("\n");
#endif
/*
* Cleanup of the old data
*/
}
}
}
ctxt->nbCounters = 0;
return(ret);
}
/**
* xmlRegNewParserCtxt:
* @string: the string to parse
*
* Allocate a new regexp parser context
*
* Returns the new context or NULL in case of error
*/
static xmlRegParserCtxtPtr
return(NULL);
return(ret);
}
/**
* xmlRegNewRange:
* @ctxt: the regexp parser context
* @neg: is that negative
* @type: the type of range
* @start: the start codepoint
* @end: the end codepoint
*
* Allocate a new regexp range
*
* Returns the new range or NULL in case of error
*/
static xmlRegRangePtr
return(NULL);
}
return(ret);
}
/**
* xmlRegFreeRange:
* @range: the regexp range
*
* Free a regexp range
*/
static void
return;
}
/**
* xmlRegCopyRange:
* @range: the regexp range
*
* Copy a regexp range
*
* Returns the new copy or NULL in case of error.
*/
static xmlRegRangePtr
return(NULL);
return(NULL);
return(NULL);
}
}
return(ret);
}
/**
* xmlRegNewAtom:
* @ctxt: the regexp parser context
* @type: the type of atom
*
* Allocate a new atom
*
* Returns the new atom or NULL in case of error
*/
static xmlRegAtomPtr
return(NULL);
}
return(ret);
}
/**
* xmlRegFreeAtom:
* @atom: the regexp atom
*
* Free a regexp atom
*/
static void
int i;
return;
}
/**
* xmlRegCopyAtom:
* @ctxt: the regexp parser context
* @atom: the oiginal atom
*
* Allocate a new regexp range
*
* Returns the new atom or NULL in case of error
*/
static xmlRegAtomPtr
return(NULL);
}
int i;
goto error;
}
goto error;
}
}
return(ret);
return(NULL);
}
static xmlRegStatePtr
return(NULL);
}
return(ret);
}
/**
* xmlRegFreeState:
* @state: the regexp state
*
* Free a regexp state
*/
static void
return;
}
/**
* xmlRegFreeParserCtxt:
* @ctxt: the regexp parser context
*
* Free a regexp parser context
*/
static void
int i;
return;
}
}
}
/************************************************************************
* *
* Display of Data structures *
* *
************************************************************************/
static void
switch (type) {
case XML_REGEXP_EPSILON:
case XML_REGEXP_CHARVAL:
case XML_REGEXP_RANGES:
case XML_REGEXP_SUBREG:
case XML_REGEXP_STRING:
case XML_REGEXP_ANYCHAR:
case XML_REGEXP_ANYSPACE:
case XML_REGEXP_NOTSPACE:
case XML_REGEXP_INITNAME:
case XML_REGEXP_NOTINITNAME:
case XML_REGEXP_NAMECHAR:
case XML_REGEXP_NOTNAMECHAR:
case XML_REGEXP_DECIMAL:
case XML_REGEXP_NOTDECIMAL:
case XML_REGEXP_REALCHAR:
case XML_REGEXP_NOTREALCHAR:
case XML_REGEXP_LETTER:
case XML_REGEXP_LETTER_OTHERS:
case XML_REGEXP_MARK:
case XML_REGEXP_NUMBER:
case XML_REGEXP_NUMBER_LETTER:
case XML_REGEXP_NUMBER_OTHERS:
case XML_REGEXP_PUNCT:
case XML_REGEXP_PUNCT_DASH:
case XML_REGEXP_PUNCT_OPEN:
case XML_REGEXP_PUNCT_CLOSE:
case XML_REGEXP_PUNCT_OTHERS:
case XML_REGEXP_SEPAR:
case XML_REGEXP_SEPAR_SPACE:
case XML_REGEXP_SEPAR_LINE:
case XML_REGEXP_SEPAR_PARA:
case XML_REGEXP_SYMBOL:
case XML_REGEXP_SYMBOL_MATH:
case XML_REGEXP_SYMBOL_OTHERS:
case XML_REGEXP_OTHER:
case XML_REGEXP_OTHER_CONTROL:
case XML_REGEXP_OTHER_FORMAT:
case XML_REGEXP_OTHER_PRIVATE:
case XML_REGEXP_OTHER_NA:
case XML_REGEXP_BLOCK_NAME:
}
}
static void
switch (type) {
case XML_REGEXP_QUANT_EPSILON:
case XML_REGEXP_QUANT_ONCE:
case XML_REGEXP_QUANT_OPT:
case XML_REGEXP_QUANT_MULT:
case XML_REGEXP_QUANT_PLUS:
case XML_REGEXP_QUANT_RANGE:
case XML_REGEXP_QUANT_ALL:
}
}
static void
}
static void
return;
}
int i;
} else {
}
}
static void
return;
}
return;
}
else
}
}
}
return;
}
}
static void
int i;
return;
}
}
}
#ifdef DEBUG_REGEXP_GRAPH
static void
int i;
return;
}
}
}
}
for (i = 0;i < ctxt->nbCounters; i++) {
}
}
#endif
/************************************************************************
* *
* Finite Automata structures manipulations *
* *
************************************************************************/
static void
ERROR("add range: atom is NULL");
return;
}
ERROR("add range: atom is not ranges");
return;
}
sizeof(xmlRegRangePtr));
return;
}
sizeof(xmlRegRangePtr));
return;
}
}
return;
}
static int
if (ctxt->maxCounters == 0) {
sizeof(xmlRegCounter));
ctxt->maxCounters = 0;
return(-1);
}
sizeof(xmlRegCounter));
return(-1);
}
}
return(ctxt->nbCounters++);
}
static int
ERROR("atom push: atom is NULL");
return(-1);
}
sizeof(xmlRegAtomPtr));
return(-1);
}
sizeof(xmlRegAtomPtr));
return(-1);
}
}
return(0);
}
static void
int from) {
if (target->maxTransTo == 0) {
sizeof(int));
target->maxTransTo = 0;
return;
}
int *tmp;
sizeof(int));
return;
}
}
}
static void
int nrtrans;
ERROR("add state: state is NULL");
return;
}
ERROR("add state: target is NULL");
return;
}
/*
* Other routines follow the philosophy 'When in doubt, add a transition'
* so we check here whether such a transition is already present and, if
* so, silently ignore this request.
*/
#ifdef DEBUG_REGEXP_GRAPH
printf("Ignoring duplicate transition from %d to %d\n",
#endif
return;
}
}
sizeof(xmlRegTrans));
return;
}
sizeof(xmlRegTrans));
return;
}
}
#ifdef DEBUG_REGEXP_GRAPH
if (count == REGEXP_ALL_COUNTER)
printf("all transition\n");
else if (count >= 0)
else if (counter >= 0)
printf("epsilon transition\n");
#endif
}
static int
sizeof(xmlRegStatePtr));
return(-1);
}
sizeof(xmlRegStatePtr));
return(-1);
}
}
return(0);
}
/**
* xmlFAGenerateAllTransition:
* @ctxt: a regexp parser context
* @from: the from state
* @to: the target state or NULL for building a new one
* @lax:
*
*/
static void
int lax) {
}
if (lax)
else
}
/**
* xmlFAGenerateEpsilonTransition:
* @ctxt: a regexp parser context
* @from: the from state
* @to: the target state or NULL for building a new one
*
*/
static void
}
}
/**
* xmlFAGenerateCountedEpsilonTransition:
* @ctxt: a regexp parser context
* @from: the from state
* @to: the target state or NULL for building a new one
* counter: the counter for that transition
*
*/
static void
}
}
/**
* xmlFAGenerateCountedTransition:
* @ctxt: a regexp parser context
* @from: the from state
* @to: the target state or NULL for building a new one
* counter: the counter for that transition
*
*/
static void
}
}
/**
* xmlFAGenerateTransitions:
* @ctxt: a regexp parser context
* @from: the from state
* @to: the target state or NULL for building a new one
* @atom: the atom generating the transition
*
* Returns 0 if success and -1 in case of error.
*/
static int
ERROR("genrate transition: atom == NULL");
return(-1);
}
/*
* this is a subexpression handling one should not need to
* create a new node except for XML_REGEXP_QUANT_RANGE.
*/
return(-1);
}
/*
* Generate an epsilon transition to link to the target
*/
#ifdef DV
#endif
}
case XML_REGEXP_QUANT_OPT:
/*
* transition done to the state after end of atom.
* 1. set transition from atom start to new state
* 2. set transition from atom end to this state.
*/
break;
case XML_REGEXP_QUANT_MULT:
break;
case XML_REGEXP_QUANT_PLUS:
break;
case XML_REGEXP_QUANT_RANGE: {
int counter;
/*
* create the final state now if needed
*/
} else {
}
/*
* The principle here is to use counted transition
* to avoid explosion in the number of states in the
* graph. This is clearly more complex but should not
* be exploitable at runtime.
*/
/*
* duplicate a transition based on atom to count next
* occurences after 1. We cannot loop to atom->start
* directly because we need an epsilon transition to
* newstate.
*/
/* ???? For some reason it seems we never reach that
case, I suppose this got optimized out before when
building the automata */
return(-1);
< 0)
return(-1);
/* count the number of times we see it again */
/* allow a way out based on the count */
/* and also allow a direct exit for 0 */
newstate);
} else {
/*
* either we need the atom at least once or there
* is an atom->start0 allowing to easilly plug the
* epsilon transition.
*/
/* count the number of times we see it again */
/* allow a way out based on the count */
/* and if needed allow a direct exit for 0 */
newstate);
}
}
default:
break;
}
return(0);
}
/*
* we can discard the atom and generate an epsilon transition instead
*/
else {
return(-1);
}
}
return(0);
}
else {
return(-1);
}
}
return(-1);
}
case XML_REGEXP_QUANT_OPT:
break;
case XML_REGEXP_QUANT_MULT:
break;
case XML_REGEXP_QUANT_PLUS:
break;
case XML_REGEXP_QUANT_RANGE:
#if DV_test
}
#endif
break;
default:
break;
}
return(0);
}
/**
* xmlFAReduceEpsilonTransitions:
* @ctxt: a regexp parser context
* @fromnr: the from state
* @tonr: the to state
* @counter: should that transition be associated to a counted
*
*/
static void
int transnr;
#ifdef DEBUG_REGEXP_GRAPH
#endif
return;
return;
return;
#ifdef DEBUG_REGEXP_GRAPH
#endif
}
continue;
/*
* Don't remove counted transitions
* Don't loop either
*/
} else {
#ifdef DEBUG_REGEXP_GRAPH
printf("Found epsilon trans %d from %d to %d\n",
#endif
} else {
counter);
}
}
}
} else {
} else {
}
}
}
}
/**
* xmlFAEliminateSimpleEpsilonTransitions:
* @ctxt: a regexp parser context
*
* Eliminating general epsilon transitions can get costly in the general
* algorithm due to the large amount of generated new transitions and
* associated comparisons. However for simple epsilon transition used just
* to separate building blocks when generating the automata this can be
* reduced to state elimination:
* - if there exists an epsilon from X to Y
* - if there is no other transition from X
* then X and Y are semantically equivalent and X can be eliminated
* If X is the start state then make Y the start state, else replace the
* target of all transitions to X by transitions to Y.
*/
static void
continue;
continue;
continue;
/* is the only transition out a basic transition */
#ifdef DEBUG_REGEXP_GRAPH
printf("Found simple epsilon trans from start %d to %d\n",
#endif
} else {
#ifdef DEBUG_REGEXP_GRAPH
printf("Found simple epsilon trans from %d to %d\n",
#endif
#ifdef DEBUG_REGEXP_GRAPH
printf("Changed transition %d on %d to go to %d\n",
#endif
}
}
}
/* eliminate the transition completely */
}
}
}
}
/**
* xmlFAEliminateEpsilonTransitions:
* @ctxt: a regexp parser context
*
*/
static void
int has_epsilon;
/*
* Eliminate simple epsilon transition and the associated unreachable
* states.
*/
#ifdef DEBUG_REGEXP_GRAPH
#endif
}
}
has_epsilon = 0;
/*
* Build the completed transitions bypassing the epsilons
* Use a marking algorithm to avoid loops
* Mark sink states too.
* Process from the latests states backward to the start when
* there is long cascading epsilon chains this minimize the
* recursions and transition compares when adding the new ones
*/
continue;
}
#ifdef DEBUG_REGEXP_GRAPH
printf("Removed loopback epsilon trans %d on %d\n",
#endif
#ifdef DEBUG_REGEXP_GRAPH
printf("Found epsilon trans %d from %d to %d\n",
#endif
has_epsilon = 1;
#ifdef DEBUG_REGEXP_GRAPH
} else {
printf("Found counted transition %d on %d\n",
#endif
}
}
}
}
/*
* Eliminate the epsilon transitions
*/
if (has_epsilon) {
continue;
}
}
}
}
/*
* Use this pass to detect unreachable states too
*/
}
/*
* Mark all states reachable from the current reachable state
*/
continue;
}
}
}
/*
* find the next accessible state not explored
*/
break;
}
}
}
}
#ifdef DEBUG_REGEXP_GRAPH
#endif
}
}
}
static int
int ret = 0;
return(-1);
/* put them in order */
}
ret = 1;
return(0);
ret = 1;
else
ret = 0;
int codepoint;
int neg = 0;
/*
* just check all codepoints in the range for acceptance,
* this is usually way cheaper since done only once at
* compilation than testing over and over at runtime or
* pushing too many states when evaluating.
*/
neg = 1;
if (ret < 0)
return(-1);
return(1);
}
return(0);
} else {
/*
* comparing a block range with anything else is way
* too costly, and maintining the table is like too much
* memory too, so let's force the automata to save state
* here.
*/
return(1);
}
ret = 0;
ret = 0;
ret = 0;
ret = 0;
ret = 0;
else {
/* same thing to limit complexity */
return(1);
}
} else {
ret = 0;
/* range1->type < range2->type here */
case XML_REGEXP_LETTER:
/* all disjoint except in the subgroups */
ret = 1;
break;
case XML_REGEXP_MARK:
ret = 1;
break;
case XML_REGEXP_NUMBER:
ret = 1;
break;
case XML_REGEXP_PUNCT:
ret = 1;
break;
case XML_REGEXP_SEPAR:
ret = 1;
break;
case XML_REGEXP_SYMBOL:
ret = 1;
break;
case XML_REGEXP_OTHER:
ret = 1;
break;
default:
ret = 0;
else {
/* safety net ! */
return(1);
}
}
}
return(1);
}
/**
* xmlFACompareAtomTypes:
* @type1: an atom type
* @type2: an atom type
*
* Compares two atoms type to check whether they intersect in some ways,
* this is used by xmlFACompareAtoms only
*
* Returns 1 if they may intersect and 0 otherwise
*/
static int
if ((type1 == XML_REGEXP_EPSILON) ||
(type1 == XML_REGEXP_CHARVAL) ||
(type1 == XML_REGEXP_RANGES) ||
(type1 == XML_REGEXP_SUBREG) ||
(type1 == XML_REGEXP_STRING) ||
(type1 == XML_REGEXP_ANYCHAR))
return(1);
if ((type2 == XML_REGEXP_EPSILON) ||
(type2 == XML_REGEXP_CHARVAL) ||
(type2 == XML_REGEXP_RANGES) ||
(type2 == XML_REGEXP_SUBREG) ||
(type2 == XML_REGEXP_STRING) ||
(type2 == XML_REGEXP_ANYCHAR))
return(1);
/* simplify subsequent compares by making sure type1 < type2 */
}
switch (type1) {
case XML_REGEXP_ANYSPACE: /* \s */
/* can't be a letter, number, mark, pontuation, symbol */
if ((type2 == XML_REGEXP_NOTSPACE) ||
((type2 >= XML_REGEXP_LETTER) &&
(type2 <= XML_REGEXP_LETTER_OTHERS)) ||
((type2 >= XML_REGEXP_NUMBER) &&
(type2 <= XML_REGEXP_NUMBER_OTHERS)) ||
((type2 >= XML_REGEXP_MARK) &&
(type2 <= XML_REGEXP_MARK_ENCLOSING)) ||
((type2 >= XML_REGEXP_PUNCT) &&
(type2 <= XML_REGEXP_PUNCT_OTHERS)) ||
((type2 >= XML_REGEXP_SYMBOL) &&
) return(0);
break;
case XML_REGEXP_NOTSPACE: /* \S */
break;
case XML_REGEXP_INITNAME: /* \l */
/* can't be a number, mark, separator, pontuation, symbol or other */
if ((type2 == XML_REGEXP_NOTINITNAME) ||
((type2 >= XML_REGEXP_NUMBER) &&
(type2 <= XML_REGEXP_NUMBER_OTHERS)) ||
((type2 >= XML_REGEXP_MARK) &&
(type2 <= XML_REGEXP_MARK_ENCLOSING)) ||
((type2 >= XML_REGEXP_SEPAR) &&
(type2 <= XML_REGEXP_SEPAR_PARA)) ||
((type2 >= XML_REGEXP_PUNCT) &&
(type2 <= XML_REGEXP_PUNCT_OTHERS)) ||
((type2 >= XML_REGEXP_SYMBOL) &&
(type2 <= XML_REGEXP_SYMBOL_OTHERS)) ||
((type2 >= XML_REGEXP_OTHER) &&
(type2 <= XML_REGEXP_OTHER_NA))
) return(0);
break;
case XML_REGEXP_NOTINITNAME: /* \L */
break;
case XML_REGEXP_NAMECHAR: /* \c */
/* can't be a mark, separator, pontuation, symbol or other */
if ((type2 == XML_REGEXP_NOTNAMECHAR) ||
((type2 >= XML_REGEXP_MARK) &&
(type2 <= XML_REGEXP_MARK_ENCLOSING)) ||
((type2 >= XML_REGEXP_PUNCT) &&
(type2 <= XML_REGEXP_PUNCT_OTHERS)) ||
((type2 >= XML_REGEXP_SEPAR) &&
(type2 <= XML_REGEXP_SEPAR_PARA)) ||
((type2 >= XML_REGEXP_SYMBOL) &&
(type2 <= XML_REGEXP_SYMBOL_OTHERS)) ||
((type2 >= XML_REGEXP_OTHER) &&
(type2 <= XML_REGEXP_OTHER_NA))
) return(0);
break;
case XML_REGEXP_NOTNAMECHAR: /* \C */
break;
case XML_REGEXP_DECIMAL: /* \d */
/* can't be a letter, mark, separator, pontuation, symbol or other */
if ((type2 == XML_REGEXP_NOTDECIMAL) ||
(type2 == XML_REGEXP_REALCHAR) ||
((type2 >= XML_REGEXP_LETTER) &&
(type2 <= XML_REGEXP_LETTER_OTHERS)) ||
((type2 >= XML_REGEXP_MARK) &&
(type2 <= XML_REGEXP_MARK_ENCLOSING)) ||
((type2 >= XML_REGEXP_PUNCT) &&
(type2 <= XML_REGEXP_PUNCT_OTHERS)) ||
((type2 >= XML_REGEXP_SEPAR) &&
(type2 <= XML_REGEXP_SEPAR_PARA)) ||
((type2 >= XML_REGEXP_SYMBOL) &&
(type2 <= XML_REGEXP_SYMBOL_OTHERS)) ||
((type2 >= XML_REGEXP_OTHER) &&
(type2 <= XML_REGEXP_OTHER_NA))
)return(0);
break;
case XML_REGEXP_NOTDECIMAL: /* \D */
break;
case XML_REGEXP_REALCHAR: /* \w */
/* can't be a mark, separator, pontuation, symbol or other */
if ((type2 == XML_REGEXP_NOTDECIMAL) ||
((type2 >= XML_REGEXP_MARK) &&
(type2 <= XML_REGEXP_MARK_ENCLOSING)) ||
((type2 >= XML_REGEXP_PUNCT) &&
(type2 <= XML_REGEXP_PUNCT_OTHERS)) ||
((type2 >= XML_REGEXP_SEPAR) &&
(type2 <= XML_REGEXP_SEPAR_PARA)) ||
((type2 >= XML_REGEXP_SYMBOL) &&
(type2 <= XML_REGEXP_SYMBOL_OTHERS)) ||
((type2 >= XML_REGEXP_OTHER) &&
(type2 <= XML_REGEXP_OTHER_NA))
)return(0);
break;
case XML_REGEXP_NOTREALCHAR: /* \W */
break;
/*
* at that point we know both type 1 and type2 are from
* character categories are ordered and are different,
* it becomes simple because this is a partition
*/
case XML_REGEXP_LETTER:
if (type2 <= XML_REGEXP_LETTER_OTHERS)
return(1);
return(0);
case XML_REGEXP_LETTER_OTHERS:
return(0);
case XML_REGEXP_MARK:
if (type2 <= XML_REGEXP_MARK_ENCLOSING)
return(1);
return(0);
return(0);
case XML_REGEXP_NUMBER:
if (type2 <= XML_REGEXP_NUMBER_OTHERS)
return(1);
return(0);
case XML_REGEXP_NUMBER_LETTER:
case XML_REGEXP_NUMBER_OTHERS:
return(0);
case XML_REGEXP_PUNCT:
if (type2 <= XML_REGEXP_PUNCT_OTHERS)
return(1);
return(0);
case XML_REGEXP_PUNCT_DASH:
case XML_REGEXP_PUNCT_OPEN:
case XML_REGEXP_PUNCT_CLOSE:
case XML_REGEXP_PUNCT_OTHERS:
return(0);
case XML_REGEXP_SEPAR:
if (type2 <= XML_REGEXP_SEPAR_PARA)
return(1);
return(0);
case XML_REGEXP_SEPAR_SPACE:
case XML_REGEXP_SEPAR_LINE:
case XML_REGEXP_SEPAR_PARA:
return(0);
case XML_REGEXP_SYMBOL:
if (type2 <= XML_REGEXP_SYMBOL_OTHERS)
return(1);
return(0);
case XML_REGEXP_SYMBOL_MATH:
case XML_REGEXP_SYMBOL_OTHERS:
return(0);
case XML_REGEXP_OTHER:
if (type2 <= XML_REGEXP_OTHER_NA)
return(1);
return(0);
case XML_REGEXP_OTHER_CONTROL:
case XML_REGEXP_OTHER_FORMAT:
case XML_REGEXP_OTHER_PRIVATE:
case XML_REGEXP_OTHER_NA:
return(0);
default:
break;
}
return(1);
}
/**
* xmlFAEqualAtoms:
* @atom1: an atom
* @atom2: an atom
*
* Compares two atoms to check whether they are the same exactly
* this is used to remove equivalent transitions
*
* Returns 1 if same and 0 otherwise
*/
static int
int ret = 0;
return(1);
return(0);
return(0);
case XML_REGEXP_EPSILON:
ret = 0;
break;
case XML_REGEXP_STRING:
break;
case XML_REGEXP_CHARVAL:
break;
case XML_REGEXP_RANGES:
/* too hard to do in the general case */
ret = 0;
default:
break;
}
return(ret);
}
/**
* xmlFACompareAtoms:
* @atom1: an atom
* @atom2: an atom
*
* Compares two atoms to check whether they intersect in some ways,
* this is used by xmlFAComputesDeterminism and xmlFARecurseDeterminism only
*
* Returns 1 if yes and 0 otherwise
*/
static int
int ret = 1;
return(1);
return(0);
return(1);
}
/* if they can't intersect at the type level break now */
if (ret == 0)
return(0);
}
case XML_REGEXP_STRING:
break;
case XML_REGEXP_EPSILON:
goto not_determinist;
case XML_REGEXP_CHARVAL:
} else {
if (ret < 0)
ret = 1;
}
break;
case XML_REGEXP_RANGES:
int i, j, res;
/*
* need to check that none of the ranges eventually matches
*/
if (res == 1) {
ret = 1;
goto done;
}
}
}
ret = 0;
}
break;
default:
goto not_determinist;
}
done:
}
if (ret == 0)
return(0);
return(1);
}
/**
* xmlFARecurseDeterminism:
* @ctxt: a regexp parser context
*
* Check whether the associated regexp is determinist,
* should be called after xmlFAEliminateEpsilonTransitions()
*
*/
static int
int ret = 1;
int res;
return(ret);
/*
* don't recurse on transitions potentially added in the course of
* the elimination.
*/
/*
* check transitions conflicting with the one looked at
*/
continue;
if (res == 0) {
ret = 0;
/* t1->nd = 1; */
}
continue;
}
continue;
ret = 0;
/* mark the transition as non-deterministic */
}
}
return(ret);
}
/**
* xmlFAComputesDeterminism:
* @ctxt: a regexp parser context
*
* Check whether the associated regexp is determinist,
* should be called after xmlFAEliminateEpsilonTransitions()
*
*/
static int
int i;
int ret = 1;
#ifdef DEBUG_REGEXP_GRAPH
printf("xmlFAComputesDeterminism\n");
#endif
return(ctxt->determinist);
/*
* First cleanup the automata removing cancelled transitions
*/
continue;
continue;
/*
* Determinism checks in case of counted or all transitions
* will have to be handled separately
*/
/* t1->nd = 1; */
continue;
}
continue;
for (i = 0;i < transnr;i++) {
continue;
}
}
}
}
}
/*
* Check for all states that there aren't 2 transitions
* with the same atom and a different target.
*/
continue;
continue;
/*
* Determinism checks in case of counted or all transitions
* will have to be handled separately
*/
continue;
}
continue;
for (i = 0;i < transnr;i++) {
continue;
/* not determinist ! */
ret = 0;
/* mark the transitions as non-deterministic ones */
}
/*
* do the closure in case of remaining specific
* epsilon transitions like choices or all
*/
/* don't shortcut the computation so all non deterministic
transition get marked down
if (ret == 0)
return(0);
*/
if (ret == 0) {
/* t2->nd = 1; */
}
}
}
/* don't shortcut the computation so all non deterministic
transition get marked down
if (ret == 0)
break; */
}
/*
* mark specifically the last non-deterministic transition
* from a state since there is no need to set-up rollback
* from it
*/
}
/* don't shortcut the computation so all non deterministic
transition get marked down
if (ret == 0)
break; */
}
return(ret);
}
/************************************************************************
* *
* Routines to check input against transition atoms *
* *
************************************************************************/
static int
int ret = 0;
switch (type) {
case XML_REGEXP_STRING:
case XML_REGEXP_SUBREG:
case XML_REGEXP_RANGES:
case XML_REGEXP_EPSILON:
return(-1);
case XML_REGEXP_ANYCHAR:
break;
case XML_REGEXP_CHARVAL:
break;
case XML_REGEXP_NOTSPACE:
case XML_REGEXP_ANYSPACE:
break;
case XML_REGEXP_NOTINITNAME:
case XML_REGEXP_INITNAME:
break;
case XML_REGEXP_NOTNAMECHAR:
case XML_REGEXP_NAMECHAR:
break;
case XML_REGEXP_NOTDECIMAL:
case XML_REGEXP_DECIMAL:
break;
case XML_REGEXP_REALCHAR:
case XML_REGEXP_NOTREALCHAR:
if (ret == 0)
if (ret == 0)
break;
case XML_REGEXP_LETTER:
break;
break;
break;
break;
break;
case XML_REGEXP_LETTER_OTHERS:
break;
case XML_REGEXP_MARK:
break;
break;
break;
break;
case XML_REGEXP_NUMBER:
break;
break;
case XML_REGEXP_NUMBER_LETTER:
break;
case XML_REGEXP_NUMBER_OTHERS:
break;
case XML_REGEXP_PUNCT:
break;
break;
case XML_REGEXP_PUNCT_DASH:
break;
case XML_REGEXP_PUNCT_OPEN:
break;
case XML_REGEXP_PUNCT_CLOSE:
break;
break;
break;
case XML_REGEXP_PUNCT_OTHERS:
break;
case XML_REGEXP_SEPAR:
break;
case XML_REGEXP_SEPAR_SPACE:
break;
case XML_REGEXP_SEPAR_LINE:
break;
case XML_REGEXP_SEPAR_PARA:
break;
case XML_REGEXP_SYMBOL:
break;
case XML_REGEXP_SYMBOL_MATH:
break;
break;
break;
case XML_REGEXP_SYMBOL_OTHERS:
break;
case XML_REGEXP_OTHER:
break;
case XML_REGEXP_OTHER_CONTROL:
break;
case XML_REGEXP_OTHER_FORMAT:
break;
case XML_REGEXP_OTHER_PRIVATE:
break;
case XML_REGEXP_OTHER_NA:
/* ret = xmlUCSIsCatCn(codepoint); */
/* Seems it doesn't exist anymore in recent Unicode releases */
ret = 0;
break;
case XML_REGEXP_BLOCK_NAME:
break;
}
if (neg)
return(!ret);
return(ret);
}
static int
int i, ret = 0;
return(-1);
case XML_REGEXP_SUBREG:
case XML_REGEXP_EPSILON:
return(-1);
case XML_REGEXP_CHARVAL:
case XML_REGEXP_RANGES: {
int accept = 0;
if (ret != 0)
return(0); /* excluded char */
if (ret == 0)
accept = 1;
else
return(0);
} else {
if (ret != 0)
}
}
return(accept);
}
case XML_REGEXP_STRING:
printf("TODO: XML_REGEXP_STRING\n");
return(-1);
case XML_REGEXP_ANYCHAR:
case XML_REGEXP_ANYSPACE:
case XML_REGEXP_NOTSPACE:
case XML_REGEXP_INITNAME:
case XML_REGEXP_NOTINITNAME:
case XML_REGEXP_NAMECHAR:
case XML_REGEXP_NOTNAMECHAR:
case XML_REGEXP_DECIMAL:
case XML_REGEXP_NOTDECIMAL:
case XML_REGEXP_REALCHAR:
case XML_REGEXP_NOTREALCHAR:
case XML_REGEXP_LETTER:
case XML_REGEXP_LETTER_OTHERS:
case XML_REGEXP_MARK:
case XML_REGEXP_NUMBER:
case XML_REGEXP_NUMBER_LETTER:
case XML_REGEXP_NUMBER_OTHERS:
case XML_REGEXP_PUNCT:
case XML_REGEXP_PUNCT_DASH:
case XML_REGEXP_PUNCT_OPEN:
case XML_REGEXP_PUNCT_CLOSE:
case XML_REGEXP_PUNCT_OTHERS:
case XML_REGEXP_SEPAR:
case XML_REGEXP_SEPAR_SPACE:
case XML_REGEXP_SEPAR_LINE:
case XML_REGEXP_SEPAR_PARA:
case XML_REGEXP_SYMBOL:
case XML_REGEXP_SYMBOL_MATH:
case XML_REGEXP_SYMBOL_OTHERS:
case XML_REGEXP_OTHER:
case XML_REGEXP_OTHER_CONTROL:
case XML_REGEXP_OTHER_FORMAT:
case XML_REGEXP_OTHER_PRIVATE:
case XML_REGEXP_OTHER_NA:
case XML_REGEXP_BLOCK_NAME:
break;
}
return(ret);
}
/************************************************************************
* *
* Saving and restoring state of an execution context *
* *
************************************************************************/
#ifdef DEBUG_REGEXP_EXEC
static void
int i;
printf(": ");
printf("%s ", (const char *)
} else {
}
printf("\n");
}
#endif
static void
#ifdef DEBUG_REGEXP_EXEC
printf("saving ");
#endif
#ifdef MAX_PUSH
return;
}
#endif
if (exec->maxRollbacks == 0) {
sizeof(xmlRegExecRollback));
exec->maxRollbacks = 0;
return;
}
return;
}
}
return;
}
}
}
exec->nbRollbacks++;
}
static void
if (exec->nbRollbacks <= 0) {
#ifdef DEBUG_REGEXP_EXEC
printf("rollback failed on empty stack\n");
#endif
return;
}
exec->nbRollbacks--;
return;
}
}
#ifdef DEBUG_REGEXP_EXEC
printf("restored ");
#endif
}
/************************************************************************
* *
* Verifier, running an input against a compiled regexp *
* *
************************************************************************/
static int
exec->maxRollbacks = 0;
exec->nbRollbacks = 0;
exec->transcount = 0;
exec->inputStackMax = 0;
if (comp->nbCounters > 0) {
return(-1);
}
} else
/*
* If end of input on non-terminal state, rollback, however we may
* still have epsilon like transition for counted transitions
* on counters, in that case don't break too early. Additionally,
* if we are working on a range like "AB{0,2}", where B is not present,
* we don't want to break.
*/
len = 1;
/*
* if there is a transition, we must check if
* atom allows minOccurs of 0
*/
goto rollback;
}
} else
goto rollback;
}
exec->transcount = 0;
continue;
ret = 0;
deter = 1;
int count;
goto error;
}
/*
* A counted transition.
*/
#ifdef DEBUG_REGEXP_EXEC
printf("testing count %d: val %d, min %d, max %d\n",
#endif
deter = 0;
break;
/*
* this is a multiple input sequence
* If there is a counter associated increment it now.
* before potentially saving and rollback
* do not increment if the counter is already over the
* maximum limit in which case get to next transition
*/
goto error;
}
continue; /* for loop on transitions */
#ifdef DEBUG_REGEXP_EXEC
#endif
}
}
do {
/*
* Try to progress as much as possible on the input
*/
break;
}
/*
* End of input: stop here
*/
break;
}
/*
* The transition is acceptable save it
*/
}
len);
exec->transcount++;
} while (ret == 1);
ret = 0;
/*
* If the last check failed but one transition was found
* possible, rollback
*/
if (ret < 0)
ret = 0;
if (ret == 0) {
goto rollback;
}
goto error;
}
#ifdef DEBUG_REGEXP_EXEC
#endif
}
/*
* we don't match on the codepoint, but minOccurs of 0
* says that's ok. Setting len to 0 inhibits stepping
* over the codepoint.
*/
len = 0;
ret = 1;
}
/* another spot to match when minOccurs is 0 */
len = 0;
ret = 1;
}
if (ret == 1) {
#ifdef DEBUG_REGEXP_EXEC
printf("Saving on nd transition atom %d for %c at %d\n",
else
printf("Saving on counted transition count %d for %c at %d\n",
#endif
}
/* make sure we don't go over the counter maximum value */
goto error;
}
continue; /* for loop on transitions */
#ifdef DEBUG_REGEXP_EXEC
#endif
}
goto error;
}
#ifdef DEBUG_REGEXP_EXEC
printf("resetting count %d on transition\n",
#endif
}
#ifdef DEBUG_REGEXP_EXEC
#endif
}
goto progress;
} else if (ret < 0) {
break;
}
}
/*
* Failed to find a way out
*/
exec->determinist = 0;
#ifdef DEBUG_REGEXP_EXEC
#endif
}
continue;
}
int i;
for (i = 0;i < exec->maxRollbacks;i++)
}
}
return(1);
return(-1);
return(0);
}
}
/************************************************************************
* *
* Progressive interface to the verifier one atom at a time *
* *
************************************************************************/
#ifdef DEBUG_ERR
#endif
/**
* xmlRegNewExecCtxt:
* @comp: a precompiled regular expression
* @callback: a callback function used for handling progresses in the
* automata matching phase
* @data: the context data associated to the callback in this context
*
* Build a context used for progressive evaluation of a regexp.
*
* Returns the new context
*/
return(NULL);
return(NULL);
return(NULL);
}
exec->maxRollbacks = 0;
exec->nbRollbacks = 0;
exec->transcount = 0;
if (comp->nbCounters > 0) {
/*
* For error handling, exec->counts is allocated twice the size
* the second half is used to store the data in case of rollback
*/
* 2);
return(NULL);
}
} else {
}
exec->inputStackMax = 0;
exec->inputStackNr = 0;
return(exec);
}
/**
* xmlRegFreeExecCtxt:
* @exec: a regular expression evaulation context
*
* Free the structures associated to a regular expression evaulation context.
*/
void
return;
int i;
for (i = 0;i < exec->maxRollbacks;i++)
}
}
int i;
for (i = 0;i < exec->inputStackNr;i++) {
}
}
}
static void
void *data) {
#ifdef DEBUG_PUSH
#endif
if (exec->inputStackMax == 0) {
exec->inputStackMax = 0;
return;
}
return;
}
}
exec->inputStackNr++;
}
/**
* xmlRegStrEqualWildcard:
* @expStr: the string to be evaluated
* @valStr: the validation string
*
* Checks if both strings are equal or have the same content. "*"
* can be used as a wildcard in @valStr; "|" is used as a seperator of
* substrings in both @expStr and @valStr.
*
* Returns 1 if the comparison is satisfied and the number of substrings
* is equal, 0 otherwise.
*/
static int
do {
/*
* Eval if we have a wildcard for the current item.
*/
/* if one of them starts with a wildcard make valStr be it */
if (*valStr == '*') {
}
do {
if (*valStr == XML_REG_STRING_SEPARATOR)
break;
valStr++;
} while (*valStr != 0);
continue;
} else
return(0);
}
expStr++;
valStr++;
} while (*valStr != 0);
if (*expStr != 0)
return (0);
else
return (1);
}
/**
* xmlRegCompactPushString:
* @exec: a regexp execution context
* @comp: the precompiled exec with a compact table
* @value: a string token input
* @data: data associated to the token to reuse in callbacks
*
* Push one input token in the execution context
*
* Returns: 1 if the regexp reached a final state, 0 if non-final, and
* a negative value in case of error.
*/
static int
void *data) {
int i, target;
return(-1);
/*
* are we at a final state ?
*/
return(1);
return(0);
}
#ifdef DEBUG_PUSH
#endif
/*
* Examine all outside transitions from current state
*/
target--; /* to avoid 0 */
}
#ifdef DEBUG_PUSH
#endif
goto error;
return(1);
return(0);
}
}
}
/*
* Failed to find an exit transition out from current state for the
* current token
*/
#ifdef DEBUG_PUSH
#endif
#ifdef DEBUG_ERR
#endif
return(-1);
}
/**
* xmlRegExecPushStringInternal:
* @exec: a regexp execution context or NULL to indicate the end
* @value: a string token input
* @data: data associated to the token to reuse in callbacks
* @compound: value was assembled from 2 strings
*
* Push one input token in the execution context
*
* Returns: 1 if the regexp reached a final state, 0 if non-final, and
* a negative value in case of error.
*/
static int
int ret;
int final = 0;
int progress = 1;
return(-1);
return(-1);
return(1);
final = 1;
}
#ifdef DEBUG_PUSH
#endif
/*
* If we have an active rollback stack push the new value there
* and get back to where we were left
*/
#ifdef DEBUG_PUSH
#endif
}
((final == 1) &&
/*
* End of input on non-terminal state, rollback, however we may
* still have epsilon like transition for counted transitions
* on counters, in that case don't break too early.
*/
goto rollback;
exec->transcount = 0;
continue;
ret = 0;
int i;
int count;
ret = 0;
#ifdef DEBUG_PUSH
#endif
/*
* Check all counted transitions from the current state
*/
ret = 1;
continue;
ret = 0;
break;
}
ret = 1;
break;
}
}
}
int i;
int count;
ret = 1;
#ifdef DEBUG_PUSH
#endif
/*
* Check all counted transitions from the current state
*/
continue;
ret = 0;
break;
}
}
int count;
/*
* A counted transition.
*/
#ifdef DEBUG_PUSH
printf("testing count %d: val %d, min %d, max %d\n",
#endif
break;
if (!compound)
ret = 0;
}
int count;
ret = 0;
}
/*
* this is a multiple input sequence
*/
if (exec->inputStackNr <= 0) {
}
}
do {
/*
* Try to progress as much as possible on the input
*/
break;
}
#ifdef DEBUG_PUSH
#endif
/*
* End of input: stop here
*/
break;
}
/*
* The transition is acceptable save it
*/
if (exec->inputStackNr <= 0) {
}
}
exec->transcount++;
} while (ret == 1);
ret = 0;
/*
* If the last check failed but one transition was found
* possible, rollback
*/
if (ret < 0)
ret = 0;
if (ret == 0) {
goto rollback;
}
}
}
if (ret == 1) {
}
if (exec->inputStackNr <= 0) {
}
}
#ifdef DEBUG_PUSH
#endif
}
#ifdef DEBUG_REGEXP_EXEC
printf("resetting count %d on transition\n",
#endif
}
#ifdef DEBUG_PUSH
#endif
/*
* entering a sink state, save the current state as error
* state.
*/
}
#ifdef DEBUG_PUSH
#endif
} else {
#ifdef DEBUG_PUSH
printf("end of input\n");
#endif
}
} else {
#ifdef DEBUG_PUSH
printf("end of input\n");
#endif
}
}
goto progress;
} else if (ret < 0) {
break;
}
}
/*
* if we didn't yet rollback on the current input
* store the current state as the error state.
*/
progress = 0;
}
/*
* Failed to find a way out
*/
exec->determinist = 0;
#ifdef DEBUG_PUSH
#endif
}
}
continue;
progress = 1;
continue;
}
}
#ifdef DEBUG_ERR
}
#endif
}
/**
* xmlRegExecPushString:
* @exec: a regexp execution context or NULL to indicate the end
* @value: a string token input
* @data: data associated to the token to reuse in callbacks
*
* Push one input token in the execution context
*
* Returns: 1 if the regexp reached a final state, 0 if non-final, and
* a negative value in case of error.
*/
int
void *data) {
}
/**
* xmlRegExecPushString2:
* @exec: a regexp execution context or NULL to indicate the end
* @value: the first string token input
* @value2: the second string token input
* @data: data associated to the token to reuse in callbacks
*
* Push one input token in the execution context
*
* Returns: 1 if the regexp reached a final state, 0 if non-final, and
* a negative value in case of error.
*/
int
return(-1);
return(-1);
return(-1);
}
} else {
}
else
return(ret);
}
/**
* xmlRegExecGetValues:
* @exec: a regexp execution context
* @err: error extraction or normal one
* @nbneg: return number of negative transitions
* @values: pointer to the array of acceptable values
* @terminal: return value if this was a terminal state
*
* Extract informations from the regexp execution, internal routine to
* implement xmlRegExecNextValues() and xmlRegExecErrInfo()
*
* Returns: 0 in case of success or -1 in case of error.
*/
static int
int maxval;
int nb = 0;
return(-1);
*nbval = 0;
*nbneg = 0;
if (err) {
} else {
}
*terminal = 1;
else
*terminal = 0;
}
(*nbval)++;
}
}
(*nbneg)++;
}
}
} else {
int transno;
*terminal = 1;
else
*terminal = 0;
}
if (err) {
} else {
}
for (transno = 0;
transno++) {
continue;
continue;
/* this should not be reached but ... */
TODO;
/* this should not be reached but ... */
TODO;
int count;
if (err)
else
else
(*nbval)++;
}
} else {
else
(*nbval)++;
}
}
}
for (transno = 0;
transno++) {
continue;
continue;
continue;
continue;
continue;
} else {
else
(*nbneg)++;
}
}
}
}
return(0);
}
/**
* xmlRegExecNextValues:
* @exec: a regexp execution context
* @nbneg: return number of negative transitions
* @values: pointer to the array of acceptable values
* @terminal: return value if this was a terminal state
*
* Extract informations from the regexp execution,
* the parameter @values must point to an array of @nbval string pointers
* on return nbval will contain the number of possible strings in that
* state and the @values array will be updated with them. The string values
* returned will be freed with the @exec context and don't need to be
* deallocated.
*
* Returns: 0 in case of success or -1 in case of error.
*/
int
}
/**
* xmlRegExecErrInfo:
* @exec: a regexp execution context generating an error
* @string: return value for the error string
* @nbneg: return number of negative transitions
* @values: pointer to the array of acceptable values
* @terminal: return value if this was a terminal state
*
* Extract error informations from the regexp execution, the parameter
* @string will be updated with the value pushed and not accepted,
* the parameter @values must point to an array of @nbval string pointers
* on return nbval will contain the number of possible strings in that
* state and the @values array will be updated with them. The string values
* returned will be freed with the @exec context and don't need to be
* deallocated.
*
* Returns: 0 in case of success or -1 in case of error.
*/
int
return(-1);
else
}
}
#ifdef DEBUG_ERR
int nb = 5;
int nbneg;
int terminal;
}
#endif
#if 0
static int
int ret;
return(-1);
/*
* End of input on non-terminal state, rollback, however we may
* still have epsilon like transition for counted transitions
* on counters, in that case don't break too early.
*/
goto rollback;
exec->transcount = 0;
continue;
ret = 0;
int count;
/*
* A counted transition.
*/
#ifdef DEBUG_REGEXP_EXEC
printf("testing count %d: val %d, min %d, max %d\n",
#endif
break;
/*
* this is a multiple input sequence
*/
}
do {
/*
* Try to progress as much as possible on the input
*/
break;
}
/*
* End of input: stop here
*/
break;
}
/*
* The transition is acceptable save it
*/
}
len);
exec->transcount++;
} while (ret == 1);
ret = 0;
/*
* If the last check failed but one transition was found
* possible, rollback
*/
if (ret < 0)
ret = 0;
if (ret == 0) {
goto rollback;
}
}
}
if (ret == 1) {
}
/*
* restart count for expressions like this ((abc){2})*
*/
#ifdef DEBUG_REGEXP_EXEC
#endif
}
#ifdef DEBUG_REGEXP_EXEC
#endif
}
#ifdef DEBUG_REGEXP_EXEC
#endif
}
goto progress;
} else if (ret < 0) {
break;
}
}
/*
* Failed to find a way out
*/
exec->determinist = 0;
}
continue;
}
}
#endif
/************************************************************************
* *
* Parser for the Schemas Datatype Regular Expressions *
* *
************************************************************************/
/**
* xmlFAIsChar:
* @ctxt: a regexp parser context
*
* [10] Char ::= [^.\?*+()|#x5B#x5D]
*/
static int
int cur;
int len;
return(-1);
return(cur);
}
/**
* xmlFAParseCharProp:
* @ctxt: a regexp parser context
*
* [27] charProp ::= IsCategory | IsBlock
* [28] IsCategory ::= Letters | Marks | Numbers | Punctuation |
* Separators | Symbols | Others
* [29] Letters ::= 'L' [ultmo]?
* [30] Marks ::= 'M' [nce]?
* [31] Numbers ::= 'N' [dlo]?
* [32] Punctuation ::= 'P' [cdseifo]?
* [33] Separators ::= 'Z' [slp]?
* [34] Symbols ::= 'S' [mcko]?
* [35] Others ::= 'C' [cfon]?
* [36] IsBlock ::= 'Is' [a-zA-Z0-9#x2D]+
*/
static void
int cur;
if (cur == 'L') {
NEXT;
if (cur == 'u') {
NEXT;
} else if (cur == 'l') {
NEXT;
} else if (cur == 't') {
NEXT;
} else if (cur == 'm') {
NEXT;
} else if (cur == 'o') {
NEXT;
} else {
}
} else if (cur == 'M') {
NEXT;
if (cur == 'n') {
NEXT;
/* nonspacing */
} else if (cur == 'c') {
NEXT;
/* spacing combining */
} else if (cur == 'e') {
NEXT;
/* enclosing */
} else {
/* all marks */
}
} else if (cur == 'N') {
NEXT;
if (cur == 'd') {
NEXT;
/* digital */
} else if (cur == 'l') {
NEXT;
/* letter */
} else if (cur == 'o') {
NEXT;
/* other */
} else {
/* all numbers */
}
} else if (cur == 'P') {
NEXT;
if (cur == 'c') {
NEXT;
/* connector */
} else if (cur == 'd') {
NEXT;
/* dash */
} else if (cur == 's') {
NEXT;
/* open */
} else if (cur == 'e') {
NEXT;
/* close */
} else if (cur == 'i') {
NEXT;
/* initial quote */
} else if (cur == 'f') {
NEXT;
/* final quote */
} else if (cur == 'o') {
NEXT;
/* other */
} else {
/* all punctuation */
}
} else if (cur == 'Z') {
NEXT;
if (cur == 's') {
NEXT;
/* space */
} else if (cur == 'l') {
NEXT;
/* line */
} else if (cur == 'p') {
NEXT;
/* paragraph */
} else {
/* all separators */
}
} else if (cur == 'S') {
NEXT;
if (cur == 'm') {
NEXT;
/* math */
} else if (cur == 'c') {
NEXT;
/* currency */
} else if (cur == 'k') {
NEXT;
/* modifiers */
} else if (cur == 'o') {
NEXT;
/* other */
} else {
/* all symbols */
}
} else if (cur == 'C') {
NEXT;
if (cur == 'c') {
NEXT;
/* control */
} else if (cur == 'f') {
NEXT;
/* format */
} else if (cur == 'o') {
NEXT;
/* private use */
} else if (cur == 'n') {
NEXT;
/* not assigned */
} else {
/* all others */
}
} else if (cur == 'I') {
NEXT;
if (cur != 's') {
ERROR("IsXXXX expected");
return;
}
NEXT;
(cur == 0x2D)) {
NEXT;
(cur == 0x2D)) {
NEXT;
}
}
} else {
ERROR("Unknown char property");
return;
}
}
}
/**
* xmlFAParseCharClassEsc:
* @ctxt: a regexp parser context
*
* [23] charClassEsc ::= ( SingleCharEsc | MultiCharEsc | catEsc | complEsc )
* [24] SingleCharEsc ::= '\' [nrt\|.?*+(){}#x2D#x5B#x5D#x5E]
* [25] catEsc ::= '\p{' charProp '}'
* [26] complEsc ::= '\P{' charProp '}'
* [37] MultiCharEsc ::= '.' | ('\' [sSiIcCdDwW])
*/
static void
int cur;
if (CUR == '.') {
XML_REGEXP_ANYCHAR, 0, 0, NULL);
}
NEXT;
return;
}
if (CUR != '\\') {
ERROR("Escaped sequence: expecting \\");
return;
}
NEXT;
if (cur == 'p') {
NEXT;
if (CUR != '{') {
ERROR("Expecting '{'");
return;
}
NEXT;
if (CUR != '}') {
ERROR("Expecting '}'");
return;
}
NEXT;
} else if (cur == 'P') {
NEXT;
if (CUR != '{') {
ERROR("Expecting '{'");
return;
}
NEXT;
if (CUR != '}') {
ERROR("Expecting '}'");
return;
}
NEXT;
(cur == 0x5E)) {
switch (cur) {
case 'n':
break;
case 'r':
break;
case 't':
break;
default:
}
}
}
NEXT;
switch (cur) {
case 's':
break;
case 'S':
break;
case 'i':
break;
case 'I':
break;
case 'c':
break;
case 'C':
break;
case 'd':
break;
case 'D':
break;
case 'w':
break;
case 'W':
break;
}
NEXT;
}
} else {
ERROR("Wrong escape sequence, misuse of character '\\'");
}
}
/**
* xmlFAParseCharRef:
* @ctxt: a regexp parser context
*
* [19] XmlCharRef ::= ( '&#' [0-9]+ ';' ) | (' &#x' [0-9a-fA-F]+ ';' )
*/
static int
return(-1);
NEXT;
NEXT;
if (cur == 'x') {
NEXT;
else
NEXT;
}
} else {
ERROR("Char ref: expecting [0-9A-F]");
return(-1);
}
} else {
NEXT;
}
} else {
ERROR("Char ref: expecting [0-9]");
return(-1);
}
}
if (cur != ';') {
ERROR("Char ref: expecting ';'");
return(-1);
} else {
NEXT;
}
return(ret);
}
/**
* xmlFAParseCharRange:
* @ctxt: a regexp parser context
*
* [17] charRange ::= seRange | XmlCharRef | XmlCharIncDash
* [18] seRange ::= charOrEsc '-' charOrEsc
* [20] charOrEsc ::= XmlChar | SingleCharEsc
* [21] XmlChar ::= [^\#x2D#x5B#x5D]
* [22] XmlCharIncDash ::= [^\#x5B#x5D]
*/
static void
int start = -1;
int end = -1;
if (CUR == '\0') {
ERROR("Expecting ']'");
return;
}
return;
}
if (cur == '\\') {
NEXT;
switch (cur) {
case '\\': case '|': case '.': case '-': case '^': case '?':
case '*': case '+': case '{': case '}': case '(': case ')':
case '[': case ']':
default:
ERROR("Invalid escape value");
return;
}
len = 1;
} else {
ERROR("Expecting a char range");
return;
}
/*
* Since we are "inside" a range, we can assume ctxt->cur is past
* the start of ctxt->string, and PREV should be safe
*/
return;
}
return;
}
NEXT;
if (cur == '\\') {
NEXT;
switch (cur) {
case '\\': case '|': case '.': case '-': case '^': case '?':
case '*': case '+': case '{': case '}': case '(': case ')':
case '[': case ']':
default:
ERROR("Invalid escape value");
return;
}
len = 1;
} else {
ERROR("Expecting the end of a char range");
return;
}
/* TODO check that the values are acceptable character ranges for XML */
ERROR("End of range is before start of range");
} else {
}
return;
}
/**
* xmlFAParsePosCharGroup:
* @ctxt: a regexp parser context
*
* [14] posCharGroup ::= ( charRange | charClassEsc )+
*/
static void
do {
} else {
}
}
/**
* xmlFAParseCharGroup:
* @ctxt: a regexp parser context
*
* [13] charGroup ::= posCharGroup | negCharGroup | charClassSub
* [15] negCharGroup ::= '^' posCharGroup
* [16] charClassSub ::= ( posCharGroup | negCharGroup ) '-' charClassExpr
* [12] charClassExpr ::= '[' charGroup ']'
*/
static void
if (CUR == '^') {
NEXT;
NEXT; /* eat the '-' */
NEXT; /* eat the '[' */
if (CUR == ']') {
NEXT;
} else {
ERROR("charClassExpr: ']' expected");
break;
}
break;
} else if (CUR != ']') {
}
}
}
/**
* xmlFAParseCharClass:
* @ctxt: a regexp parser context
*
* [11] charClass ::= charClassEsc | charClassExpr
* [12] charClassExpr ::= '[' charGroup ']'
*/
static void
if (CUR == '[') {
NEXT;
return;
if (CUR == ']') {
NEXT;
} else {
ERROR("xmlFAParseCharClass: ']' expected");
}
} else {
}
}
/**
* xmlFAParseQuantExact:
* @ctxt: a regexp parser context
*
* [8] QuantExact ::= [0-9]+
*
* Returns 0 if success or -1 in case of error
*/
static int
int ret = 0;
int ok = 0;
ok = 1;
NEXT;
}
if (ok != 1) {
return(-1);
}
return(ret);
}
/**
* xmlFAParseQuantifier:
* @ctxt: a regexp parser context
*
* [4] quantifier ::= [?*+] | ( '{' quantity '}' )
* [5] quantity ::= quantRange | quantMin | QuantExact
* [6] quantRange ::= QuantExact ',' QuantExact
* [7] quantMin ::= QuantExact ','
* [8] QuantExact ::= [0-9]+
*/
static int
int cur;
if (cur == '?')
else if (cur == '*')
else if (cur == '+')
}
NEXT;
return(1);
}
if (cur == '{') {
NEXT;
if (cur >= 0)
if (CUR == ',') {
NEXT;
if (CUR == '}')
else {
if (cur >= 0)
else {
ERROR("Improper quantifier");
}
}
}
if (CUR == '}') {
NEXT;
} else {
ERROR("Unterminated quantifier");
}
if (max == 0)
}
return(1);
}
return(0);
}
/**
* xmlFAParseAtom:
* @ctxt: a regexp parser context
*
* [9] atom ::= Char | charClass | ( '(' regExp ')' )
*/
static int
if (codepoint > 0) {
return(-1);
return(1);
} else if (CUR == '|') {
return(0);
} else if (CUR == 0) {
return(0);
} else if (CUR == ')') {
return(0);
} else if (CUR == '(') {
NEXT;
/*
* this extra Epsilon transition is needed if we count with 0 allowed
* unfortunately this can't be known at that point
*/
xmlFAParseRegExp(ctxt, 0);
if (CUR == ')') {
NEXT;
} else {
ERROR("xmlFAParseAtom: expecting ')'");
}
return(-1);
return(1);
return(1);
}
return(0);
}
/**
* xmlFAParsePiece:
* @ctxt: a regexp parser context
*
* [3] piece ::= atom quantifier?
*/
static int
int ret;
if (ret == 0)
return(0);
ERROR("internal: no atom generated");
}
return(1);
}
/**
* xmlFAParseBranch:
* @ctxt: a regexp parser context
* @to: optional target to the end of the branch
*
* @to is used to optimize by removing duplicate path in automata
* in expressions like (a|b)(c|d)
*
* [2] branch ::= piece*
*/
static int
int ret;
if (ret != 0) {
return(-1);
}
if (ret != 0) {
return(-1);
}
}
return(0);
}
/**
* xmlFAParseRegExp:
* @ctxt: a regexp parser context
* @top: is this the top-level expression ?
*
* [1] regExp ::= branch ( '|' branch )*
*/
static void
/* if not top start should have been generated by an epsilon trans */
if (top) {
#ifdef DEBUG_REGEXP_GRAPH
#endif
}
if (CUR != '|') {
return;
}
NEXT;
}
if (!top) {
}
}
/************************************************************************
* *
* The basic API *
* *
************************************************************************/
/**
* xmlRegexpPrint:
* @output: the file for the output debug
* @regexp: the compiled regexp
*
* Print the content of the compiled regular expression
*/
void
int i;
return;
return;
}
}
}
for (i = 0;i < regexp->nbCounters; i++) {
}
}
/**
* xmlRegexpCompile:
* @regexp: a regular expression string
*
* Parses a regular expression conforming to XML Schemas Part 2 Datatype
* Appendix F and builds an automata suitable for testing strings against
* that regular expression
*
* Returns the compiled expression or NULL in case of error
*/
return(NULL);
/* initialize the parser */
/* parse the expression building an automata */
if (CUR != 0) {
ERROR("xmlFAParseRegExp: extra characters");
}
return(NULL);
}
/* remove the Epsilon except for counted transitions */
return(NULL);
}
return(ret);
}
/**
* xmlRegexpExec:
* @comp: the compiled regular expression
* @content: the value to check against the regular expression
*
* Check if the regular expression generates the value
*
* Returns 1 if it matches, 0 if not and a negative value in case of error
*/
int
return(-1);
}
/**
* xmlRegexpIsDeterminist:
* @comp: the compiled regular expression
*
* Check if the regular expression is determinist
*
* Returns 1 if it yes, 0 if not and a negative value in case of error
*/
int
int ret;
return(-1);
return(comp->determinist);
am = xmlNewAutomata();
int i;
}
return(ret);
}
/**
* xmlRegFreeRegexp:
* @regexp: the regexp
*
* Free a regexp
*/
void
int i;
return;
}
}
}
}
#ifdef LIBXML_AUTOMATA_ENABLED
/************************************************************************
* *
* The Automata interface *
* *
************************************************************************/
/**
* xmlNewAutomata:
*
* Create a new automata
*
* Returns the new object or NULL in case of failure
*/
xmlNewAutomata(void) {
return(NULL);
/* initialize the parser */
return(NULL);
}
return(NULL);
}
return(ctxt);
}
/**
* xmlFreeAutomata:
* @am: an automata
*
* Free an automata
*/
void
return;
}
/**
* xmlAutomataGetInitState:
* @am: an automata
*
* Initial state lookup
*
* Returns the initial state of the automata
*/
return(NULL);
}
/**
* xmlAutomataSetFinalState:
* @am: an automata
* @state: a state in this automata
*
* Makes that state a final state
*
* Returns 0 or -1 in case of error
*/
int
return(-1);
return(0);
}
/**
* xmlAutomataNewTransition:
* @am: an automata
* @from: the starting point of the transition
* @to: the target point of the transition or NULL
* @token: the input string associated to that transition
* @data: data passed to the callback function if the transition is activated
*
* If @to is NULL, this creates first a new target state in the automata
* and then adds a transition from the @from state to the target state
* activated by the value of @token
*
* Returns the target state or NULL in case of error
*/
void *data) {
return(NULL);
return(NULL);
return(NULL);
return(NULL);
}
return(to);
}
/**
* xmlAutomataNewTransition2:
* @am: an automata
* @from: the starting point of the transition
* @to: the target point of the transition or NULL
* @token: the first input string associated to that transition
* @token2: the second input string associated to that transition
* @data: data passed to the callback function if the transition is activated
*
* If @to is NULL, this creates first a new target state in the automata
* and then adds a transition from the @from state to the target state
* activated by the value of @token
*
* Returns the target state or NULL in case of error
*/
return(NULL);
return(NULL);
} else {
return(NULL);
}
}
return(NULL);
}
return(to);
}
/**
* xmlAutomataNewNegTrans:
* @am: an automata
* @from: the starting point of the transition
* @to: the target point of the transition or NULL
* @token: the first input string associated to that transition
* @token2: the second input string associated to that transition
* @data: data passed to the callback function if the transition is activated
*
* If @to is NULL, this creates first a new target state in the automata
* and then adds a transition from the @from state to the target state
* activated by any value except (@token,@token2)
* Note that if @token2 is not NULL, then (X, NULL) won't match to follow
# the semantic of XSD ##other
*
* Returns the target state or NULL in case of error
*/
return(NULL);
return(NULL);
} else {
return(NULL);
}
}
err_msg[199] = 0;
return(NULL);
}
return(to);
}
/**
* xmlAutomataNewCountTrans2:
* @am: an automata
* @from: the starting point of the transition
* @to: the target point of the transition or NULL
* @token: the input string associated to that transition
* @token2: the second input string associated to that transition
* @min: the minimum successive occurences of token
* @max: the maximum successive occurences of token
* @data: data associated to the transition
*
* If @to is NULL, this creates first a new target state in the automata
* and then adds a transition from the @from state to the target state
* activated by a succession of input of value @token and @token2 and
* whose number is between @min and @max
*
* Returns the target state or NULL in case of error
*/
int counter;
return(NULL);
if (min < 0)
return(NULL);
return(NULL);
return(NULL);
} else {
return(NULL);
}
}
if (min == 0)
else
/*
* associate a counter to the transition.
*/
/* xmlFAGenerateTransitions(am, from, to, atom); */
}
return(NULL);
if (min == 0)
return(to);
}
/**
* xmlAutomataNewCountTrans:
* @am: an automata
* @from: the starting point of the transition
* @to: the target point of the transition or NULL
* @token: the input string associated to that transition
* @min: the minimum successive occurences of token
* @max: the maximum successive occurences of token
* @data: data associated to the transition
*
* If @to is NULL, this creates first a new target state in the automata
* and then adds a transition from the @from state to the target state
* activated by a succession of input of value @token and whose number
* is between @min and @max
*
* Returns the target state or NULL in case of error
*/
int counter;
return(NULL);
if (min < 0)
return(NULL);
return(NULL);
return(NULL);
if (min == 0)
else
/*
* associate a counter to the transition.
*/
/* xmlFAGenerateTransitions(am, from, to, atom); */
}
return(NULL);
if (min == 0)
return(to);
}
/**
* xmlAutomataNewOnceTrans2:
* @am: an automata
* @from: the starting point of the transition
* @to: the target point of the transition or NULL
* @token: the input string associated to that transition
* @token2: the second input string associated to that transition
* @min: the minimum successive occurences of token
* @max: the maximum successive occurences of token
* @data: data associated to the transition
*
* If @to is NULL, this creates first a new target state in the automata
* and then adds a transition from the @from state to the target state
* activated by a succession of input of value @token and @token2 and whose
* number is between @min and @max, moreover that transition can only be
* crossed once.
*
* Returns the target state or NULL in case of error
*/
int counter;
return(NULL);
if (min < 1)
return(NULL);
return(NULL);
return(NULL);
} else {
return(NULL);
}
}
/*
* associate a counter to the transition.
*/
/* xmlFAGenerateTransitions(am, from, to, atom); */
}
return(to);
}
/**
* xmlAutomataNewOnceTrans:
* @am: an automata
* @from: the starting point of the transition
* @to: the target point of the transition or NULL
* @token: the input string associated to that transition
* @min: the minimum successive occurences of token
* @max: the maximum successive occurences of token
* @data: data associated to the transition
*
* If @to is NULL, this creates first a new target state in the automata
* and then adds a transition from the @from state to the target state
* activated by a succession of input of value @token and whose number
* is between @min and @max, moreover that transition can only be crossed
* once.
*
* Returns the target state or NULL in case of error
*/
int counter;
return(NULL);
if (min < 1)
return(NULL);
return(NULL);
return(NULL);
/*
* associate a counter to the transition.
*/
/* xmlFAGenerateTransitions(am, from, to, atom); */
}
return(to);
}
/**
* xmlAutomataNewState:
* @am: an automata
*
* Create a new disconnected state in the automata
*
* Returns the new state or NULL in case of error
*/
return(NULL);
return(to);
}
/**
* xmlAutomataNewEpsilon:
* @am: an automata
* @from: the starting point of the transition
* @to: the target point of the transition or NULL
*
* If @to is NULL, this creates first a new target state in the automata
* and then adds an epsilon transition from the @from state to the
* target state
*
* Returns the target state or NULL in case of error
*/
return(NULL);
return(to);
}
/**
* xmlAutomataNewAllTrans:
* @am: an automata
* @from: the starting point of the transition
* @to: the target point of the transition or NULL
* @lax: allow to transition if not all all transitions have been activated
*
* If @to is NULL, this creates first a new target state in the automata
* and then adds a an ALL transition from the @from state to the
* target state. That transition is an epsilon transition allowed only when
* all transitions from the @from node have been activated.
*
* Returns the target state or NULL in case of error
*/
return(NULL);
return(to);
}
/**
* xmlAutomataNewCounter:
* @am: an automata
* @min: the minimal value on the counter
* @max: the maximal value on the counter
*
* Create a new counter
*
* Returns the counter number or -1 in case of error
*/
int
int ret;
return(-1);
if (ret < 0)
return(-1);
return(ret);
}
/**
* xmlAutomataNewCountedTrans:
* @am: an automata
* @from: the starting point of the transition
* @to: the target point of the transition or NULL
* @counter: the counter associated to that transition
*
* If @to is NULL, this creates first a new target state in the automata
* and then adds an epsilon transition from the @from state to the target state
* which will increment the counter provided
*
* Returns the target state or NULL in case of error
*/
return(NULL);
return(to);
}
/**
* xmlAutomataNewCounterTrans:
* @am: an automata
* @from: the starting point of the transition
* @to: the target point of the transition or NULL
* @counter: the counter associated to that transition
*
* If @to is NULL, this creates first a new target state in the automata
* and then adds an epsilon transition from the @from state to the target state
* which will be allowed only if the counter is within the right range.
*
* Returns the target state or NULL in case of error
*/
return(NULL);
return(to);
}
/**
* xmlAutomataCompile:
* @am: an automata
*
* Compile the automata into a Reg Exp ready for being executed.
* The automata should be free after this point.
*
* Returns the compiled regexp or NULL in case of error
*/
/* xmlFAComputesDeterminism(am); */
return(ret);
}
/**
* xmlAutomataIsDeterminist:
* @am: an automata
*
* Checks if an automata is determinist.
*
* Returns 1 if true, 0 if not, and -1 in case of error
*/
int
int ret;
return(-1);
return(ret);
}
#endif /* LIBXML_AUTOMATA_ENABLED */
#ifdef LIBXML_EXPR_ENABLED
/************************************************************************
* *
* Formal Expression handling code *
* *
************************************************************************/
/************************************************************************
* *
* Expression handling context *
* *
************************************************************************/
struct _xmlExpCtxt {
int size;
int nbElems;
int nb_nodes;
const char *expr;
const char *cur;
int nb_cons;
int tabSize;
};
/**
* xmlExpNewCtxt:
* @maxNodes: the maximum number of nodes
* @dict: optional dictionnary to use internally
*
* Creates a new context for manipulating expressions
*
* Returns the context or NULL in case of error
*/
int size = 256;
if (maxNodes <= 4096)
maxNodes = 4096;
return(NULL);
return(NULL);
}
return(NULL);
}
} else {
}
return(ret);
}
/**
* xmlExpFreeCtxt:
* @ctxt: an expression context
*
* Free an expression context
*/
void
return;
}
/************************************************************************
* *
* Structure associated to an expression node *
* *
************************************************************************/
#define MAX_NODES 10000
/* #define DEBUG_DERIV */
/*
* TODO:
* - Wildcards
* - public API for creation
*
* Started
* - regression testing
*
* Done
* - split into module and test tool
* - memleaks
*/
typedef enum {
XML_EXP_NILABLE = (1 << 0)
struct _xmlExpNode {
unsigned char type;/* xmlExpNodeType */
unsigned char info;/* OR of xmlExpNodeInfo */
unsigned short key; /* the hash key */
unsigned int ref; /* The number of references */
int c_max; /* the maximum length it can consume */
union {
struct {
int f_min;
int f_max;
} count;
struct {
} children;
} field;
};
/* #define exp_left field.children.f_left */
static xmlExpNode forbiddenExpNode = {
};
static xmlExpNode emptyExpNode = {
};
/************************************************************************
* *
* The custom hash table for unicity and canonicalization *
* of sub-expressions pointers *
* *
************************************************************************/
/*
* xmlExpHashNameComputeKey:
* Calculate the hash key for a token
*/
static unsigned short
unsigned short value = 0L;
char ch;
}
}
return (value);
}
/*
* xmlExpHashComputeKey:
* Calculate the hash key for a compound expression
*/
static unsigned short
unsigned long value;
unsigned short ret;
switch (type) {
case XML_EXP_SEQ:
value *= 3;
break;
case XML_EXP_OR:
value *= 7;
break;
case XML_EXP_COUNT:
break;
default:
ret = 0;
}
return(ret);
}
static xmlExpNodePtr
return(NULL);
return(NULL);
return(ret);
}
/**
* xmlExpHashGetEntry:
* @table: the hash table
*
* Get the unique entry from the hash table. The entry is created if
* needed. @left and @right are consumed, i.e. their ref count will
* be decremented by the operation.
*
* Returns the pointer or NULL in case of error
*/
static xmlExpNodePtr
return(NULL);
/*
* Check for duplicate and insertion location.
*/
if (type == XML_EXP_ATOM) {
} else if (type == XML_EXP_COUNT) {
/* COUNT reduction rule 1 */
/* a{1} -> a */
if (min == 1) {
return(left);
}
if (min == 0) {
return(emptyExp);
}
}
if (min < 0) {
return(forbiddenExp);
}
if (max == -1)
else
} else if (type == XML_EXP_OR) {
/* Forbid reduction rules */
return(right);
}
return(left);
}
/* OR reduction rule 1 */
/* a | a reduced to a */
return(left);
}
/* OR canonicalization rule 1 */
/* linearize (a | b) | c into a | (b | c) */
}
/* OR reduction rule 2 */
/* a | (a | b) and b | (a | b) are reduced to a | b */
return(right);
}
}
/* OR canonicalization rule 2 */
/* linearize (a | b) | c into a | (b | c) */
/* OR canonicalization rule 2 */
}
NULL, 0, 0);
NULL, 0, 0);
return(tmp);
}
/* Ordering in the tree */
/* C | (A | B) -> A | (B | C) */
return(tmp);
}
/* Ordering in the tree */
/* B | (A | C) -> A | (B | C) */
return(tmp);
}
}
/* we know both types are != XML_EXP_OR here */
}
} else if (type == XML_EXP_SEQ) {
/* Forbid reduction rules */
return(left);
}
return(right);
}
/* Empty reduction rules */
return(left);
}
return(right);
}
} else
return(NULL);
if (type == XML_EXP_ATOM) {
return(insert);
}
} else if (type == XML_EXP_COUNT) {
return(insert);
}
return(insert);
}
}
}
}
return(NULL);
if (type == XML_EXP_ATOM) {
} else if (type == XML_EXP_COUNT) {
if (max < 0)
else
} else {
if (type == XML_EXP_OR) {
else
} else {
else
}
}
return(entry);
}
/**
* xmlExpFree:
* @ctxt: the expression context
* @exp: the expression
*
* Dereference the expression
*/
void
return;
unsigned short key;
/* Unlink it first from the hash table */
} else {
break;
}
}
}
}
}
}
/**
* xmlExpRef:
* @exp: the expression
*
* Increase the reference count of the expression
*/
void
}
/**
* xmlExpNewAtom:
* @ctxt: the expression context
* @name: the atom name
* @len: the atom name lenght in byte (or -1);
*
* Get the atom associated to this name from that context
*
* Returns the node or NULL in case of error
*/
return(NULL);
return(NULL);
}
/**
* xmlExpNewOr:
* @ctxt: the expression context
* @left: left expression
* @right: right expression
*
* Get the atom associated to the choice @left | @right
* Note that @left and @right are consumed in the operation, to keep
* an handle on them use xmlExpRef() and use xmlExpFree() to release them,
* this is true even in case of failure (unless ctxt == NULL).
*
* Returns the node or NULL in case of error
*/
return(NULL);
return(NULL);
}
}
/**
* xmlExpNewSeq:
* @ctxt: the expression context
* @left: left expression
* @right: right expression
*
* Get the atom associated to the sequence @left , @right
* Note that @left and @right are consumed in the operation, to keep
* an handle on them use xmlExpRef() and use xmlExpFree() to release them,
* this is true even in case of failure (unless ctxt == NULL).
*
* Returns the node or NULL in case of error
*/
return(NULL);
return(NULL);
}
}
/**
* xmlExpNewRange:
* @ctxt: the expression context
* @subset: the expression to be repeated
* @min: the lower bound for the repetition
* @max: the upper bound for the repetition, -1 means infinite
*
* Get the atom associated to the range (@subset){@min, @max}
* Note that @subset is consumed in the operation, to keep
* an handle on it use xmlExpRef() and use xmlExpFree() to release it,
* this is true even in case of failure (unless ctxt == NULL).
*
* Returns the node or NULL in case of error
*/
return(NULL);
return(NULL);
}
}
/************************************************************************
* *
* Public API for operations on expressions *
* *
************************************************************************/
static int
tail:
case XML_EXP_EMPTY:
return(0);
case XML_EXP_ATOM:
return(0);
return(-2);
return(1);
case XML_EXP_COUNT:
goto tail;
case XML_EXP_SEQ:
case XML_EXP_OR:
if (tmp < 0)
return(tmp);
if (tmp2 < 0)
return(tmp2);
}
return(-1);
}
/**
* xmlExpGetLanguage:
* @ctxt: the expression context
* @exp: the expression
* @langList: where to store the tokens
* @len: the allocated lenght of @list
*
* Find all the strings used in @exp and store them in @list
*
* Returns the number of unique strings found, -1 in case of errors and
* -2 if there is more than @len strings
*/
int
return(-1);
}
static int
tail:
case XML_EXP_FORBID:
return(0);
case XML_EXP_EMPTY:
return(0);
case XML_EXP_ATOM:
return(0);
return(-2);
return(1);
case XML_EXP_COUNT:
goto tail;
case XML_EXP_SEQ:
if (tmp < 0)
return(tmp);
if (tmp2 < 0)
return(tmp2);
}
return(tmp);
case XML_EXP_OR:
if (tmp < 0)
return(tmp);
if (tmp2 < 0)
return(tmp2);
}
return(-1);
}
/**
* xmlExpGetStart:
* @ctxt: the expression context
* @exp: the expression
* @tokList: where to store the tokens
* @len: the allocated lenght of @list
*
* Find all the strings that appears at the start of the languages
* accepted by @exp and store them in @list. E.g. for (a, b) | c
* it will return the list [a, c]
*
* Returns the number of unique strings found, -1 in case of errors and
* -2 if there is more than @len strings
*/
int
return(-1);
}
/**
* xmlExpIsNillable:
* @exp: the expression
*
* Finds if the expression is nillable, i.e. if it accepts the empty sequqnce
*
* Returns 1 if nillable, 0 if not and -1 in case of error
*/
int
return(-1);
return(IS_NILLABLE(exp) != 0);
}
static xmlExpNodePtr
{
case XML_EXP_EMPTY:
return(forbiddenExp);
case XML_EXP_FORBID:
return(forbiddenExp);
case XML_EXP_ATOM:
#ifdef DEBUG_DERIV
printf("deriv atom: equal => Empty\n");
#endif
} else {
#ifdef DEBUG_DERIV
printf("deriv atom: mismatch => forbid\n");
#endif
/* TODO wildcards here */
ret = forbiddenExp;
}
return(ret);
case XML_EXP_OR: {
#ifdef DEBUG_DERIV
printf("deriv or: => or(derivs)\n");
#endif
return(NULL);
}
return(NULL);
}
NULL, 0, 0);
return(ret);
}
case XML_EXP_SEQ:
#ifdef DEBUG_DERIV
printf("deriv seq: starting with left\n");
#endif
return(NULL);
} else if (ret == forbiddenExp) {
#ifdef DEBUG_DERIV
printf("deriv seq: left failed but nillable\n");
#endif
}
} else {
#ifdef DEBUG_DERIV
printf("deriv seq: left match => sequence\n");
#endif
NULL, 0, 0);
}
return(ret);
case XML_EXP_COUNT: {
return(forbiddenExp);
return(NULL);
if (ret == forbiddenExp) {
#ifdef DEBUG_DERIV
printf("deriv count: pattern mismatch => forbid\n");
#endif
return(ret);
}
return(ret);
max = -1;
else
else
min = 0;
#ifdef DEBUG_DERIV
printf("deriv count: match to empty => new count\n");
#endif
return(tmp);
}
#ifdef DEBUG_DERIV
printf("deriv count: match => sequence with new count\n");
#endif
NULL, 0, 0));
}
}
return(NULL);
}
/**
* xmlExpStringDerive:
* @ctxt: the expression context
* @exp: the expression
* @str: the string
* @len: the string len in bytes if available
*
* Do one step of Brzozowski derivation of the expression @exp with
* respect to the input string
*
* Returns the resulting expression or NULL in case of internal error
*/
return(NULL);
}
/*
* check the string is in the dictionnary, if yes use an interned
* copy, otherwise we know it's not an acceptable input
*/
return(forbiddenExp);
}
}
static int
int ret = 1;
ret = 0;
ret = 0;
}
#if 0
ret = 0;
#endif
return(ret);
}
/**
* xmlExpDivide:
* @ctxt: the expressions context
* @exp: the englobing expression
* @sub: the subexpression
* @mult: the multiple expression
* @remain: the remain from the derivation of the multiple
*
* Check if exp is a multiple of sub, i.e. if there is a finite number n
* so that sub{n} subsume exp
*
* Returns the multiple value if successful, 0 if it is not a multiple
* and -1 in case of internel error.
*/
static int
int i;
return(-1);
}
continue;
}
return(-1);
}
else
else
#ifdef DEBUG_DERIV
printf("Divide succeeded %d\n", i);
#endif
return(i);
}
}
#ifdef DEBUG_DERIV
printf("Divide failed\n");
#endif
return(0);
}
/**
* xmlExpExpDeriveInt:
* @ctxt: the expressions context
* @exp: the englobing expression
* @sub: the subexpression
*
* Try to do a step of Brzozowski derivation but at a higher level
* the input being a subexpression.
*
* Returns the resulting expression or NULL in case of internal error
*/
static xmlExpNodePtr
int len, i;
/*
* In case of equality and if the expression can only consume a finite
* amount, then the derivation is empty
*/
#ifdef DEBUG_DERIV
printf("Equal(exp, sub) and finite -> Empty\n");
#endif
return(emptyExp);
}
/*
* decompose sub sequence first
*/
#ifdef DEBUG_DERIV
printf("Empty(sub) -> Empty\n");
#endif
return(exp);
}
#ifdef DEBUG_DERIV
printf("Seq(sub) -> decompose\n");
#endif
return(NULL);
if (tmp == forbiddenExp)
return(tmp);
return(ret);
}
#ifdef DEBUG_DERIV
printf("Or(sub) -> decompose\n");
#endif
if (tmp == forbiddenExp)
return(tmp);
return(NULL);
return(ret);
}
}
#ifdef DEBUG_DERIV
printf("CheckCard(exp, sub) failed -> Forbid\n");
#endif
return(forbiddenExp);
}
case XML_EXP_EMPTY:
return(emptyExp);
#ifdef DEBUG_DERIV
printf("Empty(exp) -> Forbid\n");
#endif
return(forbiddenExp);
case XML_EXP_FORBID:
#ifdef DEBUG_DERIV
printf("Forbid(exp) -> Forbid\n");
#endif
return(forbiddenExp);
case XML_EXP_ATOM:
/* TODO: handle wildcards */
#ifdef DEBUG_DERIV
printf("Atom match -> Empty\n");
#endif
return(emptyExp);
}
#ifdef DEBUG_DERIV
printf("Atom mismatch -> Forbid\n");
#endif
return(forbiddenExp);
}
/* TODO: handle wildcards */
#ifdef DEBUG_DERIV
printf("Atom match -> Empty\n");
#endif
return(emptyExp);
}
#ifdef DEBUG_DERIV
printf("Atom mismatch -> Forbid\n");
#endif
return(forbiddenExp);
}
#ifdef DEBUG_DERIV
printf("Compex exp vs Atom -> Forbid\n");
#endif
return(forbiddenExp);
case XML_EXP_SEQ:
/* try to get the sequence consumed only if possible */
/* See if the sequence can be consumed directly */
#ifdef DEBUG_DERIV
printf("Seq trying left only\n");
#endif
#ifdef DEBUG_DERIV
printf("Seq trying left only worked\n");
#endif
/*
* TODO: assumption here that we are determinist
* i.e. we won't get to a nillable exp left
* subset which could be matched by the right
* part too.
* e.g.: (a | b)+,(a | c) and 'a+,a'
*/
}
#ifdef DEBUG_DERIV
} else {
printf("Seq: left too short\n");
#endif
}
/* Try instead to decompose */
#ifdef DEBUG_DERIV
printf("Seq: sub is a count\n");
#endif
return(NULL);
if (ret != forbiddenExp) {
#ifdef DEBUG_DERIV
printf("Seq , Count match on left\n");
#endif
max = -1;
else
else
min = 0;
return(NULL);
return(NULL);
}
return(ret);
}
}
/* we made no progress on structured operations */
break;
case XML_EXP_OR:
#ifdef DEBUG_DERIV
printf("Or , trying both side\n");
#endif
return(NULL);
return(NULL);
}
case XML_EXP_COUNT: {
/*
* Try to see if the loop is completely subsumed
*/
return(NULL);
if (tmp == forbiddenExp) {
int mult;
#ifdef DEBUG_DERIV
printf("Count, Count inner don't subsume\n");
#endif
if (mult <= 0) {
#ifdef DEBUG_DERIV
printf("Count, Count not multiple => forbidden\n");
#endif
return(forbiddenExp);
}
max = -1;
min = 0;
else
} else {
#ifdef DEBUG_DERIV
printf("Count, Count finite can't subsume infinite\n");
#endif
return(forbiddenExp);
}
} else {
#ifdef DEBUG_DERIV
printf("Infinite loop consume mult finite loop\n");
#endif
max = -1;
} else {
max = -1;
min = 0;
}
} else {
#ifdef DEBUG_DERIV
printf("loops max mult mismatch => forbidden\n");
#endif
return(forbiddenExp);
}
min = 0;
else
}
}
} else if (!IS_NILLABLE(tmp)) {
/*
* TODO: loop here to try to grow if working on finite
* blocks.
*/
#ifdef DEBUG_DERIV
printf("Count, Count remain not nillable => forbidden\n");
#endif
return(forbiddenExp);
#ifdef DEBUG_DERIV
printf("Infinite loops Okay => COUNT(0,Inf)\n");
#endif
max = -1;
min = 0;
} else {
#ifdef DEBUG_DERIV
printf("Infinite loops min => Count(X,Inf)\n");
#endif
max = -1;
}
#ifdef DEBUG_DERIV
printf("loops min mismatch 1 => forbidden ???\n");
#endif
return(forbiddenExp);
} else {
max = -1;
min = 0;
}
} else {
#ifdef DEBUG_DERIV
printf("Infinite loop consume finite loop\n");
#endif
max = -1;
} else {
max = -1;
min = 0;
}
} else {
#ifdef DEBUG_DERIV
printf("loops max mismatch => forbidden\n");
#endif
return(forbiddenExp);
}
min = 0;
else
}
}
#ifdef DEBUG_DERIV
printf("loops match => SEQ(COUNT())\n");
#endif
return(NULL);
}
NULL, 0, 0);
return(ret);
}
return(NULL);
if (tmp == forbiddenExp) {
#ifdef DEBUG_DERIV
printf("loop mismatch => forbidden\n");
#endif
return(forbiddenExp);
}
else
min = 0;
max = -1;
else
#ifdef DEBUG_DERIV
printf("loop match => SEQ(COUNT())\n");
#endif
return(NULL);
NULL, 0, 0);
return(ret);
}
}
#ifdef DEBUG_DERIV
printf("Fallback to derivative\n");
#endif
if (IS_NILLABLE(sub)) {
if (!(IS_NILLABLE(exp)))
return(forbiddenExp);
else
} else
/*
* here the structured derivation made no progress so
* we use the default token based derivation to force one more step
*/
sizeof(const xmlChar *));
return(NULL);
}
/*
* collect all the strings accepted by the subexpression on input
*/
while (len < 0) {
sizeof(const xmlChar *));
return(NULL);
}
}
for (i = 0;i < len;i++) {
return(tmp);
}
return(tmp);
}
return(tmp3);
}
else {
return(NULL);
}
}
}
return(ret);
}
/**
* xmlExpExpDerive:
* @ctxt: the expressions context
* @exp: the englobing expression
* @sub: the subexpression
*
* Evaluates the expression resulting from @exp consuming a sub expression @sub
* Based on algebraic derivation and sometimes direct Brzozowski derivation
* it usually tatkes less than linear time and can handle expressions generating
* infinite languages.
*
* Returns the resulting expression or NULL in case of internal error, the
* result must be freed
*/
return(NULL);
/*
* O(1) speedups
*/
#ifdef DEBUG_DERIV
printf("Sub nillable and not exp : can't subsume\n");
#endif
return(forbiddenExp);
}
#ifdef DEBUG_DERIV
printf("sub generate longuer sequances than exp : can't subsume\n");
#endif
return(forbiddenExp);
}
}
/**
* xmlExpSubsume:
* @ctxt: the expressions context
* @exp: the englobing expression
* @sub: the subexpression
*
* Check whether @exp accepts all the languages accexpted by @sub
* the input being a subexpression.
*
* Returns 1 if true 0 if false and -1 in case of failure.
*/
int
return(-1);
/*
* TODO: speedup by checking the language of sub is a subset of the
* language of exp
*/
/*
* O(1) speedups
*/
#ifdef DEBUG_DERIV
printf("Sub nillable and not exp : can't subsume\n");
#endif
return(0);
}
#ifdef DEBUG_DERIV
printf("sub generate longuer sequances than exp : can't subsume\n");
#endif
return(0);
}
#ifdef DEBUG_DERIV
printf("Result derivation :\n");
#endif
return(-1);
if (tmp == forbiddenExp)
return(0);
return(1);
return(1);
}
return(0);
}
/************************************************************************
* *
* Parsing expression *
* *
************************************************************************/
static int
int ret = 0;
if (CUR == '*') {
return(-1);
}
return(-1);
}
return(ret);
}
static xmlExpNodePtr
const char *base;
return(NULL);
}
NEXT;
goto parse_quantifier;
}
NEXT;
return(NULL);
return(NULL);
if (CUR == '{') {
if (min < 0) {
return(NULL);
}
if (CUR == ',') {
} else
if (CUR != '}') {
return(NULL);
}
} else if (CUR == '?') {
0, 1);
} else if (CUR == '+') {
1, -1);
} else if (CUR == '*') {
0, -1);
}
return(ret);
}
static xmlExpNodePtr
while (CUR == '|') {
return(NULL);
}
return(NULL);
}
return(ret);
}
static xmlExpNodePtr
while (CUR == ',') {
return(NULL);
}
return(NULL);
}
return(ret);
}
/**
* xmlExpParse:
* @ctxt: the expressions context
* @expr: the 0 terminated string
*
* Minimal parser for regexps, it understand the following constructs
* - string terminals
* - choice operator |
* - sequence operator ,
* - subexpressions (...)
* - usual cardinality operators + * and ?
* - finite sequences { min, max }
* - infinite sequences { min, * }
* There is minimal checkings made especially no checking on strings values
*
* Returns a new expression or NULL in case of failure
*/
return(NULL);
}
return(ret);
}
static void
case XML_EXP_EMPTY:
break;
case XML_EXP_FORBID:
break;
case XML_EXP_ATOM:
break;
case XML_EXP_SEQ:
else
xmlExpDumpInt(buf, c, 0);
else
xmlExpDumpInt(buf, c, 0);
break;
case XML_EXP_OR:
else
xmlExpDumpInt(buf, c, 0);
else
xmlExpDumpInt(buf, c, 0);
break;
case XML_EXP_COUNT: {
char rep[40];
else
xmlExpDumpInt(buf, c, 0);
rep[0] = '?';
rep[1] = 0;
rep[0] = '*';
rep[1] = 0;
rep[0] = '+';
rep[1] = 0;
} else {
}
rep[39] = 0;
break;
}
default:
}
if (glob)
}
/**
* xmlExpDump:
* @buf: a buffer to receive the output
* @expr: the compiled expression
*
* Serialize the expression as compiled to the buffer
*/
void
return;
}
/**
* xmlExpMaxToken:
* @expr: a compiled expression
*
* Indicate the maximum number of input a expression can accept
*
* Returns the maximum length or -1 in case of error
*/
int
return(-1);
}
/**
* xmlExpCtxtNbNodes:
* @ctxt: an expression context
*
* Debugging facility provides the number of allocated nodes at a that point
*
* Returns the number of nodes in use or -1 in case of error
*/
int
return(-1);
}
/**
* xmlExpCtxtNbCons:
* @ctxt: an expression context
*
* Debugging facility provides the number of allocated nodes over lifetime
*
* Returns the number of nodes ever allocated or -1 in case of error
*/
int
return(-1);
}
#endif /* LIBXML_EXPR_ENABLED */
#define bottom_xmlregexp
#include "elfgcchack.h"
#endif /* LIBXML_REGEXP_ENABLED */