/*** 2001 September 15**** The author disclaims copyright to this source code.  In place of** a legal notice, here is a blessing:****    May you do good and not evil.**    May you find forgiveness for yourself and forgive others.**    May you share freely, never taking more than you give.***************************************************************************** This file contains routines used for analyzing expressions and** for generating VDBE code that evaluates expressions in SQLite.**** $Id: expr.c,v 1.257 2006/03/17 13:56:34 drh Exp $*/#include "sqliteInt.h"#include <ctype.h>/*** Return the 'affinity' of the expression pExpr if any.**** If pExpr is a column, a reference to a column via an 'AS' alias,** or a sub-select with a column as the return value, then the ** affinity of that column is returned. Otherwise, 0x00 is returned,** indicating no affinity for the expression.**** i.e. the WHERE clause expresssions in the following statements all** have an affinity:**** CREATE TABLE t1(a);** SELECT * FROM t1 WHERE a;** SELECT a AS b FROM t1 WHERE b;** SELECT * FROM t1 WHERE (select a from t1);*/char sqlite3ExprAffinity(Expr *pExpr){  int op = pExpr->op;  if( op==TK_AS ){    return sqlite3ExprAffinity(pExpr->pLeft);  }  if( op==TK_SELECT ){    return sqlite3ExprAffinity(pExpr->pSelect->pEList->a[0].pExpr);  }#ifndef SQLITE_OMIT_CAST  if( op==TK_CAST ){    return sqlite3AffinityType(&pExpr->token);  }#endif  return pExpr->affinity;}/*** Return the default collation sequence for the expression pExpr. If** there is no default collation type, return 0.*/CollSeq *sqlite3ExprCollSeq(Parse *pParse, Expr *pExpr){  CollSeq *pColl = 0;  if( pExpr ){    pColl = pExpr->pColl;    if( (pExpr->op==TK_AS || pExpr->op==TK_CAST) && !pColl ){      return sqlite3ExprCollSeq(pParse, pExpr->pLeft);    }  }  if( sqlite3CheckCollSeq(pParse, pColl) ){     pColl = 0;  }  return pColl;}/*** pExpr is an operand of a comparison operator.  aff2 is the** type affinity of the other operand.  This routine returns the** type affinity that should be used for the comparison operator.*/char sqlite3CompareAffinity(Expr *pExpr, char aff2){  char aff1 = sqlite3ExprAffinity(pExpr);  if( aff1 && aff2 ){    /* Both sides of the comparison are columns. If one has numeric    ** affinity, use that. Otherwise use no affinity.    */    if( sqlite3IsNumericAffinity(aff1) || sqlite3IsNumericAffinity(aff2) ){      return SQLITE_AFF_NUMERIC;    }else{      return SQLITE_AFF_NONE;    }  }else if( !aff1 && !aff2 ){    /* Neither side of the comparison is a column.  Compare the    ** results directly.    */    return SQLITE_AFF_NONE;  }else{    /* One side is a column, the other is not. Use the columns affinity. */    assert( aff1==0 || aff2==0 );    return (aff1 + aff2);  }}/*** pExpr is a comparison operator.  Return the type affinity that should** be applied to both operands prior to doing the comparison.*/static char comparisonAffinity(Expr *pExpr){  char aff;  assert( pExpr->op==TK_EQ || pExpr->op==TK_IN || pExpr->op==TK_LT ||          pExpr->op==TK_GT || pExpr->op==TK_GE || pExpr->op==TK_LE ||          pExpr->op==TK_NE );  assert( pExpr->pLeft );  aff = sqlite3ExprAffinity(pExpr->pLeft);  if( pExpr->pRight ){    aff = sqlite3CompareAffinity(pExpr->pRight, aff);  }  else if( pExpr->pSelect ){    aff = sqlite3CompareAffinity(pExpr->pSelect->pEList->a[0].pExpr, aff);  }  else if( !aff ){    aff = SQLITE_AFF_NUMERIC;  }  return aff;}/*** pExpr is a comparison expression, eg. '=', '<', IN(...) etc.** idx_affinity is the affinity of an indexed column. Return true** if the index with affinity idx_affinity may be used to implement** the comparison in pExpr.*/int sqlite3IndexAffinityOk(Expr *pExpr, char idx_affinity){  char aff = comparisonAffinity(pExpr);  switch( aff ){    case SQLITE_AFF_NONE:      return 1;    case SQLITE_AFF_TEXT:      return idx_affinity==SQLITE_AFF_TEXT;    default:      return sqlite3IsNumericAffinity(idx_affinity);  }}/*** Return the P1 value that should be used for a binary comparison** opcode (OP_Eq, OP_Ge etc.) used to compare pExpr1 and pExpr2.** If jumpIfNull is true, then set the low byte of the returned** P1 value to tell the opcode to jump if either expression** evaluates to NULL.*/static int binaryCompareP1(Expr *pExpr1, Expr *pExpr2, int jumpIfNull){  char aff = sqlite3ExprAffinity(pExpr2);  return ((int)sqlite3CompareAffinity(pExpr1, aff))+(jumpIfNull?0x100:0);}/*** Return a pointer to the collation sequence that should be used by** a binary comparison operator comparing pLeft and pRight.**** If the left hand expression has a collating sequence type, then it is** used. Otherwise the collation sequence for the right hand expression** is used, or the default (BINARY) if neither expression has a collating** type.*/static CollSeq* binaryCompareCollSeq(Parse *pParse, Expr *pLeft, Expr *pRight){  CollSeq *pColl = sqlite3ExprCollSeq(pParse, pLeft);  if( !pColl ){    pColl = sqlite3ExprCollSeq(pParse, pRight);  }  return pColl;}/*** Generate code for a comparison operator.*/static int codeCompare(  Parse *pParse,    /* The parsing (and code generating) context */  Expr *pLeft,      /* The left operand */  Expr *pRight,     /* The right operand */  int opcode,       /* The comparison opcode */  int dest,         /* Jump here if true.  */  int jumpIfNull    /* If true, jump if either operand is NULL */){  int p1 = binaryCompareP1(pLeft, pRight, jumpIfNull);  CollSeq *p3 = binaryCompareCollSeq(pParse, pLeft, pRight);  return sqlite3VdbeOp3(pParse->pVdbe, opcode, p1, dest, (void*)p3, P3_COLLSEQ);}/*** Construct a new expression node and return a pointer to it.  Memory** for this node is obtained from sqliteMalloc().  The calling function** is responsible for making sure the node eventually gets freed.*/Expr *sqlite3Expr(int op, Expr *pLeft, Expr *pRight, const Token *pToken){  Expr *pNew;  pNew = sqliteMalloc( sizeof(Expr) );  if( pNew==0 ){    /* When malloc fails, delete pLeft and pRight. Expressions passed to     ** this function must always be allocated with sqlite3Expr() for this     ** reason.     */    sqlite3ExprDelete(pLeft);    sqlite3ExprDelete(pRight);    return 0;  }  pNew->op = op;  pNew->pLeft = pLeft;  pNew->pRight = pRight;  pNew->iAgg = -1;  if( pToken ){    assert( pToken->dyn==0 );    pNew->span = pNew->token = *pToken;  }else if( pLeft && pRight ){    sqlite3ExprSpan(pNew, &pLeft->span, &pRight->span);  }  return pNew;}/*** When doing a nested parse, you can include terms in an expression** that look like this:   #0 #1 #2 ...  These terms refer to elements** on the stack.  "#0" means the top of the stack.** "#1" means the next down on the stack.  And so forth.**** This routine is called by the parser to deal with on of those terms.** It immediately generates code to store the value in a memory location.** The returns an expression that will code to extract the value from** that memory location as needed.*/Expr *sqlite3RegisterExpr(Parse *pParse, Token *pToken){  Vdbe *v = pParse->pVdbe;  Expr *p;  int depth;  if( pParse->nested==0 ){    sqlite3ErrorMsg(pParse, "near \"%T\": syntax error", pToken);    return 0;  }  if( v==0 ) return 0;  p = sqlite3Expr(TK_REGISTER, 0, 0, pToken);  if( p==0 ){    return 0;  /* Malloc failed */  }  depth = atoi((char*)&pToken->z[1]);  p->iTable = pParse->nMem++;  sqlite3VdbeAddOp(v, OP_Dup, depth, 0);  sqlite3VdbeAddOp(v, OP_MemStore, p->iTable, 1);  return p;}/*** Join two expressions using an AND operator.  If either expression is** NULL, then just return the other expression.*/Expr *sqlite3ExprAnd(Expr *pLeft, Expr *pRight){  if( pLeft==0 ){    return pRight;  }else if( pRight==0 ){    return pLeft;  }else{    return sqlite3Expr(TK_AND, pLeft, pRight, 0);  }}/*** Set the Expr.span field of the given expression to span all** text between the two given tokens.*/void sqlite3ExprSpan(Expr *pExpr, Token *pLeft, Token *pRight){  assert( pRight!=0 );  assert( pLeft!=0 );  if( !sqlite3MallocFailed() && pRight->z && pLeft->z ){    assert( pLeft->dyn==0 || pLeft->z[pLeft->n]==0 );    if( pLeft->dyn==0 && pRight->dyn==0 ){      pExpr->span.z = pLeft->z;      pExpr->span.n = pRight->n + (pRight->z - pLeft->z);    }else{      pExpr->span.z = 0;    }  }}/*** Construct a new expression node for a function with multiple** arguments.*/Expr *sqlite3ExprFunction(ExprList *pList, Token *pToken){  Expr *pNew;  assert( pToken );  pNew = sqliteMalloc( sizeof(Expr) );  if( pNew==0 ){    sqlite3ExprListDelete(pList); /* Avoid leaking memory when malloc fails */    return 0;  }  pNew->op = TK_FUNCTION;  pNew->pList = pList;  assert( pToken->dyn==0 );  pNew->token = *pToken;  pNew->span = pNew->token;  return pNew;}/*** Assign a variable number to an expression that encodes a wildcard** in the original SQL statement.  **** Wildcards consisting of a single "?" are assigned the next sequential** variable number.**** Wildcards of the form "?nnn" are assigned the number "nnn".  We make** sure "nnn" is not too be to avoid a denial of service attack when** the SQL statement comes from an external source.**** Wildcards of the form ":aaa" or "$aaa" are assigned the same number** as the previous instance of the same wildcard.  Or if this is the first** instance of the wildcard, the next sequenial variable number is** assigned.*/void sqlite3ExprAssignVarNumber(Parse *pParse, Expr *pExpr){  Token *pToken;  if( pExpr==0 ) return;  pToken = &pExpr->token;  assert( pToken->n>=1 );  assert( pToken->z!=0 );  assert( pToken->z[0]!=0 );  if( pToken->n==1 ){    /* Wildcard of the form "?".  Assign the next variable number */    pExpr->iTable = ++pParse->nVar;  }else if( pToken->z[0]=='?' ){    /* Wildcard of the form "?nnn".  Convert "nnn" to an integer and    ** use it as the variable number */    int i;    pExpr->iTable = i = atoi((char*)&pToken->z[1]);    if( i<1 || i>SQLITE_MAX_VARIABLE_NUMBER ){      sqlite3ErrorMsg(pParse, "variable number must be between ?1 and ?%d",          SQLITE_MAX_VARIABLE_NUMBER);    }    if( i>pParse->nVar ){      pParse->nVar = i;    }  }else{    /* Wildcards of the form ":aaa" or "$aaa".  Reuse the same variable    ** number as the prior appearance of the same name, or if the name    ** has never appeared before, reuse the same variable number    */    int i, n;    n = pToken->n;    for(i=0; i<pParse->nVarExpr; i++){      Expr *pE;      if( (pE = pParse->apVarExpr[i])!=0          && pE->token.n==n          && memcmp(pE->token.z, pToken->z, n)==0 ){        pExpr->iTable = pE->iTable;        break;      }    }    if( i>=pParse->nVarExpr ){      pExpr->iTable = ++pParse->nVar;      if( pParse->nVarExpr>=pParse->nVarExprAlloc-1 ){        pParse->nVarExprAlloc += pParse->nVarExprAlloc + 10;        sqliteReallocOrFree((void**)&pParse->apVarExpr,                       pParse->nVarExprAlloc*sizeof(pParse->apVarExpr[0]) );      }      if( !sqlite3MallocFailed() ){        assert( pParse->apVarExpr!=0 );        pParse->apVarExpr[pParse->nVarExpr++] = pExpr;      }    }  } }/*** Recursively delete an expression tree.*/void sqlite3ExprDelete(Expr *p){  if( p==0 ) return;  if( p->span.dyn ) sqliteFree((char*)p->span.z);  if( p->token.dyn ) sqliteFree((char*)p->token.z);  sqlite3ExprDelete(p->pLeft);  sqlite3ExprDelete(p->pRight);  sqlite3ExprListDelete(p->pList);  sqlite3SelectDelete(p->pSelect);  sqliteFree(p);}/*** The Expr.token field might be a string literal that is quoted.** If so, remove the quotation marks.*/void sqlite3DequoteExpr(Expr *p){  if( ExprHasAnyProperty(p, EP_Dequoted) ){    return;  }  ExprSetProperty(p, EP_Dequoted);  if( p->token.dyn==0 ){    sqlite3TokenCopy(&p->token, &p->token);  }  sqlite3Dequote((char*)p->token.z);}/*** The following group of routines make deep copies of expressions,** expression lists, ID lists, and select statements.  The copies can** be deleted (by being passed to their respective ...Delete() routines)** without effecting the originals.**** The expression list, ID, and source lists return by sqlite3ExprListDup(),** sqlite3IdListDup(), and sqlite3SrcListDup() can not be further expanded ** by subsequent calls to sqlite*ListAppend() routines.**** Any tables that the SrcList might point to are not duplicated.*/Expr *sqlite3ExprDup(Expr *p){  Expr *pNew;  if( p==0 ) return 0;