SQLite

** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** This file contains C code routines used for processing expressions
**
** $Id: expr.c,v 1.7 2000/06/06 01:50:43 drh Exp $
*/
#include "sqliteInt.h"

/*
** Walk an expression tree.  Return 1 if the expression is constant
** and 0 if it involves variables.
*/
static int isConstant(Expr *p){
  switch( p->op ){
    case TK_ID:
    case TK_FIELD:
    case TK_DOT:
      return 0;
    default: {
      if( p->pLeft && !isConstant(p->pLeft) ) return 0;
      if( p->pRight && !isConstant(p->pRight) ) return 0;
      if( p->pList ){
        int i;
        for(i=0; i<p->pList->nExpr; i++){
          if( !isConstant(p->pList->a[i].pExpr) ) return 0;
        }
      }
      break;
    }
  }
  return 1;
}

/*
** This routine walks an expression tree and resolves references to
** table fields.  Nodes of the form ID.ID or ID resolve into an
** index to the table in the table list and a field offset.  The opcode
** for such nodes is changed to TK_FIELD.  The iTable value is changed
** to the index of the referenced table in pTabList plus the pParse->nTab
** value.  The iField value is changed to the index of the field of the 
** referenced table.
**
** We also check for instances of the IN operator.  IN comes in two
** forms:
**
**           expr IN (exprlist)
** and
**           expr IN (SELECT ...)
**
** The first form is handled by creating a set holding the list
** of allowed values.  The second form causes the SELECT to generate 
** a temporary table.
**
** This routine also looks for scalar SELECTs that are part of an expression.
** If it finds any, it generates code to write the value of that select
** into a memory cell.
**
** Unknown fields 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, IdList *pTabList, Expr *pExpr){

      sqliteExprDelete(pLeft);
      pExpr->pLeft = 0;
      sqliteExprDelete(pRight);
      pExpr->pRight = 0;
      pExpr->op = TK_FIELD;
      break;
    }

    case TK_IN: {
      Vdbe *v = pParse->pVdbe;
      if( v==0 ){
        v = pParse->pVdbe = sqliteVdbeCreate(pParse->db->pBe);
      }
      if( v==0 ) return 1;
      if( pExpr->pSelect ){
        /* Case 1:     expr IN (SELECT ...)
        **
        ** Generate code to write the results of the select into a temporary
        ** table.  The cursor number of the temporary table is stored in 
        ** iTable.
        */
        pExpr->iTable = pParse->nTab++;
        sqliteVdbeAddOp(v, OP_Open, pExpr->iTable, 0, 0, 0);
        if( sqliteSelect(pParse, pExpr->pSelect, SRT_Set, pExpr->iTable) );
      }else if( pExpr->pList ){
        /* Case 2:     expr IN (exprlist)
        **
        ** Create a set to put the exprlist values in.  The Set id is stored
        ** in iTable.
        */
        int i, iSet;
        for(i=0; i<pExpr->pList->nExpr; i++){
          Expr *pE2 = pExpr->pList->a[i].pExpr;
          if( sqliteExprCheck(pParse, pE2, 0, 0) ){
            return 1;
          }
          if( !isConstant(pE2) ){
            sqliteSetString(&pParse->zErrMsg,
              "right-hand side of IN operator must be constant", 0);
            pParse->nErr++;
            return 1;
          }
        }
        iSet = pExpr->iTable = pParse->nSet++;
        for(i=0; i<pExpr->pList->nExpr; i++){
          Expr *pE2 = pExpr->pList->a[i].pExpr;
          switch( pE2->op ){
            case TK_FLOAT:
            case TK_INTEGER:
            case TK_STRING: {
              int addr = sqliteVdbeAddOp(v, OP_SetInsert, iSet, 0, 0, 0);
              sqliteVdbeChangeP3(v, addr, pE2->token.z, pE2->token.n);
              sqliteVdbeDequoteP3(v, addr);
              break;
            }
            default: {
              sqliteExprCode(pParse, pE2);
              sqliteVdbeAddOp(v, OP_SetInsert, iSet, 0, 0, 0);
              break;
            }
          }
        }
      }
    }

    case TK_SELECT: {
      /* This has to be a scalar SELECT.  Generate code to put the
      ** value of this select in a memory cell and record the number
      ** of the memory cell in iField.
      */
      pExpr->iField = pParse->nMem++;
      if( sqliteSelect(pParse, pExpr->pSelect, SRT_Mem, pExpr->iField) ){
        return 1;
      }
      break;
    }

    /* For all else, just recursively walk the tree */
    default: {

    }
    default: {
      if( pExpr->pLeft ){
        nErr = sqliteExprCheck(pParse, pExpr->pLeft, 0, 0);
      }
      if( nErr==0 && pExpr->pRight ){
        nErr = sqliteExprCheck(pParse, pExpr->pRight, 0, 0);
      }
      if( nErr==0 && pExpr->pList ){
        int n = pExpr->pList->nExpr;
        int i;
        for(i=0; nErr==0 && i<n; i++){
          nErr = sqliteExprCheck(pParse, pExpr->pList->a[i].pExpr, 0, 0);
        }
      }
      break;
    }
  }
  return nErr;
}

      }
      break;
    }
    case TK_SELECT: {
      sqliteVdbeAddOp(v, OP_MemLoad, pExpr->iField, 0, 0, 0);
      break;
    }
    case TK_IN: {
      int addr;
      sqliteVdbeAddOp(v, OP_Integer, 0, 0, 0, 0);
      sqliteExprCode(pParse, pExpr->pLeft);
      addr = sqliteVdbeCurrentAddr(v);
      if( pExpr->pSelect ){
        sqliteVdbeAddOp(v, OP_Found, pExpr->iTable, addr+2, 0, 0);
      }else{
        sqliteVdbeAddOp(v, OP_SetFound, pExpr->iTable, addr+2, 0, 0);
      }
      sqliteVdbeAddOp(v, OP_AddImm, 1, 0, 0, 0);
      break;
    }
    case TK_BETWEEN: {
      int lbl = sqliteVdbeMakeLabel(v);
      sqliteVdbeAddOp(v, OP_Integer, 0, 0, 0, 0);
      sqliteExprIfFalse(pParse, pExpr, lbl);
      sqliteVdbeAddOp(v, OP_AddImm, 1, 0, 0, 0);
      sqliteVdbeResolveLabel(v, lbl);
      break;
    }
  }
  return;
}

/*
** Generate code for a boolean expression such that a jump is made
** to the label "dest" if the expression is true but execution

      break;
    }
    case TK_ISNULL:
    case TK_NOTNULL: {
      sqliteExprCode(pParse, pExpr->pLeft);
      sqliteVdbeAddOp(v, op, 0, dest, 0, 0);
      break;
    }
    case TK_IN: {
      if( pExpr->pSelect ){
        sqliteVdbeAddOp(v, OP_Found, pExpr->iTable, dest, 0, 0);
      }else{
        sqliteVdbeAddOp(v, OP_SetFound, pExpr->iTable, dest, 0, 0);
      }
      break;
    }
    case TK_BETWEEN: {
      int lbl = sqliteVdbeMakeLabel(v);
      sqliteExprCode(pParse, pExpr->pLeft);
      sqliteVdbeAddOp(v, OP_Dup, 0, 0, 0, 0);
      sqliteExprCode(pParse, pExpr->pList->a[0].pExpr);
      sqliteVdbeAddOp(v, OP_Lt, 0, lbl, 0, 0);
      sqliteExprCode(pParse, pExpr->pList->a[1].pExpr);
      sqliteVdbeAddOp(v, OP_Le, 0, dest, 0, 0);
      sqliteVdbeAddOp(v, OP_Integer, 0, 0, 0, 0);
      sqliteVdbeAddOp(v, OP_Pop, 1, 0, 0, lbl);
      break;
    }
    default: {
      sqliteExprCode(pParse, pExpr);
      sqliteVdbeAddOp(v, OP_If, 0, dest, 0, 0);
      break;
    }
  }

      break;
    }
    case TK_ISNULL:
    case TK_NOTNULL: {
      sqliteExprCode(pParse, pExpr->pLeft);
      sqliteVdbeAddOp(v, op, 0, dest, 0, 0);
      break;
    }
    case TK_IN: {
      if( pExpr->pSelect ){
        sqliteVdbeAddOp(v, OP_NotFound, pExpr->iTable, dest, 0, 0);
      }else{
        sqliteVdbeAddOp(v, OP_SetNotFound, pExpr->iTable, dest, 0, 0);
      }
      break;
    }
    case TK_BETWEEN: {
      int addr;
      sqliteExprCode(pParse, pExpr->pLeft);
      sqliteVdbeAddOp(v, OP_Dup, 0, 0, 0, 0);
      sqliteExprCode(pParse, pExpr->pList->a[0].pExpr);
      addr = sqliteVdbeCurrentAddr(v);
      sqliteVdbeAddOp(v, OP_Ge, 0, addr+3, 0, 0);
      sqliteVdbeAddOp(v, OP_Pop, 1, 0, 0, 0);
      sqliteVdbeAddOp(v, OP_Goto, 0, dest, 0, 0);
      sqliteExprCode(pParse, pExpr->pList->a[1].pExpr);
      sqliteVdbeAddOp(v, OP_Gt, 0, dest, 0, 0);
      break;
    }
    default: {
      sqliteExprCode(pParse, pExpr);
      sqliteVdbeAddOp(v, OP_Not, 0, 0, 0, 0);
      sqliteVdbeAddOp(v, OP_If, 0, dest, 0, 0);
      break;
    }
  }
}

**
*************************************************************************
** 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.11 2000/06/06 01:50:43 drh Exp $
*/
%token_prefix TK_
%token_type {Token}
%extra_argument {Parse *pParse}
%syntax_error {
  sqliteSetNString(&pParse->zErrMsg,"syntax error near \"",0,TOKEN.z,TOKEN.n,
                   "\"", 1, 0);

// The next command format is dropping tables.
//
cmd ::= DROP TABLE id(X).          {sqliteDropTable(pParse,&X);}

// The select statement
//
cmd ::= select(X).  {
  sqliteSelect(pParse, X, SRT_Callback, 0);
  sqliteSelectDelete(X);
}

%type select {Select*}
%destructor select {sqliteSelectDelete($$);}

select(A) ::= SELECT distinct(D) selcollist(W) from(X) where_opt(Y)
              orderby_opt(Z). {
  A = sqliteSelectNew(W,X,Y,0,0,Z,D);
}

// 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;}
distinct(A) ::= ALL.        {A = 0;}
distinct(A) ::= .           {A = 0;}

// selcollist is a list of expressions that are to become the return
// values of the SELECT statement.  In the case of "SELECT * FROM ..."
// the selcollist value is NULL.  
//
%type selcollist {ExprList*}

fieldlist_opt(A) ::= LP fieldlist(X) RP.  {A = X;}
fieldlist(A) ::= fieldlist(X) COMMA ID(Y). {A = sqliteIdListAppend(X,&Y);}
fieldlist(A) ::= ID(Y).                    {A = sqliteIdListAppend(0,&Y);}

%left OR.
%left AND.
%right NOT.
%left EQ NE ISNULL NOTNULL IS LIKE GLOB BETWEEN IN.
%left GT GE LT LE.
%left PLUS MINUS.
%left STAR SLASH PERCENT.
%right UMINUS.

%type expr {Expr*}
%destructor expr {sqliteExprDelete($$);}

expr(A) ::= expr(X) LT expr(Y).    {A = sqliteExpr(TK_LT, X, Y, 0);}
expr(A) ::= expr(X) GT expr(Y).    {A = sqliteExpr(TK_GT, X, Y, 0);}
expr(A) ::= expr(X) LE expr(Y).    {A = sqliteExpr(TK_LE, X, Y, 0);}
expr(A) ::= expr(X) GE expr(Y).    {A = sqliteExpr(TK_GE, X, Y, 0);}
expr(A) ::= expr(X) NE expr(Y).    {A = sqliteExpr(TK_NE, X, Y, 0);}
expr(A) ::= expr(X) EQ expr(Y).    {A = sqliteExpr(TK_EQ, X, Y, 0);}
expr(A) ::= expr(X) LIKE expr(Y).  {A = sqliteExpr(TK_LIKE, X, Y, 0);}
expr(A) ::= expr(X) GLOB expr(Y).  {A = sqliteExpr(TK_GLOB,X,Y,0);}

expr(A) ::= expr(X) PLUS expr(Y).  {A = sqliteExpr(TK_PLUS, X, Y, 0);}
expr(A) ::= expr(X) MINUS expr(Y). {A = sqliteExpr(TK_MINUS, X, Y, 0);}
expr(A) ::= expr(X) STAR expr(Y).  {A = sqliteExpr(TK_STAR, X, Y, 0);}
expr(A) ::= expr(X) SLASH expr(Y). {A = sqliteExpr(TK_SLASH, X, Y, 0);}
expr(A) ::= expr(X) ISNULL.        {A = sqliteExpr(TK_ISNULL, X, 0, 0);}
expr(A) ::= expr(X) NOTNULL.       {A = sqliteExpr(TK_NOTNULL, X, 0, 0);}
expr(A) ::= NOT expr(X).           {A = sqliteExpr(TK_NOT, X, 0, 0);}
expr(A) ::= MINUS expr(X). [UMINUS]   {A = sqliteExpr(TK_UMINUS, X, 0, 0);}
expr(A) ::= PLUS expr(X). [UMINUS]    {A = X;}
expr(A) ::= LP select(X) RP. {
  A = sqliteExpr(TK_SELECT, 0, 0, 0);
  A->pSelect = X;
}
expr(A) ::= expr(W) BETWEEN expr(X) AND expr(Y). {
  ExprList *pList = sqliteExprListAppend(0, X, 0);
  pList = sqliteExprListAppend(pList, Y, 0);
  A = sqliteExpr(TK_BETWEEN, W, 0, 0);
  A->pList = pList;
}
expr(A) ::= expr(X) IN LP exprlist(Y) RP.  {
  A = sqliteExpr(TK_IN, X, 0, 0);
  A->pList = Y;
}
expr(A) ::= expr(X) IN LP select(Y) RP.  {
  A = sqliteExpr(TK_IN, X, 0, 0);
  A->pSelect = Y;
}



%type exprlist {ExprList*}
%destructor exprlist {sqliteExprListDelete($$);}
%type expritem {Expr*}
%destructor expritem {sqliteExprDelete($$);}

exprlist(A) ::= exprlist(X) COMMA expritem(Y). 

**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle SELECT statements.
**
** $Id: select.c,v 1.9 2000/06/06 01:50:43 drh Exp $
*/
#include "sqliteInt.h"


/*
** Allocate a new Select structure and return a pointer to that
** structure.

  sqliteExprListDelete(p->pOrderBy);
  sqliteFree(p);
}

/*
** Generate code for the given SELECT statement.
**
** The results are distributed in various ways depending on the
** value of eDest and iParm.
**
**     eDest Value       Result
**     ------------    -------------------------------------------
**     SRT_Callback    Invoke the callback for each row of the result.
**
**     SRT_Mem         Store first result in memory cell iParm
**
**     SRT_Set         Store results as keys of a table with cursor iParm
**
**     SRT_Table       Store results in a regular table with cursor iParm


**
** This routine returns the number of errors.  If any errors are
** encountered, then an appropriate error message is left in
** pParse->zErrMsg.
**
** This routine does NOT free the Select structure passed in.  The
** calling function needs to do that.
*/
int sqliteSelect(
  Parse *pParse,         /* The parser context */
  Select *p,             /* The SELECT statement being coded. */
  int eDest,             /* One of SRT_Callback, SRT_Mem, SRT_Set, SRT_Table */
  int iParm              /* Save result in this memory location, if >=0 */
){
  int i, j;
  WhereInfo *pWInfo;
  Vdbe *v;
  int isAgg = 0;         /* True for select lists like "count(*)" */
  ExprList *pEList;      /* List of fields to extract.  NULL means "*" */
  IdList *pTabList;      /* List of tables to select from */

        pEList = sqliteExprListAppend(pEList, pExpr, 0);
      }
    }
  }

  /* If writing to memory, only a single column may be output.
  */
  if( (eDest==SRT_Mem || eDest==SRT_Set) && pEList->nExpr>1 ){
    sqliteSetString(&pParse->zErrMsg, "only a single result allowed for "
       "a SELECT that is part of an expression", 0);
    pParse->nErr++;
    return 1;
  }

  /* Resolve the field names and do a semantics check on all the expressions.

      }
      if( sqliteExprCheck(pParse, pOrderBy->a[i].pExpr, 0, 0) ){
        return 1;
      }
    }
  }

  /* ORDER BY is ignored if we are not invoking callbacks.









  */
  if( isAgg || eDest!=SRT_Callback ){
    pOrderBy = 0;
  }

  /* Turn off distinct if this is an aggregate or writing to memory.
  */
  if( isAgg || eDest==SRT_Mem ){
    isDistinct = 0;
  }

  /* Begin generating code.
  */
  v = pParse->pVdbe;
  if( v==0 ){

  if( pOrderBy ){
    sqliteVdbeAddOp(v, OP_SortOpen, 0, 0, 0, 0);
  }

  /* Identify column names if we will be using a callback.  This
  ** step is skipped if the output is going to a table or a memory cell.
  */
  if( eDest==SRT_Callback ){
    sqliteVdbeAddOp(v, OP_ColumnCount, pEList->nExpr, 0, 0, 0);
    for(i=0; i<pEList->nExpr; i++){
      Expr *p;
      if( pEList->a[i].zName ){
        char *zName = pEList->a[i].zName;
        int addr = sqliteVdbeAddOp(v, OP_ColumnName, i, 0, zName, 0);
        if( zName[0]=='\'' || zName[0]=='"' ){

        }
      }
    }
  }

  /* Initialize the memory cell to NULL
  */
  if( eDest==SRT_Mem ){
    sqliteVdbeAddOp(v, OP_Null, 0, 0, 0, 0);
    sqliteVdbeAddOp(v, OP_MemStore, iParm, 0, 0, 0);
  }

  /* Begin the database scan
  */
  if( isDistinct ){
    sqliteVdbeAddOp(v, OP_Open, distinct, 1, 0, 0);
  }

        case FN_Count: op = OP_AddImm; p1 = 1; break;
        case FN_Sum:   op = OP_Add;    p1 = 0; break;
        case FN_Min:   op = OP_Min;    p1 = 1; break;
        case FN_Max:   op = OP_Max;    p1 = 0; break;
      }
      sqliteVdbeAddOp(v, op, p1, 0, 0, 0);
    }
  }else if( eDest==SRT_Table ){
    sqliteVdbeAddOp(v, OP_MakeRecord, pEList->nExpr, 0, 0, 0);
    sqliteVdbeAddOp(v, OP_New, iParm, 0, 0, 0);
    sqliteVdbeAddOp(v, OP_Pull, 1, 0, 0, 0);
    sqliteVdbeAddOp(v, OP_Put, iParm, 0, 0, 0);
  }else if( eDest==SRT_Set ){
    sqliteVdbeAddOp(v, OP_String, 0, 0, "", 0);
    sqliteVdbeAddOp(v, OP_Put, iParm, 0, 0, 0);
  }else if( eDest==SRT_Mem ){
    sqliteVdbeAddOp(v, OP_MemStore, iParm, 0, 0, 0);
    sqliteVdbeAddOp(v, OP_Goto, 0, pWInfo->iBreak, 0, 0);
  }else{
    sqliteVdbeAddOp(v, OP_Callback, pEList->nExpr, 0, 0, 0);
  }

  /* End the database scan loop.
  */

    sqliteVdbeAddOp(v, OP_SortClose, 0, 0, 0, end);
  }

  /* If this is an aggregate, then we need to invoke the callback
  ** exactly once.
  */
  if( isAgg ){
    if( eDest==SRT_Table ){
      sqliteVdbeAddOp(v, OP_MakeRecord, pEList->nExpr, 0, 0, 0);
      sqliteVdbeAddOp(v, OP_New, iParm, 0, 0, 0);
      sqliteVdbeAddOp(v, OP_Pull, 1, 0, 0, 0);
      sqliteVdbeAddOp(v, OP_Put, iParm, 0, 0, 0);
    }else if( eDest==SRT_Set ){
      sqliteVdbeAddOp(v, OP_String, 0, 0, "", 0);
      sqliteVdbeAddOp(v, OP_Put, iParm, 0, 0, 0);
    }else if( eDest==SRT_Mem ){
      sqliteVdbeAddOp(v, OP_MemStore, iParm, 0, 0, 0);
    }else{
      sqliteVdbeAddOp(v, OP_Callback, pEList->nExpr, 0, 0, 0);
    }
  }
  return 0;
}

** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.16 2000/06/06 01:50:43 drh Exp $
*/
#include "sqlite.h"
#include "dbbe.h"
#include "vdbe.h"
#include "parse.h"
#include <gdbm.h>
#include <stdio.h>

  IdList *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 */
};

/*
** The results of a select can be distributed in several ways.
*/
#define SRT_Callback     1  /* Invoke a callback with each row of result */
#define SRT_Mem          2  /* Store result in a memory cell */
#define SRT_Set          3  /* Store result in a table for use with "IN" */
#define SRT_Table        4  /* Store result in a regular table */

/*
** An SQL parser context
*/
struct Parse {
  sqlite *db;          /* The main database structure */
  sqlite_callback xCallback;  /* The callback function */
  void *pArg;          /* First argument to the callback function */
  char *zErrMsg;       /* An error message */
  Token sErrToken;     /* The token at which the error occurred */
  Token sFirstToken;   /* The first token parsed */
  Token sLastToken;    /* The last token parsed */
  Table *pNewTable;    /* A table being constructed by CREATE TABLE */
  Vdbe *pVdbe;         /* An engine for executing database bytecode */
  int explain;         /* True if the EXPLAIN flag is found on the query */
  int initFlag;        /* True if reparsing CREATE TABLEs */
  int nErr;            /* Number of errors seen */
  int nTab;            /* Number of previously allocated cursors */
  int nMem;            /* Number of memory cells used so far */
  int nSet;            /* Number of sets used so far */
};

/*
** Internal function prototypes
*/
int sqliteStrICmp(const char *, const char *);
int sqliteStrNICmp(const char *, const char *, int);

*************************************************************************
** An tokenizer for SQL
**
** This file contains C code that splits an SQL input string up into
** individual tokens and sends those tokens one-by-one over to the
** parser for analysis.
**
** $Id: tokenize.c,v 1.6 2000/06/06 01:50:43 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>
#include <stdlib.h>

/*
** All the keywords of the SQL language are stored as in a hash

  Keyword *pNext;          /* Next keyword with the same hash */
};

/*
** These are the keywords
*/
static Keyword aKeywordTable[] = {
  { "ALL",               0, TK_ALL,              0 },
  { "AND",               0, TK_AND,              0 },
  { "AS",                0, TK_AS,               0 },
  { "ASC",               0, TK_ASC,              0 },
  { "BETWEEN",           0, TK_BETWEEN,          0 },
  { "BY",                0, TK_BY,               0 },
  { "CHECK",             0, TK_CHECK,            0 },
  { "CONSTRAINT",        0, TK_CONSTRAINT,       0 },
  { "COPY",              0, TK_COPY,             0 },
  { "CREATE",            0, TK_CREATE,           0 },
  { "DEFAULT",           0, TK_DEFAULT,          0 },
  { "DELETE",            0, TK_DELETE,           0 },
  { "DELIMITERS",        0, TK_DELIMITERS,       0 },
  { "DESC",              0, TK_DESC,             0 },
  { "DISTINCT",          0, TK_DISTINCT,         0 },
  { "DROP",              0, TK_DROP,             0 },
  { "EXPLAIN",           0, TK_EXPLAIN,          0 },
  { "FROM",              0, TK_FROM,             0 },
  { "GLOB",              0, TK_GLOB,             0 },
  { "IN",                0, TK_IN,               0 },
  { "INDEX",             0, TK_INDEX,            0 },
  { "INSERT",            0, TK_INSERT,           0 },
  { "INTO",              0, TK_INTO,             0 },
  { "IS",                0, TK_IS,               0 },
  { "ISNULL",            0, TK_ISNULL,           0 },
  { "KEY",               0, TK_KEY,              0 },
  { "LIKE",              0, TK_LIKE,             0 },

** inplicit conversion from one 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.18 2000/06/06 01:50:43 drh Exp $
*/
#include "sqliteInt.h"
#include <unistd.h>

/*
** SQL is translated into a sequence of instructions to be
** executed by a virtual machine.  Each instruction is an instance

*/
struct Mem {
  Stack s;       /* All values of the memory cell besides string */
  char *z;       /* String value for this memory cell */
};
typedef struct Mem Mem;

/*
** Allowed values for Stack.flags
*/
#define STK_Null      0x0001   /* Value is NULL */
#define STK_Str       0x0002   /* Value is a string */
#define STK_Int       0x0004   /* Value is an integer */
#define STK_Real      0x0008   /* Value is a real number */
#define STK_Dyn       0x0010   /* Need to call sqliteFree() on zStack[*] */

/*
** An Agg structure describes and Aggregator.  Each Agg consists of
** zero or more Aggregator elements (AggElem).  Each AggElem contains
** a key and one or more values.  The values are used in processing
** aggregate functions in a SELECT.  The key is used to implement
** the GROUP BY clause of a select.
*/

  char *zKey;            /* The key to this AggElem */
  AggElem *pHash;        /* Next AggElem with the same hash on zKey */
  AggElem *pNext;        /* Next AggElem in a list of them all */
  Mem aMem[1];           /* The values for this AggElem */
};

