Debian Codegraph @

ext/misc/regexp.c

raw
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.
16 **
17 ** This file is an SQLite extension. It registers a single function
18 ** named "regexp(A,B)" where A is the regular expression and B is the
19 ** string to be matched. By registering this function, SQLite will also
20 ** then implement the "B regexp A" operator. Note that with the function
21 ** the regular expression comes first, but with the operator it comes
22 ** second.
23 **
24 ** The following regular expression syntax is supported:
25 **
26 ** X* zero or more occurrences of X
27 ** X+ one or more occurrences of X
28 ** X? zero or one occurrences of X
29 ** X{p,q} between p and q occurrences of X
30 ** (X) match X
31 ** X|Y X or Y
32 ** ^X X occurring at the beginning of the string
33 ** X$ X occurring at the end of the string
34 ** . Match any single character
35 ** \c Character c where c is one of \{}()[]|*+?-.
36 ** \c C-language escapes for c in afnrtv. ex: \t or \n
37 ** \uXXXX Where XXXX is exactly 4 hex digits, unicode value XXXX
38 ** \xXX Where XX is exactly 2 hex digits, unicode value XX
39 ** [abc] Any single character from the set abc
40 ** [^abc] Any single character not in the set abc
41 ** [a-z] Any single character in the range a-z
42 ** [^a-z] Any single character not in the range a-z
43 ** \b Word boundary
44 ** \w Word character. [A-Za-z0-9_]
45 ** \W Non-word character
46 ** \d Digit
47 ** \D Non-digit
48 ** \s Whitespace character
49 ** \S Non-whitespace character
50 **
51 ** A nondeterministic finite automaton (NFA) is used for matching, so the
52 ** performance is bounded by O(N*M) where N is the size of the regular
53 ** expression and M is the size of the input string. The matcher never
54 ** exhibits exponential behavior. Note that the X{p,q} operator expands
55 ** to p copies of X following by q-p copies of X? and that the size of the
56 ** regular expression in the O(N*M) performance bound is computed after
57 ** this expansion.
58 **
59 ** To help prevent DoS attacks, the maximum size of the NFA is restricted.
60 */
61 #include <string.h>
62 #include <stdlib.h>
63 #include "sqlite3ext.h"
64 SQLITE_EXTENSION_INIT1
65
66 /*
67 ** The following #defines change the names of some functions implemented in
68 ** this file to prevent name collisions with C-library functions of the
69 ** same name.
70 */
71 #define re_match sqlite3re_match
72 #define re_compile sqlite3re_compile
73 #define re_free sqlite3re_free
74
75 /* The end-of-input character */
76 #define RE_EOF 0 /* End of input */
77 #define RE_START 0xfffffff /* Start of input - larger than an UTF-8 */
78
79 /* The NFA is implemented as sequence of opcodes taken from the following
80 ** set. Each opcode has a single integer argument.
81 */
82 #define RE_OP_MATCH 1 /* Match the one character in the argument */
83 #define RE_OP_ANY 2 /* Match any one character. (Implements ".") */
84 #define RE_OP_ANYSTAR 3 /* Special optimized version of .* */
85 #define RE_OP_FORK 4 /* Continue to both next and opcode at iArg */
86 #define RE_OP_GOTO 5 /* Jump to opcode at iArg */
87 #define RE_OP_ACCEPT 6 /* Halt and indicate a successful match */
88 #define RE_OP_CC_INC 7 /* Beginning of a [...] character class */
89 #define RE_OP_CC_EXC 8 /* Beginning of a [^...] character class */
90 #define RE_OP_CC_VALUE 9 /* Single value in a character class */
91 #define RE_OP_CC_RANGE 10 /* Range of values in a character class */
92 #define RE_OP_WORD 11 /* Perl word character [A-Za-z0-9_] */
93 #define RE_OP_NOTWORD 12 /* Not a perl word character */
94 #define RE_OP_DIGIT 13 /* digit: [0-9] */
95 #define RE_OP_NOTDIGIT 14 /* Not a digit */
96 #define RE_OP_SPACE 15 /* space: [ \t\n\r\v\f] */
97 #define RE_OP_NOTSPACE 16 /* Not a digit */
98 #define RE_OP_BOUNDARY 17 /* Boundary between word and non-word */
99 #define RE_OP_ATSTART 18 /* Currently at the start of the string */
100
101 /* Each opcode is a "state" in the NFA */
102 typedef unsigned short ReStateNumber;
103
104 /* Because this is an NFA and not a DFA, multiple states can be active at
105 ** once. An instance of the following object records all active states in
106 ** the NFA. The implementation is optimized for the common case where the
107 ** number of actives states is small.
108 */
109 typedef struct ReStateSet {
110 unsigned nState; /* Number of current states */
111 ReStateNumber *aState; /* Current states */
112 } ReStateSet;
113
114 /* An input string read one character at a time.
115 */
116 typedef struct ReInput ReInput;
117 struct ReInput {
118 const unsigned char *z; /* All text */
119 int i; /* Next byte to read */
120 int mx; /* EOF when i>=mx */
121 };
122
123 /* A compiled NFA (or an NFA that is in the process of being compiled) is
124 ** an instance of the following object.
125 */
126 typedef struct ReCompiled ReCompiled;
127 struct ReCompiled {
128 ReInput sIn; /* Regular expression text */
129 const char *zErr; /* Error message to return */
130 char *aOp; /* Operators for the virtual machine */
131 int *aArg; /* Arguments to each operator */
132 unsigned (*xNextChar)(ReInput*); /* Next character function */
133 unsigned char zInit[12]; /* Initial text to match */
134 int nInit; /* Number of bytes in zInit */
135 unsigned nState; /* Number of entries in aOp[] and aArg[] */
136 unsigned nAlloc; /* Slots allocated for aOp[] and aArg[] */
137 unsigned mxAlloc; /* Complexity limit */
138 };
139
140 /* Add a state to the given state set if it is not already there */
141 static void re_add_state(ReStateSet *pSet, int newState){
142 unsigned i;
143 for(i=0; i<pSet->nState; i++) if( pSet->aState[i]==newState ) return;
144 pSet->aState[pSet->nState++] = (ReStateNumber)newState;
145 }
146
147 /* Extract the next unicode character from *pzIn and return it. Advance
148 ** *pzIn to the first byte past the end of the character returned. To
149 ** be clear: this routine converts utf8 to unicode. This routine is
150 ** optimized for the common case where the next character is a single byte.
151 */
152 static unsigned re_next_char(ReInput *p){
153 unsigned c;
154 if( p->i>=p->mx ) return 0;
155 c = p->z[p->i++];
156 if( c>=0x80 ){
157 if( (c&0xe0)==0xc0 && p->i<p->mx && (p->z[p->i]&0xc0)==0x80 ){
158 c = (c&0x1f)<<6 | (p->z[p->i++]&0x3f);
159 if( c<0x80 ) c = 0xfffd;
160 }else if( (c&0xf0)==0xe0 && p->i+1<p->mx && (p->z[p->i]&0xc0)==0x80
161 && (p->z[p->i+1]&0xc0)==0x80 ){
162 c = (c&0x0f)<<12 | ((p->z[p->i]&0x3f)<<6) | (p->z[p->i+1]&0x3f);
163 p->i += 2;
164 if( c<=0x7ff || (c>=0xd800 && c<=0xdfff) ) c = 0xfffd;
165 }else if( (c&0xf8)==0xf0 && p->i+2<p->mx && (p->z[p->i]&0xc0)==0x80
166 && (p->z[p->i+1]&0xc0)==0x80 && (p->z[p->i+2]&0xc0)==0x80 ){
167 c = (c&0x07)<<18 | ((p->z[p->i]&0x3f)<<12) | ((p->z[p->i+1]&0x3f)<<6)
168 | (p->z[p->i+2]&0x3f);
169 p->i += 3;
170 if( c<=0xffff || c>0x10ffff ) c = 0xfffd;
171 }else{
172 c = 0xfffd;
173 }
174 }
175 return c;
176 }
177 static unsigned re_next_char_nocase(ReInput *p){
178 unsigned c = re_next_char(p);
179 if( c>='A' && c<='Z' ) c += 'a' - 'A';
180 return c;
181 }
182
183 /* Return true if c is a perl "word" character: [A-Za-z0-9_] */
184 static int re_word_char(int c){
185 return (c>='0' && c<='9') || (c>='a' && c<='z')
186 || (c>='A' && c<='Z') || c=='_';
187 }
188
189 /* Return true if c is a "digit" character: [0-9] */
190 static int re_digit_char(int c){
191 return (c>='0' && c<='9');
192 }
193
194 /* Return true if c is a perl "space" character: [ \t\r\n\v\f] */
195 static int re_space_char(int c){
196 return c==' ' || c=='\t' || c=='\n' || c=='\r' || c=='\v' || c=='\f';
197 }
198
199 /* Run a compiled regular expression on the zero-terminated input
200 ** string zIn[]. Return true on a match and false if there is no match.
201 */
202 static int re_match(ReCompiled *pRe, const unsigned char *zIn, int nIn){
203 ReStateSet aStateSet[2], *pThis, *pNext;
204 ReStateNumber aSpace[100];
205 ReStateNumber *pToFree;
206 unsigned int i = 0;
207 unsigned int iSwap = 0;
208 int c = RE_START;
209 int cPrev = 0;
210 int rc = 0;
211 ReInput in;
212
213 in.z = zIn;
214 in.i = 0;
215 in.mx = nIn>=0 ? nIn : (int)strlen((char const*)zIn);
216
217 /* Look for the initial prefix match, if there is one. */
218 if( pRe->nInit ){
219 unsigned char x = pRe->zInit[0];
220 while( in.i+pRe->nInit<=in.mx
221 && (zIn[in.i]!=x ||
222 strncmp((const char*)zIn+in.i, (const char*)pRe->zInit, pRe->nInit)!=0)
223 ){
224 in.i++;
225 }
226 if( in.i+pRe->nInit>in.mx ) return 0;
227 c = RE_START-1;
228 }
229
230 if( pRe->nState<=(sizeof(aSpace)/(sizeof(aSpace[0])*2)) ){
231 pToFree = 0;
232 aStateSet[0].aState = aSpace;
233 }else{
234 pToFree = sqlite3_malloc64( sizeof(ReStateNumber)*2*pRe->nState );
235 if( pToFree==0 ) return -1;
236 aStateSet[0].aState = pToFree;
237 }
238 aStateSet[1].aState = &aStateSet[0].aState[pRe->nState];
239 pNext = &aStateSet[1];
240 pNext->nState = 0;
241 re_add_state(pNext, 0);
242 while( c!=RE_EOF && pNext->nState>0 ){
243 cPrev = c;
244 c = pRe->xNextChar(&in);
245 pThis = pNext;
246 pNext = &aStateSet[iSwap];
247 iSwap = 1 - iSwap;
248 pNext->nState = 0;
249 for(i=0; i<pThis->nState; i++){
250 int x = pThis->aState[i];
251 switch( pRe->aOp[x] ){
252 case RE_OP_MATCH: {
253 if( pRe->aArg[x]==c ) re_add_state(pNext, x+1);
254 break;
255 }
256 case RE_OP_ATSTART: {
257 if( cPrev==RE_START ) re_add_state(pThis, x+1);
258 break;
259 }
260 case RE_OP_ANY: {
261 if( c!=0 ) re_add_state(pNext, x+1);
262 break;
263 }
264 case RE_OP_WORD: {
265 if( re_word_char(c) ) re_add_state(pNext, x+1);
266 break;
267 }
268 case RE_OP_NOTWORD: {
269 if( !re_word_char(c) && c!=0 ) re_add_state(pNext, x+1);
270 break;
271 }
272 case RE_OP_DIGIT: {
273 if( re_digit_char(c) ) re_add_state(pNext, x+1);
274 break;
275 }
276 case RE_OP_NOTDIGIT: {
277 if( !re_digit_char(c) && c!=0 ) re_add_state(pNext, x+1);
278 break;
279 }
280 case RE_OP_SPACE: {
281 if( re_space_char(c) ) re_add_state(pNext, x+1);
282 break;
283 }
284 case RE_OP_NOTSPACE: {
285 if( !re_space_char(c) && c!=0 ) re_add_state(pNext, x+1);
286 break;
287 }
288 case RE_OP_BOUNDARY: {
289 if( re_word_char(c)!=re_word_char(cPrev) ) re_add_state(pThis, x+1);
290 break;
291 }
292 case RE_OP_ANYSTAR: {
293 re_add_state(pNext, x);
294 re_add_state(pThis, x+1);
295 break;
296 }
297 case RE_OP_FORK: {
298 re_add_state(pThis, x+pRe->aArg[x]);
299 re_add_state(pThis, x+1);
300 break;
301 }
302 case RE_OP_GOTO: {
303 re_add_state(pThis, x+pRe->aArg[x]);
304 break;
305 }
306 case RE_OP_ACCEPT: {
307 rc = 1;
308 goto re_match_end;
309 }
310 case RE_OP_CC_EXC: {
311 if( c==0 ) break;
312 /* fall-through */ goto re_op_cc_inc;
313 }
314 case RE_OP_CC_INC: re_op_cc_inc: {
315 int j = 1;
316 int n = pRe->aArg[x];
317 int hit = 0;
318 for(j=1; j>0 && j<n; j++){
319 if( pRe->aOp[x+j]==RE_OP_CC_VALUE ){
320 if( pRe->aArg[x+j]==c ){
321 hit = 1;
322 j = -1;
323 }
324 }else{
325 if( pRe->aArg[x+j]<=c && pRe->aArg[x+j+1]>=c ){
326 hit = 1;
327 j = -1;
328 }else{
329 j++;
330 }
331 }
332 }
333 if( pRe->aOp[x]==RE_OP_CC_EXC ) hit = !hit;
334 if( hit ) re_add_state(pNext, x+n);
335 break;
336 }
337 }
338 }
339 }
340 for(i=0; i<pNext->nState; i++){
341 int x = pNext->aState[i];
342 while( pRe->aOp[x]==RE_OP_GOTO ) x += pRe->aArg[x];
343 if( pRe->aOp[x]==RE_OP_ACCEPT ){ rc = 1; break; }
344 }
345 re_match_end:
346 sqlite3_free(pToFree);
347 return rc;
348 }
349
350 /* Resize the opcode and argument arrays for an RE under construction.
351 */
352 static int re_resize(ReCompiled *p, unsigned int N){
353 char *aOp;
354 int *aArg;
355 if( N>p->mxAlloc ){ p->zErr = "REGEXP pattern too big"; return 1; }
356 aOp = sqlite3_realloc64(p->aOp, N*sizeof(p->aOp[0]));
357 if( aOp==0 ){ p->zErr = "out of memory"; return 1; }
358 p->aOp = aOp;
359 aArg = sqlite3_realloc64(p->aArg, N*sizeof(p->aArg[0]));
360 if( aArg==0 ){ p->zErr = "out of memory"; return 1; }
361 p->aArg = aArg;
362 p->nAlloc = N;
363 return 0;
364 }
365
366 /* Insert a new opcode and argument into an RE under construction. The
367 ** insertion point is just prior to existing opcode iBefore.
368 */
369 static int re_insert(ReCompiled *p, int iBefore, int op, int arg){
370 int i;
371 if( p->nAlloc<=p->nState && re_resize(p, p->nAlloc*2) ) return 0;
372 for(i=p->nState; i>iBefore; i--){
373 p->aOp[i] = p->aOp[i-1];
374 p->aArg[i] = p->aArg[i-1];
375 }
376 p->nState++;
377 p->aOp[iBefore] = (char)op;
378 p->aArg[iBefore] = arg;
379 return iBefore;
380 }
381
382 /* Append a new opcode and argument to the end of the RE under construction.
383 */
384 static int re_append(ReCompiled *p, int op, int arg){
385 return re_insert(p, p->nState, op, arg);
386 }
387
388 /* Make a copy of N opcodes starting at iStart onto the end of the RE
389 ** under construction.
390 */
391 static void re_copy(ReCompiled *p, int iStart, unsigned int N){
392 if( p->nState+N>=p->nAlloc && re_resize(p, p->nAlloc*2+N) ) return;
393 memcpy(&p->aOp[p->nState], &p->aOp[iStart], N*sizeof(p->aOp[0]));
394 memcpy(&p->aArg[p->nState], &p->aArg[iStart], N*sizeof(p->aArg[0]));
395 p->nState += N;
396 }
397
398 /* Return true if c is a hexadecimal digit character: [0-9a-fA-F]
399 ** If c is a hex digit, also set *pV = (*pV)*16 + valueof(c). If
400 ** c is not a hex digit *pV is unchanged.
401 */
402 static int re_hex(int c, int *pV){
403 if( c>='0' && c<='9' ){
404 c -= '0';
405 }else if( c>='a' && c<='f' ){
406 c -= 'a' - 10;
407 }else if( c>='A' && c<='F' ){
408 c -= 'A' - 10;
409 }else{
410 return 0;
411 }
412 *pV = (*pV)*16 + (c & 0xff);
413 return 1;
414 }
415
416 /* A backslash character has been seen, read the next character and
417 ** return its interpretation.
418 */
419 static unsigned re_esc_char(ReCompiled *p){
420 static const char zEsc[] = "afnrtv\\()*.+?[$^{|}]-";
421 static const char zTrans[] = "\a\f\n\r\t\v";
422 int i, v = 0;
423 char c;
424 if( p->sIn.i>=p->sIn.mx ) return 0;
425 c = p->sIn.z[p->sIn.i];
426 if( c=='u' && p->sIn.i+4<p->sIn.mx ){
427 const unsigned char *zIn = p->sIn.z + p->sIn.i;
428 if( re_hex(zIn[1],&v)
429 && re_hex(zIn[2],&v)
430 && re_hex(zIn[3],&v)
431 && re_hex(zIn[4],&v)
432 ){
433 p->sIn.i += 5;
434 return v;
435 }
436 }
437 if( c=='x' && p->sIn.i+2<p->sIn.mx ){
438 const unsigned char *zIn = p->sIn.z + p->sIn.i;
439 if( re_hex(zIn[1],&v)
440 && re_hex(zIn[2],&v)
441 ){
442 p->sIn.i += 3;
443 return v;
444 }
445 }
446 for(i=0; zEsc[i] && zEsc[i]!=c; i++){}
447 if( zEsc[i] ){
448 if( i<6 ) c = zTrans[i];
449 p->sIn.i++;
450 }else{
451 p->zErr = "unknown \\ escape";
452 }
453 return c;
454 }
455
456 /* Forward declaration */
457 static const char *re_subcompile_string(ReCompiled*);
458
459 /* Peek at the next byte of input */
460 static unsigned char rePeek(ReCompiled *p){
461 return p->sIn.i<p->sIn.mx ? p->sIn.z[p->sIn.i] : 0;
462 }
463
464 /* Compile RE text into a sequence of opcodes. Continue up to the
465 ** first unmatched ")" character, then return. If an error is found,
466 ** return a pointer to the error message string.
467 */
468 static const char *re_subcompile_re(ReCompiled *p){
469 const char *zErr;
470 int iStart, iEnd, iGoto;
471 iStart = p->nState;
472 zErr = re_subcompile_string(p);
473 if( zErr ) return zErr;
474 while( rePeek(p)=='|' ){
475 iEnd = p->nState;
476 re_insert(p, iStart, RE_OP_FORK, iEnd + 2 - iStart);
477 iGoto = re_append(p, RE_OP_GOTO, 0);
478 p->sIn.i++;
479 zErr = re_subcompile_string(p);
480 if( zErr ) return zErr;
481 p->aArg[iGoto] = p->nState - iGoto;
482 }
483 return 0;
484 }
485
486 /* Compile an element of regular expression text (anything that can be
487 ** an operand to the "|" operator). Return NULL on success or a pointer
488 ** to the error message if there is a problem.
489 */
490 static const char *re_subcompile_string(ReCompiled *p){
491 int iPrev = -1;
492 int iStart;
493 unsigned c;
494 const char *zErr;
495 while( (c = p->xNextChar(&p->sIn))!=0 ){
496 iStart = p->nState;
497 switch( c ){
498 case '|':
499 case ')': {
500 p->sIn.i--;
501 return 0;
502 }
503 case '(': {
504 zErr = re_subcompile_re(p);
505 if( zErr ) return zErr;
506 if( rePeek(p)!=')' ) return "unmatched '('";
507 p->sIn.i++;
508 break;
509 }
510 case '.': {
511 if( rePeek(p)=='*' ){
512 re_append(p, RE_OP_ANYSTAR, 0);
513 p->sIn.i++;
514 }else{
515 re_append(p, RE_OP_ANY, 0);
516 }
517 break;
518 }
519 case '*': {
520 if( iPrev<0 ) return "'*' without operand";
521 re_insert(p, iPrev, RE_OP_GOTO, p->nState - iPrev + 1);
522 re_append(p, RE_OP_FORK, iPrev - p->nState + 1);
523 break;
524 }
525 case '+': {
526 if( iPrev<0 ) return "'+' without operand";
527 re_append(p, RE_OP_FORK, iPrev - p->nState);
528 break;
529 }
530 case '?': {
531 if( iPrev<0 ) return "'?' without operand";
532 re_insert(p, iPrev, RE_OP_FORK, p->nState - iPrev+1);
533 break;
534 }
535 case '$': {
536 re_append(p, RE_OP_MATCH, RE_EOF);
537 break;
538 }
539 case '^': {
540 re_append(p, RE_OP_ATSTART, 0);
541 break;
542 }
543 case '{': {
544 unsigned int m = 0, n = 0;
545 unsigned int sz, j;
546 if( iPrev<0 ) return "'{m,n}' without operand";
547 while( (c=rePeek(p))>='0' && c<='9' ){
548 m = m*10 + c - '0';
549 if( m*2>p->mxAlloc ) return "REGEXP pattern too big";
550 p->sIn.i++;
551 }
552 n = m;
553 if( c==',' ){
554 p->sIn.i++;
555 n = 0;
556 while( (c=rePeek(p))>='0' && c<='9' ){
557 n = n*10 + c-'0';
558 if( n*2>p->mxAlloc ) return "REGEXP pattern too big";
559 p->sIn.i++;
560 }
561 }
562 if( c!='}' ) return "unmatched '{'";
563 if( n<m ) return "n less than m in '{m,n}'";
564 p->sIn.i++;
565 sz = p->nState - iPrev;
566 if( m==0 ){
567 if( n==0 ) return "both m and n are zero in '{m,n}'";
568 re_insert(p, iPrev, RE_OP_FORK, sz+1);
569 iPrev++;
570 n--;
571 }else{
572 for(j=1; j<m; j++) re_copy(p, iPrev, sz);
573 }
574 for(j=m; j<n; j++){
575 re_append(p, RE_OP_FORK, sz+1);
576 re_copy(p, iPrev, sz);
577 }
578 if( n==0 && m>0 ){
579 re_append(p, RE_OP_FORK, -(int)sz);
580 }
581 break;
582 }
583 case '[': {
584 unsigned int iFirst = p->nState;
585 if( rePeek(p)=='^' ){
586 re_append(p, RE_OP_CC_EXC, 0);
587 p->sIn.i++;
588 }else{
589 re_append(p, RE_OP_CC_INC, 0);
590 }
591 while( (c = p->xNextChar(&p->sIn))!=0 ){
592 if( c=='[' && rePeek(p)==':' ){
593 return "POSIX character classes not supported";
594 }
595 if( c=='\\' ) c = re_esc_char(p);
596 if( rePeek(p)=='-' ){
597 re_append(p, RE_OP_CC_RANGE, c);
598 p->sIn.i++;
599 c = p->xNextChar(&p->sIn);
600 if( c=='\\' ) c = re_esc_char(p);
601 re_append(p, RE_OP_CC_RANGE, c);
602 }else{
603 re_append(p, RE_OP_CC_VALUE, c);
604 }
605 if( rePeek(p)==']' ){ p->sIn.i++; break; }
606 }
607 if( c==0 ) return "unclosed '['";
608 if( p->nState>iFirst ) p->aArg[iFirst] = p->nState - iFirst;
609 break;
610 }
611 case '\\': {
612 int specialOp = 0;
613 switch( rePeek(p) ){
614 case 'b': specialOp = RE_OP_BOUNDARY; break;
615 case 'd': specialOp = RE_OP_DIGIT; break;
616 case 'D': specialOp = RE_OP_NOTDIGIT; break;
617 case 's': specialOp = RE_OP_SPACE; break;
618 case 'S': specialOp = RE_OP_NOTSPACE; break;
619 case 'w': specialOp = RE_OP_WORD; break;
620 case 'W': specialOp = RE_OP_NOTWORD; break;
621 }
622 if( specialOp ){
623 p->sIn.i++;
624 re_append(p, specialOp, 0);
625 }else{
626 c = re_esc_char(p);
627 re_append(p, RE_OP_MATCH, c);
628 }
629 break;
630 }
631 default: {
632 re_append(p, RE_OP_MATCH, c);
633 break;
634 }
635 }
636 iPrev = iStart;
637 }
638 return 0;
639 }
640
641 /* Free and reclaim all the memory used by a previously compiled
642 ** regular expression. Applications should invoke this routine once
643 ** for every call to re_compile() to avoid memory leaks.
644 */
645 static void re_free(ReCompiled *pRe){
646 if( pRe ){
647 sqlite3_free(pRe->aOp);
648 sqlite3_free(pRe->aArg);
649 sqlite3_free(pRe);
650 }
651 }
652
653 /*
654 ** Version of re_free() that accepts a pointer of type (void*). Required
655 ** to satisfy sanitizers when the re_free() function is called via a
656 ** function pointer.
657 */
658 static void re_free_voidptr(void *p){
659 re_free((ReCompiled*)p);
660 }
661
662 /*
663 ** Compile a textual regular expression in zIn[] into a compiled regular
664 ** expression suitable for us by re_match() and return a pointer to the
665 ** compiled regular expression in *ppRe. Return NULL on success or an
666 ** error message if something goes wrong.
667 */
668 static const char *re_compile(
669 ReCompiled **ppRe, /* OUT: write compiled NFA here */
670 const char *zIn, /* Input regular expression */
671 int mxRe, /* Complexity limit */
672 int noCase /* True for caseless comparisons */
673 ){
674 ReCompiled *pRe;
675 const char *zErr;
676 int i, j;
677
678 *ppRe = 0;
679 pRe = sqlite3_malloc64( sizeof(*pRe) );
680 if( pRe==0 ){
681 return "out of memory";
682 }
683 memset(pRe, 0, sizeof(*pRe));
684 pRe->xNextChar = noCase ? re_next_char_nocase : re_next_char;
685 pRe->mxAlloc = mxRe;
686 if( re_resize(pRe, 30) ){
687 zErr = pRe->zErr;
688 re_free(pRe);
689 return zErr;
690 }
691 if( zIn[0]=='^' ){
692 zIn++;
693 }else{
694 re_append(pRe, RE_OP_ANYSTAR, 0);
695 }
696 pRe->sIn.z = (unsigned char*)zIn;
697 pRe->sIn.i = 0;
698 pRe->sIn.mx = (int)strlen(zIn);
699 zErr = re_subcompile_re(pRe);
700 if( zErr ){
701 re_free(pRe);
702 return zErr;
703 }
704 if( pRe->sIn.i>=pRe->sIn.mx ){
705 re_append(pRe, RE_OP_ACCEPT, 0);
706 *ppRe = pRe;
707 }else{
708 re_free(pRe);
709 return "unrecognized character";
710 }
711
712 /* The following is a performance optimization. If the regex begins with
713 ** ".*" (if the input regex lacks an initial "^") and afterwards there are
714 ** one or more matching characters, enter those matching characters into
715 ** zInit[]. The re_match() routine can then search ahead in the input
716 ** string looking for the initial match without having to run the whole
717 ** regex engine over the string. Do not worry about trying to match
718 ** unicode characters beyond plane 0 - those are very rare and this is
719 ** just an optimization. */
720 if( pRe->aOp[0]==RE_OP_ANYSTAR && !noCase ){
721 for(j=0, i=1; j<(int)sizeof(pRe->zInit)-2 && pRe->aOp[i]==RE_OP_MATCH; i++){
722 unsigned x = pRe->aArg[i];
723 if( x<=0x7f ){
724 pRe->zInit[j++] = (unsigned char)x;
725 }else if( x<=0x7ff ){
726 pRe->zInit[j++] = (unsigned char)(0xc0 | (x>>6));
727 pRe->zInit[j++] = 0x80 | (x&0x3f);
728 }else if( x<=0xffff ){
729 pRe->zInit[j++] = (unsigned char)(0xe0 | (x>>12));
730 pRe->zInit[j++] = 0x80 | ((x>>6)&0x3f);
731 pRe->zInit[j++] = 0x80 | (x&0x3f);
732 }else{
733 break;
734 }
735 }
736 if( j>0 && pRe->zInit[j-1]==0 ) j--;
737 pRe->nInit = j;
738 }
739 return pRe->zErr;
740 }
741
742 /*
743 ** The value of LIMIT_MAX_PATTERN_LENGTH.
744 */
745 static int re_maxlen(sqlite3_context *context){
746 sqlite3 *db = sqlite3_context_db_handle(context);
747 return sqlite3_limit(db, SQLITE_LIMIT_LIKE_PATTERN_LENGTH,-1);
748 }
749
750 /*
751 ** Maximum NFA size given a maximum pattern length.
752 */
753 static int re_maxnfa(int mxlen){
754 return 75+mxlen/2;
755 }
756
757 /*
758 ** Implementation of the regexp() SQL function. This function implements
759 ** the build-in REGEXP operator. The first argument to the function is the
760 ** pattern and the second argument is the string. So, the SQL statements:
761 **
762 ** A REGEXP B
763 **
764 ** is implemented as regexp(B,A).
765 */
766 static void re_sql_func(
767 sqlite3_context *context,
768 int argc,
769 sqlite3_value **argv
770 ){
771 ReCompiled *pRe; /* Compiled regular expression */
772 const char *zPattern; /* The regular expression */
773 const unsigned char *zStr;/* String being searched */
774 const char *zErr; /* Compile error message */
775 int setAux = 0; /* True to invoke sqlite3_set_auxdata() */
776
777 (void)argc; /* Unused */
778 pRe = sqlite3_get_auxdata(context, 0);
779 if( pRe==0 ){
780 int mxLen = re_maxlen(context);
781 int nPattern;
782 zPattern = (const char*)sqlite3_value_text(argv[0]);
783 if( zPattern==0 ) return;
784 nPattern = sqlite3_value_bytes(argv[0]);
785 if( nPattern>mxLen ){
786 zErr = "REGEXP pattern too big";
787 }else{
788 zErr = re_compile(&pRe, zPattern, re_maxnfa(mxLen),
789 sqlite3_user_data(context)!=0);
790 }
791 if( zErr ){
792 re_free(pRe);
793 sqlite3_result_error(context, zErr, -1);
794 return;
795 }
796 if( pRe==0 ){
797 sqlite3_result_error_nomem(context);
798 return;
799 }
800 setAux = 1;
801 }
802 zStr = (const unsigned char*)sqlite3_value_text(argv[1]);
803 if( zStr!=0 ){
804 sqlite3_result_int(context, re_match(pRe, zStr, -1));
805 }
806 if( setAux ){
807 sqlite3_set_auxdata(context, 0, pRe, re_free_voidptr);
808 }
809 }
810
811 #if defined(SQLITE_DEBUG)
812 /*
813 ** This function is used for testing and debugging only. It is only available
814 ** if the SQLITE_DEBUG compile-time option is used.
815 **
816 ** Compile a regular expression and then convert the compiled expression into
817 ** text and return that text.
818 */
819 static void re_bytecode_func(
820 sqlite3_context *context,
821 int argc,
822 sqlite3_value **argv
823 ){
824 const char *zPattern;
825 const char *zErr;
826 ReCompiled *pRe;
827 sqlite3_str *pStr;
828 int i;
829 int n;
830 char *z;
831 static const char *ReOpName[] = {
832 "EOF",
833 "MATCH",
834 "ANY",
835 "ANYSTAR",
836 "FORK",
837 "GOTO",
838 "ACCEPT",
839 "CC_INC",
840 "CC_EXC",
841 "CC_VALUE",
842 "CC_RANGE",
843 "WORD",
844 "NOTWORD",
845 "DIGIT",
846 "NOTDIGIT",
847 "SPACE",
848 "NOTSPACE",
849 "BOUNDARY",
850 "ATSTART",
851 };
852
853 (void)argc;
854 zPattern = (const char*)sqlite3_value_text(argv[0]);
855 if( zPattern==0 ) return;
856 zErr = re_compile(&pRe, zPattern, re_maxnfa(re_maxlen(context)),
857 sqlite3_user_data(context)!=0);
858 if( zErr ){
859 re_free(pRe);
860 sqlite3_result_error(context, zErr, -1);
861 return;
862 }
863 if( pRe==0 ){
864 sqlite3_result_error_nomem(context);
865 return;
866 }
867 pStr = sqlite3_str_new(0);
868 if( pStr==0 ) goto re_bytecode_func_err;
869 if( pRe->nInit>0 ){
870 sqlite3_str_appendf(pStr, "INIT ");
871 for(i=0; i<pRe->nInit; i++){
872 sqlite3_str_appendf(pStr, "%02x", pRe->zInit[i]);
873 }
874 sqlite3_str_appendf(pStr, "\n");
875 }
876 for(i=0; (unsigned)i<pRe->nState; i++){
877 sqlite3_str_appendf(pStr, "%-8s %4d\n",
878 ReOpName[(unsigned char)pRe->aOp[i]], pRe->aArg[i]);
879 }
880 n = sqlite3_str_length(pStr);
881 z = sqlite3_str_finish(pStr);
882 if( n==0 ){
883 sqlite3_free(z);
884 }else{
885 sqlite3_result_text(context, z, n-1, sqlite3_free);
886 }
887
888 re_bytecode_func_err:
889 re_free(pRe);
890 }
891
892 #endif /* SQLITE_DEBUG */
893
894
895 /*
896 ** Invoke this routine to register the regexp() function with the
897 ** SQLite database connection.
898 */
899 #ifdef _WIN32
900 __declspec(dllexport)
901 #endif
902 int sqlite3_regexp_init(
903 sqlite3 *db,
904 char **pzErrMsg,
905 const sqlite3_api_routines *pApi
906 ){
907 int rc = SQLITE_OK;
908 SQLITE_EXTENSION_INIT2(pApi);
909 (void)pzErrMsg; /* Unused */
910 rc = sqlite3_create_function(db, "regexp", 2,
911 SQLITE_UTF8|SQLITE_INNOCUOUS|SQLITE_DETERMINISTIC,
912 0, re_sql_func, 0, 0);
913 if( rc==SQLITE_OK ){
914 /* The regexpi(PATTERN,STRING) function is a case-insensitive version
915 ** of regexp(PATTERN,STRING). */
916 rc = sqlite3_create_function(db, "regexpi", 2,
917 SQLITE_UTF8|SQLITE_INNOCUOUS|SQLITE_DETERMINISTIC,
918 (void*)db, re_sql_func, 0, 0);
919 #if defined(SQLITE_DEBUG)
920 if( rc==SQLITE_OK ){
921 rc = sqlite3_create_function(db, "regexp_bytecode", 1,
922 SQLITE_UTF8|SQLITE_INNOCUOUS|SQLITE_DETERMINISTIC,
923 0, re_bytecode_func, 0, 0);
924 }
925 #endif /* SQLITE_DEBUG */
926 }
927 return rc;
928 }