**    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.372 2008/05/28 13:49:36 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** Return the 'affinity' of the expression pExpr if any.
**
................................................................................
  if( p5 & SQLITE_AFF_MASK ){
    sqlite3ExprCacheAffinityChange(pParse, in1, 1);
    sqlite3ExprCacheAffinityChange(pParse, in2, 1);
  }
  return addr;
}
































































































/*
** 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) */
................................................................................
    }
    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:   #1 #2 ...  These terms refer to registers
** in the virtual machine.  #N is the N-th register.
**
................................................................................
  }
  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.  
**
................................................................................
  testcase( pEList && pEList->nExpr==mx );
  testcase( pEList && pEList->nExpr==mx+1 );
  if( pEList && pEList->nExpr>mx ){
    sqlite3ErrorMsg(pParse, "too many columns in %s", zObject);
  }
}

/* The following three functions, heightOfExpr(), heightOfExprList()
** and heightOfSelect(), are used to determine the maximum height
** of any expression tree referenced by the structure passed as the
** first argument.
**
** If this maximum height is greater than the current value pointed
** to by pnHeight, the second parameter, then set *pnHeight to that
** value.
*/
#if SQLITE_MAX_EXPR_DEPTH>0
static void heightOfExpr(Expr *p, int *pnHeight){
  if( p ){
    if( p->nHeight>*pnHeight ){
      *pnHeight = p->nHeight;
    }
  }
}
static void heightOfExprList(ExprList *p, int *pnHeight){
  if( p ){
    int i;
    for(i=0; i<p->nExpr; i++){
      heightOfExpr(p->a[i].pExpr, pnHeight);
    }
  }
}
static void heightOfSelect(Select *p, int *pnHeight){
  if( p ){
    heightOfExpr(p->pWhere, pnHeight);
    heightOfExpr(p->pHaving, pnHeight);
    heightOfExpr(p->pLimit, pnHeight);
    heightOfExpr(p->pOffset, pnHeight);
    heightOfExprList(p->pEList, pnHeight);
    heightOfExprList(p->pGroupBy, pnHeight);
    heightOfExprList(p->pOrderBy, pnHeight);
    heightOfSelect(p->pPrior, pnHeight);
  }
}
#endif /* SQLITE_MAX_EXPR_DEPTH>0 */

/*
** Set the Expr.nHeight variable in the structure passed as an 
** argument. An expression with no children, Expr.pList or 
** Expr.pSelect member has a height of 1. Any other expression
** has a height equal to the maximum height of any other 
** referenced Expr plus one.
*/
#if SQLITE_MAX_EXPR_DEPTH>0
void sqlite3ExprSetHeight(Expr *p){
  int nHeight = 0;
  heightOfExpr(p->pLeft, &nHeight);
  heightOfExpr(p->pRight, &nHeight);
  heightOfExprList(p->pList, &nHeight);
  heightOfSelect(p->pSelect, &nHeight);
  p->nHeight = nHeight + 1;
}
#endif /* SQLITE_MAX_EXPR_DEPTH>0 */

/*
** Return the maximum height of any expression tree referenced
** by the select statement passed as an argument.
*/
#if SQLITE_MAX_EXPR_DEPTH>0
int sqlite3SelectExprHeight(Select *p){
  int nHeight = 0;
  heightOfSelect(p, &nHeight);
  return nHeight;
}
#endif /* SQLITE_MAX_EXPR_DEPTH>0 */

/*
** Delete an entire expression list.
*/
void sqlite3ExprListDelete(ExprList *pList){
  int i;
  struct ExprList_item *pItem;
  if( pList==0 ) return;
................................................................................
  Expr *pExpr             /* The expression to be analyzed. */
){
  int savedHasAgg;

  if( pExpr==0 ) return 0;
#if SQLITE_MAX_EXPR_DEPTH>0
  {
    int mxDepth = pNC->pParse->db->aLimit[SQLITE_LIMIT_EXPR_DEPTH];
    if( (pExpr->nHeight+pNC->pParse->nHeight)>mxDepth ){
      sqlite3ErrorMsg(pNC->pParse, 
         "Expression tree is too large (maximum depth %d)", mxDepth
      );
      return 1;
    }
    pNC->pParse->nHeight += pExpr->nHeight;
  }
#endif
  savedHasAgg = pNC->hasAgg;
  pNC->hasAgg = 0;

**    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.373 2008/06/05 16:47:39 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** Return the 'affinity' of the expression pExpr if any.
**
................................................................................
  if( p5 & SQLITE_AFF_MASK ){
    sqlite3ExprCacheAffinityChange(pParse, in1, 1);
    sqlite3ExprCacheAffinityChange(pParse, in2, 1);
  }
  return addr;
}

