if( wctrlFlags & WHERE_WANT_DISTINCT ){
      pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE;
    }
  }

  /* Assign a bit from the bitmask to every term in the FROM clause.
  **
  ** When assigning bitmask values to FROM clause cursors, it must be
  ** the case that if X is the bitmask for the N-th FROM clause term then
  ** the bitmask for all FROM clause terms to the left of the N-th term
  ** is (X-1).   An expression from the ON clause of a LEFT JOIN can use
  ** its Expr.iRightJoinTable value to find the bitmask of the right table
  ** of the join.  Subtracting one from the right table bitmask gives a
  ** bitmask for all tables to the left of the join.  Knowing the bitmask
  ** for all tables to the left of a left join is important.  Ticket #3015.
  **
  ** Note that bitmasks are created for all pTabList->nSrc tables in
  ** pTabList, not just the first nTabList tables.  nTabList is normally
  ** equal to pTabList->nSrc but might be shortened to 1 if the
  ** WHERE_ONETABLE_ONLY flag is set.
  */
  for(ii=0; ii<pTabList->nSrc; ii++){
    createMask(pMaskSet, pTabList->a[ii].iCursor);
    sqlite3WhereTabFuncArgs(pParse, &pTabList->a[ii], &pWInfo->sWC);
  }
#ifndef NDEBUG
  {
    Bitmask toTheLeft = 0;
    for(ii=0; ii<pTabList->nSrc; ii++){
      Bitmask m = sqlite3WhereGetMask(pMaskSet, pTabList->a[ii].iCursor);
      assert( (m-1)==toTheLeft );
      toTheLeft |= m;
    }

  }
#endif

  /* Analyze all of the subexpressions. */
  sqlite3WhereExprAnalyze(pTabList, &pWInfo->sWC);
  if( db->mallocFailed ) goto whereBeginError;

    if( wctrlFlags & WHERE_WANT_DISTINCT ){
      pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE;
    }
  }

  /* Assign a bit from the bitmask to every term in the FROM clause.
  **
  ** The N-th term of the FROM clause is assigned a bitmask of 1<<N.
  **
  ** The rule of the previous sentence ensures thta if X is the bitmask for
  ** a table T, then X-1 is the bitmask for all other tables to the left of T.


  ** Knowing the bitmask for all tables to the left of a left join is
  ** important.  Ticket #3015.
  **
  ** Note that bitmasks are created for all pTabList->nSrc tables in
  ** pTabList, not just the first nTabList tables.  nTabList is normally
  ** equal to pTabList->nSrc but might be shortened to 1 if the
  ** WHERE_ONETABLE_ONLY flag is set.
  */
  for(ii=0; ii<pTabList->nSrc; ii++){
    createMask(pMaskSet, pTabList->a[ii].iCursor);
    sqlite3WhereTabFuncArgs(pParse, &pTabList->a[ii], &pWInfo->sWC);
  }
#ifdef SQLITE_DEBUG


  for(ii=0; ii<pTabList->nSrc; ii++){
    Bitmask m = sqlite3WhereGetMask(pMaskSet, pTabList->a[ii].iCursor);



    assert( m==MASKBIT(ii) );
  }
#endif

  /* Analyze all of the subexpressions. */
  sqlite3WhereExprAnalyze(pTabList, &pWInfo->sWC);
  if( db->mallocFailed ) goto whereBeginError;

        mask |= sqlite3WhereExprUsage(pMaskSet, pSrc->a[i].pOn);
      }
    }
    pS = pS->pPrior;
  }
  return mask;
}














