/*
** A Set structure is used for quick testing to see if a value
** is part of a small set.  Sets are used to implement code like
** this:
**            x.y IN ('hi','hoo','hum')
*/

typedef struct Set Set;
typedef struct SetElem SetElem;
struct Set {
  SetElem *pAll;         /* All elements of this set */
  SetElem *apHash[41];   /* A hash table for all elements in this set */
};
struct SetElem {
  SetElem *pHash;        /* Next element with the same hash on zKey */
  SetElem *pNext;        /* Next element in a list of them all */
  char zKey[1];          /* Value of this key */


};

/*
** An instance of the virtual machine
*/
struct Vdbe {
  Dbbe *pBe;          /* Opaque context structure used by DB backend */
  FILE *trace;        /* Write an execution trace here, if not NULL */

  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 */
  int nMem;           /* Number of memory locations currently allocated */
  Mem *aMem;          /* The memory locations */
  Agg agg;            /* Aggregate information */
  int nSet;           /* Number of sets allocated */
  Set *aSet;          /* An array of sets */
};

/*
** Create a new virtual database engine.
*/
Vdbe *sqliteVdbeCreate(Dbbe *pBe){
  Vdbe *p;

    p->pCurrent = pFocus;
  }else{
    AggInsert(p,"");
    pFocus = p->pCurrent;
  }
  return pFocus;
}

