SQLite

** This routine is used to extract the "offset to cell content area" value
** from the header of a btree page.  If the page size is 65536 and the page
** is empty, the offset should be 65536, but the 2-byte value stores zero.
** This routine makes the necessary adjustment to 65536.
*/
#define get2byteNotZero(X)  (((((int)get2byte(X))-1)&0xffff)+1)

/*
** Values passed as the 5th argument to allocateBtreePage()
*/
#define BTALLOC_ANY   0           /* Allocate any page */
#define BTALLOC_EXACT 1           /* Allocate exact page if possible */
#define BTALLOC_LE    2           /* Allocate any page <= the parameter */

/*
** Macro IfNotOmitAV(x) returns (x) if SQLITE_OMIT_AUTOVACUUM is not 
** defined, or 0 if it is. For example:
**
**   bIncrVacuum = IfNotOmitAV(pBtShared->incrVacuum);
*/
#ifndef SQLITE_OMIT_AUTOVACUUM
#define IfNotOmitAV(expr) (expr)
#else
#define IfNotOmitAV(expr) 0
#endif

#ifndef SQLITE_OMIT_SHARED_CACHE
/*
** A list of BtShared objects that are eligible for participation
** in shared cache.  This variable has file scope during normal builds,
** but the test harness needs to access it so we make it global for 
** test builds.
**

  /* If the btree is already in a write-transaction, or it
  ** is already in a read-transaction and a read-transaction
  ** is requested, this is a no-op.
  */
  if( p->inTrans==TRANS_WRITE || (p->inTrans==TRANS_READ && !wrflag) ){
    goto trans_begun;
  }
  assert( pBt->bDoTruncate==0 );
  assert( IfNotOmitAV(pBt->bDoTruncate)==0 );

  /* Write transactions are not possible on a read-only database */
  if( (pBt->btsFlags & BTS_READ_ONLY)!=0 && wrflag ){
    rc = SQLITE_READONLY;
    goto trans_begun;
  }

    }
  }
  return rc;
}

/* Forward declaration required by incrVacuumStep(). */
static int allocateBtreePage(BtShared *, MemPage **, Pgno *, Pgno, u8);
#define BTALLOC_ANY   0           /* Allocate any page */
#define BTALLOC_EXACT 1           /* Allocate exact page if possible */
#define BTALLOC_LE    2           /* Allocate any page <= the parameter */

/*
** Perform a single step of an incremental-vacuum. If successful, return
** SQLITE_OK. If there is no work to do (and therefore no point in 
** calling this function again), return SQLITE_DONE. Or, if an error 
** occurs, return some other error code.
**

  u32 n;     /* Number of pages on the freelist */
  u32 k;     /* Number of leaves on the trunk of the freelist */
  MemPage *pTrunk = 0;
  MemPage *pPrevTrunk = 0;
  Pgno mxPage;     /* Total size of the database file */

  assert( sqlite3_mutex_held(pBt->mutex) );
  assert( eMode==BTALLOC_ANY || (nearby>0 && pBt->autoVacuum) );
  assert( eMode==BTALLOC_ANY || (nearby>0 && IfNotOmitAV(pBt->autoVacuum)) );
  pPage1 = pBt->pPage1;
  mxPage = btreePagecount(pBt);
  n = get4byte(&pPage1->aData[36]);
  testcase( n==mxPage-1 );
  if( n>=mxPage ){
    return SQLITE_CORRUPT_BKPT;
  }

    **
    ** Note that the pager will not actually attempt to load or journal 
    ** content for any page that really does lie past the end of the database
    ** file on disk. So the effects of disabling the no-content optimization
    ** here are confined to those pages that lie between the end of the
    ** database image and the end of the database file.
    */
    int bNoContent = (0==pBt->bDoTruncate);
    int bNoContent = (0==IfNotOmitAV(pBt->bDoTruncate));

    rc = sqlite3PagerWrite(pBt->pPage1->pDbPage);
    if( rc ) return rc;
    pBt->nPage++;
    if( pBt->nPage==PENDING_BYTE_PAGE(pBt) ) pBt->nPage++;

#ifndef SQLITE_OMIT_AUTOVACUUM

