/*

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

    sqliteFree(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 = sqliteMalloc( sizeof(pWC->a[0])*pWC->nSlot*2 );

    if( pWC->a==0 ){

      if( flags & TERM_DYNAMIC ){

        sqlite3ExprDelete(p);

      }

      return 0;

    }

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

    if( pOld!=pWC->aStatic ){

      sqliteFree(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;

  if( pS==0 ){

    mask = 0;

  }else{

    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);

  }

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

*/

static void exprCommute(Expr *pExpr){

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

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

  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(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 );