VirtualBox

source: vbox/trunk/src/libs/libxml2-2.6.30/xmlregexp.c@ 25275

Last change on this file since 25275 was 12903, checked in by vboxsync, 16 years ago

libxml: fixed an obviously typo (taken from upstream)
  • Property svn:eol-style set to native
  • Property svn:keywords set to Date Revision Author Id
File size: 212.8 KB
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 MAX_PUSH 10000000
46
47#define ERROR(str) \
48 ctxt->error = XML_REGEXP_COMPILE_ERROR; \
49 xmlRegexpErrCompile(ctxt, str);
50#define NEXT ctxt->cur++
51#define CUR (*(ctxt->cur))
52#define NXT(index) (ctxt->cur[index])
53
54#define CUR_SCHAR(s, l) xmlStringCurrentChar(NULL, s, &l)
55#define NEXTL(l) ctxt->cur += l;
56#define XML_REG_STRING_SEPARATOR '|'
57/*
58 * Need PREV to check on a '-' within a Character Group. May only be used
59 * when it's guaranteed that cur is not at the beginning of ctxt->string!
60 */
61#define PREV (ctxt->cur[-1])
62
63/**
64 * TODO:
65 *
66 * macro to flag unimplemented blocks
67 */
68#define TODO \
69 xmlGenericError(xmlGenericErrorContext, \
70 "Unimplemented block at %s:%d\n", \
71 __FILE__, __LINE__);
72
73/************************************************************************
74 * *
75 * Datatypes and structures *
76 * *
77 ************************************************************************/
78
79/*
80 * Note: the order of the enums below is significant, do not shuffle
81 */
82typedef enum {
83 XML_REGEXP_EPSILON = 1,
84 XML_REGEXP_CHARVAL,
85 XML_REGEXP_RANGES,
86 XML_REGEXP_SUBREG, /* used for () sub regexps */
87 XML_REGEXP_STRING,
88 XML_REGEXP_ANYCHAR, /* . */
89 XML_REGEXP_ANYSPACE, /* \s */
90 XML_REGEXP_NOTSPACE, /* \S */
91 XML_REGEXP_INITNAME, /* \l */
92 XML_REGEXP_NOTINITNAME, /* \L */
93 XML_REGEXP_NAMECHAR, /* \c */
94 XML_REGEXP_NOTNAMECHAR, /* \C */
95 XML_REGEXP_DECIMAL, /* \d */
96 XML_REGEXP_NOTDECIMAL, /* \D */
97 XML_REGEXP_REALCHAR, /* \w */
98 XML_REGEXP_NOTREALCHAR, /* \W */
99 XML_REGEXP_LETTER = 100,
100 XML_REGEXP_LETTER_UPPERCASE,
101 XML_REGEXP_LETTER_LOWERCASE,
102 XML_REGEXP_LETTER_TITLECASE,
103 XML_REGEXP_LETTER_MODIFIER,
104 XML_REGEXP_LETTER_OTHERS,
105 XML_REGEXP_MARK,
106 XML_REGEXP_MARK_NONSPACING,
107 XML_REGEXP_MARK_SPACECOMBINING,
108 XML_REGEXP_MARK_ENCLOSING,
109 XML_REGEXP_NUMBER,
110 XML_REGEXP_NUMBER_DECIMAL,
111 XML_REGEXP_NUMBER_LETTER,
112 XML_REGEXP_NUMBER_OTHERS,
113 XML_REGEXP_PUNCT,
114 XML_REGEXP_PUNCT_CONNECTOR,
115 XML_REGEXP_PUNCT_DASH,
116 XML_REGEXP_PUNCT_OPEN,
117 XML_REGEXP_PUNCT_CLOSE,
118 XML_REGEXP_PUNCT_INITQUOTE,
119 XML_REGEXP_PUNCT_FINQUOTE,
120 XML_REGEXP_PUNCT_OTHERS,
121 XML_REGEXP_SEPAR,
122 XML_REGEXP_SEPAR_SPACE,
123 XML_REGEXP_SEPAR_LINE,
124 XML_REGEXP_SEPAR_PARA,
125 XML_REGEXP_SYMBOL,
126 XML_REGEXP_SYMBOL_MATH,
127 XML_REGEXP_SYMBOL_CURRENCY,
128 XML_REGEXP_SYMBOL_MODIFIER,
129 XML_REGEXP_SYMBOL_OTHERS,
130 XML_REGEXP_OTHER,
131 XML_REGEXP_OTHER_CONTROL,
132 XML_REGEXP_OTHER_FORMAT,
133 XML_REGEXP_OTHER_PRIVATE,
134 XML_REGEXP_OTHER_NA,
135 XML_REGEXP_BLOCK_NAME
136} xmlRegAtomType;
137
138typedef enum {
139 XML_REGEXP_QUANT_EPSILON = 1,
140 XML_REGEXP_QUANT_ONCE,
141 XML_REGEXP_QUANT_OPT,
142 XML_REGEXP_QUANT_MULT,
143 XML_REGEXP_QUANT_PLUS,
144 XML_REGEXP_QUANT_ONCEONLY,
145 XML_REGEXP_QUANT_ALL,
146 XML_REGEXP_QUANT_RANGE
147} xmlRegQuantType;
148
149typedef enum {
150 XML_REGEXP_START_STATE = 1,
151 XML_REGEXP_FINAL_STATE,
152 XML_REGEXP_TRANS_STATE,
153 XML_REGEXP_SINK_STATE,
154 XML_REGEXP_UNREACH_STATE
155} xmlRegStateType;
156
157typedef enum {
158 XML_REGEXP_MARK_NORMAL = 0,
159 XML_REGEXP_MARK_START,
160 XML_REGEXP_MARK_VISITED
161} xmlRegMarkedType;
162
163typedef struct _xmlRegRange xmlRegRange;
164typedef xmlRegRange *xmlRegRangePtr;
165
166struct _xmlRegRange {
167 int neg; /* 0 normal, 1 not, 2 exclude */
168 xmlRegAtomType type;
169 int start;
170 int end;
171 xmlChar *blockName;
172};
173
174typedef struct _xmlRegAtom xmlRegAtom;
175typedef xmlRegAtom *xmlRegAtomPtr;
176
177typedef struct _xmlAutomataState xmlRegState;
178typedef xmlRegState *xmlRegStatePtr;
179
180struct _xmlRegAtom {
181 int no;
182 xmlRegAtomType type;
183 xmlRegQuantType quant;
184 int min;
185 int max;
186
187 void *valuep;
188 void *valuep2;
189 int neg;
190 int codepoint;
191 xmlRegStatePtr start;
192 xmlRegStatePtr start0;
193 xmlRegStatePtr stop;
194 int maxRanges;
195 int nbRanges;
196 xmlRegRangePtr *ranges;
197 void *data;
198};
199
200typedef struct _xmlRegCounter xmlRegCounter;
201typedef xmlRegCounter *xmlRegCounterPtr;
202
203struct _xmlRegCounter {
204 int min;
205 int max;
206};
207
208typedef struct _xmlRegTrans xmlRegTrans;
209typedef xmlRegTrans *xmlRegTransPtr;
210
211struct _xmlRegTrans {
212 xmlRegAtomPtr atom;
213 int to;
214 int counter;
215 int count;
216 int nd;
217};
218
219struct _xmlAutomataState {
220 xmlRegStateType type;
221 xmlRegMarkedType mark;
222 xmlRegMarkedType reached;
223 int no;
224 int maxTrans;
225 int nbTrans;
226 xmlRegTrans *trans;
227 /* knowing states ponting to us can speed things up */
228 int maxTransTo;
229 int nbTransTo;
230 int *transTo;
231};
232
233typedef struct _xmlAutomata xmlRegParserCtxt;
234typedef xmlRegParserCtxt *xmlRegParserCtxtPtr;
235
236struct _xmlAutomata {
237 xmlChar *string;
238 xmlChar *cur;
239
240 int error;
241 int neg;
242
243 xmlRegStatePtr start;
244 xmlRegStatePtr end;
245 xmlRegStatePtr state;
246
247 xmlRegAtomPtr atom;
248
249 int maxAtoms;
250 int nbAtoms;
251 xmlRegAtomPtr *atoms;
252
253 int maxStates;
254 int nbStates;
255 xmlRegStatePtr *states;
256
257 int maxCounters;
258 int nbCounters;
259 xmlRegCounter *counters;
260
261 int determinist;
262 int negs;
263};
264
265struct _xmlRegexp {
266 xmlChar *string;
267 int nbStates;
268 xmlRegStatePtr *states;
269 int nbAtoms;
270 xmlRegAtomPtr *atoms;
271 int nbCounters;
272 xmlRegCounter *counters;
273 int determinist;
274 /*
275 * That's the compact form for determinists automatas
276 */
277 int nbstates;
278 int *compact;
279 void **transdata;
280 int nbstrings;
281 xmlChar **stringMap;
282};
283
284typedef struct _xmlRegExecRollback xmlRegExecRollback;
285typedef xmlRegExecRollback *xmlRegExecRollbackPtr;
286
287struct _xmlRegExecRollback {
288 xmlRegStatePtr state;/* the current state */
289 int index; /* the index in the input stack */
290 int nextbranch; /* the next transition to explore in that state */
291 int *counts; /* save the automata state if it has some */
292};
293
294typedef struct _xmlRegInputToken xmlRegInputToken;
295typedef xmlRegInputToken *xmlRegInputTokenPtr;
296
297struct _xmlRegInputToken {
298 xmlChar *value;
299 void *data;
300};
301
302struct _xmlRegExecCtxt {
303 int status; /* execution status != 0 indicate an error */
304 int determinist; /* did we find an indeterministic behaviour */
305 xmlRegexpPtr comp; /* the compiled regexp */
306 xmlRegExecCallbacks callback;
307 void *data;
308
309 xmlRegStatePtr state;/* the current state */
310 int transno; /* the current transition on that state */
311 int transcount; /* the number of chars in char counted transitions */
312
313 /*
314 * A stack of rollback states
315 */
316 int maxRollbacks;
317 int nbRollbacks;
318 xmlRegExecRollback *rollbacks;
319
320 /*
321 * The state of the automata if any
322 */
323 int *counts;
324
325 /*
326 * The input stack
327 */
328 int inputStackMax;
329 int inputStackNr;
330 int index;
331 int *charStack;
332 const xmlChar *inputString; /* when operating on characters */
333 xmlRegInputTokenPtr inputStack;/* when operating on strings */
334
335 /*
336 * error handling
337 */
338 int errStateNo; /* the error state number */
339 xmlRegStatePtr errState; /* the error state */
340 xmlChar *errString; /* the string raising the error */
341 int *errCounts; /* counters at the error state */
342 int nbPush;
343};
344
345#define REGEXP_ALL_COUNTER 0x123456
346#define REGEXP_ALL_LAX_COUNTER 0x123457
347
348static void xmlFAParseRegExp(xmlRegParserCtxtPtr ctxt, int top);
349static void xmlRegFreeState(xmlRegStatePtr state);
350static void xmlRegFreeAtom(xmlRegAtomPtr atom);
351static int xmlRegStrEqualWildcard(const xmlChar *expStr, const xmlChar *valStr);
352static int xmlRegCheckCharacter(xmlRegAtomPtr atom, int codepoint);
353static int xmlRegCheckCharacterRange(xmlRegAtomType type, int codepoint,
354 int neg, int start, int end, const xmlChar *blockName);
355
356/************************************************************************
357 * *
358 * Regexp memory error handler *
359 * *
360 ************************************************************************/
361/**
362 * xmlRegexpErrMemory:
363 * @extra: extra information
364 *
365 * Handle an out of memory condition
366 */
367static void
368xmlRegexpErrMemory(xmlRegParserCtxtPtr ctxt, const char *extra)
369{
370 const char *regexp = NULL;
371 if (ctxt != NULL) {
372 regexp = (const char *) ctxt->string;
373 ctxt->error = XML_ERR_NO_MEMORY;
374 }
375 __xmlRaiseError(NULL, NULL, NULL, NULL, NULL, XML_FROM_REGEXP,
376 XML_ERR_NO_MEMORY, XML_ERR_FATAL, NULL, 0, extra,
377 regexp, NULL, 0, 0,
378 "Memory allocation failed : %s\n", extra);
379}
380
381/**
382 * xmlRegexpErrCompile:
383 * @extra: extra information
384 *
385 * Handle a compilation failure
386 */
387static void
388xmlRegexpErrCompile(xmlRegParserCtxtPtr ctxt, const char *extra)
389{
390 const char *regexp = NULL;
391 int idx = 0;
392
393 if (ctxt != NULL) {
394 regexp = (const char *) ctxt->string;
395 idx = ctxt->cur - ctxt->string;
396 ctxt->error = XML_REGEXP_COMPILE_ERROR;
397 }
398 __xmlRaiseError(NULL, NULL, NULL, NULL, NULL, XML_FROM_REGEXP,
399 XML_REGEXP_COMPILE_ERROR, XML_ERR_FATAL, NULL, 0, extra,
400 regexp, NULL, idx, 0,
401 "failed to compile: %s\n", extra);
402}
403
404/************************************************************************
405 * *
406 * Allocation/Deallocation *
407 * *
408 ************************************************************************/
409
410static int xmlFAComputesDeterminism(xmlRegParserCtxtPtr ctxt);
411/**
412 * xmlRegEpxFromParse:
413 * @ctxt: the parser context used to build it
414 *
415 * Allocate a new regexp and fill it with the result from the parser
416 *
417 * Returns the new regexp or NULL in case of error
418 */
419static xmlRegexpPtr
420xmlRegEpxFromParse(xmlRegParserCtxtPtr ctxt) {
421 xmlRegexpPtr ret;
422
423 ret = (xmlRegexpPtr) xmlMalloc(sizeof(xmlRegexp));
424 if (ret == NULL) {
425 xmlRegexpErrMemory(ctxt, "compiling regexp");
426 return(NULL);
427 }
428 memset(ret, 0, sizeof(xmlRegexp));
429 ret->string = ctxt->string;
430 ret->nbStates = ctxt->nbStates;
431 ret->states = ctxt->states;
432 ret->nbAtoms = ctxt->nbAtoms;
433 ret->atoms = ctxt->atoms;
434 ret->nbCounters = ctxt->nbCounters;
435 ret->counters = ctxt->counters;
436 ret->determinist = ctxt->determinist;
437 if (ret->determinist == -1) {
438 xmlRegexpIsDeterminist(ret);
439 }
440
441 if ((ret->determinist != 0) &&
442 (ret->nbCounters == 0) &&
443 (ctxt->negs == 0) &&
444 (ret->atoms != NULL) &&
445 (ret->atoms[0] != NULL) &&
446 (ret->atoms[0]->type == XML_REGEXP_STRING)) {
447 int i, j, nbstates = 0, nbatoms = 0;
448 int *stateRemap;
449 int *stringRemap;
450 int *transitions;
451 void **transdata;
452 xmlChar **stringMap;
453 xmlChar *value;
454
455 /*
456 * Switch to a compact representation
457 * 1/ counting the effective number of states left
458 * 2/ counting the unique number of atoms, and check that
459 * they are all of the string type
460 * 3/ build a table state x atom for the transitions
461 */
462
463 stateRemap = xmlMalloc(ret->nbStates * sizeof(int));
464 if (stateRemap == NULL) {
465 xmlRegexpErrMemory(ctxt, "compiling regexp");
466 xmlFree(ret);
467 return(NULL);
468 }
469 for (i = 0;i < ret->nbStates;i++) {
470 if (ret->states[i] != NULL) {
471 stateRemap[i] = nbstates;
472 nbstates++;
473 } else {
474 stateRemap[i] = -1;
475 }
476 }
477#ifdef DEBUG_COMPACTION
478 printf("Final: %d states\n", nbstates);
479#endif
480 stringMap = xmlMalloc(ret->nbAtoms * sizeof(char *));
481 if (stringMap == NULL) {
482 xmlRegexpErrMemory(ctxt, "compiling regexp");
483 xmlFree(stateRemap);
484 xmlFree(ret);
485 return(NULL);
486 }
487 stringRemap = xmlMalloc(ret->nbAtoms * sizeof(int));
488 if (stringRemap == NULL) {
489 xmlRegexpErrMemory(ctxt, "compiling regexp");
490 xmlFree(stringMap);
491 xmlFree(stateRemap);
492 xmlFree(ret);
493 return(NULL);
494 }
495 for (i = 0;i < ret->nbAtoms;i++) {
496 if ((ret->atoms[i]->type == XML_REGEXP_STRING) &&
497 (ret->atoms[i]->quant == XML_REGEXP_QUANT_ONCE)) {
498 value = ret->atoms[i]->valuep;
499 for (j = 0;j < nbatoms;j++) {
500 if (xmlStrEqual(stringMap[j], value)) {
501 stringRemap[i] = j;
502 break;
503 }
504 }
505 if (j >= nbatoms) {
506 stringRemap[i] = nbatoms;
507 stringMap[nbatoms] = xmlStrdup(value);
508 if (stringMap[nbatoms] == NULL) {
509 for (i = 0;i < nbatoms;i++)
510 xmlFree(stringMap[i]);
511 xmlFree(stringRemap);
512 xmlFree(stringMap);
513 xmlFree(stateRemap);
514 xmlFree(ret);
515 return(NULL);
516 }
517 nbatoms++;
518 }
519 } else {
520 xmlFree(stateRemap);
521 xmlFree(stringRemap);
522 for (i = 0;i < nbatoms;i++)
523 xmlFree(stringMap[i]);
524 xmlFree(stringMap);
525 xmlFree(ret);
526 return(NULL);
527 }
528 }
529#ifdef DEBUG_COMPACTION
530 printf("Final: %d atoms\n", nbatoms);
531#endif
532 transitions = (int *) xmlMalloc((nbstates + 1) *
533 (nbatoms + 1) * sizeof(int));
534 if (transitions == NULL) {
535 xmlFree(stateRemap);
536 xmlFree(stringRemap);
537 xmlFree(stringMap);
538 xmlFree(ret);
539 return(NULL);
540 }
541 memset(transitions, 0, (nbstates + 1) * (nbatoms + 1) * sizeof(int));
542
543 /*
544 * Allocate the transition table. The first entry for each
545 * state corresponds to the state type.
546 */
547 transdata = NULL;
548
549 for (i = 0;i < ret->nbStates;i++) {
550 int stateno, atomno, targetno, prev;
551 xmlRegStatePtr state;
552 xmlRegTransPtr trans;
553
554 stateno = stateRemap[i];
555 if (stateno == -1)
556 continue;
557 state = ret->states[i];
558
559 transitions[stateno * (nbatoms + 1)] = state->type;
560
561 for (j = 0;j < state->nbTrans;j++) {
562 trans = &(state->trans[j]);
563 if ((trans->to == -1) || (trans->atom == NULL))
564 continue;
565 atomno = stringRemap[trans->atom->no];
566 if ((trans->atom->data != NULL) && (transdata == NULL)) {
567 transdata = (void **) xmlMalloc(nbstates * nbatoms *
568 sizeof(void *));
569 if (transdata != NULL)
570 memset(transdata, 0,
571 nbstates * nbatoms * sizeof(void *));
572 else {
573 xmlRegexpErrMemory(ctxt, "compiling regexp");
574 break;
575 }
576 }
577 targetno = stateRemap[trans->to];
578 /*
579 * if the same atom can generate transitions to 2 different
580 * states then it means the automata is not determinist and
581 * the compact form can't be used !
582 */
583 prev = transitions[stateno * (nbatoms + 1) + atomno + 1];
584 if (prev != 0) {
585 if (prev != targetno + 1) {
586 ret->determinist = 0;
587#ifdef DEBUG_COMPACTION
588 printf("Indet: state %d trans %d, atom %d to %d : %d to %d\n",
589 i, j, trans->atom->no, trans->to, atomno, targetno);
590 printf(" previous to is %d\n", prev);
591#endif
592 if (transdata != NULL)
593 xmlFree(transdata);
594 xmlFree(transitions);
595 xmlFree(stateRemap);
596 xmlFree(stringRemap);
597 for (i = 0;i < nbatoms;i++)
598 xmlFree(stringMap[i]);
599 xmlFree(stringMap);
600 goto not_determ;
601 }
602 } else {
603#if 0
604 printf("State %d trans %d: atom %d to %d : %d to %d\n",
605 i, j, trans->atom->no, trans->to, atomno, targetno);
606#endif
607 transitions[stateno * (nbatoms + 1) + atomno + 1] =
608 targetno + 1; /* to avoid 0 */
609 if (transdata != NULL)
610 transdata[stateno * nbatoms + atomno] =
611 trans->atom->data;
612 }
613 }
614 }
615 ret->determinist = 1;
616#ifdef DEBUG_COMPACTION
617 /*
618 * Debug
619 */
620 for (i = 0;i < nbstates;i++) {
621 for (j = 0;j < nbatoms + 1;j++) {
622 printf("%02d ", transitions[i * (nbatoms + 1) + j]);
623 }
624 printf("\n");
625 }
626 printf("\n");
627#endif
628 /*
629 * Cleanup of the old data
630 */
631 if (ret->states != NULL) {
632 for (i = 0;i < ret->nbStates;i++)
633 xmlRegFreeState(ret->states[i]);
634 xmlFree(ret->states);
635 }
636 ret->states = NULL;
637 ret->nbStates = 0;
638 if (ret->atoms != NULL) {
639 for (i = 0;i < ret->nbAtoms;i++)
640 xmlRegFreeAtom(ret->atoms[i]);
641 xmlFree(ret->atoms);
642 }
643 ret->atoms = NULL;
644 ret->nbAtoms = 0;
645
646 ret->compact = transitions;
647 ret->transdata = transdata;
648 ret->stringMap = stringMap;
649 ret->nbstrings = nbatoms;
650 ret->nbstates = nbstates;
651 xmlFree(stateRemap);
652 xmlFree(stringRemap);
653 }
654not_determ:
655 ctxt->string = NULL;
656 ctxt->nbStates = 0;
657 ctxt->states = NULL;
658 ctxt->nbAtoms = 0;
659 ctxt->atoms = NULL;
660 ctxt->nbCounters = 0;
661 ctxt->counters = NULL;
662 return(ret);
663}
664
665/**
666 * xmlRegNewParserCtxt:
667 * @string: the string to parse
668 *
669 * Allocate a new regexp parser context
670 *
671 * Returns the new context or NULL in case of error
672 */
673static xmlRegParserCtxtPtr
674xmlRegNewParserCtxt(const xmlChar *string) {
675 xmlRegParserCtxtPtr ret;
676
677 ret = (xmlRegParserCtxtPtr) xmlMalloc(sizeof(xmlRegParserCtxt));
678 if (ret == NULL)
679 return(NULL);
680 memset(ret, 0, sizeof(xmlRegParserCtxt));
681 if (string != NULL)
682 ret->string = xmlStrdup(string);
683 ret->cur = ret->string;
684 ret->neg = 0;
685 ret->negs = 0;
686 ret->error = 0;
687 ret->determinist = -1;
688 return(ret);
689}
690
691/**
692 * xmlRegNewRange:
693 * @ctxt: the regexp parser context
694 * @neg: is that negative
695 * @type: the type of range
696 * @start: the start codepoint
697 * @end: the end codepoint
698 *
699 * Allocate a new regexp range
700 *
701 * Returns the new range or NULL in case of error
702 */
703static xmlRegRangePtr
704xmlRegNewRange(xmlRegParserCtxtPtr ctxt,
705 int neg, xmlRegAtomType type, int start, int end) {
706 xmlRegRangePtr ret;
707
708 ret = (xmlRegRangePtr) xmlMalloc(sizeof(xmlRegRange));
709 if (ret == NULL) {
710 xmlRegexpErrMemory(ctxt, "allocating range");
711 return(NULL);
712 }
713 ret->neg = neg;
714 ret->type = type;
715 ret->start = start;
716 ret->end = end;
717 return(ret);
718}
719
720/**
721 * xmlRegFreeRange:
722 * @range: the regexp range
723 *
724 * Free a regexp range
725 */
726static void
727xmlRegFreeRange(xmlRegRangePtr range) {
728 if (range == NULL)
729 return;
730
731 if (range->blockName != NULL)
732 xmlFree(range->blockName);
733 xmlFree(range);
734}
735
736/**
737 * xmlRegCopyRange:
738 * @range: the regexp range
739 *
740 * Copy a regexp range
741 *
742 * Returns the new copy or NULL in case of error.
743 */
744static xmlRegRangePtr
745xmlRegCopyRange(xmlRegParserCtxtPtr ctxt, xmlRegRangePtr range) {
746 xmlRegRangePtr ret;
747
748 if (range == NULL)
749 return(NULL);
750
751 ret = xmlRegNewRange(ctxt, range->neg, range->type, range->start,
752 range->end);
753 if (ret == NULL)
754 return(NULL);
755 if (range->blockName != NULL) {
756 ret->blockName = xmlStrdup(range->blockName);
757 if (ret->blockName == NULL) {
758 xmlRegexpErrMemory(ctxt, "allocating range");
759 xmlRegFreeRange(ret);
760 return(NULL);
761 }
762 }
763 return(ret);
764}
765
766/**
767 * xmlRegNewAtom:
768 * @ctxt: the regexp parser context
769 * @type: the type of atom
770 *
771 * Allocate a new atom
772 *
773 * Returns the new atom or NULL in case of error
774 */
775static xmlRegAtomPtr
776xmlRegNewAtom(xmlRegParserCtxtPtr ctxt, xmlRegAtomType type) {
777 xmlRegAtomPtr ret;
778
779 ret = (xmlRegAtomPtr) xmlMalloc(sizeof(xmlRegAtom));
780 if (ret == NULL) {
781 xmlRegexpErrMemory(ctxt, "allocating atom");
782 return(NULL);
783 }
784 memset(ret, 0, sizeof(xmlRegAtom));
785 ret->type = type;
786 ret->quant = XML_REGEXP_QUANT_ONCE;
787 ret->min = 0;
788 ret->max = 0;
789 return(ret);
790}
791
792/**
793 * xmlRegFreeAtom:
794 * @atom: the regexp atom
795 *
796 * Free a regexp atom
797 */
798static void
799xmlRegFreeAtom(xmlRegAtomPtr atom) {
800 int i;
801
802 if (atom == NULL)
803 return;
804
805 for (i = 0;i < atom->nbRanges;i++)
806 xmlRegFreeRange(atom->ranges[i]);
807 if (atom->ranges != NULL)
808 xmlFree(atom->ranges);
809 if ((atom->type == XML_REGEXP_STRING) && (atom->valuep != NULL))
810 xmlFree(atom->valuep);
811 if ((atom->type == XML_REGEXP_STRING) && (atom->valuep2 != NULL))
812 xmlFree(atom->valuep2);
813 if ((atom->type == XML_REGEXP_BLOCK_NAME) && (atom->valuep != NULL))
814 xmlFree(atom->valuep);
815 xmlFree(atom);
816}
817
818/**
819 * xmlRegCopyAtom:
820 * @ctxt: the regexp parser context
821 * @atom: the oiginal atom
822 *
823 * Allocate a new regexp range
824 *
825 * Returns the new atom or NULL in case of error
826 */
827static xmlRegAtomPtr
828xmlRegCopyAtom(xmlRegParserCtxtPtr ctxt, xmlRegAtomPtr atom) {
829 xmlRegAtomPtr ret;
830
831 ret = (xmlRegAtomPtr) xmlMalloc(sizeof(xmlRegAtom));
832 if (ret == NULL) {
833 xmlRegexpErrMemory(ctxt, "copying atom");
834 return(NULL);
835 }
836 memset(ret, 0, sizeof(xmlRegAtom));
837 ret->type = atom->type;
838 ret->quant = atom->quant;
839 ret->min = atom->min;
840 ret->max = atom->max;
841 if (atom->nbRanges > 0) {
842 int i;
843
844 ret->ranges = (xmlRegRangePtr *) xmlMalloc(sizeof(xmlRegRangePtr) *
845 atom->nbRanges);
846 if (ret->ranges == NULL) {
847 xmlRegexpErrMemory(ctxt, "copying atom");
848 goto error;
849 }
850 for (i = 0;i < atom->nbRanges;i++) {
851 ret->ranges[i] = xmlRegCopyRange(ctxt, atom->ranges[i]);
852 if (ret->ranges[i] == NULL)
853 goto error;
854 ret->nbRanges = i + 1;
855 }
856 }
857 return(ret);
858
859error:
860 xmlRegFreeAtom(ret);
861 return(NULL);
862}
863
864static xmlRegStatePtr
865xmlRegNewState(xmlRegParserCtxtPtr ctxt) {
866 xmlRegStatePtr ret;
867
868 ret = (xmlRegStatePtr) xmlMalloc(sizeof(xmlRegState));
869 if (ret == NULL) {
870 xmlRegexpErrMemory(ctxt, "allocating state");
871 return(NULL);
872 }
873 memset(ret, 0, sizeof(xmlRegState));
874 ret->type = XML_REGEXP_TRANS_STATE;
875 ret->mark = XML_REGEXP_MARK_NORMAL;
876 return(ret);
877}
878
879/**
880 * xmlRegFreeState:
881 * @state: the regexp state
882 *
883 * Free a regexp state
884 */
885static void
886xmlRegFreeState(xmlRegStatePtr state) {
887 if (state == NULL)
888 return;
889
890 if (state->trans != NULL)
891 xmlFree(state->trans);
892 if (state->transTo != NULL)
893 xmlFree(state->transTo);
894 xmlFree(state);
895}
896
897/**
898 * xmlRegFreeParserCtxt:
899 * @ctxt: the regexp parser context
900 *
901 * Free a regexp parser context
902 */
903static void
904xmlRegFreeParserCtxt(xmlRegParserCtxtPtr ctxt) {
905 int i;
906 if (ctxt == NULL)
907 return;
908
909 if (ctxt->string != NULL)
910 xmlFree(ctxt->string);
911 if (ctxt->states != NULL) {
912 for (i = 0;i < ctxt->nbStates;i++)
913 xmlRegFreeState(ctxt->states[i]);
914 xmlFree(ctxt->states);
915 }
916 if (ctxt->atoms != NULL) {
917 for (i = 0;i < ctxt->nbAtoms;i++)
918 xmlRegFreeAtom(ctxt->atoms[i]);
919 xmlFree(ctxt->atoms);
920 }
921 if (ctxt->counters != NULL)
922 xmlFree(ctxt->counters);
923 xmlFree(ctxt);
924}
925
926/************************************************************************
927 * *
928 * Display of Data structures *
929 * *
930 ************************************************************************/
931
932static void
933xmlRegPrintAtomType(FILE *output, xmlRegAtomType type) {
934 switch (type) {
935 case XML_REGEXP_EPSILON:
936 fprintf(output, "epsilon "); break;
937 case XML_REGEXP_CHARVAL:
938 fprintf(output, "charval "); break;
939 case XML_REGEXP_RANGES:
940 fprintf(output, "ranges "); break;
941 case XML_REGEXP_SUBREG:
942 fprintf(output, "subexpr "); break;
943 case XML_REGEXP_STRING:
944 fprintf(output, "string "); break;
945 case XML_REGEXP_ANYCHAR:
946 fprintf(output, "anychar "); break;
947 case XML_REGEXP_ANYSPACE:
948 fprintf(output, "anyspace "); break;
949 case XML_REGEXP_NOTSPACE:
950 fprintf(output, "notspace "); break;
951 case XML_REGEXP_INITNAME:
952 fprintf(output, "initname "); break;
953 case XML_REGEXP_NOTINITNAME:
954 fprintf(output, "notinitname "); break;
955 case XML_REGEXP_NAMECHAR:
956 fprintf(output, "namechar "); break;
957 case XML_REGEXP_NOTNAMECHAR:
958 fprintf(output, "notnamechar "); break;
959 case XML_REGEXP_DECIMAL:
960 fprintf(output, "decimal "); break;
961 case XML_REGEXP_NOTDECIMAL:
962 fprintf(output, "notdecimal "); break;
963 case XML_REGEXP_REALCHAR:
964 fprintf(output, "realchar "); break;
965 case XML_REGEXP_NOTREALCHAR:
966 fprintf(output, "notrealchar "); break;
967 case XML_REGEXP_LETTER:
968 fprintf(output, "LETTER "); break;
969 case XML_REGEXP_LETTER_UPPERCASE:
970 fprintf(output, "LETTER_UPPERCASE "); break;
971 case XML_REGEXP_LETTER_LOWERCASE:
972 fprintf(output, "LETTER_LOWERCASE "); break;
973 case XML_REGEXP_LETTER_TITLECASE:
974 fprintf(output, "LETTER_TITLECASE "); break;
975 case XML_REGEXP_LETTER_MODIFIER:
976 fprintf(output, "LETTER_MODIFIER "); break;
977 case XML_REGEXP_LETTER_OTHERS:
978 fprintf(output, "LETTER_OTHERS "); break;
979 case XML_REGEXP_MARK:
980 fprintf(output, "MARK "); break;
981 case XML_REGEXP_MARK_NONSPACING:
982 fprintf(output, "MARK_NONSPACING "); break;
983 case XML_REGEXP_MARK_SPACECOMBINING:
984 fprintf(output, "MARK_SPACECOMBINING "); break;
985 case XML_REGEXP_MARK_ENCLOSING:
986 fprintf(output, "MARK_ENCLOSING "); break;
987 case XML_REGEXP_NUMBER:
988 fprintf(output, "NUMBER "); break;
989 case XML_REGEXP_NUMBER_DECIMAL:
990 fprintf(output, "NUMBER_DECIMAL "); break;
991 case XML_REGEXP_NUMBER_LETTER:
992 fprintf(output, "NUMBER_LETTER "); break;
993 case XML_REGEXP_NUMBER_OTHERS:
994 fprintf(output, "NUMBER_OTHERS "); break;
995 case XML_REGEXP_PUNCT:
996 fprintf(output, "PUNCT "); break;
997 case XML_REGEXP_PUNCT_CONNECTOR:
998 fprintf(output, "PUNCT_CONNECTOR "); break;
999 case XML_REGEXP_PUNCT_DASH:
1000 fprintf(output, "PUNCT_DASH "); break;
1001 case XML_REGEXP_PUNCT_OPEN:
1002 fprintf(output, "PUNCT_OPEN "); break;
1003 case XML_REGEXP_PUNCT_CLOSE:
1004 fprintf(output, "PUNCT_CLOSE "); break;
1005 case XML_REGEXP_PUNCT_INITQUOTE:
1006 fprintf(output, "PUNCT_INITQUOTE "); break;
1007 case XML_REGEXP_PUNCT_FINQUOTE:
1008 fprintf(output, "PUNCT_FINQUOTE "); break;
1009 case XML_REGEXP_PUNCT_OTHERS:
1010 fprintf(output, "PUNCT_OTHERS "); break;
1011 case XML_REGEXP_SEPAR:
1012 fprintf(output, "SEPAR "); break;
1013 case XML_REGEXP_SEPAR_SPACE:
1014 fprintf(output, "SEPAR_SPACE "); break;
1015 case XML_REGEXP_SEPAR_LINE:
1016 fprintf(output, "SEPAR_LINE "); break;
1017 case XML_REGEXP_SEPAR_PARA:
1018 fprintf(output, "SEPAR_PARA "); break;
1019 case XML_REGEXP_SYMBOL:
1020 fprintf(output, "SYMBOL "); break;
1021 case XML_REGEXP_SYMBOL_MATH:
1022 fprintf(output, "SYMBOL_MATH "); break;
1023 case XML_REGEXP_SYMBOL_CURRENCY:
1024 fprintf(output, "SYMBOL_CURRENCY "); break;
1025 case XML_REGEXP_SYMBOL_MODIFIER:
1026 fprintf(output, "SYMBOL_MODIFIER "); break;
1027 case XML_REGEXP_SYMBOL_OTHERS:
1028 fprintf(output, "SYMBOL_OTHERS "); break;
1029 case XML_REGEXP_OTHER:
1030 fprintf(output, "OTHER "); break;
1031 case XML_REGEXP_OTHER_CONTROL:
1032 fprintf(output, "OTHER_CONTROL "); break;
1033 case XML_REGEXP_OTHER_FORMAT:
1034 fprintf(output, "OTHER_FORMAT "); break;
1035 case XML_REGEXP_OTHER_PRIVATE:
1036 fprintf(output, "OTHER_PRIVATE "); break;
1037 case XML_REGEXP_OTHER_NA:
1038 fprintf(output, "OTHER_NA "); break;
1039 case XML_REGEXP_BLOCK_NAME:
1040 fprintf(output, "BLOCK "); break;
1041 }
1042}
1043
1044static void
1045xmlRegPrintQuantType(FILE *output, xmlRegQuantType type) {
1046 switch (type) {
1047 case XML_REGEXP_QUANT_EPSILON:
1048 fprintf(output, "epsilon "); break;
1049 case XML_REGEXP_QUANT_ONCE:
1050 fprintf(output, "once "); break;
1051 case XML_REGEXP_QUANT_OPT:
1052 fprintf(output, "? "); break;
1053 case XML_REGEXP_QUANT_MULT:
1054 fprintf(output, "* "); break;
1055 case XML_REGEXP_QUANT_PLUS:
1056 fprintf(output, "+ "); break;
1057 case XML_REGEXP_QUANT_RANGE:
1058 fprintf(output, "range "); break;
1059 case XML_REGEXP_QUANT_ONCEONLY:
1060 fprintf(output, "onceonly "); break;
1061 case XML_REGEXP_QUANT_ALL:
1062 fprintf(output, "all "); break;
1063 }
1064}
1065static void
1066xmlRegPrintRange(FILE *output, xmlRegRangePtr range) {
1067 fprintf(output, " range: ");
1068 if (range->neg)
1069 fprintf(output, "negative ");
1070 xmlRegPrintAtomType(output, range->type);
1071 fprintf(output, "%c - %c\n", range->start, range->end);
1072}
1073
1074static void
1075xmlRegPrintAtom(FILE *output, xmlRegAtomPtr atom) {
1076 fprintf(output, " atom: ");
1077 if (atom == NULL) {
1078 fprintf(output, "NULL\n");
1079 return;
1080 }
1081 if (atom->neg)
1082 fprintf(output, "not ");
1083 xmlRegPrintAtomType(output, atom->type);
1084 xmlRegPrintQuantType(output, atom->quant);
1085 if (atom->quant == XML_REGEXP_QUANT_RANGE)
1086 fprintf(output, "%d-%d ", atom->min, atom->max);
1087 if (atom->type == XML_REGEXP_STRING)
1088 fprintf(output, "'%s' ", (char *) atom->valuep);
1089 if (atom->type == XML_REGEXP_CHARVAL)
1090 fprintf(output, "char %c\n", atom->codepoint);
1091 else if (atom->type == XML_REGEXP_RANGES) {
1092 int i;
1093 fprintf(output, "%d entries\n", atom->nbRanges);
1094 for (i = 0; i < atom->nbRanges;i++)
1095 xmlRegPrintRange(output, atom->ranges[i]);
1096 } else if (atom->type == XML_REGEXP_SUBREG) {
1097 fprintf(output, "start %d end %d\n", atom->start->no, atom->stop->no);
1098 } else {
1099 fprintf(output, "\n");
1100 }
1101}
1102
1103static void
1104xmlRegPrintTrans(FILE *output, xmlRegTransPtr trans) {
1105 fprintf(output, " trans: ");
1106 if (trans == NULL) {
1107 fprintf(output, "NULL\n");
1108 return;
1109 }
1110 if (trans->to < 0) {
1111 fprintf(output, "removed\n");
1112 return;
1113 }
1114 if (trans->nd != 0) {
1115 if (trans->nd == 2)
1116 fprintf(output, "last not determinist, ");
1117 else
1118 fprintf(output, "not determinist, ");
1119 }
1120 if (trans->counter >= 0) {
1121 fprintf(output, "counted %d, ", trans->counter);
1122 }
1123 if (trans->count == REGEXP_ALL_COUNTER) {
1124 fprintf(output, "all transition, ");
1125 } else if (trans->count >= 0) {
1126 fprintf(output, "count based %d, ", trans->count);
1127 }
1128 if (trans->atom == NULL) {
1129 fprintf(output, "epsilon to %d\n", trans->to);
1130 return;
1131 }
1132 if (trans->atom->type == XML_REGEXP_CHARVAL)
1133 fprintf(output, "char %c ", trans->atom->codepoint);
1134 fprintf(output, "atom %d, to %d\n", trans->atom->no, trans->to);
1135}
1136
1137static void
1138xmlRegPrintState(FILE *output, xmlRegStatePtr state) {
1139 int i;
1140
1141 fprintf(output, " state: ");
1142 if (state == NULL) {
1143 fprintf(output, "NULL\n");
1144 return;
1145 }
1146 if (state->type == XML_REGEXP_START_STATE)
1147 fprintf(output, "START ");
1148 if (state->type == XML_REGEXP_FINAL_STATE)
1149 fprintf(output, "FINAL ");
1150
1151 fprintf(output, "%d, %d transitions:\n", state->no, state->nbTrans);
1152 for (i = 0;i < state->nbTrans; i++) {
1153 xmlRegPrintTrans(output, &(state->trans[i]));
1154 }
1155}
1156
1157#ifdef DEBUG_REGEXP_GRAPH
1158static void
1159xmlRegPrintCtxt(FILE *output, xmlRegParserCtxtPtr ctxt) {
1160 int i;
1161
1162 fprintf(output, " ctxt: ");
1163 if (ctxt == NULL) {
1164 fprintf(output, "NULL\n");
1165 return;
1166 }
1167 fprintf(output, "'%s' ", ctxt->string);
1168 if (ctxt->error)
1169 fprintf(output, "error ");
1170 if (ctxt->neg)
1171 fprintf(output, "neg ");
1172 fprintf(output, "\n");
1173 fprintf(output, "%d atoms:\n", ctxt->nbAtoms);
1174 for (i = 0;i < ctxt->nbAtoms; i++) {
1175 fprintf(output, " %02d ", i);
1176 xmlRegPrintAtom(output, ctxt->atoms[i]);
1177 }
1178 if (ctxt->atom != NULL) {
1179 fprintf(output, "current atom:\n");
1180 xmlRegPrintAtom(output, ctxt->atom);
1181 }
1182 fprintf(output, "%d states:", ctxt->nbStates);
1183 if (ctxt->start != NULL)
1184 fprintf(output, " start: %d", ctxt->start->no);
1185 if (ctxt->end != NULL)
1186 fprintf(output, " end: %d", ctxt->end->no);
1187 fprintf(output, "\n");
1188 for (i = 0;i < ctxt->nbStates; i++) {
1189 xmlRegPrintState(output, ctxt->states[i]);
1190 }
1191 fprintf(output, "%d counters:\n", ctxt->nbCounters);
1192 for (i = 0;i < ctxt->nbCounters; i++) {
1193 fprintf(output, " %d: min %d max %d\n", i, ctxt->counters[i].min,
1194 ctxt->counters[i].max);
1195 }
1196}
1197#endif
1198
1199/************************************************************************
1200 * *
1201 * Finite Automata structures manipulations *
1202 * *
1203 ************************************************************************/
1204
1205static void
1206xmlRegAtomAddRange(xmlRegParserCtxtPtr ctxt, xmlRegAtomPtr atom,
1207 int neg, xmlRegAtomType type, int start, int end,
1208 xmlChar *blockName) {
1209 xmlRegRangePtr range;
1210
1211 if (atom == NULL) {
1212 ERROR("add range: atom is NULL");
1213 return;
1214 }
1215 if (atom->type != XML_REGEXP_RANGES) {
1216 ERROR("add range: atom is not ranges");
1217 return;
1218 }
1219 if (atom->maxRanges == 0) {
1220 atom->maxRanges = 4;
1221 atom->ranges = (xmlRegRangePtr *) xmlMalloc(atom->maxRanges *
1222 sizeof(xmlRegRangePtr));
1223 if (atom->ranges == NULL) {
1224 xmlRegexpErrMemory(ctxt, "adding ranges");
1225 atom->maxRanges = 0;
1226 return;
1227 }
1228 } else if (atom->nbRanges >= atom->maxRanges) {
1229 xmlRegRangePtr *tmp;
1230 atom->maxRanges *= 2;
1231 tmp = (xmlRegRangePtr *) xmlRealloc(atom->ranges, atom->maxRanges *
1232 sizeof(xmlRegRangePtr));
1233 if (tmp == NULL) {
1234 xmlRegexpErrMemory(ctxt, "adding ranges");
1235 atom->maxRanges /= 2;
1236 return;
1237 }
1238 atom->ranges = tmp;
1239 }
1240 range = xmlRegNewRange(ctxt, neg, type, start, end);
1241 if (range == NULL)
1242 return;
1243 range->blockName = blockName;
1244 atom->ranges[atom->nbRanges++] = range;
1245
1246}
1247
1248static int
1249xmlRegGetCounter(xmlRegParserCtxtPtr ctxt) {
1250 if (ctxt->maxCounters == 0) {
1251 ctxt->maxCounters = 4;
1252 ctxt->counters = (xmlRegCounter *) xmlMalloc(ctxt->maxCounters *
1253 sizeof(xmlRegCounter));
1254 if (ctxt->counters == NULL) {
1255 xmlRegexpErrMemory(ctxt, "allocating counter");
1256 ctxt->maxCounters = 0;
1257 return(-1);
1258 }
1259 } else if (ctxt->nbCounters >= ctxt->maxCounters) {
1260 xmlRegCounter *tmp;
1261 ctxt->maxCounters *= 2;
1262 tmp = (xmlRegCounter *) xmlRealloc(ctxt->counters, ctxt->maxCounters *
1263 sizeof(xmlRegCounter));
1264 if (tmp == NULL) {
1265 xmlRegexpErrMemory(ctxt, "allocating counter");
1266 ctxt->maxCounters /= 2;
1267 return(-1);
1268 }
1269 ctxt->counters = tmp;
1270 }
1271 ctxt->counters[ctxt->nbCounters].min = -1;
1272 ctxt->counters[ctxt->nbCounters].max = -1;
1273 return(ctxt->nbCounters++);
1274}
1275
1276static int
1277xmlRegAtomPush(xmlRegParserCtxtPtr ctxt, xmlRegAtomPtr atom) {
1278 if (atom == NULL) {
1279 ERROR("atom push: atom is NULL");
1280 return(-1);
1281 }
1282 if (ctxt->maxAtoms == 0) {
1283 ctxt->maxAtoms = 4;
1284 ctxt->atoms = (xmlRegAtomPtr *) xmlMalloc(ctxt->maxAtoms *
1285 sizeof(xmlRegAtomPtr));
1286 if (ctxt->atoms == NULL) {
1287 xmlRegexpErrMemory(ctxt, "pushing atom");
1288 ctxt->maxAtoms = 0;
1289 return(-1);
1290 }
1291 } else if (ctxt->nbAtoms >= ctxt->maxAtoms) {
1292 xmlRegAtomPtr *tmp;
1293 ctxt->maxAtoms *= 2;
1294 tmp = (xmlRegAtomPtr *) xmlRealloc(ctxt->atoms, ctxt->maxAtoms *
1295 sizeof(xmlRegAtomPtr));
1296 if (tmp == NULL) {
1297 xmlRegexpErrMemory(ctxt, "allocating counter");
1298 ctxt->maxAtoms /= 2;
1299 return(-1);
1300 }
1301 ctxt->atoms = tmp;
1302 }
1303 atom->no = ctxt->nbAtoms;
1304 ctxt->atoms[ctxt->nbAtoms++] = atom;
1305 return(0);
1306}
1307
1308static void
1309xmlRegStateAddTransTo(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr target,
1310 int from) {
1311 if (target->maxTransTo == 0) {
1312 target->maxTransTo = 8;
1313 target->transTo = (int *) xmlMalloc(target->maxTransTo *
1314 sizeof(int));
1315 if (target->transTo == NULL) {
1316 xmlRegexpErrMemory(ctxt, "adding transition");
1317 target->maxTransTo = 0;
1318 return;
1319 }
1320 } else if (target->nbTransTo >= target->maxTransTo) {
1321 int *tmp;
1322 target->maxTransTo *= 2;
1323 tmp = (int *) xmlRealloc(target->transTo, target->maxTransTo *
1324 sizeof(int));
1325 if (tmp == NULL) {
1326 xmlRegexpErrMemory(ctxt, "adding transition");
1327 target->maxTransTo /= 2;
1328 return;
1329 }
1330 target->transTo = tmp;
1331 }
1332 target->transTo[target->nbTransTo] = from;
1333 target->nbTransTo++;
1334}
1335
1336static void
1337xmlRegStateAddTrans(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr state,
1338 xmlRegAtomPtr atom, xmlRegStatePtr target,
1339 int counter, int count) {
1340
1341 int nrtrans;
1342
1343 if (state == NULL) {
1344 ERROR("add state: state is NULL");
1345 return;
1346 }
1347 if (target == NULL) {
1348 ERROR("add state: target is NULL");
1349 return;
1350 }
1351 /*
1352 * Other routines follow the philosophy 'When in doubt, add a transition'
1353 * so we check here whether such a transition is already present and, if
1354 * so, silently ignore this request.
1355 */
1356
1357 for (nrtrans = state->nbTrans - 1; nrtrans >= 0; nrtrans--) {
1358 xmlRegTransPtr trans = &(state->trans[nrtrans]);
1359 if ((trans->atom == atom) &&
1360 (trans->to == target->no) &&
1361 (trans->counter == counter) &&
1362 (trans->count == count)) {
1363#ifdef DEBUG_REGEXP_GRAPH
1364 printf("Ignoring duplicate transition from %d to %d\n",
1365 state->no, target->no);
1366#endif
1367 return;
1368 }
1369 }
1370
1371 if (state->maxTrans == 0) {
1372 state->maxTrans = 8;
1373 state->trans = (xmlRegTrans *) xmlMalloc(state->maxTrans *
1374 sizeof(xmlRegTrans));
1375 if (state->trans == NULL) {
1376 xmlRegexpErrMemory(ctxt, "adding transition");
1377 state->maxTrans = 0;
1378 return;
1379 }
1380 } else if (state->nbTrans >= state->maxTrans) {
1381 xmlRegTrans *tmp;
1382 state->maxTrans *= 2;
1383 tmp = (xmlRegTrans *) xmlRealloc(state->trans, state->maxTrans *
1384 sizeof(xmlRegTrans));
1385 if (tmp == NULL) {
1386 xmlRegexpErrMemory(ctxt, "adding transition");
1387 state->maxTrans /= 2;
1388 return;
1389 }
1390 state->trans = tmp;
1391 }
1392#ifdef DEBUG_REGEXP_GRAPH
1393 printf("Add trans from %d to %d ", state->no, target->no);
1394 if (count == REGEXP_ALL_COUNTER)
1395 printf("all transition\n");
1396 else if (count >= 0)
1397 printf("count based %d\n", count);
1398 else if (counter >= 0)
1399 printf("counted %d\n", counter);
1400 else if (atom == NULL)
1401 printf("epsilon transition\n");
1402 else if (atom != NULL)
1403 xmlRegPrintAtom(stdout, atom);
1404#endif
1405
1406 state->trans[state->nbTrans].atom = atom;
1407 state->trans[state->nbTrans].to = target->no;
1408 state->trans[state->nbTrans].counter = counter;
1409 state->trans[state->nbTrans].count = count;
1410 state->trans[state->nbTrans].nd = 0;
1411 state->nbTrans++;
1412 xmlRegStateAddTransTo(ctxt, target, state->no);
1413}
1414
1415static int
1416xmlRegStatePush(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr state) {
1417 if (state == NULL) return(-1);
1418 if (ctxt->maxStates == 0) {
1419 ctxt->maxStates = 4;
1420 ctxt->states = (xmlRegStatePtr *) xmlMalloc(ctxt->maxStates *
1421 sizeof(xmlRegStatePtr));
1422 if (ctxt->states == NULL) {
1423 xmlRegexpErrMemory(ctxt, "adding state");
1424 ctxt->maxStates = 0;
1425 return(-1);
1426 }
1427 } else if (ctxt->nbStates >= ctxt->maxStates) {
1428 xmlRegStatePtr *tmp;
1429 ctxt->maxStates *= 2;
1430 tmp = (xmlRegStatePtr *) xmlRealloc(ctxt->states, ctxt->maxStates *
1431 sizeof(xmlRegStatePtr));
1432 if (tmp == NULL) {
1433 xmlRegexpErrMemory(ctxt, "adding state");
1434 ctxt->maxStates /= 2;
1435 return(-1);
1436 }
1437 ctxt->states = tmp;
1438 }
1439 state->no = ctxt->nbStates;
1440 ctxt->states[ctxt->nbStates++] = state;
1441 return(0);
1442}
1443
1444/**
1445 * xmlFAGenerateAllTransition:
1446 * @ctxt: a regexp parser context
1447 * @from: the from state
1448 * @to: the target state or NULL for building a new one
1449 * @lax:
1450 *
1451 */
1452static void
1453xmlFAGenerateAllTransition(xmlRegParserCtxtPtr ctxt,
1454 xmlRegStatePtr from, xmlRegStatePtr to,
1455 int lax) {
1456 if (to == NULL) {
1457 to = xmlRegNewState(ctxt);
1458 xmlRegStatePush(ctxt, to);
1459 ctxt->state = to;
1460 }
1461 if (lax)
1462 xmlRegStateAddTrans(ctxt, from, NULL, to, -1, REGEXP_ALL_LAX_COUNTER);
1463 else
1464 xmlRegStateAddTrans(ctxt, from, NULL, to, -1, REGEXP_ALL_COUNTER);
1465}
1466
1467/**
1468 * xmlFAGenerateEpsilonTransition:
1469 * @ctxt: a regexp parser context
1470 * @from: the from state
1471 * @to: the target state or NULL for building a new one
1472 *
1473 */
1474static void
1475xmlFAGenerateEpsilonTransition(xmlRegParserCtxtPtr ctxt,
1476 xmlRegStatePtr from, xmlRegStatePtr to) {
1477 if (to == NULL) {
1478 to = xmlRegNewState(ctxt);
1479 xmlRegStatePush(ctxt, to);
1480 ctxt->state = to;
1481 }
1482 xmlRegStateAddTrans(ctxt, from, NULL, to, -1, -1);
1483}
1484
1485/**
1486 * xmlFAGenerateCountedEpsilonTransition:
1487 * @ctxt: a regexp parser context
1488 * @from: the from state
1489 * @to: the target state or NULL for building a new one
1490 * counter: the counter for that transition
1491 *
1492 */
1493static void
1494xmlFAGenerateCountedEpsilonTransition(xmlRegParserCtxtPtr ctxt,
1495 xmlRegStatePtr from, xmlRegStatePtr to, int counter) {
1496 if (to == NULL) {
1497 to = xmlRegNewState(ctxt);
1498 xmlRegStatePush(ctxt, to);
1499 ctxt->state = to;
1500 }
1501 xmlRegStateAddTrans(ctxt, from, NULL, to, counter, -1);
1502}
1503
1504/**
1505 * xmlFAGenerateCountedTransition:
1506 * @ctxt: a regexp parser context
1507 * @from: the from state
1508 * @to: the target state or NULL for building a new one
1509 * counter: the counter for that transition
1510 *
1511 */
1512static void
1513xmlFAGenerateCountedTransition(xmlRegParserCtxtPtr ctxt,
1514 xmlRegStatePtr from, xmlRegStatePtr to, int counter) {
1515 if (to == NULL) {
1516 to = xmlRegNewState(ctxt);
1517 xmlRegStatePush(ctxt, to);
1518 ctxt->state = to;
1519 }
1520 xmlRegStateAddTrans(ctxt, from, NULL, to, -1, counter);
1521}
1522
1523/**
1524 * xmlFAGenerateTransitions:
1525 * @ctxt: a regexp parser context
1526 * @from: the from state
1527 * @to: the target state or NULL for building a new one
1528 * @atom: the atom generating the transition
1529 *
1530 * Returns 0 if success and -1 in case of error.
1531 */
1532static int
1533xmlFAGenerateTransitions(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr from,
1534 xmlRegStatePtr to, xmlRegAtomPtr atom) {
1535 if (atom == NULL) {
1536 ERROR("genrate transition: atom == NULL");
1537 return(-1);
1538 }
1539 if (atom->type == XML_REGEXP_SUBREG) {
1540 /*
1541 * this is a subexpression handling one should not need to
1542 * create a new node except for XML_REGEXP_QUANT_RANGE.
1543 */
1544 if (xmlRegAtomPush(ctxt, atom) < 0) {
1545 return(-1);
1546 }
1547 if ((to != NULL) && (atom->stop != to) &&
1548 (atom->quant != XML_REGEXP_QUANT_RANGE)) {
1549 /*
1550 * Generate an epsilon transition to link to the target
1551 */
1552 xmlFAGenerateEpsilonTransition(ctxt, atom->stop, to);
1553#ifdef DV
1554 } else if ((to == NULL) && (atom->quant != XML_REGEXP_QUANT_RANGE) &&
1555 (atom->quant != XML_REGEXP_QUANT_ONCE)) {
1556 to = xmlRegNewState(ctxt);
1557 xmlRegStatePush(ctxt, to);
1558 ctxt->state = to;
1559 xmlFAGenerateEpsilonTransition(ctxt, atom->stop, to);
1560#endif
1561 }
1562 switch (atom->quant) {
1563 case XML_REGEXP_QUANT_OPT:
1564 atom->quant = XML_REGEXP_QUANT_ONCE;
1565 /*
1566 * transition done to the state after end of atom.
1567 * 1. set transition from atom start to new state
1568 * 2. set transition from atom end to this state.
1569 */
1570 xmlFAGenerateEpsilonTransition(ctxt, atom->start, 0);
1571 xmlFAGenerateEpsilonTransition(ctxt, atom->stop, ctxt->state);
1572 break;
1573 case XML_REGEXP_QUANT_MULT:
1574 atom->quant = XML_REGEXP_QUANT_ONCE;
1575 xmlFAGenerateEpsilonTransition(ctxt, atom->start, atom->stop);
1576 xmlFAGenerateEpsilonTransition(ctxt, atom->stop, atom->start);
1577 break;
1578 case XML_REGEXP_QUANT_PLUS:
1579 atom->quant = XML_REGEXP_QUANT_ONCE;
1580 xmlFAGenerateEpsilonTransition(ctxt, atom->stop, atom->start);
1581 break;
1582 case XML_REGEXP_QUANT_RANGE: {
1583 int counter;
1584 xmlRegStatePtr inter, newstate;
1585
1586 /*
1587 * create the final state now if needed
1588 */
1589 if (to != NULL) {
1590 newstate = to;
1591 } else {
1592 newstate = xmlRegNewState(ctxt);
1593 xmlRegStatePush(ctxt, newstate);
1594 }
1595
1596 /*
1597 * The principle here is to use counted transition
1598 * to avoid explosion in the number of states in the
1599 * graph. This is clearly more complex but should not
1600 * be exploitable at runtime.
1601 */
1602 if ((atom->min == 0) && (atom->start0 == NULL)) {
1603 xmlRegAtomPtr copy;
1604 /*
1605 * duplicate a transition based on atom to count next
1606 * occurences after 1. We cannot loop to atom->start
1607 * directly because we need an epsilon transition to
1608 * newstate.
1609 */
1610 /* ???? For some reason it seems we never reach that
1611 case, I suppose this got optimized out before when
1612 building the automata */
1613 copy = xmlRegCopyAtom(ctxt, atom);
1614 if (copy == NULL)
1615 return(-1);
1616 copy->quant = XML_REGEXP_QUANT_ONCE;
1617 copy->min = 0;
1618 copy->max = 0;
1619
1620 if (xmlFAGenerateTransitions(ctxt, atom->start, NULL, copy)
1621 < 0)
1622 return(-1);
1623 inter = ctxt->state;
1624 counter = xmlRegGetCounter(ctxt);
1625 ctxt->counters[counter].min = atom->min - 1;
1626 ctxt->counters[counter].max = atom->max - 1;
1627 /* count the number of times we see it again */
1628 xmlFAGenerateCountedEpsilonTransition(ctxt, inter,
1629 atom->stop, counter);
1630 /* allow a way out based on the count */
1631 xmlFAGenerateCountedTransition(ctxt, inter,
1632 newstate, counter);
1633 /* and also allow a direct exit for 0 */
1634 xmlFAGenerateEpsilonTransition(ctxt, atom->start,
1635 newstate);
1636 } else {
1637 /*
1638 * either we need the atom at least once or there
1639 * is an atom->start0 allowing to easilly plug the
1640 * epsilon transition.
1641 */
1642 counter = xmlRegGetCounter(ctxt);
1643 ctxt->counters[counter].min = atom->min - 1;
1644 ctxt->counters[counter].max = atom->max - 1;
1645 /* count the number of times we see it again */
1646 xmlFAGenerateCountedEpsilonTransition(ctxt, atom->stop,
1647 atom->start, counter);
1648 /* allow a way out based on the count */
1649 xmlFAGenerateCountedTransition(ctxt, atom->stop,
1650 newstate, counter);
1651 /* and if needed allow a direct exit for 0 */
1652 if (atom->min == 0)
1653 xmlFAGenerateEpsilonTransition(ctxt, atom->start0,
1654 newstate);
1655
1656 }
1657 atom->min = 0;
1658 atom->max = 0;
1659 atom->quant = XML_REGEXP_QUANT_ONCE;
1660 ctxt->state = newstate;
1661 }
1662 default:
1663 break;
1664 }
1665 return(0);
1666 }
1667 if ((atom->min == 0) && (atom->max == 0) &&
1668 (atom->quant == XML_REGEXP_QUANT_RANGE)) {
1669 /*
1670 * we can discard the atom and generate an epsilon transition instead
1671 */
1672 if (to == NULL) {
1673 to = xmlRegNewState(ctxt);
1674 if (to != NULL)
1675 xmlRegStatePush(ctxt, to);
1676 else {
1677 return(-1);
1678 }
1679 }
1680 xmlFAGenerateEpsilonTransition(ctxt, from, to);
1681 ctxt->state = to;
1682 xmlRegFreeAtom(atom);
1683 return(0);
1684 }
1685 if (to == NULL) {
1686 to = xmlRegNewState(ctxt);
1687 if (to != NULL)
1688 xmlRegStatePush(ctxt, to);
1689 else {
1690 return(-1);
1691 }
1692 }
1693 if (xmlRegAtomPush(ctxt, atom) < 0) {
1694 return(-1);
1695 }
1696 xmlRegStateAddTrans(ctxt, from, atom, to, -1, -1);
1697 ctxt->state = to;
1698 switch (atom->quant) {
1699 case XML_REGEXP_QUANT_OPT:
1700 atom->quant = XML_REGEXP_QUANT_ONCE;
1701 xmlFAGenerateEpsilonTransition(ctxt, from, to);
1702 break;
1703 case XML_REGEXP_QUANT_MULT:
1704 atom->quant = XML_REGEXP_QUANT_ONCE;
1705 xmlFAGenerateEpsilonTransition(ctxt, from, to);
1706 xmlRegStateAddTrans(ctxt, to, atom, to, -1, -1);
1707 break;
1708 case XML_REGEXP_QUANT_PLUS:
1709 atom->quant = XML_REGEXP_QUANT_ONCE;
1710 xmlRegStateAddTrans(ctxt, to, atom, to, -1, -1);
1711 break;
1712 case XML_REGEXP_QUANT_RANGE:
1713 if (atom->min == 0) {
1714 xmlFAGenerateEpsilonTransition(ctxt, from, to);
1715 }
1716 break;
1717 default:
1718 break;
1719 }
1720 return(0);
1721}
1722
1723/**
1724 * xmlFAReduceEpsilonTransitions:
1725 * @ctxt: a regexp parser context
1726 * @fromnr: the from state
1727 * @tonr: the to state
1728 * @counter: should that transition be associated to a counted
1729 *
1730 */
1731static void
1732xmlFAReduceEpsilonTransitions(xmlRegParserCtxtPtr ctxt, int fromnr,
1733 int tonr, int counter) {
1734 int transnr;
1735 xmlRegStatePtr from;
1736 xmlRegStatePtr to;
1737
1738#ifdef DEBUG_REGEXP_GRAPH
1739 printf("xmlFAReduceEpsilonTransitions(%d, %d)\n", fromnr, tonr);
1740#endif
1741 from = ctxt->states[fromnr];
1742 if (from == NULL)
1743 return;
1744 to = ctxt->states[tonr];
1745 if (to == NULL)
1746 return;
1747 if ((to->mark == XML_REGEXP_MARK_START) ||
1748 (to->mark == XML_REGEXP_MARK_VISITED))
1749 return;
1750
1751 to->mark = XML_REGEXP_MARK_VISITED;
1752 if (to->type == XML_REGEXP_FINAL_STATE) {
1753#ifdef DEBUG_REGEXP_GRAPH
1754 printf("State %d is final, so %d becomes final\n", tonr, fromnr);
1755#endif
1756 from->type = XML_REGEXP_FINAL_STATE;
1757 }
1758 for (transnr = 0;transnr < to->nbTrans;transnr++) {
1759 if (to->trans[transnr].to < 0)
1760 continue;
1761 if (to->trans[transnr].atom == NULL) {
1762 /*
1763 * Don't remove counted transitions
1764 * Don't loop either
1765 */
1766 if (to->trans[transnr].to != fromnr) {
1767 if (to->trans[transnr].count >= 0) {
1768 int newto = to->trans[transnr].to;
1769
1770 xmlRegStateAddTrans(ctxt, from, NULL,
1771 ctxt->states[newto],
1772 -1, to->trans[transnr].count);
1773 } else {
1774#ifdef DEBUG_REGEXP_GRAPH
1775 printf("Found epsilon trans %d from %d to %d\n",
1776 transnr, tonr, to->trans[transnr].to);
1777#endif
1778 if (to->trans[transnr].counter >= 0) {
1779 xmlFAReduceEpsilonTransitions(ctxt, fromnr,
1780 to->trans[transnr].to,
1781 to->trans[transnr].counter);
1782 } else {
1783 xmlFAReduceEpsilonTransitions(ctxt, fromnr,
1784 to->trans[transnr].to,
1785 counter);
1786 }
1787 }
1788 }
1789 } else {
1790 int newto = to->trans[transnr].to;
1791
1792 if (to->trans[transnr].counter >= 0) {
1793 xmlRegStateAddTrans(ctxt, from, to->trans[transnr].atom,
1794 ctxt->states[newto],
1795 to->trans[transnr].counter, -1);
1796 } else {
1797 xmlRegStateAddTrans(ctxt, from, to->trans[transnr].atom,
1798 ctxt->states[newto], counter, -1);
1799 }
1800 }
1801 }
1802 to->mark = XML_REGEXP_MARK_NORMAL;
1803}
1804
1805/**
1806 * xmlFAEliminateSimpleEpsilonTransitions:
1807 * @ctxt: a regexp parser context
1808 *
1809 * Eliminating general epsilon transitions can get costly in the general
1810 * algorithm due to the large amount of generated new transitions and
1811 * associated comparisons. However for simple epsilon transition used just
1812 * to separate building blocks when generating the automata this can be
1813 * reduced to state elimination:
1814 * - if there exists an epsilon from X to Y
1815 * - if there is no other transition from X
1816 * then X and Y are semantically equivalent and X can be eliminated
1817 * If X is the start state then make Y the start state, else replace the
1818 * target of all transitions to X by transitions to Y.
1819 */
1820static void
1821xmlFAEliminateSimpleEpsilonTransitions(xmlRegParserCtxtPtr ctxt) {
1822 int statenr, i, j, newto;
1823 xmlRegStatePtr state, tmp;
1824
1825 for (statenr = 0;statenr < ctxt->nbStates;statenr++) {
1826 state = ctxt->states[statenr];
1827 if (state == NULL)
1828 continue;
1829 if (state->nbTrans != 1)
1830 continue;
1831 if (state->type == XML_REGEXP_UNREACH_STATE)
1832 continue;
1833 /* is the only transition out a basic transition */
1834 if ((state->trans[0].atom == NULL) &&
1835 (state->trans[0].to >= 0) &&
1836 (state->trans[0].to != statenr) &&
1837 (state->trans[0].counter < 0) &&
1838 (state->trans[0].count < 0)) {
1839 newto = state->trans[0].to;
1840
1841 if (state->type == XML_REGEXP_START_STATE) {
1842#ifdef DEBUG_REGEXP_GRAPH
1843 printf("Found simple epsilon trans from start %d to %d\n",
1844 statenr, newto);
1845#endif
1846 } else {
1847#ifdef DEBUG_REGEXP_GRAPH
1848 printf("Found simple epsilon trans from %d to %d\n",
1849 statenr, newto);
1850#endif
1851 for (i = 0;i < state->nbTransTo;i++) {
1852 tmp = ctxt->states[state->transTo[i]];
1853 for (j = 0;j < tmp->nbTrans;j++) {
1854 if (tmp->trans[j].to == statenr) {
1855#ifdef DEBUG_REGEXP_GRAPH
1856 printf("Changed transition %d on %d to go to %d\n",
1857 j, tmp->no, newto);
1858#endif
1859 tmp->trans[j].to = -1;
1860 xmlRegStateAddTrans(ctxt, tmp, tmp->trans[j].atom,
1861 ctxt->states[newto],
1862 tmp->trans[j].counter,
1863 tmp->trans[j].count);
1864 }
1865 }
1866 }
1867 if (state->type == XML_REGEXP_FINAL_STATE)
1868 ctxt->states[newto]->type = XML_REGEXP_FINAL_STATE;
1869 /* eliminate the transition completely */
1870 state->nbTrans = 0;
1871
1872 state->type = XML_REGEXP_UNREACH_STATE;
1873
1874 }
1875
1876 }
1877 }
1878}
1879/**
1880 * xmlFAEliminateEpsilonTransitions:
1881 * @ctxt: a regexp parser context
1882 *
1883 */
1884static void
1885xmlFAEliminateEpsilonTransitions(xmlRegParserCtxtPtr ctxt) {
1886 int statenr, transnr;
1887 xmlRegStatePtr state;
1888 int has_epsilon;
1889
1890 if (ctxt->states == NULL) return;
1891
1892 /*
1893 * Eliminate simple epsilon transition and the associated unreachable
1894 * states.
1895 */
1896 xmlFAEliminateSimpleEpsilonTransitions(ctxt);
1897 for (statenr = 0;statenr < ctxt->nbStates;statenr++) {
1898 state = ctxt->states[statenr];
1899 if ((state != NULL) && (state->type == XML_REGEXP_UNREACH_STATE)) {
1900#ifdef DEBUG_REGEXP_GRAPH
1901 printf("Removed unreachable state %d\n", statenr);
1902#endif
1903 xmlRegFreeState(state);
1904 ctxt->states[statenr] = NULL;
1905 }
1906 }
1907
1908 has_epsilon = 0;
1909
1910 /*
1911 * Build the completed transitions bypassing the epsilons
1912 * Use a marking algorithm to avoid loops
1913 * Mark sink states too.
1914 * Process from the latests states backward to the start when
1915 * there is long cascading epsilon chains this minimize the
1916 * recursions and transition compares when adding the new ones
1917 */
1918 for (statenr = ctxt->nbStates - 1;statenr >= 0;statenr--) {
1919 state = ctxt->states[statenr];
1920 if (state == NULL)
1921 continue;
1922 if ((state->nbTrans == 0) &&
1923 (state->type != XML_REGEXP_FINAL_STATE)) {
1924 state->type = XML_REGEXP_SINK_STATE;
1925 }
1926 for (transnr = 0;transnr < state->nbTrans;transnr++) {
1927 if ((state->trans[transnr].atom == NULL) &&
1928 (state->trans[transnr].to >= 0)) {
1929 if (state->trans[transnr].to == statenr) {
1930 state->trans[transnr].to = -1;
1931#ifdef DEBUG_REGEXP_GRAPH
1932 printf("Removed loopback epsilon trans %d on %d\n",
1933 transnr, statenr);
1934#endif
1935 } else if (state->trans[transnr].count < 0) {
1936 int newto = state->trans[transnr].to;
1937
1938#ifdef DEBUG_REGEXP_GRAPH
1939 printf("Found epsilon trans %d from %d to %d\n",
1940 transnr, statenr, newto);
1941#endif
1942 has_epsilon = 1;
1943 state->trans[transnr].to = -2;
1944 state->mark = XML_REGEXP_MARK_START;
1945 xmlFAReduceEpsilonTransitions(ctxt, statenr,
1946 newto, state->trans[transnr].counter);
1947 state->mark = XML_REGEXP_MARK_NORMAL;
1948#ifdef DEBUG_REGEXP_GRAPH
1949 } else {
1950 printf("Found counted transition %d on %d\n",
1951 transnr, statenr);
1952#endif
1953 }
1954 }
1955 }
1956 }
1957 /*
1958 * Eliminate the epsilon transitions
1959 */
1960 if (has_epsilon) {
1961 for (statenr = 0;statenr < ctxt->nbStates;statenr++) {
1962 state = ctxt->states[statenr];
1963 if (state == NULL)
1964 continue;
1965 for (transnr = 0;transnr < state->nbTrans;transnr++) {
1966 xmlRegTransPtr trans = &(state->trans[transnr]);
1967 if ((trans->atom == NULL) &&
1968 (trans->count < 0) &&
1969 (trans->to >= 0)) {
1970 trans->to = -1;
1971 }
1972 }
1973 }
1974 }
1975
1976 /*
1977 * Use this pass to detect unreachable states too
1978 */
1979 for (statenr = 0;statenr < ctxt->nbStates;statenr++) {
1980 state = ctxt->states[statenr];
1981 if (state != NULL)
1982 state->reached = XML_REGEXP_MARK_NORMAL;
1983 }
1984 state = ctxt->states[0];
1985 if (state != NULL)
1986 state->reached = XML_REGEXP_MARK_START;
1987 while (state != NULL) {
1988 xmlRegStatePtr target = NULL;
1989 state->reached = XML_REGEXP_MARK_VISITED;
1990 /*
1991 * Mark all states reachable from the current reachable state
1992 */
1993 for (transnr = 0;transnr < state->nbTrans;transnr++) {
1994 if ((state->trans[transnr].to >= 0) &&
1995 ((state->trans[transnr].atom != NULL) ||
1996 (state->trans[transnr].count >= 0))) {
1997 int newto = state->trans[transnr].to;
1998
1999 if (ctxt->states[newto] == NULL)
2000 continue;
2001 if (ctxt->states[newto]->reached == XML_REGEXP_MARK_NORMAL) {
2002 ctxt->states[newto]->reached = XML_REGEXP_MARK_START;
2003 target = ctxt->states[newto];
2004 }
2005 }
2006 }
2007
2008 /*
2009 * find the next accessible state not explored
2010 */
2011 if (target == NULL) {
2012 for (statenr = 1;statenr < ctxt->nbStates;statenr++) {
2013 state = ctxt->states[statenr];
2014 if ((state != NULL) && (state->reached ==
2015 XML_REGEXP_MARK_START)) {
2016 target = state;
2017 break;
2018 }
2019 }
2020 }
2021 state = target;
2022 }
2023 for (statenr = 0;statenr < ctxt->nbStates;statenr++) {
2024 state = ctxt->states[statenr];
2025 if ((state != NULL) && (state->reached == XML_REGEXP_MARK_NORMAL)) {
2026#ifdef DEBUG_REGEXP_GRAPH
2027 printf("Removed unreachable state %d\n", statenr);
2028#endif
2029 xmlRegFreeState(state);
2030 ctxt->states[statenr] = NULL;
2031 }
2032 }
2033
2034}
2035
2036static int
2037xmlFACompareRanges(xmlRegRangePtr range1, xmlRegRangePtr range2) {
2038 int ret = 0;
2039
2040 if ((range1->type == XML_REGEXP_RANGES) ||
2041 (range2->type == XML_REGEXP_RANGES) ||
2042 (range2->type == XML_REGEXP_SUBREG) ||
2043 (range1->type == XML_REGEXP_SUBREG) ||
2044 (range1->type == XML_REGEXP_STRING) ||
2045 (range2->type == XML_REGEXP_STRING))
2046 return(-1);
2047
2048 /* put them in order */
2049 if (range1->type > range2->type) {
2050 xmlRegRangePtr tmp;
2051
2052 tmp = range1;
2053 range1 = range2;
2054 range2 = tmp;
2055 }
2056 if ((range1->type == XML_REGEXP_ANYCHAR) ||
2057 (range2->type == XML_REGEXP_ANYCHAR)) {
2058 ret = 1;
2059 } else if ((range1->type == XML_REGEXP_EPSILON) ||
2060 (range2->type == XML_REGEXP_EPSILON)) {
2061 return(0);
2062 } else if (range1->type == range2->type) {
2063 if ((range1->type != XML_REGEXP_CHARVAL) ||
2064 (range1->end < range2->start) ||
2065 (range2->end < range1->start))
2066 ret = 1;
2067 else
2068 ret = 0;
2069 } else if (range1->type == XML_REGEXP_CHARVAL) {
2070 int codepoint;
2071 int neg = 0;
2072
2073 /*
2074 * just check all codepoints in the range for acceptance,
2075 * this is usually way cheaper since done only once at
2076 * compilation than testing over and over at runtime or
2077 * pushing too many states when evaluating.
2078 */
2079 if (((range1->neg == 0) && (range2->neg != 0)) ||
2080 ((range1->neg != 0) && (range2->neg == 0)))
2081 neg = 1;
2082
2083 for (codepoint = range1->start;codepoint <= range1->end ;codepoint++) {
2084 ret = xmlRegCheckCharacterRange(range2->type, codepoint,
2085 0, range2->start, range2->end,
2086 range2->blockName);
2087 if (ret < 0)
2088 return(-1);
2089 if (((neg == 1) && (ret == 0)) ||
2090 ((neg == 0) && (ret == 1)))
2091 return(1);
2092 }
2093 return(0);
2094 } else if ((range1->type == XML_REGEXP_BLOCK_NAME) ||
2095 (range2->type == XML_REGEXP_BLOCK_NAME)) {
2096 if (range1->type == range2->type) {
2097 ret = xmlStrEqual(range1->blockName, range2->blockName);
2098 } else {
2099 /*
2100 * comparing a block range with anything else is way
2101 * too costly, and maintining the table is like too much
2102 * memory too, so let's force the automata to save state
2103 * here.
2104 */
2105 return(1);
2106 }
2107 } else if ((range1->type < XML_REGEXP_LETTER) ||
2108 (range2->type < XML_REGEXP_LETTER)) {
2109 if ((range1->type == XML_REGEXP_ANYSPACE) &&
2110 (range2->type == XML_REGEXP_NOTSPACE))
2111 ret = 0;
2112 else if ((range1->type == XML_REGEXP_INITNAME) &&
2113 (range2->type == XML_REGEXP_NOTINITNAME))
2114 ret = 0;
2115 else if ((range1->type == XML_REGEXP_NAMECHAR) &&
2116 (range2->type == XML_REGEXP_NOTNAMECHAR))
2117 ret = 0;
2118 else if ((range1->type == XML_REGEXP_DECIMAL) &&
2119 (range2->type == XML_REGEXP_NOTDECIMAL))
2120 ret = 0;
2121 else if ((range1->type == XML_REGEXP_REALCHAR) &&
2122 (range2->type == XML_REGEXP_NOTREALCHAR))
2123 ret = 0;
2124 else {
2125 /* same thing to limit complexity */
2126 return(1);
2127 }
2128 } else {
2129 ret = 0;
2130 /* range1->type < range2->type here */
2131 switch (range1->type) {
2132 case XML_REGEXP_LETTER:
2133 /* all disjoint except in the subgroups */
2134 if ((range2->type == XML_REGEXP_LETTER_UPPERCASE) ||
2135 (range2->type == XML_REGEXP_LETTER_LOWERCASE) ||
2136 (range2->type == XML_REGEXP_LETTER_TITLECASE) ||
2137 (range2->type == XML_REGEXP_LETTER_MODIFIER) ||
2138 (range2->type == XML_REGEXP_LETTER_OTHERS))
2139 ret = 1;
2140 break;
2141 case XML_REGEXP_MARK:
2142 if ((range2->type == XML_REGEXP_MARK_NONSPACING) ||
2143 (range2->type == XML_REGEXP_MARK_SPACECOMBINING) ||
2144 (range2->type == XML_REGEXP_MARK_ENCLOSING))
2145 ret = 1;
2146 break;
2147 case XML_REGEXP_NUMBER:
2148 if ((range2->type == XML_REGEXP_NUMBER_DECIMAL) ||
2149 (range2->type == XML_REGEXP_NUMBER_LETTER) ||
2150 (range2->type == XML_REGEXP_NUMBER_OTHERS))
2151 ret = 1;
2152 break;
2153 case XML_REGEXP_PUNCT:
2154 if ((range2->type == XML_REGEXP_PUNCT_CONNECTOR) ||
2155 (range2->type == XML_REGEXP_PUNCT_DASH) ||
2156 (range2->type == XML_REGEXP_PUNCT_OPEN) ||
2157 (range2->type == XML_REGEXP_PUNCT_CLOSE) ||
2158 (range2->type == XML_REGEXP_PUNCT_INITQUOTE) ||
2159 (range2->type == XML_REGEXP_PUNCT_FINQUOTE) ||
2160 (range2->type == XML_REGEXP_PUNCT_OTHERS))
2161 ret = 1;
2162 break;
2163 case XML_REGEXP_SEPAR:
2164 if ((range2->type == XML_REGEXP_SEPAR_SPACE) ||
2165 (range2->type == XML_REGEXP_SEPAR_LINE) ||
2166 (range2->type == XML_REGEXP_SEPAR_PARA))
2167 ret = 1;
2168 break;
2169 case XML_REGEXP_SYMBOL:
2170 if ((range2->type == XML_REGEXP_SYMBOL_MATH) ||
2171 (range2->type == XML_REGEXP_SYMBOL_CURRENCY) ||
2172 (range2->type == XML_REGEXP_SYMBOL_MODIFIER) ||
2173 (range2->type == XML_REGEXP_SYMBOL_OTHERS))
2174 ret = 1;
2175 break;
2176 case XML_REGEXP_OTHER:
2177 if ((range2->type == XML_REGEXP_OTHER_CONTROL) ||
2178 (range2->type == XML_REGEXP_OTHER_FORMAT) ||
2179 (range2->type == XML_REGEXP_OTHER_PRIVATE))
2180 ret = 1;
2181 break;
2182 default:
2183 if ((range2->type >= XML_REGEXP_LETTER) &&
2184 (range2->type < XML_REGEXP_BLOCK_NAME))
2185 ret = 0;
2186 else {
2187 /* safety net ! */
2188 return(1);
2189 }
2190 }
2191 }
2192 if (((range1->neg == 0) && (range2->neg != 0)) ||
2193 ((range1->neg != 0) && (range2->neg == 0)))
2194 ret = !ret;
2195 return(1);
2196}
2197
2198/**
2199 * xmlFACompareAtomTypes:
2200 * @type1: an atom type
2201 * @type2: an atom type
2202 *
2203 * Compares two atoms type to check whether they intersect in some ways,
2204 * this is used by xmlFACompareAtoms only
2205 *
2206 * Returns 1 if they may intersect and 0 otherwise
2207 */
2208static int
2209xmlFACompareAtomTypes(xmlRegAtomType type1, xmlRegAtomType type2) {
2210 if ((type1 == XML_REGEXP_EPSILON) ||
2211 (type1 == XML_REGEXP_CHARVAL) ||
2212 (type1 == XML_REGEXP_RANGES) ||
2213 (type1 == XML_REGEXP_SUBREG) ||
2214 (type1 == XML_REGEXP_STRING) ||
2215 (type1 == XML_REGEXP_ANYCHAR))
2216 return(1);
2217 if ((type2 == XML_REGEXP_EPSILON) ||
2218 (type2 == XML_REGEXP_CHARVAL) ||
2219 (type2 == XML_REGEXP_RANGES) ||
2220 (type2 == XML_REGEXP_SUBREG) ||
2221 (type2 == XML_REGEXP_STRING) ||
2222 (type2 == XML_REGEXP_ANYCHAR))
2223 return(1);
2224
2225 if (type1 == type2) return(1);
2226
2227 /* simplify subsequent compares by making sure type1 < type2 */
2228 if (type1 > type2) {
2229 xmlRegAtomType tmp = type1;
2230 type1 = type2;
2231 type2 = tmp;
2232 }
2233 switch (type1) {
2234 case XML_REGEXP_ANYSPACE: /* \s */
2235 /* can't be a letter, number, mark, pontuation, symbol */
2236 if ((type2 == XML_REGEXP_NOTSPACE) ||
2237 ((type2 >= XML_REGEXP_LETTER) &&
2238 (type2 <= XML_REGEXP_LETTER_OTHERS)) ||
2239 ((type2 >= XML_REGEXP_NUMBER) &&
2240 (type2 <= XML_REGEXP_NUMBER_OTHERS)) ||
2241 ((type2 >= XML_REGEXP_MARK) &&
2242 (type2 <= XML_REGEXP_MARK_ENCLOSING)) ||
2243 ((type2 >= XML_REGEXP_PUNCT) &&
2244 (type2 <= XML_REGEXP_PUNCT_OTHERS)) ||
2245 ((type2 >= XML_REGEXP_SYMBOL) &&
2246 (type2 <= XML_REGEXP_SYMBOL_OTHERS))
2247 ) return(0);
2248 break;
2249 case XML_REGEXP_NOTSPACE: /* \S */
2250 break;
2251 case XML_REGEXP_INITNAME: /* \l */
2252 /* can't be a number, mark, separator, pontuation, symbol or other */
2253 if ((type2 == XML_REGEXP_NOTINITNAME) ||
2254 ((type2 >= XML_REGEXP_NUMBER) &&
2255 (type2 <= XML_REGEXP_NUMBER_OTHERS)) ||
2256 ((type2 >= XML_REGEXP_MARK) &&
2257 (type2 <= XML_REGEXP_MARK_ENCLOSING)) ||
2258 ((type2 >= XML_REGEXP_SEPAR) &&
2259 (type2 <= XML_REGEXP_SEPAR_PARA)) ||
2260 ((type2 >= XML_REGEXP_PUNCT) &&
2261 (type2 <= XML_REGEXP_PUNCT_OTHERS)) ||
2262 ((type2 >= XML_REGEXP_SYMBOL) &&
2263 (type2 <= XML_REGEXP_SYMBOL_OTHERS)) ||
2264 ((type2 >= XML_REGEXP_OTHER) &&
2265 (type2 <= XML_REGEXP_OTHER_NA))
2266 ) return(0);
2267 break;
2268 case XML_REGEXP_NOTINITNAME: /* \L */
2269 break;
2270 case XML_REGEXP_NAMECHAR: /* \c */
2271 /* can't be a mark, separator, pontuation, symbol or other */
2272 if ((type2 == XML_REGEXP_NOTNAMECHAR) ||
2273 ((type2 >= XML_REGEXP_MARK) &&
2274 (type2 <= XML_REGEXP_MARK_ENCLOSING)) ||
2275 ((type2 >= XML_REGEXP_PUNCT) &&
2276 (type2 <= XML_REGEXP_PUNCT_OTHERS)) ||
2277 ((type2 >= XML_REGEXP_SEPAR) &&
2278 (type2 <= XML_REGEXP_SEPAR_PARA)) ||
2279 ((type2 >= XML_REGEXP_SYMBOL) &&
2280 (type2 <= XML_REGEXP_SYMBOL_OTHERS)) ||
2281 ((type2 >= XML_REGEXP_OTHER) &&
2282 (type2 <= XML_REGEXP_OTHER_NA))
2283 ) return(0);
2284 break;
2285 case XML_REGEXP_NOTNAMECHAR: /* \C */
2286 break;
2287 case XML_REGEXP_DECIMAL: /* \d */
2288 /* can't be a letter, mark, separator, pontuation, symbol or other */
2289 if ((type2 == XML_REGEXP_NOTDECIMAL) ||
2290 (type2 == XML_REGEXP_REALCHAR) ||
2291 ((type2 >= XML_REGEXP_LETTER) &&
2292 (type2 <= XML_REGEXP_LETTER_OTHERS)) ||
2293 ((type2 >= XML_REGEXP_MARK) &&
2294 (type2 <= XML_REGEXP_MARK_ENCLOSING)) ||
2295 ((type2 >= XML_REGEXP_PUNCT) &&
2296 (type2 <= XML_REGEXP_PUNCT_OTHERS)) ||
2297 ((type2 >= XML_REGEXP_SEPAR) &&
2298 (type2 <= XML_REGEXP_SEPAR_PARA)) ||
2299 ((type2 >= XML_REGEXP_SYMBOL) &&
2300 (type2 <= XML_REGEXP_SYMBOL_OTHERS)) ||
2301 ((type2 >= XML_REGEXP_OTHER) &&
2302 (type2 <= XML_REGEXP_OTHER_NA))
2303 )return(0);
2304 break;
2305 case XML_REGEXP_NOTDECIMAL: /* \D */
2306 break;
2307 case XML_REGEXP_REALCHAR: /* \w */
2308 /* can't be a mark, separator, pontuation, symbol or other */
2309 if ((type2 == XML_REGEXP_NOTDECIMAL) ||
2310 ((type2 >= XML_REGEXP_MARK) &&
2311 (type2 <= XML_REGEXP_MARK_ENCLOSING)) ||
2312 ((type2 >= XML_REGEXP_PUNCT) &&
2313 (type2 <= XML_REGEXP_PUNCT_OTHERS)) ||
2314 ((type2 >= XML_REGEXP_SEPAR) &&
2315 (type2 <= XML_REGEXP_SEPAR_PARA)) ||
2316 ((type2 >= XML_REGEXP_SYMBOL) &&
2317 (type2 <= XML_REGEXP_SYMBOL_OTHERS)) ||
2318 ((type2 >= XML_REGEXP_OTHER) &&
2319 (type2 <= XML_REGEXP_OTHER_NA))
2320 )return(0);
2321 break;
2322 case XML_REGEXP_NOTREALCHAR: /* \W */
2323 break;
2324 /*
2325 * at that point we know both type 1 and type2 are from
2326 * character categories are ordered and are different,
2327 * it becomes simple because this is a partition
2328 */
2329 case XML_REGEXP_LETTER:
2330 if (type2 <= XML_REGEXP_LETTER_OTHERS)
2331 return(1);
2332 return(0);
2333 case XML_REGEXP_LETTER_UPPERCASE:
2334 case XML_REGEXP_LETTER_LOWERCASE:
2335 case XML_REGEXP_LETTER_TITLECASE:
2336 case XML_REGEXP_LETTER_MODIFIER:
2337 case XML_REGEXP_LETTER_OTHERS:
2338 return(0);
2339 case XML_REGEXP_MARK:
2340 if (type2 <= XML_REGEXP_MARK_ENCLOSING)
2341 return(1);
2342 return(0);
2343 case XML_REGEXP_MARK_NONSPACING:
2344 case XML_REGEXP_MARK_SPACECOMBINING:
2345 case XML_REGEXP_MARK_ENCLOSING:
2346 return(0);
2347 case XML_REGEXP_NUMBER:
2348 if (type2 <= XML_REGEXP_NUMBER_OTHERS)
2349 return(1);
2350 return(0);
2351 case XML_REGEXP_NUMBER_DECIMAL:
2352 case XML_REGEXP_NUMBER_LETTER:
2353 case XML_REGEXP_NUMBER_OTHERS:
2354 return(0);
2355 case XML_REGEXP_PUNCT:
2356 if (type2 <= XML_REGEXP_PUNCT_OTHERS)
2357 return(1);
2358 return(0);
2359 case XML_REGEXP_PUNCT_CONNECTOR:
2360 case XML_REGEXP_PUNCT_DASH:
2361 case XML_REGEXP_PUNCT_OPEN:
2362 case XML_REGEXP_PUNCT_CLOSE:
2363 case XML_REGEXP_PUNCT_INITQUOTE:
2364 case XML_REGEXP_PUNCT_FINQUOTE:
2365 case XML_REGEXP_PUNCT_OTHERS:
2366 return(0);
2367 case XML_REGEXP_SEPAR:
2368 if (type2 <= XML_REGEXP_SEPAR_PARA)
2369 return(1);
2370 return(0);
2371 case XML_REGEXP_SEPAR_SPACE:
2372 case XML_REGEXP_SEPAR_LINE:
2373 case XML_REGEXP_SEPAR_PARA:
2374 return(0);
2375 case XML_REGEXP_SYMBOL:
2376 if (type2 <= XML_REGEXP_SYMBOL_OTHERS)
2377 return(1);
2378 return(0);
2379 case XML_REGEXP_SYMBOL_MATH:
2380 case XML_REGEXP_SYMBOL_CURRENCY:
2381 case XML_REGEXP_SYMBOL_MODIFIER:
2382 case XML_REGEXP_SYMBOL_OTHERS:
2383 return(0);
2384 case XML_REGEXP_OTHER:
2385 if (type2 <= XML_REGEXP_OTHER_NA)
2386 return(1);
2387 return(0);
2388 case XML_REGEXP_OTHER_CONTROL:
2389 case XML_REGEXP_OTHER_FORMAT:
2390 case XML_REGEXP_OTHER_PRIVATE:
2391 case XML_REGEXP_OTHER_NA:
2392 return(0);
2393 default:
2394 break;
2395 }
2396 return(1);
2397}
2398
2399/**
2400 * xmlFAEqualAtoms:
2401 * @atom1: an atom
2402 * @atom2: an atom
2403 *
2404 * Compares two atoms to check whether they are the same exactly
2405 * this is used to remove equivalent transitions
2406 *
2407 * Returns 1 if same and 0 otherwise
2408 */
2409static int
2410xmlFAEqualAtoms(xmlRegAtomPtr atom1, xmlRegAtomPtr atom2) {
2411 int ret = 0;
2412
2413 if (atom1 == atom2)
2414 return(1);
2415 if ((atom1 == NULL) || (atom2 == NULL))
2416 return(0);
2417
2418 if (atom1->type != atom2->type)
2419 return(0);
2420 switch (atom1->type) {
2421 case XML_REGEXP_EPSILON:
2422 ret = 0;
2423 break;
2424 case XML_REGEXP_STRING:
2425 ret = xmlStrEqual((xmlChar *)atom1->valuep,
2426 (xmlChar *)atom2->valuep);
2427 break;
2428 case XML_REGEXP_CHARVAL:
2429 ret = (atom1->codepoint == atom2->codepoint);
2430 break;
2431 case XML_REGEXP_RANGES:
2432 /* too hard to do in the general case */
2433 ret = 0;
2434 default:
2435 break;
2436 }
2437 return(ret);
2438}
2439
2440/**
2441 * xmlFACompareAtoms:
2442 * @atom1: an atom
2443 * @atom2: an atom
2444 *
2445 * Compares two atoms to check whether they intersect in some ways,
2446 * this is used by xmlFAComputesDeterminism and xmlFARecurseDeterminism only
2447 *
2448 * Returns 1 if yes and 0 otherwise
2449 */
2450static int
2451xmlFACompareAtoms(xmlRegAtomPtr atom1, xmlRegAtomPtr atom2) {
2452 int ret = 1;
2453
2454 if (atom1 == atom2)
2455 return(1);
2456 if ((atom1 == NULL) || (atom2 == NULL))
2457 return(0);
2458
2459 if ((atom1->type == XML_REGEXP_ANYCHAR) ||
2460 (atom2->type == XML_REGEXP_ANYCHAR))
2461 return(1);
2462
2463 if (atom1->type > atom2->type) {
2464 xmlRegAtomPtr tmp;
2465 tmp = atom1;
2466 atom1 = atom2;
2467 atom2 = tmp;
2468 }
2469 if (atom1->type != atom2->type) {
2470 ret = xmlFACompareAtomTypes(atom1->type, atom2->type);
2471 /* if they can't intersect at the type level break now */
2472 if (ret == 0)
2473 return(0);
2474 }
2475 switch (atom1->type) {
2476 case XML_REGEXP_STRING:
2477 ret = xmlRegStrEqualWildcard((xmlChar *)atom1->valuep,
2478 (xmlChar *)atom2->valuep);
2479 break;
2480 case XML_REGEXP_EPSILON:
2481 goto not_determinist;
2482 case XML_REGEXP_CHARVAL:
2483 if (atom2->type == XML_REGEXP_CHARVAL) {
2484 ret = (atom1->codepoint == atom2->codepoint);
2485 } else {
2486 ret = xmlRegCheckCharacter(atom2, atom1->codepoint);
2487 if (ret < 0)
2488 ret = 1;
2489 }
2490 break;
2491 case XML_REGEXP_RANGES:
2492 if (atom2->type == XML_REGEXP_RANGES) {
2493 int i, j, res;
2494 xmlRegRangePtr r1, r2;
2495
2496 /*
2497 * need to check that none of the ranges eventually matches
2498 */
2499 for (i = 0;i < atom1->nbRanges;i++) {
2500 for (j = 0;j < atom2->nbRanges;j++) {
2501 r1 = atom1->ranges[i];
2502 r2 = atom2->ranges[j];
2503 res = xmlFACompareRanges(r1, r2);
2504 if (res == 1) {
2505 ret = 1;
2506 goto done;
2507 }
2508 }
2509 }
2510 ret = 0;
2511 }
2512 break;
2513 default:
2514 goto not_determinist;
2515 }
2516done:
2517 if (atom1->neg != atom2->neg) {
2518 ret = !ret;
2519 }
2520 if (ret == 0)
2521 return(0);
2522not_determinist:
2523 return(1);
2524}
2525
2526/**
2527 * xmlFARecurseDeterminism:
2528 * @ctxt: a regexp parser context
2529 *
2530 * Check whether the associated regexp is determinist,
2531 * should be called after xmlFAEliminateEpsilonTransitions()
2532 *
2533 */
2534static int
2535xmlFARecurseDeterminism(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr state,
2536 int to, xmlRegAtomPtr atom) {
2537 int ret = 1;
2538 int res;
2539 int transnr, nbTrans;
2540 xmlRegTransPtr t1;
2541
2542 if (state == NULL)
2543 return(ret);
2544 /*
2545 * don't recurse on transitions potentially added in the course of
2546 * the elimination.
2547 */
2548 nbTrans = state->nbTrans;
2549 for (transnr = 0;transnr < nbTrans;transnr++) {
2550 t1 = &(state->trans[transnr]);
2551 /*
2552 * check transitions conflicting with the one looked at
2553 */
2554 if (t1->atom == NULL) {
2555 if (t1->to < 0)
2556 continue;
2557 res = xmlFARecurseDeterminism(ctxt, ctxt->states[t1->to],
2558 to, atom);
2559 if (res == 0) {
2560 ret = 0;
2561 /* t1->nd = 1; */
2562 }
2563 continue;
2564 }
2565 if (t1->to != to)
2566 continue;
2567 if (xmlFACompareAtoms(t1->atom, atom)) {
2568 ret = 0;
2569 /* mark the transition as non-deterministic */
2570 t1->nd = 1;
2571 }
2572 }
2573 return(ret);
2574}
2575
2576/**
2577 * xmlFAComputesDeterminism:
2578 * @ctxt: a regexp parser context
2579 *
2580 * Check whether the associated regexp is determinist,
2581 * should be called after xmlFAEliminateEpsilonTransitions()
2582 *
2583 */
2584static int
2585xmlFAComputesDeterminism(xmlRegParserCtxtPtr ctxt) {
2586 int statenr, transnr;
2587 xmlRegStatePtr state;
2588 xmlRegTransPtr t1, t2, last;
2589 int i;
2590 int ret = 1;
2591
2592#ifdef DEBUG_REGEXP_GRAPH
2593 printf("xmlFAComputesDeterminism\n");
2594 xmlRegPrintCtxt(stdout, ctxt);
2595#endif
2596 if (ctxt->determinist != -1)
2597 return(ctxt->determinist);
2598
2599 /*
2600 * First cleanup the automata removing cancelled transitions
2601 */
2602 for (statenr = 0;statenr < ctxt->nbStates;statenr++) {
2603 state = ctxt->states[statenr];
2604 if (state == NULL)
2605 continue;
2606 if (state->nbTrans < 2)
2607 continue;
2608 for (transnr = 0;transnr < state->nbTrans;transnr++) {
2609 t1 = &(state->trans[transnr]);
2610 /*
2611 * Determinism checks in case of counted or all transitions
2612 * will have to be handled separately
2613 */
2614 if (t1->atom == NULL) {
2615 /* t1->nd = 1; */
2616 continue;
2617 }
2618 if (t1->to == -1) /* eliminated */
2619 continue;
2620 for (i = 0;i < transnr;i++) {
2621 t2 = &(state->trans[i]);
2622 if (t2->to == -1) /* eliminated */
2623 continue;
2624 if (t2->atom != NULL) {
2625 if (t1->to == t2->to) {
2626 if (xmlFAEqualAtoms(t1->atom, t2->atom))
2627 t2->to = -1; /* eliminated */
2628 }
2629 }
2630 }
2631 }
2632 }
2633
2634 /*
2635 * Check for all states that there aren't 2 transitions
2636 * with the same atom and a different target.
2637 */
2638 for (statenr = 0;statenr < ctxt->nbStates;statenr++) {
2639 state = ctxt->states[statenr];
2640 if (state == NULL)
2641 continue;
2642 if (state->nbTrans < 2)
2643 continue;
2644 last = NULL;
2645 for (transnr = 0;transnr < state->nbTrans;transnr++) {
2646 t1 = &(state->trans[transnr]);
2647 /*
2648 * Determinism checks in case of counted or all transitions
2649 * will have to be handled separately
2650 */
2651 if (t1->atom == NULL) {
2652 continue;
2653 }
2654 if (t1->to == -1) /* eliminated */
2655 continue;
2656 for (i = 0;i < transnr;i++) {
2657 t2 = &(state->trans[i]);
2658 if (t2->to == -1) /* eliminated */
2659 continue;
2660 if (t2->atom != NULL) {
2661 /* not determinist ! */
2662 if (xmlFACompareAtoms(t1->atom, t2->atom)) {
2663 ret = 0;
2664 /* mark the transitions as non-deterministic ones */
2665 t1->nd = 1;
2666 t2->nd = 1;
2667 last = t1;
2668 }
2669 } else if (t1->to != -1) {
2670 /*
2671 * do the closure in case of remaining specific
2672 * epsilon transitions like choices or all
2673 */
2674 ret = xmlFARecurseDeterminism(ctxt, ctxt->states[t1->to],
2675 t2->to, t2->atom);
2676 /* don't shortcut the computation so all non deterministic
2677 transition get marked down
2678 if (ret == 0)
2679 return(0);
2680 */
2681 if (ret == 0) {
2682 t1->nd = 1;
2683 /* t2->nd = 1; */
2684 last = t1;
2685 }
2686 }
2687 }
2688 /* don't shortcut the computation so all non deterministic
2689 transition get marked down
2690 if (ret == 0)
2691 break; */
2692 }
2693
2694 /*
2695 * mark specifically the last non-deterministic transition
2696 * from a state since there is no need to set-up rollback
2697 * from it
2698 */
2699 if (last != NULL) {
2700 last->nd = 2;
2701 }
2702
2703 /* don't shortcut the computation so all non deterministic
2704 transition get marked down
2705 if (ret == 0)
2706 break; */
2707 }
2708
2709 ctxt->determinist = ret;
2710 return(ret);
2711}
2712
2713/************************************************************************
2714 * *
2715 * Routines to check input against transition atoms *
2716 * *
2717 ************************************************************************/
2718
2719static int
2720xmlRegCheckCharacterRange(xmlRegAtomType type, int codepoint, int neg,
2721 int start, int end, const xmlChar *blockName) {
2722 int ret = 0;
2723
2724 switch (type) {
2725 case XML_REGEXP_STRING:
2726 case XML_REGEXP_SUBREG:
2727 case XML_REGEXP_RANGES:
2728 case XML_REGEXP_EPSILON:
2729 return(-1);
2730 case XML_REGEXP_ANYCHAR:
2731 ret = ((codepoint != '\n') && (codepoint != '\r'));
2732 break;
2733 case XML_REGEXP_CHARVAL:
2734 ret = ((codepoint >= start) && (codepoint <= end));
2735 break;
2736 case XML_REGEXP_NOTSPACE:
2737 neg = !neg;
2738 case XML_REGEXP_ANYSPACE:
2739 ret = ((codepoint == '\n') || (codepoint == '\r') ||
2740 (codepoint == '\t') || (codepoint == ' '));
2741 break;
2742 case XML_REGEXP_NOTINITNAME:
2743 neg = !neg;
2744 case XML_REGEXP_INITNAME:
2745 ret = (IS_LETTER(codepoint) ||
2746 (codepoint == '_') || (codepoint == ':'));
2747 break;
2748 case XML_REGEXP_NOTNAMECHAR:
2749 neg = !neg;
2750 case XML_REGEXP_NAMECHAR:
2751 ret = (IS_LETTER(codepoint) || IS_DIGIT(codepoint) ||
2752 (codepoint == '.') || (codepoint == '-') ||
2753 (codepoint == '_') || (codepoint == ':') ||
2754 IS_COMBINING(codepoint) || IS_EXTENDER(codepoint));
2755 break;
2756 case XML_REGEXP_NOTDECIMAL:
2757 neg = !neg;
2758 case XML_REGEXP_DECIMAL:
2759 ret = xmlUCSIsCatNd(codepoint);
2760 break;
2761 case XML_REGEXP_REALCHAR:
2762 neg = !neg;
2763 case XML_REGEXP_NOTREALCHAR:
2764 ret = xmlUCSIsCatP(codepoint);
2765 if (ret == 0)
2766 ret = xmlUCSIsCatZ(codepoint);
2767 if (ret == 0)
2768 ret = xmlUCSIsCatC(codepoint);
2769 break;
2770 case XML_REGEXP_LETTER:
2771 ret = xmlUCSIsCatL(codepoint);
2772 break;
2773 case XML_REGEXP_LETTER_UPPERCASE:
2774 ret = xmlUCSIsCatLu(codepoint);
2775 break;
2776 case XML_REGEXP_LETTER_LOWERCASE:
2777 ret = xmlUCSIsCatLl(codepoint);
2778 break;
2779 case XML_REGEXP_LETTER_TITLECASE:
2780 ret = xmlUCSIsCatLt(codepoint);
2781 break;
2782 case XML_REGEXP_LETTER_MODIFIER:
2783 ret = xmlUCSIsCatLm(codepoint);
2784 break;
2785 case XML_REGEXP_LETTER_OTHERS:
2786 ret = xmlUCSIsCatLo(codepoint);
2787 break;
2788 case XML_REGEXP_MARK:
2789 ret = xmlUCSIsCatM(codepoint);
2790 break;
2791 case XML_REGEXP_MARK_NONSPACING:
2792 ret = xmlUCSIsCatMn(codepoint);
2793 break;
2794 case XML_REGEXP_MARK_SPACECOMBINING:
2795 ret = xmlUCSIsCatMc(codepoint);
2796 break;
2797 case XML_REGEXP_MARK_ENCLOSING:
2798 ret = xmlUCSIsCatMe(codepoint);
2799 break;
2800 case XML_REGEXP_NUMBER:
2801 ret = xmlUCSIsCatN(codepoint);
2802 break;
2803 case XML_REGEXP_NUMBER_DECIMAL:
2804 ret = xmlUCSIsCatNd(codepoint);
2805 break;
2806 case XML_REGEXP_NUMBER_LETTER:
2807 ret = xmlUCSIsCatNl(codepoint);
2808 break;
2809 case XML_REGEXP_NUMBER_OTHERS:
2810 ret = xmlUCSIsCatNo(codepoint);
2811 break;
2812 case XML_REGEXP_PUNCT:
2813 ret = xmlUCSIsCatP(codepoint);
2814 break;
2815 case XML_REGEXP_PUNCT_CONNECTOR:
2816 ret = xmlUCSIsCatPc(codepoint);
2817 break;
2818 case XML_REGEXP_PUNCT_DASH:
2819 ret = xmlUCSIsCatPd(codepoint);
2820 break;
2821 case XML_REGEXP_PUNCT_OPEN:
2822 ret = xmlUCSIsCatPs(codepoint);
2823 break;
2824 case XML_REGEXP_PUNCT_CLOSE:
2825 ret = xmlUCSIsCatPe(codepoint);
2826 break;
2827 case XML_REGEXP_PUNCT_INITQUOTE:
2828 ret = xmlUCSIsCatPi(codepoint);
2829 break;
2830 case XML_REGEXP_PUNCT_FINQUOTE:
2831 ret = xmlUCSIsCatPf(codepoint);
2832 break;
2833 case XML_REGEXP_PUNCT_OTHERS:
2834 ret = xmlUCSIsCatPo(codepoint);
2835 break;
2836 case XML_REGEXP_SEPAR:
2837 ret = xmlUCSIsCatZ(codepoint);
2838 break;
2839 case XML_REGEXP_SEPAR_SPACE:
2840 ret = xmlUCSIsCatZs(codepoint);
2841 break;
2842 case XML_REGEXP_SEPAR_LINE:
2843 ret = xmlUCSIsCatZl(codepoint);
2844 break;
2845 case XML_REGEXP_SEPAR_PARA:
2846 ret = xmlUCSIsCatZp(codepoint);
2847 break;
2848 case XML_REGEXP_SYMBOL:
2849 ret = xmlUCSIsCatS(codepoint);
2850 break;
2851 case XML_REGEXP_SYMBOL_MATH:
2852 ret = xmlUCSIsCatSm(codepoint);
2853 break;
2854 case XML_REGEXP_SYMBOL_CURRENCY:
2855 ret = xmlUCSIsCatSc(codepoint);
2856 break;
2857 case XML_REGEXP_SYMBOL_MODIFIER:
2858 ret = xmlUCSIsCatSk(codepoint);
2859 break;
2860 case XML_REGEXP_SYMBOL_OTHERS:
2861 ret = xmlUCSIsCatSo(codepoint);
2862 break;
2863 case XML_REGEXP_OTHER:
2864 ret = xmlUCSIsCatC(codepoint);
2865 break;
2866 case XML_REGEXP_OTHER_CONTROL:
2867 ret = xmlUCSIsCatCc(codepoint);
2868 break;
2869 case XML_REGEXP_OTHER_FORMAT:
2870 ret = xmlUCSIsCatCf(codepoint);
2871 break;
2872 case XML_REGEXP_OTHER_PRIVATE:
2873 ret = xmlUCSIsCatCo(codepoint);
2874 break;
2875 case XML_REGEXP_OTHER_NA:
2876 /* ret = xmlUCSIsCatCn(codepoint); */
2877 /* Seems it doesn't exist anymore in recent Unicode releases */
2878 ret = 0;
2879 break;
2880 case XML_REGEXP_BLOCK_NAME:
2881 ret = xmlUCSIsBlock(codepoint, (const char *) blockName);
2882 break;
2883 }
2884 if (neg)
2885 return(!ret);
2886 return(ret);
2887}
2888
2889static int
2890xmlRegCheckCharacter(xmlRegAtomPtr atom, int codepoint) {
2891 int i, ret = 0;
2892 xmlRegRangePtr range;
2893
2894 if ((atom == NULL) || (!IS_CHAR(codepoint)))
2895 return(-1);
2896
2897 switch (atom->type) {
2898 case XML_REGEXP_SUBREG:
2899 case XML_REGEXP_EPSILON:
2900 return(-1);
2901 case XML_REGEXP_CHARVAL:
2902 return(codepoint == atom->codepoint);
2903 case XML_REGEXP_RANGES: {
2904 int accept = 0;
2905
2906 for (i = 0;i < atom->nbRanges;i++) {
2907 range = atom->ranges[i];
2908 if (range->neg == 2) {
2909 ret = xmlRegCheckCharacterRange(range->type, codepoint,
2910 0, range->start, range->end,
2911 range->blockName);
2912 if (ret != 0)
2913 return(0); /* excluded char */
2914 } else if (range->neg) {
2915 ret = xmlRegCheckCharacterRange(range->type, codepoint,
2916 0, range->start, range->end,
2917 range->blockName);
2918 if (ret == 0)
2919 accept = 1;
2920 else
2921 return(0);
2922 } else {
2923 ret = xmlRegCheckCharacterRange(range->type, codepoint,
2924 0, range->start, range->end,
2925 range->blockName);
2926 if (ret != 0)
2927 accept = 1; /* might still be excluded */
2928 }
2929 }
2930 return(accept);
2931 }
2932 case XML_REGEXP_STRING:
2933 printf("TODO: XML_REGEXP_STRING\n");
2934 return(-1);
2935 case XML_REGEXP_ANYCHAR:
2936 case XML_REGEXP_ANYSPACE:
2937 case XML_REGEXP_NOTSPACE:
2938 case XML_REGEXP_INITNAME:
2939 case XML_REGEXP_NOTINITNAME:
2940 case XML_REGEXP_NAMECHAR:
2941 case XML_REGEXP_NOTNAMECHAR:
2942 case XML_REGEXP_DECIMAL:
2943 case XML_REGEXP_NOTDECIMAL:
2944 case XML_REGEXP_REALCHAR:
2945 case XML_REGEXP_NOTREALCHAR:
2946 case XML_REGEXP_LETTER:
2947 case XML_REGEXP_LETTER_UPPERCASE:
2948 case XML_REGEXP_LETTER_LOWERCASE:
2949 case XML_REGEXP_LETTER_TITLECASE:
2950 case XML_REGEXP_LETTER_MODIFIER:
2951 case XML_REGEXP_LETTER_OTHERS:
2952 case XML_REGEXP_MARK:
2953 case XML_REGEXP_MARK_NONSPACING:
2954 case XML_REGEXP_MARK_SPACECOMBINING:
2955 case XML_REGEXP_MARK_ENCLOSING:
2956 case XML_REGEXP_NUMBER:
2957 case XML_REGEXP_NUMBER_DECIMAL:
2958 case XML_REGEXP_NUMBER_LETTER:
2959 case XML_REGEXP_NUMBER_OTHERS:
2960 case XML_REGEXP_PUNCT:
2961 case XML_REGEXP_PUNCT_CONNECTOR:
2962 case XML_REGEXP_PUNCT_DASH:
2963 case XML_REGEXP_PUNCT_OPEN:
2964 case XML_REGEXP_PUNCT_CLOSE:
2965 case XML_REGEXP_PUNCT_INITQUOTE:
2966 case XML_REGEXP_PUNCT_FINQUOTE:
2967 case XML_REGEXP_PUNCT_OTHERS:
2968 case XML_REGEXP_SEPAR:
2969 case XML_REGEXP_SEPAR_SPACE:
2970 case XML_REGEXP_SEPAR_LINE:
2971 case XML_REGEXP_SEPAR_PARA:
2972 case XML_REGEXP_SYMBOL:
2973 case XML_REGEXP_SYMBOL_MATH:
2974 case XML_REGEXP_SYMBOL_CURRENCY:
2975 case XML_REGEXP_SYMBOL_MODIFIER:
2976 case XML_REGEXP_SYMBOL_OTHERS:
2977 case XML_REGEXP_OTHER:
2978 case XML_REGEXP_OTHER_CONTROL:
2979 case XML_REGEXP_OTHER_FORMAT:
2980 case XML_REGEXP_OTHER_PRIVATE:
2981 case XML_REGEXP_OTHER_NA:
2982 case XML_REGEXP_BLOCK_NAME:
2983 ret = xmlRegCheckCharacterRange(atom->type, codepoint, 0, 0, 0,
2984 (const xmlChar *)atom->valuep);
2985 if (atom->neg)
2986 ret = !ret;
2987 break;
2988 }
2989 return(ret);
2990}
2991
2992/************************************************************************
2993 * *
2994 * Saving and restoring state of an execution context *
2995 * *
2996 ************************************************************************/
2997
2998#ifdef DEBUG_REGEXP_EXEC
2999static void
3000xmlFARegDebugExec(xmlRegExecCtxtPtr exec) {
3001 printf("state: %d:%d:idx %d", exec->state->no, exec->transno, exec->index);
3002 if (exec->inputStack != NULL) {
3003 int i;
3004 printf(": ");
3005 for (i = 0;(i < 3) && (i < exec->inputStackNr);i++)
3006 printf("%s ", (const char *)
3007 exec->inputStack[exec->inputStackNr - (i + 1)].value);
3008 } else {
3009 printf(": %s", &(exec->inputString[exec->index]));
3010 }
3011 printf("\n");
3012}
3013#endif
3014
3015static void
3016xmlFARegExecSave(xmlRegExecCtxtPtr exec) {
3017#ifdef DEBUG_REGEXP_EXEC
3018 printf("saving ");
3019 exec->transno++;
3020 xmlFARegDebugExec(exec);
3021 exec->transno--;
3022#endif
3023#ifdef MAX_PUSH
3024 if (exec->nbPush > MAX_PUSH) {
3025 return;
3026 }
3027 exec->nbPush++;
3028#endif
3029
3030 if (exec->maxRollbacks == 0) {
3031 exec->maxRollbacks = 4;
3032 exec->rollbacks = (xmlRegExecRollback *) xmlMalloc(exec->maxRollbacks *
3033 sizeof(xmlRegExecRollback));
3034 if (exec->rollbacks == NULL) {
3035 xmlRegexpErrMemory(NULL, "saving regexp");
3036 exec->maxRollbacks = 0;
3037 return;
3038 }
3039 memset(exec->rollbacks, 0,
3040 exec->maxRollbacks * sizeof(xmlRegExecRollback));
3041 } else if (exec->nbRollbacks >= exec->maxRollbacks) {
3042 xmlRegExecRollback *tmp;
3043 int len = exec->maxRollbacks;
3044
3045 exec->maxRollbacks *= 2;
3046 tmp = (xmlRegExecRollback *) xmlRealloc(exec->rollbacks,
3047 exec->maxRollbacks * sizeof(xmlRegExecRollback));
3048 if (tmp == NULL) {
3049 xmlRegexpErrMemory(NULL, "saving regexp");
3050 exec->maxRollbacks /= 2;
3051 return;
3052 }
3053 exec->rollbacks = tmp;
3054 tmp = &exec->rollbacks[len];
3055 memset(tmp, 0, (exec->maxRollbacks - len) * sizeof(xmlRegExecRollback));
3056 }
3057 exec->rollbacks[exec->nbRollbacks].state = exec->state;
3058 exec->rollbacks[exec->nbRollbacks].index = exec->index;
3059 exec->rollbacks[exec->nbRollbacks].nextbranch = exec->transno + 1;
3060 if (exec->comp->nbCounters > 0) {
3061 if (exec->rollbacks[exec->nbRollbacks].counts == NULL) {
3062 exec->rollbacks[exec->nbRollbacks].counts = (int *)
3063 xmlMalloc(exec->comp->nbCounters * sizeof(int));
3064 if (exec->rollbacks[exec->nbRollbacks].counts == NULL) {
3065 xmlRegexpErrMemory(NULL, "saving regexp");
3066 exec->status = -5;
3067 return;
3068 }
3069 }
3070 memcpy(exec->rollbacks[exec->nbRollbacks].counts, exec->counts,
3071 exec->comp->nbCounters * sizeof(int));
3072 }
3073 exec->nbRollbacks++;
3074}
3075
3076static void
3077xmlFARegExecRollBack(xmlRegExecCtxtPtr exec) {
3078 if (exec->nbRollbacks <= 0) {
3079 exec->status = -1;
3080#ifdef DEBUG_REGEXP_EXEC
3081 printf("rollback failed on empty stack\n");
3082#endif
3083 return;
3084 }
3085 exec->nbRollbacks--;
3086 exec->state = exec->rollbacks[exec->nbRollbacks].state;
3087 exec->index = exec->rollbacks[exec->nbRollbacks].index;
3088 exec->transno = exec->rollbacks[exec->nbRollbacks].nextbranch;
3089 if (exec->comp->nbCounters > 0) {
3090 if (exec->rollbacks[exec->nbRollbacks].counts == NULL) {
3091 fprintf(stderr, "exec save: allocation failed");
3092 exec->status = -6;
3093 return;
3094 }
3095 memcpy(exec->counts, exec->rollbacks[exec->nbRollbacks].counts,
3096 exec->comp->nbCounters * sizeof(int));
3097 }
3098
3099#ifdef DEBUG_REGEXP_EXEC
3100 printf("restored ");
3101 xmlFARegDebugExec(exec);
3102#endif
3103}
3104
3105/************************************************************************
3106 * *
3107 * Verifier, running an input against a compiled regexp *
3108 * *
3109 ************************************************************************/
3110
3111static int
3112xmlFARegExec(xmlRegexpPtr comp, const xmlChar *content) {
3113 xmlRegExecCtxt execval;
3114 xmlRegExecCtxtPtr exec = &execval;
3115 int ret, codepoint = 0, len, deter;
3116
3117 exec->inputString = content;
3118 exec->index = 0;
3119 exec->nbPush = 0;
3120 exec->determinist = 1;
3121 exec->maxRollbacks = 0;
3122 exec->nbRollbacks = 0;
3123 exec->rollbacks = NULL;
3124 exec->status = 0;
3125 exec->comp = comp;
3126 exec->state = comp->states[0];
3127 exec->transno = 0;
3128 exec->transcount = 0;
3129 exec->inputStack = NULL;
3130 exec->inputStackMax = 0;
3131 if (comp->nbCounters > 0) {
3132 exec->counts = (int *) xmlMalloc(comp->nbCounters * sizeof(int));
3133 if (exec->counts == NULL) {
3134 xmlRegexpErrMemory(NULL, "running regexp");
3135 return(-1);
3136 }
3137 memset(exec->counts, 0, comp->nbCounters * sizeof(int));
3138 } else
3139 exec->counts = NULL;
3140 while ((exec->status == 0) &&
3141 ((exec->inputString[exec->index] != 0) ||
3142 (exec->state->type != XML_REGEXP_FINAL_STATE))) {
3143 xmlRegTransPtr trans;
3144 xmlRegAtomPtr atom;
3145
3146 /*
3147 * If end of input on non-terminal state, rollback, however we may
3148 * still have epsilon like transition for counted transitions
3149 * on counters, in that case don't break too early. Additionally,
3150 * if we are working on a range like "AB{0,2}", where B is not present,
3151 * we don't want to break.
3152 */
3153 len = 1;
3154 if ((exec->inputString[exec->index] == 0) && (exec->counts == NULL)) {
3155 /*
3156 * if there is a transition, we must check if
3157 * atom allows minOccurs of 0
3158 */
3159 if (exec->transno < exec->state->nbTrans) {
3160 trans = &exec->state->trans[exec->transno];
3161 if (trans->to >=0) {
3162 atom = trans->atom;
3163 if (!((atom->min == 0) && (atom->max > 0)))
3164 goto rollback;
3165 }
3166 } else
3167 goto rollback;
3168 }
3169
3170 exec->transcount = 0;
3171 for (;exec->transno < exec->state->nbTrans;exec->transno++) {
3172 trans = &exec->state->trans[exec->transno];
3173 if (trans->to < 0)
3174 continue;
3175 atom = trans->atom;
3176 ret = 0;
3177 deter = 1;
3178 if (trans->count >= 0) {
3179 int count;
3180 xmlRegCounterPtr counter;
3181
3182 if (exec->counts == NULL) {
3183 exec->status = -1;
3184 goto error;
3185 }
3186 /*
3187 * A counted transition.
3188 */
3189
3190 count = exec->counts[trans->count];
3191 counter = &exec->comp->counters[trans->count];
3192#ifdef DEBUG_REGEXP_EXEC
3193 printf("testing count %d: val %d, min %d, max %d\n",
3194 trans->count, count, counter->min, counter->max);
3195#endif
3196 ret = ((count >= counter->min) && (count <= counter->max));
3197 if ((ret) && (counter->min != counter->max))
3198 deter = 0;
3199 } else if (atom == NULL) {
3200 fprintf(stderr, "epsilon transition left at runtime\n");
3201 exec->status = -2;
3202 break;
3203 } else if (exec->inputString[exec->index] != 0) {
3204 codepoint = CUR_SCHAR(&(exec->inputString[exec->index]), len);
3205 ret = xmlRegCheckCharacter(atom, codepoint);
3206 if ((ret == 1) && (atom->min >= 0) && (atom->max > 0)) {
3207 xmlRegStatePtr to = comp->states[trans->to];
3208
3209 /*
3210 * this is a multiple input sequence
3211 * If there is a counter associated increment it now.
3212 * before potentially saving and rollback
3213 */
3214 if (trans->counter >= 0) {
3215 if (exec->counts == NULL) {
3216 exec->status = -1;
3217 goto error;
3218 }
3219#ifdef DEBUG_REGEXP_EXEC
3220 printf("Increasing count %d\n", trans->counter);
3221#endif
3222 exec->counts[trans->counter]++;
3223 }
3224 if (exec->state->nbTrans > exec->transno + 1) {
3225 xmlFARegExecSave(exec);
3226 }
3227 exec->transcount = 1;
3228 do {
3229 /*
3230 * Try to progress as much as possible on the input
3231 */
3232 if (exec->transcount == atom->max) {
3233 break;
3234 }
3235 exec->index += len;
3236 /*
3237 * End of input: stop here
3238 */
3239 if (exec->inputString[exec->index] == 0) {
3240 exec->index -= len;
3241 break;
3242 }
3243 if (exec->transcount >= atom->min) {
3244 int transno = exec->transno;
3245 xmlRegStatePtr state = exec->state;
3246
3247 /*
3248 * The transition is acceptable save it
3249 */
3250 exec->transno = -1; /* trick */
3251 exec->state = to;
3252 xmlFARegExecSave(exec);
3253 exec->transno = transno;
3254 exec->state = state;
3255 }
3256 codepoint = CUR_SCHAR(&(exec->inputString[exec->index]),
3257 len);
3258 ret = xmlRegCheckCharacter(atom, codepoint);
3259 exec->transcount++;
3260 } while (ret == 1);
3261 if (exec->transcount < atom->min)
3262 ret = 0;
3263
3264 /*
3265 * If the last check failed but one transition was found
3266 * possible, rollback
3267 */
3268 if (ret < 0)
3269 ret = 0;
3270 if (ret == 0) {
3271 goto rollback;
3272 }
3273 if (trans->counter >= 0) {
3274 if (exec->counts == NULL) {
3275 exec->status = -1;
3276 goto error;
3277 }
3278#ifdef DEBUG_REGEXP_EXEC
3279 printf("Decreasing count %d\n", trans->counter);
3280#endif
3281 exec->counts[trans->counter]--;
3282 }
3283 } else if ((ret == 0) && (atom->min == 0) && (atom->max > 0)) {
3284 /*
3285 * we don't match on the codepoint, but minOccurs of 0
3286 * says that's ok. Setting len to 0 inhibits stepping
3287 * over the codepoint.
3288 */
3289 exec->transcount = 1;
3290 len = 0;
3291 ret = 1;
3292 }
3293 } else if ((atom->min == 0) && (atom->max > 0)) {
3294 /* another spot to match when minOccurs is 0 */
3295 exec->transcount = 1;
3296 len = 0;
3297 ret = 1;
3298 }
3299 if (ret == 1) {
3300 if ((trans->nd == 1) ||
3301 ((trans->count >= 0) && (deter == 0) &&
3302 (exec->state->nbTrans > exec->transno + 1))) {
3303#ifdef DEBUG_REGEXP_EXEC
3304 if (trans->nd == 1)
3305 printf("Saving on nd transition atom %d for %c at %d\n",
3306 trans->atom->no, codepoint, exec->index);
3307 else
3308 printf("Saving on counted transition count %d for %c at %d\n",
3309 trans->count, codepoint, exec->index);
3310#endif
3311 xmlFARegExecSave(exec);
3312 }
3313 if (trans->counter >= 0) {
3314 if (exec->counts == NULL) {
3315 exec->status = -1;
3316 goto error;
3317 }
3318#ifdef DEBUG_REGEXP_EXEC
3319 printf("Increasing count %d\n", trans->counter);
3320#endif
3321 exec->counts[trans->counter]++;
3322 }
3323 if ((trans->count >= 0) &&
3324 (trans->count < REGEXP_ALL_COUNTER)) {
3325 if (exec->counts == NULL) {
3326 exec->status = -1;
3327 goto error;
3328 }
3329#ifdef DEBUG_REGEXP_EXEC
3330 printf("resetting count %d on transition\n",
3331 trans->count);
3332#endif
3333 exec->counts[trans->count] = 0;
3334 }
3335#ifdef DEBUG_REGEXP_EXEC
3336 printf("entering state %d\n", trans->to);
3337#endif
3338 exec->state = comp->states[trans->to];
3339 exec->transno = 0;
3340 if (trans->atom != NULL) {
3341 exec->index += len;
3342 }
3343 goto progress;
3344 } else if (ret < 0) {
3345 exec->status = -4;
3346 break;
3347 }
3348 }
3349 if ((exec->transno != 0) || (exec->state->nbTrans == 0)) {
3350rollback:
3351 /*
3352 * Failed to find a way out
3353 */
3354 exec->determinist = 0;
3355#ifdef DEBUG_REGEXP_EXEC
3356 printf("rollback from state %d on %d:%c\n", exec->state->no,
3357 codepoint,codepoint);
3358#endif
3359 xmlFARegExecRollBack(exec);
3360 }
3361progress:
3362 continue;
3363 }
3364error:
3365 if (exec->rollbacks != NULL) {
3366 if (exec->counts != NULL) {
3367 int i;
3368
3369 for (i = 0;i < exec->maxRollbacks;i++)
3370 if (exec->rollbacks[i].counts != NULL)
3371 xmlFree(exec->rollbacks[i].counts);
3372 }
3373 xmlFree(exec->rollbacks);
3374 }
3375 if (exec->counts != NULL)
3376 xmlFree(exec->counts);
3377 if (exec->status == 0)
3378 return(1);
3379 if (exec->status == -1) {
3380 if (exec->nbPush > MAX_PUSH)
3381 return(-1);
3382 return(0);
3383 }
3384 return(exec->status);
3385}
3386
3387/************************************************************************
3388 * *
3389 * Progressive interface to the verifier one atom at a time *
3390 * *
3391 ************************************************************************/
3392#ifdef DEBUG_ERR
3393static void testerr(xmlRegExecCtxtPtr exec);
3394#endif
3395
3396/**
3397 * xmlRegNewExecCtxt:
3398 * @comp: a precompiled regular expression
3399 * @callback: a callback function used for handling progresses in the
3400 * automata matching phase
3401 * @data: the context data associated to the callback in this context
3402 *
3403 * Build a context used for progressive evaluation of a regexp.
3404 *
3405 * Returns the new context
3406 */
3407xmlRegExecCtxtPtr
3408xmlRegNewExecCtxt(xmlRegexpPtr comp, xmlRegExecCallbacks callback, void *data) {
3409 xmlRegExecCtxtPtr exec;
3410
3411 if (comp == NULL)
3412 return(NULL);
3413 if ((comp->compact == NULL) && (comp->states == NULL))
3414 return(NULL);
3415 exec = (xmlRegExecCtxtPtr) xmlMalloc(sizeof(xmlRegExecCtxt));
3416 if (exec == NULL) {
3417 xmlRegexpErrMemory(NULL, "creating execution context");
3418 return(NULL);
3419 }
3420 memset(exec, 0, sizeof(xmlRegExecCtxt));
3421 exec->inputString = NULL;
3422 exec->index = 0;
3423 exec->determinist = 1;
3424 exec->maxRollbacks = 0;
3425 exec->nbRollbacks = 0;
3426 exec->rollbacks = NULL;
3427 exec->status = 0;
3428 exec->comp = comp;
3429 if (comp->compact == NULL)
3430 exec->state = comp->states[0];
3431 exec->transno = 0;
3432 exec->transcount = 0;
3433 exec->callback = callback;
3434 exec->data = data;
3435 if (comp->nbCounters > 0) {
3436 /*
3437 * For error handling, exec->counts is allocated twice the size
3438 * the second half is used to store the data in case of rollback
3439 */
3440 exec->counts = (int *) xmlMalloc(comp->nbCounters * sizeof(int)
3441 * 2);
3442 if (exec->counts == NULL) {
3443 xmlRegexpErrMemory(NULL, "creating execution context");
3444 xmlFree(exec);
3445 return(NULL);
3446 }
3447 memset(exec->counts, 0, comp->nbCounters * sizeof(int) * 2);
3448 exec->errCounts = &exec->counts[comp->nbCounters];
3449 } else {
3450 exec->counts = NULL;
3451 exec->errCounts = NULL;
3452 }
3453 exec->inputStackMax = 0;
3454 exec->inputStackNr = 0;
3455 exec->inputStack = NULL;
3456 exec->errStateNo = -1;
3457 exec->errString = NULL;
3458 exec->nbPush = 0;
3459 return(exec);
3460}
3461
3462/**
3463 * xmlRegFreeExecCtxt:
3464 * @exec: a regular expression evaulation context
3465 *
3466 * Free the structures associated to a regular expression evaulation context.
3467 */
3468void
3469xmlRegFreeExecCtxt(xmlRegExecCtxtPtr exec) {
3470 if (exec == NULL)
3471 return;
3472
3473 if (exec->rollbacks != NULL) {
3474 if (exec->counts != NULL) {
3475 int i;
3476
3477 for (i = 0;i < exec->maxRollbacks;i++)
3478 if (exec->rollbacks[i].counts != NULL)
3479 xmlFree(exec->rollbacks[i].counts);
3480 }
3481 xmlFree(exec->rollbacks);
3482 }
3483 if (exec->counts != NULL)
3484 xmlFree(exec->counts);
3485 if (exec->inputStack != NULL) {
3486 int i;
3487
3488 for (i = 0;i < exec->inputStackNr;i++) {
3489 if (exec->inputStack[i].value != NULL)
3490 xmlFree(exec->inputStack[i].value);
3491 }
3492 xmlFree(exec->inputStack);
3493 }
3494 if (exec->errString != NULL)
3495 xmlFree(exec->errString);
3496 xmlFree(exec);
3497}
3498
3499static void
3500xmlFARegExecSaveInputString(xmlRegExecCtxtPtr exec, const xmlChar *value,
3501 void *data) {
3502#ifdef DEBUG_PUSH
3503 printf("saving value: %d:%s\n", exec->inputStackNr, value);
3504#endif
3505 if (exec->inputStackMax == 0) {
3506 exec->inputStackMax = 4;
3507 exec->inputStack = (xmlRegInputTokenPtr)
3508 xmlMalloc(exec->inputStackMax * sizeof(xmlRegInputToken));
3509 if (exec->inputStack == NULL) {
3510 xmlRegexpErrMemory(NULL, "pushing input string");
3511 exec->inputStackMax = 0;
3512 return;
3513 }
3514 } else if (exec->inputStackNr + 1 >= exec->inputStackMax) {
3515 xmlRegInputTokenPtr tmp;
3516
3517 exec->inputStackMax *= 2;
3518 tmp = (xmlRegInputTokenPtr) xmlRealloc(exec->inputStack,
3519 exec->inputStackMax * sizeof(xmlRegInputToken));
3520 if (tmp == NULL) {
3521 xmlRegexpErrMemory(NULL, "pushing input string");
3522 exec->inputStackMax /= 2;
3523 return;
3524 }
3525 exec->inputStack = tmp;
3526 }
3527 exec->inputStack[exec->inputStackNr].value = xmlStrdup(value);
3528 exec->inputStack[exec->inputStackNr].data = data;
3529 exec->inputStackNr++;
3530 exec->inputStack[exec->inputStackNr].value = NULL;
3531 exec->inputStack[exec->inputStackNr].data = NULL;
3532}
3533
3534/**
3535 * xmlRegStrEqualWildcard:
3536 * @expStr: the string to be evaluated
3537 * @valStr: the validation string
3538 *
3539 * Checks if both strings are equal or have the same content. "*"
3540 * can be used as a wildcard in @valStr; "|" is used as a seperator of
3541 * substrings in both @expStr and @valStr.
3542 *
3543 * Returns 1 if the comparison is satisfied and the number of substrings
3544 * is equal, 0 otherwise.
3545 */
3546
3547static int
3548xmlRegStrEqualWildcard(const xmlChar *expStr, const xmlChar *valStr) {
3549 if (expStr == valStr) return(1);
3550 if (expStr == NULL) return(0);
3551 if (valStr == NULL) return(0);
3552 do {
3553 /*
3554 * Eval if we have a wildcard for the current item.
3555 */
3556 if (*expStr != *valStr) {
3557 /* if one of them starts with a wildcard make valStr be it */
3558 if (*valStr == '*') {
3559 const xmlChar *tmp;
3560
3561 tmp = valStr;
3562 valStr = expStr;
3563 expStr = tmp;
3564 }
3565 if ((*valStr != 0) && (*expStr != 0) && (*expStr++ == '*')) {
3566 do {
3567 if (*valStr == XML_REG_STRING_SEPARATOR)
3568 break;
3569 valStr++;
3570 } while (*valStr != 0);
3571 continue;
3572 } else
3573 return(0);
3574 }
3575 expStr++;
3576 valStr++;
3577 } while (*valStr != 0);
3578 if (*expStr != 0)
3579 return (0);
3580 else
3581 return (1);
3582}
3583
3584/**
3585 * xmlRegCompactPushString:
3586 * @exec: a regexp execution context
3587 * @comp: the precompiled exec with a compact table
3588 * @value: a string token input
3589 * @data: data associated to the token to reuse in callbacks
3590 *
3591 * Push one input token in the execution context
3592 *
3593 * Returns: 1 if the regexp reached a final state, 0 if non-final, and
3594 * a negative value in case of error.
3595 */
3596static int
3597xmlRegCompactPushString(xmlRegExecCtxtPtr exec,
3598 xmlRegexpPtr comp,
3599 const xmlChar *value,
3600 void *data) {
3601 int state = exec->index;
3602 int i, target;
3603
3604 if ((comp == NULL) || (comp->compact == NULL) || (comp->stringMap == NULL))
3605 return(-1);
3606
3607 if (value == NULL) {
3608 /*
3609 * are we at a final state ?
3610 */
3611 if (comp->compact[state * (comp->nbstrings + 1)] ==
3612 XML_REGEXP_FINAL_STATE)
3613 return(1);
3614 return(0);
3615 }
3616
3617#ifdef DEBUG_PUSH
3618 printf("value pushed: %s\n", value);
3619#endif
3620
3621 /*
3622 * Examine all outside transitions from current state
3623 */
3624 for (i = 0;i < comp->nbstrings;i++) {
3625 target = comp->compact[state * (comp->nbstrings + 1) + i + 1];
3626 if ((target > 0) && (target <= comp->nbstates)) {
3627 target--; /* to avoid 0 */
3628 if (xmlRegStrEqualWildcard(comp->stringMap[i], value)) {
3629 exec->index = target;
3630 if ((exec->callback != NULL) && (comp->transdata != NULL)) {
3631 exec->callback(exec->data, value,
3632 comp->transdata[state * comp->nbstrings + i], data);
3633 }
3634#ifdef DEBUG_PUSH
3635 printf("entering state %d\n", target);
3636#endif
3637 if (comp->compact[target * (comp->nbstrings + 1)] ==
3638 XML_REGEXP_SINK_STATE)
3639 goto error;
3640
3641 if (comp->compact[target * (comp->nbstrings + 1)] ==
3642 XML_REGEXP_FINAL_STATE)
3643 return(1);
3644 return(0);
3645 }
3646 }
3647 }
3648 /*
3649 * Failed to find an exit transition out from current state for the
3650 * current token
3651 */
3652#ifdef DEBUG_PUSH
3653 printf("failed to find a transition for %s on state %d\n", value, state);
3654#endif
3655error:
3656 if (exec->errString != NULL)
3657 xmlFree(exec->errString);
3658 exec->errString = xmlStrdup(value);
3659 exec->errStateNo = state;
3660 exec->status = -1;
3661#ifdef DEBUG_ERR
3662 testerr(exec);
3663#endif
3664 return(-1);
3665}
3666
3667/**
3668 * xmlRegExecPushStringInternal:
3669 * @exec: a regexp execution context or NULL to indicate the end
3670 * @value: a string token input
3671 * @data: data associated to the token to reuse in callbacks
3672 * @compound: value was assembled from 2 strings
3673 *
3674 * Push one input token in the execution context
3675 *
3676 * Returns: 1 if the regexp reached a final state, 0 if non-final, and
3677 * a negative value in case of error.
3678 */
3679static int
3680xmlRegExecPushStringInternal(xmlRegExecCtxtPtr exec, const xmlChar *value,
3681 void *data, int compound) {
3682 xmlRegTransPtr trans;
3683 xmlRegAtomPtr atom;
3684 int ret;
3685 int final = 0;
3686 int progress = 1;
3687
3688 if (exec == NULL)
3689 return(-1);
3690 if (exec->comp == NULL)
3691 return(-1);
3692 if (exec->status != 0)
3693 return(exec->status);
3694
3695 if (exec->comp->compact != NULL)
3696 return(xmlRegCompactPushString(exec, exec->comp, value, data));
3697
3698 if (value == NULL) {
3699 if (exec->state->type == XML_REGEXP_FINAL_STATE)
3700 return(1);
3701 final = 1;
3702 }
3703
3704#ifdef DEBUG_PUSH
3705 printf("value pushed: %s\n", value);
3706#endif
3707 /*
3708 * If we have an active rollback stack push the new value there
3709 * and get back to where we were left
3710 */
3711 if ((value != NULL) && (exec->inputStackNr > 0)) {
3712 xmlFARegExecSaveInputString(exec, value, data);
3713 value = exec->inputStack[exec->index].value;
3714 data = exec->inputStack[exec->index].data;
3715#ifdef DEBUG_PUSH
3716 printf("value loaded: %s\n", value);
3717#endif
3718 }
3719
3720 while ((exec->status == 0) &&
3721 ((value != NULL) ||
3722 ((final == 1) &&
3723 (exec->state->type != XML_REGEXP_FINAL_STATE)))) {
3724
3725 /*
3726 * End of input on non-terminal state, rollback, however we may
3727 * still have epsilon like transition for counted transitions
3728 * on counters, in that case don't break too early.
3729 */
3730 if ((value == NULL) && (exec->counts == NULL))
3731 goto rollback;
3732
3733 exec->transcount = 0;
3734 for (;exec->transno < exec->state->nbTrans;exec->transno++) {
3735 trans = &exec->state->trans[exec->transno];
3736 if (trans->to < 0)
3737 continue;
3738 atom = trans->atom;
3739 ret = 0;
3740 if (trans->count == REGEXP_ALL_LAX_COUNTER) {
3741 int i;
3742 int count;
3743 xmlRegTransPtr t;
3744 xmlRegCounterPtr counter;
3745
3746 ret = 0;
3747
3748#ifdef DEBUG_PUSH
3749 printf("testing all lax %d\n", trans->count);
3750#endif
3751 /*
3752 * Check all counted transitions from the current state
3753 */
3754 if ((value == NULL) && (final)) {
3755 ret = 1;
3756 } else if (value != NULL) {
3757 for (i = 0;i < exec->state->nbTrans;i++) {
3758 t = &exec->state->trans[i];
3759 if ((t->counter < 0) || (t == trans))
3760 continue;
3761 counter = &exec->comp->counters[t->counter];
3762 count = exec->counts[t->counter];
3763 if ((count < counter->max) &&
3764 (t->atom != NULL) &&
3765 (xmlStrEqual(value, t->atom->valuep))) {
3766 ret = 0;
3767 break;
3768 }
3769 if ((count >= counter->min) &&
3770 (count < counter->max) &&
3771 (t->atom != NULL) &&
3772 (xmlStrEqual(value, t->atom->valuep))) {
3773 ret = 1;
3774 break;
3775 }
3776 }
3777 }
3778 } else if (trans->count == REGEXP_ALL_COUNTER) {
3779 int i;
3780 int count;
3781 xmlRegTransPtr t;
3782 xmlRegCounterPtr counter;
3783
3784 ret = 1;
3785
3786#ifdef DEBUG_PUSH
3787 printf("testing all %d\n", trans->count);
3788#endif
3789 /*
3790 * Check all counted transitions from the current state
3791 */
3792 for (i = 0;i < exec->state->nbTrans;i++) {
3793 t = &exec->state->trans[i];
3794 if ((t->counter < 0) || (t == trans))
3795 continue;
3796 counter = &exec->comp->counters[t->counter];
3797 count = exec->counts[t->counter];
3798 if ((count < counter->min) || (count > counter->max)) {
3799 ret = 0;
3800 break;
3801 }
3802 }
3803 } else if (trans->count >= 0) {
3804 int count;
3805 xmlRegCounterPtr counter;
3806
3807 /*
3808 * A counted transition.
3809 */
3810
3811 count = exec->counts[trans->count];
3812 counter = &exec->comp->counters[trans->count];
3813#ifdef DEBUG_PUSH
3814 printf("testing count %d: val %d, min %d, max %d\n",
3815 trans->count, count, counter->min, counter->max);
3816#endif
3817 ret = ((count >= counter->min) && (count <= counter->max));
3818 } else if (atom == NULL) {
3819 fprintf(stderr, "epsilon transition left at runtime\n");
3820 exec->status = -2;
3821 break;
3822 } else if (value != NULL) {
3823 ret = xmlRegStrEqualWildcard(atom->valuep, value);
3824 if (atom->neg) {
3825 ret = !ret;
3826 if (!compound)
3827 ret = 0;
3828 }
3829 if ((ret == 1) && (trans->counter >= 0)) {
3830 xmlRegCounterPtr counter;
3831 int count;
3832
3833 count = exec->counts[trans->counter];
3834 counter = &exec->comp->counters[trans->counter];
3835 if (count >= counter->max)
3836 ret = 0;
3837 }
3838
3839 if ((ret == 1) && (atom->min > 0) && (atom->max > 0)) {
3840 xmlRegStatePtr to = exec->comp->states[trans->to];
3841
3842 /*
3843 * this is a multiple input sequence
3844 */
3845 if (exec->state->nbTrans > exec->transno + 1) {
3846 if (exec->inputStackNr <= 0) {
3847 xmlFARegExecSaveInputString(exec, value, data);
3848 }
3849 xmlFARegExecSave(exec);
3850 }
3851 exec->transcount = 1;
3852 do {
3853 /*
3854 * Try to progress as much as possible on the input
3855 */
3856 if (exec->transcount == atom->max) {
3857 break;
3858 }
3859 exec->index++;
3860 value = exec->inputStack[exec->index].value;
3861 data = exec->inputStack[exec->index].data;
3862#ifdef DEBUG_PUSH
3863 printf("value loaded: %s\n", value);
3864#endif
3865
3866 /*
3867 * End of input: stop here
3868 */
3869 if (value == NULL) {
3870 exec->index --;
3871 break;
3872 }
3873 if (exec->transcount >= atom->min) {
3874 int transno = exec->transno;
3875 xmlRegStatePtr state = exec->state;
3876
3877 /*
3878 * The transition is acceptable save it
3879 */
3880 exec->transno = -1; /* trick */
3881 exec->state = to;
3882 if (exec->inputStackNr <= 0) {
3883 xmlFARegExecSaveInputString(exec, value, data);
3884 }
3885 xmlFARegExecSave(exec);
3886 exec->transno = transno;
3887 exec->state = state;
3888 }
3889 ret = xmlStrEqual(value, atom->valuep);
3890 exec->transcount++;
3891 } while (ret == 1);
3892 if (exec->transcount < atom->min)
3893 ret = 0;
3894
3895 /*
3896 * If the last check failed but one transition was found
3897 * possible, rollback
3898 */
3899 if (ret < 0)
3900 ret = 0;
3901 if (ret == 0) {
3902 goto rollback;
3903 }
3904 }
3905 }
3906 if (ret == 1) {
3907 if ((exec->callback != NULL) && (atom != NULL) &&
3908 (data != NULL)) {
3909 exec->callback(exec->data, atom->valuep,
3910 atom->data, data);
3911 }
3912 if (exec->state->nbTrans > exec->transno + 1) {
3913 if (exec->inputStackNr <= 0) {
3914 xmlFARegExecSaveInputString(exec, value, data);
3915 }
3916 xmlFARegExecSave(exec);
3917 }
3918 if (trans->counter >= 0) {
3919#ifdef DEBUG_PUSH
3920 printf("Increasing count %d\n", trans->counter);
3921#endif
3922 exec->counts[trans->counter]++;
3923 }
3924 if ((trans->count >= 0) &&
3925 (trans->count < REGEXP_ALL_COUNTER)) {
3926#ifdef DEBUG_REGEXP_EXEC
3927 printf("resetting count %d on transition\n",
3928 trans->count);
3929#endif
3930 exec->counts[trans->count] = 0;
3931 }
3932#ifdef DEBUG_PUSH
3933 printf("entering state %d\n", trans->to);
3934#endif
3935 if ((exec->comp->states[trans->to] != NULL) &&
3936 (exec->comp->states[trans->to]->type ==
3937 XML_REGEXP_SINK_STATE)) {
3938 /*
3939 * entering a sink state, save the current state as error
3940 * state.
3941 */
3942 if (exec->errString != NULL)
3943 xmlFree(exec->errString);
3944 exec->errString = xmlStrdup(value);
3945 exec->errState = exec->state;
3946 memcpy(exec->errCounts, exec->counts,
3947 exec->comp->nbCounters * sizeof(int));
3948 }
3949 exec->state = exec->comp->states[trans->to];
3950 exec->transno = 0;
3951 if (trans->atom != NULL) {
3952 if (exec->inputStack != NULL) {
3953 exec->index++;
3954 if (exec->index < exec->inputStackNr) {
3955 value = exec->inputStack[exec->index].value;
3956 data = exec->inputStack[exec->index].data;
3957#ifdef DEBUG_PUSH
3958 printf("value loaded: %s\n", value);
3959#endif
3960 } else {
3961 value = NULL;
3962 data = NULL;
3963#ifdef DEBUG_PUSH
3964 printf("end of input\n");
3965#endif
3966 }
3967 } else {
3968 value = NULL;
3969 data = NULL;
3970#ifdef DEBUG_PUSH
3971 printf("end of input\n");
3972#endif
3973 }
3974 }
3975 goto progress;
3976 } else if (ret < 0) {
3977 exec->status = -4;
3978 break;
3979 }
3980 }
3981 if ((exec->transno != 0) || (exec->state->nbTrans == 0)) {
3982rollback:
3983 /*
3984 * if we didn't yet rollback on the current input
3985 * store the current state as the error state.
3986 */
3987 if ((progress) && (exec->state != NULL) &&
3988 (exec->state->type != XML_REGEXP_SINK_STATE)) {
3989 progress = 0;
3990 if (exec->errString != NULL)
3991 xmlFree(exec->errString);
3992 exec->errString = xmlStrdup(value);
3993 exec->errState = exec->state;
3994 memcpy(exec->errCounts, exec->counts,
3995 exec->comp->nbCounters * sizeof(int));
3996 }
3997
3998 /*
3999 * Failed to find a way out
4000 */
4001 exec->determinist = 0;
4002 xmlFARegExecRollBack(exec);
4003 if (exec->status == 0) {
4004 value = exec->inputStack[exec->index].value;
4005 data = exec->inputStack[exec->index].data;
4006#ifdef DEBUG_PUSH
4007 printf("value loaded: %s\n", value);
4008#endif
4009 }
4010 }
4011 continue;
4012progress:
4013 progress = 1;
4014 continue;
4015 }
4016 if (exec->status == 0) {
4017 return(exec->state->type == XML_REGEXP_FINAL_STATE);
4018 }
4019#ifdef DEBUG_ERR
4020 if (exec->status < 0) {
4021 testerr(exec);
4022 }
4023#endif
4024 return(exec->status);
4025}
4026
4027/**
4028 * xmlRegExecPushString:
4029 * @exec: a regexp execution context or NULL to indicate the end
4030 * @value: a string token input
4031 * @data: data associated to the token to reuse in callbacks
4032 *
4033 * Push one input token in the execution context
4034 *
4035 * Returns: 1 if the regexp reached a final state, 0 if non-final, and
4036 * a negative value in case of error.
4037 */
4038int
4039xmlRegExecPushString(xmlRegExecCtxtPtr exec, const xmlChar *value,
4040 void *data) {
4041 return(xmlRegExecPushStringInternal(exec, value, data, 0));
4042}
4043
4044/**
4045 * xmlRegExecPushString2:
4046 * @exec: a regexp execution context or NULL to indicate the end
4047 * @value: the first string token input
4048 * @value2: the second string token input
4049 * @data: data associated to the token to reuse in callbacks
4050 *
4051 * Push one input token in the execution context
4052 *
4053 * Returns: 1 if the regexp reached a final state, 0 if non-final, and
4054 * a negative value in case of error.
4055 */
4056int
4057xmlRegExecPushString2(xmlRegExecCtxtPtr exec, const xmlChar *value,
4058 const xmlChar *value2, void *data) {
4059 xmlChar buf[150];
4060 int lenn, lenp, ret;
4061 xmlChar *str;
4062
4063 if (exec == NULL)
4064 return(-1);
4065 if (exec->comp == NULL)
4066 return(-1);
4067 if (exec->status != 0)
4068 return(exec->status);
4069
4070 if (value2 == NULL)
4071 return(xmlRegExecPushString(exec, value, data));
4072
4073 lenn = strlen((char *) value2);
4074 lenp = strlen((char *) value);
4075
4076 if (150 < lenn + lenp + 2) {
4077 str = (xmlChar *) xmlMallocAtomic(lenn + lenp + 2);
4078 if (str == NULL) {
4079 exec->status = -1;
4080 return(-1);
4081 }
4082 } else {
4083 str = buf;
4084 }
4085 memcpy(&str[0], value, lenp);
4086 str[lenp] = XML_REG_STRING_SEPARATOR;
4087 memcpy(&str[lenp + 1], value2, lenn);
4088 str[lenn + lenp + 1] = 0;
4089
4090 if (exec->comp->compact != NULL)
4091 ret = xmlRegCompactPushString(exec, exec->comp, str, data);
4092 else
4093 ret = xmlRegExecPushStringInternal(exec, str, data, 1);
4094
4095 if (str != buf)
4096 xmlFree(str);
4097 return(ret);
4098}
4099
4100/**
4101 * xmlRegExecGetValues:
4102 * @exec: a regexp execution context
4103 * @err: error extraction or normal one
4104 * @nbval: pointer to the number of accepted values IN/OUT
4105 * @nbneg: return number of negative transitions
4106 * @values: pointer to the array of acceptable values
4107 * @terminal: return value if this was a terminal state
4108 *
4109 * Extract informations from the regexp execution, internal routine to
4110 * implement xmlRegExecNextValues() and xmlRegExecErrInfo()
4111 *
4112 * Returns: 0 in case of success or -1 in case of error.
4113 */
4114static int
4115xmlRegExecGetValues(xmlRegExecCtxtPtr exec, int err,
4116 int *nbval, int *nbneg,
4117 xmlChar **values, int *terminal) {
4118 int maxval;
4119 int nb = 0;
4120
4121 if ((exec == NULL) || (nbval == NULL) || (nbneg == NULL) ||
4122 (values == NULL) || (*nbval <= 0))
4123 return(-1);
4124
4125 maxval = *nbval;
4126 *nbval = 0;
4127 *nbneg = 0;
4128 if ((exec->comp != NULL) && (exec->comp->compact != NULL)) {
4129 xmlRegexpPtr comp;
4130 int target, i, state;
4131
4132 comp = exec->comp;
4133
4134 if (err) {
4135 if (exec->errStateNo == -1) return(-1);
4136 state = exec->errStateNo;
4137 } else {
4138 state = exec->index;
4139 }
4140 if (terminal != NULL) {
4141 if (comp->compact[state * (comp->nbstrings + 1)] ==
4142 XML_REGEXP_FINAL_STATE)
4143 *terminal = 1;
4144 else
4145 *terminal = 0;
4146 }
4147 for (i = 0;(i < comp->nbstrings) && (nb < maxval);i++) {
4148 target = comp->compact[state * (comp->nbstrings + 1) + i + 1];
4149 if ((target > 0) && (target <= comp->nbstates) &&
4150 (comp->compact[(target - 1) * (comp->nbstrings + 1)] !=
4151 XML_REGEXP_SINK_STATE)) {
4152 values[nb++] = comp->stringMap[i];
4153 (*nbval)++;
4154 }
4155 }
4156 for (i = 0;(i < comp->nbstrings) && (nb < maxval);i++) {
4157 target = comp->compact[state * (comp->nbstrings + 1) + i + 1];
4158 if ((target > 0) && (target <= comp->nbstates) &&
4159 (comp->compact[(target - 1) * (comp->nbstrings + 1)] ==
4160 XML_REGEXP_SINK_STATE)) {
4161 values[nb++] = comp->stringMap[i];
4162 (*nbneg)++;
4163 }
4164 }
4165 } else {
4166 int transno;
4167 xmlRegTransPtr trans;
4168 xmlRegAtomPtr atom;
4169 xmlRegStatePtr state;
4170
4171 if (terminal != NULL) {
4172 if (exec->state->type == XML_REGEXP_FINAL_STATE)
4173 *terminal = 1;
4174 else
4175 *terminal = 0;
4176 }
4177
4178 if (err) {
4179 if (exec->errState == NULL) return(-1);
4180 state = exec->errState;
4181 } else {
4182 if (exec->state == NULL) return(-1);
4183 state = exec->state;
4184 }
4185 for (transno = 0;
4186 (transno < state->nbTrans) && (nb < maxval);
4187 transno++) {
4188 trans = &state->trans[transno];
4189 if (trans->to < 0)
4190 continue;
4191 atom = trans->atom;
4192 if ((atom == NULL) || (atom->valuep == NULL))
4193 continue;
4194 if (trans->count == REGEXP_ALL_LAX_COUNTER) {
4195 /* this should not be reached but ... */
4196 TODO;
4197 } else if (trans->count == REGEXP_ALL_COUNTER) {
4198 /* this should not be reached but ... */
4199 TODO;
4200 } else if (trans->counter >= 0) {
4201 xmlRegCounterPtr counter = NULL;
4202 int count;
4203
4204 if (err)
4205 count = exec->errCounts[trans->counter];
4206 else
4207 count = exec->counts[trans->counter];
4208 if (exec->comp != NULL)
4209 counter = &exec->comp->counters[trans->counter];
4210 if ((counter == NULL) || (count < counter->max)) {
4211 if (atom->neg)
4212 values[nb++] = (xmlChar *) atom->valuep2;
4213 else
4214 values[nb++] = (xmlChar *) atom->valuep;
4215 (*nbval)++;
4216 }
4217 } else {
4218 if ((exec->comp->states[trans->to] != NULL) &&
4219 (exec->comp->states[trans->to]->type !=
4220 XML_REGEXP_SINK_STATE)) {
4221 if (atom->neg)
4222 values[nb++] = (xmlChar *) atom->valuep2;
4223 else
4224 values[nb++] = (xmlChar *) atom->valuep;
4225 (*nbval)++;
4226 }
4227 }
4228 }
4229 for (transno = 0;
4230 (transno < state->nbTrans) && (nb < maxval);
4231 transno++) {
4232 trans = &state->trans[transno];
4233 if (trans->to < 0)
4234 continue;
4235 atom = trans->atom;
4236 if ((atom == NULL) || (atom->valuep == NULL))
4237 continue;
4238 if (trans->count == REGEXP_ALL_LAX_COUNTER) {
4239 continue;
4240 } else if (trans->count == REGEXP_ALL_COUNTER) {
4241 continue;
4242 } else if (trans->counter >= 0) {
4243 continue;
4244 } else {
4245 if ((exec->comp->states[trans->to] != NULL) &&
4246 (exec->comp->states[trans->to]->type ==
4247 XML_REGEXP_SINK_STATE)) {
4248 if (atom->neg)
4249 values[nb++] = (xmlChar *) atom->valuep2;
4250 else
4251 values[nb++] = (xmlChar *) atom->valuep;
4252 (*nbneg)++;
4253 }
4254 }
4255 }
4256 }
4257 return(0);
4258}
4259
4260/**
4261 * xmlRegExecNextValues:
4262 * @exec: a regexp execution context
4263 * @nbval: pointer to the number of accepted values IN/OUT
4264 * @nbneg: return number of negative transitions
4265 * @values: pointer to the array of acceptable values
4266 * @terminal: return value if this was a terminal state
4267 *
4268 * Extract informations from the regexp execution,
4269 * the parameter @values must point to an array of @nbval string pointers
4270 * on return nbval will contain the number of possible strings in that
4271 * state and the @values array will be updated with them. The string values
4272 * returned will be freed with the @exec context and don't need to be
4273 * deallocated.
4274 *
4275 * Returns: 0 in case of success or -1 in case of error.
4276 */
4277int
4278xmlRegExecNextValues(xmlRegExecCtxtPtr exec, int *nbval, int *nbneg,
4279 xmlChar **values, int *terminal) {
4280 return(xmlRegExecGetValues(exec, 0, nbval, nbneg, values, terminal));
4281}
4282
4283/**
4284 * xmlRegExecErrInfo:
4285 * @exec: a regexp execution context generating an error
4286 * @string: return value for the error string
4287 * @nbval: pointer to the number of accepted values IN/OUT
4288 * @nbneg: return number of negative transitions
4289 * @values: pointer to the array of acceptable values
4290 * @terminal: return value if this was a terminal state
4291 *
4292 * Extract error informations from the regexp execution, the parameter
4293 * @string will be updated with the value pushed and not accepted,
4294 * the parameter @values must point to an array of @nbval string pointers
4295 * on return nbval will contain the number of possible strings in that
4296 * state and the @values array will be updated with them. The string values
4297 * returned will be freed with the @exec context and don't need to be
4298 * deallocated.
4299 *
4300 * Returns: 0 in case of success or -1 in case of error.
4301 */
4302int
4303xmlRegExecErrInfo(xmlRegExecCtxtPtr exec, const xmlChar **string,
4304 int *nbval, int *nbneg, xmlChar **values, int *terminal) {
4305 if (exec == NULL)
4306 return(-1);
4307 if (string != NULL) {
4308 if (exec->status != 0)
4309 *string = exec->errString;
4310 else
4311 *string = NULL;
4312 }
4313 return(xmlRegExecGetValues(exec, 1, nbval, nbneg, values, terminal));
4314}
4315
4316#ifdef DEBUG_ERR
4317static void testerr(xmlRegExecCtxtPtr exec) {
4318 const xmlChar *string;
4319 xmlChar *values[5];
4320 int nb = 5;
4321 int nbneg;
4322 int terminal;
4323 xmlRegExecErrInfo(exec, &string, &nb, &nbneg, &values[0], &terminal);
4324}
4325#endif
4326
4327#if 0
4328static int
4329xmlRegExecPushChar(xmlRegExecCtxtPtr exec, int UCS) {
4330 xmlRegTransPtr trans;
4331 xmlRegAtomPtr atom;
4332 int ret;
4333 int codepoint, len;
4334
4335 if (exec == NULL)
4336 return(-1);
4337 if (exec->status != 0)
4338 return(exec->status);
4339
4340 while ((exec->status == 0) &&
4341 ((exec->inputString[exec->index] != 0) ||
4342 (exec->state->type != XML_REGEXP_FINAL_STATE))) {
4343
4344 /*
4345 * End of input on non-terminal state, rollback, however we may
4346 * still have epsilon like transition for counted transitions
4347 * on counters, in that case don't break too early.
4348 */
4349 if ((exec->inputString[exec->index] == 0) && (exec->counts == NULL))
4350 goto rollback;
4351
4352 exec->transcount = 0;
4353 for (;exec->transno < exec->state->nbTrans;exec->transno++) {
4354 trans = &exec->state->trans[exec->transno];
4355 if (trans->to < 0)
4356 continue;
4357 atom = trans->atom;
4358 ret = 0;
4359 if (trans->count >= 0) {
4360 int count;
4361 xmlRegCounterPtr counter;
4362
4363 /*
4364 * A counted transition.
4365 */
4366
4367 count = exec->counts[trans->count];
4368 counter = &exec->comp->counters[trans->count];
4369#ifdef DEBUG_REGEXP_EXEC
4370 printf("testing count %d: val %d, min %d, max %d\n",
4371 trans->count, count, counter->min, counter->max);
4372#endif
4373 ret = ((count >= counter->min) && (count <= counter->max));
4374 } else if (atom == NULL) {
4375 fprintf(stderr, "epsilon transition left at runtime\n");
4376 exec->status = -2;
4377 break;
4378 } else if (exec->inputString[exec->index] != 0) {
4379 codepoint = CUR_SCHAR(&(exec->inputString[exec->index]), len);
4380 ret = xmlRegCheckCharacter(atom, codepoint);
4381 if ((ret == 1) && (atom->min > 0) && (atom->max > 0)) {
4382 xmlRegStatePtr to = exec->comp->states[trans->to];
4383
4384 /*
4385 * this is a multiple input sequence
4386 */
4387 if (exec->state->nbTrans > exec->transno + 1) {
4388 xmlFARegExecSave(exec);
4389 }
4390 exec->transcount = 1;
4391 do {
4392 /*
4393 * Try to progress as much as possible on the input
4394 */
4395 if (exec->transcount == atom->max) {
4396 break;
4397 }
4398 exec->index += len;
4399 /*
4400 * End of input: stop here
4401 */
4402 if (exec->inputString[exec->index] == 0) {
4403 exec->index -= len;
4404 break;
4405 }
4406 if (exec->transcount >= atom->min) {
4407 int transno = exec->transno;
4408 xmlRegStatePtr state = exec->state;
4409
4410 /*
4411 * The transition is acceptable save it
4412 */
4413 exec->transno = -1; /* trick */
4414 exec->state = to;
4415 xmlFARegExecSave(exec);
4416 exec->transno = transno;
4417 exec->state = state;
4418 }
4419 codepoint = CUR_SCHAR(&(exec->inputString[exec->index]),
4420 len);
4421 ret = xmlRegCheckCharacter(atom, codepoint);
4422 exec->transcount++;
4423 } while (ret == 1);
4424 if (exec->transcount < atom->min)
4425 ret = 0;
4426
4427 /*
4428 * If the last check failed but one transition was found
4429 * possible, rollback
4430 */
4431 if (ret < 0)
4432 ret = 0;
4433 if (ret == 0) {
4434 goto rollback;
4435 }
4436 }
4437 }
4438 if (ret == 1) {
4439 if (exec->state->nbTrans > exec->transno + 1) {
4440 xmlFARegExecSave(exec);
4441 }
4442 /*
4443 * restart count for expressions like this ((abc){2})*
4444 */
4445 if (trans->count >= 0) {
4446#ifdef DEBUG_REGEXP_EXEC
4447 printf("Reset count %d\n", trans->count);
4448#endif
4449 exec->counts[trans->count] = 0;
4450 }
4451 if (trans->counter >= 0) {
4452#ifdef DEBUG_REGEXP_EXEC
4453 printf("Increasing count %d\n", trans->counter);
4454#endif
4455 exec->counts[trans->counter]++;
4456 }
4457#ifdef DEBUG_REGEXP_EXEC
4458 printf("entering state %d\n", trans->to);
4459#endif
4460 exec->state = exec->comp->states[trans->to];
4461 exec->transno = 0;
4462 if (trans->atom != NULL) {
4463 exec->index += len;
4464 }
4465 goto progress;
4466 } else if (ret < 0) {
4467 exec->status = -4;
4468 break;
4469 }
4470 }
4471 if ((exec->transno != 0) || (exec->state->nbTrans == 0)) {
4472rollback:
4473 /*
4474 * Failed to find a way out
4475 */
4476 exec->determinist = 0;
4477 xmlFARegExecRollBack(exec);
4478 }
4479progress:
4480 continue;
4481 }
4482}
4483#endif
4484/************************************************************************
4485 * *
4486 * Parser for the Schemas Datatype Regular Expressions *
4487 * http://www.w3.org/TR/2001/REC-xmlschema-2-20010502/#regexs *
4488 * *
4489 ************************************************************************/
4490
4491/**
4492 * xmlFAIsChar:
4493 * @ctxt: a regexp parser context
4494 *
4495 * [10] Char ::= [^.\?*+()|#x5B#x5D]
4496 */
4497static int
4498xmlFAIsChar(xmlRegParserCtxtPtr ctxt) {
4499 int cur;
4500 int len;
4501
4502 cur = CUR_SCHAR(ctxt->cur, len);
4503 if ((cur == '.') || (cur == '\\') || (cur == '?') ||
4504 (cur == '*') || (cur == '+') || (cur == '(') ||
4505 (cur == ')') || (cur == '|') || (cur == 0x5B) ||
4506 (cur == 0x5D) || (cur == 0))
4507 return(-1);
4508 return(cur);
4509}
4510
4511/**
4512 * xmlFAParseCharProp:
4513 * @ctxt: a regexp parser context
4514 *
4515 * [27] charProp ::= IsCategory | IsBlock
4516 * [28] IsCategory ::= Letters | Marks | Numbers | Punctuation |
4517 * Separators | Symbols | Others
4518 * [29] Letters ::= 'L' [ultmo]?
4519 * [30] Marks ::= 'M' [nce]?
4520 * [31] Numbers ::= 'N' [dlo]?
4521 * [32] Punctuation ::= 'P' [cdseifo]?
4522 * [33] Separators ::= 'Z' [slp]?
4523 * [34] Symbols ::= 'S' [mcko]?
4524 * [35] Others ::= 'C' [cfon]?
4525 * [36] IsBlock ::= 'Is' [a-zA-Z0-9#x2D]+
4526 */
4527static void
4528xmlFAParseCharProp(xmlRegParserCtxtPtr ctxt) {
4529 int cur;
4530 xmlRegAtomType type = (xmlRegAtomType) 0;
4531 xmlChar *blockName = NULL;
4532
4533 cur = CUR;
4534 if (cur == 'L') {
4535 NEXT;
4536 cur = CUR;
4537 if (cur == 'u') {
4538 NEXT;
4539 type = XML_REGEXP_LETTER_UPPERCASE;
4540 } else if (cur == 'l') {
4541 NEXT;
4542 type = XML_REGEXP_LETTER_LOWERCASE;
4543 } else if (cur == 't') {
4544 NEXT;
4545 type = XML_REGEXP_LETTER_TITLECASE;
4546 } else if (cur == 'm') {
4547 NEXT;
4548 type = XML_REGEXP_LETTER_MODIFIER;
4549 } else if (cur == 'o') {
4550 NEXT;
4551 type = XML_REGEXP_LETTER_OTHERS;
4552 } else {
4553 type = XML_REGEXP_LETTER;
4554 }
4555 } else if (cur == 'M') {
4556 NEXT;
4557 cur = CUR;
4558 if (cur == 'n') {
4559 NEXT;
4560 /* nonspacing */
4561 type = XML_REGEXP_MARK_NONSPACING;
4562 } else if (cur == 'c') {
4563 NEXT;
4564 /* spacing combining */
4565 type = XML_REGEXP_MARK_SPACECOMBINING;
4566 } else if (cur == 'e') {
4567 NEXT;
4568 /* enclosing */
4569 type = XML_REGEXP_MARK_ENCLOSING;
4570 } else {
4571 /* all marks */
4572 type = XML_REGEXP_MARK;
4573 }
4574 } else if (cur == 'N') {
4575 NEXT;
4576 cur = CUR;
4577 if (cur == 'd') {
4578 NEXT;
4579 /* digital */
4580 type = XML_REGEXP_NUMBER_DECIMAL;
4581 } else if (cur == 'l') {
4582 NEXT;
4583 /* letter */
4584 type = XML_REGEXP_NUMBER_LETTER;
4585 } else if (cur == 'o') {
4586 NEXT;
4587 /* other */
4588 type = XML_REGEXP_NUMBER_OTHERS;
4589 } else {
4590 /* all numbers */
4591 type = XML_REGEXP_NUMBER;
4592 }
4593 } else if (cur == 'P') {
4594 NEXT;
4595 cur = CUR;
4596 if (cur == 'c') {
4597 NEXT;
4598 /* connector */
4599 type = XML_REGEXP_PUNCT_CONNECTOR;
4600 } else if (cur == 'd') {
4601 NEXT;
4602 /* dash */
4603 type = XML_REGEXP_PUNCT_DASH;
4604 } else if (cur == 's') {
4605 NEXT;
4606 /* open */
4607 type = XML_REGEXP_PUNCT_OPEN;
4608 } else if (cur == 'e') {
4609 NEXT;
4610 /* close */
4611 type = XML_REGEXP_PUNCT_CLOSE;
4612 } else if (cur == 'i') {
4613 NEXT;
4614 /* initial quote */
4615 type = XML_REGEXP_PUNCT_INITQUOTE;
4616 } else if (cur == 'f') {
4617 NEXT;
4618 /* final quote */
4619 type = XML_REGEXP_PUNCT_FINQUOTE;
4620 } else if (cur == 'o') {
4621 NEXT;
4622 /* other */
4623 type = XML_REGEXP_PUNCT_OTHERS;
4624 } else {
4625 /* all punctuation */
4626 type = XML_REGEXP_PUNCT;
4627 }
4628 } else if (cur == 'Z') {
4629 NEXT;
4630 cur = CUR;
4631 if (cur == 's') {
4632 NEXT;
4633 /* space */
4634 type = XML_REGEXP_SEPAR_SPACE;
4635 } else if (cur == 'l') {
4636 NEXT;
4637 /* line */
4638 type = XML_REGEXP_SEPAR_LINE;
4639 } else if (cur == 'p') {
4640 NEXT;
4641 /* paragraph */
4642 type = XML_REGEXP_SEPAR_PARA;
4643 } else {
4644 /* all separators */
4645 type = XML_REGEXP_SEPAR;
4646 }
4647 } else if (cur == 'S') {
4648 NEXT;
4649 cur = CUR;
4650 if (cur == 'm') {
4651 NEXT;
4652 type = XML_REGEXP_SYMBOL_MATH;
4653 /* math */
4654 } else if (cur == 'c') {
4655 NEXT;
4656 type = XML_REGEXP_SYMBOL_CURRENCY;
4657 /* currency */
4658 } else if (cur == 'k') {
4659 NEXT;
4660 type = XML_REGEXP_SYMBOL_MODIFIER;
4661 /* modifiers */
4662 } else if (cur == 'o') {
4663 NEXT;
4664 type = XML_REGEXP_SYMBOL_OTHERS;
4665 /* other */
4666 } else {
4667 /* all symbols */
4668 type = XML_REGEXP_SYMBOL;
4669 }
4670 } else if (cur == 'C') {
4671 NEXT;
4672 cur = CUR;
4673 if (cur == 'c') {
4674 NEXT;
4675 /* control */
4676 type = XML_REGEXP_OTHER_CONTROL;
4677 } else if (cur == 'f') {
4678 NEXT;
4679 /* format */
4680 type = XML_REGEXP_OTHER_FORMAT;
4681 } else if (cur == 'o') {
4682 NEXT;
4683 /* private use */
4684 type = XML_REGEXP_OTHER_PRIVATE;
4685 } else if (cur == 'n') {
4686 NEXT;
4687 /* not assigned */
4688 type = XML_REGEXP_OTHER_NA;
4689 } else {
4690 /* all others */
4691 type = XML_REGEXP_OTHER;
4692 }
4693 } else if (cur == 'I') {
4694 const xmlChar *start;
4695 NEXT;
4696 cur = CUR;
4697 if (cur != 's') {
4698 ERROR("IsXXXX expected");
4699 return;
4700 }
4701 NEXT;
4702 start = ctxt->cur;
4703 cur = CUR;
4704 if (((cur >= 'a') && (cur <= 'z')) ||
4705 ((cur >= 'A') && (cur <= 'Z')) ||
4706 ((cur >= '0') && (cur <= '9')) ||
4707 (cur == 0x2D)) {
4708 NEXT;
4709 cur = CUR;
4710 while (((cur >= 'a') && (cur <= 'z')) ||
4711 ((cur >= 'A') && (cur <= 'Z')) ||
4712 ((cur >= '0') && (cur <= '9')) ||
4713 (cur == 0x2D)) {
4714 NEXT;
4715 cur = CUR;
4716 }
4717 }
4718 type = XML_REGEXP_BLOCK_NAME;
4719 blockName = xmlStrndup(start, ctxt->cur - start);
4720 } else {
4721 ERROR("Unknown char property");
4722 return;
4723 }
4724 if (ctxt->atom == NULL) {
4725 ctxt->atom = xmlRegNewAtom(ctxt, type);
4726 if (ctxt->atom != NULL)
4727 ctxt->atom->valuep = blockName;
4728 } else if (ctxt->atom->type == XML_REGEXP_RANGES) {
4729 xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,
4730 type, 0, 0, blockName);
4731 }
4732}
4733
4734/**
4735 * xmlFAParseCharClassEsc:
4736 * @ctxt: a regexp parser context
4737 *
4738 * [23] charClassEsc ::= ( SingleCharEsc | MultiCharEsc | catEsc | complEsc )
4739 * [24] SingleCharEsc ::= '\' [nrt\|.?*+(){}#x2D#x5B#x5D#x5E]
4740 * [25] catEsc ::= '\p{' charProp '}'
4741 * [26] complEsc ::= '\P{' charProp '}'
4742 * [37] MultiCharEsc ::= '.' | ('\' [sSiIcCdDwW])
4743 */
4744static void
4745xmlFAParseCharClassEsc(xmlRegParserCtxtPtr ctxt) {
4746 int cur;
4747
4748 if (CUR == '.') {
4749 if (ctxt->atom == NULL) {
4750 ctxt->atom = xmlRegNewAtom(ctxt, XML_REGEXP_ANYCHAR);
4751 } else if (ctxt->atom->type == XML_REGEXP_RANGES) {
4752 xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,
4753 XML_REGEXP_ANYCHAR, 0, 0, NULL);
4754 }
4755 NEXT;
4756 return;
4757 }
4758 if (CUR != '\\') {
4759 ERROR("Escaped sequence: expecting \\");
4760 return;
4761 }
4762 NEXT;
4763 cur = CUR;
4764 if (cur == 'p') {
4765 NEXT;
4766 if (CUR != '{') {
4767 ERROR("Expecting '{'");
4768 return;
4769 }
4770 NEXT;
4771 xmlFAParseCharProp(ctxt);
4772 if (CUR != '}') {
4773 ERROR("Expecting '}'");
4774 return;
4775 }
4776 NEXT;
4777 } else if (cur == 'P') {
4778 NEXT;
4779 if (CUR != '{') {
4780 ERROR("Expecting '{'");
4781 return;
4782 }
4783 NEXT;
4784 xmlFAParseCharProp(ctxt);
4785 ctxt->atom->neg = 1;
4786 if (CUR != '}') {
4787 ERROR("Expecting '}'");
4788 return;
4789 }
4790 NEXT;
4791 } else if ((cur == 'n') || (cur == 'r') || (cur == 't') || (cur == '\\') ||
4792 (cur == '|') || (cur == '.') || (cur == '?') || (cur == '*') ||
4793 (cur == '+') || (cur == '(') || (cur == ')') || (cur == '{') ||
4794 (cur == '}') || (cur == 0x2D) || (cur == 0x5B) || (cur == 0x5D) ||
4795 (cur == 0x5E)) {
4796 if (ctxt->atom == NULL) {
4797 ctxt->atom = xmlRegNewAtom(ctxt, XML_REGEXP_CHARVAL);
4798 if (ctxt->atom != NULL) {
4799 switch (cur) {
4800 case 'n':
4801 ctxt->atom->codepoint = '\n';
4802 break;
4803 case 'r':
4804 ctxt->atom->codepoint = '\r';
4805 break;
4806 case 't':
4807 ctxt->atom->codepoint = '\t';
4808 break;
4809 default:
4810 ctxt->atom->codepoint = cur;
4811 }
4812 }
4813 } else if (ctxt->atom->type == XML_REGEXP_RANGES) {
4814 xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,
4815 XML_REGEXP_CHARVAL, cur, cur, NULL);
4816 }
4817 NEXT;
4818 } else if ((cur == 's') || (cur == 'S') || (cur == 'i') || (cur == 'I') ||
4819 (cur == 'c') || (cur == 'C') || (cur == 'd') || (cur == 'D') ||
4820 (cur == 'w') || (cur == 'W')) {
4821 xmlRegAtomType type = XML_REGEXP_ANYSPACE;
4822
4823 switch (cur) {
4824 case 's':
4825 type = XML_REGEXP_ANYSPACE;
4826 break;
4827 case 'S':
4828 type = XML_REGEXP_NOTSPACE;
4829 break;
4830 case 'i':
4831 type = XML_REGEXP_INITNAME;
4832 break;
4833 case 'I':
4834 type = XML_REGEXP_NOTINITNAME;
4835 break;
4836 case 'c':
4837 type = XML_REGEXP_NAMECHAR;
4838 break;
4839 case 'C':
4840 type = XML_REGEXP_NOTNAMECHAR;
4841 break;
4842 case 'd':
4843 type = XML_REGEXP_DECIMAL;
4844 break;
4845 case 'D':
4846 type = XML_REGEXP_NOTDECIMAL;
4847 break;
4848 case 'w':
4849 type = XML_REGEXP_REALCHAR;
4850 break;
4851 case 'W':
4852 type = XML_REGEXP_NOTREALCHAR;
4853 break;
4854 }
4855 NEXT;
4856 if (ctxt->atom == NULL) {
4857 ctxt->atom = xmlRegNewAtom(ctxt, type);
4858 } else if (ctxt->atom->type == XML_REGEXP_RANGES) {
4859 xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,
4860 type, 0, 0, NULL);
4861 }
4862 } else {
4863 ERROR("Wrong escape sequence, misuse of character '\\'");
4864 }
4865}
4866
4867/**
4868 * xmlFAParseCharRef:
4869 * @ctxt: a regexp parser context
4870 *
4871 * [19] XmlCharRef ::= ( '&#' [0-9]+ ';' ) | (' &#x' [0-9a-fA-F]+ ';' )
4872 */
4873static int
4874xmlFAParseCharRef(xmlRegParserCtxtPtr ctxt) {
4875 int ret = 0, cur;
4876
4877 if ((CUR != '&') || (NXT(1) != '#'))
4878 return(-1);
4879 NEXT;
4880 NEXT;
4881 cur = CUR;
4882 if (cur == 'x') {
4883 NEXT;
4884 cur = CUR;
4885 if (((cur >= '0') && (cur <= '9')) ||
4886 ((cur >= 'a') && (cur <= 'f')) ||
4887 ((cur >= 'A') && (cur <= 'F'))) {
4888 while (((cur >= '0') && (cur <= '9')) ||
4889 ((cur >= 'a') && (cur <= 'f')) ||
4890 ((cur >= 'A') && (cur <= 'F'))) {
4891 if ((cur >= '0') && (cur <= '9'))
4892 ret = ret * 16 + cur - '0';
4893 else if ((cur >= 'a') && (cur <= 'f'))
4894 ret = ret * 16 + 10 + (cur - 'a');
4895 else
4896 ret = ret * 16 + 10 + (cur - 'A');
4897 NEXT;
4898 cur = CUR;
4899 }
4900 } else {
4901 ERROR("Char ref: expecting [0-9A-F]");
4902 return(-1);
4903 }
4904 } else {
4905 if ((cur >= '0') && (cur <= '9')) {
4906 while ((cur >= '0') && (cur <= '9')) {
4907 ret = ret * 10 + cur - '0';
4908 NEXT;
4909 cur = CUR;
4910 }
4911 } else {
4912 ERROR("Char ref: expecting [0-9]");
4913 return(-1);
4914 }
4915 }
4916 if (cur != ';') {
4917 ERROR("Char ref: expecting ';'");
4918 return(-1);
4919 } else {
4920 NEXT;
4921 }
4922 return(ret);
4923}
4924
4925/**
4926 * xmlFAParseCharRange:
4927 * @ctxt: a regexp parser context
4928 *
4929 * [17] charRange ::= seRange | XmlCharRef | XmlCharIncDash
4930 * [18] seRange ::= charOrEsc '-' charOrEsc
4931 * [20] charOrEsc ::= XmlChar | SingleCharEsc
4932 * [21] XmlChar ::= [^\#x2D#x5B#x5D]
4933 * [22] XmlCharIncDash ::= [^\#x5B#x5D]
4934 */
4935static void
4936xmlFAParseCharRange(xmlRegParserCtxtPtr ctxt) {
4937 int cur, len;
4938 int start = -1;
4939 int end = -1;
4940
4941 if (CUR == '\0') {
4942 ERROR("Expecting ']'");
4943 return;
4944 }
4945
4946 if ((CUR == '&') && (NXT(1) == '#')) {
4947 end = start = xmlFAParseCharRef(ctxt);
4948 xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,
4949 XML_REGEXP_CHARVAL, start, end, NULL);
4950 return;
4951 }
4952 cur = CUR;
4953 if (cur == '\\') {
4954 NEXT;
4955 cur = CUR;
4956 switch (cur) {
4957 case 'n': start = 0xA; break;
4958 case 'r': start = 0xD; break;
4959 case 't': start = 0x9; break;
4960 case '\\': case '|': case '.': case '-': case '^': case '?':
4961 case '*': case '+': case '{': case '}': case '(': case ')':
4962 case '[': case ']':
4963 start = cur; break;
4964 default:
4965 ERROR("Invalid escape value");
4966 return;
4967 }
4968 end = start;
4969 len = 1;
4970 } else if ((cur != 0x5B) && (cur != 0x5D)) {
4971 end = start = CUR_SCHAR(ctxt->cur, len);
4972 } else {
4973 ERROR("Expecting a char range");
4974 return;
4975 }
4976 /*
4977 * Since we are "inside" a range, we can assume ctxt->cur is past
4978 * the start of ctxt->string, and PREV should be safe
4979 */
4980 if ((start == '-') && (NXT(1) != ']') && (PREV != '[') && (PREV != '^')) {
4981 NEXTL(len);
4982 return;
4983 }
4984 NEXTL(len);
4985 cur = CUR;
4986 if ((cur != '-') || (NXT(1) == ']')) {
4987 xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,
4988 XML_REGEXP_CHARVAL, start, end, NULL);
4989 return;
4990 }
4991 NEXT;
4992 cur = CUR;
4993 if (cur == '\\') {
4994 NEXT;
4995 cur = CUR;
4996 switch (cur) {
4997 case 'n': end = 0xA; break;
4998 case 'r': end = 0xD; break;
4999 case 't': end = 0x9; break;
5000 case '\\': case '|': case '.': case '-': case '^': case '?':
5001 case '*': case '+': case '{': case '}': case '(': case ')':
5002 case '[': case ']':
5003 end = cur; break;
5004 default:
5005 ERROR("Invalid escape value");
5006 return;
5007 }
5008 len = 1;
5009 } else if ((cur != 0x5B) && (cur != 0x5D)) {
5010 end = CUR_SCHAR(ctxt->cur, len);
5011 } else {
5012 ERROR("Expecting the end of a char range");
5013 return;
5014 }
5015 NEXTL(len);
5016 /* TODO check that the values are acceptable character ranges for XML */
5017 if (end < start) {
5018 ERROR("End of range is before start of range");
5019 } else {
5020 xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,
5021 XML_REGEXP_CHARVAL, start, end, NULL);
5022 }
5023 return;
5024}
5025
5026/**
5027 * xmlFAParsePosCharGroup:
5028 * @ctxt: a regexp parser context
5029 *
5030 * [14] posCharGroup ::= ( charRange | charClassEsc )+
5031 */
5032static void
5033xmlFAParsePosCharGroup(xmlRegParserCtxtPtr ctxt) {
5034 do {
5035 if ((CUR == '\\') || (CUR == '.')) {
5036 xmlFAParseCharClassEsc(ctxt);
5037 } else {
5038 xmlFAParseCharRange(ctxt);
5039 }
5040 } while ((CUR != ']') && (CUR != '^') && (CUR != '-') &&
5041 (CUR != 0) && (ctxt->error == 0));
5042}
5043
5044/**
5045 * xmlFAParseCharGroup:
5046 * @ctxt: a regexp parser context
5047 *
5048 * [13] charGroup ::= posCharGroup | negCharGroup | charClassSub
5049 * [15] negCharGroup ::= '^' posCharGroup
5050 * [16] charClassSub ::= ( posCharGroup | negCharGroup ) '-' charClassExpr
5051 * [12] charClassExpr ::= '[' charGroup ']'
5052 */
5053static void
5054xmlFAParseCharGroup(xmlRegParserCtxtPtr ctxt) {
5055 int n = ctxt->neg;
5056 while ((CUR != ']') && (ctxt->error == 0)) {
5057 if (CUR == '^') {
5058 int neg = ctxt->neg;
5059
5060 NEXT;
5061 ctxt->neg = !ctxt->neg;
5062 xmlFAParsePosCharGroup(ctxt);
5063 ctxt->neg = neg;
5064 } else if ((CUR == '-') && (NXT(1) == '[')) {
5065 int neg = ctxt->neg;
5066 ctxt->neg = 2;
5067 NEXT; /* eat the '-' */
5068 NEXT; /* eat the '[' */
5069 xmlFAParseCharGroup(ctxt);
5070 if (CUR == ']') {
5071 NEXT;
5072 } else {
5073 ERROR("charClassExpr: ']' expected");
5074 break;
5075 }
5076 ctxt->neg = neg;
5077 break;
5078 } else if (CUR != ']') {
5079 xmlFAParsePosCharGroup(ctxt);
5080 }
5081 }
5082 ctxt->neg = n;
5083}
5084
5085/**
5086 * xmlFAParseCharClass:
5087 * @ctxt: a regexp parser context
5088 *
5089 * [11] charClass ::= charClassEsc | charClassExpr
5090 * [12] charClassExpr ::= '[' charGroup ']'
5091 */
5092static void
5093xmlFAParseCharClass(xmlRegParserCtxtPtr ctxt) {
5094 if (CUR == '[') {
5095 NEXT;
5096 ctxt->atom = xmlRegNewAtom(ctxt, XML_REGEXP_RANGES);
5097 if (ctxt->atom == NULL)
5098 return;
5099 xmlFAParseCharGroup(ctxt);
5100 if (CUR == ']') {
5101 NEXT;
5102 } else {
5103 ERROR("xmlFAParseCharClass: ']' expected");
5104 }
5105 } else {
5106 xmlFAParseCharClassEsc(ctxt);
5107 }
5108}
5109
5110/**
5111 * xmlFAParseQuantExact:
5112 * @ctxt: a regexp parser context
5113 *
5114 * [8] QuantExact ::= [0-9]+
5115 *
5116 * Returns 0 if success or -1 in case of error
5117 */
5118static int
5119xmlFAParseQuantExact(xmlRegParserCtxtPtr ctxt) {
5120 int ret = 0;
5121 int ok = 0;
5122
5123 while ((CUR >= '0') && (CUR <= '9')) {
5124 ret = ret * 10 + (CUR - '0');
5125 ok = 1;
5126 NEXT;
5127 }
5128 if (ok != 1) {
5129 return(-1);
5130 }
5131 return(ret);
5132}
5133
5134/**
5135 * xmlFAParseQuantifier:
5136 * @ctxt: a regexp parser context
5137 *
5138 * [4] quantifier ::= [?*+] | ( '{' quantity '}' )
5139 * [5] quantity ::= quantRange | quantMin | QuantExact
5140 * [6] quantRange ::= QuantExact ',' QuantExact
5141 * [7] quantMin ::= QuantExact ','
5142 * [8] QuantExact ::= [0-9]+
5143 */
5144static int
5145xmlFAParseQuantifier(xmlRegParserCtxtPtr ctxt) {
5146 int cur;
5147
5148 cur = CUR;
5149 if ((cur == '?') || (cur == '*') || (cur == '+')) {
5150 if (ctxt->atom != NULL) {
5151 if (cur == '?')
5152 ctxt->atom->quant = XML_REGEXP_QUANT_OPT;
5153 else if (cur == '*')
5154 ctxt->atom->quant = XML_REGEXP_QUANT_MULT;
5155 else if (cur == '+')
5156 ctxt->atom->quant = XML_REGEXP_QUANT_PLUS;
5157 }
5158 NEXT;
5159 return(1);
5160 }
5161 if (cur == '{') {
5162 int min = 0, max = 0;
5163
5164 NEXT;
5165 cur = xmlFAParseQuantExact(ctxt);
5166 if (cur >= 0)
5167 min = cur;
5168 if (CUR == ',') {
5169 NEXT;
5170 if (CUR == '}')
5171 max = INT_MAX;
5172 else {
5173 cur = xmlFAParseQuantExact(ctxt);
5174 if (cur >= 0)
5175 max = cur;
5176 else {
5177 ERROR("Improper quantifier");
5178 }
5179 }
5180 }
5181 if (CUR == '}') {
5182 NEXT;
5183 } else {
5184 ERROR("Unterminated quantifier");
5185 }
5186 if (max == 0)
5187 max = min;
5188 if (ctxt->atom != NULL) {
5189 ctxt->atom->quant = XML_REGEXP_QUANT_RANGE;
5190 ctxt->atom->min = min;
5191 ctxt->atom->max = max;
5192 }
5193 return(1);
5194 }
5195 return(0);
5196}
5197
5198/**
5199 * xmlFAParseAtom:
5200 * @ctxt: a regexp parser context
5201 *
5202 * [9] atom ::= Char | charClass | ( '(' regExp ')' )
5203 */
5204static int
5205xmlFAParseAtom(xmlRegParserCtxtPtr ctxt) {
5206 int codepoint, len;
5207
5208 codepoint = xmlFAIsChar(ctxt);
5209 if (codepoint > 0) {
5210 ctxt->atom = xmlRegNewAtom(ctxt, XML_REGEXP_CHARVAL);
5211 if (ctxt->atom == NULL)
5212 return(-1);
5213 codepoint = CUR_SCHAR(ctxt->cur, len);
5214 ctxt->atom->codepoint = codepoint;
5215 NEXTL(len);
5216 return(1);
5217 } else if (CUR == '|') {
5218 return(0);
5219 } else if (CUR == 0) {
5220 return(0);
5221 } else if (CUR == ')') {
5222 return(0);
5223 } else if (CUR == '(') {
5224 xmlRegStatePtr start, oldend, start0;
5225
5226 NEXT;
5227 /*
5228 * this extra Epsilon transition is needed if we count with 0 allowed
5229 * unfortunately this can't be known at that point
5230 */
5231 xmlFAGenerateEpsilonTransition(ctxt, ctxt->state, NULL);
5232 start0 = ctxt->state;
5233 xmlFAGenerateEpsilonTransition(ctxt, ctxt->state, NULL);
5234 start = ctxt->state;
5235 oldend = ctxt->end;
5236 ctxt->end = NULL;
5237 ctxt->atom = NULL;
5238 xmlFAParseRegExp(ctxt, 0);
5239 if (CUR == ')') {
5240 NEXT;
5241 } else {
5242 ERROR("xmlFAParseAtom: expecting ')'");
5243 }
5244 ctxt->atom = xmlRegNewAtom(ctxt, XML_REGEXP_SUBREG);
5245 if (ctxt->atom == NULL)
5246 return(-1);
5247 ctxt->atom->start = start;
5248 ctxt->atom->start0 = start0;
5249 ctxt->atom->stop = ctxt->state;
5250 ctxt->end = oldend;
5251 return(1);
5252 } else if ((CUR == '[') || (CUR == '\\') || (CUR == '.')) {
5253 xmlFAParseCharClass(ctxt);
5254 return(1);
5255 }
5256 return(0);
5257}
5258
5259/**
5260 * xmlFAParsePiece:
5261 * @ctxt: a regexp parser context
5262 *
5263 * [3] piece ::= atom quantifier?
5264 */
5265static int
5266xmlFAParsePiece(xmlRegParserCtxtPtr ctxt) {
5267 int ret;
5268
5269 ctxt->atom = NULL;
5270 ret = xmlFAParseAtom(ctxt);
5271 if (ret == 0)
5272 return(0);
5273 if (ctxt->atom == NULL) {
5274 ERROR("internal: no atom generated");
5275 }
5276 xmlFAParseQuantifier(ctxt);
5277 return(1);
5278}
5279
5280/**
5281 * xmlFAParseBranch:
5282 * @ctxt: a regexp parser context
5283 * @to: optional target to the end of the branch
5284 *
5285 * @to is used to optimize by removing duplicate path in automata
5286 * in expressions like (a|b)(c|d)
5287 *
5288 * [2] branch ::= piece*
5289 */
5290static int
5291xmlFAParseBranch(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr to) {
5292 xmlRegStatePtr previous;
5293 int ret;
5294
5295 previous = ctxt->state;
5296 ret = xmlFAParsePiece(ctxt);
5297 if (ret != 0) {
5298 if (xmlFAGenerateTransitions(ctxt, previous,
5299 (CUR=='|' || CUR==')') ? to : NULL, ctxt->atom) < 0)
5300 return(-1);
5301 previous = ctxt->state;
5302 ctxt->atom = NULL;
5303 }
5304 while ((ret != 0) && (ctxt->error == 0)) {
5305 ret = xmlFAParsePiece(ctxt);
5306 if (ret != 0) {
5307 if (xmlFAGenerateTransitions(ctxt, previous,
5308 (CUR=='|' || CUR==')') ? to : NULL, ctxt->atom) < 0)
5309 return(-1);
5310 previous = ctxt->state;
5311 ctxt->atom = NULL;
5312 }
5313 }
5314 return(0);
5315}
5316
5317/**
5318 * xmlFAParseRegExp:
5319 * @ctxt: a regexp parser context
5320 * @top: is this the top-level expression ?
5321 *
5322 * [1] regExp ::= branch ( '|' branch )*
5323 */
5324static void
5325xmlFAParseRegExp(xmlRegParserCtxtPtr ctxt, int top) {
5326 xmlRegStatePtr start, end;
5327
5328 /* if not top start should have been generated by an epsilon trans */
5329 start = ctxt->state;
5330 ctxt->end = NULL;
5331 xmlFAParseBranch(ctxt, NULL);
5332 if (top) {
5333#ifdef DEBUG_REGEXP_GRAPH
5334 printf("State %d is final\n", ctxt->state->no);
5335#endif
5336 ctxt->state->type = XML_REGEXP_FINAL_STATE;
5337 }
5338 if (CUR != '|') {
5339 ctxt->end = ctxt->state;
5340 return;
5341 }
5342 end = ctxt->state;
5343 while ((CUR == '|') && (ctxt->error == 0)) {
5344 NEXT;
5345 ctxt->state = start;
5346 ctxt->end = NULL;
5347 xmlFAParseBranch(ctxt, end);
5348 }
5349 if (!top) {
5350 ctxt->state = end;
5351 ctxt->end = end;
5352 }
5353}
5354
5355/************************************************************************
5356 * *
5357 * The basic API *
5358 * *
5359 ************************************************************************/
5360
5361/**
5362 * xmlRegexpPrint:
5363 * @output: the file for the output debug
5364 * @regexp: the compiled regexp
5365 *
5366 * Print the content of the compiled regular expression
5367 */
5368void
5369xmlRegexpPrint(FILE *output, xmlRegexpPtr regexp) {
5370 int i;
5371
5372 if (output == NULL)
5373 return;
5374 fprintf(output, " regexp: ");
5375 if (regexp == NULL) {
5376 fprintf(output, "NULL\n");
5377 return;
5378 }
5379 fprintf(output, "'%s' ", regexp->string);
5380 fprintf(output, "\n");
5381 fprintf(output, "%d atoms:\n", regexp->nbAtoms);
5382 for (i = 0;i < regexp->nbAtoms; i++) {
5383 fprintf(output, " %02d ", i);
5384 xmlRegPrintAtom(output, regexp->atoms[i]);
5385 }
5386 fprintf(output, "%d states:", regexp->nbStates);
5387 fprintf(output, "\n");
5388 for (i = 0;i < regexp->nbStates; i++) {
5389 xmlRegPrintState(output, regexp->states[i]);
5390 }
5391 fprintf(output, "%d counters:\n", regexp->nbCounters);
5392 for (i = 0;i < regexp->nbCounters; i++) {
5393 fprintf(output, " %d: min %d max %d\n", i, regexp->counters[i].min,
5394 regexp->counters[i].max);
5395 }
5396}
5397
5398/**
5399 * xmlRegexpCompile:
5400 * @regexp: a regular expression string
5401 *
5402 * Parses a regular expression conforming to XML Schemas Part 2 Datatype
5403 * Appendix F and builds an automata suitable for testing strings against
5404 * that regular expression
5405 *
5406 * Returns the compiled expression or NULL in case of error
5407 */
5408xmlRegexpPtr
5409xmlRegexpCompile(const xmlChar *regexp) {
5410 xmlRegexpPtr ret;
5411 xmlRegParserCtxtPtr ctxt;
5412
5413 ctxt = xmlRegNewParserCtxt(regexp);
5414 if (ctxt == NULL)
5415 return(NULL);
5416
5417 /* initialize the parser */
5418 ctxt->end = NULL;
5419 ctxt->start = ctxt->state = xmlRegNewState(ctxt);
5420 xmlRegStatePush(ctxt, ctxt->start);
5421
5422 /* parse the expression building an automata */
5423 xmlFAParseRegExp(ctxt, 1);
5424 if (CUR != 0) {
5425 ERROR("xmlFAParseRegExp: extra characters");
5426 }
5427 if (ctxt->error != 0) {
5428 xmlRegFreeParserCtxt(ctxt);
5429 return(NULL);
5430 }
5431 ctxt->end = ctxt->state;
5432 ctxt->start->type = XML_REGEXP_START_STATE;
5433 ctxt->end->type = XML_REGEXP_FINAL_STATE;
5434
5435 /* remove the Epsilon except for counted transitions */
5436 xmlFAEliminateEpsilonTransitions(ctxt);
5437
5438
5439 if (ctxt->error != 0) {
5440 xmlRegFreeParserCtxt(ctxt);
5441 return(NULL);
5442 }
5443 ret = xmlRegEpxFromParse(ctxt);
5444 xmlRegFreeParserCtxt(ctxt);
5445 return(ret);
5446}
5447
5448/**
5449 * xmlRegexpExec:
5450 * @comp: the compiled regular expression
5451 * @content: the value to check against the regular expression
5452 *
5453 * Check if the regular expression generates the value
5454 *
5455 * Returns 1 if it matches, 0 if not and a negative value in case of error
5456 */
5457int
5458xmlRegexpExec(xmlRegexpPtr comp, const xmlChar *content) {
5459 if ((comp == NULL) || (content == NULL))
5460 return(-1);
5461 return(xmlFARegExec(comp, content));
5462}
5463
5464/**
5465 * xmlRegexpIsDeterminist:
5466 * @comp: the compiled regular expression
5467 *
5468 * Check if the regular expression is determinist
5469 *
5470 * Returns 1 if it yes, 0 if not and a negative value in case of error
5471 */
5472int
5473xmlRegexpIsDeterminist(xmlRegexpPtr comp) {
5474 xmlAutomataPtr am;
5475 int ret;
5476
5477 if (comp == NULL)
5478 return(-1);
5479 if (comp->determinist != -1)
5480 return(comp->determinist);
5481
5482 am = xmlNewAutomata();
5483 if (am->states != NULL) {
5484 int i;
5485
5486 for (i = 0;i < am->nbStates;i++)
5487 xmlRegFreeState(am->states[i]);
5488 xmlFree(am->states);
5489 }
5490 am->nbAtoms = comp->nbAtoms;
5491 am->atoms = comp->atoms;
5492 am->nbStates = comp->nbStates;
5493 am->states = comp->states;
5494 am->determinist = -1;
5495 ret = xmlFAComputesDeterminism(am);
5496 am->atoms = NULL;
5497 am->states = NULL;
5498 xmlFreeAutomata(am);
5499 return(ret);
5500}
5501
5502/**
5503 * xmlRegFreeRegexp:
5504 * @regexp: the regexp
5505 *
5506 * Free a regexp
5507 */
5508void
5509xmlRegFreeRegexp(xmlRegexpPtr regexp) {
5510 int i;
5511 if (regexp == NULL)
5512 return;
5513
5514 if (regexp->string != NULL)
5515 xmlFree(regexp->string);
5516 if (regexp->states != NULL) {
5517 for (i = 0;i < regexp->nbStates;i++)
5518 xmlRegFreeState(regexp->states[i]);
5519 xmlFree(regexp->states);
5520 }
5521 if (regexp->atoms != NULL) {
5522 for (i = 0;i < regexp->nbAtoms;i++)
5523 xmlRegFreeAtom(regexp->atoms[i]);
5524 xmlFree(regexp->atoms);
5525 }
5526 if (regexp->counters != NULL)
5527 xmlFree(regexp->counters);
5528 if (regexp->compact != NULL)
5529 xmlFree(regexp->compact);
5530 if (regexp->transdata != NULL)
5531 xmlFree(regexp->transdata);
5532 if (regexp->stringMap != NULL) {
5533 for (i = 0; i < regexp->nbstrings;i++)
5534 xmlFree(regexp->stringMap[i]);
5535 xmlFree(regexp->stringMap);
5536 }
5537
5538 xmlFree(regexp);
5539}
5540
5541#ifdef LIBXML_AUTOMATA_ENABLED
5542/************************************************************************
5543 * *
5544 * The Automata interface *
5545 * *
5546 ************************************************************************/
5547
5548/**
5549 * xmlNewAutomata:
5550 *
5551 * Create a new automata
5552 *
5553 * Returns the new object or NULL in case of failure
5554 */
5555xmlAutomataPtr
5556xmlNewAutomata(void) {
5557 xmlAutomataPtr ctxt;
5558
5559 ctxt = xmlRegNewParserCtxt(NULL);
5560 if (ctxt == NULL)
5561 return(NULL);
5562
5563 /* initialize the parser */
5564 ctxt->end = NULL;
5565 ctxt->start = ctxt->state = xmlRegNewState(ctxt);
5566 if (ctxt->start == NULL) {
5567 xmlFreeAutomata(ctxt);
5568 return(NULL);
5569 }
5570 ctxt->start->type = XML_REGEXP_START_STATE;
5571 if (xmlRegStatePush(ctxt, ctxt->start) < 0) {
5572 xmlRegFreeState(ctxt->start);
5573 xmlFreeAutomata(ctxt);
5574 return(NULL);
5575 }
5576
5577 return(ctxt);
5578}
5579
5580/**
5581 * xmlFreeAutomata:
5582 * @am: an automata
5583 *
5584 * Free an automata
5585 */
5586void
5587xmlFreeAutomata(xmlAutomataPtr am) {
5588 if (am == NULL)
5589 return;
5590 xmlRegFreeParserCtxt(am);
5591}
5592
5593/**
5594 * xmlAutomataGetInitState:
5595 * @am: an automata
5596 *
5597 * Initial state lookup
5598 *
5599 * Returns the initial state of the automata
5600 */
5601xmlAutomataStatePtr
5602xmlAutomataGetInitState(xmlAutomataPtr am) {
5603 if (am == NULL)
5604 return(NULL);
5605 return(am->start);
5606}
5607
5608/**
5609 * xmlAutomataSetFinalState:
5610 * @am: an automata
5611 * @state: a state in this automata
5612 *
5613 * Makes that state a final state
5614 *
5615 * Returns 0 or -1 in case of error
5616 */
5617int
5618xmlAutomataSetFinalState(xmlAutomataPtr am, xmlAutomataStatePtr state) {
5619 if ((am == NULL) || (state == NULL))
5620 return(-1);
5621 state->type = XML_REGEXP_FINAL_STATE;
5622 return(0);
5623}
5624
5625/**
5626 * xmlAutomataNewTransition:
5627 * @am: an automata
5628 * @from: the starting point of the transition
5629 * @to: the target point of the transition or NULL
5630 * @token: the input string associated to that transition
5631 * @data: data passed to the callback function if the transition is activated
5632 *
5633 * If @to is NULL, this creates first a new target state in the automata
5634 * and then adds a transition from the @from state to the target state
5635 * activated by the value of @token
5636 *
5637 * Returns the target state or NULL in case of error
5638 */
5639xmlAutomataStatePtr
5640xmlAutomataNewTransition(xmlAutomataPtr am, xmlAutomataStatePtr from,
5641 xmlAutomataStatePtr to, const xmlChar *token,
5642 void *data) {
5643 xmlRegAtomPtr atom;
5644
5645 if ((am == NULL) || (from == NULL) || (token == NULL))
5646 return(NULL);
5647 atom = xmlRegNewAtom(am, XML_REGEXP_STRING);
5648 if (atom == NULL)
5649 return(NULL);
5650 atom->data = data;
5651 if (atom == NULL)
5652 return(NULL);
5653 atom->valuep = xmlStrdup(token);
5654
5655 if (xmlFAGenerateTransitions(am, from, to, atom) < 0) {
5656 xmlRegFreeAtom(atom);
5657 return(NULL);
5658 }
5659 if (to == NULL)
5660 return(am->state);
5661 return(to);
5662}
5663
5664/**
5665 * xmlAutomataNewTransition2:
5666 * @am: an automata
5667 * @from: the starting point of the transition
5668 * @to: the target point of the transition or NULL
5669 * @token: the first input string associated to that transition
5670 * @token2: the second input string associated to that transition
5671 * @data: data passed to the callback function if the transition is activated
5672 *
5673 * If @to is NULL, this creates first a new target state in the automata
5674 * and then adds a transition from the @from state to the target state
5675 * activated by the value of @token
5676 *
5677 * Returns the target state or NULL in case of error
5678 */
5679xmlAutomataStatePtr
5680xmlAutomataNewTransition2(xmlAutomataPtr am, xmlAutomataStatePtr from,
5681 xmlAutomataStatePtr to, const xmlChar *token,
5682 const xmlChar *token2, void *data) {
5683 xmlRegAtomPtr atom;
5684
5685 if ((am == NULL) || (from == NULL) || (token == NULL))
5686 return(NULL);
5687 atom = xmlRegNewAtom(am, XML_REGEXP_STRING);
5688 if (atom == NULL)
5689 return(NULL);
5690 atom->data = data;
5691 if ((token2 == NULL) || (*token2 == 0)) {
5692 atom->valuep = xmlStrdup(token);
5693 } else {
5694 int lenn, lenp;
5695 xmlChar *str;
5696
5697 lenn = strlen((char *) token2);
5698 lenp = strlen((char *) token);
5699
5700 str = (xmlChar *) xmlMallocAtomic(lenn + lenp + 2);
5701 if (str == NULL) {
5702 xmlRegFreeAtom(atom);
5703 return(NULL);
5704 }
5705 memcpy(&str[0], token, lenp);
5706 str[lenp] = '|';
5707 memcpy(&str[lenp + 1], token2, lenn);
5708 str[lenn + lenp + 1] = 0;
5709
5710 atom->valuep = str;
5711 }
5712
5713 if (xmlFAGenerateTransitions(am, from, to, atom) < 0) {
5714 xmlRegFreeAtom(atom);
5715 return(NULL);
5716 }
5717 if (to == NULL)
5718 return(am->state);
5719 return(to);
5720}
5721
5722/**
5723 * xmlAutomataNewNegTrans:
5724 * @am: an automata
5725 * @from: the starting point of the transition
5726 * @to: the target point of the transition or NULL
5727 * @token: the first input string associated to that transition
5728 * @token2: the second input string associated to that transition
5729 * @data: data passed to the callback function if the transition is activated
5730 *
5731 * If @to is NULL, this creates first a new target state in the automata
5732 * and then adds a transition from the @from state to the target state
5733 * activated by any value except (@token,@token2)
5734 * Note that if @token2 is not NULL, then (X, NULL) won't match to follow
5735 # the semantic of XSD ##other
5736 *
5737 * Returns the target state or NULL in case of error
5738 */
5739xmlAutomataStatePtr
5740xmlAutomataNewNegTrans(xmlAutomataPtr am, xmlAutomataStatePtr from,
5741 xmlAutomataStatePtr to, const xmlChar *token,
5742 const xmlChar *token2, void *data) {
5743 xmlRegAtomPtr atom;
5744 xmlChar err_msg[200];
5745
5746 if ((am == NULL) || (from == NULL) || (token == NULL))
5747 return(NULL);
5748 atom = xmlRegNewAtom(am, XML_REGEXP_STRING);
5749 if (atom == NULL)
5750 return(NULL);
5751 atom->data = data;
5752 atom->neg = 1;
5753 if ((token2 == NULL) || (*token2 == 0)) {
5754 atom->valuep = xmlStrdup(token);
5755 } else {
5756 int lenn, lenp;
5757 xmlChar *str;
5758
5759 lenn = strlen((char *) token2);
5760 lenp = strlen((char *) token);
5761
5762 str = (xmlChar *) xmlMallocAtomic(lenn + lenp + 2);
5763 if (str == NULL) {
5764 xmlRegFreeAtom(atom);
5765 return(NULL);
5766 }
5767 memcpy(&str[0], token, lenp);
5768 str[lenp] = '|';
5769 memcpy(&str[lenp + 1], token2, lenn);
5770 str[lenn + lenp + 1] = 0;
5771
5772 atom->valuep = str;
5773 }
5774 snprintf((char *) err_msg, 199, "not %s", (const char *) atom->valuep);
5775 err_msg[199] = 0;
5776 atom->valuep2 = xmlStrdup(err_msg);
5777
5778 if (xmlFAGenerateTransitions(am, from, to, atom) < 0) {
5779 xmlRegFreeAtom(atom);
5780 return(NULL);
5781 }
5782 am->negs++;
5783 if (to == NULL)
5784 return(am->state);
5785 return(to);
5786}
5787
5788/**
5789 * xmlAutomataNewCountTrans2:
5790 * @am: an automata
5791 * @from: the starting point of the transition
5792 * @to: the target point of the transition or NULL
5793 * @token: the input string associated to that transition
5794 * @token2: the second input string associated to that transition
5795 * @min: the minimum successive occurences of token
5796 * @max: the maximum successive occurences of token
5797 * @data: data associated to the transition
5798 *
5799 * If @to is NULL, this creates first a new target state in the automata
5800 * and then adds a transition from the @from state to the target state
5801 * activated by a succession of input of value @token and @token2 and
5802 * whose number is between @min and @max
5803 *
5804 * Returns the target state or NULL in case of error
5805 */
5806xmlAutomataStatePtr
5807xmlAutomataNewCountTrans2(xmlAutomataPtr am, xmlAutomataStatePtr from,
5808 xmlAutomataStatePtr to, const xmlChar *token,
5809 const xmlChar *token2,
5810 int min, int max, void *data) {
5811 xmlRegAtomPtr atom;
5812 int counter;
5813
5814 if ((am == NULL) || (from == NULL) || (token == NULL))
5815 return(NULL);
5816 if (min < 0)
5817 return(NULL);
5818 if ((max < min) || (max < 1))
5819 return(NULL);
5820 atom = xmlRegNewAtom(am, XML_REGEXP_STRING);
5821 if (atom == NULL)
5822 return(NULL);
5823 if ((token2 == NULL) || (*token2 == 0)) {
5824 atom->valuep = xmlStrdup(token);
5825 } else {
5826 int lenn, lenp;
5827 xmlChar *str;
5828
5829 lenn = strlen((char *) token2);
5830 lenp = strlen((char *) token);
5831
5832 str = (xmlChar *) xmlMallocAtomic(lenn + lenp + 2);
5833 if (str == NULL) {
5834 xmlRegFreeAtom(atom);
5835 return(NULL);
5836 }
5837 memcpy(&str[0], token, lenp);
5838 str[lenp] = '|';
5839 memcpy(&str[lenp + 1], token2, lenn);
5840 str[lenn + lenp + 1] = 0;
5841
5842 atom->valuep = str;
5843 }
5844 atom->data = data;
5845 if (min == 0)
5846 atom->min = 1;
5847 else
5848 atom->min = min;
5849 atom->max = max;
5850
5851 /*
5852 * associate a counter to the transition.
5853 */
5854 counter = xmlRegGetCounter(am);
5855 am->counters[counter].min = min;
5856 am->counters[counter].max = max;
5857
5858 /* xmlFAGenerateTransitions(am, from, to, atom); */
5859 if (to == NULL) {
5860 to = xmlRegNewState(am);
5861 xmlRegStatePush(am, to);
5862 }
5863 xmlRegStateAddTrans(am, from, atom, to, counter, -1);
5864 xmlRegAtomPush(am, atom);
5865 am->state = to;
5866
5867 if (to == NULL)
5868 to = am->state;
5869 if (to == NULL)
5870 return(NULL);
5871 if (min == 0)
5872 xmlFAGenerateEpsilonTransition(am, from, to);
5873 return(to);
5874}
5875
5876/**
5877 * xmlAutomataNewCountTrans:
5878 * @am: an automata
5879 * @from: the starting point of the transition
5880 * @to: the target point of the transition or NULL
5881 * @token: the input string associated to that transition
5882 * @min: the minimum successive occurences of token
5883 * @max: the maximum successive occurences of token
5884 * @data: data associated to the transition
5885 *
5886 * If @to is NULL, this creates first a new target state in the automata
5887 * and then adds a transition from the @from state to the target state
5888 * activated by a succession of input of value @token and whose number
5889 * is between @min and @max
5890 *
5891 * Returns the target state or NULL in case of error
5892 */
5893xmlAutomataStatePtr
5894xmlAutomataNewCountTrans(xmlAutomataPtr am, xmlAutomataStatePtr from,
5895 xmlAutomataStatePtr to, const xmlChar *token,
5896 int min, int max, void *data) {
5897 xmlRegAtomPtr atom;
5898 int counter;
5899
5900 if ((am == NULL) || (from == NULL) || (token == NULL))
5901 return(NULL);
5902 if (min < 0)
5903 return(NULL);
5904 if ((max < min) || (max < 1))
5905 return(NULL);
5906 atom = xmlRegNewAtom(am, XML_REGEXP_STRING);
5907 if (atom == NULL)
5908 return(NULL);
5909 atom->valuep = xmlStrdup(token);
5910 atom->data = data;
5911 if (min == 0)
5912 atom->min = 1;
5913 else
5914 atom->min = min;
5915 atom->max = max;
5916
5917 /*
5918 * associate a counter to the transition.
5919 */
5920 counter = xmlRegGetCounter(am);
5921 am->counters[counter].min = min;
5922 am->counters[counter].max = max;
5923
5924 /* xmlFAGenerateTransitions(am, from, to, atom); */
5925 if (to == NULL) {
5926 to = xmlRegNewState(am);
5927 xmlRegStatePush(am, to);
5928 }
5929 xmlRegStateAddTrans(am, from, atom, to, counter, -1);
5930 xmlRegAtomPush(am, atom);
5931 am->state = to;
5932
5933 if (to == NULL)
5934 to = am->state;
5935 if (to == NULL)
5936 return(NULL);
5937 if (min == 0)
5938 xmlFAGenerateEpsilonTransition(am, from, to);
5939 return(to);
5940}
5941
5942/**
5943 * xmlAutomataNewOnceTrans2:
5944 * @am: an automata
5945 * @from: the starting point of the transition
5946 * @to: the target point of the transition or NULL
5947 * @token: the input string associated to that transition
5948 * @token2: the second input string associated to that transition
5949 * @min: the minimum successive occurences of token
5950 * @max: the maximum successive occurences of token
5951 * @data: data associated to the transition
5952 *
5953 * If @to is NULL, this creates first a new target state in the automata
5954 * and then adds a transition from the @from state to the target state
5955 * activated by a succession of input of value @token and @token2 and whose
5956 * number is between @min and @max, moreover that transition can only be
5957 * crossed once.
5958 *
5959 * Returns the target state or NULL in case of error
5960 */
5961xmlAutomataStatePtr
5962xmlAutomataNewOnceTrans2(xmlAutomataPtr am, xmlAutomataStatePtr from,
5963 xmlAutomataStatePtr to, const xmlChar *token,
5964 const xmlChar *token2,
5965 int min, int max, void *data) {
5966 xmlRegAtomPtr atom;
5967 int counter;
5968
5969 if ((am == NULL) || (from == NULL) || (token == NULL))
5970 return(NULL);
5971 if (min < 1)
5972 return(NULL);
5973 if ((max < min) || (max < 1))
5974 return(NULL);
5975 atom = xmlRegNewAtom(am, XML_REGEXP_STRING);
5976 if (atom == NULL)
5977 return(NULL);
5978 if ((token2 == NULL) || (*token2 == 0)) {
5979 atom->valuep = xmlStrdup(token);
5980 } else {
5981 int lenn, lenp;
5982 xmlChar *str;
5983
5984 lenn = strlen((char *) token2);
5985 lenp = strlen((char *) token);
5986
5987 str = (xmlChar *) xmlMallocAtomic(lenn + lenp + 2);
5988 if (str == NULL) {
5989 xmlRegFreeAtom(atom);
5990 return(NULL);
5991 }
5992 memcpy(&str[0], token, lenp);
5993 str[lenp] = '|';
5994 memcpy(&str[lenp + 1], token2, lenn);
5995 str[lenn + lenp + 1] = 0;
5996
5997 atom->valuep = str;
5998 }
5999 atom->data = data;
6000 atom->quant = XML_REGEXP_QUANT_ONCEONLY;
6001 atom->min = min;
6002 atom->max = max;
6003 /*
6004 * associate a counter to the transition.
6005 */
6006 counter = xmlRegGetCounter(am);
6007 am->counters[counter].min = 1;
6008 am->counters[counter].max = 1;
6009
6010 /* xmlFAGenerateTransitions(am, from, to, atom); */
6011 if (to == NULL) {
6012 to = xmlRegNewState(am);
6013 xmlRegStatePush(am, to);
6014 }
6015 xmlRegStateAddTrans(am, from, atom, to, counter, -1);
6016 xmlRegAtomPush(am, atom);
6017 am->state = to;
6018 return(to);
6019}
6020
6021
6022
6023/**
6024 * xmlAutomataNewOnceTrans:
6025 * @am: an automata
6026 * @from: the starting point of the transition
6027 * @to: the target point of the transition or NULL
6028 * @token: the input string associated to that transition
6029 * @min: the minimum successive occurences of token
6030 * @max: the maximum successive occurences of token
6031 * @data: data associated to the transition
6032 *
6033 * If @to is NULL, this creates first a new target state in the automata
6034 * and then adds a transition from the @from state to the target state
6035 * activated by a succession of input of value @token and whose number
6036 * is between @min and @max, moreover that transition can only be crossed
6037 * once.
6038 *
6039 * Returns the target state or NULL in case of error
6040 */
6041xmlAutomataStatePtr
6042xmlAutomataNewOnceTrans(xmlAutomataPtr am, xmlAutomataStatePtr from,
6043 xmlAutomataStatePtr to, const xmlChar *token,
6044 int min, int max, void *data) {
6045 xmlRegAtomPtr atom;
6046 int counter;
6047
6048 if ((am == NULL) || (from == NULL) || (token == NULL))
6049 return(NULL);
6050 if (min < 1)
6051 return(NULL);
6052 if ((max < min) || (max < 1))
6053 return(NULL);
6054 atom = xmlRegNewAtom(am, XML_REGEXP_STRING);
6055 if (atom == NULL)
6056 return(NULL);
6057 atom->valuep = xmlStrdup(token);
6058 atom->data = data;
6059 atom->quant = XML_REGEXP_QUANT_ONCEONLY;
6060 atom->min = min;
6061 atom->max = max;
6062 /*
6063 * associate a counter to the transition.
6064 */
6065 counter = xmlRegGetCounter(am);
6066 am->counters[counter].min = 1;
6067 am->counters[counter].max = 1;
6068
6069 /* xmlFAGenerateTransitions(am, from, to, atom); */
6070 if (to == NULL) {
6071 to = xmlRegNewState(am);
6072 xmlRegStatePush(am, to);
6073 }
6074 xmlRegStateAddTrans(am, from, atom, to, counter, -1);
6075 xmlRegAtomPush(am, atom);
6076 am->state = to;
6077 return(to);
6078}
6079
6080/**
6081 * xmlAutomataNewState:
6082 * @am: an automata
6083 *
6084 * Create a new disconnected state in the automata
6085 *
6086 * Returns the new state or NULL in case of error
6087 */
6088xmlAutomataStatePtr
6089xmlAutomataNewState(xmlAutomataPtr am) {
6090 xmlAutomataStatePtr to;
6091
6092 if (am == NULL)
6093 return(NULL);
6094 to = xmlRegNewState(am);
6095 xmlRegStatePush(am, to);
6096 return(to);
6097}
6098
6099/**
6100 * xmlAutomataNewEpsilon:
6101 * @am: an automata
6102 * @from: the starting point of the transition
6103 * @to: the target point of the transition or NULL
6104 *
6105 * If @to is NULL, this creates first a new target state in the automata
6106 * and then adds an epsilon transition from the @from state to the
6107 * target state
6108 *
6109 * Returns the target state or NULL in case of error
6110 */
6111xmlAutomataStatePtr
6112xmlAutomataNewEpsilon(xmlAutomataPtr am, xmlAutomataStatePtr from,
6113 xmlAutomataStatePtr to) {
6114 if ((am == NULL) || (from == NULL))
6115 return(NULL);
6116 xmlFAGenerateEpsilonTransition(am, from, to);
6117 if (to == NULL)
6118 return(am->state);
6119 return(to);
6120}
6121
6122/**
6123 * xmlAutomataNewAllTrans:
6124 * @am: an automata
6125 * @from: the starting point of the transition
6126 * @to: the target point of the transition or NULL
6127 * @lax: allow to transition if not all all transitions have been activated
6128 *
6129 * If @to is NULL, this creates first a new target state in the automata
6130 * and then adds a an ALL transition from the @from state to the
6131 * target state. That transition is an epsilon transition allowed only when
6132 * all transitions from the @from node have been activated.
6133 *
6134 * Returns the target state or NULL in case of error
6135 */
6136xmlAutomataStatePtr
6137xmlAutomataNewAllTrans(xmlAutomataPtr am, xmlAutomataStatePtr from,
6138 xmlAutomataStatePtr to, int lax) {
6139 if ((am == NULL) || (from == NULL))
6140 return(NULL);
6141 xmlFAGenerateAllTransition(am, from, to, lax);
6142 if (to == NULL)
6143 return(am->state);
6144 return(to);
6145}
6146
6147/**
6148 * xmlAutomataNewCounter:
6149 * @am: an automata
6150 * @min: the minimal value on the counter
6151 * @max: the maximal value on the counter
6152 *
6153 * Create a new counter
6154 *
6155 * Returns the counter number or -1 in case of error
6156 */
6157int
6158xmlAutomataNewCounter(xmlAutomataPtr am, int min, int max) {
6159 int ret;
6160
6161 if (am == NULL)
6162 return(-1);
6163
6164 ret = xmlRegGetCounter(am);
6165 if (ret < 0)
6166 return(-1);
6167 am->counters[ret].min = min;
6168 am->counters[ret].max = max;
6169 return(ret);
6170}
6171
6172/**
6173 * xmlAutomataNewCountedTrans:
6174 * @am: an automata
6175 * @from: the starting point of the transition
6176 * @to: the target point of the transition or NULL
6177 * @counter: the counter associated to that transition
6178 *
6179 * If @to is NULL, this creates first a new target state in the automata
6180 * and then adds an epsilon transition from the @from state to the target state
6181 * which will increment the counter provided
6182 *
6183 * Returns the target state or NULL in case of error
6184 */
6185xmlAutomataStatePtr
6186xmlAutomataNewCountedTrans(xmlAutomataPtr am, xmlAutomataStatePtr from,
6187 xmlAutomataStatePtr to, int counter) {
6188 if ((am == NULL) || (from == NULL) || (counter < 0))
6189 return(NULL);
6190 xmlFAGenerateCountedEpsilonTransition(am, from, to, counter);
6191 if (to == NULL)
6192 return(am->state);
6193 return(to);
6194}
6195
6196/**
6197 * xmlAutomataNewCounterTrans:
6198 * @am: an automata
6199 * @from: the starting point of the transition
6200 * @to: the target point of the transition or NULL
6201 * @counter: the counter associated to that transition
6202 *
6203 * If @to is NULL, this creates first a new target state in the automata
6204 * and then adds an epsilon transition from the @from state to the target state
6205 * which will be allowed only if the counter is within the right range.
6206 *
6207 * Returns the target state or NULL in case of error
6208 */
6209xmlAutomataStatePtr
6210xmlAutomataNewCounterTrans(xmlAutomataPtr am, xmlAutomataStatePtr from,
6211 xmlAutomataStatePtr to, int counter) {
6212 if ((am == NULL) || (from == NULL) || (counter < 0))
6213 return(NULL);
6214 xmlFAGenerateCountedTransition(am, from, to, counter);
6215 if (to == NULL)
6216 return(am->state);
6217 return(to);
6218}
6219
6220/**
6221 * xmlAutomataCompile:
6222 * @am: an automata
6223 *
6224 * Compile the automata into a Reg Exp ready for being executed.
6225 * The automata should be free after this point.
6226 *
6227 * Returns the compiled regexp or NULL in case of error
6228 */
6229xmlRegexpPtr
6230xmlAutomataCompile(xmlAutomataPtr am) {
6231 xmlRegexpPtr ret;
6232
6233 if ((am == NULL) || (am->error != 0)) return(NULL);
6234 xmlFAEliminateEpsilonTransitions(am);
6235 /* xmlFAComputesDeterminism(am); */
6236 ret = xmlRegEpxFromParse(am);
6237
6238 return(ret);
6239}
6240
6241/**
6242 * xmlAutomataIsDeterminist:
6243 * @am: an automata
6244 *
6245 * Checks if an automata is determinist.
6246 *
6247 * Returns 1 if true, 0 if not, and -1 in case of error
6248 */
6249int
6250xmlAutomataIsDeterminist(xmlAutomataPtr am) {
6251 int ret;
6252
6253 if (am == NULL)
6254 return(-1);
6255
6256 ret = xmlFAComputesDeterminism(am);
6257 return(ret);
6258}
6259#endif /* LIBXML_AUTOMATA_ENABLED */
6260
6261#ifdef LIBXML_EXPR_ENABLED
6262/************************************************************************
6263 * *
6264 * Formal Expression handling code *
6265 * *
6266 ************************************************************************/
6267/************************************************************************
6268 * *
6269 * Expression handling context *
6270 * *
6271 ************************************************************************/
6272
6273struct _xmlExpCtxt {
6274 xmlDictPtr dict;
6275 xmlExpNodePtr *table;
6276 int size;
6277 int nbElems;
6278 int nb_nodes;
6279 const char *expr;
6280 const char *cur;
6281 int nb_cons;
6282 int tabSize;
6283};
6284
6285/**
6286 * xmlExpNewCtxt:
6287 * @maxNodes: the maximum number of nodes
6288 * @dict: optional dictionnary to use internally
6289 *
6290 * Creates a new context for manipulating expressions
6291 *
6292 * Returns the context or NULL in case of error
6293 */
6294xmlExpCtxtPtr
6295xmlExpNewCtxt(int maxNodes, xmlDictPtr dict) {
6296 xmlExpCtxtPtr ret;
6297 int size = 256;
6298
6299 if (maxNodes <= 4096)
6300 maxNodes = 4096;
6301
6302 ret = (xmlExpCtxtPtr) xmlMalloc(sizeof(xmlExpCtxt));
6303 if (ret == NULL)
6304 return(NULL);
6305 memset(ret, 0, sizeof(xmlExpCtxt));
6306 ret->size = size;
6307 ret->nbElems = 0;
6308 ret->table = xmlMalloc(size * sizeof(xmlExpNodePtr));
6309 if (ret->table == NULL) {
6310 xmlFree(ret);
6311 return(NULL);
6312 }
6313 memset(ret->table, 0, size * sizeof(xmlExpNodePtr));
6314 if (dict == NULL) {
6315 ret->dict = xmlDictCreate();
6316 if (ret->dict == NULL) {
6317 xmlFree(ret->table);
6318 xmlFree(ret);
6319 return(NULL);
6320 }
6321 } else {
6322 ret->dict = dict;
6323 xmlDictReference(ret->dict);
6324 }
6325 return(ret);
6326}
6327
6328/**
6329 * xmlExpFreeCtxt:
6330 * @ctxt: an expression context
6331 *
6332 * Free an expression context
6333 */
6334void
6335xmlExpFreeCtxt(xmlExpCtxtPtr ctxt) {
6336 if (ctxt == NULL)
6337 return;
6338 xmlDictFree(ctxt->dict);
6339 if (ctxt->table != NULL)
6340 xmlFree(ctxt->table);
6341 xmlFree(ctxt);
6342}
6343
6344/************************************************************************
6345 * *
6346 * Structure associated to an expression node *
6347 * *
6348 ************************************************************************/
6349#define MAX_NODES 10000
6350
6351/* #define DEBUG_DERIV */
6352
6353/*
6354 * TODO:
6355 * - Wildcards
6356 * - public API for creation
6357 *
6358 * Started
6359 * - regression testing
6360 *
6361 * Done
6362 * - split into module and test tool
6363 * - memleaks
6364 */
6365
6366typedef enum {
6367 XML_EXP_NILABLE = (1 << 0)
6368} xmlExpNodeInfo;
6369
6370#define IS_NILLABLE(node) ((node)->info & XML_EXP_NILABLE)
6371
6372struct _xmlExpNode {
6373 unsigned char type;/* xmlExpNodeType */
6374 unsigned char info;/* OR of xmlExpNodeInfo */
6375 unsigned short key; /* the hash key */
6376 unsigned int ref; /* The number of references */
6377 int c_max; /* the maximum length it can consume */
6378 xmlExpNodePtr exp_left;
6379 xmlExpNodePtr next;/* the next node in the hash table or free list */
6380 union {
6381 struct {
6382 int f_min;
6383 int f_max;
6384 } count;
6385 struct {
6386 xmlExpNodePtr f_right;
6387 } children;
6388 const xmlChar *f_str;
6389 } field;
6390};
6391
6392#define exp_min field.count.f_min
6393#define exp_max field.count.f_max
6394/* #define exp_left field.children.f_left */
6395#define exp_right field.children.f_right
6396#define exp_str field.f_str
6397
6398static xmlExpNodePtr xmlExpNewNode(xmlExpCtxtPtr ctxt, xmlExpNodeType type);
6399static xmlExpNode forbiddenExpNode = {
6400 XML_EXP_FORBID, 0, 0, 0, 0, NULL, NULL, {{ 0, 0}}
6401};
6402xmlExpNodePtr forbiddenExp = &forbiddenExpNode;
6403static xmlExpNode emptyExpNode = {
6404 XML_EXP_EMPTY, 1, 0, 0, 0, NULL, NULL, {{ 0, 0}}
6405};
6406xmlExpNodePtr emptyExp = &emptyExpNode;
6407
6408/************************************************************************
6409 * *
6410 * The custom hash table for unicity and canonicalization *
6411 * of sub-expressions pointers *
6412 * *
6413 ************************************************************************/
6414/*
6415 * xmlExpHashNameComputeKey:
6416 * Calculate the hash key for a token
6417 */
6418static unsigned short
6419xmlExpHashNameComputeKey(const xmlChar *name) {
6420 unsigned short value = 0L;
6421 char ch;
6422
6423 if (name != NULL) {
6424 value += 30 * (*name);
6425 while ((ch = *name++) != 0) {
6426 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
6427 }
6428 }
6429 return (value);
6430}
6431
6432/*
6433 * xmlExpHashComputeKey:
6434 * Calculate the hash key for a compound expression
6435 */
6436static unsigned short
6437xmlExpHashComputeKey(xmlExpNodeType type, xmlExpNodePtr left,
6438 xmlExpNodePtr right) {
6439 unsigned long value;
6440 unsigned short ret;
6441
6442 switch (type) {
6443 case XML_EXP_SEQ:
6444 value = left->key;
6445 value += right->key;
6446 value *= 3;
6447 ret = (unsigned short) value;
6448 break;
6449 case XML_EXP_OR:
6450 value = left->key;
6451 value += right->key;
6452 value *= 7;
6453 ret = (unsigned short) value;
6454 break;
6455 case XML_EXP_COUNT:
6456 value = left->key;
6457 value += right->key;
6458 ret = (unsigned short) value;
6459 break;
6460 default:
6461 ret = 0;
6462 }
6463 return(ret);
6464}
6465
6466
6467static xmlExpNodePtr
6468xmlExpNewNode(xmlExpCtxtPtr ctxt, xmlExpNodeType type) {
6469 xmlExpNodePtr ret;
6470
6471 if (ctxt->nb_nodes >= MAX_NODES)
6472 return(NULL);
6473 ret = (xmlExpNodePtr) xmlMalloc(sizeof(xmlExpNode));
6474 if (ret == NULL)
6475 return(NULL);
6476 memset(ret, 0, sizeof(xmlExpNode));
6477 ret->type = type;
6478 ret->next = NULL;
6479 ctxt->nb_nodes++;
6480 ctxt->nb_cons++;
6481 return(ret);
6482}
6483
6484/**
6485 * xmlExpHashGetEntry:
6486 * @table: the hash table
6487 *
6488 * Get the unique entry from the hash table. The entry is created if
6489 * needed. @left and @right are consumed, i.e. their ref count will
6490 * be decremented by the operation.
6491 *
6492 * Returns the pointer or NULL in case of error
6493 */
6494static xmlExpNodePtr
6495xmlExpHashGetEntry(xmlExpCtxtPtr ctxt, xmlExpNodeType type,
6496 xmlExpNodePtr left, xmlExpNodePtr right,
6497 const xmlChar *name, int min, int max) {
6498 unsigned short kbase, key;
6499 xmlExpNodePtr entry;
6500 xmlExpNodePtr insert;
6501
6502 if (ctxt == NULL)
6503 return(NULL);
6504
6505 /*
6506 * Check for duplicate and insertion location.
6507 */
6508 if (type == XML_EXP_ATOM) {
6509 kbase = xmlExpHashNameComputeKey(name);
6510 } else if (type == XML_EXP_COUNT) {
6511 /* COUNT reduction rule 1 */
6512 /* a{1} -> a */
6513 if (min == max) {
6514 if (min == 1) {
6515 return(left);
6516 }
6517 if (min == 0) {
6518 xmlExpFree(ctxt, left);
6519 return(emptyExp);
6520 }
6521 }
6522 if (min < 0) {
6523 xmlExpFree(ctxt, left);
6524 return(forbiddenExp);
6525 }
6526 if (max == -1)
6527 kbase = min + 79;
6528 else
6529 kbase = max - min;
6530 kbase += left->key;
6531 } else if (type == XML_EXP_OR) {
6532 /* Forbid reduction rules */
6533 if (left->type == XML_EXP_FORBID) {
6534 xmlExpFree(ctxt, left);
6535 return(right);
6536 }
6537 if (right->type == XML_EXP_FORBID) {
6538 xmlExpFree(ctxt, right);
6539 return(left);
6540 }
6541
6542 /* OR reduction rule 1 */
6543 /* a | a reduced to a */
6544 if (left == right) {
6545 left->ref--;
6546 return(left);
6547 }
6548 /* OR canonicalization rule 1 */
6549 /* linearize (a | b) | c into a | (b | c) */
6550 if ((left->type == XML_EXP_OR) && (right->type != XML_EXP_OR)) {
6551 xmlExpNodePtr tmp = left;
6552 left = right;
6553 right = tmp;
6554 }
6555 /* OR reduction rule 2 */
6556 /* a | (a | b) and b | (a | b) are reduced to a | b */
6557 if (right->type == XML_EXP_OR) {
6558 if ((left == right->exp_left) ||
6559 (left == right->exp_right)) {
6560 xmlExpFree(ctxt, left);
6561 return(right);
6562 }
6563 }
6564 /* OR canonicalization rule 2 */
6565 /* linearize (a | b) | c into a | (b | c) */
6566 if (left->type == XML_EXP_OR) {
6567 xmlExpNodePtr tmp;
6568
6569 /* OR canonicalization rule 2 */
6570 if ((left->exp_right->type != XML_EXP_OR) &&
6571 (left->exp_right->key < left->exp_left->key)) {
6572 tmp = left->exp_right;
6573 left->exp_right = left->exp_left;
6574 left->exp_left = tmp;
6575 }
6576 left->exp_right->ref++;
6577 tmp = xmlExpHashGetEntry(ctxt, XML_EXP_OR, left->exp_right, right,
6578 NULL, 0, 0);
6579 left->exp_left->ref++;
6580 tmp = xmlExpHashGetEntry(ctxt, XML_EXP_OR, left->exp_left, tmp,
6581 NULL, 0, 0);
6582
6583 xmlExpFree(ctxt, left);
6584 return(tmp);
6585 }
6586 if (right->type == XML_EXP_OR) {
6587 /* Ordering in the tree */
6588 /* C | (A | B) -> A | (B | C) */
6589 if (left->key > right->exp_right->key) {
6590 xmlExpNodePtr tmp;
6591 right->exp_right->ref++;
6592 tmp = xmlExpHashGetEntry(ctxt, XML_EXP_OR, right->exp_right,
6593 left, NULL, 0, 0);
6594 right->exp_left->ref++;
6595 tmp = xmlExpHashGetEntry(ctxt, XML_EXP_OR, right->exp_left,
6596 tmp, NULL, 0, 0);
6597 xmlExpFree(ctxt, right);
6598 return(tmp);
6599 }
6600 /* Ordering in the tree */
6601 /* B | (A | C) -> A | (B | C) */
6602 if (left->key > right->exp_left->key) {
6603 xmlExpNodePtr tmp;
6604 right->exp_right->ref++;
6605 tmp = xmlExpHashGetEntry(ctxt, XML_EXP_OR, left,
6606 right->exp_right, NULL, 0, 0);
6607 right->exp_left->ref++;
6608 tmp = xmlExpHashGetEntry(ctxt, XML_EXP_OR, right->exp_left,
6609 tmp, NULL, 0, 0);
6610 xmlExpFree(ctxt, right);
6611 return(tmp);
6612 }
6613 }
6614 /* we know both types are != XML_EXP_OR here */
6615 else if (left->key > right->key) {
6616 xmlExpNodePtr tmp = left;
6617 left = right;
6618 right = tmp;
6619 }
6620 kbase = xmlExpHashComputeKey(type, left, right);
6621 } else if (type == XML_EXP_SEQ) {
6622 /* Forbid reduction rules */
6623 if (left->type == XML_EXP_FORBID) {
6624 xmlExpFree(ctxt, right);
6625 return(left);
6626 }
6627 if (right->type == XML_EXP_FORBID) {
6628 xmlExpFree(ctxt, left);
6629 return(right);
6630 }
6631 /* Empty reduction rules */
6632 if (right->type == XML_EXP_EMPTY) {
6633 return(left);
6634 }
6635 if (left->type == XML_EXP_EMPTY) {
6636 return(right);
6637 }
6638 kbase = xmlExpHashComputeKey(type, left, right);
6639 } else
6640 return(NULL);
6641
6642 key = kbase % ctxt->size;
6643 if (ctxt->table[key] != NULL) {
6644 for (insert = ctxt->table[key]; insert != NULL;
6645 insert = insert->next) {
6646 if ((insert->key == kbase) &&
6647 (insert->type == type)) {
6648 if (type == XML_EXP_ATOM) {
6649 if (name == insert->exp_str) {
6650 insert->ref++;
6651 return(insert);
6652 }
6653 } else if (type == XML_EXP_COUNT) {
6654 if ((insert->exp_min == min) && (insert->exp_max == max) &&
6655 (insert->exp_left == left)) {
6656 insert->ref++;
6657 left->ref--;
6658 return(insert);
6659 }
6660 } else if ((insert->exp_left == left) &&
6661 (insert->exp_right == right)) {
6662 insert->ref++;
6663 left->ref--;
6664 right->ref--;
6665 return(insert);
6666 }
6667 }
6668 }
6669 }
6670
6671 entry = xmlExpNewNode(ctxt, type);
6672 if (entry == NULL)
6673 return(NULL);
6674 entry->key = kbase;
6675 if (type == XML_EXP_ATOM) {
6676 entry->exp_str = name;
6677 entry->c_max = 1;
6678 } else if (type == XML_EXP_COUNT) {
6679 entry->exp_min = min;
6680 entry->exp_max = max;
6681 entry->exp_left = left;
6682 if ((min == 0) || (IS_NILLABLE(left)))
6683 entry->info |= XML_EXP_NILABLE;
6684 if (max < 0)
6685 entry->c_max = -1;
6686 else
6687 entry->c_max = max * entry->exp_left->c_max;
6688 } else {
6689 entry->exp_left = left;
6690 entry->exp_right = right;
6691 if (type == XML_EXP_OR) {
6692 if ((IS_NILLABLE(left)) || (IS_NILLABLE(right)))
6693 entry->info |= XML_EXP_NILABLE;
6694 if ((entry->exp_left->c_max == -1) ||
6695 (entry->exp_right->c_max == -1))
6696 entry->c_max = -1;
6697 else if (entry->exp_left->c_max > entry->exp_right->c_max)
6698 entry->c_max = entry->exp_left->c_max;
6699 else
6700 entry->c_max = entry->exp_right->c_max;
6701 } else {
6702 if ((IS_NILLABLE(left)) && (IS_NILLABLE(right)))
6703 entry->info |= XML_EXP_NILABLE;
6704 if ((entry->exp_left->c_max == -1) ||
6705 (entry->exp_right->c_max == -1))
6706 entry->c_max = -1;
6707 else
6708 entry->c_max = entry->exp_left->c_max + entry->exp_right->c_max;
6709 }
6710 }
6711 entry->ref = 1;
6712 if (ctxt->table[key] != NULL)
6713 entry->next = ctxt->table[key];
6714
6715 ctxt->table[key] = entry;
6716 ctxt->nbElems++;
6717
6718 return(entry);
6719}
6720
6721/**
6722 * xmlExpFree:
6723 * @ctxt: the expression context
6724 * @exp: the expression
6725 *
6726 * Dereference the expression
6727 */
6728void
6729xmlExpFree(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp) {
6730 if ((exp == NULL) || (exp == forbiddenExp) || (exp == emptyExp))
6731 return;
6732 exp->ref--;
6733 if (exp->ref == 0) {
6734 unsigned short key;
6735
6736 /* Unlink it first from the hash table */
6737 key = exp->key % ctxt->size;
6738 if (ctxt->table[key] == exp) {
6739 ctxt->table[key] = exp->next;
6740 } else {
6741 xmlExpNodePtr tmp;
6742
6743 tmp = ctxt->table[key];
6744 while (tmp != NULL) {
6745 if (tmp->next == exp) {
6746 tmp->next = exp->next;
6747 break;
6748 }
6749 tmp = tmp->next;
6750 }
6751 }
6752
6753 if ((exp->type == XML_EXP_SEQ) || (exp->type == XML_EXP_OR)) {
6754 xmlExpFree(ctxt, exp->exp_left);
6755 xmlExpFree(ctxt, exp->exp_right);
6756 } else if (exp->type == XML_EXP_COUNT) {
6757 xmlExpFree(ctxt, exp->exp_left);
6758 }
6759 xmlFree(exp);
6760 ctxt->nb_nodes--;
6761 }
6762}
6763
6764/**
6765 * xmlExpRef:
6766 * @exp: the expression
6767 *
6768 * Increase the reference count of the expression
6769 */
6770void
6771xmlExpRef(xmlExpNodePtr exp) {
6772 if (exp != NULL)
6773 exp->ref++;
6774}
6775
6776/**
6777 * xmlExpNewAtom:
6778 * @ctxt: the expression context
6779 * @name: the atom name
6780 * @len: the atom name lenght in byte (or -1);
6781 *
6782 * Get the atom associated to this name from that context
6783 *
6784 * Returns the node or NULL in case of error
6785 */
6786xmlExpNodePtr
6787xmlExpNewAtom(xmlExpCtxtPtr ctxt, const xmlChar *name, int len) {
6788 if ((ctxt == NULL) || (name == NULL))
6789 return(NULL);
6790 name = xmlDictLookup(ctxt->dict, name, len);
6791 if (name == NULL)
6792 return(NULL);
6793 return(xmlExpHashGetEntry(ctxt, XML_EXP_ATOM, NULL, NULL, name, 0, 0));
6794}
6795
6796/**
6797 * xmlExpNewOr:
6798 * @ctxt: the expression context
6799 * @left: left expression
6800 * @right: right expression
6801 *
6802 * Get the atom associated to the choice @left | @right
6803 * Note that @left and @right are consumed in the operation, to keep
6804 * an handle on them use xmlExpRef() and use xmlExpFree() to release them,
6805 * this is true even in case of failure (unless ctxt == NULL).
6806 *
6807 * Returns the node or NULL in case of error
6808 */
6809xmlExpNodePtr
6810xmlExpNewOr(xmlExpCtxtPtr ctxt, xmlExpNodePtr left, xmlExpNodePtr right) {
6811 if (ctxt == NULL)
6812 return(NULL);
6813 if ((left == NULL) || (right == NULL)) {
6814 xmlExpFree(ctxt, left);
6815 xmlExpFree(ctxt, right);
6816 return(NULL);
6817 }
6818 return(xmlExpHashGetEntry(ctxt, XML_EXP_OR, left, right, NULL, 0, 0));
6819}
6820
6821/**
6822 * xmlExpNewSeq:
6823 * @ctxt: the expression context
6824 * @left: left expression
6825 * @right: right expression
6826 *
6827 * Get the atom associated to the sequence @left , @right
6828 * Note that @left and @right are consumed in the operation, to keep
6829 * an handle on them use xmlExpRef() and use xmlExpFree() to release them,
6830 * this is true even in case of failure (unless ctxt == NULL).
6831 *
6832 * Returns the node or NULL in case of error
6833 */
6834xmlExpNodePtr
6835xmlExpNewSeq(xmlExpCtxtPtr ctxt, xmlExpNodePtr left, xmlExpNodePtr right) {
6836 if (ctxt == NULL)
6837 return(NULL);
6838 if ((left == NULL) || (right == NULL)) {
6839 xmlExpFree(ctxt, left);
6840 xmlExpFree(ctxt, right);
6841 return(NULL);
6842 }
6843 return(xmlExpHashGetEntry(ctxt, XML_EXP_SEQ, left, right, NULL, 0, 0));
6844}
6845
6846/**
6847 * xmlExpNewRange:
6848 * @ctxt: the expression context
6849 * @subset: the expression to be repeated
6850 * @min: the lower bound for the repetition
6851 * @max: the upper bound for the repetition, -1 means infinite
6852 *
6853 * Get the atom associated to the range (@subset){@min, @max}
6854 * Note that @subset is consumed in the operation, to keep
6855 * an handle on it use xmlExpRef() and use xmlExpFree() to release it,
6856 * this is true even in case of failure (unless ctxt == NULL).
6857 *
6858 * Returns the node or NULL in case of error
6859 */
6860xmlExpNodePtr
6861xmlExpNewRange(xmlExpCtxtPtr ctxt, xmlExpNodePtr subset, int min, int max) {
6862 if (ctxt == NULL)
6863 return(NULL);
6864 if ((subset == NULL) || (min < 0) || (max < -1) ||
6865 ((max >= 0) && (min > max))) {
6866 xmlExpFree(ctxt, subset);
6867 return(NULL);
6868 }
6869 return(xmlExpHashGetEntry(ctxt, XML_EXP_COUNT, subset,
6870 NULL, NULL, min, max));
6871}
6872
6873/************************************************************************
6874 * *
6875 * Public API for operations on expressions *
6876 * *
6877 ************************************************************************/
6878
6879static int
6880xmlExpGetLanguageInt(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp,
6881 const xmlChar**list, int len, int nb) {
6882 int tmp, tmp2;
6883tail:
6884 switch (exp->type) {
6885 case XML_EXP_EMPTY:
6886 return(0);
6887 case XML_EXP_ATOM:
6888 for (tmp = 0;tmp < nb;tmp++)
6889 if (list[tmp] == exp->exp_str)
6890 return(0);
6891 if (nb >= len)
6892 return(-2);
6893 list[nb++] = exp->exp_str;
6894 return(1);
6895 case XML_EXP_COUNT:
6896 exp = exp->exp_left;
6897 goto tail;
6898 case XML_EXP_SEQ:
6899 case XML_EXP_OR:
6900 tmp = xmlExpGetLanguageInt(ctxt, exp->exp_left, list, len, nb);
6901 if (tmp < 0)
6902 return(tmp);
6903 tmp2 = xmlExpGetLanguageInt(ctxt, exp->exp_right, list, len,
6904 nb + tmp);
6905 if (tmp2 < 0)
6906 return(tmp2);
6907 return(tmp + tmp2);
6908 }
6909 return(-1);
6910}
6911
6912/**
6913 * xmlExpGetLanguage:
6914 * @ctxt: the expression context
6915 * @exp: the expression
6916 * @langList: where to store the tokens
6917 * @len: the allocated lenght of @list
6918 *
6919 * Find all the strings used in @exp and store them in @list
6920 *
6921 * Returns the number of unique strings found, -1 in case of errors and
6922 * -2 if there is more than @len strings
6923 */
6924int
6925xmlExpGetLanguage(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp,
6926 const xmlChar**langList, int len) {
6927 if ((ctxt == NULL) || (exp == NULL) || (langList == NULL) || (len <= 0))
6928 return(-1);
6929 return(xmlExpGetLanguageInt(ctxt, exp, langList, len, 0));
6930}
6931
6932static int
6933xmlExpGetStartInt(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp,
6934 const xmlChar**list, int len, int nb) {
6935 int tmp, tmp2;
6936tail:
6937 switch (exp->type) {
6938 case XML_EXP_FORBID:
6939 return(0);
6940 case XML_EXP_EMPTY:
6941 return(0);
6942 case XML_EXP_ATOM:
6943 for (tmp = 0;tmp < nb;tmp++)
6944 if (list[tmp] == exp->exp_str)
6945 return(0);
6946 if (nb >= len)
6947 return(-2);
6948 list[nb++] = exp->exp_str;
6949 return(1);
6950 case XML_EXP_COUNT:
6951 exp = exp->exp_left;
6952 goto tail;
6953 case XML_EXP_SEQ:
6954 tmp = xmlExpGetStartInt(ctxt, exp->exp_left, list, len, nb);
6955 if (tmp < 0)
6956 return(tmp);
6957 if (IS_NILLABLE(exp->exp_left)) {
6958 tmp2 = xmlExpGetStartInt(ctxt, exp->exp_right, list, len,
6959 nb + tmp);
6960 if (tmp2 < 0)
6961 return(tmp2);
6962 tmp += tmp2;
6963 }
6964 return(tmp);
6965 case XML_EXP_OR:
6966 tmp = xmlExpGetStartInt(ctxt, exp->exp_left, list, len, nb);
6967 if (tmp < 0)
6968 return(tmp);
6969 tmp2 = xmlExpGetStartInt(ctxt, exp->exp_right, list, len,
6970 nb + tmp);
6971 if (tmp2 < 0)
6972 return(tmp2);
6973 return(tmp + tmp2);
6974 }
6975 return(-1);
6976}
6977
6978/**
6979 * xmlExpGetStart:
6980 * @ctxt: the expression context
6981 * @exp: the expression
6982 * @tokList: where to store the tokens
6983 * @len: the allocated lenght of @list
6984 *
6985 * Find all the strings that appears at the start of the languages
6986 * accepted by @exp and store them in @list. E.g. for (a, b) | c
6987 * it will return the list [a, c]
6988 *
6989 * Returns the number of unique strings found, -1 in case of errors and
6990 * -2 if there is more than @len strings
6991 */
6992int
6993xmlExpGetStart(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp,
6994 const xmlChar**tokList, int len) {
6995 if ((ctxt == NULL) || (exp == NULL) || (tokList == NULL) || (len <= 0))
6996 return(-1);
6997 return(xmlExpGetStartInt(ctxt, exp, tokList, len, 0));
6998}
6999
7000/**
7001 * xmlExpIsNillable:
7002 * @exp: the expression
7003 *
7004 * Finds if the expression is nillable, i.e. if it accepts the empty sequqnce
7005 *
7006 * Returns 1 if nillable, 0 if not and -1 in case of error
7007 */
7008int
7009xmlExpIsNillable(xmlExpNodePtr exp) {
7010 if (exp == NULL)
7011 return(-1);
7012 return(IS_NILLABLE(exp) != 0);
7013}
7014
7015static xmlExpNodePtr
7016xmlExpStringDeriveInt(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp, const xmlChar *str)
7017{
7018 xmlExpNodePtr ret;
7019
7020 switch (exp->type) {
7021 case XML_EXP_EMPTY:
7022 return(forbiddenExp);
7023 case XML_EXP_FORBID:
7024 return(forbiddenExp);
7025 case XML_EXP_ATOM:
7026 if (exp->exp_str == str) {
7027#ifdef DEBUG_DERIV
7028 printf("deriv atom: equal => Empty\n");
7029#endif
7030 ret = emptyExp;
7031 } else {
7032#ifdef DEBUG_DERIV
7033 printf("deriv atom: mismatch => forbid\n");
7034#endif
7035 /* TODO wildcards here */
7036 ret = forbiddenExp;
7037 }
7038 return(ret);
7039 case XML_EXP_OR: {
7040 xmlExpNodePtr tmp;
7041
7042#ifdef DEBUG_DERIV
7043 printf("deriv or: => or(derivs)\n");
7044#endif
7045 tmp = xmlExpStringDeriveInt(ctxt, exp->exp_left, str);
7046 if (tmp == NULL) {
7047 return(NULL);
7048 }
7049 ret = xmlExpStringDeriveInt(ctxt, exp->exp_right, str);
7050 if (ret == NULL) {
7051 xmlExpFree(ctxt, tmp);
7052 return(NULL);
7053 }
7054 ret = xmlExpHashGetEntry(ctxt, XML_EXP_OR, tmp, ret,
7055 NULL, 0, 0);
7056 return(ret);
7057 }
7058 case XML_EXP_SEQ:
7059#ifdef DEBUG_DERIV
7060 printf("deriv seq: starting with left\n");
7061#endif
7062 ret = xmlExpStringDeriveInt(ctxt, exp->exp_left, str);
7063 if (ret == NULL) {
7064 return(NULL);
7065 } else if (ret == forbiddenExp) {
7066 if (IS_NILLABLE(exp->exp_left)) {
7067#ifdef DEBUG_DERIV
7068 printf("deriv seq: left failed but nillable\n");
7069#endif
7070 ret = xmlExpStringDeriveInt(ctxt, exp->exp_right, str);
7071 }
7072 } else {
7073#ifdef DEBUG_DERIV
7074 printf("deriv seq: left match => sequence\n");
7075#endif
7076 exp->exp_right->ref++;
7077 ret = xmlExpHashGetEntry(ctxt, XML_EXP_SEQ, ret, exp->exp_right,
7078 NULL, 0, 0);
7079 }
7080 return(ret);
7081 case XML_EXP_COUNT: {
7082 int min, max;
7083 xmlExpNodePtr tmp;
7084
7085 if (exp->exp_max == 0)
7086 return(forbiddenExp);
7087 ret = xmlExpStringDeriveInt(ctxt, exp->exp_left, str);
7088 if (ret == NULL)
7089 return(NULL);
7090 if (ret == forbiddenExp) {
7091#ifdef DEBUG_DERIV
7092 printf("deriv count: pattern mismatch => forbid\n");
7093#endif
7094 return(ret);
7095 }
7096 if (exp->exp_max == 1)
7097 return(ret);
7098 if (exp->exp_max < 0) /* unbounded */
7099 max = -1;
7100 else
7101 max = exp->exp_max - 1;
7102 if (exp->exp_min > 0)
7103 min = exp->exp_min - 1;
7104 else
7105 min = 0;
7106 exp->exp_left->ref++;
7107 tmp = xmlExpHashGetEntry(ctxt, XML_EXP_COUNT, exp->exp_left, NULL,
7108 NULL, min, max);
7109 if (ret == emptyExp) {
7110#ifdef DEBUG_DERIV
7111 printf("deriv count: match to empty => new count\n");
7112#endif
7113 return(tmp);
7114 }
7115#ifdef DEBUG_DERIV
7116 printf("deriv count: match => sequence with new count\n");
7117#endif
7118 return(xmlExpHashGetEntry(ctxt, XML_EXP_SEQ, ret, tmp,
7119 NULL, 0, 0));
7120 }
7121 }
7122 return(NULL);
7123}
7124
7125/**
7126 * xmlExpStringDerive:
7127 * @ctxt: the expression context
7128 * @exp: the expression
7129 * @str: the string
7130 * @len: the string len in bytes if available
7131 *
7132 * Do one step of Brzozowski derivation of the expression @exp with
7133 * respect to the input string
7134 *
7135 * Returns the resulting expression or NULL in case of internal error
7136 */
7137xmlExpNodePtr
7138xmlExpStringDerive(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp,
7139 const xmlChar *str, int len) {
7140 const xmlChar *input;
7141
7142 if ((exp == NULL) || (ctxt == NULL) || (str == NULL)) {
7143 return(NULL);
7144 }
7145 /*
7146 * check the string is in the dictionnary, if yes use an interned
7147 * copy, otherwise we know it's not an acceptable input
7148 */
7149 input = xmlDictExists(ctxt->dict, str, len);
7150 if (input == NULL) {
7151 return(forbiddenExp);
7152 }
7153 return(xmlExpStringDeriveInt(ctxt, exp, input));
7154}
7155
7156static int
7157xmlExpCheckCard(xmlExpNodePtr exp, xmlExpNodePtr sub) {
7158 int ret = 1;
7159
7160 if (sub->c_max == -1) {
7161 if (exp->c_max != -1)
7162 ret = 0;
7163 } else if ((exp->c_max >= 0) && (exp->c_max < sub->c_max)) {
7164 ret = 0;
7165 }
7166#if 0
7167 if ((IS_NILLABLE(sub)) && (!IS_NILLABLE(exp)))
7168 ret = 0;
7169#endif
7170 return(ret);
7171}
7172
7173static xmlExpNodePtr xmlExpExpDeriveInt(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp,
7174 xmlExpNodePtr sub);
7175/**
7176 * xmlExpDivide:
7177 * @ctxt: the expressions context
7178 * @exp: the englobing expression
7179 * @sub: the subexpression
7180 * @mult: the multiple expression
7181 * @remain: the remain from the derivation of the multiple
7182 *
7183 * Check if exp is a multiple of sub, i.e. if there is a finite number n
7184 * so that sub{n} subsume exp
7185 *
7186 * Returns the multiple value if successful, 0 if it is not a multiple
7187 * and -1 in case of internel error.
7188 */
7189
7190static int
7191xmlExpDivide(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp, xmlExpNodePtr sub,
7192 xmlExpNodePtr *mult, xmlExpNodePtr *remain) {
7193 int i;
7194 xmlExpNodePtr tmp, tmp2;
7195
7196 if (mult != NULL) *mult = NULL;
7197 if (remain != NULL) *remain = NULL;
7198 if (exp->c_max == -1) return(0);
7199 if (IS_NILLABLE(exp) && (!IS_NILLABLE(sub))) return(0);
7200
7201 for (i = 1;i <= exp->c_max;i++) {
7202 sub->ref++;
7203 tmp = xmlExpHashGetEntry(ctxt, XML_EXP_COUNT,
7204 sub, NULL, NULL, i, i);
7205 if (tmp == NULL) {
7206 return(-1);
7207 }
7208 if (!xmlExpCheckCard(tmp, exp)) {
7209 xmlExpFree(ctxt, tmp);
7210 continue;
7211 }
7212 tmp2 = xmlExpExpDeriveInt(ctxt, tmp, exp);
7213 if (tmp2 == NULL) {
7214 xmlExpFree(ctxt, tmp);
7215 return(-1);
7216 }
7217 if ((tmp2 != forbiddenExp) && (IS_NILLABLE(tmp2))) {
7218 if (remain != NULL)
7219 *remain = tmp2;
7220 else
7221 xmlExpFree(ctxt, tmp2);
7222 if (mult != NULL)
7223 *mult = tmp;
7224 else
7225 xmlExpFree(ctxt, tmp);
7226#ifdef DEBUG_DERIV
7227 printf("Divide succeeded %d\n", i);
7228#endif
7229 return(i);
7230 }
7231 xmlExpFree(ctxt, tmp);
7232 xmlExpFree(ctxt, tmp2);
7233 }
7234#ifdef DEBUG_DERIV
7235 printf("Divide failed\n");
7236#endif
7237 return(0);
7238}
7239
7240/**
7241 * xmlExpExpDeriveInt:
7242 * @ctxt: the expressions context
7243 * @exp: the englobing expression
7244 * @sub: the subexpression
7245 *
7246 * Try to do a step of Brzozowski derivation but at a higher level
7247 * the input being a subexpression.
7248 *
7249 * Returns the resulting expression or NULL in case of internal error
7250 */
7251static xmlExpNodePtr
7252xmlExpExpDeriveInt(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp, xmlExpNodePtr sub) {
7253 xmlExpNodePtr ret, tmp, tmp2, tmp3;
7254 const xmlChar **tab;
7255 int len, i;
7256
7257 /*
7258 * In case of equality and if the expression can only consume a finite
7259 * amount, then the derivation is empty
7260 */
7261 if ((exp == sub) && (exp->c_max >= 0)) {
7262#ifdef DEBUG_DERIV
7263 printf("Equal(exp, sub) and finite -> Empty\n");
7264#endif
7265 return(emptyExp);
7266 }
7267 /*
7268 * decompose sub sequence first
7269 */
7270 if (sub->type == XML_EXP_EMPTY) {
7271#ifdef DEBUG_DERIV
7272 printf("Empty(sub) -> Empty\n");
7273#endif
7274 exp->ref++;
7275 return(exp);
7276 }
7277 if (sub->type == XML_EXP_SEQ) {
7278#ifdef DEBUG_DERIV
7279 printf("Seq(sub) -> decompose\n");
7280#endif
7281 tmp = xmlExpExpDeriveInt(ctxt, exp, sub->exp_left);
7282 if (tmp == NULL)
7283 return(NULL);
7284 if (tmp == forbiddenExp)
7285 return(tmp);
7286 ret = xmlExpExpDeriveInt(ctxt, tmp, sub->exp_right);
7287 xmlExpFree(ctxt, tmp);
7288 return(ret);
7289 }
7290 if (sub->type == XML_EXP_OR) {
7291#ifdef DEBUG_DERIV
7292 printf("Or(sub) -> decompose\n");
7293#endif
7294 tmp = xmlExpExpDeriveInt(ctxt, exp, sub->exp_left);
7295 if (tmp == forbiddenExp)
7296 return(tmp);
7297 if (tmp == NULL)
7298 return(NULL);
7299 ret = xmlExpExpDeriveInt(ctxt, exp, sub->exp_right);
7300 if ((ret == NULL) || (ret == forbiddenExp)) {
7301 xmlExpFree(ctxt, tmp);
7302 return(ret);
7303 }
7304 return(xmlExpHashGetEntry(ctxt, XML_EXP_OR, tmp, ret, NULL, 0, 0));
7305 }
7306 if (!xmlExpCheckCard(exp, sub)) {
7307#ifdef DEBUG_DERIV
7308 printf("CheckCard(exp, sub) failed -> Forbid\n");
7309#endif
7310 return(forbiddenExp);
7311 }
7312 switch (exp->type) {
7313 case XML_EXP_EMPTY:
7314 if (sub == emptyExp)
7315 return(emptyExp);
7316#ifdef DEBUG_DERIV
7317 printf("Empty(exp) -> Forbid\n");
7318#endif
7319 return(forbiddenExp);
7320 case XML_EXP_FORBID:
7321#ifdef DEBUG_DERIV
7322 printf("Forbid(exp) -> Forbid\n");
7323#endif
7324 return(forbiddenExp);
7325 case XML_EXP_ATOM:
7326 if (sub->type == XML_EXP_ATOM) {
7327 /* TODO: handle wildcards */
7328 if (exp->exp_str == sub->exp_str) {
7329#ifdef DEBUG_DERIV
7330 printf("Atom match -> Empty\n");
7331#endif
7332 return(emptyExp);
7333 }
7334#ifdef DEBUG_DERIV
7335 printf("Atom mismatch -> Forbid\n");
7336#endif
7337 return(forbiddenExp);
7338 }
7339 if ((sub->type == XML_EXP_COUNT) &&
7340 (sub->exp_max == 1) &&
7341 (sub->exp_left->type == XML_EXP_ATOM)) {
7342 /* TODO: handle wildcards */
7343 if (exp->exp_str == sub->exp_left->exp_str) {
7344#ifdef DEBUG_DERIV
7345 printf("Atom match -> Empty\n");
7346#endif
7347 return(emptyExp);
7348 }
7349#ifdef DEBUG_DERIV
7350 printf("Atom mismatch -> Forbid\n");
7351#endif
7352 return(forbiddenExp);
7353 }
7354#ifdef DEBUG_DERIV
7355 printf("Compex exp vs Atom -> Forbid\n");
7356#endif
7357 return(forbiddenExp);
7358 case XML_EXP_SEQ:
7359 /* try to get the sequence consumed only if possible */
7360 if (xmlExpCheckCard(exp->exp_left, sub)) {
7361 /* See if the sequence can be consumed directly */
7362#ifdef DEBUG_DERIV
7363 printf("Seq trying left only\n");
7364#endif
7365 ret = xmlExpExpDeriveInt(ctxt, exp->exp_left, sub);
7366 if ((ret != forbiddenExp) && (ret != NULL)) {
7367#ifdef DEBUG_DERIV
7368 printf("Seq trying left only worked\n");
7369#endif
7370 /*
7371 * TODO: assumption here that we are determinist
7372 * i.e. we won't get to a nillable exp left
7373 * subset which could be matched by the right
7374 * part too.
7375 * e.g.: (a | b)+,(a | c) and 'a+,a'
7376 */
7377 exp->exp_right->ref++;
7378 return(xmlExpHashGetEntry(ctxt, XML_EXP_SEQ, ret,
7379 exp->exp_right, NULL, 0, 0));
7380 }
7381#ifdef DEBUG_DERIV
7382 } else {
7383 printf("Seq: left too short\n");
7384#endif
7385 }
7386 /* Try instead to decompose */
7387 if (sub->type == XML_EXP_COUNT) {
7388 int min, max;
7389
7390#ifdef DEBUG_DERIV
7391 printf("Seq: sub is a count\n");
7392#endif
7393 ret = xmlExpExpDeriveInt(ctxt, exp->exp_left, sub->exp_left);
7394 if (ret == NULL)
7395 return(NULL);
7396 if (ret != forbiddenExp) {
7397#ifdef DEBUG_DERIV
7398 printf("Seq , Count match on left\n");
7399#endif
7400 if (sub->exp_max < 0)
7401 max = -1;
7402 else
7403 max = sub->exp_max -1;
7404 if (sub->exp_min > 0)
7405 min = sub->exp_min -1;
7406 else
7407 min = 0;
7408 exp->exp_right->ref++;
7409 tmp = xmlExpHashGetEntry(ctxt, XML_EXP_SEQ, ret,
7410 exp->exp_right, NULL, 0, 0);
7411 if (tmp == NULL)
7412 return(NULL);
7413
7414 sub->exp_left->ref++;
7415 tmp2 = xmlExpHashGetEntry(ctxt, XML_EXP_COUNT,
7416 sub->exp_left, NULL, NULL, min, max);
7417 if (tmp2 == NULL) {
7418 xmlExpFree(ctxt, tmp);
7419 return(NULL);
7420 }
7421 ret = xmlExpExpDeriveInt(ctxt, tmp, tmp2);
7422 xmlExpFree(ctxt, tmp);
7423 xmlExpFree(ctxt, tmp2);
7424 return(ret);
7425 }
7426 }
7427 /* we made no progress on structured operations */
7428 break;
7429 case XML_EXP_OR:
7430#ifdef DEBUG_DERIV
7431 printf("Or , trying both side\n");
7432#endif
7433 ret = xmlExpExpDeriveInt(ctxt, exp->exp_left, sub);
7434 if (ret == NULL)
7435 return(NULL);
7436 tmp = xmlExpExpDeriveInt(ctxt, exp->exp_right, sub);
7437 if (tmp == NULL) {
7438 xmlExpFree(ctxt, ret);
7439 return(NULL);
7440 }
7441 return(xmlExpHashGetEntry(ctxt, XML_EXP_OR, ret, tmp, NULL, 0, 0));
7442 case XML_EXP_COUNT: {
7443 int min, max;
7444
7445 if (sub->type == XML_EXP_COUNT) {
7446 /*
7447 * Try to see if the loop is completely subsumed
7448 */
7449 tmp = xmlExpExpDeriveInt(ctxt, exp->exp_left, sub->exp_left);
7450 if (tmp == NULL)
7451 return(NULL);
7452 if (tmp == forbiddenExp) {
7453 int mult;
7454
7455#ifdef DEBUG_DERIV
7456 printf("Count, Count inner don't subsume\n");
7457#endif
7458 mult = xmlExpDivide(ctxt, sub->exp_left, exp->exp_left,
7459 NULL, &tmp);
7460 if (mult <= 0) {
7461#ifdef DEBUG_DERIV
7462 printf("Count, Count not multiple => forbidden\n");
7463#endif
7464 return(forbiddenExp);
7465 }
7466 if (sub->exp_max == -1) {
7467 max = -1;
7468 if (exp->exp_max == -1) {
7469 if (exp->exp_min <= sub->exp_min * mult)
7470 min = 0;
7471 else
7472 min = exp->exp_min - sub->exp_min * mult;
7473 } else {
7474#ifdef DEBUG_DERIV
7475 printf("Count, Count finite can't subsume infinite\n");
7476#endif
7477 xmlExpFree(ctxt, tmp);
7478 return(forbiddenExp);
7479 }
7480 } else {
7481 if (exp->exp_max == -1) {
7482#ifdef DEBUG_DERIV
7483 printf("Infinite loop consume mult finite loop\n");
7484#endif
7485 if (exp->exp_min > sub->exp_min * mult) {
7486 max = -1;
7487 min = exp->exp_min - sub->exp_min * mult;
7488 } else {
7489 max = -1;
7490 min = 0;
7491 }
7492 } else {
7493 if (exp->exp_max < sub->exp_max * mult) {
7494#ifdef DEBUG_DERIV
7495 printf("loops max mult mismatch => forbidden\n");
7496#endif
7497 xmlExpFree(ctxt, tmp);
7498 return(forbiddenExp);
7499 }
7500 if (sub->exp_max * mult > exp->exp_min)
7501 min = 0;
7502 else
7503 min = exp->exp_min - sub->exp_max * mult;
7504 max = exp->exp_max - sub->exp_max * mult;
7505 }
7506 }
7507 } else if (!IS_NILLABLE(tmp)) {
7508 /*
7509 * TODO: loop here to try to grow if working on finite
7510 * blocks.
7511 */
7512#ifdef DEBUG_DERIV
7513 printf("Count, Count remain not nillable => forbidden\n");
7514#endif
7515 xmlExpFree(ctxt, tmp);
7516 return(forbiddenExp);
7517 } else if (sub->exp_max == -1) {
7518 if (exp->exp_max == -1) {
7519 if (exp->exp_min <= sub->exp_min) {
7520#ifdef DEBUG_DERIV
7521 printf("Infinite loops Okay => COUNT(0,Inf)\n");
7522#endif
7523 max = -1;
7524 min = 0;
7525 } else {
7526#ifdef DEBUG_DERIV
7527 printf("Infinite loops min => Count(X,Inf)\n");
7528#endif
7529 max = -1;
7530 min = exp->exp_min - sub->exp_min;
7531 }
7532 } else if (exp->exp_min > sub->exp_min) {
7533#ifdef DEBUG_DERIV
7534 printf("loops min mismatch 1 => forbidden ???\n");
7535#endif
7536 xmlExpFree(ctxt, tmp);
7537 return(forbiddenExp);
7538 } else {
7539 max = -1;
7540 min = 0;
7541 }
7542 } else {
7543 if (exp->exp_max == -1) {
7544#ifdef DEBUG_DERIV
7545 printf("Infinite loop consume finite loop\n");
7546#endif
7547 if (exp->exp_min > sub->exp_min) {
7548 max = -1;
7549 min = exp->exp_min - sub->exp_min;
7550 } else {
7551 max = -1;
7552 min = 0;
7553 }
7554 } else {
7555 if (exp->exp_max < sub->exp_max) {
7556#ifdef DEBUG_DERIV
7557 printf("loops max mismatch => forbidden\n");
7558#endif
7559 xmlExpFree(ctxt, tmp);
7560 return(forbiddenExp);
7561 }
7562 if (sub->exp_max > exp->exp_min)
7563 min = 0;
7564 else
7565 min = exp->exp_min - sub->exp_max;
7566 max = exp->exp_max - sub->exp_max;
7567 }
7568 }
7569#ifdef DEBUG_DERIV
7570 printf("loops match => SEQ(COUNT())\n");
7571#endif
7572 exp->exp_left->ref++;
7573 tmp2 = xmlExpHashGetEntry(ctxt, XML_EXP_COUNT, exp->exp_left,
7574 NULL, NULL, min, max);
7575 if (tmp2 == NULL) {
7576 return(NULL);
7577 }
7578 ret = xmlExpHashGetEntry(ctxt, XML_EXP_SEQ, tmp, tmp2,
7579 NULL, 0, 0);
7580 return(ret);
7581 }
7582 tmp = xmlExpExpDeriveInt(ctxt, exp->exp_left, sub);
7583 if (tmp == NULL)
7584 return(NULL);
7585 if (tmp == forbiddenExp) {
7586#ifdef DEBUG_DERIV
7587 printf("loop mismatch => forbidden\n");
7588#endif
7589 return(forbiddenExp);
7590 }
7591 if (exp->exp_min > 0)
7592 min = exp->exp_min - 1;
7593 else
7594 min = 0;
7595 if (exp->exp_max < 0)
7596 max = -1;
7597 else
7598 max = exp->exp_max - 1;
7599
7600#ifdef DEBUG_DERIV
7601 printf("loop match => SEQ(COUNT())\n");
7602#endif
7603 exp->exp_left->ref++;
7604 tmp2 = xmlExpHashGetEntry(ctxt, XML_EXP_COUNT, exp->exp_left,
7605 NULL, NULL, min, max);
7606 if (tmp2 == NULL)
7607 return(NULL);
7608 ret = xmlExpHashGetEntry(ctxt, XML_EXP_SEQ, tmp, tmp2,
7609 NULL, 0, 0);
7610 return(ret);
7611 }
7612 }
7613
7614#ifdef DEBUG_DERIV
7615 printf("Fallback to derivative\n");
7616#endif
7617 if (IS_NILLABLE(sub)) {
7618 if (!(IS_NILLABLE(exp)))
7619 return(forbiddenExp);
7620 else
7621 ret = emptyExp;
7622 } else
7623 ret = NULL;
7624 /*
7625 * here the structured derivation made no progress so
7626 * we use the default token based derivation to force one more step
7627 */
7628 if (ctxt->tabSize == 0)
7629 ctxt->tabSize = 40;
7630
7631 tab = (const xmlChar **) xmlMalloc(ctxt->tabSize *
7632 sizeof(const xmlChar *));
7633 if (tab == NULL) {
7634 return(NULL);
7635 }
7636
7637 /*
7638 * collect all the strings accepted by the subexpression on input
7639 */
7640 len = xmlExpGetStartInt(ctxt, sub, tab, ctxt->tabSize, 0);
7641 while (len < 0) {
7642 const xmlChar **temp;
7643 temp = (const xmlChar **) xmlRealloc((xmlChar **) tab, ctxt->tabSize * 2 *
7644 sizeof(const xmlChar *));
7645 if (temp == NULL) {
7646 xmlFree((xmlChar **) tab);
7647 return(NULL);
7648 }
7649 tab = temp;
7650 ctxt->tabSize *= 2;
7651 len = xmlExpGetStartInt(ctxt, sub, tab, ctxt->tabSize, 0);
7652 }
7653 for (i = 0;i < len;i++) {
7654 tmp = xmlExpStringDeriveInt(ctxt, exp, tab[i]);
7655 if ((tmp == NULL) || (tmp == forbiddenExp)) {
7656 xmlExpFree(ctxt, ret);
7657 xmlFree((xmlChar **) tab);
7658 return(tmp);
7659 }
7660 tmp2 = xmlExpStringDeriveInt(ctxt, sub, tab[i]);
7661 if ((tmp2 == NULL) || (tmp2 == forbiddenExp)) {
7662 xmlExpFree(ctxt, tmp);
7663 xmlExpFree(ctxt, ret);
7664 xmlFree((xmlChar **) tab);
7665 return(tmp);
7666 }
7667 tmp3 = xmlExpExpDeriveInt(ctxt, tmp, tmp2);
7668 xmlExpFree(ctxt, tmp);
7669 xmlExpFree(ctxt, tmp2);
7670
7671 if ((tmp3 == NULL) || (tmp3 == forbiddenExp)) {
7672 xmlExpFree(ctxt, ret);
7673 xmlFree((xmlChar **) tab);
7674 return(tmp3);
7675 }
7676
7677 if (ret == NULL)
7678 ret = tmp3;
7679 else {
7680 ret = xmlExpHashGetEntry(ctxt, XML_EXP_OR, ret, tmp3, NULL, 0, 0);
7681 if (ret == NULL) {
7682 xmlFree((xmlChar **) tab);
7683 return(NULL);
7684 }
7685 }
7686 }
7687 xmlFree((xmlChar **) tab);
7688 return(ret);
7689}
7690
7691/**
7692 * xmlExpExpDerive:
7693 * @ctxt: the expressions context
7694 * @exp: the englobing expression
7695 * @sub: the subexpression
7696 *
7697 * Evaluates the expression resulting from @exp consuming a sub expression @sub
7698 * Based on algebraic derivation and sometimes direct Brzozowski derivation
7699 * it usually tatkes less than linear time and can handle expressions generating
7700 * infinite languages.
7701 *
7702 * Returns the resulting expression or NULL in case of internal error, the
7703 * result must be freed
7704 */
7705xmlExpNodePtr
7706xmlExpExpDerive(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp, xmlExpNodePtr sub) {
7707 if ((exp == NULL) || (ctxt == NULL) || (sub == NULL))
7708 return(NULL);
7709
7710 /*
7711 * O(1) speedups
7712 */
7713 if (IS_NILLABLE(sub) && (!IS_NILLABLE(exp))) {
7714#ifdef DEBUG_DERIV
7715 printf("Sub nillable and not exp : can't subsume\n");
7716#endif
7717 return(forbiddenExp);
7718 }
7719 if (xmlExpCheckCard(exp, sub) == 0) {
7720#ifdef DEBUG_DERIV
7721 printf("sub generate longuer sequances than exp : can't subsume\n");
7722#endif
7723 return(forbiddenExp);
7724 }
7725 return(xmlExpExpDeriveInt(ctxt, exp, sub));
7726}
7727
7728/**
7729 * xmlExpSubsume:
7730 * @ctxt: the expressions context
7731 * @exp: the englobing expression
7732 * @sub: the subexpression
7733 *
7734 * Check whether @exp accepts all the languages accexpted by @sub
7735 * the input being a subexpression.
7736 *
7737 * Returns 1 if true 0 if false and -1 in case of failure.
7738 */
7739int
7740xmlExpSubsume(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp, xmlExpNodePtr sub) {
7741 xmlExpNodePtr tmp;
7742
7743 if ((exp == NULL) || (ctxt == NULL) || (sub == NULL))
7744 return(-1);
7745
7746 /*
7747 * TODO: speedup by checking the language of sub is a subset of the
7748 * language of exp
7749 */
7750 /*
7751 * O(1) speedups
7752 */
7753 if (IS_NILLABLE(sub) && (!IS_NILLABLE(exp))) {
7754#ifdef DEBUG_DERIV
7755 printf("Sub nillable and not exp : can't subsume\n");
7756#endif
7757 return(0);
7758 }
7759 if (xmlExpCheckCard(exp, sub) == 0) {
7760#ifdef DEBUG_DERIV
7761 printf("sub generate longuer sequances than exp : can't subsume\n");
7762#endif
7763 return(0);
7764 }
7765 tmp = xmlExpExpDeriveInt(ctxt, exp, sub);
7766#ifdef DEBUG_DERIV
7767 printf("Result derivation :\n");
7768 PRINT_EXP(tmp);
7769#endif
7770 if (tmp == NULL)
7771 return(-1);
7772 if (tmp == forbiddenExp)
7773 return(0);
7774 if (tmp == emptyExp)
7775 return(1);
7776 if ((tmp != NULL) && (IS_NILLABLE(tmp))) {
7777 xmlExpFree(ctxt, tmp);
7778 return(1);
7779 }
7780 xmlExpFree(ctxt, tmp);
7781 return(0);
7782}
7783
7784/************************************************************************
7785 * *
7786 * Parsing expression *
7787 * *
7788 ************************************************************************/
7789
7790static xmlExpNodePtr xmlExpParseExpr(xmlExpCtxtPtr ctxt);
7791
7792#undef CUR
7793#define CUR (*ctxt->cur)
7794#undef NEXT
7795#define NEXT ctxt->cur++;
7796#undef IS_BLANK
7797#define IS_BLANK(c) ((c == ' ') || (c == '\n') || (c == '\r') || (c == '\t'))
7798#define SKIP_BLANKS while (IS_BLANK(*ctxt->cur)) ctxt->cur++;
7799
7800static int
7801xmlExpParseNumber(xmlExpCtxtPtr ctxt) {
7802 int ret = 0;
7803
7804 SKIP_BLANKS
7805 if (CUR == '*') {
7806 NEXT
7807 return(-1);
7808 }
7809 if ((CUR < '0') || (CUR > '9'))
7810 return(-1);
7811 while ((CUR >= '0') && (CUR <= '9')) {
7812 ret = ret * 10 + (CUR - '0');
7813 NEXT
7814 }
7815 return(ret);
7816}
7817
7818static xmlExpNodePtr
7819xmlExpParseOr(xmlExpCtxtPtr ctxt) {
7820 const char *base;
7821 xmlExpNodePtr ret;
7822 const xmlChar *val;
7823
7824 SKIP_BLANKS
7825 base = ctxt->cur;
7826 if (*ctxt->cur == '(') {
7827 NEXT
7828 ret = xmlExpParseExpr(ctxt);
7829 SKIP_BLANKS
7830 if (*ctxt->cur != ')') {
7831 fprintf(stderr, "unbalanced '(' : %s\n", base);
7832 xmlExpFree(ctxt, ret);
7833 return(NULL);
7834 }
7835 NEXT;
7836 SKIP_BLANKS
7837 goto parse_quantifier;
7838 }
7839 while ((CUR != 0) && (!(IS_BLANK(CUR))) && (CUR != '(') &&
7840 (CUR != ')') && (CUR != '|') && (CUR != ',') && (CUR != '{') &&
7841 (CUR != '*') && (CUR != '+') && (CUR != '?') && (CUR != '}'))
7842 NEXT;
7843 val = xmlDictLookup(ctxt->dict, BAD_CAST base, ctxt->cur - base);
7844 if (val == NULL)
7845 return(NULL);
7846 ret = xmlExpHashGetEntry(ctxt, XML_EXP_ATOM, NULL, NULL, val, 0, 0);
7847 if (ret == NULL)
7848 return(NULL);
7849 SKIP_BLANKS
7850parse_quantifier:
7851 if (CUR == '{') {
7852 int min, max;
7853
7854 NEXT
7855 min = xmlExpParseNumber(ctxt);
7856 if (min < 0) {
7857 xmlExpFree(ctxt, ret);
7858 return(NULL);
7859 }
7860 SKIP_BLANKS
7861 if (CUR == ',') {
7862 NEXT
7863 max = xmlExpParseNumber(ctxt);
7864 SKIP_BLANKS
7865 } else
7866 max = min;
7867 if (CUR != '}') {
7868 xmlExpFree(ctxt, ret);
7869 return(NULL);
7870 }
7871 NEXT
7872 ret = xmlExpHashGetEntry(ctxt, XML_EXP_COUNT, ret, NULL, NULL,
7873 min, max);
7874 SKIP_BLANKS
7875 } else if (CUR == '?') {
7876 NEXT
7877 ret = xmlExpHashGetEntry(ctxt, XML_EXP_COUNT, ret, NULL, NULL,
7878 0, 1);
7879 SKIP_BLANKS
7880 } else if (CUR == '+') {
7881 NEXT
7882 ret = xmlExpHashGetEntry(ctxt, XML_EXP_COUNT, ret, NULL, NULL,
7883 1, -1);
7884 SKIP_BLANKS
7885 } else if (CUR == '*') {
7886 NEXT
7887 ret = xmlExpHashGetEntry(ctxt, XML_EXP_COUNT, ret, NULL, NULL,
7888 0, -1);
7889 SKIP_BLANKS
7890 }
7891 return(ret);
7892}
7893
7894
7895static xmlExpNodePtr
7896xmlExpParseSeq(xmlExpCtxtPtr ctxt) {
7897 xmlExpNodePtr ret, right;
7898
7899 ret = xmlExpParseOr(ctxt);
7900 SKIP_BLANKS
7901 while (CUR == '|') {
7902 NEXT
7903 right = xmlExpParseOr(ctxt);
7904 if (right == NULL) {
7905 xmlExpFree(ctxt, ret);
7906 return(NULL);
7907 }
7908 ret = xmlExpHashGetEntry(ctxt, XML_EXP_OR, ret, right, NULL, 0, 0);
7909 if (ret == NULL)
7910 return(NULL);
7911 }
7912 return(ret);
7913}
7914
7915static xmlExpNodePtr
7916xmlExpParseExpr(xmlExpCtxtPtr ctxt) {
7917 xmlExpNodePtr ret, right;
7918
7919 ret = xmlExpParseSeq(ctxt);
7920 SKIP_BLANKS
7921 while (CUR == ',') {
7922 NEXT
7923 right = xmlExpParseSeq(ctxt);
7924 if (right == NULL) {
7925 xmlExpFree(ctxt, ret);
7926 return(NULL);
7927 }
7928 ret = xmlExpHashGetEntry(ctxt, XML_EXP_SEQ, ret, right, NULL, 0, 0);
7929 if (ret == NULL)
7930 return(NULL);
7931 }
7932 return(ret);
7933}
7934
7935/**
7936 * xmlExpParse:
7937 * @ctxt: the expressions context
7938 * @expr: the 0 terminated string
7939 *
7940 * Minimal parser for regexps, it understand the following constructs
7941 * - string terminals
7942 * - choice operator |
7943 * - sequence operator ,
7944 * - subexpressions (...)
7945 * - usual cardinality operators + * and ?
7946 * - finite sequences { min, max }
7947 * - infinite sequences { min, * }
7948 * There is minimal checkings made especially no checking on strings values
7949 *
7950 * Returns a new expression or NULL in case of failure
7951 */
7952xmlExpNodePtr
7953xmlExpParse(xmlExpCtxtPtr ctxt, const char *expr) {
7954 xmlExpNodePtr ret;
7955
7956 ctxt->expr = expr;
7957 ctxt->cur = expr;
7958
7959 ret = xmlExpParseExpr(ctxt);
7960 SKIP_BLANKS
7961 if (*ctxt->cur != 0) {
7962 xmlExpFree(ctxt, ret);
7963 return(NULL);
7964 }
7965 return(ret);
7966}
7967
7968static void
7969xmlExpDumpInt(xmlBufferPtr buf, xmlExpNodePtr expr, int glob) {
7970 xmlExpNodePtr c;
7971
7972 if (expr == NULL) return;
7973 if (glob) xmlBufferWriteChar(buf, "(");
7974 switch (expr->type) {
7975 case XML_EXP_EMPTY:
7976 xmlBufferWriteChar(buf, "empty");
7977 break;
7978 case XML_EXP_FORBID:
7979 xmlBufferWriteChar(buf, "forbidden");
7980 break;
7981 case XML_EXP_ATOM:
7982 xmlBufferWriteCHAR(buf, expr->exp_str);
7983 break;
7984 case XML_EXP_SEQ:
7985 c = expr->exp_left;
7986 if ((c->type == XML_EXP_SEQ) || (c->type == XML_EXP_OR))
7987 xmlExpDumpInt(buf, c, 1);
7988 else
7989 xmlExpDumpInt(buf, c, 0);
7990 xmlBufferWriteChar(buf, " , ");
7991 c = expr->exp_right;
7992 if ((c->type == XML_EXP_SEQ) || (c->type == XML_EXP_OR))
7993 xmlExpDumpInt(buf, c, 1);
7994 else
7995 xmlExpDumpInt(buf, c, 0);
7996 break;
7997 case XML_EXP_OR:
7998 c = expr->exp_left;
7999 if ((c->type == XML_EXP_SEQ) || (c->type == XML_EXP_OR))
8000 xmlExpDumpInt(buf, c, 1);
8001 else
8002 xmlExpDumpInt(buf, c, 0);
8003 xmlBufferWriteChar(buf, " | ");
8004 c = expr->exp_right;
8005 if ((c->type == XML_EXP_SEQ) || (c->type == XML_EXP_OR))
8006 xmlExpDumpInt(buf, c, 1);
8007 else
8008 xmlExpDumpInt(buf, c, 0);
8009 break;
8010 case XML_EXP_COUNT: {
8011 char rep[40];
8012
8013 c = expr->exp_left;
8014 if ((c->type == XML_EXP_SEQ) || (c->type == XML_EXP_OR))
8015 xmlExpDumpInt(buf, c, 1);
8016 else
8017 xmlExpDumpInt(buf, c, 0);
8018 if ((expr->exp_min == 0) && (expr->exp_max == 1)) {
8019 rep[0] = '?';
8020 rep[1] = 0;
8021 } else if ((expr->exp_min == 0) && (expr->exp_max == -1)) {
8022 rep[0] = '*';
8023 rep[1] = 0;
8024 } else if ((expr->exp_min == 1) && (expr->exp_max == -1)) {
8025 rep[0] = '+';
8026 rep[1] = 0;
8027 } else if (expr->exp_max == expr->exp_min) {
8028 snprintf(rep, 39, "{%d}", expr->exp_min);
8029 } else if (expr->exp_max < 0) {
8030 snprintf(rep, 39, "{%d,inf}", expr->exp_min);
8031 } else {
8032 snprintf(rep, 39, "{%d,%d}", expr->exp_min, expr->exp_max);
8033 }
8034 rep[39] = 0;
8035 xmlBufferWriteChar(buf, rep);
8036 break;
8037 }
8038 default:
8039 fprintf(stderr, "Error in tree\n");
8040 }
8041 if (glob)
8042 xmlBufferWriteChar(buf, ")");
8043}
8044/**
8045 * xmlExpDump:
8046 * @buf: a buffer to receive the output
8047 * @expr: the compiled expression
8048 *
8049 * Serialize the expression as compiled to the buffer
8050 */
8051void
8052xmlExpDump(xmlBufferPtr buf, xmlExpNodePtr expr) {
8053 if ((buf == NULL) || (expr == NULL))
8054 return;
8055 xmlExpDumpInt(buf, expr, 0);
8056}
8057
8058/**
8059 * xmlExpMaxToken:
8060 * @expr: a compiled expression
8061 *
8062 * Indicate the maximum number of input a expression can accept
8063 *
8064 * Returns the maximum length or -1 in case of error
8065 */
8066int
8067xmlExpMaxToken(xmlExpNodePtr expr) {
8068 if (expr == NULL)
8069 return(-1);
8070 return(expr->c_max);
8071}
8072
8073/**
8074 * xmlExpCtxtNbNodes:
8075 * @ctxt: an expression context
8076 *
8077 * Debugging facility provides the number of allocated nodes at a that point
8078 *
8079 * Returns the number of nodes in use or -1 in case of error
8080 */
8081int
8082xmlExpCtxtNbNodes(xmlExpCtxtPtr ctxt) {
8083 if (ctxt == NULL)
8084 return(-1);
8085 return(ctxt->nb_nodes);
8086}
8087
8088/**
8089 * xmlExpCtxtNbCons:
8090 * @ctxt: an expression context
8091 *
8092 * Debugging facility provides the number of allocated nodes over lifetime
8093 *
8094 * Returns the number of nodes ever allocated or -1 in case of error
8095 */
8096int
8097xmlExpCtxtNbCons(xmlExpCtxtPtr ctxt) {
8098 if (ctxt == NULL)
8099 return(-1);
8100 return(ctxt->nb_cons);
8101}
8102
8103#endif /* LIBXML_EXPR_ENABLED */
8104#define bottom_xmlregexp
8105#include "elfgcchack.h"
8106#endif /* LIBXML_REGEXP_ENABLED */
Note: See TracBrowser for help on using the repository browser.

© 2023 Oracle
Contact – Privacy policy – Terms of Use