**    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.104 2004/01/14 03:12:42 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** 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 *sqliteExpr(int op, Expr *pLeft, Expr *pRight, Token *pToken){
  Expr *pNew;
  pNew = sqliteMalloc( sizeof(Expr) );
  if( pNew==0 ){
    sqliteExprDelete(pLeft);
    sqliteExprDelete(pRight);
    return 0;
  }
  pNew->op = op;
  pNew->pLeft = pLeft;
  pNew->pRight = pRight;
  if( pToken ){
    assert( pToken->dyn==0 );
    pNew->token = *pToken;
    pNew->span = *pToken;
  }else{
    pNew->token.dyn = 0;
    pNew->token.z = 0;
    pNew->token.n = 0;
    if( pLeft && pRight ){
      sqliteExprSpan(pNew, &pLeft->span, &pRight->span);
    }else{
      pNew->span = pNew->token;
    }
  }
  return pNew;
................................................................................
}

/*
** Set the Expr.span field of the given expression to span all
** text between the two given tokens.
*/
void sqliteExprSpan(Expr *pExpr, Token *pLeft, Token *pRight){



  if( pExpr && pRight && pRight->z && pLeft && pLeft->z ){
    if( pLeft->dyn==0 && pRight->dyn==0 ){
      pExpr->span.z = pLeft->z;
      pExpr->span.n = pRight->n + Addr(pRight->z) - Addr(pLeft->z);
    }else{
      pExpr->span.z = 0;
      pExpr->span.n = 0;
      pExpr->span.dyn = 0;
    }
  }
}

/*
** Construct a new expression node for a function with multiple
** arguments.
*/
Expr *sqliteExprFunction(ExprList *pList, Token *pToken){
  Expr *pNew;
  pNew = sqliteMalloc( sizeof(Expr) );
  if( pNew==0 ){
    sqliteExprListDelete(pList);
    return 0;
  }
  pNew->op = TK_FUNCTION;
  pNew->pList = pList;
  pNew->token.dyn = 0;
  if( pToken ){
    assert( pToken->dyn==0 );
    pNew->token = *pToken;
  }else{
    pNew->token.z = 0;
    pNew->token.n = 0;
  }
  pNew->span = pNew->token;
  return pNew;
}

/*
** Recursively delete an expression tree.
*/
void sqliteExprDelete(Expr *p){
  if( p==0 ) return;
  if( p->span.dyn && p->span.z ) sqliteFree((char*)p->span.z);
  if( p->token.dyn && p->token.z ) sqliteFree((char*)p->token.z);
  if( p->pLeft ) sqliteExprDelete(p->pLeft);
  if( p->pRight ) sqliteExprDelete(p->pRight);
  if( p->pList ) sqliteExprListDelete(p->pList);
  if( p->pSelect ) sqliteSelectDelete(p->pSelect);
  sqliteFree(p);
}