** all members of the RHS set, skipping duplicates.
**
** A cursor is opened on the b-tree object that the RHS of the IN operator
** and pX->iTable is set to the index of that cursor.
**
** The returned value of this function indicates the b-tree type, as follows:
**
**   IN_INDEX_ROWID - The cursor was opened on a database table.
**   IN_INDEX_INDEX - The cursor was opened on a database index.
**   IN_INDEX_EPH -   The cursor was opened on a specially created and
**                    populated epheremal table.
**   IN_INDEX_ROWID      - The cursor was opened on a database table.
**   IN_INDEX_INDEX_ASC  - The cursor was opened on an ascending index.
**   IN_INDEX_INDEX_DESC - The cursor was opened on a descending index.
**   IN_INDEX_EPH        - The cursor was opened on a specially created and
**                         populated epheremal table.
**
** An existing b-tree might be used if the RHS expression pX is a simple
** subquery such as:
**
**     SELECT <column> FROM <table>
**
** If the RHS of the IN operator is a list or a more complex subquery, then

  
          pKey = (char *)sqlite3IndexKeyinfo(pParse, pIdx);
          iAddr = sqlite3CodeOnce(pParse);
  
          sqlite3VdbeAddOp4(v, OP_OpenRead, iTab, pIdx->tnum, iDb,
                               pKey,P4_KEYINFO_HANDOFF);
          VdbeComment((v, "%s", pIdx->zName));
          assert( IN_INDEX_INDEX_DESC == IN_INDEX_INDEX_ASC+1 );
          eType = IN_INDEX_INDEX;
          eType = IN_INDEX_INDEX_ASC + pIdx->aSortOrder[0];

          sqlite3VdbeJumpHere(v, iAddr);
          if( prNotFound && !pTab->aCol[iCol].notNull ){
            *prNotFound = ++pParse->nMem;
            sqlite3VdbeAddOp2(v, OP_Null, 0, *prNotFound);
          }
        }

        }
      }
    }
  }else
#endif /* !defined(SQLITE_OMIT_FOREIGN_KEY) */

#ifndef SQLITE_OMIT_FOREIGN_KEY
#ifndef SQLITE_OMIT_TRIGGER
  if( sqlite3StrICmp(zLeft, "foreign_key_check")==0 ){
    FKey *pFK;             /* A foreign key constraint */
    Table *pTab;           /* Child table contain "REFERENCES" keyword */
    Table *pParent;        /* Parent table that child points to */
    Index *pIdx;           /* Index in the parent table */
    int i;                 /* Loop counter:  Foreign key number for pTab */
    int j;                 /* Loop counter:  Field of the foreign key */

        sqlite3VdbeResolveLabel(v, addrOk);
        sqlite3DbFree(db, aiCols);
      }
      sqlite3VdbeAddOp2(v, OP_Next, 0, addrTop+1);
      sqlite3VdbeJumpHere(v, addrTop);
    }
  }else
#endif /* !defined(SQLITE_OMIT_TRIGGER) */
#endif /* !defined(SQLITE_OMIT_FOREIGN_KEY) */

