SQLite

  $(TOP)\src\test_autoext.c \
  $(TOP)\src\test_async.c \
  $(TOP)\src\test_backup.c \
  $(TOP)\src\test_btree.c \
  $(TOP)\src\test_config.c \
  $(TOP)\src\test_demovfs.c \
  $(TOP)\src\test_devsym.c \
  $(TOP)\src\test_fs.c \
  $(TOP)\src\test_func.c \
  $(TOP)\src\test_fuzzer.c \
  $(TOP)\src\test_hexio.c \
  $(TOP)\src\test_init.c \
  $(TOP)\src\test_intarray.c \
  $(TOP)\src\test_journal.c \
  $(TOP)\src\test_malloc.c \

** This ensures that each node is stored on a single database page. If the 
** database page-size is so large that more than RTREE_MAXCELLS entries 
** would fit in a single node, use a smaller node-size.
*/
static int getNodeSize(
  sqlite3 *db,                    /* Database handle */
  Rtree *pRtree,                  /* Rtree handle */
  int isCreate,                   /* True for xCreate, false for xConnect */
  char **pzErr                    /* OUT: Error message, if any */
){
  int rc;
  char *zSql;
  if( isCreate ){
    int iPageSize = 0;
    zSql = sqlite3_mprintf("PRAGMA %Q.page_size", pRtree->zDb);
    rc = getIntFromStmt(db, zSql, &iPageSize);
    if( rc==SQLITE_OK ){
      pRtree->iNodeSize = iPageSize-64;
      if( (4+pRtree->nBytesPerCell*RTREE_MAXCELLS)<pRtree->iNodeSize ){
        pRtree->iNodeSize = 4+pRtree->nBytesPerCell*RTREE_MAXCELLS;
      }
    }else{
      *pzErr = sqlite3_mprintf("%s", sqlite3_errmsg(db));
    }
  }else{
    zSql = sqlite3_mprintf(
        "SELECT length(data) FROM '%q'.'%q_node' WHERE nodeno = 1",
        pRtree->zDb, pRtree->zName
    );
    rc = getIntFromStmt(db, zSql, &pRtree->iNodeSize);
    if( rc!=SQLITE_OK ){
      *pzErr = sqlite3_mprintf("%s", sqlite3_errmsg(db));
    }
  }

  sqlite3_free(zSql);
  return rc;
}

/* 

  pRtree->nDim = (argc-4)/2;
  pRtree->nBytesPerCell = 8 + pRtree->nDim*4*2;
  pRtree->eCoordType = eCoordType;
  memcpy(pRtree->zDb, argv[1], nDb);
  memcpy(pRtree->zName, argv[2], nName);

  /* Figure out the node size to use. */
  rc = getNodeSize(db, pRtree, isCreate, pzErr);

  /* Create/Connect to the underlying relational database schema. If
  ** that is successful, call sqlite3_declare_vtab() to configure
  ** the r-tree table schema.
  */
  if( rc==SQLITE_OK ){
    if( (rc = rtreeSqlInit(pRtree, db, argv[1], argv[2], isCreate)) ){

  $(TOP)/src/test_autoext.c \
  $(TOP)/src/test_async.c \
  $(TOP)/src/test_backup.c \
  $(TOP)/src/test_btree.c \
  $(TOP)/src/test_config.c \
  $(TOP)/src/test_demovfs.c \
  $(TOP)/src/test_devsym.c \
  $(TOP)/src/test_fs.c \
  $(TOP)/src/test_func.c \
  $(TOP)/src/test_fuzzer.c \
  $(TOP)/src/test_hexio.c \
  $(TOP)/src/test_init.c \
  $(TOP)/src/test_intarray.c \
  $(TOP)/src/test_journal.c \
  $(TOP)/src/test_malloc.c \

      sqlite3_key(db, zKey, i/2);
    }else{
      sqlite3_rekey(db, zKey, i/2);
    }
  }else
