source: trunk/third/libxml2/xmlregexp.c @ 21532

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