/ Check-in [46c8c01b]
Login

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: 46c8c01b751c1ea7fc02cc35e3b5bb99dbe46c4b
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
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

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