1 /* 2 ** 2001 September 15 3 ** 4 ** The author disclaims copyright to this source code. In place of 5 ** a legal notice, here is a blessing: 6 ** 7 ** May you do good and not evil. 8 ** May you find forgiveness for yourself and forgive others. 9 ** May you share freely, never taking more than you give. 10 ** 11 ************************************************************************* 12 ** A tokenizer for SQL 13 ** 14 ** This file contains C code that splits an SQL input string up into 15 ** individual tokens and sends those tokens one-by-one over to the 16 ** parser for analysis. 17 */ 18 19 #include <ctype.h> 20 #include <stdarg.h> 21 #include <stdlib.h> 22 23 #include "windef.h" 24 #include "winbase.h" 25 #include "wine/unicode.h" 26 #include "query.h" 27 #include "sql.tab.h" 28 29 /* 30 ** All the keywords of the SQL language are stored as in a hash 31 ** table composed of instances of the following structure. 32 */ 33 typedef struct Keyword Keyword; 34 struct Keyword { 35 const WCHAR *name; /* The keyword name */ 36 unsigned int len; 37 int tokenType; /* The token value for this keyword */ 38 }; 39 40 #define MAX_TOKEN_LEN 11 41 42 static const WCHAR addW[] = {'A','D','D'}; 43 static const WCHAR alterW[] = {'A','L','T','E','R'}; 44 static const WCHAR andW[] = {'A','N','D'}; 45 static const WCHAR byW[] = {'B','Y'}; 46 static const WCHAR charW[] = {'C','H','A','R'}; 47 static const WCHAR characterW[] = {'C','H','A','R','A','C','T','E','R'}; 48 static const WCHAR createW[] = {'C','R','E','A','T','E'}; 49 static const WCHAR deleteW[] = {'D','E','L','E','T','E'}; 50 static const WCHAR distinctW[] = {'D','I','S','T','I','N','C','T'}; 51 static const WCHAR dropW[] = {'D','R','O','P'}; 52 static const WCHAR freeW[] = {'F','R','E','E'}; 53 static const WCHAR fromW[] = {'F','R','O','M'}; 54 static const WCHAR holdW[] = {'H','O','L','D'}; 55 static const WCHAR insertW[] = {'I','N','S','E','R','T'}; 56 static const WCHAR intW[] = {'I','N','T'}; 57 static const WCHAR integerW[] = {'I','N','T','E','G','E','R'}; 58 static const WCHAR intoW[] = {'I','N','T','O'}; 59 static const WCHAR isW[] = {'I','S'}; 60 static const WCHAR keyW[] = {'K','E','Y'}; 61 static const WCHAR likeW[] = {'L','I','K','E'}; 62 static const WCHAR localizableW[] = {'L','O','C','A','L','I','Z','A','B','L','E'}; 63 static const WCHAR longW[] = {'L','O','N','G'}; 64 static const WCHAR longcharW[] = {'L','O','N','G','C','H','A','R'}; 65 static const WCHAR notW[] = {'N','O','T'}; 66 static const WCHAR nullW[] = {'N','U','L','L'}; 67 static const WCHAR objectW[] = {'O','B','J','E','C','T'}; 68 static const WCHAR orW[] = {'O','R'}; 69 static const WCHAR orderW[] = {'O','R','D','E','R'}; 70 static const WCHAR primaryW[] = {'P','R','I','M','A','R','Y'}; 71 static const WCHAR selectW[] = {'S','E','L','E','C','T'}; 72 static const WCHAR setW[] = {'S','E','T'}; 73 static const WCHAR shortW[] = {'S','H','O','R','T'}; 74 static const WCHAR tableW[] = {'T','A','B','L','E'}; 75 static const WCHAR temporaryW[] = {'T','E','M','P','O','R','A','R','Y'}; 76 static const WCHAR updateW[] = {'U','P','D','A','T','E'}; 77 static const WCHAR valuesW[] = {'V','A','L','U','E','S'}; 78 static const WCHAR whereW[] = {'W','H','E','R','E'}; 79 80 #define ARRAY_SIZE(array) (sizeof(array)/sizeof((array)[0])) 81 82 /* 83 ** These are the keywords 84 ** They MUST be in alphabetical order 85 */ 86 static const Keyword aKeywordTable[] = { 87 { addW, ARRAY_SIZE(addW), TK_ADD }, 88 { alterW, ARRAY_SIZE(alterW), TK_ALTER }, 89 { andW, ARRAY_SIZE(andW), TK_AND }, 90 { byW, ARRAY_SIZE(byW), TK_BY }, 91 { charW, ARRAY_SIZE(charW), TK_CHAR }, 92 { characterW, ARRAY_SIZE(characterW), TK_CHAR }, 93 { createW, ARRAY_SIZE(createW), TK_CREATE }, 94 { deleteW, ARRAY_SIZE(deleteW), TK_DELETE }, 95 { distinctW, ARRAY_SIZE(distinctW), TK_DISTINCT }, 96 { dropW, ARRAY_SIZE(dropW), TK_DROP }, 97 { freeW, ARRAY_SIZE(freeW), TK_FREE }, 98 { fromW, ARRAY_SIZE(fromW), TK_FROM }, 99 { holdW, ARRAY_SIZE(holdW), TK_HOLD }, 100 { insertW, ARRAY_SIZE(insertW), TK_INSERT }, 101 { intW, ARRAY_SIZE(intW), TK_INT }, 102 { integerW, ARRAY_SIZE(integerW), TK_INT }, 103 { intoW, ARRAY_SIZE(intoW), TK_INTO }, 104 { isW, ARRAY_SIZE(isW), TK_IS }, 105 { keyW, ARRAY_SIZE(keyW), TK_KEY }, 106 { likeW, ARRAY_SIZE(likeW), TK_LIKE }, 107 { localizableW, ARRAY_SIZE(localizableW), TK_LOCALIZABLE }, 108 { longW, ARRAY_SIZE(longW), TK_LONG }, 109 { longcharW, ARRAY_SIZE(longcharW), TK_LONGCHAR }, 110 { notW, ARRAY_SIZE(notW), TK_NOT }, 111 { nullW, ARRAY_SIZE(nullW), TK_NULL }, 112 { objectW, ARRAY_SIZE(objectW), TK_OBJECT }, 113 { orW, ARRAY_SIZE(orW), TK_OR }, 114 { orderW, ARRAY_SIZE(orderW), TK_ORDER }, 115 { primaryW, ARRAY_SIZE(primaryW), TK_PRIMARY }, 116 { selectW, ARRAY_SIZE(selectW), TK_SELECT }, 117 { setW, ARRAY_SIZE(setW), TK_SET }, 118 { shortW, ARRAY_SIZE(shortW), TK_SHORT }, 119 { tableW, ARRAY_SIZE(tableW), TK_TABLE }, 120 { temporaryW, ARRAY_SIZE(temporaryW), TK_TEMPORARY }, 121 { updateW, ARRAY_SIZE(updateW), TK_UPDATE }, 122 { valuesW, ARRAY_SIZE(valuesW), TK_VALUES }, 123 { whereW, ARRAY_SIZE(whereW), TK_WHERE }, 124 }; 125 126 /* 127 ** Comparison function for binary search. 128 */ 129 static int compKeyword(const void *m1, const void *m2){ 130 const Keyword *k1 = m1, *k2 = m2; 131 int ret, len = min( k1->len, k2->len ); 132 133 if ((ret = memicmpW( k1->name, k2->name, len ))) return ret; 134 if (k1->len < k2->len) return -1; 135 else if (k1->len > k2->len) return 1; 136 return 0; 137 } 138 139 /* 140 ** This function looks up an identifier to determine if it is a 141 ** keyword. If it is a keyword, the token code of that keyword is 142 ** returned. If the input is not a keyword, TK_ID is returned. 143 */ 144 static int sqliteKeywordCode(const WCHAR *z, int n){ 145 Keyword key, *r; 146 147 if( n>MAX_TOKEN_LEN ) 148 return TK_ID; 149 150 key.tokenType = 0; 151 key.name = z; 152 key.len = n; 153 r = bsearch( &key, aKeywordTable, ARRAY_SIZE(aKeywordTable), sizeof(Keyword), compKeyword ); 154 if( r ) 155 return r->tokenType; 156 return TK_ID; 157 } 158 159 160 /* 161 ** If X is a character that can be used in an identifier then 162 ** isIdChar[X] will be 1. Otherwise isIdChar[X] will be 0. 163 ** 164 ** In this implementation, an identifier can be a string of 165 ** alphabetic characters, digits, and "_" plus any character 166 ** with the high-order bit set. The latter rule means that 167 ** any sequence of UTF-8 characters or characters taken from 168 ** an extended ISO8859 character set can form an identifier. 169 */ 170 static const char isIdChar[] = { 171 /* x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 xA xB xC xD xE xF */ 172 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 0x */ 173 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 1x */ 174 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, /* 2x */ 175 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, /* 3x */ 176 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 4x */ 177 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, /* 5x */ 178 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 6x */ 179 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, /* 7x */ 180 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 8x */ 181 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 9x */ 182 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* Ax */ 183 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* Bx */ 184 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* Cx */ 185 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* Dx */ 186 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* Ex */ 187 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* Fx */ 188 }; 189 190 /* 191 ** WCHAR safe version of isdigit() 192 */ 193 static inline int isDigit(WCHAR c) 194 { 195 return c >= '0' && c <= '9'; 196 } 197 198 /* 199 ** WCHAR safe version of isspace(), except '\r' 200 */ 201 static inline int isSpace(WCHAR c) 202 { 203 return c == ' ' || c == '\t' || c == '\n' || c == '\f'; 204 } 205 206 /* 207 ** Return the length of the token that begins at z[0]. Return 208 ** -1 if the token is (or might be) incomplete. Store the token 209 ** type in *tokenType before returning. 210 */ 211 int sqliteGetToken(const WCHAR *z, int *tokenType, int *skip){ 212 int i; 213 214 *skip = 0; 215 switch( *z ){ 216 case ' ': case '\t': case '\n': case '\f': 217 for(i=1; isSpace(z[i]); i++){} 218 *tokenType = TK_SPACE; 219 return i; 220 case '-': 221 if( z[1]==0 ) return -1; 222 *tokenType = TK_MINUS; 223 return 1; 224 case '(': 225 *tokenType = TK_LP; 226 return 1; 227 case ')': 228 *tokenType = TK_RP; 229 return 1; 230 case '*': 231 *tokenType = TK_STAR; 232 return 1; 233 case '=': 234 *tokenType = TK_EQ; 235 return 1; 236 case '<': 237 if( z[1]=='=' ){ 238 *tokenType = TK_LE; 239 return 2; 240 }else if( z[1]=='>' ){ 241 *tokenType = TK_NE; 242 return 2; 243 }else{ 244 *tokenType = TK_LT; 245 return 1; 246 } 247 case '>': 248 if( z[1]=='=' ){ 249 *tokenType = TK_GE; 250 return 2; 251 }else{ 252 *tokenType = TK_GT; 253 return 1; 254 } 255 case '!': 256 if( z[1]!='=' ){ 257 *tokenType = TK_ILLEGAL; 258 return 2; 259 }else{ 260 *tokenType = TK_NE; 261 return 2; 262 } 263 case '?': 264 *tokenType = TK_WILDCARD; 265 return 1; 266 case ',': 267 *tokenType = TK_COMMA; 268 return 1; 269 case '`': case '\'': { 270 int delim = z[0]; 271 for(i=1; z[i]; i++){ 272 if( z[i]==delim ) 273 break; 274 } 275 if( z[i] ) i++; 276 if( delim == '`' ) 277 *tokenType = TK_ID; 278 else 279 *tokenType = TK_STRING; 280 return i; 281 } 282 case '.': 283 if( !isDigit(z[1]) ){ 284 *tokenType = TK_DOT; 285 return 1; 286 } 287 /* Fall through */ 288 case '0': case '1': case '2': case '3': case '4': 289 case '5': case '6': case '7': case '8': case '9': 290 *tokenType = TK_INTEGER; 291 for(i=1; isDigit(z[i]); i++){} 292 return i; 293 case '[': 294 for(i=1; z[i] && z[i-1]!=']'; i++){} 295 *tokenType = TK_ID; 296 return i; 297 default: 298 if( !isIdChar[*z] ){ 299 break; 300 } 301 for(i=1; isIdChar[z[i]]; i++){} 302 *tokenType = sqliteKeywordCode(z, i); 303 if( *tokenType == TK_ID && z[i] == '`' ) *skip = 1; 304 return i; 305 } 306 *tokenType = TK_ILLEGAL; 307 return 1; 308 } 309