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