/*
** The following group of routines make deep copies of expressions,
** expression lists, ID lists, and select statements.  The copies can
................................................................................
  pNew = sqliteMallocRaw( sizeof(*p) );
  if( pNew==0 ) return 0;
  memcpy(pNew, p, sizeof(*pNew));
  if( p->token.z!=0 ){
    pNew->token.z = sqliteStrDup(p->token.z);
    pNew->token.dyn = 1;
  }else{
    pNew->token.z = 0;
    pNew->token.n = 0;
    pNew->token.dyn = 0;
  }
  pNew->span.z = 0;
  pNew->span.n = 0;
  pNew->span.dyn = 0;
  pNew->pLeft = sqliteExprDup(p->pLeft);
  pNew->pRight = sqliteExprDup(p->pRight);
  pNew->pList = sqliteExprListDup(p->pList);
  pNew->pSelect = sqliteSelectDup(p->pSelect);
  return pNew;
}
void sqliteTokenCopy(Token *pTo, Token *pFrom){
  if( pTo->dyn ) sqliteFree((char*)pTo->z);
  if( pFrom->z ){
    pTo->n = pFrom->n;
    pTo->z = sqliteStrNDup(pFrom->z, pFrom->n);
    pTo->dyn = 1;
  }else{
    pTo->n = 0;
    pTo->z = 0;
    pTo->dyn = 0;
  }
}
ExprList *sqliteExprListDup(ExprList *p){
  ExprList *pNew;
  int i;
  if( p==0 ) return 0;
  pNew = sqliteMalloc( sizeof(*pNew) );
................................................................................
}
SrcList *sqliteSrcListDup(SrcList *p){
  SrcList *pNew;
  int i;
  int nByte;
  if( p==0 ) return 0;
  nByte = sizeof(*p) + (p->nSrc>0 ? sizeof(p->a[0]) * (p->nSrc-1) : 0);
  pNew = sqliteMalloc( nByte );
  if( pNew==0 ) return 0;
  pNew->nSrc = pNew->nAlloc = p->nSrc;
  for(i=0; i<p->nSrc; i++){


    pNew->a[i].zDatabase = sqliteStrDup(p->a[i].zDatabase);
    pNew->a[i].zName = sqliteStrDup(p->a[i].zName);
    pNew->a[i].zAlias = sqliteStrDup(p->a[i].zAlias);
    pNew->a[i].jointype = p->a[i].jointype;
    pNew->a[i].iCursor = p->a[i].iCursor;


    pNew->a[i].pTab = 0;
    pNew->a[i].pSelect = sqliteSelectDup(p->a[i].pSelect);
    pNew->a[i].pOn = sqliteExprDup(p->a[i].pOn);
    pNew->a[i].pUsing = sqliteIdListDup(p->a[i].pUsing);
  }
  return pNew;
}
IdList *sqliteIdListDup(IdList *p){
  IdList *pNew;
  int i;
  if( p==0 ) return 0;
  pNew = sqliteMalloc( sizeof(*pNew) );
  if( pNew==0 ) return 0;
  pNew->nId = pNew->nAlloc = p->nId;
  pNew->a = sqliteMalloc( p->nId*sizeof(p->a[0]) );
  if( pNew->a==0 ) return 0;
  for(i=0; i<p->nId; i++){


    pNew->a[i].zName = sqliteStrDup(p->a[i].zName);
    pNew->a[i].idx = p->a[i].idx;

  }
  return pNew;
}
Select *sqliteSelectDup(Select *p){
  Select *pNew;
  if( p==0 ) return 0;
  pNew = sqliteMalloc( sizeof(*p) );
  if( pNew==0 ) return 0;
  pNew->isDistinct = p->isDistinct;
  pNew->pEList = sqliteExprListDup(p->pEList);
  pNew->pSrc = sqliteSrcListDup(p->pSrc);
  pNew->pWhere = sqliteExprDup(p->pWhere);
  pNew->pGroupBy = sqliteExprListDup(p->pGroupBy);
  pNew->pHaving = sqliteExprDup(p->pHaving);
................................................................................
** initially NULL, then create a new expression list.
*/
ExprList *sqliteExprListAppend(ExprList *pList, Expr *pExpr, Token *pName){
  int i;
  if( pList==0 ){
    pList = sqliteMalloc( sizeof(ExprList) );
    if( pList==0 ){
      sqliteExprDelete(pExpr);
      return 0;
    }
    pList->nAlloc = 0;
  }
  if( pList->nAlloc<=pList->nExpr ){
    struct ExprList_item *a;
    pList->nAlloc = pList->nAlloc*2 + 4;
    a = sqliteRealloc(pList->a, pList->nAlloc*sizeof(pList->a[0]));
    if( a==0 ){
      sqliteExprDelete(pExpr);

      return pList;
    }
    pList->a = a;
  }

  if( pList->a && (pExpr || pName) ){
    i = pList->nExpr++;
    memset(&pList->a[i], 0, sizeof(pList->a[i]));
    pList->a[i].pExpr = pExpr;
    if( pName ){
      sqliteSetNString(&pList->a[i].zName, pName->z, pName->n, 0);
      sqliteDequote(pList->a[i].zName);
    }
  }
  return pList;
}

/*
** Delete an entire expression list.

**    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.105 2004/01/16 15:55:38 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** 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 *sqliteExpr(int op, Expr *pLeft, Expr *pRight, Token *pToken){
  Expr *pNew;
  pNew = sqliteMalloc( sizeof(Expr) );
  if( pNew==0 ){
    /* When malloc fails, we leak memory from pLeft and pRight */

    return 0;
  }
  pNew->op = op;
  pNew->pLeft = pLeft;
  pNew->pRight = pRight;
  if( pToken ){
    assert( pToken->dyn==0 );
    pNew->token = *pToken;
    pNew->span = *pToken;
  }else{
    assert( pNew->token.dyn==0 );
    assert( pNew->token.z==0 );
    assert( pNew->token.n==0 );
    if( pLeft && pRight ){
      sqliteExprSpan(pNew, &pLeft->span, &pRight->span);
    }else{
      pNew->span = pNew->token;
    }
  }
  return pNew;
