Gitiles
Code Review Sign In
gerrit-public.fairphone.software / fp2-dev / platform / external / libxml2 / 4255d504151db75c17f85192ce74f45dd2d65533 / . / xmlregexp.c
blob: 1139e158a8d6944b011818c5cbe9fd8263b639ce [file] [log] [blame]
Daniel Veillard4255d502002-04-16 15:50:10 +0000[diff] [blame^]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/shemas mechanisms now available in
6 * XML related specifications thise includes:
7 * - XML-1.0 DTD validation
8 * - XML Schemas structure part 1
9 * - XML Schemas Datatypes part 2 especially Appendix F
10 * - RELAX-NG/TREX i.e. the counter proposal
11 *
12 * See Copyright for the status of this software.
13 *
14 * Daniel Veillard <veillard@redhat.com>
15 */
16
17#define IN_LIBXML
18#include "libxml.h"
19
20#ifdef LIBXML_REGEXP_ENABLED
21
22#include <stdio.h>
23#include <string.h>
24#include <libxml/tree.h>
25#include <libxml/parserInternals.h>
26#include <libxml/xmlregexp.h>
27#include <libxml/xmlautomata.h>
28#include <libxml/xmlunicode.h>
29
30/* #define DEBUG_REGEXP_GRAPH */
31/* #define DEBUG_REGEXP_EXEC */
32/* #define DEBUG_PUSH */
33
34#define ERROR(str) ctxt->error = 1; \
35 xmlGenericError(xmlGenericErrorContext, "Regexp: %s: %s\n", str, ctxt->cur)
36#define NEXT ctxt->cur++
37#define CUR (*(ctxt->cur))
38#define NXT(index) (ctxt->cur[index])
39
40#define CUR_SCHAR(s, l) xmlStringCurrentChar(NULL, s, &l)
41#define NEXTL(l) ctxt->cur += l;
42
43
44/************************************************************************
45 * *
46 * Datatypes and structures *
47 * *
48 ************************************************************************/
49
50typedef enum {
51 XML_REGEXP_EPSILON = 1,
52 XML_REGEXP_CHARVAL,
53 XML_REGEXP_RANGES,
54 XML_REGEXP_SUBREG,
55 XML_REGEXP_STRING,
56 XML_REGEXP_ANYCHAR, /* . */
57 XML_REGEXP_ANYSPACE, /* \s */
58 XML_REGEXP_NOTSPACE, /* \S */
59 XML_REGEXP_INITNAME, /* \l */
60 XML_REGEXP_NOTINITNAME, /* \l */
61 XML_REGEXP_NAMECHAR, /* \c */
62 XML_REGEXP_NOTNAMECHAR, /* \C */
63 XML_REGEXP_DECIMAL, /* \d */
64 XML_REGEXP_NOTDECIMAL, /* \d */
65 XML_REGEXP_REALCHAR, /* \w */
66 XML_REGEXP_NOTREALCHAR, /* \w */
67 XML_REGEXP_LETTER,
68 XML_REGEXP_LETTER_UPPERCASE,
69 XML_REGEXP_LETTER_LOWERCASE,
70 XML_REGEXP_LETTER_TITLECASE,
71 XML_REGEXP_LETTER_MODIFIER,
72 XML_REGEXP_LETTER_OTHERS,
73 XML_REGEXP_MARK,
74 XML_REGEXP_MARK_NONSPACING,
75 XML_REGEXP_MARK_SPACECOMBINING,
76 XML_REGEXP_MARK_ENCLOSING,
77 XML_REGEXP_NUMBER,
78 XML_REGEXP_NUMBER_DECIMAL,
79 XML_REGEXP_NUMBER_LETTER,
80 XML_REGEXP_NUMBER_OTHERS,
81 XML_REGEXP_PUNCT,
82 XML_REGEXP_PUNCT_CONNECTOR,
83 XML_REGEXP_PUNCT_DASH,
84 XML_REGEXP_PUNCT_OPEN,
85 XML_REGEXP_PUNCT_CLOSE,
86 XML_REGEXP_PUNCT_INITQUOTE,
87 XML_REGEXP_PUNCT_FINQUOTE,
88 XML_REGEXP_PUNCT_OTHERS,
89 XML_REGEXP_SEPAR,
90 XML_REGEXP_SEPAR_SPACE,
91 XML_REGEXP_SEPAR_LINE,
92 XML_REGEXP_SEPAR_PARA,
93 XML_REGEXP_SYMBOL,
94 XML_REGEXP_SYMBOL_MATH,
95 XML_REGEXP_SYMBOL_CURRENCY,
96 XML_REGEXP_SYMBOL_MODIFIER,
97 XML_REGEXP_SYMBOL_OTHERS,
98 XML_REGEXP_OTHER,
99 XML_REGEXP_OTHER_CONTROL,
100 XML_REGEXP_OTHER_FORMAT,
101 XML_REGEXP_OTHER_PRIVATE,
102 XML_REGEXP_OTHER_NA,
103 XML_REGEXP_BLOCK_NAME
104} xmlRegAtomType;
105
106typedef enum {
107 XML_REGEXP_QUANT_EPSILON = 1,
108 XML_REGEXP_QUANT_ONCE,
109 XML_REGEXP_QUANT_OPT,
110 XML_REGEXP_QUANT_MULT,
111 XML_REGEXP_QUANT_PLUS,
112 XML_REGEXP_QUANT_RANGE
113} xmlRegQuantType;
114
115typedef enum {
116 XML_REGEXP_START_STATE = 1,
117 XML_REGEXP_FINAL_STATE,
118 XML_REGEXP_TRANS_STATE
119} xmlRegStateType;
120
121typedef enum {
122 XML_REGEXP_MARK_NORMAL = 0,
123 XML_REGEXP_MARK_START,
124 XML_REGEXP_MARK_VISITED
125} xmlRegMarkedType;
126
127typedef struct _xmlRegRange xmlRegRange;
128typedef xmlRegRange *xmlRegRangePtr;
129
130struct _xmlRegRange {
131 int neg;
132 xmlRegAtomType type;
133 int start;
134 int end;
135 xmlChar *blockName;
136};
137
138typedef struct _xmlRegAtom xmlRegAtom;
139typedef xmlRegAtom *xmlRegAtomPtr;
140
141typedef struct _xmlAutomataState xmlRegState;
142typedef xmlRegState *xmlRegStatePtr;
143
144struct _xmlRegAtom {
145 int no;
146 xmlRegAtomType type;
147 xmlRegQuantType quant;
148 int min;
149 int max;
150
151 void *valuep;
152 int neg;
153 int codepoint;
154 xmlRegStatePtr start;
155 xmlRegStatePtr stop;
156 int maxRanges;
157 int nbRanges;
158 xmlRegRangePtr *ranges;
159 void *data;
160};
161
162typedef struct _xmlRegCounter xmlRegCounter;
163typedef xmlRegCounter *xmlRegCounterPtr;
164
165struct _xmlRegCounter {
166 int min;
167 int max;
168};
169
170typedef struct _xmlRegTrans xmlRegTrans;
171typedef xmlRegTrans *xmlRegTransPtr;
172
173struct _xmlRegTrans {
174 xmlRegAtomPtr atom;
175 int to;
176 int counter;
177 int count;
178};
179
180struct _xmlAutomataState {
181 xmlRegStateType type;
182 xmlRegMarkedType mark;
183 int no;
184
185 int maxTrans;
186 int nbTrans;
187 xmlRegTrans *trans;
188};
189
190typedef struct _xmlAutomata xmlRegParserCtxt;
191typedef xmlRegParserCtxt *xmlRegParserCtxtPtr;
192
193struct _xmlAutomata {
194 xmlChar *string;
195 xmlChar *cur;
196
197 int error;
198 int neg;
199
200 xmlRegStatePtr start;
201 xmlRegStatePtr end;
202 xmlRegStatePtr state;
203
204 xmlRegAtomPtr atom;
205
206 int maxAtoms;
207 int nbAtoms;
208 xmlRegAtomPtr *atoms;
209
210 int maxStates;
211 int nbStates;
212 xmlRegStatePtr *states;
213
214 int maxCounters;
215 int nbCounters;
216 xmlRegCounter *counters;
217};
218
219struct _xmlRegexp {
220 xmlChar *string;
221 int nbStates;
222 xmlRegStatePtr *states;
223 int nbAtoms;
224 xmlRegAtomPtr *atoms;
225 int nbCounters;
226 xmlRegCounter *counters;
227};
228
229typedef struct _xmlRegExecRollback xmlRegExecRollback;
230typedef xmlRegExecRollback *xmlRegExecRollbackPtr;
231
232struct _xmlRegExecRollback {
233 xmlRegStatePtr state;/* the current state */
234 int index; /* the index in the input stack */
235 int nextbranch; /* the next transition to explore in that state */
236 int *counts; /* save the automate state if it has some */
237};
238
239typedef struct _xmlRegInputToken xmlRegInputToken;
240typedef xmlRegInputToken *xmlRegInputTokenPtr;
241
242struct _xmlRegInputToken {
243 xmlChar *value;
244 void *data;
245};
246
247struct _xmlRegExecCtxt {
248 int status; /* execution status != 0 indicate an error */
249 int determinist; /* did we found an inderterministic behaviour */
250 xmlRegexpPtr comp; /* the compiled regexp */
251 xmlRegExecCallbacks callback;
252 void *data;
253
254 xmlRegStatePtr state;/* the current state */
255 int transno; /* the current transition on that state */
256 int transcount; /* the number of char in char counted transitions */
257
258 /*
259 * A stack of rollback states
260 */
261 int maxRollbacks;
262 int nbRollbacks;
263 xmlRegExecRollback *rollbacks;
264
265 /*
266 * The state of the automata if any
267 */
268 int *counts;
269
270 /*
271 * The input stack
272 */
273 int inputStackMax;
274 int inputStackNr;
275 int index;
276 int *charStack;
277 const xmlChar *inputString; /* when operating on characters */
278 xmlRegInputTokenPtr inputStack;/* when operating on strings */
279
280};
281
282static void xmlFAParseRegExp(xmlRegParserCtxtPtr ctxt, int top);
283
284/************************************************************************
285 * *
286 * Allocation/Deallocation *
287 * *
288 ************************************************************************/
289
290/**
291 * xmlRegEpxFromParse:
292 * @ctxt: the parser context used to build it
293 *
294 * Allocate a new regexp and fill it with the reult from the parser
295 *
296 * Returns the new regexp or NULL in case of error
297 */
298static xmlRegexpPtr
299xmlRegEpxFromParse(xmlRegParserCtxtPtr ctxt) {
300 xmlRegexpPtr ret;
301
302 ret = (xmlRegexpPtr) xmlMalloc(sizeof(xmlRegexp));
303 if (ret == NULL)
304 return(NULL);
305 memset(ret, 0, sizeof(xmlRegexp));
306 ret->string = ctxt->string;
307 ctxt->string = NULL;
308 ret->nbStates = ctxt->nbStates;
309 ctxt->nbStates = 0;
310 ret->states = ctxt->states;
311 ctxt->states = NULL;
312 ret->nbAtoms = ctxt->nbAtoms;
313 ctxt->nbAtoms = 0;
314 ret->atoms = ctxt->atoms;
315 ctxt->atoms = NULL;
316 ret->nbCounters = ctxt->nbCounters;
317 ctxt->nbCounters = 0;
318 ret->counters = ctxt->counters;
319 ctxt->counters = NULL;
320 return(ret);
321}
322
323/**
324 * xmlRegNewParserCtxt:
325 * @string: the string to parse
326 *
327 * Allocate a new regexp parser context
328 *
329 * Returns the new context or NULL in case of error
330 */
331static xmlRegParserCtxtPtr
332xmlRegNewParserCtxt(const xmlChar *string) {
333 xmlRegParserCtxtPtr ret;
334
335 ret = (xmlRegParserCtxtPtr) xmlMalloc(sizeof(xmlRegParserCtxt));
336 if (ret == NULL)
337 return(NULL);
338 memset(ret, 0, sizeof(xmlRegParserCtxt));
339 if (string != NULL)
340 ret->string = xmlStrdup(string);
341 ret->cur = ret->string;
342 ret->neg = 0;
343 ret->error = 0;
344 return(ret);
345}
346
347/**
348 * xmlRegNewRange:
349 * @ctxt: the regexp parser context
350 * @neg: is that negative
351 * @type: the type of range
352 * @start: the start codepoint
353 * @end: the end codepoint
354 *
355 * Allocate a new regexp range
356 *
357 * Returns the new range or NULL in case of error
358 */
359static xmlRegRangePtr
360xmlRegNewRange(xmlRegParserCtxtPtr ctxt,
361 int neg, xmlRegAtomType type, int start, int end) {
362 xmlRegRangePtr ret;
363
364 ret = (xmlRegRangePtr) xmlMalloc(sizeof(xmlRegRange));
365 if (ret == NULL) {
366 ERROR("failed to allocate regexp range");
367 return(NULL);
368 }
369 ret->neg = neg;
370 ret->type = type;
371 ret->start = start;
372 ret->end = end;
373 return(ret);
374}
375
376/**
377 * xmlRegFreeRange:
378 * @range: the regexp range
379 *
380 * Free a regexp range
381 */
382static void
383xmlRegFreeRange(xmlRegRangePtr range) {
384 if (range == NULL)
385 return;
386
387 if (range->blockName != NULL)
388 xmlFree(range->blockName);
389 xmlFree(range);
390}
391
392/**
393 * xmlRegNewAtom:
394 * @ctxt: the regexp parser context
395 * @type: the type of atom
396 *
397 * Allocate a new regexp range
398 *
399 * Returns the new atom or NULL in case of error
400 */
401static xmlRegAtomPtr
402xmlRegNewAtom(xmlRegParserCtxtPtr ctxt, xmlRegAtomType type) {
403 xmlRegAtomPtr ret;
404
405 ret = (xmlRegAtomPtr) xmlMalloc(sizeof(xmlRegAtom));
406 if (ret == NULL) {
407 ERROR("failed to allocate regexp atom");
408 return(NULL);
409 }
410 memset(ret, 0, sizeof(xmlRegAtom));
411 ret->type = type;
412 ret->quant = XML_REGEXP_QUANT_ONCE;
413 ret->min = 0;
414 ret->max = 0;
415 return(ret);
416}
417
418/**
419 * xmlRegFreeAtom:
420 * @atom: the regexp atom
421 *
422 * Free a regexp atom
423 */
424static void
425xmlRegFreeAtom(xmlRegAtomPtr atom) {
426 int i;
427
428 if (atom == NULL)
429 return;
430
431 for (i = 0;i < atom->nbRanges;i++)
432 xmlRegFreeRange(atom->ranges[i]);
433 if (atom->ranges != NULL)
434 xmlFree(atom->ranges);
435 if (atom->type == XML_REGEXP_STRING)
436 xmlFree(atom->valuep);
437 xmlFree(atom);
438}
439
440static xmlRegStatePtr
441xmlRegNewState(xmlRegParserCtxtPtr ctxt) {
442 xmlRegStatePtr ret;
443
444 ret = (xmlRegStatePtr) xmlMalloc(sizeof(xmlRegState));
445 if (ret == NULL) {
446 ERROR("failed to allocate regexp state");
447 return(NULL);
448 }
449 memset(ret, 0, sizeof(xmlRegState));
450 ret->type = XML_REGEXP_TRANS_STATE;
451 ret->mark = XML_REGEXP_MARK_NORMAL;
452 return(ret);
453}
454
455/**
456 * xmlRegFreeState:
457 * @state: the regexp state
458 *
459 * Free a regexp state
460 */
461static void
462xmlRegFreeState(xmlRegStatePtr state) {
463 if (state == NULL)
464 return;
465
466 if (state->trans != NULL)
467 xmlFree(state->trans);
468 xmlFree(state);
469}
470
471/**
472 * xmlRegFreeParserCtxt:
473 * @ctxt: the regexp parser context
474 *
475 * Free a regexp parser context
476 */
477static void
478xmlRegFreeParserCtxt(xmlRegParserCtxtPtr ctxt) {
479 int i;
480 if (ctxt == NULL)
481 return;
482
483 if (ctxt->string != NULL)
484 xmlFree(ctxt->string);
485 if (ctxt->states != NULL) {
486 for (i = 0;i < ctxt->nbStates;i++)
487 xmlRegFreeState(ctxt->states[i]);
488 xmlFree(ctxt->states);
489 }
490 if (ctxt->atoms != NULL) {
491 for (i = 0;i < ctxt->nbAtoms;i++)
492 xmlRegFreeAtom(ctxt->atoms[i]);
493 xmlFree(ctxt->atoms);
494 }
495 if (ctxt->counters != NULL)
496 xmlFree(ctxt->counters);
497 xmlFree(ctxt);
498}
499
500/************************************************************************
501 * *
502 * Display of Data structures *
503 * *
504 ************************************************************************/
505
506static void
507xmlRegPrintAtomType(FILE *output, xmlRegAtomType type) {
508 switch (type) {
509 case XML_REGEXP_EPSILON:
510 fprintf(output, "epsilon "); break;
511 case XML_REGEXP_CHARVAL:
512 fprintf(output, "charval "); break;
513 case XML_REGEXP_RANGES:
514 fprintf(output, "ranges "); break;
515 case XML_REGEXP_SUBREG:
516 fprintf(output, "subexpr "); break;
517 case XML_REGEXP_STRING:
518 fprintf(output, "string "); break;
519 case XML_REGEXP_ANYCHAR:
520 fprintf(output, "anychar "); break;
521 case XML_REGEXP_ANYSPACE:
522 fprintf(output, "anyspace "); break;
523 case XML_REGEXP_NOTSPACE:
524 fprintf(output, "notspace "); break;
525 case XML_REGEXP_INITNAME:
526 fprintf(output, "initname "); break;
527 case XML_REGEXP_NOTINITNAME:
528 fprintf(output, "notinitname "); break;
529 case XML_REGEXP_NAMECHAR:
530 fprintf(output, "namechar "); break;
531 case XML_REGEXP_NOTNAMECHAR:
532 fprintf(output, "notnamechar "); break;
533 case XML_REGEXP_DECIMAL:
534 fprintf(output, "decimal "); break;
535 case XML_REGEXP_NOTDECIMAL:
536 fprintf(output, "notdecimal "); break;
537 case XML_REGEXP_REALCHAR:
538 fprintf(output, "realchar "); break;
539 case XML_REGEXP_NOTREALCHAR:
540 fprintf(output, "notrealchar "); break;
541 case XML_REGEXP_LETTER:
542 fprintf(output, "LETTER "); break;
543 case XML_REGEXP_LETTER_UPPERCASE:
544 fprintf(output, "LETTER_UPPERCASE "); break;
545 case XML_REGEXP_LETTER_LOWERCASE:
546 fprintf(output, "LETTER_LOWERCASE "); break;
547 case XML_REGEXP_LETTER_TITLECASE:
548 fprintf(output, "LETTER_TITLECASE "); break;
549 case XML_REGEXP_LETTER_MODIFIER:
550 fprintf(output, "LETTER_MODIFIER "); break;
551 case XML_REGEXP_LETTER_OTHERS:
552 fprintf(output, "LETTER_OTHERS "); break;
553 case XML_REGEXP_MARK:
554 fprintf(output, "MARK "); break;
555 case XML_REGEXP_MARK_NONSPACING:
556 fprintf(output, "MARK_NONSPACING "); break;
557 case XML_REGEXP_MARK_SPACECOMBINING:
558 fprintf(output, "MARK_SPACECOMBINING "); break;
559 case XML_REGEXP_MARK_ENCLOSING:
560 fprintf(output, "MARK_ENCLOSING "); break;
561 case XML_REGEXP_NUMBER:
562 fprintf(output, "NUMBER "); break;
563 case XML_REGEXP_NUMBER_DECIMAL:
564 fprintf(output, "NUMBER_DECIMAL "); break;
565 case XML_REGEXP_NUMBER_LETTER:
566 fprintf(output, "NUMBER_LETTER "); break;
567 case XML_REGEXP_NUMBER_OTHERS:
568 fprintf(output, "NUMBER_OTHERS "); break;
569 case XML_REGEXP_PUNCT:
570 fprintf(output, "PUNCT "); break;
571 case XML_REGEXP_PUNCT_CONNECTOR:
572 fprintf(output, "PUNCT_CONNECTOR "); break;
573 case XML_REGEXP_PUNCT_DASH:
574 fprintf(output, "PUNCT_DASH "); break;
575 case XML_REGEXP_PUNCT_OPEN:
576 fprintf(output, "PUNCT_OPEN "); break;
577 case XML_REGEXP_PUNCT_CLOSE:
578 fprintf(output, "PUNCT_CLOSE "); break;
579 case XML_REGEXP_PUNCT_INITQUOTE:
580 fprintf(output, "PUNCT_INITQUOTE "); break;
581 case XML_REGEXP_PUNCT_FINQUOTE:
582 fprintf(output, "PUNCT_FINQUOTE "); break;
583 case XML_REGEXP_PUNCT_OTHERS:
584 fprintf(output, "PUNCT_OTHERS "); break;
585 case XML_REGEXP_SEPAR:
586 fprintf(output, "SEPAR "); break;
587 case XML_REGEXP_SEPAR_SPACE:
588 fprintf(output, "SEPAR_SPACE "); break;
589 case XML_REGEXP_SEPAR_LINE:
590 fprintf(output, "SEPAR_LINE "); break;
591 case XML_REGEXP_SEPAR_PARA:
592 fprintf(output, "SEPAR_PARA "); break;
593 case XML_REGEXP_SYMBOL:
594 fprintf(output, "SYMBOL "); break;
595 case XML_REGEXP_SYMBOL_MATH:
596 fprintf(output, "SYMBOL_MATH "); break;
597 case XML_REGEXP_SYMBOL_CURRENCY:
598 fprintf(output, "SYMBOL_CURRENCY "); break;
599 case XML_REGEXP_SYMBOL_MODIFIER:
600 fprintf(output, "SYMBOL_MODIFIER "); break;
601 case XML_REGEXP_SYMBOL_OTHERS:
602 fprintf(output, "SYMBOL_OTHERS "); break;
603 case XML_REGEXP_OTHER:
604 fprintf(output, "OTHER "); break;
605 case XML_REGEXP_OTHER_CONTROL:
606 fprintf(output, "OTHER_CONTROL "); break;
607 case XML_REGEXP_OTHER_FORMAT:
608 fprintf(output, "OTHER_FORMAT "); break;
609 case XML_REGEXP_OTHER_PRIVATE:
610 fprintf(output, "OTHER_PRIVATE "); break;
611 case XML_REGEXP_OTHER_NA:
612 fprintf(output, "OTHER_NA "); break;
613 case XML_REGEXP_BLOCK_NAME:
614 fprintf(output, "BLOCK "); break;
615 }
616}
617
618static void
619xmlRegPrintQuantType(FILE *output, xmlRegQuantType type) {
620 switch (type) {
621 case XML_REGEXP_QUANT_EPSILON:
622 fprintf(output, "epsilon "); break;
623 case XML_REGEXP_QUANT_ONCE:
624 fprintf(output, "once "); break;
625 case XML_REGEXP_QUANT_OPT:
626 fprintf(output, "? "); break;
627 case XML_REGEXP_QUANT_MULT:
628 fprintf(output, "* "); break;
629 case XML_REGEXP_QUANT_PLUS:
630 fprintf(output, "+ "); break;
631 case XML_REGEXP_QUANT_RANGE:
632 fprintf(output, "range "); break;
633 }
634}
635static void
636xmlRegPrintRange(FILE *output, xmlRegRangePtr range) {
637 fprintf(output, " range: ");
638 if (range->neg)
639 fprintf(output, "negative ");
640 xmlRegPrintAtomType(output, range->type);
641 fprintf(output, "%c - %c\n", range->start, range->end);
642}
643
644static void
645xmlRegPrintAtom(FILE *output, xmlRegAtomPtr atom) {
646 fprintf(output, " atom: ");
647 if (atom == NULL) {
648 fprintf(output, "NULL\n");
649 return;
650 }
651 xmlRegPrintAtomType(output, atom->type);
652 xmlRegPrintQuantType(output, atom->quant);
653 if (atom->quant == XML_REGEXP_QUANT_RANGE)
654 fprintf(output, "%d-%d ", atom->min, atom->max);
655 if (atom->type == XML_REGEXP_STRING)
656 fprintf(output, "'%s' ", (char *) atom->valuep);
657 if (atom->type == XML_REGEXP_CHARVAL)
658 fprintf(output, "char %c\n", atom->codepoint);
659 else if (atom->type == XML_REGEXP_RANGES) {
660 int i;
661 fprintf(output, "%d entries\n", atom->nbRanges);
662 for (i = 0; i < atom->nbRanges;i++)
663 xmlRegPrintRange(output, atom->ranges[i]);
664 } else if (atom->type == XML_REGEXP_SUBREG) {
665 fprintf(output, "start %d end %d\n", atom->start->no, atom->stop->no);
666 } else {
667 fprintf(output, "\n");
668 }
669}
670
671static void
672xmlRegPrintTrans(FILE *output, xmlRegTransPtr trans) {
673 fprintf(output, " trans: ");
674 if (trans == NULL) {
675 fprintf(output, "NULL\n");
676 return;
677 }
678 if (trans->to < 0) {
679 fprintf(output, "removed\n");
680 return;
681 }
682 if (trans->counter >= 0) {
683 fprintf(output, "counted %d, ", trans->counter);
684 }
685 if (trans->count >= 0) {
686 fprintf(output, "count based %d, ", trans->count);
687 }
688 if (trans->atom == NULL) {
689 fprintf(output, "epsilon to %d\n", trans->to);
690 return;
691 }
692 if (trans->atom->type == XML_REGEXP_CHARVAL)
693 fprintf(output, "char %c ", trans->atom->codepoint);
694 fprintf(output, "atom %d, to %d\n", trans->atom->no, trans->to);
695}
696
697static void
698xmlRegPrintState(FILE *output, xmlRegStatePtr state) {
699 int i;
700
701 fprintf(output, " state: ");
702 if (state == NULL) {
703 fprintf(output, "NULL\n");
704 return;
705 }
706 if (state->type == XML_REGEXP_START_STATE)
707 fprintf(output, "START ");
708 if (state->type == XML_REGEXP_FINAL_STATE)
709 fprintf(output, "FINAL ");
710
711 fprintf(output, "%d, %d transitions:\n", state->no, state->nbTrans);
712 for (i = 0;i < state->nbTrans; i++) {
713 xmlRegPrintTrans(output, &(state->trans[i]));
714 }
715}
716
717#if 0
718static void
719xmlRegPrintCtxt(FILE *output, xmlRegParserCtxtPtr ctxt) {
720 int i;
721
722 fprintf(output, " ctxt: ");
723 if (ctxt == NULL) {
724 fprintf(output, "NULL\n");
725 return;
726 }
727 fprintf(output, "'%s' ", ctxt->string);
728 if (ctxt->error)
729 fprintf(output, "error ");
730 if (ctxt->neg)
731 fprintf(output, "neg ");
732 fprintf(output, "\n");
733 fprintf(output, "%d atoms:\n", ctxt->nbAtoms);
734 for (i = 0;i < ctxt->nbAtoms; i++) {
735 fprintf(output, " %02d ", i);
736 xmlRegPrintAtom(output, ctxt->atoms[i]);
737 }
738 if (ctxt->atom != NULL) {
739 fprintf(output, "current atom:\n");
740 xmlRegPrintAtom(output, ctxt->atom);
741 }
742 fprintf(output, "%d states:", ctxt->nbStates);
743 if (ctxt->start != NULL)
744 fprintf(output, " start: %d", ctxt->start->no);
745 if (ctxt->end != NULL)
746 fprintf(output, " end: %d", ctxt->end->no);
747 fprintf(output, "\n");
748 for (i = 0;i < ctxt->nbStates; i++) {
749 xmlRegPrintState(output, ctxt->states[i]);
750 }
751 fprintf(output, "%d counters:\n", ctxt->nbCounters);
752 for (i = 0;i < ctxt->nbCounters; i++) {
753 fprintf(output, " %d: min %d max %d\n", i, ctxt->counters[i].min,
754 ctxt->counters[i].max);
755 }
756}
757#endif
758
759/************************************************************************
760 * *
761 * Finite Automata structures manipulations *
762 * *
763 ************************************************************************/
764
765static void
766xmlRegAtomAddRange(xmlRegParserCtxtPtr ctxt, xmlRegAtomPtr atom,
767 int neg, xmlRegAtomType type, int start, int end,
768 xmlChar *blockName) {
769 xmlRegRangePtr range;
770
771 if (atom == NULL) {
772 ERROR("add range: atom is NULL");
773 return;
774 }
775 if (atom->type != XML_REGEXP_RANGES) {
776 ERROR("add range: atom is not ranges");
777 return;
778 }
779 if (atom->maxRanges == 0) {
780 atom->maxRanges = 4;
781 atom->ranges = (xmlRegRangePtr *) xmlMalloc(atom->maxRanges *
782 sizeof(xmlRegRangePtr));
783 if (atom->ranges == NULL) {
784 ERROR("add range: allocation failed");
785 atom->maxRanges = 0;
786 return;
787 }
788 } else if (atom->nbRanges >= atom->maxRanges) {
789 xmlRegRangePtr *tmp;
790 atom->maxRanges *= 2;
791 tmp = (xmlRegRangePtr *) xmlRealloc(atom->ranges, atom->maxRanges *
792 sizeof(xmlRegRangePtr));
793 if (tmp == NULL) {
794 ERROR("add range: allocation failed");
795 atom->maxRanges /= 2;
796 return;
797 }
798 atom->ranges = tmp;
799 }
800 range = xmlRegNewRange(ctxt, neg, type, start, end);
801 if (range == NULL)
802 return;
803 range->blockName = blockName;
804 atom->ranges[atom->nbRanges++] = range;
805
806}
807
808static int
809xmlRegGetCounter(xmlRegParserCtxtPtr ctxt) {
810 if (ctxt->maxCounters == 0) {
811 ctxt->maxCounters = 4;
812 ctxt->counters = (xmlRegCounter *) xmlMalloc(ctxt->maxCounters *
813 sizeof(xmlRegCounter));
814 if (ctxt->counters == NULL) {
815 ERROR("reg counter: allocation failed");
816 ctxt->maxCounters = 0;
817 return(-1);
818 }
819 } else if (ctxt->nbCounters >= ctxt->maxCounters) {
820 xmlRegCounter *tmp;
821 ctxt->maxCounters *= 2;
822 tmp = (xmlRegCounter *) xmlRealloc(ctxt->counters, ctxt->maxCounters *
823 sizeof(xmlRegCounter));
824 if (tmp == NULL) {
825 ERROR("reg counter: allocation failed");
826 ctxt->maxCounters /= 2;
827 return(-1);
828 }
829 ctxt->counters = tmp;
830 }
831 ctxt->counters[ctxt->nbCounters].min = -1;
832 ctxt->counters[ctxt->nbCounters].max = -1;
833 return(ctxt->nbCounters++);
834}
835
836static void
837xmlRegAtomPush(xmlRegParserCtxtPtr ctxt, xmlRegAtomPtr atom) {
838 if (atom == NULL) {
839 ERROR("atom push: atom is NULL");
840 return;
841 }
842 if (ctxt->maxAtoms == 0) {
843 ctxt->maxAtoms = 4;
844 ctxt->atoms = (xmlRegAtomPtr *) xmlMalloc(ctxt->maxAtoms *
845 sizeof(xmlRegAtomPtr));
846 if (ctxt->atoms == NULL) {
847 ERROR("atom push: allocation failed");
848 ctxt->maxAtoms = 0;
849 return;
850 }
851 } else if (ctxt->nbAtoms >= ctxt->maxAtoms) {
852 xmlRegAtomPtr *tmp;
853 ctxt->maxAtoms *= 2;
854 tmp = (xmlRegAtomPtr *) xmlRealloc(ctxt->atoms, ctxt->maxAtoms *
855 sizeof(xmlRegAtomPtr));
856 if (tmp == NULL) {
857 ERROR("atom push: allocation failed");
858 ctxt->maxAtoms /= 2;
859 return;
860 }
861 ctxt->atoms = tmp;
862 }
863 atom->no = ctxt->nbAtoms;
864 ctxt->atoms[ctxt->nbAtoms++] = atom;
865}
866
867static void
868xmlRegStateAddTrans(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr state,
869 xmlRegAtomPtr atom, xmlRegStatePtr target,
870 int counter, int count) {
871 if (state == NULL) {
872 ERROR("add state: state is NULL");
873 return;
874 }
875 if (target == NULL) {
876 ERROR("add state: target is NULL");
877 return;
878 }
879 if (state->maxTrans == 0) {
880 state->maxTrans = 4;
881 state->trans = (xmlRegTrans *) xmlMalloc(state->maxTrans *
882 sizeof(xmlRegTrans));
883 if (state->trans == NULL) {
884 ERROR("add range: allocation failed");
885 state->maxTrans = 0;
886 return;
887 }
888 } else if (state->nbTrans >= state->maxTrans) {
889 xmlRegTrans *tmp;
890 state->maxTrans *= 2;
891 tmp = (xmlRegTrans *) xmlRealloc(state->trans, state->maxTrans *
892 sizeof(xmlRegTrans));
893 if (tmp == NULL) {
894 ERROR("add range: allocation failed");
895 state->maxTrans /= 2;
896 return;
897 }
898 state->trans = tmp;
899 }
900#ifdef DEBUG_REGEXP_GRAPH
901 printf("Add trans from %d to %d ", state->no, target->no);
902 if (count >= 0)
903 printf("count based %d", count);
904 else if (counter >= 0)
905 printf("counted %d", counter);
906 else if (atom == NULL)
907 printf("epsilon transition");
908 printf("\n");
909#endif
910
911 state->trans[state->nbTrans].atom = atom;
912 state->trans[state->nbTrans].to = target->no;
913 state->trans[state->nbTrans].counter = counter;
914 state->trans[state->nbTrans].count = count;
915 state->nbTrans++;
916}
917
918static void
919xmlRegStatePush(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr state) {
920 if (ctxt->maxStates == 0) {
921 ctxt->maxStates = 4;
922 ctxt->states = (xmlRegStatePtr *) xmlMalloc(ctxt->maxStates *
923 sizeof(xmlRegStatePtr));
924 if (ctxt->states == NULL) {
925 ERROR("add range: allocation failed");
926 ctxt->maxStates = 0;
927 return;
928 }
929 } else if (ctxt->nbStates >= ctxt->maxStates) {
930 xmlRegStatePtr *tmp;
931 ctxt->maxStates *= 2;
932 tmp = (xmlRegStatePtr *) xmlRealloc(ctxt->states, ctxt->maxStates *
933 sizeof(xmlRegStatePtr));
934 if (tmp == NULL) {
935 ERROR("add range: allocation failed");
936 ctxt->maxStates /= 2;
937 return;
938 }
939 ctxt->states = tmp;
940 }
941 state->no = ctxt->nbStates;
942 ctxt->states[ctxt->nbStates++] = state;
943}
944
945/**
946 * xmlFAGenerateEpsilonTransition:
947 * ctxt: a regexp parser context
948 * from: the from state
949 * to: the target state or NULL for building a new one
950 *
951 */
952static void
953xmlFAGenerateEpsilonTransition(xmlRegParserCtxtPtr ctxt,
954 xmlRegStatePtr from, xmlRegStatePtr to) {
955 if (to == NULL) {
956 to = xmlRegNewState(ctxt);
957 xmlRegStatePush(ctxt, to);
958 ctxt->state = to;
959 }
960 xmlRegStateAddTrans(ctxt, from, NULL, to, -1, -1);
961}
962
963/**
964 * xmlFAGenerateCountedEpsilonTransition:
965 * ctxt: a regexp parser context
966 * from: the from state
967 * to: the target state or NULL for building a new one
968 * counter: the counter for that transition
969 *
970 */
971static void
972xmlFAGenerateCountedEpsilonTransition(xmlRegParserCtxtPtr ctxt,
973 xmlRegStatePtr from, xmlRegStatePtr to, int counter) {
974 if (to == NULL) {
975 to = xmlRegNewState(ctxt);
976 xmlRegStatePush(ctxt, to);
977 ctxt->state = to;
978 }
979 xmlRegStateAddTrans(ctxt, from, NULL, to, counter, -1);
980}
981
982/**
983 * xmlFAGenerateCountedTransition:
984 * ctxt: a regexp parser context
985 * from: the from state
986 * to: the target state or NULL for building a new one
987 * counter: the counter for that transition
988 *
989 */
990static void
991xmlFAGenerateCountedTransition(xmlRegParserCtxtPtr ctxt,
992 xmlRegStatePtr from, xmlRegStatePtr to, int counter) {
993 if (to == NULL) {
994 to = xmlRegNewState(ctxt);
995 xmlRegStatePush(ctxt, to);
996 ctxt->state = to;
997 }
998 xmlRegStateAddTrans(ctxt, from, NULL, to, -1, counter);
999}
1000
1001/**
1002 * xmlFAGenerateTransitions:
1003 * ctxt: a regexp parser context
1004 * from: the from state
1005 * to: the target state or NULL for building a new one
1006 * atom: the atom generating the transition
1007 *
1008 */
1009static void
1010xmlFAGenerateTransitions(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr from,
1011 xmlRegStatePtr to, xmlRegAtomPtr atom) {
1012 if (atom == NULL) {
1013 ERROR("genrate transition: atom == NULL");
1014 return;
1015 }
1016 if (atom->type == XML_REGEXP_SUBREG) {
1017 /*
1018 * this is a subexpression handling one should not need to
1019 * create a new node excep for XML_REGEXP_QUANT_RANGE.
1020 */
1021 xmlRegAtomPush(ctxt, atom);
1022 if ((to != NULL) && (atom->stop != to) &&
1023 (atom->quant != XML_REGEXP_QUANT_RANGE)) {
1024 /*
1025 * Generate an epsilon transition to link to the target
1026 */
1027 xmlFAGenerateEpsilonTransition(ctxt, atom->stop, to);
1028 }
1029 switch (atom->quant) {
1030 case XML_REGEXP_QUANT_OPT:
1031 atom->quant = XML_REGEXP_QUANT_ONCE;
1032 xmlFAGenerateEpsilonTransition(ctxt, atom->start, atom->stop);
1033 break;
1034 case XML_REGEXP_QUANT_MULT:
1035 atom->quant = XML_REGEXP_QUANT_ONCE;
1036 xmlFAGenerateEpsilonTransition(ctxt, atom->start, atom->stop);
1037 xmlFAGenerateEpsilonTransition(ctxt, atom->stop, atom->start);
1038 break;
1039 case XML_REGEXP_QUANT_PLUS:
1040 atom->quant = XML_REGEXP_QUANT_ONCE;
1041 xmlFAGenerateEpsilonTransition(ctxt, atom->stop, atom->start);
1042 break;
1043 case XML_REGEXP_QUANT_RANGE: {
1044 int counter;
1045 xmlRegStatePtr newstate;
1046
1047 /*
1048 * This one is nasty:
1049 * 1/ register a new counter
1050 * 2/ register an epsilon transition associated to
1051 * this counter going from atom->stop to atom->start
1052 * 3/ create a new state
1053 * 4/ generate a counted transition from atom->stop to
1054 * that state
1055 */
1056 counter = xmlRegGetCounter(ctxt);
1057 ctxt->counters[counter].min = atom->min - 1;
1058 ctxt->counters[counter].max = atom->max - 1;
1059 atom->min = 0;
1060 atom->max = 0;
1061 atom->quant = XML_REGEXP_QUANT_ONCE;
1062 xmlFAGenerateCountedEpsilonTransition(ctxt, atom->stop,
1063 atom->start, counter);
1064 if (to != NULL) {
1065 newstate = to;
1066 } else {
1067 newstate = xmlRegNewState(ctxt);
1068 xmlRegStatePush(ctxt, newstate);
1069 ctxt->state = newstate;
1070 }
1071 xmlFAGenerateCountedTransition(ctxt, atom->stop,
1072 newstate, counter);
1073 }
1074 default:
1075 break;
1076 }
1077 return;
1078 } else {
1079 if (to == NULL) {
1080 to = xmlRegNewState(ctxt);
1081 xmlRegStatePush(ctxt, to);
1082 }
1083 xmlRegStateAddTrans(ctxt, from, atom, to, -1, -1);
1084 xmlRegAtomPush(ctxt, atom);
1085 ctxt->state = to;
1086 }
1087 switch (atom->quant) {
1088 case XML_REGEXP_QUANT_OPT:
1089 atom->quant = XML_REGEXP_QUANT_ONCE;
1090 xmlFAGenerateEpsilonTransition(ctxt, from, to);
1091 break;
1092 case XML_REGEXP_QUANT_MULT:
1093 atom->quant = XML_REGEXP_QUANT_ONCE;
1094 xmlFAGenerateEpsilonTransition(ctxt, from, to);
1095 xmlRegStateAddTrans(ctxt, to, atom, to, -1, -1);
1096 break;
1097 case XML_REGEXP_QUANT_PLUS:
1098 atom->quant = XML_REGEXP_QUANT_ONCE;
1099 xmlRegStateAddTrans(ctxt, to, atom, to, -1, -1);
1100 break;
1101 default:
1102 break;
1103 }
1104}
1105
1106/**
1107 * xmlFAReduceEpsilonTransitions:
1108 * ctxt: a regexp parser context
1109 * @fromnr: the from state
1110 * @tonr: the to state
1111 * @cpunter: should that transition be associted to a counted
1112 *
1113 */
1114static void
1115xmlFAReduceEpsilonTransitions(xmlRegParserCtxtPtr ctxt, int fromnr,
1116 int tonr, int counter) {
1117 int transnr;
1118 xmlRegStatePtr from;
1119 xmlRegStatePtr to;
1120
1121#ifdef DEBUG_REGEXP_GRAPH
1122 printf("xmlFAReduceEpsilonTransitions(%d, %d)\n", fromnr, tonr);
1123#endif
1124 from = ctxt->states[fromnr];
1125 if (from == NULL)
1126 return;
1127 to = ctxt->states[tonr];
1128 if (to == NULL)
1129 return;
1130 if ((to->mark == XML_REGEXP_MARK_START) ||
1131 (to->mark == XML_REGEXP_MARK_VISITED))
1132 return;
1133
1134 to->mark = XML_REGEXP_MARK_VISITED;
1135 if (to->type == XML_REGEXP_FINAL_STATE) {
1136#ifdef DEBUG_REGEXP_GRAPH
1137 printf("State %d is final, so %d becomes final\n", tonr, fromnr);
1138#endif
1139 from->type = XML_REGEXP_FINAL_STATE;
1140 }
1141 for (transnr = 0;transnr < to->nbTrans;transnr++) {
1142 if (to->trans[transnr].atom == NULL) {
1143 /*
1144 * Don't remove counted transitions
1145 * Don't loop either
1146 */
1147 if ((to->trans[transnr].count < 0) &&
1148 (to->trans[transnr].to != fromnr)) {
1149#ifdef DEBUG_REGEXP_GRAPH
1150 printf("Found epsilon trans %d from %d to %d\n",
1151 transnr, tonr, to->trans[transnr].to);
1152#endif
1153 xmlFAReduceEpsilonTransitions(ctxt, fromnr,
1154 to->trans[transnr].to, counter);
1155 }
1156 } else {
1157 int newto = to->trans[transnr].to;
1158
1159 xmlRegStateAddTrans(ctxt, from, to->trans[transnr].atom,
1160 ctxt->states[newto], counter, -1);
1161 }
1162 }
1163 to->mark = XML_REGEXP_MARK_NORMAL;
1164}
1165
1166/**
1167 * xmlFAEliminateEpsilonTransitions:
1168 * ctxt: a regexp parser context
1169 *
1170 */
1171static void
1172xmlFAEliminateEpsilonTransitions(xmlRegParserCtxtPtr ctxt) {
1173 int statenr, transnr;
1174 xmlRegStatePtr state;
1175
1176 /*
1177 * build the completed transitions bypassing the epsilons
1178 * Use a marking algorithm to avoid loops
1179 */
1180 for (statenr = 0;statenr < ctxt->nbStates;statenr++) {
1181 state = ctxt->states[statenr];
1182 if (state == NULL)
1183 continue;
1184 for (transnr = 0;transnr < state->nbTrans;transnr++) {
1185 if ((state->trans[transnr].atom == NULL) &&
1186 (state->trans[transnr].to >= 0)) {
1187 if (state->trans[transnr].to == statenr) {
1188 state->trans[transnr].to = -1;
1189#ifdef DEBUG_REGEXP_GRAPH
1190 printf("Removed loopback epsilon trans %d on %d\n",
1191 transnr, statenr);
1192#endif
1193 } else if (state->trans[transnr].count < 0) {
1194 int newto = state->trans[transnr].to;
1195
1196#ifdef DEBUG_REGEXP_GRAPH
1197 printf("Found epsilon trans %d from %d to %d\n",
1198 transnr, statenr, newto);
1199#endif
1200 state->mark = XML_REGEXP_MARK_START;
1201 xmlFAReduceEpsilonTransitions(ctxt, statenr,
1202 newto, state->trans[transnr].counter);
1203 state->mark = XML_REGEXP_MARK_NORMAL;
1204#ifdef DEBUG_REGEXP_GRAPH
1205 } else {
1206 printf("Found counted transition %d on %d\n",
1207 transnr, statenr);
1208#endif
1209 }
1210 }
1211 }
1212 }
1213 /*
1214 * Eliminate the epsilon transitions
1215 */
1216 for (statenr = 0;statenr < ctxt->nbStates;statenr++) {
1217 state = ctxt->states[statenr];
1218 if (state == NULL)
1219 continue;
1220 for (transnr = 0;transnr < state->nbTrans;transnr++) {
1221 if ((state->trans[transnr].atom == NULL) &&
1222 (state->trans[transnr].count < 0) &&
1223 (state->trans[transnr].to >= 0)) {
1224 state->trans[transnr].to = -1;
1225 }
1226 }
1227 }
1228}
1229
1230/************************************************************************
1231 * *
1232 * Routines to check input against transition atoms *
1233 * *
1234 ************************************************************************/
1235
1236static int
1237xmlRegCheckCharacterRange(xmlRegAtomType type, int codepoint, int neg,
1238 int start, int end, const xmlChar *blockName) {
1239 int ret = 0;
1240
1241 switch (type) {
1242 case XML_REGEXP_STRING:
1243 case XML_REGEXP_SUBREG:
1244 case XML_REGEXP_RANGES:
1245 case XML_REGEXP_EPSILON:
1246 return(-1);
1247 case XML_REGEXP_ANYCHAR:
1248 ret = ((codepoint != '\n') && (codepoint != '\r'));
1249 break;
1250 case XML_REGEXP_CHARVAL:
1251 ret = ((codepoint >= start) && (codepoint <= end));
1252 break;
1253 case XML_REGEXP_NOTSPACE:
1254 neg = !neg;
1255 case XML_REGEXP_ANYSPACE:
1256 ret = ((codepoint == '\n') || (codepoint == '\r') ||
1257 (codepoint == '\t') || (codepoint == ' '));
1258 break;
1259 case XML_REGEXP_NOTINITNAME:
1260 neg = !neg;
1261 case XML_REGEXP_INITNAME:
1262 ret = (xmlIsLetter(codepoint) ||
1263 (codepoint == '_') || (codepoint == ':'));
1264 break;
1265 case XML_REGEXP_NOTNAMECHAR:
1266 neg = !neg;
1267 case XML_REGEXP_NAMECHAR:
1268 ret = (xmlIsLetter(codepoint) || xmlIsDigit(codepoint) ||
1269 (codepoint == '.') || (codepoint == '-') ||
1270 (codepoint == '_') || (codepoint == ':') ||
1271 xmlIsCombining(codepoint) || xmlIsExtender(codepoint));
1272 break;
1273 case XML_REGEXP_NOTDECIMAL:
1274 neg = !neg;
1275 case XML_REGEXP_DECIMAL:
1276 ret = xmlUCSIsCatNd(codepoint);
1277 break;
1278 case XML_REGEXP_REALCHAR:
1279 neg = !neg;
1280 case XML_REGEXP_NOTREALCHAR:
1281 ret = xmlUCSIsCatP(codepoint);
1282 if (ret == 0)
1283 ret = xmlUCSIsCatZ(codepoint);
1284 if (ret == 0)
1285 ret = xmlUCSIsCatC(codepoint);
1286 break;
1287 case XML_REGEXP_LETTER:
1288 ret = xmlUCSIsCatL(codepoint);
1289 break;
1290 case XML_REGEXP_LETTER_UPPERCASE:
1291 ret = xmlUCSIsCatLu(codepoint);
1292 break;
1293 case XML_REGEXP_LETTER_LOWERCASE:
1294 ret = xmlUCSIsCatLl(codepoint);
1295 break;
1296 case XML_REGEXP_LETTER_TITLECASE:
1297 ret = xmlUCSIsCatLt(codepoint);
1298 break;
1299 case XML_REGEXP_LETTER_MODIFIER:
1300 ret = xmlUCSIsCatLm(codepoint);
1301 break;
1302 case XML_REGEXP_LETTER_OTHERS:
1303 ret = xmlUCSIsCatLo(codepoint);
1304 break;
1305 case XML_REGEXP_MARK:
1306 ret = xmlUCSIsCatM(codepoint);
1307 break;
1308 case XML_REGEXP_MARK_NONSPACING:
1309 ret = xmlUCSIsCatMn(codepoint);
1310 break;
1311 case XML_REGEXP_MARK_SPACECOMBINING:
1312 ret = xmlUCSIsCatMc(codepoint);
1313 break;
1314 case XML_REGEXP_MARK_ENCLOSING:
1315 ret = xmlUCSIsCatMe(codepoint);
1316 break;
1317 case XML_REGEXP_NUMBER:
1318 ret = xmlUCSIsCatN(codepoint);
1319 break;
1320 case XML_REGEXP_NUMBER_DECIMAL:
1321 ret = xmlUCSIsCatNd(codepoint);
1322 break;
1323 case XML_REGEXP_NUMBER_LETTER:
1324 ret = xmlUCSIsCatNl(codepoint);
1325 break;
1326 case XML_REGEXP_NUMBER_OTHERS:
1327 ret = xmlUCSIsCatNo(codepoint);
1328 break;
1329 case XML_REGEXP_PUNCT:
1330 ret = xmlUCSIsCatP(codepoint);
1331 break;
1332 case XML_REGEXP_PUNCT_CONNECTOR:
1333 ret = xmlUCSIsCatPc(codepoint);
1334 break;
1335 case XML_REGEXP_PUNCT_DASH:
1336 ret = xmlUCSIsCatPd(codepoint);
1337 break;
1338 case XML_REGEXP_PUNCT_OPEN:
1339 ret = xmlUCSIsCatPs(codepoint);
1340 break;
1341 case XML_REGEXP_PUNCT_CLOSE:
1342 ret = xmlUCSIsCatPe(codepoint);
1343 break;
1344 case XML_REGEXP_PUNCT_INITQUOTE:
1345 ret = xmlUCSIsCatPi(codepoint);
1346 break;
1347 case XML_REGEXP_PUNCT_FINQUOTE:
1348 ret = xmlUCSIsCatPf(codepoint);
1349 break;
1350 case XML_REGEXP_PUNCT_OTHERS:
1351 ret = xmlUCSIsCatPo(codepoint);
1352 break;
1353 case XML_REGEXP_SEPAR:
1354 ret = xmlUCSIsCatZ(codepoint);
1355 break;
1356 case XML_REGEXP_SEPAR_SPACE:
1357 ret = xmlUCSIsCatZs(codepoint);
1358 break;
1359 case XML_REGEXP_SEPAR_LINE:
1360 ret = xmlUCSIsCatZl(codepoint);
1361 break;
1362 case XML_REGEXP_SEPAR_PARA:
1363 ret = xmlUCSIsCatZp(codepoint);
1364 break;
1365 case XML_REGEXP_SYMBOL:
1366 ret = xmlUCSIsCatS(codepoint);
1367 break;
1368 case XML_REGEXP_SYMBOL_MATH:
1369 ret = xmlUCSIsCatSm(codepoint);
1370 break;
1371 case XML_REGEXP_SYMBOL_CURRENCY:
1372 ret = xmlUCSIsCatSc(codepoint);
1373 break;
1374 case XML_REGEXP_SYMBOL_MODIFIER:
1375 ret = xmlUCSIsCatSk(codepoint);
1376 break;
1377 case XML_REGEXP_SYMBOL_OTHERS:
1378 ret = xmlUCSIsCatSo(codepoint);
1379 break;
1380 case XML_REGEXP_OTHER:
1381 ret = xmlUCSIsCatC(codepoint);
1382 break;
1383 case XML_REGEXP_OTHER_CONTROL:
1384 ret = xmlUCSIsCatCc(codepoint);
1385 break;
1386 case XML_REGEXP_OTHER_FORMAT:
1387 ret = xmlUCSIsCatCf(codepoint);
1388 break;
1389 case XML_REGEXP_OTHER_PRIVATE:
1390 ret = xmlUCSIsCatCo(codepoint);
1391 break;
1392 case XML_REGEXP_OTHER_NA:
1393 /* ret = xmlUCSIsCatCn(codepoint); */
1394 /* Seems it doesn't exist anymore in recent Unicode releases */
1395 ret = 0;
1396 break;
1397 case XML_REGEXP_BLOCK_NAME:
1398 ret = xmlUCSIsBlock(codepoint, (const char *) blockName);
1399 break;
1400 }
1401 if (neg)
1402 return(!ret);
1403 return(ret);
1404}
1405
1406static int
1407xmlRegCheckCharacter(xmlRegAtomPtr atom, int codepoint) {
1408 int i, ret = 0;
1409 xmlRegRangePtr range;
1410
1411 if ((atom == NULL) || (!xmlIsChar(codepoint)))
1412 return(-1);
1413
1414 switch (atom->type) {
1415 case XML_REGEXP_SUBREG:
1416 case XML_REGEXP_EPSILON:
1417 return(-1);
1418 case XML_REGEXP_CHARVAL:
1419 return(codepoint == atom->codepoint);
1420 case XML_REGEXP_RANGES: {
1421 int accept = 0;
1422 for (i = 0;i < atom->nbRanges;i++) {
1423 range = atom->ranges[i];
1424 if (range->neg) {
1425 ret = xmlRegCheckCharacterRange(range->type, codepoint,
1426 0, range->start, range->end,
1427 range->blockName);
1428 if (ret != 0)
1429 return(0); /* excluded char */
1430 } else {
1431 ret = xmlRegCheckCharacterRange(range->type, codepoint,
1432 0, range->start, range->end,
1433 range->blockName);
1434 if (ret != 0)
1435 accept = 1; /* might still be excluded */
1436 }
1437 }
1438 return(accept);
1439 }
1440 case XML_REGEXP_STRING:
1441 printf("TODO: XML_REGEXP_STRING\n");
1442 return(-1);
1443 case XML_REGEXP_ANYCHAR:
1444 case XML_REGEXP_ANYSPACE:
1445 case XML_REGEXP_NOTSPACE:
1446 case XML_REGEXP_INITNAME:
1447 case XML_REGEXP_NOTINITNAME:
1448 case XML_REGEXP_NAMECHAR:
1449 case XML_REGEXP_NOTNAMECHAR:
1450 case XML_REGEXP_DECIMAL:
1451 case XML_REGEXP_NOTDECIMAL:
1452 case XML_REGEXP_REALCHAR:
1453 case XML_REGEXP_NOTREALCHAR:
1454 case XML_REGEXP_LETTER:
1455 case XML_REGEXP_LETTER_UPPERCASE:
1456 case XML_REGEXP_LETTER_LOWERCASE:
1457 case XML_REGEXP_LETTER_TITLECASE:
1458 case XML_REGEXP_LETTER_MODIFIER:
1459 case XML_REGEXP_LETTER_OTHERS:
1460 case XML_REGEXP_MARK:
1461 case XML_REGEXP_MARK_NONSPACING:
1462 case XML_REGEXP_MARK_SPACECOMBINING:
1463 case XML_REGEXP_MARK_ENCLOSING:
1464 case XML_REGEXP_NUMBER:
1465 case XML_REGEXP_NUMBER_DECIMAL:
1466 case XML_REGEXP_NUMBER_LETTER:
1467 case XML_REGEXP_NUMBER_OTHERS:
1468 case XML_REGEXP_PUNCT:
1469 case XML_REGEXP_PUNCT_CONNECTOR:
1470 case XML_REGEXP_PUNCT_DASH:
1471 case XML_REGEXP_PUNCT_OPEN:
1472 case XML_REGEXP_PUNCT_CLOSE:
1473 case XML_REGEXP_PUNCT_INITQUOTE:
1474 case XML_REGEXP_PUNCT_FINQUOTE:
1475 case XML_REGEXP_PUNCT_OTHERS:
1476 case XML_REGEXP_SEPAR:
1477 case XML_REGEXP_SEPAR_SPACE:
1478 case XML_REGEXP_SEPAR_LINE:
1479 case XML_REGEXP_SEPAR_PARA:
1480 case XML_REGEXP_SYMBOL:
1481 case XML_REGEXP_SYMBOL_MATH:
1482 case XML_REGEXP_SYMBOL_CURRENCY:
1483 case XML_REGEXP_SYMBOL_MODIFIER:
1484 case XML_REGEXP_SYMBOL_OTHERS:
1485 case XML_REGEXP_OTHER:
1486 case XML_REGEXP_OTHER_CONTROL:
1487 case XML_REGEXP_OTHER_FORMAT:
1488 case XML_REGEXP_OTHER_PRIVATE:
1489 case XML_REGEXP_OTHER_NA:
1490 case XML_REGEXP_BLOCK_NAME:
1491 ret = xmlRegCheckCharacterRange(atom->type, codepoint, 0, 0, 0,
1492 (const xmlChar *)atom->valuep);
1493 if (atom->neg)
1494 ret = !ret;
1495 break;
1496 }
1497 return(ret);
1498}
1499
1500/************************************************************************
1501 * *
1502 * Saving an restoring state of an execution context *
1503 * *
1504 ************************************************************************/
1505
1506#ifdef DEBUG_REGEXP_EXEC
1507static void
1508xmlFARegDebugExec(xmlRegExecCtxtPtr exec) {
1509 printf("state: %d:%d:idx %d", exec->state->no, exec->transno, exec->index);
1510 if (exec->inputStack != NULL) {
1511 int i;
1512 printf(": ");
1513 for (i = 0;(i < 3) && (i < exec->inputStackNr);i++)
1514 printf("%s ", exec->inputStack[exec->inputStackNr - (i + 1)]);
1515 } else {
1516 printf(": %s", &(exec->inputString[exec->index]));
1517 }
1518 printf("\n");
1519}
1520#endif
1521
1522static void
1523xmlFARegExecSave(xmlRegExecCtxtPtr exec) {
1524#ifdef DEBUG_REGEXP_EXEC
1525 printf("saving ");
1526 exec->transno++;
1527 xmlFARegDebugExec(exec);
1528 exec->transno--;
1529#endif
1530
1531 if (exec->maxRollbacks == 0) {
1532 exec->maxRollbacks = 4;
1533 exec->rollbacks = (xmlRegExecRollback *) xmlMalloc(exec->maxRollbacks *
1534 sizeof(xmlRegExecRollback));
1535 if (exec->rollbacks == NULL) {
1536 fprintf(stderr, "exec save: allocation failed");
1537 exec->maxRollbacks = 0;
1538 return;
1539 }
1540 memset(exec->rollbacks, 0,
1541 exec->maxRollbacks * sizeof(xmlRegExecRollback));
1542 } else if (exec->nbRollbacks >= exec->maxRollbacks) {
1543 xmlRegExecRollback *tmp;
1544 int len = exec->maxRollbacks;
1545
1546 exec->maxRollbacks *= 2;
1547 tmp = (xmlRegExecRollback *) xmlRealloc(exec->rollbacks,
1548 exec->maxRollbacks * sizeof(xmlRegExecRollback));
1549 if (tmp == NULL) {
1550 fprintf(stderr, "exec save: allocation failed");
1551 exec->maxRollbacks /= 2;
1552 return;
1553 }
1554 exec->rollbacks = tmp;
1555 tmp = &exec->rollbacks[len];
1556 memset(tmp, 0, (exec->maxRollbacks - len) * sizeof(xmlRegExecRollback));
1557 }
1558 exec->rollbacks[exec->nbRollbacks].state = exec->state;
1559 exec->rollbacks[exec->nbRollbacks].index = exec->index;
1560 exec->rollbacks[exec->nbRollbacks].nextbranch = exec->transno + 1;
1561 if (exec->comp->nbCounters > 0) {
1562 if (exec->rollbacks[exec->nbRollbacks].counts == NULL) {
1563 exec->rollbacks[exec->nbRollbacks].counts = (int *)
1564 xmlMalloc(exec->comp->nbCounters * sizeof(int));
1565 if (exec->rollbacks[exec->nbRollbacks].counts == NULL) {
1566 fprintf(stderr, "exec save: allocation failed");
1567 exec->status = -5;
1568 return;
1569 }
1570 }
1571 memcpy(exec->rollbacks[exec->nbRollbacks].counts, exec->counts,
1572 exec->comp->nbCounters * sizeof(int));
1573 }
1574 exec->nbRollbacks++;
1575}
1576
1577static void
1578xmlFARegExecRollBack(xmlRegExecCtxtPtr exec) {
1579 if (exec->nbRollbacks <= 0) {
1580 exec->status = -1;
1581#ifdef DEBUG_REGEXP_EXEC
1582 printf("rollback failed on empty stack\n");
1583#endif
1584 return;
1585 }
1586 exec->nbRollbacks--;
1587 exec->state = exec->rollbacks[exec->nbRollbacks].state;
1588 exec->index = exec->rollbacks[exec->nbRollbacks].index;
1589 exec->transno = exec->rollbacks[exec->nbRollbacks].nextbranch;
1590 if (exec->comp->nbCounters > 0) {
1591 if (exec->rollbacks[exec->nbRollbacks].counts == NULL) {
1592 fprintf(stderr, "exec save: allocation failed");
1593 exec->status = -6;
1594 return;
1595 }
1596 memcpy(exec->counts, exec->rollbacks[exec->nbRollbacks].counts,
1597 exec->comp->nbCounters * sizeof(int));
1598 }
1599
1600#ifdef DEBUG_REGEXP_EXEC
1601 printf("restored ");
1602 xmlFARegDebugExec(exec);
1603#endif
1604}
1605
1606/************************************************************************
1607 * *
1608 * Verifyer, running an input against a compiled regexp *
1609 * *
1610 ************************************************************************/
1611
1612static int
1613xmlFARegExec(xmlRegexpPtr comp, const xmlChar *content) {
1614 xmlRegExecCtxt execval;
1615 xmlRegExecCtxtPtr exec = &execval;
1616 int ret, codepoint, len;
1617
1618 exec->inputString = content;
1619 exec->index = 0;
1620 exec->determinist = 1;
1621 exec->maxRollbacks = 0;
1622 exec->nbRollbacks = 0;
1623 exec->rollbacks = NULL;
1624 exec->status = 0;
1625 exec->comp = comp;
1626 exec->state = comp->states[0];
1627 exec->transno = 0;
1628 exec->transcount = 0;
1629 if (comp->nbCounters > 0) {
1630 exec->counts = (int *) xmlMalloc(comp->nbCounters * sizeof(int));
1631 if (exec->counts == NULL)
1632 return(-1);
1633 memset(exec->counts, 0, comp->nbCounters * sizeof(int));
1634 } else
1635 exec->counts = NULL;
1636 while ((exec->status == 0) &&
1637 ((exec->inputString[exec->index] != 0) ||
1638 (exec->state->type != XML_REGEXP_FINAL_STATE))) {
1639 xmlRegTransPtr trans;
1640 xmlRegAtomPtr atom;
1641
1642 /*
1643 * End of input on non-terminal state, rollback, however we may
1644 * still have epsilon like transition for counted transitions
1645 * on counters, in that case don't break too early.
1646 */
1647 if ((exec->inputString[exec->index] == 0) && (exec->counts == NULL))
1648 goto rollback;
1649
1650 exec->transcount = 0;
1651 for (;exec->transno < exec->state->nbTrans;exec->transno++) {
1652 trans = &exec->state->trans[exec->transno];
1653 if (trans->to < 0)
1654 continue;
1655 atom = trans->atom;
1656 ret = 0;
1657 if (trans->count >= 0) {
1658 int count;
1659 xmlRegCounterPtr counter;
1660
1661 /*
1662 * A counted transition.
1663 */
1664
1665 count = exec->counts[trans->count];
1666 counter = &exec->comp->counters[trans->count];
1667#ifdef DEBUG_REGEXP_EXEC
1668 printf("testing count %d: val %d, min %d, max %d\n",
1669 trans->count, count, counter->min, counter->max);
1670#endif
1671 ret = ((count >= counter->min) && (count <= counter->max));
1672 } else if (atom == NULL) {
1673 fprintf(stderr, "epsilon transition left at runtime\n");
1674 exec->status = -2;
1675 break;
1676 } else if (exec->inputString[exec->index] != 0) {
1677 codepoint = CUR_SCHAR(&(exec->inputString[exec->index]), len);
1678 ret = xmlRegCheckCharacter(atom, codepoint);
1679 if ((ret == 1) && (atom->min > 0) && (atom->max > 0)) {
1680 xmlRegStatePtr to = comp->states[trans->to];
1681
1682 /*
1683 * this is a multiple input sequence
1684 */
1685 if (exec->state->nbTrans > exec->transno + 1) {
1686 xmlFARegExecSave(exec);
1687 }
1688 exec->transcount = 1;
1689 do {
1690 /*
1691 * Try to progress as much as possible on the input
1692 */
1693 if (exec->transcount == atom->max) {
1694 break;
1695 }
1696 exec->index += len;
1697 /*
1698 * End of input: stop here
1699 */
1700 if (exec->inputString[exec->index] == 0) {
1701 exec->index -= len;
1702 break;
1703 }
1704 if (exec->transcount >= atom->min) {
1705 int transno = exec->transno;
1706 xmlRegStatePtr state = exec->state;
1707
1708 /*
1709 * The transition is acceptable save it
1710 */
1711 exec->transno = -1; /* trick */
1712 exec->state = to;
1713 xmlFARegExecSave(exec);
1714 exec->transno = transno;
1715 exec->state = state;
1716 }
1717 codepoint = CUR_SCHAR(&(exec->inputString[exec->index]),
1718 len);
1719 ret = xmlRegCheckCharacter(atom, codepoint);
1720 exec->transcount++;
1721 } while (ret == 1);
1722 if (exec->transcount < atom->min)
1723 ret = 0;
1724
1725 /*
1726 * If the last check failed but one transition was found
1727 * possible, rollback
1728 */
1729 if (ret < 0)
1730 ret = 0;
1731 if (ret == 0) {
1732 goto rollback;
1733 }
1734 }
1735 }
1736 if (ret == 1) {
1737 if (exec->state->nbTrans > exec->transno + 1) {
1738 xmlFARegExecSave(exec);
1739 }
1740 if (trans->counter >= 0) {
1741#ifdef DEBUG_REGEXP_EXEC
1742 printf("Increasing count %d\n", trans->counter);
1743#endif
1744 exec->counts[trans->counter]++;
1745 }
1746#ifdef DEBUG_REGEXP_EXEC
1747 printf("entering state %d\n", trans->to);
1748#endif
1749 exec->state = comp->states[trans->to];
1750 exec->transno = 0;
1751 if (trans->atom != NULL) {
1752 exec->index += len;
1753 }
1754 goto progress;
1755 } else if (ret < 0) {
1756 exec->status = -4;
1757 break;
1758 }
1759 }
1760 if ((exec->transno != 0) || (exec->state->nbTrans == 0)) {
1761rollback:
1762 /*
1763 * Failed to find a way out
1764 */
1765 exec->determinist = 0;
1766 xmlFARegExecRollBack(exec);
1767 }
1768progress:
1769 continue;
1770 }
1771 if (exec->rollbacks != NULL) {
1772 if (exec->counts != NULL) {
1773 int i;
1774
1775 for (i = 0;i < exec->maxRollbacks;i++)
1776 if (exec->rollbacks[i].counts != NULL)
1777 xmlFree(exec->rollbacks[i].counts);
1778 }
1779 xmlFree(exec->rollbacks);
1780 }
1781 if (exec->counts != NULL)
1782 xmlFree(exec->counts);
1783 if (exec->status == 0)
1784 return(1);
1785 if (exec->status == -1)
1786 return(0);
1787 return(exec->status);
1788}
1789
1790/************************************************************************
1791 * *
1792 * Progressive interface to the verifyer one atom at a time *
1793 * *
1794 ************************************************************************/
1795
1796/**
1797 * xmlRegExecCtxtPtr:
1798 * @comp: a precompiled regular expression
1799 * @callback: a callback function used for handling progresses in the
1800 * automata matching phase
1801 * @data: the context data associated to the callback in this context
1802 *
1803 * Build a context used for progressive evaluation of a regexp.
1804 */
1805xmlRegExecCtxtPtr
1806xmlRegNewExecCtxt(xmlRegexpPtr comp, xmlRegExecCallbacks callback, void *data) {
1807 xmlRegExecCtxtPtr exec;
1808
1809 if (comp == NULL)
1810 return(NULL);
1811 exec = (xmlRegExecCtxtPtr) xmlMalloc(sizeof(xmlRegExecCtxt));
1812 if (exec == NULL) {
1813 return(NULL);
1814 }
1815 memset(exec, 0, sizeof(xmlRegExecCtxt));
1816 exec->inputString = NULL;
1817 exec->index = 0;
1818 exec->determinist = 1;
1819 exec->maxRollbacks = 0;
1820 exec->nbRollbacks = 0;
1821 exec->rollbacks = NULL;
1822 exec->status = 0;
1823 exec->comp = comp;
1824 exec->state = comp->states[0];
1825 exec->transno = 0;
1826 exec->transcount = 0;
1827 exec->callback = callback;
1828 exec->data = data;
1829 if (comp->nbCounters > 0) {
1830 exec->counts = (int *) xmlMalloc(comp->nbCounters * sizeof(int));
1831 if (exec->counts == NULL) {
1832 xmlFree(exec);
1833 return(NULL);
1834 }
1835 memset(exec->counts, 0, comp->nbCounters * sizeof(int));
1836 } else
1837 exec->counts = NULL;
1838 exec->inputStackMax = 0;
1839 exec->inputStackNr = 0;
1840 exec->inputStack = NULL;
1841 return(exec);
1842}
1843
1844/**
1845 * xmlRegFreeExecCtxt:
1846 * @exec: a regular expression evaulation context
1847 *
1848 * Free the structures associated to a regular expression evaulation context.
1849 */
1850void
1851xmlRegFreeExecCtxt(xmlRegExecCtxtPtr exec) {
1852 if (exec == NULL)
1853 return;
1854
1855 if (exec->rollbacks != NULL) {
1856 if (exec->counts != NULL) {
1857 int i;
1858
1859 for (i = 0;i < exec->maxRollbacks;i++)
1860 if (exec->rollbacks[i].counts != NULL)
1861 xmlFree(exec->rollbacks[i].counts);
1862 }
1863 xmlFree(exec->rollbacks);
1864 }
1865 if (exec->counts != NULL)
1866 xmlFree(exec->counts);
1867 if (exec->inputStack != NULL) {
1868 int i;
1869
1870 for (i = 0;i < exec->inputStackNr;i++)
1871 xmlFree(exec->inputStack[i].value);
1872 xmlFree(exec->inputStack);
1873 }
1874 xmlFree(exec);
1875}
1876
1877static void
1878xmlFARegExecSaveInputString(xmlRegExecCtxtPtr exec, const xmlChar *value,
1879 void *data) {
1880#ifdef DEBUG_PUSH
1881 printf("saving value: %d:%s\n", exec->inputStackNr, value);
1882#endif
1883 if (exec->inputStackMax == 0) {
1884 exec->inputStackMax = 4;
1885 exec->inputStack = (xmlRegInputTokenPtr)
1886 xmlMalloc(exec->inputStackMax * sizeof(xmlRegInputToken));
1887 if (exec->inputStack == NULL) {
1888 fprintf(stderr, "push input: allocation failed");
1889 exec->inputStackMax = 0;
1890 return;
1891 }
1892 } else if (exec->inputStackNr + 1 >= exec->inputStackMax) {
1893 xmlRegInputTokenPtr tmp;
1894
1895 exec->inputStackMax *= 2;
1896 tmp = (xmlRegInputTokenPtr) xmlRealloc(exec->inputStack,
1897 exec->inputStackMax * sizeof(xmlRegInputToken));
1898 if (tmp == NULL) {
1899 fprintf(stderr, "push input: allocation failed");
1900 exec->inputStackMax /= 2;
1901 return;
1902 }
1903 exec->inputStack = tmp;
1904 }
1905 exec->inputStack[exec->inputStackNr].value = xmlStrdup(value);
1906 exec->inputStack[exec->inputStackNr].data = data;
1907 exec->inputStackNr++;
1908 exec->inputStack[exec->inputStackNr].value = NULL;
1909 exec->inputStack[exec->inputStackNr].data = NULL;
1910}
1911
1912
1913/**
1914 * xmlRegExecPushString:
1915 * @exec: a regexp execution context
1916 * @value: a string token input
1917 * @data: data associated to the token to reuse in callbacks
1918 *
1919 * Push one input token in the execution context
1920 *
1921 * Returns: 1 if the regexp reached a final state, 0 if non-final, and
1922 * a negative value in case of error.
1923 */
1924int
1925xmlRegExecPushString(xmlRegExecCtxtPtr exec, const xmlChar *value,
1926 void *data) {
1927 xmlRegTransPtr trans;
1928 xmlRegAtomPtr atom;
1929 int ret;
1930 int final = 0;
1931
1932 if (exec == NULL)
1933 return(-1);
1934 if (exec->status != 0)
1935 return(exec->status);
1936
1937 if (value == NULL) {
1938 if (exec->state->type == XML_REGEXP_FINAL_STATE)
1939 return(1);
1940 final = 1;
1941 }
1942
1943#ifdef DEBUG_PUSH
1944 printf("value pushed: %s\n", value);
1945#endif
1946 /*
1947 * If we have an active rollback stack push the new value there
1948 * and get back to where we were left
1949 */
1950 if ((value != NULL) && (exec->inputStackNr > 0)) {
1951 xmlFARegExecSaveInputString(exec, value, data);
1952 value = exec->inputStack[exec->index].value;
1953 data = exec->inputStack[exec->index].data;
1954#ifdef DEBUG_PUSH
1955 printf("value loaded: %s\n", value);
1956#endif
1957 }
1958
1959 while ((exec->status == 0) &&
1960 ((value != NULL) ||
1961 ((final == 1) &&
1962 (exec->state->type != XML_REGEXP_FINAL_STATE)))) {
1963
1964 /*
1965 * End of input on non-terminal state, rollback, however we may
1966 * still have epsilon like transition for counted transitions
1967 * on counters, in that case don't break too early.
1968 */
1969 if (value == NULL)
1970 goto rollback;
1971
1972 exec->transcount = 0;
1973 for (;exec->transno < exec->state->nbTrans;exec->transno++) {
1974 trans = &exec->state->trans[exec->transno];
1975 if (trans->to < 0)
1976 continue;
1977 atom = trans->atom;
1978 ret = 0;
1979 if (trans->count >= 0) {
1980 int count;
1981 xmlRegCounterPtr counter;
1982
1983 /*
1984 * A counted transition.
1985 */
1986
1987 count = exec->counts[trans->count];
1988 counter = &exec->comp->counters[trans->count];
1989#ifdef DEBUG_PUSH
1990 printf("testing count %d: val %d, min %d, max %d\n",
1991 trans->count, count, counter->min, counter->max);
1992#endif
1993 ret = ((count >= counter->min) && (count <= counter->max));
1994 } else if (atom == NULL) {
1995 fprintf(stderr, "epsilon transition left at runtime\n");
1996 exec->status = -2;
1997 break;
1998 } else if (value != NULL) {
1999 ret = xmlStrEqual(value, atom->valuep);
2000 if ((ret == 1) && (atom->min > 0) && (atom->max > 0)) {
2001 xmlRegStatePtr to = exec->comp->states[trans->to];
2002
2003 /*
2004 * this is a multiple input sequence
2005 */
2006 if (exec->state->nbTrans > exec->transno + 1) {
2007 if (exec->inputStackNr <= 0) {
2008 xmlFARegExecSaveInputString(exec, value, data);
2009 }
2010 xmlFARegExecSave(exec);
2011 }
2012 exec->transcount = 1;
2013 do {
2014 /*
2015 * Try to progress as much as possible on the input
2016 */
2017 if (exec->transcount == atom->max) {
2018 break;
2019 }
2020 exec->index++;
2021 value = exec->inputStack[exec->index].value;
2022 data = exec->inputStack[exec->index].data;
2023#ifdef DEBUG_PUSH
2024 printf("value loaded: %s\n", value);
2025#endif
2026
2027 /*
2028 * End of input: stop here
2029 */
2030 if (value == NULL) {
2031 exec->index --;
2032 break;
2033 }
2034 if (exec->transcount >= atom->min) {
2035 int transno = exec->transno;
2036 xmlRegStatePtr state = exec->state;
2037
2038 /*
2039 * The transition is acceptable save it
2040 */
2041 exec->transno = -1; /* trick */
2042 exec->state = to;
2043 if (exec->inputStackNr <= 0) {
2044 xmlFARegExecSaveInputString(exec, value, data);
2045 }
2046 xmlFARegExecSave(exec);
2047 exec->transno = transno;
2048 exec->state = state;
2049 }
2050 ret = xmlStrEqual(value, atom->valuep);
2051 exec->transcount++;
2052 } while (ret == 1);
2053 if (exec->transcount < atom->min)
2054 ret = 0;
2055
2056 /*
2057 * If the last check failed but one transition was found
2058 * possible, rollback
2059 */
2060 if (ret < 0)
2061 ret = 0;
2062 if (ret == 0) {
2063 goto rollback;
2064 }
2065 }
2066 }
2067 if (ret == 1) {
2068 if ((exec->callback != NULL) && (atom != NULL)) {
2069 exec->callback(exec->data, atom->valuep,
2070 atom->data, data);
2071 }
2072 if (exec->state->nbTrans > exec->transno + 1) {
2073 if (exec->inputStackNr <= 0) {
2074 xmlFARegExecSaveInputString(exec, value, data);
2075 }
2076 xmlFARegExecSave(exec);
2077 }
2078 if (trans->counter >= 0) {
2079#ifdef DEBUG_PUSH
2080 printf("Increasing count %d\n", trans->counter);
2081#endif
2082 exec->counts[trans->counter]++;
2083 }
2084#ifdef DEBUG_PUSH
2085 printf("entering state %d\n", trans->to);
2086#endif
2087 exec->state = exec->comp->states[trans->to];
2088 exec->transno = 0;
2089 if (trans->atom != NULL) {
2090 if (exec->inputStack != NULL) {
2091 exec->index++;
2092 if (exec->index < exec->inputStackNr) {
2093 value = exec->inputStack[exec->index].value;
2094 data = exec->inputStack[exec->index].data;
2095#ifdef DEBUG_PUSH
2096 printf("value loaded: %s\n", value);
2097#endif
2098 } else {
2099 value = NULL;
2100 data = NULL;
2101#ifdef DEBUG_PUSH
2102 printf("end of input\n");
2103#endif
2104 }
2105 } else {
2106 value = NULL;
2107 data = NULL;
2108#ifdef DEBUG_PUSH
2109 printf("end of input\n");
2110#endif
2111 }
2112 }
2113 goto progress;
2114 } else if (ret < 0) {
2115 exec->status = -4;
2116 break;
2117 }
2118 }
2119 if ((exec->transno != 0) || (exec->state->nbTrans == 0)) {
2120rollback:
2121 /*
2122 * Failed to find a way out
2123 */
2124 exec->determinist = 0;
2125 xmlFARegExecRollBack(exec);
2126 if (exec->status == 0) {
2127 value = exec->inputStack[exec->index].value;
2128 data = exec->inputStack[exec->index].data;
2129#ifdef DEBUG_PUSH
2130 printf("value loaded: %s\n", value);
2131#endif
2132 }
2133 }
2134progress:
2135 continue;
2136 }
2137 if (exec->status == 0) {
2138 return(exec->state->type == XML_REGEXP_FINAL_STATE);
2139 }
2140 return(exec->status);
2141}
2142
2143#if 0
2144static int
2145xmlRegExecPushChar(xmlRegExecCtxtPtr exec, int UCS) {
2146 xmlRegTransPtr trans;
2147 xmlRegAtomPtr atom;
2148 int ret;
2149 int codepoint, len;
2150
2151 if (exec == NULL)
2152 return(-1);
2153 if (exec->status != 0)
2154 return(exec->status);
2155
2156 while ((exec->status == 0) &&
2157 ((exec->inputString[exec->index] != 0) ||
2158 (exec->state->type != XML_REGEXP_FINAL_STATE))) {
2159
2160 /*
2161 * End of input on non-terminal state, rollback, however we may
2162 * still have epsilon like transition for counted transitions
2163 * on counters, in that case don't break too early.
2164 */
2165 if ((exec->inputString[exec->index] == 0) && (exec->counts == NULL))
2166 goto rollback;
2167
2168 exec->transcount = 0;
2169 for (;exec->transno < exec->state->nbTrans;exec->transno++) {
2170 trans = &exec->state->trans[exec->transno];
2171 if (trans->to < 0)
2172 continue;
2173 atom = trans->atom;
2174 ret = 0;
2175 if (trans->count >= 0) {
2176 int count;
2177 xmlRegCounterPtr counter;
2178
2179 /*
2180 * A counted transition.
2181 */
2182
2183 count = exec->counts[trans->count];
2184 counter = &exec->comp->counters[trans->count];
2185#ifdef DEBUG_REGEXP_EXEC
2186 printf("testing count %d: val %d, min %d, max %d\n",
2187 trans->count, count, counter->min, counter->max);
2188#endif
2189 ret = ((count >= counter->min) && (count <= counter->max));
2190 } else if (atom == NULL) {
2191 fprintf(stderr, "epsilon transition left at runtime\n");
2192 exec->status = -2;
2193 break;
2194 } else if (exec->inputString[exec->index] != 0) {
2195 codepoint = CUR_SCHAR(&(exec->inputString[exec->index]), len);
2196 ret = xmlRegCheckCharacter(atom, codepoint);
2197 if ((ret == 1) && (atom->min > 0) && (atom->max > 0)) {
2198 xmlRegStatePtr to = exec->comp->states[trans->to];
2199
2200 /*
2201 * this is a multiple input sequence
2202 */
2203 if (exec->state->nbTrans > exec->transno + 1) {
2204 xmlFARegExecSave(exec);
2205 }
2206 exec->transcount = 1;
2207 do {
2208 /*
2209 * Try to progress as much as possible on the input
2210 */
2211 if (exec->transcount == atom->max) {
2212 break;
2213 }
2214 exec->index += len;
2215 /*
2216 * End of input: stop here
2217 */
2218 if (exec->inputString[exec->index] == 0) {
2219 exec->index -= len;
2220 break;
2221 }
2222 if (exec->transcount >= atom->min) {
2223 int transno = exec->transno;
2224 xmlRegStatePtr state = exec->state;
2225
2226 /*
2227 * The transition is acceptable save it
2228 */
2229 exec->transno = -1; /* trick */
2230 exec->state = to;
2231 xmlFARegExecSave(exec);
2232 exec->transno = transno;
2233 exec->state = state;
2234 }
2235 codepoint = CUR_SCHAR(&(exec->inputString[exec->index]),
2236 len);
2237 ret = xmlRegCheckCharacter(atom, codepoint);
2238 exec->transcount++;
2239 } while (ret == 1);
2240 if (exec->transcount < atom->min)
2241 ret = 0;
2242
2243 /*
2244 * If the last check failed but one transition was found
2245 * possible, rollback
2246 */
2247 if (ret < 0)
2248 ret = 0;
2249 if (ret == 0) {
2250 goto rollback;
2251 }
2252 }
2253 }
2254 if (ret == 1) {
2255 if (exec->state->nbTrans > exec->transno + 1) {
2256 xmlFARegExecSave(exec);
2257 }
2258 if (trans->counter >= 0) {
2259#ifdef DEBUG_REGEXP_EXEC
2260 printf("Increasing count %d\n", trans->counter);
2261#endif
2262 exec->counts[trans->counter]++;
2263 }
2264#ifdef DEBUG_REGEXP_EXEC
2265 printf("entering state %d\n", trans->to);
2266#endif
2267 exec->state = exec->comp->states[trans->to];
2268 exec->transno = 0;
2269 if (trans->atom != NULL) {
2270 exec->index += len;
2271 }
2272 goto progress;
2273 } else if (ret < 0) {
2274 exec->status = -4;
2275 break;
2276 }
2277 }
2278 if ((exec->transno != 0) || (exec->state->nbTrans == 0)) {
2279rollback:
2280 /*
2281 * Failed to find a way out
2282 */
2283 exec->determinist = 0;
2284 xmlFARegExecRollBack(exec);
2285 }
2286progress:
2287 continue;
2288 }
2289}
2290#endif
2291/************************************************************************
2292 * *
2293 * Parser for the Shemas Datatype Regular Expressions *
2294 * http://www.w3.org/TR/2001/REC-xmlschema-2-20010502/#regexs *
2295 * *
2296 ************************************************************************/
2297
2298/**
2299 * xmlFAIsChar:
2300 * ctxt: a regexp parser context
2301 *
2302 * [10] Char ::= [^.\?*+()|#x5B#x5D]
2303 */
2304static int
2305xmlFAIsChar(xmlRegParserCtxtPtr ctxt) {
2306 int cur;
2307 int len;
2308
2309 cur = CUR_SCHAR(ctxt->cur, len);
2310 if ((cur == '.') || (cur == '\\') || (cur == '?') ||
2311 (cur == '*') || (cur == '+') || (cur == '(') ||
2312 (cur == ')') || (cur == '|') || (cur == 0x5B) ||
2313 (cur == 0x5D) || (cur == 0))
2314 return(-1);
2315 return(cur);
2316}
2317
2318/**
2319 * xmlFAParseCharProp:
2320 * ctxt: a regexp parser context
2321 *
2322 * [27] charProp ::= IsCategory | IsBlock
2323 * [28] IsCategory ::= Letters | Marks | Numbers | Punctuation |
2324 * Separators | Symbols | Others
2325 * [29] Letters ::= 'L' [ultmo]?
2326 * [30] Marks ::= 'M' [nce]?
2327 * [31] Numbers ::= 'N' [dlo]?
2328 * [32] Punctuation ::= 'P' [cdseifo]?
2329 * [33] Separators ::= 'Z' [slp]?
2330 * [34] Symbols ::= 'S' [mcko]?
2331 * [35] Others ::= 'C' [cfon]?
2332 * [36] IsBlock ::= 'Is' [a-zA-Z0-9#x2D]+
2333 */
2334static void
2335xmlFAParseCharProp(xmlRegParserCtxtPtr ctxt) {
2336 int cur;
2337 xmlRegAtomType type = 0;
2338 xmlChar *blockName = NULL;
2339
2340 cur = CUR;
2341 if (cur == 'L') {
2342 NEXT;
2343 cur = CUR;
2344 if (cur == 'u') {
2345 NEXT;
2346 type = XML_REGEXP_LETTER_UPPERCASE;
2347 } else if (cur == 'l') {
2348 NEXT;
2349 type = XML_REGEXP_LETTER_LOWERCASE;
2350 } else if (cur == 't') {
2351 NEXT;
2352 type = XML_REGEXP_LETTER_TITLECASE;
2353 } else if (cur == 'm') {
2354 NEXT;
2355 type = XML_REGEXP_LETTER_MODIFIER;
2356 } else if (cur == 'o') {
2357 NEXT;
2358 type = XML_REGEXP_LETTER_OTHERS;
2359 } else {
2360 type = XML_REGEXP_LETTER;
2361 }
2362 } else if (cur == 'M') {
2363 NEXT;
2364 cur = CUR;
2365 if (cur == 'n') {
2366 NEXT;
2367 /* nonspacing */
2368 type = XML_REGEXP_MARK_NONSPACING;
2369 } else if (cur == 'c') {
2370 NEXT;
2371 /* spacing combining */
2372 type = XML_REGEXP_MARK_SPACECOMBINING;
2373 } else if (cur == 'e') {
2374 NEXT;
2375 /* enclosing */
2376 type = XML_REGEXP_MARK_ENCLOSING;
2377 } else {
2378 /* all marks */
2379 type = XML_REGEXP_MARK;
2380 }
2381 } else if (cur == 'N') {
2382 NEXT;
2383 cur = CUR;
2384 if (cur == 'd') {
2385 NEXT;
2386 /* digital */
2387 type = XML_REGEXP_NUMBER_DECIMAL;
2388 } else if (cur == 'l') {
2389 NEXT;
2390 /* letter */
2391 type = XML_REGEXP_NUMBER_LETTER;
2392 } else if (cur == 'o') {
2393 NEXT;
2394 /* other */
2395 type = XML_REGEXP_NUMBER_OTHERS;
2396 } else {
2397 /* all numbers */
2398 type = XML_REGEXP_NUMBER;
2399 }
2400 } else if (cur == 'P') {
2401 NEXT;
2402 cur = CUR;
2403 if (cur == 'c') {
2404 NEXT;
2405 /* connector */
2406 type = XML_REGEXP_PUNCT_CONNECTOR;
2407 } else if (cur == 'd') {
2408 NEXT;
2409 /* dash */
2410 type = XML_REGEXP_PUNCT_DASH;
2411 } else if (cur == 's') {
2412 NEXT;
2413 /* open */
2414 type = XML_REGEXP_PUNCT_OPEN;
2415 } else if (cur == 'e') {
2416 NEXT;
2417 /* close */
2418 type = XML_REGEXP_PUNCT_CLOSE;
2419 } else if (cur == 'i') {
2420 NEXT;
2421 /* initial quote */
2422 type = XML_REGEXP_PUNCT_INITQUOTE;
2423 } else if (cur == 'f') {
2424 NEXT;
2425 /* final quote */
2426 type = XML_REGEXP_PUNCT_FINQUOTE;
2427 } else if (cur == 'o') {
2428 NEXT;
2429 /* other */
2430 type = XML_REGEXP_PUNCT_OTHERS;
2431 } else {
2432 /* all punctuation */
2433 type = XML_REGEXP_PUNCT;
2434 }
2435 } else if (cur == 'Z') {
2436 NEXT;
2437 cur = CUR;
2438 if (cur == 's') {
2439 NEXT;
2440 /* space */
2441 type = XML_REGEXP_SEPAR_SPACE;
2442 } else if (cur == 'l') {
2443 NEXT;
2444 /* line */
2445 type = XML_REGEXP_SEPAR_LINE;
2446 } else if (cur == 'p') {
2447 NEXT;
2448 /* paragraph */
2449 type = XML_REGEXP_SEPAR_PARA;
2450 } else {
2451 /* all separators */
2452 type = XML_REGEXP_SEPAR;
2453 }
2454 } else if (cur == 'S') {
2455 NEXT;
2456 cur = CUR;
2457 if (cur == 'm') {
2458 NEXT;
2459 type = XML_REGEXP_SYMBOL_MATH;
2460 /* math */
2461 } else if (cur == 'c') {
2462 NEXT;
2463 type = XML_REGEXP_SYMBOL_CURRENCY;
2464 /* currency */
2465 } else if (cur == 'k') {
2466 NEXT;
2467 type = XML_REGEXP_SYMBOL_MODIFIER;
2468 /* modifiers */
2469 } else if (cur == 'o') {
2470 NEXT;
2471 type = XML_REGEXP_SYMBOL_OTHERS;
2472 /* other */
2473 } else {
2474 /* all symbols */
2475 type = XML_REGEXP_SYMBOL;
2476 }
2477 } else if (cur == 'C') {
2478 NEXT;
2479 cur = CUR;
2480 if (cur == 'c') {
2481 NEXT;
2482 /* control */
2483 type = XML_REGEXP_OTHER_CONTROL;
2484 } else if (cur == 'f') {
2485 NEXT;
2486 /* format */
2487 type = XML_REGEXP_OTHER_FORMAT;
2488 } else if (cur == 'o') {
2489 NEXT;
2490 /* private use */
2491 type = XML_REGEXP_OTHER_PRIVATE;
2492 } else if (cur == 'n') {
2493 NEXT;
2494 /* not assigned */
2495 type = XML_REGEXP_OTHER_NA;
2496 } else {
2497 /* all others */
2498 type = XML_REGEXP_OTHER;
2499 }
2500 } else if (cur == 'I') {
2501 const xmlChar *start;
2502 NEXT;
2503 cur = CUR;
2504 if (cur != 's') {
2505 ERROR("IsXXXX expected");
2506 return;
2507 }
2508 NEXT;
2509 start = ctxt->cur;
2510 cur = CUR;
2511 if (((cur >= 'a') && (cur <= 'z')) ||
2512 ((cur >= 'A') && (cur <= 'Z')) ||
2513 ((cur >= '0') && (cur <= '9')) ||
2514 (cur == 0x2D)) {
2515 NEXT;
2516 cur = CUR;
2517 while (((cur >= 'a') && (cur <= 'z')) ||
2518 ((cur >= 'A') && (cur <= 'Z')) ||
2519 ((cur >= '0') && (cur <= '9')) ||
2520 (cur == 0x2D)) {
2521 NEXT;
2522 cur = CUR;
2523 }
2524 }
2525 type = XML_REGEXP_BLOCK_NAME;
2526 blockName = xmlStrndup(start, ctxt->cur - start);
2527 } else {
2528 ERROR("Unknown char property");
2529 return;
2530 }
2531 if (ctxt->atom == NULL) {
2532 ctxt->atom = xmlRegNewAtom(ctxt, type);
2533 if (ctxt->atom != NULL)
2534 ctxt->atom->valuep = blockName;
2535 } else if (ctxt->atom->type == XML_REGEXP_RANGES) {
2536 xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,
2537 type, 0, 0, blockName);
2538 }
2539}
2540
2541/**
2542 * xmlFAParseCharClassEsc:
2543 * ctxt: a regexp parser context
2544 *
2545 * [23] charClassEsc ::= ( SingleCharEsc | MultiCharEsc | catEsc | complEsc )
2546 * [24] SingleCharEsc ::= '\' [nrt\|.?*+(){}#x2D#x5B#x5D#x5E]
2547 * [25] catEsc ::= '\p{' charProp '}'
2548 * [26] complEsc ::= '\P{' charProp '}'
2549 * [37] MultiCharEsc ::= '.' | ('\' [sSiIcCdDwW])
2550 */
2551static void
2552xmlFAParseCharClassEsc(xmlRegParserCtxtPtr ctxt) {
2553 int cur;
2554
2555 if (CUR == '.') {
2556 if (ctxt->atom == NULL) {
2557 ctxt->atom = xmlRegNewAtom(ctxt, XML_REGEXP_ANYCHAR);
2558 } else if (ctxt->atom->type == XML_REGEXP_RANGES) {
2559 xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,
2560 XML_REGEXP_ANYCHAR, 0, 0, NULL);
2561 }
2562 NEXT;
2563 return;
2564 }
2565 if (CUR != '\\') {
2566 ERROR("Escaped sequence: expecting \\");
2567 return;
2568 }
2569 NEXT;
2570 cur = CUR;
2571 if (cur == 'p') {
2572 NEXT;
2573 if (CUR != '{') {
2574 ERROR("Expecting '{'");
2575 return;
2576 }
2577 NEXT;
2578 xmlFAParseCharProp(ctxt);
2579 if (CUR != '}') {
2580 ERROR("Expecting '}'");
2581 return;
2582 }
2583 NEXT;
2584 } else if (cur == 'P') {
2585 NEXT;
2586 if (CUR != '{') {
2587 ERROR("Expecting '{'");
2588 return;
2589 }
2590 NEXT;
2591 xmlFAParseCharProp(ctxt);
2592 ctxt->atom->neg = 1;
2593 if (CUR != '}') {
2594 ERROR("Expecting '}'");
2595 return;
2596 }
2597 NEXT;
2598 } else if ((cur == 'n') || (cur == 'r') || (cur == 't') || (cur == '\\') ||
2599 (cur == '|') || (cur == '.') || (cur == '?') || (cur == '*') ||
2600 (cur == '+') || (cur == '(') || (cur == ')') || (cur == '{') ||
2601 (cur == '}') || (cur == 0x2D) || (cur == 0x5B) || (cur == 0x5D) ||
2602 (cur == 0x5E)) {
2603 if (ctxt->atom == NULL) {
2604 ctxt->atom = xmlRegNewAtom(ctxt, XML_REGEXP_CHARVAL);
2605 if (ctxt->atom != NULL)
2606 ctxt->atom->codepoint = cur;
2607 } else if (ctxt->atom->type == XML_REGEXP_RANGES) {
2608 xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,
2609 XML_REGEXP_CHARVAL, cur, cur, NULL);
2610 }
2611 NEXT;
2612 } else if ((cur == 's') || (cur == 'S') || (cur == 'i') || (cur == 'I') ||
2613 (cur == 'c') || (cur == 'C') || (cur == 'd') || (cur == 'D') ||
2614 (cur == 'w') || (cur == 'W')) {
2615 xmlRegAtomType type;
2616
2617 switch (cur) {
2618 case 's':
2619 type = XML_REGEXP_ANYSPACE;
2620 break;
2621 case 'S':
2622 type = XML_REGEXP_NOTSPACE;
2623 break;
2624 case 'i':
2625 type = XML_REGEXP_INITNAME;
2626 break;
2627 case 'I':
2628 type = XML_REGEXP_NOTINITNAME;
2629 break;
2630 case 'c':
2631 type = XML_REGEXP_NAMECHAR;
2632 break;
2633 case 'C':
2634 type = XML_REGEXP_NOTNAMECHAR;
2635 break;
2636 case 'd':
2637 type = XML_REGEXP_DECIMAL;
2638 break;
2639 case 'D':
2640 type = XML_REGEXP_NOTDECIMAL;
2641 break;
2642 case 'w':
2643 type = XML_REGEXP_REALCHAR;
2644 break;
2645 case 'W':
2646 type = XML_REGEXP_NOTREALCHAR;
2647 break;
2648 }
2649 NEXT;
2650 if (ctxt->atom == NULL) {
2651 ctxt->atom = xmlRegNewAtom(ctxt, type);
2652 } else if (ctxt->atom->type == XML_REGEXP_RANGES) {
2653 xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,
2654 type, 0, 0, NULL);
2655 }
2656 }
2657}
2658
2659/**
2660 * xmlFAParseCharRef:
2661 * ctxt: a regexp parser context
2662 *
2663 * [19] XmlCharRef ::= ( '&#' [0-9]+ ';' ) | (' &#x' [0-9a-fA-F]+ ';' )
2664 */
2665static int
2666xmlFAParseCharRef(xmlRegParserCtxtPtr ctxt) {
2667 int ret = 0, cur;
2668
2669 if ((CUR != '&') || (NXT(1) != '#'))
2670 return(-1);
2671 NEXT;
2672 NEXT;
2673 cur = CUR;
2674 if (cur == 'x') {
2675 NEXT;
2676 cur = CUR;
2677 if (((cur >= '0') && (cur <= '9')) ||
2678 ((cur >= 'a') && (cur <= 'f')) ||
2679 ((cur >= 'A') && (cur <= 'F'))) {
2680 while (((cur >= '0') && (cur <= '9')) ||
2681 ((cur >= 'A') && (cur <= 'F'))) {
2682 if ((cur >= '0') && (cur <= '9'))
2683 ret = ret * 16 + cur - '0';
2684 else if ((cur >= 'a') && (cur <= 'f'))
2685 ret = ret * 16 + 10 + (cur - 'a');
2686 else
2687 ret = ret * 16 + 10 + (cur - 'A');
2688 NEXT;
2689 cur = CUR;
2690 }
2691 } else {
2692 ERROR("Char ref: expecting [0-9A-F]");
2693 return(-1);
2694 }
2695 } else {
2696 if ((cur >= '0') && (cur <= '9')) {
2697 while ((cur >= '0') && (cur <= '9')) {
2698 ret = ret * 10 + cur - '0';
2699 NEXT;
2700 cur = CUR;
2701 }
2702 } else {
2703 ERROR("Char ref: expecting [0-9]");
2704 return(-1);
2705 }
2706 }
2707 if (cur != ';') {
2708 ERROR("Char ref: expecting ';'");
2709 return(-1);
2710 } else {
2711 NEXT;
2712 }
2713 return(ret);
2714}
2715
2716/**
2717 * xmlFAParseCharRange:
2718 * ctxt: a regexp parser context
2719 *
2720 * [17] charRange ::= seRange | XmlCharRef | XmlCharIncDash
2721 * [18] seRange ::= charOrEsc '-' charOrEsc
2722 * [20] charOrEsc ::= XmlChar | SingleCharEsc
2723 * [21] XmlChar ::= [^\#x2D#x5B#x5D]
2724 * [22] XmlCharIncDash ::= [^\#x5B#x5D]
2725 */
2726static void
2727xmlFAParseCharRange(xmlRegParserCtxtPtr ctxt) {
2728 int cur;
2729 int start = -1;
2730 int end = -1;
2731
2732 if ((CUR == '&') && (NXT(1) == '#')) {
2733 end = start = xmlFAParseCharRef(ctxt);
2734 xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,
2735 XML_REGEXP_CHARVAL, start, end, NULL);
2736 return;
2737 }
2738 cur = CUR;
2739 if (cur == '\\') {
2740 NEXT;
2741 cur = CUR;
2742 switch (cur) {
2743 case 'n': start = 0xA; break;
2744 case 'r': start = 0xD; break;
2745 case 't': start = 0x9; break;
2746 case '\\': case '|': case '.': case '-': case '^': case '?':
2747 case '*': case '+': case '{': case '}': case '(': case ')':
2748 case '[': case ']':
2749 start = cur; break;
2750 default:
2751 ERROR("Invalid escape value");
2752 return;
2753 }
2754 end = start;
2755 } else if ((cur != 0x5B) && (cur != 0x5D)) {
2756 end = start = cur;
2757 } else {
2758 ERROR("Expecting a char range");
2759 return;
2760 }
2761 NEXT;
2762 if (start == '-') {
2763 return;
2764 }
2765 cur = CUR;
2766 if (cur != '-') {
2767 xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,
2768 XML_REGEXP_CHARVAL, start, end, NULL);
2769 return;
2770 }
2771 NEXT;
2772 cur = CUR;
2773 if (cur == '\\') {
2774 NEXT;
2775 cur = CUR;
2776 switch (cur) {
2777 case 'n': end = 0xA; break;
2778 case 'r': end = 0xD; break;
2779 case 't': end = 0x9; break;
2780 case '\\': case '|': case '.': case '-': case '^': case '?':
2781 case '*': case '+': case '{': case '}': case '(': case ')':
2782 case '[': case ']':
2783 end = cur; break;
2784 default:
2785 ERROR("Invalid escape value");
2786 return;
2787 }
2788 } else if ((cur != 0x5B) && (cur != 0x5D)) {
2789 end = cur;
2790 } else {
2791 ERROR("Expecting the end of a char range");
2792 return;
2793 }
2794 NEXT;
2795 /* TODO check that the values are acceptable character ranges for XML */
2796 if (end < start) {
2797 ERROR("End of range is before start of range");
2798 } else {
2799 xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,
2800 XML_REGEXP_CHARVAL, start, end, NULL);
2801 }
2802 return;
2803}
2804
2805/**
2806 * xmlFAParsePosCharGroup:
2807 * ctxt: a regexp parser context
2808 *
2809 * [14] posCharGroup ::= ( charRange | charClassEsc )+
2810 */
2811static void
2812xmlFAParsePosCharGroup(xmlRegParserCtxtPtr ctxt) {
2813 do {
2814 if ((CUR == '\\') || (CUR == '.')) {
2815 xmlFAParseCharClassEsc(ctxt);
2816 } else {
2817 xmlFAParseCharRange(ctxt);
2818 }
2819 } while ((CUR != ']') && (CUR != '^') && (CUR != '-') &&
2820 (ctxt->error == 0));
2821}
2822
2823/**
2824 * xmlFAParseCharGroup:
2825 * ctxt: a regexp parser context
2826 *
2827 * [13] charGroup ::= posCharGroup | negCharGroup | charClassSub
2828 * [15] negCharGroup ::= '^' posCharGroup
2829 * [16] charClassSub ::= ( posCharGroup | negCharGroup ) '-' charClassExpr
2830 * [12] charClassExpr ::= '[' charGroup ']'
2831 */
2832static void
2833xmlFAParseCharGroup(xmlRegParserCtxtPtr ctxt) {
2834 int n = ctxt->neg;
2835 while ((CUR != ']') && (ctxt->error == 0)) {
2836 if (CUR == '^') {
2837 int neg = ctxt->neg;
2838
2839 NEXT;
2840 ctxt->neg = !ctxt->neg;
2841 xmlFAParsePosCharGroup(ctxt);
2842 ctxt->neg = neg;
2843 } else if (CUR == '-') {
2844 NEXT;
2845 ctxt->neg = !ctxt->neg;
2846 if (CUR != '[') {
2847 ERROR("charClassExpr: '[' expected");
2848 break;
2849 }
2850 NEXT;
2851 xmlFAParseCharGroup(ctxt);
2852 if (CUR == ']') {
2853 NEXT;
2854 } else {
2855 ERROR("charClassExpr: ']' expected");
2856 break;
2857 }
2858 break;
2859 } else if (CUR != ']') {
2860 xmlFAParsePosCharGroup(ctxt);
2861 }
2862 }
2863 ctxt->neg = n;
2864}
2865
2866/**
2867 * xmlFAParseCharClass:
2868 * ctxt: a regexp parser context
2869 *
2870 * [11] charClass ::= charClassEsc | charClassExpr
2871 * [12] charClassExpr ::= '[' charGroup ']'
2872 */
2873static void
2874xmlFAParseCharClass(xmlRegParserCtxtPtr ctxt) {
2875 if (CUR == '[') {
2876 NEXT;
2877 ctxt->atom = xmlRegNewAtom(ctxt, XML_REGEXP_RANGES);
2878 if (ctxt->atom == NULL)
2879 return;
2880 xmlFAParseCharGroup(ctxt);
2881 if (CUR == ']') {
2882 NEXT;
2883 } else {
2884 ERROR("xmlFAParseCharClass: ']' expected");
2885 }
2886 } else {
2887 xmlFAParseCharClassEsc(ctxt);
2888 }
2889}
2890
2891/**
2892 * xmlFAParseQuantExact:
2893 * ctxt: a regexp parser context
2894 *
2895 * [8] QuantExact ::= [0-9]+
2896 */
2897static int
2898xmlFAParseQuantExact(xmlRegParserCtxtPtr ctxt) {
2899 int ret = 0;
2900 int ok = 0;
2901
2902 while ((CUR >= '0') && (CUR <= '9')) {
2903 ret = ret * 10 + (CUR - '0');
2904 ok = 1;
2905 NEXT;
2906 }
2907 if (ok != 1) {
2908 return(-1);
2909 }
2910 return(ret);
2911}
2912
2913/**
2914 * xmlFAParseQuantifier:
2915 * ctxt: a regexp parser context
2916 *
2917 * [4] quantifier ::= [?*+] | ( '{' quantity '}' )
2918 * [5] quantity ::= quantRange | quantMin | QuantExact
2919 * [6] quantRange ::= QuantExact ',' QuantExact
2920 * [7] quantMin ::= QuantExact ','
2921 * [8] QuantExact ::= [0-9]+
2922 */
2923static int
2924xmlFAParseQuantifier(xmlRegParserCtxtPtr ctxt) {
2925 int cur;
2926
2927 cur = CUR;
2928 if ((cur == '?') || (cur == '*') || (cur == '+')) {
2929 if (ctxt->atom != NULL) {
2930 if (cur == '?')
2931 ctxt->atom->quant = XML_REGEXP_QUANT_OPT;
2932 else if (cur == '*')
2933 ctxt->atom->quant = XML_REGEXP_QUANT_MULT;
2934 else if (cur == '+')
2935 ctxt->atom->quant = XML_REGEXP_QUANT_PLUS;
2936 }
2937 NEXT;
2938 return(1);
2939 }
2940 if (cur == '{') {
2941 int min = 0, max = 0;
2942
2943 NEXT;
2944 cur = xmlFAParseQuantExact(ctxt);
2945 if (cur >= 0)
2946 min = cur;
2947 if (CUR == ',') {
2948 NEXT;
2949 cur = xmlFAParseQuantExact(ctxt);
2950 if (cur >= 0)
2951 max = cur;
2952 }
2953 if (CUR == '}') {
2954 NEXT;
2955 } else {
2956 ERROR("Unterminated quantifier");
2957 }
2958 if (max == 0)
2959 max = min;
2960 if (ctxt->atom != NULL) {
2961 ctxt->atom->quant = XML_REGEXP_QUANT_RANGE;
2962 ctxt->atom->min = min;
2963 ctxt->atom->max = max;
2964 }
2965 return(1);
2966 }
2967 return(0);
2968}
2969
2970/**
2971 * xmlFAParseAtom:
2972 * ctxt: a regexp parser context
2973 *
2974 * [9] atom ::= Char | charClass | ( '(' regExp ')' )
2975 */
2976static int
2977xmlFAParseAtom(xmlRegParserCtxtPtr ctxt) {
2978 int codepoint, len;
2979
2980 codepoint = xmlFAIsChar(ctxt);
2981 if (codepoint > 0) {
2982 ctxt->atom = xmlRegNewAtom(ctxt, XML_REGEXP_CHARVAL);
2983 if (ctxt->atom == NULL)
2984 return(-1);
2985 codepoint = CUR_SCHAR(ctxt->cur, len);
2986 ctxt->atom->codepoint = codepoint;
2987 NEXTL(len);
2988 return(1);
2989 } else if (CUR == '|') {
2990 return(0);
2991 } else if (CUR == 0) {
2992 return(0);
2993 } else if (CUR == ')') {
2994 return(0);
2995 } else if (CUR == '(') {
2996 xmlRegStatePtr start, oldend;
2997
2998 NEXT;
2999 xmlFAGenerateEpsilonTransition(ctxt, ctxt->state, NULL);
3000 start = ctxt->state;
3001 oldend = ctxt->end;
3002 ctxt->end = NULL;
3003 ctxt->atom = NULL;
3004 xmlFAParseRegExp(ctxt, 0);
3005 if (CUR == ')') {
3006 NEXT;
3007 } else {
3008 ERROR("xmlFAParseAtom: expecting ')'");
3009 }
3010 ctxt->atom = xmlRegNewAtom(ctxt, XML_REGEXP_SUBREG);
3011 if (ctxt->atom == NULL)
3012 return(-1);
3013 ctxt->atom->start = start;
3014 ctxt->atom->stop = ctxt->state;
3015 ctxt->end = oldend;
3016 return(1);
3017 } else if ((CUR == '[') || (CUR == '\\') || (CUR == '.')) {
3018 xmlFAParseCharClass(ctxt);
3019 return(1);
3020 }
3021 return(0);
3022}
3023
3024/**
3025 * xmlFAParsePiece:
3026 * ctxt: a regexp parser context
3027 *
3028 * [3] piece ::= atom quantifier?
3029 */
3030static int
3031xmlFAParsePiece(xmlRegParserCtxtPtr ctxt) {
3032 int ret;
3033
3034 ctxt->atom = NULL;
3035 ret = xmlFAParseAtom(ctxt);
3036 if (ret == 0)
3037 return(0);
3038 if (ctxt->atom == NULL) {
3039 ERROR("internal: no atom generated");
3040 }
3041 xmlFAParseQuantifier(ctxt);
3042 return(1);
3043}
3044
3045/**
3046 * xmlFAParseBranch:
3047 * ctxt: a regexp parser context
3048 * first: is taht the first
3049 *
3050 * [2] branch ::= piece*
3051 */
3052static void
3053xmlFAParseBranch(xmlRegParserCtxtPtr ctxt, int first) {
3054 xmlRegStatePtr previous;
3055 xmlRegAtomPtr prevatom = NULL;
3056 int ret;
3057
3058 previous = ctxt->state;
3059 ret = xmlFAParsePiece(ctxt);
3060 if (ret != 0) {
3061 if (first) {
3062 xmlFAGenerateTransitions(ctxt, previous, NULL, ctxt->atom);
3063 previous = ctxt->state;
3064 } else {
3065 prevatom = ctxt->atom;
3066 }
3067 ctxt->atom = NULL;
3068 }
3069 while ((ret != 0) && (ctxt->error == 0)) {
3070 ret = xmlFAParsePiece(ctxt);
3071 if (ret != 0) {
3072 if (first) {
3073 xmlFAGenerateTransitions(ctxt, previous, NULL, ctxt->atom);
3074 } else {
3075 xmlFAGenerateTransitions(ctxt, previous, NULL, prevatom);
3076 prevatom = ctxt->atom;
3077 }
3078 previous = ctxt->state;
3079 ctxt->atom = NULL;
3080 }
3081 }
3082 if (!first) {
3083 xmlFAGenerateTransitions(ctxt, previous, ctxt->end, prevatom);
3084 }
3085}
3086
3087/**
3088 * xmlFAParseRegExp:
3089 * ctxt: a regexp parser context
3090 * top: is that the top-level expressions ?
3091 *
3092 * [1] regExp ::= branch ( '|' branch )*
3093 */
3094static void
3095xmlFAParseRegExp(xmlRegParserCtxtPtr ctxt, int top) {
3096 xmlRegStatePtr start, end, oldend;
3097
3098 oldend = ctxt->end;
3099
3100 start = ctxt->state;
3101 xmlFAParseBranch(ctxt, (ctxt->end == NULL));
3102 if (CUR != '|') {
3103 ctxt->end = ctxt->state;
3104 return;
3105 }
3106 end = ctxt->state;
3107 while ((CUR == '|') && (ctxt->error == 0)) {
3108 NEXT;
3109 ctxt->state = start;
3110 ctxt->end = end;
3111 xmlFAParseBranch(ctxt, 0);
3112 }
3113 if (!top)
3114 ctxt->end = oldend;
3115}
3116
3117/************************************************************************
3118 * *
3119 * The basic API *
3120 * *
3121 ************************************************************************/
3122
3123/**
3124 * xmlRegexpPrint:
3125 * @output: the file for the output debug
3126 * @regexp: the compiled regexp
3127 *
3128 * Print the content of the compiled regular expression
3129 */
3130void
3131xmlRegexpPrint(FILE *output, xmlRegexpPtr regexp) {
3132 int i;
3133
3134 fprintf(output, " regexp: ");
3135 if (regexp == NULL) {
3136 fprintf(output, "NULL\n");
3137 return;
3138 }
3139 fprintf(output, "'%s' ", regexp->string);
3140 fprintf(output, "\n");
3141 fprintf(output, "%d atoms:\n", regexp->nbAtoms);
3142 for (i = 0;i < regexp->nbAtoms; i++) {
3143 fprintf(output, " %02d ", i);
3144 xmlRegPrintAtom(output, regexp->atoms[i]);
3145 }
3146 fprintf(output, "%d states:", regexp->nbStates);
3147 fprintf(output, "\n");
3148 for (i = 0;i < regexp->nbStates; i++) {
3149 xmlRegPrintState(output, regexp->states[i]);
3150 }
3151 fprintf(output, "%d counters:\n", regexp->nbCounters);
3152 for (i = 0;i < regexp->nbCounters; i++) {
3153 fprintf(output, " %d: min %d max %d\n", i, regexp->counters[i].min,
3154 regexp->counters[i].max);
3155 }
3156}
3157
3158/**
3159 * xmlRegexpCompile:
3160 * @regexp: a regular expression string
3161 *
3162 * Parses a regular expression conforming to XML Schemas Part 2 Datatype
3163 * Appendix F and build an automata suitable for testing strings against
3164 * that regular expression
3165 *
3166 * Returns the compiled expression or NULL in case of error
3167 */
3168xmlRegexpPtr
3169xmlRegexpCompile(const xmlChar *regexp) {
3170 xmlRegexpPtr ret;
3171 xmlRegParserCtxtPtr ctxt;
3172
3173 ctxt = xmlRegNewParserCtxt(regexp);
3174 if (ctxt == NULL)
3175 return(NULL);
3176
3177 /* initialize the parser */
3178 ctxt->end = NULL;
3179 ctxt->start = ctxt->state = xmlRegNewState(ctxt);
3180 xmlRegStatePush(ctxt, ctxt->start);
3181
3182 /* parse the expression building an automata */
3183 xmlFAParseRegExp(ctxt, 1);
3184 if (CUR != 0) {
3185 ERROR("xmlFAParseRegExp: extra characters");
3186 }
3187 ctxt->end = ctxt->state;
3188 ctxt->start->type = XML_REGEXP_START_STATE;
3189 ctxt->end->type = XML_REGEXP_FINAL_STATE;
3190
3191 /* remove the Epsilon except for counted transitions */
3192 xmlFAEliminateEpsilonTransitions(ctxt);
3193
3194
3195 if (ctxt->error != 0) {
3196 xmlRegFreeParserCtxt(ctxt);
3197 return(NULL);
3198 }
3199 ret = xmlRegEpxFromParse(ctxt);
3200 xmlRegFreeParserCtxt(ctxt);
3201 return(ret);
3202}
3203
3204/**
3205 * xmlRegexpExec:
3206 * @comp: the compiled regular expression
3207 * @content: the value to check against the regular expression
3208 *
3209 * Check if the regular expression generate the value
3210 *
3211 * Returns 1 if it matches, 0 if not and a negativa value in case of error
3212 */
3213int
3214xmlRegexpExec(xmlRegexpPtr comp, const xmlChar *content) {
3215 if ((comp == NULL) || (content == NULL))
3216 return(-1);
3217 return(xmlFARegExec(comp, content));
3218}
3219
3220/**
3221 * xmlRegFreeRegexp:
3222 * @regexp: the regexp
3223 *
3224 * Free a regexp
3225 */
3226void
3227xmlRegFreeRegexp(xmlRegexpPtr regexp) {
3228 int i;
3229 if (regexp == NULL)
3230 return;
3231
3232 if (regexp->string != NULL)
3233 xmlFree(regexp->string);
3234 if (regexp->states != NULL) {
3235 for (i = 0;i < regexp->nbStates;i++)
3236 xmlRegFreeState(regexp->states[i]);
3237 xmlFree(regexp->states);
3238 }
3239 if (regexp->atoms != NULL) {
3240 for (i = 0;i < regexp->nbAtoms;i++)
3241 xmlRegFreeAtom(regexp->atoms[i]);
3242 xmlFree(regexp->atoms);
3243 }
3244 if (regexp->counters != NULL)
3245 xmlFree(regexp->counters);
3246 xmlFree(regexp);
3247}
3248
3249#ifdef LIBXML_AUTOMATA_ENABLED
3250/************************************************************************
3251 * *
3252 * The Automata interface *
3253 * *
3254 ************************************************************************/
3255
3256/**
3257 * xmlNewAutomata:
3258 *
3259 * Create a new automata
3260 *
3261 * Returns the new object or NULL in case of failure
3262 */
3263xmlAutomataPtr
3264xmlNewAutomata(void) {
3265 xmlAutomataPtr ctxt;
3266
3267 ctxt = xmlRegNewParserCtxt(NULL);
3268 if (ctxt == NULL)
3269 return(NULL);
3270
3271 /* initialize the parser */
3272 ctxt->end = NULL;
3273 ctxt->start = ctxt->state = xmlRegNewState(ctxt);
3274 xmlRegStatePush(ctxt, ctxt->start);
3275
3276 return(ctxt);
3277}
3278
3279/**
3280 * xmlFreeAutomata:
3281 * @am: an automata
3282 *
3283 * Free an automata
3284 */
3285void
3286xmlFreeAutomata(xmlAutomataPtr am) {
3287 if (am == NULL)
3288 return;
3289 xmlRegFreeParserCtxt(am);
3290}
3291
3292/**
3293 * xmlAutomataGetInitState:
3294 * @am: an automata
3295 *
3296 * Returns the initial state of the automata
3297 */
3298xmlAutomataStatePtr
3299xmlAutomataGetInitState(xmlAutomataPtr am) {
3300 if (am == NULL)
3301 return(NULL);
3302 return(am->start);
3303}
3304
3305/**
3306 * xmlAutomataSetFinalState:
3307 * @am: an automata
3308 * @state: a state in this automata
3309 *
3310 * Makes that state a final state
3311 *
3312 * Returns 0 or -1 in case of error
3313 */
3314int
3315xmlAutomataSetFinalState(xmlAutomataPtr am, xmlAutomataStatePtr state) {
3316 if ((am == NULL) || (state == NULL))
3317 return(-1);
3318 state->type = XML_REGEXP_FINAL_STATE;
3319 return(0);
3320}
3321
3322/**
3323 * xmlAutomataNewTransition:
3324 * @am: an automata
3325 * @from: the starting point of the transition
3326 * @to: the target point of the transition or NULL
3327 * @token: the input string associated to that transition
3328 * @data: data passed to the callback function if the transition is activated
3329 *
3330 * If @to is NULL, this create first a new target state in the automata
3331 * and then adds a transition from the @from state to the target state
3332 * activated by the value of @token
3333 *
3334 * Returns the target state or NULL in case of error
3335 */
3336xmlAutomataStatePtr
3337xmlAutomataNewTransition(xmlAutomataPtr am, xmlAutomataStatePtr from,
3338 xmlAutomataStatePtr to, const xmlChar *token,
3339 void *data) {
3340 xmlRegAtomPtr atom;
3341
3342 if ((am == NULL) || (from == NULL) || (token == NULL))
3343 return(NULL);
3344 atom = xmlRegNewAtom(am, XML_REGEXP_STRING);
3345 atom->data = data;
3346 if (atom == NULL)
3347 return(NULL);
3348 atom->valuep = xmlStrdup(token);
3349
3350 xmlFAGenerateTransitions(am, from, to, atom);
3351 if (to == NULL)
3352 return(am->state);
3353 return(to);
3354}
3355
3356/**
3357 * xmlAutomataNewCountTrans:
3358 * @am: an automata
3359 * @from: the starting point of the transition
3360 * @to: the target point of the transition or NULL
3361 * @token: the input string associated to that transition
3362 * @min: the minimum successive occurences of token
3363 * @min: the maximum successive occurences of token
3364 *
3365 * If @to is NULL, this create first a new target state in the automata
3366 * and then adds a transition from the @from state to the target state
3367 * activated by a succession of input of value @token and whose number
3368 * is between @min and @max
3369 *
3370 * Returns the target state or NULL in case of error
3371 */
3372xmlAutomataStatePtr
3373xmlAutomataNewCountTrans(xmlAutomataPtr am, xmlAutomataStatePtr from,
3374 xmlAutomataStatePtr to, const xmlChar *token,
3375 int min, int max, void *data) {
3376 xmlRegAtomPtr atom;
3377
3378 if ((am == NULL) || (from == NULL) || (token == NULL))
3379 return(NULL);
3380 if (min < 0)
3381 return(NULL);
3382 if ((max < min) || (max < 1))
3383 return(NULL);
3384 atom = xmlRegNewAtom(am, XML_REGEXP_STRING);
3385 if (atom == NULL)
3386 return(NULL);
3387 atom->valuep = xmlStrdup(token);
3388 atom->data = data;
3389 if (min == 0)
3390 atom->min = 1;
3391 else
3392 atom->min = min;
3393 atom->max = max;
3394
3395 xmlFAGenerateTransitions(am, from, to, atom);
3396 if (to == NULL)
3397 to = am->state;
3398 if (to == NULL)
3399 return(NULL);
3400 if (min == 0)
3401 xmlFAGenerateEpsilonTransition(am, from, to);
3402 return(to);
3403}
3404
3405/**
3406 * xmlAutomataNewState:
3407 * @am: an automata
3408 *
3409 * Create a new disconnected state in the automata
3410 *
3411 * Returns the new state or NULL in case of error
3412 */
3413xmlAutomataStatePtr
3414xmlAutomataNewState(xmlAutomataPtr am) {
3415 xmlAutomataStatePtr to;
3416
3417 if (am == NULL)
3418 return(NULL);
3419 to = xmlRegNewState(am);
3420 xmlRegStatePush(am, to);
3421 return(to);
3422}
3423
3424/**
3425 * xmlAutomataNewTransition:
3426 * @am: an automata
3427 * @from: the starting point of the transition
3428 * @to: the target point of the transition or NULL
3429 *
3430 * If @to is NULL, this create first a new target state in the automata
3431 * and then adds a an epsilon transition from the @from state to the
3432 * target state
3433 *
3434 * Returns the target state or NULL in case of error
3435 */
3436xmlAutomataStatePtr
3437xmlAutomataNewEpsilon(xmlAutomataPtr am, xmlAutomataStatePtr from,
3438 xmlAutomataStatePtr to) {
3439 if ((am == NULL) || (from == NULL))
3440 return(NULL);
3441 xmlFAGenerateEpsilonTransition(am, from, to);
3442 if (to == NULL)
3443 return(am->state);
3444 return(to);
3445}
3446
3447#if 0
3448int xmlAutomataNewCounter (xmlAutomataPtr am);
3449#endif
3450
3451/**
3452 * xmlAutomataCompile:
3453 * @am: an automata
3454 *
3455 * Compile the automata into a Reg Exp ready for being executed.
3456 * The automata should be free after this point.
3457 *
3458 * Returns the compiled regexp or NULL in case of error
3459 */
3460xmlRegexpPtr
3461xmlAutomataCompile(xmlAutomataPtr am) {
3462 xmlRegexpPtr ret;
3463
3464 xmlFAEliminateEpsilonTransitions(am);
3465 ret = xmlRegEpxFromParse(am);
3466
3467 return(ret);
3468}
3469#endif /* LIBXML_AUTOMATA_ENABLED */
3470#endif /* LIBXML_REGEXP_ENABLED */