SQLite

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains routines used for analyzing expressions and
** for generating VDBE code that evaluates expressions in SQLite.
**
** $Id: expr.c,v 1.164 2004/09/24 12:24:07 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

char const *sqlite3AffinityString(char affinity){
  switch( affinity ){
    case SQLITE_AFF_INTEGER: return "i";
    case SQLITE_AFF_NUMERIC: return "n";
    case SQLITE_AFF_TEXT:    return "t";
    case SQLITE_AFF_NONE:    return "o";
    default:
      assert(0);
  }
  return 0;
}


/*
** Return the 'affinity' of the expression pExpr if any.
**
** If pExpr is a column, a reference to a column via an 'AS' alias,
** or a sub-select with a column as the return value, then the 
** affinity of that column is returned. Otherwise, 0x00 is returned,

  Expr *pRight,     /* The right operand */
  int opcode,       /* The comparison opcode */
  int dest,         /* Jump here if true.  */
  int jumpIfNull    /* If true, jump if either operand is NULL */
){
  int p1 = binaryCompareP1(pLeft, pRight, jumpIfNull);
  CollSeq *p3 = binaryCompareCollSeq(pParse, pLeft, pRight);
  return sqlite3VdbeOp3(pParse->pVdbe, opcode, p1, dest, (void *)p3, P3_COLLSEQ);
}

