SQLite

**     COPY
**     VACUUM
**     BEGIN TRANSACTION
**     COMMIT
**     ROLLBACK
**     PRAGMA
**
** $Id: build.c,v 1.94 2002/05/24 02:04:33 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** This routine is called after a single SQL statement has been
** parsed and we want to execute the VDBE code to implement 

    }else{
      sqliteDequote(*pz);
    }
  }
  pList->nId++;
  return pList;
}

/*
** Append a new table name to the given SrcList.  Create a new SrcList if
** need be.  A new entry is created in the SrcList even if pToken is NULL.
**
** A new SrcList is returned, or NULL if malloc() fails.
*/
SrcList *sqliteSrcListAppend(SrcList *pList, Token *pToken){
  if( pList==0 ){
    pList = sqliteMalloc( sizeof(IdList) );
    if( pList==0 ) return 0;
  }
  if( (pList->nSrc & 7)==0 ){
    struct SrcList_item *a;
    a = sqliteRealloc(pList->a, (pList->nSrc+8)*sizeof(pList->a[0]) );
    if( a==0 ){
      sqliteSrcListDelete(pList);
      return 0;
    }
    pList->a = a;
  }
  memset(&pList->a[pList->nSrc], 0, sizeof(pList->a[0]));
  if( pToken ){
    char **pz = &pList->a[pList->nSrc].zName;
    sqliteSetNString(pz, pToken->z, pToken->n, 0);
    if( *pz==0 ){
      sqliteSrcListDelete(pList);
      return 0;
    }else{
      sqliteDequote(*pz);
    }
  }
  pList->nSrc++;
  return pList;
}

/*
** Add an alias to the last identifier on the given identifier list.
*/
void sqliteSrcListAddAlias(SrcList *pList, Token *pToken){
  if( pList && pList->nSrc>0 ){
    int i = pList->nSrc - 1;
    sqliteSetNString(&pList->a[i].zAlias, pToken->z, pToken->n, 0);
    sqliteDequote(pList->a[i].zAlias);
  }
}

/*
** Delete an IdList.
*/
void sqliteIdListDelete(IdList *pList){
  int i;
  if( pList==0 ) return;
  for(i=0; i<pList->nId; i++){
    sqliteFree(pList->a[i].zName);
  }
  sqliteFree(pList->a);
  sqliteFree(pList);
}

/*
** Delete an entire SrcList including all its substructure.
*/
void sqliteSrcListDelete(SrcList *pList){
  int i;
  if( pList==0 ) return;
  for(i=0; i<pList->nSrc; i++){
    sqliteFree(pList->a[i].zName);
    sqliteFree(pList->a[i].zAlias);
    if( pList->a[i].pTab && pList->a[i].pTab->isTransient ){
      sqliteDeleteTable(0, pList->a[i].pTab);
    }
    sqliteSelectDelete(pList->a[i].pSelect);
    sqliteExprDelete(pList->a[i].pOn);
    sqliteIdListDelete(pList->a[i].pUsing);
  }
  sqliteFree(pList->a);
  sqliteFree(pList);
}

/*
** The COPY command is for compatibility with PostgreSQL and specificially

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle DELETE FROM statements.
**
** $Id: delete.c,v 1.36 2002/05/24 02:04:33 drh Exp $
*/
#include "sqliteInt.h"


/*
** Given a table name, find the corresponding table and make sure the
** table is writeable.  Generate an error and return NULL if not.  If

    return 0;      
  }
  return pTab;
}

/*
** Given a table name, check to make sure the table exists, is writable
** and is not a view.  If everything is OK, construct an SrcList holding
** the table and return a pointer to the SrcList.  The calling function
** is responsible for freeing the SrcList when it has finished with it.
** If there is an error, leave a message on pParse->zErrMsg and return
** NULL.
*/
SrcList *sqliteTableTokenToSrcList(Parse *pParse, Token *pTableName){
  Table *pTab;
  SrcList *pTabList;

  pTabList = sqliteSrcListAppend(0, pTableName);
  if( pTabList==0 ) return 0;
  assert( pTabList->nSrc==1 );
  pTab = sqliteTableNameToTable(pParse, pTabList->a[0].zName);
  if( pTab==0 ){
    sqliteSrcListDelete(pTabList);
    return 0;
  }
  pTabList->a[0].pTab = pTab;
  return pTabList;
}

/*
** Process a DELETE FROM statement.
*/
void sqliteDeleteFrom(
  Parse *pParse,         /* The parser context */
  Token *pTableName,     /* The table from which we should delete things */
  Expr *pWhere           /* The WHERE clause.  May be null */
){
  Vdbe *v;               /* The virtual database engine */
  Table *pTab;           /* The table from which records will be deleted */
  char *zTab;            /* Name of the table from which we are deleting */
  SrcList *pTabList;     /* A fake FROM clause holding just pTab */
  int end, addr;         /* A couple addresses of generated code */
  int i;                 /* Loop counter */
  WhereInfo *pWInfo;     /* Information about the WHERE clause */
  Index *pIdx;           /* For looping over indices of the table */
  int base;              /* Index of the first available table cursor */
  sqlite *db;            /* Main database structure */
  int openOp;            /* Opcode used to open a cursor to the table */

      /* Just fire VIEW triggers */
      sqliteViewTriggers(pParse, pTab, pWhere, OE_Replace, 0);
      return;
    }
  }

  /* Locate the table which we want to delete.  This table has to be
  ** put in an SrcList structure because some of the subroutines we
  ** will be calling are designed to work with multiple tables and expect
  ** an SrcList* parameter instead of just a Table* parameter.
  */
  pTabList = sqliteTableTokenToSrcList(pParse, pTableName);
  if( pTabList==0 ) goto delete_from_cleanup;
  assert( pTabList->nSrc==1 );
  pTab = pTabList->a[0].pTab;
  assert( pTab->pSelect==0 );  /* This table is not a view */

  /* Allocate a cursor used to store the old.* data for a trigger.
  */
  if( row_triggers_exist ){ 
    oldIdx = pParse->nTab++;

    sqliteVdbeAddOp(v, OP_ColumnCount, 1, 0);
    sqliteVdbeAddOp(v, OP_ColumnName, 0, 0);
    sqliteVdbeChangeP3(v, -1, "rows deleted", P3_STATIC);
    sqliteVdbeAddOp(v, OP_Callback, 1, 0);
  }

delete_from_cleanup:
  sqliteSrcListDelete(pTabList);
  sqliteExprDelete(pWhere);
  return;
}

/*
** This routine generates VDBE code that causes a single row of a
** single table to be deleted.

**    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.63 2002/05/24 02:04:33 drh Exp $
*/
#include "sqliteInt.h"


