**    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.316 2007/11/12 09:50:26 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** Return the 'affinity' of the expression pExpr if any.
**
................................................................................
*/
typedef struct QueryCoder QueryCoder;
struct QueryCoder {
  Parse *pParse;       /* The parsing context */
  NameContext *pNC;    /* Namespace of first enclosing query */
};











































































































































/*
** Generate code for scalar subqueries used as an expression
** and IN operators.  Examples:
**
**     (SELECT a FROM b)          -- subquery
**     EXISTS (SELECT a FROM b)   -- EXISTS subquery
................................................................................
      VdbeComment((v, "# load subquery result"));
      break;
    }
    case TK_IN: {
      int addr;
      char affinity;
      int ckOffset = pParse->ckOffset;
      sqlite3CodeSubselect(pParse, pExpr);




      /* Figure out the affinity to use to create a key from the results
      ** of the expression. affinityStr stores a static string suitable for
      ** P3 of OP_MakeRecord.
      */
      affinity = comparisonAffinity(pExpr);

................................................................................
      ** pExpr->iTable contains the values that make up the (...) set.
      */
      sqlite3ExprCode(pParse, pExpr->pLeft);
      addr = sqlite3VdbeCurrentAddr(v);
      sqlite3VdbeAddOp(v, OP_NotNull, -1, addr+4);            /* addr + 0 */
      sqlite3VdbeAddOp(v, OP_Pop, 2, 0);
      sqlite3VdbeAddOp(v, OP_Null, 0, 0);
      sqlite3VdbeAddOp(v, OP_Goto, 0, addr+7);






      sqlite3VdbeOp3(v, OP_MakeRecord, 1, 0, &affinity, 1);   /* addr + 4 */
      sqlite3VdbeAddOp(v, OP_Found, pExpr->iTable, addr+7);

      sqlite3VdbeAddOp(v, OP_AddImm, -1, 0);                  /* addr + 6 */


      break;
    }
#endif
    case TK_BETWEEN: {
      Expr *pLeft = pExpr->pLeft;
      struct ExprList_item *pLItem = pExpr->pList->a;

**    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.317 2007/11/29 17:05:18 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** Return the 'affinity' of the expression pExpr if any.
**
................................................................................
*/
typedef struct QueryCoder QueryCoder;
struct QueryCoder {
  Parse *pParse;       /* The parsing context */
  NameContext *pNC;    /* Namespace of first enclosing query */
};

#ifdef SQLITE_TEST
  int sqlite3_enable_in_opt = 1;
#else
  #define sqlite3_enable_in_opt 1
#endif

/*
** This function is used by the implementation of the IN (...) operator.
** It's job is to find or create a b-tree structure that may be used
** either to test for membership of the (...) set or to iterate through
** it's members, skipping duplicates.
**
** The cursor opened on the structure (database table, database index 
** or ephermal table) is stored in pX->iTable before this function returns.
** The returned value indicates the structure type, as follows:
**
**   IN_INDEX_ROWID - The cursor was opened on a database table.
**   IN_INDEX_INDEX - The cursor was opened on a database indec.
**   IN_INDEX_EPH -   The cursor was opened on a specially created and
**                    populated epheremal table.
**
** An existing structure may only be used if the SELECT is of the simple
** form:
**
**     SELECT <column> FROM <table>
**
** If the mustBeUnique parameter is false, the structure will be used 
** for fast set membership tests. In this case an epheremal table must 
** be used unless <column> is an INTEGER PRIMARY KEY or an index can 
** be found with <column> as it's left-most column.
**
** If mustBeUnique is true, then the structure will be used to iterate
** through the set members, skipping any duplicates. In this case an
** epheremal table must be used unless the selected <column> is guaranteed
** to be unique - either because it is an INTEGER PRIMARY KEY or it
** is unique by virtue of a constraint or implicit index.
*/
int sqlite3FindInIndex(Parse *pParse, Expr *pX, int mustBeUnique){
  Select *p;
  int eType = 0;
  int iTab = pParse->nTab++;

  /* The follwing if(...) expression is true if the SELECT is of the 
  ** simple form:
  **
  **     SELECT <column> FROM <table>
  **
  ** If this is the case, it may be possible to use an existing table
  ** or index instead of generating an epheremal table.
  */
  if( sqlite3_enable_in_opt
   && (p=pX->pSelect) && !p->pPrior
   && !p->isDistinct && !p->isAgg && !p->pGroupBy
   && p->pSrc && p->pSrc->nSrc==1 && !p->pSrc->a[0].pSelect
   && !p->pSrc->a[0].pTab->pSelect                                  
   && p->pEList->nExpr==1 && p->pEList->a[0].pExpr->op==TK_COLUMN
   && !p->pLimit && !p->pOffset && !p->pWhere
  ){
    sqlite3 *db = pParse->db;
    Index *pIdx;
    Expr *pExpr = p->pEList->a[0].pExpr;
    int iCol = pExpr->iColumn;
    Vdbe *v = sqlite3GetVdbe(pParse);

    /* This function is only called from two places. In both cases the vdbe
    ** has already been allocated. So assume sqlite3GetVdbe() is always
    ** successful here.
    */
    assert(v);
    if( iCol<0 ){
      int iMem = pParse->nMem++;
      int iAddr;
      Table *pTab = p->pSrc->a[0].pTab;
      int iDb = sqlite3SchemaToIndex(db, pTab->pSchema);
      sqlite3VdbeUsesBtree(v, iDb);

      sqlite3VdbeAddOp(v, OP_MemLoad, iMem, 0);
      iAddr = sqlite3VdbeAddOp(v, OP_If, 0, iMem);
      sqlite3VdbeAddOp(v, OP_MemInt, 1, iMem);

      sqlite3OpenTable(pParse, iTab, iDb, pTab, OP_OpenRead);
      eType = IN_INDEX_ROWID;

      sqlite3VdbeJumpHere(v, iAddr);
    }else{
      /* The collation sequence used by the comparison. If an index is to 
      ** be used in place of a temp-table, it must be ordered according
      ** to this collation sequence.
      */
      CollSeq *pReq = sqlite3BinaryCompareCollSeq(pParse, pX->pLeft, pExpr);

      /* Check that the affinity that will be used to perform the 
      ** comparison is the same as the affinity of the column. If
      ** it is not, it is not possible to use any index.
      */
      Table *pTab = p->pSrc->a[0].pTab;
      char aff = comparisonAffinity(pX);
      int affinity_ok = (pTab->aCol[iCol].affinity==aff||aff==SQLITE_AFF_NONE);

      for(pIdx=pTab->pIndex; pIdx && eType==0 && affinity_ok; pIdx=pIdx->pNext){
        if( (pIdx->aiColumn[0]==iCol)
         && (pReq==sqlite3FindCollSeq(db, ENC(db), pIdx->azColl[0], -1, 0))
         && (!mustBeUnique || (pIdx->nColumn==1 && pIdx->onError!=OE_None))
        ){
          int iDb;
          int iMem = pParse->nMem++;
          int iAddr;
          char *pKey;
  
          pKey = (char *)sqlite3IndexKeyinfo(pParse, pIdx);
          iDb = sqlite3SchemaToIndex(db, pIdx->pSchema);
          sqlite3VdbeUsesBtree(v, iDb);

          sqlite3VdbeAddOp(v, OP_MemLoad, iMem, 0);
          iAddr = sqlite3VdbeAddOp(v, OP_If, 0, iMem);
          sqlite3VdbeAddOp(v, OP_MemInt, 1, iMem);
  
          sqlite3VdbeAddOp(v, OP_Integer, iDb, 0);
          VdbeComment((v, "# %s", pIdx->zName));
          sqlite3VdbeOp3(v,OP_OpenRead,iTab,pIdx->tnum,pKey,P3_KEYINFO_HANDOFF);
          eType = IN_INDEX_INDEX;
          sqlite3VdbeAddOp(v, OP_SetNumColumns, iTab, pIdx->nColumn);

          sqlite3VdbeJumpHere(v, iAddr);
        }
      }
    }
  }

  if( eType==0 ){
    sqlite3CodeSubselect(pParse, pX);
    eType = IN_INDEX_EPH;
  }else{
    pX->iTable = iTab;
  }
  return eType;
}

/*
** Generate code for scalar subqueries used as an expression
** and IN operators.  Examples:
**
**     (SELECT a FROM b)          -- subquery
**     EXISTS (SELECT a FROM b)   -- EXISTS subquery
................................................................................
      VdbeComment((v, "# load subquery result"));
      break;
    }
    case TK_IN: {
      int addr;
      char affinity;
      int ckOffset = pParse->ckOffset;
      int eType;
      int iLabel = sqlite3VdbeMakeLabel(v);

      eType = sqlite3FindInIndex(pParse, pExpr, 0);

      /* Figure out the affinity to use to create a key from the results
      ** of the expression. affinityStr stores a static string suitable for
      ** P3 of OP_MakeRecord.
      */
      affinity = comparisonAffinity(pExpr);

................................................................................
      ** pExpr->iTable contains the values that make up the (...) set.
      */
      sqlite3ExprCode(pParse, pExpr->pLeft);
      addr = sqlite3VdbeCurrentAddr(v);
      sqlite3VdbeAddOp(v, OP_NotNull, -1, addr+4);            /* addr + 0 */
      sqlite3VdbeAddOp(v, OP_Pop, 2, 0);
      sqlite3VdbeAddOp(v, OP_Null, 0, 0);
      sqlite3VdbeAddOp(v, OP_Goto, 0, iLabel);
      if( eType==IN_INDEX_ROWID ){
        int iAddr = sqlite3VdbeCurrentAddr(v)+3;
        sqlite3VdbeAddOp(v, OP_MustBeInt, 1, iAddr);
        sqlite3VdbeAddOp(v, OP_NotExists, pExpr->iTable, iAddr);
        sqlite3VdbeAddOp(v, OP_Goto, pExpr->iTable, iLabel);
      }else{
        sqlite3VdbeOp3(v, OP_MakeRecord, 1, 0, &affinity, 1);   /* addr + 4 */
        sqlite3VdbeAddOp(v, OP_Found, pExpr->iTable, iLabel);
      }
      sqlite3VdbeAddOp(v, OP_AddImm, -1, 0);                  /* addr + 6 */
      sqlite3VdbeResolveLabel(v, iLabel);

      break;
    }
