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: expr.c,v 1.268 2006/08/24 15:18:25 drh Exp $

    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   int op = pExpr->op;

    38   if( op==TK_AS ){

    39     return sqlite3ExprAffinity(pExpr->pLeft);

    40   }

    41   if( op==TK_SELECT ){

    42     return sqlite3ExprAffinity(pExpr->pSelect->pEList->a[0].pExpr);

    43   }

    44 #ifndef SQLITE_OMIT_CAST

    45   if( op==TK_CAST ){

    46     return sqlite3AffinityType(&pExpr->token);

    47   }

    48 #endif

    49   return pExpr->affinity;

    50 }

    51 

    52 /*

    53 ** Return the default collation sequence for the expression pExpr. If

    54 ** there is no default collation type, return 0.

    55 */

    56 CollSeq *sqlite3ExprCollSeq(Parse *pParse, Expr *pExpr){

    57   CollSeq *pColl = 0;

    58   if( pExpr ){

    59     pColl = pExpr->pColl;

    60     if( (pExpr->op==TK_AS || pExpr->op==TK_CAST) && !pColl ){

    61       return sqlite3ExprCollSeq(pParse, pExpr->pLeft);

    62     }

    63   }

    64   if( sqlite3CheckCollSeq(pParse, pColl) ){ 

    65     pColl = 0;

    66   }

    67   return pColl;

    68 }

    69 

    70 /*

    71 ** pExpr is an operand of a comparison operator.  aff2 is the

    72 ** type affinity of the other operand.  This routine returns the

    73 ** type affinity that should be used for the comparison operator.

    74 */

    75 char sqlite3CompareAffinity(Expr *pExpr, char aff2){

    76   char aff1 = sqlite3ExprAffinity(pExpr);

    77   if( aff1 && aff2 ){

    78     /* Both sides of the comparison are columns. If one has numeric

    79     ** affinity, use that. Otherwise use no affinity.

    80     */

    81     if( sqlite3IsNumericAffinity(aff1) || sqlite3IsNumericAffinity(aff2) ){

    82       return SQLITE_AFF_NUMERIC;

    83     }else{

    84       return SQLITE_AFF_NONE;

    85     }

    86   }else if( !aff1 && !aff2 ){

    87     /* Neither side of the comparison is a column.  Compare the

    88     ** results directly.

    89     */

    90     return SQLITE_AFF_NONE;

    91   }else{

    92     /* One side is a column, the other is not. Use the columns affinity. */

    93     assert( aff1==0 || aff2==0 );

    94     return (aff1 + aff2);

    95   }

    96 }

    97 

    98 /*

    99 ** pExpr is a comparison operator.  Return the type affinity that should

   100 ** be applied to both operands prior to doing the comparison.

   101 */

   102 static char comparisonAffinity(Expr *pExpr){

   103   char aff;

   104   assert( pExpr->op==TK_EQ || pExpr->op==TK_IN || pExpr->op==TK_LT ||

   105           pExpr->op==TK_GT || pExpr->op==TK_GE || pExpr->op==TK_LE ||

   106           pExpr->op==TK_NE );

   107   assert( pExpr->pLeft );

   108   aff = sqlite3ExprAffinity(pExpr->pLeft);

   109   if( pExpr->pRight ){

   110     aff = sqlite3CompareAffinity(pExpr->pRight, aff);

   111   }

   112   else if( pExpr->pSelect ){

   113     aff = sqlite3CompareAffinity(pExpr->pSelect->pEList->a[0].pExpr, aff);

   114   }

   115   else if( !aff ){

   116     aff = SQLITE_AFF_NUMERIC;

   117   }

   118   return aff;

   119 }

   120 

   121 /*

   122 ** pExpr is a comparison expression, eg. '=', '<', IN(...) etc.

   123 ** idx_affinity is the affinity of an indexed column. Return true

   124 ** if the index with affinity idx_affinity may be used to implement

   125 ** the comparison in pExpr.

   126 */

   127 int sqlite3IndexAffinityOk(Expr *pExpr, char idx_affinity){

   128   char aff = comparisonAffinity(pExpr);

   129   switch( aff ){

   130     case SQLITE_AFF_NONE:

   131       return 1;

   132     case SQLITE_AFF_TEXT:

   133       return idx_affinity==SQLITE_AFF_TEXT;

   134     default:

   135       return sqlite3IsNumericAffinity(idx_affinity);

   136   }

   137 }

   138 

   139 /*

   140 ** Return the P1 value that should be used for a binary comparison

   141 ** opcode (OP_Eq, OP_Ge etc.) used to compare pExpr1 and pExpr2.

   142 ** If jumpIfNull is true, then set the low byte of the returned

   143 ** P1 value to tell the opcode to jump if either expression

   144 ** evaluates to NULL.

   145 */

   146 static int binaryCompareP1(Expr *pExpr1, Expr *pExpr2, int jumpIfNull){

   147   char aff = sqlite3ExprAffinity(pExpr2);

   148   return ((int)sqlite3CompareAffinity(pExpr1, aff))+(jumpIfNull?0x100:0);

   149 }

   150 

   151 /*

   152 ** Return a pointer to the collation sequence that should be used by

   153 ** a binary comparison operator comparing pLeft and pRight.

   154 **

   155 ** If the left hand expression has a collating sequence type, then it is

   156 ** used. Otherwise the collation sequence for the right hand expression

   157 ** is used, or the default (BINARY) if neither expression has a collating

   158 ** type.

   159 */

   160 static CollSeq* binaryCompareCollSeq(Parse *pParse, Expr *pLeft, Expr *pRight){

   161   CollSeq *pColl = sqlite3ExprCollSeq(pParse, pLeft);

   162   if( !pColl ){

   163     pColl = sqlite3ExprCollSeq(pParse, pRight);

   164   }

   165   return pColl;

   166 }

   167 

   168 /*

   169 ** Generate code for a comparison operator.

   170 */

   171 static int codeCompare(

   172   Parse *pParse,    /* The parsing (and code generating) context */

   173   Expr *pLeft,      /* The left operand */

   174   Expr *pRight,     /* The right operand */

   175   int opcode,       /* The comparison opcode */

   176   int dest,         /* Jump here if true.  */

   177   int jumpIfNull    /* If true, jump if either operand is NULL */

   178 ){

   179   int p1 = binaryCompareP1(pLeft, pRight, jumpIfNull);

   180   CollSeq *p3 = binaryCompareCollSeq(pParse, pLeft, pRight);

   181   return sqlite3VdbeOp3(pParse->pVdbe, opcode, p1, dest, (void*)p3, P3_COLLSEQ);

   182 }

   183 

   184 /*

   185 ** Construct a new expression node and return a pointer to it.  Memory

   186 ** for this node is obtained from sqliteMalloc().  The calling function

   187 ** is responsible for making sure the node eventually gets freed.

   188 */

   189 Expr *sqlite3Expr(int op, Expr *pLeft, Expr *pRight, const Token *pToken){

   190   Expr *pNew;

   191   pNew = sqliteMalloc( sizeof(Expr) );

   192   if( pNew==0 ){

   193     /* When malloc fails, delete pLeft and pRight. Expressions passed to 

   194     ** this function must always be allocated with sqlite3Expr() for this 

   195     ** reason. 

   196     */

   197     sqlite3ExprDelete(pLeft);

   198     sqlite3ExprDelete(pRight);

   199     return 0;

   200   }

   201   pNew->op = op;

   202   pNew->pLeft = pLeft;

   203   pNew->pRight = pRight;

   204   pNew->iAgg = -1;

   205   if( pToken ){

   206     assert( pToken->dyn==0 );

   207     pNew->span = pNew->token = *pToken;

   208   }else if( pLeft && pRight ){

   209     sqlite3ExprSpan(pNew, &pLeft->span, &pRight->span);

   210   }

   211   return pNew;

   212 }

   213 

   214 /*

   215 ** Works like sqlite3Expr() but frees its pLeft and pRight arguments

   216 ** if it fails due to a malloc problem.

   217 */

   218 Expr *sqlite3ExprOrFree(int op, Expr *pLeft, Expr *pRight, const Token *pToken){

   219   Expr *pNew = sqlite3Expr(op, pLeft, pRight, pToken);

   220   if( pNew==0 ){

   221     sqlite3ExprDelete(pLeft);

   222     sqlite3ExprDelete(pRight);

   223   }

   224   return pNew;

   225 }

   226 

   227 /*

   228 ** When doing a nested parse, you can include terms in an expression

   229 ** that look like this:   #0 #1 #2 ...  These terms refer to elements

   230 ** on the stack.  "#0" means the top of the stack.

   231 ** "#1" means the next down on the stack.  And so forth.

   232 **

   233 ** This routine is called by the parser to deal with on of those terms.

   234 ** It immediately generates code to store the value in a memory location.

   235 ** The returns an expression that will code to extract the value from

   236 ** that memory location as needed.

   237 */

   238 Expr *sqlite3RegisterExpr(Parse *pParse, Token *pToken){

   239   Vdbe *v = pParse->pVdbe;

   240   Expr *p;

   241   int depth;

   242   if( pParse->nested==0 ){

   243     sqlite3ErrorMsg(pParse, "near \"%T\": syntax error", pToken);

   244     return 0;

   245   }

   246   if( v==0 ) return 0;

   247   p = sqlite3Expr(TK_REGISTER, 0, 0, pToken);

   248   if( p==0 ){

   249     return 0;  /* Malloc failed */

   250   }

   251   depth = atoi((char*)&pToken->z[1]);

   252   p->iTable = pParse->nMem++;

   253   sqlite3VdbeAddOp(v, OP_Dup, depth, 0);

   254   sqlite3VdbeAddOp(v, OP_MemStore, p->iTable, 1);

   255   return p;

   256 }

   257 

   258 /*

   259 ** Join two expressions using an AND operator.  If either expression is

   260 ** NULL, then just return the other expression.

   261 */

   262 Expr *sqlite3ExprAnd(Expr *pLeft, Expr *pRight){

   263   if( pLeft==0 ){

   264     return pRight;

   265   }else if( pRight==0 ){

   266     return pLeft;

   267   }else{

   268     return sqlite3Expr(TK_AND, pLeft, pRight, 0);

   269   }

   270 }

   271 

   272 /*

   273 ** Set the Expr.span field of the given expression to span all

   274 ** text between the two given tokens.

   275 */

   276 void sqlite3ExprSpan(Expr *pExpr, Token *pLeft, Token *pRight){

   277   assert( pRight!=0 );

   278   assert( pLeft!=0 );

   279   if( !sqlite3MallocFailed() && pRight->z && pLeft->z ){

   280     assert( pLeft->dyn==0 || pLeft->z[pLeft->n]==0 );

   281     if( pLeft->dyn==0 && pRight->dyn==0 ){

   282       pExpr->span.z = pLeft->z;

   283       pExpr->span.n = pRight->n + (pRight->z - pLeft->z);

   284     }else{

   285       pExpr->span.z = 0;

   286     }

   287   }

   288 }

   289 

   290 /*

   291 ** Construct a new expression node for a function with multiple

   292 ** arguments.

   293 */

   294 Expr *sqlite3ExprFunction(ExprList *pList, Token *pToken){

   295   Expr *pNew;

   296   assert( pToken );

   297   pNew = sqliteMalloc( sizeof(Expr) );

   298   if( pNew==0 ){

   299     sqlite3ExprListDelete(pList); /* Avoid leaking memory when malloc fails */

   300     return 0;

   301   }

   302   pNew->op = TK_FUNCTION;

   303   pNew->pList = pList;

   304   assert( pToken->dyn==0 );

   305   pNew->token = *pToken;

   306   pNew->span = pNew->token;

   307   return pNew;

   308 }

   309 

   310 /*

   311 ** Assign a variable number to an expression that encodes a wildcard

   312 ** in the original SQL statement.  

   313 **

   314 ** Wildcards consisting of a single "?" are assigned the next sequential

   315 ** variable number.

   316 **

   317 ** Wildcards of the form "?nnn" are assigned the number "nnn".  We make

   318 ** sure "nnn" is not too be to avoid a denial of service attack when

   319 ** the SQL statement comes from an external source.

   320 **

   321 ** Wildcards of the form ":aaa" or "$aaa" are assigned the same number

   322 ** as the previous instance of the same wildcard.  Or if this is the first

   323 ** instance of the wildcard, the next sequenial variable number is

   324 ** assigned.

   325 */

   326 void sqlite3ExprAssignVarNumber(Parse *pParse, Expr *pExpr){

   327   Token *pToken;

   328   if( pExpr==0 ) return;

   329   pToken = &pExpr->token;

   330   assert( pToken->n>=1 );

   331   assert( pToken->z!=0 );

   332   assert( pToken->z[0]!=0 );

   333   if( pToken->n==1 ){

   334     /* Wildcard of the form "?".  Assign the next variable number */

   335     pExpr->iTable = ++pParse->nVar;

   336   }else if( pToken->z[0]=='?' ){

   337     /* Wildcard of the form "?nnn".  Convert "nnn" to an integer and

   338     ** use it as the variable number */

   339     int i;

   340     pExpr->iTable = i = atoi((char*)&pToken->z[1]);

   341     if( i<1 || i>SQLITE_MAX_VARIABLE_NUMBER ){

   342       sqlite3ErrorMsg(pParse, "variable number must be between ?1 and ?%d",

   343           SQLITE_MAX_VARIABLE_NUMBER);

   344     }

   345     if( i>pParse->nVar ){

   346       pParse->nVar = i;

   347     }

   348   }else{

   349     /* Wildcards of the form ":aaa" or "$aaa".  Reuse the same variable

   350     ** number as the prior appearance of the same name, or if the name

   351     ** has never appeared before, reuse the same variable number

   352     */

   353     int i, n;

   354     n = pToken->n;

   355     for(i=0; i<pParse->nVarExpr; i++){

   356       Expr *pE;

   357       if( (pE = pParse->apVarExpr[i])!=0

   358           && pE->token.n==n

   359           && memcmp(pE->token.z, pToken->z, n)==0 ){

   360         pExpr->iTable = pE->iTable;

   361         break;

   362       }

   363     }

   364     if( i>=pParse->nVarExpr ){

   365       pExpr->iTable = ++pParse->nVar;

   366       if( pParse->nVarExpr>=pParse->nVarExprAlloc-1 ){

   367         pParse->nVarExprAlloc += pParse->nVarExprAlloc + 10;

   368         sqliteReallocOrFree((void**)&pParse->apVarExpr,

   369                        pParse->nVarExprAlloc*sizeof(pParse->apVarExpr[0]) );

   370       }

   371       if( !sqlite3MallocFailed() ){

   372         assert( pParse->apVarExpr!=0 );

   373         pParse->apVarExpr[pParse->nVarExpr++] = pExpr;

   374       }

   375     }

   376   } 

   377 }

   378 

   379 /*

   380 ** Recursively delete an expression tree.

   381 */

   382 void sqlite3ExprDelete(Expr *p){

   383   if( p==0 ) return;

   384   if( p->span.dyn ) sqliteFree((char*)p->span.z);

   385   if( p->token.dyn ) sqliteFree((char*)p->token.z);

   386   sqlite3ExprDelete(p->pLeft);

   387   sqlite3ExprDelete(p->pRight);

   388   sqlite3ExprListDelete(p->pList);

   389   sqlite3SelectDelete(p->pSelect);

   390   sqliteFree(p);

   391 }

   392 

   393 /*

   394 ** The Expr.token field might be a string literal that is quoted.

   395 ** If so, remove the quotation marks.

   396 */

   397 void sqlite3DequoteExpr(Expr *p){

   398   if( ExprHasAnyProperty(p, EP_Dequoted) ){

   399     return;

   400   }

   401   ExprSetProperty(p, EP_Dequoted);

   402   if( p->token.dyn==0 ){

   403     sqlite3TokenCopy(&p->token, &p->token);

   404   }

   405   sqlite3Dequote((char*)p->token.z);

   406 }

   407 

   408 

   409 /*

   410 ** The following group of routines make deep copies of expressions,

   411 ** expression lists, ID lists, and select statements.  The copies can

   412 ** be deleted (by being passed to their respective ...Delete() routines)

   413 ** without effecting the originals.

   414 **

   415 ** The expression list, ID, and source lists return by sqlite3ExprListDup(),

   416 ** sqlite3IdListDup(), and sqlite3SrcListDup() can not be further expanded 

   417 ** by subsequent calls to sqlite*ListAppend() routines.

   418 **

   419 ** Any tables that the SrcList might point to are not duplicated.

   420 */

   421 Expr *sqlite3ExprDup(Expr *p){

   422   Expr *pNew;

   423   if( p==0 ) return 0;

   424   pNew = sqliteMallocRaw( sizeof(*p) );

   425   if( pNew==0 ) return 0;

   426   memcpy(pNew, p, sizeof(*pNew));

   427   if( p->token.z!=0 ){

   428     pNew->token.z = (u8*)sqliteStrNDup((char*)p->token.z, p->token.n);

   429     pNew->token.dyn = 1;

   430   }else{

   431     assert( pNew->token.z==0 );

   432   }

   433   pNew->span.z = 0;

   434   pNew->pLeft = sqlite3ExprDup(p->pLeft);

   435   pNew->pRight = sqlite3ExprDup(p->pRight);

   436   pNew->pList = sqlite3ExprListDup(p->pList);

   437   pNew->pSelect = sqlite3SelectDup(p->pSelect);

   438   pNew->pTab = p->pTab;

   439   return pNew;

   440 }

   441 void sqlite3TokenCopy(Token *pTo, Token *pFrom){

   442   if( pTo->dyn ) sqliteFree((char*)pTo->z);

   443   if( pFrom->z ){

   444     pTo->n = pFrom->n;

   445     pTo->z = (u8*)sqliteStrNDup((char*)pFrom->z, pFrom->n);

   446     pTo->dyn = 1;

   447   }else{

   448     pTo->z = 0;

   449   }

   450 }

   451 ExprList *sqlite3ExprListDup(ExprList *p){

   452   ExprList *pNew;

   453   struct ExprList_item *pItem, *pOldItem;

   454   int i;

   455   if( p==0 ) return 0;

   456   pNew = sqliteMalloc( sizeof(*pNew) );

   457   if( pNew==0 ) return 0;

   458   pNew->nExpr = pNew->nAlloc = p->nExpr;

   459   pNew->a = pItem = sqliteMalloc( p->nExpr*sizeof(p->a[0]) );

   460   if( pItem==0 ){

   461     sqliteFree(pNew);

   462     return 0;

   463   } 

   464   pOldItem = p->a;

   465   for(i=0; i<p->nExpr; i++, pItem++, pOldItem++){

   466     Expr *pNewExpr, *pOldExpr;

   467     pItem->pExpr = pNewExpr = sqlite3ExprDup(pOldExpr = pOldItem->pExpr);

   468     if( pOldExpr->span.z!=0 && pNewExpr ){

   469       /* Always make a copy of the span for top-level expressions in the

   470       ** expression list.  The logic in SELECT processing that determines

   471       ** the names of columns in the result set needs this information */

   472       sqlite3TokenCopy(&pNewExpr->span, &pOldExpr->span);

   473     }

   474     assert( pNewExpr==0 || pNewExpr->span.z!=0 

   475             || pOldExpr->span.z==0

   476             || sqlite3MallocFailed() );

   477     pItem->zName = sqliteStrDup(pOldItem->zName);

   478     pItem->sortOrder = pOldItem->sortOrder;

   479     pItem->isAgg = pOldItem->isAgg;

   480     pItem->done = 0;

   481   }

   482   return pNew;

   483 }

   484 

   485 /*

   486 ** If cursors, triggers, views and subqueries are all omitted from

   487 ** the build, then none of the following routines, except for 

   488 ** sqlite3SelectDup(), can be called. sqlite3SelectDup() is sometimes

   489 ** called with a NULL argument.

   490 */

   491 #if !defined(SQLITE_OMIT_VIEW) || !defined(SQLITE_OMIT_TRIGGER) \

   492  || !defined(SQLITE_OMIT_SUBQUERY)

   493 SrcList *sqlite3SrcListDup(SrcList *p){

   494   SrcList *pNew;

   495   int i;

   496   int nByte;

   497   if( p==0 ) return 0;

   498   nByte = sizeof(*p) + (p->nSrc>0 ? sizeof(p->a[0]) * (p->nSrc-1) : 0);

   499   pNew = sqliteMallocRaw( nByte );

   500   if( pNew==0 ) return 0;

   501   pNew->nSrc = pNew->nAlloc = p->nSrc;

   502   for(i=0; i<p->nSrc; i++){

   503     struct SrcList_item *pNewItem = &pNew->a[i];

   504     struct SrcList_item *pOldItem = &p->a[i];

   505     Table *pTab;

   506     pNewItem->zDatabase = sqliteStrDup(pOldItem->zDatabase);

   507     pNewItem->zName = sqliteStrDup(pOldItem->zName);

   508     pNewItem->zAlias = sqliteStrDup(pOldItem->zAlias);

   509     pNewItem->jointype = pOldItem->jointype;

   510     pNewItem->iCursor = pOldItem->iCursor;

   511     pNewItem->isPopulated = pOldItem->isPopulated;

   512     pTab = pNewItem->pTab = pOldItem->pTab;

   513     if( pTab ){

   514       pTab->nRef++;

   515     }

   516     pNewItem->pSelect = sqlite3SelectDup(pOldItem->pSelect);

   517     pNewItem->pOn = sqlite3ExprDup(pOldItem->pOn);

   518     pNewItem->pUsing = sqlite3IdListDup(pOldItem->pUsing);

   519     pNewItem->colUsed = pOldItem->colUsed;

   520   }

   521   return pNew;

   522 }

   523 IdList *sqlite3IdListDup(IdList *p){

   524   IdList *pNew;

   525   int i;

   526   if( p==0 ) return 0;

   527   pNew = sqliteMallocRaw( sizeof(*pNew) );

   528   if( pNew==0 ) return 0;

   529   pNew->nId = pNew->nAlloc = p->nId;

   530   pNew->a = sqliteMallocRaw( p->nId*sizeof(p->a[0]) );

   531   if( pNew->a==0 ){

   532     sqliteFree(pNew);

   533     return 0;

   534   }

   535   for(i=0; i<p->nId; i++){

   536     struct IdList_item *pNewItem = &pNew->a[i];

   537     struct IdList_item *pOldItem = &p->a[i];

   538     pNewItem->zName = sqliteStrDup(pOldItem->zName);

   539     pNewItem->idx = pOldItem->idx;

   540   }

   541   return pNew;

   542 }

   543 Select *sqlite3SelectDup(Select *p){

   544   Select *pNew;

   545   if( p==0 ) return 0;

   546   pNew = sqliteMallocRaw( sizeof(*p) );

   547   if( pNew==0 ) return 0;

   548   pNew->isDistinct = p->isDistinct;

   549   pNew->pEList = sqlite3ExprListDup(p->pEList);

   550   pNew->pSrc = sqlite3SrcListDup(p->pSrc);

   551   pNew->pWhere = sqlite3ExprDup(p->pWhere);

   552   pNew->pGroupBy = sqlite3ExprListDup(p->pGroupBy);

   553   pNew->pHaving = sqlite3ExprDup(p->pHaving);

   554   pNew->pOrderBy = sqlite3ExprListDup(p->pOrderBy);

   555   pNew->op = p->op;

   556   pNew->pPrior = sqlite3SelectDup(p->pPrior);

   557   pNew->pLimit = sqlite3ExprDup(p->pLimit);

   558   pNew->pOffset = sqlite3ExprDup(p->pOffset);

   559   pNew->iLimit = -1;

   560   pNew->iOffset = -1;

   561   pNew->isResolved = p->isResolved;

   562   pNew->isAgg = p->isAgg;

   563   pNew->usesEphm = 0;

   564   pNew->disallowOrderBy = 0;

   565   pNew->pRightmost = 0;

   566   pNew->addrOpenEphm[0] = -1;

   567   pNew->addrOpenEphm[1] = -1;

   568   pNew->addrOpenEphm[2] = -1;

   569   return pNew;

   570 }

   571 #else

   572 Select *sqlite3SelectDup(Select *p){

   573   assert( p==0 );

   574   return 0;

   575 }

   576 #endif

   577 

   578 

   579 /*

   580 ** Add a new element to the end of an expression list.  If pList is

   581 ** initially NULL, then create a new expression list.

   582 */

   583 ExprList *sqlite3ExprListAppend(ExprList *pList, Expr *pExpr, Token *pName){

   584   if( pList==0 ){

   585     pList = sqliteMalloc( sizeof(ExprList) );

   586     if( pList==0 ){

   587       goto no_mem;

   588     }

   589     assert( pList->nAlloc==0 );

   590   }

   591   if( pList->nAlloc<=pList->nExpr ){

   592     struct ExprList_item *a;

   593     int n = pList->nAlloc*2 + 4;

   594     a = sqliteRealloc(pList->a, n*sizeof(pList->a[0]));

   595     if( a==0 ){

   596       goto no_mem;

   597     }

   598     pList->a = a;

   599     pList->nAlloc = n;

   600   }

   601   assert( pList->a!=0 );

   602   if( pExpr || pName ){

   603     struct ExprList_item *pItem = &pList->a[pList->nExpr++];

   604     memset(pItem, 0, sizeof(*pItem));

   605     pItem->zName = sqlite3NameFromToken(pName);

   606     pItem->pExpr = pExpr;

   607   }

   608   return pList;

   609 

   610 no_mem:     

   611   /* Avoid leaking memory if malloc has failed. */

   612   sqlite3ExprDelete(pExpr);

   613   sqlite3ExprListDelete(pList);

   614   return 0;

   615 }

   616 

   617 /*

   618 ** Delete an entire expression list.

   619 */

   620 void sqlite3ExprListDelete(ExprList *pList){

   621   int i;

   622   struct ExprList_item *pItem;

   623   if( pList==0 ) return;

   624   assert( pList->a!=0 || (pList->nExpr==0 && pList->nAlloc==0) );

   625   assert( pList->nExpr<=pList->nAlloc );

   626   for(pItem=pList->a, i=0; i<pList->nExpr; i++, pItem++){

   627     sqlite3ExprDelete(pItem->pExpr);

   628     sqliteFree(pItem->zName);

   629   }

   630   sqliteFree(pList->a);

   631   sqliteFree(pList);

   632 }

   633 

   634 /*

   635 ** Walk an expression tree.  Call xFunc for each node visited.

   636 **

   637 ** The return value from xFunc determines whether the tree walk continues.

   638 ** 0 means continue walking the tree.  1 means do not walk children

   639 ** of the current node but continue with siblings.  2 means abandon

   640 ** the tree walk completely.

   641 **

   642 ** The return value from this routine is 1 to abandon the tree walk

   643 ** and 0 to continue.

   644 **

   645 ** NOTICE:  This routine does *not* descend into subqueries.

   646 */

   647 static int walkExprList(ExprList *, int (*)(void *, Expr*), void *);

   648 static int walkExprTree(Expr *pExpr, int (*xFunc)(void*,Expr*), void *pArg){

   649   int rc;

   650   if( pExpr==0 ) return 0;

   651   rc = (*xFunc)(pArg, pExpr);

   652   if( rc==0 ){

   653     if( walkExprTree(pExpr->pLeft, xFunc, pArg) ) return 1;

   654     if( walkExprTree(pExpr->pRight, xFunc, pArg) ) return 1;

   655     if( walkExprList(pExpr->pList, xFunc, pArg) ) return 1;

   656   }

   657   return rc>1;

   658 }

   659 

   660 /*

   661 ** Call walkExprTree() for every expression in list p.

   662 */

   663 static int walkExprList(ExprList *p, int (*xFunc)(void *, Expr*), void *pArg){

   664   int i;

   665   struct ExprList_item *pItem;

   666   if( !p ) return 0;

   667   for(i=p->nExpr, pItem=p->a; i>0; i--, pItem++){

   668     if( walkExprTree(pItem->pExpr, xFunc, pArg) ) return 1;

   669   }

   670   return 0;

   671 }

   672 

   673 /*

   674 ** Call walkExprTree() for every expression in Select p, not including

   675 ** expressions that are part of sub-selects in any FROM clause or the LIMIT

   676 ** or OFFSET expressions..

   677 */

   678 static int walkSelectExpr(Select *p, int (*xFunc)(void *, Expr*), void *pArg){

   679   walkExprList(p->pEList, xFunc, pArg);

   680   walkExprTree(p->pWhere, xFunc, pArg);

   681   walkExprList(p->pGroupBy, xFunc, pArg);

   682   walkExprTree(p->pHaving, xFunc, pArg);

   683   walkExprList(p->pOrderBy, xFunc, pArg);

   684   return 0;

   685 }

   686 

   687 

   688 /*

   689 ** This routine is designed as an xFunc for walkExprTree().

   690 **

   691 ** pArg is really a pointer to an integer.  If we can tell by looking

   692 ** at pExpr that the expression that contains pExpr is not a constant

   693 ** expression, then set *pArg to 0 and return 2 to abandon the tree walk.

   694 ** If pExpr does does not disqualify the expression from being a constant

   695 ** then do nothing.

   696 **

   697 ** After walking the whole tree, if no nodes are found that disqualify

   698 ** the expression as constant, then we assume the whole expression

   699 ** is constant.  See sqlite3ExprIsConstant() for additional information.

   700 */

   701 static int exprNodeIsConstant(void *pArg, Expr *pExpr){

   702   switch( pExpr->op ){

   703     /* Consider functions to be constant if all their arguments are constant

   704     ** and *pArg==2 */

   705     case TK_FUNCTION:

   706       if( *((int*)pArg)==2 ) return 0;

   707       /* Fall through */

   708     case TK_ID:

   709     case TK_COLUMN:

   710     case TK_DOT:

   711     case TK_AGG_FUNCTION:

   712     case TK_AGG_COLUMN:

   713 #ifndef SQLITE_OMIT_SUBQUERY

   714     case TK_SELECT:

   715     case TK_EXISTS:

   716 #endif

   717       *((int*)pArg) = 0;

   718       return 2;

   719     case TK_IN:

   720       if( pExpr->pSelect ){

   721         *((int*)pArg) = 0;

   722         return 2;

   723       }

   724     default:

   725       return 0;

   726   }

   727 }

   728 

   729 /*

   730 ** Walk an expression tree.  Return 1 if the expression is constant

   731 ** and 0 if it involves variables or function calls.

   732 **

   733 ** For the purposes of this function, a double-quoted string (ex: "abc")

   734 ** is considered a variable but a single-quoted string (ex: 'abc') is

   735 ** a constant.

   736 */

   737 int sqlite3ExprIsConstant(Expr *p){

   738   int isConst = 1;

   739   walkExprTree(p, exprNodeIsConstant, &isConst);

   740   return isConst;

   741 }

   742 

   743 /*

   744 ** Walk an expression tree.  Return 1 if the expression is constant

   745 ** or a function call with constant arguments.  Return and 0 if there

   746 ** are any variables.

   747 **

   748 ** For the purposes of this function, a double-quoted string (ex: "abc")

   749 ** is considered a variable but a single-quoted string (ex: 'abc') is

   750 ** a constant.

   751 */

   752 int sqlite3ExprIsConstantOrFunction(Expr *p){

   753   int isConst = 2;

   754   walkExprTree(p, exprNodeIsConstant, &isConst);

   755   return isConst!=0;

   756 }

   757 

   758 /*

   759 ** If the expression p codes a constant integer that is small enough

   760 ** to fit in a 32-bit integer, return 1 and put the value of the integer

   761 ** in *pValue.  If the expression is not an integer or if it is too big

   762 ** to fit in a signed 32-bit integer, return 0 and leave *pValue unchanged.

   763 */

   764 int sqlite3ExprIsInteger(Expr *p, int *pValue){

   765   switch( p->op ){

   766     case TK_INTEGER: {

   767       if( sqlite3GetInt32((char*)p->token.z, pValue) ){

   768         return 1;

   769       }

   770       break;

   771     }

   772     case TK_UPLUS: {

   773       return sqlite3ExprIsInteger(p->pLeft, pValue);

   774     }

   775     case TK_UMINUS: {

   776       int v;

   777       if( sqlite3ExprIsInteger(p->pLeft, &v) ){

   778         *pValue = -v;

   779         return 1;

   780       }

   781       break;

   782     }

   783     default: break;

   784   }

   785   return 0;

   786 }

   787 

   788 /*

   789 ** Return TRUE if the given string is a row-id column name.

   790 */

   791 int sqlite3IsRowid(const char *z){

   792   if( sqlite3StrICmp(z, "_ROWID_")==0 ) return 1;

   793   if( sqlite3StrICmp(z, "ROWID")==0 ) return 1;

   794   if( sqlite3StrICmp(z, "OID")==0 ) return 1;

   795   return 0;

   796 }

   797 

   798 /*

   799 ** Given the name of a column of the form X.Y.Z or Y.Z or just Z, look up

   800 ** that name in the set of source tables in pSrcList and make the pExpr 

   801 ** expression node refer back to that source column.  The following changes

   802 ** are made to pExpr:

   803 **

   804 **    pExpr->iDb           Set the index in db->aDb[] of the database holding

   805 **                         the table.

   806 **    pExpr->iTable        Set to the cursor number for the table obtained

   807 **                         from pSrcList.

   808 **    pExpr->iColumn       Set to the column number within the table.

   809 **    pExpr->op            Set to TK_COLUMN.

   810 **    pExpr->pLeft         Any expression this points to is deleted

   811 **    pExpr->pRight        Any expression this points to is deleted.

   812 **

   813 ** The pDbToken is the name of the database (the "X").  This value may be

   814 ** NULL meaning that name is of the form Y.Z or Z.  Any available database

   815 ** can be used.  The pTableToken is the name of the table (the "Y").  This

   816 ** value can be NULL if pDbToken is also NULL.  If pTableToken is NULL it

   817 ** means that the form of the name is Z and that columns from any table

   818 ** can be used.

   819 **

   820 ** If the name cannot be resolved unambiguously, leave an error message

   821 ** in pParse and return non-zero.  Return zero on success.

   822 */

   823 static int lookupName(

   824   Parse *pParse,       /* The parsing context */

   825   Token *pDbToken,     /* Name of the database containing table, or NULL */

   826   Token *pTableToken,  /* Name of table containing column, or NULL */

   827   Token *pColumnToken, /* Name of the column. */

   828   NameContext *pNC,    /* The name context used to resolve the name */

   829   Expr *pExpr          /* Make this EXPR node point to the selected column */

   830 ){

   831   char *zDb = 0;       /* Name of the database.  The "X" in X.Y.Z */

   832   char *zTab = 0;      /* Name of the table.  The "Y" in X.Y.Z or Y.Z */

   833   char *zCol = 0;      /* Name of the column.  The "Z" */

   834   int i, j;            /* Loop counters */

   835   int cnt = 0;         /* Number of matching column names */

   836   int cntTab = 0;      /* Number of matching table names */

   837   sqlite3 *db = pParse->db;  /* The database */

   838   struct SrcList_item *pItem;       /* Use for looping over pSrcList items */

   839   struct SrcList_item *pMatch = 0;  /* The matching pSrcList item */

   840   NameContext *pTopNC = pNC;        /* First namecontext in the list */

   841 

   842   assert( pColumnToken && pColumnToken->z ); /* The Z in X.Y.Z cannot be NULL */

   843   zDb = sqlite3NameFromToken(pDbToken);

   844   zTab = sqlite3NameFromToken(pTableToken);

   845   zCol = sqlite3NameFromToken(pColumnToken);

   846   if( sqlite3MallocFailed() ){

   847     goto lookupname_end;

   848   }

   849 

   850   pExpr->iTable = -1;

   851   while( pNC && cnt==0 ){

   852     ExprList *pEList;

   853     SrcList *pSrcList = pNC->pSrcList;

   854 

   855     if( pSrcList ){

   856       for(i=0, pItem=pSrcList->a; i<pSrcList->nSrc; i++, pItem++){

   857         Table *pTab;

   858         int iDb;

   859         Column *pCol;

   860   

   861         pTab = pItem->pTab;

   862         assert( pTab!=0 );

   863         iDb = sqlite3SchemaToIndex(db, pTab->pSchema);

   864         assert( pTab->nCol>0 );

   865         if( zTab ){

   866           if( pItem->zAlias ){

   867             char *zTabName = pItem->zAlias;

   868             if( sqlite3StrICmp(zTabName, zTab)!=0 ) continue;

   869           }else{

   870             char *zTabName = pTab->zName;

   871             if( zTabName==0 || sqlite3StrICmp(zTabName, zTab)!=0 ) continue;

   872             if( zDb!=0 && sqlite3StrICmp(db->aDb[iDb].zName, zDb)!=0 ){

   873               continue;

   874             }

   875           }

   876         }

   877         if( 0==(cntTab++) ){

   878           pExpr->iTable = pItem->iCursor;

   879           pExpr->pSchema = pTab->pSchema;

   880           pMatch = pItem;

   881         }

   882         for(j=0, pCol=pTab->aCol; j<pTab->nCol; j++, pCol++){

   883           if( sqlite3StrICmp(pCol->zName, zCol)==0 ){

   884             const char *zColl = pTab->aCol[j].zColl;

   885             IdList *pUsing;

   886             cnt++;

   887             pExpr->iTable = pItem->iCursor;

   888             pMatch = pItem;

   889             pExpr->pSchema = pTab->pSchema;

   890             /* Substitute the rowid (column -1) for the INTEGER PRIMARY KEY */

   891             pExpr->iColumn = j==pTab->iPKey ? -1 : j;

   892             pExpr->affinity = pTab->aCol[j].affinity;

   893             pExpr->pColl = sqlite3FindCollSeq(db, ENC(db), zColl,-1, 0);

   894             if( pItem->jointype & JT_NATURAL ){

   895               /* If this match occurred in the left table of a natural join,

   896               ** then skip the right table to avoid a duplicate match */

   897               pItem++;

   898               i++;

   899             }

   900             if( (pUsing = pItem->pUsing)!=0 ){

   901               /* If this match occurs on a column that is in the USING clause

   902               ** of a join, skip the search of the right table of the join

   903               ** to avoid a duplicate match there. */

   904               int k;

   905               for(k=0; k<pUsing->nId; k++){

   906                 if( sqlite3StrICmp(pUsing->a[k].zName, zCol)==0 ){

   907                   pItem++;

   908                   i++;

   909                   break;

   910                 }

   911               }

   912             }

   913             break;

   914           }

   915         }

   916       }

   917     }

   918 

   919 #ifndef SQLITE_OMIT_TRIGGER

   920     /* If we have not already resolved the name, then maybe 

   921     ** it is a new.* or old.* trigger argument reference

   922     */

   923     if( zDb==0 && zTab!=0 && cnt==0 && pParse->trigStack!=0 ){

   924       TriggerStack *pTriggerStack = pParse->trigStack;

   925       Table *pTab = 0;

   926       if( pTriggerStack->newIdx != -1 && sqlite3StrICmp("new", zTab) == 0 ){

   927         pExpr->iTable = pTriggerStack->newIdx;

   928         assert( pTriggerStack->pTab );

   929         pTab = pTriggerStack->pTab;

   930       }else if( pTriggerStack->oldIdx != -1 && sqlite3StrICmp("old", zTab)==0 ){

   931         pExpr->iTable = pTriggerStack->oldIdx;

   932         assert( pTriggerStack->pTab );

   933         pTab = pTriggerStack->pTab;

   934       }

   935 

   936       if( pTab ){ 

   937         int iCol;

   938         Column *pCol = pTab->aCol;

   939 

   940         pExpr->pSchema = pTab->pSchema;

   941         cntTab++;

   942         for(iCol=0; iCol < pTab->nCol; iCol++, pCol++) {

   943           if( sqlite3StrICmp(pCol->zName, zCol)==0 ){

   944             const char *zColl = pTab->aCol[iCol].zColl;

   945             cnt++;

   946             pExpr->iColumn = iCol==pTab->iPKey ? -1 : iCol;

   947             pExpr->affinity = pTab->aCol[iCol].affinity;

   948             pExpr->pColl = sqlite3FindCollSeq(db, ENC(db), zColl,-1, 0);

   949             pExpr->pTab = pTab;

   950             break;

   951           }

   952         }

   953       }

   954     }

   955 #endif /* !defined(SQLITE_OMIT_TRIGGER) */

   956 

   957     /*

   958     ** Perhaps the name is a reference to the ROWID

   959     */

   960     if( cnt==0 && cntTab==1 && sqlite3IsRowid(zCol) ){

   961       cnt = 1;

   962       pExpr->iColumn = -1;

   963       pExpr->affinity = SQLITE_AFF_INTEGER;

   964     }

   965 

   966     /*

   967     ** If the input is of the form Z (not Y.Z or X.Y.Z) then the name Z

   968     ** might refer to an result-set alias.  This happens, for example, when

   969     ** we are resolving names in the WHERE clause of the following command:

   970     **

   971     **     SELECT a+b AS x FROM table WHERE x<10;

   972     **

   973     ** In cases like this, replace pExpr with a copy of the expression that

   974     ** forms the result set entry ("a+b" in the example) and return immediately.

   975     ** Note that the expression in the result set should have already been

   976     ** resolved by the time the WHERE clause is resolved.

   977     */

   978     if( cnt==0 && (pEList = pNC->pEList)!=0 && zTab==0 ){

   979       for(j=0; j<pEList->nExpr; j++){

   980         char *zAs = pEList->a[j].zName;

   981         if( zAs!=0 && sqlite3StrICmp(zAs, zCol)==0 ){

   982           assert( pExpr->pLeft==0 && pExpr->pRight==0 );

   983           pExpr->op = TK_AS;

   984           pExpr->iColumn = j;

   985           pExpr->pLeft = sqlite3ExprDup(pEList->a[j].pExpr);

   986           cnt = 1;

   987           assert( zTab==0 && zDb==0 );

   988           goto lookupname_end_2;

   989         }

   990       } 

   991     }

   992 

   993     /* Advance to the next name context.  The loop will exit when either

   994     ** we have a match (cnt>0) or when we run out of name contexts.

   995     */

   996     if( cnt==0 ){

   997       pNC = pNC->pNext;

   998     }

   999   }

  1000 

  1001   /*

  1002   ** If X and Y are NULL (in other words if only the column name Z is

  1003   ** supplied) and the value of Z is enclosed in double-quotes, then

  1004   ** Z is a string literal if it doesn't match any column names.  In that

  1005   ** case, we need to return right away and not make any changes to

  1006   ** pExpr.

  1007   **

  1008   ** Because no reference was made to outer contexts, the pNC->nRef

  1009   ** fields are not changed in any context.

  1010   */

  1011   if( cnt==0 && zTab==0 && pColumnToken->z[0]=='"' ){

  1012     sqliteFree(zCol);

  1013     return 0;

  1014   }

  1015 

  1016   /*

  1017   ** cnt==0 means there was not match.  cnt>1 means there were two or

  1018   ** more matches.  Either way, we have an error.

  1019   */

  1020   if( cnt!=1 ){

  1021     char *z = 0;

  1022     char *zErr;

  1023     zErr = cnt==0 ? "no such column: %s" : "ambiguous column name: %s";

  1024     if( zDb ){

  1025       sqlite3SetString(&z, zDb, ".", zTab, ".", zCol, (char*)0);

  1026     }else if( zTab ){

  1027       sqlite3SetString(&z, zTab, ".", zCol, (char*)0);

  1028     }else{

  1029       z = sqliteStrDup(zCol);

  1030     }

  1031     sqlite3ErrorMsg(pParse, zErr, z);

  1032     sqliteFree(z);

  1033     pTopNC->nErr++;

  1034   }

  1035 

  1036   /* If a column from a table in pSrcList is referenced, then record

  1037   ** this fact in the pSrcList.a[].colUsed bitmask.  Column 0 causes

  1038   ** bit 0 to be set.  Column 1 sets bit 1.  And so forth.  If the

  1039   ** column number is greater than the number of bits in the bitmask

  1040   ** then set the high-order bit of the bitmask.

  1041   */

  1042   if( pExpr->iColumn>=0 && pMatch!=0 ){

  1043     int n = pExpr->iColumn;

  1044     if( n>=sizeof(Bitmask)*8 ){

  1045       n = sizeof(Bitmask)*8-1;

  1046     }

  1047     assert( pMatch->iCursor==pExpr->iTable );

  1048     pMatch->colUsed |= 1<<n;

  1049   }

  1050 

  1051 lookupname_end:

  1052   /* Clean up and return

  1053   */

  1054   sqliteFree(zDb);

  1055   sqliteFree(zTab);

  1056   sqlite3ExprDelete(pExpr->pLeft);

  1057   pExpr->pLeft = 0;

  1058   sqlite3ExprDelete(pExpr->pRight);

  1059   pExpr->pRight = 0;

  1060   pExpr->op = TK_COLUMN;

  1061 lookupname_end_2:

  1062   sqliteFree(zCol);

  1063   if( cnt==1 ){

  1064     assert( pNC!=0 );

  1065     sqlite3AuthRead(pParse, pExpr, pNC->pSrcList);

  1066     if( pMatch && !pMatch->pSelect ){

  1067       pExpr->pTab = pMatch->pTab;

  1068     }

  1069     /* Increment the nRef value on all name contexts from TopNC up to

  1070     ** the point where the name matched. */

  1071     for(;;){

  1072       assert( pTopNC!=0 );

  1073       pTopNC->nRef++;

  1074       if( pTopNC==pNC ) break;

  1075       pTopNC = pTopNC->pNext;

  1076     }

  1077     return 0;

  1078   } else {

  1079     return 1;

  1080   }

  1081 }

  1082 

  1083 /*

  1084 ** This routine is designed as an xFunc for walkExprTree().

  1085 **

  1086 ** Resolve symbolic names into TK_COLUMN operators for the current

  1087 ** node in the expression tree.  Return 0 to continue the search down

  1088 ** the tree or 2 to abort the tree walk.

  1089 **

  1090 ** This routine also does error checking and name resolution for

  1091 ** function names.  The operator for aggregate functions is changed

  1092 ** to TK_AGG_FUNCTION.

  1093 */

  1094 static int nameResolverStep(void *pArg, Expr *pExpr){

  1095   NameContext *pNC = (NameContext*)pArg;

  1096   Parse *pParse;

  1097 

  1098   if( pExpr==0 ) return 1;

  1099   assert( pNC!=0 );

  1100   pParse = pNC->pParse;

  1101 

  1102   if( ExprHasAnyProperty(pExpr, EP_Resolved) ) return 1;

  1103   ExprSetProperty(pExpr, EP_Resolved);

  1104 #ifndef NDEBUG

  1105   if( pNC->pSrcList && pNC->pSrcList->nAlloc>0 ){

  1106     SrcList *pSrcList = pNC->pSrcList;

  1107     int i;

  1108     for(i=0; i<pNC->pSrcList->nSrc; i++){

  1109       assert( pSrcList->a[i].iCursor>=0 && pSrcList->a[i].iCursor<pParse->nTab);

  1110     }

  1111   }

  1112 #endif

  1113   switch( pExpr->op ){

  1114     /* Double-quoted strings (ex: "abc") are used as identifiers if

  1115     ** possible.  Otherwise they remain as strings.  Single-quoted

  1116     ** strings (ex: 'abc') are always string literals.

  1117     */

  1118     case TK_STRING: {

  1119       if( pExpr->token.z[0]=='\'' ) break;

  1120       /* Fall thru into the TK_ID case if this is a double-quoted string */

  1121     }

  1122     /* A lone identifier is the name of a column.

  1123     */

  1124     case TK_ID: {

  1125       lookupName(pParse, 0, 0, &pExpr->token, pNC, pExpr);

  1126       return 1;

  1127     }

  1128   

  1129     /* A table name and column name:     ID.ID

  1130     ** Or a database, table and column:  ID.ID.ID

  1131     */

  1132     case TK_DOT: {

  1133       Token *pColumn;

  1134       Token *pTable;

  1135       Token *pDb;