** 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.146 2005/07/19 17:38:23 drh Exp $
*/
#include "sqliteInt.h"

/*
** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
*/
#define BMS  (sizeof(Bitmask)*8-1)
................................................................................
static void buildIndexProbe(Vdbe *v, int nColumn, int brk, Index *pIdx){
  sqlite3VdbeAddOp(v, OP_NotNull, -nColumn, sqlite3VdbeCurrentAddr(v)+3);
  sqlite3VdbeAddOp(v, OP_Pop, nColumn, 0);
  sqlite3VdbeAddOp(v, OP_Goto, 0, brk);
  sqlite3VdbeAddOp(v, OP_MakeRecord, nColumn, 0);
  sqlite3IndexAffinityStr(v, pIdx);
}






























/*
** Generate code for an equality term of the WHERE clause.  An equality
** term can be either X=expr  or X IN (...).   pTerm is the X.  
*/
static void codeEqualityTerm(
  Parse *pParse,      /* The parsing context */
................................................................................
      int nColumn = (pLevel->score+16)/32;
      brk = pLevel->brk = sqlite3VdbeMakeLabel(v);

      /* For each column of the index, find the term of the WHERE clause that
      ** constraints that column.  If the WHERE clause term is X=expr, then
      ** generate code to evaluate expr and leave the result on the stack */
      for(j=0; j<nColumn; j++){
        for(pTerm=wc.a, k=0; k<wc.nTerm; k++, pTerm++){
          Expr *pX = pTerm->pExpr;
          assert( pX );
          if( pTerm->leftCursor==iCur
             && (pTerm->prereqRight & loopMask)==0
             && pTerm->leftColumn==pIdx->aiColumn[j]
             && (pX->op==TK_EQ || pX->op==TK_IN)
          ){
            char idxaff = pIdx->pTable->aCol[pTerm->leftColumn].affinity;
            assert( (pTerm->flags & TERM_CODED)==0 );
            if( sqlite3IndexAffinityOk(pX, idxaff) ){
              codeEqualityTerm(pParse, pTerm, brk, pLevel);
              break;
            }
          }
        }
      }
      pLevel->iMem = pParse->nMem++;
      cont = pLevel->cont = sqlite3VdbeMakeLabel(v);
      buildIndexProbe(v, nColumn, brk, pIdx);
      sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 0);

      /* Generate code (1) to move to the first matching element of the table.
................................................................................
      int start;
      int leFlag=0, geFlag=0;
      int testOp;

      /* Evaluate the equality constraints
      */
      for(j=0; j<nEqColumn; j++){
        int iIdxCol = pIdx->aiColumn[j];
        for(pTerm=wc.a, k=0; k<wc.nTerm; k++, pTerm++){
          Expr *pX;
          if( pTerm->leftCursor==iCur
             && pTerm->leftColumn==iIdxCol
             && (pX = pTerm->pExpr)->op==TK_EQ
             && (pTerm->prereqRight & loopMask)==0
          ){
            assert( (pTerm->flags & TERM_CODED)==0 );
            sqlite3ExprCode(pParse, pX->pRight);
            disableTerm(pLevel, pTerm);
            break;
          }
        }
        assert( k<wc.nTerm );
      }

      /* Duplicate the equality term values because they will all be
      ** used twice: once to make the termination key and once to make the
      ** start key.
      */
      for(j=0; j<nEqColumn; j++){
................................................................................
      ** will end the search.  There is no termination key if there
      ** are no equality terms and no "X<..." term.
      **
      ** 2002-Dec-04: On a reverse-order scan, the so-called "termination"
      ** key computed here really ends up being the start key.
      */
      if( (score & 4)!=0 ){
        for(pTerm=wc.a, k=0; k<wc.nTerm; k++, pTerm++){
          Expr *pX = pTerm->pExpr;

          assert( pX );
          if( pTerm->leftCursor==iCur
             && (pX->op==TK_LT || pX->op==TK_LE)
             && (pTerm->prereqRight & loopMask)==0
             && pTerm->leftColumn==pIdx->aiColumn[j]
          ){
            assert( (pTerm->flags & TERM_CODED)==0 );
            sqlite3ExprCode(pParse, pX->pRight);
            leFlag = pX->op==TK_LE;
            disableTerm(pLevel, pTerm);
            break;
          }
        }
        assert( k<wc.nTerm );
        testOp = OP_IdxGE;
      }else{
        testOp = nEqColumn>0 ? OP_IdxGE : OP_Noop;
        leFlag = 1;
      }
      if( testOp!=OP_Noop ){
        int nCol = nEqColumn + ((score & 4)!=0);
................................................................................
      ** that case, generate a "Rewind" instruction in place of the
      ** start key search.
      **
      ** 2002-Dec-04: In the case of a reverse-order search, the so-called
      ** "start" key really ends up being used as the termination key.
      */
      if( (score & 8)!=0 ){
        for(pTerm=wc.a, k=0; k<wc.nTerm; k++, pTerm++){
          Expr *pX = pTerm->pExpr;

          assert( pX );
          if( pTerm->leftCursor==iCur
             && (pX->op==TK_GT || pX->op==TK_GE)
             && (pTerm->prereqRight & loopMask)==0
             && pTerm->leftColumn==pIdx->aiColumn[j]
          ){
            assert( (pTerm->flags & TERM_CODED)==0 );
            sqlite3ExprCode(pParse, pX->pRight);
            geFlag = pX->op==TK_GE;
            disableTerm(pLevel, pTerm);
            break;
          }
        }
      }else{
        geFlag = 1;
      }
      if( nEqColumn>0 || (score&8)!=0 ){
        int nCol = nEqColumn + ((score&8)!=0);
        buildIndexProbe(v, nCol, brk, pIdx);
        if( pLevel->bRev ){

** 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.147 2005/07/19 22:22:13 drh Exp $
*/
#include "sqliteInt.h"

/*
** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
*/
#define BMS  (sizeof(Bitmask)*8-1)
................................................................................
static void buildIndexProbe(Vdbe *v, int nColumn, int brk, Index *pIdx){
  sqlite3VdbeAddOp(v, OP_NotNull, -nColumn, sqlite3VdbeCurrentAddr(v)+3);
  sqlite3VdbeAddOp(v, OP_Pop, nColumn, 0);
  sqlite3VdbeAddOp(v, OP_Goto, 0, brk);
  sqlite3VdbeAddOp(v, OP_MakeRecord, nColumn, 0);
  sqlite3IndexAffinityStr(v, pIdx);
}

/*
** 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 either
** op1 or op2.  Return a pointer to the term.
*/
static WhereTerm *findTerm(
  WhereClause *pWC,     /* The WHERE clause to be searched */
  int iCur,             /* Cursor number of LHS */
  int iColumn,          /* Column number of LHS */
  Bitmask loopMask,     /* RHS must not overlap with this mask */
  u8 op1, u8 op2        /* Expression must use either of these opcodes */
){
  WhereTerm *pTerm;
  int k;
  for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){
    u8 op = pTerm->pExpr->op;
    if( pTerm->leftCursor==iCur
       && (pTerm->prereqRight & loopMask)==0
       && pTerm->leftColumn==iColumn
       && (op==op1 || op==op2)
    ){
      break;
    }
  }
  assert( k>0 );  /* The search is always successful */
  return pTerm;
}


/*
** Generate code for an equality term of the WHERE clause.  An equality
** term can be either X=expr  or X IN (...).   pTerm is the X.  
*/
static void codeEqualityTerm(
  Parse *pParse,      /* The parsing context */
................................................................................
      int nColumn = (pLevel->score+16)/32;
      brk = pLevel->brk = sqlite3VdbeMakeLabel(v);

      /* For each column of the index, find the term of the WHERE clause that
      ** constraints that column.  If the WHERE clause term is X=expr, then
      ** generate code to evaluate expr and leave the result on the stack */
      for(j=0; j<nColumn; j++){
        pTerm = findTerm(&wc, iCur, pIdx->aiColumn[j], loopMask, TK_EQ, TK_IN);

        assert( pTerm!=0 );






        assert( (pTerm->flags & TERM_CODED)==0 );

        codeEqualityTerm(pParse, pTerm, brk, pLevel);




      }
      pLevel->iMem = pParse->nMem++;
      cont = pLevel->cont = sqlite3VdbeMakeLabel(v);
      buildIndexProbe(v, nColumn, brk, pIdx);
      sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 0);

      /* Generate code (1) to move to the first matching element of the table.
................................................................................
      int start;
      int leFlag=0, geFlag=0;
      int testOp;

      /* Evaluate the equality constraints
      */
      for(j=0; j<nEqColumn; j++){
        pTerm = findTerm(&wc, iCur, pIdx->aiColumn[j], loopMask, TK_EQ, TK_EQ);
        assert( pTerm!=0 );






        assert( (pTerm->flags & TERM_CODED)==0 );
        sqlite3ExprCode(pParse, pTerm->pExpr->pRight);
        disableTerm(pLevel, pTerm);




      }

      /* Duplicate the equality term values because they will all be
      ** used twice: once to make the termination key and once to make the
      ** start key.
      */
      for(j=0; j<nEqColumn; j++){
................................................................................
      ** will end the search.  There is no termination key if there
      ** are no equality terms and no "X<..." term.
      **
      ** 2002-Dec-04: On a reverse-order scan, the so-called "termination"
      ** key computed here really ends up being the start key.
      */
      if( (score & 4)!=0 ){

        Expr *pX;
        pTerm = findTerm(&wc, iCur, pIdx->aiColumn[j], loopMask, TK_LT, TK_LE);
        assert( pTerm!=0 );
        pX = pTerm->pExpr;




        assert( (pTerm->flags & TERM_CODED)==0 );
        sqlite3ExprCode(pParse, pX->pRight);
        leFlag = pX->op==TK_LE;
        disableTerm(pLevel, pTerm);




        testOp = OP_IdxGE;
      }else{
        testOp = nEqColumn>0 ? OP_IdxGE : OP_Noop;
        leFlag = 1;
      }
      if( testOp!=OP_Noop ){
        int nCol = nEqColumn + ((score & 4)!=0);
................................................................................
      ** that case, generate a "Rewind" instruction in place of the
      ** start key search.
      **
      ** 2002-Dec-04: In the case of a reverse-order search, the so-called
      ** "start" key really ends up being used as the termination key.
      */
      if( (score & 8)!=0 ){

        Expr *pX;
        pTerm = findTerm(&wc, iCur, pIdx->aiColumn[j], loopMask, TK_GT, TK_GE);
        assert( pTerm!=0 );
        pX = pTerm->pExpr;




        assert( (pTerm->flags & TERM_CODED)==0 );
        sqlite3ExprCode(pParse, pX->pRight);
        geFlag = pX->op==TK_GE;
        disableTerm(pLevel, pTerm);



      }else{
        geFlag = 1;
      }
      if( nEqColumn>0 || (score&8)!=0 ){
        int nCol = nEqColumn + ((score&8)!=0);
        buildIndexProbe(v, nCol, brk, pIdx);
        if( pLevel->bRev ){