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