#if SQLITE_MAX_EXPR_DEPTH>0
/*
** Check that argument nHeight is less than or equal to the maximum
** expression depth allowed. If it is not, leave an error message in
** pParse.
*/
static int checkExprHeight(Parse *pParse, int nHeight){
  int rc = SQLITE_OK;
  int mxHeight = pParse->db->aLimit[SQLITE_LIMIT_EXPR_DEPTH];
  if( nHeight>mxHeight ){
    sqlite3ErrorMsg(pParse, 
       "Expression tree is too large (maximum depth %d)", mxHeight
    );
    rc = SQLITE_ERROR;
  }
  return rc;
}

/* The following three functions, heightOfExpr(), heightOfExprList()
** and heightOfSelect(), are used to determine the maximum height
** of any expression tree referenced by the structure passed as the
** first argument.
**
** If this maximum height is greater than the current value pointed
** to by pnHeight, the second parameter, then set *pnHeight to that
** value.
*/
static void heightOfExpr(Expr *p, int *pnHeight){
  if( p ){
    if( p->nHeight>*pnHeight ){
      *pnHeight = p->nHeight;
    }
  }
}
static void heightOfExprList(ExprList *p, int *pnHeight){
  if( p ){
    int i;
    for(i=0; i<p->nExpr; i++){
      heightOfExpr(p->a[i].pExpr, pnHeight);
    }
  }
}
static void heightOfSelect(Select *p, int *pnHeight){
  if( p ){
    heightOfExpr(p->pWhere, pnHeight);
    heightOfExpr(p->pHaving, pnHeight);
    heightOfExpr(p->pLimit, pnHeight);
    heightOfExpr(p->pOffset, pnHeight);
    heightOfExprList(p->pEList, pnHeight);
    heightOfExprList(p->pGroupBy, pnHeight);
    heightOfExprList(p->pOrderBy, pnHeight);
    heightOfSelect(p->pPrior, pnHeight);
  }
}

/*
** Set the Expr.nHeight variable in the structure passed as an 
** argument. An expression with no children, Expr.pList or 
** Expr.pSelect member has a height of 1. Any other expression
** has a height equal to the maximum height of any other 
** referenced Expr plus one.
*/
static void exprSetHeight(Expr *p){
  int nHeight = 0;
  heightOfExpr(p->pLeft, &nHeight);
  heightOfExpr(p->pRight, &nHeight);
  heightOfExprList(p->pList, &nHeight);
  heightOfSelect(p->pSelect, &nHeight);
  p->nHeight = nHeight + 1;
}

/*
** Set the Expr.nHeight variable using the exprSetHeight() function. If
** the height is greater than the maximum allowed expression depth,
** leave an error in pParse.
*/
void sqlite3ExprSetHeight(Parse *pParse, Expr *p){
  exprSetHeight(p);
  checkExprHeight(pParse, p->nHeight);
}

/*
** Return the maximum height of any expression tree referenced
** by the select statement passed as an argument.
*/
int sqlite3SelectExprHeight(Select *p){
  int nHeight = 0;
  heightOfSelect(p, &nHeight);
  return nHeight;
}
#else
  #define checkExprHeight(x,y)
  #define exprSetHeight(y)
#endif /* SQLITE_MAX_EXPR_DEPTH>0 */

/*
** 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) */
................................................................................
    }
    if( pLeft->flags & EP_ExpCollate ){
      pNew->flags |= EP_ExpCollate;
      pNew->pColl = pLeft->pColl;
    }
  }

  exprSetHeight(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 */
){
  Expr *p = sqlite3Expr(pParse->db, op, pLeft, pRight, pToken);
  if( p ){
    checkExprHeight(pParse, p->nHeight);
  }
  return p;
}