#endif
#if defined(SQLITE_HAS_CODEC) || defined(SQLITE_ENABLE_CEROD)
  if( sqlite3StrICmp(zLeft, "activate_extensions")==0 && zRight ){
#ifdef SQLITE_HAS_CODEC
    if( sqlite3StrNICmp(zRight, "see-", 4)==0 ){
      sqlite3_activate_see(&zRight[4]);
    }
#endif
#ifdef SQLITE_ENABLE_CEROD
    if( sqlite3StrNICmp(zRight, "cerod-", 6)==0 ){

  }

  /* Process the input line.
  */
  if( nArg==0 ) return 0; /* no tokens, no error */
  n = strlen30(azArg[0]);
  c = azArg[0][0];
  if( c=='b' && n>=3 && strncmp(azArg[0], "backup", n)==0 ){
    const char *zDestFile = 0;
    const char *zDb = 0;
    const char *zKey = 0;
    sqlite3 *pDest;
    sqlite3_backup *pBackup;
    int j;
    for(j=1; j<nArg; j++){
      const char *z = azArg[j];
      if( z[0]=='-' ){
        while( z[0]=='-' ) z++;
        if( strcmp(z,"key")==0 && j<nArg-1 ){
          zKey = azArg[++j];
        }else
        {
          fprintf(stderr, "unknown option: %s\n", azArg[j]);
          return 1;
        }
      }else if( zDestFile==0 ){
        zDestFile = azArg[j];
      }else if( zDb==0 ){
        zDb = zDestFile;
        zDestFile = azArg[j];
      }else{
        fprintf(stderr, "too many arguments to .backup\n");
        return 1;
      }
    }
    if( zDestFile==0 ){
      fprintf(stderr, "missing FILENAME argument on .backup\n");
      return 1;
    }
    if( zDb==0 ) zDb = "main";
    rc = sqlite3_open(zDestFile, &pDest);
    if( rc!=SQLITE_OK ){
      fprintf(stderr, "Error: cannot open \"%s\"\n", zDestFile);
      sqlite3_close(pDest);
      return 1;
    }
#ifdef SQLITE_HAS_CODEC
    sqlite3_key(pDest, zKey, (int)strlen(zKey));
#else
    (void)zKey;
#endif
    open_db(p);
    pBackup = sqlite3_backup_init(pDest, "main", p->db, zDb);
    if( pBackup==0 ){
      fprintf(stderr, "Error: %s\n", sqlite3_errmsg(pDest));
      sqlite3_close(pDest);
      return 1;
    }

/*
** A convenience macro that returns the number of elements in
** an array.
*/
#define ArraySize(X)    ((int)(sizeof(X)/sizeof(X[0])))

/*
** Determine if the argument is a power of two
*/
#define IsPowerOfTwo(X) (((X)&((X)-1))==0)

/*
** The following value as a destructor means to use sqlite3DbFree().
** The sqlite3DbFree() routine requires two parameters instead of the 
** one parameter that destructors normally want.  So we have to introduce 
** this magic value that the code knows to handle differently.  Any 
** pointer will work here as long as it is distinct from SQLITE_STATIC
** and SQLITE_TRANSIENT.

#define SQLITE_GroupByOrder   0x0004   /* GROUPBY cover of ORDERBY */
#define SQLITE_FactorOutConst 0x0008   /* Constant factoring */
#define SQLITE_IdxRealAsInt   0x0010   /* Store REAL as INT in indices */
#define SQLITE_DistinctOpt    0x0020   /* DISTINCT using indexes */
#define SQLITE_CoverIdxScan   0x0040   /* Covering index scans */
#define SQLITE_OrderByIdxJoin 0x0080   /* ORDER BY of joins via index */
#define SQLITE_SubqCoroutine  0x0100   /* Evaluate subqueries as coroutines */
#define SQLITE_Transitive     0x0200   /* Transitive constraints */
#define SQLITE_AllOpts        0xffff   /* All optimizations */

/*
** Macros for testing whether or not optimizations are enabled or disabled.
*/
#ifndef SQLITE_OMIT_BUILTIN_TEST
#define OptimizationDisabled(db, mask)  (((db)->dbOptFlags&(mask))!=0)

    extern int Sqlitetest_hexio_Init(Tcl_Interp*);
    extern int Sqlitetest_init_Init(Tcl_Interp*);
    extern int Sqlitetest_malloc_Init(Tcl_Interp*);
    extern int Sqlitetest_mutex_Init(Tcl_Interp*);
    extern int Sqlitetestschema_Init(Tcl_Interp*);
    extern int Sqlitetestsse_Init(Tcl_Interp*);
    extern int Sqlitetesttclvar_Init(Tcl_Interp*);
    extern int Sqlitetestfs_Init(Tcl_Interp*);
    extern int SqlitetestThread_Init(Tcl_Interp*);
    extern int SqlitetestOnefile_Init();
    extern int SqlitetestOsinst_Init(Tcl_Interp*);
    extern int Sqlitetestbackup_Init(Tcl_Interp*);
    extern int Sqlitetestintarray_Init(Tcl_Interp*);
    extern int Sqlitetestvfs_Init(Tcl_Interp *);
    extern int Sqlitetestrtree_Init(Tcl_Interp*);

    Sqlitetest_func_Init(interp);
    Sqlitetest_hexio_Init(interp);
    Sqlitetest_init_Init(interp);
    Sqlitetest_malloc_Init(interp);
    Sqlitetest_mutex_Init(interp);
    Sqlitetestschema_Init(interp);
    Sqlitetesttclvar_Init(interp);
    Sqlitetestfs_Init(interp);
    SqlitetestThread_Init(interp);
    SqlitetestOnefile_Init(interp);
    SqlitetestOsinst_Init(interp);
    Sqlitetestbackup_Init(interp);
    Sqlitetestintarray_Init(interp);
    Sqlitetestvfs_Init(interp);
    Sqlitetestrtree_Init(interp);

/*
** 2013 Jan 11
**
** 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.
**
*************************************************************************
** Code for testing the virtual table interfaces.  This code
** is not included in the SQLite library.  It is used for automated
** testing of the SQLite library.
**
** The FS virtual table is created as follows:
**
**   CREATE VIRTUAL TABLE tbl USING fs(idx);
**
** where idx is the name of a table in the db with 2 columns.  The virtual
** table also has two columns - file path and file contents.
**
** The first column of table idx must be an IPK, and the second contains file
** paths. For example:
**
**   CREATE TABLE idx(id INTEGER PRIMARY KEY, path TEXT);
**   INSERT INTO idx VALUES(4, '/etc/passwd');
**
** Adding the row to the idx table automatically creates a row in the 
** virtual table with rowid=4, path=/etc/passwd and a text field that 
** contains data read from file /etc/passwd on disk.
*/
#include "sqliteInt.h"
#include "tcl.h"

#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>

#if SQLITE_OS_UNIX
# include <unistd.h>
#endif
#if SQLITE_OS_WIN
# include <io.h>
#endif

#ifndef SQLITE_OMIT_VIRTUALTABLE

typedef struct fs_vtab fs_vtab;
typedef struct fs_cursor fs_cursor;

/* 
** A fs virtual-table object 
*/
struct fs_vtab {
  sqlite3_vtab base;
  sqlite3 *db;
  char *zDb;                      /* Name of db containing zTbl */
  char *zTbl;                     /* Name of docid->file map table */
};

/* A fs cursor object */
struct fs_cursor {
  sqlite3_vtab_cursor base;
  sqlite3_stmt *pStmt;
  char *zBuf;
  int nBuf;
  int nAlloc;
};

/*
** This function is the implementation of both the xConnect and xCreate
** methods of the fs virtual table.
**
** The argv[] array contains the following:
**
**   argv[0]   -> module name  ("fs")
**   argv[1]   -> database name
**   argv[2]   -> table name
**   argv[...] -> other module argument fields.
*/
static int fsConnect(
  sqlite3 *db,
  void *pAux,
  int argc, const char *const*argv,
  sqlite3_vtab **ppVtab,
  char **pzErr
){
  fs_vtab *pVtab;
  int nByte;
  const char *zTbl;
  const char *zDb = argv[1];

  if( argc!=4 ){
    *pzErr = sqlite3_mprintf("wrong number of arguments");
    return SQLITE_ERROR;
  }
  zTbl = argv[3];

  nByte = sizeof(fs_vtab) + strlen(zTbl) + 1 + strlen(zDb) + 1;
  pVtab = (fs_vtab *)sqlite3MallocZero( nByte );
  if( !pVtab ) return SQLITE_NOMEM;

  pVtab->zTbl = (char *)&pVtab[1];
  pVtab->zDb = &pVtab->zTbl[strlen(zTbl)+1];
  pVtab->db = db;
  memcpy(pVtab->zTbl, zTbl, strlen(zTbl));
  memcpy(pVtab->zDb, zDb, strlen(zDb));
  *ppVtab = &pVtab->base;
  sqlite3_declare_vtab(db, "CREATE TABLE xyz(path TEXT, data TEXT)");

  return SQLITE_OK;
}
/* Note that for this virtual table, the xCreate and xConnect
** methods are identical. */

static int fsDisconnect(sqlite3_vtab *pVtab){
  sqlite3_free(pVtab);
  return SQLITE_OK;
}
/* The xDisconnect and xDestroy methods are also the same */

/*
** Open a new fs cursor.
*/
static int fsOpen(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCursor){
  fs_cursor *pCur;
  pCur = sqlite3MallocZero(sizeof(fs_cursor));
  *ppCursor = &pCur->base;
  return SQLITE_OK;
}

/*
** Close a fs cursor.
*/
static int fsClose(sqlite3_vtab_cursor *cur){
  fs_cursor *pCur = (fs_cursor *)cur;
  sqlite3_finalize(pCur->pStmt);
  sqlite3_free(pCur->zBuf);
  sqlite3_free(pCur);
  return SQLITE_OK;
}

static int fsNext(sqlite3_vtab_cursor *cur){
  fs_cursor *pCur = (fs_cursor *)cur;
  int rc;

  rc = sqlite3_step(pCur->pStmt);
  if( rc==SQLITE_ROW || rc==SQLITE_DONE ) rc = SQLITE_OK;

  return rc;
}

static int fsFilter(
  sqlite3_vtab_cursor *pVtabCursor, 
  int idxNum, const char *idxStr,
  int argc, sqlite3_value **argv
){
  int rc;
  fs_cursor *pCur = (fs_cursor *)pVtabCursor;
  fs_vtab *p = (fs_vtab *)(pVtabCursor->pVtab);

  assert( (idxNum==0 && argc==0) || (idxNum==1 && argc==1) );
  if( idxNum==1 ){
    char *zStmt = sqlite3_mprintf(
        "SELECT * FROM %Q.%Q WHERE rowid=?", p->zDb, p->zTbl);
    if( !zStmt ) return SQLITE_NOMEM;
    rc = sqlite3_prepare_v2(p->db, zStmt, -1, &pCur->pStmt, 0);
    sqlite3_free(zStmt);
    if( rc==SQLITE_OK ){
      sqlite3_bind_value(pCur->pStmt, 1, argv[0]);
    }
  }else{
    char *zStmt = sqlite3_mprintf("SELECT * FROM %Q.%Q", p->zDb, p->zTbl);
    if( !zStmt ) return SQLITE_NOMEM;
    rc = sqlite3_prepare_v2(p->db, zStmt, -1, &pCur->pStmt, 0);
    sqlite3_free(zStmt);
  }

  if( rc==SQLITE_OK ){
    rc = fsNext(pVtabCursor); 
  }
  return rc;
}

static int fsColumn(sqlite3_vtab_cursor *cur, sqlite3_context *ctx, int i){
  fs_cursor *pCur = (fs_cursor*)cur;

  assert( i==0 || i==1 );
  if( i==0 ){
    sqlite3_result_value(ctx, sqlite3_column_value(pCur->pStmt, 0));
  }else{
    const char *zFile = (const char *)sqlite3_column_text(pCur->pStmt, 1);
    struct stat sbuf;
    int fd;

    fd = open(zFile, O_RDONLY);
    if( fd<0 ) return SQLITE_IOERR;
    fstat(fd, &sbuf);

    if( sbuf.st_size>=pCur->nAlloc ){
      int nNew = sbuf.st_size*2;
      char *zNew;
      if( nNew<1024 ) nNew = 1024;

      zNew = sqlite3Realloc(pCur->zBuf, nNew);
      if( zNew==0 ){
        close(fd);
        return SQLITE_NOMEM;
      }
      pCur->zBuf = zNew;
      pCur->nAlloc = nNew;
    }

    read(fd, pCur->zBuf, sbuf.st_size);
    close(fd);
    pCur->nBuf = sbuf.st_size;
    pCur->zBuf[pCur->nBuf] = '\0';

    sqlite3_result_text(ctx, pCur->zBuf, -1, SQLITE_TRANSIENT);
  }
  return SQLITE_OK;
}

static int fsRowid(sqlite3_vtab_cursor *cur, sqlite_int64 *pRowid){
  fs_cursor *pCur = (fs_cursor*)cur;
  *pRowid = sqlite3_column_int64(pCur->pStmt, 0);
  return SQLITE_OK;
}

static int fsEof(sqlite3_vtab_cursor *cur){
  fs_cursor *pCur = (fs_cursor*)cur;
  return (sqlite3_data_count(pCur->pStmt)==0);
}

static int fsBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){
  int ii;

  for(ii=0; ii<pIdxInfo->nConstraint; ii++){
    struct sqlite3_index_constraint const *pCons = &pIdxInfo->aConstraint[ii];
    if( pCons->iColumn<0 && pCons->usable
           && pCons->op==SQLITE_INDEX_CONSTRAINT_EQ ){
      struct sqlite3_index_constraint_usage *pUsage;
      pUsage = &pIdxInfo->aConstraintUsage[ii];
      pUsage->omit = 0;
      pUsage->argvIndex = 1;
      pIdxInfo->idxNum = 1;
      pIdxInfo->estimatedCost = 1.0;
      break;
    }
  }

  return SQLITE_OK;
}

/*
** A virtual table module that provides read-only access to a
** Tcl global variable namespace.
*/
static sqlite3_module fsModule = {
  0,                         /* iVersion */
  fsConnect,
  fsConnect,
  fsBestIndex,
  fsDisconnect, 
  fsDisconnect,
  fsOpen,                      /* xOpen - open a cursor */
  fsClose,                     /* xClose - close a cursor */
  fsFilter,                    /* xFilter - configure scan constraints */
  fsNext,                      /* xNext - advance a cursor */
  fsEof,                       /* xEof - check for end of scan */
  fsColumn,                    /* xColumn - read data */
  fsRowid,                     /* xRowid - read data */
  0,                           /* xUpdate */
  0,                           /* xBegin */
  0,                           /* xSync */
  0,                           /* xCommit */
  0,                           /* xRollback */
  0,                           /* xFindMethod */
  0,                           /* xRename */
};

/*
** Decode a pointer to an sqlite3 object.
*/
extern int getDbPointer(Tcl_Interp *interp, const char *zA, sqlite3 **ppDb);

/*
** Register the echo virtual table module.
*/
static int register_fs_module(
  ClientData clientData, /* Pointer to sqlite3_enable_XXX function */
  Tcl_Interp *interp,    /* The TCL interpreter that invoked this command */
  int objc,              /* Number of arguments */
  Tcl_Obj *CONST objv[]  /* Command arguments */
){
  sqlite3 *db;
  if( objc!=2 ){
    Tcl_WrongNumArgs(interp, 1, objv, "DB");
    return TCL_ERROR;
  }
  if( getDbPointer(interp, Tcl_GetString(objv[1]), &db) ) return TCL_ERROR;
#ifndef SQLITE_OMIT_VIRTUALTABLE
  sqlite3_create_module(db, "fs", &fsModule, (void *)interp);
#endif
  return TCL_OK;
}

#endif


/*
** Register commands with the TCL interpreter.
*/
int Sqlitetestfs_Init(Tcl_Interp *interp){
#ifndef SQLITE_OMIT_VIRTUALTABLE
  static struct {
     char *zName;
     Tcl_ObjCmdProc *xProc;
     void *clientData;
  } aObjCmd[] = {
     { "register_fs_module",   register_fs_module, 0 },
  };
  int i;
  for(i=0; i<sizeof(aObjCmd)/sizeof(aObjCmd[0]); i++){
    Tcl_CreateObjCommand(interp, aObjCmd[i].zName, 
        aObjCmd[i].xProc, aObjCmd[i].clientData, 0);
  }
#endif
  return TCL_OK;
}

**     X|Y     X or Y
**     ^X      X occurring at the beginning of the string
**     X$      X occurring at the end of the string
**     .       Match any single character
**     \c      Character c where c is one of \{}()[]|*+?.
**     \c      C-language escapes for c in afnrtv.  ex: \t or \n
**     \uXXXX  Where XXXX is exactly 4 hex digits, unicode value XXXX
**     \xXX    Where XX is exactly 2 hex digits, unicode value XX
**     [abc]   Any single character from the set abc
**     [^abc]  Any single character not in the set abc
**     [a-z]   Any single character in the range a-z
**     [^a-z]  Any single character not in the range a-z
**     \b      Word boundary
**     \w      Word character.  [A-Za-z0-9_]
**     \W      Non-word character

    return 0;
  }
  *pV = (*pV)*16 + (c & 0xff);
  return 1;
}