#endif
    case TK_BETWEEN: {
      Expr *pLeft = pExpr->pLeft;
      struct ExprList_item *pLItem = pExpr->pList->a;

**    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.621 2007/11/28 22:36:41 drh Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

/*
** The macro unlikely() is a hint that surrounds a boolean
** expression that is usually false.  Macro likely() surrounds
................................................................................
** otherwise be equal, then return a result as if the second key
** were larger.
*/
struct KeyInfo {
  sqlite3 *db;        /* The database connection */
  u8 enc;             /* Text encoding - one of the TEXT_Utf* values */
  u8 incrKey;         /* Increase 2nd key by epsilon before comparison */

  int nField;         /* Number of entries in aColl[] */
  u8 *aSortOrder;     /* If defined an aSortOrder[i] is true, sort DESC */
  CollSeq *aColl[1];  /* Collating sequence for each term of the key */
};

/*
** Each SQL index is represented in memory by an
................................................................................
int sqlite3VtabBegin(sqlite3 *, sqlite3_vtab *);
FuncDef *sqlite3VtabOverloadFunction(sqlite3 *,FuncDef*, int nArg, Expr*);
void sqlite3InvalidFunction(sqlite3_context*,int,sqlite3_value**);
int sqlite3Reprepare(Vdbe*);
void sqlite3ExprListCheckLength(Parse*, ExprList*, int, const char*);
CollSeq *sqlite3BinaryCompareCollSeq(Parse *, Expr *, Expr *);






#ifdef SQLITE_ENABLE_ATOMIC_WRITE
  int sqlite3JournalOpen(sqlite3_vfs *, const char *, sqlite3_file *, int, int);
  int sqlite3JournalSize(sqlite3_vfs *);
  int sqlite3JournalCreate(sqlite3_file *);
#else
  #define sqlite3JournalSize(pVfs) ((pVfs)->szOsFile)
#endif

**    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.622 2007/11/29 17:05:18 danielk1977 Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

/*
** The macro unlikely() is a hint that surrounds a boolean
** expression that is usually false.  Macro likely() surrounds
................................................................................
** otherwise be equal, then return a result as if the second key
** were larger.
*/
struct KeyInfo {
  sqlite3 *db;        /* The database connection */
  u8 enc;             /* Text encoding - one of the TEXT_Utf* values */
  u8 incrKey;         /* Increase 2nd key by epsilon before comparison */
  u8 prefixIsEqual;   /* Treat a prefix as equal */
  int nField;         /* Number of entries in aColl[] */
  u8 *aSortOrder;     /* If defined an aSortOrder[i] is true, sort DESC */
  CollSeq *aColl[1];  /* Collating sequence for each term of the key */
};

/*
** Each SQL index is represented in memory by an
................................................................................
int sqlite3VtabBegin(sqlite3 *, sqlite3_vtab *);
FuncDef *sqlite3VtabOverloadFunction(sqlite3 *,FuncDef*, int nArg, Expr*);
void sqlite3InvalidFunction(sqlite3_context*,int,sqlite3_value**);
int sqlite3Reprepare(Vdbe*);
void sqlite3ExprListCheckLength(Parse*, ExprList*, int, const char*);
CollSeq *sqlite3BinaryCompareCollSeq(Parse *, Expr *, Expr *);

#define IN_INDEX_ROWID           1
#define IN_INDEX_EPH             2
#define IN_INDEX_INDEX           3
int sqlite3FindInIndex(Parse *, Expr *, int);

#ifdef SQLITE_ENABLE_ATOMIC_WRITE
  int sqlite3JournalOpen(sqlite3_vfs *, const char *, sqlite3_file *, int, int);
  int sqlite3JournalSize(sqlite3_vfs *);
  int sqlite3JournalCreate(sqlite3_file *);
#else
  #define sqlite3JournalSize(pVfs) ((pVfs)->szOsFile)
#endif

**    May you share freely, never taking more than you give.
**
*************************************************************************
** Code for testing all sorts of SQLite interfaces.  This code
** is not included in the SQLite library.  It is used for automated
** testing of the SQLite library.
**
** $Id: test1.c,v 1.279 2007/10/23 15:39:45 drh Exp $
*/
#include "sqliteInt.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>

/*
................................................................................
#endif
#ifdef SQLITE_DEBUG
  extern int sqlite3_where_trace;
  extern int sqlite3_os_trace;
  extern int sqlite3_vdbe_addop_trace;
#endif
#ifdef SQLITE_TEST

  extern char sqlite3_query_plan[];
  static char *query_plan = sqlite3_query_plan;
#endif

  for(i=0; i<sizeof(aCmd)/sizeof(aCmd[0]); i++){
    Tcl_CreateCommand(interp, aCmd[i].zName, aCmd[i].xProc, 0, 0);
  }
................................................................................
      (char*)&sqlite3_temp_directory, TCL_LINK_STRING);
  Tcl_LinkVar(interp, "bitmask_size",
      (char*)&bitmask_size, TCL_LINK_INT|TCL_LINK_READ_ONLY);
  Tcl_LinkVar(interp, "sqlite_sync_count",
      (char*)&sqlite3_sync_count, TCL_LINK_INT);
  Tcl_LinkVar(interp, "sqlite_fullsync_count",
      (char*)&sqlite3_fullsync_count, TCL_LINK_INT);




  return TCL_OK;
}

**    May you share freely, never taking more than you give.
**
*************************************************************************
** Code for testing all sorts of SQLite interfaces.  This code
** is not included in the SQLite library.  It is used for automated
** testing of the SQLite library.
**
** $Id: test1.c,v 1.280 2007/11/29 17:05:18 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>

/*
................................................................................
#endif
#ifdef SQLITE_DEBUG
  extern int sqlite3_where_trace;
  extern int sqlite3_os_trace;
  extern int sqlite3_vdbe_addop_trace;
#endif
#ifdef SQLITE_TEST
  extern int sqlite3_enable_in_opt;
  extern char sqlite3_query_plan[];
  static char *query_plan = sqlite3_query_plan;
#endif

  for(i=0; i<sizeof(aCmd)/sizeof(aCmd[0]); i++){
    Tcl_CreateCommand(interp, aCmd[i].zName, aCmd[i].xProc, 0, 0);
  }
................................................................................
      (char*)&sqlite3_temp_directory, TCL_LINK_STRING);
  Tcl_LinkVar(interp, "bitmask_size",
      (char*)&bitmask_size, TCL_LINK_INT|TCL_LINK_READ_ONLY);
  Tcl_LinkVar(interp, "sqlite_sync_count",
      (char*)&sqlite3_sync_count, TCL_LINK_INT);
  Tcl_LinkVar(interp, "sqlite_fullsync_count",
      (char*)&sqlite3_fullsync_count, TCL_LINK_INT);
#ifdef SQLITE_TEST
  Tcl_LinkVar(interp, "sqlite_enable_in_opt",
      (char*)&sqlite3_enable_in_opt, TCL_LINK_INT);
#endif
  return TCL_OK;
}

**
** Various scripts scan this source file in order to generate HTML
** documentation, headers files, or other derived files.  The formatting
** of the code in this file is, therefore, important.  See other comments
** in this file for details.  If in doubt, do not deviate from existing
** commenting and indentation practices when changing or adding code.
**
** $Id: vdbe.c,v 1.654 2007/11/12 08:09:35 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>
#include "vdbeInt.h"

/*
** The following global variable is incremented every time a cursor
................................................................................
  break;
}

/* Opcode: MustBeInt P1 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.
**
** If the top of the stack is not an integer and P2 is not zero and
** P1 is 1, then the stack is popped.  In all other cases, the depth
** of the stack is unchanged.
*/
case OP_MustBeInt: {            /* no-push */
................................................................................
** Top of the stack holds a blob constructed by MakeRecord.  P1 is an index.
** If an entry that matches the top of the stack exists in P1 then
** jump to P2.  If the top of the stack does not match any entry in P1
** then fall thru.  The P1 cursor is left pointing at the matching entry
** if it exists.  The blob is popped off the top of the stack.
**
** This instruction is used to implement the IN operator where the
** left-hand side is a SELECT statement.  P1 is not a true index but
** is instead a temporary index that holds the results of the SELECT
** statement.  This instruction just checks to see if the left-hand side
** of the IN operator (stored on the top of the stack) exists in the
** result of the SELECT statement.





**
** See also: Distinct, NotFound, MoveTo, IsUnique, NotExists
*/
/* Opcode: NotFound P1 P2 *
**
** The top of the stack holds a blob constructed by MakeRecord.  P1 is
** an index.  If no entry exists in P1 that matches the blob then jump
................................................................................
  assert( i>=0 && i<p->nCursor );
  assert( p->apCsr[i]!=0 );
  if( (pC = p->apCsr[i])->pCursor!=0 ){
    int res;
    assert( pC->isTable==0 );
    assert( pTos->flags & MEM_Blob );
    Stringify(pTos, encoding);



    rc = sqlite3BtreeMoveto(pC->pCursor, pTos->z, pTos->n, 0, &res);

    if( rc!=SQLITE_OK ){
      break;
    }
    alreadyExists = (res==0);
    pC->deferredMoveto = 0;
    pC->cacheStatus = CACHE_STALE;
  }

**
** Various scripts scan this source file in order to generate HTML
** documentation, headers files, or other derived files.  The formatting
** of the code in this file is, therefore, important.  See other comments
** in this file for details.  If in doubt, do not deviate from existing
** commenting and indentation practices when changing or adding code.
**
** $Id: vdbe.c,v 1.655 2007/11/29 17:05:18 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>
#include "vdbeInt.h"

/*
** The following global variable is incremented every time a cursor
................................................................................
  break;
}

/* Opcode: MustBeInt P1 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
** without data loss, then jump immediately to P2, or if P2==0
** raise an SQLITE_MISMATCH exception.
**
** If the top of the stack is not an integer and P2 is not zero and
** P1 is 1, then the stack is popped.  In all other cases, the depth
** of the stack is unchanged.
*/
case OP_MustBeInt: {            /* no-push */
................................................................................
** Top of the stack holds a blob constructed by MakeRecord.  P1 is an index.
** If an entry that matches the top of the stack exists in P1 then
** jump to P2.  If the top of the stack does not match any entry in P1
** then fall thru.  The P1 cursor is left pointing at the matching entry
** if it exists.  The blob is popped off the top of the stack.
**
** This instruction is used to implement the IN operator where the
** left-hand side is a SELECT statement.  P1 may be a true index, or it
** may be a temporary index that holds the results of the SELECT


** statement. 
**
** This instruction checks if index P1 contains a record for which 
** the first N serialised values exactly match the N serialised values
** in the record on the stack, where N is the total number of values in
** the stack record (stack record is a prefix of the P1 record). 
**
** See also: Distinct, NotFound, MoveTo, IsUnique, NotExists
*/
/* Opcode: NotFound P1 P2 *
**
** The top of the stack holds a blob constructed by MakeRecord.  P1 is
** an index.  If no entry exists in P1 that matches the blob then jump
................................................................................
  assert( i>=0 && i<p->nCursor );
  assert( p->apCsr[i]!=0 );
  if( (pC = p->apCsr[i])->pCursor!=0 ){
    int res;
    assert( pC->isTable==0 );
    assert( pTos->flags & MEM_Blob );
    Stringify(pTos, encoding);
    if( pOp->opcode==OP_Found ){
      pC->pKeyInfo->prefixIsEqual = 1;
    }
    rc = sqlite3BtreeMoveto(pC->pCursor, pTos->z, pTos->n, 0, &res);
    pC->pKeyInfo->prefixIsEqual = 0;
    if( rc!=SQLITE_OK ){
      break;
    }
    alreadyExists = (res==0);
    pC->deferredMoveto = 0;
    pC->cacheStatus = CACHE_STALE;
  }

  /* One of the keys ran out of fields, but all the fields up to that point
  ** were equal. If the incrKey flag is true, then the second key is
  ** treated as larger.
  */
  if( rc==0 ){
    if( pKeyInfo->incrKey ){
      rc = -1;

    }else if( d1<nKey1 ){
      rc = 1;
    }else if( d2<nKey2 ){
      rc = -1;

    }
  }else if( pKeyInfo->aSortOrder && i<pKeyInfo->nField
               && pKeyInfo->aSortOrder[i] ){
    rc = -rc;
  }

  return rc;

  /* One of the keys ran out of fields, but all the fields up to that point
  ** were equal. If the incrKey flag is true, then the second key is
  ** treated as larger.
  */
  if( rc==0 ){
    if( pKeyInfo->incrKey ){
      rc = -1;
    }else if( !pKeyInfo->prefixIsEqual ){
      if( d1<nKey1 ){
        rc = 1;
      }else if( d2<nKey2 ){
        rc = -1;
      }
    }
  }else if( pKeyInfo->aSortOrder && i<pKeyInfo->nField
               && pKeyInfo->aSortOrder[i] ){
    rc = -rc;
  }

  return rc;

** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.  This module is reponsible for
** generating the code that loops through a table looking for applicable
** rows.  Indices are selected and used to speed the search when doing
** so is applicable.  Because this module is responsible for selecting
** indices, you might also think of this module as the "query optimizer".
**
** $Id: where.c,v 1.263 2007/11/26 13:36:00 drh Exp $
*/
#include "sqliteInt.h"

/*
** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
*/
#define BMS  (sizeof(Bitmask)*8)
................................................................................
  Vdbe *v = pParse->pVdbe;
  if( pX->op==TK_EQ ){
    sqlite3ExprCode(pParse, pX->pRight);
  }else if( pX->op==TK_ISNULL ){
    sqlite3VdbeAddOp(v, OP_Null, 0, 0);
#ifndef SQLITE_OMIT_SUBQUERY
  }else{

    int iTab;
    struct InLoop *pIn;

    assert( pX->op==TK_IN );
    sqlite3CodeSubselect(pParse, pX);
    iTab = pX->iTable;
    sqlite3VdbeAddOp(v, OP_Rewind, iTab, 0);
    VdbeComment((v, "# %.*s", pX->span.n, pX->span.z));
    if( pLevel->nIn==0 ){
      pLevel->nxt = sqlite3VdbeMakeLabel(v);
    }
    pLevel->nIn++;
    pLevel->aInLoop = sqlite3DbReallocOrFree(pParse->db, pLevel->aInLoop,
                                    sizeof(pLevel->aInLoop[0])*pLevel->nIn);
    pIn = pLevel->aInLoop;
    if( pIn ){

      pIn += pLevel->nIn - 1;
      pIn->iCur = iTab;
      pIn->topAddr = sqlite3VdbeAddOp(v, OP_Column, iTab, 0);
      sqlite3VdbeAddOp(v, OP_IsNull, -1, 0);
    }else{
      pLevel->nIn = 0;
    }
#endif
  }
  disableTerm(pLevel, pTerm);

** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.  This module is reponsible for
** generating the code that loops through a table looking for applicable
** rows.  Indices are selected and used to speed the search when doing
** so is applicable.  Because this module is responsible for selecting
** indices, you might also think of this module as the "query optimizer".
**
** $Id: where.c,v 1.264 2007/11/29 17:05:18 danielk1977 Exp $
*/
#include "sqliteInt.h"

/*
** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
*/
#define BMS  (sizeof(Bitmask)*8)
................................................................................
  Vdbe *v = pParse->pVdbe;
  if( pX->op==TK_EQ ){
    sqlite3ExprCode(pParse, pX->pRight);
  }else if( pX->op==TK_ISNULL ){
    sqlite3VdbeAddOp(v, OP_Null, 0, 0);
#ifndef SQLITE_OMIT_SUBQUERY
  }else{
    int eType;
    int iTab;
    struct InLoop *pIn;

    assert( pX->op==TK_IN );
    eType = sqlite3FindInIndex(pParse, pX, 1);
    iTab = pX->iTable;
    sqlite3VdbeAddOp(v, OP_Rewind, iTab, 0);
    VdbeComment((v, "# %.*s", pX->span.n, pX->span.z));
    if( pLevel->nIn==0 ){
      pLevel->nxt = sqlite3VdbeMakeLabel(v);
    }
    pLevel->nIn++;
    pLevel->aInLoop = sqlite3DbReallocOrFree(pParse->db, pLevel->aInLoop,
                                    sizeof(pLevel->aInLoop[0])*pLevel->nIn);
    pIn = pLevel->aInLoop;
    if( pIn ){
      int op = ((eType==IN_INDEX_ROWID)?OP_Rowid:OP_Column);
      pIn += pLevel->nIn - 1;
      pIn->iCur = iTab;
      pIn->topAddr = sqlite3VdbeAddOp(v, op, iTab, 0);
      sqlite3VdbeAddOp(v, OP_IsNull, -1, 0);
    }else{
      pLevel->nIn = 0;
    }
#endif
  }
  disableTerm(pLevel, pTerm);

# 2007 November 29
#
# 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.
#
#***********************************************************************
# This file tests the optimisations made in November 2007 of expressions 
# of the following form:
#
#     <value> IN (SELECT <column> FROM <table>)
#
# $Id: in3.test,v 1.1 2007/11/29 17:05:18 danielk1977 Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

# Return the number of OpenEphemeral instructions used in the
# implementation of the sql statement passed as a an argument.
#
proc nEphemeral {sql} {
  set nEph 0
  foreach op [execsql "EXPLAIN $sql"] {
    if {$op eq "OpenEphemeral"} {incr nEph}
  }
  set nEph
}

# This proc works the same way as execsql, except that the number
# of OpenEphemeral instructions used in the implementation of the
# statement is inserted into the start of the returned list.
#
proc exec_neph {sql} {
  return [concat [nEphemeral $sql] [execsql $sql]]
}

do_test in3-1.1 {
  execsql {
    CREATE TABLE t1(a PRIMARY KEY, b);
    INSERT INTO t1 VALUES(1, 2);
    INSERT INTO t1 VALUES(3, 4);
    INSERT INTO t1 VALUES(5, 6);
  }
} {}

# All of these queries should avoid using a temp-table:
#
do_test in3-1.2 {
  exec_neph { SELECT rowid FROM t1 WHERE rowid IN (SELECT rowid FROM t1); }
} {0 1 2 3}
do_test in3-1.3 {
  exec_neph { SELECT a FROM t1 WHERE a IN (SELECT a FROM t1); }
} {0 1 3 5}
do_test in3-1.4 {
  exec_neph { SELECT rowid FROM t1 WHERE rowid+0 IN (SELECT rowid FROM t1); }
} {0 1 2 3}
do_test in3-1.5 {
  exec_neph { SELECT a FROM t1 WHERE a+0 IN (SELECT a FROM t1); }
} {0 1 3 5}

# Because none of the sub-select queries in the following statements
# match the pattern ("SELECT <column> FROM <table>"), the following do 
# require a temp table.
#
do_test in3-1.6 {
  exec_neph { SELECT rowid FROM t1 WHERE rowid IN (SELECT rowid+0 FROM t1); }
} {1 1 2 3}
do_test in3-1.7 {
  exec_neph { SELECT a FROM t1 WHERE a IN (SELECT a+0 FROM t1); }
} {1 1 3 5}
do_test in3-1.8 {
  exec_neph { SELECT a FROM t1 WHERE a IN (SELECT a FROM t1 WHERE 1); }
} {1 1 3 5}
do_test in3-1.9 {
  exec_neph { SELECT a FROM t1 WHERE a IN (SELECT a FROM t1 GROUP BY a); }
} {1 1 3 5}

# This should not use a temp-table. Even though the sub-select does
# not exactly match the pattern "SELECT <column> FROM <table>", in
# this case the ORDER BY is a no-op and can be ignored.
do_test in3-1.10 {
  exec_neph { SELECT a FROM t1 WHERE a IN (SELECT a FROM t1 ORDER BY a); }
} {0 1 3 5}

# These do use the temp-table. Adding the LIMIT clause means the 
# ORDER BY cannot be ignored.
do_test in3-1.11 {
  exec_neph {SELECT a FROM t1 WHERE a IN (SELECT a FROM t1 ORDER BY a LIMIT 1)}
} {1 1}
do_test in3-1.12 {
  exec_neph {
    SELECT a FROM t1 WHERE a IN (SELECT a FROM t1 ORDER BY a LIMIT 1 OFFSET 1)
  }
} {1 3}

# Has to use a temp-table because of the compound sub-select.
#
do_test in3-1.13 {
  exec_neph {
    SELECT a FROM t1 WHERE a IN (
      SELECT a FROM t1 UNION ALL SELECT a FROM t1
    )
  }
} {1 1 3 5}

# The first of these queries has to use the temp-table, because the 
# collation sequence used for the index on "t1.a" does not match the
# collation sequence used by the "IN" comparison. The second does not
# require a temp-table, because the collation sequences match.
#
do_test in3-1.14 {
  exec_neph { SELECT a FROM t1 WHERE a COLLATE nocase IN (SELECT a FROM t1) }
} {1 1 3 5}
do_test in3-1.15 {
  exec_neph { SELECT a FROM t1 WHERE a COLLATE binary IN (SELECT a FROM t1) }
} {0 1 3 5}

# Neither of these queries require a temp-table. The collation sequence
# makes no difference when using a rowid.
#
do_test in3-1.16 {
  exec_neph {SELECT a FROM t1 WHERE a COLLATE nocase IN (SELECT rowid FROM t1)}
} {0 1 3}
do_test in3-1.17 {
  exec_neph {SELECT a FROM t1 WHERE a COLLATE binary IN (SELECT rowid FROM t1)}
} {0 1 3}

# The following tests - in3.2.* - test a bug that was difficult to track
# down during development. They are not particularly well focused.
#
do_test in3-2.1 {
  execsql {
    DROP TABLE IF EXISTS t1;
    CREATE TABLE t1(w int, x int, y int);
    CREATE TABLE t2(p int, q int, r int, s int);
  }
  for {set i 1} {$i<=100} {incr i} {
    set w $i
    set x [expr {int(log($i)/log(2))}]
    set y [expr {$i*$i + 2*$i + 1}]
    execsql "INSERT INTO t1 VALUES($w,$x,$y)"
  }
  set maxy [execsql {select max(y) from t1}]
  db eval { INSERT INTO t2 SELECT 101-w, x, $maxy+1-y, y FROM t1 }
} {}
do_test in3-2.2 {
  execsql {
    SELECT rowid 
    FROM t1 
    WHERE rowid IN (SELECT rowid FROM t1 WHERE rowid IN (1, 2));
  }
} {1 2}
do_test in3-2.3 {
  execsql {
    select rowid from t1 where rowid IN (-1,2,4)
  }
} {2 4}
do_test in3-2.4 {
  execsql {
    SELECT rowid FROM t1 WHERE rowid IN 
       (select rowid from t1 where rowid IN (-1,2,4))
  }
} {2 4}

#-------------------------------------------------------------------------
# This next block of tests - in3-3.* - verify that column affinity is
# correctly handled in cases where an index might be used to optimise
# an IN (SELECT) expression.
#
do_test in3-3.1 {
  catch {execsql {
    DROP TABLE t1;
    DROP TABLE t2;
  }}

  execsql {

    CREATE TABLE t1(a BLOB, b NUMBER ,c TEXT);
    CREATE UNIQUE INDEX t1_i1 ON t1(a);        /* no affinity */
    CREATE UNIQUE INDEX t1_i2 ON t1(b);        /* numeric affinity */
    CREATE UNIQUE INDEX t1_i3 ON t1(c);        /* text affinity */

    CREATE TABLE t2(x BLOB, y NUMBER, z TEXT);
    CREATE UNIQUE INDEX t2_i1 ON t2(x);        /* no affinity */
    CREATE UNIQUE INDEX t2_i2 ON t2(y);        /* numeric affinity */
    CREATE UNIQUE INDEX t2_i3 ON t2(z);        /* text affinity */

    INSERT INTO t1 VALUES(1, 1, 1);
    INSERT INTO t2 VALUES('1', '1', '1');
  }
} {}

do_test in3-3.2 {
  # No affinity is applied before comparing "x" and "a". Therefore
  # the index can be used (the comparison is false, text!=number).
  exec_neph { SELECT x IN (SELECT a FROM t1) FROM t2 }
} {0 0}
do_test in3-3.3 {
  # Logically, numeric affinity is applied to both sides before 
  # the comparison.  Therefore it is possible to use index t1_i2.
  exec_neph { SELECT x IN (SELECT b FROM t1) FROM t2 }
} {0 1}
do_test in3-3.4 {
  # No affinity is applied before the comparison takes place. Making
  # it possible to use index t1_i3.
  exec_neph { SELECT x IN (SELECT c FROM t1) FROM t2 }
} {0 1}

do_test in3-3.5 {
  # Numeric affinity should be applied to each side before the comparison
  # takes place. Therefore we cannot use index t1_i1, which has no affinity.
  exec_neph { SELECT y IN (SELECT a FROM t1) FROM t2 }
} {1 1}
do_test in3-3.6 {
  # Numeric affinity is applied to both sides before 
  # the comparison.  Therefore it is possible to use index t1_i2.
  exec_neph { SELECT y IN (SELECT b FROM t1) FROM t2 }
} {0 1}
do_test in3-3.7 {
  # Numeric affinity is applied before the comparison takes place. 
  # Making it impossible to use index t1_i3.
  exec_neph { SELECT y IN (SELECT c FROM t1) FROM t2 }
} {1 1}

#---------------------------------------------------------------------
#
# Test using a multi-column index.
#
do_test in3-4.1 {
  execsql {
    CREATE TABLE t3(a, b, c);
    CREATE UNIQUE INDEX t3_i ON t3(b, a);
  }

  execsql {
    INSERT INTO t3 VALUES(1, 'numeric', 2);
    INSERT INTO t3 VALUES(2, 'text', 2);
    INSERT INTO t3 VALUES(3, 'real', 2);
    INSERT INTO t3 VALUES(4, 'none', 2);
  }
} {}
do_test in3-4.2 {
  exec_neph { SELECT 'text' IN (SELECT b FROM t3) }
} {0 1}
do_test in3-4.3 {
  exec_neph { SELECT 'TEXT' COLLATE nocase IN (SELECT b FROM t3) }
} {1 1}
do_test in3-4.4 {
  # A temp table must be used because t3_i.b is not guaranteed to be unique.
  exec_neph { SELECT b FROM t3 WHERE b IN (SELECT b FROM t3) }
} {1 none numeric real text}
do_test in3-4.5 {
  execsql { CREATE UNIQUE INDEX t3_i2 ON t3(b) }
  exec_neph { SELECT b FROM t3 WHERE b IN (SELECT b FROM t3) }
} {0 none numeric real text}
do_test in3-4.6 {
  execsql { DROP INDEX t3_i2 }
} {}

finish_test