000001  /*
000002  ** 2001 September 15
000003  **
000004  ** The author disclaims copyright to this source code.  In place of
000005  ** a legal notice, here is a blessing:
000006  **
000007  **    May you do good and not evil.
000008  **    May you find forgiveness for yourself and forgive others.
000009  **    May you share freely, never taking more than you give.
000010  **
000011  *************************************************************************
000012  ** An tokenizer for SQL
000013  **
000014  ** This file contains C code that splits an SQL input string up into
000015  ** individual tokens and sends those tokens one-by-one over to the
000016  ** parser for analysis.
000017  */
000018  #include "sqliteInt.h"
000019  #include <stdlib.h>
000020  
000021  /* Character classes for tokenizing
000022  **
000023  ** In the sqlite3GetToken() function, a switch() on aiClass[c] is implemented
000024  ** using a lookup table, whereas a switch() directly on c uses a binary search.
000025  ** The lookup table is much faster.  To maximize speed, and to ensure that
000026  ** a lookup table is used, all of the classes need to be small integers and
000027  ** all of them need to be used within the switch.
000028  */
000029  #define CC_X          0    /* The letter 'x', or start of BLOB literal */
000030  #define CC_KYWD0      1    /* First letter of a keyword */
000031  #define CC_KYWD       2    /* Alphabetics or '_'.  Usable in a keyword */
000032  #define CC_DIGIT      3    /* Digits */
000033  #define CC_DOLLAR     4    /* '$' */
000034  #define CC_VARALPHA   5    /* '@', '#', ':'.  Alphabetic SQL variables */
000035  #define CC_VARNUM     6    /* '?'.  Numeric SQL variables */
000036  #define CC_SPACE      7    /* Space characters */
000037  #define CC_QUOTE      8    /* '"', '\'', or '`'.  String literals, quoted ids */
000038  #define CC_QUOTE2     9    /* '['.   [...] style quoted ids */
000039  #define CC_PIPE      10    /* '|'.   Bitwise OR or concatenate */
000040  #define CC_MINUS     11    /* '-'.  Minus or SQL-style comment */
000041  #define CC_LT        12    /* '<'.  Part of < or <= or <> */
000042  #define CC_GT        13    /* '>'.  Part of > or >= */
000043  #define CC_EQ        14    /* '='.  Part of = or == */
000044  #define CC_BANG      15    /* '!'.  Part of != */
000045  #define CC_SLASH     16    /* '/'.  / or c-style comment */
000046  #define CC_LP        17    /* '(' */
000047  #define CC_RP        18    /* ')' */
000048  #define CC_SEMI      19    /* ';' */
000049  #define CC_PLUS      20    /* '+' */
000050  #define CC_STAR      21    /* '*' */
000051  #define CC_PERCENT   22    /* '%' */
000052  #define CC_COMMA     23    /* ',' */
000053  #define CC_AND       24    /* '&' */
000054  #define CC_TILDA     25    /* '~' */
000055  #define CC_DOT       26    /* '.' */
000056  #define CC_ID        27    /* unicode characters usable in IDs */
000057  #define CC_ILLEGAL   28    /* Illegal character */
000058  #define CC_NUL       29    /* 0x00 */
000059  #define CC_BOM       30    /* First byte of UTF8 BOM:  0xEF 0xBB 0xBF */
000060  
000061  static const unsigned char aiClass[] = {
000062  #ifdef SQLITE_ASCII
000063  /*         x0  x1  x2  x3  x4  x5  x6  x7  x8  x9  xa  xb  xc  xd  xe  xf */
000064  /* 0x */   29, 28, 28, 28, 28, 28, 28, 28, 28,  7,  7, 28,  7,  7, 28, 28,
000065  /* 1x */   28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
000066  /* 2x */    7, 15,  8,  5,  4, 22, 24,  8, 17, 18, 21, 20, 23, 11, 26, 16,
000067  /* 3x */    3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  5, 19, 12, 14, 13,  6,
000068  /* 4x */    5,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
000069  /* 5x */    1,  1,  1,  1,  1,  1,  1,  1,  0,  2,  2,  9, 28, 28, 28,  2,
000070  /* 6x */    8,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
000071  /* 7x */    1,  1,  1,  1,  1,  1,  1,  1,  0,  2,  2, 28, 10, 28, 25, 28,
000072  /* 8x */   27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
000073  /* 9x */   27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
000074  /* Ax */   27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
000075  /* Bx */   27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
000076  /* Cx */   27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
000077  /* Dx */   27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
000078  /* Ex */   27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 30,
000079  /* Fx */   27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27
000080  #endif
000081  #ifdef SQLITE_EBCDIC
000082  /*         x0  x1  x2  x3  x4  x5  x6  x7  x8  x9  xa  xb  xc  xd  xe  xf */
000083  /* 0x */   29, 28, 28, 28, 28,  7, 28, 28, 28, 28, 28, 28,  7,  7, 28, 28,
000084  /* 1x */   28, 28, 28, 28, 28,  7, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
000085  /* 2x */   28, 28, 28, 28, 28,  7, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
000086  /* 3x */   28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
000087  /* 4x */    7, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 26, 12, 17, 20, 10,
000088  /* 5x */   24, 28, 28, 28, 28, 28, 28, 28, 28, 28, 15,  4, 21, 18, 19, 28,
000089  /* 6x */   11, 16, 28, 28, 28, 28, 28, 28, 28, 28, 28, 23, 22,  2, 13,  6,
000090  /* 7x */   28, 28, 28, 28, 28, 28, 28, 28, 28,  8,  5,  5,  5,  8, 14,  8,
000091  /* 8x */   28,  1,  1,  1,  1,  1,  1,  1,  1,  1, 28, 28, 28, 28, 28, 28,
000092  /* 9x */   28,  1,  1,  1,  1,  1,  1,  1,  1,  1, 28, 28, 28, 28, 28, 28,
000093  /* Ax */   28, 25,  1,  1,  1,  1,  1,  0,  2,  2, 28, 28, 28, 28, 28, 28,
000094  /* Bx */   28, 28, 28, 28, 28, 28, 28, 28, 28, 28,  9, 28, 28, 28, 28, 28,
000095  /* Cx */   28,  1,  1,  1,  1,  1,  1,  1,  1,  1, 28, 28, 28, 28, 28, 28,
000096  /* Dx */   28,  1,  1,  1,  1,  1,  1,  1,  1,  1, 28, 28, 28, 28, 28, 28,
000097  /* Ex */   28, 28,  1,  1,  1,  1,  1,  0,  2,  2, 28, 28, 28, 28, 28, 28,
000098  /* Fx */    3,  3,  3,  3,  3,  3,  3,  3,  3,  3, 28, 28, 28, 28, 28, 28,
000099  #endif
000100  };
000101  
000102  /*
000103  ** The charMap() macro maps alphabetic characters (only) into their
000104  ** lower-case ASCII equivalent.  On ASCII machines, this is just
000105  ** an upper-to-lower case map.  On EBCDIC machines we also need
000106  ** to adjust the encoding.  The mapping is only valid for alphabetics
000107  ** which are the only characters for which this feature is used. 
000108  **
000109  ** Used by keywordhash.h
000110  */
000111  #ifdef SQLITE_ASCII
000112  # define charMap(X) sqlite3UpperToLower[(unsigned char)X]
000113  #endif
000114  #ifdef SQLITE_EBCDIC
000115  # define charMap(X) ebcdicToAscii[(unsigned char)X]
000116  const unsigned char ebcdicToAscii[] = {
000117  /* 0   1   2   3   4   5   6   7   8   9   A   B   C   D   E   F */
000118     0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  /* 0x */
000119     0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  /* 1x */
000120     0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  /* 2x */
000121     0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  /* 3x */
000122     0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  /* 4x */
000123     0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  /* 5x */
000124     0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 95,  0,  0,  /* 6x */
000125     0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  /* 7x */
000126     0, 97, 98, 99,100,101,102,103,104,105,  0,  0,  0,  0,  0,  0,  /* 8x */
000127     0,106,107,108,109,110,111,112,113,114,  0,  0,  0,  0,  0,  0,  /* 9x */
000128     0,  0,115,116,117,118,119,120,121,122,  0,  0,  0,  0,  0,  0,  /* Ax */
000129     0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  /* Bx */
000130     0, 97, 98, 99,100,101,102,103,104,105,  0,  0,  0,  0,  0,  0,  /* Cx */
000131     0,106,107,108,109,110,111,112,113,114,  0,  0,  0,  0,  0,  0,  /* Dx */
000132     0,  0,115,116,117,118,119,120,121,122,  0,  0,  0,  0,  0,  0,  /* Ex */
000133     0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  /* Fx */
000134  };
000135  #endif
000136  
000137  /*
000138  ** The sqlite3KeywordCode function looks up an identifier to determine if
000139  ** it is a keyword.  If it is a keyword, the token code of that keyword is 
000140  ** returned.  If the input is not a keyword, TK_ID is returned.
000141  **
000142  ** The implementation of this routine was generated by a program,
000143  ** mkkeywordhash.c, located in the tool subdirectory of the distribution.
000144  ** The output of the mkkeywordhash.c program is written into a file
000145  ** named keywordhash.h and then included into this source file by
000146  ** the #include below.
000147  */
000148  #include "keywordhash.h"
000149  
000150  
000151  /*
000152  ** If X is a character that can be used in an identifier then
000153  ** IdChar(X) will be true.  Otherwise it is false.
000154  **
000155  ** For ASCII, any character with the high-order bit set is
000156  ** allowed in an identifier.  For 7-bit characters, 
000157  ** sqlite3IsIdChar[X] must be 1.
000158  **
000159  ** For EBCDIC, the rules are more complex but have the same
000160  ** end result.
000161  **
000162  ** Ticket #1066.  the SQL standard does not allow '$' in the
000163  ** middle of identifiers.  But many SQL implementations do. 
000164  ** SQLite will allow '$' in identifiers for compatibility.
000165  ** But the feature is undocumented.
000166  */
000167  #ifdef SQLITE_ASCII
000168  #define IdChar(C)  ((sqlite3CtypeMap[(unsigned char)C]&0x46)!=0)
000169  #endif
000170  #ifdef SQLITE_EBCDIC
000171  const char sqlite3IsEbcdicIdChar[] = {
000172  /* x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 xA xB xC xD xE xF */
000173      0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0,  /* 4x */
000174      0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0,  /* 5x */
000175      0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0,  /* 6x */
000176      0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0,  /* 7x */
000177      0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0,  /* 8x */
000178      0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0,  /* 9x */
000179      1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0,  /* Ax */
000180      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /* Bx */
000181      0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1,  /* Cx */
000182      0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1,  /* Dx */
000183      0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1,  /* Ex */
000184      1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0,  /* Fx */
000185  };
000186  #define IdChar(C)  (((c=C)>=0x42 && sqlite3IsEbcdicIdChar[c-0x40]))
000187  #endif
000188  
000189  /* Make the IdChar function accessible from ctime.c and alter.c */
000190  int sqlite3IsIdChar(u8 c){ return IdChar(c); }
000191  
000192  #ifndef SQLITE_OMIT_WINDOWFUNC
000193  /*
000194  ** Return the id of the next token in string (*pz). Before returning, set
000195  ** (*pz) to point to the byte following the parsed token.
000196  */
000197  static int getToken(const unsigned char **pz){
000198    const unsigned char *z = *pz;
000199    int t;                          /* Token type to return */
000200    do {
000201      z += sqlite3GetToken(z, &t);
000202    }while( t==TK_SPACE );
000203    if( t==TK_ID 
000204     || t==TK_STRING 
000205     || t==TK_JOIN_KW 
000206     || t==TK_WINDOW 
000207     || t==TK_OVER 
000208     || sqlite3ParserFallback(t)==TK_ID 
000209    ){
000210      t = TK_ID;
000211    }
000212    *pz = z;
000213    return t;
000214  }
000215  
000216  /*
000217  ** The following three functions are called immediately after the tokenizer
000218  ** reads the keywords WINDOW, OVER and FILTER, respectively, to determine
000219  ** whether the token should be treated as a keyword or an SQL identifier.
000220  ** This cannot be handled by the usual lemon %fallback method, due to
000221  ** the ambiguity in some constructions. e.g.
000222  **
000223  **   SELECT sum(x) OVER ...
000224  **
000225  ** In the above, "OVER" might be a keyword, or it might be an alias for the 
000226  ** sum(x) expression. If a "%fallback ID OVER" directive were added to 
000227  ** grammar, then SQLite would always treat "OVER" as an alias, making it
000228  ** impossible to call a window-function without a FILTER clause.
000229  **
000230  ** WINDOW is treated as a keyword if:
000231  **
000232  **   * the following token is an identifier, or a keyword that can fallback
000233  **     to being an identifier, and
000234  **   * the token after than one is TK_AS.
000235  **
000236  ** OVER is a keyword if:
000237  **
000238  **   * the previous token was TK_RP, and
000239  **   * the next token is either TK_LP or an identifier.
000240  **
000241  ** FILTER is a keyword if:
000242  **
000243  **   * the previous token was TK_RP, and
000244  **   * the next token is TK_LP.
000245  */
000246  static int analyzeWindowKeyword(const unsigned char *z){
000247    int t;
000248    t = getToken(&z);
000249    if( t!=TK_ID ) return TK_ID;
000250    t = getToken(&z);
000251    if( t!=TK_AS ) return TK_ID;
000252    return TK_WINDOW;
000253  }
000254  static int analyzeOverKeyword(const unsigned char *z, int lastToken){
000255    if( lastToken==TK_RP ){
000256      int t = getToken(&z);
000257      if( t==TK_LP || t==TK_ID ) return TK_OVER;
000258    }
000259    return TK_ID;
000260  }
000261  static int analyzeFilterKeyword(const unsigned char *z, int lastToken){
000262    if( lastToken==TK_RP && getToken(&z)==TK_LP ){
000263      return TK_FILTER;
000264    }
000265    return TK_ID;
000266  }
000267  #endif /* SQLITE_OMIT_WINDOWFUNC */
000268  
000269  /*
000270  ** Return the length (in bytes) of the token that begins at z[0]. 
000271  ** Store the token type in *tokenType before returning.
000272  */
000273  int sqlite3GetToken(const unsigned char *z, int *tokenType){
000274    int i, c;
000275    switch( aiClass[*z] ){  /* Switch on the character-class of the first byte
000276                            ** of the token. See the comment on the CC_ defines
000277                            ** above. */
000278      case CC_SPACE: {
000279        testcase( z[0]==' ' );
000280        testcase( z[0]=='\t' );
000281        testcase( z[0]=='\n' );
000282        testcase( z[0]=='\f' );
000283        testcase( z[0]=='\r' );
000284        for(i=1; sqlite3Isspace(z[i]); i++){}
000285        *tokenType = TK_SPACE;
000286        return i;
000287      }
000288      case CC_MINUS: {
000289        if( z[1]=='-' ){
000290          for(i=2; (c=z[i])!=0 && c!='\n'; i++){}
000291          *tokenType = TK_SPACE;   /* IMP: R-22934-25134 */
000292          return i;
000293        }else if( z[1]=='>' ){
000294          *tokenType = TK_PTR;
000295          return 2 + (z[2]=='>');
000296        }
000297        *tokenType = TK_MINUS;
000298        return 1;
000299      }
000300      case CC_LP: {
000301        *tokenType = TK_LP;
000302        return 1;
000303      }
000304      case CC_RP: {
000305        *tokenType = TK_RP;
000306        return 1;
000307      }
000308      case CC_SEMI: {
000309        *tokenType = TK_SEMI;
000310        return 1;
000311      }
000312      case CC_PLUS: {
000313        *tokenType = TK_PLUS;
000314        return 1;
000315      }
000316      case CC_STAR: {
000317        *tokenType = TK_STAR;
000318        return 1;
000319      }
000320      case CC_SLASH: {
000321        if( z[1]!='*' || z[2]==0 ){
000322          *tokenType = TK_SLASH;
000323          return 1;
000324        }
000325        for(i=3, c=z[2]; (c!='*' || z[i]!='/') && (c=z[i])!=0; i++){}
000326        if( c ) i++;
000327        *tokenType = TK_SPACE;   /* IMP: R-22934-25134 */
000328        return i;
000329      }
000330      case CC_PERCENT: {
000331        *tokenType = TK_REM;
000332        return 1;
000333      }
000334      case CC_EQ: {
000335        *tokenType = TK_EQ;
000336        return 1 + (z[1]=='=');
000337      }
000338      case CC_LT: {
000339        if( (c=z[1])=='=' ){
000340          *tokenType = TK_LE;
000341          return 2;
000342        }else if( c=='>' ){
000343          *tokenType = TK_NE;
000344          return 2;
000345        }else if( c=='<' ){
000346          *tokenType = TK_LSHIFT;
000347          return 2;
000348        }else{
000349          *tokenType = TK_LT;
000350          return 1;
000351        }
000352      }
000353      case CC_GT: {
000354        if( (c=z[1])=='=' ){
000355          *tokenType = TK_GE;
000356          return 2;
000357        }else if( c=='>' ){
000358          *tokenType = TK_RSHIFT;
000359          return 2;
000360        }else{
000361          *tokenType = TK_GT;
000362          return 1;
000363        }
000364      }
000365      case CC_BANG: {
000366        if( z[1]!='=' ){
000367          *tokenType = TK_ILLEGAL;
000368          return 1;
000369        }else{
000370          *tokenType = TK_NE;
000371          return 2;
000372        }
000373      }
000374      case CC_PIPE: {
000375        if( z[1]!='|' ){
000376          *tokenType = TK_BITOR;
000377          return 1;
000378        }else{
000379          *tokenType = TK_CONCAT;
000380          return 2;
000381        }
000382      }
000383      case CC_COMMA: {
000384        *tokenType = TK_COMMA;
000385        return 1;
000386      }
000387      case CC_AND: {
000388        *tokenType = TK_BITAND;
000389        return 1;
000390      }
000391      case CC_TILDA: {
000392        *tokenType = TK_BITNOT;
000393        return 1;
000394      }
000395      case CC_QUOTE: {
000396        int delim = z[0];
000397        testcase( delim=='`' );
000398        testcase( delim=='\'' );
000399        testcase( delim=='"' );
000400        for(i=1; (c=z[i])!=0; i++){
000401          if( c==delim ){
000402            if( z[i+1]==delim ){
000403              i++;
000404            }else{
000405              break;
000406            }
000407          }
000408        }
000409        if( c=='\'' ){
000410          *tokenType = TK_STRING;
000411          return i+1;
000412        }else if( c!=0 ){
000413          *tokenType = TK_ID;
000414          return i+1;
000415        }else{
000416          *tokenType = TK_ILLEGAL;
000417          return i;
000418        }
000419      }
000420      case CC_DOT: {
000421  #ifndef SQLITE_OMIT_FLOATING_POINT
000422        if( !sqlite3Isdigit(z[1]) )
000423  #endif
000424        {
000425          *tokenType = TK_DOT;
000426          return 1;
000427        }
000428        /* If the next character is a digit, this is a floating point
000429        ** number that begins with ".".  Fall thru into the next case */
000430        /* no break */ deliberate_fall_through
000431      }
000432      case CC_DIGIT: {
000433        testcase( z[0]=='0' );  testcase( z[0]=='1' );  testcase( z[0]=='2' );
000434        testcase( z[0]=='3' );  testcase( z[0]=='4' );  testcase( z[0]=='5' );
000435        testcase( z[0]=='6' );  testcase( z[0]=='7' );  testcase( z[0]=='8' );
000436        testcase( z[0]=='9' );
000437        *tokenType = TK_INTEGER;
000438  #ifndef SQLITE_OMIT_HEX_INTEGER
000439        if( z[0]=='0' && (z[1]=='x' || z[1]=='X') && sqlite3Isxdigit(z[2]) ){
000440          for(i=3; sqlite3Isxdigit(z[i]); i++){}
000441          return i;
000442        }
000443  #endif
000444        for(i=0; sqlite3Isdigit(z[i]); i++){}
000445  #ifndef SQLITE_OMIT_FLOATING_POINT
000446        if( z[i]=='.' ){
000447          i++;
000448          while( sqlite3Isdigit(z[i]) ){ i++; }
000449          *tokenType = TK_FLOAT;
000450        }
000451        if( (z[i]=='e' || z[i]=='E') &&
000452             ( sqlite3Isdigit(z[i+1]) 
000453              || ((z[i+1]=='+' || z[i+1]=='-') && sqlite3Isdigit(z[i+2]))
000454             )
000455        ){
000456          i += 2;
000457          while( sqlite3Isdigit(z[i]) ){ i++; }
000458          *tokenType = TK_FLOAT;
000459        }
000460  #endif
000461        while( IdChar(z[i]) ){
000462          *tokenType = TK_ILLEGAL;
000463          i++;
000464        }
000465        return i;
000466      }
000467      case CC_QUOTE2: {
000468        for(i=1, c=z[0]; c!=']' && (c=z[i])!=0; i++){}
000469        *tokenType = c==']' ? TK_ID : TK_ILLEGAL;
000470        return i;
000471      }
000472      case CC_VARNUM: {
000473        *tokenType = TK_VARIABLE;
000474        for(i=1; sqlite3Isdigit(z[i]); i++){}
000475        return i;
000476      }
000477      case CC_DOLLAR:
000478      case CC_VARALPHA: {
000479        int n = 0;
000480        testcase( z[0]=='$' );  testcase( z[0]=='@' );
000481        testcase( z[0]==':' );  testcase( z[0]=='#' );
000482        *tokenType = TK_VARIABLE;
000483        for(i=1; (c=z[i])!=0; i++){
000484          if( IdChar(c) ){
000485            n++;
000486  #ifndef SQLITE_OMIT_TCL_VARIABLE
000487          }else if( c=='(' && n>0 ){
000488            do{
000489              i++;
000490            }while( (c=z[i])!=0 && !sqlite3Isspace(c) && c!=')' );
000491            if( c==')' ){
000492              i++;
000493            }else{
000494              *tokenType = TK_ILLEGAL;
000495            }
000496            break;
000497          }else if( c==':' && z[i+1]==':' ){
000498            i++;
000499  #endif
000500          }else{
000501            break;
000502          }
000503        }
000504        if( n==0 ) *tokenType = TK_ILLEGAL;
000505        return i;
000506      }
000507      case CC_KYWD0: {
000508        for(i=1; aiClass[z[i]]<=CC_KYWD; i++){}
000509        if( IdChar(z[i]) ){
000510          /* This token started out using characters that can appear in keywords,
000511          ** but z[i] is a character not allowed within keywords, so this must
000512          ** be an identifier instead */
000513          i++;
000514          break;
000515        }
000516        *tokenType = TK_ID;
000517        return keywordCode((char*)z, i, tokenType);
000518      }
000519      case CC_X: {
000520  #ifndef SQLITE_OMIT_BLOB_LITERAL
000521        testcase( z[0]=='x' ); testcase( z[0]=='X' );
000522        if( z[1]=='\'' ){
000523          *tokenType = TK_BLOB;
000524          for(i=2; sqlite3Isxdigit(z[i]); i++){}
000525          if( z[i]!='\'' || i%2 ){
000526            *tokenType = TK_ILLEGAL;
000527            while( z[i] && z[i]!='\'' ){ i++; }
000528          }
000529          if( z[i] ) i++;
000530          return i;
000531        }
000532  #endif
000533        /* If it is not a BLOB literal, then it must be an ID, since no
000534        ** SQL keywords start with the letter 'x'.  Fall through */
000535        /* no break */ deliberate_fall_through
000536      }
000537      case CC_KYWD:
000538      case CC_ID: {
000539        i = 1;
000540        break;
000541      }
000542      case CC_BOM: {
000543        if( z[1]==0xbb && z[2]==0xbf ){
000544          *tokenType = TK_SPACE;
000545          return 3;
000546        }
000547        i = 1;
000548        break;
000549      }
000550      case CC_NUL: {
000551        *tokenType = TK_ILLEGAL;
000552        return 0;
000553      }
000554      default: {
000555        *tokenType = TK_ILLEGAL;
000556        return 1;
000557      }
000558    }
000559    while( IdChar(z[i]) ){ i++; }
000560    *tokenType = TK_ID;
000561    return i;
000562  }
000563  
000564  /*
000565  ** Run the parser on the given SQL string.
000566  */
000567  int sqlite3RunParser(Parse *pParse, const char *zSql){
000568    int nErr = 0;                   /* Number of errors encountered */
000569    void *pEngine;                  /* The LEMON-generated LALR(1) parser */
000570    int n = 0;                      /* Length of the next token token */
000571    int tokenType;                  /* type of the next token */
000572    int lastTokenParsed = -1;       /* type of the previous token */
000573    sqlite3 *db = pParse->db;       /* The database connection */
000574    int mxSqlLen;                   /* Max length of an SQL string */
000575    Parse *pParentParse = 0;        /* Outer parse context, if any */
000576  #ifdef sqlite3Parser_ENGINEALWAYSONSTACK
000577    yyParser sEngine;    /* Space to hold the Lemon-generated Parser object */
000578  #endif
000579    VVA_ONLY( u8 startedWithOom = db->mallocFailed );
000580  
000581    assert( zSql!=0 );
000582    mxSqlLen = db->aLimit[SQLITE_LIMIT_SQL_LENGTH];
000583    if( db->nVdbeActive==0 ){
000584      AtomicStore(&db->u1.isInterrupted, 0);
000585    }
000586    pParse->rc = SQLITE_OK;
000587    pParse->zTail = zSql;
000588  #ifdef SQLITE_DEBUG
000589    if( db->flags & SQLITE_ParserTrace ){
000590      printf("parser: [[[%s]]]\n", zSql);
000591      sqlite3ParserTrace(stdout, "parser: ");
000592    }else{
000593      sqlite3ParserTrace(0, 0);
000594    }
000595  #endif
000596  #ifdef sqlite3Parser_ENGINEALWAYSONSTACK
000597    pEngine = &sEngine;
000598    sqlite3ParserInit(pEngine, pParse);
000599  #else
000600    pEngine = sqlite3ParserAlloc(sqlite3Malloc, pParse);
000601    if( pEngine==0 ){
000602      sqlite3OomFault(db);
000603      return SQLITE_NOMEM_BKPT;
000604    }
000605  #endif
000606    assert( pParse->pNewTable==0 );
000607    assert( pParse->pNewTrigger==0 );
000608    assert( pParse->nVar==0 );
000609    assert( pParse->pVList==0 );
000610    pParentParse = db->pParse;
000611    db->pParse = pParse;
000612    while( 1 ){
000613      n = sqlite3GetToken((u8*)zSql, &tokenType);
000614      mxSqlLen -= n;
000615      if( mxSqlLen<0 ){
000616        pParse->rc = SQLITE_TOOBIG;
000617        break;
000618      }
000619  #ifndef SQLITE_OMIT_WINDOWFUNC
000620      if( tokenType>=TK_WINDOW ){
000621        assert( tokenType==TK_SPACE || tokenType==TK_OVER || tokenType==TK_FILTER
000622             || tokenType==TK_ILLEGAL || tokenType==TK_WINDOW 
000623        );
000624  #else
000625      if( tokenType>=TK_SPACE ){
000626        assert( tokenType==TK_SPACE || tokenType==TK_ILLEGAL );
000627  #endif /* SQLITE_OMIT_WINDOWFUNC */
000628        if( AtomicLoad(&db->u1.isInterrupted) ){
000629          pParse->rc = SQLITE_INTERRUPT;
000630          pParse->nErr++;
000631          break;
000632        }
000633        if( tokenType==TK_SPACE ){
000634          zSql += n;
000635          continue;
000636        }
000637        if( zSql[0]==0 ){
000638          /* Upon reaching the end of input, call the parser two more times
000639          ** with tokens TK_SEMI and 0, in that order. */
000640          if( lastTokenParsed==TK_SEMI ){
000641            tokenType = 0;
000642          }else if( lastTokenParsed==0 ){
000643            break;
000644          }else{
000645            tokenType = TK_SEMI;
000646          }
000647          n = 0;
000648  #ifndef SQLITE_OMIT_WINDOWFUNC
000649        }else if( tokenType==TK_WINDOW ){
000650          assert( n==6 );
000651          tokenType = analyzeWindowKeyword((const u8*)&zSql[6]);
000652        }else if( tokenType==TK_OVER ){
000653          assert( n==4 );
000654          tokenType = analyzeOverKeyword((const u8*)&zSql[4], lastTokenParsed);
000655        }else if( tokenType==TK_FILTER ){
000656          assert( n==6 );
000657          tokenType = analyzeFilterKeyword((const u8*)&zSql[6], lastTokenParsed);
000658  #endif /* SQLITE_OMIT_WINDOWFUNC */
000659        }else{
000660          Token x;
000661          x.z = zSql;
000662          x.n = n;
000663          sqlite3ErrorMsg(pParse, "unrecognized token: \"%T\"", &x);
000664          break;
000665        }
000666      }
000667      pParse->sLastToken.z = zSql;
000668      pParse->sLastToken.n = n;
000669      sqlite3Parser(pEngine, tokenType, pParse->sLastToken);
000670      lastTokenParsed = tokenType;
000671      zSql += n;
000672      assert( db->mallocFailed==0 || pParse->rc!=SQLITE_OK || startedWithOom );
000673      if( pParse->rc!=SQLITE_OK ) break;
000674    }
000675    assert( nErr==0 );
000676  #ifdef YYTRACKMAXSTACKDEPTH
000677    sqlite3_mutex_enter(sqlite3MallocMutex());
000678    sqlite3StatusHighwater(SQLITE_STATUS_PARSER_STACK,
000679        sqlite3ParserStackPeak(pEngine)
000680    );
000681    sqlite3_mutex_leave(sqlite3MallocMutex());
000682  #endif /* YYDEBUG */
000683  #ifdef sqlite3Parser_ENGINEALWAYSONSTACK
000684    sqlite3ParserFinalize(pEngine);
000685  #else
000686    sqlite3ParserFree(pEngine, sqlite3_free);
000687  #endif
000688    if( db->mallocFailed ){
000689      pParse->rc = SQLITE_NOMEM_BKPT;
000690    }
000691    if( pParse->zErrMsg || (pParse->rc!=SQLITE_OK && pParse->rc!=SQLITE_DONE) ){
000692      if( pParse->zErrMsg==0 ){
000693        pParse->zErrMsg = sqlite3MPrintf(db, "%s", sqlite3ErrStr(pParse->rc));
000694      }
000695      sqlite3_log(pParse->rc, "%s in \"%s\"", pParse->zErrMsg, pParse->zTail);
000696      nErr++;
000697    }
000698    pParse->zTail = zSql;
000699  #ifndef SQLITE_OMIT_VIRTUALTABLE
000700    sqlite3_free(pParse->apVtabLock);
000701  #endif
000702  
000703    if( pParse->pNewTable && !IN_SPECIAL_PARSE ){
000704      /* If the pParse->declareVtab flag is set, do not delete any table 
000705      ** structure built up in pParse->pNewTable. The calling code (see vtab.c)
000706      ** will take responsibility for freeing the Table structure.
000707      */
000708      sqlite3DeleteTable(db, pParse->pNewTable);
000709    }
000710    if( pParse->pNewTrigger && !IN_RENAME_OBJECT ){
000711      sqlite3DeleteTrigger(db, pParse->pNewTrigger);
000712    }
000713    sqlite3DbFree(db, pParse->pVList);
000714    db->pParse = pParentParse;
000715    assert( nErr==0 || pParse->rc!=SQLITE_OK );
000716    return nErr;
000717  }
000718  
000719  
000720  #ifdef SQLITE_ENABLE_NORMALIZE
000721  /*
000722  ** Insert a single space character into pStr if the current string
000723  ** ends with an identifier
000724  */
000725  static void addSpaceSeparator(sqlite3_str *pStr){
000726    if( pStr->nChar && sqlite3IsIdChar(pStr->zText[pStr->nChar-1]) ){
000727      sqlite3_str_append(pStr, " ", 1);
000728    }
000729  }
000730  
000731  /*
000732  ** Compute a normalization of the SQL given by zSql[0..nSql-1].  Return
000733  ** the normalization in space obtained from sqlite3DbMalloc().  Or return
000734  ** NULL if anything goes wrong or if zSql is NULL.
000735  */
000736  char *sqlite3Normalize(
000737    Vdbe *pVdbe,       /* VM being reprepared */
000738    const char *zSql   /* The original SQL string */
000739  ){
000740    sqlite3 *db;       /* The database connection */
000741    int i;             /* Next unread byte of zSql[] */
000742    int n;             /* length of current token */
000743    int tokenType;     /* type of current token */
000744    int prevType = 0;  /* Previous non-whitespace token */
000745    int nParen;        /* Number of nested levels of parentheses */
000746    int iStartIN;      /* Start of RHS of IN operator in z[] */
000747    int nParenAtIN;    /* Value of nParent at start of RHS of IN operator */
000748    u32 j;             /* Bytes of normalized SQL generated so far */
000749    sqlite3_str *pStr; /* The normalized SQL string under construction */
000750  
000751    db = sqlite3VdbeDb(pVdbe);
000752    tokenType = -1;
000753    nParen = iStartIN = nParenAtIN = 0;
000754    pStr = sqlite3_str_new(db);
000755    assert( pStr!=0 );  /* sqlite3_str_new() never returns NULL */
000756    for(i=0; zSql[i] && pStr->accError==0; i+=n){
000757      if( tokenType!=TK_SPACE ){
000758        prevType = tokenType;
000759      }
000760      n = sqlite3GetToken((unsigned char*)zSql+i, &tokenType);
000761      if( NEVER(n<=0) ) break;
000762      switch( tokenType ){
000763        case TK_SPACE: {
000764          break;
000765        }
000766        case TK_NULL: {
000767          if( prevType==TK_IS || prevType==TK_NOT ){
000768            sqlite3_str_append(pStr, " NULL", 5);
000769            break;
000770          }
000771          /* Fall through */
000772        }
000773        case TK_STRING:
000774        case TK_INTEGER:
000775        case TK_FLOAT:
000776        case TK_VARIABLE:
000777        case TK_BLOB: {
000778          sqlite3_str_append(pStr, "?", 1);
000779          break;
000780        }
000781        case TK_LP: {
000782          nParen++;
000783          if( prevType==TK_IN ){
000784            iStartIN = pStr->nChar;
000785            nParenAtIN = nParen;
000786          }
000787          sqlite3_str_append(pStr, "(", 1);
000788          break;
000789        }
000790        case TK_RP: {
000791          if( iStartIN>0 && nParen==nParenAtIN ){
000792            assert( pStr->nChar>=(u32)iStartIN );
000793            pStr->nChar = iStartIN+1;
000794            sqlite3_str_append(pStr, "?,?,?", 5);
000795            iStartIN = 0;
000796          }
000797          nParen--;
000798          sqlite3_str_append(pStr, ")", 1);
000799          break;
000800        }
000801        case TK_ID: {
000802          iStartIN = 0;
000803          j = pStr->nChar;
000804          if( sqlite3Isquote(zSql[i]) ){
000805            char *zId = sqlite3DbStrNDup(db, zSql+i, n);
000806            int nId;
000807            int eType = 0;
000808            if( zId==0 ) break;
000809            sqlite3Dequote(zId);
000810            if( zSql[i]=='"' && sqlite3VdbeUsesDoubleQuotedString(pVdbe, zId) ){
000811              sqlite3_str_append(pStr, "?", 1);
000812              sqlite3DbFree(db, zId);
000813              break;
000814            }
000815            nId = sqlite3Strlen30(zId);
000816            if( sqlite3GetToken((u8*)zId, &eType)==nId && eType==TK_ID ){
000817              addSpaceSeparator(pStr);
000818              sqlite3_str_append(pStr, zId, nId);
000819            }else{
000820              sqlite3_str_appendf(pStr, "\"%w\"", zId);
000821            }
000822            sqlite3DbFree(db, zId);
000823          }else{
000824            addSpaceSeparator(pStr);
000825            sqlite3_str_append(pStr, zSql+i, n);
000826          }
000827          while( j<pStr->nChar ){
000828            pStr->zText[j] = sqlite3Tolower(pStr->zText[j]);
000829            j++;
000830          }
000831          break;
000832        }
000833        case TK_SELECT: {
000834          iStartIN = 0;
000835          /* fall through */
000836        }
000837        default: {
000838          if( sqlite3IsIdChar(zSql[i]) ) addSpaceSeparator(pStr);
000839          j = pStr->nChar;
000840          sqlite3_str_append(pStr, zSql+i, n);
000841          while( j<pStr->nChar ){
000842            pStr->zText[j] = sqlite3Toupper(pStr->zText[j]);
000843            j++;
000844          }
000845          break;
000846        }
000847      }
000848    }
000849    if( tokenType!=TK_SEMI ) sqlite3_str_append(pStr, ";", 1);
000850    return sqlite3_str_finish(pStr);
000851  }
000852  #endif /* SQLITE_ENABLE_NORMALIZE */