#ifndef NDEBUG
  if( sqlite3StrICmp(zLeft, "parser_trace")==0 ){
    if( zRight ){
      if( sqlite3GetBoolean(zRight, 0) ){
        sqlite3ParserTrace(stderr, "parser: ");

** host languages that are garbage collected, and where the order in which
** destructors are called is arbitrary.
**
** Applications should [sqlite3_finalize | finalize] all [prepared statements],
** [sqlite3_blob_close | close] all [BLOB handles], and 
** [sqlite3_backup_finish | finish] all [sqlite3_backup] objects associated
** with the [sqlite3] object prior to attempting to close the object.  ^If
** sqlite3_close() is called on a [database connection] that still has
** sqlite3_close_v2() is called on a [database connection] that still has
** outstanding [prepared statements], [BLOB handles], and/or
** [sqlite3_backup] objects then it returns SQLITE_OK but the deallocation
** of resources is deferred until all [prepared statements], [BLOB handles],
** and [sqlite3_backup] objects are also destroyed.
**
** ^If an [sqlite3] object is destroyed while a transaction is open,
** the transaction is automatically rolled back.

#endif

/* Needed for various definitions... */
#ifndef _GNU_SOURCE
# define _GNU_SOURCE
#endif

#if defined(__OpenBSD__) && !defined(_BSD_SOURCE)
# define _BSD_SOURCE
#endif

/*
** Include standard header files as necessary
*/
#ifdef HAVE_STDINT_H
#include <stdint.h>
#endif
#ifdef HAVE_INTTYPES_H

#else
  #define sqlite3BeginBenignMalloc()
  #define sqlite3EndBenignMalloc()
#endif

#define IN_INDEX_ROWID           1
#define IN_INDEX_EPH             2
#define IN_INDEX_INDEX           3
#define IN_INDEX_INDEX_ASC       3
#define IN_INDEX_INDEX_DESC      4
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 *);
  int sqlite3JournalExists(sqlite3_file *p);

** For a constraint of the form X=expr, the expression is evaluated and its
** result is left on the stack.  For constraints of the form X IN (...)
** this routine sets up a loop that will iterate over all values of X.
*/
static int codeEqualityTerm(
  Parse *pParse,      /* The parsing context */
  WhereTerm *pTerm,   /* The term of the WHERE clause to be coded */
  WhereLevel *pLevel, /* When level of the FROM clause we are working on */
  WhereLevel *pLevel, /* The level of the FROM clause we are working on */
  int iEq,            /* Index of the equality term within this level */
  int iTarget         /* Attempt to leave results in this register */
){
  Expr *pX = pTerm->pExpr;
  Vdbe *v = pParse->pVdbe;
  int iReg;                  /* Register holding results */

  assert( iTarget>0 );
  if( pX->op==TK_EQ ){
    iReg = sqlite3ExprCodeTarget(pParse, pX->pRight, iTarget);
  }else if( pX->op==TK_ISNULL ){
    iReg = iTarget;
    sqlite3VdbeAddOp2(v, OP_Null, 0, iReg);
#ifndef SQLITE_OMIT_SUBQUERY
  }else{
    int eType;
    int iTab;
    struct InLoop *pIn;
    u8 bRev = (pLevel->plan.wsFlags & WHERE_REVERSE)!=0;

    if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 
      && pLevel->plan.u.pIdx->aSortOrder[iEq]
    ){
      testcase( iEq==0 );
      testcase( iEq==pLevel->plan.u.pIdx->nColumn-1 );
      testcase( iEq>0 && iEq+1<pLevel->plan.u.pIdx->nColumn );
      testcase( bRev );
      bRev = !bRev;
    }
    assert( pX->op==TK_IN );
    iReg = iTarget;
    eType = sqlite3FindInIndex(pParse, pX, 0);
    if( eType==IN_INDEX_INDEX_DESC ){
      testcase( bRev );
      bRev = !bRev;
    }
    iTab = pX->iTable;
    sqlite3VdbeAddOp2(v, bRev ? OP_Last : OP_Rewind, iTab, 0);
    assert( pLevel->plan.wsFlags & WHERE_IN_ABLE );
    if( pLevel->u.in.nIn==0 ){
      pLevel->addrNxt = sqlite3VdbeMakeLabel(v);
    }
    pLevel->u.in.nIn++;

    int k = pIdx->aiColumn[j];
    pTerm = findTerm(pWC, iCur, k, notReady, pLevel->plan.wsFlags, pIdx);
    if( pTerm==0 ) break;
    /* The following true for indices with redundant columns. 
    ** Ex: CREATE INDEX i1 ON t1(a,b,a); SELECT * FROM t1 WHERE a=0 AND b=0; */
    testcase( (pTerm->wtFlags & TERM_CODED)!=0 );
    testcase( pTerm->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
    r1 = codeEqualityTerm(pParse, pTerm, pLevel, regBase+j);
    r1 = codeEqualityTerm(pParse, pTerm, pLevel, j, regBase+j);
    if( r1!=regBase+j ){
      if( nReg==1 ){
        sqlite3ReleaseTempReg(pParse, regBase);
        regBase = r1;
      }else{
        sqlite3VdbeAddOp2(v, OP_SCopy, r1, regBase+j);
      }

    addrNotFound = pLevel->addrBrk;
    for(j=1; j<=nConstraint; j++){
      for(k=0; k<nConstraint; k++){
        if( aUsage[k].argvIndex==j ){
          int iTarget = iReg+j+1;
          pTerm = &pWC->a[aConstraint[k].iTermOffset];
          if( pTerm->eOperator & WO_IN ){
            codeEqualityTerm(pParse, pTerm, pLevel, iTarget);
            codeEqualityTerm(pParse, pTerm, pLevel, k, iTarget);
            addrNotFound = pLevel->addrNxt;
          }else{
            sqlite3ExprCode(pParse, pTerm->pExpr->pRight, iTarget);
          }
          break;
        }
      }

    */
    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);
    iRowidReg = codeEqualityTerm(pParse, pTerm, pLevel, 0, iReleaseReg);
    addrNxt = pLevel->addrNxt;
    sqlite3VdbeAddOp2(v, OP_MustBeInt, iRowidReg, addrNxt);
    sqlite3VdbeAddOp3(v, OP_NotExists, iCur, addrNxt, iRowidReg);
    sqlite3ExprCacheAffinityChange(pParse, iRowidReg, 1);
    sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg);
    VdbeComment((v, "pk"));
    pLevel->op = OP_Noop;

} {9 7 6 8 3 4 2 5}

ifcapable subquery {
  # If the subquery capability is not compiled in to the binary, then
  # the IN(...) operator is not available. Hence these tests cannot be 
  # run.
  do_test descidx3-4.1 {
    execsql {
    lsort [execsql {
      UPDATE t1 SET a=2 WHERE i<6;
      SELECT i FROM t1 WHERE a IN (1,2) AND b>0 AND b<'zzz';
    }
  } {8 6 2 4 3}
    }]
  } {2 3 4 6 8}
  do_test descidx3-4.2 {
    execsql {
      UPDATE t1 SET a=1;
      SELECT i FROM t1 WHERE a IN (1,2) AND b>0 AND b<'zzz';
    }
  } {2 4 3 8 6}
  do_test descidx3-4.3 {

# 2013 March 13
#
# 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. 
#

set testdir [file dirname $argv0]
source $testdir/tester.tcl
set ::testprefix tkt-4dd95f6943

do_execsql_test 1.0 {
  CREATE TABLE t1(x);
  INSERT INTO t1 VALUES (3), (4), (2), (1), (5), (6);
}

foreach {tn1 idx} {
  1 { CREATE INDEX i1 ON t1(x ASC) }
  2 { CREATE INDEX i1 ON t1(x DESC) }
} {
  do_execsql_test 1.$tn1.1 { DROP INDEX IF EXISTS i1; }
  do_execsql_test 1.$tn1.2 $idx

  do_execsql_test 1.$tn1.3 {
    SELECT x FROM t1 WHERE x IN(2, 4, 5) ORDER BY x ASC;
  } {2 4 5}

  do_execsql_test 1.$tn1.4 {
    SELECT x FROM t1 WHERE x IN(2, 4, 5) ORDER BY x DESC;
  } {5 4 2}
}


do_execsql_test 2.0 {
  CREATE TABLE t2(x, y);
  INSERT INTO t2 VALUES (5, 3), (5, 4), (5, 2), (5, 1), (5, 5), (5, 6);
  INSERT INTO t2 VALUES (1, 3), (1, 4), (1, 2), (1, 1), (1, 5), (1, 6);
  INSERT INTO t2 VALUES (3, 3), (3, 4), (3, 2), (3, 1), (3, 5), (3, 6);
  INSERT INTO t2 VALUES (2, 3), (2, 4), (2, 2), (2, 1), (2, 5), (2, 6);
  INSERT INTO t2 VALUES (4, 3), (4, 4), (4, 2), (4, 1), (4, 5), (4, 6);
  INSERT INTO t2 VALUES (6, 3), (6, 4), (6, 2), (6, 1), (6, 5), (6, 6);

  CREATE TABLE t3(a, b);
  INSERT INTO t3 VALUES (2, 2), (4, 4), (5, 5);
  CREATE UNIQUE INDEX t3i1 ON t3(a ASC);
  CREATE UNIQUE INDEX t3i2 ON t3(b DESC);
}

foreach {tn1 idx} {
  1 { CREATE INDEX i1 ON t2(x ASC,  y ASC) }
  2 { CREATE INDEX i1 ON t2(x ASC,  y DESC) }
  3 { CREATE INDEX i1 ON t2(x DESC, y ASC) }
  4 { CREATE INDEX i1 ON t2(x DESC, y DESC) }

  5 { CREATE INDEX i1 ON t2(y ASC,  x ASC) }
  6 { CREATE INDEX i1 ON t2(y ASC,  x DESC) }
  7 { CREATE INDEX i1 ON t2(y DESC, x ASC) }
  8 { CREATE INDEX i1 ON t2(y DESC, x DESC) }
} {
  do_execsql_test 2.$tn1.1 { DROP INDEX IF EXISTS i1; }
  do_execsql_test 2.$tn1.2 $idx

  foreach {tn2 inexpr} {
    3  "(2, 4, 5)"
    4  "(SELECT a FROM t3)"
    5  "(SELECT b FROM t3)"
  } {
    do_execsql_test 2.$tn1.$tn2.1 "
      SELECT x, y FROM t2 WHERE x = 1 AND y IN $inexpr ORDER BY x ASC, y ASC;
    " {1 2  1 4  1 5}

    do_execsql_test 2.$tn1.$tn2.2 "
      SELECT x, y FROM t2 WHERE x = 2 AND y IN $inexpr ORDER BY x ASC, y DESC;
    " {2 5  2 4  2 2}

    do_execsql_test 2.$tn1.$tn2.3 "
      SELECT x, y FROM t2 WHERE x = 3 AND y IN $inexpr ORDER BY x DESC, y ASC;
    " {3 2  3 4  3 5}

    do_execsql_test 2.$tn1.$tn2.4 "
      SELECT x, y FROM t2 WHERE x = 4 AND y IN $inexpr ORDER BY x DESC, y DESC;
    " {4 5  4 4  4 2}
    
    do_execsql_test 2.$tn1.$tn2.5 "
      SELECT a, x, y FROM t2, t3 WHERE a = 4 AND x = 1 AND y IN $inexpr 
      ORDER BY a, x ASC, y ASC;
    " {4 1 2  4 1 4  4 1 5}
    do_execsql_test 2.$tn1.$tn2.6 "
      SELECT a, x, y FROM t2, t3 WHERE a = 2 AND x = 1 AND y IN $inexpr 
      ORDER BY x ASC, y ASC;
    " {2 1 2  2 1 4  2 1 5}

    do_execsql_test 2.$tn1.$tn2.7 "
      SELECT a, x, y FROM t2, t3 WHERE a = 4 AND x = 1 AND y IN $inexpr 
      ORDER BY a, x ASC, y DESC;
    " {4 1 5  4 1 4  4 1 2}
    do_execsql_test 2.$tn1.8 "
      SELECT a, x, y FROM t2, t3 WHERE a = 2 AND x = 1 AND y IN $inexpr 
      ORDER BY x ASC, y DESC;
    " {2 1 5  2 1 4  2 1 2}

    do_execsql_test 2.$tn1.$tn2.9 "
      SELECT a, x, y FROM t2, t3 WHERE a = 4 AND x = 1 AND y IN $inexpr 
      ORDER BY a, x DESC, y ASC;
    " {4 1 2  4 1 4  4 1 5}
    do_execsql_test 2.$tn1.10 "
      SELECT a, x, y FROM t2, t3 WHERE a = 2 AND x = 1 AND y IN $inexpr 
      ORDER BY x DESC, y ASC;
    " {2 1 2  2 1 4  2 1 5}

    do_execsql_test 2.$tn1.$tn2.11 "
      SELECT a, x, y FROM t2, t3 WHERE a = 4 AND x = 1 AND y IN $inexpr 
      ORDER BY a, x DESC, y DESC;
    " {4 1 5  4 1 4  4 1 2}
    do_execsql_test 2.$tn1.$tn2.12 "
      SELECT a, x, y FROM t2, t3 WHERE a = 2 AND x = 1 AND y IN $inexpr 
      ORDER BY x DESC, y DESC;
    " {2 1 5  2 1 4  2 1 2}
  }
}

do_execsql_test 3.0 {
  CREATE TABLE t7(x);
  INSERT INTO t7 VALUES (1), (2), (3);
  CREATE INDEX i7 ON t7(x);

  CREATE TABLE t8(y);
  INSERT INTO t8 VALUES (1), (2), (3);
}

foreach {tn idxdir sortdir sortdata} {
  1 ASC  ASC  {1 2 3}
  2 ASC  DESC {3 2 1}
  3 DESC ASC  {1 2 3}
  4 ASC  DESC {3 2 1}
} {

  do_execsql_test 3.$tn "
    DROP INDEX IF EXISTS i8;
    CREATE UNIQUE INDEX i8 ON t8(y $idxdir);
    SELECT x FROM t7 WHERE x IN (SELECT y FROM t8) ORDER BY x $sortdir;
  " $sortdata
}

finish_test