| /* |
| ** 2012-11-13 |
| ** |
| ** The author disclaims copyright to this source code. In place of |
| ** a legal notice, here is a blessing: |
| ** |
| ** May you do good and not evil. |
| ** May you find forgiveness for yourself and forgive others. |
| ** May you share freely, never taking more than you give. |
| ** |
| ****************************************************************************** |
| ** |
| ** The code in this file implements a compact but reasonably |
| ** efficient regular-expression matcher for posix extended regular |
| ** expressions against UTF8 text. |
| ** |
| ** This file is an SQLite extension. It registers a single function |
| ** named "regexp(A,B)" where A is the regular expression and B is the |
| ** string to be matched. By registering this function, SQLite will also |
| ** then implement the "B regexp A" operator. Note that with the function |
| ** the regular expression comes first, but with the operator it comes |
| ** second. |
| ** |
| ** The following regular expression syntax is supported: |
| ** |
| ** X* zero or more occurrences of X |
| ** X+ one or more occurrences of X |
| ** X? zero or one occurrences of X |
| ** X{p,q} between p and q occurrences of X |
| ** (X) match X |
| ** X|Y X or Y |
| ** ^X X occurring at the beginning of the string |
| ** X$ X occurring at the end of the string |
| ** . Match any single character |
| ** \c Character c where c is one of \{}()[]|*+?. |
| ** \c C-language escapes for c in afnrtv. ex: \t or \n |
| ** \uXXXX Where XXXX is exactly 4 hex digits, unicode value XXXX |
| ** \xXX Where XX is exactly 2 hex digits, unicode value XX |
| ** [abc] Any single character from the set abc |
| ** [^abc] Any single character not in the set abc |
| ** [a-z] Any single character in the range a-z |
| ** [^a-z] Any single character not in the range a-z |
| ** \b Word boundary |
| ** \w Word character. [A-Za-z0-9_] |
| ** \W Non-word character |
| ** \d Digit |
| ** \D Non-digit |
| ** \s Whitespace character |
| ** \S Non-whitespace character |
| ** |
| ** A nondeterministic finite automaton (NFA) is used for matching, so the |
| ** performance is bounded by O(N*M) where N is the size of the regular |
| ** expression and M is the size of the input string. The matcher never |
| ** exhibits exponential behavior. Note that the X{p,q} operator expands |
| ** to p copies of X following by q-p copies of X? and that the size of the |
| ** regular expression in the O(N*M) performance bound is computed after |
| ** this expansion. |
| */ |
| #include <string.h> |
| #include <stdlib.h> |
| #include "sqlite3ext.h" |
| SQLITE_EXTENSION_INIT1 |
| |
| /* |
| ** The following #defines change the names of some functions implemented in |
| ** this file to prevent name collisions with C-library functions of the |
| ** same name. |
| */ |
| #define re_match sqlite3re_match |
| #define re_compile sqlite3re_compile |
| #define re_free sqlite3re_free |
| |
| /* The end-of-input character */ |
| #define RE_EOF 0 /* End of input */ |
| |
| /* The NFA is implemented as sequence of opcodes taken from the following |
| ** set. Each opcode has a single integer argument. |
| */ |
| #define RE_OP_MATCH 0 /* Match the one character in the argument */ |
| #define RE_OP_ANY 1 /* Match any one character. (Implements ".") */ |
| #define RE_OP_CC_INC 2 /* Beginning of a [...] character class */ |
| #define RE_OP_CC_EXC 3 /* Beginning of a [^...] character class */ |
| #define RE_OP_CC_VALUE 4 /* Single value in a character class */ |
| #define RE_OP_CC_RANGE 5 /* Range of values in a character class */ |
| #define RE_OP_WORD 6 /* Perl word character [A-Za-z0-9_] */ |
| #define RE_OP_NOTWORD 7 /* Not a perl word character */ |
| #define RE_OP_DIGIT 8 /* digit: [0-9] */ |
| #define RE_OP_NOTDIGIT 9 /* Not a digit */ |
| #define RE_OP_SPACE 10 /* space: [ \t\n\r\v\f] */ |
| #define RE_OP_NOTSPACE 11 /* Not a digit */ |
| #define RE_IMMEDIATE 12 /* OPs >= this evaluate immediately */ |
| #define RE_OP_BOUNDARY 12 /* Boundary between word and non-word */ |
| #define RE_OP_FORK 13 /* Continue to both next and opcode at iArg */ |
| #define RE_OP_GOTO 14 /* Jump to opcode at iArg */ |
| #define RE_OP_ACCEPT 15 /* Halt and indicate a successful match */ |
| |
| /* Each opcode is a "state" in the NFA */ |
| typedef unsigned short ReStateNumber; |
| |
| /* Because this is an NFA and not a DFA, multiple states can be active at |
| ** once. An instance of the following object records all active states in |
| ** 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. |
| ** |
| ** The application must serialize access to this object. The code here |
| ** is threadsafe, as long as each thread is using its own ReCompiled object. |
| ** But a single ReCompiled object is neither threadsafe nor reentrant. |
| ** |
| ** The iBegin value is the earliest possible start of the match. The |
| ** true start of the match might be later. |
| */ |
| typedef struct ReCompiled ReCompiled; |
| struct ReCompiled { |
| ReInput sIn; /* Regexp text, or match string text */ |
| const char *zErr; /* Error message to return */ |
| char *aOp; /* Operators for the virtual machine */ |
| int *aArg; /* Arguments to each operator */ |
| ReStateSet a, b; /* Used by re_match() */ |
| unsigned (*xNextChar)(ReInput*); /* Next character function */ |
| unsigned char nInit; /* Number of characters in zInit */ |
| unsigned char bFlexStart; /* Input regexp omits the initial "^" */ |
| unsigned char bKeepSpan; /* When matching, remember start and end */ |
| unsigned char bMultiBegin; /* iBegin might not be accurate */ |
| unsigned int iBegin; /* Offset to first character in the match */ |
| unsigned int iEnd; /* Offset past the end of last match char */ |
| unsigned int nState; /* Number of entries in aOp[] and aArg[] */ |
| unsigned int nAlloc; /* Slots allocated for aOp[] and aArg[] */ |
| unsigned char zInit[12]; /* Initial text to match */ |
| }; |
| |
| #if SQLITE_REGEXP_DEBUG |
| /************************************************************************ |
| ** The following interfaces are used for development and debugging only |
| ** and are commented out for deployment. |
| */ |
| #include <stdio.h> |
| #include <ctype.h> |
| |
| /* Render one character. */ |
| static char *re_char(int c){ |
| static char zBuf[20]; |
| if( isprint(c) && (c==' ' || !isspace(c)) ){ |
| sqlite3_snprintf(sizeof(zBuf),zBuf,"'%c'",c); |
| }else{ |
| sqlite3_snprintf(sizeof(zBuf),zBuf,"0x%02x",c); |
| } |
| return zBuf; |
| } |
| |
| /* |
| ** Print out a regexp program. |
| */ |
| static void re_print(ReCompiled *pRe){ |
| int i; |
| for(i=0; i<pRe->nState; i++){ |
| printf("%3d ", i); |
| switch( pRe->aOp[i] ){ |
| case RE_OP_MATCH: printf("MATCH %s\n", re_char(pRe->aArg[i])); |
| break; |
| case RE_OP_ANY: printf("ANY\n"); break; |
| case RE_OP_WORD: printf("WORD\n"); break; |
| case RE_OP_NOTWORD: printf("NOTWORD\n"); break; |
| case RE_OP_DIGIT: printf("DIGIT\n"); break; |
| case RE_OP_NOTDIGIT: printf("NOTDIGIT\n"); break; |
| case RE_OP_SPACE: printf("SPACE\n"); break; |
| case RE_OP_NOTSPACE: printf("NOTSPACE\n"); break; |
| case RE_OP_BOUNDARY: printf("BOUNDARY\n"); break; |
| case RE_OP_FORK: printf("FORK %d\n", i+pRe->aArg[i]); break; |
| case RE_OP_GOTO: printf("GOTO %d\n", i+pRe->aArg[i]); break; |
| case RE_OP_ACCEPT: printf("ACCEPT\n"); break; |
| case RE_OP_CC_INC: |
| case RE_OP_CC_EXC: { |
| printf("%s\n", pRe->aOp[i]==RE_OP_CC_INC ? "CC_INC" : "CC_EXC"); |
| int j; |
| int n = pRe->aArg[i]; |
| for(j=1; j>0 && j<n; j++){ |
| printf("%3d ... %s %s\n", i+j, |
| pRe->aOp[i+j]==RE_OP_CC_VALUE ? "VALUE" : "RANGE", |
| re_char(pRe->aArg[i+j])); |
| } |
| i += n-1; |
| break; |
| } |
| } |
| } |
| } |
| /* |
| ** Print out a ReStateSet |
| */ |
| static void restateset_print(ReStateSet *pSet){ |
| int i; |
| for(i=0; i<pSet->nState; i++){ |
| if( i ) printf(" "); |
| printf(" %2d", pSet->aState[i]); |
| } |
| } |
| /* End of debugging utilities |
| *****************************************************************************/ |
| #endif /* SQLITE_REGEXP_DEBUG */ |
| |
| /* Add a state to the given state set if it is not already there */ |
| static void re_add_state_to_set(ReStateSet *pSet, int newState){ |
| unsigned i; |
| for(i=0; i<pSet->nState; i++) if( pSet->aState[i]==newState ) return; |
| pSet->aState[pSet->nState++] = (ReStateNumber)newState; |
| } |
| |
| /* Add a state to the appropriate state set. States for immediate |
| ** evaluation are added into pRe->a. If another input token is required |
| ** before the state can be evaluated, then it is added to pRe->b. |
| */ |
| static void re_add_state(ReCompiled *pRe, int newState){ |
| ReStateSet *pSet; |
| if( pRe->aOp[newState]>=RE_IMMEDIATE ){ |
| pSet = &pRe->a; |
| }else{ |
| pSet = &pRe->b; |
| } |
| re_add_state_to_set(pSet, 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>0x10ffff ) 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=='_'; |
| } |
| |
| /* Return true if c is a "digit" character: [0-9] */ |
| static int re_digit_char(int c){ |
| return (c>='0' && c<='9'); |
| } |
| |
| /* Return true if c is a perl "space" character: [ \t\r\n\v\f] */ |
| static int re_space_char(int c){ |
| return c==' ' || c=='\t' || c=='\n' || c=='\r' || c=='\v' || c=='\f'; |
| } |
| |
| /* Interchange pRe->a and pRe->b */ |
| static void re_swap(ReCompiled *pRe){ |
| ReStateSet t = pRe->a; |
| pRe->a = pRe->b; |
| pRe->b = t; |
| } |
| |
| /* Run a compiled regular expression on the zero-terminated input |
| ** string zIn[]. Return true on a match and false if there is no match. |
| */ |
| static int re_match(ReCompiled *pRe, const unsigned char *zIn, int nIn){ |
| unsigned int i = 0; |
| int c = RE_EOF+1; |
| int rc = 0; |
| int iIdx = -1; |
| int iBegin = -1; |
| int iReset = -1; |
| ReInput *pIn = &pRe->sIn; |
| |
| pIn->z = zIn; |
| pIn->i = 0; |
| pIn->mx = nIn>=0 ? nIn : (int)strlen((char const*)zIn); |
| pRe->bMultiBegin = 0; |
| |
| /* Look for the initial prefix match, if there is one. */ |
| if( pRe->nInit ){ |
| unsigned char x = pRe->zInit[0]; |
| while( pIn->i+pRe->nInit<=pIn->mx |
| && (zIn[pIn->i]!=x || |
| strncmp((const char*)zIn+pIn->i, |
| (const char*)pRe->zInit,pRe->nInit)!=0) |
| ){ |
| pIn->i++; |
| } |
| if( pIn->i+pRe->nInit>pIn->mx ) return 0; |
| } |
| |
| re_print(pRe); |
| printf("INPUT: [%.*s]\n", nIn, zIn); |
| pRe->b.nState = 0; |
| pRe->a.nState = 0; |
| re_add_state(pRe, 0); |
| iReset = -1; |
| c = 0; |
| while(1){ |
| for(i=0; i<pRe->a.nState; i++){ |
| int x = pRe->a.aState[i]; |
| printf("%2d,%-5s %d.%d = ", pRe->sIn.i, re_char(c), i, x); |
| restateset_print(&pRe->a); |
| printf(" => "); |
| restateset_print(&pRe->b); |
| printf("\n"); |
| switch( pRe->aOp[x] ){ |
| case RE_OP_MATCH: { |
| if( pRe->aArg[x]!=c ) break; |
| /* Fall thru */ |
| } |
| case RE_OP_ANY: { |
| add_next: |
| re_add_state(pRe, x+1); |
| break; |
| } |
| case RE_OP_WORD: { |
| if( re_word_char(c) ) goto add_next; |
| break; |
| } |
| case RE_OP_NOTWORD: { |
| if( !re_word_char(c) ) goto add_next; |
| break; |
| } |
| case RE_OP_DIGIT: { |
| if( re_digit_char(c) ) goto add_next; |
| break; |
| } |
| case RE_OP_NOTDIGIT: { |
| if( !re_digit_char(c) ) goto add_next; |
| break; |
| } |
| case RE_OP_SPACE: { |
| if( re_space_char(c) ) goto add_next; |
| break; |
| } |
| case RE_OP_NOTSPACE: { |
| if( !re_space_char(c) ) goto add_next; |
| break; |
| } |
| case RE_OP_BOUNDARY: { |
| int iCur = pIn->i; |
| int cNext = pRe->xNextChar(pIn); |
| pIn->i = iCur; |
| if( re_word_char(c)!=re_word_char(cNext) ){ |
| if( iReset>=0 ) goto add_next; |
| re_add_state_to_set(&pRe->b, x); |
| } |
| break; |
| } |
| 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++){ |
| if( pRe->aOp[x+j]==RE_OP_CC_VALUE ){ |
| if( pRe->aArg[x+j]==c ){ |
| hit = 1; |
| j = -1; |
| } |
| }else{ |
| if( pRe->aArg[x+j]<=c && pRe->aArg[x+j+1]>=c ){ |
| hit = 1; |
| j = -1; |
| }else{ |
| j++; |
| } |
| } |
| } |
| if( pRe->aOp[x]==RE_OP_CC_EXC ) hit = !hit; |
| if( hit ) re_add_state(pRe, x+n); |
| break; |
| } |
| case RE_OP_FORK: { |
| re_add_state(pRe, x+1); |
| /* Fall thru */ |
| } |
| case RE_OP_GOTO: { |
| re_add_state(pRe, x+pRe->aArg[x]); |
| break; |
| } |
| case RE_OP_ACCEPT: { |
| if( !pRe->bKeepSpan ) return 1; |
| pRe->iEnd = pIn->i; |
| printf("ACCEPT %d\n", pIn->i); |
| rc = 1; |
| break; |
| } |
| } /* End of switch( pRe->aOp[x] ) */ |
| } /* End of loop over states in pRe->a.aState[] */ |
| if( iReset<0 ){ |
| if( pRe->bFlexStart ){ |
| iReset = pRe->b.nState; |
| memcpy(pRe->a.aState, pRe->b.aState, iReset*sizeof(ReStateNumber)); |
| }else{ |
| iReset = 0; |
| } |
| printf("iReset=%d\n", iReset); |
| }else if( c==RE_EOF || pRe->b.nState==0 ){ |
| break; |
| }else if( pRe->b.nState>iReset ){ |
| if( iBegin<0 ){ |
| iBegin = iIdx; |
| printf("Begin at %d\n", iIdx); |
| }else{ |
| pRe->bMultiBegin = 1; |
| printf("Another possible beginning: %d\n", iIdx); |
| } |
| } |
| re_swap(pRe); |
| pRe->b.nState = iReset; |
| iIdx = pIn->i; |
| c = pRe->xNextChar(pIn); |
| } |
| pRe->iBegin = iBegin; |
| 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 |
| ** insertion point is just prior to existing opcode iBefore. |
| */ |
| static int re_insert(ReCompiled *p, int iBefore, int op, int arg){ |
| int i; |
| if( p->nAlloc<=p->nState && re_resize(p, p->nAlloc*2) ) return 0; |
| for(i=p->nState; i>iBefore; i--){ |
| p->aOp[i] = p->aOp[i-1]; |
| p->aArg[i] = p->aArg[i-1]; |
| } |
| p->nState++; |
| p->aOp[iBefore] = (char)op; |
| p->aArg[iBefore] = arg; |
| return iBefore; |
| } |
| |
| /* Append a new opcode and argument to the end of the RE under construction. |
| */ |
| static int re_append(ReCompiled *p, int op, int arg){ |
| return re_insert(p, p->nState, op, arg); |
| } |
| |
| /* Make a copy of N opcodes starting at iStart onto the end of the RE |
| ** under construction. |
| */ |
| static void re_copy(ReCompiled *p, int iStart, int N){ |
| if( p->nState+N>=p->nAlloc && re_resize(p, p->nAlloc*2+N) ) return; |
| memcpy(&p->aOp[p->nState], &p->aOp[iStart], N*sizeof(p->aOp[0])); |
| memcpy(&p->aArg[p->nState], &p->aArg[iStart], N*sizeof(p->aArg[0])); |
| p->nState += N; |
| } |
| |
| /* Return true if c is a hexadecimal digit character: [0-9a-fA-F] |
| ** If c is a hex digit, also set *pV = (*pV)*16 + valueof(c). If |
| ** c is not a hex digit *pV is unchanged. |
| */ |
| static int re_hex(int c, int *pV){ |
| if( c>='0' && c<='9' ){ |
| c -= '0'; |
| }else if( c>='a' && c<='f' ){ |
| c -= 'a' - 10; |
| }else if( c>='A' && c<='F' ){ |
| c -= 'A' - 10; |
| }else{ |
| return 0; |
| } |
| *pV = (*pV)*16 + (c & 0xff); |
| return 1; |
| } |
| |
| /* A backslash character has been seen, read the next character and |
| ** return its interpretation. |
| */ |
| 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+4<p->sIn.mx ){ |
| 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' && p->sIn.i+2<p->sIn.mx ){ |
| const unsigned char *zIn = p->sIn.z + p->sIn.i; |
| if( re_hex(zIn[1],&v) |
| && re_hex(zIn[2],&v) |
| ){ |
| p->sIn.i += 3; |
| 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 '.': { |
| re_append(p, RE_OP_ANY, 0); |
| break; |
| } |
| case '*': { |
| if( iPrev<0 ) return "'*' without operand"; |
| re_insert(p, iPrev, RE_OP_GOTO, p->nState - iPrev + 1); |
| re_append(p, RE_OP_FORK, iPrev - p->nState + 1); |
| break; |
| } |
| case '+': { |
| if( iPrev<0 ) return "'+' without operand"; |
| re_append(p, RE_OP_FORK, iPrev - p->nState); |
| break; |
| } |
| case '?': { |
| if( iPrev<0 ) return "'?' without operand"; |
| 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; |
| } |
| default: { |
| re_append(p, RE_OP_MATCH, c); |
| break; |
| } |
| } |
| iPrev = iStart; |
| } |
| 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->a.aState); |
| sqlite3_free(pRe->b.aState); |
| 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{ |
| pRe->bFlexStart = 1; |
| } |
| pRe->sIn.z = (unsigned char*)zIn; |
| pRe->sIn.i = 0; |
| pRe->sIn.mx = (int)strlen(zIn); |
| 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"; |
| } |
| pRe->a.aState = sqlite3_malloc64( sizeof(pRe->a.aState[0])*pRe->nState ); |
| pRe->b.aState = sqlite3_malloc64( sizeof(pRe->b.aState[0])*pRe->nState ); |
| if( pRe->a.aState==0 || pRe->b.aState==0 ){ |
| re_free(pRe); |
| return "out of memory"; |
| } |
| |
| /* The following is a performance optimization. If the regex begins with |
| ** ".*" (if the input regex lacks an initial "^") and afterwards there are |
| ** one or more matching characters, enter those matching characters into |
| ** zInit[]. The re_match() routine can then search ahead in the input |
| ** string looking for the initial match without having to run the whole |
| ** regex engine over the string. Do not worry able trying to match |
| ** unicode characters beyond plane 0 - those are very rare and this is |
| ** just an optimization. */ |
| if( pRe->bFlexStart && !noCase ){ |
| for(j=0, i=0; j<sizeof(pRe->zInit)-2 && pRe->aOp[i]==RE_OP_MATCH; i++){ |
| unsigned x = pRe->aArg[i]; |
| if( x<=127 ){ |
| pRe->zInit[j++] = (unsigned char)x; |
| }else if( x<=0xfff ){ |
| pRe->zInit[j++] = (unsigned char)(0xc0 | (x>>6)); |
| pRe->zInit[j++] = 0x80 | (x&0x3f); |
| }else if( x<=0xffff ){ |
| pRe->zInit[j++] = (unsigned char)(0xd0 | (x>>12)); |
| pRe->zInit[j++] = 0x80 | ((x>>6)&0x3f); |
| pRe->zInit[j++] = 0x80 | (x&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 |
| ** the build-in REGEXP operator. The first argument to the function is the |
| ** pattern and the second argument is the string. So, the SQL statements: |
| ** |
| ** A REGEXP B |
| ** |
| ** is implemented as regexp(B,A). |
| */ |
| static void re_sql_func( |
| sqlite3_context *context, |
| int argc, |
| sqlite3_value **argv |
| ){ |
| ReCompiled *pRe; /* Compiled regular expression */ |
| const char *zPattern; /* The regular expression */ |
| const unsigned char *zStr;/* String being searched */ |
| const char *zErr; /* Compile error message */ |
| int setAux = 0; /* True to invoke sqlite3_set_auxdata() */ |
| |
| 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; |
| } |
| setAux = 1; |
| } |
| zStr = (const unsigned char*)sqlite3_value_text(argv[1]); |
| if( zStr!=0 ){ |
| sqlite3_result_int(context, re_match(pRe, zStr, -1)); |
| } |
| if( setAux ){ |
| sqlite3_set_auxdata(context, 0, pRe, (void(*)(void*))re_free); |
| } |
| } |
| |
| /* |
| ** Implementation of the regexp_test1() SQL function. |
| ** |
| ** regexp_test1(PATTERN, STRING) |
| ** |
| ** Return the part of STRING that matches PATTERN. Or return NULL |
| ** if there is no match. |
| */ |
| static void re_test1_func( |
| sqlite3_context *context, |
| int argc, |
| sqlite3_value **argv |
| ){ |
| ReCompiled *pRe; /* Compiled regular expression */ |
| const char *zPattern; /* The regular expression */ |
| const unsigned char *zStr;/* String being searched */ |
| const char *zErr; /* Compile error message */ |
| int setAux = 0; /* True to invoke sqlite3_set_auxdata() */ |
| int rc; |
| |
| 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; |
| } |
| setAux = 1; |
| } |
| zStr = (const unsigned char*)sqlite3_value_text(argv[1]); |
| if( zStr!=0 ){ |
| int iBegin, iEnd; |
| pRe->bKeepSpan = 1; |
| rc = re_match(pRe, zStr, -1); |
| if( !rc ) goto re_test1_end; |
| iBegin = pRe->iBegin; |
| iEnd = pRe->iEnd; |
| if( pRe->bMultiBegin ){ |
| pRe->bKeepSpan = 0; |
| while( re_match(pRe, zStr+iBegin, iEnd-iBegin)==0 ){ |
| if( zStr[++iBegin]>=0xc0 ){ |
| while( (zStr[iBegin]&0xc0)==0x80 ) iBegin++; |
| } |
| if( iBegin>=iEnd ) goto re_test1_end; |
| } |
| } |
| sqlite3_result_text(context, (const char*)zStr+iBegin, |
| iEnd - iBegin, SQLITE_TRANSIENT); |
| } |
| re_test1_end: |
| if( setAux ){ |
| sqlite3_set_auxdata(context, 0, pRe, (void(*)(void*))re_free); |
| } |
| } |
| |
| /* |
| ** Invoke this routine to register the regexp() function with the |
| ** SQLite database connection. |
| */ |
| #ifdef _WIN32 |
| __declspec(dllexport) |
| #endif |
| int sqlite3_regexp_init( |
| sqlite3 *db, |
| char **pzErrMsg, |
| const sqlite3_api_routines *pApi |
| ){ |
| int rc = SQLITE_OK; |
| SQLITE_EXTENSION_INIT2(pApi); |
| rc = sqlite3_create_function(db, "regexp", 2, SQLITE_UTF8, 0, |
| re_sql_func, 0, 0); |
| if( rc==SQLITE_OK ){ |
| rc = sqlite3_create_function(db, "re_test1", 2, SQLITE_UTF8, 0, |
| re_test1_func, 0, 0); |
| } |
| return rc; |
| } |