/*
** Construct a new expression node and return a pointer to it.  Memory
** for this node is obtained from sqliteMalloc().  The calling function

** be deleted (by being passed to their respective ...Delete() routines)
** without effecting the originals.
**
** Note, however, that the Expr.token.z and Expr.span.z fields point to
** string space that is allocated separately from the expression tree
** itself.  These routines do NOT duplicate that string space.
**
** The expression list, ID, and source lists return by sqliteExprListDup(),
** sqliteIdListDup(), and sqliteSrcListDup() can not be further expanded 
** by subsequent calls to sqlite*ListAppend() routines.
**
** Any tables that the SrcList might point to are not duplicated.
*/
Expr *sqliteExprDup(Expr *p){
  Expr *pNew;
  if( p==0 ) return 0;
  pNew = sqliteMalloc( sizeof(*p) );
  if( pNew==0 ) return 0;
  pNew->op = p->op;

    pNew->a[i].pExpr = sqliteExprDup(p->a[i].pExpr);
    pNew->a[i].zName = sqliteStrDup(p->a[i].zName);
    pNew->a[i].sortOrder = p->a[i].sortOrder;
    pNew->a[i].isAgg = p->a[i].isAgg;
    pNew->a[i].done = 0;
  }
  return pNew;
}
SrcList *sqliteSrcListDup(SrcList *p){
  SrcList *pNew;
  int i;
  if( p==0 ) return 0;
  pNew = sqliteMalloc( sizeof(*pNew) );
  if( pNew==0 ) return 0;
  pNew->nSrc = p->nSrc;
  pNew->a = sqliteMalloc( p->nSrc*sizeof(p->a[0]) );
  if( pNew->a==0 ) return 0;
  for(i=0; i<p->nSrc; i++){
    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].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 = 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);
  pNew->pOrderBy = sqliteExprListDup(p->pOrderBy);
  pNew->op = p->op;
  pNew->pPrior = sqliteSelectDup(p->pPrior);
  pNew->nLimit = p->nLimit;

