Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Bring back test_regexp changes that were made when porting to Fossil. Also fix some bugs that were introduced by the Fossil port. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
45c158b1a015e0295244982e7a61ecc5 |
User & Date: | drh 2013-01-03 19:34:46.935 |
Context
2013-01-04
| ||
14:06 | Fix the zInit[] optimization of test_regexp.c when the initial string contains 3-byte UTF8 characters. (check-in: 357231ec97 user: drh tags: trunk) | |
2013-01-03
| ||
22:22 | Merge recent trunk changes into the sessions branch. (check-in: 7e068e39b3 user: drh tags: sessions) | |
19:34 | Bring back test_regexp changes that were made when porting to Fossil. Also fix some bugs that were introduced by the Fossil port. (check-in: 45c158b1a0 user: drh tags: trunk) | |
18:07 | Improvements to column name resolution in queries with parenthesized FROM clauses. Also includes a fix for ticket [beba9cae6345a3]. (check-in: 99127a669c user: drh tags: trunk) | |
Changes
Changes to src/test_regexp.c.
︙ | ︙ | |||
83 84 85 86 87 88 89 90 91 92 93 | ** the NFA. The implementation is optimized for the common case where the ** number of actives states is small. */ typedef struct ReStateSet { unsigned nState; /* Number of current states */ ReStateNumber *aState; /* Current states */ } ReStateSet; /* A compiled NFA (or an NFA that is in the process of being compiled) is ** an instance of the following object. */ | > > > > > > > > > | > | > | | | | > | | < | | | | | | | | | > > > > > | 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 | ** the NFA. The implementation is optimized for the common case where the ** number of actives states is small. */ typedef struct ReStateSet { unsigned nState; /* Number of current states */ ReStateNumber *aState; /* Current states */ } ReStateSet; /* An input string read one character at a time. */ typedef struct ReInput ReInput; struct ReInput { const unsigned char *z; /* All text */ int i; /* Next byte to read */ int mx; /* EOF when i>=mx */ }; /* A compiled NFA (or an NFA that is in the process of being compiled) is ** an instance of the following object. */ typedef struct ReCompiled ReCompiled; struct ReCompiled { ReInput sIn; /* Regular expression text */ const char *zErr; /* Error message to return */ char *aOp; /* Operators for the virtual machine */ int *aArg; /* Arguments to each operator */ unsigned (*xNextChar)(ReInput*); /* Next character function */ char zInit[12]; /* Initial text to match */ int nInit; /* Number of characters in zInit */ unsigned nState; /* Number of entries in aOp[] and aArg[] */ unsigned nAlloc; /* Slots allocated for aOp[] and aArg[] */ }; /* Add a state to the given state set if it is not already there */ static void re_add_state(ReStateSet *pSet, int newState){ unsigned i; for(i=0; i<pSet->nState; i++) if( pSet->aState[i]==newState ) return; pSet->aState[pSet->nState++] = newState; } /* Extract the next unicode character from *pzIn and return it. Advance ** *pzIn to the first byte past the end of the character returned. To ** be clear: this routine converts utf8 to unicode. This routine is ** optimized for the common case where the next character is a single byte. */ static unsigned re_next_char(ReInput *p){ unsigned c; if( p->i>=p->mx ) return 0; c = p->z[p->i++]; if( c>0x80 ){ if( (c&0xe0)==0xc0 && p->i<p->mx && (p->z[p->i]&0xc0)==0x80 ){ c = (c&0x1f)<<6 | (p->z[p->i++]&0x3f); if( c<0x80 ) c = 0xfffd; }else if( (c&0xf0)==0xe0 && p->i+1<p->mx && (p->z[p->i]&0xc0)==0x80 && (p->z[p->i+1]&0xc0)==0x80 ){ c = (c&0x0f)<<12 | ((p->z[p->i]&0x3f)<<6) | (p->z[p->i+1]&0x3f); p->i += 2; if( c<0x3ff || (c>=0xd800 && c<=0xdfff) ) c = 0xfffd; }else if( (c&0xf8)==0xf0 && p->i+3<p->mx && (p->z[p->i]&0xc0)==0x80 && (p->z[p->i+1]&0xc0)==0x80 && (p->z[p->i+2]&0xc0)==0x80 ){ c = (c&0x07)<<18 | ((p->z[p->i]&0x3f)<<12) | ((p->z[p->i+1]&0x3f)<<6) | (p->z[p->i+2]&0x3f); p->i += 3; if( c<0xffff ) c = 0xfffd; }else{ c = 0xfffd; } } return c; } static unsigned re_next_char_nocase(ReInput *p){ unsigned c = re_next_char(p); if( c>='A' && c<='Z' ) c += 'a' - 'A'; return c; } /* Return true if c is a perl "word" character: [A-Za-z0-9_] */ static int re_word_char(int c){ return (c>='0' && c<='9') || (c>='a' && c<='z') || (c>='A' && c<='Z') || c=='_'; } |
︙ | ︙ | |||
155 156 157 158 159 160 161 | static int re_space_char(int c){ return c==' ' || c=='\t' || c=='\n' || c=='\v' || c=='\f'; } /* Run a compiled regular expression on the zero-terminated input ** string zIn[]. Return true on a match and false if there is no match. */ | | > > > > > | > | | | | | 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 | static int re_space_char(int c){ return c==' ' || c=='\t' || c=='\n' || c=='\v' || c=='\f'; } /* Run a compiled regular expression on the zero-terminated input ** string zIn[]. Return true on a match and false if there is no match. */ int re_match(ReCompiled *pRe, const unsigned char *zIn, int nIn){ ReStateSet aStateSet[2], *pThis, *pNext; ReStateNumber aSpace[100]; ReStateNumber *pToFree; unsigned int i = 0; unsigned int iSwap = 0; int c = RE_EOF+1; int cPrev = 0; int rc = 0; ReInput in; in.z = zIn; in.i = 0; in.mx = nIn>=0 ? nIn : strlen((char*)zIn); if( pRe->nInit ){ unsigned char x = pRe->zInit[0]; while( in.i+pRe->nInit<=in.mx && (zIn[in.i]!=x || memcmp(zIn+in.i, pRe->zInit, pRe->nInit)!=0) ){ in.i++; } if( in.i+pRe->nInit>in.mx ) return 0; } if( pRe->nState<=(sizeof(aSpace)/(sizeof(aSpace[0])*2)) ){ pToFree = 0; aStateSet[0].aState = aSpace; }else{ pToFree = sqlite3_malloc( sizeof(ReStateNumber)*2*pRe->nState ); if( pToFree==0 ) return -1; aStateSet[0].aState = pToFree; } aStateSet[1].aState = &aStateSet[0].aState[pRe->nState]; pNext = &aStateSet[1]; pNext->nState = 0; re_add_state(pNext, 0); while( c!=RE_EOF && pNext->nState>0 ){ cPrev = c; c = pRe->xNextChar(&in); pThis = pNext; pNext = &aStateSet[iSwap]; iSwap = 1 - iSwap; pNext->nState = 0; for(i=0; i<pThis->nState; i++){ int x = pThis->aState[i]; switch( pRe->aOp[x] ){ |
︙ | ︙ | |||
246 247 248 249 250 251 252 | } case RE_OP_GOTO: { re_add_state(pThis, x+pRe->aArg[x]); break; } case RE_OP_ACCEPT: { rc = 1; | | | 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 | } case RE_OP_GOTO: { re_add_state(pThis, x+pRe->aArg[x]); break; } case RE_OP_ACCEPT: { rc = 1; goto re_match_end; } case RE_OP_CC_INC: case RE_OP_CC_EXC: { int j = 1; int n = pRe->aArg[x]; int hit = 0; for(j=1; j>0 && j<n; j++){ |
︙ | ︙ | |||
278 279 280 281 282 283 284 | } } } } for(i=0; i<pNext->nState; i++){ if( pRe->aOp[pNext->aState[i]]==RE_OP_ACCEPT ){ rc = 1; break; } } | | | | | | 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 | } } } } for(i=0; i<pNext->nState; i++){ if( pRe->aOp[pNext->aState[i]]==RE_OP_ACCEPT ){ rc = 1; break; } } re_match_end: sqlite3_free(pToFree); return rc; } /* Resize the opcode and argument arrays for an RE under construction. */ static int re_resize(ReCompiled *p, int N){ char *aOp; int *aArg; aOp = sqlite3_realloc(p->aOp, N*sizeof(p->aOp[0])); if( aOp==0 ) return 1; p->aOp = aOp; aArg = sqlite3_realloc(p->aArg, N*sizeof(p->aArg[0])); if( aArg==0 ) return 1; p->aArg = aArg; p->nAlloc = N; return 0; } /* Insert a new opcode and argument into an RE under construction. The |
︙ | ︙ | |||
355 356 357 358 359 360 361 | /* A backslash character has been seen, read the next character and ** return its intepretation. */ static unsigned re_esc_char(ReCompiled *p){ static const char zEsc[] = "afnrtv\\()*.+?[$^{|}]"; static const char zTrans[] = "\a\f\n\r\t\v"; int i, v = 0; | | > > | > | | | | | | | | > > > > > | | | | | | | | | 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 | /* A backslash character has been seen, read the next character and ** return its intepretation. */ static unsigned re_esc_char(ReCompiled *p){ static const char zEsc[] = "afnrtv\\()*.+?[$^{|}]"; static const char zTrans[] = "\a\f\n\r\t\v"; int i, v = 0; char c; if( p->sIn.i>=p->sIn.mx ) return 0; c = p->sIn.z[p->sIn.i]; if( c=='u' && p->sIn.i+5<p->sIn.mx ){ v = 0; const unsigned char *zIn = p->sIn.z + p->sIn.i; if( re_hex(zIn[1],&v) && re_hex(zIn[2],&v) && re_hex(zIn[3],&v) && re_hex(zIn[4],&v) ){ p->sIn.i += 5; return v; } } if( c=='x' ){ v = 0; for(i=1; p->sIn.i<p->sIn.mx && re_hex(p->sIn.z[p->sIn.i+i], &v); i++){} if( i>1 ){ p->sIn.i += i; return v; } } for(i=0; zEsc[i] && zEsc[i]!=c; i++){} if( zEsc[i] ){ if( i<6 ) c = zTrans[i]; p->sIn.i++; }else{ p->zErr = "unknown \\ escape"; } return c; } /* Forward declaration */ static const char *re_subcompile_string(ReCompiled*); /* Peek at the next byte of input */ static unsigned char rePeek(ReCompiled *p){ return p->sIn.i<p->sIn.mx ? p->sIn.z[p->sIn.i] : 0; } /* Compile RE text into a sequence of opcodes. Continue up to the ** first unmatched ")" character, then return. If an error is found, ** return a pointer to the error message string. */ static const char *re_subcompile_re(ReCompiled *p){ const char *zErr; int iStart, iEnd, iGoto; iStart = p->nState; zErr = re_subcompile_string(p); if( zErr ) return zErr; while( rePeek(p)=='|' ){ iEnd = p->nState; re_insert(p, iStart, RE_OP_FORK, iEnd + 2 - iStart); iGoto = re_append(p, RE_OP_GOTO, 0); p->sIn.i++; zErr = re_subcompile_string(p); if( zErr ) return zErr; p->aArg[iGoto] = p->nState - iGoto; } return 0; } /* Compile an element of regular expression text (anything that can be ** an operand to the "|" operator). Return NULL on success or a pointer ** to the error message if there is a problem. */ static const char *re_subcompile_string(ReCompiled *p){ int iPrev = -1; int iStart; unsigned c; const char *zErr; while( (c = p->xNextChar(&p->sIn))!=0 ){ iStart = p->nState; switch( c ){ case '|': case '$': case ')': { p->sIn.i--; return 0; } case '(': { zErr = re_subcompile_re(p); if( zErr ) return zErr; if( rePeek(p)!=')' ) return "unmatched '('"; p->sIn.i++; break; } case '.': { if( rePeek(p)=='*' ){ re_append(p, RE_OP_ANYSTAR, 0); p->sIn.i++; }else{ re_append(p, RE_OP_ANY, 0); } break; } case '*': { if( iPrev<0 ) return "'*' without operand"; |
︙ | ︙ | |||
464 465 466 467 468 469 470 | re_insert(p, iPrev, RE_OP_FORK, p->nState - iPrev+1); break; } case '{': { int m = 0, n = 0; int sz, j; if( iPrev<0 ) return "'{m,n}' without operand"; | | | | | | | | | | | | | | | | 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 | re_insert(p, iPrev, RE_OP_FORK, p->nState - iPrev+1); break; } case '{': { int m = 0, n = 0; int sz, j; if( iPrev<0 ) return "'{m,n}' without operand"; while( (c=rePeek(p))>='0' && c<='9' ){ m = m*10 + c - '0'; p->sIn.i++; } n = m; if( c==',' ){ p->sIn.i++; n = 0; while( (c=rePeek(p))>='0' && c<='9' ){ n = n*10 + c-'0'; p->sIn.i++; } } if( c!='}' ) return "unmatched '{'"; if( n>0 && n<m ) return "n less than m in '{m,n}'"; p->sIn.i++; sz = p->nState - iPrev; if( m==0 ){ if( n==0 ) return "both m and n are zero in '{m,n}'"; re_insert(p, iPrev, RE_OP_FORK, sz+1); n--; }else{ for(j=1; j<m; j++) re_copy(p, iPrev, sz); } for(j=m; j<n; j++){ re_append(p, RE_OP_FORK, sz+1); re_copy(p, iPrev, sz); } if( n==0 && m>0 ){ re_append(p, RE_OP_FORK, -sz); } break; } case '[': { int iFirst = p->nState; if( rePeek(p)=='^' ){ re_append(p, RE_OP_CC_EXC, 0); p->sIn.i++; }else{ re_append(p, RE_OP_CC_INC, 0); } while( (c = p->xNextChar(&p->sIn))!=0 ){ if( c=='[' && rePeek(p)==':' ){ return "POSIX character classes not supported"; } if( c=='\\' ) c = re_esc_char(p); if( rePeek(p)=='-' ){ re_append(p, RE_OP_CC_RANGE, c); p->sIn.i++; c = p->xNextChar(&p->sIn); if( c=='\\' ) c = re_esc_char(p); re_append(p, RE_OP_CC_RANGE, c); }else{ re_append(p, RE_OP_CC_VALUE, c); } if( rePeek(p)==']' ){ p->sIn.i++; break; } } if( c==0 ) return "unclosed '['"; p->aArg[iFirst] = p->nState - iFirst; break; } case '\\': { int specialOp = 0; switch( rePeek(p) ){ case 'b': specialOp = RE_OP_BOUNDARY; break; case 'd': specialOp = RE_OP_DIGIT; break; case 'D': specialOp = RE_OP_NOTDIGIT; break; case 's': specialOp = RE_OP_SPACE; break; case 'S': specialOp = RE_OP_NOTSPACE; break; case 'w': specialOp = RE_OP_WORD; break; case 'W': specialOp = RE_OP_NOTWORD; break; } if( specialOp ){ p->sIn.i++; re_append(p, specialOp, 0); }else{ c = re_esc_char(p); re_append(p, RE_OP_MATCH, c); } break; } |
︙ | ︙ | |||
553 554 555 556 557 558 559 | return 0; } /* Free and reclaim all the memory used by a previously compiled ** regular expression. Applications should invoke this routine once ** for every call to re_compile() to avoid memory leaks. */ | | | | > | | | > | > > | | | 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 | return 0; } /* Free and reclaim all the memory used by a previously compiled ** regular expression. Applications should invoke this routine once ** for every call to re_compile() to avoid memory leaks. */ void re_free(ReCompiled *pRe){ if( pRe ){ sqlite3_free(pRe->aOp); sqlite3_free(pRe->aArg); sqlite3_free(pRe); } } /* ** Compile a textual regular expression in zIn[] into a compiled regular ** expression suitable for us by re_match() and return a pointer to the ** compiled regular expression in *ppRe. Return NULL on success or an ** error message if something goes wrong. */ const char *re_compile(ReCompiled **ppRe, const char *zIn, int noCase){ ReCompiled *pRe; const char *zErr; int i, j; *ppRe = 0; pRe = sqlite3_malloc( sizeof(*pRe) ); if( pRe==0 ){ return "out of memory"; } memset(pRe, 0, sizeof(*pRe)); pRe->xNextChar = noCase ? re_next_char_nocase : re_next_char; if( re_resize(pRe, 30) ){ re_free(pRe); return "out of memory"; } if( zIn[0]=='^' ){ zIn++; }else{ re_append(pRe, RE_OP_ANYSTAR, 0); } pRe->sIn.z = (unsigned char*)zIn; pRe->sIn.i = 0; pRe->sIn.mx = strlen((char*)pRe->sIn.z); zErr = re_subcompile_re(pRe); if( zErr ){ re_free(pRe); return zErr; } if( rePeek(pRe)=='$' && pRe->sIn.i+1>=pRe->sIn.mx ){ re_append(pRe, RE_OP_MATCH, RE_EOF); re_append(pRe, RE_OP_ACCEPT, 0); *ppRe = pRe; }else if( pRe->sIn.i>=pRe->sIn.mx ){ re_append(pRe, RE_OP_ACCEPT, 0); *ppRe = pRe; }else{ re_free(pRe); return "unrecognized character"; } if( pRe->aOp[0]==RE_OP_ANYSTAR ){ |
︙ | ︙ | |||
619 620 621 622 623 624 625 626 627 628 629 630 631 632 | pRe->zInit[j++] = 0xd0 | (x>>12); pRe->zInit[j++] = 0x80 | ((x>>6)&0x3f); pRe->zInit[j++] = 0x80 | ((x>>6)&0x3f); }else{ break; } } pRe->nInit = j; } return pRe->zErr; } /* ** Implementation of the regexp() SQL function. This function implements | > | 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 | pRe->zInit[j++] = 0xd0 | (x>>12); pRe->zInit[j++] = 0x80 | ((x>>6)&0x3f); pRe->zInit[j++] = 0x80 | ((x>>6)&0x3f); }else{ break; } } if( j>0 && pRe->zInit[j-1]==0 ) j--; pRe->nInit = j; } return pRe->zErr; } /* ** Implementation of the regexp() SQL function. This function implements |
︙ | ︙ | |||
647 648 649 650 651 652 653 | const unsigned char *zStr;/* String being searched */ const char *zErr; /* Compile error message */ pRe = sqlite3_get_auxdata(context, 0); if( pRe==0 ){ zPattern = (const char*)sqlite3_value_text(argv[0]); if( zPattern==0 ) return; | | > | | 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 | const unsigned char *zStr;/* String being searched */ const char *zErr; /* Compile error message */ pRe = sqlite3_get_auxdata(context, 0); if( pRe==0 ){ zPattern = (const char*)sqlite3_value_text(argv[0]); if( zPattern==0 ) return; zErr = re_compile(&pRe, zPattern, 0); if( zErr ){ re_free(pRe); sqlite3_result_error(context, zErr, -1); return; } if( pRe==0 ){ sqlite3_result_error_nomem(context); return; } sqlite3_set_auxdata(context, 0, pRe, (void(*)(void*))re_free); } zStr = (const unsigned char*)sqlite3_value_text(argv[1]); if( zStr!=0 ){ sqlite3_result_int(context, re_match(pRe, zStr, -1)); } } /* ** Invoke this routine in order to install the REGEXP function in an ** SQLite database connection. ** |
︙ | ︙ |