/* A backslash character has been seen, read the next character and
** return its interpretation.
*/
static unsigned re_esc_char(ReCompiled *p){
  static const char zEsc[] = "afnrtv\\()*.+?[$^{|}]";
  static const char zTrans[] = "\a\f\n\r\t\v";
  int i, v = 0;
  char c;
  if( p->sIn.i>=p->sIn.mx ) return 0;
  c = p->sIn.z[p->sIn.i];
  if( c=='u' && p->sIn.i+4<p->sIn.mx ){
    const unsigned char *zIn = p->sIn.z + p->sIn.i;

    if( re_hex(zIn[1],&v)
     && re_hex(zIn[2],&v)
     && re_hex(zIn[3],&v)
     && re_hex(zIn[4],&v)
    ){
      p->sIn.i += 5;
      return v;
    }
  }
  if( c=='x' && p->sIn.i+2<p->sIn.mx ){
    const unsigned char *zIn = p->sIn.z + p->sIn.i;
    if( re_hex(zIn[1],&v)
     && re_hex(zIn[2],&v)
    ){
      p->sIn.i += 3;
      return v;
    }
  }
  for(i=0; zEsc[i] && zEsc[i]!=c; i++){}
  if( zEsc[i] ){
    if( i<6 ) c = zTrans[i];
    p->sIn.i++;

  for(i=p->nzVar-1; i>=0; i--) sqlite3DbFree(db, p->azVar[i]);
  vdbeFreeOpArray(db, p->aOp, p->nOp);
  sqlite3DbFree(db, p->aLabel);
  sqlite3DbFree(db, p->aColName);
  sqlite3DbFree(db, p->zSql);
  sqlite3DbFree(db, p->pFree);
#if defined(SQLITE_ENABLE_TREE_EXPLAIN)
  sqlite3DbFree(db, p->zExplain);
  sqlite3DbFree(db, p->pExplain);
#endif
}

/*
** Delete an entire VDBE.
*/

typedef struct WhereTerm WhereTerm;
struct WhereTerm {
  Expr *pExpr;            /* Pointer to the subexpression that is this term */
  int iParent;            /* Disable pWC->a[iParent] when this term disabled */
  int leftCursor;         /* Cursor number of X in "X <op> <expr>" */
  union {
    int leftColumn;         /* Column number of X in "X <op> <expr>" */
    WhereOrInfo *pOrInfo;   /* Extra information if (eOperator & WO_OR)!=0 */
    WhereAndInfo *pAndInfo; /* Extra information if (eOperator& WO_AND)!=0 */
  } u;
  u16 eOperator;          /* A WO_xx value describing <op> */
  u8 wtFlags;             /* TERM_xxx bit flags.  See below */
  u8 nChild;              /* Number of children that must disable us */
  WhereClause *pWC;       /* The clause this term is part of */
  Bitmask prereqRight;    /* Bitmask of tables used by pExpr->pRight */
  Bitmask prereqAll;      /* Bitmask of tables referenced by pExpr */

#define WO_LE     (WO_EQ<<(TK_LE-TK_EQ))
#define WO_GT     (WO_EQ<<(TK_GT-TK_EQ))
#define WO_GE     (WO_EQ<<(TK_GE-TK_EQ))
#define WO_MATCH  0x040
#define WO_ISNULL 0x080
#define WO_OR     0x100       /* Two or more OR-connected terms */
#define WO_AND    0x200       /* Two or more AND-connected terms */
#define WO_EQUIV  0x400       /* Of the form A==B, both columns */
#define WO_NOOP   0x800       /* This term does not restrict search space */

#define WO_ALL    0xfff       /* Mask of all possible WO_* values */
#define WO_SINGLE 0x0ff       /* Mask of all non-compound WO_* values */

/*
** Value for wsFlags returned by bestIndex() and stored in

}

/*
** Search for a term in the WHERE clause that is of the form "X <op> <expr>"
** where X is a reference to the iColumn of table iCur and <op> is one of
** the WO_xx operator codes specified by the op parameter.
** Return a pointer to the term.  Return 0 if not found.
**
** The term returned might by Y=<expr> if there is another constraint in
** the WHERE clause that specifies that X=Y.  Any such constraints will be
** identified by the WO_EQUIV bit in the pTerm->eOperator field.  The
** aEquiv[] array holds X and all its equivalents, with each SQL variable
** taking up two slots in aEquiv[].  The first slot is for the cursor number
** and the second is for the column number.  There are 22 slots in aEquiv[]
** so that means we can look for X plus up to 10 other equivalent values.
** Hence a search for X will return <expr> if X=A1 and A1=A2 and A2=A3
** and ... and A9=A10 and A10=<expr>.
**
** If there are multiple terms in the WHERE clause of the form "X <op> <expr>"
** then try for the one with no dependencies on <expr> - in other words where
** <expr> is a constant expression of some kind.  Only return entries of
** the form "X <op> Y" where Y is a column in another table if no terms of
** the form "X <op> <const-expr>" exist.  Other than this priority, if there
** are two or more terms that match, then the choice of which term to return
** is arbitrary.
*/
static WhereTerm *findTerm(
  WhereClause *pWC,     /* The WHERE clause to be searched */
  int iCur,             /* Cursor number of LHS */
  int iColumn,          /* Column number of LHS */
  Bitmask notReady,     /* RHS must not overlap with this mask */
  u32 op,               /* Mask of WO_xx values describing operator */
  Index *pIdx           /* Must be compatible with this index, if not NULL */
){
  WhereTerm *pTerm;            /* Term being examined as possible result */
  WhereTerm *pResult = 0;      /* The answer to return */
  WhereClause *pWCOrig = pWC;  /* Original pWC value */
  int j, k;                    /* Loop counters */
  Expr *pX;                /* Pointer to an expression */
  Parse *pParse;           /* Parsing context */
  int iOrigCol = iColumn;  /* Original value of iColumn */
  int nEquiv = 2;          /* Number of entires in aEquiv[] */
  int iEquiv = 2;          /* Number of entries of aEquiv[] processed so far */
  int aEquiv[22];          /* iCur,iColumn and up to 10 other equivalents */

  assert( iCur>=0 );
  aEquiv[0] = iCur;
  aEquiv[1] = iColumn;
  for(;;){
    for(pWC=pWCOrig; pWC; pWC=pWC->pOuter){
      for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){
        if( pTerm->leftCursor==iCur

          && pTerm->u.leftColumn==iColumn
        ){
          if( (pTerm->prereqRight & notReady)==0
           && (pTerm->eOperator & op & WO_ALL)!=0
          ){
            if( iOrigCol>=0 && pIdx && (pTerm->eOperator & WO_ISNULL)==0 ){

              CollSeq *pColl;
              char idxaff;
      
              pX = pTerm->pExpr;
              pParse = pWC->pParse;

              idxaff = pIdx->pTable->aCol[iOrigCol].affinity;
              if( !sqlite3IndexAffinityOk(pX, idxaff) ){
                continue;
              }
      
              /* Figure out the collation sequence required from an index for
              ** it to be useful for optimising expression pX. Store this
              ** value in variable pColl.
              */
              assert(pX->pLeft);
              pColl = sqlite3BinaryCompareCollSeq(pParse,pX->pLeft,pX->pRight);
              if( pColl==0 ) pColl = pParse->db->pDfltColl;
      
              for(j=0; pIdx->aiColumn[j]!=iOrigCol; j++){
                if( NEVER(j>=pIdx->nColumn) ) return 0;
              }
              if( sqlite3StrICmp(pColl->zName, pIdx->azColl[j]) ){
                continue;
              }
            }
            pResult = pTerm;
            if( pTerm->prereqRight==0 ) goto findTerm_success;
          }
          if( (pTerm->eOperator & WO_EQUIV)!=0
           && nEquiv<ArraySize(aEquiv)
          ){
            pX = sqlite3ExprSkipCollate(pTerm->pExpr->pRight);
            assert( pX->op==TK_COLUMN );
            for(j=0; j<nEquiv; j+=2){
              if( aEquiv[j]==pX->iTable && aEquiv[j+1]==pX->iColumn ) break;
            }
            if( j==nEquiv ){
              aEquiv[j] = pX->iTable;
              aEquiv[j+1] = pX->iColumn;
              nEquiv += 2;
            }
          }
        }
      }
    }
    if( iEquiv>=nEquiv ) break;
    iCur = aEquiv[iEquiv++];
    iColumn = aEquiv[iEquiv++];
  }
findTerm_success:
  return pResult;
}

/* Forward reference */
static void exprAnalyze(SrcList*, WhereClause*, int);

/*
** Call exprAnalyze on all terms in a WHERE clause.  

  ** Compute the set of tables that might satisfy cases 1 or 2.
  */
  indexable = ~(Bitmask)0;
  chngToIN = ~(pWC->vmask);
  for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0 && indexable; i--, pOrTerm++){
    if( (pOrTerm->eOperator & WO_SINGLE)==0 ){
      WhereAndInfo *pAndInfo;

      assert( (pOrTerm->wtFlags & (TERM_ANDINFO|TERM_ORINFO))==0 );
      chngToIN = 0;
      pAndInfo = sqlite3DbMallocRaw(db, sizeof(*pAndInfo));
      if( pAndInfo ){
        WhereClause *pAndWC;
        WhereTerm *pAndTerm;
        int j;

      Bitmask b;
      b = getMask(pMaskSet, pOrTerm->leftCursor);
      if( pOrTerm->wtFlags & TERM_VIRTUAL ){
        WhereTerm *pOther = &pOrWc->a[pOrTerm->iParent];
        b |= getMask(pMaskSet, pOther->leftCursor);
      }
      indexable &= b;
      if( (pOrTerm->eOperator & WO_EQ)==0 ){
        chngToIN = 0;
      }else{
        chngToIN &= b;
      }
    }
  }

    ** will be recorded in iCursor and iColumn.  There might not be any
    ** such table and column.  Set okToChngToIN if an appropriate table
    ** and column is found but leave okToChngToIN false if not found.
    */
    for(j=0; j<2 && !okToChngToIN; j++){
      pOrTerm = pOrWc->a;
      for(i=pOrWc->nTerm-1; i>=0; i--, pOrTerm++){
        assert( pOrTerm->eOperator & WO_EQ );
        pOrTerm->wtFlags &= ~TERM_OR_OK;
        if( pOrTerm->leftCursor==iCursor ){
          /* This is the 2-bit case and we are on the second iteration and
          ** current term is from the first iteration.  So skip this term. */
          assert( j==1 );
          continue;
        }

        iCursor = pOrTerm->leftCursor;
        break;
      }
      if( i<0 ){
        /* No candidate table+column was found.  This can only occur
        ** on the second iteration */
        assert( j==1 );
        assert( IsPowerOfTwo(chngToIN) );
        assert( chngToIN==getMask(pMaskSet, iCursor) );
        break;
      }
      testcase( j==1 );

      /* We have found a candidate table and column.  Check to see if that
      ** table and column is common to every term in the OR clause */
      okToChngToIN = 1;
      for(; i>=0 && okToChngToIN; i--, pOrTerm++){
        assert( pOrTerm->eOperator & WO_EQ );
        if( pOrTerm->leftCursor!=iCursor ){
          pOrTerm->wtFlags &= ~TERM_OR_OK;
        }else if( pOrTerm->u.leftColumn!=iColumn ){
          okToChngToIN = 0;
        }else{
          int affLeft, affRight;
          /* If the right-hand side is also a column, then the affinities

      Expr *pDup;            /* A transient duplicate expression */
      ExprList *pList = 0;   /* The RHS of the IN operator */
      Expr *pLeft = 0;       /* The LHS of the IN operator */
      Expr *pNew;            /* The complete IN operator */

      for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0; i--, pOrTerm++){
        if( (pOrTerm->wtFlags & TERM_OR_OK)==0 ) continue;
        assert( pOrTerm->eOperator & WO_EQ );
        assert( pOrTerm->leftCursor==iCursor );
        assert( pOrTerm->u.leftColumn==iColumn );
        pDup = sqlite3ExprDup(db, pOrTerm->pExpr->pRight, 0);
        pList = sqlite3ExprListAppend(pWC->pParse, pList, pDup);
        pLeft = pOrTerm->pExpr->pLeft;
      }
      assert( pLeft!=0 );

        sqlite3ExprListDelete(db, pList);
      }
      pTerm->eOperator = WO_NOOP;  /* case 1 trumps case 2 */
    }
  }
}
#endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */


/*
** The input to this routine is an WhereTerm structure with only the
** "pExpr" field filled in.  The job of this routine is to analyze the
** subexpression and populate all the other fields of the WhereTerm
** structure.
**

    extraRight = x-1;  /* ON clause terms may not be used with an index
                       ** on left table of a LEFT JOIN.  Ticket #3015 */
  }
  pTerm->prereqAll = prereqAll;
  pTerm->leftCursor = -1;
  pTerm->iParent = -1;
  pTerm->eOperator = 0;
  if( allowedOp(op) ){
    Expr *pLeft = sqlite3ExprSkipCollate(pExpr->pLeft);
    Expr *pRight = sqlite3ExprSkipCollate(pExpr->pRight);
    u16 opMask = (pTerm->prereqRight & prereqLeft)==0 ? WO_ALL : WO_EQUIV;
    if( pLeft->op==TK_COLUMN ){
      pTerm->leftCursor = pLeft->iTable;
      pTerm->u.leftColumn = pLeft->iColumn;
      pTerm->eOperator = operatorMask(op) & opMask;
    }
    if( pRight && pRight->op==TK_COLUMN ){
      WhereTerm *pNew;
      Expr *pDup;
      u16 eExtraOp = 0;        /* Extra bits for pNew->eOperator */
      if( pTerm->leftCursor>=0 ){
        int idxNew;
        pDup = sqlite3ExprDup(db, pExpr, 0);
        if( db->mallocFailed ){
          sqlite3ExprDelete(db, pDup);
          return;
        }
        idxNew = whereClauseInsert(pWC, pDup, TERM_VIRTUAL|TERM_DYNAMIC);
        if( idxNew==0 ) return;
        pNew = &pWC->a[idxNew];
        pNew->iParent = idxTerm;
        pTerm = &pWC->a[idxTerm];
        pTerm->nChild = 1;
        pTerm->wtFlags |= TERM_COPIED;
        if( pExpr->op==TK_EQ
         && !ExprHasProperty(pExpr, EP_FromJoin)
         && OptimizationEnabled(db, SQLITE_Transitive)
        ){
          pTerm->eOperator |= WO_EQUIV;
          eExtraOp = WO_EQUIV;
        }
      }else{
        pDup = pExpr;
        pNew = pTerm;
      }
      exprCommute(pParse, pDup);
      pLeft = sqlite3ExprSkipCollate(pDup->pLeft);
      pNew->leftCursor = pLeft->iTable;
      pNew->u.leftColumn = pLeft->iColumn;
      testcase( (prereqLeft | extraRight) != prereqLeft );
      pNew->prereqRight = prereqLeft | extraRight;
      pNew->prereqAll = prereqAll;
      pNew->eOperator = (operatorMask(pDup->op) + eExtraOp) & opMask;
    }
  }

#ifndef SQLITE_OMIT_BETWEEN_OPTIMIZATION
  /* If a term is the BETWEEN operator, create two new virtual terms
  ** that define the range that the BETWEEN implements.  For example:
  **

  }
  if( pWC->wctrlFlags & WHERE_AND_ONLY ){
    return;
  }

  /* Search the WHERE clause terms for a usable WO_OR term. */
  for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
    if( (pTerm->eOperator & WO_OR)!=0
     && ((pTerm->prereqAll & ~maskSrc) & p->notReady)==0
     && (pTerm->u.pOrInfo->indexable & maskSrc)!=0 
    ){
      WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc;
      WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm];
      WhereTerm *pOrTerm;
      int flags = WHERE_MULTI_OR;
      double rTotal = 0;
      double nRow = 0;
      Bitmask used = 0;
      WhereBestIdx sBOI;

      sBOI = *p;
      sBOI.pOrderBy = 0;
      sBOI.pDistinct = 0;
      sBOI.ppIdxInfo = 0;
      for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){
        WHERETRACE(("... Multi-index OR testing for term %d of %d....\n", 
          (pOrTerm - pOrWC->a), (pTerm - pWC->a)
        ));
        if( (pOrTerm->eOperator& WO_AND)!=0 ){
          sBOI.pWC = &pOrTerm->u.pAndInfo->wc;
          bestIndex(&sBOI);
        }else if( pOrTerm->leftCursor==iCur ){
          WhereClause tempWC;
          tempWC.pParse = pWC->pParse;
          tempWC.pMaskSet = pWC->pMaskSet;
          tempWC.pOuter = pWC;

static int termCanDriveIndex(
  WhereTerm *pTerm,              /* WHERE clause term to check */
  struct SrcList_item *pSrc,     /* Table we are trying to access */
  Bitmask notReady               /* Tables in outer loops of the join */
){
  char aff;
  if( pTerm->leftCursor!=pSrc->iCursor ) return 0;
  if( (pTerm->eOperator & WO_EQ)==0 ) return 0;
  if( (pTerm->prereqRight & notReady)!=0 ) return 0;
  aff = pSrc->pTab->aCol[pTerm->u.leftColumn].affinity;
  if( !sqlite3IndexAffinityOk(pTerm->pExpr, aff) ) return 0;
  return 1;
}
#endif

  WHERETRACE(("Recomputing index info for %s...\n", pSrc->pTab->zName));

  /* Count the number of possible WHERE clause constraints referring
  ** to this virtual table */
  for(i=nTerm=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
    if( pTerm->leftCursor != pSrc->iCursor ) continue;
    assert( IsPowerOfTwo(pTerm->eOperator & ~WO_EQUIV) );
    testcase( pTerm->eOperator & WO_IN );
    testcase( pTerm->eOperator & WO_ISNULL );
    if( pTerm->eOperator & (WO_ISNULL) ) continue;
    if( pTerm->wtFlags & TERM_VNULL ) continue;
    nTerm++;
  }

  /* If the ORDER BY clause contains only columns in the current 
  ** virtual table then allocate space for the aOrderBy part of

  *(struct sqlite3_index_orderby**)&pIdxInfo->aOrderBy = pIdxOrderBy;
  *(struct sqlite3_index_constraint_usage**)&pIdxInfo->aConstraintUsage =
                                                                   pUsage;

  for(i=j=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
    u8 op;
    if( pTerm->leftCursor != pSrc->iCursor ) continue;
    assert( IsPowerOfTwo(pTerm->eOperator & ~WO_EQUIV) );
    testcase( pTerm->eOperator & WO_IN );
    testcase( pTerm->eOperator & WO_ISNULL );
    if( pTerm->eOperator & (WO_ISNULL) ) continue;
    if( pTerm->wtFlags & TERM_VNULL ) continue;
    pIdxCons[j].iColumn = pTerm->u.leftColumn;
    pIdxCons[j].iTermOffset = i;
    op = (u8)pTerm->eOperator & WO_ALL;
    if( op==WO_IN ) op = WO_EQ;
    pIdxCons[j].op = op;
    /* The direct assignment in the previous line is possible only because
    ** the WO_ and SQLITE_INDEX_CONSTRAINT_ codes are identical.  The
    ** following asserts verify this fact. */
    assert( WO_EQ==SQLITE_INDEX_CONSTRAINT_EQ );
    assert( WO_LT==SQLITE_INDEX_CONSTRAINT_LT );

    */
    pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
    pUsage = pIdxInfo->aConstraintUsage;
    for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){
      j = pIdxCons->iTermOffset;
      pTerm = &pWC->a[j];
      if( (pTerm->prereqRight&p->notReady)==0
       && (bAllowIN || (pTerm->eOperator & WO_IN)==0)
      ){
        pIdxCons->usable = 1;
      }else{
        pIdxCons->usable = 0;
      }
    }
    memset(pUsage, 0, sizeof(pUsage[0])*pIdxInfo->nConstraint);

  
    pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
    for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){
      if( pUsage[i].argvIndex>0 ){
        j = pIdxCons->iTermOffset;
        pTerm = &pWC->a[j];
        p->cost.used |= pTerm->prereqRight;
        if( (pTerm->eOperator & WO_IN)!=0 && pUsage[i].omit==0 ){
          /* Do not attempt to use an IN constraint if the virtual table
          ** says that the equivalent EQ constraint cannot be safely omitted.
          ** If we do attempt to use such a constraint, some rows might be
          ** repeated in the output. */
          break;
        }
      }

    tRowcnt iUpper = p->aiRowEst[0];
    tRowcnt a[2];
    u8 aff = p->pTable->aCol[p->aiColumn[0]].affinity;

    if( pLower ){
      Expr *pExpr = pLower->pExpr->pRight;
      rc = valueFromExpr(pParse, pExpr, aff, &pRangeVal);
      assert( (pLower->eOperator & (WO_GT|WO_GE))!=0 );
      if( rc==SQLITE_OK
       && whereKeyStats(pParse, p, pRangeVal, 0, a)==SQLITE_OK
      ){
        iLower = a[0];
        if( (pLower->eOperator & WO_GT)!=0 ) iLower += a[1];
      }
      sqlite3ValueFree(pRangeVal);
    }
    if( rc==SQLITE_OK && pUpper ){
      Expr *pExpr = pUpper->pExpr->pRight;
      rc = valueFromExpr(pParse, pExpr, aff, &pRangeVal);
      assert( (pUpper->eOperator & (WO_LT|WO_LE))!=0 );
      if( rc==SQLITE_OK
       && whereKeyStats(pParse, p, pRangeVal, 1, a)==SQLITE_OK
      ){
        iUpper = a[0];
        if( (pUpper->eOperator & WO_LE)!=0 ) iUpper += a[1];
      }
      sqlite3ValueFree(pRangeVal);
    }
    if( rc==SQLITE_OK ){
      if( iUpper<=iLower ){
        *pRangeDiv = (double)p->aiRowEst[0];
      }else{

    /* If X is the column in the index and ORDER BY clause, check to see
    ** if there are any X= or X IS NULL constraints in the WHERE clause. */
    pConstraint = findTerm(p->pWC, base, iColumn, p->notReady,
                           WO_EQ|WO_ISNULL|WO_IN, pIdx);
    if( pConstraint==0 ){
      isEq = 0;
    }else if( (pConstraint->eOperator & WO_IN)!=0 ){
      /* Constraints of the form: "X IN ..." cannot be used with an ORDER BY
      ** because we do not know in what order the values on the RHS of the IN
      ** operator will occur. */
      break;
    }else if( (pConstraint->eOperator & WO_ISNULL)!=0 ){
      uniqueNotNull = 0;
      isEq = 1;  /* "X IS NULL" means X has only a single value */
    }else if( pConstraint->prereqRight==0 ){
      isEq = 1;  /* Constraint "X=constant" means X has only a single value */
    }else{
      Expr *pRight = pConstraint->pExpr->pRight;
      if( pRight->op==TK_COLUMN ){

    ** to get a better estimate on the number of rows based on
    ** VALUE and how common that value is according to the histogram.
    */
    if( pc.plan.nRow>(double)1 && pc.plan.nEq==1
     && pFirstTerm!=0 && aiRowEst[1]>1 ){
      assert( (pFirstTerm->eOperator & (WO_EQ|WO_ISNULL|WO_IN))!=0 );
      if( pFirstTerm->eOperator & (WO_EQ|WO_ISNULL) ){
        testcase( pFirstTerm->eOperator & WO_EQ );
        testcase( pFirstTerm->eOperator & WO_EQUIV );
        testcase( pFirstTerm->eOperator & WO_ISNULL );
        whereEqualScanEst(pParse, pProbe, pFirstTerm->pExpr->pRight,
                          &pc.plan.nRow);
      }else if( bInEst==0 ){
        assert( pFirstTerm->eOperator & WO_IN );
        whereInScanEst(pParse, pProbe, pFirstTerm->pExpr->x.pList,
                       &pc.plan.nRow);
      }
    }
#endif /* SQLITE_ENABLE_STAT3 */

    /* Adjust the number of output rows and downward to reflect rows

            ** set size by a factor of 3.  Indexed range constraints reduce
            ** the search space by a larger factor: 4.  We make indexed range
            ** more selective intentionally because of the subjective 
            ** observation that indexed range constraints really are more
            ** selective in practice, on average. */
            pc.plan.nRow /= 3;
          }
        }else if( (pTerm->eOperator & WO_NOOP)==0 ){
          /* Any other expression lowers the output row count by half */
          pc.plan.nRow /= 2;
        }
      }
      if( pc.plan.nRow<2 ) pc.plan.nRow = 2;
    }

  assert( p->pOrderBy || (p->cost.plan.wsFlags&WHERE_ORDERED)==0 );
  assert( p->cost.plan.u.pIdx==0 || (p->cost.plan.wsFlags&WHERE_ROWID_EQ)==0 );
  assert( pSrc->pIndex==0 
       || p->cost.plan.u.pIdx==0 
       || p->cost.plan.u.pIdx==pSrc->pIndex 
  );

  WHERETRACE(("   best index is %s cost=%.1f\n",
         p->cost.plan.u.pIdx ? p->cost.plan.u.pIdx->zName : "ipk",
         p->cost.rCost));
  
  bestOrClauseIndex(p);
  bestAutomaticIndex(p);
  p->cost.plan.wsFlags |= eqTermMask;
}

/*

    **          we reference multiple rows using a "rowid IN (...)"
    **          construct.
    */
    iReleaseReg = sqlite3GetTempReg(pParse);
    pTerm = findTerm(pWC, iCur, -1, notReady, WO_EQ|WO_IN, 0);
    assert( pTerm!=0 );
    assert( pTerm->pExpr!=0 );

    assert( omitTable==0 );
    testcase( pTerm->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
    iRowidReg = codeEqualityTerm(pParse, pTerm, pLevel, iReleaseReg);
    addrNxt = pLevel->addrNxt;
    sqlite3VdbeAddOp2(v, OP_MustBeInt, iRowidReg, addrNxt);
    sqlite3VdbeAddOp3(v, OP_NotExists, iCur, addrNxt, iRowidReg);
    sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg);

    int iRetInit;                             /* Address of regReturn init */
    int untestedTerms = 0;             /* Some terms not completely tested */
    int ii;                            /* Loop counter */
    Expr *pAndExpr = 0;                /* An ".. AND (...)" expression */
   
    pTerm = pLevel->plan.u.pTerm;
    assert( pTerm!=0 );
    assert( pTerm->eOperator & WO_OR );
    assert( (pTerm->wtFlags & TERM_ORINFO)!=0 );
    pOrWc = &pTerm->u.pOrInfo->wc;
    pLevel->op = OP_Return;
    pLevel->p1 = regReturn;

    /* Set up a new SrcList in pOrTab containing the table being scanned
    ** by this loop in the a[0] slot and all notReady tables in a[1..] slots.

      if( pAndExpr ){
        pAndExpr = sqlite3PExpr(pParse, TK_AND, 0, pAndExpr, 0);
      }
    }

    for(ii=0; ii<pOrWc->nTerm; ii++){
      WhereTerm *pOrTerm = &pOrWc->a[ii];
      if( pOrTerm->leftCursor==iCur || (pOrTerm->eOperator & WO_AND)!=0 ){
        WhereInfo *pSubWInfo;          /* Info for single OR-term scan */
        Expr *pOrExpr = pOrTerm->pExpr;
        if( pAndExpr ){
          pAndExpr->pLeft = pOrExpr;
          pOrExpr = pAndExpr;
        }
        /* Loop through table entries that match term pOrTerm. */

  for(sWBI.i=iFrom=0, pLevel=pWInfo->a; sWBI.i<nTabList; sWBI.i++, pLevel++){
    WhereCost bestPlan;         /* Most efficient plan seen so far */
    Index *pIdx;                /* Index for FROM table at pTabItem */
    int j;                      /* For looping over FROM tables */
    int bestJ = -1;             /* The value of j */
    Bitmask m;                  /* Bitmask value for j or bestJ */
    int isOptimal;              /* Iterator for optimal/non-optimal search */
    int ckOptimal;              /* Do the optimal scan check */
    int nUnconstrained;         /* Number tables without INDEXED BY */
    Bitmask notIndexed;         /* Mask of tables that cannot use an index */

    memset(&bestPlan, 0, sizeof(bestPlan));
    bestPlan.rCost = SQLITE_BIG_DBL;
    WHERETRACE(("*** Begin search for loop %d ***\n", sWBI.i));

    ** that do not use indices.  But this nRow reduction only happens if the
    ** table really is the innermost join.  
    **
    ** The second loop iteration is only performed if no optimal scan
    ** strategies were found by the first iteration. This second iteration
    ** is used to search for the lowest cost scan overall.
    **
    ** Without the optimal scan step (the first iteration) a suboptimal


    ** plan might be chosen for queries like this:
    **   
    **   CREATE TABLE t1(a, b); 
    **   CREATE TABLE t2(c, d);
    **   SELECT * FROM t2, t1 WHERE t2.rowid = t1.a;
    **
    ** The best strategy is to iterate through table t1 first. However it
    ** is not possible to determine this with a simple greedy algorithm.
    ** Since the cost of a linear scan through table t2 is the same 
    ** as the cost of a linear scan through table t1, a simple greedy 
    ** algorithm may choose to use t2 for the outer loop, which is a much
    ** costlier approach.
    */
    nUnconstrained = 0;
    notIndexed = 0;

    /* The optimal scan check only occurs if there are two or more tables
    ** available to be reordered */
    if( iFrom==nTabList-1 ){
      ckOptimal = 0;  /* Common case of just one table in the FROM clause */
    }else{
      ckOptimal = -1;
      for(j=iFrom, sWBI.pSrc=&pTabList->a[j]; j<nTabList; j++, sWBI.pSrc++){




        m = getMask(pMaskSet, sWBI.pSrc->iCursor);
        if( (m & sWBI.notValid)==0 ){
          if( j==iFrom ) iFrom++;
          continue;
        }
        if( j>iFrom && (sWBI.pSrc->jointype & (JT_LEFT|JT_CROSS))!=0 ) break;
        if( ++ckOptimal ) break;
        if( (sWBI.pSrc->jointype & JT_LEFT)!=0 ) break;
      }
    }
    assert( ckOptimal==0 || ckOptimal==1 );

    for(isOptimal=ckOptimal; isOptimal>=0 && bestJ<0; isOptimal--){
      for(j=iFrom, sWBI.pSrc=&pTabList->a[j]; j<nTabList; j++, sWBI.pSrc++){
        if( j>iFrom && (sWBI.pSrc->jointype & (JT_LEFT|JT_CROSS))!=0 ){
          /* This break and one like it in the ckOptimal computation loop
          ** above prevent table reordering across LEFT and CROSS JOINs.
          ** The LEFT JOIN case is necessary for correctness.  The prohibition
          ** against reordering across a CROSS JOIN is an SQLite feature that
          ** allows the developer to control table reordering */
          break;
        }
        m = getMask(pMaskSet, sWBI.pSrc->iCursor);
        if( (m & sWBI.notValid)==0 ){
          assert( j>iFrom );
          continue;
        }
        sWBI.notReady = (isOptimal ? m : sWBI.notValid);
        if( sWBI.pSrc->pIndex==0 ) nUnconstrained++;
  
        WHERETRACE(("   === trying table %d (%s) with isOptimal=%d ===\n",
                    j, sWBI.pSrc->pTab->zName, isOptimal));
        assert( sWBI.pSrc->pTab );

                  || sWBI.cost.plan.u.pIdx==sWBI.pSrc->pIndex );

        if( isOptimal && (sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)==0 ){
          notIndexed |= m;
        }
        if( isOptimal ){
          pWInfo->a[j].rOptCost = sWBI.cost.rCost;
        }else if( ckOptimal ){
          /* If two or more tables have nearly the same outer loop cost, but
          ** very different inner loop (optimal) cost, we want to choose
          ** for the outer loop that table which benefits the least from
          ** being in the inner loop.  The following code scales the 
          ** outer loop cost estimate to accomplish that. */
          WHERETRACE(("   scaling cost from %.1f to %.1f\n",
                      sWBI.cost.rCost,
                      sWBI.cost.rCost/pWInfo->a[j].rOptCost));

                      "       cost=%.1f, nRow=%.1f, nOBSat=%d, wsFlags=%08x\n",
                      j, sWBI.pSrc->pTab->zName,
                      sWBI.cost.rCost, sWBI.cost.plan.nRow,
                      sWBI.cost.plan.nOBSat, sWBI.cost.plan.wsFlags));
          bestPlan = sWBI.cost;
          bestJ = j;
        }

        /* In a join like "w JOIN x LEFT JOIN y JOIN z"  make sure that
        ** table y (and not table z) is always the next inner loop inside
        ** of table x. */
        if( (sWBI.pSrc->jointype & JT_LEFT)!=0 ) break;
      }
    }
    assert( bestJ>=0 );
    assert( sWBI.notValid & getMask(pMaskSet, pTabList->a[bestJ].iCursor) );
    assert( bestJ==iFrom || (pTabList->a[iFrom].jointype & JT_LEFT)==0 );
    testcase( bestJ>iFrom && (pTabList->a[iFrom].jointype & JT_CROSS)!=0 );
    testcase( bestJ>iFrom && bestJ<nTabList-1
                          && (pTabList->a[bestJ+1].jointype & JT_LEFT)!=0 );
    WHERETRACE(("*** Optimizer selects table %d (%s) for loop %d with:\n"
                "    cost=%.1f, nRow=%.1f, nOBSat=%d, wsFlags=0x%08x\n",
                bestJ, pTabList->a[bestJ].pTab->zName,
                pLevel-pWInfo->a, bestPlan.rCost, bestPlan.plan.nRow,
                bestPlan.plan.nOBSat, bestPlan.plan.wsFlags));
    if( (bestPlan.plan.wsFlags & WHERE_DISTINCT)!=0 ){
      assert( pWInfo->eDistinct==0 );

  CREATE TABLE t5(a, b, c);
  EXPLAIN QUERY PLAN SELECT a FROM t5 WHERE b=10 ORDER BY c;
} {
  0 0 0 {SCAN TABLE t5 (~100000 rows)} 
  0 0 0 {USE TEMP B-TREE FOR ORDER BY}
}

# The following checks a performance issue reported on the sqlite-dev
# mailing list on 2013-01-10
#
do_execsql_test autoindex1-800 {
  CREATE TABLE accounts(
    _id INTEGER PRIMARY KEY AUTOINCREMENT,
    account_name TEXT,
    account_type TEXT,
    data_set TEXT
  );
  CREATE TABLE data(
    _id INTEGER PRIMARY KEY AUTOINCREMENT,
    package_id INTEGER REFERENCES package(_id),
    mimetype_id INTEGER REFERENCES mimetype(_id) NOT NULL,
    raw_contact_id INTEGER REFERENCES raw_contacts(_id) NOT NULL,
    is_read_only INTEGER NOT NULL DEFAULT 0,
    is_primary INTEGER NOT NULL DEFAULT 0,
    is_super_primary INTEGER NOT NULL DEFAULT 0,
    data_version INTEGER NOT NULL DEFAULT 0,
    data1 TEXT,
    data2 TEXT,
    data3 TEXT,
    data4 TEXT,
    data5 TEXT,
    data6 TEXT,
    data7 TEXT,
    data8 TEXT,
    data9 TEXT,
    data10 TEXT,
    data11 TEXT,
    data12 TEXT,
    data13 TEXT,
    data14 TEXT,
    data15 TEXT,
    data_sync1 TEXT,
    data_sync2 TEXT,
    data_sync3 TEXT,
    data_sync4 TEXT 
  );
  CREATE TABLE mimetypes(
    _id INTEGER PRIMARY KEY AUTOINCREMENT,
    mimetype TEXT NOT NULL
  );
  CREATE TABLE raw_contacts(
    _id INTEGER PRIMARY KEY AUTOINCREMENT,
    account_id INTEGER REFERENCES accounts(_id),
    sourceid TEXT,
    raw_contact_is_read_only INTEGER NOT NULL DEFAULT 0,
    version INTEGER NOT NULL DEFAULT 1,
    dirty INTEGER NOT NULL DEFAULT 0,
    deleted INTEGER NOT NULL DEFAULT 0,
    contact_id INTEGER REFERENCES contacts(_id),
    aggregation_mode INTEGER NOT NULL DEFAULT 0,
    aggregation_needed INTEGER NOT NULL DEFAULT 1,
    custom_ringtone TEXT,
    send_to_voicemail INTEGER NOT NULL DEFAULT 0,
    times_contacted INTEGER NOT NULL DEFAULT 0,
    last_time_contacted INTEGER,
    starred INTEGER NOT NULL DEFAULT 0,
    display_name TEXT,
    display_name_alt TEXT,
    display_name_source INTEGER NOT NULL DEFAULT 0,
    phonetic_name TEXT,
    phonetic_name_style TEXT,
    sort_key TEXT,
    sort_key_alt TEXT,
    name_verified INTEGER NOT NULL DEFAULT 0,
    sync1 TEXT,
    sync2 TEXT,
    sync3 TEXT,
    sync4 TEXT,
    sync_uid TEXT,
    sync_version INTEGER NOT NULL DEFAULT 1,
    has_calendar_event INTEGER NOT NULL DEFAULT 0,
    modified_time INTEGER,
    is_restricted INTEGER DEFAULT 0,
    yp_source TEXT,
    method_selected INTEGER DEFAULT 0,
    custom_vibration_type INTEGER DEFAULT 0,
    custom_ringtone_path TEXT,
    message_notification TEXT,
    message_notification_path TEXT
  );
  CREATE INDEX data_mimetype_data1_index ON data (mimetype_id,data1);
  CREATE INDEX data_raw_contact_id ON data (raw_contact_id);
  CREATE UNIQUE INDEX mime_type ON mimetypes (mimetype);
  CREATE INDEX raw_contact_sort_key1_index ON raw_contacts (sort_key);
  CREATE INDEX raw_contact_sort_key2_index ON raw_contacts (sort_key_alt);
  CREATE INDEX raw_contacts_contact_id_index ON raw_contacts (contact_id);
  CREATE INDEX raw_contacts_source_id_account_id_index
      ON raw_contacts (sourceid, account_id);
  ANALYZE sqlite_master;
  INSERT INTO sqlite_stat1
     VALUES('raw_contacts','raw_contact_sort_key2_index','1600 4');
  INSERT INTO sqlite_stat1
     VALUES('raw_contacts','raw_contact_sort_key1_index','1600 4');
  INSERT INTO sqlite_stat1
     VALUES('raw_contacts','raw_contacts_source_id_account_id_index',
            '1600 1600 1600');
  INSERT INTO sqlite_stat1
     VALUES('raw_contacts','raw_contacts_contact_id_index','1600 1');
  INSERT INTO sqlite_stat1 VALUES('mimetypes','mime_type','12 1');
  INSERT INTO sqlite_stat1
     VALUES('data','data_mimetype_data1_index','9819 2455 3');
  INSERT INTO sqlite_stat1 VALUES('data','data_raw_contact_id','9819 7');
  INSERT INTO sqlite_stat1 VALUES('accounts',NULL,'1');
  DROP TABLE IF EXISTS sqlite_stat3;
  ANALYZE sqlite_master;
  
  EXPLAIN QUERY PLAN
  SELECT * FROM 
        data JOIN mimetypes ON (data.mimetype_id=mimetypes._id) 
             JOIN raw_contacts ON (data.raw_contact_id=raw_contacts._id) 
             JOIN accounts ON (raw_contacts.account_id=accounts._id)
   WHERE mimetype_id=10 AND data14 IS NOT NULL;
} {/SEARCH TABLE data .*SEARCH TABLE raw_contacts/}
do_execsql_test autoindex1-801 {
  EXPLAIN QUERY PLAN
  SELECT * FROM 
        data JOIN mimetypes ON (data.mimetype_id=mimetypes._id) 
             JOIN raw_contacts ON (data.raw_contact_id=raw_contacts._id) 
             JOIN accounts ON (raw_contacts.account_id=accounts._id)
   WHERE mimetypes._id=10 AND data14 IS NOT NULL;
} {/SEARCH TABLE data .*SEARCH TABLE raw_contacts/}

