sqlite3/expr.c

   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 ** This file contains routines used for analyzing expressions and
  13 ** for generating VDBE code that evaluates expressions in SQLite.
  14 **
  15 ** $Id$
  16 */
  17 #include "sqliteInt.h"
  18 #include <ctype.h>
  19
  20 /*
  21 ** Return the 'affinity' of the expression pExpr if any.
  22 **
  23 ** If pExpr is a column, a reference to a column via an 'AS' alias,
  24 ** or a sub-select with a column as the return value, then the
  25 ** affinity of that column is returned. Otherwise, 0x00 is returned,
  26 ** indicating no affinity for the expression.
  27 **
  28 ** i.e. the WHERE clause expresssions in the following statements all
  29 ** have an affinity:
  30 **
  31 ** CREATE TABLE t1(a);
  32 ** SELECT * FROM t1 WHERE a;
  33 ** SELECT a AS b FROM t1 WHERE b;
  34 ** SELECT * FROM t1 WHERE (select a from t1);
  35 */
  36 char sqlite3ExprAffinity(Expr *pExpr){
  37   if( pExpr->op==TK_AS ){
  38     return sqlite3ExprAffinity(pExpr->pLeft);
  39   }
  40   if( pExpr->op==TK_SELECT ){
  41     return sqlite3ExprAffinity(pExpr->pSelect->pEList->a[0].pExpr);
  42   }
  43   return pExpr->affinity;
  44 }
  45
  46 /*
  47 ** Return the default collation sequence for the expression pExpr. If
  48 ** there is no default collation type, return 0.
  49 */
  50 CollSeq *sqlite3ExprCollSeq(Parse *pParse, Expr *pExpr){
  51   CollSeq *pColl = 0;
  52   if( pExpr ){
  53     pColl = pExpr->pColl;
  54     if( pExpr->op==TK_AS && !pColl ){
  55       return sqlite3ExprCollSeq(pParse, pExpr->pLeft);
  56     }
  57   }
  58   if( sqlite3CheckCollSeq(pParse, pColl) ){
  59     pColl = 0;
  60   }
  61   return pColl;
  62 }
  63
  64 /*
  65 ** pExpr is an operand of a comparison operator.  aff2 is the
  66 ** type affinity of the other operand.  This routine returns the
  67 ** type affinity that should be used for the comparison operator.
  68 */
  69 char sqlite3CompareAffinity(Expr *pExpr, char aff2){
  70   char aff1 = sqlite3ExprAffinity(pExpr);
  71   if( aff1 && aff2 ){
  72     /* Both sides of the comparison are columns. If one has numeric or
  73     ** integer affinity, use that. Otherwise use no affinity.
  74     */
  75     if( aff1==SQLITE_AFF_INTEGER || aff2==SQLITE_AFF_INTEGER ){
  76       return SQLITE_AFF_INTEGER;
  77     }else if( aff1==SQLITE_AFF_NUMERIC || aff2==SQLITE_AFF_NUMERIC ){
  78       return SQLITE_AFF_NUMERIC;
  79     }else{
  80       return SQLITE_AFF_NONE;
  81     }
  82   }else if( !aff1 && !aff2 ){
  83     /* Neither side of the comparison is a column.  Compare the
  84     ** results directly.
  85     */
  86     /* return SQLITE_AFF_NUMERIC;  // Ticket #805 */
  87     return SQLITE_AFF_NONE;
  88   }else{
  89     /* One side is a column, the other is not. Use the columns affinity. */
  90     return (aff1 + aff2);
  91   }
  92 }
  93
  94 /*
  95 ** pExpr is a comparison operator.  Return the type affinity that should
  96 ** be applied to both operands prior to doing the comparison.
  97 */
  98 static char comparisonAffinity(Expr *pExpr){
  99   char aff;
 100   assert( pExpr->op==TK_EQ || pExpr->op==TK_IN || pExpr->op==TK_LT ||
 101           pExpr->op==TK_GT || pExpr->op==TK_GE || pExpr->op==TK_LE ||
 102           pExpr->op==TK_NE );
 103   assert( pExpr->pLeft );
 104   aff = sqlite3ExprAffinity(pExpr->pLeft);
 105   if( pExpr->pRight ){
 106     aff = sqlite3CompareAffinity(pExpr->pRight, aff);
 107   }
 108   else if( pExpr->pSelect ){
 109     aff = sqlite3CompareAffinity(pExpr->pSelect->pEList->a[0].pExpr, aff);
 110   }
 111   else if( !aff ){
 112     aff = SQLITE_AFF_NUMERIC;
 113   }
 114   return aff;
 115 }
 116
 117 /*
 118 ** pExpr is a comparison expression, eg. '=', '<', IN(...) etc.
 119 ** idx_affinity is the affinity of an indexed column. Return true
 120 ** if the index with affinity idx_affinity may be used to implement
 121 ** the comparison in pExpr.
 122 */
 123 int sqlite3IndexAffinityOk(Expr *pExpr, char idx_affinity){
 124   char aff = comparisonAffinity(pExpr);
 125   return
 126     (aff==SQLITE_AFF_NONE) ||
 127     (aff==SQLITE_AFF_NUMERIC && idx_affinity==SQLITE_AFF_INTEGER) ||
 128     (aff==SQLITE_AFF_INTEGER && idx_affinity==SQLITE_AFF_NUMERIC) ||
 129     (aff==idx_affinity);
 130 }
 131
 132 /*
 133 ** Return the P1 value that should be used for a binary comparison
 134 ** opcode (OP_Eq, OP_Ge etc.) used to compare pExpr1 and pExpr2.
 135 ** If jumpIfNull is true, then set the low byte of the returned
 136 ** P1 value to tell the opcode to jump if either expression
 137 ** evaluates to NULL.
 138 */
 139 static int binaryCompareP1(Expr *pExpr1, Expr *pExpr2, int jumpIfNull){
 140   char aff = sqlite3ExprAffinity(pExpr2);
 141   return ((int)sqlite3CompareAffinity(pExpr1, aff))+(jumpIfNull?0x100:0);
 142 }
 143
 144 /*
 145 ** Return a pointer to the collation sequence that should be used by
 146 ** a binary comparison operator comparing pLeft and pRight.
 147 **
 148 ** If the left hand expression has a collating sequence type, then it is
 149 ** used. Otherwise the collation sequence for the right hand expression
 150 ** is used, or the default (BINARY) if neither expression has a collating
 151 ** type.
 152 */
 153 static CollSeq* binaryCompareCollSeq(Parse *pParse, Expr *pLeft, Expr *pRight){
 154   CollSeq *pColl = sqlite3ExprCollSeq(pParse, pLeft);
 155   if( !pColl ){
 156     pColl = sqlite3ExprCollSeq(pParse, pRight);
 157   }
 158   return pColl;
 159 }
 160
 161 /*
 162 ** Generate code for a comparison operator.
 163 */
 164 static int codeCompare(
 165   Parse *pParse,    /* The parsing (and code generating) context */
 166   Expr *pLeft,      /* The left operand */
 167   Expr *pRight,     /* The right operand */
 168   int opcode,       /* The comparison opcode */
 169   int dest,         /* Jump here if true.  */
 170   int jumpIfNull    /* If true, jump if either operand is NULL */
 171 ){
 172   int p1 = binaryCompareP1(pLeft, pRight, jumpIfNull);
 173   CollSeq *p3 = binaryCompareCollSeq(pParse, pLeft, pRight);
 174   return sqlite3VdbeOp3(pParse->pVdbe, opcode, p1, dest, (void*)p3, P3_COLLSEQ);
 175 }
 176
 177 /*
 178 ** Construct a new expression node and return a pointer to it.  Memory
 179 ** for this node is obtained from sqliteMalloc().  The calling function
 180 ** is responsible for making sure the node eventually gets freed.
 181 */
 182 Expr *sqlite3Expr(int op, Expr *pLeft, Expr *pRight, const Token *pToken){
 183   Expr *pNew;
 184   pNew = sqliteMalloc( sizeof(Expr) );
 185   if( pNew==0 ){
 186     /* When malloc fails, delete pLeft and pRight. Expressions passed to
 187     ** this function must always be allocated with sqlite3Expr() for this
 188     ** reason.
 189     */
 190     sqlite3ExprDelete(pLeft);
 191     sqlite3ExprDelete(pRight);
 192     return 0;
 193   }
 194   pNew->op = op;
 195   pNew->pLeft = pLeft;
 196   pNew->pRight = pRight;
 197   pNew->iAgg = -1;
 198   if( pToken ){
 199     assert( pToken->dyn==0 );
 200     pNew->span = pNew->token = *pToken;
 201   }else if( pLeft && pRight ){
 202     sqlite3ExprSpan(pNew, &pLeft->span, &pRight->span);
 203   }
 204   return pNew;
 205 }
 206
 207 /*
 208 ** When doing a nested parse, you can include terms in an expression
 209 ** that look like this:   #0 #1 #2 ...  These terms refer to elements
 210 ** on the stack.  "#0" (or just "#") means the top of the stack.
 211 ** "#1" means the next down on the stack.  And so forth.  #-1 means
 212 ** memory location 0.  #-2 means memory location 1.  And so forth.
 213 **
 214 ** This routine is called by the parser to deal with on of those terms.
 215 ** It immediately generates code to store the value in a memory location.
 216 ** The returns an expression that will code to extract the value from
 217 ** that memory location as needed.
 218 */
 219 Expr *sqlite3RegisterExpr(Parse *pParse, Token *pToken){
 220   Vdbe *v = pParse->pVdbe;
 221   Expr *p;
 222   int depth;
 223   if( v==0 ) return 0;
 224   if( pParse->nested==0 ){
 225     sqlite3ErrorMsg(pParse, "near \"%T\": syntax error", pToken);
 226     return 0;
 227   }
 228   p = sqlite3Expr(TK_REGISTER, 0, 0, pToken);
 229   if( p==0 ){
 230     return 0;  /* Malloc failed */
 231   }
 232   depth = atoi(&pToken->z[1]);
 233   if( depth>=0 ){
 234     p->iTable = pParse->nMem++;
 235     sqlite3VdbeAddOp(v, OP_Dup, depth, 0);
 236     sqlite3VdbeAddOp(v, OP_MemStore, p->iTable, 1);
 237   }else{
 238     p->iTable = -1-depth;
 239   }
 240   return p;
 241 }
 242
 243 /*
 244 ** Join two expressions using an AND operator.  If either expression is
 245 ** NULL, then just return the other expression.
 246 */
 247 Expr *sqlite3ExprAnd(Expr *pLeft, Expr *pRight){
 248   if( pLeft==0 ){
 249     return pRight;
 250   }else if( pRight==0 ){
 251     return pLeft;
 252   }else{
 253     return sqlite3Expr(TK_AND, pLeft, pRight, 0);
 254   }
 255 }
 256
 257 /*
 258 ** Set the Expr.span field of the given expression to span all
 259 ** text between the two given tokens.
 260 */
 261 void sqlite3ExprSpan(Expr *pExpr, Token *pLeft, Token *pRight){
 262   assert( pRight!=0 );
 263   assert( pLeft!=0 );
 264   if( !sqlite3_malloc_failed && pRight->z && pLeft->z ){
 265     assert( pLeft->dyn==0 || pLeft->z[pLeft->n]==0 );
 266     if( pLeft->dyn==0 && pRight->dyn==0 ){
 267       pExpr->span.z = pLeft->z;
 268       pExpr->span.n = pRight->n + (pRight->z - pLeft->z);
 269     }else{
 270       pExpr->span.z = 0;
 271     }
 272   }
 273 }
 274
 275 /*
 276 ** Construct a new expression node for a function with multiple
 277 ** arguments.
 278 */
 279 Expr *sqlite3ExprFunction(ExprList *pList, Token *pToken){
 280   Expr *pNew;
 281   pNew = sqliteMalloc( sizeof(Expr) );
 282   if( pNew==0 ){
 283     sqlite3ExprListDelete(pList); /* Avoid leaking memory when malloc fails */
 284     return 0;
 285   }
 286   pNew->op = TK_FUNCTION;
 287   pNew->pList = pList;
 288   if( pToken ){
 289     assert( pToken->dyn==0 );
 290     pNew->token = *pToken;
 291   }else{
 292     pNew->token.z = 0;
 293   }
 294   pNew->span = pNew->token;
 295   return pNew;
 296 }
 297
 298 /*
 299 ** Assign a variable number to an expression that encodes a wildcard
 300 ** in the original SQL statement.
 301 **
 302 ** Wildcards consisting of a single "?" are assigned the next sequential
 303 ** variable number.
 304 **
 305 ** Wildcards of the form "?nnn" are assigned the number "nnn".  We make
 306 ** sure "nnn" is not too be to avoid a denial of service attack when
 307 ** the SQL statement comes from an external source.
 308 **
 309 ** Wildcards of the form ":aaa" or "$aaa" are assigned the same number
 310 ** as the previous instance of the same wildcard.  Or if this is the first
 311 ** instance of the wildcard, the next sequenial variable number is
 312 ** assigned.
 313 */
 314 void sqlite3ExprAssignVarNumber(Parse *pParse, Expr *pExpr){
 315   Token *pToken;
 316   if( pExpr==0 ) return;
 317   pToken = &pExpr->token;
 318   assert( pToken->n>=1 );
 319   assert( pToken->z!=0 );
 320   assert( pToken->z[0]!=0 );
 321   if( pToken->n==1 ){
 322     /* Wildcard of the form "?".  Assign the next variable number */
 323     pExpr->iTable = ++pParse->nVar;
 324   }else if( pToken->z[0]=='?' ){
 325     /* Wildcard of the form "?nnn".  Convert "nnn" to an integer and
 326     ** use it as the variable number */
 327     int i;
 328     pExpr->iTable = i = atoi(&pToken->z[1]);
 329     if( i<1 || i>SQLITE_MAX_VARIABLE_NUMBER ){
 330       sqlite3ErrorMsg(pParse, "variable number must be between ?1 and ?%d",
 331           SQLITE_MAX_VARIABLE_NUMBER);
 332     }
 333     if( i>pParse->nVar ){
 334       pParse->nVar = i;
 335     }
 336   }else{
 337     /* Wildcards of the form ":aaa" or "$aaa".  Reuse the same variable
 338     ** number as the prior appearance of the same name, or if the name
 339     ** has never appeared before, reuse the same variable number
 340     */
 341     int i, n;
 342     n = pToken->n;
 343     for(i=0; i<pParse->nVarExpr; i++){
 344       Expr *pE;
 345       if( (pE = pParse->apVarExpr[i])!=0
 346           && pE->token.n==n
 347           && memcmp(pE->token.z, pToken->z, n)==0 ){
 348         pExpr->iTable = pE->iTable;
 349         break;
 350       }
 351     }
 352     if( i>=pParse->nVarExpr ){
 353       pExpr->iTable = ++pParse->nVar;
 354       if( pParse->nVarExpr>=pParse->nVarExprAlloc-1 ){
 355         pParse->nVarExprAlloc += pParse->nVarExprAlloc + 10;
 356         pParse->apVarExpr = sqliteRealloc(pParse->apVarExpr,
 357                        pParse->nVarExprAlloc*sizeof(pParse->apVarExpr[0]) );
 358       }
 359       if( !sqlite3_malloc_failed ){
 360         assert( pParse->apVarExpr!=0 );
 361         pParse->apVarExpr[pParse->nVarExpr++] = pExpr;
 362       }
 363     }
 364   }
 365 }
 366
 367 /*
 368 ** Recursively delete an expression tree.
 369 */
 370 void sqlite3ExprDelete(Expr *p){
 371   if( p==0 ) return;
 372   if( p->span.dyn ) sqliteFree((char*)p->span.z);
 373   if( p->token.dyn ) sqliteFree((char*)p->token.z);
 374   sqlite3ExprDelete(p->pLeft);
 375   sqlite3ExprDelete(p->pRight);
 376   sqlite3ExprListDelete(p->pList);
 377   sqlite3SelectDelete(p->pSelect);
 378   sqliteFree(p);
 379 }
 380
 381
 382 /*
 383 ** The following group of routines make deep copies of expressions,
 384 ** expression lists, ID lists, and select statements.  The copies can
 385 ** be deleted (by being passed to their respective ...Delete() routines)
 386 ** without effecting the originals.
 387 **
 388 ** The expression list, ID, and source lists return by sqlite3ExprListDup(),
 389 ** sqlite3IdListDup(), and sqlite3SrcListDup() can not be further expanded
 390 ** by subsequent calls to sqlite*ListAppend() routines.
 391 **
 392 ** Any tables that the SrcList might point to are not duplicated.
 393 */
 394 Expr *sqlite3ExprDup(Expr *p){
 395   Expr *pNew;
 396   if( p==0 ) return 0;
 397   pNew = sqliteMallocRaw( sizeof(*p) );
 398   if( pNew==0 ) return 0;
 399   memcpy(pNew, p, sizeof(*pNew));
 400   if( p->token.z!=0 ){
 401     pNew->token.z = sqliteStrNDup(p->token.z, p->token.n);
 402     pNew->token.dyn = 1;
 403   }else{
 404     assert( pNew->token.z==0 );
 405   }
 406   pNew->span.z = 0;
 407   pNew->pLeft = sqlite3ExprDup(p->pLeft);
 408   pNew->pRight = sqlite3ExprDup(p->pRight);
 409   pNew->pList = sqlite3ExprListDup(p->pList);
 410   pNew->pSelect = sqlite3SelectDup(p->pSelect);
 411   pNew->pTab = p->pTab;
 412   return pNew;
 413 }
 414 void sqlite3TokenCopy(Token *pTo, Token *pFrom){
 415   if( pTo->dyn ) sqliteFree((char*)pTo->z);
 416   if( pFrom->z ){
 417     pTo->n = pFrom->n;
 418     pTo->z = sqliteStrNDup(pFrom->z, pFrom->n);
 419     pTo->dyn = 1;
 420   }else{
 421     pTo->z = 0;
 422   }
 423 }
 424 ExprList *sqlite3ExprListDup(ExprList *p){
 425   ExprList *pNew;
 426   struct ExprList_item *pItem, *pOldItem;
 427   int i;
 428   if( p==0 ) return 0;
 429   pNew = sqliteMalloc( sizeof(*pNew) );
 430   if( pNew==0 ) return 0;
 431   pNew->nExpr = pNew->nAlloc = p->nExpr;
 432   pNew->a = pItem = sqliteMalloc( p->nExpr*sizeof(p->a[0]) );
 433   if( pItem==0 ){
 434     sqliteFree(pNew);
 435     return 0;
 436   }
 437   pOldItem = p->a;
 438   for(i=0; i<p->nExpr; i++, pItem++, pOldItem++){
 439     Expr *pNewExpr, *pOldExpr;
 440     pItem->pExpr = pNewExpr = sqlite3ExprDup(pOldExpr = pOldItem->pExpr);
 441     if( pOldExpr->span.z!=0 && pNewExpr ){
 442       /* Always make a copy of the span for top-level expressions in the
 443       ** expression list.  The logic in SELECT processing that determines
 444       ** the names of columns in the result set needs this information */
 445       sqlite3TokenCopy(&pNewExpr->span, &pOldExpr->span);
 446     }
 447     assert( pNewExpr==0 || pNewExpr->span.z!=0
 448             || pOldExpr->span.z==0 || sqlite3_malloc_failed );
 449     pItem->zName = sqliteStrDup(pOldItem->zName);
 450     pItem->sortOrder = pOldItem->sortOrder;
 451     pItem->isAgg = pOldItem->isAgg;
 452     pItem->done = 0;
 453   }
 454   return pNew;
 455 }
 456
 457 /*
 458 ** If cursors, triggers, views and subqueries are all omitted from
 459 ** the build, then none of the following routines, except for
 460 ** sqlite3SelectDup(), can be called. sqlite3SelectDup() is sometimes
 461 ** called with a NULL argument.
 462 */
 463 #if !defined(SQLITE_OMIT_VIEW) || !defined(SQLITE_OMIT_TRIGGER) \
 464  || !defined(SQLITE_OMIT_SUBQUERY)
 465 SrcList *sqlite3SrcListDup(SrcList *p){
 466   SrcList *pNew;
 467   int i;
 468   int nByte;
 469   if( p==0 ) return 0;
 470   nByte = sizeof(*p) + (p->nSrc>0 ? sizeof(p->a[0]) * (p->nSrc-1) : 0);
 471   pNew = sqliteMallocRaw( nByte );
 472   if( pNew==0 ) return 0;
 473   pNew->nSrc = pNew->nAlloc = p->nSrc;
 474   for(i=0; i<p->nSrc; i++){
 475     struct SrcList_item *pNewItem = &pNew->a[i];
 476     struct SrcList_item *pOldItem = &p->a[i];
 477     Table *pTab;
 478     pNewItem->zDatabase = sqliteStrDup(pOldItem->zDatabase);
 479     pNewItem->zName = sqliteStrDup(pOldItem->zName);
 480     pNewItem->zAlias = sqliteStrDup(pOldItem->zAlias);
 481     pNewItem->jointype = pOldItem->jointype;
 482     pNewItem->iCursor = pOldItem->iCursor;
 483     pTab = pNewItem->pTab = pOldItem->pTab;
 484     if( pTab ){
 485       pTab->nRef++;
 486     }
 487     pNewItem->pSelect = sqlite3SelectDup(pOldItem->pSelect);
 488     pNewItem->pOn = sqlite3ExprDup(pOldItem->pOn);
 489     pNewItem->pUsing = sqlite3IdListDup(pOldItem->pUsing);
 490     pNewItem->colUsed = pOldItem->colUsed;
 491   }
 492   return pNew;
 493 }
 494 IdList *sqlite3IdListDup(IdList *p){
 495   IdList *pNew;
 496   int i;
 497   if( p==0 ) return 0;
 498   pNew = sqliteMallocRaw( sizeof(*pNew) );
 499   if( pNew==0 ) return 0;
 500   pNew->nId = pNew->nAlloc = p->nId;
 501   pNew->a = sqliteMallocRaw( p->nId*sizeof(p->a[0]) );
 502   if( pNew->a==0 ){
 503     sqliteFree(pNew);
 504     return 0;
 505   }
 506   for(i=0; i<p->nId; i++){
 507     struct IdList_item *pNewItem = &pNew->a[i];
 508     struct IdList_item *pOldItem = &p->a[i];
 509     pNewItem->zName = sqliteStrDup(pOldItem->zName);
 510     pNewItem->idx = pOldItem->idx;
 511   }
 512   return pNew;
 513 }
 514 Select *sqlite3SelectDup(Select *p){
 515   Select *pNew;
 516   if( p==0 ) return 0;
 517   pNew = sqliteMallocRaw( sizeof(*p) );
 518   if( pNew==0 ) return 0;
 519   pNew->isDistinct = p->isDistinct;
 520   pNew->pEList = sqlite3ExprListDup(p->pEList);
 521   pNew->pSrc = sqlite3SrcListDup(p->pSrc);
 522   pNew->pWhere = sqlite3ExprDup(p->pWhere);
 523   pNew->pGroupBy = sqlite3ExprListDup(p->pGroupBy);
 524   pNew->pHaving = sqlite3ExprDup(p->pHaving);
 525   pNew->pOrderBy = sqlite3ExprListDup(p->pOrderBy);
 526   pNew->op = p->op;
 527   pNew->pPrior = sqlite3SelectDup(p->pPrior);
 528   pNew->pLimit = sqlite3ExprDup(p->pLimit);
 529   pNew->pOffset = sqlite3ExprDup(p->pOffset);
 530   pNew->iLimit = -1;
 531   pNew->iOffset = -1;
 532   pNew->ppOpenTemp = 0;
 533   pNew->isResolved = p->isResolved;
 534   pNew->isAgg = p->isAgg;
 535   return pNew;
 536 }
 537 #else
 538 Select *sqlite3SelectDup(Select *p){
 539   assert( p==0 );
 540   return 0;
 541 }
 542 #endif
 543
 544
 545 /*
 546 ** Add a new element to the end of an expression list.  If pList is
 547 ** initially NULL, then create a new expression list.
 548 */
 549 ExprList *sqlite3ExprListAppend(ExprList *pList, Expr *pExpr, Token *pName){
 550   if( pList==0 ){
 551     pList = sqliteMalloc( sizeof(ExprList) );
 552     if( pList==0 ){
 553       goto no_mem;
 554     }
 555     assert( pList->nAlloc==0 );
 556   }
 557   if( pList->nAlloc<=pList->nExpr ){
 558     struct ExprList_item *a;
 559     int n = pList->nAlloc*2 + 4;
 560     a = sqliteRealloc(pList->a, n*sizeof(pList->a[0]));
 561     if( a==0 ){
 562       goto no_mem;
 563     }
 564     pList->a = a;
 565     pList->nAlloc = n;
 566   }
 567   assert( pList->a!=0 );
 568   if( pExpr || pName ){
 569     struct ExprList_item *pItem = &pList->a[pList->nExpr++];
 570     memset(pItem, 0, sizeof(*pItem));
 571     pItem->zName = sqlite3NameFromToken(pName);
 572     pItem->pExpr = pExpr;
 573   }
 574   return pList;
 575
 576 no_mem:
 577   /* Avoid leaking memory if malloc has failed. */
 578   sqlite3ExprDelete(pExpr);
 579   sqlite3ExprListDelete(pList);
 580   return 0;
 581 }
 582
 583 /*
 584 ** Delete an entire expression list.
 585 */
 586 void sqlite3ExprListDelete(ExprList *pList){
 587   int i;
 588   struct ExprList_item *pItem;
 589   if( pList==0 ) return;
 590   assert( pList->a!=0 || (pList->nExpr==0 && pList->nAlloc==0) );
 591   assert( pList->nExpr<=pList->nAlloc );
 592   for(pItem=pList->a, i=0; i<pList->nExpr; i++, pItem++){
 593     sqlite3ExprDelete(pItem->pExpr);
 594     sqliteFree(pItem->zName);
 595   }
 596   sqliteFree(pList->a);
 597   sqliteFree(pList);
 598 }
 599
 600 /*
 601 ** Walk an expression tree.  Call xFunc for each node visited.
 602 **
 603 ** The return value from xFunc determines whether the tree walk continues.
 604 ** 0 means continue walking the tree.  1 means do not walk children
 605 ** of the current node but continue with siblings.  2 means abandon
 606 ** the tree walk completely.
 607 **
 608 ** The return value from this routine is 1 to abandon the tree walk
 609 ** and 0 to continue.
 610 */
 611 static int walkExprList(ExprList *, int (*)(void *, Expr*), void *);
 612 static int walkExprTree(Expr *pExpr, int (*xFunc)(void*,Expr*), void *pArg){
 613   int rc;
 614   if( pExpr==0 ) return 0;
 615   rc = (*xFunc)(pArg, pExpr);
 616   if( rc==0 ){
 617     if( walkExprTree(pExpr->pLeft, xFunc, pArg) ) return 1;
 618     if( walkExprTree(pExpr->pRight, xFunc, pArg) ) return 1;
 619     if( walkExprList(pExpr->pList, xFunc, pArg) ) return 1;
 620   }
 621   return rc>1;
 622 }
 623
 624 /*
 625 ** Call walkExprTree() for every expression in list p.
 626 */
 627 static int walkExprList(ExprList *p, int (*xFunc)(void *, Expr*), void *pArg){
 628   int i;
 629   struct ExprList_item *pItem;
 630   if( !p ) return 0;
 631   for(i=p->nExpr, pItem=p->a; i>0; i--, pItem++){
 632     if( walkExprTree(pItem->pExpr, xFunc, pArg) ) return 1;
 633   }
 634   return 0;
 635 }
 636
 637 /*
 638 ** Call walkExprTree() for every expression in Select p, not including
 639 ** expressions that are part of sub-selects in any FROM clause or the LIMIT
 640 ** or OFFSET expressions..
 641 */
 642 static int walkSelectExpr(Select *p, int (*xFunc)(void *, Expr*), void *pArg){
 643   walkExprList(p->pEList, xFunc, pArg);
 644   walkExprTree(p->pWhere, xFunc, pArg);
 645   walkExprList(p->pGroupBy, xFunc, pArg);
 646   walkExprTree(p->pHaving, xFunc, pArg);
 647   walkExprList(p->pOrderBy, xFunc, pArg);
 648   return 0;
 649 }
 650
 651
 652 /*
 653 ** This routine is designed as an xFunc for walkExprTree().
 654 **
 655 ** pArg is really a pointer to an integer.  If we can tell by looking
 656 ** at pExpr that the expression that contains pExpr is not a constant
 657 ** expression, then set *pArg to 0 and return 2 to abandon the tree walk.
 658 ** If pExpr does does not disqualify the expression from being a constant
 659 ** then do nothing.
 660 **
 661 ** After walking the whole tree, if no nodes are found that disqualify
 662 ** the expression as constant, then we assume the whole expression
 663 ** is constant.  See sqlite3ExprIsConstant() for additional information.
 664 */
 665 static int exprNodeIsConstant(void *pArg, Expr *pExpr){
 666   switch( pExpr->op ){
 667     case TK_ID:
 668     case TK_COLUMN:
 669     case TK_DOT:
 670     case TK_AGG_FUNCTION:
 671     case TK_FUNCTION:
 672 #ifndef SQLITE_OMIT_SUBQUERY
 673     case TK_SELECT:
 674     case TK_EXISTS:
 675 #endif
 676       *((int*)pArg) = 0;
 677       return 2;
 678     default:
 679       return 0;
 680   }
 681 }
 682
 683 /*
 684 ** Walk an expression tree.  Return 1 if the expression is constant
 685 ** and 0 if it involves variables.
 686 **
 687 ** For the purposes of this function, a double-quoted string (ex: "abc")
 688 ** is considered a variable but a single-quoted string (ex: 'abc') is
 689 ** a constant.
 690 */
 691 int sqlite3ExprIsConstant(Expr *p){
 692   int isConst = 1;
 693   walkExprTree(p, exprNodeIsConstant, &isConst);
 694   return isConst;
 695 }
 696
 697 /*
 698 ** If the expression p codes a constant integer that is small enough
 699 ** to fit in a 32-bit integer, return 1 and put the value of the integer
 700 ** in *pValue.  If the expression is not an integer or if it is too big
 701 ** to fit in a signed 32-bit integer, return 0 and leave *pValue unchanged.
 702 */
 703 int sqlite3ExprIsInteger(Expr *p, int *pValue){
 704   switch( p->op ){
 705     case TK_INTEGER: {
 706       if( sqlite3GetInt32(p->token.z, pValue) ){
 707         return 1;
 708       }
 709       break;
 710     }
 711     case TK_UPLUS: {
 712       return sqlite3ExprIsInteger(p->pLeft, pValue);
 713     }
 714     case TK_UMINUS: {
 715       int v;
 716       if( sqlite3ExprIsInteger(p->pLeft, &v) ){
 717         *pValue = -v;
 718         return 1;
 719       }
 720       break;
 721     }
 722     default: break;
 723   }
 724   return 0;
 725 }
 726
 727 /*
 728 ** Return TRUE if the given string is a row-id column name.
 729 */
 730 int sqlite3IsRowid(const char *z){
 731   if( sqlite3StrICmp(z, "_ROWID_")==0 ) return 1;
 732   if( sqlite3StrICmp(z, "ROWID")==0 ) return 1;
 733   if( sqlite3StrICmp(z, "OID")==0 ) return 1;
 734   return 0;
 735 }
 736
 737 /*
 738 ** Given the name of a column of the form X.Y.Z or Y.Z or just Z, look up
 739 ** that name in the set of source tables in pSrcList and make the pExpr
 740 ** expression node refer back to that source column.  The following changes
 741 ** are made to pExpr:
 742 **
 743 **    pExpr->iDb           Set the index in db->aDb[] of the database holding
 744 **                         the table.
 745 **    pExpr->iTable        Set to the cursor number for the table obtained
 746 **                         from pSrcList.
 747 **    pExpr->iColumn       Set to the column number within the table.
 748 **    pExpr->op            Set to TK_COLUMN.
 749 **    pExpr->pLeft         Any expression this points to is deleted
 750 **    pExpr->pRight        Any expression this points to is deleted.
 751 **
 752 ** The pDbToken is the name of the database (the "X").  This value may be
 753 ** NULL meaning that name is of the form Y.Z or Z.  Any available database
 754 ** can be used.  The pTableToken is the name of the table (the "Y").  This
 755 ** value can be NULL if pDbToken is also NULL.  If pTableToken is NULL it
 756 ** means that the form of the name is Z and that columns from any table
 757 ** can be used.
 758 **
 759 ** If the name cannot be resolved unambiguously, leave an error message
 760 ** in pParse and return non-zero.  Return zero on success.
 761 */
 762 static int lookupName(
 763   Parse *pParse,      /* The parsing context */
 764   Token *pDbToken,     /* Name of the database containing table, or NULL */
 765   Token *pTableToken,  /* Name of table containing column, or NULL */
 766   Token *pColumnToken, /* Name of the column. */
 767   NameContext *pNC,    /* The name context used to resolve the name */
 768   Expr *pExpr          /* Make this EXPR node point to the selected column */
 769 ){
 770   char *zDb = 0;       /* Name of the database.  The "X" in X.Y.Z */
 771   char *zTab = 0;      /* Name of the table.  The "Y" in X.Y.Z or Y.Z */
 772   char *zCol = 0;      /* Name of the column.  The "Z" */
 773   int i, j;            /* Loop counters */
 774   int cnt = 0;         /* Number of matching column names */
 775   int cntTab = 0;      /* Number of matching table names */
 776   sqlite3 *db = pParse->db;  /* The database */
 777   struct SrcList_item *pItem;       /* Use for looping over pSrcList items */
 778   struct SrcList_item *pMatch = 0;  /* The matching pSrcList item */
 779   NameContext *pTopNC = pNC;        /* First namecontext in the list */
 780
 781   assert( pColumnToken && pColumnToken->z ); /* The Z in X.Y.Z cannot be NULL */
 782   zDb = sqlite3NameFromToken(pDbToken);
 783   zTab = sqlite3NameFromToken(pTableToken);
 784   zCol = sqlite3NameFromToken(pColumnToken);
 785   if( sqlite3_malloc_failed ){
 786     goto lookupname_end;
 787   }
 788
 789   pExpr->iTable = -1;
 790   while( pNC && cnt==0 ){
 791     SrcList *pSrcList = pNC->pSrcList;
 792     ExprList *pEList = pNC->pEList;
 793
 794     /* assert( zTab==0 || pEList==0 ); */
 795     if( pSrcList ){
 796       for(i=0, pItem=pSrcList->a; i<pSrcList->nSrc; i++, pItem++){
 797         Table *pTab = pItem->pTab;
 798         Column *pCol;
 799
 800         if( pTab==0 ) continue;
 801         assert( pTab->nCol>0 );
 802         if( zTab ){
 803           if( pItem->zAlias ){
 804             char *zTabName = pItem->zAlias;
 805             if( sqlite3StrICmp(zTabName, zTab)!=0 ) continue;
 806           }else{
 807             char *zTabName = pTab->zName;
 808             if( zTabName==0 || sqlite3StrICmp(zTabName, zTab)!=0 ) continue;
 809             if( zDb!=0 && sqlite3StrICmp(db->aDb[pTab->iDb].zName, zDb)!=0 ){
 810               continue;
 811             }
 812           }
 813         }
 814         if( 0==(cntTab++) ){
 815           pExpr->iTable = pItem->iCursor;
 816           pExpr->iDb = pTab->iDb;
 817           pMatch = pItem;
 818         }
 819         for(j=0, pCol=pTab->aCol; j<pTab->nCol; j++, pCol++){
 820           if( sqlite3StrICmp(pCol->zName, zCol)==0 ){
 821             IdList *pUsing;
 822             cnt++;
 823             pExpr->iTable = pItem->iCursor;
 824             pMatch = pItem;
 825             pExpr->iDb = pTab->iDb;
 826             /* Substitute the rowid (column -1) for the INTEGER PRIMARY KEY */
 827             pExpr->iColumn = j==pTab->iPKey ? -1 : j;
 828             pExpr->affinity = pTab->aCol[j].affinity;
 829             pExpr->pColl = pTab->aCol[j].pColl;
 830             if( pItem->jointype & JT_NATURAL ){
 831               /* If this match occurred in the left table of a natural join,
 832               ** then skip the right table to avoid a duplicate match */
 833               pItem++;
 834               i++;
 835             }
 836             if( (pUsing = pItem->pUsing)!=0 ){
 837               /* If this match occurs on a column that is in the USING clause
 838               ** of a join, skip the search of the right table of the join
 839               ** to avoid a duplicate match there. */
 840               int k;
 841               for(k=0; k<pUsing->nId; k++){
 842                 if( sqlite3StrICmp(pUsing->a[k].zName, zCol)==0 ){
 843                   pItem++;
 844                   i++;
 845                   break;
 846                 }
 847               }
 848             }
 849             break;
 850           }
 851         }
 852       }
 853     }
 854
 855 #ifndef SQLITE_OMIT_TRIGGER
 856     /* If we have not already resolved the name, then maybe
 857     ** it is a new.* or old.* trigger argument reference
 858     */
 859     if( zDb==0 && zTab!=0 && cnt==0 && pParse->trigStack!=0 ){
 860       TriggerStack *pTriggerStack = pParse->trigStack;
 861       Table *pTab = 0;
 862       if( pTriggerStack->newIdx != -1 && sqlite3StrICmp("new", zTab) == 0 ){
 863         pExpr->iTable = pTriggerStack->newIdx;
 864         assert( pTriggerStack->pTab );
 865         pTab = pTriggerStack->pTab;
 866       }else if( pTriggerStack->oldIdx != -1 && sqlite3StrICmp("old", zTab)==0 ){
 867         pExpr->iTable = pTriggerStack->oldIdx;
 868         assert( pTriggerStack->pTab );
 869         pTab = pTriggerStack->pTab;
 870       }
 871
 872       if( pTab ){
 873         int j;
 874         Column *pCol = pTab->aCol;
 875
 876         pExpr->iDb = pTab->iDb;
 877         cntTab++;
 878         for(j=0; j < pTab->nCol; j++, pCol++) {
 879           if( sqlite3StrICmp(pCol->zName, zCol)==0 ){
 880             cnt++;
 881             pExpr->iColumn = j==pTab->iPKey ? -1 : j;
 882             pExpr->affinity = pTab->aCol[j].affinity;
 883             pExpr->pColl = pTab->aCol[j].pColl;
 884             pExpr->pTab = pTab;
 885             break;
 886           }
 887         }
 888       }
 889     }
 890 #endif /* !defined(SQLITE_OMIT_TRIGGER) */
 891
 892     /*
 893     ** Perhaps the name is a reference to the ROWID
 894     */
 895     if( cnt==0 && cntTab==1 && sqlite3IsRowid(zCol) ){
 896       cnt = 1;
 897       pExpr->iColumn = -1;
 898       pExpr->affinity = SQLITE_AFF_INTEGER;
 899     }
 900
 901     /*
 902     ** If the input is of the form Z (not Y.Z or X.Y.Z) then the name Z
 903     ** might refer to an result-set alias.  This happens, for example, when
 904     ** we are resolving names in the WHERE clause of the following command:
 905     **
 906     **     SELECT a+b AS x FROM table WHERE x<10;
 907     **
 908     ** In cases like this, replace pExpr with a copy of the expression that
 909     ** forms the result set entry ("a+b" in the example) and return immediately.
 910     ** Note that the expression in the result set should have already been
 911     ** resolved by the time the WHERE clause is resolved.
 912     */
 913     if( cnt==0 && pEList!=0 && zTab==0 ){
 914       for(j=0; j<pEList->nExpr; j++){
 915         char *zAs = pEList->a[j].zName;
 916         if( zAs!=0 && sqlite3StrICmp(zAs, zCol)==0 ){
 917           assert( pExpr->pLeft==0 && pExpr->pRight==0 );
 918           pExpr->op = TK_AS;
 919           pExpr->iColumn = j;
 920           pExpr->pLeft = sqlite3ExprDup(pEList->a[j].pExpr);
 921           cnt = 1;
 922           assert( zTab==0 && zDb==0 );
 923           goto lookupname_end_2;
 924         }
 925       }
 926     }
 927
 928     /* Advance to the next name context.  The loop will exit when either
 929     ** we have a match (cnt>0) or when we run out of name contexts.
 930     */
 931     if( cnt==0 ){
 932       pNC = pNC->pNext;
 933     }
 934   }
 935
 936   /*
 937   ** If X and Y are NULL (in other words if only the column name Z is
 938   ** supplied) and the value of Z is enclosed in double-quotes, then
 939   ** Z is a string literal if it doesn't match any column names.  In that
 940   ** case, we need to return right away and not make any changes to
 941   ** pExpr.
 942   **
 943   ** Because no reference was made to outer contexts, the pNC->nRef
 944   ** fields are not changed in any context.
 945   */
 946   if( cnt==0 && zTab==0 && pColumnToken->z[0]=='"' ){
 947     sqliteFree(zCol);
 948     return 0;
 949   }
 950
 951   /*
 952   ** cnt==0 means there was not match.  cnt>1 means there were two or
 953   ** more matches.  Either way, we have an error.
 954   */
 955   if( cnt!=1 ){
 956     STRPTR z = NULL;
 957     char *zErr;
 958     zErr = cnt==0 ? "no such column: %s" : "ambiguous column name: %s";
 959     if( zDb ){
 960       sqlite3SetString(&z, zDb, ".", zTab, ".", zCol, 0);
 961     }else if( zTab ){
 962       sqlite3SetString(&z, zTab, ".", zCol, 0);
 963     }else{
 964       z = sqliteStrDup(zCol);
 965     }
 966     sqlite3ErrorMsg(pParse, zErr, z);
 967     sqliteFree(z);
 968     pTopNC->nErr++;
 969   }
 970
 971   /* If a column from a table in pSrcList is referenced, then record
 972   ** this fact in the pSrcList.a[].colUsed bitmask.  Column 0 causes
 973   ** bit 0 to be set.  Column 1 sets bit 1.  And so forth.  If the
 974   ** column number is greater than the number of bits in the bitmask
 975   ** then set the high-order bit of the bitmask.
 976   */
 977   if( pExpr->iColumn>=0 && pMatch!=0 ){
 978     int n = pExpr->iColumn;
 979     if( n>=sizeof(Bitmask)*8 ){
 980       n = sizeof(Bitmask)*8-1;
 981     }
 982     assert( pMatch->iCursor==pExpr->iTable );
 983     pMatch->colUsed |= 1<<n;
 984   }
 985
 986 lookupname_end:
 987   /* Clean up and return
 988   */
 989   sqliteFree(zDb);
 990   sqliteFree(zTab);
 991   sqlite3ExprDelete(pExpr->pLeft);
 992   pExpr->pLeft = 0;
 993   sqlite3ExprDelete(pExpr->pRight);
 994   pExpr->pRight = 0;
 995   pExpr->op = TK_COLUMN;
 996 lookupname_end_2:
 997   sqliteFree(zCol);
 998   if( cnt==1 ){
 999     assert( pNC!=0 );
1000     sqlite3AuthRead(pParse, pExpr, pNC->pSrcList);
1001     if( pMatch && !pMatch->pSelect ){
1002       pExpr->pTab = pMatch->pTab;
1003     }
1004     /* Increment the nRef value on all name contexts from TopNC up to
1005     ** the point where the name matched. */
1006     for(;;){
1007       assert( pTopNC!=0 );
1008       pTopNC->nRef++;
1009       if( pTopNC==pNC ) break;
1010       pTopNC = pTopNC->pNext;
1011     }
1012     return 0;
1013   } else {
1014     return 1;
1015   }
1016 }
1017
1018 /*
1019 ** This routine is designed as an xFunc for walkExprTree().
1020 **
1021 ** Resolve symbolic names into TK_COLUMN operators for the current
1022 ** node in the expression tree.  Return 0 to continue the search down
1023 ** the tree or 2 to abort the tree walk.
1024 **
1025 ** This routine also does error checking and name resolution for
1026 ** function names.  The operator for aggregate functions is changed
1027 ** to TK_AGG_FUNCTION.
1028 */
1029 static int nameResolverStep(void *pArg, Expr *pExpr){
1030   NameContext *pNC = (NameContext*)pArg;
1031   SrcList *pSrcList;
1032   Parse *pParse;
1033
1034   if( pExpr==0 ) return 1;
1035   assert( pNC!=0 );
1036   pSrcList = pNC->pSrcList;
1037   pParse = pNC->pParse;
1038
1039   if( ExprHasAnyProperty(pExpr, EP_Resolved) ) return 1;
1040   ExprSetProperty(pExpr, EP_Resolved);
1041 #ifndef NDEBUG
1042   if( pSrcList ){
1043     int i;
1044     for(i=0; i<pSrcList->nSrc; i++){
1045       assert( pSrcList->a[i].iCursor>=0 && pSrcList->a[i].iCursor<pParse->nTab);
1046     }
1047   }
1048 #endif
1049   switch( pExpr->op ){
1050     /* Double-quoted strings (ex: "abc") are used as identifiers if
1051     ** possible.  Otherwise they remain as strings.  Single-quoted
1052     ** strings (ex: 'abc') are always string literals.
1053     */
1054     case TK_STRING: {
1055       if( pExpr->token.z[0]=='\'' ) break;
1056       /* Fall thru into the TK_ID case if this is a double-quoted string */
1057     }
1058     /* A lone identifier is the name of a column.
1059     */
1060     case TK_ID: {
1061       lookupName(pParse, 0, 0, &pExpr->token, pNC, pExpr);
1062       return 1;
1063     }
1064
1065     /* A table name and column name:     ID.ID
1066     ** Or a database, table and column:  ID.ID.ID
1067     */
1068     case TK_DOT: {
1069       Token *pColumn;
1070       Token *pTable;
1071       Token *pDb;
1072       Expr *pRight;
1073
1074       /* if( pSrcList==0 ) break; */
1075       pRight = pExpr->pRight;
1076       if( pRight->op==TK_ID ){
1077         pDb = 0;
1078         pTable = &pExpr->pLeft->token;
1079         pColumn = &pRight->token;
1080       }else{
1081         assert( pRight->op==TK_DOT );
1082         pDb = &pExpr->pLeft->token;
1083         pTable = &pRight->pLeft->token;
1084         pColumn = &pRight->pRight->token;
1085       }
1086       lookupName(pParse, pDb, pTable, pColumn, pNC, pExpr);
1087       return 1;
1088     }
1089
1090     /* Resolve function names
1091     */
1092     case TK_CONST_FUNC:
1093     case TK_FUNCTION: {
1094       ExprList *pList = pExpr->pList;    /* The argument list */
1095       int n = pList ? pList->nExpr : 0;  /* Number of arguments */
1096       int no_such_func = 0;       /* True if no such function exists */
1097       int wrong_num_args = 0;     /* True if wrong number of arguments */
1098       int is_agg = 0;             /* True if is an aggregate function */
1099       int i;
1100       int nId;                    /* Number of characters in function name */
1101       const char *zId;            /* The function name. */
1102       FuncDef *pDef;              /* Information about the function */
1103       int enc = pParse->db->enc;  /* The database encoding */
1104
1105       zId = pExpr->token.z;
1106       nId = pExpr->token.n;
1107       pDef = sqlite3FindFunction(pParse->db, zId, nId, n, enc, 0);
1108       if( pDef==0 ){
1109         pDef = sqlite3FindFunction(pParse->db, zId, nId, -1, enc, 0);
1110         if( pDef==0 ){
1111           no_such_func = 1;
1112         }else{
1113           wrong_num_args = 1;
1114         }
1115       }else{
1116         is_agg = pDef->xFunc==0;
1117       }
1118       if( is_agg && !pNC->allowAgg ){
1119         sqlite3ErrorMsg(pParse, "misuse of aggregate function %.*s()", nId,zId);
1120         pNC->nErr++;
1121         is_agg = 0;
1122       }else if( no_such_func ){
1123         sqlite3ErrorMsg(pParse, "no such function: %.*s", nId, zId);
1124         pNC->nErr++;
1125       }else if( wrong_num_args ){
1126         sqlite3ErrorMsg(pParse,"wrong number of arguments to function %.*s()",
1127              nId, zId);
1128         pNC->nErr++;
1129       }
1130       if( is_agg ){
1131         pExpr->op = TK_AGG_FUNCTION;
1132         pNC->hasAgg = 1;
1133       }
1134       if( is_agg ) pNC->allowAgg = 0;
1135       for(i=0; pNC->nErr==0 && i<n; i++){
1136         walkExprTree(pList->a[i].pExpr, nameResolverStep, pNC);
1137       }
1138       if( is_agg ) pNC->allowAgg = 1;
1139       /* FIX ME:  Compute pExpr->affinity based on the expected return
1140       ** type of the function
1141       */
1142       return is_agg;
1143     }
1144 #ifndef SQLITE_OMIT_SUBQUERY
1145     case TK_SELECT:
1146     case TK_EXISTS:
1147 #endif
1148     case TK_IN: {
1149       if( pExpr->pSelect ){
1150         int nRef = pNC->nRef;
1151         sqlite3SelectResolve(pParse, pExpr->pSelect, pNC);
1152         assert( pNC->nRef>=nRef );
1153         if( nRef!=pNC->nRef ){
1154           ExprSetProperty(pExpr, EP_VarSelect);
1155         }
1156       }
1157     }
1158   }
1159   return 0;
1160 }
1161
1162 /*
1163 ** This routine walks an expression tree and resolves references to
1164 ** table columns.  Nodes of the form ID.ID or ID resolve into an
1165 ** index to the table in the table list and a column offset.  The
1166 ** Expr.opcode for such nodes is changed to TK_COLUMN.  The Expr.iTable
1167 ** value is changed to the index of the referenced table in pTabList
1168 ** plus the "base" value.  The base value will ultimately become the
1169 ** VDBE cursor number for a cursor that is pointing into the referenced
1170 ** table.  The Expr.iColumn value is changed to the index of the column
1171 ** of the referenced table.  The Expr.iColumn value for the special
1172 ** ROWID column is -1.  Any INTEGER PRIMARY KEY column is tried as an
1173 ** alias for ROWID.
1174 **
1175 ** Also resolve function names and check the functions for proper
1176 ** usage.  Make sure all function names are recognized and all functions
1177 ** have the correct number of arguments.  Leave an error message
1178 ** in pParse->zErrMsg if anything is amiss.  Return the number of errors.
1179 **
1180 ** If the expression contains aggregate functions then set the EP_Agg
1181 ** property on the expression.
1182 */
1183 int sqlite3ExprResolveNames(
1184   NameContext *pNC,       /* Namespace to resolve expressions in. */
1185   Expr *pExpr             /* The expression to be analyzed. */
1186 ){
1187   if( pExpr==0 ) return 0;
1188   walkExprTree(pExpr, nameResolverStep, pNC);
1189   if( pNC->nErr>0 ){
1190     ExprSetProperty(pExpr, EP_Error);
1191   }
1192   return ExprHasProperty(pExpr, EP_Error);
1193 }
1194
1195 /*
1196 ** A pointer instance of this structure is used to pass information
1197 ** through walkExprTree into codeSubqueryStep().
1198 */
1199 typedef struct QueryCoder QueryCoder;
1200 struct QueryCoder {
1201   Parse *pParse;       /* The parsing context */
1202   NameContext *pNC;    /* Namespace of first enclosing query */
1203 };
1204
1205
1206 /*
1207 ** Generate code for subqueries and IN operators.
1208 **
1209 ** IN operators comes in two forms:
1210 **
1211 **           expr IN (exprlist)
1212 ** and
1213 **           expr IN (SELECT ...)
1214 **
1215 ** The first form is handled by creating a set holding the list
1216 ** of allowed values.  The second form causes the SELECT to generate
1217 ** a temporary table.
1218 */
1219 #ifndef SQLITE_OMIT_SUBQUERY
1220 void sqlite3CodeSubselect(Parse *pParse, Expr *pExpr){
1221   int label = 0;                         /* Address after sub-select code */
1222   Vdbe *v = sqlite3GetVdbe(pParse);
1223   if( v==0 ) return;
1224
1225   /* If this is not a variable (correlated) select, then execute
1226   ** it only once. Unless this is part of a trigger program. In
1227   ** that case re-execute every time (this could be optimized).
1228   */
1229   if( !ExprHasAnyProperty(pExpr, EP_VarSelect) && !pParse->trigStack ){
1230     int mem = pParse->nMem++;
1231     sqlite3VdbeAddOp(v, OP_MemLoad, mem, 0);
1232     label = sqlite3VdbeMakeLabel(v);
1233     sqlite3VdbeAddOp(v, OP_If, 0, label);
1234     sqlite3VdbeAddOp(v, OP_Integer, 1, 0);
1235     sqlite3VdbeAddOp(v, OP_MemStore, mem, 1);
1236   }
1237
1238   if( pExpr->pSelect ){
1239     sqlite3VdbeAddOp(v, OP_AggContextPush, 0, 0);
1240   }
1241
1242   switch( pExpr->op ){
1243     case TK_IN: {
1244       char affinity;
1245       KeyInfo keyInfo;
1246       int addr;        /* Address of OP_OpenTemp instruction */
1247
1248       affinity = sqlite3ExprAffinity(pExpr->pLeft);
1249
1250       /* Whether this is an 'x IN(SELECT...)' or an 'x IN(<exprlist>)'
1251       ** expression it is handled the same way. A temporary table is
1252       ** filled with single-field index keys representing the results
1253       ** from the SELECT or the <exprlist>.
1254       **
1255       ** If the 'x' expression is a column value, or the SELECT...
1256       ** statement returns a column value, then the affinity of that
1257       ** column is used to build the index keys. If both 'x' and the
1258       ** SELECT... statement are columns, then numeric affinity is used
1259       ** if either column has NUMERIC or INTEGER affinity. If neither
1260       ** 'x' nor the SELECT... statement are columns, then numeric affinity
1261       ** is used.
1262       */
1263       pExpr->iTable = pParse->nTab++;
1264       addr = sqlite3VdbeAddOp(v, OP_OpenTemp, pExpr->iTable, 0);
1265       memset(&keyInfo, 0, sizeof(keyInfo));
1266       keyInfo.nField = 1;
1267       sqlite3VdbeAddOp(v, OP_SetNumColumns, pExpr->iTable, 1);
1268
1269       if( pExpr->pSelect ){
1270         /* Case 1:     expr IN (SELECT ...)
1271         **
1272         ** Generate code to write the results of the select into the temporary
1273         ** table allocated and opened above.
1274         */
1275         int iParm = pExpr->iTable +  (((int)affinity)<<16);
1276         ExprList *pEList;
1277         assert( (pExpr->iTable&0x0000FFFF)==pExpr->iTable );
1278         sqlite3Select(pParse, pExpr->pSelect, SRT_Set, iParm, 0, 0, 0, 0);
1279         pEList = pExpr->pSelect->pEList;
1280         if( pEList && pEList->nExpr>0 ){
1281           keyInfo.aColl[0] = binaryCompareCollSeq(pParse, pExpr->pLeft,
1282               pEList->a[0].pExpr);
1283         }
1284       }else if( pExpr->pList ){
1285         /* Case 2:     expr IN (exprlist)
1286         **
1287         ** For each expression, build an index key from the evaluation and
1288         ** store it in the temporary table. If <expr> is a column, then use
1289         ** that columns affinity when building index keys. If <expr> is not
1290         ** a column, use numeric affinity.
1291         */
1292         int i;
1293         if( !affinity ){
1294           affinity = SQLITE_AFF_NUMERIC;
1295         }
1296         keyInfo.aColl[0] = pExpr->pLeft->pColl;
1297
1298         /* Loop through each expression in <exprlist>. */
1299         for(i=0; i<pExpr->pList->nExpr; i++){
1300           Expr *pE2 = pExpr->pList->a[i].pExpr;
1301
1302           /* Check that the expression is constant and valid. */
1303           if( !sqlite3ExprIsConstant(pE2) ){
1304             sqlite3ErrorMsg(pParse,
1305               "right-hand side of IN operator must be constant");
1306             return;
1307           }
1308
1309           /* Evaluate the expression and insert it into the temp table */
1310           sqlite3ExprCode(pParse, pE2);
1311           sqlite3VdbeOp3(v, OP_MakeRecord, 1, 0, &affinity, 1);
1312           sqlite3VdbeAddOp(v, OP_IdxInsert, pExpr->iTable, 0);
1313         }
1314       }
1315       sqlite3VdbeChangeP3(v, addr, (void *)&keyInfo, P3_KEYINFO);
1316       break;
1317     }
1318
1319     case TK_EXISTS:
1320     case TK_SELECT: {
1321       /* This has to be a scalar SELECT.  Generate code to put the
1322       ** value of this select in a memory cell and record the number
1323       ** of the memory cell in iColumn.
1324       */
1325       int sop;
1326       Select *pSel;
1327
1328       pExpr->iColumn = pParse->nMem++;
1329       pSel = pExpr->pSelect;
1330       if( pExpr->op==TK_SELECT ){
1331         sop = SRT_Mem;
1332       }else{
1333         static const Token one = { "1", 0, 1 };
1334         sop = SRT_Exists;
1335         sqlite3ExprListDelete(pSel->pEList);
1336         pSel->pEList = sqlite3ExprListAppend(0,
1337                           sqlite3Expr(TK_INTEGER, 0, 0, &one), 0);
1338       }
1339       sqlite3Select(pParse, pSel, sop, pExpr->iColumn, 0, 0, 0, 0);
1340       break;
1341     }
1342   }
1343
1344   if( pExpr->pSelect ){
1345     sqlite3VdbeAddOp(v, OP_AggContextPop, 0, 0);
1346   }
1347   if( label<0 ){
1348     sqlite3VdbeResolveLabel(v, label);
1349   }
1350   return;
1351 }
1352 #endif /* SQLITE_OMIT_SUBQUERY */
1353
1354 /*
1355 ** Generate an instruction that will put the integer describe by
1356 ** text z[0..n-1] on the stack.
1357 */
1358 static void codeInteger(Vdbe *v, const char *z, int n){
1359   int i;
1360   if( sqlite3GetInt32(z, &i) ){
1361     sqlite3VdbeAddOp(v, OP_Integer, i, 0);
1362   }else if( sqlite3FitsIn64Bits(z) ){
1363     sqlite3VdbeOp3(v, OP_Integer, 0, 0, z, n);
1364   }else{
1365     sqlite3VdbeOp3(v, OP_Real, 0, 0, z, n);
1366   }
1367 }
1368
1369 /*
1370 ** Generate code into the current Vdbe to evaluate the given
1371 ** expression and leave the result on the top of stack.
1372 **
1373 ** This code depends on the fact that certain token values (ex: TK_EQ)
1374 ** are the same as opcode values (ex: OP_Eq) that implement the corresponding
1375 ** operation.  Special comments in vdbe.c and the mkopcodeh.awk script in
1376 ** the make process cause these values to align.  Assert()s in the code
1377 ** below verify that the numbers are aligned correctly.
1378 */
1379 void sqlite3ExprCode(Parse *pParse, Expr *pExpr){
1380   Vdbe *v = pParse->pVdbe;
1381   int op;
1382   if( v==0 ) return;
1383   if( pExpr==0 ){
1384     sqlite3VdbeAddOp(v, OP_Null, 0, 0);
1385     return;
1386   }
1387   op = pExpr->op;
1388   switch( op ){
1389     case TK_COLUMN: {
1390       if( !pParse->fillAgg && pExpr->iAgg>=0 ){
1391         sqlite3VdbeAddOp(v, OP_AggGet, pExpr->iAggCtx, pExpr->iAgg);
1392       }else if( pExpr->iColumn>=0 ){
1393         sqlite3VdbeAddOp(v, OP_Column, pExpr->iTable, pExpr->iColumn);
1394         sqlite3ColumnDefault(v, pExpr->pTab, pExpr->iColumn);
1395       }else{
1396         sqlite3VdbeAddOp(v, OP_Rowid, pExpr->iTable, 0);
1397       }
1398       break;
1399     }
1400     case TK_INTEGER: {
1401       codeInteger(v, pExpr->token.z, pExpr->token.n);
1402       break;
1403     }
1404     case TK_FLOAT:
1405     case TK_STRING: {
1406       assert( TK_FLOAT==OP_Real );
1407       assert( TK_STRING==OP_String8 );
1408       sqlite3VdbeOp3(v, op, 0, 0, pExpr->token.z, pExpr->token.n);
1409       sqlite3VdbeDequoteP3(v, -1);
1410       break;
1411     }
1412     case TK_NULL: {
1413       sqlite3VdbeAddOp(v, OP_Null, 0, 0);
1414       break;
1415     }
1416 #ifndef SQLITE_OMIT_BLOB_LITERAL
1417     case TK_BLOB: {
1418       assert( TK_BLOB==OP_HexBlob );
1419       sqlite3VdbeOp3(v, op, 0, 0, pExpr->token.z+1, pExpr->token.n-1);
1420       sqlite3VdbeDequoteP3(v, -1);
1421       break;
1422     }
1423 #endif
1424     case TK_VARIABLE: {
1425       sqlite3VdbeAddOp(v, OP_Variable, pExpr->iTable, 0);
1426       if( pExpr->token.n>1 ){
1427         sqlite3VdbeChangeP3(v, -1, pExpr->token.z, pExpr->token.n);
1428       }
1429       break;
1430     }
1431     case TK_REGISTER: {
1432       sqlite3VdbeAddOp(v, OP_MemLoad, pExpr->iTable, 0);
1433       break;
1434     }
1435     case TK_LT:
1436     case TK_LE:
1437     case TK_GT:
1438     case TK_GE:
1439     case TK_NE:
1440     case TK_EQ: {
1441       assert( TK_LT==OP_Lt );
1442       assert( TK_LE==OP_Le );
1443       assert( TK_GT==OP_Gt );
1444       assert( TK_GE==OP_Ge );
1445       assert( TK_EQ==OP_Eq );
1446       assert( TK_NE==OP_Ne );
1447       sqlite3ExprCode(pParse, pExpr->pLeft);
1448       sqlite3ExprCode(pParse, pExpr->pRight);
1449       codeCompare(pParse, pExpr->pLeft, pExpr->pRight, op, 0, 0);
1450       break;
1451     }
1452     case TK_AND:
1453     case TK_OR:
1454     case TK_PLUS:
1455     case TK_STAR:
1456     case TK_MINUS:
1457     case TK_REM:
1458     case TK_BITAND:
1459     case TK_BITOR:
1460     case TK_SLASH:
1461     case TK_LSHIFT:
1462     case TK_RSHIFT:
1463     case TK_CONCAT: {
1464       assert( TK_AND==OP_And );
1465       assert( TK_OR==OP_Or );
1466       assert( TK_PLUS==OP_Add );
1467       assert( TK_MINUS==OP_Subtract );
1468       assert( TK_REM==OP_Remainder );
1469       assert( TK_BITAND==OP_BitAnd );
1470       assert( TK_BITOR==OP_BitOr );
1471       assert( TK_SLASH==OP_Divide );
1472       assert( TK_LSHIFT==OP_ShiftLeft );
1473       assert( TK_RSHIFT==OP_ShiftRight );
1474       assert( TK_CONCAT==OP_Concat );
1475       sqlite3ExprCode(pParse, pExpr->pLeft);
1476       sqlite3ExprCode(pParse, pExpr->pRight);
1477       sqlite3VdbeAddOp(v, op, 0, 0);
1478       break;
1479     }
1480     case TK_UMINUS: {
1481       Expr *pLeft = pExpr->pLeft;
1482       assert( pLeft );
1483       if( pLeft->op==TK_FLOAT || pLeft->op==TK_INTEGER ){
1484         Token *p = &pLeft->token;
1485         char *z = sqliteMalloc( p->n + 2 );
1486         sprintf(z, "-%.*s", p->n, p->z);
1487         if( pLeft->op==TK_FLOAT ){
1488           sqlite3VdbeOp3(v, OP_Real, 0, 0, z, p->n+1);
1489         }else{
1490           codeInteger(v, z, p->n+1);
1491         }
1492         sqliteFree(z);
1493         break;
1494       }
1495       /* Fall through into TK_NOT */
1496     }
1497     case TK_BITNOT:
1498     case TK_NOT: {
1499       assert( TK_BITNOT==OP_BitNot );
1500       assert( TK_NOT==OP_Not );
1501       sqlite3ExprCode(pParse, pExpr->pLeft);
1502       sqlite3VdbeAddOp(v, op, 0, 0);
1503       break;
1504     }
1505     case TK_ISNULL:
1506     case TK_NOTNULL: {
1507       int dest;
1508       assert( TK_ISNULL==OP_IsNull );
1509       assert( TK_NOTNULL==OP_NotNull );
1510       sqlite3VdbeAddOp(v, OP_Integer, 1, 0);
1511       sqlite3ExprCode(pParse, pExpr->pLeft);
1512       dest = sqlite3VdbeCurrentAddr(v) + 2;
1513       sqlite3VdbeAddOp(v, op, 1, dest);
1514       sqlite3VdbeAddOp(v, OP_AddImm, -1, 0);
1515       break;
1516     }
1517     case TK_AGG_FUNCTION: {
1518       sqlite3VdbeAddOp(v, OP_AggGet, 0, pExpr->iAgg);
1519       break;
1520     }
1521     case TK_CONST_FUNC:
1522     case TK_FUNCTION: {
1523       ExprList *pList = pExpr->pList;
1524       int nExpr = pList ? pList->nExpr : 0;
1525       FuncDef *pDef;
1526       int nId;
1527       const char *zId;
1528       int p2 = 0;
1529       int i;
1530       u8 enc = pParse->db->enc;
1531       CollSeq *pColl = 0;
1532       zId = pExpr->token.z;
1533       nId = pExpr->token.n;
1534       pDef = sqlite3FindFunction(pParse->db, zId, nId, nExpr, enc, 0);
1535       assert( pDef!=0 );
1536       nExpr = sqlite3ExprCodeExprList(pParse, pList);
1537       for(i=0; i<nExpr && i<32; i++){
1538         if( sqlite3ExprIsConstant(pList->a[i].pExpr) ){
1539           p2 |= (1<<i);
1540         }
1541         if( pDef->needCollSeq && !pColl ){
1542           pColl = sqlite3ExprCollSeq(pParse, pList->a[i].pExpr);
1543         }
1544       }
1545       if( pDef->needCollSeq ){
1546         if( !pColl ) pColl = pParse->db->pDfltColl;
1547         sqlite3VdbeOp3(v, OP_CollSeq, 0, 0, (char *)pColl, P3_COLLSEQ);
1548       }
1549       sqlite3VdbeOp3(v, OP_Function, nExpr, p2, (char*)pDef, P3_FUNCDEF);
1550       break;
1551     }
1552 #ifndef SQLITE_OMIT_SUBQUERY
1553     case TK_EXISTS:
1554     case TK_SELECT: {
1555       sqlite3CodeSubselect(pParse, pExpr);
1556       sqlite3VdbeAddOp(v, OP_MemLoad, pExpr->iColumn, 0);
1557       VdbeComment((v, "# load subquery result"));
1558       break;
1559     }
1560     case TK_IN: {
1561       int addr;
1562       char affinity;
1563       sqlite3CodeSubselect(pParse, pExpr);
1564
1565       /* Figure out the affinity to use to create a key from the results
1566       ** of the expression. affinityStr stores a static string suitable for
1567       ** P3 of OP_MakeRecord.
1568       */
1569       affinity = comparisonAffinity(pExpr);
1570
1571       sqlite3VdbeAddOp(v, OP_Integer, 1, 0);
1572
1573       /* Code the <expr> from "<expr> IN (...)". The temporary table
1574       ** pExpr->iTable contains the values that make up the (...) set.
1575       */
1576       sqlite3ExprCode(pParse, pExpr->pLeft);
1577       addr = sqlite3VdbeCurrentAddr(v);
1578       sqlite3VdbeAddOp(v, OP_NotNull, -1, addr+4);            /* addr + 0 */
1579       sqlite3VdbeAddOp(v, OP_Pop, 2, 0);
1580       sqlite3VdbeAddOp(v, OP_Null, 0, 0);
1581       sqlite3VdbeAddOp(v, OP_Goto, 0, addr+7);
1582       sqlite3VdbeOp3(v, OP_MakeRecord, 1, 0, &affinity, 1);   /* addr + 4 */
1583       sqlite3VdbeAddOp(v, OP_Found, pExpr->iTable, addr+7);
1584       sqlite3VdbeAddOp(v, OP_AddImm, -1, 0);                  /* addr + 6 */
1585
1586       break;
1587     }
1588 #endif
1589     case TK_BETWEEN: {
1590       Expr *pLeft = pExpr->pLeft;
1591       struct ExprList_item *pLItem = pExpr->pList->a;
1592       Expr *pRight = pLItem->pExpr;
1593       sqlite3ExprCode(pParse, pLeft);
1594       sqlite3VdbeAddOp(v, OP_Dup, 0, 0);
1595       sqlite3ExprCode(pParse, pRight);
1596       codeCompare(pParse, pLeft, pRight, OP_Ge, 0, 0);
1597       sqlite3VdbeAddOp(v, OP_Pull, 1, 0);
1598       pLItem++;
1599       pRight = pLItem->pExpr;
1600       sqlite3ExprCode(pParse, pRight);
1601       codeCompare(pParse, pLeft, pRight, OP_Le, 0, 0);
1602       sqlite3VdbeAddOp(v, OP_And, 0, 0);
1603       break;
1604     }
1605     case TK_UPLUS:
1606     case TK_AS: {
1607       sqlite3ExprCode(pParse, pExpr->pLeft);
1608       break;
1609     }
1610     case TK_CASE: {
1611       int expr_end_label;
1612       int jumpInst;
1613       int addr;
1614       int nExpr;
1615       int i;
1616       ExprList *pEList;
1617       struct ExprList_item *aListelem;
1618
1619       assert(pExpr->pList);
1620       assert((pExpr->pList->nExpr % 2) == 0);
1621       assert(pExpr->pList->nExpr > 0);
1622       pEList = pExpr->pList;
1623       aListelem = pEList->a;
1624       nExpr = pEList->nExpr;
1625       expr_end_label = sqlite3VdbeMakeLabel(v);
1626       if( pExpr->pLeft ){
1627         sqlite3ExprCode(pParse, pExpr->pLeft);
1628       }
1629       for(i=0; i<nExpr; i=i+2){
1630         sqlite3ExprCode(pParse, aListelem[i].pExpr);
1631         if( pExpr->pLeft ){
1632           sqlite3VdbeAddOp(v, OP_Dup, 1, 1);
1633           jumpInst = codeCompare(pParse, pExpr->pLeft, aListelem[i].pExpr,
1634                                  OP_Ne, 0, 1);
1635           sqlite3VdbeAddOp(v, OP_Pop, 1, 0);
1636         }else{
1637           jumpInst = sqlite3VdbeAddOp(v, OP_IfNot, 1, 0);
1638         }
1639         sqlite3ExprCode(pParse, aListelem[i+1].pExpr);
1640         sqlite3VdbeAddOp(v, OP_Goto, 0, expr_end_label);
1641         addr = sqlite3VdbeCurrentAddr(v);
1642         sqlite3VdbeChangeP2(v, jumpInst, addr);
1643       }
1644       if( pExpr->pLeft ){
1645         sqlite3VdbeAddOp(v, OP_Pop, 1, 0);
1646       }
1647       if( pExpr->pRight ){
1648         sqlite3ExprCode(pParse, pExpr->pRight);
1649       }else{
1650         sqlite3VdbeAddOp(v, OP_Null, 0, 0);
1651       }
1652       sqlite3VdbeResolveLabel(v, expr_end_label);
1653       break;
1654     }
1655 #ifndef SQLITE_OMIT_TRIGGER
1656     case TK_RAISE: {
1657       if( !pParse->trigStack ){
1658         sqlite3ErrorMsg(pParse,
1659                        "RAISE() may only be used within a trigger-program");
1660         return;
1661       }
1662       if( pExpr->iColumn!=OE_Ignore ){
1663          assert( pExpr->iColumn==OE_Rollback ||
1664                  pExpr->iColumn == OE_Abort ||
1665                  pExpr->iColumn == OE_Fail );
1666          sqlite3VdbeOp3(v, OP_Halt, SQLITE_CONSTRAINT, pExpr->iColumn,
1667                         pExpr->token.z, pExpr->token.n);
1668          sqlite3VdbeDequoteP3(v, -1);
1669       } else {
1670          assert( pExpr->iColumn == OE_Ignore );
1671          sqlite3VdbeAddOp(v, OP_ContextPop, 0, 0);
1672          sqlite3VdbeAddOp(v, OP_Goto, 0, pParse->trigStack->ignoreJump);
1673          VdbeComment((v, "# raise(IGNORE)"));
1674       }
1675     }
1676 #endif
1677     break;
1678   }
1679 }
1680
1681 #ifndef SQLITE_OMIT_TRIGGER
1682 /*
1683 ** Generate code that evalutes the given expression and leaves the result
1684 ** on the stack.  See also sqlite3ExprCode().
1685 **
1686 ** This routine might also cache the result and modify the pExpr tree
1687 ** so that it will make use of the cached result on subsequent evaluations
1688 ** rather than evaluate the whole expression again.  Trivial expressions are
1689 ** not cached.  If the expression is cached, its result is stored in a
1690 ** memory location.
1691 */
1692 void sqlite3ExprCodeAndCache(Parse *pParse, Expr *pExpr){
1693   Vdbe *v = pParse->pVdbe;
1694   int iMem;
1695   int addr1, addr2;
1696   if( v==0 ) return;
1697   addr1 = sqlite3VdbeCurrentAddr(v);
1698   sqlite3ExprCode(pParse, pExpr);
1699   addr2 = sqlite3VdbeCurrentAddr(v);
1700   if( addr2>addr1+1 || sqlite3VdbeGetOp(v, addr1)->opcode==OP_Function ){
1701     iMem = pExpr->iTable = pParse->nMem++;
1702     sqlite3VdbeAddOp(v, OP_MemStore, iMem, 0);
1703     pExpr->op = TK_REGISTER;
1704   }
1705 }
1706 #endif
1707
1708 /*
1709 ** Generate code that pushes the value of every element of the given
1710 ** expression list onto the stack.
1711 **
1712 ** Return the number of elements pushed onto the stack.
1713 */
1714 int sqlite3ExprCodeExprList(
1715   Parse *pParse,     /* Parsing context */
1716   ExprList *pList    /* The expression list to be coded */
1717 ){
1718   struct ExprList_item *pItem;
1719   int i, n;
1720   Vdbe *v;
1721   if( pList==0 ) return 0;
1722   v = sqlite3GetVdbe(pParse);
1723   n = pList->nExpr;
1724   for(pItem=pList->a, i=0; i<n; i++, pItem++){
1725     sqlite3ExprCode(pParse, pItem->pExpr);
1726   }
1727   return n;
1728 }
1729
1730 /*
1731 ** Generate code for a boolean expression such that a jump is made
1732 ** to the label "dest" if the expression is true but execution
1733 ** continues straight thru if the expression is false.
1734 **
1735 ** If the expression evaluates to NULL (neither true nor false), then
1736 ** take the jump if the jumpIfNull flag is true.
1737 **
1738 ** This code depends on the fact that certain token values (ex: TK_EQ)
1739 ** are the same as opcode values (ex: OP_Eq) that implement the corresponding
1740 ** operation.  Special comments in vdbe.c and the mkopcodeh.awk script in
1741 ** the make process cause these values to align.  Assert()s in the code
1742 ** below verify that the numbers are aligned correctly.
1743 */
1744 void sqlite3ExprIfTrue(Parse *pParse, Expr *pExpr, int dest, int jumpIfNull){
1745   Vdbe *v = pParse->pVdbe;
1746   int op = 0;
1747   if( v==0 || pExpr==0 ) return;
1748   op = pExpr->op;
1749   switch( op ){
1750     case TK_AND: {
1751       int d2 = sqlite3VdbeMakeLabel(v);
1752       sqlite3ExprIfFalse(pParse, pExpr->pLeft, d2, !jumpIfNull);
1753       sqlite3ExprIfTrue(pParse, pExpr->pRight, dest, jumpIfNull);
1754       sqlite3VdbeResolveLabel(v, d2);
1755       break;
1756     }
1757     case TK_OR: {
1758       sqlite3ExprIfTrue(pParse, pExpr->pLeft, dest, jumpIfNull);
1759       sqlite3ExprIfTrue(pParse, pExpr->pRight, dest, jumpIfNull);
1760       break;
1761     }
1762     case TK_NOT: {
1763       sqlite3ExprIfFalse(pParse, pExpr->pLeft, dest, jumpIfNull);
1764       break;
1765     }
1766     case TK_LT:
1767     case TK_LE:
1768     case TK_GT:
1769     case TK_GE:
1770     case TK_NE:
1771     case TK_EQ: {
1772       assert( TK_LT==OP_Lt );
1773       assert( TK_LE==OP_Le );
1774       assert( TK_GT==OP_Gt );
1775       assert( TK_GE==OP_Ge );
1776       assert( TK_EQ==OP_Eq );
1777       assert( TK_NE==OP_Ne );
1778       sqlite3ExprCode(pParse, pExpr->pLeft);
1779       sqlite3ExprCode(pParse, pExpr->pRight);
1780       codeCompare(pParse, pExpr->pLeft, pExpr->pRight, op, dest, jumpIfNull);
1781       break;
1782     }
1783     case TK_ISNULL:
1784     case TK_NOTNULL: {
1785       assert( TK_ISNULL==OP_IsNull );
1786       assert( TK_NOTNULL==OP_NotNull );
1787       sqlite3ExprCode(pParse, pExpr->pLeft);
1788       sqlite3VdbeAddOp(v, op, 1, dest);
1789       break;
1790     }
1791     case TK_BETWEEN: {
1792       /* The expression "x BETWEEN y AND z" is implemented as:
1793       **
1794       ** 1 IF (x < y) GOTO 3
1795       ** 2 IF (x <= z) GOTO <dest>
1796       ** 3 ...
1797       */
1798       int addr;
1799       Expr *pLeft = pExpr->pLeft;
1800       Expr *pRight = pExpr->pList->a[0].pExpr;
1801       sqlite3ExprCode(pParse, pLeft);
1802       sqlite3VdbeAddOp(v, OP_Dup, 0, 0);
1803       sqlite3ExprCode(pParse, pRight);
1804       addr = codeCompare(pParse, pLeft, pRight, OP_Lt, 0, !jumpIfNull);
1805
1806       pRight = pExpr->pList->a[1].pExpr;
1807       sqlite3ExprCode(pParse, pRight);
1808       codeCompare(pParse, pLeft, pRight, OP_Le, dest, jumpIfNull);
1809
1810       sqlite3VdbeAddOp(v, OP_Integer, 0, 0);
1811       sqlite3VdbeChangeP2(v, addr, sqlite3VdbeCurrentAddr(v));
1812       sqlite3VdbeAddOp(v, OP_Pop, 1, 0);
1813       break;
1814     }
1815     default: {
1816       sqlite3ExprCode(pParse, pExpr);
1817       sqlite3VdbeAddOp(v, OP_If, jumpIfNull, dest);
1818       break;
1819     }
1820   }
1821 }
1822
1823 /*
1824 ** Generate code for a boolean expression such that a jump is made
1825 ** to the label "dest" if the expression is false but execution
1826 ** continues straight thru if the expression is true.
1827 **
1828 ** If the expression evaluates to NULL (neither true nor false) then
1829 ** jump if jumpIfNull is true or fall through if jumpIfNull is false.
1830 */
1831 void sqlite3ExprIfFalse(Parse *pParse, Expr *pExpr, int dest, int jumpIfNull){
1832   Vdbe *v = pParse->pVdbe;
1833   int op = 0;
1834   if( v==0 || pExpr==0 ) return;
1835
1836   /* The value of pExpr->op and op are related as follows:
1837   **
1838   **       pExpr->op            op
1839   **       ---------          ----------
1840   **       TK_ISNULL          OP_NotNull
1841   **       TK_NOTNULL         OP_IsNull
1842   **       TK_NE              OP_Eq
1843   **       TK_EQ              OP_Ne
1844   **       TK_GT              OP_Le
1845   **       TK_LE              OP_Gt
1846   **       TK_GE              OP_Lt
1847   **       TK_LT              OP_Ge
1848   **
1849   ** For other values of pExpr->op, op is undefined and unused.
1850   ** The value of TK_ and OP_ constants are arranged such that we
1851   ** can compute the mapping above using the following expression.
1852   ** Assert()s verify that the computation is correct.
1853   */
1854   op = ((pExpr->op+(TK_ISNULL&1))^1)-(TK_ISNULL&1);
1855
1856   /* Verify correct alignment of TK_ and OP_ constants
1857   */
1858   assert( pExpr->op!=TK_ISNULL || op==OP_NotNull );
1859   assert( pExpr->op!=TK_NOTNULL || op==OP_IsNull );
1860   assert( pExpr->op!=TK_NE || op==OP_Eq );
1861   assert( pExpr->op!=TK_EQ || op==OP_Ne );
1862   assert( pExpr->op!=TK_LT || op==OP_Ge );
1863   assert( pExpr->op!=TK_LE || op==OP_Gt );
1864   assert( pExpr->op!=TK_GT || op==OP_Le );
1865   assert( pExpr->op!=TK_GE || op==OP_Lt );
1866
1867   switch( pExpr->op ){
1868     case TK_AND: {
1869       sqlite3ExprIfFalse(pParse, pExpr->pLeft, dest, jumpIfNull);
1870       sqlite3ExprIfFalse(pParse, pExpr->pRight, dest, jumpIfNull);
1871       break;
1872     }
1873     case TK_OR: {
1874       int d2 = sqlite3VdbeMakeLabel(v);
1875       sqlite3ExprIfTrue(pParse, pExpr->pLeft, d2, !jumpIfNull);
1876       sqlite3ExprIfFalse(pParse, pExpr->pRight, dest, jumpIfNull);
1877       sqlite3VdbeResolveLabel(v, d2);
1878       break;
1879     }
1880     case TK_NOT: {
1881       sqlite3ExprIfTrue(pParse, pExpr->pLeft, dest, jumpIfNull);
1882       break;
1883     }
1884     case TK_LT:
1885     case TK_LE:
1886     case TK_GT:
1887     case TK_GE:
1888     case TK_NE:
1889     case TK_EQ: {
1890       sqlite3ExprCode(pParse, pExpr->pLeft);
1891       sqlite3ExprCode(pParse, pExpr->pRight);
1892       codeCompare(pParse, pExpr->pLeft, pExpr->pRight, op, dest, jumpIfNull);
1893       break;
1894     }
1895     case TK_ISNULL:
1896     case TK_NOTNULL: {
1897       sqlite3ExprCode(pParse, pExpr->pLeft);
1898       sqlite3VdbeAddOp(v, op, 1, dest);
1899       break;
1900     }
1901     case TK_BETWEEN: {
1902       /* The expression is "x BETWEEN y AND z". It is implemented as:
1903       **
1904       ** 1 IF (x >= y) GOTO 3
1905       ** 2 GOTO <dest>
1906       ** 3 IF (x > z) GOTO <dest>
1907       */
1908       int addr;
1909       Expr *pLeft = pExpr->pLeft;
1910       Expr *pRight = pExpr->pList->a[0].pExpr;
1911       sqlite3ExprCode(pParse, pLeft);
1912       sqlite3VdbeAddOp(v, OP_Dup, 0, 0);
1913       sqlite3ExprCode(pParse, pRight);
1914       addr = sqlite3VdbeCurrentAddr(v);
1915       codeCompare(pParse, pLeft, pRight, OP_Ge, addr+3, !jumpIfNull);
1916
1917       sqlite3VdbeAddOp(v, OP_Pop, 1, 0);
1918       sqlite3VdbeAddOp(v, OP_Goto, 0, dest);
1919       pRight = pExpr->pList->a[1].pExpr;
1920       sqlite3ExprCode(pParse, pRight);
1921       codeCompare(pParse, pLeft, pRight, OP_Gt, dest, jumpIfNull);
1922       break;
1923     }
1924     default: {
1925       sqlite3ExprCode(pParse, pExpr);
1926       sqlite3VdbeAddOp(v, OP_IfNot, jumpIfNull, dest);
1927       break;
1928     }
1929   }
1930 }
1931
1932 /*
1933 ** Do a deep comparison of two expression trees.  Return TRUE (non-zero)
1934 ** if they are identical and return FALSE if they differ in any way.
1935 */
1936 int sqlite3ExprCompare(Expr *pA, Expr *pB){
1937   int i;
1938   if( pA==0 ){
1939     return pB==0;
1940   }else if( pB==0 ){
1941     return 0;
1942   }
1943   if( pA->op!=pB->op ) return 0;
1944   if( !sqlite3ExprCompare(pA->pLeft, pB->pLeft) ) return 0;
1945   if( !sqlite3ExprCompare(pA->pRight, pB->pRight) ) return 0;
1946   if( pA->pList ){
1947     if( pB->pList==0 ) return 0;
1948     if( pA->pList->nExpr!=pB->pList->nExpr ) return 0;
1949     for(i=0; i<pA->pList->nExpr; i++){
1950       if( !sqlite3ExprCompare(pA->pList->a[i].pExpr, pB->pList->a[i].pExpr) ){
1951         return 0;
1952       }
1953     }
1954   }else if( pB->pList ){
1955     return 0;
1956   }
1957   if( pA->pSelect || pB->pSelect ) return 0;
1958   if( pA->iTable!=pB->iTable || pA->iColumn!=pB->iColumn ) return 0;
1959   if( pA->token.z ){
1960     if( pB->token.z==0 ) return 0;
1961     if( pB->token.n!=pA->token.n ) return 0;
1962     if( sqlite3StrNICmp(pA->token.z, pB->token.z, pB->token.n)!=0 ) return 0;
1963   }
1964   return 1;
1965 }
1966
1967 /*
1968 ** Add a new element to the pParse->aAgg[] array and return its index.
1969 ** The new element is initialized to zero.  The calling function is
1970 ** expected to fill it in.
1971 */
1972 static int appendAggInfo(Parse *pParse){
1973   if( (pParse->nAgg & 0x7)==0 ){
1974     int amt = pParse->nAgg + 8;
1975     AggExpr *aAgg = sqliteRealloc(pParse->aAgg, amt*sizeof(pParse->aAgg[0]));
1976     if( aAgg==0 ){
1977       return -1;
1978     }
1979     pParse->aAgg = aAgg;
1980   }
1981   memset(&pParse->aAgg[pParse->nAgg], 0, sizeof(pParse->aAgg[0]));
1982   return pParse->nAgg++;
1983 }
1984
1985 /*
1986 ** This is an xFunc for walkExprTree() used to implement
1987 ** sqlite3ExprAnalyzeAggregates().  See sqlite3ExprAnalyzeAggregates
1988 ** for additional information.
1989 **
1990 ** This routine analyzes the aggregate function at pExpr.
1991 */
1992 static int analyzeAggregate(void *pArg, Expr *pExpr){
1993   int i;
1994   AggExpr *aAgg;
1995   NameContext *pNC = (NameContext *)pArg;
1996   Parse *pParse = pNC->pParse;
1997   SrcList *pSrcList = pNC->pSrcList;
1998
1999   switch( pExpr->op ){
2000     case TK_COLUMN: {
2001       for(i=0; pSrcList && i<pSrcList->nSrc; i++){
2002         if( pExpr->iTable==pSrcList->a[i].iCursor ){
2003           aAgg = pParse->aAgg;
2004           for(i=0; i<pParse->nAgg; i++){
2005             if( aAgg[i].isAgg ) continue;
2006             if( aAgg[i].pExpr->iTable==pExpr->iTable
2007              && aAgg[i].pExpr->iColumn==pExpr->iColumn ){
2008               break;
2009             }
2010           }
2011           if( i>=pParse->nAgg ){
2012             i = appendAggInfo(pParse);
2013             if( i<0 ) return 1;
2014             pParse->aAgg[i].isAgg = 0;
2015             pParse->aAgg[i].pExpr = pExpr;
2016           }
2017           pExpr->iAgg = i;
2018           pExpr->iAggCtx = pNC->nDepth;
2019           return 1;
2020         }
2021       }
2022       return 1;
2023     }
2024     case TK_AGG_FUNCTION: {
2025       if( pNC->nDepth==0 ){
2026         aAgg = pParse->aAgg;
2027         for(i=0; i<pParse->nAgg; i++){
2028           if( !aAgg[i].isAgg ) continue;
2029           if( sqlite3ExprCompare(aAgg[i].pExpr, pExpr) ){
2030             break;
2031           }
2032         }
2033         if( i>=pParse->nAgg ){
2034           u8 enc = pParse->db->enc;
2035           i = appendAggInfo(pParse);
2036           if( i<0 ) return 1;
2037           pParse->aAgg[i].isAgg = 1;
2038           pParse->aAgg[i].pExpr = pExpr;
2039           pParse->aAgg[i].pFunc = sqlite3FindFunction(pParse->db,
2040                pExpr->token.z, pExpr->token.n,
2041                pExpr->pList ? pExpr->pList->nExpr : 0, enc, 0);
2042         }
2043         pExpr->iAgg = i;
2044         return 1;
2045       }
2046     }
2047   }
2048   if( pExpr->pSelect ){
2049     pNC->nDepth++;
2050     walkSelectExpr(pExpr->pSelect, analyzeAggregate, pNC);
2051     pNC->nDepth--;
2052   }
2053   return 0;
2054 }
2055
2056 /*
2057 ** Analyze the given expression looking for aggregate functions and
2058 ** for variables that need to be added to the pParse->aAgg[] array.
2059 ** Make additional entries to the pParse->aAgg[] array as necessary.
2060 **
2061 ** This routine should only be called after the expression has been
2062 ** analyzed by sqlite3ExprResolveNames().
2063 **
2064 ** If errors are seen, leave an error message in zErrMsg and return
2065 ** the number of errors.
2066 */
2067 int sqlite3ExprAnalyzeAggregates(NameContext *pNC, Expr *pExpr){
2068   int nErr = pNC->pParse->nErr;
2069   walkExprTree(pExpr, analyzeAggregate, pNC);
2070   return pNC->pParse->nErr - nErr;
2071 }