VirtualBox

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

Last change on this file since 9721 was 6076, checked in by vboxsync, 17 years ago

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

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette