SQLite

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This is the header file for the generic hash-table implemenation
** used in SQLite.
**
** $Id: hash.h,v 1.5 2002/06/08 23:25:09 drh Exp $
*/
#ifndef _SQLITE_HASH_H_
#define _SQLITE_HASH_H_

/* Forward declarations of structures. */
typedef struct Hash Hash;
typedef struct HashElem HashElem;

**     // do something with pData
**   }
*/
#define sqliteHashFirst(H)  ((H)->first)
#define sqliteHashNext(E)   ((E)->next)
#define sqliteHashData(E)   ((E)->data)
#define sqliteHashKey(E)    ((E)->pKey)
#define sqliteHashKeysize(E) ((E)->nKey)

/*
** Number of entries in a hash table
*/
#define sqliteHashCount(H)  ((H)->count)

#endif /* _SQLITE_HASH_H_ */

/*
** 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.121 2002/06/08 23:25:09 drh Exp $
*/
#include "sqlite.h"
#include "hash.h"
#include "vdbe.h"
#include "parse.h"
#include "btree.h"
#include <stdio.h>

** be the right operand of an IN operator.  Or, if a scalar SELECT appears
** in an expression the opcode is TK_SELECT and Expr.pSelect is the only
** operand.
*/
struct Expr {
  int op;                /* Operation performed by this node */
  Expr *pLeft, *pRight;  /* Left and right subnodes */
  ExprList *pList;       /* A list of expressions used as function arguments
                         ** or in "<expr> IN (<expr-list)" */
  Token token;           /* An operand token */
  Token span;            /* Complete text of the expression */
  int iTable, iColumn;   /* When op==TK_COLUMN, then this expr node means the
                         ** iColumn-th field of the iTable-th table.  When
                         ** op==TK_FUNCTION, iColumn holds the function id */
  int iAgg;              /* When op==TK_COLUMN and pParse->useAgg==TRUE, pull
                         ** result from the iAgg-th element of the aggregator */
  Select *pSelect;       /* When the expression is a sub-select.  Also the
                         ** right side of "<expr> IN (<select>)" */
};

/*
** 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

  int iCur;            /* Cursor number used for this index */
  int score;           /* How well this indexed scored */
  int brk;             /* Jump here to break out of the loop */
  int cont;            /* Jump here to continue with the next loop cycle */
  int op, p1, p2;      /* Opcode used to terminate the loop */
  int iLeftJoin;       /* Memory cell used to implement LEFT OUTER JOIN */
  int top;             /* First instruction of interior of the loop */
  int inOp, inP1, inP2;/* Opcode used to implement an IN operator */
};

/*
** The WHERE clause processing routine has two halves.  The
** 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

** 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.154 2002/06/08 23:25:09 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

** is part of a small set.  Sets are used to implement code like
** this:
**            x.y IN ('hi','hoo','hum')
*/
typedef struct Set Set;
struct Set {
  Hash hash;             /* A set is just a hash table */
  HashElem *prev;        /* Previously accessed hash elemen */
};

/*
** A Keylist is a bunch of keys into a table.  The keylist can
** grow without bound.  The keylist stores the ROWIDs of database
** records that need to be deleted or updated.
*/

  "IdxGE",             "MemLoad",           "MemStore",          "ListWrite",
  "ListRewind",        "ListRead",          "ListReset",         "ListPush",
  "ListPop",           "SortPut",           "SortMakeRec",       "SortMakeKey",
  "Sort",              "SortNext",          "SortCallback",      "SortReset",
  "FileOpen",          "FileRead",          "FileColumn",        "AggReset",
  "AggFocus",          "AggNext",           "AggSet",            "AggGet",
  "AggFunc",           "AggInit",           "AggPush",           "AggPop",
  "SetInsert",         "SetFound",          "SetNotFound",       "SetFirst",
  "SetNext",           "MakeRecord",        "MakeKey",           "MakeIdxKey",
  "IncrKey",           "Goto",              "If",                "IfNot",
  "Halt",              "ColumnCount",       "ColumnName",        "Callback",
  "NullCallback",      "Integer",           "String",            "Pop",
  "Dup",               "Pull",              "Push",              "MustBeInt",
  "Add",               "AddImm",            "Subtract",          "Multiply",
  "Divide",            "Remainder",         "BitAnd",            "BitOr",
  "BitNot",            "ShiftLeft",         "ShiftRight",        "AbsValue",
  "Eq",                "Ne",                "Lt",                "Le",
  "Gt",                "Ge",                "IsNull",            "NotNull",
  "Negative",          "And",               "Or",                "Not",
  "Concat",            "Noop",              "Function",          "Limit",
};

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

  aStack[tos].i += pOp->p1;
  break;
}

