blob: 1706c7403984b3ec42b396b34672a9b78f805e9a [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
6 * XML related specifications thise includes:
7 * - 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
22#include <stdio.h>
23#include <string.h>
Daniel Veillardebe48c62003-12-03 12:12:27 +000024#ifdef HAVE_LIMITS_H
25#include <limits.h>
26#endif
27
Daniel Veillard4255d502002-04-16 15:50:10 +000028#include <libxml/tree.h>
29#include <libxml/parserInternals.h>
30#include <libxml/xmlregexp.h>
31#include <libxml/xmlautomata.h>
32#include <libxml/xmlunicode.h>
33
Daniel Veillardebe48c62003-12-03 12:12:27 +000034#ifndef INT_MAX
35#define INT_MAX 123456789 /* easy to flag and big enough for our needs */
36#endif
37
Daniel Veillard4255d502002-04-16 15:50:10 +000038/* #define DEBUG_REGEXP_GRAPH */
39/* #define DEBUG_REGEXP_EXEC */
40/* #define DEBUG_PUSH */
Daniel Veillard23e73572002-09-19 19:56:43 +000041/* #define DEBUG_COMPACTION */
Daniel Veillard4255d502002-04-16 15:50:10 +000042
Daniel Veillardff46a042003-10-08 08:53:17 +000043#define ERROR(str) \
44 ctxt->error = XML_REGEXP_COMPILE_ERROR; \
45 xmlRegexpErrCompile(ctxt, str);
Daniel Veillard4255d502002-04-16 15:50:10 +000046#define NEXT ctxt->cur++
47#define CUR (*(ctxt->cur))
48#define NXT(index) (ctxt->cur[index])
49
50#define CUR_SCHAR(s, l) xmlStringCurrentChar(NULL, s, &l)
51#define NEXTL(l) ctxt->cur += l;
52
Daniel Veillarde19fc232002-04-22 16:01:24 +000053/**
54 * TODO:
55 *
56 * macro to flag unimplemented blocks
57 */
58#define TODO \
59 xmlGenericError(xmlGenericErrorContext, \
60 "Unimplemented block at %s:%d\n", \
61 __FILE__, __LINE__);
62
Daniel Veillard4255d502002-04-16 15:50:10 +000063/************************************************************************
64 * *
65 * Datatypes and structures *
66 * *
67 ************************************************************************/
68
69typedef enum {
70 XML_REGEXP_EPSILON = 1,
71 XML_REGEXP_CHARVAL,
72 XML_REGEXP_RANGES,
73 XML_REGEXP_SUBREG,
74 XML_REGEXP_STRING,
75 XML_REGEXP_ANYCHAR, /* . */
76 XML_REGEXP_ANYSPACE, /* \s */
77 XML_REGEXP_NOTSPACE, /* \S */
78 XML_REGEXP_INITNAME, /* \l */
79 XML_REGEXP_NOTINITNAME, /* \l */
80 XML_REGEXP_NAMECHAR, /* \c */
81 XML_REGEXP_NOTNAMECHAR, /* \C */
82 XML_REGEXP_DECIMAL, /* \d */
83 XML_REGEXP_NOTDECIMAL, /* \d */
84 XML_REGEXP_REALCHAR, /* \w */
85 XML_REGEXP_NOTREALCHAR, /* \w */
86 XML_REGEXP_LETTER,
87 XML_REGEXP_LETTER_UPPERCASE,
88 XML_REGEXP_LETTER_LOWERCASE,
89 XML_REGEXP_LETTER_TITLECASE,
90 XML_REGEXP_LETTER_MODIFIER,
91 XML_REGEXP_LETTER_OTHERS,
92 XML_REGEXP_MARK,
93 XML_REGEXP_MARK_NONSPACING,
94 XML_REGEXP_MARK_SPACECOMBINING,
95 XML_REGEXP_MARK_ENCLOSING,
96 XML_REGEXP_NUMBER,
97 XML_REGEXP_NUMBER_DECIMAL,
98 XML_REGEXP_NUMBER_LETTER,
99 XML_REGEXP_NUMBER_OTHERS,
100 XML_REGEXP_PUNCT,
101 XML_REGEXP_PUNCT_CONNECTOR,
102 XML_REGEXP_PUNCT_DASH,
103 XML_REGEXP_PUNCT_OPEN,
104 XML_REGEXP_PUNCT_CLOSE,
105 XML_REGEXP_PUNCT_INITQUOTE,
106 XML_REGEXP_PUNCT_FINQUOTE,
107 XML_REGEXP_PUNCT_OTHERS,
108 XML_REGEXP_SEPAR,
109 XML_REGEXP_SEPAR_SPACE,
110 XML_REGEXP_SEPAR_LINE,
111 XML_REGEXP_SEPAR_PARA,
112 XML_REGEXP_SYMBOL,
113 XML_REGEXP_SYMBOL_MATH,
114 XML_REGEXP_SYMBOL_CURRENCY,
115 XML_REGEXP_SYMBOL_MODIFIER,
116 XML_REGEXP_SYMBOL_OTHERS,
117 XML_REGEXP_OTHER,
118 XML_REGEXP_OTHER_CONTROL,
119 XML_REGEXP_OTHER_FORMAT,
120 XML_REGEXP_OTHER_PRIVATE,
121 XML_REGEXP_OTHER_NA,
122 XML_REGEXP_BLOCK_NAME
123} xmlRegAtomType;
124
125typedef enum {
126 XML_REGEXP_QUANT_EPSILON = 1,
127 XML_REGEXP_QUANT_ONCE,
128 XML_REGEXP_QUANT_OPT,
129 XML_REGEXP_QUANT_MULT,
130 XML_REGEXP_QUANT_PLUS,
Daniel Veillard7646b182002-04-20 06:41:40 +0000131 XML_REGEXP_QUANT_ONCEONLY,
132 XML_REGEXP_QUANT_ALL,
Daniel Veillard4255d502002-04-16 15:50:10 +0000133 XML_REGEXP_QUANT_RANGE
134} xmlRegQuantType;
135
136typedef enum {
137 XML_REGEXP_START_STATE = 1,
138 XML_REGEXP_FINAL_STATE,
139 XML_REGEXP_TRANS_STATE
140} xmlRegStateType;
141
142typedef enum {
143 XML_REGEXP_MARK_NORMAL = 0,
144 XML_REGEXP_MARK_START,
145 XML_REGEXP_MARK_VISITED
146} xmlRegMarkedType;
147
148typedef struct _xmlRegRange xmlRegRange;
149typedef xmlRegRange *xmlRegRangePtr;
150
151struct _xmlRegRange {
Daniel Veillardf8b9de32003-11-24 14:27:26 +0000152 int neg; /* 0 normal, 1 not, 2 exclude */
Daniel Veillard4255d502002-04-16 15:50:10 +0000153 xmlRegAtomType type;
154 int start;
155 int end;
156 xmlChar *blockName;
157};
158
159typedef struct _xmlRegAtom xmlRegAtom;
160typedef xmlRegAtom *xmlRegAtomPtr;
161
162typedef struct _xmlAutomataState xmlRegState;
163typedef xmlRegState *xmlRegStatePtr;
164
165struct _xmlRegAtom {
166 int no;
167 xmlRegAtomType type;
168 xmlRegQuantType quant;
169 int min;
170 int max;
171
172 void *valuep;
Daniel Veillarda646cfd2002-09-17 21:50:03 +0000173 void *valuep2;
Daniel Veillard4255d502002-04-16 15:50:10 +0000174 int neg;
175 int codepoint;
176 xmlRegStatePtr start;
177 xmlRegStatePtr stop;
178 int maxRanges;
179 int nbRanges;
180 xmlRegRangePtr *ranges;
181 void *data;
182};
183
184typedef struct _xmlRegCounter xmlRegCounter;
185typedef xmlRegCounter *xmlRegCounterPtr;
186
187struct _xmlRegCounter {
188 int min;
189 int max;
190};
191
192typedef struct _xmlRegTrans xmlRegTrans;
193typedef xmlRegTrans *xmlRegTransPtr;
194
195struct _xmlRegTrans {
196 xmlRegAtomPtr atom;
197 int to;
198 int counter;
199 int count;
200};
201
202struct _xmlAutomataState {
203 xmlRegStateType type;
204 xmlRegMarkedType mark;
Daniel Veillard23e73572002-09-19 19:56:43 +0000205 xmlRegMarkedType reached;
Daniel Veillard4255d502002-04-16 15:50:10 +0000206 int no;
207
208 int maxTrans;
209 int nbTrans;
210 xmlRegTrans *trans;
211};
212
213typedef struct _xmlAutomata xmlRegParserCtxt;
214typedef xmlRegParserCtxt *xmlRegParserCtxtPtr;
215
216struct _xmlAutomata {
217 xmlChar *string;
218 xmlChar *cur;
219
220 int error;
221 int neg;
222
223 xmlRegStatePtr start;
224 xmlRegStatePtr end;
225 xmlRegStatePtr state;
226
227 xmlRegAtomPtr atom;
228
229 int maxAtoms;
230 int nbAtoms;
231 xmlRegAtomPtr *atoms;
232
233 int maxStates;
234 int nbStates;
235 xmlRegStatePtr *states;
236
237 int maxCounters;
238 int nbCounters;
239 xmlRegCounter *counters;
Daniel Veillarde19fc232002-04-22 16:01:24 +0000240
241 int determinist;
Daniel Veillard4255d502002-04-16 15:50:10 +0000242};
243
244struct _xmlRegexp {
245 xmlChar *string;
246 int nbStates;
247 xmlRegStatePtr *states;
248 int nbAtoms;
249 xmlRegAtomPtr *atoms;
250 int nbCounters;
251 xmlRegCounter *counters;
Daniel Veillarde19fc232002-04-22 16:01:24 +0000252 int determinist;
Daniel Veillard23e73572002-09-19 19:56:43 +0000253 /*
254 * That's the compact form for determinists automatas
255 */
256 int nbstates;
257 int *compact;
Daniel Veillard118aed72002-09-24 14:13:13 +0000258 void **transdata;
Daniel Veillard23e73572002-09-19 19:56:43 +0000259 int nbstrings;
260 xmlChar **stringMap;
Daniel Veillard4255d502002-04-16 15:50:10 +0000261};
262
263typedef struct _xmlRegExecRollback xmlRegExecRollback;
264typedef xmlRegExecRollback *xmlRegExecRollbackPtr;
265
266struct _xmlRegExecRollback {
267 xmlRegStatePtr state;/* the current state */
268 int index; /* the index in the input stack */
269 int nextbranch; /* the next transition to explore in that state */
270 int *counts; /* save the automate state if it has some */
271};
272
273typedef struct _xmlRegInputToken xmlRegInputToken;
274typedef xmlRegInputToken *xmlRegInputTokenPtr;
275
276struct _xmlRegInputToken {
277 xmlChar *value;
278 void *data;
279};
280
281struct _xmlRegExecCtxt {
282 int status; /* execution status != 0 indicate an error */
283 int determinist; /* did we found an inderterministic behaviour */
284 xmlRegexpPtr comp; /* the compiled regexp */
285 xmlRegExecCallbacks callback;
286 void *data;
287
288 xmlRegStatePtr state;/* the current state */
289 int transno; /* the current transition on that state */
290 int transcount; /* the number of char in char counted transitions */
291
292 /*
293 * A stack of rollback states
294 */
295 int maxRollbacks;
296 int nbRollbacks;
297 xmlRegExecRollback *rollbacks;
298
299 /*
300 * The state of the automata if any
301 */
302 int *counts;
303
304 /*
305 * The input stack
306 */
307 int inputStackMax;
308 int inputStackNr;
309 int index;
310 int *charStack;
311 const xmlChar *inputString; /* when operating on characters */
312 xmlRegInputTokenPtr inputStack;/* when operating on strings */
313
314};
315
Daniel Veillard441bc322002-04-20 17:38:48 +0000316#define REGEXP_ALL_COUNTER 0x123456
317#define REGEXP_ALL_LAX_COUNTER 0x123457
Daniel Veillard7646b182002-04-20 06:41:40 +0000318
Daniel Veillard4255d502002-04-16 15:50:10 +0000319static void xmlFAParseRegExp(xmlRegParserCtxtPtr ctxt, int top);
Daniel Veillard23e73572002-09-19 19:56:43 +0000320static void xmlRegFreeState(xmlRegStatePtr state);
321static void xmlRegFreeAtom(xmlRegAtomPtr atom);
Daniel Veillard4255d502002-04-16 15:50:10 +0000322
323/************************************************************************
Daniel Veillardff46a042003-10-08 08:53:17 +0000324 * *
325 * Regexp memory error handler *
326 * *
327 ************************************************************************/
328/**
329 * xmlRegexpErrMemory:
330 * @extra: extra informations
331 *
332 * Handle an out of memory condition
333 */
334static void
335xmlRegexpErrMemory(xmlRegParserCtxtPtr ctxt, const char *extra)
336{
337 const char *regexp = NULL;
338 if (ctxt != NULL) {
339 regexp = (const char *) ctxt->string;
340 ctxt->error = XML_ERR_NO_MEMORY;
341 }
Daniel Veillard659e71e2003-10-10 14:10:40 +0000342 __xmlRaiseError(NULL, NULL, NULL, NULL, NULL, XML_FROM_REGEXP,
Daniel Veillardff46a042003-10-08 08:53:17 +0000343 XML_ERR_NO_MEMORY, XML_ERR_FATAL, NULL, 0, extra,
344 regexp, NULL, 0, 0,
345 "Memory allocation failed : %s\n", extra);
346}
347
348/**
349 * xmlRegexpErrCompile:
350 * @extra: extra informations
351 *
352 * Handle an compilation failure
353 */
354static void
355xmlRegexpErrCompile(xmlRegParserCtxtPtr ctxt, const char *extra)
356{
357 const char *regexp = NULL;
358 int idx = 0;
359
360 if (ctxt != NULL) {
361 regexp = (const char *) ctxt->string;
362 idx = ctxt->cur - ctxt->string;
363 ctxt->error = XML_REGEXP_COMPILE_ERROR;
364 }
Daniel Veillard659e71e2003-10-10 14:10:40 +0000365 __xmlRaiseError(NULL, NULL, NULL, NULL, NULL, XML_FROM_REGEXP,
Daniel Veillardff46a042003-10-08 08:53:17 +0000366 XML_REGEXP_COMPILE_ERROR, XML_ERR_FATAL, NULL, 0, extra,
367 regexp, NULL, idx, 0,
368 "failed to compile: %s\n", extra);
369}
370
371/************************************************************************
Daniel Veillard4255d502002-04-16 15:50:10 +0000372 * *
373 * Allocation/Deallocation *
374 * *
375 ************************************************************************/
376
Daniel Veillard23e73572002-09-19 19:56:43 +0000377static int xmlFAComputesDeterminism(xmlRegParserCtxtPtr ctxt);
Daniel Veillard4255d502002-04-16 15:50:10 +0000378/**
379 * xmlRegEpxFromParse:
380 * @ctxt: the parser context used to build it
381 *
382 * Allocate a new regexp and fill it with the reult from the parser
383 *
384 * Returns the new regexp or NULL in case of error
385 */
386static xmlRegexpPtr
387xmlRegEpxFromParse(xmlRegParserCtxtPtr ctxt) {
388 xmlRegexpPtr ret;
389
390 ret = (xmlRegexpPtr) xmlMalloc(sizeof(xmlRegexp));
Daniel Veillarda76fe5c2003-04-24 16:06:47 +0000391 if (ret == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +0000392 xmlRegexpErrMemory(ctxt, "compiling regexp");
Daniel Veillard4255d502002-04-16 15:50:10 +0000393 return(NULL);
Daniel Veillarda76fe5c2003-04-24 16:06:47 +0000394 }
Daniel Veillard4255d502002-04-16 15:50:10 +0000395 memset(ret, 0, sizeof(xmlRegexp));
396 ret->string = ctxt->string;
Daniel Veillard4255d502002-04-16 15:50:10 +0000397 ret->nbStates = ctxt->nbStates;
Daniel Veillard4255d502002-04-16 15:50:10 +0000398 ret->states = ctxt->states;
Daniel Veillard4255d502002-04-16 15:50:10 +0000399 ret->nbAtoms = ctxt->nbAtoms;
Daniel Veillard4255d502002-04-16 15:50:10 +0000400 ret->atoms = ctxt->atoms;
Daniel Veillard4255d502002-04-16 15:50:10 +0000401 ret->nbCounters = ctxt->nbCounters;
Daniel Veillard4255d502002-04-16 15:50:10 +0000402 ret->counters = ctxt->counters;
Daniel Veillarde19fc232002-04-22 16:01:24 +0000403 ret->determinist = ctxt->determinist;
Daniel Veillard23e73572002-09-19 19:56:43 +0000404
405 if ((ret->determinist != 0) &&
406 (ret->nbCounters == 0) &&
Daniel Veillard118aed72002-09-24 14:13:13 +0000407 (ret->atoms != NULL) &&
Daniel Veillard23e73572002-09-19 19:56:43 +0000408 (ret->atoms[0] != NULL) &&
409 (ret->atoms[0]->type == XML_REGEXP_STRING)) {
410 int i, j, nbstates = 0, nbatoms = 0;
411 int *stateRemap;
412 int *stringRemap;
413 int *transitions;
Daniel Veillard118aed72002-09-24 14:13:13 +0000414 void **transdata;
Daniel Veillard23e73572002-09-19 19:56:43 +0000415 xmlChar **stringMap;
416 xmlChar *value;
417
418 /*
419 * Switch to a compact representation
420 * 1/ counting the effective number of states left
421 * 2/ conting the unique number of atoms, and check that
422 * they are all of the string type
423 * 3/ build a table state x atom for the transitions
424 */
425
426 stateRemap = xmlMalloc(ret->nbStates * sizeof(int));
Daniel Veillarda76fe5c2003-04-24 16:06:47 +0000427 if (stateRemap == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +0000428 xmlRegexpErrMemory(ctxt, "compiling regexp");
Daniel Veillarda76fe5c2003-04-24 16:06:47 +0000429 xmlFree(ret);
430 return(NULL);
431 }
Daniel Veillard23e73572002-09-19 19:56:43 +0000432 for (i = 0;i < ret->nbStates;i++) {
433 if (ret->states[i] != NULL) {
434 stateRemap[i] = nbstates;
435 nbstates++;
436 } else {
437 stateRemap[i] = -1;
438 }
439 }
440#ifdef DEBUG_COMPACTION
441 printf("Final: %d states\n", nbstates);
442#endif
443 stringMap = xmlMalloc(ret->nbAtoms * sizeof(char *));
Daniel Veillarda76fe5c2003-04-24 16:06:47 +0000444 if (stringMap == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +0000445 xmlRegexpErrMemory(ctxt, "compiling regexp");
Daniel Veillarda76fe5c2003-04-24 16:06:47 +0000446 xmlFree(stateRemap);
447 xmlFree(ret);
448 return(NULL);
449 }
Daniel Veillard23e73572002-09-19 19:56:43 +0000450 stringRemap = xmlMalloc(ret->nbAtoms * sizeof(int));
Daniel Veillarda76fe5c2003-04-24 16:06:47 +0000451 if (stringRemap == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +0000452 xmlRegexpErrMemory(ctxt, "compiling regexp");
Daniel Veillarda76fe5c2003-04-24 16:06:47 +0000453 xmlFree(stringMap);
454 xmlFree(stateRemap);
455 xmlFree(ret);
456 return(NULL);
457 }
Daniel Veillard23e73572002-09-19 19:56:43 +0000458 for (i = 0;i < ret->nbAtoms;i++) {
459 if ((ret->atoms[i]->type == XML_REGEXP_STRING) &&
460 (ret->atoms[i]->quant == XML_REGEXP_QUANT_ONCE)) {
461 value = ret->atoms[i]->valuep;
462 for (j = 0;j < nbatoms;j++) {
463 if (xmlStrEqual(stringMap[j], value)) {
464 stringRemap[i] = j;
465 break;
466 }
467 }
468 if (j >= nbatoms) {
469 stringRemap[i] = nbatoms;
470 stringMap[nbatoms] = xmlStrdup(value);
Daniel Veillarda76fe5c2003-04-24 16:06:47 +0000471 if (stringMap[nbatoms] == NULL) {
472 for (i = 0;i < nbatoms;i++)
473 xmlFree(stringMap[i]);
474 xmlFree(stringRemap);
475 xmlFree(stringMap);
476 xmlFree(stateRemap);
477 xmlFree(ret);
478 return(NULL);
479 }
Daniel Veillard23e73572002-09-19 19:56:43 +0000480 nbatoms++;
481 }
482 } else {
483 xmlFree(stateRemap);
484 xmlFree(stringRemap);
485 for (i = 0;i < nbatoms;i++)
486 xmlFree(stringMap[i]);
487 xmlFree(stringMap);
Daniel Veillarda76fe5c2003-04-24 16:06:47 +0000488 xmlFree(ret);
489 return(NULL);
Daniel Veillard23e73572002-09-19 19:56:43 +0000490 }
491 }
492#ifdef DEBUG_COMPACTION
493 printf("Final: %d atoms\n", nbatoms);
494#endif
Daniel Veillarda76fe5c2003-04-24 16:06:47 +0000495 transitions = (int *) xmlMalloc((nbstates + 1) *
496 (nbatoms + 1) * sizeof(int));
497 if (transitions == NULL) {
498 xmlFree(stateRemap);
499 xmlFree(stringRemap);
500 xmlFree(stringMap);
501 xmlFree(ret);
502 return(NULL);
503 }
504 memset(transitions, 0, (nbstates + 1) * (nbatoms + 1) * sizeof(int));
Daniel Veillard23e73572002-09-19 19:56:43 +0000505
506 /*
507 * Allocate the transition table. The first entry for each
508 * state correspond to the state type.
509 */
Daniel Veillard118aed72002-09-24 14:13:13 +0000510 transdata = NULL;
Daniel Veillard23e73572002-09-19 19:56:43 +0000511
512 for (i = 0;i < ret->nbStates;i++) {
513 int stateno, atomno, targetno, prev;
514 xmlRegStatePtr state;
515 xmlRegTransPtr trans;
516
517 stateno = stateRemap[i];
518 if (stateno == -1)
519 continue;
520 state = ret->states[i];
521
522 transitions[stateno * (nbatoms + 1)] = state->type;
523
524 for (j = 0;j < state->nbTrans;j++) {
525 trans = &(state->trans[j]);
526 if ((trans->to == -1) || (trans->atom == NULL))
527 continue;
528 atomno = stringRemap[trans->atom->no];
Daniel Veillard118aed72002-09-24 14:13:13 +0000529 if ((trans->atom->data != NULL) && (transdata == NULL)) {
530 transdata = (void **) xmlMalloc(nbstates * nbatoms *
531 sizeof(void *));
532 if (transdata != NULL)
533 memset(transdata, 0,
534 nbstates * nbatoms * sizeof(void *));
Daniel Veillarda76fe5c2003-04-24 16:06:47 +0000535 else {
Daniel Veillardff46a042003-10-08 08:53:17 +0000536 xmlRegexpErrMemory(ctxt, "compiling regexp");
Daniel Veillarda76fe5c2003-04-24 16:06:47 +0000537 break;
538 }
Daniel Veillard118aed72002-09-24 14:13:13 +0000539 }
Daniel Veillard23e73572002-09-19 19:56:43 +0000540 targetno = stateRemap[trans->to];
541 /*
542 * if the same atome can generate transition to 2 different
543 * states then it means the automata is not determinist and
544 * the compact form can't be used !
545 */
546 prev = transitions[stateno * (nbatoms + 1) + atomno + 1];
547 if (prev != 0) {
548 if (prev != targetno + 1) {
Daniel Veillard23e73572002-09-19 19:56:43 +0000549 ret->determinist = 0;
550#ifdef DEBUG_COMPACTION
551 printf("Indet: state %d trans %d, atom %d to %d : %d to %d\n",
552 i, j, trans->atom->no, trans->to, atomno, targetno);
553 printf(" previous to is %d\n", prev);
554#endif
555 ret->determinist = 0;
Daniel Veillard118aed72002-09-24 14:13:13 +0000556 if (transdata != NULL)
557 xmlFree(transdata);
Daniel Veillard23e73572002-09-19 19:56:43 +0000558 xmlFree(transitions);
559 xmlFree(stateRemap);
560 xmlFree(stringRemap);
561 for (i = 0;i < nbatoms;i++)
562 xmlFree(stringMap[i]);
563 xmlFree(stringMap);
Daniel Veillarda76fe5c2003-04-24 16:06:47 +0000564 goto not_determ;
Daniel Veillard23e73572002-09-19 19:56:43 +0000565 }
566 } else {
567#if 0
568 printf("State %d trans %d: atom %d to %d : %d to %d\n",
569 i, j, trans->atom->no, trans->to, atomno, targetno);
570#endif
571 transitions[stateno * (nbatoms + 1) + atomno + 1] =
Daniel Veillard118aed72002-09-24 14:13:13 +0000572 targetno + 1; /* to avoid 0 */
573 if (transdata != NULL)
574 transdata[stateno * nbatoms + atomno] =
575 trans->atom->data;
Daniel Veillard23e73572002-09-19 19:56:43 +0000576 }
577 }
578 }
579 ret->determinist = 1;
580#ifdef DEBUG_COMPACTION
581 /*
582 * Debug
583 */
584 for (i = 0;i < nbstates;i++) {
585 for (j = 0;j < nbatoms + 1;j++) {
586 printf("%02d ", transitions[i * (nbatoms + 1) + j]);
587 }
588 printf("\n");
589 }
590 printf("\n");
591#endif
592 /*
593 * Cleanup of the old data
594 */
595 if (ret->states != NULL) {
596 for (i = 0;i < ret->nbStates;i++)
597 xmlRegFreeState(ret->states[i]);
598 xmlFree(ret->states);
599 }
600 ret->states = NULL;
601 ret->nbStates = 0;
602 if (ret->atoms != NULL) {
603 for (i = 0;i < ret->nbAtoms;i++)
604 xmlRegFreeAtom(ret->atoms[i]);
605 xmlFree(ret->atoms);
606 }
607 ret->atoms = NULL;
608 ret->nbAtoms = 0;
609
610 ret->compact = transitions;
Daniel Veillard118aed72002-09-24 14:13:13 +0000611 ret->transdata = transdata;
Daniel Veillard23e73572002-09-19 19:56:43 +0000612 ret->stringMap = stringMap;
613 ret->nbstrings = nbatoms;
614 ret->nbstates = nbstates;
615 xmlFree(stateRemap);
616 xmlFree(stringRemap);
617 }
Daniel Veillarda76fe5c2003-04-24 16:06:47 +0000618not_determ:
619 ctxt->string = NULL;
620 ctxt->nbStates = 0;
621 ctxt->states = NULL;
622 ctxt->nbAtoms = 0;
623 ctxt->atoms = NULL;
624 ctxt->nbCounters = 0;
625 ctxt->counters = NULL;
Daniel Veillard4255d502002-04-16 15:50:10 +0000626 return(ret);
627}
628
629/**
630 * xmlRegNewParserCtxt:
631 * @string: the string to parse
632 *
633 * Allocate a new regexp parser context
634 *
635 * Returns the new context or NULL in case of error
636 */
637static xmlRegParserCtxtPtr
638xmlRegNewParserCtxt(const xmlChar *string) {
639 xmlRegParserCtxtPtr ret;
640
641 ret = (xmlRegParserCtxtPtr) xmlMalloc(sizeof(xmlRegParserCtxt));
642 if (ret == NULL)
643 return(NULL);
644 memset(ret, 0, sizeof(xmlRegParserCtxt));
645 if (string != NULL)
646 ret->string = xmlStrdup(string);
647 ret->cur = ret->string;
648 ret->neg = 0;
649 ret->error = 0;
Daniel Veillarde19fc232002-04-22 16:01:24 +0000650 ret->determinist = -1;
Daniel Veillard4255d502002-04-16 15:50:10 +0000651 return(ret);
652}
653
654/**
655 * xmlRegNewRange:
656 * @ctxt: the regexp parser context
657 * @neg: is that negative
658 * @type: the type of range
659 * @start: the start codepoint
660 * @end: the end codepoint
661 *
662 * Allocate a new regexp range
663 *
664 * Returns the new range or NULL in case of error
665 */
666static xmlRegRangePtr
667xmlRegNewRange(xmlRegParserCtxtPtr ctxt,
668 int neg, xmlRegAtomType type, int start, int end) {
669 xmlRegRangePtr ret;
670
671 ret = (xmlRegRangePtr) xmlMalloc(sizeof(xmlRegRange));
672 if (ret == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +0000673 xmlRegexpErrMemory(ctxt, "allocating range");
Daniel Veillard4255d502002-04-16 15:50:10 +0000674 return(NULL);
675 }
676 ret->neg = neg;
677 ret->type = type;
678 ret->start = start;
679 ret->end = end;
680 return(ret);
681}
682
683/**
684 * xmlRegFreeRange:
685 * @range: the regexp range
686 *
687 * Free a regexp range
688 */
689static void
690xmlRegFreeRange(xmlRegRangePtr range) {
691 if (range == NULL)
692 return;
693
694 if (range->blockName != NULL)
695 xmlFree(range->blockName);
696 xmlFree(range);
697}
698
699/**
700 * xmlRegNewAtom:
701 * @ctxt: the regexp parser context
702 * @type: the type of atom
703 *
704 * Allocate a new regexp range
705 *
706 * Returns the new atom or NULL in case of error
707 */
708static xmlRegAtomPtr
709xmlRegNewAtom(xmlRegParserCtxtPtr ctxt, xmlRegAtomType type) {
710 xmlRegAtomPtr ret;
711
712 ret = (xmlRegAtomPtr) xmlMalloc(sizeof(xmlRegAtom));
713 if (ret == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +0000714 xmlRegexpErrMemory(ctxt, "allocating atom");
Daniel Veillard4255d502002-04-16 15:50:10 +0000715 return(NULL);
716 }
717 memset(ret, 0, sizeof(xmlRegAtom));
718 ret->type = type;
719 ret->quant = XML_REGEXP_QUANT_ONCE;
720 ret->min = 0;
721 ret->max = 0;
722 return(ret);
723}
724
725/**
726 * xmlRegFreeAtom:
727 * @atom: the regexp atom
728 *
729 * Free a regexp atom
730 */
731static void
732xmlRegFreeAtom(xmlRegAtomPtr atom) {
733 int i;
734
735 if (atom == NULL)
736 return;
737
738 for (i = 0;i < atom->nbRanges;i++)
739 xmlRegFreeRange(atom->ranges[i]);
740 if (atom->ranges != NULL)
741 xmlFree(atom->ranges);
742 if (atom->type == XML_REGEXP_STRING)
743 xmlFree(atom->valuep);
744 xmlFree(atom);
745}
746
747static xmlRegStatePtr
748xmlRegNewState(xmlRegParserCtxtPtr ctxt) {
749 xmlRegStatePtr ret;
750
751 ret = (xmlRegStatePtr) xmlMalloc(sizeof(xmlRegState));
752 if (ret == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +0000753 xmlRegexpErrMemory(ctxt, "allocating state");
Daniel Veillard4255d502002-04-16 15:50:10 +0000754 return(NULL);
755 }
756 memset(ret, 0, sizeof(xmlRegState));
757 ret->type = XML_REGEXP_TRANS_STATE;
758 ret->mark = XML_REGEXP_MARK_NORMAL;
759 return(ret);
760}
761
762/**
763 * xmlRegFreeState:
764 * @state: the regexp state
765 *
766 * Free a regexp state
767 */
768static void
769xmlRegFreeState(xmlRegStatePtr state) {
770 if (state == NULL)
771 return;
772
773 if (state->trans != NULL)
774 xmlFree(state->trans);
775 xmlFree(state);
776}
777
778/**
779 * xmlRegFreeParserCtxt:
780 * @ctxt: the regexp parser context
781 *
782 * Free a regexp parser context
783 */
784static void
785xmlRegFreeParserCtxt(xmlRegParserCtxtPtr ctxt) {
786 int i;
787 if (ctxt == NULL)
788 return;
789
790 if (ctxt->string != NULL)
791 xmlFree(ctxt->string);
792 if (ctxt->states != NULL) {
793 for (i = 0;i < ctxt->nbStates;i++)
794 xmlRegFreeState(ctxt->states[i]);
795 xmlFree(ctxt->states);
796 }
797 if (ctxt->atoms != NULL) {
798 for (i = 0;i < ctxt->nbAtoms;i++)
799 xmlRegFreeAtom(ctxt->atoms[i]);
800 xmlFree(ctxt->atoms);
801 }
802 if (ctxt->counters != NULL)
803 xmlFree(ctxt->counters);
804 xmlFree(ctxt);
805}
806
807/************************************************************************
808 * *
809 * Display of Data structures *
810 * *
811 ************************************************************************/
812
813static void
814xmlRegPrintAtomType(FILE *output, xmlRegAtomType type) {
815 switch (type) {
816 case XML_REGEXP_EPSILON:
817 fprintf(output, "epsilon "); break;
818 case XML_REGEXP_CHARVAL:
819 fprintf(output, "charval "); break;
820 case XML_REGEXP_RANGES:
821 fprintf(output, "ranges "); break;
822 case XML_REGEXP_SUBREG:
823 fprintf(output, "subexpr "); break;
824 case XML_REGEXP_STRING:
825 fprintf(output, "string "); break;
826 case XML_REGEXP_ANYCHAR:
827 fprintf(output, "anychar "); break;
828 case XML_REGEXP_ANYSPACE:
829 fprintf(output, "anyspace "); break;
830 case XML_REGEXP_NOTSPACE:
831 fprintf(output, "notspace "); break;
832 case XML_REGEXP_INITNAME:
833 fprintf(output, "initname "); break;
834 case XML_REGEXP_NOTINITNAME:
835 fprintf(output, "notinitname "); break;
836 case XML_REGEXP_NAMECHAR:
837 fprintf(output, "namechar "); break;
838 case XML_REGEXP_NOTNAMECHAR:
839 fprintf(output, "notnamechar "); break;
840 case XML_REGEXP_DECIMAL:
841 fprintf(output, "decimal "); break;
842 case XML_REGEXP_NOTDECIMAL:
843 fprintf(output, "notdecimal "); break;
844 case XML_REGEXP_REALCHAR:
845 fprintf(output, "realchar "); break;
846 case XML_REGEXP_NOTREALCHAR:
847 fprintf(output, "notrealchar "); break;
848 case XML_REGEXP_LETTER:
849 fprintf(output, "LETTER "); break;
850 case XML_REGEXP_LETTER_UPPERCASE:
851 fprintf(output, "LETTER_UPPERCASE "); break;
852 case XML_REGEXP_LETTER_LOWERCASE:
853 fprintf(output, "LETTER_LOWERCASE "); break;
854 case XML_REGEXP_LETTER_TITLECASE:
855 fprintf(output, "LETTER_TITLECASE "); break;
856 case XML_REGEXP_LETTER_MODIFIER:
857 fprintf(output, "LETTER_MODIFIER "); break;
858 case XML_REGEXP_LETTER_OTHERS:
859 fprintf(output, "LETTER_OTHERS "); break;
860 case XML_REGEXP_MARK:
861 fprintf(output, "MARK "); break;
862 case XML_REGEXP_MARK_NONSPACING:
863 fprintf(output, "MARK_NONSPACING "); break;
864 case XML_REGEXP_MARK_SPACECOMBINING:
865 fprintf(output, "MARK_SPACECOMBINING "); break;
866 case XML_REGEXP_MARK_ENCLOSING:
867 fprintf(output, "MARK_ENCLOSING "); break;
868 case XML_REGEXP_NUMBER:
869 fprintf(output, "NUMBER "); break;
870 case XML_REGEXP_NUMBER_DECIMAL:
871 fprintf(output, "NUMBER_DECIMAL "); break;
872 case XML_REGEXP_NUMBER_LETTER:
873 fprintf(output, "NUMBER_LETTER "); break;
874 case XML_REGEXP_NUMBER_OTHERS:
875 fprintf(output, "NUMBER_OTHERS "); break;
876 case XML_REGEXP_PUNCT:
877 fprintf(output, "PUNCT "); break;
878 case XML_REGEXP_PUNCT_CONNECTOR:
879 fprintf(output, "PUNCT_CONNECTOR "); break;
880 case XML_REGEXP_PUNCT_DASH:
881 fprintf(output, "PUNCT_DASH "); break;
882 case XML_REGEXP_PUNCT_OPEN:
883 fprintf(output, "PUNCT_OPEN "); break;
884 case XML_REGEXP_PUNCT_CLOSE:
885 fprintf(output, "PUNCT_CLOSE "); break;
886 case XML_REGEXP_PUNCT_INITQUOTE:
887 fprintf(output, "PUNCT_INITQUOTE "); break;
888 case XML_REGEXP_PUNCT_FINQUOTE:
889 fprintf(output, "PUNCT_FINQUOTE "); break;
890 case XML_REGEXP_PUNCT_OTHERS:
891 fprintf(output, "PUNCT_OTHERS "); break;
892 case XML_REGEXP_SEPAR:
893 fprintf(output, "SEPAR "); break;
894 case XML_REGEXP_SEPAR_SPACE:
895 fprintf(output, "SEPAR_SPACE "); break;
896 case XML_REGEXP_SEPAR_LINE:
897 fprintf(output, "SEPAR_LINE "); break;
898 case XML_REGEXP_SEPAR_PARA:
899 fprintf(output, "SEPAR_PARA "); break;
900 case XML_REGEXP_SYMBOL:
901 fprintf(output, "SYMBOL "); break;
902 case XML_REGEXP_SYMBOL_MATH:
903 fprintf(output, "SYMBOL_MATH "); break;
904 case XML_REGEXP_SYMBOL_CURRENCY:
905 fprintf(output, "SYMBOL_CURRENCY "); break;
906 case XML_REGEXP_SYMBOL_MODIFIER:
907 fprintf(output, "SYMBOL_MODIFIER "); break;
908 case XML_REGEXP_SYMBOL_OTHERS:
909 fprintf(output, "SYMBOL_OTHERS "); break;
910 case XML_REGEXP_OTHER:
911 fprintf(output, "OTHER "); break;
912 case XML_REGEXP_OTHER_CONTROL:
913 fprintf(output, "OTHER_CONTROL "); break;
914 case XML_REGEXP_OTHER_FORMAT:
915 fprintf(output, "OTHER_FORMAT "); break;
916 case XML_REGEXP_OTHER_PRIVATE:
917 fprintf(output, "OTHER_PRIVATE "); break;
918 case XML_REGEXP_OTHER_NA:
919 fprintf(output, "OTHER_NA "); break;
920 case XML_REGEXP_BLOCK_NAME:
921 fprintf(output, "BLOCK "); break;
922 }
923}
924
925static void
926xmlRegPrintQuantType(FILE *output, xmlRegQuantType type) {
927 switch (type) {
928 case XML_REGEXP_QUANT_EPSILON:
929 fprintf(output, "epsilon "); break;
930 case XML_REGEXP_QUANT_ONCE:
931 fprintf(output, "once "); break;
932 case XML_REGEXP_QUANT_OPT:
933 fprintf(output, "? "); break;
934 case XML_REGEXP_QUANT_MULT:
935 fprintf(output, "* "); break;
936 case XML_REGEXP_QUANT_PLUS:
937 fprintf(output, "+ "); break;
938 case XML_REGEXP_QUANT_RANGE:
939 fprintf(output, "range "); break;
Daniel Veillard7646b182002-04-20 06:41:40 +0000940 case XML_REGEXP_QUANT_ONCEONLY:
941 fprintf(output, "onceonly "); break;
942 case XML_REGEXP_QUANT_ALL:
943 fprintf(output, "all "); break;
Daniel Veillard4255d502002-04-16 15:50:10 +0000944 }
945}
946static void
947xmlRegPrintRange(FILE *output, xmlRegRangePtr range) {
948 fprintf(output, " range: ");
949 if (range->neg)
950 fprintf(output, "negative ");
951 xmlRegPrintAtomType(output, range->type);
952 fprintf(output, "%c - %c\n", range->start, range->end);
953}
954
955static void
956xmlRegPrintAtom(FILE *output, xmlRegAtomPtr atom) {
957 fprintf(output, " atom: ");
958 if (atom == NULL) {
959 fprintf(output, "NULL\n");
960 return;
961 }
962 xmlRegPrintAtomType(output, atom->type);
963 xmlRegPrintQuantType(output, atom->quant);
964 if (atom->quant == XML_REGEXP_QUANT_RANGE)
965 fprintf(output, "%d-%d ", atom->min, atom->max);
966 if (atom->type == XML_REGEXP_STRING)
967 fprintf(output, "'%s' ", (char *) atom->valuep);
968 if (atom->type == XML_REGEXP_CHARVAL)
969 fprintf(output, "char %c\n", atom->codepoint);
970 else if (atom->type == XML_REGEXP_RANGES) {
971 int i;
972 fprintf(output, "%d entries\n", atom->nbRanges);
973 for (i = 0; i < atom->nbRanges;i++)
974 xmlRegPrintRange(output, atom->ranges[i]);
975 } else if (atom->type == XML_REGEXP_SUBREG) {
976 fprintf(output, "start %d end %d\n", atom->start->no, atom->stop->no);
977 } else {
978 fprintf(output, "\n");
979 }
980}
981
982static void
983xmlRegPrintTrans(FILE *output, xmlRegTransPtr trans) {
984 fprintf(output, " trans: ");
985 if (trans == NULL) {
986 fprintf(output, "NULL\n");
987 return;
988 }
989 if (trans->to < 0) {
990 fprintf(output, "removed\n");
991 return;
992 }
993 if (trans->counter >= 0) {
994 fprintf(output, "counted %d, ", trans->counter);
995 }
Daniel Veillard8a001f62002-04-20 07:24:11 +0000996 if (trans->count == REGEXP_ALL_COUNTER) {
997 fprintf(output, "all transition, ");
998 } else if (trans->count >= 0) {
Daniel Veillard4255d502002-04-16 15:50:10 +0000999 fprintf(output, "count based %d, ", trans->count);
1000 }
1001 if (trans->atom == NULL) {
1002 fprintf(output, "epsilon to %d\n", trans->to);
1003 return;
1004 }
1005 if (trans->atom->type == XML_REGEXP_CHARVAL)
1006 fprintf(output, "char %c ", trans->atom->codepoint);
1007 fprintf(output, "atom %d, to %d\n", trans->atom->no, trans->to);
1008}
1009
1010static void
1011xmlRegPrintState(FILE *output, xmlRegStatePtr state) {
1012 int i;
1013
1014 fprintf(output, " state: ");
1015 if (state == NULL) {
1016 fprintf(output, "NULL\n");
1017 return;
1018 }
1019 if (state->type == XML_REGEXP_START_STATE)
1020 fprintf(output, "START ");
1021 if (state->type == XML_REGEXP_FINAL_STATE)
1022 fprintf(output, "FINAL ");
1023
1024 fprintf(output, "%d, %d transitions:\n", state->no, state->nbTrans);
1025 for (i = 0;i < state->nbTrans; i++) {
1026 xmlRegPrintTrans(output, &(state->trans[i]));
1027 }
1028}
1029
Daniel Veillard23e73572002-09-19 19:56:43 +00001030#ifdef DEBUG_REGEXP_GRAPH
Daniel Veillard4255d502002-04-16 15:50:10 +00001031static void
1032xmlRegPrintCtxt(FILE *output, xmlRegParserCtxtPtr ctxt) {
1033 int i;
1034
1035 fprintf(output, " ctxt: ");
1036 if (ctxt == NULL) {
1037 fprintf(output, "NULL\n");
1038 return;
1039 }
1040 fprintf(output, "'%s' ", ctxt->string);
1041 if (ctxt->error)
1042 fprintf(output, "error ");
1043 if (ctxt->neg)
1044 fprintf(output, "neg ");
1045 fprintf(output, "\n");
1046 fprintf(output, "%d atoms:\n", ctxt->nbAtoms);
1047 for (i = 0;i < ctxt->nbAtoms; i++) {
1048 fprintf(output, " %02d ", i);
1049 xmlRegPrintAtom(output, ctxt->atoms[i]);
1050 }
1051 if (ctxt->atom != NULL) {
1052 fprintf(output, "current atom:\n");
1053 xmlRegPrintAtom(output, ctxt->atom);
1054 }
1055 fprintf(output, "%d states:", ctxt->nbStates);
1056 if (ctxt->start != NULL)
1057 fprintf(output, " start: %d", ctxt->start->no);
1058 if (ctxt->end != NULL)
1059 fprintf(output, " end: %d", ctxt->end->no);
1060 fprintf(output, "\n");
1061 for (i = 0;i < ctxt->nbStates; i++) {
1062 xmlRegPrintState(output, ctxt->states[i]);
1063 }
1064 fprintf(output, "%d counters:\n", ctxt->nbCounters);
1065 for (i = 0;i < ctxt->nbCounters; i++) {
1066 fprintf(output, " %d: min %d max %d\n", i, ctxt->counters[i].min,
1067 ctxt->counters[i].max);
1068 }
1069}
Daniel Veillard23e73572002-09-19 19:56:43 +00001070#endif
Daniel Veillard4255d502002-04-16 15:50:10 +00001071
1072/************************************************************************
1073 * *
1074 * Finite Automata structures manipulations *
1075 * *
1076 ************************************************************************/
1077
1078static void
1079xmlRegAtomAddRange(xmlRegParserCtxtPtr ctxt, xmlRegAtomPtr atom,
1080 int neg, xmlRegAtomType type, int start, int end,
1081 xmlChar *blockName) {
1082 xmlRegRangePtr range;
1083
1084 if (atom == NULL) {
1085 ERROR("add range: atom is NULL");
1086 return;
1087 }
1088 if (atom->type != XML_REGEXP_RANGES) {
1089 ERROR("add range: atom is not ranges");
1090 return;
1091 }
1092 if (atom->maxRanges == 0) {
1093 atom->maxRanges = 4;
1094 atom->ranges = (xmlRegRangePtr *) xmlMalloc(atom->maxRanges *
1095 sizeof(xmlRegRangePtr));
1096 if (atom->ranges == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +00001097 xmlRegexpErrMemory(ctxt, "adding ranges");
Daniel Veillard4255d502002-04-16 15:50:10 +00001098 atom->maxRanges = 0;
1099 return;
1100 }
1101 } else if (atom->nbRanges >= atom->maxRanges) {
1102 xmlRegRangePtr *tmp;
1103 atom->maxRanges *= 2;
1104 tmp = (xmlRegRangePtr *) xmlRealloc(atom->ranges, atom->maxRanges *
1105 sizeof(xmlRegRangePtr));
1106 if (tmp == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +00001107 xmlRegexpErrMemory(ctxt, "adding ranges");
Daniel Veillard4255d502002-04-16 15:50:10 +00001108 atom->maxRanges /= 2;
1109 return;
1110 }
1111 atom->ranges = tmp;
1112 }
1113 range = xmlRegNewRange(ctxt, neg, type, start, end);
1114 if (range == NULL)
1115 return;
1116 range->blockName = blockName;
1117 atom->ranges[atom->nbRanges++] = range;
1118
1119}
1120
1121static int
1122xmlRegGetCounter(xmlRegParserCtxtPtr ctxt) {
1123 if (ctxt->maxCounters == 0) {
1124 ctxt->maxCounters = 4;
1125 ctxt->counters = (xmlRegCounter *) xmlMalloc(ctxt->maxCounters *
1126 sizeof(xmlRegCounter));
1127 if (ctxt->counters == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +00001128 xmlRegexpErrMemory(ctxt, "allocating counter");
Daniel Veillard4255d502002-04-16 15:50:10 +00001129 ctxt->maxCounters = 0;
1130 return(-1);
1131 }
1132 } else if (ctxt->nbCounters >= ctxt->maxCounters) {
1133 xmlRegCounter *tmp;
1134 ctxt->maxCounters *= 2;
1135 tmp = (xmlRegCounter *) xmlRealloc(ctxt->counters, ctxt->maxCounters *
1136 sizeof(xmlRegCounter));
1137 if (tmp == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +00001138 xmlRegexpErrMemory(ctxt, "allocating counter");
Daniel Veillard4255d502002-04-16 15:50:10 +00001139 ctxt->maxCounters /= 2;
1140 return(-1);
1141 }
1142 ctxt->counters = tmp;
1143 }
1144 ctxt->counters[ctxt->nbCounters].min = -1;
1145 ctxt->counters[ctxt->nbCounters].max = -1;
1146 return(ctxt->nbCounters++);
1147}
1148
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00001149static int
Daniel Veillard4255d502002-04-16 15:50:10 +00001150xmlRegAtomPush(xmlRegParserCtxtPtr ctxt, xmlRegAtomPtr atom) {
1151 if (atom == NULL) {
1152 ERROR("atom push: atom is NULL");
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00001153 return(-1);
Daniel Veillard4255d502002-04-16 15:50:10 +00001154 }
1155 if (ctxt->maxAtoms == 0) {
1156 ctxt->maxAtoms = 4;
1157 ctxt->atoms = (xmlRegAtomPtr *) xmlMalloc(ctxt->maxAtoms *
1158 sizeof(xmlRegAtomPtr));
1159 if (ctxt->atoms == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +00001160 xmlRegexpErrMemory(ctxt, "pushing atom");
Daniel Veillard4255d502002-04-16 15:50:10 +00001161 ctxt->maxAtoms = 0;
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00001162 return(-1);
Daniel Veillard4255d502002-04-16 15:50:10 +00001163 }
1164 } else if (ctxt->nbAtoms >= ctxt->maxAtoms) {
1165 xmlRegAtomPtr *tmp;
1166 ctxt->maxAtoms *= 2;
1167 tmp = (xmlRegAtomPtr *) xmlRealloc(ctxt->atoms, ctxt->maxAtoms *
1168 sizeof(xmlRegAtomPtr));
1169 if (tmp == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +00001170 xmlRegexpErrMemory(ctxt, "allocating counter");
Daniel Veillard4255d502002-04-16 15:50:10 +00001171 ctxt->maxAtoms /= 2;
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00001172 return(-1);
Daniel Veillard4255d502002-04-16 15:50:10 +00001173 }
1174 ctxt->atoms = tmp;
1175 }
1176 atom->no = ctxt->nbAtoms;
1177 ctxt->atoms[ctxt->nbAtoms++] = atom;
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00001178 return(0);
Daniel Veillard4255d502002-04-16 15:50:10 +00001179}
1180
1181static void
1182xmlRegStateAddTrans(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr state,
1183 xmlRegAtomPtr atom, xmlRegStatePtr target,
1184 int counter, int count) {
1185 if (state == NULL) {
1186 ERROR("add state: state is NULL");
1187 return;
1188 }
1189 if (target == NULL) {
1190 ERROR("add state: target is NULL");
1191 return;
1192 }
1193 if (state->maxTrans == 0) {
1194 state->maxTrans = 4;
1195 state->trans = (xmlRegTrans *) xmlMalloc(state->maxTrans *
1196 sizeof(xmlRegTrans));
1197 if (state->trans == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +00001198 xmlRegexpErrMemory(ctxt, "adding transition");
Daniel Veillard4255d502002-04-16 15:50:10 +00001199 state->maxTrans = 0;
1200 return;
1201 }
1202 } else if (state->nbTrans >= state->maxTrans) {
1203 xmlRegTrans *tmp;
1204 state->maxTrans *= 2;
1205 tmp = (xmlRegTrans *) xmlRealloc(state->trans, state->maxTrans *
1206 sizeof(xmlRegTrans));
1207 if (tmp == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +00001208 xmlRegexpErrMemory(ctxt, "adding transition");
Daniel Veillard4255d502002-04-16 15:50:10 +00001209 state->maxTrans /= 2;
1210 return;
1211 }
1212 state->trans = tmp;
1213 }
1214#ifdef DEBUG_REGEXP_GRAPH
1215 printf("Add trans from %d to %d ", state->no, target->no);
Daniel Veillard8a001f62002-04-20 07:24:11 +00001216 if (count == REGEXP_ALL_COUNTER)
1217 printf("all transition");
Daniel Veillard4402ab42002-09-12 16:02:56 +00001218 else if (count >= 0)
Daniel Veillard4255d502002-04-16 15:50:10 +00001219 printf("count based %d", count);
1220 else if (counter >= 0)
1221 printf("counted %d", counter);
1222 else if (atom == NULL)
1223 printf("epsilon transition");
1224 printf("\n");
1225#endif
1226
1227 state->trans[state->nbTrans].atom = atom;
1228 state->trans[state->nbTrans].to = target->no;
1229 state->trans[state->nbTrans].counter = counter;
1230 state->trans[state->nbTrans].count = count;
1231 state->nbTrans++;
1232}
1233
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00001234static int
Daniel Veillard4255d502002-04-16 15:50:10 +00001235xmlRegStatePush(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr state) {
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00001236 if (state == NULL) return(-1);
Daniel Veillard4255d502002-04-16 15:50:10 +00001237 if (ctxt->maxStates == 0) {
1238 ctxt->maxStates = 4;
1239 ctxt->states = (xmlRegStatePtr *) xmlMalloc(ctxt->maxStates *
1240 sizeof(xmlRegStatePtr));
1241 if (ctxt->states == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +00001242 xmlRegexpErrMemory(ctxt, "adding state");
Daniel Veillard4255d502002-04-16 15:50:10 +00001243 ctxt->maxStates = 0;
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00001244 return(-1);
Daniel Veillard4255d502002-04-16 15:50:10 +00001245 }
1246 } else if (ctxt->nbStates >= ctxt->maxStates) {
1247 xmlRegStatePtr *tmp;
1248 ctxt->maxStates *= 2;
1249 tmp = (xmlRegStatePtr *) xmlRealloc(ctxt->states, ctxt->maxStates *
1250 sizeof(xmlRegStatePtr));
1251 if (tmp == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +00001252 xmlRegexpErrMemory(ctxt, "adding state");
Daniel Veillard4255d502002-04-16 15:50:10 +00001253 ctxt->maxStates /= 2;
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00001254 return(-1);
Daniel Veillard4255d502002-04-16 15:50:10 +00001255 }
1256 ctxt->states = tmp;
1257 }
1258 state->no = ctxt->nbStates;
1259 ctxt->states[ctxt->nbStates++] = state;
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00001260 return(0);
Daniel Veillard4255d502002-04-16 15:50:10 +00001261}
1262
1263/**
Daniel Veillard7646b182002-04-20 06:41:40 +00001264 * xmlFAGenerateAllTransition:
Daniel Veillard441bc322002-04-20 17:38:48 +00001265 * @ctxt: a regexp parser context
1266 * @from: the from state
1267 * @to: the target state or NULL for building a new one
1268 * @lax:
Daniel Veillard7646b182002-04-20 06:41:40 +00001269 *
1270 */
1271static void
1272xmlFAGenerateAllTransition(xmlRegParserCtxtPtr ctxt,
Daniel Veillard441bc322002-04-20 17:38:48 +00001273 xmlRegStatePtr from, xmlRegStatePtr to,
1274 int lax) {
Daniel Veillard7646b182002-04-20 06:41:40 +00001275 if (to == NULL) {
1276 to = xmlRegNewState(ctxt);
1277 xmlRegStatePush(ctxt, to);
1278 ctxt->state = to;
1279 }
Daniel Veillard441bc322002-04-20 17:38:48 +00001280 if (lax)
1281 xmlRegStateAddTrans(ctxt, from, NULL, to, -1, REGEXP_ALL_LAX_COUNTER);
1282 else
1283 xmlRegStateAddTrans(ctxt, from, NULL, to, -1, REGEXP_ALL_COUNTER);
Daniel Veillard7646b182002-04-20 06:41:40 +00001284}
1285
1286/**
Daniel Veillard4255d502002-04-16 15:50:10 +00001287 * xmlFAGenerateEpsilonTransition:
Daniel Veillard441bc322002-04-20 17:38:48 +00001288 * @ctxt: a regexp parser context
1289 * @from: the from state
1290 * @to: the target state or NULL for building a new one
Daniel Veillard4255d502002-04-16 15:50:10 +00001291 *
1292 */
1293static void
1294xmlFAGenerateEpsilonTransition(xmlRegParserCtxtPtr ctxt,
1295 xmlRegStatePtr from, xmlRegStatePtr to) {
1296 if (to == NULL) {
1297 to = xmlRegNewState(ctxt);
1298 xmlRegStatePush(ctxt, to);
1299 ctxt->state = to;
1300 }
1301 xmlRegStateAddTrans(ctxt, from, NULL, to, -1, -1);
1302}
1303
1304/**
1305 * xmlFAGenerateCountedEpsilonTransition:
Daniel Veillard441bc322002-04-20 17:38:48 +00001306 * @ctxt: a regexp parser context
1307 * @from: the from state
1308 * @to: the target state or NULL for building a new one
Daniel Veillard4255d502002-04-16 15:50:10 +00001309 * counter: the counter for that transition
1310 *
1311 */
1312static void
1313xmlFAGenerateCountedEpsilonTransition(xmlRegParserCtxtPtr ctxt,
1314 xmlRegStatePtr from, xmlRegStatePtr to, int counter) {
1315 if (to == NULL) {
1316 to = xmlRegNewState(ctxt);
1317 xmlRegStatePush(ctxt, to);
1318 ctxt->state = to;
1319 }
1320 xmlRegStateAddTrans(ctxt, from, NULL, to, counter, -1);
1321}
1322
1323/**
1324 * xmlFAGenerateCountedTransition:
Daniel Veillard441bc322002-04-20 17:38:48 +00001325 * @ctxt: a regexp parser context
1326 * @from: the from state
1327 * @to: the target state or NULL for building a new one
Daniel Veillard4255d502002-04-16 15:50:10 +00001328 * counter: the counter for that transition
1329 *
1330 */
1331static void
1332xmlFAGenerateCountedTransition(xmlRegParserCtxtPtr ctxt,
1333 xmlRegStatePtr from, xmlRegStatePtr to, int counter) {
1334 if (to == NULL) {
1335 to = xmlRegNewState(ctxt);
1336 xmlRegStatePush(ctxt, to);
1337 ctxt->state = to;
1338 }
1339 xmlRegStateAddTrans(ctxt, from, NULL, to, -1, counter);
1340}
1341
1342/**
1343 * xmlFAGenerateTransitions:
Daniel Veillard441bc322002-04-20 17:38:48 +00001344 * @ctxt: a regexp parser context
1345 * @from: the from state
1346 * @to: the target state or NULL for building a new one
1347 * @atom: the atom generating the transition
Daniel Veillard4255d502002-04-16 15:50:10 +00001348 *
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00001349 * Returns 0 if succes and -1 in case of error.
Daniel Veillard4255d502002-04-16 15:50:10 +00001350 */
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00001351static int
Daniel Veillard4255d502002-04-16 15:50:10 +00001352xmlFAGenerateTransitions(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr from,
1353 xmlRegStatePtr to, xmlRegAtomPtr atom) {
1354 if (atom == NULL) {
1355 ERROR("genrate transition: atom == NULL");
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00001356 return(-1);
Daniel Veillard4255d502002-04-16 15:50:10 +00001357 }
1358 if (atom->type == XML_REGEXP_SUBREG) {
1359 /*
1360 * this is a subexpression handling one should not need to
1361 * create a new node excep for XML_REGEXP_QUANT_RANGE.
1362 */
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00001363 if (xmlRegAtomPush(ctxt, atom) < 0) {
1364 return(-1);
1365 }
Daniel Veillard4255d502002-04-16 15:50:10 +00001366 if ((to != NULL) && (atom->stop != to) &&
1367 (atom->quant != XML_REGEXP_QUANT_RANGE)) {
1368 /*
1369 * Generate an epsilon transition to link to the target
1370 */
1371 xmlFAGenerateEpsilonTransition(ctxt, atom->stop, to);
1372 }
1373 switch (atom->quant) {
1374 case XML_REGEXP_QUANT_OPT:
1375 atom->quant = XML_REGEXP_QUANT_ONCE;
1376 xmlFAGenerateEpsilonTransition(ctxt, atom->start, atom->stop);
1377 break;
1378 case XML_REGEXP_QUANT_MULT:
1379 atom->quant = XML_REGEXP_QUANT_ONCE;
1380 xmlFAGenerateEpsilonTransition(ctxt, atom->start, atom->stop);
1381 xmlFAGenerateEpsilonTransition(ctxt, atom->stop, atom->start);
1382 break;
1383 case XML_REGEXP_QUANT_PLUS:
1384 atom->quant = XML_REGEXP_QUANT_ONCE;
1385 xmlFAGenerateEpsilonTransition(ctxt, atom->stop, atom->start);
1386 break;
1387 case XML_REGEXP_QUANT_RANGE: {
1388 int counter;
1389 xmlRegStatePtr newstate;
1390
1391 /*
1392 * This one is nasty:
1393 * 1/ register a new counter
1394 * 2/ register an epsilon transition associated to
1395 * this counter going from atom->stop to atom->start
1396 * 3/ create a new state
1397 * 4/ generate a counted transition from atom->stop to
1398 * that state
1399 */
1400 counter = xmlRegGetCounter(ctxt);
1401 ctxt->counters[counter].min = atom->min - 1;
1402 ctxt->counters[counter].max = atom->max - 1;
1403 atom->min = 0;
1404 atom->max = 0;
1405 atom->quant = XML_REGEXP_QUANT_ONCE;
1406 xmlFAGenerateCountedEpsilonTransition(ctxt, atom->stop,
1407 atom->start, counter);
1408 if (to != NULL) {
1409 newstate = to;
1410 } else {
1411 newstate = xmlRegNewState(ctxt);
1412 xmlRegStatePush(ctxt, newstate);
1413 ctxt->state = newstate;
1414 }
1415 xmlFAGenerateCountedTransition(ctxt, atom->stop,
1416 newstate, counter);
1417 }
1418 default:
1419 break;
1420 }
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00001421 return(0);
Daniel Veillard4255d502002-04-16 15:50:10 +00001422 } else {
1423 if (to == NULL) {
1424 to = xmlRegNewState(ctxt);
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00001425 if (to != NULL)
1426 xmlRegStatePush(ctxt, to);
1427 else {
1428 return(-1);
1429 }
1430 }
1431 if (xmlRegAtomPush(ctxt, atom) < 0) {
1432 return(-1);
Daniel Veillard4255d502002-04-16 15:50:10 +00001433 }
1434 xmlRegStateAddTrans(ctxt, from, atom, to, -1, -1);
Daniel Veillard4255d502002-04-16 15:50:10 +00001435 ctxt->state = to;
1436 }
1437 switch (atom->quant) {
1438 case XML_REGEXP_QUANT_OPT:
1439 atom->quant = XML_REGEXP_QUANT_ONCE;
1440 xmlFAGenerateEpsilonTransition(ctxt, from, to);
1441 break;
1442 case XML_REGEXP_QUANT_MULT:
1443 atom->quant = XML_REGEXP_QUANT_ONCE;
1444 xmlFAGenerateEpsilonTransition(ctxt, from, to);
1445 xmlRegStateAddTrans(ctxt, to, atom, to, -1, -1);
1446 break;
1447 case XML_REGEXP_QUANT_PLUS:
1448 atom->quant = XML_REGEXP_QUANT_ONCE;
1449 xmlRegStateAddTrans(ctxt, to, atom, to, -1, -1);
1450 break;
1451 default:
1452 break;
1453 }
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00001454 return(0);
Daniel Veillard4255d502002-04-16 15:50:10 +00001455}
1456
1457/**
1458 * xmlFAReduceEpsilonTransitions:
Daniel Veillard441bc322002-04-20 17:38:48 +00001459 * @ctxt: a regexp parser context
Daniel Veillard4255d502002-04-16 15:50:10 +00001460 * @fromnr: the from state
1461 * @tonr: the to state
1462 * @cpunter: should that transition be associted to a counted
1463 *
1464 */
1465static void
1466xmlFAReduceEpsilonTransitions(xmlRegParserCtxtPtr ctxt, int fromnr,
1467 int tonr, int counter) {
1468 int transnr;
1469 xmlRegStatePtr from;
1470 xmlRegStatePtr to;
1471
1472#ifdef DEBUG_REGEXP_GRAPH
1473 printf("xmlFAReduceEpsilonTransitions(%d, %d)\n", fromnr, tonr);
1474#endif
1475 from = ctxt->states[fromnr];
1476 if (from == NULL)
1477 return;
1478 to = ctxt->states[tonr];
1479 if (to == NULL)
1480 return;
1481 if ((to->mark == XML_REGEXP_MARK_START) ||
1482 (to->mark == XML_REGEXP_MARK_VISITED))
1483 return;
1484
1485 to->mark = XML_REGEXP_MARK_VISITED;
1486 if (to->type == XML_REGEXP_FINAL_STATE) {
1487#ifdef DEBUG_REGEXP_GRAPH
1488 printf("State %d is final, so %d becomes final\n", tonr, fromnr);
1489#endif
1490 from->type = XML_REGEXP_FINAL_STATE;
1491 }
1492 for (transnr = 0;transnr < to->nbTrans;transnr++) {
1493 if (to->trans[transnr].atom == NULL) {
1494 /*
1495 * Don't remove counted transitions
1496 * Don't loop either
1497 */
Daniel Veillardb509f152002-04-17 16:28:10 +00001498 if (to->trans[transnr].to != fromnr) {
1499 if (to->trans[transnr].count >= 0) {
1500 int newto = to->trans[transnr].to;
1501
1502 xmlRegStateAddTrans(ctxt, from, NULL,
1503 ctxt->states[newto],
1504 -1, to->trans[transnr].count);
1505 } else {
Daniel Veillard4255d502002-04-16 15:50:10 +00001506#ifdef DEBUG_REGEXP_GRAPH
Daniel Veillardb509f152002-04-17 16:28:10 +00001507 printf("Found epsilon trans %d from %d to %d\n",
1508 transnr, tonr, to->trans[transnr].to);
Daniel Veillard4255d502002-04-16 15:50:10 +00001509#endif
Daniel Veillardb509f152002-04-17 16:28:10 +00001510 if (to->trans[transnr].counter >= 0) {
1511 xmlFAReduceEpsilonTransitions(ctxt, fromnr,
1512 to->trans[transnr].to,
1513 to->trans[transnr].counter);
1514 } else {
1515 xmlFAReduceEpsilonTransitions(ctxt, fromnr,
1516 to->trans[transnr].to,
1517 counter);
1518 }
1519 }
Daniel Veillard4255d502002-04-16 15:50:10 +00001520 }
1521 } else {
1522 int newto = to->trans[transnr].to;
1523
Daniel Veillardb509f152002-04-17 16:28:10 +00001524 if (to->trans[transnr].counter >= 0) {
1525 xmlRegStateAddTrans(ctxt, from, to->trans[transnr].atom,
1526 ctxt->states[newto],
1527 to->trans[transnr].counter, -1);
1528 } else {
1529 xmlRegStateAddTrans(ctxt, from, to->trans[transnr].atom,
1530 ctxt->states[newto], counter, -1);
1531 }
Daniel Veillard4255d502002-04-16 15:50:10 +00001532 }
1533 }
1534 to->mark = XML_REGEXP_MARK_NORMAL;
1535}
1536
1537/**
1538 * xmlFAEliminateEpsilonTransitions:
Daniel Veillard441bc322002-04-20 17:38:48 +00001539 * @ctxt: a regexp parser context
Daniel Veillard4255d502002-04-16 15:50:10 +00001540 *
1541 */
1542static void
1543xmlFAEliminateEpsilonTransitions(xmlRegParserCtxtPtr ctxt) {
1544 int statenr, transnr;
1545 xmlRegStatePtr state;
1546
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00001547 if (ctxt->states == NULL) return;
1548
1549
Daniel Veillard4255d502002-04-16 15:50:10 +00001550 /*
1551 * build the completed transitions bypassing the epsilons
1552 * Use a marking algorithm to avoid loops
1553 */
1554 for (statenr = 0;statenr < ctxt->nbStates;statenr++) {
1555 state = ctxt->states[statenr];
1556 if (state == NULL)
1557 continue;
1558 for (transnr = 0;transnr < state->nbTrans;transnr++) {
1559 if ((state->trans[transnr].atom == NULL) &&
1560 (state->trans[transnr].to >= 0)) {
1561 if (state->trans[transnr].to == statenr) {
1562 state->trans[transnr].to = -1;
1563#ifdef DEBUG_REGEXP_GRAPH
1564 printf("Removed loopback epsilon trans %d on %d\n",
1565 transnr, statenr);
1566#endif
1567 } else if (state->trans[transnr].count < 0) {
1568 int newto = state->trans[transnr].to;
1569
1570#ifdef DEBUG_REGEXP_GRAPH
1571 printf("Found epsilon trans %d from %d to %d\n",
1572 transnr, statenr, newto);
1573#endif
1574 state->mark = XML_REGEXP_MARK_START;
1575 xmlFAReduceEpsilonTransitions(ctxt, statenr,
1576 newto, state->trans[transnr].counter);
1577 state->mark = XML_REGEXP_MARK_NORMAL;
1578#ifdef DEBUG_REGEXP_GRAPH
1579 } else {
1580 printf("Found counted transition %d on %d\n",
1581 transnr, statenr);
1582#endif
1583 }
1584 }
1585 }
1586 }
1587 /*
1588 * Eliminate the epsilon transitions
1589 */
1590 for (statenr = 0;statenr < ctxt->nbStates;statenr++) {
1591 state = ctxt->states[statenr];
1592 if (state == NULL)
1593 continue;
1594 for (transnr = 0;transnr < state->nbTrans;transnr++) {
1595 if ((state->trans[transnr].atom == NULL) &&
1596 (state->trans[transnr].count < 0) &&
1597 (state->trans[transnr].to >= 0)) {
1598 state->trans[transnr].to = -1;
1599 }
1600 }
1601 }
Daniel Veillard23e73572002-09-19 19:56:43 +00001602
1603 /*
1604 * Use this pass to detect unreachable states too
1605 */
1606 for (statenr = 0;statenr < ctxt->nbStates;statenr++) {
1607 state = ctxt->states[statenr];
1608 if (state != NULL)
William M. Brack779af002003-08-01 15:55:39 +00001609 state->reached = XML_REGEXP_MARK_NORMAL;
Daniel Veillard23e73572002-09-19 19:56:43 +00001610 }
1611 state = ctxt->states[0];
1612 if (state != NULL)
William M. Brack779af002003-08-01 15:55:39 +00001613 state->reached = XML_REGEXP_MARK_START;
Daniel Veillard23e73572002-09-19 19:56:43 +00001614 while (state != NULL) {
1615 xmlRegStatePtr target = NULL;
William M. Brack779af002003-08-01 15:55:39 +00001616 state->reached = XML_REGEXP_MARK_VISITED;
Daniel Veillard23e73572002-09-19 19:56:43 +00001617 /*
1618 * Mark all state reachable from the current reachable state
1619 */
1620 for (transnr = 0;transnr < state->nbTrans;transnr++) {
1621 if ((state->trans[transnr].to >= 0) &&
1622 ((state->trans[transnr].atom != NULL) ||
1623 (state->trans[transnr].count >= 0))) {
1624 int newto = state->trans[transnr].to;
1625
1626 if (ctxt->states[newto] == NULL)
1627 continue;
William M. Brack779af002003-08-01 15:55:39 +00001628 if (ctxt->states[newto]->reached == XML_REGEXP_MARK_NORMAL) {
1629 ctxt->states[newto]->reached = XML_REGEXP_MARK_START;
Daniel Veillard23e73572002-09-19 19:56:43 +00001630 target = ctxt->states[newto];
1631 }
1632 }
1633 }
1634 /*
1635 * find the next accessible state not explored
1636 */
1637 if (target == NULL) {
1638 for (statenr = 1;statenr < ctxt->nbStates;statenr++) {
1639 state = ctxt->states[statenr];
William M. Brack779af002003-08-01 15:55:39 +00001640 if ((state != NULL) && (state->reached ==
1641 XML_REGEXP_MARK_START)) {
Daniel Veillard23e73572002-09-19 19:56:43 +00001642 target = state;
1643 break;
1644 }
1645 }
1646 }
1647 state = target;
1648 }
1649 for (statenr = 0;statenr < ctxt->nbStates;statenr++) {
1650 state = ctxt->states[statenr];
William M. Brack779af002003-08-01 15:55:39 +00001651 if ((state != NULL) && (state->reached == XML_REGEXP_MARK_NORMAL)) {
Daniel Veillard23e73572002-09-19 19:56:43 +00001652#ifdef DEBUG_REGEXP_GRAPH
1653 printf("Removed unreachable state %d\n", statenr);
1654#endif
1655 xmlRegFreeState(state);
1656 ctxt->states[statenr] = NULL;
1657 }
1658 }
1659
Daniel Veillard4255d502002-04-16 15:50:10 +00001660}
1661
Daniel Veillarde19fc232002-04-22 16:01:24 +00001662/**
1663 * xmlFACompareAtoms:
1664 * @atom1: an atom
1665 * @atom2: an atom
1666 *
1667 * Compares two atoms to check whether they are equivatents
1668 *
1669 * Returns 1 if yes and 0 otherwise
1670 */
1671static int
1672xmlFACompareAtoms(xmlRegAtomPtr atom1, xmlRegAtomPtr atom2) {
1673 if (atom1 == atom2)
1674 return(1);
1675 if ((atom1 == NULL) || (atom2 == NULL))
1676 return(0);
1677
1678 if (atom1->type != atom2->type)
1679 return(0);
1680 switch (atom1->type) {
1681 case XML_REGEXP_STRING:
1682 return(xmlStrEqual((xmlChar *)atom1->valuep,
1683 (xmlChar *)atom2->valuep));
1684 case XML_REGEXP_EPSILON:
1685 return(1);
1686 case XML_REGEXP_CHARVAL:
1687 return(atom1->codepoint == atom2->codepoint);
1688 case XML_REGEXP_RANGES:
1689 TODO;
1690 return(0);
1691 default:
1692 break;
1693 }
1694 return(1);
1695}
1696
1697/**
1698 * xmlFARecurseDeterminism:
1699 * @ctxt: a regexp parser context
1700 *
1701 * Check whether the associated regexp is determinist,
1702 * should be called after xmlFAEliminateEpsilonTransitions()
1703 *
1704 */
1705static int
1706xmlFARecurseDeterminism(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr state,
1707 int to, xmlRegAtomPtr atom) {
1708 int ret = 1;
1709 int transnr;
1710 xmlRegTransPtr t1;
1711
1712 if (state == NULL)
1713 return(ret);
1714 for (transnr = 0;transnr < state->nbTrans;transnr++) {
1715 t1 = &(state->trans[transnr]);
1716 /*
1717 * check transitions conflicting with the one looked at
1718 */
1719 if (t1->atom == NULL) {
1720 if (t1->to == -1)
1721 continue;
1722 ret = xmlFARecurseDeterminism(ctxt, ctxt->states[t1->to],
1723 to, atom);
1724 if (ret == 0)
1725 return(0);
1726 continue;
1727 }
1728 if (t1->to != to)
1729 continue;
1730 if (xmlFACompareAtoms(t1->atom, atom))
1731 return(0);
1732 }
1733 return(ret);
1734}
1735
1736/**
1737 * xmlFAComputesDeterminism:
1738 * @ctxt: a regexp parser context
1739 *
1740 * Check whether the associated regexp is determinist,
1741 * should be called after xmlFAEliminateEpsilonTransitions()
1742 *
1743 */
1744static int
1745xmlFAComputesDeterminism(xmlRegParserCtxtPtr ctxt) {
1746 int statenr, transnr;
1747 xmlRegStatePtr state;
1748 xmlRegTransPtr t1, t2;
1749 int i;
1750 int ret = 1;
1751
Daniel Veillard4402ab42002-09-12 16:02:56 +00001752#ifdef DEBUG_REGEXP_GRAPH
1753 printf("xmlFAComputesDeterminism\n");
1754 xmlRegPrintCtxt(stdout, ctxt);
1755#endif
Daniel Veillarde19fc232002-04-22 16:01:24 +00001756 if (ctxt->determinist != -1)
1757 return(ctxt->determinist);
1758
1759 /*
1760 * Check for all states that there isn't 2 transitions
1761 * with the same atom and a different target.
1762 */
1763 for (statenr = 0;statenr < ctxt->nbStates;statenr++) {
1764 state = ctxt->states[statenr];
1765 if (state == NULL)
1766 continue;
1767 for (transnr = 0;transnr < state->nbTrans;transnr++) {
1768 t1 = &(state->trans[transnr]);
1769 /*
1770 * Determinism checks in case of counted or all transitions
1771 * will have to be handled separately
1772 */
1773 if (t1->atom == NULL)
1774 continue;
1775 if (t1->to == -1) /* eliminated */
1776 continue;
1777 for (i = 0;i < transnr;i++) {
1778 t2 = &(state->trans[i]);
1779 if (t2->to == -1) /* eliminated */
1780 continue;
1781 if (t2->atom != NULL) {
1782 if (t1->to == t2->to) {
1783 if (xmlFACompareAtoms(t1->atom, t2->atom))
1784 t2->to = -1; /* eliminate */
1785 } else {
1786 /* not determinist ! */
1787 if (xmlFACompareAtoms(t1->atom, t2->atom))
1788 ret = 0;
1789 }
1790 } else if (t1->to != -1) {
1791 /*
1792 * do the closure in case of remaining specific
1793 * epsilon transitions like choices or all
1794 */
1795 ret = xmlFARecurseDeterminism(ctxt, ctxt->states[t1->to],
1796 t2->to, t2->atom);
1797 if (ret == 0)
1798 return(0);
1799 }
1800 }
1801 if (ret == 0)
1802 break;
1803 }
1804 if (ret == 0)
1805 break;
1806 }
1807 ctxt->determinist = ret;
1808 return(ret);
1809}
1810
Daniel Veillard4255d502002-04-16 15:50:10 +00001811/************************************************************************
1812 * *
1813 * Routines to check input against transition atoms *
1814 * *
1815 ************************************************************************/
1816
1817static int
1818xmlRegCheckCharacterRange(xmlRegAtomType type, int codepoint, int neg,
1819 int start, int end, const xmlChar *blockName) {
1820 int ret = 0;
1821
1822 switch (type) {
1823 case XML_REGEXP_STRING:
1824 case XML_REGEXP_SUBREG:
1825 case XML_REGEXP_RANGES:
1826 case XML_REGEXP_EPSILON:
1827 return(-1);
1828 case XML_REGEXP_ANYCHAR:
1829 ret = ((codepoint != '\n') && (codepoint != '\r'));
1830 break;
1831 case XML_REGEXP_CHARVAL:
1832 ret = ((codepoint >= start) && (codepoint <= end));
1833 break;
1834 case XML_REGEXP_NOTSPACE:
1835 neg = !neg;
1836 case XML_REGEXP_ANYSPACE:
1837 ret = ((codepoint == '\n') || (codepoint == '\r') ||
1838 (codepoint == '\t') || (codepoint == ' '));
1839 break;
1840 case XML_REGEXP_NOTINITNAME:
1841 neg = !neg;
1842 case XML_REGEXP_INITNAME:
William M. Brack871611b2003-10-18 04:53:14 +00001843 ret = (IS_LETTER(codepoint) ||
Daniel Veillard4255d502002-04-16 15:50:10 +00001844 (codepoint == '_') || (codepoint == ':'));
1845 break;
1846 case XML_REGEXP_NOTNAMECHAR:
1847 neg = !neg;
1848 case XML_REGEXP_NAMECHAR:
William M. Brack871611b2003-10-18 04:53:14 +00001849 ret = (IS_LETTER(codepoint) || IS_DIGIT(codepoint) ||
Daniel Veillard4255d502002-04-16 15:50:10 +00001850 (codepoint == '.') || (codepoint == '-') ||
1851 (codepoint == '_') || (codepoint == ':') ||
William M. Brack871611b2003-10-18 04:53:14 +00001852 IS_COMBINING(codepoint) || IS_EXTENDER(codepoint));
Daniel Veillard4255d502002-04-16 15:50:10 +00001853 break;
1854 case XML_REGEXP_NOTDECIMAL:
1855 neg = !neg;
1856 case XML_REGEXP_DECIMAL:
1857 ret = xmlUCSIsCatNd(codepoint);
1858 break;
1859 case XML_REGEXP_REALCHAR:
1860 neg = !neg;
1861 case XML_REGEXP_NOTREALCHAR:
1862 ret = xmlUCSIsCatP(codepoint);
1863 if (ret == 0)
1864 ret = xmlUCSIsCatZ(codepoint);
1865 if (ret == 0)
1866 ret = xmlUCSIsCatC(codepoint);
1867 break;
1868 case XML_REGEXP_LETTER:
1869 ret = xmlUCSIsCatL(codepoint);
1870 break;
1871 case XML_REGEXP_LETTER_UPPERCASE:
1872 ret = xmlUCSIsCatLu(codepoint);
1873 break;
1874 case XML_REGEXP_LETTER_LOWERCASE:
1875 ret = xmlUCSIsCatLl(codepoint);
1876 break;
1877 case XML_REGEXP_LETTER_TITLECASE:
1878 ret = xmlUCSIsCatLt(codepoint);
1879 break;
1880 case XML_REGEXP_LETTER_MODIFIER:
1881 ret = xmlUCSIsCatLm(codepoint);
1882 break;
1883 case XML_REGEXP_LETTER_OTHERS:
1884 ret = xmlUCSIsCatLo(codepoint);
1885 break;
1886 case XML_REGEXP_MARK:
1887 ret = xmlUCSIsCatM(codepoint);
1888 break;
1889 case XML_REGEXP_MARK_NONSPACING:
1890 ret = xmlUCSIsCatMn(codepoint);
1891 break;
1892 case XML_REGEXP_MARK_SPACECOMBINING:
1893 ret = xmlUCSIsCatMc(codepoint);
1894 break;
1895 case XML_REGEXP_MARK_ENCLOSING:
1896 ret = xmlUCSIsCatMe(codepoint);
1897 break;
1898 case XML_REGEXP_NUMBER:
1899 ret = xmlUCSIsCatN(codepoint);
1900 break;
1901 case XML_REGEXP_NUMBER_DECIMAL:
1902 ret = xmlUCSIsCatNd(codepoint);
1903 break;
1904 case XML_REGEXP_NUMBER_LETTER:
1905 ret = xmlUCSIsCatNl(codepoint);
1906 break;
1907 case XML_REGEXP_NUMBER_OTHERS:
1908 ret = xmlUCSIsCatNo(codepoint);
1909 break;
1910 case XML_REGEXP_PUNCT:
1911 ret = xmlUCSIsCatP(codepoint);
1912 break;
1913 case XML_REGEXP_PUNCT_CONNECTOR:
1914 ret = xmlUCSIsCatPc(codepoint);
1915 break;
1916 case XML_REGEXP_PUNCT_DASH:
1917 ret = xmlUCSIsCatPd(codepoint);
1918 break;
1919 case XML_REGEXP_PUNCT_OPEN:
1920 ret = xmlUCSIsCatPs(codepoint);
1921 break;
1922 case XML_REGEXP_PUNCT_CLOSE:
1923 ret = xmlUCSIsCatPe(codepoint);
1924 break;
1925 case XML_REGEXP_PUNCT_INITQUOTE:
1926 ret = xmlUCSIsCatPi(codepoint);
1927 break;
1928 case XML_REGEXP_PUNCT_FINQUOTE:
1929 ret = xmlUCSIsCatPf(codepoint);
1930 break;
1931 case XML_REGEXP_PUNCT_OTHERS:
1932 ret = xmlUCSIsCatPo(codepoint);
1933 break;
1934 case XML_REGEXP_SEPAR:
1935 ret = xmlUCSIsCatZ(codepoint);
1936 break;
1937 case XML_REGEXP_SEPAR_SPACE:
1938 ret = xmlUCSIsCatZs(codepoint);
1939 break;
1940 case XML_REGEXP_SEPAR_LINE:
1941 ret = xmlUCSIsCatZl(codepoint);
1942 break;
1943 case XML_REGEXP_SEPAR_PARA:
1944 ret = xmlUCSIsCatZp(codepoint);
1945 break;
1946 case XML_REGEXP_SYMBOL:
1947 ret = xmlUCSIsCatS(codepoint);
1948 break;
1949 case XML_REGEXP_SYMBOL_MATH:
1950 ret = xmlUCSIsCatSm(codepoint);
1951 break;
1952 case XML_REGEXP_SYMBOL_CURRENCY:
1953 ret = xmlUCSIsCatSc(codepoint);
1954 break;
1955 case XML_REGEXP_SYMBOL_MODIFIER:
1956 ret = xmlUCSIsCatSk(codepoint);
1957 break;
1958 case XML_REGEXP_SYMBOL_OTHERS:
1959 ret = xmlUCSIsCatSo(codepoint);
1960 break;
1961 case XML_REGEXP_OTHER:
1962 ret = xmlUCSIsCatC(codepoint);
1963 break;
1964 case XML_REGEXP_OTHER_CONTROL:
1965 ret = xmlUCSIsCatCc(codepoint);
1966 break;
1967 case XML_REGEXP_OTHER_FORMAT:
1968 ret = xmlUCSIsCatCf(codepoint);
1969 break;
1970 case XML_REGEXP_OTHER_PRIVATE:
1971 ret = xmlUCSIsCatCo(codepoint);
1972 break;
1973 case XML_REGEXP_OTHER_NA:
1974 /* ret = xmlUCSIsCatCn(codepoint); */
1975 /* Seems it doesn't exist anymore in recent Unicode releases */
1976 ret = 0;
1977 break;
1978 case XML_REGEXP_BLOCK_NAME:
1979 ret = xmlUCSIsBlock(codepoint, (const char *) blockName);
1980 break;
1981 }
1982 if (neg)
1983 return(!ret);
1984 return(ret);
1985}
1986
1987static int
1988xmlRegCheckCharacter(xmlRegAtomPtr atom, int codepoint) {
1989 int i, ret = 0;
1990 xmlRegRangePtr range;
1991
William M. Brack871611b2003-10-18 04:53:14 +00001992 if ((atom == NULL) || (!IS_CHAR(codepoint)))
Daniel Veillard4255d502002-04-16 15:50:10 +00001993 return(-1);
1994
1995 switch (atom->type) {
1996 case XML_REGEXP_SUBREG:
1997 case XML_REGEXP_EPSILON:
1998 return(-1);
1999 case XML_REGEXP_CHARVAL:
2000 return(codepoint == atom->codepoint);
2001 case XML_REGEXP_RANGES: {
2002 int accept = 0;
Daniel Veillardf2a12832003-11-24 13:04:35 +00002003
Daniel Veillard4255d502002-04-16 15:50:10 +00002004 for (i = 0;i < atom->nbRanges;i++) {
2005 range = atom->ranges[i];
Daniel Veillardf8b9de32003-11-24 14:27:26 +00002006 if (range->neg == 2) {
Daniel Veillard4255d502002-04-16 15:50:10 +00002007 ret = xmlRegCheckCharacterRange(range->type, codepoint,
2008 0, range->start, range->end,
2009 range->blockName);
2010 if (ret != 0)
2011 return(0); /* excluded char */
Daniel Veillardf8b9de32003-11-24 14:27:26 +00002012 } else if (range->neg) {
2013 ret = xmlRegCheckCharacterRange(range->type, codepoint,
2014 0, range->start, range->end,
2015 range->blockName);
2016 if (ret == 0)
Daniel Veillardf2a12832003-11-24 13:04:35 +00002017 accept = 1;
Daniel Veillardf8b9de32003-11-24 14:27:26 +00002018 else
2019 return(0);
Daniel Veillard4255d502002-04-16 15:50:10 +00002020 } else {
2021 ret = xmlRegCheckCharacterRange(range->type, codepoint,
2022 0, range->start, range->end,
2023 range->blockName);
2024 if (ret != 0)
2025 accept = 1; /* might still be excluded */
2026 }
2027 }
2028 return(accept);
2029 }
2030 case XML_REGEXP_STRING:
2031 printf("TODO: XML_REGEXP_STRING\n");
2032 return(-1);
2033 case XML_REGEXP_ANYCHAR:
2034 case XML_REGEXP_ANYSPACE:
2035 case XML_REGEXP_NOTSPACE:
2036 case XML_REGEXP_INITNAME:
2037 case XML_REGEXP_NOTINITNAME:
2038 case XML_REGEXP_NAMECHAR:
2039 case XML_REGEXP_NOTNAMECHAR:
2040 case XML_REGEXP_DECIMAL:
2041 case XML_REGEXP_NOTDECIMAL:
2042 case XML_REGEXP_REALCHAR:
2043 case XML_REGEXP_NOTREALCHAR:
2044 case XML_REGEXP_LETTER:
2045 case XML_REGEXP_LETTER_UPPERCASE:
2046 case XML_REGEXP_LETTER_LOWERCASE:
2047 case XML_REGEXP_LETTER_TITLECASE:
2048 case XML_REGEXP_LETTER_MODIFIER:
2049 case XML_REGEXP_LETTER_OTHERS:
2050 case XML_REGEXP_MARK:
2051 case XML_REGEXP_MARK_NONSPACING:
2052 case XML_REGEXP_MARK_SPACECOMBINING:
2053 case XML_REGEXP_MARK_ENCLOSING:
2054 case XML_REGEXP_NUMBER:
2055 case XML_REGEXP_NUMBER_DECIMAL:
2056 case XML_REGEXP_NUMBER_LETTER:
2057 case XML_REGEXP_NUMBER_OTHERS:
2058 case XML_REGEXP_PUNCT:
2059 case XML_REGEXP_PUNCT_CONNECTOR:
2060 case XML_REGEXP_PUNCT_DASH:
2061 case XML_REGEXP_PUNCT_OPEN:
2062 case XML_REGEXP_PUNCT_CLOSE:
2063 case XML_REGEXP_PUNCT_INITQUOTE:
2064 case XML_REGEXP_PUNCT_FINQUOTE:
2065 case XML_REGEXP_PUNCT_OTHERS:
2066 case XML_REGEXP_SEPAR:
2067 case XML_REGEXP_SEPAR_SPACE:
2068 case XML_REGEXP_SEPAR_LINE:
2069 case XML_REGEXP_SEPAR_PARA:
2070 case XML_REGEXP_SYMBOL:
2071 case XML_REGEXP_SYMBOL_MATH:
2072 case XML_REGEXP_SYMBOL_CURRENCY:
2073 case XML_REGEXP_SYMBOL_MODIFIER:
2074 case XML_REGEXP_SYMBOL_OTHERS:
2075 case XML_REGEXP_OTHER:
2076 case XML_REGEXP_OTHER_CONTROL:
2077 case XML_REGEXP_OTHER_FORMAT:
2078 case XML_REGEXP_OTHER_PRIVATE:
2079 case XML_REGEXP_OTHER_NA:
2080 case XML_REGEXP_BLOCK_NAME:
2081 ret = xmlRegCheckCharacterRange(atom->type, codepoint, 0, 0, 0,
2082 (const xmlChar *)atom->valuep);
2083 if (atom->neg)
2084 ret = !ret;
2085 break;
2086 }
2087 return(ret);
2088}
2089
2090/************************************************************************
2091 * *
2092 * Saving an restoring state of an execution context *
2093 * *
2094 ************************************************************************/
2095
2096#ifdef DEBUG_REGEXP_EXEC
2097static void
2098xmlFARegDebugExec(xmlRegExecCtxtPtr exec) {
2099 printf("state: %d:%d:idx %d", exec->state->no, exec->transno, exec->index);
2100 if (exec->inputStack != NULL) {
2101 int i;
2102 printf(": ");
2103 for (i = 0;(i < 3) && (i < exec->inputStackNr);i++)
2104 printf("%s ", exec->inputStack[exec->inputStackNr - (i + 1)]);
2105 } else {
2106 printf(": %s", &(exec->inputString[exec->index]));
2107 }
2108 printf("\n");
2109}
2110#endif
2111
2112static void
2113xmlFARegExecSave(xmlRegExecCtxtPtr exec) {
2114#ifdef DEBUG_REGEXP_EXEC
2115 printf("saving ");
2116 exec->transno++;
2117 xmlFARegDebugExec(exec);
2118 exec->transno--;
2119#endif
2120
2121 if (exec->maxRollbacks == 0) {
2122 exec->maxRollbacks = 4;
2123 exec->rollbacks = (xmlRegExecRollback *) xmlMalloc(exec->maxRollbacks *
2124 sizeof(xmlRegExecRollback));
2125 if (exec->rollbacks == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +00002126 xmlRegexpErrMemory(NULL, "saving regexp");
Daniel Veillard4255d502002-04-16 15:50:10 +00002127 exec->maxRollbacks = 0;
2128 return;
2129 }
2130 memset(exec->rollbacks, 0,
2131 exec->maxRollbacks * sizeof(xmlRegExecRollback));
2132 } else if (exec->nbRollbacks >= exec->maxRollbacks) {
2133 xmlRegExecRollback *tmp;
2134 int len = exec->maxRollbacks;
2135
2136 exec->maxRollbacks *= 2;
2137 tmp = (xmlRegExecRollback *) xmlRealloc(exec->rollbacks,
2138 exec->maxRollbacks * sizeof(xmlRegExecRollback));
2139 if (tmp == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +00002140 xmlRegexpErrMemory(NULL, "saving regexp");
Daniel Veillard4255d502002-04-16 15:50:10 +00002141 exec->maxRollbacks /= 2;
2142 return;
2143 }
2144 exec->rollbacks = tmp;
2145 tmp = &exec->rollbacks[len];
2146 memset(tmp, 0, (exec->maxRollbacks - len) * sizeof(xmlRegExecRollback));
2147 }
2148 exec->rollbacks[exec->nbRollbacks].state = exec->state;
2149 exec->rollbacks[exec->nbRollbacks].index = exec->index;
2150 exec->rollbacks[exec->nbRollbacks].nextbranch = exec->transno + 1;
2151 if (exec->comp->nbCounters > 0) {
2152 if (exec->rollbacks[exec->nbRollbacks].counts == NULL) {
2153 exec->rollbacks[exec->nbRollbacks].counts = (int *)
2154 xmlMalloc(exec->comp->nbCounters * sizeof(int));
2155 if (exec->rollbacks[exec->nbRollbacks].counts == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +00002156 xmlRegexpErrMemory(NULL, "saving regexp");
Daniel Veillard4255d502002-04-16 15:50:10 +00002157 exec->status = -5;
2158 return;
2159 }
2160 }
2161 memcpy(exec->rollbacks[exec->nbRollbacks].counts, exec->counts,
2162 exec->comp->nbCounters * sizeof(int));
2163 }
2164 exec->nbRollbacks++;
2165}
2166
2167static void
2168xmlFARegExecRollBack(xmlRegExecCtxtPtr exec) {
2169 if (exec->nbRollbacks <= 0) {
2170 exec->status = -1;
2171#ifdef DEBUG_REGEXP_EXEC
2172 printf("rollback failed on empty stack\n");
2173#endif
2174 return;
2175 }
2176 exec->nbRollbacks--;
2177 exec->state = exec->rollbacks[exec->nbRollbacks].state;
2178 exec->index = exec->rollbacks[exec->nbRollbacks].index;
2179 exec->transno = exec->rollbacks[exec->nbRollbacks].nextbranch;
2180 if (exec->comp->nbCounters > 0) {
2181 if (exec->rollbacks[exec->nbRollbacks].counts == NULL) {
2182 fprintf(stderr, "exec save: allocation failed");
2183 exec->status = -6;
2184 return;
2185 }
2186 memcpy(exec->counts, exec->rollbacks[exec->nbRollbacks].counts,
2187 exec->comp->nbCounters * sizeof(int));
2188 }
2189
2190#ifdef DEBUG_REGEXP_EXEC
2191 printf("restored ");
2192 xmlFARegDebugExec(exec);
2193#endif
2194}
2195
2196/************************************************************************
2197 * *
2198 * Verifyer, running an input against a compiled regexp *
2199 * *
2200 ************************************************************************/
2201
2202static int
2203xmlFARegExec(xmlRegexpPtr comp, const xmlChar *content) {
2204 xmlRegExecCtxt execval;
2205 xmlRegExecCtxtPtr exec = &execval;
2206 int ret, codepoint, len;
2207
2208 exec->inputString = content;
2209 exec->index = 0;
2210 exec->determinist = 1;
2211 exec->maxRollbacks = 0;
2212 exec->nbRollbacks = 0;
2213 exec->rollbacks = NULL;
2214 exec->status = 0;
2215 exec->comp = comp;
2216 exec->state = comp->states[0];
2217 exec->transno = 0;
2218 exec->transcount = 0;
Daniel Veillardf2a12832003-11-24 13:04:35 +00002219 exec->inputStack = NULL;
2220 exec->inputStackMax = 0;
Daniel Veillard4255d502002-04-16 15:50:10 +00002221 if (comp->nbCounters > 0) {
2222 exec->counts = (int *) xmlMalloc(comp->nbCounters * sizeof(int));
Daniel Veillardff46a042003-10-08 08:53:17 +00002223 if (exec->counts == NULL) {
2224 xmlRegexpErrMemory(NULL, "running regexp");
Daniel Veillard4255d502002-04-16 15:50:10 +00002225 return(-1);
Daniel Veillardff46a042003-10-08 08:53:17 +00002226 }
Daniel Veillard4255d502002-04-16 15:50:10 +00002227 memset(exec->counts, 0, comp->nbCounters * sizeof(int));
2228 } else
2229 exec->counts = NULL;
2230 while ((exec->status == 0) &&
2231 ((exec->inputString[exec->index] != 0) ||
2232 (exec->state->type != XML_REGEXP_FINAL_STATE))) {
2233 xmlRegTransPtr trans;
2234 xmlRegAtomPtr atom;
2235
2236 /*
2237 * End of input on non-terminal state, rollback, however we may
2238 * still have epsilon like transition for counted transitions
2239 * on counters, in that case don't break too early.
2240 */
2241 if ((exec->inputString[exec->index] == 0) && (exec->counts == NULL))
2242 goto rollback;
2243
2244 exec->transcount = 0;
2245 for (;exec->transno < exec->state->nbTrans;exec->transno++) {
2246 trans = &exec->state->trans[exec->transno];
2247 if (trans->to < 0)
2248 continue;
2249 atom = trans->atom;
2250 ret = 0;
2251 if (trans->count >= 0) {
2252 int count;
2253 xmlRegCounterPtr counter;
2254
2255 /*
2256 * A counted transition.
2257 */
2258
2259 count = exec->counts[trans->count];
2260 counter = &exec->comp->counters[trans->count];
2261#ifdef DEBUG_REGEXP_EXEC
2262 printf("testing count %d: val %d, min %d, max %d\n",
2263 trans->count, count, counter->min, counter->max);
2264#endif
2265 ret = ((count >= counter->min) && (count <= counter->max));
2266 } else if (atom == NULL) {
2267 fprintf(stderr, "epsilon transition left at runtime\n");
2268 exec->status = -2;
2269 break;
2270 } else if (exec->inputString[exec->index] != 0) {
2271 codepoint = CUR_SCHAR(&(exec->inputString[exec->index]), len);
2272 ret = xmlRegCheckCharacter(atom, codepoint);
2273 if ((ret == 1) && (atom->min > 0) && (atom->max > 0)) {
2274 xmlRegStatePtr to = comp->states[trans->to];
2275
2276 /*
2277 * this is a multiple input sequence
2278 */
2279 if (exec->state->nbTrans > exec->transno + 1) {
2280 xmlFARegExecSave(exec);
2281 }
2282 exec->transcount = 1;
2283 do {
2284 /*
2285 * Try to progress as much as possible on the input
2286 */
2287 if (exec->transcount == atom->max) {
2288 break;
2289 }
2290 exec->index += len;
2291 /*
2292 * End of input: stop here
2293 */
2294 if (exec->inputString[exec->index] == 0) {
2295 exec->index -= len;
2296 break;
2297 }
2298 if (exec->transcount >= atom->min) {
2299 int transno = exec->transno;
2300 xmlRegStatePtr state = exec->state;
2301
2302 /*
2303 * The transition is acceptable save it
2304 */
2305 exec->transno = -1; /* trick */
2306 exec->state = to;
2307 xmlFARegExecSave(exec);
2308 exec->transno = transno;
2309 exec->state = state;
2310 }
2311 codepoint = CUR_SCHAR(&(exec->inputString[exec->index]),
2312 len);
2313 ret = xmlRegCheckCharacter(atom, codepoint);
2314 exec->transcount++;
2315 } while (ret == 1);
2316 if (exec->transcount < atom->min)
2317 ret = 0;
2318
2319 /*
2320 * If the last check failed but one transition was found
2321 * possible, rollback
2322 */
2323 if (ret < 0)
2324 ret = 0;
2325 if (ret == 0) {
2326 goto rollback;
2327 }
2328 }
2329 }
2330 if (ret == 1) {
2331 if (exec->state->nbTrans > exec->transno + 1) {
2332 xmlFARegExecSave(exec);
2333 }
2334 if (trans->counter >= 0) {
2335#ifdef DEBUG_REGEXP_EXEC
2336 printf("Increasing count %d\n", trans->counter);
2337#endif
2338 exec->counts[trans->counter]++;
2339 }
2340#ifdef DEBUG_REGEXP_EXEC
2341 printf("entering state %d\n", trans->to);
2342#endif
2343 exec->state = comp->states[trans->to];
2344 exec->transno = 0;
2345 if (trans->atom != NULL) {
2346 exec->index += len;
2347 }
2348 goto progress;
2349 } else if (ret < 0) {
2350 exec->status = -4;
2351 break;
2352 }
2353 }
2354 if ((exec->transno != 0) || (exec->state->nbTrans == 0)) {
2355rollback:
2356 /*
2357 * Failed to find a way out
2358 */
2359 exec->determinist = 0;
2360 xmlFARegExecRollBack(exec);
2361 }
2362progress:
2363 continue;
2364 }
2365 if (exec->rollbacks != NULL) {
2366 if (exec->counts != NULL) {
2367 int i;
2368
2369 for (i = 0;i < exec->maxRollbacks;i++)
2370 if (exec->rollbacks[i].counts != NULL)
2371 xmlFree(exec->rollbacks[i].counts);
2372 }
2373 xmlFree(exec->rollbacks);
2374 }
2375 if (exec->counts != NULL)
2376 xmlFree(exec->counts);
2377 if (exec->status == 0)
2378 return(1);
2379 if (exec->status == -1)
2380 return(0);
2381 return(exec->status);
2382}
2383
2384/************************************************************************
2385 * *
2386 * Progressive interface to the verifyer one atom at a time *
2387 * *
2388 ************************************************************************/
2389
2390/**
Daniel Veillard01c13b52002-12-10 15:19:08 +00002391 * xmlRegNewExecCtxt:
Daniel Veillard4255d502002-04-16 15:50:10 +00002392 * @comp: a precompiled regular expression
2393 * @callback: a callback function used for handling progresses in the
2394 * automata matching phase
2395 * @data: the context data associated to the callback in this context
2396 *
2397 * Build a context used for progressive evaluation of a regexp.
Daniel Veillard01c13b52002-12-10 15:19:08 +00002398 *
2399 * Returns the new context
Daniel Veillard4255d502002-04-16 15:50:10 +00002400 */
2401xmlRegExecCtxtPtr
2402xmlRegNewExecCtxt(xmlRegexpPtr comp, xmlRegExecCallbacks callback, void *data) {
2403 xmlRegExecCtxtPtr exec;
2404
2405 if (comp == NULL)
2406 return(NULL);
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00002407 if ((comp->compact == NULL) && (comp->states == NULL))
2408 return(NULL);
Daniel Veillard4255d502002-04-16 15:50:10 +00002409 exec = (xmlRegExecCtxtPtr) xmlMalloc(sizeof(xmlRegExecCtxt));
2410 if (exec == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +00002411 xmlRegexpErrMemory(NULL, "creating execution context");
Daniel Veillard4255d502002-04-16 15:50:10 +00002412 return(NULL);
2413 }
2414 memset(exec, 0, sizeof(xmlRegExecCtxt));
2415 exec->inputString = NULL;
2416 exec->index = 0;
2417 exec->determinist = 1;
2418 exec->maxRollbacks = 0;
2419 exec->nbRollbacks = 0;
2420 exec->rollbacks = NULL;
2421 exec->status = 0;
2422 exec->comp = comp;
Daniel Veillard23e73572002-09-19 19:56:43 +00002423 if (comp->compact == NULL)
2424 exec->state = comp->states[0];
Daniel Veillard4255d502002-04-16 15:50:10 +00002425 exec->transno = 0;
2426 exec->transcount = 0;
2427 exec->callback = callback;
2428 exec->data = data;
2429 if (comp->nbCounters > 0) {
2430 exec->counts = (int *) xmlMalloc(comp->nbCounters * sizeof(int));
2431 if (exec->counts == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +00002432 xmlRegexpErrMemory(NULL, "creating execution context");
Daniel Veillard4255d502002-04-16 15:50:10 +00002433 xmlFree(exec);
2434 return(NULL);
2435 }
2436 memset(exec->counts, 0, comp->nbCounters * sizeof(int));
2437 } else
2438 exec->counts = NULL;
2439 exec->inputStackMax = 0;
2440 exec->inputStackNr = 0;
2441 exec->inputStack = NULL;
2442 return(exec);
2443}
2444
2445/**
2446 * xmlRegFreeExecCtxt:
2447 * @exec: a regular expression evaulation context
2448 *
2449 * Free the structures associated to a regular expression evaulation context.
2450 */
2451void
2452xmlRegFreeExecCtxt(xmlRegExecCtxtPtr exec) {
2453 if (exec == NULL)
2454 return;
2455
2456 if (exec->rollbacks != NULL) {
2457 if (exec->counts != NULL) {
2458 int i;
2459
2460 for (i = 0;i < exec->maxRollbacks;i++)
2461 if (exec->rollbacks[i].counts != NULL)
2462 xmlFree(exec->rollbacks[i].counts);
2463 }
2464 xmlFree(exec->rollbacks);
2465 }
2466 if (exec->counts != NULL)
2467 xmlFree(exec->counts);
2468 if (exec->inputStack != NULL) {
2469 int i;
2470
Daniel Veillard32370232002-10-16 14:08:14 +00002471 for (i = 0;i < exec->inputStackNr;i++) {
2472 if (exec->inputStack[i].value != NULL)
2473 xmlFree(exec->inputStack[i].value);
2474 }
Daniel Veillard4255d502002-04-16 15:50:10 +00002475 xmlFree(exec->inputStack);
2476 }
2477 xmlFree(exec);
2478}
2479
2480static void
2481xmlFARegExecSaveInputString(xmlRegExecCtxtPtr exec, const xmlChar *value,
2482 void *data) {
2483#ifdef DEBUG_PUSH
2484 printf("saving value: %d:%s\n", exec->inputStackNr, value);
2485#endif
2486 if (exec->inputStackMax == 0) {
2487 exec->inputStackMax = 4;
2488 exec->inputStack = (xmlRegInputTokenPtr)
2489 xmlMalloc(exec->inputStackMax * sizeof(xmlRegInputToken));
2490 if (exec->inputStack == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +00002491 xmlRegexpErrMemory(NULL, "pushing input string");
Daniel Veillard4255d502002-04-16 15:50:10 +00002492 exec->inputStackMax = 0;
2493 return;
2494 }
2495 } else if (exec->inputStackNr + 1 >= exec->inputStackMax) {
2496 xmlRegInputTokenPtr tmp;
2497
2498 exec->inputStackMax *= 2;
2499 tmp = (xmlRegInputTokenPtr) xmlRealloc(exec->inputStack,
2500 exec->inputStackMax * sizeof(xmlRegInputToken));
2501 if (tmp == NULL) {
Daniel Veillardff46a042003-10-08 08:53:17 +00002502 xmlRegexpErrMemory(NULL, "pushing input string");
Daniel Veillard4255d502002-04-16 15:50:10 +00002503 exec->inputStackMax /= 2;
2504 return;
2505 }
2506 exec->inputStack = tmp;
2507 }
2508 exec->inputStack[exec->inputStackNr].value = xmlStrdup(value);
2509 exec->inputStack[exec->inputStackNr].data = data;
2510 exec->inputStackNr++;
2511 exec->inputStack[exec->inputStackNr].value = NULL;
2512 exec->inputStack[exec->inputStackNr].data = NULL;
2513}
2514
2515
2516/**
Daniel Veillard23e73572002-09-19 19:56:43 +00002517 * xmlRegCompactPushString:
2518 * @exec: a regexp execution context
2519 * @comp: the precompiled exec with a compact table
2520 * @value: a string token input
2521 * @data: data associated to the token to reuse in callbacks
2522 *
2523 * Push one input token in the execution context
2524 *
2525 * Returns: 1 if the regexp reached a final state, 0 if non-final, and
2526 * a negative value in case of error.
2527 */
2528static int
2529xmlRegCompactPushString(xmlRegExecCtxtPtr exec,
2530 xmlRegexpPtr comp,
2531 const xmlChar *value,
2532 void *data) {
2533 int state = exec->index;
2534 int i, target;
2535
2536 if ((comp == NULL) || (comp->compact == NULL) || (comp->stringMap == NULL))
2537 return(-1);
2538
2539 if (value == NULL) {
2540 /*
2541 * are we at a final state ?
2542 */
2543 if (comp->compact[state * (comp->nbstrings + 1)] ==
2544 XML_REGEXP_FINAL_STATE)
2545 return(1);
2546 return(0);
2547 }
2548
2549#ifdef DEBUG_PUSH
2550 printf("value pushed: %s\n", value);
2551#endif
2552
2553 /*
2554 * Examine all outside transition from current state
2555 */
2556 for (i = 0;i < comp->nbstrings;i++) {
2557 target = comp->compact[state * (comp->nbstrings + 1) + i + 1];
2558 if ((target > 0) && (target <= comp->nbstates)) {
2559 target--; /* to avoid 0 */
2560 if (xmlStrEqual(comp->stringMap[i], value)) {
2561 exec->index = target;
Daniel Veillard118aed72002-09-24 14:13:13 +00002562 if ((exec->callback != NULL) && (comp->transdata != NULL)) {
2563 exec->callback(exec->data, value,
2564 comp->transdata[state * comp->nbstrings + i], data);
2565 }
Daniel Veillard23e73572002-09-19 19:56:43 +00002566#ifdef DEBUG_PUSH
2567 printf("entering state %d\n", target);
2568#endif
2569 if (comp->compact[target * (comp->nbstrings + 1)] ==
2570 XML_REGEXP_FINAL_STATE)
2571 return(1);
2572 return(0);
2573 }
2574 }
2575 }
2576 /*
2577 * Failed to find an exit transition out from current state for the
2578 * current token
2579 */
2580#ifdef DEBUG_PUSH
2581 printf("failed to find a transition for %s on state %d\n", value, state);
2582#endif
2583 exec->status = -1;
2584 return(-1);
2585}
2586
2587/**
Daniel Veillard4255d502002-04-16 15:50:10 +00002588 * xmlRegExecPushString:
Daniel Veillardea7751d2002-12-20 00:16:24 +00002589 * @exec: a regexp execution context or NULL to indicate the end
Daniel Veillard4255d502002-04-16 15:50:10 +00002590 * @value: a string token input
2591 * @data: data associated to the token to reuse in callbacks
2592 *
2593 * Push one input token in the execution context
2594 *
2595 * Returns: 1 if the regexp reached a final state, 0 if non-final, and
2596 * a negative value in case of error.
2597 */
2598int
2599xmlRegExecPushString(xmlRegExecCtxtPtr exec, const xmlChar *value,
2600 void *data) {
2601 xmlRegTransPtr trans;
2602 xmlRegAtomPtr atom;
2603 int ret;
2604 int final = 0;
2605
2606 if (exec == NULL)
2607 return(-1);
Daniel Veillard23e73572002-09-19 19:56:43 +00002608 if (exec->comp == NULL)
2609 return(-1);
Daniel Veillard4255d502002-04-16 15:50:10 +00002610 if (exec->status != 0)
2611 return(exec->status);
2612
Daniel Veillard23e73572002-09-19 19:56:43 +00002613 if (exec->comp->compact != NULL)
2614 return(xmlRegCompactPushString(exec, exec->comp, value, data));
2615
Daniel Veillard4255d502002-04-16 15:50:10 +00002616 if (value == NULL) {
2617 if (exec->state->type == XML_REGEXP_FINAL_STATE)
2618 return(1);
2619 final = 1;
2620 }
2621
2622#ifdef DEBUG_PUSH
2623 printf("value pushed: %s\n", value);
2624#endif
2625 /*
2626 * If we have an active rollback stack push the new value there
2627 * and get back to where we were left
2628 */
2629 if ((value != NULL) && (exec->inputStackNr > 0)) {
2630 xmlFARegExecSaveInputString(exec, value, data);
2631 value = exec->inputStack[exec->index].value;
2632 data = exec->inputStack[exec->index].data;
2633#ifdef DEBUG_PUSH
2634 printf("value loaded: %s\n", value);
2635#endif
2636 }
2637
2638 while ((exec->status == 0) &&
2639 ((value != NULL) ||
2640 ((final == 1) &&
2641 (exec->state->type != XML_REGEXP_FINAL_STATE)))) {
2642
2643 /*
2644 * End of input on non-terminal state, rollback, however we may
2645 * still have epsilon like transition for counted transitions
2646 * on counters, in that case don't break too early.
2647 */
Daniel Veillardb509f152002-04-17 16:28:10 +00002648 if ((value == NULL) && (exec->counts == NULL))
Daniel Veillard4255d502002-04-16 15:50:10 +00002649 goto rollback;
2650
2651 exec->transcount = 0;
2652 for (;exec->transno < exec->state->nbTrans;exec->transno++) {
2653 trans = &exec->state->trans[exec->transno];
2654 if (trans->to < 0)
2655 continue;
2656 atom = trans->atom;
2657 ret = 0;
Daniel Veillard441bc322002-04-20 17:38:48 +00002658 if (trans->count == REGEXP_ALL_LAX_COUNTER) {
2659 int i;
2660 int count;
2661 xmlRegTransPtr t;
2662 xmlRegCounterPtr counter;
2663
2664 ret = 0;
2665
2666#ifdef DEBUG_PUSH
2667 printf("testing all lax %d\n", trans->count);
2668#endif
2669 /*
2670 * Check all counted transitions from the current state
2671 */
2672 if ((value == NULL) && (final)) {
2673 ret = 1;
2674 } else if (value != NULL) {
2675 for (i = 0;i < exec->state->nbTrans;i++) {
2676 t = &exec->state->trans[i];
2677 if ((t->counter < 0) || (t == trans))
2678 continue;
2679 counter = &exec->comp->counters[t->counter];
2680 count = exec->counts[t->counter];
2681 if ((count < counter->max) &&
2682 (t->atom != NULL) &&
2683 (xmlStrEqual(value, t->atom->valuep))) {
2684 ret = 0;
2685 break;
2686 }
2687 if ((count >= counter->min) &&
2688 (count < counter->max) &&
2689 (xmlStrEqual(value, t->atom->valuep))) {
2690 ret = 1;
2691 break;
2692 }
2693 }
2694 }
2695 } else if (trans->count == REGEXP_ALL_COUNTER) {
Daniel Veillard8a001f62002-04-20 07:24:11 +00002696 int i;
2697 int count;
2698 xmlRegTransPtr t;
2699 xmlRegCounterPtr counter;
2700
2701 ret = 1;
2702
2703#ifdef DEBUG_PUSH
2704 printf("testing all %d\n", trans->count);
2705#endif
2706 /*
2707 * Check all counted transitions from the current state
2708 */
2709 for (i = 0;i < exec->state->nbTrans;i++) {
2710 t = &exec->state->trans[i];
2711 if ((t->counter < 0) || (t == trans))
2712 continue;
2713 counter = &exec->comp->counters[t->counter];
2714 count = exec->counts[t->counter];
2715 if ((count < counter->min) || (count > counter->max)) {
2716 ret = 0;
2717 break;
2718 }
2719 }
2720 } else if (trans->count >= 0) {
Daniel Veillard4255d502002-04-16 15:50:10 +00002721 int count;
2722 xmlRegCounterPtr counter;
2723
2724 /*
2725 * A counted transition.
2726 */
2727
2728 count = exec->counts[trans->count];
2729 counter = &exec->comp->counters[trans->count];
2730#ifdef DEBUG_PUSH
2731 printf("testing count %d: val %d, min %d, max %d\n",
2732 trans->count, count, counter->min, counter->max);
2733#endif
2734 ret = ((count >= counter->min) && (count <= counter->max));
2735 } else if (atom == NULL) {
2736 fprintf(stderr, "epsilon transition left at runtime\n");
2737 exec->status = -2;
2738 break;
2739 } else if (value != NULL) {
2740 ret = xmlStrEqual(value, atom->valuep);
Daniel Veillard441bc322002-04-20 17:38:48 +00002741 if ((ret == 1) && (trans->counter >= 0)) {
2742 xmlRegCounterPtr counter;
2743 int count;
2744
2745 count = exec->counts[trans->counter];
2746 counter = &exec->comp->counters[trans->counter];
2747 if (count >= counter->max)
2748 ret = 0;
2749 }
2750
Daniel Veillard4255d502002-04-16 15:50:10 +00002751 if ((ret == 1) && (atom->min > 0) && (atom->max > 0)) {
2752 xmlRegStatePtr to = exec->comp->states[trans->to];
2753
2754 /*
2755 * this is a multiple input sequence
2756 */
2757 if (exec->state->nbTrans > exec->transno + 1) {
2758 if (exec->inputStackNr <= 0) {
2759 xmlFARegExecSaveInputString(exec, value, data);
2760 }
2761 xmlFARegExecSave(exec);
2762 }
2763 exec->transcount = 1;
2764 do {
2765 /*
2766 * Try to progress as much as possible on the input
2767 */
2768 if (exec->transcount == atom->max) {
2769 break;
2770 }
2771 exec->index++;
2772 value = exec->inputStack[exec->index].value;
2773 data = exec->inputStack[exec->index].data;
2774#ifdef DEBUG_PUSH
2775 printf("value loaded: %s\n", value);
2776#endif
2777
2778 /*
2779 * End of input: stop here
2780 */
2781 if (value == NULL) {
2782 exec->index --;
2783 break;
2784 }
2785 if (exec->transcount >= atom->min) {
2786 int transno = exec->transno;
2787 xmlRegStatePtr state = exec->state;
2788
2789 /*
2790 * The transition is acceptable save it
2791 */
2792 exec->transno = -1; /* trick */
2793 exec->state = to;
2794 if (exec->inputStackNr <= 0) {
2795 xmlFARegExecSaveInputString(exec, value, data);
2796 }
2797 xmlFARegExecSave(exec);
2798 exec->transno = transno;
2799 exec->state = state;
2800 }
2801 ret = xmlStrEqual(value, atom->valuep);
2802 exec->transcount++;
2803 } while (ret == 1);
2804 if (exec->transcount < atom->min)
2805 ret = 0;
2806
2807 /*
2808 * If the last check failed but one transition was found
2809 * possible, rollback
2810 */
2811 if (ret < 0)
2812 ret = 0;
2813 if (ret == 0) {
2814 goto rollback;
2815 }
2816 }
2817 }
2818 if (ret == 1) {
William M. Brack98873952003-12-26 06:03:14 +00002819 if ((exec->callback != NULL) && (atom != NULL) &&
2820 (data != NULL)) {
Daniel Veillard4255d502002-04-16 15:50:10 +00002821 exec->callback(exec->data, atom->valuep,
2822 atom->data, data);
2823 }
2824 if (exec->state->nbTrans > exec->transno + 1) {
2825 if (exec->inputStackNr <= 0) {
2826 xmlFARegExecSaveInputString(exec, value, data);
2827 }
2828 xmlFARegExecSave(exec);
2829 }
2830 if (trans->counter >= 0) {
2831#ifdef DEBUG_PUSH
2832 printf("Increasing count %d\n", trans->counter);
2833#endif
2834 exec->counts[trans->counter]++;
2835 }
2836#ifdef DEBUG_PUSH
2837 printf("entering state %d\n", trans->to);
2838#endif
2839 exec->state = exec->comp->states[trans->to];
2840 exec->transno = 0;
2841 if (trans->atom != NULL) {
2842 if (exec->inputStack != NULL) {
2843 exec->index++;
2844 if (exec->index < exec->inputStackNr) {
2845 value = exec->inputStack[exec->index].value;
2846 data = exec->inputStack[exec->index].data;
2847#ifdef DEBUG_PUSH
2848 printf("value loaded: %s\n", value);
2849#endif
2850 } else {
2851 value = NULL;
2852 data = NULL;
2853#ifdef DEBUG_PUSH
2854 printf("end of input\n");
2855#endif
2856 }
2857 } else {
2858 value = NULL;
2859 data = NULL;
2860#ifdef DEBUG_PUSH
2861 printf("end of input\n");
2862#endif
2863 }
2864 }
2865 goto progress;
2866 } else if (ret < 0) {
2867 exec->status = -4;
2868 break;
2869 }
2870 }
2871 if ((exec->transno != 0) || (exec->state->nbTrans == 0)) {
2872rollback:
2873 /*
2874 * Failed to find a way out
2875 */
2876 exec->determinist = 0;
2877 xmlFARegExecRollBack(exec);
2878 if (exec->status == 0) {
2879 value = exec->inputStack[exec->index].value;
2880 data = exec->inputStack[exec->index].data;
2881#ifdef DEBUG_PUSH
2882 printf("value loaded: %s\n", value);
2883#endif
2884 }
2885 }
2886progress:
2887 continue;
2888 }
2889 if (exec->status == 0) {
2890 return(exec->state->type == XML_REGEXP_FINAL_STATE);
2891 }
2892 return(exec->status);
2893}
2894
Daniel Veillard52b48c72003-04-13 19:53:42 +00002895/**
2896 * xmlRegExecPushString2:
2897 * @exec: a regexp execution context or NULL to indicate the end
2898 * @value: the first string token input
2899 * @value2: the second string token input
2900 * @data: data associated to the token to reuse in callbacks
2901 *
2902 * Push one input token in the execution context
2903 *
2904 * Returns: 1 if the regexp reached a final state, 0 if non-final, and
2905 * a negative value in case of error.
2906 */
2907int
2908xmlRegExecPushString2(xmlRegExecCtxtPtr exec, const xmlChar *value,
2909 const xmlChar *value2, void *data) {
2910 xmlChar buf[150];
2911 int lenn, lenp, ret;
2912 xmlChar *str;
2913
2914 if (exec == NULL)
2915 return(-1);
2916 if (exec->comp == NULL)
2917 return(-1);
2918 if (exec->status != 0)
2919 return(exec->status);
2920
2921 if (value2 == NULL)
2922 return(xmlRegExecPushString(exec, value, data));
2923
2924 lenn = strlen((char *) value2);
2925 lenp = strlen((char *) value);
2926
2927 if (150 < lenn + lenp + 2) {
Daniel Veillard3c908dc2003-04-19 00:07:51 +00002928 str = (xmlChar *) xmlMallocAtomic(lenn + lenp + 2);
Daniel Veillard52b48c72003-04-13 19:53:42 +00002929 if (str == NULL) {
2930 exec->status = -1;
2931 return(-1);
2932 }
2933 } else {
2934 str = buf;
2935 }
2936 memcpy(&str[0], value, lenp);
2937 str[lenp] = '|';
2938 memcpy(&str[lenp + 1], value2, lenn);
2939 str[lenn + lenp + 1] = 0;
2940
2941 if (exec->comp->compact != NULL)
2942 ret = xmlRegCompactPushString(exec, exec->comp, str, data);
2943 else
2944 ret = xmlRegExecPushString(exec, str, data);
2945
2946 if (str != buf)
2947 xmlFree(buf);
2948 return(ret);
2949}
2950
Daniel Veillard4255d502002-04-16 15:50:10 +00002951#if 0
2952static int
2953xmlRegExecPushChar(xmlRegExecCtxtPtr exec, int UCS) {
2954 xmlRegTransPtr trans;
2955 xmlRegAtomPtr atom;
2956 int ret;
2957 int codepoint, len;
2958
2959 if (exec == NULL)
2960 return(-1);
2961 if (exec->status != 0)
2962 return(exec->status);
2963
2964 while ((exec->status == 0) &&
2965 ((exec->inputString[exec->index] != 0) ||
2966 (exec->state->type != XML_REGEXP_FINAL_STATE))) {
2967
2968 /*
2969 * End of input on non-terminal state, rollback, however we may
2970 * still have epsilon like transition for counted transitions
2971 * on counters, in that case don't break too early.
2972 */
2973 if ((exec->inputString[exec->index] == 0) && (exec->counts == NULL))
2974 goto rollback;
2975
2976 exec->transcount = 0;
2977 for (;exec->transno < exec->state->nbTrans;exec->transno++) {
2978 trans = &exec->state->trans[exec->transno];
2979 if (trans->to < 0)
2980 continue;
2981 atom = trans->atom;
2982 ret = 0;
2983 if (trans->count >= 0) {
2984 int count;
2985 xmlRegCounterPtr counter;
2986
2987 /*
2988 * A counted transition.
2989 */
2990
2991 count = exec->counts[trans->count];
2992 counter = &exec->comp->counters[trans->count];
2993#ifdef DEBUG_REGEXP_EXEC
2994 printf("testing count %d: val %d, min %d, max %d\n",
2995 trans->count, count, counter->min, counter->max);
2996#endif
2997 ret = ((count >= counter->min) && (count <= counter->max));
2998 } else if (atom == NULL) {
2999 fprintf(stderr, "epsilon transition left at runtime\n");
3000 exec->status = -2;
3001 break;
3002 } else if (exec->inputString[exec->index] != 0) {
3003 codepoint = CUR_SCHAR(&(exec->inputString[exec->index]), len);
3004 ret = xmlRegCheckCharacter(atom, codepoint);
3005 if ((ret == 1) && (atom->min > 0) && (atom->max > 0)) {
3006 xmlRegStatePtr to = exec->comp->states[trans->to];
3007
3008 /*
3009 * this is a multiple input sequence
3010 */
3011 if (exec->state->nbTrans > exec->transno + 1) {
3012 xmlFARegExecSave(exec);
3013 }
3014 exec->transcount = 1;
3015 do {
3016 /*
3017 * Try to progress as much as possible on the input
3018 */
3019 if (exec->transcount == atom->max) {
3020 break;
3021 }
3022 exec->index += len;
3023 /*
3024 * End of input: stop here
3025 */
3026 if (exec->inputString[exec->index] == 0) {
3027 exec->index -= len;
3028 break;
3029 }
3030 if (exec->transcount >= atom->min) {
3031 int transno = exec->transno;
3032 xmlRegStatePtr state = exec->state;
3033
3034 /*
3035 * The transition is acceptable save it
3036 */
3037 exec->transno = -1; /* trick */
3038 exec->state = to;
3039 xmlFARegExecSave(exec);
3040 exec->transno = transno;
3041 exec->state = state;
3042 }
3043 codepoint = CUR_SCHAR(&(exec->inputString[exec->index]),
3044 len);
3045 ret = xmlRegCheckCharacter(atom, codepoint);
3046 exec->transcount++;
3047 } while (ret == 1);
3048 if (exec->transcount < atom->min)
3049 ret = 0;
3050
3051 /*
3052 * If the last check failed but one transition was found
3053 * possible, rollback
3054 */
3055 if (ret < 0)
3056 ret = 0;
3057 if (ret == 0) {
3058 goto rollback;
3059 }
3060 }
3061 }
3062 if (ret == 1) {
3063 if (exec->state->nbTrans > exec->transno + 1) {
3064 xmlFARegExecSave(exec);
3065 }
3066 if (trans->counter >= 0) {
3067#ifdef DEBUG_REGEXP_EXEC
3068 printf("Increasing count %d\n", trans->counter);
3069#endif
3070 exec->counts[trans->counter]++;
3071 }
3072#ifdef DEBUG_REGEXP_EXEC
3073 printf("entering state %d\n", trans->to);
3074#endif
3075 exec->state = exec->comp->states[trans->to];
3076 exec->transno = 0;
3077 if (trans->atom != NULL) {
3078 exec->index += len;
3079 }
3080 goto progress;
3081 } else if (ret < 0) {
3082 exec->status = -4;
3083 break;
3084 }
3085 }
3086 if ((exec->transno != 0) || (exec->state->nbTrans == 0)) {
3087rollback:
3088 /*
3089 * Failed to find a way out
3090 */
3091 exec->determinist = 0;
3092 xmlFARegExecRollBack(exec);
3093 }
3094progress:
3095 continue;
3096 }
3097}
3098#endif
3099/************************************************************************
3100 * *
3101 * Parser for the Shemas Datatype Regular Expressions *
3102 * http://www.w3.org/TR/2001/REC-xmlschema-2-20010502/#regexs *
3103 * *
3104 ************************************************************************/
3105
3106/**
3107 * xmlFAIsChar:
Daniel Veillard441bc322002-04-20 17:38:48 +00003108 * @ctxt: a regexp parser context
Daniel Veillard4255d502002-04-16 15:50:10 +00003109 *
3110 * [10] Char ::= [^.\?*+()|#x5B#x5D]
3111 */
3112static int
3113xmlFAIsChar(xmlRegParserCtxtPtr ctxt) {
3114 int cur;
3115 int len;
3116
3117 cur = CUR_SCHAR(ctxt->cur, len);
3118 if ((cur == '.') || (cur == '\\') || (cur == '?') ||
3119 (cur == '*') || (cur == '+') || (cur == '(') ||
3120 (cur == ')') || (cur == '|') || (cur == 0x5B) ||
3121 (cur == 0x5D) || (cur == 0))
3122 return(-1);
3123 return(cur);
3124}
3125
3126/**
3127 * xmlFAParseCharProp:
Daniel Veillard441bc322002-04-20 17:38:48 +00003128 * @ctxt: a regexp parser context
Daniel Veillard4255d502002-04-16 15:50:10 +00003129 *
3130 * [27] charProp ::= IsCategory | IsBlock
3131 * [28] IsCategory ::= Letters | Marks | Numbers | Punctuation |
3132 * Separators | Symbols | Others
3133 * [29] Letters ::= 'L' [ultmo]?
3134 * [30] Marks ::= 'M' [nce]?
3135 * [31] Numbers ::= 'N' [dlo]?
3136 * [32] Punctuation ::= 'P' [cdseifo]?
3137 * [33] Separators ::= 'Z' [slp]?
3138 * [34] Symbols ::= 'S' [mcko]?
3139 * [35] Others ::= 'C' [cfon]?
3140 * [36] IsBlock ::= 'Is' [a-zA-Z0-9#x2D]+
3141 */
3142static void
3143xmlFAParseCharProp(xmlRegParserCtxtPtr ctxt) {
3144 int cur;
William M. Brack779af002003-08-01 15:55:39 +00003145 xmlRegAtomType type = (xmlRegAtomType) 0;
Daniel Veillard4255d502002-04-16 15:50:10 +00003146 xmlChar *blockName = NULL;
3147
3148 cur = CUR;
3149 if (cur == 'L') {
3150 NEXT;
3151 cur = CUR;
3152 if (cur == 'u') {
3153 NEXT;
3154 type = XML_REGEXP_LETTER_UPPERCASE;
3155 } else if (cur == 'l') {
3156 NEXT;
3157 type = XML_REGEXP_LETTER_LOWERCASE;
3158 } else if (cur == 't') {
3159 NEXT;
3160 type = XML_REGEXP_LETTER_TITLECASE;
3161 } else if (cur == 'm') {
3162 NEXT;
3163 type = XML_REGEXP_LETTER_MODIFIER;
3164 } else if (cur == 'o') {
3165 NEXT;
3166 type = XML_REGEXP_LETTER_OTHERS;
3167 } else {
3168 type = XML_REGEXP_LETTER;
3169 }
3170 } else if (cur == 'M') {
3171 NEXT;
3172 cur = CUR;
3173 if (cur == 'n') {
3174 NEXT;
3175 /* nonspacing */
3176 type = XML_REGEXP_MARK_NONSPACING;
3177 } else if (cur == 'c') {
3178 NEXT;
3179 /* spacing combining */
3180 type = XML_REGEXP_MARK_SPACECOMBINING;
3181 } else if (cur == 'e') {
3182 NEXT;
3183 /* enclosing */
3184 type = XML_REGEXP_MARK_ENCLOSING;
3185 } else {
3186 /* all marks */
3187 type = XML_REGEXP_MARK;
3188 }
3189 } else if (cur == 'N') {
3190 NEXT;
3191 cur = CUR;
3192 if (cur == 'd') {
3193 NEXT;
3194 /* digital */
3195 type = XML_REGEXP_NUMBER_DECIMAL;
3196 } else if (cur == 'l') {
3197 NEXT;
3198 /* letter */
3199 type = XML_REGEXP_NUMBER_LETTER;
3200 } else if (cur == 'o') {
3201 NEXT;
3202 /* other */
3203 type = XML_REGEXP_NUMBER_OTHERS;
3204 } else {
3205 /* all numbers */
3206 type = XML_REGEXP_NUMBER;
3207 }
3208 } else if (cur == 'P') {
3209 NEXT;
3210 cur = CUR;
3211 if (cur == 'c') {
3212 NEXT;
3213 /* connector */
3214 type = XML_REGEXP_PUNCT_CONNECTOR;
3215 } else if (cur == 'd') {
3216 NEXT;
3217 /* dash */
3218 type = XML_REGEXP_PUNCT_DASH;
3219 } else if (cur == 's') {
3220 NEXT;
3221 /* open */
3222 type = XML_REGEXP_PUNCT_OPEN;
3223 } else if (cur == 'e') {
3224 NEXT;
3225 /* close */
3226 type = XML_REGEXP_PUNCT_CLOSE;
3227 } else if (cur == 'i') {
3228 NEXT;
3229 /* initial quote */
3230 type = XML_REGEXP_PUNCT_INITQUOTE;
3231 } else if (cur == 'f') {
3232 NEXT;
3233 /* final quote */
3234 type = XML_REGEXP_PUNCT_FINQUOTE;
3235 } else if (cur == 'o') {
3236 NEXT;
3237 /* other */
3238 type = XML_REGEXP_PUNCT_OTHERS;
3239 } else {
3240 /* all punctuation */
3241 type = XML_REGEXP_PUNCT;
3242 }
3243 } else if (cur == 'Z') {
3244 NEXT;
3245 cur = CUR;
3246 if (cur == 's') {
3247 NEXT;
3248 /* space */
3249 type = XML_REGEXP_SEPAR_SPACE;
3250 } else if (cur == 'l') {
3251 NEXT;
3252 /* line */
3253 type = XML_REGEXP_SEPAR_LINE;
3254 } else if (cur == 'p') {
3255 NEXT;
3256 /* paragraph */
3257 type = XML_REGEXP_SEPAR_PARA;
3258 } else {
3259 /* all separators */
3260 type = XML_REGEXP_SEPAR;
3261 }
3262 } else if (cur == 'S') {
3263 NEXT;
3264 cur = CUR;
3265 if (cur == 'm') {
3266 NEXT;
3267 type = XML_REGEXP_SYMBOL_MATH;
3268 /* math */
3269 } else if (cur == 'c') {
3270 NEXT;
3271 type = XML_REGEXP_SYMBOL_CURRENCY;
3272 /* currency */
3273 } else if (cur == 'k') {
3274 NEXT;
3275 type = XML_REGEXP_SYMBOL_MODIFIER;
3276 /* modifiers */
3277 } else if (cur == 'o') {
3278 NEXT;
3279 type = XML_REGEXP_SYMBOL_OTHERS;
3280 /* other */
3281 } else {
3282 /* all symbols */
3283 type = XML_REGEXP_SYMBOL;
3284 }
3285 } else if (cur == 'C') {
3286 NEXT;
3287 cur = CUR;
3288 if (cur == 'c') {
3289 NEXT;
3290 /* control */
3291 type = XML_REGEXP_OTHER_CONTROL;
3292 } else if (cur == 'f') {
3293 NEXT;
3294 /* format */
3295 type = XML_REGEXP_OTHER_FORMAT;
3296 } else if (cur == 'o') {
3297 NEXT;
3298 /* private use */
3299 type = XML_REGEXP_OTHER_PRIVATE;
3300 } else if (cur == 'n') {
3301 NEXT;
3302 /* not assigned */
3303 type = XML_REGEXP_OTHER_NA;
3304 } else {
3305 /* all others */
3306 type = XML_REGEXP_OTHER;
3307 }
3308 } else if (cur == 'I') {
3309 const xmlChar *start;
3310 NEXT;
3311 cur = CUR;
3312 if (cur != 's') {
3313 ERROR("IsXXXX expected");
3314 return;
3315 }
3316 NEXT;
3317 start = ctxt->cur;
3318 cur = CUR;
3319 if (((cur >= 'a') && (cur <= 'z')) ||
3320 ((cur >= 'A') && (cur <= 'Z')) ||
3321 ((cur >= '0') && (cur <= '9')) ||
3322 (cur == 0x2D)) {
3323 NEXT;
3324 cur = CUR;
3325 while (((cur >= 'a') && (cur <= 'z')) ||
3326 ((cur >= 'A') && (cur <= 'Z')) ||
3327 ((cur >= '0') && (cur <= '9')) ||
3328 (cur == 0x2D)) {
3329 NEXT;
3330 cur = CUR;
3331 }
3332 }
3333 type = XML_REGEXP_BLOCK_NAME;
3334 blockName = xmlStrndup(start, ctxt->cur - start);
3335 } else {
3336 ERROR("Unknown char property");
3337 return;
3338 }
3339 if (ctxt->atom == NULL) {
3340 ctxt->atom = xmlRegNewAtom(ctxt, type);
3341 if (ctxt->atom != NULL)
3342 ctxt->atom->valuep = blockName;
3343 } else if (ctxt->atom->type == XML_REGEXP_RANGES) {
3344 xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,
3345 type, 0, 0, blockName);
3346 }
3347}
3348
3349/**
3350 * xmlFAParseCharClassEsc:
Daniel Veillard441bc322002-04-20 17:38:48 +00003351 * @ctxt: a regexp parser context
Daniel Veillard4255d502002-04-16 15:50:10 +00003352 *
3353 * [23] charClassEsc ::= ( SingleCharEsc | MultiCharEsc | catEsc | complEsc )
3354 * [24] SingleCharEsc ::= '\' [nrt\|.?*+(){}#x2D#x5B#x5D#x5E]
3355 * [25] catEsc ::= '\p{' charProp '}'
3356 * [26] complEsc ::= '\P{' charProp '}'
3357 * [37] MultiCharEsc ::= '.' | ('\' [sSiIcCdDwW])
3358 */
3359static void
3360xmlFAParseCharClassEsc(xmlRegParserCtxtPtr ctxt) {
3361 int cur;
3362
3363 if (CUR == '.') {
3364 if (ctxt->atom == NULL) {
3365 ctxt->atom = xmlRegNewAtom(ctxt, XML_REGEXP_ANYCHAR);
3366 } else if (ctxt->atom->type == XML_REGEXP_RANGES) {
3367 xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,
3368 XML_REGEXP_ANYCHAR, 0, 0, NULL);
3369 }
3370 NEXT;
3371 return;
3372 }
3373 if (CUR != '\\') {
3374 ERROR("Escaped sequence: expecting \\");
3375 return;
3376 }
3377 NEXT;
3378 cur = CUR;
3379 if (cur == 'p') {
3380 NEXT;
3381 if (CUR != '{') {
3382 ERROR("Expecting '{'");
3383 return;
3384 }
3385 NEXT;
3386 xmlFAParseCharProp(ctxt);
3387 if (CUR != '}') {
3388 ERROR("Expecting '}'");
3389 return;
3390 }
3391 NEXT;
3392 } else if (cur == 'P') {
3393 NEXT;
3394 if (CUR != '{') {
3395 ERROR("Expecting '{'");
3396 return;
3397 }
3398 NEXT;
3399 xmlFAParseCharProp(ctxt);
3400 ctxt->atom->neg = 1;
3401 if (CUR != '}') {
3402 ERROR("Expecting '}'");
3403 return;
3404 }
3405 NEXT;
3406 } else if ((cur == 'n') || (cur == 'r') || (cur == 't') || (cur == '\\') ||
3407 (cur == '|') || (cur == '.') || (cur == '?') || (cur == '*') ||
3408 (cur == '+') || (cur == '(') || (cur == ')') || (cur == '{') ||
3409 (cur == '}') || (cur == 0x2D) || (cur == 0x5B) || (cur == 0x5D) ||
3410 (cur == 0x5E)) {
3411 if (ctxt->atom == NULL) {
3412 ctxt->atom = xmlRegNewAtom(ctxt, XML_REGEXP_CHARVAL);
3413 if (ctxt->atom != NULL)
3414 ctxt->atom->codepoint = cur;
3415 } else if (ctxt->atom->type == XML_REGEXP_RANGES) {
3416 xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,
3417 XML_REGEXP_CHARVAL, cur, cur, NULL);
3418 }
3419 NEXT;
3420 } else if ((cur == 's') || (cur == 'S') || (cur == 'i') || (cur == 'I') ||
3421 (cur == 'c') || (cur == 'C') || (cur == 'd') || (cur == 'D') ||
3422 (cur == 'w') || (cur == 'W')) {
Daniel Veillardb509f152002-04-17 16:28:10 +00003423 xmlRegAtomType type = XML_REGEXP_ANYSPACE;
Daniel Veillard4255d502002-04-16 15:50:10 +00003424
3425 switch (cur) {
3426 case 's':
3427 type = XML_REGEXP_ANYSPACE;
3428 break;
3429 case 'S':
3430 type = XML_REGEXP_NOTSPACE;
3431 break;
3432 case 'i':
3433 type = XML_REGEXP_INITNAME;
3434 break;
3435 case 'I':
3436 type = XML_REGEXP_NOTINITNAME;
3437 break;
3438 case 'c':
3439 type = XML_REGEXP_NAMECHAR;
3440 break;
3441 case 'C':
3442 type = XML_REGEXP_NOTNAMECHAR;
3443 break;
3444 case 'd':
3445 type = XML_REGEXP_DECIMAL;
3446 break;
3447 case 'D':
3448 type = XML_REGEXP_NOTDECIMAL;
3449 break;
3450 case 'w':
3451 type = XML_REGEXP_REALCHAR;
3452 break;
3453 case 'W':
3454 type = XML_REGEXP_NOTREALCHAR;
3455 break;
3456 }
3457 NEXT;
3458 if (ctxt->atom == NULL) {
3459 ctxt->atom = xmlRegNewAtom(ctxt, type);
3460 } else if (ctxt->atom->type == XML_REGEXP_RANGES) {
3461 xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,
3462 type, 0, 0, NULL);
3463 }
3464 }
3465}
3466
3467/**
3468 * xmlFAParseCharRef:
Daniel Veillard441bc322002-04-20 17:38:48 +00003469 * @ctxt: a regexp parser context
Daniel Veillard4255d502002-04-16 15:50:10 +00003470 *
3471 * [19] XmlCharRef ::= ( '&#' [0-9]+ ';' ) | (' &#x' [0-9a-fA-F]+ ';' )
3472 */
3473static int
3474xmlFAParseCharRef(xmlRegParserCtxtPtr ctxt) {
3475 int ret = 0, cur;
3476
3477 if ((CUR != '&') || (NXT(1) != '#'))
3478 return(-1);
3479 NEXT;
3480 NEXT;
3481 cur = CUR;
3482 if (cur == 'x') {
3483 NEXT;
3484 cur = CUR;
3485 if (((cur >= '0') && (cur <= '9')) ||
3486 ((cur >= 'a') && (cur <= 'f')) ||
3487 ((cur >= 'A') && (cur <= 'F'))) {
3488 while (((cur >= '0') && (cur <= '9')) ||
3489 ((cur >= 'A') && (cur <= 'F'))) {
3490 if ((cur >= '0') && (cur <= '9'))
3491 ret = ret * 16 + cur - '0';
3492 else if ((cur >= 'a') && (cur <= 'f'))
3493 ret = ret * 16 + 10 + (cur - 'a');
3494 else
3495 ret = ret * 16 + 10 + (cur - 'A');
3496 NEXT;
3497 cur = CUR;
3498 }
3499 } else {
3500 ERROR("Char ref: expecting [0-9A-F]");
3501 return(-1);
3502 }
3503 } else {
3504 if ((cur >= '0') && (cur <= '9')) {
3505 while ((cur >= '0') && (cur <= '9')) {
3506 ret = ret * 10 + cur - '0';
3507 NEXT;
3508 cur = CUR;
3509 }
3510 } else {
3511 ERROR("Char ref: expecting [0-9]");
3512 return(-1);
3513 }
3514 }
3515 if (cur != ';') {
3516 ERROR("Char ref: expecting ';'");
3517 return(-1);
3518 } else {
3519 NEXT;
3520 }
3521 return(ret);
3522}
3523
3524/**
3525 * xmlFAParseCharRange:
Daniel Veillard441bc322002-04-20 17:38:48 +00003526 * @ctxt: a regexp parser context
Daniel Veillard4255d502002-04-16 15:50:10 +00003527 *
3528 * [17] charRange ::= seRange | XmlCharRef | XmlCharIncDash
3529 * [18] seRange ::= charOrEsc '-' charOrEsc
3530 * [20] charOrEsc ::= XmlChar | SingleCharEsc
3531 * [21] XmlChar ::= [^\#x2D#x5B#x5D]
3532 * [22] XmlCharIncDash ::= [^\#x5B#x5D]
3533 */
3534static void
3535xmlFAParseCharRange(xmlRegParserCtxtPtr ctxt) {
William M. Brackdc99df92003-12-27 01:54:25 +00003536 int cur, len;
Daniel Veillard4255d502002-04-16 15:50:10 +00003537 int start = -1;
3538 int end = -1;
3539
3540 if ((CUR == '&') && (NXT(1) == '#')) {
3541 end = start = xmlFAParseCharRef(ctxt);
3542 xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,
3543 XML_REGEXP_CHARVAL, start, end, NULL);
3544 return;
3545 }
3546 cur = CUR;
3547 if (cur == '\\') {
3548 NEXT;
3549 cur = CUR;
3550 switch (cur) {
3551 case 'n': start = 0xA; break;
3552 case 'r': start = 0xD; break;
3553 case 't': start = 0x9; break;
3554 case '\\': case '|': case '.': case '-': case '^': case '?':
3555 case '*': case '+': case '{': case '}': case '(': case ')':
3556 case '[': case ']':
3557 start = cur; break;
3558 default:
3559 ERROR("Invalid escape value");
3560 return;
3561 }
3562 end = start;
William M. Brackdc99df92003-12-27 01:54:25 +00003563 len = 1;
Daniel Veillard4255d502002-04-16 15:50:10 +00003564 } else if ((cur != 0x5B) && (cur != 0x5D)) {
William M. Brackdc99df92003-12-27 01:54:25 +00003565 end = start = CUR_SCHAR(ctxt->cur, len);
Daniel Veillard4255d502002-04-16 15:50:10 +00003566 } else {
3567 ERROR("Expecting a char range");
3568 return;
3569 }
William M. Brackdc99df92003-12-27 01:54:25 +00003570 NEXTL(len);
Daniel Veillard4255d502002-04-16 15:50:10 +00003571 if (start == '-') {
3572 return;
3573 }
3574 cur = CUR;
3575 if (cur != '-') {
3576 xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,
3577 XML_REGEXP_CHARVAL, start, end, NULL);
3578 return;
3579 }
3580 NEXT;
3581 cur = CUR;
3582 if (cur == '\\') {
3583 NEXT;
3584 cur = CUR;
3585 switch (cur) {
3586 case 'n': end = 0xA; break;
3587 case 'r': end = 0xD; break;
3588 case 't': end = 0x9; break;
3589 case '\\': case '|': case '.': case '-': case '^': case '?':
3590 case '*': case '+': case '{': case '}': case '(': case ')':
3591 case '[': case ']':
3592 end = cur; break;
3593 default:
3594 ERROR("Invalid escape value");
3595 return;
3596 }
William M. Brackdc99df92003-12-27 01:54:25 +00003597 len = 1;
Daniel Veillard4255d502002-04-16 15:50:10 +00003598 } else if ((cur != 0x5B) && (cur != 0x5D)) {
William M. Brackdc99df92003-12-27 01:54:25 +00003599 end = CUR_SCHAR(ctxt->cur, len);
Daniel Veillard4255d502002-04-16 15:50:10 +00003600 } else {
3601 ERROR("Expecting the end of a char range");
3602 return;
3603 }
William M. Brackdc99df92003-12-27 01:54:25 +00003604 NEXTL(len);
Daniel Veillard4255d502002-04-16 15:50:10 +00003605 /* TODO check that the values are acceptable character ranges for XML */
3606 if (end < start) {
3607 ERROR("End of range is before start of range");
3608 } else {
3609 xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,
3610 XML_REGEXP_CHARVAL, start, end, NULL);
3611 }
3612 return;
3613}
3614
3615/**
3616 * xmlFAParsePosCharGroup:
Daniel Veillard441bc322002-04-20 17:38:48 +00003617 * @ctxt: a regexp parser context
Daniel Veillard4255d502002-04-16 15:50:10 +00003618 *
3619 * [14] posCharGroup ::= ( charRange | charClassEsc )+
3620 */
3621static void
3622xmlFAParsePosCharGroup(xmlRegParserCtxtPtr ctxt) {
3623 do {
3624 if ((CUR == '\\') || (CUR == '.')) {
3625 xmlFAParseCharClassEsc(ctxt);
3626 } else {
3627 xmlFAParseCharRange(ctxt);
3628 }
3629 } while ((CUR != ']') && (CUR != '^') && (CUR != '-') &&
3630 (ctxt->error == 0));
3631}
3632
3633/**
3634 * xmlFAParseCharGroup:
Daniel Veillard441bc322002-04-20 17:38:48 +00003635 * @ctxt: a regexp parser context
Daniel Veillard4255d502002-04-16 15:50:10 +00003636 *
3637 * [13] charGroup ::= posCharGroup | negCharGroup | charClassSub
3638 * [15] negCharGroup ::= '^' posCharGroup
3639 * [16] charClassSub ::= ( posCharGroup | negCharGroup ) '-' charClassExpr
3640 * [12] charClassExpr ::= '[' charGroup ']'
3641 */
3642static void
3643xmlFAParseCharGroup(xmlRegParserCtxtPtr ctxt) {
3644 int n = ctxt->neg;
3645 while ((CUR != ']') && (ctxt->error == 0)) {
3646 if (CUR == '^') {
3647 int neg = ctxt->neg;
3648
3649 NEXT;
3650 ctxt->neg = !ctxt->neg;
3651 xmlFAParsePosCharGroup(ctxt);
3652 ctxt->neg = neg;
3653 } else if (CUR == '-') {
Daniel Veillardf8b9de32003-11-24 14:27:26 +00003654 int neg = ctxt->neg;
Daniel Veillard4255d502002-04-16 15:50:10 +00003655 NEXT;
Daniel Veillardf8b9de32003-11-24 14:27:26 +00003656 ctxt->neg = 2;
Daniel Veillard4255d502002-04-16 15:50:10 +00003657 if (CUR != '[') {
3658 ERROR("charClassExpr: '[' expected");
3659 break;
3660 }
3661 NEXT;
3662 xmlFAParseCharGroup(ctxt);
3663 if (CUR == ']') {
3664 NEXT;
3665 } else {
3666 ERROR("charClassExpr: ']' expected");
3667 break;
3668 }
Daniel Veillardf8b9de32003-11-24 14:27:26 +00003669 ctxt->neg = neg;
Daniel Veillard4255d502002-04-16 15:50:10 +00003670 break;
3671 } else if (CUR != ']') {
3672 xmlFAParsePosCharGroup(ctxt);
3673 }
3674 }
3675 ctxt->neg = n;
3676}
3677
3678/**
3679 * xmlFAParseCharClass:
Daniel Veillard441bc322002-04-20 17:38:48 +00003680 * @ctxt: a regexp parser context
Daniel Veillard4255d502002-04-16 15:50:10 +00003681 *
3682 * [11] charClass ::= charClassEsc | charClassExpr
3683 * [12] charClassExpr ::= '[' charGroup ']'
3684 */
3685static void
3686xmlFAParseCharClass(xmlRegParserCtxtPtr ctxt) {
3687 if (CUR == '[') {
3688 NEXT;
3689 ctxt->atom = xmlRegNewAtom(ctxt, XML_REGEXP_RANGES);
3690 if (ctxt->atom == NULL)
3691 return;
3692 xmlFAParseCharGroup(ctxt);
3693 if (CUR == ']') {
3694 NEXT;
3695 } else {
3696 ERROR("xmlFAParseCharClass: ']' expected");
3697 }
3698 } else {
3699 xmlFAParseCharClassEsc(ctxt);
3700 }
3701}
3702
3703/**
3704 * xmlFAParseQuantExact:
Daniel Veillard441bc322002-04-20 17:38:48 +00003705 * @ctxt: a regexp parser context
Daniel Veillard4255d502002-04-16 15:50:10 +00003706 *
3707 * [8] QuantExact ::= [0-9]+
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00003708 *
3709 * Returns 0 if success or -1 in case of error
Daniel Veillard4255d502002-04-16 15:50:10 +00003710 */
3711static int
3712xmlFAParseQuantExact(xmlRegParserCtxtPtr ctxt) {
3713 int ret = 0;
3714 int ok = 0;
3715
3716 while ((CUR >= '0') && (CUR <= '9')) {
3717 ret = ret * 10 + (CUR - '0');
3718 ok = 1;
3719 NEXT;
3720 }
3721 if (ok != 1) {
3722 return(-1);
3723 }
3724 return(ret);
3725}
3726
3727/**
3728 * xmlFAParseQuantifier:
Daniel Veillard441bc322002-04-20 17:38:48 +00003729 * @ctxt: a regexp parser context
Daniel Veillard4255d502002-04-16 15:50:10 +00003730 *
3731 * [4] quantifier ::= [?*+] | ( '{' quantity '}' )
3732 * [5] quantity ::= quantRange | quantMin | QuantExact
3733 * [6] quantRange ::= QuantExact ',' QuantExact
3734 * [7] quantMin ::= QuantExact ','
3735 * [8] QuantExact ::= [0-9]+
3736 */
3737static int
3738xmlFAParseQuantifier(xmlRegParserCtxtPtr ctxt) {
3739 int cur;
3740
3741 cur = CUR;
3742 if ((cur == '?') || (cur == '*') || (cur == '+')) {
3743 if (ctxt->atom != NULL) {
3744 if (cur == '?')
3745 ctxt->atom->quant = XML_REGEXP_QUANT_OPT;
3746 else if (cur == '*')
3747 ctxt->atom->quant = XML_REGEXP_QUANT_MULT;
3748 else if (cur == '+')
3749 ctxt->atom->quant = XML_REGEXP_QUANT_PLUS;
3750 }
3751 NEXT;
3752 return(1);
3753 }
3754 if (cur == '{') {
3755 int min = 0, max = 0;
3756
3757 NEXT;
3758 cur = xmlFAParseQuantExact(ctxt);
3759 if (cur >= 0)
3760 min = cur;
3761 if (CUR == ',') {
3762 NEXT;
Daniel Veillardebe48c62003-12-03 12:12:27 +00003763 if (CUR == '}')
3764 max = INT_MAX;
3765 else {
3766 cur = xmlFAParseQuantExact(ctxt);
3767 if (cur >= 0)
3768 max = cur;
3769 else {
3770 ERROR("Improper quantifier");
3771 }
3772 }
Daniel Veillard4255d502002-04-16 15:50:10 +00003773 }
3774 if (CUR == '}') {
3775 NEXT;
3776 } else {
3777 ERROR("Unterminated quantifier");
3778 }
3779 if (max == 0)
3780 max = min;
3781 if (ctxt->atom != NULL) {
3782 ctxt->atom->quant = XML_REGEXP_QUANT_RANGE;
3783 ctxt->atom->min = min;
3784 ctxt->atom->max = max;
3785 }
3786 return(1);
3787 }
3788 return(0);
3789}
3790
3791/**
3792 * xmlFAParseAtom:
Daniel Veillard441bc322002-04-20 17:38:48 +00003793 * @ctxt: a regexp parser context
Daniel Veillard4255d502002-04-16 15:50:10 +00003794 *
3795 * [9] atom ::= Char | charClass | ( '(' regExp ')' )
3796 */
3797static int
3798xmlFAParseAtom(xmlRegParserCtxtPtr ctxt) {
3799 int codepoint, len;
3800
3801 codepoint = xmlFAIsChar(ctxt);
3802 if (codepoint > 0) {
3803 ctxt->atom = xmlRegNewAtom(ctxt, XML_REGEXP_CHARVAL);
3804 if (ctxt->atom == NULL)
3805 return(-1);
3806 codepoint = CUR_SCHAR(ctxt->cur, len);
3807 ctxt->atom->codepoint = codepoint;
3808 NEXTL(len);
3809 return(1);
3810 } else if (CUR == '|') {
3811 return(0);
3812 } else if (CUR == 0) {
3813 return(0);
3814 } else if (CUR == ')') {
3815 return(0);
3816 } else if (CUR == '(') {
3817 xmlRegStatePtr start, oldend;
3818
3819 NEXT;
3820 xmlFAGenerateEpsilonTransition(ctxt, ctxt->state, NULL);
3821 start = ctxt->state;
3822 oldend = ctxt->end;
3823 ctxt->end = NULL;
3824 ctxt->atom = NULL;
3825 xmlFAParseRegExp(ctxt, 0);
3826 if (CUR == ')') {
3827 NEXT;
3828 } else {
3829 ERROR("xmlFAParseAtom: expecting ')'");
3830 }
3831 ctxt->atom = xmlRegNewAtom(ctxt, XML_REGEXP_SUBREG);
3832 if (ctxt->atom == NULL)
3833 return(-1);
3834 ctxt->atom->start = start;
3835 ctxt->atom->stop = ctxt->state;
3836 ctxt->end = oldend;
3837 return(1);
3838 } else if ((CUR == '[') || (CUR == '\\') || (CUR == '.')) {
3839 xmlFAParseCharClass(ctxt);
3840 return(1);
3841 }
3842 return(0);
3843}
3844
3845/**
3846 * xmlFAParsePiece:
Daniel Veillard441bc322002-04-20 17:38:48 +00003847 * @ctxt: a regexp parser context
Daniel Veillard4255d502002-04-16 15:50:10 +00003848 *
3849 * [3] piece ::= atom quantifier?
3850 */
3851static int
3852xmlFAParsePiece(xmlRegParserCtxtPtr ctxt) {
3853 int ret;
3854
3855 ctxt->atom = NULL;
3856 ret = xmlFAParseAtom(ctxt);
3857 if (ret == 0)
3858 return(0);
3859 if (ctxt->atom == NULL) {
3860 ERROR("internal: no atom generated");
3861 }
3862 xmlFAParseQuantifier(ctxt);
3863 return(1);
3864}
3865
3866/**
3867 * xmlFAParseBranch:
Daniel Veillard441bc322002-04-20 17:38:48 +00003868 * @ctxt: a regexp parser context
3869 * @first: is taht the first
Daniel Veillard4255d502002-04-16 15:50:10 +00003870 *
3871 * [2] branch ::= piece*
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00003872 8
Daniel Veillard4255d502002-04-16 15:50:10 +00003873 */
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00003874static int
Daniel Veillard4255d502002-04-16 15:50:10 +00003875xmlFAParseBranch(xmlRegParserCtxtPtr ctxt, int first) {
3876 xmlRegStatePtr previous;
3877 xmlRegAtomPtr prevatom = NULL;
3878 int ret;
3879
3880 previous = ctxt->state;
3881 ret = xmlFAParsePiece(ctxt);
3882 if (ret != 0) {
3883 if (first) {
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00003884 if (xmlFAGenerateTransitions(ctxt, previous, NULL, ctxt->atom) < 0)
3885 return(-1);
Daniel Veillard4255d502002-04-16 15:50:10 +00003886 previous = ctxt->state;
3887 } else {
3888 prevatom = ctxt->atom;
3889 }
3890 ctxt->atom = NULL;
3891 }
3892 while ((ret != 0) && (ctxt->error == 0)) {
3893 ret = xmlFAParsePiece(ctxt);
3894 if (ret != 0) {
3895 if (first) {
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00003896 if (xmlFAGenerateTransitions(ctxt, previous, NULL,
3897 ctxt->atom) < 0)
3898 return(-1);
Daniel Veillard4255d502002-04-16 15:50:10 +00003899 } else {
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00003900 if (xmlFAGenerateTransitions(ctxt, previous, NULL,
3901 prevatom) < 0)
3902 return(-1);
Daniel Veillard4255d502002-04-16 15:50:10 +00003903 prevatom = ctxt->atom;
3904 }
3905 previous = ctxt->state;
3906 ctxt->atom = NULL;
3907 }
3908 }
3909 if (!first) {
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00003910 if (xmlFAGenerateTransitions(ctxt, previous, ctxt->end, prevatom) < 0)
3911 return(-1);
Daniel Veillard4255d502002-04-16 15:50:10 +00003912 }
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00003913 return(0);
Daniel Veillard4255d502002-04-16 15:50:10 +00003914}
3915
3916/**
3917 * xmlFAParseRegExp:
Daniel Veillard441bc322002-04-20 17:38:48 +00003918 * @ctxt: a regexp parser context
3919 * @top: is that the top-level expressions ?
Daniel Veillard4255d502002-04-16 15:50:10 +00003920 *
3921 * [1] regExp ::= branch ( '|' branch )*
3922 */
3923static void
3924xmlFAParseRegExp(xmlRegParserCtxtPtr ctxt, int top) {
3925 xmlRegStatePtr start, end, oldend;
3926
3927 oldend = ctxt->end;
3928
3929 start = ctxt->state;
3930 xmlFAParseBranch(ctxt, (ctxt->end == NULL));
3931 if (CUR != '|') {
3932 ctxt->end = ctxt->state;
3933 return;
3934 }
3935 end = ctxt->state;
3936 while ((CUR == '|') && (ctxt->error == 0)) {
3937 NEXT;
3938 ctxt->state = start;
3939 ctxt->end = end;
3940 xmlFAParseBranch(ctxt, 0);
3941 }
3942 if (!top)
3943 ctxt->end = oldend;
3944}
3945
3946/************************************************************************
3947 * *
3948 * The basic API *
3949 * *
3950 ************************************************************************/
3951
3952/**
3953 * xmlRegexpPrint:
3954 * @output: the file for the output debug
3955 * @regexp: the compiled regexp
3956 *
3957 * Print the content of the compiled regular expression
3958 */
3959void
3960xmlRegexpPrint(FILE *output, xmlRegexpPtr regexp) {
3961 int i;
3962
3963 fprintf(output, " regexp: ");
3964 if (regexp == NULL) {
3965 fprintf(output, "NULL\n");
3966 return;
3967 }
3968 fprintf(output, "'%s' ", regexp->string);
3969 fprintf(output, "\n");
3970 fprintf(output, "%d atoms:\n", regexp->nbAtoms);
3971 for (i = 0;i < regexp->nbAtoms; i++) {
3972 fprintf(output, " %02d ", i);
3973 xmlRegPrintAtom(output, regexp->atoms[i]);
3974 }
3975 fprintf(output, "%d states:", regexp->nbStates);
3976 fprintf(output, "\n");
3977 for (i = 0;i < regexp->nbStates; i++) {
3978 xmlRegPrintState(output, regexp->states[i]);
3979 }
3980 fprintf(output, "%d counters:\n", regexp->nbCounters);
3981 for (i = 0;i < regexp->nbCounters; i++) {
3982 fprintf(output, " %d: min %d max %d\n", i, regexp->counters[i].min,
3983 regexp->counters[i].max);
3984 }
3985}
3986
3987/**
3988 * xmlRegexpCompile:
3989 * @regexp: a regular expression string
3990 *
3991 * Parses a regular expression conforming to XML Schemas Part 2 Datatype
3992 * Appendix F and build an automata suitable for testing strings against
3993 * that regular expression
3994 *
3995 * Returns the compiled expression or NULL in case of error
3996 */
3997xmlRegexpPtr
3998xmlRegexpCompile(const xmlChar *regexp) {
3999 xmlRegexpPtr ret;
4000 xmlRegParserCtxtPtr ctxt;
4001
4002 ctxt = xmlRegNewParserCtxt(regexp);
4003 if (ctxt == NULL)
4004 return(NULL);
4005
4006 /* initialize the parser */
4007 ctxt->end = NULL;
4008 ctxt->start = ctxt->state = xmlRegNewState(ctxt);
4009 xmlRegStatePush(ctxt, ctxt->start);
4010
4011 /* parse the expression building an automata */
4012 xmlFAParseRegExp(ctxt, 1);
4013 if (CUR != 0) {
4014 ERROR("xmlFAParseRegExp: extra characters");
4015 }
4016 ctxt->end = ctxt->state;
4017 ctxt->start->type = XML_REGEXP_START_STATE;
4018 ctxt->end->type = XML_REGEXP_FINAL_STATE;
4019
4020 /* remove the Epsilon except for counted transitions */
4021 xmlFAEliminateEpsilonTransitions(ctxt);
4022
4023
4024 if (ctxt->error != 0) {
4025 xmlRegFreeParserCtxt(ctxt);
4026 return(NULL);
4027 }
4028 ret = xmlRegEpxFromParse(ctxt);
4029 xmlRegFreeParserCtxt(ctxt);
4030 return(ret);
4031}
4032
4033/**
4034 * xmlRegexpExec:
4035 * @comp: the compiled regular expression
4036 * @content: the value to check against the regular expression
4037 *
4038 * Check if the regular expression generate the value
4039 *
4040 * Returns 1 if it matches, 0 if not and a negativa value in case of error
4041 */
4042int
4043xmlRegexpExec(xmlRegexpPtr comp, const xmlChar *content) {
4044 if ((comp == NULL) || (content == NULL))
4045 return(-1);
4046 return(xmlFARegExec(comp, content));
4047}
4048
4049/**
Daniel Veillard23e73572002-09-19 19:56:43 +00004050 * xmlRegexpIsDeterminist:
4051 * @comp: the compiled regular expression
4052 *
4053 * Check if the regular expression is determinist
4054 *
4055 * Returns 1 if it yes, 0 if not and a negativa value in case of error
4056 */
4057int
4058xmlRegexpIsDeterminist(xmlRegexpPtr comp) {
4059 xmlAutomataPtr am;
4060 int ret;
4061
4062 if (comp == NULL)
4063 return(-1);
4064 if (comp->determinist != -1)
4065 return(comp->determinist);
4066
4067 am = xmlNewAutomata();
Daniel Veillardbd9afb52002-09-25 22:25:35 +00004068 if (am->states != NULL) {
4069 int i;
4070
4071 for (i = 0;i < am->nbStates;i++)
4072 xmlRegFreeState(am->states[i]);
4073 xmlFree(am->states);
4074 }
Daniel Veillard23e73572002-09-19 19:56:43 +00004075 am->nbAtoms = comp->nbAtoms;
4076 am->atoms = comp->atoms;
4077 am->nbStates = comp->nbStates;
4078 am->states = comp->states;
4079 am->determinist = -1;
4080 ret = xmlFAComputesDeterminism(am);
4081 am->atoms = NULL;
4082 am->states = NULL;
4083 xmlFreeAutomata(am);
4084 return(ret);
4085}
4086
4087/**
Daniel Veillard4255d502002-04-16 15:50:10 +00004088 * xmlRegFreeRegexp:
4089 * @regexp: the regexp
4090 *
4091 * Free a regexp
4092 */
4093void
4094xmlRegFreeRegexp(xmlRegexpPtr regexp) {
4095 int i;
4096 if (regexp == NULL)
4097 return;
4098
4099 if (regexp->string != NULL)
4100 xmlFree(regexp->string);
4101 if (regexp->states != NULL) {
4102 for (i = 0;i < regexp->nbStates;i++)
4103 xmlRegFreeState(regexp->states[i]);
4104 xmlFree(regexp->states);
4105 }
4106 if (regexp->atoms != NULL) {
4107 for (i = 0;i < regexp->nbAtoms;i++)
4108 xmlRegFreeAtom(regexp->atoms[i]);
4109 xmlFree(regexp->atoms);
4110 }
4111 if (regexp->counters != NULL)
4112 xmlFree(regexp->counters);
Daniel Veillard23e73572002-09-19 19:56:43 +00004113 if (regexp->compact != NULL)
4114 xmlFree(regexp->compact);
Daniel Veillard118aed72002-09-24 14:13:13 +00004115 if (regexp->transdata != NULL)
4116 xmlFree(regexp->transdata);
Daniel Veillard23e73572002-09-19 19:56:43 +00004117 if (regexp->stringMap != NULL) {
4118 for (i = 0; i < regexp->nbstrings;i++)
4119 xmlFree(regexp->stringMap[i]);
4120 xmlFree(regexp->stringMap);
4121 }
4122
Daniel Veillard4255d502002-04-16 15:50:10 +00004123 xmlFree(regexp);
4124}
4125
4126#ifdef LIBXML_AUTOMATA_ENABLED
4127/************************************************************************
4128 * *
4129 * The Automata interface *
4130 * *
4131 ************************************************************************/
4132
4133/**
4134 * xmlNewAutomata:
4135 *
4136 * Create a new automata
4137 *
4138 * Returns the new object or NULL in case of failure
4139 */
4140xmlAutomataPtr
4141xmlNewAutomata(void) {
4142 xmlAutomataPtr ctxt;
4143
4144 ctxt = xmlRegNewParserCtxt(NULL);
4145 if (ctxt == NULL)
4146 return(NULL);
4147
4148 /* initialize the parser */
4149 ctxt->end = NULL;
4150 ctxt->start = ctxt->state = xmlRegNewState(ctxt);
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00004151 if (ctxt->start == NULL) {
4152 xmlFreeAutomata(ctxt);
4153 return(NULL);
4154 }
4155 if (xmlRegStatePush(ctxt, ctxt->start) < 0) {
4156 xmlRegFreeState(ctxt->start);
4157 xmlFreeAutomata(ctxt);
4158 return(NULL);
4159 }
Daniel Veillard4255d502002-04-16 15:50:10 +00004160
4161 return(ctxt);
4162}
4163
4164/**
4165 * xmlFreeAutomata:
4166 * @am: an automata
4167 *
4168 * Free an automata
4169 */
4170void
4171xmlFreeAutomata(xmlAutomataPtr am) {
4172 if (am == NULL)
4173 return;
4174 xmlRegFreeParserCtxt(am);
4175}
4176
4177/**
4178 * xmlAutomataGetInitState:
4179 * @am: an automata
4180 *
Daniel Veillarda9b66d02002-12-11 14:23:49 +00004181 * Initial state lookup
4182 *
Daniel Veillard4255d502002-04-16 15:50:10 +00004183 * Returns the initial state of the automata
4184 */
4185xmlAutomataStatePtr
4186xmlAutomataGetInitState(xmlAutomataPtr am) {
4187 if (am == NULL)
4188 return(NULL);
4189 return(am->start);
4190}
4191
4192/**
4193 * xmlAutomataSetFinalState:
4194 * @am: an automata
4195 * @state: a state in this automata
4196 *
4197 * Makes that state a final state
4198 *
4199 * Returns 0 or -1 in case of error
4200 */
4201int
4202xmlAutomataSetFinalState(xmlAutomataPtr am, xmlAutomataStatePtr state) {
4203 if ((am == NULL) || (state == NULL))
4204 return(-1);
4205 state->type = XML_REGEXP_FINAL_STATE;
4206 return(0);
4207}
4208
4209/**
4210 * xmlAutomataNewTransition:
4211 * @am: an automata
4212 * @from: the starting point of the transition
4213 * @to: the target point of the transition or NULL
4214 * @token: the input string associated to that transition
4215 * @data: data passed to the callback function if the transition is activated
4216 *
4217 * If @to is NULL, this create first a new target state in the automata
4218 * and then adds a transition from the @from state to the target state
4219 * activated by the value of @token
4220 *
4221 * Returns the target state or NULL in case of error
4222 */
4223xmlAutomataStatePtr
4224xmlAutomataNewTransition(xmlAutomataPtr am, xmlAutomataStatePtr from,
4225 xmlAutomataStatePtr to, const xmlChar *token,
4226 void *data) {
4227 xmlRegAtomPtr atom;
4228
4229 if ((am == NULL) || (from == NULL) || (token == NULL))
4230 return(NULL);
4231 atom = xmlRegNewAtom(am, XML_REGEXP_STRING);
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00004232 if (atom == NULL)
4233 return(NULL);
Daniel Veillard4255d502002-04-16 15:50:10 +00004234 atom->data = data;
4235 if (atom == NULL)
4236 return(NULL);
4237 atom->valuep = xmlStrdup(token);
4238
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00004239 if (xmlFAGenerateTransitions(am, from, to, atom) < 0) {
4240 xmlRegFreeAtom(atom);
4241 return(NULL);
4242 }
Daniel Veillard4255d502002-04-16 15:50:10 +00004243 if (to == NULL)
4244 return(am->state);
4245 return(to);
4246}
4247
4248/**
Daniel Veillard52b48c72003-04-13 19:53:42 +00004249 * xmlAutomataNewTransition2:
4250 * @am: an automata
4251 * @from: the starting point of the transition
4252 * @to: the target point of the transition or NULL
4253 * @token: the first input string associated to that transition
4254 * @token2: the second input string associated to that transition
4255 * @data: data passed to the callback function if the transition is activated
4256 *
4257 * If @to is NULL, this create first a new target state in the automata
4258 * and then adds a transition from the @from state to the target state
4259 * activated by the value of @token
4260 *
4261 * Returns the target state or NULL in case of error
4262 */
4263xmlAutomataStatePtr
4264xmlAutomataNewTransition2(xmlAutomataPtr am, xmlAutomataStatePtr from,
4265 xmlAutomataStatePtr to, const xmlChar *token,
4266 const xmlChar *token2, void *data) {
4267 xmlRegAtomPtr atom;
4268
4269 if ((am == NULL) || (from == NULL) || (token == NULL))
4270 return(NULL);
4271 atom = xmlRegNewAtom(am, XML_REGEXP_STRING);
4272 atom->data = data;
4273 if (atom == NULL)
4274 return(NULL);
4275 if ((token2 == NULL) || (*token2 == 0)) {
4276 atom->valuep = xmlStrdup(token);
4277 } else {
4278 int lenn, lenp;
4279 xmlChar *str;
4280
4281 lenn = strlen((char *) token2);
4282 lenp = strlen((char *) token);
4283
Daniel Veillard3c908dc2003-04-19 00:07:51 +00004284 str = (xmlChar *) xmlMallocAtomic(lenn + lenp + 2);
Daniel Veillard52b48c72003-04-13 19:53:42 +00004285 if (str == NULL) {
4286 xmlRegFreeAtom(atom);
4287 return(NULL);
4288 }
4289 memcpy(&str[0], token, lenp);
4290 str[lenp] = '|';
4291 memcpy(&str[lenp + 1], token2, lenn);
4292 str[lenn + lenp + 1] = 0;
4293
4294 atom->valuep = str;
4295 }
4296
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00004297 if (xmlFAGenerateTransitions(am, from, to, atom) < 0) {
4298 xmlRegFreeAtom(atom);
4299 return(NULL);
4300 }
Daniel Veillard52b48c72003-04-13 19:53:42 +00004301 if (to == NULL)
4302 return(am->state);
4303 return(to);
4304}
4305
4306/**
Daniel Veillard4255d502002-04-16 15:50:10 +00004307 * xmlAutomataNewCountTrans:
4308 * @am: an automata
4309 * @from: the starting point of the transition
4310 * @to: the target point of the transition or NULL
4311 * @token: the input string associated to that transition
4312 * @min: the minimum successive occurences of token
Daniel Veillarda9b66d02002-12-11 14:23:49 +00004313 * @max: the maximum successive occurences of token
4314 * @data: data associated to the transition
Daniel Veillard4255d502002-04-16 15:50:10 +00004315 *
4316 * If @to is NULL, this create first a new target state in the automata
4317 * and then adds a transition from the @from state to the target state
4318 * activated by a succession of input of value @token and whose number
4319 * is between @min and @max
4320 *
4321 * Returns the target state or NULL in case of error
4322 */
4323xmlAutomataStatePtr
4324xmlAutomataNewCountTrans(xmlAutomataPtr am, xmlAutomataStatePtr from,
4325 xmlAutomataStatePtr to, const xmlChar *token,
4326 int min, int max, void *data) {
4327 xmlRegAtomPtr atom;
Daniel Veillard0ddb21c2004-02-12 12:43:49 +00004328 int counter;
Daniel Veillard4255d502002-04-16 15:50:10 +00004329
4330 if ((am == NULL) || (from == NULL) || (token == NULL))
4331 return(NULL);
4332 if (min < 0)
4333 return(NULL);
4334 if ((max < min) || (max < 1))
4335 return(NULL);
4336 atom = xmlRegNewAtom(am, XML_REGEXP_STRING);
4337 if (atom == NULL)
4338 return(NULL);
4339 atom->valuep = xmlStrdup(token);
4340 atom->data = data;
4341 if (min == 0)
4342 atom->min = 1;
4343 else
4344 atom->min = min;
4345 atom->max = max;
4346
Daniel Veillard0ddb21c2004-02-12 12:43:49 +00004347 /*
4348 * associate a counter to the transition.
4349 */
4350 counter = xmlRegGetCounter(am);
4351 am->counters[counter].min = min;
4352 am->counters[counter].max = max;
4353
4354 /* xmlFAGenerateTransitions(am, from, to, atom); */
4355 if (to == NULL) {
4356 to = xmlRegNewState(am);
4357 xmlRegStatePush(am, to);
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00004358 }
Daniel Veillard0ddb21c2004-02-12 12:43:49 +00004359 xmlRegStateAddTrans(am, from, atom, to, counter, -1);
4360 xmlRegAtomPush(am, atom);
4361 am->state = to;
4362
Daniel Veillard4255d502002-04-16 15:50:10 +00004363 if (to == NULL)
4364 to = am->state;
4365 if (to == NULL)
4366 return(NULL);
4367 if (min == 0)
4368 xmlFAGenerateEpsilonTransition(am, from, to);
4369 return(to);
4370}
4371
4372/**
Daniel Veillard7646b182002-04-20 06:41:40 +00004373 * xmlAutomataNewOnceTrans:
4374 * @am: an automata
4375 * @from: the starting point of the transition
4376 * @to: the target point of the transition or NULL
4377 * @token: the input string associated to that transition
4378 * @min: the minimum successive occurences of token
Daniel Veillarda9b66d02002-12-11 14:23:49 +00004379 * @max: the maximum successive occurences of token
4380 * @data: data associated to the transition
Daniel Veillard7646b182002-04-20 06:41:40 +00004381 *
4382 * If @to is NULL, this create first a new target state in the automata
4383 * and then adds a transition from the @from state to the target state
4384 * activated by a succession of input of value @token and whose number
4385 * is between @min and @max, moreover that transistion can only be crossed
4386 * once.
4387 *
4388 * Returns the target state or NULL in case of error
4389 */
4390xmlAutomataStatePtr
4391xmlAutomataNewOnceTrans(xmlAutomataPtr am, xmlAutomataStatePtr from,
4392 xmlAutomataStatePtr to, const xmlChar *token,
4393 int min, int max, void *data) {
4394 xmlRegAtomPtr atom;
4395 int counter;
4396
4397 if ((am == NULL) || (from == NULL) || (token == NULL))
4398 return(NULL);
4399 if (min < 1)
4400 return(NULL);
4401 if ((max < min) || (max < 1))
4402 return(NULL);
4403 atom = xmlRegNewAtom(am, XML_REGEXP_STRING);
4404 if (atom == NULL)
4405 return(NULL);
4406 atom->valuep = xmlStrdup(token);
4407 atom->data = data;
4408 atom->quant = XML_REGEXP_QUANT_ONCEONLY;
4409 if (min == 0)
4410 atom->min = 1;
4411 else
4412 atom->min = min;
4413 atom->max = max;
4414 /*
4415 * associate a counter to the transition.
4416 */
4417 counter = xmlRegGetCounter(am);
4418 am->counters[counter].min = 1;
4419 am->counters[counter].max = 1;
4420
4421 /* xmlFAGenerateTransitions(am, from, to, atom); */
4422 if (to == NULL) {
4423 to = xmlRegNewState(am);
4424 xmlRegStatePush(am, to);
4425 }
4426 xmlRegStateAddTrans(am, from, atom, to, counter, -1);
4427 xmlRegAtomPush(am, atom);
4428 am->state = to;
4429 if (to == NULL)
4430 to = am->state;
4431 if (to == NULL)
4432 return(NULL);
4433 return(to);
4434}
4435
4436/**
Daniel Veillard4255d502002-04-16 15:50:10 +00004437 * xmlAutomataNewState:
4438 * @am: an automata
4439 *
4440 * Create a new disconnected state in the automata
4441 *
4442 * Returns the new state or NULL in case of error
4443 */
4444xmlAutomataStatePtr
4445xmlAutomataNewState(xmlAutomataPtr am) {
4446 xmlAutomataStatePtr to;
4447
4448 if (am == NULL)
4449 return(NULL);
4450 to = xmlRegNewState(am);
4451 xmlRegStatePush(am, to);
4452 return(to);
4453}
4454
4455/**
Daniel Veillarda9b66d02002-12-11 14:23:49 +00004456 * xmlAutomataNewEpsilon:
Daniel Veillard4255d502002-04-16 15:50:10 +00004457 * @am: an automata
4458 * @from: the starting point of the transition
4459 * @to: the target point of the transition or NULL
4460 *
4461 * If @to is NULL, this create first a new target state in the automata
4462 * and then adds a an epsilon transition from the @from state to the
4463 * target state
4464 *
4465 * Returns the target state or NULL in case of error
4466 */
4467xmlAutomataStatePtr
4468xmlAutomataNewEpsilon(xmlAutomataPtr am, xmlAutomataStatePtr from,
4469 xmlAutomataStatePtr to) {
4470 if ((am == NULL) || (from == NULL))
4471 return(NULL);
4472 xmlFAGenerateEpsilonTransition(am, from, to);
4473 if (to == NULL)
4474 return(am->state);
4475 return(to);
4476}
4477
Daniel Veillardb509f152002-04-17 16:28:10 +00004478/**
Daniel Veillard7646b182002-04-20 06:41:40 +00004479 * xmlAutomataNewAllTrans:
4480 * @am: an automata
4481 * @from: the starting point of the transition
4482 * @to: the target point of the transition or NULL
Daniel Veillarda9b66d02002-12-11 14:23:49 +00004483 * @lax: allow to transition if not all all transitions have been activated
Daniel Veillard7646b182002-04-20 06:41:40 +00004484 *
4485 * If @to is NULL, this create first a new target state in the automata
4486 * and then adds a an ALL transition from the @from state to the
4487 * target state. That transition is an epsilon transition allowed only when
4488 * all transitions from the @from node have been activated.
4489 *
4490 * Returns the target state or NULL in case of error
4491 */
4492xmlAutomataStatePtr
4493xmlAutomataNewAllTrans(xmlAutomataPtr am, xmlAutomataStatePtr from,
Daniel Veillard441bc322002-04-20 17:38:48 +00004494 xmlAutomataStatePtr to, int lax) {
Daniel Veillard7646b182002-04-20 06:41:40 +00004495 if ((am == NULL) || (from == NULL))
4496 return(NULL);
Daniel Veillard441bc322002-04-20 17:38:48 +00004497 xmlFAGenerateAllTransition(am, from, to, lax);
Daniel Veillard7646b182002-04-20 06:41:40 +00004498 if (to == NULL)
4499 return(am->state);
4500 return(to);
4501}
4502
4503/**
Daniel Veillardb509f152002-04-17 16:28:10 +00004504 * xmlAutomataNewCounter:
4505 * @am: an automata
4506 * @min: the minimal value on the counter
4507 * @max: the maximal value on the counter
4508 *
4509 * Create a new counter
4510 *
4511 * Returns the counter number or -1 in case of error
4512 */
4513int
4514xmlAutomataNewCounter(xmlAutomataPtr am, int min, int max) {
4515 int ret;
4516
4517 if (am == NULL)
4518 return(-1);
4519
4520 ret = xmlRegGetCounter(am);
4521 if (ret < 0)
4522 return(-1);
4523 am->counters[ret].min = min;
4524 am->counters[ret].max = max;
4525 return(ret);
4526}
4527
4528/**
4529 * xmlAutomataNewCountedTrans:
4530 * @am: an automata
4531 * @from: the starting point of the transition
4532 * @to: the target point of the transition or NULL
4533 * @counter: the counter associated to that transition
4534 *
4535 * If @to is NULL, this create first a new target state in the automata
4536 * and then adds an epsilon transition from the @from state to the target state
4537 * which will increment the counter provided
4538 *
4539 * Returns the target state or NULL in case of error
4540 */
4541xmlAutomataStatePtr
4542xmlAutomataNewCountedTrans(xmlAutomataPtr am, xmlAutomataStatePtr from,
4543 xmlAutomataStatePtr to, int counter) {
4544 if ((am == NULL) || (from == NULL) || (counter < 0))
4545 return(NULL);
4546 xmlFAGenerateCountedEpsilonTransition(am, from, to, counter);
4547 if (to == NULL)
4548 return(am->state);
4549 return(to);
4550}
4551
4552/**
4553 * xmlAutomataNewCounterTrans:
4554 * @am: an automata
4555 * @from: the starting point of the transition
4556 * @to: the target point of the transition or NULL
4557 * @counter: the counter associated to that transition
4558 *
4559 * If @to is NULL, this create first a new target state in the automata
4560 * and then adds an epsilon transition from the @from state to the target state
4561 * which will be allowed only if the counter is within the right range.
4562 *
4563 * Returns the target state or NULL in case of error
4564 */
4565xmlAutomataStatePtr
4566xmlAutomataNewCounterTrans(xmlAutomataPtr am, xmlAutomataStatePtr from,
4567 xmlAutomataStatePtr to, int counter) {
4568 if ((am == NULL) || (from == NULL) || (counter < 0))
4569 return(NULL);
4570 xmlFAGenerateCountedTransition(am, from, to, counter);
4571 if (to == NULL)
4572 return(am->state);
4573 return(to);
4574}
Daniel Veillard4255d502002-04-16 15:50:10 +00004575
4576/**
4577 * xmlAutomataCompile:
4578 * @am: an automata
4579 *
4580 * Compile the automata into a Reg Exp ready for being executed.
4581 * The automata should be free after this point.
4582 *
4583 * Returns the compiled regexp or NULL in case of error
4584 */
4585xmlRegexpPtr
4586xmlAutomataCompile(xmlAutomataPtr am) {
4587 xmlRegexpPtr ret;
4588
Daniel Veillarda76fe5c2003-04-24 16:06:47 +00004589 if ((am == NULL) || (am->error != 0)) return(NULL);
Daniel Veillard4255d502002-04-16 15:50:10 +00004590 xmlFAEliminateEpsilonTransitions(am);
Daniel Veillard23e73572002-09-19 19:56:43 +00004591 /* xmlFAComputesDeterminism(am); */
Daniel Veillard4255d502002-04-16 15:50:10 +00004592 ret = xmlRegEpxFromParse(am);
4593
4594 return(ret);
4595}
Daniel Veillarde19fc232002-04-22 16:01:24 +00004596
4597/**
4598 * xmlAutomataIsDeterminist:
4599 * @am: an automata
4600 *
4601 * Checks if an automata is determinist.
4602 *
4603 * Returns 1 if true, 0 if not, and -1 in case of error
4604 */
4605int
4606xmlAutomataIsDeterminist(xmlAutomataPtr am) {
4607 int ret;
4608
4609 if (am == NULL)
4610 return(-1);
4611
4612 ret = xmlFAComputesDeterminism(am);
4613 return(ret);
4614}
Daniel Veillard4255d502002-04-16 15:50:10 +00004615#endif /* LIBXML_AUTOMATA_ENABLED */
4616#endif /* LIBXML_REGEXP_ENABLED */