/*
** Erase all information from a Set
*/
static void SetClear(Set *p){
  SetElem *pElem, *pNext;
  for(pElem=p->pAll; pElem; pElem=pNext){
    pNext = pElem->pNext;
    sqliteFree(pElem);
  }
  memset(p, 0, sizeof(*p));
}

/*
** Insert a new element into the set
*/
static void SetInsert(Set *p, char *zKey){
  SetElem *pElem;
  int h = sqliteHashNoCase(zKey, 0) % ArraySize(p->apHash);
  for(pElem=p->apHash[h]; pElem; pElem=pElem->pHash){
    if( strcmp(pElem->zKey, zKey)==0 ) return;
  }
  pElem = sqliteMalloc( sizeof(pElem) + strlen(zKey) );
  if( pElem==0 ) return;
  strcpy(pElem->zKey, zKey);
  pElem->pNext = p->pAll;
  p->pAll = pElem;
  pElem->pHash = p->apHash[h];
  p->apHash[h] = pElem;
}

/*
** Return TRUE if an element is in the set.  Return FALSE if not.
*/
static int SetTest(Set *p, char *zKey){
  SetElem *pElem;
  int h = sqliteHashNoCase(zKey, 0) % ArraySize(p->apHash);
  for(pElem=p->apHash[h]; pElem; pElem=pElem->pHash){
    if( strcmp(pElem->zKey, zKey)==0 ) return 1;
  }
  return 0;
}

/*
** Convert the given stack entity into a string if it isn't one
** already.  Return non-zero if we run out of memory.
**
** NULLs are converted into an empty string.
*/

  p->nField = 0;
  if( p->zLine ){
    sqliteFree(p->zLine);
    p->zLine = 0;
  }
  p->nLineAlloc = 0;
  AggReset(&p->agg);
  for(i=0; i<p->nSet; i++){
    SetClear(&p->aSet[i]);
  }
  sqliteFree(p->aSet);
  p->aSet = 0;
  p->nSet = 0;
}