................................................................................
}

/*
** Set the Expr.span field of the given expression to span all
** text between the two given tokens.
*/
void sqliteExprSpan(Expr *pExpr, Token *pLeft, Token *pRight){
  assert( pRight!=0 );
  assert( pLeft!=0 );
  /* Note: pExpr might be NULL due to a prior malloc failure */
  if( pExpr && pRight->z && pLeft->z ){
    if( pLeft->dyn==0 && pRight->dyn==0 ){
      pExpr->span.z = pLeft->z;
      pExpr->span.n = pRight->n + Addr(pRight->z) - Addr(pLeft->z);
    }else{
      pExpr->span.z = 0;


    }
  }
}

/*
** Construct a new expression node for a function with multiple
** arguments.
*/
Expr *sqliteExprFunction(ExprList *pList, Token *pToken){
  Expr *pNew;
  pNew = sqliteMalloc( sizeof(Expr) );
  if( pNew==0 ){
    /* sqliteExprListDelete(pList); // Leak pList when malloc fails */
    return 0;
  }
  pNew->op = TK_FUNCTION;
  pNew->pList = pList;

  if( pToken ){
    assert( pToken->dyn==0 );
    pNew->token = *pToken;
  }else{
    pNew->token.z = 0;

  }
  pNew->span = pNew->token;
  return pNew;
}

/*
** Recursively delete an expression tree.
*/
void sqliteExprDelete(Expr *p){
  if( p==0 ) return;
  if( p->span.dyn ) sqliteFree((char*)p->span.z);
  if( p->token.dyn ) sqliteFree((char*)p->token.z);
  sqliteExprDelete(p->pLeft);
  sqliteExprDelete(p->pRight);
  sqliteExprListDelete(p->pList);
  sqliteSelectDelete(p->pSelect);
  sqliteFree(p);
}