/*
** 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.
**
................................................................................
                       ** on left table of a LEFT JOIN.  Ticket #3015 */
  }
  pTerm->prereqAll = prereqAll;
  pTerm->leftCursor = -1;
  pTerm->iParent = -1;
  pTerm->eOperator = 0;
  if( allowedOp(op) ){

    Expr *pLeft = sqlite3ExprSkipCollate(pExpr->pLeft);
    Expr *pRight = sqlite3ExprSkipCollate(pExpr->pRight);
    u16 opMask = (pTerm->prereqRight & prereqLeft)==0 ? WO_ALL : WO_EQUIV;
    if( pLeft->op==TK_COLUMN ){
      pTerm->leftCursor = pLeft->iTable;
      pTerm->u.leftColumn = pLeft->iColumn;
      pTerm->eOperator = operatorMask(op) & opMask;
    }else if( prereqLeft!=0 && (prereqLeft&(prereqLeft-1))==0 ){
      int i;
      for(i=0; (prereqLeft>>i)<1; i++){}
      pTerm->leftCursor = pMaskSet->ix[i];
      pTerm->u.leftColumn = -2;
      pTerm->eOperator = operatorMask(op) & opMask;
    }
    if( op==TK_IS ) pTerm->wtFlags |= TERM_IS;
    if( pRight && pRight->op==TK_COLUMN ){


      WhereTerm *pNew;
      Expr *pDup;
      u16 eExtraOp = 0;        /* Extra bits for pNew->eOperator */
      if( pTerm->leftCursor>=0 ){
        int idxNew;
        pDup = sqlite3ExprDup(db, pExpr, 0);
        if( db->mallocFailed ){
................................................................................
        }
      }else{
        pDup = pExpr;
        pNew = pTerm;
      }
      exprCommute(pParse, pDup);
      pLeft = sqlite3ExprSkipCollate(pDup->pLeft);
      pNew->leftCursor = pLeft->iTable;
      pNew->u.leftColumn = pLeft->iColumn;
      testcase( (prereqLeft | extraRight) != prereqLeft );
      pNew->prereqRight = prereqLeft | extraRight;
      pNew->prereqAll = prereqAll;
      pNew->eOperator = (operatorMask(pDup->op) + eExtraOp) & opMask;
    }
  }

        mask |= sqlite3WhereExprUsage(pMaskSet, pSrc->a[i].pOn);
      }
    }
    pS = pS->pPrior;
  }
  return mask;
}

/*
** Expression pExpr is one operand of a comparison operator that might
** be useful for indexing.  This routine checks to see if pExpr appears
** in any index.  Return TRUE (1) if pExpr is an indexed term and return
** FALSE (0) if not.  If TRUE is returned, also set *piCur to the cursor
** number of the table that is indexed and *piColumn to the column number
** of the column that is indexed, or -2 if an expression is being indexed.
**
** If pExpr is a TK_COLUMN column reference, then this routine always returns
** true even if that particular column is not indexed, because the column
** might be added to an automatic index later.
*/
static int exprMightBeIndexed(
  SrcList *pFrom,        /* The FROM clause */
  Bitmask mPrereq,       /* Bitmask of FROM clause terms referenced by pExpr */
  Expr *pExpr,           /* An operand of a comparison operator */
  int *piCur,            /* Write the referenced table cursor number here */
  int *piColumn          /* Write the referenced table column number here */
){
  Index *pIdx;
  int i;
  int iCur;
  if( pExpr->op==TK_COLUMN ){
    *piCur = pExpr->iTable;
    *piColumn = pExpr->iColumn;
    return 1;
  }
  if( mPrereq==0 ) return 0;                 /* No table references */
  if( (mPrereq&(mPrereq-1))!=0 ) return 0;   /* Refs more than one table */
  for(i=0; mPrereq>1; i++, mPrereq>>=1){}
  iCur = pFrom->a[i].iCursor;
  for(pIdx=pFrom->a[i].pTab->pIndex; pIdx; pIdx=pIdx->pNext){
    if( pIdx->aColExpr==0 ) continue;
    for(i=0; i<pIdx->nKeyCol; i++){
      if( pIdx->aiColumn[i]!=(-2) ) continue;
      if( sqlite3ExprCompare(pExpr, pIdx->aColExpr->a[i].pExpr, iCur)==0 ){
        *piCur = iCur;
        *piColumn = -2;
        return 1;
      }
    }
  }
  return 0;
}

