blob: 7638c714ae2ba20e2dfc763df505c31fa2b3f7b1 [file] [log] [blame]
Daniel Veillard4255d502002-04-16 15:50:10 +00001/*
2 * regexp.c: generic and extensible Regular Expression engine
3 *
4 * Basically designed with the purpose of compiling regexps for
5 * the variety of validation/shemas mechanisms now available in
William M. Brackddf71d62004-05-06 04:17:26 +00006 * XML related specifications these include:
Daniel Veillard4255d502002-04-16 15:50:10 +00007 * - XML-1.0 DTD validation
8 * - XML Schemas structure part 1
9 * - XML Schemas Datatypes part 2 especially Appendix F
10 * - RELAX-NG/TREX i.e. the counter proposal
11 *
12 * See Copyright for the status of this software.
13 *
14 * Daniel Veillard <veillard@redhat.com>
15 */
16
17#define IN_LIBXML
18#include "libxml.h"
19
20#ifdef LIBXML_REGEXP_ENABLED
21
Daniel Veillardcee2b3a2005-01-25 00:22:52 +000022/* #define DEBUG_ERR */
Daniel Veillardfc0b6f62005-01-09 17:48:02 +000023
Daniel Veillard4255d502002-04-16 15:50:10 +000024#include <stdio.h>
25#include <string.h>
Daniel Veillardebe48c62003-12-03 12:12:27 +000026#ifdef HAVE_LIMITS_H
27#include <limits.h>
28#endif
29
Daniel Veillard4255d502002-04-16 15:50:10 +000030#include <libxml/tree.h>
31#include <libxml/parserInternals.h>
32#include <libxml/xmlregexp.h>
33#include <libxml/xmlautomata.h>
34#include <libxml/xmlunicode.h>
35
Daniel Veillardebe48c62003-12-03 12:12:27 +000036#ifndef INT_MAX
37#define INT_MAX 123456789 /* easy to flag and big enough for our needs */
38#endif
39
Daniel Veillardc0826a72004-08-10 14:17:33 +000040/* #define DEBUG_REGEXP_GRAPH */
41/* #define DEBUG_REGEXP_EXEC */
Daniel Veillard4255d502002-04-16 15:50:10 +000042/* #define DEBUG_PUSH */
Daniel Veillard23e73572002-09-19 19:56:43 +000043/* #define DEBUG_COMPACTION */
Daniel Veillard4255d502002-04-16 15:50:10 +000044
Daniel Veillardff46a042003-10-08 08:53:17 +000045#define ERROR(str) \
46 ctxt->error = XML_REGEXP_COMPILE_ERROR; \
47 xmlRegexpErrCompile(ctxt, str);
Daniel Veillard4255d502002-04-16 15:50:10 +000048#define NEXT ctxt->cur++
49#define CUR (*(ctxt->cur))
50#define NXT(index) (ctxt->cur[index])
51
52#define CUR_SCHAR(s, l) xmlStringCurrentChar(NULL, s, &l)
53#define NEXTL(l) ctxt->cur += l;
Daniel Veillardc0826a72004-08-10 14:17:33 +000054#define XML_REG_STRING_SEPARATOR '|'
Daniel Veillard4255d502002-04-16 15:50:10 +000055
Daniel Veillarde19fc232002-04-22 16:01:24 +000056/**
57 * TODO:
58 *
59 * macro to flag unimplemented blocks
60 */
61#define TODO \
62 xmlGenericError(xmlGenericErrorContext, \
63 "Unimplemented block at %s:%d\n", \
64 __FILE__, __LINE__);
65
Daniel Veillard4255d502002-04-16 15:50:10 +000066/************************************************************************
67 * *
68 * Datatypes and structures *
69 * *
70 ************************************************************************/
71
72typedef enum {
73 XML_REGEXP_EPSILON = 1,
74 XML_REGEXP_CHARVAL,
75 XML_REGEXP_RANGES,
76 XML_REGEXP_SUBREG,
77 XML_REGEXP_STRING,
78 XML_REGEXP_ANYCHAR, /* . */
79 XML_REGEXP_ANYSPACE, /* \s */
80 XML_REGEXP_NOTSPACE, /* \S */
81 XML_REGEXP_INITNAME, /* \l */
82 XML_REGEXP_NOTINITNAME, /* \l */
83 XML_REGEXP_NAMECHAR, /* \c */
84 XML_REGEXP_NOTNAMECHAR, /* \C */
85 XML_REGEXP_DECIMAL, /* \d */
86 XML_REGEXP_NOTDECIMAL, /* \d */
87 XML_REGEXP_REALCHAR, /* \w */
88 XML_REGEXP_NOTREALCHAR, /* \w */
89 XML_REGEXP_LETTER,
90 XML_REGEXP_LETTER_UPPERCASE,
91 XML_REGEXP_LETTER_LOWERCASE,
92 XML_REGEXP_LETTER_TITLECASE,
93 XML_REGEXP_LETTER_MODIFIER,
94 XML_REGEXP_LETTER_OTHERS,
95 XML_REGEXP_MARK,
96 XML_REGEXP_MARK_NONSPACING,
97 XML_REGEXP_MARK_SPACECOMBINING,
98 XML_REGEXP_MARK_ENCLOSING,
99 XML_REGEXP_NUMBER,
100 XML_REGEXP_NUMBER_DECIMAL,
101 XML_REGEXP_NUMBER_LETTER,
102 XML_REGEXP_NUMBER_OTHERS,
103 XML_REGEXP_PUNCT,
104 XML_REGEXP_PUNCT_CONNECTOR,
105 XML_REGEXP_PUNCT_DASH,
106 XML_REGEXP_PUNCT_OPEN,
107 XML_REGEXP_PUNCT_CLOSE,
108 XML_REGEXP_PUNCT_INITQUOTE,
109 XML_REGEXP_PUNCT_FINQUOTE,
110 XML_REGEXP_PUNCT_OTHERS,
111 XML_REGEXP_SEPAR,
112 XML_REGEXP_SEPAR_SPACE,
113 XML_REGEXP_SEPAR_LINE,
114 XML_REGEXP_SEPAR_PARA,
115 XML_REGEXP_SYMBOL,
116 XML_REGEXP_SYMBOL_MATH,
117 XML_REGEXP_SYMBOL_CURRENCY,
118 XML_REGEXP_SYMBOL_MODIFIER,
119 XML_REGEXP_SYMBOL_OTHERS,
120 XML_REGEXP_OTHER,
121 XML_REGEXP_OTHER_CONTROL,
122 XML_REGEXP_OTHER_FORMAT,
123 XML_REGEXP_OTHER_PRIVATE,
124 XML_REGEXP_OTHER_NA,
125 XML_REGEXP_BLOCK_NAME
126} xmlRegAtomType;
127
128typedef enum {
129 XML_REGEXP_QUANT_EPSILON = 1,
130 XML_REGEXP_QUANT_ONCE,
131 XML_REGEXP_QUANT_OPT,
132 XML_REGEXP_QUANT_MULT,
133 XML_REGEXP_QUANT_PLUS,
Daniel Veillard7646b182002-04-20 06:41:40 +0000134 XML_REGEXP_QUANT_ONCEONLY,
135 XML_REGEXP_QUANT_ALL,
Daniel Veillard4255d502002-04-16 15:50:10 +0000136 XML_REGEXP_QUANT_RANGE
137} xmlRegQuantType;
138
139typedef enum {
140 XML_REGEXP_START_STATE = 1,
141 XML_REGEXP_FINAL_STATE,
Daniel Veillardcc026dc2005-01-12 13:21:17 +0000142 XML_REGEXP_TRANS_STATE,
143 XML_REGEXP_SINK_STATE
Daniel Veillard4255d502002-04-16 15:50:10 +0000144} xmlRegStateType;
145
146typedef enum {
147 XML_REGEXP_MARK_NORMAL = 0,
148 XML_REGEXP_MARK_START,
149 XML_REGEXP_MARK_VISITED
150} xmlRegMarkedType;
151
152typedef struct _xmlRegRange xmlRegRange;
153typedef xmlRegRange *xmlRegRangePtr;
154
155struct _xmlRegRange {
Daniel Veillardf8b9de32003-11-24 14:27:26 +0000156 int neg; /* 0 normal, 1 not, 2 exclude */
Daniel Veillard4255d502002-04-16 15:50:10 +0000157 xmlRegAtomType type;
158 int start;
159 int end;
160 xmlChar *blockName;
161};
162
163typedef struct _xmlRegAtom xmlRegAtom;
164typedef xmlRegAtom *xmlRegAtomPtr;
165
166typedef struct _xmlAutomataState xmlRegState;
167typedef xmlRegState *xmlRegStatePtr;
168
169struct _xmlRegAtom {
170 int no;
171 xmlRegAtomType type;
172 xmlRegQuantType quant;
173 int min;
174 int max;
175
176 void *valuep;
Daniel Veillarda646cfd2002-09-17 21:50:03 +0000177 void *valuep2;
Daniel Veillard4255d502002-04-16 15:50:10 +0000178 int neg;
179 int codepoint;
180 xmlRegStatePtr start;
181 xmlRegStatePtr stop;
182 int maxRanges;
183 int nbRanges;
184 xmlRegRangePtr *ranges;
185 void *data;
186};
187
188typedef struct _xmlRegCounter xmlRegCounter;
189typedef xmlRegCounter *xmlRegCounterPtr;
190
191struct _xmlRegCounter {
192 int min;
193 int max;
194};
195
196typedef struct _xmlRegTrans xmlRegTrans;
197typedef xmlRegTrans *xmlRegTransPtr;
198
199struct _xmlRegTrans {
200 xmlRegAtomPtr atom;
201 int to;
202 int counter;
203 int count;
204};
205
206struct _xmlAutomataState {
207 xmlRegStateType type;
208 xmlRegMarkedType mark;
Daniel Veillard23e73572002-09-19 19:56:43 +0000209 xmlRegMarkedType reached;
Daniel Veillard4255d502002-04-16 15:50:10 +0000210 int no;
Daniel Veillard4255d502002-04-16 15:50:10 +0000211 int maxTrans;
212 int nbTrans;
213 xmlRegTrans *trans;
214};
215
216typedef struct _xmlAutomata xmlRegParserCtxt;
217typedef xmlRegParserCtxt *xmlRegParserCtxtPtr;
218
219struct _xmlAutomata {
220 xmlChar *string;
221 xmlChar *cur;
222
223 int error;
224 int neg;
225
226 xmlRegStatePtr start;
227 xmlRegStatePtr end;
228 xmlRegStatePtr state;
229
230 xmlRegAtomPtr atom;
231
232 int maxAtoms;
233 int nbAtoms;
234 xmlRegAtomPtr *atoms;
235
236 int maxStates;
237 int nbStates;
238 xmlRegStatePtr *states;
239
240 int maxCounters;
241 int nbCounters;
242 xmlRegCounter *counters;
Daniel Veillarde19fc232002-04-22 16:01:24 +0000243
244 int determinist;
Daniel Veillard4255d502002-04-16 15:50:10 +0000245};
246
247struct _xmlRegexp {
248 xmlChar *string;
249 int nbStates;
250 xmlRegStatePtr *states;
251 int nbAtoms;
252 xmlRegAtomPtr *atoms;
253 int nbCounters;
254 xmlRegCounter *counters;
Daniel Veillarde19fc232002-04-22 16:01:24 +0000255 int determinist;
Daniel Veillard23e73572002-09-19 19:56:43 +0000256 /*
257 * That's the compact form for determinists automatas
258 */
259 int nbstates;
260 int *compact;
Daniel Veillard118aed72002-09-24 14:13:13 +0000261 void **transdata;
Daniel Veillard23e73572002-09-19 19:56:43 +0000262 int nbstrings;
263 xmlChar **stringMap;
Daniel Veillard4255d502002-04-16 15:50:10 +0000264};
265
266typedef struct _xmlRegExecRollback xmlRegExecRollback;
267typedef xmlRegExecRollback *xmlRegExecRollbackPtr;
268
269struct _xmlRegExecRollback {
270 xmlRegStatePtr state;/* the current state */
271 int index; /* the index in the input stack */
272 int nextbranch; /* the next transition to explore in that state */
William M. Brackddf71d62004-05-06 04:17:26 +0000273 int *counts; /* save the automata state if it has some */
Daniel Veillard4255d502002-04-16 15:50:10 +0000274};
275
276typedef struct _xmlRegInputToken xmlRegInputToken;
277typedef xmlRegInputToken *xmlRegInputTokenPtr;
278
279struct _xmlRegInputToken {
280 xmlChar *value;
281 void *data;
282};
283
284struct _xmlRegExecCtxt {
285 int status; /* execution status != 0 indicate an error */
William M. Brackddf71d62004-05-06 04:17:26 +0000286 int determinist; /* did we find an indeterministic behaviour */
Daniel Veillard4255d502002-04-16 15:50:10 +0000287 xmlRegexpPtr comp; /* the compiled regexp */
288 xmlRegExecCallbacks callback;
289 void *data;
290
291 xmlRegStatePtr state;/* the current state */
292 int transno; /* the current transition on that state */
William M. Brackddf71d62004-05-06 04:17:26 +0000293 int transcount; /* the number of chars in char counted transitions */
Daniel Veillard4255d502002-04-16 15:50:10 +0000294
295 /*
296 * A stack of rollback states
297 */
298 int maxRollbacks;
299 int nbRollbacks;
300 xmlRegExecRollback *rollbacks;
301
302 /*
303 * The state of the automata if any
304 */
305 int *counts;
306
307 /*
308 * The input stack
309 */
310 int inputStackMax;
311 int inputStackNr;
312 int index;
313 int *charStack;
314 const xmlChar *inputString; /* when operating on characters */
315 xmlRegInputTokenPtr inputStack;/* when operating on strings */
316
Daniel Veillard7bd8b4b2005-01-07 13:56:19 +0000317 /*
318 * error handling
319 */
320 int errStateNo; /* the error state number */
321 xmlRegStatePtr errState; /* the error state */
322 xmlChar *errString; /* the string raising the error */
323 int *errCounts; /* counters at the error state */
Daniel Veillard4255d502002-04-16 15:50:10 +0000324};
325
Daniel Veillard441bc322002-04-20 17:38:48 +0000326#define REGEXP_ALL_COUNTER 0x123456
327#define REGEXP_ALL_LAX_COUNTER 0x123457
Daniel Veillard7646b182002-04-20 06:41:40 +0000328
Daniel Veillard4255d502002-04-16 15:50:10 +0000329static void xmlFAParseRegExp(xmlRegParserCtxtPtr ctxt, int top);
Daniel Veillard23e73572002-09-19 19:56:43 +0000330static void xmlRegFreeState(xmlRegStatePtr state);
331static void xmlRegFreeAtom(xmlRegAtomPtr atom);
Daniel Veillard4255d502002-04-16 15:50:10 +0000332
333/************************************************************************
Daniel Veillardff46a042003-10-08 08:53:17 +0000334 * *
335 * Regexp memory error handler *
336 * *
337 ************************************************************************/
338/**
339 * xmlRegexpErrMemory:
William M. Brackddf71d62004-05-06 04:17:26 +0000340 * @extra: extra information
Daniel Veillardff46a042003-10-08 08:53:17 +0000341 *
342 * Handle an out of memory condition
343 */
344static void
345xmlRegexpErrMemory(xmlRegParserCtxtPtr ctxt, const char *extra)
346{
347 const char *regexp = NULL;
348 if (ctxt != NULL) {
349 regexp = (const char *) ctxt->string;
350 ctxt->error = XML_ERR_NO_MEMORY;
351 }
Daniel Veillard659e71e2003-10-10 14:10:40 +0000352 __xmlRaiseError(NULL, NULL, NULL, NULL, NULL, XML_FROM_REGEXP,
Daniel Veillardff46a042003-10-08 08:53:17 +0000353 XML_ERR_NO_MEMORY, XML_ERR_FATAL, NULL, 0, extra,
354 regexp, NULL, 0, 0,
355 "Memory allocation failed : %s\n", extra);
356}
357
358/**
359 * xmlRegexpErrCompile:
William M. Brackddf71d62004-05-06 04:17:26 +0000360 * @extra: extra information
Daniel Veillardff46a042003-10-08 08:53:17 +0000361 *
William M. Brackddf71d62004-05-06 04:17:26 +0000362 * Handle a compilation failure
Daniel Veillardff46a042003-10-08 08:53:17 +0000363 */
364static void
365xmlRegexpErrCompile(xmlRegParserCtxtPtr ctxt, const char *extra)
366{
367 const char *regexp = NULL;
368 int idx = 0;
369
370 if (ctxt != NULL) {
371 regexp = (const char *) ctxt->string;
372 idx = ctxt->cur - ctxt->string;
373 ctxt->error = XML_REGEXP_COMPILE_ERROR;
374 }
Daniel Veillard659e71e2003-10-10 14:10:40 +0000375 __xmlRaiseError(NULL, NULL, NULL, NULL, NULL, XML_FROM_REGEXP,
Daniel Veillardff46a042003-10-08 08:53:17 +0000376 XML_REGEXP_COMPILE_ERROR, XML_ERR_FATAL, NULL, 0, extra,
377 regexp, NULL, idx, 0,
378 "failed to compile: %s\n", extra);
379}
380
381/************************************************************************
Daniel Veillard4255d502002-04-16 15:50:10 +0000382 * *
383 * Allocation/Deallocation *
384 * *
385 ************************************************************************/
386
Daniel Veillard23e73572002-09-19 19:56:43 +0000387static int xmlFAComputesDeterminism(xmlRegParserCtxtPtr ctxt);
Daniel Veillard4255d502002-04-16 15:50:10 +0000388/**
389 * xmlRegEpxFromParse:
390 * @ctxt: the parser context used to build it
391 *
William M. Brackddf71d62004-05-06 04:17:26 +0000392 * Allocate a new regexp and fill it with the result from the parser
Daniel Veillard4255d502002-04-16 15:50:10 +0000393 *
394 * Returns the new regexp or NULL in case of error
395 */
396static xmlRegexpPtr
397xmlRegEpxFromParse(xmlRegParserCtxtPtr ctxt) {
398 xmlRegexpPtr ret;
399
400 ret = (xmlRegexpPtr) xmlMalloc(sizeof(xmlRegexp));
Daniel Veillarda76fe5c2003-04-24 16:06:47 +0000401 if (ret == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +0000402 xmlRegexpErrMemory(ctxt, "compiling regexp");
Daniel Veillard4255d502002-04-16 15:50:10 +0000403 return(NULL);
Daniel Veillarda76fe5c2003-04-24 16:06:47 +0000404 }
Daniel Veillard4255d502002-04-16 15:50:10 +0000405 memset(ret, 0, sizeof(xmlRegexp));
406 ret->string = ctxt->string;
Daniel Veillard4255d502002-04-16 15:50:10 +0000407 ret->nbStates = ctxt->nbStates;
Daniel Veillard4255d502002-04-16 15:50:10 +0000408 ret->states = ctxt->states;
Daniel Veillard4255d502002-04-16 15:50:10 +0000409 ret->nbAtoms = ctxt->nbAtoms;
Daniel Veillard4255d502002-04-16 15:50:10 +0000410 ret->atoms = ctxt->atoms;
Daniel Veillard4255d502002-04-16 15:50:10 +0000411 ret->nbCounters = ctxt->nbCounters;
Daniel Veillard4255d502002-04-16 15:50:10 +0000412 ret->counters = ctxt->counters;
Daniel Veillarde19fc232002-04-22 16:01:24 +0000413 ret->determinist = ctxt->determinist;
Daniel Veillard23e73572002-09-19 19:56:43 +0000414
415 if ((ret->determinist != 0) &&
416 (ret->nbCounters == 0) &&
Daniel Veillard118aed72002-09-24 14:13:13 +0000417 (ret->atoms != NULL) &&
Daniel Veillard23e73572002-09-19 19:56:43 +0000418 (ret->atoms[0] != NULL) &&
419 (ret->atoms[0]->type == XML_REGEXP_STRING)) {
420 int i, j, nbstates = 0, nbatoms = 0;
421 int *stateRemap;
422 int *stringRemap;
423 int *transitions;
Daniel Veillard118aed72002-09-24 14:13:13 +0000424 void **transdata;
Daniel Veillard23e73572002-09-19 19:56:43 +0000425 xmlChar **stringMap;
426 xmlChar *value;
427
428 /*
429 * Switch to a compact representation
430 * 1/ counting the effective number of states left
William M. Brackddf71d62004-05-06 04:17:26 +0000431 * 2/ counting the unique number of atoms, and check that
Daniel Veillard23e73572002-09-19 19:56:43 +0000432 * they are all of the string type
433 * 3/ build a table state x atom for the transitions
434 */
435
436 stateRemap = xmlMalloc(ret->nbStates * sizeof(int));
Daniel Veillarda76fe5c2003-04-24 16:06:47 +0000437 if (stateRemap == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +0000438 xmlRegexpErrMemory(ctxt, "compiling regexp");
Daniel Veillarda76fe5c2003-04-24 16:06:47 +0000439 xmlFree(ret);
440 return(NULL);
441 }
Daniel Veillard23e73572002-09-19 19:56:43 +0000442 for (i = 0;i < ret->nbStates;i++) {
443 if (ret->states[i] != NULL) {
444 stateRemap[i] = nbstates;
445 nbstates++;
446 } else {
447 stateRemap[i] = -1;
448 }
449 }
450#ifdef DEBUG_COMPACTION
451 printf("Final: %d states\n", nbstates);
452#endif
453 stringMap = xmlMalloc(ret->nbAtoms * sizeof(char *));
Daniel Veillarda76fe5c2003-04-24 16:06:47 +0000454 if (stringMap == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +0000455 xmlRegexpErrMemory(ctxt, "compiling regexp");
Daniel Veillarda76fe5c2003-04-24 16:06:47 +0000456 xmlFree(stateRemap);
457 xmlFree(ret);
458 return(NULL);
459 }
Daniel Veillard23e73572002-09-19 19:56:43 +0000460 stringRemap = xmlMalloc(ret->nbAtoms * sizeof(int));
Daniel Veillarda76fe5c2003-04-24 16:06:47 +0000461 if (stringRemap == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +0000462 xmlRegexpErrMemory(ctxt, "compiling regexp");
Daniel Veillarda76fe5c2003-04-24 16:06:47 +0000463 xmlFree(stringMap);
464 xmlFree(stateRemap);
465 xmlFree(ret);
466 return(NULL);
467 }
Daniel Veillard23e73572002-09-19 19:56:43 +0000468 for (i = 0;i < ret->nbAtoms;i++) {
469 if ((ret->atoms[i]->type == XML_REGEXP_STRING) &&
470 (ret->atoms[i]->quant == XML_REGEXP_QUANT_ONCE)) {
471 value = ret->atoms[i]->valuep;
472 for (j = 0;j < nbatoms;j++) {
473 if (xmlStrEqual(stringMap[j], value)) {
474 stringRemap[i] = j;
475 break;
476 }
477 }
478 if (j >= nbatoms) {
479 stringRemap[i] = nbatoms;
480 stringMap[nbatoms] = xmlStrdup(value);
Daniel Veillarda76fe5c2003-04-24 16:06:47 +0000481 if (stringMap[nbatoms] == NULL) {
482 for (i = 0;i < nbatoms;i++)
483 xmlFree(stringMap[i]);
484 xmlFree(stringRemap);
485 xmlFree(stringMap);
486 xmlFree(stateRemap);
487 xmlFree(ret);
488 return(NULL);
489 }
Daniel Veillard23e73572002-09-19 19:56:43 +0000490 nbatoms++;
491 }
492 } else {
493 xmlFree(stateRemap);
494 xmlFree(stringRemap);
495 for (i = 0;i < nbatoms;i++)
496 xmlFree(stringMap[i]);
497 xmlFree(stringMap);
Daniel Veillarda76fe5c2003-04-24 16:06:47 +0000498 xmlFree(ret);
499 return(NULL);
Daniel Veillard23e73572002-09-19 19:56:43 +0000500 }
501 }
502#ifdef DEBUG_COMPACTION
503 printf("Final: %d atoms\n", nbatoms);
504#endif
Daniel Veillarda76fe5c2003-04-24 16:06:47 +0000505 transitions = (int *) xmlMalloc((nbstates + 1) *
506 (nbatoms + 1) * sizeof(int));
507 if (transitions == NULL) {
508 xmlFree(stateRemap);
509 xmlFree(stringRemap);
510 xmlFree(stringMap);
511 xmlFree(ret);
512 return(NULL);
513 }
514 memset(transitions, 0, (nbstates + 1) * (nbatoms + 1) * sizeof(int));
Daniel Veillard23e73572002-09-19 19:56:43 +0000515
516 /*
517 * Allocate the transition table. The first entry for each
William M. Brackddf71d62004-05-06 04:17:26 +0000518 * state corresponds to the state type.
Daniel Veillard23e73572002-09-19 19:56:43 +0000519 */
Daniel Veillard118aed72002-09-24 14:13:13 +0000520 transdata = NULL;
Daniel Veillard23e73572002-09-19 19:56:43 +0000521
522 for (i = 0;i < ret->nbStates;i++) {
523 int stateno, atomno, targetno, prev;
524 xmlRegStatePtr state;
525 xmlRegTransPtr trans;
526
527 stateno = stateRemap[i];
528 if (stateno == -1)
529 continue;
530 state = ret->states[i];
531
532 transitions[stateno * (nbatoms + 1)] = state->type;
533
534 for (j = 0;j < state->nbTrans;j++) {
535 trans = &(state->trans[j]);
536 if ((trans->to == -1) || (trans->atom == NULL))
537 continue;
538 atomno = stringRemap[trans->atom->no];
Daniel Veillard118aed72002-09-24 14:13:13 +0000539 if ((trans->atom->data != NULL) && (transdata == NULL)) {
540 transdata = (void **) xmlMalloc(nbstates * nbatoms *
541 sizeof(void *));
542 if (transdata != NULL)
543 memset(transdata, 0,
544 nbstates * nbatoms * sizeof(void *));
Daniel Veillarda76fe5c2003-04-24 16:06:47 +0000545 else {
Daniel Veillardff46a042003-10-08 08:53:17 +0000546 xmlRegexpErrMemory(ctxt, "compiling regexp");
Daniel Veillarda76fe5c2003-04-24 16:06:47 +0000547 break;
548 }
Daniel Veillard118aed72002-09-24 14:13:13 +0000549 }
Daniel Veillard23e73572002-09-19 19:56:43 +0000550 targetno = stateRemap[trans->to];
551 /*
William M. Brackddf71d62004-05-06 04:17:26 +0000552 * if the same atom can generate transitions to 2 different
Daniel Veillard23e73572002-09-19 19:56:43 +0000553 * states then it means the automata is not determinist and
554 * the compact form can't be used !
555 */
556 prev = transitions[stateno * (nbatoms + 1) + atomno + 1];
557 if (prev != 0) {
558 if (prev != targetno + 1) {
Daniel Veillard23e73572002-09-19 19:56:43 +0000559 ret->determinist = 0;
560#ifdef DEBUG_COMPACTION
561 printf("Indet: state %d trans %d, atom %d to %d : %d to %d\n",
562 i, j, trans->atom->no, trans->to, atomno, targetno);
563 printf(" previous to is %d\n", prev);
564#endif
565 ret->determinist = 0;
Daniel Veillard118aed72002-09-24 14:13:13 +0000566 if (transdata != NULL)
567 xmlFree(transdata);
Daniel Veillard23e73572002-09-19 19:56:43 +0000568 xmlFree(transitions);
569 xmlFree(stateRemap);
570 xmlFree(stringRemap);
571 for (i = 0;i < nbatoms;i++)
572 xmlFree(stringMap[i]);
573 xmlFree(stringMap);
Daniel Veillarda76fe5c2003-04-24 16:06:47 +0000574 goto not_determ;
Daniel Veillard23e73572002-09-19 19:56:43 +0000575 }
576 } else {
577#if 0
578 printf("State %d trans %d: atom %d to %d : %d to %d\n",
579 i, j, trans->atom->no, trans->to, atomno, targetno);
580#endif
581 transitions[stateno * (nbatoms + 1) + atomno + 1] =
Daniel Veillard118aed72002-09-24 14:13:13 +0000582 targetno + 1; /* to avoid 0 */
583 if (transdata != NULL)
584 transdata[stateno * nbatoms + atomno] =
585 trans->atom->data;
Daniel Veillard23e73572002-09-19 19:56:43 +0000586 }
587 }
588 }
589 ret->determinist = 1;
590#ifdef DEBUG_COMPACTION
591 /*
592 * Debug
593 */
594 for (i = 0;i < nbstates;i++) {
595 for (j = 0;j < nbatoms + 1;j++) {
596 printf("%02d ", transitions[i * (nbatoms + 1) + j]);
597 }
598 printf("\n");
599 }
600 printf("\n");
601#endif
602 /*
603 * Cleanup of the old data
604 */
605 if (ret->states != NULL) {
606 for (i = 0;i < ret->nbStates;i++)
607 xmlRegFreeState(ret->states[i]);
608 xmlFree(ret->states);
609 }
610 ret->states = NULL;
611 ret->nbStates = 0;
612 if (ret->atoms != NULL) {
613 for (i = 0;i < ret->nbAtoms;i++)
614 xmlRegFreeAtom(ret->atoms[i]);
615 xmlFree(ret->atoms);
616 }
617 ret->atoms = NULL;
618 ret->nbAtoms = 0;
619
620 ret->compact = transitions;
Daniel Veillard118aed72002-09-24 14:13:13 +0000621 ret->transdata = transdata;
Daniel Veillard23e73572002-09-19 19:56:43 +0000622 ret->stringMap = stringMap;
623 ret->nbstrings = nbatoms;
624 ret->nbstates = nbstates;
625 xmlFree(stateRemap);
626 xmlFree(stringRemap);
627 }
Daniel Veillarda76fe5c2003-04-24 16:06:47 +0000628not_determ:
629 ctxt->string = NULL;
630 ctxt->nbStates = 0;
631 ctxt->states = NULL;
632 ctxt->nbAtoms = 0;
633 ctxt->atoms = NULL;
634 ctxt->nbCounters = 0;
635 ctxt->counters = NULL;
Daniel Veillard4255d502002-04-16 15:50:10 +0000636 return(ret);
637}
638
639/**
640 * xmlRegNewParserCtxt:
641 * @string: the string to parse
642 *
643 * Allocate a new regexp parser context
644 *
645 * Returns the new context or NULL in case of error
646 */
647static xmlRegParserCtxtPtr
648xmlRegNewParserCtxt(const xmlChar *string) {
649 xmlRegParserCtxtPtr ret;
650
651 ret = (xmlRegParserCtxtPtr) xmlMalloc(sizeof(xmlRegParserCtxt));
652 if (ret == NULL)
653 return(NULL);
654 memset(ret, 0, sizeof(xmlRegParserCtxt));
655 if (string != NULL)
656 ret->string = xmlStrdup(string);
657 ret->cur = ret->string;
658 ret->neg = 0;
659 ret->error = 0;
Daniel Veillarde19fc232002-04-22 16:01:24 +0000660 ret->determinist = -1;
Daniel Veillard4255d502002-04-16 15:50:10 +0000661 return(ret);
662}
663
664/**
665 * xmlRegNewRange:
666 * @ctxt: the regexp parser context
667 * @neg: is that negative
668 * @type: the type of range
669 * @start: the start codepoint
670 * @end: the end codepoint
671 *
672 * Allocate a new regexp range
673 *
674 * Returns the new range or NULL in case of error
675 */
676static xmlRegRangePtr
677xmlRegNewRange(xmlRegParserCtxtPtr ctxt,
678 int neg, xmlRegAtomType type, int start, int end) {
679 xmlRegRangePtr ret;
680
681 ret = (xmlRegRangePtr) xmlMalloc(sizeof(xmlRegRange));
682 if (ret == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +0000683 xmlRegexpErrMemory(ctxt, "allocating range");
Daniel Veillard4255d502002-04-16 15:50:10 +0000684 return(NULL);
685 }
686 ret->neg = neg;
687 ret->type = type;
688 ret->start = start;
689 ret->end = end;
690 return(ret);
691}
692
693/**
694 * xmlRegFreeRange:
695 * @range: the regexp range
696 *
697 * Free a regexp range
698 */
699static void
700xmlRegFreeRange(xmlRegRangePtr range) {
701 if (range == NULL)
702 return;
703
704 if (range->blockName != NULL)
705 xmlFree(range->blockName);
706 xmlFree(range);
707}
708
709/**
710 * xmlRegNewAtom:
711 * @ctxt: the regexp parser context
712 * @type: the type of atom
713 *
714 * Allocate a new regexp range
715 *
716 * Returns the new atom or NULL in case of error
717 */
718static xmlRegAtomPtr
719xmlRegNewAtom(xmlRegParserCtxtPtr ctxt, xmlRegAtomType type) {
720 xmlRegAtomPtr ret;
721
722 ret = (xmlRegAtomPtr) xmlMalloc(sizeof(xmlRegAtom));
723 if (ret == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +0000724 xmlRegexpErrMemory(ctxt, "allocating atom");
Daniel Veillard4255d502002-04-16 15:50:10 +0000725 return(NULL);
726 }
727 memset(ret, 0, sizeof(xmlRegAtom));
728 ret->type = type;
729 ret->quant = XML_REGEXP_QUANT_ONCE;
730 ret->min = 0;
731 ret->max = 0;
732 return(ret);
733}
734
735/**
736 * xmlRegFreeAtom:
737 * @atom: the regexp atom
738 *
739 * Free a regexp atom
740 */
741static void
742xmlRegFreeAtom(xmlRegAtomPtr atom) {
743 int i;
744
745 if (atom == NULL)
746 return;
747
748 for (i = 0;i < atom->nbRanges;i++)
749 xmlRegFreeRange(atom->ranges[i]);
750 if (atom->ranges != NULL)
751 xmlFree(atom->ranges);
752 if (atom->type == XML_REGEXP_STRING)
753 xmlFree(atom->valuep);
754 xmlFree(atom);
755}
756
757static xmlRegStatePtr
758xmlRegNewState(xmlRegParserCtxtPtr ctxt) {
759 xmlRegStatePtr ret;
760
761 ret = (xmlRegStatePtr) xmlMalloc(sizeof(xmlRegState));
762 if (ret == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +0000763 xmlRegexpErrMemory(ctxt, "allocating state");
Daniel Veillard4255d502002-04-16 15:50:10 +0000764 return(NULL);
765 }
766 memset(ret, 0, sizeof(xmlRegState));
767 ret->type = XML_REGEXP_TRANS_STATE;
768 ret->mark = XML_REGEXP_MARK_NORMAL;
769 return(ret);
770}
771
772/**
773 * xmlRegFreeState:
774 * @state: the regexp state
775 *
776 * Free a regexp state
777 */
778static void
779xmlRegFreeState(xmlRegStatePtr state) {
780 if (state == NULL)
781 return;
782
783 if (state->trans != NULL)
784 xmlFree(state->trans);
785 xmlFree(state);
786}
787
788/**
789 * xmlRegFreeParserCtxt:
790 * @ctxt: the regexp parser context
791 *
792 * Free a regexp parser context
793 */
794static void
795xmlRegFreeParserCtxt(xmlRegParserCtxtPtr ctxt) {
796 int i;
797 if (ctxt == NULL)
798 return;
799
800 if (ctxt->string != NULL)
801 xmlFree(ctxt->string);
802 if (ctxt->states != NULL) {
803 for (i = 0;i < ctxt->nbStates;i++)
804 xmlRegFreeState(ctxt->states[i]);
805 xmlFree(ctxt->states);
806 }
807 if (ctxt->atoms != NULL) {
808 for (i = 0;i < ctxt->nbAtoms;i++)
809 xmlRegFreeAtom(ctxt->atoms[i]);
810 xmlFree(ctxt->atoms);
811 }
812 if (ctxt->counters != NULL)
813 xmlFree(ctxt->counters);
814 xmlFree(ctxt);
815}
816
817/************************************************************************
818 * *
819 * Display of Data structures *
820 * *
821 ************************************************************************/
822
823static void
824xmlRegPrintAtomType(FILE *output, xmlRegAtomType type) {
825 switch (type) {
826 case XML_REGEXP_EPSILON:
827 fprintf(output, "epsilon "); break;
828 case XML_REGEXP_CHARVAL:
829 fprintf(output, "charval "); break;
830 case XML_REGEXP_RANGES:
831 fprintf(output, "ranges "); break;
832 case XML_REGEXP_SUBREG:
833 fprintf(output, "subexpr "); break;
834 case XML_REGEXP_STRING:
835 fprintf(output, "string "); break;
836 case XML_REGEXP_ANYCHAR:
837 fprintf(output, "anychar "); break;
838 case XML_REGEXP_ANYSPACE:
839 fprintf(output, "anyspace "); break;
840 case XML_REGEXP_NOTSPACE:
841 fprintf(output, "notspace "); break;
842 case XML_REGEXP_INITNAME:
843 fprintf(output, "initname "); break;
844 case XML_REGEXP_NOTINITNAME:
845 fprintf(output, "notinitname "); break;
846 case XML_REGEXP_NAMECHAR:
847 fprintf(output, "namechar "); break;
848 case XML_REGEXP_NOTNAMECHAR:
849 fprintf(output, "notnamechar "); break;
850 case XML_REGEXP_DECIMAL:
851 fprintf(output, "decimal "); break;
852 case XML_REGEXP_NOTDECIMAL:
853 fprintf(output, "notdecimal "); break;
854 case XML_REGEXP_REALCHAR:
855 fprintf(output, "realchar "); break;
856 case XML_REGEXP_NOTREALCHAR:
857 fprintf(output, "notrealchar "); break;
858 case XML_REGEXP_LETTER:
859 fprintf(output, "LETTER "); break;
860 case XML_REGEXP_LETTER_UPPERCASE:
861 fprintf(output, "LETTER_UPPERCASE "); break;
862 case XML_REGEXP_LETTER_LOWERCASE:
863 fprintf(output, "LETTER_LOWERCASE "); break;
864 case XML_REGEXP_LETTER_TITLECASE:
865 fprintf(output, "LETTER_TITLECASE "); break;
866 case XML_REGEXP_LETTER_MODIFIER:
867 fprintf(output, "LETTER_MODIFIER "); break;
868 case XML_REGEXP_LETTER_OTHERS:
869 fprintf(output, "LETTER_OTHERS "); break;
870 case XML_REGEXP_MARK:
871 fprintf(output, "MARK "); break;
872 case XML_REGEXP_MARK_NONSPACING:
873 fprintf(output, "MARK_NONSPACING "); break;
874 case XML_REGEXP_MARK_SPACECOMBINING:
875 fprintf(output, "MARK_SPACECOMBINING "); break;
876 case XML_REGEXP_MARK_ENCLOSING:
877 fprintf(output, "MARK_ENCLOSING "); break;
878 case XML_REGEXP_NUMBER:
879 fprintf(output, "NUMBER "); break;
880 case XML_REGEXP_NUMBER_DECIMAL:
881 fprintf(output, "NUMBER_DECIMAL "); break;
882 case XML_REGEXP_NUMBER_LETTER:
883 fprintf(output, "NUMBER_LETTER "); break;
884 case XML_REGEXP_NUMBER_OTHERS:
885 fprintf(output, "NUMBER_OTHERS "); break;
886 case XML_REGEXP_PUNCT:
887 fprintf(output, "PUNCT "); break;
888 case XML_REGEXP_PUNCT_CONNECTOR:
889 fprintf(output, "PUNCT_CONNECTOR "); break;
890 case XML_REGEXP_PUNCT_DASH:
891 fprintf(output, "PUNCT_DASH "); break;
892 case XML_REGEXP_PUNCT_OPEN:
893 fprintf(output, "PUNCT_OPEN "); break;
894 case XML_REGEXP_PUNCT_CLOSE:
895 fprintf(output, "PUNCT_CLOSE "); break;
896 case XML_REGEXP_PUNCT_INITQUOTE:
897 fprintf(output, "PUNCT_INITQUOTE "); break;
898 case XML_REGEXP_PUNCT_FINQUOTE:
899 fprintf(output, "PUNCT_FINQUOTE "); break;
900 case XML_REGEXP_PUNCT_OTHERS:
901 fprintf(output, "PUNCT_OTHERS "); break;
902 case XML_REGEXP_SEPAR:
903 fprintf(output, "SEPAR "); break;
904 case XML_REGEXP_SEPAR_SPACE:
905 fprintf(output, "SEPAR_SPACE "); break;
906 case XML_REGEXP_SEPAR_LINE:
907 fprintf(output, "SEPAR_LINE "); break;
908 case XML_REGEXP_SEPAR_PARA:
909 fprintf(output, "SEPAR_PARA "); break;
910 case XML_REGEXP_SYMBOL:
911 fprintf(output, "SYMBOL "); break;
912 case XML_REGEXP_SYMBOL_MATH:
913 fprintf(output, "SYMBOL_MATH "); break;
914 case XML_REGEXP_SYMBOL_CURRENCY:
915 fprintf(output, "SYMBOL_CURRENCY "); break;
916 case XML_REGEXP_SYMBOL_MODIFIER:
917 fprintf(output, "SYMBOL_MODIFIER "); break;
918 case XML_REGEXP_SYMBOL_OTHERS:
919 fprintf(output, "SYMBOL_OTHERS "); break;
920 case XML_REGEXP_OTHER:
921 fprintf(output, "OTHER "); break;
922 case XML_REGEXP_OTHER_CONTROL:
923 fprintf(output, "OTHER_CONTROL "); break;
924 case XML_REGEXP_OTHER_FORMAT:
925 fprintf(output, "OTHER_FORMAT "); break;
926 case XML_REGEXP_OTHER_PRIVATE:
927 fprintf(output, "OTHER_PRIVATE "); break;
928 case XML_REGEXP_OTHER_NA:
929 fprintf(output, "OTHER_NA "); break;
930 case XML_REGEXP_BLOCK_NAME:
931 fprintf(output, "BLOCK "); break;
932 }
933}
934
935static void
936xmlRegPrintQuantType(FILE *output, xmlRegQuantType type) {
937 switch (type) {
938 case XML_REGEXP_QUANT_EPSILON:
939 fprintf(output, "epsilon "); break;
940 case XML_REGEXP_QUANT_ONCE:
941 fprintf(output, "once "); break;
942 case XML_REGEXP_QUANT_OPT:
943 fprintf(output, "? "); break;
944 case XML_REGEXP_QUANT_MULT:
945 fprintf(output, "* "); break;
946 case XML_REGEXP_QUANT_PLUS:
947 fprintf(output, "+ "); break;
948 case XML_REGEXP_QUANT_RANGE:
949 fprintf(output, "range "); break;
Daniel Veillard7646b182002-04-20 06:41:40 +0000950 case XML_REGEXP_QUANT_ONCEONLY:
951 fprintf(output, "onceonly "); break;
952 case XML_REGEXP_QUANT_ALL:
953 fprintf(output, "all "); break;
Daniel Veillard4255d502002-04-16 15:50:10 +0000954 }
955}
956static void
957xmlRegPrintRange(FILE *output, xmlRegRangePtr range) {
958 fprintf(output, " range: ");
959 if (range->neg)
960 fprintf(output, "negative ");
961 xmlRegPrintAtomType(output, range->type);
962 fprintf(output, "%c - %c\n", range->start, range->end);
963}
964
965static void
966xmlRegPrintAtom(FILE *output, xmlRegAtomPtr atom) {
967 fprintf(output, " atom: ");
968 if (atom == NULL) {
969 fprintf(output, "NULL\n");
970 return;
971 }
972 xmlRegPrintAtomType(output, atom->type);
973 xmlRegPrintQuantType(output, atom->quant);
974 if (atom->quant == XML_REGEXP_QUANT_RANGE)
975 fprintf(output, "%d-%d ", atom->min, atom->max);
976 if (atom->type == XML_REGEXP_STRING)
977 fprintf(output, "'%s' ", (char *) atom->valuep);
978 if (atom->type == XML_REGEXP_CHARVAL)
979 fprintf(output, "char %c\n", atom->codepoint);
980 else if (atom->type == XML_REGEXP_RANGES) {
981 int i;
982 fprintf(output, "%d entries\n", atom->nbRanges);
983 for (i = 0; i < atom->nbRanges;i++)
984 xmlRegPrintRange(output, atom->ranges[i]);
985 } else if (atom->type == XML_REGEXP_SUBREG) {
986 fprintf(output, "start %d end %d\n", atom->start->no, atom->stop->no);
987 } else {
988 fprintf(output, "\n");
989 }
990}
991
992static void
993xmlRegPrintTrans(FILE *output, xmlRegTransPtr trans) {
994 fprintf(output, " trans: ");
995 if (trans == NULL) {
996 fprintf(output, "NULL\n");
997 return;
998 }
999 if (trans->to < 0) {
1000 fprintf(output, "removed\n");
1001 return;
1002 }
1003 if (trans->counter >= 0) {
1004 fprintf(output, "counted %d, ", trans->counter);
1005 }
Daniel Veillard8a001f62002-04-20 07:24:11 +00001006 if (trans->count == REGEXP_ALL_COUNTER) {
1007 fprintf(output, "all transition, ");
1008 } else if (trans->count >= 0) {
Daniel Veillard4255d502002-04-16 15:50:10 +00001009 fprintf(output, "count based %d, ", trans->count);
1010 }
1011 if (trans->atom == NULL) {
1012 fprintf(output, "epsilon to %d\n", trans->to);
1013 return;
1014 }
1015 if (trans->atom->type == XML_REGEXP_CHARVAL)
1016 fprintf(output, "char %c ", trans->atom->codepoint);
1017 fprintf(output, "atom %d, to %d\n", trans->atom->no, trans->to);
1018}
1019
1020static void
1021xmlRegPrintState(FILE *output, xmlRegStatePtr state) {
1022 int i;
1023
1024 fprintf(output, " state: ");
1025 if (state == NULL) {
1026 fprintf(output, "NULL\n");
1027 return;
1028 }
1029 if (state->type == XML_REGEXP_START_STATE)
1030 fprintf(output, "START ");
1031 if (state->type == XML_REGEXP_FINAL_STATE)
1032 fprintf(output, "FINAL ");
1033
1034 fprintf(output, "%d, %d transitions:\n", state->no, state->nbTrans);
1035 for (i = 0;i < state->nbTrans; i++) {
1036 xmlRegPrintTrans(output, &(state->trans[i]));
1037 }
1038}
1039
Daniel Veillard23e73572002-09-19 19:56:43 +00001040#ifdef DEBUG_REGEXP_GRAPH
Daniel Veillard4255d502002-04-16 15:50:10 +00001041static void
1042xmlRegPrintCtxt(FILE *output, xmlRegParserCtxtPtr ctxt) {
1043 int i;
1044
1045 fprintf(output, " ctxt: ");
1046 if (ctxt == NULL) {
1047 fprintf(output, "NULL\n");
1048 return;
1049 }
1050 fprintf(output, "'%s' ", ctxt->string);
1051 if (ctxt->error)
1052 fprintf(output, "error ");
1053 if (ctxt->neg)
1054 fprintf(output, "neg ");
1055 fprintf(output, "\n");
1056 fprintf(output, "%d atoms:\n", ctxt->nbAtoms);
1057 for (i = 0;i < ctxt->nbAtoms; i++) {
1058 fprintf(output, " %02d ", i);
1059 xmlRegPrintAtom(output, ctxt->atoms[i]);
1060 }
1061 if (ctxt->atom != NULL) {
1062 fprintf(output, "current atom:\n");
1063 xmlRegPrintAtom(output, ctxt->atom);
1064 }
1065 fprintf(output, "%d states:", ctxt->nbStates);
1066 if (ctxt->start != NULL)
1067 fprintf(output, " start: %d", ctxt->start->no);
1068 if (ctxt->end != NULL)
1069 fprintf(output, " end: %d", ctxt->end->no);
1070 fprintf(output, "\n");
1071 for (i = 0;i < ctxt->nbStates; i++) {
1072 xmlRegPrintState(output, ctxt->states[i]);
1073 }
1074 fprintf(output, "%d counters:\n", ctxt->nbCounters);
1075 for (i = 0;i < ctxt->nbCounters; i++) {
1076 fprintf(output, " %d: min %d max %d\n", i, ctxt->counters[i].min,
1077 ctxt->counters[i].max);
1078 }
1079}
Daniel Veillard23e73572002-09-19 19:56:43 +00001080#endif
Daniel Veillard4255d502002-04-16 15:50:10 +00001081
1082/************************************************************************
1083 * *
1084 * Finite Automata structures manipulations *
1085 * *
1086 ************************************************************************/
1087
1088static void
1089xmlRegAtomAddRange(xmlRegParserCtxtPtr ctxt, xmlRegAtomPtr atom,
1090 int neg, xmlRegAtomType type, int start, int end,
1091 xmlChar *blockName) {
1092 xmlRegRangePtr range;
1093
1094 if (atom == NULL) {
1095 ERROR("add range: atom is NULL");
1096 return;
1097 }
1098 if (atom->type != XML_REGEXP_RANGES) {
1099 ERROR("add range: atom is not ranges");
1100 return;
1101 }
1102 if (atom->maxRanges == 0) {
1103 atom->maxRanges = 4;
1104 atom->ranges = (xmlRegRangePtr *) xmlMalloc(atom->maxRanges *
1105 sizeof(xmlRegRangePtr));
1106 if (atom->ranges == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +00001107 xmlRegexpErrMemory(ctxt, "adding ranges");
Daniel Veillard4255d502002-04-16 15:50:10 +00001108 atom->maxRanges = 0;
1109 return;
1110 }
1111 } else if (atom->nbRanges >= atom->maxRanges) {
1112 xmlRegRangePtr *tmp;
1113 atom->maxRanges *= 2;
1114 tmp = (xmlRegRangePtr *) xmlRealloc(atom->ranges, atom->maxRanges *
1115 sizeof(xmlRegRangePtr));
1116 if (tmp == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +00001117 xmlRegexpErrMemory(ctxt, "adding ranges");
Daniel Veillard4255d502002-04-16 15:50:10 +00001118 atom->maxRanges /= 2;
1119 return;
1120 }
1121 atom->ranges = tmp;
1122 }
1123 range = xmlRegNewRange(ctxt, neg, type, start, end);
1124 if (range == NULL)
1125 return;
1126 range->blockName = blockName;
1127 atom->ranges[atom->nbRanges++] = range;
1128
1129}
1130
1131static int
1132xmlRegGetCounter(xmlRegParserCtxtPtr ctxt) {
1133 if (ctxt->maxCounters == 0) {
1134 ctxt->maxCounters = 4;
1135 ctxt->counters = (xmlRegCounter *) xmlMalloc(ctxt->maxCounters *
1136 sizeof(xmlRegCounter));
1137 if (ctxt->counters == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +00001138 xmlRegexpErrMemory(ctxt, "allocating counter");
Daniel Veillard4255d502002-04-16 15:50:10 +00001139 ctxt->maxCounters = 0;
1140 return(-1);
1141 }
1142 } else if (ctxt->nbCounters >= ctxt->maxCounters) {
1143 xmlRegCounter *tmp;
1144 ctxt->maxCounters *= 2;
1145 tmp = (xmlRegCounter *) xmlRealloc(ctxt->counters, ctxt->maxCounters *
1146 sizeof(xmlRegCounter));
1147 if (tmp == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +00001148 xmlRegexpErrMemory(ctxt, "allocating counter");
Daniel Veillard4255d502002-04-16 15:50:10 +00001149 ctxt->maxCounters /= 2;
1150 return(-1);
1151 }
1152 ctxt->counters = tmp;
1153 }
1154 ctxt->counters[ctxt->nbCounters].min = -1;
1155 ctxt->counters[ctxt->nbCounters].max = -1;
1156 return(ctxt->nbCounters++);
1157}
1158
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00001159static int
Daniel Veillard4255d502002-04-16 15:50:10 +00001160xmlRegAtomPush(xmlRegParserCtxtPtr ctxt, xmlRegAtomPtr atom) {
1161 if (atom == NULL) {
1162 ERROR("atom push: atom is NULL");
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00001163 return(-1);
Daniel Veillard4255d502002-04-16 15:50:10 +00001164 }
1165 if (ctxt->maxAtoms == 0) {
1166 ctxt->maxAtoms = 4;
1167 ctxt->atoms = (xmlRegAtomPtr *) xmlMalloc(ctxt->maxAtoms *
1168 sizeof(xmlRegAtomPtr));
1169 if (ctxt->atoms == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +00001170 xmlRegexpErrMemory(ctxt, "pushing atom");
Daniel Veillard4255d502002-04-16 15:50:10 +00001171 ctxt->maxAtoms = 0;
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00001172 return(-1);
Daniel Veillard4255d502002-04-16 15:50:10 +00001173 }
1174 } else if (ctxt->nbAtoms >= ctxt->maxAtoms) {
1175 xmlRegAtomPtr *tmp;
1176 ctxt->maxAtoms *= 2;
1177 tmp = (xmlRegAtomPtr *) xmlRealloc(ctxt->atoms, ctxt->maxAtoms *
1178 sizeof(xmlRegAtomPtr));
1179 if (tmp == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +00001180 xmlRegexpErrMemory(ctxt, "allocating counter");
Daniel Veillard4255d502002-04-16 15:50:10 +00001181 ctxt->maxAtoms /= 2;
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00001182 return(-1);
Daniel Veillard4255d502002-04-16 15:50:10 +00001183 }
1184 ctxt->atoms = tmp;
1185 }
1186 atom->no = ctxt->nbAtoms;
1187 ctxt->atoms[ctxt->nbAtoms++] = atom;
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00001188 return(0);
Daniel Veillard4255d502002-04-16 15:50:10 +00001189}
1190
1191static void
1192xmlRegStateAddTrans(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr state,
1193 xmlRegAtomPtr atom, xmlRegStatePtr target,
1194 int counter, int count) {
William M. Brackf9b5fa22004-05-10 07:52:15 +00001195
1196 int nrtrans;
1197
Daniel Veillard4255d502002-04-16 15:50:10 +00001198 if (state == NULL) {
1199 ERROR("add state: state is NULL");
1200 return;
1201 }
1202 if (target == NULL) {
1203 ERROR("add state: target is NULL");
1204 return;
1205 }
William M. Brackf9b5fa22004-05-10 07:52:15 +00001206 /*
1207 * Other routines follow the philosophy 'When in doubt, add a transition'
1208 * so we check here whether such a transition is already present and, if
1209 * so, silently ignore this request.
1210 */
1211
1212 for (nrtrans=0; nrtrans<state->nbTrans; nrtrans++) {
1213 if ((state->trans[nrtrans].atom == atom) &&
1214 (state->trans[nrtrans].to == target->no) &&
1215 (state->trans[nrtrans].counter == counter) &&
1216 (state->trans[nrtrans].count == count)) {
1217#ifdef DEBUG_REGEXP_GRAPH
1218 printf("Ignoring duplicate transition from %d to %d\n",
1219 state->no, target->no);
1220#endif
1221 return;
1222 }
1223 }
1224
Daniel Veillard4255d502002-04-16 15:50:10 +00001225 if (state->maxTrans == 0) {
1226 state->maxTrans = 4;
1227 state->trans = (xmlRegTrans *) xmlMalloc(state->maxTrans *
1228 sizeof(xmlRegTrans));
1229 if (state->trans == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +00001230 xmlRegexpErrMemory(ctxt, "adding transition");
Daniel Veillard4255d502002-04-16 15:50:10 +00001231 state->maxTrans = 0;
1232 return;
1233 }
1234 } else if (state->nbTrans >= state->maxTrans) {
1235 xmlRegTrans *tmp;
1236 state->maxTrans *= 2;
1237 tmp = (xmlRegTrans *) xmlRealloc(state->trans, state->maxTrans *
1238 sizeof(xmlRegTrans));
1239 if (tmp == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +00001240 xmlRegexpErrMemory(ctxt, "adding transition");
Daniel Veillard4255d502002-04-16 15:50:10 +00001241 state->maxTrans /= 2;
1242 return;
1243 }
1244 state->trans = tmp;
1245 }
1246#ifdef DEBUG_REGEXP_GRAPH
1247 printf("Add trans from %d to %d ", state->no, target->no);
Daniel Veillard8a001f62002-04-20 07:24:11 +00001248 if (count == REGEXP_ALL_COUNTER)
Daniel Veillard2cbf5962004-03-31 15:50:43 +00001249 printf("all transition\n");
Daniel Veillard4402ab42002-09-12 16:02:56 +00001250 else if (count >= 0)
Daniel Veillard2cbf5962004-03-31 15:50:43 +00001251 printf("count based %d\n", count);
Daniel Veillard4255d502002-04-16 15:50:10 +00001252 else if (counter >= 0)
Daniel Veillard2cbf5962004-03-31 15:50:43 +00001253 printf("counted %d\n", counter);
Daniel Veillard4255d502002-04-16 15:50:10 +00001254 else if (atom == NULL)
Daniel Veillard2cbf5962004-03-31 15:50:43 +00001255 printf("epsilon transition\n");
1256 else if (atom != NULL)
1257 xmlRegPrintAtom(stdout, atom);
Daniel Veillard4255d502002-04-16 15:50:10 +00001258#endif
1259
1260 state->trans[state->nbTrans].atom = atom;
1261 state->trans[state->nbTrans].to = target->no;
1262 state->trans[state->nbTrans].counter = counter;
1263 state->trans[state->nbTrans].count = count;
1264 state->nbTrans++;
1265}
1266
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00001267static int
Daniel Veillard4255d502002-04-16 15:50:10 +00001268xmlRegStatePush(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr state) {
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00001269 if (state == NULL) return(-1);
Daniel Veillard4255d502002-04-16 15:50:10 +00001270 if (ctxt->maxStates == 0) {
1271 ctxt->maxStates = 4;
1272 ctxt->states = (xmlRegStatePtr *) xmlMalloc(ctxt->maxStates *
1273 sizeof(xmlRegStatePtr));
1274 if (ctxt->states == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +00001275 xmlRegexpErrMemory(ctxt, "adding state");
Daniel Veillard4255d502002-04-16 15:50:10 +00001276 ctxt->maxStates = 0;
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00001277 return(-1);
Daniel Veillard4255d502002-04-16 15:50:10 +00001278 }
1279 } else if (ctxt->nbStates >= ctxt->maxStates) {
1280 xmlRegStatePtr *tmp;
1281 ctxt->maxStates *= 2;
1282 tmp = (xmlRegStatePtr *) xmlRealloc(ctxt->states, ctxt->maxStates *
1283 sizeof(xmlRegStatePtr));
1284 if (tmp == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +00001285 xmlRegexpErrMemory(ctxt, "adding state");
Daniel Veillard4255d502002-04-16 15:50:10 +00001286 ctxt->maxStates /= 2;
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00001287 return(-1);
Daniel Veillard4255d502002-04-16 15:50:10 +00001288 }
1289 ctxt->states = tmp;
1290 }
1291 state->no = ctxt->nbStates;
1292 ctxt->states[ctxt->nbStates++] = state;
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00001293 return(0);
Daniel Veillard4255d502002-04-16 15:50:10 +00001294}
1295
1296/**
Daniel Veillard7646b182002-04-20 06:41:40 +00001297 * xmlFAGenerateAllTransition:
Daniel Veillard441bc322002-04-20 17:38:48 +00001298 * @ctxt: a regexp parser context
1299 * @from: the from state
1300 * @to: the target state or NULL for building a new one
1301 * @lax:
Daniel Veillard7646b182002-04-20 06:41:40 +00001302 *
1303 */
1304static void
1305xmlFAGenerateAllTransition(xmlRegParserCtxtPtr ctxt,
Daniel Veillard441bc322002-04-20 17:38:48 +00001306 xmlRegStatePtr from, xmlRegStatePtr to,
1307 int lax) {
Daniel Veillard7646b182002-04-20 06:41:40 +00001308 if (to == NULL) {
1309 to = xmlRegNewState(ctxt);
1310 xmlRegStatePush(ctxt, to);
1311 ctxt->state = to;
1312 }
Daniel Veillard441bc322002-04-20 17:38:48 +00001313 if (lax)
1314 xmlRegStateAddTrans(ctxt, from, NULL, to, -1, REGEXP_ALL_LAX_COUNTER);
1315 else
1316 xmlRegStateAddTrans(ctxt, from, NULL, to, -1, REGEXP_ALL_COUNTER);
Daniel Veillard7646b182002-04-20 06:41:40 +00001317}
1318
1319/**
Daniel Veillard4255d502002-04-16 15:50:10 +00001320 * xmlFAGenerateEpsilonTransition:
Daniel Veillard441bc322002-04-20 17:38:48 +00001321 * @ctxt: a regexp parser context
1322 * @from: the from state
1323 * @to: the target state or NULL for building a new one
Daniel Veillard4255d502002-04-16 15:50:10 +00001324 *
1325 */
1326static void
1327xmlFAGenerateEpsilonTransition(xmlRegParserCtxtPtr ctxt,
1328 xmlRegStatePtr from, xmlRegStatePtr to) {
1329 if (to == NULL) {
1330 to = xmlRegNewState(ctxt);
1331 xmlRegStatePush(ctxt, to);
1332 ctxt->state = to;
1333 }
1334 xmlRegStateAddTrans(ctxt, from, NULL, to, -1, -1);
1335}
1336
1337/**
1338 * xmlFAGenerateCountedEpsilonTransition:
Daniel Veillard441bc322002-04-20 17:38:48 +00001339 * @ctxt: a regexp parser context
1340 * @from: the from state
1341 * @to: the target state or NULL for building a new one
Daniel Veillard4255d502002-04-16 15:50:10 +00001342 * counter: the counter for that transition
1343 *
1344 */
1345static void
1346xmlFAGenerateCountedEpsilonTransition(xmlRegParserCtxtPtr ctxt,
1347 xmlRegStatePtr from, xmlRegStatePtr to, int counter) {
1348 if (to == NULL) {
1349 to = xmlRegNewState(ctxt);
1350 xmlRegStatePush(ctxt, to);
1351 ctxt->state = to;
1352 }
1353 xmlRegStateAddTrans(ctxt, from, NULL, to, counter, -1);
1354}
1355
1356/**
1357 * xmlFAGenerateCountedTransition:
Daniel Veillard441bc322002-04-20 17:38:48 +00001358 * @ctxt: a regexp parser context
1359 * @from: the from state
1360 * @to: the target state or NULL for building a new one
Daniel Veillard4255d502002-04-16 15:50:10 +00001361 * counter: the counter for that transition
1362 *
1363 */
1364static void
1365xmlFAGenerateCountedTransition(xmlRegParserCtxtPtr ctxt,
1366 xmlRegStatePtr from, xmlRegStatePtr to, int counter) {
1367 if (to == NULL) {
1368 to = xmlRegNewState(ctxt);
1369 xmlRegStatePush(ctxt, to);
1370 ctxt->state = to;
1371 }
1372 xmlRegStateAddTrans(ctxt, from, NULL, to, -1, counter);
1373}
1374
1375/**
1376 * xmlFAGenerateTransitions:
Daniel Veillard441bc322002-04-20 17:38:48 +00001377 * @ctxt: a regexp parser context
1378 * @from: the from state
1379 * @to: the target state or NULL for building a new one
1380 * @atom: the atom generating the transition
Daniel Veillard4255d502002-04-16 15:50:10 +00001381 *
William M. Brackddf71d62004-05-06 04:17:26 +00001382 * Returns 0 if success and -1 in case of error.
Daniel Veillard4255d502002-04-16 15:50:10 +00001383 */
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00001384static int
Daniel Veillard4255d502002-04-16 15:50:10 +00001385xmlFAGenerateTransitions(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr from,
1386 xmlRegStatePtr to, xmlRegAtomPtr atom) {
1387 if (atom == NULL) {
1388 ERROR("genrate transition: atom == NULL");
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00001389 return(-1);
Daniel Veillard4255d502002-04-16 15:50:10 +00001390 }
1391 if (atom->type == XML_REGEXP_SUBREG) {
1392 /*
1393 * this is a subexpression handling one should not need to
William M. Brackddf71d62004-05-06 04:17:26 +00001394 * create a new node except for XML_REGEXP_QUANT_RANGE.
Daniel Veillard4255d502002-04-16 15:50:10 +00001395 */
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00001396 if (xmlRegAtomPush(ctxt, atom) < 0) {
1397 return(-1);
1398 }
Daniel Veillard4255d502002-04-16 15:50:10 +00001399 if ((to != NULL) && (atom->stop != to) &&
1400 (atom->quant != XML_REGEXP_QUANT_RANGE)) {
1401 /*
1402 * Generate an epsilon transition to link to the target
1403 */
1404 xmlFAGenerateEpsilonTransition(ctxt, atom->stop, to);
1405 }
1406 switch (atom->quant) {
1407 case XML_REGEXP_QUANT_OPT:
1408 atom->quant = XML_REGEXP_QUANT_ONCE;
1409 xmlFAGenerateEpsilonTransition(ctxt, atom->start, atom->stop);
1410 break;
1411 case XML_REGEXP_QUANT_MULT:
1412 atom->quant = XML_REGEXP_QUANT_ONCE;
1413 xmlFAGenerateEpsilonTransition(ctxt, atom->start, atom->stop);
1414 xmlFAGenerateEpsilonTransition(ctxt, atom->stop, atom->start);
1415 break;
1416 case XML_REGEXP_QUANT_PLUS:
1417 atom->quant = XML_REGEXP_QUANT_ONCE;
1418 xmlFAGenerateEpsilonTransition(ctxt, atom->stop, atom->start);
1419 break;
1420 case XML_REGEXP_QUANT_RANGE: {
1421 int counter;
1422 xmlRegStatePtr newstate;
1423
1424 /*
1425 * This one is nasty:
William M. Brackddf71d62004-05-06 04:17:26 +00001426 * 1/ if range has minOccurs == 0, create a new state
1427 * and create epsilon transitions from atom->start
1428 * to atom->stop, as well as atom->start to the new
1429 * state
1430 * 2/ register a new counter
1431 * 3/ register an epsilon transition associated to
Daniel Veillard4255d502002-04-16 15:50:10 +00001432 * this counter going from atom->stop to atom->start
William M. Brackddf71d62004-05-06 04:17:26 +00001433 * 4/ create a new state
1434 * 5/ generate a counted transition from atom->stop to
Daniel Veillard4255d502002-04-16 15:50:10 +00001435 * that state
1436 */
William M. Brackddf71d62004-05-06 04:17:26 +00001437 if (atom->min == 0) {
1438 xmlFAGenerateEpsilonTransition(ctxt, atom->start,
1439 atom->stop);
1440 newstate = xmlRegNewState(ctxt);
1441 xmlRegStatePush(ctxt, newstate);
1442 ctxt->state = newstate;
1443 xmlFAGenerateEpsilonTransition(ctxt, atom->start,
1444 newstate);
1445 }
Daniel Veillard4255d502002-04-16 15:50:10 +00001446 counter = xmlRegGetCounter(ctxt);
1447 ctxt->counters[counter].min = atom->min - 1;
1448 ctxt->counters[counter].max = atom->max - 1;
1449 atom->min = 0;
1450 atom->max = 0;
1451 atom->quant = XML_REGEXP_QUANT_ONCE;
1452 xmlFAGenerateCountedEpsilonTransition(ctxt, atom->stop,
1453 atom->start, counter);
1454 if (to != NULL) {
1455 newstate = to;
1456 } else {
1457 newstate = xmlRegNewState(ctxt);
1458 xmlRegStatePush(ctxt, newstate);
1459 ctxt->state = newstate;
1460 }
1461 xmlFAGenerateCountedTransition(ctxt, atom->stop,
1462 newstate, counter);
1463 }
1464 default:
1465 break;
1466 }
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00001467 return(0);
Daniel Veillard4255d502002-04-16 15:50:10 +00001468 } else {
1469 if (to == NULL) {
1470 to = xmlRegNewState(ctxt);
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00001471 if (to != NULL)
1472 xmlRegStatePush(ctxt, to);
1473 else {
1474 return(-1);
1475 }
1476 }
1477 if (xmlRegAtomPush(ctxt, atom) < 0) {
1478 return(-1);
Daniel Veillard4255d502002-04-16 15:50:10 +00001479 }
1480 xmlRegStateAddTrans(ctxt, from, atom, to, -1, -1);
Daniel Veillard4255d502002-04-16 15:50:10 +00001481 ctxt->state = to;
1482 }
1483 switch (atom->quant) {
1484 case XML_REGEXP_QUANT_OPT:
1485 atom->quant = XML_REGEXP_QUANT_ONCE;
1486 xmlFAGenerateEpsilonTransition(ctxt, from, to);
1487 break;
1488 case XML_REGEXP_QUANT_MULT:
1489 atom->quant = XML_REGEXP_QUANT_ONCE;
1490 xmlFAGenerateEpsilonTransition(ctxt, from, to);
1491 xmlRegStateAddTrans(ctxt, to, atom, to, -1, -1);
1492 break;
1493 case XML_REGEXP_QUANT_PLUS:
1494 atom->quant = XML_REGEXP_QUANT_ONCE;
1495 xmlRegStateAddTrans(ctxt, to, atom, to, -1, -1);
1496 break;
1497 default:
1498 break;
1499 }
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00001500 return(0);
Daniel Veillard4255d502002-04-16 15:50:10 +00001501}
1502
1503/**
1504 * xmlFAReduceEpsilonTransitions:
Daniel Veillard441bc322002-04-20 17:38:48 +00001505 * @ctxt: a regexp parser context
Daniel Veillard4255d502002-04-16 15:50:10 +00001506 * @fromnr: the from state
1507 * @tonr: the to state
William M. Brackddf71d62004-05-06 04:17:26 +00001508 * @counter: should that transition be associated to a counted
Daniel Veillard4255d502002-04-16 15:50:10 +00001509 *
1510 */
1511static void
1512xmlFAReduceEpsilonTransitions(xmlRegParserCtxtPtr ctxt, int fromnr,
1513 int tonr, int counter) {
1514 int transnr;
1515 xmlRegStatePtr from;
1516 xmlRegStatePtr to;
1517
1518#ifdef DEBUG_REGEXP_GRAPH
1519 printf("xmlFAReduceEpsilonTransitions(%d, %d)\n", fromnr, tonr);
1520#endif
1521 from = ctxt->states[fromnr];
1522 if (from == NULL)
1523 return;
1524 to = ctxt->states[tonr];
1525 if (to == NULL)
1526 return;
1527 if ((to->mark == XML_REGEXP_MARK_START) ||
1528 (to->mark == XML_REGEXP_MARK_VISITED))
1529 return;
1530
1531 to->mark = XML_REGEXP_MARK_VISITED;
1532 if (to->type == XML_REGEXP_FINAL_STATE) {
1533#ifdef DEBUG_REGEXP_GRAPH
1534 printf("State %d is final, so %d becomes final\n", tonr, fromnr);
1535#endif
1536 from->type = XML_REGEXP_FINAL_STATE;
1537 }
1538 for (transnr = 0;transnr < to->nbTrans;transnr++) {
1539 if (to->trans[transnr].atom == NULL) {
1540 /*
1541 * Don't remove counted transitions
1542 * Don't loop either
1543 */
Daniel Veillardb509f152002-04-17 16:28:10 +00001544 if (to->trans[transnr].to != fromnr) {
1545 if (to->trans[transnr].count >= 0) {
1546 int newto = to->trans[transnr].to;
1547
1548 xmlRegStateAddTrans(ctxt, from, NULL,
1549 ctxt->states[newto],
1550 -1, to->trans[transnr].count);
1551 } else {
Daniel Veillard4255d502002-04-16 15:50:10 +00001552#ifdef DEBUG_REGEXP_GRAPH
Daniel Veillardb509f152002-04-17 16:28:10 +00001553 printf("Found epsilon trans %d from %d to %d\n",
1554 transnr, tonr, to->trans[transnr].to);
Daniel Veillard4255d502002-04-16 15:50:10 +00001555#endif
Daniel Veillardb509f152002-04-17 16:28:10 +00001556 if (to->trans[transnr].counter >= 0) {
1557 xmlFAReduceEpsilonTransitions(ctxt, fromnr,
1558 to->trans[transnr].to,
1559 to->trans[transnr].counter);
1560 } else {
1561 xmlFAReduceEpsilonTransitions(ctxt, fromnr,
1562 to->trans[transnr].to,
1563 counter);
1564 }
1565 }
Daniel Veillard4255d502002-04-16 15:50:10 +00001566 }
1567 } else {
1568 int newto = to->trans[transnr].to;
1569
Daniel Veillardb509f152002-04-17 16:28:10 +00001570 if (to->trans[transnr].counter >= 0) {
1571 xmlRegStateAddTrans(ctxt, from, to->trans[transnr].atom,
1572 ctxt->states[newto],
1573 to->trans[transnr].counter, -1);
1574 } else {
1575 xmlRegStateAddTrans(ctxt, from, to->trans[transnr].atom,
1576 ctxt->states[newto], counter, -1);
1577 }
Daniel Veillard4255d502002-04-16 15:50:10 +00001578 }
1579 }
1580 to->mark = XML_REGEXP_MARK_NORMAL;
1581}
1582
1583/**
1584 * xmlFAEliminateEpsilonTransitions:
Daniel Veillard441bc322002-04-20 17:38:48 +00001585 * @ctxt: a regexp parser context
Daniel Veillard4255d502002-04-16 15:50:10 +00001586 *
1587 */
1588static void
1589xmlFAEliminateEpsilonTransitions(xmlRegParserCtxtPtr ctxt) {
1590 int statenr, transnr;
1591 xmlRegStatePtr state;
1592
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00001593 if (ctxt->states == NULL) return;
1594
1595
Daniel Veillard4255d502002-04-16 15:50:10 +00001596 /*
1597 * build the completed transitions bypassing the epsilons
1598 * Use a marking algorithm to avoid loops
Daniel Veillardcc026dc2005-01-12 13:21:17 +00001599 * mark sink states too.
Daniel Veillard4255d502002-04-16 15:50:10 +00001600 */
1601 for (statenr = 0;statenr < ctxt->nbStates;statenr++) {
1602 state = ctxt->states[statenr];
1603 if (state == NULL)
1604 continue;
Daniel Veillardcc026dc2005-01-12 13:21:17 +00001605 if ((state->nbTrans == 0) &&
1606 (state->type != XML_REGEXP_FINAL_STATE)) {
1607 state->type = XML_REGEXP_SINK_STATE;
1608 }
Daniel Veillard4255d502002-04-16 15:50:10 +00001609 for (transnr = 0;transnr < state->nbTrans;transnr++) {
1610 if ((state->trans[transnr].atom == NULL) &&
1611 (state->trans[transnr].to >= 0)) {
1612 if (state->trans[transnr].to == statenr) {
1613 state->trans[transnr].to = -1;
1614#ifdef DEBUG_REGEXP_GRAPH
1615 printf("Removed loopback epsilon trans %d on %d\n",
1616 transnr, statenr);
1617#endif
1618 } else if (state->trans[transnr].count < 0) {
1619 int newto = state->trans[transnr].to;
1620
1621#ifdef DEBUG_REGEXP_GRAPH
1622 printf("Found epsilon trans %d from %d to %d\n",
1623 transnr, statenr, newto);
1624#endif
1625 state->mark = XML_REGEXP_MARK_START;
1626 xmlFAReduceEpsilonTransitions(ctxt, statenr,
1627 newto, state->trans[transnr].counter);
1628 state->mark = XML_REGEXP_MARK_NORMAL;
1629#ifdef DEBUG_REGEXP_GRAPH
1630 } else {
1631 printf("Found counted transition %d on %d\n",
1632 transnr, statenr);
1633#endif
1634 }
1635 }
1636 }
1637 }
1638 /*
1639 * Eliminate the epsilon transitions
1640 */
1641 for (statenr = 0;statenr < ctxt->nbStates;statenr++) {
1642 state = ctxt->states[statenr];
1643 if (state == NULL)
1644 continue;
1645 for (transnr = 0;transnr < state->nbTrans;transnr++) {
1646 if ((state->trans[transnr].atom == NULL) &&
1647 (state->trans[transnr].count < 0) &&
1648 (state->trans[transnr].to >= 0)) {
1649 state->trans[transnr].to = -1;
1650 }
1651 }
1652 }
Daniel Veillard23e73572002-09-19 19:56:43 +00001653
1654 /*
1655 * Use this pass to detect unreachable states too
1656 */
1657 for (statenr = 0;statenr < ctxt->nbStates;statenr++) {
1658 state = ctxt->states[statenr];
1659 if (state != NULL)
William M. Brack779af002003-08-01 15:55:39 +00001660 state->reached = XML_REGEXP_MARK_NORMAL;
Daniel Veillard23e73572002-09-19 19:56:43 +00001661 }
1662 state = ctxt->states[0];
1663 if (state != NULL)
William M. Brack779af002003-08-01 15:55:39 +00001664 state->reached = XML_REGEXP_MARK_START;
Daniel Veillard23e73572002-09-19 19:56:43 +00001665 while (state != NULL) {
1666 xmlRegStatePtr target = NULL;
William M. Brack779af002003-08-01 15:55:39 +00001667 state->reached = XML_REGEXP_MARK_VISITED;
Daniel Veillard23e73572002-09-19 19:56:43 +00001668 /*
William M. Brackddf71d62004-05-06 04:17:26 +00001669 * Mark all states reachable from the current reachable state
Daniel Veillard23e73572002-09-19 19:56:43 +00001670 */
1671 for (transnr = 0;transnr < state->nbTrans;transnr++) {
1672 if ((state->trans[transnr].to >= 0) &&
1673 ((state->trans[transnr].atom != NULL) ||
1674 (state->trans[transnr].count >= 0))) {
1675 int newto = state->trans[transnr].to;
1676
1677 if (ctxt->states[newto] == NULL)
1678 continue;
William M. Brack779af002003-08-01 15:55:39 +00001679 if (ctxt->states[newto]->reached == XML_REGEXP_MARK_NORMAL) {
1680 ctxt->states[newto]->reached = XML_REGEXP_MARK_START;
Daniel Veillard23e73572002-09-19 19:56:43 +00001681 target = ctxt->states[newto];
1682 }
1683 }
1684 }
Daniel Veillardcc026dc2005-01-12 13:21:17 +00001685
Daniel Veillard23e73572002-09-19 19:56:43 +00001686 /*
1687 * find the next accessible state not explored
1688 */
1689 if (target == NULL) {
1690 for (statenr = 1;statenr < ctxt->nbStates;statenr++) {
1691 state = ctxt->states[statenr];
William M. Brack779af002003-08-01 15:55:39 +00001692 if ((state != NULL) && (state->reached ==
1693 XML_REGEXP_MARK_START)) {
Daniel Veillard23e73572002-09-19 19:56:43 +00001694 target = state;
1695 break;
1696 }
1697 }
1698 }
1699 state = target;
1700 }
1701 for (statenr = 0;statenr < ctxt->nbStates;statenr++) {
1702 state = ctxt->states[statenr];
William M. Brack779af002003-08-01 15:55:39 +00001703 if ((state != NULL) && (state->reached == XML_REGEXP_MARK_NORMAL)) {
Daniel Veillard23e73572002-09-19 19:56:43 +00001704#ifdef DEBUG_REGEXP_GRAPH
1705 printf("Removed unreachable state %d\n", statenr);
1706#endif
1707 xmlRegFreeState(state);
1708 ctxt->states[statenr] = NULL;
1709 }
1710 }
1711
Daniel Veillard4255d502002-04-16 15:50:10 +00001712}
1713
Daniel Veillarde19fc232002-04-22 16:01:24 +00001714/**
1715 * xmlFACompareAtoms:
1716 * @atom1: an atom
1717 * @atom2: an atom
1718 *
William M. Brackddf71d62004-05-06 04:17:26 +00001719 * Compares two atoms to check whether they are equivalents
Daniel Veillarde19fc232002-04-22 16:01:24 +00001720 *
1721 * Returns 1 if yes and 0 otherwise
1722 */
1723static int
1724xmlFACompareAtoms(xmlRegAtomPtr atom1, xmlRegAtomPtr atom2) {
1725 if (atom1 == atom2)
1726 return(1);
1727 if ((atom1 == NULL) || (atom2 == NULL))
1728 return(0);
1729
1730 if (atom1->type != atom2->type)
1731 return(0);
1732 switch (atom1->type) {
1733 case XML_REGEXP_STRING:
1734 return(xmlStrEqual((xmlChar *)atom1->valuep,
1735 (xmlChar *)atom2->valuep));
1736 case XML_REGEXP_EPSILON:
1737 return(1);
1738 case XML_REGEXP_CHARVAL:
1739 return(atom1->codepoint == atom2->codepoint);
1740 case XML_REGEXP_RANGES:
1741 TODO;
1742 return(0);
1743 default:
1744 break;
1745 }
1746 return(1);
1747}
1748
1749/**
1750 * xmlFARecurseDeterminism:
1751 * @ctxt: a regexp parser context
1752 *
1753 * Check whether the associated regexp is determinist,
1754 * should be called after xmlFAEliminateEpsilonTransitions()
1755 *
1756 */
1757static int
1758xmlFARecurseDeterminism(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr state,
1759 int to, xmlRegAtomPtr atom) {
1760 int ret = 1;
1761 int transnr;
1762 xmlRegTransPtr t1;
1763
1764 if (state == NULL)
1765 return(ret);
1766 for (transnr = 0;transnr < state->nbTrans;transnr++) {
1767 t1 = &(state->trans[transnr]);
1768 /*
1769 * check transitions conflicting with the one looked at
1770 */
1771 if (t1->atom == NULL) {
1772 if (t1->to == -1)
1773 continue;
1774 ret = xmlFARecurseDeterminism(ctxt, ctxt->states[t1->to],
1775 to, atom);
1776 if (ret == 0)
1777 return(0);
1778 continue;
1779 }
1780 if (t1->to != to)
1781 continue;
1782 if (xmlFACompareAtoms(t1->atom, atom))
1783 return(0);
1784 }
1785 return(ret);
1786}
1787
1788/**
1789 * xmlFAComputesDeterminism:
1790 * @ctxt: a regexp parser context
1791 *
1792 * Check whether the associated regexp is determinist,
1793 * should be called after xmlFAEliminateEpsilonTransitions()
1794 *
1795 */
1796static int
1797xmlFAComputesDeterminism(xmlRegParserCtxtPtr ctxt) {
1798 int statenr, transnr;
1799 xmlRegStatePtr state;
1800 xmlRegTransPtr t1, t2;
1801 int i;
1802 int ret = 1;
1803
Daniel Veillard4402ab42002-09-12 16:02:56 +00001804#ifdef DEBUG_REGEXP_GRAPH
1805 printf("xmlFAComputesDeterminism\n");
1806 xmlRegPrintCtxt(stdout, ctxt);
1807#endif
Daniel Veillarde19fc232002-04-22 16:01:24 +00001808 if (ctxt->determinist != -1)
1809 return(ctxt->determinist);
1810
1811 /*
William M. Brackddf71d62004-05-06 04:17:26 +00001812 * Check for all states that there aren't 2 transitions
Daniel Veillarde19fc232002-04-22 16:01:24 +00001813 * with the same atom and a different target.
1814 */
1815 for (statenr = 0;statenr < ctxt->nbStates;statenr++) {
1816 state = ctxt->states[statenr];
1817 if (state == NULL)
1818 continue;
1819 for (transnr = 0;transnr < state->nbTrans;transnr++) {
1820 t1 = &(state->trans[transnr]);
1821 /*
1822 * Determinism checks in case of counted or all transitions
1823 * will have to be handled separately
1824 */
1825 if (t1->atom == NULL)
1826 continue;
1827 if (t1->to == -1) /* eliminated */
1828 continue;
1829 for (i = 0;i < transnr;i++) {
1830 t2 = &(state->trans[i]);
1831 if (t2->to == -1) /* eliminated */
1832 continue;
1833 if (t2->atom != NULL) {
1834 if (t1->to == t2->to) {
1835 if (xmlFACompareAtoms(t1->atom, t2->atom))
William M. Brackddf71d62004-05-06 04:17:26 +00001836 t2->to = -1; /* eliminated */
Daniel Veillarde19fc232002-04-22 16:01:24 +00001837 } else {
1838 /* not determinist ! */
1839 if (xmlFACompareAtoms(t1->atom, t2->atom))
1840 ret = 0;
1841 }
1842 } else if (t1->to != -1) {
1843 /*
1844 * do the closure in case of remaining specific
1845 * epsilon transitions like choices or all
1846 */
1847 ret = xmlFARecurseDeterminism(ctxt, ctxt->states[t1->to],
1848 t2->to, t2->atom);
1849 if (ret == 0)
1850 return(0);
1851 }
1852 }
1853 if (ret == 0)
1854 break;
1855 }
1856 if (ret == 0)
1857 break;
1858 }
1859 ctxt->determinist = ret;
1860 return(ret);
1861}
1862
Daniel Veillard4255d502002-04-16 15:50:10 +00001863/************************************************************************
1864 * *
1865 * Routines to check input against transition atoms *
1866 * *
1867 ************************************************************************/
1868
1869static int
1870xmlRegCheckCharacterRange(xmlRegAtomType type, int codepoint, int neg,
1871 int start, int end, const xmlChar *blockName) {
1872 int ret = 0;
1873
1874 switch (type) {
1875 case XML_REGEXP_STRING:
1876 case XML_REGEXP_SUBREG:
1877 case XML_REGEXP_RANGES:
1878 case XML_REGEXP_EPSILON:
1879 return(-1);
1880 case XML_REGEXP_ANYCHAR:
1881 ret = ((codepoint != '\n') && (codepoint != '\r'));
1882 break;
1883 case XML_REGEXP_CHARVAL:
1884 ret = ((codepoint >= start) && (codepoint <= end));
1885 break;
1886 case XML_REGEXP_NOTSPACE:
1887 neg = !neg;
1888 case XML_REGEXP_ANYSPACE:
1889 ret = ((codepoint == '\n') || (codepoint == '\r') ||
1890 (codepoint == '\t') || (codepoint == ' '));
1891 break;
1892 case XML_REGEXP_NOTINITNAME:
1893 neg = !neg;
1894 case XML_REGEXP_INITNAME:
William M. Brack871611b2003-10-18 04:53:14 +00001895 ret = (IS_LETTER(codepoint) ||
Daniel Veillard4255d502002-04-16 15:50:10 +00001896 (codepoint == '_') || (codepoint == ':'));
1897 break;
1898 case XML_REGEXP_NOTNAMECHAR:
1899 neg = !neg;
1900 case XML_REGEXP_NAMECHAR:
William M. Brack871611b2003-10-18 04:53:14 +00001901 ret = (IS_LETTER(codepoint) || IS_DIGIT(codepoint) ||
Daniel Veillard4255d502002-04-16 15:50:10 +00001902 (codepoint == '.') || (codepoint == '-') ||
1903 (codepoint == '_') || (codepoint == ':') ||
William M. Brack871611b2003-10-18 04:53:14 +00001904 IS_COMBINING(codepoint) || IS_EXTENDER(codepoint));
Daniel Veillard4255d502002-04-16 15:50:10 +00001905 break;
1906 case XML_REGEXP_NOTDECIMAL:
1907 neg = !neg;
1908 case XML_REGEXP_DECIMAL:
1909 ret = xmlUCSIsCatNd(codepoint);
1910 break;
1911 case XML_REGEXP_REALCHAR:
1912 neg = !neg;
1913 case XML_REGEXP_NOTREALCHAR:
1914 ret = xmlUCSIsCatP(codepoint);
1915 if (ret == 0)
1916 ret = xmlUCSIsCatZ(codepoint);
1917 if (ret == 0)
1918 ret = xmlUCSIsCatC(codepoint);
1919 break;
1920 case XML_REGEXP_LETTER:
1921 ret = xmlUCSIsCatL(codepoint);
1922 break;
1923 case XML_REGEXP_LETTER_UPPERCASE:
1924 ret = xmlUCSIsCatLu(codepoint);
1925 break;
1926 case XML_REGEXP_LETTER_LOWERCASE:
1927 ret = xmlUCSIsCatLl(codepoint);
1928 break;
1929 case XML_REGEXP_LETTER_TITLECASE:
1930 ret = xmlUCSIsCatLt(codepoint);
1931 break;
1932 case XML_REGEXP_LETTER_MODIFIER:
1933 ret = xmlUCSIsCatLm(codepoint);
1934 break;
1935 case XML_REGEXP_LETTER_OTHERS:
1936 ret = xmlUCSIsCatLo(codepoint);
1937 break;
1938 case XML_REGEXP_MARK:
1939 ret = xmlUCSIsCatM(codepoint);
1940 break;
1941 case XML_REGEXP_MARK_NONSPACING:
1942 ret = xmlUCSIsCatMn(codepoint);
1943 break;
1944 case XML_REGEXP_MARK_SPACECOMBINING:
1945 ret = xmlUCSIsCatMc(codepoint);
1946 break;
1947 case XML_REGEXP_MARK_ENCLOSING:
1948 ret = xmlUCSIsCatMe(codepoint);
1949 break;
1950 case XML_REGEXP_NUMBER:
1951 ret = xmlUCSIsCatN(codepoint);
1952 break;
1953 case XML_REGEXP_NUMBER_DECIMAL:
1954 ret = xmlUCSIsCatNd(codepoint);
1955 break;
1956 case XML_REGEXP_NUMBER_LETTER:
1957 ret = xmlUCSIsCatNl(codepoint);
1958 break;
1959 case XML_REGEXP_NUMBER_OTHERS:
1960 ret = xmlUCSIsCatNo(codepoint);
1961 break;
1962 case XML_REGEXP_PUNCT:
1963 ret = xmlUCSIsCatP(codepoint);
1964 break;
1965 case XML_REGEXP_PUNCT_CONNECTOR:
1966 ret = xmlUCSIsCatPc(codepoint);
1967 break;
1968 case XML_REGEXP_PUNCT_DASH:
1969 ret = xmlUCSIsCatPd(codepoint);
1970 break;
1971 case XML_REGEXP_PUNCT_OPEN:
1972 ret = xmlUCSIsCatPs(codepoint);
1973 break;
1974 case XML_REGEXP_PUNCT_CLOSE:
1975 ret = xmlUCSIsCatPe(codepoint);
1976 break;
1977 case XML_REGEXP_PUNCT_INITQUOTE:
1978 ret = xmlUCSIsCatPi(codepoint);
1979 break;
1980 case XML_REGEXP_PUNCT_FINQUOTE:
1981 ret = xmlUCSIsCatPf(codepoint);
1982 break;
1983 case XML_REGEXP_PUNCT_OTHERS:
1984 ret = xmlUCSIsCatPo(codepoint);
1985 break;
1986 case XML_REGEXP_SEPAR:
1987 ret = xmlUCSIsCatZ(codepoint);
1988 break;
1989 case XML_REGEXP_SEPAR_SPACE:
1990 ret = xmlUCSIsCatZs(codepoint);
1991 break;
1992 case XML_REGEXP_SEPAR_LINE:
1993 ret = xmlUCSIsCatZl(codepoint);
1994 break;
1995 case XML_REGEXP_SEPAR_PARA:
1996 ret = xmlUCSIsCatZp(codepoint);
1997 break;
1998 case XML_REGEXP_SYMBOL:
1999 ret = xmlUCSIsCatS(codepoint);
2000 break;
2001 case XML_REGEXP_SYMBOL_MATH:
2002 ret = xmlUCSIsCatSm(codepoint);
2003 break;
2004 case XML_REGEXP_SYMBOL_CURRENCY:
2005 ret = xmlUCSIsCatSc(codepoint);
2006 break;
2007 case XML_REGEXP_SYMBOL_MODIFIER:
2008 ret = xmlUCSIsCatSk(codepoint);
2009 break;
2010 case XML_REGEXP_SYMBOL_OTHERS:
2011 ret = xmlUCSIsCatSo(codepoint);
2012 break;
2013 case XML_REGEXP_OTHER:
2014 ret = xmlUCSIsCatC(codepoint);
2015 break;
2016 case XML_REGEXP_OTHER_CONTROL:
2017 ret = xmlUCSIsCatCc(codepoint);
2018 break;
2019 case XML_REGEXP_OTHER_FORMAT:
2020 ret = xmlUCSIsCatCf(codepoint);
2021 break;
2022 case XML_REGEXP_OTHER_PRIVATE:
2023 ret = xmlUCSIsCatCo(codepoint);
2024 break;
2025 case XML_REGEXP_OTHER_NA:
2026 /* ret = xmlUCSIsCatCn(codepoint); */
2027 /* Seems it doesn't exist anymore in recent Unicode releases */
2028 ret = 0;
2029 break;
2030 case XML_REGEXP_BLOCK_NAME:
2031 ret = xmlUCSIsBlock(codepoint, (const char *) blockName);
2032 break;
2033 }
2034 if (neg)
2035 return(!ret);
2036 return(ret);
2037}
2038
2039static int
2040xmlRegCheckCharacter(xmlRegAtomPtr atom, int codepoint) {
2041 int i, ret = 0;
2042 xmlRegRangePtr range;
2043
William M. Brack871611b2003-10-18 04:53:14 +00002044 if ((atom == NULL) || (!IS_CHAR(codepoint)))
Daniel Veillard4255d502002-04-16 15:50:10 +00002045 return(-1);
2046
2047 switch (atom->type) {
2048 case XML_REGEXP_SUBREG:
2049 case XML_REGEXP_EPSILON:
2050 return(-1);
2051 case XML_REGEXP_CHARVAL:
2052 return(codepoint == atom->codepoint);
2053 case XML_REGEXP_RANGES: {
2054 int accept = 0;
Daniel Veillardf2a12832003-11-24 13:04:35 +00002055
Daniel Veillard4255d502002-04-16 15:50:10 +00002056 for (i = 0;i < atom->nbRanges;i++) {
2057 range = atom->ranges[i];
Daniel Veillardf8b9de32003-11-24 14:27:26 +00002058 if (range->neg == 2) {
Daniel Veillard4255d502002-04-16 15:50:10 +00002059 ret = xmlRegCheckCharacterRange(range->type, codepoint,
2060 0, range->start, range->end,
2061 range->blockName);
2062 if (ret != 0)
2063 return(0); /* excluded char */
Daniel Veillardf8b9de32003-11-24 14:27:26 +00002064 } else if (range->neg) {
2065 ret = xmlRegCheckCharacterRange(range->type, codepoint,
2066 0, range->start, range->end,
2067 range->blockName);
2068 if (ret == 0)
Daniel Veillardf2a12832003-11-24 13:04:35 +00002069 accept = 1;
Daniel Veillardf8b9de32003-11-24 14:27:26 +00002070 else
2071 return(0);
Daniel Veillard4255d502002-04-16 15:50:10 +00002072 } else {
2073 ret = xmlRegCheckCharacterRange(range->type, codepoint,
2074 0, range->start, range->end,
2075 range->blockName);
2076 if (ret != 0)
2077 accept = 1; /* might still be excluded */
2078 }
2079 }
2080 return(accept);
2081 }
2082 case XML_REGEXP_STRING:
2083 printf("TODO: XML_REGEXP_STRING\n");
2084 return(-1);
2085 case XML_REGEXP_ANYCHAR:
2086 case XML_REGEXP_ANYSPACE:
2087 case XML_REGEXP_NOTSPACE:
2088 case XML_REGEXP_INITNAME:
2089 case XML_REGEXP_NOTINITNAME:
2090 case XML_REGEXP_NAMECHAR:
2091 case XML_REGEXP_NOTNAMECHAR:
2092 case XML_REGEXP_DECIMAL:
2093 case XML_REGEXP_NOTDECIMAL:
2094 case XML_REGEXP_REALCHAR:
2095 case XML_REGEXP_NOTREALCHAR:
2096 case XML_REGEXP_LETTER:
2097 case XML_REGEXP_LETTER_UPPERCASE:
2098 case XML_REGEXP_LETTER_LOWERCASE:
2099 case XML_REGEXP_LETTER_TITLECASE:
2100 case XML_REGEXP_LETTER_MODIFIER:
2101 case XML_REGEXP_LETTER_OTHERS:
2102 case XML_REGEXP_MARK:
2103 case XML_REGEXP_MARK_NONSPACING:
2104 case XML_REGEXP_MARK_SPACECOMBINING:
2105 case XML_REGEXP_MARK_ENCLOSING:
2106 case XML_REGEXP_NUMBER:
2107 case XML_REGEXP_NUMBER_DECIMAL:
2108 case XML_REGEXP_NUMBER_LETTER:
2109 case XML_REGEXP_NUMBER_OTHERS:
2110 case XML_REGEXP_PUNCT:
2111 case XML_REGEXP_PUNCT_CONNECTOR:
2112 case XML_REGEXP_PUNCT_DASH:
2113 case XML_REGEXP_PUNCT_OPEN:
2114 case XML_REGEXP_PUNCT_CLOSE:
2115 case XML_REGEXP_PUNCT_INITQUOTE:
2116 case XML_REGEXP_PUNCT_FINQUOTE:
2117 case XML_REGEXP_PUNCT_OTHERS:
2118 case XML_REGEXP_SEPAR:
2119 case XML_REGEXP_SEPAR_SPACE:
2120 case XML_REGEXP_SEPAR_LINE:
2121 case XML_REGEXP_SEPAR_PARA:
2122 case XML_REGEXP_SYMBOL:
2123 case XML_REGEXP_SYMBOL_MATH:
2124 case XML_REGEXP_SYMBOL_CURRENCY:
2125 case XML_REGEXP_SYMBOL_MODIFIER:
2126 case XML_REGEXP_SYMBOL_OTHERS:
2127 case XML_REGEXP_OTHER:
2128 case XML_REGEXP_OTHER_CONTROL:
2129 case XML_REGEXP_OTHER_FORMAT:
2130 case XML_REGEXP_OTHER_PRIVATE:
2131 case XML_REGEXP_OTHER_NA:
2132 case XML_REGEXP_BLOCK_NAME:
2133 ret = xmlRegCheckCharacterRange(atom->type, codepoint, 0, 0, 0,
2134 (const xmlChar *)atom->valuep);
2135 if (atom->neg)
2136 ret = !ret;
2137 break;
2138 }
2139 return(ret);
2140}
2141
2142/************************************************************************
2143 * *
William M. Brackddf71d62004-05-06 04:17:26 +00002144 * Saving and restoring state of an execution context *
Daniel Veillard4255d502002-04-16 15:50:10 +00002145 * *
2146 ************************************************************************/
2147
2148#ifdef DEBUG_REGEXP_EXEC
2149static void
2150xmlFARegDebugExec(xmlRegExecCtxtPtr exec) {
2151 printf("state: %d:%d:idx %d", exec->state->no, exec->transno, exec->index);
2152 if (exec->inputStack != NULL) {
2153 int i;
2154 printf(": ");
2155 for (i = 0;(i < 3) && (i < exec->inputStackNr);i++)
2156 printf("%s ", exec->inputStack[exec->inputStackNr - (i + 1)]);
2157 } else {
2158 printf(": %s", &(exec->inputString[exec->index]));
2159 }
2160 printf("\n");
2161}
2162#endif
2163
2164static void
2165xmlFARegExecSave(xmlRegExecCtxtPtr exec) {
2166#ifdef DEBUG_REGEXP_EXEC
2167 printf("saving ");
2168 exec->transno++;
2169 xmlFARegDebugExec(exec);
2170 exec->transno--;
2171#endif
2172
2173 if (exec->maxRollbacks == 0) {
2174 exec->maxRollbacks = 4;
2175 exec->rollbacks = (xmlRegExecRollback *) xmlMalloc(exec->maxRollbacks *
2176 sizeof(xmlRegExecRollback));
2177 if (exec->rollbacks == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +00002178 xmlRegexpErrMemory(NULL, "saving regexp");
Daniel Veillard4255d502002-04-16 15:50:10 +00002179 exec->maxRollbacks = 0;
2180 return;
2181 }
2182 memset(exec->rollbacks, 0,
2183 exec->maxRollbacks * sizeof(xmlRegExecRollback));
2184 } else if (exec->nbRollbacks >= exec->maxRollbacks) {
2185 xmlRegExecRollback *tmp;
2186 int len = exec->maxRollbacks;
2187
2188 exec->maxRollbacks *= 2;
2189 tmp = (xmlRegExecRollback *) xmlRealloc(exec->rollbacks,
2190 exec->maxRollbacks * sizeof(xmlRegExecRollback));
2191 if (tmp == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +00002192 xmlRegexpErrMemory(NULL, "saving regexp");
Daniel Veillard4255d502002-04-16 15:50:10 +00002193 exec->maxRollbacks /= 2;
2194 return;
2195 }
2196 exec->rollbacks = tmp;
2197 tmp = &exec->rollbacks[len];
2198 memset(tmp, 0, (exec->maxRollbacks - len) * sizeof(xmlRegExecRollback));
2199 }
2200 exec->rollbacks[exec->nbRollbacks].state = exec->state;
2201 exec->rollbacks[exec->nbRollbacks].index = exec->index;
2202 exec->rollbacks[exec->nbRollbacks].nextbranch = exec->transno + 1;
2203 if (exec->comp->nbCounters > 0) {
2204 if (exec->rollbacks[exec->nbRollbacks].counts == NULL) {
2205 exec->rollbacks[exec->nbRollbacks].counts = (int *)
2206 xmlMalloc(exec->comp->nbCounters * sizeof(int));
2207 if (exec->rollbacks[exec->nbRollbacks].counts == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +00002208 xmlRegexpErrMemory(NULL, "saving regexp");
Daniel Veillard4255d502002-04-16 15:50:10 +00002209 exec->status = -5;
2210 return;
2211 }
2212 }
2213 memcpy(exec->rollbacks[exec->nbRollbacks].counts, exec->counts,
2214 exec->comp->nbCounters * sizeof(int));
2215 }
2216 exec->nbRollbacks++;
2217}
2218
2219static void
2220xmlFARegExecRollBack(xmlRegExecCtxtPtr exec) {
2221 if (exec->nbRollbacks <= 0) {
2222 exec->status = -1;
2223#ifdef DEBUG_REGEXP_EXEC
2224 printf("rollback failed on empty stack\n");
2225#endif
2226 return;
2227 }
2228 exec->nbRollbacks--;
2229 exec->state = exec->rollbacks[exec->nbRollbacks].state;
2230 exec->index = exec->rollbacks[exec->nbRollbacks].index;
2231 exec->transno = exec->rollbacks[exec->nbRollbacks].nextbranch;
2232 if (exec->comp->nbCounters > 0) {
2233 if (exec->rollbacks[exec->nbRollbacks].counts == NULL) {
2234 fprintf(stderr, "exec save: allocation failed");
2235 exec->status = -6;
2236 return;
2237 }
2238 memcpy(exec->counts, exec->rollbacks[exec->nbRollbacks].counts,
2239 exec->comp->nbCounters * sizeof(int));
2240 }
2241
2242#ifdef DEBUG_REGEXP_EXEC
2243 printf("restored ");
2244 xmlFARegDebugExec(exec);
2245#endif
2246}
2247
2248/************************************************************************
2249 * *
William M. Brackddf71d62004-05-06 04:17:26 +00002250 * Verifier, running an input against a compiled regexp *
Daniel Veillard4255d502002-04-16 15:50:10 +00002251 * *
2252 ************************************************************************/
2253
2254static int
2255xmlFARegExec(xmlRegexpPtr comp, const xmlChar *content) {
2256 xmlRegExecCtxt execval;
2257 xmlRegExecCtxtPtr exec = &execval;
Daniel Veillard7bd8b4b2005-01-07 13:56:19 +00002258 int ret, codepoint = 0, len;
Daniel Veillard4255d502002-04-16 15:50:10 +00002259
2260 exec->inputString = content;
2261 exec->index = 0;
2262 exec->determinist = 1;
2263 exec->maxRollbacks = 0;
2264 exec->nbRollbacks = 0;
2265 exec->rollbacks = NULL;
2266 exec->status = 0;
2267 exec->comp = comp;
2268 exec->state = comp->states[0];
2269 exec->transno = 0;
2270 exec->transcount = 0;
Daniel Veillardf2a12832003-11-24 13:04:35 +00002271 exec->inputStack = NULL;
2272 exec->inputStackMax = 0;
Daniel Veillard4255d502002-04-16 15:50:10 +00002273 if (comp->nbCounters > 0) {
2274 exec->counts = (int *) xmlMalloc(comp->nbCounters * sizeof(int));
Daniel Veillardff46a042003-10-08 08:53:17 +00002275 if (exec->counts == NULL) {
2276 xmlRegexpErrMemory(NULL, "running regexp");
Daniel Veillard4255d502002-04-16 15:50:10 +00002277 return(-1);
Daniel Veillardff46a042003-10-08 08:53:17 +00002278 }
Daniel Veillard4255d502002-04-16 15:50:10 +00002279 memset(exec->counts, 0, comp->nbCounters * sizeof(int));
2280 } else
2281 exec->counts = NULL;
2282 while ((exec->status == 0) &&
2283 ((exec->inputString[exec->index] != 0) ||
2284 (exec->state->type != XML_REGEXP_FINAL_STATE))) {
2285 xmlRegTransPtr trans;
2286 xmlRegAtomPtr atom;
2287
2288 /*
William M. Brack0e00b282004-04-26 15:40:47 +00002289 * If end of input on non-terminal state, rollback, however we may
Daniel Veillard4255d502002-04-16 15:50:10 +00002290 * still have epsilon like transition for counted transitions
William M. Brack0e00b282004-04-26 15:40:47 +00002291 * on counters, in that case don't break too early. Additionally,
2292 * if we are working on a range like "AB{0,2}", where B is not present,
2293 * we don't want to break.
Daniel Veillard4255d502002-04-16 15:50:10 +00002294 */
William M. Brack0e00b282004-04-26 15:40:47 +00002295 if ((exec->inputString[exec->index] == 0) && (exec->counts == NULL)) {
William M. Brackddf71d62004-05-06 04:17:26 +00002296 /*
2297 * if there is a transition, we must check if
2298 * atom allows minOccurs of 0
2299 */
2300 if (exec->transno < exec->state->nbTrans) {
William M. Brack0e00b282004-04-26 15:40:47 +00002301 trans = &exec->state->trans[exec->transno];
2302 if (trans->to >=0) {
2303 atom = trans->atom;
2304 if (!((atom->min == 0) && (atom->max > 0)))
2305 goto rollback;
2306 }
2307 } else
2308 goto rollback;
2309 }
Daniel Veillard4255d502002-04-16 15:50:10 +00002310
2311 exec->transcount = 0;
2312 for (;exec->transno < exec->state->nbTrans;exec->transno++) {
2313 trans = &exec->state->trans[exec->transno];
2314 if (trans->to < 0)
2315 continue;
2316 atom = trans->atom;
2317 ret = 0;
2318 if (trans->count >= 0) {
2319 int count;
2320 xmlRegCounterPtr counter;
2321
2322 /*
2323 * A counted transition.
2324 */
2325
2326 count = exec->counts[trans->count];
2327 counter = &exec->comp->counters[trans->count];
2328#ifdef DEBUG_REGEXP_EXEC
2329 printf("testing count %d: val %d, min %d, max %d\n",
2330 trans->count, count, counter->min, counter->max);
2331#endif
2332 ret = ((count >= counter->min) && (count <= counter->max));
2333 } else if (atom == NULL) {
2334 fprintf(stderr, "epsilon transition left at runtime\n");
2335 exec->status = -2;
2336 break;
2337 } else if (exec->inputString[exec->index] != 0) {
2338 codepoint = CUR_SCHAR(&(exec->inputString[exec->index]), len);
2339 ret = xmlRegCheckCharacter(atom, codepoint);
William M. Brack0e00b282004-04-26 15:40:47 +00002340 if ((ret == 1) && (atom->min >= 0) && (atom->max > 0)) {
Daniel Veillard4255d502002-04-16 15:50:10 +00002341 xmlRegStatePtr to = comp->states[trans->to];
2342
2343 /*
2344 * this is a multiple input sequence
2345 */
2346 if (exec->state->nbTrans > exec->transno + 1) {
2347 xmlFARegExecSave(exec);
2348 }
2349 exec->transcount = 1;
2350 do {
2351 /*
2352 * Try to progress as much as possible on the input
2353 */
2354 if (exec->transcount == atom->max) {
2355 break;
2356 }
2357 exec->index += len;
2358 /*
2359 * End of input: stop here
2360 */
2361 if (exec->inputString[exec->index] == 0) {
2362 exec->index -= len;
2363 break;
2364 }
2365 if (exec->transcount >= atom->min) {
2366 int transno = exec->transno;
2367 xmlRegStatePtr state = exec->state;
2368
2369 /*
2370 * The transition is acceptable save it
2371 */
2372 exec->transno = -1; /* trick */
2373 exec->state = to;
2374 xmlFARegExecSave(exec);
2375 exec->transno = transno;
2376 exec->state = state;
2377 }
2378 codepoint = CUR_SCHAR(&(exec->inputString[exec->index]),
2379 len);
2380 ret = xmlRegCheckCharacter(atom, codepoint);
2381 exec->transcount++;
2382 } while (ret == 1);
2383 if (exec->transcount < atom->min)
2384 ret = 0;
2385
2386 /*
2387 * If the last check failed but one transition was found
2388 * possible, rollback
2389 */
2390 if (ret < 0)
2391 ret = 0;
2392 if (ret == 0) {
2393 goto rollback;
2394 }
William M. Brack0e00b282004-04-26 15:40:47 +00002395 } else if ((ret == 0) && (atom->min == 0) && (atom->max > 0)) {
2396 /*
2397 * we don't match on the codepoint, but minOccurs of 0
2398 * says that's ok. Setting len to 0 inhibits stepping
2399 * over the codepoint.
2400 */
2401 exec->transcount = 1;
2402 len = 0;
2403 ret = 1;
Daniel Veillard4255d502002-04-16 15:50:10 +00002404 }
William M. Brack0e00b282004-04-26 15:40:47 +00002405 } else if ((atom->min == 0) && (atom->max > 0)) {
2406 /* another spot to match when minOccurs is 0 */
2407 exec->transcount = 1;
2408 len = 0;
2409 ret = 1;
Daniel Veillard4255d502002-04-16 15:50:10 +00002410 }
2411 if (ret == 1) {
2412 if (exec->state->nbTrans > exec->transno + 1) {
2413 xmlFARegExecSave(exec);
2414 }
2415 if (trans->counter >= 0) {
2416#ifdef DEBUG_REGEXP_EXEC
2417 printf("Increasing count %d\n", trans->counter);
2418#endif
2419 exec->counts[trans->counter]++;
2420 }
2421#ifdef DEBUG_REGEXP_EXEC
2422 printf("entering state %d\n", trans->to);
2423#endif
2424 exec->state = comp->states[trans->to];
2425 exec->transno = 0;
2426 if (trans->atom != NULL) {
2427 exec->index += len;
2428 }
2429 goto progress;
2430 } else if (ret < 0) {
2431 exec->status = -4;
2432 break;
2433 }
2434 }
2435 if ((exec->transno != 0) || (exec->state->nbTrans == 0)) {
2436rollback:
2437 /*
2438 * Failed to find a way out
2439 */
2440 exec->determinist = 0;
2441 xmlFARegExecRollBack(exec);
2442 }
2443progress:
2444 continue;
2445 }
2446 if (exec->rollbacks != NULL) {
2447 if (exec->counts != NULL) {
2448 int i;
2449
2450 for (i = 0;i < exec->maxRollbacks;i++)
2451 if (exec->rollbacks[i].counts != NULL)
2452 xmlFree(exec->rollbacks[i].counts);
2453 }
2454 xmlFree(exec->rollbacks);
2455 }
2456 if (exec->counts != NULL)
2457 xmlFree(exec->counts);
2458 if (exec->status == 0)
2459 return(1);
2460 if (exec->status == -1)
2461 return(0);
2462 return(exec->status);
2463}
2464
2465/************************************************************************
2466 * *
William M. Brackddf71d62004-05-06 04:17:26 +00002467 * Progressive interface to the verifier one atom at a time *
Daniel Veillard4255d502002-04-16 15:50:10 +00002468 * *
2469 ************************************************************************/
Daniel Veillard7bd8b4b2005-01-07 13:56:19 +00002470#ifdef DEBUG_ERR
2471static void testerr(xmlRegExecCtxtPtr exec);
2472#endif
Daniel Veillard4255d502002-04-16 15:50:10 +00002473
2474/**
Daniel Veillard01c13b52002-12-10 15:19:08 +00002475 * xmlRegNewExecCtxt:
Daniel Veillard4255d502002-04-16 15:50:10 +00002476 * @comp: a precompiled regular expression
2477 * @callback: a callback function used for handling progresses in the
2478 * automata matching phase
2479 * @data: the context data associated to the callback in this context
2480 *
2481 * Build a context used for progressive evaluation of a regexp.
Daniel Veillard01c13b52002-12-10 15:19:08 +00002482 *
2483 * Returns the new context
Daniel Veillard4255d502002-04-16 15:50:10 +00002484 */
2485xmlRegExecCtxtPtr
2486xmlRegNewExecCtxt(xmlRegexpPtr comp, xmlRegExecCallbacks callback, void *data) {
2487 xmlRegExecCtxtPtr exec;
2488
2489 if (comp == NULL)
2490 return(NULL);
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00002491 if ((comp->compact == NULL) && (comp->states == NULL))
2492 return(NULL);
Daniel Veillard4255d502002-04-16 15:50:10 +00002493 exec = (xmlRegExecCtxtPtr) xmlMalloc(sizeof(xmlRegExecCtxt));
2494 if (exec == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +00002495 xmlRegexpErrMemory(NULL, "creating execution context");
Daniel Veillard4255d502002-04-16 15:50:10 +00002496 return(NULL);
2497 }
2498 memset(exec, 0, sizeof(xmlRegExecCtxt));
2499 exec->inputString = NULL;
2500 exec->index = 0;
2501 exec->determinist = 1;
2502 exec->maxRollbacks = 0;
2503 exec->nbRollbacks = 0;
2504 exec->rollbacks = NULL;
2505 exec->status = 0;
2506 exec->comp = comp;
Daniel Veillard23e73572002-09-19 19:56:43 +00002507 if (comp->compact == NULL)
2508 exec->state = comp->states[0];
Daniel Veillard4255d502002-04-16 15:50:10 +00002509 exec->transno = 0;
2510 exec->transcount = 0;
2511 exec->callback = callback;
2512 exec->data = data;
2513 if (comp->nbCounters > 0) {
Daniel Veillard7bd8b4b2005-01-07 13:56:19 +00002514 /*
2515 * For error handling, exec->counts is allocated twice the size
2516 * the second half is used to store the data in case of rollback
2517 */
2518 exec->counts = (int *) xmlMalloc(comp->nbCounters * sizeof(int)
2519 * 2);
Daniel Veillard4255d502002-04-16 15:50:10 +00002520 if (exec->counts == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +00002521 xmlRegexpErrMemory(NULL, "creating execution context");
Daniel Veillard4255d502002-04-16 15:50:10 +00002522 xmlFree(exec);
2523 return(NULL);
2524 }
Daniel Veillard7bd8b4b2005-01-07 13:56:19 +00002525 memset(exec->counts, 0, comp->nbCounters * sizeof(int) * 2);
2526 exec->errCounts = &exec->counts[comp->nbCounters];
2527 } else {
Daniel Veillard4255d502002-04-16 15:50:10 +00002528 exec->counts = NULL;
Daniel Veillard7bd8b4b2005-01-07 13:56:19 +00002529 exec->errCounts = NULL;
2530 }
Daniel Veillard4255d502002-04-16 15:50:10 +00002531 exec->inputStackMax = 0;
2532 exec->inputStackNr = 0;
2533 exec->inputStack = NULL;
Daniel Veillard7bd8b4b2005-01-07 13:56:19 +00002534 exec->errStateNo = -1;
2535 exec->errString = NULL;
Daniel Veillard4255d502002-04-16 15:50:10 +00002536 return(exec);
2537}
2538
2539/**
2540 * xmlRegFreeExecCtxt:
2541 * @exec: a regular expression evaulation context
2542 *
2543 * Free the structures associated to a regular expression evaulation context.
2544 */
2545void
2546xmlRegFreeExecCtxt(xmlRegExecCtxtPtr exec) {
2547 if (exec == NULL)
2548 return;
2549
2550 if (exec->rollbacks != NULL) {
2551 if (exec->counts != NULL) {
2552 int i;
2553
2554 for (i = 0;i < exec->maxRollbacks;i++)
2555 if (exec->rollbacks[i].counts != NULL)
2556 xmlFree(exec->rollbacks[i].counts);
2557 }
2558 xmlFree(exec->rollbacks);
2559 }
2560 if (exec->counts != NULL)
2561 xmlFree(exec->counts);
2562 if (exec->inputStack != NULL) {
2563 int i;
2564
Daniel Veillard32370232002-10-16 14:08:14 +00002565 for (i = 0;i < exec->inputStackNr;i++) {
2566 if (exec->inputStack[i].value != NULL)
2567 xmlFree(exec->inputStack[i].value);
2568 }
Daniel Veillard4255d502002-04-16 15:50:10 +00002569 xmlFree(exec->inputStack);
2570 }
Daniel Veillard7bd8b4b2005-01-07 13:56:19 +00002571 if (exec->errString != NULL)
2572 xmlFree(exec->errString);
Daniel Veillard4255d502002-04-16 15:50:10 +00002573 xmlFree(exec);
2574}
2575
2576static void
2577xmlFARegExecSaveInputString(xmlRegExecCtxtPtr exec, const xmlChar *value,
2578 void *data) {
2579#ifdef DEBUG_PUSH
2580 printf("saving value: %d:%s\n", exec->inputStackNr, value);
2581#endif
2582 if (exec->inputStackMax == 0) {
2583 exec->inputStackMax = 4;
2584 exec->inputStack = (xmlRegInputTokenPtr)
2585 xmlMalloc(exec->inputStackMax * sizeof(xmlRegInputToken));
2586 if (exec->inputStack == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +00002587 xmlRegexpErrMemory(NULL, "pushing input string");
Daniel Veillard4255d502002-04-16 15:50:10 +00002588 exec->inputStackMax = 0;
2589 return;
2590 }
2591 } else if (exec->inputStackNr + 1 >= exec->inputStackMax) {
2592 xmlRegInputTokenPtr tmp;
2593
2594 exec->inputStackMax *= 2;
2595 tmp = (xmlRegInputTokenPtr) xmlRealloc(exec->inputStack,
2596 exec->inputStackMax * sizeof(xmlRegInputToken));
2597 if (tmp == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +00002598 xmlRegexpErrMemory(NULL, "pushing input string");
Daniel Veillard4255d502002-04-16 15:50:10 +00002599 exec->inputStackMax /= 2;
2600 return;
2601 }
2602 exec->inputStack = tmp;
2603 }
2604 exec->inputStack[exec->inputStackNr].value = xmlStrdup(value);
2605 exec->inputStack[exec->inputStackNr].data = data;
2606 exec->inputStackNr++;
2607 exec->inputStack[exec->inputStackNr].value = NULL;
2608 exec->inputStack[exec->inputStackNr].data = NULL;
2609}
2610
Daniel Veillardc0826a72004-08-10 14:17:33 +00002611/**
2612 * xmlRegStrEqualWildcard:
2613 * @expStr: the string to be evaluated
2614 * @valStr: the validation string
2615 *
2616 * Checks if both strings are equal or have the same content. "*"
2617 * can be used as a wildcard in @valStr; "|" is used as a seperator of
2618 * substrings in both @expStr and @valStr.
2619 *
2620 * Returns 1 if the comparison is satisfied and the number of substrings
2621 * is equal, 0 otherwise.
2622 */
2623
2624static int
2625xmlRegStrEqualWildcard(const xmlChar *expStr, const xmlChar *valStr) {
2626 if (expStr == valStr) return(1);
2627 if (expStr == NULL) return(0);
2628 if (valStr == NULL) return(0);
2629 do {
2630 /*
2631 * Eval if we have a wildcard for the current item.
2632 */
2633 if (*expStr != *valStr) {
2634 if ((*valStr != 0) && (*expStr != 0) && (*expStr++ == '*')) {
2635 do {
2636 if (*valStr == XML_REG_STRING_SEPARATOR)
2637 break;
2638 *valStr++;
2639 } while (*valStr != 0);
2640 continue;
2641 } else
2642 return(0);
2643 }
2644 *expStr++;
2645 *valStr++;
2646 } while (*valStr != 0);
2647 if (*expStr != 0)
2648 return (0);
2649 else
2650 return (1);
2651}
Daniel Veillard4255d502002-04-16 15:50:10 +00002652
2653/**
Daniel Veillard23e73572002-09-19 19:56:43 +00002654 * xmlRegCompactPushString:
2655 * @exec: a regexp execution context
2656 * @comp: the precompiled exec with a compact table
2657 * @value: a string token input
2658 * @data: data associated to the token to reuse in callbacks
2659 *
2660 * Push one input token in the execution context
2661 *
2662 * Returns: 1 if the regexp reached a final state, 0 if non-final, and
2663 * a negative value in case of error.
2664 */
2665static int
2666xmlRegCompactPushString(xmlRegExecCtxtPtr exec,
2667 xmlRegexpPtr comp,
2668 const xmlChar *value,
2669 void *data) {
2670 int state = exec->index;
2671 int i, target;
2672
2673 if ((comp == NULL) || (comp->compact == NULL) || (comp->stringMap == NULL))
2674 return(-1);
2675
2676 if (value == NULL) {
2677 /*
2678 * are we at a final state ?
2679 */
2680 if (comp->compact[state * (comp->nbstrings + 1)] ==
2681 XML_REGEXP_FINAL_STATE)
2682 return(1);
2683 return(0);
2684 }
2685
2686#ifdef DEBUG_PUSH
2687 printf("value pushed: %s\n", value);
2688#endif
2689
2690 /*
William M. Brackddf71d62004-05-06 04:17:26 +00002691 * Examine all outside transitions from current state
Daniel Veillard23e73572002-09-19 19:56:43 +00002692 */
2693 for (i = 0;i < comp->nbstrings;i++) {
2694 target = comp->compact[state * (comp->nbstrings + 1) + i + 1];
2695 if ((target > 0) && (target <= comp->nbstates)) {
Daniel Veillardc0826a72004-08-10 14:17:33 +00002696 target--; /* to avoid 0 */
2697 if (xmlRegStrEqualWildcard(comp->stringMap[i], value)) {
2698 exec->index = target;
Daniel Veillard118aed72002-09-24 14:13:13 +00002699 if ((exec->callback != NULL) && (comp->transdata != NULL)) {
2700 exec->callback(exec->data, value,
2701 comp->transdata[state * comp->nbstrings + i], data);
2702 }
Daniel Veillard23e73572002-09-19 19:56:43 +00002703#ifdef DEBUG_PUSH
2704 printf("entering state %d\n", target);
2705#endif
2706 if (comp->compact[target * (comp->nbstrings + 1)] ==
Daniel Veillardcc026dc2005-01-12 13:21:17 +00002707 XML_REGEXP_SINK_STATE)
2708 goto error;
2709
2710 if (comp->compact[target * (comp->nbstrings + 1)] ==
Daniel Veillard23e73572002-09-19 19:56:43 +00002711 XML_REGEXP_FINAL_STATE)
2712 return(1);
2713 return(0);
2714 }
2715 }
2716 }
2717 /*
2718 * Failed to find an exit transition out from current state for the
2719 * current token
2720 */
2721#ifdef DEBUG_PUSH
2722 printf("failed to find a transition for %s on state %d\n", value, state);
2723#endif
Daniel Veillardcc026dc2005-01-12 13:21:17 +00002724error:
Daniel Veillard7bd8b4b2005-01-07 13:56:19 +00002725 if (exec->errString != NULL)
2726 xmlFree(exec->errString);
2727 exec->errString = xmlStrdup(value);
2728 exec->errStateNo = state;
Daniel Veillard23e73572002-09-19 19:56:43 +00002729 exec->status = -1;
Daniel Veillard7bd8b4b2005-01-07 13:56:19 +00002730#ifdef DEBUG_ERR
2731 testerr(exec);
2732#endif
Daniel Veillard23e73572002-09-19 19:56:43 +00002733 return(-1);
2734}
2735
2736/**
Daniel Veillard4255d502002-04-16 15:50:10 +00002737 * xmlRegExecPushString:
Daniel Veillardea7751d2002-12-20 00:16:24 +00002738 * @exec: a regexp execution context or NULL to indicate the end
Daniel Veillard4255d502002-04-16 15:50:10 +00002739 * @value: a string token input
2740 * @data: data associated to the token to reuse in callbacks
2741 *
2742 * Push one input token in the execution context
2743 *
2744 * Returns: 1 if the regexp reached a final state, 0 if non-final, and
2745 * a negative value in case of error.
2746 */
2747int
2748xmlRegExecPushString(xmlRegExecCtxtPtr exec, const xmlChar *value,
2749 void *data) {
2750 xmlRegTransPtr trans;
2751 xmlRegAtomPtr atom;
2752 int ret;
2753 int final = 0;
Daniel Veillard90700152005-01-08 22:05:09 +00002754 int progress = 1;
Daniel Veillard4255d502002-04-16 15:50:10 +00002755
2756 if (exec == NULL)
2757 return(-1);
Daniel Veillard23e73572002-09-19 19:56:43 +00002758 if (exec->comp == NULL)
2759 return(-1);
Daniel Veillard4255d502002-04-16 15:50:10 +00002760 if (exec->status != 0)
2761 return(exec->status);
2762
Daniel Veillard23e73572002-09-19 19:56:43 +00002763 if (exec->comp->compact != NULL)
2764 return(xmlRegCompactPushString(exec, exec->comp, value, data));
2765
Daniel Veillard4255d502002-04-16 15:50:10 +00002766 if (value == NULL) {
2767 if (exec->state->type == XML_REGEXP_FINAL_STATE)
2768 return(1);
2769 final = 1;
2770 }
2771
2772#ifdef DEBUG_PUSH
2773 printf("value pushed: %s\n", value);
2774#endif
2775 /*
2776 * If we have an active rollback stack push the new value there
2777 * and get back to where we were left
2778 */
2779 if ((value != NULL) && (exec->inputStackNr > 0)) {
2780 xmlFARegExecSaveInputString(exec, value, data);
2781 value = exec->inputStack[exec->index].value;
2782 data = exec->inputStack[exec->index].data;
2783#ifdef DEBUG_PUSH
2784 printf("value loaded: %s\n", value);
2785#endif
2786 }
2787
2788 while ((exec->status == 0) &&
2789 ((value != NULL) ||
2790 ((final == 1) &&
2791 (exec->state->type != XML_REGEXP_FINAL_STATE)))) {
2792
2793 /*
2794 * End of input on non-terminal state, rollback, however we may
2795 * still have epsilon like transition for counted transitions
2796 * on counters, in that case don't break too early.
2797 */
Daniel Veillardb509f152002-04-17 16:28:10 +00002798 if ((value == NULL) && (exec->counts == NULL))
Daniel Veillard4255d502002-04-16 15:50:10 +00002799 goto rollback;
2800
2801 exec->transcount = 0;
2802 for (;exec->transno < exec->state->nbTrans;exec->transno++) {
2803 trans = &exec->state->trans[exec->transno];
2804 if (trans->to < 0)
2805 continue;
2806 atom = trans->atom;
2807 ret = 0;
Daniel Veillard441bc322002-04-20 17:38:48 +00002808 if (trans->count == REGEXP_ALL_LAX_COUNTER) {
2809 int i;
2810 int count;
2811 xmlRegTransPtr t;
2812 xmlRegCounterPtr counter;
2813
2814 ret = 0;
2815
2816#ifdef DEBUG_PUSH
2817 printf("testing all lax %d\n", trans->count);
2818#endif
2819 /*
2820 * Check all counted transitions from the current state
2821 */
2822 if ((value == NULL) && (final)) {
2823 ret = 1;
2824 } else if (value != NULL) {
2825 for (i = 0;i < exec->state->nbTrans;i++) {
2826 t = &exec->state->trans[i];
2827 if ((t->counter < 0) || (t == trans))
2828 continue;
2829 counter = &exec->comp->counters[t->counter];
2830 count = exec->counts[t->counter];
2831 if ((count < counter->max) &&
2832 (t->atom != NULL) &&
2833 (xmlStrEqual(value, t->atom->valuep))) {
2834 ret = 0;
2835 break;
2836 }
2837 if ((count >= counter->min) &&
2838 (count < counter->max) &&
2839 (xmlStrEqual(value, t->atom->valuep))) {
2840 ret = 1;
2841 break;
2842 }
2843 }
2844 }
2845 } else if (trans->count == REGEXP_ALL_COUNTER) {
Daniel Veillard8a001f62002-04-20 07:24:11 +00002846 int i;
2847 int count;
2848 xmlRegTransPtr t;
2849 xmlRegCounterPtr counter;
2850
2851 ret = 1;
2852
2853#ifdef DEBUG_PUSH
2854 printf("testing all %d\n", trans->count);
2855#endif
2856 /*
2857 * Check all counted transitions from the current state
2858 */
2859 for (i = 0;i < exec->state->nbTrans;i++) {
2860 t = &exec->state->trans[i];
2861 if ((t->counter < 0) || (t == trans))
2862 continue;
2863 counter = &exec->comp->counters[t->counter];
2864 count = exec->counts[t->counter];
2865 if ((count < counter->min) || (count > counter->max)) {
2866 ret = 0;
2867 break;
2868 }
2869 }
2870 } else if (trans->count >= 0) {
Daniel Veillard4255d502002-04-16 15:50:10 +00002871 int count;
2872 xmlRegCounterPtr counter;
2873
2874 /*
2875 * A counted transition.
2876 */
2877
2878 count = exec->counts[trans->count];
2879 counter = &exec->comp->counters[trans->count];
2880#ifdef DEBUG_PUSH
2881 printf("testing count %d: val %d, min %d, max %d\n",
2882 trans->count, count, counter->min, counter->max);
2883#endif
2884 ret = ((count >= counter->min) && (count <= counter->max));
2885 } else if (atom == NULL) {
2886 fprintf(stderr, "epsilon transition left at runtime\n");
2887 exec->status = -2;
2888 break;
2889 } else if (value != NULL) {
Daniel Veillardc0826a72004-08-10 14:17:33 +00002890 ret = xmlRegStrEqualWildcard(atom->valuep, value);
Daniel Veillard441bc322002-04-20 17:38:48 +00002891 if ((ret == 1) && (trans->counter >= 0)) {
2892 xmlRegCounterPtr counter;
2893 int count;
2894
2895 count = exec->counts[trans->counter];
2896 counter = &exec->comp->counters[trans->counter];
2897 if (count >= counter->max)
2898 ret = 0;
2899 }
2900
Daniel Veillard4255d502002-04-16 15:50:10 +00002901 if ((ret == 1) && (atom->min > 0) && (atom->max > 0)) {
2902 xmlRegStatePtr to = exec->comp->states[trans->to];
2903
2904 /*
2905 * this is a multiple input sequence
2906 */
2907 if (exec->state->nbTrans > exec->transno + 1) {
2908 if (exec->inputStackNr <= 0) {
2909 xmlFARegExecSaveInputString(exec, value, data);
2910 }
2911 xmlFARegExecSave(exec);
2912 }
2913 exec->transcount = 1;
2914 do {
2915 /*
2916 * Try to progress as much as possible on the input
2917 */
2918 if (exec->transcount == atom->max) {
2919 break;
2920 }
2921 exec->index++;
2922 value = exec->inputStack[exec->index].value;
2923 data = exec->inputStack[exec->index].data;
2924#ifdef DEBUG_PUSH
2925 printf("value loaded: %s\n", value);
2926#endif
2927
2928 /*
2929 * End of input: stop here
2930 */
2931 if (value == NULL) {
2932 exec->index --;
2933 break;
2934 }
2935 if (exec->transcount >= atom->min) {
2936 int transno = exec->transno;
2937 xmlRegStatePtr state = exec->state;
2938
2939 /*
2940 * The transition is acceptable save it
2941 */
2942 exec->transno = -1; /* trick */
2943 exec->state = to;
2944 if (exec->inputStackNr <= 0) {
2945 xmlFARegExecSaveInputString(exec, value, data);
2946 }
2947 xmlFARegExecSave(exec);
2948 exec->transno = transno;
2949 exec->state = state;
2950 }
2951 ret = xmlStrEqual(value, atom->valuep);
2952 exec->transcount++;
2953 } while (ret == 1);
2954 if (exec->transcount < atom->min)
2955 ret = 0;
2956
2957 /*
2958 * If the last check failed but one transition was found
2959 * possible, rollback
2960 */
2961 if (ret < 0)
2962 ret = 0;
2963 if (ret == 0) {
2964 goto rollback;
2965 }
2966 }
2967 }
2968 if (ret == 1) {
William M. Brack98873952003-12-26 06:03:14 +00002969 if ((exec->callback != NULL) && (atom != NULL) &&
2970 (data != NULL)) {
Daniel Veillard4255d502002-04-16 15:50:10 +00002971 exec->callback(exec->data, atom->valuep,
2972 atom->data, data);
2973 }
2974 if (exec->state->nbTrans > exec->transno + 1) {
2975 if (exec->inputStackNr <= 0) {
2976 xmlFARegExecSaveInputString(exec, value, data);
2977 }
2978 xmlFARegExecSave(exec);
2979 }
2980 if (trans->counter >= 0) {
2981#ifdef DEBUG_PUSH
2982 printf("Increasing count %d\n", trans->counter);
2983#endif
2984 exec->counts[trans->counter]++;
2985 }
2986#ifdef DEBUG_PUSH
2987 printf("entering state %d\n", trans->to);
2988#endif
Daniel Veillardcc026dc2005-01-12 13:21:17 +00002989 if ((exec->comp->states[trans->to] != NULL) &&
2990 (exec->comp->states[trans->to]->type ==
2991 XML_REGEXP_SINK_STATE)) {
2992 /*
2993 * entering a sink state, save the current state as error
2994 * state.
2995 */
2996 if (exec->errString != NULL)
2997 xmlFree(exec->errString);
2998 exec->errString = xmlStrdup(value);
2999 exec->errState = exec->state;
3000 memcpy(exec->errCounts, exec->counts,
3001 exec->comp->nbCounters * sizeof(int));
3002 }
Daniel Veillard4255d502002-04-16 15:50:10 +00003003 exec->state = exec->comp->states[trans->to];
3004 exec->transno = 0;
3005 if (trans->atom != NULL) {
3006 if (exec->inputStack != NULL) {
3007 exec->index++;
3008 if (exec->index < exec->inputStackNr) {
3009 value = exec->inputStack[exec->index].value;
3010 data = exec->inputStack[exec->index].data;
3011#ifdef DEBUG_PUSH
3012 printf("value loaded: %s\n", value);
3013#endif
3014 } else {
3015 value = NULL;
3016 data = NULL;
3017#ifdef DEBUG_PUSH
3018 printf("end of input\n");
3019#endif
3020 }
3021 } else {
3022 value = NULL;
3023 data = NULL;
3024#ifdef DEBUG_PUSH
3025 printf("end of input\n");
3026#endif
3027 }
3028 }
3029 goto progress;
3030 } else if (ret < 0) {
3031 exec->status = -4;
3032 break;
3033 }
3034 }
3035 if ((exec->transno != 0) || (exec->state->nbTrans == 0)) {
3036rollback:
Daniel Veillard90700152005-01-08 22:05:09 +00003037 /*
Daniel Veillardcc026dc2005-01-12 13:21:17 +00003038 * if we didn't yet rollback on the current input
3039 * store the current state as the error state.
Daniel Veillard90700152005-01-08 22:05:09 +00003040 */
Daniel Veillardcc026dc2005-01-12 13:21:17 +00003041 if ((progress) && (exec->state != NULL) &&
3042 (exec->state->type != XML_REGEXP_SINK_STATE)) {
Daniel Veillard90700152005-01-08 22:05:09 +00003043 progress = 0;
3044 if (exec->errString != NULL)
3045 xmlFree(exec->errString);
3046 exec->errString = xmlStrdup(value);
3047 exec->errState = exec->state;
3048 memcpy(exec->errCounts, exec->counts,
3049 exec->comp->nbCounters * sizeof(int));
3050 }
3051
Daniel Veillard4255d502002-04-16 15:50:10 +00003052 /*
3053 * Failed to find a way out
3054 */
3055 exec->determinist = 0;
3056 xmlFARegExecRollBack(exec);
3057 if (exec->status == 0) {
3058 value = exec->inputStack[exec->index].value;
3059 data = exec->inputStack[exec->index].data;
3060#ifdef DEBUG_PUSH
3061 printf("value loaded: %s\n", value);
3062#endif
3063 }
3064 }
Daniel Veillard90700152005-01-08 22:05:09 +00003065 continue;
Daniel Veillard4255d502002-04-16 15:50:10 +00003066progress:
Daniel Veillard90700152005-01-08 22:05:09 +00003067 progress = 1;
Daniel Veillard4255d502002-04-16 15:50:10 +00003068 continue;
3069 }
3070 if (exec->status == 0) {
3071 return(exec->state->type == XML_REGEXP_FINAL_STATE);
3072 }
Daniel Veillard7bd8b4b2005-01-07 13:56:19 +00003073#ifdef DEBUG_ERR
Daniel Veillard90700152005-01-08 22:05:09 +00003074 if (exec->status < 0) {
Daniel Veillard7bd8b4b2005-01-07 13:56:19 +00003075 testerr(exec);
Daniel Veillard7bd8b4b2005-01-07 13:56:19 +00003076 }
Daniel Veillard90700152005-01-08 22:05:09 +00003077#endif
Daniel Veillard4255d502002-04-16 15:50:10 +00003078 return(exec->status);
3079}
3080
Daniel Veillard52b48c72003-04-13 19:53:42 +00003081/**
3082 * xmlRegExecPushString2:
3083 * @exec: a regexp execution context or NULL to indicate the end
3084 * @value: the first string token input
3085 * @value2: the second string token input
3086 * @data: data associated to the token to reuse in callbacks
3087 *
3088 * Push one input token in the execution context
3089 *
3090 * Returns: 1 if the regexp reached a final state, 0 if non-final, and
3091 * a negative value in case of error.
3092 */
3093int
3094xmlRegExecPushString2(xmlRegExecCtxtPtr exec, const xmlChar *value,
3095 const xmlChar *value2, void *data) {
3096 xmlChar buf[150];
3097 int lenn, lenp, ret;
3098 xmlChar *str;
3099
3100 if (exec == NULL)
3101 return(-1);
3102 if (exec->comp == NULL)
3103 return(-1);
3104 if (exec->status != 0)
3105 return(exec->status);
3106
3107 if (value2 == NULL)
3108 return(xmlRegExecPushString(exec, value, data));
3109
3110 lenn = strlen((char *) value2);
3111 lenp = strlen((char *) value);
3112
3113 if (150 < lenn + lenp + 2) {
Daniel Veillard3c908dc2003-04-19 00:07:51 +00003114 str = (xmlChar *) xmlMallocAtomic(lenn + lenp + 2);
Daniel Veillard52b48c72003-04-13 19:53:42 +00003115 if (str == NULL) {
3116 exec->status = -1;
3117 return(-1);
3118 }
3119 } else {
3120 str = buf;
3121 }
3122 memcpy(&str[0], value, lenp);
Daniel Veillardc0826a72004-08-10 14:17:33 +00003123 str[lenp] = XML_REG_STRING_SEPARATOR;
Daniel Veillard52b48c72003-04-13 19:53:42 +00003124 memcpy(&str[lenp + 1], value2, lenn);
3125 str[lenn + lenp + 1] = 0;
3126
3127 if (exec->comp->compact != NULL)
3128 ret = xmlRegCompactPushString(exec, exec->comp, str, data);
3129 else
3130 ret = xmlRegExecPushString(exec, str, data);
3131
3132 if (str != buf)
3133 xmlFree(buf);
3134 return(ret);
3135}
3136
Daniel Veillard7bd8b4b2005-01-07 13:56:19 +00003137/**
Daniel Veillardfc0b6f62005-01-09 17:48:02 +00003138 * xmlRegExecGetalues:
3139 * @exec: a regexp execution context
3140 * @err: error extraction or normal one
Daniel Veillard7bd8b4b2005-01-07 13:56:19 +00003141 * @nbval: pointer to the number of accepted values IN/OUT
Daniel Veillardcc026dc2005-01-12 13:21:17 +00003142 * @nbneg: return number of negative transitions
Daniel Veillard7bd8b4b2005-01-07 13:56:19 +00003143 * @values: pointer to the array of acceptable values
Daniel Veillardfc0b6f62005-01-09 17:48:02 +00003144 * @terminal: return value if this was a terminal state
Daniel Veillard7bd8b4b2005-01-07 13:56:19 +00003145 *
Daniel Veillardfc0b6f62005-01-09 17:48:02 +00003146 * Extract informations from the regexp execution, internal routine to
3147 * implement xmlRegExecNextValues() and xmlRegExecErrInfo()
Daniel Veillard7bd8b4b2005-01-07 13:56:19 +00003148 *
3149 * Returns: 0 in case of success or -1 in case of error.
3150 */
Daniel Veillardfc0b6f62005-01-09 17:48:02 +00003151static int
3152xmlRegExecGetValues(xmlRegExecCtxtPtr exec, int err,
Daniel Veillardcc026dc2005-01-12 13:21:17 +00003153 int *nbval, int *nbneg,
3154 xmlChar **values, int *terminal) {
Daniel Veillard7bd8b4b2005-01-07 13:56:19 +00003155 int maxval;
Daniel Veillardcc026dc2005-01-12 13:21:17 +00003156 int nb = 0;
Daniel Veillard7bd8b4b2005-01-07 13:56:19 +00003157
Daniel Veillardcc026dc2005-01-12 13:21:17 +00003158 if ((exec == NULL) || (nbval == NULL) || (nbneg == NULL) ||
3159 (values == NULL) || (*nbval <= 0))
Daniel Veillard7bd8b4b2005-01-07 13:56:19 +00003160 return(-1);
Daniel Veillardfc0b6f62005-01-09 17:48:02 +00003161
Daniel Veillard7bd8b4b2005-01-07 13:56:19 +00003162 maxval = *nbval;
3163 *nbval = 0;
Daniel Veillardcc026dc2005-01-12 13:21:17 +00003164 *nbneg = 0;
Daniel Veillard7bd8b4b2005-01-07 13:56:19 +00003165 if ((exec->comp != NULL) && (exec->comp->compact != NULL)) {
3166 xmlRegexpPtr comp;
3167 int target, i, state;
3168
3169 comp = exec->comp;
Daniel Veillardfc0b6f62005-01-09 17:48:02 +00003170
3171 if (err) {
3172 if (exec->errStateNo == -1) return(-1);
3173 state = exec->errStateNo;
3174 } else {
3175 state = exec->index;
3176 }
3177 if (terminal != NULL) {
3178 if (comp->compact[state * (comp->nbstrings + 1)] ==
3179 XML_REGEXP_FINAL_STATE)
3180 *terminal = 1;
3181 else
3182 *terminal = 0;
3183 }
Daniel Veillardcc026dc2005-01-12 13:21:17 +00003184 for (i = 0;(i < comp->nbstrings) && (nb < maxval);i++) {
Daniel Veillard7bd8b4b2005-01-07 13:56:19 +00003185 target = comp->compact[state * (comp->nbstrings + 1) + i + 1];
Daniel Veillardcc026dc2005-01-12 13:21:17 +00003186 if ((target > 0) && (target <= comp->nbstates) &&
3187 (comp->compact[(target - 1) * (comp->nbstrings + 1)] !=
3188 XML_REGEXP_SINK_STATE)) {
3189 values[nb++] = comp->stringMap[i];
Daniel Veillard7bd8b4b2005-01-07 13:56:19 +00003190 (*nbval)++;
3191 }
3192 }
Daniel Veillardcc026dc2005-01-12 13:21:17 +00003193 for (i = 0;(i < comp->nbstrings) && (nb < maxval);i++) {
3194 target = comp->compact[state * (comp->nbstrings + 1) + i + 1];
3195 if ((target > 0) && (target <= comp->nbstates) &&
3196 (comp->compact[(target - 1) * (comp->nbstrings + 1)] ==
3197 XML_REGEXP_SINK_STATE)) {
3198 values[nb++] = comp->stringMap[i];
3199 (*nbneg)++;
3200 }
3201 }
Daniel Veillard7bd8b4b2005-01-07 13:56:19 +00003202 } else {
3203 int transno;
3204 xmlRegTransPtr trans;
3205 xmlRegAtomPtr atom;
Daniel Veillardfc0b6f62005-01-09 17:48:02 +00003206 xmlRegStatePtr state;
Daniel Veillard7bd8b4b2005-01-07 13:56:19 +00003207
Daniel Veillardfc0b6f62005-01-09 17:48:02 +00003208 if (terminal != NULL) {
3209 if (exec->state->type == XML_REGEXP_FINAL_STATE)
3210 *terminal = 1;
3211 else
3212 *terminal = 0;
3213 }
3214
3215 if (err) {
3216 if (exec->errState == NULL) return(-1);
3217 state = exec->errState;
3218 } else {
3219 if (exec->state == NULL) return(-1);
3220 state = exec->state;
3221 }
Daniel Veillard7bd8b4b2005-01-07 13:56:19 +00003222 for (transno = 0;
Daniel Veillardcc026dc2005-01-12 13:21:17 +00003223 (transno < state->nbTrans) && (nb < maxval);
Daniel Veillard7bd8b4b2005-01-07 13:56:19 +00003224 transno++) {
Daniel Veillardfc0b6f62005-01-09 17:48:02 +00003225 trans = &state->trans[transno];
Daniel Veillard7bd8b4b2005-01-07 13:56:19 +00003226 if (trans->to < 0)
3227 continue;
3228 atom = trans->atom;
3229 if ((atom == NULL) || (atom->valuep == NULL))
3230 continue;
3231 if (trans->count == REGEXP_ALL_LAX_COUNTER) {
Daniel Veillardcc026dc2005-01-12 13:21:17 +00003232 /* this should not be reached but ... */
Daniel Veillard7bd8b4b2005-01-07 13:56:19 +00003233 TODO;
3234 } else if (trans->count == REGEXP_ALL_COUNTER) {
Daniel Veillardcc026dc2005-01-12 13:21:17 +00003235 /* this should not be reached but ... */
Daniel Veillard7bd8b4b2005-01-07 13:56:19 +00003236 TODO;
3237 } else if (trans->counter >= 0) {
3238 xmlRegCounterPtr counter;
3239 int count;
3240
Daniel Veillardfc0b6f62005-01-09 17:48:02 +00003241 if (err)
3242 count = exec->errCounts[trans->counter];
3243 else
3244 count = exec->counts[trans->counter];
Daniel Veillard7bd8b4b2005-01-07 13:56:19 +00003245 counter = &exec->comp->counters[trans->counter];
3246 if (count < counter->max) {
Daniel Veillardcc026dc2005-01-12 13:21:17 +00003247 values[nb++] = (xmlChar *) atom->valuep;
Daniel Veillard7bd8b4b2005-01-07 13:56:19 +00003248 (*nbval)++;
3249 }
3250 } else {
Daniel Veillardcc026dc2005-01-12 13:21:17 +00003251 if ((exec->comp->states[trans->to] != NULL) &&
3252 (exec->comp->states[trans->to]->type !=
3253 XML_REGEXP_SINK_STATE)) {
3254 values[nb++] = (xmlChar *) atom->valuep;
3255 (*nbval)++;
3256 }
3257 }
3258 }
3259 for (transno = 0;
3260 (transno < state->nbTrans) && (nb < maxval);
3261 transno++) {
3262 trans = &state->trans[transno];
3263 if (trans->to < 0)
3264 continue;
3265 atom = trans->atom;
3266 if ((atom == NULL) || (atom->valuep == NULL))
3267 continue;
3268 if (trans->count == REGEXP_ALL_LAX_COUNTER) {
3269 continue;
3270 } else if (trans->count == REGEXP_ALL_COUNTER) {
3271 continue;
3272 } else if (trans->counter >= 0) {
3273 continue;
3274 } else {
3275 if ((exec->comp->states[trans->to] != NULL) &&
3276 (exec->comp->states[trans->to]->type ==
3277 XML_REGEXP_SINK_STATE)) {
3278 values[nb++] = (xmlChar *) atom->valuep;
3279 (*nbneg)++;
3280 }
Daniel Veillard7bd8b4b2005-01-07 13:56:19 +00003281 }
3282 }
3283 }
3284 return(0);
3285}
3286
Daniel Veillardfc0b6f62005-01-09 17:48:02 +00003287/**
3288 * xmlRegExecNextValues:
3289 * @exec: a regexp execution context
3290 * @nbval: pointer to the number of accepted values IN/OUT
Daniel Veillardcc026dc2005-01-12 13:21:17 +00003291 * @nbneg: return number of negative transitions
Daniel Veillardfc0b6f62005-01-09 17:48:02 +00003292 * @values: pointer to the array of acceptable values
3293 * @terminal: return value if this was a terminal state
3294 *
3295 * Extract informations from the regexp execution,
3296 * the parameter @values must point to an array of @nbval string pointers
3297 * on return nbval will contain the number of possible strings in that
3298 * state and the @values array will be updated with them. The string values
3299 * returned will be freed with the @exec context and don't need to be
3300 * deallocated.
3301 *
3302 * Returns: 0 in case of success or -1 in case of error.
3303 */
3304int
Daniel Veillardcc026dc2005-01-12 13:21:17 +00003305xmlRegExecNextValues(xmlRegExecCtxtPtr exec, int *nbval, int *nbneg,
3306 xmlChar **values, int *terminal) {
3307 return(xmlRegExecGetValues(exec, 0, nbval, nbneg, values, terminal));
Daniel Veillardfc0b6f62005-01-09 17:48:02 +00003308}
3309
3310/**
3311 * xmlRegExecErrInfo:
3312 * @exec: a regexp execution context generating an error
3313 * @string: return value for the error string
3314 * @nbval: pointer to the number of accepted values IN/OUT
Daniel Veillardcc026dc2005-01-12 13:21:17 +00003315 * @nbneg: return number of negative transitions
Daniel Veillardfc0b6f62005-01-09 17:48:02 +00003316 * @values: pointer to the array of acceptable values
3317 * @terminal: return value if this was a terminal state
3318 *
3319 * Extract error informations from the regexp execution, the parameter
3320 * @string will be updated with the value pushed and not accepted,
3321 * the parameter @values must point to an array of @nbval string pointers
3322 * on return nbval will contain the number of possible strings in that
3323 * state and the @values array will be updated with them. The string values
3324 * returned will be freed with the @exec context and don't need to be
3325 * deallocated.
3326 *
3327 * Returns: 0 in case of success or -1 in case of error.
3328 */
3329int
3330xmlRegExecErrInfo(xmlRegExecCtxtPtr exec, const xmlChar **string,
Daniel Veillardcc026dc2005-01-12 13:21:17 +00003331 int *nbval, int *nbneg, xmlChar **values, int *terminal) {
Daniel Veillardfc0b6f62005-01-09 17:48:02 +00003332 if (exec == NULL)
3333 return(-1);
3334 if (string != NULL) {
3335 if (exec->status != 0)
3336 *string = exec->errString;
3337 else
3338 *string = NULL;
3339 }
Daniel Veillardcc026dc2005-01-12 13:21:17 +00003340 return(xmlRegExecGetValues(exec, 1, nbval, nbneg, values, terminal));
Daniel Veillardfc0b6f62005-01-09 17:48:02 +00003341}
3342
Daniel Veillard7bd8b4b2005-01-07 13:56:19 +00003343#ifdef DEBUG_ERR
3344static void testerr(xmlRegExecCtxtPtr exec) {
3345 const xmlChar *string;
Daniel Veillardcee2b3a2005-01-25 00:22:52 +00003346 xmlChar *values[5];
Daniel Veillard7bd8b4b2005-01-07 13:56:19 +00003347 int nb = 5;
Daniel Veillardcc026dc2005-01-12 13:21:17 +00003348 int nbneg;
Daniel Veillardfc0b6f62005-01-09 17:48:02 +00003349 int terminal;
Daniel Veillardcc026dc2005-01-12 13:21:17 +00003350 xmlRegExecErrInfo(exec, &string, &nb, &nbneg, &values[0], &terminal);
Daniel Veillard7bd8b4b2005-01-07 13:56:19 +00003351}
3352#endif
3353
Daniel Veillard4255d502002-04-16 15:50:10 +00003354#if 0
3355static int
3356xmlRegExecPushChar(xmlRegExecCtxtPtr exec, int UCS) {
3357 xmlRegTransPtr trans;
3358 xmlRegAtomPtr atom;
3359 int ret;
3360 int codepoint, len;
3361
3362 if (exec == NULL)
3363 return(-1);
3364 if (exec->status != 0)
3365 return(exec->status);
3366
3367 while ((exec->status == 0) &&
3368 ((exec->inputString[exec->index] != 0) ||
3369 (exec->state->type != XML_REGEXP_FINAL_STATE))) {
3370
3371 /*
3372 * End of input on non-terminal state, rollback, however we may
3373 * still have epsilon like transition for counted transitions
3374 * on counters, in that case don't break too early.
3375 */
3376 if ((exec->inputString[exec->index] == 0) && (exec->counts == NULL))
3377 goto rollback;
3378
3379 exec->transcount = 0;
3380 for (;exec->transno < exec->state->nbTrans;exec->transno++) {
3381 trans = &exec->state->trans[exec->transno];
3382 if (trans->to < 0)
3383 continue;
3384 atom = trans->atom;
3385 ret = 0;
3386 if (trans->count >= 0) {
3387 int count;
3388 xmlRegCounterPtr counter;
3389
3390 /*
3391 * A counted transition.
3392 */
3393
3394 count = exec->counts[trans->count];
3395 counter = &exec->comp->counters[trans->count];
3396#ifdef DEBUG_REGEXP_EXEC
3397 printf("testing count %d: val %d, min %d, max %d\n",
3398 trans->count, count, counter->min, counter->max);
3399#endif
3400 ret = ((count >= counter->min) && (count <= counter->max));
3401 } else if (atom == NULL) {
3402 fprintf(stderr, "epsilon transition left at runtime\n");
3403 exec->status = -2;
3404 break;
3405 } else if (exec->inputString[exec->index] != 0) {
3406 codepoint = CUR_SCHAR(&(exec->inputString[exec->index]), len);
3407 ret = xmlRegCheckCharacter(atom, codepoint);
3408 if ((ret == 1) && (atom->min > 0) && (atom->max > 0)) {
3409 xmlRegStatePtr to = exec->comp->states[trans->to];
3410
3411 /*
3412 * this is a multiple input sequence
3413 */
3414 if (exec->state->nbTrans > exec->transno + 1) {
3415 xmlFARegExecSave(exec);
3416 }
3417 exec->transcount = 1;
3418 do {
3419 /*
3420 * Try to progress as much as possible on the input
3421 */
3422 if (exec->transcount == atom->max) {
3423 break;
3424 }
3425 exec->index += len;
3426 /*
3427 * End of input: stop here
3428 */
3429 if (exec->inputString[exec->index] == 0) {
3430 exec->index -= len;
3431 break;
3432 }
3433 if (exec->transcount >= atom->min) {
3434 int transno = exec->transno;
3435 xmlRegStatePtr state = exec->state;
3436
3437 /*
3438 * The transition is acceptable save it
3439 */
3440 exec->transno = -1; /* trick */
3441 exec->state = to;
3442 xmlFARegExecSave(exec);
3443 exec->transno = transno;
3444 exec->state = state;
3445 }
3446 codepoint = CUR_SCHAR(&(exec->inputString[exec->index]),
3447 len);
3448 ret = xmlRegCheckCharacter(atom, codepoint);
3449 exec->transcount++;
3450 } while (ret == 1);
3451 if (exec->transcount < atom->min)
3452 ret = 0;
3453
3454 /*
3455 * If the last check failed but one transition was found
3456 * possible, rollback
3457 */
3458 if (ret < 0)
3459 ret = 0;
3460 if (ret == 0) {
3461 goto rollback;
3462 }
3463 }
3464 }
3465 if (ret == 1) {
3466 if (exec->state->nbTrans > exec->transno + 1) {
3467 xmlFARegExecSave(exec);
3468 }
3469 if (trans->counter >= 0) {
3470#ifdef DEBUG_REGEXP_EXEC
3471 printf("Increasing count %d\n", trans->counter);
3472#endif
3473 exec->counts[trans->counter]++;
3474 }
3475#ifdef DEBUG_REGEXP_EXEC
3476 printf("entering state %d\n", trans->to);
3477#endif
3478 exec->state = exec->comp->states[trans->to];
3479 exec->transno = 0;
3480 if (trans->atom != NULL) {
3481 exec->index += len;
3482 }
3483 goto progress;
3484 } else if (ret < 0) {
3485 exec->status = -4;
3486 break;
3487 }
3488 }
3489 if ((exec->transno != 0) || (exec->state->nbTrans == 0)) {
3490rollback:
3491 /*
3492 * Failed to find a way out
3493 */
3494 exec->determinist = 0;
3495 xmlFARegExecRollBack(exec);
3496 }
3497progress:
3498 continue;
3499 }
3500}
3501#endif
3502/************************************************************************
3503 * *
William M. Brackddf71d62004-05-06 04:17:26 +00003504 * Parser for the Schemas Datatype Regular Expressions *
Daniel Veillard4255d502002-04-16 15:50:10 +00003505 * http://www.w3.org/TR/2001/REC-xmlschema-2-20010502/#regexs *
3506 * *
3507 ************************************************************************/
3508
3509/**
3510 * xmlFAIsChar:
Daniel Veillard441bc322002-04-20 17:38:48 +00003511 * @ctxt: a regexp parser context
Daniel Veillard4255d502002-04-16 15:50:10 +00003512 *
3513 * [10] Char ::= [^.\?*+()|#x5B#x5D]
3514 */
3515static int
3516xmlFAIsChar(xmlRegParserCtxtPtr ctxt) {
3517 int cur;
3518 int len;
3519
3520 cur = CUR_SCHAR(ctxt->cur, len);
3521 if ((cur == '.') || (cur == '\\') || (cur == '?') ||
3522 (cur == '*') || (cur == '+') || (cur == '(') ||
3523 (cur == ')') || (cur == '|') || (cur == 0x5B) ||
3524 (cur == 0x5D) || (cur == 0))
3525 return(-1);
3526 return(cur);
3527}
3528
3529/**
3530 * xmlFAParseCharProp:
Daniel Veillard441bc322002-04-20 17:38:48 +00003531 * @ctxt: a regexp parser context
Daniel Veillard4255d502002-04-16 15:50:10 +00003532 *
3533 * [27] charProp ::= IsCategory | IsBlock
3534 * [28] IsCategory ::= Letters | Marks | Numbers | Punctuation |
3535 * Separators | Symbols | Others
3536 * [29] Letters ::= 'L' [ultmo]?
3537 * [30] Marks ::= 'M' [nce]?
3538 * [31] Numbers ::= 'N' [dlo]?
3539 * [32] Punctuation ::= 'P' [cdseifo]?
3540 * [33] Separators ::= 'Z' [slp]?
3541 * [34] Symbols ::= 'S' [mcko]?
3542 * [35] Others ::= 'C' [cfon]?
3543 * [36] IsBlock ::= 'Is' [a-zA-Z0-9#x2D]+
3544 */
3545static void
3546xmlFAParseCharProp(xmlRegParserCtxtPtr ctxt) {
3547 int cur;
William M. Brack779af002003-08-01 15:55:39 +00003548 xmlRegAtomType type = (xmlRegAtomType) 0;
Daniel Veillard4255d502002-04-16 15:50:10 +00003549 xmlChar *blockName = NULL;
3550
3551 cur = CUR;
3552 if (cur == 'L') {
3553 NEXT;
3554 cur = CUR;
3555 if (cur == 'u') {
3556 NEXT;
3557 type = XML_REGEXP_LETTER_UPPERCASE;
3558 } else if (cur == 'l') {
3559 NEXT;
3560 type = XML_REGEXP_LETTER_LOWERCASE;
3561 } else if (cur == 't') {
3562 NEXT;
3563 type = XML_REGEXP_LETTER_TITLECASE;
3564 } else if (cur == 'm') {
3565 NEXT;
3566 type = XML_REGEXP_LETTER_MODIFIER;
3567 } else if (cur == 'o') {
3568 NEXT;
3569 type = XML_REGEXP_LETTER_OTHERS;
3570 } else {
3571 type = XML_REGEXP_LETTER;
3572 }
3573 } else if (cur == 'M') {
3574 NEXT;
3575 cur = CUR;
3576 if (cur == 'n') {
3577 NEXT;
3578 /* nonspacing */
3579 type = XML_REGEXP_MARK_NONSPACING;
3580 } else if (cur == 'c') {
3581 NEXT;
3582 /* spacing combining */
3583 type = XML_REGEXP_MARK_SPACECOMBINING;
3584 } else if (cur == 'e') {
3585 NEXT;
3586 /* enclosing */
3587 type = XML_REGEXP_MARK_ENCLOSING;
3588 } else {
3589 /* all marks */
3590 type = XML_REGEXP_MARK;
3591 }
3592 } else if (cur == 'N') {
3593 NEXT;
3594 cur = CUR;
3595 if (cur == 'd') {
3596 NEXT;
3597 /* digital */
3598 type = XML_REGEXP_NUMBER_DECIMAL;
3599 } else if (cur == 'l') {
3600 NEXT;
3601 /* letter */
3602 type = XML_REGEXP_NUMBER_LETTER;
3603 } else if (cur == 'o') {
3604 NEXT;
3605 /* other */
3606 type = XML_REGEXP_NUMBER_OTHERS;
3607 } else {
3608 /* all numbers */
3609 type = XML_REGEXP_NUMBER;
3610 }
3611 } else if (cur == 'P') {
3612 NEXT;
3613 cur = CUR;
3614 if (cur == 'c') {
3615 NEXT;
3616 /* connector */
3617 type = XML_REGEXP_PUNCT_CONNECTOR;
3618 } else if (cur == 'd') {
3619 NEXT;
3620 /* dash */
3621 type = XML_REGEXP_PUNCT_DASH;
3622 } else if (cur == 's') {
3623 NEXT;
3624 /* open */
3625 type = XML_REGEXP_PUNCT_OPEN;
3626 } else if (cur == 'e') {
3627 NEXT;
3628 /* close */
3629 type = XML_REGEXP_PUNCT_CLOSE;
3630 } else if (cur == 'i') {
3631 NEXT;
3632 /* initial quote */
3633 type = XML_REGEXP_PUNCT_INITQUOTE;
3634 } else if (cur == 'f') {
3635 NEXT;
3636 /* final quote */
3637 type = XML_REGEXP_PUNCT_FINQUOTE;
3638 } else if (cur == 'o') {
3639 NEXT;
3640 /* other */
3641 type = XML_REGEXP_PUNCT_OTHERS;
3642 } else {
3643 /* all punctuation */
3644 type = XML_REGEXP_PUNCT;
3645 }
3646 } else if (cur == 'Z') {
3647 NEXT;
3648 cur = CUR;
3649 if (cur == 's') {
3650 NEXT;
3651 /* space */
3652 type = XML_REGEXP_SEPAR_SPACE;
3653 } else if (cur == 'l') {
3654 NEXT;
3655 /* line */
3656 type = XML_REGEXP_SEPAR_LINE;
3657 } else if (cur == 'p') {
3658 NEXT;
3659 /* paragraph */
3660 type = XML_REGEXP_SEPAR_PARA;
3661 } else {
3662 /* all separators */
3663 type = XML_REGEXP_SEPAR;
3664 }
3665 } else if (cur == 'S') {
3666 NEXT;
3667 cur = CUR;
3668 if (cur == 'm') {
3669 NEXT;
3670 type = XML_REGEXP_SYMBOL_MATH;
3671 /* math */
3672 } else if (cur == 'c') {
3673 NEXT;
3674 type = XML_REGEXP_SYMBOL_CURRENCY;
3675 /* currency */
3676 } else if (cur == 'k') {
3677 NEXT;
3678 type = XML_REGEXP_SYMBOL_MODIFIER;
3679 /* modifiers */
3680 } else if (cur == 'o') {
3681 NEXT;
3682 type = XML_REGEXP_SYMBOL_OTHERS;
3683 /* other */
3684 } else {
3685 /* all symbols */
3686 type = XML_REGEXP_SYMBOL;
3687 }
3688 } else if (cur == 'C') {
3689 NEXT;
3690 cur = CUR;
3691 if (cur == 'c') {
3692 NEXT;
3693 /* control */
3694 type = XML_REGEXP_OTHER_CONTROL;
3695 } else if (cur == 'f') {
3696 NEXT;
3697 /* format */
3698 type = XML_REGEXP_OTHER_FORMAT;
3699 } else if (cur == 'o') {
3700 NEXT;
3701 /* private use */
3702 type = XML_REGEXP_OTHER_PRIVATE;
3703 } else if (cur == 'n') {
3704 NEXT;
3705 /* not assigned */
3706 type = XML_REGEXP_OTHER_NA;
3707 } else {
3708 /* all others */
3709 type = XML_REGEXP_OTHER;
3710 }
3711 } else if (cur == 'I') {
3712 const xmlChar *start;
3713 NEXT;
3714 cur = CUR;
3715 if (cur != 's') {
3716 ERROR("IsXXXX expected");
3717 return;
3718 }
3719 NEXT;
3720 start = ctxt->cur;
3721 cur = CUR;
3722 if (((cur >= 'a') && (cur <= 'z')) ||
3723 ((cur >= 'A') && (cur <= 'Z')) ||
3724 ((cur >= '0') && (cur <= '9')) ||
3725 (cur == 0x2D)) {
3726 NEXT;
3727 cur = CUR;
3728 while (((cur >= 'a') && (cur <= 'z')) ||
3729 ((cur >= 'A') && (cur <= 'Z')) ||
3730 ((cur >= '0') && (cur <= '9')) ||
3731 (cur == 0x2D)) {
3732 NEXT;
3733 cur = CUR;
3734 }
3735 }
3736 type = XML_REGEXP_BLOCK_NAME;
3737 blockName = xmlStrndup(start, ctxt->cur - start);
3738 } else {
3739 ERROR("Unknown char property");
3740 return;
3741 }
3742 if (ctxt->atom == NULL) {
3743 ctxt->atom = xmlRegNewAtom(ctxt, type);
3744 if (ctxt->atom != NULL)
3745 ctxt->atom->valuep = blockName;
3746 } else if (ctxt->atom->type == XML_REGEXP_RANGES) {
3747 xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,
3748 type, 0, 0, blockName);
3749 }
3750}
3751
3752/**
3753 * xmlFAParseCharClassEsc:
Daniel Veillard441bc322002-04-20 17:38:48 +00003754 * @ctxt: a regexp parser context
Daniel Veillard4255d502002-04-16 15:50:10 +00003755 *
3756 * [23] charClassEsc ::= ( SingleCharEsc | MultiCharEsc | catEsc | complEsc )
3757 * [24] SingleCharEsc ::= '\' [nrt\|.?*+(){}#x2D#x5B#x5D#x5E]
3758 * [25] catEsc ::= '\p{' charProp '}'
3759 * [26] complEsc ::= '\P{' charProp '}'
3760 * [37] MultiCharEsc ::= '.' | ('\' [sSiIcCdDwW])
3761 */
3762static void
3763xmlFAParseCharClassEsc(xmlRegParserCtxtPtr ctxt) {
3764 int cur;
3765
3766 if (CUR == '.') {
3767 if (ctxt->atom == NULL) {
3768 ctxt->atom = xmlRegNewAtom(ctxt, XML_REGEXP_ANYCHAR);
3769 } else if (ctxt->atom->type == XML_REGEXP_RANGES) {
3770 xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,
3771 XML_REGEXP_ANYCHAR, 0, 0, NULL);
3772 }
3773 NEXT;
3774 return;
3775 }
3776 if (CUR != '\\') {
3777 ERROR("Escaped sequence: expecting \\");
3778 return;
3779 }
3780 NEXT;
3781 cur = CUR;
3782 if (cur == 'p') {
3783 NEXT;
3784 if (CUR != '{') {
3785 ERROR("Expecting '{'");
3786 return;
3787 }
3788 NEXT;
3789 xmlFAParseCharProp(ctxt);
3790 if (CUR != '}') {
3791 ERROR("Expecting '}'");
3792 return;
3793 }
3794 NEXT;
3795 } else if (cur == 'P') {
3796 NEXT;
3797 if (CUR != '{') {
3798 ERROR("Expecting '{'");
3799 return;
3800 }
3801 NEXT;
3802 xmlFAParseCharProp(ctxt);
3803 ctxt->atom->neg = 1;
3804 if (CUR != '}') {
3805 ERROR("Expecting '}'");
3806 return;
3807 }
3808 NEXT;
3809 } else if ((cur == 'n') || (cur == 'r') || (cur == 't') || (cur == '\\') ||
3810 (cur == '|') || (cur == '.') || (cur == '?') || (cur == '*') ||
3811 (cur == '+') || (cur == '(') || (cur == ')') || (cur == '{') ||
3812 (cur == '}') || (cur == 0x2D) || (cur == 0x5B) || (cur == 0x5D) ||
3813 (cur == 0x5E)) {
3814 if (ctxt->atom == NULL) {
3815 ctxt->atom = xmlRegNewAtom(ctxt, XML_REGEXP_CHARVAL);
3816 if (ctxt->atom != NULL)
3817 ctxt->atom->codepoint = cur;
3818 } else if (ctxt->atom->type == XML_REGEXP_RANGES) {
3819 xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,
3820 XML_REGEXP_CHARVAL, cur, cur, NULL);
3821 }
3822 NEXT;
3823 } else if ((cur == 's') || (cur == 'S') || (cur == 'i') || (cur == 'I') ||
3824 (cur == 'c') || (cur == 'C') || (cur == 'd') || (cur == 'D') ||
3825 (cur == 'w') || (cur == 'W')) {
Daniel Veillardb509f152002-04-17 16:28:10 +00003826 xmlRegAtomType type = XML_REGEXP_ANYSPACE;
Daniel Veillard4255d502002-04-16 15:50:10 +00003827
3828 switch (cur) {
3829 case 's':
3830 type = XML_REGEXP_ANYSPACE;
3831 break;
3832 case 'S':
3833 type = XML_REGEXP_NOTSPACE;
3834 break;
3835 case 'i':
3836 type = XML_REGEXP_INITNAME;
3837 break;
3838 case 'I':
3839 type = XML_REGEXP_NOTINITNAME;
3840 break;
3841 case 'c':
3842 type = XML_REGEXP_NAMECHAR;
3843 break;
3844 case 'C':
3845 type = XML_REGEXP_NOTNAMECHAR;
3846 break;
3847 case 'd':
3848 type = XML_REGEXP_DECIMAL;
3849 break;
3850 case 'D':
3851 type = XML_REGEXP_NOTDECIMAL;
3852 break;
3853 case 'w':
3854 type = XML_REGEXP_REALCHAR;
3855 break;
3856 case 'W':
3857 type = XML_REGEXP_NOTREALCHAR;
3858 break;
3859 }
3860 NEXT;
3861 if (ctxt->atom == NULL) {
3862 ctxt->atom = xmlRegNewAtom(ctxt, type);
3863 } else if (ctxt->atom->type == XML_REGEXP_RANGES) {
3864 xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,
3865 type, 0, 0, NULL);
3866 }
3867 }
3868}
3869
3870/**
3871 * xmlFAParseCharRef:
Daniel Veillard441bc322002-04-20 17:38:48 +00003872 * @ctxt: a regexp parser context
Daniel Veillard4255d502002-04-16 15:50:10 +00003873 *
3874 * [19] XmlCharRef ::= ( '&#' [0-9]+ ';' ) | (' &#x' [0-9a-fA-F]+ ';' )
3875 */
3876static int
3877xmlFAParseCharRef(xmlRegParserCtxtPtr ctxt) {
3878 int ret = 0, cur;
3879
3880 if ((CUR != '&') || (NXT(1) != '#'))
3881 return(-1);
3882 NEXT;
3883 NEXT;
3884 cur = CUR;
3885 if (cur == 'x') {
3886 NEXT;
3887 cur = CUR;
3888 if (((cur >= '0') && (cur <= '9')) ||
3889 ((cur >= 'a') && (cur <= 'f')) ||
3890 ((cur >= 'A') && (cur <= 'F'))) {
3891 while (((cur >= '0') && (cur <= '9')) ||
3892 ((cur >= 'A') && (cur <= 'F'))) {
3893 if ((cur >= '0') && (cur <= '9'))
3894 ret = ret * 16 + cur - '0';
3895 else if ((cur >= 'a') && (cur <= 'f'))
3896 ret = ret * 16 + 10 + (cur - 'a');
3897 else
3898 ret = ret * 16 + 10 + (cur - 'A');
3899 NEXT;
3900 cur = CUR;
3901 }
3902 } else {
3903 ERROR("Char ref: expecting [0-9A-F]");
3904 return(-1);
3905 }
3906 } else {
3907 if ((cur >= '0') && (cur <= '9')) {
3908 while ((cur >= '0') && (cur <= '9')) {
3909 ret = ret * 10 + cur - '0';
3910 NEXT;
3911 cur = CUR;
3912 }
3913 } else {
3914 ERROR("Char ref: expecting [0-9]");
3915 return(-1);
3916 }
3917 }
3918 if (cur != ';') {
3919 ERROR("Char ref: expecting ';'");
3920 return(-1);
3921 } else {
3922 NEXT;
3923 }
3924 return(ret);
3925}
3926
3927/**
3928 * xmlFAParseCharRange:
Daniel Veillard441bc322002-04-20 17:38:48 +00003929 * @ctxt: a regexp parser context
Daniel Veillard4255d502002-04-16 15:50:10 +00003930 *
3931 * [17] charRange ::= seRange | XmlCharRef | XmlCharIncDash
3932 * [18] seRange ::= charOrEsc '-' charOrEsc
3933 * [20] charOrEsc ::= XmlChar | SingleCharEsc
3934 * [21] XmlChar ::= [^\#x2D#x5B#x5D]
3935 * [22] XmlCharIncDash ::= [^\#x5B#x5D]
3936 */
3937static void
3938xmlFAParseCharRange(xmlRegParserCtxtPtr ctxt) {
William M. Brackdc99df92003-12-27 01:54:25 +00003939 int cur, len;
Daniel Veillard4255d502002-04-16 15:50:10 +00003940 int start = -1;
3941 int end = -1;
3942
3943 if ((CUR == '&') && (NXT(1) == '#')) {
3944 end = start = xmlFAParseCharRef(ctxt);
3945 xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,
3946 XML_REGEXP_CHARVAL, start, end, NULL);
3947 return;
3948 }
3949 cur = CUR;
3950 if (cur == '\\') {
3951 NEXT;
3952 cur = CUR;
3953 switch (cur) {
3954 case 'n': start = 0xA; break;
3955 case 'r': start = 0xD; break;
3956 case 't': start = 0x9; break;
3957 case '\\': case '|': case '.': case '-': case '^': case '?':
3958 case '*': case '+': case '{': case '}': case '(': case ')':
3959 case '[': case ']':
3960 start = cur; break;
3961 default:
3962 ERROR("Invalid escape value");
3963 return;
3964 }
3965 end = start;
William M. Brackdc99df92003-12-27 01:54:25 +00003966 len = 1;
Daniel Veillard4255d502002-04-16 15:50:10 +00003967 } else if ((cur != 0x5B) && (cur != 0x5D)) {
William M. Brackdc99df92003-12-27 01:54:25 +00003968 end = start = CUR_SCHAR(ctxt->cur, len);
Daniel Veillard4255d502002-04-16 15:50:10 +00003969 } else {
3970 ERROR("Expecting a char range");
3971 return;
3972 }
William M. Brackdc99df92003-12-27 01:54:25 +00003973 NEXTL(len);
Daniel Veillard4255d502002-04-16 15:50:10 +00003974 if (start == '-') {
3975 return;
3976 }
3977 cur = CUR;
William M. Brack10f1ef42004-03-20 14:51:25 +00003978 if ((cur != '-') || (NXT(1) == ']')) {
Daniel Veillard4255d502002-04-16 15:50:10 +00003979 xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,
3980 XML_REGEXP_CHARVAL, start, end, NULL);
3981 return;
3982 }
3983 NEXT;
3984 cur = CUR;
3985 if (cur == '\\') {
3986 NEXT;
3987 cur = CUR;
3988 switch (cur) {
3989 case 'n': end = 0xA; break;
3990 case 'r': end = 0xD; break;
3991 case 't': end = 0x9; break;
3992 case '\\': case '|': case '.': case '-': case '^': case '?':
3993 case '*': case '+': case '{': case '}': case '(': case ')':
3994 case '[': case ']':
3995 end = cur; break;
3996 default:
3997 ERROR("Invalid escape value");
3998 return;
3999 }
William M. Brackdc99df92003-12-27 01:54:25 +00004000 len = 1;
Daniel Veillard4255d502002-04-16 15:50:10 +00004001 } else if ((cur != 0x5B) && (cur != 0x5D)) {
William M. Brackdc99df92003-12-27 01:54:25 +00004002 end = CUR_SCHAR(ctxt->cur, len);
Daniel Veillard4255d502002-04-16 15:50:10 +00004003 } else {
4004 ERROR("Expecting the end of a char range");
4005 return;
4006 }
William M. Brackdc99df92003-12-27 01:54:25 +00004007 NEXTL(len);
Daniel Veillard4255d502002-04-16 15:50:10 +00004008 /* TODO check that the values are acceptable character ranges for XML */
4009 if (end < start) {
4010 ERROR("End of range is before start of range");
4011 } else {
4012 xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,
4013 XML_REGEXP_CHARVAL, start, end, NULL);
4014 }
4015 return;
4016}
4017
4018/**
4019 * xmlFAParsePosCharGroup:
Daniel Veillard441bc322002-04-20 17:38:48 +00004020 * @ctxt: a regexp parser context
Daniel Veillard4255d502002-04-16 15:50:10 +00004021 *
4022 * [14] posCharGroup ::= ( charRange | charClassEsc )+
4023 */
4024static void
4025xmlFAParsePosCharGroup(xmlRegParserCtxtPtr ctxt) {
4026 do {
4027 if ((CUR == '\\') || (CUR == '.')) {
4028 xmlFAParseCharClassEsc(ctxt);
4029 } else {
4030 xmlFAParseCharRange(ctxt);
4031 }
4032 } while ((CUR != ']') && (CUR != '^') && (CUR != '-') &&
4033 (ctxt->error == 0));
4034}
4035
4036/**
4037 * xmlFAParseCharGroup:
Daniel Veillard441bc322002-04-20 17:38:48 +00004038 * @ctxt: a regexp parser context
Daniel Veillard4255d502002-04-16 15:50:10 +00004039 *
4040 * [13] charGroup ::= posCharGroup | negCharGroup | charClassSub
4041 * [15] negCharGroup ::= '^' posCharGroup
4042 * [16] charClassSub ::= ( posCharGroup | negCharGroup ) '-' charClassExpr
4043 * [12] charClassExpr ::= '[' charGroup ']'
4044 */
4045static void
4046xmlFAParseCharGroup(xmlRegParserCtxtPtr ctxt) {
4047 int n = ctxt->neg;
4048 while ((CUR != ']') && (ctxt->error == 0)) {
4049 if (CUR == '^') {
4050 int neg = ctxt->neg;
4051
4052 NEXT;
4053 ctxt->neg = !ctxt->neg;
4054 xmlFAParsePosCharGroup(ctxt);
4055 ctxt->neg = neg;
William M. Brack10f1ef42004-03-20 14:51:25 +00004056 } else if ((CUR == '-') && (NXT(1) == '[')) {
Daniel Veillardf8b9de32003-11-24 14:27:26 +00004057 int neg = ctxt->neg;
Daniel Veillardf8b9de32003-11-24 14:27:26 +00004058 ctxt->neg = 2;
William M. Brack10f1ef42004-03-20 14:51:25 +00004059 NEXT; /* eat the '-' */
4060 NEXT; /* eat the '[' */
Daniel Veillard4255d502002-04-16 15:50:10 +00004061 xmlFAParseCharGroup(ctxt);
4062 if (CUR == ']') {
4063 NEXT;
4064 } else {
4065 ERROR("charClassExpr: ']' expected");
4066 break;
4067 }
Daniel Veillardf8b9de32003-11-24 14:27:26 +00004068 ctxt->neg = neg;
Daniel Veillard4255d502002-04-16 15:50:10 +00004069 break;
4070 } else if (CUR != ']') {
4071 xmlFAParsePosCharGroup(ctxt);
4072 }
4073 }
4074 ctxt->neg = n;
4075}
4076
4077/**
4078 * xmlFAParseCharClass:
Daniel Veillard441bc322002-04-20 17:38:48 +00004079 * @ctxt: a regexp parser context
Daniel Veillard4255d502002-04-16 15:50:10 +00004080 *
4081 * [11] charClass ::= charClassEsc | charClassExpr
4082 * [12] charClassExpr ::= '[' charGroup ']'
4083 */
4084static void
4085xmlFAParseCharClass(xmlRegParserCtxtPtr ctxt) {
4086 if (CUR == '[') {
4087 NEXT;
4088 ctxt->atom = xmlRegNewAtom(ctxt, XML_REGEXP_RANGES);
4089 if (ctxt->atom == NULL)
4090 return;
4091 xmlFAParseCharGroup(ctxt);
4092 if (CUR == ']') {
4093 NEXT;
4094 } else {
4095 ERROR("xmlFAParseCharClass: ']' expected");
4096 }
4097 } else {
4098 xmlFAParseCharClassEsc(ctxt);
4099 }
4100}
4101
4102/**
4103 * xmlFAParseQuantExact:
Daniel Veillard441bc322002-04-20 17:38:48 +00004104 * @ctxt: a regexp parser context
Daniel Veillard4255d502002-04-16 15:50:10 +00004105 *
4106 * [8] QuantExact ::= [0-9]+
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00004107 *
4108 * Returns 0 if success or -1 in case of error
Daniel Veillard4255d502002-04-16 15:50:10 +00004109 */
4110static int
4111xmlFAParseQuantExact(xmlRegParserCtxtPtr ctxt) {
4112 int ret = 0;
4113 int ok = 0;
4114
4115 while ((CUR >= '0') && (CUR <= '9')) {
4116 ret = ret * 10 + (CUR - '0');
4117 ok = 1;
4118 NEXT;
4119 }
4120 if (ok != 1) {
4121 return(-1);
4122 }
4123 return(ret);
4124}
4125
4126/**
4127 * xmlFAParseQuantifier:
Daniel Veillard441bc322002-04-20 17:38:48 +00004128 * @ctxt: a regexp parser context
Daniel Veillard4255d502002-04-16 15:50:10 +00004129 *
4130 * [4] quantifier ::= [?*+] | ( '{' quantity '}' )
4131 * [5] quantity ::= quantRange | quantMin | QuantExact
4132 * [6] quantRange ::= QuantExact ',' QuantExact
4133 * [7] quantMin ::= QuantExact ','
4134 * [8] QuantExact ::= [0-9]+
4135 */
4136static int
4137xmlFAParseQuantifier(xmlRegParserCtxtPtr ctxt) {
4138 int cur;
4139
4140 cur = CUR;
4141 if ((cur == '?') || (cur == '*') || (cur == '+')) {
4142 if (ctxt->atom != NULL) {
4143 if (cur == '?')
4144 ctxt->atom->quant = XML_REGEXP_QUANT_OPT;
4145 else if (cur == '*')
4146 ctxt->atom->quant = XML_REGEXP_QUANT_MULT;
4147 else if (cur == '+')
4148 ctxt->atom->quant = XML_REGEXP_QUANT_PLUS;
4149 }
4150 NEXT;
4151 return(1);
4152 }
4153 if (cur == '{') {
4154 int min = 0, max = 0;
4155
4156 NEXT;
4157 cur = xmlFAParseQuantExact(ctxt);
4158 if (cur >= 0)
4159 min = cur;
4160 if (CUR == ',') {
4161 NEXT;
Daniel Veillardebe48c62003-12-03 12:12:27 +00004162 if (CUR == '}')
4163 max = INT_MAX;
4164 else {
4165 cur = xmlFAParseQuantExact(ctxt);
4166 if (cur >= 0)
4167 max = cur;
4168 else {
4169 ERROR("Improper quantifier");
4170 }
4171 }
Daniel Veillard4255d502002-04-16 15:50:10 +00004172 }
4173 if (CUR == '}') {
4174 NEXT;
4175 } else {
4176 ERROR("Unterminated quantifier");
4177 }
4178 if (max == 0)
4179 max = min;
4180 if (ctxt->atom != NULL) {
4181 ctxt->atom->quant = XML_REGEXP_QUANT_RANGE;
4182 ctxt->atom->min = min;
4183 ctxt->atom->max = max;
4184 }
4185 return(1);
4186 }
4187 return(0);
4188}
4189
4190/**
4191 * xmlFAParseAtom:
Daniel Veillard441bc322002-04-20 17:38:48 +00004192 * @ctxt: a regexp parser context
Daniel Veillard4255d502002-04-16 15:50:10 +00004193 *
4194 * [9] atom ::= Char | charClass | ( '(' regExp ')' )
4195 */
4196static int
4197xmlFAParseAtom(xmlRegParserCtxtPtr ctxt) {
4198 int codepoint, len;
4199
4200 codepoint = xmlFAIsChar(ctxt);
4201 if (codepoint > 0) {
4202 ctxt->atom = xmlRegNewAtom(ctxt, XML_REGEXP_CHARVAL);
4203 if (ctxt->atom == NULL)
4204 return(-1);
4205 codepoint = CUR_SCHAR(ctxt->cur, len);
4206 ctxt->atom->codepoint = codepoint;
4207 NEXTL(len);
4208 return(1);
4209 } else if (CUR == '|') {
4210 return(0);
4211 } else if (CUR == 0) {
4212 return(0);
4213 } else if (CUR == ')') {
4214 return(0);
4215 } else if (CUR == '(') {
4216 xmlRegStatePtr start, oldend;
4217
4218 NEXT;
4219 xmlFAGenerateEpsilonTransition(ctxt, ctxt->state, NULL);
4220 start = ctxt->state;
4221 oldend = ctxt->end;
4222 ctxt->end = NULL;
4223 ctxt->atom = NULL;
4224 xmlFAParseRegExp(ctxt, 0);
4225 if (CUR == ')') {
4226 NEXT;
4227 } else {
4228 ERROR("xmlFAParseAtom: expecting ')'");
4229 }
4230 ctxt->atom = xmlRegNewAtom(ctxt, XML_REGEXP_SUBREG);
4231 if (ctxt->atom == NULL)
4232 return(-1);
4233 ctxt->atom->start = start;
4234 ctxt->atom->stop = ctxt->state;
4235 ctxt->end = oldend;
4236 return(1);
4237 } else if ((CUR == '[') || (CUR == '\\') || (CUR == '.')) {
4238 xmlFAParseCharClass(ctxt);
4239 return(1);
4240 }
4241 return(0);
4242}
4243
4244/**
4245 * xmlFAParsePiece:
Daniel Veillard441bc322002-04-20 17:38:48 +00004246 * @ctxt: a regexp parser context
Daniel Veillard4255d502002-04-16 15:50:10 +00004247 *
4248 * [3] piece ::= atom quantifier?
4249 */
4250static int
4251xmlFAParsePiece(xmlRegParserCtxtPtr ctxt) {
4252 int ret;
4253
4254 ctxt->atom = NULL;
4255 ret = xmlFAParseAtom(ctxt);
4256 if (ret == 0)
4257 return(0);
4258 if (ctxt->atom == NULL) {
4259 ERROR("internal: no atom generated");
4260 }
4261 xmlFAParseQuantifier(ctxt);
4262 return(1);
4263}
4264
4265/**
4266 * xmlFAParseBranch:
Daniel Veillard441bc322002-04-20 17:38:48 +00004267 * @ctxt: a regexp parser context
Daniel Veillard4255d502002-04-16 15:50:10 +00004268 *
4269 * [2] branch ::= piece*
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00004270 8
Daniel Veillard4255d502002-04-16 15:50:10 +00004271 */
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00004272static int
Daniel Veillard2cbf5962004-03-31 15:50:43 +00004273xmlFAParseBranch(xmlRegParserCtxtPtr ctxt) {
Daniel Veillard4255d502002-04-16 15:50:10 +00004274 xmlRegStatePtr previous;
Daniel Veillard4255d502002-04-16 15:50:10 +00004275 int ret;
4276
4277 previous = ctxt->state;
4278 ret = xmlFAParsePiece(ctxt);
4279 if (ret != 0) {
Daniel Veillard2cbf5962004-03-31 15:50:43 +00004280 if (xmlFAGenerateTransitions(ctxt, previous, NULL, ctxt->atom) < 0)
4281 return(-1);
4282 previous = ctxt->state;
Daniel Veillard4255d502002-04-16 15:50:10 +00004283 ctxt->atom = NULL;
4284 }
4285 while ((ret != 0) && (ctxt->error == 0)) {
4286 ret = xmlFAParsePiece(ctxt);
4287 if (ret != 0) {
Daniel Veillard2cbf5962004-03-31 15:50:43 +00004288 if (xmlFAGenerateTransitions(ctxt, previous, NULL,
4289 ctxt->atom) < 0)
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00004290 return(-1);
Daniel Veillard4255d502002-04-16 15:50:10 +00004291 previous = ctxt->state;
4292 ctxt->atom = NULL;
4293 }
4294 }
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00004295 return(0);
Daniel Veillard4255d502002-04-16 15:50:10 +00004296}
4297
4298/**
4299 * xmlFAParseRegExp:
Daniel Veillard441bc322002-04-20 17:38:48 +00004300 * @ctxt: a regexp parser context
William M. Brackddf71d62004-05-06 04:17:26 +00004301 * @top: is this the top-level expression ?
Daniel Veillard4255d502002-04-16 15:50:10 +00004302 *
4303 * [1] regExp ::= branch ( '|' branch )*
4304 */
4305static void
4306xmlFAParseRegExp(xmlRegParserCtxtPtr ctxt, int top) {
Daniel Veillardc7e3cc42004-09-28 12:33:52 +00004307 xmlRegStatePtr start, end;
Daniel Veillard4255d502002-04-16 15:50:10 +00004308
Daniel Veillard2cbf5962004-03-31 15:50:43 +00004309 /* if not top start should have been generated by an epsilon trans */
Daniel Veillard4255d502002-04-16 15:50:10 +00004310 start = ctxt->state;
Daniel Veillard2cbf5962004-03-31 15:50:43 +00004311 ctxt->end = NULL;
4312 xmlFAParseBranch(ctxt);
4313 if (top) {
4314#ifdef DEBUG_REGEXP_GRAPH
4315 printf("State %d is final\n", ctxt->state->no);
4316#endif
4317 ctxt->state->type = XML_REGEXP_FINAL_STATE;
4318 }
Daniel Veillard4255d502002-04-16 15:50:10 +00004319 if (CUR != '|') {
4320 ctxt->end = ctxt->state;
4321 return;
4322 }
4323 end = ctxt->state;
4324 while ((CUR == '|') && (ctxt->error == 0)) {
4325 NEXT;
4326 ctxt->state = start;
Daniel Veillard2cbf5962004-03-31 15:50:43 +00004327 ctxt->end = NULL;
4328 xmlFAParseBranch(ctxt);
4329 if (top) {
4330 ctxt->state->type = XML_REGEXP_FINAL_STATE;
4331#ifdef DEBUG_REGEXP_GRAPH
4332 printf("State %d is final\n", ctxt->state->no);
4333#endif
4334 } else {
4335 xmlFAGenerateEpsilonTransition(ctxt, ctxt->state, end);
4336 }
Daniel Veillard4255d502002-04-16 15:50:10 +00004337 }
Daniel Veillard2cbf5962004-03-31 15:50:43 +00004338 if (!top) {
4339 ctxt->state = end;
4340 ctxt->end = end;
4341 }
Daniel Veillard4255d502002-04-16 15:50:10 +00004342}
4343
4344/************************************************************************
4345 * *
4346 * The basic API *
4347 * *
4348 ************************************************************************/
4349
4350/**
4351 * xmlRegexpPrint:
4352 * @output: the file for the output debug
4353 * @regexp: the compiled regexp
4354 *
4355 * Print the content of the compiled regular expression
4356 */
4357void
4358xmlRegexpPrint(FILE *output, xmlRegexpPtr regexp) {
4359 int i;
4360
Daniel Veillarda82b1822004-11-08 16:24:57 +00004361 if (output == NULL)
4362 return;
Daniel Veillard4255d502002-04-16 15:50:10 +00004363 fprintf(output, " regexp: ");
4364 if (regexp == NULL) {
4365 fprintf(output, "NULL\n");
4366 return;
4367 }
4368 fprintf(output, "'%s' ", regexp->string);
4369 fprintf(output, "\n");
4370 fprintf(output, "%d atoms:\n", regexp->nbAtoms);
4371 for (i = 0;i < regexp->nbAtoms; i++) {
4372 fprintf(output, " %02d ", i);
4373 xmlRegPrintAtom(output, regexp->atoms[i]);
4374 }
4375 fprintf(output, "%d states:", regexp->nbStates);
4376 fprintf(output, "\n");
4377 for (i = 0;i < regexp->nbStates; i++) {
4378 xmlRegPrintState(output, regexp->states[i]);
4379 }
4380 fprintf(output, "%d counters:\n", regexp->nbCounters);
4381 for (i = 0;i < regexp->nbCounters; i++) {
4382 fprintf(output, " %d: min %d max %d\n", i, regexp->counters[i].min,
4383 regexp->counters[i].max);
4384 }
4385}
4386
4387/**
4388 * xmlRegexpCompile:
4389 * @regexp: a regular expression string
4390 *
4391 * Parses a regular expression conforming to XML Schemas Part 2 Datatype
William M. Brackddf71d62004-05-06 04:17:26 +00004392 * Appendix F and builds an automata suitable for testing strings against
Daniel Veillard4255d502002-04-16 15:50:10 +00004393 * that regular expression
4394 *
4395 * Returns the compiled expression or NULL in case of error
4396 */
4397xmlRegexpPtr
4398xmlRegexpCompile(const xmlChar *regexp) {
4399 xmlRegexpPtr ret;
4400 xmlRegParserCtxtPtr ctxt;
4401
4402 ctxt = xmlRegNewParserCtxt(regexp);
4403 if (ctxt == NULL)
4404 return(NULL);
4405
4406 /* initialize the parser */
4407 ctxt->end = NULL;
4408 ctxt->start = ctxt->state = xmlRegNewState(ctxt);
4409 xmlRegStatePush(ctxt, ctxt->start);
4410
4411 /* parse the expression building an automata */
4412 xmlFAParseRegExp(ctxt, 1);
4413 if (CUR != 0) {
4414 ERROR("xmlFAParseRegExp: extra characters");
4415 }
4416 ctxt->end = ctxt->state;
4417 ctxt->start->type = XML_REGEXP_START_STATE;
4418 ctxt->end->type = XML_REGEXP_FINAL_STATE;
4419
4420 /* remove the Epsilon except for counted transitions */
4421 xmlFAEliminateEpsilonTransitions(ctxt);
4422
4423
4424 if (ctxt->error != 0) {
4425 xmlRegFreeParserCtxt(ctxt);
4426 return(NULL);
4427 }
4428 ret = xmlRegEpxFromParse(ctxt);
4429 xmlRegFreeParserCtxt(ctxt);
4430 return(ret);
4431}
4432
4433/**
4434 * xmlRegexpExec:
4435 * @comp: the compiled regular expression
4436 * @content: the value to check against the regular expression
4437 *
William M. Brackddf71d62004-05-06 04:17:26 +00004438 * Check if the regular expression generates the value
Daniel Veillard4255d502002-04-16 15:50:10 +00004439 *
William M. Brackddf71d62004-05-06 04:17:26 +00004440 * Returns 1 if it matches, 0 if not and a negative value in case of error
Daniel Veillard4255d502002-04-16 15:50:10 +00004441 */
4442int
4443xmlRegexpExec(xmlRegexpPtr comp, const xmlChar *content) {
4444 if ((comp == NULL) || (content == NULL))
4445 return(-1);
4446 return(xmlFARegExec(comp, content));
4447}
4448
4449/**
Daniel Veillard23e73572002-09-19 19:56:43 +00004450 * xmlRegexpIsDeterminist:
4451 * @comp: the compiled regular expression
4452 *
4453 * Check if the regular expression is determinist
4454 *
William M. Brackddf71d62004-05-06 04:17:26 +00004455 * Returns 1 if it yes, 0 if not and a negative value in case of error
Daniel Veillard23e73572002-09-19 19:56:43 +00004456 */
4457int
4458xmlRegexpIsDeterminist(xmlRegexpPtr comp) {
4459 xmlAutomataPtr am;
4460 int ret;
4461
4462 if (comp == NULL)
4463 return(-1);
4464 if (comp->determinist != -1)
4465 return(comp->determinist);
4466
4467 am = xmlNewAutomata();
Daniel Veillardbd9afb52002-09-25 22:25:35 +00004468 if (am->states != NULL) {
4469 int i;
4470
4471 for (i = 0;i < am->nbStates;i++)
4472 xmlRegFreeState(am->states[i]);
4473 xmlFree(am->states);
4474 }
Daniel Veillard23e73572002-09-19 19:56:43 +00004475 am->nbAtoms = comp->nbAtoms;
4476 am->atoms = comp->atoms;
4477 am->nbStates = comp->nbStates;
4478 am->states = comp->states;
4479 am->determinist = -1;
4480 ret = xmlFAComputesDeterminism(am);
4481 am->atoms = NULL;
4482 am->states = NULL;
4483 xmlFreeAutomata(am);
4484 return(ret);
4485}
4486
4487/**
Daniel Veillard4255d502002-04-16 15:50:10 +00004488 * xmlRegFreeRegexp:
4489 * @regexp: the regexp
4490 *
4491 * Free a regexp
4492 */
4493void
4494xmlRegFreeRegexp(xmlRegexpPtr regexp) {
4495 int i;
4496 if (regexp == NULL)
4497 return;
4498
4499 if (regexp->string != NULL)
4500 xmlFree(regexp->string);
4501 if (regexp->states != NULL) {
4502 for (i = 0;i < regexp->nbStates;i++)
4503 xmlRegFreeState(regexp->states[i]);
4504 xmlFree(regexp->states);
4505 }
4506 if (regexp->atoms != NULL) {
4507 for (i = 0;i < regexp->nbAtoms;i++)
4508 xmlRegFreeAtom(regexp->atoms[i]);
4509 xmlFree(regexp->atoms);
4510 }
4511 if (regexp->counters != NULL)
4512 xmlFree(regexp->counters);
Daniel Veillard23e73572002-09-19 19:56:43 +00004513 if (regexp->compact != NULL)
4514 xmlFree(regexp->compact);
Daniel Veillard118aed72002-09-24 14:13:13 +00004515 if (regexp->transdata != NULL)
4516 xmlFree(regexp->transdata);
Daniel Veillard23e73572002-09-19 19:56:43 +00004517 if (regexp->stringMap != NULL) {
4518 for (i = 0; i < regexp->nbstrings;i++)
4519 xmlFree(regexp->stringMap[i]);
4520 xmlFree(regexp->stringMap);
4521 }
4522
Daniel Veillard4255d502002-04-16 15:50:10 +00004523 xmlFree(regexp);
4524}
4525
4526#ifdef LIBXML_AUTOMATA_ENABLED
4527/************************************************************************
4528 * *
4529 * The Automata interface *
4530 * *
4531 ************************************************************************/
4532
4533/**
4534 * xmlNewAutomata:
4535 *
4536 * Create a new automata
4537 *
4538 * Returns the new object or NULL in case of failure
4539 */
4540xmlAutomataPtr
4541xmlNewAutomata(void) {
4542 xmlAutomataPtr ctxt;
4543
4544 ctxt = xmlRegNewParserCtxt(NULL);
4545 if (ctxt == NULL)
4546 return(NULL);
4547
4548 /* initialize the parser */
4549 ctxt->end = NULL;
4550 ctxt->start = ctxt->state = xmlRegNewState(ctxt);
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00004551 if (ctxt->start == NULL) {
4552 xmlFreeAutomata(ctxt);
4553 return(NULL);
4554 }
4555 if (xmlRegStatePush(ctxt, ctxt->start) < 0) {
4556 xmlRegFreeState(ctxt->start);
4557 xmlFreeAutomata(ctxt);
4558 return(NULL);
4559 }
Daniel Veillard4255d502002-04-16 15:50:10 +00004560
4561 return(ctxt);
4562}
4563
4564/**
4565 * xmlFreeAutomata:
4566 * @am: an automata
4567 *
4568 * Free an automata
4569 */
4570void
4571xmlFreeAutomata(xmlAutomataPtr am) {
4572 if (am == NULL)
4573 return;
4574 xmlRegFreeParserCtxt(am);
4575}
4576
4577/**
4578 * xmlAutomataGetInitState:
4579 * @am: an automata
4580 *
Daniel Veillarda9b66d02002-12-11 14:23:49 +00004581 * Initial state lookup
4582 *
Daniel Veillard4255d502002-04-16 15:50:10 +00004583 * Returns the initial state of the automata
4584 */
4585xmlAutomataStatePtr
4586xmlAutomataGetInitState(xmlAutomataPtr am) {
4587 if (am == NULL)
4588 return(NULL);
4589 return(am->start);
4590}
4591
4592/**
4593 * xmlAutomataSetFinalState:
4594 * @am: an automata
4595 * @state: a state in this automata
4596 *
4597 * Makes that state a final state
4598 *
4599 * Returns 0 or -1 in case of error
4600 */
4601int
4602xmlAutomataSetFinalState(xmlAutomataPtr am, xmlAutomataStatePtr state) {
4603 if ((am == NULL) || (state == NULL))
4604 return(-1);
4605 state->type = XML_REGEXP_FINAL_STATE;
4606 return(0);
4607}
4608
4609/**
4610 * xmlAutomataNewTransition:
4611 * @am: an automata
4612 * @from: the starting point of the transition
4613 * @to: the target point of the transition or NULL
4614 * @token: the input string associated to that transition
4615 * @data: data passed to the callback function if the transition is activated
4616 *
William M. Brackddf71d62004-05-06 04:17:26 +00004617 * If @to is NULL, this creates first a new target state in the automata
Daniel Veillard4255d502002-04-16 15:50:10 +00004618 * and then adds a transition from the @from state to the target state
4619 * activated by the value of @token
4620 *
4621 * Returns the target state or NULL in case of error
4622 */
4623xmlAutomataStatePtr
4624xmlAutomataNewTransition(xmlAutomataPtr am, xmlAutomataStatePtr from,
4625 xmlAutomataStatePtr to, const xmlChar *token,
4626 void *data) {
4627 xmlRegAtomPtr atom;
4628
4629 if ((am == NULL) || (from == NULL) || (token == NULL))
4630 return(NULL);
4631 atom = xmlRegNewAtom(am, XML_REGEXP_STRING);
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00004632 if (atom == NULL)
4633 return(NULL);
Daniel Veillard4255d502002-04-16 15:50:10 +00004634 atom->data = data;
4635 if (atom == NULL)
4636 return(NULL);
4637 atom->valuep = xmlStrdup(token);
4638
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00004639 if (xmlFAGenerateTransitions(am, from, to, atom) < 0) {
4640 xmlRegFreeAtom(atom);
4641 return(NULL);
4642 }
Daniel Veillard4255d502002-04-16 15:50:10 +00004643 if (to == NULL)
4644 return(am->state);
4645 return(to);
4646}
4647
4648/**
Daniel Veillard52b48c72003-04-13 19:53:42 +00004649 * xmlAutomataNewTransition2:
4650 * @am: an automata
4651 * @from: the starting point of the transition
4652 * @to: the target point of the transition or NULL
4653 * @token: the first input string associated to that transition
4654 * @token2: the second input string associated to that transition
4655 * @data: data passed to the callback function if the transition is activated
4656 *
William M. Brackddf71d62004-05-06 04:17:26 +00004657 * If @to is NULL, this creates first a new target state in the automata
Daniel Veillard52b48c72003-04-13 19:53:42 +00004658 * and then adds a transition from the @from state to the target state
4659 * activated by the value of @token
4660 *
4661 * Returns the target state or NULL in case of error
4662 */
4663xmlAutomataStatePtr
4664xmlAutomataNewTransition2(xmlAutomataPtr am, xmlAutomataStatePtr from,
4665 xmlAutomataStatePtr to, const xmlChar *token,
4666 const xmlChar *token2, void *data) {
4667 xmlRegAtomPtr atom;
4668
4669 if ((am == NULL) || (from == NULL) || (token == NULL))
4670 return(NULL);
4671 atom = xmlRegNewAtom(am, XML_REGEXP_STRING);
4672 atom->data = data;
4673 if (atom == NULL)
4674 return(NULL);
4675 if ((token2 == NULL) || (*token2 == 0)) {
4676 atom->valuep = xmlStrdup(token);
4677 } else {
4678 int lenn, lenp;
4679 xmlChar *str;
4680
4681 lenn = strlen((char *) token2);
4682 lenp = strlen((char *) token);
4683
Daniel Veillard3c908dc2003-04-19 00:07:51 +00004684 str = (xmlChar *) xmlMallocAtomic(lenn + lenp + 2);
Daniel Veillard52b48c72003-04-13 19:53:42 +00004685 if (str == NULL) {
4686 xmlRegFreeAtom(atom);
4687 return(NULL);
4688 }
4689 memcpy(&str[0], token, lenp);
4690 str[lenp] = '|';
4691 memcpy(&str[lenp + 1], token2, lenn);
4692 str[lenn + lenp + 1] = 0;
4693
4694 atom->valuep = str;
4695 }
4696
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00004697 if (xmlFAGenerateTransitions(am, from, to, atom) < 0) {
4698 xmlRegFreeAtom(atom);
4699 return(NULL);
4700 }
Daniel Veillard52b48c72003-04-13 19:53:42 +00004701 if (to == NULL)
4702 return(am->state);
4703 return(to);
4704}
4705
4706/**
Kasimier T. Buchcik87876402004-09-29 13:29:03 +00004707 * xmlAutomataNewCountTrans2:
4708 * @am: an automata
4709 * @from: the starting point of the transition
4710 * @to: the target point of the transition or NULL
4711 * @token: the input string associated to that transition
4712 * @token2: the second input string associated to that transition
4713 * @min: the minimum successive occurences of token
4714 * @max: the maximum successive occurences of token
4715 * @data: data associated to the transition
4716 *
4717 * If @to is NULL, this creates first a new target state in the automata
4718 * and then adds a transition from the @from state to the target state
4719 * activated by a succession of input of value @token and @token2 and
4720 * whose number is between @min and @max
4721 *
4722 * Returns the target state or NULL in case of error
4723 */
4724xmlAutomataStatePtr
4725xmlAutomataNewCountTrans2(xmlAutomataPtr am, xmlAutomataStatePtr from,
4726 xmlAutomataStatePtr to, const xmlChar *token,
4727 const xmlChar *token2,
4728 int min, int max, void *data) {
4729 xmlRegAtomPtr atom;
4730 int counter;
4731
4732 if ((am == NULL) || (from == NULL) || (token == NULL))
4733 return(NULL);
4734 if (min < 0)
4735 return(NULL);
4736 if ((max < min) || (max < 1))
4737 return(NULL);
4738 atom = xmlRegNewAtom(am, XML_REGEXP_STRING);
4739 if (atom == NULL)
4740 return(NULL);
4741 if ((token2 == NULL) || (*token2 == 0)) {
4742 atom->valuep = xmlStrdup(token);
4743 } else {
4744 int lenn, lenp;
4745 xmlChar *str;
4746
4747 lenn = strlen((char *) token2);
4748 lenp = strlen((char *) token);
4749
4750 str = (xmlChar *) xmlMallocAtomic(lenn + lenp + 2);
4751 if (str == NULL) {
4752 xmlRegFreeAtom(atom);
4753 return(NULL);
4754 }
4755 memcpy(&str[0], token, lenp);
4756 str[lenp] = '|';
4757 memcpy(&str[lenp + 1], token2, lenn);
4758 str[lenn + lenp + 1] = 0;
4759
4760 atom->valuep = str;
4761 }
4762 atom->data = data;
4763 if (min == 0)
4764 atom->min = 1;
4765 else
4766 atom->min = min;
4767 atom->max = max;
4768
4769 /*
4770 * associate a counter to the transition.
4771 */
4772 counter = xmlRegGetCounter(am);
4773 am->counters[counter].min = min;
4774 am->counters[counter].max = max;
4775
4776 /* xmlFAGenerateTransitions(am, from, to, atom); */
4777 if (to == NULL) {
4778 to = xmlRegNewState(am);
4779 xmlRegStatePush(am, to);
4780 }
4781 xmlRegStateAddTrans(am, from, atom, to, counter, -1);
4782 xmlRegAtomPush(am, atom);
4783 am->state = to;
4784
4785 if (to == NULL)
4786 to = am->state;
4787 if (to == NULL)
4788 return(NULL);
4789 if (min == 0)
4790 xmlFAGenerateEpsilonTransition(am, from, to);
4791 return(to);
4792}
4793
4794/**
Daniel Veillard4255d502002-04-16 15:50:10 +00004795 * xmlAutomataNewCountTrans:
4796 * @am: an automata
4797 * @from: the starting point of the transition
4798 * @to: the target point of the transition or NULL
4799 * @token: the input string associated to that transition
4800 * @min: the minimum successive occurences of token
Daniel Veillarda9b66d02002-12-11 14:23:49 +00004801 * @max: the maximum successive occurences of token
4802 * @data: data associated to the transition
Daniel Veillard4255d502002-04-16 15:50:10 +00004803 *
William M. Brackddf71d62004-05-06 04:17:26 +00004804 * If @to is NULL, this creates first a new target state in the automata
Daniel Veillard4255d502002-04-16 15:50:10 +00004805 * and then adds a transition from the @from state to the target state
4806 * activated by a succession of input of value @token and whose number
4807 * is between @min and @max
4808 *
4809 * Returns the target state or NULL in case of error
4810 */
4811xmlAutomataStatePtr
4812xmlAutomataNewCountTrans(xmlAutomataPtr am, xmlAutomataStatePtr from,
4813 xmlAutomataStatePtr to, const xmlChar *token,
4814 int min, int max, void *data) {
4815 xmlRegAtomPtr atom;
Daniel Veillard0ddb21c2004-02-12 12:43:49 +00004816 int counter;
Daniel Veillard4255d502002-04-16 15:50:10 +00004817
4818 if ((am == NULL) || (from == NULL) || (token == NULL))
4819 return(NULL);
4820 if (min < 0)
4821 return(NULL);
4822 if ((max < min) || (max < 1))
4823 return(NULL);
4824 atom = xmlRegNewAtom(am, XML_REGEXP_STRING);
4825 if (atom == NULL)
4826 return(NULL);
4827 atom->valuep = xmlStrdup(token);
4828 atom->data = data;
4829 if (min == 0)
4830 atom->min = 1;
4831 else
4832 atom->min = min;
4833 atom->max = max;
4834
Daniel Veillard0ddb21c2004-02-12 12:43:49 +00004835 /*
4836 * associate a counter to the transition.
4837 */
4838 counter = xmlRegGetCounter(am);
4839 am->counters[counter].min = min;
4840 am->counters[counter].max = max;
4841
4842 /* xmlFAGenerateTransitions(am, from, to, atom); */
4843 if (to == NULL) {
4844 to = xmlRegNewState(am);
4845 xmlRegStatePush(am, to);
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00004846 }
Daniel Veillard0ddb21c2004-02-12 12:43:49 +00004847 xmlRegStateAddTrans(am, from, atom, to, counter, -1);
4848 xmlRegAtomPush(am, atom);
4849 am->state = to;
4850
Daniel Veillard4255d502002-04-16 15:50:10 +00004851 if (to == NULL)
4852 to = am->state;
4853 if (to == NULL)
4854 return(NULL);
4855 if (min == 0)
4856 xmlFAGenerateEpsilonTransition(am, from, to);
4857 return(to);
4858}
4859
4860/**
Kasimier T. Buchcik87876402004-09-29 13:29:03 +00004861 * xmlAutomataNewOnceTrans2:
4862 * @am: an automata
4863 * @from: the starting point of the transition
4864 * @to: the target point of the transition or NULL
4865 * @token: the input string associated to that transition
4866 * @token2: the second input string associated to that transition
4867 * @min: the minimum successive occurences of token
4868 * @max: the maximum successive occurences of token
4869 * @data: data associated to the transition
4870 *
4871 * If @to is NULL, this creates first a new target state in the automata
4872 * and then adds a transition from the @from state to the target state
4873 * activated by a succession of input of value @token and @token2 and whose
4874 * number is between @min and @max, moreover that transition can only be
4875 * crossed once.
4876 *
4877 * Returns the target state or NULL in case of error
4878 */
4879xmlAutomataStatePtr
4880xmlAutomataNewOnceTrans2(xmlAutomataPtr am, xmlAutomataStatePtr from,
4881 xmlAutomataStatePtr to, const xmlChar *token,
4882 const xmlChar *token2,
4883 int min, int max, void *data) {
4884 xmlRegAtomPtr atom;
4885 int counter;
4886
4887 if ((am == NULL) || (from == NULL) || (token == NULL))
4888 return(NULL);
4889 if (min < 1)
4890 return(NULL);
4891 if ((max < min) || (max < 1))
4892 return(NULL);
4893 atom = xmlRegNewAtom(am, XML_REGEXP_STRING);
4894 if (atom == NULL)
4895 return(NULL);
4896 if ((token2 == NULL) || (*token2 == 0)) {
4897 atom->valuep = xmlStrdup(token);
4898 } else {
4899 int lenn, lenp;
4900 xmlChar *str;
4901
4902 lenn = strlen((char *) token2);
4903 lenp = strlen((char *) token);
4904
4905 str = (xmlChar *) xmlMallocAtomic(lenn + lenp + 2);
4906 if (str == NULL) {
4907 xmlRegFreeAtom(atom);
4908 return(NULL);
4909 }
4910 memcpy(&str[0], token, lenp);
4911 str[lenp] = '|';
4912 memcpy(&str[lenp + 1], token2, lenn);
4913 str[lenn + lenp + 1] = 0;
4914
4915 atom->valuep = str;
4916 }
4917 atom->data = data;
4918 atom->quant = XML_REGEXP_QUANT_ONCEONLY;
4919 if (min == 0)
4920 atom->min = 1;
4921 else
4922 atom->min = min;
4923 atom->max = max;
4924 /*
4925 * associate a counter to the transition.
4926 */
4927 counter = xmlRegGetCounter(am);
4928 am->counters[counter].min = 1;
4929 am->counters[counter].max = 1;
4930
4931 /* xmlFAGenerateTransitions(am, from, to, atom); */
4932 if (to == NULL) {
4933 to = xmlRegNewState(am);
4934 xmlRegStatePush(am, to);
4935 }
4936 xmlRegStateAddTrans(am, from, atom, to, counter, -1);
4937 xmlRegAtomPush(am, atom);
4938 am->state = to;
4939 return(to);
4940}
4941
4942
4943
4944/**
Daniel Veillard7646b182002-04-20 06:41:40 +00004945 * xmlAutomataNewOnceTrans:
4946 * @am: an automata
4947 * @from: the starting point of the transition
4948 * @to: the target point of the transition or NULL
4949 * @token: the input string associated to that transition
4950 * @min: the minimum successive occurences of token
Daniel Veillarda9b66d02002-12-11 14:23:49 +00004951 * @max: the maximum successive occurences of token
4952 * @data: data associated to the transition
Daniel Veillard7646b182002-04-20 06:41:40 +00004953 *
William M. Brackddf71d62004-05-06 04:17:26 +00004954 * If @to is NULL, this creates first a new target state in the automata
Daniel Veillard7646b182002-04-20 06:41:40 +00004955 * and then adds a transition from the @from state to the target state
4956 * activated by a succession of input of value @token and whose number
William M. Brackddf71d62004-05-06 04:17:26 +00004957 * is between @min and @max, moreover that transition can only be crossed
Daniel Veillard7646b182002-04-20 06:41:40 +00004958 * once.
4959 *
4960 * Returns the target state or NULL in case of error
4961 */
4962xmlAutomataStatePtr
4963xmlAutomataNewOnceTrans(xmlAutomataPtr am, xmlAutomataStatePtr from,
4964 xmlAutomataStatePtr to, const xmlChar *token,
4965 int min, int max, void *data) {
4966 xmlRegAtomPtr atom;
4967 int counter;
4968
4969 if ((am == NULL) || (from == NULL) || (token == NULL))
4970 return(NULL);
4971 if (min < 1)
4972 return(NULL);
4973 if ((max < min) || (max < 1))
4974 return(NULL);
4975 atom = xmlRegNewAtom(am, XML_REGEXP_STRING);
4976 if (atom == NULL)
4977 return(NULL);
4978 atom->valuep = xmlStrdup(token);
4979 atom->data = data;
4980 atom->quant = XML_REGEXP_QUANT_ONCEONLY;
4981 if (min == 0)
4982 atom->min = 1;
4983 else
4984 atom->min = min;
4985 atom->max = max;
4986 /*
4987 * associate a counter to the transition.
4988 */
4989 counter = xmlRegGetCounter(am);
4990 am->counters[counter].min = 1;
4991 am->counters[counter].max = 1;
4992
4993 /* xmlFAGenerateTransitions(am, from, to, atom); */
4994 if (to == NULL) {
4995 to = xmlRegNewState(am);
4996 xmlRegStatePush(am, to);
4997 }
4998 xmlRegStateAddTrans(am, from, atom, to, counter, -1);
4999 xmlRegAtomPush(am, atom);
5000 am->state = to;
Daniel Veillard7646b182002-04-20 06:41:40 +00005001 return(to);
5002}
5003
5004/**
Daniel Veillard4255d502002-04-16 15:50:10 +00005005 * xmlAutomataNewState:
5006 * @am: an automata
5007 *
5008 * Create a new disconnected state in the automata
5009 *
5010 * Returns the new state or NULL in case of error
5011 */
5012xmlAutomataStatePtr
5013xmlAutomataNewState(xmlAutomataPtr am) {
5014 xmlAutomataStatePtr to;
5015
5016 if (am == NULL)
5017 return(NULL);
5018 to = xmlRegNewState(am);
5019 xmlRegStatePush(am, to);
5020 return(to);
5021}
5022
5023/**
Daniel Veillarda9b66d02002-12-11 14:23:49 +00005024 * xmlAutomataNewEpsilon:
Daniel Veillard4255d502002-04-16 15:50:10 +00005025 * @am: an automata
5026 * @from: the starting point of the transition
5027 * @to: the target point of the transition or NULL
5028 *
William M. Brackddf71d62004-05-06 04:17:26 +00005029 * If @to is NULL, this creates first a new target state in the automata
5030 * and then adds an epsilon transition from the @from state to the
Daniel Veillard4255d502002-04-16 15:50:10 +00005031 * target state
5032 *
5033 * Returns the target state or NULL in case of error
5034 */
5035xmlAutomataStatePtr
5036xmlAutomataNewEpsilon(xmlAutomataPtr am, xmlAutomataStatePtr from,
5037 xmlAutomataStatePtr to) {
5038 if ((am == NULL) || (from == NULL))
5039 return(NULL);
5040 xmlFAGenerateEpsilonTransition(am, from, to);
5041 if (to == NULL)
5042 return(am->state);
5043 return(to);
5044}
5045
Daniel Veillardb509f152002-04-17 16:28:10 +00005046/**
Daniel Veillard7646b182002-04-20 06:41:40 +00005047 * xmlAutomataNewAllTrans:
5048 * @am: an automata
5049 * @from: the starting point of the transition
5050 * @to: the target point of the transition or NULL
Daniel Veillarda9b66d02002-12-11 14:23:49 +00005051 * @lax: allow to transition if not all all transitions have been activated
Daniel Veillard7646b182002-04-20 06:41:40 +00005052 *
William M. Brackddf71d62004-05-06 04:17:26 +00005053 * If @to is NULL, this creates first a new target state in the automata
Daniel Veillard7646b182002-04-20 06:41:40 +00005054 * and then adds a an ALL transition from the @from state to the
5055 * target state. That transition is an epsilon transition allowed only when
5056 * all transitions from the @from node have been activated.
5057 *
5058 * Returns the target state or NULL in case of error
5059 */
5060xmlAutomataStatePtr
5061xmlAutomataNewAllTrans(xmlAutomataPtr am, xmlAutomataStatePtr from,
Daniel Veillard441bc322002-04-20 17:38:48 +00005062 xmlAutomataStatePtr to, int lax) {
Daniel Veillard7646b182002-04-20 06:41:40 +00005063 if ((am == NULL) || (from == NULL))
5064 return(NULL);
Daniel Veillard441bc322002-04-20 17:38:48 +00005065 xmlFAGenerateAllTransition(am, from, to, lax);
Daniel Veillard7646b182002-04-20 06:41:40 +00005066 if (to == NULL)
5067 return(am->state);
5068 return(to);
5069}
5070
5071/**
Daniel Veillardb509f152002-04-17 16:28:10 +00005072 * xmlAutomataNewCounter:
5073 * @am: an automata
5074 * @min: the minimal value on the counter
5075 * @max: the maximal value on the counter
5076 *
5077 * Create a new counter
5078 *
5079 * Returns the counter number or -1 in case of error
5080 */
5081int
5082xmlAutomataNewCounter(xmlAutomataPtr am, int min, int max) {
5083 int ret;
5084
5085 if (am == NULL)
5086 return(-1);
5087
5088 ret = xmlRegGetCounter(am);
5089 if (ret < 0)
5090 return(-1);
5091 am->counters[ret].min = min;
5092 am->counters[ret].max = max;
5093 return(ret);
5094}
5095
5096/**
5097 * xmlAutomataNewCountedTrans:
5098 * @am: an automata
5099 * @from: the starting point of the transition
5100 * @to: the target point of the transition or NULL
5101 * @counter: the counter associated to that transition
5102 *
William M. Brackddf71d62004-05-06 04:17:26 +00005103 * If @to is NULL, this creates first a new target state in the automata
Daniel Veillardb509f152002-04-17 16:28:10 +00005104 * and then adds an epsilon transition from the @from state to the target state
5105 * which will increment the counter provided
5106 *
5107 * Returns the target state or NULL in case of error
5108 */
5109xmlAutomataStatePtr
5110xmlAutomataNewCountedTrans(xmlAutomataPtr am, xmlAutomataStatePtr from,
5111 xmlAutomataStatePtr to, int counter) {
5112 if ((am == NULL) || (from == NULL) || (counter < 0))
5113 return(NULL);
5114 xmlFAGenerateCountedEpsilonTransition(am, from, to, counter);
5115 if (to == NULL)
5116 return(am->state);
5117 return(to);
5118}
5119
5120/**
5121 * xmlAutomataNewCounterTrans:
5122 * @am: an automata
5123 * @from: the starting point of the transition
5124 * @to: the target point of the transition or NULL
5125 * @counter: the counter associated to that transition
5126 *
William M. Brackddf71d62004-05-06 04:17:26 +00005127 * If @to is NULL, this creates first a new target state in the automata
Daniel Veillardb509f152002-04-17 16:28:10 +00005128 * and then adds an epsilon transition from the @from state to the target state
5129 * which will be allowed only if the counter is within the right range.
5130 *
5131 * Returns the target state or NULL in case of error
5132 */
5133xmlAutomataStatePtr
5134xmlAutomataNewCounterTrans(xmlAutomataPtr am, xmlAutomataStatePtr from,
5135 xmlAutomataStatePtr to, int counter) {
5136 if ((am == NULL) || (from == NULL) || (counter < 0))
5137 return(NULL);
5138 xmlFAGenerateCountedTransition(am, from, to, counter);
5139 if (to == NULL)
5140 return(am->state);
5141 return(to);
5142}
Daniel Veillard4255d502002-04-16 15:50:10 +00005143
5144/**
5145 * xmlAutomataCompile:
5146 * @am: an automata
5147 *
5148 * Compile the automata into a Reg Exp ready for being executed.
5149 * The automata should be free after this point.
5150 *
5151 * Returns the compiled regexp or NULL in case of error
5152 */
5153xmlRegexpPtr
5154xmlAutomataCompile(xmlAutomataPtr am) {
5155 xmlRegexpPtr ret;
5156
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00005157 if ((am == NULL) || (am->error != 0)) return(NULL);
Daniel Veillard4255d502002-04-16 15:50:10 +00005158 xmlFAEliminateEpsilonTransitions(am);
Daniel Veillard23e73572002-09-19 19:56:43 +00005159 /* xmlFAComputesDeterminism(am); */
Daniel Veillard4255d502002-04-16 15:50:10 +00005160 ret = xmlRegEpxFromParse(am);
5161
5162 return(ret);
5163}
Daniel Veillarde19fc232002-04-22 16:01:24 +00005164
5165/**
5166 * xmlAutomataIsDeterminist:
5167 * @am: an automata
5168 *
5169 * Checks if an automata is determinist.
5170 *
5171 * Returns 1 if true, 0 if not, and -1 in case of error
5172 */
5173int
5174xmlAutomataIsDeterminist(xmlAutomataPtr am) {
5175 int ret;
5176
5177 if (am == NULL)
5178 return(-1);
5179
5180 ret = xmlFAComputesDeterminism(am);
5181 return(ret);
5182}
Daniel Veillard4255d502002-04-16 15:50:10 +00005183#endif /* LIBXML_AUTOMATA_ENABLED */
5184#endif /* LIBXML_REGEXP_ENABLED */