**
** Unknown columns or tables provoke an error.  The function returns
** the number of errors seen and leaves an error message on pParse->zErrMsg.
*/
int sqliteExprResolveIds(
  Parse *pParse,     /* The parser context */
  int base,          /* VDBE cursor number for first entry in pTabList */
  SrcList *pTabList, /* List of tables used to resolve column names */
  ExprList *pEList,  /* List of expressions used to resolve "AS" */
  Expr *pExpr        /* The expression to be analyzed. */
){
  if( pExpr==0 || pTabList==0 ) return 0;
  assert( base+pTabList->nSrc<=pParse->nTab );
  switch( pExpr->op ){
    /* Double-quoted strings (ex: "abc") are used as identifiers if
    ** possible.  Otherwise they remain as strings.  Single-quoted
    ** strings (ex: 'abc') are always string literals.
    */
    case TK_STRING: {
      if( pExpr->token.z[0]=='\'' ) break;

      int cnt = 0;      /* Number of matches */
      int i;            /* Loop counter */
      char *z;
      assert( pExpr->token.z );
      z = sqliteStrNDup(pExpr->token.z, pExpr->token.n);
      sqliteDequote(z);
      if( z==0 ) return 1;
      for(i=0; i<pTabList->nSrc; i++){
        int j;
        Table *pTab = pTabList->a[i].pTab;
        if( pTab==0 ) continue;
        assert( pTab->nCol>0 );
        for(j=0; j<pTab->nCol; j++){
          if( sqliteStrICmp(pTab->aCol[j].zName, z)==0 ){
            cnt++;

            pExpr->pLeft = sqliteExprDup(pEList->a[j].pExpr);
          }
        } 
      }
      if( cnt==0 && sqliteIsRowid(z) ){
        pExpr->iColumn = -1;
        pExpr->iTable = base;
        cnt = 1 + (pTabList->nSrc>1);
        pExpr->op = TK_COLUMN;
      }
      sqliteFree(z);
      if( cnt==0 && pExpr->token.z[0]!='"' ){
        sqliteSetNString(&pParse->zErrMsg, "no such column: ", -1,  
          pExpr->token.z, pExpr->token.n, 0);
        pParse->nErr++;

        sqliteFree(zLeft);
        sqliteFree(zRight);
        return 1;
      }
      sqliteDequote(zLeft);
      sqliteDequote(zRight);
      pExpr->iTable = -1;
      for(i=0; i<pTabList->nSrc; i++){
        int j;
        char *zTab;
        Table *pTab = pTabList->a[i].pTab;
        if( pTab==0 ) continue;
        assert( pTab->nCol>0 );
        if( pTabList->a[i].zAlias ){
          zTab = pTabList->a[i].zAlias;

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle INSERT statements in SQLite.
**
** $Id: insert.c,v 1.58 2002/05/24 02:04:33 drh Exp $
*/
#include "sqliteInt.h"

/*
** This routine is call to handle SQL of the following forms:
**
**    insert into TABLE (IDLIST) values(EXPRLIST)

    srcTab = pParse->nTab++;
    sqliteVdbeAddOp(v, OP_OpenTemp, srcTab, 0);
    rc = sqliteSelect(pParse, pSelect, SRT_Table, srcTab, 0,0,0);
    if( rc || pParse->nErr || sqlite_malloc_failed ) goto insert_cleanup;
    assert( pSelect->pEList );
    nColumn = pSelect->pEList->nExpr;
  }else{
    SrcList dummy;
    assert( pList!=0 );
    srcTab = -1;
    assert( pList );
    nColumn = pList->nExpr;
    dummy.nSrc = 0;
    for(i=0; i<nColumn; i++){
      if( sqliteExprResolveIds(pParse, 0, &dummy, 0, pList->a[i].pExpr) ){
        goto insert_cleanup;
      }
      if( sqliteExprCheck(pParse, pList->a[i].pExpr, 0, 0) ){
        goto insert_cleanup;
      }

**
*************************************************************************
** 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.68 2002/05/24 02:04:33 drh Exp $
*/
%token_prefix TK_
%token_type {Token}
%default_type {Token}
%extra_argument {Parse *pParse}
%syntax_error {
  sqliteSetString(&pParse->zErrMsg,"syntax error",0);
  pParse->sErrToken = TOKEN;
}
%name sqliteParser
%include {
#include "sqliteInt.h"
#include "parse.h"

/*
** An instance of this structure holds information about the
** LIMIT clause of a SELECT statement.
*/
struct LimitVal {
  int limit;    /* The LIMIT value.  -1 if there is no limit */
  int offset;   /* The OFFSET.  0 if there is none */
};

/*
** An instance of the following structure describes the event of a
** TRIGGER.  "a" is the event type, one of TK_UPDATE, TK_INSERT,
** TK_DELETE, or TK_INSTEAD.  If the event is of the form
**
**      UPDATE ON (a,b,c)
**
** Then the "b" IdList records the list "a,b,c".
*/
struct TrigEvent { int a; IdList * b; };
}

// These are extra tokens used by the lexer but never seen by the
// parser.  We put them in a rule so that the parser generator will
// add them to the parse.h output file.
//
%nonassoc END_OF_FILE ILLEGAL SPACE UNCLOSED_STRING COMMENT FUNCTION

%type multiselect_op {int}
multiselect_op(A) ::= UNION.      {A = TK_UNION;}
multiselect_op(A) ::= UNION ALL.  {A = TK_ALL;}
multiselect_op(A) ::= INTERSECT.  {A = TK_INTERSECT;}
multiselect_op(A) ::= EXCEPT.     {A = TK_EXCEPT;}
oneselect(A) ::= SELECT distinct(D) selcollist(W) from(X) where_opt(Y)
                 groupby_opt(P) having_opt(Q) orderby_opt(Z) limit_opt(L). {
  A = sqliteSelectNew(W,X,Y,P,Q,Z,D,L.limit,L.offset);
}

// The "distinct" nonterminal is true (1) if the DISTINCT keyword is
// present and false (0) if it is not.
//
%type distinct {int}
distinct(A) ::= DISTINCT.   {A = 1;}

  Expr *pLeft = sqliteExpr(TK_ID, 0, 0, &X);
  A = sqliteExprListAppend(P, sqliteExpr(TK_DOT, pLeft, pRight, 0), 0);
}
as ::= .
as ::= AS.


%type seltablist {SrcList*}
%destructor seltablist {sqliteSrcListDelete($$);}
%type stl_prefix {SrcList*}
%destructor stl_prefix {sqliteSrcListDelete($$);}
%type from {SrcList*}
%destructor from {sqliteSrcListDelete($$);}

from(A) ::= .                                 {A = sqliteMalloc(sizeof(*A));}
from(A) ::= FROM seltablist(X).               {A = X;}
stl_prefix(A) ::= seltablist(X) COMMA.        {A = X;}
stl_prefix(A) ::= .                           {A = 0;}
seltablist(A) ::= stl_prefix(X) ids(Y).       {A = sqliteSrcListAppend(X,&Y);}
seltablist(A) ::= stl_prefix(X) ids(Y) as ids(Z). {
  A = sqliteSrcListAppend(X,&Y);
  sqliteSrcListAddAlias(A,&Z);
}
seltablist(A) ::= stl_prefix(X) LP select(S) RP. {
  A = sqliteSrcListAppend(X,0);
  A->a[A->nSrc-1].pSelect = S;
  if( S->pOrderBy ){
    sqliteExprListDelete(S->pOrderBy);
    S->pOrderBy = 0;
  }
}
seltablist(A) ::= stl_prefix(X) LP select(S) RP as ids(Z). {
  A = sqliteSrcListAppend(X,0);
  A->a[A->nSrc-1].pSelect = S;
  if( S->pOrderBy ){
    sqliteExprListDelete(S->pOrderBy);
    S->pOrderBy = 0;
  }
  sqliteSrcListAddAlias(A,&Z);
}

%type orderby_opt {ExprList*}
%destructor orderby_opt {sqliteExprListDelete($$);}
%type sortlist {ExprList*}
%destructor sortlist {sqliteExprListDelete($$);}
%type sortitem {Expr*}

groupby_opt(A) ::= GROUP BY exprlist(X).  {A = X;}

%type having_opt {Expr*}
%destructor having_opt {sqliteExprDelete($$);}
having_opt(A) ::= .                {A = 0;}
having_opt(A) ::= HAVING expr(X).  {A = X;}

%type limit_opt {struct LimitVal}
limit_opt(A) ::= .                  {A.limit = -1; A.offset = 0;}
limit_opt(A) ::= LIMIT INTEGER(X).  {A.limit = atoi(X.z); A.offset = 0;}
limit_opt(A) ::= LIMIT INTEGER(X) limit_sep INTEGER(Y). 
                                    {A.limit = atoi(X.z); A.offset = atoi(Y.z);}
limit_sep ::= OFFSET.
limit_sep ::= COMMA.

/////////////////////////// The DELETE statement /////////////////////////////
//
cmd ::= DELETE FROM ids(X) where_opt(Y).
    {sqliteDeleteFrom(pParse, &X, Y);}

%type trigger_time  {int}
trigger_time(A) ::= BEFORE.      { A = TK_BEFORE; }
trigger_time(A) ::= AFTER.       { A = TK_AFTER;  }
trigger_time(A) ::= INSTEAD OF.  { A = TK_INSTEAD;}
trigger_time(A) ::= .            { A = TK_BEFORE; }

%type trigger_event {struct TrigEvent}
%destructor trigger_event {sqliteIdListDelete($$.b);}
trigger_event(A) ::= DELETE. { A.a = TK_DELETE; A.b = 0; }
trigger_event(A) ::= INSERT. { A.a = TK_INSERT; A.b = 0; }
trigger_event(A) ::= UPDATE. { A.a = TK_UPDATE; A.b = 0;}
trigger_event(A) ::= UPDATE OF inscollist(X). {A.a = TK_UPDATE; A.b = X; }

%type foreach_clause {int}
foreach_clause(A) ::= .                   { A = TK_ROW; }

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle SELECT statements in SQLite.
**
** $Id: select.c,v 1.82 2002/05/24 02:04:33 drh Exp $
*/
#include "sqliteInt.h"

/*
** Allocate a new Select structure and return a pointer to that
** structure.
*/
Select *sqliteSelectNew(
  ExprList *pEList,     /* which columns to include in the result */
  SrcList *pSrc,        /* the FROM clause -- which tables to scan */
  Expr *pWhere,         /* the WHERE clause */
  ExprList *pGroupBy,   /* the GROUP BY clause */
  Expr *pHaving,        /* the HAVING clause */
  ExprList *pOrderBy,   /* the ORDER BY clause */
  int isDistinct,       /* true if the DISTINCT keyword is present */
  int nLimit,           /* LIMIT value.  -1 means not used */
  int nOffset           /* OFFSET value.  -1 means not used */
){
  Select *pNew;
  pNew = sqliteMalloc( sizeof(*pNew) );
  if( pNew==0 ){
    sqliteExprListDelete(pEList);
    sqliteSrcListDelete(pSrc);
    sqliteExprDelete(pWhere);
    sqliteExprListDelete(pGroupBy);
    sqliteExprDelete(pHaving);
    sqliteExprListDelete(pOrderBy);
  }else{
    pNew->pEList = pEList;
    pNew->pSrc = pSrc;

/*
** Delete the given Select structure and all of its substructures.
*/
void sqliteSelectDelete(Select *p){
  if( p==0 ) return;
  sqliteExprListDelete(p->pEList);
  sqliteSrcListDelete(p->pSrc);
  sqliteExprDelete(p->pWhere);
  sqliteExprListDelete(p->pGroupBy);
  sqliteExprDelete(p->pHaving);
  sqliteExprListDelete(p->pOrderBy);
  sqliteSelectDelete(p->pPrior);
  sqliteFree(p->zSelect);
  sqliteFree(p);

** Generate code that will tell the VDBE how many columns there
** are in the result and the name for each column.  This information
** is used to provide "argc" and "azCol[]" values in the callback.
*/
static void generateColumnNames(
  Parse *pParse,      /* Parser context */
  int base,           /* VDBE cursor corresponding to first entry in pTabList */
  SrcList *pTabList,  /* List of tables */
  ExprList *pEList    /* Expressions defining the result set */
){
  Vdbe *v = pParse->pVdbe;
  int i;
  if( pParse->colNamesSet || v==0 || sqlite_malloc_failed ) return;
  pParse->colNamesSet = 1;
  sqliteVdbeAddOp(v, OP_ColumnCount, pEList->nExpr, 0);

    }else if( p->op==TK_COLUMN && pTabList ){
      Table *pTab = pTabList->a[p->iTable - base].pTab;
      char *zCol;
      int iCol = p->iColumn;
      if( iCol<0 ) iCol = pTab->iPKey;
      assert( iCol==-1 || (iCol>=0 && iCol<pTab->nCol) );
      zCol = iCol<0 ? "_ROWID_" : pTab->aCol[iCol].zName;
      if( pTabList->nSrc>1 || showFullNames ){
        char *zName = 0;
        char *zTab;
 
        zTab = pTabList->a[p->iTable - base].zAlias;
        if( showFullNames || zTab==0 ) zTab = pTab->zName;
        sqliteSetString(&zName, zTab, ".", zCol, 0);
        sqliteVdbeAddOp(v, OP_ColumnName, i, 0);

  pTab->iPKey = -1;
  return pTab;
}

/*
** For the given SELECT statement, do two things.
**
**    (1)  Fill in the pTabList->a[].pTab fields in the SrcList that 
**         defines the set of tables that should be scanned. 
**
**    (2)  Scan the list of columns in the result set (pEList) looking
**         for instances of the "*" operator or the TABLE.* operator.
**         If found, expand each "*" to be every column in every table
**         and TABLE.* to be every column in TABLE.
**
** Return 0 on success.  If there are problems, leave an error message
** in pParse and return non-zero.
*/
static int fillInColumnList(Parse *pParse, Select *p){
  int i, j, k, rc;
  SrcList *pTabList;
  ExprList *pEList;
  Table *pTab;

  if( p==0 || p->pSrc==0 ) return 1;
  pTabList = p->pSrc;
  pEList = p->pEList;

  /* Look up every table in the table list.
  */
  for(i=0; i<pTabList->nSrc; i++){
    if( pTabList->a[i].pTab ){
      /* This routine has run before!  No need to continue */
      return 0;
    }
    if( pTabList->a[i].zName==0 ){
      /* A sub-query in the FROM clause of a SELECT */
      assert( pTabList->a[i].pSelect!=0 );

        int tableSeen = 0;      /* Set to 1 when TABLE matches */
        Token *pName;           /* text of name of TABLE */
        if( pE->op==TK_DOT && pE->pLeft ){
          pName = &pE->pLeft->token;
        }else{
          pName = 0;
        }
        for(i=0; i<pTabList->nSrc; i++){
          Table *pTab = pTabList->a[i].pTab;
          char *zTabName = pTabList->a[i].zAlias;
          if( zTabName==0 || zTabName[0]==0 ){ 
            zTabName = pTab->zName;
          }
          if( pName && (zTabName==0 || zTabName[0]==0 ||
                sqliteStrNICmp(pName->z, zTabName, pName->n)!=0) ){

**
** This routine is called on the Select structure that defines a
** VIEW in order to undo any bindings to tables.  This is necessary
** because those tables might be DROPed by a subsequent SQL command.
*/
void sqliteSelectUnbind(Select *p){
  int i;
  SrcList *pSrc = p->pSrc;
  Table *pTab;
  if( p==0 ) return;
  for(i=0; i<pSrc->nSrc; i++){
    if( (pTab = pSrc->a[i].pTab)!=0 ){
      if( pTab->isTransient ){
        sqliteDeleteTable(0, pTab);
        sqliteSelectDelete(pSrc->a[i].pSelect);
        pSrc->a[i].pSelect = 0;
      }
      pSrc->a[i].pTab = 0;

** If flattening is attempted this routine returns 1.
**
** All of the expression analysis must occur on both the outer query and
** the subquery before this routine runs.
*/
int flattenSubquery(Select *p, int iFrom, int isAgg, int subqueryIsAgg){
  Select *pSub;       /* The inner query or "subquery" */
  SrcList *pSrc;      /* The FROM clause of the outer query */
  SrcList *pSubSrc;   /* The FROM clause of the subquery */
  ExprList *pList;    /* The result set of the outer query */
  int i;
  int iParent, iSub;
  Expr *pWhere;

  /* Check to see if flattening is permitted.  Return 0 if not.
  */
  if( p==0 ) return 0;
  pSrc = p->pSrc;
  assert( pSrc && iFrom>=0 && iFrom<pSrc->nSrc );
  pSub = pSrc->a[iFrom].pSelect;
  assert( pSub!=0 );
  if( isAgg && subqueryIsAgg ) return 0;
  if( subqueryIsAgg && pSrc->nSrc>1 ) return 0;
  pSubSrc = pSub->pSrc;
  assert( pSubSrc );
  if( pSubSrc->nSrc!=1 ) return 0;
  if( pSub->isDistinct && pSrc->nSrc>1 ) return 0;
  if( pSub->isDistinct && isAgg ) return 0;
  if( p->isDistinct && subqueryIsAgg ) return 0;

  /* If we reach this point, it means flattening is permitted for the
  ** i-th entry of the FROM clause in the outer query.
  */
  iParent = p->base + iFrom;

  ExprList eList;
  struct ExprList_item eListItem;

  /* Check to see if this query is a simple min() or max() query.  Return
  ** zero if it is  not.
  */
  if( p->pGroupBy || p->pHaving || p->pWhere ) return 0;
  if( p->pSrc->nSrc!=1 ) return 0;
  if( p->pEList->nExpr!=1 ) return 0;
  pExpr = p->pEList->a[0].pExpr;
  if( pExpr->op!=TK_AGG_FUNCTION ) return 0;
  if( pExpr->pList==0 || pExpr->pList->nExpr!=1 ) return 0;
  if( pExpr->token.n!=3 ) return 0;
  if( sqliteStrNICmp(pExpr->token.z,"min",3)==0 ){
    seekOp = OP_Rewind;

  int *pParentAgg        /* True if pParent uses aggregate functions */
){
  int i;
  WhereInfo *pWInfo;
  Vdbe *v;
  int isAgg = 0;         /* True for select lists like "count(*)" */
  ExprList *pEList;      /* List of columns to extract. */
  SrcList *pTabList;     /* List of tables to select from */
  Expr *pWhere;          /* The WHERE clause.  May be NULL */
  ExprList *pOrderBy;    /* The ORDER BY clause.  May be NULL */
  ExprList *pGroupBy;    /* The GROUP BY clause.  May be NULL */
  Expr *pHaving;         /* The HAVING clause.  May be NULL */
  int isDistinct;        /* True if the DISTINCT keyword is present */
  int distinct;          /* Table to use for the distinct set */
  int base;              /* First cursor available for use */

  isDistinct = p->isDistinct;

  /* Allocate a block of VDBE cursors, one for each table in the FROM clause.
  ** The WHERE processing requires that the cursors for the tables in the
  ** FROM clause be consecutive.
  */
  base = p->base = pParse->nTab;
  pParse->nTab += pTabList->nSrc;

  /* 
  ** Do not even attempt to generate any code if we have already seen
  ** errors before this routine starts.
  */
  if( pParse->nErr>0 ) goto select_end;

  }else{
    if( p->nOffset<0 ) p->nOffset = 0;
    sqliteVdbeAddOp(v, OP_Limit, p->nLimit, p->nOffset);
  }

  /* Generate code for all sub-queries in the FROM clause
  */
  for(i=0; i<pTabList->nSrc; i++){
    if( pTabList->a[i].pSelect==0 ) continue;
    sqliteSelect(pParse, pTabList->a[i].pSelect, SRT_TempTable, base+i,
                 p, i, &isAgg);
    pTabList = p->pSrc;
    pWhere = p->pWhere;
    if( eDest==SRT_Callback ){
      pOrderBy = p->pOrderBy;

/*
** 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.
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.113 2002/05/24 02:04:33 drh Exp $
*/
#include "sqlite.h"
#include "hash.h"
#include "vdbe.h"
#include "parse.h"
#include "btree.h"
#include <stdio.h>

typedef struct Index Index;
typedef struct Instruction Instruction;
typedef struct Expr Expr;
typedef struct ExprList ExprList;
typedef struct Parse Parse;
typedef struct Token Token;
typedef struct IdList IdList;
typedef struct SrcList SrcList;
typedef struct WhereInfo WhereInfo;
typedef struct WhereLevel WhereLevel;
typedef struct Select Select;
typedef struct AggExpr AggExpr;
typedef struct FuncDef FuncDef;
typedef struct Trigger Trigger;
typedef struct TriggerStep TriggerStep;

};

/*
** A list of expressions.  Each expression may optionally have a
** name.  An expr/name combination can be used in several ways, such
** as the list of "expr AS ID" fields following a "SELECT" or in the
** list of "ID = expr" items in an UPDATE.  A list of expressions can
** also be used as the argument to a function, in which case the a.zName
** field is not used.
*/
struct ExprList {
  int nExpr;             /* Number of expressions on the list */
  struct ExprList_item {
    Expr *pExpr;           /* The list of expressions */
    char *zName;           /* Token associated with this expression */
    char sortOrder;        /* 1 for DESC or 0 for ASC */
    char isAgg;            /* True if this is an aggregate like count(*) */
    char done;             /* A flag to indicate when processing is finished */
  } *a;                  /* One entry for each expression */
};

/*
** An instance of this structure can hold a simple list of identifiers,
** such as the list "a,b,c" in the following statements:
**
**      INSERT INTO t(a,b,c) VALUES ...;
**      CREATE INDEX idx ON t(a,b,c);
**      CREATE TRIGGER trig BEFORE UPDATE ON t(a,b,c) ...;
**
** The IdList.a.idx field is used when the IdList represents the list of
** column names after a table name in an INSERT statement.  In the statement
**
**     INSERT INTO t(a,b,c) ...
**
** If "a" is the k-th column of table "t", then IdList.a[0].idx==k.
*/
struct IdList {
  int nId;         /* Number of identifiers on the list */
  struct IdList_item {
    char *zName;      /* Name of the identifier */
    int idx;          /* Index in some Table.aCol[] of a column named zName */
  } *a;
};

/*
** The following structure describes the FROM clause of a SELECT statement.
** Each table or subquery in the FROM clause is a separate element of
** the SrcList.a[] array.
*/
struct SrcList {
  int nSrc;        /* Number of tables or subqueries in the FROM clause */
  struct SrcList_item {
    char *zName;      /* Name of the table */
    char *zAlias;     /* The "B" part of a "A AS B" phrase.  zName is the "A" */

    Table *pTab;      /* An SQL table corresponding to zName */
    Select *pSelect;  /* A SELECT statement used in place of a table name */
    int jointype;     /* Type of join between this table and the next */
    Expr *pOn;        /* The ON clause of a join */
    IdList *pUsing;   /* The USING clause of a join */
  } *a;            /* One entry for each identifier on the list */
};

/*
** For each nested loop in a WHERE clause implementation, the WhereInfo
** structure contains a single instance of this structure.  This structure
** is intended to be private the the where.c module and should not be

** first part does the start of the WHERE loop and the second
** half does the tail of the WHERE loop.  An instance of
** this structure is returned by the first half and passed
** into the second half to give some continuity.
*/
struct WhereInfo {
  Parse *pParse;
  SrcList *pTabList;   /* List of tables in the join */
  int iContinue;       /* Jump here to continue with next record */
  int iBreak;          /* Jump here to break out of the loop */
  int base;            /* Index of first Open opcode */
  int nLevel;          /* Number of nested loop */
  int savedNTab;       /* Value of pParse->nTab before WhereBegin() */
  int peakNTab;        /* Value of pParse->nTab after WhereBegin() */
  WhereLevel a[1];     /* Information about each nest loop in the WHERE */

** a VIEW) we have to make a copy of the input string so that the nodes
** of the expression tree will have something to point to.  zSelect is used
** to hold that copy.
*/
struct Select {
  int isDistinct;        /* True if the DISTINCT keyword is present */
  ExprList *pEList;      /* The fields of the result */
  SrcList *pSrc;         /* The FROM clause */
  Expr *pWhere;          /* The WHERE clause */
  ExprList *pGroupBy;    /* The GROUP BY clause */
  Expr *pHaving;         /* The HAVING clause */
  ExprList *pOrderBy;    /* The ORDER BY clause */
  int op;                /* One of: TK_UNION TK_ALL TK_INTERSECT TK_EXCEPT */
  Select *pPrior;        /* Prior select in a compound select statement */
  int nLimit, nOffset;   /* LIMIT and OFFSET values.  -1 means not used */

 * Each trigger present in the database schema is stored as an instance of
 * struct Trigger. 
 *
 * Pointers to instances of struct Trigger are stored in two ways.
 * 1. In the "trigHash" hash table (part of the sqlite* that represents the 
 *    database). This allows Trigger structures to be retrieved by name.
 * 2. All triggers associated with a single table form a linked list, using the
 *    pNext member of struct Trigger. A pointer to the first element of the
 *    linked list is stored as the "pTrigger" member of the associated
 *    struct Table.
 *
 * The "strings" member of struct Trigger contains a pointer to the memory 
 * referenced by the various Token structures referenced indirectly by the
 * "pWhen", "pColumns" and "step_list" members. (ie. the memory allocated for
 * use in conjunction with the sqliteExprMoveStrings() etc. interface).
 *
 * The "step_list" member points to the first element of a linked list
 * containing the SQL statements specified as the trigger program.
 *
 * When a trigger is initially created, the "isCommit" member is set to FALSE.
 * When a transaction is rolled back, any Trigger structures with "isCommit" set
 * to FALSE are deleted by the logic in sqliteRollbackInternalChanges(). When
 * a transaction is commited, the "isCommit" member is set to TRUE for any
 * Trigger structures for which it is FALSE.
 *
 * When a trigger is dropped, using the sqliteDropTrigger() interfaced, it is 
 * removed from the trigHash hash table and added to the trigDrop hash table.
 * If the transaction is rolled back, the trigger is re-added into the trigHash
 * hash table (and hence the database schema). If the transaction is commited,
 * then the Trigger structure is deleted permanently.
 */
struct Trigger {
  char *name;             /* The name of the trigger                        */
  char *table;            /* The table or view to which the trigger applies */
  int op;                 /* One of TK_DELETE, TK_UPDATE, TK_INSERT         */

 * orconf    -> stores the ON CONFLICT algorithm
 * pSelect   -> If this is an INSERT INTO ... SELECT ... statement, then
 *              this stores a pointer to the SELECT statement. Otherwise NULL.
 * target    -> A token holding the name of the table to insert into.
 * pExprList -> If this is an INSERT INTO ... VALUES ... statement, then
 *              this stores values to be inserted. Otherwise NULL.
 * pIdList   -> If this is an INSERT INTO ... (<column-names>) VALUES ... 
 *              statement, then this stores the column-names to be
 *              inserted into.
 *
 * (op == TK_DELETE)
 * target    -> A token holding the name of the table to delete from.
 * pWhere    -> The WHERE clause of the DELETE statement if one is specified.
 *              Otherwise NULL.
 * 
 * (op == TK_UPDATE)
 * target    -> A token holding the name of the table to update rows of.
 * pWhere    -> The WHERE clause of the UPDATE statement if one is specified.
 *              Otherwise NULL.
 * pExprList -> A list of the columns to update and the expressions to update
 *              them to. See sqliteUpdate() documentation of "pChanges"
 *              argument.
 * 
 */
struct TriggerStep {
  int op;              /* One of TK_DELETE, TK_UPDATE, TK_INSERT, TK_SELECT */
  int orconf;          /* OE_Rollback etc. */

  Select *pSelect;     /* Valid for SELECT and sometimes 

void sqliteCreateView(Parse*,Token*,Token*,Select*);
int sqliteViewGetColumnNames(Parse*,Table*);
void sqliteViewResetAll(sqlite*);
void sqliteDropTable(Parse*, Token*, int);
void sqliteDeleteTable(sqlite*, Table*);
void sqliteInsert(Parse*, Token*, ExprList*, Select*, IdList*, int);
IdList *sqliteIdListAppend(IdList*, Token*);
SrcList *sqliteSrcListAppend(SrcList*, Token*);
void sqliteSrcListAddAlias(SrcList*, Token*);
void sqliteIdListDelete(IdList*);
void sqliteSrcListDelete(SrcList*);
void sqliteCreateIndex(Parse*, Token*, Token*, IdList*, int, Token*, Token*);
void sqliteDropIndex(Parse*, Token*);
int sqliteSelect(Parse*, Select*, int, int, Select*, int, int*);
Select *sqliteSelectNew(ExprList*,SrcList*,Expr*,ExprList*,Expr*,ExprList*,
                        int,int,int);
void sqliteSelectDelete(Select*);
void sqliteSelectUnbind(Select*);
Table *sqliteTableNameToTable(Parse*, const char*);
SrcList *sqliteTableTokenToSrcList(Parse*, Token*);
void sqliteDeleteFrom(Parse*, Token*, Expr*);
void sqliteUpdate(Parse*, Token*, ExprList*, Expr*, int);
WhereInfo *sqliteWhereBegin(Parse*, int, SrcList*, Expr*, int);
void sqliteWhereEnd(WhereInfo*);
void sqliteExprCode(Parse*, Expr*);
void sqliteExprIfTrue(Parse*, Expr*, int);
void sqliteExprIfFalse(Parse*, Expr*, int);
Table *sqliteFindTable(sqlite*,const char*);
Index *sqliteFindIndex(sqlite*,const char*);
void sqliteUnlinkAndDeleteIndex(sqlite*,Index*);
void sqliteCopy(Parse*, Token*, Token*, Token*, int);
void sqliteVacuum(Parse*, Token*);
int sqliteGlobCompare(const unsigned char*,const unsigned char*);
int sqliteLikeCompare(const unsigned char*,const unsigned char*);
char *sqliteTableNameFromToken(Token*);
int sqliteExprCheck(Parse*, Expr*, int, int*);
int sqliteExprCompare(Expr*, Expr*);
int sqliteFuncId(Token*);
int sqliteExprResolveIds(Parse*, int, SrcList*, ExprList*, Expr*);
int sqliteExprAnalyzeAggregates(Parse*, Expr*);
Vdbe *sqliteGetVdbe(Parse*);
int sqliteRandomByte(void);
int sqliteRandomInteger(void);
void sqliteBeginTransaction(Parse*, int);
void sqliteCommitTransaction(Parse*);
void sqliteRollbackTransaction(Parse*);
char *sqlite_mprintf(const char *, ...);
int sqliteExprIsConstant(Expr*);
void sqliteGenerateRowDelete(Vdbe*, Table*, int, int);
void sqliteGenerateRowIndexDelete(Vdbe*, Table*, int, char*);
void sqliteGenerateConstraintChecks(Parse*,Table*,int,char*,int,int,int,int);
void sqliteCompleteInsertion(Parse*, Table*, int, char*, int, int);
void sqliteBeginWriteOperation(Parse*, int);
void sqliteEndWriteOperation(Parse*);
void sqliteExprMoveStrings(Expr*, int);
void sqliteExprListMoveStrings(ExprList*, int);
void sqliteSelectMoveStrings(Select*, int);
Expr *sqliteExprDup(Expr*);
ExprList *sqliteExprListDup(ExprList*);
SrcList *sqliteSrcListDup(SrcList*);
IdList *sqliteIdListDup(IdList*);
Select *sqliteSelectDup(Select*);
FuncDef *sqliteFindFunction(sqlite*,const char*,int,int,int);
void sqliteRegisterBuildinFunctions(sqlite*);
int sqliteSafetyOn(sqlite*);
int sqliteSafetyOff(sqlite*);
int sqliteSafetyCheck(sqlite*);

          !checkColumnOverLap(pTrigger->pColumns, pChanges) ){
        fire_this = 0;
      }
    }

    if( fire_this && (pTriggerStack = sqliteMalloc(sizeof(TriggerStack)))!=0 ){
      int endTrigger;
      SrcList dummyTablist;
      Expr * whenExpr;

      dummyTablist.nSrc = 0;
      dummyTablist.a = 0;

      /* Push an entry on to the trigger stack */
      pTriggerStack->pTrigger = pTrigger;
      pTriggerStack->newIdx = newIdx;
      pTriggerStack->oldIdx = oldIdx;
      pTriggerStack->pTab = pTab;

  assert(pTab->pSelect);

  tblNameToken.z = pTab->zName;
  tblNameToken.n = strlen(pTab->zName);

  theSelect.isDistinct = 0;
  theSelect.pEList = sqliteExprListAppend(0, sqliteExpr(TK_ALL, 0, 0, 0), 0);
  theSelect.pSrc   = sqliteSrcListAppend(0, &tblNameToken);
  theSelect.pWhere = pWhere;    pWhere = 0;
  theSelect.pGroupBy = 0;
  theSelect.pHaving = 0;
  theSelect.pOrderBy = 0;
  theSelect.op = TK_SELECT; /* ?? */
  theSelect.pPrior = 0;
  theSelect.nLimit = -1;

  sqliteEndWriteOperation(pParse);

trigger_cleanup:
  sqliteFree(aXRef);
  sqliteExprListDelete(pChanges);
  sqliteExprDelete(pWhere);
  sqliteExprListDelete(theSelect.pEList);
  sqliteSrcListDelete(theSelect.pSrc);
  sqliteExprDelete(theSelect.pWhere);
  return;
}

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle UPDATE statements.
**
** $Id: update.c,v 1.43 2002/05/24 02:04:34 drh Exp $
*/
#include "sqliteInt.h"

/*
** Process an UPDATE statement.
*/
void sqliteUpdate(
  Parse *pParse,         /* The parser context */
  Token *pTableName,     /* The table in which we should change things */
  ExprList *pChanges,    /* Things to be changed */
  Expr *pWhere,          /* The WHERE clause.  May be null */
  int onError            /* How to handle constraint errors */
){
  int i, j;              /* Loop counters */
  Table *pTab;           /* The table to be updated */
  SrcList *pTabList = 0; /* Fake FROM clause containing only pTab */
  int addr;              /* VDBE instruction address of the start of the loop */
  WhereInfo *pWInfo;     /* Information about the WHERE clause */
  Vdbe *v;               /* The virtual database engine */
  Index *pIdx;           /* For looping over indices */
  int nIdx;              /* Number of indices that need updating */
  int nIdxTotal;         /* Total number of indices */
  int base;              /* Index of first available table cursor */

        sqliteViewTriggers(pParse, pTab, pWhere, onError, pChanges);
        return;
      }
    }
  }

  /* Locate the table which we want to update.  This table has to be
  ** put in an SrcList structure because some of the subroutines we
  ** will be calling are designed to work with multiple tables and expect
  ** an SrcList* parameter instead of just a Table* parameter.
  */
  pTabList = sqliteTableTokenToSrcList(pParse, pTableName);
  if( pTabList==0 ) goto update_cleanup;
  pTab = pTabList->a[0].pTab;
  assert( pTab->pSelect==0 );  /* This table is not a VIEW */
  aXRef = sqliteMalloc( sizeof(int) * pTab->nCol );
  if( aXRef==0 ) goto update_cleanup;
  for(i=0; i<pTab->nCol; i++) aXRef[i] = -1;

    sqliteVdbeChangeP3(v, -1, "rows updated", P3_STATIC);
    sqliteVdbeAddOp(v, OP_Callback, 1, 0);
  }

update_cleanup:
  sqliteFree(apIdx);
  sqliteFree(aXRef);
  sqliteSrcListDelete(pTabList);
  sqliteExprListDelete(pChanges);
  sqliteExprDelete(pWhere);
  return;
}

** type to the other occurs as necessary.
** 
** Most of the code in this file is taken up by the sqliteVdbeExec()
** function which does the work of interpreting a VDBE program.
** But other routines are also provided to help in building up
** a program instruction by instruction.
**
** $Id: vdbe.c,v 1.147 2002/05/24 02:04:34 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** The following global variable is incremented every time a cursor
** moves, either by the OP_MoveTo or the OP_Next opcode.  The test

  int *aLabel;        /* Space to hold the labels */
  int tos;            /* Index of top of stack */
  int nStackAlloc;    /* Size of the stack */
  Stack *aStack;      /* The operand stack, except string values */
  char **zStack;      /* Text or binary values of the stack */
  char **azColName;   /* Becomes the 4th parameter to callbacks */
  int nCursor;        /* Number of slots in aCsr[] */
  Cursor *aCsr;       /* One element of this array for each open cursor */
  Keylist *pList;     /* A list of ROWIDs */
  Sorter *pSort;      /* A linked list of objects to be sorted */
  FILE *pFile;        /* At most one open file handler */
  int nField;         /* Number of file fields */
  char **azField;     /* Data for each file field */
  char *zLine;        /* A single line from the input file */
  int nLineAlloc;     /* Number of spaces allocated for zLine */

    p->pList = 0;
  }
  break;
}

/* Opcode: ListPush * * * 
**
** Save the current Vdbe list such that it can be restored by a ListPop
** opcode. The list is empty after this is executed.
*/
case OP_ListPush: {
  p->keylistStackDepth++;
  assert(p->keylistStackDepth > 0);
  p->keylistStack = sqliteRealloc(p->keylistStack, 
          sizeof(Keylist *) * p->keylistStackDepth);
  p->keylistStack[p->keylistStackDepth - 1] = p->pList;
  p->pList = 0;
  break;
}

/* Opcode: ListPop * * * 
**
** Restore the Vdbe list to the state it was in when ListPush was last
** executed.
*/
case OP_ListPop: {
  assert(p->keylistStackDepth > 0);
  p->keylistStackDepth--;
  KeylistFree(p->pList);
  p->pList = p->keylistStack[p->keylistStackDepth];

**    May you share freely, never taking more than you give.
**
*************************************************************************
** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.  Also found here are subroutines
** to generate VDBE code to evaluate expressions.
**
** $Id: where.c,v 1.46 2002/05/24 02:04:34 drh Exp $
*/
#include "sqliteInt.h"

/*
** The query generator uses an array of instances of this structure to
** help it analyze the subexpressions of the WHERE clause.  Each WHERE
** clause subexpression is separated from the others by an AND operator.

** in order to complete the WHERE clause processing.
**
** If an error occurs, this routine returns NULL.
*/
WhereInfo *sqliteWhereBegin(
  Parse *pParse,       /* The parser context */
  int base,            /* VDBE cursor index for left-most table in pTabList */
  SrcList *pTabList,   /* A list of all tables to be scanned */
  Expr *pWhere,        /* The WHERE clause */
  int pushKey          /* If TRUE, leave the table key on the stack */
){
  int i;                     /* Loop counter */
  WhereInfo *pWInfo;         /* Will become the return value of this function */
  Vdbe *v = pParse->pVdbe;   /* The virtual database engine */
  int brk, cont;             /* Addresses used during code generation */
  int *aOrder;         /* Order in which pTabList entries are searched */
  int nExpr;           /* Number of subexpressions in the WHERE clause */
  int loopMask;        /* One bit set for each outer loop */
  int haveKey;         /* True if KEY is on the stack */
  int aDirect[32];     /* If TRUE, then index this table using ROWID */
  int iDirectEq[32];   /* Term of the form ROWID==X for the N-th table */
  int iDirectLt[32];   /* Term of the form ROWID<X or ROWID<=X */
  int iDirectGt[32];   /* Term of the form ROWID>X or ROWID>=X */
  ExprInfo aExpr[50];  /* The WHERE clause is divided into these expressions */

  /* Allocate space for aOrder[] and aiMem[]. */
  aOrder = sqliteMalloc( sizeof(int) * pTabList->nSrc );

  /* Allocate and initialize the WhereInfo structure that will become the
  ** return value.
  */
  pWInfo = sqliteMalloc( sizeof(WhereInfo) + pTabList->nSrc*sizeof(WhereLevel));
  if( sqlite_malloc_failed ){
    sqliteFree(aOrder);
    sqliteFree(pWInfo);
    return 0;
  }
  pWInfo->pParse = pParse;
  pWInfo->pTabList = pTabList;

        aExpr[i].prereqAll &= mask;
      }
    }
  }

  /* Figure out a good nesting order for the tables.  aOrder[0] will
  ** be the index in pTabList of the outermost table.  aOrder[1] will
  ** be the first nested loop and so on.  aOrder[pTabList->nSrc-1] will
  ** be the innermost loop.
  **
  ** Someday we will put in a good algorithm here to reorder the loops
  ** for an effiecient query.  But for now, just use whatever order the
  ** tables appear in in the pTabList.
  */
  for(i=0; i<pTabList->nSrc; i++){
    aOrder[i] = i;
  }

  /* Figure out what index to use (if any) for each nested loop.
  ** Make pWInfo->a[i].pIdx point to the index to use for the i-th nested
  ** loop where i==0 is the outer loop and i==pTabList->nSrc-1 is the inner
  ** loop. 
  **
  ** If terms exist that use the ROWID of any table, then set the
  ** iDirectEq[], iDirectLt[], or iDirectGt[] elements for that table
  ** to the index of the term containing the ROWID.  We always prefer
  ** to use a ROWID which can directly access a table rather than an
  ** index which requires reading an index first to get the rowid then
  ** doing a second read of the actual database table.
  **
  ** Actually, if there are more than 32 tables in the join, only the
  ** first 32 tables are candidates for indices.  This is (again) due
  ** to the limit of 32 bits in an integer bitmask.
  */
  loopMask = 0;
  for(i=0; i<pTabList->nSrc && i<ARRAYSIZE(aDirect); i++){
    int j;
    int idx = aOrder[i];
    Table *pTab = pTabList->a[idx].pTab;
    Index *pIdx;
    Index *pBestIdx = 0;
    int bestScore = 0;

      pWInfo->a[i].iCur = pParse->nTab++;
      pWInfo->peakNTab = pParse->nTab;
    }
  }

  /* Open all tables in the pTabList and all indices used by those tables.
  */
  for(i=0; i<pTabList->nSrc; i++){
    int openOp;
    Table *pTab;

    pTab = pTabList->a[i].pTab;
    if( pTab->isTransient || pTab->pSelect ) continue;
    openOp = pTab->isTemp ? OP_OpenAux : OP_Open;
    sqliteVdbeAddOp(v, openOp, base+i, pTab->tnum);

      sqliteVdbeChangeP3(v, -1, pWInfo->a[i].pIdx->zName, P3_STATIC);
    }
  }

  /* Generate the code to do the search
  */
  loopMask = 0;
  for(i=0; i<pTabList->nSrc; i++){
    int j, k;
    int idx = aOrder[i];
    Index *pIdx;
    WhereLevel *pLevel = &pWInfo->a[i];

    pIdx = pLevel->pIdx;
    if( i<ARRAYSIZE(iDirectEq) && iDirectEq[i]>=0 ){

      }else{
        sqliteExprCode(pParse, aExpr[k].p->pLeft);
      }
      aExpr[k].p = 0;
      brk = pLevel->brk = sqliteVdbeMakeLabel(v);
      cont = pLevel->cont = brk;
      sqliteVdbeAddOp(v, OP_MustBeInt, 0, brk);
      if( i==pTabList->nSrc-1 && pushKey ){
        /* Note: The OP_Dup below will cause the recno to be left on the
        ** stack if the record does not exists and the OP_NotExists jump is
        ** taken.  This violates a general rule of the VDBE that you should
        ** never leave values on the stack in order to avoid a stack overflow.
        ** But in this case, the OP_Dup will never happen inside of a loop,
        ** because the pushKey flag is only true for UPDATE and DELETE, not
        ** for SELECT, and nested loops only occur on a SELECT.

        sqliteVdbeAddOp(v, OP_MemStore, pLevel->iMem, 1);
        testOp = OP_IdxGE;
      }
      sqliteVdbeAddOp(v, OP_MoveTo, pLevel->iCur, brk);
      start = sqliteVdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0);
      sqliteVdbeAddOp(v, testOp, pLevel->iCur, brk);
      sqliteVdbeAddOp(v, OP_IdxRecno, pLevel->iCur, 0);
      if( i==pTabList->nSrc-1 && pushKey ){
        haveKey = 1;
      }else{
        sqliteVdbeAddOp(v, OP_MoveTo, base+idx, 0);
        haveKey = 0;
      }
      pLevel->op = OP_Next;
      pLevel->p1 = pLevel->iCur;

      */
      start = sqliteVdbeCurrentAddr(v);
      if( testOp!=OP_Noop ){
        sqliteVdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0);
        sqliteVdbeAddOp(v, testOp, pLevel->iCur, brk);
      }
      sqliteVdbeAddOp(v, OP_IdxRecno, pLevel->iCur, 0);
      if( i==pTabList->nSrc-1 && pushKey ){
        haveKey = 1;
      }else{
        sqliteVdbeAddOp(v, OP_MoveTo, base+idx, 0);
        haveKey = 0;
      }

      /* Record the instruction used to terminate the loop.

** Generate the end of the WHERE loop.
*/
void sqliteWhereEnd(WhereInfo *pWInfo){
  Vdbe *v = pWInfo->pParse->pVdbe;
  int i;
  int base = pWInfo->base;
  WhereLevel *pLevel;
  SrcList *pTabList = pWInfo->pTabList;

  for(i=pTabList->nSrc-1; i>=0; i--){
    pLevel = &pWInfo->a[i];
    sqliteVdbeResolveLabel(v, pLevel->cont);
    if( pLevel->op!=OP_Noop ){
      sqliteVdbeAddOp(v, pLevel->op, pLevel->p1, pLevel->p2);
    }
    sqliteVdbeResolveLabel(v, pLevel->brk);
  }
  sqliteVdbeResolveLabel(v, pWInfo->iBreak);
  for(i=0; i<pTabList->nSrc; i++){
    if( pTabList->a[i].pTab->isTransient ) continue;
    pLevel = &pWInfo->a[i];
    sqliteVdbeAddOp(v, OP_Close, base+i, 0);
    if( pLevel->pIdx!=0 ){
      sqliteVdbeAddOp(v, OP_Close, pLevel->iCur, 0);
    }
  }
  if( pWInfo->pParse->nTab==pWInfo->peakNTab ){
    pWInfo->pParse->nTab = pWInfo->savedNTab;
  }
  sqliteFree(pWInfo);
  return;
}