/*
** When doing a nested parse, you can include terms in an expression
** that look like this:   #1 #2 ...  These terms refer to registers
** in the virtual machine.  #N is the N-th register.
**
................................................................................
  }
  pNew->op = TK_FUNCTION;
  pNew->pList = pList;
  assert( pToken->dyn==0 );
  pNew->token = *pToken;
  pNew->span = pNew->token;

  sqlite3ExprSetHeight(pParse, pNew);
  return pNew;
}

/*
** Assign a variable number to an expression that encodes a wildcard
** in the original SQL statement.  
**
................................................................................
  testcase( pEList && pEList->nExpr==mx );
  testcase( pEList && pEList->nExpr==mx+1 );
  if( pEList && pEList->nExpr>mx ){
    sqlite3ErrorMsg(pParse, "too many columns in %s", zObject);
  }
}






































































/*
** Delete an entire expression list.
*/
void sqlite3ExprListDelete(ExprList *pList){
  int i;
  struct ExprList_item *pItem;
  if( pList==0 ) return;
................................................................................
  Expr *pExpr             /* The expression to be analyzed. */
){
  int savedHasAgg;

  if( pExpr==0 ) return 0;
#if SQLITE_MAX_EXPR_DEPTH>0
  {
    if( checkExprHeight(pNC->pParse, pExpr->nHeight + pNC->pParse->nHeight) ){




      return 1;
    }
    pNC->pParse->nHeight += pExpr->nHeight;
  }
#endif
  savedHasAgg = pNC->hasAgg;
  pNC->hasAgg = 0;

**
*************************************************************************
** This file contains SQLite's grammar for SQL.  Process this file
** using the lemon parser generator to generate C code that runs
** the parser.  Lemon will also generate a header file containing
** numeric codes for all of the tokens.
**
** @(#) $Id: parse.y,v 1.243 2008/04/17 20:59:38 drh Exp $
*/

// All token codes are small integers with #defines that begin with "TK_"
%token_prefix TK_

// The type of the data attached to each token is Token.  This is also the
// default type for non-terminals.
................................................................................
  %type in_op {int}
  in_op(A) ::= IN.      {A = 0;}
  in_op(A) ::= NOT IN.  {A = 1;}
  expr(A) ::= expr(X) in_op(N) LP exprlist(Y) RP(E). [IN] {
    A = sqlite3PExpr(pParse, TK_IN, X, 0, 0);
    if( A ){
      A->pList = Y;
      sqlite3ExprSetHeight(A);
    }else{
      sqlite3ExprListDelete(Y);
    }
    if( N ) A = sqlite3PExpr(pParse, TK_NOT, A, 0, 0);
    sqlite3ExprSpan(A,&X->span,&E);
  }
  expr(A) ::= LP(B) select(X) RP(E). {
    A = sqlite3PExpr(pParse, TK_SELECT, 0, 0, 0);
    if( A ){
      A->pSelect = X;
      sqlite3ExprSetHeight(A);
    }else{
      sqlite3SelectDelete(X);
    }
    sqlite3ExprSpan(A,&B,&E);
  }
  expr(A) ::= expr(X) in_op(N) LP select(Y) RP(E).  [IN] {
    A = sqlite3PExpr(pParse, TK_IN, X, 0, 0);
    if( A ){
      A->pSelect = Y;
      sqlite3ExprSetHeight(A);
    }else{
      sqlite3SelectDelete(Y);
    }
    if( N ) A = sqlite3PExpr(pParse, TK_NOT, A, 0, 0);
    sqlite3ExprSpan(A,&X->span,&E);
  }
  expr(A) ::= expr(X) in_op(N) nm(Y) dbnm(Z). [IN] {
    SrcList *pSrc = sqlite3SrcListAppend(pParse->db, 0,&Y,&Z);
    A = sqlite3PExpr(pParse, TK_IN, X, 0, 0);
    if( A ){
      A->pSelect = sqlite3SelectNew(pParse, 0,pSrc,0,0,0,0,0,0,0);
      sqlite3ExprSetHeight(A);
    }else{
      sqlite3SrcListDelete(pSrc);
    }
    if( N ) A = sqlite3PExpr(pParse, TK_NOT, A, 0, 0);
    sqlite3ExprSpan(A,&X->span,Z.z?&Z:&Y);
  }
  expr(A) ::= EXISTS(B) LP select(Y) RP(E). {
    Expr *p = A = sqlite3PExpr(pParse, TK_EXISTS, 0, 0, 0);
    if( p ){
      p->pSelect = Y;
      sqlite3ExprSpan(p,&B,&E);
      sqlite3ExprSetHeight(A);
    }else{
      sqlite3SelectDelete(Y);
    }
  }
%endif SQLITE_OMIT_SUBQUERY

/* CASE expressions */
expr(A) ::= CASE(C) case_operand(X) case_exprlist(Y) case_else(Z) END(E). {
  A = sqlite3PExpr(pParse, TK_CASE, X, Z, 0);
  if( A ){
    A->pList = Y;
    sqlite3ExprSetHeight(A);
  }else{
    sqlite3ExprListDelete(Y);
  }
  sqlite3ExprSpan(A, &C, &E);
}
%type case_exprlist {ExprList*}
%destructor case_exprlist {sqlite3ExprListDelete($$);}

**
*************************************************************************
** This file contains SQLite's grammar for SQL.  Process this file
** using the lemon parser generator to generate C code that runs
** the parser.  Lemon will also generate a header file containing
** numeric codes for all of the tokens.
**
** @(#) $Id: parse.y,v 1.244 2008/06/05 16:47:39 danielk1977 Exp $
*/

// All token codes are small integers with #defines that begin with "TK_"
%token_prefix TK_

// The type of the data attached to each token is Token.  This is also the
// default type for non-terminals.
................................................................................
  %type in_op {int}
  in_op(A) ::= IN.      {A = 0;}
  in_op(A) ::= NOT IN.  {A = 1;}
  expr(A) ::= expr(X) in_op(N) LP exprlist(Y) RP(E). [IN] {
    A = sqlite3PExpr(pParse, TK_IN, X, 0, 0);
    if( A ){
      A->pList = Y;
      sqlite3ExprSetHeight(pParse, A);
    }else{
      sqlite3ExprListDelete(Y);
    }
    if( N ) A = sqlite3PExpr(pParse, TK_NOT, A, 0, 0);
    sqlite3ExprSpan(A,&X->span,&E);
  }
  expr(A) ::= LP(B) select(X) RP(E). {
    A = sqlite3PExpr(pParse, TK_SELECT, 0, 0, 0);
    if( A ){
      A->pSelect = X;
      sqlite3ExprSetHeight(pParse, A);
    }else{
      sqlite3SelectDelete(X);
    }
    sqlite3ExprSpan(A,&B,&E);
  }
  expr(A) ::= expr(X) in_op(N) LP select(Y) RP(E).  [IN] {
    A = sqlite3PExpr(pParse, TK_IN, X, 0, 0);
    if( A ){
      A->pSelect = Y;
      sqlite3ExprSetHeight(pParse, A);
    }else{
      sqlite3SelectDelete(Y);
    }
    if( N ) A = sqlite3PExpr(pParse, TK_NOT, A, 0, 0);
    sqlite3ExprSpan(A,&X->span,&E);
  }
  expr(A) ::= expr(X) in_op(N) nm(Y) dbnm(Z). [IN] {
    SrcList *pSrc = sqlite3SrcListAppend(pParse->db, 0,&Y,&Z);
    A = sqlite3PExpr(pParse, TK_IN, X, 0, 0);
    if( A ){
      A->pSelect = sqlite3SelectNew(pParse, 0,pSrc,0,0,0,0,0,0,0);
      sqlite3ExprSetHeight(pParse, A);
    }else{
      sqlite3SrcListDelete(pSrc);
    }
    if( N ) A = sqlite3PExpr(pParse, TK_NOT, A, 0, 0);
    sqlite3ExprSpan(A,&X->span,Z.z?&Z:&Y);
  }
  expr(A) ::= EXISTS(B) LP select(Y) RP(E). {
    Expr *p = A = sqlite3PExpr(pParse, TK_EXISTS, 0, 0, 0);
    if( p ){
      p->pSelect = Y;
      sqlite3ExprSpan(p,&B,&E);
      sqlite3ExprSetHeight(pParse, A);
    }else{
      sqlite3SelectDelete(Y);
    }
  }
%endif SQLITE_OMIT_SUBQUERY

/* CASE expressions */
expr(A) ::= CASE(C) case_operand(X) case_exprlist(Y) case_else(Z) END(E). {
  A = sqlite3PExpr(pParse, TK_CASE, X, Z, 0);
  if( A ){
    A->pList = Y;
    sqlite3ExprSetHeight(pParse, A);
  }else{
    sqlite3ExprListDelete(Y);
  }
  sqlite3ExprSpan(A, &C, &E);
}
%type case_exprlist {ExprList*}
%destructor case_exprlist {sqlite3ExprListDelete($$);}

**    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.
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.705 2008/05/28 13:49:36 drh Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

/*
** Include the configuration header output by 'configure' if we're using the
** autoconf-based build
................................................................................
  int sqlite3JournalSize(sqlite3_vfs *);
  int sqlite3JournalCreate(sqlite3_file *);
#else
  #define sqlite3JournalSize(pVfs) ((pVfs)->szOsFile)
#endif

#if SQLITE_MAX_EXPR_DEPTH>0
  void sqlite3ExprSetHeight(Expr *);
  int sqlite3SelectExprHeight(Select *);
#else
  #define sqlite3ExprSetHeight(x)
  #define sqlite3SelectExprHeight(x) 0
#endif

u32 sqlite3Get4byte(const u8*);
void sqlite3Put4byte(u8*, u32);

#ifdef SQLITE_SSE

**    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.
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.706 2008/06/05 16:47:39 danielk1977 Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

/*
** Include the configuration header output by 'configure' if we're using the
** autoconf-based build
................................................................................
  int sqlite3JournalSize(sqlite3_vfs *);
  int sqlite3JournalCreate(sqlite3_file *);
#else
  #define sqlite3JournalSize(pVfs) ((pVfs)->szOsFile)
#endif

#if SQLITE_MAX_EXPR_DEPTH>0
  void sqlite3ExprSetHeight(Parse *pParse, Expr *p);
  int sqlite3SelectExprHeight(Select *);
#else
  #define sqlite3ExprSetHeight(x,y)
  #define sqlite3SelectExprHeight(x) 0
#endif

u32 sqlite3Get4byte(const u8*);
void sqlite3Put4byte(u8*, u32);

#ifdef SQLITE_SSE