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