SQLite

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.
**
** $Id: where.c,v 1.110 2004/07/19 19:14:01 drh Exp $
*/
#include "sqliteInt.h"

/*
** The query generator uses an array of instances of this structure to
** help it analyze the subexpressions of the WHERE clause.  Each WHERE
** clause subexpression is separated from the others by an AND operator.

    case TK_EQ:
    case TK_IN:
      return 1;
    default:
      return 0;
  }
}























/*
** The input to this routine is an ExprInfo structure with only the
** "p" field filled in.  The job of this routine is to analyze the
** subexpression and populate all the other fields of the ExprInfo
** structure.
*/
static void exprAnalyze(ExprMaskSet *pMaskSet, ExprInfo *pInfo){
  Expr *pExpr = pInfo->p;
  pInfo->prereqLeft = exprTableUsage(pMaskSet, pExpr->pLeft);
  pInfo->prereqRight = exprTableUsage(pMaskSet, pExpr->pRight);
  pInfo->prereqAll = exprTableUsage(pMaskSet, pExpr);
  pInfo->indexable = 0;
  pInfo->idxLeft = -1;
  pInfo->idxRight = -1;
  if( allowedOp(pExpr->op) && (pInfo->prereqRight & pInfo->prereqLeft)==0 ){
    if( pExpr->pRight && pExpr->pRight->op==TK_COLUMN ){
      pInfo->idxRight = pExpr->pRight->iTable;
      pInfo->indexable = 1;
    }
    if( pExpr->pLeft->op==TK_COLUMN ){
      pInfo->idxLeft = pExpr->pLeft->iTable;
      pInfo->indexable = 1;
    }
  }


























}