/*
** Delete an entire VDBE.
*/
void sqliteVdbeDelete(Vdbe *p){
  int i;

** If any of the numeric OP_ values for opcodes defined in sqliteVdbe.h
** change, be sure to change this array to match.  You can use the
** "opNames.awk" awk script which is part of the source tree to regenerate
** this array, then copy and paste it into this file, if you want.
*/
static char *zOpName[] = { 0,
  "Open",           "Close",          "Fetch",          "New",
  "Put",            "Distinct",       "Found",          "NotFound",
  "Delete",         "Field",          "Key",            "Rewind",
  "Next",           "Destroy",        "Reorganize",     "ResetIdx",
  "NextIdx",        "PutIdx",         "DeleteIdx",      "MemLoad",
  "MemStore",       "ListOpen",       "ListWrite",      "ListRewind",
  "ListRead",       "ListClose",      "SortOpen",       "SortPut",
  "SortMakeRec",    "SortMakeKey",    "Sort",           "SortNext",
  "SortKey",        "SortCallback",   "SortClose",      "FileOpen",
  "FileRead",       "FileField",      "FileClose",      "AggReset",
  "AggFocus",       "AggIncr",        "AggNext",        "AggSet",
  "AggGet",         "SetInsert",      "SetFound",       "SetNotFound",
  "SetClear",       "MakeRecord",     "MakeKey",        "Goto",
  "If",             "Halt",           "ColumnCount",    "ColumnName",
  "Callback",       "Integer",        "String",         "Null",
  "Pop",            "Dup",            "Pull",           "Add",
  "AddImm",         "Subtract",       "Multiply",       "Divide",
  "Min",            "Max",            "Like",           "Glob",
  "Eq",             "Ne",             "Lt",             "Le",
  "Gt",             "Ge",             "IsNull",         "NotNull",
  "Negative",       "And",            "Or",             "Not",
  "Concat",         "Noop",         
};

/*
** Given the name of an opcode, return its number.  Return 0 if
** there is no match.
**
** This routine is used for testing and debugging.

      /* Opcode: Distinct P1 P2 *
      **
      ** Use the top of the stack as a key.  If a record with that key
      ** does not exist in table P1, then jump to P2.  If the record
      ** does already exist, then fall thru.  The record is not retrieved.
      ** The key is not popped from the stack.
      */
      /* Opcode: Found P1 P2 *
      **
      ** Use the top of the stack as a key.  If a record with that key
      ** does exist in table P1, then jump to P2.  If the record
      ** does not exist, then fall thru.  The record is not retrieved.
      ** The key is popped from the stack.
      */
      /* Opcode: NotFound P1 P2 *
      **
      ** Use the top of the stack as a key.  If a record with that key
      ** does exist in table P1, then jump to P2.  If the record
      ** does not exist, then fall thru.  The record is not retrieved.
      ** The key is popped from the stack.
      */
      case OP_Distinct:
      case OP_NotFound:
      case OP_Found: {
        int i = pOp->p1;
        int tos = p->tos;
        int alreadyExists = 0;
        if( tos<0 ) goto not_enough_stack;
        if( i>=0 && i<p->nTable && p->aTab[i].pTable ){
          if( p->aStack[tos].flags & STK_Int ){
            alreadyExists = sqliteDbbeTest(p->aTab[i].pTable, sizeof(int), 
                                          (char*)&p->aStack[tos].i);
          }else{
            if( Stringify(p, tos) ) goto no_mem;
            alreadyExists = sqliteDbbeTest(p->aTab[i].pTable, p->aStack[tos].n, 
                                           p->zStack[tos]);
          }
        }
        if( pOp->opcode==OP_Found ){
          if( alreadyExists ) pc = pOp->p2 - 1;
        }else{
          if( !alreadyExists ) pc = pOp->p2 - 1;
        }
        if( pOp->opcode!=OP_Distinct ){
          PopStack(p, 1);
        }
        break;
      }

      /* Opcode: New P1 * *
      **
      ** Get a new integer key not previous used by table P1 and

          p->agg.nElem--;
        }
        if( p->agg.pCurrent==0 ){
          pc = pOp->p2-1;
        }
        break;
      }

      /* Opcode: SetClear P1 * *
      **
      ** Remove all elements from the given Set.
      */
      case OP_SetClear: {
        int i = pOp->p1;
        if( i>=0 && i<p->nSet ){
          SetClear(&p->aSet[i]);
        }
        break;
      }

      /* Opcode: SetInsert P1 * P3
      **
      ** If Set p1 does not exist then create it.  Then insert value
      ** P3 into that set.  If P3 is NULL, then insert the top of the
      ** stack into the set.
      */
      case OP_SetInsert: {
        int i = pOp->p1;
        if( p->nSet<=i ){
          p->aSet = sqliteRealloc(p->aSet, (i+1)*sizeof(p->aSet[0]) );
          if( p->aSet==0 ) goto no_mem;
          memset(&p->aSet[p->nSet], 0, sizeof(p->aSet[0])*(i+1 - p->nSet));
          p->nSet = i+1;
        }
        if( pOp->p3 ){
          SetInsert(&p->aSet[i], pOp->p3);
        }else{
          int tos = p->tos;
          if( tos<0 ) goto not_enough_stack;
          Stringify(p, tos);
          SetInsert(&p->aSet[i], p->zStack[tos]);
          PopStack(p, 1);
        }
        break;
      }

      /* Opcode: SetFound P1 P2 *
      **
      ** Pop the stack once and compare the value popped off with the
      ** contents of set P1.  If the element popped exists in set P1,
      ** then jump to P2.  Otherwise fall through.
      */
      case OP_SetFound: {
        int i = pOp->p1;
        int tos = p->tos;
        if( tos<0 ) goto not_enough_stack;
        Stringify(p, tos);
        if( i>=0 && i<p->nSet && SetTest(&p->aSet[i], p->zStack[tos]) ){
          pc = pOp->p2 - 1;
        }
        PopStack(p, 1);
      }

      /* Opcode: SetNotFound P1 P2 *
      **
      ** Pop the stack once and compare the value popped off with the
      ** contents of set P1.  If the element popped does not exists in 
      ** set P1, then jump to P2.  Otherwise fall through.
      */
      case OP_SetNotFound: {
        int i = pOp->p1;
        int tos = p->tos;
        if( tos<0 ) goto not_enough_stack;
        Stringify(p, tos);
        if( i>=0 && i<p->nSet && !SetTest(&p->aSet[i], p->zStack[tos]) ){
          pc = pOp->p2 - 1;
        }
        PopStack(p, 1);
      }

      /* An other opcode is illegal...
      */
      default: {
        sprintf(zBuf,"%d",pOp->opcode);
        sqliteSetString(pzErrMsg, "unknown opcode ", zBuf, 0);
        rc = SQLITE_INTERNAL;

*************************************************************************
** Header file for the Virtual DataBase Engine (VDBE)
**
** This header defines the interface to the virtual database engine
** or VDBE.  The VDBE implements an abstract machine that runs a
** simple program to access and modify the underlying database.
**
** $Id: vdbe.h,v 1.8 2000/06/06 01:50:44 drh Exp $
*/
#ifndef _SQLITE_VDBE_H_
#define _SQLITE_VDBE_H_
#include <stdio.h>

/*
** A single VDBE is an opaque structure named "Vdbe".  Only routines

*/
#define OP_Open                1
#define OP_Close               2
#define OP_Fetch               3
#define OP_New                 4
#define OP_Put                 5
#define OP_Distinct            6
#define OP_Found               7
#define OP_NotFound            8
#define OP_Delete              9
#define OP_Field              10
#define OP_Key                11
#define OP_Rewind             12
#define OP_Next               13

#define OP_Destroy            14
#define OP_Reorganize         15

#define OP_ResetIdx           16
#define OP_NextIdx            17
#define OP_PutIdx             18
#define OP_DeleteIdx          19

#define OP_MemLoad            20
#define OP_MemStore           21

#define OP_ListOpen           22
#define OP_ListWrite          23
#define OP_ListRewind         24
#define OP_ListRead           25
#define OP_ListClose          26

#define OP_SortOpen           27
#define OP_SortPut            28
#define OP_SortMakeRec        29
#define OP_SortMakeKey        30
#define OP_Sort               31
#define OP_SortNext           32
#define OP_SortKey            33
#define OP_SortCallback       34
#define OP_SortClose          35

#define OP_FileOpen           36
#define OP_FileRead           37
#define OP_FileField          38
#define OP_FileClose          39

#define OP_AggReset           40
#define OP_AggFocus           41
#define OP_AggIncr            42
#define OP_AggNext            43
#define OP_AggSet             44
#define OP_AggGet             45

#define OP_SetInsert          46
#define OP_SetFound           47
#define OP_SetNotFound        48
#define OP_SetClear           49

#define OP_MakeRecord         50
#define OP_MakeKey            51

#define OP_Goto               52
#define OP_If                 53
#define OP_Halt               54

#define OP_ColumnCount        55
#define OP_ColumnName         56
#define OP_Callback           57

#define OP_Integer            58
#define OP_String             59
#define OP_Null               60
#define OP_Pop                61
#define OP_Dup                62
#define OP_Pull               63

#define OP_Add                64
#define OP_AddImm             65
#define OP_Subtract           66
#define OP_Multiply           67
#define OP_Divide             68
#define OP_Min                69
#define OP_Max                70
#define OP_Like               71
#define OP_Glob               72
#define OP_Eq                 73
#define OP_Ne                 74
#define OP_Lt                 75
#define OP_Le                 76
#define OP_Gt                 77
#define OP_Ge                 78
#define OP_IsNull             79
#define OP_NotNull            80
#define OP_Negative           81
#define OP_And                82
#define OP_Or                 83
#define OP_Not                84
#define OP_Concat             85
#define OP_Noop               86

#define OP_MAX                86

/*
** Prototypes for the VDBE interface.  See comments on the implementation
** for a description of what each of these routines does.
*/
Vdbe *sqliteVdbeCreate(Dbbe*);
int sqliteVdbeAddOp(Vdbe*,int,int,int,const char*,int);