/*
** 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.
**
................................................................................
                       ** on left table of a LEFT JOIN.  Ticket #3015 */
  }
  pTerm->prereqAll = prereqAll;
  pTerm->leftCursor = -1;
  pTerm->iParent = -1;
  pTerm->eOperator = 0;
  if( allowedOp(op) ){
    int iCur, iColumn;
    Expr *pLeft = sqlite3ExprSkipCollate(pExpr->pLeft);
    Expr *pRight = sqlite3ExprSkipCollate(pExpr->pRight);
    u16 opMask = (pTerm->prereqRight & prereqLeft)==0 ? WO_ALL : WO_EQUIV;
    if( exprMightBeIndexed(pSrc, prereqLeft, pLeft, &iCur, &iColumn) ){
      pTerm->leftCursor = iCur;






      pTerm->u.leftColumn = iColumn;
      pTerm->eOperator = operatorMask(op) & opMask;
    }
    if( op==TK_IS ) pTerm->wtFlags |= TERM_IS;
    if( pRight 
     && exprMightBeIndexed(pSrc, pTerm->prereqRight, pRight, &iCur, &iColumn)
    ){
      WhereTerm *pNew;
      Expr *pDup;
      u16 eExtraOp = 0;        /* Extra bits for pNew->eOperator */
      if( pTerm->leftCursor>=0 ){
        int idxNew;
        pDup = sqlite3ExprDup(db, pExpr, 0);
        if( db->mallocFailed ){
................................................................................
        }
      }else{
        pDup = pExpr;
        pNew = pTerm;
      }
      exprCommute(pParse, pDup);
      pLeft = sqlite3ExprSkipCollate(pDup->pLeft);
      pNew->leftCursor = iCur;
      pNew->u.leftColumn = iColumn;
      testcase( (prereqLeft | extraRight) != prereqLeft );
      pNew->prereqRight = prereqLeft | extraRight;
      pNew->prereqAll = prereqAll;
      pNew->eOperator = (operatorMask(pDup->op) + eExtraOp) & opMask;
    }
  }

# 2015-08-31
#
# 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 file implements regression tests for SQLite library.  The
# focus of this file is testing indexes on expressions.
#

set testdir [file dirname $argv0]
source $testdir/tester.tcl

do_execsql_test indexexpr1-100 {
  CREATE TABLE t1(a,b,c);
  INSERT INTO t1(a,b,c)
  VALUES('In the beginning was the Word',1,1),
        ('and the Word was with God',1,2),
        ('and the Word was God',1,3),
        ('The same was in the beginning with God',2,1),
        ('All things were made by him',3,1),
        ('and without him was not any thing made that was made',3,2);
  CREATE INDEX t1a1 ON t1(substr(a,1,12));
} {}
do_execsql_test indexexpr1-110 {
  SELECT b, c, '|' FROM t1 WHERE substr(a,1,12)=='and the Word' ORDER BY b, c;
} {1 2 | 1 3 |}
do_execsql_test indexexpr1-110eqp {
  EXPLAIN QUERY PLAN
  SELECT b, c, '|' FROM t1 WHERE substr(a,1,12)=='and the Word' ORDER BY b, c;
} {/USING INDEX t1a1/}
do_execsql_test indexexpr1-120 {
  SELECT b, c, '|' FROM t1 WHERE 'and the Word'==substr(a,1,12) ORDER BY b, c;
} {1 2 | 1 3 |}
do_execsql_test indexexpr1-120eqp {
  EXPLAIN QUERY PLAN
  SELECT b, c, '|' FROM t1 WHERE 'and the Word'==substr(a,1,12) ORDER BY b, c;
} {/USING INDEX t1a1/}


finish_test