/*** 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.320 2007/12/14 15:12:21 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_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;}/*** Set the collating sequence for expression pExpr to be the collating** sequence named by pToken.   Return a pointer to the revised expression.** The collating sequence is marked as "explicit" using the EP_ExpCollate** flag.  An explicit collating sequence will override implicit** collating sequences.*/Expr *sqlite3ExprSetColl(Parse *pParse, Expr *pExpr, Token *pName){  char *zColl = 0;            /* Dequoted name of collation sequence */  CollSeq *pColl;  zColl = sqlite3NameFromToken(pParse->db, pName);  if( pExpr && zColl ){    pColl = sqlite3LocateCollSeq(pParse, zColl, -1);    if( pColl ){      pExpr->pColl = pColl;      pExpr->flags |= EP_ExpCollate;    }  }  sqlite3_free(zColl);  return pExpr;}/*** 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 ){    int op;    pColl = pExpr->pColl;    op = pExpr->op;    if( (op==TK_CAST || op==TK_UPLUS) && !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_NONE;  }  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.**** Argument pRight (but not pLeft) may be a null pointer. In this case,** it is not considered.*/CollSeq *sqlite3BinaryCompareCollSeq(  Parse *pParse,   Expr *pLeft,   Expr *pRight){  CollSeq *pColl;  assert( pLeft );  if( pLeft->flags & EP_ExpCollate ){    assert( pLeft->pColl );    pColl = pLeft->pColl;  }else if( pRight && pRight->flags & EP_ExpCollate ){    assert( pRight->pColl );    pColl = pRight->pColl;  }else{    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 = sqlite3BinaryCompareCollSeq(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 sqlite3_malloc().  The calling function** is responsible for making sure the node eventually gets freed.*/Expr *sqlite3Expr(  sqlite3 *db,            /* Handle for sqlite3DbMallocZero() (may be null) */  int op,                 /* Expression opcode */  Expr *pLeft,            /* Left operand */  Expr *pRight,           /* Right operand */  const Token *pToken     /* Argument token */){  Expr *pNew;  pNew = sqlite3DbMallocZero(db, 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 ){    if( pRight ){      sqlite3ExprSpan(pNew, &pLeft->span, &pRight->span);      if( pRight->flags & EP_ExpCollate ){        pNew->flags |= EP_ExpCollate;        pNew->pColl = pRight->pColl;      }    }    if( pLeft->flags & EP_ExpCollate ){      pNew->flags |= EP_ExpCollate;      pNew->pColl = pLeft->pColl;    }  }  sqlite3ExprSetHeight(pNew);  return pNew;}/*** Works like sqlite3Expr() except that it takes an extra Parse*** argument and notifies the associated connection object if malloc fails.*/Expr *sqlite3PExpr(  Parse *pParse,          /* Parsing context */  int op,                 /* Expression opcode */  Expr *pLeft,            /* Left operand */  Expr *pRight,           /* Right operand */  const Token *pToken     /* Argument token */){  return sqlite3Expr(pParse->db, op, pLeft, pRight, pToken);}/*** 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 sqlite3PExpr(pParse, TK_NULL, 0, 0, 0);  }  if( v==0 ) return 0;  p = sqlite3PExpr(pParse, 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(sqlite3 *db, Expr *pLeft, Expr *pRight){  if( pLeft==0 ){    return pRight;  }else if( pRight==0 ){    return pLeft;  }else{    return sqlite3Expr(db, 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( pExpr && 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(Parse *pParse, ExprList *pList, Token *pToken){  Expr *pNew;  assert( pToken );  pNew = sqlite3DbMallocZero(pParse->db, 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;  sqlite3ExprSetHeight(pNew);  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;  sqlite3 *db = pParse->db;  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;