Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | Add the test_regexp.c module containing a cross-platform implementation of the REGEXP operator. |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | descendants | both | trunk |
| Files: | files | file ages | folders |
| SHA1: |
46c8c01b751c1ea7fc02cc35e3b5bb99 |
| User & Date: | drh 2012-12-31 19:18:38 |
Context
|
2012-12-31
| ||
| 20:16 | More test cases for the REGEXP operator. Fix minor bugs uncovered by these test cases. check-in: a611c750 user: drh tags: trunk | |
| 19:18 | Add the test_regexp.c module containing a cross-platform implementation of the REGEXP operator. check-in: 46c8c01b user: drh tags: trunk | |
|
2012-12-21
| ||
| 16:15 | Ensure the database size field in the db header of a backup database is set correctly. Fix for [0cfd98ee201]. check-in: ff6857b6 user: dan tags: trunk | |
Changes
Changes to Makefile.in.
366 366 $(TOP)/src/test_malloc.c \ 367 367 $(TOP)/src/test_multiplex.c \ 368 368 $(TOP)/src/test_mutex.c \ 369 369 $(TOP)/src/test_onefile.c \ 370 370 $(TOP)/src/test_osinst.c \ 371 371 $(TOP)/src/test_pcache.c \ 372 372 $(TOP)/src/test_quota.c \ 373 + $(TOP)/src/test_regexp.c \ 373 374 $(TOP)/src/test_rtree.c \ 374 375 $(TOP)/src/test_schema.c \ 375 376 $(TOP)/src/test_server.c \ 376 377 $(TOP)/src/test_superlock.c \ 377 378 $(TOP)/src/test_syscall.c \ 378 379 $(TOP)/src/test_stat.c \ 379 380 $(TOP)/src/test_tclvar.c \
Changes to Makefile.msc.
687 687 $(TOP)\src\test_malloc.c \ 688 688 $(TOP)\src\test_multiplex.c \ 689 689 $(TOP)\src\test_mutex.c \ 690 690 $(TOP)\src\test_onefile.c \ 691 691 $(TOP)\src\test_osinst.c \ 692 692 $(TOP)\src\test_pcache.c \ 693 693 $(TOP)\src\test_quota.c \ 694 + $(TOP)\src\test_regexp.c \ 694 695 $(TOP)\src\test_rtree.c \ 695 696 $(TOP)\src\test_schema.c \ 696 697 $(TOP)\src\test_server.c \ 697 698 $(TOP)\src\test_superlock.c \ 698 699 $(TOP)\src\test_syscall.c \ 699 700 $(TOP)\src\test_stat.c \ 700 701 $(TOP)\src\test_tclvar.c \
Changes to main.mk.
249 249 $(TOP)/src/test_malloc.c \ 250 250 $(TOP)/src/test_multiplex.c \ 251 251 $(TOP)/src/test_mutex.c \ 252 252 $(TOP)/src/test_onefile.c \ 253 253 $(TOP)/src/test_osinst.c \ 254 254 $(TOP)/src/test_pcache.c \ 255 255 $(TOP)/src/test_quota.c \ 256 + $(TOP)/src/test_regexp.c \ 256 257 $(TOP)/src/test_rtree.c \ 257 258 $(TOP)/src/test_schema.c \ 258 259 $(TOP)/src/test_server.c \ 259 260 $(TOP)/src/test_stat.c \ 260 261 $(TOP)/src/test_sqllog.c \ 261 262 $(TOP)/src/test_superlock.c \ 262 263 $(TOP)/src/test_syscall.c \
Changes to src/shell.c.
1475 1475 if( db==0 || SQLITE_OK!=sqlite3_errcode(db) ){ 1476 1476 fprintf(stderr,"Error: unable to open database \"%s\": %s\n", 1477 1477 p->zDbFilename, sqlite3_errmsg(db)); 1478 1478 exit(1); 1479 1479 } 1480 1480 #ifndef SQLITE_OMIT_LOAD_EXTENSION 1481 1481 sqlite3_enable_load_extension(p->db, 1); 1482 +#endif 1483 +#ifdef SQLITE_ENABLE_REGEXP 1484 + { 1485 + extern sqlite3_add_regexp_func(sqlite3*); 1486 + sqlite3_add_regexp_func(db); 1487 + } 1482 1488 #endif 1483 1489 } 1484 1490 } 1485 1491 1486 1492 /* 1487 1493 ** Do C-language style dequoting. 1488 1494 **
Changes to src/tclsqlite.c.
3680 3680 extern int Sqlitetestrtree_Init(Tcl_Interp*); 3681 3681 extern int Sqlitequota_Init(Tcl_Interp*); 3682 3682 extern int Sqlitemultiplex_Init(Tcl_Interp*); 3683 3683 extern int SqliteSuperlock_Init(Tcl_Interp*); 3684 3684 extern int SqlitetestSyscall_Init(Tcl_Interp*); 3685 3685 extern int Sqlitetestfuzzer_Init(Tcl_Interp*); 3686 3686 extern int Sqlitetestwholenumber_Init(Tcl_Interp*); 3687 + extern int Sqlitetestregexp_Init(Tcl_Interp*); 3687 3688 3688 3689 #if defined(SQLITE_ENABLE_FTS3) || defined(SQLITE_ENABLE_FTS4) 3689 3690 extern int Sqlitetestfts3_Init(Tcl_Interp *interp); 3690 3691 #endif 3691 3692 3692 3693 #ifdef SQLITE_ENABLE_ZIPVFS 3693 3694 extern int Zipvfs_Init(Tcl_Interp*); ................................................................................ 3723 3724 Sqlitetestrtree_Init(interp); 3724 3725 Sqlitequota_Init(interp); 3725 3726 Sqlitemultiplex_Init(interp); 3726 3727 SqliteSuperlock_Init(interp); 3727 3728 SqlitetestSyscall_Init(interp); 3728 3729 Sqlitetestfuzzer_Init(interp); 3729 3730 Sqlitetestwholenumber_Init(interp); 3731 + Sqlitetestregexp_Init(interp); 3730 3732 3731 3733 #if defined(SQLITE_ENABLE_FTS3) || defined(SQLITE_ENABLE_FTS4) 3732 3734 Sqlitetestfts3_Init(interp); 3733 3735 #endif 3734 3736 3735 3737 Tcl_CreateObjCommand( 3736 3738 interp, "load_testfixture_extensions", init_all_cmd, 0, 0
Added src/test_regexp.c.
1 +/* 2 +** 2012-11-13 3 +** 4 +** The author disclaims copyright to this source code. In place of 5 +** a legal notice, here is a blessing: 6 +** 7 +** May you do good and not evil. 8 +** May you find forgiveness for yourself and forgive others. 9 +** May you share freely, never taking more than you give. 10 +** 11 +****************************************************************************** 12 +** 13 +** The code in this file implements a compact but reasonably 14 +** efficient regular-expression matcher for posix extended regular 15 +** expressions against UTF8 text. The following syntax is supported: 16 +** 17 +** X* zero or more occurrences of X 18 +** X+ one or more occurrences of X 19 +** X? zero or one occurrences of X 20 +** X{p,q} between p and q occurrences of X 21 +** (X) match X 22 +** X|Y X or Y 23 +** ^X X occurring at the beginning of the string 24 +** X$ X occurring at the end of the string 25 +** . Match any single character 26 +** \c Character c where c is one of \{}()[]|*+?. 27 +** \c C-language escapes for c in afnrtv. ex: \t or \n 28 +** \uXXXX Where XXXX is exactly 4 hex digits, unicode value XXXX 29 +** \xXXX Where XXX is any number of hex digits, unicode value XXX 30 +** [abc] Any single character from the set abc 31 +** [^abc] Any single character not in the set abc 32 +** [a-z] Any single character in the range a-z 33 +** [^a-z] Any single character not in the range a-z 34 +** \b Word boundary 35 +** \w Word character. [A-Za-z0-9_] 36 +** \W Non-word character 37 +** \d Digit 38 +** \D Non-digit 39 +** \s Whitespace character 40 +** \S Non-whitespace character 41 +** 42 +** A nondeterministic finite automaton (NFA) is used for matching, so the 43 +** performance is bounded by O(N*M) where N is the size of the regular 44 +** expression and M is the size of the input string. The matcher never 45 +** exhibits exponential behavior. Note that the X{p,q} operator expands 46 +** to p copies of X following by q-p copies of X? and that the size of the 47 +** regular expression in the O(N*M) performance bound is computed after 48 +** this expansion. 49 +*/ 50 +#include <string.h> 51 +#include <stdlib.h> 52 +#include "sqlite3.h" 53 + 54 +/* The end-of-input character */ 55 +#define RE_EOF 0 /* End of input */ 56 + 57 +/* The NFA is implemented as sequence of opcodes taken from the following 58 +** set. Each opcode has a single integer argument. 59 +*/ 60 +#define RE_OP_MATCH 1 /* Match the one character in the argument */ 61 +#define RE_OP_ANY 2 /* Match any one character. (Implements ".") */ 62 +#define RE_OP_ANYSTAR 3 /* Special optimized version of .* */ 63 +#define RE_OP_FORK 4 /* Continue to both next and opcode at iArg */ 64 +#define RE_OP_GOTO 5 /* Jump to opcode at iArg */ 65 +#define RE_OP_ACCEPT 6 /* Halt and indicate a successful match */ 66 +#define RE_OP_CC_INC 7 /* Beginning of a [...] character class */ 67 +#define RE_OP_CC_EXC 8 /* Beginning of a [^...] character class */ 68 +#define RE_OP_CC_VALUE 9 /* Single value in a character class */ 69 +#define RE_OP_CC_RANGE 10 /* Range of values in a character class */ 70 +#define RE_OP_WORD 11 /* Perl word character [A-Za-z0-9_] */ 71 +#define RE_OP_NOTWORD 12 /* Not a perl word character */ 72 +#define RE_OP_DIGIT 13 /* digit: [0-9] */ 73 +#define RE_OP_NOTDIGIT 14 /* Not a digit */ 74 +#define RE_OP_SPACE 15 /* space: [ \t\n\r\v\f] */ 75 +#define RE_OP_NOTSPACE 16 /* Not a digit */ 76 +#define RE_OP_BOUNDARY 17 /* Boundary between word and non-word */ 77 + 78 +/* Each opcode is a "state" in the NFA */ 79 +typedef unsigned short ReStateNumber; 80 + 81 +/* Because this is an NFA and not a DFA, multiple states can be active at 82 +** once. An instance of the following object records all active states in 83 +** the NFA. The implementation is optimized for the common case where the 84 +** number of actives states is small. 85 +*/ 86 +typedef struct ReStateSet { 87 + unsigned nState; /* Number of current states */ 88 + ReStateNumber *aState; /* Current states */ 89 +} ReStateSet; 90 + 91 +/* A compiled NFA (or an NFA that is in the process of being compiled) is 92 +** an instance of the following object. 93 +*/ 94 +typedef struct ReCompiled { 95 + const unsigned char *zIn; /* Regular expression text */ 96 + const char *zErr; /* Error message to return */ 97 + char *aOp; /* Operators for the virtual machine */ 98 + int *aArg; /* Arguments to each operator */ 99 + char zInit[12]; /* Initial text to match */ 100 + int nInit; /* Number of characters in zInit */ 101 + unsigned nState; /* Number of entries in aOp[] and aArg[] */ 102 + unsigned nAlloc; /* Slots allocated for aOp[] and aArg[] */ 103 +} ReCompiled; 104 + 105 +/* Add a state to the given state set if it is not already there */ 106 +static void re_add_state(ReStateSet *pSet, int newState){ 107 + unsigned i; 108 + for(i=0; i<pSet->nState; i++) if( pSet->aState[i]==newState ) return; 109 + pSet->aState[pSet->nState++] = newState; 110 +} 111 + 112 +/* Extract the next unicode character from *pzIn and return it. Advance 113 +** *pzIn to the first byte past the end of the character returned. To 114 +** be clear: this routine converts utf8 to unicode. This routine is 115 +** optimized for the common case where the next character is a single byte. 116 +*/ 117 +static unsigned re_next_char(const unsigned char **pzIn){ 118 + unsigned c = **pzIn; 119 + if( c>0 ) (*pzIn)++; 120 + if( c>0x80 ){ 121 + if( (c&0xe0)==0xc0 && ((*pzIn)[0]&0xc0)==0x80 ){ 122 + c = (c&0x1f)<<6 | ((*pzIn)[0]&0x3f); 123 + (*pzIn)++; 124 + if( c<0x80 ) c = 0xfffd; 125 + }else if( (c&0xf0)==0xe0 && ((*pzIn)[0]&0xc0)==0x80 126 + && ((*pzIn)[1]&0xc0)==0x80 ){ 127 + c = (c&0x0f)<<12 | (((*pzIn)[0]&0x3f)<<6) | ((*pzIn)[1]&0x3f); 128 + *pzIn += 2; 129 + if( c<0x3ff || (c>=0xd800 && c<=0xdfff) ) c = 0xfffd; 130 + }else if( (c&0xf8)==0xf0 && ((*pzIn)[0]&0xc0)==0x80 131 + && ((*pzIn)[1]&0xc0)==0x80 && ((*pzIn)[2]&0xc0)==0x80 ){ 132 + c = (c&0x07)<<18 | (((*pzIn)[0]&0x3f)<<12) | (((*pzIn)[1]&0x3f)<<6) 133 + | ((*pzIn)[2]&0x3f); 134 + *pzIn += 3; 135 + if( c<0xffff ) c = 0xfffd; 136 + }else{ 137 + c = 0xfffd; 138 + } 139 + } 140 + return c; 141 +} 142 + 143 +/* Return true if c is a perl "word" character: [A-Za-z0-9_] */ 144 +static int re_word_char(int c){ 145 + return (c>='0' && c<='9') || (c>='a' && c<='z') 146 + || (c>='A' && c<='Z') || c=='_'; 147 +} 148 + 149 +/* Return true if c is a "digit" character: [0-9] */ 150 +static int re_digit_char(int c){ 151 + return (c>='0' && c<='9'); 152 +} 153 + 154 +/* Return true if c is a perl "space" character: [ \t\r\n\v\f] */ 155 +static int re_space_char(int c){ 156 + return c==' ' || c=='\t' || c=='\n' || c=='\v' || c=='\f'; 157 +} 158 + 159 +/* Run a compiled regular expression on the zero-terminated input 160 +** string zIn[]. Return true on a match and false if there is no match. 161 +*/ 162 +static int re_exec(ReCompiled *pRe, const unsigned char *zIn){ 163 + ReStateSet aStateSet[2], *pThis, *pNext; 164 + ReStateNumber aSpace[100]; 165 + ReStateNumber *pToFree; 166 + unsigned int i = 0; 167 + unsigned int iSwap = 0; 168 + int c = RE_EOF+1; 169 + int cPrev = 0; 170 + int rc = 0; 171 + 172 + if( pRe->nInit ){ 173 + unsigned char x = pRe->zInit[0]; 174 + while( zIn[0] && (zIn[0]!=x || memcmp(zIn, pRe->zInit, pRe->nInit)!=0) ){ 175 + zIn++; 176 + } 177 + if( zIn[0]==0 ) return 0; 178 + } 179 + if( pRe->nState<=(sizeof(aSpace)/(sizeof(aSpace[0])*2)) ){ 180 + pToFree = 0; 181 + aStateSet[0].aState = aSpace; 182 + }else{ 183 + pToFree = malloc( sizeof(ReStateNumber)*2*pRe->nState ); 184 + if( pToFree==0 ) return -1; 185 + aStateSet[0].aState = pToFree; 186 + } 187 + aStateSet[1].aState = &aStateSet[0].aState[pRe->nState]; 188 + pNext = &aStateSet[1]; 189 + pNext->nState = 0; 190 + re_add_state(pNext, 0); 191 + while( c!=RE_EOF && pNext->nState>0 ){ 192 + cPrev = c; 193 + c = re_next_char(&zIn); 194 + pThis = pNext; 195 + pNext = &aStateSet[iSwap]; 196 + iSwap = 1 - iSwap; 197 + pNext->nState = 0; 198 + for(i=0; i<pThis->nState; i++){ 199 + int x = pThis->aState[i]; 200 + switch( pRe->aOp[x] ){ 201 + case RE_OP_MATCH: { 202 + if( pRe->aArg[x]==c ) re_add_state(pNext, x+1); 203 + break; 204 + } 205 + case RE_OP_ANY: { 206 + re_add_state(pNext, x+1); 207 + break; 208 + } 209 + case RE_OP_WORD: { 210 + if( re_word_char(c) ) re_add_state(pNext, x+1); 211 + break; 212 + } 213 + case RE_OP_NOTWORD: { 214 + if( !re_word_char(c) ) re_add_state(pNext, x+1); 215 + break; 216 + } 217 + case RE_OP_DIGIT: { 218 + if( re_digit_char(c) ) re_add_state(pNext, x+1); 219 + break; 220 + } 221 + case RE_OP_NOTDIGIT: { 222 + if( !re_digit_char(c) ) re_add_state(pNext, x+1); 223 + break; 224 + } 225 + case RE_OP_SPACE: { 226 + if( re_space_char(c) ) re_add_state(pNext, x+1); 227 + break; 228 + } 229 + case RE_OP_NOTSPACE: { 230 + if( !re_space_char(c) ) re_add_state(pNext, x+1); 231 + break; 232 + } 233 + case RE_OP_BOUNDARY: { 234 + if( re_word_char(c)!=re_word_char(cPrev) ) re_add_state(pThis, x+1); 235 + break; 236 + } 237 + case RE_OP_ANYSTAR: { 238 + re_add_state(pNext, x); 239 + re_add_state(pThis, x+1); 240 + break; 241 + } 242 + case RE_OP_FORK: { 243 + re_add_state(pThis, x+pRe->aArg[x]); 244 + re_add_state(pThis, x+1); 245 + break; 246 + } 247 + case RE_OP_GOTO: { 248 + re_add_state(pThis, x+pRe->aArg[x]); 249 + break; 250 + } 251 + case RE_OP_ACCEPT: { 252 + rc = 1; 253 + goto re_exec_end; 254 + } 255 + case RE_OP_CC_INC: 256 + case RE_OP_CC_EXC: { 257 + int j = 1; 258 + int n = pRe->aArg[x]; 259 + int hit = 0; 260 + for(j=1; j>0 && j<n; j++){ 261 + if( pRe->aOp[x+j]==RE_OP_CC_VALUE ){ 262 + if( pRe->aArg[x+j]==c ){ 263 + hit = 1; 264 + j = -1; 265 + } 266 + }else{ 267 + if( pRe->aArg[x+j]<=c && pRe->aArg[x+j+1]>=c ){ 268 + hit = 1; 269 + j = -1; 270 + }else{ 271 + j++; 272 + } 273 + } 274 + } 275 + if( pRe->aOp[x]==RE_OP_CC_EXC ) hit = !hit; 276 + if( hit ) re_add_state(pNext, x+n); 277 + break; 278 + } 279 + } 280 + } 281 + } 282 + for(i=0; i<pNext->nState; i++){ 283 + if( pRe->aOp[pNext->aState[i]]==RE_OP_ACCEPT ){ rc = 1; break; } 284 + } 285 +re_exec_end: 286 + free(pToFree); 287 + return rc; 288 +} 289 + 290 +/* Resize the opcode and argument arrays for an RE under construction. 291 +*/ 292 +static int re_resize(ReCompiled *p, int N){ 293 + char *aOp; 294 + int *aArg; 295 + aOp = realloc(p->aOp, N*sizeof(p->aOp[0])); 296 + if( aOp==0 ) return 1; 297 + p->aOp = aOp; 298 + aArg = realloc(p->aArg, N*sizeof(p->aArg[0])); 299 + if( aArg==0 ) return 1; 300 + p->aArg = aArg; 301 + p->nAlloc = N; 302 + return 0; 303 +} 304 + 305 +/* Insert a new opcode and argument into an RE under construction. The 306 +** insertion point is just prior to existing opcode iBefore. 307 +*/ 308 +static int re_insert(ReCompiled *p, int iBefore, int op, int arg){ 309 + int i; 310 + if( p->nAlloc<=p->nState && re_resize(p, p->nAlloc*2) ) return 0; 311 + for(i=p->nState; i>iBefore; i--){ 312 + p->aOp[i] = p->aOp[i-1]; 313 + p->aArg[i] = p->aArg[i-1]; 314 + } 315 + p->nState++; 316 + p->aOp[iBefore] = op; 317 + p->aArg[iBefore] = arg; 318 + return iBefore; 319 +} 320 + 321 +/* Append a new opcode and argument to the end of the RE under construction. 322 +*/ 323 +static int re_append(ReCompiled *p, int op, int arg){ 324 + return re_insert(p, p->nState, op, arg); 325 +} 326 + 327 +/* Make a copy of N opcodes starting at iStart onto the end of the RE 328 +** under construction. 329 +*/ 330 +static void re_copy(ReCompiled *p, int iStart, int N){ 331 + if( p->nState+N>=p->nAlloc && re_resize(p, p->nAlloc*2+N) ) return; 332 + memcpy(&p->aOp[p->nState], &p->aOp[iStart], N*sizeof(p->aOp[0])); 333 + memcpy(&p->aArg[p->nState], &p->aArg[iStart], N*sizeof(p->aArg[0])); 334 + p->nState += N; 335 +} 336 + 337 +/* Return true if c is a hexadecimal digit character: [0-9a-fA-F] 338 +** If c is a hex digit, also set *pV = (*pV)*16 + valueof(c). If 339 +** c is not a hex digit *pV is unchanged. 340 +*/ 341 +static int re_hex(int c, int *pV){ 342 + if( c>='0' && c<='9' ){ 343 + c -= '0'; 344 + }else if( c>='a' && c<='f' ){ 345 + c -= 'a' + 10; 346 + }else if( c>='A' && c<='F' ){ 347 + c -= 'A' + 10; 348 + }else{ 349 + return 0; 350 + } 351 + *pV = (*pV)*16 + c; 352 + return 1; 353 +} 354 + 355 +/* A backslash character has been seen, read the next character and 356 +** return its intepretation. 357 +*/ 358 +static unsigned re_esc_char(ReCompiled *p){ 359 + static const char zEsc[] = "afnrtv\\()*.+?[$^{|"; 360 + static const char zTrans[] = "\a\f\n\r\t\v"; 361 + int i, v = 0; 362 + char c = p->zIn[0]; 363 + if( c=='u' ){ 364 + v = 0; 365 + if( re_hex(p->zIn[1],&v) 366 + && re_hex(p->zIn[2],&v) 367 + && re_hex(p->zIn[3],&v) 368 + && re_hex(p->zIn[4],&v) 369 + ){ 370 + p->zIn += 5; 371 + return v; 372 + } 373 + } 374 + if( c=='x' ){ 375 + v = 0; 376 + for(i=1; re_hex(p->zIn[i], &v); i++){} 377 + if( i>1 ){ 378 + p->zIn += i; 379 + return v; 380 + } 381 + } 382 + for(i=0; zEsc[i] && zEsc[i]!=c; i++){} 383 + if( zEsc[i] ){ 384 + if( c<6 ) c = zTrans[i]; 385 + p->zIn++; 386 + }else{ 387 + p->zErr = "unknown \\ escape"; 388 + } 389 + return c; 390 +} 391 + 392 +/* Forward declaration */ 393 +static const char *re_subcompile_string(ReCompiled*); 394 + 395 +/* Compile RE text into a sequence of opcodes. Continue up to the 396 +** first unmatched ")" character, then return. If an error is found, 397 +** return a pointer to the error message string. 398 +*/ 399 +static const char *re_subcompile_re(ReCompiled *p){ 400 + const char *zErr; 401 + int iStart, iEnd, iGoto; 402 + iStart = p->nState; 403 + zErr = re_subcompile_string(p); 404 + if( zErr ) return zErr; 405 + while( p->zIn[0]=='|' ){ 406 + iEnd = p->nState; 407 + re_insert(p, iStart, RE_OP_FORK, iEnd + 2 - iStart); 408 + iGoto = re_append(p, RE_OP_GOTO, 0); 409 + p->zIn++; 410 + zErr = re_subcompile_string(p); 411 + if( zErr ) return zErr; 412 + p->aArg[iGoto] = p->nState - iGoto; 413 + } 414 + return 0; 415 +} 416 + 417 +/* Compile an element of regular expression text (anything that can be 418 +** an operand to the "|" operator). Return NULL on success or a pointer 419 +** to the error message if there is a problem. 420 +*/ 421 +static const char *re_subcompile_string(ReCompiled *p){ 422 + int iPrev = -1; 423 + int iStart; 424 + unsigned c; 425 + const char *zErr; 426 + while( (c = re_next_char(&p->zIn))!=0 ){ 427 + iStart = p->nState; 428 + switch( c ){ 429 + case '|': 430 + case '$': 431 + case ')': { 432 + p->zIn--; 433 + return 0; 434 + } 435 + case '(': { 436 + zErr = re_subcompile_re(p); 437 + if( zErr ) return zErr; 438 + if( p->zIn[0]!=')' ) return "unmatched '('"; 439 + p->zIn++; 440 + break; 441 + } 442 + case '.': { 443 + if( p->zIn[0]=='*' ){ 444 + re_append(p, RE_OP_ANYSTAR, 0); 445 + p->zIn++; 446 + }else{ 447 + re_append(p, RE_OP_ANY, 0); 448 + } 449 + break; 450 + } 451 + case '*': { 452 + if( iPrev<0 ) return "'*' without operand"; 453 + re_insert(p, iPrev, RE_OP_GOTO, p->nState - iPrev + 1); 454 + re_append(p, RE_OP_FORK, iPrev - p->nState + 1); 455 + break; 456 + } 457 + case '+': { 458 + if( iPrev<0 ) return "'+' without operand"; 459 + re_append(p, RE_OP_FORK, iPrev - p->nState); 460 + break; 461 + } 462 + case '?': { 463 + if( iPrev<0 ) return "'?' without operand"; 464 + re_insert(p, iPrev, RE_OP_FORK, p->nState - iPrev+1); 465 + break; 466 + } 467 + case '{': { 468 + int m = 0, n = 0; 469 + int sz, j; 470 + if( iPrev<0 ) return "'{m,n}' without operand"; 471 + while( (c=p->zIn[0])>='0' && c<='9' ){ m = m*10 + c - '0'; p->zIn++; } 472 + n = m; 473 + if( c==',' ){ 474 + p->zIn++; 475 + n = 0; 476 + while( (c=p->zIn[0])>='0' && c<='9' ){ n = n*10 + c - '0'; p->zIn++; } 477 + } 478 + if( c!='}' ) return "unmatched '{'"; 479 + if( n>0 && n<m ) return "n less than m in '{m,n}'"; 480 + p->zIn++; 481 + sz = p->nState - iPrev; 482 + if( m==0 ){ 483 + if( n==0 ) return "both m and n are zero in '{m,n}'"; 484 + re_insert(p, iPrev, RE_OP_FORK, sz+1); 485 + n--; 486 + }else{ 487 + for(j=1; j<m; j++) re_copy(p, iPrev, sz); 488 + } 489 + for(j=m; j<n; j++){ 490 + re_append(p, RE_OP_FORK, sz+1); 491 + re_copy(p, iPrev, sz); 492 + } 493 + if( n==0 && m>0 ){ 494 + re_append(p, RE_OP_FORK, -sz); 495 + } 496 + break; 497 + } 498 + case '[': { 499 + int iFirst = p->nState; 500 + if( p->zIn[0]=='^' ){ 501 + re_append(p, RE_OP_CC_EXC, 0); 502 + p->zIn++; 503 + }else{ 504 + re_append(p, RE_OP_CC_INC, 0); 505 + } 506 + while( (c = re_next_char(&p->zIn))!=0 ){ 507 + if( c=='[' && p->zIn[0]==':' ){ 508 + return "POSIX character classes not supported"; 509 + } 510 + if( c=='\\' ) c = re_esc_char(p); 511 + if( p->zIn[0]=='-' && p->zIn[1] ){ 512 + re_append(p, RE_OP_CC_RANGE, c); 513 + p->zIn++; 514 + c = re_next_char(&p->zIn); 515 + if( c=='\\' ) c = re_esc_char(p); 516 + re_append(p, RE_OP_CC_RANGE, c); 517 + }else{ 518 + re_append(p, RE_OP_CC_VALUE, c); 519 + } 520 + if( p->zIn[0]==']' ){ p->zIn++; break; } 521 + } 522 + if( c==0 ) return "unclosed '['"; 523 + p->aArg[iFirst] = p->nState - iFirst; 524 + break; 525 + } 526 + case '\\': { 527 + int specialOp = 0; 528 + switch( p->zIn[0] ){ 529 + case 'b': specialOp = RE_OP_BOUNDARY; break; 530 + case 'd': specialOp = RE_OP_DIGIT; break; 531 + case 'D': specialOp = RE_OP_NOTDIGIT; break; 532 + case 's': specialOp = RE_OP_SPACE; break; 533 + case 'S': specialOp = RE_OP_NOTSPACE; break; 534 + case 'w': specialOp = RE_OP_WORD; break; 535 + case 'W': specialOp = RE_OP_NOTWORD; break; 536 + } 537 + if( specialOp ){ 538 + p->zIn++; 539 + re_append(p, specialOp, 0); 540 + }else{ 541 + c = re_esc_char(p); 542 + re_append(p, RE_OP_MATCH, c); 543 + } 544 + break; 545 + } 546 + default: { 547 + re_append(p, RE_OP_MATCH, c); 548 + break; 549 + } 550 + } 551 + iPrev = iStart; 552 + } 553 + return 0; 554 +} 555 + 556 +/* Free and reclaim all the memory used by a previously compiled 557 +** regular expression. Applications should invoke this routine once 558 +** for every call to re_compile() to avoid memory leaks. 559 +*/ 560 +static void re_free(ReCompiled *pRe){ 561 + if( pRe ){ 562 + free(pRe->aOp); 563 + free(pRe->aArg); 564 + } 565 +} 566 + 567 +/* 568 +** Compile a textual regular expression in zIn[] into a compiled regular 569 +** expression suitable for us by re_exec() and return a pointer to the 570 +** compiled regular expression in *ppRe. Return NULL on success or an 571 +** error message if something goes wrong. 572 +*/ 573 +static const char *re_compile(ReCompiled **ppRe, const char *zIn){ 574 + ReCompiled *pRe; 575 + const char *zErr; 576 + int i, j; 577 + 578 + *ppRe = 0; 579 + pRe = malloc( sizeof(*pRe) ); 580 + if( pRe==0 ){ 581 + return "out of memory"; 582 + } 583 + memset(pRe, 0, sizeof(*pRe)); 584 + if( re_resize(pRe, 30) ){ 585 + re_free(pRe); 586 + return "out of memory"; 587 + } 588 + if( zIn[0]=='^' ){ 589 + zIn++; 590 + }else{ 591 + re_append(pRe, RE_OP_ANYSTAR, 0); 592 + } 593 + pRe->zIn = (unsigned char*)zIn; 594 + zErr = re_subcompile_re(pRe); 595 + if( zErr ){ 596 + re_free(pRe); 597 + return zErr; 598 + } 599 + if( pRe->zIn[0]=='$' && pRe->zIn[1]==0 ){ 600 + re_append(pRe, RE_OP_MATCH, RE_EOF); 601 + re_append(pRe, RE_OP_ACCEPT, 0); 602 + *ppRe = pRe; 603 + }else if( pRe->zIn[0]==0 ){ 604 + re_append(pRe, RE_OP_ACCEPT, 0); 605 + *ppRe = pRe; 606 + }else{ 607 + re_free(pRe); 608 + return "unrecognized character"; 609 + } 610 + if( pRe->aOp[0]==RE_OP_ANYSTAR ){ 611 + for(j=0, i=1; j<sizeof(pRe->zInit)-2 && pRe->aOp[i]==RE_OP_MATCH; i++){ 612 + unsigned x = pRe->aArg[i]; 613 + if( x<=127 ){ 614 + pRe->zInit[j++] = x; 615 + }else if( x<=0xfff ){ 616 + pRe->zInit[j++] = 0xc0 | (x>>6); 617 + pRe->zInit[j++] = 0x80 | (x&0x3f); 618 + }else if( x<=0xffff ){ 619 + pRe->zInit[j++] = 0xd0 | (x>>12); 620 + pRe->zInit[j++] = 0x80 | ((x>>6)&0x3f); 621 + pRe->zInit[j++] = 0x80 | ((x>>6)&0x3f); 622 + }else{ 623 + break; 624 + } 625 + } 626 + pRe->nInit = j; 627 + } 628 + return pRe->zErr; 629 +} 630 + 631 +/* 632 +** Implementation of the regexp() SQL function. This function implements 633 +** the build-in REGEXP operator. The first argument to the function is the 634 +** pattern and the second argument is the string. So, the SQL statements: 635 +** 636 +** A REGEXP B 637 +** 638 +** is implemented as regexp(B,A). 639 +*/ 640 +static void re_sql_func( 641 + sqlite3_context *context, 642 + int argc, 643 + sqlite3_value **argv 644 +){ 645 + ReCompiled *pRe; /* Compiled regular expression */ 646 + const char *zPattern; /* The regular expression */ 647 + const unsigned char *zStr;/* String being searched */ 648 + const char *zErr; /* Compile error message */ 649 + 650 + pRe = sqlite3_get_auxdata(context, 0); 651 + if( pRe==0 ){ 652 + zPattern = (const char*)sqlite3_value_text(argv[0]); 653 + if( zPattern==0 ) return; 654 + zErr = re_compile(&pRe, zPattern); 655 + if( zErr ){ 656 + sqlite3_result_error(context, zErr, -1); 657 + return; 658 + } 659 + if( pRe==0 ){ 660 + sqlite3_result_error_nomem(context); 661 + return; 662 + } 663 + sqlite3_set_auxdata(context, 0, pRe, (void(*)(void*))re_free); 664 + } 665 + zStr = (const unsigned char*)sqlite3_value_text(argv[1]); 666 + if( zStr!=0 ){ 667 + sqlite3_result_int(context, re_exec(pRe, zStr)); 668 + } 669 +} 670 + 671 +/* 672 +** Invoke this routine in order to install the REGEXP function in an 673 +** SQLite database connection. 674 +** 675 +** Use: 676 +** 677 +** sqlite3_auto_extension(sqlite3_add_regexp_func); 678 +** 679 +** to cause this extension to be automatically loaded into each new 680 +** database connection. 681 +*/ 682 +int sqlite3_add_regexp_func(sqlite3 *db){ 683 + return sqlite3_create_function(db, "regexp", 2, SQLITE_UTF8, 0, 684 + re_sql_func, 0, 0); 685 +} 686 + 687 + 688 +/***************************** Test Code ***********************************/ 689 +#ifdef SQLITE_TEST 690 +#include <tcl.h> 691 +extern int getDbPointer(Tcl_Interp *interp, const char *zA, sqlite3 **ppDb); 692 + 693 +/* Implementation of the TCL command: 694 +** 695 +** sqlite3_add_regexp_func $DB 696 +*/ 697 +static int tclSqlite3AddRegexpFunc( 698 + void * clientData, 699 + Tcl_Interp *interp, 700 + int objc, 701 + Tcl_Obj *CONST objv[] 702 +){ 703 + sqlite3 *db; 704 + if( objc!=2 ){ 705 + Tcl_WrongNumArgs(interp, 1, objv, "DB"); 706 + return TCL_ERROR; 707 + } 708 + if( getDbPointer(interp, Tcl_GetString(objv[1]), &db) ) return TCL_ERROR; 709 + sqlite3_add_regexp_func(db); 710 + return TCL_OK; 711 +} 712 + 713 +/* Register the sqlite3_add_regexp_func TCL command with the TCL interpreter. 714 +*/ 715 +int Sqlitetestregexp_Init(Tcl_Interp *interp){ 716 + Tcl_CreateObjCommand(interp, "sqlite3_add_regexp_func", 717 + tclSqlite3AddRegexpFunc, 0, 0); 718 + return TCL_OK; 719 +} 720 +#endif /* SQLITE_TEST */ 721 +/**************************** End Of Test Code *******************************/
Added test/regexp1.test.
1 +# 2012 December 31 2 +# 3 +# The author disclaims copyright to this source code. In place of 4 +# a legal notice, here is a blessing: 5 +# 6 +# May you do good and not evil. 7 +# May you find forgiveness for yourself and forgive others. 8 +# May you share freely, never taking more than you give. 9 +# 10 +#*********************************************************************** 11 +# 12 +# This file implements test for the REGEXP operator in test_regexp.c. 13 +# 14 + 15 +set testdir [file dirname $argv0] 16 +source $testdir/tester.tcl 17 + 18 +do_test regexp1-1.1 { 19 + sqlite3_add_regexp_func db 20 + db eval { 21 + CREATE TABLE t1(x INTEGER PRIMARY KEY, y TEXT); 22 + INSERT INTO t1 VALUES(1, 'For since by man came death,'); 23 + INSERT INTO t1 VALUES(2, 'by man came also the resurrection of the dead.'); 24 + INSERT INTO t1 VALUES(3, 'For as in Adam all die,'); 25 + INSERT INTO t1 VALUES(4, 'even so in Christ shall all be made alive.'); 26 + 27 + SELECT x FROM t1 WHERE y REGEXP '^For ' ORDER BY x; 28 + } 29 +} {1 3} 30 + 31 +do_execsql_test regexp1-1.2 { 32 + SELECT x FROM t1 WHERE y REGEXP 'by|in' ORDER BY x; 33 +} {1 2 3 4} 34 +do_execsql_test regexp1-1.3 { 35 + SELECT x FROM t1 WHERE y REGEXP 'by|Christ' ORDER BY x; 36 +} {1 2 4} 37 +do_execsql_test regexp1-1.4 { 38 + SELECT x FROM t1 WHERE y REGEXP 'shal+ al+' ORDER BY x; 39 +} {4} 40 +do_execsql_test regexp1-1.5 { 41 + SELECT x FROM t1 WHERE y REGEXP 'shall x*y*z*all' ORDER BY x; 42 +} {4} 43 +do_execsql_test regexp1-1.6 { 44 + SELECT x FROM t1 WHERE y REGEXP 'shallx?y? ?z?all' ORDER BY x; 45 +} {4} 46 +do_execsql_test regexp1-1.7 { 47 + SELECT x FROM t1 WHERE y REGEXP 'r{2}' ORDER BY x; 48 +} {2} 49 +do_execsql_test regexp1-1.8 { 50 + SELECT x FROM t1 WHERE y REGEXP 'r{3}' ORDER BY x; 51 +} {} 52 +do_execsql_test regexp1-1.9 { 53 + SELECT x FROM t1 WHERE y REGEXP 'r{1}' ORDER BY x; 54 +} {1 2 3 4} 55 +do_execsql_test regexp1-1.10 { 56 + SELECT x FROM t1 WHERE y REGEXP 'ur{2,10}e' ORDER BY x; 57 +} {2} 58 +do_execsql_test regexp1-1.11 { 59 + SELECT x FROM t1 WHERE y REGEXP '[Aa]dam' ORDER BY x; 60 +} {3} 61 +do_execsql_test regexp1-1.12 { 62 + SELECT x FROM t1 WHERE y REGEXP '[^Aa]dam' ORDER BY x; 63 +} {} 64 +do_execsql_test regexp1-1.13 { 65 + SELECT x FROM t1 WHERE y REGEXP '[^b-zB-Z]dam' ORDER BY x; 66 +} {3} 67 +do_execsql_test regexp1-1.14 { 68 + SELECT x FROM t1 WHERE y REGEXP 'alive' ORDER BY x; 69 +} {4} 70 +do_execsql_test regexp1-1.15 { 71 + SELECT x FROM t1 WHERE y REGEXP '^alive' ORDER BY x; 72 +} {} 73 +do_execsql_test regexp1-1.16 { 74 + SELECT x FROM t1 WHERE y REGEXP 'alive$' ORDER BY x; 75 +} {} 76 +do_execsql_test regexp1-1.17 { 77 + SELECT x FROM t1 WHERE y REGEXP 'alive.$' ORDER BY x; 78 +} {4} 79 +do_execsql_test regexp1-1.18 { 80 + SELECT x FROM t1 WHERE y REGEXP 'alive\.$' ORDER BY x; 81 +} {4} 82 + 83 + 84 +finish_test
Changes to tool/build-shell.sh.
11 11 make sqlite3.c 12 12 gcc -o sqlite3 -g -Os -I. \ 13 13 -DSQLITE_THREADSAFE=0 \ 14 14 -DSQLITE_ENABLE_VFSTRACE \ 15 15 -DSQLITE_ENABLE_STAT3 \ 16 16 -DSQLITE_ENABLE_FTS4 \ 17 17 -DSQLITE_ENABLE_RTREE \ 18 + -DSQLITE_ENABLE_REGEXP \ 18 19 -DHAVE_READLINE \ 19 20 -DHAVE_USLEEP=1 \ 20 21 ../sqlite/src/shell.c ../sqlite/src/test_vfstrace.c \ 22 + ../sqlite/src/test_regexp.c \ 21 23 sqlite3.c -ldl -lreadline -lncurses