/* Opcode: MustBeInt  * P2 *
** 
** Force the top of the stack to be an integer.  If the top of the
** stack is not an integer and cannot be converted into an integer
** with out data loss, then jump immediately to P2, or if P2==0
** raise an SQLITE_MISMATCH exception.
*/
case OP_MustBeInt: {
  int tos = p->tos;
  VERIFY( if( tos<0 ) goto not_enough_stack; )
  if( aStack[tos].flags & STK_Int ){

** not exist in the table of cursor P1, then jump to P2.  If the record
** does already exist, then fall thru.  The cursor is left pointing
** at the record if it exists. The key is not popped from the stack.
**
** This operation is similar to NotFound except that this operation
** does not pop the key from the stack.
**
** See also: Found, NotFound, MoveTo, IsUnique, NotExists
*/
/* Opcode: Found P1 P2 *
**
** Use the top of the stack as a string key.  If a record with that key
** does exist in table of P1, then jump to P2.  If the record
** does not exist, then fall thru.  The cursor is left pointing
** to the record if it exists.  The key is popped from the stack.
**
** See also: Distinct, NotFound, MoveTo, IsUnique, NotExists
*/
/* Opcode: NotFound P1 P2 *
**
** Use the top of the stack as a string key.  If a record with that key
** does not exist in table of P1, then jump to P2.  If the record
** does exist, then fall thru.  The cursor is left pointing to the
** record if it exists.  The key is popped from the stack.

** index string matches K but the record number is different
** from R.  If there is no such entry, then there is an immediate
** jump to P2.  If any entry does exist where the index string
** matches K but the record number is not R, then the record
** number for that entry is pushed onto the stack and control
** falls through to the next instruction.
**
** See also: Distinct, NotFound, NotExists, Found
*/
case OP_IsUnique: {
  int i = pOp->p1;
  int tos = p->tos;
  int nos = tos-1;
  BtCursor *pCrsr;
  int R;

** does exist, then fall thru.  The cursor is left pointing to the
** record if it exists.  The integer key is popped from the stack.
**
** The difference between this operation and NotFound is that this
** operation assumes the key is an integer and NotFound assumes it
** is a string.
**
** See also: Distinct, Found, MoveTo, NotFound, IsUnique
*/
case OP_NotExists: {
  int i = pOp->p1;
  int tos = p->tos;
  BtCursor *pCrsr;
  VERIFY( if( tos<0 ) goto not_enough_stack; )
  if( VERIFY( i>=0 && i<p->nCursor && ) (pCrsr = p->aCsr[i].pCursor)!=0 ){

       sqliteHashFind(&p->aSet[i].hash, zStack[tos], aStack[tos].n)==0 ){
    pc = pOp->p2 - 1;
  }
  POPSTACK;
  break;
}

/* Opcode: SetFirst P1 P2 *
**
** Read the first element from set P1 and push it onto the stack.  If the
** set is empty, push nothing and jump immediately to P2.  This opcode is
** used in combination with OP_SetNext to loop over all elements of a set.
*/
/* Opcode: SetNext P1 P2 *
**
** Read the next element from set P1 and push it onto the stack.  If there
** are no more elements in the set, do not do the push and fall through.
** Otherwise, jump to P2 after pushing the next set element.
*/
case OP_SetFirst: 
case OP_SetNext: {
  Set *pSet;
  int tos;
  VERIFY( if( pOp->p1<0 || pOp->p1>=p->nSet ) goto bad_instruction; )
  pSet = &p->aSet[pOp->p1];
  if( pOp->opcode==OP_SetFirst ){
    pSet->prev = sqliteHashFirst(&pSet->hash);
    if( pSet->prev==0 ){
      pc = pOp->p2 - 1;
      break;
    }
  }else{
    VERIFY( if( pSet->prev==0 ) goto bad_instruction; )
    pSet->prev = sqliteHashNext(pSet->prev);
    if( pSet->prev==0 ){
      break;
    }else{
      pc = pOp->p2 - 1;
    }
  }
  tos = ++p->tos;
  VERIFY( if( NeedStack(p, p->tos) ) goto no_mem; )
  zStack[tos] = sqliteHashKey(pSet->prev);
  aStack[tos].n = sqliteHashKeysize(pSet->prev);
  aStack[tos].flags = STK_Str | STK_Static;
  break;
}

/* 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.54 2002/06/08 23:25:09 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_AggInit            66
#define OP_AggPush            67
#define OP_AggPop             68

#define OP_SetInsert          69
#define OP_SetFound           70
#define OP_SetNotFound        71
#define OP_SetFirst           72
#define OP_SetNext            73

#define OP_MakeRecord         74
#define OP_MakeKey            75
#define OP_MakeIdxKey         76
#define OP_IncrKey            77

#define OP_Goto               78
#define OP_If                 79
#define OP_IfNot              80
#define OP_Halt               81

#define OP_ColumnCount        82
#define OP_ColumnName         83
#define OP_Callback           84
#define OP_NullCallback       85

#define OP_Integer            86
#define OP_String             87
#define OP_Pop                88
#define OP_Dup                89
#define OP_Pull               90
#define OP_Push               91
#define OP_MustBeInt          92

#define OP_Add                93
#define OP_AddImm             94
#define OP_Subtract           95
#define OP_Multiply           96
#define OP_Divide             97
#define OP_Remainder          98
#define OP_BitAnd             99
#define OP_BitOr             100
#define OP_BitNot            101
#define OP_ShiftLeft         102
#define OP_ShiftRight        103
#define OP_AbsValue          104
#define OP_Eq                105
#define OP_Ne                106
#define OP_Lt                107
#define OP_Le                108
#define OP_Gt                109
#define OP_Ge                110
#define OP_IsNull            111
#define OP_NotNull           112
#define OP_Negative          113
#define OP_And               114
#define OP_Or                115
#define OP_Not               116
#define OP_Concat            117
#define OP_Noop              118
#define OP_Function          119

#define OP_Limit             120


#define OP_MAX               120

/*
** Prototypes for the VDBE interface.  See comments on the implementation
** for a description of what each of these routines does.
*/
Vdbe *sqliteVdbeCreate(sqlite*);
void sqliteVdbeCreateCallback(Vdbe*, int*);

**    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.49 2002/06/08 23:25:10 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.

static int allowedOp(int op){
  switch( op ){
    case TK_LT:
    case TK_LE:
    case TK_GT:
    case TK_GE:
    case TK_EQ:
    case TK_IN:
      return 1;
    default:
      return 0;
  }
}

/*

  pInfo->prereqLeft = exprTableUsage(base, pExpr->pLeft);
  pInfo->prereqRight = exprTableUsage(base, pExpr->pRight);
  pInfo->prereqAll = exprTableUsage(base, pExpr);
  pInfo->indexable = 0;
  pInfo->idxLeft = -1;
  pInfo->idxRight = -1;
  if( allowedOp(pExpr->op) && (pInfo->prereqRight & pInfo->prereqLeft)==0 ){
    if( pExpr->pRight && pExpr->pRight->op==TK_COLUMN ){
      pInfo->idxRight = pExpr->pRight->iTable - base;
      pInfo->indexable = 1;
    }
    if( pExpr->pLeft->op==TK_COLUMN ){
      pInfo->idxLeft = pExpr->pLeft->iTable - base;
      pInfo->indexable = 1;
    }

    iDirectEq[i] = -1;
    iDirectLt[i] = -1;
    iDirectGt[i] = -1;
    for(j=0; j<nExpr; j++){
      if( aExpr[j].idxLeft==idx && aExpr[j].p->pLeft->iColumn<0
            && (aExpr[j].prereqRight & loopMask)==aExpr[j].prereqRight ){
        switch( aExpr[j].p->op ){
          case TK_IN:
          case TK_EQ: iDirectEq[i] = j; break;
          case TK_LE:
          case TK_LT: iDirectLt[i] = j; break;
          case TK_GE:
          case TK_GT: iDirectGt[i] = j;  break;
        }
      }

    **
    ** This scoring system is designed so that the score can later be
    ** used to determine how the index is used.  If the score&3 is 0
    ** then all constraints are equalities.  If score&1 is not 0 then
    ** there is an inequality used as a termination key.  (ex: "x<...")
    ** If score&2 is not 0 then there is an inequality used as the
    ** start key.  (ex: "x>...");
    **
    ** The IN operator as in "<expr> IN (...)" is treated the same as
    ** an equality comparison.
    */
    for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
      int eqMask = 0;  /* Index columns covered by an x=... constraint */
      int ltMask = 0;  /* Index columns covered by an x<... constraint */
      int gtMask = 0;  /* Index columns covered by an x>... constraing */
      int nEq, m, score;

      if( pIdx->isDropped ) continue;   /* Ignore dropped indices */
      if( pIdx->nColumn>32 ) continue;  /* Ignore indices too many columns */
      for(j=0; j<nExpr; j++){
        if( aExpr[j].idxLeft==idx 
             && (aExpr[j].prereqRight & loopMask)==aExpr[j].prereqRight ){
          int iColumn = aExpr[j].p->pLeft->iColumn;
          int k;
          for(k=0; k<pIdx->nColumn; k++){
            if( pIdx->aiColumn[k]==iColumn ){
              switch( aExpr[j].p->op ){
                case TK_IN:
                case TK_EQ: {
                  eqMask |= 1<<k;
                  break;
                }
                case TK_LE:
                case TK_LT: {
                  ltMask |= 1<<k;

      if( !pParse->nMem ) pParse->nMem++;
      pLevel->iLeftJoin = pParse->nMem++;
      sqliteVdbeAddOp(v, OP_String, 0, 0);
      sqliteVdbeAddOp(v, OP_MemStore, pLevel->iLeftJoin, 1);
    }

    pIdx = pLevel->pIdx;
    pLevel->inOp = OP_Noop;
    if( i<ARRAYSIZE(iDirectEq) && iDirectEq[i]>=0 ){
      /* Case 1:  We can directly reference a single row using an
      **          equality comparison against the ROWID field.
      */
      k = iDirectEq[i];
      assert( k<nExpr );
      assert( aExpr[k].p!=0 );
      assert( aExpr[k].idxLeft==idx || aExpr[k].idxRight==idx );
      brk = pLevel->brk = sqliteVdbeMakeLabel(v);
      if( aExpr[k].idxLeft==idx ){
        Expr *pX = aExpr[k].p;
        if( pX->op!=TK_IN ){
          sqliteExprCode(pParse, aExpr[k].p->pRight);
        }else if( pX->pList ){
          sqliteVdbeAddOp(v, OP_SetFirst, pX->iTable, brk);
          pLevel->inOp = OP_SetNext;
          pLevel->inP1 = pX->iTable;
          pLevel->inP2 = sqliteVdbeCurrentAddr(v);
        }else{
          assert( pX->pSelect );
          sqliteVdbeAddOp(v, OP_Rewind, pX->iTable, brk);
          sqliteVdbeAddOp(v, OP_KeyAsData, pX->iTable, 1);
          pLevel->inP2 = sqliteVdbeAddOp(v, OP_FullKey, pX->iTable, 0);
          pLevel->inOp = OP_Next;
          pLevel->inP1 = pX->iTable;
        }
      }else{
        sqliteExprCode(pParse, aExpr[k].p->pLeft);
      }
      aExpr[k].p = 0;

      cont = pLevel->cont = sqliteVdbeMakeLabel(v);
      sqliteVdbeAddOp(v, OP_MustBeInt, 0, brk);













      haveKey = 0;

      sqliteVdbeAddOp(v, OP_NotExists, base+idx, brk);
      pLevel->op = OP_Noop;
    }else if( pIdx!=0 && pLevel->score%4==0 ){
      /* Case 2:  All index constraints are equality operators.
      */
      int start;
      int testOp;
      int nColumn = pLevel->score/4;
      brk = pLevel->brk = sqliteVdbeMakeLabel(v);
      for(j=0; j<nColumn; j++){
        for(k=0; k<nExpr; k++){
          Expr *pX = aExpr[k].p;
          if( pX==0 ) continue;
          if( aExpr[k].idxLeft==idx 

             && (aExpr[k].prereqRight & loopMask)==aExpr[k].prereqRight 
             && pX->pLeft->iColumn==pIdx->aiColumn[j]
          ){
            if( pX->op==TK_EQ ){
              sqliteExprCode(pParse, pX->pRight);
              aExpr[k].p = 0;
              break;
            }
            if( pX->op==TK_IN && nColumn==1 ){
              if( pX->pList ){
                sqliteVdbeAddOp(v, OP_SetFirst, pX->iTable, brk);
                pLevel->inOp = OP_SetNext;
                pLevel->inP1 = pX->iTable;
                pLevel->inP2 = sqliteVdbeCurrentAddr(v);
              }else{
                assert( pX->pSelect );
                sqliteVdbeAddOp(v, OP_Rewind, pX->iTable, brk);
                sqliteVdbeAddOp(v, OP_KeyAsData, pX->iTable, 1);
                pLevel->inP2 = sqliteVdbeAddOp(v, OP_FullKey, pX->iTable, 0);
                pLevel->inOp = OP_Next;
                pLevel->inP1 = pX->iTable;
              }
              aExpr[k].p = 0;
              break;
            }
          }
          if( aExpr[k].idxRight==idx 
             && aExpr[k].p->op==TK_EQ
             && (aExpr[k].prereqLeft & loopMask)==aExpr[k].prereqLeft
             && aExpr[k].p->pRight->iColumn==pIdx->aiColumn[j]
          ){
            sqliteExprCode(pParse, aExpr[k].p->pLeft);
            aExpr[k].p = 0;
            break;
          }
        }
      }
      pLevel->iMem = pParse->nMem++;

      cont = pLevel->cont = sqliteVdbeMakeLabel(v);
      sqliteVdbeAddOp(v, OP_MakeKey, nColumn, 0);
      if( nColumn==pIdx->nColumn ){
        sqliteVdbeAddOp(v, OP_MemStore, pLevel->iMem, 0);
        testOp = OP_IdxGT;
      }else{
        sqliteVdbeAddOp(v, OP_Dup, 0, 0);

  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);
    if( pLevel->inOp!=OP_Noop ){
      sqliteVdbeAddOp(v, pLevel->inOp, pLevel->inP1, pLevel->inP2);
    }
    if( pLevel->iLeftJoin ){
      int addr;
      addr = sqliteVdbeAddOp(v, OP_MemLoad, pLevel->iLeftJoin, 0);
      sqliteVdbeAddOp(v, OP_NotNull, 0, addr+4);
      sqliteVdbeAddOp(v, OP_NullRow, base+i, 0);
      sqliteVdbeAddOp(v, OP_Goto, 0, pLevel->top);
    }