finish_test

#   7.* - Test that if content=xxx is specified and table xxx does not
#         exist, the FTS table can still be used for INSERT and some
#         SELECT statements.
#
#   8.* - Test that if the content=xxx and prefix options are used together,
#         the 'rebuild' command still works.
#
#   9.* - Test using content=xxx where xxx is a virtual table.
#

do_execsql_test 1.1.1 {
  CREATE TABLE t1(a, b, c);
  INSERT INTO t1 VALUES('w x', 'x y', 'y z');
  CREATE VIRTUAL TABLE ft1 USING fts4(content=t1);
}

}

do_execsql_test 8.2 { SELECT * FROM ft10 WHERE a MATCH 'ab*';          }
do_execsql_test 8.3 { INSERT INTO ft10(ft10) VALUES('rebuild');        }
do_execsql_test 8.4 { SELECT rowid FROM ft10 WHERE a MATCH 'ab*';      } {1 2 3}
do_execsql_test 8.5 { SELECT rowid FROM ft10 WHERE b MATCH 'abav*';    } {3}
do_execsql_test 8.6 { SELECT rowid FROM ft10 WHERE ft10 MATCH 'abas*'; } {1}

#-------------------------------------------------------------------------
# Test cases 9.*
# 
reset_db
register_echo_module [sqlite3_connection_pointer db]

do_execsql_test 9.1 {
  CREATE TABLE tbl1(a, b);
  INSERT INTO tbl1 VALUES('a b', 'c d');
  INSERT INTO tbl1 VALUES('e f', 'a b');
  CREATE VIRTUAL TABLE e1 USING echo(tbl1);
  CREATE VIRTUAL TABLE ft1 USING fts4(content=e1);
  INSERT INTO ft1(ft1) VALUES('rebuild');
}

do_execsql_test 9.2 {
  SELECT rowid, * FROM ft1 WHERE ft1 MATCH 'e'
} {2 {e f} {a b}}

do_execsql_test 9.3 {
  SELECT rowid, * FROM ft1 WHERE ft1 MATCH 'a'
} {1 {a b} {c d} 2 {e f} {a b}}

do_execsql_test 9.4 { 
  DELETE FROM ft1 WHERE docid=1;
}

do_execsql_test 9.5 {
  SELECT rowid, * FROM ft1 WHERE ft1 MATCH 'a'
} {2 {e f} {a b}}

do_execsql_test 9.6 {
  INSERT INTO ft1(ft1) VALUES('rebuild');
  SELECT rowid, * FROM ft1 WHERE ft1 MATCH 'a'
} {1 {a b} {c d} 2 {e f} {a b}}


#-------------------------------------------------------------------------
# Test cases 10.*
# 
reset_db
register_fs_module [sqlite3_connection_pointer db]

proc write_file {path text} {
  set fd [open $path w]
  puts -nonewline $fd $text
  close $fd
}

write_file t1.txt {a b c d e f g h i j k l m n o p q r s t u v w x y z}
write_file t2.txt {a b c d e f g h i j k l m a b c d e f g h i j k l m}
write_file t3.txt {n o p q r s t u v w x y z n o p q r s t u v w x y z}

do_execsql_test 10.1 {
  CREATE TABLE idx(id INTEGER PRIMARY KEY, path TEXT);
  INSERT INTO idx VALUES (1, 't1.txt');
  INSERT INTO idx VALUES (2, 't2.txt');
  INSERT INTO idx VALUES (3, 't3.txt');

  CREATE VIRTUAL TABLE vt USING fs(idx);
  SELECT * FROM vt;
} {
  1 {a b c d e f g h i j k l m n o p q r s t u v w x y z} 
  2 {a b c d e f g h i j k l m a b c d e f g h i j k l m}
  3 {n o p q r s t u v w x y z n o p q r s t u v w x y z}
}

do_execsql_test 10.2 {
  SELECT * FROM vt WHERE rowid = 2;
} {
  2 {a b c d e f g h i j k l m a b c d e f g h i j k l m}
}

do_execsql_test 10.3 {
  CREATE VIRTUAL TABLE ft USING fts4(content=vt);
  INSERT INTO ft(ft) VALUES('rebuild');
}

do_execsql_test 10.4 {
  SELECT snippet(ft, '[', ']', '...', -1, 5) FROM ft WHERE ft MATCH 'e'
} {
  {...c d [e] f g...} {...c d [e] f g...}
}

do_execsql_test 10.5 {
  SELECT snippet(ft, '[', ']', '...', -1, 5) FROM ft WHERE ft MATCH 't'
} {
  {...r s [t] u v...} {...r s [t] u v...}
}

do_execsql_test 10.6 { DELETE FROM ft WHERE docid=2 }

do_execsql_test 10.7 {
  SELECT snippet(ft, '[', ']', '...', -1, 5) FROM ft WHERE ft MATCH 'e'
} {
  {...c d [e] f g...}
}

finish_test

         'abc{4}x' REGEXP '^abc\{4\}x$',
         'abc|def' REGEXP '^abc\|def$'
} {1 1 1 1 1 1 1 1 1 1 1 1}

do_execsql_test regexp1-2.20 {
  SELECT 'abc$¢€xyz' REGEXP '^abc\u0024\u00a2\u20acxyz$',
         'abc$¢€xyz' REGEXP '^abc\u0024\u00A2\u20ACxyz$',
         'abc$¢€xyz' REGEXP '^abc\x24\xa2\u20acxyz$'
} {1 1 1}
do_execsql_test regexp1-2.21 {
  SELECT 'abc$¢€xyz' REGEXP '^abc[\u0024][\u00a2][\u20ac]xyz$',
         'abc$¢€xyz' REGEXP '^abc[\u0024\u00A2\u20AC]{3}xyz$',
         'abc$¢€xyz' REGEXP '^abc[\x24][\xa2\u20ac]+xyz$'
} {1 1 1}
do_execsql_test regexp1-2.22 {
  SELECT 'abc$¢€xyz' REGEXP '^abc[^\u0025-X][^ -\u007f][^\u20ab]xyz$'
} {1}

finish_test

#----------------------------------------------------------------------------
# Test cases shell1-3.*: Basic test that "dot" command can be called.
#

# .backup ?DB? FILE      Backup DB (default "main") to FILE
do_test shell1-3.1.1 {
  catchcmd "test.db" ".backup"
} {1 {missing FILENAME argument on .backup}}
do_test shell1-3.1.2 {
  catchcmd "test.db" ".backup FOO"
} {0 {}}
do_test shell1-3.1.3 {
  catchcmd "test.db" ".backup FOO BAR"
} {1 {Error: unknown database FOO}}
do_test shell1-3.1.4 {
  # too many arguments
  catchcmd "test.db" ".backup FOO BAR BAD"
} {1 {too many arguments to .backup}}

# .bail ON|OFF           Stop after hitting an error.  Default OFF
do_test shell1-3.2.1 {
  catchcmd "test.db" ".bail"
} {1 {Error: unknown command or invalid arguments:  "bail". Enter ".help" for help}}
do_test shell1-3.2.2 {
  catchcmd "test.db" ".bail ON"

# 2013 April 17
#
# 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 implements regression tests for SQLite library.  The
# focus of this script is testing of transitive WHERE clause constraints
#

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

do_execsql_test transitive1-100 {
  CREATE TABLE t1(a TEXT, b TEXT, c TEXT COLLATE NOCASE);
  INSERT INTO t1 VALUES('abc','abc','Abc');
  INSERT INTO t1 VALUES('def','def','def');
  INSERT INTO t1 VALUES('ghi','ghi','GHI');
  CREATE INDEX t1a1 ON t1(a);
  CREATE INDEX t1a2 ON t1(a COLLATE nocase);

  SELECT * FROM t1 WHERE a=b AND c=b AND c='DEF';
} {def def def}
do_execsql_test transitive1-110 {
  SELECT * FROM t1 WHERE a=b AND c=b AND c>='DEF' ORDER BY +a;
} {def def def ghi ghi GHI}
do_execsql_test transitive1-120 {
  SELECT * FROM t1 WHERE a=b AND c=b AND c<='DEF' ORDER BY +a;
} {abc abc Abc def def def}

do_execsql_test transitive1-200 {
  CREATE TABLE t2(a INTEGER, b INTEGER, c TEXT);
  INSERT INTO t2 VALUES(100,100,100);
  INSERT INTO t2 VALUES(20,20,20);
  INSERT INTO t2 VALUES(3,3,3);

  SELECT * FROM t2 WHERE a=b AND c=b AND c=20;
} {20 20 20}
do_execsql_test transitive1-210 {
  SELECT * FROM t2 WHERE a=b AND c=b AND c>=20 ORDER BY +a;
} {3 3 3 20 20 20}
do_execsql_test transitive1-220 {
  SELECT * FROM t2 WHERE a=b AND c=b AND c<=20 ORDER BY +a;
} {20 20 20 100 100 100}

finish_test