SQLite

** 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 ){