1 /* 2 ** Copyright (c) 1999, 2000 D. Richard Hipp 3 ** 4 ** This program is free software; you can redistribute it and/or 5 ** modify it under the terms of the GNU General Public 6 ** License as published by the Free Software Foundation; either 7 ** version 2 of the License, or (at your option) any later version. 8 ** 9 ** This program is distributed in the hope that it will be useful, 10 ** but WITHOUT ANY WARRANTY; without even the implied warranty of 11 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 12 ** General Public License for more details. 13 ** 14 ** You should have received a copy of the GNU General Public 15 ** License along with this library; if not, write to the 16 ** Free Software Foundation, Inc., 59 Temple Place - Suite 330, 17 ** Boston, MA 02111-1307, USA. 18 ** 19 ** Author contact information: 20 ** [email protected] 21 ** http://www.hwaci.com/drh/ 22 ** 23 ************************************************************************* 24 ** Internal interface definitions for SQLite. 25 ** 26 ** @(#) $Id: sqliteInt.h,v 1.30 2000/08/28 15:51:44 drh Exp $ 27 */ 28 #include "sqlite.h" 29 #include "dbbe.h" 30 #include "vdbe.h" 31 #include "parse.h" 32 #include <gdbm.h> 33 #include <stdio.h> 34 #include <stdlib.h> 35 #include <string.h> 36 #include <assert.h> 37 38 /* 39 ** If memory allocation problems are found, recompile with 40 ** 41 ** -DMEMORY_DEBUG=1 42 ** 43 ** to enable some sanity checking on malloc() and free(). To 44 ** check for memory leaks, recompile with 45 ** 46 ** -DMEMORY_DEBUG=2 47 ** 48 ** and a line of text will be written to standard error for 49 ** each malloc() and free(). This output can be analyzed 50 ** by an AWK script to determine if there are any leaks. 51 */ 52 #ifdef MEMORY_DEBUG 53 # define sqliteMalloc(X) sqliteMalloc_(X,__FILE__,__LINE__) 54 # define sqliteFree(X) sqliteFree_(X,__FILE__,__LINE__) 55 # define sqliteRealloc(X,Y) sqliteRealloc_(X,Y,__FILE__,__LINE__) 56 # define sqliteStrDup(X) sqliteStrDup_(X,__FILE__,__LINE__) 57 # define sqliteStrNDup(X,Y) sqliteStrNDup_(X,Y,__FILE__,__LINE__) 58 void sqliteStrRealloc(char**); 59 #else 60 # define sqliteStrRealloc(X) 61 #endif 62 63 /* 64 ** The following global variables are used for testing and debugging 65 ** only. Thy only work if MEMORY_DEBUG is defined. 66 */ 67 #ifdef MEMORY_DEBUG 68 int sqlite_nMalloc; /* Number of sqliteMalloc() calls */ 69 int sqlite_nFree; /* Number of sqliteFree() calls */ 70 int sqlite_iMallocFail; /* Fail sqliteMalloc() after this many calls */ 71 #endif 72 73 /* 74 ** The number of entries in the in-memory hash array holding the 75 ** database schema. 76 */ 77 #define N_HASH 51 78 79 /* 80 ** Name of the master database table. The master database table 81 ** is a special table that holds the names and attributes of all 82 ** user tables and indices. 83 */ 84 #define MASTER_NAME "sqlite_master" 85 86 /* 87 ** A convenience macro that returns the number of elements in 88 ** an array. 89 */ 90 #define ArraySize(X) (sizeof(X)/sizeof(X[0])) 91 92 /* 93 ** Integer identifiers for built-in SQL functions. 94 */ 95 #define FN_Unknown 0 96 #define FN_Count 1 97 #define FN_Min 2 98 #define FN_Max 3 99 #define FN_Sum 4 100 #define FN_Avg 5 101 #define FN_Fcnt 6 102 #define FN_Length 7 103 #define FN_Substr 8 104 105 /* 106 ** Forward references to structures 107 */ 108 typedef struct Column Column; 109 typedef struct Table Table; 110 typedef struct Index Index; 111 typedef struct Instruction Instruction; 112 typedef struct Expr Expr; 113 typedef struct ExprList ExprList; 114 typedef struct Parse Parse; 115 typedef struct Token Token; 116 typedef struct IdList IdList; 117 typedef struct WhereInfo WhereInfo; 118 typedef struct Select Select; 119 typedef struct AggExpr AggExpr; 120 121 /* 122 ** Each database is an instance of the following structure 123 */ 124 struct sqlite { 125 Dbbe *pBe; /* The backend driver */ 126 int flags; /* Miscellanous flags */ 127 int file_format; /* What file format version is this database? */ 128 int nTable; /* Number of tables in the database */ 129 void *pBusyArg; /* 1st Argument to the busy callback */ 130 int (*xBusyCallback)(void *,const char*,int); /* The busy callback */ 131 Table *apTblHash[N_HASH]; /* All tables of the database */ 132 Index *apIdxHash[N_HASH]; /* All indices of the database */ 133 }; 134 135 /* 136 ** Possible values for the sqlite.flags. 137 */ 138 #define SQLITE_VdbeTrace 0x00000001 139 #define SQLITE_Initialized 0x00000002 140 141 /* 142 ** Current file format version 143 */ 144 #define SQLITE_FileFormat 2 145 146 /* 147 ** information about each column of an SQL table is held in an instance 148 ** of this structure. 149 */ 150 struct Column { 151 char *zName; /* Name of this column */ 152 char *zDflt; /* Default value of this column */ 153 int notNull; /* True if there is a NOT NULL constraint */ 154 }; 155 156 /* 157 ** Each SQL table is represented in memory by 158 ** an instance of the following structure. 159 */ 160 struct Table { 161 char *zName; /* Name of the table */ 162 Table *pHash; /* Next table with same hash on zName */ 163 int nCol; /* Number of columns in this table */ 164 Column *aCol; /* Information about each column */ 165 int readOnly; /* True if this table should not be written by the user */ 166 Index *pIndex; /* List of SQL indexes on this table. */ 167 }; 168 169 /* 170 ** Each SQL index is represented in memory by and 171 ** instance of the following structure. 172 ** 173 ** The columns of the table that are to be indexed are described 174 ** by the aiColumn[] field of this structure. For example, suppose 175 ** we have the following table and index: 176 ** 177 ** CREATE TABLE Ex1(c1 int, c2 int, c3 text); 178 ** CREATE INDEX Ex2 ON Ex1(c3,c1); 179 ** 180 ** In the Table structure describing Ex1, nCol==3 because there are 181 ** three columns in the table. In the Index structure describing 182 ** Ex2, nColumn==2 since 2 of the 3 columns of Ex1 are indexed. 183 ** The value of aiColumn is {2, 0}. aiColumn[0]==2 because the 184 ** first column to be indexed (c3) has an index of 2 in Ex1.aCol[]. 185 ** The second column to be indexed (c1) has an index of 0 in 186 ** Ex1.aCol[], hence Ex2.aiColumn[1]==0. 187 */ 188 struct Index { 189 char *zName; /* Name of this index */ 190 Index *pHash; /* Next index with the same hash on zName */ 191 int nColumn; /* Number of columns in the table used by this index */ 192 int *aiColumn; /* Which columns are used by this index. 1st is 0 */ 193 Table *pTable; /* The SQL table being indexed */ 194 int isUnique; /* True if keys must all be unique */ 195 Index *pNext; /* The next index associated with the same table */ 196 }; 197 198 /* 199 ** Each token coming out of the lexer is an instance of 200 ** this structure. 201 */ 202 struct Token { 203 char *z; /* Text of the token */ 204 int n; /* Number of characters in this token */ 205 }; 206 207 /* 208 ** Each node of an expression in the parse tree is an instance 209 ** of this structure 210 */ 211 struct Expr { 212 int op; /* Operation performed by this node */ 213 Expr *pLeft, *pRight; /* Left and right subnodes */ 214 ExprList *pList; /* A list of expressions used as a function argument */ 215 Token token; /* An operand token */ 216 Token span; /* Complete text of the expression */ 217 int iTable, iColumn; /* When op==TK_COLUMN, then this expr node means the 218 ** iColumn-th field of the iTable-th table. When 219 ** op==TK_FUNCTION, iColumn holds the function id */ 220 int iAgg; /* When op==TK_COLUMN and pParse->useAgg==TRUE, pull 221 ** result from the iAgg-th element of the aggregator */ 222 Select *pSelect; /* When the expression is a sub-select */ 223 }; 224 225 /* 226 ** A list of expressions. Each expression may optionally have a 227 ** name. An expr/name combination can be used in several ways, such 228 ** as the list of "expr AS ID" fields following a "SELECT" or in the 229 ** list of "ID = expr" items in an UPDATE. A list of expressions can 230 ** also be used as the argument to a function, in which case the azName 231 ** field is not used. 232 */ 233 struct ExprList { 234 int nExpr; /* Number of expressions on the list */ 235 struct { 236 Expr *pExpr; /* The list of expressions */ 237 char *zName; /* Token associated with this expression */ 238 char sortOrder; /* 1 for DESC or 0 for ASC */ 239 char isAgg; /* True if this is an aggregate like count(*) */ 240 char done; /* A flag to indicate when processing is finished */ 241 } *a; /* One entry for each expression */ 242 }; 243 244 /* 245 ** A list of identifiers. 246 */ 247 struct IdList { 248 int nId; /* Number of identifiers on the list */ 249 struct { 250 char *zName; /* Text of the identifier. */ 251 char *zAlias; /* The "B" part of a "A AS B" phrase. zName is the "A" */ 252 Table *pTab; /* An SQL table corresponding to zName */ 253 int idx; /* Index in some Table.aCol[] of a column named zName */ 254 } *a; /* One entry for each identifier on the list */ 255 }; 256 257 /* 258 ** The WHERE clause processing routine has two halves. The 259 ** first part does the start of the WHERE loop and the second 260 ** half does the tail of the WHERE loop. An instance of 261 ** this structure is returned by the first half and passed 262 ** into the second half to give some continuity. 263 */ 264 struct WhereInfo { 265 Parse *pParse; 266 IdList *pTabList; /* List of tables in the join */ 267 int iContinue; /* Jump here to continue with next record */ 268 int iBreak; /* Jump here to break out of the loop */ 269 int base; /* Index of first Open opcode */ 270 Index *aIdx[32]; /* Indices used for each table */ 271 }; 272 273 /* 274 ** An instance of the following structure contains all information 275 ** needed to generate code for a single SELECT statement. 276 */ 277 struct Select { 278 int isDistinct; /* True if the DISTINCT keyword is present */ 279 ExprList *pEList; /* The fields of the result */ 280 IdList *pSrc; /* The FROM clause */ 281 Expr *pWhere; /* The WHERE clause */ 282 ExprList *pGroupBy; /* The GROUP BY clause */ 283 Expr *pHaving; /* The HAVING clause */ 284 ExprList *pOrderBy; /* The ORDER BY clause */ 285 int op; /* One of: TK_UNION TK_ALL TK_INTERSECT TK_EXCEPT */ 286 Select *pPrior; /* Prior select in a compound select statement */ 287 }; 288 289 /* 290 ** The results of a select can be distributed in several ways. 291 */ 292 #define SRT_Callback 1 /* Invoke a callback with each row of result */ 293 #define SRT_Mem 2 /* Store result in a memory cell */ 294 #define SRT_Set 3 /* Store result as unique keys in a table */ 295 #define SRT_Union 5 /* Store result as keys in a table */ 296 #define SRT_Except 6 /* Remove result from a UNION table */ 297 #define SRT_Table 7 /* Store result as data with a unique key */ 298 299 /* 300 ** When a SELECT uses aggregate functions (like "count(*)" or "avg(f1)") 301 ** we have to do some additional analysis of expressions. An instance 302 ** of the following structure holds information about a single subexpression 303 ** somewhere in the SELECT statement. An array of these structures holds 304 ** all the information we need to generate code for aggregate 305 ** expressions. 306 ** 307 ** Note that when analyzing a SELECT containing aggregates, both 308 ** non-aggregate field variables and aggregate functions are stored 309 ** in the AggExpr array of the Parser structure. 310 ** 311 ** The pExpr field points to an expression that is part of either the 312 ** field list, the GROUP BY clause, the HAVING clause or the ORDER BY 313 ** clause. The expression will be freed when those clauses are cleaned 314 ** up. Do not try to delete the expression attached to AggExpr.pExpr. 315 ** 316 ** If AggExpr.pExpr==0, that means the expression is "count(*)". 317 */ 318 struct AggExpr { 319 int isAgg; /* if TRUE contains an aggregate function */ 320 Expr *pExpr; /* The expression */ 321 }; 322 323 /* 324 ** An SQL parser context 325 */ 326 struct Parse { 327 sqlite *db; /* The main database structure */ 328 sqlite_callback xCallback; /* The callback function */ 329 void *pArg; /* First argument to the callback function */ 330 char *zErrMsg; /* An error message */ 331 Token sErrToken; /* The token at which the error occurred */ 332 Token sFirstToken; /* The first token parsed */ 333 Token sLastToken; /* The last token parsed */ 334 Table *pNewTable; /* A table being constructed by CREATE TABLE */ 335 Vdbe *pVdbe; /* An engine for executing database bytecode */ 336 int colNamesSet; /* TRUE after OP_ColumnCount has been issued to pVdbe */ 337 int explain; /* True if the EXPLAIN flag is found on the query */ 338 int initFlag; /* True if reparsing CREATE TABLEs */ 339 int nErr; /* Number of errors seen */ 340 int nTab; /* Number of previously allocated cursors */ 341 int nMem; /* Number of memory cells used so far */ 342 int nSet; /* Number of sets used so far */ 343 int nAgg; /* Number of aggregate expressions */ 344 AggExpr *aAgg; /* An array of aggregate expressions */ 345 int iAggCount; /* Index of the count(*) aggregate in aAgg[] */ 346 int useAgg; /* If true, extract field values from the aggregator 347 ** while generating expressions. Normally false */ 348 }; 349 350 /* 351 ** Internal function prototypes 352 */ 353 int sqliteStrICmp(const char *, const char *); 354 int sqliteStrNICmp(const char *, const char *, int); 355 int sqliteHashNoCase(const char *, int); 356 int sqliteCompare(const char *, const char *); 357 int sqliteSortCompare(const char *, const char *); 358 #ifdef MEMORY_DEBUG 359 void *sqliteMalloc_(int,char*,int); 360 void sqliteFree_(void*,char*,int); 361 void *sqliteRealloc_(void*,int,char*,int); 362 char *sqliteStrDup_(const char*,char*,int); 363 char *sqliteStrNDup_(const char*, int,char*,int); 364 #else 365 void *sqliteMalloc(int); 366 void sqliteFree(void*); 367 void *sqliteRealloc(void*,int); 368 char *sqliteStrDup(const char*); 369 char *sqliteStrNDup(const char*, int); 370 #endif 371 int sqliteGetToken(const char*, int *); 372 void sqliteSetString(char **, const char *, ...); 373 void sqliteSetNString(char **, ...); 374 void sqliteDequote(char*); 375 int sqliteRunParser(Parse*, char*, char **); 376 void sqliteExec(Parse*); 377 Expr *sqliteExpr(int, Expr*, Expr*, Token*); 378 void sqliteExprSpan(Expr*,Token*,Token*); 379 Expr *sqliteExprFunction(ExprList*, Token*); 380 void sqliteExprDelete(Expr*); 381 ExprList *sqliteExprListAppend(ExprList*,Expr*,Token*); 382 void sqliteExprListDelete(ExprList*); 383 void sqliteStartTable(Parse*,Token*,Token*); 384 void sqliteAddColumn(Parse*,Token*); 385 void sqliteAddDefaultValue(Parse*,Token*,int); 386 void sqliteEndTable(Parse*,Token*); 387 void sqliteDropTable(Parse*, Token*); 388 void sqliteDeleteTable(sqlite*, Table*); 389 void sqliteInsert(Parse*, Token*, ExprList*, Select*, IdList*); 390 IdList *sqliteIdListAppend(IdList*, Token*); 391 void sqliteIdListAddAlias(IdList*, Token*); 392 void sqliteIdListDelete(IdList*); 393 void sqliteCreateIndex(Parse*, Token*, Token*, IdList*, Token*, Token*); 394 void sqliteDropIndex(Parse*, Token*); 395 int sqliteSelect(Parse*, Select*, int, int); 396 Select *sqliteSelectNew(ExprList*,IdList*,Expr*,ExprList*,Expr*,ExprList*,int); 397 void sqliteSelectDelete(Select*); 398 void sqliteDeleteFrom(Parse*, Token*, Expr*); 399 void sqliteUpdate(Parse*, Token*, ExprList*, Expr*); 400 WhereInfo *sqliteWhereBegin(Parse*, IdList*, Expr*, int); 401 void sqliteWhereEnd(WhereInfo*); 402 void sqliteExprCode(Parse*, Expr*); 403 void sqliteExprIfTrue(Parse*, Expr*, int); 404 void sqliteExprIfFalse(Parse*, Expr*, int); 405 Table *sqliteFindTable(sqlite*,char*); 406 void sqliteCopy(Parse*, Token*, Token*, Token*); 407 void sqliteVacuum(Parse*, Token*); 408 int sqliteGlobCompare(const char*,const char*); 409 int sqliteLikeCompare(const unsigned char*,const unsigned char*); 410 char *sqliteTableNameFromToken(Token*); 411 int sqliteExprCheck(Parse*, Expr*, int, int*); 412 int sqliteExprCompare(Expr*, Expr*); 413 int sqliteFuncId(Token*); 414 int sqliteExprResolveIds(Parse*, IdList*, Expr*); 415 void sqliteExprResolveInSelect(Parse*, Expr*); 416 int sqliteExprAnalyzeAggregates(Parse*, Expr*); 417 void sqliteParseInfoReset(Parse*); 418 Vdbe *sqliteGetVdbe(Parse*); 419