SQLite

CollSeq *sqlite3ExprCollSeq(Parse *pParse, Expr *pExpr){
  sqlite3 *db = pParse->db;
  CollSeq *pColl = 0;
  Expr *p = pExpr;
  while( p ){
    int op = p->op;
    if( p->flags & EP_Generic ) break;








    if( (op==TK_AGG_COLUMN || op==TK_COLUMN
          || op==TK_REGISTER || op==TK_TRIGGER)
     && p->pTab!=0
    ){
      /* op==TK_REGISTER && p->pTab!=0 happens when pExpr was originally
      ** a TK_COLUMN but was previously evaluated and cached in a register */
      int j = p->iColumn;
      if( j>=0 ){
        const char *zColl = p->pTab->aCol[j].zColl;
        pColl = sqlite3FindCollSeq(db, ENC(db), zColl, 0);
      }
      break;
    }
    if( op==TK_CAST || op==TK_UPLUS ){
      p = p->pLeft;
      continue;
    }
    if( op==TK_COLLATE || (op==TK_REGISTER && p->op2==TK_COLLATE) ){
      pColl = sqlite3GetCollSeq(pParse, ENC(db), 0, p->u.zToken);
      break;
    }
    if( p->flags & EP_Collate ){
      if( p->pLeft && (p->pLeft->flags & EP_Collate)!=0 ){
        p = p->pLeft;
      }else{
        Expr *pNext  = p->pRight;
        /* The Expr.x union is never used at the same time as Expr.pRight */

    case TK_COLUMN:
    case TK_AGG_FUNCTION:
    case TK_AGG_COLUMN:
      testcase( pExpr->op==TK_ID );
      testcase( pExpr->op==TK_COLUMN );
      testcase( pExpr->op==TK_AGG_FUNCTION );
      testcase( pExpr->op==TK_AGG_COLUMN );
      if( ExprHasProperty(pExpr, EP_FixedCol) ){
        return WRC_Continue;
      }
      if( pWalker->eCode==3 && pExpr->iTable==pWalker->u.iCur ){
        return WRC_Continue;
      }
      /* Fall through */
    case TK_IF_NULL_ROW:
    case TK_REGISTER:
      testcase( pExpr->op==TK_REGISTER );

  /* Check if pExpr is identical to any GROUP BY term. If so, consider
  ** it constant.  */
  for(i=0; i<pGroupBy->nExpr; i++){
    Expr *p = pGroupBy->a[i].pExpr;
    if( sqlite3ExprCompare(0, pExpr, p, -1)<2 ){
      CollSeq *pColl = sqlite3ExprNNCollSeq(pWalker->pParse, p);
      if( sqlite3IsBinary(pColl) ){
        return WRC_Prune;
      }
    }
  }

  /* Check if pExpr is a sub-select. If so, consider it variable. */
  if( ExprHasProperty(pExpr, EP_xIsSelect) ){

                              pCol->iSorterColumn, target);
        return target;
      }
      /* Otherwise, fall thru into the TK_COLUMN case */
    }
    case TK_COLUMN: {
      int iTab = pExpr->iTable;
      if( ExprHasProperty(pExpr, EP_FixedCol) ){
        return sqlite3ExprCodeTarget(pParse, pExpr->pLeft,target);
      }
      if( iTab<0 ){
        if( pParse->iSelfTab<0 ){
          /* Generating CHECK constraints or inserting into partial index */
          return pExpr->iColumn - pParse->iSelfTab;
        }else{
          /* Coding an expression that is part of an index where column names
          ** in the index refer to the table to which the index belongs */

    }else if( strcmp(pA->u.zToken,pB->u.zToken)!=0 ){
      return 2;
    }
  }
  if( (pA->flags & EP_Distinct)!=(pB->flags & EP_Distinct) ) return 2;
  if( ALWAYS((combinedFlags & EP_TokenOnly)==0) ){
    if( combinedFlags & EP_xIsSelect ) return 2;
    if( (combinedFlags & EP_FixedCol)==0
     && sqlite3ExprCompare(pParse, pA->pLeft, pB->pLeft, iTab) ) return 2;
    if( sqlite3ExprCompare(pParse, pA->pRight, pB->pRight, iTab) ) return 2;
    if( sqlite3ExprListCompare(pA->x.pList, pB->x.pList, iTab) ) return 2;
    assert( (combinedFlags & EP_Reduced)==0 );
    if( pA->op!=TK_STRING && pA->op!=TK_TRUEFALSE ){
      if( pA->iColumn!=pB->iColumn ) return 2;
      if( pA->iTable!=pB->iTable 
       && (pA->iTable!=iTab || NEVER(pB->iTable>=0)) ) return 2;

      */
    }else{
      rc = nKey1 - nKey2;
    }
  }
  return rc;
}

/*
** Return true if CollSeq is the default built-in BINARY.
*/
int sqlite3IsBinary(const CollSeq *p){
  assert( p==0 || p->xCmp!=binCollFunc || p->pUser!=0
            || strcmp(p->zName,"BINARY")==0 );
  return p==0 || (p->xCmp==binCollFunc && p->pUser==0);
}

/*
** Another built-in collating sequence: NOCASE. 
**
** This collating sequence is intended to be used for "case independent
** comparison". SQLite's knowledge of upper and lower case equivalents
** extends only to the 26 characters used in the English language.

  }
#endif

  return 1;
}
#endif /* !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW) */

/*
** A structure to keep track of all of the column values that fixed to
** a known value due to WHERE clause constraints of the form COLUMN=VALUE.
*/
typedef struct WhereConst WhereConst;
struct WhereConst {
  Parse *pParse;   /* Parsing context */
  int nConst;      /* Number for COLUMN=CONSTANT terms */
  int nChng;       /* Number of times a constant is propagated */
  Expr **apExpr;   /* [i*2] is COLUMN and [i*2+1] is VALUE */
};

/*
** Add a new entry to the pConst object
*/
static void constInsert(
  WhereConst *pConst,
  Expr *pColumn,
  Expr *pValue
){

  pConst->nConst++;
  pConst->apExpr = sqlite3DbReallocOrFree(pConst->pParse->db, pConst->apExpr,
                         pConst->nConst*2*sizeof(Expr*));
  if( pConst->apExpr==0 ){
    pConst->nConst = 0;
  }else{
    if( ExprHasProperty(pValue, EP_FixedCol) ) pValue = pValue->pLeft;
    pConst->apExpr[pConst->nConst*2-2] = pColumn;
    pConst->apExpr[pConst->nConst*2-1] = pValue;
  }
}

/*
** Find all terms of COLUMN=VALUE or VALUE=COLUMN in pExpr where VALUE
** is a constant expression and where the term must be true because it
** is part of the AND-connected terms of the expression.  For each term
** found, add it to the pConst structure.
*/
static void findConstInWhere(WhereConst *pConst, Expr *pExpr){
  Expr *pRight, *pLeft;
  if( pExpr==0 ) return;
  if( ExprHasProperty(pExpr, EP_FromJoin) ) return;
  if( pExpr->op==TK_AND ){
    findConstInWhere(pConst, pExpr->pRight);
    findConstInWhere(pConst, pExpr->pLeft);
    return;
  }
  if( pExpr->op!=TK_EQ ) return;
  pRight = pExpr->pRight;
  pLeft = pExpr->pLeft;
  assert( pRight!=0 );
  assert( pLeft!=0 );
  if( pRight->op==TK_COLUMN
   && !ExprHasProperty(pRight, EP_FixedCol)
   && sqlite3ExprIsConstant(pLeft)
   && sqlite3IsBinary(sqlite3BinaryCompareCollSeq(pConst->pParse,pLeft,pRight))
  ){
    constInsert(pConst, pRight, pLeft);
  }else
  if( pLeft->op==TK_COLUMN
   && !ExprHasProperty(pLeft, EP_FixedCol)
   && sqlite3ExprIsConstant(pRight)
   && sqlite3IsBinary(sqlite3BinaryCompareCollSeq(pConst->pParse,pLeft,pRight))
  ){
    constInsert(pConst, pLeft, pRight);
  }
}

/*
** This is a Walker expression callback.  pExpr is a candidate expression
** to be replaced by a value.  If pExpr is equivalent to one of the
** columns named in pWalker->u.pConst, then overwrite it with its
** corresponding value.
*/
static int propagateConstantExprRewrite(Walker *pWalker, Expr *pExpr){
  int i;
  WhereConst *pConst;
  if( pExpr->op!=TK_COLUMN ) return WRC_Continue;
  if( ExprHasProperty(pExpr, EP_FixedCol) ) return WRC_Continue;
  pConst = pWalker->u.pConst;
  for(i=0; i<pConst->nConst; i++){
    Expr *pColumn = pConst->apExpr[i*2];
    if( pColumn==pExpr ) continue;
    if( pColumn->iTable!=pExpr->iTable ) continue;
    if( pColumn->iColumn!=pExpr->iColumn ) continue;
    /* A match is found.  Add the EP_FixedCol property */
    pConst->nChng++;
    ExprClearProperty(pExpr, EP_Leaf);
    ExprSetProperty(pExpr, EP_FixedCol);
    assert( pExpr->pLeft==0 );
    pExpr->pLeft = sqlite3ExprDup(pConst->pParse->db, pConst->apExpr[i*2+1], 0);
    break;
  }
  return WRC_Prune;
}

/*
** The WHERE-clause constant propagation optimization.
**
** If the WHERE clause contains terms of the form COLUMN=CONSTANT or
** CONSTANT=COLUMN that must be tree (in other words, if the terms top-level
** AND-connected terms that are not part of a ON clause from a LEFT JOIN)
** then throughout the query replace all other occurrences of COLUMN
** with CONSTANT within the WHERE clause.
**
** For example, the query:
**
**      SELECT * FROM t1, t2, t3 WHERE t1.a=39 AND t2.b=t1.a AND t3.c=t2.b
**
** Is transformed into
**
**      SELECT * FROM t1, t2, t3 WHERE t1.a=39 AND t2.b=39 AND t3.c=39
**
** Return true if any transformations where made and false if not.
**
** Implementation note:  Constant propagation is tricky due to affinity
** and collating sequence interactions.  Consider this example:
**
**    CREATE TABLE t1(a INT,b TEXT);
**    INSERT INTO t1 VALUES(123,'0123');
**    SELECT * FROM t1 WHERE a=123 AND b=a;
**    SELECT * FROM t1 WHERE a=123 AND b=123;
**
** The two SELECT statements above should return different answers.  b=a
** is alway true because the comparison uses numeric affinity, but b=123
** is false because it uses text affinity and '0123' is not the same as '123'.
** To work around this, the expression tree is not actually changed from
** "b=a" to "b=123" but rather the "a" in "b=a" is tagged with EP_FixedCol
** and the "123" value is hung off of the pLeft pointer.  Code generator
** routines know to generate the constant "123" instead of looking up the
** column value.  Also, to avoid collation problems, this optimization is
** only attempted if the "a=123" term uses the default BINARY collation.
*/
static int propagateConstants(
  Parse *pParse,   /* The parsing context */
  Select *p        /* The query in which to propagate constants */
){
  WhereConst x;
  Walker w;
  int nChng = 0;
  x.pParse = pParse;
  do{
    x.nConst = 0;
    x.nChng = 0;
    x.apExpr = 0;
    findConstInWhere(&x, p->pWhere);
    if( x.nConst ){
      memset(&w, 0, sizeof(w));
      w.pParse = pParse;
      w.xExprCallback = propagateConstantExprRewrite;
      w.xSelectCallback = sqlite3SelectWalkNoop;
      w.xSelectCallback2 = 0;
      w.walkerDepth = 0;
      w.u.pConst = &x;
      sqlite3WalkExpr(&w, p->pWhere);
      sqlite3DbFree(x.pParse->db, x.apExpr);
      nChng += x.nChng;
    }
  }while( x.nChng );  
  return nChng;
}

#if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
/*
** Make copies of relevant WHERE clause terms of the outer query into
** the WHERE clause of subquery.  Example:
**
**    SELECT * FROM (SELECT a AS x, c-d AS y FROM t1) WHERE x=5 AND y=10;

      sqlite3TreeViewSelect(0, p, 0);
    }
#endif
    if( p->pNext==0 ) ExplainQueryPlanPop(pParse);
    return rc;
  }
#endif

  /* Do the WHERE-clause constant propagation optimization if this is
  ** a join.  No need to speed time on this operation for non-join queries
  ** as the equivalent optimization will be handled by query planner in
  ** sqlite3WhereBegin().
  */
  if( pTabList->nSrc>1
   && OptimizationEnabled(db, SQLITE_PropagateConst)
   && propagateConstants(pParse, p)
  ){
#if SELECTTRACE_ENABLED
    if( sqlite3SelectTrace & 0x100 ){
      SELECTTRACE(0x100,pParse,p,("After constant propagation:\n"));
      sqlite3TreeViewSelect(0, p, 0);
    }
#endif
  }else{
    SELECTTRACE(0x100,pParse,p,("Constant propagation not helpful\n"));
  }

  /* For each term in the FROM clause, do two things:
  ** (1) Authorized unreferenced tables
  ** (2) Generate code for all sub-queries
  */
  for(i=0; i<pTabList->nSrc; i++){
    struct SrcList_item *pItem = &pTabList->a[i];

#define SQLITE_CountOfView    0x0200   /* The count-of-view optimization */
#define SQLITE_CursorHints    0x0400   /* Add OP_CursorHint opcodes */
#define SQLITE_Stat34         0x0800   /* Use STAT3 or STAT4 data */
   /* TH3 expects the Stat34  ^^^^^^ value to be 0x0800.  Don't change it */
#define SQLITE_PushDown       0x1000   /* The push-down optimization */
#define SQLITE_SimplifyJoin   0x2000   /* Convert LEFT JOIN to JOIN */
#define SQLITE_SkipScan       0x4000   /* Skip-scans */
#define SQLITE_PropagateConst 0x8000   /* The constant propagation opt */
#define SQLITE_AllOpts        0xffff   /* All optimizations */

/*
** Macros for testing whether or not optimizations are enabled or disabled.
*/
#define OptimizationDisabled(db, mask)  (((db)->dbOptFlags&(mask))!=0)
#define OptimizationEnabled(db, mask)   (((db)->dbOptFlags&(mask))==0)

/*
** The following are the meanings of bits in the Expr.flags field.
*/
#define EP_FromJoin  0x000001 /* Originates in ON/USING clause of outer join */
#define EP_Agg       0x000002 /* Contains one or more aggregate functions */
#define EP_HasFunc   0x000004 /* Contains one or more functions of any kind */
#define EP_FixedCol  0x000008 /* TK_Column with a known fixed value */
#define EP_Distinct  0x000010 /* Aggregate function with DISTINCT keyword */
#define EP_VarSelect 0x000020 /* pSelect is correlated, not constant */
#define EP_DblQuoted 0x000040 /* token.z was originally in "..." */
#define EP_InfixFunc 0x000080 /* True for an infix function: LIKE, GLOB, etc */
#define EP_Collate   0x000100 /* Tree contains a TK_COLLATE operator */
#define EP_Generic   0x000200 /* Ignore COLLATE or affinity on this tree */
#define EP_IntValue  0x000400 /* Integer value contained in u.iValue */

    struct CCurHint *pCCurHint;               /* Used by codeCursorHint() */
    int *aiCol;                               /* array of column indexes */
    struct IdxCover *pIdxCover;               /* Check for index coverage */
    struct IdxExprTrans *pIdxTrans;           /* Convert idxed expr to column */
    ExprList *pGroupBy;                       /* GROUP BY clause */
    Select *pSelect;                          /* HAVING to WHERE clause ctx */
    struct WindowRewrite *pRewrite;           /* Window rewrite context */
    struct WhereConst *pConst;                /* WHERE clause constants */
  } u;
};

/* Forward declarations */
int sqlite3WalkExpr(Walker*, Expr*);
int sqlite3WalkExprList(Walker*, ExprList*);
int sqlite3WalkSelect(Walker*, Select*);

#ifdef SQLITE_ENABLE_DESERIALIZE
int sqlite3MemdbInit(void);
#endif

const char *sqlite3ErrStr(int);
int sqlite3ReadSchema(Parse *pParse);
CollSeq *sqlite3FindCollSeq(sqlite3*,u8 enc, const char*,int);
int sqlite3IsBinary(const CollSeq*);
CollSeq *sqlite3LocateCollSeq(Parse *pParse, const char*zName);
CollSeq *sqlite3ExprCollSeq(Parse *pParse, Expr *pExpr);
CollSeq *sqlite3ExprNNCollSeq(Parse *pParse, Expr *pExpr);
int sqlite3ExprCollSeqMatch(Parse*,Expr*,Expr*);
Expr *sqlite3ExprAddCollateToken(Parse *pParse, Expr*, const Token*, int);
Expr *sqlite3ExprAddCollateString(Parse*,Expr*,const char*);
Expr *sqlite3ExprSkipCollate(Expr*);

      if( pExpr->iTable<0 ){
        /* This only happens when coding check constraints */
        sqlite3TreeViewLine(pView, "COLUMN(%d)%s", pExpr->iColumn, zFlgs);
      }else{
        sqlite3TreeViewLine(pView, "{%d:%d}%s",
                             pExpr->iTable, pExpr->iColumn, zFlgs);
      }
      if( ExprHasProperty(pExpr, EP_FixedCol) ){
        sqlite3TreeViewExpr(pView, pExpr->pLeft, 0);
      }
      break;
    }
    case TK_INTEGER: {
      if( pExpr->flags & EP_IntValue ){
        sqlite3TreeViewLine(pView, "%d", pExpr->u.iValue);
      }else{
        sqlite3TreeViewLine(pView, "%s", pExpr->u.zToken);

  if( iCons>=0 && iCons<pIdxInfo->nConstraint ){
    CollSeq *pC = 0;
    int iTerm = pIdxInfo->aConstraint[iCons].iTermOffset;
    Expr *pX = pHidden->pWC->a[iTerm].pExpr;
    if( pX->pLeft ){
      pC = sqlite3BinaryCompareCollSeq(pHidden->pParse, pX->pLeft, pX->pRight);
    }
    zRet = (pC ? pC->zName : sqlite3StrBINARY);
  }
  return zRet;
}

/*
** Add all WhereLoop objects for a table of the join identified by
** pBuilder->pNew->iTab.  That table is guaranteed to be a virtual table.

** by pCCurHint.iTabCur, and an index is being used (which we will
** know because CCurHint.pIdx!=0) then transform the TK_COLUMN into
** an access of the index rather than the original table.
*/
static int codeCursorHintFixExpr(Walker *pWalker, Expr *pExpr){
  int rc = WRC_Continue;
  struct CCurHint *pHint = pWalker->u.pCCurHint;
  if( pExpr->op==TK_COLUMN && !ExprHasProperty(pExpr, EP_FixedCol) ){
    if( pExpr->iTable!=pHint->iTabCur ){
      Vdbe *v = pWalker->pParse->pVdbe;
      int reg = ++pWalker->pParse->nMem;   /* Register for column value */
      sqlite3ExprCodeGetColumnOfTable(
          v, pExpr->pTab, pExpr->iTable, pExpr->iColumn, reg
      );
      pExpr->op = TK_REGISTER;

  aff2 = sqlite3ExprAffinity(pExpr->pRight);
  if( aff1!=aff2
   && (!sqlite3IsNumericAffinity(aff1) || !sqlite3IsNumericAffinity(aff2))
  ){
    return 0;
  }
  pColl = sqlite3BinaryCompareCollSeq(pParse, pExpr->pLeft, pExpr->pRight);
  if( sqlite3IsBinary(pColl) ) return 1;
  return sqlite3ExprCollSeqMatch(pParse, pExpr->pLeft, pExpr->pRight);
}

/*
** Recursively walk the expressions of a SELECT statement and generate
** a bitmask indicating which tables are used in that expression
** tree.

        ** LIKE on all candidate expressions by clearing the isComplete flag
        */
        if( c=='A'-1 ) isComplete = 0;
        c = sqlite3UpperToLower[c];
      }
      *pC = c + 1;
    }
    zCollSeqName = noCase ? "NOCASE" : sqlite3StrBINARY;
    pNewExpr1 = sqlite3ExprDup(db, pLeft, 0);
    pNewExpr1 = sqlite3PExpr(pParse, TK_GE,
           sqlite3ExprAddCollateString(pParse,pNewExpr1,zCollSeqName),
           pStr1);
    transferJoinMarkings(pNewExpr1, pExpr);
    idxNew1 = whereClauseInsert(pWC, pNewExpr1, wtFlags);
    testcase( idxNew1==0 );

/*
** These routines walk (recursively) an expression tree and generate
** a bitmask indicating which tables are used in that expression
** tree.
*/
Bitmask sqlite3WhereExprUsageNN(WhereMaskSet *pMaskSet, Expr *p){
  Bitmask mask;
  if( p->op==TK_COLUMN && !ExprHasProperty(p, EP_FixedCol) ){
    return sqlite3WhereGetMask(pMaskSet, p->iTable);
  }else if( ExprHasProperty(p, EP_TokenOnly|EP_Leaf) ){
    assert( p->op!=TK_IF_NULL_ROW );
    return 0;
  }
  mask = (p->op==TK_IF_NULL_ROW) ? sqlite3WhereGetMask(pMaskSet, p->iTable) : 0;
  if( p->pLeft ) mask |= sqlite3WhereExprUsageNN(pMaskSet, p->pLeft);

# 2018-07-26
#
# 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 the WHERE-clause constant propagation
# optimization.
#
set testdir [file dirname $argv0]
source $testdir/tester.tcl
set ::testprefix whereL

do_execsql_test 100 {
  CREATE TABLE t1(a INT PRIMARY KEY, b, c, d, e);
  CREATE TABLE t2(a INT PRIMARY KEY, f, g, h, i);
  CREATE TABLE t3(a INT PRIMARY KEY, j, k, l, m);
  CREATE VIEW v4 AS SELECT * FROM t2 UNION ALL SELECT * FROM t3;
}
do_eqp_test 110 {
  SELECT * FROM t1, v4 WHERE t1.a=?1 AND v4.a=t1.a;
} {
  QUERY PLAN
  |--MATERIALIZE xxxxxx
  |  `--COMPOUND QUERY
  |     |--LEFT-MOST SUBQUERY
  |     |  `--SEARCH TABLE t2 USING INDEX sqlite_autoindex_t2_1 (a=?)
  |     `--UNION ALL
  |        `--SEARCH TABLE t3 USING INDEX sqlite_autoindex_t3_1 (a=?)
  |--SCAN SUBQUERY xxxxxx
  `--SEARCH TABLE t1 USING INDEX sqlite_autoindex_t1_1 (a=?)
}

# The scan of the t1 table goes first since that enables the ORDER BY
# sort to be omitted.  This would not be possible without constant
# propagation because without it the t1 table would depend on t3.
#
do_eqp_test 120 {
  SELECT * FROM t1, t2, t3
   WHERE t1.a=t2.a AND t2.a=t3.j AND t3.j=5
  ORDER BY t1.a;
} {
  QUERY PLAN
  |--SEARCH TABLE t1 USING INDEX sqlite_autoindex_t1_1 (a=?)
  |--SEARCH TABLE t2 USING INDEX sqlite_autoindex_t2_1 (a=?)
  `--SCAN TABLE t3
}

# Constant propagation in the face of collating sequences:
#
do_execsql_test 200 {
  CREATE TABLE c3(x COLLATE binary, y COLLATE nocase, z COLLATE binary);
  CREATE INDEX c3x ON c3(x);
  INSERT INTO c3 VALUES('ABC', 'ABC', 'abc');
  SELECT * FROM c3 WHERE x=y AND y=z AND z='abc';
} {ABC ABC abc}

# If the constants are blindly propagated, as shown in the following
# query, the wrong answer results:
#
do_execsql_test 201 {
  SELECT * FROM c3 WHERE x='abc' AND y='abc' AND z='abc';
} {}

finish_test