/*
** The following group of routines make deep copies of expressions,
** expression lists, ID lists, and select statements.  The copies can
................................................................................
  pNew = sqliteMallocRaw( sizeof(*p) );
  if( pNew==0 ) return 0;
  memcpy(pNew, p, sizeof(*pNew));
  if( p->token.z!=0 ){
    pNew->token.z = sqliteStrDup(p->token.z);
    pNew->token.dyn = 1;
  }else{
    assert( pNew->token.z==0 );


  }
  pNew->span.z = 0;


  pNew->pLeft = sqliteExprDup(p->pLeft);
  pNew->pRight = sqliteExprDup(p->pRight);
  pNew->pList = sqliteExprListDup(p->pList);
  pNew->pSelect = sqliteSelectDup(p->pSelect);
  return pNew;
}
void sqliteTokenCopy(Token *pTo, Token *pFrom){
  if( pTo->dyn ) sqliteFree((char*)pTo->z);
  if( pFrom->z ){
    pTo->n = pFrom->n;
    pTo->z = sqliteStrNDup(pFrom->z, pFrom->n);
    pTo->dyn = 1;
  }else{

    pTo->z = 0;

  }
}
ExprList *sqliteExprListDup(ExprList *p){
  ExprList *pNew;
  int i;
  if( p==0 ) return 0;
  pNew = sqliteMalloc( sizeof(*pNew) );
................................................................................
}
SrcList *sqliteSrcListDup(SrcList *p){
  SrcList *pNew;
  int i;
  int nByte;
  if( p==0 ) return 0;
  nByte = sizeof(*p) + (p->nSrc>0 ? sizeof(p->a[0]) * (p->nSrc-1) : 0);
  pNew = sqliteMallocRaw( nByte );
  if( pNew==0 ) return 0;
  pNew->nSrc = pNew->nAlloc = p->nSrc;
  for(i=0; i<p->nSrc; i++){
    struct SrcList_item *pNewItem = &pNew->a[i];
    struct SrcList_item *pOldItem = &p->a[i];
    pNewItem->zDatabase = sqliteStrDup(pOldItem->zDatabase);
    pNewItem->zName = sqliteStrDup(pOldItem->zName);
    pNewItem->zAlias = sqliteStrDup(pOldItem->zAlias);


    pNewItem->jointype = pOldItem->jointype;
    pNewItem->iCursor = pOldItem->iCursor;
    pNewItem->pTab = 0;
    pNewItem->pSelect = sqliteSelectDup(pOldItem->pSelect);
    pNewItem->pOn = sqliteExprDup(pOldItem->pOn);
    pNewItem->pUsing = sqliteIdListDup(pOldItem->pUsing);
  }
  return pNew;
}
IdList *sqliteIdListDup(IdList *p){
  IdList *pNew;
  int i;
  if( p==0 ) return 0;
  pNew = sqliteMallocRaw( sizeof(*pNew) );
  if( pNew==0 ) return 0;
  pNew->nId = pNew->nAlloc = p->nId;
  pNew->a = sqliteMallocRaw( p->nId*sizeof(p->a[0]) );
  if( pNew->a==0 ) return 0;
  for(i=0; i<p->nId; i++){
    struct IdList_item *pNewItem = &pNew->a[i];
    struct IdList_item *pOldItem = &p->a[i];
    pNewItem->zName = sqliteStrDup(pOldItem->zName);

    pNewItem->idx = pOldItem->idx;
  }
  return pNew;
}
Select *sqliteSelectDup(Select *p){
  Select *pNew;
  if( p==0 ) return 0;
  pNew = sqliteMallocRaw( sizeof(*p) );
  if( pNew==0 ) return 0;
  pNew->isDistinct = p->isDistinct;
  pNew->pEList = sqliteExprListDup(p->pEList);
  pNew->pSrc = sqliteSrcListDup(p->pSrc);
  pNew->pWhere = sqliteExprDup(p->pWhere);
  pNew->pGroupBy = sqliteExprListDup(p->pGroupBy);
  pNew->pHaving = sqliteExprDup(p->pHaving);
................................................................................
** initially NULL, then create a new expression list.
*/
ExprList *sqliteExprListAppend(ExprList *pList, Expr *pExpr, Token *pName){
  int i;
  if( pList==0 ){
    pList = sqliteMalloc( sizeof(ExprList) );
    if( pList==0 ){
      /* sqliteExprDelete(pExpr); // Leak memory if malloc fails */
      return 0;
    }
    assert( pList->nAlloc==0 );
  }
  if( pList->nAlloc<=pList->nExpr ){

    pList->nAlloc = pList->nAlloc*2 + 4;
    pList->a = sqliteRealloc(pList->a, pList->nAlloc*sizeof(pList->a[0]));
    if( pList->a==0 ){
      /* sqliteExprDelete(pExpr); // Leak memory if malloc fails */
      pList->nExpr = pList->nAlloc = 0;
      return pList;
    }

  }
  assert( pList->a!=0 );
  if( pExpr || pName ){
    struct ExprList_item *pItem = &pList->a[pList->nExpr++];
    memset(pItem, 0, sizeof(*pItem));
    pItem->pExpr = pExpr;
    if( pName ){
      sqliteSetNString(&pItem->zName, pName->z, pName->n, 0);
      sqliteDequote(pItem->zName);
    }
  }
  return pList;
}

/*
** Delete an entire expression list.

**    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.208 2004/01/15 02:44:03 drh Exp $
*/
#include "config.h"
#include "sqlite.h"
#include "hash.h"
#include "vdbe.h"
#include "parse.h"
#include "btree.h"
................................................................................
  u8 iDb;          /* Index in sqlite.aDb[] of where this index is stored */
  Index *pNext;    /* The next index associated with the same table */
};

/*
** Each token coming out of the lexer is an instance of
** this structure.  Tokens are also used as part of an expression.




*/
struct Token {
  const char *z;      /* Text of the token.  Not NULL-terminated! */
  unsigned dyn  : 1;  /* True for malloced memory, false for static */
  unsigned n    : 31; /* Number of characters in this token */
};

**    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.209 2004/01/16 15:55:38 drh Exp $
*/
#include "config.h"
#include "sqlite.h"
#include "hash.h"
#include "vdbe.h"
#include "parse.h"
#include "btree.h"
................................................................................
  u8 iDb;          /* Index in sqlite.aDb[] of where this index is stored */
  Index *pNext;    /* The next index associated with the same table */
};

/*
** Each token coming out of the lexer is an instance of
** this structure.  Tokens are also used as part of an expression.
**
** Note if Token.z==0 then Token.dyn and Token.n are undefined and
** may contain random values.  Do not make any assuptions about Token.dyn
** and Token.n when Token.z==0.
*/
struct Token {
  const char *z;      /* Text of the token.  Not NULL-terminated! */
  unsigned dyn  : 1;  /* True for malloced memory, false for static */
  unsigned n    : 31; /* Number of characters in this token */
};