/*
** Construct a new expression node and return a pointer to it.  Memory
** for this node is obtained from sqliteMalloc().  The calling function
** is responsible for making sure the node eventually gets freed.
*/

        **
	** For each expression, build an index key from the evaluation and
        ** store it in the temporary table. If <expr> is a column, then use
        ** that columns affinity when building index keys. If <expr> is not
        ** a column, use numeric affinity.
        */
        int i;
        char const *affStr;
        if( !affinity ){
          affinity = SQLITE_AFF_NUMERIC;
        }
        affStr = sqlite3AffinityString(affinity);
        keyInfo.aColl[0] = pExpr->pLeft->pColl;

        /* Loop through each expression in <exprlist>. */
        for(i=0; i<pExpr->pList->nExpr; i++){
          Expr *pE2 = pExpr->pList->a[i].pExpr;

          /* Check that the expression is constant and valid. */
          if( !sqlite3ExprIsConstant(pE2) ){
            sqlite3ErrorMsg(pParse,
              "right-hand side of IN operator must be constant");
            return 1;
          }
          if( sqlite3ExprCheck(pParse, pE2, 0, 0) ){
            return 1;
          }

          /* Evaluate the expression and insert it into the temp table */
          sqlite3ExprCode(pParse, pE2);
          sqlite3VdbeOp3(v, OP_MakeRecord, 1, 0, affStr, P3_STATIC);
          sqlite3VdbeAddOp(v, OP_String8, 0, 0);
          sqlite3VdbeAddOp(v, OP_PutStrKey, pExpr->iTable, 0);
        }
      }
      sqlite3VdbeChangeP3(v, addr, (void *)&keyInfo, P3_KEYINFO);

      break;

    case TK_SELECT: {
      sqlite3VdbeAddOp(v, OP_MemLoad, pExpr->iColumn, 0);
      VdbeComment((v, "# load subquery result"));
      break;
    }
    case TK_IN: {
      int addr;
      char const *affStr;

      /* Figure out the affinity to use to create a key from the results
      ** of the expression. affinityStr stores a static string suitable for
      ** P3 of OP_MakeRecord.
      */
      affStr = sqlite3AffinityString(comparisonAffinity(pExpr));

      sqlite3VdbeAddOp(v, OP_Integer, 1, 0);

      /* Code the <expr> from "<expr> IN (...)". The temporary table
      ** pExpr->iTable contains the values that make up the (...) set.
      */
      sqlite3ExprCode(pParse, pExpr->pLeft);
      addr = sqlite3VdbeCurrentAddr(v);
      sqlite3VdbeAddOp(v, OP_NotNull, -1, addr+4);            /* addr + 0 */
      sqlite3VdbeAddOp(v, OP_Pop, 2, 0);
      sqlite3VdbeAddOp(v, OP_String8, 0, 0);
      sqlite3VdbeAddOp(v, OP_Goto, 0, addr+7);
      sqlite3VdbeOp3(v, OP_MakeRecord, 1, 0, affStr, P3_STATIC); /* addr + 4 */
      sqlite3VdbeAddOp(v, OP_Found, pExpr->iTable, addr+7);
      sqlite3VdbeAddOp(v, OP_AddImm, -1, 0);                  /* addr + 6 */

      break;
    }
    case TK_BETWEEN: {
      Expr *pLeft = pExpr->pLeft;

**
*************************************************************************
** This file contains SQLite's grammar for SQL.  Process this file
** using the lemon parser generator to generate C code that runs
** the parser.  Lemon will also generate a header file containing
** numeric codes for all of the tokens.
**
** @(#) $Id: parse.y,v 1.136 2004/09/07 16:19:54 drh Exp $
*/
%token_prefix TK_
%token_type {Token}
%default_type {Token}
%extra_argument {Parse *pParse}
%syntax_error {
  if( pParse->zErrMsg==0 ){

// of the operator tokens in the grammer.  Keeping the operators together
// causes them to be assigned integer values that are close together,
// which keeps parser tables smaller.
//
%left OR.
%left AND.
%right NOT.
%left EQ NE ISNULL NOTNULL IS LIKE GLOB BETWEEN IN.
%left GT GE LT LE.
%left BITAND BITOR LSHIFT RSHIFT.
%left PLUS MINUS.
%left STAR SLASH REM.
%left CONCAT.
%right UMINUS UPLUS BITNOT.

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle SELECT statements in SQLite.
**
** $Id: select.c,v 1.209 2004/09/19 02:15:26 drh Exp $
*/
#include "sqliteInt.h"


/*
** Allocate a new Select structure and return a pointer to that
** structure.

      addr2 = sqlite3VdbeAddOp(v, OP_Goto, 0, 0);
      if( pOrderBy ){
        pushOntoSorter(pParse, v, pOrderBy);
      }else{
        char const *affStr;
        char aff = (iParm>>16)&0xFF;
        aff = sqlite3CompareAffinity(pEList->a[0].pExpr, aff);
        affStr = sqlite3AffinityString(aff);
        sqlite3VdbeOp3(v, OP_MakeRecord, 1, 0, affStr, P3_STATIC);
        sqlite3VdbeAddOp(v, OP_String8, 0, 0);
        sqlite3VdbeAddOp(v, OP_PutStrKey, (iParm&0x0000FFFF), 0);
      }
      sqlite3VdbeChangeP2(v, addr2, sqlite3VdbeCurrentAddr(v));
      break;
    }

/*
** 2001 September 15
**
** 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.
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.322 2004/09/19 02:15:26 drh Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

#include "config.h"
#include "sqlite3.h"
#include "hash.h"

int sqlite3GetVarint(const unsigned char *, u64 *);
int sqlite3GetVarint32(const unsigned char *, u32 *);
int sqlite3VarintLen(u64 v);
char sqlite3AffinityType(const char *, int);
void sqlite3IndexAffinityStr(Vdbe *, Index *);
void sqlite3TableAffinityStr(Vdbe *, Table *);
char sqlite3CompareAffinity(Expr *pExpr, char aff2);
char const *sqlite3AffinityString(char affinity);
int sqlite3IndexAffinityOk(Expr *pExpr, char idx_affinity);
char sqlite3ExprAffinity(Expr *pExpr);
int sqlite3atoi64(const char*, i64*);
void sqlite3Error(sqlite3*, int, const char*,...);
void *sqlite3HexToBlob(const char *z);
int sqlite3TwoPartName(Parse *, Token *, Token *, Token **);
const char *sqlite3ErrStr(int);

**    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.114 2004/09/19 02:15:26 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.

*/
static void disableTerm(WhereLevel *pLevel, Expr **ppExpr){
  Expr *pExpr = *ppExpr;
  if( pLevel->iLeftJoin==0 || ExprHasProperty(pExpr, EP_FromJoin) ){
    *ppExpr = 0;
  }
}















































/*
** Generate the beginning of the loop used for WHERE clause processing.
** The return value is a pointer to an (opaque) structure that contains
** information needed to terminate the loop.  Later, the calling routine
** should invoke sqlite3WhereEnd() with the return value of this function
** in order to complete the WHERE clause processing.

  ** Actually, if there are more than 32 tables in the join, only the
  ** first 32 tables are candidates for indices.  This is (again) due
  ** to the limit of 32 bits in an integer bitmask.
  */
  loopMask = 0;
  for(i=0; i<pTabList->nSrc && i<ARRAYSIZE(iDirectEq); i++){
    int j;

    int iCur = pTabList->a[i].iCursor;    /* The cursor for this table */
    int mask = getMask(&maskSet, iCur);   /* Cursor mask for this table */
    Table *pTab = pTabList->a[i].pTab;
    Index *pIdx;
    Index *pBestIdx = 0;
    int bestScore = 0;

    /* Check to see if there is an expression that uses only the
    ** ROWID field of this table.  For terms of the form ROWID==expr
    ** set iDirectEq[i] to the index of the term.  For terms of the
    ** form ROWID<expr or ROWID<=expr set iDirectLt[i] to the term index.
    ** For terms like ROWID>expr or ROWID>=expr set iDirectGt[i].
    **
    ** (Added:) Treat ROWID IN expr like ROWID=expr.
    */
    pWInfo->a[i].iCur = -1;
    iDirectEq[i] = -1;
    iDirectLt[i] = -1;
    iDirectGt[i] = -1;
    for(pTerm=aExpr, j=0; j<nExpr; j++, pTerm++){
      Expr *pX = pTerm->p;
      if( pTerm->idxLeft==iCur && pX->pLeft->iColumn<0
            && (pTerm->prereqRight & loopMask)==pTerm->prereqRight ){
        switch( pX->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( iDirectEq[i]>=0 ){
      loopMask |= mask;
      pWInfo->a[i].pIdx = 0;
      continue;
    }

    /* Do a search for usable indices.  Leave pBestIdx pointing to
    ** the "best" index.  pBestIdx is left set to NULL if no indices
    ** are usable.
    **

      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(pTerm=aExpr, j=0; j<nExpr; j++, pTerm++){
        CollSeq *pColl = sqlite3ExprCollSeq(pParse, pTerm->p->pLeft);
        Expr *pX = pTerm->p;

        if( !pColl && pX->pRight ){
          pColl = sqlite3ExprCollSeq(pParse, pX->pRight);
        }
        if( !pColl ){
          pColl = pParse->db->pDfltColl;
        }
        if( pTerm->idxLeft==iCur 

      if( m & gtMask ) score+=2;   /* Increase score for a > constraint */
      if( score==0 && inMask ) score = 4;  /* Default score for IN constraint */
      if( score>bestScore ){
        pBestIdx = pIdx;
        bestScore = score;
      }
    }
    pWInfo->a[i].pIdx = pBestIdx;
    pWInfo->a[i].score = bestScore;
    pWInfo->a[i].bRev = 0;
    loopMask |= mask;
    if( pBestIdx ){
      pWInfo->a[i].iCur = pParse->nTab++;
    }
  }

  /* Check to see if the ORDER BY clause is or can be satisfied by the
  ** use of an index on the first table.
  */
  if( ppOrderBy && *ppOrderBy && pTabList->nSrc>0 ){

      sqlite3VdbeAddOp(v, OP_String8, 0, 0);
      sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iLeftJoin, 1);
      VdbeComment((v, "# init LEFT JOIN no-match flag"));
    }

    pIdx = pLevel->pIdx;
    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.
      */
      Expr *pX;
      k = iDirectEq[i];
      assert( k<nExpr );
      pTerm = &aExpr[k];
      assert( pTerm->p!=0 );
      assert( pTerm->idxLeft==iCur || pTerm->idxRight==iCur );
      brk = pLevel->brk = sqlite3VdbeMakeLabel(v);
      pX = pTerm->p;
      assert( pTerm->idxLeft==iCur );
      if( pX->op!=TK_IN ){
        sqlite3ExprCode(pParse, pTerm->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;
      }
      disableTerm(pLevel, &pTerm->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

          Expr *pX = pTerm->p;
          if( pX==0 ) continue;
          if( pTerm->idxLeft==iCur
             && (pTerm->prereqRight & loopMask)==pTerm->prereqRight 
             && pX->pLeft->iColumn==pIdx->aiColumn[j]
          ){
            char idxaff = pIdx->pTable->aCol[pX->pLeft->iColumn].affinity;
            if( sqlite3IndexAffinityOk(pTerm->p, idxaff) ){
              if( pX->op==TK_EQ ){
                sqlite3ExprCode(pParse, pX->pRight);
                disableTerm(pLevel, &pTerm->p);
                break;
              }
              assert( pX->op==TK_IN && nColumn==1 );
              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, &pTerm->p);
                break;
              }
            }
          }
        }
      }
      pLevel->iMem = pParse->nMem++;
      cont = pLevel->cont = sqlite3VdbeMakeLabel(v);

      /* At this point, the top nColumn elements of the stack are the
      ** values of columns in the index we are using.  Check to see if
      ** any of these values are NULL.  If they are, they will not match any
      ** index entries, so skip immediately to the next iteration of the loop */
      sqlite3VdbeAddOp(v, OP_NotNull, -nColumn, sqlite3VdbeCurrentAddr(v)+3);
      sqlite3VdbeAddOp(v, OP_Pop, nColumn, 0);
      sqlite3VdbeAddOp(v, OP_Goto, 0, brk);

      /* Generate an index key from the top nColumn elements of the stack */
      sqlite3VdbeAddOp(v, OP_MakeRecord, nColumn, 0);
      sqlite3IndexAffinityStr(v, pIdx);
      sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 0);

      /* Generate code (1) to move to the first matching element of the table.
      ** Then generate code (2) that jumps to "brk" after the cursor is past
      ** the last matching element of the table.  The code (1) is executed
      ** once to initialize the search, the code (2) is executed before each
      ** iteration of the scan to see if the scan has finished. */

      */
      int testOp = OP_Noop;
      int start;

      brk = pLevel->brk = sqlite3VdbeMakeLabel(v);
      cont = pLevel->cont = sqlite3VdbeMakeLabel(v);
      if( iDirectGt[i]>=0 ){

        k = iDirectGt[i];
        assert( k<nExpr );
        pTerm = &aExpr[k];

        assert( pTerm->p!=0 );
        assert( pTerm->idxLeft==iCur );
        sqlite3ExprCode(pParse, pTerm->p->pRight);
        sqlite3VdbeAddOp(v, OP_ForceInt,
          pTerm->p->op==TK_LT || pTerm->p->op==TK_GT, brk);
        sqlite3VdbeAddOp(v, OP_MoveGe, iCur, brk);
        disableTerm(pLevel, &pTerm->p);
      }else{
        sqlite3VdbeAddOp(v, OP_Rewind, iCur, brk);
      }
      if( iDirectLt[i]>=0 ){

        k = iDirectLt[i];
        assert( k<nExpr );
        pTerm = &aExpr[k];

        assert( pTerm->p!=0 );
        assert( pTerm->idxLeft==iCur );
        sqlite3ExprCode(pParse, pTerm->p->pRight);
        /* sqlite3VdbeAddOp(v, OP_MustBeInt, 0, sqlite3VdbeCurrentAddr(v)+1); */
        pLevel->iMem = pParse->nMem++;
        sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 1);
        if( pTerm->p->op==TK_LT || pTerm->p->op==TK_GT ){
          testOp = OP_Ge;
        }else{
          testOp = OP_Gt;
        }
        disableTerm(pLevel, &pTerm->p);
      }
      start = sqlite3VdbeCurrentAddr(v);

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

      /* Evaluate the equality constraints
      */
      for(j=0; j<nEqColumn; j++){

        for(pTerm=aExpr, k=0; k<nExpr; k++, pTerm++){

          if( pTerm->p==0 ) continue;
          if( pTerm->idxLeft==iCur
             && pTerm->p->op==TK_EQ
             && (pTerm->prereqRight & loopMask)==pTerm->prereqRight 
             && pTerm->p->pLeft->iColumn==pIdx->aiColumn[j]
          ){
            sqlite3ExprCode(pParse, pTerm->p->pRight);
            disableTerm(pLevel, &pTerm->p);
            break;
          }
        }
      }

      /* Duplicate the equality term values because they will all be

      ** 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(pTerm=aExpr, k=0; k<nExpr; k++, pTerm++){
          Expr *pExpr = pTerm->p;
          if( pExpr==0 ) continue;
          if( pTerm->idxLeft==iCur
             && (pExpr->op==TK_LT || pExpr->op==TK_LE)
             && (pTerm->prereqRight & loopMask)==pTerm->prereqRight 
             && pExpr->pLeft->iColumn==pIdx->aiColumn[j]
          ){
            sqlite3ExprCode(pParse, pExpr->pRight);
            leFlag = pExpr->op==TK_LE;
            disableTerm(pLevel, &pTerm->p);
            break;
          }
        }
        testOp = OP_IdxGE;
      }else{
        testOp = nEqColumn>0 ? OP_IdxGE : OP_Noop;
        leFlag = 1;
      }
      if( testOp!=OP_Noop ){
        int nCol = nEqColumn + (score & 1);
        pLevel->iMem = pParse->nMem++;
        sqlite3VdbeAddOp(v, OP_NotNull, -nCol, sqlite3VdbeCurrentAddr(v)+3);
        sqlite3VdbeAddOp(v, OP_Pop, nCol, 0);
        sqlite3VdbeAddOp(v, OP_Goto, 0, brk);
        sqlite3VdbeAddOp(v, OP_MakeRecord, nCol, 0);
        sqlite3IndexAffinityStr(v, pIdx);
        if( pLevel->bRev ){
          int op = leFlag ? OP_MoveLe : OP_MoveLt;
          sqlite3VdbeAddOp(v, op, pLevel->iCur, brk);
        }else{
          sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 1);
        }
      }else if( pLevel->bRev ){

      ** 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(pTerm=aExpr, k=0; k<nExpr; k++, pTerm++){
          Expr *pExpr = pTerm->p;
          if( pExpr==0 ) continue;
          if( pTerm->idxLeft==iCur
             && (pExpr->op==TK_GT || pExpr->op==TK_GE)
             && (pTerm->prereqRight & loopMask)==pTerm->prereqRight 
             && pExpr->pLeft->iColumn==pIdx->aiColumn[j]
          ){
            sqlite3ExprCode(pParse, pExpr->pRight);
            geFlag = pExpr->op==TK_GE;
            disableTerm(pLevel, &pTerm->p);
            break;
          }
        }
      }else{
        geFlag = 1;
      }
      if( nEqColumn>0 || (score&2)!=0 ){
        int nCol = nEqColumn + ((score&2)!=0);
        sqlite3VdbeAddOp(v, OP_NotNull, -nCol, sqlite3VdbeCurrentAddr(v)+3);
        sqlite3VdbeAddOp(v, OP_Pop, nCol, 0);
        sqlite3VdbeAddOp(v, OP_Goto, 0, brk);
        sqlite3VdbeAddOp(v, OP_MakeRecord, nCol, 0);
        sqlite3IndexAffinityStr(v, pIdx);
        if( pLevel->bRev ){
          pLevel->iMem = pParse->nMem++;
          sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 1);
          testOp = OP_IdxLT;
        }else{
          int op = geFlag ? OP_MoveGe : OP_MoveGt;
          sqlite3VdbeAddOp(v, op, pLevel->iCur, brk);