/src/libprotobuf-mutator/build/examples/libxml2/external.libxml2/src/external.libxml2/xmlregexp.c
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
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/schemas mechanisms now available in |
6 | | * XML related specifications these include: |
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> |
24 | | #include <limits.h> |
25 | | |
26 | | #include <libxml/tree.h> |
27 | | #include <libxml/parserInternals.h> |
28 | | #include <libxml/xmlregexp.h> |
29 | | #include <libxml/xmlautomata.h> |
30 | | #include <libxml/xmlunicode.h> |
31 | | |
32 | | #include "private/error.h" |
33 | | #include "private/regexp.h" |
34 | | |
35 | | #ifndef SIZE_MAX |
36 | 0 | #define SIZE_MAX ((size_t) -1) |
37 | | #endif |
38 | | |
39 | 0 | #define MAX_PUSH 10000000 |
40 | | |
41 | | /* |
42 | | * -2 and -3 are used by xmlValidateElementType for other things. |
43 | | */ |
44 | 0 | #define XML_REGEXP_OK 0 |
45 | 0 | #define XML_REGEXP_NOT_FOUND (-1) |
46 | 0 | #define XML_REGEXP_INTERNAL_ERROR (-4) |
47 | 0 | #define XML_REGEXP_OUT_OF_MEMORY (-5) |
48 | 0 | #define XML_REGEXP_INTERNAL_LIMIT (-6) |
49 | 0 | #define XML_REGEXP_INVALID_UTF8 (-7) |
50 | | |
51 | | #ifdef ERROR |
52 | | #undef ERROR |
53 | | #endif |
54 | | #define ERROR(str) \ |
55 | 0 | ctxt->error = XML_REGEXP_COMPILE_ERROR; \ |
56 | 0 | xmlRegexpErrCompile(ctxt, str); |
57 | 0 | #define NEXT ctxt->cur++ |
58 | 0 | #define CUR (*(ctxt->cur)) |
59 | 0 | #define NXT(index) (ctxt->cur[index]) |
60 | | |
61 | 0 | #define NEXTL(l) ctxt->cur += l; |
62 | 0 | #define XML_REG_STRING_SEPARATOR '|' |
63 | | /* |
64 | | * Need PREV to check on a '-' within a Character Group. May only be used |
65 | | * when it's guaranteed that cur is not at the beginning of ctxt->string! |
66 | | */ |
67 | 0 | #define PREV (ctxt->cur[-1]) |
68 | | |
69 | | /** |
70 | | * TODO: |
71 | | * |
72 | | * macro to flag unimplemented blocks |
73 | | */ |
74 | | #define TODO \ |
75 | 0 | xmlGenericError(xmlGenericErrorContext, \ |
76 | 0 | "Unimplemented block at %s:%d\n", \ |
77 | 0 | __FILE__, __LINE__); |
78 | | |
79 | | /************************************************************************ |
80 | | * * |
81 | | * Datatypes and structures * |
82 | | * * |
83 | | ************************************************************************/ |
84 | | |
85 | | /* |
86 | | * Note: the order of the enums below is significant, do not shuffle |
87 | | */ |
88 | | typedef enum { |
89 | | XML_REGEXP_EPSILON = 1, |
90 | | XML_REGEXP_CHARVAL, |
91 | | XML_REGEXP_RANGES, |
92 | | XML_REGEXP_SUBREG, /* used for () sub regexps */ |
93 | | XML_REGEXP_STRING, |
94 | | XML_REGEXP_ANYCHAR, /* . */ |
95 | | XML_REGEXP_ANYSPACE, /* \s */ |
96 | | XML_REGEXP_NOTSPACE, /* \S */ |
97 | | XML_REGEXP_INITNAME, /* \l */ |
98 | | XML_REGEXP_NOTINITNAME, /* \L */ |
99 | | XML_REGEXP_NAMECHAR, /* \c */ |
100 | | XML_REGEXP_NOTNAMECHAR, /* \C */ |
101 | | XML_REGEXP_DECIMAL, /* \d */ |
102 | | XML_REGEXP_NOTDECIMAL, /* \D */ |
103 | | XML_REGEXP_REALCHAR, /* \w */ |
104 | | XML_REGEXP_NOTREALCHAR, /* \W */ |
105 | | XML_REGEXP_LETTER = 100, |
106 | | XML_REGEXP_LETTER_UPPERCASE, |
107 | | XML_REGEXP_LETTER_LOWERCASE, |
108 | | XML_REGEXP_LETTER_TITLECASE, |
109 | | XML_REGEXP_LETTER_MODIFIER, |
110 | | XML_REGEXP_LETTER_OTHERS, |
111 | | XML_REGEXP_MARK, |
112 | | XML_REGEXP_MARK_NONSPACING, |
113 | | XML_REGEXP_MARK_SPACECOMBINING, |
114 | | XML_REGEXP_MARK_ENCLOSING, |
115 | | XML_REGEXP_NUMBER, |
116 | | XML_REGEXP_NUMBER_DECIMAL, |
117 | | XML_REGEXP_NUMBER_LETTER, |
118 | | XML_REGEXP_NUMBER_OTHERS, |
119 | | XML_REGEXP_PUNCT, |
120 | | XML_REGEXP_PUNCT_CONNECTOR, |
121 | | XML_REGEXP_PUNCT_DASH, |
122 | | XML_REGEXP_PUNCT_OPEN, |
123 | | XML_REGEXP_PUNCT_CLOSE, |
124 | | XML_REGEXP_PUNCT_INITQUOTE, |
125 | | XML_REGEXP_PUNCT_FINQUOTE, |
126 | | XML_REGEXP_PUNCT_OTHERS, |
127 | | XML_REGEXP_SEPAR, |
128 | | XML_REGEXP_SEPAR_SPACE, |
129 | | XML_REGEXP_SEPAR_LINE, |
130 | | XML_REGEXP_SEPAR_PARA, |
131 | | XML_REGEXP_SYMBOL, |
132 | | XML_REGEXP_SYMBOL_MATH, |
133 | | XML_REGEXP_SYMBOL_CURRENCY, |
134 | | XML_REGEXP_SYMBOL_MODIFIER, |
135 | | XML_REGEXP_SYMBOL_OTHERS, |
136 | | XML_REGEXP_OTHER, |
137 | | XML_REGEXP_OTHER_CONTROL, |
138 | | XML_REGEXP_OTHER_FORMAT, |
139 | | XML_REGEXP_OTHER_PRIVATE, |
140 | | XML_REGEXP_OTHER_NA, |
141 | | XML_REGEXP_BLOCK_NAME |
142 | | } xmlRegAtomType; |
143 | | |
144 | | typedef enum { |
145 | | XML_REGEXP_QUANT_EPSILON = 1, |
146 | | XML_REGEXP_QUANT_ONCE, |
147 | | XML_REGEXP_QUANT_OPT, |
148 | | XML_REGEXP_QUANT_MULT, |
149 | | XML_REGEXP_QUANT_PLUS, |
150 | | XML_REGEXP_QUANT_ONCEONLY, |
151 | | XML_REGEXP_QUANT_ALL, |
152 | | XML_REGEXP_QUANT_RANGE |
153 | | } xmlRegQuantType; |
154 | | |
155 | | typedef enum { |
156 | | XML_REGEXP_START_STATE = 1, |
157 | | XML_REGEXP_FINAL_STATE, |
158 | | XML_REGEXP_TRANS_STATE, |
159 | | XML_REGEXP_SINK_STATE, |
160 | | XML_REGEXP_UNREACH_STATE |
161 | | } xmlRegStateType; |
162 | | |
163 | | typedef enum { |
164 | | XML_REGEXP_MARK_NORMAL = 0, |
165 | | XML_REGEXP_MARK_START, |
166 | | XML_REGEXP_MARK_VISITED |
167 | | } xmlRegMarkedType; |
168 | | |
169 | | typedef struct _xmlRegRange xmlRegRange; |
170 | | typedef xmlRegRange *xmlRegRangePtr; |
171 | | |
172 | | struct _xmlRegRange { |
173 | | int neg; /* 0 normal, 1 not, 2 exclude */ |
174 | | xmlRegAtomType type; |
175 | | int start; |
176 | | int end; |
177 | | xmlChar *blockName; |
178 | | }; |
179 | | |
180 | | typedef struct _xmlRegAtom xmlRegAtom; |
181 | | typedef xmlRegAtom *xmlRegAtomPtr; |
182 | | |
183 | | typedef struct _xmlAutomataState xmlRegState; |
184 | | typedef xmlRegState *xmlRegStatePtr; |
185 | | |
186 | | struct _xmlRegAtom { |
187 | | int no; |
188 | | xmlRegAtomType type; |
189 | | xmlRegQuantType quant; |
190 | | int min; |
191 | | int max; |
192 | | |
193 | | void *valuep; |
194 | | void *valuep2; |
195 | | int neg; |
196 | | int codepoint; |
197 | | xmlRegStatePtr start; |
198 | | xmlRegStatePtr start0; |
199 | | xmlRegStatePtr stop; |
200 | | int maxRanges; |
201 | | int nbRanges; |
202 | | xmlRegRangePtr *ranges; |
203 | | void *data; |
204 | | }; |
205 | | |
206 | | typedef struct _xmlRegCounter xmlRegCounter; |
207 | | typedef xmlRegCounter *xmlRegCounterPtr; |
208 | | |
209 | | struct _xmlRegCounter { |
210 | | int min; |
211 | | int max; |
212 | | }; |
213 | | |
214 | | typedef struct _xmlRegTrans xmlRegTrans; |
215 | | typedef xmlRegTrans *xmlRegTransPtr; |
216 | | |
217 | | struct _xmlRegTrans { |
218 | | xmlRegAtomPtr atom; |
219 | | int to; |
220 | | int counter; |
221 | | int count; |
222 | | int nd; |
223 | | }; |
224 | | |
225 | | struct _xmlAutomataState { |
226 | | xmlRegStateType type; |
227 | | xmlRegMarkedType mark; |
228 | | xmlRegMarkedType markd; |
229 | | xmlRegMarkedType reached; |
230 | | int no; |
231 | | int maxTrans; |
232 | | int nbTrans; |
233 | | xmlRegTrans *trans; |
234 | | /* knowing states pointing to us can speed things up */ |
235 | | int maxTransTo; |
236 | | int nbTransTo; |
237 | | int *transTo; |
238 | | }; |
239 | | |
240 | | typedef struct _xmlAutomata xmlRegParserCtxt; |
241 | | typedef xmlRegParserCtxt *xmlRegParserCtxtPtr; |
242 | | |
243 | 0 | #define AM_AUTOMATA_RNG 1 |
244 | | |
245 | | struct _xmlAutomata { |
246 | | xmlChar *string; |
247 | | xmlChar *cur; |
248 | | |
249 | | int error; |
250 | | int neg; |
251 | | |
252 | | xmlRegStatePtr start; |
253 | | xmlRegStatePtr end; |
254 | | xmlRegStatePtr state; |
255 | | |
256 | | xmlRegAtomPtr atom; |
257 | | |
258 | | int maxAtoms; |
259 | | int nbAtoms; |
260 | | xmlRegAtomPtr *atoms; |
261 | | |
262 | | int maxStates; |
263 | | int nbStates; |
264 | | xmlRegStatePtr *states; |
265 | | |
266 | | int maxCounters; |
267 | | int nbCounters; |
268 | | xmlRegCounter *counters; |
269 | | |
270 | | int determinist; |
271 | | int negs; |
272 | | int flags; |
273 | | |
274 | | int depth; |
275 | | }; |
276 | | |
277 | | struct _xmlRegexp { |
278 | | xmlChar *string; |
279 | | int nbStates; |
280 | | xmlRegStatePtr *states; |
281 | | int nbAtoms; |
282 | | xmlRegAtomPtr *atoms; |
283 | | int nbCounters; |
284 | | xmlRegCounter *counters; |
285 | | int determinist; |
286 | | int flags; |
287 | | /* |
288 | | * That's the compact form for determinists automatas |
289 | | */ |
290 | | int nbstates; |
291 | | int *compact; |
292 | | void **transdata; |
293 | | int nbstrings; |
294 | | xmlChar **stringMap; |
295 | | }; |
296 | | |
297 | | typedef struct _xmlRegExecRollback xmlRegExecRollback; |
298 | | typedef xmlRegExecRollback *xmlRegExecRollbackPtr; |
299 | | |
300 | | struct _xmlRegExecRollback { |
301 | | xmlRegStatePtr state;/* the current state */ |
302 | | int index; /* the index in the input stack */ |
303 | | int nextbranch; /* the next transition to explore in that state */ |
304 | | int *counts; /* save the automata state if it has some */ |
305 | | }; |
306 | | |
307 | | typedef struct _xmlRegInputToken xmlRegInputToken; |
308 | | typedef xmlRegInputToken *xmlRegInputTokenPtr; |
309 | | |
310 | | struct _xmlRegInputToken { |
311 | | xmlChar *value; |
312 | | void *data; |
313 | | }; |
314 | | |
315 | | struct _xmlRegExecCtxt { |
316 | | int status; /* execution status != 0 indicate an error */ |
317 | | int determinist; /* did we find an indeterministic behaviour */ |
318 | | xmlRegexpPtr comp; /* the compiled regexp */ |
319 | | xmlRegExecCallbacks callback; |
320 | | void *data; |
321 | | |
322 | | xmlRegStatePtr state;/* the current state */ |
323 | | int transno; /* the current transition on that state */ |
324 | | int transcount; /* the number of chars in char counted transitions */ |
325 | | |
326 | | /* |
327 | | * A stack of rollback states |
328 | | */ |
329 | | int maxRollbacks; |
330 | | int nbRollbacks; |
331 | | xmlRegExecRollback *rollbacks; |
332 | | |
333 | | /* |
334 | | * The state of the automata if any |
335 | | */ |
336 | | int *counts; |
337 | | |
338 | | /* |
339 | | * The input stack |
340 | | */ |
341 | | int inputStackMax; |
342 | | int inputStackNr; |
343 | | int index; |
344 | | int *charStack; |
345 | | const xmlChar *inputString; /* when operating on characters */ |
346 | | xmlRegInputTokenPtr inputStack;/* when operating on strings */ |
347 | | |
348 | | /* |
349 | | * error handling |
350 | | */ |
351 | | int errStateNo; /* the error state number */ |
352 | | xmlRegStatePtr errState; /* the error state */ |
353 | | xmlChar *errString; /* the string raising the error */ |
354 | | int *errCounts; /* counters at the error state */ |
355 | | int nbPush; |
356 | | }; |
357 | | |
358 | 0 | #define REGEXP_ALL_COUNTER 0x123456 |
359 | 0 | #define REGEXP_ALL_LAX_COUNTER 0x123457 |
360 | | |
361 | | static void xmlFAParseRegExp(xmlRegParserCtxtPtr ctxt, int top); |
362 | | static void xmlRegFreeState(xmlRegStatePtr state); |
363 | | static void xmlRegFreeAtom(xmlRegAtomPtr atom); |
364 | | static int xmlRegStrEqualWildcard(const xmlChar *expStr, const xmlChar *valStr); |
365 | | static int xmlRegCheckCharacter(xmlRegAtomPtr atom, int codepoint); |
366 | | static int xmlRegCheckCharacterRange(xmlRegAtomType type, int codepoint, |
367 | | int neg, int start, int end, const xmlChar *blockName); |
368 | | |
369 | | /************************************************************************ |
370 | | * * |
371 | | * Regexp memory error handler * |
372 | | * * |
373 | | ************************************************************************/ |
374 | | /** |
375 | | * xmlRegexpErrMemory: |
376 | | * @extra: extra information |
377 | | * |
378 | | * Handle an out of memory condition |
379 | | */ |
380 | | static void |
381 | | xmlRegexpErrMemory(xmlRegParserCtxtPtr ctxt, const char *extra) |
382 | 0 | { |
383 | 0 | const char *regexp = NULL; |
384 | 0 | if (ctxt != NULL) { |
385 | 0 | regexp = (const char *) ctxt->string; |
386 | 0 | ctxt->error = XML_ERR_NO_MEMORY; |
387 | 0 | } |
388 | 0 | __xmlRaiseError(NULL, NULL, NULL, NULL, NULL, XML_FROM_REGEXP, |
389 | 0 | XML_ERR_NO_MEMORY, XML_ERR_FATAL, NULL, 0, extra, |
390 | 0 | regexp, NULL, 0, 0, |
391 | 0 | "Memory allocation failed : %s\n", extra); |
392 | 0 | } |
393 | | |
394 | | /** |
395 | | * xmlRegexpErrCompile: |
396 | | * @extra: extra information |
397 | | * |
398 | | * Handle a compilation failure |
399 | | */ |
400 | | static void |
401 | | xmlRegexpErrCompile(xmlRegParserCtxtPtr ctxt, const char *extra) |
402 | 0 | { |
403 | 0 | const char *regexp = NULL; |
404 | 0 | int idx = 0; |
405 | |
|
406 | 0 | if (ctxt != NULL) { |
407 | 0 | regexp = (const char *) ctxt->string; |
408 | 0 | idx = ctxt->cur - ctxt->string; |
409 | 0 | ctxt->error = XML_REGEXP_COMPILE_ERROR; |
410 | 0 | } |
411 | 0 | __xmlRaiseError(NULL, NULL, NULL, NULL, NULL, XML_FROM_REGEXP, |
412 | 0 | XML_REGEXP_COMPILE_ERROR, XML_ERR_FATAL, NULL, 0, extra, |
413 | 0 | regexp, NULL, idx, 0, |
414 | 0 | "failed to compile: %s\n", extra); |
415 | 0 | } |
416 | | |
417 | | /************************************************************************ |
418 | | * * |
419 | | * Allocation/Deallocation * |
420 | | * * |
421 | | ************************************************************************/ |
422 | | |
423 | | static int xmlFAComputesDeterminism(xmlRegParserCtxtPtr ctxt); |
424 | | |
425 | | /** |
426 | | * xmlRegCalloc2: |
427 | | * @dim1: size of first dimension |
428 | | * @dim2: size of second dimension |
429 | | * @elemSize: size of element |
430 | | * |
431 | | * Allocate a two-dimensional array and set all elements to zero. |
432 | | * |
433 | | * Returns the new array or NULL in case of error. |
434 | | */ |
435 | | static void* |
436 | 0 | xmlRegCalloc2(size_t dim1, size_t dim2, size_t elemSize) { |
437 | 0 | size_t totalSize; |
438 | 0 | void *ret; |
439 | | |
440 | | /* Check for overflow */ |
441 | 0 | if ((dim2 == 0) || (elemSize == 0) || |
442 | 0 | (dim1 > SIZE_MAX / dim2 / elemSize)) |
443 | 0 | return (NULL); |
444 | 0 | totalSize = dim1 * dim2 * elemSize; |
445 | 0 | ret = xmlMalloc(totalSize); |
446 | 0 | if (ret != NULL) |
447 | 0 | memset(ret, 0, totalSize); |
448 | 0 | return (ret); |
449 | 0 | } |
450 | | |
451 | | /** |
452 | | * xmlRegEpxFromParse: |
453 | | * @ctxt: the parser context used to build it |
454 | | * |
455 | | * Allocate a new regexp and fill it with the result from the parser |
456 | | * |
457 | | * Returns the new regexp or NULL in case of error |
458 | | */ |
459 | | static xmlRegexpPtr |
460 | 0 | xmlRegEpxFromParse(xmlRegParserCtxtPtr ctxt) { |
461 | 0 | xmlRegexpPtr ret; |
462 | |
|
463 | 0 | ret = (xmlRegexpPtr) xmlMalloc(sizeof(xmlRegexp)); |
464 | 0 | if (ret == NULL) { |
465 | 0 | xmlRegexpErrMemory(ctxt, "compiling regexp"); |
466 | 0 | return(NULL); |
467 | 0 | } |
468 | 0 | memset(ret, 0, sizeof(xmlRegexp)); |
469 | 0 | ret->string = ctxt->string; |
470 | 0 | ret->nbStates = ctxt->nbStates; |
471 | 0 | ret->states = ctxt->states; |
472 | 0 | ret->nbAtoms = ctxt->nbAtoms; |
473 | 0 | ret->atoms = ctxt->atoms; |
474 | 0 | ret->nbCounters = ctxt->nbCounters; |
475 | 0 | ret->counters = ctxt->counters; |
476 | 0 | ret->determinist = ctxt->determinist; |
477 | 0 | ret->flags = ctxt->flags; |
478 | 0 | if (ret->determinist == -1) { |
479 | 0 | if (xmlRegexpIsDeterminist(ret) < 0) { |
480 | 0 | xmlRegexpErrMemory(ctxt, "checking determinism"); |
481 | 0 | xmlFree(ret); |
482 | 0 | return(NULL); |
483 | 0 | } |
484 | 0 | } |
485 | | |
486 | 0 | if ((ret->determinist != 0) && |
487 | 0 | (ret->nbCounters == 0) && |
488 | 0 | (ctxt->negs == 0) && |
489 | 0 | (ret->atoms != NULL) && |
490 | 0 | (ret->atoms[0] != NULL) && |
491 | 0 | (ret->atoms[0]->type == XML_REGEXP_STRING)) { |
492 | 0 | int i, j, nbstates = 0, nbatoms = 0; |
493 | 0 | int *stateRemap; |
494 | 0 | int *stringRemap; |
495 | 0 | int *transitions; |
496 | 0 | void **transdata; |
497 | 0 | xmlChar **stringMap; |
498 | 0 | xmlChar *value; |
499 | | |
500 | | /* |
501 | | * Switch to a compact representation |
502 | | * 1/ counting the effective number of states left |
503 | | * 2/ counting the unique number of atoms, and check that |
504 | | * they are all of the string type |
505 | | * 3/ build a table state x atom for the transitions |
506 | | */ |
507 | |
|
508 | 0 | stateRemap = xmlMalloc(ret->nbStates * sizeof(int)); |
509 | 0 | if (stateRemap == NULL) { |
510 | 0 | xmlRegexpErrMemory(ctxt, "compiling regexp"); |
511 | 0 | xmlFree(ret); |
512 | 0 | return(NULL); |
513 | 0 | } |
514 | 0 | for (i = 0;i < ret->nbStates;i++) { |
515 | 0 | if (ret->states[i] != NULL) { |
516 | 0 | stateRemap[i] = nbstates; |
517 | 0 | nbstates++; |
518 | 0 | } else { |
519 | 0 | stateRemap[i] = -1; |
520 | 0 | } |
521 | 0 | } |
522 | 0 | stringMap = xmlMalloc(ret->nbAtoms * sizeof(char *)); |
523 | 0 | if (stringMap == NULL) { |
524 | 0 | xmlRegexpErrMemory(ctxt, "compiling regexp"); |
525 | 0 | xmlFree(stateRemap); |
526 | 0 | xmlFree(ret); |
527 | 0 | return(NULL); |
528 | 0 | } |
529 | 0 | stringRemap = xmlMalloc(ret->nbAtoms * sizeof(int)); |
530 | 0 | if (stringRemap == NULL) { |
531 | 0 | xmlRegexpErrMemory(ctxt, "compiling regexp"); |
532 | 0 | xmlFree(stringMap); |
533 | 0 | xmlFree(stateRemap); |
534 | 0 | xmlFree(ret); |
535 | 0 | return(NULL); |
536 | 0 | } |
537 | 0 | for (i = 0;i < ret->nbAtoms;i++) { |
538 | 0 | if ((ret->atoms[i]->type == XML_REGEXP_STRING) && |
539 | 0 | (ret->atoms[i]->quant == XML_REGEXP_QUANT_ONCE)) { |
540 | 0 | value = ret->atoms[i]->valuep; |
541 | 0 | for (j = 0;j < nbatoms;j++) { |
542 | 0 | if (xmlStrEqual(stringMap[j], value)) { |
543 | 0 | stringRemap[i] = j; |
544 | 0 | break; |
545 | 0 | } |
546 | 0 | } |
547 | 0 | if (j >= nbatoms) { |
548 | 0 | stringRemap[i] = nbatoms; |
549 | 0 | stringMap[nbatoms] = xmlStrdup(value); |
550 | 0 | if (stringMap[nbatoms] == NULL) { |
551 | 0 | for (i = 0;i < nbatoms;i++) |
552 | 0 | xmlFree(stringMap[i]); |
553 | 0 | xmlFree(stringRemap); |
554 | 0 | xmlFree(stringMap); |
555 | 0 | xmlFree(stateRemap); |
556 | 0 | xmlFree(ret); |
557 | 0 | return(NULL); |
558 | 0 | } |
559 | 0 | nbatoms++; |
560 | 0 | } |
561 | 0 | } else { |
562 | 0 | xmlFree(stateRemap); |
563 | 0 | xmlFree(stringRemap); |
564 | 0 | for (i = 0;i < nbatoms;i++) |
565 | 0 | xmlFree(stringMap[i]); |
566 | 0 | xmlFree(stringMap); |
567 | 0 | xmlFree(ret); |
568 | 0 | return(NULL); |
569 | 0 | } |
570 | 0 | } |
571 | 0 | transitions = (int *) xmlRegCalloc2(nbstates + 1, nbatoms + 1, |
572 | 0 | sizeof(int)); |
573 | 0 | if (transitions == NULL) { |
574 | 0 | xmlFree(stateRemap); |
575 | 0 | xmlFree(stringRemap); |
576 | 0 | for (i = 0;i < nbatoms;i++) |
577 | 0 | xmlFree(stringMap[i]); |
578 | 0 | xmlFree(stringMap); |
579 | 0 | xmlFree(ret); |
580 | 0 | return(NULL); |
581 | 0 | } |
582 | | |
583 | | /* |
584 | | * Allocate the transition table. The first entry for each |
585 | | * state corresponds to the state type. |
586 | | */ |
587 | 0 | transdata = NULL; |
588 | |
|
589 | 0 | for (i = 0;i < ret->nbStates;i++) { |
590 | 0 | int stateno, atomno, targetno, prev; |
591 | 0 | xmlRegStatePtr state; |
592 | 0 | xmlRegTransPtr trans; |
593 | |
|
594 | 0 | stateno = stateRemap[i]; |
595 | 0 | if (stateno == -1) |
596 | 0 | continue; |
597 | 0 | state = ret->states[i]; |
598 | |
|
599 | 0 | transitions[stateno * (nbatoms + 1)] = state->type; |
600 | |
|
601 | 0 | for (j = 0;j < state->nbTrans;j++) { |
602 | 0 | trans = &(state->trans[j]); |
603 | 0 | if ((trans->to < 0) || (trans->atom == NULL)) |
604 | 0 | continue; |
605 | 0 | atomno = stringRemap[trans->atom->no]; |
606 | 0 | if ((trans->atom->data != NULL) && (transdata == NULL)) { |
607 | 0 | transdata = (void **) xmlRegCalloc2(nbstates, nbatoms, |
608 | 0 | sizeof(void *)); |
609 | 0 | if (transdata == NULL) { |
610 | 0 | xmlRegexpErrMemory(ctxt, "compiling regexp"); |
611 | 0 | break; |
612 | 0 | } |
613 | 0 | } |
614 | 0 | targetno = stateRemap[trans->to]; |
615 | | /* |
616 | | * if the same atom can generate transitions to 2 different |
617 | | * states then it means the automata is not deterministic and |
618 | | * the compact form can't be used ! |
619 | | */ |
620 | 0 | prev = transitions[stateno * (nbatoms + 1) + atomno + 1]; |
621 | 0 | if (prev != 0) { |
622 | 0 | if (prev != targetno + 1) { |
623 | 0 | ret->determinist = 0; |
624 | 0 | if (transdata != NULL) |
625 | 0 | xmlFree(transdata); |
626 | 0 | xmlFree(transitions); |
627 | 0 | xmlFree(stateRemap); |
628 | 0 | xmlFree(stringRemap); |
629 | 0 | for (i = 0;i < nbatoms;i++) |
630 | 0 | xmlFree(stringMap[i]); |
631 | 0 | xmlFree(stringMap); |
632 | 0 | goto not_determ; |
633 | 0 | } |
634 | 0 | } else { |
635 | | #if 0 |
636 | | printf("State %d trans %d: atom %d to %d : %d to %d\n", |
637 | | i, j, trans->atom->no, trans->to, atomno, targetno); |
638 | | #endif |
639 | 0 | transitions[stateno * (nbatoms + 1) + atomno + 1] = |
640 | 0 | targetno + 1; /* to avoid 0 */ |
641 | 0 | if (transdata != NULL) |
642 | 0 | transdata[stateno * nbatoms + atomno] = |
643 | 0 | trans->atom->data; |
644 | 0 | } |
645 | 0 | } |
646 | 0 | } |
647 | 0 | ret->determinist = 1; |
648 | | /* |
649 | | * Cleanup of the old data |
650 | | */ |
651 | 0 | if (ret->states != NULL) { |
652 | 0 | for (i = 0;i < ret->nbStates;i++) |
653 | 0 | xmlRegFreeState(ret->states[i]); |
654 | 0 | xmlFree(ret->states); |
655 | 0 | } |
656 | 0 | ret->states = NULL; |
657 | 0 | ret->nbStates = 0; |
658 | 0 | if (ret->atoms != NULL) { |
659 | 0 | for (i = 0;i < ret->nbAtoms;i++) |
660 | 0 | xmlRegFreeAtom(ret->atoms[i]); |
661 | 0 | xmlFree(ret->atoms); |
662 | 0 | } |
663 | 0 | ret->atoms = NULL; |
664 | 0 | ret->nbAtoms = 0; |
665 | |
|
666 | 0 | ret->compact = transitions; |
667 | 0 | ret->transdata = transdata; |
668 | 0 | ret->stringMap = stringMap; |
669 | 0 | ret->nbstrings = nbatoms; |
670 | 0 | ret->nbstates = nbstates; |
671 | 0 | xmlFree(stateRemap); |
672 | 0 | xmlFree(stringRemap); |
673 | 0 | } |
674 | 0 | not_determ: |
675 | 0 | ctxt->string = NULL; |
676 | 0 | ctxt->nbStates = 0; |
677 | 0 | ctxt->states = NULL; |
678 | 0 | ctxt->nbAtoms = 0; |
679 | 0 | ctxt->atoms = NULL; |
680 | 0 | ctxt->nbCounters = 0; |
681 | 0 | ctxt->counters = NULL; |
682 | 0 | return(ret); |
683 | 0 | } |
684 | | |
685 | | /** |
686 | | * xmlRegNewParserCtxt: |
687 | | * @string: the string to parse |
688 | | * |
689 | | * Allocate a new regexp parser context |
690 | | * |
691 | | * Returns the new context or NULL in case of error |
692 | | */ |
693 | | static xmlRegParserCtxtPtr |
694 | 0 | xmlRegNewParserCtxt(const xmlChar *string) { |
695 | 0 | xmlRegParserCtxtPtr ret; |
696 | |
|
697 | 0 | ret = (xmlRegParserCtxtPtr) xmlMalloc(sizeof(xmlRegParserCtxt)); |
698 | 0 | if (ret == NULL) |
699 | 0 | return(NULL); |
700 | 0 | memset(ret, 0, sizeof(xmlRegParserCtxt)); |
701 | 0 | if (string != NULL) |
702 | 0 | ret->string = xmlStrdup(string); |
703 | 0 | ret->cur = ret->string; |
704 | 0 | ret->neg = 0; |
705 | 0 | ret->negs = 0; |
706 | 0 | ret->error = 0; |
707 | 0 | ret->determinist = -1; |
708 | 0 | return(ret); |
709 | 0 | } |
710 | | |
711 | | /** |
712 | | * xmlRegNewRange: |
713 | | * @ctxt: the regexp parser context |
714 | | * @neg: is that negative |
715 | | * @type: the type of range |
716 | | * @start: the start codepoint |
717 | | * @end: the end codepoint |
718 | | * |
719 | | * Allocate a new regexp range |
720 | | * |
721 | | * Returns the new range or NULL in case of error |
722 | | */ |
723 | | static xmlRegRangePtr |
724 | | xmlRegNewRange(xmlRegParserCtxtPtr ctxt, |
725 | 0 | int neg, xmlRegAtomType type, int start, int end) { |
726 | 0 | xmlRegRangePtr ret; |
727 | |
|
728 | 0 | ret = (xmlRegRangePtr) xmlMalloc(sizeof(xmlRegRange)); |
729 | 0 | if (ret == NULL) { |
730 | 0 | xmlRegexpErrMemory(ctxt, "allocating range"); |
731 | 0 | return(NULL); |
732 | 0 | } |
733 | 0 | ret->neg = neg; |
734 | 0 | ret->type = type; |
735 | 0 | ret->start = start; |
736 | 0 | ret->end = end; |
737 | 0 | return(ret); |
738 | 0 | } |
739 | | |
740 | | /** |
741 | | * xmlRegFreeRange: |
742 | | * @range: the regexp range |
743 | | * |
744 | | * Free a regexp range |
745 | | */ |
746 | | static void |
747 | 0 | xmlRegFreeRange(xmlRegRangePtr range) { |
748 | 0 | if (range == NULL) |
749 | 0 | return; |
750 | | |
751 | 0 | if (range->blockName != NULL) |
752 | 0 | xmlFree(range->blockName); |
753 | 0 | xmlFree(range); |
754 | 0 | } |
755 | | |
756 | | /** |
757 | | * xmlRegCopyRange: |
758 | | * @range: the regexp range |
759 | | * |
760 | | * Copy a regexp range |
761 | | * |
762 | | * Returns the new copy or NULL in case of error. |
763 | | */ |
764 | | static xmlRegRangePtr |
765 | 0 | xmlRegCopyRange(xmlRegParserCtxtPtr ctxt, xmlRegRangePtr range) { |
766 | 0 | xmlRegRangePtr ret; |
767 | |
|
768 | 0 | if (range == NULL) |
769 | 0 | return(NULL); |
770 | | |
771 | 0 | ret = xmlRegNewRange(ctxt, range->neg, range->type, range->start, |
772 | 0 | range->end); |
773 | 0 | if (ret == NULL) |
774 | 0 | return(NULL); |
775 | 0 | if (range->blockName != NULL) { |
776 | 0 | ret->blockName = xmlStrdup(range->blockName); |
777 | 0 | if (ret->blockName == NULL) { |
778 | 0 | xmlRegexpErrMemory(ctxt, "allocating range"); |
779 | 0 | xmlRegFreeRange(ret); |
780 | 0 | return(NULL); |
781 | 0 | } |
782 | 0 | } |
783 | 0 | return(ret); |
784 | 0 | } |
785 | | |
786 | | /** |
787 | | * xmlRegNewAtom: |
788 | | * @ctxt: the regexp parser context |
789 | | * @type: the type of atom |
790 | | * |
791 | | * Allocate a new atom |
792 | | * |
793 | | * Returns the new atom or NULL in case of error |
794 | | */ |
795 | | static xmlRegAtomPtr |
796 | 0 | xmlRegNewAtom(xmlRegParserCtxtPtr ctxt, xmlRegAtomType type) { |
797 | 0 | xmlRegAtomPtr ret; |
798 | |
|
799 | 0 | ret = (xmlRegAtomPtr) xmlMalloc(sizeof(xmlRegAtom)); |
800 | 0 | if (ret == NULL) { |
801 | 0 | xmlRegexpErrMemory(ctxt, "allocating atom"); |
802 | 0 | return(NULL); |
803 | 0 | } |
804 | 0 | memset(ret, 0, sizeof(xmlRegAtom)); |
805 | 0 | ret->type = type; |
806 | 0 | ret->quant = XML_REGEXP_QUANT_ONCE; |
807 | 0 | ret->min = 0; |
808 | 0 | ret->max = 0; |
809 | 0 | return(ret); |
810 | 0 | } |
811 | | |
812 | | /** |
813 | | * xmlRegFreeAtom: |
814 | | * @atom: the regexp atom |
815 | | * |
816 | | * Free a regexp atom |
817 | | */ |
818 | | static void |
819 | 0 | xmlRegFreeAtom(xmlRegAtomPtr atom) { |
820 | 0 | int i; |
821 | |
|
822 | 0 | if (atom == NULL) |
823 | 0 | return; |
824 | | |
825 | 0 | for (i = 0;i < atom->nbRanges;i++) |
826 | 0 | xmlRegFreeRange(atom->ranges[i]); |
827 | 0 | if (atom->ranges != NULL) |
828 | 0 | xmlFree(atom->ranges); |
829 | 0 | if ((atom->type == XML_REGEXP_STRING) && (atom->valuep != NULL)) |
830 | 0 | xmlFree(atom->valuep); |
831 | 0 | if ((atom->type == XML_REGEXP_STRING) && (atom->valuep2 != NULL)) |
832 | 0 | xmlFree(atom->valuep2); |
833 | 0 | if ((atom->type == XML_REGEXP_BLOCK_NAME) && (atom->valuep != NULL)) |
834 | 0 | xmlFree(atom->valuep); |
835 | 0 | xmlFree(atom); |
836 | 0 | } |
837 | | |
838 | | /** |
839 | | * xmlRegCopyAtom: |
840 | | * @ctxt: the regexp parser context |
841 | | * @atom: the original atom |
842 | | * |
843 | | * Allocate a new regexp range |
844 | | * |
845 | | * Returns the new atom or NULL in case of error |
846 | | */ |
847 | | static xmlRegAtomPtr |
848 | 0 | xmlRegCopyAtom(xmlRegParserCtxtPtr ctxt, xmlRegAtomPtr atom) { |
849 | 0 | xmlRegAtomPtr ret; |
850 | |
|
851 | 0 | ret = (xmlRegAtomPtr) xmlMalloc(sizeof(xmlRegAtom)); |
852 | 0 | if (ret == NULL) { |
853 | 0 | xmlRegexpErrMemory(ctxt, "copying atom"); |
854 | 0 | return(NULL); |
855 | 0 | } |
856 | 0 | memset(ret, 0, sizeof(xmlRegAtom)); |
857 | 0 | ret->type = atom->type; |
858 | 0 | ret->quant = atom->quant; |
859 | 0 | ret->min = atom->min; |
860 | 0 | ret->max = atom->max; |
861 | 0 | if (atom->nbRanges > 0) { |
862 | 0 | int i; |
863 | |
|
864 | 0 | ret->ranges = (xmlRegRangePtr *) xmlMalloc(sizeof(xmlRegRangePtr) * |
865 | 0 | atom->nbRanges); |
866 | 0 | if (ret->ranges == NULL) { |
867 | 0 | xmlRegexpErrMemory(ctxt, "copying atom"); |
868 | 0 | goto error; |
869 | 0 | } |
870 | 0 | for (i = 0;i < atom->nbRanges;i++) { |
871 | 0 | ret->ranges[i] = xmlRegCopyRange(ctxt, atom->ranges[i]); |
872 | 0 | if (ret->ranges[i] == NULL) |
873 | 0 | goto error; |
874 | 0 | ret->nbRanges = i + 1; |
875 | 0 | } |
876 | 0 | } |
877 | 0 | return(ret); |
878 | | |
879 | 0 | error: |
880 | 0 | xmlRegFreeAtom(ret); |
881 | 0 | return(NULL); |
882 | 0 | } |
883 | | |
884 | | static xmlRegStatePtr |
885 | 0 | xmlRegNewState(xmlRegParserCtxtPtr ctxt) { |
886 | 0 | xmlRegStatePtr ret; |
887 | |
|
888 | 0 | ret = (xmlRegStatePtr) xmlMalloc(sizeof(xmlRegState)); |
889 | 0 | if (ret == NULL) { |
890 | 0 | xmlRegexpErrMemory(ctxt, "allocating state"); |
891 | 0 | return(NULL); |
892 | 0 | } |
893 | 0 | memset(ret, 0, sizeof(xmlRegState)); |
894 | 0 | ret->type = XML_REGEXP_TRANS_STATE; |
895 | 0 | ret->mark = XML_REGEXP_MARK_NORMAL; |
896 | 0 | return(ret); |
897 | 0 | } |
898 | | |
899 | | /** |
900 | | * xmlRegFreeState: |
901 | | * @state: the regexp state |
902 | | * |
903 | | * Free a regexp state |
904 | | */ |
905 | | static void |
906 | 0 | xmlRegFreeState(xmlRegStatePtr state) { |
907 | 0 | if (state == NULL) |
908 | 0 | return; |
909 | | |
910 | 0 | if (state->trans != NULL) |
911 | 0 | xmlFree(state->trans); |
912 | 0 | if (state->transTo != NULL) |
913 | 0 | xmlFree(state->transTo); |
914 | 0 | xmlFree(state); |
915 | 0 | } |
916 | | |
917 | | /** |
918 | | * xmlRegFreeParserCtxt: |
919 | | * @ctxt: the regexp parser context |
920 | | * |
921 | | * Free a regexp parser context |
922 | | */ |
923 | | static void |
924 | 0 | xmlRegFreeParserCtxt(xmlRegParserCtxtPtr ctxt) { |
925 | 0 | int i; |
926 | 0 | if (ctxt == NULL) |
927 | 0 | return; |
928 | | |
929 | 0 | if (ctxt->string != NULL) |
930 | 0 | xmlFree(ctxt->string); |
931 | 0 | if (ctxt->states != NULL) { |
932 | 0 | for (i = 0;i < ctxt->nbStates;i++) |
933 | 0 | xmlRegFreeState(ctxt->states[i]); |
934 | 0 | xmlFree(ctxt->states); |
935 | 0 | } |
936 | 0 | if (ctxt->atoms != NULL) { |
937 | 0 | for (i = 0;i < ctxt->nbAtoms;i++) |
938 | 0 | xmlRegFreeAtom(ctxt->atoms[i]); |
939 | 0 | xmlFree(ctxt->atoms); |
940 | 0 | } |
941 | 0 | if (ctxt->counters != NULL) |
942 | 0 | xmlFree(ctxt->counters); |
943 | 0 | xmlFree(ctxt); |
944 | 0 | } |
945 | | |
946 | | /************************************************************************ |
947 | | * * |
948 | | * Display of Data structures * |
949 | | * * |
950 | | ************************************************************************/ |
951 | | |
952 | | static void |
953 | 0 | xmlRegPrintAtomType(FILE *output, xmlRegAtomType type) { |
954 | 0 | switch (type) { |
955 | 0 | case XML_REGEXP_EPSILON: |
956 | 0 | fprintf(output, "epsilon "); break; |
957 | 0 | case XML_REGEXP_CHARVAL: |
958 | 0 | fprintf(output, "charval "); break; |
959 | 0 | case XML_REGEXP_RANGES: |
960 | 0 | fprintf(output, "ranges "); break; |
961 | 0 | case XML_REGEXP_SUBREG: |
962 | 0 | fprintf(output, "subexpr "); break; |
963 | 0 | case XML_REGEXP_STRING: |
964 | 0 | fprintf(output, "string "); break; |
965 | 0 | case XML_REGEXP_ANYCHAR: |
966 | 0 | fprintf(output, "anychar "); break; |
967 | 0 | case XML_REGEXP_ANYSPACE: |
968 | 0 | fprintf(output, "anyspace "); break; |
969 | 0 | case XML_REGEXP_NOTSPACE: |
970 | 0 | fprintf(output, "notspace "); break; |
971 | 0 | case XML_REGEXP_INITNAME: |
972 | 0 | fprintf(output, "initname "); break; |
973 | 0 | case XML_REGEXP_NOTINITNAME: |
974 | 0 | fprintf(output, "notinitname "); break; |
975 | 0 | case XML_REGEXP_NAMECHAR: |
976 | 0 | fprintf(output, "namechar "); break; |
977 | 0 | case XML_REGEXP_NOTNAMECHAR: |
978 | 0 | fprintf(output, "notnamechar "); break; |
979 | 0 | case XML_REGEXP_DECIMAL: |
980 | 0 | fprintf(output, "decimal "); break; |
981 | 0 | case XML_REGEXP_NOTDECIMAL: |
982 | 0 | fprintf(output, "notdecimal "); break; |
983 | 0 | case XML_REGEXP_REALCHAR: |
984 | 0 | fprintf(output, "realchar "); break; |
985 | 0 | case XML_REGEXP_NOTREALCHAR: |
986 | 0 | fprintf(output, "notrealchar "); break; |
987 | 0 | case XML_REGEXP_LETTER: |
988 | 0 | fprintf(output, "LETTER "); break; |
989 | 0 | case XML_REGEXP_LETTER_UPPERCASE: |
990 | 0 | fprintf(output, "LETTER_UPPERCASE "); break; |
991 | 0 | case XML_REGEXP_LETTER_LOWERCASE: |
992 | 0 | fprintf(output, "LETTER_LOWERCASE "); break; |
993 | 0 | case XML_REGEXP_LETTER_TITLECASE: |
994 | 0 | fprintf(output, "LETTER_TITLECASE "); break; |
995 | 0 | case XML_REGEXP_LETTER_MODIFIER: |
996 | 0 | fprintf(output, "LETTER_MODIFIER "); break; |
997 | 0 | case XML_REGEXP_LETTER_OTHERS: |
998 | 0 | fprintf(output, "LETTER_OTHERS "); break; |
999 | 0 | case XML_REGEXP_MARK: |
1000 | 0 | fprintf(output, "MARK "); break; |
1001 | 0 | case XML_REGEXP_MARK_NONSPACING: |
1002 | 0 | fprintf(output, "MARK_NONSPACING "); break; |
1003 | 0 | case XML_REGEXP_MARK_SPACECOMBINING: |
1004 | 0 | fprintf(output, "MARK_SPACECOMBINING "); break; |
1005 | 0 | case XML_REGEXP_MARK_ENCLOSING: |
1006 | 0 | fprintf(output, "MARK_ENCLOSING "); break; |
1007 | 0 | case XML_REGEXP_NUMBER: |
1008 | 0 | fprintf(output, "NUMBER "); break; |
1009 | 0 | case XML_REGEXP_NUMBER_DECIMAL: |
1010 | 0 | fprintf(output, "NUMBER_DECIMAL "); break; |
1011 | 0 | case XML_REGEXP_NUMBER_LETTER: |
1012 | 0 | fprintf(output, "NUMBER_LETTER "); break; |
1013 | 0 | case XML_REGEXP_NUMBER_OTHERS: |
1014 | 0 | fprintf(output, "NUMBER_OTHERS "); break; |
1015 | 0 | case XML_REGEXP_PUNCT: |
1016 | 0 | fprintf(output, "PUNCT "); break; |
1017 | 0 | case XML_REGEXP_PUNCT_CONNECTOR: |
1018 | 0 | fprintf(output, "PUNCT_CONNECTOR "); break; |
1019 | 0 | case XML_REGEXP_PUNCT_DASH: |
1020 | 0 | fprintf(output, "PUNCT_DASH "); break; |
1021 | 0 | case XML_REGEXP_PUNCT_OPEN: |
1022 | 0 | fprintf(output, "PUNCT_OPEN "); break; |
1023 | 0 | case XML_REGEXP_PUNCT_CLOSE: |
1024 | 0 | fprintf(output, "PUNCT_CLOSE "); break; |
1025 | 0 | case XML_REGEXP_PUNCT_INITQUOTE: |
1026 | 0 | fprintf(output, "PUNCT_INITQUOTE "); break; |
1027 | 0 | case XML_REGEXP_PUNCT_FINQUOTE: |
1028 | 0 | fprintf(output, "PUNCT_FINQUOTE "); break; |
1029 | 0 | case XML_REGEXP_PUNCT_OTHERS: |
1030 | 0 | fprintf(output, "PUNCT_OTHERS "); break; |
1031 | 0 | case XML_REGEXP_SEPAR: |
1032 | 0 | fprintf(output, "SEPAR "); break; |
1033 | 0 | case XML_REGEXP_SEPAR_SPACE: |
1034 | 0 | fprintf(output, "SEPAR_SPACE "); break; |
1035 | 0 | case XML_REGEXP_SEPAR_LINE: |
1036 | 0 | fprintf(output, "SEPAR_LINE "); break; |
1037 | 0 | case XML_REGEXP_SEPAR_PARA: |
1038 | 0 | fprintf(output, "SEPAR_PARA "); break; |
1039 | 0 | case XML_REGEXP_SYMBOL: |
1040 | 0 | fprintf(output, "SYMBOL "); break; |
1041 | 0 | case XML_REGEXP_SYMBOL_MATH: |
1042 | 0 | fprintf(output, "SYMBOL_MATH "); break; |
1043 | 0 | case XML_REGEXP_SYMBOL_CURRENCY: |
1044 | 0 | fprintf(output, "SYMBOL_CURRENCY "); break; |
1045 | 0 | case XML_REGEXP_SYMBOL_MODIFIER: |
1046 | 0 | fprintf(output, "SYMBOL_MODIFIER "); break; |
1047 | 0 | case XML_REGEXP_SYMBOL_OTHERS: |
1048 | 0 | fprintf(output, "SYMBOL_OTHERS "); break; |
1049 | 0 | case XML_REGEXP_OTHER: |
1050 | 0 | fprintf(output, "OTHER "); break; |
1051 | 0 | case XML_REGEXP_OTHER_CONTROL: |
1052 | 0 | fprintf(output, "OTHER_CONTROL "); break; |
1053 | 0 | case XML_REGEXP_OTHER_FORMAT: |
1054 | 0 | fprintf(output, "OTHER_FORMAT "); break; |
1055 | 0 | case XML_REGEXP_OTHER_PRIVATE: |
1056 | 0 | fprintf(output, "OTHER_PRIVATE "); break; |
1057 | 0 | case XML_REGEXP_OTHER_NA: |
1058 | 0 | fprintf(output, "OTHER_NA "); break; |
1059 | 0 | case XML_REGEXP_BLOCK_NAME: |
1060 | 0 | fprintf(output, "BLOCK "); break; |
1061 | 0 | } |
1062 | 0 | } |
1063 | | |
1064 | | static void |
1065 | 0 | xmlRegPrintQuantType(FILE *output, xmlRegQuantType type) { |
1066 | 0 | switch (type) { |
1067 | 0 | case XML_REGEXP_QUANT_EPSILON: |
1068 | 0 | fprintf(output, "epsilon "); break; |
1069 | 0 | case XML_REGEXP_QUANT_ONCE: |
1070 | 0 | fprintf(output, "once "); break; |
1071 | 0 | case XML_REGEXP_QUANT_OPT: |
1072 | 0 | fprintf(output, "? "); break; |
1073 | 0 | case XML_REGEXP_QUANT_MULT: |
1074 | 0 | fprintf(output, "* "); break; |
1075 | 0 | case XML_REGEXP_QUANT_PLUS: |
1076 | 0 | fprintf(output, "+ "); break; |
1077 | 0 | case XML_REGEXP_QUANT_RANGE: |
1078 | 0 | fprintf(output, "range "); break; |
1079 | 0 | case XML_REGEXP_QUANT_ONCEONLY: |
1080 | 0 | fprintf(output, "onceonly "); break; |
1081 | 0 | case XML_REGEXP_QUANT_ALL: |
1082 | 0 | fprintf(output, "all "); break; |
1083 | 0 | } |
1084 | 0 | } |
1085 | | static void |
1086 | 0 | xmlRegPrintRange(FILE *output, xmlRegRangePtr range) { |
1087 | 0 | fprintf(output, " range: "); |
1088 | 0 | if (range->neg) |
1089 | 0 | fprintf(output, "negative "); |
1090 | 0 | xmlRegPrintAtomType(output, range->type); |
1091 | 0 | fprintf(output, "%c - %c\n", range->start, range->end); |
1092 | 0 | } |
1093 | | |
1094 | | static void |
1095 | 0 | xmlRegPrintAtom(FILE *output, xmlRegAtomPtr atom) { |
1096 | 0 | fprintf(output, " atom: "); |
1097 | 0 | if (atom == NULL) { |
1098 | 0 | fprintf(output, "NULL\n"); |
1099 | 0 | return; |
1100 | 0 | } |
1101 | 0 | if (atom->neg) |
1102 | 0 | fprintf(output, "not "); |
1103 | 0 | xmlRegPrintAtomType(output, atom->type); |
1104 | 0 | xmlRegPrintQuantType(output, atom->quant); |
1105 | 0 | if (atom->quant == XML_REGEXP_QUANT_RANGE) |
1106 | 0 | fprintf(output, "%d-%d ", atom->min, atom->max); |
1107 | 0 | if (atom->type == XML_REGEXP_STRING) |
1108 | 0 | fprintf(output, "'%s' ", (char *) atom->valuep); |
1109 | 0 | if (atom->type == XML_REGEXP_CHARVAL) |
1110 | 0 | fprintf(output, "char %c\n", atom->codepoint); |
1111 | 0 | else if (atom->type == XML_REGEXP_RANGES) { |
1112 | 0 | int i; |
1113 | 0 | fprintf(output, "%d entries\n", atom->nbRanges); |
1114 | 0 | for (i = 0; i < atom->nbRanges;i++) |
1115 | 0 | xmlRegPrintRange(output, atom->ranges[i]); |
1116 | 0 | } else if (atom->type == XML_REGEXP_SUBREG) { |
1117 | 0 | fprintf(output, "start %d end %d\n", atom->start->no, atom->stop->no); |
1118 | 0 | } else { |
1119 | 0 | fprintf(output, "\n"); |
1120 | 0 | } |
1121 | 0 | } |
1122 | | |
1123 | | static void |
1124 | 0 | xmlRegPrintTrans(FILE *output, xmlRegTransPtr trans) { |
1125 | 0 | fprintf(output, " trans: "); |
1126 | 0 | if (trans == NULL) { |
1127 | 0 | fprintf(output, "NULL\n"); |
1128 | 0 | return; |
1129 | 0 | } |
1130 | 0 | if (trans->to < 0) { |
1131 | 0 | fprintf(output, "removed\n"); |
1132 | 0 | return; |
1133 | 0 | } |
1134 | 0 | if (trans->nd != 0) { |
1135 | 0 | if (trans->nd == 2) |
1136 | 0 | fprintf(output, "last not determinist, "); |
1137 | 0 | else |
1138 | 0 | fprintf(output, "not determinist, "); |
1139 | 0 | } |
1140 | 0 | if (trans->counter >= 0) { |
1141 | 0 | fprintf(output, "counted %d, ", trans->counter); |
1142 | 0 | } |
1143 | 0 | if (trans->count == REGEXP_ALL_COUNTER) { |
1144 | 0 | fprintf(output, "all transition, "); |
1145 | 0 | } else if (trans->count >= 0) { |
1146 | 0 | fprintf(output, "count based %d, ", trans->count); |
1147 | 0 | } |
1148 | 0 | if (trans->atom == NULL) { |
1149 | 0 | fprintf(output, "epsilon to %d\n", trans->to); |
1150 | 0 | return; |
1151 | 0 | } |
1152 | 0 | if (trans->atom->type == XML_REGEXP_CHARVAL) |
1153 | 0 | fprintf(output, "char %c ", trans->atom->codepoint); |
1154 | 0 | fprintf(output, "atom %d, to %d\n", trans->atom->no, trans->to); |
1155 | 0 | } |
1156 | | |
1157 | | static void |
1158 | 0 | xmlRegPrintState(FILE *output, xmlRegStatePtr state) { |
1159 | 0 | int i; |
1160 | |
|
1161 | 0 | fprintf(output, " state: "); |
1162 | 0 | if (state == NULL) { |
1163 | 0 | fprintf(output, "NULL\n"); |
1164 | 0 | return; |
1165 | 0 | } |
1166 | 0 | if (state->type == XML_REGEXP_START_STATE) |
1167 | 0 | fprintf(output, "START "); |
1168 | 0 | if (state->type == XML_REGEXP_FINAL_STATE) |
1169 | 0 | fprintf(output, "FINAL "); |
1170 | |
|
1171 | 0 | fprintf(output, "%d, %d transitions:\n", state->no, state->nbTrans); |
1172 | 0 | for (i = 0;i < state->nbTrans; i++) { |
1173 | 0 | xmlRegPrintTrans(output, &(state->trans[i])); |
1174 | 0 | } |
1175 | 0 | } |
1176 | | |
1177 | | /************************************************************************ |
1178 | | * * |
1179 | | * Finite Automata structures manipulations * |
1180 | | * * |
1181 | | ************************************************************************/ |
1182 | | |
1183 | | static xmlRegRangePtr |
1184 | | xmlRegAtomAddRange(xmlRegParserCtxtPtr ctxt, xmlRegAtomPtr atom, |
1185 | | int neg, xmlRegAtomType type, int start, int end, |
1186 | 0 | xmlChar *blockName) { |
1187 | 0 | xmlRegRangePtr range; |
1188 | |
|
1189 | 0 | if (atom == NULL) { |
1190 | 0 | ERROR("add range: atom is NULL"); |
1191 | 0 | return(NULL); |
1192 | 0 | } |
1193 | 0 | if (atom->type != XML_REGEXP_RANGES) { |
1194 | 0 | ERROR("add range: atom is not ranges"); |
1195 | 0 | return(NULL); |
1196 | 0 | } |
1197 | 0 | if (atom->maxRanges == 0) { |
1198 | 0 | atom->maxRanges = 4; |
1199 | 0 | atom->ranges = (xmlRegRangePtr *) xmlMalloc(atom->maxRanges * |
1200 | 0 | sizeof(xmlRegRangePtr)); |
1201 | 0 | if (atom->ranges == NULL) { |
1202 | 0 | xmlRegexpErrMemory(ctxt, "adding ranges"); |
1203 | 0 | atom->maxRanges = 0; |
1204 | 0 | return(NULL); |
1205 | 0 | } |
1206 | 0 | } else if (atom->nbRanges >= atom->maxRanges) { |
1207 | 0 | xmlRegRangePtr *tmp; |
1208 | 0 | atom->maxRanges *= 2; |
1209 | 0 | tmp = (xmlRegRangePtr *) xmlRealloc(atom->ranges, atom->maxRanges * |
1210 | 0 | sizeof(xmlRegRangePtr)); |
1211 | 0 | if (tmp == NULL) { |
1212 | 0 | xmlRegexpErrMemory(ctxt, "adding ranges"); |
1213 | 0 | atom->maxRanges /= 2; |
1214 | 0 | return(NULL); |
1215 | 0 | } |
1216 | 0 | atom->ranges = tmp; |
1217 | 0 | } |
1218 | 0 | range = xmlRegNewRange(ctxt, neg, type, start, end); |
1219 | 0 | if (range == NULL) |
1220 | 0 | return(NULL); |
1221 | 0 | range->blockName = blockName; |
1222 | 0 | atom->ranges[atom->nbRanges++] = range; |
1223 | |
|
1224 | 0 | return(range); |
1225 | 0 | } |
1226 | | |
1227 | | static int |
1228 | 0 | xmlRegGetCounter(xmlRegParserCtxtPtr ctxt) { |
1229 | 0 | if (ctxt->maxCounters == 0) { |
1230 | 0 | ctxt->maxCounters = 4; |
1231 | 0 | ctxt->counters = (xmlRegCounter *) xmlMalloc(ctxt->maxCounters * |
1232 | 0 | sizeof(xmlRegCounter)); |
1233 | 0 | if (ctxt->counters == NULL) { |
1234 | 0 | xmlRegexpErrMemory(ctxt, "allocating counter"); |
1235 | 0 | ctxt->maxCounters = 0; |
1236 | 0 | return(-1); |
1237 | 0 | } |
1238 | 0 | } else if (ctxt->nbCounters >= ctxt->maxCounters) { |
1239 | 0 | xmlRegCounter *tmp; |
1240 | 0 | ctxt->maxCounters *= 2; |
1241 | 0 | tmp = (xmlRegCounter *) xmlRealloc(ctxt->counters, ctxt->maxCounters * |
1242 | 0 | sizeof(xmlRegCounter)); |
1243 | 0 | if (tmp == NULL) { |
1244 | 0 | xmlRegexpErrMemory(ctxt, "allocating counter"); |
1245 | 0 | ctxt->maxCounters /= 2; |
1246 | 0 | return(-1); |
1247 | 0 | } |
1248 | 0 | ctxt->counters = tmp; |
1249 | 0 | } |
1250 | 0 | ctxt->counters[ctxt->nbCounters].min = -1; |
1251 | 0 | ctxt->counters[ctxt->nbCounters].max = -1; |
1252 | 0 | return(ctxt->nbCounters++); |
1253 | 0 | } |
1254 | | |
1255 | | static int |
1256 | 0 | xmlRegAtomPush(xmlRegParserCtxtPtr ctxt, xmlRegAtomPtr atom) { |
1257 | 0 | if (atom == NULL) { |
1258 | 0 | ERROR("atom push: atom is NULL"); |
1259 | 0 | return(-1); |
1260 | 0 | } |
1261 | 0 | if (ctxt->nbAtoms >= ctxt->maxAtoms) { |
1262 | 0 | size_t newSize = ctxt->maxAtoms ? ctxt->maxAtoms * 2 : 4; |
1263 | 0 | xmlRegAtomPtr *tmp; |
1264 | |
|
1265 | 0 | tmp = xmlRealloc(ctxt->atoms, newSize * sizeof(xmlRegAtomPtr)); |
1266 | 0 | if (tmp == NULL) { |
1267 | 0 | xmlRegexpErrMemory(ctxt, "allocating counter"); |
1268 | 0 | return(-1); |
1269 | 0 | } |
1270 | 0 | ctxt->atoms = tmp; |
1271 | 0 | ctxt->maxAtoms = newSize; |
1272 | 0 | } |
1273 | 0 | atom->no = ctxt->nbAtoms; |
1274 | 0 | ctxt->atoms[ctxt->nbAtoms++] = atom; |
1275 | 0 | return(0); |
1276 | 0 | } |
1277 | | |
1278 | | static void |
1279 | | xmlRegStateAddTransTo(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr target, |
1280 | 0 | int from) { |
1281 | 0 | if (target->maxTransTo == 0) { |
1282 | 0 | target->maxTransTo = 8; |
1283 | 0 | target->transTo = (int *) xmlMalloc(target->maxTransTo * |
1284 | 0 | sizeof(int)); |
1285 | 0 | if (target->transTo == NULL) { |
1286 | 0 | xmlRegexpErrMemory(ctxt, "adding transition"); |
1287 | 0 | target->maxTransTo = 0; |
1288 | 0 | return; |
1289 | 0 | } |
1290 | 0 | } else if (target->nbTransTo >= target->maxTransTo) { |
1291 | 0 | int *tmp; |
1292 | 0 | target->maxTransTo *= 2; |
1293 | 0 | tmp = (int *) xmlRealloc(target->transTo, target->maxTransTo * |
1294 | 0 | sizeof(int)); |
1295 | 0 | if (tmp == NULL) { |
1296 | 0 | xmlRegexpErrMemory(ctxt, "adding transition"); |
1297 | 0 | target->maxTransTo /= 2; |
1298 | 0 | return; |
1299 | 0 | } |
1300 | 0 | target->transTo = tmp; |
1301 | 0 | } |
1302 | 0 | target->transTo[target->nbTransTo] = from; |
1303 | 0 | target->nbTransTo++; |
1304 | 0 | } |
1305 | | |
1306 | | static void |
1307 | | xmlRegStateAddTrans(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr state, |
1308 | | xmlRegAtomPtr atom, xmlRegStatePtr target, |
1309 | 0 | int counter, int count) { |
1310 | |
|
1311 | 0 | int nrtrans; |
1312 | |
|
1313 | 0 | if (state == NULL) { |
1314 | 0 | ERROR("add state: state is NULL"); |
1315 | 0 | return; |
1316 | 0 | } |
1317 | 0 | if (target == NULL) { |
1318 | 0 | ERROR("add state: target is NULL"); |
1319 | 0 | return; |
1320 | 0 | } |
1321 | | /* |
1322 | | * Other routines follow the philosophy 'When in doubt, add a transition' |
1323 | | * so we check here whether such a transition is already present and, if |
1324 | | * so, silently ignore this request. |
1325 | | */ |
1326 | | |
1327 | 0 | for (nrtrans = state->nbTrans - 1; nrtrans >= 0; nrtrans--) { |
1328 | 0 | xmlRegTransPtr trans = &(state->trans[nrtrans]); |
1329 | 0 | if ((trans->atom == atom) && |
1330 | 0 | (trans->to == target->no) && |
1331 | 0 | (trans->counter == counter) && |
1332 | 0 | (trans->count == count)) { |
1333 | 0 | return; |
1334 | 0 | } |
1335 | 0 | } |
1336 | | |
1337 | 0 | if (state->maxTrans == 0) { |
1338 | 0 | state->maxTrans = 8; |
1339 | 0 | state->trans = (xmlRegTrans *) xmlMalloc(state->maxTrans * |
1340 | 0 | sizeof(xmlRegTrans)); |
1341 | 0 | if (state->trans == NULL) { |
1342 | 0 | xmlRegexpErrMemory(ctxt, "adding transition"); |
1343 | 0 | state->maxTrans = 0; |
1344 | 0 | return; |
1345 | 0 | } |
1346 | 0 | } else if (state->nbTrans >= state->maxTrans) { |
1347 | 0 | xmlRegTrans *tmp; |
1348 | 0 | state->maxTrans *= 2; |
1349 | 0 | tmp = (xmlRegTrans *) xmlRealloc(state->trans, state->maxTrans * |
1350 | 0 | sizeof(xmlRegTrans)); |
1351 | 0 | if (tmp == NULL) { |
1352 | 0 | xmlRegexpErrMemory(ctxt, "adding transition"); |
1353 | 0 | state->maxTrans /= 2; |
1354 | 0 | return; |
1355 | 0 | } |
1356 | 0 | state->trans = tmp; |
1357 | 0 | } |
1358 | | |
1359 | 0 | state->trans[state->nbTrans].atom = atom; |
1360 | 0 | state->trans[state->nbTrans].to = target->no; |
1361 | 0 | state->trans[state->nbTrans].counter = counter; |
1362 | 0 | state->trans[state->nbTrans].count = count; |
1363 | 0 | state->trans[state->nbTrans].nd = 0; |
1364 | 0 | state->nbTrans++; |
1365 | 0 | xmlRegStateAddTransTo(ctxt, target, state->no); |
1366 | 0 | } |
1367 | | |
1368 | | static xmlRegStatePtr |
1369 | 0 | xmlRegStatePush(xmlRegParserCtxtPtr ctxt) { |
1370 | 0 | xmlRegStatePtr state; |
1371 | |
|
1372 | 0 | if (ctxt->nbStates >= ctxt->maxStates) { |
1373 | 0 | size_t newSize = ctxt->maxStates ? ctxt->maxStates * 2 : 4; |
1374 | 0 | xmlRegStatePtr *tmp; |
1375 | |
|
1376 | 0 | tmp = xmlRealloc(ctxt->states, newSize * sizeof(tmp[0])); |
1377 | 0 | if (tmp == NULL) { |
1378 | 0 | xmlRegexpErrMemory(ctxt, "adding state"); |
1379 | 0 | return(NULL); |
1380 | 0 | } |
1381 | 0 | ctxt->states = tmp; |
1382 | 0 | ctxt->maxStates = newSize; |
1383 | 0 | } |
1384 | | |
1385 | 0 | state = xmlRegNewState(ctxt); |
1386 | 0 | if (state == NULL) |
1387 | 0 | return(NULL); |
1388 | | |
1389 | 0 | state->no = ctxt->nbStates; |
1390 | 0 | ctxt->states[ctxt->nbStates++] = state; |
1391 | |
|
1392 | 0 | return(state); |
1393 | 0 | } |
1394 | | |
1395 | | /** |
1396 | | * xmlFAGenerateAllTransition: |
1397 | | * @ctxt: a regexp parser context |
1398 | | * @from: the from state |
1399 | | * @to: the target state or NULL for building a new one |
1400 | | * @lax: |
1401 | | * |
1402 | | */ |
1403 | | static int |
1404 | | xmlFAGenerateAllTransition(xmlRegParserCtxtPtr ctxt, |
1405 | | xmlRegStatePtr from, xmlRegStatePtr to, |
1406 | 0 | int lax) { |
1407 | 0 | if (to == NULL) { |
1408 | 0 | to = xmlRegStatePush(ctxt); |
1409 | 0 | if (to == NULL) |
1410 | 0 | return(-1); |
1411 | 0 | ctxt->state = to; |
1412 | 0 | } |
1413 | 0 | if (lax) |
1414 | 0 | xmlRegStateAddTrans(ctxt, from, NULL, to, -1, REGEXP_ALL_LAX_COUNTER); |
1415 | 0 | else |
1416 | 0 | xmlRegStateAddTrans(ctxt, from, NULL, to, -1, REGEXP_ALL_COUNTER); |
1417 | 0 | return(0); |
1418 | 0 | } |
1419 | | |
1420 | | /** |
1421 | | * xmlFAGenerateEpsilonTransition: |
1422 | | * @ctxt: a regexp parser context |
1423 | | * @from: the from state |
1424 | | * @to: the target state or NULL for building a new one |
1425 | | * |
1426 | | */ |
1427 | | static int |
1428 | | xmlFAGenerateEpsilonTransition(xmlRegParserCtxtPtr ctxt, |
1429 | 0 | xmlRegStatePtr from, xmlRegStatePtr to) { |
1430 | 0 | if (to == NULL) { |
1431 | 0 | to = xmlRegStatePush(ctxt); |
1432 | 0 | if (to == NULL) |
1433 | 0 | return(-1); |
1434 | 0 | ctxt->state = to; |
1435 | 0 | } |
1436 | 0 | xmlRegStateAddTrans(ctxt, from, NULL, to, -1, -1); |
1437 | 0 | return(0); |
1438 | 0 | } |
1439 | | |
1440 | | /** |
1441 | | * xmlFAGenerateCountedEpsilonTransition: |
1442 | | * @ctxt: a regexp parser context |
1443 | | * @from: the from state |
1444 | | * @to: the target state or NULL for building a new one |
1445 | | * counter: the counter for that transition |
1446 | | * |
1447 | | */ |
1448 | | static int |
1449 | | xmlFAGenerateCountedEpsilonTransition(xmlRegParserCtxtPtr ctxt, |
1450 | 0 | xmlRegStatePtr from, xmlRegStatePtr to, int counter) { |
1451 | 0 | if (to == NULL) { |
1452 | 0 | to = xmlRegStatePush(ctxt); |
1453 | 0 | if (to == NULL) |
1454 | 0 | return(-1); |
1455 | 0 | ctxt->state = to; |
1456 | 0 | } |
1457 | 0 | xmlRegStateAddTrans(ctxt, from, NULL, to, counter, -1); |
1458 | 0 | return(0); |
1459 | 0 | } |
1460 | | |
1461 | | /** |
1462 | | * xmlFAGenerateCountedTransition: |
1463 | | * @ctxt: a regexp parser context |
1464 | | * @from: the from state |
1465 | | * @to: the target state or NULL for building a new one |
1466 | | * counter: the counter for that transition |
1467 | | * |
1468 | | */ |
1469 | | static int |
1470 | | xmlFAGenerateCountedTransition(xmlRegParserCtxtPtr ctxt, |
1471 | 0 | xmlRegStatePtr from, xmlRegStatePtr to, int counter) { |
1472 | 0 | if (to == NULL) { |
1473 | 0 | to = xmlRegStatePush(ctxt); |
1474 | 0 | if (to == NULL) |
1475 | 0 | return(-1); |
1476 | 0 | ctxt->state = to; |
1477 | 0 | } |
1478 | 0 | xmlRegStateAddTrans(ctxt, from, NULL, to, -1, counter); |
1479 | 0 | return(0); |
1480 | 0 | } |
1481 | | |
1482 | | /** |
1483 | | * xmlFAGenerateTransitions: |
1484 | | * @ctxt: a regexp parser context |
1485 | | * @from: the from state |
1486 | | * @to: the target state or NULL for building a new one |
1487 | | * @atom: the atom generating the transition |
1488 | | * |
1489 | | * Returns 0 if success and -1 in case of error. |
1490 | | */ |
1491 | | static int |
1492 | | xmlFAGenerateTransitions(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr from, |
1493 | 0 | xmlRegStatePtr to, xmlRegAtomPtr atom) { |
1494 | 0 | xmlRegStatePtr end; |
1495 | 0 | int nullable = 0; |
1496 | |
|
1497 | 0 | if (atom == NULL) { |
1498 | 0 | ERROR("generate transition: atom == NULL"); |
1499 | 0 | return(-1); |
1500 | 0 | } |
1501 | 0 | if (atom->type == XML_REGEXP_SUBREG) { |
1502 | | /* |
1503 | | * this is a subexpression handling one should not need to |
1504 | | * create a new node except for XML_REGEXP_QUANT_RANGE. |
1505 | | */ |
1506 | 0 | if ((to != NULL) && (atom->stop != to) && |
1507 | 0 | (atom->quant != XML_REGEXP_QUANT_RANGE)) { |
1508 | | /* |
1509 | | * Generate an epsilon transition to link to the target |
1510 | | */ |
1511 | 0 | xmlFAGenerateEpsilonTransition(ctxt, atom->stop, to); |
1512 | | #ifdef DV |
1513 | | } else if ((to == NULL) && (atom->quant != XML_REGEXP_QUANT_RANGE) && |
1514 | | (atom->quant != XML_REGEXP_QUANT_ONCE)) { |
1515 | | to = xmlRegStatePush(ctxt, to); |
1516 | | if (to == NULL) |
1517 | | return(-1); |
1518 | | ctxt->state = to; |
1519 | | xmlFAGenerateEpsilonTransition(ctxt, atom->stop, to); |
1520 | | #endif |
1521 | 0 | } |
1522 | 0 | switch (atom->quant) { |
1523 | 0 | case XML_REGEXP_QUANT_OPT: |
1524 | 0 | atom->quant = XML_REGEXP_QUANT_ONCE; |
1525 | | /* |
1526 | | * transition done to the state after end of atom. |
1527 | | * 1. set transition from atom start to new state |
1528 | | * 2. set transition from atom end to this state. |
1529 | | */ |
1530 | 0 | if (to == NULL) { |
1531 | 0 | xmlFAGenerateEpsilonTransition(ctxt, atom->start, 0); |
1532 | 0 | xmlFAGenerateEpsilonTransition(ctxt, atom->stop, |
1533 | 0 | ctxt->state); |
1534 | 0 | } else { |
1535 | 0 | xmlFAGenerateEpsilonTransition(ctxt, atom->start, to); |
1536 | 0 | } |
1537 | 0 | break; |
1538 | 0 | case XML_REGEXP_QUANT_MULT: |
1539 | 0 | atom->quant = XML_REGEXP_QUANT_ONCE; |
1540 | 0 | xmlFAGenerateEpsilonTransition(ctxt, atom->start, atom->stop); |
1541 | 0 | xmlFAGenerateEpsilonTransition(ctxt, atom->stop, atom->start); |
1542 | 0 | break; |
1543 | 0 | case XML_REGEXP_QUANT_PLUS: |
1544 | 0 | atom->quant = XML_REGEXP_QUANT_ONCE; |
1545 | 0 | xmlFAGenerateEpsilonTransition(ctxt, atom->stop, atom->start); |
1546 | 0 | break; |
1547 | 0 | case XML_REGEXP_QUANT_RANGE: { |
1548 | 0 | int counter; |
1549 | 0 | xmlRegStatePtr inter, newstate; |
1550 | | |
1551 | | /* |
1552 | | * create the final state now if needed |
1553 | | */ |
1554 | 0 | if (to != NULL) { |
1555 | 0 | newstate = to; |
1556 | 0 | } else { |
1557 | 0 | newstate = xmlRegStatePush(ctxt); |
1558 | 0 | if (newstate == NULL) |
1559 | 0 | return(-1); |
1560 | 0 | } |
1561 | | |
1562 | | /* |
1563 | | * The principle here is to use counted transition |
1564 | | * to avoid explosion in the number of states in the |
1565 | | * graph. This is clearly more complex but should not |
1566 | | * be exploitable at runtime. |
1567 | | */ |
1568 | 0 | if ((atom->min == 0) && (atom->start0 == NULL)) { |
1569 | 0 | xmlRegAtomPtr copy; |
1570 | | /* |
1571 | | * duplicate a transition based on atom to count next |
1572 | | * occurrences after 1. We cannot loop to atom->start |
1573 | | * directly because we need an epsilon transition to |
1574 | | * newstate. |
1575 | | */ |
1576 | | /* ???? For some reason it seems we never reach that |
1577 | | case, I suppose this got optimized out before when |
1578 | | building the automata */ |
1579 | 0 | copy = xmlRegCopyAtom(ctxt, atom); |
1580 | 0 | if (copy == NULL) |
1581 | 0 | return(-1); |
1582 | 0 | copy->quant = XML_REGEXP_QUANT_ONCE; |
1583 | 0 | copy->min = 0; |
1584 | 0 | copy->max = 0; |
1585 | |
|
1586 | 0 | if (xmlFAGenerateTransitions(ctxt, atom->start, NULL, copy) |
1587 | 0 | < 0) { |
1588 | 0 | xmlRegFreeAtom(copy); |
1589 | 0 | return(-1); |
1590 | 0 | } |
1591 | 0 | inter = ctxt->state; |
1592 | 0 | counter = xmlRegGetCounter(ctxt); |
1593 | 0 | if (counter < 0) |
1594 | 0 | return(-1); |
1595 | 0 | ctxt->counters[counter].min = atom->min - 1; |
1596 | 0 | ctxt->counters[counter].max = atom->max - 1; |
1597 | | /* count the number of times we see it again */ |
1598 | 0 | xmlFAGenerateCountedEpsilonTransition(ctxt, inter, |
1599 | 0 | atom->stop, counter); |
1600 | | /* allow a way out based on the count */ |
1601 | 0 | xmlFAGenerateCountedTransition(ctxt, inter, |
1602 | 0 | newstate, counter); |
1603 | | /* and also allow a direct exit for 0 */ |
1604 | 0 | xmlFAGenerateEpsilonTransition(ctxt, atom->start, |
1605 | 0 | newstate); |
1606 | 0 | } else { |
1607 | | /* |
1608 | | * either we need the atom at least once or there |
1609 | | * is an atom->start0 allowing to easily plug the |
1610 | | * epsilon transition. |
1611 | | */ |
1612 | 0 | counter = xmlRegGetCounter(ctxt); |
1613 | 0 | if (counter < 0) |
1614 | 0 | return(-1); |
1615 | 0 | ctxt->counters[counter].min = atom->min - 1; |
1616 | 0 | ctxt->counters[counter].max = atom->max - 1; |
1617 | | /* allow a way out based on the count */ |
1618 | 0 | xmlFAGenerateCountedTransition(ctxt, atom->stop, |
1619 | 0 | newstate, counter); |
1620 | | /* count the number of times we see it again */ |
1621 | 0 | xmlFAGenerateCountedEpsilonTransition(ctxt, atom->stop, |
1622 | 0 | atom->start, counter); |
1623 | | /* and if needed allow a direct exit for 0 */ |
1624 | 0 | if (atom->min == 0) |
1625 | 0 | xmlFAGenerateEpsilonTransition(ctxt, atom->start0, |
1626 | 0 | newstate); |
1627 | |
|
1628 | 0 | } |
1629 | 0 | atom->min = 0; |
1630 | 0 | atom->max = 0; |
1631 | 0 | atom->quant = XML_REGEXP_QUANT_ONCE; |
1632 | 0 | ctxt->state = newstate; |
1633 | 0 | } |
1634 | 0 | default: |
1635 | 0 | break; |
1636 | 0 | } |
1637 | 0 | if (xmlRegAtomPush(ctxt, atom) < 0) |
1638 | 0 | return(-1); |
1639 | 0 | return(0); |
1640 | 0 | } |
1641 | 0 | if ((atom->min == 0) && (atom->max == 0) && |
1642 | 0 | (atom->quant == XML_REGEXP_QUANT_RANGE)) { |
1643 | | /* |
1644 | | * we can discard the atom and generate an epsilon transition instead |
1645 | | */ |
1646 | 0 | if (to == NULL) { |
1647 | 0 | to = xmlRegStatePush(ctxt); |
1648 | 0 | if (to == NULL) |
1649 | 0 | return(-1); |
1650 | 0 | } |
1651 | 0 | xmlFAGenerateEpsilonTransition(ctxt, from, to); |
1652 | 0 | ctxt->state = to; |
1653 | 0 | xmlRegFreeAtom(atom); |
1654 | 0 | return(0); |
1655 | 0 | } |
1656 | 0 | if (to == NULL) { |
1657 | 0 | to = xmlRegStatePush(ctxt); |
1658 | 0 | if (to == NULL) |
1659 | 0 | return(-1); |
1660 | 0 | } |
1661 | 0 | end = to; |
1662 | 0 | if ((atom->quant == XML_REGEXP_QUANT_MULT) || |
1663 | 0 | (atom->quant == XML_REGEXP_QUANT_PLUS)) { |
1664 | | /* |
1665 | | * Do not pollute the target state by adding transitions from |
1666 | | * it as it is likely to be the shared target of multiple branches. |
1667 | | * So isolate with an epsilon transition. |
1668 | | */ |
1669 | 0 | xmlRegStatePtr tmp; |
1670 | |
|
1671 | 0 | tmp = xmlRegStatePush(ctxt); |
1672 | 0 | if (tmp == NULL) |
1673 | 0 | return(-1); |
1674 | 0 | xmlFAGenerateEpsilonTransition(ctxt, tmp, to); |
1675 | 0 | to = tmp; |
1676 | 0 | } |
1677 | 0 | if ((atom->quant == XML_REGEXP_QUANT_RANGE) && |
1678 | 0 | (atom->min == 0) && (atom->max > 0)) { |
1679 | 0 | nullable = 1; |
1680 | 0 | atom->min = 1; |
1681 | 0 | if (atom->max == 1) |
1682 | 0 | atom->quant = XML_REGEXP_QUANT_OPT; |
1683 | 0 | } |
1684 | 0 | xmlRegStateAddTrans(ctxt, from, atom, to, -1, -1); |
1685 | 0 | ctxt->state = end; |
1686 | 0 | switch (atom->quant) { |
1687 | 0 | case XML_REGEXP_QUANT_OPT: |
1688 | 0 | atom->quant = XML_REGEXP_QUANT_ONCE; |
1689 | 0 | xmlFAGenerateEpsilonTransition(ctxt, from, to); |
1690 | 0 | break; |
1691 | 0 | case XML_REGEXP_QUANT_MULT: |
1692 | 0 | atom->quant = XML_REGEXP_QUANT_ONCE; |
1693 | 0 | xmlFAGenerateEpsilonTransition(ctxt, from, to); |
1694 | 0 | xmlRegStateAddTrans(ctxt, to, atom, to, -1, -1); |
1695 | 0 | break; |
1696 | 0 | case XML_REGEXP_QUANT_PLUS: |
1697 | 0 | atom->quant = XML_REGEXP_QUANT_ONCE; |
1698 | 0 | xmlRegStateAddTrans(ctxt, to, atom, to, -1, -1); |
1699 | 0 | break; |
1700 | 0 | case XML_REGEXP_QUANT_RANGE: |
1701 | 0 | if (nullable) |
1702 | 0 | xmlFAGenerateEpsilonTransition(ctxt, from, to); |
1703 | 0 | break; |
1704 | 0 | default: |
1705 | 0 | break; |
1706 | 0 | } |
1707 | 0 | if (xmlRegAtomPush(ctxt, atom) < 0) |
1708 | 0 | return(-1); |
1709 | 0 | return(0); |
1710 | 0 | } |
1711 | | |
1712 | | /** |
1713 | | * xmlFAReduceEpsilonTransitions: |
1714 | | * @ctxt: a regexp parser context |
1715 | | * @fromnr: the from state |
1716 | | * @tonr: the to state |
1717 | | * @counter: should that transition be associated to a counted |
1718 | | * |
1719 | | */ |
1720 | | static void |
1721 | | xmlFAReduceEpsilonTransitions(xmlRegParserCtxtPtr ctxt, int fromnr, |
1722 | 0 | int tonr, int counter) { |
1723 | 0 | int transnr; |
1724 | 0 | xmlRegStatePtr from; |
1725 | 0 | xmlRegStatePtr to; |
1726 | |
|
1727 | 0 | from = ctxt->states[fromnr]; |
1728 | 0 | if (from == NULL) |
1729 | 0 | return; |
1730 | 0 | to = ctxt->states[tonr]; |
1731 | 0 | if (to == NULL) |
1732 | 0 | return; |
1733 | 0 | if ((to->mark == XML_REGEXP_MARK_START) || |
1734 | 0 | (to->mark == XML_REGEXP_MARK_VISITED)) |
1735 | 0 | return; |
1736 | | |
1737 | 0 | to->mark = XML_REGEXP_MARK_VISITED; |
1738 | 0 | if (to->type == XML_REGEXP_FINAL_STATE) { |
1739 | 0 | from->type = XML_REGEXP_FINAL_STATE; |
1740 | 0 | } |
1741 | 0 | for (transnr = 0;transnr < to->nbTrans;transnr++) { |
1742 | 0 | xmlRegTransPtr t1 = &to->trans[transnr]; |
1743 | 0 | int tcounter; |
1744 | |
|
1745 | 0 | if (t1->to < 0) |
1746 | 0 | continue; |
1747 | 0 | if (t1->counter >= 0) { |
1748 | | /* assert(counter < 0); */ |
1749 | 0 | tcounter = t1->counter; |
1750 | 0 | } else { |
1751 | 0 | tcounter = counter; |
1752 | 0 | } |
1753 | 0 | if (t1->atom == NULL) { |
1754 | | /* |
1755 | | * Don't remove counted transitions |
1756 | | * Don't loop either |
1757 | | */ |
1758 | 0 | if (t1->to != fromnr) { |
1759 | 0 | if (t1->count >= 0) { |
1760 | 0 | xmlRegStateAddTrans(ctxt, from, NULL, ctxt->states[t1->to], |
1761 | 0 | -1, t1->count); |
1762 | 0 | } else { |
1763 | 0 | xmlFAReduceEpsilonTransitions(ctxt, fromnr, t1->to, |
1764 | 0 | tcounter); |
1765 | 0 | } |
1766 | 0 | } |
1767 | 0 | } else { |
1768 | 0 | xmlRegStateAddTrans(ctxt, from, t1->atom, |
1769 | 0 | ctxt->states[t1->to], tcounter, -1); |
1770 | 0 | } |
1771 | 0 | } |
1772 | 0 | } |
1773 | | |
1774 | | /** |
1775 | | * xmlFAFinishReduceEpsilonTransitions: |
1776 | | * @ctxt: a regexp parser context |
1777 | | * @fromnr: the from state |
1778 | | * @tonr: the to state |
1779 | | * @counter: should that transition be associated to a counted |
1780 | | * |
1781 | | */ |
1782 | | static void |
1783 | 0 | xmlFAFinishReduceEpsilonTransitions(xmlRegParserCtxtPtr ctxt, int tonr) { |
1784 | 0 | int transnr; |
1785 | 0 | xmlRegStatePtr to; |
1786 | |
|
1787 | 0 | to = ctxt->states[tonr]; |
1788 | 0 | if (to == NULL) |
1789 | 0 | return; |
1790 | 0 | if ((to->mark == XML_REGEXP_MARK_START) || |
1791 | 0 | (to->mark == XML_REGEXP_MARK_NORMAL)) |
1792 | 0 | return; |
1793 | | |
1794 | 0 | to->mark = XML_REGEXP_MARK_NORMAL; |
1795 | 0 | for (transnr = 0;transnr < to->nbTrans;transnr++) { |
1796 | 0 | xmlRegTransPtr t1 = &to->trans[transnr]; |
1797 | 0 | if ((t1->to >= 0) && (t1->atom == NULL)) |
1798 | 0 | xmlFAFinishReduceEpsilonTransitions(ctxt, t1->to); |
1799 | 0 | } |
1800 | 0 | } |
1801 | | |
1802 | | /** |
1803 | | * xmlFAEliminateSimpleEpsilonTransitions: |
1804 | | * @ctxt: a regexp parser context |
1805 | | * |
1806 | | * Eliminating general epsilon transitions can get costly in the general |
1807 | | * algorithm due to the large amount of generated new transitions and |
1808 | | * associated comparisons. However for simple epsilon transition used just |
1809 | | * to separate building blocks when generating the automata this can be |
1810 | | * reduced to state elimination: |
1811 | | * - if there exists an epsilon from X to Y |
1812 | | * - if there is no other transition from X |
1813 | | * then X and Y are semantically equivalent and X can be eliminated |
1814 | | * If X is the start state then make Y the start state, else replace the |
1815 | | * target of all transitions to X by transitions to Y. |
1816 | | * |
1817 | | * If X is a final state, skip it. |
1818 | | * Otherwise it would be necessary to manipulate counters for this case when |
1819 | | * eliminating state 2: |
1820 | | * State 1 has a transition with an atom to state 2. |
1821 | | * State 2 is final and has an epsilon transition to state 1. |
1822 | | */ |
1823 | | static void |
1824 | 0 | xmlFAEliminateSimpleEpsilonTransitions(xmlRegParserCtxtPtr ctxt) { |
1825 | 0 | int statenr, i, j, newto; |
1826 | 0 | xmlRegStatePtr state, tmp; |
1827 | |
|
1828 | 0 | for (statenr = 0;statenr < ctxt->nbStates;statenr++) { |
1829 | 0 | state = ctxt->states[statenr]; |
1830 | 0 | if (state == NULL) |
1831 | 0 | continue; |
1832 | 0 | if (state->nbTrans != 1) |
1833 | 0 | continue; |
1834 | 0 | if (state->type == XML_REGEXP_UNREACH_STATE || |
1835 | 0 | state->type == XML_REGEXP_FINAL_STATE) |
1836 | 0 | continue; |
1837 | | /* is the only transition out a basic transition */ |
1838 | 0 | if ((state->trans[0].atom == NULL) && |
1839 | 0 | (state->trans[0].to >= 0) && |
1840 | 0 | (state->trans[0].to != statenr) && |
1841 | 0 | (state->trans[0].counter < 0) && |
1842 | 0 | (state->trans[0].count < 0)) { |
1843 | 0 | newto = state->trans[0].to; |
1844 | |
|
1845 | 0 | if (state->type == XML_REGEXP_START_STATE) { |
1846 | 0 | } else { |
1847 | 0 | for (i = 0;i < state->nbTransTo;i++) { |
1848 | 0 | tmp = ctxt->states[state->transTo[i]]; |
1849 | 0 | for (j = 0;j < tmp->nbTrans;j++) { |
1850 | 0 | if (tmp->trans[j].to == statenr) { |
1851 | 0 | tmp->trans[j].to = -1; |
1852 | 0 | xmlRegStateAddTrans(ctxt, tmp, tmp->trans[j].atom, |
1853 | 0 | ctxt->states[newto], |
1854 | 0 | tmp->trans[j].counter, |
1855 | 0 | tmp->trans[j].count); |
1856 | 0 | } |
1857 | 0 | } |
1858 | 0 | } |
1859 | 0 | if (state->type == XML_REGEXP_FINAL_STATE) |
1860 | 0 | ctxt->states[newto]->type = XML_REGEXP_FINAL_STATE; |
1861 | | /* eliminate the transition completely */ |
1862 | 0 | state->nbTrans = 0; |
1863 | |
|
1864 | 0 | state->type = XML_REGEXP_UNREACH_STATE; |
1865 | |
|
1866 | 0 | } |
1867 | |
|
1868 | 0 | } |
1869 | 0 | } |
1870 | 0 | } |
1871 | | /** |
1872 | | * xmlFAEliminateEpsilonTransitions: |
1873 | | * @ctxt: a regexp parser context |
1874 | | * |
1875 | | */ |
1876 | | static void |
1877 | 0 | xmlFAEliminateEpsilonTransitions(xmlRegParserCtxtPtr ctxt) { |
1878 | 0 | int statenr, transnr; |
1879 | 0 | xmlRegStatePtr state; |
1880 | 0 | int has_epsilon; |
1881 | |
|
1882 | 0 | if (ctxt->states == NULL) return; |
1883 | | |
1884 | | /* |
1885 | | * Eliminate simple epsilon transition and the associated unreachable |
1886 | | * states. |
1887 | | */ |
1888 | 0 | xmlFAEliminateSimpleEpsilonTransitions(ctxt); |
1889 | 0 | for (statenr = 0;statenr < ctxt->nbStates;statenr++) { |
1890 | 0 | state = ctxt->states[statenr]; |
1891 | 0 | if ((state != NULL) && (state->type == XML_REGEXP_UNREACH_STATE)) { |
1892 | 0 | xmlRegFreeState(state); |
1893 | 0 | ctxt->states[statenr] = NULL; |
1894 | 0 | } |
1895 | 0 | } |
1896 | |
|
1897 | 0 | has_epsilon = 0; |
1898 | | |
1899 | | /* |
1900 | | * Build the completed transitions bypassing the epsilons |
1901 | | * Use a marking algorithm to avoid loops |
1902 | | * Mark sink states too. |
1903 | | * Process from the latest states backward to the start when |
1904 | | * there is long cascading epsilon chains this minimize the |
1905 | | * recursions and transition compares when adding the new ones |
1906 | | */ |
1907 | 0 | for (statenr = ctxt->nbStates - 1;statenr >= 0;statenr--) { |
1908 | 0 | state = ctxt->states[statenr]; |
1909 | 0 | if (state == NULL) |
1910 | 0 | continue; |
1911 | 0 | if ((state->nbTrans == 0) && |
1912 | 0 | (state->type != XML_REGEXP_FINAL_STATE)) { |
1913 | 0 | state->type = XML_REGEXP_SINK_STATE; |
1914 | 0 | } |
1915 | 0 | for (transnr = 0;transnr < state->nbTrans;transnr++) { |
1916 | 0 | if ((state->trans[transnr].atom == NULL) && |
1917 | 0 | (state->trans[transnr].to >= 0)) { |
1918 | 0 | if (state->trans[transnr].to == statenr) { |
1919 | 0 | state->trans[transnr].to = -1; |
1920 | 0 | } else if (state->trans[transnr].count < 0) { |
1921 | 0 | int newto = state->trans[transnr].to; |
1922 | |
|
1923 | 0 | has_epsilon = 1; |
1924 | 0 | state->trans[transnr].to = -2; |
1925 | 0 | state->mark = XML_REGEXP_MARK_START; |
1926 | 0 | xmlFAReduceEpsilonTransitions(ctxt, statenr, |
1927 | 0 | newto, state->trans[transnr].counter); |
1928 | 0 | xmlFAFinishReduceEpsilonTransitions(ctxt, newto); |
1929 | 0 | state->mark = XML_REGEXP_MARK_NORMAL; |
1930 | 0 | } |
1931 | 0 | } |
1932 | 0 | } |
1933 | 0 | } |
1934 | | /* |
1935 | | * Eliminate the epsilon transitions |
1936 | | */ |
1937 | 0 | if (has_epsilon) { |
1938 | 0 | for (statenr = 0;statenr < ctxt->nbStates;statenr++) { |
1939 | 0 | state = ctxt->states[statenr]; |
1940 | 0 | if (state == NULL) |
1941 | 0 | continue; |
1942 | 0 | for (transnr = 0;transnr < state->nbTrans;transnr++) { |
1943 | 0 | xmlRegTransPtr trans = &(state->trans[transnr]); |
1944 | 0 | if ((trans->atom == NULL) && |
1945 | 0 | (trans->count < 0) && |
1946 | 0 | (trans->to >= 0)) { |
1947 | 0 | trans->to = -1; |
1948 | 0 | } |
1949 | 0 | } |
1950 | 0 | } |
1951 | 0 | } |
1952 | | |
1953 | | /* |
1954 | | * Use this pass to detect unreachable states too |
1955 | | */ |
1956 | 0 | for (statenr = 0;statenr < ctxt->nbStates;statenr++) { |
1957 | 0 | state = ctxt->states[statenr]; |
1958 | 0 | if (state != NULL) |
1959 | 0 | state->reached = XML_REGEXP_MARK_NORMAL; |
1960 | 0 | } |
1961 | 0 | state = ctxt->states[0]; |
1962 | 0 | if (state != NULL) |
1963 | 0 | state->reached = XML_REGEXP_MARK_START; |
1964 | 0 | while (state != NULL) { |
1965 | 0 | xmlRegStatePtr target = NULL; |
1966 | 0 | state->reached = XML_REGEXP_MARK_VISITED; |
1967 | | /* |
1968 | | * Mark all states reachable from the current reachable state |
1969 | | */ |
1970 | 0 | for (transnr = 0;transnr < state->nbTrans;transnr++) { |
1971 | 0 | if ((state->trans[transnr].to >= 0) && |
1972 | 0 | ((state->trans[transnr].atom != NULL) || |
1973 | 0 | (state->trans[transnr].count >= 0))) { |
1974 | 0 | int newto = state->trans[transnr].to; |
1975 | |
|
1976 | 0 | if (ctxt->states[newto] == NULL) |
1977 | 0 | continue; |
1978 | 0 | if (ctxt->states[newto]->reached == XML_REGEXP_MARK_NORMAL) { |
1979 | 0 | ctxt->states[newto]->reached = XML_REGEXP_MARK_START; |
1980 | 0 | target = ctxt->states[newto]; |
1981 | 0 | } |
1982 | 0 | } |
1983 | 0 | } |
1984 | | |
1985 | | /* |
1986 | | * find the next accessible state not explored |
1987 | | */ |
1988 | 0 | if (target == NULL) { |
1989 | 0 | for (statenr = 1;statenr < ctxt->nbStates;statenr++) { |
1990 | 0 | state = ctxt->states[statenr]; |
1991 | 0 | if ((state != NULL) && (state->reached == |
1992 | 0 | XML_REGEXP_MARK_START)) { |
1993 | 0 | target = state; |
1994 | 0 | break; |
1995 | 0 | } |
1996 | 0 | } |
1997 | 0 | } |
1998 | 0 | state = target; |
1999 | 0 | } |
2000 | 0 | for (statenr = 0;statenr < ctxt->nbStates;statenr++) { |
2001 | 0 | state = ctxt->states[statenr]; |
2002 | 0 | if ((state != NULL) && (state->reached == XML_REGEXP_MARK_NORMAL)) { |
2003 | 0 | xmlRegFreeState(state); |
2004 | 0 | ctxt->states[statenr] = NULL; |
2005 | 0 | } |
2006 | 0 | } |
2007 | |
|
2008 | 0 | } |
2009 | | |
2010 | | static int |
2011 | 0 | xmlFACompareRanges(xmlRegRangePtr range1, xmlRegRangePtr range2) { |
2012 | 0 | int ret = 0; |
2013 | |
|
2014 | 0 | if ((range1->type == XML_REGEXP_RANGES) || |
2015 | 0 | (range2->type == XML_REGEXP_RANGES) || |
2016 | 0 | (range2->type == XML_REGEXP_SUBREG) || |
2017 | 0 | (range1->type == XML_REGEXP_SUBREG) || |
2018 | 0 | (range1->type == XML_REGEXP_STRING) || |
2019 | 0 | (range2->type == XML_REGEXP_STRING)) |
2020 | 0 | return(-1); |
2021 | | |
2022 | | /* put them in order */ |
2023 | 0 | if (range1->type > range2->type) { |
2024 | 0 | xmlRegRangePtr tmp; |
2025 | |
|
2026 | 0 | tmp = range1; |
2027 | 0 | range1 = range2; |
2028 | 0 | range2 = tmp; |
2029 | 0 | } |
2030 | 0 | if ((range1->type == XML_REGEXP_ANYCHAR) || |
2031 | 0 | (range2->type == XML_REGEXP_ANYCHAR)) { |
2032 | 0 | ret = 1; |
2033 | 0 | } else if ((range1->type == XML_REGEXP_EPSILON) || |
2034 | 0 | (range2->type == XML_REGEXP_EPSILON)) { |
2035 | 0 | return(0); |
2036 | 0 | } else if (range1->type == range2->type) { |
2037 | 0 | if (range1->type != XML_REGEXP_CHARVAL) |
2038 | 0 | ret = 1; |
2039 | 0 | else if ((range1->end < range2->start) || |
2040 | 0 | (range2->end < range1->start)) |
2041 | 0 | ret = 0; |
2042 | 0 | else |
2043 | 0 | ret = 1; |
2044 | 0 | } else if (range1->type == XML_REGEXP_CHARVAL) { |
2045 | 0 | int codepoint; |
2046 | 0 | int neg = 0; |
2047 | | |
2048 | | /* |
2049 | | * just check all codepoints in the range for acceptance, |
2050 | | * this is usually way cheaper since done only once at |
2051 | | * compilation than testing over and over at runtime or |
2052 | | * pushing too many states when evaluating. |
2053 | | */ |
2054 | 0 | if (((range1->neg == 0) && (range2->neg != 0)) || |
2055 | 0 | ((range1->neg != 0) && (range2->neg == 0))) |
2056 | 0 | neg = 1; |
2057 | |
|
2058 | 0 | for (codepoint = range1->start;codepoint <= range1->end ;codepoint++) { |
2059 | 0 | ret = xmlRegCheckCharacterRange(range2->type, codepoint, |
2060 | 0 | 0, range2->start, range2->end, |
2061 | 0 | range2->blockName); |
2062 | 0 | if (ret < 0) |
2063 | 0 | return(-1); |
2064 | 0 | if (((neg == 1) && (ret == 0)) || |
2065 | 0 | ((neg == 0) && (ret == 1))) |
2066 | 0 | return(1); |
2067 | 0 | } |
2068 | 0 | return(0); |
2069 | 0 | } else if ((range1->type == XML_REGEXP_BLOCK_NAME) || |
2070 | 0 | (range2->type == XML_REGEXP_BLOCK_NAME)) { |
2071 | 0 | if (range1->type == range2->type) { |
2072 | 0 | ret = xmlStrEqual(range1->blockName, range2->blockName); |
2073 | 0 | } else { |
2074 | | /* |
2075 | | * comparing a block range with anything else is way |
2076 | | * too costly, and maintaining the table is like too much |
2077 | | * memory too, so let's force the automata to save state |
2078 | | * here. |
2079 | | */ |
2080 | 0 | return(1); |
2081 | 0 | } |
2082 | 0 | } else if ((range1->type < XML_REGEXP_LETTER) || |
2083 | 0 | (range2->type < XML_REGEXP_LETTER)) { |
2084 | 0 | if ((range1->type == XML_REGEXP_ANYSPACE) && |
2085 | 0 | (range2->type == XML_REGEXP_NOTSPACE)) |
2086 | 0 | ret = 0; |
2087 | 0 | else if ((range1->type == XML_REGEXP_INITNAME) && |
2088 | 0 | (range2->type == XML_REGEXP_NOTINITNAME)) |
2089 | 0 | ret = 0; |
2090 | 0 | else if ((range1->type == XML_REGEXP_NAMECHAR) && |
2091 | 0 | (range2->type == XML_REGEXP_NOTNAMECHAR)) |
2092 | 0 | ret = 0; |
2093 | 0 | else if ((range1->type == XML_REGEXP_DECIMAL) && |
2094 | 0 | (range2->type == XML_REGEXP_NOTDECIMAL)) |
2095 | 0 | ret = 0; |
2096 | 0 | else if ((range1->type == XML_REGEXP_REALCHAR) && |
2097 | 0 | (range2->type == XML_REGEXP_NOTREALCHAR)) |
2098 | 0 | ret = 0; |
2099 | 0 | else { |
2100 | | /* same thing to limit complexity */ |
2101 | 0 | return(1); |
2102 | 0 | } |
2103 | 0 | } else { |
2104 | 0 | ret = 0; |
2105 | | /* range1->type < range2->type here */ |
2106 | 0 | switch (range1->type) { |
2107 | 0 | case XML_REGEXP_LETTER: |
2108 | | /* all disjoint except in the subgroups */ |
2109 | 0 | if ((range2->type == XML_REGEXP_LETTER_UPPERCASE) || |
2110 | 0 | (range2->type == XML_REGEXP_LETTER_LOWERCASE) || |
2111 | 0 | (range2->type == XML_REGEXP_LETTER_TITLECASE) || |
2112 | 0 | (range2->type == XML_REGEXP_LETTER_MODIFIER) || |
2113 | 0 | (range2->type == XML_REGEXP_LETTER_OTHERS)) |
2114 | 0 | ret = 1; |
2115 | 0 | break; |
2116 | 0 | case XML_REGEXP_MARK: |
2117 | 0 | if ((range2->type == XML_REGEXP_MARK_NONSPACING) || |
2118 | 0 | (range2->type == XML_REGEXP_MARK_SPACECOMBINING) || |
2119 | 0 | (range2->type == XML_REGEXP_MARK_ENCLOSING)) |
2120 | 0 | ret = 1; |
2121 | 0 | break; |
2122 | 0 | case XML_REGEXP_NUMBER: |
2123 | 0 | if ((range2->type == XML_REGEXP_NUMBER_DECIMAL) || |
2124 | 0 | (range2->type == XML_REGEXP_NUMBER_LETTER) || |
2125 | 0 | (range2->type == XML_REGEXP_NUMBER_OTHERS)) |
2126 | 0 | ret = 1; |
2127 | 0 | break; |
2128 | 0 | case XML_REGEXP_PUNCT: |
2129 | 0 | if ((range2->type == XML_REGEXP_PUNCT_CONNECTOR) || |
2130 | 0 | (range2->type == XML_REGEXP_PUNCT_DASH) || |
2131 | 0 | (range2->type == XML_REGEXP_PUNCT_OPEN) || |
2132 | 0 | (range2->type == XML_REGEXP_PUNCT_CLOSE) || |
2133 | 0 | (range2->type == XML_REGEXP_PUNCT_INITQUOTE) || |
2134 | 0 | (range2->type == XML_REGEXP_PUNCT_FINQUOTE) || |
2135 | 0 | (range2->type == XML_REGEXP_PUNCT_OTHERS)) |
2136 | 0 | ret = 1; |
2137 | 0 | break; |
2138 | 0 | case XML_REGEXP_SEPAR: |
2139 | 0 | if ((range2->type == XML_REGEXP_SEPAR_SPACE) || |
2140 | 0 | (range2->type == XML_REGEXP_SEPAR_LINE) || |
2141 | 0 | (range2->type == XML_REGEXP_SEPAR_PARA)) |
2142 | 0 | ret = 1; |
2143 | 0 | break; |
2144 | 0 | case XML_REGEXP_SYMBOL: |
2145 | 0 | if ((range2->type == XML_REGEXP_SYMBOL_MATH) || |
2146 | 0 | (range2->type == XML_REGEXP_SYMBOL_CURRENCY) || |
2147 | 0 | (range2->type == XML_REGEXP_SYMBOL_MODIFIER) || |
2148 | 0 | (range2->type == XML_REGEXP_SYMBOL_OTHERS)) |
2149 | 0 | ret = 1; |
2150 | 0 | break; |
2151 | 0 | case XML_REGEXP_OTHER: |
2152 | 0 | if ((range2->type == XML_REGEXP_OTHER_CONTROL) || |
2153 | 0 | (range2->type == XML_REGEXP_OTHER_FORMAT) || |
2154 | 0 | (range2->type == XML_REGEXP_OTHER_PRIVATE)) |
2155 | 0 | ret = 1; |
2156 | 0 | break; |
2157 | 0 | default: |
2158 | 0 | if ((range2->type >= XML_REGEXP_LETTER) && |
2159 | 0 | (range2->type < XML_REGEXP_BLOCK_NAME)) |
2160 | 0 | ret = 0; |
2161 | 0 | else { |
2162 | | /* safety net ! */ |
2163 | 0 | return(1); |
2164 | 0 | } |
2165 | 0 | } |
2166 | 0 | } |
2167 | 0 | if (((range1->neg == 0) && (range2->neg != 0)) || |
2168 | 0 | ((range1->neg != 0) && (range2->neg == 0))) |
2169 | 0 | ret = !ret; |
2170 | 0 | return(ret); |
2171 | 0 | } |
2172 | | |
2173 | | /** |
2174 | | * xmlFACompareAtomTypes: |
2175 | | * @type1: an atom type |
2176 | | * @type2: an atom type |
2177 | | * |
2178 | | * Compares two atoms type to check whether they intersect in some ways, |
2179 | | * this is used by xmlFACompareAtoms only |
2180 | | * |
2181 | | * Returns 1 if they may intersect and 0 otherwise |
2182 | | */ |
2183 | | static int |
2184 | 0 | xmlFACompareAtomTypes(xmlRegAtomType type1, xmlRegAtomType type2) { |
2185 | 0 | if ((type1 == XML_REGEXP_EPSILON) || |
2186 | 0 | (type1 == XML_REGEXP_CHARVAL) || |
2187 | 0 | (type1 == XML_REGEXP_RANGES) || |
2188 | 0 | (type1 == XML_REGEXP_SUBREG) || |
2189 | 0 | (type1 == XML_REGEXP_STRING) || |
2190 | 0 | (type1 == XML_REGEXP_ANYCHAR)) |
2191 | 0 | return(1); |
2192 | 0 | if ((type2 == XML_REGEXP_EPSILON) || |
2193 | 0 | (type2 == XML_REGEXP_CHARVAL) || |
2194 | 0 | (type2 == XML_REGEXP_RANGES) || |
2195 | 0 | (type2 == XML_REGEXP_SUBREG) || |
2196 | 0 | (type2 == XML_REGEXP_STRING) || |
2197 | 0 | (type2 == XML_REGEXP_ANYCHAR)) |
2198 | 0 | return(1); |
2199 | | |
2200 | 0 | if (type1 == type2) return(1); |
2201 | | |
2202 | | /* simplify subsequent compares by making sure type1 < type2 */ |
2203 | 0 | if (type1 > type2) { |
2204 | 0 | xmlRegAtomType tmp = type1; |
2205 | 0 | type1 = type2; |
2206 | 0 | type2 = tmp; |
2207 | 0 | } |
2208 | 0 | switch (type1) { |
2209 | 0 | case XML_REGEXP_ANYSPACE: /* \s */ |
2210 | | /* can't be a letter, number, mark, punctuation, symbol */ |
2211 | 0 | if ((type2 == XML_REGEXP_NOTSPACE) || |
2212 | 0 | ((type2 >= XML_REGEXP_LETTER) && |
2213 | 0 | (type2 <= XML_REGEXP_LETTER_OTHERS)) || |
2214 | 0 | ((type2 >= XML_REGEXP_NUMBER) && |
2215 | 0 | (type2 <= XML_REGEXP_NUMBER_OTHERS)) || |
2216 | 0 | ((type2 >= XML_REGEXP_MARK) && |
2217 | 0 | (type2 <= XML_REGEXP_MARK_ENCLOSING)) || |
2218 | 0 | ((type2 >= XML_REGEXP_PUNCT) && |
2219 | 0 | (type2 <= XML_REGEXP_PUNCT_OTHERS)) || |
2220 | 0 | ((type2 >= XML_REGEXP_SYMBOL) && |
2221 | 0 | (type2 <= XML_REGEXP_SYMBOL_OTHERS)) |
2222 | 0 | ) return(0); |
2223 | 0 | break; |
2224 | 0 | case XML_REGEXP_NOTSPACE: /* \S */ |
2225 | 0 | break; |
2226 | 0 | case XML_REGEXP_INITNAME: /* \l */ |
2227 | | /* can't be a number, mark, separator, punctuation, symbol or other */ |
2228 | 0 | if ((type2 == XML_REGEXP_NOTINITNAME) || |
2229 | 0 | ((type2 >= XML_REGEXP_NUMBER) && |
2230 | 0 | (type2 <= XML_REGEXP_NUMBER_OTHERS)) || |
2231 | 0 | ((type2 >= XML_REGEXP_MARK) && |
2232 | 0 | (type2 <= XML_REGEXP_MARK_ENCLOSING)) || |
2233 | 0 | ((type2 >= XML_REGEXP_SEPAR) && |
2234 | 0 | (type2 <= XML_REGEXP_SEPAR_PARA)) || |
2235 | 0 | ((type2 >= XML_REGEXP_PUNCT) && |
2236 | 0 | (type2 <= XML_REGEXP_PUNCT_OTHERS)) || |
2237 | 0 | ((type2 >= XML_REGEXP_SYMBOL) && |
2238 | 0 | (type2 <= XML_REGEXP_SYMBOL_OTHERS)) || |
2239 | 0 | ((type2 >= XML_REGEXP_OTHER) && |
2240 | 0 | (type2 <= XML_REGEXP_OTHER_NA)) |
2241 | 0 | ) return(0); |
2242 | 0 | break; |
2243 | 0 | case XML_REGEXP_NOTINITNAME: /* \L */ |
2244 | 0 | break; |
2245 | 0 | case XML_REGEXP_NAMECHAR: /* \c */ |
2246 | | /* can't be a mark, separator, punctuation, symbol or other */ |
2247 | 0 | if ((type2 == XML_REGEXP_NOTNAMECHAR) || |
2248 | 0 | ((type2 >= XML_REGEXP_MARK) && |
2249 | 0 | (type2 <= XML_REGEXP_MARK_ENCLOSING)) || |
2250 | 0 | ((type2 >= XML_REGEXP_PUNCT) && |
2251 | 0 | (type2 <= XML_REGEXP_PUNCT_OTHERS)) || |
2252 | 0 | ((type2 >= XML_REGEXP_SEPAR) && |
2253 | 0 | (type2 <= XML_REGEXP_SEPAR_PARA)) || |
2254 | 0 | ((type2 >= XML_REGEXP_SYMBOL) && |
2255 | 0 | (type2 <= XML_REGEXP_SYMBOL_OTHERS)) || |
2256 | 0 | ((type2 >= XML_REGEXP_OTHER) && |
2257 | 0 | (type2 <= XML_REGEXP_OTHER_NA)) |
2258 | 0 | ) return(0); |
2259 | 0 | break; |
2260 | 0 | case XML_REGEXP_NOTNAMECHAR: /* \C */ |
2261 | 0 | break; |
2262 | 0 | case XML_REGEXP_DECIMAL: /* \d */ |
2263 | | /* can't be a letter, mark, separator, punctuation, symbol or other */ |
2264 | 0 | if ((type2 == XML_REGEXP_NOTDECIMAL) || |
2265 | 0 | (type2 == XML_REGEXP_REALCHAR) || |
2266 | 0 | ((type2 >= XML_REGEXP_LETTER) && |
2267 | 0 | (type2 <= XML_REGEXP_LETTER_OTHERS)) || |
2268 | 0 | ((type2 >= XML_REGEXP_MARK) && |
2269 | 0 | (type2 <= XML_REGEXP_MARK_ENCLOSING)) || |
2270 | 0 | ((type2 >= XML_REGEXP_PUNCT) && |
2271 | 0 | (type2 <= XML_REGEXP_PUNCT_OTHERS)) || |
2272 | 0 | ((type2 >= XML_REGEXP_SEPAR) && |
2273 | 0 | (type2 <= XML_REGEXP_SEPAR_PARA)) || |
2274 | 0 | ((type2 >= XML_REGEXP_SYMBOL) && |
2275 | 0 | (type2 <= XML_REGEXP_SYMBOL_OTHERS)) || |
2276 | 0 | ((type2 >= XML_REGEXP_OTHER) && |
2277 | 0 | (type2 <= XML_REGEXP_OTHER_NA)) |
2278 | 0 | )return(0); |
2279 | 0 | break; |
2280 | 0 | case XML_REGEXP_NOTDECIMAL: /* \D */ |
2281 | 0 | break; |
2282 | 0 | case XML_REGEXP_REALCHAR: /* \w */ |
2283 | | /* can't be a mark, separator, punctuation, symbol or other */ |
2284 | 0 | if ((type2 == XML_REGEXP_NOTDECIMAL) || |
2285 | 0 | ((type2 >= XML_REGEXP_MARK) && |
2286 | 0 | (type2 <= XML_REGEXP_MARK_ENCLOSING)) || |
2287 | 0 | ((type2 >= XML_REGEXP_PUNCT) && |
2288 | 0 | (type2 <= XML_REGEXP_PUNCT_OTHERS)) || |
2289 | 0 | ((type2 >= XML_REGEXP_SEPAR) && |
2290 | 0 | (type2 <= XML_REGEXP_SEPAR_PARA)) || |
2291 | 0 | ((type2 >= XML_REGEXP_SYMBOL) && |
2292 | 0 | (type2 <= XML_REGEXP_SYMBOL_OTHERS)) || |
2293 | 0 | ((type2 >= XML_REGEXP_OTHER) && |
2294 | 0 | (type2 <= XML_REGEXP_OTHER_NA)) |
2295 | 0 | )return(0); |
2296 | 0 | break; |
2297 | 0 | case XML_REGEXP_NOTREALCHAR: /* \W */ |
2298 | 0 | break; |
2299 | | /* |
2300 | | * at that point we know both type 1 and type2 are from |
2301 | | * character categories are ordered and are different, |
2302 | | * it becomes simple because this is a partition |
2303 | | */ |
2304 | 0 | case XML_REGEXP_LETTER: |
2305 | 0 | if (type2 <= XML_REGEXP_LETTER_OTHERS) |
2306 | 0 | return(1); |
2307 | 0 | return(0); |
2308 | 0 | case XML_REGEXP_LETTER_UPPERCASE: |
2309 | 0 | case XML_REGEXP_LETTER_LOWERCASE: |
2310 | 0 | case XML_REGEXP_LETTER_TITLECASE: |
2311 | 0 | case XML_REGEXP_LETTER_MODIFIER: |
2312 | 0 | case XML_REGEXP_LETTER_OTHERS: |
2313 | 0 | return(0); |
2314 | 0 | case XML_REGEXP_MARK: |
2315 | 0 | if (type2 <= XML_REGEXP_MARK_ENCLOSING) |
2316 | 0 | return(1); |
2317 | 0 | return(0); |
2318 | 0 | case XML_REGEXP_MARK_NONSPACING: |
2319 | 0 | case XML_REGEXP_MARK_SPACECOMBINING: |
2320 | 0 | case XML_REGEXP_MARK_ENCLOSING: |
2321 | 0 | return(0); |
2322 | 0 | case XML_REGEXP_NUMBER: |
2323 | 0 | if (type2 <= XML_REGEXP_NUMBER_OTHERS) |
2324 | 0 | return(1); |
2325 | 0 | return(0); |
2326 | 0 | case XML_REGEXP_NUMBER_DECIMAL: |
2327 | 0 | case XML_REGEXP_NUMBER_LETTER: |
2328 | 0 | case XML_REGEXP_NUMBER_OTHERS: |
2329 | 0 | return(0); |
2330 | 0 | case XML_REGEXP_PUNCT: |
2331 | 0 | if (type2 <= XML_REGEXP_PUNCT_OTHERS) |
2332 | 0 | return(1); |
2333 | 0 | return(0); |
2334 | 0 | case XML_REGEXP_PUNCT_CONNECTOR: |
2335 | 0 | case XML_REGEXP_PUNCT_DASH: |
2336 | 0 | case XML_REGEXP_PUNCT_OPEN: |
2337 | 0 | case XML_REGEXP_PUNCT_CLOSE: |
2338 | 0 | case XML_REGEXP_PUNCT_INITQUOTE: |
2339 | 0 | case XML_REGEXP_PUNCT_FINQUOTE: |
2340 | 0 | case XML_REGEXP_PUNCT_OTHERS: |
2341 | 0 | return(0); |
2342 | 0 | case XML_REGEXP_SEPAR: |
2343 | 0 | if (type2 <= XML_REGEXP_SEPAR_PARA) |
2344 | 0 | return(1); |
2345 | 0 | return(0); |
2346 | 0 | case XML_REGEXP_SEPAR_SPACE: |
2347 | 0 | case XML_REGEXP_SEPAR_LINE: |
2348 | 0 | case XML_REGEXP_SEPAR_PARA: |
2349 | 0 | return(0); |
2350 | 0 | case XML_REGEXP_SYMBOL: |
2351 | 0 | if (type2 <= XML_REGEXP_SYMBOL_OTHERS) |
2352 | 0 | return(1); |
2353 | 0 | return(0); |
2354 | 0 | case XML_REGEXP_SYMBOL_MATH: |
2355 | 0 | case XML_REGEXP_SYMBOL_CURRENCY: |
2356 | 0 | case XML_REGEXP_SYMBOL_MODIFIER: |
2357 | 0 | case XML_REGEXP_SYMBOL_OTHERS: |
2358 | 0 | return(0); |
2359 | 0 | case XML_REGEXP_OTHER: |
2360 | 0 | if (type2 <= XML_REGEXP_OTHER_NA) |
2361 | 0 | return(1); |
2362 | 0 | return(0); |
2363 | 0 | case XML_REGEXP_OTHER_CONTROL: |
2364 | 0 | case XML_REGEXP_OTHER_FORMAT: |
2365 | 0 | case XML_REGEXP_OTHER_PRIVATE: |
2366 | 0 | case XML_REGEXP_OTHER_NA: |
2367 | 0 | return(0); |
2368 | 0 | default: |
2369 | 0 | break; |
2370 | 0 | } |
2371 | 0 | return(1); |
2372 | 0 | } |
2373 | | |
2374 | | /** |
2375 | | * xmlFAEqualAtoms: |
2376 | | * @atom1: an atom |
2377 | | * @atom2: an atom |
2378 | | * @deep: if not set only compare string pointers |
2379 | | * |
2380 | | * Compares two atoms to check whether they are the same exactly |
2381 | | * this is used to remove equivalent transitions |
2382 | | * |
2383 | | * Returns 1 if same and 0 otherwise |
2384 | | */ |
2385 | | static int |
2386 | 0 | xmlFAEqualAtoms(xmlRegAtomPtr atom1, xmlRegAtomPtr atom2, int deep) { |
2387 | 0 | int ret = 0; |
2388 | |
|
2389 | 0 | if (atom1 == atom2) |
2390 | 0 | return(1); |
2391 | 0 | if ((atom1 == NULL) || (atom2 == NULL)) |
2392 | 0 | return(0); |
2393 | | |
2394 | 0 | if (atom1->type != atom2->type) |
2395 | 0 | return(0); |
2396 | 0 | switch (atom1->type) { |
2397 | 0 | case XML_REGEXP_EPSILON: |
2398 | 0 | ret = 0; |
2399 | 0 | break; |
2400 | 0 | case XML_REGEXP_STRING: |
2401 | 0 | if (!deep) |
2402 | 0 | ret = (atom1->valuep == atom2->valuep); |
2403 | 0 | else |
2404 | 0 | ret = xmlStrEqual((xmlChar *)atom1->valuep, |
2405 | 0 | (xmlChar *)atom2->valuep); |
2406 | 0 | break; |
2407 | 0 | case XML_REGEXP_CHARVAL: |
2408 | 0 | ret = (atom1->codepoint == atom2->codepoint); |
2409 | 0 | break; |
2410 | 0 | case XML_REGEXP_RANGES: |
2411 | | /* too hard to do in the general case */ |
2412 | 0 | ret = 0; |
2413 | 0 | default: |
2414 | 0 | break; |
2415 | 0 | } |
2416 | 0 | return(ret); |
2417 | 0 | } |
2418 | | |
2419 | | /** |
2420 | | * xmlFACompareAtoms: |
2421 | | * @atom1: an atom |
2422 | | * @atom2: an atom |
2423 | | * @deep: if not set only compare string pointers |
2424 | | * |
2425 | | * Compares two atoms to check whether they intersect in some ways, |
2426 | | * this is used by xmlFAComputesDeterminism and xmlFARecurseDeterminism only |
2427 | | * |
2428 | | * Returns 1 if yes and 0 otherwise |
2429 | | */ |
2430 | | static int |
2431 | 0 | xmlFACompareAtoms(xmlRegAtomPtr atom1, xmlRegAtomPtr atom2, int deep) { |
2432 | 0 | int ret = 1; |
2433 | |
|
2434 | 0 | if (atom1 == atom2) |
2435 | 0 | return(1); |
2436 | 0 | if ((atom1 == NULL) || (atom2 == NULL)) |
2437 | 0 | return(0); |
2438 | | |
2439 | 0 | if ((atom1->type == XML_REGEXP_ANYCHAR) || |
2440 | 0 | (atom2->type == XML_REGEXP_ANYCHAR)) |
2441 | 0 | return(1); |
2442 | | |
2443 | 0 | if (atom1->type > atom2->type) { |
2444 | 0 | xmlRegAtomPtr tmp; |
2445 | 0 | tmp = atom1; |
2446 | 0 | atom1 = atom2; |
2447 | 0 | atom2 = tmp; |
2448 | 0 | } |
2449 | 0 | if (atom1->type != atom2->type) { |
2450 | 0 | ret = xmlFACompareAtomTypes(atom1->type, atom2->type); |
2451 | | /* if they can't intersect at the type level break now */ |
2452 | 0 | if (ret == 0) |
2453 | 0 | return(0); |
2454 | 0 | } |
2455 | 0 | switch (atom1->type) { |
2456 | 0 | case XML_REGEXP_STRING: |
2457 | 0 | if (!deep) |
2458 | 0 | ret = (atom1->valuep != atom2->valuep); |
2459 | 0 | else { |
2460 | 0 | xmlChar *val1 = (xmlChar *)atom1->valuep; |
2461 | 0 | xmlChar *val2 = (xmlChar *)atom2->valuep; |
2462 | 0 | int compound1 = (xmlStrchr(val1, '|') != NULL); |
2463 | 0 | int compound2 = (xmlStrchr(val2, '|') != NULL); |
2464 | | |
2465 | | /* Ignore negative match flag for ##other namespaces */ |
2466 | 0 | if (compound1 != compound2) |
2467 | 0 | return(0); |
2468 | | |
2469 | 0 | ret = xmlRegStrEqualWildcard(val1, val2); |
2470 | 0 | } |
2471 | 0 | break; |
2472 | 0 | case XML_REGEXP_EPSILON: |
2473 | 0 | goto not_determinist; |
2474 | 0 | case XML_REGEXP_CHARVAL: |
2475 | 0 | if (atom2->type == XML_REGEXP_CHARVAL) { |
2476 | 0 | ret = (atom1->codepoint == atom2->codepoint); |
2477 | 0 | } else { |
2478 | 0 | ret = xmlRegCheckCharacter(atom2, atom1->codepoint); |
2479 | 0 | if (ret < 0) |
2480 | 0 | ret = 1; |
2481 | 0 | } |
2482 | 0 | break; |
2483 | 0 | case XML_REGEXP_RANGES: |
2484 | 0 | if (atom2->type == XML_REGEXP_RANGES) { |
2485 | 0 | int i, j, res; |
2486 | 0 | xmlRegRangePtr r1, r2; |
2487 | | |
2488 | | /* |
2489 | | * need to check that none of the ranges eventually matches |
2490 | | */ |
2491 | 0 | for (i = 0;i < atom1->nbRanges;i++) { |
2492 | 0 | for (j = 0;j < atom2->nbRanges;j++) { |
2493 | 0 | r1 = atom1->ranges[i]; |
2494 | 0 | r2 = atom2->ranges[j]; |
2495 | 0 | res = xmlFACompareRanges(r1, r2); |
2496 | 0 | if (res == 1) { |
2497 | 0 | ret = 1; |
2498 | 0 | goto done; |
2499 | 0 | } |
2500 | 0 | } |
2501 | 0 | } |
2502 | 0 | ret = 0; |
2503 | 0 | } |
2504 | 0 | break; |
2505 | 0 | default: |
2506 | 0 | goto not_determinist; |
2507 | 0 | } |
2508 | 0 | done: |
2509 | 0 | if (atom1->neg != atom2->neg) { |
2510 | 0 | ret = !ret; |
2511 | 0 | } |
2512 | 0 | if (ret == 0) |
2513 | 0 | return(0); |
2514 | 0 | not_determinist: |
2515 | 0 | return(1); |
2516 | 0 | } |
2517 | | |
2518 | | /** |
2519 | | * xmlFARecurseDeterminism: |
2520 | | * @ctxt: a regexp parser context |
2521 | | * |
2522 | | * Check whether the associated regexp is determinist, |
2523 | | * should be called after xmlFAEliminateEpsilonTransitions() |
2524 | | * |
2525 | | */ |
2526 | | static int |
2527 | | xmlFARecurseDeterminism(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr state, |
2528 | 0 | int fromnr, int tonr, xmlRegAtomPtr atom) { |
2529 | 0 | int ret = 1; |
2530 | 0 | int res; |
2531 | 0 | int transnr, nbTrans; |
2532 | 0 | xmlRegTransPtr t1; |
2533 | 0 | int deep = 1; |
2534 | |
|
2535 | 0 | if (state == NULL) |
2536 | 0 | return(ret); |
2537 | 0 | if (state->markd == XML_REGEXP_MARK_VISITED) |
2538 | 0 | return(ret); |
2539 | | |
2540 | 0 | if (ctxt->flags & AM_AUTOMATA_RNG) |
2541 | 0 | deep = 0; |
2542 | | |
2543 | | /* |
2544 | | * don't recurse on transitions potentially added in the course of |
2545 | | * the elimination. |
2546 | | */ |
2547 | 0 | nbTrans = state->nbTrans; |
2548 | 0 | for (transnr = 0;transnr < nbTrans;transnr++) { |
2549 | 0 | t1 = &(state->trans[transnr]); |
2550 | | /* |
2551 | | * check transitions conflicting with the one looked at |
2552 | | */ |
2553 | 0 | if ((t1->to < 0) || (t1->to == fromnr)) |
2554 | 0 | continue; |
2555 | 0 | if (t1->atom == NULL) { |
2556 | 0 | state->markd = XML_REGEXP_MARK_VISITED; |
2557 | 0 | res = xmlFARecurseDeterminism(ctxt, ctxt->states[t1->to], |
2558 | 0 | fromnr, tonr, atom); |
2559 | 0 | if (res == 0) { |
2560 | 0 | ret = 0; |
2561 | | /* t1->nd = 1; */ |
2562 | 0 | } |
2563 | 0 | continue; |
2564 | 0 | } |
2565 | 0 | if (xmlFACompareAtoms(t1->atom, atom, deep)) { |
2566 | | /* Treat equal transitions as deterministic. */ |
2567 | 0 | if ((t1->to != tonr) || |
2568 | 0 | (!xmlFAEqualAtoms(t1->atom, atom, deep))) |
2569 | 0 | ret = 0; |
2570 | | /* mark the transition as non-deterministic */ |
2571 | 0 | t1->nd = 1; |
2572 | 0 | } |
2573 | 0 | } |
2574 | 0 | return(ret); |
2575 | 0 | } |
2576 | | |
2577 | | /** |
2578 | | * xmlFAFinishRecurseDeterminism: |
2579 | | * @ctxt: a regexp parser context |
2580 | | * |
2581 | | * Reset flags after checking determinism. |
2582 | | */ |
2583 | | static void |
2584 | 0 | xmlFAFinishRecurseDeterminism(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr state) { |
2585 | 0 | int transnr, nbTrans; |
2586 | |
|
2587 | 0 | if (state == NULL) |
2588 | 0 | return; |
2589 | 0 | if (state->markd != XML_REGEXP_MARK_VISITED) |
2590 | 0 | return; |
2591 | 0 | state->markd = 0; |
2592 | |
|
2593 | 0 | nbTrans = state->nbTrans; |
2594 | 0 | for (transnr = 0; transnr < nbTrans; transnr++) { |
2595 | 0 | xmlRegTransPtr t1 = &state->trans[transnr]; |
2596 | 0 | if ((t1->atom == NULL) && (t1->to >= 0)) |
2597 | 0 | xmlFAFinishRecurseDeterminism(ctxt, ctxt->states[t1->to]); |
2598 | 0 | } |
2599 | 0 | } |
2600 | | |
2601 | | /** |
2602 | | * xmlFAComputesDeterminism: |
2603 | | * @ctxt: a regexp parser context |
2604 | | * |
2605 | | * Check whether the associated regexp is determinist, |
2606 | | * should be called after xmlFAEliminateEpsilonTransitions() |
2607 | | * |
2608 | | */ |
2609 | | static int |
2610 | 0 | xmlFAComputesDeterminism(xmlRegParserCtxtPtr ctxt) { |
2611 | 0 | int statenr, transnr; |
2612 | 0 | xmlRegStatePtr state; |
2613 | 0 | xmlRegTransPtr t1, t2, last; |
2614 | 0 | int i; |
2615 | 0 | int ret = 1; |
2616 | 0 | int deep = 1; |
2617 | |
|
2618 | 0 | if (ctxt->determinist != -1) |
2619 | 0 | return(ctxt->determinist); |
2620 | | |
2621 | 0 | if (ctxt->flags & AM_AUTOMATA_RNG) |
2622 | 0 | deep = 0; |
2623 | | |
2624 | | /* |
2625 | | * First cleanup the automata removing cancelled transitions |
2626 | | */ |
2627 | 0 | for (statenr = 0;statenr < ctxt->nbStates;statenr++) { |
2628 | 0 | state = ctxt->states[statenr]; |
2629 | 0 | if (state == NULL) |
2630 | 0 | continue; |
2631 | 0 | if (state->nbTrans < 2) |
2632 | 0 | continue; |
2633 | 0 | for (transnr = 0;transnr < state->nbTrans;transnr++) { |
2634 | 0 | t1 = &(state->trans[transnr]); |
2635 | | /* |
2636 | | * Determinism checks in case of counted or all transitions |
2637 | | * will have to be handled separately |
2638 | | */ |
2639 | 0 | if (t1->atom == NULL) { |
2640 | | /* t1->nd = 1; */ |
2641 | 0 | continue; |
2642 | 0 | } |
2643 | 0 | if (t1->to < 0) /* eliminated */ |
2644 | 0 | continue; |
2645 | 0 | for (i = 0;i < transnr;i++) { |
2646 | 0 | t2 = &(state->trans[i]); |
2647 | 0 | if (t2->to < 0) /* eliminated */ |
2648 | 0 | continue; |
2649 | 0 | if (t2->atom != NULL) { |
2650 | 0 | if (t1->to == t2->to) { |
2651 | | /* |
2652 | | * Here we use deep because we want to keep the |
2653 | | * transitions which indicate a conflict |
2654 | | */ |
2655 | 0 | if (xmlFAEqualAtoms(t1->atom, t2->atom, deep) && |
2656 | 0 | (t1->counter == t2->counter) && |
2657 | 0 | (t1->count == t2->count)) |
2658 | 0 | t2->to = -1; /* eliminated */ |
2659 | 0 | } |
2660 | 0 | } |
2661 | 0 | } |
2662 | 0 | } |
2663 | 0 | } |
2664 | | |
2665 | | /* |
2666 | | * Check for all states that there aren't 2 transitions |
2667 | | * with the same atom and a different target. |
2668 | | */ |
2669 | 0 | for (statenr = 0;statenr < ctxt->nbStates;statenr++) { |
2670 | 0 | state = ctxt->states[statenr]; |
2671 | 0 | if (state == NULL) |
2672 | 0 | continue; |
2673 | 0 | if (state->nbTrans < 2) |
2674 | 0 | continue; |
2675 | 0 | last = NULL; |
2676 | 0 | for (transnr = 0;transnr < state->nbTrans;transnr++) { |
2677 | 0 | t1 = &(state->trans[transnr]); |
2678 | | /* |
2679 | | * Determinism checks in case of counted or all transitions |
2680 | | * will have to be handled separately |
2681 | | */ |
2682 | 0 | if (t1->atom == NULL) { |
2683 | 0 | continue; |
2684 | 0 | } |
2685 | 0 | if (t1->to < 0) /* eliminated */ |
2686 | 0 | continue; |
2687 | 0 | for (i = 0;i < transnr;i++) { |
2688 | 0 | t2 = &(state->trans[i]); |
2689 | 0 | if (t2->to < 0) /* eliminated */ |
2690 | 0 | continue; |
2691 | 0 | if (t2->atom != NULL) { |
2692 | | /* |
2693 | | * But here we don't use deep because we want to |
2694 | | * find transitions which indicate a conflict |
2695 | | */ |
2696 | 0 | if (xmlFACompareAtoms(t1->atom, t2->atom, 1)) { |
2697 | | /* |
2698 | | * Treat equal counter transitions that couldn't be |
2699 | | * eliminated as deterministic. |
2700 | | */ |
2701 | 0 | if ((t1->to != t2->to) || |
2702 | 0 | (t1->counter == t2->counter) || |
2703 | 0 | (!xmlFAEqualAtoms(t1->atom, t2->atom, deep))) |
2704 | 0 | ret = 0; |
2705 | | /* mark the transitions as non-deterministic ones */ |
2706 | 0 | t1->nd = 1; |
2707 | 0 | t2->nd = 1; |
2708 | 0 | last = t1; |
2709 | 0 | } |
2710 | 0 | } else { |
2711 | 0 | int res; |
2712 | | |
2713 | | /* |
2714 | | * do the closure in case of remaining specific |
2715 | | * epsilon transitions like choices or all |
2716 | | */ |
2717 | 0 | res = xmlFARecurseDeterminism(ctxt, ctxt->states[t2->to], |
2718 | 0 | statenr, t1->to, t1->atom); |
2719 | 0 | xmlFAFinishRecurseDeterminism(ctxt, ctxt->states[t2->to]); |
2720 | | /* don't shortcut the computation so all non deterministic |
2721 | | transition get marked down |
2722 | | if (ret == 0) |
2723 | | return(0); |
2724 | | */ |
2725 | 0 | if (res == 0) { |
2726 | 0 | t1->nd = 1; |
2727 | | /* t2->nd = 1; */ |
2728 | 0 | last = t1; |
2729 | 0 | ret = 0; |
2730 | 0 | } |
2731 | 0 | } |
2732 | 0 | } |
2733 | | /* don't shortcut the computation so all non deterministic |
2734 | | transition get marked down |
2735 | | if (ret == 0) |
2736 | | break; */ |
2737 | 0 | } |
2738 | | |
2739 | | /* |
2740 | | * mark specifically the last non-deterministic transition |
2741 | | * from a state since there is no need to set-up rollback |
2742 | | * from it |
2743 | | */ |
2744 | 0 | if (last != NULL) { |
2745 | 0 | last->nd = 2; |
2746 | 0 | } |
2747 | | |
2748 | | /* don't shortcut the computation so all non deterministic |
2749 | | transition get marked down |
2750 | | if (ret == 0) |
2751 | | break; */ |
2752 | 0 | } |
2753 | |
|
2754 | 0 | ctxt->determinist = ret; |
2755 | 0 | return(ret); |
2756 | 0 | } |
2757 | | |
2758 | | /************************************************************************ |
2759 | | * * |
2760 | | * Routines to check input against transition atoms * |
2761 | | * * |
2762 | | ************************************************************************/ |
2763 | | |
2764 | | static int |
2765 | | xmlRegCheckCharacterRange(xmlRegAtomType type, int codepoint, int neg, |
2766 | 0 | int start, int end, const xmlChar *blockName) { |
2767 | 0 | int ret = 0; |
2768 | |
|
2769 | 0 | switch (type) { |
2770 | 0 | case XML_REGEXP_STRING: |
2771 | 0 | case XML_REGEXP_SUBREG: |
2772 | 0 | case XML_REGEXP_RANGES: |
2773 | 0 | case XML_REGEXP_EPSILON: |
2774 | 0 | return(-1); |
2775 | 0 | case XML_REGEXP_ANYCHAR: |
2776 | 0 | ret = ((codepoint != '\n') && (codepoint != '\r')); |
2777 | 0 | break; |
2778 | 0 | case XML_REGEXP_CHARVAL: |
2779 | 0 | ret = ((codepoint >= start) && (codepoint <= end)); |
2780 | 0 | break; |
2781 | 0 | case XML_REGEXP_NOTSPACE: |
2782 | 0 | neg = !neg; |
2783 | | /* Falls through. */ |
2784 | 0 | case XML_REGEXP_ANYSPACE: |
2785 | 0 | ret = ((codepoint == '\n') || (codepoint == '\r') || |
2786 | 0 | (codepoint == '\t') || (codepoint == ' ')); |
2787 | 0 | break; |
2788 | 0 | case XML_REGEXP_NOTINITNAME: |
2789 | 0 | neg = !neg; |
2790 | | /* Falls through. */ |
2791 | 0 | case XML_REGEXP_INITNAME: |
2792 | 0 | ret = (IS_LETTER(codepoint) || |
2793 | 0 | (codepoint == '_') || (codepoint == ':')); |
2794 | 0 | break; |
2795 | 0 | case XML_REGEXP_NOTNAMECHAR: |
2796 | 0 | neg = !neg; |
2797 | | /* Falls through. */ |
2798 | 0 | case XML_REGEXP_NAMECHAR: |
2799 | 0 | ret = (IS_LETTER(codepoint) || IS_DIGIT(codepoint) || |
2800 | 0 | (codepoint == '.') || (codepoint == '-') || |
2801 | 0 | (codepoint == '_') || (codepoint == ':') || |
2802 | 0 | IS_COMBINING(codepoint) || IS_EXTENDER(codepoint)); |
2803 | 0 | break; |
2804 | 0 | case XML_REGEXP_NOTDECIMAL: |
2805 | 0 | neg = !neg; |
2806 | | /* Falls through. */ |
2807 | 0 | case XML_REGEXP_DECIMAL: |
2808 | 0 | ret = xmlUCSIsCatNd(codepoint); |
2809 | 0 | break; |
2810 | 0 | case XML_REGEXP_REALCHAR: |
2811 | 0 | neg = !neg; |
2812 | | /* Falls through. */ |
2813 | 0 | case XML_REGEXP_NOTREALCHAR: |
2814 | 0 | ret = xmlUCSIsCatP(codepoint); |
2815 | 0 | if (ret == 0) |
2816 | 0 | ret = xmlUCSIsCatZ(codepoint); |
2817 | 0 | if (ret == 0) |
2818 | 0 | ret = xmlUCSIsCatC(codepoint); |
2819 | 0 | break; |
2820 | 0 | case XML_REGEXP_LETTER: |
2821 | 0 | ret = xmlUCSIsCatL(codepoint); |
2822 | 0 | break; |
2823 | 0 | case XML_REGEXP_LETTER_UPPERCASE: |
2824 | 0 | ret = xmlUCSIsCatLu(codepoint); |
2825 | 0 | break; |
2826 | 0 | case XML_REGEXP_LETTER_LOWERCASE: |
2827 | 0 | ret = xmlUCSIsCatLl(codepoint); |
2828 | 0 | break; |
2829 | 0 | case XML_REGEXP_LETTER_TITLECASE: |
2830 | 0 | ret = xmlUCSIsCatLt(codepoint); |
2831 | 0 | break; |
2832 | 0 | case XML_REGEXP_LETTER_MODIFIER: |
2833 | 0 | ret = xmlUCSIsCatLm(codepoint); |
2834 | 0 | break; |
2835 | 0 | case XML_REGEXP_LETTER_OTHERS: |
2836 | 0 | ret = xmlUCSIsCatLo(codepoint); |
2837 | 0 | break; |
2838 | 0 | case XML_REGEXP_MARK: |
2839 | 0 | ret = xmlUCSIsCatM(codepoint); |
2840 | 0 | break; |
2841 | 0 | case XML_REGEXP_MARK_NONSPACING: |
2842 | 0 | ret = xmlUCSIsCatMn(codepoint); |
2843 | 0 | break; |
2844 | 0 | case XML_REGEXP_MARK_SPACECOMBINING: |
2845 | 0 | ret = xmlUCSIsCatMc(codepoint); |
2846 | 0 | break; |
2847 | 0 | case XML_REGEXP_MARK_ENCLOSING: |
2848 | 0 | ret = xmlUCSIsCatMe(codepoint); |
2849 | 0 | break; |
2850 | 0 | case XML_REGEXP_NUMBER: |
2851 | 0 | ret = xmlUCSIsCatN(codepoint); |
2852 | 0 | break; |
2853 | 0 | case XML_REGEXP_NUMBER_DECIMAL: |
2854 | 0 | ret = xmlUCSIsCatNd(codepoint); |
2855 | 0 | break; |
2856 | 0 | case XML_REGEXP_NUMBER_LETTER: |
2857 | 0 | ret = xmlUCSIsCatNl(codepoint); |
2858 | 0 | break; |
2859 | 0 | case XML_REGEXP_NUMBER_OTHERS: |
2860 | 0 | ret = xmlUCSIsCatNo(codepoint); |
2861 | 0 | break; |
2862 | 0 | case XML_REGEXP_PUNCT: |
2863 | 0 | ret = xmlUCSIsCatP(codepoint); |
2864 | 0 | break; |
2865 | 0 | case XML_REGEXP_PUNCT_CONNECTOR: |
2866 | 0 | ret = xmlUCSIsCatPc(codepoint); |
2867 | 0 | break; |
2868 | 0 | case XML_REGEXP_PUNCT_DASH: |
2869 | 0 | ret = xmlUCSIsCatPd(codepoint); |
2870 | 0 | break; |
2871 | 0 | case XML_REGEXP_PUNCT_OPEN: |
2872 | 0 | ret = xmlUCSIsCatPs(codepoint); |
2873 | 0 | break; |
2874 | 0 | case XML_REGEXP_PUNCT_CLOSE: |
2875 | 0 | ret = xmlUCSIsCatPe(codepoint); |
2876 | 0 | break; |
2877 | 0 | case XML_REGEXP_PUNCT_INITQUOTE: |
2878 | 0 | ret = xmlUCSIsCatPi(codepoint); |
2879 | 0 | break; |
2880 | 0 | case XML_REGEXP_PUNCT_FINQUOTE: |
2881 | 0 | ret = xmlUCSIsCatPf(codepoint); |
2882 | 0 | break; |
2883 | 0 | case XML_REGEXP_PUNCT_OTHERS: |
2884 | 0 | ret = xmlUCSIsCatPo(codepoint); |
2885 | 0 | break; |
2886 | 0 | case XML_REGEXP_SEPAR: |
2887 | 0 | ret = xmlUCSIsCatZ(codepoint); |
2888 | 0 | break; |
2889 | 0 | case XML_REGEXP_SEPAR_SPACE: |
2890 | 0 | ret = xmlUCSIsCatZs(codepoint); |
2891 | 0 | break; |
2892 | 0 | case XML_REGEXP_SEPAR_LINE: |
2893 | 0 | ret = xmlUCSIsCatZl(codepoint); |
2894 | 0 | break; |
2895 | 0 | case XML_REGEXP_SEPAR_PARA: |
2896 | 0 | ret = xmlUCSIsCatZp(codepoint); |
2897 | 0 | break; |
2898 | 0 | case XML_REGEXP_SYMBOL: |
2899 | 0 | ret = xmlUCSIsCatS(codepoint); |
2900 | 0 | break; |
2901 | 0 | case XML_REGEXP_SYMBOL_MATH: |
2902 | 0 | ret = xmlUCSIsCatSm(codepoint); |
2903 | 0 | break; |
2904 | 0 | case XML_REGEXP_SYMBOL_CURRENCY: |
2905 | 0 | ret = xmlUCSIsCatSc(codepoint); |
2906 | 0 | break; |
2907 | 0 | case XML_REGEXP_SYMBOL_MODIFIER: |
2908 | 0 | ret = xmlUCSIsCatSk(codepoint); |
2909 | 0 | break; |
2910 | 0 | case XML_REGEXP_SYMBOL_OTHERS: |
2911 | 0 | ret = xmlUCSIsCatSo(codepoint); |
2912 | 0 | break; |
2913 | 0 | case XML_REGEXP_OTHER: |
2914 | 0 | ret = xmlUCSIsCatC(codepoint); |
2915 | 0 | break; |
2916 | 0 | case XML_REGEXP_OTHER_CONTROL: |
2917 | 0 | ret = xmlUCSIsCatCc(codepoint); |
2918 | 0 | break; |
2919 | 0 | case XML_REGEXP_OTHER_FORMAT: |
2920 | 0 | ret = xmlUCSIsCatCf(codepoint); |
2921 | 0 | break; |
2922 | 0 | case XML_REGEXP_OTHER_PRIVATE: |
2923 | 0 | ret = xmlUCSIsCatCo(codepoint); |
2924 | 0 | break; |
2925 | 0 | case XML_REGEXP_OTHER_NA: |
2926 | | /* ret = xmlUCSIsCatCn(codepoint); */ |
2927 | | /* Seems it doesn't exist anymore in recent Unicode releases */ |
2928 | 0 | ret = 0; |
2929 | 0 | break; |
2930 | 0 | case XML_REGEXP_BLOCK_NAME: |
2931 | 0 | ret = xmlUCSIsBlock(codepoint, (const char *) blockName); |
2932 | 0 | break; |
2933 | 0 | } |
2934 | 0 | if (neg) |
2935 | 0 | return(!ret); |
2936 | 0 | return(ret); |
2937 | 0 | } |
2938 | | |
2939 | | static int |
2940 | 0 | xmlRegCheckCharacter(xmlRegAtomPtr atom, int codepoint) { |
2941 | 0 | int i, ret = 0; |
2942 | 0 | xmlRegRangePtr range; |
2943 | |
|
2944 | 0 | if ((atom == NULL) || (!IS_CHAR(codepoint))) |
2945 | 0 | return(-1); |
2946 | | |
2947 | 0 | switch (atom->type) { |
2948 | 0 | case XML_REGEXP_SUBREG: |
2949 | 0 | case XML_REGEXP_EPSILON: |
2950 | 0 | return(-1); |
2951 | 0 | case XML_REGEXP_CHARVAL: |
2952 | 0 | return(codepoint == atom->codepoint); |
2953 | 0 | case XML_REGEXP_RANGES: { |
2954 | 0 | int accept = 0; |
2955 | |
|
2956 | 0 | for (i = 0;i < atom->nbRanges;i++) { |
2957 | 0 | range = atom->ranges[i]; |
2958 | 0 | if (range->neg == 2) { |
2959 | 0 | ret = xmlRegCheckCharacterRange(range->type, codepoint, |
2960 | 0 | 0, range->start, range->end, |
2961 | 0 | range->blockName); |
2962 | 0 | if (ret != 0) |
2963 | 0 | return(0); /* excluded char */ |
2964 | 0 | } else if (range->neg) { |
2965 | 0 | ret = xmlRegCheckCharacterRange(range->type, codepoint, |
2966 | 0 | 0, range->start, range->end, |
2967 | 0 | range->blockName); |
2968 | 0 | if (ret == 0) |
2969 | 0 | accept = 1; |
2970 | 0 | else |
2971 | 0 | return(0); |
2972 | 0 | } else { |
2973 | 0 | ret = xmlRegCheckCharacterRange(range->type, codepoint, |
2974 | 0 | 0, range->start, range->end, |
2975 | 0 | range->blockName); |
2976 | 0 | if (ret != 0) |
2977 | 0 | accept = 1; /* might still be excluded */ |
2978 | 0 | } |
2979 | 0 | } |
2980 | 0 | return(accept); |
2981 | 0 | } |
2982 | 0 | case XML_REGEXP_STRING: |
2983 | 0 | printf("TODO: XML_REGEXP_STRING\n"); |
2984 | 0 | return(-1); |
2985 | 0 | case XML_REGEXP_ANYCHAR: |
2986 | 0 | case XML_REGEXP_ANYSPACE: |
2987 | 0 | case XML_REGEXP_NOTSPACE: |
2988 | 0 | case XML_REGEXP_INITNAME: |
2989 | 0 | case XML_REGEXP_NOTINITNAME: |
2990 | 0 | case XML_REGEXP_NAMECHAR: |
2991 | 0 | case XML_REGEXP_NOTNAMECHAR: |
2992 | 0 | case XML_REGEXP_DECIMAL: |
2993 | 0 | case XML_REGEXP_NOTDECIMAL: |
2994 | 0 | case XML_REGEXP_REALCHAR: |
2995 | 0 | case XML_REGEXP_NOTREALCHAR: |
2996 | 0 | case XML_REGEXP_LETTER: |
2997 | 0 | case XML_REGEXP_LETTER_UPPERCASE: |
2998 | 0 | case XML_REGEXP_LETTER_LOWERCASE: |
2999 | 0 | case XML_REGEXP_LETTER_TITLECASE: |
3000 | 0 | case XML_REGEXP_LETTER_MODIFIER: |
3001 | 0 | case XML_REGEXP_LETTER_OTHERS: |
3002 | 0 | case XML_REGEXP_MARK: |
3003 | 0 | case XML_REGEXP_MARK_NONSPACING: |
3004 | 0 | case XML_REGEXP_MARK_SPACECOMBINING: |
3005 | 0 | case XML_REGEXP_MARK_ENCLOSING: |
3006 | 0 | case XML_REGEXP_NUMBER: |
3007 | 0 | case XML_REGEXP_NUMBER_DECIMAL: |
3008 | 0 | case XML_REGEXP_NUMBER_LETTER: |
3009 | 0 | case XML_REGEXP_NUMBER_OTHERS: |
3010 | 0 | case XML_REGEXP_PUNCT: |
3011 | 0 | case XML_REGEXP_PUNCT_CONNECTOR: |
3012 | 0 | case XML_REGEXP_PUNCT_DASH: |
3013 | 0 | case XML_REGEXP_PUNCT_OPEN: |
3014 | 0 | case XML_REGEXP_PUNCT_CLOSE: |
3015 | 0 | case XML_REGEXP_PUNCT_INITQUOTE: |
3016 | 0 | case XML_REGEXP_PUNCT_FINQUOTE: |
3017 | 0 | case XML_REGEXP_PUNCT_OTHERS: |
3018 | 0 | case XML_REGEXP_SEPAR: |
3019 | 0 | case XML_REGEXP_SEPAR_SPACE: |
3020 | 0 | case XML_REGEXP_SEPAR_LINE: |
3021 | 0 | case XML_REGEXP_SEPAR_PARA: |
3022 | 0 | case XML_REGEXP_SYMBOL: |
3023 | 0 | case XML_REGEXP_SYMBOL_MATH: |
3024 | 0 | case XML_REGEXP_SYMBOL_CURRENCY: |
3025 | 0 | case XML_REGEXP_SYMBOL_MODIFIER: |
3026 | 0 | case XML_REGEXP_SYMBOL_OTHERS: |
3027 | 0 | case XML_REGEXP_OTHER: |
3028 | 0 | case XML_REGEXP_OTHER_CONTROL: |
3029 | 0 | case XML_REGEXP_OTHER_FORMAT: |
3030 | 0 | case XML_REGEXP_OTHER_PRIVATE: |
3031 | 0 | case XML_REGEXP_OTHER_NA: |
3032 | 0 | case XML_REGEXP_BLOCK_NAME: |
3033 | 0 | ret = xmlRegCheckCharacterRange(atom->type, codepoint, 0, 0, 0, |
3034 | 0 | (const xmlChar *)atom->valuep); |
3035 | 0 | if (atom->neg) |
3036 | 0 | ret = !ret; |
3037 | 0 | break; |
3038 | 0 | } |
3039 | 0 | return(ret); |
3040 | 0 | } |
3041 | | |
3042 | | /************************************************************************ |
3043 | | * * |
3044 | | * Saving and restoring state of an execution context * |
3045 | | * * |
3046 | | ************************************************************************/ |
3047 | | |
3048 | | static void |
3049 | 0 | xmlFARegExecSave(xmlRegExecCtxtPtr exec) { |
3050 | 0 | #ifdef MAX_PUSH |
3051 | 0 | if (exec->nbPush > MAX_PUSH) { |
3052 | 0 | exec->status = XML_REGEXP_INTERNAL_LIMIT; |
3053 | 0 | return; |
3054 | 0 | } |
3055 | 0 | exec->nbPush++; |
3056 | 0 | #endif |
3057 | |
|
3058 | 0 | if (exec->maxRollbacks == 0) { |
3059 | 0 | exec->maxRollbacks = 4; |
3060 | 0 | exec->rollbacks = (xmlRegExecRollback *) xmlMalloc(exec->maxRollbacks * |
3061 | 0 | sizeof(xmlRegExecRollback)); |
3062 | 0 | if (exec->rollbacks == NULL) { |
3063 | 0 | xmlRegexpErrMemory(NULL, "saving regexp"); |
3064 | 0 | exec->maxRollbacks = 0; |
3065 | 0 | exec->status = XML_REGEXP_OUT_OF_MEMORY; |
3066 | 0 | return; |
3067 | 0 | } |
3068 | 0 | memset(exec->rollbacks, 0, |
3069 | 0 | exec->maxRollbacks * sizeof(xmlRegExecRollback)); |
3070 | 0 | } else if (exec->nbRollbacks >= exec->maxRollbacks) { |
3071 | 0 | xmlRegExecRollback *tmp; |
3072 | 0 | int len = exec->maxRollbacks; |
3073 | |
|
3074 | 0 | exec->maxRollbacks *= 2; |
3075 | 0 | tmp = (xmlRegExecRollback *) xmlRealloc(exec->rollbacks, |
3076 | 0 | exec->maxRollbacks * sizeof(xmlRegExecRollback)); |
3077 | 0 | if (tmp == NULL) { |
3078 | 0 | xmlRegexpErrMemory(NULL, "saving regexp"); |
3079 | 0 | exec->maxRollbacks /= 2; |
3080 | 0 | exec->status = XML_REGEXP_OUT_OF_MEMORY; |
3081 | 0 | return; |
3082 | 0 | } |
3083 | 0 | exec->rollbacks = tmp; |
3084 | 0 | tmp = &exec->rollbacks[len]; |
3085 | 0 | memset(tmp, 0, (exec->maxRollbacks - len) * sizeof(xmlRegExecRollback)); |
3086 | 0 | } |
3087 | 0 | exec->rollbacks[exec->nbRollbacks].state = exec->state; |
3088 | 0 | exec->rollbacks[exec->nbRollbacks].index = exec->index; |
3089 | 0 | exec->rollbacks[exec->nbRollbacks].nextbranch = exec->transno + 1; |
3090 | 0 | if (exec->comp->nbCounters > 0) { |
3091 | 0 | if (exec->rollbacks[exec->nbRollbacks].counts == NULL) { |
3092 | 0 | exec->rollbacks[exec->nbRollbacks].counts = (int *) |
3093 | 0 | xmlMalloc(exec->comp->nbCounters * sizeof(int)); |
3094 | 0 | if (exec->rollbacks[exec->nbRollbacks].counts == NULL) { |
3095 | 0 | xmlRegexpErrMemory(NULL, "saving regexp"); |
3096 | 0 | exec->status = XML_REGEXP_OUT_OF_MEMORY; |
3097 | 0 | return; |
3098 | 0 | } |
3099 | 0 | } |
3100 | 0 | memcpy(exec->rollbacks[exec->nbRollbacks].counts, exec->counts, |
3101 | 0 | exec->comp->nbCounters * sizeof(int)); |
3102 | 0 | } |
3103 | 0 | exec->nbRollbacks++; |
3104 | 0 | } |
3105 | | |
3106 | | static void |
3107 | 0 | xmlFARegExecRollBack(xmlRegExecCtxtPtr exec) { |
3108 | 0 | if (exec->status != XML_REGEXP_OK) |
3109 | 0 | return; |
3110 | 0 | if (exec->nbRollbacks <= 0) { |
3111 | 0 | exec->status = XML_REGEXP_NOT_FOUND; |
3112 | 0 | return; |
3113 | 0 | } |
3114 | 0 | exec->nbRollbacks--; |
3115 | 0 | exec->state = exec->rollbacks[exec->nbRollbacks].state; |
3116 | 0 | exec->index = exec->rollbacks[exec->nbRollbacks].index; |
3117 | 0 | exec->transno = exec->rollbacks[exec->nbRollbacks].nextbranch; |
3118 | 0 | if (exec->comp->nbCounters > 0) { |
3119 | 0 | if (exec->rollbacks[exec->nbRollbacks].counts == NULL) { |
3120 | 0 | fprintf(stderr, "exec save: allocation failed"); |
3121 | 0 | exec->status = XML_REGEXP_INTERNAL_ERROR; |
3122 | 0 | return; |
3123 | 0 | } |
3124 | 0 | if (exec->counts) { |
3125 | 0 | memcpy(exec->counts, exec->rollbacks[exec->nbRollbacks].counts, |
3126 | 0 | exec->comp->nbCounters * sizeof(int)); |
3127 | 0 | } |
3128 | 0 | } |
3129 | 0 | } |
3130 | | |
3131 | | /************************************************************************ |
3132 | | * * |
3133 | | * Verifier, running an input against a compiled regexp * |
3134 | | * * |
3135 | | ************************************************************************/ |
3136 | | |
3137 | | static int |
3138 | 0 | xmlFARegExec(xmlRegexpPtr comp, const xmlChar *content) { |
3139 | 0 | xmlRegExecCtxt execval; |
3140 | 0 | xmlRegExecCtxtPtr exec = &execval; |
3141 | 0 | int ret, codepoint = 0, len, deter; |
3142 | |
|
3143 | 0 | exec->inputString = content; |
3144 | 0 | exec->index = 0; |
3145 | 0 | exec->nbPush = 0; |
3146 | 0 | exec->determinist = 1; |
3147 | 0 | exec->maxRollbacks = 0; |
3148 | 0 | exec->nbRollbacks = 0; |
3149 | 0 | exec->rollbacks = NULL; |
3150 | 0 | exec->status = XML_REGEXP_OK; |
3151 | 0 | exec->comp = comp; |
3152 | 0 | exec->state = comp->states[0]; |
3153 | 0 | exec->transno = 0; |
3154 | 0 | exec->transcount = 0; |
3155 | 0 | exec->inputStack = NULL; |
3156 | 0 | exec->inputStackMax = 0; |
3157 | 0 | if (comp->nbCounters > 0) { |
3158 | 0 | exec->counts = (int *) xmlMalloc(comp->nbCounters * sizeof(int)); |
3159 | 0 | if (exec->counts == NULL) { |
3160 | 0 | xmlRegexpErrMemory(NULL, "running regexp"); |
3161 | 0 | return(XML_REGEXP_OUT_OF_MEMORY); |
3162 | 0 | } |
3163 | 0 | memset(exec->counts, 0, comp->nbCounters * sizeof(int)); |
3164 | 0 | } else |
3165 | 0 | exec->counts = NULL; |
3166 | 0 | while ((exec->status == XML_REGEXP_OK) && (exec->state != NULL) && |
3167 | 0 | ((exec->inputString[exec->index] != 0) || |
3168 | 0 | ((exec->state != NULL) && |
3169 | 0 | (exec->state->type != XML_REGEXP_FINAL_STATE)))) { |
3170 | 0 | xmlRegTransPtr trans; |
3171 | 0 | xmlRegAtomPtr atom; |
3172 | | |
3173 | | /* |
3174 | | * If end of input on non-terminal state, rollback, however we may |
3175 | | * still have epsilon like transition for counted transitions |
3176 | | * on counters, in that case don't break too early. Additionally, |
3177 | | * if we are working on a range like "AB{0,2}", where B is not present, |
3178 | | * we don't want to break. |
3179 | | */ |
3180 | 0 | len = 1; |
3181 | 0 | if ((exec->inputString[exec->index] == 0) && (exec->counts == NULL)) { |
3182 | | /* |
3183 | | * if there is a transition, we must check if |
3184 | | * atom allows minOccurs of 0 |
3185 | | */ |
3186 | 0 | if (exec->transno < exec->state->nbTrans) { |
3187 | 0 | trans = &exec->state->trans[exec->transno]; |
3188 | 0 | if (trans->to >=0) { |
3189 | 0 | atom = trans->atom; |
3190 | 0 | if (!((atom->min == 0) && (atom->max > 0))) |
3191 | 0 | goto rollback; |
3192 | 0 | } |
3193 | 0 | } else |
3194 | 0 | goto rollback; |
3195 | 0 | } |
3196 | | |
3197 | 0 | exec->transcount = 0; |
3198 | 0 | for (;exec->transno < exec->state->nbTrans;exec->transno++) { |
3199 | 0 | trans = &exec->state->trans[exec->transno]; |
3200 | 0 | if (trans->to < 0) |
3201 | 0 | continue; |
3202 | 0 | atom = trans->atom; |
3203 | 0 | ret = 0; |
3204 | 0 | deter = 1; |
3205 | 0 | if (trans->count >= 0) { |
3206 | 0 | int count; |
3207 | 0 | xmlRegCounterPtr counter; |
3208 | |
|
3209 | 0 | if (exec->counts == NULL) { |
3210 | 0 | exec->status = XML_REGEXP_INTERNAL_ERROR; |
3211 | 0 | goto error; |
3212 | 0 | } |
3213 | | /* |
3214 | | * A counted transition. |
3215 | | */ |
3216 | | |
3217 | 0 | count = exec->counts[trans->count]; |
3218 | 0 | counter = &exec->comp->counters[trans->count]; |
3219 | 0 | ret = ((count >= counter->min) && (count <= counter->max)); |
3220 | 0 | if ((ret) && (counter->min != counter->max)) |
3221 | 0 | deter = 0; |
3222 | 0 | } else if (atom == NULL) { |
3223 | 0 | fprintf(stderr, "epsilon transition left at runtime\n"); |
3224 | 0 | exec->status = XML_REGEXP_INTERNAL_ERROR; |
3225 | 0 | break; |
3226 | 0 | } else if (exec->inputString[exec->index] != 0) { |
3227 | 0 | len = 4; |
3228 | 0 | codepoint = xmlGetUTF8Char(&exec->inputString[exec->index], |
3229 | 0 | &len); |
3230 | 0 | if (codepoint < 0) { |
3231 | 0 | exec->status = XML_REGEXP_INVALID_UTF8; |
3232 | 0 | goto error; |
3233 | 0 | } |
3234 | 0 | ret = xmlRegCheckCharacter(atom, codepoint); |
3235 | 0 | if ((ret == 1) && (atom->min >= 0) && (atom->max > 0)) { |
3236 | 0 | xmlRegStatePtr to = comp->states[trans->to]; |
3237 | | |
3238 | | /* |
3239 | | * this is a multiple input sequence |
3240 | | * If there is a counter associated increment it now. |
3241 | | * do not increment if the counter is already over the |
3242 | | * maximum limit in which case get to next transition |
3243 | | */ |
3244 | 0 | if (trans->counter >= 0) { |
3245 | 0 | xmlRegCounterPtr counter; |
3246 | |
|
3247 | 0 | if ((exec->counts == NULL) || |
3248 | 0 | (exec->comp == NULL) || |
3249 | 0 | (exec->comp->counters == NULL)) { |
3250 | 0 | exec->status = XML_REGEXP_INTERNAL_ERROR; |
3251 | 0 | goto error; |
3252 | 0 | } |
3253 | 0 | counter = &exec->comp->counters[trans->counter]; |
3254 | 0 | if (exec->counts[trans->counter] >= counter->max) |
3255 | 0 | continue; /* for loop on transitions */ |
3256 | 0 | } |
3257 | | /* Save before incrementing */ |
3258 | 0 | if (exec->state->nbTrans > exec->transno + 1) { |
3259 | 0 | xmlFARegExecSave(exec); |
3260 | 0 | if (exec->status != XML_REGEXP_OK) |
3261 | 0 | goto error; |
3262 | 0 | } |
3263 | 0 | if (trans->counter >= 0) { |
3264 | 0 | exec->counts[trans->counter]++; |
3265 | 0 | } |
3266 | 0 | exec->transcount = 1; |
3267 | 0 | do { |
3268 | | /* |
3269 | | * Try to progress as much as possible on the input |
3270 | | */ |
3271 | 0 | if (exec->transcount == atom->max) { |
3272 | 0 | break; |
3273 | 0 | } |
3274 | 0 | exec->index += len; |
3275 | | /* |
3276 | | * End of input: stop here |
3277 | | */ |
3278 | 0 | if (exec->inputString[exec->index] == 0) { |
3279 | 0 | exec->index -= len; |
3280 | 0 | break; |
3281 | 0 | } |
3282 | 0 | if (exec->transcount >= atom->min) { |
3283 | 0 | int transno = exec->transno; |
3284 | 0 | xmlRegStatePtr state = exec->state; |
3285 | | |
3286 | | /* |
3287 | | * The transition is acceptable save it |
3288 | | */ |
3289 | 0 | exec->transno = -1; /* trick */ |
3290 | 0 | exec->state = to; |
3291 | 0 | xmlFARegExecSave(exec); |
3292 | 0 | if (exec->status != XML_REGEXP_OK) |
3293 | 0 | goto error; |
3294 | 0 | exec->transno = transno; |
3295 | 0 | exec->state = state; |
3296 | 0 | } |
3297 | 0 | len = 4; |
3298 | 0 | codepoint = xmlGetUTF8Char( |
3299 | 0 | &exec->inputString[exec->index], &len); |
3300 | 0 | if (codepoint < 0) { |
3301 | 0 | exec->status = XML_REGEXP_INVALID_UTF8; |
3302 | 0 | goto error; |
3303 | 0 | } |
3304 | 0 | ret = xmlRegCheckCharacter(atom, codepoint); |
3305 | 0 | exec->transcount++; |
3306 | 0 | } while (ret == 1); |
3307 | 0 | if (exec->transcount < atom->min) |
3308 | 0 | ret = 0; |
3309 | | |
3310 | | /* |
3311 | | * If the last check failed but one transition was found |
3312 | | * possible, rollback |
3313 | | */ |
3314 | 0 | if (ret < 0) |
3315 | 0 | ret = 0; |
3316 | 0 | if (ret == 0) { |
3317 | 0 | goto rollback; |
3318 | 0 | } |
3319 | 0 | if (trans->counter >= 0) { |
3320 | 0 | if (exec->counts == NULL) { |
3321 | 0 | exec->status = XML_REGEXP_INTERNAL_ERROR; |
3322 | 0 | goto error; |
3323 | 0 | } |
3324 | 0 | exec->counts[trans->counter]--; |
3325 | 0 | } |
3326 | 0 | } else if ((ret == 0) && (atom->min == 0) && (atom->max > 0)) { |
3327 | | /* |
3328 | | * we don't match on the codepoint, but minOccurs of 0 |
3329 | | * says that's ok. Setting len to 0 inhibits stepping |
3330 | | * over the codepoint. |
3331 | | */ |
3332 | 0 | exec->transcount = 1; |
3333 | 0 | len = 0; |
3334 | 0 | ret = 1; |
3335 | 0 | } |
3336 | 0 | } else if ((atom->min == 0) && (atom->max > 0)) { |
3337 | | /* another spot to match when minOccurs is 0 */ |
3338 | 0 | exec->transcount = 1; |
3339 | 0 | len = 0; |
3340 | 0 | ret = 1; |
3341 | 0 | } |
3342 | 0 | if (ret == 1) { |
3343 | 0 | if ((trans->nd == 1) || |
3344 | 0 | ((trans->count >= 0) && (deter == 0) && |
3345 | 0 | (exec->state->nbTrans > exec->transno + 1))) { |
3346 | 0 | xmlFARegExecSave(exec); |
3347 | 0 | if (exec->status != XML_REGEXP_OK) |
3348 | 0 | goto error; |
3349 | 0 | } |
3350 | 0 | if (trans->counter >= 0) { |
3351 | 0 | xmlRegCounterPtr counter; |
3352 | | |
3353 | | /* make sure we don't go over the counter maximum value */ |
3354 | 0 | if ((exec->counts == NULL) || |
3355 | 0 | (exec->comp == NULL) || |
3356 | 0 | (exec->comp->counters == NULL)) { |
3357 | 0 | exec->status = XML_REGEXP_INTERNAL_ERROR; |
3358 | 0 | goto error; |
3359 | 0 | } |
3360 | 0 | counter = &exec->comp->counters[trans->counter]; |
3361 | 0 | if (exec->counts[trans->counter] >= counter->max) |
3362 | 0 | continue; /* for loop on transitions */ |
3363 | 0 | exec->counts[trans->counter]++; |
3364 | 0 | } |
3365 | 0 | if ((trans->count >= 0) && |
3366 | 0 | (trans->count < REGEXP_ALL_COUNTER)) { |
3367 | 0 | if (exec->counts == NULL) { |
3368 | 0 | exec->status = XML_REGEXP_INTERNAL_ERROR; |
3369 | 0 | goto error; |
3370 | 0 | } |
3371 | 0 | exec->counts[trans->count] = 0; |
3372 | 0 | } |
3373 | 0 | exec->state = comp->states[trans->to]; |
3374 | 0 | exec->transno = 0; |
3375 | 0 | if (trans->atom != NULL) { |
3376 | 0 | exec->index += len; |
3377 | 0 | } |
3378 | 0 | goto progress; |
3379 | 0 | } else if (ret < 0) { |
3380 | 0 | exec->status = XML_REGEXP_INTERNAL_ERROR; |
3381 | 0 | break; |
3382 | 0 | } |
3383 | 0 | } |
3384 | 0 | if ((exec->transno != 0) || (exec->state->nbTrans == 0)) { |
3385 | 0 | rollback: |
3386 | | /* |
3387 | | * Failed to find a way out |
3388 | | */ |
3389 | 0 | exec->determinist = 0; |
3390 | 0 | xmlFARegExecRollBack(exec); |
3391 | 0 | } |
3392 | 0 | progress: |
3393 | 0 | continue; |
3394 | 0 | } |
3395 | 0 | error: |
3396 | 0 | if (exec->rollbacks != NULL) { |
3397 | 0 | if (exec->counts != NULL) { |
3398 | 0 | int i; |
3399 | |
|
3400 | 0 | for (i = 0;i < exec->maxRollbacks;i++) |
3401 | 0 | if (exec->rollbacks[i].counts != NULL) |
3402 | 0 | xmlFree(exec->rollbacks[i].counts); |
3403 | 0 | } |
3404 | 0 | xmlFree(exec->rollbacks); |
3405 | 0 | } |
3406 | 0 | if (exec->state == NULL) |
3407 | 0 | return(XML_REGEXP_INTERNAL_ERROR); |
3408 | 0 | if (exec->counts != NULL) |
3409 | 0 | xmlFree(exec->counts); |
3410 | 0 | if (exec->status == XML_REGEXP_OK) |
3411 | 0 | return(1); |
3412 | 0 | if (exec->status == XML_REGEXP_NOT_FOUND) |
3413 | 0 | return(0); |
3414 | 0 | return(exec->status); |
3415 | 0 | } |
3416 | | |
3417 | | /************************************************************************ |
3418 | | * * |
3419 | | * Progressive interface to the verifier one atom at a time * |
3420 | | * * |
3421 | | ************************************************************************/ |
3422 | | |
3423 | | /** |
3424 | | * xmlRegNewExecCtxt: |
3425 | | * @comp: a precompiled regular expression |
3426 | | * @callback: a callback function used for handling progresses in the |
3427 | | * automata matching phase |
3428 | | * @data: the context data associated to the callback in this context |
3429 | | * |
3430 | | * Build a context used for progressive evaluation of a regexp. |
3431 | | * |
3432 | | * Returns the new context |
3433 | | */ |
3434 | | xmlRegExecCtxtPtr |
3435 | 0 | xmlRegNewExecCtxt(xmlRegexpPtr comp, xmlRegExecCallbacks callback, void *data) { |
3436 | 0 | xmlRegExecCtxtPtr exec; |
3437 | |
|
3438 | 0 | if (comp == NULL) |
3439 | 0 | return(NULL); |
3440 | 0 | if ((comp->compact == NULL) && (comp->states == NULL)) |
3441 | 0 | return(NULL); |
3442 | 0 | exec = (xmlRegExecCtxtPtr) xmlMalloc(sizeof(xmlRegExecCtxt)); |
3443 | 0 | if (exec == NULL) { |
3444 | 0 | xmlRegexpErrMemory(NULL, "creating execution context"); |
3445 | 0 | return(NULL); |
3446 | 0 | } |
3447 | 0 | memset(exec, 0, sizeof(xmlRegExecCtxt)); |
3448 | 0 | exec->inputString = NULL; |
3449 | 0 | exec->index = 0; |
3450 | 0 | exec->determinist = 1; |
3451 | 0 | exec->maxRollbacks = 0; |
3452 | 0 | exec->nbRollbacks = 0; |
3453 | 0 | exec->rollbacks = NULL; |
3454 | 0 | exec->status = XML_REGEXP_OK; |
3455 | 0 | exec->comp = comp; |
3456 | 0 | if (comp->compact == NULL) |
3457 | 0 | exec->state = comp->states[0]; |
3458 | 0 | exec->transno = 0; |
3459 | 0 | exec->transcount = 0; |
3460 | 0 | exec->callback = callback; |
3461 | 0 | exec->data = data; |
3462 | 0 | if (comp->nbCounters > 0) { |
3463 | | /* |
3464 | | * For error handling, exec->counts is allocated twice the size |
3465 | | * the second half is used to store the data in case of rollback |
3466 | | */ |
3467 | 0 | exec->counts = (int *) xmlMalloc(comp->nbCounters * sizeof(int) |
3468 | 0 | * 2); |
3469 | 0 | if (exec->counts == NULL) { |
3470 | 0 | xmlRegexpErrMemory(NULL, "creating execution context"); |
3471 | 0 | xmlFree(exec); |
3472 | 0 | return(NULL); |
3473 | 0 | } |
3474 | 0 | memset(exec->counts, 0, comp->nbCounters * sizeof(int) * 2); |
3475 | 0 | exec->errCounts = &exec->counts[comp->nbCounters]; |
3476 | 0 | } else { |
3477 | 0 | exec->counts = NULL; |
3478 | 0 | exec->errCounts = NULL; |
3479 | 0 | } |
3480 | 0 | exec->inputStackMax = 0; |
3481 | 0 | exec->inputStackNr = 0; |
3482 | 0 | exec->inputStack = NULL; |
3483 | 0 | exec->errStateNo = -1; |
3484 | 0 | exec->errString = NULL; |
3485 | 0 | exec->nbPush = 0; |
3486 | 0 | return(exec); |
3487 | 0 | } |
3488 | | |
3489 | | /** |
3490 | | * xmlRegFreeExecCtxt: |
3491 | | * @exec: a regular expression evaluation context |
3492 | | * |
3493 | | * Free the structures associated to a regular expression evaluation context. |
3494 | | */ |
3495 | | void |
3496 | 0 | xmlRegFreeExecCtxt(xmlRegExecCtxtPtr exec) { |
3497 | 0 | if (exec == NULL) |
3498 | 0 | return; |
3499 | | |
3500 | 0 | if (exec->rollbacks != NULL) { |
3501 | 0 | if (exec->counts != NULL) { |
3502 | 0 | int i; |
3503 | |
|
3504 | 0 | for (i = 0;i < exec->maxRollbacks;i++) |
3505 | 0 | if (exec->rollbacks[i].counts != NULL) |
3506 | 0 | xmlFree(exec->rollbacks[i].counts); |
3507 | 0 | } |
3508 | 0 | xmlFree(exec->rollbacks); |
3509 | 0 | } |
3510 | 0 | if (exec->counts != NULL) |
3511 | 0 | xmlFree(exec->counts); |
3512 | 0 | if (exec->inputStack != NULL) { |
3513 | 0 | int i; |
3514 | |
|
3515 | 0 | for (i = 0;i < exec->inputStackNr;i++) { |
3516 | 0 | if (exec->inputStack[i].value != NULL) |
3517 | 0 | xmlFree(exec->inputStack[i].value); |
3518 | 0 | } |
3519 | 0 | xmlFree(exec->inputStack); |
3520 | 0 | } |
3521 | 0 | if (exec->errString != NULL) |
3522 | 0 | xmlFree(exec->errString); |
3523 | 0 | xmlFree(exec); |
3524 | 0 | } |
3525 | | |
3526 | | static void |
3527 | | xmlFARegExecSaveInputString(xmlRegExecCtxtPtr exec, const xmlChar *value, |
3528 | 0 | void *data) { |
3529 | 0 | if (exec->inputStackMax == 0) { |
3530 | 0 | exec->inputStackMax = 4; |
3531 | 0 | exec->inputStack = (xmlRegInputTokenPtr) |
3532 | 0 | xmlMalloc(exec->inputStackMax * sizeof(xmlRegInputToken)); |
3533 | 0 | if (exec->inputStack == NULL) { |
3534 | 0 | xmlRegexpErrMemory(NULL, "pushing input string"); |
3535 | 0 | exec->inputStackMax = 0; |
3536 | 0 | return; |
3537 | 0 | } |
3538 | 0 | } else if (exec->inputStackNr + 1 >= exec->inputStackMax) { |
3539 | 0 | xmlRegInputTokenPtr tmp; |
3540 | |
|
3541 | 0 | exec->inputStackMax *= 2; |
3542 | 0 | tmp = (xmlRegInputTokenPtr) xmlRealloc(exec->inputStack, |
3543 | 0 | exec->inputStackMax * sizeof(xmlRegInputToken)); |
3544 | 0 | if (tmp == NULL) { |
3545 | 0 | xmlRegexpErrMemory(NULL, "pushing input string"); |
3546 | 0 | exec->inputStackMax /= 2; |
3547 | 0 | return; |
3548 | 0 | } |
3549 | 0 | exec->inputStack = tmp; |
3550 | 0 | } |
3551 | 0 | exec->inputStack[exec->inputStackNr].value = xmlStrdup(value); |
3552 | 0 | exec->inputStack[exec->inputStackNr].data = data; |
3553 | 0 | exec->inputStackNr++; |
3554 | 0 | exec->inputStack[exec->inputStackNr].value = NULL; |
3555 | 0 | exec->inputStack[exec->inputStackNr].data = NULL; |
3556 | 0 | } |
3557 | | |
3558 | | /** |
3559 | | * xmlRegStrEqualWildcard: |
3560 | | * @expStr: the string to be evaluated |
3561 | | * @valStr: the validation string |
3562 | | * |
3563 | | * Checks if both strings are equal or have the same content. "*" |
3564 | | * can be used as a wildcard in @valStr; "|" is used as a separator of |
3565 | | * substrings in both @expStr and @valStr. |
3566 | | * |
3567 | | * Returns 1 if the comparison is satisfied and the number of substrings |
3568 | | * is equal, 0 otherwise. |
3569 | | */ |
3570 | | |
3571 | | static int |
3572 | 0 | xmlRegStrEqualWildcard(const xmlChar *expStr, const xmlChar *valStr) { |
3573 | 0 | if (expStr == valStr) return(1); |
3574 | 0 | if (expStr == NULL) return(0); |
3575 | 0 | if (valStr == NULL) return(0); |
3576 | 0 | do { |
3577 | | /* |
3578 | | * Eval if we have a wildcard for the current item. |
3579 | | */ |
3580 | 0 | if (*expStr != *valStr) { |
3581 | | /* if one of them starts with a wildcard make valStr be it */ |
3582 | 0 | if (*valStr == '*') { |
3583 | 0 | const xmlChar *tmp; |
3584 | |
|
3585 | 0 | tmp = valStr; |
3586 | 0 | valStr = expStr; |
3587 | 0 | expStr = tmp; |
3588 | 0 | } |
3589 | 0 | if ((*valStr != 0) && (*expStr != 0) && (*expStr++ == '*')) { |
3590 | 0 | do { |
3591 | 0 | if (*valStr == XML_REG_STRING_SEPARATOR) |
3592 | 0 | break; |
3593 | 0 | valStr++; |
3594 | 0 | } while (*valStr != 0); |
3595 | 0 | continue; |
3596 | 0 | } else |
3597 | 0 | return(0); |
3598 | 0 | } |
3599 | 0 | expStr++; |
3600 | 0 | valStr++; |
3601 | 0 | } while (*valStr != 0); |
3602 | 0 | if (*expStr != 0) |
3603 | 0 | return (0); |
3604 | 0 | else |
3605 | 0 | return (1); |
3606 | 0 | } |
3607 | | |
3608 | | /** |
3609 | | * xmlRegCompactPushString: |
3610 | | * @exec: a regexp execution context |
3611 | | * @comp: the precompiled exec with a compact table |
3612 | | * @value: a string token input |
3613 | | * @data: data associated to the token to reuse in callbacks |
3614 | | * |
3615 | | * Push one input token in the execution context |
3616 | | * |
3617 | | * Returns: 1 if the regexp reached a final state, 0 if non-final, and |
3618 | | * a negative value in case of error. |
3619 | | */ |
3620 | | static int |
3621 | | xmlRegCompactPushString(xmlRegExecCtxtPtr exec, |
3622 | | xmlRegexpPtr comp, |
3623 | | const xmlChar *value, |
3624 | 0 | void *data) { |
3625 | 0 | int state = exec->index; |
3626 | 0 | int i, target; |
3627 | |
|
3628 | 0 | if ((comp == NULL) || (comp->compact == NULL) || (comp->stringMap == NULL)) |
3629 | 0 | return(-1); |
3630 | | |
3631 | 0 | if (value == NULL) { |
3632 | | /* |
3633 | | * are we at a final state ? |
3634 | | */ |
3635 | 0 | if (comp->compact[state * (comp->nbstrings + 1)] == |
3636 | 0 | XML_REGEXP_FINAL_STATE) |
3637 | 0 | return(1); |
3638 | 0 | return(0); |
3639 | 0 | } |
3640 | | |
3641 | | /* |
3642 | | * Examine all outside transitions from current state |
3643 | | */ |
3644 | 0 | for (i = 0;i < comp->nbstrings;i++) { |
3645 | 0 | target = comp->compact[state * (comp->nbstrings + 1) + i + 1]; |
3646 | 0 | if ((target > 0) && (target <= comp->nbstates)) { |
3647 | 0 | target--; /* to avoid 0 */ |
3648 | 0 | if (xmlRegStrEqualWildcard(comp->stringMap[i], value)) { |
3649 | 0 | exec->index = target; |
3650 | 0 | if ((exec->callback != NULL) && (comp->transdata != NULL)) { |
3651 | 0 | exec->callback(exec->data, value, |
3652 | 0 | comp->transdata[state * comp->nbstrings + i], data); |
3653 | 0 | } |
3654 | 0 | if (comp->compact[target * (comp->nbstrings + 1)] == |
3655 | 0 | XML_REGEXP_SINK_STATE) |
3656 | 0 | goto error; |
3657 | | |
3658 | 0 | if (comp->compact[target * (comp->nbstrings + 1)] == |
3659 | 0 | XML_REGEXP_FINAL_STATE) |
3660 | 0 | return(1); |
3661 | 0 | return(0); |
3662 | 0 | } |
3663 | 0 | } |
3664 | 0 | } |
3665 | | /* |
3666 | | * Failed to find an exit transition out from current state for the |
3667 | | * current token |
3668 | | */ |
3669 | 0 | error: |
3670 | 0 | if (exec->errString != NULL) |
3671 | 0 | xmlFree(exec->errString); |
3672 | 0 | exec->errString = xmlStrdup(value); |
3673 | 0 | exec->errStateNo = state; |
3674 | 0 | exec->status = XML_REGEXP_NOT_FOUND; |
3675 | 0 | return(XML_REGEXP_NOT_FOUND); |
3676 | 0 | } |
3677 | | |
3678 | | /** |
3679 | | * xmlRegExecPushStringInternal: |
3680 | | * @exec: a regexp execution context or NULL to indicate the end |
3681 | | * @value: a string token input |
3682 | | * @data: data associated to the token to reuse in callbacks |
3683 | | * @compound: value was assembled from 2 strings |
3684 | | * |
3685 | | * Push one input token in the execution context |
3686 | | * |
3687 | | * Returns: 1 if the regexp reached a final state, 0 if non-final, and |
3688 | | * a negative value in case of error. |
3689 | | */ |
3690 | | static int |
3691 | | xmlRegExecPushStringInternal(xmlRegExecCtxtPtr exec, const xmlChar *value, |
3692 | 0 | void *data, int compound) { |
3693 | 0 | xmlRegTransPtr trans; |
3694 | 0 | xmlRegAtomPtr atom; |
3695 | 0 | int ret; |
3696 | 0 | int final = 0; |
3697 | 0 | int progress = 1; |
3698 | |
|
3699 | 0 | if (exec == NULL) |
3700 | 0 | return(-1); |
3701 | 0 | if (exec->comp == NULL) |
3702 | 0 | return(-1); |
3703 | 0 | if (exec->status != XML_REGEXP_OK) |
3704 | 0 | return(exec->status); |
3705 | | |
3706 | 0 | if (exec->comp->compact != NULL) |
3707 | 0 | return(xmlRegCompactPushString(exec, exec->comp, value, data)); |
3708 | | |
3709 | 0 | if (value == NULL) { |
3710 | 0 | if (exec->state->type == XML_REGEXP_FINAL_STATE) |
3711 | 0 | return(1); |
3712 | 0 | final = 1; |
3713 | 0 | } |
3714 | | |
3715 | | /* |
3716 | | * If we have an active rollback stack push the new value there |
3717 | | * and get back to where we were left |
3718 | | */ |
3719 | 0 | if ((value != NULL) && (exec->inputStackNr > 0)) { |
3720 | 0 | xmlFARegExecSaveInputString(exec, value, data); |
3721 | 0 | value = exec->inputStack[exec->index].value; |
3722 | 0 | data = exec->inputStack[exec->index].data; |
3723 | 0 | } |
3724 | |
|
3725 | 0 | while ((exec->status == XML_REGEXP_OK) && |
3726 | 0 | ((value != NULL) || |
3727 | 0 | ((final == 1) && |
3728 | 0 | (exec->state->type != XML_REGEXP_FINAL_STATE)))) { |
3729 | | |
3730 | | /* |
3731 | | * End of input on non-terminal state, rollback, however we may |
3732 | | * still have epsilon like transition for counted transitions |
3733 | | * on counters, in that case don't break too early. |
3734 | | */ |
3735 | 0 | if ((value == NULL) && (exec->counts == NULL)) |
3736 | 0 | goto rollback; |
3737 | | |
3738 | 0 | exec->transcount = 0; |
3739 | 0 | for (;exec->transno < exec->state->nbTrans;exec->transno++) { |
3740 | 0 | trans = &exec->state->trans[exec->transno]; |
3741 | 0 | if (trans->to < 0) |
3742 | 0 | continue; |
3743 | 0 | atom = trans->atom; |
3744 | 0 | ret = 0; |
3745 | 0 | if (trans->count == REGEXP_ALL_LAX_COUNTER) { |
3746 | 0 | int i; |
3747 | 0 | int count; |
3748 | 0 | xmlRegTransPtr t; |
3749 | 0 | xmlRegCounterPtr counter; |
3750 | |
|
3751 | 0 | ret = 0; |
3752 | | |
3753 | | /* |
3754 | | * Check all counted transitions from the current state |
3755 | | */ |
3756 | 0 | if ((value == NULL) && (final)) { |
3757 | 0 | ret = 1; |
3758 | 0 | } else if (value != NULL) { |
3759 | 0 | for (i = 0;i < exec->state->nbTrans;i++) { |
3760 | 0 | t = &exec->state->trans[i]; |
3761 | 0 | if ((t->counter < 0) || (t == trans)) |
3762 | 0 | continue; |
3763 | 0 | counter = &exec->comp->counters[t->counter]; |
3764 | 0 | count = exec->counts[t->counter]; |
3765 | 0 | if ((count < counter->max) && |
3766 | 0 | (t->atom != NULL) && |
3767 | 0 | (xmlStrEqual(value, t->atom->valuep))) { |
3768 | 0 | ret = 0; |
3769 | 0 | break; |
3770 | 0 | } |
3771 | 0 | if ((count >= counter->min) && |
3772 | 0 | (count < counter->max) && |
3773 | 0 | (t->atom != NULL) && |
3774 | 0 | (xmlStrEqual(value, t->atom->valuep))) { |
3775 | 0 | ret = 1; |
3776 | 0 | break; |
3777 | 0 | } |
3778 | 0 | } |
3779 | 0 | } |
3780 | 0 | } else if (trans->count == REGEXP_ALL_COUNTER) { |
3781 | 0 | int i; |
3782 | 0 | int count; |
3783 | 0 | xmlRegTransPtr t; |
3784 | 0 | xmlRegCounterPtr counter; |
3785 | |
|
3786 | 0 | ret = 1; |
3787 | | |
3788 | | /* |
3789 | | * Check all counted transitions from the current state |
3790 | | */ |
3791 | 0 | for (i = 0;i < exec->state->nbTrans;i++) { |
3792 | 0 | t = &exec->state->trans[i]; |
3793 | 0 | if ((t->counter < 0) || (t == trans)) |
3794 | 0 | continue; |
3795 | 0 | counter = &exec->comp->counters[t->counter]; |
3796 | 0 | count = exec->counts[t->counter]; |
3797 | 0 | if ((count < counter->min) || (count > counter->max)) { |
3798 | 0 | ret = 0; |
3799 | 0 | break; |
3800 | 0 | } |
3801 | 0 | } |
3802 | 0 | } else if (trans->count >= 0) { |
3803 | 0 | int count; |
3804 | 0 | xmlRegCounterPtr counter; |
3805 | | |
3806 | | /* |
3807 | | * A counted transition. |
3808 | | */ |
3809 | |
|
3810 | 0 | count = exec->counts[trans->count]; |
3811 | 0 | counter = &exec->comp->counters[trans->count]; |
3812 | 0 | ret = ((count >= counter->min) && (count <= counter->max)); |
3813 | 0 | } else if (atom == NULL) { |
3814 | 0 | fprintf(stderr, "epsilon transition left at runtime\n"); |
3815 | 0 | exec->status = XML_REGEXP_INTERNAL_ERROR; |
3816 | 0 | break; |
3817 | 0 | } else if (value != NULL) { |
3818 | 0 | ret = xmlRegStrEqualWildcard(atom->valuep, value); |
3819 | 0 | if (atom->neg) { |
3820 | 0 | ret = !ret; |
3821 | 0 | if (!compound) |
3822 | 0 | ret = 0; |
3823 | 0 | } |
3824 | 0 | if ((ret == 1) && (trans->counter >= 0)) { |
3825 | 0 | xmlRegCounterPtr counter; |
3826 | 0 | int count; |
3827 | |
|
3828 | 0 | count = exec->counts[trans->counter]; |
3829 | 0 | counter = &exec->comp->counters[trans->counter]; |
3830 | 0 | if (count >= counter->max) |
3831 | 0 | ret = 0; |
3832 | 0 | } |
3833 | |
|
3834 | 0 | if ((ret == 1) && (atom->min > 0) && (atom->max > 0)) { |
3835 | 0 | xmlRegStatePtr to = exec->comp->states[trans->to]; |
3836 | | |
3837 | | /* |
3838 | | * this is a multiple input sequence |
3839 | | */ |
3840 | 0 | if (exec->state->nbTrans > exec->transno + 1) { |
3841 | 0 | if (exec->inputStackNr <= 0) { |
3842 | 0 | xmlFARegExecSaveInputString(exec, value, data); |
3843 | 0 | } |
3844 | 0 | xmlFARegExecSave(exec); |
3845 | 0 | } |
3846 | 0 | exec->transcount = 1; |
3847 | 0 | do { |
3848 | | /* |
3849 | | * Try to progress as much as possible on the input |
3850 | | */ |
3851 | 0 | if (exec->transcount == atom->max) { |
3852 | 0 | break; |
3853 | 0 | } |
3854 | 0 | exec->index++; |
3855 | 0 | value = exec->inputStack[exec->index].value; |
3856 | 0 | data = exec->inputStack[exec->index].data; |
3857 | | |
3858 | | /* |
3859 | | * End of input: stop here |
3860 | | */ |
3861 | 0 | if (value == NULL) { |
3862 | 0 | exec->index --; |
3863 | 0 | break; |
3864 | 0 | } |
3865 | 0 | if (exec->transcount >= atom->min) { |
3866 | 0 | int transno = exec->transno; |
3867 | 0 | xmlRegStatePtr state = exec->state; |
3868 | | |
3869 | | /* |
3870 | | * The transition is acceptable save it |
3871 | | */ |
3872 | 0 | exec->transno = -1; /* trick */ |
3873 | 0 | exec->state = to; |
3874 | 0 | if (exec->inputStackNr <= 0) { |
3875 | 0 | xmlFARegExecSaveInputString(exec, value, data); |
3876 | 0 | } |
3877 | 0 | xmlFARegExecSave(exec); |
3878 | 0 | exec->transno = transno; |
3879 | 0 | exec->state = state; |
3880 | 0 | } |
3881 | 0 | ret = xmlStrEqual(value, atom->valuep); |
3882 | 0 | exec->transcount++; |
3883 | 0 | } while (ret == 1); |
3884 | 0 | if (exec->transcount < atom->min) |
3885 | 0 | ret = 0; |
3886 | | |
3887 | | /* |
3888 | | * If the last check failed but one transition was found |
3889 | | * possible, rollback |
3890 | | */ |
3891 | 0 | if (ret < 0) |
3892 | 0 | ret = 0; |
3893 | 0 | if (ret == 0) { |
3894 | 0 | goto rollback; |
3895 | 0 | } |
3896 | 0 | } |
3897 | 0 | } |
3898 | 0 | if (ret == 1) { |
3899 | 0 | if ((exec->callback != NULL) && (atom != NULL) && |
3900 | 0 | (data != NULL)) { |
3901 | 0 | exec->callback(exec->data, atom->valuep, |
3902 | 0 | atom->data, data); |
3903 | 0 | } |
3904 | 0 | if (exec->state->nbTrans > exec->transno + 1) { |
3905 | 0 | if (exec->inputStackNr <= 0) { |
3906 | 0 | xmlFARegExecSaveInputString(exec, value, data); |
3907 | 0 | } |
3908 | 0 | xmlFARegExecSave(exec); |
3909 | 0 | } |
3910 | 0 | if (trans->counter >= 0) { |
3911 | 0 | exec->counts[trans->counter]++; |
3912 | 0 | } |
3913 | 0 | if ((trans->count >= 0) && |
3914 | 0 | (trans->count < REGEXP_ALL_COUNTER)) { |
3915 | 0 | exec->counts[trans->count] = 0; |
3916 | 0 | } |
3917 | 0 | if ((exec->comp->states[trans->to] != NULL) && |
3918 | 0 | (exec->comp->states[trans->to]->type == |
3919 | 0 | XML_REGEXP_SINK_STATE)) { |
3920 | | /* |
3921 | | * entering a sink state, save the current state as error |
3922 | | * state. |
3923 | | */ |
3924 | 0 | if (exec->errString != NULL) |
3925 | 0 | xmlFree(exec->errString); |
3926 | 0 | exec->errString = xmlStrdup(value); |
3927 | 0 | exec->errState = exec->state; |
3928 | 0 | memcpy(exec->errCounts, exec->counts, |
3929 | 0 | exec->comp->nbCounters * sizeof(int)); |
3930 | 0 | } |
3931 | 0 | exec->state = exec->comp->states[trans->to]; |
3932 | 0 | exec->transno = 0; |
3933 | 0 | if (trans->atom != NULL) { |
3934 | 0 | if (exec->inputStack != NULL) { |
3935 | 0 | exec->index++; |
3936 | 0 | if (exec->index < exec->inputStackNr) { |
3937 | 0 | value = exec->inputStack[exec->index].value; |
3938 | 0 | data = exec->inputStack[exec->index].data; |
3939 | 0 | } else { |
3940 | 0 | value = NULL; |
3941 | 0 | data = NULL; |
3942 | 0 | } |
3943 | 0 | } else { |
3944 | 0 | value = NULL; |
3945 | 0 | data = NULL; |
3946 | 0 | } |
3947 | 0 | } |
3948 | 0 | goto progress; |
3949 | 0 | } else if (ret < 0) { |
3950 | 0 | exec->status = XML_REGEXP_INTERNAL_ERROR; |
3951 | 0 | break; |
3952 | 0 | } |
3953 | 0 | } |
3954 | 0 | if ((exec->transno != 0) || (exec->state->nbTrans == 0)) { |
3955 | 0 | rollback: |
3956 | | /* |
3957 | | * if we didn't yet rollback on the current input |
3958 | | * store the current state as the error state. |
3959 | | */ |
3960 | 0 | if ((progress) && (exec->state != NULL) && |
3961 | 0 | (exec->state->type != XML_REGEXP_SINK_STATE)) { |
3962 | 0 | progress = 0; |
3963 | 0 | if (exec->errString != NULL) |
3964 | 0 | xmlFree(exec->errString); |
3965 | 0 | exec->errString = xmlStrdup(value); |
3966 | 0 | exec->errState = exec->state; |
3967 | 0 | if (exec->comp->nbCounters) |
3968 | 0 | memcpy(exec->errCounts, exec->counts, |
3969 | 0 | exec->comp->nbCounters * sizeof(int)); |
3970 | 0 | } |
3971 | | |
3972 | | /* |
3973 | | * Failed to find a way out |
3974 | | */ |
3975 | 0 | exec->determinist = 0; |
3976 | 0 | xmlFARegExecRollBack(exec); |
3977 | 0 | if ((exec->inputStack != NULL ) && |
3978 | 0 | (exec->status == XML_REGEXP_OK)) { |
3979 | 0 | value = exec->inputStack[exec->index].value; |
3980 | 0 | data = exec->inputStack[exec->index].data; |
3981 | 0 | } |
3982 | 0 | } |
3983 | 0 | continue; |
3984 | 0 | progress: |
3985 | 0 | progress = 1; |
3986 | 0 | continue; |
3987 | 0 | } |
3988 | 0 | if (exec->status == XML_REGEXP_OK) { |
3989 | 0 | return(exec->state->type == XML_REGEXP_FINAL_STATE); |
3990 | 0 | } |
3991 | 0 | return(exec->status); |
3992 | 0 | } |
3993 | | |
3994 | | /** |
3995 | | * xmlRegExecPushString: |
3996 | | * @exec: a regexp execution context or NULL to indicate the end |
3997 | | * @value: a string token input |
3998 | | * @data: data associated to the token to reuse in callbacks |
3999 | | * |
4000 | | * Push one input token in the execution context |
4001 | | * |
4002 | | * Returns: 1 if the regexp reached a final state, 0 if non-final, and |
4003 | | * a negative value in case of error. |
4004 | | */ |
4005 | | int |
4006 | | xmlRegExecPushString(xmlRegExecCtxtPtr exec, const xmlChar *value, |
4007 | 0 | void *data) { |
4008 | 0 | return(xmlRegExecPushStringInternal(exec, value, data, 0)); |
4009 | 0 | } |
4010 | | |
4011 | | /** |
4012 | | * xmlRegExecPushString2: |
4013 | | * @exec: a regexp execution context or NULL to indicate the end |
4014 | | * @value: the first string token input |
4015 | | * @value2: the second string token input |
4016 | | * @data: data associated to the token to reuse in callbacks |
4017 | | * |
4018 | | * Push one input token in the execution context |
4019 | | * |
4020 | | * Returns: 1 if the regexp reached a final state, 0 if non-final, and |
4021 | | * a negative value in case of error. |
4022 | | */ |
4023 | | int |
4024 | | xmlRegExecPushString2(xmlRegExecCtxtPtr exec, const xmlChar *value, |
4025 | 0 | const xmlChar *value2, void *data) { |
4026 | 0 | xmlChar buf[150]; |
4027 | 0 | int lenn, lenp, ret; |
4028 | 0 | xmlChar *str; |
4029 | |
|
4030 | 0 | if (exec == NULL) |
4031 | 0 | return(-1); |
4032 | 0 | if (exec->comp == NULL) |
4033 | 0 | return(-1); |
4034 | 0 | if (exec->status != XML_REGEXP_OK) |
4035 | 0 | return(exec->status); |
4036 | | |
4037 | 0 | if (value2 == NULL) |
4038 | 0 | return(xmlRegExecPushString(exec, value, data)); |
4039 | | |
4040 | 0 | lenn = strlen((char *) value2); |
4041 | 0 | lenp = strlen((char *) value); |
4042 | |
|
4043 | 0 | if (150 < lenn + lenp + 2) { |
4044 | 0 | str = (xmlChar *) xmlMallocAtomic(lenn + lenp + 2); |
4045 | 0 | if (str == NULL) { |
4046 | 0 | exec->status = XML_REGEXP_OUT_OF_MEMORY; |
4047 | 0 | return(-1); |
4048 | 0 | } |
4049 | 0 | } else { |
4050 | 0 | str = buf; |
4051 | 0 | } |
4052 | 0 | memcpy(&str[0], value, lenp); |
4053 | 0 | str[lenp] = XML_REG_STRING_SEPARATOR; |
4054 | 0 | memcpy(&str[lenp + 1], value2, lenn); |
4055 | 0 | str[lenn + lenp + 1] = 0; |
4056 | |
|
4057 | 0 | if (exec->comp->compact != NULL) |
4058 | 0 | ret = xmlRegCompactPushString(exec, exec->comp, str, data); |
4059 | 0 | else |
4060 | 0 | ret = xmlRegExecPushStringInternal(exec, str, data, 1); |
4061 | |
|
4062 | 0 | if (str != buf) |
4063 | 0 | xmlFree(str); |
4064 | 0 | return(ret); |
4065 | 0 | } |
4066 | | |
4067 | | /** |
4068 | | * xmlRegExecGetValues: |
4069 | | * @exec: a regexp execution context |
4070 | | * @err: error extraction or normal one |
4071 | | * @nbval: pointer to the number of accepted values IN/OUT |
4072 | | * @nbneg: return number of negative transitions |
4073 | | * @values: pointer to the array of acceptable values |
4074 | | * @terminal: return value if this was a terminal state |
4075 | | * |
4076 | | * Extract information from the regexp execution, internal routine to |
4077 | | * implement xmlRegExecNextValues() and xmlRegExecErrInfo() |
4078 | | * |
4079 | | * Returns: 0 in case of success or -1 in case of error. |
4080 | | */ |
4081 | | static int |
4082 | | xmlRegExecGetValues(xmlRegExecCtxtPtr exec, int err, |
4083 | | int *nbval, int *nbneg, |
4084 | 0 | xmlChar **values, int *terminal) { |
4085 | 0 | int maxval; |
4086 | 0 | int nb = 0; |
4087 | |
|
4088 | 0 | if ((exec == NULL) || (nbval == NULL) || (nbneg == NULL) || |
4089 | 0 | (values == NULL) || (*nbval <= 0)) |
4090 | 0 | return(-1); |
4091 | | |
4092 | 0 | maxval = *nbval; |
4093 | 0 | *nbval = 0; |
4094 | 0 | *nbneg = 0; |
4095 | 0 | if ((exec->comp != NULL) && (exec->comp->compact != NULL)) { |
4096 | 0 | xmlRegexpPtr comp; |
4097 | 0 | int target, i, state; |
4098 | |
|
4099 | 0 | comp = exec->comp; |
4100 | |
|
4101 | 0 | if (err) { |
4102 | 0 | if (exec->errStateNo == -1) return(-1); |
4103 | 0 | state = exec->errStateNo; |
4104 | 0 | } else { |
4105 | 0 | state = exec->index; |
4106 | 0 | } |
4107 | 0 | if (terminal != NULL) { |
4108 | 0 | if (comp->compact[state * (comp->nbstrings + 1)] == |
4109 | 0 | XML_REGEXP_FINAL_STATE) |
4110 | 0 | *terminal = 1; |
4111 | 0 | else |
4112 | 0 | *terminal = 0; |
4113 | 0 | } |
4114 | 0 | for (i = 0;(i < comp->nbstrings) && (nb < maxval);i++) { |
4115 | 0 | target = comp->compact[state * (comp->nbstrings + 1) + i + 1]; |
4116 | 0 | if ((target > 0) && (target <= comp->nbstates) && |
4117 | 0 | (comp->compact[(target - 1) * (comp->nbstrings + 1)] != |
4118 | 0 | XML_REGEXP_SINK_STATE)) { |
4119 | 0 | values[nb++] = comp->stringMap[i]; |
4120 | 0 | (*nbval)++; |
4121 | 0 | } |
4122 | 0 | } |
4123 | 0 | for (i = 0;(i < comp->nbstrings) && (nb < maxval);i++) { |
4124 | 0 | target = comp->compact[state * (comp->nbstrings + 1) + i + 1]; |
4125 | 0 | if ((target > 0) && (target <= comp->nbstates) && |
4126 | 0 | (comp->compact[(target - 1) * (comp->nbstrings + 1)] == |
4127 | 0 | XML_REGEXP_SINK_STATE)) { |
4128 | 0 | values[nb++] = comp->stringMap[i]; |
4129 | 0 | (*nbneg)++; |
4130 | 0 | } |
4131 | 0 | } |
4132 | 0 | } else { |
4133 | 0 | int transno; |
4134 | 0 | xmlRegTransPtr trans; |
4135 | 0 | xmlRegAtomPtr atom; |
4136 | 0 | xmlRegStatePtr state; |
4137 | |
|
4138 | 0 | if (terminal != NULL) { |
4139 | 0 | if (exec->state->type == XML_REGEXP_FINAL_STATE) |
4140 | 0 | *terminal = 1; |
4141 | 0 | else |
4142 | 0 | *terminal = 0; |
4143 | 0 | } |
4144 | |
|
4145 | 0 | if (err) { |
4146 | 0 | if (exec->errState == NULL) return(-1); |
4147 | 0 | state = exec->errState; |
4148 | 0 | } else { |
4149 | 0 | if (exec->state == NULL) return(-1); |
4150 | 0 | state = exec->state; |
4151 | 0 | } |
4152 | 0 | for (transno = 0; |
4153 | 0 | (transno < state->nbTrans) && (nb < maxval); |
4154 | 0 | transno++) { |
4155 | 0 | trans = &state->trans[transno]; |
4156 | 0 | if (trans->to < 0) |
4157 | 0 | continue; |
4158 | 0 | atom = trans->atom; |
4159 | 0 | if ((atom == NULL) || (atom->valuep == NULL)) |
4160 | 0 | continue; |
4161 | 0 | if (trans->count == REGEXP_ALL_LAX_COUNTER) { |
4162 | | /* this should not be reached but ... */ |
4163 | 0 | TODO; |
4164 | 0 | } else if (trans->count == REGEXP_ALL_COUNTER) { |
4165 | | /* this should not be reached but ... */ |
4166 | 0 | TODO; |
4167 | 0 | } else if (trans->counter >= 0) { |
4168 | 0 | xmlRegCounterPtr counter = NULL; |
4169 | 0 | int count; |
4170 | |
|
4171 | 0 | if (err) |
4172 | 0 | count = exec->errCounts[trans->counter]; |
4173 | 0 | else |
4174 | 0 | count = exec->counts[trans->counter]; |
4175 | 0 | if (exec->comp != NULL) |
4176 | 0 | counter = &exec->comp->counters[trans->counter]; |
4177 | 0 | if ((counter == NULL) || (count < counter->max)) { |
4178 | 0 | if (atom->neg) |
4179 | 0 | values[nb++] = (xmlChar *) atom->valuep2; |
4180 | 0 | else |
4181 | 0 | values[nb++] = (xmlChar *) atom->valuep; |
4182 | 0 | (*nbval)++; |
4183 | 0 | } |
4184 | 0 | } else { |
4185 | 0 | if ((exec->comp != NULL) && (exec->comp->states[trans->to] != NULL) && |
4186 | 0 | (exec->comp->states[trans->to]->type != |
4187 | 0 | XML_REGEXP_SINK_STATE)) { |
4188 | 0 | if (atom->neg) |
4189 | 0 | values[nb++] = (xmlChar *) atom->valuep2; |
4190 | 0 | else |
4191 | 0 | values[nb++] = (xmlChar *) atom->valuep; |
4192 | 0 | (*nbval)++; |
4193 | 0 | } |
4194 | 0 | } |
4195 | 0 | } |
4196 | 0 | for (transno = 0; |
4197 | 0 | (transno < state->nbTrans) && (nb < maxval); |
4198 | 0 | transno++) { |
4199 | 0 | trans = &state->trans[transno]; |
4200 | 0 | if (trans->to < 0) |
4201 | 0 | continue; |
4202 | 0 | atom = trans->atom; |
4203 | 0 | if ((atom == NULL) || (atom->valuep == NULL)) |
4204 | 0 | continue; |
4205 | 0 | if (trans->count == REGEXP_ALL_LAX_COUNTER) { |
4206 | 0 | continue; |
4207 | 0 | } else if (trans->count == REGEXP_ALL_COUNTER) { |
4208 | 0 | continue; |
4209 | 0 | } else if (trans->counter >= 0) { |
4210 | 0 | continue; |
4211 | 0 | } else { |
4212 | 0 | if ((exec->comp->states[trans->to] != NULL) && |
4213 | 0 | (exec->comp->states[trans->to]->type == |
4214 | 0 | XML_REGEXP_SINK_STATE)) { |
4215 | 0 | if (atom->neg) |
4216 | 0 | values[nb++] = (xmlChar *) atom->valuep2; |
4217 | 0 | else |
4218 | 0 | values[nb++] = (xmlChar *) atom->valuep; |
4219 | 0 | (*nbneg)++; |
4220 | 0 | } |
4221 | 0 | } |
4222 | 0 | } |
4223 | 0 | } |
4224 | 0 | return(0); |
4225 | 0 | } |
4226 | | |
4227 | | /** |
4228 | | * xmlRegExecNextValues: |
4229 | | * @exec: a regexp execution context |
4230 | | * @nbval: pointer to the number of accepted values IN/OUT |
4231 | | * @nbneg: return number of negative transitions |
4232 | | * @values: pointer to the array of acceptable values |
4233 | | * @terminal: return value if this was a terminal state |
4234 | | * |
4235 | | * Extract information from the regexp execution, |
4236 | | * the parameter @values must point to an array of @nbval string pointers |
4237 | | * on return nbval will contain the number of possible strings in that |
4238 | | * state and the @values array will be updated with them. The string values |
4239 | | * returned will be freed with the @exec context and don't need to be |
4240 | | * deallocated. |
4241 | | * |
4242 | | * Returns: 0 in case of success or -1 in case of error. |
4243 | | */ |
4244 | | int |
4245 | | xmlRegExecNextValues(xmlRegExecCtxtPtr exec, int *nbval, int *nbneg, |
4246 | 0 | xmlChar **values, int *terminal) { |
4247 | 0 | return(xmlRegExecGetValues(exec, 0, nbval, nbneg, values, terminal)); |
4248 | 0 | } |
4249 | | |
4250 | | /** |
4251 | | * xmlRegExecErrInfo: |
4252 | | * @exec: a regexp execution context generating an error |
4253 | | * @string: return value for the error string |
4254 | | * @nbval: pointer to the number of accepted values IN/OUT |
4255 | | * @nbneg: return number of negative transitions |
4256 | | * @values: pointer to the array of acceptable values |
4257 | | * @terminal: return value if this was a terminal state |
4258 | | * |
4259 | | * Extract error information from the regexp execution, the parameter |
4260 | | * @string will be updated with the value pushed and not accepted, |
4261 | | * the parameter @values must point to an array of @nbval string pointers |
4262 | | * on return nbval will contain the number of possible strings in that |
4263 | | * state and the @values array will be updated with them. The string values |
4264 | | * returned will be freed with the @exec context and don't need to be |
4265 | | * deallocated. |
4266 | | * |
4267 | | * Returns: 0 in case of success or -1 in case of error. |
4268 | | */ |
4269 | | int |
4270 | | xmlRegExecErrInfo(xmlRegExecCtxtPtr exec, const xmlChar **string, |
4271 | 0 | int *nbval, int *nbneg, xmlChar **values, int *terminal) { |
4272 | 0 | if (exec == NULL) |
4273 | 0 | return(-1); |
4274 | 0 | if (string != NULL) { |
4275 | 0 | if (exec->status != XML_REGEXP_OK) |
4276 | 0 | *string = exec->errString; |
4277 | 0 | else |
4278 | 0 | *string = NULL; |
4279 | 0 | } |
4280 | 0 | return(xmlRegExecGetValues(exec, 1, nbval, nbneg, values, terminal)); |
4281 | 0 | } |
4282 | | |
4283 | | #if 0 |
4284 | | static int |
4285 | | xmlRegExecPushChar(xmlRegExecCtxtPtr exec, int UCS) { |
4286 | | xmlRegTransPtr trans; |
4287 | | xmlRegAtomPtr atom; |
4288 | | int ret; |
4289 | | int codepoint, len; |
4290 | | |
4291 | | if (exec == NULL) |
4292 | | return(-1); |
4293 | | if (exec->status != XML_REGEXP_OK) |
4294 | | return(exec->status); |
4295 | | |
4296 | | while ((exec->status == XML_REGEXP_OK) && |
4297 | | ((exec->inputString[exec->index] != 0) || |
4298 | | (exec->state->type != XML_REGEXP_FINAL_STATE))) { |
4299 | | |
4300 | | /* |
4301 | | * End of input on non-terminal state, rollback, however we may |
4302 | | * still have epsilon like transition for counted transitions |
4303 | | * on counters, in that case don't break too early. |
4304 | | */ |
4305 | | if ((exec->inputString[exec->index] == 0) && (exec->counts == NULL)) |
4306 | | goto rollback; |
4307 | | |
4308 | | exec->transcount = 0; |
4309 | | for (;exec->transno < exec->state->nbTrans;exec->transno++) { |
4310 | | trans = &exec->state->trans[exec->transno]; |
4311 | | if (trans->to < 0) |
4312 | | continue; |
4313 | | atom = trans->atom; |
4314 | | ret = 0; |
4315 | | if (trans->count >= 0) { |
4316 | | int count; |
4317 | | xmlRegCounterPtr counter; |
4318 | | |
4319 | | /* |
4320 | | * A counted transition. |
4321 | | */ |
4322 | | |
4323 | | count = exec->counts[trans->count]; |
4324 | | counter = &exec->comp->counters[trans->count]; |
4325 | | ret = ((count >= counter->min) && (count <= counter->max)); |
4326 | | } else if (atom == NULL) { |
4327 | | fprintf(stderr, "epsilon transition left at runtime\n"); |
4328 | | exec->status = XML_REGEXP_INTERNAL_ERROR; |
4329 | | break; |
4330 | | } else if (exec->inputString[exec->index] != 0) { |
4331 | | codepoint = CUR_SCHAR(&(exec->inputString[exec->index]), len); |
4332 | | ret = xmlRegCheckCharacter(atom, codepoint); |
4333 | | if ((ret == 1) && (atom->min > 0) && (atom->max > 0)) { |
4334 | | xmlRegStatePtr to = exec->comp->states[trans->to]; |
4335 | | |
4336 | | /* |
4337 | | * this is a multiple input sequence |
4338 | | */ |
4339 | | if (exec->state->nbTrans > exec->transno + 1) { |
4340 | | xmlFARegExecSave(exec); |
4341 | | } |
4342 | | exec->transcount = 1; |
4343 | | do { |
4344 | | /* |
4345 | | * Try to progress as much as possible on the input |
4346 | | */ |
4347 | | if (exec->transcount == atom->max) { |
4348 | | break; |
4349 | | } |
4350 | | exec->index += len; |
4351 | | /* |
4352 | | * End of input: stop here |
4353 | | */ |
4354 | | if (exec->inputString[exec->index] == 0) { |
4355 | | exec->index -= len; |
4356 | | break; |
4357 | | } |
4358 | | if (exec->transcount >= atom->min) { |
4359 | | int transno = exec->transno; |
4360 | | xmlRegStatePtr state = exec->state; |
4361 | | |
4362 | | /* |
4363 | | * The transition is acceptable save it |
4364 | | */ |
4365 | | exec->transno = -1; /* trick */ |
4366 | | exec->state = to; |
4367 | | xmlFARegExecSave(exec); |
4368 | | exec->transno = transno; |
4369 | | exec->state = state; |
4370 | | } |
4371 | | codepoint = CUR_SCHAR(&(exec->inputString[exec->index]), |
4372 | | len); |
4373 | | ret = xmlRegCheckCharacter(atom, codepoint); |
4374 | | exec->transcount++; |
4375 | | } while (ret == 1); |
4376 | | if (exec->transcount < atom->min) |
4377 | | ret = 0; |
4378 | | |
4379 | | /* |
4380 | | * If the last check failed but one transition was found |
4381 | | * possible, rollback |
4382 | | */ |
4383 | | if (ret < 0) |
4384 | | ret = 0; |
4385 | | if (ret == 0) { |
4386 | | goto rollback; |
4387 | | } |
4388 | | } |
4389 | | } |
4390 | | if (ret == 1) { |
4391 | | if (exec->state->nbTrans > exec->transno + 1) { |
4392 | | xmlFARegExecSave(exec); |
4393 | | } |
4394 | | /* |
4395 | | * restart count for expressions like this ((abc){2})* |
4396 | | */ |
4397 | | if (trans->count >= 0) { |
4398 | | exec->counts[trans->count] = 0; |
4399 | | } |
4400 | | if (trans->counter >= 0) { |
4401 | | exec->counts[trans->counter]++; |
4402 | | } |
4403 | | exec->state = exec->comp->states[trans->to]; |
4404 | | exec->transno = 0; |
4405 | | if (trans->atom != NULL) { |
4406 | | exec->index += len; |
4407 | | } |
4408 | | goto progress; |
4409 | | } else if (ret < 0) { |
4410 | | exec->status = XML_REGEXP_INTERNAL_ERROR; |
4411 | | break; |
4412 | | } |
4413 | | } |
4414 | | if ((exec->transno != 0) || (exec->state->nbTrans == 0)) { |
4415 | | rollback: |
4416 | | /* |
4417 | | * Failed to find a way out |
4418 | | */ |
4419 | | exec->determinist = 0; |
4420 | | xmlFARegExecRollBack(exec); |
4421 | | } |
4422 | | progress: |
4423 | | continue; |
4424 | | } |
4425 | | } |
4426 | | #endif |
4427 | | /************************************************************************ |
4428 | | * * |
4429 | | * Parser for the Schemas Datatype Regular Expressions * |
4430 | | * http://www.w3.org/TR/2001/REC-xmlschema-2-20010502/#regexs * |
4431 | | * * |
4432 | | ************************************************************************/ |
4433 | | |
4434 | | /** |
4435 | | * xmlFAIsChar: |
4436 | | * @ctxt: a regexp parser context |
4437 | | * |
4438 | | * [10] Char ::= [^.\?*+()|#x5B#x5D] |
4439 | | */ |
4440 | | static int |
4441 | 0 | xmlFAIsChar(xmlRegParserCtxtPtr ctxt) { |
4442 | 0 | int cur; |
4443 | 0 | int len; |
4444 | |
|
4445 | 0 | len = 4; |
4446 | 0 | cur = xmlGetUTF8Char(ctxt->cur, &len); |
4447 | 0 | if (cur < 0) { |
4448 | 0 | ERROR("Invalid UTF-8"); |
4449 | 0 | return(0); |
4450 | 0 | } |
4451 | 0 | if ((cur == '.') || (cur == '\\') || (cur == '?') || |
4452 | 0 | (cur == '*') || (cur == '+') || (cur == '(') || |
4453 | 0 | (cur == ')') || (cur == '|') || (cur == 0x5B) || |
4454 | 0 | (cur == 0x5D) || (cur == 0)) |
4455 | 0 | return(-1); |
4456 | 0 | return(cur); |
4457 | 0 | } |
4458 | | |
4459 | | /** |
4460 | | * xmlFAParseCharProp: |
4461 | | * @ctxt: a regexp parser context |
4462 | | * |
4463 | | * [27] charProp ::= IsCategory | IsBlock |
4464 | | * [28] IsCategory ::= Letters | Marks | Numbers | Punctuation | |
4465 | | * Separators | Symbols | Others |
4466 | | * [29] Letters ::= 'L' [ultmo]? |
4467 | | * [30] Marks ::= 'M' [nce]? |
4468 | | * [31] Numbers ::= 'N' [dlo]? |
4469 | | * [32] Punctuation ::= 'P' [cdseifo]? |
4470 | | * [33] Separators ::= 'Z' [slp]? |
4471 | | * [34] Symbols ::= 'S' [mcko]? |
4472 | | * [35] Others ::= 'C' [cfon]? |
4473 | | * [36] IsBlock ::= 'Is' [a-zA-Z0-9#x2D]+ |
4474 | | */ |
4475 | | static void |
4476 | 0 | xmlFAParseCharProp(xmlRegParserCtxtPtr ctxt) { |
4477 | 0 | int cur; |
4478 | 0 | xmlRegAtomType type = (xmlRegAtomType) 0; |
4479 | 0 | xmlChar *blockName = NULL; |
4480 | |
|
4481 | 0 | cur = CUR; |
4482 | 0 | if (cur == 'L') { |
4483 | 0 | NEXT; |
4484 | 0 | cur = CUR; |
4485 | 0 | if (cur == 'u') { |
4486 | 0 | NEXT; |
4487 | 0 | type = XML_REGEXP_LETTER_UPPERCASE; |
4488 | 0 | } else if (cur == 'l') { |
4489 | 0 | NEXT; |
4490 | 0 | type = XML_REGEXP_LETTER_LOWERCASE; |
4491 | 0 | } else if (cur == 't') { |
4492 | 0 | NEXT; |
4493 | 0 | type = XML_REGEXP_LETTER_TITLECASE; |
4494 | 0 | } else if (cur == 'm') { |
4495 | 0 | NEXT; |
4496 | 0 | type = XML_REGEXP_LETTER_MODIFIER; |
4497 | 0 | } else if (cur == 'o') { |
4498 | 0 | NEXT; |
4499 | 0 | type = XML_REGEXP_LETTER_OTHERS; |
4500 | 0 | } else { |
4501 | 0 | type = XML_REGEXP_LETTER; |
4502 | 0 | } |
4503 | 0 | } else if (cur == 'M') { |
4504 | 0 | NEXT; |
4505 | 0 | cur = CUR; |
4506 | 0 | if (cur == 'n') { |
4507 | 0 | NEXT; |
4508 | | /* nonspacing */ |
4509 | 0 | type = XML_REGEXP_MARK_NONSPACING; |
4510 | 0 | } else if (cur == 'c') { |
4511 | 0 | NEXT; |
4512 | | /* spacing combining */ |
4513 | 0 | type = XML_REGEXP_MARK_SPACECOMBINING; |
4514 | 0 | } else if (cur == 'e') { |
4515 | 0 | NEXT; |
4516 | | /* enclosing */ |
4517 | 0 | type = XML_REGEXP_MARK_ENCLOSING; |
4518 | 0 | } else { |
4519 | | /* all marks */ |
4520 | 0 | type = XML_REGEXP_MARK; |
4521 | 0 | } |
4522 | 0 | } else if (cur == 'N') { |
4523 | 0 | NEXT; |
4524 | 0 | cur = CUR; |
4525 | 0 | if (cur == 'd') { |
4526 | 0 | NEXT; |
4527 | | /* digital */ |
4528 | 0 | type = XML_REGEXP_NUMBER_DECIMAL; |
4529 | 0 | } else if (cur == 'l') { |
4530 | 0 | NEXT; |
4531 | | /* letter */ |
4532 | 0 | type = XML_REGEXP_NUMBER_LETTER; |
4533 | 0 | } else if (cur == 'o') { |
4534 | 0 | NEXT; |
4535 | | /* other */ |
4536 | 0 | type = XML_REGEXP_NUMBER_OTHERS; |
4537 | 0 | } else { |
4538 | | /* all numbers */ |
4539 | 0 | type = XML_REGEXP_NUMBER; |
4540 | 0 | } |
4541 | 0 | } else if (cur == 'P') { |
4542 | 0 | NEXT; |
4543 | 0 | cur = CUR; |
4544 | 0 | if (cur == 'c') { |
4545 | 0 | NEXT; |
4546 | | /* connector */ |
4547 | 0 | type = XML_REGEXP_PUNCT_CONNECTOR; |
4548 | 0 | } else if (cur == 'd') { |
4549 | 0 | NEXT; |
4550 | | /* dash */ |
4551 | 0 | type = XML_REGEXP_PUNCT_DASH; |
4552 | 0 | } else if (cur == 's') { |
4553 | 0 | NEXT; |
4554 | | /* open */ |
4555 | 0 | type = XML_REGEXP_PUNCT_OPEN; |
4556 | 0 | } else if (cur == 'e') { |
4557 | 0 | NEXT; |
4558 | | /* close */ |
4559 | 0 | type = XML_REGEXP_PUNCT_CLOSE; |
4560 | 0 | } else if (cur == 'i') { |
4561 | 0 | NEXT; |
4562 | | /* initial quote */ |
4563 | 0 | type = XML_REGEXP_PUNCT_INITQUOTE; |
4564 | 0 | } else if (cur == 'f') { |
4565 | 0 | NEXT; |
4566 | | /* final quote */ |
4567 | 0 | type = XML_REGEXP_PUNCT_FINQUOTE; |
4568 | 0 | } else if (cur == 'o') { |
4569 | 0 | NEXT; |
4570 | | /* other */ |
4571 | 0 | type = XML_REGEXP_PUNCT_OTHERS; |
4572 | 0 | } else { |
4573 | | /* all punctuation */ |
4574 | 0 | type = XML_REGEXP_PUNCT; |
4575 | 0 | } |
4576 | 0 | } else if (cur == 'Z') { |
4577 | 0 | NEXT; |
4578 | 0 | cur = CUR; |
4579 | 0 | if (cur == 's') { |
4580 | 0 | NEXT; |
4581 | | /* space */ |
4582 | 0 | type = XML_REGEXP_SEPAR_SPACE; |
4583 | 0 | } else if (cur == 'l') { |
4584 | 0 | NEXT; |
4585 | | /* line */ |
4586 | 0 | type = XML_REGEXP_SEPAR_LINE; |
4587 | 0 | } else if (cur == 'p') { |
4588 | 0 | NEXT; |
4589 | | /* paragraph */ |
4590 | 0 | type = XML_REGEXP_SEPAR_PARA; |
4591 | 0 | } else { |
4592 | | /* all separators */ |
4593 | 0 | type = XML_REGEXP_SEPAR; |
4594 | 0 | } |
4595 | 0 | } else if (cur == 'S') { |
4596 | 0 | NEXT; |
4597 | 0 | cur = CUR; |
4598 | 0 | if (cur == 'm') { |
4599 | 0 | NEXT; |
4600 | 0 | type = XML_REGEXP_SYMBOL_MATH; |
4601 | | /* math */ |
4602 | 0 | } else if (cur == 'c') { |
4603 | 0 | NEXT; |
4604 | 0 | type = XML_REGEXP_SYMBOL_CURRENCY; |
4605 | | /* currency */ |
4606 | 0 | } else if (cur == 'k') { |
4607 | 0 | NEXT; |
4608 | 0 | type = XML_REGEXP_SYMBOL_MODIFIER; |
4609 | | /* modifiers */ |
4610 | 0 | } else if (cur == 'o') { |
4611 | 0 | NEXT; |
4612 | 0 | type = XML_REGEXP_SYMBOL_OTHERS; |
4613 | | /* other */ |
4614 | 0 | } else { |
4615 | | /* all symbols */ |
4616 | 0 | type = XML_REGEXP_SYMBOL; |
4617 | 0 | } |
4618 | 0 | } else if (cur == 'C') { |
4619 | 0 | NEXT; |
4620 | 0 | cur = CUR; |
4621 | 0 | if (cur == 'c') { |
4622 | 0 | NEXT; |
4623 | | /* control */ |
4624 | 0 | type = XML_REGEXP_OTHER_CONTROL; |
4625 | 0 | } else if (cur == 'f') { |
4626 | 0 | NEXT; |
4627 | | /* format */ |
4628 | 0 | type = XML_REGEXP_OTHER_FORMAT; |
4629 | 0 | } else if (cur == 'o') { |
4630 | 0 | NEXT; |
4631 | | /* private use */ |
4632 | 0 | type = XML_REGEXP_OTHER_PRIVATE; |
4633 | 0 | } else if (cur == 'n') { |
4634 | 0 | NEXT; |
4635 | | /* not assigned */ |
4636 | 0 | type = XML_REGEXP_OTHER_NA; |
4637 | 0 | } else { |
4638 | | /* all others */ |
4639 | 0 | type = XML_REGEXP_OTHER; |
4640
|