/ Hex Artifact Content
Login

Artifact c24ae2a0de64eb9dfa1dd77b77448b1d794cd395:


0000: 2f 2a 0a 2a 2a 20 32 30 31 32 2d 31 31 2d 31 33  /*.** 2012-11-13
0010: 0a 2a 2a 0a 2a 2a 20 54 68 65 20 61 75 74 68 6f  .**.** The autho
0020: 72 20 64 69 73 63 6c 61 69 6d 73 20 63 6f 70 79  r disclaims copy
0030: 72 69 67 68 74 20 74 6f 20 74 68 69 73 20 73 6f  right to this so
0040: 75 72 63 65 20 63 6f 64 65 2e 20 20 49 6e 20 70  urce code.  In p
0050: 6c 61 63 65 20 6f 66 0a 2a 2a 20 61 20 6c 65 67  lace of.** a leg
0060: 61 6c 20 6e 6f 74 69 63 65 2c 20 68 65 72 65 20  al notice, here 
0070: 69 73 20 61 20 62 6c 65 73 73 69 6e 67 3a 0a 2a  is a blessing:.*
0080: 2a 0a 2a 2a 20 20 20 20 4d 61 79 20 79 6f 75 20  *.**    May you 
0090: 64 6f 20 67 6f 6f 64 20 61 6e 64 20 6e 6f 74 20  do good and not 
00a0: 65 76 69 6c 2e 0a 2a 2a 20 20 20 20 4d 61 79 20  evil..**    May 
00b0: 79 6f 75 20 66 69 6e 64 20 66 6f 72 67 69 76 65  you find forgive
00c0: 6e 65 73 73 20 66 6f 72 20 79 6f 75 72 73 65 6c  ness for yoursel
00d0: 66 20 61 6e 64 20 66 6f 72 67 69 76 65 20 6f 74  f and forgive ot
00e0: 68 65 72 73 2e 0a 2a 2a 20 20 20 20 4d 61 79 20  hers..**    May 
00f0: 79 6f 75 20 73 68 61 72 65 20 66 72 65 65 6c 79  you share freely
0100: 2c 20 6e 65 76 65 72 20 74 61 6b 69 6e 67 20 6d  , never taking m
0110: 6f 72 65 20 74 68 61 6e 20 79 6f 75 20 67 69 76  ore than you giv
0120: 65 2e 0a 2a 2a 0a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  e..**.**********
0130: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0140: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0150: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0160: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0170: 2a 2a 2a 2a 0a 2a 2a 0a 2a 2a 20 54 68 65 20 63  ****.**.** The c
0180: 6f 64 65 20 69 6e 20 74 68 69 73 20 66 69 6c 65  ode in this file
0190: 20 69 6d 70 6c 65 6d 65 6e 74 73 20 61 20 63 6f   implements a co
01a0: 6d 70 61 63 74 20 62 75 74 20 72 65 61 73 6f 6e  mpact but reason
01b0: 61 62 6c 79 0a 2a 2a 20 65 66 66 69 63 69 65 6e  ably.** efficien
01c0: 74 20 72 65 67 75 6c 61 72 2d 65 78 70 72 65 73  t regular-expres
01d0: 73 69 6f 6e 20 6d 61 74 63 68 65 72 20 66 6f 72  sion matcher for
01e0: 20 70 6f 73 69 78 20 65 78 74 65 6e 64 65 64 20   posix extended 
01f0: 72 65 67 75 6c 61 72 0a 2a 2a 20 65 78 70 72 65  regular.** expre
0200: 73 73 69 6f 6e 73 20 61 67 61 69 6e 73 74 20 55  ssions against U
0210: 54 46 38 20 74 65 78 74 2e 20 20 54 68 65 20 66  TF8 text.  The f
0220: 6f 6c 6c 6f 77 69 6e 67 20 73 79 6e 74 61 78 20  ollowing syntax 
0230: 69 73 20 73 75 70 70 6f 72 74 65 64 3a 0a 2a 2a  is supported:.**
0240: 0a 2a 2a 20 20 20 20 20 58 2a 20 20 20 20 20 20  .**     X*      
0250: 7a 65 72 6f 20 6f 72 20 6d 6f 72 65 20 6f 63 63  zero or more occ
0260: 75 72 72 65 6e 63 65 73 20 6f 66 20 58 0a 2a 2a  urrences of X.**
0270: 20 20 20 20 20 58 2b 20 20 20 20 20 20 6f 6e 65       X+      one
0280: 20 6f 72 20 6d 6f 72 65 20 6f 63 63 75 72 72 65   or more occurre
0290: 6e 63 65 73 20 6f 66 20 58 0a 2a 2a 20 20 20 20  nces of X.**    
02a0: 20 58 3f 20 20 20 20 20 20 7a 65 72 6f 20 6f 72   X?      zero or
02b0: 20 6f 6e 65 20 6f 63 63 75 72 72 65 6e 63 65 73   one occurrences
02c0: 20 6f 66 20 58 0a 2a 2a 20 20 20 20 20 58 7b 70   of X.**     X{p
02d0: 2c 71 7d 20 20 62 65 74 77 65 65 6e 20 70 20 61  ,q}  between p a
02e0: 6e 64 20 71 20 6f 63 63 75 72 72 65 6e 63 65 73  nd q occurrences
02f0: 20 6f 66 20 58 0a 2a 2a 20 20 20 20 20 28 58 29   of X.**     (X)
0300: 20 20 20 20 20 6d 61 74 63 68 20 58 0a 2a 2a 20       match X.** 
0310: 20 20 20 20 58 7c 59 20 20 20 20 20 58 20 6f 72      X|Y     X or
0320: 20 59 0a 2a 2a 20 20 20 20 20 5e 58 20 20 20 20   Y.**     ^X    
0330: 20 20 58 20 6f 63 63 75 72 72 69 6e 67 20 61 74    X occurring at
0340: 20 74 68 65 20 62 65 67 69 6e 6e 69 6e 67 20 6f   the beginning o
0350: 66 20 74 68 65 20 73 74 72 69 6e 67 0a 2a 2a 20  f the string.** 
0360: 20 20 20 20 58 24 20 20 20 20 20 20 58 20 6f 63      X$      X oc
0370: 63 75 72 72 69 6e 67 20 61 74 20 74 68 65 20 65  curring at the e
0380: 6e 64 20 6f 66 20 74 68 65 20 73 74 72 69 6e 67  nd of the string
0390: 0a 2a 2a 20 20 20 20 20 2e 20 20 20 20 20 20 20  .**     .       
03a0: 4d 61 74 63 68 20 61 6e 79 20 73 69 6e 67 6c 65  Match any single
03b0: 20 63 68 61 72 61 63 74 65 72 0a 2a 2a 20 20 20   character.**   
03c0: 20 20 5c 63 20 20 20 20 20 20 43 68 61 72 61 63    \c      Charac
03d0: 74 65 72 20 63 20 77 68 65 72 65 20 63 20 69 73  ter c where c is
03e0: 20 6f 6e 65 20 6f 66 20 5c 7b 7d 28 29 5b 5d 7c   one of \{}()[]|
03f0: 2a 2b 3f 2e 0a 2a 2a 20 20 20 20 20 5c 63 20 20  *+?..**     \c  
0400: 20 20 20 20 43 2d 6c 61 6e 67 75 61 67 65 20 65      C-language e
0410: 73 63 61 70 65 73 20 66 6f 72 20 63 20 69 6e 20  scapes for c in 
0420: 61 66 6e 72 74 76 2e 20 20 65 78 3a 20 5c 74 20  afnrtv.  ex: \t 
0430: 6f 72 20 5c 6e 0a 2a 2a 20 20 20 20 20 5c 75 58  or \n.**     \uX
0440: 58 58 58 20 20 57 68 65 72 65 20 58 58 58 58 20  XXX  Where XXXX 
0450: 69 73 20 65 78 61 63 74 6c 79 20 34 20 68 65 78  is exactly 4 hex
0460: 20 64 69 67 69 74 73 2c 20 75 6e 69 63 6f 64 65   digits, unicode
0470: 20 76 61 6c 75 65 20 58 58 58 58 0a 2a 2a 20 20   value XXXX.**  
0480: 20 20 20 5c 78 58 58 58 20 20 20 57 68 65 72 65     \xXXX   Where
0490: 20 58 58 58 20 69 73 20 61 6e 79 20 6e 75 6d 62   XXX is any numb
04a0: 65 72 20 6f 66 20 68 65 78 20 64 69 67 69 74 73  er of hex digits
04b0: 2c 20 75 6e 69 63 6f 64 65 20 76 61 6c 75 65 20  , unicode value 
04c0: 58 58 58 0a 2a 2a 20 20 20 20 20 5b 61 62 63 5d  XXX.**     [abc]
04d0: 20 20 20 41 6e 79 20 73 69 6e 67 6c 65 20 63 68     Any single ch
04e0: 61 72 61 63 74 65 72 20 66 72 6f 6d 20 74 68 65  aracter from the
04f0: 20 73 65 74 20 61 62 63 0a 2a 2a 20 20 20 20 20   set abc.**     
0500: 5b 5e 61 62 63 5d 20 20 41 6e 79 20 73 69 6e 67  [^abc]  Any sing
0510: 6c 65 20 63 68 61 72 61 63 74 65 72 20 6e 6f 74  le character not
0520: 20 69 6e 20 74 68 65 20 73 65 74 20 61 62 63 0a   in the set abc.
0530: 2a 2a 20 20 20 20 20 5b 61 2d 7a 5d 20 20 20 41  **     [a-z]   A
0540: 6e 79 20 73 69 6e 67 6c 65 20 63 68 61 72 61 63  ny single charac
0550: 74 65 72 20 69 6e 20 74 68 65 20 72 61 6e 67 65  ter in the range
0560: 20 61 2d 7a 0a 2a 2a 20 20 20 20 20 5b 5e 61 2d   a-z.**     [^a-
0570: 7a 5d 20 20 41 6e 79 20 73 69 6e 67 6c 65 20 63  z]  Any single c
0580: 68 61 72 61 63 74 65 72 20 6e 6f 74 20 69 6e 20  haracter not in 
0590: 74 68 65 20 72 61 6e 67 65 20 61 2d 7a 0a 2a 2a  the range a-z.**
05a0: 20 20 20 20 20 5c 62 20 20 20 20 20 20 57 6f 72       \b      Wor
05b0: 64 20 62 6f 75 6e 64 61 72 79 0a 2a 2a 20 20 20  d boundary.**   
05c0: 20 20 5c 77 20 20 20 20 20 20 57 6f 72 64 20 63    \w      Word c
05d0: 68 61 72 61 63 74 65 72 2e 20 20 5b 41 2d 5a 61  haracter.  [A-Za
05e0: 2d 7a 30 2d 39 5f 5d 0a 2a 2a 20 20 20 20 20 5c  -z0-9_].**     \
05f0: 57 20 20 20 20 20 20 4e 6f 6e 2d 77 6f 72 64 20  W      Non-word 
0600: 63 68 61 72 61 63 74 65 72 0a 2a 2a 20 20 20 20  character.**    
0610: 20 5c 64 20 20 20 20 20 20 44 69 67 69 74 0a 2a   \d      Digit.*
0620: 2a 20 20 20 20 20 5c 44 20 20 20 20 20 20 4e 6f  *     \D      No
0630: 6e 2d 64 69 67 69 74 0a 2a 2a 20 20 20 20 20 5c  n-digit.**     \
0640: 73 20 20 20 20 20 20 57 68 69 74 65 73 70 61 63  s      Whitespac
0650: 65 20 63 68 61 72 61 63 74 65 72 0a 2a 2a 20 20  e character.**  
0660: 20 20 20 5c 53 20 20 20 20 20 20 4e 6f 6e 2d 77     \S      Non-w
0670: 68 69 74 65 73 70 61 63 65 20 63 68 61 72 61 63  hitespace charac
0680: 74 65 72 0a 2a 2a 0a 2a 2a 20 41 20 6e 6f 6e 64  ter.**.** A nond
0690: 65 74 65 72 6d 69 6e 69 73 74 69 63 20 66 69 6e  eterministic fin
06a0: 69 74 65 20 61 75 74 6f 6d 61 74 6f 6e 20 28 4e  ite automaton (N
06b0: 46 41 29 20 69 73 20 75 73 65 64 20 66 6f 72 20  FA) is used for 
06c0: 6d 61 74 63 68 69 6e 67 2c 20 73 6f 20 74 68 65  matching, so the
06d0: 0a 2a 2a 20 70 65 72 66 6f 72 6d 61 6e 63 65 20  .** performance 
06e0: 69 73 20 62 6f 75 6e 64 65 64 20 62 79 20 4f 28  is bounded by O(
06f0: 4e 2a 4d 29 20 77 68 65 72 65 20 4e 20 69 73 20  N*M) where N is 
0700: 74 68 65 20 73 69 7a 65 20 6f 66 20 74 68 65 20  the size of the 
0710: 72 65 67 75 6c 61 72 0a 2a 2a 20 65 78 70 72 65  regular.** expre
0720: 73 73 69 6f 6e 20 61 6e 64 20 4d 20 69 73 20 74  ssion and M is t
0730: 68 65 20 73 69 7a 65 20 6f 66 20 74 68 65 20 69  he size of the i
0740: 6e 70 75 74 20 73 74 72 69 6e 67 2e 20 20 54 68  nput string.  Th
0750: 65 20 6d 61 74 63 68 65 72 20 6e 65 76 65 72 0a  e matcher never.
0760: 2a 2a 20 65 78 68 69 62 69 74 73 20 65 78 70 6f  ** exhibits expo
0770: 6e 65 6e 74 69 61 6c 20 62 65 68 61 76 69 6f 72  nential behavior
0780: 2e 20 20 4e 6f 74 65 20 74 68 61 74 20 74 68 65  .  Note that the
0790: 20 58 7b 70 2c 71 7d 20 6f 70 65 72 61 74 6f 72   X{p,q} operator
07a0: 20 65 78 70 61 6e 64 73 0a 2a 2a 20 74 6f 20 70   expands.** to p
07b0: 20 63 6f 70 69 65 73 20 6f 66 20 58 20 66 6f 6c   copies of X fol
07c0: 6c 6f 77 69 6e 67 20 62 79 20 71 2d 70 20 63 6f  lowing by q-p co
07d0: 70 69 65 73 20 6f 66 20 58 3f 20 61 6e 64 20 74  pies of X? and t
07e0: 68 61 74 20 74 68 65 20 73 69 7a 65 20 6f 66 20  hat the size of 
07f0: 74 68 65 0a 2a 2a 20 72 65 67 75 6c 61 72 20 65  the.** regular e
0800: 78 70 72 65 73 73 69 6f 6e 20 69 6e 20 74 68 65  xpression in the
0810: 20 4f 28 4e 2a 4d 29 20 70 65 72 66 6f 72 6d 61   O(N*M) performa
0820: 6e 63 65 20 62 6f 75 6e 64 20 69 73 20 63 6f 6d  nce bound is com
0830: 70 75 74 65 64 20 61 66 74 65 72 0a 2a 2a 20 74  puted after.** t
0840: 68 69 73 20 65 78 70 61 6e 73 69 6f 6e 2e 0a 2a  his expansion..*
0850: 2f 0a 23 69 6e 63 6c 75 64 65 20 3c 73 74 72 69  /.#include <stri
0860: 6e 67 2e 68 3e 0a 23 69 6e 63 6c 75 64 65 20 3c  ng.h>.#include <
0870: 73 74 64 6c 69 62 2e 68 3e 0a 23 69 6e 63 6c 75  stdlib.h>.#inclu
0880: 64 65 20 22 73 71 6c 69 74 65 33 2e 68 22 0a 0a  de "sqlite3.h"..
0890: 2f 2a 20 54 68 65 20 65 6e 64 2d 6f 66 2d 69 6e  /* The end-of-in
08a0: 70 75 74 20 63 68 61 72 61 63 74 65 72 20 2a 2f  put character */
08b0: 0a 23 64 65 66 69 6e 65 20 52 45 5f 45 4f 46 20  .#define RE_EOF 
08c0: 20 20 20 20 20 20 20 20 20 20 20 30 20 20 20 20             0    
08d0: 2f 2a 20 45 6e 64 20 6f 66 20 69 6e 70 75 74 20  /* End of input 
08e0: 2a 2f 0a 0a 2f 2a 20 54 68 65 20 4e 46 41 20 69  */../* The NFA i
08f0: 73 20 69 6d 70 6c 65 6d 65 6e 74 65 64 20 61 73  s implemented as
0900: 20 73 65 71 75 65 6e 63 65 20 6f 66 20 6f 70 63   sequence of opc
0910: 6f 64 65 73 20 74 61 6b 65 6e 20 66 72 6f 6d 20  odes taken from 
0920: 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 0a 2a 2a  the following.**
0930: 20 73 65 74 2e 20 20 45 61 63 68 20 6f 70 63 6f   set.  Each opco
0940: 64 65 20 68 61 73 20 61 20 73 69 6e 67 6c 65 20  de has a single 
0950: 69 6e 74 65 67 65 72 20 61 72 67 75 6d 65 6e 74  integer argument
0960: 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65 20 52 45 5f  ..*/.#define RE_
0970: 4f 50 5f 4d 41 54 43 48 20 20 20 20 20 20 20 31  OP_MATCH       1
0980: 20 20 20 20 2f 2a 20 4d 61 74 63 68 20 74 68 65      /* Match the
0990: 20 6f 6e 65 20 63 68 61 72 61 63 74 65 72 20 69   one character i
09a0: 6e 20 74 68 65 20 61 72 67 75 6d 65 6e 74 20 2a  n the argument *
09b0: 2f 0a 23 64 65 66 69 6e 65 20 52 45 5f 4f 50 5f  /.#define RE_OP_
09c0: 41 4e 59 20 20 20 20 20 20 20 20 20 32 20 20 20  ANY         2   
09d0: 20 2f 2a 20 4d 61 74 63 68 20 61 6e 79 20 6f 6e   /* Match any on
09e0: 65 20 63 68 61 72 61 63 74 65 72 2e 20 20 28 49  e character.  (I
09f0: 6d 70 6c 65 6d 65 6e 74 73 20 22 2e 22 29 20 2a  mplements ".") *
0a00: 2f 0a 23 64 65 66 69 6e 65 20 52 45 5f 4f 50 5f  /.#define RE_OP_
0a10: 41 4e 59 53 54 41 52 20 20 20 20 20 33 20 20 20  ANYSTAR     3   
0a20: 20 2f 2a 20 53 70 65 63 69 61 6c 20 6f 70 74 69   /* Special opti
0a30: 6d 69 7a 65 64 20 76 65 72 73 69 6f 6e 20 6f 66  mized version of
0a40: 20 2e 2a 20 2a 2f 0a 23 64 65 66 69 6e 65 20 52   .* */.#define R
0a50: 45 5f 4f 50 5f 46 4f 52 4b 20 20 20 20 20 20 20  E_OP_FORK       
0a60: 20 34 20 20 20 20 2f 2a 20 43 6f 6e 74 69 6e 75   4    /* Continu
0a70: 65 20 74 6f 20 62 6f 74 68 20 6e 65 78 74 20 61  e to both next a
0a80: 6e 64 20 6f 70 63 6f 64 65 20 61 74 20 69 41 72  nd opcode at iAr
0a90: 67 20 2a 2f 0a 23 64 65 66 69 6e 65 20 52 45 5f  g */.#define RE_
0aa0: 4f 50 5f 47 4f 54 4f 20 20 20 20 20 20 20 20 35  OP_GOTO        5
0ab0: 20 20 20 20 2f 2a 20 4a 75 6d 70 20 74 6f 20 6f      /* Jump to o
0ac0: 70 63 6f 64 65 20 61 74 20 69 41 72 67 20 2a 2f  pcode at iArg */
0ad0: 0a 23 64 65 66 69 6e 65 20 52 45 5f 4f 50 5f 41  .#define RE_OP_A
0ae0: 43 43 45 50 54 20 20 20 20 20 20 36 20 20 20 20  CCEPT      6    
0af0: 2f 2a 20 48 61 6c 74 20 61 6e 64 20 69 6e 64 69  /* Halt and indi
0b00: 63 61 74 65 20 61 20 73 75 63 63 65 73 73 66 75  cate a successfu
0b10: 6c 20 6d 61 74 63 68 20 2a 2f 0a 23 64 65 66 69  l match */.#defi
0b20: 6e 65 20 52 45 5f 4f 50 5f 43 43 5f 49 4e 43 20  ne RE_OP_CC_INC 
0b30: 20 20 20 20 20 37 20 20 20 20 2f 2a 20 42 65 67       7    /* Beg
0b40: 69 6e 6e 69 6e 67 20 6f 66 20 61 20 5b 2e 2e 2e  inning of a [...
0b50: 5d 20 63 68 61 72 61 63 74 65 72 20 63 6c 61 73  ] character clas
0b60: 73 20 2a 2f 0a 23 64 65 66 69 6e 65 20 52 45 5f  s */.#define RE_
0b70: 4f 50 5f 43 43 5f 45 58 43 20 20 20 20 20 20 38  OP_CC_EXC      8
0b80: 20 20 20 20 2f 2a 20 42 65 67 69 6e 6e 69 6e 67      /* Beginning
0b90: 20 6f 66 20 61 20 5b 5e 2e 2e 2e 5d 20 63 68 61   of a [^...] cha
0ba0: 72 61 63 74 65 72 20 63 6c 61 73 73 20 2a 2f 0a  racter class */.
0bb0: 23 64 65 66 69 6e 65 20 52 45 5f 4f 50 5f 43 43  #define RE_OP_CC
0bc0: 5f 56 41 4c 55 45 20 20 20 20 39 20 20 20 20 2f  _VALUE    9    /
0bd0: 2a 20 53 69 6e 67 6c 65 20 76 61 6c 75 65 20 69  * Single value i
0be0: 6e 20 61 20 63 68 61 72 61 63 74 65 72 20 63 6c  n a character cl
0bf0: 61 73 73 20 2a 2f 0a 23 64 65 66 69 6e 65 20 52  ass */.#define R
0c00: 45 5f 4f 50 5f 43 43 5f 52 41 4e 47 45 20 20 20  E_OP_CC_RANGE   
0c10: 31 30 20 20 20 20 2f 2a 20 52 61 6e 67 65 20 6f  10    /* Range o
0c20: 66 20 76 61 6c 75 65 73 20 69 6e 20 61 20 63 68  f values in a ch
0c30: 61 72 61 63 74 65 72 20 63 6c 61 73 73 20 2a 2f  aracter class */
0c40: 0a 23 64 65 66 69 6e 65 20 52 45 5f 4f 50 5f 57  .#define RE_OP_W
0c50: 4f 52 44 20 20 20 20 20 20 20 31 31 20 20 20 20  ORD       11    
0c60: 2f 2a 20 50 65 72 6c 20 77 6f 72 64 20 63 68 61  /* Perl word cha
0c70: 72 61 63 74 65 72 20 5b 41 2d 5a 61 2d 7a 30 2d  racter [A-Za-z0-
0c80: 39 5f 5d 20 2a 2f 0a 23 64 65 66 69 6e 65 20 52  9_] */.#define R
0c90: 45 5f 4f 50 5f 4e 4f 54 57 4f 52 44 20 20 20 20  E_OP_NOTWORD    
0ca0: 31 32 20 20 20 20 2f 2a 20 4e 6f 74 20 61 20 70  12    /* Not a p
0cb0: 65 72 6c 20 77 6f 72 64 20 63 68 61 72 61 63 74  erl word charact
0cc0: 65 72 20 2a 2f 0a 23 64 65 66 69 6e 65 20 52 45  er */.#define RE
0cd0: 5f 4f 50 5f 44 49 47 49 54 20 20 20 20 20 20 31  _OP_DIGIT      1
0ce0: 33 20 20 20 20 2f 2a 20 64 69 67 69 74 3a 20 20  3    /* digit:  
0cf0: 5b 30 2d 39 5d 20 2a 2f 0a 23 64 65 66 69 6e 65  [0-9] */.#define
0d00: 20 52 45 5f 4f 50 5f 4e 4f 54 44 49 47 49 54 20   RE_OP_NOTDIGIT 
0d10: 20 20 31 34 20 20 20 20 2f 2a 20 4e 6f 74 20 61    14    /* Not a
0d20: 20 64 69 67 69 74 20 2a 2f 0a 23 64 65 66 69 6e   digit */.#defin
0d30: 65 20 52 45 5f 4f 50 5f 53 50 41 43 45 20 20 20  e RE_OP_SPACE   
0d40: 20 20 20 31 35 20 20 20 20 2f 2a 20 73 70 61 63     15    /* spac
0d50: 65 3a 20 20 5b 20 5c 74 5c 6e 5c 72 5c 76 5c 66  e:  [ \t\n\r\v\f
0d60: 5d 20 2a 2f 0a 23 64 65 66 69 6e 65 20 52 45 5f  ] */.#define RE_
0d70: 4f 50 5f 4e 4f 54 53 50 41 43 45 20 20 20 31 36  OP_NOTSPACE   16
0d80: 20 20 20 20 2f 2a 20 4e 6f 74 20 61 20 64 69 67      /* Not a dig
0d90: 69 74 20 2a 2f 0a 23 64 65 66 69 6e 65 20 52 45  it */.#define RE
0da0: 5f 4f 50 5f 42 4f 55 4e 44 41 52 59 20 20 20 31  _OP_BOUNDARY   1
0db0: 37 20 20 20 20 2f 2a 20 42 6f 75 6e 64 61 72 79  7    /* Boundary
0dc0: 20 62 65 74 77 65 65 6e 20 77 6f 72 64 20 61 6e   between word an
0dd0: 64 20 6e 6f 6e 2d 77 6f 72 64 20 2a 2f 0a 0a 2f  d non-word */../
0de0: 2a 20 45 61 63 68 20 6f 70 63 6f 64 65 20 69 73  * Each opcode is
0df0: 20 61 20 22 73 74 61 74 65 22 20 69 6e 20 74 68   a "state" in th
0e00: 65 20 4e 46 41 20 2a 2f 0a 74 79 70 65 64 65 66  e NFA */.typedef
0e10: 20 75 6e 73 69 67 6e 65 64 20 73 68 6f 72 74 20   unsigned short 
0e20: 52 65 53 74 61 74 65 4e 75 6d 62 65 72 3b 0a 0a  ReStateNumber;..
0e30: 2f 2a 20 42 65 63 61 75 73 65 20 74 68 69 73 20  /* Because this 
0e40: 69 73 20 61 6e 20 4e 46 41 20 61 6e 64 20 6e 6f  is an NFA and no
0e50: 74 20 61 20 44 46 41 2c 20 6d 75 6c 74 69 70 6c  t a DFA, multipl
0e60: 65 20 73 74 61 74 65 73 20 63 61 6e 20 62 65 20  e states can be 
0e70: 61 63 74 69 76 65 20 61 74 0a 2a 2a 20 6f 6e 63  active at.** onc
0e80: 65 2e 20 20 41 6e 20 69 6e 73 74 61 6e 63 65 20  e.  An instance 
0e90: 6f 66 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67  of the following
0ea0: 20 6f 62 6a 65 63 74 20 72 65 63 6f 72 64 73 20   object records 
0eb0: 61 6c 6c 20 61 63 74 69 76 65 20 73 74 61 74 65  all active state
0ec0: 73 20 69 6e 0a 2a 2a 20 74 68 65 20 4e 46 41 2e  s in.** the NFA.
0ed0: 20 20 54 68 65 20 69 6d 70 6c 65 6d 65 6e 74 61    The implementa
0ee0: 74 69 6f 6e 20 69 73 20 6f 70 74 69 6d 69 7a 65  tion is optimize
0ef0: 64 20 66 6f 72 20 74 68 65 20 63 6f 6d 6d 6f 6e  d for the common
0f00: 20 63 61 73 65 20 77 68 65 72 65 20 74 68 65 0a   case where the.
0f10: 2a 2a 20 6e 75 6d 62 65 72 20 6f 66 20 61 63 74  ** number of act
0f20: 69 76 65 73 20 73 74 61 74 65 73 20 69 73 20 73  ives states is s
0f30: 6d 61 6c 6c 2e 0a 2a 2f 0a 74 79 70 65 64 65 66  mall..*/.typedef
0f40: 20 73 74 72 75 63 74 20 52 65 53 74 61 74 65 53   struct ReStateS
0f50: 65 74 20 7b 0a 20 20 75 6e 73 69 67 6e 65 64 20  et {.  unsigned 
0f60: 6e 53 74 61 74 65 3b 20 20 20 20 20 20 20 20 20  nState;         
0f70: 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20     /* Number of 
0f80: 63 75 72 72 65 6e 74 20 73 74 61 74 65 73 20 2a  current states *
0f90: 2f 0a 20 20 52 65 53 74 61 74 65 4e 75 6d 62 65  /.  ReStateNumbe
0fa0: 72 20 2a 61 53 74 61 74 65 3b 20 20 20 20 20 20  r *aState;      
0fb0: 2f 2a 20 43 75 72 72 65 6e 74 20 73 74 61 74 65  /* Current state
0fc0: 73 20 2a 2f 0a 7d 20 52 65 53 74 61 74 65 53 65  s */.} ReStateSe
0fd0: 74 3b 0a 0a 2f 2a 20 41 20 63 6f 6d 70 69 6c 65  t;../* A compile
0fe0: 64 20 4e 46 41 20 28 6f 72 20 61 6e 20 4e 46 41  d NFA (or an NFA
0ff0: 20 74 68 61 74 20 69 73 20 69 6e 20 74 68 65 20   that is in the 
1000: 70 72 6f 63 65 73 73 20 6f 66 20 62 65 69 6e 67  process of being
1010: 20 63 6f 6d 70 69 6c 65 64 29 20 69 73 0a 2a 2a   compiled) is.**
1020: 20 61 6e 20 69 6e 73 74 61 6e 63 65 20 6f 66 20   an instance of 
1030: 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20 6f 62  the following ob
1040: 6a 65 63 74 2e 0a 2a 2f 0a 74 79 70 65 64 65 66  ject..*/.typedef
1050: 20 73 74 72 75 63 74 20 52 65 43 6f 6d 70 69 6c   struct ReCompil
1060: 65 64 20 7b 0a 20 20 63 6f 6e 73 74 20 75 6e 73  ed {.  const uns
1070: 69 67 6e 65 64 20 63 68 61 72 20 2a 7a 49 6e 3b  igned char *zIn;
1080: 20 20 20 2f 2a 20 52 65 67 75 6c 61 72 20 65 78     /* Regular ex
1090: 70 72 65 73 73 69 6f 6e 20 74 65 78 74 20 2a 2f  pression text */
10a0: 0a 20 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 7a  .  const char *z
10b0: 45 72 72 3b 20 20 20 20 20 20 20 20 20 20 20 2f  Err;           /
10c0: 2a 20 45 72 72 6f 72 20 6d 65 73 73 61 67 65 20  * Error message 
10d0: 74 6f 20 72 65 74 75 72 6e 20 2a 2f 0a 20 20 63  to return */.  c
10e0: 68 61 72 20 2a 61 4f 70 3b 20 20 20 20 20 20 20  har *aOp;       
10f0: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4f 70             /* Op
1100: 65 72 61 74 6f 72 73 20 66 6f 72 20 74 68 65 20  erators for the 
1110: 76 69 72 74 75 61 6c 20 6d 61 63 68 69 6e 65 20  virtual machine 
1120: 2a 2f 0a 20 20 69 6e 74 20 2a 61 41 72 67 3b 20  */.  int *aArg; 
1130: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1140: 20 2f 2a 20 41 72 67 75 6d 65 6e 74 73 20 74 6f   /* Arguments to
1150: 20 65 61 63 68 20 6f 70 65 72 61 74 6f 72 20 2a   each operator *
1160: 2f 0a 20 20 63 68 61 72 20 7a 49 6e 69 74 5b 31  /.  char zInit[1
1170: 32 5d 3b 20 20 20 20 20 20 20 20 20 20 20 20 20  2];             
1180: 2f 2a 20 49 6e 69 74 69 61 6c 20 74 65 78 74 20  /* Initial text 
1190: 74 6f 20 6d 61 74 63 68 20 2a 2f 0a 20 20 69 6e  to match */.  in
11a0: 74 20 6e 49 6e 69 74 3b 20 20 20 20 20 20 20 20  t nInit;        
11b0: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d            /* Num
11c0: 62 65 72 20 6f 66 20 63 68 61 72 61 63 74 65 72  ber of character
11d0: 73 20 69 6e 20 7a 49 6e 69 74 20 2a 2f 0a 20 20  s in zInit */.  
11e0: 75 6e 73 69 67 6e 65 64 20 6e 53 74 61 74 65 3b  unsigned nState;
11f0: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4e              /* N
1200: 75 6d 62 65 72 20 6f 66 20 65 6e 74 72 69 65 73  umber of entries
1210: 20 69 6e 20 61 4f 70 5b 5d 20 61 6e 64 20 61 41   in aOp[] and aA
1220: 72 67 5b 5d 20 2a 2f 0a 20 20 75 6e 73 69 67 6e  rg[] */.  unsign
1230: 65 64 20 6e 41 6c 6c 6f 63 3b 20 20 20 20 20 20  ed nAlloc;      
1240: 20 20 20 20 20 20 2f 2a 20 53 6c 6f 74 73 20 61        /* Slots a
1250: 6c 6c 6f 63 61 74 65 64 20 66 6f 72 20 61 4f 70  llocated for aOp
1260: 5b 5d 20 61 6e 64 20 61 41 72 67 5b 5d 20 2a 2f  [] and aArg[] */
1270: 0a 7d 20 52 65 43 6f 6d 70 69 6c 65 64 3b 0a 0a  .} ReCompiled;..
1280: 2f 2a 20 41 64 64 20 61 20 73 74 61 74 65 20 74  /* Add a state t
1290: 6f 20 74 68 65 20 67 69 76 65 6e 20 73 74 61 74  o the given stat
12a0: 65 20 73 65 74 20 69 66 20 69 74 20 69 73 20 6e  e set if it is n
12b0: 6f 74 20 61 6c 72 65 61 64 79 20 74 68 65 72 65  ot already there
12c0: 20 2a 2f 0a 73 74 61 74 69 63 20 76 6f 69 64 20   */.static void 
12d0: 72 65 5f 61 64 64 5f 73 74 61 74 65 28 52 65 53  re_add_state(ReS
12e0: 74 61 74 65 53 65 74 20 2a 70 53 65 74 2c 20 69  tateSet *pSet, i
12f0: 6e 74 20 6e 65 77 53 74 61 74 65 29 7b 0a 20 20  nt newState){.  
1300: 75 6e 73 69 67 6e 65 64 20 69 3b 0a 20 20 66 6f  unsigned i;.  fo
1310: 72 28 69 3d 30 3b 20 69 3c 70 53 65 74 2d 3e 6e  r(i=0; i<pSet->n
1320: 53 74 61 74 65 3b 20 69 2b 2b 29 20 69 66 28 20  State; i++) if( 
1330: 70 53 65 74 2d 3e 61 53 74 61 74 65 5b 69 5d 3d  pSet->aState[i]=
1340: 3d 6e 65 77 53 74 61 74 65 20 29 20 72 65 74 75  =newState ) retu
1350: 72 6e 3b 0a 20 20 70 53 65 74 2d 3e 61 53 74 61  rn;.  pSet->aSta
1360: 74 65 5b 70 53 65 74 2d 3e 6e 53 74 61 74 65 2b  te[pSet->nState+
1370: 2b 5d 20 3d 20 6e 65 77 53 74 61 74 65 3b 0a 7d  +] = newState;.}
1380: 0a 0a 2f 2a 20 45 78 74 72 61 63 74 20 74 68 65  ../* Extract the
1390: 20 6e 65 78 74 20 75 6e 69 63 6f 64 65 20 63 68   next unicode ch
13a0: 61 72 61 63 74 65 72 20 66 72 6f 6d 20 2a 70 7a  aracter from *pz
13b0: 49 6e 20 61 6e 64 20 72 65 74 75 72 6e 20 69 74  In and return it
13c0: 2e 20 20 41 64 76 61 6e 63 65 0a 2a 2a 20 2a 70  .  Advance.** *p
13d0: 7a 49 6e 20 74 6f 20 74 68 65 20 66 69 72 73 74  zIn to the first
13e0: 20 62 79 74 65 20 70 61 73 74 20 74 68 65 20 65   byte past the e
13f0: 6e 64 20 6f 66 20 74 68 65 20 63 68 61 72 61 63  nd of the charac
1400: 74 65 72 20 72 65 74 75 72 6e 65 64 2e 20 20 54  ter returned.  T
1410: 6f 0a 2a 2a 20 62 65 20 63 6c 65 61 72 3a 20 20  o.** be clear:  
1420: 74 68 69 73 20 72 6f 75 74 69 6e 65 20 63 6f 6e  this routine con
1430: 76 65 72 74 73 20 75 74 66 38 20 74 6f 20 75 6e  verts utf8 to un
1440: 69 63 6f 64 65 2e 20 20 54 68 69 73 20 72 6f 75  icode.  This rou
1450: 74 69 6e 65 20 69 73 20 0a 2a 2a 20 6f 70 74 69  tine is .** opti
1460: 6d 69 7a 65 64 20 66 6f 72 20 74 68 65 20 63 6f  mized for the co
1470: 6d 6d 6f 6e 20 63 61 73 65 20 77 68 65 72 65 20  mmon case where 
1480: 74 68 65 20 6e 65 78 74 20 63 68 61 72 61 63 74  the next charact
1490: 65 72 20 69 73 20 61 20 73 69 6e 67 6c 65 20 62  er is a single b
14a0: 79 74 65 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 75  yte..*/.static u
14b0: 6e 73 69 67 6e 65 64 20 72 65 5f 6e 65 78 74 5f  nsigned re_next_
14c0: 63 68 61 72 28 63 6f 6e 73 74 20 75 6e 73 69 67  char(const unsig
14d0: 6e 65 64 20 63 68 61 72 20 2a 2a 70 7a 49 6e 29  ned char **pzIn)
14e0: 7b 0a 20 20 75 6e 73 69 67 6e 65 64 20 63 20 3d  {.  unsigned c =
14f0: 20 2a 2a 70 7a 49 6e 3b 0a 20 20 69 66 28 20 63   **pzIn;.  if( c
1500: 3e 30 20 29 20 28 2a 70 7a 49 6e 29 2b 2b 3b 0a  >0 ) (*pzIn)++;.
1510: 20 20 69 66 28 20 63 3e 30 78 38 30 20 29 7b 0a    if( c>0x80 ){.
1520: 20 20 20 20 69 66 28 20 28 63 26 30 78 65 30 29      if( (c&0xe0)
1530: 3d 3d 30 78 63 30 20 26 26 20 28 28 2a 70 7a 49  ==0xc0 && ((*pzI
1540: 6e 29 5b 30 5d 26 30 78 63 30 29 3d 3d 30 78 38  n)[0]&0xc0)==0x8
1550: 30 20 29 7b 0a 20 20 20 20 20 20 63 20 3d 20 28  0 ){.      c = (
1560: 63 26 30 78 31 66 29 3c 3c 36 20 7c 20 28 28 2a  c&0x1f)<<6 | ((*
1570: 70 7a 49 6e 29 5b 30 5d 26 30 78 33 66 29 3b 0a  pzIn)[0]&0x3f);.
1580: 20 20 20 20 20 20 28 2a 70 7a 49 6e 29 2b 2b 3b        (*pzIn)++;
1590: 0a 20 20 20 20 20 20 69 66 28 20 63 3c 30 78 38  .      if( c<0x8
15a0: 30 20 29 20 63 20 3d 20 30 78 66 66 66 64 3b 0a  0 ) c = 0xfffd;.
15b0: 20 20 20 20 7d 65 6c 73 65 20 69 66 28 20 28 63      }else if( (c
15c0: 26 30 78 66 30 29 3d 3d 30 78 65 30 20 26 26 20  &0xf0)==0xe0 && 
15d0: 28 28 2a 70 7a 49 6e 29 5b 30 5d 26 30 78 63 30  ((*pzIn)[0]&0xc0
15e0: 29 3d 3d 30 78 38 30 0a 20 20 20 20 20 20 20 20  )==0x80.        
15f0: 20 20 20 26 26 20 28 28 2a 70 7a 49 6e 29 5b 31     && ((*pzIn)[1
1600: 5d 26 30 78 63 30 29 3d 3d 30 78 38 30 20 29 7b  ]&0xc0)==0x80 ){
1610: 0a 20 20 20 20 20 20 63 20 3d 20 28 63 26 30 78  .      c = (c&0x
1620: 30 66 29 3c 3c 31 32 20 7c 20 28 28 28 2a 70 7a  0f)<<12 | (((*pz
1630: 49 6e 29 5b 30 5d 26 30 78 33 66 29 3c 3c 36 29  In)[0]&0x3f)<<6)
1640: 20 7c 20 28 28 2a 70 7a 49 6e 29 5b 31 5d 26 30   | ((*pzIn)[1]&0
1650: 78 33 66 29 3b 0a 20 20 20 20 20 20 2a 70 7a 49  x3f);.      *pzI
1660: 6e 20 2b 3d 20 32 3b 0a 20 20 20 20 20 20 69 66  n += 2;.      if
1670: 28 20 63 3c 30 78 33 66 66 20 7c 7c 20 28 63 3e  ( c<0x3ff || (c>
1680: 3d 30 78 64 38 30 30 20 26 26 20 63 3c 3d 30 78  =0xd800 && c<=0x
1690: 64 66 66 66 29 20 29 20 63 20 3d 20 30 78 66 66  dfff) ) c = 0xff
16a0: 66 64 3b 0a 20 20 20 20 7d 65 6c 73 65 20 69 66  fd;.    }else if
16b0: 28 20 28 63 26 30 78 66 38 29 3d 3d 30 78 66 30  ( (c&0xf8)==0xf0
16c0: 20 26 26 20 28 28 2a 70 7a 49 6e 29 5b 30 5d 26   && ((*pzIn)[0]&
16d0: 30 78 63 30 29 3d 3d 30 78 38 30 0a 20 20 20 20  0xc0)==0x80.    
16e0: 20 20 20 20 20 20 20 26 26 20 28 28 2a 70 7a 49         && ((*pzI
16f0: 6e 29 5b 31 5d 26 30 78 63 30 29 3d 3d 30 78 38  n)[1]&0xc0)==0x8
1700: 30 20 26 26 20 28 28 2a 70 7a 49 6e 29 5b 32 5d  0 && ((*pzIn)[2]
1710: 26 30 78 63 30 29 3d 3d 30 78 38 30 20 29 7b 0a  &0xc0)==0x80 ){.
1720: 20 20 20 20 20 20 63 20 3d 20 28 63 26 30 78 30        c = (c&0x0
1730: 37 29 3c 3c 31 38 20 7c 20 28 28 28 2a 70 7a 49  7)<<18 | (((*pzI
1740: 6e 29 5b 30 5d 26 30 78 33 66 29 3c 3c 31 32 29  n)[0]&0x3f)<<12)
1750: 20 7c 20 28 28 28 2a 70 7a 49 6e 29 5b 31 5d 26   | (((*pzIn)[1]&
1760: 30 78 33 66 29 3c 3c 36 29 0a 20 20 20 20 20 20  0x3f)<<6).      
1770: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1780: 20 7c 20 28 28 2a 70 7a 49 6e 29 5b 32 5d 26 30   | ((*pzIn)[2]&0
1790: 78 33 66 29 3b 0a 20 20 20 20 20 20 2a 70 7a 49  x3f);.      *pzI
17a0: 6e 20 2b 3d 20 33 3b 0a 20 20 20 20 20 20 69 66  n += 3;.      if
17b0: 28 20 63 3c 30 78 66 66 66 66 20 29 20 63 20 3d  ( c<0xffff ) c =
17c0: 20 30 78 66 66 66 64 3b 0a 20 20 20 20 7d 65 6c   0xfffd;.    }el
17d0: 73 65 7b 0a 20 20 20 20 20 20 63 20 3d 20 30 78  se{.      c = 0x
17e0: 66 66 66 64 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a  fffd;.    }.  }.
17f0: 20 20 72 65 74 75 72 6e 20 63 3b 0a 7d 0a 0a 2f    return c;.}../
1800: 2a 20 52 65 74 75 72 6e 20 74 72 75 65 20 69 66  * Return true if
1810: 20 63 20 69 73 20 61 20 70 65 72 6c 20 22 77 6f   c is a perl "wo
1820: 72 64 22 20 63 68 61 72 61 63 74 65 72 3a 20 20  rd" character:  
1830: 5b 41 2d 5a 61 2d 7a 30 2d 39 5f 5d 20 2a 2f 0a  [A-Za-z0-9_] */.
1840: 73 74 61 74 69 63 20 69 6e 74 20 72 65 5f 77 6f  static int re_wo
1850: 72 64 5f 63 68 61 72 28 69 6e 74 20 63 29 7b 0a  rd_char(int c){.
1860: 20 20 72 65 74 75 72 6e 20 28 63 3e 3d 27 30 27    return (c>='0'
1870: 20 26 26 20 63 3c 3d 27 39 27 29 20 7c 7c 20 28   && c<='9') || (
1880: 63 3e 3d 27 61 27 20 26 26 20 63 3c 3d 27 7a 27  c>='a' && c<='z'
1890: 29 0a 20 20 20 20 20 20 7c 7c 20 28 63 3e 3d 27  ).      || (c>='
18a0: 41 27 20 26 26 20 63 3c 3d 27 5a 27 29 20 7c 7c  A' && c<='Z') ||
18b0: 20 63 3d 3d 27 5f 27 3b 0a 7d 0a 0a 2f 2a 20 52   c=='_';.}../* R
18c0: 65 74 75 72 6e 20 74 72 75 65 20 69 66 20 63 20  eturn true if c 
18d0: 69 73 20 61 20 22 64 69 67 69 74 22 20 63 68 61  is a "digit" cha
18e0: 72 61 63 74 65 72 3a 20 20 5b 30 2d 39 5d 20 2a  racter:  [0-9] *
18f0: 2f 0a 73 74 61 74 69 63 20 69 6e 74 20 72 65 5f  /.static int re_
1900: 64 69 67 69 74 5f 63 68 61 72 28 69 6e 74 20 63  digit_char(int c
1910: 29 7b 0a 20 20 72 65 74 75 72 6e 20 28 63 3e 3d  ){.  return (c>=
1920: 27 30 27 20 26 26 20 63 3c 3d 27 39 27 29 3b 0a  '0' && c<='9');.
1930: 7d 0a 0a 2f 2a 20 52 65 74 75 72 6e 20 74 72 75  }../* Return tru
1940: 65 20 69 66 20 63 20 69 73 20 61 20 70 65 72 6c  e if c is a perl
1950: 20 22 73 70 61 63 65 22 20 63 68 61 72 61 63 74   "space" charact
1960: 65 72 3a 20 20 5b 20 5c 74 5c 72 5c 6e 5c 76 5c  er:  [ \t\r\n\v\
1970: 66 5d 20 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74  f] */.static int
1980: 20 72 65 5f 73 70 61 63 65 5f 63 68 61 72 28 69   re_space_char(i
1990: 6e 74 20 63 29 7b 0a 20 20 72 65 74 75 72 6e 20  nt c){.  return 
19a0: 63 3d 3d 27 20 27 20 7c 7c 20 63 3d 3d 27 5c 74  c==' ' || c=='\t
19b0: 27 20 7c 7c 20 63 3d 3d 27 5c 6e 27 20 7c 7c 20  ' || c=='\n' || 
19c0: 63 3d 3d 27 5c 76 27 20 7c 7c 20 63 3d 3d 27 5c  c=='\v' || c=='\
19d0: 66 27 3b 0a 7d 0a 0a 2f 2a 20 52 75 6e 20 61 20  f';.}../* Run a 
19e0: 63 6f 6d 70 69 6c 65 64 20 72 65 67 75 6c 61 72  compiled regular
19f0: 20 65 78 70 72 65 73 73 69 6f 6e 20 6f 6e 20 74   expression on t
1a00: 68 65 20 7a 65 72 6f 2d 74 65 72 6d 69 6e 61 74  he zero-terminat
1a10: 65 64 20 69 6e 70 75 74 0a 2a 2a 20 73 74 72 69  ed input.** stri
1a20: 6e 67 20 7a 49 6e 5b 5d 2e 20 20 52 65 74 75 72  ng zIn[].  Retur
1a30: 6e 20 74 72 75 65 20 6f 6e 20 61 20 6d 61 74 63  n true on a matc
1a40: 68 20 61 6e 64 20 66 61 6c 73 65 20 69 66 20 74  h and false if t
1a50: 68 65 72 65 20 69 73 20 6e 6f 20 6d 61 74 63 68  here is no match
1a60: 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74 20  ..*/.static int 
1a70: 72 65 5f 65 78 65 63 28 52 65 43 6f 6d 70 69 6c  re_exec(ReCompil
1a80: 65 64 20 2a 70 52 65 2c 20 63 6f 6e 73 74 20 75  ed *pRe, const u
1a90: 6e 73 69 67 6e 65 64 20 63 68 61 72 20 2a 7a 49  nsigned char *zI
1aa0: 6e 29 7b 0a 20 20 52 65 53 74 61 74 65 53 65 74  n){.  ReStateSet
1ab0: 20 61 53 74 61 74 65 53 65 74 5b 32 5d 2c 20 2a   aStateSet[2], *
1ac0: 70 54 68 69 73 2c 20 2a 70 4e 65 78 74 3b 0a 20  pThis, *pNext;. 
1ad0: 20 52 65 53 74 61 74 65 4e 75 6d 62 65 72 20 61   ReStateNumber a
1ae0: 53 70 61 63 65 5b 31 30 30 5d 3b 0a 20 20 52 65  Space[100];.  Re
1af0: 53 74 61 74 65 4e 75 6d 62 65 72 20 2a 70 54 6f  StateNumber *pTo
1b00: 46 72 65 65 3b 0a 20 20 75 6e 73 69 67 6e 65 64  Free;.  unsigned
1b10: 20 69 6e 74 20 69 20 3d 20 30 3b 0a 20 20 75 6e   int i = 0;.  un
1b20: 73 69 67 6e 65 64 20 69 6e 74 20 69 53 77 61 70  signed int iSwap
1b30: 20 3d 20 30 3b 0a 20 20 69 6e 74 20 63 20 3d 20   = 0;.  int c = 
1b40: 52 45 5f 45 4f 46 2b 31 3b 0a 20 20 69 6e 74 20  RE_EOF+1;.  int 
1b50: 63 50 72 65 76 20 3d 20 30 3b 0a 20 20 69 6e 74  cPrev = 0;.  int
1b60: 20 72 63 20 3d 20 30 3b 0a 20 20 0a 20 20 69 66   rc = 0;.  .  if
1b70: 28 20 70 52 65 2d 3e 6e 49 6e 69 74 20 29 7b 0a  ( pRe->nInit ){.
1b80: 20 20 20 20 75 6e 73 69 67 6e 65 64 20 63 68 61      unsigned cha
1b90: 72 20 78 20 3d 20 70 52 65 2d 3e 7a 49 6e 69 74  r x = pRe->zInit
1ba0: 5b 30 5d 3b 0a 20 20 20 20 77 68 69 6c 65 28 20  [0];.    while( 
1bb0: 7a 49 6e 5b 30 5d 20 26 26 20 28 7a 49 6e 5b 30  zIn[0] && (zIn[0
1bc0: 5d 21 3d 78 20 7c 7c 20 6d 65 6d 63 6d 70 28 7a  ]!=x || memcmp(z
1bd0: 49 6e 2c 20 70 52 65 2d 3e 7a 49 6e 69 74 2c 20  In, pRe->zInit, 
1be0: 70 52 65 2d 3e 6e 49 6e 69 74 29 21 3d 30 29 20  pRe->nInit)!=0) 
1bf0: 29 7b 0a 20 20 20 20 20 20 7a 49 6e 2b 2b 3b 0a  ){.      zIn++;.
1c00: 20 20 20 20 7d 0a 20 20 20 20 69 66 28 20 7a 49      }.    if( zI
1c10: 6e 5b 30 5d 3d 3d 30 20 29 20 72 65 74 75 72 6e  n[0]==0 ) return
1c20: 20 30 3b 0a 20 20 7d 0a 20 20 69 66 28 20 70 52   0;.  }.  if( pR
1c30: 65 2d 3e 6e 53 74 61 74 65 3c 3d 28 73 69 7a 65  e->nState<=(size
1c40: 6f 66 28 61 53 70 61 63 65 29 2f 28 73 69 7a 65  of(aSpace)/(size
1c50: 6f 66 28 61 53 70 61 63 65 5b 30 5d 29 2a 32 29  of(aSpace[0])*2)
1c60: 29 20 29 7b 0a 20 20 20 20 70 54 6f 46 72 65 65  ) ){.    pToFree
1c70: 20 3d 20 30 3b 0a 20 20 20 20 61 53 74 61 74 65   = 0;.    aState
1c80: 53 65 74 5b 30 5d 2e 61 53 74 61 74 65 20 3d 20  Set[0].aState = 
1c90: 61 53 70 61 63 65 3b 0a 20 20 7d 65 6c 73 65 7b  aSpace;.  }else{
1ca0: 0a 20 20 20 20 70 54 6f 46 72 65 65 20 3d 20 6d  .    pToFree = m
1cb0: 61 6c 6c 6f 63 28 20 73 69 7a 65 6f 66 28 52 65  alloc( sizeof(Re
1cc0: 53 74 61 74 65 4e 75 6d 62 65 72 29 2a 32 2a 70  StateNumber)*2*p
1cd0: 52 65 2d 3e 6e 53 74 61 74 65 20 29 3b 0a 20 20  Re->nState );.  
1ce0: 20 20 69 66 28 20 70 54 6f 46 72 65 65 3d 3d 30    if( pToFree==0
1cf0: 20 29 20 72 65 74 75 72 6e 20 2d 31 3b 0a 20 20   ) return -1;.  
1d00: 20 20 61 53 74 61 74 65 53 65 74 5b 30 5d 2e 61    aStateSet[0].a
1d10: 53 74 61 74 65 20 3d 20 70 54 6f 46 72 65 65 3b  State = pToFree;
1d20: 0a 20 20 7d 0a 20 20 61 53 74 61 74 65 53 65 74  .  }.  aStateSet
1d30: 5b 31 5d 2e 61 53 74 61 74 65 20 3d 20 26 61 53  [1].aState = &aS
1d40: 74 61 74 65 53 65 74 5b 30 5d 2e 61 53 74 61 74  tateSet[0].aStat
1d50: 65 5b 70 52 65 2d 3e 6e 53 74 61 74 65 5d 3b 0a  e[pRe->nState];.
1d60: 20 20 70 4e 65 78 74 20 3d 20 26 61 53 74 61 74    pNext = &aStat
1d70: 65 53 65 74 5b 31 5d 3b 0a 20 20 70 4e 65 78 74  eSet[1];.  pNext
1d80: 2d 3e 6e 53 74 61 74 65 20 3d 20 30 3b 0a 20 20  ->nState = 0;.  
1d90: 72 65 5f 61 64 64 5f 73 74 61 74 65 28 70 4e 65  re_add_state(pNe
1da0: 78 74 2c 20 30 29 3b 0a 20 20 77 68 69 6c 65 28  xt, 0);.  while(
1db0: 20 63 21 3d 52 45 5f 45 4f 46 20 26 26 20 70 4e   c!=RE_EOF && pN
1dc0: 65 78 74 2d 3e 6e 53 74 61 74 65 3e 30 20 29 7b  ext->nState>0 ){
1dd0: 0a 20 20 20 20 63 50 72 65 76 20 3d 20 63 3b 0a  .    cPrev = c;.
1de0: 20 20 20 20 63 20 3d 20 72 65 5f 6e 65 78 74 5f      c = re_next_
1df0: 63 68 61 72 28 26 7a 49 6e 29 3b 0a 20 20 20 20  char(&zIn);.    
1e00: 70 54 68 69 73 20 3d 20 70 4e 65 78 74 3b 0a 20  pThis = pNext;. 
1e10: 20 20 20 70 4e 65 78 74 20 3d 20 26 61 53 74 61     pNext = &aSta
1e20: 74 65 53 65 74 5b 69 53 77 61 70 5d 3b 0a 20 20  teSet[iSwap];.  
1e30: 20 20 69 53 77 61 70 20 3d 20 31 20 2d 20 69 53    iSwap = 1 - iS
1e40: 77 61 70 3b 0a 20 20 20 20 70 4e 65 78 74 2d 3e  wap;.    pNext->
1e50: 6e 53 74 61 74 65 20 3d 20 30 3b 0a 20 20 20 20  nState = 0;.    
1e60: 66 6f 72 28 69 3d 30 3b 20 69 3c 70 54 68 69 73  for(i=0; i<pThis
1e70: 2d 3e 6e 53 74 61 74 65 3b 20 69 2b 2b 29 7b 0a  ->nState; i++){.
1e80: 20 20 20 20 20 20 69 6e 74 20 78 20 3d 20 70 54        int x = pT
1e90: 68 69 73 2d 3e 61 53 74 61 74 65 5b 69 5d 3b 0a  his->aState[i];.
1ea0: 20 20 20 20 20 20 73 77 69 74 63 68 28 20 70 52        switch( pR
1eb0: 65 2d 3e 61 4f 70 5b 78 5d 20 29 7b 0a 20 20 20  e->aOp[x] ){.   
1ec0: 20 20 20 20 20 63 61 73 65 20 52 45 5f 4f 50 5f       case RE_OP_
1ed0: 4d 41 54 43 48 3a 20 7b 0a 20 20 20 20 20 20 20  MATCH: {.       
1ee0: 20 20 20 69 66 28 20 70 52 65 2d 3e 61 41 72 67     if( pRe->aArg
1ef0: 5b 78 5d 3d 3d 63 20 29 20 72 65 5f 61 64 64 5f  [x]==c ) re_add_
1f00: 73 74 61 74 65 28 70 4e 65 78 74 2c 20 78 2b 31  state(pNext, x+1
1f10: 29 3b 0a 20 20 20 20 20 20 20 20 20 20 62 72 65  );.          bre
1f20: 61 6b 3b 0a 20 20 20 20 20 20 20 20 7d 0a 20 20  ak;.        }.  
1f30: 20 20 20 20 20 20 63 61 73 65 20 52 45 5f 4f 50        case RE_OP
1f40: 5f 41 4e 59 3a 20 7b 0a 20 20 20 20 20 20 20 20  _ANY: {.        
1f50: 20 20 72 65 5f 61 64 64 5f 73 74 61 74 65 28 70    re_add_state(p
1f60: 4e 65 78 74 2c 20 78 2b 31 29 3b 0a 20 20 20 20  Next, x+1);.    
1f70: 20 20 20 20 20 20 62 72 65 61 6b 3b 0a 20 20 20        break;.   
1f80: 20 20 20 20 20 7d 0a 20 20 20 20 20 20 20 20 63       }.        c
1f90: 61 73 65 20 52 45 5f 4f 50 5f 57 4f 52 44 3a 20  ase RE_OP_WORD: 
1fa0: 7b 0a 20 20 20 20 20 20 20 20 20 20 69 66 28 20  {.          if( 
1fb0: 72 65 5f 77 6f 72 64 5f 63 68 61 72 28 63 29 20  re_word_char(c) 
1fc0: 29 20 72 65 5f 61 64 64 5f 73 74 61 74 65 28 70  ) re_add_state(p
1fd0: 4e 65 78 74 2c 20 78 2b 31 29 3b 0a 20 20 20 20  Next, x+1);.    
1fe0: 20 20 20 20 20 20 62 72 65 61 6b 3b 0a 20 20 20        break;.   
1ff0: 20 20 20 20 20 7d 0a 20 20 20 20 20 20 20 20 63       }.        c
2000: 61 73 65 20 52 45 5f 4f 50 5f 4e 4f 54 57 4f 52  ase RE_OP_NOTWOR
2010: 44 3a 20 7b 0a 20 20 20 20 20 20 20 20 20 20 69  D: {.          i
2020: 66 28 20 21 72 65 5f 77 6f 72 64 5f 63 68 61 72  f( !re_word_char
2030: 28 63 29 20 29 20 72 65 5f 61 64 64 5f 73 74 61  (c) ) re_add_sta
2040: 74 65 28 70 4e 65 78 74 2c 20 78 2b 31 29 3b 0a  te(pNext, x+1);.
2050: 20 20 20 20 20 20 20 20 20 20 62 72 65 61 6b 3b            break;
2060: 0a 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20  .        }.     
2070: 20 20 20 63 61 73 65 20 52 45 5f 4f 50 5f 44 49     case RE_OP_DI
2080: 47 49 54 3a 20 7b 0a 20 20 20 20 20 20 20 20 20  GIT: {.         
2090: 20 69 66 28 20 72 65 5f 64 69 67 69 74 5f 63 68   if( re_digit_ch
20a0: 61 72 28 63 29 20 29 20 72 65 5f 61 64 64 5f 73  ar(c) ) re_add_s
20b0: 74 61 74 65 28 70 4e 65 78 74 2c 20 78 2b 31 29  tate(pNext, x+1)
20c0: 3b 0a 20 20 20 20 20 20 20 20 20 20 62 72 65 61  ;.          brea
20d0: 6b 3b 0a 20 20 20 20 20 20 20 20 7d 0a 20 20 20  k;.        }.   
20e0: 20 20 20 20 20 63 61 73 65 20 52 45 5f 4f 50 5f       case RE_OP_
20f0: 4e 4f 54 44 49 47 49 54 3a 20 7b 0a 20 20 20 20  NOTDIGIT: {.    
2100: 20 20 20 20 20 20 69 66 28 20 21 72 65 5f 64 69        if( !re_di
2110: 67 69 74 5f 63 68 61 72 28 63 29 20 29 20 72 65  git_char(c) ) re
2120: 5f 61 64 64 5f 73 74 61 74 65 28 70 4e 65 78 74  _add_state(pNext
2130: 2c 20 78 2b 31 29 3b 0a 20 20 20 20 20 20 20 20  , x+1);.        
2140: 20 20 62 72 65 61 6b 3b 0a 20 20 20 20 20 20 20    break;.       
2150: 20 7d 0a 20 20 20 20 20 20 20 20 63 61 73 65 20   }.        case 
2160: 52 45 5f 4f 50 5f 53 50 41 43 45 3a 20 7b 0a 20  RE_OP_SPACE: {. 
2170: 20 20 20 20 20 20 20 20 20 69 66 28 20 72 65 5f           if( re_
2180: 73 70 61 63 65 5f 63 68 61 72 28 63 29 20 29 20  space_char(c) ) 
2190: 72 65 5f 61 64 64 5f 73 74 61 74 65 28 70 4e 65  re_add_state(pNe
21a0: 78 74 2c 20 78 2b 31 29 3b 0a 20 20 20 20 20 20  xt, x+1);.      
21b0: 20 20 20 20 62 72 65 61 6b 3b 0a 20 20 20 20 20      break;.     
21c0: 20 20 20 7d 0a 20 20 20 20 20 20 20 20 63 61 73     }.        cas
21d0: 65 20 52 45 5f 4f 50 5f 4e 4f 54 53 50 41 43 45  e RE_OP_NOTSPACE
21e0: 3a 20 7b 0a 20 20 20 20 20 20 20 20 20 20 69 66  : {.          if
21f0: 28 20 21 72 65 5f 73 70 61 63 65 5f 63 68 61 72  ( !re_space_char
2200: 28 63 29 20 29 20 72 65 5f 61 64 64 5f 73 74 61  (c) ) re_add_sta
2210: 74 65 28 70 4e 65 78 74 2c 20 78 2b 31 29 3b 0a  te(pNext, x+1);.
2220: 20 20 20 20 20 20 20 20 20 20 62 72 65 61 6b 3b            break;
2230: 0a 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20  .        }.     
2240: 20 20 20 63 61 73 65 20 52 45 5f 4f 50 5f 42 4f     case RE_OP_BO
2250: 55 4e 44 41 52 59 3a 20 7b 0a 20 20 20 20 20 20  UNDARY: {.      
2260: 20 20 20 20 69 66 28 20 72 65 5f 77 6f 72 64 5f      if( re_word_
2270: 63 68 61 72 28 63 29 21 3d 72 65 5f 77 6f 72 64  char(c)!=re_word
2280: 5f 63 68 61 72 28 63 50 72 65 76 29 20 29 20 72  _char(cPrev) ) r
2290: 65 5f 61 64 64 5f 73 74 61 74 65 28 70 54 68 69  e_add_state(pThi
22a0: 73 2c 20 78 2b 31 29 3b 0a 20 20 20 20 20 20 20  s, x+1);.       
22b0: 20 20 20 62 72 65 61 6b 3b 0a 20 20 20 20 20 20     break;.      
22c0: 20 20 7d 0a 20 20 20 20 20 20 20 20 63 61 73 65    }.        case
22d0: 20 52 45 5f 4f 50 5f 41 4e 59 53 54 41 52 3a 20   RE_OP_ANYSTAR: 
22e0: 7b 0a 20 20 20 20 20 20 20 20 20 20 72 65 5f 61  {.          re_a
22f0: 64 64 5f 73 74 61 74 65 28 70 4e 65 78 74 2c 20  dd_state(pNext, 
2300: 78 29 3b 0a 20 20 20 20 20 20 20 20 20 20 72 65  x);.          re
2310: 5f 61 64 64 5f 73 74 61 74 65 28 70 54 68 69 73  _add_state(pThis
2320: 2c 20 78 2b 31 29 3b 0a 20 20 20 20 20 20 20 20  , x+1);.        
2330: 20 20 62 72 65 61 6b 3b 0a 20 20 20 20 20 20 20    break;.       
2340: 20 7d 0a 20 20 20 20 20 20 20 20 63 61 73 65 20   }.        case 
2350: 52 45 5f 4f 50 5f 46 4f 52 4b 3a 20 7b 0a 20 20  RE_OP_FORK: {.  
2360: 20 20 20 20 20 20 20 20 72 65 5f 61 64 64 5f 73          re_add_s
2370: 74 61 74 65 28 70 54 68 69 73 2c 20 78 2b 70 52  tate(pThis, x+pR
2380: 65 2d 3e 61 41 72 67 5b 78 5d 29 3b 0a 20 20 20  e->aArg[x]);.   
2390: 20 20 20 20 20 20 20 72 65 5f 61 64 64 5f 73 74         re_add_st
23a0: 61 74 65 28 70 54 68 69 73 2c 20 78 2b 31 29 3b  ate(pThis, x+1);
23b0: 0a 20 20 20 20 20 20 20 20 20 20 62 72 65 61 6b  .          break
23c0: 3b 0a 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20  ;.        }.    
23d0: 20 20 20 20 63 61 73 65 20 52 45 5f 4f 50 5f 47      case RE_OP_G
23e0: 4f 54 4f 3a 20 7b 0a 20 20 20 20 20 20 20 20 20  OTO: {.         
23f0: 20 72 65 5f 61 64 64 5f 73 74 61 74 65 28 70 54   re_add_state(pT
2400: 68 69 73 2c 20 78 2b 70 52 65 2d 3e 61 41 72 67  his, x+pRe->aArg
2410: 5b 78 5d 29 3b 0a 20 20 20 20 20 20 20 20 20 20  [x]);.          
2420: 62 72 65 61 6b 3b 0a 20 20 20 20 20 20 20 20 7d  break;.        }
2430: 0a 20 20 20 20 20 20 20 20 63 61 73 65 20 52 45  .        case RE
2440: 5f 4f 50 5f 41 43 43 45 50 54 3a 20 7b 0a 20 20  _OP_ACCEPT: {.  
2450: 20 20 20 20 20 20 20 20 72 63 20 3d 20 31 3b 0a          rc = 1;.
2460: 20 20 20 20 20 20 20 20 20 20 67 6f 74 6f 20 72            goto r
2470: 65 5f 65 78 65 63 5f 65 6e 64 3b 0a 20 20 20 20  e_exec_end;.    
2480: 20 20 20 20 7d 0a 20 20 20 20 20 20 20 20 63 61      }.        ca
2490: 73 65 20 52 45 5f 4f 50 5f 43 43 5f 49 4e 43 3a  se RE_OP_CC_INC:
24a0: 0a 20 20 20 20 20 20 20 20 63 61 73 65 20 52 45  .        case RE
24b0: 5f 4f 50 5f 43 43 5f 45 58 43 3a 20 7b 0a 20 20  _OP_CC_EXC: {.  
24c0: 20 20 20 20 20 20 20 20 69 6e 74 20 6a 20 3d 20          int j = 
24d0: 31 3b 0a 20 20 20 20 20 20 20 20 20 20 69 6e 74  1;.          int
24e0: 20 6e 20 3d 20 70 52 65 2d 3e 61 41 72 67 5b 78   n = pRe->aArg[x
24f0: 5d 3b 0a 20 20 20 20 20 20 20 20 20 20 69 6e 74  ];.          int
2500: 20 68 69 74 20 3d 20 30 3b 0a 20 20 20 20 20 20   hit = 0;.      
2510: 20 20 20 20 66 6f 72 28 6a 3d 31 3b 20 6a 3e 30      for(j=1; j>0
2520: 20 26 26 20 6a 3c 6e 3b 20 6a 2b 2b 29 7b 0a 20   && j<n; j++){. 
2530: 20 20 20 20 20 20 20 20 20 20 20 69 66 28 20 70             if( p
2540: 52 65 2d 3e 61 4f 70 5b 78 2b 6a 5d 3d 3d 52 45  Re->aOp[x+j]==RE
2550: 5f 4f 50 5f 43 43 5f 56 41 4c 55 45 20 29 7b 0a  _OP_CC_VALUE ){.
2560: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 69 66                if
2570: 28 20 70 52 65 2d 3e 61 41 72 67 5b 78 2b 6a 5d  ( pRe->aArg[x+j]
2580: 3d 3d 63 20 29 7b 0a 20 20 20 20 20 20 20 20 20  ==c ){.         
2590: 20 20 20 20 20 20 20 68 69 74 20 3d 20 31 3b 0a         hit = 1;.
25a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
25b0: 6a 20 3d 20 2d 31 3b 0a 20 20 20 20 20 20 20 20  j = -1;.        
25c0: 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 20 20        }.        
25d0: 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20      }else{.     
25e0: 20 20 20 20 20 20 20 20 20 69 66 28 20 70 52 65           if( pRe
25f0: 2d 3e 61 41 72 67 5b 78 2b 6a 5d 3c 3d 63 20 26  ->aArg[x+j]<=c &
2600: 26 20 70 52 65 2d 3e 61 41 72 67 5b 78 2b 6a 2b  & pRe->aArg[x+j+
2610: 31 5d 3e 3d 63 20 29 7b 0a 20 20 20 20 20 20 20  1]>=c ){.       
2620: 20 20 20 20 20 20 20 20 20 68 69 74 20 3d 20 31           hit = 1
2630: 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ;.              
2640: 20 20 6a 20 3d 20 2d 31 3b 0a 20 20 20 20 20 20    j = -1;.      
2650: 20 20 20 20 20 20 20 20 7d 65 6c 73 65 7b 0a 20          }else{. 
2660: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 6a                 j
2670: 2b 2b 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20  ++;.            
2680: 20 20 7d 0a 20 20 20 20 20 20 20 20 20 20 20 20    }.            
2690: 7d 0a 20 20 20 20 20 20 20 20 20 20 7d 0a 20 20  }.          }.  
26a0: 20 20 20 20 20 20 20 20 69 66 28 20 70 52 65 2d          if( pRe-
26b0: 3e 61 4f 70 5b 78 5d 3d 3d 52 45 5f 4f 50 5f 43  >aOp[x]==RE_OP_C
26c0: 43 5f 45 58 43 20 29 20 68 69 74 20 3d 20 21 68  C_EXC ) hit = !h
26d0: 69 74 3b 0a 20 20 20 20 20 20 20 20 20 20 69 66  it;.          if
26e0: 28 20 68 69 74 20 29 20 72 65 5f 61 64 64 5f 73  ( hit ) re_add_s
26f0: 74 61 74 65 28 70 4e 65 78 74 2c 20 78 2b 6e 29  tate(pNext, x+n)
2700: 3b 0a 20 20 20 20 20 20 20 20 20 20 62 72 65 61  ;.          brea
2710: 6b 3b 20 20 20 20 20 20 20 20 20 20 20 20 0a 20  k;            . 
2720: 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 7d         }.      }
2730: 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20 66 6f 72  .    }.  }.  for
2740: 28 69 3d 30 3b 20 69 3c 70 4e 65 78 74 2d 3e 6e  (i=0; i<pNext->n
2750: 53 74 61 74 65 3b 20 69 2b 2b 29 7b 0a 20 20 20  State; i++){.   
2760: 20 69 66 28 20 70 52 65 2d 3e 61 4f 70 5b 70 4e   if( pRe->aOp[pN
2770: 65 78 74 2d 3e 61 53 74 61 74 65 5b 69 5d 5d 3d  ext->aState[i]]=
2780: 3d 52 45 5f 4f 50 5f 41 43 43 45 50 54 20 29 7b  =RE_OP_ACCEPT ){
2790: 20 72 63 20 3d 20 31 3b 20 62 72 65 61 6b 3b 20   rc = 1; break; 
27a0: 7d 0a 20 20 7d 0a 72 65 5f 65 78 65 63 5f 65 6e  }.  }.re_exec_en
27b0: 64 3a 0a 20 20 66 72 65 65 28 70 54 6f 46 72 65  d:.  free(pToFre
27c0: 65 29 3b 0a 20 20 72 65 74 75 72 6e 20 72 63 3b  e);.  return rc;
27d0: 0a 7d 0a 0a 2f 2a 20 52 65 73 69 7a 65 20 74 68  .}../* Resize th
27e0: 65 20 6f 70 63 6f 64 65 20 61 6e 64 20 61 72 67  e opcode and arg
27f0: 75 6d 65 6e 74 20 61 72 72 61 79 73 20 66 6f 72  ument arrays for
2800: 20 61 6e 20 52 45 20 75 6e 64 65 72 20 63 6f 6e   an RE under con
2810: 73 74 72 75 63 74 69 6f 6e 2e 0a 2a 2f 0a 73 74  struction..*/.st
2820: 61 74 69 63 20 69 6e 74 20 72 65 5f 72 65 73 69  atic int re_resi
2830: 7a 65 28 52 65 43 6f 6d 70 69 6c 65 64 20 2a 70  ze(ReCompiled *p
2840: 2c 20 69 6e 74 20 4e 29 7b 0a 20 20 63 68 61 72  , int N){.  char
2850: 20 2a 61 4f 70 3b 0a 20 20 69 6e 74 20 2a 61 41   *aOp;.  int *aA
2860: 72 67 3b 0a 20 20 61 4f 70 20 3d 20 72 65 61 6c  rg;.  aOp = real
2870: 6c 6f 63 28 70 2d 3e 61 4f 70 2c 20 4e 2a 73 69  loc(p->aOp, N*si
2880: 7a 65 6f 66 28 70 2d 3e 61 4f 70 5b 30 5d 29 29  zeof(p->aOp[0]))
2890: 3b 0a 20 20 69 66 28 20 61 4f 70 3d 3d 30 20 29  ;.  if( aOp==0 )
28a0: 20 72 65 74 75 72 6e 20 31 3b 0a 20 20 70 2d 3e   return 1;.  p->
28b0: 61 4f 70 20 3d 20 61 4f 70 3b 0a 20 20 61 41 72  aOp = aOp;.  aAr
28c0: 67 20 3d 20 72 65 61 6c 6c 6f 63 28 70 2d 3e 61  g = realloc(p->a
28d0: 41 72 67 2c 20 4e 2a 73 69 7a 65 6f 66 28 70 2d  Arg, N*sizeof(p-
28e0: 3e 61 41 72 67 5b 30 5d 29 29 3b 0a 20 20 69 66  >aArg[0]));.  if
28f0: 28 20 61 41 72 67 3d 3d 30 20 29 20 72 65 74 75  ( aArg==0 ) retu
2900: 72 6e 20 31 3b 0a 20 20 70 2d 3e 61 41 72 67 20  rn 1;.  p->aArg 
2910: 3d 20 61 41 72 67 3b 0a 20 20 70 2d 3e 6e 41 6c  = aArg;.  p->nAl
2920: 6c 6f 63 20 3d 20 4e 3b 0a 20 20 72 65 74 75 72  loc = N;.  retur
2930: 6e 20 30 3b 0a 7d 0a 0a 2f 2a 20 49 6e 73 65 72  n 0;.}../* Inser
2940: 74 20 61 20 6e 65 77 20 6f 70 63 6f 64 65 20 61  t a new opcode a
2950: 6e 64 20 61 72 67 75 6d 65 6e 74 20 69 6e 74 6f  nd argument into
2960: 20 61 6e 20 52 45 20 75 6e 64 65 72 20 63 6f 6e   an RE under con
2970: 73 74 72 75 63 74 69 6f 6e 2e 20 20 54 68 65 0a  struction.  The.
2980: 2a 2a 20 69 6e 73 65 72 74 69 6f 6e 20 70 6f 69  ** insertion poi
2990: 6e 74 20 69 73 20 6a 75 73 74 20 70 72 69 6f 72  nt is just prior
29a0: 20 74 6f 20 65 78 69 73 74 69 6e 67 20 6f 70 63   to existing opc
29b0: 6f 64 65 20 69 42 65 66 6f 72 65 2e 0a 2a 2f 0a  ode iBefore..*/.
29c0: 73 74 61 74 69 63 20 69 6e 74 20 72 65 5f 69 6e  static int re_in
29d0: 73 65 72 74 28 52 65 43 6f 6d 70 69 6c 65 64 20  sert(ReCompiled 
29e0: 2a 70 2c 20 69 6e 74 20 69 42 65 66 6f 72 65 2c  *p, int iBefore,
29f0: 20 69 6e 74 20 6f 70 2c 20 69 6e 74 20 61 72 67   int op, int arg
2a00: 29 7b 0a 20 20 69 6e 74 20 69 3b 0a 20 20 69 66  ){.  int i;.  if
2a10: 28 20 70 2d 3e 6e 41 6c 6c 6f 63 3c 3d 70 2d 3e  ( p->nAlloc<=p->
2a20: 6e 53 74 61 74 65 20 26 26 20 72 65 5f 72 65 73  nState && re_res
2a30: 69 7a 65 28 70 2c 20 70 2d 3e 6e 41 6c 6c 6f 63  ize(p, p->nAlloc
2a40: 2a 32 29 20 29 20 72 65 74 75 72 6e 20 30 3b 0a  *2) ) return 0;.
2a50: 20 20 66 6f 72 28 69 3d 70 2d 3e 6e 53 74 61 74    for(i=p->nStat
2a60: 65 3b 20 69 3e 69 42 65 66 6f 72 65 3b 20 69 2d  e; i>iBefore; i-
2a70: 2d 29 7b 0a 20 20 20 20 70 2d 3e 61 4f 70 5b 69  -){.    p->aOp[i
2a80: 5d 20 3d 20 70 2d 3e 61 4f 70 5b 69 2d 31 5d 3b  ] = p->aOp[i-1];
2a90: 0a 20 20 20 20 70 2d 3e 61 41 72 67 5b 69 5d 20  .    p->aArg[i] 
2aa0: 3d 20 70 2d 3e 61 41 72 67 5b 69 2d 31 5d 3b 0a  = p->aArg[i-1];.
2ab0: 20 20 7d 0a 20 20 70 2d 3e 6e 53 74 61 74 65 2b    }.  p->nState+
2ac0: 2b 3b 0a 20 20 70 2d 3e 61 4f 70 5b 69 42 65 66  +;.  p->aOp[iBef
2ad0: 6f 72 65 5d 20 3d 20 6f 70 3b 0a 20 20 70 2d 3e  ore] = op;.  p->
2ae0: 61 41 72 67 5b 69 42 65 66 6f 72 65 5d 20 3d 20  aArg[iBefore] = 
2af0: 61 72 67 3b 0a 20 20 72 65 74 75 72 6e 20 69 42  arg;.  return iB
2b00: 65 66 6f 72 65 3b 0a 7d 0a 0a 2f 2a 20 41 70 70  efore;.}../* App
2b10: 65 6e 64 20 61 20 6e 65 77 20 6f 70 63 6f 64 65  end a new opcode
2b20: 20 61 6e 64 20 61 72 67 75 6d 65 6e 74 20 74 6f   and argument to
2b30: 20 74 68 65 20 65 6e 64 20 6f 66 20 74 68 65 20   the end of the 
2b40: 52 45 20 75 6e 64 65 72 20 63 6f 6e 73 74 72 75  RE under constru
2b50: 63 74 69 6f 6e 2e 0a 2a 2f 0a 73 74 61 74 69 63  ction..*/.static
2b60: 20 69 6e 74 20 72 65 5f 61 70 70 65 6e 64 28 52   int re_append(R
2b70: 65 43 6f 6d 70 69 6c 65 64 20 2a 70 2c 20 69 6e  eCompiled *p, in
2b80: 74 20 6f 70 2c 20 69 6e 74 20 61 72 67 29 7b 0a  t op, int arg){.
2b90: 20 20 72 65 74 75 72 6e 20 72 65 5f 69 6e 73 65    return re_inse
2ba0: 72 74 28 70 2c 20 70 2d 3e 6e 53 74 61 74 65 2c  rt(p, p->nState,
2bb0: 20 6f 70 2c 20 61 72 67 29 3b 0a 7d 0a 0a 2f 2a   op, arg);.}../*
2bc0: 20 4d 61 6b 65 20 61 20 63 6f 70 79 20 6f 66 20   Make a copy of 
2bd0: 4e 20 6f 70 63 6f 64 65 73 20 73 74 61 72 74 69  N opcodes starti
2be0: 6e 67 20 61 74 20 69 53 74 61 72 74 20 6f 6e 74  ng at iStart ont
2bf0: 6f 20 74 68 65 20 65 6e 64 20 6f 66 20 74 68 65  o the end of the
2c00: 20 52 45 0a 2a 2a 20 75 6e 64 65 72 20 63 6f 6e   RE.** under con
2c10: 73 74 72 75 63 74 69 6f 6e 2e 0a 2a 2f 0a 73 74  struction..*/.st
2c20: 61 74 69 63 20 76 6f 69 64 20 72 65 5f 63 6f 70  atic void re_cop
2c30: 79 28 52 65 43 6f 6d 70 69 6c 65 64 20 2a 70 2c  y(ReCompiled *p,
2c40: 20 69 6e 74 20 69 53 74 61 72 74 2c 20 69 6e 74   int iStart, int
2c50: 20 4e 29 7b 0a 20 20 69 66 28 20 70 2d 3e 6e 53   N){.  if( p->nS
2c60: 74 61 74 65 2b 4e 3e 3d 70 2d 3e 6e 41 6c 6c 6f  tate+N>=p->nAllo
2c70: 63 20 26 26 20 72 65 5f 72 65 73 69 7a 65 28 70  c && re_resize(p
2c80: 2c 20 70 2d 3e 6e 41 6c 6c 6f 63 2a 32 2b 4e 29  , p->nAlloc*2+N)
2c90: 20 29 20 72 65 74 75 72 6e 3b 0a 20 20 6d 65 6d   ) return;.  mem
2ca0: 63 70 79 28 26 70 2d 3e 61 4f 70 5b 70 2d 3e 6e  cpy(&p->aOp[p->n
2cb0: 53 74 61 74 65 5d 2c 20 26 70 2d 3e 61 4f 70 5b  State], &p->aOp[
2cc0: 69 53 74 61 72 74 5d 2c 20 4e 2a 73 69 7a 65 6f  iStart], N*sizeo
2cd0: 66 28 70 2d 3e 61 4f 70 5b 30 5d 29 29 3b 0a 20  f(p->aOp[0]));. 
2ce0: 20 6d 65 6d 63 70 79 28 26 70 2d 3e 61 41 72 67   memcpy(&p->aArg
2cf0: 5b 70 2d 3e 6e 53 74 61 74 65 5d 2c 20 26 70 2d  [p->nState], &p-
2d00: 3e 61 41 72 67 5b 69 53 74 61 72 74 5d 2c 20 4e  >aArg[iStart], N
2d10: 2a 73 69 7a 65 6f 66 28 70 2d 3e 61 41 72 67 5b  *sizeof(p->aArg[
2d20: 30 5d 29 29 3b 0a 20 20 70 2d 3e 6e 53 74 61 74  0]));.  p->nStat
2d30: 65 20 2b 3d 20 4e 3b 0a 7d 0a 0a 2f 2a 20 52 65  e += N;.}../* Re
2d40: 74 75 72 6e 20 74 72 75 65 20 69 66 20 63 20 69  turn true if c i
2d50: 73 20 61 20 68 65 78 61 64 65 63 69 6d 61 6c 20  s a hexadecimal 
2d60: 64 69 67 69 74 20 63 68 61 72 61 63 74 65 72 3a  digit character:
2d70: 20 20 5b 30 2d 39 61 2d 66 41 2d 46 5d 0a 2a 2a    [0-9a-fA-F].**
2d80: 20 49 66 20 63 20 69 73 20 61 20 68 65 78 20 64   If c is a hex d
2d90: 69 67 69 74 2c 20 61 6c 73 6f 20 73 65 74 20 2a  igit, also set *
2da0: 70 56 20 3d 20 28 2a 70 56 29 2a 31 36 20 2b 20  pV = (*pV)*16 + 
2db0: 76 61 6c 75 65 6f 66 28 63 29 2e 20 20 49 66 0a  valueof(c).  If.
2dc0: 2a 2a 20 63 20 69 73 20 6e 6f 74 20 61 20 68 65  ** c is not a he
2dd0: 78 20 64 69 67 69 74 20 2a 70 56 20 69 73 20 75  x digit *pV is u
2de0: 6e 63 68 61 6e 67 65 64 2e 0a 2a 2f 0a 73 74 61  nchanged..*/.sta
2df0: 74 69 63 20 69 6e 74 20 72 65 5f 68 65 78 28 69  tic int re_hex(i
2e00: 6e 74 20 63 2c 20 69 6e 74 20 2a 70 56 29 7b 0a  nt c, int *pV){.
2e10: 20 20 69 66 28 20 63 3e 3d 27 30 27 20 26 26 20    if( c>='0' && 
2e20: 63 3c 3d 27 39 27 20 29 7b 0a 20 20 20 20 63 20  c<='9' ){.    c 
2e30: 2d 3d 20 27 30 27 3b 0a 20 20 7d 65 6c 73 65 20  -= '0';.  }else 
2e40: 69 66 28 20 63 3e 3d 27 61 27 20 26 26 20 63 3c  if( c>='a' && c<
2e50: 3d 27 66 27 20 29 7b 0a 20 20 20 20 63 20 2d 3d  ='f' ){.    c -=
2e60: 20 27 61 27 20 2b 20 31 30 3b 0a 20 20 7d 65 6c   'a' + 10;.  }el
2e70: 73 65 20 69 66 28 20 63 3e 3d 27 41 27 20 26 26  se if( c>='A' &&
2e80: 20 63 3c 3d 27 46 27 20 29 7b 0a 20 20 20 20 63   c<='F' ){.    c
2e90: 20 2d 3d 20 27 41 27 20 2b 20 31 30 3b 0a 20 20   -= 'A' + 10;.  
2ea0: 7d 65 6c 73 65 7b 0a 20 20 20 20 72 65 74 75 72  }else{.    retur
2eb0: 6e 20 30 3b 0a 20 20 7d 0a 20 20 2a 70 56 20 3d  n 0;.  }.  *pV =
2ec0: 20 28 2a 70 56 29 2a 31 36 20 2b 20 63 3b 0a 20   (*pV)*16 + c;. 
2ed0: 20 72 65 74 75 72 6e 20 31 3b 0a 7d 0a 0a 2f 2a   return 1;.}../*
2ee0: 20 41 20 62 61 63 6b 73 6c 61 73 68 20 63 68 61   A backslash cha
2ef0: 72 61 63 74 65 72 20 68 61 73 20 62 65 65 6e 20  racter has been 
2f00: 73 65 65 6e 2c 20 72 65 61 64 20 74 68 65 20 6e  seen, read the n
2f10: 65 78 74 20 63 68 61 72 61 63 74 65 72 20 61 6e  ext character an
2f20: 64 0a 2a 2a 20 72 65 74 75 72 6e 20 69 74 73 20  d.** return its 
2f30: 69 6e 74 65 70 72 65 74 61 74 69 6f 6e 2e 0a 2a  intepretation..*
2f40: 2f 0a 73 74 61 74 69 63 20 75 6e 73 69 67 6e 65  /.static unsigne
2f50: 64 20 72 65 5f 65 73 63 5f 63 68 61 72 28 52 65  d re_esc_char(Re
2f60: 43 6f 6d 70 69 6c 65 64 20 2a 70 29 7b 0a 20 20  Compiled *p){.  
2f70: 73 74 61 74 69 63 20 63 6f 6e 73 74 20 63 68 61  static const cha
2f80: 72 20 7a 45 73 63 5b 5d 20 3d 20 22 61 66 6e 72  r zEsc[] = "afnr
2f90: 74 76 5c 5c 28 29 2a 2e 2b 3f 5b 24 5e 7b 7c 22  tv\\()*.+?[$^{|"
2fa0: 3b 0a 20 20 73 74 61 74 69 63 20 63 6f 6e 73 74  ;.  static const
2fb0: 20 63 68 61 72 20 7a 54 72 61 6e 73 5b 5d 20 3d   char zTrans[] =
2fc0: 20 22 5c 61 5c 66 5c 6e 5c 72 5c 74 5c 76 22 3b   "\a\f\n\r\t\v";
2fd0: 0a 20 20 69 6e 74 20 69 2c 20 76 20 3d 20 30 3b  .  int i, v = 0;
2fe0: 0a 20 20 63 68 61 72 20 63 20 3d 20 70 2d 3e 7a  .  char c = p->z
2ff0: 49 6e 5b 30 5d 3b 0a 20 20 69 66 28 20 63 3d 3d  In[0];.  if( c==
3000: 27 75 27 20 29 7b 0a 20 20 20 20 76 20 3d 20 30  'u' ){.    v = 0
3010: 3b 0a 20 20 20 20 69 66 28 20 72 65 5f 68 65 78  ;.    if( re_hex
3020: 28 70 2d 3e 7a 49 6e 5b 31 5d 2c 26 76 29 0a 20  (p->zIn[1],&v). 
3030: 20 20 20 20 26 26 20 72 65 5f 68 65 78 28 70 2d      && re_hex(p-
3040: 3e 7a 49 6e 5b 32 5d 2c 26 76 29 0a 20 20 20 20  >zIn[2],&v).    
3050: 20 26 26 20 72 65 5f 68 65 78 28 70 2d 3e 7a 49   && re_hex(p->zI
3060: 6e 5b 33 5d 2c 26 76 29 0a 20 20 20 20 20 26 26  n[3],&v).     &&
3070: 20 72 65 5f 68 65 78 28 70 2d 3e 7a 49 6e 5b 34   re_hex(p->zIn[4
3080: 5d 2c 26 76 29 0a 20 20 20 20 29 7b 0a 20 20 20  ],&v).    ){.   
3090: 20 20 20 70 2d 3e 7a 49 6e 20 2b 3d 20 35 3b 0a     p->zIn += 5;.
30a0: 20 20 20 20 20 20 72 65 74 75 72 6e 20 76 3b 0a        return v;.
30b0: 20 20 20 20 7d 0a 20 20 7d 0a 20 20 69 66 28 20      }.  }.  if( 
30c0: 63 3d 3d 27 78 27 20 29 7b 0a 20 20 20 20 76 20  c=='x' ){.    v 
30d0: 3d 20 30 3b 0a 20 20 20 20 66 6f 72 28 69 3d 31  = 0;.    for(i=1
30e0: 3b 20 72 65 5f 68 65 78 28 70 2d 3e 7a 49 6e 5b  ; re_hex(p->zIn[
30f0: 69 5d 2c 20 26 76 29 3b 20 69 2b 2b 29 7b 7d 0a  i], &v); i++){}.
3100: 20 20 20 20 69 66 28 20 69 3e 31 20 29 7b 0a 20      if( i>1 ){. 
3110: 20 20 20 20 20 70 2d 3e 7a 49 6e 20 2b 3d 20 69       p->zIn += i
3120: 3b 0a 20 20 20 20 20 20 72 65 74 75 72 6e 20 76  ;.      return v
3130: 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20 66 6f  ;.    }.  }.  fo
3140: 72 28 69 3d 30 3b 20 7a 45 73 63 5b 69 5d 20 26  r(i=0; zEsc[i] &
3150: 26 20 7a 45 73 63 5b 69 5d 21 3d 63 3b 20 69 2b  & zEsc[i]!=c; i+
3160: 2b 29 7b 7d 0a 20 20 69 66 28 20 7a 45 73 63 5b  +){}.  if( zEsc[
3170: 69 5d 20 29 7b 0a 20 20 20 20 69 66 28 20 63 3c  i] ){.    if( c<
3180: 36 20 29 20 63 20 3d 20 7a 54 72 61 6e 73 5b 69  6 ) c = zTrans[i
3190: 5d 3b 0a 20 20 20 20 70 2d 3e 7a 49 6e 2b 2b 3b  ];.    p->zIn++;
31a0: 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 70 2d  .  }else{.    p-
31b0: 3e 7a 45 72 72 20 3d 20 22 75 6e 6b 6e 6f 77 6e  >zErr = "unknown
31c0: 20 5c 5c 20 65 73 63 61 70 65 22 3b 0a 20 20 7d   \\ escape";.  }
31d0: 0a 20 20 72 65 74 75 72 6e 20 63 3b 0a 7d 0a 0a  .  return c;.}..
31e0: 2f 2a 20 46 6f 72 77 61 72 64 20 64 65 63 6c 61  /* Forward decla
31f0: 72 61 74 69 6f 6e 20 2a 2f 0a 73 74 61 74 69 63  ration */.static
3200: 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 72 65 5f   const char *re_
3210: 73 75 62 63 6f 6d 70 69 6c 65 5f 73 74 72 69 6e  subcompile_strin
3220: 67 28 52 65 43 6f 6d 70 69 6c 65 64 2a 29 3b 0a  g(ReCompiled*);.
3230: 0a 2f 2a 20 43 6f 6d 70 69 6c 65 20 52 45 20 74  ./* Compile RE t
3240: 65 78 74 20 69 6e 74 6f 20 61 20 73 65 71 75 65  ext into a seque
3250: 6e 63 65 20 6f 66 20 6f 70 63 6f 64 65 73 2e 20  nce of opcodes. 
3260: 20 43 6f 6e 74 69 6e 75 65 20 75 70 20 74 6f 20   Continue up to 
3270: 74 68 65 0a 2a 2a 20 66 69 72 73 74 20 75 6e 6d  the.** first unm
3280: 61 74 63 68 65 64 20 22 29 22 20 63 68 61 72 61  atched ")" chara
3290: 63 74 65 72 2c 20 74 68 65 6e 20 72 65 74 75 72  cter, then retur
32a0: 6e 2e 20 20 49 66 20 61 6e 20 65 72 72 6f 72 20  n.  If an error 
32b0: 69 73 20 66 6f 75 6e 64 2c 0a 2a 2a 20 72 65 74  is found,.** ret
32c0: 75 72 6e 20 61 20 70 6f 69 6e 74 65 72 20 74 6f  urn a pointer to
32d0: 20 74 68 65 20 65 72 72 6f 72 20 6d 65 73 73 61   the error messa
32e0: 67 65 20 73 74 72 69 6e 67 2e 0a 2a 2f 0a 73 74  ge string..*/.st
32f0: 61 74 69 63 20 63 6f 6e 73 74 20 63 68 61 72 20  atic const char 
3300: 2a 72 65 5f 73 75 62 63 6f 6d 70 69 6c 65 5f 72  *re_subcompile_r
3310: 65 28 52 65 43 6f 6d 70 69 6c 65 64 20 2a 70 29  e(ReCompiled *p)
3320: 7b 0a 20 20 63 6f 6e 73 74 20 63 68 61 72 20 2a  {.  const char *
3330: 7a 45 72 72 3b 0a 20 20 69 6e 74 20 69 53 74 61  zErr;.  int iSta
3340: 72 74 2c 20 69 45 6e 64 2c 20 69 47 6f 74 6f 3b  rt, iEnd, iGoto;
3350: 0a 20 20 69 53 74 61 72 74 20 3d 20 70 2d 3e 6e  .  iStart = p->n
3360: 53 74 61 74 65 3b 0a 20 20 7a 45 72 72 20 3d 20  State;.  zErr = 
3370: 72 65 5f 73 75 62 63 6f 6d 70 69 6c 65 5f 73 74  re_subcompile_st
3380: 72 69 6e 67 28 70 29 3b 0a 20 20 69 66 28 20 7a  ring(p);.  if( z
3390: 45 72 72 20 29 20 72 65 74 75 72 6e 20 7a 45 72  Err ) return zEr
33a0: 72 3b 0a 20 20 77 68 69 6c 65 28 20 70 2d 3e 7a  r;.  while( p->z
33b0: 49 6e 5b 30 5d 3d 3d 27 7c 27 20 29 7b 0a 20 20  In[0]=='|' ){.  
33c0: 20 20 69 45 6e 64 20 3d 20 70 2d 3e 6e 53 74 61    iEnd = p->nSta
33d0: 74 65 3b 0a 20 20 20 20 72 65 5f 69 6e 73 65 72  te;.    re_inser
33e0: 74 28 70 2c 20 69 53 74 61 72 74 2c 20 52 45 5f  t(p, iStart, RE_
33f0: 4f 50 5f 46 4f 52 4b 2c 20 69 45 6e 64 20 2b 20  OP_FORK, iEnd + 
3400: 32 20 2d 20 69 53 74 61 72 74 29 3b 0a 20 20 20  2 - iStart);.   
3410: 20 69 47 6f 74 6f 20 3d 20 72 65 5f 61 70 70 65   iGoto = re_appe
3420: 6e 64 28 70 2c 20 52 45 5f 4f 50 5f 47 4f 54 4f  nd(p, RE_OP_GOTO
3430: 2c 20 30 29 3b 0a 20 20 20 20 70 2d 3e 7a 49 6e  , 0);.    p->zIn
3440: 2b 2b 3b 0a 20 20 20 20 7a 45 72 72 20 3d 20 72  ++;.    zErr = r
3450: 65 5f 73 75 62 63 6f 6d 70 69 6c 65 5f 73 74 72  e_subcompile_str
3460: 69 6e 67 28 70 29 3b 0a 20 20 20 20 69 66 28 20  ing(p);.    if( 
3470: 7a 45 72 72 20 29 20 72 65 74 75 72 6e 20 7a 45  zErr ) return zE
3480: 72 72 3b 0a 20 20 20 20 70 2d 3e 61 41 72 67 5b  rr;.    p->aArg[
3490: 69 47 6f 74 6f 5d 20 3d 20 70 2d 3e 6e 53 74 61  iGoto] = p->nSta
34a0: 74 65 20 2d 20 69 47 6f 74 6f 3b 0a 20 20 7d 0a  te - iGoto;.  }.
34b0: 20 20 72 65 74 75 72 6e 20 30 3b 0a 7d 0a 0a 2f    return 0;.}../
34c0: 2a 20 43 6f 6d 70 69 6c 65 20 61 6e 20 65 6c 65  * Compile an ele
34d0: 6d 65 6e 74 20 6f 66 20 72 65 67 75 6c 61 72 20  ment of regular 
34e0: 65 78 70 72 65 73 73 69 6f 6e 20 74 65 78 74 20  expression text 
34f0: 28 61 6e 79 74 68 69 6e 67 20 74 68 61 74 20 63  (anything that c
3500: 61 6e 20 62 65 0a 2a 2a 20 61 6e 20 6f 70 65 72  an be.** an oper
3510: 61 6e 64 20 74 6f 20 74 68 65 20 22 7c 22 20 6f  and to the "|" o
3520: 70 65 72 61 74 6f 72 29 2e 20 20 52 65 74 75 72  perator).  Retur
3530: 6e 20 4e 55 4c 4c 20 6f 6e 20 73 75 63 63 65 73  n NULL on succes
3540: 73 20 6f 72 20 61 20 70 6f 69 6e 74 65 72 0a 2a  s or a pointer.*
3550: 2a 20 74 6f 20 74 68 65 20 65 72 72 6f 72 20 6d  * to the error m
3560: 65 73 73 61 67 65 20 69 66 20 74 68 65 72 65 20  essage if there 
3570: 69 73 20 61 20 70 72 6f 62 6c 65 6d 2e 0a 2a 2f  is a problem..*/
3580: 0a 73 74 61 74 69 63 20 63 6f 6e 73 74 20 63 68  .static const ch
3590: 61 72 20 2a 72 65 5f 73 75 62 63 6f 6d 70 69 6c  ar *re_subcompil
35a0: 65 5f 73 74 72 69 6e 67 28 52 65 43 6f 6d 70 69  e_string(ReCompi
35b0: 6c 65 64 20 2a 70 29 7b 0a 20 20 69 6e 74 20 69  led *p){.  int i
35c0: 50 72 65 76 20 3d 20 2d 31 3b 0a 20 20 69 6e 74  Prev = -1;.  int
35d0: 20 69 53 74 61 72 74 3b 0a 20 20 75 6e 73 69 67   iStart;.  unsig
35e0: 6e 65 64 20 63 3b 0a 20 20 63 6f 6e 73 74 20 63  ned c;.  const c
35f0: 68 61 72 20 2a 7a 45 72 72 3b 0a 20 20 77 68 69  har *zErr;.  whi
3600: 6c 65 28 20 28 63 20 3d 20 72 65 5f 6e 65 78 74  le( (c = re_next
3610: 5f 63 68 61 72 28 26 70 2d 3e 7a 49 6e 29 29 21  _char(&p->zIn))!
3620: 3d 30 20 29 7b 0a 20 20 20 20 69 53 74 61 72 74  =0 ){.    iStart
3630: 20 3d 20 70 2d 3e 6e 53 74 61 74 65 3b 0a 20 20   = p->nState;.  
3640: 20 20 73 77 69 74 63 68 28 20 63 20 29 7b 0a 20    switch( c ){. 
3650: 20 20 20 20 20 63 61 73 65 20 27 7c 27 3a 0a 20       case '|':. 
3660: 20 20 20 20 20 63 61 73 65 20 27 24 27 3a 20 0a       case '$': .
3670: 20 20 20 20 20 20 63 61 73 65 20 27 29 27 3a 20        case ')': 
3680: 7b 0a 20 20 20 20 20 20 20 20 70 2d 3e 7a 49 6e  {.        p->zIn
3690: 2d 2d 3b 0a 20 20 20 20 20 20 20 20 72 65 74 75  --;.        retu
36a0: 72 6e 20 30 3b 0a 20 20 20 20 20 20 7d 0a 20 20  rn 0;.      }.  
36b0: 20 20 20 20 63 61 73 65 20 27 28 27 3a 20 7b 0a      case '(': {.
36c0: 20 20 20 20 20 20 20 20 7a 45 72 72 20 3d 20 72          zErr = r
36d0: 65 5f 73 75 62 63 6f 6d 70 69 6c 65 5f 72 65 28  e_subcompile_re(
36e0: 70 29 3b 0a 20 20 20 20 20 20 20 20 69 66 28 20  p);.        if( 
36f0: 7a 45 72 72 20 29 20 72 65 74 75 72 6e 20 7a 45  zErr ) return zE
3700: 72 72 3b 0a 20 20 20 20 20 20 20 20 69 66 28 20  rr;.        if( 
3710: 70 2d 3e 7a 49 6e 5b 30 5d 21 3d 27 29 27 20 29  p->zIn[0]!=')' )
3720: 20 72 65 74 75 72 6e 20 22 75 6e 6d 61 74 63 68   return "unmatch
3730: 65 64 20 27 28 27 22 3b 0a 20 20 20 20 20 20 20  ed '('";.       
3740: 20 70 2d 3e 7a 49 6e 2b 2b 3b 0a 20 20 20 20 20   p->zIn++;.     
3750: 20 20 20 62 72 65 61 6b 3b 0a 20 20 20 20 20 20     break;.      
3760: 7d 0a 20 20 20 20 20 20 63 61 73 65 20 27 2e 27  }.      case '.'
3770: 3a 20 7b 0a 20 20 20 20 20 20 20 20 69 66 28 20  : {.        if( 
3780: 70 2d 3e 7a 49 6e 5b 30 5d 3d 3d 27 2a 27 20 29  p->zIn[0]=='*' )
3790: 7b 0a 20 20 20 20 20 20 20 20 20 20 72 65 5f 61  {.          re_a
37a0: 70 70 65 6e 64 28 70 2c 20 52 45 5f 4f 50 5f 41  ppend(p, RE_OP_A
37b0: 4e 59 53 54 41 52 2c 20 30 29 3b 0a 20 20 20 20  NYSTAR, 0);.    
37c0: 20 20 20 20 20 20 70 2d 3e 7a 49 6e 2b 2b 3b 0a        p->zIn++;.
37d0: 20 20 20 20 20 20 20 20 7d 65 6c 73 65 7b 20 0a          }else{ .
37e0: 20 20 20 20 20 20 20 20 20 20 72 65 5f 61 70 70            re_app
37f0: 65 6e 64 28 70 2c 20 52 45 5f 4f 50 5f 41 4e 59  end(p, RE_OP_ANY
3800: 2c 20 30 29 3b 0a 20 20 20 20 20 20 20 20 7d 0a  , 0);.        }.
3810: 20 20 20 20 20 20 20 20 62 72 65 61 6b 3b 0a 20          break;. 
3820: 20 20 20 20 20 7d 0a 20 20 20 20 20 20 63 61 73       }.      cas
3830: 65 20 27 2a 27 3a 20 7b 0a 20 20 20 20 20 20 20  e '*': {.       
3840: 20 69 66 28 20 69 50 72 65 76 3c 30 20 29 20 72   if( iPrev<0 ) r
3850: 65 74 75 72 6e 20 22 27 2a 27 20 77 69 74 68 6f  eturn "'*' witho
3860: 75 74 20 6f 70 65 72 61 6e 64 22 3b 0a 20 20 20  ut operand";.   
3870: 20 20 20 20 20 72 65 5f 69 6e 73 65 72 74 28 70       re_insert(p
3880: 2c 20 69 50 72 65 76 2c 20 52 45 5f 4f 50 5f 47  , iPrev, RE_OP_G
3890: 4f 54 4f 2c 20 70 2d 3e 6e 53 74 61 74 65 20 2d  OTO, p->nState -
38a0: 20 69 50 72 65 76 20 2b 20 31 29 3b 0a 20 20 20   iPrev + 1);.   
38b0: 20 20 20 20 20 72 65 5f 61 70 70 65 6e 64 28 70       re_append(p
38c0: 2c 20 52 45 5f 4f 50 5f 46 4f 52 4b 2c 20 69 50  , RE_OP_FORK, iP
38d0: 72 65 76 20 2d 20 70 2d 3e 6e 53 74 61 74 65 20  rev - p->nState 
38e0: 2b 20 31 29 3b 0a 20 20 20 20 20 20 20 20 62 72  + 1);.        br
38f0: 65 61 6b 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20  eak;.      }.   
3900: 20 20 20 63 61 73 65 20 27 2b 27 3a 20 7b 0a 20     case '+': {. 
3910: 20 20 20 20 20 20 20 69 66 28 20 69 50 72 65 76         if( iPrev
3920: 3c 30 20 29 20 72 65 74 75 72 6e 20 22 27 2b 27  <0 ) return "'+'
3930: 20 77 69 74 68 6f 75 74 20 6f 70 65 72 61 6e 64   without operand
3940: 22 3b 0a 20 20 20 20 20 20 20 20 72 65 5f 61 70  ";.        re_ap
3950: 70 65 6e 64 28 70 2c 20 52 45 5f 4f 50 5f 46 4f  pend(p, RE_OP_FO
3960: 52 4b 2c 20 69 50 72 65 76 20 2d 20 70 2d 3e 6e  RK, iPrev - p->n
3970: 53 74 61 74 65 29 3b 0a 20 20 20 20 20 20 20 20  State);.        
3980: 62 72 65 61 6b 3b 0a 20 20 20 20 20 20 7d 0a 20  break;.      }. 
3990: 20 20 20 20 20 63 61 73 65 20 27 3f 27 3a 20 7b       case '?': {
39a0: 0a 20 20 20 20 20 20 20 20 69 66 28 20 69 50 72  .        if( iPr
39b0: 65 76 3c 30 20 29 20 72 65 74 75 72 6e 20 22 27  ev<0 ) return "'
39c0: 3f 27 20 77 69 74 68 6f 75 74 20 6f 70 65 72 61  ?' without opera
39d0: 6e 64 22 3b 0a 20 20 20 20 20 20 20 20 72 65 5f  nd";.        re_
39e0: 69 6e 73 65 72 74 28 70 2c 20 69 50 72 65 76 2c  insert(p, iPrev,
39f0: 20 52 45 5f 4f 50 5f 46 4f 52 4b 2c 20 70 2d 3e   RE_OP_FORK, p->
3a00: 6e 53 74 61 74 65 20 2d 20 69 50 72 65 76 2b 31  nState - iPrev+1
3a10: 29 3b 0a 20 20 20 20 20 20 20 20 62 72 65 61 6b  );.        break
3a20: 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20  ;.      }.      
3a30: 63 61 73 65 20 27 7b 27 3a 20 7b 0a 20 20 20 20  case '{': {.    
3a40: 20 20 20 20 69 6e 74 20 6d 20 3d 20 30 2c 20 6e      int m = 0, n
3a50: 20 3d 20 30 3b 0a 20 20 20 20 20 20 20 20 69 6e   = 0;.        in
3a60: 74 20 73 7a 2c 20 6a 3b 0a 20 20 20 20 20 20 20  t sz, j;.       
3a70: 20 69 66 28 20 69 50 72 65 76 3c 30 20 29 20 72   if( iPrev<0 ) r
3a80: 65 74 75 72 6e 20 22 27 7b 6d 2c 6e 7d 27 20 77  eturn "'{m,n}' w
3a90: 69 74 68 6f 75 74 20 6f 70 65 72 61 6e 64 22 3b  ithout operand";
3aa0: 0a 20 20 20 20 20 20 20 20 77 68 69 6c 65 28 20  .        while( 
3ab0: 28 63 3d 70 2d 3e 7a 49 6e 5b 30 5d 29 3e 3d 27  (c=p->zIn[0])>='
3ac0: 30 27 20 26 26 20 63 3c 3d 27 39 27 20 29 7b 20  0' && c<='9' ){ 
3ad0: 6d 20 3d 20 6d 2a 31 30 20 2b 20 63 20 2d 20 27  m = m*10 + c - '
3ae0: 30 27 3b 20 70 2d 3e 7a 49 6e 2b 2b 3b 20 7d 0a  0'; p->zIn++; }.
3af0: 20 20 20 20 20 20 20 20 6e 20 3d 20 6d 3b 0a 20          n = m;. 
3b00: 20 20 20 20 20 20 20 69 66 28 20 63 3d 3d 27 2c         if( c==',
3b10: 27 20 29 7b 0a 20 20 20 20 20 20 20 20 20 20 70  ' ){.          p
3b20: 2d 3e 7a 49 6e 2b 2b 3b 0a 20 20 20 20 20 20 20  ->zIn++;.       
3b30: 20 20 20 6e 20 3d 20 30 3b 0a 20 20 20 20 20 20     n = 0;.      
3b40: 20 20 20 20 77 68 69 6c 65 28 20 28 63 3d 70 2d      while( (c=p-
3b50: 3e 7a 49 6e 5b 30 5d 29 3e 3d 27 30 27 20 26 26  >zIn[0])>='0' &&
3b60: 20 63 3c 3d 27 39 27 20 29 7b 20 6e 20 3d 20 6e   c<='9' ){ n = n
3b70: 2a 31 30 20 2b 20 63 20 2d 20 27 30 27 3b 20 70  *10 + c - '0'; p
3b80: 2d 3e 7a 49 6e 2b 2b 3b 20 7d 0a 20 20 20 20 20  ->zIn++; }.     
3b90: 20 20 20 7d 0a 20 20 20 20 20 20 20 20 69 66 28     }.        if(
3ba0: 20 63 21 3d 27 7d 27 20 29 20 72 65 74 75 72 6e   c!='}' ) return
3bb0: 20 22 75 6e 6d 61 74 63 68 65 64 20 27 7b 27 22   "unmatched '{'"
3bc0: 3b 0a 20 20 20 20 20 20 20 20 69 66 28 20 6e 3e  ;.        if( n>
3bd0: 30 20 26 26 20 6e 3c 6d 20 29 20 72 65 74 75 72  0 && n<m ) retur
3be0: 6e 20 22 6e 20 6c 65 73 73 20 74 68 61 6e 20 6d  n "n less than m
3bf0: 20 69 6e 20 27 7b 6d 2c 6e 7d 27 22 3b 0a 20 20   in '{m,n}'";.  
3c00: 20 20 20 20 20 20 70 2d 3e 7a 49 6e 2b 2b 3b 0a        p->zIn++;.
3c10: 20 20 20 20 20 20 20 20 73 7a 20 3d 20 70 2d 3e          sz = p->
3c20: 6e 53 74 61 74 65 20 2d 20 69 50 72 65 76 3b 0a  nState - iPrev;.
3c30: 20 20 20 20 20 20 20 20 69 66 28 20 6d 3d 3d 30          if( m==0
3c40: 20 29 7b 0a 20 20 20 20 20 20 20 20 20 20 69 66   ){.          if
3c50: 28 20 6e 3d 3d 30 20 29 20 72 65 74 75 72 6e 20  ( n==0 ) return 
3c60: 22 62 6f 74 68 20 6d 20 61 6e 64 20 6e 20 61 72  "both m and n ar
3c70: 65 20 7a 65 72 6f 20 69 6e 20 27 7b 6d 2c 6e 7d  e zero in '{m,n}
3c80: 27 22 3b 0a 20 20 20 20 20 20 20 20 20 20 72 65  '";.          re
3c90: 5f 69 6e 73 65 72 74 28 70 2c 20 69 50 72 65 76  _insert(p, iPrev
3ca0: 2c 20 52 45 5f 4f 50 5f 46 4f 52 4b 2c 20 73 7a  , RE_OP_FORK, sz
3cb0: 2b 31 29 3b 0a 20 20 20 20 20 20 20 20 20 20 6e  +1);.          n
3cc0: 2d 2d 3b 0a 20 20 20 20 20 20 20 20 7d 65 6c 73  --;.        }els
3cd0: 65 7b 0a 20 20 20 20 20 20 20 20 20 20 66 6f 72  e{.          for
3ce0: 28 6a 3d 31 3b 20 6a 3c 6d 3b 20 6a 2b 2b 29 20  (j=1; j<m; j++) 
3cf0: 72 65 5f 63 6f 70 79 28 70 2c 20 69 50 72 65 76  re_copy(p, iPrev
3d00: 2c 20 73 7a 29 3b 0a 20 20 20 20 20 20 20 20 7d  , sz);.        }
3d10: 0a 20 20 20 20 20 20 20 20 66 6f 72 28 6a 3d 6d  .        for(j=m
3d20: 3b 20 6a 3c 6e 3b 20 6a 2b 2b 29 7b 0a 20 20 20  ; j<n; j++){.   
3d30: 20 20 20 20 20 20 20 72 65 5f 61 70 70 65 6e 64         re_append
3d40: 28 70 2c 20 52 45 5f 4f 50 5f 46 4f 52 4b 2c 20  (p, RE_OP_FORK, 
3d50: 73 7a 2b 31 29 3b 0a 20 20 20 20 20 20 20 20 20  sz+1);.         
3d60: 20 72 65 5f 63 6f 70 79 28 70 2c 20 69 50 72 65   re_copy(p, iPre
3d70: 76 2c 20 73 7a 29 3b 0a 20 20 20 20 20 20 20 20  v, sz);.        
3d80: 7d 0a 20 20 20 20 20 20 20 20 69 66 28 20 6e 3d  }.        if( n=
3d90: 3d 30 20 26 26 20 6d 3e 30 20 29 7b 0a 20 20 20  =0 && m>0 ){.   
3da0: 20 20 20 20 20 20 20 72 65 5f 61 70 70 65 6e 64         re_append
3db0: 28 70 2c 20 52 45 5f 4f 50 5f 46 4f 52 4b 2c 20  (p, RE_OP_FORK, 
3dc0: 2d 73 7a 29 3b 0a 20 20 20 20 20 20 20 20 7d 0a  -sz);.        }.
3dd0: 20 20 20 20 20 20 20 20 62 72 65 61 6b 3b 0a 20          break;. 
3de0: 20 20 20 20 20 7d 0a 20 20 20 20 20 20 63 61 73       }.      cas
3df0: 65 20 27 5b 27 3a 20 7b 0a 20 20 20 20 20 20 20  e '[': {.       
3e00: 20 69 6e 74 20 69 46 69 72 73 74 20 3d 20 70 2d   int iFirst = p-
3e10: 3e 6e 53 74 61 74 65 3b 0a 20 20 20 20 20 20 20  >nState;.       
3e20: 20 69 66 28 20 70 2d 3e 7a 49 6e 5b 30 5d 3d 3d   if( p->zIn[0]==
3e30: 27 5e 27 20 29 7b 0a 20 20 20 20 20 20 20 20 20  '^' ){.         
3e40: 20 72 65 5f 61 70 70 65 6e 64 28 70 2c 20 52 45   re_append(p, RE
3e50: 5f 4f 50 5f 43 43 5f 45 58 43 2c 20 30 29 3b 0a  _OP_CC_EXC, 0);.
3e60: 20 20 20 20 20 20 20 20 20 20 70 2d 3e 7a 49 6e            p->zIn
3e70: 2b 2b 3b 0a 20 20 20 20 20 20 20 20 7d 65 6c 73  ++;.        }els
3e80: 65 7b 0a 20 20 20 20 20 20 20 20 20 20 72 65 5f  e{.          re_
3e90: 61 70 70 65 6e 64 28 70 2c 20 52 45 5f 4f 50 5f  append(p, RE_OP_
3ea0: 43 43 5f 49 4e 43 2c 20 30 29 3b 0a 20 20 20 20  CC_INC, 0);.    
3eb0: 20 20 20 20 7d 0a 20 20 20 20 20 20 20 20 77 68      }.        wh
3ec0: 69 6c 65 28 20 28 63 20 3d 20 72 65 5f 6e 65 78  ile( (c = re_nex
3ed0: 74 5f 63 68 61 72 28 26 70 2d 3e 7a 49 6e 29 29  t_char(&p->zIn))
3ee0: 21 3d 30 20 29 7b 0a 20 20 20 20 20 20 20 20 20  !=0 ){.         
3ef0: 20 69 66 28 20 63 3d 3d 27 5b 27 20 26 26 20 70   if( c=='[' && p
3f00: 2d 3e 7a 49 6e 5b 30 5d 3d 3d 27 3a 27 20 29 7b  ->zIn[0]==':' ){
3f10: 0a 20 20 20 20 20 20 20 20 20 20 20 20 72 65 74  .            ret
3f20: 75 72 6e 20 22 50 4f 53 49 58 20 63 68 61 72 61  urn "POSIX chara
3f30: 63 74 65 72 20 63 6c 61 73 73 65 73 20 6e 6f 74  cter classes not
3f40: 20 73 75 70 70 6f 72 74 65 64 22 3b 0a 20 20 20   supported";.   
3f50: 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 20         }.       
3f60: 20 20 20 69 66 28 20 63 3d 3d 27 5c 5c 27 20 29     if( c=='\\' )
3f70: 20 63 20 3d 20 72 65 5f 65 73 63 5f 63 68 61 72   c = re_esc_char
3f80: 28 70 29 3b 0a 20 20 20 20 20 20 20 20 20 20 69  (p);.          i
3f90: 66 28 20 70 2d 3e 7a 49 6e 5b 30 5d 3d 3d 27 2d  f( p->zIn[0]=='-
3fa0: 27 20 26 26 20 70 2d 3e 7a 49 6e 5b 31 5d 20 29  ' && p->zIn[1] )
3fb0: 7b 0a 20 20 20 20 20 20 20 20 20 20 20 20 72 65  {.            re
3fc0: 5f 61 70 70 65 6e 64 28 70 2c 20 52 45 5f 4f 50  _append(p, RE_OP
3fd0: 5f 43 43 5f 52 41 4e 47 45 2c 20 63 29 3b 0a 20  _CC_RANGE, c);. 
3fe0: 20 20 20 20 20 20 20 20 20 20 20 70 2d 3e 7a 49             p->zI
3ff0: 6e 2b 2b 3b 0a 20 20 20 20 20 20 20 20 20 20 20  n++;.           
4000: 20 63 20 3d 20 72 65 5f 6e 65 78 74 5f 63 68 61   c = re_next_cha
4010: 72 28 26 70 2d 3e 7a 49 6e 29 3b 0a 20 20 20 20  r(&p->zIn);.    
4020: 20 20 20 20 20 20 20 20 69 66 28 20 63 3d 3d 27          if( c=='
4030: 5c 5c 27 20 29 20 63 20 3d 20 72 65 5f 65 73 63  \\' ) c = re_esc
4040: 5f 63 68 61 72 28 70 29 3b 0a 20 20 20 20 20 20  _char(p);.      
4050: 20 20 20 20 20 20 72 65 5f 61 70 70 65 6e 64 28        re_append(
4060: 70 2c 20 52 45 5f 4f 50 5f 43 43 5f 52 41 4e 47  p, RE_OP_CC_RANG
4070: 45 2c 20 63 29 3b 0a 20 20 20 20 20 20 20 20 20  E, c);.         
4080: 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 20 20   }else{.        
4090: 20 20 20 20 72 65 5f 61 70 70 65 6e 64 28 70 2c      re_append(p,
40a0: 20 52 45 5f 4f 50 5f 43 43 5f 56 41 4c 55 45 2c   RE_OP_CC_VALUE,
40b0: 20 63 29 3b 0a 20 20 20 20 20 20 20 20 20 20 7d   c);.          }
40c0: 0a 20 20 20 20 20 20 20 20 20 20 69 66 28 20 70  .          if( p
40d0: 2d 3e 7a 49 6e 5b 30 5d 3d 3d 27 5d 27 20 29 7b  ->zIn[0]==']' ){
40e0: 20 70 2d 3e 7a 49 6e 2b 2b 3b 20 62 72 65 61 6b   p->zIn++; break
40f0: 3b 20 7d 0a 20 20 20 20 20 20 20 20 7d 0a 20 20  ; }.        }.  
4100: 20 20 20 20 20 20 69 66 28 20 63 3d 3d 30 20 29        if( c==0 )
4110: 20 72 65 74 75 72 6e 20 22 75 6e 63 6c 6f 73 65   return "unclose
4120: 64 20 27 5b 27 22 3b 0a 20 20 20 20 20 20 20 20  d '['";.        
4130: 70 2d 3e 61 41 72 67 5b 69 46 69 72 73 74 5d 20  p->aArg[iFirst] 
4140: 3d 20 70 2d 3e 6e 53 74 61 74 65 20 2d 20 69 46  = p->nState - iF
4150: 69 72 73 74 3b 0a 20 20 20 20 20 20 20 20 62 72  irst;.        br
4160: 65 61 6b 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20  eak;.      }.   
4170: 20 20 20 63 61 73 65 20 27 5c 5c 27 3a 20 7b 0a     case '\\': {.
4180: 20 20 20 20 20 20 20 20 69 6e 74 20 73 70 65 63          int spec
4190: 69 61 6c 4f 70 20 3d 20 30 3b 0a 20 20 20 20 20  ialOp = 0;.     
41a0: 20 20 20 73 77 69 74 63 68 28 20 70 2d 3e 7a 49     switch( p->zI
41b0: 6e 5b 30 5d 20 29 7b 0a 20 20 20 20 20 20 20 20  n[0] ){.        
41c0: 20 20 63 61 73 65 20 27 62 27 3a 20 73 70 65 63    case 'b': spec
41d0: 69 61 6c 4f 70 20 3d 20 52 45 5f 4f 50 5f 42 4f  ialOp = RE_OP_BO
41e0: 55 4e 44 41 52 59 3b 20 20 20 62 72 65 61 6b 3b  UNDARY;   break;
41f0: 0a 20 20 20 20 20 20 20 20 20 20 63 61 73 65 20  .          case 
4200: 27 64 27 3a 20 73 70 65 63 69 61 6c 4f 70 20 3d  'd': specialOp =
4210: 20 52 45 5f 4f 50 5f 44 49 47 49 54 3b 20 20 20   RE_OP_DIGIT;   
4220: 20 20 20 62 72 65 61 6b 3b 0a 20 20 20 20 20 20     break;.      
4230: 20 20 20 20 63 61 73 65 20 27 44 27 3a 20 73 70      case 'D': sp
4240: 65 63 69 61 6c 4f 70 20 3d 20 52 45 5f 4f 50 5f  ecialOp = RE_OP_
4250: 4e 4f 54 44 49 47 49 54 3b 20 20 20 62 72 65 61  NOTDIGIT;   brea
4260: 6b 3b 0a 20 20 20 20 20 20 20 20 20 20 63 61 73  k;.          cas
4270: 65 20 27 73 27 3a 20 73 70 65 63 69 61 6c 4f 70  e 's': specialOp
4280: 20 3d 20 52 45 5f 4f 50 5f 53 50 41 43 45 3b 20   = RE_OP_SPACE; 
4290: 20 20 20 20 20 62 72 65 61 6b 3b 0a 20 20 20 20       break;.    
42a0: 20 20 20 20 20 20 63 61 73 65 20 27 53 27 3a 20        case 'S': 
42b0: 73 70 65 63 69 61 6c 4f 70 20 3d 20 52 45 5f 4f  specialOp = RE_O
42c0: 50 5f 4e 4f 54 53 50 41 43 45 3b 20 20 20 62 72  P_NOTSPACE;   br
42d0: 65 61 6b 3b 0a 20 20 20 20 20 20 20 20 20 20 63  eak;.          c
42e0: 61 73 65 20 27 77 27 3a 20 73 70 65 63 69 61 6c  ase 'w': special
42f0: 4f 70 20 3d 20 52 45 5f 4f 50 5f 57 4f 52 44 3b  Op = RE_OP_WORD;
4300: 20 20 20 20 20 20 20 62 72 65 61 6b 3b 0a 20 20         break;.  
4310: 20 20 20 20 20 20 20 20 63 61 73 65 20 27 57 27          case 'W'
4320: 3a 20 73 70 65 63 69 61 6c 4f 70 20 3d 20 52 45  : specialOp = RE
4330: 5f 4f 50 5f 4e 4f 54 57 4f 52 44 3b 20 20 20 20  _OP_NOTWORD;    
4340: 62 72 65 61 6b 3b 0a 20 20 20 20 20 20 20 20 7d  break;.        }
4350: 0a 20 20 20 20 20 20 20 20 69 66 28 20 73 70 65  .        if( spe
4360: 63 69 61 6c 4f 70 20 29 7b 0a 20 20 20 20 20 20  cialOp ){.      
4370: 20 20 20 20 70 2d 3e 7a 49 6e 2b 2b 3b 0a 20 20      p->zIn++;.  
4380: 20 20 20 20 20 20 20 20 72 65 5f 61 70 70 65 6e          re_appen
4390: 64 28 70 2c 20 73 70 65 63 69 61 6c 4f 70 2c 20  d(p, specialOp, 
43a0: 30 29 3b 0a 20 20 20 20 20 20 20 20 7d 65 6c 73  0);.        }els
43b0: 65 7b 0a 20 20 20 20 20 20 20 20 20 20 63 20 3d  e{.          c =
43c0: 20 72 65 5f 65 73 63 5f 63 68 61 72 28 70 29 3b   re_esc_char(p);
43d0: 0a 20 20 20 20 20 20 20 20 20 20 72 65 5f 61 70  .          re_ap
43e0: 70 65 6e 64 28 70 2c 20 52 45 5f 4f 50 5f 4d 41  pend(p, RE_OP_MA
43f0: 54 43 48 2c 20 63 29 3b 0a 20 20 20 20 20 20 20  TCH, c);.       
4400: 20 7d 0a 20 20 20 20 20 20 20 20 62 72 65 61 6b   }.        break
4410: 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20  ;.      }.      
4420: 64 65 66 61 75 6c 74 3a 20 7b 0a 20 20 20 20 20  default: {.     
4430: 20 20 20 72 65 5f 61 70 70 65 6e 64 28 70 2c 20     re_append(p, 
4440: 52 45 5f 4f 50 5f 4d 41 54 43 48 2c 20 63 29 3b  RE_OP_MATCH, c);
4450: 0a 20 20 20 20 20 20 20 20 62 72 65 61 6b 3b 0a  .        break;.
4460: 20 20 20 20 20 20 7d 0a 20 20 20 20 7d 0a 20 20        }.    }.  
4470: 20 20 69 50 72 65 76 20 3d 20 69 53 74 61 72 74    iPrev = iStart
4480: 3b 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e 20 30  ;.  }.  return 0
4490: 3b 0a 7d 0a 0a 2f 2a 20 46 72 65 65 20 61 6e 64  ;.}../* Free and
44a0: 20 72 65 63 6c 61 69 6d 20 61 6c 6c 20 74 68 65   reclaim all the
44b0: 20 6d 65 6d 6f 72 79 20 75 73 65 64 20 62 79 20   memory used by 
44c0: 61 20 70 72 65 76 69 6f 75 73 6c 79 20 63 6f 6d  a previously com
44d0: 70 69 6c 65 64 0a 2a 2a 20 72 65 67 75 6c 61 72  piled.** regular
44e0: 20 65 78 70 72 65 73 73 69 6f 6e 2e 20 20 41 70   expression.  Ap
44f0: 70 6c 69 63 61 74 69 6f 6e 73 20 73 68 6f 75 6c  plications shoul
4500: 64 20 69 6e 76 6f 6b 65 20 74 68 69 73 20 72 6f  d invoke this ro
4510: 75 74 69 6e 65 20 6f 6e 63 65 0a 2a 2a 20 66 6f  utine once.** fo
4520: 72 20 65 76 65 72 79 20 63 61 6c 6c 20 74 6f 20  r every call to 
4530: 72 65 5f 63 6f 6d 70 69 6c 65 28 29 20 74 6f 20  re_compile() to 
4540: 61 76 6f 69 64 20 6d 65 6d 6f 72 79 20 6c 65 61  avoid memory lea
4550: 6b 73 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 76 6f  ks..*/.static vo
4560: 69 64 20 72 65 5f 66 72 65 65 28 52 65 43 6f 6d  id re_free(ReCom
4570: 70 69 6c 65 64 20 2a 70 52 65 29 7b 0a 20 20 69  piled *pRe){.  i
4580: 66 28 20 70 52 65 20 29 7b 0a 20 20 20 20 66 72  f( pRe ){.    fr
4590: 65 65 28 70 52 65 2d 3e 61 4f 70 29 3b 0a 20 20  ee(pRe->aOp);.  
45a0: 20 20 66 72 65 65 28 70 52 65 2d 3e 61 41 72 67    free(pRe->aArg
45b0: 29 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a 0a 2a 2a 20  );.  }.}../*.** 
45c0: 43 6f 6d 70 69 6c 65 20 61 20 74 65 78 74 75 61  Compile a textua
45d0: 6c 20 72 65 67 75 6c 61 72 20 65 78 70 72 65 73  l regular expres
45e0: 73 69 6f 6e 20 69 6e 20 7a 49 6e 5b 5d 20 69 6e  sion in zIn[] in
45f0: 74 6f 20 61 20 63 6f 6d 70 69 6c 65 64 20 72 65  to a compiled re
4600: 67 75 6c 61 72 0a 2a 2a 20 65 78 70 72 65 73 73  gular.** express
4610: 69 6f 6e 20 73 75 69 74 61 62 6c 65 20 66 6f 72  ion suitable for
4620: 20 75 73 20 62 79 20 72 65 5f 65 78 65 63 28 29   us by re_exec()
4630: 20 61 6e 64 20 72 65 74 75 72 6e 20 61 20 70 6f   and return a po
4640: 69 6e 74 65 72 20 74 6f 20 74 68 65 0a 2a 2a 20  inter to the.** 
4650: 63 6f 6d 70 69 6c 65 64 20 72 65 67 75 6c 61 72  compiled regular
4660: 20 65 78 70 72 65 73 73 69 6f 6e 20 69 6e 20 2a   expression in *
4670: 70 70 52 65 2e 20 20 52 65 74 75 72 6e 20 4e 55  ppRe.  Return NU
4680: 4c 4c 20 6f 6e 20 73 75 63 63 65 73 73 20 6f 72  LL on success or
4690: 20 61 6e 0a 2a 2a 20 65 72 72 6f 72 20 6d 65 73   an.** error mes
46a0: 73 61 67 65 20 69 66 20 73 6f 6d 65 74 68 69 6e  sage if somethin
46b0: 67 20 67 6f 65 73 20 77 72 6f 6e 67 2e 0a 2a 2f  g goes wrong..*/
46c0: 0a 73 74 61 74 69 63 20 63 6f 6e 73 74 20 63 68  .static const ch
46d0: 61 72 20 2a 72 65 5f 63 6f 6d 70 69 6c 65 28 52  ar *re_compile(R
46e0: 65 43 6f 6d 70 69 6c 65 64 20 2a 2a 70 70 52 65  eCompiled **ppRe
46f0: 2c 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 7a 49  , const char *zI
4700: 6e 29 7b 0a 20 20 52 65 43 6f 6d 70 69 6c 65 64  n){.  ReCompiled
4710: 20 2a 70 52 65 3b 0a 20 20 63 6f 6e 73 74 20 63   *pRe;.  const c
4720: 68 61 72 20 2a 7a 45 72 72 3b 0a 20 20 69 6e 74  har *zErr;.  int
4730: 20 69 2c 20 6a 3b 0a 0a 20 20 2a 70 70 52 65 20   i, j;..  *ppRe 
4740: 3d 20 30 3b 0a 20 20 70 52 65 20 3d 20 6d 61 6c  = 0;.  pRe = mal
4750: 6c 6f 63 28 20 73 69 7a 65 6f 66 28 2a 70 52 65  loc( sizeof(*pRe
4760: 29 20 29 3b 0a 20 20 69 66 28 20 70 52 65 3d 3d  ) );.  if( pRe==
4770: 30 20 29 7b 0a 20 20 20 20 72 65 74 75 72 6e 20  0 ){.    return 
4780: 22 6f 75 74 20 6f 66 20 6d 65 6d 6f 72 79 22 3b  "out of memory";
4790: 0a 20 20 7d 0a 20 20 6d 65 6d 73 65 74 28 70 52  .  }.  memset(pR
47a0: 65 2c 20 30 2c 20 73 69 7a 65 6f 66 28 2a 70 52  e, 0, sizeof(*pR
47b0: 65 29 29 3b 0a 20 20 69 66 28 20 72 65 5f 72 65  e));.  if( re_re
47c0: 73 69 7a 65 28 70 52 65 2c 20 33 30 29 20 29 7b  size(pRe, 30) ){
47d0: 0a 20 20 20 20 72 65 5f 66 72 65 65 28 70 52 65  .    re_free(pRe
47e0: 29 3b 0a 20 20 20 20 72 65 74 75 72 6e 20 22 6f  );.    return "o
47f0: 75 74 20 6f 66 20 6d 65 6d 6f 72 79 22 3b 0a 20  ut of memory";. 
4800: 20 7d 0a 20 20 69 66 28 20 7a 49 6e 5b 30 5d 3d   }.  if( zIn[0]=
4810: 3d 27 5e 27 20 29 7b 0a 20 20 20 20 7a 49 6e 2b  ='^' ){.    zIn+
4820: 2b 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20  +;.  }else{.    
4830: 72 65 5f 61 70 70 65 6e 64 28 70 52 65 2c 20 52  re_append(pRe, R
4840: 45 5f 4f 50 5f 41 4e 59 53 54 41 52 2c 20 30 29  E_OP_ANYSTAR, 0)
4850: 3b 0a 20 20 7d 0a 20 20 70 52 65 2d 3e 7a 49 6e  ;.  }.  pRe->zIn
4860: 20 3d 20 28 75 6e 73 69 67 6e 65 64 20 63 68 61   = (unsigned cha
4870: 72 2a 29 7a 49 6e 3b 0a 20 20 7a 45 72 72 20 3d  r*)zIn;.  zErr =
4880: 20 72 65 5f 73 75 62 63 6f 6d 70 69 6c 65 5f 72   re_subcompile_r
4890: 65 28 70 52 65 29 3b 0a 20 20 69 66 28 20 7a 45  e(pRe);.  if( zE
48a0: 72 72 20 29 7b 0a 20 20 20 20 72 65 5f 66 72 65  rr ){.    re_fre
48b0: 65 28 70 52 65 29 3b 0a 20 20 20 20 72 65 74 75  e(pRe);.    retu
48c0: 72 6e 20 7a 45 72 72 3b 0a 20 20 7d 0a 20 20 69  rn zErr;.  }.  i
48d0: 66 28 20 70 52 65 2d 3e 7a 49 6e 5b 30 5d 3d 3d  f( pRe->zIn[0]==
48e0: 27 24 27 20 26 26 20 70 52 65 2d 3e 7a 49 6e 5b  '$' && pRe->zIn[
48f0: 31 5d 3d 3d 30 20 29 7b 0a 20 20 20 20 72 65 5f  1]==0 ){.    re_
4900: 61 70 70 65 6e 64 28 70 52 65 2c 20 52 45 5f 4f  append(pRe, RE_O
4910: 50 5f 4d 41 54 43 48 2c 20 52 45 5f 45 4f 46 29  P_MATCH, RE_EOF)
4920: 3b 0a 20 20 20 20 72 65 5f 61 70 70 65 6e 64 28  ;.    re_append(
4930: 70 52 65 2c 20 52 45 5f 4f 50 5f 41 43 43 45 50  pRe, RE_OP_ACCEP
4940: 54 2c 20 30 29 3b 0a 20 20 20 20 2a 70 70 52 65  T, 0);.    *ppRe
4950: 20 3d 20 70 52 65 3b 0a 20 20 7d 65 6c 73 65 20   = pRe;.  }else 
4960: 69 66 28 20 70 52 65 2d 3e 7a 49 6e 5b 30 5d 3d  if( pRe->zIn[0]=
4970: 3d 30 20 29 7b 0a 20 20 20 20 72 65 5f 61 70 70  =0 ){.    re_app
4980: 65 6e 64 28 70 52 65 2c 20 52 45 5f 4f 50 5f 41  end(pRe, RE_OP_A
4990: 43 43 45 50 54 2c 20 30 29 3b 0a 20 20 20 20 2a  CCEPT, 0);.    *
49a0: 70 70 52 65 20 3d 20 70 52 65 3b 0a 20 20 7d 65  ppRe = pRe;.  }e
49b0: 6c 73 65 7b 0a 20 20 20 20 72 65 5f 66 72 65 65  lse{.    re_free
49c0: 28 70 52 65 29 3b 0a 20 20 20 20 72 65 74 75 72  (pRe);.    retur
49d0: 6e 20 22 75 6e 72 65 63 6f 67 6e 69 7a 65 64 20  n "unrecognized 
49e0: 63 68 61 72 61 63 74 65 72 22 3b 0a 20 20 7d 0a  character";.  }.
49f0: 20 20 69 66 28 20 70 52 65 2d 3e 61 4f 70 5b 30    if( pRe->aOp[0
4a00: 5d 3d 3d 52 45 5f 4f 50 5f 41 4e 59 53 54 41 52  ]==RE_OP_ANYSTAR
4a10: 20 29 7b 0a 20 20 20 20 66 6f 72 28 6a 3d 30 2c   ){.    for(j=0,
4a20: 20 69 3d 31 3b 20 6a 3c 73 69 7a 65 6f 66 28 70   i=1; j<sizeof(p
4a30: 52 65 2d 3e 7a 49 6e 69 74 29 2d 32 20 26 26 20  Re->zInit)-2 && 
4a40: 70 52 65 2d 3e 61 4f 70 5b 69 5d 3d 3d 52 45 5f  pRe->aOp[i]==RE_
4a50: 4f 50 5f 4d 41 54 43 48 3b 20 69 2b 2b 29 7b 0a  OP_MATCH; i++){.
4a60: 20 20 20 20 20 20 75 6e 73 69 67 6e 65 64 20 78        unsigned x
4a70: 20 3d 20 70 52 65 2d 3e 61 41 72 67 5b 69 5d 3b   = pRe->aArg[i];
4a80: 0a 20 20 20 20 20 20 69 66 28 20 78 3c 3d 31 32  .      if( x<=12
4a90: 37 20 29 7b 0a 20 20 20 20 20 20 20 20 70 52 65  7 ){.        pRe
4aa0: 2d 3e 7a 49 6e 69 74 5b 6a 2b 2b 5d 20 3d 20 78  ->zInit[j++] = x
4ab0: 3b 0a 20 20 20 20 20 20 7d 65 6c 73 65 20 69 66  ;.      }else if
4ac0: 28 20 78 3c 3d 30 78 66 66 66 20 29 7b 0a 20 20  ( x<=0xfff ){.  
4ad0: 20 20 20 20 20 20 70 52 65 2d 3e 7a 49 6e 69 74        pRe->zInit
4ae0: 5b 6a 2b 2b 5d 20 3d 20 30 78 63 30 20 7c 20 28  [j++] = 0xc0 | (
4af0: 78 3e 3e 36 29 3b 0a 20 20 20 20 20 20 20 20 70  x>>6);.        p
4b00: 52 65 2d 3e 7a 49 6e 69 74 5b 6a 2b 2b 5d 20 3d  Re->zInit[j++] =
4b10: 20 30 78 38 30 20 7c 20 28 78 26 30 78 33 66 29   0x80 | (x&0x3f)
4b20: 3b 0a 20 20 20 20 20 20 7d 65 6c 73 65 20 69 66  ;.      }else if
4b30: 28 20 78 3c 3d 30 78 66 66 66 66 20 29 7b 0a 20  ( x<=0xffff ){. 
4b40: 20 20 20 20 20 20 20 70 52 65 2d 3e 7a 49 6e 69         pRe->zIni
4b50: 74 5b 6a 2b 2b 5d 20 3d 20 30 78 64 30 20 7c 20  t[j++] = 0xd0 | 
4b60: 28 78 3e 3e 31 32 29 3b 0a 20 20 20 20 20 20 20  (x>>12);.       
4b70: 20 70 52 65 2d 3e 7a 49 6e 69 74 5b 6a 2b 2b 5d   pRe->zInit[j++]
4b80: 20 3d 20 30 78 38 30 20 7c 20 28 28 78 3e 3e 36   = 0x80 | ((x>>6
4b90: 29 26 30 78 33 66 29 3b 0a 20 20 20 20 20 20 20  )&0x3f);.       
4ba0: 20 70 52 65 2d 3e 7a 49 6e 69 74 5b 6a 2b 2b 5d   pRe->zInit[j++]
4bb0: 20 3d 20 30 78 38 30 20 7c 20 28 28 78 3e 3e 36   = 0x80 | ((x>>6
4bc0: 29 26 30 78 33 66 29 3b 0a 20 20 20 20 20 20 7d  )&0x3f);.      }
4bd0: 65 6c 73 65 7b 0a 20 20 20 20 20 20 20 20 62 72  else{.        br
4be0: 65 61 6b 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20  eak;.      }.   
4bf0: 20 7d 0a 20 20 20 20 70 52 65 2d 3e 6e 49 6e 69   }.    pRe->nIni
4c00: 74 20 3d 20 6a 3b 0a 20 20 7d 0a 20 20 72 65 74  t = j;.  }.  ret
4c10: 75 72 6e 20 70 52 65 2d 3e 7a 45 72 72 3b 0a 7d  urn pRe->zErr;.}
4c20: 0a 0a 2f 2a 0a 2a 2a 20 49 6d 70 6c 65 6d 65 6e  ../*.** Implemen
4c30: 74 61 74 69 6f 6e 20 6f 66 20 74 68 65 20 72 65  tation of the re
4c40: 67 65 78 70 28 29 20 53 51 4c 20 66 75 6e 63 74  gexp() SQL funct
4c50: 69 6f 6e 2e 20 20 54 68 69 73 20 66 75 6e 63 74  ion.  This funct
4c60: 69 6f 6e 20 69 6d 70 6c 65 6d 65 6e 74 73 0a 2a  ion implements.*
4c70: 2a 20 74 68 65 20 62 75 69 6c 64 2d 69 6e 20 52  * the build-in R
4c80: 45 47 45 58 50 20 6f 70 65 72 61 74 6f 72 2e 20  EGEXP operator. 
4c90: 20 54 68 65 20 66 69 72 73 74 20 61 72 67 75 6d   The first argum
4ca0: 65 6e 74 20 74 6f 20 74 68 65 20 66 75 6e 63 74  ent to the funct
4cb0: 69 6f 6e 20 69 73 20 74 68 65 0a 2a 2a 20 70 61  ion is the.** pa
4cc0: 74 74 65 72 6e 20 61 6e 64 20 74 68 65 20 73 65  ttern and the se
4cd0: 63 6f 6e 64 20 61 72 67 75 6d 65 6e 74 20 69 73  cond argument is
4ce0: 20 74 68 65 20 73 74 72 69 6e 67 2e 20 20 53 6f   the string.  So
4cf0: 2c 20 74 68 65 20 53 51 4c 20 73 74 61 74 65 6d  , the SQL statem
4d00: 65 6e 74 73 3a 0a 2a 2a 0a 2a 2a 20 20 20 20 20  ents:.**.**     
4d10: 20 20 41 20 52 45 47 45 58 50 20 42 0a 2a 2a 0a    A REGEXP B.**.
4d20: 2a 2a 20 69 73 20 69 6d 70 6c 65 6d 65 6e 74 65  ** is implemente
4d30: 64 20 61 73 20 72 65 67 65 78 70 28 42 2c 41 29  d as regexp(B,A)
4d40: 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 76 6f 69 64  ..*/.static void
4d50: 20 72 65 5f 73 71 6c 5f 66 75 6e 63 28 0a 20 20   re_sql_func(.  
4d60: 73 71 6c 69 74 65 33 5f 63 6f 6e 74 65 78 74 20  sqlite3_context 
4d70: 2a 63 6f 6e 74 65 78 74 2c 20 0a 20 20 69 6e 74  *context, .  int
4d80: 20 61 72 67 63 2c 20 0a 20 20 73 71 6c 69 74 65   argc, .  sqlite
4d90: 33 5f 76 61 6c 75 65 20 2a 2a 61 72 67 76 0a 29  3_value **argv.)
4da0: 7b 0a 20 20 52 65 43 6f 6d 70 69 6c 65 64 20 2a  {.  ReCompiled *
4db0: 70 52 65 3b 20 20 20 20 20 20 20 20 20 20 2f 2a  pRe;          /*
4dc0: 20 43 6f 6d 70 69 6c 65 64 20 72 65 67 75 6c 61   Compiled regula
4dd0: 72 20 65 78 70 72 65 73 73 69 6f 6e 20 2a 2f 0a  r expression */.
4de0: 20 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 7a 50    const char *zP
4df0: 61 74 74 65 72 6e 3b 20 20 20 20 20 2f 2a 20 54  attern;     /* T
4e00: 68 65 20 72 65 67 75 6c 61 72 20 65 78 70 72 65  he regular expre
4e10: 73 73 69 6f 6e 20 2a 2f 0a 20 20 63 6f 6e 73 74  ssion */.  const
4e20: 20 75 6e 73 69 67 6e 65 64 20 63 68 61 72 20 2a   unsigned char *
4e30: 7a 53 74 72 3b 2f 2a 20 53 74 72 69 6e 67 20 62  zStr;/* String b
4e40: 65 69 6e 67 20 73 65 61 72 63 68 65 64 20 2a 2f  eing searched */
4e50: 0a 20 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 7a  .  const char *z
4e60: 45 72 72 3b 20 20 20 20 20 20 20 20 20 2f 2a 20  Err;         /* 
4e70: 43 6f 6d 70 69 6c 65 20 65 72 72 6f 72 20 6d 65  Compile error me
4e80: 73 73 61 67 65 20 2a 2f 0a 0a 20 20 70 52 65 20  ssage */..  pRe 
4e90: 3d 20 73 71 6c 69 74 65 33 5f 67 65 74 5f 61 75  = sqlite3_get_au
4ea0: 78 64 61 74 61 28 63 6f 6e 74 65 78 74 2c 20 30  xdata(context, 0
4eb0: 29 3b 0a 20 20 69 66 28 20 70 52 65 3d 3d 30 20  );.  if( pRe==0 
4ec0: 29 7b 0a 20 20 20 20 7a 50 61 74 74 65 72 6e 20  ){.    zPattern 
4ed0: 3d 20 28 63 6f 6e 73 74 20 63 68 61 72 2a 29 73  = (const char*)s
4ee0: 71 6c 69 74 65 33 5f 76 61 6c 75 65 5f 74 65 78  qlite3_value_tex
4ef0: 74 28 61 72 67 76 5b 30 5d 29 3b 0a 20 20 20 20  t(argv[0]);.    
4f00: 69 66 28 20 7a 50 61 74 74 65 72 6e 3d 3d 30 20  if( zPattern==0 
4f10: 29 20 72 65 74 75 72 6e 3b 0a 20 20 20 20 7a 45  ) return;.    zE
4f20: 72 72 20 3d 20 72 65 5f 63 6f 6d 70 69 6c 65 28  rr = re_compile(
4f30: 26 70 52 65 2c 20 7a 50 61 74 74 65 72 6e 29 3b  &pRe, zPattern);
4f40: 0a 20 20 20 20 69 66 28 20 7a 45 72 72 20 29 7b  .    if( zErr ){
4f50: 0a 20 20 20 20 20 20 73 71 6c 69 74 65 33 5f 72  .      sqlite3_r
4f60: 65 73 75 6c 74 5f 65 72 72 6f 72 28 63 6f 6e 74  esult_error(cont
4f70: 65 78 74 2c 20 7a 45 72 72 2c 20 2d 31 29 3b 0a  ext, zErr, -1);.
4f80: 20 20 20 20 20 20 72 65 74 75 72 6e 3b 0a 20 20        return;.  
4f90: 20 20 7d 0a 20 20 20 20 69 66 28 20 70 52 65 3d    }.    if( pRe=
4fa0: 3d 30 20 29 7b 0a 20 20 20 20 20 20 73 71 6c 69  =0 ){.      sqli
4fb0: 74 65 33 5f 72 65 73 75 6c 74 5f 65 72 72 6f 72  te3_result_error
4fc0: 5f 6e 6f 6d 65 6d 28 63 6f 6e 74 65 78 74 29 3b  _nomem(context);
4fd0: 0a 20 20 20 20 20 20 72 65 74 75 72 6e 3b 0a 20  .      return;. 
4fe0: 20 20 20 7d 0a 20 20 20 20 73 71 6c 69 74 65 33     }.    sqlite3
4ff0: 5f 73 65 74 5f 61 75 78 64 61 74 61 28 63 6f 6e  _set_auxdata(con
5000: 74 65 78 74 2c 20 30 2c 20 70 52 65 2c 20 28 76  text, 0, pRe, (v
5010: 6f 69 64 28 2a 29 28 76 6f 69 64 2a 29 29 72 65  oid(*)(void*))re
5020: 5f 66 72 65 65 29 3b 0a 20 20 7d 0a 20 20 7a 53  _free);.  }.  zS
5030: 74 72 20 3d 20 28 63 6f 6e 73 74 20 75 6e 73 69  tr = (const unsi
5040: 67 6e 65 64 20 63 68 61 72 2a 29 73 71 6c 69 74  gned char*)sqlit
5050: 65 33 5f 76 61 6c 75 65 5f 74 65 78 74 28 61 72  e3_value_text(ar
5060: 67 76 5b 31 5d 29 3b 0a 20 20 69 66 28 20 7a 53  gv[1]);.  if( zS
5070: 74 72 21 3d 30 20 29 7b 0a 20 20 20 20 73 71 6c  tr!=0 ){.    sql
5080: 69 74 65 33 5f 72 65 73 75 6c 74 5f 69 6e 74 28  ite3_result_int(
5090: 63 6f 6e 74 65 78 74 2c 20 72 65 5f 65 78 65 63  context, re_exec
50a0: 28 70 52 65 2c 20 7a 53 74 72 29 29 3b 0a 20 20  (pRe, zStr));.  
50b0: 7d 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 49 6e 76 6f 6b  }.}../*.** Invok
50c0: 65 20 74 68 69 73 20 72 6f 75 74 69 6e 65 20 69  e this routine i
50d0: 6e 20 6f 72 64 65 72 20 74 6f 20 69 6e 73 74 61  n order to insta
50e0: 6c 6c 20 74 68 65 20 52 45 47 45 58 50 20 66 75  ll the REGEXP fu
50f0: 6e 63 74 69 6f 6e 20 69 6e 20 61 6e 0a 2a 2a 20  nction in an.** 
5100: 53 51 4c 69 74 65 20 64 61 74 61 62 61 73 65 20  SQLite database 
5110: 63 6f 6e 6e 65 63 74 69 6f 6e 2e 0a 2a 2a 0a 2a  connection..**.*
5120: 2a 20 55 73 65 3a 0a 2a 2a 0a 2a 2a 20 20 20 20  * Use:.**.**    
5130: 20 20 73 71 6c 69 74 65 33 5f 61 75 74 6f 5f 65    sqlite3_auto_e
5140: 78 74 65 6e 73 69 6f 6e 28 73 71 6c 69 74 65 33  xtension(sqlite3
5150: 5f 61 64 64 5f 72 65 67 65 78 70 5f 66 75 6e 63  _add_regexp_func
5160: 29 3b 0a 2a 2a 0a 2a 2a 20 74 6f 20 63 61 75 73  );.**.** to caus
5170: 65 20 74 68 69 73 20 65 78 74 65 6e 73 69 6f 6e  e this extension
5180: 20 74 6f 20 62 65 20 61 75 74 6f 6d 61 74 69 63   to be automatic
5190: 61 6c 6c 79 20 6c 6f 61 64 65 64 20 69 6e 74 6f  ally loaded into
51a0: 20 65 61 63 68 20 6e 65 77 0a 2a 2a 20 64 61 74   each new.** dat
51b0: 61 62 61 73 65 20 63 6f 6e 6e 65 63 74 69 6f 6e  abase connection
51c0: 2e 0a 2a 2f 0a 69 6e 74 20 73 71 6c 69 74 65 33  ..*/.int sqlite3
51d0: 5f 61 64 64 5f 72 65 67 65 78 70 5f 66 75 6e 63  _add_regexp_func
51e0: 28 73 71 6c 69 74 65 33 20 2a 64 62 29 7b 0a 20  (sqlite3 *db){. 
51f0: 20 72 65 74 75 72 6e 20 73 71 6c 69 74 65 33 5f   return sqlite3_
5200: 63 72 65 61 74 65 5f 66 75 6e 63 74 69 6f 6e 28  create_function(
5210: 64 62 2c 20 22 72 65 67 65 78 70 22 2c 20 32 2c  db, "regexp", 2,
5220: 20 53 51 4c 49 54 45 5f 55 54 46 38 2c 20 30 2c   SQLITE_UTF8, 0,
5230: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
5240: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
5250: 20 20 72 65 5f 73 71 6c 5f 66 75 6e 63 2c 20 30    re_sql_func, 0
5260: 2c 20 30 29 3b 0a 7d 0a 0a 0a 2f 2a 2a 2a 2a 2a  , 0);.}.../*****
5270: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
5280: 2a 2a 2a 2a 2a 2a 2a 2a 20 54 65 73 74 20 43 6f  ******** Test Co
5290: 64 65 20 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  de *************
52a0: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
52b0: 2a 2a 2a 2a 2a 2a 2f 0a 23 69 66 64 65 66 20 53  ******/.#ifdef S
52c0: 51 4c 49 54 45 5f 54 45 53 54 0a 23 69 6e 63 6c  QLITE_TEST.#incl
52d0: 75 64 65 20 3c 74 63 6c 2e 68 3e 0a 65 78 74 65  ude <tcl.h>.exte
52e0: 72 6e 20 69 6e 74 20 67 65 74 44 62 50 6f 69 6e  rn int getDbPoin
52f0: 74 65 72 28 54 63 6c 5f 49 6e 74 65 72 70 20 2a  ter(Tcl_Interp *
5300: 69 6e 74 65 72 70 2c 20 63 6f 6e 73 74 20 63 68  interp, const ch
5310: 61 72 20 2a 7a 41 2c 20 73 71 6c 69 74 65 33 20  ar *zA, sqlite3 
5320: 2a 2a 70 70 44 62 29 3b 0a 0a 2f 2a 20 49 6d 70  **ppDb);../* Imp
5330: 6c 65 6d 65 6e 74 61 74 69 6f 6e 20 6f 66 20 74  lementation of t
5340: 68 65 20 54 43 4c 20 63 6f 6d 6d 61 6e 64 3a 0a  he TCL command:.
5350: 2a 2a 0a 2a 2a 20 20 20 20 20 20 73 71 6c 69 74  **.**      sqlit
5360: 65 33 5f 61 64 64 5f 72 65 67 65 78 70 5f 66 75  e3_add_regexp_fu
5370: 6e 63 20 24 44 42 0a 2a 2f 0a 73 74 61 74 69 63  nc $DB.*/.static
5380: 20 69 6e 74 20 74 63 6c 53 71 6c 69 74 65 33 41   int tclSqlite3A
5390: 64 64 52 65 67 65 78 70 46 75 6e 63 28 0a 20 20  ddRegexpFunc(.  
53a0: 76 6f 69 64 20 2a 20 63 6c 69 65 6e 74 44 61 74  void * clientDat
53b0: 61 2c 0a 20 20 54 63 6c 5f 49 6e 74 65 72 70 20  a,.  Tcl_Interp 
53c0: 2a 69 6e 74 65 72 70 2c 0a 20 20 69 6e 74 20 6f  *interp,.  int o
53d0: 62 6a 63 2c 0a 20 20 54 63 6c 5f 4f 62 6a 20 2a  bjc,.  Tcl_Obj *
53e0: 43 4f 4e 53 54 20 6f 62 6a 76 5b 5d 0a 29 7b 0a  CONST objv[].){.
53f0: 20 20 73 71 6c 69 74 65 33 20 2a 64 62 3b 0a 20    sqlite3 *db;. 
5400: 20 69 66 28 20 6f 62 6a 63 21 3d 32 20 29 7b 0a   if( objc!=2 ){.
5410: 20 20 20 20 54 63 6c 5f 57 72 6f 6e 67 4e 75 6d      Tcl_WrongNum
5420: 41 72 67 73 28 69 6e 74 65 72 70 2c 20 31 2c 20  Args(interp, 1, 
5430: 6f 62 6a 76 2c 20 22 44 42 22 29 3b 0a 20 20 20  objv, "DB");.   
5440: 20 72 65 74 75 72 6e 20 54 43 4c 5f 45 52 52 4f   return TCL_ERRO
5450: 52 3b 0a 20 20 7d 0a 20 20 69 66 28 20 67 65 74  R;.  }.  if( get
5460: 44 62 50 6f 69 6e 74 65 72 28 69 6e 74 65 72 70  DbPointer(interp
5470: 2c 20 54 63 6c 5f 47 65 74 53 74 72 69 6e 67 28  , Tcl_GetString(
5480: 6f 62 6a 76 5b 31 5d 29 2c 20 26 64 62 29 20 29  objv[1]), &db) )
5490: 20 72 65 74 75 72 6e 20 54 43 4c 5f 45 52 52 4f   return TCL_ERRO
54a0: 52 3b 0a 20 20 73 71 6c 69 74 65 33 5f 61 64 64  R;.  sqlite3_add
54b0: 5f 72 65 67 65 78 70 5f 66 75 6e 63 28 64 62 29  _regexp_func(db)
54c0: 3b 0a 20 20 72 65 74 75 72 6e 20 54 43 4c 5f 4f  ;.  return TCL_O
54d0: 4b 3b 0a 7d 0a 0a 2f 2a 20 52 65 67 69 73 74 65  K;.}../* Registe
54e0: 72 20 74 68 65 20 73 71 6c 69 74 65 33 5f 61 64  r the sqlite3_ad
54f0: 64 5f 72 65 67 65 78 70 5f 66 75 6e 63 20 54 43  d_regexp_func TC
5500: 4c 20 63 6f 6d 6d 61 6e 64 20 77 69 74 68 20 74  L command with t
5510: 68 65 20 54 43 4c 20 69 6e 74 65 72 70 72 65 74  he TCL interpret
5520: 65 72 2e 0a 2a 2f 0a 69 6e 74 20 53 71 6c 69 74  er..*/.int Sqlit
5530: 65 74 65 73 74 72 65 67 65 78 70 5f 49 6e 69 74  etestregexp_Init
5540: 28 54 63 6c 5f 49 6e 74 65 72 70 20 2a 69 6e 74  (Tcl_Interp *int
5550: 65 72 70 29 7b 0a 20 20 54 63 6c 5f 43 72 65 61  erp){.  Tcl_Crea
5560: 74 65 4f 62 6a 43 6f 6d 6d 61 6e 64 28 69 6e 74  teObjCommand(int
5570: 65 72 70 2c 20 22 73 71 6c 69 74 65 33 5f 61 64  erp, "sqlite3_ad
5580: 64 5f 72 65 67 65 78 70 5f 66 75 6e 63 22 2c 0a  d_regexp_func",.
5590: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
55a0: 20 20 20 20 20 20 20 74 63 6c 53 71 6c 69 74 65         tclSqlite
55b0: 33 41 64 64 52 65 67 65 78 70 46 75 6e 63 2c 20  3AddRegexpFunc, 
55c0: 30 2c 20 30 29 3b 0a 20 20 72 65 74 75 72 6e 20  0, 0);.  return 
55d0: 54 43 4c 5f 4f 4b 3b 0a 7d 0a 23 65 6e 64 69 66  TCL_OK;.}.#endif
55e0: 20 2f 2a 20 53 51 4c 49 54 45 5f 54 45 53 54 20   /* SQLITE_TEST 
55f0: 2a 2f 0a 2f 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  */./************
5600: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
5610: 20 45 6e 64 20 4f 66 20 54 65 73 74 20 43 6f 64   End Of Test Cod
5620: 65 20 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  e **************
5630: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
5640: 2a 2f 0a                                         */.