/*
** pOrderBy is an ORDER BY clause from a SELECT statement.  pTab is the
** left-most table in the FROM clause of that same SELECT statement and
** the table has a cursor number of "base".
**

  int i;                     /* Loop counter */
  WhereInfo *pWInfo;         /* Will become the return value of this function */
  Vdbe *v = pParse->pVdbe;   /* The virtual database engine */
  int brk, cont = 0;         /* Addresses used during code generation */
  int nExpr;           /* Number of subexpressions in the WHERE clause */
  int loopMask;        /* One bit set for each outer loop */
  int haveKey = 0;     /* True if KEY is on the stack */

  ExprMaskSet maskSet; /* The expression mask set */
  int iDirectEq[32];   /* Term of the form ROWID==X for the N-th table */
  int iDirectLt[32];   /* Term of the form ROWID<X or ROWID<=X */
  int iDirectGt[32];   /* Term of the form ROWID>X or ROWID>=X */
  ExprInfo aExpr[101]; /* The WHERE clause is divided into these expressions */

  /* pushKey is only allowed if there is a single table (as in an INSERT or
  ** UPDATE statement)
  */
  assert( pushKey==0 || pTabList->nSrc==1 );

  /* Split the WHERE clause into separate subexpressions where each

  }
  
  /* Allocate and initialize the WhereInfo structure that will become the
  ** return value.
  */
  pWInfo = sqliteMalloc( sizeof(WhereInfo) + pTabList->nSrc*sizeof(WhereLevel));
  if( sqlite3_malloc_failed ){
    sqliteFree(pWInfo);
    return 0;
  }
  pWInfo->pParse = pParse;
  pWInfo->pTabList = pTabList;
  pWInfo->peakNTab = pWInfo->savedNTab = pParse->nTab;
  pWInfo->iBreak = sqlite3VdbeMakeLabel(v);

  /* Special case: a WHERE clause that is constant.  Evaluate the
  ** expression and either jump over all of the code or fall thru.
  */
  if( pWhere && (pTabList->nSrc==0 || sqlite3ExprIsConstant(pWhere)) ){
    sqlite3ExprIfFalse(pParse, pWhere, pWInfo->iBreak, 1);
    pWhere = 0;
  }

  /* Analyze all of the subexpressions.
  */
  for(i=0; i<nExpr; i++){

    exprAnalyze(&maskSet, &aExpr[i]);

    /* If we are executing a trigger body, remove all references to
    ** new.* and old.* tables from the prerequisite masks.
    */
    if( pParse->trigStack ){
      int x;
      if( (x = pParse->trigStack->newIdx) >= 0 ){
        int mask = ~getMask(&maskSet, x);
        aExpr[i].prereqRight &= mask;
        aExpr[i].prereqLeft &= mask;
        aExpr[i].prereqAll &= mask;
      }
      if( (x = pParse->trigStack->oldIdx) >= 0 ){
        int mask = ~getMask(&maskSet, x);
        aExpr[i].prereqRight &= mask;
        aExpr[i].prereqLeft &= mask;
        aExpr[i].prereqAll &= mask;
      }
    }
  }

  /* Figure out what index to use (if any) for each nested loop.
  ** Make pWInfo->a[i].pIdx point to the index to use for the i-th nested
  ** loop where i==0 is the outer loop and i==pTabList->nSrc-1 is the inner

    **
    ** (Added:) Treat ROWID IN expr like ROWID=expr.
    */
    pWInfo->a[i].iCur = -1;
    iDirectEq[i] = -1;
    iDirectLt[i] = -1;
    iDirectGt[i] = -1;
    for(j=0; j<nExpr; j++){

      if( aExpr[j].idxLeft==iCur && aExpr[j].p->pLeft->iColumn<0
            && (aExpr[j].prereqRight & loopMask)==aExpr[j].prereqRight ){
        switch( aExpr[j].p->op ){
          case TK_IN:
          case TK_EQ: iDirectEq[i] = j; break;
          case TK_LE:
          case TK_LT: iDirectLt[i] = j; break;
          case TK_GE:
          case TK_GT: iDirectGt[i] = j;  break;
        }
      }
      if( aExpr[j].idxRight==iCur && aExpr[j].p->pRight->iColumn<0
            && (aExpr[j].prereqLeft & loopMask)==aExpr[j].prereqLeft ){
        switch( aExpr[j].p->op ){
          case TK_EQ: iDirectEq[i] = j;  break;
          case TK_LE:
          case TK_LT: iDirectGt[i] = j;  break;
          case TK_GE:
          case TK_GT: iDirectLt[i] = j;  break;
        }
      }
    }
    if( iDirectEq[i]>=0 ){
      loopMask |= mask;
      pWInfo->a[i].pIdx = 0;
      continue;
    }

      int eqMask = 0;  /* Index columns covered by an x=... term */
      int ltMask = 0;  /* Index columns covered by an x<... term */
      int gtMask = 0;  /* Index columns covered by an x>... term */
      int inMask = 0;  /* Index columns covered by an x IN .. term */
      int nEq, m, score;

      if( pIdx->nColumn>32 ) continue;  /* Ignore indices too many columns */
      for(j=0; j<nExpr; j++){
        CollSeq *pColl = sqlite3ExprCollSeq(pParse, aExpr[j].p->pLeft);

        if( !pColl && aExpr[j].p->pRight ){
          pColl = sqlite3ExprCollSeq(pParse, aExpr[j].p->pRight);
        }
        if( !pColl ){
          pColl = pParse->db->pDfltColl;
        }
        if( aExpr[j].idxLeft==iCur 
             && (aExpr[j].prereqRight & loopMask)==aExpr[j].prereqRight ){
          int iColumn = aExpr[j].p->pLeft->iColumn;
          int k;
          char idxaff = pIdx->pTable->aCol[iColumn].affinity; 
          for(k=0; k<pIdx->nColumn; k++){
            /* If the collating sequences or affinities don't match, 
            ** ignore this index.  */
            if( pColl!=pIdx->keyInfo.aColl[k] ) continue;
            if( !sqlite3IndexAffinityOk(aExpr[j].p, idxaff) ) continue;
            if( pIdx->aiColumn[k]==iColumn ){
              switch( aExpr[j].p->op ){
                case TK_IN: {
                  if( k==0 ) inMask |= 1;
                  break;
                }
                case TK_EQ: {
                  eqMask |= 1<<k;
                  break;
                }
                case TK_LE:
                case TK_LT: {
                  ltMask |= 1<<k;
                  break;
                }
                case TK_GE:
                case TK_GT: {
                  gtMask |= 1<<k;
                  break;
                }
                default: {
                  /* CANT_HAPPEN */
                  assert( 0 );
                  break;
                }
              }
              break;
            }
          }
        }
        if( aExpr[j].idxRight==iCur 
             && (aExpr[j].prereqLeft & loopMask)==aExpr[j].prereqLeft ){
          int iColumn = aExpr[j].p->pRight->iColumn;
          int k;
          char idxaff = pIdx->pTable->aCol[iColumn].affinity; 
          for(k=0; k<pIdx->nColumn; k++){
            /* If the collating sequences or affinities don't match, 
            ** ignore this index.  */
            if( pColl!=pIdx->keyInfo.aColl[k] ) continue;
            if( !sqlite3IndexAffinityOk(aExpr[j].p, idxaff) ) continue;
            if( pIdx->aiColumn[k]==iColumn ){
              switch( aExpr[j].p->op ){
                case TK_EQ: {
                  eqMask |= 1<<k;
                  break;
                }
                case TK_LE:
                case TK_LT: {
                  gtMask |= 1<<k;
                  break;
                }
                case TK_GE:
                case TK_GT: {
                  ltMask |= 1<<k;
                  break;
                }
                default: {
                  /* CANT_HAPPEN */
                  assert( 0 );
                  break;
                }
              }
              break;

    pLevel->inOp = OP_Noop;
    if( i<ARRAYSIZE(iDirectEq) && iDirectEq[i]>=0 ){
      /* Case 1:  We can directly reference a single row using an
      **          equality comparison against the ROWID field.  Or
      **          we reference multiple rows using a "rowid IN (...)"
      **          construct.
      */

      k = iDirectEq[i];
      assert( k<nExpr );
      assert( aExpr[k].p!=0 );

      assert( aExpr[k].idxLeft==iCur || aExpr[k].idxRight==iCur );
      brk = pLevel->brk = sqlite3VdbeMakeLabel(v);

      if( aExpr[k].idxLeft==iCur ){
        Expr *pX = aExpr[k].p;
        if( pX->op!=TK_IN ){
          sqlite3ExprCode(pParse, aExpr[k].p->pRight);
        }else{
          sqlite3VdbeAddOp(v, OP_Rewind, pX->iTable, brk);
          sqlite3VdbeAddOp(v, OP_KeyAsData, pX->iTable, 1);
          pLevel->inP2 = sqlite3VdbeAddOp(v, OP_IdxColumn, pX->iTable, 0);
          pLevel->inOp = OP_Next;
          pLevel->inP1 = pX->iTable;
        }
      }else{
        sqlite3ExprCode(pParse, aExpr[k].p->pLeft);
      }
      disableTerm(pLevel, &aExpr[k].p);
      cont = pLevel->cont = sqlite3VdbeMakeLabel(v);
      sqlite3VdbeAddOp(v, OP_MustBeInt, 1, brk);
      haveKey = 0;
      sqlite3VdbeAddOp(v, OP_NotExists, iCur, brk);
      pLevel->op = OP_Noop;
    }else if( pIdx!=0 && pLevel->score>0 && pLevel->score%4==0 ){
      /* Case 2:  There is an index and all terms of the WHERE clause that
      **          refer to the index use the "==" or "IN" operators.
      */
      int start;
      int nColumn = (pLevel->score+4)/8;
      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
      ** evaluation expr and leave the result on the stack */
      for(j=0; j<nColumn; j++){
        for(k=0; k<nExpr; k++){
          Expr *pX = aExpr[k].p;
          if( pX==0 ) continue;
          if( aExpr[k].idxLeft==iCur
             && (aExpr[k].prereqRight & loopMask)==aExpr[k].prereqRight 
             && pX->pLeft->iColumn==pIdx->aiColumn[j]
          ){
            char idxaff = pIdx->pTable->aCol[pX->pLeft->iColumn].affinity;
            if( sqlite3IndexAffinityOk(aExpr[k].p, idxaff) ){
              if( pX->op==TK_EQ ){
                sqlite3ExprCode(pParse, pX->pRight);
                disableTerm(pLevel, &aExpr[k].p);
                break;
              }

              if( pX->op==TK_IN && nColumn==1 ){
                sqlite3VdbeAddOp(v, OP_Rewind, pX->iTable, brk);
                sqlite3VdbeAddOp(v, OP_KeyAsData, pX->iTable, 1);
                pLevel->inP2 = sqlite3VdbeAddOp(v, OP_IdxColumn, pX->iTable, 0);
                pLevel->inOp = OP_Next;
                pLevel->inP1 = pX->iTable;
                disableTerm(pLevel, &aExpr[k].p);
                break;
              }
            }
          }
          if( aExpr[k].idxRight==iCur
             && aExpr[k].p->op==TK_EQ
             && (aExpr[k].prereqLeft & loopMask)==aExpr[k].prereqLeft
             && aExpr[k].p->pRight->iColumn==pIdx->aiColumn[j]
          ){
            char idxaff = pIdx->pTable->aCol[pX->pRight->iColumn].affinity;
            if( sqlite3IndexAffinityOk(aExpr[k].p, idxaff) ){
              sqlite3ExprCode(pParse, aExpr[k].p->pLeft);
              disableTerm(pLevel, &aExpr[k].p);
              break;
            }
          }
        }
      }
      pLevel->iMem = pParse->nMem++;
      cont = pLevel->cont = sqlite3VdbeMakeLabel(v);

      int start;

      brk = pLevel->brk = sqlite3VdbeMakeLabel(v);
      cont = pLevel->cont = sqlite3VdbeMakeLabel(v);
      if( iDirectGt[i]>=0 ){
        k = iDirectGt[i];
        assert( k<nExpr );
        assert( aExpr[k].p!=0 );
        assert( aExpr[k].idxLeft==iCur || aExpr[k].idxRight==iCur );
        if( aExpr[k].idxLeft==iCur ){
          sqlite3ExprCode(pParse, aExpr[k].p->pRight);
        }else{
          sqlite3ExprCode(pParse, aExpr[k].p->pLeft);
        }
        sqlite3VdbeAddOp(v, OP_ForceInt,
          aExpr[k].p->op==TK_LT || aExpr[k].p->op==TK_GT, brk);
        sqlite3VdbeAddOp(v, OP_MoveGe, iCur, brk);
        disableTerm(pLevel, &aExpr[k].p);
      }else{
        sqlite3VdbeAddOp(v, OP_Rewind, iCur, brk);
      }
      if( iDirectLt[i]>=0 ){
        k = iDirectLt[i];
        assert( k<nExpr );
        assert( aExpr[k].p!=0 );
        assert( aExpr[k].idxLeft==iCur || aExpr[k].idxRight==iCur );
        if( aExpr[k].idxLeft==iCur ){
          sqlite3ExprCode(pParse, aExpr[k].p->pRight);
        }else{
          sqlite3ExprCode(pParse, aExpr[k].p->pLeft);
        }
        /* sqlite3VdbeAddOp(v, OP_MustBeInt, 0, sqlite3VdbeCurrentAddr(v)+1); */
        pLevel->iMem = pParse->nMem++;
        sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 1);
        if( aExpr[k].p->op==TK_LT || aExpr[k].p->op==TK_GT ){
          testOp = OP_Ge;
        }else{
          testOp = OP_Gt;
        }
        disableTerm(pLevel, &aExpr[k].p);
      }
      start = sqlite3VdbeCurrentAddr(v);
      pLevel->op = OP_Next;
      pLevel->p1 = iCur;
      pLevel->p2 = start;
      if( testOp!=OP_Noop ){
        sqlite3VdbeAddOp(v, OP_Recno, iCur, 0);

      int start;
      int leFlag=0, geFlag=0;
      int testOp;

      /* Evaluate the equality constraints
      */
      for(j=0; j<nEqColumn; j++){
        for(k=0; k<nExpr; k++){
          if( aExpr[k].p==0 ) continue;
          if( aExpr[k].idxLeft==iCur
             && aExpr[k].p->op==TK_EQ
             && (aExpr[k].prereqRight & loopMask)==aExpr[k].prereqRight 
             && aExpr[k].p->pLeft->iColumn==pIdx->aiColumn[j]
          ){
            sqlite3ExprCode(pParse, aExpr[k].p->pRight);
            disableTerm(pLevel, &aExpr[k].p);
            break;
          }
          if( aExpr[k].idxRight==iCur
             && aExpr[k].p->op==TK_EQ
             && (aExpr[k].prereqLeft & loopMask)==aExpr[k].prereqLeft
             && aExpr[k].p->pRight->iColumn==pIdx->aiColumn[j]
          ){
            sqlite3ExprCode(pParse, aExpr[k].p->pLeft);
            disableTerm(pLevel, &aExpr[k].p);
            break;
          }
        }
      }

      /* Duplicate the equality term values because they will all be
      ** used twice: once to make the termination key and once to make the

      ** 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 & 1)!=0 ){
        for(k=0; k<nExpr; k++){
          Expr *pExpr = aExpr[k].p;
          if( pExpr==0 ) continue;
          if( aExpr[k].idxLeft==iCur
             && (pExpr->op==TK_LT || pExpr->op==TK_LE)
             && (aExpr[k].prereqRight & loopMask)==aExpr[k].prereqRight 
             && pExpr->pLeft->iColumn==pIdx->aiColumn[j]
          ){
            sqlite3ExprCode(pParse, pExpr->pRight);
            leFlag = pExpr->op==TK_LE;
            disableTerm(pLevel, &aExpr[k].p);
            break;
          }
          if( aExpr[k].idxRight==iCur
             && (pExpr->op==TK_GT || pExpr->op==TK_GE)
             && (aExpr[k].prereqLeft & loopMask)==aExpr[k].prereqLeft
             && pExpr->pRight->iColumn==pIdx->aiColumn[j]
          ){
            sqlite3ExprCode(pParse, pExpr->pLeft);
            leFlag = pExpr->op==TK_GE;
            disableTerm(pLevel, &aExpr[k].p);
            break;
          }
        }
        testOp = OP_IdxGE;
      }else{
        testOp = nEqColumn>0 ? OP_IdxGE : OP_Noop;
        leFlag = 1;

      ** 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 & 2)!=0 ){
        for(k=0; k<nExpr; k++){
          Expr *pExpr = aExpr[k].p;
          if( pExpr==0 ) continue;
          if( aExpr[k].idxLeft==iCur
             && (pExpr->op==TK_GT || pExpr->op==TK_GE)
             && (aExpr[k].prereqRight & loopMask)==aExpr[k].prereqRight 
             && pExpr->pLeft->iColumn==pIdx->aiColumn[j]
          ){
            sqlite3ExprCode(pParse, pExpr->pRight);
            geFlag = pExpr->op==TK_GE;
            disableTerm(pLevel, &aExpr[k].p);
            break;
          }
          if( aExpr[k].idxRight==iCur
             && (pExpr->op==TK_LT || pExpr->op==TK_LE)
             && (aExpr[k].prereqLeft & loopMask)==aExpr[k].prereqLeft
             && pExpr->pRight->iColumn==pIdx->aiColumn[j]
          ){
            sqlite3ExprCode(pParse, pExpr->pLeft);
            geFlag = pExpr->op==TK_LE;
            disableTerm(pLevel, &aExpr[k].p);
            break;
          }
        }
      }else{
        geFlag = 1;
      }
      if( nEqColumn>0 || (score&2)!=0 ){

      pLevel->p2 = start;
    }
    loopMask |= getMask(&maskSet, iCur);

    /* Insert code to test every subexpression that can be completely
    ** computed using the current set of tables.
    */
    for(j=0; j<nExpr; j++){
      if( aExpr[j].p==0 ) continue;
      if( (aExpr[j].prereqAll & loopMask)!=aExpr[j].prereqAll ) continue;
      if( pLevel->iLeftJoin && !ExprHasProperty(aExpr[j].p,EP_FromJoin) ){
        continue;
      }
      if( haveKey ){
        haveKey = 0;
        sqlite3VdbeAddOp(v, OP_MoveGe, iCur, 0);
      }
      sqlite3ExprIfFalse(pParse, aExpr[j].p, cont, 1);
      aExpr[j].p = 0;
    }
    brk = cont;

    /* For a LEFT OUTER JOIN, generate code that will record the fact that
    ** at least one row of the right table has matched the left table.  
    */
    if( pLevel->iLeftJoin ){
      pLevel->top = sqlite3VdbeCurrentAddr(v);
      sqlite3VdbeAddOp(v, OP_Integer, 1, 0);
      sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iLeftJoin, 1);
      for(j=0; j<nExpr; j++){
        if( aExpr[j].p==0 ) continue;
        if( (aExpr[j].prereqAll & loopMask)!=aExpr[j].prereqAll ) continue;
        if( haveKey ){
          /* Cannot happen.  "haveKey" can only be true if pushKey is true
          ** an pushKey can only be true for DELETE and UPDATE and there are
          ** no outer joins with DELETE and UPDATE.
          */
          haveKey = 0;
          sqlite3VdbeAddOp(v, OP_MoveGe, iCur, 0);
        }
        sqlite3ExprIfFalse(pParse, aExpr[j].p, cont, 1);
        aExpr[j].p = 0;
      }
    }
  }
  pWInfo->iContinue = cont;
  if( pushKey && !haveKey ){
    sqlite3VdbeAddOp(v, OP_Recno, pTabList->a[0].iCursor, 0);
  }