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