/*

 ** 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.

 **

 *************************************************************************

 ** 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$

 */

 #include "sqliteInt.h"

 /*

 ** The number of bits in a Bitmask.  "BMS" means "BitMask Size".

 */

 #define BMS  (sizeof(Bitmask)*8)

 /*

 ** Trace output macros

 */

 #if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)

 int sqlite3_where_trace = 0;

 # define WHERETRACE(X)  if(sqlite3_where_trace) sqlite3DebugPrintf X

 #else

 # define WHERETRACE(X)

 #endif

 /* Forward reference

 */

 typedef struct WhereClause WhereClause;

 typedef struct ExprMaskSet ExprMaskSet;

 /*

 ** 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.

 **

 ** All WhereTerms are collected into a single WhereClause structure.  

 ** The following identity holds:

 **

 **        WhereTerm.pWC->a[WhereTerm.idx] == WhereTerm

 **

 ** When a term is of the form:

 **

 **              X <op> <expr>

 **

 ** where X is a column name and <op> is one of certain operators,

 ** then WhereTerm.leftCursor and WhereTerm.leftColumn record the

 ** cursor number and column number for X.  WhereTerm.operator records

 ** the <op> using a bitmask encoding defined by WO_xxx below.  The

 ** use of a bitmask encoding for the operator allows us to search

 ** quickly for terms that match any of several different operators.

 **

 ** prereqRight and prereqAll record sets of cursor numbers,

 ** but they do so indirectly.  A single ExprMaskSet structure translates

 ** cursor number into bits and the translated bit is stored in the prereq

 ** fields.  The translation is used in order to maximize the number of

 ** bits that will fit in a Bitmask.  The VDBE cursor numbers might be

 ** spread out over the non-negative integers.  For example, the cursor

 ** numbers might be 3, 8, 9, 10, 20, 23, 41, and 45.  The ExprMaskSet

 ** translates these sparse cursor numbers into consecutive integers

 ** beginning with 0 in order to make the best possible use of the available

 ** bits in the Bitmask.  So, in the example above, the cursor numbers

 ** would be mapped into integers 0 through 7.

 */

 typedef struct WhereTerm WhereTerm;

 struct WhereTerm {

   Expr *pExpr;            /* Pointer to the subexpression */

   i16 iParent;            /* Disable pWC->a[iParent] when this term disabled */

   i16 leftCursor;         /* Cursor number of X in "X <op> <expr>" */

   i16 leftColumn;         /* Column number of X in "X <op> <expr>" */

   u16 eOperator;          /* A WO_xx value describing <op> */

   u8 flags;               /* Bit flags.  See below */

   u8 nChild;              /* Number of children that must disable us */

   WhereClause *pWC;       /* The clause this term is part of */

   Bitmask prereqRight;    /* Bitmask of tables used by pRight */

   Bitmask prereqAll;      /* Bitmask of tables referenced by p */

 };

 /*

 ** Allowed values of WhereTerm.flags

 */

 #define TERM_DYNAMIC    0x01   /* Need to call sqlite3ExprDelete(pExpr) */

 #define TERM_VIRTUAL    0x02   /* Added by the optimizer.  Do not code */

 #define TERM_CODED      0x04   /* This term is already coded */

 #define TERM_COPIED     0x08   /* Has a child */

 #define TERM_OR_OK      0x10   /* Used during OR-clause processing */

 /*

 ** An instance of the following structure holds all information about a

 ** WHERE clause.  Mostly this is a container for one or more WhereTerms.

 */

 struct WhereClause {

   Parse *pParse;           /* The parser context */

   ExprMaskSet *pMaskSet;   /* Mapping of table indices to bitmasks */

   int nTerm;               /* Number of terms */

   int nSlot;               /* Number of entries in a[] */

   WhereTerm *a;            /* Each a[] describes a term of the WHERE cluase */

   WhereTerm aStatic[10];   /* Initial static space for a[] */

 };

 /*

 ** An instance of the following structure keeps track of a mapping

 ** between VDBE cursor numbers and bits of the bitmasks in WhereTerm.

 **

 ** The VDBE cursor numbers are small integers contained in 

 ** SrcList_item.iCursor and Expr.iTable fields.  For any given WHERE 

 ** clause, the cursor numbers might not begin with 0 and they might

 ** contain gaps in the numbering sequence.  But we want to make maximum

 ** use of the bits in our bitmasks.  This structure provides a mapping

 ** from the sparse cursor numbers into consecutive integers beginning

 ** with 0.

 **

 ** If ExprMaskSet.ix[A]==B it means that The A-th bit of a Bitmask

 ** corresponds VDBE cursor number B.  The A-th bit of a bitmask is 1<<A.

 **

 ** For example, if the WHERE clause expression used these VDBE

 ** cursors:  4, 5, 8, 29, 57, 73.  Then the  ExprMaskSet structure

 ** would map those cursor numbers into bits 0 through 5.

 **

 ** Note that the mapping is not necessarily ordered.  In the example

 ** above, the mapping might go like this:  4->3, 5->1, 8->2, 29->0,

 ** 57->5, 73->4.  Or one of 719 other combinations might be used. It

 ** does not really matter.  What is important is that sparse cursor

 ** numbers all get mapped into bit numbers that begin with 0 and contain

 ** no gaps.

 */

 struct ExprMaskSet {

   int n;                        /* Number of assigned cursor values */

   int ix[sizeof(Bitmask)*8];    /* Cursor assigned to each bit */

 };

 /*

 ** Bitmasks for the operators that indices are able to exploit.  An

 ** OR-ed combination of these values can be used when searching for

 ** terms in the where clause.

 */

 #define WO_IN     1

 #define WO_EQ     2

 #define WO_LT     (WO_EQ<<(TK_LT-TK_EQ))

 #define WO_LE     (WO_EQ<<(TK_LE-TK_EQ))

 #define WO_GT     (WO_EQ<<(TK_GT-TK_EQ))

 #define WO_GE     (WO_EQ<<(TK_GE-TK_EQ))

 #define WO_MATCH  64

 #define WO_ISNULL 128

 /*

 ** Value for flags returned by bestIndex().  

 **

 ** The least significant byte is reserved as a mask for WO_ values above.

 ** The WhereLevel.flags field is usually set to WO_IN|WO_EQ|WO_ISNULL.

 ** But if the table is the right table of a left join, WhereLevel.flags

 ** is set to WO_IN|WO_EQ.  The WhereLevel.flags field can then be used as

 ** the "op" parameter to findTerm when we are resolving equality constraints.

 ** ISNULL constraints will then not be used on the right table of a left

 ** join.  Tickets #2177 and #2189.

 */

 #define WHERE_ROWID_EQ     0x000100   /* rowid=EXPR or rowid IN (...) */

 #define WHERE_ROWID_RANGE  0x000200   /* rowid<EXPR and/or rowid>EXPR */

 #define WHERE_COLUMN_EQ    0x001000   /* x=EXPR or x IN (...) */

 #define WHERE_COLUMN_RANGE 0x002000   /* x<EXPR and/or x>EXPR */

 #define WHERE_COLUMN_IN    0x004000   /* x IN (...) */

 #define WHERE_TOP_LIMIT    0x010000   /* x<EXPR or x<=EXPR constraint */

 #define WHERE_BTM_LIMIT    0x020000   /* x>EXPR or x>=EXPR constraint */

 #define WHERE_IDX_ONLY     0x080000   /* Use index only - omit table */

 #define WHERE_ORDERBY      0x100000   /* Output will appear in correct order */

 #define WHERE_REVERSE      0x200000   /* Scan in reverse order */

 #define WHERE_UNIQUE       0x400000   /* Selects no more than one row */

 #define WHERE_VIRTUALTABLE 0x800000   /* Use virtual-table processing */

 /*

 ** Initialize a preallocated WhereClause structure.

 */

 static void whereClauseInit(

   WhereClause *pWC,        /* The WhereClause to be initialized */

   Parse *pParse,           /* The parsing context */

   ExprMaskSet *pMaskSet    /* Mapping from table indices to bitmasks */

 ){

   pWC->pParse = pParse;

   pWC->pMaskSet = pMaskSet;

   pWC->nTerm = 0;

   pWC->nSlot = ArraySize(pWC->aStatic);

   pWC->a = pWC->aStatic;

 }

 /*

 ** Deallocate a WhereClause structure.  The WhereClause structure

 ** itself is not freed.  This routine is the inverse of whereClauseInit().

 */

 static void whereClauseClear(WhereClause *pWC){

   int i;

   WhereTerm *a;

   for(i=pWC->nTerm-1, a=pWC->a; i>=0; i--, a++){

     if( a->flags & TERM_DYNAMIC ){

       sqlite3ExprDelete(a->pExpr);

     }

   }

   if( pWC->a!=pWC->aStatic ){

     sqlite3_free(pWC->a);

   }

 }

 /*

 ** Add a new entries to the WhereClause structure.  Increase the allocated

 ** space as necessary.

 **

 ** If the flags argument includes TERM_DYNAMIC, then responsibility

 ** for freeing the expression p is assumed by the WhereClause object.

 **

 ** WARNING:  This routine might reallocate the space used to store

 ** WhereTerms.  All pointers to WhereTerms should be invalided after

 ** calling this routine.  Such pointers may be reinitialized by referencing

 ** the pWC->a[] array.

 */

 static int whereClauseInsert(WhereClause *pWC, Expr *p, int flags){

   WhereTerm *pTerm;

   int idx;

   if( pWC->nTerm>=pWC->nSlot ){

     WhereTerm *pOld = pWC->a;

     pWC->a = sqlite3_malloc( sizeof(pWC->a[0])*pWC->nSlot*2 );

     if( pWC->a==0 ){

       pWC->pParse->db->mallocFailed = 1;

       if( flags & TERM_DYNAMIC ){

         sqlite3ExprDelete(p);

       }

       return 0;

     }

     memcpy(pWC->a, pOld, sizeof(pWC->a[0])*pWC->nTerm);

     if( pOld!=pWC->aStatic ){

       sqlite3_free(pOld);

     }

     pWC->nSlot *= 2;

   }

   pTerm = &pWC->a[idx = pWC->nTerm];

   pWC->nTerm++;

   pTerm->pExpr = p;

   pTerm->flags = flags;

   pTerm->pWC = pWC;

   pTerm->iParent = -1;

   return idx;

 }

 /*

 ** This routine identifies subexpressions in the WHERE clause where

 ** each subexpression is separated by the AND operator or some other

 ** operator specified in the op parameter.  The WhereClause structure

 ** is filled with pointers to subexpressions.  For example:

 **

 **    WHERE  a=='hello' AND coalesce(b,11)<10 AND (c+12!=d OR c==22)

 **           \________/     \_______________/     \________________/

 **            slot[0]            slot[1]               slot[2]

 **

 ** The original WHERE clause in pExpr is unaltered.  All this routine

 ** does is make slot[] entries point to substructure within pExpr.

 **

 ** In the previous sentence and in the diagram, "slot[]" refers to

 ** the WhereClause.a[] array.  This array grows as needed to contain

 ** all terms of the WHERE clause.

 */

 static void whereSplit(WhereClause *pWC, Expr *pExpr, int op){

   if( pExpr==0 ) return;

   if( pExpr->op!=op ){

     whereClauseInsert(pWC, pExpr, 0);

   }else{

     whereSplit(pWC, pExpr->pLeft, op);

     whereSplit(pWC, pExpr->pRight, op);

   }

 }

 /*

 ** Initialize an expression mask set

 */

 #define initMaskSet(P)  memset(P, 0, sizeof(*P))

 /*

 ** Return the bitmask for the given cursor number.  Return 0 if

 ** iCursor is not in the set.

 */

 static Bitmask getMask(ExprMaskSet *pMaskSet, int iCursor){

   int i;

   for(i=0; i<pMaskSet->n; i++){

     if( pMaskSet->ix[i]==iCursor ){

       return ((Bitmask)1)<<i;

     }

   }

   return 0;

 }

 /*

 ** Create a new mask for cursor iCursor.

 **

 ** There is one cursor per table in the FROM clause.  The number of

 ** tables in the FROM clause is limited by a test early in the

 ** sqlite3WhereBegin() routine.  So we know that the pMaskSet->ix[]

 ** array will never overflow.

 */

 static void createMask(ExprMaskSet *pMaskSet, int iCursor){

   assert( pMaskSet->n < ArraySize(pMaskSet->ix) );

   pMaskSet->ix[pMaskSet->n++] = iCursor;

 }

 /*

 ** This routine walks (recursively) an expression tree and generates

 ** a bitmask indicating which tables are used in that expression

 ** tree.

 **

 ** In order for this routine to work, the calling function must have

 ** previously invoked sqlite3ExprResolveNames() on the expression.  See

 ** the header comment on that routine for additional information.

 ** The sqlite3ExprResolveNames() routines looks for column names and

 ** sets their opcodes to TK_COLUMN and their Expr.iTable fields to

 ** the VDBE cursor number of the table.  This routine just has to

 ** translate the cursor numbers into bitmask values and OR all

 ** the bitmasks together.

 */

 static Bitmask exprListTableUsage(ExprMaskSet*, ExprList*);

 static Bitmask exprSelectTableUsage(ExprMaskSet*, Select*);

 static Bitmask exprTableUsage(ExprMaskSet *pMaskSet, Expr *p){

   Bitmask mask = 0;

   if( p==0 ) return 0;

   if( p->op==TK_COLUMN ){

     mask = getMask(pMaskSet, p->iTable);

     return mask;

   }

   mask = exprTableUsage(pMaskSet, p->pRight);

   mask |= exprTableUsage(pMaskSet, p->pLeft);

   mask |= exprListTableUsage(pMaskSet, p->pList);

   mask |= exprSelectTableUsage(pMaskSet, p->pSelect);

   return mask;

 }

 static Bitmask exprListTableUsage(ExprMaskSet *pMaskSet, ExprList *pList){

   int i;

   Bitmask mask = 0;

   if( pList ){

     for(i=0; i<pList->nExpr; i++){

       mask |= exprTableUsage(pMaskSet, pList->a[i].pExpr);

     }

   }

   return mask;

 }

 static Bitmask exprSelectTableUsage(ExprMaskSet *pMaskSet, Select *pS){

   Bitmask mask = 0;

   while( pS ){

     mask |= exprListTableUsage(pMaskSet, pS->pEList);

     mask |= exprListTableUsage(pMaskSet, pS->pGroupBy);

     mask |= exprListTableUsage(pMaskSet, pS->pOrderBy);

     mask |= exprTableUsage(pMaskSet, pS->pWhere);

     mask |= exprTableUsage(pMaskSet, pS->pHaving);

     pS = pS->pPrior;

   }

   return mask;

 }

 /*

 ** Return TRUE if the given operator is one of the operators that is

 ** allowed for an indexable WHERE clause term.  The allowed operators are

 ** "=", "<", ">", "<=", ">=", and "IN".

 */

 static int allowedOp(int op){

   assert( TK_GT>TK_EQ && TK_GT<TK_GE );

   assert( TK_LT>TK_EQ && TK_LT<TK_GE );

   assert( TK_LE>TK_EQ && TK_LE<TK_GE );

   assert( TK_GE==TK_EQ+4 );

   return op==TK_IN || (op>=TK_EQ && op<=TK_GE) || op==TK_ISNULL;

 }

 /*

 ** Swap two objects of type T.

 */

 #define SWAP(TYPE,A,B) {TYPE t=A; A=B; B=t;}

 /*

 ** Commute a comparision operator.  Expressions of the form "X op Y"

 ** are converted into "Y op X".

 **

 ** If a collation sequence is associated with either the left or right

 ** side of the comparison, it remains associated with the same side after

 ** the commutation. So "Y collate NOCASE op X" becomes 

 ** "X collate NOCASE op Y". This is because any collation sequence on

 ** the left hand side of a comparison overrides any collation sequence 

 ** attached to the right. For the same reason the EP_ExpCollate flag

 ** is not commuted.

 */

 static void exprCommute(Expr *pExpr){

   u16 expRight = (pExpr->pRight->flags & EP_ExpCollate);

   u16 expLeft = (pExpr->pLeft->flags & EP_ExpCollate);

   assert( allowedOp(pExpr->op) && pExpr->op!=TK_IN );

   SWAP(CollSeq*,pExpr->pRight->pColl,pExpr->pLeft->pColl);

   pExpr->pRight->flags = (pExpr->pRight->flags & ~EP_ExpCollate) | expLeft;

   pExpr->pLeft->flags = (pExpr->pLeft->flags & ~EP_ExpCollate) | expRight;

   SWAP(Expr*,pExpr->pRight,pExpr->pLeft);

   if( pExpr->op>=TK_GT ){

     assert( TK_LT==TK_GT+2 );

     assert( TK_GE==TK_LE+2 );

     assert( TK_GT>TK_EQ );

     assert( TK_GT<TK_LE );

     assert( pExpr->op>=TK_GT && pExpr->op<=TK_GE );

     pExpr->op = ((pExpr->op-TK_GT)^2)+TK_GT;

   }

 }

 /*

 ** Translate from TK_xx operator to WO_xx bitmask.

 */

 static int operatorMask(int op){

   int c;

   assert( allowedOp(op) );

   if( op==TK_IN ){

     c = WO_IN;

   }else if( op==TK_ISNULL ){

     c = WO_ISNULL;

   }else{

     c = WO_EQ<<(op-TK_EQ);

   }

   assert( op!=TK_ISNULL || c==WO_ISNULL );

   assert( op!=TK_IN || c==WO_IN );

   assert( op!=TK_EQ || c==WO_EQ );

   assert( op!=TK_LT || c==WO_LT );

   assert( op!=TK_LE || c==WO_LE );

   assert( op!=TK_GT || c==WO_GT );

   assert( op!=TK_GE || c==WO_GE );

   return c;

 }

 /*

 ** 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 one of

 ** the WO_xx operator codes specified by the op parameter.

 ** Return a pointer to the term.  Return 0 if not found.

 */

 static WhereTerm *findTerm(

   WhereClause *pWC,     /* The WHERE clause to be searched */

   int iCur,             /* Cursor number of LHS */

   int iColumn,          /* Column number of LHS */

   Bitmask notReady,     /* RHS must not overlap with this mask */

   u16 op,               /* Mask of WO_xx values describing operator */

   Index *pIdx           /* Must be compatible with this index, if not NULL */

 ){

   WhereTerm *pTerm;

   int k;

   for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){

     if( pTerm->leftCursor==iCur

        && (pTerm->prereqRight & notReady)==0

        && pTerm->leftColumn==iColumn

        && (pTerm->eOperator & op)!=0

     ){

       if( iCur>=0 && pIdx && pTerm->eOperator!=WO_ISNULL ){

         Expr *pX = pTerm->pExpr;

         CollSeq *pColl;

         char idxaff;

         int j;

         Parse *pParse = pWC->pParse;

         idxaff = pIdx->pTable->aCol[iColumn].affinity;

         if( !sqlite3IndexAffinityOk(pX, idxaff) ) continue;

         /* Figure out the collation sequence required from an index for

         ** it to be useful for optimising expression pX. Store this

         ** value in variable pColl.

         */

         assert(pX->pLeft);

         pColl = sqlite3BinaryCompareCollSeq(pParse, pX->pLeft, pX->pRight);

         if( !pColl ){

           pColl = pParse->db->pDfltColl;

         }

         for(j=0; j<pIdx->nColumn && pIdx->aiColumn[j]!=iColumn; j++){}

         assert( j<pIdx->nColumn );

         if( sqlite3StrICmp(pColl->zName, pIdx->azColl[j]) ) continue;

       }

       return pTerm;

     }

   }

   return 0;

 }

 /* Forward reference */

 static void exprAnalyze(SrcList*, WhereClause*, int);

 /*

 ** Call exprAnalyze on all terms in a WHERE clause.  

 **

 **

 */

 static void exprAnalyzeAll(

   SrcList *pTabList,       /* the FROM clause */

   WhereClause *pWC         /* the WHERE clause to be analyzed */

 ){

   int i;

   for(i=pWC->nTerm-1; i>=0; i--){

     exprAnalyze(pTabList, pWC, i);

   }

 }

 #ifndef SQLITE_OMIT_LIKE_OPTIMIZATION

 /*

 ** Check to see if the given expression is a LIKE or GLOB operator that

 ** can be optimized using inequality constraints.  Return TRUE if it is

 ** so and false if not.

 **

 ** In order for the operator to be optimizible, the RHS must be a string

 ** literal that does not begin with a wildcard.  

 */

 static int isLikeOrGlob(

   sqlite3 *db,      /* The database */

   Expr *pExpr,      /* Test this expression */

   int *pnPattern,   /* Number of non-wildcard prefix characters */

   int *pisComplete  /* True if the only wildcard is % in the last character */

 ){

   const char *z;

   Expr *pRight, *pLeft;

   ExprList *pList;

   int c, cnt;

   int noCase;

   char wc[3];

   CollSeq *pColl;

   if( !sqlite3IsLikeFunction(db, pExpr, &noCase, wc) ){

     return 0;

   }

   pList = pExpr->pList;

   pRight = pList->a[0].pExpr;

   if( pRight->op!=TK_STRING ){

     return 0;

   }

   pLeft = pList->a[1].pExpr;

   if( pLeft->op!=TK_COLUMN ){

     return 0;

   }

   pColl = pLeft->pColl;

   if( pColl==0 ){

     /* TODO: Coverage testing doesn't get this case. Is it actually possible

     ** for an expression of type TK_COLUMN to not have an assigned collation 

     ** sequence at this point?

     */

     pColl = db->pDfltColl;

   }

   if( (pColl->type!=SQLITE_COLL_BINARY || noCase) &&

       (pColl->type!=SQLITE_COLL_NOCASE || !noCase) ){

     return 0;

   }

   sqlite3DequoteExpr(db, pRight);

   z = (char *)pRight->token.z;

   for(cnt=0; (c=z[cnt])!=0 && c!=wc[0] && c!=wc[1] && c!=wc[2]; cnt++){}

   if( cnt==0 || 255==(u8)z[cnt] ){

     return 0;

   }

   *pisComplete = z[cnt]==wc[0] && z[cnt+1]==0;

   *pnPattern = cnt;

   return 1;

 }

 #endif /* SQLITE_OMIT_LIKE_OPTIMIZATION */

 #ifndef SQLITE_OMIT_VIRTUALTABLE

 /*

 ** Check to see if the given expression is of the form

 **

 **         column MATCH expr

 **

 ** If it is then return TRUE.  If not, return FALSE.

 */

 static int isMatchOfColumn(

   Expr *pExpr      /* Test this expression */

 ){

   ExprList *pList;

   if( pExpr->op!=TK_FUNCTION ){

     return 0;

   }

   if( pExpr->token.n!=5 ||

        sqlite3StrNICmp((const char*)pExpr->token.z,"match",5)!=0 ){

     return 0;

   }

   pList = pExpr->pList;

   if( pList->nExpr!=2 ){

     return 0;

   }

   if( pList->a[1].pExpr->op != TK_COLUMN ){

     return 0;

   }

   return 1;

 }

 #endif /* SQLITE_OMIT_VIRTUALTABLE */

 /*

 ** If the pBase expression originated in the ON or USING clause of

 ** a join, then transfer the appropriate markings over to derived.

 */

 static void transferJoinMarkings(Expr *pDerived, Expr *pBase){

   pDerived->flags |= pBase->flags & EP_FromJoin;

   pDerived->iRightJoinTable = pBase->iRightJoinTable;

 }

 #if !defined(SQLITE_OMIT_OR_OPTIMIZATION) && !defined(SQLITE_OMIT_SUBQUERY)

 /*

 ** Return TRUE if the given term of an OR clause can be converted

 ** into an IN clause.  The iCursor and iColumn define the left-hand

 ** side of the IN clause.

 **

 ** The context is that we have multiple OR-connected equality terms

 ** like this:

 **

 **           a=<expr1> OR  a=<expr2> OR b=<expr3>  OR ...

 **

 ** The pOrTerm input to this routine corresponds to a single term of

 ** this OR clause.  In order for the term to be a condidate for

 ** conversion to an IN operator, the following must be true:

 **

 **     *  The left-hand side of the term must be the column which

 **        is identified by iCursor and iColumn.

 **

 **     *  If the right-hand side is also a column, then the affinities

 **        of both right and left sides must be such that no type

 **        conversions are required on the right.  (Ticket #2249)

 **

 ** If both of these conditions are true, then return true.  Otherwise

 ** return false.

 */

 static int orTermIsOptCandidate(WhereTerm *pOrTerm, int iCursor, int iColumn){

   int affLeft, affRight;

   assert( pOrTerm->eOperator==WO_EQ );

   if( pOrTerm->leftCursor!=iCursor ){

     return 0;

   }

   if( pOrTerm->leftColumn!=iColumn ){

     return 0;

   }

   affRight = sqlite3ExprAffinity(pOrTerm->pExpr->pRight);

   if( affRight==0 ){

     return 1;

   }

   affLeft = sqlite3ExprAffinity(pOrTerm->pExpr->pLeft);

   if( affRight!=affLeft ){

     return 0;

   }

   return 1;

 }

 /*

 ** Return true if the given term of an OR clause can be ignored during

 ** a check to make sure all OR terms are candidates for optimization.

 ** In other words, return true if a call to the orTermIsOptCandidate()

 ** above returned false but it is not necessary to disqualify the

 ** optimization.

 **

 ** Suppose the original OR phrase was this:

 **

 **           a=4  OR  a=11  OR  a=b

 **

 ** During analysis, the third term gets flipped around and duplicate

 ** so that we are left with this:

 **

 **           a=4  OR  a=11  OR  a=b  OR  b=a

 **

 ** Since the last two terms are duplicates, only one of them

 ** has to qualify in order for the whole phrase to qualify.  When

 ** this routine is called, we know that pOrTerm did not qualify.

 ** This routine merely checks to see if pOrTerm has a duplicate that

 ** might qualify.  If there is a duplicate that has not yet been

 ** disqualified, then return true.  If there are no duplicates, or

 ** the duplicate has also been disqualifed, return false.

 */

 static int orTermHasOkDuplicate(WhereClause *pOr, WhereTerm *pOrTerm){

   if( pOrTerm->flags & TERM_COPIED ){

     /* This is the original term.  The duplicate is to the left had

     ** has not yet been analyzed and thus has not yet been disqualified. */

     return 1;

   }

   if( (pOrTerm->flags & TERM_VIRTUAL)!=0

      && (pOr->a[pOrTerm->iParent].flags & TERM_OR_OK)!=0 ){

     /* This is a duplicate term.  The original qualified so this one

     ** does not have to. */

     return 1;

   }

   /* This is either a singleton term or else it is a duplicate for

   ** which the original did not qualify.  Either way we are done for. */

   return 0;

 }

 #endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */

 /*

 ** The input to this routine is an WhereTerm structure with only the

 ** "pExpr" field filled in.  The job of this routine is to analyze the

 ** subexpression and populate all the other fields of the WhereTerm

 ** structure.

 **

 ** If the expression is of the form "<expr> <op> X" it gets commuted

 ** to the standard form of "X <op> <expr>".  If the expression is of

 ** the form "X <op> Y" where both X and Y are columns, then the original

 ** expression is unchanged and a new virtual expression of the form

 ** "Y <op> X" is added to the WHERE clause and analyzed separately.

 */

 static void exprAnalyze(

   SrcList *pSrc,            /* the FROM clause */

   WhereClause *pWC,         /* the WHERE clause */

   int idxTerm               /* Index of the term to be analyzed */

 ){

   WhereTerm *pTerm = &pWC->a[idxTerm];

   ExprMaskSet *pMaskSet = pWC->pMaskSet;

   Expr *pExpr = pTerm->pExpr;

   Bitmask prereqLeft;

   Bitmask prereqAll;

   int nPattern;

   int isComplete;

   int op;

   Parse *pParse = pWC->pParse;

   sqlite3 *db = pParse->db;

   if( db->mallocFailed ) return;

   prereqLeft = exprTableUsage(pMaskSet, pExpr->pLeft);

   op = pExpr->op;

   if( op==TK_IN ){

     assert( pExpr->pRight==0 );

     pTerm->prereqRight = exprListTableUsage(pMaskSet, pExpr->pList)

                           | exprSelectTableUsage(pMaskSet, pExpr->pSelect);

   }else if( op==TK_ISNULL ){

     pTerm->prereqRight = 0;

   }else{

     pTerm->prereqRight = exprTableUsage(pMaskSet, pExpr->pRight);

   }

   prereqAll = exprTableUsage(pMaskSet, pExpr);

   if( ExprHasProperty(pExpr, EP_FromJoin) ){

     prereqAll |= getMask(pMaskSet, pExpr->iRightJoinTable);

   }

   pTerm->prereqAll = prereqAll;

   pTerm->leftCursor = -1;

   pTerm->iParent = -1;

   pTerm->eOperator = 0;

   if( allowedOp(op) && (pTerm->prereqRight & prereqLeft)==0 ){

     Expr *pLeft = pExpr->pLeft;

     Expr *pRight = pExpr->pRight;

     if( pLeft->op==TK_COLUMN ){

       pTerm->leftCursor = pLeft->iTable;

       pTerm->leftColumn = pLeft->iColumn;

       pTerm->eOperator = operatorMask(op);

     }

     if( pRight && pRight->op==TK_COLUMN ){

       WhereTerm *pNew;

       Expr *pDup;

       if( pTerm->leftCursor>=0 ){

         int idxNew;

         pDup = sqlite3ExprDup(db, pExpr);

         if( db->mallocFailed ){

           sqlite3ExprDelete(pDup);

           return;

         }

         idxNew = whereClauseInsert(pWC, pDup, TERM_VIRTUAL|TERM_DYNAMIC);

         if( idxNew==0 ) return;

         pNew = &pWC->a[idxNew];

         pNew->iParent = idxTerm;

         pTerm = &pWC->a[idxTerm];

         pTerm->nChild = 1;

         pTerm->flags |= TERM_COPIED;

       }else{

         pDup = pExpr;

         pNew = pTerm;

       }

       exprCommute(pDup);

       pLeft = pDup->pLeft;

       pNew->leftCursor = pLeft->iTable;

       pNew->leftColumn = pLeft->iColumn;

       pNew->prereqRight = prereqLeft;

       pNew->prereqAll = prereqAll;

       pNew->eOperator = operatorMask(pDup->op);

     }

   }

 #ifndef SQLITE_OMIT_BETWEEN_OPTIMIZATION

   /* If a term is the BETWEEN operator, create two new virtual terms

   ** that define the range that the BETWEEN implements.

   */

   else if( pExpr->op==TK_BETWEEN ){

     ExprList *pList = pExpr->pList;

     int i;

     static const u8 ops[] = {TK_GE, TK_LE};

     assert( pList!=0 );

     assert( pList->nExpr==2 );

     for(i=0; i<2; i++){

       Expr *pNewExpr;

       int idxNew;

       pNewExpr = sqlite3Expr(db, ops[i], sqlite3ExprDup(db, pExpr->pLeft),

                              sqlite3ExprDup(db, pList->a[i].pExpr), 0);

       idxNew = whereClauseInsert(pWC, pNewExpr, TERM_VIRTUAL|TERM_DYNAMIC);

       exprAnalyze(pSrc, pWC, idxNew);

       pTerm = &pWC->a[idxTerm];

       pWC->a[idxNew].iParent = idxTerm;

     }

     pTerm->nChild = 2;

   }

 #endif /* SQLITE_OMIT_BETWEEN_OPTIMIZATION */

 #if !defined(SQLITE_OMIT_OR_OPTIMIZATION) && !defined(SQLITE_OMIT_SUBQUERY)

   /* Attempt to convert OR-connected terms into an IN operator so that

   ** they can make use of indices.  Example:

   **

   **      x = expr1  OR  expr2 = x  OR  x = expr3

   **

   ** is converted into

   **

   **      x IN (expr1,expr2,expr3)

   **

   ** This optimization must be omitted if OMIT_SUBQUERY is defined because

   ** the compiler for the the IN operator is part of sub-queries.

   */

   else if( pExpr->op==TK_OR ){

     int ok;

     int i, j;

     int iColumn, iCursor;

     WhereClause sOr;

     WhereTerm *pOrTerm;

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

     whereClauseInit(&sOr, pWC->pParse, pMaskSet);

     whereSplit(&sOr, pExpr, TK_OR);

     exprAnalyzeAll(pSrc, &sOr);

     assert( sOr.nTerm>=2 );

     j = 0;

     do{

       assert( j<sOr.nTerm );

       iColumn = sOr.a[j].leftColumn;

       iCursor = sOr.a[j].leftCursor;

       ok = iCursor>=0;

       for(i=sOr.nTerm-1, pOrTerm=sOr.a; i>=0 && ok; i--, pOrTerm++){

         if( pOrTerm->eOperator!=WO_EQ ){

           goto or_not_possible;

         }

         if( orTermIsOptCandidate(pOrTerm, iCursor, iColumn) ){

           pOrTerm->flags |= TERM_OR_OK;

         }else if( orTermHasOkDuplicate(&sOr, pOrTerm) ){

           pOrTerm->flags &= ~TERM_OR_OK;

         }else{

           ok = 0;

         }

       }

     }while( !ok && (sOr.a[j++].flags & TERM_COPIED)!=0 && j<2 );

     if( ok ){

       ExprList *pList = 0;

       Expr *pNew, *pDup;

       Expr *pLeft = 0;

       for(i=sOr.nTerm-1, pOrTerm=sOr.a; i>=0 && ok; i--, pOrTerm++){

         if( (pOrTerm->flags & TERM_OR_OK)==0 ) continue;

         pDup = sqlite3ExprDup(db, pOrTerm->pExpr->pRight);

         pList = sqlite3ExprListAppend(pWC->pParse, pList, pDup, 0);

         pLeft = pOrTerm->pExpr->pLeft;

       }

       assert( pLeft!=0 );

       pDup = sqlite3ExprDup(db, pLeft);

       pNew = sqlite3Expr(db, TK_IN, pDup, 0, 0);

       if( pNew ){

         int idxNew;

         transferJoinMarkings(pNew, pExpr);

         pNew->pList = pList;

         idxNew = whereClauseInsert(pWC, pNew, TERM_VIRTUAL|TERM_DYNAMIC);

         exprAnalyze(pSrc, pWC, idxNew);

         pTerm = &pWC->a[idxTerm];

         pWC->a[idxNew].iParent = idxTerm;

         pTerm->nChild = 1;

       }else{

         sqlite3ExprListDelete(pList);

       }

     }

 or_not_possible:

     whereClauseClear(&sOr);

   }

 #endif /* SQLITE_OMIT_OR_OPTIMIZATION */

 #ifndef SQLITE_OMIT_LIKE_OPTIMIZATION

   /* Add constraints to reduce the search space on a LIKE or GLOB

   ** operator.

   */

   if( isLikeOrGlob(db, pExpr, &nPattern, &isComplete) ){

     Expr *pLeft, *pRight;

     Expr *pStr1, *pStr2;

     Expr *pNewExpr1, *pNewExpr2;

     int idxNew1, idxNew2;

     pLeft = pExpr->pList->a[1].pExpr;

     pRight = pExpr->pList->a[0].pExpr;

     pStr1 = sqlite3PExpr(pParse, TK_STRING, 0, 0, 0);

     if( pStr1 ){

       sqlite3TokenCopy(db, &pStr1->token, &pRight->token);

       pStr1->token.n = nPattern;

       pStr1->flags = EP_Dequoted;

     }

     pStr2 = sqlite3ExprDup(db, pStr1);

     if( pStr2 ){

       assert( pStr2->token.dyn );

       ++*(u8*)&pStr2->token.z[nPattern-1];

     }

     pNewExpr1 = sqlite3PExpr(pParse, TK_GE, sqlite3ExprDup(db,pLeft), pStr1, 0);

     idxNew1 = whereClauseInsert(pWC, pNewExpr1, TERM_VIRTUAL|TERM_DYNAMIC);

     exprAnalyze(pSrc, pWC, idxNew1);

     pNewExpr2 = sqlite3PExpr(pParse, TK_LT, sqlite3ExprDup(db,pLeft), pStr2, 0);

     idxNew2 = whereClauseInsert(pWC, pNewExpr2, TERM_VIRTUAL|TERM_DYNAMIC);

     exprAnalyze(pSrc, pWC, idxNew2);

     pTerm = &pWC->a[idxTerm];

     if( isComplete ){

       pWC->a[idxNew1].iParent = idxTerm;

       pWC->a[idxNew2].iParent = idxTerm;

       pTerm->nChild = 2;

     }

   }

 #endif /* SQLITE_OMIT_LIKE_OPTIMIZATION */

 #ifndef SQLITE_OMIT_VIRTUALTABLE